《OS02经典进程同步问题2014-2015-2》由会员分享，可在线阅读，更多相关《OS02经典进程同步问题2014-2015-2（49页珍藏版）》请在金锄头文库上搜索。
1、操作系统 Operating SystemsWINDOWSWINDOWSUNIXUNIXLINUXLINUXOS2OS2VxWorksVxWorksMac OSMac OS2.5 经典进程的同步问题 2.5.1 生产者消费者问题 生产者消费者问题是相互合作的进程关系的一种抽象 制约关系： 只要缓冲池未满，生产者便可将消息送入缓冲池； 只要缓冲池未空，消费者便可从缓冲池中取走一个消息 互斥 123 . nPC信号量解决生产者消费者问题 用信号量及P、V操作解决进程间同步问题 一个生产者、一个消费者共享一个缓冲区多个生产者、多个消费者共享多个缓冲区一个生产者、一个消费者共享一个缓 冲区的解int
2、B;semaphore empty; /可以使用的空缓冲区数semaphore full; /缓冲区内可以使用的产品数empty=1; /缓冲区内允许放入一件产品full=0; /缓冲区内没有产品一个 缓冲 区一个 生产 者生产一 个产品取出一 个产品一个生产者、一个消费者共享一个缓冲区void producer() void consumer()while(true) while(true) produce( ); wait(empty); append( ) to B; signal(full); Emptyfull1001-1-1wait(full);signal(empty);cons
3、ume( );take( ) from B;一组生产者，一组消费者，公用n个环形缓冲区利用记录型信号量解决生产者消费者问题item buffern;int in=0，out=0; /放入、取出缓冲区指针semaphore mutex=1；semaphore empty=n; /可以使用的空缓冲区数semaphore full=0; /缓冲区内可以使用的产品数123 . nP1P2P3.Pm.C1C2C3.Ck信号量设置 为解决这一类生产者消费者问题，应设置两个同步信号 量：empty，full 生产者通过在信号量full上做V操作表示生产一个资源;如果有一个资源释放，在等待队列中的第一个进程被
4、唤醒。 消费者在信号量full上做P操作来表示消耗一个资源; 当资源是不可利用时，将申请资源的进程放置到等待队列中， 由于有界缓冲区是一个临界资源，必须互斥使用，所以，另外还需要设置一个互斥信号量： mutex，初值为1。9 9生产者消费者问题 生产者进程Pi(i=1,2, ,m) 消费者进程Cj(j=1,2, ,k)从缓冲区取一个产品wait(mutex)signal(empty)signal(mutex)消耗该产品wait(full)生产者/消费者、共享多个缓冲区的解void proceducer() do produce an item nextp;wait(empty);wait(mu
5、tex);bufferin=nextp;in=(in+1) % n;signal(mutex);signal(full);while(true); void consumer() do wait(full);wait(mutex);nextc=bufferout;out=(out+1) %n;signal(mutex);signal(empty)；consumer the item in nextc;while(true); 永远等待void producer( )while(true) produce( );wait(mutex); wait(empty); append to Bin;in
6、=(in+1)%k;signal(mutex); signal(full); void consumer( )while(true) wait(full);wait(mutex);take( ) from Bout;out=(out+1)%k;signal(mutex);signal(empty);consume( ); emptyfull0kMutex=1Mutex=0-1信号量及P、V操作讨论 P、V操作必须成对出现 当为互斥操作时，它们处于同一进程 当为同步操作时，则不在同一进程中出现 如果P(S1)和P(S2)两个操作在一起，那么P操作的顺序至关重要 一个同步P操作与一个互斥P操作在一
7、起时，同步P操作在互斥P操作前 两个V操作无关紧要讨论 在生产者-消费者问题中，如果将两个wait 操作，即 wait(full)和 wait(mutex)互换位置 或 wait(empty)和 wait(mutex)互换位置后，其后果如何？ 若将 signal(mutex)和 signal(full)互换位置或signal(mutex)和 signal(empty)互换位置后，其后果如何？Producer:wait(empty); wait(mutex); 将数据加入缓冲区;signal(mutex); signal(full); Consumer:wait(full);wait(mutex
8、);从缓冲区中取出一个数据；signal(mutex);signal(empty);wait(mutex) ; wait(empty) ; signal(empty) ; signal(mutex) ;苹果桔子问题 苹果桔子问题 桌上有一只盘子，每次只能放入一个水果；爸爸专向盘子中放苹果，妈妈专向盘子中放桔子；一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果苹果桔子问题 解决思路： 生产者消费者问题的变形，有两类生产者和两类消费者 互斥： 盘子 同步：爸爸和女儿；妈妈和儿子 进程数目分析 设置3个信号量 empty表示盘子能放的水果数目，初值为1 full_o表示盘子里有无桔子，初值为0
9、 full_a表示盘子里有无苹果，初值为0 empty, full_o, full_a : semaphore; empty := 1;full_o:= 0; full_a:= 0;process father beginL1:削一个苹果；wait(empty);放苹果;signal(full_a);goto L1; end;process mother beginL2:剥一个桔子；wait(empty);放桔子；signal(full_o);goto L2; end; process daughter process daughter beginbeginL4: L4: wait(wait(
10、full_a); );取苹果；取苹果；signal(empty); ); 吃苹果；goto L4;goto L4;end; end; process son process son beginbeginL3: wait( L3: wait(full_o); ); 取桔子；取桔子；signal( (empty); );吃桔子；goto L3;goto L3; end; end; empty盘子容量 full_o有无桔子 full_a有无苹果 问题 可以放n个水果？ empty表示盘子能放的水果数目，初值为n full_o表示盘子里有无桔子，初值为0 full_a表示盘子里有无苹果，初值为0 mu
11、tex对盘子的互斥访问,初值为1empty, full_o, full_a，mutext : semaphore; empty := n; full_o:= 0; full_a:= 0;mutex=1process father beginL1:削一个苹果；wait(empty);wait(mutex);放苹果;signal(mutex);signal(full_a);goto L1;end;process daughter process daughter beginbeginL4: L4: wait( wait(full_a); );wait(mutex);取苹果；取苹果；signal(m
12、utex);signal(empty); ); 吃苹果；吃苹果；goto L4;goto L4;end; end; Empty盘子容量full_o盘子里有无桔子 full_a盘子里有无苹果 Mutex对盘子的互斥访问process mother BeginL2:剥一个桔子；P(empty);P(mutex); 放桔子；V(mutex);V(full_o);goto L2;end; process son process son beginbeginL3: L3: P( P(full_o); ); P(mutex);取桔子；取桔子；V(mutex);V(V(empty); );吃桔子；吃桔子；g
13、oto L3;goto L3;end; end; Empty盘子容量full_o盘子里有无桔子 full_a盘子里有无苹果 Mutex对盘子的互斥访问苹果桔子问题讨论 盘子能放入5个水果；爸爸向盘子中放苹果或桔子；一个儿子专等吃盘子中的桔子，一个女儿专等吃盘子里的苹果father :while(1) wait(empty);wait(mutex);放水果;signal(mutex);if(桔子桔子) )signal(full_o);elsesignal(full_a);daughter : while(1) wait(full_a);wait(mutex);取苹果；signal(mutex);
14、signal(empty); 吃苹果 Son: while(1) wait(full_o); wait(mutex);取桔子；signal(mutex);signal(empty);吃桔子； Empty=5盘子容量full_o=0有无桔子full_a=0有无苹果Mutex=1互斥访问2.5.2 哲学家进餐问题 有五个哲学家围坐在一圆桌旁，桌中央有一盘通心面，每人面前有一只空盘于，每两人之间放一把筷子。每个哲学家思考、饥饿、然后吃通心面。为了吃面，每个哲学家必须获得两只筷子，且每人只能直接从自己左边或右边去取叉子 解决思路 5位哲学家看作5个进程 筷子是临界资源，在一段时间内只允许一位哲学家使用 可以用一个信号量表示一只筷子 由这五个信号量构成信号量数组。其描述如下： semaphore chopstick5=1,1,1,1,1； 所有信号量均被初始化为1用记录型信号量解决哲学家进餐问题 第i位哲学家的活动可描述为：do wait(chopsticki)；wait(chopstick(i+1)mod 5)；eat；signal(chopsticki)；signal(chopstick(i+1)mod 5)；think； while(TRUE)； 分析 上述解法可保证不会有两个相邻的哲学家同时进餐问题 有可能引起死锁 可能出现永远等待
