程序同步（作業系統）

2.9 程序同步的基本概念：臨界資源、同步和互斥

在多道程式環境下，程序是并發執行的，不同程序之間存在着不同的互相制約關系。為了協調程序之間的互相制約關系，引入了程序同步的概念。

臨界資源

雖然多個程序可以共享系統中的各種資源，但其中許多資源一次隻能為一個程序所使用，我們把一次僅允許一個程序使用的資源稱為臨界資源。許多實體裝置都屬于臨界資源，如列印機等。此外，還有許多變量、資料等都可以被若幹程序共享，也屬于臨界資源。

對臨界資源的通路，必須互斥地進行，在每個程序中，通路臨界資源的那段代碼稱為臨界區。為了保證臨界資源的正确使用，可以把臨界資源的通路過程分成四個部分：

• 進入區。為了進入臨界區使用臨界資源，在進入區要檢查可否進入臨界區，如果可以進入臨界區，則應設定正在通路臨界區的标志，以阻止其他程序同時進入臨界區。
• 臨界區。程序中通路臨界資源的那段代碼，又稱臨界段。
• 退出區。将正在通路臨界區的标志清除。
• 剩餘區。代碼中的其餘部分。

• do {
  entry section; //進入區
  critical section; //臨界區
  exit section; //退出區
  remainder section; //剩餘區
  } while (true)
             

• 同步

  同步亦稱直接制約關系，它是指為完成某種任務而建立的兩個或多個程序，這些程序因為需要在某些位置上協調它們的工作次序而等待、傳遞資訊所産生的制約關系。程序間的直接制約關系就是源于它們之間的互相合作。

  例如，輸入程序A通過單緩沖向程序B提供資料。當該緩沖區空時，程序B不能獲得所需資料而阻塞，一旦程序A将資料送入緩沖區，程序B被喚醒。反之，當緩沖區滿時，程序A被阻塞，僅當程序B取走緩沖資料時，才喚醒程序A。

  互斥

  互斥亦稱間接制約關系。當一個程序進入臨界區使用臨界資源時，另一個程序必須等待, 當占用臨界資源的程序退出臨界區後，另一程序才允許去通路此臨界資源。

  例如，在僅有一台列印機的系統中，有兩個程序A和程序B，如果程序A需要列印時, 系統已将列印機配置設定給程序B,則程序A必須阻塞。一旦程序B将列印機釋放，系統便将程序A喚醒，并将其由阻塞狀态變為就緒狀态。

  為禁止兩個程序同時進入臨界區，同步機制應遵循以下準則：

  • 空閑讓進。臨界區空閑時，可以允許一個請求進入臨界區的程序立即進入臨界區。
  • 忙則等待。當已有程序進入臨界區時，其他試圖進入臨界區的程序必須等待。
  • 有限等待。對請求通路的程序，應保證能在有限時間内進入臨界區。
  • 讓權等待。當程序不能進入臨界區時，應立即釋放處理器，防止程序忙等待。

• 2.10 實作臨界區互斥的基本方法

  軟體實作方法

  在進入區設定和檢查一些标志來标明是否有程序在臨界區中，如果已有程序在臨界區，則在進入區通過循環檢查進行等待，程序離開臨界區後則在退出區修改标志。

  1) 算法一：單标志法。

  該算法設定一個公用整型變量turn,用于訓示被允許進入臨界區的程序編号，即若turn=0，則允許P0程序進入臨界區。該算法可確定每次隻允許一個程序進入臨界區。但兩個程序必須交替進入臨界區，如果某個程序不再進入臨界區了，那麼另一個程序也将進入臨界區（違背“空閑讓進”）這樣很容易造成資源利用的不充分。

