操作系統(tǒng)課件章進(jìn)程管理

2.3進(jìn)程的同步與通信

進(jìn)程間的聯(lián)系進(jìn)程的同步機(jī)制─信號(hào)量及wait-signal操作（解決進(jìn)程同步互斥問(wèn)題）舊稱P-V操作2.3.1進(jìn)程同步的基本概念1.進(jìn)程之間的兩種相互制約關(guān)系進(jìn)程的并發(fā)執(zhí)行雖然提高了資源利用率,但由于進(jìn)程的異步性,會(huì)給系統(tǒng)造成混亂。為了使并發(fā)執(zhí)行的各進(jìn)程都能正確執(zhí)行,使它們之間能有效地共享資源和相互合作,必須研究并發(fā)執(zhí)行的各進(jìn)程之間的相互制約關(guān)系,采取一定的措施使系統(tǒng)中諸進(jìn)程有條不紊的同步向前推進(jìn)。進(jìn)程之間有兩種相互制約關(guān)系：間接相互制約關(guān)系(資源共享關(guān)系)

直接相互制約關(guān)系(功能合作關(guān)系)1)間接相互制約關(guān)系(資源共享關(guān)系、互斥關(guān)系)

由于共享資源,使得系統(tǒng)中本來(lái)沒(méi)有邏輯關(guān)系的進(jìn)程,因相互競(jìng)爭(zhēng)資源而產(chǎn)生了制約關(guān)系。例如:進(jìn)程P1和P2在運(yùn)行中都要使用打印機(jī),為了保證各進(jìn)程輸出的完整,打印機(jī)必須互斥訪問(wèn)(獨(dú)占使用)。這樣,一旦系統(tǒng)將打印機(jī)分配給進(jìn)程P1,進(jìn)程P2就必須等待,直到P1用完打印機(jī)并釋放后,P2才能使用。這種因共享資源而使并發(fā)執(zhí)行的各進(jìn)程之間產(chǎn)生的關(guān)系,叫做間接制約關(guān)系,又叫做互斥(mutualexclusion)關(guān)系。這種關(guān)系可用“進(jìn)程-資源-進(jìn)程”來(lái)描述。2)直接制約關(guān)系(相互功能合作關(guān)系、同步關(guān)系)

通常,一個(gè)用戶作業(yè)要涉及一組并發(fā)進(jìn)程(輸入、計(jì)算和輸出進(jìn)程),這些進(jìn)程必須相互協(xié)作共同完成這項(xiàng)任務(wù)。具體說(shuō),在運(yùn)行過(guò)程中,某進(jìn)程可能要在某些同步點(diǎn)上等待另一伙伴(協(xié)作進(jìn)程)為它提供消息,在未獲得消息之前,該進(jìn)程處于等待狀態(tài),獲得消息后被喚醒進(jìn)入就緒態(tài),此后,才能繼續(xù)運(yùn)行。進(jìn)程間的這種制約關(guān)系叫做直接制約關(guān)系,又叫同步(synchronism)關(guān)系。這種關(guān)系可用“進(jìn)程-進(jìn)程”來(lái)描述。3)進(jìn)程通訊進(jìn)程通訊,就是指進(jìn)程之間的信息交換。處理進(jìn)程的同步與互斥兩種關(guān)系所交換的信息量很少，所以將它們稱做進(jìn)程的低級(jí)通信。例:司機(jī)P1售票員P2REPEATREPEAT

啟動(dòng)關(guān)門(mén)

正常行駛售票

到站停開(kāi)門(mén)

UNTILFALSEUNTILFALSE

同步與互斥表示了進(jìn)程之間的相互依賴又相互制約、相互合作又相互競(jìng)爭(zhēng)的關(guān)系2.臨界資源和臨界區(qū)

進(jìn)程的互斥是由于共享資源而引起的,為描述這類情況,引入臨界資源和臨界區(qū)的概念。臨界資源(互斥資源)：criticalresource

系統(tǒng)中一次只允許一個(gè)進(jìn)程訪問(wèn)的資源;這些資源既包括I/O設(shè)備,如打印機(jī)等資源,也包括軟件資源,如共享變量、共享文件等。臨界區(qū)(互斥區(qū)):criticalsection

并發(fā)執(zhí)行的進(jìn)程中,訪問(wèn)臨界資源的必須互斥執(zhí)行的程序段叫臨界區(qū)。臨界區(qū)分散在每個(gè)要并發(fā)執(zhí)行的進(jìn)程中,它們都對(duì)某個(gè)共享的數(shù)據(jù)結(jié)構(gòu)(共享資源)進(jìn)行訪問(wèn)P1:P2:

變量a是臨界資源

C1、C2、C3是臨界區(qū)對(duì)a應(yīng)互斥訪問(wèn)P3:C3)C1)C2)……a:=a+1print(a)…………a:=a+1print(a)…………ifa<0thena:=a+1elsea:=a-1……共享變量臨界區(qū)2臨界區(qū)n臨界區(qū)1SolutionRequirementsMutualExclusionOnlyoneprocesscanbeinthecriticalsectionatanytimeProgressDecisiononwhoentersCScannotbeindefinitelypostponedNodeadlockBoundedWaitingBoundon#timesotherscanenterCS,whileIamwaitingNolivelockAlsoefficient(noextraresources),fair,simple,…3.同步機(jī)制應(yīng)遵循的原則(進(jìn)入臨界區(qū)的原則)空閑讓進(jìn)：當(dāng)無(wú)進(jìn)程在臨界區(qū)時(shí)，任何一個(gè)有權(quán)使用臨界區(qū)的進(jìn)程可進(jìn)入。(多中擇一):當(dāng)沒(méi)有進(jìn)程在臨界區(qū)，而同時(shí)有多個(gè)進(jìn)程要求進(jìn)入臨界區(qū)，只能讓其中之一進(jìn)入忙則等待：當(dāng)有進(jìn)程在臨界區(qū)時(shí)，其它試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，即不許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入臨界區(qū)有限等待：任何進(jìn)入臨界區(qū)的要求應(yīng)在有限的時(shí)間內(nèi)得到滿足讓權(quán)等待：處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU

以免進(jìn)程陷入“忙等”。

硬件硬件指令(原語(yǔ)不可中斷)和屏蔽中斷兩種辦法。軟件編程解決:進(jìn)入臨界區(qū)之前附加一段檢查的代碼(進(jìn)入?yún)^(qū)),以保證互斥進(jìn)入,在臨界區(qū)后各附加程序(退出區(qū))恢復(fù)標(biāo)志,表明已從臨界區(qū)退出,其它進(jìn)程可進(jìn)入。缺點(diǎn):需要高的編程技巧,忙等待。2.3.2如何解決互斥問(wèn)題軟件解法(1)

varfree:boolean;{true:臨界區(qū)空(初值)false:非空}

procp(n);{每個(gè)并發(fā)進(jìn)程}……

L:iffreethenbeginfree:=false;

criticalsectionend

elsegotoL;

