chapter-2-進(jìn)程的描述與控制解析課件

1、2022/10/101內(nèi)容概述進(jìn)程管理的主要功能是把處理機(jī)分配給進(jìn)程,并對處理器運(yùn)行進(jìn)行有效地控制和管理,以及協(xié)調(diào)各個(gè)進(jìn)程之間的相互關(guān)系。2.1 前驅(qū)圖和程序執(zhí)行 2.2 進(jìn)程的描述2.3 進(jìn)程控制2.4 進(jìn)程同步2.5 經(jīng)典進(jìn)程的同步問題2.6 進(jìn)程通信2.7 線程的基本概念2.8 線程的實(shí)現(xiàn)2022/10/91內(nèi)容概述進(jìn)程管理的主要功能是把處理機(jī)分配2022/10/1022.1 前驅(qū)圖和程序執(zhí)行2.1.1 前趨圖2.1.2 程序順序執(zhí)行2.1.3 程序并發(fā)執(zhí)行2022/10/922.1 前驅(qū)圖和程序執(zhí)行2.1.1 前趨2022/10/1032.1.1 前趨圖前趨圖是一個(gè)有向無循環(huán)圖，記為D

2、AG。用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程，乃至一條語句；結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序或前趨關(guān)系“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可寫成PiPj：稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。把沒有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(Initial Node)，把沒有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(Final Node)。2022/10/932.1.1 前趨圖前趨圖是一個(gè)有向無循環(huán)2022/10/104 每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的

3、程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。 圖2-1 前趨圖 直接前趨直接后繼初始結(jié)點(diǎn)終止結(jié)點(diǎn)2022/10/94 每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(W2022/10/105對于圖 2-1(a)所示的前趨圖,存在下述前趨關(guān)系P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示為: P=P1, P2, P3, P4, P5, P6, P7, P8, P9=(P1, P2),(P1, P3),(P1, P4),(P2, P5),(P3, P5),(P4, P6),(P4, P7),(P5, P8),(P6, P8),(P7, P9),(P8,

4、P9) 應(yīng)當(dāng)注意,前趨圖中必須不存在循環(huán),但在圖2-1(b)中卻有著下述的前趨關(guān)系: S2S3, S3S2 2022/10/95對于圖 2-1(a)所示的前趨圖,存在下2022/10/1062.1 進(jìn)程的基本概念2.1.1 前趨圖2.1.2 程序順序執(zhí)行2.1.3 程序并發(fā)執(zhí)行2022/10/962.1 進(jìn)程的基本概念2.1.1 前趨圖2022/10/107圖2-2 程序的順序執(zhí)行 1.程序的順序執(zhí)行僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。 S1: a:=x+y; S2: b:=a-5; S3: c:

5、=b+1;2.1.2 程序順序執(zhí)行2022/10/97圖2-2 程序的順序執(zhí)行 1.程序的順序2022/10/1082.程序順序執(zhí)行時(shí)的特征(1)順序性:處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行,只有當(dāng)上一個(gè)操作完成后,下一個(gè)操作才能執(zhí)行。(2)封閉性:程序運(yùn)行在一個(gè)封閉的環(huán)境中,即程序運(yùn)行時(shí)獨(dú)占系統(tǒng)的全部資源,這些資源的狀態(tài)只能因程序的執(zhí)行而改變,不受任何外界因素的影響。(3)可再現(xiàn)性:由于程序順序執(zhí)行的封閉性,只要程序順序執(zhí)行的初始條件和環(huán)境相同,則不論何時(shí)執(zhí)行,也不論程序執(zhí)行期間是否存在停頓,程序所得的結(jié)果也相同。結(jié)論:正由于程序順序執(zhí)行的特點(diǎn),程序員可以檢測和重現(xiàn)程序的錯誤,可以調(diào)試和

6、校正程序。2022/10/982.程序順序執(zhí)行時(shí)的特征(1)順序性:處2022/10/1092.1 進(jìn)程的基本概念2.1.1 前趨圖2.1.2 程序順序執(zhí)行2.1.3 程序并發(fā)執(zhí)行2022/10/992.1 進(jìn)程的基本概念2.1.1 前趨圖2022/10/10102.1.3 程序并發(fā)執(zhí)行1.程序的并發(fā)執(zhí)行 圖2-3 并發(fā)執(zhí)行時(shí)的前趨圖 并發(fā)輸入程序I計(jì)算程序C輸出程序P2022/10/9102.1.3 程序并發(fā)執(zhí)行1.程序的并發(fā)2022/10/1011下述四條語句的程序段: S1: a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6 圖2-4 四條語句的前趨關(guān)系什么

7、樣的程序可以并發(fā)執(zhí)行？2022/10/911下述四條語句的程序段:圖2-4 四條2022/10/10122.程序并發(fā)執(zhí)行時(shí)的特征 (1)間斷性 相互制約導(dǎo)致并發(fā)程序具有“執(zhí)行-暫停-執(zhí)行”的間斷性活動規(guī)律。(2)失去封閉性 系統(tǒng)中多道程序共享資源，資源的狀態(tài)由多個(gè)程序來改變，必然失去了程序的封閉性。(3)不可再現(xiàn)性 失去封閉性失去可再現(xiàn)性，外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復(fù)特征。2022/10/9122.程序并發(fā)執(zhí)行時(shí)的特征 (1)間斷性例如,有兩個(gè)程序A和B,它們共享一個(gè)變量N(初始值為x)。 A: N:=N+1 B: Print(N); N:=0; 程序A和B并發(fā)執(zhí)行，

8、可出現(xiàn)以下三種情況: (1)N:=N+1在Print(N)和N:=0之前,此時(shí)得到的N值分別為x+1, x+1, 0。 (2)N:=N+1在Print(N)和N:=0之后,此時(shí)得到的N值分別為x, 0, 1。 (3)N:=N+1在Print(N)和N:=0之間,此時(shí)得到的N值分別為x, x+1, 0。 2022/10/1013例如,有兩個(gè)程序A和B,它們共享一個(gè)變量N(初始值為x)。22022/10/10142.2 進(jìn)程的描述2.2.1 進(jìn)程的定義和特征2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換2.2.3 掛起狀態(tài)和進(jìn)程狀態(tài)的轉(zhuǎn)換2.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)2022/10/9142.2 進(jìn)程的描述2

