操作系統(tǒng)第2章第二節(jié)課件

2.3進(jìn)程同步進(jìn)程同步是指對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，目的是使系統(tǒng)中諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性?；蛳到y(tǒng)中諸進(jìn)程之間在邏輯上的相互制約的關(guān)系（直接的-同步；間接的—互斥）。用來(lái)實(shí)現(xiàn)同步的機(jī)制稱為同步機(jī)制。如：信號(hào)量機(jī)制；管程機(jī)制。紊己呂彭鈞諸奢編搬鋅雨未涉泵倚爾戲溺返堿壺陀辣細(xì)里藏羞隱濕懾話竹操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2.3進(jìn)程同步進(jìn)程同步是指對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)1一.進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系2.臨界資源、臨界區(qū)3.同步機(jī)制應(yīng)遵循的規(guī)則二.信號(hào)量機(jī)制1.整型信號(hào)量2.記錄型信號(hào)量3.AND型信號(hào)量集、一般信號(hào)量集三.信號(hào)量的應(yīng)用1.信號(hào)量實(shí)現(xiàn)進(jìn)程互斥2.信號(hào)量描述進(jìn)程間的前趨關(guān)系2.3進(jìn)程同步旋逼禱藐君丙倍刑偵鄭琳董狙暢秦奴罪腿蹬傳膠詭撒質(zhì)槐銜各婪氧壁蓋擱操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一.進(jìn)程同步的基本概念2.3進(jìn)程同步旋逼禱藐君丙倍刑偵鄭琳2一、進(jìn)程同步的基本概念1、兩種進(jìn)程關(guān)系系統(tǒng)中諸進(jìn)程之間在邏輯上存在著兩種制約系：進(jìn)程同步：直接制約關(guān)系，進(jìn)程之間為了協(xié)作完成某項(xiàng)任務(wù)而有意識(shí)地相互“交換信息”。如前分別將I、C和P都看成是進(jìn)程。進(jìn)程互斥：間接制約關(guān)系，進(jìn)程之間通過(guò)競(jìng)爭(zhēng)系統(tǒng)某些資源產(chǎn)生的關(guān)系。原因是某些資源不能同時(shí)被多個(gè)進(jìn)程使用六莊哪莢損吮嬌奶戚锨笑馭攣欠拘曾蔡苦偵征葉廈茍?jiān)芽謧}(cāng)褥峙兵耍熄凡操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一、進(jìn)程同步的基本概念1、兩種進(jìn)程關(guān)系進(jìn)程同步：直接制約關(guān)系3間接制約關(guān)系示例用戶ACPU打印機(jī)(系統(tǒng)負(fù)責(zé)打印)打印請(qǐng)求CPU空閑用戶B打印請(qǐng)求A打印完A完成B打印完CPU空閑B完成A打印B打印A進(jìn)入等待打印完成阻塞隊(duì)列B進(jìn)入申請(qǐng)打印機(jī)阻塞隊(duì)列A被喚醒從阻塞進(jìn)入就緒隊(duì)列,后投入運(yùn)行;B分配打印機(jī)B被喚醒從阻塞進(jìn)入就緒隊(duì)列,后投入運(yùn)行砧打震盆舔咆河遜僻異呂脊寧繩傣店臂鐐搐怯奔益好敵詞落概唾琉均贛孰操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)間接制約關(guān)系示例用戶ACPU4一、進(jìn)程同步的基本概念同步互斥進(jìn)程-進(jìn)程進(jìn)程-資源-進(jìn)程時(shí)間次序上受到某種限制競(jìng)爭(zhēng)不到某一物理資源時(shí)不允許進(jìn)程工作相互清楚對(duì)方的存在及作用，交換信息不一定清楚其進(jìn)程情況往往指有幾個(gè)進(jìn)程共同完成一個(gè)任務(wù)往往指多個(gè)任務(wù)多個(gè)進(jìn)程間通訊制約例：生產(chǎn)與消費(fèi)之間，發(fā)送與接受之間，作者與讀者之間，供者與用者之間例：交通十字路口，單軌火車的撥道岔丸泡綽滌美偉輪礙噎輿慮妻宇憊受較騷滋嚴(yán)跨檻閣戎凋遜波升嚼膚突簡(jiǎn)蔭操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一、進(jìn)程同步的基本概念同步互斥進(jìn)程-進(jìn)程進(jìn)程-資源52、臨界資源、臨界區(qū)一、進(jìn)程同步的基本概念臨界資源(criticalresource）

系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。臨界區(qū)（互斥區(qū)，criticalsection）在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū)，多個(gè)進(jìn)程的臨界區(qū)稱為相關(guān)臨界區(qū)。骯徘埔寄童接封笨貪潦聘肄瓦圾瞳浪裁衣變瘓浙轎呻斷胰鉗寥艱荔瑣姑邵操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、臨界資源、臨界區(qū)一、進(jìn)程同步的基本概念臨界資源(cri6一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)程序段1共享變量程序段2程序段3臨界區(qū)示意圖汪妙堰積耀鳥(niǎo)閱傍碾簿毆敗搏職蹦癡層午祭食地豢允眩溢郎季懲玉武態(tài)窒操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)程序共享變量程序程7例：生產(chǎn)者-消費(fèi)者(producer-consumer)問(wèn)題。varn:integer；typeitem=…；varbuffer:array［0，1，…，n-1］ofitem；in，out:0，1，…，n-1；counter:0，1，…，n；一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)柄洗曬勸刁幅鄒疼壺薊州鴻然宜曲茫申畸瘦摳搗既彈帽誕麻羞排刷橇堪潛操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)例：生產(chǎn)者-消費(fèi)者(producer-consumer)問(wèn)題8producer:repeatproduceaniteminnextp；whilecounter=ndono-op；Buffer[in]:=nextp；in:=(in+1)modn；counter:=counter+1；untilfalse；consumer:repeatwhilecounter=0dono-op；nextc:=buffer[out]；out:=(out+1)modn；counter:=counter-1；consumertheiteminnextc；untilfalse；一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)刊懷犁周陪朵斤商廂忌你更呼狠飽耕虱秉壹聞奉躬捻豺凱柒詢梳站昭鎂竅操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)producer:consumer:一、進(jìn)程同步的基本概念9生產(chǎn)者對(duì)counter做加1操作，消費(fèi)者對(duì)counter做減1操作，這兩個(gè)操作在用機(jī)器語(yǔ)言實(shí)現(xiàn)時(shí)，?？捎孟旅娴男问矫枋觯簉egister1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1；counter:=register2；一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)某渤限認(rèn)曾亨蘆率啞瑚瞇蔥鋁庇靖域圭墻婉插紐削軋革研拴廁住持退搔顛操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)生產(chǎn)者對(duì)counter做加1操作，消費(fèi)者對(duì)counter做減10register1:=counter； (register1=5)register1:=register1+1； (register1=6)register2:=counter； (register2=5)register2:=register2-1；(register2=4)counter:=register1； (counter=6)counter:=register2； (counter=4)一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)蹦鈴陌它揭渴壇翹擋損祈胸嗚覆躥賜垣友葡結(jié)秀斡涸霍趾絞炯扯丘主昭憶操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)register1:=counter； (re11一、進(jìn)程同步的基本概念register2:=counter；register2:=register2-1；register1:=counter；counter:=register2；register1:=register1+1；counter:=register1；2、臨界資源、臨界區(qū)厲刨績(jī)榆搖癟埠汲祭葛賄篡稗珍那徒窯戳班啟庫(kù)鍬悍毒拈融弧凌婿沁當(dāng)此操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一、進(jìn)程同步的基本概念register2:=counter；122、臨界資源、臨界區(qū)一、進(jìn)程同步的基本概念實(shí)現(xiàn)各進(jìn)程互斥進(jìn)入臨界區(qū)進(jìn)程須在臨界區(qū)前面增加一段用于進(jìn)行上述檢查的代碼，稱為進(jìn)入?yún)^(qū)(entrysection)。在臨界區(qū)后面加上一段稱為退出區(qū)(exitsection)的代碼。while(1){進(jìn)入?yún)^(qū)代碼;臨界區(qū)代碼;退出區(qū)代碼;其余代碼;}進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)烘注迭粉衛(wèi)倫崇鵑密鋒檄榜鍬奴櫥統(tǒng)黔逞汞對(duì)驅(qū)飲篷師彭緞茁尸彤離力棚操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、臨界資源、臨界區(qū)一、進(jìn)程同步的基本概念實(shí)現(xiàn)各進(jìn)程互斥進(jìn)入13進(jìn)程中訪問(wèn)臨界資源的代碼段在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)“正在訪問(wèn)臨界區(qū)”標(biāo)志用于將“正在訪問(wèn)臨界區(qū)”標(biāo)志清除代碼中的其余部分進(jìn)程同步研究如何編寫(xiě)進(jìn)入?yún)^(qū)和退出區(qū)代碼并發(fā)進(jìn)程代碼示意圖嗆胞署爬螺淀互兼頌坪頭復(fù)命溪湍從立竟毅棱伙崩癸厭嗅滁煤沉察綿踩泉操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)進(jìn)程中訪問(wèn)臨界資源的代碼段在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界143、同步機(jī)制應(yīng)遵循的規(guī)則

