第二、三章 进程、死锁

第三章进程进程的同步和互斥并发性一个进程的顺序性是指每个进程在顺序处理器上的执行是严格按序的，即只有当一个操作结束后，才能开始后续操作。一组进程的并发性是指进程的执行在时间上是重叠的，把这些可交叉执行的进程称为并发进程所谓进程的执行在时间上是重叠的，是指一个进程的第一个操作是在另一个进程的最后一个操作完成之前开始。例：有两个进程A和B，他们分别执行操作a1，a2，a3和b1，b2，b3。在一个单处理器上，进程A和B的执行顺序分别为a1，a2，a3和b1，b2，b3，这是进程的顺序性。如果这两个进程在单处理器上交叉执行，如执行序列为a1，b1，a2，b2，a3，b3或a1，b1，a2，b2，b3，a3等，则说进程A和进程B是并发的。并发的进程可能是无关的，也可能是交往的。无关的并发进程是指他们分别在不同的变量集合上操作，所以一个进程的执行与其他并发进程的进展无关，即一个并发进程不会改变另一个并发进程的变量值。交往的并发进程，它们共享某些变量，所以一个进程的执行可能影响其他进程的结果，因此，这种交往必须是有控制的，否则会出现不正确的结果。两个交往的并发进程，其中一个进程对另一个进程的影响常常是不可预期的，甚至无法再现。因为两个并发进程执行的相对速度无法相互控制，交往进程的速度不仅受到处理器调度的响应，而且还受到与这两个交往的并发进程无关的其他进程的影响，所以一个进程的速度通常无法为另一个进程所知。与时间有关的错误例假设一个飞机订票系统有两个终端，分别运行进程T1和T2。该系统的公共数据区中的一些单元Aj（j=1,2…）分别存放某月某日某次航班的余票数，而x1和x2表示进程T1和T2执行时所用的工作单元。procedureT1(x1)begin

按旅客订票要求找到Ajx1:=Aj;ifx1>=1thenbeginx1:=x1-1;Aj:=x1;procedureT2(x2)begin

按旅游订票要求找到Ajx2:=Aj;ifx2>=1thenbegin

输出一张票

endelse输出“票售完”

end;x2:=x2-1;Aj:=x2;

输出一张票

endelse输出“票售完”

end;进程的定义cobeginrepeatT1(x1)repeatT2(x2)Coend进程的执行t1t2t3t4t5t6t7T1x1:=Ajx1:=x1-1Aj:=x1输出一张票T2x2:=Ajx2:=x2-1Aj:=x2输出一张票t1t2t3t4t5t6t7T1x1:=Ajx1:=x1-1Aj:=x1输出一张票T2x2:=Ajx2:=x2-1Aj:=x2输出一张票按照第一个表的序列执行时，即使两个终端的旅客都要求购买同天同次航班的机票，其结构是正确的。但如果按照第二个表的顺序执行，则两个旅客可能各自都买到同一张同天同次航班的机票，可Aj的值实际上只减去了1，造成余票数的不正确。特别是，余票只有一张时，就可能一张票卖给了两个旅客。例假设有两个并发进程borrow和return分别负责申请和归还主存资源。x表示现有的空闲主存量，B表示申请或归还的主存量。cobegin

repeatborrow(...B,x,...)

repeatreturn(...B,x,...)

coend

procedureborrow(...B,x,...)

varB,x:integer;

begin

ifB>xthen{等待主存资源}

x:=x-B;

{修改主存分配表}

end;

procedurereturn(...B,x,...)

varB,x:integer;

begin

x:=x+B;

{释放等待主存资源者}

{修改主存分配表}

end;若进程borrow在执行了比较B和x指令后，发现B〉x，但在执行{等待主存资源}前，进程return执行，归还了全部主存。这时，由于进程borrow还未成为等待状态，因此，进程return中的{释放等待主存资源者}相当于空操作。以后当borrow被置成等待主存资源状态时，可能已经没有进程来归还主存资源了，从而borrow可能永远等待下去。进程互斥售票管理系统之所以会产生错误，原因在于两个进程交叉访问了共享变量Aj。并发进程中与共享变量有关的程序段称为“临界区”。进程T1的临界区进程T2的临界区procedureT1(x1)begin

