操作系統(tǒng)-CH2-進(jìn)程管理

1、操作系統(tǒng)XIA TIAN目錄CONTENTS2.1 進(jìn)程的基本概念2.2 進(jìn)程控制2.3 進(jìn)程同步2.4 經(jīng)典進(jìn)程同步問(wèn)題2.5 管程機(jī)制2.6 進(jìn)程通信2.7 線程XIA TIAN2.1進(jìn)程的基本概念未配置OS的系統(tǒng)：程序順序執(zhí)行 程序的順序執(zhí)行及其特征現(xiàn)代多道程序環(huán)境下：程序并發(fā)執(zhí)行 程序的并發(fā)執(zhí)行及其特征XIA TIAN2.1進(jìn)程的基本概念2.1.1 程序的順序執(zhí)行及特征 1. 程序執(zhí)行有固定的時(shí)序 2. 程序順序執(zhí)行時(shí)的特征 順序性：操作的前后依賴性 封閉型：獨(dú)占資源，資源狀態(tài)只有本程序更改 可再現(xiàn)性：初始環(huán)境和條件，結(jié)果相同I1C1P1I2C2P2XIA TIAN程序順序執(zhí)行的優(yōu)點(diǎn)符

2、合人的直覺(jué)有利于錯(cuò)誤調(diào)試XIA TIAN2.1.2 前趨圖有向無(wú)循環(huán)圖DAG目的：描述進(jìn)程之間的前后順序表示方式： (1) p1p2 (2) =(p1,p2)| p1 必須在p2開(kāi)始前完成P1P2P3P4P1P2P3XIA TIAN2.1.3 程序的并發(fā)執(zhí)行1. 多個(gè)程序的并發(fā)執(zhí)行I1I2I3I4C1C2C3C4P1P2P3P4tXIA TIAN例根據(jù)下述語(yǔ)句，畫(huà)出前趨圖 S1:a = x+2 S2:b = y+4 S3:c = a+b S4d = c+bXIA TIAN2.1.3 程序的并發(fā)執(zhí)行2. 特征 間斷性: 如打印程序等待計(jì)算程序完成之后方可繼續(xù) 執(zhí)行暫停執(zhí)行 失去封閉性 主要由共享

3、資源引起，資源的狀態(tài)將由多個(gè)程序改變； 不可再現(xiàn)性 計(jì)算結(jié)果與并發(fā)程序的執(zhí)行速度有關(guān) 例P29XIA TIAN例 有2個(gè)循環(huán)程序A和B，它們共享一個(gè)變量N（ 設(shè)N的初值為n ） 程序A每執(zhí)行一次時(shí)，都要做N:=N+1; 程序B每次要執(zhí)行Print(N), 然后再做N:=0. 若程序A,B以不同的速度運(yùn)行，其結(jié)果將會(huì)是？XIA TIAN2.1.3 程序的并發(fā)執(zhí)行 N:=N+1在print(N)和N:=0之前，則N值分別為n+1, n+1, 0. N:=N+1在print(N)和N:=0之后，則N值分別為n, 0, 1. N:=N+1在print(N)和N:=0之間，則N值分別為n, n+1, 0

