第三章进程管理5

1、复习n进程间的制约关系有哪两种？n什么是进程互斥？什么是进程同步？n什么是私用信号量？什么是公用信号量？各用于何处？n解决进程互斥和同步问题的步骤是什么？第三章 进程管理习题课生产者-消费者问题n把并发进程同步和互斥问题一般化，得到一个抽象的模型，即生产者消费者问题n生产者：释放某一类资源的进程n消费者：使用某一类资源的进程n问题描述：若干个进程通过有限的共享缓冲区交换数据，其中生产者进程不断写入，消费者进程不断读出，共享缓冲区共有n个，任一时刻只能有一个进程对整个共享缓冲区进行操作生产者-消费者问题n分析：n1）同步问题：生产者想写入时，缓冲区中至少有一个时空的，消费者想读出时，缓冲区中至少

2、有一个是满的n互斥问题：任一时刻只能有一个进程可以对缓冲区操作共享缓冲区共享缓冲区P 1P 2. PmC 1C 2.Cn用P、V原语实现生产者-消费者问题n解：1）设私用信号量avail表示缓冲区中的空单元数，full表示缓冲区中的满单元数；公用信号量mutex表示整个缓冲区是否在使用n 2）设初始值avail=n，full=0，mutex=1n 3）描述生产者-消费者问题n注意:P操作顺序很重要：先检查是否有资源可用，再检查是否互斥；V操作顺序无所谓Producer:P(avail);P(mutex);将数据送入缓冲区某单元将数据送入缓冲区某单元V(mutex);V(full);Consum

3、er:P(full);P(mutex);取缓冲区中某单元数据取缓冲区中某单元数据V(mutex);V(avail);用P、V原语实现哲学家问题n例1：5个哲学家在圆桌前进餐，两个人之间各放一根筷子。哲学家或者思考或者分别取左右手边的筷子进餐。请用P、V原语描述每个哲学家的进餐过程。0123414032用P、V原语实现哲学家问题n解：1）设公用信号量si表示是否能取到第i个筷子（i=0,1,2,3,4 ）n 2）设初始值，si=1 （i=0,1,2,3,4 ）n 3）描述第i个哲学家Pi：Pi:repeat think P(si) P(s(i+1) mod 5) eat V(si) V (s(i

4、+1) mod 5) Until false用P、V原语实现哲学家问题(完整)n解：1）设公用信号量mutex表示哲学家是否能同时取到2个筷子，si表示是否能取到第I个筷子（i=0,1,2,3,4 ）n 2）设初始值mutex=1，si=1 （i=0,1,2,3,4 ）n 3）描述第i个哲学家Pi：Pi:repeat think P(mutex) P(si) P(s(i+1) mod 5) V(mutex) eat V(si) V (s(i+1) mod 5) Until false用P、V原语实现同步n例2 设公共汽车上，司机和售票员的活动如下。在汽车不断到站停车、行驶过程中，这两个活动有什

5、么同步关系？用P、V原语实现他们的同步。用P、V原语实现同步n1 1）设）设closeclose为进程为进程P1P1的私有信号量，表示售票员是否的私有信号量，表示售票员是否关门，关门，stopstop为进程为进程P2P2的私有信号量，表示车辆是否停的私有信号量，表示车辆是否停止到站。止到站。n2 2）设初始值）设初始值close=1close=1，stop=0stop=0，表示车正在运行。，表示车正在运行。n3 3）描述：）描述：P1: P1: A:P(close) A:P(close) 启动启动 行车行车 停车停车 V(stop)V(stop) Goto A Goto AP2: P2: B:

6、P(stop) B:P(stop) 开门开门 关门关门 V(close)V(close) 售票售票 Goto BGoto Bn例3 设有一个作业由四个进程组成，这四个进程在运行时必须按图所示的顺序，用P、V原语操作表达四个进程的同步关系。T1T3T2T4n解：1）设同步（私有）信号量 s12，s13，s24，s34分别用于T1与T2，T1与T3，T2与T4，T3与T4之间进行同步n2）设初始值s12=0，s13=0，s24=0，s34=0n3）PV原语描述：T1( ) begin T1; V(s12); V(s13); endT2() begin P(s12); T2; V(s24); end