• </pre><pre name="code" class="cpp">// P0程序
  while(turn!=0);
  critical section;
  turn=1;
  remainder section;
             

  // P1程序
  while(turn!=1);  // 進入區
  critical section;  // 臨界區
  turn = 0;  // 退出區
  remainder section;  // 剩餘區
             

  2) 算法二：雙标志法先檢查。

  該算法的基本思想是在每一個程序通路臨界區資源之前，先檢視一下臨界資源是否正被通路，若正被通路，該程序需等待；否則，程序才進入自己的臨界區。為此，設定了一個資料flag[i]，如第i個元素值為FALSE，表示Pi程序未進入臨界區，值為TRUE，表示Pi程序進入臨界區。

  // Pi 程序
  while(flag[j]);  // ①    
  flag[i]=TRUE;  // ③  
  critical section;   
  flag[i] = FALSE; 
  remainder section;
             

  // Pj 程序
  while(flag[i]);  // ② 進入區
  flag[j] =TRUE;  // ④ 進入區
  critical section;  // 臨界區
  flag[j] = FALSE;  // 退出區
  remainder section;  // 剩餘區
             

  優點：不用交替進入，可連續使用；缺點：Pi和Pj可能同時進入臨界區。按序列①②③④ 執行時，會同時進入臨界區（違背“忙則等待”)。即在檢查對方flag之後和切換自己flag 之前有一段時間，結果都檢查通過。這裡的問題出在檢查和修改操作不能一次進行。

  3) 算法三：雙标志法後檢查。

  算法二是先檢測對方程序狀态标志後，再置自己标志，由于在檢測和放置中可插入另一個程序到達時的檢測操作，會造成兩個程序在分别檢測後，同時進入臨界區。為此，算法三釆用先設定自己标志為TRUE後,再檢測對方狀态标志，若對方标志為TURE，則程序等待；否則進入臨界區。

// Pi程序
flag[i] =TRUE;
while(flag[j]);
critical section;
flag[i] =FLASE;
remainder section;
           

// Pj程序
flag[j] =TRUE;  // 進入區
while(flag[i]);  // 進入區
critical section;  // 臨界區
flag [j] =FLASE;   // 退出區
remainder section;  // 剩餘區
           

當兩個程序幾乎同時都想進入臨界區時，它們分别将自己的标志值flag設定為TRUE，并且同時檢測對方的狀态（執行while語句），發現對方也要進入臨界區，于是雙方互相謙讓，結果誰也進不了臨界區，進而導緻“饑餓”現象。

4)算法四：Peterson’s Algorithm。

為了防止兩個程序為進入臨界區而無限期等待，又設定變量turn，訓示不允許進入臨界區的程序編号，每個程序在先設定自己标志後再設定turn 标志，不允許另一個程序進入。這時，再同時檢測另一個程序狀态标志和不允許進入标志，這樣可以保證當兩個程序同時要求進入臨界區，隻允許一個程序進入臨界區。

// Pi程序
flag[i]=TURE; turn=j;
while(flag[j]&&turn==j); 
critical section;
flag[i]=FLASE;
remainder section;
           
   

// Pj程序
flag[j] =TRUE;turn=i;  // 進入區
while(flag[i]&&turn==i);   // 進入區
critical section;  // 臨界區
flag[j]=FLASE;  // 退出區
remainder section;  // 剩餘區
           

本算法的基本思想是算法一和算法三的結合。利用flag解決臨界資源的互斥通路，而利用turn解決“饑餓”現象。

硬體實作方法

本節對硬體實作的具體了解對後面的信号量的學習很有幫助。計算機提供了特殊的硬體指令，允許對一個字中的内容進行檢測和修正，或者是對兩個字的内容進行交換等。通過硬體支援實作臨界段問題的低級方法或稱為元方法。

1) 中斷屏蔽方法

當一個程序正在使用處理機執行它的臨界區代碼時，要防止其他程序再進入其臨界區通路的最簡單方法是禁止一切中斷發生，或稱之為屏蔽中斷、關中斷。因為CPU隻在發生中斷時引起程序切換，這樣屏蔽中斷就能保證目前運作程序将臨界區代碼順利地執行完，進而保證了互斥的正确實作，然後再執行開中斷。其典型模式為：…關中斷;臨界區;開中斷;…這種方法限制了處理機交替執行程式的能力，是以執行的效率将會明顯降低。對核心來說，當它執行更新變量或清單的幾條指令期間關中斷是很友善的，但将關中斷的權力交給使用者則很不明智，若一個程序關中斷之後不再開中斷，則系統可能會是以終止。

2) 硬體指令方法

TestAndSet指令：這條指令是原子操作，即執行該代碼時不允許被中斷。其功能是讀出指定标志後把該标志設定為真。指令的功能描述如下：

