2.3 進程同步

2.3.1 進程同步的基本概念

2.3.1.1 進程同步

進程具有異步性的特征。異步性是指，各并發(fā)執(zhí)行的進程以各自獨立的、不可預(yù)知的速度向前推進。同步亦稱直接制約關(guān)系，它是指為完成某種任務(wù)而建立的兩個或多個進程，這些進程因為需要在某些位置上協(xié)調(diào)它們的工作次序而產(chǎn)生的制約關(guān)系。進程間的直接制約關(guān)系就是源于它們之間的相互合作。

2.3.1.1 臨界資源

進程的“并發(fā)”需要“共享”的支持。各個并發(fā)執(zhí)行的進程不可避免的需要共享一些系統(tǒng)資源，兩種資源共享方式為

• 互斥共享方式：系統(tǒng)中的某些資源，雖然可以提供給多個進程使用，但一個時間段內(nèi)只允許一個進程訪問該資源
• 同時共享方式：系統(tǒng)中的某些資源，允許一個時間段內(nèi)由多個進程“同時”對它們進行訪問

我們把一個時間段內(nèi)只允許一個進程使用的資源稱為臨界資源。許多物理設(shè)備（比如攝像頭、打印機）都屬于臨界資源。此外還有許多變量、數(shù)據(jù)、內(nèi)存緩沖區(qū)等都屬于臨界資源。

對臨界資源的訪問，必須互斥地進行。互斥，亦稱間接制約關(guān)系。進程互斥指當(dāng)一個進程訪問某臨界資源時，另一個想要訪問該臨界資源的進程必須等待。當(dāng)前訪問臨界資源的進程訪問結(jié)束，釋放該資源之后，另一個進程才能去訪問臨界資源

對臨界資源的互斥訪問，可以在邏輯上分為如下四個部分：

do {
    /*
        進入?yún)^(qū),負責(zé)檢查是否可進入臨界區(qū)，
        若可進入，則應(yīng)設(shè)置正在訪問臨界資
        源的標志（可理解為“上鎖”），以阻
        止其他進程同時進入臨界區(qū)
    */
    entry section;      
    critical section;   //臨界區(qū),訪問臨界資源的那段代碼
    exit section;       //退出去,負責(zé)解除正在訪問臨界資源的標志（可理解為“解鎖”）
    remainder section;  //剩余區(qū),做其他處理
} while(true)

臨界區(qū)也可稱為“臨界段”,是進程中訪問臨界資源的代碼段。

進入?yún)^(qū)和退出區(qū)是負責(zé)實現(xiàn)互斥的代碼段.

2.3.1.2 進程互斥

當(dāng)一個進程進入臨界區(qū)使用臨界資源時，另一個進程必須等待，當(dāng)占用臨界資源的進程推出臨界區(qū)后，另一經(jīng)常才允許區(qū)訪問次臨界資源。為了實現(xiàn)對臨界資源的互斥訪問，同時保證系統(tǒng)整體性能，需要遵循以下原則：

1. 空閑讓進。臨界區(qū)空閑時，可以允許一個請求進入臨界區(qū)的進程立即進入臨界區(qū)；
2. 忙則等待。當(dāng)已有進程進入臨界區(qū)時，其他試圖進入臨界區(qū)的進程必須等待；
3. 有限等待。對請求訪問的進程，應(yīng)保證能在有限時間內(nèi)進入臨界區(qū)（保證不會饑餓）；
4. 讓權(quán)等待。當(dāng)進程不能進入臨界區(qū)時，應(yīng)立即釋放處理機，防止進程忙等待。

2.3.2 實現(xiàn)臨界區(qū)互斥的基本方法

2.3.2.1 軟件實現(xiàn)方法

2.3.2.1.1 單標志法

算法思想：兩個進程在訪問完臨界區(qū)后會把使用臨界區(qū)的權(quán)限轉(zhuǎn)交給另一個進程。也就是說每個進程進入臨界區(qū)的權(quán)限只能被另一個進程賦予

int turn = 0;       //turn表示當(dāng)前允許進入臨界區(qū)的進程號

//P0進程
while (turn != 0);  //進入?yún)^(qū)
critical section;   //臨界區(qū)
turn = 1;           //退出區(qū)
remainder section;  //剩余區(qū)

