本文地址：http://www.CUOXin.com/archimedes/p/classic-PRocess-synchronization-problems.html，轉(zhuǎn)載請注明源地址。

用信號量機(jī)制實(shí)現(xiàn)進(jìn)程間的同步和互斥，既方便又有效。但存在以下兩個(gè)問題：

• 每個(gè)訪問臨界資源的進(jìn)程都必須自備同步操作（P、V操作），這使大量的同步操作分散在各個(gè)進(jìn)程中，給系統(tǒng)的管理帶來麻煩。

• 會(huì)因同步操作使用不當(dāng)而導(dǎo)致系統(tǒng)死鎖。

解決方法：

管程（Monitors)

Dijkstra于1971年提出：為每個(gè)共享資源設(shè)立一個(gè)“秘書”來管理對它的訪問。 一切來訪者都要通過秘書，而秘書每次僅允許一個(gè)來訪者（進(jìn)程）來訪問共享資源。這樣既便于系統(tǒng)管理共享資源，又能保證進(jìn)程的互斥訪問和同步。1973年，Hanson和Hoare又把“秘書”概念發(fā)展為管程概念。

基本思想

系統(tǒng)中的各種軟硬件資源，其特性都可用數(shù)據(jù)結(jié)構(gòu)抽象地描述，把對該共享數(shù)據(jù)結(jié)構(gòu)實(shí)施的操作定義為一組過程。

進(jìn)程對共享資源的訪問都是通過這組過程對共享數(shù)據(jù)結(jié)構(gòu)的操作來實(shí)現(xiàn)的，這組過程可以根據(jù)資源的使用情況，接受或阻塞進(jìn)程的訪問，確保每次只有一個(gè)進(jìn)程使用共享資源，

實(shí)現(xiàn)進(jìn)程的互斥。

管程的定義

一個(gè)數(shù)據(jù)結(jié)構(gòu)和在該數(shù)據(jù)結(jié)構(gòu)上能被并發(fā)進(jìn)程所執(zhí)行的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。如下圖所示：

管程的結(jié)構(gòu)

TYPE <管程名> = MONITOR

<共享變量說明>;

procedure<過程名>(<形式參數(shù)表>);

begin

<過程體>；

end;

……

procedure <過程名>(<形式參數(shù)表>);

begin

<過程體>；

end;

begin

<管程的局部數(shù)據(jù)初始化語句序列>；

end;

管程相當(dāng)于圍墻，它把共享變量和對它進(jìn)行操作的若干過程圍了起來，所有進(jìn)程要訪問臨界資源時(shí)，都必須經(jīng)過管程才能進(jìn)入，而管程每次只允許一個(gè)進(jìn)程進(jìn)入管程，從而實(shí)現(xiàn)進(jìn)程互斥。

管程的特性

模塊化：是一個(gè)基本程序單位，可單獨(dú)編譯

抽象數(shù)據(jù)類型：管程中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)的操作

信息隱蔽：數(shù)據(jù)結(jié)構(gòu)和過程的具體實(shí)現(xiàn)外部不可見

管程與進(jìn)程作比較

管程定義的是公用數(shù)據(jù)結(jié)構(gòu)，而進(jìn)程定義的是私有數(shù)據(jù)結(jié)構(gòu)PCB；

管程把共享變量上的同步操作集中起來，而臨界區(qū)卻分散在每個(gè)進(jìn)程中；

管程是為管理共享資源而建立的，進(jìn)程主要是為占有系統(tǒng)資源和實(shí)現(xiàn)系統(tǒng)并發(fā)性而引入的；

管程是被要使用共享資源的進(jìn)程所調(diào)用的，管程和調(diào)用它的進(jìn)程不能并發(fā)工作，而進(jìn)程之間能并發(fā)工作，并發(fā)性是進(jìn)程的固有特性；

管程是OS中一個(gè)資源管理模塊，供進(jìn)程調(diào)用；而進(jìn)程有生命周期，由創(chuàng)建而產(chǎn)生、由撤銷而消亡