9、.2.1 進(jìn)程的定2022/10/10151.進(jìn)程的定義進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程,是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。2.進(jìn)程實(shí)體的構(gòu)成(1)程序(段)：進(jìn)程要進(jìn)行的操作。(2)數(shù)據(jù)段：包括操作的數(shù)據(jù)和程序自己的變量。(3)進(jìn)程控制塊PCB(Process Control Block)：存放進(jìn)程標(biāo)識符、進(jìn)程運(yùn)行的當(dāng)前狀態(tài)、程序和數(shù)據(jù)的地址、程序運(yùn)行時(shí)的CPU環(huán)境等。2.2.1 進(jìn)程的定義和特征 2022/10/9152.2.1 進(jìn)程的定義和特征 2022/10/10162.2.1 進(jìn)程的定義和特征 2.進(jìn)程的特征 動態(tài)性：進(jìn)程是一個(gè)動態(tài)的概念，實(shí)質(zhì)上是程序的一次執(zhí)行過程。進(jìn)程具有生命期：它

10、因“創(chuàng)建”而產(chǎn)生，因“調(diào)度”而執(zhí)行，執(zhí)行時(shí)還走走停停，因“撤消”而滅亡。并發(fā)性：多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中,且能在一段時(shí)間內(nèi)同時(shí)運(yùn)行,共享系統(tǒng)資源;引入進(jìn)程實(shí)體的目的就是并發(fā)執(zhí)行。獨(dú)立性：進(jìn)程是一個(gè)能獨(dú)立運(yùn)行的基本單位，也是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位。異步性：各進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。2022/10/9162.2.1 進(jìn)程的定義和特征 2.進(jìn)程3.進(jìn)程與程序的區(qū)別進(jìn)程是動態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合，它可以復(fù)制；進(jìn)程是程序在數(shù)據(jù)集上的一次執(zhí)行。進(jìn)程是暫時(shí)的,程序是永久的：進(jìn)程是一個(gè)狀態(tài)變化的過程，有它的撤銷，程序可長久保存。進(jìn)程具有結(jié)構(gòu)特征：由程序段、數(shù)據(jù)段和

11、進(jìn)程控制塊三者組成，而程序僅是指令的有序集合,是進(jìn)程的組成部分之一。進(jìn)程與程序的對應(yīng)關(guān)系：通過多次執(zhí)行，一個(gè)程序可對應(yīng)多個(gè)進(jìn)程。2022/10/10172.2.1 進(jìn)程的定義和特征 3.進(jìn)程與程序的區(qū)別進(jìn)程是動態(tài)的，程序是靜態(tài)的：程序是有序代2022/10/10182.2 進(jìn)程的描述2.2.1 進(jìn)程的定義和特征2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換2.2.3 掛起狀態(tài)和進(jìn)程狀態(tài)的轉(zhuǎn)換（略）2.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)2022/10/9182.2 進(jìn)程的描述2.2.1 進(jìn)程的定2022/10/10191.進(jìn)程的三種基本狀態(tài)就緒(Ready)狀態(tài)：進(jìn)程已獲得除處理機(jī)外的所需資源，等待分配處理機(jī)資源；

12、只要分配CPU就可執(zhí)行。執(zhí)行(Running)狀態(tài)：處于就緒狀態(tài)的進(jìn)程一旦獲得了處理機(jī)，進(jìn)程狀態(tài)就處于執(zhí)行狀態(tài)。阻塞(Blocked)狀態(tài)(“等待”或“睡眠”)：由于進(jìn)程等待某種事件(如I/O操作或進(jìn)程同步)，在事件發(fā)生之前無法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機(jī)分配給該進(jìn)程,也無法運(yùn)行。如:請求I/O操作，申請緩沖空間等。2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換 2022/10/9191.進(jìn)程的三種基本狀態(tài)2.2.2 進(jìn)程2022/10/1020圖2-5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 1.時(shí)間片用完2.有優(yōu)先級高的進(jìn)程到來終止2.進(jìn)程的三種基本狀態(tài)的轉(zhuǎn)換2022/10/920圖2-5 進(jìn)程的三種基本狀態(tài)

13、及其轉(zhuǎn)換 3.創(chuàng)建狀態(tài)和終止?fàn)顟B(tài) 創(chuàng)建狀態(tài)：當(dāng)一個(gè)新進(jìn)程剛剛建立,還未將其放入就緒隊(duì)列時(shí)的狀態(tài)，稱為新狀態(tài)。 終止?fàn)顟B(tài)：當(dāng)一個(gè)進(jìn)程已經(jīng)正常結(jié)束或異常結(jié)束，操作系統(tǒng)已將其從系統(tǒng)隊(duì)列中移出，但尚未撤消，這時(shí)稱為終止?fàn)顟B(tài)。 2022/10/10213.創(chuàng)建狀態(tài)和終止?fàn)顟B(tài) 創(chuàng)建狀態(tài)：當(dāng)一個(gè)新進(jìn)程剛剛建立,還未2022/10/1022圖2-6 進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換 釋放2022/10/922圖2-6 進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換 2022/10/10232.2 進(jìn)程的描述2.2.1 進(jìn)程的定義和特征2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換2.2.3 掛起狀態(tài)和進(jìn)程狀態(tài)的轉(zhuǎn)換2.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)2

14、022/10/9232.2 進(jìn)程的描述2.2.1 進(jìn)程的定2022/10/1024掛起操作的引入終端用戶的請求父進(jìn)程請求負(fù)荷調(diào)節(jié)的需要操作系統(tǒng)的需要2.2.3 掛起操作和進(jìn)程狀態(tài)的轉(zhuǎn)換圖2-7 具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 2022/10/924掛起操作的引入2.2.3 掛起操作和進(jìn)2022/10/10252.2 進(jìn)程的描述2.2.1 進(jìn)程的定義和特征2.2.2 進(jìn)程的基本狀態(tài)及轉(zhuǎn)換2.2.3 掛起狀態(tài)和進(jìn)程狀態(tài)的轉(zhuǎn)換2.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu)2022/10/9252.2 進(jìn)程的描述2.2.1 進(jìn)程的定2022/10/10262.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu) 1.操作系統(tǒng)中用于管理控制的數(shù)據(jù)

15、結(jié)構(gòu) 對于每個(gè)資源和每個(gè)進(jìn)程都設(shè)置了一個(gè)數(shù)據(jù)結(jié)構(gòu)。資源信息表、進(jìn)程信息表（稱為PCB）2022/10/9262.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu) 1.2022/10/10272.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu) 2.進(jìn)程控制塊的作用 進(jìn)程控制塊的作用是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。 記錄了操作系統(tǒng)所需的,用于描述進(jìn)程情況及控制進(jìn)程運(yùn)行所需的全部信息。 PCB是進(jìn)程存在的唯一標(biāo)志。2022/10/9272.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu) 2.2022/10/102