free:=true;……問(wèn)題:當(dāng)p(i)測(cè)試free為true,還未將free改為false時(shí),此時(shí)恰好p(j)也測(cè)試free,其值仍然是true,使兩個(gè)進(jìn)程都進(jìn)入臨界區(qū)違反了忙則等待的原則。begin{主程序}Parbeginp(1)；p(2)；…p(n)；

parendend；軟件解法(2)varturn:boolean;

{當(dāng)turn=true時(shí)P可進(jìn)入臨界區(qū),否則Q可進(jìn)入臨界區(qū)}P)…Q)…repeatuntilturn;repeatuntilnotturn;criticalsectioncriticalsectionturn:=flase;turn:=true;……問(wèn)題:解決了解法(1)的問(wèn)題,不會(huì)使兩個(gè)進(jìn)程都進(jìn)入臨界區(qū),但P和Q必須輪流進(jìn)入臨界區(qū),當(dāng)P退出臨界區(qū)后turn=flase,此時(shí)臨界區(qū)空閑,但P不能再進(jìn)入臨界區(qū),違反了空閑讓進(jìn)的原則。

軟件解法：(3)

varpturn,qturn:boolean;初值為false{P進(jìn)入臨界區(qū)的條件:pturn¬qturnQ進(jìn)入臨界區(qū)的條件:notpturn&qturn}P)……Q)……pturn:=true;qturn:=ture;while(qturn)do;while(pturn)do;

criticalsectioncriticalsectionpturn:=false;qturn:=false

…...…...問(wèn)題:似乎解決了解法(2)的問(wèn)題,P和Q不必輪流進(jìn)入臨界區(qū),但當(dāng)P和Q同時(shí)執(zhí)行pturn=true;qturn=true;時(shí),臨界區(qū)空閑,而P和Q都不能進(jìn)入臨界區(qū),仍然違反空閑讓進(jìn)的原則。

軟件解法(4):

在解法(3)基礎(chǔ)上引入turn枚舉類型(初值任意)varturn:(p,q)pturn,qturn:boolean;初值為false

{P等待的條件:qturn&turn=pQ等待的條件:pturn&turn=q}P)……Q)……pturn:=true;qturn:=ture;turn:=p;turn:=q;while(qturn&turn=p)do;while(pturn&turn=q)do;

criticalsectioncriticalsectionpturn:=false;qturn:=false

…...…...

可見(jiàn)軟件法需要很高的編程技巧,而且“忙等”效率低。vark:boolean;{全局變量k=true表示資源已被占用}funcLock(vartarget:boolean):boolean;{TestandSet}begin{加鎖原語(yǔ)或測(cè)試并設(shè)置原語(yǔ)不可中斷}Lock:=target;target:=trueend;procp(n);{每個(gè)并發(fā)進(jìn)程}……whileLock(k)do;

criticalsectionk:=false;{開(kāi)鎖}……硬件解法(1)—用硬件指令“測(cè)試并設(shè)置”begin{主程序}k:=false;

{初值表示資源可用}parbeginp(1)；p(2)；…p(n)；

parendend；varlock:boolean;{每組共享定義一個(gè)全局變量}functionswap(vara,b:boolean);{交換指令不可中斷}vartemp:boolean;begintemp:=a;a:=b;b:=tempend;procp;{每個(gè)并發(fā)進(jìn)程}varkey:boolean;{定義一個(gè)局部變量}……key:=true;repeatswap(lock,key)untilkey=false;

criticalsection

{局部變量key存儲(chǔ)lock的原值}lock:=false;……硬件解法(2)—用硬件指令“交換”指令硬件解法(3)—“開(kāi)關(guān)中斷”指令CPU從某進(jìn)程轉(zhuǎn)接到另一進(jìn)程是由于時(shí)鐘中斷(時(shí)間片到)或其它中斷引起的。當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū)前,關(guān)閉所有的中斷,其它進(jìn)程就不可能進(jìn)入臨界區(qū)。當(dāng)進(jìn)程退出臨界區(qū)后,再開(kāi)中斷。此后要進(jìn)入臨界區(qū)的進(jìn)程就可進(jìn)入。描述如下：關(guān)中斷(disable)criticalsection開(kāi)中斷(enable)開(kāi)、關(guān)中斷可以保證各進(jìn)程互斥地進(jìn)入臨界區(qū)。這種方法簡(jiǎn)單,但系統(tǒng)要付出較高代價(jià)。缺點(diǎn)是：限制了處理機(jī)交叉執(zhí)行程序的能力。2.3.3信號(hào)量機(jī)制同步機(jī)制：信號(hào)量及wait-signal操作；管程；條件臨界域；路徑表達(dá)式等（用于集中式系統(tǒng)中）會(huì)合；通信順序進(jìn)程；分布進(jìn)程；遠(yuǎn)程過(guò)程調(diào)用等（適用于分布式系統(tǒng)中）同步機(jī)制應(yīng)滿足的基本要求：描述能力、可以實(shí)現(xiàn)、效率高、使用方便信號(hào)量(Semaphores)共享資源的使用信號(hào)的量:1965年荷蘭學(xué)者Dijkstra提出信號(hào)量機(jī)制，現(xiàn)已被廣泛用于解決各種互斥和同步問(wèn)題。1.整型信號(hào)量：管理控制鐵路交通的重要工具是信號(hào)燈。利用信號(hào)燈的狀態(tài)(顏色)控制火車的通行。單段鐵路任何時(shí)刻只允許一列火車通行(相當(dāng)于臨界區(qū)),遇紅燈(表示路段被占用)應(yīng)等待,遇綠燈可進(jìn)入(同時(shí)紅燈亮禁止其它火車進(jìn)入),駛出后綠燈亮,信號(hào)燈標(biāo)志路段資源的占用情況。為了管理各并發(fā)進(jìn)程對(duì)共享資源的使用,引入表示共享資源的使用信號(hào)的量——信號(hào)量的概念;它被定義為一個(gè)整型量S;S<=0表示該資源已被占用(另一進(jìn)程在臨界區(qū)相當(dāng)于紅燈亮);S>0表示資源可用(無(wú)進(jìn)程在臨界區(qū)相當(dāng)于綠燈亮);某進(jìn)程企圖進(jìn)入臨界區(qū)時(shí),若S<=0禁止進(jìn)入,若S>0允許進(jìn)入;信號(hào)量S只能通過(guò)兩個(gè)標(biāo)準(zhǔn)原子操作(不可中斷)wait(S)和signal(S)來(lái)訪問(wèn)。過(guò)去它們被稱為P-V操作,可描述為：wait(S)：whileS<=0do;{有進(jìn)程在臨界區(qū)空循環(huán)}S:=S-1;signal(S)：

S:=S+1;進(jìn)入?yún)^(qū)執(zhí)行wait(S)操作,退出區(qū)執(zhí)行signal(S),例如:vars:integer;s:=1;parbeginp1:beginp2:begin……wait(s);wait(s);

臨界區(qū)代碼臨界區(qū)代碼

signal(s);signal(s);……end;end;parendwait(S)操作中,當(dāng)S<=0時(shí)會(huì)使進(jìn)程處于“忙等”狀態(tài)。2.記錄型信號(hào)量為了消除“忙等”現(xiàn)象,若資源被占用應(yīng)自我阻塞,記錄型信號(hào)量用記錄結(jié)構(gòu),增加等待隊(duì)列頭指針域：typesemaphore=recordvalue:integer;L:listofprocess；