//P1進程
while (turn != 1);  //進入?yún)^(qū)
critical section;   //臨界區(qū)
turn = 0;           //退出區(qū)
remainder section;  //剩余區(qū)

該算法可以實現(xiàn)“同一時刻最多只允許一個進程訪問臨界區(qū)”，單標志法存在的主要問題是：違背“空閑讓進”原則。

2.3.2.1.2 雙標志先檢查法

算法思想：設(shè)置一個布爾型數(shù)組flag[]，數(shù)組中各個元素用來標記各進程想進入臨界區(qū)的意愿，比如“flag[0] = ture”意味著0 號進程P0 現(xiàn)在想要進入臨界區(qū)。每個進程在進入臨界區(qū)之前先檢查當(dāng)前有沒有別的進程想進入臨界區(qū)，如果沒有，則把自身對應(yīng)的標志flag[i] 設(shè)為true，之后開始訪問臨界區(qū)。

bool flag[2];       //表示進入臨界區(qū)意愿的數(shù)組
//剛開始設(shè)置為兩個進程都不想進入臨界區(qū)
flag[0] = false;    
flag[1] = false;

//P0進程
while(flag[1]);     //進入?yún)^(qū)
flag[0] = true;     //進入?yún)^(qū)
critical section;   //臨界區(qū)
flag[0] = false;    //退出區(qū)
remainder section;  //剩余區(qū)

//P1進程
while(flag[0]);     //如果此時P0想進入臨界區(qū)，P1就循環(huán)等待
flag[1] = true;     //標記為P1進程想要進入臨界區(qū)
critical section;   //訪問臨界區(qū)
flag[1] = false;    //訪問完臨界區(qū)，修改標記為P1不想使用臨界區(qū)
remainder section;

雙標志先檢查法優(yōu)點：不用交替進入，可連續(xù)使用；主要問題是：違反“忙則等待”原則。原因在于，進入?yún)^(qū)的“檢查”和“上鎖” 兩個處理不是一氣呵成的?！皺z查”后，“上鎖”前可能發(fā)生進程切換。

2.3.2.1.3 雙標志后檢查法

算法思想：雙標志先檢查法的改版。前一個算法的問題是先“檢查”后“上鎖”，但是這兩個操作又無法一氣呵成，因此導(dǎo)致了兩個進程同時進入臨界區(qū)的問題。因此，人們又想到先“上鎖”后“檢查”的方法，來避免上述問題。

bool flag[2];       //表示進入臨界區(qū)意愿的數(shù)組
//剛開始設(shè)置為兩個進程都不想進入臨界區(qū)
flag[0] = false;    
flag[1] = false;

//P0進程
flag[0] = true;     //進入?yún)^(qū)
while(flag[1]);     //進入?yún)^(qū)
critical section;   //臨界區(qū)
flag[0] = false;    //退出區(qū)
remainder section;  //剩余區(qū)

//P1進程
flag[1] = true;     //標記為P1進程想要進入臨界區(qū)
while(flag[0]);     //如果此時P0想進入臨界區(qū)，P1就循環(huán)等待
critical section;   //訪問臨界區(qū)
flag[1] = false;    //訪問完臨界區(qū)，修改標記為P1不想使用臨界區(qū)
remainder section;

因此，雙標志后檢查法雖然解決了“忙則等待”的問題，但是又違背了“空閑讓進”和“有限等待”原則，會因各進程都長期無法訪問臨界資源而產(chǎn)生“饑餓”現(xiàn)象。兩個進程都爭著想進入臨界區(qū)，但是誰也不讓誰，最后誰都無法進入臨界區(qū)。

2.3.2.1.4 Peterson 算法

算法思想：結(jié)合雙標志法、單標志法的思想。如果雙方都爭著想進入臨界區(qū)，那可以讓進程嘗試“孔融讓梨”（謙讓）。做一個有禮貌的進程。

bool flag[2];       //表示進入臨界區(qū)意愿的數(shù)組
//剛開始設(shè)置為兩個進程都不想進入臨界區(qū)
flag[0] = false;    
flag[1] = false;
int turn = 0;       //turn表示優(yōu)先讓哪個進程進入臨界區(qū)

//P0進程
flag[0] = true;     //進入?yún)^(qū)
turn = 1;           //進入?yún)^(qū)
while (flag[1] && turn == 1);   //進入?yún)^(qū)
critical section;   //臨界區(qū)
flag[0] = false;    //退出區(qū)
remainder section;  //剩余區(qū)

