教学课件PPT 同步、通信与死锁.ppt

《教学课件PPT 同步、通信与死锁.ppt》由会员分享，可在线阅读，更多相关《教学课件PPT 同步、通信与死锁.ppt（146页珍藏版）》请在三一办公上搜索。

1、1,第3章 同步、通信与死锁,主要内容并发进程临界区管理信号量与PV操作管程（删）进程通信死锁Linux同步机制和通信机制Windows2003同步机制和通信,2,3.1 并发进程,3.1.1 顺序程序设计 3.1.2 进程的并发性 3.1.3 进程的交互：协作和竞争,3,3.1.1 顺序程序设计,进程的顺序性一个进程在顺序处理器上的执行是严格按序的，一个进程只有当一个操作结束后，才能开始后继操作。顺序程序设计是把一个程序设计成一个顺序执行的程序模块，顺序的含义不但指一个程序模块内部，也指两个程序模块之间。,4,顺序程序设计的特性,程序执行的顺序性程序环境的封闭性程序执行结果的确定性计算过程的

2、可再现性,顺序程序设计的缺点计算机系统效率不高。,5,3.1.2 进程的并发性,1、并发程序设计进程执行的并发性：一组进程的执行在时间上是重叠的。并发性举例：有两个进程A(a1、a2、a3)和B(b1、b2、b3)并发执行。a1、a2、a3、b1、b2、b3 顺序执行 a1、b1、a2、b2、a3、b3 并发执行从宏观上看，一个时间段中几个进程都在同一处理器上，处于运行还未运行结束状态。从微观上看，任一时刻仅有一个进程在处理器上运行。,6,串行工作图示,i1,p1,o1,i2,p2,o2,7,并行工作图示,8,并发的实质,并发的实质是一个处理器在几个进程之间的多路复用，并发是对有限的物理资源强

3、制行使多用户共享，消除计算机部件之间的互等现象，以提高系统资源利用率。,9,2、并发进程的特性,无关的并发进程一组并发进程分别在不同的变量集合上操作，一个进程的执行与其他并发进程的进展无关。并发进程的无关性是进程的执行与时间无关的一个充分条件，又称为Bernstein条件。交互的并发进程一组并发进程共享某些变量，一个进程的执行可能影响其他并发进程的结果。,10,Bernstein条件,R(pi)=a1,a2,an，程序pi在执行期间引用的变量集W(pi)=b1,b2,bm，程序pi在执行期间改变的变量集若两个程序的变量集交集之和为空集：R(p1)W(p2)R(p2)W(p1)W(p1)W(p2

4、)=则并发进程的执行与时间无关。,11,Bernstein条件举例,例如，有如下四条语句：S1:a:=x+y S2:b:=z+1 S3:c:=a b S4:w:=c+1于是有：R(S1)=x,y,R(S2)=z，R(S3)=a,b，R(S4)=c；W(S1)=a,W(S2)=b，W(S3)=c，W(S4)=w。S1和S2可并发执行，满足Bernstein条件。其他语句并发执行可能会产生与时间有关的错误。,12,并发程序设计的优点,对于单处理器系统,可让处理器和各I/O设备同时工作,发挥硬部件的并行能力。对于多处理器系统,可让各进程在不同处理器上物理地并行，加快计算速度。简化了程序设计任务。,1

