计算机操作系统原理 ch3 进程同步.ppt

《计算机操作系统原理 ch3 进程同步.ppt》由会员分享，可在线阅读，更多相关《计算机操作系统原理 ch3 进程同步.ppt（125页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第三章进程的同步与通信n进程互斥n信号量和、操作n进程同步n经典的进程同步问题n进程通信1进程互斥n基本概念n利用软件方法解决进程互斥问题n利用硬件方法解决进程互斥问题n用上锁开锁原语实现进程互斥2 基本概念n与时间有关的错误:一飞机订票系统，两个终端，运行T1、T2进程T1:T2:.Read(x);Read(x);if x=1 then if x=1 then x:=x-1;x:=x-1;write(x);write(x);.3并发环境下程序间的制约关系并发环境下程序间的制约关系4 n同同步步：对于进程操作的时间顺序所加的某种限制，如操作应在之前执行。n互互斥斥：同步的特例，多个操作决不能同

2、时执行，如：操作和操作不能在同时执行。（注意：理解不能同时执行的准确含义）5n临临界界资资源源(criticalresource)：一次仅允许一个进程访问的资源。如：进程共享一台打印机，若让它们交替使用则得到的结果肯定不是我们希望的。临界资源可能是硬件，也可能是软件：变量，数据，表格，队列等。并发进程对临界资源的访问必须作某种限制，否则就可能出与时间有关的错误与时间有关的错误，如：联网售票。6n临临界界区区(criticalsection)：临界段，在每个程序中，访问临界资源的那段程序。注注意意：临界区是对某一临界资源而言的，对于不同临界资源的临界区，它们之间不存在互斥。如有程序段A、B是关于

3、变量X的临界区，而C、D是关于变量Y的临界区，那么，A、B之间需要互斥执行，C、D之间也要互斥执行，而A与C、B与D之间不用互斥执行。7解决互斥的准则为了禁止两个进程同时进入临界区内,可以采用软件办法或系统提供的同步机构来协调它们的关系。但是，不论用什么办法都要遵循下述准则:1、当有若干进程欲进入它的临界区时,应在有有限限时时间间内内使使进进程程进进入入临临界界区区。换言之，它们不应相互阻塞而致使彼此都不能进入临界区2、每次至多有一个进程至多有一个进程处于临界区。3、进程在临界区内仅逗留有限的时间逗留有限的时间。8软件方法解决进程互斥n现在很少用软件方法解决互斥，但通过学习软件解法能使读者了解

4、到，在早期进程互斥问题的解决并不是一件很简单的事。假如有两个进程Pi和Pj，它们共享一个临界资源R。如何用软件方法使进程Pi和Pj能互斥地访问R。下面介绍四个算法。9算法1n设整型变量turn，用于指示被允许进入临界区的进程的编号，即若turn=i，表示进程Pi可进入。turn=j表示进程Pj可进入。10进程Pi:RepeatWhileturnidono_op;Criticalsectionturn:=j;OthercodeUntilfalse;11算法1的问题该算法可确保每次只允许一个进程进该算法可确保每次只允许一个进程进入临界区。但它强制两个进程轮流进入。入临界区。但它强制两个进程轮流进入

5、。如当如当Pi退出时将退出时将turn置为置为j，以便，以便Pj能进能进入，但入，但Pj暂不需要进入，而这时暂不需要进入，而这时Pi又需又需要进入时，它无法进入。这不能保证准要进入时，它无法进入。这不能保证准则则1。12算法2设varflag:array0.1ofboolean，若flagi=true，表示进程Pi正在临界区内。flagi=false表示进程Pi不在临界区内。若flagj=true，表示进程Pj正在临界区内。flagj=false表示进程Pj不在临界区内。13Pi进程：RepeatWhileflagjdono_op;flagi:=true;Criticalsectionflag

