二、进程管理

处理机管理也称为进程管理，其核心是如何合理地分配出理时间，提高系统地效率。在计算机系统中有多个并发执行程序，采用“程序”这个静态地概念已经不能描述程序执行时动态变化的过程，所以引入了“进程”。

1、基本概念

（1）程序执行时的特征

程序顺序执行时的主要特征如下：

①顺序性：程序的各程序段严格按照规定的顺序执行；

②封闭性：程序运行时系统内的资源只受该程序控制而改变，执行结果不受外界因素的影响。

③可再现性：只要程序执行环境和初始条件相同，多次执行的结果一致。

进程管理-前趋图：

前趋图是用于描述程序执行顺序的一个有向无循环图，由结点和有向边组成，结点代表程序段的操作，而结点间的有向边表示两个程序段操作之间存在的前趋关系（→）。程序段Pi和Pj的前趋关系表示成Pi→Pj，其中Pi是Pj的前趋，Pj是Pi的后继，其含义是Pi执行结束后Pj才能执行。例如，下图为三个程序段，其中输入是计算的前驱，计算是输入的后继。

2、进程的组成

进程（Process）是程序的一次执行，是进行资源分配和调度的基本单位。进程通常由程序、数据和进程控制块（PCB）组成。其中，程序部分描述了进程需要完成的功能。假如，一个程序能被多个进程同时共享执行，那么这部分就应该以可再入码的形式编制，它是程序执行时不可修改的部分。数据部分包括程序执行时所需的数据及工作区，这部分只能为一个进程所专用，是进程的可修改部分；为了描述和控制进程的运行，系统为每个进程定义了一个数据结构——进程控制块（PBC），它是进程重要的组成部分，它记录了进程操作系统所需的、用于描述进程的当前状态和控制进程的全部信息，操作系统根据的PBC来感知进程的存在，并依此对进程进行管理和控制，进程控制块是进程存在的唯一标志。

3、进程的状态及其状态间的切换

（1）三态模型

在多道程序系统中，进程的运行是走走停停，在处理器上交替运行，状态也不断地发生变化，因此进程一般有三种基本状态：运行、就绪和阻塞。

●运行：当一个进程在处理机上运行时，称该进程处于运行状态。显然，对于单机处理系统，处于运行状态的进程只有一个。

●就绪：一个进程获得了除处理机外的一切所需资源，一旦得到处理机即可运行，则称此进程处于就绪状态。

●阻塞：也称为等待或睡眠状态，一个进程正在等待某一事件发生（例如请求I/O、等待I/O完成等）而暂停运行，这时即使把处理机分配给此进程，它也无法运行，称此进程处于阻塞状态。

（2）五态模型

事实上，对于一个实际的系统，进程的状态及其转换将更复杂，三态模型不能够满足我们的需求，所以产生了五态模型。

4、进程控制

进程控制是指对系统中所有进程从创建到消亡的全过程实施有效的控制。在操作系统中通过设置一套控制机构对进程实施控制，其主要功能包括创建一个新进程，撤销一个已经运行完成的进程，改变进程的状态，实现进程间的通信，进程控制是由操作系统内核（Kernel）中的原语实现的。

原语（Primitive）是指由若干条机器指令组成的、用于完成特定功能的程序段。原语的特点是在执行时不能被分割，即原子操作要么都做，要么都不做。内核中所包含的原语主要有进程控制原语、进程通信原语、资源管理原语以及其他原语。

属于进程控制方面的原语有进程创建原语、进程撤销原语、进程挂起原语、进程激活原语、进程阻塞原语以及进程唤醒原语等。

4.1、进程通信

在多道程序环境的系统中，存在多个可并发执行的进程，进程间必然存在资源共享和相互合作的问题。进程间通信是指各个进程交换信息的过程。

4.1.1、同步与互斥

通常，同步是合作进程间的相互依赖和相互制约的问题，与异步互为反义词。互斥是申请临界资源进程间的间接制约问题，与共享互为反义词。

（1）进程间的同步

