《教学课件PPT 同步、通信与死锁》由会员分享，可在线阅读，更多相关《教学课件PPT 同步、通信与死锁（146页珍藏版）》请在金锄头文库上搜索。
1、第第3 3章章 同步、通信与死锁同步、通信与死锁主要内容主要内容0并发进程并发进程0临界区管理临界区管理0信号量与信号量与PVPV操作操作0管程（删）管程（删）0进程通信进程通信0死锁死锁0LinuxLinux同步机制和通信机制同步机制和通信机制0Windows2003Windows2003同步机制和通信同步机制和通信13.1 3.1 并发进程并发进程3.1.1 3.1.1 顺序程序设计顺序程序设计 3.1.2 3.1.2 进程的并发性进程的并发性 3.1.3 3.1.3 进程的交互：协作和竞争进程的交互：协作和竞争 23.1.1 3.1.1 顺序程序设计顺序程序设计进程的顺序性进程的顺序性一
2、一个个进进程程在在顺顺序序处处理理器器上上的的执执行行是是严严格格按按序序的的，一一个个进进程程只只有有当当一一个个操操作作结结束束后后，才能开始后继操作。才能开始后继操作。顺顺序序程程序序设设计计是是把把一一个个程程序序设设计计成成一一个个顺顺序序执执行行的的程程序序模模块块，顺顺序序的的含含义义不不但但指指一一个程序模块内部，也指两个程序模块之间。个程序模块内部，也指两个程序模块之间。3顺序程序设计的特性顺序程序设计的特性程序执行的顺序性程序执行的顺序性程序环境的封闭性程序环境的封闭性程序执行结果的确定性程序执行结果的确定性计算过程的可再现性计算过程的可再现性l顺序程序设计的缺点顺序程序设
3、计的缺点计算机系统效率不高。计算机系统效率不高。43.1.2 3.1.2 进程的并发性进程的并发性1 1、并发程序设计、并发程序设计进进程程执执行行的的并并发发性性：一一组组进进程程的的执执行行在在时时间间上上是是重叠的。重叠的。并并发发性性举举例例：有有两两个个进进程程A(a1A(a1、a2a2、a3)a3)和和B(b1B(b1、b2b2、b3)b3)并发执行。并发执行。0 a1a1、a2a2、a3a3、b1b1、b2b2、b3 b3 顺序执行顺序执行0 a1a1、b1b1、a2a2、b2b2、a3a3、b3 b3 并发执行并发执行从从宏宏观观上上看看，一一个个时时间间段段中中几几个个进进程
4、程都都在在同同一一处处理器上，处于运行还未运行结束状态。理器上，处于运行还未运行结束状态。从从微微观观上上看看，任任一一时时刻刻仅仅有有一一个个进进程程在在处处理理器器上上运行。运行。5串行工作图示串行工作图示i1p1o1i2p2o26并行工作图示并行工作图示进程进程i1i1p1p1 i i p p o oo1o1i2i2p2p2o2o2i3i3p3p3o3o3t1t1t2t2t3t3时间时间并行工作并行工作i4i4t4t4i5i5P4P4t5t57并发的实质并发的实质并并发发的的实实质质是是一一个个处处理理器器在在几几个个进进程程之之间间的的多多路路复复用用，并并发发是是对对有有限限的的物物
5、理理资资源源强强制制行行使使多多用用户户共共享享，消消除除计计算算机机部部件件之之间间的互等现象，以提高系统资源利用率。的互等现象，以提高系统资源利用率。82 2、并发进程的特性、并发进程的特性无关的并发进程无关的并发进程0一一组组并并发发进进程程分分别别在在不不同同的的变变量量集集合合上上操操作作，一个进程的执行与其他并发进程的进展无关。一个进程的执行与其他并发进程的进展无关。x并并发发进进程程的的无无关关性性是是进进程程的的执执行行与与时时间间无无关关的的一个充分条件，又称为一个充分条件，又称为BernsteinBernstein条件条件。交互的并发进程交互的并发进程0一一组组并并发发进进
6、程程共共享享某某些些变变量量，一一个个进进程程的的执执行行可能影响其他并发进程的结果。可能影响其他并发进程的结果。 9BernsteinBernstein条件条件 R(piR(pi)=a1,a2,an)=a1,a2,an，程程序序pipi在在执执行行期期间间引引用用的的变量集变量集W(piW(pi)=b1,b2,)=b1,b2,bmbm ，程程序序pipi在在执执行行期期间间改改变变的的变量集变量集若若 两两 个个 程程 序序 的的 变变 量量 集集 交交 集集 之之 和和 为为 空空 集集 ： R(p1)W(p2)R(p2)W(p1)W(p1)W(p2)= R(p1)W(p2)R(p2)W(
7、p1)W(p1)W(p2)= 则并发进程的执行与时间无关。则并发进程的执行与时间无关。10BernsteinBernstein条件举例条件举例例如，有如下四条语句：例如，有如下四条语句： S1: a := x + y S2: b := z + 1S1: a := x + y S2: b := z + 1 S3: c := a b S4: w := c + 1 S3: c := a b S4: w := c + 1于是有于是有：R(S1)=x,y ,R(S2)=zR(S1)=x,y ,R(S2)=z，R(S3)=a,bR(S3)=a,b，R(S4)=cR(S4)=c；W(S1)=a, W(S1)
8、=a, W(S2)=bW(S2)=b，W(S3)=cW(S3)=c，W(S4)=wW(S4)=w。 S1S1和和S2S2可可并并发发执执行行，满满足足BernsteinBernstein条条件件。其其他他语语句句并并发发执执行行可可能能会会产产生生与与时时间间有有关关的错误。的错误。11并发程序设计的优点并发程序设计的优点l对对于于单单处处理理器器系系统统, ,可可让让处处理理器器和和各各I/OI/O设设备同时工作备同时工作, ,发挥硬部件的并行能力。发挥硬部件的并行能力。l对对于于多多处处理理器器系系统统, ,可可让让各各进进程程在在不不同同处处理理器上物理地并行，加快计算速度。器上物理地并
9、行，加快计算速度。l简化了程序设计任务。简化了程序设计任务。 12采用并发程序设计的目的采用并发程序设计的目的充充分分发发挥挥硬硬件件的的并并行行性性，提提高高系系统统效效率率。硬硬件件能能并并行行工工作作仅仅有有了了提提高高效效率率的的可可能能性性，硬硬部部件件并并行行性性的的实实现现需需要要软软件件技技术术去去利利用用和发挥，这种软件技术就是并发程序设计。和发挥，这种软件技术就是并发程序设计。并并发发程程序序设设计计是是多多道道程程序序设设计计的的基基础础，多多道道程程序序的的实实质质就就是是把把并并发发程程序序设设计计引引入入到到系统中。系统中。133 3、与时间有关的错误、与时间有关的
10、错误对于一组交互的并发进程，执行的相对速对于一组交互的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误度无法相互控制，各种与时间有关的错误就可能出现。就可能出现。与时间有关错误的表现形式：与时间有关错误的表现形式：0结果不唯一结果不唯一0永远等待永远等待14（结果不唯一）机票问题（结果不唯一）机票问题/飞机票售票问题飞机票售票问题void T1( ) void T2( ) void T1( ) void T2( ) 按旅客订票要求找到按旅客订票要求找到AjAj; ; 按旅客订票要求找到按旅客订票要求找到AjAj; intint X1= X1=AjAj; ; intint X2= X2
11、=AjAj; ; if(X1=1) if(X2=1) if(X1=1) if(X2=1) X1-; X2-; X1-; X2-; AjAj=X1; =X1; AjAj=X2;=X2; 输出一张票输出一张票; ; 输出一张票输出一张票; else else elseelse 输出信息输出信息 票已售完票已售完; ; 输出信息输出信息 票已售完票已售完; 15T1T1、T2T2并发执行，可能出现如下交叉情况：并发执行，可能出现如下交叉情况：T1:X1=T1:X1=AjAj; /X1=m; /X1=mT2:X2=T2:X2=AjAj; /X2=m; /X2=mT2:X2-;Aj=X2;T2:X2-;
12、Aj=X2;输出一张票输出一张票; /; /AjAj=m-1=m-1T1:X1-;Aj=X1;T1:X1-;Aj=X1;输出一张票输出一张票; /; /AjAj=m-1=m-1同一张票卖给两位旅客（若只有一张余票）或者余同一张票卖给两位旅客（若只有一张余票）或者余票数不正确（若有多张余票）。票数不正确（若有多张余票）。16（永远等待）主存管理问题（永远等待）主存管理问题申请和归还主存资源问题申请和归还主存资源问题intint X=memory; /memory X=memory; /memory为初始主存容量为初始主存容量voidvoid borrow(intborrow(int B) voi
13、d B) void return(intreturn(int B) B) while(Bwhile(BX) X=X+B;X) X=X+B; 进程进入等待主存资源队列进程进入等待主存资源队列; ; 修改主存分配表修改主存分配表; X=X-B ; X=X-B ; 释放等主存资源进程释放等主存资源进程; ; 修改主存分配表，修改主存分配表， 进程获得主存资源进程获得主存资源; ; 17若对若对borrowborrow和和returnreturn的并发执行不加限制将会导致的并发执行不加限制将会导致错误，例如：错误，例如：Borrow:while(BBorrow:while(BX);X);Return:
14、XReturn:X=X+B;=X+B;修改主存分配表修改主存分配表;释放等待主存资释放等待主存资源的进程源的进程 ；此时，因为此时，因为borrowborrow还没有进入等待队列，因此，还没有进入等待队列，因此，returnreturn的释放操作是空操作，当的释放操作是空操作，当borrowborrow进入等待队进入等待队列时，可能没有进程再来归还，处于永远等待状态。列时，可能没有进程再来归还，处于永远等待状态。183.1.3 3.1.3 进程的交互：竞争与协作进程的交互：竞争与协作(1)(1)第一种是竞争关系第一种是竞争关系 系统中的多个进程之间彼此无关系统中的多个进程之间彼此无关系统中的多
15、个进程之间彼此相关系统中的多个进程之间彼此相关 l资源竞争的两个控制问题：资源竞争的两个控制问题：l 一个是死锁一个是死锁(Deadlock)(Deadlock)问题，问题， l 一个是饥饿一个是饥饿(Starvation) (Starvation) 问题问题l 既要解决饥饿问题，又要解决死锁问题。既要解决饥饿问题，又要解决死锁问题。l进进程程互互斥斥是是指指若若干干个个进进程程因因相相互互争争夺夺独独占占型型资资源源时所产生的竞争制约关系。时所产生的竞争制约关系。19进程的交往：竞争与协作进程的交往：竞争与协作(2)(2)第二种是协作关系第二种是协作关系l某些进程为完成同一任务需要分工协作。
16、某些进程为完成同一任务需要分工协作。l进进程程同同步步指指为为完完成成共共同同任任务务的的并并发发进进程程基基于于某某个个条条件件来来协协调调它它们们的的活活动动，因因为为需需要要在在某某些些位位置置上上排排定定执执行行的的先先后后次次序序而而等等待待、传传递递信信号号或或消消息息所所产生的协作制约关系。产生的协作制约关系。l进程同步指两个以上进程基于某个条件来协调它们的进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时当一个进程没有得到来自于协作进程的消息
17、或信号时需等待，直到消息或信号到达才被唤醒。需等待，直到消息或信号到达才被唤醒。进进程程互互斥斥关关系系是是一一种种特特殊殊的的进进程程同同步步关关系系，即即逐逐次次使使用用互互斥斥共共享享资资源源，是是对对进进程程使使用用资资源源次次序序上上的一种协调。的一种协调。203.2 3.2 临界区管理临界区管理3.2.1 3.2.1 互斥与临界区互斥与临界区3.2.2 3.2.2 实现临界区管理的几种尝试实现临界区管理的几种尝试3.2.3 3.2.3 实现临界区管理的软件方法实现临界区管理的软件方法3.2.4 3.2.4 实现临界区管理的硬件设施实现临界区管理的硬件设施213.2.1 3.2.1
18、互斥与临界区互斥与临界区(1)(1)并并发发进进程程中中与与共共享享变变量量有有关关的的程程序序段段叫叫“临临界界区区”， 共共享享变变量量代代表表的的资资源源叫叫“临临界界资资源源”。 与与同同一一变变量量有有关关的的临临界界区区分分散散在在各各进进程程的的程程序段中，而各进程的执行速度不可预知。序段中，而各进程的执行速度不可预知。如如果果保保证证进进程程在在临临界界区区执执行行时时，不不让让另另一一个个进进程程进进入入临临界界区区，即即各各进进程程对对共共享享变变量量的的访访问是互斥的，就不会造成与时间有关的错误。问是互斥的，就不会造成与时间有关的错误。22互斥与临界区互斥与临界区(2)(
19、2)临界区调度原则：临界区调度原则：0一次至多一个进程能够进入临界区内执行；一次至多一个进程能够进入临界区内执行；0如果已有进程在临界区，其他试图进入的进程应等待；如果已有进程在临界区，其他试图进入的进程应等待；0进入临界区内的进程应在有限时间内退出，以便让等待进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入。进程中的一个进入。临界区调度原则总结：临界区调度原则总结：0互斥使用，有空让进；互斥使用，有空让进；0忙则等待，有限等待；忙则等待，有限等待；0择一而入，算法可行。择一而入，算法可行。233.2.2 3.2.2 临界区管理的尝试临界区管理的尝试 (1)(1)bool in
20、side1=false; /P1bool inside1=false; /P1不在其临界区内不在其临界区内boolbool inside2=false; /P2 inside2=false; /P2不在其临界区内不在其临界区内cobegincobegin /* /*cobegincobegin和和coendcoend表示括号中的进程是一组并表示括号中的进程是一组并发进程发进程* */ /process P1( ) process P2( ) process P1( ) process P2( ) while(inside2);/while(inside2);/等待等待 while(inside
21、1);/while(inside1);/等待等待 inside1=true; inside2=true;inside1=true; inside2=true; 临界区临界区; ; 临界区临界区; inside1=false; inside2=false; inside1=false; inside2=false; coendcoend可能不满足互斥条件可能不满足互斥条件24临界区管理的尝试临界区管理的尝试 (2)(2)bool inside1=false; /P1bool inside1=false; /P1不在其临界区内不在其临界区内boolbool inside2=false; /P2 i
22、nside2=false; /P2不在其临界区内不在其临界区内cobegincobeginprocess P1( ) process P2( ) process P1( ) process P2( ) inside1=true; inside2=true; inside1=true; inside2=true; while(inside2);/ while(inside2);/等待等待 while(inside1);/while(inside1);/等待等待 临界区临界区; ; 临界区临界区; inside1=false; inside2=false; inside1=false; insid
23、e2=false; coendcoend可能出现死循环可能出现死循环253.2.33.2.3实现临界区的软件算法实现临界区的软件算法PetersonPeterson算法算法(1)(1)bool inside2;bool inside2;inside0=false;inside0=false;inside1=false;inside1=false;enumenum 0,1 turn; 0,1 turn;26PetersonPeterson算法算法(2)(2)cobegincobeginprocess P0( ) process P0( ) inside0=true; inside0=true;
24、turn=1; turn=1; while(inside1&turn=1); while(inside1&turn=1); 临界区临界区; ; inside0=false; inside0=false; 27PetersonPeterson算法算法(3)(3) process P1( ) process P1( ) inside1=true; inside1=true; turn=0; turn=0; while(inside0&turn=0); while(inside0&turn=0); 临界区临界区; ; inside1=false; inside1=false; coendcoend2
25、83.2.4 3.2.4 实现临界区管理的硬件设施实现临界区管理的硬件设施关中断关中断测试并建立指令（删）测试并建立指令（删）对换指令（删）对换指令（删）29关中断关中断实现互斥的最简单方法实现互斥的最简单方法关中断适用场合关中断适用场合0简简单单有有效效，对对操操作作系系统统自自身身有有用用，可可在在更更新新共共享享变变量量或列表的几条指令期间禁止中断。或列表的几条指令期间禁止中断。关中断方法的缺点关中断方法的缺点0不不适适合合作作为为通通用用的的互互斥斥机机制制，关关中中断断时时间间过过长长会会影影响响性能和系统效率；性能和系统效率；0不不适适应应于于多多处处理理器器计计算算机机系系统统，
26、因因为为一一个个处处理理器器关关中中断断，并并不不能能防防止止进进程程在在其其它它处处理理器器上上执执行行相相同同的的临临界界段代码；段代码；0若若将将这这项项权权力力赋赋予予用用户户会会存存在在危危险险，若若用用户户未未开开中中断断，则系统可能因此而终止。则系统可能因此而终止。303.3 3.3 信号量信号量与与PVPV操作操作3.3.1 3.3.1 同步与同步机制同步与同步机制3.3.2 3.3.2 信号量与信号量与PVPV操作操作3.3.3 3.3.3 信号量实现互斥信号量实现互斥3.3.4 3.3.4 五个哲学家吃通心面问题五个哲学家吃通心面问题3.3.5 3.3.5 生产者生产者-
27、-消费者问题消费者问题3.3.6 3.3.6 读者读者- -写者问题写者问题3.3.7 3.3.7 理发师问题理发师问题313.3.1 3.3.1 同步和同步机制同步和同步机制著著名名的的生生产产者者-消消费费者者问问题题是是计计算算机机操操作作系系统统中中并并发发进进程程内内在在关关系系的的一一种种抽抽象象，是是典典型型的的进进程程同同步问题。步问题。在在操操作作系系统统中中，生生产产者者进进程程可可以以是是计计算算进进程程、发发送送进进程程；而而消消费费者者进进程程可可以以是是打打印印进进程程、接接收收进进程等等。程等等。解解决决好好生生产产者者-消消费费者者问问题题就就解解决决好好了了一
28、一类类并并发发进程的同步问题。进程的同步问题。32生产者生产者-消费者问题表述消费者问题表述有界缓冲问题有界缓冲问题有有n n个个生生产产者者和和m m个个消消费费者者，连连接接在在一一个个有有k k个个单单位位缓缓冲冲区区的的有有界界缓缓冲冲上上。其其中中，pipi和和cjcj都都是是并并发发进进程程，只只要要缓缓冲冲区区未未满满，生生产产者者pipi生生产产的的产产品品就就可可投投入入缓缓冲冲区区；只只要要缓缓冲冲区区不不空空，消消费费者者进进程程cjcj就就可可从从缓缓冲冲区区取取走并消耗产品。走并消耗产品。33生产者生产者- -消费者问题算法描述消费者问题算法描述(1)(1)intin
29、t k; k;typedeftypedef anyitemanyitem item; /item item; /item类型类型item item bufferkbufferk;intint in=0,out=0,counter=0; in=0,out=0,counter=0;34生产者生产者- -消费者问题算法描述消费者问题算法描述(2)(2)process process producer(voidproducer(void) ) while (true) /while (true) /无限循环无限循环 produce an item in produce an item in nextp
30、nextp;/;/生产一个产品生产一个产品 if (counter=k) /if (counter=k) /缓冲满时，生产者睡眠缓冲满时，生产者睡眠 sleep(producersleep(producer);); bufferinbufferin=nextpnextp;/;/将一个产品放入缓冲区将一个产品放入缓冲区 in=(in+1)%k; /in=(in+1)%k; /指针推进指针推进 counter+; /counter+; /缓冲内产品数加缓冲内产品数加1 1 if(counterif(counter=1) /=1) /缓冲为空，加进一件产品缓冲为空，加进一件产品 wakeup(con
31、sumerwakeup(consumer);); / /并唤醒消费者并唤醒消费者 35生产者生产者- -消费者问题算法描述消费者问题算法描述(3)(3)process process consumer(voidconsumer(void) ) while (true) /while (true) /无限循环无限循环if (counter=0) /if (counter=0) /缓冲区空，消费者睡眠缓冲区空，消费者睡眠 sleep(consumersleep(consumer);); nextcnextc= =bufferoutbufferout;/;/取一个产品到取一个产品到nextcnext
32、c out=(out+1)%k; / out=(out+1)%k; /指针推进指针推进 counter-; /counter-; /取走一个产品，计数减取走一个产品，计数减1 1if(counterif(counter=k-1) /=k-1) /缓冲满了，取走一件产品并唤缓冲满了，取走一件产品并唤 wakeup(producerwakeup(producer);); / /醒生产者醒生产者consume the item in consume the item in nextcnextc;/;/消耗产品消耗产品 36生产者生产者- -消费者问题的算法描述消费者问题的算法描述(4)(4)生产者和
33、消费者进程生产者和消费者进程对对countercounter的交替执行的交替执行会使其结果不唯一。会使其结果不唯一。 生产者和消费者进程的交替执行会导致进生产者和消费者进程的交替执行会导致进程永远等待。程永远等待。373.3.2 3.3.2 信号量与信号量与PVPV操作操作(1)(1)前节种种方法解决临界区调度问题的缺点前节种种方法解决临界区调度问题的缺点: : 1)1)对对不不能能进进入入临临界界区区的的进进程程，采采用用忙忙式式等等待待测测试试法法，浪费浪费CPUCPU时间。时间。 2)2)将将测测试试能能否否进进入入临临界界区区的的责责任任推推给给各各个个竞竞争争的的进进程会削弱系统的可
34、靠性，加重了用户编程负担。程会削弱系统的可靠性，加重了用户编程负担。19651965年年E.W.DijkstraE.W.Dijkstra提出了新的同步工具提出了新的同步工具-信号量信号量和和P P、V V操作。操作。 38信号量与信号量与PVPV操作操作(2)(2)信号量：一种软件资源信号量：一种软件资源原语：内核中执行时不可被中断的过程原语：内核中执行时不可被中断的过程P P操作原语和操作原语和V V操作操作原语原语一一个个进进程程在在某某一一特特殊殊点点上上被被迫迫停停止止执执行行直直到到接接收收到到一一个个对对应应的的特特殊殊变变量量值值，这这种种特特殊殊变变量量就就是是信信号号量量(s
35、emaphore)(semaphore)，复复杂杂的的进进程程合合作作需需求求都都可可以以通过适当的信号结构得到满足。通过适当的信号结构得到满足。39信号量与信号量与PVPV操作操作(3)(3)操操作作系系统统中中，信信号号量量表表示示物物理理资资源源的的实实体体，它它是是一个与队列有关的整型变量。一个与队列有关的整型变量。实实现现时时，信信号号量量是是一一种种记记录录型型数数据据结结构构，有有两两个个分分量量：一一个个是是信信号号量量的的值值，另另一一个个是是信信号号量量队队列列的队列指针。的队列指针。信号量的值信号量的值(-2)(-2) 信号量队列指针信号量队列指针40信号量分类信号量分类
36、信号量按其用途分为信号量按其用途分为公公用用信信号号量量：用用户户实实现现进进程程互互斥斥，初初值值为为1 1，相相关进程均可在此信号量上执行关进程均可在此信号量上执行PVPV操作；操作；私私有有信信号号量量：多多用用于于并并发发进进程程同同步步，初初值值为为0 0或或正正整整数数，仅仅允允许许此此信信号号量量所所拥拥有有的的进进程程执执行行P P操操作，而其它相关进程可执行作，而其它相关进程可执行V V操作。操作。信号量按其取值分为信号量按其取值分为二元信号量二元信号量：仅允许取值为：仅允许取值为0 0或或1 1，主要用于解决，主要用于解决互斥问题；互斥问题；一般信号量：允许取大于一般信号量
37、：允许取大于1 1的整型值，主要用于的整型值，主要用于解决同步问题。解决同步问题。41一般信号量一般信号量(1)(1) 设设s s为为一一个个记记录录型型数数据据结结构构, ,一一个个分分量量为为整整形形量量value,value,另另一一个个为为信信号号量量队队列列queue, queue, P P和和V V操作原语定义：操作原语定义： P(s)P(s)；将将信信号号量量s s减减去去l l，若若结结果果小小于于0 0，则则调调用用P(s)P(s)的的进进程程被被置置成成等等待待信信号号量量s s的的状状态。态。 V(s)V(s)：将将信信号号量量s s加加1 1，若若结结果果不不大大于于0
38、 0，则释放一个等待信号量则释放一个等待信号量s s的进程。的进程。42一般信号量一般信号量(2)(2)typedeftypedef structstruct semaphore semaphore intint value; / value; /信号量值信号量值structstruct pcbpcb *list; / *list; /信号量队列指针信号量队列指针 ; ; void void P(semaphoreP(semaphore &s) &s) s.values.value-; -; if(s.valueif(s.value0) 0) W(s.listW(s.list); ); voi
39、d void V(semaphoreV(semaphore &s) &s) s.values.value+; +; if(s.valueif(s.value=0) =0) R(s.listR(s.list);); 43一般信号量一般信号量(3)(3)推推论论1 1：若若信信号号量量s s为为正正值值，则则该该值值等等于于在在封封锁锁进进程程之之前前对对信信号号量量s s可可施施行行的的P P操操作作数数、亦亦等等于于s s所所代表的实际还可以使用的物理资源数代表的实际还可以使用的物理资源数推推论论2 2：若若信信号号量量s s为为负负值值，则则其其绝绝对对值值等等于于登登记记排排列列在在该该信
40、信号号量量s s队队列列之之中中等等待待的的进进程程个个数数、亦亦即即恰恰好好等等于于对对信信号号量量s s实实施施P P操操作作而而被被封封锁锁起起来来并并进入信号量进入信号量s s队列的进程数队列的进程数推推论论3 3：通通常常，P P操操作作意意味味着着请请求求一一个个资资源源，V V操操作作意意味味着着释释放放一一个个资资源源。在在一一定定条条件件下下，P P操操作作代代表表挂挂起起进进程程操操作作，而而V V操操作作代代表表唤唤醒醒被被挂挂起起进进程的操作程的操作443.3.3 3.3.3 信号量实现互斥信号量实现互斥 semaphore semaphore mutexmutex;
41、; mutexmutex=1;=1; cobegincobegin process Pi( ) /i=1, process Pi( ) /i=1,n,n P(mutexP(mutex);); 临界区临界区; V(mutexV(mutex);); coendcoend453.3.4 3.3.4 信号量解决五个哲学家吃通心面问题信号量解决五个哲学家吃通心面问题(1)(1) 有有五五个个哲哲学学家家围围坐坐在在一一圆圆桌桌旁旁，桌桌中中央央有有一一盘盘通通心心面面，每每人人面面前前有有一一只只空空盘盘子子，每每两两人人之之间间放放一一把把叉叉子子。每每个个哲哲学学家家思思考考、饥饥饿饿、然然后后吃吃
42、通通心心面面。为为了了吃吃面面，每每个个哲哲学学家家必必须须获获得得两两把把叉叉子子，且且每每人人只只能能直接从自己左边或右边去取叉子。直接从自己左边或右边去取叉子。46 信号量解决五个哲学家吃通心面问题信号量解决五个哲学家吃通心面问题(2)(2)47哲学哲学家吃家吃通通心心面问面问题题(3)(3)semaphore fork5;semaphore fork5;for (for (intint i=0;i5;i+) i=0;i5;i+)forkiforki=1;=1;cobegincobeginprocess process philosopher_iphilosopher_i( ) ( )
43、/i= 0,1,2,3,4 /i= 0,1,2,3,4while(truewhile(true) ) think( ); think( ); P(forkiP(forki);); P(fork(i+1)%5);P(fork(i+1)%5); eat( ); eat( ); V(forkiV(forki);); V(fork(i+1)%5);V(fork(i+1)%5); coendcoend可能死锁！可能死锁！48有若干种办法可避免这类死有若干种办法可避免这类死锁锁l上上述述解解法法可可能能出出现现永永远远等等待待，有有若若干干种种办办法可避免死法可避免死锁：锁：l至多允许四个哲学家同时吃；至
44、多允许四个哲学家同时吃；l奇奇数数号号先先取取左左手手边边的的叉叉子子，偶偶数数号号先先取取右右手手边边的叉子；的叉子；l每每个个哲哲学学家家取取到到手手边边的的两两把把叉叉子子才才吃吃，否否则则一一把叉子也不取。把叉子也不取。493.3.5 3.3.5 信号量解决生产者消费者问题信号量解决生产者消费者问题一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享多个缓冲区一个生产者、一个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区50一个生产者、一个消费者共享一个缓冲区的解一个生产者、一个消费者共享一个缓
45、冲区的解intint B; B;semaphore empty; /semaphore empty; /可以使用的空缓冲区数可以使用的空缓冲区数semaphore full; /semaphore full; /缓冲区内可以使用的产品数缓冲区内可以使用的产品数empty=1; /empty=1; /缓冲区内允许放入一件产品缓冲区内允许放入一件产品full=0; /full=0; /缓冲区内没有产品缓冲区内没有产品51cobegincobeginprocess producer() process consumer()process producer() process consumer() w
46、hile(truewhile(true) ) while(truewhile(true) ) produce( ); produce( ); P(fullP(full););P(empty);P(empty); take( ) from B; take( ) from B;append( ) to B; append( ) to B; V(emptyV(empty););V(full);V(full); consume( ); consume( ); coendcoend52多个生产者多个生产者/ /消费者、共享多个缓冲区的解消费者、共享多个缓冲区的解item item BkBk;semaph
47、ore empty;semaphore empty;empty=k; empty=k; / /可以使用的空缓冲区数可以使用的空缓冲区数semaphore full; full=0; semaphore full; full=0; / /缓冲区内可以使用的产品数缓冲区内可以使用的产品数semaphore semaphore mutexmutex; ;mutexmutex=1; /=1; /互斥信号量互斥信号量intint in=0; in=0;/放入缓冲区指针放入缓冲区指针intint out=0; / out=0; /取出缓冲区指针取出缓冲区指针53cobegincobeginprocess
48、producer_i ( ) process consumer_j ( ) process producer_i ( ) process consumer_j ( ) while(truewhile(true) ) while(truewhile(true) ) produce( ); produce( ); P(fullP(full);); P(emptyP(empty);); P(mutexP(mutex);); P(mutexP(mutex);); take( ) from take( ) from BoutBout; append to append to BinBin; out=(o
49、ut+1)%k; out=(out+1)%k; in=(in+1)%k; in=(in+1)%k; V(mutexV(mutex);); V(mutexV(mutex);); V(emptyV(empty);); V(fullV(full);); consume( ); consume( ); coendcoend543.3.6 3.3.6 信号量解决读者信号量解决读者- -写者问题写者问题(1)(1) 有有两两组组并并发发进进程程：读读者者和和写写者者，共共享享一一个个文文件件F F，要求：要求：允许多个读者同时执行读操作允许多个读者同时执行读操作任任一一写写者者在在完完成成写写操操作作之之
50、前前不不允允许许其其它它读读者者或或写写者工作者工作写写者者执执行行写写操操作作前前，应应让让已已有有的的写写者者和和读读者者全全部部退出退出55信号量解决读者写者问题信号量解决读者写者问题(2)(2)intint readcountreadcount=0;/=0;/读进程计数读进程计数semaphore semaphore writeblock,mutexwriteblock,mutex; ;writeblockwriteblock=1;mutex=1;=1;mutex=1;56信号量解决读者写者问题信号量解决读者写者问题(3)(3)cobegincobeginprocess process
51、 reader_ireader_i( )( ) process process writer_jwriter_j( )( ) P(mutexP(mutex);); P(writeblockP(writeblock);); readcountreadcount+; +; 写文件写文件; if(readcountif(readcount=1) =1) V(writeblockV(writeblock);); P(writeblockP(writeblock); ); V(mutexV(mutex); ); 读文件读文件; P(mutexP(mutex););readcountreadcount-;
52、-;if(readcountif(readcount=0)=0) V(writeblockV(writeblock);); V(mutexV(mutex);); coendcoend573.3.7 3.3.7 信号量解决理发师问题信号量解决理发师问题(1)(1)理理发发店店里里有有一一位位理理发发师师、一一把把理理发发椅椅和和n n把把供供等等候理发的顾客坐的椅子候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师一个顾客到来时，它必须叫醒理发师如如果果理理发发师师正正在在理理发发时时又又有有顾顾客客来来到到，则则如如果果
53、有有空椅子可坐，就坐下来等待，否则就离开空椅子可坐，就坐下来等待，否则就离开58信号量解决理发师问题信号量解决理发师问题(2)(2)intint waiting=0;/ waiting=0;/等候理发顾客坐的椅子等候理发顾客坐的椅子数数intint CHAIRS=N; / CHAIRS=N; /为顾客准备的椅子数为顾客准备的椅子数semaphore semaphore customers,barbers,mutexcustomers,barbers,mutex; ;customers=0;barbers=0;mutex=1;customers=0;barbers=0;mutex=1;59信号量
54、解决理发师问题信号量解决理发师问题(3)(3)cobegincobeginprocess barber( ) process barber( ) while(truewhile(true) ) P(customersP(customers);); / /有顾客吗？若无顾客，理发师睡眠有顾客吗？若无顾客，理发师睡眠 P(mutexP(mutex);); / /若有顾客时，进入临界区若有顾客时，进入临界区waiting-; /waiting-; /等候顾客数少一个等候顾客数少一个 V(barbersV(barbers);); / /理发师准备为顾客理发理发师准备为顾客理发 V(mutexV(mut
55、ex);); / /退出临界区退出临界区cut_haircut_hair(); /(); /理发师正在理发理发师正在理发( (非临界区非临界区) ) 60process process customer_icustomer_i( ) ( ) P(mutexP(mutex);); / /进入临界区进入临界区 if(waitingif(waitingCHAIRS) /CHAIRS) /有空椅子吗有空椅子吗waiting+; /waiting+; /等候顾客数加等候顾客数加1 1 V(customersV(customers);); / /唤醒理发师唤醒理发师 V(mutexV(mutex););
56、/ /退出临界区退出临界区 P(barbersP(barbers);); / /理发师忙，顾客坐下等待理发师忙，顾客坐下等待get_haircutget_haircut(); /(); /否则顾客坐下理发否则顾客坐下理发 else else V(mutexV(mutex);); / /人满了，走吧！人满了，走吧！ coendcoend61总结补充总结补充信号量小结信号量小结P P、V V操作小结操作小结针对信号量问题的补充练习针对信号量问题的补充练习621 1、信号量小结、信号量小结v一个信号量可用于一个信号量可用于n n个进程的同步互斥；且只能由个进程的同步互斥；且只能由P P、V V操操作
57、修改。作修改。用于互斥时，用于互斥时，S S初值为初值为1 1，取值为，取值为1 - (n-1) 1 - (n-1) （相当于临界区的通行证，实际上也是资源个数）相当于临界区的通行证，实际上也是资源个数） S=1S=1：临界区可用：临界区可用 S=0S=0：已有一进程进入临界区：已有一进程进入临界区 S0S=0=0 S=0:S=0:表示可用资源个数表示可用资源个数 S0:S0: 表示该资源的等待队列长度表示该资源的等待队列长度632 2、P P、V V操作小结操作小结P(S)P(S)：请求分配一个资源。请求分配一个资源。V(S)V(S)：释放一个资源。释放一个资源。P P、V V操作必须成对出
58、现。操作必须成对出现。 用于互斥时，位于同一进程内；用于互斥时，位于同一进程内； 用于同步时，交错出现于两个合作进程内。用于同步时，交错出现于两个合作进程内。多个多个P P操作的次序不能颠倒，否则可能导致死锁。操作的次序不能颠倒，否则可能导致死锁。 多个多个V V操作的次序可任意。操作的次序可任意。643 3、针对信号量问题的补充练习、针对信号量问题的补充练习1)1)桌子上有一个盘子，可以存放一个水果。父亲总桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；是放苹果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃盘中的香蕉，而女儿专等吃盘中的苹儿子专等吃盘中的
59、香蕉，而女儿专等吃盘中的苹果。果。分析：生产者消费者问题的一种变形，生产者、消费分析：生产者消费者问题的一种变形，生产者、消费者以及放入缓冲区的产品都有两类，但每类消费者只消者以及放入缓冲区的产品都有两类，但每类消费者只消费其中固定的一种产品。费其中固定的一种产品。数据结构：数据结构：semaphore dishsemaphore dish， apple apple ， banana ;banana ;dishdish：表示盘子是否为空，初值为表示盘子是否为空，初值为1 1appleapple：表示盘中是否有苹果，初值为表示盘中是否有苹果，初值为0 0bananabanana：表示盘中是否有香
60、蕉，初值为表示盘中是否有香蕉，初值为0 065cobegincobeginprocess father()process father() P(dishP(dish);); 将苹果放到盘中；将苹果放到盘中； V(appleV(apple);); process mother()process mother() P(dishP(dish);); 将香蕉放到盘中；将香蕉放到盘中； V(bananaV(banana);); process son()process son() P(bananaP(banana);); 从盘中取出香蕉；从盘中取出香蕉； V(dishV(dish);); process
61、 daughter()process daughter() P(appleP(apple);); 从盘中取出苹果；从盘中取出苹果； V(dishV(dish);); coendcoend. .662)哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全体到齐后开始讨论；在讨论的间隙四位哲学家进餐，每体到齐后开始讨论；在讨论的间隙四位哲学家进餐，每人进餐时都需使用刀、叉各一把，餐桌上的布置如下图人进餐时都需使用刀、叉各一把，餐桌上的布置如下图所示。用信号量机制说明四位哲学家的同步互斥过程。所示。用信号量机制说明四位哲学家的同步互斥过程。食品食品乙乙丙丙
62、丁丁甲甲刀刀2叉叉1刀刀1叉叉267分析分析标准的哲学家进餐问题，只是哲学家人数和标准的哲学家进餐问题，只是哲学家人数和餐具及分布与经典哲学家进餐问题略有不同餐具及分布与经典哲学家进餐问题略有不同数据结构数据结构semaphore fork1,fork2,knife1,knife2;semaphore fork1,fork2,knife1,knife2;frokfrok表示叉，表示叉，knifeknife表示刀，初值均为表示刀，初值均为1 168cobegincobeginprocess pa() process pa() /哲学家甲哲学家甲 P(knife1);P(knife1); P(fo
63、rk1); P(fork1); 进餐；进餐； V(knife1);V(knife1); V(fork1); V(fork1); 讨论问题；讨论问题； process pb() /哲学家乙哲学家乙 P(knife2);P(knife2); P(fork1); P(fork1); 进餐；进餐； V(knife2);V(knife2); V(fork1); V(fork1); 讨论问题；讨论问题； 69process pc() /哲学家丙哲学家丙 P(knife2);P(knife2); P(fork2); P(fork2); 进餐；进餐； V(knife2);V(knife2); V(fork2)
64、; V(fork2); 讨论问题；讨论问题； process pd() /哲学家丁哲学家丁 P(knife1);P(knife1); P(fork2); P(fork2); 进餐；进餐； V(knife1);V(knife1); V(fork2); V(fork2); 讨论问题；讨论问题； coend.703)3)有一个阅览室，读者进入时必须先在一张登记有一个阅览室，读者进入时必须先在一张登记表上登记，此表为每个座位列出一个表目，包表上登记，此表为每个座位列出一个表目，包括座位号、姓名，读者离开时要注意注销登记括座位号、姓名，读者离开时要注意注销登记信息；假如阅览室共有信息；假如阅览室共有10
65、0100个座位，请用信号量个座位，请用信号量和和P P、V V操作实现用户进程的同步算法。操作实现用户进程的同步算法。71分析：实际上是一个非常简单的同步分析：实际上是一个非常简单的同步- -互斥问题，不要互斥问题，不要想复杂了想复杂了数据结构：数据结构：structcharstructchar name10; name10; intint number; number; A100; A100;semaphore semaphore mutexmutex, , seatcountseatcount; ;mutexmutex：用来互斥，初值为：用来互斥，初值为1 1seatcountseatco
66、unt：对空座位计数，初值为：对空座位计数，初值为100100for(intfor(int i=0;i100;i+) i=0;i100;i+) Ai.numberAi.number=i; =i; Ai.nameAi.name=null;=null;72cobegincobeginprocess process readeri(charreaderi(char readernamereadername) P(seatcountP(seatcount);); P(mutexP(mutex) )； for(intfor(int i=0;i100;i+) i=0;i100;i+) if(Ai.name
67、if(Ai.name=null) =null) Ai.nameAi.name= =readernamereadername; ; reader get the seat number=i; reader get the seat number=i; V(mutexV(mutex);); 进入阅览室，在座位号进入阅览室，在座位号i i处坐下读书；处坐下读书； P(mutexP(mutex);); Ai.nameAi.name=null;=null; V(mutexV(mutex);); V(seatcountV(seatcount);); 离开阅览室；离开阅览室； coendcoend; ;73
68、4)4)在一个盒子里，混装了数量相等的黑白围棋子。现在用在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有两个进自动分拣系统把黑子、白子分开，设分拣系统有两个进程程P1P1和和P2P2，其中，其中P1P1拣白子，拣白子，P2P2拣黑子。规定每个进程每拣黑子。规定每个进程每次拣一子，当一个进程在拣时，不允许另一个进程去拣；次拣一子，当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试用当一个进程拣了一子时，必须让另一个进程去拣。试用信号量和信号量和P P、V V操作协调两个进程的并发执行。操作协调两个进程的并发执行。分析：
69、分析：实际上就是两个进程的同步问题。实际上就是两个进程的同步问题。数据结构：数据结构：semaphore S1semaphore S1， S2 ;S2 ;S1 和和S2 分别表示可拣白子和黑子，不失一般性，若分别表示可拣白子和黑子，不失一般性，若令先拣白子。初值，令先拣白子。初值， S1=1； S2=0；74cobegincobeginprocess P1()process P1() while(truewhile(true) P(S1); P(S1); 拣白子；拣白子； V(S2);V(S2); process P2() while(true) P(S2); 拣黑子；拣黑子； V(S1);
70、coendcoend. .753.5 3.5 进程通信进程通信3.5.1 3.5.1 信号通信机制信号通信机制 3.5.2 3.5.2 管道通信机制管道通信机制 3.5.3 3.5.3 共享主存通信机制共享主存通信机制 3.5.4 3.5.4 消息传递通信机制消息传递通信机制 76进程通信概念进程通信概念并并发发进进程程之之间间的的交交互互必必须须满满足足两两个个基基本本要要求求：同同步和通信。步和通信。进进程程竞竞争争资资源源时时要要实实施施互互斥斥，互互斥斥是是一一种种特特殊殊的的同步，实质上需要解决好进程同步问题，同步，实质上需要解决好进程同步问题，进进程程同同步步是是一一种种进进程程通
71、通信信，通通过过修修改改信信号号量量，进进程之间建立起联系，相互协调运行和协同工作。程之间建立起联系，相互协调运行和协同工作。进进程程协协同同工工作作时时，需需互互相相交交换换信信息息，可可能能是是少少量量信息，也可能交换大批数据。信息，也可能交换大批数据。进程之间互相交换信息的工作称为进程之间互相交换信息的工作称为进程通信进程通信IPCIPC（InterProcessInterProcess Communication Communication）。）。77进程间通信的方式进程间通信的方式 信号信号(signal)(signal)通信机制通信机制管道管道(pipeline)(pipeline
72、)通信机制通信机制 消息传递消息传递(message passing)(message passing)通信机制通信机制 信号量信号量(semaphore)(semaphore)通信机制通信机制共享主存共享主存(shared memory)(shared memory)通信机制通信机制78进程间通信的方式发展进程间通信的方式发展UNIXUNIX发发展展历历史史中中，AT&TAT&T的的BellBell与与加加大大伯伯克克利利的的BSDBSD是两大主力。是两大主力。BellBell致致力力于于改改进进传传统统的的进进程程IPCIPC，形形成成了了SYSTEM SYSTEM IPC IPC机制。机
73、制。BSDBSD在在改改进进IPCIPC的的同同时时，把把网网络络通通信信规规程程(TCP/IP)(TCP/IP)实实现现到到UNIXUNIX内内核核中中，考考虑虑把把同同一一计计算算机机上上的的进进程程通通信信纳纳入入更更广广的的网网络络范范围围的的进进程程间间通通信信，这这种种努努力结果出现了力结果出现了socketsocket网络通信机制。网络通信机制。 793.5.1 3.5.1 信号通信机制信号通信机制信号机制又称软中断，一种简单的通信机制，通过信号机制又称软中断，一种简单的通信机制，通过发送一个指定信号通知进程某个异常事件发生。发送一个指定信号通知进程某个异常事件发生。 用户、内核
74、和进程都能生成信号请求：用户、内核和进程都能生成信号请求： 1)1)用户用户-用户能通过输入用户能通过输入ctrl+cctrl+c，或终端驱动程序，或终端驱动程序分配给信号控制字符的其他任何键来请求内核产生分配给信号控制字符的其他任何键来请求内核产生信号。信号。 2)2)内核内核-当进程执行出错时，内核检测到事件并给当进程执行出错时，内核检测到事件并给进程发送信号，例如，非法段存取、浮点数溢出、进程发送信号，例如，非法段存取、浮点数溢出、或非法操作码，内核也利用信号通知进程种种特定或非法操作码，内核也利用信号通知进程种种特定事件发生。事件发生。 3)3)进程进程-进程可通过系统调用进程可通过系
75、统调用killkill给另一个进程发给另一个进程发送信号，一个进程可通过信号与另一个进程通信。送信号，一个进程可通过信号与另一个进程通信。80LinuxLinux系统信号分类系统信号分类l与进程终止相关的信号与进程终止相关的信号l与进程例外事件相关的信号与进程例外事件相关的信号l与进程执行系统调用相关的信号与进程执行系统调用相关的信号l与进程终端交互相关的信号与进程终端交互相关的信号l用户进程发信号用户进程发信号l跟踪进程执行的信号跟踪进程执行的信号813.5.2 3.5.2 管道通信机制管道通信机制管管道道(pipeline)(pipeline)是是连连接接读读写写进进程程的的一一个个特特殊
76、殊文文件件，允允许许进进程程按按先先进进先先出出方方式式传传送送数数据据, ,也也能能使使进进程程同步执行操作。同步执行操作。发发送送进进程程以以字字符符流流形形式式把把大大量量数数据据送送入入管管道道，接接收进程从管道中接收数据，所以叫管道通信。收进程从管道中接收数据，所以叫管道通信。管管道道的的实实质质是是一一个个共共享享文文件件，基基本本上上可可借借助助于于文文件件系系统统的的机机制制实实现现，包包括括（管管道道）文文件件的的创创建建、打开、关闭和读写。打开、关闭和读写。82共享文件通信机制共享文件通信机制读写进程相互协调，必须做到：读写进程相互协调，必须做到： 进进程程对对通通信信机机
77、构构的的使使用用应应该该互互斥斥，一一个个进进程程正正在在使使用用某某个个管管道道写写入入或或读读出出数数据据时时，另另一一个个进进程程就就必必须须等等待待。 (write(write阻阻塞塞、readread阻塞阻塞) ) 发发送送者者和和接接收收者者双双方方必必须须能能够够知知道道对对方方是是否否存存在在，如如果果对对方方已已经经不不存存在在，就就没没有有必必要再发送信息。要再发送信息。833.5.3 3.5.3 共享主存通信机制共享主存通信机制进程进程1 1的虚存空间的虚存空间虚存段虚存段进程进程2 2的虚存空间的虚存空间虚存段虚存段 物理主存物理主存共享主存共享主存843.5.4 3.
78、5.4 消息传递消息传递(1)(1)什么是消息传递（什么是消息传递（message passingmessage passing）? ?消息和消息传递机制消息和消息传递机制 基本的消息传递原语基本的消息传递原语send send ，receivereceive85消息传递消息传递(2)(2)l采采用用消消息息传传递递机机制制后后，一一个个正正在在执执行行的的进进程程可可在在任任何何时时刻刻向向另另一一个个正正在在执执行行的的进进程程发发送送消消息息；一一个个正正在在执执行行的的进进程程也也可可在在任任何何时时刻刻向向正正在在执执行行的的另一个进程请求消息。另一个进程请求消息。l一一个个进进程程
79、在在某某一一时时刻刻的的执执行行依依赖赖于于另另一一进进程程的的消消息息或或等等待待其其他他进进程程对对发发出出消消息息的的回回答答，那那么么，消消息息传传递递机机制制紧紧密密地地与与进进程程的的阻阻塞塞和和释释放放相相联联系系。消消息息传传递递就就进进一一步步扩扩充充了了并并发发进进程程间间对对数数据据的的共共享，提供了进程同步的能力。享，提供了进程同步的能力。86直接通信直接通信发发送送或或接接收收消消息息的的进进程程必必须须指指出出信信件件发发给给谁或从谁那里接收消息。谁或从谁那里接收消息。0原原语语sendsend（P P，消息）消息）x把一个消息发送给进程把一个消息发送给进程P P0
80、原语原语receivereceive（Q Q，消息）消息）x从进程从进程Q Q接收一个消息接收一个消息87间接通信间接通信l原语原语sendsend（A A，信件）信件）l把一封信件（消息）传送到信箱把一封信件（消息）传送到信箱A Al原语原语receivereceive（A A，信件）信件）l从信箱从信箱A A接收一封信件（消息）接收一封信件（消息）l信信箱箱是是存存放放信信件件的的存存储储区区域域，每每个个信信箱箱可可分成信箱特征和信箱体两部分。分成信箱特征和信箱体两部分。l信箱特征指出信箱容量、信件格式、指针等；信箱特征指出信箱容量、信件格式、指针等；l信箱体用来存放信件信箱体用来存放信
81、件88间接通信的实现间接通信的实现发送信件：发送信件： 如如果果指指定定信信箱箱未未满满，则则将将信信件件送送入入信信箱箱中中由由指指针针所所指指示示的的位位置置，并并释释放放等等待待该该信信箱箱中中信信件件的的等等待待者者；否否则则发发送送信信件件者者被被置置成成等待信箱状态等待信箱状态接收信件：接收信件： 如如果果指指定定信信箱箱中中有有信信，则则取取出出一一封封信信件件，并并释释放放等等待待信信箱箱的的等等待待者者，否否则则接接收收信信件件者被置成等待信箱中信件的状态者被置成等待信箱中信件的状态893.6 3.6 死锁死锁3.6.1 3.6.1 死锁产生死锁产生3.6.2 3.6.2 死
82、锁防止死锁防止3.6.3 3.6.3 死锁避免死锁避免3.6.4 3.6.4 死锁检测和解除死锁检测和解除903.6.1 3.6.1 死锁产生死锁产生若干死锁的例子若干死锁的例子例进程推进顺序不当产生死锁例进程推进顺序不当产生死锁 设设系系统统有有打打印印机机、读读卡卡机机各各一一台台，被被进进程程和和共共享享。两两个个进进程程并并发发执执行行，按按下下列列次序请求和释放资源：次序请求和释放资源： 进程进程 进程进程 请求读卡机请求读卡机 请求打印机请求打印机 请求打印机请求打印机 请求读卡机请求读卡机 释放读卡机释放读卡机 释放读卡机释放读卡机 释放打印机释放打印机 释放打印机释放打印机91
83、P PQ Q读卡机读卡机打印机打印机出现死锁！出现死锁！92例例 PVPV操作使用不当产生死锁操作使用不当产生死锁 进程进程Q1 Q1 进程进程Q2 Q2 P(S1); P(S2); P(S1); P(S2); P(S2); P(S1); P(S2); P(S1); 使用使用r1r1和和r2; r2; 使用使用r1r1和和r2r2 V(S1); V(S1); V(S2); V(S2); V(S2); V(S1); V(S2); V(S1); 93Q1Q1Q2Q2S1S2出现死锁！出现死锁！94例资源分配不当引起死锁例资源分配不当引起死锁 若系统中若系统中有有m m个资源个资源被被n n个进程共
84、享，每个个进程共享，每个进程都要求个资源，进程都要求个资源，而而m nKm nK时，即资时，即资源数小于进程所要求的总数时，如果分配不源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。得当就可能引起死锁。 95例对临时性资源使用不加限制引起死锁例对临时性资源使用不加限制引起死锁进程通信使用的信件是一种临时性资源，如果对进程通信使用的信件是一种临时性资源，如果对信件的发送和接收不加限制，可能引起死锁。信件的发送和接收不加限制，可能引起死锁。进程进程P1P1等待进程等待进程P3P3的信件的信件S3S3来到后再向进程来到后再向进程P2P2发发送信件送信件S1S1；P2P2又要等待又要等待P1
85、P1的信件的信件S1S1来到后再向来到后再向P3P3发送信件发送信件S2S2；而；而P3P3也要等待也要等待P2P2的信件的信件S2S2来到后才来到后才能发出信件能发出信件S3S3。这种情况下形成了循环等待，产这种情况下形成了循环等待，产生死锁。生死锁。 96P1P1P2P2S1S2出现死锁！出现死锁！P3P3S397死锁定义死锁定义操操作作系系统统中中的的死死锁锁：如如果果在在一一个个进进程程集集合合中中的的每每个个进进程程都都在在等等待待只只能能由由该该集集合合中中的的其其他他一一个个进进程程才才能能引引发发的的事事件件，则则称称一一组组进进程程或或系系统统此此时时发发生生死锁。死锁。例例
86、如如，n n个个进进程程P1P1、P2P2，PnPn，PiPi因因为为申申请请不不到到资资源源RjRj而而处处于于等等待待状状态态，而而RjRj又又被被Pi+1Pi+1占占有有，PnPn欲欲申申请请的的资资源源被被P1P1占占有有，此此时时这这n n个个进进程程的的等等待待状状态态永永远远不不能能结结束束，则则说说这这n n个个进进程程处处于于死死锁锁状态。状态。98产生死锁因素产生死锁因素不仅与系统拥有的资源数量有关，而且与不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关。及并发进程的推进顺序有关。993.6
87、.2 3.6.2 死锁防止死锁防止(1)(1)系统形成死锁的四个必要条件系统形成死锁的四个必要条件0互斥条件：进程互斥使用资源互斥条件：进程互斥使用资源0占占有有并并等等待待条条件件：申申请请新新资资源源时时不不释释放放已已占占有资源有资源0不不剥剥夺夺条条件件：一一个个进进程程不不能能抢抢夺夺其其他他进进程程占占有的资源有的资源0循循环环等等待待条条件件：存存在在一一组组进进程程循循环环等等待待资资源源的状态的状态100死锁防止死锁防止(2)(2) 破坏第一个条件破坏第一个条件使资源可同时访问而不是互斥使用，使资源可同时访问而不是互斥使用， 破坏第三个条件破坏第三个条件采用剥夺式调度方法，采
88、用剥夺式调度方法，当当进进程程在在申申请请资资源源未未获获准准许许的的情情况况下下, ,如如主主动动释释放资源放资源( (一种剥夺式一种剥夺式),),然后才去等待。然后才去等待。 破坏第二个条件或第四个条件破坏第二个条件或第四个条件上上述述死死锁锁防防止止办办法法造造成成资资源源利利用用率率和和吞吞吐吐率率低低。介绍两种比较实用的死锁防止方法。介绍两种比较实用的死锁防止方法。101死锁的防止死锁的防止(3)(3)采用层次分配策略（破坏条件采用层次分配策略（破坏条件2 2和和4 4）0资源被分成多个层次资源被分成多个层次0当当进进程程得得到到某某一一层层的的一一个个资资源源后后，它它只只能能再再
89、申申请较高层次的资源请较高层次的资源0当当进进程程要要释释放放某某层层的的一一个个资资源源时时，必必须须先先释释放放占有的较高层次的资源占有的较高层次的资源0当当进进程程得得到到某某一一层层的的一一个个资资源源后后，它它想想申申请请该该层层的的另另一一个个资资源源时时，必必须须先先释释放放该该层层中中的的已已占占资源资源102死锁防止死锁防止(4)(4)层次策略的变种按序分配策略层次策略的变种按序分配策略把把系系统统的的所所有有资资源源排排一一个个顺顺序序，例例如如，系系统统若若共共有有n n个个进进程程, ,共共有有m m个个资资源源，用用riri表表示示第第i i个个资资源源，于是这于是这
90、m m个资源是：个资源是：r1,r2,r1,r2,rmrm规定如果进程不得在占用资源规定如果进程不得在占用资源ri(1im)ri(1im)后再后再申请申请rj(jrj(ji)i)。不难证明，按这种策略分配资源不难证明，按这种策略分配资源时系统不会发生死锁。时系统不会发生死锁。 1033.6.3 3.6.3 死锁避免死锁避免主主要要思思想想：动动态态的的检检测测资资源源分分配配状状态态以以确确保保循循环环等待条件不可能成立。等待条件不可能成立。银行家算法银行家算法0银行家拥有一笔周转资金银行家拥有一笔周转资金0客客户户要要求求分分期期贷贷款款，如如果果客客户户能能够够得得到到各各期期贷贷款款，就
91、就一一定定能能够够归归还还贷贷款款，否否则则就就一一定定不不能能归归还贷款还贷款0银行家应谨慎的贷款，防止出现坏帐银行家应谨慎的贷款，防止出现坏帐用银行家算法避免死锁用银行家算法避免死锁0操作系统（银行家）操作系统（银行家）0操作系统管理的资源操作系统管理的资源( (周转资金周转资金) )0进程（要求贷款的客户）进程（要求贷款的客户） 1041 1、安全状态、安全状态 最大需求最大需求 当前占有当前占有P0 10 5P0 10 5P1 4 2P1 4 2P2 9 2P2 9 2说明：某系统有说明：某系统有1212台磁带驱台磁带驱动器动器P0P0：最多要求最多要求1010台台P1P1：最多要求最
92、多要求4 4台台P2P2：最多要求最多要求9 9台台P1 P1 分配分配2 2；用完释放；用完释放4 4；则系统剩余；则系统剩余5 5P0 P0 分配分配5 5；用完释放；用完释放1010；则系统剩余；则系统剩余1010P2 P2 分配分配7 7；用完释放；用完释放9 9；则系统剩余；则系统剩余1212若存在一个安全序列，则系统处于安全状态若存在一个安全序列，则系统处于安全状态例例P1P2105死锁死锁不安全不安全安全安全安全、不安全和死锁状态空间安全、不安全和死锁状态空间结论：结论：安全状态不是死锁状态安全状态不是死锁状态死锁状态是不安全状态死锁状态是不安全状态不是所有不安全状态都是死锁不是
93、所有不安全状态都是死锁状态状态1062 2、银行家算法、银行家算法数据结构数据结构AvailableAvailable：Availablej=kAvailablej=k0资源类型资源类型R Rj j 现有现有k k个实例个实例MaxMax：Maxi,j=kMaxi,j=k0进程进程P Pi i最多可申请最多可申请k k个个R Rj j的实例的实例AllocationAllocation：Allocationi,j=kAllocationi,j=k0进程进程P Pi i现在已经分配了现在已经分配了k k个个R Rj j的实例的实例NeedNeed：Needi,j=kNeedi,j=k0进程进程P
94、 Pi i还可能申请还可能申请k k个个R Rj j的实例的实例0Needi,j = Maxi,j - Allocationi,jNeedi,j = Maxi,j - Allocationi,j107符号说明符号说明X=YX=Y0（X X和和Y Y是长度为是长度为n n的向量），当且仅当对所有的向量），当且仅当对所有i=1,2,ni=1,2,n，Xi=YiXi=YiAllocationAllocationi i 0表示分配给进程表示分配给进程P Pi i的资源（将的资源（将AllocationAllocation每行作为向每行作为向量）量）NeedNeed同同AllocationAllocat
95、ion108安全性算法安全性算法用于确定计算机系统是否处于安全状态用于确定计算机系统是否处于安全状态1)1)设设WorkWork和和FinishFinish分别是长度为分别是长度为m m和和n n的向量，初始化的向量，初始化Work:=AvailableWork:=Available，Finishi=false(i=1,2,n)Finishi=false(i=1,2,n)2)2)查找查找 i i 使其满足使其满足a.a.Finishi = falseFinishi = falseb.b.NeedNeedi i =Work =Work 若没有这样的若没有这样的 i i 存在，转到存在，转到4 4
96、）。）。3)3)Work := Work + Work := Work + AllocationAllocationi i FinishiFinishi := true := true 返回到返回到2 2）4)4)如果对所有如果对所有 i i，Finishi = trueFinishi = true，则系统处于安全状态则系统处于安全状态109资源请求算法资源请求算法设设RequestRequesti i 为进程为进程P Pi i的请求向量的请求向量1)1)如果如果RequestRequesti i = = NeedNeedi i ，那么转到第，那么转到第2 2）步。否则，产生）步。否则，产生出
97、错条件，因为进程已超过了其请求。出错条件，因为进程已超过了其请求。2)2)如果如果RequestRequesti i =Available =Available，那么转到第那么转到第3 3）步。否则，）步。否则， P Pi i等待，因为没有可用资源。等待，因为没有可用资源。3)3)假定系统可以分配给进程假定系统可以分配给进程P Pi i 所请求的资源，并按如下方式所请求的资源，并按如下方式修改状态：修改状态：0Available:= Available Available:= Available RequestRequesti i ; ;0AllocationAllocationi i :=
98、:= AllocationAllocationi i + + RequestRequesti i ; ;0NeedNeedi i := := NeedNeedi i RequestRequesti i ; ;4)4)调用安全性算法确定新状态是否安全调用安全性算法确定新状态是否安全0安全安全操作完成且进程操作完成且进程P Pi i分配到其所需要的资源分配到其所需要的资源0不安全不安全进程进程P Pi i必须等待，并将数据结构恢复到原状态必须等待，并将数据结构恢复到原状态（即（即 3 3）的逆操作）的逆操作）110银行家算法举例银行家算法举例说明：说明：v 5 5个进程个进程P P0 0P P4
99、4，v 3 3种资源类型种资源类型A A、B B、C C，且实例个数分别为且实例个数分别为1010、5 5、7 7v T0 T0时刻状态如图所示时刻状态如图所示 Allocation Max Available A B C A B C A B CP0 0 1 0 7 5 3 3 3 2 P1 2 0 0 3 2 2 P2 3 0 2 9 0 2P3 2 1 1 2 2 2P4 0 0 2 4 3 3111 问题：问题：1)1)T0T0时刻是否为安全状态？若是，给出安全序列时刻是否为安全状态？若是，给出安全序列2)2)若在若在T0T0时刻进程时刻进程P1P1请求资源（请求资源（1 1，0 0，2
100、 2），是否能实施），是否能实施分配？为什么？分配？为什么？3)3)在（在（2 2）的基础上，若进程）的基础上，若进程P4P4请求资源（请求资源（3 3，3 3，0 0），），是否能实施分配？为什么？是否能实施分配？为什么？4)4)在（在（3 3）的基础上，若进程）的基础上，若进程P0P0请求资源（请求资源（ 0 0，2 2，0 0），），是否能实施分配？为什么？是否能实施分配？为什么？112MaxA B CAllocationA B CNeedA B CAvailableA B CP07 5 30 1 07 4 33 3 2P13 2 22 0 01 2 2P29 0 23 0 26 0 0
101、P32 2 22 1 10 1 1P44 3 30 0 24 3 1转换（转换（NeedNeed）113、T0T0时刻是安全的，存在安全序列时刻是安全的，存在安全序列P1 P0 0 1 0True 10 5 77 4 310 4 7P03 0 2True10 4 76 0 07 4 5P20 0 2True7 4 54 3 17 4 3P42 1 1True7 4 30 1 15 3 2P32 0 0True5 3 21 2 23 3 2P1AllocationA B CfinishWork+allocationA B CNeedA B CWorkA B C1141Request（1，0，2）
102、Request（1，0，2）系统试探为系统试探为P1分配资源后，资源情况是：分配资源后，资源情况是：0 2 03 0 22 3 04 3 10 0 24 3 3P40 1 12 1 12 2 2P36 0 03 0 29 0 2P23 2 2P17 4 30 1 07 5 3P0AvailableA B CNeedA B CAllocationA B CMaxA B C4执行安全性算法执行安全性算法，得到安全序列，得到安全序列:WorkA B CNeedA B CAllocationA B CWork+allocationA B CfinishP12 3 00 2 03 0 25 3 2Tru
103、eP35 3 20 1 12 1 17 4 3TrueP47 4 34 3 10 0 27 4 5TrueP07 4 57 4 30 1 07 5 5TrueP27 5 56 0 03 0 210 5 7True P1P1请求资源请求资源Request(1Request(1，0 0，2), 2), 执行银行家算法执行银行家算法: :115 P0P0请求资源请求资源RequestRequest（0 0，2 2，0 0） , ,执行银行家算法执行银行家算法: : 1Request（0，2，0）Request（0，2，0）系统试探为系统试探为P0分配资源后，资源情况是：分配资源后，资源情况是：Max
104、A B CAllocationA B CNeedA B CAvailableA B CP07 5 30 3 07 2 32 1 0P13 2 23 0 20 2 0P29 0 23 0 26 0 0P32 2 22 1 10 1 1P44 3 30 0 24 3 14再进行安全性检查，再进行安全性检查，Available(2,1,0)不能满足任何不能满足任何进程，进入不安全状态，恢复旧数据结构，进程，进入不安全状态，恢复旧数据结构， P0等待。等待。 P4P4请求资源请求资源RequestRequest（3 3，3 3，0 0） , ,执行银行家算法执行银行家算法: : 1Request(3,
105、3,0)Request(3,3,0)=Available(2,3,0),P4等待等待.116 练习练习 Allocation Max Available A B C A B C A B CP1 2 1 2 5 5 9 2 3 3 P2 4 0 2 5 3 6 P3 4 0 5 4 0 11P4 2 0 4 4 2 5P5 3 1 4 4 2 4说明：说明：v 5 5个进程个进程P P1 1P P5 5，v 3 3种资源类型种资源类型A A、B B、C C，且实例个数分别为且实例个数分别为1717、5 5、2020v T0 T0时刻状态如图所示时刻状态如图所示117 问题：问题：1)1)T0T0
106、时刻是否为安全状态？若是，给出安全序列时刻是否为安全状态？若是，给出安全序列2)2)若在若在T0T0时刻进程时刻进程P2P2请求资源（请求资源（0 0，3 3，4 4），是否能实施），是否能实施分配？为什么？分配？为什么？3)3)在（在（2 2）的基础上，若进程）的基础上，若进程P4P4请求资源（请求资源（2 2，0 0，1 1），），是否能实施分配？为什么？是否能实施分配？为什么？4)4)在（在（3 3）的基础上，若进程）的基础上，若进程P1P1请求资源（请求资源（ 0 0，2 2，0 0），），是否能实施分配？为什么？是否能实施分配？为什么？118MaxA B CAllocationA B
107、 CNeedA B CAvailableA B CP15 5 92 1 23 4 72 3 3P25 3 64 0 21 3 4P3 4 0 114 0 50 0 6P44 2 52 0 42 2 1P54 2 43 1 41 1 0转换（转换（NeedNeed）119（1）T0T0时刻是安全的，存在安全序列时刻是安全的，存在安全序列P5 P4 2 0 4True 17 5 202 2 115 5 16P44 0 5True15 5 160 0 611 5 11P34 0 2True11 5 111 3 47 5 9P22 1 2True7 5 93 4 75 4 7P13 1 4True5
108、4 71 1 02 3 3P5AllocationABCfinishWork+allocationABCNeedABCWorkABC1201Request（0，3，4）Request（0，3，4）Available（2，3，3）；）；没有可用资源，不能分配，需等待！没有可用资源，不能分配，需等待！（2） P2P2请求资源请求资源Request(0Request(0，3 3，4), 4), 执行银行家算法执行银行家算法: :1211Request（2，0，1）Request（2，0，1）系统试探为系统试探为P4分配资源后，资源情况是：分配资源后，资源情况是：1 3 44 0 20 3 21103
109、14424P5020405425P40064054011P3536P2347212559P1AvailableABCNeedABCAllocationABCMaxABC4执行安全性算法执行安全性算法，得到安全序列，得到安全序列:WorkABCNeedABCAllocationABCWork+allocationABCfinishP4032020405437TrueP54371103147411TrueP174113472129513TrueP2951313440213515TrueP31351500640517520True（3）P4P4请求资源请求资源Request(2Request(2，0
110、 0，1), 1), 执行银行家算法执行银行家算法: :122（4 4）P1P1请求资源请求资源RequestRequest（0 0，2 2，0 0） , ,执行银行家算法执行银行家算法: : 1Request（0，2，0）Request（0，2，0）系统试探为系统试探为P1分配资源后，资源情况是：分配资源后，资源情况是：4再进行安全性检查，再进行安全性检查，Available(0,1,2)不能满足任何不能满足任何进程，进入不安全状态，恢复旧数据结构，进程，进入不安全状态，恢复旧数据结构， P1等待。等待。1 3 44 0 20 1 2110314424P5020405425P40064054
111、011P3536P2327232559P1AvailableABCNeedABCAllocationABCMaxABC1233.6.4 3.6.4 死锁检测和解除死锁检测和解除资源分配图和死锁定理资源分配图和死锁定理解决死锁问题的一条途径是死锁检测和解解决死锁问题的一条途径是死锁检测和解除，这种方法对资源的分配不加任何限制，除，这种方法对资源的分配不加任何限制，也不采取死锁避免措施，但系统定时地运也不采取死锁避免措施，但系统定时地运行一个行一个“死锁检测死锁检测”程序，判断系统内是程序，判断系统内是否已出现死锁，如果检测到系统已发生了否已出现死锁，如果检测到系统已发生了死锁，再采取措施解除它。
112、死锁，再采取措施解除它。124进程进程- -资源分配图资源分配图约定约定PiRjPiRj为请求边，表示进程为请求边，表示进程PiPi申请资源申请资源类类RjRj中的一个资源得不到满足而处于等待中的一个资源得不到满足而处于等待RjRj类资源的类资源的状态，该有向边从进程开始指到方框的边缘，表状态，该有向边从进程开始指到方框的边缘，表示进程示进程PiPi申请申请RjRj类中的一个资源。类中的一个资源。RjPiRjPi为分配边，表示为分配边，表示RjRj类中的一个资源已被进类中的一个资源已被进程程PiPi占用，由于已把一个具体的资源分给了进程占用，由于已把一个具体的资源分给了进程PiPi，故该有向边
113、从方框内的某个黑圆点出发指向故该有向边从方框内的某个黑圆点出发指向进程。进程。 125资源分配图例资源分配图例P1P2P3R4R3R2R1126简化进程简化进程- -资源分配图检测系统是否处于死锁状态资源分配图检测系统是否处于死锁状态(1)(1)如果进程如果进程- -资源分配图中无环路，则此时系统没资源分配图中无环路，则此时系统没有发生死锁。有发生死锁。如果进程如果进程- -资源分配图中有环路，且每个资源类资源分配图中有环路，且每个资源类中仅有一个资源，则系统中发生了死锁，此时，中仅有一个资源，则系统中发生了死锁，此时，环路是系统发生死锁的充要条件，环路中的进环路是系统发生死锁的充要条件，环路
114、中的进程便为死锁进程。程便为死锁进程。如如果果进进程程- -资资源源分分配配图图中中有有环环路路，且且涉涉及及的的资资源源类类中中有有多多个个资资源源，则则环环路路的的存存在在只只是是产产生生死死锁锁的必要条件而不是充分条件。的必要条件而不是充分条件。127P1P2P3R4R3R2R11 1、存在环存在死锁的资源分配图、存在环存在死锁的资源分配图1282 2、存在环但无死锁的资源分配图、存在环但无死锁的资源分配图P1P2P3R2R1P4129简化进程简化进程- -资源分配图检测系统是否处于死锁状态资源分配图检测系统是否处于死锁状态(2)(2)如如果果能能在在进进程程- -资资源源分分配配图图中
115、中消消去去此此进进程程的的所所有有请请求求边边和和分分配配边边，成成为为孤孤立立结结点点。经经一一系系列列简简化化，使使所所有有进进程程成成为为孤孤立立结结点点，则则该该图图是是可可完完全全简简化化的；否则则称该图是不可完全简化的。的；否则则称该图是不可完全简化的。系系统统为为死死锁锁状状态态的的充充分分条条件件是是：当当且且仅仅当当该该状状态态的的进进程程- -资资源源分分配配图图是是不不可可完完全全简简化化的的。该该充充分分条件称为死锁定理条件称为死锁定理。130检测方法：检测方法：1 1、每种资源类型只有单个实例、每种资源类型只有单个实例思想：将资源分配图转换成对应的等待图，看是否有环。
116、思想：将资源分配图转换成对应的等待图，看是否有环。转换方法举例如下：转换方法举例如下：P1P2P4P3P5R1R5R4R3R2P4P5P3P2P1资源分配图资源分配图对应的等待图对应的等待图1312 2、每种资源类型有多个实例、每种资源类型有多个实例思想：类似于银行家算法，描述如下思想：类似于银行家算法，描述如下1)1)设设WorkWork和和FinishFinish分别是长度为分别是长度为m m和和n n的向量，初始化的向量，初始化Work:=AvailableWork:=Available，若若 AllocationAllocationi i不为不为0 0，则，则 Finishi Fini
117、shi = false= false，否则，否则，Finishi = true (i=1,2,n)Finishi = true (i=1,2,n)2)2)查找查找 i i 使其满足使其满足a.a.Finishi = falseFinishi = falseb.b.RequestRequesti i =Work =Work 若没有这样的若没有这样的 i i 存在，转到存在，转到4 4）。）。3)3)Work := Work + Work := Work + AllocationAllocationi i Finishi := true Finishi := true 返回到返回到2 2）4)4)
118、如果对某个如果对某个 i i，Finishi = falseFinishi = false，则系统死锁（进程则系统死锁（进程P Pi i死锁）死锁）132例例说明：说明：v 5 5个进程个进程P P0 0P P4 4，v 3 3种资源类型种资源类型A A、B B、C C，且实例个数分别为且实例个数分别为7 7、2 2、6 6v T0 T0时刻状态如下时刻状态如下 Allocation Request Available A B C A B C A B CP0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 0P3 2 1 1 1 0 0P4 0 0
119、2 0 0 2133 问题：问题：1)1)T0T0时刻是否处于死锁状态？为什么？时刻是否处于死锁状态？为什么？2)2)若在若在T0T0时刻进程时刻进程P2P2请求资源（请求资源（0 0，0 0，1 1），新），新的状态是否处于死锁状态？为什么？的状态是否处于死锁状态？为什么？134（1）T0T0时刻是安全的，存在安全序列时刻是安全的，存在安全序列P0 P4 0 0 2True 7 2 60 0 27 2 4P42 0 0True7 2 42 0 25 2 4P12 1 1True5 2 41 0 03 1 3P33 0 3True3 1 30 0 00 1 0P20 1 0True0 1 00
120、 0 00 0 0P0AllocationA B CfinishWork+allocationA B CRequestA B CWorkA B C135 Allocation Request Available A B C A B C A B CP0 0 1 0 0 0 0 0 0 0 P1 2 0 0 2 0 2 P2 3 0 3 0 0 1P3 2 1 1 1 0 0P4 0 0 2 0 0 2（2 2）P2P2请求资源（请求资源（0 0，0 0，1 1）后的新状态：）后的新状态：WorkA B CRequestA B CAllocationA B CWork+allocationA B
121、CfinishP0P0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0T T对于对于i=1,2,3,4，均有均有Requesti(0,1,0)，因此死锁！因此死锁！1363 3、应用检测算法、应用检测算法何时调用检测算法所取决的因素何时调用检测算法所取决的因素0死锁可能发生的频率死锁可能发生的频率0当死锁发生时，受影响的进程数量当死锁发生时，受影响的进程数量常用方式常用方式0对于每个请求都调用死锁检测算法计算开销对于每个请求都调用死锁检测算法计算开销0在一个不频繁的时间间隔里调用检测算法通常不能在一个不频繁的时间间隔里调用检测算法通常不能确定死锁
122、进程中是哪些引起了死锁确定死锁进程中是哪些引起了死锁137死锁的解除：死锁的解除：1 1、结束进程、结束进程结束所有进程的执行，重新启动操作系统。结束所有进程的执行，重新启动操作系统。方法简单，但以前工作全部作废，损失很大。方法简单，但以前工作全部作废，损失很大。撤销陷于死锁的所有进程，解除死锁继续运撤销陷于死锁的所有进程，解除死锁继续运行。行。逐个撤销陷于死锁的进程，回收其资源重新逐个撤销陷于死锁的进程，回收其资源重新分派，直至死锁解除。分派，直至死锁解除。138死锁的解除：死锁的解除：2 2、剥夺资源、剥夺资源剥夺陷于死锁的进程占用的资源，但并不撤销它，剥夺陷于死锁的进程占用的资源，但并不
123、撤销它，直至死锁解除。可仿照撤销陷于死锁进程的条件直至死锁解除。可仿照撤销陷于死锁进程的条件来选择剥夺资源的进程来选择剥夺资源的进程根据系统保存的检查点，让所有进程回退，直到根据系统保存的检查点，让所有进程回退，直到足以解除死锁，这种措施要求系统建立保存检查足以解除死锁，这种措施要求系统建立保存检查点、回退及重启机制。点、回退及重启机制。当检测到死锁时，如果存在某些未卷入死锁的进当检测到死锁时，如果存在某些未卷入死锁的进程，而随着这些进程执行到结束，有可能释放足程，而随着这些进程执行到结束，有可能释放足够的资源来解除死锁。够的资源来解除死锁。139补充：补充：综合多种技术处理死锁综合多种技术处
124、理死锁把资源分级，以缩小死锁的危害范围：把资源分级，以缩小死锁的危害范围：0内部资源（由系统使用的内部资源（由系统使用的PCBPCB等）：采用资源编号等）：采用资源编号预防预防死锁；死锁；0内存：采用换入换出的抢占式分配内存：采用换入换出的抢占式分配预防预防死锁；死锁；0作业资源（如设备和文件等）：采用死锁作业资源（如设备和文件等）：采用死锁避免避免方法；方法；0对换空间（即磁盘交换空间）：由于通常可以知道最对换空间（即磁盘交换空间）：由于通常可以知道最大需求量，所以采用大需求量，所以采用预先分配预先分配方法。方法。140思考：思考：一个计算机系统中有某种资源一个计算机系统中有某种资源 10
125、10 个，供个，供n n个交互个交互型进程使用，每个进程都需要型进程使用，每个进程都需要 3 3 个资源。个资源。当当n n最大为何值时，系统能让尽量多的进程运行完最大为何值时，系统能让尽量多的进程运行完而不会发生死锁？而不会发生死锁？死锁是否会只涉及一个进程或一个资源？死锁是否会只涉及一个进程或一个资源？n=8否否1413.7 Linux3.7 Linux同步机制和通信机制同步机制和通信机制l同步机制同步机制l原子操作、信号量、关中断等原子操作、信号量、关中断等l通信机制通信机制l消息、共享主存消息、共享主存1423.8 Windows 20033.8 Windows 2003同步机制和通信
126、机制同步机制和通信机制1.1.同步机制同步机制提供互斥对象提供互斥对象 、信号量对象和事件对象及相应的、信号量对象和事件对象及相应的系统调用，用于进程和线程的互斥和同步。系统调用，用于进程和线程的互斥和同步。提供两个等待操作提供两个等待操作WaitForSingleObjectWaitForSingleObject和和WaitForMultipleObjectsWaitForMultipleObjects前者可在指定的时间内等待指定对象转换为可用状态前者可在指定的时间内等待指定对象转换为可用状态后者可在指定的时间内等待多个对象转换为可用状态后者可在指定的时间内等待多个对象转换为可用状态1432
127、.2.通信机制通信机制信号信号0一种低级通信方式，单向、异步。一种低级通信方式，单向、异步。共享存储区共享存储区0用于进程间的大数据量通信。用于进程间的大数据量通信。管道管道0在进程间以字节流方式传送信息。在进程间以字节流方式传送信息。邮件槽邮件槽0一种不定长和不可靠的单向消息通信机制。一种不定长和不可靠的单向消息通信机制。套接字套接字0一种网络通信机制。一种网络通信机制。144作业作业P218 10,29P218 10,29P220 8P220 8145补充、考虑下面一个系统在某一时刻的状态，使用银行家算法补充、考虑下面一个系统在某一时刻的状态，使用银行家算法回答下面问题：回答下面问题： a
128、.a.NeedNeed矩阵的内容是怎样的？矩阵的内容是怎样的？b.b.系统是否处于安全状态？系统是否处于安全状态？c.c.如果进程如果进程P1P1请求请求(0,4,2,0)(0,4,2,0)，这个请求能否立刻被满足？，这个请求能否立刻被满足？AllocationAllocationA B C DA B C DMaxMaxA B C DA B C DAvailableAvailableA B C DA B C DP0P00 0 1 20 0 1 20 0 1 20 0 1 21 5 2 01 5 2 0P1P11 0 0 01 0 0 01 7 5 01 7 5 0P2P21 3 5 41 3 5 42 3 5 62 3 5 6P3P30 6 3 20 6 3 20 6 5 20 6 5 2P4P40 0 1 40 0 1 40 6 5 60 6 5 6146
