操作系統(tǒng)課件：Chapter-02進(jìn)程管理

進(jìn)程管理第二章2.1什么是進(jìn)程2.2進(jìn)程控制2.3進(jìn)程同步2.4經(jīng)典IPC問(wèn)題2.5管程2.6進(jìn)程高級(jí)通信2.7線程1什么是進(jìn)程（1）為了提高計(jì)算機(jī)系統(tǒng)中各種資源的利用率，現(xiàn)代操作系統(tǒng)廣泛采用多道程序技術(shù)（multi-programming），使多個(gè)程序同時(shí)在系統(tǒng)中存在并運(yùn)行。Whyprocesses?2什么是進(jìn)程（2）3什么是進(jìn)程（3）在多道程序系統(tǒng)中，各個(gè)程序之間是并發(fā)執(zhí)行的，共享系統(tǒng)資源。CPU需要在各個(gè)運(yùn)行的程序之間來(lái)回地切換，這樣的話，要想描述這些多道的并發(fā)活動(dòng)過(guò)程就變得很困難。MIT的MULTICS系統(tǒng)中首先引入了“進(jìn)程”(Process)概念。4什么是進(jìn)程（4）一個(gè)進(jìn)程應(yīng)該包括：程序的代碼；程序的數(shù)據(jù)；PC中的值，用來(lái)指示下一條將運(yùn)行的指令；一組通用的寄存器的當(dāng)前值，堆、棧；一組系統(tǒng)資源（如打開(kāi)的文件）Aprocess＝aprograminexecution5什么是進(jìn)程（5）程序是文本，是語(yǔ)句的描述（靜態(tài)）進(jìn)程是運(yùn)行中的程序，含有上下文信息（動(dòng)態(tài)）Process≠Programmain()

{…..}A()

{…..}

PROCESSmain()

{…..}A()

{…..}

PROGRAMheap

StackAMainRegisters,PC6什么是進(jìn)程（6）一位有手好廚藝的計(jì)算機(jī)科學(xué)家正在為他的女兒烘制生日蛋糕。他有做生日蛋糕的食譜，廚房里有所需的原料：面粉、雞蛋、糖、香草汁等。食譜＝程序；科學(xué)家＝CPU；

原料＝數(shù)據(jù)；進(jìn)程＝做蛋糕；7什么是進(jìn)程（7）現(xiàn)在假設(shè)計(jì)算機(jī)科學(xué)家的兒子哭著跑了進(jìn)來(lái)，說(shuō)他被一只蜜蜂蜇了。計(jì)算機(jī)科學(xué)家就記錄下食譜做到哪兒了（保存進(jìn)程的當(dāng)前狀態(tài)），然而拿出一本急救手冊(cè)，按照其中的指示處理蜇傷。CPU從一個(gè)進(jìn)程（做蛋糕）切換到另一個(gè)進(jìn)程（醫(yī)療救護(hù)）。8什么是進(jìn)程（8）進(jìn)程特征結(jié)構(gòu)特征：程序段、相關(guān)的數(shù)據(jù)段、PCB構(gòu)成了進(jìn)程實(shí)體動(dòng)態(tài)性：進(jìn)程是進(jìn)程實(shí)體的一次執(zhí)行，進(jìn)程的狀態(tài)總是在變化，PCB的內(nèi)容總是在變化并發(fā)性：多個(gè)進(jìn)程實(shí)體，同存于內(nèi)存中，能在一段時(shí)間內(nèi)同時(shí)運(yùn)行（宏觀上）9什么是進(jìn)程（9）進(jìn)程特征獨(dú)立性：獨(dú)立運(yùn)行和資源調(diào)度的基本單位。每個(gè)進(jìn)程都有“自己”的PC和內(nèi)部狀態(tài)，運(yùn)行時(shí)獨(dú)立于其他的進(jìn)程（邏輯PC和物理PC）異步性：以各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)10什么是進(jìn)程（10）4個(gè)進(jìn)程并發(fā)執(zhí)行11什么是進(jìn)程（11）進(jìn)程與程序的區(qū)別：程序是靜態(tài)的被動(dòng)的，進(jìn)程是動(dòng)態(tài)的，主動(dòng)的。程序在外存上存儲(chǔ)，進(jìn)程在內(nèi)存中實(shí)現(xiàn)；程序沒(méi)有PCB，無(wú)法并發(fā)執(zhí)行，無(wú)法被調(diào)度，而進(jìn)程相反。一個(gè)程序多次執(zhí)行可以產(chǎn)生多個(gè)進(jìn)程，一個(gè)進(jìn)程可以執(zhí)行多個(gè)程序。12什么是進(jìn)程（12）進(jìn)程的三種基本狀態(tài)1)就緒(Ready)狀態(tài)：進(jìn)程一旦獲得CPU就可以投入運(yùn)行的狀態(tài)2)執(zhí)行狀態(tài)：進(jìn)程獲得CPU正在運(yùn)行的狀態(tài)3)阻塞狀態(tài)：進(jìn)程由于等待資源或某個(gè)事件的發(fā)生而暫停執(zhí)行的狀態(tài)13什么是進(jìn)程（13）可能的進(jìn)程狀態(tài)運(yùn)行阻塞就緒狀態(tài)間的轉(zhuǎn)化14什么是進(jìn)程（14）運(yùn)行

阻塞等待I/O的結(jié)果等待某一進(jìn)程提供輸入運(yùn)行

就緒運(yùn)行進(jìn)程用完了時(shí)間片運(yùn)行進(jìn)程被中斷，因?yàn)橐桓邇?yōu)先級(jí)進(jìn)程處于就緒狀態(tài)就緒

運(yùn)行調(diào)度程序選擇一個(gè)新的進(jìn)程運(yùn)行阻塞就緒當(dāng)所等待的事件發(fā)生時(shí)15什么是進(jìn)程（15）在某些系統(tǒng)中，由于一些特殊的原因（比如說(shuō)考察進(jìn)程情況或者調(diào)節(jié)系統(tǒng)負(fù)荷），進(jìn)程被從內(nèi)存中調(diào)出進(jìn)駐外存，不再接受調(diào)度。這種新的狀態(tài)被稱(chēng)為掛起狀態(tài)。16什么是進(jìn)程（16）ReadyaRunningBlockedaBlockedsReadyswakeup(喚醒)事件發(fā)生掛起suspend時(shí)間片完被調(diào)度schoduler解掛

active掛起

suspend解掛

active掛起

suspend等待事件