5、3,采用并发程序设计的目的,充分发挥硬件的并行性，提高系统效率。硬件能并行工作仅有了提高效率的可能性，硬部件并行性的实现需要软件技术去利用和发挥，这种软件技术就是并发程序设计。并发程序设计是多道程序设计的基础，多道程序的实质就是把并发程序设计引入到系统中。,14,3、与时间有关的错误,对于一组交互的并发进程，执行的相对速度无法相互控制，各种与时间有关的错误就可能出现。与时间有关错误的表现形式：结果不唯一永远等待,15,（结果不唯一）机票问题,/飞机票售票问题void T1()void T2()按旅客订票要求找到Aj;按旅客订票要求找到Aj;int X1=Aj;int X2=Aj;if(X1=1

6、)if(X2=1)X1-;X2-;Aj=X1;Aj=X2;输出一张票;输出一张票;else else 输出信息票已售完;输出信息票已售完;,16,T1、T2并发执行，可能出现如下交叉情况：T1:X1=Aj;/X1=mT2:X2=Aj;/X2=mT2:X2-;Aj=X2;输出一张票;/Aj=m-1T1:X1-;Aj=X1;输出一张票;/Aj=m-1同一张票卖给两位旅客（若只有一张余票）或者余票数不正确（若有多张余票）。,17,（永远等待）主存管理问题,申请和归还主存资源问题int X=memory;/memory为初始主存容量void borrow(int B)void return(int B

7、)while(BX)X=X+B;进程进入等待主存资源队列;修改主存分配表;X=X-B;释放等主存资源进程;修改主存分配表，进程获得主存资源;,18,若对borrow和return的并发执行不加限制将会导致错误，例如：Borrow:while(BX);Return:X=X+B;修改主存分配表;释放等待主存资源的进程；此时，因为borrow还没有进入等待队列，因此，return的释放操作是空操作，当borrow进入等待队列时，可能没有进程再来归还，处于永远等待状态。,19,3.1.3 进程的交互：竞争与协作(1)第一种是竞争关系,系统中的多个进程之间彼此无关系统中的多个进程之间彼此相关 资源竞争的

8、两个控制问题：一个是死锁(Deadlock)问题，一个是饥饿(Starvation)问题 既要解决饥饿问题，又要解决死锁问题。进程互斥是指若干个进程因相互争夺独占型资源时所产生的竞争制约关系。,20,进程的交往：竞争与协作(2)第二种是协作关系,某些进程为完成同一任务需要分工协作。进程同步指为完成共同任务的并发进程基于某个条件来协调它们的活动，因为需要在某些位置上排定执行的先后次序而等待、传递信号或消息所产生的协作制约关系。进程同步指两个以上进程基于某个条件来协调它们的活动。一个进程的执行依赖于协作进程的消息或信号，当一个进程没有得到来自于协作进程的消息或信号时需等待，直到消息或信号到达才被唤

9、醒。进程互斥关系是一种特殊的进程同步关系，即逐次使用互斥共享资源，是对进程使用资源次序上的一种协调。,21,3.2 临界区管理,3.2.1 互斥与临界区3.2.2 实现临界区管理的几种尝试3.2.3 实现临界区管理的软件方法3.2.4 实现临界区管理的硬件设施,22,3.2.1 互斥与临界区(1),并发进程中与共享变量有关的程序段叫“临界区”，共享变量代表的资源叫“临界资源”。与同一变量有关的临界区分散在各进程的程序段中，而各进程的执行速度不可预知。如果保证进程在临界区执行时，不让另一个进程进入临界区，即各进程对共享变量的访问是互斥的，就不会造成与时间有关的错误。,23,互斥与临界区(2),临

10、界区调度原则：一次至多一个进程能够进入临界区内执行；如果已有进程在临界区，其他试图进入的进程应等待；进入临界区内的进程应在有限时间内退出，以便让等待进程中的一个进入。临界区调度原则总结：互斥使用，有空让进；忙则等待，有限等待；择一而入，算法可行。,24,3.2.2 临界区管理的尝试(1),bool inside1=false;/P1不在其临界区内bool inside2=false;/P2不在其临界区内cobegin/*cobegin和coend表示括号中的进程是一组并发进程*/process P1()process P2()while(inside2);/等待 while(inside1);

11、/等待 inside1=true;inside2=true;临界区;临界区;inside1=false;inside2=false;coend,可能不满足互斥条件,25,临界区管理的尝试(2),bool inside1=false;/P1不在其临界区内bool inside2=false;/P2不在其临界区内cobeginprocess P1()process P2()inside1=true;inside2=true;while(inside2);/等待 while(inside1);/等待临界区;临界区;inside1=false;inside2=false;coend,可能出现死循环,2

