第二章進(jìn)程管理

1、2022-3-1912022-3-192內(nèi)容概述內(nèi)容概述2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 2.2 2.2 進(jìn)程控制進(jìn)程控制 2.3 2.3 進(jìn)程同步進(jìn)程同步 2.4 2.4 經(jīng)典進(jìn)程的同步問題經(jīng)典進(jìn)程的同步問題 2.5 2.5 進(jìn)程通信進(jìn)程通信 2.6 2.6 線程線程 進(jìn)程管理的進(jìn)程管理的主要功能主要功能是把處理機(jī)分配給進(jìn)程是把處理機(jī)分配給進(jìn)程,并對(duì)處理器運(yùn)并對(duì)處理器運(yùn)行進(jìn)行有效地控制和管理行進(jìn)行有效地控制和管理,以及協(xié)調(diào)各個(gè)進(jìn)程之間的相互關(guān)系。以及協(xié)調(diào)各個(gè)進(jìn)程之間的相互關(guān)系。2022-3-1932.1.1 2.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征2.1.2 2.

2、1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征2.1.4 2.1.4 進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài)2.1.5 2.1.5 進(jìn)程控制塊進(jìn)程控制塊2022-3-194圖圖2-1 2-1 程序的順序執(zhí)行程序的順序執(zhí)行 1.程序的順序執(zhí)行程序的順序執(zhí)行僅當(dāng)前一操作僅當(dāng)前一操作(程序段程序段)執(zhí)行完后，才能執(zhí)行后繼操作。執(zhí)行完后，才能執(zhí)行后繼操作。例如例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。計(jì)算，最后才能打印計(jì)算結(jié)果。 S1: a:=x+y; S2: b:=a-5;

3、 S3: c:=b+1;2.1.1 2.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征2022-3-1952.2.程序順序執(zhí)行時(shí)的特征程序順序執(zhí)行時(shí)的特征(1)(1)順序性順序性: :處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行, ,只有當(dāng)上一個(gè)操作完成后只有當(dāng)上一個(gè)操作完成后, ,下一個(gè)操作才能執(zhí)行。下一個(gè)操作才能執(zhí)行。(2)(2)封閉性封閉性: :程序運(yùn)行在一個(gè)封閉的環(huán)境中程序運(yùn)行在一個(gè)封閉的環(huán)境中, ,即程序運(yùn)行時(shí)獨(dú)即程序運(yùn)行時(shí)獨(dú)占系統(tǒng)的全部資源占系統(tǒng)的全部資源, ,這些資源的狀態(tài)只能因程序的執(zhí)行而改這些資源的狀態(tài)只能因程序的執(zhí)行而改變變, ,不

4、受任何外界因素的影響。不受任何外界因素的影響。(3)(3)可再現(xiàn)性可再現(xiàn)性: :由于程序順序執(zhí)行的封閉性由于程序順序執(zhí)行的封閉性, ,只要程序順序執(zhí)只要程序順序執(zhí)行的行的初始條件和環(huán)境相同初始條件和環(huán)境相同, ,則不論何時(shí)執(zhí)行則不論何時(shí)執(zhí)行, ,也不論程序執(zhí)也不論程序執(zhí)行期間是否存在停頓行期間是否存在停頓, ,程序所得的程序所得的結(jié)果結(jié)果也也相同相同。結(jié)論結(jié)論: :正由于程序順序執(zhí)行的特點(diǎn)正由于程序順序執(zhí)行的特點(diǎn), ,程序員可以檢測和重現(xiàn)程序員可以檢測和重現(xiàn)程序的錯(cuò)誤程序的錯(cuò)誤, ,可以調(diào)試和校正程序?？梢哉{(diào)試和校正程序。2022-3-1962.1.1 2.1.1 程序的順序執(zhí)行及其特征程序的

5、順序執(zhí)行及其特征2.1.2 2.1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征2.1.4 2.1.4 進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài)2.1.5 2.1.5 進(jìn)程控制塊進(jìn)程控制塊2022-3-1972.1.2 2.1.2 前趨圖前趨圖(Precedence Graph)(Precedence Graph) 前趨圖是一個(gè)有向前趨圖是一個(gè)有向無循環(huán)無循環(huán)圖，記為圖，記為DAG。用于描述進(jìn)程之。用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。間執(zhí)行的前后關(guān)系。圖中的每個(gè)圖中的每個(gè)結(jié)點(diǎn)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程，乃至一條可用于描述一個(gè)程序段或進(jìn)程，乃至一條語句；結(jié)點(diǎn)間的語

6、句；結(jié)點(diǎn)間的有向邊有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序偏序或或前趨關(guā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)稱為初始結(jié)點(diǎn)初始結(jié)點(diǎn)(Initial Node)，把沒有后繼，把沒有后繼的結(jié)點(diǎn)稱為的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)終止結(jié)點(diǎn)(Final Node)。2022-3-198 每個(gè)結(jié)點(diǎn)還具有一個(gè)每個(gè)結(jié)點(diǎn)還具有一個(gè)重量重量(Weight)，用于

7、表示該結(jié)點(diǎn)，用于表示該結(jié)點(diǎn)所含有的所含有的程序量程序量或結(jié)點(diǎn)的或結(jié)點(diǎn)的執(zhí)行時(shí)間執(zhí)行時(shí)間。 圖圖2-2 2-2 前趨圖前趨圖 直接前趨直接前趨直接后繼直接后繼初始結(jié)點(diǎn)初始結(jié)點(diǎn)終止結(jié)點(diǎn)終止結(jié)點(diǎn)2022-3-199對(duì)于圖對(duì)于圖 2-2(a)所示的前趨圖所示的前趨圖,存在下述前趨關(guān)系存在下述前趨關(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

8、),(P4, P6),(P4, P7),(P5, P8),(P6, P8),(P7, P9),(P8, P9) 應(yīng)當(dāng)注意應(yīng)當(dāng)注意,前趨圖中必須前趨圖中必須不存在不存在循環(huán)循環(huán),但在圖但在圖2-2(b)中卻有著下中卻有著下述的前趨關(guān)系述的前趨關(guān)系: S2S3, S3S2 2022-3-19102.1.1 2.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征2.1.2 2.1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征2.1.4 2.1.4 進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài)2.1.5 2.1.5 進(jìn)程控制塊進(jìn)程控制塊2022-3-19112.1.3 2

9、.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征 1.1.程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行 圖圖2-3 2-3 并發(fā)執(zhí)行時(shí)的前趨圖并發(fā)執(zhí)行時(shí)的前趨圖 并發(fā)并發(fā)輸入程序輸入程序I I計(jì)算程序計(jì)算程序C C輸出程序輸出程序P P2022-3-1912下述四條語句的程序段下述四條語句的程序段: S1: a:=x+2 S2: b:=y+4 S3: c:=a+b S4: d:=c+6 圖圖2-4 2-4 四條語句的前趨關(guān)系四條語句的前趨關(guān)系S1S2S3S4什么樣的程序可以并發(fā)執(zhí)行？什么樣的程序可以并發(fā)執(zhí)行？2022-3-19132.2.程序并發(fā)執(zhí)行時(shí)的特征程序并發(fā)執(zhí)行時(shí)的特征 (1)(1)間斷性間斷性