sleep事件發(fā)生wakeup(喚醒)17什么是進(jìn)程（17）描述進(jìn)程的數(shù)據(jù)結(jié)構(gòu)：進(jìn)程控制塊（ProcessControlBlock，PCB）。進(jìn)程控制塊是進(jìn)程實(shí)體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)，PCB中記錄了操作系統(tǒng)所需要的，用于描述進(jìn)程情況及控制進(jìn)程運(yùn)行所需的全部信息。OS是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。進(jìn)程控制塊（PCB）18什么是進(jìn)程（18）PCB的內(nèi)容19什么是進(jìn)程（19）系統(tǒng)用PCB來(lái)描述進(jìn)程的基本情況以及運(yùn)行變化的過(guò)程，PCB是進(jìn)程存在的唯一標(biāo)志。進(jìn)程的創(chuàng)建：為該進(jìn)程生成一個(gè)PCB；進(jìn)程的終止：回收它的PCB；進(jìn)程的組織管理：通過(guò)對(duì)PCB的組織管理來(lái)實(shí)現(xiàn)；進(jìn)程的狀態(tài)轉(zhuǎn)換：……？20什么是進(jìn)程（20）兩個(gè)進(jìn)程的狀態(tài)轉(zhuǎn)換21什么是進(jìn)程（21）將CPU切換到另一進(jìn)程需要保存原來(lái)進(jìn)程的狀態(tài)并裝入新進(jìn)程的保存狀態(tài)，這被稱(chēng)為上下文切換。上下文切換時(shí)間是額外開(kāi)銷(xiāo)，因?yàn)榍袚Q時(shí)系統(tǒng)并不能做什么有用的工作。上下文切換時(shí)間與硬件支持密切相關(guān)。上下文切換22什么是進(jìn)程（22）PCB的組織-鏈接23什么是進(jìn)程（23）PCB的組織-索引24什么是進(jìn)程（24）就緒隊(duì)列和各種I/O設(shè)備隊(duì)列25進(jìn)程控制（1）引起進(jìn)程創(chuàng)建的四個(gè)主要事件系統(tǒng)初始化時(shí)；在一個(gè)正在運(yùn)行的進(jìn)程當(dāng)中，執(zhí)行了創(chuàng)建進(jìn)程的系統(tǒng)調(diào)用；用戶請(qǐng)求創(chuàng)建一個(gè)新進(jìn)程；初始化一個(gè)批處理作業(yè)。進(jìn)程創(chuàng)建26進(jìn)程控制（2）從技術(shù)上來(lái)說(shuō)，只有一種創(chuàng)建進(jìn)程的方法，即在一個(gè)已經(jīng)存在的進(jìn)程（用戶進(jìn)程或系統(tǒng)進(jìn)程）當(dāng)中，通過(guò)系統(tǒng)調(diào)用來(lái)創(chuàng)建一個(gè)新的進(jìn)程。Unix：fork函數(shù)；Windows：CreateProcess函數(shù);進(jìn)程創(chuàng)建27進(jìn)程控制（3）進(jìn)程的創(chuàng)建(CreationofProgress)步驟(1)申請(qǐng)空白PCB(2)為新進(jìn)程分配資源(3)初始化進(jìn)程控制塊(4)將新進(jìn)程插入就緒隊(duì)列，如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程，便將新進(jìn)程插入就緒隊(duì)列進(jìn)程創(chuàng)建28進(jìn)程控制（4）在以下四種情形下，進(jìn)程終止：正常退出（自愿的）；錯(cuò)誤退出（自愿的）；致命錯(cuò)誤（強(qiáng)制性的）；被其他進(jìn)程所殺（強(qiáng)制性的），

Unix：kill，

Windows：TerminateProcess。進(jìn)程終止29進(jìn)程控制（5）進(jìn)程的終止步驟(1)讀出該進(jìn)程的狀態(tài)。(2)終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。(3)將其所有子孫進(jìn)程予以終止(4)將被終止進(jìn)程所擁有的全部資源歸還給其父進(jìn)程或者系統(tǒng)。(5)將被終止進(jìn)程的PCB從所在隊(duì)列(或鏈表)中移出。進(jìn)程終止30進(jìn)程控制（6）引起進(jìn)程阻塞和喚醒的事件(1)請(qǐng)求系統(tǒng)服務(wù)(2)啟動(dòng)某種操作(3)新數(shù)據(jù)尚未到達(dá)(4)無(wú)新工作可做進(jìn)程阻塞與喚醒31進(jìn)程控制（7）進(jìn)程阻塞過(guò)程(1)調(diào)用阻塞原語(yǔ)block把自己阻塞(2)將PCB插入阻塞隊(duì)列(3)最后，轉(zhuǎn)調(diào)度程序進(jìn)行重新調(diào)度，將處理機(jī)分配給另一就緒進(jìn)程，并進(jìn)行切換，亦即，保留被阻塞進(jìn)程的處理機(jī)狀態(tài)(在PCB中)，再按新進(jìn)程的PCB中的處理機(jī)狀態(tài)設(shè)置CPU的環(huán)境。

進(jìn)程阻塞與喚醒32進(jìn)程控制（8）進(jìn)程喚醒過(guò)程(1)首先把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出(2)將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒(3)然后再將該P(yáng)CB插入到就緒隊(duì)列中。進(jìn)程阻塞與喚醒33進(jìn)程控制（9）進(jìn)程的掛起過(guò)程修改進(jìn)程狀態(tài)PCB復(fù)制到某指定的內(nèi)存區(qū)域如有必要轉(zhuǎn)調(diào)度程序進(jìn)程的激活過(guò)程進(jìn)程調(diào)入內(nèi)存修改進(jìn)程狀態(tài)如搶占調(diào)度考慮是否執(zhí)行進(jìn)程的掛起與激活34進(jìn)程同步（1）進(jìn)程間通信（InterProcess

Communi-

cation，IPC）：進(jìn)程之間的信息交流與協(xié)調(diào)。如果兩個(gè)并發(fā)運(yùn)行的進(jìn)程之間沒(méi)有任何關(guān)聯(lián)關(guān)系（直接的或間接的），那么無(wú)須通信；如果兩個(gè)并發(fā)運(yùn)行的進(jìn)程之間存在著某種關(guān)聯(lián)關(guān)系（直接的或間接的），那么可能需要通信。例

如：兩個(gè)進(jìn)程使用相同的一個(gè)共享文件。35進(jìn)程同步（2）進(jìn)程間如何來(lái)通信呢，如何來(lái)相互傳遞信息呢？當(dāng)兩個(gè)或多個(gè)進(jìn)程在進(jìn)行一些關(guān)鍵性的臨界活動(dòng)時(shí)（如對(duì)共享資源的訪問(wèn)），如何確保它們不會(huì)相互妨礙——進(jìn)程互斥問(wèn)題；當(dāng)進(jìn)程之間存在著某種依存關(guān)系時(shí)，如何來(lái)調(diào)整它們的運(yùn)行次序——進(jìn)程同步問(wèn)題。36進(jìn)程同步（3）進(jìn)程的互斥spoolerdirectory:假脫機(jī)目錄，裝著要打印的內(nèi)容，進(jìn)程A和B同時(shí)要求打印，out指向下一個(gè)要打印的文件，in指向下一個(gè)空閑槽位。37進(jìn)程同步（4）...next_free_slot=in;write"file_a"toitemnext_free_slot++;updatein;...processAprocessB...next_free_slot=in;write"file_b"toitemnext_free_slot++;updatein;...next_free_slot=in;//7next_free_slot=in;//7write"file_b"toitemfile_bnext_free_slot++;//8updatein;//8write"file_a"toitemfile_anext_free_slot++//8;updatein;//838進(jìn)程同步（5）競(jìng)爭(zhēng)條件（racecondition）：兩個(gè)或多個(gè)進(jìn)程對(duì)同一共享數(shù)據(jù)同時(shí)進(jìn)行讀寫(xiě)操作，而最后的結(jié)果是不可預(yù)測(cè)的，它取決于各個(gè)進(jìn)程具體運(yùn)行情況。解決之道：在同一時(shí)刻，只允許一個(gè)進(jìn)程訪問(wèn)該共享數(shù)據(jù)，即如果當(dāng)前已有一個(gè)進(jìn)程正在使用該數(shù)據(jù)，那么其他進(jìn)程暫時(shí)不能訪問(wèn)。這就是互斥的概念。39進(jìn)程同步（6）進(jìn)程在運(yùn)行過(guò)程中所做的工作分為兩類(lèi)：內(nèi)部計(jì)算（不會(huì)導(dǎo)致競(jìng)爭(zhēng)條件）對(duì)共享內(nèi)存或共享文件的訪問(wèn)（可能導(dǎo)致競(jìng)爭(zhēng)條件）我們把完成第二類(lèi)工作的程序稱(chēng)為“臨界區(qū)”，把需要互斥訪問(wèn)的共享資源稱(chēng)為“臨界資源”。如果我們能設(shè)計(jì)出某種方法，使得任何兩個(gè)進(jìn)程都不會(huì)同時(shí)出現(xiàn)在臨界區(qū)中，就可以避免競(jìng)爭(zhēng)條件的出現(xiàn)。臨界資源和臨界區(qū)的引入40進(jìn)程同步（7）Repeat