12、6,3.2.3实现临界区的软件算法Peterson算法(1),bool inside2;inside0=false;inside1=false;enum 0,1 turn;,27,Peterson算法(2),cobeginprocess P0()inside0=true;turn=1;while(inside1,28,Peterson算法(3),process P1()inside1=true;turn=0;while(inside0 coend,29,3.2.4 实现临界区管理的硬件设施,关中断测试并建立指令（删）对换指令（删）,30,关中断,实现互斥的最简单方法关中断适用场合简单有效，对操

13、作系统自身有用，可在更新共享变量或列表的几条指令期间禁止中断。关中断方法的缺点不适合作为通用的互斥机制，关中断时间过长会影响性能和系统效率；不适应于多处理器计算机系统，因为一个处理器关中断，并不能防止进程在其它处理器上执行相同的临界段代码；若将这项权力赋予用户会存在危险，若用户未开中断，则系统可能因此而终止。,31,3.3 信号量与PV操作,3.3.1 同步与同步机制3.3.2 信号量与PV操作3.3.3 信号量实现互斥3.3.4 五个哲学家吃通心面问题3.3.5 生产者-消费者问题3.3.6 读者-写者问题3.3.7 理发师问题,32,3.3.1 同步和同步机制,著名的生产者-消费者问题是计

14、算机操作系统中并发进程内在关系的一种抽象，是典型的进程同步问题。在操作系统中，生产者进程可以是计算进程、发送进程；而消费者进程可以是打印进程、接收进程等等。解决好生产者-消费者问题就解决好了一类并发进程的同步问题。,33,生产者-消费者问题表述,有界缓冲问题有n个生产者和m个消费者，连接在一个有k个单位缓冲区的有界缓冲上。其中，pi和cj都是并发进程，只要缓冲区未满，生产者pi生产的产品就可投入缓冲区；只要缓冲区不空，消费者进程cj就可从缓冲区取走并消耗产品。,34,生产者-消费者问题算法描述(1),int k;typedef anyitem item;/item类型item bufferk;

15、int in=0,out=0,counter=0;,35,生产者-消费者问题算法描述(2),process producer(void)while(true)/无限循环 produce an item in nextp;/生产一个产品 if(counter=k)/缓冲满时，生产者睡眠 sleep(producer);bufferin=nextp;/将一个产品放入缓冲区 in=(in+1)%k;/指针推进 counter+;/缓冲内产品数加1 if(counter=1)/缓冲为空，加进一件产品 wakeup(consumer);/并唤醒消费者,36,生产者-消费者问题算法描述(3),proces

16、s consumer(void)while(true)/无限循环if(counter=0)/缓冲区空，消费者睡眠 sleep(consumer);nextc=bufferout;/取一个产品到nextc out=(out+1)%k;/指针推进 counter-;/取走一个产品，计数减1if(counter=k-1)/缓冲满了，取走一件产品并唤 wakeup(producer);/醒生产者consume the item in nextc;/消耗产品,37,生产者-消费者问题的算法描述(4),生产者和消费者进程对counter的交替执行会使其结果不唯一。生产者和消费者进程的交替执行会导致进程永远

17、等待。,38,3.3.2 信号量与PV操作(1),前节种种方法解决临界区调度问题的缺点:1)对不能进入临界区的进程，采用忙式等待测试法，浪费CPU时间。2)将测试能否进入临界区的责任推给各个竞争的进程会削弱系统的可靠性，加重了用户编程负担。1965年E.W.Dijkstra提出了新的同步工具-信号量和P、V操作。,39,信号量与PV操作(2),信号量：一种软件资源原语：内核中执行时不可被中断的过程P操作原语和V操作原语一个进程在某一特殊点上被迫停止执行直到接收到一个对应的特殊变量值，这种特殊变量就是信号量(semaphore)，复杂的进程合作需求都可以通过适当的信号结构得到满足。,40,信号量

18、与PV操作(3),操作系统中，信号量表示物理资源的实体，它是一个与队列有关的整型变量。实现时，信号量是一种记录型数据结构，有两个分量：一个是信号量的值，另一个是信号量队列的队列指针。,41,信号量分类,信号量按其用途分为公用信号量：用户实现进程互斥，初值为1，相关进程均可在此信号量上执行PV操作；私有信号量：多用于并发进程同步，初值为0或正整数，仅允许此信号量所拥有的进程执行P操作，而其它相关进程可执行V操作。信号量按其取值分为二元信号量：仅允许取值为0或1，主要用于解决互斥问题；一般信号量：允许取大于1的整型值，主要用于解决同步问题。,42,一般信号量(1),设s为一个记录型数据结构,一个分