10、 相互制約導(dǎo)致并發(fā)程序具有相互制約導(dǎo)致并發(fā)程序具有“執(zhí)行執(zhí)行- -暫停暫停- -執(zhí)行執(zhí)行”的間斷性活動(dòng)規(guī)律。的間斷性活動(dòng)規(guī)律。(2)(2)失去封閉性失去封閉性 系統(tǒng)中多道程序系統(tǒng)中多道程序共享共享資源，資源的狀態(tài)由多個(gè)程資源，資源的狀態(tài)由多個(gè)程序來改變，必然失去了程序的封閉性。序來改變，必然失去了程序的封閉性。(3)(3)不可再現(xiàn)性不可再現(xiàn)性 失去封閉性失去封閉性 失去可再現(xiàn)性，外界環(huán)境在程序的失去可再現(xiàn)性，外界環(huán)境在程序的兩次執(zhí)行期間發(fā)生變化，失去原有的可重復(fù)特征。兩次執(zhí)行期間發(fā)生變化，失去原有的可重復(fù)特征。2022-3-1914例如例如, ,有兩個(gè)程序有兩個(gè)程序A A和和B,B,它們共享一

11、個(gè)變量它們共享一個(gè)變量N(N(初始值為初始值為x)x)。 A:A:N:=N+1N:=N+1 B: B:Print(N);Print(N);N:=0; N:=0; 程序程序A A和和B B并發(fā)執(zhí)行，可出現(xiàn)以下并發(fā)執(zhí)行，可出現(xiàn)以下三種三種情況情況: : (1)N:=N+1 (1)N:=N+1在在Print(N)Print(N)和和N:=0N:=0之之前前, ,此時(shí)得到的此時(shí)得到的N N值分別為值分別為x+1, x+1, 0 x+1, x+1, 0。 (2)N:=N+1(2)N:=N+1在在Print(N)Print(N)和和N:=0N:=0之之后后, ,此時(shí)得到的此時(shí)得到的N N值分別為值分別為x

12、, 0, 1x, 0, 1。 (3)N:=N+1(3)N:=N+1在在Print(N)Print(N)和和N:=0N:=0之之間間, ,此時(shí)得到的此時(shí)得到的N N值分別為值分別為x, x+1, 0 x, x+1, 0。 2022-3-19152.1.1 2.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征2.1.2 2.1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征2.1.4 2.1.4 進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài)2.1.5 2.1.5 進(jìn)程控制塊進(jìn)程控制塊2022-3-19161 1、進(jìn)程實(shí)體的構(gòu)成、進(jìn)程實(shí)體的構(gòu)成(1)(1)程序程序( (

13、段段) )：進(jìn)程要進(jìn)行的操作。：進(jìn)程要進(jìn)行的操作。(2)(2)數(shù)據(jù)段數(shù)據(jù)段：包括操作的數(shù)據(jù)和程序自己的變量。：包括操作的數(shù)據(jù)和程序自己的變量。(3)(3)進(jìn)程控制塊進(jìn)程控制塊PCB(Process Control Block)PCB(Process Control Block)：存放進(jìn)程：存放進(jìn)程標(biāo)識(shí)符、進(jìn)程運(yùn)行的當(dāng)前狀態(tài)、程序和數(shù)據(jù)的地址、程標(biāo)識(shí)符、進(jìn)程運(yùn)行的當(dāng)前狀態(tài)、程序和數(shù)據(jù)的地址、程序運(yùn)行時(shí)的序運(yùn)行時(shí)的CPUCPU環(huán)境等。環(huán)境等。2022-3-19172.1.4 2.1.4 進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài) 2.2.進(jìn)程的特征進(jìn)程的特征 結(jié)構(gòu)特征結(jié)構(gòu)特征：進(jìn)程的創(chuàng)建與撤消就是：進(jìn)程的創(chuàng)

14、建與撤消就是PCB的創(chuàng)建與撤消。的創(chuàng)建與撤消。 動(dòng)態(tài)性動(dòng)態(tài)性：進(jìn)程是一個(gè)動(dòng)態(tài)的概念，實(shí)質(zhì)上是程序的一次：進(jìn)程是一個(gè)動(dòng)態(tài)的概念，實(shí)質(zhì)上是程序的一次執(zhí)行過程。進(jìn)程具有生命期：它因執(zhí)行過程。進(jìn)程具有生命期：它因“創(chuàng)建創(chuàng)建”而產(chǎn)生，因而產(chǎn)生，因“調(diào)度調(diào)度”而執(zhí)行，執(zhí)行時(shí)還走走停停，因而執(zhí)行，執(zhí)行時(shí)還走走停停，因“撤消撤消”而滅而滅亡。亡。 并發(fā)性并發(fā)性：多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中：多個(gè)進(jìn)程實(shí)體同存于內(nèi)存中, ,且能在一段時(shí)間且能在一段時(shí)間內(nèi)同時(shí)運(yùn)行內(nèi)同時(shí)運(yùn)行, ,共享系統(tǒng)資源共享系統(tǒng)資源; ;引入進(jìn)程實(shí)體的目的就是并引入進(jìn)程實(shí)體的目的就是并發(fā)執(zhí)行。發(fā)執(zhí)行。2022-3-19182.進(jìn)程的特征進(jìn)程的特征獨(dú)

15、立性獨(dú)立性：進(jìn)程是一個(gè)能：進(jìn)程是一個(gè)能獨(dú)立運(yùn)行獨(dú)立運(yùn)行的基本單位，也是系統(tǒng)的基本單位，也是系統(tǒng)進(jìn)行資源分配和調(diào)度的基本單位。進(jìn)行資源分配和調(diào)度的基本單位。異步性異步性：各進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推：各進(jìn)程按各自獨(dú)立的、不可預(yù)知的速度向前推進(jìn)。進(jìn)。3.3.進(jìn)程的定義進(jìn)程的定義進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程, ,是系統(tǒng)進(jìn)行資源分配和調(diào)度是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。的一個(gè)獨(dú)立單位。2022-3-1919進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的進(jìn)程是動(dòng)態(tài)的，程序是靜態(tài)的：程序是有序代碼的集合，：程序是有序代碼的集合，它可以復(fù)制；進(jìn)程是程序在數(shù)據(jù)集上的一次執(zhí)行。它可以復(fù)制；進(jìn)