4、.XIA TIAN例from multiprocessing import Processdef f1(i): while i-10: i = i-1 print f2 finished!if _name_=_main_: Process(target=f1, args=(0, ).start() Process(target=f2, args=(0,).start()XIA TIAN多次運(yùn)行結(jié)果XIA TIAN思考在多道程序環(huán)境下，程序執(zhí)行屬于并發(fā)執(zhí)行，具有3個(gè)典型特性（哪3個(gè)？）結(jié)果的不可再現(xiàn)性的問(wèn)題要保證結(jié)果的再現(xiàn)性，就需要對(duì)并發(fā)執(zhí)行的程序加以描述和控制，其結(jié)果就是引入了“進(jìn)程”概念進(jìn)程

5、=程序+執(zhí)行在Multics OS之前，主要采用IBM的“作業(yè)（job）”概念，之后，改為進(jìn)程（Process）XIA TIAN2.1.4 進(jìn)程的特征和狀態(tài)1. 進(jìn)程的特征和定義XIA TIAN2.1.4 進(jìn)程的特征和狀態(tài)(2) 如同時(shí)瀏覽多個(gè)網(wǎng)頁(yè) 只有建立了進(jìn)程，才能并發(fā)執(zhí)行。 獨(dú)立運(yùn)行，獨(dú)立獲得資源。資源分配與調(diào)度的基本單位 瀏覽器郵箱登陸實(shí)例XIA TIAN進(jìn)程定義進(jìn)程是程序?qū)嶓w的執(zhí)行過(guò)程，是系統(tǒng)進(jìn)行資源分配與調(diào)度的獨(dú)立單位。XIA TIAN2.1.4 進(jìn)程的特征和狀態(tài)(3)進(jìn)程執(zhí)行的間斷性，使得進(jìn)程具有多種不同的狀態(tài)2. 進(jìn)程的三種基本狀態(tài) 就緒 執(zhí)行 阻塞就緒就緒阻塞阻塞執(zhí)行執(zhí)行時(shí)間

6、片完時(shí)間片完進(jìn)程調(diào)度進(jìn)程調(diào)度I/OI/O請(qǐng)求請(qǐng)求I/OI/O完成完成圖圖2 25 5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換XIA TIAN2.1.4 進(jìn)程的特征和狀態(tài)(4)3. 掛起狀態(tài)（被換出內(nèi)存的狀態(tài)） 引入原因 終端用戶請(qǐng)求 父進(jìn)程請(qǐng)求 負(fù)荷調(diào)節(jié)需要 操作系統(tǒng)需要 掛起演示 vi，CTRL+z debugging 進(jìn)程狀態(tài)的轉(zhuǎn)換(圖2-6) 活動(dòng)就緒靜止就緒 活動(dòng)阻塞靜止阻塞 靜止就緒活動(dòng)就緒 靜止阻塞活動(dòng)阻塞XIA TIAN圖26 具有掛起狀態(tài)的進(jìn)程狀態(tài)圖執(zhí)行執(zhí)行活動(dòng)活動(dòng)就緒就緒靜止靜止就緒就緒活動(dòng)活動(dòng)阻塞阻塞靜止靜止阻塞阻塞激活激活掛起掛起激活激活掛起掛起釋放釋放釋放

7、釋放掛起掛起請(qǐng)求請(qǐng)求I/OI/OXIA TIAN實(shí)驗(yàn)寫(xiě)一個(gè)程序描述進(jìn)程狀態(tài)遷移過(guò)程。要求： 提供導(dǎo)致進(jìn)程狀態(tài)變化的調(diào)用接口，包括創(chuàng)建、刪除、調(diào)度、阻塞、時(shí)間到、掛起、激活等。 實(shí)現(xiàn)進(jìn)程列表顯示的接口。 注：這里設(shè)計(jì)的進(jìn)程是一個(gè)假設(shè)的對(duì)象實(shí)體，是由程序自己創(chuàng)建和刪除，不是系統(tǒng)維護(hù)的進(jìn)程。XIA TIAN2.1.5 進(jìn)程控制塊1.進(jìn)程控制塊的作用 是不能獨(dú)立運(yùn)行的程序變?yōu)槟塥?dú)立運(yùn)行的基本單位 是進(jìn)程存在的唯一標(biāo)志； PCB (Process Control Block)常駐內(nèi)存2.進(jìn)程控制塊中的信息 標(biāo)識(shí)、處理機(jī)狀態(tài)，進(jìn)程調(diào)度信息，進(jìn)程控制信息pid進(jìn)程狀態(tài)現(xiàn)場(chǎng)優(yōu)先級(jí)阻塞原因程序地址同步機(jī)制資源清

8、單鏈接指針XIA TIANPCB進(jìn)程標(biāo)識(shí)符 內(nèi)部標(biāo)識(shí)符與外部標(biāo)識(shí)符處理機(jī)狀態(tài) 能在斷點(diǎn)恢復(fù)運(yùn)行 通用寄存器、指令計(jì)數(shù)器、程序狀態(tài)字PSW、用戶棧指針進(jìn)程調(diào)度信息 進(jìn)程狀態(tài)、優(yōu)先級(jí)、與調(diào)度有關(guān)的其他信息（如等待時(shí)間）、事件（阻塞事件）進(jìn)程控制信息 程序和數(shù)據(jù)的地址 進(jìn)程同步和通信機(jī)制：消息隊(duì)列指針、信號(hào)量 資源清單 在PCB隊(duì)列中的鏈接指針XIA TIAN2.1.5 進(jìn)程控制塊(2)3.PCB的組織 鏈接方式 Q:什么是指針？執(zhí)行指針就緒隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB91XIA TIAN等待隊(duì)列示例struct

9、 wait_queue struct task_struct * task;struct wait_queue * next;PCBPCBPCBXIA TIAN2.1.5 進(jìn)程控制塊(3)3. PCB的組織 索引方式PCB1PCB2PCB3PCB4PCB5PCB6PCB7執(zhí)行指針執(zhí)行指針就緒表指針就緒表指針阻塞表指針阻塞表指針XIA TIAN補(bǔ)充PCB和進(jìn)程的代碼數(shù)據(jù)放在一起嗎？ 系統(tǒng)態(tài)和用戶態(tài) 系統(tǒng)空間和用戶空間系統(tǒng)調(diào)用和普通調(diào)用的區(qū)別？ 系統(tǒng)調(diào)用會(huì)引起從用戶態(tài)進(jìn)入核心態(tài)XIA TIAN2.2 進(jìn)程控制2.2.1 進(jìn)程的創(chuàng)建 一、進(jìn)程圖： 描述了進(jìn)程的家族關(guān)系：（P34 圖2-9） 子進(jìn)程可

10、繼承父的資源，撤消時(shí)應(yīng)歸還給父進(jìn)程，父的撤消會(huì)撤消全部子進(jìn)程。 二、引起創(chuàng)建進(jìn)程的事件： 1.用戶登錄： 為終端用戶建立一進(jìn)程 2.作業(yè)調(diào)度： 為被調(diào)度的作業(yè)建立進(jìn)程 3.提供服務(wù)： 如要打印時(shí)建立打印進(jìn)程 4.應(yīng)用請(qǐng)求： 由應(yīng)用程序建立多個(gè)進(jìn)程XIA TIAN2.2.1 進(jìn)程的創(chuàng)建(2) 三、進(jìn)程的創(chuàng)建：(create原語(yǔ)) 1.申請(qǐng)空白PCB（一個(gè)系統(tǒng)的PCB是有限的） 2.為新進(jìn)程分配資源（不同于一般的分配，PCB-LIST在一個(gè)特殊區(qū)域） 3.初始化PCB 4.將新進(jìn)程插入就緒隊(duì)列。XIA TIAN2.2.2 進(jìn)程的終止一、引起進(jìn)程終止的事件1.正常結(jié)束：如Halt、logoff2.異

