信號量機制-課堂練習(xí)

1、用wait,signal操作解決進程的同步和互斥問題，絕大部分題目可以按以下步驟解決：根據(jù)題目要求將每個進程的執(zhí)行過程一步一步描述出來；分析每個進程每一步的執(zhí)行條件，將條件一一記錄；比較各個條件，將同一條件歸為一個，若條件可以歸結(jié)為一種資源，設(shè)置一個信號量表示；注意：這里是做題，不是實現(xiàn)系統(tǒng)，所以若某個條件題目中沒有加以說明或限制，則刪除；設(shè)置信號量初值：若信號量是代表某種資源，則為系統(tǒng)初始時的可使用的資源數(shù)或可使用資源的進程數(shù)，若為互斥則為“1”；重新分析每個進程的每個步驟：若該步驟有執(zhí)行條件涉及信號量A，則在該步驟語句前加入wait(A)；若該步驟有執(zhí)行后某個信號量B會增值，則在該步驟語句

2、后加入signal(B)；注意：若某個步驟前同時有幾個wait操作，則一般同步信號量在前，互斥信號量在后；題目已經(jīng)做完，最后檢查各個進程是否能按題目要求并發(fā)執(zhí)行，若可以，停止；若不可以，檢查上述過程，查找錯誤。例1 有一個生產(chǎn)者和一個消費者共享容量為n的緩沖器(n均大于1)，生產(chǎn)者把生產(chǎn)的物品存入緩沖器，而消費者從緩沖器中取出物品去消費。要求用wait,signal操作對生產(chǎn)者和消費者進行正確管理。第一步 根據(jù)題目要求將每個進程的執(zhí)行過程一步一步描述出來：生產(chǎn)者進程 L1: 生產(chǎn)一件產(chǎn)品；產(chǎn)品放入緩沖；goto L1；消費者進程 L2: 從緩沖中區(qū)走產(chǎn)品；消費一件產(chǎn)品；goto L2；第二步

3、分析每個進程每一步的執(zhí)行條件，將條件一一記錄：生產(chǎn)者進程：生產(chǎn)一件產(chǎn)品的條件是有生產(chǎn)產(chǎn)品的原料，在題目中不曾提及，所以該條件不考慮，認為這一步驟沒有限制條件；產(chǎn)品放入緩沖條件是要有產(chǎn)品、緩沖，由于前一步驟已經(jīng)生產(chǎn)出產(chǎn)品，所以這一步驟執(zhí)行是肯定有產(chǎn)品，這一步驟的限制條件是有緩沖；消費者進程：從緩沖中取走產(chǎn)品條件是緩沖中有產(chǎn)品和，這一步驟的限制條件是緩沖中的產(chǎn)品；消費產(chǎn)品的條件是應(yīng)該是已獲得產(chǎn)品，由于前一步驟已經(jīng)獲得產(chǎn)品，所以這一步驟執(zhí)行是肯定有產(chǎn)品的，所以這一步驟沒有限制條件；第三步 比較各個條件，將同一條件歸為一個，設(shè)置一個信號量表示；根據(jù)第二步分析，本題中有四個限制條件：一個是緩沖，定義信號

4、量empty；一個是產(chǎn)品，定義信號量full；第四步 設(shè)置信號量初值：empty，full是資源數(shù)量，系統(tǒng)初始狀態(tài)應(yīng)該是緩沖均空，無產(chǎn)品，所以empty=n，full=0。第五步 重新分析每個進程的每個步驟，加入wait,signal操作：生產(chǎn)者進程：生產(chǎn)一件產(chǎn)品，無限制條件，且對上述四個信號量無影響；產(chǎn)品放入緩沖條件是緩沖，所以這條語句前加上wait(empty)，這條語句執(zhí)行完后，應(yīng)該緩沖中產(chǎn)品會增加一個，所以這條語句后應(yīng)加入signal(full)；消費者進程：從緩沖中取走產(chǎn)品條件是緩沖中有產(chǎn)品和無消費者從緩沖中取產(chǎn)品，所以這條語句前加上wait(full)，這條語句執(zhí)行完后，緩沖會增加

