进程的同步与通信教学课件

《进程的同步与通信教学课件》由会员分享，可在线阅读，更多相关《进程的同步与通信教学课件（41页珍藏版）》请在装配图网上搜索。

1、第3章进程的同步与通信3.1 基本点、重点和难点在多道程序系统中，程序的执行失去了封闭性和再现性，程序的运行具有不确定性，这是我们所不希望看到的。如果多道程序系统中程序的执行不加控制，程序的每次执行就可能得到不同的结果。如何使多道程序的执行的结果具有再现性和确定性？这就需要通过进程间的同步和互斥来实现，将原来无序的、不确定的程序的执行转换为有序的、确定的执行。解决同步和互斥问题最常用的方法就是信号量的方法，通过在程序中使用P、v 操作达到同步和互斥的目的。在使用信号量和P、v 操作时，很多学生觉得无从下手，感到困惑。这主要是因为他们对进程的本质理解还不够深入、对多道程序设计的原理还不够清楚、对

2、信号量的含义还不够明白造成的。但这部分内容又是各类考试的必考点。本章有很多经典问题，其解题的方法和答案在很多资料上都可以见到。但这些解题的结果是专家们长期精炼而成的，初学者在开始时不可能得到这样的结果。对于初学者而言,迫切想知道的已不单是解题的结果，而是问题解决的思考和分析过程。为此，本章中对一些问题的解答给出了详细的分析过程。3.1.1 进程的同步和互斥的概念1.同步(Synchronization)相互合作的进程需要在某些点上协调，先到达某点的进程需要等待后到达的进程，进程间的这种协调关系叫同步。2.互斥(Mutex)互斥是一种特殊的同步方式。当多个进程需要使用相同的资源，而此资源在任一时

3、刻却只能供一个进程使用，获得资源的进程可以继续执行，没有获得资源的进程必须等待。进程间的这种相互排斥关系叫互斥。3.临界资源与临界区(Critical Resource and Critical Section)临界资源是一次只允许一个进程使用的资源。临界区是在进程中操作临界资源的程序段。3.1.2 锁操作法实现互斥1.基本思想实现互斥的基本思想是使多个进程不能同时进入临界区。给每个临界资源分配一个锁：锁打开时，进程进入临界区，将锁关闭，开始操作临界资源，离开临界区时，将锁打开；锁关闭时，需要进入临界区的进程要等待。2.操作锁的步骤(1)确定临界资源；(2)确定临界区；(3)确定锁个数；(4)

4、设置锁操作。3.1.3信号量与P、V操作1.信号量的引入1965年，荷兰学者Dijkstra提出的信号量机制是一种卓有成效的进程同步工具。在长期且广泛的应用中，信号量机制得到了很大的发展：它从整型信号量经记录型信号量，进而发展为“信号量集”机制。现在的信号量机制已被广泛的应用于单处理机、多处理机系统和计算机网络中。2.信号量(Semaphore)设 S 为信号量，可以将S 看成一个信号灯，但 S 能比信号灯表达更丰富的含义。(1)当 S0时，是绿灯，进程看到绿灯可以通过。S 值越大，通过进程的能力越大，供进程使用的相关资源越多。S 值反映了可供进程使用的相关资源的数量。(2)当 S=0时，是红

5、灯，进程看到红灯需要等待。此时表示等待S 信号的进程的个数。3.信号量的操作最初由Dijkstra把整型信号量定义为一个整型量，除初始化外，仅能通过两个标准的原子操作Wait(S)和 Signal(S)来访问，其它方法都不能操作信号量。这两个操作很长时间以来，一直被分别称为P、V 操作，因为希腊语的Wait词头为P,Signal的词头为V。对信号量的操作定义如下：(1)P(S)或 Wait(S)：是等待信号的操作，是查看信号的操作，是看灯操作。若为绿灯，进程继续前进；若为红灯，进程必须等待。在该操作中，进 行 S=S-1,操作使S 的值向负方向转化，即操作使信号灯S 向红的方向转化。(2)V(

6、S)或 Signal(S)：是发送信号的操作。在该操作中,进行S=S+1,操作使S 的值向正方向转化，即操作使信号灯S 向绿的方向转化。4.P(S)、V(S)的实现(1)整型信号量P(S)：while s=0 do no-opS：=S-1；V(S)：S：=S+1；(2)记录型信号量在整型信号量机制中的wait操作，只要是信号量S =0,就会不断地测试。因此，该机制并未遵循“让权等待”的准则，而是该进程处于“忙等”的状态。记录型信号量机制则是一种不存在“忙等”问题的进程同步机制。但在采取了“让权等待”的策略后，又会出现多个进程等待访问同一临界资源的问题。为此，在信号量机制中，除了需要一个用于代表

7、资源数目的整型变量value外，还应增加一个进程链表L,用于链接或记录上述的所有因此信号量而等待的进程。记录型信号量是由于它采用了纪录型的数据结构而得名的。它所包含的上述两个数据项可描述为：type semaphore=recordvalue:integer;L:list of process;End相应地，wait(s)和 singal(s)操作可描述为：Procedure wait(s)var s:semaphore;BeginS.value:=S.value-l;If S.value0 thenBeginInsert(*,S.L)；Block(*)；EndEndProcedure sig

8、nal(s)var S:semaphore;BeginS.value:=S.value+1;If S.value=0 thenBeginN=remove(S.L);Wakeup(N);EndEnd每次的wait操作，意味着进程请求一个单位的资源，因此描述为S.value:=S.value-1；当 S.valuevO时，表示资源已分配完毕，进程需要等待而进入阻塞状态。为了便于唤醒，在当前进程需要进入阻塞状态前，将当前进程号插入到信号量链表S.L中，进程调用block原语，进行自我阻塞，放弃处理机。因为只有在S.valuevO时进程才进入阻塞状态，所以当 S.value0时，进程可以操作临界资源，