end；

s:semaphore;S.value的初值表示系統(tǒng)中該類資源的數(shù)目(又稱資源信號(hào)量)。運(yùn)行中S.value>0表示該資源可用的數(shù)目,S.value<0的絕對(duì)值表示在該資源的等待鏈表中已阻塞進(jìn)程的數(shù)目,S.L則為該鏈隊(duì)列頭指針。若S.value初值為1則轉(zhuǎn)化為互斥信號(hào)量。相應(yīng)的wait(S)signal(S)操作可描述為：procedurewait(s:semaphore);begins.value:=s.value-1;{先減1再判斷}ifs.value<0thenblock(s.L)end;其中:block(s.L)原語(yǔ)是將該進(jìn)程自我阻塞,置為等待狀態(tài),并將它的PCB插到信號(hào)量隊(duì)列s.L的末尾。將來(lái)被喚醒后,運(yùn)行應(yīng)從wait之后開(kāi)始。proceduresignal(s:semaphore);begins.value:=s.value+1;ifs.value<=0thenwakeup(s.L)end;{s.value<=0表示有等待s的進(jìn)程}其中:wakeup(s.L)原語(yǔ)是喚醒信號(hào)量等待隊(duì)列s.L中的第一個(gè)進(jìn)程,將其改為就緒態(tài)插入就緒隊(duì)列。

(等待隊(duì)列中的進(jìn)程都已執(zhí)行過(guò)wait操作)P(S)V(S)P(S)V(S)P(S)V(S)互斥區(qū)P1P2Pn利用信號(hào)量實(shí)現(xiàn)進(jìn)程之間的互斥用記錄型信號(hào)量S解決n個(gè)進(jìn)程互斥地進(jìn)入臨界區(qū)的問(wèn)題,S取值范圍是+1~-(n-1);S的值為負(fù)時(shí),說(shuō)明有一個(gè)進(jìn)程正在臨界區(qū)執(zhí)行,其它欲進(jìn)入臨界區(qū)的進(jìn)程排在等待S的隊(duì)列中,等待的進(jìn)程數(shù)等于信號(hào)量值的絕對(duì)值。對(duì)應(yīng)于這種互斥信號(hào)量的初始值只能為1。vars:semaphore:=1;

{為表達(dá)方便簡(jiǎn)寫(xiě),只寫(xiě)整數(shù)部分parbegin

含義是s.value的初值設(shè)為1}

p1:beginp2:begin……

wait(s);wait(s);

臨界區(qū)代碼臨界區(qū)代碼

signal(s);signal(s);……end;end;p3:…p4:…parend

若p2先進(jìn)入臨界區(qū)此時(shí)s=0,p1要進(jìn)入,執(zhí)行wait(s);自我阻塞插入等待隊(duì)列此時(shí)s=-1,之后p4也要進(jìn)入,執(zhí)行wait(s);自我阻塞插入等待隊(duì)列此時(shí)s=-2;接著p2出臨界區(qū)s=-1,并將p1喚醒,p1就可以進(jìn)入臨界區(qū)(等待隊(duì)列中的進(jìn)程已執(zhí)行過(guò)wait,喚醒后從wait之后繼續(xù))。信號(hào)量的使用：必須置一次且只能置一次初值,初值不能為負(fù)數(shù)對(duì)信號(hào)量S只允許用wait、signal

操作訪問(wèn)。wait-signal操作為原語(yǔ)操作原語(yǔ)(primitiveoratomicaction)是由若干條機(jī)器指令構(gòu)成的完成某種特定功能的一段程序,具有不可分割性,在執(zhí)行過(guò)程中不允許被中斷。原語(yǔ)實(shí)現(xiàn)時(shí)必須：開(kāi)關(guān)中斷3.AND型信號(hào)量當(dāng)某進(jìn)程要先獲得多種臨界資源后才能執(zhí)行時(shí),容易處于僵持狀態(tài)(死鎖);如果對(duì)多種臨界資源要么全部分配到進(jìn)程,要么一種也不分配;則可避免死鎖的發(fā)生。為此在wait操作中增加AND條件,稱之為AND同步機(jī)制或同時(shí)wait操作,改名為Swait操作：

Swait(S1,S2,…Sn)ifS1≥1and…andSn≥1thenfori:=1tondoSi:=Si–1else自我阻塞,插到第一個(gè)Si<1的隊(duì)列Si.L,

并將程序計(jì)數(shù)定位到Swait操作的起點(diǎn);相應(yīng):Ssignal(S1,S2,…Sn)fori:=1tondo[Si:=Si+1;喚醒Si.L的所有進(jìn)程]4.信號(hào)量集在記錄型信號(hào)量機(jī)制中，當(dāng)一次需要d個(gè)某類資源時(shí)應(yīng)同時(shí)申請(qǐng)d個(gè)資源，該類資源的可用數(shù)低于某下限值t時(shí)不予分配，這樣就需要對(duì)AND型信號(hào)量機(jī)制加以擴(kuò)充，形成信號(hào)量集機(jī)制。Swait操作如下：Swait(S1,t1,d1,…Sn,tn,dn)ifS1≥t1and…andSn≥tnthenfori:=1tondoSi:=Si–dielse自我阻塞,插到第一個(gè)Si<ti的隊(duì)列Si.L,

并將程序計(jì)數(shù)定位到Swait操作的起點(diǎn);相應(yīng)的Ssignal操作為:Ssignal(S1,d1,…Sn,dn)fori:=1tondo[Si:=Si+di;喚醒Si.L的所有進(jìn)程]

信號(hào)量集的特殊情況AND信號(hào)量是所有ti、di都等于1的特例Swait(S,d,d)每次申請(qǐng)d個(gè)資源,資源數(shù)低于d個(gè)不分配。Swait(S,1,1)退化為一般記錄型信號(hào)量(操作有差別)Swait(S,1,0)特殊信號(hào)量,S>=1時(shí),允許多進(jìn)程進(jìn)入臨界區(qū),S=0時(shí)阻止所有進(jìn)程進(jìn)入臨界區(qū),相當(dāng)于一個(gè)開(kāi)關(guān)。幾種信號(hào)量的對(duì)比:

記錄型信號(hào)量整型信號(hào)量

有等待隊(duì)列無(wú)等待隊(duì)列

wait操作先減后判斷wait操作先判斷后減無(wú)資源則自我阻塞無(wú)資源則“忙等”

signal操作釋放資源后signal操作釋放資源后有等待進(jìn)程則喚醒

無(wú)喚醒操作有何差別?

記錄型信號(hào)量一般信號(hào)量集

一種資源多種資源每次申請(qǐng)一個(gè)每次每種申請(qǐng)di個(gè)少于1個(gè)不分配少于ti個(gè)不分配先減后判斷先判斷后減自我阻塞后程序計(jì)數(shù)定自我阻塞后程序計(jì)數(shù)定位到wait()操作之后位到Swait()操作的起點(diǎn)

signal喚醒第一個(gè)進(jìn)程Ssignal喚醒各種-所有