16、程是程序在數(shù)據(jù)集上的一次執(zhí)行。進(jìn)程是暫時(shí)的進(jìn)程是暫時(shí)的, ,程序是永久的程序是永久的：進(jìn)程是一個(gè)狀態(tài)變化的過程，：進(jìn)程是一個(gè)狀態(tài)變化的過程，有它的撤銷，程序可長久保存。有它的撤銷，程序可長久保存。進(jìn)程具有結(jié)構(gòu)特征進(jìn)程具有結(jié)構(gòu)特征：由程序段、數(shù)據(jù)段和進(jìn)程控制塊三者：由程序段、數(shù)據(jù)段和進(jìn)程控制塊三者組成，而程序僅是指令的有序集合組成，而程序僅是指令的有序集合, ,是進(jìn)程的組成部分之一。是進(jìn)程的組成部分之一。進(jìn)程與程序的對(duì)應(yīng)關(guān)系進(jìn)程與程序的對(duì)應(yīng)關(guān)系：通過多次執(zhí)行，一個(gè)程序可對(duì)應(yīng)：通過多次執(zhí)行，一個(gè)程序可對(duì)應(yīng)多個(gè)進(jìn)程。多個(gè)進(jìn)程。2022-3-19205.5.進(jìn)程的狀態(tài)進(jìn)程的狀態(tài)(1)(1)進(jìn)程的三種基

17、本狀態(tài)進(jìn)程的三種基本狀態(tài)就緒就緒(Ready)(Ready)狀態(tài)：進(jìn)程已獲得除處理機(jī)外的所需資源，狀態(tài)：進(jìn)程已獲得除處理機(jī)外的所需資源，等待分配處理機(jī)資源；只要分配等待分配處理機(jī)資源；只要分配CPUCPU就可執(zhí)行。就可執(zhí)行。執(zhí)行執(zhí)行(Running)(Running)狀態(tài)：處于就緒狀態(tài)的進(jìn)程一旦獲得了處狀態(tài)：處于就緒狀態(tài)的進(jìn)程一旦獲得了處理機(jī)，進(jìn)程狀態(tài)就處于執(zhí)行狀態(tài)。理機(jī)，進(jìn)程狀態(tài)就處于執(zhí)行狀態(tài)。阻塞阻塞(Blocked)(Blocked)狀態(tài)狀態(tài)( (“等待等待”或或“睡眠睡眠”) )：由于進(jìn)程等待：由于進(jìn)程等待某種事件某種事件( (如如I/OI/O操作或進(jìn)程同步操作或進(jìn)程同步) )，在事件

18、發(fā)生之前無法，在事件發(fā)生之前無法繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機(jī)分配給該進(jìn)程繼續(xù)執(zhí)行。該事件發(fā)生前即使把處理機(jī)分配給該進(jìn)程, ,也也無法運(yùn)行。如無法運(yùn)行。如: :請(qǐng)求請(qǐng)求I/OI/O操作，申請(qǐng)緩沖空間等。操作，申請(qǐng)緩沖空間等。2022-3-1921圖圖2-5 2-5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 1.1.時(shí)間片用光時(shí)間片用光2.2.有優(yōu)先級(jí)高的進(jìn)程到來有優(yōu)先級(jí)高的進(jìn)程到來2022-3-1922 引入掛起狀態(tài)的原因引入掛起狀態(tài)的原因 v終端用戶的請(qǐng)求終端用戶的請(qǐng)求v父進(jìn)程請(qǐng)求父進(jìn)程請(qǐng)求v負(fù)荷調(diào)節(jié)的需要負(fù)荷調(diào)節(jié)的需要v操作系統(tǒng)的需要操作系統(tǒng)的需要 (2)進(jìn)程的掛起狀態(tài)進(jìn)程

19、的掛起狀態(tài)圖圖2-6 2-6 具有掛起狀態(tài)的進(jìn)程狀態(tài)圖具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 2022-3-1923創(chuàng)建狀態(tài)創(chuàng)建狀態(tài)：當(dāng)一個(gè)新進(jìn)程剛剛建立：當(dāng)一個(gè)新進(jìn)程剛剛建立, ,還未將其放入就緒還未將其放入就緒隊(duì)列時(shí)的狀態(tài)，稱為新狀態(tài)。隊(duì)列時(shí)的狀態(tài)，稱為新狀態(tài)。 終止?fàn)顟B(tài)終止?fàn)顟B(tài)：當(dāng)一個(gè)進(jìn)程已經(jīng)正常結(jié)束或異常結(jié)束，操：當(dāng)一個(gè)進(jìn)程已經(jīng)正常結(jié)束或異常結(jié)束，操作系統(tǒng)已將其從系統(tǒng)隊(duì)列中移出，但尚未撤消，這時(shí)作系統(tǒng)已將其從系統(tǒng)隊(duì)列中移出，但尚未撤消，這時(shí)稱為終止?fàn)顟B(tài)。稱為終止?fàn)顟B(tài)。 2022-3-1924圖圖2-7 2-7 進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換進(jìn)程的五種基本狀態(tài)及其轉(zhuǎn)換 2022-3-19252.1.1 2

20、.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征2.1.2 2.1.2 前趨圖前趨圖2.1.3 2.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征2.1.4 2.1.4 進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài)2.1.5 2.1.5 進(jìn)程控制塊進(jìn)程控制塊2022-3-19262.1.5 2.1.5 進(jìn)程控制塊進(jìn)程控制塊 1.1.進(jìn)程控制塊的作用進(jìn)程控制塊的作用 進(jìn)程控制塊的進(jìn)程控制塊的作用作用是使一個(gè)在多道程序環(huán)境下不能是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序獨(dú)立運(yùn)行的程序( (含數(shù)據(jù)含數(shù)據(jù)) )，成為一個(gè)能獨(dú)立運(yùn)行的基本，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；?/p>

21、者說，單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f，OSOS是根據(jù)是根據(jù)PCBPCB來對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。來對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。 記錄了操作系統(tǒng)所需的記錄了操作系統(tǒng)所需的, ,用于描述進(jìn)程情況及控制進(jìn)用于描述進(jìn)程情況及控制進(jìn)程運(yùn)行所需的程運(yùn)行所需的全部信息全部信息。 PCBPCB是進(jìn)程存在的唯一標(biāo)志。是進(jìn)程存在的唯一標(biāo)志。2022-3-19272.2.進(jìn)程控制塊中的信息進(jìn)程控制塊中的信息 進(jìn)程標(biāo)識(shí)符進(jìn)程標(biāo)識(shí)符 內(nèi)部標(biāo)識(shí)符和外部標(biāo)識(shí)符。內(nèi)部標(biāo)識(shí)符和外部標(biāo)識(shí)符。 處理機(jī)狀態(tài)處理機(jī)狀態(tài)通用寄存器通用寄存器指令計(jì)數(shù)器指令計(jì)數(shù)器PC程序狀態(tài)字程序狀態(tài)字PSW用戶棧指針用戶棧指

22、針 進(jìn)程調(diào)度信息進(jìn)程調(diào)度信息進(jìn)程狀態(tài)進(jìn)程狀態(tài)進(jìn)程優(yōu)先級(jí)進(jìn)程優(yōu)先級(jí)進(jìn)程調(diào)度所需的其它信息進(jìn)程調(diào)度所需的其它信息事件事件 進(jìn)程控制信息進(jìn)程控制信息程序和數(shù)據(jù)的地址程序和數(shù)據(jù)的地址進(jìn)程同步和通信機(jī)制進(jìn)程同步和通信機(jī)制資源清單資源清單鏈接指針鏈接指針struct pcb int id; /進(jìn)程序號(hào)進(jìn)程序號(hào) int ra; /所需資源所需資源A的數(shù)量的數(shù)量 int rb; /所需資源所需資源B的數(shù)量的數(shù)量 int rc; /所需資源所需資源C的數(shù)量的數(shù)量 int ntime; /所需的時(shí)間片個(gè)數(shù)所需的時(shí)間片個(gè)數(shù) int rtime; /已經(jīng)運(yùn)行的時(shí)間片個(gè)數(shù)已經(jīng)運(yùn)行的時(shí)間片個(gè)數(shù) char state; /

