操作系统-第三章 进程管理

1、第三章 进程管理3.1 进程(PROCESS)3.2 进程描述及状态转换3.3 进程控制3.4 进程互斥3.5 进程同步3.6 死锁问题(DEADLOCK)为了描述程序在并发执行时对系统资源的共享，我们需要一个描述程序执行时动态特征的概念，这就是进程。在本章中，我们将讨论进程概念、进程控制和进程间关系。3.1 进程(PROCESS)3.1.1 程序的顺序执行和并发执行3.1.2 进程的引入3.1.3 进程的定义3.1.4 进程和程序及作业的关系返回3.1.1 程序的顺序执行和并发执行程序的执行有两种方式：顺序执行和并发执行。顺序执行是单道批处理系统的执行方式，也用于简单的单片机系统；现在的操作

2、系统多为并发执行，具有许多新的特征。引入并发执行的目的是为了提高资源利用率。1程序的顺序执行及其特性图3.1表示每次仅能调度一个用户作业进行操作的先后次序。输入、计算和打印输出工作只能串行执行，我们可以把程序的执行过程看作是一系列状态转变过程，每执行一个操作，系统就从一种状态变成另一种状态。图中I表示输入操作，P表示处理操作，O表示输出操作。图3.1 顺序处理操作的先后次序顺序执行的特征顺序性：按照程序结构所指定的次序（可能有分支或循环）封闭性：独占全部资源，计算机的状态只由于该程序的控制逻辑所决定可再现性：初始条件相同则结果相同。如：可通过空指令控制时间关系。2资源共享操作系统是用来实现对计

3、算机资源进行管理的一个大型系统程序，其基本特征之一就是资源共享。这里的资源就是指计算机处理一个任务或一个作业时的所有硬设备（处理机、内存、外存、输入/输出设备等）和软设备（文件、程序、数据、信息等）的总称。所谓资源共享，就是指计算机中并发执行的多个程序交替使用计算机硬件和软件资源。操作系统提供了两种实现资源共享的方法 。（1）由操作系统统一管理和分配。（2）由进程自行使用。 3多道系统中程序执行环境的变化1、多道系统运行环境的变化：多个程序同时位于内存中，处于并发状态。在大多数计算问题中，仅要求操作在时间上是部分有序的。有些操作必须在其他操作之后执行，另外有些操作却可以并行地执行。如图3.2所

4、示，其先后次序是：I1先于P1和I2；P1先于O1、P2和I3；O1先于O2，P3部分有序使某些操作的并行执行成为可能，如I2和P1，I3，P2与O1等操作的执行可以在时间上互相重叠I1P1O1I2P2O2I3P3O3作业1图3.2 并行计算的先后次序并发执行的条件：达到封闭性和可再现性例：假设有两个程序P1和P2，其工作过程如下：P1：XX1 P2： XX1 设C1、C2是共享内存的双处理机系统的两个CPU。两个寄存器R1和R2。其中P1在C1上运行，P2在C2上运行，则以下执行顺序在整个执行过程中都有可能发生。并发执行失去封闭性的原因是共享资源的影响，去掉这种影响就行了。如下例说明了并发环

5、境下程序执行对封闭性和可再现性的影响。1）P1：R1X，R1R11，XR1（设X初值为0） P2： R2X， R2R21，XR2 两个程序运行后X的结果为1。2）P1：R1X，R1R11， XR1 P2： R2X， R2R21，XR2 两个程序运行后X的结果为2。 显然，顺序2的结果是正确的，而顺序1产生错误的原因在于X是一个不允许多个程序同时交叉使用的公共变量（变量即内存的一个存储单元）程序并发执行的概念定义：一组在逻辑上互相独立的程序或 程序段在执行过程中，其执行时间在客观上互相重叠，即一个程序的执行尚未结束，另一个的执行已经开始。并发和并行的区别：并行执行指多个程序在多个资源上按独立的、