16、82.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu) 2.進(jìn)程控制塊的作用 具體作用：作為獨(dú)立運(yùn)行基本單位的標(biāo)志能實(shí)現(xiàn)間斷性運(yùn)行方式提供進(jìn)程管理所需的信息提供進(jìn)程調(diào)度所需的信息實(shí)現(xiàn)與其它進(jìn)程的同步與通信2022/10/9282.2.4 進(jìn)程管理中的數(shù)據(jù)結(jié)構(gòu) 2.2022/10/10293.進(jìn)程控制塊中的信息 進(jìn)程標(biāo)識符 內(nèi)部標(biāo)識符和外部標(biāo)識符。 處理機(jī)狀態(tài)通用寄存器指令計(jì)數(shù)器PC程序狀態(tài)字PSW用戶棧指針 進(jìn)程調(diào)度信息進(jìn)程狀態(tài)進(jìn)程優(yōu)先級進(jìn)程調(diào)度所需的其它信息事件進(jìn)程控制信息程序和數(shù)據(jù)的地址進(jìn)程同步和通信機(jī)制資源清單鏈接指針struct pcb int id; /進(jìn)程序號 int ra; /所需資源A的數(shù)量 in

17、t rb; /所需資源B的數(shù)量 int rc; /所需資源C的數(shù)量 int ntime; /所需的時(shí)間片個(gè)數(shù) int rtime; /已經(jīng)運(yùn)行的時(shí)間片個(gè)數(shù) char state; /進(jìn)程狀態(tài) struct pcb *next; 2022/10/9293.進(jìn)程控制塊中的信息 進(jìn)程標(biāo)識符進(jìn)2022/10/1030圖2-11 PCB鏈接隊(duì)列示意圖 4.進(jìn)程控制塊的組織方式(1)線性方式(2)鏈接方式 (3)索引方式2022/10/930圖2-11 PCB鏈接隊(duì)列示意圖 4.2022/10/1031圖2-12 按索引方式組織PCB 4.進(jìn)程控制塊的組織方式(1)線性方式(2)鏈接方式 (3)索引方式2

18、022/10/931圖2-12 按索引方式組織PCB 4.內(nèi)容概述2022/10/10322.1 前驅(qū)圖和程序執(zhí)行 2.2 進(jìn)程的描述2.3 進(jìn)程控制2.4 進(jìn)程同步2.5 經(jīng)典進(jìn)程的同步問題2.6 進(jìn)程通信2.7 線程的基本概念2.8 線程的實(shí)現(xiàn)內(nèi)容概述2022/10/9322.1 前驅(qū)圖和程序執(zhí)行 2.3 進(jìn) 程 控 制主要內(nèi)容操作系統(tǒng)內(nèi)核進(jìn)程的創(chuàng)建進(jìn)程的終止進(jìn)程的阻塞與喚醒進(jìn)程的掛起與激活2.3 進(jìn) 程 控 制主要內(nèi)容操作系統(tǒng)內(nèi)核問題：現(xiàn)代操作系統(tǒng)中通常將一些與硬件緊密相關(guān)的模塊，各種常用的設(shè)備的驅(qū)動程序以及運(yùn)行頻率較高的模塊都安排在緊靠硬件的軟件層次中，將它們常駐內(nèi)存，即OS內(nèi)核。為什

19、么這樣做？便于對這些軟件進(jìn)行保護(hù)提高OS的運(yùn)行效率操作系統(tǒng)內(nèi)核問題：現(xiàn)代操作系統(tǒng)中通常將一些與硬件緊密相關(guān)的模操作系統(tǒng)內(nèi)核1.處理機(jī)執(zhí)行狀態(tài)：系統(tǒng)態(tài)和用戶態(tài)處理機(jī)的執(zhí)行狀態(tài)分系統(tǒng)態(tài)和用戶態(tài)兩種:系統(tǒng)態(tài)(管態(tài)、核心態(tài))：有較高特權(quán)，能執(zhí)行一切指令，訪問所有寄存器和存儲區(qū)。用戶態(tài)(目態(tài))：有較低特權(quán)，能執(zhí)行規(guī)定指令，訪問指定寄存器和存儲區(qū)。用戶程序運(yùn)行在用戶態(tài)，不能執(zhí)行OS指令及區(qū)域。OS內(nèi)核運(yùn)行在系統(tǒng)態(tài)，進(jìn)程控制是由OS內(nèi)核實(shí)現(xiàn)的。操作系統(tǒng)內(nèi)核1.處理機(jī)執(zhí)行狀態(tài)：系統(tǒng)態(tài)和用戶態(tài)用戶程序運(yùn)行在操作系統(tǒng)內(nèi)核2.支撐功能 中斷處理 時(shí)鐘管理 原語操作由若干條指令構(gòu)成的“原子操作”過程，在執(zhí)行期間不可中

20、斷，作為一個(gè)整體而不可分割。原子操作：一個(gè)操作中的所有動作要么全做，要么全不做。原子操作在管態(tài)下執(zhí)行，常駐內(nèi)存。原語的作用是為了實(shí)現(xiàn)進(jìn)程的通信和控制。思考：進(jìn)程控制有哪些原語操作？1.創(chuàng)建原語2.撤消原語3.阻塞原語4.喚醒原語5.掛起原語6.激活原語操作系統(tǒng)內(nèi)核2.支撐功能由若干條指令構(gòu)成的“原子操作”過程，操作系統(tǒng)內(nèi)核3.資源管理功能進(jìn)程管理存儲器管理 設(shè)備管理操作系統(tǒng)內(nèi)核3.資源管理功能2022/10/1038進(jìn)程的創(chuàng)建圖2-13 進(jìn)程樹 1.進(jìn)程的層次結(jié)構(gòu)父進(jìn)程與子進(jìn)程UNIX中進(jìn)程家族Windows中進(jìn)程句柄 2.進(jìn)程圖(Process Graph)進(jìn)程圖是用于描述一個(gè)進(jìn)程的家族關(guān)系