多个并发执行的进程都以各自独立的、不可预知的速度向前推进，但是有时需要在某些确定点上协调相互合作进程间的工作。例如：进程A向缓冲区传送数据，进程B从缓冲区取数据加工，当进程B要取数据加工时，必须是进程A完成了向缓冲区传送数据的操作，否则进程B必须停下来等待进程A的操作结束。可见，进程间的同步是指进程间完成一项任务时直接发生相互作用的关系。

（2）进程间的互斥

在多道程序系统环境中，各进程可以共享各类资源，但有些资源同一时刻只能供一个进程使用，称为临界资源（Critical Resource，CR）,如打印机、共享变量等。进程间的互斥是指系统中各进程互斥使用临界资源。

（3）临界区管理的原则

临界区（Critical Section，CS）是进程中对临界资源实施操作的那段程序。对互斥临界区管理的4条原则如下：

●有空即进：当无进程处于临界区时，允许进程进入临界区，并且只能在临界区运行有限的时间。

●无空则等：当有一个进程在临界区时，其他需要进入临界区的进程必须等待，以保证进程互斥地访问临界资源。

●有限等待：对要求访问临界资源地进程，应保证进程等待有限时间后进入临界区，以免陷入“饥饿”状态。

●让权等待：当进程不能进入自己的临界区时，应立即释放处理机，以免进程陷入“忙等”状态。

4.1.2、信号量机制（PV操作）（待）

信号量机制是一种有效地进程同步与互斥工具。目前信号量机制有了很大地发展，主要有整型信号量、记录型信号量和信号量集机制。

（1）整型信号量与PV操作

信号量是一个整型变量，根据控制对象的不同被赋予不同的值。信号量分为以下两类：

●公用信号量：实现进程间的互斥，初值为1或资源的数目。

●私用信号量：实现进程间的同步，初值为0或某个正整数。

信号量S的物理意义：若S≧0，表示某资源的可用数；若S<0，则其绝对值表示阻塞队列中等待此资源的进程数。

对系统中每个进程，其工作的正确与否不仅取决于它自身的正确性，而且与它在执行中能与其他相关进程正确地实施同步互斥有关。

PV操作是实现进程同步互斥的常用方法。P操作和V操作是低级通信原语，在执行期间不可分割。其中，P操作表示申请一个资源，V操作表示释放一个资源。

P操作的定义：S=S-1，若S≧0，则执行P操作的进程继续执行；若S<0，则置此进程为阻塞状态（因为无可用资源），并将其插入阻塞队列。

V操作的定义：S=S+1，若S>0，则执行V操作的进程继续执行，若S≦0，则从阻塞状态唤醒一个进程，并将其插入就绪队列，然后执行V操作的进程继续。

（2）利用PV操作实现进程的互斥

令信号量mutex的初值为1，进入临界区时执行P操作，退出临界区时执行V操作。这样，进入临界区的代码段为：P(mutex)；临界区；V(mutex)。

例：两个并发执行的程序段完成交通流量的统计，其中”观察者”P1识别通过的车辆，“报告者”P2定时将观察者的计数值清“0”.用PV操作实现的交通流量统计程序如下：

（3）利用PV操作实现进程的同步

进程的同步时由于进程间的合作而引起的相互制约问题。实现进程同步的一种方法是将一个信号量与消息相联系，当信号量的值为0时表示希望的消息未产生，否则表示希望的消息已经来到。假定用信号量S表示某条消息，进程可以通过调用P操作测试消息是否到达，调用V操作通知消息已准备好。典型的应用是单缓冲区的生产者和消费者同步问题。

例：生产者进程P1不断地生产产品送入缓冲区，缓冲区可以存放一件产品。消费者进程P2不断地从缓存区中取出产品消费，利用PV操作实现进程P1与P2之间地同步问题，需要设置几个信号量，信号量地初值为多少？

解：本题需要设置两个信号量，其中，一个信号量S1，表示缓冲区是否有空闲，初值为1，表示缓冲区空可以将产品送入缓冲区；另一个信号量S2，表示缓冲区有无产品，初值为0。P1和P2的同步过程如图所示：

4.1.3、高级通信

根据进程间通信交换信息量的多少和效率的高低，进程通信的方式为低级方式和高级方式。PV操作属于低级通信方式，若用PV操作实现进程间通信，则存在如下问题：