entrysection

criticalsection

exitsectionremaindersectionUntilfalse對(duì)含有臨界區(qū)進(jìn)程的描述41進(jìn)程同步（8）任何兩個(gè)進(jìn)程都不能同時(shí)進(jìn)入臨界區(qū)；不能事先假定CPU的個(gè)數(shù)和運(yùn)行速度；當(dāng)一個(gè)進(jìn)程運(yùn)行在它的臨界區(qū)外面時(shí)，不能妨礙其他的進(jìn)程進(jìn)入臨界區(qū)；任何一個(gè)進(jìn)程進(jìn)入臨界區(qū)的要求應(yīng)該在有限時(shí)間內(nèi)得到滿足。實(shí)現(xiàn)互斥訪問(wèn)的四個(gè)條件42進(jìn)程同步（9）使用臨界區(qū)的互斥43進(jìn)程同步（10）信號(hào)量機(jī)制

1965年，由荷蘭學(xué)者Dijkstra

提出了信號(hào)量機(jī)制提出goto有害論最短路徑算法的創(chuàng)造者Algol60編譯器的設(shè)計(jì)者和實(shí)現(xiàn)者THE操作系統(tǒng)的設(shè)計(jì)者和開(kāi)發(fā)者提出信號(hào)量機(jī)制解決了有趣的“哲學(xué)家聚餐”問(wèn)題44進(jìn)程同步（11）整形信號(hào)量最初由Dijkstra把整型信號(hào)量定義為一個(gè)整型量，除初始化外，僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作(AtomicOperation)wait(S)和signal(S)來(lái)訪問(wèn)。這兩個(gè)操作一直被分別稱(chēng)為P、V操作。wait(S):whileS≤0dono-opS:=S-1;signal(S):S:=S+1;45進(jìn)程同步（12）整形信號(hào)量whileS≤0dono-opS:=S-1;臨界區(qū)S:=S+1;whileS≤0dono-opS:=S-1;臨界區(qū)S:=S+1;process0process1S：1whileS≤0dono-opS:=S-1;0臨界區(qū)whileS≤0dono-op執(zhí)行阻塞就緒P0P1時(shí)間片還沒(méi)完，我再歇會(huì)......S:=S+1;S:=S-1;臨界區(qū)S:=S+1;46進(jìn)程同步（13）記錄型信號(hào)量信號(hào)量被描述為一個(gè)記錄（或者結(jié)構(gòu)）。

typesemaphore=recordvalue:integer;L:listofprocess;endvalueL47進(jìn)程同步（14）P原語(yǔ)操作的定義：procedurewait(S)

varS:semaphore;begin

S.value:=S.value-1;ifS.value＜0then block(S,L)end48進(jìn)程同步（15）V原語(yǔ)操作的定義：proceduresignal(S)

varS:semaphore;begin

S.value:=S.value+1;ifS.value≤0then wakeup(S,L);end49進(jìn)程同步（16）在記錄型信號(hào)量機(jī)制中，S.value的初值表示系統(tǒng)中某類(lèi)資源的數(shù)目，因而又稱(chēng)為資源信號(hào)量，對(duì)它的每次wait操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類(lèi)資源，因此描述為S.value:=S.value-1；當(dāng)S.value＜0時(shí)，表示該類(lèi)資源已分配完畢，因此進(jìn)程應(yīng)調(diào)用block原語(yǔ)，進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號(hào)量鏈表S.L中。信號(hào)量值的意義50進(jìn)程同步（17）當(dāng)n個(gè)進(jìn)程互斥的使用某個(gè)臨界資源時(shí)，我們可以為此臨界資源設(shè)置一個(gè)用于互斥訪問(wèn)的信號(hào)量mutex，并初始化為1。每個(gè)進(jìn)程的組織結(jié)構(gòu)如下：

利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥wait(mutex)臨界區(qū)signal(mutex)剩余區(qū)51進(jìn)程同步（18）實(shí)例：有3個(gè)客戶在某天的日常生活中使用了某個(gè)ATM自動(dòng)取款機(jī)。假設(shè)他們對(duì)ATM的使用順序是a到來(lái)，a進(jìn)入，b到來(lái)，c到來(lái)，a離開(kāi)，b進(jìn)入，b離開(kāi)，c進(jìn)入，c離開(kāi)。52進(jìn)程同步（19）P(mutex)V(mutex)P1P2P3互斥區(qū)P(mutex)P(mutex)V(mutex)V(mutex)53進(jìn)程同步（20）執(zhí)行阻塞就緒1^0^-1Pcb_b-2Pcb_bPcb_c-1Pcb_c0^1^信號(hào)量變化54進(jìn)程同步（21）某閱覽室，最多可容納100名讀者同時(shí)閱覽，當(dāng)閱覽室中少于100名讀者時(shí)，閱覽室外等候的讀者可以立即進(jìn)入，否則需要在外面等待。每個(gè)讀者可看成一個(gè)進(jìn)程?；コ饫}55進(jìn)程同步（22）semaphoreseats；seats.value=100;while(閱覽時(shí)間){wait(seats);進(jìn)入閱覽室；閱讀；離開(kāi)閱覽室；signal(seats);}56進(jìn)程同步（23）互斥中可能出現(xiàn)的死鎖processA:……wait(Dmutex);

wait(Emutex);……signal(Dmutex);signal(Emutex);……

processB:……wait(Dmutex); wait(Emutex);……signal(Dmutex);signal(Emutex);……

57進(jìn)程同步（24）AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。這樣就可避免上述死鎖情況的發(fā)生。AND型信號(hào)量58進(jìn)程同步（25）Swait(S1,S2,…,Sn)ifSi≥1and…andSn≥1thenfori:=1tondo

Si:=Si-1;

endforelse

將進(jìn)程放入第一個(gè)Si

<1的信號(hào)量阻塞隊(duì)列，設(shè)置進(jìn)程pc到swait操作的開(kāi)始處endif59進(jìn)程同步（26）Ssignal(S1,S2,…,Sn)fori∶=1tondo