9、可以进入临界区，否则mutex0；,S1没有执行时，信号量S=0。初始状态S1语句没有执行，因此S=0。因为S1执行后S 应变成大于0 的值，所以S 应被初始化为0。这样，若 P2先执行必定阻塞自己，只有在进程P1执行完SI；signal(s)后，使 S 增 为 1 时,P2进程才能执行语句S2o同样，可以利用信号量，按下图语句间的前趋关系，写出一个可并发执行的程序。详细描述如下：var a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;beginparbeginbegin SI;signal(a);signal(b);end;begin wait(a);S2;si

10、gnal(c);signal(d);end;begin wait(b);S3;signal(e);end;begin wait(c);S4;signal(f);end;begin wait(d);S5;signal(g);end;begin wait(e);wait(f);wait(g);S6;end;parendend图4.1进程前趋关系图3.解决同步和互斥问题的步骤(1)确定并发和顺序操作哪些操作是并发的？哪些操作是顺序的？这是解决同步和互斥问题时首先要确定的。并发操作可以用多个进程实现，同步和互斥就发生在这多个进程之间。多个进程操作同一临界资源就是进程间的互斥问题，多个进程要按一定的顺序

11、进行操作就是进程间的同步问题。(2)确定互斥和同步的规则分析具体问题，确定同步和互斥的基本方式，确定能够进行正确操作的条件，在这些条件中隐含着同步和互斥的规则。(3)确定同步、互斥的操作流程按操作的步骤，写出每个进程操作的流程(4)确定信号量的个数和含义根据同步和互斥规则以及操作流程确定信号量的个数，确定信号量代表的含义，只有确切地知道信号量所代表的含义，设置这个信号量才有意义。(5)确定信号量的初值同步信号量的初值则要根据进程的初始状态确定，具体问题要具体分析，没有统的方法。(6)确定P、V 操作的位置根据同步和互斥规则和每个进程的操作流程就可以确定P、V操作的位置。需要说明的是无论是互斥问

12、题还是同步问题，只要是需要进程进入阻塞状态，就必须想到在什么时候将进程唤醒。初学者开始时可以按上述步骤解决同步和互斥问题，熟练后，就可以不局限于这些规则，灵活应用。这好象学骑自行车一样，开始时需要左看右看，掌握了基本要领，熟练操作以后就可以随心所欲。以上讲述的只是一般的求解规则，虽然有一定的可操作性，但在实际应用中还是要针对具体情况，多做多想，领悟出其中的原理和窍门。4.同步和互斥的经典问题(1)生产者和消费者问题(P C P:P r o d u c e r-C o n s u m e r P r o b l e m)。例如，消息缓冲通信的管理。(2)读者和写者问题(R W P:R e a d

13、 e r-W r i t e r P r o b l e m )(,例如，共享文件的读写问题。(3)哲学家进餐问题(D P P:D i n i n g P h i l o s o p h e r P r o b l e m)。例如，进程对多类资源的竞争使用。3.2 例题解析例 3.2.1多道程序系统程序的执行失去了封闭性和再现性，因此多道程序的执行不需要这些特性，这种说法是否正确？解 这种说法不正确。可以想象，如果一个程序在多道程序系统中，在相同的输入的情况下，多次执行所得结果是不同的，有谁还敢使用这个程序？因此，多道程序的执行也需要封闭性和再现性，只不过单道程序系统的封闭性和再现性是先天固有

14、的，多道程序系统的程序执行要想获得封闭性和再现性，需通过程序员的精心设计才能得到。所使用的方法就是同步和互斥的方法。例 3 2 2 多个进程对信号量S进行了 5次P操作，2次V操作后，现在信号量的值是-3,与信号量S相关的处于阻塞状态的进程有几个？信号量的初值是多少？解(1)因为S的当前值是-3,因此因为S处于阻塞状态的进程有3个；(2)因为每进行一次P(S)操作，S的值都减1,每执行1次V操作S的值加1,故信号量的初值为-3+5-2=。；例 3.2.3如下锁的实现方法存在什么缺点？如何改进？L O C K(X)U N L O C K(X)d o w h i l e X=1 ;X=1X=0;)

15、解 存在的缺点是：当锁是关闭时，采用的是循环等待的方法，这样的等待还是要占用处理机的时间，应该采用阻塞等待的方法。改进的锁实现如下：L O C K(X)U N L O C K(X)(i f X.v a l u e=li f n o t e m p t y(X.L)i n s e r t (*,X.L);P=r e m o v e (X.L);B l o c k (*)W a k e u p(P)e l s e X.V a l u e=le l s e X.V a l u e=0)这里X.v a l u e是锁的值，X.L是存放由于锁X而阻塞的进程的队列。i n s e r t (*,X.L)将