19、量为整形量value,另一个为信号量队列queue,P和V操作原语定义：P(s)；将信号量s减去l，若结果小于0，则调用P(s)的进程被置成等待信号量s的状态。V(s)：将信号量s加1，若结果不大于0，则释放一个等待信号量s的进程。,43,一般信号量(2),typedef struct semaphore int value;/信号量值struct pcb*list;/信号量队列指针;void P(semaphore,44,一般信号量(3),推论1：若信号量s为正值，则该值等于在封锁进程之前对信号量s可施行的P操作数、亦等于s所代表的实际还可以使用的物理资源数推论2：若信号量s为负值，则其绝对

20、值等于登记排列在该信号量s队列之中等待的进程个数、亦即恰好等于对信号量s实施P操作而被封锁起来并进入信号量s队列的进程数推论3：通常，P操作意味着请求一个资源，V操作意味着释放一个资源。在一定条件下，P操作代表挂起进程操作，而V操作代表唤醒被挂起进程的操作,45,3.3.3 信号量实现互斥,semaphore mutex;mutex=1;cobegin process Pi()/i=1,n P(mutex);临界区;V(mutex);coend,46,3.3.4 信号量解决五个哲学家吃通心面问题(1),有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘子，每两人之间放一把叉子。

21、每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两把叉子，且每人只能直接从自己左边或右边去取叉子。,47,信号量解决五个哲学家吃通心面问题(2),48,哲学家吃通心面问题(3),semaphore fork5;for(int i=0;i5;i+)forki=1;cobeginprocess philosopher_i()/i=0,1,2,3,4while(true)think();P(forki);P(fork(i+1)%5);eat();V(forki);V(fork(i+1)%5);coend,可能死锁！,49,有若干种办法可避免这类死锁,上述解法可能出现永远等待，有若干种

22、办法可避免死锁：至多允许四个哲学家同时吃；奇数号先取左手边的叉子，偶数号先取右手边的叉子；每个哲学家取到手边的两把叉子才吃，否则一把叉子也不取。,50,3.3.5 信号量解决生产者消费者问题,一个生产者、一个消费者共享一个缓冲区一个生产者、一个消费者共享多个缓冲区多个生产者、多个消费者共享多个缓冲区,51,一个生产者、一个消费者共享一个缓冲区的解,int B;semaphore empty;/可以使用的空缓冲区数semaphore full;/缓冲区内可以使用的产品数empty=1;/缓冲区内允许放入一件产品full=0;/缓冲区内没有产品,52,cobeginprocess producer

23、()process consumer()while(true)while(true)produce();P(full);P(empty);take()from B;append()to B;V(empty);V(full);consume();coend,53,多个生产者/消费者、共享多个缓冲区的解,item Bk;semaphore empty;empty=k;/可以使用的空缓冲区数semaphore full;full=0;/缓冲区内可以使用的产品数semaphore mutex;mutex=1;/互斥信号量int in=0;/放入缓冲区指针int out=0;/取出缓冲区指针,54,co

24、beginprocess producer_i()process consumer_j()while(true)while(true)produce();P(full);P(empty);P(mutex);P(mutex);take()from Bout;append to Bin;out=(out+1)%k;in=(in+1)%k;V(mutex);V(mutex);V(empty);V(full);consume();coend,55,3.3.6 信号量解决读者-写者问题(1),有两组并发进程：读者和写者，共享一个文件F，要求：允许多个读者同时执行读操作任一写者在完成写操作之前不允许其它读

25、者或写者工作写者执行写操作前，应让已有的写者和读者全部退出,56,信号量解决读者写者问题(2),int readcount=0;/读进程计数semaphore writeblock,mutex;writeblock=1;mutex=1;,57,信号量解决读者写者问题(3),cobeginprocess reader_i()process writer_j()P(mutex);P(writeblock);readcount+;写文件;if(readcount=1)V(writeblock);P(writeblock);V(mutex);读文件;P(mutex);readcount-;if(rea

26、dcount=0)V(writeblock);V(mutex);coend,58,3.3.7 信号量解决理发师问题(1),理发店里有一位理发师、一把理发椅和n把供等候理发的顾客坐的椅子如果没有顾客，理发师便在理发椅上睡觉一个顾客到来时，它必须叫醒理发师如果理发师正在理发时又有顾客来到，则如果有空椅子可坐，就坐下来等待，否则就离开,59,信号量解决理发师问题(2),int waiting=0;/等候理发顾客坐的椅子数int CHAIRS=N;/为顾客准备的椅子数semaphore customers,barbers,mutex;customers=0;barbers=0;mutex=1;,60,

27、信号量解决理发师问题(3),cobeginprocess barber()while(true)P(customers);/有顾客吗？若无顾客，理发师睡眠 P(mutex);/若有顾客时，进入临界区waiting-;/等候顾客数少一个 V(barbers);/理发师准备为顾客理发 V(mutex);/退出临界区cut_hair();/理发师正在理发(非临界区),61,process customer_i()P(mutex);/进入临界区 if(waitingCHAIRS)/有空椅子吗waiting+;/等候顾客数加1 V(customers);/唤醒理发师 V(mutex);/退出临界区 P(

28、barbers);/理发师忙，顾客坐下等待get_haircut();/否则顾客坐下理发 else V(mutex);/人满了，走吧！coend,62,总结补充,信号量小结P、V操作小结针对信号量问题的补充练习,63,1、信号量小结,一个信号量可用于n个进程的同步互斥；且只能由P、V操作修改。用于互斥时，S初值为1，取值为1-(n-1)（相当于临界区的通行证，实际上也是资源个数）S=1：临界区可用 S=0：已有一进程进入临界区 S=0 S=0:表示可用资源个数 S0:表示该资源的等待队列长度,64,2、P、V操作小结,P(S)：请求分配一个资源。V(S)：释放一个资源。P、V操作必须成对出现。

29、用于互斥时，位于同一进程内；用于同步时，交错出现于两个合作进程内。多个P操作的次序不能颠倒，否则可能导致死锁。多个V操作的次序可任意。,65,3、针对信号量问题的补充练习,桌子上有一个盘子，可以存放一个水果。父亲总是放苹果到盘子中，而母亲总是放香蕉到盘子中；儿子专等吃盘中的香蕉，而女儿专等吃盘中的苹果。,分析：生产者消费者问题的一种变形，生产者、消费者以及放入缓冲区的产品都有两类，但每类消费者只消费其中固定的一种产品。数据结构：semaphore dish，apple，banana;dish：表示盘子是否为空，初值为1apple：表示盘中是否有苹果，初值为0banana：表示盘中是否有香蕉，初

30、值为0,66,cobeginprocess father()P(dish);将苹果放到盘中；V(apple);process mother()P(dish);将香蕉放到盘中；V(banana);,process son()P(banana);从盘中取出香蕉；V(dish);process daughter()P(apple);从盘中取出苹果；V(dish);coend.,67,哲学家甲请哲学家乙、丙、丁到某处讨论问题，约定全体到齐后开始讨论；在讨论的间隙四位哲学家进餐，每人进餐时都需使用刀、叉各一把，餐桌上的布置如下图所示。用信号量机制说明四位哲学家的同步互斥过程。,食品,乙,丙,丁,甲,刀2

31、,叉1,刀1,叉2,68,分析标准的哲学家进餐问题，只是哲学家人数和餐具及分布与经典哲学家进餐问题略有不同数据结构semaphore fork1,fork2,knife1,knife2;frok表示叉，knife表示刀，初值均为1,69,cobeginprocess pa()/哲学家甲 P(knife1);P(fork1);进餐；V(knife1);V(fork1);讨论问题；,process pb()/哲学家乙 P(knife2);P(fork1);进餐；V(knife2);V(fork1);讨论问题；,70,process pc()/哲学家丙 P(knife2);P(fork2);进餐；V

32、(knife2);V(fork2);讨论问题；,process pd()/哲学家丁 P(knife1);P(fork2);进餐；V(knife1);V(fork2);讨论问题；coend.,71,有一个阅览室，读者进入时必须先在一张登记表上登记，此表为每个座位列出一个表目，包括座位号、姓名，读者离开时要注意注销登记信息；假如阅览室共有100个座位，请用信号量和P、V操作实现用户进程的同步算法。,72,分析：实际上是一个非常简单的同步-互斥问题，不要想复杂了数据结构：structchar name10;int number;A100;semaphore mutex,seatcount;mutex

33、：用来互斥，初值为1seatcount：对空座位计数，初值为100for(int i=0;i100;i+)Ai.number=i;Ai.name=null;,73,cobeginprocess readeri(char readername)P(seatcount);P(mutex)；for(int i=0;i100;i+)if(Ai.name=null)Ai.name=readername;reader get the seat number=i;V(mutex);进入阅览室，在座位号i处坐下读书；P(mutex);Ai.name=null;V(mutex);V(seatcount);离开阅

34、览室；coend;,74,在一个盒子里，混装了数量相等的黑白围棋子。现在用自动分拣系统把黑子、白子分开，设分拣系统有两个进程P1和P2，其中P1拣白子，P2拣黑子。规定每个进程每次拣一子，当一个进程在拣时，不允许另一个进程去拣；当一个进程拣了一子时，必须让另一个进程去拣。试用信号量和P、V操作协调两个进程的并发执行。,分析：实际上就是两个进程的同步问题。数据结构：semaphore S1，S2;S1 和S2 分别表示可拣白子和黑子，不失一般性，若令先拣白子。初值，S1=1；S2=0；,75,cobeginprocess P1()while(true)P(S1);拣白子；V(S2);,proce

35、ss P2()while(true)P(S2);拣黑子；V(S1);coend.,76,3.5 进程通信,3.5.1 信号通信机制 3.5.2 管道通信机制 3.5.3 共享主存通信机制 3.5.4 消息传递通信机制,77,进程通信概念,并发进程之间的交互必须满足两个基本要求：同步和通信。进程竞争资源时要实施互斥，互斥是一种特殊的同步，实质上需要解决好进程同步问题，进程同步是一种进程通信，通过修改信号量，进程之间建立起联系，相互协调运行和协同工作。进程协同工作时，需互相交换信息，可能是少量信息，也可能交换大批数据。进程之间互相交换信息的工作称为进程通信IPC（InterProcess Comm

36、unication）。,78,进程间通信的方式,信号(signal)通信机制管道(pipeline)通信机制 消息传递(message passing)通信机制 信号量(semaphore)通信机制共享主存(shared memory)通信机制,79,进程间通信的方式发展,UNIX发展历史中，AT&T的Bell与加大伯克利的BSD是两大主力。Bell致力于改进传统的进程IPC，形成了SYSTEM IPC机制。BSD在改进IPC的同时，把网络通信规程(TCP/IP)实现到UNIX内核中，考虑把同一计算机上的进程通信纳入更广的网络范围的进程间通信，这种努力结果出现了socket网络通信机制。,80

37、,3.5.1 信号通信机制,信号机制又称软中断，一种简单的通信机制，通过发送一个指定信号通知进程某个异常事件发生。用户、内核和进程都能生成信号请求：1)用户-用户能通过输入ctrl+c，或终端驱动程序分配给信号控制字符的其他任何键来请求内核产生信号。2)内核-当进程执行出错时，内核检测到事件并给进程发送信号，例如，非法段存取、浮点数溢出、或非法操作码，内核也利用信号通知进程种种特定事件发生。3)进程-进程可通过系统调用kill给另一个进程发送信号，一个进程可通过信号与另一个进程通信。,81,Linux系统信号分类,与进程终止相关的信号与进程例外事件相关的信号与进程执行系统调用相关的信号与进程终