6、异步的速度执行，程序之间的执行互不影响。而并发则存在多个程序因共享同一资源而互相影响的现象。程序的并发执行带来的影响由于资源的有限性，多个程序在并发执行的过程中必然会对有限的资源进行竞争，从而破坏程序结果的封闭性和可再现性。3.1.2 进程的定义一个具有独立功能的程序对一个数据集在处理机上的一次动态执行过程。2. 进程的特征动态性：进程具有动态的地址空间（数量和内容），地址空间上包括：代码（指令执行和CPU状态的改变）数据（变量的生成和赋值）系统控制信息（进程控制块的生成和删除）独立性：各进程的地址空间相互独立，除非采用进程间通信手段；并发性、异步性：虚拟结构化：代码段、数据段和核心段（在地址

7、空间中）；程序文件中通常也划分了代码段和数据段，而核心段通常就是OS核心（由各个进程共享，包括各进程的PCB）3. 进程与程序的区别进程是动态的，程序是静态的：程序是有序代码的集合；进程是程序的执行。通常进程不可在计算机之间迁移；而程序通常对应着文件、静态和可以复制。进程是暂时的，程序的永久的：进程是一个状态变化的过程，程序可长久保存。进程与程序的组成不同：进程的组成包括程序、数据和进程控制块（即进程状态信息）。进程与程序的对应关系：通过多次执行，一个程序可对应多个进程；通过调用关系，一个进程可包括多个程序。4.进程和作业的关系1、作业是用户向计算机提交任务的实体，有可能全部位于外存，而进程则

8、是完成用户任务的执行实体，总会有一部分位于内存。2、一个作业可由多个进程组成且至少包含一个进程，反之不可。3、作业的概念只存在于批处理系统中。3.2 进程描述及状态转换1进程的结构进程都是由一系列操作（动作）所组成，通过这些操作来完成其任务。因此，不同的进程，其内部操作也不相同。在操作系统中，描述一个进程除了需要程序和私有数据之外，最主要的是需要一个与动态过程相联系的数据结构，该数据结构用来描述进程的外部特性（名字、状态等）以及与其他进程的联系（通信关系）等信息，该数据结构称为进程控制块（PCB，Process Control Block）。 PCB程序段私有数据块图3.5 进程的结构2进程控

9、制块PCB及组织方式（1）进程控制块PCB进程控制块跟踪程序执行过程中的状态，它们表达了进程在当前时刻的状态以及它与其他进程和资源的关系。进程控制块是进程存在的标志，当系统或父进程创建一个进程时，实际上就是为其建立一个进程控制块。进程控制块不但指出了进程的名字，而且也标志出程序和数据集合的物理位置 。进程名当前状态优先数现场保留区指示处于同一状态进程的链指针资源清单进程起始地址家族关系其他图3.6 进程控制块的基本内容（2）进程控制块PCB的组织方式 1）线性表方式：不论进程的状态如何，将所有的PCB连续地存放在内存的系统区。这种方式适用于系统中进程数目不多的情况。 2）索引表方式：该方式是线

10、性表方式的改进，系统按照进程的状态分别建立就绪索引表、阻塞索引表等。 3）链接表方式：系统按照进程的状态将进程的PCB组成队列，从而形成就绪队列、阻塞队列、运行队列等。 PCB的组织方式链表：同一状态的进程其PCB成一链表，多个状态对应多个不同的链表各状态的进程形成不同的链表：就绪链表、阻塞链表索引表：同一状态的进程归入一个index表（由index指向PCB），多个状态对应多个不同的index表各状态的进行形成不同的索引表：就绪索引表、阻塞索引表进程的状态及转换运行状态(Running)：占用处理机资源；处于此状态的进程的数目小于等于CPU的数目。在没有其他进程可以执行时（如所有进程都在阻塞

11、状态），通常会自动执行系统的idle进程（相当于空操作）。就绪状态(Ready)：进程已获得除处理机外的所需资源，等待分配处理机资源；只要分配CPU就可执行。可以按多个优先级来划分队列，如：时间片用完低优，I/O完成中优，页面调入完成高优阻塞状态(Blocked)：由于进程等待某种条件（如I/O操作或进程同步），在条件满足之前无法继续执行。该事件发生前即使把处理机分配给该进程，也无法运行。如：等待I/O操作的完成。状态的转换运行就绪阻塞进程因某事件（如等待I/O完成）变成阻塞状态某事件被解除（I/O完成）时间片已用完进程调度程序把处理机分配给进程（1）（2）（3）（4）状态变化 ：（1）就绪状