//P1進程
flag[1] = true;     //表示自己想進入臨界區(qū)
turn = 0;           //可以優(yōu)先讓對方進入臨界區(qū)
while (flag[0] && turn == 0);   //對方詳盡，且最后一次是自己禮讓，那就循環(huán)等待
critical section;
flag[1] = false;    //訪問完臨界區(qū)，表示不想訪問臨界區(qū)
remainder section;

Peterson 算法用軟件方法解決了進程互斥問題，遵循了空閑讓進、忙則等待、有限等待三個原則，但是依然未遵循讓權(quán)等待的原則。

2.3.2.2 硬件實現(xiàn)方法

2.3.2.2.1 中斷屏蔽方法

利用“開/關(guān)中斷指令”實現(xiàn)（與原語的實現(xiàn)思想相同，即在某進程開始訪問臨界區(qū)到結(jié)束訪問為止都不允許被中斷，也就不能發(fā)生進程切換，因此也不可能發(fā)生兩個同時訪問臨界區(qū)的情況)

優(yōu)點:簡單、高效

缺點:不適用于多處理機;只適用于操作系統(tǒng)內(nèi)核進程，不適用于用戶進程（因為開/關(guān)中斷指令只能運行在內(nèi)核態(tài)，這組指令如果能讓用戶隨意使用會很危險)

2.3.2.2.2 TestAndSet指令

簡稱TS指令，也有地方稱為TestAndSetLock指令，或TSL指令TSL指令是用硬件實現(xiàn)的，執(zhí)行的過程不允許被中斷，只能一氣呵成。以下是用c語言描述的邏輯

//布爾型共享變量lock表示當(dāng)前臨界區(qū)是否被加鎖，true表示已加鎖
bool TestAndSet(bool *lock){
    bool old;
    old = *lock;        //old用來存放lock原來的值
    *lock = true;       //無論之前是否已經(jīng)加鎖，都設(shè)置為true
    return old;         //返回lock原來的值
}

該指令實現(xiàn)進程互斥的算法描述為

while TestAndSet(&lock);    //上鎖并檢查
...     //臨界區(qū)代碼段
lock = false;   //解鎖
...     //剩余區(qū)代碼段

若剛開始lock是false，則TSL返回的old值為false，while循環(huán)條件不滿足，直接跳過循環(huán)，進入臨界區(qū)。若剛開始lock是true，則執(zhí)行TLS后old返回的值為true，while循環(huán)條件滿足，會一直循環(huán)，直到當(dāng)前訪問臨界區(qū)的進程在退出區(qū)進行“解鎖”。

相比軟件實現(xiàn)方法，TSL指令把“上鎖”和“檢查”操作用硬件的方式變成了一氣呵成的原子操作。優(yōu)點:實現(xiàn)簡單，無需像軟件實現(xiàn)方法那樣嚴格檢查是否會有邏輯漏洞;適用于多處理機環(huán)境；缺點:不滿足“讓權(quán)等待”原則，暫時無法進入臨界區(qū)的進程會占用CPU并循環(huán)執(zhí)行TSL指令，從而導(dǎo)致“忙等”。

2.3.2.2.3 Swap指令

有的地方也叫 Exchange指令，或簡稱XCHG指令。Swap指令是用硬件實現(xiàn)的，執(zhí)行的過程不允許被中斷，只能一氣呵成。以下是用c語言描述的邏輯

// 交換兩個字的內(nèi)容
void swap(boolean *a, boolean *b){
    boolean temp;
    temp = *a;
    *a = *b;
    *b = temp;
}

Swap指令實現(xiàn)進程互斥的代碼

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

邏輯上來看Swap和TSL并無太大區(qū)別，都是先記錄下此時臨界區(qū)是否已經(jīng)被上鎖（記錄在old變量上），再將上鎖標記lock設(shè)置為true，最后檢查old，如果old為 false則說明之前沒有別的進程對臨界區(qū)上鎖，則可跳出循環(huán)，進入臨界區(qū)。

優(yōu)點:實現(xiàn)簡單，無需像軟件實現(xiàn)方法那樣嚴格檢查是否會有邏輯漏洞;適用于多處理機環(huán)境；缺點:不滿足“讓權(quán)等待”原則，暫時無法進入臨界區(qū)的進程會占用CPU并循環(huán)執(zhí)行TSL指令，從而導(dǎo)致“忙等”。