按旅客订票要求找到Aj

x1:=Aj;ifx1>=1thenbeginx1:=x1-1;Aj:=x1;procedureT2(x2)begin

按旅游订票要求找到Aj

x2:=Aj;ifx2>=1thenbegin

输出一张票

endelse输出“票售完”

end;

x2:=x2-1;Aj:=x2;

输出一张票

endelse输出“票售完”

end;进程的定义cobeginrepeatT1(x1)repeatT2(x2)Coend进程的执行临界区访问结构入口区临界区退出区进入准则一次仅允许一个进程进入任何时候，处于临界区的进程不可多于一个限时退出不能进入，则让出cpu互斥实现硬件禁止中断用户进程权利过大多处理机无效专用机器指令TestandSetLock,TSL忙式等待操作系统级原语用户级Dekker算法1-5，Peterson算法，置锁算法（例），严格“轮流坐庄”法等不能完全解决多进程互斥，过于复杂，应用困难置锁变量法为每个临界区设置一把锁，开和闭两个状态。关锁，lock(W)执行临界区开锁,unlock(W)问题：忙等信号量E.W.Dijkstra,1965.THE操作系统P、V操作整形信号量P、V操作—整型信号量P(s){ while(s<=0) ;//不执行任何操作

s--;}P操作V(s){ s++;}V操作mutex=1do{ P(mutex);

临界区

V(mutex);

其他代码区}while(1);信号量P、V操作整形信号量忙等，单CPU的多道程序系统中结构型信号量P、V操作—结构型信号量typedefstruct{ intvalue; structPCB*list;};semaphore;Remarks:sispre-defineddatatype,semaphorecanbedeclaredasneeded,eg.vars1,s2:semaphore;信号灯变量S.valueS.listS.valueS.listPCBPCBPCBSemaphores;FIFO信号量可以赋初值，且初值为非负信号量的值可以修改，但只能由P和V操作来访问P操作定义voidP(semaphoreS){ S.value--; if(S.value<0){

把这个进程加到S.list对列；

block(); }}V操作定义voidV(semaphoreS){ S.value++; if(S.value<0){

从S.list对列中移走进程Q；

wakeup(Q); }}信号量P、V操作整形信号量忙等，单CPU的多道程序系统中结构型信号量二值信号量结构型信号量的特例依赖底层硬件体系结构，0、1P、V操作—二值信号量typedefstruct{ enum{false,true}value;//枚举量

structPCB*list;}B_semaphore;定义voidP_B(B_sempaphoreS){ if(S.value==true) S.value=false; else{

把该进程放入S.list对列；

block(); }}P操作voidV_B(B_semaphoreS){ if(S.list==NULL) S.value=true; else{

从S.list对列中移走进程Q；

wakeup(Q); }}V操作实现B_semaphoreS1,S2;intc;//c为信号量S1.value=true;S2.value=false;P_B(S1);c--;if(c<0){ V_B(S1); P_B(S2);}elseV_B(S1);信号量上的P操作P_B(S1);c++;if(c<=0) V_B(S2);elseV_B(S1)信号量上的V操作应用1—用信号量实现进程互斥对打印机的互斥使用使用、空闲信号量mutex用于互斥，初值为1P（mutex）、V(mutex)成对出现，先P，临界区，后V……P（mutex）分配打印机V(mutex)……应用2—用信号量实现进程同步供者和用者对缓冲区的使用供者：空、不空；用者：满、不满

Buffer供者用者供者进程L1:P(S1)

启动读卡机

……

收到输入结果

V(S2);gotoL1;用者进程L2:……

P(S2)

从缓冲区取出信息

V(S1);

加工并且存盘

