操作系統(tǒng)原理第4章進(jìn)程同步與進(jìn)程通信

操作系統(tǒng)原理

OperatingSystemPrinciples四川大學(xué)計(jì)算機(jī)學(xué)院段磊leiduan@2014Spring2/5/20231《計(jì)算機(jī)操作系統(tǒng)》-第4章第4章進(jìn)程同步與進(jìn)程通信

進(jìn)程同步使得進(jìn)程之間能夠相互協(xié)作和有序使用資源。

進(jìn)程通信是進(jìn)程之間數(shù)據(jù)的相互交換和信息的相互傳遞。2/5/20232《計(jì)算機(jī)操作系統(tǒng)》-第4章本章目錄4.1進(jìn)程并發(fā)4.2臨界區(qū)管理4.3信號(hào)量機(jī)制4.4用信號(hào)量解決經(jīng)典進(jìn)程同步問(wèn)題4.5管程4.6進(jìn)程通信4.7線程的同步和通信2/5/20233《計(jì)算機(jī)操作系統(tǒng)》-第4章4.1進(jìn)程并發(fā)并發(fā)是操作系統(tǒng)的基本特征進(jìn)程并發(fā)使得程序執(zhí)行的特點(diǎn)發(fā)生了變化4.1.1程序的順序執(zhí)行程序的順序性包括程序的內(nèi)部順序性程序的外部順序性2/5/20234《計(jì)算機(jī)操作系統(tǒng)》-第4章4.1進(jìn)程并發(fā)并發(fā)是操作系統(tǒng)的基本特征進(jìn)程并發(fā)使得程序執(zhí)行的特點(diǎn)發(fā)生了變化4.1.1程序的順序執(zhí)行程序的順序性包括程序的內(nèi)部順序性程序的外部順序性2/5/20235《計(jì)算機(jī)操作系統(tǒng)》-第4章4.1.1程序的順序執(zhí)行程序的內(nèi)部順序性一個(gè)程序的操作代碼在計(jì)算機(jī)處理器上按照順序執(zhí)行，一個(gè)代碼結(jié)束后，后一個(gè)代碼才能開(kāi)始。程序的外部順序性如果一項(xiàng)任務(wù)由多個(gè)程序模塊組成，程序模塊的運(yùn)行也需要按照調(diào)用順序執(zhí)行，即程序模塊之間的順序性。2/5/20236《計(jì)算機(jī)操作系統(tǒng)》-第4章程序順序執(zhí)行具有的特點(diǎn)順序性每個(gè)操作必須在上一個(gè)操作完成后才能開(kāi)始；一個(gè)程序模塊執(zhí)行完成后另一個(gè)程序模塊才能開(kāi)始。封閉性程序運(yùn)行獨(dú)占系統(tǒng)全部資源，程序執(zhí)行的結(jié)果除初始條件外，由程序本身決定，不會(huì)受到任何其它程序和外界因素的干擾。再現(xiàn)性針對(duì)相同的數(shù)據(jù)集合，程序執(zhí)行的結(jié)果總是相同的。中斷對(duì)程序執(zhí)行的最終結(jié)果沒(méi)有影響。程序執(zhí)行的結(jié)果是可再現(xiàn)的。2/5/20237《計(jì)算機(jī)操作系統(tǒng)》-第4章程序順序執(zhí)行的不足限制了多個(gè)程序模塊的并發(fā)執(zhí)行。在多道程序并發(fā)執(zhí)行環(huán)境下，處理器的利用率低，系統(tǒng)性能差。傳統(tǒng)的程序順序執(zhí)行在多道程序環(huán)境下已不適合。2/5/20238《計(jì)算機(jī)操作系統(tǒng)》-第4章4.1.2進(jìn)程的并發(fā)性在多道程序環(huán)境下，程序是按照多個(gè)進(jìn)程并發(fā)執(zhí)行的。進(jìn)程的并發(fā)性是指一組進(jìn)程執(zhí)行在時(shí)間點(diǎn)上交替，在時(shí)間段上重疊。2/5/20239《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程的并發(fā)性進(jìn)程并發(fā)環(huán)境下，一個(gè)輸入進(jìn)程還沒(méi)有完成，另一個(gè)計(jì)算進(jìn)程已經(jīng)開(kāi)始；或者一個(gè)計(jì)算進(jìn)程還沒(méi)有完成，另一個(gè)輸出進(jìn)程已經(jīng)開(kāi)始。程序的外部順序性不再存在。并發(fā)進(jìn)程之間可能是交互的，相關(guān)的?？赡茉谕粫r(shí)間段內(nèi)，多個(gè)進(jìn)程執(zhí)行相同的軟件代碼，或多個(gè)進(jìn)程共享某些變量，或多個(gè)進(jìn)程請(qǐng)求同一硬件資源，一個(gè)進(jìn)程的執(zhí)行可能影響到其他進(jìn)程的執(zhí)行結(jié)果，并發(fā)進(jìn)程之間具有制約關(guān)系。2/5/202310《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程并發(fā)性舉例例如，兩個(gè)計(jì)數(shù)程序A、B，都為： N=N+1； print（N）； 其中，計(jì)數(shù)值N是共享變量。 如果N的初始值為0，程序A、B執(zhí)行的順序不同，產(chǎn)生的結(jié)果也不同。2/5/202311《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程并發(fā)性舉例（續(xù)）A→B程序A：N=N+1；print（N）；/*此時(shí)打印出的結(jié)果為1*/程序B：N=N+1；print（N）；/*此時(shí)打印出的結(jié)果為2*/2/5/202312《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程并發(fā)性舉例（續(xù)）B→A程序B：N=N+1；print（N）；/*此時(shí)打印出的結(jié)果為1*/程序A：N=N+1；print（N）；/*此時(shí)打印出的結(jié)果為2*/2/5/202313《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程并發(fā)性舉例（續(xù)）A→B→A→B(A、B交替進(jìn)行)程序A：N=N+1；程序B：N=N+1；程序A：print(N)；/*此時(shí)打印出的結(jié)果為2*/程序B：print(N)；/*此時(shí)打印出的結(jié)果為2*/程序運(yùn)行出現(xiàn)了不可再現(xiàn)性！2/5/202314《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程并發(fā)執(zhí)行的特點(diǎn)間斷性多個(gè)并發(fā)進(jìn)程共享處理器，執(zhí)行過(guò)程是斷斷續(xù)續(xù)的，呈現(xiàn)間斷性。制約性并發(fā)進(jìn)程存在相互制約關(guān)系，系統(tǒng)必須對(duì)運(yùn)行次序進(jìn)行協(xié)調(diào)。不可再現(xiàn)性并發(fā)進(jìn)程交替執(zhí)行，如果存在共享變量等關(guān)系，程序執(zhí)行的先后不同，會(huì)使共享變量的值不同。失去封閉性一個(gè)進(jìn)程的執(zhí)行環(huán)境與其它進(jìn)程有關(guān)，程序執(zhí)行失去了封閉性。進(jìn)程并發(fā)執(zhí)行充分利用計(jì)算機(jī)資源，提高了效率。2/5/202315《計(jì)算機(jī)操作系統(tǒng)》-第4章4.1.3進(jìn)程間的競(jìng)爭(zhēng)和協(xié)作并發(fā)執(zhí)行的進(jìn)程以各自的速度向前推進(jìn)，相互之間構(gòu)成了相互競(jìng)爭(zhēng)資源和相互協(xié)作的關(guān)系。1．進(jìn)程間的競(jìng)爭(zhēng)多道程序并發(fā)執(zhí)行環(huán)境下，進(jìn)程的執(zhí)行失去了封閉性。并發(fā)進(jìn)程相互共處在一個(gè)系統(tǒng)中，一個(gè)進(jìn)程的執(zhí)行必然會(huì)影響到其他進(jìn)程。2/5/202316《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程間的競(jìng)爭(zhēng)共享的資源分為：互斥共享資源：只有一個(gè)進(jìn)程對(duì)資源訪問(wèn)，訪問(wèn)結(jié)束并釋放后，另外的進(jìn)程才能訪問(wèn)該資源。同時(shí)共享資源：多個(gè)進(jìn)程可并發(fā)訪問(wèn)，不需要一個(gè)進(jìn)程訪問(wèn)結(jié)束，其他的進(jìn)程就可訪問(wèn)的資源。進(jìn)程對(duì)互斥共享資源的競(jìng)爭(zhēng)要求OS對(duì)進(jìn)程操作采取同步措施，從時(shí)間上和順序上加以限制，使得進(jìn)程之間相互制約地使用這些資源，保證資源的完整性。2/5/202317《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程間的協(xié)作由于每個(gè)進(jìn)程都以獨(dú)立地不可知的速度向前推進(jìn)，需要具有協(xié)作關(guān)系的進(jìn)程需要在某些協(xié)調(diào)點(diǎn)上相互協(xié)調(diào)、相互等待，使得雙方都能夠順利地運(yùn)行直至完成。協(xié)作的進(jìn)程之間存在數(shù)據(jù)或變量等的共享關(guān)系，進(jìn)程的推進(jìn)順序受到一定的限制，進(jìn)程推進(jìn)需要按照特定的順序進(jìn)行，否則會(huì)發(fā)生進(jìn)程執(zhí)行結(jié)果的不可再現(xiàn)與不確定的情況。2/5/202318《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程間的協(xié)作在并發(fā)進(jìn)程之間存在相互協(xié)作關(guān)系時(shí)，系統(tǒng)需要采取同步措施，確保進(jìn)程以合理的順序推進(jìn)，確保進(jìn)程運(yùn)行的可再現(xiàn)性和結(jié)果的確定性。并發(fā)進(jìn)程之間的互斥共享資源關(guān)系最終也是進(jìn)程之間的一種協(xié)作關(guān)系，即并發(fā)進(jìn)程協(xié)作共享資源，也是進(jìn)程同步關(guān)系。2/5/202319《計(jì)算機(jī)操作系統(tǒng)》-第4章4.1.4進(jìn)程同步生產(chǎn)者和消費(fèi)者問(wèn)題并發(fā)進(jìn)程的共享資源問(wèn)題并發(fā)進(jìn)程之間的協(xié)作問(wèn)題2/5/202320《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者與消費(fèi)者問(wèn)題問(wèn)題描述一個(gè)有限空間的共享緩沖區(qū)，負(fù)責(zé)存放貨物生產(chǎn)者向緩沖區(qū)中放物品，緩沖區(qū)滿則不能放消費(fèi)者從緩沖區(qū)中拿物品，緩沖區(qū)空則不能拿生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程（如何體現(xiàn)進(jìn)程的同步）2/5/202321《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者與消費(fèi)者問(wèn)題緩沖池：數(shù)組表示，具有n個(gè)(0，1，…，n-1)緩沖區(qū)輸入指針in：指示下一個(gè)可投放產(chǎn)品的緩沖區(qū)輸出指針out：指示下一個(gè)可從中獲取產(chǎn)品的緩沖區(qū)緩沖池采用循環(huán)組織，故：輸入指針加1表示成in:=(in+1)modn；輸出指針加1表示成out:=(out+1)modn。當(dāng)(in+1)modn=out時(shí)表示緩沖池滿；而in=out則表示緩沖池空。整型變量counter：生產(chǎn)者進(jìn)程投放產(chǎn)品使counter加1；消費(fèi)者進(jìn)程取走產(chǎn)品使counter減1。Varn，integer；typeitem=…；varbuffer:array［0，1，…，n-1］ofitem；in，out:0，1，…，n-1；counter:0，1，…，n；2/5/202322《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者與消費(fèi)者問(wèn)題生產(chǎn)者進(jìn)程producer:repeat

