2.2 进程的描述 P35 全考

• 1、进程的定义

  • (1)、进程是程序的一次执行
  • (2)、进程是一个程序及其数据在处理机上顺序执行时所发生的活动
  • (3)、进程是具有独立功能的程序在一个数据集合上运行的过程，它是系统进行资源分配和调度的独立单位
  • 总结：在引入进程实体的概念后，可以把传统OS中的进程定义为“进程是进程实体的运行过程，是系统进行资源分配和调度的一个独立单位。”

• 2、进程的特征

  • (1)动态性。进程的实质是进程实体的执行过程，所有动态性是进程的基本特征。
  • (2)并发性。指多个进程实体同存于内存中，且能在一段时间内同时运行。
  • (3)独立性。指进程实体是一个能独立运行、独立获得资源和独立接受调度的基本单位。
  • (4)异步性 。指进程是按照异步方式运行的，即按各自独立的、不可预知的速度向前推进。

• 3、进程的基本状态及转换

  • 1、进程的三种基本状态

    • (1)、就绪(Ready)状态。指进程已处于准备好运行的状态，指进程已经分配到除CPU外的所有必要资源，只要获取到CPU便可立即执行。
    • (2)、执行(Running)状态。指进程以获取到CPU，其程序正在执行的状态
    • (3)、阻塞(Block)状态。指正在执行的进程由于发生某些事件（如I/O请求、申请缓冲区失败等）暂时无法继续执行的状态，也就是进程的执行收到阻塞。此时会引起进程调度，OS把处理机分配给另一个就绪进程，而让受阻的进程处于暂停的状态，一般将这种状态称为阻塞状态，有时也称为等待状态或封锁状态。

    • 备注：OS将阻塞的进程放进一个队列，这个队列称为阻塞队列

  • 2、三种基本状态的转换

    • 就绪状态的进程，获得处理机之后便可执行，此时转换为执行状态；
    • 执行状态的进程，因为分配的时间片已完，此时转换为就绪状态；
    • 执行状态的进程，因为发送某些事件导致执行受阻，此时转换为阻塞状态；

  • 3、创建和终止状态

    • (1)创建状态：进程是由创建产生的。对于创建状态的进程，当其获得了所需的资源以及对PCB的初始化工作完成后，便可由创建状态转入就绪状态。
    • (2)终止状态：进程自然结束，或是出现了无法克服的错误，或是被操作系统终结，将进入终止状态。

• 4、挂起操作和进程的状态转换

  • 1、什么是挂起

    • 当操作作用于某个进程时，该进程将被挂起，此时进程处于静止状态
    • 如果进程正在执行，将被暂停执行
    • 如果进程处于就绪状态，则该进程暂不接受调度。
    • 与挂起操作相对应的是激活操作

  • 2、挂起操作的引入

    • (1)终端用户的需要。当终端用户在自己的程序运行期间发现有可疑问题，希望暂停自己的程序运行，使之停下来，以便用户研究其直行情况或对程序进行修改。
    • (2)父进程请求。有时父进程希望挂起自己的某个子进程，以便考查和修改该子进程，或者协调各子进程间的活动。
    • (3)负荷调节的需要。当实时系统中的负荷较重，有可能影响到对实时任务的控制时，可由系统把一些不重要的进程挂起，以保证系统能够正常运行。
    • (4)操作系统的需要。操作系统有时希望挂起某些进程，以便检查运行中的资源使用情况或进行记账。

  • 3、引入挂起原语操作后的三个进程状态的转换

    • (1)活动就绪->静止就绪。未被挂起的就绪状态，称为活动就绪。被挂起的就绪状态，称为静止就绪状态，此状态不再被调度执行。
    • (2)活动阻塞->静止阻塞。未被挂起的阻塞状态，称为活动阻塞。被挂起的阻塞状态，称为静止阻塞。处于该状态的进程在其所期待的事件出现之后，又禁止阻塞变为静止就绪状态。
    • (3)静止就绪->活动就绪。静止就绪状态的进程若用激活原语激活后。则转换为活动就绪状态。
    • (4)静止阻塞->活动阻塞。静止阻塞状态的进程若用激活原语激活后。则转换为活动阻塞状态。

  • 4、引入挂起操作后五个进程状态的转换

    • (1)NULL->创建：一个新的进程产生时，处于创建状态。
    • (2)创建->活动就绪：在当前操作系统资源允许的情况下，完成对创建进程的必要操作之后，进程转换为活动就绪状态
    • (3)创建->静止就绪：如果操作系统没有给进程分配所需的资源，则进程转换为静止就绪状态，不参与调度，此时创建进程操作尚未完成。

    • (4)执行->终止：进程执行完，或出现错误，或被系统和其他进程所终结，则转换为终止状态。

      
      
      image.png