boolean TestAndSet(boolean *lock){
    boolean old;
    old = *lock;
    *lock=true;
    return old;
}
           

可以為每個臨界資源設定一個共享布爾變量lock，表示資源的兩種狀态：true表示正被占用，初值為false。在程序通路臨界資源之前，利用TestAndSet檢查和修改标志lock；若有程序在臨界區，則重複檢查，直到程序退出。利用該指令實作程序互斥的算法描述如下：

while TestAndSet (& 1 ock);
// 程序的臨界區代碼段;
lock=false;
// 程序的其他代碼
           

Swap指令：該指令的功能是交換兩個位元組的内容。其功能描述如下。

Swap(boolean *a, boolean *b){  
    boolean temp;
    Temp=*a;
    *a = *b;
    *b = temp;
}
           

注意：以上對TestAndSet和Swap指令的描述僅僅是功能實作，并非軟體實作定義，事實上它們是由硬體邏輯直接實作的，不會被中斷。應為每個臨界資源設定了一個共享布爾變量lock，初值為false；在每個程序中再設定一個局部布爾變量key，用于與lock交換資訊。在進入臨界區之前先利用Swap指令交換lock 與key的内容，然後檢查key的狀态；有程序在臨界區時，重複交換和檢查過程，直到程序退出。利用Swap指令實作程序互斥的算法描述如下：

key=true;
while(key!=false)
Swap(&lock, &key); 
// 程序的臨界區代碼段；
lock=false;
// 程序的其他代碼；
           

硬體方法的優點：适用于任意數目的程序，不管是單處理機還是多處理機；簡單、容易驗證其正确性。可以支援程序内有多個臨界區，隻需為每個臨界區設立一個布爾變量。硬體方法的缺點：程序等待進入臨界區時要耗費處理機時間，不能實作讓權等待。從等待程序中随機選擇一個進入臨界區，有的程序可能一直選不上，進而導緻“饑餓”現象。

2.11 信号量：整型、記錄型信号量以及利用信号量實作程序互斥和前驅關系

信号量機構是一種功能較強的機制，可用來解決互斥與同步的問題，它隻能被兩個标準的原語wait(S)和signal(S)來通路，也可以記為“P操作”（通過）和“V操作（釋放）”。原語是指完成某種功能且不被分割不被中斷執行的操作序列，通常可由硬體來實作完成不被分割執行特性的功能。如前述的“Test-and-Set”和“Swap”指令，就是由硬體實作的原子操作。原語功能的不被中斷執行特性在單處理機時可由軟體通過屏蔽中斷方法實作。原語之是以不能被中斷執行，是因為原語對變量的操作過程如果被打斷，可能會去運作另一個對同一變量的操作過程，進而出現臨界段問題。如果能夠找到一種解決臨界段問題的元方法，就可以實作對共享變量操作的原子性。

整型信号量

整型信号量被定義為一個用于表示資源數目的整型量S，wait和signal操作可描述為：

wait(S){
    while (S<=0);
    S=S-1;
}
signal(S){
    S=S+1;
}
           

wait操作中，隻要信号量S<=0，就會不斷地測試。是以，該機制并未遵循“讓權等待” 的準則，而是使程序處于“忙等”的狀态。

記錄型信号量

記錄型信号量是不存在“忙等”現象的程序同步機制。除了需要一個用于代表資源數目的整型變量value外，再增加一個程序連結清單L，用于連結所有等待該資源的程序，記錄型信号量是由于釆用了記錄型的資料結構得名。記錄型信号量可描述為：

typedef struct{
    int value;
    struct process *L;
} semaphore;
           

相應的wait(S)和signal(S)的操作如下：

void wait (semaphore S) { //相當于申請資源
    S.value--;
    if(S.value<0) {
        add this process to S.L;
        block(S.L);
    }
}
           

wait操作，S.value--，表示程序請求一個該類資源，當S.value<0時，表示該類資源已配置設定完畢，是以程序應調用block原語，進行自我阻塞，放棄處理機，并插入到該類資源的等待隊列S.L中，可見該機制遵循了“讓權等待”的準則。

void signal (semaphore S) {  //相當于釋放資源
    S.value++;
    if(S.value<=0){
        remove a process P from S.L;
        wakeup(P);
    }
}      