①编程难度大，通信对用户不透明，即需要用户利用低级通信工具实现进程间的同步与互斥，而且，PV操作使用不当还容易引起死锁。

②效率低，生产者每次只能向缓冲区放一个消息，消费者只能从缓冲区取一个消息。

为了提高通信效率，能传递大量数据，减轻程序的复杂度，系统引入了高级通信方式。高级通信方式主要分为共享存储模式、消息传递模式和管道通信。

• ①共享存储模式：互相通信的进程共享某些数据结构（或存储区），实现进程之间的通信。
• ②消息传递模式(实现通信的方式)：进程间的数据交换以消息为单位，程序员直接利用系统提供的一组通信命令（原语）来实现通信。如Send（A）、Receive（A）。
• ③管道通信：管道是用于连接一个读进程和一个写进程以实现它们之间通信的共享文件（pipe文件）。向管道提供输入的发送进程（即写进程），以字符流的形式将大量的数据送入管道；接收进程可从管道接收大量的数据。

4.1.4、直接和间接通信

直接通信是将消息直接发送给指定进程，因此，Send和Receive原语中应指出进程名字。其调用格式如下：

Send（Who，Message） 发送消息给指定进程或一组进程

Receive（Who,Message） 从约定进程接收消息

间接通信是以信箱为媒体来实现通信的，接收信件的进程只需设立一个信箱，若干个进程都可以向同一个进程发送信件。因此，Send和Receive原语中应给出信箱名。其调用格式如下：

Send（N，M） 将信件M发送到信箱N中

Receive（N，X） 从信箱N中取一封信存入X

`有些系统还提供带标记的发送，用Tag可以指定进程是否要等到接收进程取到信息在继续运行。一般接收进程总是要等待消息到达后才继续运行。其调用格式如下： Send（Who，Message，Tag）`

4.2、进程调度

进程调度方式是指当有更高优先级的进程到来时如何分配CPU。调度方式分为可剥夺和不可剥夺两种。可剥夺式是指当有更高优先级的进程到来时，强行将正在运行的进程的CPU分配给高优先级的进程；不可剥夺式是指当有更高优先级的进程到来时，必须等待正在运行进程自动释放占用的CPU，然后将CPU分配给高优先级的进程。

4.2.1、三级调度

在某些操作系统中，一个作业从提交到完成需要经历高、中、低三级调度。

（1）高级调度：又称为“长调度”、“作业调度”或“接纳调度”，它决定处于输入池中哪个后备作业可以调入主系统做好运行的准备，成为一个或一组就绪进程。系统中一个作业只需经过一次高级调度。

（2）中极调度：又称为“中程调度”或“对换调度”，它决定处于交换区中的就绪进程哪个可以调入内存，以便直接参与对CPU的竞争。在内存资源紧张时，为了将进程调入内存，必须将内存中处于阻塞状态的进程调出至交换区，以便为调入进程腾出空间。这相当于使处于内存的进程和处于盘交换区的进程交换了位置。

（3）低级调度：又称“短程调度”或“进程调度”，它决定处于内存中的就绪进程哪个可以占用CPU，是操作系统中最活跃、最重要的调度程序，对系统影响很大。

4.2.2、调度算法

常用的进程调度算法有先来先服务、时间片轮转、优先级调度和多级反馈调度算法。

（1）先来先服务（First Come First Served，FCFS）

FCFS按照作业提交或进程变为就绪状态的先后次序分配CPU，即每当进入进程调度时，总是将就绪对列队首进程投入运行。FCFS调度法比较有利于长作业和CPU繁忙作业；而不利于I/O繁忙作业。FCFS算法主要用于宏观调度。

（2）时间片轮转

时间片轮转算法主要用于微观调度，其设计目标是提高资源利用率。通过时间片轮转，提高进程并发性和响应时间特性，从而提高资源利用率。时间片的长度可从几个ms到几百ms，选择的方法一般有以下两种：

①固定时间片：分配给每个进程相等的时间片，使所有进程都公平执行，是一种实现简单有效的方法。