21、的有向樹，樹中的結(jié)點(diǎn)表示進(jìn)程。子進(jìn)程可以繼承父進(jìn)程的資源。撤消父進(jìn)程時(shí)必須同時(shí)撤消子進(jìn)程2022/10/938進(jìn)程的創(chuàng)建圖2-13 進(jìn)程樹 1.進(jìn)程2022/10/10393.引起創(chuàng)建進(jìn)程的事件用戶登錄作業(yè)調(diào)度提供服務(wù)應(yīng)用請求 進(jìn)程的創(chuàng)建2022/10/9393.引起創(chuàng)建進(jìn)程的事件進(jìn)程的創(chuàng)建2022/10/10404.進(jìn)程的創(chuàng)建申請空白PCB 為新進(jìn)程分配資源 初始化進(jìn)程控制塊 將新進(jìn)程插入就緒隊(duì)列進(jìn)程的創(chuàng)建2022/10/9404.進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建2022/10/1041進(jìn)程的終止 1.引起進(jìn)程終止的事件正常結(jié)束異常結(jié)束外界干預(yù)2022/10/941進(jìn)程的終止 1.引起進(jìn)程終止的事件20

22、22/10/10422.進(jìn)程的終止過程 (1)從PCB集合中檢索出該進(jìn)程的PCB, 讀出該進(jìn)程的狀態(tài)。 (2)若被終止進(jìn)程正處于執(zhí)行狀態(tài),應(yīng)立即終止該進(jìn)程的執(zhí)行。 (3)若該進(jìn)程還有子孫進(jìn)程,應(yīng)將其所有子孫進(jìn)程予以終止。 (4)將被終止進(jìn)程所擁有的全部資源, 歸還給其父進(jìn)程, 或者歸還給系統(tǒng)。 (5)將被終止進(jìn)程(它的PCB)從所在隊(duì)列(或鏈表)中移出,等待其他程序來搜集信息。 進(jìn)程的終止 2022/10/9422.進(jìn)程的終止過程進(jìn)程的終止 2022/10/1043進(jìn)程的阻塞與喚醒1.引起進(jìn)程阻塞和喚醒的事件 請求系統(tǒng)服務(wù) 啟動某種操作 新數(shù)據(jù)尚未到達(dá) 無新工作可做2022/10/943進(jìn)程的

23、阻塞與喚醒1.引起進(jìn)程阻塞和喚醒2022/10/1044 2.進(jìn)程阻塞過程進(jìn)程調(diào)用阻塞原語block()把自己阻塞，立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞，并將PCB插入阻塞隊(duì)列。將本進(jìn)程插入到具有相同事件的阻塞(等待)隊(duì)列。調(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)程的阻塞與喚醒2022/10/944 2.進(jìn)程阻塞過程進(jìn)程的阻塞與喚醒2022/10/1045 3.進(jìn)程喚醒過程調(diào)用喚醒原語wakeup( )將等待該事件的進(jìn)程喚醒。喚醒原語執(zhí)行的過程是把被阻塞

24、的進(jìn)程從等待該事件的阻塞隊(duì)列中移出將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒將該P(yáng)CB插入到就緒隊(duì)列中進(jìn)程的阻塞與喚醒2022/10/945 3.進(jìn)程喚醒過程進(jìn)程的阻塞與喚醒2022/10/1046進(jìn)程的掛起與激活 1.進(jìn)程的掛起系統(tǒng)將利用掛起原語suspend( )將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。suspend()原語的執(zhí)行過程首先檢查被掛起進(jìn)程的狀態(tài)，若處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)的進(jìn)程，則將之改為靜止阻塞。把該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域。若被掛起的進(jìn)程正在執(zhí)行,則轉(zhuǎn)向調(diào)度程序重新調(diào)度。2022/10/946進(jìn)程的掛起與激活 1.進(jìn)程的掛起2022/10/1

25、047 2.進(jìn)程的激活過程系統(tǒng)將利用激活原語active( )將指定進(jìn)程激活。active()原語執(zhí)行過程將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)，若是靜止就緒，將之改為活動就緒；若為靜止阻塞便將之改為活動阻塞。假如采用的是搶占調(diào)度策略，則每當(dāng)有新進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，應(yīng)檢查是否要進(jìn)行重新調(diào)度，即由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行優(yōu)先級的比較，如果被激活進(jìn)程的優(yōu)先級更低，就不必重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運(yùn)行，把處理機(jī)分配給剛被激活的進(jìn)程。進(jìn)程的掛起與激活 2022/10/947 2.進(jìn)程的激活過程進(jìn)程的掛起與激活2022/10/10481.引起進(jìn)程創(chuàng)建的主要事件？2.在創(chuàng)建一個(gè)進(jìn)程時(shí)

26、所需要完成的主要工作是什么？3.在撤消一個(gè)進(jìn)程時(shí)所要完成的主要工作是什么？課后思考題 2022/10/9481.引起進(jìn)程創(chuàng)建的主要事件？課后思考題內(nèi)容概述2022/10/10492.1 前驅(qū)圖和程序執(zhí)行 2.2 進(jìn)程的描述2.3 進(jìn)程控制2.4 進(jìn)程同步2.5 經(jīng)典進(jìn)程的同步問題2.6 進(jìn)程通信2.7 線程的基本概念2.8 線程的實(shí)現(xiàn)內(nèi)容概述2022/10/9492.1 前驅(qū)圖和程序執(zhí)行 2.4 進(jìn)程同步 進(jìn)程同步的主要任務(wù)是對多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，以使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。2.4.1 進(jìn)程同步的基本概念2.4.2 硬件同步機(jī)

27、制2.4.3 信號量機(jī)制2.4.4 信號量的應(yīng)用2.4.5 管程機(jī)制2022/10/10502.4 進(jìn)程同步 進(jìn)程同步的主要任務(wù)是對多個(gè)相關(guān)進(jìn)程在執(zhí)行2022/10/10512.4.1 進(jìn)程同步的基本概念1.兩種形式的制約關(guān)系(1)間接相互制約關(guān)系 源于資源共享。如A、B共享打印機(jī)，若A申請打印時(shí)，打印機(jī)已分配給B，則A只能阻塞，等B釋放后再改為就緒，又稱為“互斥”。(2)直接相互制約關(guān)系 源于進(jìn)程之間的合作關(guān)系。如進(jìn)程A向B提供數(shù)據(jù)，當(dāng)輸入緩沖空時(shí)，B不能得到數(shù)據(jù)而阻塞；反之當(dāng)緩沖滿時(shí)，A無法寫入而阻塞，又稱為“同步”。2022/10/9512.4.1 進(jìn)程同步的基本概念1.兩種2.臨界資源