• 5、进程管理中的数据结构

  • 1、操作系统中用于管理控制的数据结构

    • 在计算机系统中，对于每个资源和每个进程都设置了一个数据结构，用于表征其实体，称之为资源信息表或进程信息表。其中包含了资源或进程的标识、描述、状态等信息以及一批指针。
    • OS管理这些数据结构一般分为四类：内存表、设备表、文件表、进程表(进程控制块PCB)。

  • 2、进程控制块PCB的作用

    • PCB的作用是使一个在多道程序环境下不能独立运行的程序(含数据)称为一个能够独立运行的基本单位，一个能与其它进程并发执行的进程。

    • (1)作为独立运行基本单位的标志：系统通过PCB感知进程的存在，PCB是进程存在于系统的唯一标志。
    • (2)能实现间断性运行方式：系统可将中断进程的CPU现场信息保存在PCB中，以便进程再次被调度执行时恢复CPU现场时使用。
    • (3)提供进程管理所需的信息：进程的整个生命周期中，操作系统都需要根据PCB实施对进程的控制和管理。
    • (4)提供进程调度所需的信息：PCB存储了进程的状态信息、执行时间和已执行时间等，以便调度使用。
    • (5)实现与其它进程的同步与通信：PCB中具有用于同步的信号量、用于实现进程通信的区域或通信队列指针等。

  • 3、进程控制块中的信息

    • 1、进程标识符：用于唯一的标识一个进程

      • (1)外部标识符：为方便用户(进程)对进程的访问
      • (2)内部标识符：为方便系统对进程的使用，通常为进程的序号

    • 2、处理机状态：也被称为处理机的上下文，主要由处理机的各种寄存器中的内容组成。

      • 寄存器包括：通用寄存器、指令寄存器、程序状态字PSW、用户栈指针
      • 当进程被切换时，处理机状态信息都必须保存在相对应的PCB中，以便该进程重新执行时能再从断点继续执行。

    • 3、进程调度信息：指进程状态及有关调度的信息

      • (1)进程状态：指明当前进程的状态，作为进程调度时和对换时的依据
      • (2)进程优先级：用于描述进程使用处理机的优先级别的一个整数，优先级高的进程应优先获得处理机。
      • (3)进程调度的其他信息：与所采用的的进程调度算法有关，如进程已等待CPU时间总和、进程已执行时间总和等。
      • (4)事件：指进程由执行状态转换为阻塞状态所等待发生的事件，及阻塞原因。

    • 4、进程控制信息：指用于进程控制所必须的信息

      • (1)程序和数据的地址：能够从PCB中通过地址找到程序和数据。
      • (2)进程同步和通信机制：实现进程同步和进程通信时所必须的机制，如消息队列指针、信号量等
      • (3)资源清单：列出了进程执行期间所需的全部资源(CPU除外)，以及一张已分配到资源的清单
      • (4)链接指针：它给出了本进程(PCB)所在队列的下一个进程的PCB的首地址

  • 4、进程控制块的组织方式

    • (1)线性方式

    将系统中所有的PCB都组织在一张线性表中，将该表的首地址存放在内存的一个专用区域中。
    优点：实现简单、开销小
    缺点：每次查找都要扫描整张表，因此适合进程数目不多的系统

    • (2)链接方式

    把具有相同状态的PCB分别通过PCB中的链接字链接成一个队列。
    优点：可以形成就绪队列、若干个阻塞队列和空白队列等。也可以把阻塞状态进程的PCB根据其阻塞状态的原因不同，排成多个阻塞队列，如等待I、O操作完成的队列和等待分配内存的队列。

    • (3)索引方式

    系统根据所有进程状态的不同，建立多张索引表。

• 2.3 进程控制 P42 不考2.3.5 进程的挂起与激活

  • 进程控制主要包括：创建新进程、终止已完成进程、将异常进程转换为阻塞状态、负责进程运行中的状态转换等功能
  • 进程控制一般是由OS的内核中的原语来实现