23、進(jìn)程狀態(tài)進(jìn)程狀態(tài) struct pcb *next; 2022-3-1928圖圖2-9 PCB2-9 PCB鏈接隊(duì)列示意圖鏈接隊(duì)列示意圖 3.3.進(jìn)程控制塊的組織方式進(jìn)程控制塊的組織方式(1)(1)鏈接方式鏈接方式 (2)(2)索引方式索引方式2022-3-1929圖圖2-10 2-10 按索引方式組織按索引方式組織PCB PCB 3.3.進(jìn)程控制塊的組織方式進(jìn)程控制塊的組織方式(1)(1)鏈接方式鏈接方式 (2)(2)索引方式索引方式2022-3-19302.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 2.2 2.2 進(jìn)程控制進(jìn)程控制 2.3 2.3 進(jìn)程同步進(jìn)程同步 2.4 2.4 經(jīng)典進(jìn)程

24、的同步問題經(jīng)典進(jìn)程的同步問題 2.5 2.5 進(jìn)程通信進(jìn)程通信2.6 2.6 線程線程2022-3-19311.1.系統(tǒng)態(tài)和用戶態(tài)系統(tǒng)態(tài)和用戶態(tài) 處理機(jī)的執(zhí)行狀態(tài)分處理機(jī)的執(zhí)行狀態(tài)分系統(tǒng)態(tài)系統(tǒng)態(tài)和和用戶態(tài)用戶態(tài)兩種兩種: : (1) (1)系統(tǒng)態(tài)系統(tǒng)態(tài)( (管態(tài)、核心態(tài)管態(tài)、核心態(tài)) )：有較高特權(quán)，能執(zhí)行一切：有較高特權(quán)，能執(zhí)行一切指令，訪問所有寄存器和存儲(chǔ)區(qū)。指令，訪問所有寄存器和存儲(chǔ)區(qū)。 (2)(2)用戶態(tài)用戶態(tài)( (目態(tài)目態(tài)) )：有較低特權(quán)，能執(zhí)行規(guī)定指令，訪：有較低特權(quán)，能執(zhí)行規(guī)定指令，訪問指定寄存器和存儲(chǔ)區(qū)。問指定寄存器和存儲(chǔ)區(qū)。用戶程序運(yùn)行在用戶態(tài)，不能執(zhí)行用戶程序運(yùn)行在用戶態(tài)

25、，不能執(zhí)行OSOS指令及區(qū)域。指令及區(qū)域。OSOS內(nèi)核運(yùn)行在系統(tǒng)態(tài)，進(jìn)程控制是由內(nèi)核運(yùn)行在系統(tǒng)態(tài)，進(jìn)程控制是由OSOS內(nèi)核實(shí)現(xiàn)的。內(nèi)核實(shí)現(xiàn)的。2022-3-19322.2.進(jìn)程控制的功能進(jìn)程控制的功能 進(jìn)程控制是進(jìn)程管理中最基本的功能：進(jìn)程控制是進(jìn)程管理中最基本的功能：創(chuàng)建創(chuàng)建新進(jìn)程新進(jìn)程終止終止已結(jié)束進(jìn)程已結(jié)束進(jìn)程終止終止由于某事件而無法運(yùn)行下去的進(jìn)程由于某事件而無法運(yùn)行下去的進(jìn)程負(fù)責(zé)進(jìn)程的狀態(tài)負(fù)責(zé)進(jìn)程的狀態(tài)轉(zhuǎn)換轉(zhuǎn)換 進(jìn)程控制一般由進(jìn)程控制一般由OSOS的內(nèi)核中的原語來實(shí)現(xiàn)的。的內(nèi)核中的原語來實(shí)現(xiàn)的。2022-3-19333.3.原語原語由若干條指令構(gòu)成的由若干條指令構(gòu)成的“原子操作原子操作

26、”過程，在執(zhí)行期過程，在執(zhí)行期間間不可中斷不可中斷，作為一個(gè)整體而不可分割。，作為一個(gè)整體而不可分割。原子操作：一個(gè)操作中的所有動(dòng)作要么全做，要么原子操作：一個(gè)操作中的所有動(dòng)作要么全做，要么全不做。全不做。原子操作在管態(tài)下執(zhí)行，常駐內(nèi)存。原子操作在管態(tài)下執(zhí)行，常駐內(nèi)存。原語的作用是為了實(shí)現(xiàn)進(jìn)程的通信和控制。原語的作用是為了實(shí)現(xiàn)進(jìn)程的通信和控制。1.創(chuàng)建原語創(chuàng)建原語2.撤消原語撤消原語3.阻塞原語阻塞原語4.喚醒原語喚醒原語5.掛起原語掛起原語6.激活原語激活原語2022-3-19342.2.1 2.2.1 進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建2.2.2 2.2.2 進(jìn)程的終止進(jìn)程的終止2.2.3 2.2.3

27、進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒2.2.4 2.2.4 進(jìn)程的掛起與激活進(jìn)程的掛起與激活2022-3-1935圖圖2-9 2-9 進(jìn)程樹進(jìn)程樹 1. 1.進(jìn)程圖進(jìn)程圖(Process Graph)(Process Graph)進(jìn)程圖進(jìn)程圖是用于描述一個(gè)進(jìn)程的是用于描述一個(gè)進(jìn)程的家族關(guān)系的有向樹，樹中的結(jié)家族關(guān)系的有向樹，樹中的結(jié)點(diǎn)表示進(jìn)程。點(diǎn)表示進(jìn)程。子進(jìn)程可以繼承父進(jìn)程的資源。子進(jìn)程可以繼承父進(jìn)程的資源。撤消父進(jìn)程時(shí)必須同時(shí)撤消子撤消父進(jìn)程時(shí)必須同時(shí)撤消子進(jìn)程進(jìn)程2022-3-19362.2.引起創(chuàng)建進(jìn)程的事件引起創(chuàng)建進(jìn)程的事件 (1)(1)用戶登錄用戶登錄 (2)(2)作業(yè)調(diào)度作業(yè)調(diào)度 (

28、3)(3)提供服務(wù)提供服務(wù) (4)(4)應(yīng)用請(qǐng)求應(yīng)用請(qǐng)求 3.3.進(jìn)程的創(chuàng)建步驟進(jìn)程的創(chuàng)建步驟(1)(1)申請(qǐng)空白申請(qǐng)空白PCB PCB (2)(2)為新進(jìn)程分配資源為新進(jìn)程分配資源 (3)(3)初始化進(jìn)程控制塊初始化進(jìn)程控制塊 (4)(4)將新進(jìn)程插入就緒隊(duì)列將新進(jìn)程插入就緒隊(duì)列2022-3-19372.2.1 2.2.1 進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建2.2.2 2.2.2 進(jìn)程的終止進(jìn)程的終止2.2.3 2.2.3 進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒2.2.4 2.2.4 進(jìn)程的掛起與激活進(jìn)程的掛起與激活2022-3-19381.1.引起進(jìn)程終止的事件引起進(jìn)程終止的事件 1)1)正常結(jié)束正常結(jié)束 2