11、常結(jié)束：如Protect error、overtime等3.外界干預(yù)： a.系統(tǒng)員kill進(jìn)程；（Linux演示） b.父進(jìn)程終止； c.父進(jìn)程請(qǐng)求。XIA TIAN2.2.2 進(jìn)程的終止(2)二、進(jìn)程的終止過(guò)程 （1）檢查進(jìn)程狀態(tài)； （2）執(zhí)行態(tài)中止，且置調(diào)度標(biāo)志為真。 （3）有無(wú)子孫需終止。 （4）歸還資源給其父進(jìn)程或系統(tǒng)。 （5）從PCB隊(duì)列中移出PCB.XIA TIAN2.2.3 進(jìn)程的阻塞與喚醒一、引起進(jìn)程阻塞和喚醒的事件 1.請(qǐng)求系統(tǒng)服務(wù)而得不到滿足時(shí)，如問(wèn)系統(tǒng)請(qǐng)求打印。 2.啟動(dòng)某種操作而需同步時(shí)：如該操作和請(qǐng)求該操作的進(jìn)程需同步運(yùn)行（即非異步操作）。 3.新數(shù)據(jù)尚未到達(dá)：如進(jìn)程

12、A寫(xiě)，進(jìn)程B讀，則A未寫(xiě)，完B不能讀。 4.無(wú)新工作可做。XIA TIAN2.2.3 進(jìn)程的阻塞與喚醒(2)二、進(jìn)程阻塞過(guò)程： 是進(jìn)程自身的一種主動(dòng)行為 a.調(diào)block原語(yǔ) b.停止執(zhí)行，修改PCB入阻塞隊(duì)列（一個(gè)或多個(gè)），并轉(zhuǎn)調(diào)度。三、喚醒過(guò)程 其它相關(guān)進(jìn)程完成。 a.wakeup原語(yǔ) b.修改PCB，入就緒隊(duì)列 可見(jiàn)，有block原語(yǔ)，在其它進(jìn)程中就應(yīng)有wakeup原語(yǔ)。XIA TIAN2.2.4 進(jìn)程的掛起與激活一、進(jìn)程的掛起過(guò)程 由進(jìn)程自己或其父進(jìn)程調(diào)suspend原語(yǔ)完成，將該進(jìn)程PCB移到指定區(qū)域，注意狀態(tài)的改變，有可能要重新調(diào)度。二、進(jìn)程的激活過(guò)程。 active原語(yǔ)（如在外存

13、，調(diào)入內(nèi)存，改變狀態(tài)，根據(jù)情況看是否調(diào)度，如搶先或非搶先）。阻塞、喚醒一般由OS實(shí)現(xiàn)，而掛起與激活可由用戶干預(yù)。XIA TIAN進(jìn)程同步部分XIA TIAN2.3 進(jìn)程同步并發(fā)提高了資源利用率和系統(tǒng)吞吐量，但也會(huì)給系統(tǒng)造成混亂。同步： 并發(fā)進(jìn)程在執(zhí)行次序上的協(xié)調(diào)，以達(dá)到有效的資源共享和相互合作，使程序執(zhí)行有可再現(xiàn)性。XIA TIAN2.3.1 進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系 資源共享關(guān)系：（進(jìn)程間接制約） 如爭(zhēng)用一臺(tái)打印機(jī) 需互斥地訪問(wèn)臨界資源。 相互合作關(guān)系：（進(jìn)程直接制約） 如A的輸出作為B的輸入 需要同步解決2. 臨界資源：（一次僅允許一個(gè)進(jìn)程訪問(wèn)的資源） 引起不可再現(xiàn)性是因?yàn)?/p>

14、臨界資源沒(méi)有互斥訪問(wèn)。XIA TIAN生產(chǎn)者消費(fèi)者問(wèn)題var n, integer; /變量定義Type item=;var buffer:array0,1,n-1 of item;in, out: 0,1, , n-1;counter: 0,1,n;XIA TIAN生產(chǎn)者消費(fèi)者問(wèn)題producer: repeatproduce an item in nextp; while counter=n do no-op;bufferin:=nextp;in:=(in+1)mod n;counter:=counter+1;until false;consumer: repeatwhile counte

15、r=0 do no-op;nextc:=bufferout;out:=(out+1) mod n;counter:=counter-1;consumer the item in nextc;until false;XIA TIANQuestion兩個(gè)進(jìn)程共享變量countercounter會(huì)導(dǎo)致結(jié)果不確定XIA TIAN生產(chǎn)者消費(fèi)者問(wèn)題(2)XIA TIAN3. 臨界區(qū)定義：進(jìn)程訪問(wèn)臨界資源的那段代碼稱(chēng)為臨界區(qū)訪問(wèn)臨界資源的描述： 進(jìn)入?yún)^(qū)：檢查有無(wú)進(jìn)程進(jìn)入 臨界區(qū)： 退出區(qū)：將訪問(wèn)標(biāo)志復(fù)位RepeatEntry sectionCritical sectionExit sectionUntil