7、T3() begin P(s13); T3; V(s34); endT4( ) begin P(s24); P(s34); T4; end用P、V原语实现进程同步和互斥n例4：某寺庙，有小、老和尚若干。寺庙有一水缸，可容10桶水，由小和尚提水入缸、取水出缸供老和尚饮用，每次入水、取水仅为1桶，且不可同时进行。水取自同一井中，口窄，每次只能容一个桶取水。水桶总数为3个。用P、V原语给出取水入水的算法描述井缸入水出水用P、V原语实现进程同步和互斥n解：1）设公用信号量mutex1，mutex2分别控制井和缸的互斥，count表示空闲的水桶数；私用信号量empty表示缸中还可以入几桶水，full表示

8、缸中已入几桶水n 2）设初始值mutex1=1，mutex2=1，empty=10，full=0，count=3n 3）描述用P、V原语实现进程同步和互斥n入水：nL1:P(empty)n P(count)n P(mutex1)n 从井中取水n V(mutex1)n P(mutex2)n 送水入缸n V(mutex2)n V(count)n V(full)n Goto L1n取水：nL2:P(full)n P(count)n P(mutex2)n 从缸中取水n V(mutex2)n V(count)n V(empty)n Goto L2用P、V原语实现进程同步和互斥n例5：某车站售票厅有20个

9、窗口，任何时刻最多可容纳20名购票者进入，当售票厅中少于20名购票者时，则厅外的购票者可立即进入，否则需在厅外等待。若把购票者看做一个进程，请用P，V操作管理这些进程，要求如下：(1)在主函数中给出信号量的定义和初值。(2)给出一个购票者进程的算法(3)给出当购票者最多不超过n(设n20)个时，信号量可能的变化范围。用P、V原语实现进程同步和互斥(1)主函数算法 (2)购票者i的算法main() pi() int mutex=20; p(mutex); cobegin 进入售票厅 占有一个窗口购票; p1();p2();pi();pn(); v(mutex); coend （3）信号量最大值为

10、20，最小值为20-n用P、V原语实现进程同步和互斥 例例6：桌上有一空盘，允许存放一只水果。爸：桌上有一空盘，允许存放一只水果。爸爸可向盘中放苹果，也可向盘中放桔子，儿子爸可向盘中放苹果，也可向盘中放桔子，儿子专等吃盘中的桔子，女儿专等吃盘中的苹果。专等吃盘中的桔子，女儿专等吃盘中的苹果。规定当盘空时一次只能放一只水果供吃者取用，规定当盘空时一次只能放一只水果供吃者取用，请用请用P，V原语实现爸爸，儿子，女儿原语实现爸爸，儿子，女儿3个并发个并发进程的同步。进程的同步。解答n1）设同步信号量empty表示盘子是否为空，orange和apple分别表示盘子中放了橘子或苹果n2）设初值empty

11、=1， orange=apple=0，表示盘子为空父亲进程父亲进程()： while(1) P(empty); 往盘中放水果往盘中放水果; if(水果水果=橘子橘子) V(orange); else V(apple); 儿子进程儿子进程()： while(没吃够没吃够)P(orange); 从盘中取橘子从盘中取橘子;V(empty); 女儿进程女儿进程()： while(没吃够没吃够) P(apple);从盘中取苹果从盘中取苹果; V(empty); 用P、V原语实现进程互斥与同步n例7：图书馆阅览室有100个座位，一张登记表，要求阅读者进入时登记，取得座位号，出来时注销座位号。登记表同时只能