29、)異常結(jié)束異常結(jié)束 3)外界干預(yù)外界干預(yù)2022-3-19392.2.進(jìn)程的終止過程進(jìn)程的終止過程 (1)(1)從從PCBPCB集合中檢索出該進(jìn)程的集合中檢索出該進(jìn)程的PCB, PCB, 讀出該進(jìn)程的狀態(tài)。讀出該進(jìn)程的狀態(tài)。 (2)(2)若被終止進(jìn)程正處于執(zhí)行狀態(tài)若被終止進(jìn)程正處于執(zhí)行狀態(tài), ,應(yīng)立即終止該進(jìn)程的執(zhí)應(yīng)立即終止該進(jìn)程的執(zhí)行。行。 (3)(3)若該進(jìn)程還有子孫進(jìn)程若該進(jìn)程還有子孫進(jìn)程, ,應(yīng)將其所有子孫進(jìn)程予以終止。應(yīng)將其所有子孫進(jìn)程予以終止。 (4)(4)將被終止進(jìn)程所擁有的全部資源將被終止進(jìn)程所擁有的全部資源, , 歸還給其父進(jìn)程歸還給其父進(jìn)程, , 或者歸還給系統(tǒng)。或者歸還給

30、系統(tǒng)。 (5)(5)將被終止進(jìn)程將被終止進(jìn)程( (它的它的PCB)PCB)從所在隊(duì)列從所在隊(duì)列( (或鏈表或鏈表) )中移出中移出, ,等待其他程序來搜集信息。等待其他程序來搜集信息。 2022-3-19402.2.1 2.2.1 進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建2.2.2 2.2.2 進(jìn)程的終止進(jìn)程的終止2.2.3 2.2.3 進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒2.2.4 2.2.4 進(jìn)程的掛起與激活進(jìn)程的掛起與激活2022-3-19411.1.引起進(jìn)程阻塞和喚醒的事件引起進(jìn)程阻塞和喚醒的事件 (1) (1)請(qǐng)求系統(tǒng)服務(wù)請(qǐng)求系統(tǒng)服務(wù) (2)(2)啟動(dòng)某種操作啟動(dòng)某種操作 (3)(3)新數(shù)據(jù)尚未到達(dá)新數(shù)據(jù)尚

31、未到達(dá) (4)(4)無新工作可做無新工作可做2022-3-1942 2. 2.進(jìn)程阻塞過程進(jìn)程阻塞過程 進(jìn)程調(diào)用阻塞原語進(jìn)程調(diào)用阻塞原語block()block()把自己阻塞，立即停止執(zhí)把自己阻塞，立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行執(zhí)行”改為阻塞，改為阻塞，并將并將PCBPCB插入阻塞隊(duì)列。插入阻塞隊(duì)列。 將本進(jìn)程插入到具有相同事件的阻塞將本進(jìn)程插入到具有相同事件的阻塞( (等待等待) )隊(duì)列。隊(duì)列。 調(diào)度程序進(jìn)行重新調(diào)度調(diào)度程序進(jìn)行重新調(diào)度, ,將處理機(jī)分配給另一就緒進(jìn)將處理機(jī)分配給另一就緒進(jìn)程，并進(jìn)行切換，亦即，保留被阻塞進(jìn)程的處理機(jī)狀程，并進(jìn)行切

32、換，亦即，保留被阻塞進(jìn)程的處理機(jī)狀態(tài)態(tài)( (在在PCBPCB中中) )，再按新進(jìn)程的，再按新進(jìn)程的PCBPCB中的處理機(jī)狀態(tài)設(shè)置中的處理機(jī)狀態(tài)設(shè)置CPUCPU的環(huán)境。的環(huán)境。2022-3-1943 3. 3.進(jìn)程喚醒過程進(jìn)程喚醒過程 調(diào)用喚醒原語調(diào)用喚醒原語wakeup( )wakeup( )將等待該事件的進(jìn)程喚醒。將等待該事件的進(jìn)程喚醒。 喚醒原語執(zhí)行的過程是喚醒原語執(zhí)行的過程是 把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出 將其將其PCBPCB中的現(xiàn)行狀態(tài)由阻塞改為就緒中的現(xiàn)行狀態(tài)由阻塞改為就緒 將該將該P(yáng)CBPCB插入到就緒隊(duì)列中插入到就緒隊(duì)列中2

33、022-3-19442.2.1 2.2.1 進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建2.2.2 2.2.2 進(jìn)程的終止進(jìn)程的終止2.2.3 2.2.3 進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒2.2.4 2.2.4 進(jìn)程的掛起與激活進(jìn)程的掛起與激活2022-3-1945 1. 1.進(jìn)程的掛起進(jìn)程的掛起 系統(tǒng)將利用掛起原語系統(tǒng)將利用掛起原語suspend( )suspend( )將指定進(jìn)程或處于阻將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。塞狀態(tài)的進(jìn)程掛起。 suspend()suspend()原語的執(zhí)行過程原語的執(zhí)行過程 首先檢查被掛起進(jìn)程的狀態(tài)，若處于活動(dòng)就緒狀首先檢查被掛起進(jìn)程的狀態(tài)，若處于活動(dòng)就緒狀態(tài)，便將其改為靜止就緒；

34、對(duì)于活動(dòng)阻塞狀態(tài)的態(tài)，便將其改為靜止就緒；對(duì)于活動(dòng)阻塞狀態(tài)的進(jìn)程，則將之改為靜止阻塞。進(jìn)程，則將之改為靜止阻塞。 把該進(jìn)程的把該進(jìn)程的PCBPCB復(fù)制到某指定的內(nèi)存區(qū)域。復(fù)制到某指定的內(nèi)存區(qū)域。 若被掛起的進(jìn)程正在執(zhí)行若被掛起的進(jìn)程正在執(zhí)行, ,則轉(zhuǎn)向調(diào)度程序重新調(diào)則轉(zhuǎn)向調(diào)度程序重新調(diào)度。度。2022-3-1946 2. 2.進(jìn)程的激活過程進(jìn)程的激活過程 系統(tǒng)將利用激活原語系統(tǒng)將利用激活原語active( )active( )將指定進(jìn)程激活。將指定進(jìn)程激活。 active()active()原語執(zhí)行過程原語執(zhí)行過程 將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)，將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的

