OS4(同步軟硬件方法)

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

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

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

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

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

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

(1)進(jìn)程互斥的軟件方法（補(bǔ)充）

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

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

intturn=0；

//公共變量

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

Criticalsection；//臨界區(qū)

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

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

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

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

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

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

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

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

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

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

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

試問該算法能夠保證兩個(gè)進(jìn)程互斥的進(jìn)入臨界區(qū)？會(huì)不會(huì)出現(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)進(jìn)程互斥的硬件方法P51完全利用軟件方法，有很大局限性（如不適于多進(jìn)程），實(shí)現(xiàn)過于復(fù)雜，需要高的編程技巧?？梢岳媚承┯布噶睢渥x寫操作由一條指令完成，因而保證讀操作與寫操作不被打斷；兩種硬件方法：

中斷屏蔽方法

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