術(shù)語

• 進度圖 進度圖是將 n 個并發(fā)進程的執(zhí)行模型化為一條 n 維笛卡爾空間中的軌跡線，每條軸 k 對應(yīng)于線程 k 的進度，每個進度對應(yīng)一條指令。
• 臨界區(qū) 某個線程操作共享變量 cnt 內(nèi)容的一串指令
• 不安全區(qū) 兩個臨界區(qū)的交集形成的狀態(tài)空間區(qū)域稱為不安全區(qū)
• 安全軌跡區(qū) 繞開不安全區(qū)的軌跡線
• 信號量 是一個具有非負整數(shù)值的全局變量，只能由兩種特殊的操作 P(s)（測試減一） 和 V(s)（增加加一） 來處理，這兩個操作都是原子的，不可分割的
  
  臨界區(qū)與安全軌跡線
  
  為了保證線程化程序的正確執(zhí)行（實際上是任何共享全局數(shù)據(jù)結(jié)構(gòu)的冰法程序的正確執(zhí)行）我們必須以某種方式同步線程，使它們總是有一條安全軌跡線，一個經(jīng)典的方法是基于信號量的思想。

使用信號量來實現(xiàn)互斥

基本思想是將每個共享變量與一個信號量 s(初始化為一個整數(shù) n) 聯(lián)系起來，然后用 P(s) 和 V(s) 操作將相應(yīng)的臨界區(qū)包圍起來。
s 的初始值決定了這個資源可以同時被 n 個進程使用
n=1 時的信號量成為互斥鎖(mutex)，P(s) 和 V(s)相應(yīng)的成為加鎖和解鎖，信號量操作確保了對臨界區(qū)的互斥訪問。

使用信號量實現(xiàn)互斥

使用信號量來調(diào)度共享資源

除了提供互斥之外，信號量的另外一個重要作用是用來調(diào)度對共享資源的訪問，即一個線程用信號量來通知另一個線程，線程狀態(tài)中的某個條件已經(jīng)為真了。

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

生產(chǎn)者消費者問題也稱為有限緩沖問題，是一個多線程同步問題的經(jīng)典案例。該問題描述了共享固定大小緩沖區(qū)的兩個線程——即所謂的“生產(chǎn)者”和“消費者”——在實際運行時會發(fā)生的問題。生產(chǎn)者的主要作用是生成一定量的數(shù)據(jù)放到緩沖區(qū)中，然后重復(fù)此過程。與此同時，消費者也在緩沖區(qū)消耗這些數(shù)據(jù)。該問題的關(guān)鍵就是要保證生產(chǎn)者不會在緩沖區(qū)滿時加入數(shù)據(jù)，消費者也不會在緩沖區(qū)中空時消耗數(shù)據(jù)。
要解決該問題，就必須讓生產(chǎn)者在緩沖區(qū)滿時休眠（要么干脆就放棄數(shù)據(jù)），等到下次消費者消耗緩沖區(qū)中的數(shù)據(jù)的時候，生產(chǎn)者才能被喚醒，開始往緩沖區(qū)添加數(shù)據(jù)。同樣，也可以讓消費者在緩沖區(qū)空時進入休眠，等到生產(chǎn)者往緩沖區(qū)添加數(shù)據(jù)之后。
經(jīng)典進程同步問題1：生產(chǎn)者-消費者問題

semaphore mutex=1; //臨界區(qū)互斥信號量
semaphore empty=n;  //空閑緩沖區(qū)
semaphore full=0;  //緩沖區(qū)初始化為空
producer () { //生產(chǎn)者進程
   while(1){
       produce an item in nextp;  //生產(chǎn)數(shù)據(jù)
       P(empty);  //獲取空緩沖區(qū)單元
       P(mutex);  //進入臨界區(qū).
       add nextp to buffer;  //將數(shù)據(jù)放入緩沖區(qū)
       V(mutex);  //離開臨界區(qū),釋放互斥信號量
       V(full);  //滿緩沖區(qū)數(shù)加1
   }
}
consumer () {  //消費者進程
   while(1){
       P(full);  //獲取滿緩沖區(qū)單元
       P(mutex);  // 進入臨界區(qū)
       remove an item from buffer;  //從緩沖區(qū)中取出數(shù)據(jù)
       V (mutex);  //離開臨界區(qū)，釋放互斥信號量
       V (empty) ;  //空緩沖區(qū)數(shù)加1
       consume the item;  //消費數(shù)據(jù)
   }
}

讀者寫者問題

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

int count = 0;  //用于記錄當(dāng)前的讀者數(shù)量
semaphore mutex = 1;  //用于保護更新count變量時的互斥
semaphore rw=1;  //用于保證讀者和寫者互斥地訪問文件
semaphore w=1;  //用于實現(xiàn)“寫優(yōu)先”
writer(){
    while(1){
        P(w);  //在無寫進程請求時進入
        P(rw);  //互斥訪問共享文件
        writing;  //寫入
        V(rw);  // 釋放共享文件
        V(w) ;  //恢復(fù)對共享支件的訪問
    }
}
reader () {  //讀者進程
    while (1){
        P (w) ;  // 在無寫進程請求時進入
        P (mutex);  // 互斥訪問count變量
        if (count==0)  //當(dāng)?shù)谝粋€讀進程讀共享文件時
            P(rw);  //阻止寫進程寫
        count++;  //讀者計數(shù)器加1
        V (mutex) ;  //釋放互斥變量count
        V(w);  //恢復(fù)對共享文件的訪問
        reading;  //讀取
        P (mutex) ; //互斥訪問count變量
        count--;  //讀者計數(shù)器減1
        if (count==0)  //當(dāng)最后一個讀進程讀完共享文件
            V(rw);  //允許寫進程寫
        V (mutex);  //釋放互斥變量count
    }
}