16、falseXIA TIAN4. 同步機(jī)制應(yīng)遵循的準(zhǔn)則1.空閑讓進(jìn)2.忙則等待3.有限等待：應(yīng)保證為有限等待，避免“死等”。4.讓權(quán)等待：不能進(jìn)入臨界區(qū)的執(zhí)行進(jìn)程應(yīng)放棄CPU執(zhí)行權(quán)。避免“忙等”XIA TIAN信號(hào)量機(jī)制Edsger Wybe Dijkstra： 1930年5月11日2002年8月6日 畢業(yè)于Leiden大學(xué) 1972年獲得圖靈獎(jiǎng) 1989年計(jì)算機(jī)科學(xué)教育杰出貢獻(xiàn)獎(jiǎng) 2002年ACM PODC最具影響力論文獎(jiǎng) p 提出“goto有害論”;p 1965年，提出信號(hào)量和PV原語(yǔ);p 解決了有趣的“哲學(xué)家聚餐”問(wèn)題;p 最短路徑算法(SPF)和銀行家算法的創(chuàng)造者;p 第一個(gè)Algol

17、60編譯器的設(shè)計(jì)者和實(shí)現(xiàn)者;p THE操作系統(tǒng)的設(shè)計(jì)者和開(kāi)發(fā)者;與Knuth并稱(chēng)為我們這個(gè)時(shí)代最偉大的計(jì)算機(jī)科學(xué)家的人。 XIA TIAN2.3.2 信號(hào)量機(jī)制1 整型信號(hào)量 是一個(gè)整型量，通過(guò)2個(gè)原子操作wait(s)和signal(s)來(lái)訪問(wèn)。 Wait(s):while s= 0 do no-ops:=s-1; Signal(s):s:=s+1;XIA TIAN2 記錄型信號(hào)量由于整型機(jī)制中會(huì)不斷測(cè)試不滿足“讓權(quán)等待”而引入type semaphore=recordvalue:integer;L: list of process;endL:為進(jìn)程鏈表，用于鏈接所有等待該類(lèi)資源進(jìn)程。pro

18、cedure wait(s)var s: semaphorebegins.value:=s.value 1;if s.value 0 then block (S,L)endXIA TIAN2 記錄型信號(hào)量(2)procedure signal (S)var s:semaphonebegins.value:=s.vaule+1if s.value=0 then wakeup(s.L)End 用wait(s)和signal(s)實(shí)現(xiàn)同步與互斥。 在記錄型信號(hào)量機(jī)制中： s.value初值：表示系統(tǒng)中某類(lèi)資源的數(shù)目。 s.value0:表該信號(hào)量鏈表中已阻塞進(jìn)程的數(shù)目。為什么叫“記錄型”信號(hào)量？XI

19、A TIANP V操作Wait(s): 也用P(s) 表示，相當(dāng)于申請(qǐng)資源Signal(s): 也用V(s) 表示，相當(dāng)于釋放資源例如： 在公共電話廳打電話 上廁所XIA TIAN3 AND型信號(hào)量當(dāng)不用它時(shí)，有可能發(fā)生系統(tǒng)死鎖。死鎖：在無(wú)外力作用下的一種僵持狀態(tài)。AND信號(hào)量例：P42.特點(diǎn)：要么全分配，要么一個(gè)也不分配。XIA TIAN3 AND型信號(hào)量XIA TIANSwait(s1,s2,sn)if s11 and and sn 1 then for i:=1 to n do si:=si-1; endforelseplace the process in the waiting qu

20、eue with the first si found with si1，記錄型信號(hào)量。 S=1時(shí)，互斥型信號(hào)量。 （3）Swait(s,1,0)，可控開(kāi)關(guān)，當(dāng)S=1時(shí)，允許進(jìn)入，S1時(shí)，不能進(jìn)入。XIA TIAN2.3.3 信號(hào)量的應(yīng)用1.利用信號(hào)量實(shí)現(xiàn)互斥XIA TIAN1 利用信號(hào)量實(shí)現(xiàn)互斥(2)XIA TIAN2 利用信號(hào)量來(lái)描述前趨關(guān)系(1)S1S2S3S4S5S6abcdegfXIA TIAN2 利用信號(hào)量來(lái)描述前趨關(guān)系(2)XIA TIANLession 3XIA TIAN2.4 經(jīng)典進(jìn)程同步問(wèn)題2.4.1 生產(chǎn)者消費(fèi)者問(wèn)題2.4.2 哲學(xué)家進(jìn)餐問(wèn)題2.4.3 讀者寫(xiě)者問(wèn)題XIA

21、 TIAN生產(chǎn)者消費(fèi)者問(wèn)題定義兩個(gè)同步信號(hào)量： empty表示緩沖區(qū)中空緩沖區(qū)的數(shù)量，初值為n。 full表示緩沖區(qū)中滿的數(shù)量，初值為0。生產(chǎn)一個(gè)產(chǎn)品取出一個(gè)產(chǎn)品XIA TIAN producer: begin repeat Produce an item in nextp; 一、記錄型信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題XIA TIANwait(empty);wait(mutex);buffer(in):=nextp;in:=(in+1) mod n;signal(mutex);signal(full);Until false;endconsumer:beginrepeat wait(full);wa

