版權(quán)說(shuō)明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
第五章并發(fā)進(jìn)程及死鎖問(wèn)題進(jìn)程間的聯(lián)系進(jìn)程的同步機(jī)制──信號(hào)量及P.V操作(解決進(jìn)程同步互斥問(wèn)題)第五章并發(fā)進(jìn)程及死鎖問(wèn)題進(jìn)程間的聯(lián)系5.1進(jìn)程間的制約關(guān)系相交進(jìn)程與無(wú)關(guān)進(jìn)程相交進(jìn)程:指多個(gè)并發(fā)進(jìn)程在邏輯上有某種聯(lián)系無(wú)關(guān)進(jìn)程(不相交進(jìn)程):在邏輯上無(wú)任何聯(lián)系的進(jìn)程5.1進(jìn)程間的制約關(guān)系相交進(jìn)程與無(wú)關(guān)進(jìn)程直接作用和間接作用直接作用: 進(jìn)程間的相互聯(lián)系是有意識(shí)的安排的,直接作用只發(fā)生在相交進(jìn)程間間接作用: 進(jìn)程間要通過(guò)某種中介發(fā)生聯(lián)系,是無(wú)意識(shí)安排的,可發(fā)生在相交進(jìn)程之間,也可發(fā)生在無(wú)關(guān)進(jìn)程之間直接作用和間接作用相互感知程度
交互關(guān)系
一個(gè)進(jìn)程對(duì)其他進(jìn)程的影響
相互不感知(完全不了解其它進(jìn)程的存在)競(jìng)爭(zhēng)(competition)一個(gè)進(jìn)程的操作對(duì)其他進(jìn)程的結(jié)果無(wú)影響
間接感知(雙方都與第三方交互,如共享資源)通過(guò)共享進(jìn)行協(xié)作
一個(gè)進(jìn)程的結(jié)果依賴于從其他進(jìn)程獲得的信息
直接感知(雙方直接交互,如通信)通過(guò)通信進(jìn)行協(xié)作
一個(gè)進(jìn)程的結(jié)果依賴于從其他進(jìn)程獲得的信息
相互感知程度交互關(guān)系一個(gè)進(jìn)程對(duì)其他進(jìn)程的影響相互不感知進(jìn)程的同步(直接作用)進(jìn)程的同步:synchronism 指系統(tǒng)中多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系,需要相互合作,共同完成一項(xiàng)任務(wù)。具體說(shuō),一個(gè)進(jìn)程運(yùn)行到某一點(diǎn)時(shí)要求另一伙伴進(jìn)程為它提供消息,在未獲得消息之前,該進(jìn)程處于等待狀態(tài),獲得消息后被喚醒進(jìn)入就緒態(tài)進(jìn)程的同步(直接作用)進(jìn)程的同步:synchronism例:
司機(jī)P1售票員P2
while(true)while(true)
{{
啟動(dòng)車輛;關(guān)門(mén);
正常運(yùn)行;售票;
到站停車;開(kāi)門(mén);
}}
例:
司機(jī)P1售票員P進(jìn)程的互斥(間接作用)mutualexclusion
由于各進(jìn)程要求共享資源,而有些資源需要互斥使用,因此各進(jìn)程間競(jìng)爭(zhēng)使用這些資源,進(jìn)程的這種關(guān)系為進(jìn)程的互斥臨界資源:criticalresource 系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用,稱這樣的資源為臨界資源或互斥資源或共享變量進(jìn)程的互斥(間接作用)mutualexclusion臨界區(qū)(互斥區(qū)):criticalsection
一個(gè)程序片段的集合,這些程序片段分散在不同的進(jìn)程中,對(duì)某個(gè)共享的數(shù)據(jù)結(jié)構(gòu)(共享資源)進(jìn)行操作在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū)多個(gè)進(jìn)程的臨界區(qū)稱為相關(guān)臨界區(qū)臨界區(qū)(互斥區(qū)):criticalsectiona:=a-1print(a)a:=a+1print(a)P1互斥P2互斥Ifa<0thena:=a+1elsea:=a-1P3互斥
進(jìn)程的互斥(間接作用)a:=a-1a:=a+1P1互斥P2互斥If并發(fā)進(jìn)程及死鎖問(wèn)題課件使用互斥區(qū)的原則:有空讓進(jìn):當(dāng)無(wú)進(jìn)程在互斥區(qū)時(shí),任何有權(quán)使用互斥區(qū)的進(jìn)程可進(jìn)入無(wú)空等待:不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入互斥區(qū)多中擇一:當(dāng)沒(méi)有進(jìn)程在臨界區(qū),而同時(shí)有多個(gè)進(jìn)程要求進(jìn)入臨界區(qū),只能讓其中之一進(jìn)入臨界區(qū),其他進(jìn)程必須等待有限等待:任何進(jìn)入互斥區(qū)的要求應(yīng)在有限的時(shí)間內(nèi)得到滿足讓權(quán)等待:處于等待狀態(tài)的進(jìn)程應(yīng)放棄占用CPU,以使其他進(jìn)程有機(jī)會(huì)得到CPU的使用權(quán)使用互斥區(qū)的原則:有空讓進(jìn):當(dāng)無(wú)進(jìn)程在互斥區(qū)時(shí),任何有權(quán)使用使用互斥區(qū)的原則:前提:任何進(jìn)程無(wú)權(quán)停止其它進(jìn)程的運(yùn)行 進(jìn)程之間相對(duì)運(yùn)行速度無(wú)硬性規(guī)定進(jìn)程互斥的解決有兩種做法:由競(jìng)爭(zhēng)各方平等協(xié)商引入進(jìn)程管理者,由管理者來(lái)協(xié)調(diào)競(jìng)爭(zhēng)各方對(duì)互斥資源的使用具體方法:硬件(當(dāng)一個(gè)進(jìn)程進(jìn)入臨界區(qū),就屏蔽所有中斷,但成本高)軟件(用編程解決,但常常忙等待)使用互斥區(qū)的原則:進(jìn)程互斥的軟件方法通過(guò)平等協(xié)商方式實(shí)現(xiàn)進(jìn)程互斥的最初方法是軟件方法
其基本思路是在進(jìn)入?yún)^(qū)檢查和設(shè)置一些標(biāo)志,如果已有進(jìn)程在臨界區(qū),則在進(jìn)入?yún)^(qū)通過(guò)循環(huán)檢查進(jìn)行等待;在退出區(qū)修改標(biāo)志
其中的主要問(wèn)題是設(shè)置什么標(biāo)志和如何檢查標(biāo)志進(jìn)程互斥的軟件方法通過(guò)平等協(xié)商方式實(shí)現(xiàn)進(jìn)程互斥的最初方法是軟軟件解法(1)free:表示臨界區(qū)標(biāo)志
true:有進(jìn)程在臨界區(qū)
false:無(wú)進(jìn)程在臨界區(qū)(初值)
....
while(free);
free=true;
臨界區(qū)free=false;軟件解法(1)free:表示臨界區(qū)標(biāo)志
軟件解法(2)turn:true P進(jìn)入臨界區(qū)false Q進(jìn)入臨界區(qū)....P:while(notturn);臨界區(qū)turn=false;Q:while(turn);臨界區(qū)turn=true;軟件解法(2)turn:true P進(jìn)入臨界區(qū)軟件解法的缺點(diǎn):1.忙等待2.實(shí)現(xiàn)過(guò)于復(fù)雜,需要高的編程技巧
軟件解法的缺點(diǎn):硬件解法(1)
“測(cè)試并設(shè)置”指令booleanTS(boolean*lock){booleanold;old=*lock;*lock=true;}whileTS(&lock);臨界區(qū)lock=false;硬件解法(1)
“測(cè)試并設(shè)置”指令boolean硬件解法(2)
“交換”指令voidSWAP(int*a,int*b){inttemp;temp=*a;*a=*b;*b=temp;}key=true;do{SWAP(&lock,key);}while(key);臨界區(qū)lock:=false;硬件解法(2)
“交換”指令voidSWAP(i硬件解法(3)
“開(kāi)關(guān)中斷”指令進(jìn)入臨界區(qū)前執(zhí)行:執(zhí)行“關(guān)中斷”指令離開(kāi)臨界區(qū)后執(zhí)行:執(zhí)行“開(kāi)中斷”指令硬件解法(3)
“開(kāi)關(guān)中斷”指令進(jìn)入臨界區(qū)前執(zhí)行:5.2進(jìn)程的同步機(jī)制──
信號(hào)量及P.V操作(解決進(jìn)程同步與互斥)
5.2.1概念同步機(jī)制:信號(hào)量及P、V操作;管程;條件臨界域;路徑表達(dá)式等(用于集中式系統(tǒng)中)
會(huì)合;通信順序進(jìn)程;分布進(jìn)程;遠(yuǎn)程過(guò)程調(diào)用等(適用于分布式系統(tǒng)中)5.2進(jìn)程的同步機(jī)制──
信號(hào)量及P.V操作(解決進(jìn)程同步信號(hào)量分類公用信號(hào)量私用信號(hào)量二元信號(hào)量一般信號(hào)量信號(hào)量分類公用信號(hào)量同步機(jī)制應(yīng)滿足的基本要求:*描述能力*可以實(shí)現(xiàn)*效率高*使用方便同步機(jī)制應(yīng)滿足的基本要求:信號(hào)量:semaphore是一個(gè)數(shù)據(jù)結(jié)構(gòu)定義如下:strucsemaphore{ intvalue; pointer_PCBqueue;}信號(hào)量說(shuō)明:semaphores;信號(hào)量:semaphore是一個(gè)數(shù)據(jù)結(jié)構(gòu)P、V操作P(s){s.value=s.value--;if(s.value<0){ 該進(jìn)程狀態(tài)置為等待狀態(tài)將該進(jìn)程的PCB插入相應(yīng)的等待隊(duì)列末尾s.queue;}}P、V操作P(s)P、V操作V(s){s.value=s.value++;if(s.value<=0){喚醒相應(yīng)等待隊(duì)列s.queue中等待的一個(gè)進(jìn)程改變其狀態(tài)為就緒態(tài)并將其插入就緒隊(duì)列
}}P、V操作V(s)P、V操作為原語(yǔ)操作原語(yǔ):primitiveoratomicaction是由若干多機(jī)器指令構(gòu)成的完成某種特定功能的一段程序,具有不可分割性 即原語(yǔ)的執(zhí)行必須是連續(xù)的,在執(zhí)行過(guò)程中不允許被中斷實(shí)現(xiàn):開(kāi)關(guān)中斷P、V操作為原語(yǔ)操作信號(hào)量的使用:
必須置一次且只能置一次初值初值不能為負(fù)數(shù)
只能執(zhí)行P、V操作信號(hào)量的使用:用P、V操作解決進(jìn)程間互斥問(wèn)題P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)用P、V操作解決進(jìn)程間互斥問(wèn)題P(mutex)V(mutex經(jīng)典的生產(chǎn)者─消費(fèi)者問(wèn)題消費(fèi)者生產(chǎn)者經(jīng)典的生產(chǎn)者─消費(fèi)者問(wèn)題消費(fèi)者生產(chǎn)者經(jīng)典的生產(chǎn)者─消費(fèi)者問(wèn)題同步問(wèn)題: P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品,設(shè)置信號(hào)量為S1Q進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品,設(shè)置信號(hào)量S2經(jīng)典的生產(chǎn)者─消費(fèi)者問(wèn)題同步問(wèn)題:S1初值為1,S2初值為0P:Q:while(true){while(true){生產(chǎn)一個(gè)產(chǎn)品;P(s2);P(s1);從緩沖區(qū)取產(chǎn)品;送產(chǎn)品到緩沖區(qū);V(s1);V(s2);消費(fèi)產(chǎn)品;};};單緩沖區(qū)生產(chǎn)者-消費(fèi)者問(wèn)題S1初值為1,S2初值為0P:并發(fā)進(jìn)程及死鎖問(wèn)題課件多個(gè)緩沖區(qū)的生產(chǎn)者和消費(fèi)者P:
i=0;
while(true){
生產(chǎn)產(chǎn)品;
P(S1);
往Buffer[i]放產(chǎn)品;
V(S2);
i=(i+1)%n;};Q:j=0;while(true){P(S2);從Buffer[j]取產(chǎn)品;V(S1);消費(fèi)產(chǎn)品;j=(j+1)%n;};多個(gè)緩沖區(qū)的生產(chǎn)者和消費(fèi)者P:
i=0;
while(【思考題】要不要對(duì)緩沖區(qū)(臨界資源)進(jìn)行互斥操作?【思考題】要不要對(duì)緩沖區(qū)(臨界資源)進(jìn)行互斥操作?Q:j=0;while(true){P(S2);P(mutex);從Buffer[j]取產(chǎn)品;V(mutex);V(S1);消費(fèi)產(chǎn)品;j=(j+1)%n;};n個(gè)緩沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(fèi)者P:
i=0;
while(true){
生產(chǎn)產(chǎn)品;
P(S1);
P(mutex);往Buffer[i]放產(chǎn)品;V(mutex);
V(S2);
i=(i+1)%n;};有錯(cuò)誤?若顛倒兩個(gè)P操作的順序?Q:n個(gè)緩沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(fèi)者P:
i=0;
wQ:j=0;while(true){P(S2);P(mutex);從Buffer[j]取產(chǎn)品;j=(j+1)%n;V(mutex);V(S1);消費(fèi)產(chǎn)品;};n個(gè)緩沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(fèi)者P:
i=0;
while(true){
生產(chǎn)產(chǎn)品;
P(S1);
P(mutex);往Buffer[i]放產(chǎn)品;i=(i+1)%n;V(mutex);
V(S2);
};正確Q:n個(gè)緩沖區(qū)、m個(gè)生產(chǎn)者和k個(gè)消費(fèi)者P:
i=0;
wP.V操作討論1)信號(hào)量的物理含義:S>0表示有S個(gè)資源可用S=0表示無(wú)資源可用S<0則|S|表示S等待隊(duì)列中的進(jìn)程個(gè)數(shù)P(S):表示申請(qǐng)一個(gè)資源V(S)表示釋放一個(gè)資源。信號(hào)量的初值應(yīng)該大于等于0P.V操作討論2)P.V操作必須成對(duì)出現(xiàn),有一個(gè)P操作就一定有一個(gè)V操作當(dāng)為互斥操作時(shí),它們同處于同一進(jìn)程當(dāng)為同步操作時(shí),則不在同一進(jìn)程中出現(xiàn)如果P(S1)和P(S2)兩個(gè)操作在一起,那么P操作的順序至關(guān)重要,一個(gè)同步P操作與一個(gè)互斥P操作在一起時(shí)同步P操作在互斥P操作前而兩個(gè)V操作無(wú)關(guān)緊要2)P.V操作必須成對(duì)出現(xiàn),有一個(gè)P操作就一定有一個(gè)V操作3)P.V操作的優(yōu)缺點(diǎn)優(yōu)點(diǎn):簡(jiǎn)單,而且表達(dá)能力強(qiáng)(用P.V操作可解決任何同步互斥問(wèn)題)缺點(diǎn):不夠安全;P.V操作使用不當(dāng)會(huì)出現(xiàn)死鎖;遇到復(fù)雜同步互斥問(wèn)題時(shí)實(shí)現(xiàn)復(fù)雜3)P.V操作的優(yōu)缺點(diǎn)當(dāng)同時(shí)需要多種資源時(shí)怎么辦?
單個(gè)信號(hào)量使用很不方便,容易產(chǎn)生混亂,且前面已經(jīng)提到對(duì)多個(gè)信號(hào)量進(jìn)行P操作時(shí),如果順序稍有差錯(cuò)會(huì)導(dǎo)致錯(cuò)誤發(fā)生,因此可以采用信號(hào)量集的方法當(dāng)同時(shí)需要多種資源時(shí)怎么辦?單個(gè)信號(hào)量信號(hào)量集——AND型信號(hào)量集
AND型信號(hào)量集是指同時(shí)需要多種資源且每種占用一個(gè)時(shí)的信號(hào)量操作
AND型信號(hào)量集的基本思想:在一個(gè)原語(yǔ)中申請(qǐng)整段代碼需要的多個(gè)臨界資源,要么全部分配給它,要么一個(gè)都不分配AND型信號(hào)量集P原語(yǔ)為SwaitAND型信號(hào)量集V原語(yǔ)為Ssignal信號(hào)量集——AND型信號(hào)量集AND型信號(hào)量集是指同時(shí)需要多Swait(S1,S2,…,Sn) //P原語(yǔ);{while(TRUE){if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時(shí)的處理;for(i=1;i<=n;++i)-–Si;//注:與P的處理不同,這里是在確信可滿足//資源要求時(shí),才進(jìn)行減1操作;break;}else{ //某些資源不夠時(shí)的處理;
調(diào)用進(jìn)程進(jìn)入第一個(gè)小于1信號(hào)量的等待隊(duì)列Sj.queue;
阻塞調(diào)用進(jìn)程;}}}Swait(S1,S2,…,Sn) //P原語(yǔ);Ssignal(S1,S2,…,Sn){for(i=1;i<=n;++i){++Si; //釋放占用的資源;for(在Si.queue中等待的每一個(gè)進(jìn)程P)//檢查每種資源的等待隊(duì)列的所有進(jìn)程;{從等待隊(duì)列Si.queue中取出進(jìn)程P;
Ssignal(S1,S2,…,Sn)if(判斷進(jìn)程P是否通過(guò)Swait中的測(cè)試)//注:與signal不同,這里要進(jìn)行重新判斷;{//通過(guò)檢查(資源夠用)時(shí)的處理;
進(jìn)程P進(jìn)入就緒隊(duì)列;}else{//未通過(guò)檢查(資源不夠用)時(shí)的處理;
進(jìn)程P進(jìn)入某等待隊(duì)列;}}}}if(判斷進(jìn)程P是否通過(guò)Swait中的測(cè)試)一般“信號(hào)量集”一般信號(hào)量集是指同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的信號(hào)量處理
一般信號(hào)量集的基本思路就是在AND型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充,在一次原語(yǔ)操作中完成所有的資源申請(qǐng)一般“信號(hào)量集”一般信號(hào)量集是指同時(shí)需要多種資源、每種占用的進(jìn)程對(duì)信號(hào)量Si的測(cè)試值為ti(表示信號(hào)量的判斷條件,要求Si>=ti;即當(dāng)資源數(shù)量低于ti時(shí),便不予分配)占用值為di(表示資源的申請(qǐng)量,即Si=Si-di)對(duì)應(yīng)的P、V原語(yǔ)格式為:Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);進(jìn)程對(duì)信號(hào)量Si的一般“信號(hào)量集”可以用于各種情況的資源分配和釋放,幾種特殊情況:Swait(S,d,d)表示每次申請(qǐng)d個(gè)資源,當(dāng)少于d個(gè)時(shí),便不分配Swait(S,1,1)表示互斥信號(hào)量Swait(S,1,0)可作為一個(gè)可控開(kāi)關(guān)(當(dāng)S
1時(shí),允許多個(gè)進(jìn)程進(jìn)入臨界區(qū);當(dāng)S=0時(shí),禁止任何進(jìn)程進(jìn)入臨界區(qū))一般“信號(hào)量集”可以用于各種情況的資源分配和釋放,幾種特殊情【思考題】1.用P.V操作解決下圖之同步問(wèn)題:getcopyputfstg【思考題】1.用P.V操作解決下圖之同步問(wèn)題:getcopy用P.V操作解決司機(jī)與售票員的問(wèn)題司機(jī)進(jìn)程:while(true){啟動(dòng)車輛正常駕駛到站停車}…售票員進(jìn)程:while(true){關(guān)門(mén)售票開(kāi)門(mén)}…用P.V操作解決司機(jī)與售票員的問(wèn)題司機(jī)進(jìn)程:售票員進(jìn)程:5.2.2IPC經(jīng)典問(wèn)題1.讀者寫(xiě)者問(wèn)題
有兩組并發(fā)進(jìn)程:讀者和寫(xiě)者,共享一組數(shù)據(jù)區(qū)要求:允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫(xiě)者同時(shí)操作不允許多個(gè)寫(xiě)者同時(shí)操作5.2.2IPC經(jīng)典問(wèn)題1.讀者寫(xiě)者問(wèn)題第一類:讀者優(yōu)先如果讀者來(lái):1)無(wú)讀者、寫(xiě)者,新讀者可以讀2)有寫(xiě)者等,但有其它讀者正在讀,則新讀者也可以讀3)有寫(xiě)者寫(xiě),新讀者等如果寫(xiě)者來(lái):1)無(wú)讀者,新寫(xiě)者可以寫(xiě)2)有讀者,新寫(xiě)者等待3)有其它寫(xiě)者,新寫(xiě)者等待第一類:讀者優(yōu)先如果讀者來(lái):第一類讀者寫(xiě)者問(wèn)題的解法讀者:while(true){P(mutex);readcount++;if(readcount==1)P(w);V(mutex);讀P(mutex);readcount--;if(readcount==0)V(w);V(mutex);};寫(xiě)者:while(true){P(w);寫(xiě)V(w);};第一類讀者寫(xiě)者問(wèn)題的解法讀者:寫(xiě)者:第一類讀者寫(xiě)者問(wèn)題的解法
(一般信號(hào)量集)讀者:swait(wmutex,1,1;rcount,R,0);寫(xiě);ssignal(wmutex,1);寫(xiě)者:swait(rcount,1,1;wmutex,1,0);寫(xiě);ssignal(rcount,1);第一類讀者寫(xiě)者問(wèn)題的解法
(一般信號(hào)量集)讀者:寫(xiě)者:2.哲學(xué)家就餐問(wèn)題 有五個(gè)哲學(xué)家圍坐在一圓桌旁,桌中央有一盤(pán)通心粉,每人面前有一只空盤(pán)子,每?jī)扇酥g放一只筷子每個(gè)哲學(xué)家的行為是思考,感到饑餓,然后吃通心粉 為了吃通心粉,每個(gè)哲學(xué)家必須拿到兩只筷子,并且每個(gè)人只能直接從自己的左邊或右邊去取筷子2.哲學(xué)家就餐問(wèn)題 有五個(gè)哲學(xué)家圍坐在一圓桌旁,桌中央有一盤(pán)#defineN5voidphilosopher(inti){while(true){
思考;取fork[i];取fork[(i+1)%5];進(jìn)食;放fork[i];放fork[(i+1)%5];}}#defineN5
為防止死鎖發(fā)生可采取的措施:最多允許4個(gè)哲學(xué)家同時(shí)坐在桌子周圍僅當(dāng)一個(gè)哲學(xué)家左右兩邊的筷子都可用時(shí),才允許他拿筷子(
)給所有哲學(xué)家編號(hào),奇數(shù)號(hào)的哲學(xué)家必須首先拿左邊的筷子,偶數(shù)號(hào)的哲學(xué)家則反之為了避免死鎖,把哲學(xué)家分為三種狀態(tài),思考,饑餓,進(jìn)食,并且一次拿到兩只筷子,否則不拿 為防止死鎖發(fā)生可采取的措施:哲學(xué)家就餐問(wèn)題解法(1)#defineN5voidphilosopher(inti){while(true){
思考;取fork[i];取fork[(i+1)%5];進(jìn)食;放fork[i];放fork[(i+1)%5];}}哲學(xué)家就餐問(wèn)題解法(1)#defineN5哲學(xué)家就餐問(wèn)題解法(2)#defineN5#defineTHINKING0#defineHUNGRY1#defineEATING2#typedefintsemaphore;intstate[N];semaphoremutex=1;semaphores[N];哲學(xué)家就餐問(wèn)題解法(2)#defineN5voidtest(inti){if(state[i]==HUNGRY)&&(state[(i-1)%5]!=EATING)&&(state[(i+1)%5]!=EATING){state[i]=EATING;V(&s[i]);}}voidtest(inti)voidphilosopher(inti){while(true){思考;P(&mutex);state[i]=HUNGRY;test(i);V(&mutex);P(&s[i]);拿左筷子;拿右筷子;進(jìn)食;
放左筷子;放右筷子;P(&mutex)state[i]=THINKING;test([i-1]%5);test([i+1]%5);V(&mutex);}}state[i]=THINKINGs[i]=0voidphilosopher(inti)【作業(yè)】1.推廣例子中的消息緩沖問(wèn)題。消息緩沖區(qū)為k個(gè),有1個(gè)發(fā)送進(jìn)程,n個(gè)接收進(jìn)程,每個(gè)接收進(jìn)程對(duì)發(fā)送來(lái)的消息都必須取一次若有m個(gè)發(fā)送進(jìn)程呢?【作業(yè)】1.推廣例子中的消息緩沖問(wèn)題。2.第二類讀者寫(xiě)者問(wèn)題:寫(xiě)者優(yōu)先條件:1)多個(gè)讀者可以同時(shí)進(jìn)行讀2)寫(xiě)者必須互斥(只允許一個(gè)寫(xiě)者寫(xiě),也不能讀者寫(xiě)者同時(shí)進(jìn)行)3)寫(xiě)者優(yōu)先于讀者(一旦有寫(xiě)者,則后續(xù)讀者必須等待,喚醒時(shí)優(yōu)先考慮寫(xiě)者)2.第二類讀者寫(xiě)者問(wèn)題:3.有一個(gè)系統(tǒng),定義P、V操作如下:P(s):s:=s-1;ifs<0then
將本進(jìn)程插入相應(yīng)隊(duì)列末尾等待;V(s):s:=s+1;ifs<=0then從相應(yīng)等待隊(duì)列隊(duì)尾喚醒一個(gè)進(jìn)程,將其插入就緒隊(duì)列;3.有一個(gè)系統(tǒng),定義P、V操作如下:
問(wèn)題:1)這樣定義P、V操作是否有問(wèn)題?2)用這樣的P、V操作實(shí)現(xiàn)N個(gè)進(jìn)程競(jìng)爭(zhēng)使用某一共享變量的互斥機(jī)制。3)對(duì)于2)的解法,有無(wú)效率更高的方法。如有,試問(wèn)降低了多少?gòu)?fù)雜性?問(wèn)題:4.理發(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)4.理發(fā)師睡覺(jué)問(wèn)題5.3進(jìn)程通信概述消息緩沖通信方式5.3進(jìn)程通信概述5.3.1概述 P.V操作實(shí)現(xiàn)的是進(jìn)程之間的低級(jí)通訊,所以P.V為低級(jí)通訊原語(yǔ)。它只能傳遞簡(jiǎn)單的信號(hào),不能傳遞交換大量信息
如果要在進(jìn)程間傳遞大量信息則要用Send/Receive原語(yǔ)(高級(jí)通訊原語(yǔ))5.3.1概述 P.V操作實(shí)現(xiàn)的是進(jìn)程之間的低級(jí)通訊,所以進(jìn)程通信的方式共享內(nèi)存:相互通信的進(jìn)程間設(shè)有公共內(nèi)存,一組進(jìn)程向該公共內(nèi)存中寫(xiě),另一組進(jìn)程從公共內(nèi)存中讀,通過(guò)這種方式實(shí)現(xiàn)兩組進(jìn)程間的信息交換這種通信模式需要解決兩個(gè)問(wèn)題?進(jìn)程通信的方式消息傳遞:系統(tǒng)為進(jìn)程提供了兩個(gè)高級(jí)通訊原語(yǔ)send和receivesend: 當(dāng)要進(jìn)行消息傳遞時(shí)執(zhí)行sendreceive: 當(dāng)接收者要接收消息時(shí)執(zhí)行receive消息傳遞:共享文件模式:管道通信共享文件模式:管道通信消息傳遞模式消息緩沖在內(nèi)存中開(kāi)設(shè)緩沖區(qū),發(fā)送進(jìn)程將消息送入緩沖區(qū),接收進(jìn)程接收傳遞來(lái)的緩沖區(qū)信箱通信消息傳遞模式消息緩沖直接方式:發(fā)送進(jìn)程發(fā)消息時(shí)要指定接收進(jìn)程的名字,反過(guò)來(lái),接收時(shí)要指明發(fā)送進(jìn)程的名字Send(receiver,message)Receiver(sender,message)*對(duì)稱形式:一對(duì)一*非對(duì)稱形式:多對(duì)一(顧客/服務(wù)員)有緩沖(有界,無(wú)界),無(wú)緩沖直接方式:發(fā)送進(jìn)程發(fā)消息時(shí)要指定接收進(jìn)程的名字,間接方式:發(fā)送進(jìn)程發(fā)消息時(shí)不指定接收進(jìn)程的名字,而是指定一個(gè)中間媒介,即信箱。進(jìn)程間通過(guò)信箱實(shí)現(xiàn)通信
發(fā)送原語(yǔ):send(MB,Message)接收原語(yǔ):receive(MB,Message)間接方式:發(fā)送進(jìn)程發(fā)消息時(shí)不指定接收進(jìn)程的名字,而是指定5.3.2消息緩沖(有界緩沖區(qū)原理):在操作系統(tǒng)空間設(shè)置一組緩沖區(qū),當(dāng)發(fā)送進(jìn)程需要發(fā)送消息時(shí),執(zhí)行send系統(tǒng)調(diào)用,產(chǎn)生自愿性中斷,進(jìn)入操作系統(tǒng),操作系統(tǒng)為發(fā)送進(jìn)程分配一個(gè)空緩沖區(qū),并將所發(fā)送的消息從發(fā)送進(jìn)程copy到緩沖區(qū)中,然后將該載有消息的緩沖區(qū)連接到接收進(jìn)程的消息鏈鏈尾,如此就完成了發(fā)送過(guò)程。發(fā)送進(jìn)程返回到用戶態(tài)繼續(xù)執(zhí)行5.3.2消息緩沖(有界緩沖區(qū)原理):5.3.2消息緩沖(續(xù)1)(有界緩沖區(qū)原理):在以后某個(gè)時(shí)刻,當(dāng)接收進(jìn)程執(zhí)行到receive接收原語(yǔ)時(shí),也產(chǎn)生自愿性中斷進(jìn)入操作系統(tǒng),由操作系統(tǒng)將載有消息的緩沖區(qū)從消息鏈中取出,并把消息內(nèi)容copy到接收進(jìn)程空間,之后收回緩沖區(qū),如此就完成了消息的接收,接收進(jìn)程返回到用戶態(tài)繼續(xù)進(jìn)行5.3.2消息緩沖(續(xù)1)(有界緩沖區(qū)原理):PCB......Send(R,M)......SIZE:消息長(zhǎng)度TEXT:消息正文......消息鏈指針............Receive(pid,N)......SIZE:消息長(zhǎng)度TEXT:消息正文......M:N:接受進(jìn)程R發(fā)送進(jìn)程S消息消息消息......PCB..................M:N:接受進(jìn)程消息緩沖區(qū)結(jié)構(gòu):消息長(zhǎng)度消息正文發(fā)送者消息隊(duì)列指針消息緩沖區(qū)結(jié)構(gòu):用P.V操作來(lái)實(shí)現(xiàn)Send原語(yǔ):Send(R,M)P(m-mutex);Begin把緩沖區(qū)掛到接收進(jìn)程根據(jù)R找接收進(jìn)程,的消息鏈鏈尾;如果沒(méi)找到出錯(cuò)返回;V(m-mutex);申請(qǐng)空緩沖區(qū)P(s-b);V(s-m);P(b-mutex);END摘空緩沖區(qū);V(b-mutex);把消息從M處copy到空緩沖區(qū);其中s-b初值:n;s-m初值:0用P.V操作來(lái)實(shí)現(xiàn)Send原語(yǔ):5.3.3信箱通信信箱組成信箱說(shuō)明
與
信箱體可存放信件數(shù),已存放信件數(shù),指針信箱使用規(guī)則若發(fā)送信件時(shí)信箱已滿,則發(fā)送進(jìn)程被置為“等信箱”狀態(tài),直到信箱有空時(shí)才被釋放若取信件時(shí)信箱中無(wú)信,則接收進(jìn)程被置為“等信件”狀態(tài),直到有信件時(shí)才被釋放5.3.3信箱通信信箱組成5.3.3信箱通信(續(xù)1)Send實(shí)現(xiàn)send(N,M):把信件M送到指定的信箱N中步驟:查找指定信箱N;若信箱未滿,則把信件M送入信箱且釋放“等信件”者;若信箱已滿置發(fā)送信件進(jìn)程為“等信箱”狀態(tài);5.3.3信箱通信(續(xù)1)Send實(shí)現(xiàn)5.3.3信箱通信(續(xù)2)Receive實(shí)現(xiàn)receive(N,X):從指定信箱N中取出一封信,存放到指定的地址X中步驟:查找指定信箱N;若信箱中有信,則取出一封信存于X中且釋放“等信箱”者;若信箱中無(wú)信件則置接收信件進(jìn)程“等信件”狀態(tài);5.3.3信箱通信(續(xù)2)Receive實(shí)現(xiàn)5.3.3信箱通信(續(xù)3)應(yīng)用實(shí)例磁盤(pán)管理進(jìn)程:從信箱中收取信件,處理,啟動(dòng)磁盤(pán)工作其他進(jìn)程:要求訪問(wèn)磁盤(pán),向磁盤(pán)管理進(jìn)程發(fā)一封信作業(yè):
用進(jìn)程通信的辦法解決生產(chǎn)者消費(fèi)者問(wèn)題
5.3.3信箱通信(續(xù)3)應(yīng)用實(shí)例5.3.4管道通信方式Pipe
也稱共享文件方式,基于文件系統(tǒng),利用一個(gè)打開(kāi)的共享文件連接兩個(gè)相互通信的進(jìn)程,文件作為緩沖傳輸介質(zhì)發(fā)送進(jìn)程接收進(jìn)程字符流方式寫(xiě)入讀出先進(jìn)先出順序5.3.4管道通信方式Pipe發(fā)送進(jìn)程接收進(jìn)程字符流方式5.4線程的基本概念線程的引入線程與進(jìn)程的對(duì)比線程的實(shí)現(xiàn)實(shí)例:Solaris5.4線程的基本概念線程的引入5.4.1線程的引入進(jìn)程的兩個(gè)基本屬性:資源的擁有者:
給每個(gè)進(jìn)程分配一虛擬地址空間,保存進(jìn)程映像,控制一些資源(文件,I/O設(shè)備),有狀態(tài)、優(yōu)先級(jí)、調(diào)度調(diào)度單位:
進(jìn)程是一個(gè)執(zhí)行軌跡
以上兩個(gè)屬性構(gòu)成進(jìn)程并發(fā)執(zhí)行的基礎(chǔ)5.4.1線程的引入進(jìn)程的兩個(gè)基本屬性:5.4.1線程的引入(續(xù)1)系統(tǒng)必須完成的操作:創(chuàng)建進(jìn)程撤消進(jìn)程進(jìn)程切換缺點(diǎn):時(shí)間空間開(kāi)銷大,限制并發(fā)度的提高5.4.1線程的引入(續(xù)1)系統(tǒng)必須完成的操作:5.4.1線程的引入(續(xù)2)在操作系統(tǒng)中,進(jìn)程的引入提高了計(jì)算機(jī)資源的利用效率。但在進(jìn)一步提高進(jìn)程的并發(fā)性時(shí),人們發(fā)現(xiàn)進(jìn)程切換開(kāi)銷占的比重越來(lái)越大,同時(shí)進(jìn)程間通信的效率也受到限制線程的引入正是為了簡(jiǎn)化進(jìn)程間的通信,以小的開(kāi)銷來(lái)提高進(jìn)程內(nèi)的并發(fā)程度5.4.1線程的引入(續(xù)2)在操作系統(tǒng)中,進(jìn)程的引入提高了5.4.1線程的引入(續(xù)3)線程:有時(shí)稱輕量級(jí)進(jìn)程
進(jìn)程中的一個(gè)運(yùn)行實(shí)體是一個(gè)CPU調(diào)度單位資源的擁有者還是進(jìn)程或稱任務(wù)將原來(lái)進(jìn)程的兩個(gè)屬性分開(kāi)處理5.4.1線程的引入(續(xù)3)線程:有時(shí)稱輕量級(jí)進(jìn)程5.4.1線程的引入(續(xù)4)線程:有執(zhí)行狀態(tài)(狀態(tài)轉(zhuǎn)換)不運(yùn)行時(shí)保存上下文有一個(gè)執(zhí)行棧有一些局部變量的靜態(tài)存儲(chǔ)可存取所在進(jìn)程的內(nèi)存和其他資源可以創(chuàng)建、撤消另一個(gè)線程5.4.1線程的引入(續(xù)4)線程:線程和進(jìn)程:?jiǎn)芜M(jìn)程、單線程單進(jìn)程、多線程多進(jìn)程、一個(gè)進(jìn)程一個(gè)線程多進(jìn)程、一個(gè)進(jìn)程多個(gè)線程線程和進(jìn)程:PCB用戶棧單線程進(jìn)程模型用戶地址空間核心棧線程控制塊:包含了寄存器映像,線程優(yōu)先數(shù)和線程狀態(tài)信息PCB用單線程進(jìn)程模型用戶地址空間核線程控制塊:PCB多線程進(jìn)程模型用戶地址空間用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊用戶棧核心棧線程控制塊PCB多線程進(jìn)程模型用戶用核線程用核線程用核線程引入線程的好處:創(chuàng)建一個(gè)新線程花費(fèi)時(shí)間少(結(jié)束亦如此)兩個(gè)線程的切換花費(fèi)時(shí)間少(如果機(jī)器設(shè)有“存儲(chǔ)[恢復(fù)]所有寄存器”指令,則整個(gè)切換過(guò)程用幾條指令即可完成)因?yàn)橥贿M(jìn)程內(nèi)的線程共享內(nèi)存和文件,因此它們之間相互通信無(wú)須調(diào)用內(nèi)核適合多處理機(jī)系統(tǒng)引入線程的好處:創(chuàng)建一個(gè)新線程花費(fèi)時(shí)間少(結(jié)束亦如此)例子1:LAN中的一個(gè)文件服務(wù)器,在一段時(shí)間內(nèi)需要處理幾個(gè)文件請(qǐng)求因此有效的方法是:為每一個(gè)請(qǐng)求創(chuàng)建一個(gè)線程在一個(gè)SMP機(jī)器上:多個(gè)線程可以同時(shí)在不同的處理器上運(yùn)行例子1:LAN中的一個(gè)文件服務(wù)器,在一段時(shí)間內(nèi)需要處理幾個(gè)文例子2:一個(gè)線程顯示菜單,并讀入用戶輸入;另一個(gè)線程執(zhí)行用戶命令考慮一個(gè)應(yīng)用:由幾個(gè)獨(dú)立部分組成,這幾個(gè)部分不需要順序執(zhí)行,則每個(gè)部分可以以線程方式實(shí)現(xiàn)當(dāng)一個(gè)線程因I/O阻塞時(shí),可以切換到同一應(yīng)用的另一個(gè)線程例子2:一個(gè)線程顯示菜單,并讀入用戶輸入;5.4.2線程與進(jìn)程的比較調(diào)度并發(fā)性擁有資源系統(tǒng)開(kāi)銷5.4.2線程與進(jìn)程的比較調(diào)度5.4.3線程的實(shí)現(xiàn)機(jī)制用戶級(jí)線程核心級(jí)線程兩者結(jié)合方法5.4.3線程的實(shí)現(xiàn)機(jī)制用戶級(jí)線程一、用戶級(jí)線程(UserLevelThread)由應(yīng)用程序完成所有線程的管理
通過(guò)線程庫(kù)(用戶空間)一組管理線程的過(guò)程核心不知道線程的存在線程切換不需要核心態(tài)特權(quán)調(diào)度是應(yīng)用特定的一、用戶級(jí)線程(UserLevelThread)由應(yīng)用程線程庫(kù)創(chuàng)建、撤消線程在線程之間傳遞消息和數(shù)據(jù)調(diào)度線程執(zhí)行保護(hù)和恢復(fù)線程上下文線程庫(kù)創(chuàng)建、撤消線程對(duì)用戶級(jí)線程的核心活動(dòng)核心不知道線程的活動(dòng),但仍然管理線程的進(jìn)程的活動(dòng)當(dāng)線程調(diào)用系統(tǒng)調(diào)用時(shí),整個(gè)進(jìn)程阻塞但對(duì)線程庫(kù)來(lái)說(shuō),線程仍然是運(yùn)行狀態(tài)
即線程狀態(tài)是與進(jìn)程狀態(tài)獨(dú)立的對(duì)用戶級(jí)線程的核心活動(dòng)核心不知道線程的活動(dòng),但仍然管理線程的
溫馨提示
- 1. 本站所有資源如無(wú)特殊說(shuō)明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒(méi)有圖紙預(yù)覽就沒(méi)有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 人人文庫(kù)網(wǎng)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 《正弦量的基本概念》課件
- 《多層廠房設(shè)計(jì)》課件
- 《GIS程序設(shè)計(jì)》課件
- 天津市 二手房合同范本
- 2025年許昌道路貨運(yùn)輸從業(yè)資格證模擬考試題庫(kù)
- 2025年黃岡道路運(yùn)輸從業(yè)人員從業(yè)資格考試
- 2025年馬鞍山貨運(yùn)從業(yè)資格模擬考
- 2025年三門(mén)峽道路運(yùn)輸從業(yè)資格證考試題和答案
- 2025年牡丹江年貨運(yùn)從業(yè)資格證考試從業(yè)從業(yè)資格資格題庫(kù)及答案
- 2025年日喀則貨運(yùn)模擬考試
- 浙江省嘉興市2023-2024學(xué)年八年級(jí)上學(xué)期期末英語(yǔ)試題
- 水泵維護(hù)保養(yǎng)方案
- 庫(kù)存管理中的供應(yīng)與需求平衡
- 空表機(jī)械加工工藝過(guò)程卡片-工序卡片-工序附圖
- 信息化作戰(zhàn)平臺(tái)
- 有機(jī)硅合成革行業(yè)報(bào)告
- 個(gè)人勞動(dòng)防護(hù)用品的使用和維護(hù)安全培訓(xùn)課件
- 城市營(yíng)銷方案書(shū)
- 9205-2015版鐵路工程試驗(yàn)報(bào)告表
- 《森林病蟲(chóng)害防治》課件
- 遼寧省沈陽(yáng)市鐵西區(qū)2023-2024學(xué)年七年級(jí)上學(xué)期期末考試英語(yǔ)試題(含聽(tīng)力)
評(píng)論
0/150
提交評(píng)論