gotoL2;同步注意事项分析进程的制约关系，确定信号量种类信号量的初值与相应资源的数量有关，也与P，V操作的在程序代码中出现的位置有关同一信号量的P，V操作要“成对”出现，但可分别出现在不同进程代码中。利用信号量机制解经典进程同步问题

经典进程同步问题是从进程并发执行中归纳的典型例子，这些问题常用来测试新的进程同步机制可行性。主要的经典同步问题有生产者-消费者问题、读者-写者问题、哲学家进餐问题等。（1）生产者-消费者问题（producer-consumerProblem）生产者-消费者问题是最著名的同步问题，它描述一组生产者（P1

……Pm）向一组消费者（C1……Cq）提供消息。它们共享一个有界缓冲池（boundedbufferpool）,生产者向其中投放消息，消费者从中取得消息，如下图所示。生产者-消费者问题是许多相互合作进程的一种抽象。利用信号量机制解经典进程同步问题-1

假定缓冲池中有n个缓冲区，每个缓冲区存放一个消息。由于缓冲池是临界资源，它只允许一个生产者投入消息，或者一个消费者从中取出消息。即生产者之间、生产者与消费者之间、消费者之间都必须互斥使用缓冲池。所以必须设置互斥信号量mutex，它代表缓冲池资源，它的数值为1。P1PmC1CqB0B1….…...………Bn-1

利用信号量机制解经典进程同步问题-2

与计算打印两进程同步关系相同，生产者和消费者二类进程P和C之间应满足下列二个同步条件：只有在缓冲池中至少有一个缓冲区已存入消息后，消费者才能从中提取消息，否则消费者必须等待。只有缓冲池中至少有一个缓冲区是空时，生产者才能把消息放入缓冲区，否则生产者必须等待。为了满足第一个同步条件，设置一个同步信号量full，它代表的资源是缓冲区满，它的初始值为0，它的值为n时整个缓冲池满。这个资源是消费者类进程C所拥有，C进程可以申请该资源，对它施加P操作，而C进程的合作进程生产者进程P对它施加V操作。同样为了满足第二个同步条件，设置另一个同步信号量empty，它代表的资源是缓冲区空，它的初始值为n，表示缓冲池中所有缓冲区空。用类并行语言和信号量机制解生产者-消费者问题程序：利用信号量机制解生产者-消费者互斥问题生产者进程Producer：while(TRUE){ P(empty);/*使用一个可用缓冲区

P(mutex);/*互斥进入临界区 产品送往buffer(in); in=(in+1)modN;/*以N为模*/V(mutex);/*退出临界区

V(full);/*多出一个放有产品的 }缓冲区 消费者进程Consumer：while(TRUE){P(full);/*使用一个放产品的缓冲区

P(mutex);/*互斥进入临界区从buffer(out)中取出产品；

out=(out+1)modN;/*以N为模*/V(mutex);/*退出临界区

V(empty);/*多出一个空的}缓冲区(2)哲学家就餐问题Dining-PhilosophersProblemShareddatasemaphorechopstick[5];

ThestructureofPhilosophersiPhilosopher[i]:while(TURE){

思考问题

P(chopstick[i]);P(chopstick[(i+1)mod5]);

进餐

V(chopstick[i]);V(chopstick[(i+1)mod5];}哲学家就餐问题-1此解虽然可以保证互斥使用筷子，但有可能发生死锁。假如五位哲学家同时饥饿而各自拿起左边的筷子时，就会使五个信号量chopstick均为o；当他们再试图去拿右边的筷子时，都将因无筷子可拿而无限期地等待。为防止死锁发生可采取的措施：1.最多允许4个哲学家同时去拿左边的筷子，最终能保证至少有一位哲学家能够进餐，并在用毕时能释放出他用过的两只筷子，从而使更多的哲学家能够进餐。哲学家就餐问题-22.给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之，首先拿右边的筷子。按此规定，将是0、1号哲学家竞争1号筷子；2、3号哲学家竞争3号筷子。即五位哲学家都先竞争奇数号筷子，获得后，再去竞争偶数号筷子，最后总会有一位哲学家能获得两只筷子而进餐。3.仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子。前二个措施读者可用P、V编程解，第三个措施要使用AND型信号量集机制。#defineN5#defineLEFT(i-1)%N#defineRIGHT(i+1)%N#defineTHINKING0#defineHUNGRY1#defineEATING2typedefstruct{/*定义结构型信号量*/intvalue;structPCB*list;}semaphore;intstate[N];semaphoremutex=1;/*互斥进入临界区*/semaphores[N];/*每位哲学家一个信号量*/voidphilosopher(inti){while(TRUE){think(); /*哲学家在思考问题*/take_chopstick(i);/*拿到两根筷子或者等待*/eat(); /*进餐*/put_chopstick(i);/*把筷子放回原处*/}}voidtake_chopstick(inti){P(mutex);state[i]=HUNGRY;test(i);/*试图拿两根筷子*/V(mutex);P(s[i]);}voidput_chopstick(inti){P(mutex);state[i]=THINKING;test(LEFT);//看左邻,现在能否进餐

test(RIGHT);//看右邻,现在能否进餐

V(mutex);}voidtest(inti){if(state[i]==HUNGRY&&state[LEFT]!=EATING&&state[RIGHT]!=EATING){state[i]=EATING;V(s[i]);}}（3）读者-写者问题（Readers/WritersProblem）