• 1、操作系统内核

  • 什么是系统内核

  将一些与硬件紧密相关的模块都安排在紧靠硬件的软件层次中，将它们常驻内存，通常被称为OS内核。
  优点：1、便于对这些软件进行保护，防止遭受其他应用程序的破坏；2、可以提高OS的运行效率

  • 处理机的执行状态分为系统态和用户态两种不同的形态：

  (1)系统态：也叫做管态或内核态，具有较高的特权，能执行一切命令，访问所有寄存器和存储区
  (2)用户态：也交目态，是一种具有较低特权的执行状态，能执行规定的指令，访问规定的存储区和寄存器

  • 通常操作系统内核运行在系统态，用户程序运行在用户态

  • 主要功能：

    • 1、支撑功能

    中断处理
    时钟管理
    原语操作

    • 2、资源管理功能

    进程管理
    存储器管理
    设备管理

• 2、进程的创建

  • 创建进程是通过创建原语完成的，被创建的进程称为子进程，创建子进程的进程称之为父进程。
  • 子进程可以创建自己的子进程，从而形成一课有向的进程树，即进程图。
  • 进程创建原语的主要任务是创建进程控制块PCB；步骤为先从PCB集合中申请一个空闲的PCB，再为新进程分配内存等资源，并根据父进程提供的参数和分配到的资源情况来对PCB进行初始化，最后将新进程插入就绪队列。

• 3、进程的终止

  • 进程终止的实质是收回PCB
  • 当进程完成任务或遇到异常情况和外界干预需要结束时，应通过进程终止原语来终止进程。

• 4、进程的阻塞与唤醒

  • 当正在执行的进程需要等待某种事件的完成或本身无任务时，应调用阻塞原语将自己从执行状态转换为阻塞状态。
  • 当阻塞进程所等待的事件完成时，应调用唤醒原语将该进程的状态从阻塞状态转换成就绪状态。

• 2.4 进程同步 P47 不考2.4.5管程机制

  • 进程同步是指对多个相关进程在执行次序上进行协调，目的是使系统中的进程之间能够按照一定的规则(或时序)，共享资源和相互合作，从而使程序的执行具有可再现性。
  • 用来实现同步的机制称为同步机制

• 1、进程同步的基本概念

  • (1)两种形式的制约关系

    • 1、间接相互制约。这种制约主要源于资源共享。
    • 2、直接相互制约。这种制约主要源于进程合作。

  • (2)临界资源和临界区

    • 临界资源：一次只能被一个进程使用的资源称为临界资源
    • 临界区：每个进程中，访问临界资源的那段代码称为临界区
    • 进入区：临界区前用来检查临界资源是否被占用的代码称为进入区
    • 退出区：临界区后用来标志未被访问的代码称为退出区

  • (3)同步机制应遵循的规则

    • 1、空闲让步：临界资源空闲时，应允许一个请求资源的进程立即进入自己的临界区，以便有效利用资源
    • 2、忙则等待：临界资源被占用时，其他请求资源的进程必须等待，以保证临界资源的互斥使用
    • 3、有限等待：任何要求访问临界资源的进程应能在有限的时间进入自己的临界区，以免“死等”
    • 4、让权等待：不能进入临界区的进程应立即释放CPU，以免“忙等”

• 2、硬件同步机制

  • 关中断：是实现互斥最简单的方法之一
  • Test-and-Set指令：使用指令TS（硬件指令-“测试并建立”）来实现互斥
  • Swap：也称为对换指令

• 3、信号量机制

  • 1、整型信号量

    • 一个整型信号量通常对应一类临界资源
    • 是一个非负的共享整数，用来表示该类资源的数目
    • 除了初始化外，只能通过两个标准的原子操作wait（也称作 P）和signal（也称作 V）来访问

    • 整型变量不遵循“让权等待”的规则

      
      
      image.png

  • 2、记录型信号量

    • 除了一个表示资源的数目的整型变量value外，还增加了一个进程链表指针list，用于链接等待该资源的进程

    • 记录型信号量遵循“让权等待”的规则

      
      
      image.png

• 4、信号量的应用

  • 1、利用信号量实现前驱关系：信号量可以用来描述程序或语句之间的前驱关系

  • 2、利用信号量实现互斥：为资源设置互斥信号量mutex

    
    
    image.png