2.3.3 信號量

用戶進程可以通過使用操作系統(tǒng)提供的一對原語來對信號量進行操作，從而很方便的實現(xiàn)了進程互斥、進程同步。

信號量其實就是一個變量，可以用一個信號量來表示系統(tǒng)中某種資源的數(shù)量，比如：系統(tǒng)中只有一臺打印機，就可以設(shè)置一個初值為1 的信號量。只能被一對原語所訪問：wait(S) 原語和signal(S) 原語，可以把原語理解為我們自己寫的函數(shù)，函數(shù)名分別為wait和signal，括號里的信號量S 其實就是函數(shù)調(diào)用時傳入的一個參數(shù)。wait、signal 原語常簡稱為P、V操作（來自荷蘭語proberen 和verhogen）。因此，做題的時候常把wait(S)、signal(S) 兩個操作分別寫為P(S)、V(S)

原語是一種特殊的程序段，其執(zhí)行只能一氣呵成，不可被中斷。原語是由關(guān)中斷/開中斷指令實現(xiàn)的。軟件解決方案的主要問題是由“進入?yún)^(qū)的各種操作無法一氣呵成”，因此如果能把進入?yún)^(qū)、退出區(qū)的操作都用“原語”實現(xiàn)，使這些操作能“一氣呵成”就能避免問題。

2.3.3.1 整型信號量

用一個整數(shù)型的變量作為信號量，用來表示系統(tǒng)中某種資源的數(shù)量。

int S = 1;              //初始化整型信號量S，表示當(dāng)前可用資源數(shù)

void wait(int S){       //wait原語，相當(dāng)于進入?yún)^(qū)
    while (S <= 0);     //如果資源數(shù)不夠，就循環(huán)等待
    S = S - 1;          //如果資源數(shù)夠，則占用一個資源
}

void signal(int S){     //signal原語，相當(dāng)于退出區(qū)
    S = S + 1;          //使用完資源后，在退出區(qū)釋放資源
}

存在的問題：不滿足“讓權(quán)等待”原則，會發(fā)生“忙等”

2.3.3.2 記錄型信號量

整型信號量的缺陷是存在“忙等”問題，因此人們又提出了“記錄型信號量”，即用記錄型數(shù)據(jù)結(jié)構(gòu)表示的信號量

// 記錄型信號量的定義
typedef struct{
    int value;          //剩余資源數(shù)
    struct process *L   //等待隊列
}semaphore;

//某進程需要使用資源時，通過wait原語申請
void wait(semaphore S){
    S.value--;
    if (S.value < 0){
        /*
            如果剩余資源數(shù)不夠，使用block原語使進程從
            運行態(tài)進入阻塞態(tài)，并把掛到信號量S 的等待
            隊列（即阻塞隊列）中
        */
        block(S.L)
    }
}

//進程使用完資源后，通過signal原語釋放
void signal(semaphore S){
    S.value ++ ;
    if (S.value <= 0){.
        /*
            釋放資源后，若還有別的進程在等待這種資源，則使用
            wakeup 原語喚醒等待隊列中的一個進程，該進程從阻
            塞態(tài)變?yōu)榫途w態(tài)
        */
        wakeup(S.L);
    }
}

2.3.3.3 利用信號量實現(xiàn)進程互斥

1. 分析并發(fā)進程的關(guān)鍵活動，劃定臨界區(qū)（如：對臨界資源打印機的訪問就應(yīng)放在臨界區(qū)）
2. 設(shè)置互斥信號量mutex，初值為1
3. 在進入?yún)^(qū)P(mutex)——申請資源
4. 在退出區(qū)V(mutex)——釋放資源

// 記錄型信號量的定義
typedef struct{
    int value;          //剩余資源數(shù)
    struct process *L   //等待隊列
}semaphore;

semaphore mutex = 1;

P1(){
    ...;
    P(mutex);       //使用臨界資源前需要加鎖
    ...;            //臨界區(qū)代碼段
    V(mutex);       //使用臨界資源后需要解鎖
    ...;
}

P2(){
    ...;
    P(mutex);       //使用臨界資源前需要加鎖
    ...;            //臨界區(qū)代碼段
    V(mutex);       //使用臨界資源后需要解鎖
    ...;
}