一个数据集（如文件）如果被几个并行进程所共享，有些进程只要求读数据集内容，它称读者，而另一些进程则要求修改数据集内容，它称写者，几个读者可以同时读些数据集，而不需要互斥，但一个写者不能和其它进程（不管是写者或读者）同时访问些数据集，它们之间必须互斥，这是读者-写者问题。这里读者和写者之间的互斥是指一群先后读的读者作为一个整体和写者间要互斥，读者群的第一个读者到时就要禁止任何一个写者写，读者群最后一个读者离开后能允许一个写者写。

设置两个信号量：读互斥信号量rmutex和写互斥信号量wmutex。另外设立一个读计数器readcount，它是一个整型变量，初值为0。rmutex：用于读者互斥地访问readcount，初值为1。wmutex：用于保证一个写者与其他读者/写者互斥地访问共享资源，初值为1。读者-写者问题-1读者Readers:while(TRUE){P(rmutex);readcount=readcount+1;if(readcount==1)P(wmutex);V(rmutex);

执行读操作

P(rmutex);readcount=readcount-1;if(readcount==0)V(wmutex);V(rmutex);

使用读取的数据

}写者Writers：while(TRUE){P(wmutex);

执行写操作

V(wmutex);}（4）进程同步的分析

用信号量机制解决进程同步问题需在程序中正确设置信号量和在适当位置安排P、V操作。例如生产者-消费者问题中，用于互斥进入临界区的P（mutex）、V(mutex)语句需紧靠着临界区前和后，而生产者用于同步的P（empty）和V（full）(消费者为P（full）和V(empty))语句相对临界区就在外面一层，格式如上程序所述。如在以上问题中生产者的P（empty）和P(mutex)先后位置对调，相应消费者的P（full）和P（mutex）先后位置也对调，则生产者和消费者在并发执行时，在某个执行序列会出现问题。下面介绍如何寻找会发生问题的那个执行序列，分析方法用下表表示。表左边是生产者和消费者二进程推进序列，此推进序列需用户寻找；表中间是该操作执行后信号量的变化值，表中信号量有mutex、empty和full；表的右边是该操作执行后引起进程PCB的队列变化。表中队列有就绪队列RL，因分别等待mutex、empty、full信号量而阻塞的队列QmL、QeL、和QfL。进程同步的分析-1在表中已找到一个推进序列。该序列先执行消费者进程，由于消费者进程交换了P操作，消费者进程在先后执行P（muyex）和P（full）后阻塞在等待full信号量的队列中。这时只能执行生产者进程，由于生产者进程也交换了P操作，在生产者进程执行了P（mutex）操作后，生产者进程阻塞在等待mutex信号量的队列中。这样生产者和消费者两进程分别阻塞在等待mutex和full信号量的队列，没有进程可以向前推进，系统进入死锁状态。这说明在生产者-消费者问题中对同步信号量和互斥信号量的二个P操作的是不能颠倒，而对互斥信号量和同步信号量的二个V操作的顺序交换影响不大。生产者、消费者交换P操作后发生问题的那个执行序列：进程同步的分析-24．打瞌睡的理发师问题