signal操作，表示程序釋放一個資源，使系統中可供配置設定的該類資源數增1，故S.value++。若加1後仍是S.value<=0，則表示在S.L中仍有等待該資源的程序被阻塞，故還應調用wakeup 原語，将S.L中的第一個等待程序喚醒。

利用信号量實作同步

信号量機構能用于解決程序間各種同步問題。設S為實作程序P1、P2同步的公共信号量，初值為0。程序P2中的語句y要使用程序P1中語句x的運作結果，是以隻有當語句x執行完成之後語句y才可以執行。其實作程序同步的算法如下：

semaphore S = 0;  //初始化信号量
P1 ( ) {
    // …
    x;  //語句x
    V(S);  //告訴程序P2,語句乂已經完成
}
P2()）{
    // …
    P(S) ;  //檢查語句x是否運作完成
    y;  // 檢查無誤，運作y語句
    // …
}      

利用信号量實作程序互斥

信号量機構也能很友善地解決程序互斥問題。設S為實作程序Pl、P2互斥的信号量，由于每次隻允許一個程序進入臨界區，是以S的初值應為1（即可用資源數為1)。隻需把臨界區置于P(S)和V(S)之間，即可實作兩程序對臨界資源的互斥通路。其算法如下：

semaphore S = 1;  //初化信号量
P1 ( ) {
    // …
    P(S);  // 準備開始通路臨界資源，加鎖
    // 程序P1的臨界區
    V(S);  // 通路結束，解鎖
    // …
}
P2() {
    // …
    P(S); //準備開始通路臨界資源，加鎖
    // 程序P2的臨界區；
    V(S);  // 通路結束，解鎖
    // …
}      

互斥的實作是不同程序對同一信号量進行P、V操作，一個程序在成功地對信号量執行了P操作後進入臨界區，并在退出臨界區後，由該程序本身對該信号量執行V操作,表示目前沒有程序進入臨界區，可以讓其他程序進入。

利用信号量實作前驅關系

信号量也可以用來描述程式之間或者語句之間的前驅關系。圖2-8給出了一個前驅圖，其中S1, S2, S3, …, S6是最簡單的程式段（隻有一條語句）。為使各程式段能正确執行，應設定若幹個初始值為“0”的信号量。例如，為保證S1 -> S2、 S1 -> S3的前驅關系，應分别設定信号量a1、a2。同樣，為了保證 S2 -> S4、S2 ->S5、S3 -> S6、S4 -> S6、S5 -> S6,應設定信号量bl、b2、c、d、e。 

圖2-8 前驅圖舉例

實作算法如下：

semaphore  al=a2=bl=b2=c=d=e=0;  //初始化信号量
S1() {
    // …
    V(al);  V(a2) ;  //S1已經運作完成
}
S2() {
    P(a1);  //檢查S1是否運作完成
    // …
    V(bl); V(b2); // S2已經運作完成
}
S3() {
    P(a2);  //檢查S1是否已經運作完成
    // …
    V(c);  //S3已經運作完成
}
S4() {
    P(b1);  //檢查S2是否已經運作完成
    // …
    V(d);  //S4已經運作完成
}
S5() {
    P(b2);  //檢查S2是否已經運作完成
    // …
    V(e);  // S5已經運作完成
}
S6() {
    P(c);  //檢查S3是否已經運作完成
    P(d);  //檢查S4是否已經運作完成
    P(e);  //檢查S5是否已經運作完成
    // …;
}
           

分析程序同步和互斥問題的方法步驟

1) 關系分析。找出問題中的程序數，并且分析它們之間的同步和互斥關系。同步、互斥、前驅關系直接按照上面例子中的經典範式改寫。2) 整理思路。找出解決問題的關鍵點，并且根據做過的題目找出解決的思路。根據程序的操作流程确定P操作、V操作的大緻順序。3) 設定信号量。根據上面兩步，設定需要的信号量，确定初值，完善整理。

2.12 管程：管程的定義、組成及基本特性

管程的定義

系統中的各種硬體資源和軟體資源，均可用資料結構抽象地描述其資源特性，即用少量資訊和對資源所執行的操作來表征該資源，而忽略了它們的内部結構和實作細節。管程是由一組資料以及定義在這組資料之上的對這組資料的操作組成的軟體子產品，這組操作能初始化并改變管程中的資料和同步程序。

