第3章PV专题

1、本课程内容本课程内容 第第1 1章章 绪论绪论 第第2 2章章 操作系统用户界面操作系统用户界面 第第3 3章章 进程管理进程管理 第第4 4章章 处理机调度处理机调度 第第5 5章章 存储管理存储管理 第第8 8章章 文件系统文件系统 第第9 9章章 设备管理设备管理 例例1 1： 有一个阅览室，读者进入时必须先有一个阅览室，读者进入时必须先在一张登记表上进行登记，该表为每一座位列在一张登记表上进行登记，该表为每一座位列一表目，包括座号和读者姓名，读者离开时，一表目，包括座号和读者姓名，读者离开时，要删掉登记的信息，阅览室共有要删掉登记的信息，阅览室共有100100个座位，个座位，试问：试问

2、： （1 1）为描写读者动作，应编写几个程序，）为描写读者动作，应编写几个程序，应设置几个进程？进程与程序间关系如何？应设置几个进程？进程与程序间关系如何？ （2 2）试问）试问P P、V V操作写出这些进程间的同步操作写出这些进程间的同步算法。算法。 解法解法1 1： （1 1）因阅览室有）因阅览室有100100个座位可容纳个座位可容纳100100个读个读者同时阅读，基于这种并行性，因此可为每一者同时阅读，基于这种并行性，因此可为每一个读者设立一个进程。因为任何读者进出阅览个读者设立一个进程。因为任何读者进出阅览室都做相同的工作（登记阅读和取消登记）。室都做相同的工作（登记阅读和取消登记）。

3、所以对于所以对于100100个读者进程可以共同对应一个程个读者进程可以共同对应一个程序。此程序功能是入室时查表登记，入室阅读序。此程序功能是入室时查表登记，入室阅读和离室时查表取消登记。和离室时查表取消登记。 （2 2）设置信号量（）设置信号量（S S位）来表示空座位个位）来表示空座位个数，初值为数，初值为100100，用来控制进入阅览室的读者，用来控制进入阅览室的读者进程个数不超过进程个数不超过100100。 设置信号量（设置信号量（S S表）来表）来表示被共享的登记表这一临界资源。初值为表示被共享的登记表这一临界资源。初值为1 1，用来防止两个以上读者进程同时查表。用来防止两个以上读者进程

4、同时查表。 每个进程和其他进程之间的同步关系如下：每个进程和其他进程之间的同步关系如下： 解法解法2 2： （1 1）将读者入室查表登记和离室查表取消）将读者入室查表登记和离室查表取消登记各编一个程序，这样每个读者需设两个进登记各编一个程序，这样每个读者需设两个进程，分别执行入室和离室程序。程，分别执行入室和离室程序。 （2 2）原设信号量）原设信号量S S位为座位入室进程私有位为座位入室进程私有信号量，增设离室进程私有信号量信号量，增设离室进程私有信号量S S人人-入室入室读者数，初值为读者数，初值为0 0，这时进程间的同步关系如，这时进程间的同步关系如下：下： 例例2 2：桌上有一只盘子，

5、最多可以容纳：桌上有一只盘子，最多可以容纳M M只水果，每次只能放入或取出一个水果。爸爸只水果，每次只能放入或取出一个水果。爸爸专向盘子中放苹果（专向盘子中放苹果（AppleApple），妈妈专向盘子），妈妈专向盘子中放桔子（中放桔子（OrangeOrange），两个儿子专等吃盘子中），两个儿子专等吃盘子中的桔子，两个女儿专等吃盘子中的苹果。用的桔子，两个女儿专等吃盘子中的苹果。用P P、V V操作来实现爸爸、妈妈、儿子、女儿之间的操作来实现爸爸、妈妈、儿子、女儿之间的同步与互斥关系。同步与互斥关系。 解答：设信号量解答：设信号量placeplace、appleapple、 orangeora

6、nge和和mutexmutex分别表示盘子里能放水果的数目、盘分别表示盘子里能放水果的数目、盘子里已放入的苹果数目和盘子里已放入的桔子子里已放入的苹果数目和盘子里已放入的桔子的数目和对盘子的互斥访问，其初值分别为的数目和对盘子的互斥访问，其初值分别为m m、0 0、0 0和和1 1，其同步与互斥关系描述如下：，其同步与互斥关系描述如下： int place=m;int place=m; int apple=0; int apple=0; int orange=0; int orange=0; int mutex=1; int mutex=1; main()main() father(); fa