voidbarber(void){while(TRUE){P(customers);/*如果没有顾客，则理发师打瞌睡*/P(mutex);/*互斥进入临界区*/waiting--;V(barbers);/*一个理发师准备理发*/V(mutex);/*退出临界区*/cut_hair();/*理发（在临界区之外）*/}}4．打瞌睡的理发师问题

voidcustomer(void){P(mutex); /*互斥进入临界区*/if(waiting﹤CHAIRS){waiting++;V(customers); /*若有必要，唤醒理发师*/V(mutex);/*退出临界区*/P(barbers); /*如果理发师正忙着，则顾客打瞌睡*/get_haircut();}elseV(mutex); /*店里人满了，不等了*/}2.7管程管程概念的定义是：一个管程定义一个数据结构和能为并发进程在其上执行的一组操作，这组操作能使进程同步和改变管程中的数据。一个管程由管程名称、局部于管程的共享数据的说明、对数据进行操作的一组过程和对该共享数据赋初值的语句四部分组成。2.7管程2.7管程管程具有以下三个特性：①管程内部的局部数据变量只能被管程内定义的过程所访问，不能被管程外面声明的过程直接访问。②进程要想进入管程，必须调用管程内的某个过程。③一次只能有一个进程在管程内执行，而其余调用该管程的进程都被挂起，等待该管程成为可用的。即管程能有效地实现互斥。2.7管程定义两个条件变量x和y：

conditionx,y;操作wait(x)：挂起等待条件x的调用进程，释放相应的管程，以便供其他进程使用。操作signal(x)：恢复执行先前因在条件x上执行wait而挂起的那个进程。管程的职责与信号量的职责不同。2.8进程通信

进程通信是指进程间的信息交换。各进程在执行过程中为合作完成一项共同的任务，需要协调步伐，交流信息。前面介绍的进程的互斥和同步机构因交换的信息量少，被称为低级进程通信。高级进程通信方式有很多种，大致可归并为共享存储器、消息传递和管道文件三类。2.8进程通信1．共享存储器方式共享存储器方式是在内存中分配一片空间作为共享存储区。需要进行通信的各个进程把共享存储区附加到自己的地址空间中，然后，就像正常操作一样对共享区中的数据进行读或写。通过对共享存储区的访问，相关进程间就可以传输大量的数据。2.8进程通信

2．消息传递方式消息传递方式以消息（Message）为单位在进程间进行数据交换。有两种实现方式：①直接通信方式：发送进程直接将消息挂在接收进程的消息缓冲队列上，接收进程从消息缓冲队列中得到消息。②间接通信方式：发送进程将消息送到称为信箱的中间设施中，接收进程从信箱中得到消息。2.8进程通信

3．管道文件方式管道文件也称管道线，它是连接两个命令的一个打开文件。一个命令向该文件中写入数据，称做写者；另一个命令从该文件中读出数据，称做读者。

$>who|wc-l$>ls–l|wc-l2.8进程通信

2.8.1消息传递系统send和receive的一般格式是：send(destination,message)receive(source,message)2.8.2客户-服务器系统中的通信

常用的进程通信方式有socket和远程过程调用。

1．socketsocket好像一条通信线两端的接插口——