②可变时间片：根据进程不同的要求对时间片的大小实时修改，可以更好地提高效率。

（3）优先级调度

优先级调度算法是让每一个进程都拥有一个优先数，通常数值大的表示优先级高，系统在调度时总选择优先级高地占用CPU。优先级调度分为静态优先级和动态优先级。

①静态优先级：进程的优先级在创建时确定，直到进程终止都不会改变。确定优先级的因素有进程类型（系统进程优先级较高）、对资源的需求（如对CPU和内存需求较少的进程优先级较高）和用户要求（如紧迫程度）。

②动态优先级：在创建进程时赋予一个优先级，在进程运行过程中还可以改变，以便获得更好的调度性能。例如：在就绪队列中，随着等待时间增长，优先级将提高。这样，对于一个优先级较低的进程在等待足够的时间后，其优先级提高到可被调度执行。进程每执行一个时间片，就降低其优先级，从而当一个进程持续执行时，其优先级会降低到让出CPU。

（4）多级反馈调度

多级反馈队列算法是时间片轮转算法和优先级算法的综合与发展。其优点是照顾短进程以提高系统吞吐量、缩短了平均周转时间；照顾I/O型进程以获得较好的I/O设备利用率和缩短响应时间；不必估计进程的执行时间，动态调节优先级。

5、死锁

在计算机系统中有各种互斥资源（如磁带机、打印机和绘图仪等）和软件资源（如进程表、临界区等），若两个进程互相要求对方已占用的资源，或同时进入临界区则会出现问题。所谓死锁，是指两个以上的进程互相都要求使用对方已经占有的资源而导致无法继续运行的现象。

进程管理是操作系统的核心，设计不当就会出现死锁问题。如果一个进程在等待一件不可能发生的事，则进程就死锁了。而如果一个或多个进程产生死锁，就会造成系统死锁。

5.1、产生死锁的原因及条件

产生死锁的原因是竞争资源或非法的进程推进顺序。当系统中有多个进程共享的资源不足以同时满足它们的需求时，引起这些进程对资源的竞争导致死锁。由于非法的进程推进顺序，进程在运行过程中，请求和释放资源的顺序不当，导致进程死锁。

产生死锁的4个必要条件为互斥条件、请求保持条件、不可剥夺条件和环路条件。

• （1）互斥条件：进程对其所要求的资源进行排他性控制，即一次只允许一个进程使用。
• （2）请求保持条件：零星的请求资源，即已获得部分资源又请求资源被阻塞。
• （3）不可剥夺条件：进程已获得的资源在未使用完之前不能被剥夺，只能在使用完时由自己释放。
• （4）环路等待条件：当发生死锁时，在进程资源有向图中必然构成环路，其中每个进程占有了下一个进程申请的一个或多个资源。

5.2、死锁的预访：打破四大条件

① 打破互斥资源：共享资源

② 打破保持和等待：进程主动释放资源

③ 打破不可剥夺：系统剥夺其他已分配资源

④ 打破环路等待：使其不构成环路

5.3、死锁的避免

① 有序资源分配法：资源轮流分配，进程依次执行（资源利用率低）。 进程一个一个的执行，多的空间不使用。

② 银行家算法：按照一定的原则进行资源分配（更加灵活）。

资源分配原则：

① 当一个进程对资源的最大需求量不超过系统中剩余资源数时，可以将资源分配给此进程，使其能够正常运行。

② 进程可以分批请求资源，但请求的总数不能超过此进程的最大需求量。

③ 当系统现有的资源不能满足进程尚需资源数时，对进程的资源请求可以推迟分配，但总能使进程在有限时间内得到所需资源。

例题：

假设系统中有三类互斥资源R1、R2、R3，可用资源数量分别是9、8、5。在同一时刻系统中有P1、P2、P3、P4和P5五个进程，这些进程对资源的最大需求量和已分配资源数如下所示，如果进程按（ ）序列执行，那么系统状态是安全的。

解析：

① 求剩下的资源数量：

R1=9-（1+2+2+1+1）=2，R2=8-（2+1+1+2+1）=1，R3=5-(1+1+0+0+3)=0

② 进程运行完成后释放它所占用的资源。