35、現(xiàn)行狀態(tài)，若是靜止就緒，將之改為活動(dòng)就緒；若為靜止阻若是靜止就緒，將之改為活動(dòng)就緒；若為靜止阻塞便將之改為活動(dòng)阻塞。塞便將之改為活動(dòng)阻塞。 假如采用的是搶占調(diào)度策略，則每當(dāng)有新進(jìn)程進(jìn)假如采用的是搶占調(diào)度策略，則每當(dāng)有新進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，應(yīng)檢查是否要進(jìn)行重新調(diào)度，即入就緒隊(duì)列時(shí)，應(yīng)檢查是否要進(jìn)行重新調(diào)度，即由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行優(yōu)先級(jí)由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行優(yōu)先級(jí)的比較，如果被激活進(jìn)程的優(yōu)先級(jí)更低，就不必的比較，如果被激活進(jìn)程的優(yōu)先級(jí)更低，就不必重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運(yùn)行，把重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運(yùn)行，把處理機(jī)分配給剛被激活的進(jìn)程。處理機(jī)分配給

36、剛被激活的進(jìn)程。2022-3-19472.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 2.2 2.2 進(jìn)程控制進(jìn)程控制 2.3 2.3 進(jìn)程同步進(jìn)程同步 2.4 2.4 經(jīng)典進(jìn)程的同步問題經(jīng)典進(jìn)程的同步問題 2.5 2.5 進(jìn)程通信進(jìn)程通信2.6 2.6 線程線程2022-3-1948 進(jìn)程同步的主要任務(wù)是對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序進(jìn)程同步的主要任務(wù)是對(duì)多個(gè)相關(guān)進(jìn)程在執(zhí)行次序上進(jìn)行協(xié)調(diào)，以使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地上進(jìn)行協(xié)調(diào)，以使并發(fā)執(zhí)行的諸進(jìn)程之間能有效地共享共享資源資源和和相互合作相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。，從而使程序的執(zhí)行具有可再現(xiàn)性。2.3.1 2.3.1 進(jìn)程同步的基本

37、概念進(jìn)程同步的基本概念2.3.2 2.3.2 信號(hào)量機(jī)制信號(hào)量機(jī)制2.3.3 2.3.3 信號(hào)量的應(yīng)用信號(hào)量的應(yīng)用2.3.4 2.3.4 管程機(jī)制管程機(jī)制2022-3-19492.3.1 2.3.1 進(jìn)程同步的基本概進(jìn)程同步的基本概念念1.兩種形式的制約關(guān)系兩種形式的制約關(guān)系(1)(1)間接相互制約關(guān)系間接相互制約關(guān)系 源于資源共享。如源于資源共享。如A A、B B共享打印機(jī)，若共享打印機(jī)，若A A申請(qǐng)打印時(shí)，申請(qǐng)打印時(shí)，打印機(jī)已分配給打印機(jī)已分配給B B，則，則A A只能阻塞，等只能阻塞，等B B釋放后再改為就緒，釋放后再改為就緒，又稱為又稱為“互斥互斥”。(2)(2)直接相互制約關(guān)系直接相

38、互制約關(guān)系 源于進(jìn)程之間的合作關(guān)系。如進(jìn)程源于進(jìn)程之間的合作關(guān)系。如進(jìn)程A A向向B B提供數(shù)據(jù)，當(dāng)提供數(shù)據(jù)，當(dāng)輸入緩沖空時(shí)，輸入緩沖空時(shí)，B B不能得到數(shù)據(jù)而阻塞；反之當(dāng)緩沖滿時(shí)，不能得到數(shù)據(jù)而阻塞；反之當(dāng)緩沖滿時(shí)，A A無法寫入而阻塞，又稱為無法寫入而阻塞，又稱為“同步同步”。2022-3-19502.2.臨界資源臨界資源定義定義: :在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源。在一段時(shí)間內(nèi)只允許一個(gè)進(jìn)程訪問的資源。例如例如: :打印機(jī)、磁帶機(jī)、卡片輸入機(jī)、變量、表格、數(shù)據(jù)、打印機(jī)、磁帶機(jī)、卡片輸入機(jī)、變量、表格、數(shù)據(jù)、 指針、數(shù)組等。進(jìn)程之間采取互斥方式實(shí)現(xiàn)對(duì)這些指針、數(shù)組等。進(jìn)程之間采取互斥

39、方式實(shí)現(xiàn)對(duì)這些 資源的共享。資源的共享。例子：例子： 生產(chǎn)者生產(chǎn)者- -消費(fèi)者消費(fèi)者(producer-consumer)(producer-consumer)問題是一個(gè)著名的問題是一個(gè)著名的進(jìn)程同步問題。進(jìn)程同步問題。有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，提供給消費(fèi)者進(jìn)程去消費(fèi)。有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，提供給消費(fèi)者進(jìn)程去消費(fèi)。不能向滿緩沖區(qū)投放產(chǎn)品，不能從空緩沖區(qū)中取產(chǎn)品。不能向滿緩沖區(qū)投放產(chǎn)品，不能從空緩沖區(qū)中取產(chǎn)品。2022-3-1951 一個(gè)數(shù)組緩沖池，有一個(gè)數(shù)組緩沖池，有n個(gè)緩沖區(qū)。個(gè)緩沖區(qū)。 buffer:array0, 1, , n-1 of item 輸入指針輸入指針in in =(

40、in+1)mod n。 輸出指針輸出指針out out =(out+1) mod n。 counter：初始值為：初始值為0。緩沖池中含有的產(chǎn)品數(shù)目。緩沖池中含有的產(chǎn)品數(shù)目。0 1 n-1inout 2022-3-1952producer: repeat producer: repeat 生產(chǎn)者進(jìn)程生產(chǎn)者進(jìn)程 produce an item in nextp; produce an item in nextp;/生產(chǎn)一個(gè)產(chǎn)品生產(chǎn)一個(gè)產(chǎn)品 while counter=n do no-op; while counter=n do no-op; buffer bufferinin = =nextp;

41、nextp;/將產(chǎn)品放入緩沖區(qū)內(nèi)將產(chǎn)品放入緩沖區(qū)內(nèi) in =in =in+1 mod n;in+1 mod n; counter = counter =counter+1;counter+1; / /緩沖池中產(chǎn)品數(shù)加一緩沖池中產(chǎn)品數(shù)加一 until false;until false;consumer: repeat consumer: repeat 消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程 while counter=0 do no-op; while counter=0 do no-op; nextc = nextc =bufferbufferoutout; ;/從緩沖區(qū)中消費(fèi)產(chǎn)品從緩沖區(qū)中消費(fèi)產(chǎn)品 out

42、=out =(out+1) mod n;(out+1) mod n; counter = counter-1; counter = counter-1; / /緩沖池中產(chǎn)品數(shù)減一緩沖池中產(chǎn)品數(shù)減一 consumer the item in nextc;/consumer the item in nextc;/消費(fèi)一個(gè)產(chǎn)品消費(fèi)一個(gè)產(chǎn)品 until false; until false; 2022-3-1953 雖然上面的生產(chǎn)者程序和消費(fèi)者程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的，但若并發(fā)執(zhí)行時(shí)，就會(huì)出現(xiàn)差錯(cuò)，問題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對(duì)它做加1操

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

44、是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-3-1955不論是不論是硬件臨界資源硬件臨界資源還是還是軟件臨界資源軟件臨界資源，多個(gè)進(jìn)程必須，多