produceaniteminnextp；

whilecounter=ndono-op；

buffer［in］:=nextp；

in:=in+1modn；

counter:=counter+1；untilfalse；消費(fèi)者進(jìn)程

consumer:repeat

whilecounter=0dono-op；nextc:=buffer［out］；out:=(out+1)modn；counter:=counter-1；consumertheiteminnextc；

untilfalse；2/5/202323《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者、消費(fèi)者進(jìn)程分析生產(chǎn)者進(jìn)程→消費(fèi)者進(jìn)程不存在資源的競(jìng)爭(zhēng)，不會(huì)出現(xiàn)問(wèn)題。生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程并發(fā)運(yùn)行生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程對(duì)緩沖區(qū)競(jìng)爭(zhēng)使用出現(xiàn)生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程之間不能協(xié)作的問(wèn)題。當(dāng)緩沖區(qū)中已經(jīng)裝滿產(chǎn)品時(shí)，生產(chǎn)者進(jìn)程得到緩沖區(qū)的訪問(wèn)權(quán)，生產(chǎn)者進(jìn)程無(wú)法進(jìn)行生產(chǎn)。生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程都需要對(duì)變量counter進(jìn)行訪問(wèn)，對(duì)共享變量的訪問(wèn)可能造成數(shù)據(jù)不一致。2/5/202324《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者與消費(fèi)者問(wèn)題問(wèn)題的出現(xiàn)兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對(duì)它做加1操作，消費(fèi)者對(duì)它做減1操作，這兩個(gè)操作在用機(jī)器語(yǔ)言實(shí)現(xiàn)時(shí)，?？捎孟旅娴男问矫枋觯海▎?wèn)題何在？）register1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1；counter:=register2；2/5/202325《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者與消費(fèi)者問(wèn)題register1:=counter；register2:=counter；register1:=register1+1；register2:=register2-1；counter:=register1；counter:=register2；

register1:=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)

程序的執(zhí)行已經(jīng)失去了再現(xiàn)性。為了預(yù)防產(chǎn)生這種錯(cuò)誤，解決此問(wèn)題的關(guān)鍵是應(yīng)把變量counter作為臨界資源處理，亦即，令生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程互斥地訪問(wèn)變量counter。2/5/202326《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者與消費(fèi)者問(wèn)題A1→B1→A2→B2→A3→B3經(jīng)過(guò)寄存器register1得到的count值為11，經(jīng)過(guò)寄存器register2得到的count值為9，最后count的值為9。A1→A2→A3→B1→B2→B3經(jīng)過(guò)寄存器register1得到的count值為11，經(jīng)過(guò)寄存器register2得到的count值為10，最后count的值為10。A1→B1→A2→B2→B3→A3count的值為11。在進(jìn)程并發(fā)環(huán)境下，競(jìng)爭(zhēng)使用的資源和共享訪問(wèn)的變量，如果在程序中不采取同步措施，實(shí)現(xiàn)互斥訪問(wèn)和有序訪問(wèn)，則會(huì)出現(xiàn)數(shù)據(jù)不一致等問(wèn)題。A1:register1:=counter；

B1:register2:=counter；A2:register1:=register1+1；

B2:register2:=register2-1；A3:counter:=register1；

B3:counter:=register2；

2/5/202327《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者與消費(fèi)者問(wèn)題A1→B1→A2→B2→A3→B3經(jīng)過(guò)寄存器register1得到的count值為11，經(jīng)過(guò)寄存器register2得到的count值為9，最后count的值為9。A1→A2→A3→B1→B2→B3經(jīng)過(guò)寄存器register1得到的count值為11，經(jīng)過(guò)寄存器register2得到的count值為10，最后count的值為10。A1→B1→A2→B2→B3→A3count的值為11。在進(jìn)程并發(fā)環(huán)境下，競(jìng)爭(zhēng)使用的資源和共享訪問(wèn)的變量，如果在程序中不采取同步措施，實(shí)現(xiàn)互斥訪問(wèn)和有序訪問(wèn)，則會(huì)出現(xiàn)數(shù)據(jù)不一致等問(wèn)題。2/5/202328《計(jì)算機(jī)操作系統(tǒng)》-第4章本章目錄4.1進(jìn)程并發(fā)4.2臨界區(qū)管理4.3信號(hào)量機(jī)制4.4用信號(hào)量解決經(jīng)典進(jìn)程同步問(wèn)題4.5管程4.6進(jìn)程通信4.7線程的同步和通信2/5/202329《計(jì)算機(jī)操作系統(tǒng)》-第4章再次說(shuō)明：程序的制約方式間接制約方式由于競(jìng)爭(zhēng)相同資源而引起的，得到資源的程序段可以投入運(yùn)行，而得不到資源的程序段就是暫時(shí)等待，直至獲得可用資源時(shí)再繼續(xù)運(yùn)行。直接制約方式通常在那些邏輯上相關(guān)的程序段之間發(fā)生的，一般是由于各種程序段要求共享信息引起的。2/5/202330《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步基本概念制約關(guān)系的兩種形式臨界資源臨界區(qū)信號(hào)量機(jī)制整型、記錄型、AND型、信號(hào)量集信號(hào)量的應(yīng)用實(shí)現(xiàn)進(jìn)程互斥實(shí)現(xiàn)前趨關(guān)系2/5/202331《計(jì)算機(jī)操作系統(tǒng)》-第4章進(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)2/5/202332《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程的互斥（間接作用）mutualexclusion由于各進(jìn)程要求共享資源，而有些資源需要互斥使用，因此各進(jìn)程間競(jìng)爭(zhēng)使用這些資源，進(jìn)程的這種關(guān)系為進(jìn)程的互斥臨界資源：criticalresource系統(tǒng)中某些資源一次只允許一個(gè)進(jìn)程使用，稱這樣的資源為臨界資源或互斥資源或共享變量2/5/202333《計(jì)算機(jī)操作系統(tǒng)》-第4章“司機(jī)－售票員”問(wèn)題（同步）司機(jī)進(jìn)程While(True){啟動(dòng)公車；駕駛公車；停止公車；}售票員進(jìn)程While(True){關(guān)車門(mén)；賣車票；開(kāi)車門(mén)；}正確運(yùn)行過(guò)程While(True){（售票員）關(guān)車門(mén)（司機(jī)）啟動(dòng)公車；（司機(jī)）駕駛公車；（售票員）賣車票（司機(jī)）停止公車；（售票員）開(kāi)車門(mén)；}2/5/202334《計(jì)算機(jī)操作系統(tǒng)》-第4章Spooler目錄問(wèn)題（互斥）Out：4In：7進(jìn)程A：N_f_s=In;

//In==7

InsertFileIntoSpooler(N_f_s); In=N_f_s++;

//In==8

進(jìn)程B：N_f_s=In;

//In==8

InsertFileIntoSpooler(N_f_s); In=N_f_s++;

//In==9

4：File15：File26：File37：Null8：Null………Spooler目錄………進(jìn)程切換，一切正常2/5/202335《計(jì)算機(jī)操作系統(tǒng)》-第4章Spooler目錄問(wèn)題（互斥）Out：4In：7進(jìn)程A： N_f_s=In;

//In==7

進(jìn)程B： N_f_s=In;

//In==7

InsertFileIntoSpooler(N_f_s); In=N_f_s++;

//In==8

4：File15：File26：File37：Null8：Null………Spooler目錄………進(jìn)程切換進(jìn)程A： InsertFileIntoSpooler(N_f_s); In=N_f_s++;

//In==8