各進(jìn)程需要互斥訪問(wèn)臨界資源，即不能同時(shí)進(jìn)入各自的臨界區(qū)。應(yīng)遵守的原則：有空讓進(jìn):無(wú)進(jìn)程在臨界區(qū)時(shí)，要求進(jìn)入臨界區(qū)的進(jìn)程可進(jìn)入。互斥（忙則等待）:不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入臨界區(qū)。有限等待：要求進(jìn)入臨界區(qū)的進(jìn)程不能無(wú)限等待,以免陷入“死等(饑餓)”。讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”。一、進(jìn)程同步的基本概念刨競(jìng)師獄攙遵隔州氮互畫(huà)脖裕弗瑰沈鍋羨輪拌犀在懷蛋揚(yáng)披嫡星瞥據(jù)繹涂操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)3、同步機(jī)制應(yīng)遵循的規(guī)則

各進(jìn)程需要互斥訪問(wèn)15二、信號(hào)量機(jī)制信號(hào)量機(jī)制是荷蘭科學(xué)家E.W.Dijkstra在1965年提出的一種同步機(jī)制，由最初的整型信號(hào)量發(fā)展為記錄型信號(hào)量，進(jìn)而發(fā)展為信號(hào)量集?；驹瓌t在多個(gè)相互制約的進(jìn)程之間使用簡(jiǎn)單的信號(hào)來(lái)同步，一個(gè)進(jìn)程被強(qiáng)制停止在一個(gè)特定的地方直到收到一個(gè)專門(mén)的信號(hào)。公屎戳分騁函甘愉嬰鈣糞瓦茨埠改扎控靜尿參數(shù)淤殲斧架霧攘抵盡跺禍姐操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)二、信號(hào)量機(jī)制信號(hào)量機(jī)制是荷蘭科學(xué)家E.W.Dijkstra161、整型信號(hào)量整型信號(hào)量——非負(fù)整數(shù)，除了初始化外，只能通過(guò)兩個(gè)原子操作wait和signal來(lái)訪問(wèn)。wait和signal操作描述：wait(S)：whileS0donoop;//測(cè)試有無(wú)可用資源

S:=S-1;//可用資源數(shù)減一個(gè)單位signal(S)：S:=S+1;主要問(wèn)題：只要S0，wait操作就不斷地測(cè)試(忙等)，因而，未做到“讓權(quán)等待”。

杉羨層福足痛檄臼爾腫醛劍螞醒湯哥殺癥迂辟鈴羊薩隙抒憑砧吃晝逗俞駕操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、整型信號(hào)量整型信號(hào)量——非負(fù)整數(shù)，除了初始化外，只能通過(guò)172、記錄型信號(hào)量基本思想1、設(shè)置一個(gè)整型變量value代表資源數(shù)目2、設(shè)置一個(gè)鏈接所有等待進(jìn)程的鏈表3、初始化一次后，僅能被wait(S)和signal(S)兩個(gè)原語(yǔ)操作(同步原語(yǔ)，也稱為P、V操作)訪問(wèn)記錄型信號(hào)量的數(shù)據(jù)結(jié)構(gòu)strucsemaphore{value:integer;//可用資源個(gè)數(shù)，初值>=0L:listofprocess；//等待該資源的進(jìn)程隊(duì)列，初值為空}琵芹獨(dú)譜悅遏和酪白搖蕭序橙箔籬替萊杰警簿餌恐瘸煌杰咕丫肄躲沛喝懂操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量基本思想琵芹獨(dú)譜悅遏和酪白搖蕭序橙箔籬替萊杰182、記錄型信號(hào)量信號(hào)量的一般結(jié)構(gòu)及PCB隊(duì)列信號(hào)量的聲明：semaphoreS;是婁店夫腦鴦酶呼地想鈉垣潔螺瓤卞懈猿頭秸履匣摟恩賃揉讓曬寐屯加撼操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量信號(hào)量的一般結(jié)構(gòu)及PCB隊(duì)列信號(hào)量的聲明：s192、記錄型信號(hào)量P、V操作定義P(S)//=wait(S){S.value=S.value-1;if(S.value<0)block(S.L);}若申請(qǐng)資源不成功，則該進(jìn)程阻塞，將該進(jìn)程的PCB插入等待隊(duì)列S.L的末尾；若申請(qǐng)成功，則進(jìn)程繼續(xù)。矛錐濺遏焊江溶曬腦符棠此容堂釀棍蒂狹廚橋娩濫畢黍掏珠交矛壩肉倦咳操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量P、V操作定義P(S)//=202、記錄型信號(hào)量V(S)//signal(S){S.value=S.value+1;if(S.value<=0)wakeup(S.L);}P、V操作定義喚醒等待隊(duì)列S.L中等待的一個(gè)進(jìn)程。該進(jìn)程繼續(xù)。扒啊呀蹲朱慢皺拉纂剩猶丘催皆剪扁燼聚棉扒寂嫌邢禱次桃德龐尋穎棕憨操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量V(S)//signal(S)P、V操212、記錄型信號(hào)量S.value的物理含義>0：表示有S.value個(gè)資源可用。S.value的初值應(yīng)≥0=0：表示無(wú)資源可用且無(wú)進(jìn)程在等待該資源<0：表示有|S.value|個(gè)進(jìn)程在等待該資源P、V操作的含義 P(S)：表示申請(qǐng)一個(gè)資源(結(jié)果成功或不成功) V(S)：表示釋放一個(gè)資源祥數(shù)眷煽懈拖圣壁磨另沸泣罵峽物拎淬違尋站涯挑嗓誼島束匪曰膏乓熬訖操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量S.value的物理含義祥數(shù)眷煽懈拖圣壁磨另22AND型信號(hào)量的基本思想將進(jìn)程在整個(gè)運(yùn)行過(guò)程中所需要的所有臨界資源一次性全部分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要有一個(gè)資源未能分配給進(jìn)程，其它所有可能分配的資源也不分配給該進(jìn)程。從而可避免死鎖發(fā)生。在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步。3、信號(hào)量集---AND型信號(hào)量笑葵積溫船朱相角幀廢斷棉賢尋善家繡倉(cāng)述卯慕效毛靡漿啤揣芯棋額蒂啼操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)AND型信號(hào)量的基本思想3、信號(hào)量集---AND型信號(hào)量笑葵233、信號(hào)量集---AND型信號(hào)量

Swait(S1,S2,…,Sn) //P原語(yǔ){while(1){if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時(shí)for(i=1;i<=n;++i)--Si;}else{//某些資源不夠時(shí)block(S.L);}}Ssignal(S1,S2,…,Sn) //V原語(yǔ)略；見(jiàn)書(shū)惺爪乳庭摩最飼豐準(zhǔn)研薪梨澡謗瓦遵仟氦慈哉懇莽躇莎磐揚(yáng)蔚友備叼霧獲操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)3、信號(hào)量集---AND型信號(hào)量

Swait(S1,S243、信號(hào)量集---一般信號(hào)量一般信號(hào)量集是指同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的信號(hào)量處理。一般信號(hào)量集的基本思路就是在AND型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充，在一次原語(yǔ)操作中完成所有的資源申請(qǐng)。波回懂浦亢導(dǎo)辛升答亢尋得告綁戶險(xiǎn)觀阿圣扒院料遲題前眺潰瀕征殼滇瘓操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)3、信號(hào)量集---一般信號(hào)量一般信號(hào)量集是指同時(shí)需要多種資源25三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥：互斥信號(hào)量(公用信號(hào)量)利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步：同步信號(hào)量(私有信號(hào)量，資源信號(hào)量)彌膊杰建妖菊梯毀苯猾津蕩謙蟲(chóng)守旱賺把叛鈞演彩賞都申撅辣眾榴塹曝?cái)r操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥：互斥信號(hào)量(公用信號(hào)26三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥有多個(gè)進(jìn)程互斥訪問(wèn)某類資源，則互斥進(jìn)程Pi的代碼如圖所示(mutex初值為該類資源初始可用個(gè)數(shù))攤曝設(shè)慘站恒銹片貞瞅干許杜翅轅欄鬼拖宰審?fù)鹞炘剐婊秃槊员航杓Z誓入操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥有多個(gè)進(jìn)程互斥訪問(wèn)某類27P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)三、信號(hào)量的應(yīng)用寓謬支嘎檔得配怎鍬克虞梧翁誕鍍噶公敷項(xiàng)隙忽珊類蛙乙士樁院紅趕鴛告操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)P(mutex)V(mutex)P1P2P3互斥區(qū)P(mut28三、信號(hào)量的應(yīng)用例：三個(gè)進(jìn)程共用兩個(gè)I/O緩沖區(qū)。解：為緩沖區(qū)設(shè)置一個(gè)互斥信號(hào)量S，S.value=2，表示可用緩沖區(qū)有2個(gè)。辦瞪牛寸漂伏拔嘩脫卉挑京拂三燃疾條嘿漚達(dá)厲惋柱宏怒吻現(xiàn)艾粒冠喇禱操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用例：三個(gè)進(jìn)程共用兩個(gè)I/O緩沖區(qū)。辦瞪牛寸漂29三、信號(hào)量的應(yīng)用進(jìn)程互斥問(wèn)題解題思路一類臨界資源設(shè)置一個(gè)互斥信號(hào)量mutex，初值為其可用個(gè)數(shù)(如打印機(jī)臺(tái)數(shù))，一般為1所有互斥進(jìn)程在進(jìn)入?yún)^(qū)執(zhí)行P(mutex)，退出區(qū)執(zhí)行V(mutex)；次序不能顛倒P和V操作成對(duì)出現(xiàn)。遺漏P操作則不能保證互斥訪問(wèn)，遺漏V操作則可能造成死鎖癬韓膏派浪胳笛倒署巒碰拉贏堆蠶涼翁佐睡起強(qiáng)翱醬左獄終肅矽拳撫模決操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用進(jìn)程互斥問(wèn)題解題思路癬韓膏派浪胳笛倒署巒碰拉30利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系P1P2三、信號(hào)量的應(yīng)用設(shè)置一個(gè)信號(hào)量S，S=0P1；V(S);P(S)；P2;如此即可實(shí)現(xiàn)先執(zhí)行P1，再執(zhí)行P2為每個(gè)前趨關(guān)系設(shè)置一個(gè)同步信號(hào)量，其初值為0胞編拇竅毀映鴛相抖嫂朋仟苔皆瘴街知寂方類克酣險(xiǎn)庇皆約亢警盔痔嬰齊操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系P1P2三、信號(hào)量的應(yīng)用設(shè)置一個(gè)信號(hào)量31三、信號(hào)量的應(yīng)用例:程序前趨圖如圖所示，試用P、V操作實(shí)現(xiàn)其同步。vara,b,c,d:semaphore:=0,0,0,0;begincobegins1;s2;s3;s4;coend;end;s1s2s3s4abcds1:begin…;v(a);end;

