进程的同步与通信

1、进程的同步与通信操作系统习题课知识概要n一次仅允许一个进程使用的资源称为临界一次仅允许一个进程使用的资源称为临界资源；对临界资源进行访问的程序段成为资源；对临界资源进行访问的程序段成为临界区。临界区。n互斥互斥因共享某一公用资源而导不允许交叉执行因共享某一公用资源而导不允许交叉执行。n同步同步因直接制约关系，相互合作，互相等待。因直接制约关系，相互合作，互相等待。知识概要（续）nP(S)S=S-1if(S=0)继续运行继续运行else进程阻塞，进入进程阻塞，进入等待队列等待队列nV(S)S=S+1if(S0)继续执行继续执行else从等待队列中选择从等待队列中选择一个进程，变为就绪，一个进程，

2、变为就绪，原进程继续原进程继续知识概要（续2）n当一个过程包含公用和私用信号量时，当一个过程包含公用和私用信号量时，P、V原语的次序要非常小心。一般来讲，原语的次序要非常小心。一般来讲，V语语言是释放资源，可以以任意次序出现；但言是释放资源，可以以任意次序出现；但P语言如果次序混乱，会造成死锁。语言如果次序混乱，会造成死锁。习题1n若若P、V操作的信号量操作的信号量S初值为初值为2，当前值为，当前值为-1，则表示有（，则表示有（ ）个等待进程。个等待进程。A) 0 B) 1 C) 2 D) 3习题1答案n若若P、V操作的信号量操作的信号量S初值为初值为2，当前值为，当前值为-1，则表示有（，则

3、表示有（B）个等待进程。个等待进程。A) 0 B) 1 C) 2 D) 3习题2n有有n个进程都要使用某个共享文件，但系统个进程都要使用某个共享文件，但系统限制最多限制最多m个进程（个进程（nm1）同时读文件。）同时读文件。用用PV操作管理时信号量的值不可能变化为操作管理时信号量的值不可能变化为（ ）。）。A) 1 B) n C) m D) m-n习题2答案n有有n个进程都要使用某个共享文件，但系统个进程都要使用某个共享文件，但系统限制最多限制最多m个进程（个进程（nm1）同时读文件。）同时读文件。用用PV操作管理时信号量的值不可能变化为操作管理时信号量的值不可能变化为（B）。）。A) 1 B

4、) n C) m D) m-n习题3n以下活动属于互斥关系还是同步关系？以下活动属于互斥关系还是同步关系？若干同学去图书馆借书若干同学去图书馆借书两队举行篮球赛两队举行篮球赛流水线生产的各道工序流水线生产的各道工序商品生产和社会消费商品生产和社会消费习题3答案n以下活动属于互斥关系还是同步关系？以下活动属于互斥关系还是同步关系？若干同学去图书馆借书若干同学去图书馆借书n互斥互斥两队举行篮球赛两队举行篮球赛n互斥互斥流水线生产的各道工序流水线生产的各道工序n同步同步商品生产和社会消费商品生产和社会消费n同步同步 习题4n下图给出了四个进程合作完成某一任务的下图给出了四个进程合作完成某一任务的前趋

5、图，试说明这四个进程间的同步关系，前趋图，试说明这四个进程间的同步关系，并用并用P、V操作描述它。操作描述它。S1S2S3S4习题4解答nb2=0; b3=0; b4=0; /Sn是否开始是否开始S1() v(b2); v(b3); S2() p(b2); v(b4); S3() p(b3); v(b4); S4() p(b4); p(b4); S1S2S3S4习题5n桌上有一空盘，允许存放一只水果。爸爸桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果或桔子，儿子专吃桔子，可向盘中放苹果或桔子，儿子专吃桔子，女儿专吃苹果。规定当盘空时一次只能放女儿专吃苹果。规定当盘空时一次只能放一只水果供吃

