自考操作系统概论-第6章

第6章并发进程,6.1 进程的并发性,6.1.1进程的顺序性目前使用的计算机基本上是冯诺依曼（Von Neumann）式的结构，其基本特点是处理器按指令地址的指示顺序执行指令，这样的处理器称为顺序处理器。进程的顺序性是指进程在顺序处理器上的执行是严格按序的，即按照程序规定的操作顺序，只有在前一个操作结束后才能开始后继操作。当一个进程独占处理器顺序执行时，它具有两个特性：（1）封闭性进程执行的结果只取决于进程本身，不受外界影响。也就是说，进程执行的结果与其执行的速度无关。（2）可再现性进程重复执行时，必定获得同样的结果。也即，只要初始条件相同，则无论在什么时间执行都产生相同的结果。,6.1 进程的并发性,6.1.2进程的并发性在多道程序设计的系统中会同时存在着许多进程。每一个进程都具有顺序性。在单处理器的情况下，这些进程要竞争处理器，它们必须轮流占用处理器。但是，进程什么时间能占用处理器，能占用多长时间，这不仅取决于进程自身，还取决于进程调度策略。例如，有两个进程A和B，它们各自顺序执行的操作序列如下：进程A：a1,a2,a3,am；进程B：b1,b2,b3,bn在多道程序设计系统中，处理器会交替执行它们的操作。处理器可能按序列a1, b1,a2, b2,a3 ,b3,执行这些操作，也可能按序列a1, a2,b1, b2, b3,a3 ,执行这些操作，还可能按其他序列来执行。也就是说，在一个进程的工作没有全部完成之前，另一个进程就可以开始工作，我们说这些进程是可同时执行的，或称它们具有并发性，并且把可同时执行的进程称为并发进程。并发进程相互之间可能是无关的，也可能是有交互的。例如，为两个不同的源程序进行编译的两个进程，它们可以是并发的，但它们之间却是无关的。因为这两个进程分别为不同的源程序进行编译，也就是分别在不同的数据集合上运行，因此一个进程的执行不会影响另一个进程的执行，一个进程的执行与另一个进程的进展情况无关，它们是各自独立的。又如，第2章图2.2计算问题中的输入进程、处理进程、输出进程是三个并发进程，其中每一个进程的执行都依赖另一个进程的进展情况。只有当输入进程把一批数据读入后，处理进程才能对它加工，输出进程要等数据加工好后才能把它输出，也只有当处理进程把输入进程读入的一批数据取走后，输入进程才能读下一批数据。可见，它们是一组有交互的并发进程。有交互的并发进程一定共享某些资源。例如上例中的输入数据是输入进程与处理进程的共享资源，输出数据是处理进程与输出进程的共享资源，存放数据的工作区也是这些并发进程的共享资源。进程并发执行时，执行结果与其执行的相对速度有关。在上例中，如果输入进程尚未把一批数据全部读入，处理进程就对其进行加工的话，那么其结果就会出错。因而，进程的并发执行会破坏“封闭性”和“可再现性”。,6.2与时间有关的错误,一个进程运行时，经常会由于自身或外界的原因而被中断，且断点是不固定的。一个进程被中断后，哪个进程可以运行呢？被中断的进程什么时候能再去占用处理器呢？这是与进程调度策略有关的。所以，进程执行的相对速度不能由进程自己来控制，于是，就可能导致并发进程在共享资源时出现错误。例如，某游艺场设置了一个自动计数系统，用一个计数器count指示在场的人数。当有一个人进入时，由进程PIN实现计数加1；当退出一个人时，由进程POUT实现计数减1。这两个进程的程序如下：process PIN R1:interger;begin R1:=count; R1:=R1+1; count:=R1;end;process POUT R2:integer;begin R2:=count; R2:=R2-1 count:=R2;end;,6.2与时间有关的错误,如果这两个程序各自顺序执行，其执行结果毫无疑问是正确的。但是，由于入场和退场是随机的，因此，进程PIN和POUT的执行是并发的。我们把并发执行的进程用cobegin和coend括起来，于是，并发执行的程序可表示如下：begin count:integer; count:=0cobeginprocess PIN R1:ingeger;begin R1:=count; R1:=R1+1; count:=R1;end;process POUT R2:integer;begin R2:=count; R2:=R2-1; count:=R2; end;coend;end;,6.2与时间有关的错误,假定某个时候的计数值count=n.。这时有一个人要进入，正好有一个人要退出，于是进程PIN和POUT都要执行。如果进程PIN和POUT的执行都没有被打断过，那么各自完成了count+1和count-1的工作，使计数值保持为n。这是正确的的。如果两个进程执行中由于某种原因，进程PIN被打断，且进程调度使他们的执行呈下面的次序（见表6-1）：,按这样的次序执行后，count的最终值不能保持为n，而变成n+1。如果进程被打断的情况如下（见表6-2）。于是，两个进程执行完后，count的终值为n-1。由此可见，进程的执行次序对结果是有影响的。关键是它们涉及到共享变量count。这两个进程交替访问了count，访问count的时间不同，就可能使count的值不同。所以，造成计数值不正确的因素是与进程被打断的时间和能占用处理器的时间有关。由这种原因造成的错误称为与时间有关的错误。,下面再看一个例子。设一个飞机航班售票系统有n个售票处，每个售票处通过终端访问系统的公共数据区。假定公共数据区中的一些单元AK（K=1，2，m）分别存放某月某日某次航班的余票数。设P1，P2，Pn表示各售票处的处理进程，R1，R2，Rn表示各进程执行时所用的工作单元。当各售票处有旅客买票时，进程如下工作：process Pi(i=1,2,n) begin按旅客订票要求找到AK；Ri:=AK;if Ri=1 then begin Ri:=Ri-1; AK:=Ri; 输出一张票 endelse输出“票已售完”end;,由于各售票处旅客订票的时间以及要订的机票日期和航班是随意的，因此可能有若干个旅客在几乎相同的时间里到不同的售票处要求购买同一天同一航班的机票，于是若干个进程都要访问同一个AK，进程并发执行时可能会出现如下情况（见表6-3）：进程Pi和Pj分别在时刻t1和t2取到相同的值AK，当AK1时，都认为有票可售给旅客。于是各自执行余票数减1的操作，然后把当前的余票数存回AK。显然，这两个进程共售出同一天同一航班的机票2张。AK的值应该减去2，但是实际上AK的值只被减去了1，产生了错误。特别是，若当这两个进程执行前AK=1，它们并发执行后，则将发生“把唯一的一张机票卖给了两个旅客”的错误。这个错误也是由于进程交替访问了共享变量AK而造成的与时间有关的错误。,6.3临界区与PV操作,6.3.1临界区我们把并发进程中与共享变量有关的程序段称为临界区。在6.2节的第一个例子中，PIN和POUT这两个并发进程的临界区分别如下：PIN的临界区是：R1:=count; R1:=R1+1; count:=R1;POUT的临界区是：R2:=count; R2:=R2-1; count:=R2;在6.2节的第二个例子中有n个并发进程P1，P2，Pn。进程Pi（i=1，2，n）的临界区是：Ri:=AK;if Ri=1 then begin Ri:=Ri-1; AK:=Ri;如果能保证一个进程在临界区执行时，不让另一个进程进入相关的临界区执行，即各进程对共享变量的访问是互斥的，那么就不会造成与时间有关的错误。,6.3临界区与PV操作,相关临界区是指并发进程中涉及到相同变量的那些临界区。例如上面的第一个例子中，进程PIN和POUT都要访问变量count，所以它们的临界区是相关的。同样，第二个例子中，进程P1，P2，Pn都要访问变量AK，所以它们的临界区也是相关的。当然，PIN和POUT是不会去访问任何一个Pi中的变量，反之，各个Pi也不会去访问PIN和POUT中的变量，因而PIN和POUT的临界区与任何一个Pi的临界区是无关的。对同一共享变量的若干临界区必须互斥执行，而对不同变量的临界区的执行是不必互斥的。所以，当PIN和POUT在临界区执行时，不应妨碍P1，P2，Pn中任何一个进程进入它们的临界区执行。对若干个并发进程共享某一变量的相关临界区的管理有三个要求：（1）一次最多一个进程能够进入临界区。当有进程在临界区执行时，其他想进入临界区执行的进程必须等待：（2）不能让一个进程无限制地在临界区执行，即任何一个进入临界区的进程必须在有限的时间内退出临界区；（3）不能强迫一个进程无限制地等待进入它的临界区，即有进程退出临界区时应让一个等待进入临界区的进程进入它的临界区执行。怎样按照这三个要求实现对临界区的管理呢？,6.3.2 PV操作,为了实现对临界区的管理要求，必须做到：当无进程在临界区时，若有进程要进入临界区，则允许一个进程立即进入它的临界区；当有一个进程在临界区执行时，其他试图进入临界区的进程必须等待；当有一个进程离开临界区时，其有等待进入临界区的进程，则允许其中一个进程进入它的临界区。Dijkstra发明的PV操作能够实现对临界区的管理要法度。PV操作是由两个操作P操作和V操作组成。它们是两个不可中断的过程，它们在屏蔽中断的情况下连续执行。通常把这种不可中断的过程称为原语。因此，P操作和V操作也可称为P操作原语和V操作原语，简称PV操作。PV操作是对信号量进行操作，它们的定义如下：P操作P（S）：将信号量S减去1，若结果小于0，则把调用P（S）的进程置成等待信号量S的状态。V操作V（S）：将信号量加1，若结果不大于0，则释放一个等待信号量S的进程。,6.3.2 PV操作,这两个操作可表示成如下两个过程。Procedure P(Var S:Semaphore);begin S:=S-1; if S0 then W(S)end;PProcedure V(Var S:Semaphore);begin S:=S+1; if S=1 then begin Ri:=Ri-1; AK:=Ri; V(S); 输出一张票 endelse 输出“票已售完” end;coend;end;,进程执行时调用P（S）判定是否能进入临界区。由于S的初值为1，故每次只能有一个进程进入临界区，其他想进入临界区执行的进程必须等待，这符合临界区管理的第一个要求。但在改写的程序中，忽略了当条件Ri1不成立时执行else部分的V操作，以致使进程在临界区中判别条件Ri1不成立时无法退出临界区，当然也就不能释放等待进入临界区的进程，造成进程无限地等待进入临界区，这就违反了对临界区管理的第二、第三两个要求。正确的做法应该是：,begin S:semaphore; S:=1;cobeginprocess Pi(i=1,2,n) begin 按旅客订票要求找到AK；P（S）；Ri=AK;if Ri=1 then begin Ri:=Ri-1; AK:=Ri; V(S); 输出一张票 endelse beginV(S);输出“票已售完” end end;coend;end;,6.4.2进程的同步,进程的同步是指在并发进程之间存在一种制约关系，一个进程的执行依赖另一个进程的消息，当一个进程没有得到另一个进程的消息时应等待，直到消息到达才被唤醒。先看一个例子。设有两个进程A和B，它们共享一个缓冲器。进程A不断地读入记录，并送入缓冲器中。进程B不断地从缓冲器中取出记录并加工。如图6-1所示。假定缓冲器的容量为每次只能存放一个记录。于是，正确的工作过程应该是：进程A把一个记录送入缓冲器后，应等到进程B发来信息（已将缓冲器中的记录取走），才能把下一个记录存放缓冲器。进程B把已存入缓冲器的记录取走后，也应该等到进程A发来消息（缓冲器中已存入一个待加工的记录），才能从缓冲器中取出记录去加工。如果两个进程不相互制约的话，就会造成错误。例如，进程A把一个记录存放缓冲器后，进程B还没有取走该记录，而进程A又把新读来的一个记录存入缓冲器，这样就把上一个尚未取走的记录覆盖了。同样，如果进程B在下一个记录存入缓冲器之前，又去取缓冲器中的记录，则造成重复地取同一个记录加工。这种错误的出现是由两个进程的执行速度造成的。当进程A的执行速度超过进程B的执行速度是会造成记录的丢失。当进程B的执行速度超过进程A的执行速度时会造成记录的重复加工。只有当两个进程按一定速度（相互制约）执行时才能正确地工作，即进程A和进程B之间必须同步。,6.4.2进程的同步,1.同步机制要实现进程的同步就必须提供一种机制，这种机制应能测试进程所需的消息是否到达，还能把共创进程所需的消息发送出去。我们已经知道怎样用PV操作来实现进程的互斥。事实上，PV操作不仅是实现进程互斥的有效工具，而且还是一个简单又方便的同步工具。用一个信号量与一个消息联系起来，当信号量的值为0时，表示所期望的消息尚未产生，当信号量的值为大于0时，表示所期望的消息已经存。显然，任何进程只要调用P操作就可测试自己所期望的消息是否已经到达。若用信号量S表示一种消息，如果消息尚未产生则S=0，调用P（S）后，调用者成为等待消息S的状态；如果消息已经存在则S0，调用P（S）后，调用者不会成为等待状态，即测试到自己所期望的消息已经到达，可继续执行。同样，任何进程要向其他进程发送消息时可调用V操作。若调用V操作之前S=0，表示消息尚未产生，且也无等待该消息的进程，这时调用V（S）后，使S0，即意味着消息已产生；若调用V操作之前S0，消费者调用P（SG）后总可去取物品。每取走一件物品后，由于调用V（SP），便增加了一个可用来存放物品的位置。用指针K和t分别指示生产者往缓冲器存放物品和消费者从缓冲器中取物品的相对位置。它们的初值为0。这样，一个消费者和一个生产者共用容量为n的缓冲区时，可如下同步工作：,2.生产者/消费者问题,begin B:array0.(n-1) of integer; k,t:integer; SP,SG:semaphore; k:=0;t:=0; SP:=1;SG:=0;cobegin process producer begin L1:produce a product; P(SP); Bk:=product; k:=(k+1) mod n; V(SG); go to L1 end;process consumer begin L2:P(SG); take a product from Bt; t:=(t+1) mod n; V(SP); consume; go to L2; end;coend;end;,进程的同步例题：,假定有三人进程R、W1、W2共享一个缓冲器B，设B中每次只能存放一个数。要求：当缓冲器中无数时，进程R可将从输入设备上读入的数存放到缓冲器B中。若存放到缓冲器中的数是奇数，则允许进程W1将其取出打印；若存放到缓冲器中的数是偶数，则允许进程W2将其取出打印。还要求：进程R必须等缓冲器中的数被取出打印后才能存放下一个数；进程W1或W2对每次存入缓冲器中的数只能打印一次；W1和W2都不能从空的缓冲器中取数。写出这三个并发进程能正确工作的程序。,进程的同步例题：,分析：在这个问题中，我们可把进程R看到是生产者，把进程W1和W2看作是消费者。现有一个生产者（进程R）能生产不同的产品（读入奇数或偶数），把生产的产品存放在缓冲器B中，供不同的消费者（进程W1和进程W2）取用。可以看出，当进程R读入的是奇数，则要把有奇数的消息发送给进程W1；当进程R读入的是偶数，则要把偶数的消息发送给进程W2。在进程W1或W2从缓冲器中取出数后，应把缓冲器中又可存放数的消息，告诉进程R。于是，可以如下定义三个信号量S、SO、SE；S表示是否可以把数存入缓冲器。由于缓冲器中每次只能放一个数，所以它的初值取为1。SO表示缓冲器中是否有奇数。初值为0，表示无奇数。SE表示缓冲器中是否有偶数。初值为0，表示无偶数。,进程的同步例题：,R、W1、W2这三个并发进程能正确执行的程序如下：begin B:integer; S,SO,SE:semaphore; S:=1;SO:=0;SE:=0; cobegin process R x:integer; begin L1:从输入设备读入一个数； x：=读入的数； P（S）； B：=x； if B为奇数 then V(SO) else V(SE); go to L1 end;process W1 y:integer; beginL2:P(SO); y:=B; V(S); 打印y中数； go to L2 end;process W2 z:integer; beginL3:P(SE)z:=B;V(S);打印z中数；go to L3 end;coend;end;,结论：进程的互斥实际上是进程同步的一种特殊情况。实现进程互斥时用P操作测试是否可以使用共享资源，这相当于测试“资源已可使用”的消息是否到达；用V操作归还共享资源，这相当于发送了“共享资源已空闲”的消息。所以，经常把进程的互斥与进程的同步统称为进程的同步，把用来解决进程互斥与进程同步的机制（如PV操作）统称为同步机制。但是，进程的互斥与进程的同步是有差别的。进程的互斥是进程之间竞争共享资源的使用权。这种竞争没有固定的必然关系，哪个进程竞争到使用权则共享资源就归哪个进程使用，直到不需要使用时再归还使用权。若无进程在使用共享资源，就允许有进程去使用它，即使是一个刚刚使用过某共享资源的进程，而此时无其他进程要使用这个共享资源，则该进程仍可再次使用它。而进程同步的情况就不同了，涉及共享资源的并发进程之间有一种必然的依赖关系。当进程必须同步时，即使无进程在使用共享资源，尚未得到同步消息的进程仍然不能去使用这个资源。所以用PV操作管理共享资源时，一定要正确区分互斥与同步。最关键的是确切地定义信号量，以及合理地调用各信号量上的P操作和V操作。,3.同步与互斥的混合问题,6.5进程通信,我们已经知道，一个作业的执行经常是由若干个进程的相互合作来完成，这些进程是并发执行的，但它们之间必须保持一定的联系，使之能协调地完成任务。例如，在多道程序设计系统中，若干个作业有可能要共享某些资源。在上面几节的讨论中，我们看到为了保证安全地共享这些资源，进程间必须交换一些信息来实现进程的互斥和同步。有时进程间还需通报一些执行要求和执行情况。总之，在计算机系统中，并发进程之间经常要交换一些信息。并发进程间可以通过PV操作交换信息实现进程的互斥与同步，因此可把PV操作看作是进程间的一种通信方式，但这种通信只交换了少量的信息，如缓冲器中是否可以存放物品，缓冲器中是否已有物品等。只交换少量信息的通信方式是一种低级通信方式。有时，进程间要交换大量信息，这种大量信息的传递要有专门的通信机制来实现， 这是一种高级的通信方式。我们把通过专门的通信机制实现进程间交换大量信息的通信方式称为进程通信。目前常用的高级通信方式有信箱通信、消息缓冲通信、管道通信等。这里仅介绍一种利用信箱进行通信的方式。采用信息方式进行通信时，进程间用信件来传递信息。一个正在执行的进程可向其他进程发送信件，一个正在执行的进程也可向其他进程索取信件。,6.5.1信件,一个进程要向其他进程发送信息时，应先组织好一封信。信件的内容应包括：发送者名信息（或信息存放的地址和长度）等/不等回信回信存放地址其中：“发送者名”为发送信件进程的进程名；“信息”指要传送给某一进程的信息，若信息量很大，则可把信息存放在某个缓冲区中，在信件中指出缓冲区的起始地址和信息长度，这样可缩短信件长度，减少传递信件的时间，接收信件者可直接从指定的地址中取信息：“等/不等回信”表示信件发送者是否等信件接收者的回信，若需要等回信，则应指出“回信存放地址”。,6.5.2信箱,若干个进程都可向同一进程发送信件。接收信件的进程可以设立一个信箱。信箱的大小决定了信箱中可以容纳的信件数。为了便于了解信箱中的情况，每个信箱可以由“信箱说明”和“信箱体”两部分组成，如图6-2所示。“可存信件数”是在设立信箱时根据信箱的容量预先确定的。根据“可存信件数”和“已有信件数”能判别信箱是否满和信箱中是否有信件。若信箱不满，则按“可存信件的指针”指示的位置存入当前的一封信。当存入一封信后，应修改“已有信件数”和“可存信件的指针”。若信箱中有信，则信件接收者每次可从中取出一封信。为简便起见，可约定每次总是取信箱中的第一封信。当第一封信取走后，如果信箱中还有信，则把信箱中剩余的信件的存放位置向上移。,6.5.3通信原语,用信箱实现进程间互通信息的通信机制要有两个通信原语，它们是“发送”（send）原语和“接收”(receive)原语。为避免信件的丢失和错误地索取信件，通信时应遵循如下规则：（1）若发送信件时信箱已满，则应把发送信件的进程置成“等信箱”状态，直到信箱有空时才被释放。（2）若取信件时信箱中无信，则应把接收信件的进程置成“等信件”状态，直到信箱中有信件时才被释放。于是，“send”和“receive”的功能以及实现要求如下：（1）send(N,M)。功能：把信件M送到指定的信箱N中。实现要求：查指定信箱N。若信箱未满，则按“可存信件的指针”把信件M存入信箱且释放“等信件”者；若信箱已满，则把发送信件进程置为“等信箱”状态。（2）receive(N,Z)。功能：从指定信箱N中取出一封信，存到指定的地址Z中。实现要法度：查指定信箱N。若信箱中有信，则取出一封信存于Z中，且释放“等信箱”者；若信箱中无信，则把接收信件进程置为“等信件”状态。,6.5.3通信原语,一个进程要向其他进程发送信件时，必须先组织好信件，然后再调用“send”原语，且调用时要给出参数，即信件送到哪个信箱，以及信件的内容（或信件存放地址）。进程调用“receive”原语接收信件时也要给出参数，即从哪个信箱取信，以及取出的信存放到哪里。图6-3是进程间进行通信的示意。A进程欲向B进程发送信息时，把信息组织成一封信件，然后调用send原语向B进程发出信件，投入B进程的信箱中。B进程想得到A进程的信息时，只需要调用receive原语就可从信箱中索取来自A进程的信件。这样就完成了一次A进程与B进程的通信过程。B进程得到A进程发来的信件后进行适当的处理，然后可以把处理的结果组织成一封回信发送回去。A进程发出信件后，要想得到对方的处理情况，也可向对方索取一封回信，实现了B进程与A进程之间的另一次通信过程。,6.6死锁,6.6.1死锁的形成在计算机系统中，各种资源（包括硬件资源和软件资源）都是由操作系统进行管理和分配的。作业所需要的资源是在调度到这个作业时根据作业提出的要求（例如，需要多少主存区域，要用哪些外围设备等）来分配的。作业在分进程执行时，各进程根据执行情况还可动态地申请资源（例如，请求读某个文件，请求从打印机输出结果，请求增加存储区域等）。前面的章节中已经介绍了对各类资源的管理和分配技术，目的是要充分发挥各个资源的作用，提高资源的利用率。当多个进程竞争共享资源时，还要采取必要的措施来实现资源的互斥使用和保证进程能在有限时间内获得所需的资源。但是，这些管理和分配都是根据一个作业或一个进程对某类或某个资源的需求来进行分配和调度的，而没有考虑一个进程已经占了某类资源后又要申请其他资源时会发生什么样的情况。实际上，计算机系统中有限的资源与众多的请求分配资源的作业和进程间会存在矛盾。如果管理和分配不当，则会引起进程相互等待资源的情况，使得这些进程都既在等待资源而无法继续执行，又不能归还已占有资源。显然，这种等待永远不能结束。,6.6死锁,例如，某系统中有两个并发进程A和B，它们都要使用资源R1和R2（如图6-4）。如果在分配资源时把资源R1分给了进程A，把资源R2分给了进程B，进程A和B在分别得到了一个资源后都还想要第二个资源，在第二个资源没有得到之前又不肯归还已占有的资源，于是进程A和进程B只好都处于等待资源的状态。这种等待是相互的，进程A等待进程B释放资源R2，进程B等待进程A释放资源R1，两个进程各占了对方所要的资源又互不相让，造成永远等待。若系统中存在一组进程（两个或多个进程），它们中的每一个进程都占用了某种资源而又都在等待该组进程中另一个进程所占用的资源，这种等待永远不能结束，则说系统出现了死锁，或说这组进程处于死锁状态。形成死锁的起因是系统提供的资源数比进程要求的资源数少，或者是若干个进程要求的资源总数大于系统能提供的资源数。这时，进程间就会出现竞争资源的现象，对进程竞争的资源如果管理或分配不当，就会引起死锁。死锁的出现与资源分配策略和并发执行的速度有关。,形成死锁的例子,例 资源分配不当引起死锁。若系统有某类资源m个，被n个进程共享，每个进程都要求k个资源(km)，当mnk时，即资源数小于进程所要资源的总数时，如果分配不当，就可能引起死锁。假定m5,n5,k2，采用的分配策略是：只要进程提出申请资源的要求，而资源尚未分配完，则就按进程的申请要求把资源分配给它。现在5个进程都提出先申请1个资源。按分配策略每个进程都分得了1个资源，这时资源都分完了。当进程提出再要第二个资源时，系统已无资源可分配，于是各个进程都等待其他进程释放资源。由于各个进程都得不到需要的全部资源而不能结束，也就不释放所占的资源，因而这组进程的等待资源的状态永远不能结束，导致了死锁。例 并发进程执行的速度引起死锁。有五个哲学家P1，P2，P3，P4和P5，他们围坐在一张圆桌旁。桌中央有一盘面条。每人面前有一只空盘。另有五根共享的筷子f1,f2,f3,f4,和f5，分别放在两人之间（如图6-5）。每个哲学家或思考问题或吃面条。当思考问题时放下筷子。想吃面条时必须获得两根筷子老能把面条取到自己的盘中，且各人只能从自己的左右两旁去取筷子，用过后，把筷子仍放回左右两旁，以供他人或自己需要时使用。,6.6.2死锁的必要条件,为了解决死锁问题，我们先分析在什么情况下可能发生死锁。从死锁的定义中可以知道，系统出现死锁必须同时保持下列四个必要条件：（1）互斥地使用资源每个资源每次只能给一个进程使用。（2）占有且等待资源一个进程申请资源得不到满足时处于等待资源的状态，且不释放已占有资源。（3）非抢夺式分配任何一个进程不能抢夺另一个进程所占的资源，即已被占用的资源只能由占用进程自己来释放。（4）循环等待资源存在一组进程，其中每个进程分别等待另一个进程所占用的资源。必须强调，这四个条件仅仅是必要条件而不是充分条件，即只要发生死锁，则这四个条件一定同时成立，即若有其中一个或几个条件不成立，则一定没有死锁。但反之不然，即若这四个条件同时成立，系统未必就有死锁存在。这四个条件也不是完全独立的，其中“循环等待资源”条件就包含了“占有且等待资源”条件。但是，“占有且等待资源”条件存在时并不一定存在“循环等待资源”条件，两者既不完全独立也不是等价的。在讨论操作系统设计中可能引起的死锁问题时，应避免与硬件故障以及其他程序性错误纠缠在一起。我们假定任何一个进程在执行中所申请的资源都能得到满足，那么它一定能在有限的时间内执行结束，且归还它所占的全部资源；一个进程只有在申请资源得不到满足时才处于等待资源状态。如果出现某个进程申请系统中不存在的资源或申请的资源数超过了系统拥有的最大数，这就不发球操作系统分配资源引起的问题。应另当别论。死锁影响系统的可靠性，因此设计操作系统时必须考虑死锁问题。解决死锁的方法通常有：死锁的防止、死锁的避免和死锁的检测。,6.6.3死锁的防止,死锁的防止是指当采用某种资源分配策略后，使系统一定不会出现死锁。显然，如果采用的资源分配策略能破坏四个必要条件中的一个，则死锁就可防止。通常使用的防止死锁的资源分配策略有：（1）静态分配资源。 静态分配资源是指进程必须在开始执行前就申请自己所要的全部资源，仅当系统能满足进程的全部资源申请要求且把资源分配给进程后，该进程才开始执行。 显然，采用表态分配资源的策略后，进程在执行过程中不再申请资源，故不可能出现占有了某些资源再等待其他资源的情况，也即使得四个必要条件的“占有且等待资源”和“循环等待资源”两个条件不成立，从而防止了死锁的发生。 静态分配资源的策略实现起来简单，但降低了资源的利用率。例如，某进程要对存放在磁带上的文件进行处理后再打印输出。按照静态分配策略，该进程在得到磁带机和打印机后才开始执行，但在处理文件这段时间里打印机被闲置，一直要到文件处理结束后才会去使用打印机。（2）按序分配资源。 按序分配资源是指对系统中每一个资源给出一个编号。规定任何一个进程申请两个以上资源时，总是先申请编号小的资源，再申请编号大的资源。 按这种策略分配资源可破坏“循环等待资源”的条件，达到防止死锁的目的。(3)剥夺式分配资源。 剥夺式分配资源是指：当一个进程申请资源得不到满足时，可从另一个进程那里去抢夺。 这咱分配策略目前只适用于对处理器和主存资源的分配。例如，当若干个进程申请主存区域得不到满足而都处于等待时，为防止永远等待的发生，可抢夺某进程已占的主存区域，把它们分配给其中一个等待资源的进程，使该进程得到资源后能执行到结束，然后归还所占的全部主存资源。这时再把归还的主存资源分配给被剥夺主存资源的进程，让它继续执行。显然，这种分配策略破坏了四个必要条件中的第三个条件“非抢夺式分配”，可防止死锁的发生。,6.6.4死锁的避免,在防止死锁的分配策略中，有的只适用于对某些资源的分配，有的会影响资源的使用效率。例如，剥夺式分配目前只适用于对处理器和主存资源的分配。静态分配策略把资源预先分配给进程，而这些进程占有了资源后可能在一段时间里并不使用它，这时其他想使用这些资源的进程却又因得不到而等待，降低了资源的利用率。采用按序分配时，各进程要求使用资源的次序往往不能与系统安排的次序一致，但申请资源时必须按编号的次序来申请，可能出现先申请到的资源在很长一段时间里闲置不用，也降低了资源的利用率。如果不采用防止死锁的分配策略，则对资源的分配不能确保不产生死锁。这时可采用如下办法：当估计到可能会产生死锁时，设法避免死锁的发生。只要系统能掌握并发进程中各个进程的资源申请情况，分配资源时就可先测试系统状态，分析会不会产生死锁，若把资源分配给申请者将产生死锁，则拒绝申请者的要求。,一个古典的测试方法-银行家算法,银行家把一定数量的资金供多个用户周转使用。当顾客对资金的最大申请量不超过银行家现金时，就可接纳一个新顾客；顾客可以分期借款；但借款总数不能超过最大申请量；银行家对顾客的借款可以推迟支付，但一定使顾客总能在有限的时间里得到借款；当顾客得到外贸部资金后，他一定能在有限时间里归还所有的资金。采用银行家算法分配资源时，测试进程对资源的最大需求量，如果系统现存的资源可以满足它的最大需求量，就满足进程当前的申请，否则就推迟分配。这样做，能保证至少有一个进程可得到需要的全部资源而执行到结束，然后归还资源供别的进程使用。如果操作系统能保证所有的进程在有限时间内得到需要的全部资源，则称系统处于安全状态，否则就说系统是不安全的。不安全状态可能引起死锁。银行家算法是在能确保系统处于安全状态时才把资源分配给申请者。,银行家算法,例如，现在有某类资源12个，供三个进程共享。进程1总共需要4个资源，但第一次先申请1个资源。进程2总共需要6个资源，第一次要求4个资源。进程3总共需要8个资源，第一次要5个资源。现在的分配情况如下：,三个进程都想继续要求资源。若把资源分给进程1（或进程3）就会出现不安全状态。假定又给进程1分配了1个资源，则分配的情况如下：,这时系统是不安全的，因为剩余的1个资源已不能满足任何一个进程的最大需求量，每一个进程都不能得到所需的全部资源，它们都等待其他进程归还资源，但任一进程在执行没有结束之前都不会归还资源，从而引起死锁。所以不能把资源先分给进程1（或进程3）。,银行家算法,为了避免死锁，可采用银行家算法。该算法规定，只有当系统现存的资源能满足进程的最大需求量时，才把资源分配给该进程。因此，剩余的2个资源只能分给进程2使用（已占4个资源，还需2个）。进程2在得到全部资源（6个）后，能在有限时间内执行结束，且归还所占的全部6个资源。归还后，这6个资源又可分给进程1和进程3，使得每个进程都能在有限时间内得到全部资源而执行结束。只有这样才能确保系统是安全的。如果进程要求使用系统中的若干类资源，则仅当系统现存的各类资源都能满足进程的最大需求量时，才把资源分配给进程。例如，某系统有A、B、C、D四类资源供5个进程P1、P2、P3、P4和P5共享。系统对这四类资源的拥有量为：A类3个，B类14个，C类12个，D类12个，表示为（3，14，12，12）。设现在各个进程对资源的需求和分配情况如表6-4：,银行家算法,由于5个进程对四类资源的占有量为（2，9，10，12），故当前系统中各类资源的剩余量为（，）。根据各进程对各类资源的最大需求和已占有量可知它们尚需的资源量如下：进程尚需（，），进程尚需（，），进程3尚需（1，2），进程4尚需（，2，），进程5尚需（，6，4，2）可见，进程P1不会再申请资源。按银行家算法，如果现进程P2提出需要（0，4，2，0）个资源，由于当前剩余的资源（1，5，2，0）小于它的尚需量（0，7，5，0），则暂时不能满足它的请求。为保证系统的安全，根据系统当前的剩余量（1，5，2，0）可先满足进程P4的需求，当进程P4执行结束后归还所占的全部资源，收回的资源又可继续分配给其他进程。如果系统按如下顺序分配和回收资源（见表6-5）：,则可保证所有进程在有限时间里得到所需的全部资源。银行家算法是在保证至少有一个进程能得到所需的全部资源的前提下进行资源分配的，避免了进程共享资源时可能发生的死锁，但这种算法必须不断测试各个进程占用和申请资源的情况，需花费较多的时间。,6.6.5死锁的检测,不少系统并不是经常会出现死锁的，所以有些系统在分配资源时并不加特别的限制，只要有剩余资源，总是把资源分给申请者。当然，这样的系统有时可能会出现死锁。为解决死锁问题，这种系统设置了一个定时运行的“死锁检测程序”，当检测到死锁情况时再设法将其排除。实现死锁检测的一种方法是，可以设置两张表格来记录进程使用和等待资源的情况。例如，系统有5个资源r1,r2,r3,r4和r5，现有三个进程P1，P2和P3，它们依次申请资源的要求为：P1依次申请r1,r5,r3；P2依次申请r3,r4,r2；P3依次申请r2,r5。这三个进程并发执行时，可能P1在得到资源r1和r5后，就有P2申请r3，再有P3申请r2。按这样的序列执行时，这些进程都能得到所申请的资源。但以后继续执行时会发生：P1申请r3，不能满足而等待资源r3;P2申请r4不能满足，再申请r2，不能满足而等待资源r2;P3申请r5,不能满足而等待资源r5。于是两张表格记录的情况为：,“死锁检测”程序定时地检测这两张表。如果发现有循环等待资源的进程，则就有死锁出现了。在上例中就有进程P1等待被进程P2占用的资源r3，而P2等待被进程P3占用的资源r2，进程P3又等待被P1占用的资源r5，形成了进