進(jìn)程切換，進(jìn)程B數(shù)據(jù)丟失2/5/202336《計(jì)算機(jī)操作系統(tǒng)》-第4章4.2.1臨界資源和臨界區(qū)互斥共享的資源稱為臨界資源。在生產(chǎn)者和消費(fèi)者進(jìn)程中，緩沖區(qū)和變量count都是臨界資源。在程序中對(duì)臨界資源訪問(wèn)的代碼部分稱為臨界區(qū)。進(jìn)程訪問(wèn)臨界資源前都要判斷該資源能否訪問(wèn)，如果能訪問(wèn)，進(jìn)入到臨界區(qū)訪問(wèn)臨界資源；如果不能訪問(wèn)，則需要等待，直到該資源能夠訪問(wèn)；訪問(wèn)結(jié)束后，需要將資源歸還，使其他進(jìn)程能夠知道臨界資源已經(jīng)被當(dāng)前進(jìn)程訪問(wèn)結(jié)束。2/5/202337《計(jì)算機(jī)操作系統(tǒng)》-第4章臨界資源和臨界區(qū)步驟臨界資源與臨界區(qū) While(1){ …… entry_section; //申請(qǐng)進(jìn)入 critical_section; //臨界區(qū) exit_section; //聲明退出 ……… }2/5/202338《計(jì)算機(jī)操作系統(tǒng)》-第4章4.2.2進(jìn)程同步準(zhǔn)則空閑讓進(jìn)：當(dāng)無(wú)進(jìn)程在互斥區(qū)時(shí)，任何有權(quán)使用互斥區(qū)的進(jìn)程可進(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)程有機(jī)會(huì)得到CPU的使用權(quán)2/5/202339《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步準(zhǔn)則程序設(shè)計(jì)時(shí)，進(jìn)入?yún)^(qū)是判別能否訪問(wèn)臨界資源的關(guān)鍵。如果進(jìn)程能訪問(wèn)臨界資源，則通過(guò)進(jìn)入?yún)^(qū)，進(jìn)入臨界區(qū)訪問(wèn)臨界資源；否則，進(jìn)程不能進(jìn)入臨界區(qū)訪問(wèn)臨界資源；當(dāng)進(jìn)程訪問(wèn)臨界資源完后，通過(guò)退出區(qū)，釋放臨界資源。2/5/202340《計(jì)算機(jī)操作系統(tǒng)》-第4章4.2.3早期的臨界區(qū)管理方法1．軟件方法軟件方法在共享內(nèi)存的單處理機(jī)或多處理機(jī)系統(tǒng)中實(shí)現(xiàn)進(jìn)程的并發(fā)。軟件方法假定基于內(nèi)存訪問(wèn)級(jí)別的一些基本互斥，對(duì)內(nèi)存同一位置的同時(shí)訪問(wèn)將被排序，而訪問(wèn)的順序并不事先指定。不需要硬件或操作系統(tǒng)或程序設(shè)計(jì)語(yǔ)言的任何支持。2/5/202341《計(jì)算機(jī)操作系統(tǒng)》-第4章早期的臨界區(qū)管理方法–軟件方法算法1：臨界區(qū)標(biāo)志法為了實(shí)現(xiàn)臨界區(qū)的管理，采用標(biāo)志來(lái)表示哪個(gè)并發(fā)進(jìn)程可以進(jìn)入臨界區(qū)訪問(wèn)。確保每次只有一個(gè)進(jìn)程進(jìn)入臨界區(qū)，但強(qiáng)制兩個(gè)進(jìn)程輪流進(jìn)入臨界區(qū)。違背進(jìn)程同步機(jī)制中“空閑讓進(jìn)”原則算法2：先判斷對(duì)方進(jìn)程標(biāo)志的進(jìn)程數(shù)組標(biāo)志法進(jìn)程每次訪問(wèn)臨界資源前，首先查看其他進(jìn)程訪問(wèn)臨界資源的標(biāo)志。如果其他進(jìn)程標(biāo)志處于正在訪問(wèn)，則進(jìn)程等待。違背了“忙則等待”的同步準(zhǔn)則2/5/202342《計(jì)算機(jī)操作系統(tǒng)》-第4章早期的臨界區(qū)管理方法–軟件方法算法3：先設(shè)置自己標(biāo)志的進(jìn)程數(shù)組標(biāo)志法違背了“空閑讓進(jìn)”的同步準(zhǔn)則算法4：雙標(biāo)志法標(biāo)志flag用于表示每個(gè)進(jìn)程是否訪問(wèn)臨界資源，標(biāo)志turn用于表示臨界資源此時(shí)是否有對(duì)方進(jìn)程在訪問(wèn)。應(yīng)用性非常方便的進(jìn)程同步算法在臨界區(qū)訪問(wèn)標(biāo)志算法中，出現(xiàn)了違背“忙則等待”或“空閑讓進(jìn)”準(zhǔn)則的根本原因在于管理臨界區(qū)標(biāo)志要用兩條指令，一條指令是看對(duì)方的標(biāo)志，一條指令是設(shè)置自己的標(biāo)志。

2/5/202343《計(jì)算機(jī)操作系統(tǒng)》-第4章早期的臨界區(qū)管理方法–硬件方法2．硬件方法要保證進(jìn)程在執(zhí)行這兩條指令時(shí)不被中斷，可以采取鎖的方式。如果臨界區(qū)沒(méi)有被訪問(wèn)，則鎖是打開(kāi)的，在進(jìn)程訪問(wèn)臨界區(qū)時(shí)，只要進(jìn)程一進(jìn)入臨界區(qū)，則系統(tǒng)立即上鎖，直到訪問(wèn)臨界區(qū)的進(jìn)程離開(kāi)臨界區(qū)才打開(kāi)鎖。測(cè)試鎖和上鎖這兩個(gè)操作不能分開(kāi)，否則會(huì)造成多個(gè)進(jìn)程測(cè)試到鎖打開(kāi)而同時(shí)上鎖的現(xiàn)象，引起沖突。進(jìn)程在執(zhí)行這兩個(gè)操作期間在處理器上的運(yùn)行不能被中斷。軟件方法來(lái)解決有一定局限性和難度，現(xiàn)一般借助于硬件設(shè)施。2/5/202344《計(jì)算機(jī)操作系統(tǒng)》-第4章早期的臨界區(qū)管理方法–硬件方法優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單：只需要硬件指令就可實(shí)現(xiàn)。適用性強(qiáng)：可用于多并發(fā)進(jìn)程單CPU系統(tǒng)或共享內(nèi)存多CPU系統(tǒng)。支持多個(gè)臨界區(qū)：每個(gè)臨界區(qū)用單獨(dú)的變量定義，對(duì)臨界區(qū)的多少?zèng)]有限制，可支持多個(gè)臨界區(qū)。缺點(diǎn)：耗費(fèi)處理器時(shí)間：采用忙等待，處理器空閑時(shí)間增多。進(jìn)程產(chǎn)生饑餓現(xiàn)象：一個(gè)進(jìn)程離開(kāi)臨界區(qū)并喚醒阻塞等待的其它進(jìn)程，可能阻塞更早的進(jìn)程長(zhǎng)期得不到喚醒，產(chǎn)生饑餓現(xiàn)象?？赡墚a(chǎn)生死鎖：在單處理器系統(tǒng)中，進(jìn)程執(zhí)行特殊指令并進(jìn)入臨界區(qū)，擁有更高優(yōu)先級(jí)的進(jìn)程搶占，但得不到?jīng)]有釋放的臨界資源，于是這兩個(gè)進(jìn)程發(fā)生死鎖。2/5/202345《計(jì)算機(jī)操作系統(tǒng)》-第4章早期的臨界區(qū)管理方法–硬件方法（1）禁止中斷方法最簡(jiǎn)單的方法影響計(jì)算機(jī)效率不能及時(shí)處理重要程序在多處理器下方法失效（2）測(cè)試并建立指令（3）對(duì)換指令2/5/202346《計(jì)算機(jī)操作系統(tǒng)》-第4章本章目錄4.1進(jìn)程并發(fā)4.2臨界區(qū)管理4.3信號(hào)量機(jī)制4.4用信號(hào)量解決經(jīng)典進(jìn)程同步問(wèn)題4.5管程4.6進(jìn)程通信4.7線程的同步和通信重點(diǎn)與難點(diǎn)2/5/202347《計(jì)算機(jī)操作系統(tǒng)》-第4章信號(hào)量機(jī)制信號(hào)量（semaphore）機(jī)制解決并發(fā)進(jìn)程同步的工具在信號(hào)量同步機(jī)制中，有“檢測(cè)”和“歸還”兩個(gè)重要的操作荷蘭語(yǔ)“Proberen”的意思為“檢測(cè)”，用P操作表示；荷蘭語(yǔ)“Verhogen”的意思為“增量”，用V操作表示?！霸隽俊奔丛黾右粋€(gè)可以使用的臨界資源，也就是“歸還”的意思。2/5/202348《計(jì)算機(jī)操作系統(tǒng)》-第4章信號(hào)量機(jī)制P操作表示同步進(jìn)程發(fā)出的檢測(cè)信號(hào)量操作，檢測(cè)是否能夠使用臨界資源如果能使用，則檢測(cè)通過(guò)，進(jìn)程可以訪問(wèn)臨界資源；如果不能使用，則等待，直到訪問(wèn)臨界區(qū)的進(jìn)程將臨界資源歸還后，等待的進(jìn)程才能夠訪問(wèn)臨界資源。V操作表示訪問(wèn)完臨界資源的進(jìn)程通知等待進(jìn)程已經(jīng)完成了臨界資源的訪問(wèn)，將臨界資源釋放。2/5/202349《計(jì)算機(jī)操作系統(tǒng)》-第4章信號(hào)量機(jī)制信號(hào)量機(jī)制強(qiáng)調(diào)P操作和V操作都是原子操作。原子操作是不可分割的操作，原語(yǔ)。即通常所說(shuō)的“要么做，要么不做”，而不可能操作沒(méi)有完成就被終止。2/5/202350《計(jì)算機(jī)操作系統(tǒng)》-第4章4.3.1整型信號(hào)量整型信號(hào)量設(shè)S為一個(gè)需要初始化值的正整型量。對(duì)S的訪問(wèn)只能通過(guò)P、V操作。P操作 wait（S）：whileS≤0dono-opS:＝S－1;V操作 signal（S）：S:＝S＋1;2/5/202351《計(jì)算機(jī)操作系統(tǒng)》-第4章整型信號(hào)量S>0，表示臨界資源可以訪問(wèn)，P(s)中的檢測(cè)語(yǔ)句通過(guò)，調(diào)用P(s)的進(jìn)程可以訪問(wèn)臨界資源。S≤0，表示有進(jìn)程在訪問(wèn)臨界資源，此時(shí)臨界資源處于忙，調(diào)用P(s)的進(jìn)程只能等待，直到s的值大于0，才可以訪問(wèn)臨界資源。2/5/202352《計(jì)算機(jī)操作系統(tǒng)》-第4章整型信號(hào)量的應(yīng)用－實(shí)現(xiàn)進(jìn)程互斥例4-3輸入進(jìn)程和計(jì)算進(jìn)程共用緩沖區(qū)，如圖所示。輸入進(jìn)程I和計(jì)算進(jìn)程P并發(fā)執(zhí)行，緩沖區(qū)是競(jìng)爭(zhēng)訪問(wèn)的臨界資源，緩沖區(qū)的大小為n。用整型信號(hào)量實(shí)現(xiàn)進(jìn)程同步。公共緩沖區(qū)PI為緩沖區(qū)設(shè)置整型信號(hào)量mutex;設(shè)mutex的初值為1將各進(jìn)程對(duì)臨界區(qū)訪問(wèn)置于P(mutex)和V(mutex)之間2/5/202353《計(jì)算機(jī)操作系統(tǒng)》-第4章整型信號(hào)量的應(yīng)用－實(shí)現(xiàn)進(jìn)程互斥Pi: /*輸入進(jìn)程*/beginwhile(輸入未完成){…P(mutex);/*如果緩沖區(qū)裝滿，則等待*/

將一批輸入數(shù)據(jù)放入緩沖區(qū);V(mutex);}end;Pc： /*計(jì)算進(jìn)程*/beginwhile(計(jì)算未完成){P(mutex);/*如果緩沖區(qū)為空，則等待*/從緩沖區(qū)中拿出一批數(shù)據(jù);V(mutex);計(jì)算;…}end;coend;2/5/202354《計(jì)算機(jī)操作系統(tǒng)》-第4章整型信號(hào)量的應(yīng)用－實(shí)現(xiàn)進(jìn)程互斥例4-3分析：對(duì)于輸入進(jìn)程：只要緩沖區(qū)沒(méi)有裝滿，進(jìn)程就能將數(shù)據(jù)輸入到緩沖區(qū)中。緩沖區(qū)是否裝滿：需要用P(mutex)去檢測(cè)，如果P(mutex)檢測(cè)通過(guò)，則進(jìn)程能夠訪問(wèn)緩沖區(qū)。訪問(wèn)完后用V(mutex)釋放緩沖區(qū)；如果P(mutex)檢測(cè)不能通過(guò)，則進(jìn)程等待。2/5/202355《計(jì)算機(jī)操作系統(tǒng)》-第4章整型信號(hào)量的應(yīng)用－實(shí)現(xiàn)進(jìn)程互斥例4-3分析：對(duì)于輸入進(jìn)程：只要緩沖區(qū)沒(méi)有裝滿，進(jìn)程就能將數(shù)據(jù)輸入到緩沖區(qū)中。緩沖區(qū)是否裝滿：需要用P(mutex)去檢測(cè)，如果P(mutex)檢測(cè)通過(guò)，則進(jìn)程能夠訪問(wèn)緩沖區(qū)。訪問(wèn)完后用V(mutex)釋放緩沖區(qū)；如果P(mutex)檢測(cè)不能通過(guò)，則進(jìn)程等待。對(duì)于計(jì)算進(jìn)程：只要緩沖區(qū)不為空，則進(jìn)程能夠從緩沖區(qū)中取走數(shù)據(jù)。緩沖區(qū)是否為空，需要用P(mutex)去檢測(cè)，如果P(mutex)檢測(cè)通過(guò)，進(jìn)程能夠訪問(wèn)緩沖區(qū)。訪問(wèn)完后用V(mutex)釋放緩沖區(qū)；如果P(mutex)檢測(cè)不能通過(guò)，則進(jìn)程等待。2/5/202356《計(jì)算機(jī)操作系統(tǒng)》-第4章整型信號(hào)量的應(yīng)用－實(shí)現(xiàn)進(jìn)程互斥例4-3分析：對(duì)于輸入進(jìn)程：只要緩沖區(qū)沒(méi)有裝滿，進(jìn)程就能將數(shù)據(jù)輸入到緩沖區(qū)中。緩沖區(qū)是否裝滿：需要用P(mutex)去檢測(cè)，如果P(mutex)檢測(cè)通過(guò)，則進(jìn)程能夠訪問(wèn)緩沖區(qū)。訪問(wèn)完后用V(mutex)釋放緩沖區(qū)；如果P(mutex)檢測(cè)不能通過(guò)，則進(jìn)程等待。對(duì)于計(jì)算進(jìn)程：只要緩沖區(qū)不為空，則進(jìn)程能夠從緩沖區(qū)中取走數(shù)據(jù)。緩沖區(qū)是否為空，需要用P(mutex)去檢測(cè)，如果P(mutex)檢測(cè)通過(guò)，進(jìn)程能夠訪問(wèn)緩沖區(qū)。訪問(wèn)完后用V(mutex)釋放緩沖區(qū)；如果P(mutex)檢測(cè)不能通過(guò)，則進(jìn)程等待。對(duì)于輸入進(jìn)程和計(jì)算進(jìn)程：如果兩個(gè)進(jìn)程都能夠訪問(wèn)緩沖區(qū)，哪個(gè)進(jìn)程先訪問(wèn)緩沖區(qū)，關(guān)鍵在于哪個(gè)進(jìn)程先執(zhí)行P(mutex)。先執(zhí)行的進(jìn)程先進(jìn)入緩沖區(qū)訪問(wèn)；后執(zhí)行P(mutex)的進(jìn)程等待，直到先進(jìn)入緩沖區(qū)訪問(wèn)的進(jìn)程用V(mutex)釋放緩沖區(qū)為止。2/5/202357《計(jì)算機(jī)操作系統(tǒng)》-第4章整型信號(hào)量的應(yīng)用－實(shí)現(xiàn)進(jìn)程同步例4-3