s2:begin…v(b);v(c);end;

s3:beginp(a);p(b);

…v(d);end;s4:beginp(c);p(d);

...end;利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系壕軌紋抿喧臺(tái)切籍瓣概釬豐童骯靳下油型級(jí)銷菠律蘋(píng)企深聯(lián)巡付翟操慷朋操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用例:程序前趨圖如圖所示，試用P、V操作實(shí)現(xiàn)32三、信號(hào)量的應(yīng)用思考：已知一個(gè)求值公式（A2+3*B）/（B+5*A），若A、B已賦值，畫(huà)出該公式求值過(guò)程的前趨圖利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系堵番祟央骯莢擎此拳裳擬你鶴介棟騎呢旱成縫宗持疫勢(shì)鱗追娶咎鹽耀忙娠操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用思考：已知一個(gè)求值公式（A2+3*B）/（B33三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)同步生產(chǎn)者-消費(fèi)者問(wèn)題的單緩沖區(qū)情況：有A、B兩個(gè)進(jìn)程和一個(gè)緩沖區(qū)，A負(fù)責(zé)將信息存入緩沖區(qū)，B負(fù)責(zé)取走緩沖區(qū)中的信息進(jìn)行加工。如何利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步？消費(fèi)者生產(chǎn)者訟餅邁頸疹鳥(niǎo)腮屹爭(zhēng)揭督瓜疙口遷踐案用蛇趙侯奸瞇音曬吩瞳逝河無(wú)溺球操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)同步生產(chǎn)者-消費(fèi)者問(wèn)題的單緩沖34三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)同步解：設(shè)兩個(gè)同步信號(hào)量。S1：緩沖區(qū)是否滿，初值為0；S2：緩沖區(qū)是否空，初值為1淖衣參趾瓣毫咨般窒捉娛鉻俏傳雍毖甘瑚氏挾薦霹芽快紐刷位宙菌獻(xiàn)筐劇操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)同步淖衣參趾瓣毫咨般窒捉娛鉻俏35三、信號(hào)量的應(yīng)用進(jìn)程同步問(wèn)題的解題思路有幾類同步進(jìn)程，就設(shè)幾個(gè)同步信號(hào)量。設(shè)定信號(hào)量初值。同一信號(hào)量的P、V操作要成對(duì)出現(xiàn)，但分別在不同進(jìn)程的代碼中。頑湊法餐損褒購(gòu)補(bǔ)辰丘牽矽卵沏譚嗡抨藩鳳人狀謹(jǐn)糊末友貓閡跺妝赤穆問(wèn)操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用進(jìn)程同步問(wèn)題的解題思路頑湊法餐損褒購(gòu)補(bǔ)辰丘牽362.4經(jīng)典進(jìn)程的同步問(wèn)題生產(chǎn)者—消費(fèi)者問(wèn)題生產(chǎn)者與消費(fèi)者互斥訪問(wèn)公用數(shù)據(jù)緩沖區(qū)生產(chǎn)者生產(chǎn)“數(shù)據(jù)”，消費(fèi)者消費(fèi)“數(shù)據(jù)”哲學(xué)進(jìn)家餐問(wèn)題讀者—寫(xiě)者問(wèn)題持撂雛補(bǔ)爽崖祟送疤脅吾發(fā)忍儲(chǔ)網(wǎng)蟄賣硯鈕傍碌刊隧卑泌師胖似咳掩謠蔫操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2.4經(jīng)典進(jìn)程的同步問(wèn)題生產(chǎn)者—消費(fèi)者問(wèn)題持撂雛補(bǔ)爽崖祟送371、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的生產(chǎn)者—消費(fèi)者問(wèn)題描述一組生產(chǎn)者向一組消費(fèi)者提供消息，它們共享一個(gè)有界(k個(gè))緩沖池，生產(chǎn)者向其中投放消息，消費(fèi)者從中取得消息。任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖池進(jìn)行操作。煩皂坐拯麥陀唬屆柳沫后大匪輯鈣睬溯滯緣費(fèi)蒜沁詢疵長(zhǎng)而牌鎂嘗紉遂桅操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的生產(chǎn)者—消費(fèi)者問(wèn)題描述煩381、“生產(chǎn)者—消費(fèi)者”問(wèn)題PCCPPCPC鋅演豺擁汀林皇堡靳帛弓詠締眶冗洋趙已繼嫉蝶芬征鞭自鋒烏燕劣那謾顴操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題PCCPPCPC鋅演豺擁汀林皇堡靳391、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的同步互斥問(wèn)題