Si=Si+1;

將所有si信號(hào)量阻塞隊(duì)列中的進(jìn)程轉(zhuǎn)入就緒隊(duì)列endfor;60進(jìn)程同步（27）一般信號(hào)量集是指同時(shí)需要多種資源、每種占用的數(shù)目不同、且可分配的資源還存在一個(gè)臨界值時(shí)的信號(hào)量處理（一次需要N個(gè)某類(lèi)臨界資源時(shí)，就要進(jìn)行N次wait操作－－低效又可能死鎖）一般信號(hào)量集的基本思路就是在AND型信號(hào)量集的基礎(chǔ)上進(jìn)行擴(kuò)充，在一次原語(yǔ)操作中完成所有的資源申請(qǐng)信號(hào)量集61進(jìn)程同步（28）進(jìn)程對(duì)信號(hào)量Si的測(cè)試值為ti（表示信號(hào)量的判斷條件，要求Si>=ti；即當(dāng)資源數(shù)量低于ti時(shí)，便不予分配）；占用值為di（表示資源的申請(qǐng)量，即Si=Si-di）對(duì)應(yīng)的P、V原語(yǔ)格式為：Swait(S1,t1,d1;...;Sn,tn,dn);Ssignal(S1,d1;...;Sn,dn);信號(hào)量集62進(jìn)程同步（29）Swait(S1,t1,d1,…,Sn,tn,dn)ifSi≥t1and…and

Sn≥tnthenfori∶=1tondo

Si∶=Si-di;

endforelse將進(jìn)程放入第一個(gè)Si＜ti的信號(hào)量阻塞隊(duì)列，設(shè)置進(jìn)程pc到swait操作的開(kāi)始處

endif63進(jìn)程同步（30）signal(S1,d1,…,Sn,dn)fori∶=1tondo

Si∶=Si+di;將所有si信號(hào)量阻塞隊(duì)列中的進(jìn)程轉(zhuǎn)入就緒隊(duì)列

endfor;64進(jìn)程同步（31）一般“信號(hào)量集”的幾種特殊情況：(1)Swait(S,d,d)。此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量S，但允許它每次申請(qǐng)d個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)，不予分配。(2)Swait(S,1,1)。此時(shí)的信號(hào)量集已蛻化為一般的記錄型信號(hào)量(S＞1時(shí))或互斥信號(hào)量(S=1時(shí))。(3)Swait(S,1,0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng)S≥1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開(kāi)關(guān)。65進(jìn)程同步（32）進(jìn)程間的同步是指多個(gè)進(jìn)程中發(fā)生的事件存在某種時(shí)序關(guān)系，因此在各個(gè)進(jìn)程之間必須協(xié)同合作，相互配合，使各個(gè)進(jìn)程按一定的速度執(zhí)行，以共同完成某一項(xiàng)任務(wù)。進(jìn)程的互斥實(shí)質(zhì)上也是一種同步關(guān)系，進(jìn)程互斥可以看作是一種特殊的進(jìn)程同步。為便于區(qū)分，把進(jìn)程同步特指為對(duì)執(zhí)行順序嚴(yán)格要求的同步問(wèn)題。同步：合作。 互斥：競(jìng)爭(zhēng)。利用信號(hào)量實(shí)現(xiàn)進(jìn)程同步66進(jìn)程同步（33）【例子1】司機(jī)與售票員while(上班時(shí)間){

發(fā)動(dòng)汽車(chē)；正常運(yùn)行；到站停車(chē)；}while(上班時(shí)間){

關(guān)閉車(chē)門(mén)；售票；打開(kāi)車(chē)門(mén)；}只有關(guān)閉車(chē)門(mén)以后，才能啟動(dòng)汽車(chē)；只有停車(chē)以

后，才能打開(kāi)車(chē)門(mén)。67進(jìn)程同步（34）【例子2】三個(gè)并發(fā)進(jìn)程的讀寫(xiě)get進(jìn)程負(fù)責(zé)從輸入序列f中讀取字符，送到緩沖區(qū)s中；copy進(jìn)程把緩沖區(qū)s中的數(shù)據(jù)復(fù)制到緩沖區(qū)t；put進(jìn)程從緩沖區(qū)t中取出數(shù)據(jù)打印。68進(jìn)程同步（35）【例子1】司機(jī)與售票員while(上班時(shí)間){

P(S_Door);

發(fā)動(dòng)汽車(chē)；正常運(yùn)行；到站停車(chē)；

V(S_Stop);}公車(chē)司機(jī)while(上班時(shí)間){

關(guān)閉車(chē)門(mén)；

V(S_Door);

售票；

P(S_Stop);

打開(kāi)車(chē)門(mén)；}售票員semaphoreS_Door；//初始化為0semaphoreS_Stop; //初始化為0先關(guān)門(mén)

后開(kāi)車(chē)先停車(chē)

后開(kāi)門(mén)69進(jìn)程同步（36）【例子1】司機(jī)與售票員while(上班時(shí)間){

P(S_Door);

發(fā)動(dòng)汽車(chē)；正常運(yùn)行；到站停車(chē)；

V(S_Stop);}公車(chē)司機(jī)while(上班時(shí)間){

P(S_Stop);打開(kāi)車(chē)門(mén)；關(guān)閉車(chē)門(mén)；

V(S_Door);

售票；

}售票員semaphoreS_Door；//初始化為1semaphoreS_Stop; //初始化為0先關(guān)門(mén)

后開(kāi)車(chē)先停車(chē)

后開(kāi)門(mén)70進(jìn)程同步（37）【例子2】三個(gè)并發(fā)進(jìn)程的讀寫(xiě)設(shè)有一個(gè)緩沖區(qū)buffer，大小為一個(gè)字節(jié)。Compute進(jìn)程不斷產(chǎn)生字符，送buffer，Print進(jìn)程從buffer中取出字符打印。如不加控制，會(huì)出現(xiàn)多種打印結(jié)果，這取決于這兩個(gè)進(jìn)程運(yùn)行的相對(duì)速度。在這眾多的打印結(jié)果中，只有Compute和Print進(jìn)程的運(yùn)行剛好匹配的一種是正確的，其它均為錯(cuò)誤。bufferComputePrint71進(jìn)程同步（38）解題步驟：分析問(wèn)題，弄清楚同步關(guān)系；設(shè)置信號(hào)量，說(shuō)明其含義和初值；寫(xiě)出程序描述。問(wèn)題分析：要保證打印結(jié)果的正確，Compute和Print進(jìn)程必須遵循以下同步規(guī)則：當(dāng)Compute把數(shù)據(jù)送入buffer后，Print才能從

buffer中取，否則它必須等待（先存后?。?；當(dāng)Print從buffer取走數(shù)據(jù)后，Compute才能將

新數(shù)據(jù)送buffer，否則也須等待（先取后存）72進(jìn)程同步（39）while(計(jì)算未完成){

P(S_Empty);

Write_Data()；

V(S_Full);}