7、ther(); mother(); mother(); son(); son(); daughter(); daughter(); father()father() while(1)while(1) p(place); p(place); p(mutex) p(mutex) place apple; place apple; v(mutex); v(mutex); v(apple); v(apple); mother()mother() while(1)while(1) p(place); p(place); p(mutex) p(mutex) place orange; place oran

8、ge; v(mutex); v(mutex); v(orange); v(orange); son()son() while(1)while(1) p(apple); p(apple); p(mutex) p(mutex) take apple; take apple; v(mutex); v(mutex); v(place); v(place); daughter()daughter() while(1)while(1) p(orange); p(orange); p(mutex) p(mutex)take orange;take orange; v(mutex); v(mutex); v(

9、place); v(place); 例例3 3：问题：用：问题：用P P、V V操作解决下面问题操作解决下面问题司机进程：司机进程：REPEATREPEAT启动车辆启动车辆正常驾驶正常驾驶到站停车到站停车UNTIL UNTIL 售票员进程：售票员进程：REPEATREPEAT关门关门售票售票开门开门UNTIL UNTIL 同步要求：先关门，后开车；同步要求：先关门，后开车； 先停车，后开门先停车，后开门信号量：信号量：S_Door, S_Door, 初值为初值为00S_Stop; S_Stop; 初值为初值为00 乘务员进程乘务员进程: :Begin Begin Repeat Repeat 关

10、门；关门； V(S_Door);V(S_Door); 售票；售票； P(S_Stop);P(S_Stop); 开门；开门； Until false;Until false;EndEnd 司机进程：司机进程：BeginBegin Repeat Repeat P(S_Door); P(S_Door); 启动；启动； 驾驶；驾驶； 停车；停车； V(S_Stop);V(S_Stop); Until false; Until false;EndEnd 例例4 4：三个进程：三个进程PAPA、PBPB和和PCPC协作解决文件协作解决文件打印问题：打印问题：PAPA将文件记录从磁盘读入主存的缓将文件记录从

11、磁盘读入主存的缓冲区冲区1 1，每执行一次读一个记录；，每执行一次读一个记录；PBPB将缓冲区将缓冲区1 1的内容读出并读入到缓冲区的内容读出并读入到缓冲区2 2，每执行一次读，每执行一次读出并读入一个记录；出并读入一个记录；PCPC将缓冲区将缓冲区2 2的内容打印的内容打印出来，每执行一次打印一个记录。缓冲区出来，每执行一次打印一个记录。缓冲区1 1的的大小和大小和m m个记录大小一样，缓冲区个记录大小一样，缓冲区2 2的大小和的大小和n n个记录大小一样。请用个记录大小一样。请用P P、V V操作来保证文件的操作来保证文件的正确打印。正确打印。 解答：设置四个信号量解答：设置四个信号量em

12、pty1empty1、empty2empty2、full1full1、full2full2、mutex1mutex1和和mutex2mutex2，信号量，信号量empty1empty1和和empty2empty2分别表示缓冲池分别表示缓冲池1 1和缓冲池和缓冲池2 2是是否为空，其初值为否为空，其初值为m m和和n n；信号量；信号量full1full1和和full2full2分别表示缓冲池分别表示缓冲池1 1和缓冲池和缓冲池2 2是否有记录供读出，是否有记录供读出，其初值均为其初值均为0 0；信号量；信号量mutex1mutex1和和mutex2mutex2分别表分别表示对缓冲池示对缓冲池1

13、 1和缓冲池和缓冲池2 2的访问互斥，其初值为的访问互斥，其初值为1 1。其进程间的同步与互斥关系如下：。其进程间的同步与互斥关系如下：int empty1=m;int empty1=m;int empty2=n;int empty2=n;int full1=0;int full1=0;int full2=0;int full2=0;int mutex1=1;int mutex1=1;int mutex2=1;int mutex2=1;main()main() PA(); PA(); PB(); PB(); PC(); PC(); PA( )PA( )while(1)while(1) 从磁盘读