22、it(mutex);nextc:=buffer(out);out:=(out+1) mod n;signal(mutex);signal(empty);Consumer the item in nextc;Until false;endparendend一、記錄型信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題XIA TIAN二、利用AND信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題XIA TIAN2.4.2 哲學(xué)家進(jìn)餐問(wèn)題 有五個(gè)哲學(xué)家圍坐在一圓桌旁，桌中央有一盤(pán)通心面，每人面前有一只空盤(pán)子，每?jī)扇酥g放一把叉子。每個(gè)哲學(xué)家思考、饑餓、然后吃通心面。為了吃面，每個(gè)哲學(xué)家必須獲得兩把叉子，且每人只能直接從自己左邊或右邊去取叉子。XI

23、A TIAN2.4.2 哲學(xué)家進(jìn)餐問(wèn)題解決思路1、每一把叉子都是必須互斥使用的，所以，必須為每一把叉子設(shè)置一個(gè)互斥信號(hào)量Si （i0,1,2,3,4)；2、初值都為1;3、當(dāng)一個(gè)哲學(xué)家吃面時(shí)必須獲得自己左邊和右邊的兩把叉子，即執(zhí)行兩個(gè)P操作(wait)；吃完面后，必須放下兩個(gè)叉子，即執(zhí)行兩個(gè)V操作(signal)。XIA TIAN2.4.2 哲學(xué)家進(jìn)餐問(wèn)題1.利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問(wèn)題XIA TIAN2.4.2 哲學(xué)家進(jìn)餐問(wèn)題1.利用AND信號(hào)量解決哲學(xué)家進(jìn)餐問(wèn)題XIA TIAN課堂練習(xí)請(qǐng)利用記錄型信號(hào)量寫(xiě)出一個(gè)不會(huì)死鎖的哲學(xué)家進(jìn)餐問(wèn)題的算法。XIA TIAN2.4.3 讀者寫(xiě)者問(wèn)題讀

24、者寫(xiě)者問(wèn)題 有兩組并發(fā)進(jìn)程: 讀者和寫(xiě)者,共享一組數(shù)據(jù)區(qū) 要求： 允許多個(gè)讀者同時(shí)執(zhí)行讀操作 不允許讀者、寫(xiě)者同時(shí)操作 不允許多個(gè)寫(xiě)者同時(shí)操作 特點(diǎn)： 讀進(jìn)程可共享同一對(duì)象。 寫(xiě)進(jìn)程不可共享同一對(duì)象。XIA TIANProblem Statement： 一組公共數(shù)據(jù)DB R1 Rm W1 . Wn要求：（1）R-R可以同時(shí) （2）R-W不可同時(shí) （3）W-W不可同時(shí)accessingXIA TIAN一、利用記錄型信號(hào)量解決讀者寫(xiě)者問(wèn)題 讀者等待在何處？讀者等待在何處？ 讀者如何被喚醒？讀者如何被喚醒？XIA TIAN一、利用記錄型信號(hào)量解決讀者寫(xiě)者問(wèn)題XIA TIAN一、利用記錄型信號(hào)量解決讀

25、者寫(xiě)者問(wèn)題XIA TIAN二、信號(hào)量集解決讀者寫(xiě)者問(wèn)題(略)XIA TIAN二、信號(hào)量集解決讀者寫(xiě)者問(wèn)題(略)XIA TIAN上述方法為讀者優(yōu)先如果讀者來(lái)： 1）無(wú)讀者、寫(xiě)者，新讀者可以讀 2）有寫(xiě)者等，但有其它讀者正在讀，則新讀者也可以讀 3）有寫(xiě)者寫(xiě)，新讀者等如果寫(xiě)者來(lái)： 1）無(wú)讀者，新寫(xiě)者可以寫(xiě) 2）有讀者，新寫(xiě)者等待 3）有其它寫(xiě)者，新寫(xiě)者等待XIA TIAN讀者優(yōu)先分析問(wèn)題：讀者源源不斷，readCount不歸0，寫(xiě)者會(huì)被餓死。策略：一旦有寫(xiě)者等待，新到達(dá)讀者等待，正在讀的讀者都結(jié)束后，寫(xiě)者進(jìn)入。XIA TIAN寫(xiě)者優(yōu)先條件： 1）多個(gè)讀者可以同時(shí)進(jìn)行讀 2）寫(xiě)者必須互斥（只允許一個(gè)

26、寫(xiě)者寫(xiě)，也不能讀者寫(xiě)者同時(shí)進(jìn)行） 3）寫(xiě)者優(yōu)先于讀者（一旦有寫(xiě)者，則后續(xù)讀者必須等待，喚醒時(shí)優(yōu)先考慮寫(xiě)者） 練習(xí)嘗試XIA TIAN練習(xí)a,b 兩點(diǎn)間是一段東西向的單行車(chē)道，現(xiàn)要設(shè)計(jì)一個(gè)自動(dòng)管理系統(tǒng)，管理規(guī)則如下：當(dāng)ab間有車(chē)輛在行駛時(shí)同方向的車(chē)可以同時(shí)駛?cè)隺b段，但另一方向的車(chē)必須在ab段外等待；當(dāng)ab之間無(wú)車(chē)時(shí)，到達(dá)a（或b）的車(chē)輛可以進(jìn)入ab段，但不能從a，b點(diǎn)同時(shí)駛?cè)?；?dāng)某方向在ab段行駛的車(chē)輛使出了ab段且無(wú)車(chē)輛進(jìn)入ab段時(shí)，應(yīng)讓另一方向等待的車(chē)輛進(jìn)入ab段行駛。請(qǐng)用wait,signal工具對(duì)ab段實(shí)現(xiàn)正確管理。XIA TIAN答：Semaphore s, mutexab,mute