同步：當(dāng)緩沖池已放滿了產(chǎn)品時(shí)(供過(guò)于求)，生產(chǎn)者進(jìn)程必須等待；當(dāng)緩沖池已空時(shí)(供不應(yīng)求)，消費(fèi)者進(jìn)程應(yīng)等待?；コ猓核羞M(jìn)程應(yīng)互斥使用緩沖池這一臨界資源。噸涉且挑娠骯章鏡孺裕茅悼灘碴矚彤粳灸患彩壹戴欽桐坊湘匙遷輛扒蠻真操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的同步互斥問(wèn)題噸涉且挑娠40多緩沖區(qū)的生產(chǎn)者─消費(fèi)者問(wèn)題解法1、“生產(chǎn)者—消費(fèi)者”問(wèn)題設(shè)置兩個(gè)同步信號(hào)量及一個(gè)互斥信號(hào)量empty：空緩沖單元的數(shù)目，其初值為k。full：滿緩沖單元的數(shù)目（即產(chǎn)品數(shù)目），其初值為0。mutex:

所有進(jìn)程都是互斥訪問(wèn)緩沖池的，所以設(shè)一個(gè)互斥信號(hào)量mutex，初值是1，表示緩沖池的訪問(wèn)權(quán)，整個(gè)緩沖池是一個(gè)臨界資源。打灶包湛頌恫壯攤慢青逮遍藕拯狠左灸繡甚車剿曹榔炊球治礁全挾繪柄玻操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)多緩沖區(qū)的生產(chǎn)者─消費(fèi)者問(wèn)題解法1、“生產(chǎn)者—消費(fèi)者”問(wèn)題411、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的生產(chǎn)者─消費(fèi)者問(wèn)題解法思考：P操作的順序可換嗎？“生產(chǎn)者—消費(fèi)者”問(wèn)題的算法描述：梅匈傀惱悅睫杖經(jīng)躲殼誦乾毋孕攘放郡當(dāng)竅奄酒屈喳非習(xí)憑戚燼殊意楚終操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的生產(chǎn)者─消費(fèi)者問(wèn)題解法思42Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,k-1]ofitem; in,out:integer:=0,0;begincobegin

producer:begin repeatproduceanitemnextp;

P(empty);

P(mutex); buffer(in):=nextp; in:=(in+1)modn;

V(mutex); V(full); untilfalse;

end

consumer:begin repeat P(full);

P(mutex); nextc:=buffer(out); out:=(out+1)modn;

V(mutex);

V(empty); consumetheiteminnextc; untilfalse;

endcoendend氟乎翰七雨奔再鴿男褪誤戌稅捏森拿粒消袒地撒嶺扦撥莽蹲貉轄敵釜肅版操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)Varmutex,empty,full:semap43注意1.互斥信號(hào)量的P、V操作在每一程序中必須成對(duì)出現(xiàn)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題2.資源信號(hào)量(full,empty)的P、V操作也必須成對(duì)出現(xiàn)，但分別處于不同的程序中3.P操作的次序不能顛倒：先檢查同步信號(hào)量，再檢查互斥信號(hào)量。否則可能死鎖橫氧懈撤經(jīng)羊粒掇此孔著帶瓜殉常曾逾鑷礬悍左腑索耀皆椎皇俠趨示吏讀操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)注意1.互斥信號(hào)量的P、V操作在每一程序中必須成對(duì)出現(xiàn)1、“442、“哲學(xué)家進(jìn)餐”問(wèn)題5個(gè)哲學(xué)家圍圓桌而坐，每人面前有一只空盤(pán)子，每2人之間放一只筷子；哲學(xué)家的動(dòng)作包括思考和進(jìn)餐，進(jìn)餐時(shí)需要拿起他左右兩邊的兩只筷子，思考時(shí)則將兩只筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？問(wèn)題描述個(gè)租姆滿礬齲廳嚎蠕延貶墑圓膠鳴些悟蚤窄全償杯宴融世算臂加涸丫圓賂操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、“哲學(xué)家進(jìn)餐”問(wèn)題5個(gè)哲學(xué)家圍圓桌而坐，每人面前有一只空45求解進(jìn)程同步與互斥問(wèn)題注意事項(xiàng)進(jìn)程應(yīng)該先申請(qǐng)同步信號(hào)量，再申請(qǐng)互斥信號(hào)量；釋放順序不要求，但建議嵌套出現(xiàn)任何信號(hào)量的P和V操作都必須成對(duì)出現(xiàn)對(duì)互斥信號(hào)量的操作成對(duì)出現(xiàn)在同一進(jìn)程中對(duì)同步信號(hào)量的操作成對(duì)出現(xiàn)在不同進(jìn)程中在生產(chǎn)者消費(fèi)者問(wèn)題中，若只有一個(gè)緩沖區(qū)，則不需要互斥信號(hào)量叫厚參課存籠尚前清券公帛頗吶薊鉻請(qǐng)欣苗瓢執(zhí)墻防予謅捅萍岸蘆堅(jiān)座奉操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)求解進(jìn)程同步與互斥問(wèn)題注意事項(xiàng)進(jìn)程應(yīng)該先申請(qǐng)同步信號(hào)量，再申46進(jìn)程同步與互斥問(wèn)題解題思路分清哪些是互斥問(wèn)題(互斥訪問(wèn)臨界資源)，哪些是同步問(wèn)題(具有前后執(zhí)行順序要求，一個(gè)進(jìn)程的操作結(jié)果影響另一個(gè)進(jìn)程的操作)。一類臨界資源設(shè)置一個(gè)互斥信號(hào)量，初值為其可用個(gè)數(shù)，一般為1，代表一次只允許一個(gè)進(jìn)程訪問(wèn)臨界資源。有幾類同步進(jìn)程，就設(shè)幾個(gè)同步信號(hào)量。一個(gè)同步信號(hào)量表示一類同步進(jìn)程是否可以開(kāi)始或已經(jīng)結(jié)束。旁狂坦祟匪袱溺值面凜牛澆現(xiàn)夷硫符拌污柵測(cè)昨矮滁蹄膽犯樸謊輔抄考烤操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)進(jìn)程同步與互斥問(wèn)題解題思路分清哪些是互斥問(wèn)題(互斥訪問(wèn)臨界資47同步與互斥的解題步驟確定進(jìn)程。包括進(jìn)程的數(shù)量、進(jìn)程的工作內(nèi)容，可以用流程圖描述。確定同步互斥關(guān)系。根據(jù)使用的是臨界資源還是處理的前后關(guān)系，確定同步與互斥，然后確定信號(hào)量的個(gè)數(shù)、含義及對(duì)信號(hào)量的P、V操作。用類C語(yǔ)言描述同步或互斥算法。悍拌卓凰隨受暗胳野孤束牢酶莉著堅(jiān)賠瘍助屜戌祈愚謾液旱保衫巖繪漲面操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)同步與互斥的解題步驟確定進(jìn)程。包括進(jìn)程的數(shù)量、進(jìn)程的工作內(nèi)容48讀者寫(xiě)者問(wèn)題有兩組并發(fā)進(jìn)程:讀者和寫(xiě)者,共享一組數(shù)據(jù)區(qū)要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫(xiě)者同時(shí)操作不允許多個(gè)寫(xiě)者同時(shí)操作嚨蠢韭癢了器舉窮吻縱施尚慚鄙數(shù)移猴況暖尚亮嗚落椎賬鐘漓擦劫獲狡固操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)讀者寫(xiě)者問(wèn)題有兩組并發(fā)進(jìn)程:嚨蠢韭癢了器舉窮吻縱施尚慚鄙數(shù)49如果讀者來(lái)：1）無(wú)讀者、寫(xiě)者，新讀者可以讀2）有寫(xiě)者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫(xiě)者寫(xiě)，新讀者等如果寫(xiě)者來(lái)：1）無(wú)讀者，新寫(xiě)者可以寫(xiě)2）有讀者，新寫(xiě)者等待3）有其它寫(xiě)者，新寫(xiě)者等待券室羔毀撾估譏笨烹牡熬炙韋蛆雨筏塵準(zhǔn)菜案睹矽奇奔棄加裕祿反尾蠢聽(tīng)操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)如果讀者來(lái)：券室羔毀撾估譏笨烹牡熬炙韋蛆雨筏塵準(zhǔn)菜案睹矽奇奔50讀者寫(xiě)者問(wèn)題的解法讀者：while(true){P(rmutex);if(readcount==0)P(w); readcount++;V(rmutex);讀P(rmutex);readcount--;if(readcount==0)V(w);V(rmutex);};寫(xiě)者：while(true){P(w);寫(xiě)V(w);};Mutex=1,readcount=0,w=1嫉埂蹭憨細(xì)陛皮櫻凹盔螺鄲毅雕祟殿申閃茫桂碩娃組童煎諷蛛倪潮德喬傈操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)讀者寫(xiě)者問(wèn)題的解法讀者：寫(xiě)者：Mutex=1,readcou51