在例4-3的基礎(chǔ)上，當(dāng)輸入進(jìn)程和計(jì)算進(jìn)程之間共用的緩沖區(qū)中只能裝入一條數(shù)據(jù)時(shí)，用整型信號(hào)量實(shí)現(xiàn)輸入進(jìn)程和計(jì)算進(jìn)程的同步。公共緩沖區(qū)PI當(dāng)緩沖區(qū)中只能裝入一條數(shù)據(jù)時(shí)，輸入進(jìn)程每次放入一條數(shù)據(jù)后，要等待計(jì)算進(jìn)程取走數(shù)據(jù)才能再放入下一條數(shù)據(jù)。設(shè)置兩個(gè)整型信號(hào)量is和ps用于輸入進(jìn)程和計(jì)算進(jìn)程協(xié)調(diào)訪問(wèn)緩沖區(qū)初值分別設(shè)置為1和02/5/202358《計(jì)算機(jī)操作系統(tǒng)》-第4章Pi: /*輸入進(jìn)程*/

beginwhile(輸入未完成){…P(is);將一批輸入數(shù)據(jù)放入緩沖區(qū);V(ps);}end;Pc： /*計(jì)算進(jìn)程*/beginwhile(計(jì)算未完成){P(ps);從緩沖區(qū)中拿出一批數(shù)據(jù);V(is);計(jì)算;…}end;coend;整型信號(hào)量的應(yīng)用－實(shí)現(xiàn)進(jìn)程同步2/5/202359《計(jì)算機(jī)操作系統(tǒng)》-第4章整型信號(hào)量的應(yīng)用－實(shí)現(xiàn)進(jìn)程同步例4-4分析：信號(hào)量的設(shè)置是關(guān)鍵：將信號(hào)量is的初值設(shè)置為1，ps的初值設(shè)置為0?？偸禽斎脒M(jìn)程先進(jìn)入緩沖區(qū)放入數(shù)據(jù)，計(jì)算進(jìn)程先等待。輸入進(jìn)程將一條數(shù)據(jù)放入緩沖區(qū)后釋放ps，計(jì)算進(jìn)程才能進(jìn)入緩沖區(qū)取走一條數(shù)據(jù)。對(duì)于輸入進(jìn)程：如果計(jì)算進(jìn)程沒(méi)有進(jìn)入緩沖區(qū)取走一條數(shù)據(jù)，輸入進(jìn)程不能再進(jìn)入緩沖區(qū)放數(shù)據(jù)，因?yàn)檩斎脒M(jìn)程需要計(jì)算進(jìn)程釋放緩沖區(qū)is。對(duì)于計(jì)算進(jìn)程：如果沒(méi)有輸入進(jìn)程釋放緩沖區(qū)ps，計(jì)算進(jìn)程不能多次連續(xù)進(jìn)入緩沖區(qū)取走數(shù)據(jù)。2/5/202360《計(jì)算機(jī)操作系統(tǒng)》-第4章整型信號(hào)量的應(yīng)用－實(shí)現(xiàn)進(jìn)程前趨圖a,b,c,d,e,f,g:semaphore:=0,…,0beginS1;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;S1S2S4S3S5S6S1S2S4S3S5S62/5/202361《計(jì)算機(jī)操作系統(tǒng)》-第4章4.3.2記錄型信號(hào)量在整型信號(hào)量中，P操作開(kāi)始需要測(cè)試臨界資源是否能夠訪問(wèn)，即判斷s≤0是否滿足。如果滿足，表示進(jìn)程不能進(jìn)入臨界區(qū)訪問(wèn)，進(jìn)程此時(shí)“donothing”，即什么都不做而等待。這時(shí)的等待沒(méi)有放棄CPU執(zhí)行權(quán)。這違背了“讓權(quán)等待”的同步準(zhǔn)則，造成處理器資源的浪費(fèi)。2/5/202362《計(jì)算機(jī)操作系統(tǒng)》-第4章記錄型信號(hào)量解決忙等問(wèn)題，實(shí)現(xiàn)讓權(quán)等待記錄所有等待同一資源的進(jìn)程