Computewhile(打印未完成){

P(S_Full)；

Print_Data()；

V(S_Empty);}PrintsemaphoreS_Empty； //緩沖區(qū)是否為空，初值為1semaphoreS_Full; //是否有數(shù)據(jù)寫(xiě)入，初值為073進(jìn)程同步（40）【例子2】三個(gè)并發(fā)進(jìn)程的讀寫(xiě)get進(jìn)程負(fù)責(zé)從輸入序列f中讀取字符，送到緩沖區(qū)s中；copy進(jìn)程把緩沖區(qū)s中的數(shù)據(jù)復(fù)制到緩沖區(qū)t；put進(jìn)程從緩沖區(qū)t中取出數(shù)據(jù)打印。74進(jìn)程同步（41）while(…){

P(S_Empty);

Get_Data(f,s)；

V(S_Full);}

Getwhile(…){

P(S_Full)；

P(T_Empty);

Copy_Data(s,t);

V(S_Empty);

V(T_Full);}Copywhile(…){

P(T_Full);

Put_Data(t,g)；

V(T_Empty);}

Put75進(jìn)程同步（42）信號(hào)量解決互斥問(wèn)題while(……){

P(S);

臨界區(qū)；

V(S);}while(……){

P(S);

臨界區(qū)；

V(S);}while(……){

P(S);

臨界區(qū)；

V(S);}while(……){

P(S);

臨界區(qū)；

V(S);}while(……){

P(S);

臨界區(qū)；

V(S);}while(……){

P(S);

臨界區(qū)；

V(S);}while(……){

P(S);

臨界區(qū)；

V(S);}while(……){

P(S);

臨界區(qū)；

V(S);}while(……){

P(S);

臨界區(qū)；

V(S);}76進(jìn)程同步（43）信號(hào)量解決同步問(wèn)題while(……){

P(S1);

……

V(S2);}while(……){

P(S2);

……V(S1);}互相合作的兩個(gè)進(jìn)程只有一個(gè)可以先執(zhí)行；信號(hào)量S1和S2的初值，一個(gè)為1，一個(gè)為077進(jìn)程同步（44）有一個(gè)倉(cāng)庫(kù)，可以存放A和B兩種產(chǎn)品。要求：1)每次只能存入一種產(chǎn)品(A或B)；2)-N<A產(chǎn)品數(shù)量-B產(chǎn)品數(shù)量<M。試用PV操作描述產(chǎn)品A與產(chǎn)品B的入庫(kù)過(guò)程。同步與互斥的混合問(wèn)題78進(jìn)程同步（45）同步與互斥的混合問(wèn)題while(……){

P(Sa);

P(mutex);

將產(chǎn)品入庫(kù)；

V(mutex);

V(Sb);}semaphoremutex；//初始化為1semaphoresa;//初始化為m-1semaphoresb;//初始化為n-1while(……){

P(Sb);

P(mutex);

將產(chǎn)品入庫(kù)；

V(mutex);

V(Sa);}79經(jīng)典IPC問(wèn)題（1）生產(chǎn)者-消費(fèi)者問(wèn)題哲學(xué)家就餐問(wèn)題讀者-寫(xiě)者問(wèn)題用信號(hào)量來(lái)解決，主要問(wèn)題：如何選擇信號(hào)量，如何安排P、V原語(yǔ)的順序。80經(jīng)典IPC問(wèn)題（2）兩個(gè)進(jìn)程（生產(chǎn)者和消費(fèi)者）共享一個(gè)公有的、固定大小的緩沖區(qū)，生產(chǎn)者不斷地制造產(chǎn)品，并把它放入緩沖區(qū)，而消費(fèi)者不斷地把產(chǎn)品取出來(lái)，并且使用它。要求兩個(gè)進(jìn)程都能正確地工作。 生產(chǎn)者-消費(fèi)者問(wèn)題描述81經(jīng)典IPC問(wèn)題（3）12345678生產(chǎn)者生產(chǎn)—消費(fèi)者問(wèn)題消費(fèi)方向生產(chǎn)方向消費(fèi)者82經(jīng)典IPC問(wèn)題（4）對(duì)于生產(chǎn)者進(jìn)程：制造一個(gè)產(chǎn)品，當(dāng)要送入緩沖區(qū)時(shí)，要檢查緩沖區(qū)是否已滿，若未滿，才可將產(chǎn)品送入緩沖區(qū)，并在必要時(shí)通知消費(fèi)者；否則等待；對(duì)于消費(fèi)者進(jìn)程：當(dāng)它去取產(chǎn)品時(shí)，先要檢查緩沖區(qū)中是否有產(chǎn)品可取，若有，則取走一個(gè)，并在必要時(shí)通知生產(chǎn)者；否則等待。這種相互等待，并互通信息就是典型的進(jìn)程同步。同時(shí)，緩沖區(qū)是個(gè)臨界資源，因此，各個(gè)進(jìn)程在使用緩沖區(qū)的時(shí)候，還有一個(gè)互斥的問(wèn)題。生產(chǎn)者-消費(fèi)者問(wèn)題解析83經(jīng)典IPC問(wèn)題（5）semaphoreS_Buffer_Num; //空閑的緩沖區(qū)個(gè)數(shù)，初值為NsemaphoreS_Product_Num; //緩沖區(qū)當(dāng)中的產(chǎn)品個(gè)數(shù)，初值為0semaphoreS_Mutex; //用于互斥訪問(wèn)的信號(hào)量，初值為184經(jīng)典IPC問(wèn)題（6）voidproducer(void)

{

intitem;

while(TRUE){

item=produce_item(); //制造一個(gè)產(chǎn)品

P(S_Buffer_Num); //是否有空閑緩沖區(qū)

P(S_Mutex); //進(jìn)入臨界區(qū)

insert_item(item); //產(chǎn)品放入緩沖區(qū)

V(S_Mutex); //離開(kāi)臨界區(qū)

V(S_Product_Num); //新增了一個(gè)產(chǎn)品

}}85經(jīng)典IPC問(wèn)題（7）voidconsumer(void)

{

intitem;

while(TRUE){

P(S_Product_Num); //緩沖區(qū)中有無(wú)產(chǎn)品

P(S_Mutex); //進(jìn)入臨界區(qū)

item=remove_item() //從緩沖區(qū)取產(chǎn)品

V(S_Mutex); //離開(kāi)臨界區(qū)

V(S_Buffer_Num); //新增一個(gè)空閑緩沖區(qū)

consume_item(item); //使用該產(chǎn)品

}}86經(jīng)典IPC問(wèn)題（8）五個(gè)哲學(xué)家圍坐在一張圓桌旁，每個(gè)哲學(xué)家面前都擺著一大盤(pán)意大利面條，面條非?；悦總€(gè)哲學(xué)家都需要兩把叉子才能進(jìn)餐，在相鄰兩個(gè)盤(pán)子之間，只有一把叉子。桌面的布局見(jiàn)右圖。哲學(xué)家就餐問(wèn)題描述本圖摘自“ModernOperatingSystems”012340123487經(jīng)典IPC問(wèn)題（9）哲學(xué)家就餐問(wèn)題描述每個(gè)哲學(xué)家的動(dòng)作只有兩種：進(jìn)餐和思考。當(dāng)一個(gè)哲學(xué)家感到饑餓時(shí)，他試圖去獲得他左邊和右邊的兩把叉子（一次取一把，順序無(wú)關(guān)），然后才能開(kāi)始進(jìn)餐。吃完以后，他需要把兩把叉子放回原處，然后繼續(xù)思考。問(wèn)題是：如何保證哲學(xué)家們的動(dòng)作有序進(jìn)行？如：不出現(xiàn)相鄰者同時(shí)要求進(jìn)餐，也不出現(xiàn)有人永遠(yuǎn)拿不到叉子。88經(jīng)典IPC問(wèn)題（10）#defineN5 //哲學(xué)家個(gè)數(shù)