記錄型信號(hào)量

AND信號(hào)量一種資源多種資源先減后判斷先判斷后減自我阻塞后程序計(jì)數(shù)定自我阻塞后程序計(jì)數(shù)定位到wait()操作之后位到Swait()操作的起點(diǎn)

signal喚醒第一個(gè)進(jìn)程Ssignal喚醒各種-所有【習(xí)題】

P6818,19,212.3.4信號(hào)量應(yīng)用1.利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系

當(dāng)進(jìn)程P1中有語(yǔ)句S1,進(jìn)程P2中有語(yǔ)句S2兩個(gè)并發(fā)執(zhí)行希望S1執(zhí)行后再執(zhí)行S2,要實(shí)現(xiàn)這種前趨關(guān)系只需共享一個(gè)公用信號(hào)量S并賦初值0,將signal(S)放在語(yǔ)句S1后,而在S2之前插入wait(S)。即:P1:S1;signal(S);P2:wait(S);S2;

用多個(gè)信號(hào)量可實(shí)現(xiàn)右邊前趨圖表示的前趨關(guān)系:

S1S3S5S2S4S6vara,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0;{見(jiàn)p45}parbeginbegins1;

signal(a);

signal(b);end;beginwait(a);s2;signal(c);

signal(d);end;

beginwait(b);s3;signal(e);end;

beginwait(c);s4;signal(f);end;

beginwait(d);s5;signal(g);end;

beginwait(e);wait(f);

wait(g);s6;end;

parendS1S3S5S2S4S6abdcegf司機(jī)進(jìn)程:REPEAT啟動(dòng)駕駛停車UNTIL…售票員進(jìn)程:REPEAT關(guān)門(mén)售票開(kāi)門(mén)UNTIL…2.用信號(hào)量的wait-signal操作解決司機(jī)售票員的同步問(wèn)題

司機(jī)啟動(dòng)必須在售票員關(guān)門(mén)之后,用信號(hào)量s1實(shí)現(xiàn),售票員開(kāi)門(mén)又必須在司機(jī)停車之后,用信號(hào)量s2來(lái)實(shí)現(xiàn),初始狀態(tài):車停在車站,車門(mén)打開(kāi)著。

Vars1,s2:semaphore:=0,0;…………司機(jī)進(jìn)程:REPEAT

wait(s1);啟動(dòng)駕駛停車

signal(s2);UNTIL…售票員進(jìn)程:REPEAT關(guān)門(mén)

signal(s1);售票

wait(s2);開(kāi)門(mén)UNTIL…3.信號(hào)量和wait-signal操作討論1)信號(hào)量的物理含義：S>0表示有S個(gè)資源可用S=0表示無(wú)資源可用S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)信號(hào)量的初值應(yīng)該大于或等于0

wait(S):表示申請(qǐng)一個(gè)資源

signal(S):表示釋放一個(gè)資源。2)wait-signal操作必須成對(duì)出現(xiàn)當(dāng)為互斥操作時(shí),它們同處于同一進(jìn)程當(dāng)為同步操作時(shí),則不在同一進(jìn)程中出現(xiàn)

wait(S1)和wait(S2)連在一起,順序至關(guān)重要同步wait操作與互斥wait操作連在一起,同步在前兩個(gè)signal操作連在一起,順序無(wú)關(guān)緊要3)wait-signal操作的優(yōu)缺點(diǎn)優(yōu)點(diǎn)：簡(jiǎn)單，而且表達(dá)能力強(qiáng)（用wait-signal操作可解決任何同步互斥問(wèn)題）缺點(diǎn)：不夠安全；wait-signal操作使用不當(dāng)會(huì)出現(xiàn)死鎖；遇到復(fù)雜同步互斥問(wèn)題時(shí)實(shí)現(xiàn)復(fù)雜消費(fèi)者生產(chǎn)者緩沖區(qū)2.4經(jīng)典進(jìn)程同步問(wèn)題

2.4.1生產(chǎn)者─消費(fèi)者問(wèn)題1.單緩沖區(qū)的同步：引入同步信號(hào)量s1和s2。s1用來(lái)表示緩沖區(qū)是否為空,其初值為1;s2用來(lái)表示緩沖區(qū)是否為滿,其初值為0。只有當(dāng)S1>0時(shí)生產(chǎn)者進(jìn)程(Pp)才能送產(chǎn)品到緩沖區(qū);同樣,只有當(dāng)S2>0時(shí)消費(fèi)者進(jìn)程(Pc)才能從緩沖區(qū)取產(chǎn)品。生產(chǎn)者─消費(fèi)者進(jìn)程間的同步算法如下:Pc：…Pp：…RepeatRepeat

生產(chǎn)一個(gè)產(chǎn)品；wait(s2);

wait(s1);

從緩沖區(qū)取產(chǎn)品；送產(chǎn)品到緩沖區(qū)；signal(s1);

signal(s2);

消費(fèi)產(chǎn)品Untilfalse;Untilfalse;2.n個(gè)緩沖區(qū)的同步：

s1用來(lái)表示空緩沖區(qū)個(gè)數(shù)初值為n;s2用來(lái)表示裝有產(chǎn)品的緩沖個(gè)數(shù),其初始值為0。n緩沖區(qū)的生產(chǎn)者─消費(fèi)者進(jìn)程之間的同步算法如下：Var…in:=0;out:=0；

Pp：…Pc：…

RepeatRepeat

生產(chǎn)產(chǎn)品；wait(s2)；

wait(s1)；從Buffer[out]取產(chǎn)品;

往Buffer[in]中放產(chǎn)品；signal(s1)；

signal(s2)；out:=(out+1)modn；

in:=(in+1)modn；消費(fèi)產(chǎn)品；

Untilfalse;Untilfalse;要不要對(duì)緩沖區(qū)(臨界資源)進(jìn)行互斥操作？3.多個(gè)生產(chǎn)者和多個(gè)消費(fèi)者進(jìn)程并發(fā)當(dāng)有多個(gè)生產(chǎn)者進(jìn)程和多個(gè)消費(fèi)者進(jìn)程并發(fā)執(zhí)行時(shí),由于緩沖區(qū)Buffer[in]和Buffer[out]以及in和out都是臨界資源所以要對(duì)它們進(jìn)行互斥操作。可利用互斥信號(hào)量s0實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖區(qū)的互斥操作。此時(shí),n緩沖區(qū)的生進(jìn)程─消費(fèi)者進(jìn)程之間的同步算法如下：Vars0,s1,s2:semaphore:=1,n,0;{信號(hào)量p46}Buffer:array[0..n-1]ofitem;{臨界資源}in,out:integer:=0,0;{是臨界資源不是信號(hào)量}……PPi：…PCi：…

RepeatRepeat

生產(chǎn)產(chǎn)品；wait(s2)；

wait(s1)；

wait(s0)；

wait(s0)；從Buffer[out]取產(chǎn)品;

往Buffer[in]中放產(chǎn)品；out:=(out+1)modn;

in:=(in+1)modn;signal(s0

);signal(s0);signal(s1);

signal(s2);消費(fèi)產(chǎn)品；