P操作wait（S）：

S.value＝S.value－1 ifS.value<0thenblock（S,L）

V操作

S.value＝S.value＋1 ifS.value≤0thenwakeup（S,L）2/5/202363《計(jì)算機(jī)操作系統(tǒng)》-第4章記錄型信號(hào)量理解：記錄型信號(hào)量在整型信號(hào)量的基礎(chǔ)上進(jìn)行了改進(jìn)，讓不能進(jìn)入臨界區(qū)的進(jìn)程“讓權(quán)等待”，即進(jìn)程狀態(tài)由運(yùn)行轉(zhuǎn)換為阻塞狀態(tài)，進(jìn)程進(jìn)入阻塞隊(duì)列中等待。若信號(hào)量s的s.value的值為正數(shù)，該正數(shù)表示可對(duì)信號(hào)量可進(jìn)行的P操作的次數(shù)，即實(shí)際可以使用的臨界資源數(shù)。若信號(hào)量s的s.value的值為負(fù)值，表示有多個(gè)進(jìn)程申請(qǐng)臨界資源，而又不能得到，在阻塞隊(duì)列等待。s.value的絕對(duì)值表示在阻塞隊(duì)列等待臨界資源的進(jìn)程個(gè)數(shù)。2/5/202364《計(jì)算機(jī)操作系統(tǒng)》-第4章4.3.3

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ǔ)為Ssignal2/5/202365《計(jì)算機(jī)操作系統(tǒng)》-第4章AND型信號(hào)量理解：死鎖的產(chǎn)生？死鎖的預(yù)防與解決？解決的辦法是將進(jìn)程所需要的資源一次性地全部分配給進(jìn)程，等進(jìn)程運(yùn)行完后再全部一起釋放。先讓一個(gè)進(jìn)程完成后，另一個(gè)進(jìn)程才申請(qǐng)資源，得到資源并完成。也就是將并發(fā)的進(jìn)程分為先完成進(jìn)程和后完成進(jìn)程。AND型信號(hào)量集是將進(jìn)程在運(yùn)行中所需要的臨界資源全部一次性分配給進(jìn)程，等進(jìn)程用完后再全部一起釋放。如果進(jìn)程有一個(gè)臨界資源沒(méi)有得到，進(jìn)程也不可能推進(jìn)，必須將所分配到的臨界資源全部歸還。即要么全部得到向前推進(jìn)，要么一個(gè)也不能要而等待。這樣的資源分配策略可以避免死鎖。2/5/202366《計(jì)算機(jī)操作系統(tǒng)》-第4章4.3.4信號(hào)量集當(dāng)進(jìn)程需要申請(qǐng)的臨界資源種類較多，每類臨界資源個(gè)數(shù)較多時(shí)，如果用記錄型信號(hào)量，進(jìn)程每次只能一次申請(qǐng)或釋放一個(gè)臨界資源，非常麻煩。因此，引入信號(hào)量集。2/5/202367《計(jì)算機(jī)操作系統(tǒng)》-第4章信號(hào)量機(jī)制整型信號(hào)量基本信號(hào)量原理記錄型信號(hào)量多個(gè)進(jìn)程申請(qǐng)同一類資源AND型信號(hào)量同一進(jìn)程申請(qǐng)多個(gè)不同資源信號(hào)量集同一進(jìn)程申請(qǐng)多個(gè)同類資源多個(gè)進(jìn)程申請(qǐng)多個(gè)不同資源信號(hào)量機(jī)制的對(duì)比2/5/202368《計(jì)算機(jī)操作系統(tǒng)》-第4章2信號(hào)量機(jī)制信號(hào)量按聯(lián)系進(jìn)程的關(guān)系分成二類：公用信號(hào)量（互斥信號(hào)量）私用信號(hào)量（同步信號(hào)量）