對不同的臨界資源需要設(shè)置不同的互斥信號量。P、V操作必須成對出現(xiàn)。缺少P(mutex) 就不能保證臨界資源的互斥訪問。缺少V(mutex) 會導(dǎo)致資源永不被釋放，等待進程永不被喚醒。

2.3.3.4 利用信號量實現(xiàn)進程同步

進程同步：要讓各并發(fā)進程按要求有序地推進。

1. 分析什么地方需要實現(xiàn)“同步關(guān)系”，即必須保證“一前一后”執(zhí)行的兩個操作（或兩句代碼）
2. 設(shè)置同步信號量S, 初始為0
3. 在“前操作”之后執(zhí)行V(S)
4. 在“后操作”之前執(zhí)行P(S)

semaphore S = 0;

P1(){
    代碼1;
    代碼2;
    V(S);
    代碼3;
}

P2(){
    P(S);
    代碼4;
    代碼5;
    代碼6;
}

上述代碼保證了代碼4 一定是在代碼2 之后執(zhí)行

利用信號量實現(xiàn)前驅(qū)關(guān)系實際上可以理解為每兩個之間的同步，即對每一對關(guān)系設(shè)置一個信號量，分別做上述操作即可

PV操作題目分析步驟：

1. 關(guān)系分析。找出題目中描述的各個進程，分析它們之間的同步、互斥關(guān)系。
2. 整理思路。根據(jù)各進程的操作流程確定P、V操作的大致順序。
3. 設(shè)置信號量。并根據(jù)題目條件確定信號量初值。（互斥信號量初值一般為1，同步信號量的初始值要看對應(yīng)資源的初始值是多少）

2.3.4 經(jīng)典同步問題

2.3.4.1 生產(chǎn)者-消費者問題

系統(tǒng)中有一組生產(chǎn)者進程和一組消費者進程，生產(chǎn)者進程每次生產(chǎn)一個產(chǎn)品放入緩沖區(qū)，消費者進程每次從緩沖區(qū)中取出一個產(chǎn)品并使用。（注：這里的“產(chǎn)品”理解為某種數(shù)據(jù)）生產(chǎn)者、消費者共享一個初始為空、大小為n的緩沖區(qū)。只有緩沖區(qū)沒滿時，生產(chǎn)者才能把產(chǎn)品放入緩沖區(qū)，否則必須等待。只有緩沖區(qū)不空時，消費者才能從中取出產(chǎn)品，否則必須等待。緩沖區(qū)是臨界資源，各進程必須互斥地訪問。

圖片.png

semaphore mutex = 1;        //互斥信號量，實現(xiàn)對緩沖區(qū)的互斥訪問
semaphore empty = n;        //同步信號量，表示空閑緩沖區(qū)的數(shù)量
semaphore full = 0;         //同步信號量，表示產(chǎn)品的數(shù)量，也即非空緩沖區(qū)的數(shù)量

producer (){
    while(1){
        生產(chǎn)一個產(chǎn)品;
        P(empty);           //消耗一個空閑緩沖區(qū)
        P(mutex);
        把產(chǎn)品放入緩沖區(qū);
        V(mutex);
        V(full);            //增加一個產(chǎn)品
    }
}

consumer (){
    while(1){
        P(full);            //消耗一個產(chǎn)品（非空緩沖區(qū)）
        P(mutex);
        從緩沖區(qū)取出一個產(chǎn)品;
        V(mutex);
        V(empty);           //增加一個空閑緩沖區(qū)
        使用產(chǎn)品;
    }
}

實現(xiàn)互斥是在同一進程中進行一對PV操作

實現(xiàn)兩進程的同步關(guān)系，是在其中一個進程中執(zhí)行P，另一進程中執(zhí)行V

實現(xiàn)互斥的P操作一定要在實現(xiàn)同步的P操作之后,否則可能導(dǎo)致死鎖。兩個V操作順序可以交換。

2.3.4.2 多生產(chǎn)者-多消費者問題

桌子上有一只盤子，每次只能向其中放入一個水果。爸爸專向盤子中放蘋果，媽媽專向盤子中放橘子，兒子專等著吃盤子中的橘子，女兒專等著吃盤子中的蘋果。只有盤子空時，爸爸或媽媽才可向盤子中放一個水果。僅當(dāng)盤子中有自己需要的水果時，兒子或女兒可以從盤子中取出水果。用PV操作實現(xiàn)上述過程。

