OS4(同步軟硬件方法)

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

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

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

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

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

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

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

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

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

intturn=0；

//公共變量

進程P0：do{while(turn!=0);//進入?yún)^(qū)

Criticalsection；//臨界區(qū)

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

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

flag[0]=true;//進入?yún)^(qū)P0的臨界區(qū)代碼；//臨界區(qū)

flag[0]=false;//退出區(qū)

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

進程P0：當兩個進程都未進入臨界區(qū)時，它們各自的訪問標志都為false，若此時兩個進程幾乎同時都想進入臨界區(qū)，并且都發(fā)現(xiàn)對方標志值為false，兩進程同時進入了各自的臨界區(qū)，違背了臨界區(qū)訪問的“忙則等待”原則。操作系統(tǒng)算法3：鎖變量方法（雙標志、后檢查）缺點：Pi和Pj可能都進入不了臨界區(qū)。按下面序列執(zhí)行時，會都進不了臨界區(qū)："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的區(qū)別在于先修改后檢查。可防止兩個進程同時進入臨界區(qū)。enumboolean{false,true};booleanflag[2]={false,false};//公共變量以進程P0、P1為例，類C語法的偽碼描述P0進程如下：

進程P0：do{flag[0]=true;//進入?yún)^(qū)while(flag[1]);//進入?yún)^(qū)P0的臨界區(qū)代碼；//臨界區(qū)

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

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

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

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

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

i)gotoretry;turn=-1;Criticalsection;turn:=0;remaindersection;Repeat操作系統(tǒng)(2)進程互斥的硬件方法P51完全利用軟件方法，有很大局限性（如不適于多進程），實現(xiàn)過于復雜，需要高的編程技巧?？梢岳媚承┯布噶睢渥x寫操作由一條指令完成，因而保證讀操作與寫操作不被打斷；兩種硬件方法：

中斷屏蔽方法

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