操作系統(tǒng)很全很詳細(xì)的進(jìn)程同步與互斥-問題

進(jìn)程同步與互斥例題進(jìn)程同步進(jìn)程同步：并發(fā)進(jìn)程之間相互合作，完成一項(xiàng)工作，它們之間有一定的時(shí)序關(guān)系。解題步驟：確定進(jìn)程的個(gè)數(shù)及每個(gè)進(jìn)程的工作；確定關(guān)鍵工作步〔需要控制的〕；確定信號(hào)量表示的含義〔開始或結(jié)束〕；寫出偽代碼。例1：請用信號(hào)量機(jī)制描述以下并發(fā)進(jìn)程的同步關(guān)系。進(jìn)程的同步SFP1P2P3P4解法一：信號(hào)量表示進(jìn)程能否開始。設(shè)信號(hào)量m1、m2、m3、m4分別表示進(jìn)程P1、P2、P3、P4能否開始執(zhí)行，其初值m1為1，其余均為0。intm1=1,m2=m3=m4=0;cobeginp1()//P2()//P3()//P4()coend進(jìn)程的同步思考：哪個(gè)信號(hào)量可以省略？m1p1(){P(m1)；

執(zhí)行p1；V(m2)；V(m3)；}p2(){P(m2)；

執(zhí)行p2；V(m4)；}p3(){P(m3)；

執(zhí)行p3；V(m4)；}p4(){P(m4)；P(m4)；

執(zhí)行p4；}解法二：信號(hào)量表示進(jìn)程是否結(jié)束。設(shè)信號(hào)量m1、m2、m3、m4分別表示進(jìn)程P1、P2、P3、P4是否結(jié)束，其初值均為0。intm1=m2=m3=m4=0;cobeginp1()//P2()//P3()//P4()coend進(jìn)程的同步思考：哪個(gè)信號(hào)量可以省略？m4p1(){

執(zhí)行p1；V(m1)；V(m1)；}p2(){P(m1)；

執(zhí)行p2；V(m2)；}p3(){P(m1)；

執(zhí)行p3；V(m3)；}p4(){P(m2)；P(m3)；

執(zhí)行p4；V(m4)；}練習(xí)：請用信號(hào)量機(jī)制描述以下并發(fā)進(jìn)程的同步關(guān)系。進(jìn)程的同步SFP1P2P4P7P3P5P6解法一：信號(hào)量表示進(jìn)程能否開始。設(shè)信號(hào)量m1~m7分別表示進(jìn)程P1~P7能否開始執(zhí)行，其初值m1為1，其余均為0。intm1=1,m2=m3=m4=m5=m6=m7=0;cobeginp1()//p2()//p3()//p4()//p5()//p6()//p7()coend進(jìn)程的同步解法二：信號(hào)量表示進(jìn)程是否結(jié)束。設(shè)信號(hào)量m1~m7分別表示進(jìn)程P1~P7是否結(jié)束，其初值均為0。intm1=m2=m3=m4=m5=m6=m7=0;cobeginp1()//p2()//p3()//p4()//p5()//p6()//p7()coend進(jìn)程的同步進(jìn)程的同步例2：公共汽車中的司機(jī)和售票員。司機(jī)P1售票員P2while(true)while(true){{

啟動(dòng)車輛；關(guān)門；

正常運(yùn)行；售票；

到站停車；開門；

}}

解法一：信號(hào)量表示進(jìn)程能否開始。設(shè)信號(hào)量m1表示司機(jī)進(jìn)程P1能否啟動(dòng)汽車，初值為0，m2表示售票員進(jìn)程p2能否開門，初值為0。intm1=0,m2＝0;cobeginp1()//p2()coend進(jìn)程的同步p1(){while(1){P(m1);啟動(dòng)汽車；正常行駛；到站停車；V(m2);}}p2(){while(1){關(guān)門；V(m1);售票；Ｐ(m2);開門；}}解法二：信號(hào)量表示進(jìn)程是否結(jié)束。設(shè)信號(hào)量m1表示司機(jī)進(jìn)程P1到站停車結(jié)束，初值為0，m2表示售票員進(jìn)程p2關(guān)門結(jié)束，初值為0。intm1=0,m2＝0；cobeginp1()//p2()coend進(jìn)程的同步p1(){while(1){P(m2)；啟動(dòng)汽車；正常行駛；到站停車；V(m1)；}}p2(){while(1){關(guān)門；V(m2)；售票；Ｐ(m1)；開門；}}進(jìn)程的同步例3-1：吃水果。父親P1兒子P2while(true)while(true){{

洗水果；取水果；

放水果；吃水果；

}}

0父親兒子水果分析：父親先放水果，兒子再吃水果；兒子取完水果，父親再放水果，這兩個(gè)進(jìn)程是一個(gè)同步關(guān)系。解法一：設(shè)信號(hào)量m1表示父親能否放水果，m2表示兒子能否取水果。其初值m1=1,m2=0。intm1=1,m2=0；cobeginp1()//p2()coend進(jìn)程的同步p1(){while(1){洗水果；P(m1)；