• 2.5 经典进程的同步问题 P60

不考利用管程解决同步问题
不考使用AND型信号量解决同步问题

• 1、生产者-消费者问题

  • 描述了一组生产者与一组消费者，共享一个有界缓冲池，生产者向池中投入产品，消费者从池中取得产品。

    
    
    image.png

• 2、哲学家进餐问题

  image.png

• 3、读者-写者问题

  • 允许多读，但不允许多写，如文件

    
    
    image.png
    
    
    image.png

2.6 进程通信 P67 不考2.6.3 直接传递消息系统实例

• 1、进程通信的类型

  • (1)共享存储器系统：进程之间通过对共享存储区的读写进行数据交换。
  • (2)管道通信：指连接两个进程的一个共享文件。只有在确定了对方存在时才能进行通信。
  • (3)消息传递系统：进程间的数据交互以格式化的消息（网络中称为报文）为单位。
    • 直接通信：源进程直接将消息发送给目标进程
    • 间接通信：进程间需要通过中间实体进行通信，既能实现实时通信也能实现非实时通信
  • (4)客户机-服务器系统：广泛应用于网络环境的各种应用领域，实现方式主要有套接字、远程过程调用、远程方法调用
    • 套接字：
      • 基于文件类型的套接字关联到一个特殊文件，同一台计算机上的通信方式，通过这个特殊文件的读写来实现彼此之间的通信。实现原理类似于管道。
      • 基于网络类型的套接字就是一个通信标识类型的数据结构，是进程通信和网络通信的基本结构。
    • 远程过程调用和远程方法调用
      远程过程（函数）调用RPC是一个通信协议，用于通过网络连接的系统。
      该协议允许运行于一台主机上的进程进行远程调用另一台主机系统上的过程，就如同调用本地过程一样。如果设计软件采用面向对象编程，那么远程过程调用亦可称之为远程方法调用。

• 2、消息传递通信的实现方式

  • 直接消息传递系统

    • 1、直接通信原语：对称寻址方式和非对称寻址方式
    • 2、消息的格式：采用可变长的消息格式
    • 3、进程间的同步方式
    • 4、通信链路

  • 信箱通信

    • 1、信箱的结构：信箱头、信箱体
    • 2、信箱通信原语：邮件的创建和撤销、消息的发送和接收
    • 3、信箱的类型：私有邮箱、公共邮箱、共享邮箱

2.7 线程(Threads)的基本概念 P75 全考*

• 1、线程的引入

  • 目的是为了减少程序并发执行时所付出的时空开销。从而使OS具有更好的并发性。
  • 在多线程OS中，将拥有资源的基本单位与调度和分派的基本单位分开处理，此时一个进程包含一个或多个相对独立的线程，进程只是拥有资源的基本单位，而不再是一个可执行的实体；每个线程都是一个可执行的实体，即CPU调度和分派的基本单位是线程。

  • 线程的优点

  由于线程基本不拥有资源，因此，创建线程时不需要另行分配资源、终止时也不需要进行资源回收，而切换时大大减少了需要保存和恢复的现场信息，因此，线程的创建、终止和切换都比进程迅速，且开销小。
  由于同一个进程内的各个线程可以共享该进程所占用的内存空间和打开的文件，因此，进程间的通信也非常简单和迅速。

  • 线程的创建

  在多线程OS环境下，应用程序启动时，OS将为它创建一个进程，同时为该进程创建第一个线程。在线程运行的过程中，可以线程可以根据需要利用线程创建函数（或系统调用）再去创建若干个线程。所以线程是由线程创建的，但线程间不提供父子关系的支持。

