1、第三章进程之间的并发控制和死锁进程通信进程通信进程的状态是进程的状态是基于一定的原因基于一定的原因和和条件条件而变而变化的，而这些原因和条件又常常是由于进化的，而这些原因和条件又常常是由于进程之间的相互制约关系引起的。系统中诸程之间的相互制约关系引起的。系统中诸进程之所以有这种关系，是由进程之所以有这种关系，是由两方面原因两方面原因引起的：引起的：各并发进程对资源的共享各并发进程对资源的共享系统中存在若干协作进程系统中存在若干协作进程1、各并发进程对资源的共享 互斥关系：通过共享资源而使进程之间产生的关系叫间接制约关系，又叫互斥关系。可用“进程资源进程”来描述。例：进程P1和P2在运行中都要使
2、用打印机，为了使各进程输出的完整性，打印机的使用必须独占。一旦系统将打印机分配给进程P1，那么进程P2必须等待，等待P1使用完打印机并释放后，才能使用。2、系统中存在若干协作进程 同步关系：同步关系：通常，一个用户作业涉及一组并发进程（输入、计算和输出进程），这些进程须相互协作完成这项任务。在运行过程中，这些进程可能要在某些同步点上等待协作者发来信息后才能继续运行。进程之间的这种制约关系叫直接制约关系。又叫同步关系。可用“进程进程”来描述进程通信：进程通信：是指进程的上述相互依赖关系。进程之间的这种相互依赖又相互制约、相互合作又相互竞争的关系，也即进程的同步与互斥关系。互斥是同步的一个特例。进
3、程之间的这种关系就叫进程的低级通信。一、进程之间的互斥一、进程之间的互斥（进程的互斥是由于共享资源而引起的）共享资源：慢速的硬件设备，如打印机、磁带机等资源软件资源，如共享变量、共享文件等临界资源（critical resource）：就是一次仅允许一个进程使用的资源。如：打印机临界区（critical section）：就是并发执行的进程访问临界资源的那个必须互斥执行的程序段程序程序1Y=Y+1output程序程序2Y=Y+2output内存共享区内存共享区Ypcb1pcb2 为了正确而有效地使用临界资源，系统中的并发进程需要遵循如下四个准则四个准则：空闲让进空闲让进无进程在临界区就允许进入
4、忙则等待忙则等待有进程在临界区，则等待有限等待有限等待多进程要求进入临界区是，应该让某一个进入，而不能无限等待都不让进让权等待让权等待等待的进程必须释放CPU1、关中断二、解决进程之间互斥的方法二、解决进程之间互斥的方法解决思想在临界区中防止发生进程调度保证临界区操作的完整性方法分析用户控制系统中断是非常危险的本方法对多个CPU系统将失去作用2、在原语里设置一个公共变量代表临界资源的状态。x=x=使用临界资源必须做如下三步：1、检查锁的设置2、进入临界区，访问临界区3、释放临界资源，开锁资源可用资源正在使用011,0,1x关锁：资源可用继续测试资源正在使用二、解决进程之间互斥的方法二、解决进程
5、之间互斥的方法锁机制框图测试x=0?Lockx,x=1进入临界区退出临界区Unlockx,x=0返回继续测试x=1x=0返回三、进程之间的同步三、进程之间的同步同步原因：同步原因：一组进程要合作完成一项任务。例：两个用户进程通过共享缓冲区完成其计算和打印任务。计算进程负责将计算结果送入共享缓冲区，打印进程从缓冲区取数据打印。当缓冲区空时，不允许取数据，满时不允许送数据。否则，将出现错误。计算进程与打印进程这种制约关系，不是由于两个进程同时访问共享缓冲区，而是由于它们访问缓冲区时的速度不匹配造成的。为了使进程同步，需要引入信号量机制。四、信号量四、信号量1965年，荷兰学者Dijkstra提出的
6、。基本原理：两个或多个进程可以通过简单的信号进行合作，一个进程可以被迫在某一位置停止，直到它接收到一个特定的信号。任何复杂的合作需求通过适当的信号结构得到满足。为此，需要使用一个称作为信号量的特殊变量，以便通过信号量传送信号。信号量是一个数据结构定义如下：struct semaphore int value;Pointer_PCB queue;对信号量S的操作只允许执行P、V操作。其中P/V操作由原语组成，执行过程中不可分割。P P操作原语操作原语P(S)P(S)1）S:=S 1 /请求一个资源2）If S=0,go on;if S0,go on;if Sready,go on /表示在信号链
7、表，仍有等待该资源的进程，调用唤醒原语。显然，P、V操作的引入，克服了加锁操作的忙等待现象，有效提高了系统的效率操作系统正是利用信号量的状态对进程和资源进行管理和控制的。从物理意义上理解，P操作相当于申请资源；V操作相当于释放资源。1 1、利用信号量实现进程之间的互斥引入一个互斥信号量，用mutex表示。对于互斥使用的资源，其信号量的初值为1欲进入临界区执行的进程须先对互斥信号量mutex执行P操作若已有进程占有临界资源，进程必须等待，直到临界资源空闲为止；若无进程占用，可使用它进程完成临界区操作（即临界资源使用完）后，通过执行V操作释放临界资源，供其它进程使用P/VP/V操作实现进程间互斥输
8、入进程输入进程AP(s)读消息到缓冲区读消息到缓冲区V(s)输出进程输出进程BP(s)从缓冲区取走消息从缓冲区取走消息V(s)用信号量可以方便地解决n个进程互斥地使用临界区的问题。信号量的取值范围是+1（1-n)。信号量的值为负时，说明一个进程正在临界区执行，其它的正排在信号量等待队列中等待，等待的进程数等于信号量值的绝对值例：若P、V操作的信号量初值为1，当前值为-3，则表示3个等待进程。2 2、利用信号量实现进程之间的同步、利用信号量实现进程之间的同步是指相互合作的一组共行进程，各自以独立的，不可预知的速度向前推进，在前进过程中彼此之间需要相互协调步伐，才能更好地完成统一项任务。这些进程互
9、相合作，在一些关键点上可能需要互相等待或互通消息。为了解决进程的同步，同样也可以引入信号量P/VP/V操作实现进程间同步操作实现进程间同步用信号量实现计算进程与打印进程之间的同步过程。假定计算进程和打印进程共同使用。当时，计算的结果没有送入缓冲区，打印进程不能执行打印操作。一旦计算机把计算结果送入缓冲区后，就应给打印进程打印进程收到该信号后，便可从缓冲区取出计算结果进行打印。在，计算进程也不能把下一次的计算结果送入缓冲区。只有在打印进程打印完缓冲区中的内容，计算进程才能将下一次的计算结果送入缓冲区。因此，计算进程和打印进程也是同步的。为此，引入两个同步信号量s1和s2。S1：表示缓冲区是否空，
10、s1的初值为1;S2：表示缓冲区中是否有可供打印的计算结果，其初始值为0。计算进程计算进程(Pc)(Pc)和打印进程打印进程(Pp)(Pp)之间的同步算法如下：intint s1,s2;s1,s2;s1=1;s2=0;s1=1;s2=0;void void Pc()/Pc()/*计算进程计算进程*/while(TRUEwhile(TRUE)computer next number computer next number p(s1);p(s1);add the number to buffer add the number to buffer v(s2);v(s2);void Pp()/voi
11、d Pp()/*打印进程打印进程 */while(TRUEwhile(TRUE)p(s2);p(s2);take next number from buffer take next number from buffer v(s1);v(s1);print the number print the number void main()void main()parbegin(Pc,Ppparbegin(Pc,Pp););两个经典的同步两个经典的同步/互斥问题互斥问题-生产者和消费者问题假定有一组生产者和一组消费者进程，通过假定有一组生产者和一组消费者进程，通过一个有界缓冲区发生联系一个有界缓冲区发
12、生联系。正常情况下，生产者将生产的产品放入缓冲区，消费者从缓冲区取用产品。当缓冲区满时，生产者要等消费者取走产品后才能向缓冲区放下一个产品；当缓冲区空时，消费者要等生产者放一个产品入缓冲区后才能从缓冲区取下一个产品。inout01n-1同步问题：同步问题：生产者进程不能往生产者进程不能往“满满”的缓冲区中放置产品的缓冲区中放置产品 消费者进程不能从消费者进程不能从“空空”的缓冲区中取产品的缓冲区中取产品 设有界缓冲区的容量为设有界缓冲区的容量为n n。为了正确地存取缓冲区，要求各生产者与消费者进程互斥地使用缓冲区互斥地使用缓冲区。为此，要设两个同步两个同步信号量信号量分别标识生产者进程和消费者
13、进程能否正确前进的标志。用empty表示空缓冲个数，初值为n；用full表示装满产品的缓冲个数，初值为0。再设置一个互斥使用临界区的信号量mutex，初值为1。两者的同步算法如下：生产者消费者算法生产者消费者算法-1-1var mutex,empty,full:semaphore;mutex:=1;实现互斥访问的互斥信号量empty:=n;full:=0;空缓冲区和装满产品的缓冲区的个数buffer:array0.n-1 of product;环形队列缓冲区in,out,goods:integer in:=0;out:=0;指向空缓冲区和装满产品的缓冲区begin cobegin 并发进程 p
14、roducer和consumer producer;consumer;coend end生产者消费者算法生产者消费者算法-2-2procedure producer;生产者 begin while true do beginproduce next product;生产一个产品productP(empty);请求将产品存入空的缓冲区P(mutex);请求独占使用缓冲区资源buffer(in):=product;产品送入空缓冲区in:=(in+1)mod n;in指针移动到下一个空缓冲区V(mutex);释放使用缓冲区资源V(full);有产品的缓冲区增加一个 endend;生产者消费者算法生产
15、者消费者算法-3-3procedure consumer;消费者进程 begin while true do beginP(full);请求消费缓冲区中的资源P(mutex);请求独占使用缓冲区资源goods:=buffer(out);将out所指向的缓冲区产品送goodsout:=(out+1)mod n;out移动到下一个装满产品的缓冲区V(mutex);释放使用缓冲区资源V(empty);空缓冲区增加一个consume product;endend;P P、V V操作的次序问题操作的次序问题无论是生产者还是消费者，的顺序是重要的。应该将互斥使用的信号量的P操作放在紧挨临界区的位置，如果把
16、生产者进程中的两个P操作，当缓冲区时，生产者欲向缓冲区放产品时，将在P(empty)上等待，但它已得到了使用缓冲区的权力。若此后，消费者欲取产品时，由于申请使用缓冲区不成功，它将在P(mutex)上等待。从而导致生产者等待消费者取走产品，而消费者却在等待生产者释放缓冲区，这种相互等待是无休止的，从而造成。一般来说，所以，但P原语则不然，如果次序混乱，将会造成进程之间的死锁。两个经典的同步两个经典的同步/互斥问题互斥问题读者与写者问题 有一个许多进程共享的数据区，对共享资源的读写操作，任一时刻“写者”最多只允许一个，而“读者”则允许多个：若一个写进程正在写，禁止任何进程读。一次只有一个写进程可以
17、往数据区中写；任意多的读进程可以同时读这个数据区；解决读者解决读者/写者问题，需设置两个信号量：写者问题，需设置两个信号量：（1）读互斥信号量rmutex,用于使读者互斥地访问共享变量count,这里count是记录有多少读者正在读;（2）写互斥信号量wmutex,用于实现读写互斥和写写互斥地访问共享文件。读者、写者问题算法读者、写者问题算法1 1varvar rmutexrmutex,wmutex:semaphorewmutex:semaphore;rmutexrmutex:=1;:=1;wmutexwmutex:=1:=1count:integercount:integercount:=0
18、count:=0beginbegin cobegincobegin 并发进程并发进程 readerreader和和writerwriter reader;reader;writer;writer;coendcoend endend 读者、写者问题算法读者、写者问题算法2 2procedure reader;procedure reader;beginbegin P(rmutexP(rmutex););count:=count+1;count:=count+1;if count=1 then if count=1 then P(wmutexP(wmutex););第一个读者开始访问就禁止写者第一
19、个读者开始访问就禁止写者访问访问 V(rmutexV(rmutex););读文件；读文件；P(rmutexP(rmutex););count:=count-1;count:=count-1;if count=0 then if count=0 then V(wmutexV(wmutex););没有读者访问就允许写者访问没有读者访问就允许写者访问 V(rmutexV(rmutex)endend 读者、写者问题算法读者、写者问题算法3 3procedure writer;procedure writer;beginbegin P(wmutexP(wmutex););写文件；写文件；V(wmutex
20、V(wmutex););endend五、管程五、管程(monitor)(monitor)用信号量可实现进程间的同步，但由于信号量的控制分布在整个程序中，其正确性分析很困难。管程是管理进程间同步的机制，它保证进程互斥地访问共享变量，并方便地阻塞和唤醒进程。管程可用函数库的形式实现。相比之下，管程比信号量好控制。信号量同步的缺点信号量同步的缺点同步操作分散：同步操作分散：信号量机制中，同步操作分散在各个进程中，使用不当就可能导致各进程死锁（如P、V操作的次序错误、重复或遗漏）易读性差：易读性差：要了解对于一组共享变量及信号量的操作是否正确，必须检查整个系统或者并发程序；不便于维护和修改：不便于维护
21、和修改：各模块的独立性差，任一组变量或一段代码的修改都可能影响全局；正确性难易保证：正确性难易保证：操作系统或并发程序通常很大，很难保证这样的一个复杂的系统没有逻辑错误；管程的引入管程的引入1973年，Hoare和hanson提出基本思想：是把信号量及其操作原语封装在一个对象内部。即：将共享变量以及对共享变量能够进行的所有操作集中在一个模块中。管程的定义管程的定义：管程是关于共享资源的数据结构及一组针对该资源的操作过程所构成的软件模块。管程的主要特征管程的主要特征模块化：一个管程是一个基本程序单位，可以单独编译。增加了模块的相对独立性；抽象数据类型：系统按资源管理的观点分解成若干模块，用数据表
22、示抽象的系统资源，按共享资源和专用资源不同的管理方式定义模块的类型和结构，使同步操作相对集中。模块之间关系清晰。信息封装：信息封装：管程是半透明的，管程中的外部过程（函数）实现了某种功能，且这些功能的实现，在其外部则是不可见的。管程的实现要素管程的实现要素管程中的共享变量在管程外部是不可见的，外部只能通过调用管程中所说明的外部过程（函数）来间接访问管程中的共享变量；为了保证管程共享变量的数据完整性，规定管程必须互斥进入；管程通常是用来管理资源的，因而在管程中设有进程等待队列以及相应的等待及唤醒操作。管程中的多个进程进入管程中的多个进程进入当一个进入管程的进程执行等待操作时，它应当释放管程的互斥
23、权；当一个进入管程的进程执行唤醒操作时（如P唤醒Q），管程，管程中便存在两个同时处于活动状态的进程。管程中的唤醒切换方法：P等待Q继续，直到Q等待或退出；Q等待P继续，直到P等待或退出；规定唤醒为管程中最后一个可执行的操作；管程的操作管程的操作当进程执行管程中的过程时被堵塞，应该退出管程，否则就阻碍其他进程的进入引入条件变量和wait(x),signal(x)操作预防死锁。条件变量：在管程内部通常使用一种特殊类型的变量-条件变量，每个变量标识一种等待原因，对应一个队列。并不取具体数值。管程需要进行初始化monitor monitor ringbufferringbuffer;varvar rb
24、uffer:array0.n-1 of item;rbuffer:array0.n-1 of item;环形缓冲区环形缓冲区goods,k,goods,k,nextempty,nextfull:integernextempty,nextfull:integer;k k是缓冲区中的元素个是缓冲区中的元素个数数empty,full:conditionempty,full:condition;条件变量条件变量procedure entry procedure entry put(varput(var product:itemproduct:item););向缓冲区送元素的过程向缓冲区送元素的过程 b
25、eginbeginif k=n then if k=n then wait(emptywait(empty););产品已经满，等待空闲缓冲区，产品已经满，等待空闲缓冲区，阻塞阻塞rubffernextemptyrubffernextempty:=product;:=product;k:=k+1;k:=k+1;产品增加产品增加nextemptynextempty:=(nextempty+1)mod n;:=(nextempty+1)mod n;改变指针改变指针signal(fullsignal(full););唤醒因为等待产品而阻唤醒因为等待产品而阻塞的进程塞的进程end;end;管程实例：生产
26、者管程实例：生产者/消费者消费者-1procedure entry procedure entry get(varget(var goods:itemgoods:item););从缓冲区取元素的过从缓冲区取元素的过程程beginbeginif k=0 then if k=0 then wait(fullwait(full););等待有可消费的产品，阻塞等待有可消费的产品，阻塞 goods:=goods:=rbuffernextfullrbuffernextfull;k:=k-1;k:=k-1;产品减少产品减少nextfullnextfull:=(nextfull+1)mod n;:=(next
27、full+1)mod n;改变指针改变指针signal(emptysignal(empty););唤醒等待送产品的生产者唤醒等待送产品的生产者end;end;begin begin 初始化变量初始化变量k:=0;k:=0;产品的数量产品的数量nextemptynextempty:=0;nextfull:=0;:=0;nextfull:=0;end;end;管程实例：生产者管程实例：生产者/消费者消费者-2producer:beginproducer:beginrepeatrepeatproduce an item:produce an item:ringbuffer.put(itemringb
28、uffer.put(item););until false;until false;endendconsumer:beginconsumer:beginrepeatrepeatringbuffer.get(itemringbuffer.get(item););consume the item;consume the item;until falseuntil falseendend管程实例：生产者管程实例：生产者/消费者消费者-3消息缓冲消息缓冲-高级通信原语高级通信原语高级通信：高级通信：是指用户可直接利用操作系统的一组通信命令，高效地传递大量数据的一种通信方式高效通信机制一般有：管道通信系
29、统、消息传递系统等消息传递系统：消息传递系统：进程间的数据交换以消息（message）为单位，直接利用系统提供的一组通信命令（原语）实现通信消息：是进程之间以不连续的成组方式发送的信息。消息缓冲区：系统设置一个大的缓冲区，作为消息缓冲池，它又分成若干消息缓冲区，每个放一个消息当进程需要发送消息时，就申请消息缓冲区。消息缓冲区是进程通信的基本单位。消息缓冲区的类型消息缓冲区的类型structstruct message_buffermessage_buffer xx sender xx sender；发送进程标发送进程标识符识符 xx size xx size；消息长度消息长度 xx text
30、xx text；消息正文消息正文 structstruct message_buffermessage_buffer *nextnext；指向下一个指向下一个 消息缓冲区消息缓冲区的指针的指针 PCBPCB中有关消息通信的数据项中有关消息通信的数据项struct PCB.mq;接受消息队列队首指针sm;接受消息队列资源信号量mutex ;接受消息队列互斥信号量.消息缓冲通信的过程消息缓冲通信的过程发送原语.接受原语.1.申请消息缓冲区申请消息缓冲区2.消息进入消息缓冲区消息进入消息缓冲区3.消息缓冲区挂入接受队列消息缓冲区挂入接受队列4.接收进程摘下消息缓冲区，读入接收进程摘下消息缓冲区，读入
31、5.归还系统消息缓冲区归还系统消息缓冲区消息缓冲原语消息缓冲原语-send(B,asend(B,a)发送消息原语发送消息原语 先先在自己的内存空间，设置一发送区a，把待发送的消息正文、发送进程标识符、消息长度等信息填入其中，然后后调用发送原语。如下一页的消息缓冲通信图消息缓冲通信图所示。消息缓冲原语消息缓冲原语-send(B,asend(B,a)发送消息原语发送消息原语Procedure send(receiver,a)Begingetbuf(a,size,i);根据根据a区消息长度来申请一缓冲区区消息长度来申请一缓冲区ii.sender:=a.sender;i.size:=a.size;i.
32、text:=a.text;i.next:=0getid(PCB,receiver,j);获得接收进程的内部标识符获得接收进程的内部标识符jP(j.mutext);申请资源申请资源Insert(j.mq,I);将将i挂在接收进程挂在接收进程j的消息队列的消息队列mq上（属于临界资源）上（属于临界资源）V(j.mutext);释放资源释放资源V(j.sm);消息队列同步信号量消息队列同步信号量smEnd消息缓冲原语消息缓冲原语-receive(breceive(b)接受消息原语接受消息原语Procedure receive(b)BeginP(j.sm);P(j.mutext);remove(j.m
33、q,i);从自己的消息缓冲队列从自己的消息缓冲队列mq中摘下第一个消息缓冲区中摘下第一个消息缓冲区iV(j.mutext);b.sender:=i.sender;b.size:=i.size;b.text:=i.text;putbuf(i);End死死 锁锁死锁死锁在多道程序系统中，并发进程改善了系统资源利用率和提高系统的吞吐量，但可能死锁。例：例：一个计算机系统，它有4 4台磁带机和2 2个并发执行的进程。某一时刻，每一进程都已占有2 2台磁带机，还要再请求一台磁带机才能完成它们的任务。这时，由于系统再无空闲的磁带机，两个进程就处于永远的等待状态，我们就说系统产生了死锁死锁。资源特性资源特性
34、硬件资源硬件资源：如打印机、磁带机、主存等。软件资源软件资源：如共享变量、数据库中的加锁记录。可抢占资源可抢占资源：是这样一类资源，当资源从占用进程剥夺走时，对进程不产生什么破坏性的影响。如主存、主存、CPUCPU。不可抢占资源不可抢占资源：一旦分配，不能强收回，只能由其自动释放。如打印机、磁带机。通常情况下，死锁涉及的是不可抢占资源死锁涉及的是不可抢占资源。一个进程必须按下述三个顺序事件使用资源。一个进程必须按下述三个顺序事件使用资源。（1 1）请求资源：请求资源：若请求不能立即满足，则申请者等待。（2 2）使用资源：使用资源：获得资源后，可使用它。（3 3）释放资源：释放资源：使用完毕，将
35、资源归还系统。死锁的定义死锁的定义 死锁：死锁：是指多个进程因竞争资源竞争资源而造成的一种僵局，若无外力作用，这些进程都将永远不能向前推进。死锁产生原因死锁产生原因竞争资源竞争资源。系统提供的资源不能满足每个进程的需要多道程序运行时，进程推进。进程在运行过程中，请求和释放资源的顺序不当，也同样会导致产生进程死锁。死锁产生的必要条件死锁产生的必要条件1 1）互斥条件。互斥条件。指进程对所分配到的资源进行排它性使用指进程对所分配到的资源进行排它性使用。每个资源是不可共享的，它或者已经分配给一个进程，或者空闲。2 2）不剥夺条件。不剥夺条件。资源已获得，未用完不被剥夺，用完时自己释放。3 3）请求和
36、保持条件。请求和保持条件。进程已保持保持了至少一个资源，但又请请求求新资源，无时，阻塞等待，但又对已经分配给它的资源保持不放保持不放。4 4）环路等待条件。环路等待条件。存在一个进程循环链一个进程循环链，链中有二个或多个进程，每一个进程正在等待链中的下一个成员保持的资源。解决死锁的方法解决死锁的方法用有向图有向图研究解决死锁的方法。图中圆圈圆圈代表进程，方块方块代表资源。资源已经分配给进程资源已经分配给进程用从资源(方块)到进程(圆圈)的有向弧表示；进程请求该资源进程请求该资源用从进程到资源的有向弧表示。P105 P105 死锁例子死锁例子死锁的预防死锁的预防不太可能避免死锁，因为有些进程无法
37、事先提供最大资源需求量。因产生死锁须四个必要条件。若能破坏其中的一个或几个条件，则死锁不发生。(1)(1)破坏互斥条件破坏互斥条件 资源的互斥使用条件是由资源本身的性质资源本身的性质决定的，因此不能破坏。但如果采用spoolingspooling技术技术，就可以将一台独享设备改造成多台设备，满足多个进程的需求，可预防死锁。实际中，不是所有设备都能采用不是所有设备都能采用spoolingspooling技技术的术的。即使采用spooling技术，由于多个进程竞争磁盘空间，磁盘空间的不足，仍可能导致死锁。死锁的预防死锁的预防(2)(2)(2)(2)破坏请求和保持条件（破坏请求和保持条件（资源独占）
38、让进程在开始开始运行前，必须获得必须获得其所需的全部资源其所需的全部资源。若系统不能满足，则该进程等待。然而，许多进程在开始运行然而，许多进程在开始运行之前，不能精确提出所用资源数量。如果之前，不能精确提出所用资源数量。如果它能提出，那么就可以采用它能提出，那么就可以采用银行家算法银行家算法避避免死锁了。免死锁了。死锁的预防死锁的预防(3)(3)(3)(3)破坏非剥夺条件破坏非剥夺条件 当一个进程已占有某些资源，又申请新的资源而不能立即得到满足时，则在进入阻塞状态前在进入阻塞状态前强行使其释放已经占有的资源强行使其释放已经占有的资源。以后运行时，再重新申请。这个办法显然也不行显然也不行，因为因
39、为保护进程放弃资源时的现场以及之后的恢复现场，系统要付出很高的代价。死锁的预防死锁的预防(4)(4)(4)(4)破坏循环等待条件破坏循环等待条件 (资源顺序分配)将系统全部资源按类进行全局编号排序全局编号排序。进程对资源的请求必须按照资源的序号（递增或递减顺序）申请，这样，在资源分配图中就不会出不会出现环路现环路，使进程一直运行，而不出现死锁。，如打印机为1，磁带机为2，等等。并且要求每一个进程均严格地。也就是说，只要进程提出请求资源Ri，则在以后的请求中，只能请求排在Ri后面的那些资源，不能再要求编号低于Ri的那些资源。对资源请求作了这样的限制后，系统中就的情况。存在的问题：各种资源编号后不
40、宜修改，从而限制了新设备的增加。例：例：系统拥有资源为：输入机=1 1，打印机=2 2，绘图机=3 3，磁带机=4 4，光盘=5 5。系统有两个进程A A和B B。所有进程对资源的请求必须严格按序号递增序号递增顺序进行。如果如果A A请求到资源请求到资源j j，B B请求到资源请求到资源i i。若。若ijij，允许允许A A请求请求B B占有的资源占有的资源i i，但绝不允许，但绝不允许B B请求请求A A占有占有的资源的资源j j，故进程资源图绝不会形成环路，故进程资源图绝不会形成环路。但找到但找到能满足所有进程要求的资源编号不可能能满足所有进程要求的资源编号不可能。发现死锁发现死锁允许死锁
41、发生，一旦发现，则用最小的代价恢复系统正常资源分配表S进程等待表W未阻塞进程表L选择选择L中：中：未阻塞进程未阻塞进程选择选择S中：中：未阻塞进程释放资源未阻塞进程释放资源修改修改WOKLL表，所有进程进入表，死锁状态有进程不能进入解除死锁解除死锁死锁状态的恢复，常采用如下两种方法：可以从一些进程那里强行剥夺足够数量的资源分配给死锁进程，以解除死锁状态。剥夺的顺序可以是以花费最小资源数为依据。并且需要在每次剥夺后重新调用检测算法检测算法。一个资源被剥夺的进程必须退回到前面获得这个资源的地方。还原算法：恢复计算状态建立检查点：恢复到局部检查点解除死锁（解除死锁（2 2）按照某种顺序逐渐地撤销已死锁的进程，直到获得为解除死锁所需要的足够可用的资源为止。使全部死锁进程都夭折掉按照某种顺序逐个地撤销进程，直至有足够的资源可用，使死锁状态消除为止。