Untilfalse;Untilfalse;{次序不能顛倒}{次序不能顛倒}Swait(s1,s0)

Swait(s2,s0)

Ssignal(s0,s2)

Ssignal(s0,s1)

利用AND信號(hào)量機(jī)制生產(chǎn)者─消費(fèi)者進(jìn)程的互斥信號(hào)量s0能否各用一個(gè)2.3.3.哲學(xué)家就餐問(wèn)題

五個(gè)哲學(xué)家圍坐在一圓桌旁,桌中央有一盤(pán)通心粉,每人面前有一只空盤(pán)子,每?jī)扇酥g放一只筷子。每個(gè)人的行為是思考,感到饑餓,然后吃通心粉。為了吃通心粉,每個(gè)人必須拿到兩只筷子,并且每個(gè)人只能直接從自己的左邊或右邊去取筷子。varc:array[0..4]ofsemphore:=(1,1,1,1,1);processiRepeat

思考；

wait(c[i]);wait(c[(i+1)mod5]);

進(jìn)食；

signal(c[i]);signal(c[(i+1)mod5]);Untilfalse;0321414320

當(dāng)每人都已取到左筷子要取右筷子時(shí)發(fā)生死鎖。為防止死鎖發(fā)生可采取的幾種措施：最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周圍。僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí),才允許他拿筷子。利用AND信號(hào)量機(jī)制。varc:array[0..4]ofsemphore:=(1,1,1,1,1);processiRepeat

思考；

Swait(c[i],c[(i+1)mod5])；進(jìn)食；

Ssignal(c[i],c[(i+1)mod5])；Untilfalse;0321414320規(guī)定奇數(shù)號(hào)哲學(xué)家先拿右邊的再拿左邊的,偶數(shù)號(hào)哲學(xué)家相反;1,2號(hào)哲學(xué)家先競(jìng)爭(zhēng)2號(hào)筷;3,4號(hào)哲學(xué)家先競(jìng)爭(zhēng)4號(hào)筷;0號(hào)先拿0號(hào)筷。varc:array[0..4]ofsemphore:=(1,1,1,1,1);processi;{i=2*k}processi;{i=2*k-1}RepeatRepeat

思考;思考;wait(c[i]);wait(c[i+1]);wait(c[(i+1)mod5]);wait(c[i]);進(jìn)食;進(jìn)食;signal(c[(i+1)mod5]);signal(c[i]);signal(c[i]);signal(c[i+1]);Untilfalse;Untilfalse;01234

012342.4.3.讀者寫(xiě)者問(wèn)題有兩組并發(fā)進(jìn)程:

讀者和寫(xiě)者,共享一組數(shù)據(jù)區(qū),為了保證讀寫(xiě)的正確性和數(shù)據(jù)的一致性要求：當(dāng)有讀者進(jìn)程讀文件時(shí),不允許任何寫(xiě)者進(jìn)程寫(xiě)，但允許多讀者同時(shí)讀當(dāng)有寫(xiě)者進(jìn)程寫(xiě)時(shí),不允許任何其它寫(xiě)者進(jìn)程寫(xiě),也不允許任何讀者進(jìn)行讀。(或要求:)

不允許讀者、寫(xiě)者同時(shí)操作不允許多個(gè)寫(xiě)者同時(shí)操作1.利用記錄型信號(hào)量解決讀者—寫(xiě)者問(wèn)題為了解決讀者—寫(xiě)者問(wèn)題,需設(shè)置兩個(gè)信號(hào)量：

(1)讀互斥信號(hào)量rs,用于使讀者互斥地訪問(wèn)共享變量n,這里n是記錄有多少讀者正在讀;(2)寫(xiě)互斥信號(hào)量ws,用于實(shí)現(xiàn)讀寫(xiě)互斥和寫(xiě)寫(xiě)互斥地訪問(wèn)共享文件。讀者—寫(xiě)者問(wèn)題進(jìn)行如下描述：讀者：Repeatwait(rs);ifn=0thenwait(ws);n:=n+1;signal(rs);

讀wait(rs);n:=n-1;ifn=0thensignal(ws);signal(rs);Untilfalse寫(xiě)者：Repeat

wait(ws);

寫(xiě)

signal(ws);UntilfalseVarrs,ws:semaphore:=1,1;{讀,讀-寫(xiě)-寫(xiě)互斥信號(hào)量}n:integer:=0;{讀進(jìn)程數(shù)n是臨界資源不是信號(hào)量}……讀者：RepeatSwait(L,1,1);Swait(mx,1,0);讀操作;Ssignal(L,1);Untilfalse寫(xiě)者：RepeatSwait(mx,1,1,L,RN,0);

寫(xiě)操作;Ssignal(mx,1);Untilfalse2.利用信號(hào)量集機(jī)制解決讀者—寫(xiě)者問(wèn)題(p50)

增加限制,最多只允許RN個(gè)讀者同時(shí)讀;增加信號(hào)量L其初值為RN;每個(gè)讀者進(jìn)入時(shí),執(zhí)行Swait(L,1,1)操作使L減1,讀者數(shù)增到RN時(shí)L=0,讀者數(shù)再增1時(shí)被阻塞。VarL,mx:semaphore:=RN,1;{信號(hào)量}……無(wú)寫(xiě)者mx=1,任何讀者都可進(jìn)入無(wú)寫(xiě)者mx=1,又無(wú)讀者L=RN才可進(jìn)【作業(yè)】p6822,23,24,26思考題:1.消息緩沖問(wèn)題。消息緩沖區(qū)為k個(gè),有m個(gè)發(fā)送進(jìn)程,n個(gè)接收進(jìn)程,每個(gè)接收進(jìn)程對(duì)發(fā)送來(lái)的消息都必須取一次。2.理發(fā)師睡覺(jué)問(wèn)題理發(fā)店里有一位理發(fā)師,一把理發(fā)椅和N把供等候理發(fā)的顧客坐的椅子。如果沒(méi)有顧客,則理發(fā)師便在理發(fā)椅上睡覺(jué)。當(dāng)一個(gè)顧客到來(lái)時(shí),他必須先喚醒理發(fā)師。如果顧客到來(lái)時(shí)理發(fā)師正在理發(fā),則如果有空椅子,可坐下來(lái)等;否則離開(kāi)。注意:

顧客和理發(fā)師的理發(fā)動(dòng)作是同時(shí)的semphorec=0;//等候的顧客數(shù)semphoreb=0;//可理發(fā)師數(shù),b<0時(shí)|b|=等理發(fā)顧客數(shù)semphorem=0;//互斥信號(hào)量intc0=0;//等候的顧客數(shù),臨界資源ba(){while(true){wait(c);wait(m);c0--;signal(m);signal(b);理發(fā);}}cui(){wait(m);if(c0<N){c0++;signal(m);signal(c);wait(b);理發(fā);}elsesignal(m);}main(){cobeginba();cu1();cu2();…;coend}SleepingBarberProblemOneSolutionBarberP(customer);/*cuthair*/V(barber);Shared:semaphorecustomer,barber;intwaiting;Init:customer=0;barber=1;waiting=0;Customer/*gethaircut*/V(customer);P(barber);OneSolutionBarberdo{P(customer);P(mutex);waiting--;/*cuthair*/V(mutex);V(barber);}while(true);Shared:semaphorecustomer,barber;intwaiting;Init:customer=0;barber=1;waiting=0;CustomerP(mutex);if(waiting<n){/*gethaircut*/waiting++;V(customer);V(mutex);P(barber);}else{/*leave*/V(mutex);}