管程的組成

1) 局部于管程的共享結構資料說明。2) 對該資料結構進行操作的一組過程。3) 對局部于管程的共享資料設定初始值的語句。

管程的基本特性

1) 局部于管程的資料隻能被局部于管程内的過程所通路。2) 一個程序隻有通過調用管程内的過程才能進入管程通路共享資料。3) 每次僅允許一個程序在管程内執行某個内部過程。由于管程是一個語言成分，是以管程的互斥通路完全由編譯程式在編譯時自動添加，無需程式員關注，而且保證正确。

2.13 經典程序同步問題1：生産者-消費者問題

問題描述

一組生産者程序和一組消費者程序共享一個初始為空、大小為n的緩沖區，隻有緩沖區沒滿時，生産者才能把消息放入到緩沖區，否則必須等待；隻有緩沖區不空時，消費者才能從中取出消息，否則必須等待。由于緩沖區是臨界資源，它隻允許一個生産者放入消息，或者一個消費者從中取出消息。

問題分析

1) 關系分析。生産者和消費者對緩沖區互斥通路是互斥關系，同時生産者和消費者又是一個互相協作的關系，隻有生産者生産之後，消費者才能消費，他們也是同步關系。2) 整理思路。這裡比較簡單，隻有生産者和消費者兩個程序，正好是這兩個程序存在着互斥關系和同步關系。那麼需要解決的是互斥和同步PV操作的位置。3) 信号量設定。信号量mutex作為互斥信号量，它用于控制互斥通路緩沖池，互斥信号量初值為1；信号量full用于記錄目前緩沖池中“滿”緩沖區數，初值為0。信号量empty 用于記錄目前緩沖池中“空”緩沖區數，初值為n。生産者-消費者程序的描述如下：

semaphore mutex=1; //臨界區互斥信号量
semaphore empty=n;  //空閑緩沖區
semaphore full=0;  //緩沖區初始化為空
producer () { //生産者程序
    while(1){
        produce an item in nextp;  //生産資料
        P(empty);  //擷取空緩沖區單元
        P(mutex);  //進入臨界區.
        add nextp to buffer;  //将資料放入緩沖區
        V(mutex);  //離開臨界區,釋放互斥信号量
        V(full);  //滿緩沖區數加1
    }
}

consumer () {  //消費者程序
    while(1){
        P(full);  //擷取滿緩沖區單元
        P(mutex);  // 進入臨界區
        remove an item from buffer;  //從緩沖區中取出資料
        V (mutex);  //離開臨界區，釋放互斥信号量
        V (empty) ;  //空緩沖區數加1
        consume the item;  //消費資料
    }
}
           

該類問題要注意對緩沖區大小為n的處理，當緩沖區中有空時便可對empty變量執行P 操作，一旦取走一個産品便要執行V操作以釋放空閑區。對empty和full變量的P操作必須放在對mutex的P操作之前。如果生産者程序先執行P(mutex)，然後執行P(empty)，消費者執行P(mutex),然後執行P(fall),這樣可不可以？答案是否定的。設想生産者程序已經将緩沖區放滿，消費者程序并沒有取産品，即empty = 0，當下次仍然是生産者程序運作時，它先執行P(mutex)封鎖信号量，再執行P(empty)時将被阻塞，希望消費者取出産品後将其喚醒。輪到消費者程序運作時，它先執行P(mutex)，然而由于生産者程序已經封鎖mutex信号量，消費者程序也會被阻塞，這樣一來生産者、消費者程序都将阻塞，都指望對方喚醒自己，陷入了無休止的等待。同理，如果消費者程序已經将緩沖區取空，即 full = 0,下次如果還是消費者先運作，也會出現類似的死鎖。不過生産者釋放信号量時，mutex、full先釋放哪一個無所謂，消費者先釋放mutex還是empty都可以。

下面再看一個較為複雜的生産者-消費者問題:

問題描述

桌子上有一隻盤子，每次隻能向其中放入一個水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，兒子專等吃盤子中的橘子，女兒專等吃盤子中的蘋果。隻有盤子為空時，爸爸或媽媽就可向盤子中放一個水果；僅當盤子中有自己需要的水果時，兒子或女兒