38、端交互相关的信号用户进程发信号跟踪进程执行的信号,82,3.5.2 管道通信机制,管道(pipeline)是连接读写进程的一个特殊文件，允许进程按先进先出方式传送数据,也能使进程同步执行操作。发送进程以字符流形式把大量数据送入管道，接收进程从管道中接收数据，所以叫管道通信。管道的实质是一个共享文件，基本上可借助于文件系统的机制实现，包括（管道）文件的创建、打开、关闭和读写。,83,共享文件通信机制,读写进程相互协调，必须做到：进程对通信机构的使用应该互斥，一个进程正在使用某个管道写入或读出数据时，另一个进程就必须等待。(write阻塞、read阻塞)发送者和接收者双方必须能够知道对方是否存在，

39、如果对方已经不存在，就没有必要再发送信息。,84,3.5.3 共享主存通信机制,85,3.5.4 消息传递(1),什么是消息传递（message passing）?消息和消息传递机制 基本的消息传递原语send，receive,86,消息传递(2),采用消息传递机制后，一个正在执行的进程可在任何时刻向另一个正在执行的进程发送消息；一个正在执行的进程也可在任何时刻向正在执行的另一个进程请求消息。一个进程在某一时刻的执行依赖于另一进程的消息或等待其他进程对发出消息的回答，那么，消息传递机制紧密地与进程的阻塞和释放相联系。消息传递就进一步扩充了并发进程间对数据的共享，提供了进程同步的能力。,87,直