放水果；V(m2)；}}p2(){while(1){P(m2)；

取水果；V(m1)；吃水果；}}思考：假設(shè)盤子能放n個(gè)水果，如何修改同步關(guān)系？intm1=n,m2=0；分析：父親先放水果，兒子再吃水果；兒子取完水果，父親再放水果，這兩個(gè)進(jìn)程是一個(gè)同步關(guān)系。解法二：設(shè)信號(hào)量m1表示父親放完水果，m2表示兒子取完水果。其初值m1=0,m2=1。intm1=0,m2=1；cobeginp1()//p2()coend進(jìn)程的同步p1(){while(1){洗水果；P(m2)；

放水果；V(m1)；}}p2(){while(1){P(m1)；取水果；V(m2)；吃水果；}}進(jìn)程的同步例3-2：吃水果。

父親P1兒子P2女兒P3

while(true)while(true)while(true){{{

洗水果；取桔子；取蘋果；

放水果；吃桔子；吃蘋果；

}}}

桔子父親兒子女兒0蘋果分析：父親先放水果，兒子女兒再吃水果；兒子女兒取完水果，父親再放水果，這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。解法一：設(shè)信號(hào)量m1表示父親能否放水果，m2表示兒子能否取桔子，m3表示女兒能否取蘋果。intm1=1,m2=0,m3=0；cobeginp1()//p2()//p3()coend進(jìn)程的同步p1(){while(1){洗水果；P(m1)；

放水果；if(是桔子)V(m2)；elseV(m3)；}}p2(){while(1){P(m2)；

取桔子；V(m1)；吃桔子；}}p3(){while(1){P(m3)；

取蘋果；V(m1)；吃蘋果；}}分析：父親先放水果，兒子女兒再吃水果；兒子女兒取完水果，父親再放水果，這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。解法二：設(shè)信號(hào)量m1表示父親放完桔子，m2表示父親放完蘋果，m3表示兒子女兒取完水果。intm1=0,m2=0,m3=1；cobeginp1()//p2()//p3()coend進(jìn)程的同步p1(){while(1){洗水果；P(m3)；

放水果；if(是桔子)V(m1)；elseV(m2)；}}p2(){while(1){P(m1)；取桔子；V(m3)；吃桔子；}}p3(){while(1){P(m2)；

取蘋果；V(m3)；吃蘋果；}}進(jìn)程的同步例3-3：吃水果。

父親P1母親P2兒子P3

while(true)while(true)while(true){{{

洗桔子；洗蘋果；取水果；

放桔子；放蘋果；吃水果；

}}}

0父親兒子母親桔子蘋果分析：父母親先放水果，兒子再取水果吃；父親與兒子，母親與兒子是一個(gè)同步關(guān)系，父親與母親要競爭空盤子。解法一：設(shè)信號(hào)量m1表示是否有空盤子，信號(hào)量m2表示兒子能否取水果。intm1=1,m2=0；cobeginp1()//p2()//p3()coend進(jìn)程的同步p1(){while(1){洗桔子；P(m1)；

放桔子；V(m2)；}}p2(){while(1){洗蘋果；P(m1)；放蘋果；V(m2)；}}p3(){while(1){P(m2)；

取水果；V(m1)；吃水果；}}分析：父母親先放水果，兒子再取水果吃；父親與兒子，母親與兒子是一個(gè)同步關(guān)系，父親與母親要競爭空盤子。解法二：設(shè)信號(hào)量m1表示父親或母親放完水果，信號(hào)量m2表示兒子取完水果。intm1=0,m2=1；cobeginp1()//p2()//p3()coend進(jìn)程的同步p1(){while(1){洗桔子；P(m2)；

放桔子；V(m1)；}}p2(){while(1){洗蘋果；P(m2)；

放蘋果；V(m1)；}}p3(){while(1){P(m1)；

取水果；V(m2)；吃水果；}}0進(jìn)程的同步例3-4：吃水果。

父親P1母親P2兒子P3

女兒P4

while(true)while(true)while(true)while(true){{{{

洗桔子；洗蘋果；取蘋果；取桔子；

放桔子；放蘋果；吃蘋果；吃桔子；}}}}

桔子父親女兒母親蘋果兒子分析：父母親先放水果，兒子女兒再取水果；父親與女兒，母親與兒子是一個(gè)同步關(guān)系，父親與母親要競爭空盤子。解法一：設(shè)信號(hào)量m1表示是否有空盤子，信號(hào)量m2表示兒子能否取蘋果，m3表示女兒能否取桔子。intm1=1,m2=0,m3=0；cobeginp1()//p2()//p3()//p4()coend進(jìn)程的同步p1(){while(1){洗桔子；P(m1)；

放桔子；V(m3)；}}p2(){while(1){洗蘋果；P(m1)；

放蘋果；V(m2)；}}p3(){while(1){P(m2)；

取蘋果；V(m1)；吃蘋果；}}p4(){while(1){P(m3)；

取桔子；V(m1)；吃桔子；}}分析：父母親先放水果，兒子再取水果吃；父親與兒子，母親與兒子是一個(gè)同步關(guān)系，父親與母親要競爭空盤子。解法二：設(shè)信號(hào)量m1表示父親放完桔子，m2表示母親放完蘋果，信號(hào)量m3表示兒子或女兒取完水果。intm1=0,m2=0,m3=1；cobeginp1()//p2()//p3()//p4()coend進(jìn)程的同步p1(){while(1){洗桔子；P(m3)；

