經(jīng)典進(jìn)程同步問題

1、1 在多道程序環(huán)境下，進(jìn)程同步問題是十在多道程序環(huán)境下，進(jìn)程同步問題是十分重要的，也是相當(dāng)有趣的問題，因而吸引分重要的，也是相當(dāng)有趣的問題，因而吸引了不少學(xué)者對它進(jìn)行研究。了不少學(xué)者對它進(jìn)行研究。 其中較有代表性的是其中較有代表性的是“生產(chǎn)者生產(chǎn)者消費(fèi)消費(fèi)者問題者問題”、“讀者讀者寫者問題寫者問題”、“哲學(xué)哲學(xué)家進(jìn)餐問題家進(jìn)餐問題”等。等。2問題的描述：問題的描述：3需要解決的問題：需要解決的問題：1、對緩沖池的互斥訪問，即只有一個進(jìn)、對緩沖池的互斥訪問，即只有一個進(jìn)程訪問緩沖區(qū)。程訪問緩沖區(qū)。2、對生產(chǎn)、消費(fèi)進(jìn)程的同步，即：有產(chǎn)、對生產(chǎn)、消費(fèi)進(jìn)程的同步，即：有產(chǎn)品時才能消費(fèi)，無產(chǎn)品時，必須先

2、生產(chǎn)后品時才能消費(fèi)，無產(chǎn)品時，必須先生產(chǎn)后消費(fèi)；有空間時才能生產(chǎn)，空間滿時，必消費(fèi)；有空間時才能生產(chǎn)，空間滿時，必須先消費(fèi)再生產(chǎn)。須先消費(fèi)再生產(chǎn)。4信號量的設(shè)置：信號量的設(shè)置：1、一個互斥信號量、一個互斥信號量mutex，用于實(shí)現(xiàn)對共，用于實(shí)現(xiàn)對共享緩沖區(qū)的互斥訪問，初始值為享緩沖區(qū)的互斥訪問，初始值為1。2、兩個同步信號量，分別表示可用資源數(shù)：、兩個同步信號量，分別表示可用資源數(shù)：Empty：表示空緩沖區(qū)的個數(shù)，初始值為：表示空緩沖區(qū)的個數(shù)，初始值為nFull：表示裝有消息的緩沖區(qū)的個數(shù)，初：表示裝有消息的緩沖區(qū)的個數(shù)，初始值為始值為0，（一個緩沖區(qū)中放一條消息），（一個緩沖區(qū)中放一條消息）

3、5一、利用記錄型信號量一、利用記錄型信號量解決生產(chǎn)者解決生產(chǎn)者消費(fèi)者問題消費(fèi)者問題數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)：Var mutex, empty, full：semaphore =1，n，0； /定義信號量并賦初值定義信號量并賦初值 buffer：array0, , n-1 of item; /定義緩沖區(qū)定義緩沖區(qū) in, out: integer =0, 0; /定義存取指針的初始位置定義存取指針的初始位置6Proceduer： /生產(chǎn)者進(jìn)程生產(chǎn)者進(jìn)程begin repeat 生產(chǎn)一件產(chǎn)品生產(chǎn)一件產(chǎn)品; wait(empty); wait(mutex); bufferin:=nextp; in =(i

4、n+1) mod n; signal(mutex); signal(full); until false;endempty:=empty-1;if empty 0 then block;mutex:=mutex-1;if mutex 0 then block;full:=full + 1;if full =0 then wakeup;mutex:=mutex+1;if mutex =0 then wakeup;7consumer：/消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程begin repeat wait(full); wait(mutex); nextc:=bufferout; out =(out+1) mod

5、 n; signal(mutex); signal(empty); 消費(fèi)這件產(chǎn)品消費(fèi)這件產(chǎn)品; until false;end full:=full - 1;if full 0 then block;mutex:=mutex-1;if mutex0 then block;empty:=empty+1;if empty=0 then wakeup;mutex:=mutex+1;if mutex=1 and mutex=1 then empty:=empty-1;mutex:=mutex-1;mutex:=mutex+1;full:=full + 1;13consumer：/消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程b