45、個(gè)進(jìn)程必須互斥互斥地對(duì)它進(jìn)行訪問。地對(duì)它進(jìn)行訪問。在每個(gè)進(jìn)程中訪問臨界資源的那段代碼稱為在每個(gè)進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。臨界區(qū)。每個(gè)進(jìn)程進(jìn)入臨界區(qū)之前應(yīng)先對(duì)欲訪問的臨界資源進(jìn)行每個(gè)進(jìn)程進(jìn)入臨界區(qū)之前應(yīng)先對(duì)欲訪問的臨界資源進(jìn)行檢查，看是否正在被訪問。如果此刻該臨界資源未被訪檢查，看是否正在被訪問。如果此刻該臨界資源未被訪問，該進(jìn)程可進(jìn)入臨界區(qū)問，該進(jìn)程可進(jìn)入臨界區(qū), ,并設(shè)置它正在被訪問的標(biāo)志，并設(shè)置它正在被訪問的標(biāo)志，在臨界區(qū)之前執(zhí)行的這段代碼稱為在臨界區(qū)之前執(zhí)行的這段代碼稱為進(jìn)入?yún)^(qū)。進(jìn)入?yún)^(qū)。在臨界區(qū)后面也要加上一段代碼，用于將臨界區(qū)被訪問在臨界區(qū)后面也要加上一段代碼，用于將臨界

46、區(qū)被訪問的資源恢復(fù)為未被訪問的標(biāo)志，稱為的資源恢復(fù)為未被訪問的標(biāo)志，稱為退出區(qū)。退出區(qū)。2022-3-1956可把一個(gè)可把一個(gè)訪問臨界資源訪問臨界資源的循環(huán)進(jìn)程描述如下的循環(huán)進(jìn)程描述如下: :repeat critical section; 臨界區(qū)臨界區(qū) remainder section; 剩余區(qū)剩余區(qū) until false; entry sectionexit section 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) 退出區(qū)退出區(qū) 2022-3-19574.4.同步機(jī)制應(yīng)遵循的規(guī)則同步機(jī)制應(yīng)遵循的規(guī)則(1)(1)空閑讓進(jìn)：空閑讓進(jìn)：當(dāng)無進(jìn)程處于臨界區(qū)時(shí)當(dāng)無進(jìn)程處于臨界區(qū)時(shí), ,應(yīng)允許一個(gè)進(jìn)程進(jìn)應(yīng)允許一個(gè)進(jìn)程進(jìn)入臨界

47、區(qū)入臨界區(qū), ,以有效利用臨界資源。以有效利用臨界資源。(2)(2)忙則等待忙則等待：當(dāng)有進(jìn)程進(jìn)入臨界區(qū)時(shí)當(dāng)有進(jìn)程進(jìn)入臨界區(qū)時(shí), ,其他進(jìn)程必須等待。其他進(jìn)程必須等待。(3)(3)有限等待：有限等待：對(duì)要求訪問臨界資源的進(jìn)程對(duì)要求訪問臨界資源的進(jìn)程, ,應(yīng)保證在有限應(yīng)保證在有限時(shí)間內(nèi)進(jìn)入自己的臨界區(qū)時(shí)間內(nèi)進(jìn)入自己的臨界區(qū), ,防止防止“死等死等”。(4)(4)讓權(quán)等待：讓權(quán)等待：當(dāng)進(jìn)程不能進(jìn)入其臨界區(qū)時(shí)當(dāng)進(jìn)程不能進(jìn)入其臨界區(qū)時(shí), ,應(yīng)立即釋放處應(yīng)立即釋放處理機(jī)理機(jī), ,防止防止“忙等忙等”, ,不能一直用語句判斷能不能進(jìn)不能一直用語句判斷能不能進(jìn), ,占占用處理機(jī)。用處理機(jī)。2022-3-19

48、582.3.1 2.3.1 進(jìn)程同步的基本概念進(jìn)程同步的基本概念2.3.2 2.3.2 信號(hào)量機(jī)制信號(hào)量機(jī)制2.3.3 2.3.3 信號(hào)量的應(yīng)用信號(hào)量的應(yīng)用2022-3-195919651965年年, ,荷蘭學(xué)者荷蘭學(xué)者DijkstraDijkstra提出的信號(hào)量提出的信號(hào)量(Semaphores)(Semaphores)機(jī)制是一種有效的進(jìn)程同步工具機(jī)制是一種有效的進(jìn)程同步工具, ,所以所以P P、V V分別是荷蘭分別是荷蘭語的語的test(proberen)test(proberen)和和increment(verhogen)increment(verhogen)。信號(hào)量機(jī)制已從信號(hào)量機(jī)制已

49、從整型信號(hào)量整型信號(hào)量發(fā)展為發(fā)展為記錄型信號(hào)量記錄型信號(hào)量、ANDAND型信號(hào)量型信號(hào)量, ,又進(jìn)一步發(fā)展為信號(hào)量集。又進(jìn)一步發(fā)展為信號(hào)量集。信號(hào)量就是信號(hào)量就是OSOS提供的管理公有資源的有效手段。提供的管理公有資源的有效手段。信號(hào)量代表信號(hào)量代表可用資源實(shí)體的數(shù)量可用資源實(shí)體的數(shù)量。2022-3-19601.1.整型信號(hào)量整型信號(hào)量除除初始化初始化外，僅能通過兩個(gè)標(biāo)準(zhǔn)的外，僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作原子操作wait(S)和和signal(S)來訪問。也稱為來訪問。也稱為P、V操作。操作。wait和和signal操作可描述為操作可描述為:uwait(S): while S0 do no-op

50、; S:=S-1;usignal(S): S:=S+1; wait(S)和和signal(S)是原子操作，因此它們在執(zhí)行時(shí)是不可是原子操作，因此它們在執(zhí)行時(shí)是不可中斷的。另外，信號(hào)量只能通過原語操作來訪問，不能被中斷的。另外，信號(hào)量只能通過原語操作來訪問，不能被進(jìn)程調(diào)度所打斷。進(jìn)程調(diào)度所打斷。 有有“忙等忙等”現(xiàn)象?，F(xiàn)象。2022-3-1961可把一個(gè)可把一個(gè)訪問臨界資源訪問臨界資源的循環(huán)進(jìn)程描述如下的循環(huán)進(jìn)程描述如下: :repeat critical section; 臨界區(qū)臨界區(qū) remainder section; 剩余區(qū)剩余區(qū) until false; entry sectionex

51、it sectionP(S)或或wait(S);V(S)或或signal(S); 進(jìn)入?yún)^(qū)進(jìn)入?yún)^(qū) 退出區(qū)退出區(qū) 2022-3-19622.2.記錄型信號(hào)量記錄型信號(hào)量 記錄型信號(hào)量（也稱資源信號(hào)量）機(jī)制，則是一種不存記錄型信號(hào)量（也稱資源信號(hào)量）機(jī)制，則是一種不存在在“忙等忙等”現(xiàn)象的進(jìn)程同步機(jī)制，它采用了現(xiàn)象的進(jìn)程同步機(jī)制，它采用了記錄型的數(shù)記錄型的數(shù)據(jù)結(jié)構(gòu)。據(jù)結(jié)構(gòu)。 在采取了在采取了“讓權(quán)等待讓權(quán)等待”的策略后，又會(huì)出現(xiàn)多個(gè)進(jìn)程等的策略后，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界資源的情況。為此，在信號(hào)量機(jī)制中，待訪問同一臨界資源的情況。為此，在信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量除