5、一個，所以這條語句后應(yīng)加入signal(S1)；消費產(chǎn)品無限制條件，且對上述四個信號量無影響。這樣生產(chǎn)者和消費者進程的過程修改為：生產(chǎn)者進程 L1: 生產(chǎn)一件產(chǎn)品； wait(empty);產(chǎn)品放入緩沖；signal(full);goto L1；消費者進程 L2: wait(full);從緩沖中區(qū)走產(chǎn)品；signal(empty);消費一件產(chǎn)品；goto L2；用一個數(shù)組B描述緩沖，k指示放產(chǎn)品的位置，t指示取產(chǎn)品的位置，則完整的生產(chǎn)者消費者算法描述如下：semaphore empty=n,full=0;item buffern;int in=out=0;void producer() whi

6、le (1) produce an item in nextp; . wait(empty); bufferin=nextp; in=(in+1) mod n; signal(full); void consumer()while (1) . wait(full); nextc=bufferout; out=(out+1) mod n; signal(empty); . consume the item in nextc; main()cobegin producer();consumer(); 第六步 檢查：其中wait(S1)和signal(S1)之間的程序段是各生產(chǎn)者的相關(guān)臨界區(qū)，保證了

7、生產(chǎn)者放產(chǎn)品的互斥；wait(S2)和signal(S2)之間的程序段是各消費者的相關(guān)臨界區(qū)，保證了消費者的互斥；wait(empty)保證了有緩沖才可放產(chǎn)品，無緩沖時生產(chǎn)者等待；wait(full)保證了緩沖中有產(chǎn)品才可取產(chǎn)品，無產(chǎn)品時消費者等待；signal(empty)讓消費者通知系統(tǒng)釋放一個緩沖，有生產(chǎn)者等待緩沖時可將其喚醒；signal(full)讓通知生產(chǎn)者系統(tǒng)增加了一個產(chǎn)品，有消費者等待產(chǎn)品時可將其喚醒。符合題目要求，題目完成。例1改 有m個生產(chǎn)者和r個消費者共享容量為n的緩沖器(m，r，n均大于1)，每個生產(chǎn)者都要把各自生產(chǎn)的物品存入緩沖器，而每個消費者也都要從緩沖器中取出物品

8、去消費。要求用wait,signal操作對這些生產(chǎn)者和消費者進行正確管理。在這個問題中生產(chǎn)者與消費者之間應(yīng)該同步。由于沒有限定生產(chǎn)者生產(chǎn)的物品供哪個消費者取用，也沒有限制消費者只能取用哪些物品，因此，生產(chǎn)者只要測試到有緩沖器中尚未放滿物品就可把生產(chǎn)的物品存入，消費者只要測試到緩沖器中有物品就可取出。下面是實現(xiàn)同步機制的過程。第一步 根據(jù)題目要求將每個進程的執(zhí)行過程一步一步描述出來：生產(chǎn)者進程 L1: 生產(chǎn)一件產(chǎn)品；產(chǎn)品放入緩沖；goto L1；消費者進程 L2: 從緩沖中區(qū)走產(chǎn)品；消費一件產(chǎn)品；goto L2；第二步 分析每個進程每一步的執(zhí)行條件，將條件一一記錄：生產(chǎn)者進程：生產(chǎn)一件產(chǎn)品的條件

9、是有生產(chǎn)產(chǎn)品的原料，在題目中不曾提及，所以該條件不考慮，認為這一步驟沒有限制條件；產(chǎn)品放入緩沖條件是要有產(chǎn)品、緩沖和無生產(chǎn)者向緩沖中放產(chǎn)品，由于前一步驟已經(jīng)生產(chǎn)出產(chǎn)品，所以這一步驟執(zhí)行是肯定有產(chǎn)品，這一步驟的限制條件是有緩沖和無生產(chǎn)者向緩沖中放產(chǎn)品；消費者進程：從緩沖中取走產(chǎn)品條件是緩沖中有產(chǎn)品和無消費者從緩沖中取產(chǎn)品，這一步驟的限制條件是緩沖中的產(chǎn)品和無消費者從緩沖中取產(chǎn)品；消費產(chǎn)品的條件是應(yīng)該是已獲得產(chǎn)品，由于前一步驟已經(jīng)獲得產(chǎn)品，所以這一步驟執(zhí)行是肯定有產(chǎn)品的，所以這一步驟沒有限制條件；第三步 比較各個條件，將同一條件歸為一個，設(shè)置一個信號量表示；根據(jù)第二步分析，本題中有四個限制條件：一

