1、進程同步算法習題課,【例題1】,用wait、signal操作解決司機與售票員的問題,分析： 為保證車輛行駛安全，售票員必須關好車門，然后通知司機啟動車輛，在行駛過程中售票員不能打開車門，待車到站停穩(wěn)后，司機通知售票員才能打開車門，如此不斷重復。為此，須設置兩個信號量S1，S2用來控制司機和售票員的行為，初值都為0。,解: 算法如下：,司機進程： while(1) wait(S1) 啟動車輛 正常駕駛 到站停車 signal(S2) ,售票員進程： while(1) 關門 signal(S1) 售票 wait(S2) 開門 ,【例題2】,1.用wait、signal操作解決下圖之同步問題 提示：

2、分別考慮對緩沖區(qū)S和T的同步，再合并考慮,get,copy,put,s,t,解:,設置四個信號量Sin=1，Sout=0，Tin=1，Tout=0；,get： while（1） wait(Sin）; 將數(shù)放入S; signal (Sout); ,copy： while（1） wait (Sout）; wait (Tin）; 將數(shù)從S取出放入T; signal (Tout); signal (Sin); ,put： while（1） wait (Tout）; 將數(shù)從T取走; signal(Tin); ,思考題： 如果S和T是由多個緩沖區(qū)組成的緩沖池，上述算法將如何修改？,【例題3】,桌上有一空盤

3、，最多允許存放一只水果。爸爸可向盤中放一個蘋果或放一個桔子，兒子專等吃盤中的桔子，女兒專等吃蘋果。 試用wait、signal操作實現(xiàn)爸爸、兒子、女兒三個并發(fā)進程的同步。,分析： 設置一個信號量S表示空盤子數(shù)，一個信號量So表示盤中桔子數(shù)，一個信號量Sa表示盤中蘋果數(shù)，初值分別為1，0，0。,解: 算法如下：,Father() while(1) wait(S); 將水果放入盤中; if(是桔子)signal(So); else signal(Sa); ,Son() while(1) wait(So) 取桔子 signal(S); 吃桔子; ,Daughter() while(1) wait(S

4、a) 取蘋果 signal(S); 吃蘋果; ,【例題4】,有一個倉庫，可以存放A和B兩種產(chǎn)品，但要求： （1） 每次只能存入一種產(chǎn)品（A或B） （2） NA產(chǎn)品數(shù)量B產(chǎn)品數(shù)量M。 其中，N和M是正整數(shù)。試用wait、signal操作描述產(chǎn)品A與B的入庫過程。,解:,分析：設兩個同步信號量Sa、Sb，其中： Sa表示允許A產(chǎn)品比B產(chǎn)品多入庫的數(shù)量，初值為M-1。 Sb表示允許B產(chǎn)品比A產(chǎn)品多入庫的數(shù)量，初值為N-1。 設互斥信號量mutex，初值為1。,B產(chǎn)品入庫進程： j = 0; while (1) wait(Sb); wait(mutex); B產(chǎn)品入庫 signal(mutex); s

5、ignal(Sa); 消費產(chǎn)品; ;,A產(chǎn)品入庫進程：i = 0;while (1) 生產(chǎn)產(chǎn)品; wait(Sa); wait(mutex); A產(chǎn)品入庫 signal(mutex); signal(Sb); ;,算法如下：,例題5,進程A1、A2， An1通過m個緩沖區(qū)向進程B1、B2、 Bn2不斷發(fā)送消息。發(fā)送和接收工作遵循下列規(guī)則： （1） 每個發(fā)送進程一次發(fā)送一個消息，寫入一個緩沖區(qū)，緩沖區(qū)大小等于消息長度。 （2） 對每個消息，B1，B2， Bn2都須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)。 （3） m個緩沖區(qū)都滿時，發(fā)送進程等待，沒有可讀消息時，接收進程等待。 試用wait、signal操

6、作組織正確的發(fā)送和接收工作。,分析：每個緩沖區(qū)只要寫一次但要讀n2次，因此，可以看成n2組緩沖區(qū)，每個發(fā)送者要同時寫n2個緩沖區(qū)，而每個接收者只要讀它自己的緩沖區(qū)。 Sinn2=m；表示每個讀進程開始有m個空緩沖區(qū)。 Soutn2=0；表示每個讀進程開始有0個可接收的消息。,解：,先將問題簡化： 設緩沖區(qū)的大小為1 有一個發(fā)送進程A1 有二個接收進程B1、B2 設有信號量Sin1 、Sin2 初值為1 設有信號量Sout1 、Sout2 初值為0,Bi： while (1) wait(Souti); 從緩沖區(qū)取數(shù) signal(Sini); ,A1:while (1) wait(Sin1);

7、wait(Sin2);將數(shù)據(jù)放入緩沖區(qū) signal(Sout1); signal(Sout2);,向目標前進一步:,設緩沖區(qū)的大小為m 有一個發(fā)送進程A1 有二個接收進程B1、B2 設有信號量Sin1 、Sin2 初值為m 設有信號量Sout1 、Sout2 初值為0,Bi： while (1) wait(Souti); wait(mutex); 從緩沖區(qū)取數(shù) signal(mutex); signal(Sini); ;,A1:while (1) wait(Sin1); wait(Sin2); wait(mutex); 將數(shù)據(jù)放入緩沖區(qū) signal(mutex); signal(Sout1

8、); signal(Sout2);,到達目標,設緩沖區(qū)的大小為m 有n1個發(fā)送進程A1.An1 有n2個接收進程B1Bn2 設有n2個信號量Sinn2 初值均為m 設有n2個信號量Soutn2 初值均為0,Bi： while (1) wait(Souti); wait(mutex); 從緩沖區(qū)取數(shù) signal(mutex); signal(Sini); ;,Aj: while (1) for(i=1;i=n2;i+) wait(Sini); wait(mutex); 將數(shù)據(jù)放入緩沖區(qū) signal(mutex); for(i=1;i=n2;i+) signal(Sout2); ,進程同步算法

9、補充作業(yè)：,設有兩個優(yōu)先級相同的進程p1與p2，令信號量s1、s2的初值為0，已知z=2，試問p1、p2并發(fā)運行后x=?,y=?,z=? 進程p1：y=1; 進程p2： x=1; y=y+2; x=x+1; signal(s1); wait(s1); z=y+1; x=x+y; wait(s2); signal(s2); y=z+y; z=z+x;,2請按下列方法分別寫出非死鎖的哲學家進餐算法： （1）最多允許4個哲學家同時進餐。 （2）奇數(shù)號哲學家先拿其左邊的筷子，然后再那其右邊的筷子；而偶數(shù)號哲學家先拿其右邊的筷子，然后再那其左邊的筷子。,3. 有橋如下圖所示，車流方向如箭頭所示。假設橋上不允許兩車交會，但允許同方向多輛車依次通過（即橋上可有多個相同