在多道程序環(huán)境下，進(jìn)程同步問題十分重要，出現(xiàn)一系列經(jīng)典的進(jìn)程同步問題，其中有代表性有：

• 生產(chǎn)者—消費(fèi)者問題

• 哲學(xué)家進(jìn)餐問題

• 讀者—寫者問題

問題描述：

“生產(chǎn)者---消費(fèi)者”問題是最著名的進(jìn)程同步問題。它描述了一組生產(chǎn)者向一組消費(fèi)者提供產(chǎn)品，它們共享一個(gè)緩沖池（有n個(gè)緩沖區(qū)），生產(chǎn)者向其中投放產(chǎn)品，消費(fèi)者從中取得產(chǎn)品。

它是許多相互合作進(jìn)程的抽象，如輸入進(jìn)程與計(jì)算進(jìn)程；計(jì)算進(jìn)程與打印進(jìn)程等。

定義兩個(gè)同步信號量：

empty——表示緩沖區(qū)是否為空，初值為1。

full——表示緩沖區(qū)中是否為滿，初值為0。

//生產(chǎn)者進(jìn)程：while(TRUE){  生產(chǎn)一個(gè)產(chǎn)品;  P(empty);  把產(chǎn)品送往Buffer;  V(full);}//消費(fèi)者進(jìn)程：while(TRUE){  P(full);  從Buffer取出一個(gè)產(chǎn)品;  V(empty);  消費(fèi)產(chǎn)品;}

擴(kuò)展：M個(gè)生產(chǎn)者，K個(gè)消費(fèi)者，公用有n個(gè)緩沖區(qū)的緩沖池

設(shè)緩沖池的長度為n（n>0），一群生產(chǎn)者進(jìn)程P1,P2,…，Pm，一群消費(fèi)者進(jìn)程C1,C2,…，Ck，如圖所示。假定生產(chǎn)者和消費(fèi)者是相互等效，只要緩沖池未滿，生產(chǎn)者就可以把產(chǎn)品送入緩沖區(qū)，類似地，只要緩沖池未空，消費(fèi)者便可以從緩沖區(qū)取走產(chǎn)品并消耗它。生產(chǎn)者和消費(fèi)者的同步關(guān)系將禁止生產(chǎn)者向滿的緩沖池輸送產(chǎn)品，也禁止消費(fèi)者從空的緩沖池提取產(chǎn)品。

empty：說明空緩沖區(qū)的數(shù)目，其初值為緩沖池的大小n，表示消費(fèi)者已把緩沖池中全部產(chǎn)品取走，有n個(gè)空緩沖區(qū)可用。

full：說明滿緩沖區(qū)的數(shù)目（即產(chǎn)品數(shù)目），其初值為0,表示生產(chǎn)者尚未把產(chǎn)品放入緩沖池，有0個(gè)滿緩沖區(qū)可用。

mutex: 說明該緩沖池是一臨界資源，必須互斥使用，其初值為1。

“生產(chǎn)者—消費(fèi)者”問題的同步算法描述：

semaphore  full=0;  /*表示滿緩沖區(qū)的數(shù)目*/semaphore  empty=n;  /*表示空緩沖區(qū)的數(shù)目*/semaphore  mutex=1;  /*表示對緩沖池進(jìn)行操作的互斥信號量*/main(){  cobegin     producer();     consumer();  coend }producer(){  while(true) {        生產(chǎn)一個(gè)產(chǎn)品放入nextp;          P(empty);         P(mutex);         Buffer[in]=nextp;        in=(in+1) mod n;          V(mutex);        V(full);  }}consumer(){  while(true) {     P(full);      P(mutex);      nextc =Buffer[out];      out=(out+1) mod n;     V(mutex);     V(empty);         消費(fèi)nextc中的產(chǎn)品；   }}

“生產(chǎn)者-消費(fèi)者”問題中應(yīng)注意：