10、個是緩沖，定義信號量empty；一個是無生產(chǎn)者向緩沖中放產(chǎn)品，定義信號量mutex1；一個是產(chǎn)品，定義信號量full；一個是無消費者從緩沖中取產(chǎn)品，定義信號量mutex2。第四步 設(shè)置信號量初值：mutex1，mutex2是互斥信號量，每次只能由一個生產(chǎn)者（或消費者）向緩沖中放產(chǎn)品（取產(chǎn)品），所以初值均為“1”；empty，full是資源數(shù)量，系統(tǒng)初始狀態(tài)應(yīng)該是緩沖均空，無產(chǎn)品，所以empty=n，full=0。第五步 重新分析每個進程的每個步驟，加入wait,signal操作：生產(chǎn)者進程：生產(chǎn)一件產(chǎn)品，無限制條件，且對上述四個信號量無影響；產(chǎn)品放入緩沖條件是緩沖和無生產(chǎn)者向緩沖中放產(chǎn)品，所以

11、這條語句前加上wait(empty)、wait(mutex1)，這條語句執(zhí)行完后，應(yīng)該釋放互斥信號量mutex1和緩沖中產(chǎn)品會增加一個，所以這條語句后應(yīng)加入signal(mutex1)、signal(full)；消費者進程：從緩沖中取走產(chǎn)品條件是緩沖中有產(chǎn)品和無消費者從緩沖中取產(chǎn)品，所以這條語句前加上wait(full)、wait(mutex2)，這條語句執(zhí)行完后，應(yīng)該釋放互斥信號量mutex2和緩沖中產(chǎn)品少了一個，緩沖會增加一個，所以這條語句后應(yīng)加入signal(mutex1)、signal(empty)；消費產(chǎn)品無限制條件，且對上述四個信號量無影響。這樣生產(chǎn)者和消費者進程的過程修改為：生產(chǎn)

12、者進程 L1: 生產(chǎn)一件產(chǎn)品； wait(empty); wait(mutex1);產(chǎn)品放入緩沖；signal(mutex1);signal(full);goto L1；消費者進程 L2: wait(full); wait(mutex2);從緩沖中區(qū)走產(chǎn)品；signal(mutex2);signal(empty);消費一件產(chǎn)品；goto L2；用一個數(shù)組B描述緩沖，k指示放產(chǎn)品的位置，t指示取產(chǎn)品的位置，則完整的生產(chǎn)者消費者算法描述如下：semaphore mutex=1,empty=n,full=0;item buffern;int in=out=0;void producer() whil

13、e (1) produce an item in nextp; . wait(empty); wait(mutex); bufferin=nextp; in=(in+1) mod n; signal(mutex); signal(full); void consumer()while (1) . wait(full); wait(mutex); nextc=bufferout; out=(out+1) mod n; signal(mutex); signal(empty); . consume the item in nextc; main()cobegin producer();consum

14、er(); 第六步 檢查：其中wait(mutex1)和signal(mutex1)之間的程序段是各生產(chǎn)者的相關(guān)臨界區(qū)，保證了生產(chǎn)者放產(chǎn)品的互斥；wait(mutex2)和signal(mutex2)之間的程序段是各消費者的相關(guān)臨界區(qū)，保證了消費者的互斥；wait(empty)保證了有緩沖才可放產(chǎn)品，無緩沖時生產(chǎn)者等待；wait(full)保證了緩沖中有產(chǎn)品才可取產(chǎn)品，無產(chǎn)品時消費者等待；signal(empty)讓消費者通知系統(tǒng)釋放一個緩沖，有生產(chǎn)者等待緩沖時可將其喚醒；signal(full)讓通知生產(chǎn)者系統(tǒng)增加了一個產(chǎn)品，有消費者等待產(chǎn)品時可將其喚醒。符合題目要求，題目完成。例2 現(xiàn)有四