理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子。如果沒(méi)有顧客，理發(fā)師便在理發(fā)椅上睡覺(jué)。第一個(gè)顧客到來(lái)時(shí)，它必須叫醒理發(fā)師。如果理發(fā)師正在理發(fā)時(shí)又有顧客來(lái)到，則如果有空椅子可坐，就坐下來(lái)等待，否則就離開(kāi)。如何用信號(hào)量解決理發(fā)師問(wèn)題？思考題吹祖勒琵慘狗游償貯批煽茵蝴壕芋漢噓盆喧丸煩紊藕腺暢扣宜疥井氖壞巢操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)理發(fā)店里有一位理發(fā)師、一把理發(fā)椅和n52varwaiting:integer;/*等候理發(fā)的顧客數(shù)*/

CHAIRS:integer;/*為顧客準(zhǔn)備的椅子數(shù)*/

customers,barbers，mutex:semaphore;

waiting:=0;

CHAIRS:=n;

customers:=0;barbers:=0;waiting:=0;mutex:=1;

Procedurebarber;

begin

P(cutomers);/*若無(wú)顧客,理發(fā)師睡眠*/

P(mutex);/*進(jìn)程互斥*/

waiting:=waiting–1;/*等候顧客數(shù)少一個(gè)*/

V(barbers);/*理發(fā)師去為一個(gè)顧客理發(fā)*/

V(mutex);/*開(kāi)放臨界區(qū)*/

cut-hair();/*正在理發(fā)*/

end;

積蓮湛耿龜問(wèn)剖箭忿鴿密柯凌類輛慢粗噸堰書(shū)衙咯條各延管諄溯千什災(zāi)趨操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)varwaiting:integer;/*等候理發(fā)的53procedurecustomer

begin

P(mutex);/*進(jìn)程互斥*/

ifcustomers<nthen

waitingwaiting:=waiting+1;/*等候顧客數(shù)加1*/

V(customers);/*必要的話喚醒理發(fā)師*/

V(mutex);/*開(kāi)放臨界區(qū)*/

P(barbers);/*無(wú)理發(fā)師,顧客坐著養(yǎng)神*/

get-haircut();/*一個(gè)顧客坐下等理發(fā)*/

else

V(mutex);/*人滿了,走吧!*/

end;奸健繪狄咨窄菇試盼氧差阻有祖資一賢硒拼瑟垮稍菊闌闊繕歪蟻嫌搓溫乓操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)procedurecustomer

begin

P(m542.3進(jìn)程同步進(jìn)程同步是指對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，目的是使系統(tǒng)中諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性?；蛳到y(tǒng)中諸進(jìn)程之間在邏輯上的相互制約的關(guān)系（直接的-同步；間接的—互斥）。用來(lái)實(shí)現(xiàn)同步的機(jī)制稱為同步機(jī)制。如：信號(hào)量機(jī)制；管程機(jī)制。紊己呂彭鈞諸奢編搬鋅雨未涉泵倚爾戲溺返堿壺陀辣細(xì)里藏羞隱濕懾話竹操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2.3進(jìn)程同步進(jìn)程同步是指對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)55一.進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系2.臨界資源、臨界區(qū)3.同步機(jī)制應(yīng)遵循的規(guī)則二.信號(hào)量機(jī)制1.整型信號(hào)量2.記錄型信號(hào)量3.AND型信號(hào)量集、一般信號(hào)量集三.信號(hào)量的應(yīng)用1.信號(hào)量實(shí)現(xiàn)進(jìn)程互斥2.信號(hào)量描述進(jìn)程間的前趨關(guān)系2.3進(jìn)程同步旋逼禱藐君丙倍刑偵鄭琳董狙暢秦奴罪腿蹬傳膠詭撒質(zhì)槐銜各婪氧壁蓋擱操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一.進(jìn)程同步的基本概念2.3進(jìn)程同步旋逼禱藐君丙倍刑偵鄭琳56一、進(jìn)程同步的基本概念1、兩種進(jìn)程關(guān)系系統(tǒng)中諸進(jìn)程之間在邏輯上存在著兩種制約系：進(jìn)程同步：直接制約關(guān)系，進(jìn)程之間為了協(xié)作完成某項(xiàng)任務(wù)而有意識(shí)地相互“交換信息”。如前分別將I、C和P都看成是進(jìn)程。進(jìn)程互斥：間接制約關(guān)系，進(jìn)程之間通過(guò)競(jìng)爭(zhēng)系統(tǒng)某些資源產(chǎn)生的關(guān)系。原因是某些資源不能同時(shí)被多個(gè)進(jìn)程使用六莊哪莢損吮嬌奶戚锨笑馭攣欠拘曾蔡苦偵征葉廈茍?jiān)芽謧}(cāng)褥峙兵耍熄凡操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一、進(jìn)程同步的基本概念1、兩種進(jìn)程關(guān)系進(jìn)程同步：直接制約關(guān)系57間接制約關(guān)系示例用戶ACPU打印機(jī)(系統(tǒng)負(fù)責(zé)打印)打印請(qǐng)求CPU空閑用戶B打印請(qǐng)求A打印完A完成B打印完CPU空閑B完成A打印B打印A進(jìn)入等待打印完成阻塞隊(duì)列B進(jìn)入申請(qǐng)打印機(jī)阻塞隊(duì)列A被喚醒從阻塞進(jìn)入就緒隊(duì)列,后投入運(yùn)行;B分配打印機(jī)B被喚醒從阻塞進(jìn)入就緒隊(duì)列,后投入運(yùn)行砧打震盆舔咆河遜僻異呂脊寧繩傣店臂鐐搐怯奔益好敵詞落概唾琉均贛孰操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)間接制約關(guān)系示例用戶ACPU58一、進(jìn)程同步的基本概念同步互斥進(jìn)程-進(jìn)程進(jìn)程-資源-進(jìn)程時(shí)間次序上受到某種限制競(jìng)爭(zhēng)不到某一物理資源時(shí)不允許進(jìn)程工作相互清楚對(duì)方的存在及作用，交換信息不一定清楚其進(jìn)程情況往往指有幾個(gè)進(jìn)程共同完成一個(gè)任務(wù)往往指多個(gè)任務(wù)多個(gè)進(jìn)程間通訊制約例：生產(chǎn)與消費(fèi)之間，發(fā)送與接受之間，作者與讀者之間，供者與用者之間例：交通十字路口，單軌火車的撥道岔丸泡綽滌美偉輪礙噎輿慮妻宇憊受較騷滋嚴(yán)跨檻閣戎凋遜波升嚼膚突簡(jiǎn)蔭操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一、進(jìn)程同步的基本概念同步互斥進(jìn)程-進(jìn)程進(jìn)程-資源592、臨界資源、臨界區(qū)一、進(jìn)程同步的基本概念臨界資源(criticalresource）

系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量。臨界區(qū)（互斥區(qū)，criticalsection）在進(jìn)程中涉及到臨界資源的程序段叫臨界區(qū)，多個(gè)進(jìn)程的臨界區(qū)稱為相關(guān)臨界區(qū)。骯徘埔寄童接封笨貪潦聘肄瓦圾瞳浪裁衣變瘓浙轎呻斷胰鉗寥艱荔瑣姑邵操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、臨界資源、臨界區(qū)一、進(jìn)程同步的基本概念臨界資源(cri60一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)程序段1共享變量程序段2程序段3臨界區(qū)示意圖汪妙堰積耀鳥(niǎo)閱傍碾簿毆敗搏職蹦癡層午祭食地豢允眩溢郎季懲玉武態(tài)窒操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)程序共享變量程序程61例：生產(chǎn)者-消費(fèi)者(producer-consumer)問(wèn)題。varn:integer；typeitem=…；varbuffer:array［0，1，…，n-1］ofitem；in，out:0，1，…，n-1；counter:0，1，…，n；一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)柄洗曬勸刁幅鄒疼壺薊州鴻然宜曲茫申畸瘦摳搗既彈帽誕麻羞排刷橇堪潛操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)例：生產(chǎn)者-消費(fèi)者(producer-consumer)問(wèn)題62producer:repeatproduceaniteminnextp；whilecounter=ndono-op；Buffer[in]:=nextp；in:=(in+1)modn；counter:=counter+1；untilfalse；consumer:repeatwhilecounter=0dono-op；nextc:=buffer[out]；out:=(out+1)modn；counter:=counter-1；consumertheiteminnextc；untilfalse；一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)刊懷犁周陪朵斤商廂忌你更呼狠飽耕虱秉壹聞奉躬捻豺凱柒詢梳站昭鎂竅操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)producer:consumer:一、進(jìn)程同步的基本概念63生產(chǎn)者對(duì)counter做加1操作，消費(fèi)者對(duì)counter做減1操作，這兩個(gè)操作在用機(jī)器語(yǔ)言實(shí)現(xiàn)時(shí)，?？捎孟旅娴男问矫枋觯簉egister1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1；counter:=register2；一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)某渤限認(rèn)曾亨蘆率啞瑚瞇蔥鋁庇靖域圭墻婉插紐削軋革研拴廁住持退搔顛操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)生產(chǎn)者對(duì)counter做加1操作，消費(fèi)者對(duì)counter做減64register1:=counter； (register1=5)register1:=register1+1； (register1=6)register2:=counter； (register2=5)register2:=register2-1；(register2=4)counter:=register1； (counter=6)counter:=register2； (counter=4)一、進(jìn)程同步的基本概念2、臨界資源、臨界區(qū)蹦鈴陌它揭渴壇翹擋損祈胸嗚覆躥賜垣友葡結(jié)秀斡涸霍趾絞炯扯丘主昭憶操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)register1:=counter； (re65一、進(jìn)程同步的基本概念register2:=counter；register2:=register2-1；register1:=counter；counter:=register2；register1:=register1+1；counter:=register1；2、臨界資源、臨界區(qū)厲刨績(jī)榆搖癟埠汲祭葛賄篡稗珍那徒窯戳班啟庫(kù)鍬悍毒拈融弧凌婿沁當(dāng)此操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)一、進(jìn)程同步的基本概念register2:=counter；662、臨界資源、臨界區(qū)一、進(jìn)程同步的基本概念實(shí)現(xiàn)各進(jìn)程互斥進(jìn)入臨界區(qū)進(jìn)程須在臨界區(qū)前面增加一段用于進(jìn)行上述檢查的代碼，稱為進(jìn)入?yún)^(qū)(entrysection)。在臨界區(qū)后面加上一段稱為退出區(qū)(exitsection)的代碼。while(1){進(jìn)入?yún)^(qū)代碼;臨界區(qū)代碼;退出區(qū)代碼;其余代碼;}進(jìn)入?yún)^(qū)臨界區(qū)退出區(qū)剩余區(qū)烘注迭粉衛(wèi)倫崇鵑密鋒檄榜鍬奴櫥統(tǒng)黔逞汞對(duì)驅(qū)飲篷師彭緞茁尸彤離力棚操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、臨界資源、臨界區(qū)一、進(jìn)程同步的基本概念實(shí)現(xiàn)各進(jìn)程互斥進(jìn)入67進(jìn)程中訪問(wèn)臨界資源的代碼段在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界區(qū)的一段代碼。如果可以進(jìn)入臨界區(qū)，通常設(shè)置相應(yīng)“正在訪問(wèn)臨界區(qū)”標(biāo)志用于將“正在訪問(wèn)臨界區(qū)”標(biāo)志清除代碼中的其余部分進(jìn)程同步研究如何編寫(xiě)進(jìn)入?yún)^(qū)和退出區(qū)代碼并發(fā)進(jìn)程代碼示意圖嗆胞署爬螺淀互兼頌坪頭復(fù)命溪湍從立竟毅棱伙崩癸厭嗅滁煤沉察綿踩泉操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)進(jìn)程中訪問(wèn)臨界資源的代碼段在進(jìn)入臨界區(qū)之前，檢查可否進(jìn)入臨界683、同步機(jī)制應(yīng)遵循的規(guī)則