14、出一个文件记录；从磁盘读出一个文件记录；p(empty1);p(empty1);p(mutex1);p(mutex1); 将一个文件记录读入缓冲池将一个文件记录读入缓冲池1 1； v(mutex1);v(mutex1); v(full1); v(full1); PB( )PB( )while(1)while(1) p(full1); p(full1);p(mutex1);p(mutex1); 从缓冲区从缓冲区1 1中读出一个文件记录；中读出一个文件记录； v(mutex1);v(mutex1); v(empty1); v(empty1); p(empty2); p(empty2); p(mut

15、ex2); p(mutex2); 将一个记录读入缓冲区将一个记录读入缓冲区2 2； v(mutex2)v(mutex2)； v(full2);v(full2); PC( )PC( )while(1)while(1) p(full2); p(full2);p(mutex2);p(mutex2);从缓冲池从缓冲池2 2读出一个文件记录打印；读出一个文件记录打印； v(mutex2);v(mutex2); v(empty2); v(empty2); 例例5 5：有三个进程：有三个进程A A、B B、C C，其中，其中A A与与B B构成构成一对生产者和消费者，共享一个由一对生产者和消费者，共享一个由

16、n n个缓冲区个缓冲区块组成的缓冲池块组成的缓冲池1 1；B B与与C C也构成一对生产者与也构成一对生产者与消费者，共享另一个由消费者，共享另一个由m m个缓冲块组成的缓冲个缓冲块组成的缓冲池池2 2。用。用P P、V V操作描述它们之间的同步关系。操作描述它们之间的同步关系。解答：解答： 设置四个信号量设置四个信号量empty1empty1、empty2empty2、full1full1和和full2full2，其同步关系描述如下：，其同步关系描述如下：int empty1=n; /int empty1=n; /* *表示缓冲池表示缓冲池1 1中的空缓冲中的空缓冲区数区数* */ /int

17、 empty2=m; /int empty2=m; /* *表示缓冲池表示缓冲池2 2中的空缓冲中的空缓冲区数区数* */ /int full1=0; /int full1=0; /* * 表示缓冲池表示缓冲池1 1中装满产品中装满产品的缓冲区数的缓冲区数* */ /int full2=0; /int full2=0; /* * 表示缓冲池表示缓冲池2 2中装满产品中装满产品的缓冲区数的缓冲区数* */ /main( )main( ) cobegin cobegin PA( ); PA( ); PB( ); PB( ); PC( ); PC( ); Coend Coend PA( ) PA(

18、) while(1) while(1) 生产一件产品；生产一件产品； P(empty1);P(empty1); 将一件产品放入缓冲池将一件产品放入缓冲池1 1； V(full1);V(full1); PB( )PB( ) while(1) while(1) P(full1); P(full1); 从缓冲池从缓冲池1 1中取出一件产品；中取出一件产品； V(empty1);V(empty1); P(empty2); P(empty2); 将一件产品放入缓冲池将一件产品放入缓冲池2 2； V(full2);V(full2); PC( ) PC( ) while(1) while(1) P(full

19、2); P(full2); 从缓冲池从缓冲池2 2中取出一件产品；中取出一件产品； V(empty2);V(empty2); 例例6 6：两个山崖间有一根铁索，山崖两边：两个山崖间有一根铁索，山崖两边各有一群猴子，任何时候同时只能有一个方向各有一群猴子，任何时候同时只能有一个方向的猴子通过铁索。使用的猴子通过铁索。使用P P、V V操作写出山崖两边操作写出山崖两边的猴子过铁索的算法。的猴子过铁索的算法。 解答：一个山上的猴子就是一群读者，解答：一个山上的猴子就是一群读者，第二个山上的猴子为另一群读者，两群读者第二个山上的猴子为另一群读者，两群读者互斥使用铁索。设信号量互斥使用铁索。设信号量wa

20、ymutexwaymutex表示山两边表示山两边的猴子对铁索的互斥共享，初值为的猴子对铁索的互斥共享，初值为1 1；设；设m1countm1count和和m2countm2count表示对两边猴子的记数，其表示对两边猴子的记数，其初值为初值为0 0；设；设m1mutex m1mutex 和和m2mutexm2mutex表示两群猴子表示两群猴子中各猴子互斥访问记数变量的信号量，初值都中各猴子互斥访问记数变量的信号量，初值都为为1 1，其同步与互斥的算法如下：，其同步与互斥的算法如下： int waymutex=1; int waymutex=1; int m1mutex=1, m2mutex=1