voidphilosopher(inti)//哲學(xué)家編號(hào)：0－4

{

while(TRUE)

{

think(); //哲學(xué)家在思考

take_fork(i); //去拿左邊的叉子

take_fork((i+1)%N); //去拿右邊的叉子

eat(); //吃面條中….

put_fork(i); //放下左邊的叉子

put_fork((i+1)%N); //放下右邊的叉子

}}方案1：有可能死鎖89經(jīng)典IPC問(wèn)題（11）方案2：改進(jìn)版，仍有饑餓(starvation)可能while(1) //去拿兩把叉子

{

take_fork(i); //去拿左邊的叉子

if(fork((i+1)%N)){ //右邊叉子還在嗎

take_fork((i+1)%N);//去拿右邊的叉子

break; //兩把叉子均到手

}

else{ //右邊叉子已不在

put_fork(i); //放下左邊的叉子

wait_some_time(); //等待一會(huì)兒

}

}如果哲學(xué)家同時(shí)開(kāi)始算法......90經(jīng)典IPC問(wèn)題（12）方案3：繼續(xù)改進(jìn)版，可以工作，但不佳while(1) //去拿兩把叉子

{

take_fork(i); //去拿左邊的叉子

if(fork((i+1)%N)){ //右邊叉子還在嗎

take_fork((i+1)%N);//去拿右邊的叉子

break; //兩把叉子均到手

}

else{ //右邊叉子已不在

put_fork(i); //放下左邊的叉子

wait_random_time(); //等待隨機(jī)長(zhǎng)時(shí)間

}

}91經(jīng)典IPC問(wèn)題（13）方案4：獨(dú)吃大餐版，可以工作semaphoremutex //互斥信號(hào)量，初值1

voidphilosopher(inti)//哲學(xué)家編號(hào)i：0－4

{

while(TRUE){

think(); //哲學(xué)家在思考

P(mutex); //進(jìn)入臨界區(qū)

take_fork(i); //去拿左邊的叉子

take_fork((i+1)%N); //去拿右邊的叉子

eat(); //吃面條中….

put_fork(i); //放下左邊的叉子

put_fork((i+1)%N); //放下右邊的叉子

V(mutex); //退出臨界區(qū)

}}其實(shí)mutex可以最大到4......92經(jīng)典IPC問(wèn)題（14）S1思考中…

S2進(jìn)入饑餓狀態(tài)；

S3如果左鄰居或右鄰居正在進(jìn)餐，進(jìn)入阻塞狀態(tài)；

否則轉(zhuǎn)S4

S4

拿起兩把叉子；

S5吃面條…

S6放下左邊的叉子，看看左鄰居現(xiàn)在能否進(jìn)餐

（饑餓狀態(tài)、兩把叉子都在），若能則喚醒之；

S7放下右邊的叉子，看看右鄰居現(xiàn)在能否進(jìn)餐，

若能，喚醒之；

S8轉(zhuǎn)S1一種比較好的思路93經(jīng)典IPC問(wèn)題（15）必須有一個(gè)數(shù)據(jù)結(jié)構(gòu)，來(lái)描述每個(gè)哲學(xué)家的當(dāng)前狀態(tài)；該數(shù)據(jù)結(jié)構(gòu)是一個(gè)臨界資源，各個(gè)哲學(xué)家對(duì)它的訪問(wèn)應(yīng)該互斥地進(jìn)行——進(jìn)程互斥；一個(gè)哲學(xué)家吃飽后，可能要喚醒它的左鄰右舍，兩者之間存在著同步關(guān)系——進(jìn)程同步；解題關(guān)鍵問(wèn)題94經(jīng)典IPC問(wèn)題（15）數(shù)據(jù)結(jié)構(gòu)定義#defineN 5 //哲學(xué)家個(gè)數(shù)

#defineLEFT (i+N-1)%N //第i個(gè)哲學(xué)家的左鄰居

#defineRIGHT (i+1)%N //第i個(gè)哲學(xué)家的右鄰居

#defineTHINKING 0 //思考狀態(tài)

#defineHUNGRY 1 //饑餓狀態(tài)

#defineEATING 2 //進(jìn)餐狀態(tài)

int

state[N]; //記錄每個(gè)人的狀態(tài)

semaphoremutex; //互斥信號(hào)量，初值1

semaphores[N]; //每人一個(gè)信號(hào)量，095經(jīng)典IPC問(wèn)題（16）函數(shù)philosopher的定義voidphilosopher(inti)//i的取值：0到N－1

{

while(TRUE)

{

think(); //思考中…

take_forks(i); //拿到兩把叉子或被阻塞

eat(); //吃面條中…

put_forks(i); //把兩把叉子放回原處

}

}S1S2–S4S5S6–S796經(jīng)典IPC問(wèn)題（17）函數(shù)take_forks的定義//功能：要么拿到兩把叉子，要么被阻塞起來(lái)。

voidtake_forks(inti)//i的取值：0到N－1

{

P(mutex); //進(jìn)入臨界區(qū)

state[i]=HUNGRY; //我餓了！

test(i); //試圖拿兩把叉子

V(mutex); //退出臨界區(qū)

P(s[i]); //沒(méi)有叉子便阻塞

}97經(jīng)典IPC問(wèn)題（18）函數(shù)test的定義voidtest(inti) //i的取值：0到N－1

{

if(state[i]==HUNGRY&&

state[LEFT]!=EATING&&

state[RIGHT]!=EATING)

{

state[i]=EATING; //兩把叉子到手

V(s[i]); //第i人可以吃飯了

}

}98經(jīng)典IPC問(wèn)題（19）函數(shù)put_forks的定義//功能：把兩把叉子放回原處，并在需要的時(shí)候，

//去喚醒左鄰右舍。

voidput_forks(inti) //i的取值：0到N－1