• 2、线程与进程的比较

  • 1、调度的基本单位

    • 传统OS中，进程是作为独立调度和分派的基本单位，因为进程是独立运行的基本单位；每次调度时，都需要进行上下文切换，开销较大
    • 引入线程OS中，线程是作为调度和分派的基本单位，因为进程是独立运行的基本单位；线程切换时，仅需要保存和设置少量寄存器内容，切换代价远低于进程。
    • 同一个进程中，线程的切换不会引起进程的切换。但从一个进程中的线程切换到另一个进程中的线程时，必然引起进程的切换。

  • 2、并发性

    • 在引入线程的OS中，不仅进程之间可以并发地执行，而且在一个进程中的多个线程之间也可以并发执行，甚至运行一个进程中的所有线程都能并发执行。
    • 不同进程中的线程也能并发地执行。这使得OS具有更好的并发性，从而能更加有效的提高系统资源的利用率和系统的吞吐量。

  • 3、拥有资源

    • 进程可以拥有资源，并作为系统中拥有资源的一个基本单位。
    • 线程本身并不拥有资源，而是仅有一点必不可少的、能够保证独立运行的资源。比如每个线程都应具有一个用于控制线程运行的线程控制块TCB、用于指示被执行序列的程序计数器、保留局部变量、少数状态参数和返回地址等的一组寄存器和堆栈。
    • 线程除了拥有自己的少量资源外，还允许多个线程共享该进程的所拥有的资源，
      • 1、属于同一进程的所有线程都具有相同的地址空间，这意味着线程可以访问该地址空间中的每一个虚地址
      • 2、可以访问进程所拥有的资源，如已打开的文件、定时器、信号量机构等的内存空间和它所申请到的I/O设备等

  • 4、独立性

    • 同一个进程内的不同线程之间的独立性要比不同进程之间的独立性低得多。
    • 每个进程都拥有一个独立的空间地址和其他资源，除了共享全局变量外，不允许其他的进程访问。
    • 同一个进程内的不同线程，往往是为了提高并发性以及相互之间的合作而创建的，他们共享进程的内存地址空间和资源，如每个线程都可以访问它们所属进程地址空间的所有地址，如一个线程的堆栈可以被其他线程读写，甚至完全清除。有一个线程打开的文件可以供其他线程读写。

  • 5、系统开销

    • 在创建和撤销进程时，系统都要为之分配和回收进程控制块、分配或回收其它资源，如内存空间和I/O设备等。OS为此所付出的开销，明细大于线程创建或撤销时所付出的开销。
    • 进程切换时涉及到进程上下文的切换，而线程的切换代价远低于进程的
    • 线程间的同步和通信比进程简单
    • 在一些OS中，线程的切换、同步和通信都无需操作系统内核的干预

  • 6、支持多处理机系统

    • 在多处理机系统中，对于传统的进程，即单线程进行，不管有多少处理机，该进程只能运行在一个处理机上。但是对于多线程进程，就可以将一个进程的多个线程分配到多个处理机上，使他们并行执行，这无疑将加速进程的完成。
    • 现代处理机OS中，都无一例外地引入了多线程

• 3、线程的状态与线程控制块

  • 每个线程被创建后，便可与其它线程一起并发地运行。并发运行的线程之间也存在着共享资源和相互合作的制约关系，致使线性在执行时也有间断性。即线程的运行也具有：执行、就绪阻塞三种基本状态。
  • 线程完成工作后，便可正常终止；也会因为其他原因被强行终止。但是有些进程（主要是系统进程），一旦被建立起来之后，便会一直运行下去而不终止。

  • (1)内核支持线程

    • 在核心空间实现
    • 内核为每个线程在核心空间中设置了一个线程控制块，用来登记该线程的线程标识符、寄存器值、状态、优先级等信息。
    • 所有对线程的操作，都通过系统功能调用，有内核中响应的处理程序完成。
    • 优点：
      1、内核可以把同一个进程中的多个线程调度到多个处理器中；
      2、进程中的一个线程被阻塞，内核可以调用同一个进程中的另一个线程；
      3、内核本身也可以使用多线程的方式来实现
    • 缺点：
      1、即使CPU在同一个进程内的多个线程之间切换，也需要陷入内核，因此速度和效率不如用户级线程

  • (2)用户级线程

    • 仅存在于用户空间中，与内核无关
    • 对线程的操作在用户空间中有线程库中的函数（过程）完成
    • 优点：
      1、不需要内核的支持；
      2、切换开销小、速度非常快；
      3、线程库提供多种调度算法给应用程序选择使用。
    • 缺点：
      1、当一个线程因为执行系统调用而阻塞时，将导致对应进程中的所有进程阻塞；
      2、无法享用多处理机系统中多个处理器带来的好处。

  • (3)组合方式

    • 通过时分多路复用技术，用户级线程可以连接到一些内核支持线程上。
    • 可以根据需要灵活的决定，需要多少个内核支持线程与自己的用户级线程多路复用，以达到满意的效果