21、; int m1mutex=1, m2mutex=1; int m1count=0, m2count=0; int m1count=0, m2count=0; main( )main( ) cobegin cobegin monkeygroup1( ); monkeygroup1( ); monkeygroup2( ); monkeygroup2( ); coend coend monkeygroup1( )monkeygroup1( ) while(1) while(1) P(m1mutex); P(m1mutex); if m1count=0 then P(waymutex); if m1

22、count=0 then P(waymutex); m1count=m1count+1; m1count=m1count+1; V(m1mutex) V(m1mutex) P(m1mutex); P(m1mutex); m1count=m1count-1; m1count=m1count-1; if m1count=0 then V(waymutex); if m1count=0 then V(waymutex); V(m1mutex) V(m1mutex) monkeygroup2( )monkeygroup2( ) while(1) while(1) P(m2mutex); P(m2mut

23、ex); if m2count=0 then P(waymutex); if m2count=0 then P(waymutex); m2count=m2count+1; m2count=m2count+1; V(m2mutex) V(m2mutex) P(m2mutex); P(m2mutex); m2count=m2count-1; m2count=m2count-1; if m2count=0 then V(waymutex); if m2count=0 then V(waymutex); V(m2mutex) V(m2mutex) 思考题思考题 :东东西西过隧道的问题过隧道的问题思想：

24、思想： 每边的第一个进程抢互斥信号灯，后边的进每边的第一个进程抢互斥信号灯，后边的进程跟进程跟进; ; 每边的最后一个进程释放互斥信号灯。每边的最后一个进程释放互斥信号灯。问题：要计数，而且计数时应互斥；问题：要计数，而且计数时应互斥； SBmutexBASA程序描述程序描述 :main( ) mutex=1 /*互斥信号灯互斥信号灯 SB=1； /*B边计数互斥信号灯边计数互斥信号灯 SA=1；/*A边计数互斥信号灯边计数互斥信号灯 countA= 0； countB= 0； cobegin while (A边还有人边还有人) A进程进程( ) ； while (B边还有人边还有人) B进程

25、进程( ) ； coend A边进程边进程( ) 到隧道口到隧道口 P(SA) countA= countA+ 1 if (countA=1) P(mutex) V(SA) 进隧道进隧道 出隧道出隧道 P(SA) countA= countA1 if (countA=0) V(mutex) V(SA) B边进程边进程( ) 到隧道口到隧道口 P(SB) countB= countB+ 1 if (countB=1) P(mutex) V(SB) 进隧道进隧道 出隧道出隧道 P(SB) countB= countB1 if (countB=0) V(mutex) V(SB) 更进一步的考虑：更进

26、一步的考虑： 当令一边有人等当令一边有人等待时，能否规定每边待时，能否规定每边能跟进的最多人能跟进的最多人数？数？ 例例7 7：考虑过河的例子，用：考虑过河的例子，用P P、V V操作设计操作设计一个算法要求该算法能确保若干人从同一岸同一个算法要求该算法能确保若干人从同一岸同时过河而不死锁。时过河而不死锁。解答如下：解答如下： int wait2=1,0;int wait2=1,0; int s=1,mutex2=1,1,rc2=0,0; int s=1,mutex2=1,1,rc2=0,0;p(s); /p(s); /与河对面争夺过河权与河对面争夺过河权p(waiti); /p(waiti)

27、; /互斥过桥互斥过桥p(mutexi);p(mutexi);rci+;rci+;if(rci=1) p(wait(i+1) mod 2); /if(rci=1) p(wait(i+1) mod 2); /如如果是第一个则控制对方过河权果是第一个则控制对方过河权v(mutexi);v(mutexi);pass river;pass river;v(waiti);v(waiti);v(s);v(s);p(mutexi);p(mutexi);rci-;rci-;if(rci=0) v(wait(i+1) mod 2); /if(rci=0) v(wait(i+1) mod 2); /如如果是最后一

28、个则释放对方过河权果是最后一个则释放对方过河权v(mutexi)v(mutexi) 例例9 9：进程：进程A A通过一个缓冲区不断地向进程通过一个缓冲区不断地向进程B B、C C、D D发送信息，发送信息，A A每向缓冲区送入一个信息每向缓冲区送入一个信息后，必须等进程后，必须等进程B B、C C、D D都取走后才可以发送都取走后才可以发送下一个信息，下一个信息，B B、C C、D D对对A A送入的每一信息各取送入的每一信息各取一次，试用一次，试用P P、V V操作实现它们之间的正确通讯。操作实现它们之间的正确通讯。 解答：解答： 解答：设置信号量解答：设置信号量int Rab=1int R

29、ab=1； / /* *表示进程表示进程B B对进程对进程A A送入的信送入的信息取了一次息取了一次* */ /int Rac=1int Rac=1； / /* *表示进程表示进程C C对进程对进程A A送入的信送入的信息取了一次息取了一次* */ /int Rad=1int Rad=1；/ /* *表示进程表示进程D D对进程对进程A A送入的信息送入的信息取了一次取了一次* */ / int Sab=0 int Sab=0；/ /* *表示进程表示进程A A向进程向进程B B发送一个发送一个信息信息* */ /int Sac=0int Sac=0；/ /* *表示进程表示进程A A向进程向

30、进程C C发送一个信发送一个信息息* */ / int Sad=0 int Sad=0；/ /* *表示进程表示进程A A向进程向进程D D发送一个发送一个信息信息* */ /Main()Main() cobegin cobegin PA( ); PA( ); PB( ); PB( ); PC( ); PC( ); PD( ); PD( ); coend coend PA( )PA( )While(1)While(1) 生产消息；生产消息； P(Rab);P(Rab); P(Rac); P(Rac); P(Rad); P(Rad); 向缓冲区送消息；向缓冲区送消息； V(Sab);V(Sab)

