會計學1Chapter進程同步與互斥應用例子解析實用進程互斥進程互斥：并發進程之間相互競爭臨界資源的排他性關系。解題步驟：確定臨界資源及個數；確定進程的關鍵工作步（使用臨界資源的）；確定信號量的初值(臨界資源的個數)；寫出偽代碼。 使用P(wait)操作和V(signal)操作對進程互斥進行控制。第1頁/共29頁例1：過獨木橋。進程的互斥P1P2{{

由西向東過獨木橋；由東向西過獨木橋；}}P1P2第2頁/共29頁分析：進程P1、P2因競爭獨木橋這個資源而成為互斥關系。設：信號量m表示獨木橋資源，初值為1表示資源可用。

intm=1;cobeginp1()//p2()coend進程的互斥p1(){P(m)；

通過獨木橋；

V(m)；}p2(){P(m)；

通過獨木橋；

V(m)；

}第3頁/共29頁練習：過十字路口（單道）。進程的互斥P1P2P3P4{{{{

通過路口；通過路口；通過路口；通過路口；}}}}P2P3P4P1第4頁/共29頁分析：進程P1、P2、P3、P4因競爭十字路口這個資源而成為互斥關系。設：信號量m表示十字路口資源，初值為1表示資源可用。

intm=1;cobeginp1()//p2()//p3()//p4()coend進程的互斥p1(){P(m)；

通過路口；

V(m)；}p2(){P(m)；

通過路口；

V(m)；

}p3(){P(m)；

通過路口；

V(m)；}p4(){P(m)；

通過路口；

V(m)；

}第5頁/共29頁有一個閱覽室，共有100個座位。讀者進入閱覽室時必須在入口處進行登記；離開閱覽室時必須進行注銷。試用PV操作描述讀者進入/離開閱覽室的同步與互斥關系。Reader進程 { 登記進入閱覽室讀書離開閱覽室注銷}進程的互斥第6頁/共29頁分析： 在入口和出口處讀者應該互斥進行登記和注銷，

100個座位，100個互斥資源設置信號量教室內空座位數量，seat，初值100為入口處進行登記設置互斥信號量Sin，初值1，表示當前可用為出口處進行注銷設置互斥信號量Sout，初值1，表示當前可用第7頁/共29頁beginSin,Sout,seat：semaphore;seat:=100; Sin:=1; Sout:=1;cobegin processReader-i(i=1,2,…,n); begin

P(seat); P(Sin);

登記;

V(Sin);

進入閱覽室;

讀書;

離開閱覽室;

P(Sout);

注銷; V(Sout);

V（seat）; endcoend;end;第8頁/共29頁問題若有一售票廳只能容納300人，當少于300人時，可以進入。否則，需在外等候，

若將每一個購票者作為一個進程，請用P、V操作編程。第9頁/共29頁例2：讀寫數據庫。某數據庫有一個寫進程、多個讀進程，它們之間讀、寫操作的互斥要求是：寫進程運行時，其他讀、寫進程不能對數據庫進行操作。讀進程之間不互斥，可以同時讀數據庫。請用信號量及PV操作描述這一組進程的工作過程。（讀者-寫者問題）

進程的互斥數據庫寫者讀者寫者讀者{{

寫數據庫；讀數據庫；}}第10頁/共29頁分析：寫進程writer、讀進程reader因競爭數據庫這個資源而成為互斥關系。因為寫進程執行時，不能執行其他讀寫進程，所以還必須設置一個計數器統計讀進程的個數。如果是第一個讀進程，就與寫進程競爭數據庫。如果是最后一個讀進程，就釋放數據庫。因計數器是一個臨界資源，所以多個讀進程對計數器的操作又是互斥操作。

設：信號量rmutex表示數據庫資源，初值為1表示資源可用；wmutex表示計數器count資源，初值為1表示可用。

intrmutex=1，wmutex=1;cobeginreader()//writer()coend進程的互斥第11頁/共29頁小結進程互斥：進程之間要競爭臨界資源。信號量表示臨界資源是否可用，或臨界資源的數量。信號量的個數與臨界資源的個數一致。對同一個信號量的PV操作要在同一個進程中完成。P操作：進入臨界區前V操作：離開臨界區后進程的互斥第12頁/共29頁進程同步進程同步：并發進程之間相互合作，完成一項工作，它們之間有一定的時序關系。解題步驟：確定進程的個數及每個進程的工作；確定關鍵工作步（需要控制的）；確定信號量表示的含義，當信號量的值為0時，表示期望的消息尚未產生；當信號量的值非0時，表示期望的消息已經存在。

寫出偽代碼。在同步關系的控制中，同一信號量的P(wait)、V(signal)操作成對出現，但它們分別在不同的進程代碼中。