12、由一个人使用，用P、V原语描述一个读者进入和出来的过程。n分析：n1）互斥问题：登记表同时只能由一个人使用n2）同步问题：读者进入时，100个座位至少由 一个是空的，出来时，要释放所占有的座位用P、V原语实现进程互斥与同步n解：1）设私用信号量avail表示阅览室中的空座位数，公用信号量mutex表示登记表是否正在使用n 2）设初始值avail=100，mutex=1n 3）描述：Enter: P(avail) P(mutex) 登记 V(mutex)Leave: P(mutex) 注销 V(mutex) V(avail)用P、V原语实现进程同步和互斥n例8：某理发师，当没有顾客时，理发师去睡

13、觉；若有顾客进来时理发师正在睡觉，则这个顾客会叫醒他。试用P、V操作描述协调理发师和顾客之间的同步问题（假设理发店里等候服务的队伍可以无限长）用P、V原语实现进程同步和互斥n解：1）设私用信号量customers表示等候服务的顾客数，barber表示已经做好理发准备的理发师个数n 2）设初始值customers=0， barber=0，表示没有顾客，理发师正在睡觉n 3）描述：用P、V原语实现进程同步和互斥n理发师：nrepeatn P(customers)n V(barber)n 给顾客理发nUntil falsen顾客：nV(customers)nP(barber)n获得理发服务用P、V原

14、语实现进程同步和互斥n例9：某工厂有两个生产车间和一个装配车间。两个生产车间分别生产A、B两种零件，每生产一个零件后都要分别把它们送到装配车间的货架F1、F2上，F1上放零件A，F2上放零件B， F1和 F2的容量均为10个零件，装配工人每次从架上取一个零件A和一个零件B，然后组装成产品，请用P、V原语进行正确管理。A车间B车间F1F2装配工人ABBA用P、V原语实现进程同步和互斥n解：1）设公用信号量mutex1、mutex2控制进程对F1、F2的互斥操作；私用信号量empty1、empty2、full1、full2分别表示F1空位数，F2空位数，F1上零件数，F2上零件数n 2）初始化mu

15、tex1=1，mutex2=1，empty1=10，empty2=10，full1=0，full2=0n 3）描述：用P、V原语实现进程同步和互斥nA车间nL1:生产一个An P(empty1)n P(mutex1)n 放入F1上n V(mutex1)n V(full1)n Goto L1n B车间nL2:生产一个Bn P(empty2)n P(mutex2)n 放入F2上n V(mutex2)n V(full2)n Goto L2l装配工人lL3:P(full1)l P(full2)l P(mutex1)l P(mutex2)l 取AB零件装配l V(mutex1)l V(mutex2)l

16、V(empty1)l V(empty2)l Goto L3用P、V原语实现进程同步和互斥n两个进程PA和PB通过两个FIFO缓冲区队列连接（设缓冲区队列的缓冲区个数都为n个），每个缓冲区长度等于传送消息长度。进程PA和PB之间的通信满足如下条件：n至少有一个空缓冲区存在时，相应的发送进程才能发送一个消息。n当缓冲队列中至少存在一个非空缓冲区时，相应的接收进程才能接收一个消息。PAPB缓冲区队列1缓冲区队列2n试描述对第1个缓冲队列操作的发送过程send(1 , m)和接收过程receive(1 , m)。对第2个缓冲队列操作的发送过程send(2 , m)和接收过程receive(2 , m)

17、。这里1和2分别代表缓冲队列1和缓冲队列2，m代表消息。PAPB缓冲区队列1缓冲区队列2n解：n1）设私有信号量bufempty1,buffull1, bufempty2,buffull2用于进程PA和PB之间进行同步n2）设初始值bufempty1=n,buffull1=0, bufempty2=n,buffull2=0n3）描述PA调用 PB调用nSend(1,m)nBeginn Local xn P (bufempty1)n 按FIFO方式选择一个空缓冲区buf(x)n Buf(x) 消息mn buf(x)置满标记n V(buffull1)nEndnreceive(1,m)nBeginn Local xn P (buffull1)n 按FIFO方式选择一个满缓冲区buf(x)n