31、; V(Sac); V(Sac); V(Sad) V(Sad) PB( )PB( ) while(1) while(1) P(Sab); P(Sab); 从缓冲区取消息；从缓冲区取消息； V(Rab)V(Rab) PC( ) PC( ) while(1) while(1) P(Sac); P(Sac); 从缓冲区取消息；从缓冲区取消息； V(Rac)V(Rac) PD( )PD( ) while(1) while(1) P(Sad); P(Sad); 从缓冲区取消息；从缓冲区取消息； V(Rad)V(Rad) 例例8 8：有：有n+1n+1个进程个进程P1,P2,P1,P2,PnPn和和Q Q

32、： （1 1）P1,P2,P1,P2,PnPn通过同一个缓冲区各自不通过同一个缓冲区各自不断地向断地向Q Q发送消息，发送消息，Q Q不断地取消息，它必须取不断地取消息，它必须取走发来的每一个消息。刚开始时缓冲区为空。走发来的每一个消息。刚开始时缓冲区为空。试用试用P P、V V操作正确实现之。操作正确实现之。 （2 2）若缓冲区个数增至）若缓冲区个数增至k k个，试用个，试用P P、V V操操作实现正确的通讯。作实现正确的通讯。解答：解答：n+1n+1个进程个进程P1, P2, .,Pn P1, P2, .,Pn 和和 Q Q ，一个缓冲区，一个缓冲区设置信号量设置信号量int S1=1;

33、/int S1=1; /* *空缓冲区的个数空缓冲区的个数* */ /int S2=0; /int S2=0; /* *缓冲区中消息的个数缓冲区中消息的个数* */ /main()main() cobegin cobegin P1( ); P1( ); P2( ); P2( ); Pn( ); Pn( ); Q( ); Q( ); Coend Coend Pi ( )( i=1,.,n)Pi ( )( i=1,.,n) while(1) while(1) 生产消息；生产消息； P(S1);P(S1); 向缓冲区送消息；向缓冲区送消息； V(S2)V(S2) Q( )Q( ) while (1)

34、 while (1) P(S2); P(S2); 从缓冲区取消息；从缓冲区取消息； V(S1)V(S1)； 处理消息；处理消息； (2)(2) k k个缓冲区个缓冲区int S1=k; /int S1=k; /* *空缓冲区的个数空缓冲区的个数* */ /int S2=0; /int S2=0; /* *缓冲区中消息的个数缓冲区中消息的个数* */ /int mutex=1; /int mutex=1; /* *互斥访问缓冲区互斥访问缓冲区* */ /int x=0int x=0； / /* *消息送入缓冲区下标记数消息送入缓冲区下标记数* */ /int xx=0; /int xx=0; /