27、xbaPab：Wait(mutexab)Countab+If countab=1 then wait(s);Signal(mutexab) .wait(mutexab)countab- -;if countab=0 then signal(s)signal(mutexab);XIA TIAN答：Pba:wait(mutexba)countba=countba+1;If countba=1 then wait(s)signal(mutexba) enter;wait(mutexba)countba-;if countba=0 then signal(s)signal(mutexba);XIA T

28、IAN作業(yè)討論無(wú)死鎖的哲學(xué)家進(jìn)餐問(wèn)題寫(xiě)者優(yōu)先XIA TIAN練習(xí)設(shè)有兩個(gè)生產(chǎn)者進(jìn)程A、B和一個(gè)銷(xiāo)售者進(jìn)程C，他們共享一個(gè)無(wú)限大的倉(cāng)庫(kù)，生產(chǎn)者每次循環(huán)生產(chǎn)一個(gè)產(chǎn)品，然后入庫(kù)供銷(xiāo)售者銷(xiāo)售；銷(xiāo)售者每次循環(huán)從倉(cāng)庫(kù)中取出一個(gè)產(chǎn)品進(jìn)行銷(xiāo)售。如果不允許同時(shí)入庫(kù)，也不允許邊入庫(kù)邊出庫(kù)；而且要求生產(chǎn)和銷(xiāo)售A產(chǎn)品和B產(chǎn)品的件數(shù)都滿足以下關(guān)系：-nA的件數(shù)-B的件數(shù)m,其中m、n是正整數(shù)。使用信號(hào)量機(jī)制寫(xiě)出A、B和C三個(gè)進(jìn)程的工作流程XIA TIAN分析設(shè)置信號(hào)量mutext，互斥訪問(wèn)倉(cāng)庫(kù)為滿足-nA的件數(shù)-B的件數(shù)m，設(shè)置兩個(gè)同步信號(hào)量 SAB：允許A當(dāng)前生產(chǎn)的數(shù)量，初值為m SBA：允許B當(dāng)前生產(chǎn)的數(shù)量，初值為

29、nXIA TIAN分析為實(shí)現(xiàn)生產(chǎn)者和銷(xiāo)售者的同步， 設(shè)置變量Difference：表示A與B所銷(xiāo)售的數(shù)量之差，初值為0 設(shè)置三個(gè)信號(hào)量：S、SA、SB，分別表示倉(cāng)庫(kù)中總的產(chǎn)品量、倉(cāng)庫(kù)中A的產(chǎn)品量和B的產(chǎn)品量，初值為0XIA TIAN生產(chǎn)者Process A:Repeat wait(SAB) produce a product A signal(SBA) /加入倉(cāng)庫(kù) wait(mutex) add A to storehouse signal(mutex) siganl(SA) signal(S)Until falseProcess BRepeat wait(SBA) produce a pro

30、duct B signal(SAB) /加入倉(cāng)庫(kù) wait(mutex) add B to storehouse signal(mutex) siganl(SB) signal(S)Until falseXIA TIAN銷(xiāo)售者CRepeat wait(S) if (difference=m) /A賣(mài)的太多了 wait(SB) wait(mutex) take B signal(mutex) difference -= 1 else wait(mutex) take product A or B signal(mutex) if(type=A) wait(SA) difference+=1 el

31、se wait(SB) difference -=1 Sell productUntil falseXIA TIAN練習(xí)（嗜睡的理發(fā)師問(wèn)題）一個(gè)理發(fā)店由一個(gè)有N張沙發(fā)的等候室和一個(gè)放有一張理發(fā)椅的理發(fā)室組成。沒(méi)有顧客時(shí)，理發(fā)師便去睡覺(jué)。當(dāng)一個(gè)顧客走進(jìn)理發(fā)店時(shí)，如果所有的沙發(fā)都已被占用，便離開(kāi)理發(fā)店；否則，如果理發(fā)師正在為其他顧客理發(fā)，該顧客就找一張空沙發(fā)坐下等待；如果理發(fā)師因無(wú)顧客正在睡覺(jué)，則由新到的顧客喚醒理發(fā)師為其理發(fā)。在理發(fā)完成時(shí)，顧客必須付費(fèi)，直到理發(fā)師收費(fèi)后才能離開(kāi)理發(fā)店。試用信號(hào)量實(shí)現(xiàn)這一同步問(wèn)題XIA TIAN分析設(shè)置整型變量count，記錄顧客數(shù)；設(shè)置mutex信號(hào)量，保證對(duì)c

32、ount的互斥，初值為1對(duì)等候室中的N張沙發(fā)，設(shè)置信號(hào)量sofa，初值為NEmpty信號(hào)量表示是否有空閑的理發(fā)椅，初值為1Full表示理發(fā)椅上是否有等待理發(fā)的顧客，初值為0XIA TIAN分析Full表示理發(fā)椅上是否有等待理發(fā)的顧客，初值為0Cut信號(hào)量表示理發(fā)是否完成，初值為0Payment表示等待付費(fèi)，初值為0Receipt表示等待收費(fèi)，初值為0XIA TIAN顧客Wait(mutex)If(countN) signal(mutex) exit else count+; signal(mutex) if(count1) wait(sofa) sit on wait(empty) get u