12、态变化到运行状态 。（2）运行状态变化到就绪状态。 （3）运行状态变化到阻塞状态。 （4）阻塞状态变化到就绪状态。 3.3 进程控制3.3.1 原语3.4.2 进程控制原语 返回3.3.1 原语的概念原语(primitive)：由若干条指令构成的不可分割的最小程序运行单位，只能在系统态下由系统调用来执行。原语分为两类： 1）机器指令级原语：执行期间不允许中断； 2）功能级原语：允许中断但不允许并发执行。3.3.2 进程控制原语1创建原语2撤消原语3阻塞原语4唤醒原语1、创建原语1）作用：负责进程的创建，被创建的进 程处于就绪态。2）创建过程： a.查找空白PCB块并填入相关参数； b.置进程状

13、态为就绪态并将其放入系统 就绪队列末尾。2、撤销原语1）作用：负责进程的撤销。2）进程撤销的条件： a.该进程已完成其全部功能； b.进程由于错误而终止； c.祖先进程要求撤销某个子进程。3）撤销过程： a.回收进程占用的所有资源； b.回收PCB块。3、阻塞原语1）作用：完成运行态向阻塞态的转换。2）阻塞过程：a.产生中断并保存被阻塞进程的中断现场。b.置被阻塞进程状态为阻塞态并放入阻塞队列末尾。注意：阻塞原语只能由需要阻塞的进程自己来调用(为什么?)。4、唤醒原语1）作用：完成阻塞态向就绪态的转换。2）阻塞过程： a.完成被唤醒进程的状态转换； b.将被唤醒进程放入就绪队列末尾。注意：可由

14、系统进程或事件发生进程来 进行唤醒。3.4 进程互斥3.4.1 进程间的制约关系3.4.2临界资源和临界区3.4.3互斥的加锁实现3.4.4 信号量(semaphore)3.4.5互斥的信号量实现3.4.6 进程互斥举例返回1 进程间的制约关系某些进程必须在另外某些进程后运行1）间接制约：处于并发状态的多个进程由于要共享某个独享型资源而产生的执行速度的制约。2）直接制约：处于并发状态的多个进程要完成同一个任务，由于各个进程之间的协同合作而产生的制约。3）产生制约的原因： a.资源共享 b.进程合作实例： a.有进程p1、p2、p3都需要打印机，而 系统只有一台，由此产生间接制约。 b.有一计算

15、任务：（ab）（cd）， 其中：p1完成ab，p2完成cd，p3 完成p1p2，由此产生直接制约。2 临界资源和临界区1）临界资源：一次仅允许一个进程使用 的资源。2）临界区：访问临界资源的程序段或不允许多个并发进程交叉执行的一段程序。3）临界区设计原则： a.每次至多允许一个进程位于临界区； b.若有多个进程要求进入临界区，应在有限 时间内选择一个进入。 c.进程在临界区内只能停留一定的时间。 3 互斥的加锁实现1）进程互斥：当一个进程正在使用临界资源且尚未使用完毕时，则其他进程必须推迟对该资源的进一步操作，在当前进程的使用完成之前，不能从中插进去使用这个临界资源。或：两个并发的进程A、B，

16、如果当A进行某个操作时，B不能做这一操作，进程间的这种限制条件称为进程互斥。定义:不允许两个以上的共享该资源的并发进程同时进入临界区2）互斥的加锁实现：lock和unlock大部分同步方案均采用某个物理实体（如锁、信号灯等）实现通信，进程通信原语中关锁（lock）和开锁（unlock）是最简单的原语。在这两个原语中设置一个公共变量x代表某个临界资源的状态。如：x=0，表示资源可用，x=1，表示资源正在使用。关锁原语1ock（x）： L：if x1 then goto L else x：=1；开锁原语unlock（x）： x：=0；图3.7 开锁和关锁程序流程图硬件方法的优点适用于任意数目的进程