它為一組需互斥共享臨界資源的并發(fā)進(jìn)程而設(shè)置，代表共享的臨界資源，每個(gè)進(jìn)程均可對(duì)它施加P、V操作，即都可申請(qǐng)和釋放該臨界資源，其初始值置為1。取值意義如下：信號(hào)量s＝1；表示資源空閑，可供使用。信號(hào)量s＝0；表示資源已被占用，無(wú)其它進(jìn)程等待。信號(hào)量s＝-n；表示資源已被占用，還有n個(gè)進(jìn)程因等待資源而阻塞。它為一組需同步協(xié)作完成任務(wù)的并發(fā)進(jìn)程而設(shè)置，只有擁有該資源的進(jìn)程才能對(duì)它施加P操作（即可申請(qǐng)資源），而由其合作進(jìn)程對(duì)它施加V操作（即釋放資源）。2/5/202369《計(jì)算機(jī)操作系統(tǒng)》-第4章例題補(bǔ)充與講解：1知識(shí)點(diǎn)：進(jìn)程的前趨圖題目：已知一個(gè)求值公式如下所示，如果A、B已賦值，請(qǐng)畫(huà)出該公式求值過(guò)程的前趨圖思路：分辨可以并發(fā)進(jìn)行的運(yùn)算保存計(jì)算的中間結(jié)果，并為每條語(yǔ)句命名2/5/202370《計(jì)算機(jī)操作系統(tǒng)》-第4章例題補(bǔ)充與講解：12/5/202371《計(jì)算機(jī)操作系統(tǒng)》-第4章例題補(bǔ)充與講解：2知識(shí)點(diǎn)：信號(hào)量的應(yīng)用題目：設(shè)有一個(gè)作業(yè)由四個(gè)進(jìn)程組成，這四個(gè)進(jìn)程必須按右圖的次序運(yùn)行，試用P、V操作表達(dá)四個(gè)進(jìn)程的同步關(guān)系。思路：設(shè)三個(gè)同步信號(hào)量b1、b2、b3，分別表示進(jìn)程T2、T3、T4是否可以開(kāi)始執(zhí)行，初值為0。2/5/202372《計(jì)算機(jī)操作系統(tǒng)》-第4章例題補(bǔ)充與講解：2b2,b3,b4:semaphore:=0,0,0T1:{...V(b2);V(b3);}T2:{P(b2);...V(b4);}T3:{P(b3);...V(b4);}T4:{P(b4);P(b4);...}（因在T2和T3中都對(duì)b4做了V操作，所以T4要用兩個(gè)P操作）2/5/202373《計(jì)算機(jī)操作系統(tǒng)》-第4章例題補(bǔ)充與講解：3知識(shí)點(diǎn)：信號(hào)量的應(yīng)用題目：設(shè)有兩個(gè)優(yōu)先級(jí)相同的進(jìn)程P1和P2如下，信號(hào)量S1和S2的初值為0。請(qǐng)問(wèn)P1、P2并發(fā)執(zhí)行結(jié)束后，x、y、z的值分別是多少？進(jìn)程P1y=1;y=y+2;V(S1);z=y+1;P(S2);y=z+y;進(jìn)程P2x=1;x=x+1;P(S1);x=y+x;V(S2);z=x+z;思路：P1和P2具有相同的優(yōu)先級(jí)，并發(fā)，具有順序的不確定性；信號(hào)量S1和S2使得語(yǔ)句的執(zhí)行順序具有了制約關(guān)系繪制對(duì)應(yīng)的前趨圖2/5/202374《計(jì)算機(jī)操作系統(tǒng)》-第4章例題補(bǔ)充與講解：3進(jìn)程P1S1:y=1;S2:y=y+2;V(S1);S3:z=y+1;P(S2);S4:y=z+y;進(jìn)程P2S5:x=1;S6:x=x+1;P(S1);S7:x=y+x;V(S2);S8:z=x+z;x=5;y=12;z=92/5/202375《計(jì)算機(jī)操作系統(tǒng)》-第4章提問(wèn)環(huán)節(jié)－關(guān)于臨界區(qū)的管理軟件方法臨界區(qū)標(biāo)志法進(jìn)程數(shù)組標(biāo)志法1進(jìn)程數(shù)組標(biāo)志法2雙標(biāo)志法硬件方法缺陷信號(hào)量機(jī)制整型信號(hào)量基本信號(hào)量原理記錄型信號(hào)量多個(gè)進(jìn)程申請(qǐng)同一類資源AND型信號(hào)量同一進(jìn)程申請(qǐng)多個(gè)不同資源信號(hào)量集同一進(jìn)程申請(qǐng)多個(gè)同類資源多個(gè)進(jìn)程申請(qǐng)多個(gè)不同資源2/5/202376《計(jì)算機(jī)操作系統(tǒng)》-第4章本章目錄4.1進(jìn)程并發(fā)4.2臨界區(qū)管理4.3信號(hào)量機(jī)制4.4用信號(hào)量解決經(jīng)典進(jìn)程同步問(wèn)題4.5管程4.6進(jìn)程通信4.7線程的同步和通信重點(diǎn)與難點(diǎn)生產(chǎn)者－消費(fèi)者問(wèn)題讀者－寫(xiě)者問(wèn)題哲學(xué)家就餐問(wèn)題2/5/202377《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者-消費(fèi)者問(wèn)題假設(shè)緩沖池中有n個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)存放一個(gè)消息；可利用互斥信號(hào)量mutex使諸進(jìn)程對(duì)緩沖池實(shí)現(xiàn)互斥訪問(wèn)；利用empty和full計(jì)數(shù)信號(hào)量分別表示空緩沖及滿緩沖的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者互相等效，只要緩沖池未滿，生產(chǎn)者可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者可從緩沖池取走一個(gè)消息。同步問(wèn)題：生產(chǎn)者：P進(jìn)程不能往“滿”的緩沖區(qū)中放產(chǎn)品；消費(fèi)者：C進(jìn)程不能從“空”的緩沖區(qū)中取產(chǎn)品。2/5/202378《計(jì)算機(jī)操作系統(tǒng)》-第4章同步與互斥問(wèn)題互斥信號(hào)量mutex：防止多個(gè)進(jìn)程同時(shí)進(jìn)入臨界區(qū)同步信號(hào)量empty和full：保證事件發(fā)生的順序緩沖區(qū)滿時(shí)，Producer停止運(yùn)行緩沖區(qū)空時(shí)，Consumer停止運(yùn)行概念差別——互斥與同步（并發(fā)的兩個(gè)要素）互斥：保護(hù)臨界區(qū)，防止多個(gè)進(jìn)程同時(shí)進(jìn)入同步：保證進(jìn)程運(yùn)行的順序合理2/5/202379《計(jì)算機(jī)操作系統(tǒng)》-第4章同步/互斥信號(hào)量的使用方法互斥信號(hào)量必定成對(duì)出現(xiàn)：進(jìn)入臨界區(qū)——臨界區(qū)——退出臨界區(qū)同步信號(hào)量未必成對(duì)出現(xiàn)，依賴于同步關(guān)系的性質(zhì)同步信號(hào)量和互斥信號(hào)量的操作順序基本原則：互斥信號(hào)量永遠(yuǎn)緊鄰臨界區(qū)2/5/202380《計(jì)算機(jī)操作系統(tǒng)》-第4章生產(chǎn)者P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);消費(fèi)者C:Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);mutex,full,empty:semaphoremutex:=1;full:=0;empty:=n;生產(chǎn)者-消費(fèi)者問(wèn)題2/5/202381《計(jì)算機(jī)操作系統(tǒng)》-第4章P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);empty=nfull=0mutex=1in,out=0生產(chǎn)者和消費(fèi)者之間的約束：臨界區(qū)。生產(chǎn)者在生產(chǎn)時(shí)，消費(fèi)者不能消費(fèi)。生產(chǎn)者-消費(fèi)者問(wèn)題2/5/202382《計(jì)算機(jī)操作系統(tǒng)》-第4章P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);empty=nfull=0mutex=1in,out=0控制：緩沖區(qū)滿時(shí)不能繼續(xù)生產(chǎn)，制約生產(chǎn)者進(jìn)程P。生產(chǎn)者-消費(fèi)者問(wèn)題2/5/202383《計(jì)算機(jī)操作系統(tǒng)》-第4章C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);empty=nfull=0mutex=1in,out=0生產(chǎn)者和消費(fèi)者之間的約束：臨界區(qū)。生產(chǎn)者在生產(chǎn)時(shí)，消費(fèi)者不能消費(fèi)。生產(chǎn)者-消費(fèi)者問(wèn)題2/5/202384《計(jì)算機(jī)操作系統(tǒng)》-第4章C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);empty=nfull=0mutex=1in,out=0控制：緩沖區(qū)空時(shí)不能繼續(xù)消費(fèi)，制約消費(fèi)者進(jìn)程C。生產(chǎn)者-消費(fèi)者問(wèn)題2/5/202385《計(jì)算機(jī)操作系統(tǒng)》-第4章說(shuō)明wait和signal操作成對(duì)出現(xiàn)；對(duì)資源信號(hào)量的wait操作在前對(duì)互斥信號(hào)量的wait操作在后P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);生產(chǎn)者-消費(fèi)者問(wèn)題2/5/202386《計(jì)算機(jī)操作系統(tǒng)》-第4章P：Wait(empty);Wait(mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex);Signal(full);P：Wait(empty,mutex);Buffer(in)=nextp;in:=(in+1)modn;Signal(mutex,full);用AND型信號(hào)量解決同一問(wèn)題生產(chǎn)者-消費(fèi)者問(wèn)題2/5/202387《計(jì)算機(jī)操作系統(tǒng)》-第4章C：Wait(full);Wait(mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex);Signal(empty);C：Wait(full,mutex);netxc=buffer(out);out:=(out+1)modn;Signal(mutex,empty);用AND型信號(hào)量解決同一問(wèn)題生產(chǎn)者-消費(fèi)者問(wèn)題2/5/202388《計(jì)算機(jī)操作系統(tǒng)》-第4章讀者-寫(xiě)者問(wèn)題有兩組并發(fā)進(jìn)程:讀者和寫(xiě)者,共享一組數(shù)據(jù)區(qū)要求：允許多個(gè)讀者同時(shí)執(zhí)行讀操作不允許讀者、寫(xiě)者同時(shí)操作不允許多個(gè)寫(xiě)者同時(shí)操作2/5/202389《計(jì)算機(jī)操作系統(tǒng)》-第4章信號(hào)量描述互斥關(guān)系分析讀者和寫(xiě)者不能同時(shí)進(jìn)入共享數(shù)據(jù)區(qū)多個(gè)寫(xiě)者不能同時(shí)進(jìn)入共享數(shù)據(jù)區(qū)多個(gè)讀者可以同時(shí)進(jìn)入共享數(shù)據(jù)區(qū)同步關(guān)系分析讀者進(jìn)入緩沖區(qū)，寫(xiě)者必須等待寫(xiě)者進(jìn)入緩沖區(qū)，讀者必須等待讀者優(yōu)先：一旦有讀者進(jìn)入后續(xù)讀者均可進(jìn)入合理順序：讀者在先來(lái)的寫(xiě)者之后寫(xiě)者優(yōu)先：只要有寫(xiě)者等待后續(xù)讀者必須等待2/5/202390《計(jì)算機(jī)操作系統(tǒng)》-第4章信號(hào)量描述如果讀者來(lái)：1）無(wú)讀者、寫(xiě)者，新讀者可以讀2）有寫(xiě)者等，但有其它讀者正在讀，則新讀者也可以讀3）有寫(xiě)者寫(xiě)，新讀者等如果寫(xiě)者來(lái)：1）無(wú)讀者，新寫(xiě)者可以寫(xiě)2）有讀者，新寫(xiě)者等待3）有其它寫(xiě)者，新寫(xiě)者等待2/5/202391《計(jì)算機(jī)操作系統(tǒng)》-第4章兩個(gè)進(jìn)程：Reader、Writer讀者與寫(xiě)者間的互斥信號(hào)量：Wmutex＝1多個(gè)讀者間的互斥信號(hào)量：Rmutex＝1Readcount：正在讀取的進(jìn)程數(shù)目Readcount＝0時(shí)允許寫(xiě)讀者-寫(xiě)者問(wèn)題2/5/202392《計(jì)算機(jī)操作系統(tǒng)》-第4章wait(rmutex);Ifreadcount=0then wait(wmutex);Readcount:=readcount+1;signal(rmutex);……執(zhí)行讀取操作wait(rmutex);Readcount:=readcount-1ifreadcount=0then signal(wmutex);signal(rmutex);讀者部分讀者-寫(xiě)者問(wèn)題2/5/202393《計(jì)算機(jī)操作系統(tǒng)》-第4章wait(wmutex);……執(zhí)行寫(xiě)操作signal(wmutex);寫(xiě)者部分讀者-寫(xiě)者問(wèn)題2/5/202394《計(jì)算機(jī)操作系統(tǒng)》-第4章增加限制條件，即同時(shí)讀取的讀者數(shù)不能超過(guò)RNL,mx:=RN,1信號(hào)量集：Swait(S,d,t);Ssignal(S,d)S為信號(hào)量，d為需求量，t為下限值寫(xiě)者：Swait(mx,1,1;L,RN,0);……執(zhí)行寫(xiě)操作Ssignal(mx,1);讀者：Swait(L,1,1);Swait(mx,1,0);……執(zhí)行讀取操作Ssignal(L,1);讀者-寫(xiě)者問(wèn)題2/5/202395《計(jì)算機(jī)操作系統(tǒng)》-第4章讀者優(yōu)先的信號(hào)量解法typedefintsemphsemphmutex=1;semphwrite=1;intrcount=0;Reader進(jìn)程While(TRUE){P(mutex);rcount++;if(rcount==1)P(write);V(mutex);Read_Action();P(mutex);rcount--;if(rcount==0)V(write);V(mutex);}Writer進(jìn)程While(TRUE){P(Write);Write_Action();V(write);}2/5/202396《計(jì)算機(jī)操作系統(tǒng)》-第4章合理順序的信號(hào)量解法typedefintsemphsemphrmutex=1;semphwmutex=1semphwrite=1;semphconcur=1;intrcount=0;intwcount=0;Reader進(jìn)程While(TRUE){P(concur);P(rmutex);rcount++;if(rcount==1)P(write);V(rmutex);V(concur);Read_Action();P(mutex);rcount--;if(rcount==0)V(write);V(mutex);}Writer進(jìn)程While(TRUE){P(wmutex);wcount++;if(wcount==1)P(concur);V(wmutex);P(Write);Write_Action();V(write);P(wmutex);wcount--;if(wcount==0)V(concur);V(wmutex);}2/5/202397《計(jì)算機(jī)操作系統(tǒng)》-第4章互斥關(guān)系分析筷子：同一時(shí)刻只能有一個(gè)哲學(xué)家拿起筷子同步關(guān)系分析就餐：只有獲得兩個(gè)筷子后才能進(jìn)餐特殊情況考慮死鎖：如果每個(gè)哲學(xué)家都拿起一只筷子，都餓死并行程度：五只筷子允許兩人同時(shí)進(jìn)餐哲學(xué)家就餐問(wèn)題2/5/202398《計(jì)算機(jī)操作系統(tǒng)》-第4章哲學(xué)家就餐問(wèn)題的直觀解法哲學(xué)家進(jìn)程#defineN5voidphilosopher(inti){While(TRUE){think（）；take_forks(i);take_forks((i+1)%N);eat();put_forks(i);put_forks((i+1)%N);}}思考1：這樣的解法有何問(wèn)題？思考2：對(duì)左右的叉子是否可用進(jìn)行驗(yàn)證，這樣的修改有何優(yōu)缺點(diǎn)？思考3：需要引入幾個(gè)信號(hào)量才能實(shí)現(xiàn)最優(yōu)化的解法呢？2/5/202399《計(jì)算機(jī)操作系統(tǒng)》-第4章為防止死鎖發(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)食，并且一次拿到兩只筷子，否則不拿。哲學(xué)家就餐問(wèn)題2/5/2023100《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步應(yīng)用示例講解：1題目：桌上有一個(gè)盤(pán)子，可以存放一個(gè)水果。父親總是把蘋(píng)果放在盤(pán)子中，母親總是把香蕉放在盤(pán)子中；一個(gè)兒子專等吃盤(pán)中的香蕉，一個(gè)女兒專等吃盤(pán)中的蘋(píng)果。分析：四人公用一個(gè)盤(pán)子；盤(pán)子每次只能放一個(gè)水果，當(dāng)盤(pán)子為空時(shí)，父母均可嘗試放水果，但一次只能有一人成功；盤(pán)中是香蕉，兒子吃，女兒等；盤(pán)中是蘋(píng)果，女兒吃，兒子等。進(jìn)程描述：Father：父親放置水果的進(jìn)程；Mother：母親放置水果的進(jìn)程；Son：兒子吃水果的進(jìn)程；Daughter：女兒吃水果的進(jìn)程。變量設(shè)置：dish：表示盤(pán)子是否為空，初值=1；apple：表示盤(pán)中是否有蘋(píng)果，初值=0；banana：表示盤(pán)中是否有香蕉，初值=0。2/5/2023101《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步應(yīng)用示例講解：1Father:P(dish);將蘋(píng)果放入盤(pán)中；V(apple);dish：盤(pán)子是否為空，1apple：盤(pán)中是否有蘋(píng)果，0banana：盤(pán)中是否有香蕉，0Son:P(banana);從盤(pán)中取出香蕉；V(dish);吃香蕉；Mother:P(dish);將香蕉放入盤(pán)中；V(banana);Daughter:P(apple);從盤(pán)中取出蘋(píng)果；V(dish);吃蘋(píng)果；2/5/2023102《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步應(yīng)用示例講解：2題目：水入缸供老和尚飲用。水缸可容納10桶水。水井很窄，每次只能容一個(gè)桶取水。水桶總數(shù)為3個(gè)。每次入、取缸水僅為1桶，且不可同時(shí)進(jìn)行。請(qǐng)給出取水、入水的算法描述。取水：從井中取水，從缸中取水入水：水倒入缸中分析：水缸和水井互斥，即水井每次容納一個(gè)水桶進(jìn)出，水缸也是如此；井中取水、倒水入缸、取水出缸，每次用水桶1個(gè)；水缸中可以裝水10桶。進(jìn)程描述：Get：從井中取水入缸；Use：從缸中取水飲用。變量設(shè)置：mutex1：用于實(shí)現(xiàn)對(duì)水井的互斥使用，初值=1；mutex2：用于實(shí)現(xiàn)對(duì)水缸的互斥使用，初值=1；empty：用于記錄水缸還可以裝入的桶數(shù)，初值=10；full：用于記錄水缸中已裝入的桶數(shù)，初值=0；count：用于記錄可用水桶數(shù)，初值=3。2/5/2023103《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步應(yīng)用示例講解：2Get:P(empty);P(count);P(mutex1);井中取水；V(mutex1);P(mutex2);倒水入缸；V(mutex2);V(count);V(full);mutex1：對(duì)水井的互斥使用，1mutex2：對(duì)水缸的互斥使用，1empty：缸可以裝入的桶數(shù)，10full：缸中已裝入的桶數(shù)，0count：可用水桶數(shù)，3Use:P(full);P(count);P(mutex2);缸中取水；V(mutex2);V(empty);V(count);2/5/2023104《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步應(yīng)用示例講解：3題目：有一座橋如圖所示，車流如圖中箭頭所示。橋上不允許兩車交會(huì)，但允許同方向多輛車依次通行（即橋上可以有多個(gè)同方向的車）。用P、V操作實(shí)現(xiàn)交通管理，以防止橋上堵塞。2/5/2023105《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步應(yīng)用示例講解：3分析：車輛過(guò)橋時(shí)，提出過(guò)橋申請(qǐng)，如橋上無(wú)對(duì)方車輛則過(guò)橋；若該車為本方向第一輛車，應(yīng)阻塞對(duì)方車輛過(guò)橋；當(dāng)本方向無(wú)車輛過(guò)橋時(shí)，允許對(duì)方車輛過(guò)橋；同方向的多輛車可依次過(guò)橋，如果對(duì)方提出過(guò)橋申請(qǐng)，則阻塞本方向后續(xù)車輛過(guò)橋，待橋上車輛過(guò)完后，對(duì)方車輛過(guò)橋。同方向車輛的控制類似于讀者-寫(xiě)者問(wèn)題2/5/2023106《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步應(yīng)用示例講解：3變量設(shè)置：mutexN：用于實(shí)現(xiàn)北方車輛互斥訪問(wèn)變量countN，初值=1；mutexS：用于實(shí)現(xiàn)南方車輛互斥訪問(wèn)變量countS，初值=1；wait：用于實(shí)現(xiàn)雙方申請(qǐng)過(guò)橋車輛的排隊(duì)，初值=1；countN：用于記錄當(dāng)前北方正在過(guò)橋及已申請(qǐng)過(guò)橋的車輛數(shù)，初值=0；countS：用于記錄當(dāng)前南方正在過(guò)橋及已申請(qǐng)過(guò)橋的車輛數(shù)，初值=0；進(jìn)程描述：North、South：分別代表北方、南方車輛過(guò)橋的進(jìn)程2/5/2023107《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步應(yīng)用示例講解：3North:

