操作系統2.3進程同步2.3.1進程同步的基本概念2.3.2信號量(semaphore)2.3.3經典進程同步問題2.3.4進程間通信操作系統正常行車到站停車開車售票開車門關車門司機售票員合作合作進程間的合作關系操作系統打印進程1打印進程2打印打印獲得打印數據獲得打印數據競爭進程間競爭資源操作系統計算進程打印進程計算結果送到Buffer從Buffer中取數Buffer競爭競爭完成數據計算打印通知打印進程打印通知計算進程送下一個數合作與競爭合作合作操作系統相互合作競爭資源司機與售票員多個打印者計算者與打印者進程間存在兩種關系協調好這些關系的過程——進程的同步操作順序沖突共享外設、內存（變量）等資源操作系統競爭資源關系——直接相互制約：

進程同步的主要任務：保證諸進程能互斥地訪問臨界資源相互合作關系——間接相互制約：

進程同步的主要任務：保證相互合作的諸進程在執行次序上的協調——同步。2.3.1進程同步的基本概念P48操作系統計算進程打印進程計算結果送到Buffer從Buffer中取數Buffer互斥互斥向打印進程發信號通知其從Buffer里取數Buffer空？否是完成數據計算打印向計算進程發信號通知其向Buffer送數Buffer空？否是協調計算進程與打印進程的同步操作系統1.臨界資源對于計算機中的有些軟硬件資源，當多個進程對其進行訪問時（關鍵是進行寫入或修改），必須互斥地進行，這些一次只允許一個進程使用的資源稱為臨界資源(criticalresource)。打印機、內存變量、指針、數組等都是臨界資源。生活中的例子如：電話機等。臨界資源需要采用互斥方式，實現對資源的共享。操作系統2、臨界區每個進程中訪問臨界資源的那段程序段稱為臨界區（criticalsection）。操作系統訪問臨界資源的循環進程Untilfalse;EntrysectionCriticalsection;ExitsectionRemaindersection;Repeat

進入區：進入臨界區之前，檢查可否進入臨界區的一段代碼。如果可以進入臨界區，通常設置相應“正在訪問臨界區”標志；臨界區：進程中訪問臨界資源的一段代碼；

退出區：用于將"正在訪問臨界區"標志清除。

剩余區：代碼中的其余部分。操作系統進入區臨界區退出區進入區臨界區退出區........................阻塞等待資源釋放改變資源狀態釋放資源進程1進程2進入區、退出區各部分的作用互斥是針對不同進程訪問同一臨界資源。進程互斥進程互斥進程互斥是指若干共享臨界資源的進程彼此交換信息以保證排他性的進入各自的臨界區，即當若干個進程都要使用某一共享資源時，任何時刻最多只允許一個進程使用該資源，其他要使用該資源的進程必須等待，直到占有資源者釋放該資源所謂同步是指若干相互合作的進程彼此交換信息以保證在執行次序上的協調。進程同步：進程同步是指若干相互合作的進程在一些關鍵點上可能需要互相等待或互相交換信息。進程同步進程互斥可在具有一定邏輯關系的伙伴進程之間，也可在非伙伴進程之間；同步發生在相互有邏輯關系的伙伴進程之間。進程同步是一般情況，互斥是同步的一種特殊情況。進程同步和互斥的關系操作系統3、同步機制應遵循的準則空閑則入：其他進程均不處于臨界區；忙則等待：已有進程處于其臨界區；有限等待：等待進入臨界區的進程不能"死等"；讓權等待：不能進入臨界區的進程，應釋放CPU（如轉換到阻塞狀態）解決互斥問題既可采用軟件方法，也可采用硬件方法。4、進程互斥的基本方法軟件實現方法就是在進入區設置和檢查一些標志來標明是否有進程在臨界區中，如果已有進程在臨界區中，則在進入區通過循環檢查進行等待，進程離開臨界區后則在退出區修改標志。有兩個進程Pi和Pj，它們互斥的共享某個臨界資源。Pi和Pj是循環進程，它們執行一個無限循環程序，每次使用該資源一個有限的時間間隔。

(1)進程互斥的軟件方法（補充）

例如:操作系統算法1：強制輪換法（單標志）

設立一個公用整型變量turn：描述允許進入臨界區的進程標識在進入區檢查是否允許本進程進入:turn為i時,進程Pi可進入;在退出區修改turn的值：進程Pi退出時,改turn為j；缺點： 強制輪流進入臨界區，沒有考慮進程的實際需要。容易造成資源利用不充分： 在Pi出讓臨界區之后，Pj使用臨界區之前，Pi不可能再次使用臨界區；Untilfalse;RepeatWhileturnidono_opCriticalsection;turn:=j;remaindersection;對兩個進程Pi,Pj，其中的Pi描述如下圖以進程P0、P1為例，類C語法的偽碼描述P0進程如下：

intturn=0；

//公共變量