16、当前进程的进程号插入到X.L,r e m o v e (X.L)是从X.L中移出一个进程号。例 3.2.4使用多个进程计算Y=F 1(X)+F 2 (X).解(1)确定并发和顺序操作在这个问题中，F 1(X)和F 2 (X)的计算是可以并行处理的，因此F 1(X)和F 2 (X)可以分别出现在两个进程中。(2)确定互斥或同步的规则在F 1(X)+F 2(X)中，必须在F 1(X)和F 2(X)计算完毕，才能进行加法运算，因此本问题是同步问题。(3)同步的操作流程 进程m a i n)创立进程p l来计算F 1(X)；创立进程p 2来计算F 2(X)；F 1(X)计算是否完成？没有，等待；F2(

17、X)计算是否完成？没有，等待：进行加法运算。(进程p Dy l=Fl(X)；设置F1(X)计算完成标志；进程p 2)y l =F2(X)；设置F2(X)计算完成标志。(4)确定信号量的个数和含义根据同步规则以及操作流程确定信号量的个数是2个，S1 和 S2：S1 含义是F1(X)计算是否完成；S2 含义是F2(X)计算是否完成。(5)确定信号量的初值S1=O；S2=0 o(6)确定P、V 操作的位置上面处是一个P 操作，P(S1)：上面处是一个P 操作，P(S2)；上面处是一个V 操作，V(S1)；上面处是一个V 操作，V(S2)解 法 1M ain ()P u bl ic y,y l,y 2

18、,.P l,P 2Sem ap ho r e S1,S2(Sl=0;S2=0;P l=Cr eat(N-Fl,Fl,x,.);P 2=Cr eat(N-F2,F2,x,.);P(S1);P(S2);y=y l+y 2;)P r o cedu r e Fl(x)y l=计 算 1;V(S1)；)P r o cedu r e F2(x)y 2=计算2;V(S2)解法2M ain ()P u bl ic y,y l,y 2,.P l,xSem ap ho r e SI in p u t(x);Sl=0;P l=Cr eat(N-Fl,Fl,x.);Y2=F2(x);P(S1)；y=y l+y 2;P