放桔子；V(m1)；}}p2(){while(1){洗蘋果；P(m3)；

放蘋果；V(m2)；}}p3(){while(1){P(m2)；

取蘋果；V(m3)；吃蘋果；}}p4(){while(1){P(m1)；

取桔子；V(m3)；吃桔子；}}進(jìn)程的同步例4：打印文件。

P1P2P3

while(true)while(true)while(true){{{

從磁盤取文件；從緩沖1取文件；從緩沖2取文件；

放入緩沖1；放入緩沖2；打印文件；

}}}

緩沖1磁盤打印機(jī)緩沖2P1P2P3分析：P1做完，P2才能做，P2做完，P3才能做。這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。解法一：設(shè)信號(hào)量m1表示P1能否把文件放入緩沖1，m2表示P2能否從緩沖1取文件，m3表示P2能否把文件放入緩沖2，m4表示P3能否從緩沖2取文件。intm1=1,m2=0,m3=1,m4=0；cobeginp1()//p2()//p3()coend進(jìn)程的同步p1(){while(1){從磁盤讀文件；P(m1)；

放入緩沖1；V(m2)；}}p2(){while(1){P(m2)；

從緩沖1取文件；V(m1)；P(m3);

放入緩沖2；V(m4)；}}p3(){while(1){P(m4)；從緩沖2取文件；V(m3)；打印文件；}}思考：1.緩沖1可以存放n個(gè)文件，緩沖2可以存放m個(gè)文件，如何修改同步關(guān)系？2.如果P2改為如下形式，會(huì)有何影響？intm1=n,m2=0,m3=m,m4=0；P(m2)；P(m3);從緩沖1取文件；放入緩沖2；V(m1)；V(m4)；進(jìn)程的并發(fā)性不如修改前分析：P1做完，P2才能做，P2做完，P3才能做。這三個(gè)進(jìn)程是一個(gè)同步關(guān)系。解法二：設(shè)信號(hào)量m1表示P1是否把文件放入緩沖1，m2表示P2是否從緩沖1取完文件，m3表示P2是否把文件放入緩沖2，m4表示P3是否從緩沖2取完文件。intm1=0,m2=1,m3=0,m4=1；cobeginp1()//p2()//p3()coend進(jìn)程的同步p1(){while(1){從磁盤讀文件；P(m2)；

放入緩沖1；V(m1)；}}p2(){while(1){P(m1)；

從緩沖1取文件；V(m2)；P(m4);

放入緩沖2；V(m3)；}}p3(){while(1){P(m3)；從緩沖2取文件；V(m4)；打印文件；}}小結(jié)進(jìn)程同步有一定的時(shí)序關(guān)系。信號(hào)量表示進(jìn)程的關(guān)鍵工作是否可以開始或已經(jīng)結(jié)束。信號(hào)量的個(gè)數(shù)與進(jìn)程的個(gè)數(shù)一致，有時(shí)可以省略局部信號(hào)量。對同一個(gè)信號(hào)量的PV操作不在一個(gè)進(jìn)程中。表示開始：P自己，V別人表示結(jié)束：P別人，V自己進(jìn)程的同步進(jìn)程互斥進(jìn)程互斥：并發(fā)進(jìn)程之間相互競爭臨界資源的排他性關(guān)系。解題步驟：確定臨界資源及個(gè)數(shù)；確定進(jìn)程的關(guān)鍵工作步〔使用臨界資源的〕；確定信號(hào)量的初值；寫出偽代碼。例1：過獨(dú)木橋。進(jìn)程的互斥P1P2{{由西向東過獨(dú)木橋；由東向西過獨(dú)木橋；}}P1P2分析：進(jìn)程P1、P2因競爭獨(dú)木橋這個(gè)資源而成為互斥關(guān)系。設(shè)：信號(hào)量m表示獨(dú)木橋資源，初值為1表示資源可用。intm=1;cobeginp1()//p2()coend進(jìn)程的互斥p1(){P(m)；

通過獨(dú)木橋；V(m)；}p2(){P(m)；

通過獨(dú)木橋；V(m)；}練習(xí)：過十字路口〔單道〕。進(jìn)程的互斥P1P2P3P4{{{{通過路口；通過路口；通過路口；通過路口；}}}}P2P3P4P1分析：進(jìn)程P1、P2、P3、P4因競爭十字路口這個(gè)資源而成為互斥關(guān)系。設(shè)：信號(hào)量m表示十字路口資源，初值為1表示資源可用。intm=1;cobeginp1()//p2()//p3()//p4()coend進(jìn)程的互斥p1(){P(m)；