40、接通信,发送或接收消息的进程必须指出信件发给谁或从谁那里接收消息。原语send（P，消息）把一个消息发送给进程P原语receive（Q，消息）从进程Q接收一个消息,88,间接通信,原语send（A，信件）把一封信件（消息）传送到信箱A原语receive（A，信件）从信箱A接收一封信件（消息）信箱是存放信件的存储区域，每个信箱可分成信箱特征和信箱体两部分。信箱特征指出信箱容量、信件格式、指针等；信箱体用来存放信件,89,间接通信的实现,发送信件：如果指定信箱未满，则将信件送入信箱中由指针所指示的位置，并释放等待该信箱中信件的等待者；否则发送信件者被置成等待信箱状态接收信件：如果指定信箱中有信，则

41、取出一封信件，并释放等待信箱的等待者，否则接收信件者被置成等待信箱中信件的状态,90,3.6 死锁,3.6.1 死锁产生3.6.2 死锁防止3.6.3 死锁避免3.6.4 死锁检测和解除,91,3.6.1 死锁产生若干死锁的例子,例进程推进顺序不当产生死锁 设系统有打印机、读卡机各一台，被进程和共享。两个进程并发执行，按下列次序请求和释放资源：进程 进程 请求读卡机 请求打印机 请求打印机 请求读卡机 释放读卡机 释放读卡机 释放打印机 释放打印机,92,P,Q,读卡机,打印机,出现死锁！,93,例 PV操作使用不当产生死锁,进程Q1 进程Q2 P(S1);P(S2);P(S2);P(S1);