采用wait-signal同步機(jī)制來(lái)編寫(xiě)并發(fā)程序,對(duì)于共享變量及信號(hào)量變量的操作將被分散于各個(gè)進(jìn)程中。缺點(diǎn)：易讀性差:要了解對(duì)于一組共享變量及信號(hào)量的操作是否正確,則必須通讀整個(gè)系統(tǒng)或并發(fā)程序?？删S護(hù)性差:

wait-signal操作相互牽扯程序局部性很差,所以任一組變量或一段代碼的修改都可能影響全局。正確性難保:

操作系統(tǒng)或并發(fā)程序通常都很大,要保證這樣一個(gè)復(fù)雜系統(tǒng)沒(méi)有邏輯錯(cuò)誤是很難的。把所有對(duì)某種臨界資源的同步操作集中起來(lái),構(gòu)成管程,凡對(duì)該臨界資源的訪問(wèn)都通過(guò)它實(shí)現(xiàn)同步。2.5管程機(jī)制2.5.1管程的引入管程：一種集中式同步機(jī)制1.管程定義:

指關(guān)于共享資源的數(shù)據(jù)及在其上操作的一組過(guò)程或共享數(shù)據(jù)結(jié)構(gòu)及其規(guī)定的所有操作系統(tǒng)按資源管理的觀點(diǎn)分解成若干模塊，用數(shù)據(jù)表示抽象系統(tǒng)資源，同時(shí)分析了共享資源和專用資源在管理上的差別，按不同的管理方式定義模塊的類型和結(jié)構(gòu)，使同步操作相對(duì)集中，從而增加了模塊的相對(duì)獨(dú)立性。2.5.2管程的基本概念管程的基本思想:將共享變量及對(duì)共享變量能進(jìn)行的所有操作集中在一個(gè)模塊中,操作系統(tǒng)或并發(fā)程序由若干個(gè)這樣的模塊所構(gòu)成,模塊較短,模塊之間關(guān)系清晰,提高了可讀性、可維護(hù)性和正確性。管程的組成:定義管程名稱本管程內(nèi)局部共享變量說(shuō)明對(duì)該局部變量進(jìn)行操作的一組過(guò)程(函數(shù))對(duì)局部共享數(shù)據(jù)初始化管程的形式:typemonitor_name=monitor;{管程名稱}

局部共享變量說(shuō)明procedureentryp1(…);{一組過(guò)程(函數(shù))}begin……end;procedureentryp2(…);begin……end;......begin

共享變量初始化語(yǔ)句序列；end;管程的三個(gè)主要的特性：模塊化:

管程是可單獨(dú)編譯的基本程序單位。抽象數(shù)據(jù)類型:

管程是一種特殊的數(shù)據(jù)類型,其中不僅有數(shù)據(jù),而且有對(duì)數(shù)據(jù)進(jìn)行操作的代碼。信息掩蔽:

管程是半透明的,管程中的外部過(guò)程實(shí)現(xiàn)了某些功能,至于這些功能是怎樣實(shí)現(xiàn)的,在其外部則是不可見(jiàn)的。管程的要點(diǎn)：管程相當(dāng)于圍墻,它把共享變量和對(duì)它們的操作圍起來(lái),訪問(wèn)臨界資源都必須經(jīng)過(guò)管程。局部于管程的數(shù)據(jù)結(jié)構(gòu)只能被管程內(nèi)的過(guò)程訪問(wèn),管程的外部不能直接訪問(wèn),外部只能通過(guò)調(diào)用管程中所說(shuō)明的外部過(guò)程間接地訪問(wèn)。為了保證管程共享變量的數(shù)據(jù)完整性,規(guī)定每次只允許一個(gè)進(jìn)程進(jìn)入管程,即只能互斥進(jìn)入,。管程通常是用來(lái)管理資源的,因而在管程中應(yīng)當(dāng)設(shè)有進(jìn)程等待隊(duì)以及相應(yīng)的等待及喚醒操作。問(wèn)題：多個(gè)進(jìn)程出現(xiàn)在管程中當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行等待操作時(shí)，它應(yīng)當(dāng)釋放管程的互斥權(quán)；當(dāng)一個(gè)進(jìn)入管程的進(jìn)程執(zhí)行喚醒操作時(shí)(如Ｐ喚醒Ｑ),管程中便存在兩個(gè)同時(shí)處于活動(dòng)狀態(tài)的進(jìn)程處理方法有三種：Ｐ等待Ｑ繼續(xù)，直到Ｑ退出或等待Ｑ等待Ｐ繼續(xù)，直到Ｐ等待或退出規(guī)定喚醒為管程中最后一個(gè)可執(zhí)行的操作我們采用第一種處理方式。

因?yàn)楣艹淌腔コ膺M(jìn)入的，所以當(dāng)一個(gè)進(jìn)程試圖進(jìn)入一個(gè)巳被占用的管程時(shí)它應(yīng)當(dāng)在管程的入口處等待，因而在管程的入口處應(yīng)當(dāng)有一個(gè)進(jìn)程等待隊(duì)列，稱作入口等待隊(duì)列。如果進(jìn)程Ｐ喚醒進(jìn)程Ｑ,則Ｐ等待Ｑ繼續(xù),而進(jìn)程Ｑ在執(zhí)行又喚醒進(jìn)程Ｒ,則Ｑ等待Ｒ繼續(xù),…;這樣,在管程內(nèi)部,由于執(zhí)行喚醒操作,可能會(huì)出現(xiàn)多個(gè)等待進(jìn)程;因而還需要另一個(gè)進(jìn)程等待隊(duì)列;這個(gè)等待隊(duì)列都是在執(zhí)行管程的途中被阻塞的,被稱為緊急等待隊(duì)列。它的優(yōu)先級(jí)應(yīng)當(dāng)高于入口等待隊(duì)列的優(yōu)先級(jí)。2.條件變量：于管程通常是用于管理資源的。當(dāng)進(jìn)入管程的進(jìn)程因資源被占用等原因不能繼續(xù)運(yùn)行時(shí),管程使其等待。為了區(qū)別等待的原因,在管程內(nèi)部可以說(shuō)明和使用一種特殊類型的變量,稱作條件變量：

varx,y:condition;

對(duì)于條件型變量,可以執(zhí)行wait和signal操作：

x.wait:如果緊急等待隊(duì)列非空,則喚醒該隊(duì)列隊(duì)首進(jìn)程;否則釋放管程的互斥權(quán),將執(zhí)行此操作的進(jìn)程的PCB插入x鏈尾部。

x.signal:

如果x鏈為空,則相當(dāng)于空操作(不同于信號(hào)量的signal操作s:=s+1),執(zhí)行此操作的進(jìn)程繼續(xù);否則喚醒第一個(gè)等待者,執(zhí)行此操作的進(jìn)程的PCB入緊急等待隊(duì)列的尾部。