33、p from sofa signal(sofa) else wait(empty) sit on baber_chair signal(full) wait(cut) pay signal(payment) wait(receipt) get up from baber_chair signal(empty) wait(mutex) count- siganl(mutex) exit shopXIA TIAN理發(fā)師While(true)Wait(full)Cut hairSignal(cut）Wait(payment)Accept paymentSignal(recipt)XIA TIAN2.

34、5 管程機(jī)制70年代初, By E.W.Dijkstra, C.A.R.Hoare, P.B.Hansen. 背景: Structured programming引入原因： 為了避免凡要使用臨界資源的進(jìn)程都自備同步操作wait(s)和signal(s).將同步操作的機(jī)制和臨界資源結(jié)合到一起，形成管程。XIA TIAN2.5.1 管程的基本概念一、定義：一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行的一組操作。 局部于管程的共享變量。 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)程操作的一組過(guò)程。 對(duì)局部管程數(shù)據(jù)設(shè)置初值。二、條件變量： x.y: x.wait; x.signal; x.queueXIA TIAN一、建立管程：PC包括：二

35、過(guò)程：（1）put(item)過(guò)程；（2）get(item)過(guò)程一變量：countn時(shí)滿；0 時(shí)空初始： in=out=count=0Type producer-consumer=monitorvar in,out,count：integer;buffer: array 0,n-1 of item;notfull, notempty: condition;procedure entry put (item)procedure entry get (item)2.5.2 利用管程解決生產(chǎn)者消費(fèi)者問(wèn)題XIA TIANProcedure entry put(item)begin if count n

36、 then notfull.wait; buffer(in):=nextp; in:=(in+1)mod n count:=count+1; if notempty.queue then notempty.signal;endProcedure entry get(item)begin if count 0 then notempty.wait; nextc:=buffer(out); out:=(out+1)mod n count:=count-1; if notfull.queue then notfull.signal;endBegin in:=out:=0; count:=0 end2

37、.5.2 利用管程解決生產(chǎn)者消費(fèi)者問(wèn)題XIA TIANproducer: beginrepeat produce an item in nextp PC. put (item);until false.EndConsumer: beginrepeat PC.get(item); Consume the item in nextc;Until falseend 可見(jiàn)，由管程來(lái)實(shí)現(xiàn)后，進(jìn)程的同步更簡(jiǎn)單明了。2.5.2 利用管程解決生產(chǎn)者消費(fèi)者問(wèn)題XIA TIANPV操作與管程對(duì)比PV操作： 分散式同步機(jī)制：共享變量操作，PV操作，分散在整個(gè)系統(tǒng)中或各個(gè)進(jìn)程中。 缺點(diǎn)： 可讀性差； 正確性不易保證；

38、 不易修改。 優(yōu)點(diǎn)： 高效，靈活。管程： 集中式同步工具：共享變量及其所有相關(guān)操作集中在一個(gè)摸塊中。 優(yōu)點(diǎn)： 可讀性好； 正確性易于保證； 易于修改。 缺點(diǎn)： 不甚靈活，效率略低。XIA TIAN2.6 進(jìn)程通信概念：進(jìn)程間的信息交換。實(shí)例： 信號(hào)量機(jī)制（一種低級(jí)通信） 缺點(diǎn)： （1）效率低 （2）通信對(duì)用戶不透明 高級(jí)通信特點(diǎn)： 效率高，通信實(shí)現(xiàn)細(xì)節(jié)對(duì)用戶透明XIA TIAN2.6.1 進(jìn)程通信的類(lèi)型一、共享存貯器系統(tǒng) 1.基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式： produce-consume中的緩沖區(qū)，低效，不透明。 系統(tǒng)只提供了一共享存貯器，適于少量通信。 2.基于共享存儲(chǔ)區(qū)的通信方式： 系統(tǒng)提供

39、：共享存儲(chǔ)區(qū)。 通信過(guò)程： （1）向系統(tǒng)申請(qǐng)一個(gè)或多個(gè)分區(qū) （2）獲得分區(qū)獲后即可讀/寫(xiě). 特點(diǎn)：高效，速度快。XIA TIAN2.6.1 進(jìn)程通信的類(lèi)型二、消息傳遞系統(tǒng)（可用于異種機(jī)） 信息單位：消息（報(bào)文） 是目前的主要通信方式，分為直接通信方式、間接通信方式 實(shí)現(xiàn)：一組通信命令（原語(yǔ)），具有透明性 同步的實(shí)現(xiàn)。三、管道通信 管道：連接一個(gè)讀進(jìn)程和一個(gè)寫(xiě)進(jìn)程之間通信的共享文件。 功能：大量的數(shù)據(jù)發(fā)收。 注意： （1）互斥 （2）同步 （3）對(duì)方是否存在XIA TIAN2.6.2 消息傳遞通信的實(shí)現(xiàn)方法一、直接send(Receiver, message)receive(Sender, me

40、ssage)例：解決生產(chǎn)消費(fèi)問(wèn)題XIA TIAN2.6.2 直接/間接通信方式（消息通信的2種方式）二、間接（可以實(shí)現(xiàn)非實(shí)時(shí)通信） 優(yōu)點(diǎn)：在讀/寫(xiě)時(shí)間上的隨機(jī)性 寫(xiě)進(jìn)程 信箱（中間實(shí)體）讀進(jìn)程 原語(yǔ) （1）信箱的創(chuàng)建與撤消： 信箱名 屬性（公用、私用、共享）（共享者名字） （2）消息的發(fā)送和接收 Send (mailbox, message) Receive (mailbox, message)XIA TIAN2.6.2 直接/間接通信方式（消息通信的2種方式）二、間接（可以實(shí)現(xiàn)非實(shí)時(shí)通信） 信箱類(lèi)型 （1）私用：擁有者有讀/寫(xiě)數(shù)，其它只有寫(xiě)權(quán)，（單向）存在期進(jìn)程存在期。 （2）公用：系統(tǒng)創(chuàng)建