P(wait);P(mutexN);if(countN==0)P(mutexS)//本方向第一輛車，阻塞對(duì)方車輛過(guò)橋countN++；V(mutexN);V(wait);車輛過(guò)橋；P(mutexN);countN--；if(countN==0)V(mutexS)//本方向最后一輛車允許對(duì)方車輛過(guò)橋V(mutexN);mutexN：北方車輛互斥訪問(wèn)變量countN，1mutexS：南方車輛互斥訪問(wèn)變量countS，1wait：雙方申請(qǐng)過(guò)橋車輛的排隊(duì)，1countN：北方正在過(guò)橋及已申請(qǐng)過(guò)橋的車輛數(shù)，0countS：南方正在過(guò)橋及已申請(qǐng)過(guò)橋的車輛數(shù)，02/5/2023108《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程同步應(yīng)用示例講解：3South:

P(wait);P(mutexS);if(countS==0)P(mutexNS)//本方向第一輛車，阻塞對(duì)方車輛過(guò)橋countS++；V(mutexS);V(wait);車輛過(guò)橋；P(mutexS);countS--；if(countS==0)V(mutexN)//本方向最后一輛車允許對(duì)方車輛過(guò)橋V(mutexS);mutexN：北方車輛互斥訪問(wèn)變量countN，1mutexS：南方車輛互斥訪問(wèn)變量countS，1wait：雙方申請(qǐng)過(guò)橋車輛的排隊(duì)，1countN：北方正在過(guò)橋及已申請(qǐng)過(guò)橋的車輛數(shù)，0countS：南方正在過(guò)橋及已申請(qǐng)過(guò)橋的車輛數(shù)，02/5/2023109《計(jì)算機(jī)操作系統(tǒng)》-第4章本章目錄4.1進(jìn)程并發(fā)4.2臨界區(qū)管理4.3信號(hào)量機(jī)制4.4用信號(hào)量解決經(jīng)典進(jìn)程同步問(wèn)題4.5管程4.6進(jìn)程通信4.7線程的同步和通信2/5/2023110《計(jì)算機(jī)操作系統(tǒng)》-第4章4.5管程管程(monitor)：新的同步機(jī)制用管程解決同步問(wèn)題比用信號(hào)量解決同步問(wèn)題更加簡(jiǎn)單。管程機(jī)制作為同步工具，便于在高級(jí)語(yǔ)言編程中實(shí)現(xiàn)。2/5/2023111《計(jì)算機(jī)操作系統(tǒng)》-第4章4.5.1管程的定義信號(hào)量實(shí)現(xiàn)進(jìn)程同步，P、V操作隨臨界資源的訪問(wèn)分散在各個(gè)進(jìn)程中，編寫(xiě)程序時(shí)容易造成P、V操作的順序混亂而出現(xiàn)進(jìn)程死鎖。用管程實(shí)現(xiàn)進(jìn)程同步，可將對(duì)臨界資源的操作集中在一起，以過(guò)程調(diào)用的形式提供給訪問(wèn)臨界資源的進(jìn)程使用。2/5/2023112《計(jì)算機(jī)操作系統(tǒng)》-第4章管程的定義只有進(jìn)入管理的進(jìn)程才有機(jī)會(huì)訪問(wèn)臨界資源，管程忽略臨界資源的內(nèi)部結(jié)構(gòu)形式和實(shí)現(xiàn)細(xì)節(jié)。管程的定義：一組數(shù)據(jù)結(jié)構(gòu)和數(shù)據(jù)結(jié)構(gòu)上的一組相關(guān)操作被稱為管程。一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行的在該數(shù)據(jù)結(jié)構(gòu)上的一組操作。2/5/2023113《計(jì)算機(jī)操作系統(tǒng)》-第4章管程的特點(diǎn)管程保護(hù)了管程中的信息只有定義在數(shù)據(jù)結(jié)構(gòu)上的管程所提供的過(guò)程才能訪問(wèn)該數(shù)據(jù)結(jié)構(gòu)。并發(fā)進(jìn)程互斥調(diào)用管程提供的過(guò)程任一時(shí)刻，只有一個(gè)進(jìn)程能調(diào)用管程提供的過(guò)程任一時(shí)刻，在管程中只能有一個(gè)進(jìn)程運(yùn)行訪問(wèn)完臨界資源的進(jìn)程需要喚醒阻塞等待同一資源的進(jìn)程2/5/2023114《計(jì)算機(jī)操作系統(tǒng)》-第4章管程的結(jié)構(gòu)管程只有一個(gè)入口和一個(gè)出口并發(fā)進(jìn)程在管程外等待調(diào)用管程中的過(guò)程如果進(jìn)程在管程中不能訪問(wèn)臨界資源，則在管程中阻塞等待訪問(wèn)完臨界資源的進(jìn)程將其喚醒