17、，在单处理器或多处理器上简单，容易验证其正确性可以支持进程内存在多个临界区，只需为每个临界区设立一个布尔变量硬件方法的缺点等待要耗费CPU时间，不能实现让权等待可能饥饿：从等待进程中随机选择一个进入临界区，有的进程可能一直选不上可能死锁4 信号量(semaphore)前面的互斥算法都存在问题，它们是平等进程间的一种协商机制，需要一个地位高于进程的管理者来解决公有资源的使用问题。OS可从进程管理者的角度来处理互斥的问题，信号量就是OS提供的管理公有资源的有效手段。信号量代表某类可用资源实体的数量。 信号量和P、V原语1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(p

18、roberen)和increment(verhogen)），是一种卓有成效的进程同步机制。信号量：在操作系统中代表可用资源的数目，是一个整形变量，其值只能通过P、V原语改变。分类：1）公用信号量：初值为1，用于进程互斥，值域为1（n1），n为需互斥的进程的个数； 2）私用信号量：初值为0或正整数n，用于进程同步，值域范围较公用信号量宽。 P原语wait(s)-s.count;/表示申请一个资源;if (s.count 0)/表示没有空闲资源; 调用进程进入等待队列s.queue; 阻塞调用进程;P原语的执行过程每执行一次P（S）原语操作，信号量S的值减1，然后由OS判定S的值。若S0则进程继续