1. 互斥信號量的P、V操作在每一進(jìn)程中必須成對出現(xiàn)。

2. 對資源信號量(full,empty)的P、V操作也必須成對出現(xiàn)，但可分別處于不同的程序中。

3. 多個(gè)P操作順序不能顛倒。

4. 先執(zhí)行資源信號量的P操作，再執(zhí)行互斥信號量的P操作，否則可能引起進(jìn)程死鎖。

5. 它是一個(gè)同步問題：

（1）消費(fèi)者想要取產(chǎn)品，緩沖池中至少有一個(gè)緩沖區(qū)是滿的。

（2）生產(chǎn)者想要放產(chǎn)品，緩沖池中至少有一個(gè)緩沖區(qū)是空的。

6. 它是一互斥問題

緩沖池是臨界資源，因此，各生產(chǎn)者進(jìn)程和各消費(fèi)者進(jìn)程必須互斥訪問。

用管程機(jī)制解決生產(chǎn)者—消費(fèi)者問題

1、建立Producer-consumer(PC)管程

   Type PC=monitor    var in,out,count:integer;          buffer:array[0,…,n-1] of item;          notfull,notempty:condition;          put(item);          get(item);     begin          in:=out:=0;       /* 初始化代碼*/          count:=0;     end

管程中的兩個(gè)條件變量：

(1) notfull 表示等待未滿緩沖區(qū)（空緩沖區(qū)）。

(2)notempty 表示等待未空緩沖區(qū)（滿緩沖區(qū)）。

1、建立Producer-consumer(PC)管程

生產(chǎn)者利用此過程將自己生產(chǎn)的產(chǎn)品放到緩沖池中，若發(fā)現(xiàn)緩沖池已滿（count n)，則等待。

消費(fèi)者利用此過程將緩沖池中的產(chǎn)品取走，若發(fā)現(xiàn)緩沖池已空（count 0)，則等待。

put(item)Procedure entry put(item)       begin            if  count >=  n  then                 notfull.wait;            buffer(in):=nextp;            in:=(in+1) mod n;            count:=count+1;            if notempty.queue then                       notempty.signal;       endget(item)Procedure entry get(item)       begin            if  count =  0  then                  notempty.wait;            nextc:=buffer(out);            out:=(out+1) mod n;            count:=count-1;            if notfull.queue then                notfull.signal;       end

2、生產(chǎn)者—消費(fèi)者問題的解決

Producer:begin                   repeat                      produce an item in nextp;                      PC.put(item);                   until false                  endConsumer:begin                    repeat               PC.get(item);                        consume the item in nextc;                     until false                   end

有五個(gè)哲學(xué)家，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。他們共用一張圓桌，分別坐在五張椅子上。在圓桌上有五個(gè)碗和五支筷子，平時(shí)一個(gè)哲學(xué)家進(jìn)行思考，饑餓時(shí)便試圖取用其左、右最靠近他的筷子，只有在他拿到兩支筷子時(shí)才能進(jìn)餐。進(jìn)餐畢，放下筷子又繼續(xù)思考。

哲學(xué)家進(jìn)餐問題的解決:

semaphore  stick[5]={1,1,1,1,1};  /*分別表示5支筷子*/main(){  cobegin     philosopher(0);     philosopher(1);     philosopher(2);     philosopher(3);     philosopher(4);  coend }//第i個(gè)哲學(xué)家的活動(dòng)算法philosopher(int i){  while(true) {    思考;      P(stick[i]);     P(stick[(i+1) mod 5]);     進(jìn)餐；     V(stick[i]);    V(stick[(i+1) mod 5]);  }}

說明：

1、此算法可以保證不會(huì)有相鄰的兩位哲學(xué)家同時(shí)進(jìn)餐。

2、若五位哲學(xué)家同時(shí)饑餓而各自拿起了左邊的筷子，這使五個(gè)信號量stick均為0，當(dāng)他們試圖去拿起右邊的筷子時(shí)，都將因無筷子而無限期地等待下去，即可能會(huì)引起死鎖。