只要通信双方都有插口，并且中间有通信线路相连，就可以互相通信了。一对进程通过网络进行通信要用一对socket，每个进程一个。一个socket在逻辑上有网络地址、连接类型和网络规程三个要素。2.8.2客户-服务器系统中的通信网络地址表明一个socket用于哪种网络连接类型表明网络通信所遵循的模式，主要分为“有连接”和“无连接”模式。网络规程表明具体网络的规程。一般来说，网络地址和连接类型结合在一起就基本上确定了适用的规程。2.8.2客户-服务器系统中的通信2．远程过程调用远程过程调用（RemoteProcedureCall,RPC）是远程服务的一种最常见的形式。第3章死锁内容提要：3.1资源3.2死锁概念3.3死锁的预防3.4死锁的避免3.5死锁的检测和恢复3.6处理死锁的综合方式3.1资源资源是在任何时刻都只能被一个进程使用的任何对象。3.1.1资源使用模式

1．申请

2．使用

3．释放3.1.2可剥夺资源与不可剥夺资源1．可剥夺资源其他进程可以从拥有它的进程那里把它剥夺过去为己所用，并且不会产生任何不良影响。例如，内存就是可剥夺资源。2．不可剥夺资源不能从当前占有它的进程那里强行抢占的资源，必须由拥有者自动释放，否则会引起相关计算的失效。3.1.2可剥夺资源与不可剥夺资源死锁和不可剥夺资源有关。硬件资源软件资源可再用资源（SR）：一次仅供一个进程使用，且可由多个进程重复使用的资源。消耗性资源（CR）：可以被动态创建和毁坏的资源。3.2死锁概念3.2.1什么是死锁1．死锁示例图3-1汽车过窄桥时的冲突3.2.1什么是死锁在计算机系统中，涉及软件、硬件资源的进程都可能发生死锁。生产者进程Producer：消费者进程consumer：

while(TRUE){while(TRUE){P(mutex);P(mutex);P(empty);P(full);

…

…}}3.2.1什么是死锁2．死锁定义死锁是指在多道程序系统中，一组进程中的每一个进程都无限期地等待该组进程中的另一个进程所占有且永远不会释放的资源，这种现象称系统处于死锁状态，简称死锁。处于死锁状态的进程称为死锁进程。计算机系统产生死锁的根本原因就是资源有限且操作不当。一种原因是系统提供的资源太少，另一种原因是进程推进顺序不合适。3.2.1什么是死锁有两个进程A和B，竞争两个资源R和S，这两个资源都是不可剥夺资源。

进程A

进程B

……

……

申请并占用R申请并占用S

申请并占用S申请并占用R

……

……

释放R释放S

释放S释放R

……

……3.2.1什么是死锁

图3-2进程推进顺序对引发死锁的影响3.2.2死锁的条件

当计算机系统同时具备下面4个必要条件时，会发生死锁。1．互斥条件：某个资源在一段时间内只能由一个进程占有，不能同时被两个及以上的进程占有。2．占有且等待条件：进程至少已经占有一个资源，但又申请新的资源。3．不可抢占条件：一个进程所占有的资源在用完之前，其他进程不能强行夺走，只能由该进程主动释放。4．循环等待条件：存在一个进程循环等待环。只要有一个必要条件不满足，则死锁就可以排除。3.2.3资源分配图

1．资源分配图的构成该图由结对组成：G=(V,E)。式中，V是顶点的集合，E是边的集合。顶点集合可分为两部分：P={p1,p2,…,pn}，它由系统中所有活动进程组成；R={r1,r2,…,rm}，它由系统中全部资源类型组成。有向边pi

→rj称为申请边，而有向边rj

→pi称为赋给边。在资源分配图中，通常用圆圈表示每个进程，用方框表示每种资源类型，方框中的圆点表示各个资源单位。3.2.3资源分配图

2．资源分配图示例（如果图中有环路，则有可能存在死锁）图3－3资源分配图示例3.2.3资源分配图

3．环路与死锁①如果每类资源的实体都只有一个，那么图中出现环路就说明死锁了。②如果每类资源的实体不止一个，那么资源分配图中出现环路并不表明一定出现死锁。资源分配图中存在环路是死锁存在的必要条件，但不是充分条件。3.2.3资源分配图

如果资源分配图中没有环路，那么系统不会陷入死锁状态。如果存在环路，那么系统有可能出现死锁，但不确定。