第13頁/共29頁例1：假設有三個并發進程P，Q，R，其中P負責從輸入設備上讀入信息并傳送給Q，Q將信息加工后傳送給R，R則負責將信息打印輸出。進程P、Q共享一個緩沖區，進程Q、R共享另一個緩沖區。進程的同步3個進程P、Q、RP進程：

從輸入設備上讀入信息將信息放入緩沖區1Q進程：從緩沖區1取出信息將信息放入緩沖區2中R進程：從緩沖區2取出信息將信息打印輸出第14頁/共29頁確定進程的同步、互斥關系同步：P當緩存區1無數據時，才可以向緩沖區1寫入信息同步：Q當緩存區1有數據時，才可以從緩沖區1讀取信息同步：Q當緩存區2無數據時，才可以向緩沖區2寫入信息同步：R當緩存區2有數據時，才可以從緩沖區2讀取信息設置信號量緩存區1無數據，empty1，初值1緩存區1有數據，full1，初值0緩存區2無數據，empty2，初值1緩存區2有數據，full2，初值0第15頁/共29頁processP(){while(1){

從輸入設備上讀入信息; P（empty1）;

將信息放入緩沖區1；

V（full1）;}}

processQ(){while(1){ P（full1）;

從緩沖區1取出信息; V（empty1）; P（empty2）;

將信息放入緩沖區2；

V（full2）; }}

processR(){while(1){

P（full2）;

從緩沖區2取出信息; V（empty2）;

將信息打印輸出;

}}

第16頁/共29頁進程的同步例2：公共汽車中的司機和售票員。司機P1售票員P2while(true)while(true){{

啟動車輛；關門；

正常運行；售票；

到站停車；開門；

}}

第17頁/共29頁解法：信號量表示進程能否開始。設信號量m1表示司機進程P1能否啟動汽車，初值為0，m2表示售票員進程p2能否開門，初值為0。intm1=0,m2＝0;cobeginp1()//p2()coend進程的同步p1(){while(1){P(m1);

啟動汽車；正常行駛；到站停車；

V(m2);}}p2(){while(1){

關門；

V(m1);

售票；Ｐ(m2);開門；

}}第18頁/共29頁進程的同步例3-2：吃水果。

父親P1兒子P2女兒P3

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

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

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

}}}

桔子父親兒子女兒0蘋果第19頁/共29頁分析：父親先放水果，兒子女兒再吃水果；兒子女兒取完水果，父親再放水果，這三個進程是一個同步關系。解法：設信號量m1表示父親能否放水果，m2表示兒子能否取桔子，m3表示女兒能否取蘋果。intm1=1,m2=0,m3=0；cobeginp1()//p2()//p3()coend進程的同步p1(){while(1){

洗水果；

P(m1)；

放水果；

if(是桔子)V(m2)；

elseV(m3)；

}}p2(){while(1){P(m2)；

取桔子；

V(m1)；吃桔子；

}}p3(){while(1){P(m3)；

取蘋果；

V(m1)；吃蘋果；

}}第20頁/共29頁進程的同步例3-3：吃水果。

父親P1母親P2兒子P3

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

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

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

}}}

0父親兒子母親桔子蘋果第21頁/共29頁分析：父母親先放水果，兒子再取水果吃；父親與兒子，母親與兒子是一個同步關系，父親與母親要競爭空盤子。解法：設信號量m1表示是否有空盤子，信號量m2表示兒子能否取水果。intm1=1,m2=0；cobeginp1()//p2()//p3()coend進程的同步p1(){while(1){

洗桔子；

P(m1)；

放桔子；

V(m2)；

}}p2(){while(1){

洗蘋果；

P(m1)；放蘋果；

V(m2)；

}}p3(){while(1){P(m2)；

取水果；

V(m1)；吃水果；

}}第22頁/共29頁0進程的同步例3-4：吃水果。

父親P1母親P2兒子P3

女兒P4

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

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

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

桔子父親女兒母親蘋果兒子第23頁/共29頁分析：父母親先放水果，兒子女兒再取水果；父親與女兒，母親與兒子是一個同步關系，父親與母親要競爭空盤子。解法一：設信號量m1表示是否有空盤子，信號量m2表示兒子能否取蘋果，m3表示女兒能否取桔子。intm1=1,m2=0,m3=0；cobeginp1()//p2()//p3()//p4()coend進程的同步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)；吃桔子；

}}第24頁/共29頁問題有一只鐵籠子，每次只能放入一只動物，獵手向籠中放入老虎，農民向籠中放入豬，動物園等待取籠中的老虎，飯店等待取籠中的豬，試用P、V操作