42、使用r1和r2;使用r1和r2 V(S1);V(S2);V(S2);V(S1);,94,Q1,Q2,S1,S2,出现死锁！,95,例资源分配不当引起死锁,若系统中有m个资源被n个进程共享，每个进程都要求个资源，而m nK时，即资源数小于进程所要求的总数时，如果分配不得当就可能引起死锁。,96,例对临时性资源使用不加限制引起死锁,进程通信使用的信件是一种临时性资源，如果对信件的发送和接收不加限制，可能引起死锁。进程P1等待进程P3的信件S3来到后再向进程P2发送信件S1；P2又要等待P1的信件S1来到后再向P3发送信件S2；而P3也要等待P2的信件S2来到后才能发出信件S3。这种情况下形成了循环

43、等待，产生死锁。,97,P1,P2,S1,S2,出现死锁！,P3,S3,98,死锁定义,操作系统中的死锁：如果在一个进程集合中的每个进程都在等待只能由该集合中的其他一个进程才能引发的事件，则称一组进程或系统此时发生死锁。例如，n个进程P1、P2，Pn，Pi因为申请不到资源Rj而处于等待状态，而Rj又被Pi+1占有，Pn欲申请的资源被P1占有，此时这n个进程的等待状态永远不能结束，则说这n个进程处于死锁状态。,99,产生死锁因素,不仅与系统拥有的资源数量有关，而且与资源分配策略，进程对资源的使用要求以及并发进程的推进顺序有关。,100,3.6.2 死锁防止(1),系统形成死锁的四个必要条件互斥条

44、件：进程互斥使用资源占有并等待条件：申请新资源时不释放已占有资源不剥夺条件：一个进程不能抢夺其他进程占有的资源循环等待条件：存在一组进程循环等待资源的状态,101,死锁防止(2),破坏第一个条件使资源可同时访问而不是互斥使用，破坏第三个条件采用剥夺式调度方法，当进程在申请资源未获准许的情况下,如主动释放资源(一种剥夺式),然后才去等待。破坏第二个条件或第四个条件上述死锁防止办法造成资源利用率和吞吐率低。介绍两种比较实用的死锁防止方法。,102,死锁的防止(3),采用层次分配策略（破坏条件2和4）资源被分成多个层次当进程得到某一层的一个资源后，它只能再申请较高层次的资源当进程要释放某层的一个资源