通過路口；V(m)；}p2(){P(m)；

通過路口；V(m)；}p3(){P(m)；

通過路口；V(m)；}p4(){P(m)；

通過路口；V(m)；}練習(xí)2：過十字路口〔雙道〕。進(jìn)程的互斥P1P2P3P4{{{{通過路口；通過路口；通過路口；通過路口；}}}}P1P2P3P4例2：讀寫數(shù)據(jù)庫。某數(shù)據(jù)庫有一個(gè)寫進(jìn)程、多個(gè)讀進(jìn)程，它們之間讀、寫操作的互斥要求是：寫進(jìn)程運(yùn)行時(shí)，其他讀、寫進(jìn)程不能對數(shù)據(jù)庫進(jìn)行操作。讀進(jìn)程之間不互斥，可以同時(shí)讀數(shù)據(jù)庫。請用信號(hào)量及PV操作描述這一組進(jìn)程的工作過程。〔讀者-寫者問題〕進(jìn)程的互斥數(shù)據(jù)庫寫者讀者寫者讀者{{寫數(shù)據(jù)庫；讀數(shù)據(jù)庫；}}分析：寫進(jìn)程writer、讀進(jìn)程reader因競爭數(shù)據(jù)庫這個(gè)資源而成為互斥關(guān)系。因?yàn)閷戇M(jìn)程執(zhí)行時(shí)，不能執(zhí)行其他讀寫進(jìn)程，所以還必須設(shè)置一個(gè)計(jì)數(shù)器統(tǒng)計(jì)讀進(jìn)程的個(gè)數(shù)。如果是第一個(gè)讀進(jìn)程，就與寫進(jìn)程競爭數(shù)據(jù)庫。如果是最后一個(gè)讀進(jìn)程，就釋放數(shù)據(jù)庫。因計(jì)數(shù)器是一個(gè)臨界資源，所以多個(gè)讀進(jìn)程對計(jì)數(shù)器的操作又是互斥操作。

設(shè)：信號(hào)量rmutex表示數(shù)據(jù)庫資源，初值為1表示資源可用；wmutex表示計(jì)數(shù)器count資源，初值為1表示可用。intrmutex=1，wmutex=1;cobeginreader()//writer()coend進(jìn)程的互斥思考：只要有讀進(jìn)程時(shí)，寫進(jìn)程就不能開始，如何改變使寫進(jìn)程之后的讀進(jìn)程在寫進(jìn)程之后執(zhí)行？例3：哲學(xué)家就餐問題。有4位哲學(xué)家圍著一個(gè)圓桌在討論問題和進(jìn)餐，在討論時(shí)每人手中什么都不拿，當(dāng)需要進(jìn)餐時(shí)，每人需要用刀和叉各一把。餐桌上的布置如下圖，共有兩把刀和兩把叉，每把刀或叉供相鄰的兩個(gè)人使用。請用信號(hào)量及PV操作說明4位哲學(xué)家的同步過程。進(jìn)程的互斥哲學(xué)家{

進(jìn)餐；討論問題；}分析：進(jìn)程pa、pb、pc、pd因競爭刀和叉而成為互斥關(guān)系。設(shè)：4個(gè)互斥信號(hào)量fork1，fork2，knife1，knife2，其初值均為“1〞，分別表示叉1、叉2、刀1、刀2是可用的。其工作流程如下圖。intfork1=fork2=knife1=knife2=1;cobeginpa()//pb()//pc()//pd()coend進(jìn)程的互斥pa(){