可以從盤子中取出。

問題分析

1) 關系分析。這裡的關系稍複雜一些，首先由每次隻能向其中放入一隻水果可知爸爸和媽媽是互斥關系。爸爸和女兒、媽媽和兒子是同步關系，而且這兩對程序必須連起來，兒子和女兒之間沒有互斥和同步關系，因為他們是選擇條件執行，不可能并發，如圖2-8所示。

2) 整理思路。這裡有4個程序，實際上可以抽象為兩個生産者和兩個消費者被連接配接到大小為1的緩沖區上。

圖2-9  程序之間的關系

3) 信号量設定。首先設定信号量plate為互斥信号量，表示是否允許向盤子放入水果，初值為1，表示允許放入，且隻允許放入一個。信号量 apple表示盤子中是否有蘋果，初值為0，表示盤子為空，不許取，若apple=l可以取。信号量orange表示盤子中是否有橘子，初值為0，表示盤子為空，不許取，若orange=l可以取。解決該問題的代碼如下：

semaphore plate=l, apple=0, orange=0;
dad() {  //父親程序
    while (1) {
        prepare an apple;
        P(plate) ;  //互斥向盤中取、放水果
        put the apple on the plate;  //向盤中放蘋果
        V(apple);  //允許取蘋果
    }
}

mom() {  // 母親程序
    while(1) {
        prepare an orange;
        P(plate);  //互斥向盤中取、放水果
        put the orange on the plate;  //向盤中放橘子
        V(orange); //允許取橘子
    }
}

son(){  //兒子程序
    while(1){
        P(orange) ;  //互斥向盤中取橘子
        take an orange from the plate;
        V(plate);  //允許向盤中取、放水果
        eat the orange;
    }
}

daughter () {  //女兒程序
    while(1) {
        P(apple);  // 互斥向盤中取蘋果
        take an apple from the plate;
        V(plate);  //運作向盤中取、放水果
        eat the apple;
    }
}
           

程序間的關系如圖2-9所示。dad()和daughter()、mam()和son()必須連續執行，正因為如此，也隻能在女兒拿走蘋果後，或兒子拿走橘子後才能釋放盤子，即V(plate)操作。

2.14 經典程序同步問題2：讀者-寫者問題

問題描述

有讀者和寫者兩組并發程序，共享一個檔案，當兩個或以上的讀程序同時通路共享資料時不會産生副作用，但若某個寫程序和其他程序（讀程序或寫程序）同時通路共享資料時則可能導緻資料不一緻的錯誤。是以要求：①允許多個讀者可以同時對檔案執行讀操作；②隻允許一個寫者往檔案中寫資訊；③任一寫者在完成寫操作之前不允許其他讀者或寫者工作；④寫者執行寫操作前，應讓已有的讀者和寫者全部退出。

問題分析

1) 關系分析。由題目分析讀者和寫者是互斥的，寫者和寫者也是互斥的，而讀者和讀者不存在互斥問題。

2) 整理思路。兩個程序，即讀者和寫者。寫者是比較簡單的，它和任何程序互斥，用互斥信号量的P操作、V操作即可解決。讀者的問題比較複雜，它必須實作與寫者互斥的同時還要實作與其他讀者的同步，是以，僅僅簡單的一對P操作、V操作是無法解決的。那麼，在這裡用到了一個計數器，用它來判斷目前是否有讀者讀檔案。當有讀者的時候寫者是無法寫檔案的，此時讀者會一直占用檔案，當沒有讀者的時候寫者才可以寫檔案。同時這裡不同讀者對計數器的通路也應該是互斥的。

3) 信号量設定。首先設定信号量count為計數器，用來記錄目前讀者數量，初值為0; 設定mutex為互斥信号量，用于保護更新count變量時的互斥；設定互斥信号量rw用于保證讀者和寫者的互斥通路。

代碼如下：

int count=0;  //用于記錄目前的讀者數量
semaphore mutex=1;  //用于保護更新count變量時的互斥
semaphore rw=1;  //用于保證讀者和寫者互斥地通路檔案
writer () {  //寫者程序
    while (1){
        P(rw); // 互斥通路共享檔案
        Writing;  //寫入
        V(rw) ;  //釋放共享檔案
    }
}