進程P0：do{while(turn!=0);//進入區

Criticalsection；//臨界區

turn=1;//退出區P0其他代碼；//剩余區

}while(true);P0退出臨界區后將turn置1，以便允許P1進入臨界區，但若P1暫時并未要求訪問該臨界資源，恰好P0又想再次訪問該臨界資源，則P0將無法進入臨界區。此算法不能保證“空閑讓進”準則。操作系統算法2：鎖變量方法（雙標志、先檢查）優點:不用交替進入,可連續使用缺點：Pi和Pj可能同時進入臨界區。按下面序列執行時，會同時進入："Pi<a>Pj<a>Pi<b>Pj<b>"。Untilfalse;Whileflag[j]dono_op<a>Flag[i]:=true；<b>Criticalsection;Flag[i]:=false;remaindersection;Repeat設立一個標志數組flag[]：描述進程是否在臨界區，初值均為FALSE。先檢查，后修改：在進入區檢查另一個進程是否在臨界區，不在時修改本進程在臨界區的標志；在退出區修改本進程在臨界區的標志；do{while(flag[1]);//進入區

flag[0]=true;//進入區P0的臨界區代碼；//臨界區

flag[0]=false;//退出區

P0的其他代碼；//剩余區}while(true);enumboolean{false,true};booleanflag[2]={false,false};//公共變量以進程P0、P1為例，類C語法的偽碼描述P0進程如下：

進程P0：當兩個進程都未進入臨界區時，它們各自的訪問標志都為false，若此時兩個進程幾乎同時都想進入臨界區，并且都發現對方標志值為false，兩進程同時進入了各自的臨界區，違背了臨界區訪問的“忙則等待”原則。操作系統算法3：鎖變量方法（雙標志、后檢查）缺點：Pi和Pj可能都進入不了臨界區。按下面序列執行時，會都進不了臨界區："Pi<a>Pj<a>Pi<b>Pj<b>"。Untilfalse;Flag[i]:=true；<a>Whileflag[j]dono_op<b>Criticalsection;Flag[i]:=false;remaindersection;Repeat類似于算法2，與2的區別在于先修改后檢查。可防止兩個進程同時進入臨界區。enumboolean{false,true};booleanflag[2]={false,false};//公共變量以進程P0、P1為例，類C語法的偽碼描述P0進程如下：

進程P0：do{flag[0]=true;//進入區while(flag[1]);//進入區P0的臨界區代碼；//臨界區

flag[0]=false;//退出區P0的其他代碼；//剩余區}while(true);當兩個進程幾乎同時都想進入臨界區時，由于“先修改、后檢查”，它們分別將自己的標志置為true，并且同時去檢查對方的狀態，發現對方也是true，得知對方也要進入臨界區，于是雙方互相謙讓，結果是誰也進不了臨界區。算法3可以有效防止兩個進程同時進入臨界區，但存在兩個進程都進入不了臨界區的問題，即發生“饑餓”現象。在一個可以預見的時間內，一個或多個進程得不到滿足，如都不能訪問臨界資源。在一個動態系統中，操作系統對每類系統資源(臨界資源)需要確定一個分配策略，有時資源分配策略是不公平的，即不能保證等待時間上界的存在。當進程等待時間給進程推進和響應帶明顯影響時稱發生了進程饑餓。“饑餓”現象產生“饑餓”現象的原因：操作系統算法4(Peterson’sAlgorithm)：

先修改、后檢查、后修改者等待結合算法1和算法3，是正確的算法turn=j;描述可進入的進程（同時修改標志時）在進入區先修改后檢查，并檢查并發修改的先后：檢查對方flag，如果不在臨界區則自己進入——空閑則入否則再檢查turn：保存的是較晚的一次賦值，則較晚的進程等待，較早的進程進入——先到先入，后到等待Untilfalse;Flag[i]:=true;turn:=j;While(flag[j]andturn=j)dono_opCriticalsection;Flag[i]:=false;remaindersection;Repeatdo{flag[0]=true; //進入區turn=1; //進入區while(flag[1]&&turn==1); //進入區P0的臨界區代碼； //臨界區

flag[0]=false; //退出區P0的其他代碼； //剩余區}while(true);enumboolean{false,true};booleanflag[2]={false,false};intturn;以進程P0、P1為例，類C語法的偽碼描述P0進程如下：

進程P0：操作系統練習：假設只有P0和P1兩個進程競爭臨界資源，關于臨界問題的一個算法如下，i為0或1。

試問該算法能夠保證兩個進程互斥的進入臨界區？會不會出現死等（饑餓）現象？Untilfalse;retry:if(turn-1)turn:=i;if(turn

i)gotoretry;turn=-1;Criticalsection;turn:=0;remaindersection;Repeat操作系統(2)進程互斥的硬件方法P51完全利用軟件方法，有很大局限性（如不適于多進程），實現過于復雜，需要高的編程技巧。可以利用某些硬件指令——其讀寫操作由一條指令完成，因而保證讀操作與寫操作不被打斷；兩種硬件方法：

中斷屏蔽方法

硬件指令方法(TS指令，Swap指令)…關中斷臨界區開中斷…優點：簡單、有效缺點：限制了處理機交替執行程序的能力，執行效率降低。將關中斷的權力交給用戶進程，將使得某一個進程關中斷后若不再開中斷，則系統可能會因此終止。1.中斷屏蔽方法操作系統2.利用TS實現進程互斥該指令讀出標志后設置為TRUEbooleanTS(boolean*lock){booleanold;old=*lock;*lock=TRUE;returnold;}lock表示資源的兩種狀態：TRUE表示正被占用，FALSE表示空閑Test-and-Set指令操作系統TS實現進程互斥Untilfalse;WhileTS(lock)doskipCriticalsection;lock:=false;remaindersection;Repeat利用TS實現進程互斥：每個臨界資源設置一個公共布爾變量lock，初值為FALSE在進入區利用TS進行