2/5/2023115《計(jì)算機(jī)操作系統(tǒng)》-第4章管程的定義管程是臨界資源監(jiān)控器。在保護(hù)臨界資源前提下，控制對(duì)臨界資源的訪問(wèn)define定義的過(guò)程，可以被進(jìn)程或其他管程模塊引用，而未定義的過(guò)程則僅在管程內(nèi)部使用。管程要引用模塊外定義過(guò)程，必須用use說(shuō)明。type<管程名>=monitor<管程變量說(shuō)明>；define<能被其他模塊引用的過(guò)程名列表>；use<(要引用的模塊外定義的)過(guò)程名列表>；procedure<過(guò)程名>（<形式參數(shù)表>）；begin<過(guò)程體>；end；…procedure<過(guò)程名>（<形式參數(shù)表>）；begin<過(guò)程體>；end；…begin<管程的局部數(shù)據(jù)初始化語(yǔ)句>；end；2/5/2023116《計(jì)算機(jī)操作系統(tǒng)》-第4章若干進(jìn)程互斥共享1個(gè)臨界資源時(shí)，管程的定義管程中用define子句聲明(可以在模塊外引用)：申請(qǐng)get和釋放put兩個(gè)過(guò)程，分別表示進(jìn)入管程過(guò)程和退出管程過(guò)程。管程中用use子句聲明(模塊外定義的操作):PP(condition)和VV(condition)兩個(gè)原子操作操作PP(condition)表示進(jìn)入管程的進(jìn)程在不能訪問(wèn)臨界資源時(shí)，在條件condition上阻塞等待臨界資源。操作VV(condition)表示訪問(wèn)完臨界資源的進(jìn)程釋放臨界資源時(shí)，喚醒在條件condition上阻塞等待所釋放的臨界資源的進(jìn)程。2/5/2023117《計(jì)算機(jī)操作系統(tǒng)》-第4章typeMS=MONITORvarbusy；varcondition;defineget，put;usePP，VV;procedureget /*進(jìn)入管程的過(guò)程調(diào)用*/beginifbusythenPP(condition)； /*如果臨界資源忙時(shí)，進(jìn)程調(diào)用PP阻塞*/busy：=true；end；procedureput /*退出管程的過(guò)程調(diào)用*/beginbusy：=false； /*將臨界資源的狀態(tài)設(shè)置為閑*/VV(condition)； /*喚醒阻塞等待所釋放臨界資源的進(jìn)程*/end；begin /*管程變量初始化*/busy：=false；end；2/5/2023118《計(jì)算機(jī)操作系統(tǒng)》-第4章4.5.2Hoare和Hansen觀點(diǎn)現(xiàn)象：在管程中的進(jìn)程，在某一條件變量condition上執(zhí)行操作VV后，如果在管程中有進(jìn)程處于阻塞等待該進(jìn)程釋放的臨界資源，則執(zhí)行操作VV的進(jìn)程會(huì)喚醒該阻塞進(jìn)程。執(zhí)行操作VV的進(jìn)程和被喚醒的進(jìn)程，會(huì)同時(shí)調(diào)用管程中的過(guò)程。因此，執(zhí)行操作VV(condition)的進(jìn)程正調(diào)用管程的退出過(guò)程，而被操作VV(condition)喚醒的過(guò)程正調(diào)用管程的進(jìn)入過(guò)程。而根據(jù)管程的互斥訪問(wèn)條件，不允許兩個(gè)進(jìn)程同時(shí)訪問(wèn)管程中的進(jìn)程。為了防止這種現(xiàn)象的發(fā)生，Hoare和Hanse提出了兩種不同的觀點(diǎn)。2/5/2023119《計(jì)算機(jī)操作系統(tǒng)》-第4章Hoare觀點(diǎn)操作VV是管程的過(guò)程中的最后一個(gè)操作。如果一個(gè)阻塞進(jìn)程P1在阻塞等待被喚醒時(shí)，進(jìn)程P2發(fā)出了喚醒進(jìn)程P1的操作VV，則進(jìn)程P1被喚醒后立即恢復(fù)在管程中執(zhí)行，同時(shí)進(jìn)程P2用操作PP阻塞自己。當(dāng)進(jìn)程P1訪問(wèn)完管程中的臨界資源，結(jié)束對(duì)管程中的過(guò)程調(diào)用或被其它條件阻塞時(shí)，進(jìn)程P2才被進(jìn)程P1用操作VV喚醒并恢復(fù)調(diào)用管程中的過(guò)程。2/5/2023120《計(jì)算機(jī)操作系統(tǒng)》-第4章Hansen觀點(diǎn)進(jìn)程P1在阻塞等待被喚醒時(shí)，進(jìn)程P2發(fā)出了喚醒進(jìn)程P1的操作VV，進(jìn)程P2繼續(xù)執(zhí)行的同時(shí)，條件被保存。當(dāng)進(jìn)程P2離開(kāi)管程時(shí)，進(jìn)程P1才會(huì)通過(guò)重新檢查條件來(lái)試圖恢復(fù)在管程中的執(zhí)行。2/5/2023121《計(jì)算機(jī)操作系統(tǒng)》-第4章4.5.3管程的應(yīng)用Hansen管程方法實(shí)現(xiàn)生產(chǎn)者—消費(fèi)者問(wèn)題在管程中定義變量notfull和notempty作為調(diào)用管程中過(guò)程的條件，認(rèn)為只要生產(chǎn)者可以生產(chǎn)，則notfull的值為true；只要消費(fèi)者可以消費(fèi)，則notempty的值為true。用Hansen管程方法實(shí)現(xiàn)讀者—寫(xiě)者問(wèn)題用兩個(gè)計(jì)數(shù)器rc和wc分別對(duì)讀者進(jìn)程和寫(xiě)者進(jìn)程計(jì)數(shù)；用R和W表示允許讀和寫(xiě)的條件；2/5/2023122《計(jì)算機(jī)操作系統(tǒng)》-第4章本章目錄4.1進(jìn)程并發(fā)4.2臨界區(qū)管理4.3信號(hào)量機(jī)制4.4用信號(hào)量解決經(jīng)典進(jìn)程同步問(wèn)題4.5管程4.6進(jìn)程通信4.7線程的同步和通信2/5/2023123《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程通信的類型共享存儲(chǔ)器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式基于共享存儲(chǔ)區(qū)的通信方式消息傳遞系統(tǒng)直接通信方式間接通信方式管道（Pipe）通信共享文件2/5/2023124《計(jì)算機(jī)操作系統(tǒng)》-第4章進(jìn)程通信的類型共享存儲(chǔ)器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式基于共享存儲(chǔ)區(qū)的通信方式步驟向操作系統(tǒng)申請(qǐng)共享存儲(chǔ)區(qū)掛接共享存儲(chǔ)區(qū)到進(jìn)程的存儲(chǔ)空間需要進(jìn)程互斥讀寫(xiě)存儲(chǔ)區(qū)通信結(jié)束后歸還存儲(chǔ)區(qū)評(píng)價(jià)適合進(jìn)程之間通信量大的情況下優(yōu)點(diǎn)是高效、快速2/5/2023125《計(jì)算機(jī)操作系統(tǒng)》-第4章共享存儲(chǔ)器系統(tǒng)基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式基于共享存儲(chǔ)區(qū)