2.5.3利用管程解決生產(chǎn)者—消費(fèi)者問(wèn)題生產(chǎn)者和消費(fèi)者進(jìn)程：producer:beginrepeatproduceaniteminnextp;PC.put(item);untilfalse;end;consumer:beginrepeatPC.get(item);consumetheiteminnextc;untilfalse;end;typeproducer-consumer=monitor;{管程名說(shuō)明}varin,out,count:integer;buffer:array[0..n-1]ofitem;nf,ne:condition;{條件變量:非滿非空}proceduerentryput(item);{產(chǎn)品放入緩沖區(qū)過(guò)程}beginifcount>=nthennf.wait;{滿則等待}buffer[in]:=nextp;in:=(in+1)modn;count:=count+1;ifne.queuethenne.signal;{消費(fèi)者隊(duì)非空則喚醒}end;proceduerentryget(item);{從緩沖區(qū)取產(chǎn)品過(guò)程}beginifcount<=0thenne.wait;{空則等待}nextc:=buffer[out];out:=(out+1)modn;count:=count-1;ifnf.queuethennf.signal;{生產(chǎn)者隊(duì)非空則喚醒}end;管程和進(jìn)程的異同點(diǎn)：（1）設(shè)置進(jìn)程和管程的目的不同（2）系統(tǒng)管理數(shù)據(jù)結(jié)構(gòu)進(jìn)程：PCB

管程：等待隊(duì)列（3）管程被進(jìn)程調(diào)用（4）管程是操作系統(tǒng)的固有成分，無(wú)創(chuàng)建和撤消2.6進(jìn)程通信

2.6.1概述

利用信號(hào)量的wait-signal操作實(shí)現(xiàn)進(jìn)程的互斥和同步是進(jìn)程間的低級(jí)通訊;在進(jìn)程互斥中,進(jìn)程通過(guò)修改信號(hào)量相互表明臨界資源是否可用;在進(jìn)程同步中,信號(hào)量相互表明配合信息非常有效;但作為通信工具,則不夠理想。wait-signal操作為低級(jí)通訊原語(yǔ),每次只能傳遞簡(jiǎn)單的信號(hào),效率低,而且通信對(duì)用戶不透明,實(shí)現(xiàn)起來(lái)比較麻煩,不適合于傳遞交換大量信息。若要在進(jìn)程間傳遞大量信息,可直接利用系統(tǒng)提供的一組通信命令來(lái)實(shí)現(xiàn)進(jìn)程的高級(jí)通訊原語(yǔ),它們隱藏了進(jìn)程通訊的實(shí)現(xiàn)細(xì)節(jié),通信對(duì)用戶是透明的,是高效方便的專用通信方式。進(jìn)程通信的方式1.共享內(nèi)存系統(tǒng)(Shared-MemorySystem)

相互通信的進(jìn)程間共享某些數(shù)據(jù)結(jié)構(gòu)或共享存儲(chǔ)區(qū),進(jìn)程之間通過(guò)它們進(jìn)行通信。

1)諸進(jìn)程共享某些數(shù)據(jù)結(jié)構(gòu)(數(shù)組,有界緩沖區(qū)等)數(shù)據(jù)結(jié)構(gòu)的設(shè)置和同步處理都是由用戶來(lái)完成的,增加了用戶的負(fù)擔(dān),效率低,僅用于傳遞少量數(shù)據(jù)。

2)諸進(jìn)程共享存儲(chǔ)區(qū)(數(shù)據(jù)量大),進(jìn)程向系統(tǒng)申請(qǐng)共享存儲(chǔ)區(qū)中的一個(gè)分區(qū),并指定該分區(qū)的關(guān)鍵字,并將該分區(qū)連接到本進(jìn)程上對(duì)其進(jìn)行寫(xiě)。另一進(jìn)程可根據(jù)關(guān)鍵字將該分區(qū)連接到自己之上對(duì)其進(jìn)行讀/寫(xiě),通過(guò)同一分區(qū)的讀/寫(xiě),實(shí)現(xiàn)兩進(jìn)程間的信息交換。2.消息傳遞系統(tǒng)(Messagepassingsystem)3.管道(Pipe)通信—共享文件模式消息傳遞系統(tǒng)(Messagepassingsystem)

以格式化的消息(message)為通信單位;利用系統(tǒng)為進(jìn)程提供的兩個(gè)高級(jí)通訊原語(yǔ)send和receive進(jìn)行通信。隱藏了通訊的實(shí)現(xiàn)細(xì)節(jié),對(duì)用戶是透明的,使用非常方便,是使用最廣泛的進(jìn)程通信機(jī)制。

send：當(dāng)要進(jìn)行消息傳遞時(shí)執(zhí)行sendreceive：當(dāng)接收者要接收消息時(shí)執(zhí)行receive

消息傳遞系統(tǒng)可分為直接方式和間接方式。2.6.2消息傳遞通信的實(shí)現(xiàn)方法1.直接通信方式：發(fā)送進(jìn)程直接發(fā)消息給接收進(jìn)程,要求指明對(duì)方名字發(fā)送原語(yǔ):Send(Receiver,message)

接收原語(yǔ):Receive(Sender,message)

有時(shí)接收者要接收多個(gè)消息,事先不知道發(fā)送者。接收改為:Receive(id,message){

id返回發(fā)送進(jìn)程名}2.間接方式(信箱通信)：發(fā)消息時(shí)不指定接收進(jìn)程的名字,而是指定一個(gè)中間媒介,即信箱。進(jìn)程間通過(guò)信箱實(shí)現(xiàn)通信,既可以實(shí)現(xiàn)實(shí)時(shí)通信,又可以實(shí)現(xiàn)非實(shí)時(shí)通信。原語(yǔ):Send(MB,message);Receive(MB,message)

信箱可分為由操作系統(tǒng)創(chuàng)建的公用信箱和由用戶進(jìn)程創(chuàng)建的私用信箱、共享信箱。發(fā)送進(jìn)程和接收進(jìn)程間存在4種關(guān)系:一對(duì)一(專用),多對(duì)一(客/服),多對(duì)多(公),一對(duì)多(廣播)。2.6.3通信鏈路、消息格式和同步方式1.通信鏈路：

建立通信鏈路方式：先用顯式“建立連接”命令建立通信鏈路,再通信,用完后可以顯式方式拆除鏈路,用在計(jì)算機(jī)網(wǎng)絡(luò)中。發(fā)送原語(yǔ)執(zhí)行時(shí)系統(tǒng)自動(dòng)連接,用在單機(jī)系統(tǒng)中。鏈路連接方式:點(diǎn)—點(diǎn),多點(diǎn)通信方式:單工,雙工2.消息格式

消息頭:源和目的進(jìn)程名,消息類型長(zhǎng)度編號(hào),日期時(shí)間消息正文:消息的實(shí)際內(nèi)容3.同步方式緊密同步(匯合):無(wú)緩沖,收發(fā)進(jìn)程收發(fā)完后都被阻塞平時(shí)接收進(jìn)程阻塞:發(fā)送進(jìn)程發(fā)消息時(shí)將接收進(jìn)程喚醒平時(shí)都不阻塞:只有當(dāng)收發(fā)消息無(wú)法繼續(xù)時(shí)才自我阻塞2.6.4消息緩沖隊(duì)列通信機(jī)制：

