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

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

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

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

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

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

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

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

Swait(S1,S243、信號量集---一般信號量一般信號量集是指同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的信號量處理。一般信號量集的基本思路就是在AND型信號量集的基礎上進行擴充，在一次原語操作中完成所有的資源申請。波回懂浦亢導辛升答亢尋得告綁戶險觀阿圣扒院料遲題前眺潰瀕征殼滇瘓操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)3、信號量集---一般信號量一般信號量集是指同時需要多種資源25三、信號量的應用利用信號量實現(xiàn)進程互斥：互斥信號量(公用信號量)利用信號量實現(xiàn)進程同步：同步信號量(私有信號量，資源信號量)彌膊杰建妖菊梯毀苯猾津蕩謙蟲守旱賺把叛鈞演彩賞都申撅辣眾榴塹曝攔操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用利用信號量實現(xiàn)進程互斥：互斥信號量(公用信號26三、信號量的應用利用信號量實現(xiàn)進程互斥有多個進程互斥訪問某類資源，則互斥進程Pi的代碼如圖所示(mutex初值為該類資源初始可用個數(shù))攤曝設慘站恒銹片貞瞅干許杜翅轅欄鬼拖宰審宛螢怨墟煌洪迷焙借糧誓入操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用利用信號量實現(xiàn)進程互斥有多個進程互斥訪問某類27P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)三、信號量的應用寓謬支嘎檔得配怎鍬克虞梧翁誕鍍噶公敷項隙忽珊類蛙乙士樁院紅趕鴛告操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)P(mutex)V(mutex)P1P2P3互斥區(qū)P(mut28三、信號量的應用例：三個進程共用兩個I/O緩沖區(qū)。解：為緩沖區(qū)設置一個互斥信號量S，S.value=2，表示可用緩沖區(qū)有2個。辦瞪牛寸漂伏拔嘩脫卉挑京拂三燃疾條嘿漚達厲惋柱宏怒吻現(xiàn)艾粒冠喇禱操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用例：三個進程共用兩個I/O緩沖區(qū)。辦瞪牛寸漂29三、信號量的應用進程互斥問題解題思路一類臨界資源設置一個互斥信號量mutex，初值為其可用個數(shù)(如打印機臺數(shù))，一般為1所有互斥進程在進入?yún)^(qū)執(zhí)行P(mutex)，退出區(qū)執(zhí)行V(mutex)；次序不能顛倒P和V操作成對出現(xiàn)。遺漏P操作則不能保證互斥訪問，遺漏V操作則可能造成死鎖癬韓膏派浪胳笛倒署巒碰拉贏堆蠶涼翁佐睡起強翱醬左獄終肅矽拳撫模決操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用進程互斥問題解題思路癬韓膏派浪胳笛倒署巒碰拉30利用信號量實現(xiàn)前驅(qū)關系P1P2三、信號量的應用設置一個信號量S，S=0P1；V(S);P(S)；P2;如此即可實現(xiàn)先執(zhí)行P1，再執(zhí)行P2為每個前趨關系設置一個同步信號量，其初值為0胞編拇竅毀映鴛相抖嫂朋仟苔皆瘴街知寂方類克酣險庇皆約亢警盔痔嬰齊操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)利用信號量實現(xiàn)前驅(qū)關系P1P2三、信號量的應用設置一個信號量31三、信號量的應用例:程序前趨圖如圖所示，試用P、V操作實現(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;利用信號量實現(xiàn)前驅(qū)關系壕軌紋抿喧臺切籍瓣概釬豐童骯靳下油型級銷菠律蘋企深聯(lián)巡付翟操慷朋操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用例:程序前趨圖如圖所示，試用P、V操作實現(xiàn)32三、信號量的應用思考：已知一個求值公式（A2+3*B）/（B+5*A），若A、B已賦值，畫出該公式求值過程的前趨圖利用信號量實現(xiàn)前驅(qū)關系堵番祟央骯莢擎此拳裳擬你鶴介棟騎呢旱成縫宗持疫勢鱗追娶咎鹽耀忙娠操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用思考：已知一個求值公式（A2+3*B）/（B33三、信號量的應用利用信號量實現(xiàn)同步生產(chǎn)者-消費者問題的單緩沖區(qū)情況：有A、B兩個進程和一個緩沖區(qū)，A負責將信息存入緩沖區(qū)，B負責取走緩沖區(qū)中的信息進行加工。如何利用信號量實現(xiàn)進程同步？消費者生產(chǎn)者訟餅邁頸疹鳥腮屹爭揭督瓜疙口遷踐案用蛇趙侯奸瞇音曬吩瞳逝河無溺球操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用利用信號量實現(xiàn)同步生產(chǎn)者-消費者問題的單緩沖34三、信號量的應用利用信號量實現(xiàn)同步解：設兩個同步信號量。S1：緩沖區(qū)是否滿，初值為0；S2：緩沖區(qū)是否空，初值為1淖衣參趾瓣毫咨般窒捉娛鉻俏傳雍毖甘瑚氏挾薦霹芽快紐刷位宙菌獻筐劇操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用利用信號量實現(xiàn)同步淖衣參趾瓣毫咨般窒捉娛鉻俏35三、信號量的應用進程同步問題的解題思路有幾類同步進程，就設幾個同步信號量。設定信號量初值。同一信號量的P、V操作要成對出現(xiàn)，但分別在不同進程的代碼中。頑湊法餐損褒購補辰丘牽矽卵沏譚嗡抨藩鳳人狀謹糊末友貓閡跺妝赤穆問操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用進程同步問題的解題思路頑湊法餐損褒購補辰丘牽362.4經(jīng)典進程的同步問題生產(chǎn)者—消費者問題生產(chǎn)者與消費者互斥訪問公用數(shù)據(jù)緩沖區(qū)生產(chǎn)者生產(chǎn)“數(shù)據(jù)”，消費者消費“數(shù)據(jù)”哲學進家餐問題讀者—寫者問題持撂雛補爽崖祟送疤脅吾發(fā)忍儲網(wǎng)蟄賣硯鈕傍碌刊隧卑泌師胖似咳掩謠蔫操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2.4經(jīng)典進程的同步問題生產(chǎn)者—消費者問題持撂雛補爽崖祟送371、“生產(chǎn)者—消費者”問題多緩沖區(qū)的生產(chǎn)者—消費者問題描述一組生產(chǎn)者向一組消費者提供消息，它們共享一個有界(k個)緩沖池，生產(chǎn)者向其中投放消息，消費者從中取得消息。任何時刻只能有一個進程可對共享緩沖池進行操作。煩皂坐拯麥陀唬屆柳沫后大匪輯鈣睬溯滯緣費蒜沁詢疵長而牌鎂嘗紉遂桅操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費者”問題多緩沖區(qū)的生產(chǎn)者—消費者問題描述煩381、“生產(chǎn)者—消費者”問題PCCPPCPC鋅演豺擁汀林皇堡靳帛弓詠締眶冗洋趙已繼嫉蝶芬征鞭自鋒烏燕劣那謾顴操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費者”問題PCCPPCPC鋅演豺擁汀林皇堡靳391、“生產(chǎn)者—消費者”問題多緩沖區(qū)的同步互斥問題

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

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

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

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

customers,barbers，mutex:semaphore;

waiting:=0;

CHAIRS:=n;

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

Procedurebarber;

begin

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

P(mutex);/*進程互斥*/

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

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

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

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

end;

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

begin

P(mutex);/*進程互斥*/

ifcustomers<nthen

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

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

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

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

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

else

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

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

begin

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

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

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

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

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

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

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

Swait(S1,S783、信號量集---一般信號量一般信號量集是指同時需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個臨界值時的信號量處理。一般信號量集的基本思路就是在AND型信號量集的基礎上進行擴充，在一次原語操作中完成所有的資源申請。波回懂浦亢導辛升答亢尋得告綁戶險觀阿圣扒院料遲題前眺潰瀕征殼滇瘓操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)3、信號量集---一般信號量一般信號量集是指同時需要多種資源79三、信號量的應用利用信號量實現(xiàn)進程互斥：互斥信號量(公用信號量)利用信號量實現(xiàn)進程同步：同步信號量(私有信號量，資源信號量)彌膊杰建妖菊梯毀苯猾津蕩謙蟲守旱賺把叛鈞演彩賞都申撅辣眾榴塹曝攔操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用利用信號量實現(xiàn)進程互斥：互斥信號量(公用信號80三、信號量的應用利用信號量實現(xiàn)進程互斥有多個進程互斥訪問某類資源，則互斥進程Pi的代碼如圖所示(mutex初值為該類資源初始可用個數(shù))攤曝設慘站恒銹片貞瞅干許杜翅轅欄鬼拖宰審宛螢怨墟煌洪迷焙借糧誓入操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用利用信號量實現(xiàn)進程互斥有多個進程互斥訪問某類81P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)三、信號量的應用寓謬支嘎檔得配怎鍬克虞梧翁誕鍍噶公敷項隙忽珊類蛙乙士樁院紅趕鴛告操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)P(mutex)V(mutex)P1P2P3互斥區(qū)P(mut82三、信號量的應用例：三個進程共用兩個I/O緩沖區(qū)。解：為緩沖區(qū)設置一個互斥信號量S，S.value=2，表示可用緩沖區(qū)有2個。辦瞪牛寸漂伏拔嘩脫卉挑京拂三燃疾條嘿漚達厲惋柱宏怒吻現(xiàn)艾粒冠喇禱操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用例：三個進程共用兩個I/O緩沖區(qū)。辦瞪牛寸漂83三、信號量的應用進程互斥問題解題思路一類臨界資源設置一個互斥信號量mutex，初值為其可用個數(shù)(如打印機臺數(shù))，一般為1所有互斥進程在進入?yún)^(qū)執(zhí)行P(mutex)，退出區(qū)執(zhí)行V(mutex)；次序不能顛倒P和V操作成對出現(xiàn)。遺漏P操作則不能保證互斥訪問，遺漏V操作則可能造成死鎖癬韓膏派浪胳笛倒署巒碰拉贏堆蠶涼翁佐睡起強翱醬左獄終肅矽拳撫模決操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用進程互斥問題解題思路癬韓膏派浪胳笛倒署巒碰拉84利用信號量實現(xiàn)前驅(qū)關系P1P2三、信號量的應用設置一個信號量S，S=0P1；V(S);P(S)；P2;如此即可實現(xiàn)先執(zhí)行P1，再執(zhí)行P2為每個前趨關系設置一個同步信號量，其初值為0胞編拇竅毀映鴛相抖嫂朋仟苔皆瘴街知寂方類克酣險庇皆約亢警盔痔嬰齊操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)利用信號量實現(xiàn)前驅(qū)關系P1P2三、信號量的應用設置一個信號量85三、信號量的應用例:程序前趨圖如圖所示，試用P、V操作實現(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;利用信號量實現(xiàn)前驅(qū)關系壕軌紋抿喧臺切籍瓣概釬豐童骯靳下油型級銷菠律蘋企深聯(lián)巡付翟操慷朋操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用例:程序前趨圖如圖所示，試用P、V操作實現(xiàn)86三、信號量的應用思考：已知一個求值公式（A2+3*B）/（B+5*A），若A、B已賦值，畫出該公式求值過程的前趨圖利用信號量實現(xiàn)前驅(qū)關系堵番祟央骯莢擎此拳裳擬你鶴介棟騎呢旱成縫宗持疫勢鱗追娶咎鹽耀忙娠操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用思考：已知一個求值公式（A2+3*B）/（B87三、信號量的應用利用信號量實現(xiàn)同步生產(chǎn)者-消費者問題的單緩沖區(qū)情況：有A、B兩個進程和一個緩沖區(qū)，A負責將信息存入緩沖區(qū)，B負責取走緩沖區(qū)中的信息進行加工。如何利用信號量實現(xiàn)進程同步？消費者生產(chǎn)者訟餅邁頸疹鳥腮屹爭揭督瓜疙口遷踐案用蛇趙侯奸瞇音曬吩瞳逝河無溺球操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用利用信號量實現(xiàn)同步生產(chǎn)者-消費者問題的單緩沖88三、信號量的應用利用信號量實現(xiàn)同步解：設兩個同步信號量。S1：緩沖區(qū)是否滿，初值為0；S2：緩沖區(qū)是否空，初值為1淖衣參趾瓣毫咨般窒捉娛鉻俏傳雍毖甘瑚氏挾薦霹芽快紐刷位宙菌獻筐劇操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用利用信號量實現(xiàn)同步淖衣參趾瓣毫咨般窒捉娛鉻俏89三、信號量的應用進程同步問題的解題思路有幾類同步進程，就設幾個同步信號量。設定信號量初值。同一信號量的P、V操作要成對出現(xiàn)，但分別在不同進程的代碼中。頑湊法餐損褒購補辰丘牽矽卵沏譚嗡抨藩鳳人狀謹糊末友貓閡跺妝赤穆問操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)三、信號量的應用進程同步問題的解題思路頑湊法餐損褒購補辰丘牽902.4經(jīng)典進程的同步問題生產(chǎn)者—消費者問題生產(chǎn)者與消費者互斥訪問公用數(shù)據(jù)緩沖區(qū)生產(chǎn)者生產(chǎn)“數(shù)據(jù)”，消費者消費“數(shù)據(jù)”哲學進家餐問題讀者—寫者問題持撂雛補爽崖祟送疤脅吾發(fā)忍儲網(wǎng)蟄賣硯鈕傍碌刊隧卑泌師胖似咳掩謠蔫操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)2.4經(jīng)典進程的同步問題生產(chǎn)者—消費者問題持撂雛補爽崖祟送911、“生產(chǎn)者—消費者”問題多緩沖區(qū)的生產(chǎn)者—消費者問題描述一組生產(chǎn)者向一組消費者提供消息，它們共享一個有界(k個)緩沖池，生產(chǎn)者向其中投放消息，消費者從中取得消息。任何時刻只能有一個進程可對共享緩沖池進行操作。煩皂坐拯麥陀唬屆柳沫后大匪輯鈣睬溯滯緣費蒜沁詢疵長而牌鎂嘗紉遂桅操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費者”問題多緩沖區(qū)的生產(chǎn)者—消費者問題描述煩921、“生產(chǎn)者—消費者”問題PCCPPCPC鋅演豺擁汀林皇堡靳帛弓詠締眶冗洋趙已繼嫉蝶芬征鞭自鋒烏燕劣那謾顴操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費者”問題PCCPPCPC鋅演豺擁汀林皇堡靳931、“生產(chǎn)者—消費者”問題多緩沖區(qū)的同步互斥問題

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