35、* *消息取出缓冲区下标记数消息取出缓冲区下标记数* */ /main()main() cobegin cobegin P1( ); P1( ); P2( ); P2( ); Pn( ); Pn( ); Q( ); Q( ); Coend Coend PiPi（ ） ( i=1,.,n):( i=1,.,n): while(1) while(1) 生产消息；生产消息； P(S1);P(S1); P(mutex); P(mutex); 向向BUFFERxBUFFERx中送消息；中送消息； x:=(x+1) mod k;x:=(x+1) mod k; V(mutex); V(mutex); V(S

36、2) V(S2) Q( ) Q( ) while(1) while(1) P(S2); P(S2); P(mutex); P(mutex); 从从BUFFERxxBUFFERxx取消息；取消息； xx=(xx+1) mod k;xx=(xx+1) mod k; V(mutex); V(mutex); V(S1) V(S1) （3 3）进一步加深：进一步加深：P1,P2,.,PnP1,P2,.,Pn往一个往一个缓冲区中送，缓冲区中送，Q1,Q2,.,QnQ1,Q2,.,Qn从该缓冲区取从该缓冲区取 解答：解答： int s1=1; /int s1=1; /* *表示空缓冲区的个数表示空缓冲区的个

37、数* */ /int s2=0; /int s2=0; /* *表示缓冲区中消息的个数表示缓冲区中消息的个数* */ /main( )main( ) cobegin cobegin P1( ); P1( ); P2( ); P2( ); Pn( ); Pn( ); coend coend Pi( )Pi( )（i=1,2,.,ni=1,2,.,n） while(1) while(1) P(s1) P(s1)； 往缓冲区送；往缓冲区送； V(s2)V(s2)； Qi( )Qi( )（i=1,2,.,ni=1,2,.,n） while(1) while(1) P(s2) P(s2)； 从缓冲区取；

38、从缓冲区取； V(s1)V(s1)； 例例1111：设在书中所描述的生产者消费者问：设在书中所描述的生产者消费者问题中，其缓冲部分为题中，其缓冲部分为m m个长度相等的有界缓冲个长度相等的有界缓冲区组成，且每次传输数据长度等于有界缓冲区区组成，且每次传输数据长度等于有界缓冲区长度以及生产者和消费者可对缓冲区同时操作。长度以及生产者和消费者可对缓冲区同时操作。重新描述发送过程重新描述发送过程 depositdeposit（datadata）和接收过）和接收过程程 removeremove（datadata）。）。 解答：设第解答：设第1 1块缓冲区的公用信号量为块缓冲区的公用信号量为mutexm

39、utexI I，保证生产者进程和消费者进程对，保证生产者进程和消费者进程对同一块缓冲区操作的互斥，初值为同一块缓冲区操作的互斥，初值为1 1。设信号。设信号量量availavail为生产者进程的私用信号量，初值为为生产者进程的私用信号量，初值为m m。信号量信号量fullfull为消费者进程的私用信号量，初值为消费者进程的私用信号量，初值为为0 0。从而有：。从而有： deposit (data ) deposit (data ) Begin Begin P (avail ) P (avail ) 选择一个空缓冲区选择一个空缓冲区i i P (mutext I) P (mutext I) 送数

40、据入缓冲区送数据入缓冲区i i V (full ) V (full ) V (mutext I) V (mutext I) End End Remove (data ) Remove (data ) Begin Begin P (fu1l ) P (fu1l ) 选择一个满缓冲区选择一个满缓冲区I I P (mutext I) P (mutext I) 取缓冲区取缓冲区i i中的数据中的数据 V (avai1) V (avai1) V (mutext I) V (mutext I) End End 例例1212：试：试： （1 1）描述一个保证不会出现两个邻座同时）描述一个保证不会出现两个邻座