图3-4有死锁的资源分配图图3-5有环路但无死锁的资源分配图3.2.4处理死锁的方法

①利用某些协议预防或避免死锁，保证系统不会进入死锁状态。②允许系统进入死锁状态，然后设法发现并克服它。③完全忽略这个问题，好像系统中从来也不会出现死锁。3.3死锁的预防

基本思想是限制进程对资源的申请，以保证死锁不会发生。3.3.1破坏互斥条件用否定互斥条件的办法是不能预防死锁的，因为某些资源具有不可共享的固有属性。3.3.2破坏占有且等待条件保证一个进程无论什么时候都可申请它没有占有的任何资源。一种办法是预分资源策略静态分配。另一种办法是“空手”申请资源策略。3.3.3破坏非抢占条件

进程当前所占有的全部资源可被抢占。另一种方法是抢占等待者的资源。3.3.4破坏循环等待条件

1.一种方法是实行资源有序分配策略设R={r1,r2,…,rm}，表示一组资源定义一对一的函数F：R→N，式中N是一组自然数。例如，F（磁带机）=1，F（磁盘机）=5，F（打印机）=12做如下约定：所有进程对资源的申请严格按照序号递增的次序进行。2.另一种申请办法也很简单：先弃大，再取小。3.4死锁的避免排除死锁的动态策略—死锁的避免。该方法不限制进程有关申请资源的命令，而是对每个命令进行检查，根据检查结果决定是否进行资源分配。若预测有发生死锁的可能性，则加以避免。3.4.1安全状态在当前分配状态下，进程的安全序列{P1,P2,…,Pn}是这样组成的：若对于每一个进程Pi（1≤i≤n），它需要的附加资源可被系统中当前可用资源与所有进程Pj（j＜i）当前占有资源之和所满足，则{P1,P2,…,Pn}为一个安全序列。这时系统处于安全状态，不会进入死锁状态。3.4死锁的避免死锁是不安全状态中的特例

时刻已占有台数最大需求台数当前可用台数进程P1进程P2进程P3进程P1进程P2进程P3T03229473T13429471T23029—75T33079—70T43009——7T5900———1T6000———10表3-1安全状态示意3.4死锁的避免

表3-2不安全状态示意时刻已占有台数最大需求台数当前可用台数进程P1进程P2进程P3进程P1进程P2进程P3T0′3229473T1′4229472T2′4429470T3′4029—743.4死锁的避免给出安全状态的概念，就可以定义避免死锁或防止进入不安全状态的算法。①死锁状态是不安全状态。②如果系统处于不安全状态，并不意味着它就在死锁状态，而是表示存在导致死锁的危机。③如果一个进程申请的资源当前是可用的，但为了避免死锁，该进程也可能必须等待。此时资源利用率会下降。3.4.2资源分配图算法

单体资源类：某类资源只有一个单位。多体资源类：某类资源有多个单位。如果系统中的资源都是单体资源类，就可以利用资源分配图算法来避免死锁。除申请边和赋给边之外，还要有一种称为“要求边”的新边。要求边pi

rj表示进程pi能够申请资源rj，有时用虚线表示。3.4.2资源分配图算法图3-6资源分配图示例

图3-7处于不安全状态的资源分配图3.4.3银行家算法

针对多体资源类的情况，最著名的避免死锁的算法叫做“银行家算法”（Banker’sAlgorithm）。银行家算法的设计思想是：当用户申请一组资源时，系统必须做出判断；如果把这些资源分出去，系统是否还处于安全状态。若是，就可以分出这些资源；否则，该申请暂不予满足。实现银行家算法的数据结构：