reader () {  // 讀者程序
    while(1){
        P (mutex) ;  //互斥通路count變量
        if (count==0)  //當第一個讀程序讀共享檔案時
            P(rw);  //阻止寫程序寫
        count++;  //讀者計數器加1
        V (mutex) ;  //釋放互斥變量count
        reading;  //讀取
        P (mutex) ;  //互斥通路count變量
        count--; //讀者計數器減1
        if (count==0)  //當最後一個讀程序讀完共享檔案
            V(rw) ;  //允許寫程序寫
        V (mutex) ;  //釋放互斥變量 count
    }
}
           

在上面的算法中，讀程序是優先的，也就是說，當存在讀程序時，寫操作将被延遲，并且隻要有一個讀程序活躍，随後而來的讀程序都将被允許通路檔案。這樣的方式下，會導緻寫程序可能長時間等待，且存在寫程序“餓死”的情況。

如果希望寫程序優先，即當有讀程序正在讀共享檔案時，有寫程序請求通路，這時應禁止後續讀程序的請求，等待到已在共享檔案的讀程序執行完畢則立即讓寫程序執行，隻有在無寫程序執行的情況下才允許讀程序再次運作。為此，增加一個信号量并且在上面的程式中 writer()和reader()函數中各增加一對PV操作，就可以得到寫程序優先的解決程式。

int count = 0;  //用于記錄目前的讀者數量
semaphore mutex = 1;  //用于保護更新count變量時的互斥
semaphore rw=1;  //用于保證讀者和寫者互斥地通路檔案
semaphore w=1;  //用于實作“寫優先”

writer(){
    while(1){
        P(w);  //在無寫程序請求時進入
        P(rw);  //互斥通路共享檔案
        writing;  //寫入
        V(rw);  // 釋放共享檔案
        V(w) ;  //恢複對共享支件的通路
    }
}

reader () {  //讀者程序
    while (1){
        P (w) ;  // 在無寫程序請求時進入
        P (mutex);  // 互斥通路count變量

        if (count==0)  //當第一個讀程序讀共享檔案時
            P(rw);  //阻止寫程序寫

        count++;  //讀者計數器加1
        V (mutex) ;  //釋放互斥變量count
        V(w);  //恢複對共享檔案的通路
        reading;  //讀取
        P (mutex) ; //互斥通路count變量
        count--;  //讀者計數器減1

        if (count==0)  //當最後一個讀程序讀完共享檔案
            V(rw);  //允許寫程序寫

        V (mutex);  //釋放互斥變量count
    }
}
           

2.15 經典程序同步問題3：哲學家進餐問題

問題描述

一張圓桌上坐着5名哲學家，每兩個哲學家之間的桌上擺一根筷子，桌子的中間是一碗米飯，如圖2-10所示。哲學家們傾注畢生精力用于思考和進餐，哲學家在思考時，并不影響他人。隻有當哲學家饑餓的時候，才試圖拿起左、 右兩根筷子（一根一根地拿起）。如果筷子已在他人手上，則需等待。饑餓的哲學家隻有同時拿到了兩根筷子才可以開始進餐，當進餐完畢後，放下筷子繼續思考。

問題分析

1) 關系分析。5名哲學家與左右鄰居對其中間筷子的通路是互斥關系。

2) 整理思路。顯然這裡有五個程序。本題的關鍵是如何讓一個哲學家拿到左右兩個筷子而不造成死鎖或者饑餓現象。那麼解決方法有兩個，一個是讓他們同時拿兩個筷子；二是對每個哲學家的動作制定規則，避免饑餓或者死鎖現象的發生。

圖2-10 5名哲學家進餐

3) 信号量設定。定義互斥信号量數組Ch0PstiCk[5] = {l, 1, 1, 1, 1}用于對5個筷子的互斥通路。

對哲學家按順序從0～4編号，哲學家i左邊的筷子的編号為i，哲學家右邊的筷子的編号為(i+l)%5。