{

P(mutex); //進(jìn)入臨界區(qū)

state[i]=THINKING; //交出兩把叉子

test(LEFT); //看左鄰居能否進(jìn)餐

test(RIGHT); //看右鄰居能否進(jìn)餐

V(mutex); //退出臨界區(qū)

}99經(jīng)典IPC問(wèn)題（20）讀者-寫(xiě)者問(wèn)題描述一個(gè)數(shù)據(jù)文件或記錄，可被多個(gè)進(jìn)程共享，只要求讀文件的進(jìn)程稱(chēng)為“Reader進(jìn)程”，其他進(jìn)程稱(chēng)為“Writer進(jìn)程”。規(guī)則是：允許多個(gè)進(jìn)程同時(shí)讀，但不允許同時(shí)讀寫(xiě)，或多個(gè)進(jìn)程同時(shí)寫(xiě)。100經(jīng)典IPC問(wèn)題（21）讀者-寫(xiě)者問(wèn)題解析任何時(shí)候“寫(xiě)者”最多只允許一個(gè)，而“讀者”可以有多個(gè)：“讀—寫(xiě)”是互斥的；“寫(xiě)—寫(xiě)”是互斥的；“讀—讀”是允許的；101經(jīng)典IPC問(wèn)題（22）基于讀者優(yōu)先的解法假設(shè)讀者來(lái)：1）若有其它讀者在讀，則不論是否有寫(xiě)者在等，新讀者都可以讀（讀者優(yōu)先）；2）若無(wú)讀者、寫(xiě)者，則新讀者也可以讀；3）若無(wú)讀者，且有寫(xiě)者在寫(xiě)，則新讀者等待；假設(shè)寫(xiě)者來(lái)：1）若有讀者，則新寫(xiě)者等待；2）若有其它寫(xiě)者，則新寫(xiě)者等待；3）若無(wú)讀者和寫(xiě)者，則新寫(xiě)者可以寫(xiě)；102經(jīng)典IPC問(wèn)題（23）解題關(guān)鍵需要設(shè)置一個(gè)計(jì)數(shù)器rc，用來(lái)記錄并發(fā)運(yùn)行的讀者個(gè)數(shù)；對(duì)于各個(gè)讀者而言，該計(jì)數(shù)器是一個(gè)臨界資源，對(duì)它的訪問(wèn)必須互斥進(jìn)行，因此設(shè)置一個(gè)互斥信號(hào)量S_mutex；對(duì)于各個(gè)寫(xiě)者而言、寫(xiě)者與所有的讀者而言，數(shù)據(jù)庫(kù)是一個(gè)臨界資源，對(duì)它的訪問(wèn)必須互斥地進(jìn)行，因此設(shè)置一個(gè)互斥信號(hào)量S_db。103經(jīng)典IPC問(wèn)題（24）基于讀者優(yōu)先的解答int

rc=0; //并發(fā)讀者的個(gè)數(shù)

semaphoreS_mutex; //對(duì)rc的互斥信號(hào)量，初值1

semaphoreS_db; //對(duì)數(shù)據(jù)庫(kù)的信號(hào)量，初值1voidwriter(void)

{

while(TRUE){

think_up_data(); //生成數(shù)據(jù)，非臨界區(qū)

P(S_db); //希望訪問(wèn)數(shù)據(jù)庫(kù)

write_data_base(); //更新數(shù)據(jù)庫(kù)

V(S_db); //退出臨界區(qū)

}

}104經(jīng)典IPC問(wèn)題（25）voidreader(void)

{

while(TRUE){

P(S_mutex); //互斥地訪問(wèn)計(jì)數(shù)器rc

rc++; //新增了一個(gè)讀者

if(rc==1)P(S_db);//如果是第一個(gè)讀者…

V(S_mutex); //退出對(duì)rc的訪問(wèn)

read_data_base(); //讀取數(shù)據(jù)庫(kù)的內(nèi)容

P(S_mutex); //互斥地訪問(wèn)計(jì)數(shù)器rc

rc--; //減少一個(gè)讀者

if(rc==0)V(S_db);//如果是最后一個(gè)讀者

V(S_mutex); //退出對(duì)rc的訪問(wèn)

use_data_read(); //使用數(shù)據(jù)，非臨界區(qū)

}

}105南開(kāi)天大之路（1）在南開(kāi)大學(xué)和天津大學(xué)之間有一條彎曲的小路，其中從S到T（或T到S）一段路每次只允許一輛自行車(chē)通過(guò)，但中間有一個(gè)小的“安全島”M(同時(shí)允許兩輛自行車(chē)停留)，可供兩輛自行車(chē)已從兩端進(jìn)入小路情況下錯(cuò)車(chē)使用，如圖所示。試設(shè)計(jì)一個(gè)算法使來(lái)往的自行車(chē)均可順利通過(guò)。106南開(kāi)天大之路（2）107南開(kāi)天大之路（3）任何一段路不允許兩輛車(chē)行駛。所以一個(gè)方向上只允許有一輛車(chē)。安全島允許兩輛車(chē)存在。所以安全島不用設(shè)置同步機(jī)制。因?yàn)檎麠l路最多只有兩輛車(chē)。兩個(gè)方向上的兩輛車(chē)在兩個(gè)支路只允許一輛車(chē)行駛。此題只有互斥沒(méi)有同步。題目分析108南開(kāi)天大之路（4）任何一段路不允許兩輛車(chē)行駛。所以一個(gè)方向上只允許有一輛車(chē)。S到T的整條路對(duì)于南開(kāi)的車(chē)是臨界資源。T到S的整條路對(duì)于天大的車(chē)是臨界資源。兩個(gè)方向上的兩輛車(chē)在兩個(gè)支路只允許一輛車(chē)行駛。SK路段和LT路段對(duì)南開(kāi)和天大的車(chē)都是臨界資源。題目分析109南開(kāi)天大之路（5）semaphoreST_mutex,TS_mutex,SK_mutex,LT_mutex;//初值1voidnankai(void){

P(ST_mutex)；

P(SK_mutex)；通過(guò)SK路段；進(jìn)入安全島M；

V(SK_mutex)；

P(LT_mutex)；通過(guò)LT路段：

V(LT_mutex)；