15、個進程R1、R2、W1、W2，它們共享可以存放一個數(shù)的緩沖器B。進程R1每次把來自鍵盤的一個數(shù)存入緩沖器B中，供進程W1打印輸出；進程R2每次從磁盤上讀一個數(shù)存放到緩沖器B中，供進程W2打印輸出。為防止數(shù)據(jù)的丟失和重復(fù)打印，問怎樣用wait,signal操作來協(xié)調(diào)這四個進程的并發(fā)執(zhí)行。第一步 根據(jù)題目要求將每個進程的執(zhí)行過程一步一步描述出來：進程R1：Ll: 接收來自鍵盤的數(shù);x=接收的數(shù);B=x; -數(shù)據(jù)放入緩沖 goto L1;進程R2：L2: 從磁盤上讀一個數(shù);y=讀入的數(shù);B=y; -數(shù)據(jù)放入緩沖 goto L2;進程W1: L3: k=B; -從緩沖中取數(shù)據(jù)打印k中數(shù);goto L3

16、進程W2: L4：j=B; -從緩沖中取中數(shù)據(jù) 打印j中數(shù);goto L4第二步 分析每個進程每一步的執(zhí)行條件，將條件一一記錄：進程R1：接收來自鍵盤的數(shù)：執(zhí)行條件要有鍵盤，題目中無要求，所以不加考慮，無限制條件；x=接收的數(shù)：x為進程R1內(nèi)部變量，無需限制條件，此步驟無限制條件；B=x;：數(shù)據(jù)放入緩沖需要數(shù)據(jù)和緩沖，數(shù)據(jù)前面步驟一生成，所以限制條件為有空緩沖； 進程R2（與進程R1同理）：從磁盤上讀一個數(shù)：無限制條件；y=讀入的數(shù)：無限制條件；B=y; ：限制條件為有空緩沖；進程W1:k=B;：從緩沖中取數(shù)據(jù)需要緩沖中有R1輸入數(shù)據(jù)，所以限制條件為緩沖中有R1輸入的數(shù)據(jù)；打印k中數(shù);：執(zhí)行條

17、件要有打印設(shè)備，題目中無要求，所以不加考慮，無限制條件；進程W2（與進程W1同理）：j=B;：限制條件為緩沖中有R2輸入的數(shù)據(jù)；打印j中數(shù);：無限制條件。第三步 比較各個條件，將同一條件歸為一個，設(shè)置一個信號量表示；根據(jù)第二步分析，本題中有三個限制條件，需要定義三個信號量：S：表示空緩沖器B。 S1：表示緩沖器中是否存有進程R1讀入的數(shù)。S2：表示緩沖器中是否存有進程R2讀入的數(shù)。第四步 設(shè)置信號量初值：系統(tǒng)初始狀態(tài)，無數(shù)據(jù)讀入，緩沖為空，所以S的初值為1，S1和S2的初值為0；第五步 重新分析每個進程的每個步驟，加入wait,signal操作：進程R1：接收來自鍵盤的數(shù)：無限制條件，執(zhí)行后對

18、上述三個信號量無增值作用；x=接收的數(shù)：無限制條件，執(zhí)行后對上述三個信號量無增值作用；B=x;：限制條件為有空緩沖，語句前加入wait(S)，執(zhí)行后緩沖中有進程R1讀入的數(shù)，對S1有增值作用，語句后加入signal(S1); 進程R2（與進程R1同理）：從磁盤上讀一個數(shù)：無限制條件，執(zhí)行后對上述三個信號量無增值作用；y=讀入的數(shù)：無限制條件，執(zhí)行后對上述三個信號量無增值作用；B=y; ：限制條件為有空緩沖，語句前加入wait(S)，執(zhí)行后緩沖中有進程R1讀入的數(shù)，對S2有增值作用，語句后加入signal(S2);進程W1:k=B;：限制條件為緩沖中有R1輸入的數(shù)據(jù)，語句前加入wait(S1)，

19、執(zhí)行后歸還緩沖，對S有增值作用，語句后加入signal(S)；打印k中數(shù);：無限制條件，執(zhí)行后對上述三個信號量無增值作用；進程W2（與進程W1同理）：j=B;：限制條件為緩沖中有R2輸入的數(shù)據(jù)，語句前加入wait(S2)，執(zhí)行后歸還緩沖，對S有增值作用，語句后加入signal(S)；打印j中數(shù);：無限制條件，執(zhí)行后對上述三個信號量無增值作用。四個進程可如下描述：semaphore S=1,S1=S2=0;buffer B;void R1（）int x;while(1)接收來自鍵盤的數(shù);x=接收的數(shù);wait(S);B=x;signal(S1); void R2()int y;while(1)