while(1){P(knife1);P(fork1);

進(jìn)餐;V(knife1);V(fork1);討論問題;}}pb(){

while(1){

P(fork1);P(knife2);進(jìn)餐;V(knife2);V(fork1);討論問題;}}pc(){

while(1){P(knife2);P(fork2);進(jìn)餐;V(knife2);V(fork2);討論問題;}}pd(){

while(1){P(fork2);P(knife1);進(jìn)餐；V(knife1);V(fork2);討論問題;}}思考：四位哲學(xué)家同時(shí)拿起右手的餐具，再拿左手的餐具，會(huì)出現(xiàn)什么問題？P(knife1);P(fork2);P(knife2);P(fork1);例4：連續(xù)過獨(dú)木橋。在南開大學(xué)和天津大學(xué)之間有一條彎曲的小路，其中從S到T有一段路每次只允許一輛自行車通過。但是，其中有一個(gè)小的平安島M〔同時(shí)允許兩輛自行車停留〕，可以供兩輛自行車錯(cuò)車時(shí)使用，如下圖。試設(shè)計(jì)一個(gè)算法以確保來往自行車的順利通過。進(jìn)程的互斥tonan{通過TL；上平安島M；通過KS;}totian{通過KS;上平安島M；通過TL；}分析：此圖可以簡化為：在此題中，需要控制路段T到L，S到K及平安島M的使用。路段T到L，S到K都只允許一輛自行車通過，而平安島允許兩輛自行車使用，兩個(gè)路段和平安島相當(dāng)于臨界資源。通過該路段的兩個(gè)進(jìn)程沒有必然的先后次序，因此，此題屬于互斥問題。另外，為了保證平安島上最多有兩輛自行車，需要對相向行駛的兩個(gè)方向進(jìn)行控制，在每個(gè)方向上一次只允許一輛自行車通過。設(shè)：5個(gè)信號(hào)量ST、TS、K、L、M，ST表示是否允許自行車從南大到天大，TS表示是否允許自行車從天大到南大，K表示是否允許自行車通過路段SK，L表示是否允許自行車通過路段TL，M表示平安島上還可以停放自行車的數(shù)目。其工作流程如下圖。intfork1=fork2=knife1=knife2=1;cobegintotian()//tonan()coend進(jìn)程的互斥思考：在totian()中，P(ST)與P(K)互換位置，會(huì)對進(jìn)程產(chǎn)生什么影響？假設(shè)P(M)與V(K)，P(L)與V(M)，V(L)與V(ST)互換位置呢？小結(jié)進(jìn)程互斥：進(jìn)程之間要競爭臨界資源。信號(hào)量表示臨界資源是否可用，或臨界資源的數(shù)量。信號(hào)量的個(gè)數(shù)與臨界資源的個(gè)數(shù)一致。對同一個(gè)信號(hào)量的PV操作要在同一個(gè)進(jìn)程中完成。P操作：進(jìn)入臨界區(qū)前V操作：離開臨界區(qū)后進(jìn)程的互斥進(jìn)程的同步與互斥解題步驟：確定各個(gè)進(jìn)程的工作步；確定進(jìn)程的哪些工作是同步關(guān)系，哪些工作是互斥關(guān)系；同步：有時(shí)序關(guān)系的互斥：競爭臨界資源的確定信號(hào)量含義及初值；寫出偽代碼。例1：讀寫環(huán)形緩沖區(qū)。設(shè)有一個(gè)具有N個(gè)信息元素的環(huán)形緩沖區(qū)〔如下圖〕，A進(jìn)程順序地把信息寫進(jìn)緩沖區(qū)，B進(jìn)程依次從緩沖區(qū)中讀出信息，請用PV操作描述A、B進(jìn)程的同步?！采a(chǎn)者-消費(fèi)者問題〕進(jìn)程的同步與互斥進(jìn)程A{寫數(shù)據(jù)；}進(jìn)程B{讀數(shù)據(jù)；}分析：這是一個(gè)具有多個(gè)緩沖空間的生產(chǎn)者消費(fèi)者問題，也是一個(gè)同步加互斥的問題。A、B兩個(gè)進(jìn)程對緩沖區(qū)的訪問必須互斥。并且當(dāng)緩沖區(qū)滿時(shí)，A進(jìn)程不能寫入，必須等待；當(dāng)緩沖區(qū)空時(shí)，B進(jìn)程不能讀，必須等待，讀寫進(jìn)程之間又是同步問題。設(shè)：3個(gè)信號(hào)量：互斥信號(hào)量S=1〔表示對緩沖區(qū)的互斥使用〕；同步信號(hào)量Sw〔代表緩沖區(qū)是否有空閑，即寫進(jìn)程能否寫〕、Sr〔代表緩沖區(qū)是否有數(shù)據(jù)，即讀進(jìn)程能否讀〕，假設(shè)初始時(shí)緩沖區(qū)沒有任何數(shù)據(jù)，那么Sw=N，Sr=0。設(shè)一個(gè)數(shù)組array表示緩沖區(qū)，兩個(gè)整型變量in、out表示寫入和讀出的位置。其工作流程如下圖。#defineN10;intarray[N]，in=0，out=0;intS=1，Sw=N，Sr=0;cobeginPA()//PB()coend進(jìn)程的同步與互斥例2：理發(fā)師理發(fā)。理發(fā)師理發(fā)問題。有一個(gè)理發(fā)師、一把理發(fā)椅和n把等候理發(fā)顧客坐的椅子。如果沒有顧客，那么理發(fā)師在理發(fā)椅上睡覺；當(dāng)一個(gè)顧客到來時(shí)，必須喚醒理發(fā)師，進(jìn)行理發(fā)；當(dāng)理發(fā)師正在理發(fā)，又有顧客來到時(shí)，如果有空椅子，顧客就可以坐下來等候，如果沒有空椅子，他就離開。請為理發(fā)師和顧客各編一個(gè)程序表述他們的行為。進(jìn)程的同步與互斥barber

{給顧客理發(fā)；}customer

{坐下等候；理發(fā)；}分析：此題涉及兩個(gè)進(jìn)程：理發(fā)師和顧客。當(dāng)有顧客時(shí)理發(fā)師就可以理發(fā)，理完發(fā)后，從等候的顧客中選一位顧客繼續(xù)理發(fā)。當(dāng)理發(fā)師正在理發(fā)時(shí)，顧客要等待，假設(shè)沒有座位就離開，顧客與理發(fā)師的工作是同步關(guān)系。有多少顧客在等候，需設(shè)計(jì)一個(gè)計(jì)數(shù)器來記錄，顧客和理發(fā)師對計(jì)數(shù)器的操作是互斥的。所以，這是一個(gè)同步加互斥的問題。設(shè)：3個(gè)信號(hào)量：S1表示理發(fā)師是否可以開始理發(fā)，即是否有顧客；S2表示顧客是否可以被理發(fā)，即是否有理發(fā)師；S3是對計(jì)數(shù)器waiting的互斥操作；waiting表示等待顧客的人數(shù)。其工作流程如下圖。#defineCHAIR10;intS1=0，S2=0，S3=1，waiting=0;cobeginbarber()//customer()coend進(jìn)程的同步與互斥例3：單行隧道問題。對一個(gè)單行的隧道進(jìn)行模擬，為了防止死鎖，必須防止汽車同時(shí)從兩端進(jìn)入隧道。如果一次只允許一輛車通過隧道，兩個(gè)方向按車輛到達(dá)的先后順序依次通過，請用pv操作設(shè)計(jì)一個(gè)算法實(shí)現(xiàn)這個(gè)控制。進(jìn)程同步與互斥的綜合例題P1()