6、者取用，请用一只水果供吃者取用，请用P、V原语实现原语实现三人并发进程的同步。三人并发进程的同步。分析：生产者分析：生产者消费者问题的变形，两类产品消费者问题的变形，两类产品和两类消费者。和两类消费者。习题5解答nS=1; Sa=0; So=0;/盘子，苹果，桔子盘子，苹果，桔子father()while(1)p(S);放水果；放水果；if (放桔子放桔子) v(So);else v(Sa);习题5解答(续)son()while(1)p(So);拿桔子拿桔子;v(S);吃桔子吃桔子;习题5解答(续2)daughter()while(1)p(Sa);拿苹果拿苹果;v(S);吃苹果；吃苹果；习题6

7、n多个进程共享一个文件，其中只读文件的多个进程共享一个文件，其中只读文件的称为读者，只写文件的称为写者。读者可称为读者，只写文件的称为写者。读者可以同时读，但写者只能独立写。请：以同时读，但写者只能独立写。请：1. 说明进程间的相互制约关系，应设置哪些信说明进程间的相互制约关系，应设置哪些信号量？号量？2. 用用P、V操作写出其同步算法。操作写出其同步算法。3. 修改上述的同步算法，使得它对写者优先，修改上述的同步算法，使得它对写者优先，即一旦有写者到达，后续的读者必须等待，而即一旦有写者到达，后续的读者必须等待，而无论是否有读者在读文件。无论是否有读者在读文件。习题6解答1n进程间的制约关系

8、有三类：进程间的制约关系有三类：读者之间允许同时读读者之间允许同时读读者与写者之间互斥读者与写者之间互斥写者之间互斥。写者之间互斥。n解决上述三类的同步解决上述三类的同步读互斥变量读互斥变量rmutex，使读者互斥地访问共享变量，使读者互斥地访问共享变量count写互斥变量写互斥变量wmutex，用于写者与其它的互斥，用于写者与其它的互斥共享变量共享变量count，用于记录当前读者的数目。，用于记录当前读者的数目。习题6解答2nrmutex=1; wmutex=1; count=0;write()while(1)p(wmutex);写文件写文件;v(wmutex);习题6解答2(续)reade

9、r()while(1)p(rmutex);if(count = 0) p(wmutex);/第一个读者第一个读者count+;v(rmutex);读文件读文件;p(rmutex);count-;if(count = 0) v(wmutex); /最后一个读者最后一个读者v(rmutex);习题6解答3n增加一个信号量增加一个信号量s，用于在写进程到达后封锁后续的读者。，用于在写进程到达后封锁后续的读者。rmutex=1; wmutex=1; count=0;writer()while(1)p(s);p(wmutex);写文件写文件;v(wmutex);v(s);习题6解答3 (续)reader

10、()while(1)p(s);p(rmutex);if(count = 0) p(wmutex);count+;v(rmutex);v(s);读文件读文件;p(rmutex);count-;if(count = 0) v(wmutex);v(rmutex);习题7n有一个仓库，可以存放有一个仓库，可以存放A和和B两种产品，但两种产品，但要求：要求：1. 每次只能存入一种产品（每次只能存入一种产品（A或或B）；）；2. -N A数量数量-B数量数量 M。 其中，其中，N和和M是正整数。试用是正整数。试用P、V操作描述产操作描述产品品A与与B的入库过程。的入库过程。习题7解答nmutex=1; s

11、a=M-1; sb=N-1; /允许允许sa个个A入库入库process()while(1)取一个产品；取一个产品；if(取的是取的是A产品产品)p(sa);p(mutex);产品入库产品入库;v(mutex);v(sb);习题7解答（续）elsep(sb);p(mutex);产品入库产品入库;v(mutex);v(pa);习题8n进程进程A1,A2,An1通过通过m个缓冲区向进程个缓冲区向进程B1,B2,Bn2不断发送消息。发送和接收不断发送消息。发送和接收工作遵循如下规则：工作遵循如下规则：每个发送进程一次发送一个消息，写入一个缓每个发送进程一次发送一个消息，写入一个缓冲区，缓冲区大小等于