由美國(guó)Hansan提出,被廣泛用于本地進(jìn)程之間的通信,發(fā)進(jìn)程用send原語(yǔ)發(fā)送,收進(jìn)程用receive原語(yǔ)接收。1.數(shù)據(jù)結(jié)構(gòu)：

TypeMesBuf=record{消息緩沖區(qū)類型}sender;{發(fā)送者}size;{消息長(zhǎng)度}text;{消息正文}next;{指向下一緩沖區(qū)的指針}end;

TypePCBlock=record{

PCB中增加通信的數(shù)據(jù)項(xiàng)}…mq;{消息隊(duì)列首指針}mutex;{消息隊(duì)列互斥信號(hào)量}sm;{消息隊(duì)列資源信號(hào)量}…end;......send(B,m)......sender:Asize:長(zhǎng)度text:正文……m發(fā)送區(qū)進(jìn)程A進(jìn)程B......receive(A,B,n)...…sender:Asize:長(zhǎng)度text:正文……n接收區(qū)PCB(B)......mqmutexsmsender:Asize:長(zhǎng)度text:正文……next:∧對(duì)稱方式:發(fā)送者和接收者都知道對(duì)方的名字......send(B,m)......sender:Asize:長(zhǎng)度text:正文……m發(fā)送區(qū)進(jìn)程A進(jìn)程B......receive(B,n)...…sender:Asize:長(zhǎng)度text:正文……n接收區(qū)PCB(B)......mqmutexsmsender:Asize:長(zhǎng)度text:正文……next:∧

實(shí)際常用非對(duì)稱方式,接收前,接收方不必知道發(fā)送方的名字,接收到消息后從消息頭才知道對(duì)方的名字。2.Send原語(yǔ):

在操作系統(tǒng)空間設(shè)置一組緩沖區(qū),當(dāng)發(fā)送進(jìn)程需要發(fā)送消息之前,先把待發(fā)送的消息正文和其它相關(guān)信息填入在自己內(nèi)存空間中設(shè)置的發(fā)送區(qū)a,然后調(diào)用發(fā)送原語(yǔ)send系統(tǒng)調(diào)用,產(chǎn)生自愿性中斷,進(jìn)入核心態(tài),OS按發(fā)送區(qū)a中所設(shè)的消息長(zhǎng)度a.size為發(fā)送進(jìn)程分配一個(gè)空緩沖區(qū),再將所發(fā)送的消息從發(fā)送區(qū)copy到緩沖區(qū)中,然后,將該載有消息的緩沖區(qū)鏈接到接收進(jìn)程的消息鏈隊(duì)列尾,完成發(fā)送過(guò)程。之后,返回到用戶態(tài)繼續(xù)執(zhí)行。緩沖區(qū)和消息隊(duì)列都是臨界資源,分配空緩沖區(qū)要用wait-signal操作實(shí)現(xiàn)互斥,對(duì)消息鏈隊(duì)列修改時(shí)也要用wait-signal操作。Send中要訪問(wèn)臨界資源需用wait-signal操作:ProcedureSend(r,a);{r為接收進(jìn)程,a為發(fā)送區(qū)}Begin

getbuf(a.size,i);{申請(qǐng)a.size大小的空緩沖區(qū)i}{getbuf()中已用wait-signal實(shí)現(xiàn)互斥}i.sender:=a.sender;{把消息從a處copy到空緩沖區(qū)i;}i.size:=a.size;i.text:=a.text;i.next:=0;getid(PCBset,r,j);{根據(jù)r獲接收進(jìn)程內(nèi)部標(biāo)識(shí)符j}wait(j.mutex);insert(j.mq,i);{把緩沖區(qū)i掛到接收進(jìn)程r的消息鏈尾}signal(j.mutex);signal(j.sm);

{j.sm是與Receive同步的信號(hào)量}END3.Receive原語(yǔ):

當(dāng)接收進(jìn)程執(zhí)行到調(diào)用Receive接收原語(yǔ)時(shí),也產(chǎn)生自愿性中斷,進(jìn)入核心態(tài),由操作系統(tǒng)將載有消息的緩沖區(qū)從消息隊(duì)列中摘出,并把消息內(nèi)容copy到接收進(jìn)程中所設(shè)置的接收區(qū)b,然后收回緩沖區(qū),完成了消息的接收;之后,接收進(jìn)程返回到用戶態(tài)繼續(xù)進(jìn)行。緩沖區(qū)和消息隊(duì)列都是臨界資源,所以在Receive中,釋放緩沖區(qū)要用wait-signal操作實(shí)現(xiàn)互斥,從消息鏈隊(duì)列摘出時(shí)也要用wait-signal操作實(shí)現(xiàn)互斥。用wait-signal操作來(lái)實(shí)現(xiàn)Receive原語(yǔ)對(duì)稱方式:ProcedureReceive(s,r,b);{s/r為發(fā)/收進(jìn)程,b為接收區(qū)}Begingetid(PCBset,r,j);{根據(jù)r獲接收進(jìn)程內(nèi)部標(biāo)識(shí)符j}

wait(j.sm);

{j.sm是與Send同步的信號(hào)量}

wait(j.mutex);remove(j.mq,s,i);{從j.mq鏈摘下s發(fā)送的消息到i}signal(j.mutex);b.sender:=i.sender;{把消息從緩沖區(qū)i處copy到b}b.size:=i.size;b.text:=i.text;freebuf(i){釋放空緩沖區(qū)i}

{freebuf(i)中已用wait-signal實(shí)現(xiàn)互斥}ENDReceive原語(yǔ)非對(duì)稱方式:ProcedureReceive(r,b);{r為接收進(jìn)程,b為接收區(qū)}Begingetid(PCBset,r,j);{根據(jù)r獲接收進(jìn)程內(nèi)部標(biāo)識(shí)符j}

wait(j.sm);

{j.sm是與Send同步的信號(hào)量}

wait(j.mutex);remove(j.mq,i);{從j.mq鏈摘下第一個(gè)消息到i}signal(j.mutex);b.sender:=i.sender;{把消息從緩沖區(qū)i處copy到b}b.size:=i.size;b.text:=i.text;

freebuf(i){釋放空緩沖區(qū)i}

{freebuf(i)中已用wait-signal實(shí)現(xiàn)互斥}END2.6.5管道(Pipe)通信方式發(fā)送進(jìn)程接收進(jìn)程字符流方式寫(xiě)入讀出先進(jìn)先出

也稱共享文件方式,基于文件系統(tǒng),利用打開(kāi)的共享文件連接兩個(gè)相互通信的進(jìn)程,文件作為緩沖傳輸介質(zhì)管道就是用于連接讀進(jìn)程和寫(xiě)進(jìn)程的共享文件,寫(xiě)進(jìn)程向管道發(fā)送字符流,讀進(jìn)程從管道中接受字符流。管道機(jī)制必須有三方面的能力,才能正確通信?；コ?對(duì)管道讀