28、定義:在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源。例如:打印機(jī)、磁帶機(jī)、卡片輸入機(jī)、變量、表格、數(shù)據(jù)、 指針、數(shù)組等。進(jìn)程之間采取互斥方式實(shí)現(xiàn)對這些資源的共享。2022/10/1052例子： 生產(chǎn)者-消費(fèi)者(producer-consumer)問題是一個(gè)著名的進(jìn)程同步問題。有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，提供給消費(fèi)者進(jìn)程去消費(fèi)。不能向滿緩沖區(qū)投放產(chǎn)品，不能從空緩沖區(qū)中取產(chǎn)品。2.4.1 進(jìn)程同步的基本概念2.臨界資源2022/10/952例子：2.4.1 進(jìn)程同步2022/10/1053 一個(gè)數(shù)組緩沖池，有n個(gè)緩沖區(qū)。 buffer:array0, 1, , n-1 of item 輸入指針in in=

29、(in+1)mod n。 輸出指針out out=(out+1) mod n。 counter：初始值為0, 緩沖池中含有的產(chǎn)品數(shù)目。0 1 n-1 ninout 2022/10/953 一個(gè)數(shù)組緩沖池，有n個(gè)緩沖區(qū)。0 2022/10/1054producer: repeat 生產(chǎn)者進(jìn)程 produce an item in nextp;/生產(chǎn)一個(gè)產(chǎn)品 while counter=n do no-op; bufferin =nextp;/將產(chǎn)品放入緩沖區(qū)內(nèi) in =in+1 mod n; counter =counter+1; /緩沖池中產(chǎn)品數(shù)加一 until false;consumer:

30、 repeat 消費(fèi)者進(jìn)程 while counter=0 do no-op; nextc =bufferout;/從緩沖區(qū)中消費(fèi)產(chǎn)品 out =(out+1) mod n; counter = counter-1; /緩沖池中產(chǎn)品數(shù)減一 consumer the item in nextc;/消費(fèi)一個(gè)產(chǎn)品 until false; 2022/10/954producer: repeat 生2022/10/1055 雖然上面的生產(chǎn)者程序和消費(fèi)者程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會是正確的，但若并發(fā)執(zhí)行時(shí)，就會出現(xiàn)差錯，問題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對它

31、做加1操作，消費(fèi)者對它做減1操作，這兩個(gè)操作在用機(jī)器語言實(shí)現(xiàn)時(shí)， ?？捎孟旅娴男问矫枋觯簉egister1=counter; register2=counter;register1=register1+1; register2=register2-1;counter=register1; counter=register2; 2022/10/955 雖然上面的生產(chǎn)者程序和2022/10/1056 假設(shè)：counter的當(dāng)前值是5。如果生產(chǎn)者進(jìn)程先執(zhí)行左列的三條機(jī)器語言語句，然后消費(fèi)者進(jìn)程再執(zhí)行右列的三條語句，則最后共享變量counter的值仍為5；反之，如果讓消費(fèi)者進(jìn)程先執(zhí)行右列的三條語句，然

32、后再讓生產(chǎn)者進(jìn)程執(zhí)行左列的三條語句，counter值也還是5，但是，如果按下述順序執(zhí)行，counter值是4。由于并發(fā)執(zhí)行而失去封閉性。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) 共享資源的訪問互斥2022/10/956 假設(shè)：counter的當(dāng)3.

33、臨界區(qū)不論是硬件臨界資源還是軟件臨界資源，多個(gè)進(jìn)程必須互斥地對它進(jìn)行訪問。在每個(gè)進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。每個(gè)進(jìn)程進(jìn)入臨界區(qū)之前應(yīng)先對欲訪問的臨界資源進(jìn)行檢查，看是否正在被訪問。如果此刻該臨界資源未被訪問，該進(jìn)程可進(jìn)入臨界區(qū),并設(shè)置它正在被訪問的標(biāo)志，在臨界區(qū)之前執(zhí)行的這段代碼稱為進(jìn)入?yún)^(qū)。在臨界區(qū)后面也要加上一段代碼，用于將臨界區(qū)被訪問的資源恢復(fù)為未被訪問的標(biāo)志，稱為退出區(qū)。2022/10/10573.臨界區(qū)不論是硬件臨界資源還是軟件臨界資源，多個(gè)進(jìn)程必須互2022/10/1058可把一個(gè)訪問臨界資源的循環(huán)進(jìn)程描述如下:repeat critical section;臨界區(qū) re

34、mainder section;剩余區(qū)until false; entry sectionexit section進(jìn)入?yún)^(qū)退出區(qū)2022/10/958可把一個(gè)訪問臨界資源的循環(huán)進(jìn)程描述如下2022/10/10594.同步機(jī)制應(yīng)遵循的規(guī)則(1)空閑讓進(jìn)：當(dāng)無進(jìn)程處于臨界區(qū)時(shí),應(yīng)允許一個(gè)進(jìn)程進(jìn)入臨界區(qū),以有效利用臨界資源。(2)忙則等待：當(dāng)有進(jìn)程進(jìn)入臨界區(qū)時(shí),其他進(jìn)程必須等待。(3)有限等待：對要求訪問臨界資源的進(jìn)程,應(yīng)保證在有限時(shí)間內(nèi)進(jìn)入自己的臨界區(qū),防止“死等”。(4)讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入其臨界區(qū)時(shí),應(yīng)立即釋放處理機(jī),防止“忙等”,不能一直用語句判斷能不能進(jìn),占用處理機(jī)。2022/10/95

35、94.同步機(jī)制應(yīng)遵循的規(guī)則2.4.2 硬件同步機(jī)制采用軟件方法實(shí)現(xiàn)進(jìn)程互斥使用臨界資源是很困難的，它們通常能實(shí)現(xiàn)兩個(gè)進(jìn)程的互斥，很難控制多個(gè)進(jìn)程的互斥。算法設(shè)計(jì)需要非常小心，否則可能出現(xiàn)死鎖，或互斥失敗等嚴(yán)重問題。軟件方法始終不能解決“忙等”現(xiàn)象，降低系統(tǒng)效率。硬件方法包括屏蔽中斷和專用機(jī)器指令。2.4.2 硬件同步機(jī)制2.4.2 硬件同步機(jī)制-屏蔽中斷由于進(jìn)程切換需要依賴中斷來實(shí)現(xiàn)，如果屏蔽中斷，則不會出現(xiàn)進(jìn)程切換。因此，為了實(shí)現(xiàn)對臨界資源的互斥使用，可以在進(jìn)程進(jìn)入臨界區(qū)之前，屏蔽中斷,當(dāng)進(jìn)程退出臨界區(qū)時(shí)，打開系統(tǒng)中斷。中斷被屏蔽以后，系統(tǒng)時(shí)鐘中斷也被屏蔽。處理機(jī)將不會被切換到其他進(jìn)程。于是