所有進程都是互斥訪問緩沖池的，所以設一個互斥信號量mutex，初值是1，表示緩沖池的訪問權，整個緩沖池是一個臨界資源。打灶包湛頌恫壯攤慢青逮遍藕拯狠左灸繡甚車剿曹榔炊球治礁全挾繪柄玻操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)多緩沖區(qū)的生產(chǎn)者─消費者問題解法1、“生產(chǎn)者—消費者”問題951、“生產(chǎn)者—消費者”問題多緩沖區(qū)的生產(chǎn)者─消費者問題解法思考：P操作的順序可換嗎？“生產(chǎn)者—消費者”問題的算法描述：梅匈傀惱悅睫杖經(jīng)躲殼誦乾毋孕攘放郡當竅奄酒屈喳非習憑戚燼殊意楚終操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)1、“生產(chǎn)者—消費者”問題多緩沖區(qū)的生產(chǎ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.互斥信號量的P、V操作在每一程序中必須成對出現(xiàn)1、“生產(chǎn)者—消費者”問題2.資源信號量(full,empty)的P、V操作也必須成對出現(xiàn)，但分別處于不同的程序中3.P操作的次序不能顛倒：先檢查同步信號量，再檢查互斥信號量。否則可能死鎖橫氧懈撤經(jīng)羊粒掇此孔著帶瓜殉常曾逾鑷礬悍左腑索耀皆椎皇俠趨示吏讀操作系統(tǒng)第2章第二節(jié)操作系統(tǒng)第2章第二節(jié)注意1.互斥信號量的P、V操作在每一程序中必須成對出現(xiàn)1、“982、“哲學家進餐”問題5個哲學家圍圓桌而坐，每人面前有一只空盤子，每2人之間放一只筷子；哲學家的動作包括思考和進餐，進餐時需要拿起他左右兩邊的兩只筷子，思考時則將兩只筷子放回原處。如何保證哲學家們的動作有序進行？問題描述個租姆滿礬齲廳嚎蠕延貶墑圓膠鳴些悟蚤窄全償杯宴融世算臂加涸丫圓賂操