12、消息长度；冲区，缓冲区大小等于消息长度；对每一个消息，对每一个消息，B1,B2,Bn2都须各接受一都须各接受一次，读入各自的数据区内；次，读入各自的数据区内；m个缓冲区都满时，发送进程等待；没有可个缓冲区都满时，发送进程等待；没有可度的消息时，接收进程等待。度的消息时，接收进程等待。试用试用P、V操作组织正确的发送和接收工作。操作组织正确的发送和接收工作。习题8分析n生产者生产者消费者的变形，可以把一组缓冲消费者的变形，可以把一组缓冲区看成区看成n2组缓冲区。每个发送者需要同时组缓冲区。每个发送者需要同时写写n2个缓冲区，接受者只需读自己对应的个缓冲区，接受者只需读自己对应的缓冲区。缓冲区。习

13、题8解答nmutex=1;for(I=0; I=n2-1; I+)emptyi = m;fulli = 0;习题8解答（续）send()for(I=0; In2-1; I+)p(emptyi);p(mutex);将消息放入缓冲区将消息放入缓冲区;v(mutex);for(I=0; I=n2-1; I+)v(fulli);习题8解答（续2）nreceive(I)p(fulli);p(mutex);将消息从缓冲区取出将消息从缓冲区取出;v(mutex);v(emptyi);习题9n在南开大学和天津大学之间有一条弯曲的在南开大学和天津大学之间有一条弯曲的小路，其中从小路，其中从S到到T一段路每次只允

14、许一辆一段路每次只允许一辆自行车通过，但其中有一个小的安全岛自行车通过，但其中有一个小的安全岛M（同时允许两辆自行车停留），可供两辆同时允许两辆自行车停留），可供两辆自行车已从两端进入自行车已从两端进入 小路情况下错车使用，小路情况下错车使用，如下图所示。试设计一个算法使来往的自如下图所示。试设计一个算法使来往的自行车均可顺利通过。行车均可顺利通过。MSTKL习题9解答nST=1;/是否允许从南开到天大是否允许从南开到天大TS=1;/是否允许从天大到南开是否允许从天大到南开K=1;/是否允许通过是否允许通过SKL=1;/是否允许通过是否允许通过TLM=2;/M上还允许停放的数量上还允许停放的数

15、量MST习题9解答（续）totian()p(ST);p(K);from S to K;p(M);enter m;V(K);p(L);from L to T;v(M);v(L);v(ST);MST习题9解答（续2）tonan()p(TS);p(L);from T to L;p(M);enter M;v(L);p(K);from K to S;v(M);v(K);v(TS);MST习题10n有一间酒吧有三个音乐爱好者队列，第一有一间酒吧有三个音乐爱好者队列，第一队的爱好者只有随身听，第二队只有音乐队的爱好者只有随身听，第二队只有音乐磁带，第三队只有电池。而要听音乐要三磁带，第三队只有电池。而要听音

16、乐要三者齐备。酒吧老板一次出售三者中的任意者齐备。酒吧老板一次出售三者中的任意两者。一名爱好者听完后，酒吧老板才能两者。一名爱好者听完后，酒吧老板才能再一次出售三者中的任意两者，第二名爱再一次出售三者中的任意两者，第二名爱好者集其三者继续听，以此类推。试用好者集其三者继续听，以此类推。试用P、V原语操作正确解决这一买卖。原语操作正确解决这一买卖。习题10解答na=0, b=1, c=1;随身听，磁带，电池随身听，磁带，电池nmutex1=1, mutex2=1, mutex3=1;(a,b), (a,c), (b,c)的互斥的互斥nbuy1=1, buy2=0, buy3=0, sale=0;爱好者和老板同步爱好者和老板同步习题10解答（续）nP1()while(1)p(buy1);p(mutex1);b=b-1;c=c-1;v(mutex1);听音乐听音乐;v(sale);习题10解答（续2）nP2()while(1)p(buy2);p(mutex2);a=a-1;c=c-1;v(mutex2);听音乐听音