6、i:=false;OthercodeUntilfalse;14算法2的问题该算法可确保准则1。但又出现新问题。当pi和pj都未进入时，它们各自的访问标志都为false。如果pi和pj几乎同时要求进入，它们都发现对方的标志为false，于是都进入了。这不能保证准则2。15算法3n算法2的问题在于：当进程Pi观察到进程Pj的标志为false后，便将自己的标志由false改为true，而正是在这两步之间，可能发生进程切换。当Pj运行时，它会观察到Pi的标志为false，从而可以将自己的标志设为true，并进入临界区。若在临界区的执行过程中发生了进程切换，Pi可能获得处理机而进入临界区。16n在算法3

7、中，设varFlag:array0.1ofboolean，若flagi=true，表示进程Pi希望进入临界区内。若flagj=true，表示进程Pj希望进入临界区。17Pi进程：Repeatflagi:=true;Whileflagjdono_op;Criticalsectionflagi:=false;OthercodeUntilfalse;18算法3的问题该算法可确保准则2。但又出现新问题。它可能造成谁也不能进入。如，当pi和pj几乎同时都要进入，分别把自己的标志置为true，都立即检查对方的标志，发现对方为true.最终谁也不能进入。这不能保证准则1。19课本上的解法4Pi进程：Repe

8、atflagi:=true;Whileflagjdono_op;beginflagi:=false;flagi:=true;endCriticalsectionflagi:=false;OthercodeUntilfalse;20算法4（正确算法）n组合算法1、3，为每一进程设标志位flagi，当flagi=true时，表示进程pi要求进入，或正在临界区中执行。此外再设一个变量turn，用于指示允许进入的进程编号。21n进程为了进入先置flagi=true，并置turn为j，表示应轮到pj进入。接着再判断flagjandturn=j的条件是否满足。若不满足则可进入。或者说，当flagj=fal

9、se或者turn=i时，进程可以进入。前者表示pj未要求进入，后者表示仅允许pi进入。22算法4（正确算法）Repeatflagi:=true;turn:=j;While(flagjandturn=j)dono_op;Criticalsectionflagi:=false;OthercodeUntilfalse23软件解法的缺点1.忙等待忙等待2.2.实现过于复杂，需要较高的编程技实现过于复杂，需要较高的编程技巧巧24硬件方法解决进程互斥用软件解决很难，现代计算机大多提用软件解决很难，现代计算机大多提供一些硬件指令。供一些硬件指令。n利用Test-and-Set指令实现互斥n利用swap指令实

10、现进程互斥25Test-and-Set指令实现互斥1、Test-and-Set指令functionTS(varlock:boolean):boolean;beginiflock=0thenbeginlock:=1;TS:=true;endelseTS:=falseend;其中，有lock有两种状态：当lock=false时，表示该资源空闲；当lock=true时，表示该资源正在被使用。262、利用TS指令实现进程互斥为每个临界资源设置一个全局布尔变量lock，并赋初值false，表示资源空闲。repeatwhileTS(lock)doskip;criticalsectionlock:=fals

11、e;OthercodeUntilfalse;27swap指令实现进程互斥1、swap指令又称交换指令，X86中称为XCHG指令。Procedureswap(vara,b:boolean);Vartemp:boolean;BeginTemp:=a;A:=b;B:=temp;End;282、利用swap实现进程互斥为每一临界资源设置一个全局布尔变量lock，其初值为false，在每个进程中有局部布尔变量key。Repeatkey:=true;RepeatSwap(lock,key);Untilkey=false;Criticalsectionlock:=false;OthercodeUntilfa

12、lse;29用原语实现进程互斥锁即操作系统中的一标志位，表示资源可用，表示资源已被占用。用户程序不能对锁直接操作，必须通过操作系统提供的上锁和开锁原语来操作。通常锁用w表示，上锁开锁原语分别用lock(w)、unlock(w)来表示。30上锁和开锁原语上锁原语lock(w)可描述为：L：if(w=1)gotoLelsew=1；开锁原语unlock(w)可描述为：w=0；31用原语实现进程互斥32改进的上锁原语上述上锁原语中存在忙等待。上述上锁原语中存在忙等待。33改进的开锁原语34n1965年，由荷兰学者Dijkstra提出（所以P、V分别是荷兰语的test(proberen)和increme