19、 r o cedu r e Fl(x)(yl=计 算1;V(S1)采用2个进程和1个信号量来实现Y=F1(X)+F2(X)的时候，采用的方法是父进程创立子进程，F1(X)在子进程中计算，F2 (X)在父进程中计算，因此F1(X)和F2(X)计算仍然是并发进行的。S 1信号量的含义为F1(X)是否完成。改进的方法比原来的方法节约一个进程和一个信号量，但并发操作的程度并没有降低。例3.2.5生产者一消费者问题演变。情 况1 一 个bu ffer,一个生产者，一个消费者，生产者只生产一个东西，消费者只进行一次消费，即：生产者只进行一次p u t dat a操作，消费者只进行一次get dat a操作

20、。解 这是一个同步问题，生产者和消费者分别是2个并发的进程。(1)操作规则如果bu ffer为空，则消费者只能等待。(2)操作流程 生产者(p u t dat a；设置B u ffer有数据标志V(S)消费者(判断bu ffer是否有产品，没有则等待：get dat a；(3)信号量设 置 1 个信号量full,full表示buffer是否有数据，初值为O o(4)P、V 操作实现var full:semaphore:=0;buffer:array 1 of item;beginparbeginproducer:beginputdata；V(full);endconsumer:beginP(f

21、ull);getdata;endparendend情况2 一个buffer,一个生产者，一个消费者，生产者不断地进行putdata操作，消费者不断地进行getdata操作，即：生产者不断地生产，消费者不断地消费(1)操作规则只有buffer为空时才能进行putdata操作：只有buffer有数据时才能进行putdata操作。(2)操作流程 生产者repeat判断buffer是否为空，不空则等待；putdata；设置buffer有数据的标志；until false)消费者(repeat判断buffer是否有数据，没有数据则等待；getdata；设置buffer为空标志；until false)(

22、3)信号量设置2 个信号量full和 empty。full表示buffer是否有数据。因为进程在初始状态时，buffer中没有数据，故初值为0,变化范围-1 7。empty表示buffer是否为空。因为进程在初始状态时，buffer为空，故初值为0 初值为1,变化范围(4)P、V 操作实现var full:semaphore:=0;emptyl:semaphore:=1;buffer:array 1 of item;beginparbeginproducer：beginrepeatP(empty)；putdata；V(full);until falseendconsumer：beginrepe

23、at P(full)；getdata；V(empty)；until false.endparendend情 况 3-个 buffer,多个生产者，多个消费者，多个生产者和消费者都在不断地存取 buffer,即生产者不断地进行putdata操作，消费者不断地进行getdata操作。(1)操作规则只有buffer为空时才能进行putdata操作；只有buffer有数据时才能进行putdata操作。这时buffer变成了临界资源，不允许多个进程同时操作buffer,即不允许多个消费者同时进行gedata,不允许多个生产者同时进行putdata操作。(2)操作流程 生产(repeat判断buffer是

24、否为空，不则等待；是否可操作buffer；putdata；设置buffer可操作标志；设置buffer有数据的标志；until false)消费者(repeat判断buffer是否有数据，没有则等待;是否可操作buffer；getdata；设置buffer可操作标志；设置buffer为空标志；until false(3)信号量设置3 个信号量fulR empty和 B-M。full表示buffer是否有数据，初值为0；empty表示buffer是否为空，初值为1；B-M 表 示 buffer是否可操作，初值为1。由于buffer只有一个，full和 empty可以保证对buffer的正确操作，

25、故 B-M 是多余的,可以省略。(4)P、V 操作实现 生产者 消费者repeatP(empty)；P(B-M)：putdata；V(B-M)；repeatP(full)；P(B-M)；getdata；V(B-M)；V(full)；until false.V(empty)；until false )情况4多个生产者，多个消费者，N 个 buffer,多次循环存取buffer,即，即多个生产者不断地进行putdata操作，多个消费者不断地进行getdata操作。(1)操作规则只有buffer有空间才能进行putdata操作；只有buffer有数据才能进行putdata操作；这 时 buffer变

26、成了临界资源，不允许多个消费者和生产者同时对同一个buffer进行gedata 和 putdata 操作。(2)操作流程 生产者(repeat判断buffer是否有空间,没有则等待；是否可操作buffer；putdata；设置buffer可操作标志；设置buffer有数据的标志；until false)消费者(repeat判断buffer是否有数据，没有则等待；是否可操作buffer；getdata；设置buffer可操作标志；设置buffer有空间标志：until false)(3)信号量full表示buffer是否有数据，初值为0;empty表示buffer是否为空，初值为N；B-M 表

27、示 buffer是否可操作，初值为1。(4)P、V 操作实现 生产者 消费者repeatrepeatP(empty)；P(ftill);P(B-M)；P(B-M)；putdata；getdata；V(B-M)；V(B-M)；V(full)；V(empty)；until falseuntil false(5)改进的P、V 操作实现在上述的实现中，putdata和 getdata操作都在临界区中，因此多个进程对多个buffer的操作是不能并发进行的，进程间并行操作的程度很低。实际上只要保证多个进程同时操作不同buffer就可以实现对整个buffer的并行操作。因此，只要保证为不同的进程分配不同 b

28、uffer,putdata和 getdata操作是可以同时进行。这样互斥不是发生在对buffer的存取操作上，而是发生在对buffer的分配上，这个时间与存取buffer的时间相比是较短的，因此减少了进程处于临界区的时间。这里引入2 个函数：getE_buffer(),返回值是空的buffer号；getD_buffer(),返回值是有数据的buffer号。getE_buffer()和 getD_buffer()通过将buffer转换成循环队列的方法来实现对buffer的分配。buffer设有Pbuff,Pdata两个指针，分别指向空闲buffer和有数据buffer的头，每进行一次getE_b

29、uffer()和 getD_buffer(),Pbuff和 Pdata两个指针分别向后移动一个位置。GetE_buffer()c=PbuffPbuff=(Pbuff+l)MOD N;Retum(c)getD_data()c=Pdata;Pdata=(pdata+1 )MOD N;Return(c)改进的程序描述如下：var mutex.empty,full:semaphore:=1 ,n,0;buffer:array O/*,n-l of item;Pbuff,Pdata:integer:=0,0;beginparbeginproducer:beginrepeat1P(empty);P(B_M

30、);in:=getE_buffer();V(B_M)putdata(in);V(full);until false;endconsumer:beginrepeatP(full);P(B_M);out:=getD_buffer();V(B_M);Getdata(out);V(empty);until falseendparendend例 3.2.6 设公共汽车上，司机和售票员的活动分别为：司机的活动为启动车辆，正常行车，到站停车；售票员的活动为关车门，售票，开车门。试问：(I)在汽车不断地到站、停车、行驶过程中，司机和售票员的活动是同步关系还是互斥关系？(2)用信号量和P、V 操作实现他们间的协

31、调操作。解(1)确定并发和顺序操作在这个问题中，司机与售票员间是并行操作的，司机和售票员本身的操作是顺序进行的。因此司机是一个进程，售票员是一个进程，它们之间是同步关系。(2)确定同步的规则根据一般常识，司机和售票员在车上的操作规则如下：1)售票员操作的规则是只有司机停车后，售票员才能开门让乘客上下车；2)司机操作的规则是只有售票员关门后，司机才能启动开始行驶汽车。可见，售票员关车门后，要向司机发开车信号，司机接到开车信号后才能启动车辆。在汽车正常行驶过程中售票员售票，到站时司机停车，售票员在车停后开车门，让乘客上下车。因此司机启动车辆的动作必须与售票员的动作取得同步；售票员开车门的动作也必须

32、同司机停车取得同步。(3)进程的操作流程 售票员进程d o wh i l e T关车门；设立车门已关标志；售票；是否停车？没停则等待；开车门；上下乘客；e nd d o 司机进程d o wh i l e T是否关门？没关则等待；启动车辆：正常行车；到站停车；设立车停标志；e nd d o(4)确定信号量的个数和含义根据同步规则以及操作流程确定信号量的个数是2个，S 1和S 2 oS 1的含义是否关门；S 2的含义是否停车。(5)确定信号量的初值S l=0；S 2=l o(6)确定P、V操作的位置司机操作中，是否关门？没关则等待，这是一个P操作，P(S 1)；司机操作中，设立停车标志，这是一个V

33、操作，V(S 2)；售票员操作中，是否停车？没停则等待，这是一个P操作，P(S 2)；售票员操作中，设立关门标志，这是一个V操作，V(S 1),(7)P、V操作实现i nt S 1=0;i nt S 2=l;m a i n()cobegindriver();busman();coenddrive r()do while T P(S1);启动车辆；正常行车；到站停车；V(S2)；)busserver()do while T 关车门：V(S1)：售票；P(S2)；开车门；上下乘客；例 3 2 7 在 O S中引入管程的目的是什么？解 在 O S中引入管程的目的是为了更简便、更可靠地解决进程之间的同

34、步、互斥问题。在未引入管程之间，进程间的同步、互斥问题是由程序员处理的。例如，在临界区的前后插入P、V 操作。但是，由程序员处理同步、互斥问题有可能引入种种人为的错误。管程主要是管理对共享数据的操作和使用，即把对共享数据互斥使用的控制这一任务从程序员身上，交由编译程序去处理，这样既方便了编程，又不会产生人为的同步、互斥上的错误。例 3.2.8 说明管程中条件变量的含义及作用。解 管程中的条件变量(类型为Condition)是供调用管程中外部过程的进程执行Wait和 Signal操作将自己挂起和解挂的变量。可通过与信号量的比较来认识条件变量：(D 信号量要赋初值而条件变量不赋初值，它只是一个队首

35、指针；(2)在信号量上执行P 操作的进程不一定会被阻塞，而在条件变量上执行Wait操作的进程肯定被挂起；(3)在信号量上的V操作将导致信号量值加1,若增加后的值小于等于0,则要唤醒在信号量上等待的进程，但唤醒者不受什么影响；而在条件变量上的S i gna l 操作却有两种处理方式：P等待，直到Q 离开管程，或等待另一条件；Q 等待，直 到 P离开管程，或等待另一条件。P、Q 是两个进程。例 3.2.9 如果信号量S的初值是5,现在信号量的值是-5,那么系统中的相关进程至少执行了几个P(S)操作？与信号量S 相关的处于阻塞状态的进程有几个？如果要使信号量S的值大于0,应该进行怎样的操作？解(1)

36、因为每执行一次P操作S的值减1,5-(-5)=1 0,在这期间有可能有进程执行V操作，使 S的值加1,所以至少执行了 1 0 次 P(S)；5 个；(3)6个 V(S)或 5个以上。例 3.2.1 0 如下图所示，有多个P U T 操作同时向B U FF1 放数据，有一个M O V E操作不断地 将 B U FF1 的数据移到B u f f 2,有多个G ET 操作不断地从B u f f 2 中将数据取走。B U FF1 的容量为m,B U FF2 的容量是n,P U T、M O V E、G ET 每次操作一个数据，在操作的过程中要保证数据不丢失。试用P、V原语协调P U T、M O V E的

37、操作，并说明每个信号量的含义和初值。解(1)确定并发的操作本问题是把2个消费者和生产者问题综合在一起。多个P U T 操作与一个MOVE 操作并发进行，多个G E T 操作与一个MOVE 操作并发进行。因此本题涉及三类进程：P U T 类进程，有多个；G E T 类进程，有多个；MOVE 类进程，有 1 个。(2)操作规则1)只有b u f f i 有空间才能进行P U T 操作；2)只有b u f f i 有数据，b u f f 2 有空间才能进行MOVE 操作；3)只有b u f f 2 有数据才能进行G E T 操作；4)不允许多个进程同时操作b u f f i；5)不允许多个进程同时操

38、作buff2。(3)操作流程(repeat判断buffi是否有空间，没有则等待;是否可操作buffi；PUT；设置buffi可操作标志；设置buffi有数据的标志；until false(repeat判断buffi是否有数据，没有则等待;判断buff2是否有空间，没有则等待;是否可操作buffi；是否可操作buff2；MOVE；设置buffi可操作标志；设置buff2可操作标志；设置buffi有空间标志；设置buff2有数据标志；until falseGET类进程(repeat判断buff2是否有数据，没有则等待;是否可操作buff2；GET；设置buffi可操作标志；设置buffi有空间标志

39、；until false(4)信号量设置6 个信号量full 1、empty L B-ML full2、empty2、B-M 2,它们的含义和初值如1)fulll表示buffi是否有数据，初值为0；2)empty 1 表示buffi有空间，初值为m：3)B-M1表示buffi是否可操作，初值为1；4)Full2表示buff2是否有数据，初值为0；5)Empty2表示buff2有空间，初值为n；6)B-M2表示buff2是否可操作，初值为1；(5)P、V 操作实现PUT类进程repeatP(emptyl)；/*判断buffi是否有空间，没有则等待*/P(B-M1)；/*是否可操作 buffi*/

40、PUT；V(B-M1)；/*设置buflfl可操作标志*/V(ftilll)；/*设置buflfl有数据的标志*/until false)MOVE类进程repeatP(fulll)；/*判断buffi是否有数据，没有则等待*/P(empty2)；/*判断buff2是否有空间，没有则等待*/P(B-M1)；/*是否可操作 buffi*/P(B-M2)；/*是否可操作 buff2*/MOVE：V(B-M1)；/*设置bufifl可操作标志*/V(B-M2)；/*设置buff2可操作标志*/V(emptyl)；/*设置buffi有空间标志*/V(full2)；/*设置buff2有数据标志*/unti

41、l falserepeatP(empty2)；/*判断buff2是否有空间，没有则等待*/P(B-M2)；/*是否可操作 buff2*/GET；V(B-M2)；/*设置bufif2可操作标志*/：/*设置buff2有数据的标志*/until false例 3.2.11 售票厅只能容纳300人，当少于300人时，可以进入；否则，需在外等候。若将每一个购票者作为一个进程，请用P、V 操作编程，并写出信号量的初值。解 购票者进程 iP(S)；进入售票厅；购票；退出售票厅；V(S)；信号量的初值S=300例 3.2.12设 A、B 为两个并发进程，它们共享一个临界资源，其执行临界区的算法框图如卜图所示

42、。试判断该算法是否有错？请说明理由。如果有错，请改正。SI、S 1 的初值为0,CSA、CSB为临界区。I CSAV(S1)A 进程P(S2)P(S1)CSBB 进程V(S2)图 4.3 进程操作图分 析 咋一看，好像是A 进程开始未执行P 操作，便直接进入临界区，以为问题出在这里。从图中可分析出A、B 两进程的执行思路：A 进程对临界资源操作结束后，将其释放 给 B 进程，而 B 进程对临界资源操作结束后，将释放给进程A。系统初启时，S h S2初值为0,则 B 执行P(S1)被阻塞，而 A 进程可直接访问临界资源。故 A、B 两个并发进程不可能同时操作临界资源，该算法是可以保证互斥的。按本

43、题的要求，两个进程对临界资源的操作是没有先后顺序的，但是，在上面的实现中，只有A 进程先操作完临界资源后,B 进程才能操作。解 该算法有错。若 A 进程永不要求访问临界资源，则不会执行V(S1),意味着B 进程的申请永远得不到操作临界资源的机会；同理，若 B 进程不要求访问临界资源，则不会执行V(S2),意味着 A 进程下次也得不到操作临界资源的机会。所以问题在于本应进行互斥控制而使用的却是同步控制。实现改正：设置信号mutexmutex:=1;cobeginA 进程：BeginrepeatP(mutex);CSA;V(mutex);until falseEndB 进程：Beginrepeat

44、P(mutex);CSB;V(mutex);until falseEndCoend例 3.2.1 3 何谓纯代码，它有什么用途？解 纯代码是可以为多个进程共享的程序段，代码不因程序的执行而改变，又称为可重入码。并不是所有的程序段都能被多个进程共享，如果多个进程共享不可重入的代码，就可能会出现错误。纯代码的主要用途就是让多个进程共享它。例 3 2 1 4 某高校计算机系开设网络课并安排上机实习，假设机房共有2nl台机器，有2n名学生选该课，规定：(1)每两个学生组成一组，各占一台机器，协同完成上机实习；(2)只有凑够两个学生，并且此时机房有空闲机器，门卫才允许该组学生进入机房；(3)上机实习由一

45、名教师检查，检查完毕，一组学生才可以离开机房。试用P、V操作模拟上机实习过程。解(1)确定并发和顺序操作在这个问题中，学生(student)、检查教师(teacher)和门卫(gategard)是并行操作的，因此有多个学生(student)进程、一个检查教师(teacher)进程和一个门卫(gategard)进程。(2)确定互斥和同步的规则gateguard：只有凑够两个学生，并且此时机房有空闲机器时，门卫才分配计算机给学生，允许该组学生进入机房；student：只有门卫分配完计算机后，学生才能进入机房上机操作。只有老师检查完毕才能离开。Teacher：只有老师检查完学生的实习，才准许学生离开

46、。(3)每个进程的操作流程设立有学生到达标志，通知gateguard进程；学生是否可进入？上机实习；设立实习完成标志，通知教师；教师是否可检查，等待教师检查完毕；学生释放一台计算机资源；repeat是否有学生1 实习完成？是否有学生2 实习完成？(是否有一组学生实习完成)检查学生实习结果；检查完成，允许学生1 离开；检查完成，允许学生2 离开；until falserepeat等待学生1到达；等待学生2 到达；是否有可用的计算机1;是否有可用的计算机2;分配计算机；设置学生1 可进入标志；设置学生2 可进入标志；until false(4)确定信号量的个数和含义student：是否有学生；co

47、mputer：是否有可用的计算机：enter：学生是否可以进入机房；finish：是否有学生完成实习；test：老师是否检查完一组学生。(5)确定信号量的初值在初始状态，各信号量的初值如下：student=O学生没有到达；compute=2m 有 2m 个可用的计算机；enter=0不允许学生进入机房，因为需要得到门卫允许；finish-0没有学生实习完成；test=O老师没有检查学生。(6)确定P、V 操作的位置设立有学生到达标志，通知gateguard进 程=V(student)学生是否可进入？=P(enter)上机实习；设立实习完成标志，通知教师=V(finish)教师是否可检查，等待教

48、师检查完毕=P(test(i)学生释放一台计算机资源=V(computer)repeat是否有学生1 实习完成？=P(student)是否有学生2 实习完成？=P(student)(是否有一组学生实习完成)检查学生实习结果；检查完成,允许学生1离 开=V(test(i)检查完成，允许学生2 离 开=V(test)until falserepeat等待学生1到 达=P(student)等待学生2 到 达=P(student)是否有可用的计算机1 =P(computer)是否有可用的计算机2=P(computer)分配计算机；设置学生1可进入标志=V(enter)设置学生2 可进入标志=V(ent

49、er)until false(7)P、V 操作实现程序如下：student:=0;computer:=2m;enter:=0;finish:=0;test(i):=O;parbeginStudent i:BeginV(student);/*表示有学生到达，通知gate guard进 程*/P(enter);/*学生是否可进入*/上机实习；V(finish);/*实习结束，通知教师,有需要检查的学生*/P(test(i);/*等待教师检查完毕*/V(computer);/*释放计算机资源End;Teacher:BeginrepeatP(finish);/*是否有需要检查的学生，等待实习完成*/P

50、(finish);/*是否有需要检查的学生，等待实习完成*/选出可检查的第i 组学生；检查第i 组学生实习结果；V(test(i);/*检查完成*/V(test)；/*检查完成*/until falseEnd;Gategard:Beginrepeat.P(st ude nt);/*等待学生到达*/P(student);/*等待另一学生到达*/P(computer);/*是否有可用的计算机*/P(computer);/*是否有可用的计算机*/分配计算机；V(enter);/*设置学生1可进入标志*/V(enter);/*设置学生2 可进入标志*/untile falseEnd;Parend;在

51、student进程中，如果在一个学生到达后，立即向gateguard进程发信号，在 gateguard进程为其分配计算机后，该学生才被允许进入机房，因此避免了让该学生争夺计算机的使用权和死锁的发生。例 3 2 1 5 针对如下所示的优先图解答下列问题:图4.4进程优先图(1)仅使用并发语句能否将其转换成正确的程序？如果能则写出相应程序，如果不能则说明为什么？(2)若可以使用信号量机构，该优先图将如何转换成正确的程序？解(1)如果仅用并发语句不能将其转换成程序。(S3)因为S5有 2 个前趋，S4有 2 个前趋，S6有 2 个前趋。(2)使用信号量机构，就可以将其转换成程序。Var a,b,c,

52、d,e,f,g,h:Semaphores;初值均为0ParbeginBegin SI;V(a);V(b);V(c);EndBegin P(a);S2;V(d);V(e);EndBegin P(b);S3;V(f);EndBegin P(c);S4;V(h);EndBegin P(d);P(f)；S5;V(g);EndBegin P(g);P(h);S6;EndParend例 3.2.16下面是两个并发执行的进程。它们能正确执行吗？若不能，试举例说明，并改正之。CobeginVar x:integer;Process PlVar y,z:integer;Beginx:=l;y:=0;If x 2

53、 1 then y:=y+l;z:=y;End;Process P2Var t,u:integer;Beginx:=0;t:=0;If xl then t:=t+2;u:=t;End;Coend解 本题中的两个并发进程P l 和 P 2 不能正确地工作，运行结果可能具有不确定性。现说明如下：进程P1 进程P2lx:=l;(l)x:=0;y：=0;t：=0；3if xZ l then y:=y+l;(3)if xl then t:=t+2;4z:=y;(4)u:=t;如果P l和 P2按顺序执行,即f 4 ,(1)-(4),则结果为:y=l,z=l,t=2,u=2如果 Pl 和 P2 的执行顺序

54、是口 2(1)(2)34(3)(4),则结果为：y=0,z=0,t=2,u=2。结果不确定的原因在于使用了公共变量X,这里要求P 1 和 P 2 必须互斥执行。现将程序修改如下：cobeginvar x:integer;S;semaphore;S:=l;Process PlVar y,z:integer;BeginP(S)；x:=l;y：=o；If xN 1 then y:=y+l;V(S);z：=y;endprocess P2var t,u:integer;beginP(S);x:=0;t:=0;If x0时，表示有读操作进程，readcount=0时表示没有读操作进程。因此，当 readc

55、ount开始大于0 时，即 readcount=l时，开始读进程开始读写互斥，readcount=0时，读进程撤消读写互斥。这样就把每个读进程与写进程的互斥转化为整个读操作与写操作的互斥。(3)P、V 操作的确定 写进程P(WR-M)P(W-M)写数据V(W R-M)V(W-M)读进程P(c o u n t-M)Re a d c o u n t=Re a d c o u n t+1I f Re a d c o u n t=l t h e n P(W R-M);V(c o u n t-M)读数据P(c o u n t-M)Re a d c o u n t=Re a d c o u n t-1I

56、f Re a d c o u n t=0 t h e n V(W R-M);V(co u n t-M)以上的解法是读进程优先的，也就是说一旦一个读进程开始读操作，只要还有需要进行读操作的进程，那么，就要保持读操作的独占，直到没有读进程操作的时候，即读进程记数R e ad co u n t=0时，才能允许写进程进行操作。这里可以将WR-M和W-M合并成一个信号量，现在这样做可以更容易理解些。(4)信号量的初值W R-M=1；W-M=l；co u n t-M=O o例3.2.1 9桌上有一空盘，只允许存放一个水果。爸爸可向盘中放苹果，也可向盘中放桔子。儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。规

57、定当盘中空时一次只能放一只水果供吃者取用，请用P、V原语实现爸爸、儿子、女儿三个并发进程的同步。分 析 在本题中，爸爸、儿子、女儿共用一个盘子，且盘中一次只能放一个水果。当盘子为空时，爸爸可将一个水果放入果盘中。若放入果盘中的是苹果，则允许女儿吃，儿子必须等待；若放入果盘中的是桔子，则允许儿子吃，女儿必须等待。本题实际上是生产者-消费者问题的一种变形。这里，生产者放入缓冲区的产品有两类，消费者也有两类，每类消费者只消费其中固定的一类产品。解 在本题中，应设置三个信号量S、S o、S a,信号量S表示盘子是否为空，其初值为1;信号量S。表示盘中是否有桔子，其初值为0；信号量S a表示盘中是否有苹

58、果，其初值为0。同步描述如下：i n t S=l;i n t S a=0;i n t S o=0;m a i n()co be g i nfather();son();daughter();coendfather()(while(l)(P(S);将水果放入盘中；if(放入的是桔子)V(So);else V(Sa);s o n()(while(l)(P(So);从盘中取出桔子;V(s)；吃桔子；daughter()(while(l)(P(Sa);从盘中取出苹果;V(S);吃苹果；)3.3习题3.3.1选择最合适的答案1.用P、v操作管理临界区时，信号量的初值一般应定义为（）。A.-1 B.0 C

59、.1 D.任意值2.有m个进程共享同一临界资源，若使用信号量机制实现对一临界资源的互斥访问,则信号量的变化范围是（）。A.1 至-（m-1）B.1 至 m-1 C.1 至-m D.1 至 m3.在下面的叙述中，正确的是（A.临界资源是非共享资源 B.临界资源是任意共享资源C.临界资源是互斥共享资源1）.临界资源是同时共享资源4.对进程间互斥地使用临界资源，进程可以（）A.互斥地进入临界区 B.互斥地进入各自的临界区C.互斥地进入同一临界区 D.互斥地进入各自的同类资源的临界区5.设两个进程共用一个临界资源的互斥信号量m u te x,当mutex=l时 表 示（）。A.一个进程进入了临界区，另

60、一个进程等待B.没有一个进程进入临界区C.两个进程都进入了临界区D.两个进程都在等待6.设两个进程共用一个临界资源的互斥信号量m utex,当m u te x=T时表示（）。A.一个进程进入了临界区，另一个进程等待B.没有一个进程进入临界区C.两个进程都进入了临界区D.两个进程都在等待7.当一进程因在记录型信号量S上执行P（S）操作而被阻塞后，S的 值 为（）。A.0 B.0 B.0 D.W09.如果信号量的当前值为-4,则表示系统中在该信号量上有（）个进程等待。A.4 B.3 C.5 D.01 0.若有4个进程共享同一程序段,而且每次最多允许3个进程进入该程序段，则信号量的变化范围是（A.3

61、,2,1,0C.4,3,2,1,01 1.若信号S的初值为2,B.3,2,1,0,-1D.2,1,0,-1,-2当前值为-1,则表示有（）个等待进程？A.0 B.1 C.2 D.312.如果有三个进程共享同一互斥段，而且每次最多允许两个进程进入该互斥段，则信号量的初值应设置为（）。A.3 B.1 C.213.并发进程之间（）A.彼此无关C.必须互斥D.0B.必须同步D.可能需要同步或互斥14.在操作系统中，有一组进程，进程之间具有直接相互制约性。这组并发进程之间A.必定无关 B,必定相关C.可能相关 D.相关程度相同15.（）操作不是P 操作可完成的。A.为进程分配处理机 B.使信号量的值变小

62、C.可用于进程的同步 D.使进程进入阻塞状态3.3.2选择所有正确的答案1.有关进程的描述中，（）是正确的。A.进程执行的相对速度不能由进程自己来控制B.利用信号量的P.V 操作可以交换大量信息C.同步是指并发进程之间存在的一种制约关系D.并发进程在访问共享资源时，不可能出现与时间有关的错误2.下列资源中，（）是临界资源。A.打印机 B.非共享的资源C.共享变量 D.共享缓冲区3.进程从执行状态转换到阻塞状态的可能原因是（）.A.时间片完 B.需要等待其它进程的执行结果C.执行了 V 操作 D.执行了 P 操作4.进程从阻塞状态转换到就绪状态的可能原因是（）.A.时间片完 B.其它进程执行了唤

63、醒原语C.执行了 V 操作 D.执行了 P 操作5.在单处理机系统中，设系统中有n 个 进 程（n2），且当前处理机没有执行进程调度程序，下述情况哪些可能发生（A.没有运行的进程，有 2 个进程处于就绪状态，n 个进程处于等待状态。B.一个进程处于运行状态，n-1个进程处于等待状态。C.-个进程处于运行状态，1 个进程处于就绪状态，n-2个进程处于等待状态。D.一个进程处于运行状态，n T 个进程处于就绪状态，没有进程处于等待状态3.3.2 判断正误，错误的简要说明理由1.一个临界资源可以对应多个临界区。2.互斥地使用临界资源是通过互斥地进入临界区实现的。3.同步信号量的初值一般为1。4.引入

64、管程是为了让系统自动处理临界资源的互斥使用问题。5.生产者一消费者问题是一个既有同步又有互斥的问题。6.用管程实现进程同步时，管程中的过程是不可中断的。7.进 程 A、B 共享变量x,需要互斥执行；进 程 B、C 共享变量y,B、C 也需要互斥执行，因此，进程A、C 必须互斥执行。8.单道程序系统中程序的执行也需要同步和互斥。3.3.3 简答题1.为什么说互斥也是一种同步？2.为什么说进程同步问题关系到O S的成败？3.同步机制应遵循的准则是什么？4.进程通信有哪三种基本类型？5.简述解互斥问题的软、硬件方法的异同。6.什 么是原语？它与广义指令有什么区别？7.对临界区管理的要求是什么？8.设

65、 有 n 个进程共享一个互斥段，对于如下两种情况使用信号量，信号量的值的变化怎样？(1)如果每次只允许一个进程进入互斥段；(2)如果每次最多允许m 个 进 程(m n)同时进入互斥段。3.3.4 解答题1.在信号量机制中，若P(S)操作是可中断的，则会有什么问题？2.试述引起多道程序系统程序执行不确定性的内部原因？3.何谓临界区？下面给出的两个进程互斥的算法是安全的吗？为什么？#define true;#define false;int flag；flagl=flag2=false;enter-crtsec(i)inti;(while(flagl-i)flagi=true;leave-crts

66、ec(i)int i;flagi=false;process i:enter-crtsec(i);In critical section;Leave-crtsec(i);4.如何理解原语的原子性，在单机环境下如何实现原语的原子性，实现时应注意哪些问题？5.当进程X 和进程Y 共享某个资源r,进程并发执行时的程序如下：beginS:semaphore:=l;CobeginProcess XBeginL1:P(S);使用资源r；V(S);Goto L1;End;Process YBeginL2:P(S);使用资源r;V(S);Goto L2;End;Coend;End;请回答：(1)两个进程并发执行时，能否保证互斥地使用资源？为什么？(2)如果要使两个进程交替使用资源，若仍使用P、V 操作来进行管理，写出应定义的信号量及其初值。(3)修改上述程序，使两个进程能交替使用资源r。6 .某车站售票厅，任何时刻最多可容纳20名购票者进入，当售票厅中少于20购票者时，则厅外的购票者可立即进入，否则需在外面等待。若把一个购票者看作一个进程，请回答下列问题：(1)用P、V操作管理这些并发进程时，应怎样定