semaphore chopstick[5] = {1,1,1,1,1}; //定義信号量數組chopstick[5],并初始化
Pi(){  //i号哲學家的程序
    do{
        P (chopstick[i] ) ; //取左邊筷子
        P (chopstick[(i+1) %5] ) ；  //取右邊篌子
        eat;  //進餐
        V(chopstick[i]) ; //放回左邊筷子
        V(chopstick[(i+l)%5]);  //放回右邊筷子
        think;  //思考
    } while (1);
}
           

該算法存在以下問題：當五個哲學家都想要進餐，分别拿起他們左邊筷子的時候（都恰好執行完wait(chopstick[i]);)筷子已經被拿光了，等到他們再想拿右邊的筷子的時候（執行 wait(chopstick[(i+l)%5]);)就全被阻塞了，這就出現了死鎖。

為了防止死鎖的發生，可以對哲學家程序施加一些限制條件，比如至多允許四個哲學家同時進餐;僅當一個哲學家左右兩邊的筷子都可用時才允許他抓起筷子;對哲學家順序編号，要求奇數号哲學家先抓左邊的筷子，然後再轉他右邊的筷子，而偶數号哲學家剛好相反。正解制定規則如下：假設釆用第二種方法，當一個哲學家左右兩邊的筷子都可用時，才允許他抓起筷子。

semaphore chopstick[5] = {1,1,1,1,1}; //初始化信号量
semaphore mutex=l;  //設定取筷子的信号量
Pi(){ //i号哲學家的程序
    do{
        P (mutex) ; //在取筷子前獲得互斥量
        P (chopstick [i]) ; //取左邊筷子
        P (chopstick[ (i+1) %5]) ;  //取右邊筷子
        V (mutex) ; //釋放取筷子的信号量
        eat;  //進餐
        V(chopstick[i] ) ;  //放回左邊筷子
        V(chopstick[ (i+l)%5]) ;  //放回右邊筷子
        think;  // 思考
    }while(1);
}
           

此外還可以釆用AND型信号量機制來解決哲學家進餐問題，有興趣的讀者可以查閱相關資料，自行思考。

2.16 經典程序同步問題4：吸煙者問題

向題描述

假設一個系統有三個抽煙者程序和一個供應者程序。每個抽煙者不停地卷煙并抽掉它，但是要卷起并抽掉一支煙，抽煙者需要有三種材料：煙草、紙和膠水。三個抽煙者中，第一個擁有煙草、第二個擁有紙，第三個擁有膠水。供應者程序無限地提供三種材料， 供應者每次将兩種材料放到桌子上，擁有剩下那種材料的抽煙者卷一根煙并抽掉它，并給供應者一個信号告訴完成了，供應者就會放另外兩種材料在桌上，這種過程一直重複（讓三個抽煙者輪流地抽煙)。

問題分析

1) 關系分析。供應者與三個抽煙者分别是同步關系。由于供應者無法同時滿足兩個或 以上的抽煙者，三個抽煙者對抽煙這個動作互斥（或由三個抽煙者輪流抽煙得知）

2) 整理思路。顯然這裡有四個程序。供應者作為生産者向三個抽煙者提供材料。

3) 信号量設定。信号量offer1、offer2、offer3分别表示煙草和紙組合的資源、煙草和 膠水組合的資源、紙和膠水組合的資源。信号量finish用于互斥進行抽煙動作。

代碼如下：

int random; //存儲随機數
semaphore offer1=0; //定義信号量對應煙草和紙組合的資源
semaphore offer2=0; //定義信号量對應煙草和膠水組合的資源
semaphore offer3=0; //定義信号量對應紙和膠水組合的資源
semaphore finish=0; //定義信号量表示抽煙是否完成

//供應者
while(1){
    random = 任意一個整數随機數;
    random=random% 3;
    if(random==0)
        V(offerl) ; //提供煙草和紙
    else if(random==l) 
        V(offer2);  //提供煙草和膠水
    else
        V(offer3)  //提供紙和膠水
    // 任意兩種材料放在桌子上;
    P(finish);
}

//擁有煙草者
while(1){
    P (offer3);
    // 拿紙和膠水，卷成煙，抽掉;
    V(finish);
}

//擁有紙者
while(1){
    P(offer2);
    // 煙草和膠水,卷成煙，抽掉；
    V(finish);
}

//擁有膠水者
while(1){
    P(offer1);
    // 拿煙草和紙，卷成煙，抽掉;
    v(finish);
}