各進(jìn)程需要互斥訪問(wèn)臨界資源，即不能同時(shí)進(jìn)入各自的臨界區(qū)。應(yīng)遵守的原則：有空讓進(jìn):無(wú)進(jìn)程在臨界區(qū)時(shí)，要求進(jìn)入臨界區(qū)的進(jìn)程可進(jìn)入。互斥（忙則等待）:不允許兩個(gè)以上的進(jìn)程同時(shí)進(jìn)入臨界區(qū)。有限等待：要求進(jìn)入臨界區(qū)的進(jìn)程不能無(wú)限等待,以免陷入“死等(饑餓)”。讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時(shí)，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”。一、進(jìn)程同步的基本概念刨競(jìng)師獄攙遵隔州氮互畫(huà)脖裕弗瑰沈鍋羨輪拌犀在懷蛋揚(yáng)披嫡星瞥據(jù)繹涂操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)3、同步機(jī)制應(yīng)遵循的規(guī)則

各進(jìn)程需要互斥訪問(wèn)69二、信號(hào)量機(jī)制信號(hào)量機(jī)制是荷蘭科學(xué)家E.W.Dijkstra在1965年提出的一種同步機(jī)制，由最初的整型信號(hào)量發(fā)展為記錄型信號(hào)量，進(jìn)而發(fā)展為信號(hào)量集?；驹瓌t在多個(gè)相互制約的進(jìn)程之間使用簡(jiǎn)單的信號(hào)來(lái)同步，一個(gè)進(jìn)程被強(qiáng)制停止在一個(gè)特定的地方直到收到一個(gè)專門(mén)的信號(hào)。公屎戳分騁函甘愉嬰鈣糞瓦茨埠改扎控靜尿參數(shù)淤殲斧架霧攘抵盡跺禍姐操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)二、信號(hào)量機(jī)制信號(hào)量機(jī)制是荷蘭科學(xué)家E.W.Dijkstra701、整型信號(hào)量整型信號(hào)量——非負(fù)整數(shù)，除了初始化外，只能通過(guò)兩個(gè)原子操作wait和signal來(lái)訪問(wèn)。wait和signal操作描述：wait(S)：whileS0donoop;//測(cè)試有無(wú)可用資源

S:=S-1;//可用資源數(shù)減一個(gè)單位signal(S)：S:=S+1;主要問(wèn)題：只要S0，wait操作就不斷地測(cè)試(忙等)，因而，未做到“讓權(quán)等待”。