20、從磁盤上讀一個數(shù);y=接收的數(shù);wait(S);B=y;signal(S2); void W1()int k;while(1) wait(Sl);k=B;signal(S);打印k中數(shù); void W2()int j;while(1)wait(S2);j=B;signal(S);打印j中數(shù); main() cobegin R1(); R2(); W1(); W2(); 第六步 檢查：在這里，進程R1和進程R2在向緩沖器B中存數(shù)之前調(diào)用了wait(S)，這個wait(S)起兩個作用：由于S的初值為1，所以wait(S)限制了每次至多只有一個進程可以向緩沖器中存入一個數(shù)，起到了互斥地向緩沖器中存數(shù)

21、的作用；由于當(dāng)緩沖器中有數(shù)且尚未被取走時S的值為0，當(dāng)緩沖器中數(shù)被取走后S的值又為1，因此wait(S)起到了測試允許存入一個新數(shù)的消息是否到達的同步作用。進程W1和進程W2把需要的數(shù)取走后，都調(diào)用signal(S)發(fā)出可以存放一個新數(shù)的消息?？梢?，在這個問題中信號量S既被作為互斥的信號量，又被作為同步的信號量。例 假定有三個進程R、W1、W2共享一個緩沖器B,B中每次只能存放1個數(shù)。進程R每次啟動輸入設(shè)備讀一個整數(shù)且把它存放到緩沖器B中。若存放到緩沖器中的是奇數(shù)，則由進程W1，將其取出打?。蝗舸娣诺骄彌_器中的是偶數(shù)，則由進程W2將其取出打印。同時規(guī)定進程R僅當(dāng)緩沖器中無數(shù)時或緩沖器中的數(shù)已被

22、取出打印后才能再存放一個數(shù)；進程W1和進程W2對存入緩沖器的數(shù)不能重復(fù)打印，也不能從空的緩沖器中取數(shù)。要求用wait,signal操作管理這三個并發(fā)進程，使它們能正確地同步工作。第一步 根據(jù)題目要求將每個進程的執(zhí)行過程一步一步描述出來：進程R：Ll: 從輸入設(shè)備上讀一個數(shù);x=接收的數(shù);B=x; -數(shù)據(jù)放入緩沖 goto L1;進程W1: L2: y=B; -從緩沖中取奇數(shù)打印y中數(shù);goto L2進程W2: L3：z=B; -從緩沖中取中偶數(shù) 打印z中數(shù);goto L3第二步 分析每個進程每一步的執(zhí)行條件，將條件一一記錄：進程R：從輸入設(shè)備上讀一個數(shù)：執(zhí)行條件要有輸入設(shè)備，題目中無要求，所以

23、不加考慮，無限制條件；x=接收的數(shù)：x為進程R內(nèi)部變量，無需限制條件，此步驟無限制條件；B=x;：數(shù)據(jù)放入緩沖需要數(shù)據(jù)和緩沖，數(shù)據(jù)前面步驟一生成，所以限制條件為有空緩沖；進程W1:y=B;：從緩沖中取奇數(shù)，限制條件為緩沖中有R輸入的奇數(shù)；打印y中數(shù);：執(zhí)行條件要有打印設(shè)備，題目中無要求，所以不加考慮，無限制條件；進程W2（與進程W1同理）：z=B;：限制條件為緩沖中有R輸入的偶數(shù)；打印z中數(shù)：無限制條件；第三步 比較各個條件，將同一條件歸為一個，設(shè)置一個信號量表示；根據(jù)第二步分析，本題中有三個限制條件，需要定義三個信號量：S：表示空緩沖器B。 SO：表示緩沖器中是否存有進程R讀入的奇數(shù)。SE：