{通過隧道；}P2()

{通過隧道；}分析：此題涉及兩個(gè)進(jìn)程：P1和P2。隧道是一個(gè)臨界資源，一次只能被一輛車占有，可以把它看作互斥問題。設(shè)：一個(gè)互斥信號(hào)量sd=1，表示隧道是否可用。intsd=1;cobeginP1()//P2()coend進(jìn)程同步與互斥的綜合例題P1()

{P(sd);通過隧道；V(sd);}P2()

{P(sd);通過隧道；V(sd);}問題：兩個(gè)方向車輛通過隧道的交換比較平凡，系統(tǒng)效率不高分析：為了提高效率，把問題改為：一旦一輛車進(jìn)入，那么同一方向的車可以立即跟進(jìn)。寫出用信號(hào)量解決此問題的代碼，不考慮“饑餓〞的情況。(按照讀者-寫者問題處理)設(shè)：3個(gè)信號(hào)量：c表示計(jì)數(shù)器，m表示對臨界資源計(jì)數(shù)器的控制，sd表示對臨界資源隧道的控制，即隧道是否可用。intc=0,m=1,sd=1;cobeginP1()//P2()coend進(jìn)程同步與互斥的綜合例題P2()

{P(sd);通過隧道；V(sd);}P1(){ P(m);/*m1控制計(jì)數(shù)器c1*/ if(c==0)P(sd);/*p1第一輛車通過時(shí)占有隧道*/ c=c+1; V(m); 通過隧道； P(m); c=c-1; if(c==0)V(sd);/*p1最后一輛車通過后釋放隧道*/ V(m);}問題：假設(shè)P1過隧道，那么后續(xù)車輛可以跟進(jìn)；假設(shè)p2過隧道，一次只能過一輛；P1不會(huì)產(chǎn)生“饑餓〞的現(xiàn)象，而p2會(huì)產(chǎn)生“饑餓〞的現(xiàn)象。分析：解決p2“饑餓〞現(xiàn)象的方法：再設(shè)一個(gè)信號(hào)量k，讓p1、p2排隊(duì)，可以做到p1方向比p2方向晚來的車輛被k阻止。intc=0,m=1,sd=1,k=1;cobeginP1()//P2()coend進(jìn)程同步與互斥的綜合例題P2()

{

P(k);P(sd);通過隧道；V(sd);

V(k);}P1(){ P(k);

/*與P2一起排隊(duì)*/P(m);/*m1控制計(jì)數(shù)器c*/ if(c==0)P(sd);/*P1第一輛車通過時(shí)占有隧道*/ c=c+1; V(m);

V(k); 通過隧道； P(m); c=c-1; if(c==0)V(sd);/*P1最后一輛車通過后釋放隧道*/ V(m);}問題：假設(shè)P1過隧道，那么后續(xù)車輛可以跟進(jìn)；假設(shè)p2過隧道，一次只能過一輛。分析：解決p2可以過多輛車的方法：按照讀者-讀者問題處理。即：p1為讀者，p2為讀者，但兩個(gè)讀者不能同時(shí)讀

。int

c1=c2=0,m1=m2=1,sd=1;

//c1、c2為計(jì)數(shù)器，m1、m2為互斥信號(hào)量cobeginP1()//P2()coend進(jìn)程同步與互斥的綜合例題P1(){ P(m1); if(c1==0)P(sd); c1=c1+1; V(m1); 通過隧道； P(m1); c1=c1-1; if(c1==0)V(sd); V(m1);}問題：假設(shè)P1過隧道，那么后續(xù)車輛可以跟進(jìn)，有可能使p2“饑餓〞假設(shè)P2過隧道，那么后續(xù)車輛也可以跟進(jìn)，有可能使p1“饑餓〞P2(){ P(m2); if(c2==0)P(sd); c2=c2+1; V(m2); 通過隧道； P(m2); c2=c2-1; if(c2==0)V(sd); V(m2);}假設(shè)：問題改為：一旦一輛車進(jìn)入，那么同一方向的車可以立即跟進(jìn)，隧道最多只能過4輛車，如何修改算法？intc1=c2=0,m1=m2=1,sd=1,k1=4,k2=4;//c1、c2為計(jì)數(shù)器，m1、m2為互斥信號(hào)量cobegin//k1、k2為控制各自方向上通過的車輛數(shù)P1()//P2()coend進(jìn)程同步與互斥的綜合例題P1(){ P(k1);P(m1); if(c1==0)P(sd); c1=c1+1; V(m1); 通過隧道； P(m1); c1=c1-1; if(c1==0)V(sd); V(m1);