36、，一旦屏蔽中斷，進(jìn)程就可以檢查和修改共享內(nèi)存區(qū)中的數(shù)據(jù)，而不必?fù)?dān)心其他進(jìn)程介入。其偽代碼如下： 2.4.2 硬件同步機(jī)制-屏蔽中斷由于進(jìn)程切換需要依賴中斷來2.4.2 硬件同步機(jī)制-屏蔽中斷repeat ; ; ; forever.2.4.2 硬件同步機(jī)制-屏蔽中斷repeat2.4.2 硬件同步機(jī)制-屏蔽中斷這種方法約束條件太強(qiáng)，付出的代價(jià)太大因?yàn)橹袛啾黄帘我院螅到y(tǒng)將無法響應(yīng)任何外部請求，也不會響應(yīng)當(dāng)前執(zhí)行進(jìn)程的任何異常及系統(tǒng)故障，嚴(yán)重地降低了處理機(jī)性能。這種方法僅對單處理機(jī)系統(tǒng)有效，如果系統(tǒng)有兩個(gè)或多個(gè)共享內(nèi)存的處理機(jī)，屏蔽中斷僅僅對執(zhí)行本指令的處理機(jī)有效，其它處理機(jī)仍將繼續(xù)運(yùn)行，并可以

37、訪問共享內(nèi)存空間。 2.4.2 硬件同步機(jī)制-屏蔽中斷這種方法約束條件太強(qiáng)，付出2.4.2 硬件同步機(jī)制-專用機(jī)器指令利用一些專用機(jī)器指令也能實(shí)現(xiàn)互斥，機(jī)器指令在一個(gè)指令周期內(nèi)執(zhí)行，不會受到其它指令的干擾，也不會被中斷。Test and Set指令就是較常用的一種機(jī)器指令，其定義如下： 2.4.2 硬件同步機(jī)制-專用機(jī)器指令2.4.2 硬件同步機(jī)制-專用機(jī)器指令TestAndSet指令：這條指令是原子操作，即執(zhí)行該代碼時(shí)不允許被中斷。其功能是讀出指定標(biāo)志后把該標(biāo)志設(shè)置為真。指令的功能描述為：Boolean TestAndSet(Boolean *lock) Boolean old； old=*

38、lock； *lock=true； return old； while TestAndSet(&lock)；進(jìn)程的臨界區(qū)代碼；lock=false；進(jìn)程的其他代碼；2.4.2 硬件同步機(jī)制-專用機(jī)器指令TestAndSet指2.4.2 硬件同步機(jī)制-專用機(jī)器指令Swap指令：該指令的功能是交換兩個(gè)字節(jié)的內(nèi)容。其功能描述如下。Swap(boolean *a, boolean *b) boolean temp;Temp=*a;*a = *b;*b = temp;2.4.2 硬件同步機(jī)制-專用機(jī)器指令Swap指令：該指令的2.4.2 硬件同步機(jī)制-專用機(jī)器指令應(yīng)為每個(gè)臨界資源設(shè)置了一個(gè)共享布爾變量l

39、ock，初值為false；在每個(gè)進(jìn)程中再設(shè)置一個(gè)局部布爾變量key，用于與lock交換信息。在進(jìn)入臨界區(qū)之前先利用Swap指令交換lock與key的內(nèi)容，然后檢查key的狀態(tài)；有進(jìn)程在臨界區(qū)時(shí)，重復(fù)交換和檢查過程，直到進(jìn)程退出。利用Swap指令實(shí)現(xiàn)進(jìn)程互斥的算法描述如下：key=true;while(key!=false)Swap(&lock, &key); / 進(jìn)程的臨界區(qū)代碼段；lock=false;/ 進(jìn)程的其他代碼；2.4.2 硬件同步機(jī)制-專用機(jī)器指令應(yīng)為每個(gè)臨界資源設(shè)置了機(jī)器指令優(yōu)點(diǎn)非常簡單，易于證明；同時(shí)適合于單處理機(jī)系統(tǒng)和共享內(nèi)存的多處理機(jī)系統(tǒng)中多個(gè)進(jìn)程的互斥；可以分別為臨界區(qū)

40、設(shè)置屬于它自己的變量，以實(shí)現(xiàn)對多個(gè)臨界區(qū)的互斥訪問。 機(jī)器指令優(yōu)點(diǎn)機(jī)器指令缺點(diǎn) “忙等” 現(xiàn)象仍然存在。進(jìn)程都需要循環(huán)檢測，等待時(shí)機(jī)進(jìn)入臨界區(qū)。但是，由于采用了機(jī)器指令，這種“忙等”消耗的機(jī)器時(shí)間比軟件方法小，屬于“可接受的忙等”。可能出現(xiàn)饑餓現(xiàn)象。當(dāng)臨界區(qū)空閑時(shí)，執(zhí)行循環(huán)檢測的若干等待進(jìn)程能進(jìn)入臨界區(qū)的機(jī)率是相等的，有的進(jìn)程可能“運(yùn)氣”非常不好，很難有機(jī)會進(jìn)入臨界區(qū)，而饑餓。機(jī)器指令缺點(diǎn) “忙等” 現(xiàn)象仍然存在。進(jìn)程都需要循環(huán)檢測，等機(jī)器指令缺點(diǎn)還有可能導(dǎo)致死鎖。例如，進(jìn)程P1的優(yōu)先級低于P2的優(yōu)先級，若P1通過執(zhí)行專用機(jī)器指令，進(jìn)入臨界區(qū)，且在臨界區(qū)內(nèi)被中斷，P2被調(diào)度執(zhí)行。若P2也需要進(jìn)

41、入該臨界區(qū)，由于臨界區(qū)被P1占用，P2 “忙等” 。由于P1的優(yōu)先級低于P2，調(diào)度程序不可能強(qiáng)行剝奪P2的執(zhí)行而調(diào)度P1。這樣，P1將一直占用臨界區(qū)被中斷，P2一直“忙等”，如果沒有外力的作用，這種“僵持”狀態(tài)將一直保持下去，即系統(tǒng)出現(xiàn)死鎖。 機(jī)器指令缺點(diǎn)還有可能導(dǎo)致死鎖。1965年,荷蘭學(xué)者Dijkstra提出的信號量(Semaphores)機(jī)制是一種有效的進(jìn)程同步工具，所以P、V分別是荷蘭語的test(proberen)和increment(verhogen)。信號量機(jī)制已從整型信號量發(fā)展為記錄型信號量、AND型信號量，又進(jìn)一步發(fā)展為信號量集。信號量就是OS提供的管理公有資源的有效手段。信

