本文地址：http://www.CUOXin.com/archimedes/p/os-PRocess-management2.html，轉載請注明源地址。
進程同步
進程同步：指對多個相關進程在執行次序上進行協調；
同步的任務：使系統中各進程之間能有效地共享資源和相互合作，從而使程序的執行具有可再現性；
系統中各進程之間在邏輯上的相互制約的關系：
直接關系—同步
間接關系—互斥
用來實現同步的機制稱為同步機制。如：系統中各進程之間在邏輯上存在著兩種制約關系：
直接相互制約關系/相互合作關系（進程同步）：即為完成同一個任務的各進程之間，因需要協調它們的工作而相互等待、相互交換信息所產生的直接制約關系。
間接相互制約關系/資源共享關系（進程互斥）：是進程共享獨占型資源而必須互斥執行的間接制約關系。
同步與互斥比較：
2、臨界資源、臨界區一次只允許一個進程使用的共享資源稱為臨界資源，如打印機，繪圖機，變量，數據等，各進程間采取互斥方式實現對這種臨界資源的共享，從而實現并發進程的封閉性。例：生產者-消費者問題
一組生產者向一組消費者提供產品，它們共享一個緩沖池，生產者向其中投放產品，消費者從中取得產品。它是許多相互合作進程的抽象，如輸入進程與計算進程；計算進程與打印進程等。
設緩沖池的長度為n（n>0），一群生產者進程P1,P2,…，Pm，一群消費者進程C1,C2,…，Ck，如圖所示。假定生產者和消費者是相互等效，只要緩沖池未滿，生產者就可以把產品送入緩沖區，類似地，只要緩沖池未空，消費者便可以從緩沖區取走產品并消耗它。
生產者和消費者進程是以異步方式運行的，但必須保持同步關系，即禁止生產者向滿的緩沖池輸送產品，也禁止消費者從空的緩沖池提取產品。
int n; //n為緩沖池中緩沖區的個數；buffer:array[0..n-1] of item; //buffer為具有n個緩沖區的緩沖池；in,out:0..n-1; //in和out為指針，分別指向下一個可投放產品的緩沖區和下一個可獲取產品的緩沖區counter:0..n;生產者消費者進程可分別描述為：
void producer() //生產者{ while(1) { …… produce an item in nextp; //生產一個產品 …… if (counter <= n) { //當生產的數目等于count的時候停止 buffer[in] = nextp; in = (in + 1) mod n; counter = counter + 1; } else { break; } }}void consumer() //消費者{ while(1) { while (counter > 0) { nextc = buffer[out]; out = (out + 1) mod n; counter = counter - 1; consume the item in nextc; //消費一個產品 } break; }}并發執行時會出現差錯，問題出在兩進程共享的變量counter上用機器語言實現變量的加1、減1的操作為：
//變量counter加1: register1 = counter;register1 = register1 + 1;counter = register1;//變量counter減1: register2 = counter;register2 = register2-1;counter = register2;
若按另一順序對變量進行修改，會得到什么結果？
register1 = counter;register1 = register1 + 1;register2 = counter;register2 = register2 - 1;counter = register1;counter = register2;
為了保證臨界資源的正確使用，可以把一個訪問臨界資源的循環進程描述如下：
增加在臨界區前面的一段代碼，用于檢查所要訪問的臨界資源此刻是否被訪問。
退出區(Exit Section)增加在臨界區后面的一段代碼，用于將臨界資源的訪問標志恢復為未被訪問標志。
剩余區(Remainder Section)進程中除了進入區、臨界區及退出區之外的其余代碼。
要進入臨界區的若干進程必須滿足：
（1）一次只允許一個進程進入臨界區
（2）任何時候，處于臨界區的進程不得多于一個
（3）進入臨界區的進程要在有限的時間內退出
（4）如果不能進入自己的臨界區，則應讓出處理機資源
解決臨界區（互斥）問題的幾類方法：
（1）軟件方法和硬件方法
（2） P-V操作
（3）管程機制
3、同步機制應遵循的規則空閑讓進:當無進程處于臨界區時，表明臨界資源處于空閑狀態，應允許一個請求進入臨界區的進程立即進入自己的臨界區，以有效地利用臨界資源。
忙則等待:當已有進程進入臨界區時，表明臨界資源正在被訪問，因而其他試圖進入臨界區的進程必須等待，以保證對臨界資源的互斥訪問。
有限等待:對要求訪問臨界資源的進程，應保證在有限時間內能進入自己的臨界區，以免陷入“死等”狀態。
讓權等待:當進程不能進入自己的臨界區時，應立即釋放處理機，以免進程陷入“忙等”。
信號量機制是荷蘭科學家E.W.Dijkstra在1965年提出的一種同步機制，也稱為P、V操作。由最初的整型信號量發展為記錄型信號量，進而發展為信號量集機制。1、整型信號量整型信號量——非負整數，除了初始化（即賦初值：必須置一次且只能置一次初值，初值不能為負數）外，只能通過兩個原子操作wait和signal（或者叫P、V操作）來訪問（即信號量的值僅能由這兩個原子操作來改變 ）。wait和signal操作描述：
wait(S)： while S <= 0 do no-op； 測試有無可用資源
S = S - 1; 可用資源數減一個單位
signal(S): S = S + 1;
主要問題：只要S <= 0， wait操作就不斷地測試（忙等），因而，未做到“讓權等待”。
2、記錄型信號量基本思想1、設置一個代表資源數目的整型變量value（資源信號量）
2、設置一鏈表L用于鏈接所有等待訪問同一資源的等待進程
記錄型信號量的數據結構Type semaphore=record
value:integer;
L: list of process;
end
Var S: semaphore;
wait和signal操作描述：//調用阻塞原語將該進程狀態置為//等待狀態，將該進程的PCB插入//相應的等待隊列S.L末尾; wait(S)： S.value:=S.value-1; if S.value<0 then block(S.L);//調用喚醒原語喚醒相應等待隊列//S.L中等待的一個進程,改變其狀//態為就緒態,并將其插入就緒隊列 signal(S): S.value:=S.value+1; if S.value£0 then wakeup(S.L);
在記錄型信號量機制中：
S.value的初值表示系統中某類資源的數目。
S.value的初值為1，S為互斥信號量；
S.value的初值大于1，S為資源信號量；
在記錄型信號量機制中
每次wait(S)操作意味著進程請求一個單位的資源，資源數目減1。當S.value<0時表示資源已分配完畢，進程調用Block()原語進行自我阻塞，放棄處理機，并插入到信號量鏈表S.L中。此時，|S.value| 表示在該信號量鏈表中已阻塞進程的數目。
每次signal(S)表示執行進程釋放一個單位資源，資源數目加1。若加1后仍有S.value<=0，則表示在該信號量鏈表中，還有等待該資源的進程，則調用Wakeup()原語，將鏈表中第一個進程喚醒。
AND型信號量（了解）
一般信號量集（了解）
信號量的應用1、利用信號量實現進程互斥利用信號量可以方便地解決臨界區問題（進程互斥）（見后面的圖）。為臨界資源設置一互斥信號量lock，初值為1，則實現進程A、B、C互斥的描述：
完整的運行順序圖如下：
2、利用信號量描述前趨關系方法：
若圖中存在結點S1指向結點S2的有向邊，表示進程P1中的程序段S1應該先執行，而進程P2中的程序段S2后執行。設置一個信號量s,初值為0，將V(s)放在S1后面，而在S2前面先執行P(s)。
進程P1的語句序列為：S1;V(s)
進程P2的語句序列為：P(s);S2
例：利用信號量來描述前趨圖關系
具有8個結點的前趨圖。前趨圖中共有有向邊10條，可設10個信號量，初值均為0；有8個結點，可設計成8個并發進程，具體描述如下:
struct semaphore a,b,c,d,e,f,g,h,i,j=0,0,0,0,0,0,0,0,0,0cobegin {S1;V(a);V(b);V(c);} {P(a);S2;V(d);} {P(b);S3;V(e);V(f);} {P(c);S4;V(g);} {P(d);P(e);S5;V(h);} {P(f);P(g);S6;V(i)} {P(h);P(i);S7;V(j);} {P(j);S8;}coend參考資料《華東理工大學 操作系統》新聞熱點
疑難解答