V(ST_mutex)；}voidtianda(void){

P(TS_mutex)；

P(LT_mutex)；通過(guò)LT路段；進(jìn)入安全島M；

V(LT_mutex)；

P(SK_mutex)；通過(guò)SK路段：

V(SK_mutex)；

V(TS_mutex)；}110和尚喝水（1）某寺廟，有小和尚和老和尚若干，有一個(gè)水缸，由小和尚提水入缸供老和尚飲用。水缸可以容納10桶水，水取自同一口井中，由于水井口窄，每次只能容納一個(gè)水桶取水。水桶總數(shù)為3個(gè)(老和尚和小和尚共同使用）。每次入水、取水僅為一桶，且不可同時(shí)進(jìn)行。試給出有關(guān)取水、入水的算法描述。111和尚喝水（2）很顯然這個(gè)問(wèn)題包含了互斥和同步。在使用到井(well)，缸(urn)，桶(bucket)時(shí)，必須互斥的使用。對(duì)于入水和取水來(lái)說(shuō)則是生產(chǎn)者和消費(fèi)者問(wèn)題。題目分析112和尚喝水（3）取水時(shí)要查看水缸是否有“full資源”，沒(méi)有則阻塞。取水后，釋放一個(gè)“empty資源”，如果必要喚醒一個(gè)入水的進(jìn)程。入水時(shí)要查看水缸是否有“empty資源”，沒(méi)有則阻塞。入水后，釋放一個(gè)“full資源”，如果必要喚醒一個(gè)取水的進(jìn)程。題目分析113和尚喝水（4）測(cè)試full資源;取來(lái)水桶；缸中取水；將水倒入飲水容器；還回水桶；釋放empty資源;喝水；測(cè)試empty資源;取來(lái)水桶；井邊打水；入水進(jìn)缸；還回水桶；釋放full資源;取水入水Semaphorewell,urn,bucket,empty,full;//初值1,1,3,10,0114和尚喝水（5）while(取水時(shí)間){p(full);p(bucket);取來(lái)水桶；p(urn);缸中取水；v(urn);將水倒入飲水容器；還回水桶；v(bucket);v(empty);喝水；}while(入水時(shí)間){p(empty);p(bucket);取來(lái)水桶；p(well);井邊打水；v(well);p(urn);入水進(jìn)缸；v(urn);還回水桶；v(bucket);v(full);}115管程（1）使用困難：各并發(fā)進(jìn)程間的邏輯關(guān)系比較復(fù)雜，在使用信號(hào)量時(shí)，必須小心謹(jǐn)慎，稍有不當(dāng)（如P、V操作的次序錯(cuò)誤、重復(fù)或遺漏）就會(huì)出錯(cuò)；出錯(cuò)后果嚴(yán)重：如競(jìng)爭(zhēng)狀態(tài)、死鎖和各種無(wú)法預(yù)料的、不可重現(xiàn)的錯(cuò)誤現(xiàn)象；可讀性差：信號(hào)量的控制分布在整個(gè)程序中，其正確性分析很困難；維護(hù)困難：各模塊的獨(dú)立性差，任一組變量或一段代碼的修改都可能影響全局。信號(hào)量方法的缺點(diǎn)116管程（2）為了更容易地編寫(xiě)出正確的程序，Hoare(1974)和Hansen(1975)提出了管程(monitor)的概念。其基本思想是：將共享變量以及對(duì)共享變量所進(jìn)行的操作封裝在一個(gè)模塊中。管程的引入117管程（3）管程是由一組變量、數(shù)據(jù)結(jié)構(gòu)和函數(shù)所構(gòu)成的一種特殊的軟件模塊。monitor

example

integer

i;

condition

c;

procedure

producer();

…

end;

procedure

consumer();

…

end;

endmonitor;118管程（4）封裝性：進(jìn)程可以調(diào)用管程當(dāng)中的函數(shù)，但是不能直接訪問(wèn)管程的內(nèi)部數(shù)據(jù)結(jié)構(gòu)；互斥性：在任何時(shí)候，只允許一個(gè)進(jìn)程在管程中活動(dòng)（即調(diào)用管程的函數(shù)）；語(yǔ)言相關(guān)性：管程屬于編程語(yǔ)言的范疇，由編譯器來(lái)識(shí)別并實(shí)現(xiàn)對(duì)管程內(nèi)函數(shù)的互斥訪問(wèn)。管程的特性119管程（5）互斥：把共享數(shù)據(jù)封裝在管程內(nèi)，把各個(gè)進(jìn)程的臨界區(qū)變成管程當(dāng)中的函數(shù)。這樣就能夠保證任何兩個(gè)進(jìn)程都不會(huì)同時(shí)進(jìn)入它們的臨界區(qū)；同步：在管程內(nèi)部，應(yīng)當(dāng)具有某種等待機(jī)制。當(dāng)進(jìn)入管程的進(jìn)程因資源被占用等原因不能繼續(xù)運(yùn)行時(shí)應(yīng)使其等待。因此在管程內(nèi)部可以聲明和使用一種特殊類(lèi)型的變量----條件變量（conditionvariables）?；诠艹痰倪M(jìn)程同步與互斥120管程（6）管程的結(jié)構(gòu)conditionc1wait(c1)…conditioncn

wait(cn)

局部數(shù)據(jù)條件變量過(guò)程1過(guò)程k出口初始化代碼入口管程等待調(diào)用的進(jìn)程隊(duì)列管程等待區(qū)域…121管程（7）條件變量：用來(lái)描述等待的原因。每個(gè)條件變量表示一種等待的原因，它不取具體的數(shù)值。對(duì)條件變量的操作：wait和signal；當(dāng)一個(gè)管程函數(shù)發(fā)現(xiàn)它不能繼續(xù)執(zhí)行下去時(shí)，使用wait操作，使得調(diào)用它的進(jìn)程進(jìn)入阻塞狀態(tài)，同時(shí)允許其他的進(jìn)程進(jìn)入管程；而signal操作的作用是喚醒某個(gè)正在等待的進(jìn)程；條件變量122管程（8）通過(guò)wait和signal操作即可實(shí)現(xiàn)進(jìn)程間同步關(guān)系；

wait操作和signal操作有點(diǎn)類(lèi)似于P、V原語(yǔ)，但條件變量不取具體的數(shù)值，不進(jìn)行信號(hào)的累加，因此在signal操作發(fā)出信號(hào)前，必須有wait操作在等待，否則該信號(hào)就丟失了。條件變量123管程（9）問(wèn)題：當(dāng)一個(gè)進(jìn)程P用signal操作喚醒另外一個(gè)進(jìn)程Q時(shí)，如何避免兩個(gè)進(jìn)程同時(shí)位于管程當(dāng)中呢？P等待，Q先執(zhí)行，直到它退出管程或者再次被阻塞；P繼續(xù)執(zhí)行，等它退出管程后Q再執(zhí)行；P在執(zhí)行signal操作后立即退出管程，即把signal作為管程函數(shù)的最后一條語(yǔ)句。124管程（10）125進(jìn)程高級(jí)通信（1）低級(jí)通信：只能傳遞狀態(tài)和整數(shù)值（控制信息），包括用來(lái)實(shí)現(xiàn)進(jìn)程同步和互斥的信號(hào)量和管程機(jī)制。優(yōu)點(diǎn)是速度快。缺點(diǎn)是：傳送信息量?。好看瓮ㄐ艂鬟f的信息量固定，若需要傳遞較多信息，就得進(jìn)行多次通信。編程復(fù)雜：用戶需要直接去實(shí)現(xiàn)通信的細(xì)節(jié)，編程復(fù)雜，容易出錯(cuò)。高級(jí)通信：能夠傳送任意數(shù)量的數(shù)據(jù)，包括三類(lèi)：共享內(nèi)存、管道、消息。低級(jí)通信與高級(jí)通信126進(jìn)程高級(jí)通信（2）絕大多數(shù)現(xiàn)代的操作系統(tǒng)都提供了相應(yīng)的方法，來(lái)讓各個(gè)進(jìn)程共享它們地址空間當(dāng)中的某些部分，即共享內(nèi)存。在共享內(nèi)存中，可以任意讀寫(xiě)和使用任意的數(shù)據(jù)結(jié)構(gòu)（緩沖區(qū)）。一組進(jìn)程向共享內(nèi)存中寫(xiě)，另一組進(jìn)程從共享內(nèi)存中讀，通過(guò)這種方式實(shí)現(xiàn)兩組進(jìn)程間的信息交換。類(lèi)似于生產(chǎn)者－消費(fèi)者問(wèn)題中的緩沖區(qū)，需要進(jìn)程的同步和互斥機(jī)制來(lái)確保數(shù)據(jù)的一致性。共享內(nèi)存127進(jìn)程高級(jí)通信（3）管道通信由UNIX首創(chuàng)，由于其有效性，后來(lái)的一些系統(tǒng)相繼引入了管道技術(shù)；管道通信以文件系統(tǒng)為基礎(chǔ)，所謂管道即連接兩個(gè)進(jìn)程之間的一個(gè)打開(kāi)的共享文件，專(zhuān)用于進(jìn)程之間的數(shù)