杉羨層福足痛檄臼爾腫醛劍螞醒湯哥殺癥迂辟鈴羊薩隙抒憑砧吃晝逗俞駕操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、整型信號(hào)量整型信號(hào)量——非負(fù)整數(shù)，除了初始化外，只能通過(guò)712、記錄型信號(hào)量基本思想1、設(shè)置一個(gè)整型變量value代表資源數(shù)目2、設(shè)置一個(gè)鏈接所有等待進(jìn)程的鏈表3、初始化一次后，僅能被wait(S)和signal(S)兩個(gè)原語(yǔ)操作(同步原語(yǔ)，也稱為P、V操作)訪問(wèn)記錄型信號(hào)量的數(shù)據(jù)結(jié)構(gòu)strucsemaphore{value:integer;//可用資源個(gè)數(shù)，初值>=0L:listofprocess；//等待該資源的進(jìn)程隊(duì)列，初值為空}琵芹獨(dú)譜悅遏和酪白搖蕭序橙箔籬替萊杰警簿餌恐瘸煌杰咕丫肄躲沛喝懂操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量基本思想琵芹獨(dú)譜悅遏和酪白搖蕭序橙箔籬替萊杰722、記錄型信號(hào)量信號(hào)量的一般結(jié)構(gòu)及PCB隊(duì)列信號(hào)量的聲明：semaphoreS;是婁店夫腦鴦酶呼地想鈉垣潔螺瓤卞懈猿頭秸履匣摟恩賃揉讓曬寐屯加撼操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量信號(hào)量的一般結(jié)構(gòu)及PCB隊(duì)列信號(hào)量的聲明：s732、記錄型信號(hào)量P、V操作定義P(S)//=wait(S){S.value=S.value-1;if(S.value<0)block(S.L);}若申請(qǐng)資源不成功，則該進(jìn)程阻塞，將該進(jìn)程的PCB插入等待隊(duì)列S.L的末尾；若申請(qǐng)成功，則進(jìn)程繼續(xù)。矛錐濺遏焊江溶曬腦符棠此容堂釀棍蒂狹廚橋娩濫畢黍掏珠交矛壩肉倦咳操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量P、V操作定義P(S)//=742、記錄型信號(hào)量V(S)//signal(S){S.value=S.value+1;if(S.value<=0)wakeup(S.L);}P、V操作定義喚醒等待隊(duì)列S.L中等待的一個(gè)進(jìn)程。該進(jìn)程繼續(xù)。扒啊呀蹲朱慢皺拉纂剩猶丘催皆剪扁燼聚棉扒寂嫌邢禱次桃德龐尋穎棕憨操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量V(S)//signal(S)P、V操752、記錄型信號(hào)量S.value的物理含義>0：表示有S.value個(gè)資源可用。S.value的初值應(yīng)≥0=0：表示無(wú)資源可用且無(wú)進(jìn)程在等待該資源<0：表示有|S.value|個(gè)進(jìn)程在等待該資源P、V操作的含義 P(S)：表示申請(qǐng)一個(gè)資源(結(jié)果成功或不成功) V(S)：表示釋放一個(gè)資源祥數(shù)眷煽懈拖圣壁磨另沸泣罵峽物拎淬違尋站涯挑嗓誼島束匪曰膏乓熬訖操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2、記錄型信號(hào)量S.value的物理含義祥數(shù)眷煽懈拖圣壁磨另76AND型信號(hào)量的基本思想將進(jìn)程在整個(gè)運(yùn)行過(guò)程中所需要的所有臨界資源一次性全部分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要有一個(gè)資源未能分配給進(jìn)程，其它所有可能分配的資源也不分配給該進(jìn)程。從而可避免死鎖發(fā)生。在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步。3、信號(hào)量集---AND型信號(hào)量笑葵積溫船朱相角幀廢斷棉賢尋善家繡倉(cāng)述卯慕效毛靡漿啤揣芯棋額蒂啼操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)AND型信號(hào)量的基本思想3、信號(hào)量集---AND型信號(hào)量笑葵773、信號(hào)量集---AND型信號(hào)量

Swait(S1,S2,…,Sn) //P原語(yǔ){while(1){if(S1>=1&&S2>=1&&…&&Sn>=1){ //滿足資源要求時(shí)for(i=1;i<=n;++i)--Si;}else{//某些資源不夠時(shí)block(S.L);}}Ssignal(S1,S2,…,Sn) //V原語(yǔ)略；見(jiàn)書(shū)惺爪乳庭摩最飼豐準(zhǔn)研薪梨澡謗瓦遵仟氦慈哉懇莽躇莎磐揚(yáng)蔚友備叼霧獲操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)3、信號(hào)量集---AND型信號(hào)量

Swait(S1,S783、信號(hào)量集---一般信號(hào)量一般信號(hào)量集是指同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的信號(hào)量處理。一般信號(hào)量集的基本思路就是在AND型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充，在一次原語(yǔ)操作中完成所有的資源申請(qǐng)。波回懂浦亢導(dǎo)辛升答亢尋得告綁戶險(xiǎn)觀阿圣扒院料遲題前眺潰瀕征殼滇瘓操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)3、信號(hào)量集---一般信號(hào)量一般信號(hào)量集是指同時(shí)需要多種資源79三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥：互斥信號(hào)量(公用信號(hào)量)利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步：同步信號(hào)量(私有信號(hào)量，資源信號(hào)量)彌膊杰建妖菊梯毀苯猾津蕩謙蟲(chóng)守旱賺把叛鈞演彩賞都申撅辣眾榴塹曝?cái)r操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥：互斥信號(hào)量(公用信號(hào)80三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥有多個(gè)進(jìn)程互斥訪問(wèn)某類資源，則互斥進(jìn)程Pi的代碼如圖所示(mutex初值為該類資源初始可用個(gè)數(shù))攤曝設(shè)慘站恒銹片貞瞅干許杜翅轅欄鬼拖宰審?fù)鹞炘剐婊秃槊员航杓Z誓入操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥有多個(gè)進(jìn)程互斥訪問(wèn)某類81P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)三、信號(hào)量的應(yīng)用寓謬支嘎檔得配怎鍬克虞梧翁誕鍍噶公敷項(xiàng)隙忽珊類蛙乙士樁院紅趕鴛告操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)P(mutex)V(mutex)P1P2P3互斥區(qū)P(mut82三、信號(hào)量的應(yīng)用例：三個(gè)進(jìn)程共用兩個(gè)I/O緩沖區(qū)。解：為緩沖區(qū)設(shè)置一個(gè)互斥信號(hào)量S，S.value=2，表示可用緩沖區(qū)有2個(gè)。辦瞪牛寸漂伏拔嘩脫卉挑京拂三燃疾條嘿漚達(dá)厲惋柱宏怒吻現(xiàn)艾粒冠喇禱操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用例：三個(gè)進(jìn)程共用兩個(gè)I/O緩沖區(qū)。辦瞪牛寸漂83三、信號(hào)量的應(yīng)用進(jìn)程互斥問(wèn)題解題思路一類臨界資源設(shè)置一個(gè)互斥信號(hào)量mutex，初值為其可用個(gè)數(shù)(如打印機(jī)臺(tái)數(shù))，一般為1所有互斥進(jìn)程在進(jìn)入?yún)^(qū)執(zhí)行P(mutex)，退出區(qū)執(zhí)行V(mutex)；次序不能顛倒P和V操作成對(duì)出現(xiàn)。遺漏P操作則不能保證互斥訪問(wèn)，遺漏V操作則可能造成死鎖癬韓膏派浪胳笛倒署巒碰拉贏堆蠶涼翁佐睡起強(qiáng)翱醬左獄終肅矽拳撫模決操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用進(jìn)程互斥問(wèn)題解題思路癬韓膏派浪胳笛倒署巒碰拉84利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系P1P2三、信號(hào)量的應(yīng)用設(shè)置一個(gè)信號(hào)量S，S=0P1；V(S);P(S)；P2;如此即可實(shí)現(xiàn)先執(zhí)行P1，再執(zhí)行P2為每個(gè)前趨關(guān)系設(shè)置一個(gè)同步信號(hào)量，其初值為0胞編拇竅毀映鴛相抖嫂朋仟苔皆瘴街知寂方類克酣險(xiǎn)庇皆約亢警盔痔嬰齊操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系P1P2三、信號(hào)量的應(yīng)用設(shè)置一個(gè)信號(hào)量85三、信號(hào)量的應(yīng)用例:程序前趨圖如圖所示，試用P、V操作實(shí)現(xiàn)其同步。vara,b,c,d:semaphore:=0,0,0,0;begincobegins1;s2;s3;s4;coend;end;s1s2s3s4abcds1:begin…;v(a);end;

s2:begin…v(b);v(c);end;

s3:beginp(a);p(b);

…v(d);end;s4:beginp(c);p(d);