41、, 雙向, 存在期=系統(tǒng)存在期。 （3）共享信箱：一般進(jìn)程創(chuàng)建，并指明其共享者，是雙向。 發(fā)送接收進(jìn)程之間的關(guān)系： （1）一對(duì)一關(guān)系； （2）多對(duì)一關(guān)系；（客戶-服務(wù)器方式） （3）一對(duì)多關(guān)系；（適用于廣播方式） （4）多對(duì)多關(guān)系：公用信箱XIA TIAN2.6.3 消息傳遞系統(tǒng)中的幾個(gè)問(wèn)題一、通信鏈路： （1）顯式建立：（進(jìn)程完成、網(wǎng)絡(luò)中） （2）隱式建立：（系統(tǒng)完成、單機(jī)中） 鏈路類(lèi)型： （1）由連接方法分：點(diǎn)點(diǎn)鏈路，多點(diǎn)鏈路。 （2）由通信方式分：?jiǎn)蜗?、雙向。 （3）由容量分：無(wú)容量（無(wú)緩沖區(qū)）、有（有緩沖區(qū)）。XIA TIAN2.6.3 消息傳遞系統(tǒng)中的幾個(gè)問(wèn)題二、消息格式： 格式組成

42、 消息頭：含控制信息如：收/發(fā)進(jìn)程名，消息長(zhǎng)度、類(lèi)型、編號(hào) 消息內(nèi)容： 格式類(lèi)型 定長(zhǎng)消息：系統(tǒng)開(kāi)銷(xiāo)小，用戶不便（特別是傳長(zhǎng)消息用戶） 變長(zhǎng)消息：開(kāi)銷(xiāo)大，用戶方便。XIA TIAN2.6.3 消息傳遞系統(tǒng)中的幾個(gè)問(wèn)題三、進(jìn)程同步方式 1.發(fā)送和接收進(jìn)程阻塞（匯合） 用于緊密同步，無(wú)緩沖區(qū)時(shí)。 2.發(fā)送進(jìn)程不阻塞，接收進(jìn)程阻塞（多個(gè)） 相當(dāng)于接收進(jìn)程（可能是多個(gè)）一直等待發(fā)送進(jìn)程，如：打印進(jìn)程等待打印任務(wù)。 3.發(fā)送/接收進(jìn)程均不阻塞 一般在發(fā)、收進(jìn)程間有多個(gè)緩沖區(qū)時(shí)。XIA TIAN2.6.4 消息緩沖隊(duì)列通信機(jī)制 XIA TIAN2.6.4 消息緩沖隊(duì)列通信機(jī)制 XIA TIAN2.6.4

43、消息緩沖隊(duì)列通信機(jī)制 XIA TIAN2.6.4 消息緩沖隊(duì)列通信機(jī)制 mqmutexsmsender:Asize:5text:hellosend(B,a)sender :Asize :5text:hellonext:0發(fā)送區(qū)發(fā)送區(qū)A Asender:Asize:5text:Helloreceive(b)接收區(qū)接收區(qū)Bab進(jìn)程進(jìn)程APCB(B)進(jìn)程進(jìn)程BXIA TIAN練習(xí)試說(shuō)明如果使用send_mailbox和receive_mailbox 原語(yǔ)實(shí)現(xiàn)打印文件的系統(tǒng)。欲打印的進(jìn)程將要打印的文件名發(fā)送到郵箱printer,打印機(jī)假脫機(jī)將打印郵箱中出現(xiàn)名字的任何文件XIA TIAN/process

44、 wish to printCharfilename ;Status=send_mailbox(“printer”,filename);If (status 0) /failure/print spoolerchar filename while (true) status=receive_mailbox(“printer”,filename);if(status 0)/failureprint(filename);XIA TIAN2.7 線程XIA TIAN2.7.1 線程的基本概念(1)1.線程的引入 減少并發(fā)執(zhí)行時(shí)的時(shí)空開(kāi)銷(xiāo)，進(jìn)程的創(chuàng)建、撤消、切換較費(fèi)時(shí)空，因它既是調(diào)度單位，又是資源擁有者。 線程是系統(tǒng)獨(dú)立調(diào)度和分派的基本單位，其基本上不擁有系統(tǒng)資源，只有少量資源（寄存器，棧），但共享其所屬進(jìn)程所擁有的全部資源。XIA TIAN2.7.1 線程的基本概念(2)2.線程的屬性 輕型實(shí)體 獨(dú)立調(diào)度和分派的基本單位 可并發(fā)實(shí)體 共享進(jìn)程資源3.線程的狀態(tài) 狀態(tài)參數(shù) 寄存器狀態(tài)、堆棧、運(yùn)行狀態(tài)、優(yōu)先級(jí)、線程專(zhuān)有存儲(chǔ)器、 信號(hào)屏蔽 線程的運(yùn)行狀態(tài) 就緒、執(zhí)行、阻塞XIA TIAN2.7.1 線程的基本概念(3)4.線