[圖片上傳失敗...(image-5a82e5-1631025230971)]

semaphore apple = 0;        //盤子中有幾個蘋果
semaphore orange = 0;       //盤子中有幾個橘子
semaphore plate = 1;        //盤子中還可以放多少個水果

dad (){
    while(1){
        準備一個蘋果;
        P(plate);
        P(mutex);
        把蘋果放入盤子;
        V(mutex);
        V(apple);
    }
}

mom (){
    while(1){
        準備一個橘子;
        P(plate);
        P(mutex);
        把橘子放入盤子;
        V(mutex);
        V(orange);
    }
}

daughter (){
    while(1){
        P(apple);
        P(mutex);
        從盤中取出蘋果;
        V(mutex);
        V(plate);
        吃掉蘋果;
    }
}

son (){
    while(1){
        P(orange);
        P(mutex);
        從盤中取出橘子;
        V(mutex);
        V(plate);
        吃掉橘子;
    }
}

本題中的緩沖區(qū)大小為1，在任何時刻，apple、orange、plate 三個同步信號量中最多只有一個是1。因此在任何時刻，最多只有一個進程的P操作不會被阻塞，并順利地進入臨界區(qū)，因此即使不設(shè)置專門的互斥變量mutex，也不會出現(xiàn)多個進程同時訪問盤子的現(xiàn)象

2.3.4.3 吸煙者問題

假設(shè)一個系統(tǒng)有三個抽煙者進程和一個供應(yīng)者進程。每個抽煙者不停地卷煙并抽掉它，但是要卷起并抽掉一支煙，抽煙者需要有三種材料:煙草、紙和膠水。三個抽煙者中，第一個擁有煙草、第二個擁有紙、第三個擁有膠水。供應(yīng)者進程無限地提供三種材料，供應(yīng)者每次將兩種材料放桌子上，擁有剩下那種材料的抽煙者卷一根煙并抽掉它，并給供應(yīng)者進程一個信號告訴完成了，供應(yīng)者就會放另外兩種材料再桌上，這個過程一直重復(fù)（讓三個抽煙者輪流地抽煙)

圖片.png

semaphore offer1 = 0;       //桌上組合一的數(shù)量
semaphore offer2 = 0;       //桌上組合二的數(shù)量
semaphore offer3 = 0;       //桌上組合三的數(shù)量
semaphore finish = 0;       //抽煙是否完成
int i = 0;                  //用于實現(xiàn)“三個抽煙者輪流抽煙”

provider (){
    while(1){
        if(i==0) {
            將組合一放桌上;
            V(offer1);
        } else if(i==1){
            將組合二放桌上;
            V(offer2);
        } else if(i==2){
            將組合三放桌上;
            V(offer3);
        }
        i = (i+1)%3;
        P(finish);
    }
}

smoker1 (){
    while(1){
        P(offer1);
        從桌上拿走組合一；卷煙；抽掉；
        V(finish);
    }
}

smoker2 (){
    while(1){
        P(offer2);
        從桌上拿走組合二；卷煙；抽掉；
        V(finish);
    }
}

smoker3 (){
    while(1){
        P(offer2);
        從桌上拿走組合三；卷煙；抽掉；
        V(finish);
    }
}

2.3.4.4 讀者-寫者問題

有讀者和寫者兩組并發(fā)進程，共享一個文件，當(dāng)兩個或兩個以上的讀進程同時訪問共享數(shù)據(jù)時不會產(chǎn)生副作用，但若某個寫進程和其他進程（讀進程或?qū)戇M程）同時訪問共享數(shù)據(jù)時則可能導(dǎo)致數(shù)據(jù)不一致的錯誤。因此要求:①允許多個讀者可以同時對文件執(zhí)行讀操作;②只允許一個寫者往文件中寫信息;③任一寫者在完成寫操作之前不允許其他讀者或?qū)懻吖ぷ?④寫者執(zhí)行寫操作前，應(yīng)讓已有的讀者和寫者全部退出。

semaphore rw=1;         //用于實現(xiàn)對共享文件的互斥訪問
int count = 0;          //記錄當(dāng)前有幾個讀進程在訪問文件
semaphore mutex = 1;    //用于保證對count??量的互斥訪問
//semaphore w = 1;      //用于實現(xiàn)"寫優(yōu)先"