41、同时要求吃饭的通信算法。要求吃饭的通信算法。 （2 2）描述一个既没有两邻座同时吃饭，又）描述一个既没有两邻座同时吃饭，又没有人饿死（永远拿不到筷子）的算法。在什没有人饿死（永远拿不到筷子）的算法。在什么情况下，么情况下，5 5个哲学家全部吃不上饭？个哲学家全部吃不上饭？ 解答：解答：（1 1）设信号量）设信号量C C0 0c c4 4，初始值均为，初始值均为1 1，分别表示分别表示I I号筷子被拿（号筷子被拿（I I0 0，1 1，2 2，3 3，4 4），）， P Philosopherhilosopher（I I）：）：/第第I I个哲学家要吃饭个哲学家要吃饭 Begin Begin P

42、 (cI); P (cI); P(c P(c（I+lI+l）mod 5) ; mod 5) ; Eat I Eat I V(c V(c（I+lI+l）mod 5) ; mod 5) ; V (cI ) V (cI ) End; End; / /该过程能保证该过程能保证两邻座不同时吃饭，两邻座不同时吃饭，但会出现但会出现5 5个哲学家一个哲学家一人拿一只筷子，谁也人拿一只筷子，谁也吃不上饭的死锁情况。吃不上饭的死锁情况。 （2 2）解决的思路如下：让奇数号的哲学家）解决的思路如下：让奇数号的哲学家先取右手边的筷子，让偶数号的哲学家先取左先取右手边的筷子，让偶数号的哲学家先取左手边的筷子。手边的筷

43、子。 这样，任何一个哲学家拿到一只筷子以后，这样，任何一个哲学家拿到一只筷子以后，就已经阻止了他邻座的一个哲学家吃饭的企图，就已经阻止了他邻座的一个哲学家吃饭的企图，除非某个哲学家一直吃下去，否则不会有人会除非某个哲学家一直吃下去，否则不会有人会饿死。饿死。 P Philosopherhilosopher (I ): (I ): Begin Begin If I mod 2 = = 0 then If I mod 2 = = 0 then P(cI)P(cI)；P(c(I+l) mod 5 ) P(c(I+l) mod 5 ) Eat Eat ； V(cI)V(cI)；V(c(I+1) mod

44、 5) V(c(I+1) mod 5) else else P (c(I+l) mod 5 ) P (c(I+l) mod 5 ) ；P(cI) P(cI) Eat Eat V (c(I+l) mod 5 ) V (c(I+l) mod 5 ) ；V(cI) V(cI) End End 例例1414：问题：用：问题：用P P、V V操作解决下图之同步问题操作解决下图之同步问题 （同步）信号量：（同步）信号量： 实际上也起到互斥作用实际上也起到互斥作用 S_Empty, T_EmptyS_Empty, T_Empty， 初值为初值为11S_Full, T_Full; S_Full, T_Full

45、; 初值为初值为0 0 GetGet（）：（）：BeginBegin Repeat Repeat P(S_Empty) P(S_Empty) T_get_S(); T_get_S(); V(S_Full); V(S_Full); Until false; Until false;EndEnd CopyCopy（）：（）：BeginBegin Repeat Repeat P(S_Full); P(S_Full); P(T_Empty); P(T_Empty); S_copy_T(); S_copy_T(); V(T_Full); V(T_Full); V(S_Empty); V(S_Empty)

46、; Until false; Until false;EndEndPutPut（）：（）：Begin Begin Repeat Repeat P(T_Full); P(T_Full); T_put_G(); T_put_G(); V(T_Empty); V(T_Empty); Until false; Until false;End End 例例1010：main( )main( ) int sa=0 int sa=0；* *表示表示bufbuf中有无信息中有无信息 * * int sb=1int sb=1； * *表示表示bufbuf中有无空位置中有无空位置* * int ta=0int t

47、a=0； * *表示表示bufbuf中有无信息中有无信息 * * int tb=1int tb=1； * *表示表示bufbuf中有无空位置中有无空位置* *cobegincobegin get( ) get( )； copy( )copy( )； put( )put( )； coendcoend get( ) get( ) while( while(还要计算还要计算) ) 产生一个结果数据；产生一个结果数据； p(sb)p(sb)； 将数送到缓冲区将数送到缓冲区s s中；中； v(sa)v(sa)； copy( ) copy( ) while( while(还要复制还要复制) ) p(sa)