上述解法可能出現(xiàn)永遠(yuǎn)等待，有若干種辦法可避免死鎖：

• 至多允許四個(gè)哲學(xué)家同時(shí)進(jìn)餐（解決方法一）；

• 奇數(shù)號先取左手邊的筷子，偶數(shù)號先取右手邊的筷子（解決方法二）；

• 每個(gè)哲學(xué)家取到手邊的兩把筷子才進(jìn)餐，否則一把筷子也不取（解決方法三）。

解決的方法（一）

   while(true)   {                                             signal(stick[i]);      wait(Sm);                                  signal(stick[(i+1) mod 5]);       wait(stick[i]);                            signal(Sm);      wait (stick[(i+1) mod 5]);                 …...      ……                                         think;      eat;                                       }      …...

解決的方法（二）

    while(true)                                   signal(stick[i]);              {if odd(i)                                      signal (stick[(i+1) mod 5]);       {wait(stick[i]);                           …...                  wait (stick[(i+1) mod 5]);         think;       }                                                …...      else                                           }       {wait (stick[(i+1) mod 5]);               wait(stick[i]);                        }      ……      eat;                                                …...

對5個(gè)哲學(xué)家，假設(shè)規(guī)定：單號者進(jìn)餐時(shí)，先拿左手（i）的筷子，然后再拿右手（i+1）的筷子。雙號則先右后左。這樣既可使5個(gè)人同時(shí)進(jìn)餐，又不致產(chǎn)生死鎖。

利用AND信號量機(jī)制解決哲學(xué)家進(jìn)餐問題

semaphore  stick[5]={1,1,1,1,1};philosopher(int i){     while(true)     {        think;        Swait(stick[(i+1) mod 5],stick[i]);        eat;        Ssignal(stick[(i+1) mod 5],stick[i]);        }}

一個(gè)數(shù)據(jù)對象（數(shù)據(jù)文件或記錄）可被多個(gè)進(jìn)程共享。其中，讀者（reader）進(jìn)程要求讀，寫者（writer）進(jìn)程要求寫或修改。

為了保證讀寫的正確性和數(shù)據(jù)對象的一致性，系統(tǒng)要求：當(dāng)有讀者進(jìn)程讀文件時(shí)，不允許任何寫者進(jìn)程寫，但允許多個(gè)讀者同時(shí)讀；當(dāng)有寫者進(jìn)程寫時(shí)，不允許任何其它寫者進(jìn)程寫，也不允許任何讀者進(jìn)程讀。

設(shè)置一個(gè)共享變量和兩個(gè)信號量：

共享變量readcount：記錄當(dāng)前正在讀數(shù)據(jù)集的讀進(jìn)程數(shù)目，初值為0。

讀互斥信號量rmutex ：表示讀進(jìn)程互斥地訪問共享變量readcount，初值為1.

寫互斥信號量wmutex：表示寫進(jìn)程與其它進(jìn)程（讀、寫）互斥地訪問數(shù)據(jù)集，初值為1.

“讀者—寫者”問題的同步算法描述

semaphore  rmutex=1;  semaphore  wmutex=1; int  readcount=0; main(){  cobegin     reader();     writer();  coend}reader(){    while(true) {        P(rmutex);         if(readcount= =0) P(wmutex);/*第一位讀者阻止寫者*/        readcount++;  //修改readcount        V(rmutex);        讀數(shù)據(jù)集；         P(rmutex);         readcount--;  //修改readcount        if(readcount= =0) V(wmutex);/*第末位讀者允許寫者進(jìn)*/        V(rmutex);    }}writer(){  while(true) {       P(wmutex); // 阻止其它進(jìn)程（讀、寫）；       寫數(shù)據(jù)集；       V(wmutex); // 允許其它進(jìn)程（讀、寫）；  }}