13、nt(verhogen)）n一种卓有成效的进程同步机制n最初提出的是二元信号量（互斥）推广到一般信号量（多值）（同步）nP、V操作是原语信号量及P、V操作35信号量：semaphore是一个数据结构是一个数据结构定义如下：定义如下：struct semaphore int value;pointer_PCB queue;信号量说明：信号量说明：semaphore s;36P操作P(s)s.value=s.value-1;if(s.value 0)该进程状态置为等待状态 将该进程的PCB插入相应的等待队列末尾s.queue;37V操作V(s)s.value=s.value+1;if(s.valu

14、e 0表示有S个资源可用S=0表示无资源可用S=1&S2=1&Sn=1)/满足资源要求时的处理；满足资源要求时的处理；for(i=1;i=n;+i)-Si;else /某些资源不够时的处理；某些资源不够时的处理；调用进程进入第一个小于调用进程进入第一个小于1信号量的等待队列信号量的等待队列Sj.queue;阻塞调用进程阻塞调用进程;Swait原语47Ssignal(S1,S2,Sn)for(i=1;i=ti；即当资源数量低于ti时，便不予分配）占用值为di（表示资源的申请量，即Si=Si-di）对应的P、V原语格式为：nSwait(S1,t1,d1;.;Sn,tn,dn);nSsignal(S

15、1,d1;.;Sn,dn);50一般“信号量集”可以用于各种情况的资源分配和释放，几种特殊情况：nSwait(S,d,d)表示每次申请d个资源，当少于d个时，便不分配nSwait(S,1,1)表示互斥信号量nSwait(S,1,0)可作为一个可控开关（当S1时，允许多个进程进入特定区域；当S=0时，禁止任何进程进入该特定区域）n一般信号量集未必成对使用Swait和Ssignal：如：一起申请，但不一起释放51进程同步同步问题可分为两类：n保证一组合作进程按确定的次序执行n保证共享缓冲区的合作进程的同步。52合作进程的执行次序n若干个进程为了完成一个共同任务而并发执行，在这些进程中，有些进程之间

16、有次序的要求，有些进程之间没有次序的要求，为了描述方便，可以用一个图来表示进程集合的执行次序。如图53例如图，试用信号量实现这三个进程的同步。设有两个信号量SB、SC，初值均为Pa：Pb：Pc：P(SB);P(SC)V(SB);V(SC);54【思考题1】如图，试用信号量实现这三个进程的同步。如图，试用信号量实现这三个进程的同步。55解设有两个信号量S1、S2，初值均为P1：P2：P3：P(S1)V(S1);V(S2);P(S2)56【思考题2】如图，试用信号量实现这6个进程的同步57解设有5个信号量S2、S3、S4、S5、S6，初值均为P1：P2：P3：P(S2);P(S3)V(S2);V(

17、S3)；V(S4);V(S6);V(S5)P4：P5：P6：P(S4);P(S5);P(S6);P(S5);P(S6);V(S5)；V(S6);58【思考题3】司机进程：司机进程：while(1)while(1)启动车辆启动车辆正常驾驶正常驾驶到站停车到站停车售票员进程：售票员进程：while(1)while(1)关门关门售票售票开门开门用用P.VP.V操作解决司机与售票员的问题操作解决司机与售票员的问题59解n设有两个信号量S1，S2，初值均为0。司机进程：司机进程：while(1)while(1)P(S1)P(S1)启动车辆启动车辆正常驾驶正常驾驶 到站停车到站停车 V(S2)V(S2)售

18、票员进程：售票员进程：while(1)while(1)关门关门 V(S1)V(S1)售票售票 P(S2)P(S2)开门开门60共享缓冲区的进程的同步n设某计算进程和打印进程共用一个单缓冲区，进程负责不断地计算数据并送入缓冲区中，进程负责不断地从缓冲区中取出数据去打印。61分析通过分析可知，、必须遵守以下同步规则：n当进程把计算结果送入缓冲区时，IOP进程才能从缓冲区中取出结果去打印;n当IOP进程把缓冲区中的数据取出打印后，进程才能把下一个计算结果送入缓冲区62解n为此设有两个信号量Sa=0，Sb=1，Sa表示缓冲区中有无数据，Sb表示缓冲区中有无空位置。n两个进程的同步可以描述如下：63【思

19、考题】1.用P.V操作解决下图之同步问题提示：分别考虑对缓冲区S和T的同步，再合并考虑getcopyput64解n设置四个信号量Sin=1，Sout=0，Tin=1，Tout=0；get：while（1）P(Sin）;将数放入将数放入S;V(Sout);copy：while（1）P(Sout）;P(Tin）;将数从将数从S取出放入取出放入T;V(Tout);V(Sin);put：while（1）P(Tout）;将数从将数从T取走取走;V(Tin);65【思考题】n桌上有一空盘，最多允许存放一只水果。爸爸可向盘中放一个苹果或放一个桔子，儿子专等吃盘中的桔子，女儿专等吃苹果。试用P、V操作实现爸爸

20、、儿子、女儿三个并发进程的同步。提示：设置一个信号量表示可否向盘中放水果，一个信号量表示可否取桔子，一个信号量表示可否取苹果。66解设置三个信号量S,So,Sa，初值分别为1，0，0。分别表示可否向盘中放水果，可否取桔子，可否取苹果。67Father()while(1)p(S);将水果放入盘中;if(是桔子)v(So);elsev(Sa);Son()while(1)p(So)取桔子v(S);吃桔子;Daughter()while(1)p(Sa)取苹果v(S);吃苹果;68经典的进程同步问题n生产者/消费者问题n读者/写者问题n哲学家进餐问题69生产者/消费者问题n生产者消费者问题是一种同步问题

21、的抽象描述。计算机系统中的每个进程都可以消费（使用）或生产（释放）某类资源。这些资源可以是硬件资源，也可以是软件资源。n当某一进程使用某一资源时，可以看作是消费，称该进程为消费者。而当某一进程释放某一资源时，它就相当于生产者。70问题描述通过一个有界缓冲区可以把一群生产者p1,p2,pm，和一群消费者Q1,Q2,Qn联系起来。如图n只要缓冲区未满，生产者就可以把产品送入缓冲区;n只要缓冲区未空，消费者就可以从缓冲区中取走物品。71图72问题分析n为解决生产者消费者问题，应该设两个同步信号量，一个说明空缓冲区的数目，用S1表示，初值为有界缓冲区的大小N，另一个说明已用缓冲区的数目，用S2表示，初

22、值为。n由于在此问题中有M个生产者和N个消费者，它们在执行生产活动和消费活动中要对有界缓冲区进行操作。由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量mutex，其初值为。73问题的解Q：j=0;while(1)P(S2);P(mutex);从从Bufferj取产品取产品;j=(j+1)%n;V(mutex);V(S1);消费产品消费产品;P：i=0;while(1)生产产品;P(S1);P(mutex);往Bufferi放产品;i=(i+1)%n;V(mutex);V(S2);74采用AND信号量集解决生产者-消费者问题Q：j=0;while(1)Swait(s

23、2,mutex);从从Bufferj取产品取产品;j=(j+1)%n;Ssignal(s1,mutex);消费产品消费产品;P：i=0;while(1)生产产品生产产品;Swait(s1,mutex);往往Buffer i放产品放产品;i=(i+1)%n;Ssignal(s2,mutex);75【思考题】n如果生产者消费者问题中的缓冲区是无界的，又该如何解呢？76解设信号量S1,mutex初值均为0Q：j=0;while(1)P(S1);P(mutex);从从Bufferj取产品取产品;j=(j+1)%n;V(mutex);消费产品消费产品;P：i=0;while(1)生产产品;P(mutex

24、);往Bufferi放产品;i=(i+1)%n;V(mutex);V(S1);s1代表缓冲区是否为空;77【思考题】有一个仓库，可以存放A和B两种产品，但要求：（1）每次只能存入一种产品（A或B）（2）NA产品数量B产品数量M。其中，N和M是正整数。试用P、V操作描述产品A与B的入库过程。提示：设两个信号量Sa、SbSa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量78解设两个信号量Sa、Sb，初值分别为M-1，N-1Sa表示允许A产品比B产品多入库的数量Sb表示允许B产品比A产品多入库的数量设互斥信号量mutex，初值为1。79B产品入库进程：产品入库进程：j=0;

25、while(1)P(Sb);P(mutex);B产品入库产品入库 V(mutex);V(Sa);消费产品消费产品;A产品入库进程：产品入库进程：i=0;while(1)生产产品生产产品;P(Sa);P(mutex);A产品入库产品入库 V(mutex);V(Sb);80读者/写者问题 有两组并发进程:读者和写者,共享一组数据区 要求：允许多个读者同时执行读操作 不允许读者、写者同时操作 不允许多个写者同时操作81第一类：读者优先如果读者来：1 1）无读者、写者，新读者可以读）无读者、写者，新读者可以读2 2）有写者等，但有其它读者正在读，则新读者）有写者等，但有其它读者正在读，则新读者也可以读

26、也可以读3 3）有写者写，新读者等）有写者写，新读者等如果写者来：1 1）无读者，新写者可以写）无读者，新写者可以写2 2）有读者，新写者等待）有读者，新写者等待3 3）有其它写者，新写者等待）有其它写者，新写者等待82第一类读者写者问题的解法n设有两个信号量w=1，mutex=1n另设一个全局变量readcount=0nw用于读者和写者、写者和写者之间的互斥nreadcount表示正在读的读者数目nmutex用于对readcount这个临界资源的互斥访问83读者：while(1)P(mutex);readcount+;if(readcount=1)P(w);V(mutex);读P(mutex

27、);readcount-;if(readcount=0)V(w);V(mutex);写者：while(1)P(w);写V(w);84第一类读者写者问题的解法（一般信号量集）写者：while(1)Swait(wmutex,1,1;rcount,R,0);写；Ssignal(wmutex,1);读者：while(1)Swait(rcount,1,1;wmutex,1,0);读；Ssignal(rcount,1);n增加一个限制条件：同时读的“读者”最多R个nwmutexwmutex表示表示“允许写允许写”，初值是，初值是1 1nrcountrcount表示表示“允许读者数目允许读者数目”，初值为，

28、初值为R R85【思考题】写优先n修改以上读者写者问题的算法，使之对写者优先，即一旦有写者到达，后续的读者必须必须等待，无论是否有读者在读。n提示，增加一个信号量，用于在写者到达后封锁后续的读者86解增加一个信号量s，初值为1读者：while(1)P(s);P(mutex);readcount+;if(readcount=1)P(w);V(mutex);V(s);读P(mutex);readcount-;if(readcount=0)V(w);V(mutex);写者：while(1)P(s);P(w);写V(w);V(s);87哲学家就餐问题n有五个哲学家围坐在一圆桌旁，桌中央有一盘通心粉，每

29、人面前有一只空盘子，每两人之间放一只筷子n每个哲学家的行为是思考，感到饥饿，然后吃通心粉n为了吃通心粉，每个哲学家必须拿到两只筷子，并且每个人只能直接从自己的左边或右边去取筷子88设fork5为5个信号量，初值为均1Philosopheri：while(1)思考；P(forki);P(fork(i+1)%5)；进食；V(forki);V(fork(i+1)%5)；解89以上解法会出现死锁为防止死锁发生可采取的措施：n最多允许4个哲学家同时坐在桌子周围n仅当一个哲学家左右两边的筷子都可用时，才允许他拿筷子（）n给所有哲学家编号，奇数号的哲学家必须首先拿左边的筷子，偶数号的哲学家则反之 分析90采

30、用AND信号量集解决哲学家就餐问题设fork5为5个信号量，初值为均1Philosopheri：while(1)思考；Swait(forki,fork(i+1)%5)；进食；Ssignal(forki,fork(i+1)%5)；91进程通信n概念n进程通信类型 n消息缓冲通信的实现n信箱通信的实现92概念n所谓进程通信是指进程之间可直接以较高的效率传递较多数据的信息交换方式。nP.V操作实现的是进程之间的低级通讯，所以P.V为低级通讯原语。它只能传递简单的信号，不能传递交换大量信息。如果要在进程间传递大量信息则要用Send/Receive原语（高级通讯原语）93进程通信类型n共享存储器系统n消

31、息传递系统n管道通信(共享文件方式)941、共享存储器系统n基于共享数据结构的通信方式诸进程公用某些数据结构，进程通过它们交换信息。如生产者-消费者问题中的有界缓冲区。95n基于共享存储区的通信方式 高级通信，在存储器中划出一块共享存储区，进程在通信前，向系统申请共享存储区中的一个分区，并指定该分区的关键字，若系统已经给其它进程分配了这样的分区，则将该分区的描述符返回给申请者。接着，申请者把获得的共享存储分区连接到本进程上，此后可读写该分区。以上两种方式的同步互斥都要由进程自己负责。962、消息传递系统进程间的数据交换以消息为单位，程序员利用系统的通信原语实现通信。操作系统隐藏了通信的实现细节

32、，简化了通信程序编制的复杂性。因而得到广泛应用。97消息传递系统可分为：n直接通信：发送进程直接把消息发送给接收者，并将它挂在接收进程的消息缓冲队列上。接收进程从消息缓冲队列中取得消息。也称为消息缓冲通信98n间接通信：发送进程将消息发送到某种中间实体中（信箱），接收进程从中取得消息。也称信箱通信。在网络中称为电子邮件系统。99思考两种方式的主要区别？前者需要两进程都存在，后者不需要。1003、管道通信n所谓管道，是指用于连接一个读进程和一个写进程的文件，称pipe文件。向管道提供输入的进程（称写进程），以字符流的形式将大量数据送入管道，而接受管道输出的进程（读进程）可从管道中接收数据。该方式

33、首创于UNIX，它能传送大量数据，被广泛采用。发送进程发送进程接收进程接收进程字符流方式写入读出字符流方式写入读出先进先出顺序先进先出顺序101 消息缓冲通信的实现n在操作系统空间设置一组缓冲区。n当发送进程需要发送消息时，执行send系统调用，产生访管中断，进入操作系统。n操作系统为发送进程分配一个空缓冲区，并将所发送的消息从发送进程copy到缓冲区中，然后将该载有消息的缓冲区连接到接收进程的消息链链尾，如此就完成了发送过程。n发送进程返回到用户态继续执行。102n在以后某个时刻，当接收进程执行到receive接收原语时，也产生访管中断进入操作系统。n由操作系统将载有消息的缓冲区从消息链中取

34、出，并把消息内容copy到接收进程空间，之后收回缓冲区，如此就完成了消息的接收，接收进程返回到用户态继续进行103M:M:N:N:接收进程接收进程 R R发送进程发送进程 S S.104 type messageBuffer=record sender;/发送者ID size ;/消息长度 text ;/消息正文 next ;/消息队列指针 end 消息缓冲区结构105PCB中有关通信的数据项typePCB=recordmq;/消息队列首指针mutex;/消息队列互斥信号量sm;/消息队列资源信号量end106send（R,M）begin 在OS中分配M.size大小的缓冲区t;将M中的内容复

35、制到t;得到进程R的PCB的指针q；P(q.mutex);将t挂到队列q.mq队尾；V(q.mutex);V（q.sm);end 用P、V操作来实现Send原语107Receive(N）begin 得到本进程PCB的指针q；P(q.sm);P(q.mutex);从q.mq队首取下一个缓冲区t；V(q.mutex);将t的内容复制到N，并释放tend 用P、V操作来实现Receive原语108信箱通信的实现n信箱使用规则若发送信件时信箱已满，则发送进程被置为“等信箱”状态，直到信箱有空时才被唤醒若取信件时信箱中无信，则接收进程被置为“等信件”状态，直到有信件时才被唤醒109Send实现send（

36、MailBox，M）：把信件M送到指定的信箱MailBox中步骤：查找指定信箱MailBox；若信箱未满，则把信件M送入信箱且唤醒“等信件”者；若信箱已满置发送信件进程为“等信箱”状态；110Receive实现receive（MailBox，X）：从指定信箱MailBox中取出一封信，存放到指定的地址X中步骤：查找指定信箱MailBox；若信箱中有信，则取出一封信存于X中且唤醒“等信箱”者；若信箱中无信件则置接收信件进程“等信件”状态；111设fork5为5个信号量，初值均为1设信号量Mutex、W，初值为1设有全局变量Count初值为0W用于封锁第5个哲学家Mutex用于对临界资源Count

37、的访问无死锁哲学家就餐问题 解1112Philosopheri：while(1)思考；P(Mutex)Count+;if(Count=4)P(W)V(Mutex)P(forki);P(fork(i+1)%5)；进食；V(forki);V(fork(i+1)%5)；P(Mutex)Count-;if(Count=3)V(W)V(Mutex)113设fork5为5个信号量，初值为均1设信号量S，初值为4S用于封锁第5个哲学家无死锁哲学家就餐问题 解2114Philosopheri：while(1)思考；P(S)P(forki);P(fork(i+1)%5)；进食；V(forki);V(fork(i

38、+1)%5)；V(S)115设fork5为5个信号量，初值为均1无死锁哲学家就餐问题 解3116Philosopher1：while(1)思考；P(fork1);P(fork2)；进食；V(fork2);V(fork1)；Philosopher2：while(1)思考；思考；P(fork3);P(fork2)；进食；进食；V(fork2);V(fork3)；117习题进程A1、A2，。An1通过m个缓冲区向进程B1、B2、。Bn2不断发送消息。发送和接收工作遵循下列规则：（1）每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于消息长度（2）对每个消息，B1，B2，Bn2都须各接收一次

39、，读入各自的数据区内（3）m个缓冲区都满时，发送进程等待，没有可读消息时，接收进程等待。试用P、V操作组织正确的发送和接收工作。118n提示：每个缓冲区只要写一次但要读n2次，因此，可以看成n2组缓冲区，每个发送者要同时写n2个缓冲区，而每个接收者只要读它自己的缓冲区。nSinn2=mnSoutn2=0;119解先将问题简化：n设缓冲区的大小为1n有一个发送进程A1n有二个接收进程B1、B2n设有信号量Sin1、Sin2初值为1n设有信号量Sout1、Sout2初值为0120Bi：while(1)P(Souti);从缓冲区取数从缓冲区取数 V(Sini);A1:while(1)P(Sin1);

40、P(Sin2);将数据放入缓冲区V(Sout1);V(Sout2);121向目标前进一步n设缓冲区的大小为mn有一个发送进程A1n有二个接收进程B1、B2n设有信号量Sin1、Sin2初值为mn设有信号量Sout1、Sout2初值为0122Bi：while(1)P(Souti);P(mutex);从缓冲区取数从缓冲区取数 V(mutex);V(Sini);A1:while(1)P(Sin1);P(Sin2);P(mutex);将数据放入缓冲区V(mutex);V(Sout1);V(Sout2);123到达目标n设缓冲区的大小为mn有n1个发送进程A1.An1n有n2个接收进程B1Bn2n设有n2个信号量Sinn2初值均为mn设有n2个信号量Soutn2初值均为0124Bi：while(1)P(Souti);P(mutex);从缓冲区取数从缓冲区取数 V(mutex);V(Sini);Aj:while(1)for(i=1;i=n2;i+)P(Sini);P(mutex);将数据放入缓冲区V(mutex);for(i=1;i=n2;i+)V(Sout2);125