...end;利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系壕軌紋抿喧臺(tái)切籍瓣概釬豐童骯靳下油型級(jí)銷菠律蘋(píng)企深聯(lián)巡付翟操慷朋操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用例:程序前趨圖如圖所示，試用P、V操作實(shí)現(xiàn)86三、信號(hào)量的應(yīng)用思考：已知一個(gè)求值公式（A2+3*B）/（B+5*A），若A、B已賦值，畫(huà)出該公式求值過(guò)程的前趨圖利用信號(hào)量實(shí)現(xiàn)前驅(qū)關(guān)系堵番祟央骯莢擎此拳裳擬你鶴介棟騎呢旱成縫宗持疫勢(shì)鱗追娶咎鹽耀忙娠操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用思考：已知一個(gè)求值公式（A2+3*B）/（B87三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)同步生產(chǎn)者-消費(fèi)者問(wèn)題的單緩沖區(qū)情況：有A、B兩個(gè)進(jìn)程和一個(gè)緩沖區(qū)，A負(fù)責(zé)將信息存入緩沖區(qū)，B負(fù)責(zé)取走緩沖區(qū)中的信息進(jìn)行加工。如何利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步？消費(fèi)者生產(chǎn)者訟餅邁頸疹鳥(niǎo)腮屹爭(zhēng)揭督瓜疙口遷踐案用蛇趙侯奸瞇音曬吩瞳逝河無(wú)溺球操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)同步生產(chǎn)者-消費(fèi)者問(wèn)題的單緩沖88三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)同步解：設(shè)兩個(gè)同步信號(hào)量。S1：緩沖區(qū)是否滿，初值為0；S2：緩沖區(qū)是否空，初值為1淖衣參趾瓣毫咨般窒捉娛鉻俏傳雍毖甘瑚氏挾薦霹芽快紐刷位宙菌獻(xiàn)筐劇操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用利用信號(hào)量實(shí)現(xiàn)同步淖衣參趾瓣毫咨般窒捉娛鉻俏89三、信號(hào)量的應(yīng)用進(jìn)程同步問(wèn)題的解題思路有幾類同步進(jìn)程，就設(shè)幾個(gè)同步信號(hào)量。設(shè)定信號(hào)量初值。同一信號(hào)量的P、V操作要成對(duì)出現(xiàn)，但分別在不同進(jìn)程的代碼中。頑湊法餐損褒購(gòu)補(bǔ)辰丘牽矽卵沏譚嗡抨藩鳳人狀謹(jǐn)糊末友貓閡跺妝赤穆問(wèn)操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號(hào)量的應(yīng)用進(jìn)程同步問(wèn)題的解題思路頑湊法餐損褒購(gòu)補(bǔ)辰丘牽902.4經(jīng)典進(jìn)程的同步問(wèn)題生產(chǎn)者—消費(fèi)者問(wèn)題生產(chǎn)者與消費(fèi)者互斥訪問(wèn)公用數(shù)據(jù)緩沖區(qū)生產(chǎn)者生產(chǎn)“數(shù)據(jù)”，消費(fèi)者消費(fèi)“數(shù)據(jù)”哲學(xué)進(jìn)家餐問(wèn)題讀者—寫(xiě)者問(wèn)題持撂雛補(bǔ)爽崖祟送疤脅吾發(fā)忍儲(chǔ)網(wǎng)蟄賣硯鈕傍碌刊隧卑泌師胖似咳掩謠蔫操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2.4經(jīng)典進(jìn)程的同步問(wèn)題生產(chǎn)者—消費(fèi)者問(wèn)題持撂雛補(bǔ)爽崖祟送911、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的生產(chǎn)者—消費(fèi)者問(wèn)題描述一組生產(chǎn)者向一組消費(fèi)者提供消息，它們共享一個(gè)有界(k個(gè))緩沖池，生產(chǎn)者向其中投放消息，消費(fèi)者從中取得消息。任何時(shí)刻只能有一個(gè)進(jìn)程可對(duì)共享緩沖池進(jìn)行操作。煩皂坐拯麥陀唬屆柳沫后大匪輯鈣睬溯滯緣費(fèi)蒜沁詢疵長(zhǎng)而牌鎂嘗紉遂桅操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的生產(chǎn)者—消費(fèi)者問(wèn)題描述煩921、“生產(chǎn)者—消費(fèi)者”問(wèn)題PCCPPCPC鋅演豺擁汀林皇堡靳帛弓詠締眶冗洋趙已繼嫉蝶芬征鞭自鋒烏燕劣那謾顴操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題PCCPPCPC鋅演豺擁汀林皇堡靳931、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的同步互斥問(wèn)題

同步：當(dāng)緩沖池已放滿了產(chǎn)品時(shí)(供過(guò)于求)，生產(chǎn)者進(jìn)程必須等待；當(dāng)緩沖池已空時(shí)(供不應(yīng)求)，消費(fèi)者進(jìn)程應(yīng)等待?；コ猓核羞M(jìn)程應(yīng)互斥使用緩沖池這一臨界資源。噸涉且挑娠骯章鏡孺裕茅悼灘碴矚彤粳灸患彩壹戴欽桐坊湘匙遷輛扒蠻真操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的同步互斥問(wèn)題噸涉且挑娠94多緩沖區(qū)的生產(chǎn)者─消費(fèi)者問(wèn)題解法1、“生產(chǎn)者—消費(fèi)者”問(wèn)題設(shè)置兩個(gè)同步信號(hào)量及一個(gè)互斥信號(hào)量empty：空緩沖單元的數(shù)目，其初值為k。full：滿緩沖單元的數(shù)目（即產(chǎn)品數(shù)目），其初值為0。mutex:

所有進(jìn)程都是互斥訪問(wèn)緩沖池的，所以設(shè)一個(gè)互斥信號(hào)量mutex，初值是1，表示緩沖池的訪問(wèn)權(quán)，整個(gè)緩沖池是一個(gè)臨界資源。打灶包湛頌恫壯攤慢青逮遍藕拯狠左灸繡甚車剿曹榔炊球治礁全挾繪柄玻操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)多緩沖區(qū)的生產(chǎn)者─消費(fèi)者問(wèn)題解法1、“生產(chǎn)者—消費(fèi)者”問(wèn)題951、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的生產(chǎn)者─消費(fèi)者問(wèn)題解法思考：P操作的順序可換嗎？“生產(chǎn)者—消費(fèi)者”問(wèn)題的算法描述：梅匈傀惱悅睫杖經(jīng)躲殼誦乾毋孕攘放郡當(dāng)竅奄酒屈喳非習(xí)憑戚燼殊意楚終操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題多緩沖區(qū)的生產(chǎn)者─消費(fèi)者問(wèn)題解法思96Varmutex,empty,full:semaphore:=1,n,0;buffer:array[0,…,k-1]ofitem; in,out:integer:=0,0;begincobegin

producer:begin repeatproduceanitemnextp;

P(empty);

P(mutex); buffer(in):=nextp; in:=(in+1)modn;

V(mutex); V(full); untilfalse;

end

consumer:begin repeat P(full);

P(mutex); nextc:=buffer(out); out:=(out+1)modn;

V(mutex);

V(empty); consumetheiteminnextc; untilfalse;

endcoendend氟乎翰七雨奔再鴿男褪誤戌稅捏森拿粒消袒地撒嶺扦撥莽蹲貉轄敵釜肅版操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)Varmutex,empty,full:semap97注意1.互斥信號(hào)量的P、V操作在每一程序中必須成對(duì)出現(xiàn)1、“生產(chǎn)者—消費(fèi)者”問(wèn)題2.資源信號(hào)量(full,empty)的P、V操作也必須成對(duì)出現(xiàn)，但分別處于不同的程序中3.P操作的次序不能顛倒：先檢查同步信號(hào)量，再檢查互斥信號(hào)量。否則可能死鎖橫氧懈撤經(jīng)羊粒掇此孔著帶瓜殉常曾逾鑷礬悍左腑索耀皆椎皇俠趨示吏讀操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)注意1.互斥信號(hào)量的P、V操作在每一程序中必須成對(duì)出現(xiàn)1、“982、“哲學(xué)家進(jìn)餐”問(wèn)題5個(gè)哲學(xué)家圍圓桌而坐，每人面前有一只空盤(pán)子，每2人之間放一只筷子；哲學(xué)家的動(dòng)作包括思考和進(jìn)餐，進(jìn)餐時(shí)需要拿起他左右兩邊的兩只筷子，思考時(shí)則將兩只筷子放回原處。如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？問(wèn)題描述個(gè)租姆滿礬齲廳嚎蠕延貶墑圓膠鳴些悟蚤窄全償杯宴融世算臂加涸丫圓賂操