42、號量代表可用資源實(shí)體的數(shù)量。物理意義2022/10/10712.4.3 信號量機(jī)制 1965年,荷蘭學(xué)者Dijkstra提出的信號量(Semap2022/10/10721.整型信號量除初始化外，僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作wait(S)和signal(S)來訪問。也稱為P、V操作。wait和signal操作可描述為:wait(S): while S0 do no-op; S:=S-1;signal(S): S:=S+1; wait(S)和signal(S)是原子操作，因此它們在執(zhí)行時(shí)是不可中斷的。另外，信號量只能通過原語操作來訪問，不能被進(jìn)程調(diào)度所打斷。有“忙等”現(xiàn)象。2022/10/9721.

43、整型信號量2022/10/1073可把一個(gè)訪問臨界資源的循環(huán)進(jìn)程描述如下:repeat critical section; 臨界區(qū) remainder section; 剩余區(qū)until false; entry sectionexit sectionP(S)或wait(S);V(S)或signal(S);進(jìn)入?yún)^(qū)退出區(qū)1.整型信號量2022/10/973可把一個(gè)訪問臨界資源的循環(huán)進(jìn)程描述如下2022/10/10742.記錄型信號量記錄型信號量（也稱資源信號量）機(jī)制，則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制，它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)。在采取了“讓權(quán)等待”的策略后，又會出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界

44、資源的情況。為此，在信號量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表L，用于鏈接上述的所有等待進(jìn)程。2022/10/9742.記錄型信號量2022/10/1075type semaphore=record value: integer; /資源數(shù)目 L: list of process;/進(jìn)程鏈表指針 endprocedure wait(S) var S: semaphore; begin S.value:=S.value-1; if S.value0 then block(S.L); end procedure signal(S) var S: sema

45、phore; begin S.value:=S.value+1; if S.value0 then wakeup(S.L); end 請求一個(gè)單位的該類資源該類資源數(shù)減少一個(gè)自我阻塞，放棄處理機(jī)釋放一個(gè)單位資源該類資源增加一個(gè)喚醒進(jìn)程2022/10/975type semaphore=reco2022/10/10763.AND型信號量 在有些任務(wù)中,一個(gè)進(jìn)程先要獲得多個(gè)共享資源后才能執(zhí)行，若進(jìn)程A和B都要申請D和E兩種資源，設(shè)信號量Dmutex和Emutex的初值均為1在兩個(gè)進(jìn)程中都要包含兩個(gè)對Dmutex和Emutex的操作，即process A: process B: P(Dmutex);

46、 P(Emutex); P(Emutex); P(Dmutex);若進(jìn)程A和B按下述次序交替執(zhí)行P操作: process A: P(Dmutex); 于是Dmutex=0 process B: P(Emutex); 于是Emutex=0 process A: P(Emutex); 于是Emutex=-1 A阻塞 process B: P(Dmutex); 于是Dmutex=-1 B阻塞 2022/10/9763.AND型信號量 在有些任務(wù)2022/10/1077 AND同步機(jī)制的基本思想是:將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源,一次性全部地分配給進(jìn)程,待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源

47、未能分配給進(jìn)程,其它所有可能為之分配的資源,也不分配給他。亦即,對若干個(gè)臨界資源的分配,采取原子操作方式:要么全部分配到進(jìn)程,要么一個(gè)也不分配。由死鎖理論可知,這樣就可避免上述死鎖情況的發(fā)生。為此,在P操作中,增加了一個(gè)“AND”條件,故稱為AND同步,或稱為同時(shí)P操作, 即SP(Simultaneous wait)定義如下: 3.AND型信號量 2022/10/977 AND同步機(jī)制的基本思想是:將2022/10/1078SP:Swait(S1, S2, , Sn) if Si1 and and Sn1 then 每個(gè)資源都可用 for i: =1 to n do Si:=Si-1; 分配所