48、 p(sa)； p(tb)p(tb)； 将缓冲区将缓冲区s s中的数复制到中的数复制到t t中；中； v(ta)v(ta)； v(sb)v(sb)； put( )put( ) while( while(还要输出还要输出) ) p(ta)p(ta)； 从缓冲区从缓冲区t t中取数据；中取数据； v(tb)v(tb)； 在打印机上输出；在打印机上输出； 例例1111： 一类同步问题的解法一类同步问题的解法 合作进程的执行次序合作进程的执行次序 若执行次序是已知的，则可用进程流图来若执行次序是已知的，则可用进程流图来表示。表示。 进程流图可用来描述进程集合的执行时间进程流图可用来描述进程集合的执行时

49、间轨迹，图中的连接点表示进程开始执行和结束轨迹，图中的连接点表示进程开始执行和结束的约束的约束. . 例例A A：设：设 p1 p1 、p2 p2 、p3 p3 、p p 、 p p 为为一组合作进程，其进程流图如下图所示。用信一组合作进程，其进程流图如下图所示。用信号灯的号灯的p p、v v操作实现这五个进程的同步。操作实现这五个进程的同步。 分析：若一进程必须先于其他的进程完成，分析：若一进程必须先于其他的进程完成，则可将该进程的的完成作为释放的资源。因此：则可将该进程的的完成作为释放的资源。因此：p1 : p1 : 不等资源，释放二个资源不等资源，释放二个资源P2: P2: 不等资源，释

50、放一个资源不等资源，释放一个资源p3 : p3 : 等一个资源，释放一个资源等一个资源，释放一个资源p4 : p4 : 等二个资源，不释放资源等二个资源，不释放资源p5 : p5 : 等一个资源，不释放资源等一个资源，不释放资源 实现：实现： 设设3 3个同步信号灯个同步信号灯s1 s1 、 s2 s2 、 s3 s3 ，分别，分别表示：表示：进程进程 p1p1、 p p、 p p是否完成。是否完成。 程序描述程序描述 main( ) main( ) int s1=0 int s1=0；* *表示表示p1p1进程是否完成进程是否完成* * int s2=0int s2=0；* *表示表示p2p

51、2进程是否完成进程是否完成* * int s3=0int s3=0；* *表示表示p p进程是否完成进程是否完成* * cobegincobegin p p( )( )； p p( )( )； p p( )( )； p p( )( )； p p( )( )； coend coend p p( )( ) v(s v(s ) )； v(sv(s ) )； P2( ) P2( ) . . . . . . v(s2 ) v(s2 )； p3( )p3( ) p(s p(s) )； . . . . . . v(s3 ) v(s3 )； p4( )p4( ) p(s2) p(s2)； p(s3 )p(s3

52、 )； . . . . . . P5( )P5( ) p(s1 ) p(s1 )； . . . . . . 例例17.17.设有六个进程设有六个进程P1,P2,P1,P2,P6,P6,它们有如它们有如图二所示的并发关系。试用图二所示的并发关系。试用P P、V V操作实现这些操作实现这些进程间的同步。进程间的同步。 例例1818：我们说程序的并发执行将导致最终：我们说程序的并发执行将导致最终结果失去封闭性。这话对所有的程序都成立吗？结果失去封闭性。这话对所有的程序都成立吗？试举例说明。试举例说明。 答：并非所有程序均成立。答：并非所有程序均成立。 如：如： Begin Begin local x

53、 local x ； X=10 X=10 ； printprint（x x）；）； End End 上述程序中上述程序中X X是内部变量，不可能被外部是内部变量，不可能被外部程序访问，因此这段程序的运行不会受外部环程序访问，因此这段程序的运行不会受外部环境影响。境影响。 例例1919：理发师问题：理发师问题 理发店里有一位理发师理发店里有一位理发师, ,一把理发椅和一把理发椅和N N把供把供等候理发的顾客坐的椅子等候理发的顾客坐的椅子. .如果没有顾客如果没有顾客, ,则理则理发师便在理发椅上睡觉发师便在理发椅上睡觉. .当一个顾客到来时当一个顾客到来时, ,他他必须先唤醒理发师必须先唤醒理发师. .如果顾客到来时理发师正如果顾客到来时理发师正在理发，