45、时，必须先释放占有的较高层次的资源当进程得到某一层的一个资源后，它想申请该层的另一个资源时，必须先释放该层中的已占资源,103,死锁防止(4),层次策略的变种按序分配策略把系统的所有资源排一个顺序，例如，系统若共有n个进程,共有m个资源，用ri表示第i个资源，于是这m个资源是：r1,r2,rm规定如果进程不得在占用资源ri(1im)后再申请rj(ji)。不难证明，按这种策略分配资源时系统不会发生死锁。,104,3.6.3 死锁避免,主要思想：动态的检测资源分配状态以确保循环等待条件不可能成立。银行家算法银行家拥有一笔周转资金客户要求分期贷款，如果客户能够得到各期贷款，就一定能够归还贷款，否则就

46、一定不能归还贷款银行家应谨慎的贷款，防止出现坏帐用银行家算法避免死锁操作系统（银行家）操作系统管理的资源(周转资金)进程（要求贷款的客户）,105,1、安全状态,最大需求 当前占有P0 10 5P1 4 2P2 9 2,说明：某系统有12台磁带驱动器P0：最多要求10台P1：最多要求4台P2：最多要求9台,P1 分配2；用完释放4；则系统剩余5P0 分配5；用完释放10；则系统剩余10P2 分配7；用完释放9；则系统剩余12,若存在一个安全序列，则系统处于安全状态例,106,死锁,不安全,安全,安全、不安全和死锁状态空间,结论：安全状态不是死锁状态死锁状态是不安全状态不是所有不安全状态都是死锁

47、状态,107,2、银行家算法,数据结构Available：Availablej=k资源类型Rj 现有k个实例Max：Maxi,j=k进程Pi最多可申请k个Rj的实例Allocation：Allocationi,j=k进程Pi现在已经分配了k个Rj的实例Need：Needi,j=k进程Pi还可能申请k个Rj的实例Needi,j=Maxi,j-Allocationi,j,108,符号说明X=Y（X和Y是长度为n的向量），当且仅当对所有i=1,2,n，Xi=YiAllocationi 表示分配给进程Pi的资源（将Allocation每行作为向量）Need同Allocation,109,安全性算法,用

48、于确定计算机系统是否处于安全状态设Work和Finish分别是长度为m和n的向量，初始化Work:=Available，Finishi=false(i=1,2,n)查找 i 使其满足Finishi=falseNeedi=Work 若没有这样的 i 存在，转到4）。Work:=Work+Allocationi Finishi:=true 返回到2）如果对所有 i，Finishi=true，则系统处于安全状态,110,资源请求算法,设Requesti 为进程Pi的请求向量如果Requesti=Needi，那么转到第2）步。否则，产生出错条件，因为进程已超过了其请求。如果Requesti=Avail

49、able，那么转到第3）步。否则，Pi等待，因为没有可用资源。假定系统可以分配给进程Pi 所请求的资源，并按如下方式修改状态：Available:=Available Requesti;Allocationi:=Allocationi+Requesti;Needi:=Needi Requesti;调用安全性算法确定新状态是否安全安全操作完成且进程Pi分配到其所需要的资源不安全进程Pi必须等待，并将数据结构恢复到原状态（即 3）的逆操作）,111,银行家算法举例,说明：5个进程P0P4，3种资源类型A、B、C，且实例个数分别为10、5、7 T0时刻状态如图所示,Allocation Max Av

50、ailable 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 3,112,问题：T0时刻是否为安全状态？若是，给出安全序列若在T0时刻进程P1请求资源（1，0，2），是否能实施分配？为什么？在（2）的基础上，若进程P4请求资源（3，3，0），是否能实施分配？为什么？在（3）的基础上，若进程P0请求资源（0，2，0），是否能实施分配？为什么？,113,转换（Need）,114,、T0时刻是安全的，存在安全序列,115,1 Request（1，0，2）Req