48、有資源 endfor else 否則,將進(jìn)程放到等待資源Si的隊(duì)列中 “阻塞”(去第1個(gè)Si1的“等待Si”的阻塞隊(duì)列中排隊(duì),并置它的程序計(jì)數(shù)器于SP操作的起始點(diǎn)) endifSV:Ssignal(S1, S2, , Sn) for i: =1 to n do Si=Si+1; 釋放所有資源 “喚醒”(所有“等待Si”的阻塞進(jìn)程,置為“就緒”狀態(tài),移到就緒隊(duì)列中) endfor; 2022/10/978SP:Swait(S1, S2, ,4.信號量集:一次申請多個(gè)資源在記錄型信號量機(jī)制中,P(S)和V(S)操作僅能對信號量施以加1或減1操作,意味著每次只能獲得或釋放一個(gè)單位的臨界資源,效率較低

49、。在有些情況下,當(dāng)資源數(shù)量低于某下限值時(shí)便不予分配。因而,在每次分配之前,都必須測試該資源的數(shù)量,看其是否大于下限值。在對AND型信號量機(jī)制擴(kuò)充的基礎(chǔ)上,形成一般化的“信號量集”機(jī)制。2022/10/10794.信號量集:一次申請多個(gè)資源在記錄型信號量機(jī)制中,P(S)2022/10/1080SP:Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i:=1 to n do Si:=Si-di; 一次分配d個(gè)資源 endfor else “阻塞”(去第1個(gè)Sinextp; P(empty); empty減1 P(mutex)

50、; buffer(in):=nextp; in:=(in+1)mod n; 移動生產(chǎn)指針 V(mutex); V(full); full增1 until false; end consumer: 消費(fèi)者進(jìn)程 begin repeat P(full); P(mutex); nextc: =buffer(out); out:=(out+1) mod n; V(mutex); V(empty); 消費(fèi)nextc中的一條消息; until false; end parendend 2022/10/994Var mutex, empty, f2022/10/1095在生產(chǎn)者消費(fèi)者問題中要注意以下幾點(diǎn)：在

51、每個(gè)程序中用于實(shí)現(xiàn)互斥的P(mutex)和V(mutex)必須成對地出現(xiàn)；對資源信號量empty和full的P和V操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如,P(empty)在計(jì)算進(jìn)程中,而V(empty)則在打印進(jìn)程中,計(jì)算進(jìn)程若因執(zhí)行P(empty)而阻塞, 則以后將由打印進(jìn)程將它喚醒；在每個(gè)程序中的多個(gè)P操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的P操作，然后再執(zhí)行對互斥信號量的P操作，否則可能引起進(jìn)程死鎖。2022/10/995在生產(chǎn)者消費(fèi)者問題中要注意以下幾點(diǎn)：2022/10/10962.利用AND信號量解決生產(chǎn)者消費(fèi)者問題 Var mutex, empty, full:

52、semaphore:=1, n, 0; buffer:array0, , n-1 of item; in out:integer:=0, 0; begin parbegin producer: begin repeat 生產(chǎn)一條消息=nextp; SP(empty, mutex); buffer(in):=nextp; in:=(in+1)mod n; SV(mutex, full); until false; end consumer: begin repeat SP(full, mutex); nextc:=buffer(out); out:=(out+1) mod n; SV(mutex

53、, empty); 消費(fèi)nextc中的一條消息; until false; end parendend2022/10/9962.利用AND信號量解決生產(chǎn)者消費(fèi)者2.5 經(jīng)典進(jìn)程的同步問題 2.5.1 生產(chǎn)者消費(fèi)者問題2.5.2 哲學(xué)家進(jìn)餐問題2.5.3 讀者寫者問題2022/10/10972.5 經(jīng)典進(jìn)程的同步問題 2.5.1 生產(chǎn)者消費(fèi)者問題2.5.2 哲學(xué)家進(jìn)餐問題 哲學(xué)家進(jìn)餐問題(The Dinning Philosophers Problem)是由Dijkstra提出并解決的典型進(jìn)程同步問題。 問題描述:5個(gè)哲學(xué)家坐在桌子邊,桌上有5個(gè)碗和5支筷子。哲學(xué)家的生活方式交替地進(jìn)行思考和進(jìn)餐

54、。哲學(xué)家饑餓時(shí)便拿起兩邊的筷子進(jìn)餐,但只有當(dāng)拿到兩支后才能進(jìn)餐。用餐畢,放下筷子。2022/10/10982.5.2 哲學(xué)家進(jìn)餐問題 哲學(xué)家進(jìn)餐問題(Th2022/10/10991.利用記錄型信號量解決哲學(xué)家進(jìn)餐問題 經(jīng)分析可知,放在桌子上的筷子是臨界資源,在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對筷子的互斥使用,可以用一個(gè)信號量表示一只筷子,由這五個(gè)信號量構(gòu)成信號量數(shù)組。其描述如下:2022/10/9991.利用記錄型信號量解決哲學(xué)家進(jìn)餐問題2022/10/10100Var chopstick: array0, , 4of semaphore:=(1,1,1,1,1);begin repe

55、at P(chopsticki); P(chopstick(i+1) mod 5); eat;進(jìn)餐 V(chopsticki); V(chopstick(i+1) mod 5); think;思考 until false; end問題: 每個(gè)哲學(xué)家都拿起左邊的筷子等待右邊的筷子，結(jié)果誰也得不到兩把筷子，形成了死鎖。10234104322022/10/9100Var chopstick: arr2022/10/101012.利用AND信號量機(jī)制解決哲學(xué)家進(jìn)餐問題 在哲學(xué)家進(jìn)餐問題中,要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐,這在本質(zhì)上就是前面所介紹的AND同步問題,故用AND信號量機(jī)制

56、可獲得最簡潔的解法。Var chopstick array 0, , 4 of semaphore:=(1,1,1,1,1); process i repeat SP(chopstick(i+1) mod 5, chopsticki); eat; SV(chopstick(i+1) mod 5, chopsticki); think; until false; 2022/10/91012.利用AND信號量機(jī)制解決哲學(xué)家進(jìn)2.5 經(jīng)典進(jìn)程的同步問題 2.5.1 生產(chǎn)者消費(fèi)者問題2.5.2 哲學(xué)家進(jìn)餐問題2.5.3 讀者寫者問題2022/10/101022.5 經(jīng)典進(jìn)程的同步問題 2.5.1 生產(chǎn)

57、者消費(fèi)者問題2.5.3 讀者-寫者問題 一個(gè)數(shù)據(jù)文件或記錄可被多個(gè)進(jìn)程共享，把只要求讀該文件的進(jìn)程稱為“Reader進(jìn)程”，其他進(jìn)程稱為“Writer進(jìn)程”允許多個(gè)進(jìn)程同時(shí)讀一個(gè)共享對象，因?yàn)樽x不會使數(shù)據(jù)文件混亂。不允許一個(gè)Writer進(jìn)程和其他Reader進(jìn)程或Writer進(jìn)程同時(shí)訪問一個(gè)對象。讀者寫者問題是指保證一個(gè)Writer進(jìn)程必須與其他進(jìn)程互斥地訪問共享對象的同步問題。2022/10/101032.5.3 讀者-寫者問題 一個(gè)數(shù)據(jù)文件或記錄可被多個(gè)進(jìn)程共2022/10/101041.利用記錄型信號量解決讀者-寫者問題設(shè)置兩個(gè)信號量：讀互斥信號量rmutex和寫互斥信號量wmutex。

58、另外設(shè)立一個(gè)讀計(jì)數(shù)器readcount表示正在讀的進(jìn)程數(shù)目，它是一個(gè)整型變量，初值為0。wmutex：用于實(shí)現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r(shí)的互斥,初值為1。 rmutex：用于讀者互斥地訪問readcount，初值為1。2022/10/91041.利用記錄型信號量解決讀者-寫者問2022/10/10105讀者-寫者問題可描述如下:Var rmutex, wmutex:semaphore:=1,1; readcount:integer:=0; begin parbegin Reader:begin repeat P(rmutex); if readcount=0 then P(wm

59、utex); readcount:=readcount+1; V(rmutex); perform read operation; P(rmutex); readcount:=readcount-1; if readcount=0 then V(wmutex); V(rmutex); until false; end writer:begin repeat P(wmutex); perform write operation; V(wmutex); until false; end parendend2022/10/9105讀者-寫者問題可描述如下: 2022/10/101062.利用信號量集

60、機(jī)制解決讀者-寫者問題 Var RN integer; L, mx:semaphore:=RN,1; begin parbegin reader:begin repeat SP(L,1,1); SP(mx,1,0); perform read operation; SV(L,1); until false; end writer:begin repeat SP(mx,1,1; L,RN,0); perform write operation; SV(mx,1); until false; end parend end 2022/10/91062.利用信號量集機(jī)制解決讀者-寫者問進(jìn)程通信 OS可