V(k1);}問題：是p1優(yōu)先或p2優(yōu)先的方法。p1后續(xù)車輛可以跟進(jìn)，p2后續(xù)車輛也能跟進(jìn)。P1會(huì)產(chǎn)生“饑餓〞的現(xiàn)象，p2也會(huì)產(chǎn)生“饑餓〞的現(xiàn)象。P2(){ P(k2);P(m2); if(c2==0)P(sd); c2=c2+1; V(m2); 通過隧道； P(m2); c2=c2-1; if(c2==0)V(sd); V(m2);

V(k2);}解決p1、p2“饑餓〞現(xiàn)象的方法是：一方每過n〔如4〕輛車后，就允許對方也過n輛車。intc1=c2=0,m1=m2=1,sd=1,k1=4,k2=4,n1=0,n2=0;//n1、n2為計(jì)數(shù)器cobegin//k1、k2為控制各自方向上通過的車輛數(shù)P1()//P2()coend進(jìn)程同步與互斥的綜合例題P1(){ P(k1);P(m1); if(c1==0)P(sd); c1++;n1++; V(m1); 通過隧道； P(m1); c1=c1-1; if(c1==0){V(sd);//讓本方向再過4車

for(i=1;i<=n1;i++)V(k1);n1=0;} V(m1);V(k1);}P2(){ P(k2);P(m2); if(c2==0)P(sd); c2++;n2++; V(m2); 通過隧道； P(m2); c2=c2-1; if(c2==0){V(sd);//讓本方向再過4車

for(i=1;i<=n2;i++)V(k2);n2=0;} V(m2);V(k2);}使用PV操作的規(guī)那么：①分清哪些是互斥問題〔互斥訪問臨界資源的〕，哪些是同步問題〔具有前后執(zhí)行順序要求的〕。②對于互斥問題要設(shè)置互斥信號(hào)量，不管有互斥關(guān)系的進(jìn)程有幾個(gè)或幾類，互斥信號(hào)量的個(gè)數(shù)只與臨界資源的種類有關(guān)。通常，有幾類臨界資源就設(shè)置幾個(gè)互斥信號(hào)量，且初值為1，代表臨界資源可用。③對于同步問題要設(shè)置同步信號(hào)量，通常同步信號(hào)量的個(gè)數(shù)與參與同步的進(jìn)程種類有關(guān)，即同步關(guān)系涉及幾類進(jìn)程，就有幾個(gè)同步信號(hào)量。同步信號(hào)量表示該進(jìn)程是否可以開始或該進(jìn)程是否已經(jīng)結(jié)束。④在每個(gè)進(jìn)程中用于實(shí)現(xiàn)互斥的PV操作必須成對出現(xiàn)；用于實(shí)現(xiàn)同步的PV操作也必須成對出現(xiàn)，但是，它們分別出現(xiàn)在不同的進(jìn)程中；在某個(gè)進(jìn)程中如果同時(shí)存在互斥與同步的P操作，那么其順序不能顛倒。必須先執(zhí)行對同步信號(hào)量的P操作，再執(zhí)行對互斥信號(hào)量的P操作。但是，V操作的順序沒有嚴(yán)格要求。進(jìn)程的同步與互斥管程進(jìn)程的缺乏：每個(gè)訪問臨界資源的進(jìn)程都必須使用PV操作，使得大量的同步操作分散在各個(gè)進(jìn)程中。這不僅給系統(tǒng)的管理帶來了麻煩，還可能因同步操作使用不當(dāng)而導(dǎo)致系統(tǒng)故障，如順序不當(dāng)、誤寫、漏寫等。管程的引入：1971年，Dijkstra提出，把所有進(jìn)程中對某一種臨界資源的同步操作都集中起來，構(gòu)成一個(gè)所謂的“秘書〞進(jìn)程，但凡訪問該臨界資源的進(jìn)程，都需要先報(bào)告“秘書〞，由“秘書〞來實(shí)現(xiàn)進(jìn)程的同步。1973年，Hansan和Hoare又把“秘書〞進(jìn)程思想開展為管程的概念。概念一個(gè)管程實(shí)際上是定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和在該數(shù)據(jù)結(jié)構(gòu)上的能為并發(fā)進(jìn)程所執(zhí)行的一組操作。與信號(hào)量的區(qū)別信號(hào)量機(jī)制是基于進(jìn)程控制來分配和使用資源的。管程是基于資源控制來協(xié)調(diào)訪問資源的進(jìn)程的。管程的組成局部于管程的共享變量說明對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。此外，每個(gè)管程都有惟一的名字來標(biāo)識(shí)。管程類似于面向?qū)ο蟪绦蛟O(shè)計(jì)中的類。