24、表示緩沖器中是否存有進程R讀入的偶數(shù)。第四步 設(shè)置信號量初值：系統(tǒng)初始狀態(tài)，無數(shù)據(jù)讀入，緩沖為空，所以S的初值為1，SO和SE的初值為0；第五步 重新分析每個進程的每個步驟，加入wait,signal操作：進程R：從輸入設(shè)備上讀一個數(shù)：無限制條件，執(zhí)行后對上述三個信號量無增值作用；x=接收的數(shù)：無限制條件，執(zhí)行后對上述三個信號量無增值作用；B=x;：限制條件為有空緩沖，語句前加入wait(S)，執(zhí)行后，若讀入的數(shù)為奇數(shù)，對SO有增值作用，語句后加入signal(SO)，若讀入的數(shù)為偶數(shù)，對SE有增值作用，語句后加入signal(SE)；進程W1:y=B;：限制條件為緩沖中有R輸入的奇數(shù)，語句前

25、加入wait(SO)，執(zhí)行后歸還緩沖，對S有增值作用，語句后加入signal(S)；打印y中數(shù);：無限制條件，執(zhí)行后對上述三個信號量無增值作用；進程W2（與進程W1同理）：z=B;：限制條件為緩沖中有R輸入的偶數(shù)，語句前加入wait(SE)，執(zhí)行后歸還緩沖，對S有增值作用，語句后加入signal(S)；打印z中數(shù);：無限制條件，執(zhí)行后對上述三個信號量無增值作用。三個進程可如下描述：semaphore S=1,SO=SE=0;buffer B;void R1（）int x;while(1)從輸入設(shè)備上讀一個數(shù);x=接收的數(shù);wait(S);B=x;if B=奇數(shù) then signal(SO);

26、else signal(SE); void W1()int y;while(1) wait(SE);y=B;signal(S);打印y中數(shù); void W2()int z;while(1) wait(SO);z=B;signal(S);打印z中數(shù) ; main() cobegin R(); W1(); W2(); 第六步 檢查：wait(S)保證了進程R只能向緩沖中放入一個整數(shù)，若數(shù)據(jù)沒有取走，則只能等待；wait(SO)保證進程W1只能取走奇數(shù)，若無奇數(shù)則等待；wait(SE)保證進程W2只能取走偶數(shù)，若無偶數(shù)則等待；if B=奇數(shù) then signal(S);else signal(SE

27、);保證了存入奇數(shù)時喚醒W1，存入偶數(shù)時喚醒W；signal(S)可歸還緩沖，可喚醒進程R。練習(xí)： 今有3個并發(fā)進程R，M，P，它們共享一個緩沖器B。進程R負責(zé)從輸入設(shè)備讀信息，每讀出一個記錄后把它存放在緩沖器B中。進程M在緩沖器B中加工進程R存入的記錄。進程P把加工后的記錄打印輸出。緩沖器B中每次只能存放一個記錄，當(dāng)記錄被加工輸出后，緩沖器B中又可存放一個新記錄。請用PV操作為同步機制寫出它們并發(fā)執(zhí)行時能正確工作的程序。Semaphore S1=1,S2=S3=0; void R（）int x; while(1)從輸入設(shè)備上讀一個數(shù);x=接收的數(shù);wait(S1);B=x;signal(S2

28、); void M()while(1) wait(S2);加工B中數(shù)據(jù)；signal(S3); void P()int z; while(1) wait(S3);z=B;signal(S1);打印z中數(shù); Main()cobegin R(); M(); P();2考慮三個吸煙者進程和一個經(jīng)銷商進程的系統(tǒng)。每個吸煙者連續(xù)不斷地做煙卷并抽他做好的煙卷，做一支煙卷需要煙草、紙和火柴三種原料。這三個吸煙者分別掌握有煙草、紙和火柴。經(jīng)銷商源源不斷地提供上述三種原料，但他只將其中的兩種原料放在桌上，具有另一種原料的吸煙者就可以做煙卷并抽煙，且在做完后給經(jīng)銷商發(fā)信號，然后經(jīng)銷商再拿出兩種原料放在桌上，如此反復(fù)。試設(shè)計一個同步算法來描述他們的活動。設(shè)smokerA擁有煙草，需要紙和火柴 設(shè)紙和火柴為信號量A設(shè)smokerB擁有紙 ，需要煙草和火柴 設(shè)煙草和火柴為信號量B設(shè)smokerC擁有火柴，需要