6、egin repeat Swait(full，mutex); nextc:=bufferout; out =(out+1) mod n; Ssignal(mutex，empty); 消費(fèi)這件產(chǎn)品消費(fèi)這件產(chǎn)品; until false;end if full =1 and mutex=1 then full:=full - 1; mutex:=mutex-1;mutex:=mutex+1;empty:=empty+1;143利用管程解決生產(chǎn)者利用管程解決生產(chǎn)者消費(fèi)者問題消費(fèi)者問題 在利用管程方法來解決生產(chǎn)者在利用管程方法來解決生產(chǎn)者消費(fèi)者問題時，消費(fèi)者問題時，首 先 便 是 為 它 們 建 立

7、一 個 管 程 ， 并 命 名 為首 先 便 是 為 它 們 建 立 一 個 管 程 ， 并 命 名 為ProclucerConsumer，或簡稱為，或簡稱為PC。其中包括兩個。其中包括兩個過程：過程：(1) put(item)過程。生產(chǎn)者利用該過程將自己生過程。生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中，并用整型變量產(chǎn)的產(chǎn)品投放到緩沖池中，并用整型變量count來表來表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)countn時，表示時，表示緩沖池已滿，生產(chǎn)者須等待。緩沖池已滿，生產(chǎn)者須等待。(2) get(item)過程。消費(fèi)者利用該過程從緩沖池過程。消費(fèi)者利用該過程從緩

8、沖池中取出一個產(chǎn)品，當(dāng)中取出一個產(chǎn)品，當(dāng)count0時，表示緩沖池中已無時，表示緩沖池中已無可取用的產(chǎn)品，消費(fèi)者應(yīng)等待?？扇∮玫漠a(chǎn)品，消費(fèi)者應(yīng)等待。 15PC管程可描述如下：管程可描述如下：type producer-consumer=monitorVar in,out,count: integer；buffer: array0, , n-1 of item；notfull，notempty:condition；procedure entry put(item)beginif count=n then notfull.wait；buffer(in):=nextp；in:=(in+1) mod

9、n；count:=count+1；if notempty.queue then notempty.signal；end 16procedure entry get(item)beginif count=1 then L :=L - 1;if mx =1 then mx :=mx - 0; /即即mx值不變值不變L :=L + 1;35writer: repeatSwait(mx,1,1;L,RN,0);writing operation; Ssignal(mx,1); until false ;if mx =1 and L =RN then mx:=mx - 1; L:=L-0;/即在讀進(jìn)程數(shù)

10、不變即在讀進(jìn)程數(shù)不變mx :=mx + 1;36 Swait(mx,1,0) Swait(mx,1,0)語句起著開關(guān)的作用。語句起著開關(guān)的作用。只要無只要無writerwriter進(jìn)程進(jìn)入寫，則進(jìn)程進(jìn)入寫，則mxmx=1=1，readerreader進(jìn)程就都可以進(jìn)入讀。一旦有進(jìn)程就都可以進(jìn)入讀。一旦有writerwriter進(jìn)程進(jìn)進(jìn)程進(jìn)入寫時，入寫時，mxmx=0=0，則任何，則任何readerreader進(jìn)程就都無法進(jìn)程就都無法進(jìn)入讀。進(jìn)入讀。 Swait(mx,1,1,L,RN,0)Swait(mx,1,1,L,RN,0)語句表示：僅語句表示：僅當(dāng)既是無當(dāng)既是無writerwriter進(jìn)程

11、在寫（進(jìn)程在寫（mxmx=1=1）、又無）、又無 readerreader進(jìn)程在讀（進(jìn)程在讀（L=RNL=RN）時，）時，writerwriter進(jìn)程才進(jìn)程才能進(jìn)入臨界區(qū)寫。能進(jìn)入臨界區(qū)寫。373839數(shù)據(jù)結(jié)構(gòu)：數(shù)據(jù)結(jié)構(gòu)： Var mutex, avail-n, avail-s：semaphore：= 0, m, m;/mutex是互斥信號量，是互斥信號量，用于實(shí)現(xiàn)對共享緩沖區(qū)用于實(shí)現(xiàn)對共享緩沖區(qū)的互斥訪問，初始值為的互斥訪問，初始值為1 /avail-n表示允許向北行的車輛數(shù)，表示允許向北行的車輛數(shù)，初始值為初始值為m/avail-s表示允許向南行的車輛數(shù)，表示允許向南行的車輛數(shù)，初始值為初始值為m40South:Begin