令n表示系统中进程的数目，m表示资源分类数。①Available是一个长度为m的向量，它表示每类资源可用的数量。Available[j]=k，表示rj类资源可用的数量是k。②Max是一个n×m矩阵，它表示每个进程对资源的最大需求。Max[i,j]=k，表示进程pi至多可申请k个rj类资源单位。③Allocation是一个n×m矩阵，它表示当前分给每个进程的资源数目。Allocation[i,j]=k，表示进程pi当前分到k个rj类资源。④Need是一个n×m矩阵，它表示每个进程还缺少多少资源。Need[i,j]=k，表示进程pi尚需k个rj类资源才能完成其任务。可以把矩阵Allocation和Need中的每一行当做一个向量，并分别写成Allocationi和Needi。Allocationi表示当前分给进程pi的资源。1．资源分配算法令Requesti表示进程pi的申请向量。Requesti[j]=k，表示进程pi需要申请k个rj类资源。当进程pi申请资源时，就执行下列动作：①若Requesti＞Needi，表示出错，因为进程对资源的申请大于需求量。②如果Requesti＞Available，则pi等待。③假设系统把申请的资源分给进程pi，则应对有关数据结构进行修改：

Available：=Available–RequestiAllocationi：=Allocationi+RequestiNeedi：=Needi

–Requesti④系统执行安全性算法，查看此时系统状态是否安全。如果是安全的，就实际分配资源，满足进程pi的此次申请；否则，若新状态是不安全的，则pi等待，对所申请资源暂不予分配，并且把资源分配状态恢复成③之前的情况。2．安全性算法①令Work和Finish分别表示长度为m和n的向量，最初，置Work：=Available，Finish[i]：=false，i=1,2,…,n。②搜寻满足下列条件的i值：

Finish[i]=false，且Needi≤Work。若没有找到，则转向④。③修改数据值：

Work：=Work+Allocationi（pi释放所占的全部资源）

Finish[i]=true

转向②。④若Finish[i]=true对所有i都成立（任一进程都可能是pi），则系统处于安全状态；否则，系统处于不安全状态。3．算法应用示例假定系统中有4个进程{A,B,C,D}和三类资源R1,R2和R3，各自的数量分别为9,3和6个单位。

进程AllocationMaxNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A100322222112B511613102C211314103D002422420表3-3T0时刻资源分配表资源情况（1）T0时刻是安全的存在一个安全序列{B,A,C,D}

资源情况WorkNeedAllocationWork+AllocationFinishR1R2R3R1R2R3R1R2R3R1R2R3B112102511623trueA623222100723trueC723103211934trueD934420002936true进程表7-4T0时刻的安全序列（2）进程A请求资源进程A发出请求Request（1,0,1）

资源情况进程MaxAllocationNeedAvailableR1R2R3R1R2R3R1R2R3R1R2R3A322201121011B613511102C314211103011D422002420系统进入不安全的状态为了避免发生死锁，即使当前可用资源能满足某个进程的申请，也有可能不实施分配，让该进程阻塞。表3-5为进程A分配资源后的有关数据3.5死锁的检测和恢复

在实际情况下，通过预防和避免的手段达到排除死锁的目的是很难的。一般提供死锁检测与恢复的方法。死锁检测与恢复是指系统设有专门的机构，当死锁发生时，该机构能够检测到死锁发生的位置和原因，且能通过外力破坏死锁发生的必要条件，从而使并发进程从死锁状态中解脱出来。3.5.1对单体资源类的死锁检测等待图。它是从资源分配图中去掉表示资源类的节点，且把相应边折叠在一起得到的。当且仅当等待图中有环路，系统存在死锁。图3-8资源分配图和对应的等待图3.5.2对多体资源类的死锁检测

等待图不适用于多体资源类的资源分配系统。下面介绍检测算法采用若干随时间变化的数据结构，与银行家算法中所用的结构相似。①Available是一个长度为m的向量，表示每类资源的可用数目。②Allocation是一个n×m的矩阵，表示当前分给每个进程的每类资源的数目。③Request是一个n×m的矩阵，表示当前每个进程对资源的申请情况。检测算法只是简单地调查尚待完成的各个进程所有可能的分配序列。3.5.2对多体资源类的死锁检测

①令Work和Finish分别表示长度为m和n的向量，初始化Work：=Available；对于i=1,2,…,n，如果Allocationi≠0，则Finish