19、执行，进入临界区；若S0则阻塞该进程，把它插入该信号量的进程等待队列末尾。V原语signal(s)+s.count;/表示释放一个资源；if (s.count 0则进程继续执行；若S0则从该信号量等待队列的队首移出一个进程，把它插入进程就绪队列末尾，等待处理机调度。P、V原语的物理意义（1）S0时的数值表示系统中某类可用 资源的数量。执行一次P原语意味 着进程请求分配一个资源；当Sbuf1;V(S2); PB:P(S2);P(S3);Buf1-buf2;V(S1);V(S4);PC:P(S4);BUF2-PRINTER;V(S3);有编程要求：X=ABC/D； 其中：P1完成AB ，P2完成C

20、/D ，P3 完成P1P2，试用信号量方法完成这3个函数间制约关系的描述。分析:P3与P1、P2之间属于直接制约。信号量设计：S1用于描述P1的事件是否产生 初值为0； S2用于描述P2的事件是否产生， 初值为0；P1:计算；V（）；P:计算；V（）；P:P（S1）；P（S2）；计算；生产围棋的工人不小心把相等数量的黑子和白子混装载一个箱子里，现要用自动分拣系统把黑子和白子分开，该系统由两个并发执行的进程组成，功能如下：（1）进程A专门拣黑子，进程B专门拣白子；（2）每个进程每次只拣一个子，当一个进程在拣子时不允许另一个进程去拣子。分析：第一步：确定进程间的关系。由功能（2）可知进程之间是互斥

21、的关系。第二步：确定信号量及其值。由于进程A和进程B要互斥进入箱子去拣棋子，箱子是两个进程的公有资源，所以设置一个信号量s，其值取决于公有资源的数目，由于箱子只有一个，s的初值就设为1。begin s:semaphore; s:=1; cobegin process A begin L1: P(s); 拣黑子； V(s); goto L1; end; process B begin L2:P(s); 拣白子； V(s); goto L2; end; coend; end;在上例的基础之上再添加一个功能（3）当一个进程A拣了一个棋子（黑子）以后，必让另一个进程B拣一个棋子（白子）。分析：第一步：

22、确定进程间的关系。由功能（1）（2）（3）可知，进程间的关系为同步关系。第二步：确定信号量及其值。进程A和B共享箱子这个公有资源，但规定两个进程必须轮流去取不同色的棋子，因而相互间要互通消息。对于进程A可设置一个私有信号量s1，该私有信号量用于判断进程A是否能去拣黑子，初值为1。对于进程B同样设置一个私有信号量s2，该私有信号量用于判断进程B是否能去拣白子，初值为0。当然也可以设置s1初值为0，s2初值为1。PA： P（S1）； 拣黑子；V（S2）；PB： P（S2）； 拣白子； V（S1）；在公共汽车上，司机和售票员的活动分别是：司机：启动车辆，正常行车，到站停车。售票员：上乘客，关车门，售

23、票，开车门，下乘客。用PV操作对其控制。 分析：第一步：确定进程间的关系。司机到站停车后，售票员方可工作。同样，售票员关车门后，司机才能工作。所以司机与售票员之间是一种同步关系。第二步：确定信号量及其值。由于司机与售票员之间要互通消息，司机进程设置一个私有信号量run，用于判断司机能否进行工作，初值为0。售票员进程设置一个私有信号量stop，用于判断是否停车，售票员是否能够开车门，初值为0。 L1: P(run);启动车辆；正常行车；到站停车；V(stop); L2:上乘客；关车门； V(run); 售票； P(stop); 开车门； 下乘客；有四个进程R1，R2，W1，W2，它们共享可以存放

24、一个数的缓冲器B。进程R1每次把从键盘上读出的一个数存到缓冲器B中，供进程W1打印输出；进程R2每次从磁盘上读一个数存放到缓冲器B中，供进程W2打印输出。为防止数据的丢失和重复打印，问怎样用PV操作来协调这四个进程的并发执行。分析：进程R1和R2各自生产不同的产品要存入共享的缓冲器B中，由于B中每次只能存入一个数，因此，进程R1和R2在存数时必须互斥。进程R1和R2在把数存入B中后应分别发送消息通知进程W1和W2；进程W1和W2在取出数之后应发出缓冲器B中又允许存放一个新数的消息。故进程R1与W1、进程R2与W2之间要同步。信号量：首先应定义一个是否允许进程R1或R2存入缓冲器B的信号量S，初

25、值为“1”；其次，进程R1和R2分别要向进程W1和W2发送消息，要有两个信号量S1和S2来表示相应的消息，初值为“0”。然后进程W1或W2在取出缓冲器B中的数之后只需发出“允许存放一个新数”的消息，通过调用V（S）即可，不必增加新的信号量。R1：P（S）;Data-B;V(S1);R2：P（S）；Data-B;V(S2);W1：P（S1）；B-data;V(S);W2：P（S2）；B-data;V(S);4.5 进程间通信(IPC, INTER-PROCESS COMMUNICATION)4.5.0 进程间通信的类型4.5.1 信号(signal)4.5.2 共享存储区(shared memo

26、ry)4.5.3 管道(pipe)4.5.4 消息(message)4.5.5 套接字(socket)返回4.5.0 进程间通信的类型低级通信：只能传递状态和整数值（控制信息），包括进程互斥和同步所采用的信号量和管程机制。优点的速度快。缺点是：传送信息量小：效率低，每次通信传递的信息量固定，若传递较多信息则需要进行多次通信。编程复杂：用户直接实现通信的细节，编程复杂，容易出错。高级通信：能够传送任意数量的数据，包括三类：共享存储区、管道、消息。返回1. 低级通信和高级通信2. 直接通信和间接通信直接通信：信息直接传递给接收方，如管道。在发送时，指定接收方的地址或标识，也可以指定多个接收方或广播

27、式地址；在接收时，允许接收来自任意发送方的消息，并在读出消息的同时获取发送方的地址。间接通信：借助于收发双方进程之外的共享数据结构作为通信中转，如消息队列。通常收方和发方的数目可以是任意的。3. 高级通信的特征通信链路(communication link)：点对点/多点/广播单向/双向有容量（链路带缓冲区）/无容量（发送方和接收方需自备缓冲区）数据格式：字节流(byte stream)：各次发送之间的分界，在接收时不被保留，没有格式；报文(datagram/message)：各次发送之间的分界，在接收时被保留，通常有格式（如表示类型），定长/不定长报文，可靠报文/不可靠报文。收发操作的同步方

28、式发送阻塞（直到被链路容量或接收方所接受）和不阻塞（失败时立即返回）接收阻塞（直到有数据可读）和不阻塞（无数据时立即返回）由事件驱动收发：在允许发送或有数据可读时，才做发送和接收操作4.6 死锁问题(DEADLOCK)4.6.1 概述4.6.2 死锁的预防4.6.2 死锁的检测4.6.3 死锁的避免4.6.4 解决死锁问题的综合方法返回1 死锁产生的原因和必要条件在许多中型和大型计算机系统中，都期望在各级系统和用户程序上具有动态共享资源、并发程序设计及进程通信这些操作特征，来改善系统资源的利用率和提高系统的处理能力。由于资源的占用往往是互斥的，因此当某个进程提出申请资源后，使得有关进程在无外力

29、协助下，永远分配不到必需的资源而无法继续运行，这就产生了一种特殊的现象死锁。 死锁的定义死锁是指计算机系统或进程所处的一种状态,即两个或多个进程无限期地等待永远不会发生的条件。先来看一个申请不同类型资源的死锁例子，假定有两个进程Pl和P2都要修改文件F，修改时都需要一条暂时存放信息的磁带，而只有一台磁带机T可用。又假定由于某种原因，在进行修改之前，P2需要一暂存磁带（例如为了修改，要重新组织输入数据）。设F和T都是可重用资源，它们分别表示允许更新文件和允许使用磁带机。于是Pl和P2可有如下形式： 进程P1 进程P2 ： ： 申请文件F 申请磁带机T r1：申请磁带机T r2：申请文件F 释放磁

30、带机T 释放文件F 释放文件F 释放磁带机T TFP1P2请 求 配分已请 求 配 分已图3.13 简单的死锁例子R P1P2P3 分配 申请图3.14 同类资源共享时的死锁现象由以上诸例子可知，产生死锁现象的原因，一是系统提供的资源不能满足每个进程的使用，即系统资源不足；二是在多道程序运行时，进程推进顺序不合理，即进程推进顺序非法。死锁的必要条件：（1）互斥条件。 （2）不剥夺条件。 （3）请求和保持条件。 （4）环路等待条件。 解决死锁问题的策略1利用假脱机技术，变独享资源为共享资源；2采用可剥夺的资源使用方式；3采用资源的预先全部分配方式；4. 采用有控资源分配方法。死锁的预防1、资源预

31、分配法 每个用户向系统提交作业时，需一次性说明所需要的资源；并且作业调度程序只能在满足作业所需的全部资源的前提下才能将它投入运行。 当资源一旦分配给该作业后，在其整个运行期间这些资源为它独占。资源预分配法的缺点1、用户在作业运行前可能不能提出该作业运行所需的全部资源；2、资源利用率很低；3、作业等待时间较长；4、系统吞吐量很低；死锁预防方法22、有序资源分配法 该方法给系统中所有资源给定一个唯一的编号，所有的分配请求必须以上升的次序进行，系统要求每个进程： 1）对它所必须使用的而且属于同一类的所有资源，必须一次申请完； 2）在申请不同类的资源时，必须按各类资源的编号依次请求。死锁预防方法3银行

32、家算法 该算法在有进程提出资源分配请求时，首先检查申请者对各类资源的最大需求量，如果系统现存的各类资源可以满足当前它对各类资源的最大需求量时，就满足它的请求。 即：仅当申请者可以在一定时间内无条件地归还它所申请的全部资源时，才能将资源分配给它。银行家算法示例假设系统有三个进程p，q，r，系统只具有某类资源10个，目前分配情况如下： 进程 已占资源个数 还需资源个数 p 4 4 q 2 2 r 2 7 此时，p，r再申请资源系统就不能进行分配了，因为目前只剩下2个资源，不能满足它们的最大需求，如果将剩余2个资源分配给p或r，就会形成： 进程 已占资源个数 还需资源个数 p 4 或5或6 4或3或

33、2 q 2 2 r 2 或3或4 7或6或5 此后，3个进程再提出资源请求系统就无法满足了，结果就产生了死锁。 而如果等q提出请求却可以满足它，因为它只需要2个资源就可运行结束，系统此时能够满足它的最大需求。等它运行结束后就能满足p的最大要求对p进行分配。最后再对r进行分配，这样就不会产生死锁。银行家算法的数据结构包括：可用资源向量Available 最大需求矩阵Max分配矩阵Allocation需求矩阵Need 银行家算法如下：设Requesti是进程Pi的请求向量，Requesti (j)=k表示进程Pi请求分配Rj类资源k个，当Pi发出资源请求后，系统按照下列步骤进行检查。（1）若Req

34、uestiNeed，则执行步骤（2）；否则系统会因为它所需要的资源数已超过它要求的最大值而认为出错。（2）若RequestiAvailable，则执行步骤（3）；否则系统会因为系统中尚无足够的资源满足Pi的申请而使进程Pi等待。（3）系统试探地把资源分配给进程Pi并修改如下数据结构中的值：Available=Available-RequestiAllocationi=Allocationi+RequestiNeedi=Needi-Requesti（4）系统执行安全算法，检查此次资源分配后，系统是否处于安全状态。若是则系统才真正将资源分配给进程Pi以完成本次分配；若不是则系统将试探分配其他进程。

35、系统所执行的安全性算法描述如下： （1）设置两个向量：Work和Finish。 （2）从进程集合中找到一个能满足下述条件的进程： Finish(i)=false NeediWork（3）当进程Pi获得资源后可顺利执行直到完成，然后释放分配给它的资源，并作如下工作： Work=Work+Allocation Finish(i)=true（4）若所有进程的Finish(i)的值都为true，则说明系统处于安全状态；否则系统处于不安全状态。银行家算法实例1、假定系统中有5个进程P0，P1，P2，P3，P4和三种类型的资源A，B，C，每一种资源的数量分别为10、5、7，在T时刻的资源分配情况如下：已分

36、配的资源数尚需的资源数系统T时刻剩余资源数ABCABCABCp00 10743332p1200122p2302600p3211011p4002431试问：（1）T时刻的状态是否安全，并说明原因； （2）如果进程P1提出请求Request1(1，0，2)，请说明系统能否将资源分配给它？ （3）如果进程P4提出请求Request4(3，3，0)，请说明系统能否将资源分配给它？ 死锁的解除（1）资源剥夺法。1）还原算法。即恢复计算结果和状态。2）建立检查点主要是用来恢复分配前的状态。 （2）撤消进程法。1）程序的优先数，即被撤消进程的优先数。2）作业类的外部代价 3）运行代价，即重新启动它并运行到当

37、前撤消点所需要的代价。 哲学家就餐问题有5个哲学家P1,P2,P3,P4 ,P5围坐在一张圆桌旁，桌中央有一盘通心面，每人面前有一个空盘子 ，另有5把叉子f1，f2,f3,f4,f5分别放在两人之间，如图7.5所示。每个哲学家做两件事:思考问题和吃通心面 ，当思考问题时放下叉子，想吃通心面时，必须获得2把叉子 ，且每人只能直接从自己的左右两边取叉子，吃过后放下叉子以便别人使用。 方法一void philosopher(int i)while (TRUE) think( );take_fork(i);take_fork(i+1) % N);eat( );put_fork(i);put_fork(

38、i+1) % N);分析：当出现以下情形，在某一个瞬间，所有的哲学家都同时启动这个算法，拿起左侧的筷子，而看到右侧筷子不可用，又都放下左侧筷子，等一会儿，又同时拿起左侧筷子如此这样永远重复下去。对于这种情况，所有的程序都在运行，但却无法取得进展，即出现饥饿，所有的哲学家都吃不上饭。 方法二原理：至多只允许四个哲学家同时进餐,以保证至少有一个哲学家能够进餐,最终总会释放出他所使用过的两支筷子,从而可使更多的哲学家进餐。以下将room 作为信号量，只允许4 个哲学家同时进入餐厅就餐，这样就能保证至少有一个哲学家可以就餐，而申请进入餐厅的哲学家进入room 的等待队列，根据FIFO 的原则，总会进入

39、到餐厅就餐，因此不会出现饿死和死锁的现象。semaphore chopstick5=1，1，1，1，1;semaphore room=4;void philosopher(int i)while(true)think();wait(room); /请求进入房间进餐wait(chopsticki); /请求左手边的筷子wait(chopstick(i+1)%5); /请求右手边筷子eat();signal(chopstick(i+1)%5); /释放右手边的筷子signal(chopsticki); /释放左手边的筷子signal(room); /退出房间释放信号量room方法三原理：仅当哲学家的左右两支筷子都可用时,才允许他拿起筷子进餐。方法1：利用AND 型信号量机