管程利用管程實(shí)現(xiàn)同步操作利用管程實(shí)現(xiàn)同步，必須設(shè)置兩個(gè)同步操作原語：〔1〕wait原語：當(dāng)某進(jìn)程通過管程請求獲得臨界資源而未得到滿足時(shí)，管程調(diào)用該原語使該進(jìn)程阻塞，并將它排在該臨界資源的阻塞隊(duì)列上?！?〕signal原語：僅當(dāng)一個(gè)進(jìn)程訪問完成并釋放臨界資源時(shí)，管程才能調(diào)用該原語，喚醒阻塞隊(duì)列上的隊(duì)首進(jìn)程。為了區(qū)別阻塞的原因，需要設(shè)置一個(gè)條件變量。條件變量是一個(gè)整型變量，用condition說明，在條件變量上可以使用wait和signal操作原語。管程定義的一般格式為：monitor管程類名/*monitor是關(guān)鍵詞*/{ 共享變量說明； 條件變量說明； 過程定義；/*一般有多個(gè)*/}管程例1：讀寫環(huán)形緩沖區(qū)。設(shè)有一個(gè)具有N個(gè)信息元素的環(huán)形緩沖區(qū)〔如下圖〕，A進(jìn)程順序地把信息寫進(jìn)緩沖區(qū)，B進(jìn)程依次從緩沖區(qū)中讀出信息，請用PV操作描述A、B進(jìn)程的同步?！采a(chǎn)者-消費(fèi)者問題〕管程進(jìn)程A{寫數(shù)據(jù)；}進(jìn)程B{讀數(shù)據(jù)；}分析：設(shè)in,out,count,buffer[]為共享變量：buffer[]為緩沖區(qū)，即生產(chǎn)者和消費(fèi)者的共享資源。count為緩沖區(qū)產(chǎn)品的數(shù)量。in指示生產(chǎn)者存放產(chǎn)品的位置。out指示消費(fèi)者取產(chǎn)品的位置。full,empty為條件變量：full表示當(dāng)緩沖區(qū)產(chǎn)品放滿時(shí)，生產(chǎn)者排隊(duì)。empty表示當(dāng)緩沖區(qū)無產(chǎn)品時(shí)，消費(fèi)者排隊(duì)。put()，get()為兩個(gè)對緩沖區(qū)的操作過程：其中put()表示把產(chǎn)品放入緩沖區(qū)。get()表示從緩沖區(qū)取產(chǎn)品。管程#defineN10monitorproducer_consumer/*定義生產(chǎn)者-消費(fèi)者管程*/{ intin=0,out=0,count=0,buffer[N]; conditioanfull,empty; put(intitem) { if(count>=N) full.wait;/*當(dāng)緩沖區(qū)滿時(shí)排隊(duì)*/ buffer[in]=item; in=(in+1)%N; count++; empty.signal;/*喚醒消費(fèi)者等待隊(duì)列中的進(jìn)程*/}

get(intitem){ if(count<=0) empty.wait;/*當(dāng)緩沖區(qū)空時(shí)排隊(duì)*/ item=buffer[out]; out=(out+1)%N; count--; full.signal;/*喚醒生產(chǎn)者等待隊(duì)列中的進(jìn)程*/}}管程生產(chǎn)者—消費(fèi)者描述為：intitem;/*產(chǎn)品*/monitorproducer_consumerpc；/*pc為一個(gè)具體的生產(chǎn)者-消費(fèi)者管程*/cobeginproducer()/*生產(chǎn)者*/{ while(1) { 生產(chǎn)一個(gè)產(chǎn)品item; pc.put(item);/*調(diào)用管程中的過程，存放產(chǎn)品*/}}//consumer()/*消費(fèi)者*/{ while(1) { pc.get(item);/*調(diào)用管程中的過程，取產(chǎn)品*/ 消費(fèi)產(chǎn)品item;}}coend管程例2：讀寫數(shù)據(jù)庫。某數(shù)據(jù)庫有一個(gè)寫進(jìn)程、多個(gè)讀進(jìn)程，它們之間讀、寫操作的互斥要求是：寫進(jìn)程運(yùn)行時(shí)，其他讀、寫進(jìn)程不能對數(shù)據(jù)庫進(jìn)行操作。讀進(jìn)程之間不互斥，可以同時(shí)讀數(shù)據(jù)庫。請用管程機(jī)制描述這一組進(jìn)程的工作過程。

管程數(shù)據(jù)庫寫者讀者寫者讀者{{寫數(shù)據(jù)庫；讀數(shù)據(jù)庫；}}分析：設(shè)read_cnt,writing為共享變量：read_cnt為當(dāng)前讀資源進(jìn)程的數(shù)目。Writing為是否有寫者正在使用這個(gè)資源。read,write為條件變量：read為讀者等待隊(duì)列。write為寫者等待隊(duì)列。操作過程：start_read()為開始讀過程。end_read()為結(jié)束讀過程。start_write()為開始寫過程。end_write()為結(jié)束寫過程。管程管程描述如下：monitorreders_writers{intread_cnt=0;/*當(dāng)前讀資源進(jìn)程的數(shù)目*/intwriting=0;/*是否有寫者正在使用這個(gè)資源*/conditionread,write;/*讀者等待隊(duì)列，寫者等待隊(duì)列*/start_read()/*開始讀過程*/{if(writing||!empty(write))read.wait;/*如果正在寫或者有寫者進(jìn)程就阻塞讀進(jìn)程*/read_cnt++; read.signal;/*喚醒一個(gè)讀進(jìn)程*/}end_read()/*結(jié)束讀過程*/{ read_cnt=read_cnt-1;