writer (){
    while(1){
        //P(W);         //設(shè)置另一個互斥信號量,在無寫進程時請求加入
        P(rw);          //寫之前“加鎖”
        寫文件…
        V(rw);          //寫完了“解鎖”
        //V(W);         //設(shè)置另一個互斥信號量,恢復(fù)對共享文件的訪問
    }
}

reader (){
    while(1){
        P(mutex);       //各讀進程互斥訪問count
        if(count==0)    //由第一個讀進程負責(zé)
            P(rw);      //讀之前“加鎖”
        count++;        //訪問文件的讀進程數(shù)+1
        V(mutex);
        讀文件…
        P(mutex);       //各讀進程互斥訪問count
        count--;        //訪問文件的讀進程數(shù)-1
        if(count==0)    //由最后一個讀進程負責(zé)
            V(rw);      //讀完了“解鎖”
        V(mutex);
    }
}

若兩個讀進程并發(fā)執(zhí)行，則count=o時兩個進程也許都能滿足if條件，都會執(zhí)行P(rw)，從而使第二個讀進程阻塞的情況。出現(xiàn)上述問題的原因在于對count變量的檢查和賦值無法一氣呵成，因此可以設(shè)置另一個互斥信號量來保證各讀進程對count的訪問是互斥的。

2.3.4.5 哲學(xué)家進餐問題

一張圓桌上坐著5名哲學(xué)家，每兩個哲學(xué)家之間的桌上擺一根筷子，桌子的中間是一碗米飯。哲學(xué)家們傾注畢生的精力用于思考和進餐，哲學(xué)家在思考時，并不影響他人。只有當(dāng)哲學(xué)家饑餓時，才試圖拿起左、右兩根筷子（一根一根地拿起）。如果筷子已在他人手上，則需等待。饑餓的哲學(xué)家只有同時拿起兩根筷子才可以開始進餐，當(dāng)進餐完畢后，放下筷子繼續(xù)思考。

1. 關(guān)系分析。系統(tǒng)中有5個哲學(xué)家進程，5位哲學(xué)家與左右鄰居對其中間筷子的訪問是互斥關(guān)系。
2. 整理思路。這個問題中只有互斥關(guān)系，但與之前遇到的問題不同的事，每個哲學(xué)家進程需要同時持有兩個臨界資源才能開始吃飯。如何避免臨界資源分配不當(dāng)造成的死鎖現(xiàn)象，是哲學(xué)家問題的精髓。
3. 信號量設(shè)置。定義互斥信號量數(shù)組chopstick[5]={1,1,1,1,1} 用于實現(xiàn)對5個筷子的互斥訪問。并對哲學(xué)家按0~4編號，哲學(xué)家i 左邊的筷子編號為i，右邊的筷子編號為(i+1)%5。

semaphore chopstick[5]={1,1,1,1,1};     //初始化信號量
semaphore mutex = 1;                    //互斥地取筷子
Pi (){                                  //i號哲學(xué)家的進程
    while(1){
        P(mutex);                       //在取筷子前獲得互斥量
        P(chopstick[i]);                //拿左
        P(chopstick[(i+1)%5]);          //拿右
        V(mutex);                       //釋放取筷子的信號量
        吃飯…
        V(chopstick[i]);                //放左
        V(chopstick[(i+1)%5]);          //放右
        思考…
    }
}

2.3.4 管程

信號量機制存在的問題:編寫程序困難、易出錯1973年，Brinch Hansen首次在程序設(shè)計語言(Pascal)中引入了“管程”成分――一種高級同步機制。管程是一種特殊的軟件模塊，有這些部分組成:

• 局部于管程的共享數(shù)據(jù)結(jié)構(gòu)說明;
• 對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程;
• 對局部于管程的共享數(shù)據(jù)設(shè)置初始值的語句;
• 管程有一個名字。

管程的基本特征:

• 局部于管程的數(shù)據(jù)只能被局部于管程的過程所訪問;
• 一個進程只有通過調(diào)用管程內(nèi)的過程才能進入管程訪問共享數(shù)據(jù);
• 每次僅允許一個進程在管程內(nèi)執(zhí)行某個內(nèi)部過程。