52、了需要一個(gè)用于代表資源數(shù)目的整型變量valuevalue外，外，還應(yīng)增加一個(gè)進(jìn)程鏈表還應(yīng)增加一個(gè)進(jìn)程鏈表L L，用于鏈接上述的所有等待進(jìn)，用于鏈接上述的所有等待進(jìn)程。程。2022-3-1963type semaphore=record value:integer;/資源數(shù)目資源數(shù)目 L:list of process;/進(jìn)程鏈表指針進(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: s

53、emaphore; begin S.value:=S.value+1; if S.value0 then wakeup(S.L); end 請(qǐng)求一個(gè)單位的該類資源該類資源數(shù)減少一個(gè)自我阻塞，放棄處理機(jī)釋放一個(gè)單位資源該類資源增加一個(gè)喚醒進(jìn)程2022-3-1964 在有些任務(wù)中在有些任務(wù)中, ,一個(gè)進(jìn)程先要獲得多個(gè)共享資源后才能一個(gè)進(jìn)程先要獲得多個(gè)共享資源后才能執(zhí)行，若進(jìn)程執(zhí)行，若進(jìn)程A A和和B B都要申請(qǐng)都要申請(qǐng)D D和和E E兩種資源，設(shè)信號(hào)量兩種資源，設(shè)信號(hào)量DmutexDmutex和和EmutexEmutex的初值均為的初值均為1 1在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)

54、DmutexDmutex和和EmutexEmutex的操作，即的操作，即process A: process B: P(Dmutex); P(Emutex); P(Emutex); P(Dmutex);若進(jìn)程若進(jìn)程A A和和B B按下述次序交替執(zhí)行按下述次序交替執(zhí)行P 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

55、-3-1965 AND AND同步機(jī)制的同步機(jī)制的基本思想基本思想是是: :將進(jìn)程在整個(gè)運(yùn)行過程中將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源需要的所有資源, ,一次性全部一次性全部地分配給進(jìn)程地分配給進(jìn)程, ,待進(jìn)程使用完待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程, ,其它所其它所有可能為之分配的資源有可能為之分配的資源, ,也不分配給他。亦即也不分配給他。亦即, ,對(duì)若干個(gè)臨對(duì)若干個(gè)臨界資源的分配界資源的分配, ,采取原子操作方式采取原子操作方式: :要么全部分配到進(jìn)程要么全部分配到進(jìn)程, ,要要么一個(gè)也不分配。由死鎖理論可知么一個(gè)也不分配

56、。由死鎖理論可知, ,這樣就可避免上述死鎖這樣就可避免上述死鎖情況的發(fā)生。為此情況的發(fā)生。為此, ,在在P P操作中操作中, ,增加了一個(gè)增加了一個(gè)“ANDAND”條件條件, ,故故稱為稱為ANDAND同步同步, ,或稱為同時(shí)或稱為同時(shí)P P操作操作, , 即即SP(Simultaneous wait)SP(Simultaneous wait)定義如下定義如下: : 2022-3-1966SP:Swait(S1, S2, , Sn) if Si1 and and Sn1 then 每個(gè)資源都可用每個(gè)資源都可用 for i: =1 to n do Si:=Si-1; 分配所有資源分配所有資源 e

57、ndfor else 否則否則,將進(jìn)程放到等待資源將進(jìn)程放到等待資源Si的隊(duì)列中的隊(duì)列中 “阻塞阻塞”( (去第去第1 1個(gè)個(gè)S Si11的的“等待等待S Si”的阻塞隊(duì)列中排隊(duì)的阻塞隊(duì)列中排隊(duì), ,并置它的程序計(jì)數(shù)器于并置它的程序計(jì)數(shù)器于SPSP操作的起始點(diǎn)操作的起始點(diǎn)) ) endifSV:Ssignal(S1, S2, , Sn) for i: =1 to n do Si=Si+1; 釋放所有資源釋放所有資源 “喚醒喚醒”( (所有所有“等待等待S Si i”的阻塞進(jìn)程的阻塞進(jìn)程, ,置為置為“就緒就緒”狀態(tài)狀態(tài), ,移到就緒隊(duì)列中移到就緒隊(duì)列中) ) endfor; 2022-3-19

58、67在記錄型信號(hào)量機(jī)制中在記錄型信號(hào)量機(jī)制中,P(S),P(S)和和V(S)V(S)操作僅能對(duì)信號(hào)量施操作僅能對(duì)信號(hào)量施以加以加1 1或減或減1 1操作操作, ,意味著每次只能獲得或釋放一個(gè)單位的意味著每次只能獲得或釋放一個(gè)單位的臨界資源臨界資源, ,效率較低。效率較低。在有些情況下在有些情況下, ,當(dāng)資源數(shù)量低于某下限值時(shí)便不予分配。當(dāng)資源數(shù)量低于某下限值時(shí)便不予分配。因而因而, ,在每次分配之前在每次分配之前, ,都必須測試該資源的數(shù)量都必須測試該資源的數(shù)量, ,看其是看其是否大于下限值。否大于下限值。在對(duì)在對(duì)ANDAND型信號(hào)量機(jī)制擴(kuò)充的基礎(chǔ)上型信號(hào)量機(jī)制擴(kuò)充的基礎(chǔ)上, ,形成一般化的形

59、成一般化的“信信號(hào)量集號(hào)量集”機(jī)制。機(jī)制。2022-3-1968SP:Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i:=1 to n do Si:=Si-di; 一次分配一次分配d個(gè)資源個(gè)資源 endfor else “阻塞阻塞”(去第去第1個(gè)個(gè)Sinextp; P(empty); empty減減1 P(mutex); buffer(in):=nextp; in:=(in+1)mod n; 移動(dòng)生產(chǎn)指針移動(dòng)生產(chǎn)指針 V(mutex); V(full); full增增1 until false; end consum

60、er: 消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程 begin repeat P(full); P(mutex); nextc: =buffer(out); out:=(out+1) mod n; V(mutex); V(empty); 消費(fèi)消費(fèi)nextc中的一條消息中的一條消息; until false; end parendend 2022-3-1983在生產(chǎn)者在生產(chǎn)者消費(fèi)者問題中要注意以下幾點(diǎn)：消費(fèi)者問題中要注意以下幾點(diǎn)： 在每個(gè)程序中用于實(shí)現(xiàn)互斥的在每個(gè)程序中用于實(shí)現(xiàn)互斥的P(mutex)P(mutex)和和V(mutex)V(mutex)必須必須成成對(duì)對(duì)地出現(xiàn)；地出現(xiàn)； 對(duì)資源信號(hào)量對(duì)資源信號(hào)量empty