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

1、 Process Management 在傳統(tǒng)操作系統(tǒng)中，資源分配和獨立運行的基本單在傳統(tǒng)操作系統(tǒng)中，資源分配和獨立運行的基本單位是位是。OSOS的四大特征也都是基于進(jìn)程而形成的。的四大特征也都是基于進(jìn)程而形成的。 的主要功能是把處理機分配給進(jìn)程以及協(xié)的主要功能是把處理機分配給進(jìn)程以及協(xié)調(diào)各個進(jìn)程之間的相互關(guān)系。由調(diào)各個進(jìn)程之間的相互關(guān)系。由進(jìn)程調(diào)度進(jìn)程調(diào)度程序和程序和進(jìn)程控進(jìn)程控制制程序兩部分內(nèi)容組成。程序兩部分內(nèi)容組成。 第二章第二章 進(jìn)程管理進(jìn)程管理 進(jìn)程的基本概念進(jìn)程的基本概念 進(jìn)程控制進(jìn)程控制 進(jìn)程同步進(jìn)程同步 經(jīng)典進(jìn)程同步問題經(jīng)典進(jìn)程同步問題 管程機制管程機制 進(jìn)程通信進(jìn)程通信 線

2、程線程第二章第二章 進(jìn)程管理進(jìn)程管理2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The basic concept of process一、前趨圖一、前趨圖 (Precedence Graph) 有向有向（DAG）。結(jié)點表示一條語句、一個程序段）。結(jié)點表示一條語句、一個程序段或進(jìn)程?；蜻M(jìn)程。 結(jié)點間的有向邊表示結(jié)點間存在的結(jié)點間的有向邊表示結(jié)點間存在的偏序偏序(Partial Relation)或前趨關(guān)系或前趨關(guān)系(Precedence Relation) ” 。 例：例：Fig2-1 前趨圖示例前趨圖示例第二章第二章 進(jìn)程管理進(jìn)程管理 二、程序順序執(zhí)行二、程序順序執(zhí)行(Sequential

3、 Execution of Program) 程序執(zhí)行時，僅當(dāng)前一操作完成后，才能執(zhí)行后繼操作。程序執(zhí)行時，僅當(dāng)前一操作完成后，才能執(zhí)行后繼操作。2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The basic concept of processC1P1I2C2P2I1特點：特點：順序性順序性(Sequential) 封閉性封閉性(Closeness)（只有程序本身的動作才能改變運行環(huán)境）只有程序本身的動作才能改變運行環(huán)境） 可再現(xiàn)性可再現(xiàn)性(Recurrence) 第二章第二章 進(jìn)程管理進(jìn)程管理三、程序并發(fā)執(zhí)行三、程序并發(fā)執(zhí)行(Concurrent Execution of Program

4、 )1 思想：思想：以輸入、計算、打印三個操作為例：以輸入、計算、打印三個操作為例： 對于某一作業(yè)的三個操作必存在順序關(guān)系，但多個作對于某一作業(yè)的三個操作必存在順序關(guān)系，但多個作業(yè)之間并不一定。其前趨圖可表示為：業(yè)之間并不一定。其前趨圖可表示為： I1 I2 I3 I4 C1 C2 C3 C4 P1 P2 P3 P4 由此圖可以看出，多個此類作業(yè)是可以并發(fā)執(zhí)行的。由此圖可以看出，多個此類作業(yè)是可以并發(fā)執(zhí)行的。2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The basic concept of process第二章第二章 進(jìn)程管理進(jìn)程管理 例：例：s1：a:=x+2 s2：b:=y+1 s3：

5、 c:=a+b s4：d:=c+6 S1S4S3S22 特征特征：間斷性；：間斷性； 失去封閉性；失去封閉性； 不可再現(xiàn)性。不可再現(xiàn)性。S1、S2可并發(fā)執(zhí)行可并發(fā)執(zhí)行第二章第二章 進(jìn)程管理進(jìn)程管理例：有程序例：有程序A：N=N+1； B: print(N)； N=0；設(shè)某時刻；設(shè)某時刻N的初值為的初值為n，則：則：若：若：N=N+1；PRINT(N)； N=0 若：若：PRINT(N)；N=N+1；N=0若：若：PRINT(N)；N=0；N=N+1不可再現(xiàn)性舉例不可再現(xiàn)性舉例N變化結(jié)果為：變化結(jié)果為：n+1 n+1 0N變化結(jié)果為：變化結(jié)果為：n n+1 0N變化結(jié)果為：變化結(jié)果為：n 0 1

6、第二章第二章 進(jìn)程管理進(jìn)程管理2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The basic concept of process四、并發(fā)執(zhí)行條件四、并發(fā)執(zhí)行條件(Bernstein條件條件) 設(shè)設(shè)R(Pi)=a1,a2,am：表示程序：表示程序Pi在執(zhí)行期間需參考的在執(zhí)行期間需參考的所有變量集，稱所有變量集，稱“讀集讀集”； W(Pi)=b1,b2, bn： 表示表示Pi在執(zhí)行期間要改變的所有在執(zhí)行期間要改變的所有變量的集合。稱變量的集合。稱“寫集寫集”。例：例： c:=a-b w:=c+1 x:=x+1 R()=a,b W() =c R()W()= R()= c W()=w R()W()

7、= R()W()=x第二章第二章 進(jìn)程管理進(jìn)程管理 Bernstein條件條件：若兩個程序（進(jìn)程）若兩個程序（進(jìn)程）p1、p2能滿足下述條能滿足下述條件，則它們便能并發(fā)執(zhí)行，且具有可再現(xiàn)性：件，則它們便能并發(fā)執(zhí)行，且具有可再現(xiàn)性： R(p1)W(p2)R(p2) W(p1) W(p1) W(p2) = n可理解為：可理解為： 兩程序互不把對方的結(jié)果作為輸入，且兩程序互不把對方的結(jié)果作為輸入，且不改變同一個量。不改變同一個量。例例第二章第二章 進(jìn)程管理進(jìn)程管理（一）進(jìn)程的引入（一）進(jìn)程的引入 用戶角度看，作業(yè)由若干子任務(wù)組成，只有子任務(wù)被執(zhí)行時才能用戶角度看，作業(yè)由若干子任務(wù)組成，只有子任務(wù)被執(zhí)

8、行時才能體現(xiàn)任務(wù)的功能。體現(xiàn)任務(wù)的功能。 “任務(wù)任務(wù)”和和“任務(wù)的執(zhí)行任務(wù)的執(zhí)行”截然不同。前者是任務(wù)的靜態(tài)描述，截然不同。前者是任務(wù)的靜態(tài)描述，后者體現(xiàn)了任務(wù)的動態(tài)行為。后者體現(xiàn)了任務(wù)的動態(tài)行為。同一段正文（同一段正文（2kB），分別加工兩批（），分別加工兩批（8kB，4kB）不同的數(shù)據(jù)，）不同的數(shù)據(jù)，執(zhí)行兩次。第執(zhí)行兩次。第1次執(zhí)行用打印機報告某些出錯信息，占用次執(zhí)行用打印機報告某些出錯信息，占用10kB內(nèi)存；內(nèi)存；第第2次執(zhí)行中無出錯數(shù)據(jù)，不用打印機，但至少需要次執(zhí)行中無出錯數(shù)據(jù)，不用打印機，但至少需要6kB主存。主存。 五、進(jìn)程的描述五、進(jìn)程的描述 (The description o

9、f process)2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The basic concept of process第二章第二章 進(jìn)程管理進(jìn)程管理r 一個任務(wù)的一個任務(wù)的一次執(zhí)行一次執(zhí)行對應(yīng)對應(yīng)一個進(jìn)程一個進(jìn)程。第二章第二章 進(jìn)程管理進(jìn)程管理r (dynamic) ：是進(jìn)程最基本的特征。進(jìn)程有一定生命周期。是進(jìn)程最基本的特征。進(jìn)程有一定生命周期。程序是指一組有序指令集合，是靜態(tài)實體。程序是指一組有序指令集合，是靜態(tài)實體。r (concurrent) ：一段時間內(nèi)，多個進(jìn)程實體在內(nèi)存中可同時一段時間內(nèi)，多個進(jìn)程實體在內(nèi)存中可同時運行。引入進(jìn)程的目的是為了能并發(fā)。程序不能并發(fā)。運行。引入進(jìn)程

10、的目的是為了能并發(fā)。程序不能并發(fā)。r 獨立性獨立性(independent) ：進(jìn)程是一個能獨立運行、獨立獲得資源、獨進(jìn)程是一個能獨立運行、獨立獲得資源、獨立調(diào)度的基本單位。程序不能做為一個獨立單位。立調(diào)度的基本單位。程序不能做為一個獨立單位。r 異步性異步性(asynchronism) ：進(jìn)程是按各自獨立、不可預(yù)知的速度前進(jìn)，進(jìn)程是按各自獨立、不可預(yù)知的速度前進(jìn)，該特性將導(dǎo)致程序執(zhí)行的不可再現(xiàn)性。該特性將導(dǎo)致程序執(zhí)行的不可再現(xiàn)性。r 結(jié)構(gòu)特征結(jié)構(gòu)特征(structure feature) ：為正確執(zhí)行并發(fā)，每一個進(jìn)程配置為正確執(zhí)行并發(fā)，每一個進(jìn)程配置一個數(shù)據(jù)結(jié)構(gòu)，稱為進(jìn)程控制塊（一個數(shù)據(jù)結(jié)構(gòu)

11、，稱為進(jìn)程控制塊（PCB）。）。如：鍵盤鍵入命令如：鍵盤鍵入命令 $date（二）（二） 進(jìn)程的特征進(jìn)程的特征動態(tài)性動態(tài)性并發(fā)性并發(fā)性第二章第二章 進(jìn)程管理進(jìn)程管理1 三種基本狀態(tài)：三種基本狀態(tài)： 1）就緒狀態(tài)）就緒狀態(tài)(Ready )：進(jìn)程已分配到除：進(jìn)程已分配到除CPU外的所有資源。外的所有資源。只等只等CPU便可運行?？山M成就緒隊列。便可運行?？山M成就緒隊列。 2）執(zhí)行狀態(tài)）執(zhí)行狀態(tài)(Running)：已獲得：已獲得CPU正在運行。在單處理機正在運行。在單處理機系統(tǒng)中只能有一個。系統(tǒng)中只能有一個。 3）阻塞狀態(tài)）阻塞狀態(tài)(Blocked) ：因發(fā)生某事件（如：因發(fā)生某事件（如I/O、申請

12、緩沖區(qū)、申請緩沖區(qū)等）而暫停執(zhí)行。（等待、睡眠）?？捎卸鄠€此狀態(tài)進(jìn)程組等）而暫停執(zhí)行。（等待、睡眠）?？捎卸鄠€此狀態(tài)進(jìn)程組成一個或多個（由阻塞原因劃分）阻塞隊列。成一個或多個（由阻塞原因劃分）阻塞隊列。（三）進(jìn)程的基本狀態(tài)（三）進(jìn)程的基本狀態(tài) (The basic states of process )第二章第二章 進(jìn)程管理進(jìn)程管理1）新建狀態(tài)）新建狀態(tài)(New state) ：指進(jìn)程剛被建立，尚未送入就緒指進(jìn)程剛被建立，尚未送入就緒隊列的狀態(tài)。處于此狀態(tài)的進(jìn)程是不完全的，當(dāng)創(chuàng)建新進(jìn)隊列的狀態(tài)。處于此狀態(tài)的進(jìn)程是不完全的，當(dāng)創(chuàng)建新進(jìn)程的所有工作（分配進(jìn)程控制塊、分配內(nèi)存空間、對程的所有工作（分

13、配進(jìn)程控制塊、分配內(nèi)存空間、對PCB初始化等）完成后，操作系統(tǒng)就把該進(jìn)程送入就緒隊列。初始化等）完成后，操作系統(tǒng)就把該進(jìn)程送入就緒隊列。 2）終止?fàn)顟B(tài)）終止?fàn)顟B(tài)(terminal state) ：指進(jìn)程已經(jīng)結(jié)束（正常、異指進(jìn)程已經(jīng)結(jié)束（正常、異常）常）釋放了除釋放了除PCB之外的其他資源，之外的其他資源， OS已將它從就緒隊列已將它從就緒隊列中移出時的狀態(tài)。處于該狀態(tài)的進(jìn)程不能再被調(diào)度執(zhí)行，中移出時的狀態(tài)。處于該狀態(tài)的進(jìn)程不能再被調(diào)度執(zhí)行，2 新狀態(tài)和終止?fàn)顟B(tài)新狀態(tài)和終止?fàn)顟B(tài)第二章第二章 進(jìn)程管理進(jìn)程管理新進(jìn)程新進(jìn)程終止終止接納接納完成完成進(jìn)程調(diào)度進(jìn)程調(diào)度(時間片到時間片到)I/O完完成成等等

14、I/O請請求求等等中斷中斷執(zhí)行執(zhí)行阻塞阻塞就緒就緒3 進(jìn)程狀態(tài)的轉(zhuǎn)換進(jìn)程狀態(tài)的轉(zhuǎn)換(The conversion of process state)第二章第二章 進(jìn)程管理進(jìn)程管理三種基本狀態(tài)的變換體現(xiàn)了三種基本狀態(tài)的變換體現(xiàn)了OS的資源管理作用。的資源管理作用。進(jìn)程的核心思想在于進(jìn)程的核心思想在于CPU資源的分配。資源的分配。通常進(jìn)程從執(zhí)行態(tài)到阻塞態(tài)是通常進(jìn)程從執(zhí)行態(tài)到阻塞態(tài)是進(jìn)程從阻塞態(tài)到就緒態(tài)是進(jìn)程從阻塞態(tài)到就緒態(tài)是。不可能出現(xiàn)的狀態(tài)轉(zhuǎn)換：不可能出現(xiàn)的狀態(tài)轉(zhuǎn)換： n 第二章第二章 進(jìn)程管理進(jìn)程管理1） 進(jìn)程掛起的原因進(jìn)程掛起的原因（reasons for process suspenson

15、）4 進(jìn)程的掛起狀態(tài)進(jìn)程的掛起狀態(tài)(The suspended state of process) 第二章第二章 進(jìn)程管理進(jìn)程管理2) 狀態(tài)的轉(zhuǎn)換狀態(tài)的轉(zhuǎn)換 引入掛起狀態(tài)后，原狀態(tài)稱為引入掛起狀態(tài)后，原狀態(tài)稱為 “活動活動” (active) ，掛起，掛起后稱為后稱為“靜止靜止” (static) 。有：。有：執(zhí)行執(zhí)行、活動就緒活動就緒、活動阻塞活動阻塞、靜止就緒靜止就緒、靜止阻塞靜止阻塞幾種狀態(tài)。由幾種狀態(tài)。由“活動活動”到到“靜止靜止”的操的操作稱為作稱為“掛起掛起”，由，由“靜止靜止”到到“活動活動”的操作稱為的操作稱為“激激活活”。見見P32 圖圖2-6 Fig 2-6 Process

16、 State Transition Diagram with Suspend States第二章第二章 進(jìn)程管理進(jìn)程管理第二章第二章 進(jìn)程管理進(jìn)程管理六、進(jìn)程控制塊六、進(jìn)程控制塊( Process Control Block)（一）（一）PCB的作用的作用作用：作用： 2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The basic concept of processpid進(jìn)程狀態(tài)進(jìn)程狀態(tài)現(xiàn)場現(xiàn)場優(yōu)先級優(yōu)先級阻塞原因阻塞原因程序地址程序地址同步機制同步機制資源清單資源清單鏈接指針鏈接指針第二章第二章 進(jìn)程管理進(jìn)程管理暫停暫停（斷點的處理（斷點的處理機環(huán)境保存）機環(huán)境保存）調(diào)度調(diào)度（查（查PC

17、B的優(yōu)先的優(yōu)先級及現(xiàn)場狀態(tài)）級及現(xiàn)場狀態(tài)）執(zhí)行執(zhí)行（查（查PCB中處理機的狀中處理機的狀態(tài)信息，恢復(fù)現(xiàn)場）態(tài)信息，恢復(fù)現(xiàn)場）執(zhí)行中執(zhí)行中查數(shù)據(jù)、程序的地查數(shù)據(jù)、程序的地址及與其他進(jìn)程合作址及與其他進(jìn)程合作理理 解：解：在進(jìn)程的整個生命周期中，在進(jìn)程的整個生命周期中，OS根據(jù)根據(jù)PCB對進(jìn)程進(jìn)行控制管對進(jìn)程進(jìn)行控制管理。創(chuàng)建理。創(chuàng)建(分配分配PCB)、調(diào)度、運行、同步、通信、暫停、阻塞、結(jié)、調(diào)度、運行、同步、通信、暫停、阻塞、結(jié)束束(回收回收PCB)。第二章第二章 進(jìn)程管理進(jìn)程管理1）進(jìn)程標(biāo)識信息：）進(jìn)程標(biāo)識信息：用于唯一地標(biāo)識一個進(jìn)程。用于唯一地標(biāo)識一個進(jìn)程。 外部標(biāo)識符：用戶，用字母、數(shù)字構(gòu)

18、成，便于記憶。外部標(biāo)識符：用戶，用字母、數(shù)字構(gòu)成，便于記憶。 內(nèi)部標(biāo)識符：系統(tǒng)，唯一整數(shù)，通常就是進(jìn)程的序號。內(nèi)部標(biāo)識符：系統(tǒng)，唯一整數(shù)，通常就是進(jìn)程的序號。還可根據(jù)需要設(shè)置父進(jìn)程、子進(jìn)程、用戶標(biāo)識符。還可根據(jù)需要設(shè)置父進(jìn)程、子進(jìn)程、用戶標(biāo)識符。2）處理機狀態(tài)信息：）處理機狀態(tài)信息：存儲處理機中各種寄存器的內(nèi)容，用于恢存儲處理機中各種寄存器的內(nèi)容，用于恢復(fù)現(xiàn)場?？捎型ㄓ眉拇嫫鳌⒅噶钣嫈?shù)器、程序狀態(tài)字復(fù)現(xiàn)場?？捎型ㄓ眉拇嫫鳌⒅噶钣嫈?shù)器、程序狀態(tài)字PSW、用戶、用戶棧指針。棧指針。 3）進(jìn)程調(diào)度信息：）進(jìn)程調(diào)度信息：與進(jìn)程調(diào)度和進(jìn)程對換有關(guān)的內(nèi)容。進(jìn)程狀與進(jìn)程調(diào)度和進(jìn)程對換有關(guān)的內(nèi)容。進(jìn)程狀態(tài)、進(jìn)

19、程優(yōu)先級、事件、與調(diào)度算法有關(guān)的其他信息。一般常包括態(tài)、進(jìn)程優(yōu)先級、事件、與調(diào)度算法有關(guān)的其他信息。一般常包括進(jìn)程已等待的時間和已使用的處理器時間等進(jìn)程已等待的時間和已使用的處理器時間等 。（二）進(jìn)程控制塊中的信息（二）進(jìn)程控制塊中的信息(Information in PCB)第二章第二章 進(jìn)程管理進(jìn)程管理4）進(jìn)程控制信息：）進(jìn)程控制信息：程序數(shù)據(jù)的地址、進(jìn)程同步和通信機制程序數(shù)據(jù)的地址、進(jìn)程同步和通信機制（消息隊列和信號量）、資源清單（除（消息隊列和信號量）、資源清單（除CPU外進(jìn)程所需的全外進(jìn)程所需的全部資源及已分配的資源）、鏈接指針（本進(jìn)程所在隊列的下部資源及已分配的資源）、鏈接指針（本

20、進(jìn)程所在隊列的下一個進(jìn)程的一個進(jìn)程的PCB首址）。首址）。說明：說明：r 1）PCB是操作系統(tǒng)中最重要的數(shù)據(jù)結(jié)構(gòu)是操作系統(tǒng)中最重要的數(shù)據(jù)結(jié)構(gòu) 記錄進(jìn)程的記錄進(jìn)程的屬性信息；屬性信息； 標(biāo)志進(jìn)程的存在。標(biāo)志進(jìn)程的存在。r 2）進(jìn)程的）進(jìn)程的PCB與進(jìn)程同時建立，同時撤消。與進(jìn)程同時建立，同時撤消。第二章第二章 進(jìn)程管理進(jìn)程管理 由于由于PCB經(jīng)常被系統(tǒng)訪問，尤其是被運行頻率很高的進(jìn)經(jīng)常被系統(tǒng)訪問，尤其是被運行頻率很高的進(jìn)程調(diào)度及分派程序訪問，故程調(diào)度及分派程序訪問，故PCB應(yīng)常駐內(nèi)存應(yīng)常駐內(nèi)存。系統(tǒng)將所有的。系統(tǒng)將所有的PCB組成若干鏈表（或隊列），存放在組成若干鏈表（或隊列），存放在OS中專門

21、開辟的中專門開辟的PCB區(qū)內(nèi)。區(qū)內(nèi)。 在一個系統(tǒng)中，常常含有固定數(shù)目的在一個系統(tǒng)中，常常含有固定數(shù)目的PCB。對它們要進(jìn)行。對它們要進(jìn)行有效的組織與管理。有效的組織與管理。 常用的方式為：常用的方式為：r 鏈接方式鏈接方式r 索引方式索引方式（三）（三） PCB的組織方式的組織方式(The organization way of PCB )第二章第二章 進(jìn)程管理進(jìn)程管理1）鏈接方式）鏈接方式：相同狀態(tài)的：相同狀態(tài)的PCB鏈接成一個隊列。鏈接成一個隊列。阻塞隊列指針阻塞隊列指針就緒隊列指針就緒隊列指針執(zhí)行指針執(zhí)行指針空閑隊列指針空閑隊列指針PCB2PCB3PCB4PCB5PCB1PCB6PCB7

22、PCB8PCB943091708第二章第二章 進(jìn)程管理進(jìn)程管理2）索引方式）索引方式：相同狀態(tài)的：相同狀態(tài)的PCB建立一張索引表。建立一張索引表。執(zhí)行指針執(zhí)行指針就緒表指針就緒表指針阻塞表指針阻塞表指針PCB1PCB7PCB2PCB3PCB4PCB5PCB6就緒索引表就緒索引表阻塞索引表阻塞索引表第二章第二章 進(jìn)程管理進(jìn)程管理2.2 進(jìn)程控制進(jìn)程控制Process Control 進(jìn)程控制的職能就是對系統(tǒng)中的全部進(jìn)程實行有效的進(jìn)程控制的職能就是對系統(tǒng)中的全部進(jìn)程實行有效的管理，是進(jìn)程管理中最基本的功能。管理，是進(jìn)程管理中最基本的功能。 其主要表現(xiàn)為：進(jìn)程的創(chuàng)建、撤銷以及進(jìn)程運行中的其主要表現(xiàn)為

23、：進(jìn)程的創(chuàng)建、撤銷以及進(jìn)程運行中的狀態(tài)轉(zhuǎn)換。狀態(tài)轉(zhuǎn)換。 進(jìn)程控制一般是由進(jìn)程控制一般是由中的中的實現(xiàn)。實現(xiàn)。 第二章第二章 進(jìn)程管理進(jìn)程管理2.2 進(jìn)程控制進(jìn)程控制Process Control一一二二三四第二章第二章 進(jìn)程管理進(jìn)程管理一、進(jìn)程創(chuàng)建一、進(jìn)程創(chuàng)建（The creating of ProcessThe creating of Process）（reasons for process creation） 用戶登錄（如分時系統(tǒng)中）；用戶登錄（如分時系統(tǒng)中）； 作業(yè)調(diào)度（如批處理系統(tǒng)中）；作業(yè)調(diào)度（如批處理系統(tǒng)中）； 提供服務(wù)（運行中的用戶程序提出某種請求，則系統(tǒng)提供服務(wù)（運行中的用戶程

24、序提出某種請求，則系統(tǒng)創(chuàng)建進(jìn)程以完成請求，創(chuàng)建進(jìn)程以完成請求，如：打印文件如：打印文件）；）； 應(yīng)用請求（應(yīng)用進(jìn)程根據(jù)需要，為自己創(chuàng)建進(jìn)程）應(yīng)用請求（應(yīng)用進(jìn)程根據(jù)需要，為自己創(chuàng)建進(jìn)程）第二章第二章 進(jìn)程管理進(jìn)程管理 用于描述進(jìn)程家族關(guān)系（創(chuàng)建關(guān)系）的有向樹。結(jié)點代表用于描述進(jìn)程家族關(guān)系（創(chuàng)建關(guān)系）的有向樹。結(jié)點代表進(jìn)程，邊代表父子關(guān)系。父進(jìn)程、子進(jìn)程、祖父進(jìn)程、祖先。進(jìn)程，邊代表父子關(guān)系。父進(jìn)程、子進(jìn)程、祖父進(jìn)程、祖先。 子進(jìn)程可以繼承父進(jìn)程所擁有的資源，但子進(jìn)程被撤消子進(jìn)程可以繼承父進(jìn)程所擁有的資源，但子進(jìn)程被撤消時，必須歸還。撤消父進(jìn)程時，須先撤消其所有的子進(jìn)程。時，必須歸還。撤消父進(jìn)程時

25、，須先撤消其所有的子進(jìn)程。PCB中有家族關(guān)系表項，以標(biāo)識自己的父、子進(jìn)程。中有家族關(guān)系表項，以標(biāo)識自己的父、子進(jìn)程。（Process Graph）第二章第二章 進(jìn)程管理進(jìn)程管理0#1#p1p2p3p4Pn是系統(tǒng)引導(dǎo)自動是系統(tǒng)引導(dǎo)自動生成的進(jìn)程生成的進(jìn)程Linux系統(tǒng)中的進(jìn)程樹系統(tǒng)中的進(jìn)程樹 Linux內(nèi)核被加載內(nèi)存后，初始內(nèi)核被加載內(nèi)存后，初始化系統(tǒng)，創(chuàng)建系統(tǒng)中的第一個內(nèi)核化系統(tǒng)，創(chuàng)建系統(tǒng)中的第一個內(nèi)核態(tài)進(jìn)程（態(tài)進(jìn)程（idle進(jìn)程進(jìn)程，0號進(jìn)程）。號進(jìn)程）。m 0#是所有進(jìn)程的祖先。由它執(zhí)行是所有進(jìn)程的祖先。由它執(zhí)行cpu_idle()函數(shù)，當(dāng)沒有其他進(jìn)程處函數(shù)，當(dāng)沒有其他進(jìn)程處于于TASK_

26、RUNNING的時候，調(diào)度程的時候，調(diào)度程序會選擇序會選擇0號進(jìn)程運行號進(jìn)程運行。0號進(jìn)程創(chuàng)號進(jìn)程創(chuàng)建建第一個用戶態(tài)進(jìn)程第一個用戶態(tài)進(jìn)程init進(jìn)程進(jìn)程(1#進(jìn)程進(jìn)程)m1# 它創(chuàng)建和監(jiān)控其他進(jìn)程的活動它創(chuàng)建和監(jiān)控其他進(jìn)程的活動。使用宏。使用宏INIT-TASK定義了進(jìn)程控定義了進(jìn)程控制塊，實現(xiàn)了進(jìn)程模型。制塊，實現(xiàn)了進(jìn)程模型。第二章第二章 進(jìn)程管理進(jìn)程管理 由進(jìn)程由進(jìn)程創(chuàng)建原語創(chuàng)建原語Creat（）（）(fork()完成。完成。 輸入?yún)?shù)輸入?yún)?shù)：進(jìn)程名、優(yōu)先數(shù)、構(gòu)成進(jìn)程名、優(yōu)先數(shù)、構(gòu)成PCB的其他必要參數(shù)的其他必要參數(shù) 返回返回：進(jìn)程號進(jìn)程號 功能功能：創(chuàng)建一個具有指定標(biāo)識符的進(jìn)程。構(gòu)造創(chuàng)

27、建一個具有指定標(biāo)識符的進(jìn)程。構(gòu)造PCB，使該，使該PCB進(jìn)入就緒隊列，使用進(jìn)入就緒隊列，使用Creat原語的進(jìn)程即為新進(jìn)程的父進(jìn)程。原語的進(jìn)程即為新進(jìn)程的父進(jìn)程。 步驟步驟：1）申請空白）申請空白PCB：分配唯一標(biāo)識符，并從：分配唯一標(biāo)識符，并從PCB集合中索取一集合中索取一空白空白PCB； 2）為新進(jìn)程分配資源：為數(shù)據(jù)、程序、用戶棧分配內(nèi)存；）為新進(jìn)程分配資源：為數(shù)據(jù)、程序、用戶棧分配內(nèi)存； 3）初始化）初始化PCB；(標(biāo)識信息、處理機狀態(tài)信息、處理機控制信息標(biāo)識信息、處理機狀態(tài)信息、處理機控制信息) 4）插入就緒隊列。）插入就緒隊列。程序描述為：程序描述為：（The creating of

28、 Process）第二章第二章 進(jìn)程管理進(jìn)程管理q 正常結(jié)束（有一條表示進(jìn)程結(jié)束的指令）；正常結(jié)束（有一條表示進(jìn)程結(jié)束的指令）；q 異常結(jié)束（運行中出現(xiàn)錯誤或故障。如越界錯誤、申異常結(jié)束（運行中出現(xiàn)錯誤或故障。如越界錯誤、申請的內(nèi)存超過了系統(tǒng)所能提供的最大量等。）；請的內(nèi)存超過了系統(tǒng)所能提供的最大量等。）；q 外界干預(yù)（應(yīng)外界的請求而終止。如操作員或操作系外界干預(yù)（應(yīng)外界的請求而終止。如操作員或操作系統(tǒng)干預(yù)、父進(jìn)程請求、父進(jìn)程終止）統(tǒng)干預(yù)、父進(jìn)程請求、父進(jìn)程終止）二、進(jìn)程的終止二、進(jìn)程的終止(Termination of Process)(Termination of Process)第二章第

29、二章 進(jìn)程管理進(jìn)程管理由進(jìn)程由進(jìn)程終止原語終止原語Destroy（）（）完成。完成。輸入?yún)?shù)：輸入?yún)?shù)：進(jìn)程號進(jìn)程號返回：返回：成功或失敗標(biāo)記成功或失敗標(biāo)記功能：功能：撤銷指定進(jìn)程的撤銷指定進(jìn)程的PCB，收回該進(jìn)程擁有的全部資源。，收回該進(jìn)程擁有的全部資源。步驟：步驟：n1）由標(biāo)識符，在）由標(biāo)識符，在PCB集中檢索其集中檢索其PCB，讀取狀態(tài)；，讀取狀態(tài)；n2）若）若“執(zhí)行執(zhí)行”則終止運行，并進(jìn)行進(jìn)程調(diào)度。則終止運行，并進(jìn)行進(jìn)程調(diào)度。n3）查其子孫進(jìn)程，若有則對其）查其子孫進(jìn)程，若有則對其Destroy（）；（）；n4）歸還資源給父進(jìn)程或系統(tǒng)；）歸還資源給父進(jìn)程或系統(tǒng)；n5）將被終止進(jìn)程的）將

30、被終止進(jìn)程的PCB從所在隊列中移出；從所在隊列中移出；第二章第二章 進(jìn)程管理進(jìn)程管理u 請求系統(tǒng)服務(wù)。若請求請求系統(tǒng)服務(wù)。若請求未滿足，則阻塞；當(dāng)資源可以滿足未滿足，則阻塞；當(dāng)資源可以滿足時，由釋放該資源的進(jìn)程將阻塞進(jìn)程喚醒；時，由釋放該資源的進(jìn)程將阻塞進(jìn)程喚醒；u 啟動某種操作啟動某種操作。等待其完成。等待其完成。u 新數(shù)據(jù)未到達(dá)。多進(jìn)程合作時，本進(jìn)程要用的其它進(jìn)程的新數(shù)據(jù)未到達(dá)。多進(jìn)程合作時，本進(jìn)程要用的其它進(jìn)程的結(jié)果尚未到來。結(jié)果尚未到來。u 無新工作可做。某些系統(tǒng)進(jìn)程，等待工作的到達(dá)。無新工作可做。某些系統(tǒng)進(jìn)程，等待工作的到達(dá)。三三、進(jìn)程的阻塞與喚醒、進(jìn)程的阻塞與喚醒(TheThe b

31、lock and wakeup of Process )第二章第二章 進(jìn)程管理進(jìn)程管理由由阻塞原語阻塞原語Block（）（）實現(xiàn)。實現(xiàn)。正在執(zhí)行的進(jìn)程本身調(diào)用正在執(zhí)行的進(jìn)程本身調(diào)用BlockBlock，n1）停止進(jìn)程的執(zhí)行；）停止進(jìn)程的執(zhí)行；n2）改狀態(tài)）改狀態(tài)“執(zhí)行執(zhí)行”為為“阻塞阻塞”，插入相應(yīng)阻塞隊列；，插入相應(yīng)阻塞隊列；n3）重新調(diào)度（進(jìn)行切換，即保留現(xiàn)場，重設(shè)現(xiàn)場）。）重新調(diào)度（進(jìn)行切換，即保留現(xiàn)場，重設(shè)現(xiàn)場）。 BLOCK( ) 輸入?yún)?shù)：輸入?yún)?shù)：無無 返回：返回：轉(zhuǎn)進(jìn)程調(diào)度轉(zhuǎn)進(jìn)程調(diào)度 功能：功能：將現(xiàn)行進(jìn)程的將現(xiàn)行進(jìn)程的PCB置成置成“阻塞阻塞”狀態(tài)后列入阻塞隊狀態(tài)后列入阻塞隊

32、列列第二章第二章 進(jìn)程管理進(jìn)程管理 由由喚醒原語喚醒原語Wakeup（）（）實現(xiàn)。實現(xiàn)。 由和由和的進(jìn)程執(zhí)行喚醒。的進(jìn)程執(zhí)行喚醒。n 1）從阻塞隊列中移出；）從阻塞隊列中移出；n 2）改）改“阻塞阻塞”為為“就緒就緒”；n 3）插入就緒隊列。）插入就緒隊列。 WAKEUP( )輸入?yún)?shù)：輸入?yún)?shù)：進(jìn)程號進(jìn)程號返回：返回：成功或失敗標(biāo)記成功或失敗標(biāo)記功能：功能：把指定進(jìn)程的把指定進(jìn)程的PCB從阻塞隊列摘下，改狀態(tài)為就緒，從阻塞隊列摘下，改狀態(tài)為就緒，插入就緒隊列插入就緒隊列第二章第二章 進(jìn)程管理進(jìn)程管理第二章第二章 進(jìn)程管理進(jìn)程管理由由掛起原語掛起原語Suspend（）（）實現(xiàn)。實現(xiàn)。q 1）檢

33、查、修改狀態(tài)。）檢查、修改狀態(tài)?！盎顒泳途w活動就緒”“靜止就緒靜止就緒”；“活動活動阻塞阻塞” “靜止阻塞靜止阻塞”；q 2）若原狀態(tài)為）若原狀態(tài)為“執(zhí)行執(zhí)行”，則，則“執(zhí)行執(zhí)行” “靜止就緒靜止就緒”，并調(diào)，并調(diào)用進(jìn)程調(diào)度程序重新調(diào)度。用進(jìn)程調(diào)度程序重新調(diào)度。q 3）復(fù)制）復(fù)制PCB到內(nèi)存某區(qū)域到內(nèi)存某區(qū)域;由由激活原語激活原語Active（）（）實現(xiàn)。實現(xiàn)。q 1）將進(jìn)程調(diào)入內(nèi)存，改狀態(tài)。）將進(jìn)程調(diào)入內(nèi)存，改狀態(tài)。“靜止靜止” “活動活動”;q 2）若新狀態(tài)為）若新狀態(tài)為“活動就緒活動就緒”則根據(jù)情況，看是否需重新調(diào)度則根據(jù)情況，看是否需重新調(diào)度（搶占調(diào)度策略）。（搶占調(diào)度策略）。四、進(jìn)程

34、的掛起與激活四、進(jìn)程的掛起與激活(The Suspend and Active of Process)第二章第二章 進(jìn)程管理進(jìn)程管理2.3 進(jìn)程同步進(jìn)程同步 Process Synchronization 進(jìn)程同步的主要任務(wù)是使并發(fā)執(zhí)行的諸進(jìn)程進(jìn)程同步的主要任務(wù)是使并發(fā)執(zhí)行的諸進(jìn)程間能有效地共享資源和相互合作，從而使程序的間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。執(zhí)行具有可再現(xiàn)性。第二章第二章 進(jìn)程管理進(jìn)程管理 同處于一個系統(tǒng)中的進(jìn)程間可能存在兩種關(guān)系：同處于一個系統(tǒng)中的進(jìn)程間可能存在兩種關(guān)系：1）間接相互制約關(guān)系：間接相互制約關(guān)系：因多進(jìn)程共享某資源而產(chǎn)生。此時進(jìn)因多進(jìn)程共

35、享某資源而產(chǎn)生。此時進(jìn)程同步要保證進(jìn)程能互斥地訪問臨界資源。為此資源要由系統(tǒng)程同步要保證進(jìn)程能互斥地訪問臨界資源。為此資源要由系統(tǒng)統(tǒng)一分配。統(tǒng)一分配。 進(jìn)程互斥時他們的執(zhí)行順序是可以任意的，通過共享資源進(jìn)程互斥時他們的執(zhí)行順序是可以任意的，通過共享資源實現(xiàn)相互制約實現(xiàn)相互制約。進(jìn)程資源進(jìn)程進(jìn)程資源進(jìn)程。相互之間不一定清楚其它相互之間不一定清楚其它進(jìn)程情況。進(jìn)程情況。第二章第二章 進(jìn)程管理進(jìn)程管理2）直接相互制約關(guān)系：直接相互制約關(guān)系：因多進(jìn)程內(nèi)容上的聯(lián)系而產(chǎn)生。此因多進(jìn)程內(nèi)容上的聯(lián)系而產(chǎn)生。此時進(jìn)程同步要保證進(jìn)程在執(zhí)行次序上的協(xié)調(diào)。時進(jìn)程同步要保證進(jìn)程在執(zhí)行次序上的協(xié)調(diào)。 進(jìn)程同步指進(jìn)程同步指

36、并發(fā)進(jìn)程，其各自執(zhí)行結(jié)果互為對方的執(zhí)并發(fā)進(jìn)程，其各自執(zhí)行結(jié)果互為對方的執(zhí)行條件，從而限制各進(jìn)程執(zhí)行速度。行條件，從而限制各進(jìn)程執(zhí)行速度。進(jìn)程進(jìn)程。進(jìn)程進(jìn)程。相互清相互清楚對方的存在及其作用，交換信息。楚對方的存在及其作用，交換信息。計算進(jìn)程計算進(jìn)程A緩沖區(qū)緩沖區(qū)打印進(jìn)程打印進(jìn)程B第二章第二章 進(jìn)程管理進(jìn)程管理同步與互斥比較同步與互斥比較同同 步步互互 斥斥進(jìn)程進(jìn)程 -進(jìn)程進(jìn)程進(jìn)程進(jìn)程 -資源資源 - 進(jìn)程進(jìn)程時間次序上受到某種限制時間次序上受到某種限制競爭到某一物理資源時不允許進(jìn)程競爭到某一物理資源時不允許進(jìn)程工作工作相互清楚對方的存在及作用，相互清楚對方的存在及作用，交換信息交換信息不一定清

37、楚其進(jìn)程情況不一定清楚其進(jìn)程情況往往指有幾個進(jìn)程共同完成一往往指有幾個進(jìn)程共同完成一個任務(wù)個任務(wù)往往指多個任務(wù)多個進(jìn)程間通訊制往往指多個任務(wù)多個進(jìn)程間通訊制約約例：例：發(fā)送與接受之間，供者與發(fā)送與接受之間，供者與用者之間，用者之間，4100米接力，米接力，工廠流水線。工廠流水線。例：例：交通十字路口，籃球搶籃板，交通十字路口，籃球搶籃板，進(jìn)程爭搶打印機。進(jìn)程爭搶打印機。第二章第二章 進(jìn)程管理進(jìn)程管理第二章第二章 進(jìn)程管理進(jìn)程管理 若多進(jìn)程共享某臨界資源，則應(yīng)對其進(jìn)行同步控制，以若多進(jìn)程共享某臨界資源，則應(yīng)對其進(jìn)行同步控制，以實現(xiàn)對臨界資源的互斥訪問。實現(xiàn)對臨界資源的互斥訪問。 臨界資源可有硬、

38、軟資源。臨界資源可有硬、軟資源。 硬件資源如：打印機等。硬件資源如：打印機等。諸進(jìn)程要互斥使用這些資源。諸進(jìn)程要互斥使用這些資源。 軟件資源如：共享變量等。軟件資源如：共享變量等。對共享變量應(yīng)作為臨界資源對共享變量應(yīng)作為臨界資源處理。即要對它進(jìn)行互斥訪問。處理。即要對它進(jìn)行互斥訪問。 （一）臨界資源（一）臨界資源 ( Critical resource) 第二章第二章 進(jìn)程管理進(jìn)程管理 進(jìn)程進(jìn)程A：生產(chǎn)一個數(shù)據(jù)。用：生產(chǎn)一個數(shù)據(jù)。用count計數(shù)，計數(shù)，count=count+1 進(jìn)程進(jìn)程B：消費一個數(shù)據(jù)。則：消費一個數(shù)據(jù)。則count=count-1對對count的操作可細(xì)化為：（的操作可細(xì)

39、化為：（R表示寄存器，設(shè)表示寄存器，設(shè)count初值為初值為1）例例1： 兩個并發(fā)執(zhí)行的進(jìn)程兩個并發(fā)執(zhí)行的進(jìn)程A、B。A：R1=count R1=R1+1 count=R1B：R2=count R2=R2-1 count=R2n若執(zhí)行次序為：若執(zhí)行次序為：A(1) A(2) A(3) B(1) B(2) B(3) 則則count=1n若執(zhí)行次序為：若執(zhí)行次序為：A(1) B(1) A(2) A(3) B(2) B(3) 則則count=0n若執(zhí)行次序為：若執(zhí)行次序為：A(1) B(1) B(2) B(3) A(2) A(3) 則則count=2第二章第二章 進(jìn)程管理進(jìn)程管理棧指針為棧指針為to

40、p，設(shè)有兩個程序段設(shè)有兩個程序段getaddr(top) 和和 putaddr(blk)，從給定棧中取出相應(yīng)的內(nèi)存數(shù)據(jù)塊地址，從給定棧中取出相應(yīng)的內(nèi)存數(shù)據(jù)塊地址，將內(nèi)存數(shù)據(jù)塊地址將內(nèi)存數(shù)據(jù)塊地址blk放入椎棧中。放入椎棧中。例例2：設(shè)有堆棧設(shè)有堆棧S S，棧中存放內(nèi)存中相應(yīng)的數(shù)據(jù)塊地址。，棧中存放內(nèi)存中相應(yīng)的數(shù)據(jù)塊地址。第二章第二章 進(jìn)程管理進(jìn)程管理abef a b e f隨機 a b e f第二章第二章 進(jìn)程管理進(jìn)程管理 對對臨界資源，多進(jìn)程必須互斥訪問。把每個進(jìn)程臨界資源，多進(jìn)程必須互斥訪問。把每個進(jìn)程的那段的那段稱為稱為CS。 對臨界資源的互斥訪問即為多進(jìn)程互斥進(jìn)入各自的臨對臨界資源的互

41、斥訪問即為多進(jìn)程互斥進(jìn)入各自的臨界區(qū)操作。為保證互斥訪問，在進(jìn)入前必需先檢測臨界資界區(qū)操作。為保證互斥訪問，在進(jìn)入前必需先檢測臨界資源的狀態(tài)。源的狀態(tài)。(Entry section) ：進(jìn)程中在臨界區(qū)前用于檢查臨界：進(jìn)程中在臨界區(qū)前用于檢查臨界資源是否正被訪問的代碼。資源是否正被訪問的代碼。(Exit section) ：進(jìn)程中在臨界區(qū)后的一段代碼，用：進(jìn)程中在臨界區(qū)后的一段代碼，用于標(biāo)記該臨界資源已被釋放。于標(biāo)記該臨界資源已被釋放。 （二）（二） 臨界區(qū)臨界區(qū) (Critical Section)第二章第二章 進(jìn)程管理進(jìn)程管理Entry sectionExit section remaind

42、er section;until false;訪問臨界資源的循環(huán)進(jìn)程描述如下訪問臨界資源的循環(huán)進(jìn)程描述如下：repeatcritical section;為實現(xiàn)進(jìn)程互斥進(jìn)入為實現(xiàn)進(jìn)程互斥進(jìn)入自己的臨界區(qū)，采用自己的臨界區(qū)，采用進(jìn)行協(xié)調(diào)。進(jìn)行協(xié)調(diào)。第二章第二章 進(jìn)程管理進(jìn)程管理 OS利用同步機制提供互斥工具才能保證進(jìn)程互斥的進(jìn)入臨界利用同步機制提供互斥工具才能保證進(jìn)程互斥的進(jìn)入臨界區(qū)，互斥工具應(yīng)能保證如下幾點：區(qū)，互斥工具應(yīng)能保證如下幾點：1）：若臨界資源空閑，則允許一個請求進(jìn)程進(jìn)入自己的臨界區(qū)。若臨界資源空閑，則允許一個請求進(jìn)程進(jìn)入自己的臨界區(qū)。2）：若臨界資源正被使用，則其它申請該資源的進(jìn)程

43、應(yīng)該等待。若臨界資源正被使用，則其它申請該資源的進(jìn)程應(yīng)該等待。3）：保證進(jìn)程可在有限時間內(nèi)進(jìn)入自己的臨界區(qū)，防止保證進(jìn)程可在有限時間內(nèi)進(jìn)入自己的臨界區(qū)，防止“死等死等”。4）：當(dāng)進(jìn)程需臨界資源不能滿足而等待時，應(yīng)釋放當(dāng)進(jìn)程需臨界資源不能滿足而等待時，應(yīng)釋放CPU，防止，防止“忙等忙等” 互斥工具有軟件、硬件和信號量幾種方法。互斥工具有軟件、硬件和信號量幾種方法。（三）同步機制應(yīng)遵循的原則（三）同步機制應(yīng)遵循的原則第二章第二章 進(jìn)程管理進(jìn)程管理設(shè)兩個進(jìn)程設(shè)兩個進(jìn)程PiPi、 PjPj并發(fā)執(zhí)行，共享某臨界資源。描述為：并發(fā)執(zhí)行，共享某臨界資源。描述為： beginbegin parbegin pa

44、rbegin Pi Pi； PjPj； parendparend end end 利用軟件方法解決進(jìn)程互斥問題，方法之一利用軟件方法解決進(jìn)程互斥問題，方法之一 -。第二章第二章 進(jìn)程管理進(jìn)程管理 。檢查鎖狀態(tài)，若為關(guān)。檢查鎖狀態(tài)，若為關(guān)閉，則等待其打開；若已打開，閉，則等待其打開；若已打開，則將其關(guān)閉，執(zhí)行。則將其關(guān)閉，執(zhí)行。 。進(jìn)入臨界區(qū)，執(zhí)行操。進(jìn)入臨界區(qū)，執(zhí)行操作。作。 ，將鎖打開，退出臨界，將鎖打開，退出臨界區(qū)。區(qū)。 關(guān)鎖關(guān)鎖lock(W):lock(W): while(W=1); while(W=1); W=1; W=1; 開鎖開鎖unlock(W): unlock(W): W=0;

45、 W=0;為為每類臨界區(qū)每類臨界區(qū)設(shè)置一把設(shè)置一把“鎖鎖”，有，有打開打開和和關(guān)閉關(guān)閉兩種狀態(tài)?？蓛煞N狀態(tài)?？捎米兞勘硎炬i（軟件鎖），值為用變量表示鎖（軟件鎖），值為0表示打開，為表示打開，為1表示關(guān)閉。表示關(guān)閉。第二章第二章 進(jìn)程管理進(jìn)程管理例：例：利用鎖變量方法實現(xiàn)兩個進(jìn)程利用鎖變量方法實現(xiàn)兩個進(jìn)程A A、B B互斥互斥共享共享打印機打印機。進(jìn)程進(jìn)程ALock(W);打印信息打印信息S；/*CS區(qū)區(qū)*/Unlock(W);進(jìn)程進(jìn)程BLock(W);打印信息打印信息S；/*CS區(qū)區(qū)*/Unlock(W);：簡單；：簡單；：不安全，因為關(guān)鎖和開鎖操作不具有不安全，因為關(guān)鎖和開鎖操作不具有原子性

46、原子性。 出現(xiàn)出現(xiàn)“忙等忙等”，軟件算法不能完全解決多個進(jìn)程互斥問題，算法復(fù)雜，效率較軟件算法不能完全解決多個進(jìn)程互斥問題，算法復(fù)雜，效率較低。低。以變量以變量W表示鎖，置初值表示鎖，置初值為為0。兩個進(jìn)程的部分代碼如下。兩個進(jìn)程的部分代碼如下。Perterson算法算法 第二章第二章 進(jìn)程管理進(jìn)程管理 1）指令：）指令：boolean TS(boolean *lock) boolean old; old = lock; lock = TRUE; return old;lock值表示資源使用情況。值表示資源使用情況。false，表示，表示空閑（初值）；空閑（初值）；true，則表示正用。，則表

47、示正用。 利用硬件方法解決進(jìn)程互斥問題有利用硬件方法解決進(jìn)程互斥問題有和和兩種常見方式。兩種常見方式。第二章第二章 進(jìn)程管理進(jìn)程管理2）利用）利用TS實現(xiàn)進(jìn)程互斥實現(xiàn)進(jìn)程互斥while TS(lock) do skip CSlock:=false注：注：若資源可用，則若資源可用，則lock 為為false，則，則TS(lock)為為false，進(jìn)入，進(jìn)入CS，否則，否則繼續(xù)檢測。退出臨界區(qū)，繼續(xù)檢測。退出臨界區(qū)，重設(shè)資源可用。重設(shè)資源可用。缺點缺點：不能：不能“讓權(quán)等待讓權(quán)等待”，是一種是一種“忙等忙等” 更好的方法是當(dāng)臨界資源不可用時，就阻塞該進(jìn)程，直更好的方法是當(dāng)臨界資源不可用時，就阻塞該

48、進(jìn)程，直到臨界資源可用時繼續(xù)。到臨界資源可用時繼續(xù)。 該指令的具體實現(xiàn)該指令的具體實現(xiàn)第二章第二章 進(jìn)程管理進(jìn)程管理 信號量（信號量（Semaphore）方法是荷蘭學(xué)者）方法是荷蘭學(xué)者Dijkstra1965年提年提出的解決進(jìn)程同步、互斥的通用工具，在出的解決進(jìn)程同步、互斥的通用工具，在THE(荷蘭文荷蘭文Tchnische Hoogeschool Eindhov)操作系統(tǒng)中實現(xiàn)。操作系統(tǒng)中實現(xiàn)。第二章第二章 進(jìn)程管理進(jìn)程管理（四）信號量機制（四）信號量機制（Integer Semaphore） wait(s)： while s0表示一個或多表示一個或多個資源，個資源，0沒有資源。沒有資源。r

49、 信號量操作的信號量操作的： 信號量可以初始化為一個非信號量可以初始化為一個非負(fù)值；負(fù)值；除初始化外，僅能由除初始化外，僅能由wait( )和和signal( )訪問信號量訪問信號量。即即P和和V操作。操作。signal(s): s:=s+1第二章第二章 進(jìn)程管理進(jìn)程管理 其他進(jìn)程可獲得處理機，會出現(xiàn)多個進(jìn)程等待訪問同一臨其他進(jìn)程可獲得處理機，會出現(xiàn)多個進(jìn)程等待訪問同一臨界資源。界資源。 放棄處理機放棄處理機“阻塞阻塞”等待，等待，“讓權(quán)等待讓權(quán)等待”。整型信號量的整型信號量的： 未遵循未遵循“讓權(quán)等待讓權(quán)等待”，出現(xiàn)，出現(xiàn)“忙等忙等”。第二章第二章 進(jìn)程管理進(jìn)程管理（Record-type

50、Semaphore） 記錄型信號量所含內(nèi)容記錄型信號量所含內(nèi)容（1 1）代表資源數(shù)目的整型量代表資源數(shù)目的整型量（2 2）進(jìn)程鏈表，接納所有等待進(jìn)程。進(jìn)程鏈表，接納所有等待進(jìn)程。type semaphore=record value：integer; L：list of process; -L為一個進(jìn)程鏈表為一個進(jìn)程鏈表 end第二章第二章 進(jìn)程管理進(jìn)程管理procedure signal(s) var s:semaphore; begin s.value:=s.value+1 if s.value=0 then wakeup(s.L) endprocedure wait(s)var s :s

51、emaphore;begin s.value:=s.value-1； if s.value0 then block(s.L)；end第二章第二章 進(jìn)程管理進(jìn)程管理例：系統(tǒng)有兩臺打印機，有多個需要執(zhí)行打印操作的進(jìn)例：系統(tǒng)有兩臺打印機，有多個需要執(zhí)行打印操作的進(jìn)程，描述各個進(jìn)程的執(zhí)行。程，描述各個進(jìn)程的執(zhí)行。 s第二章第二章 進(jìn)程管理進(jìn)程管理 1）s.value的的。s.L表示該表示該資源的阻塞隊列。資源的阻塞隊列。 2）wait()表示請求一個單位的資源。表示請求一個單位的資源。s.value-1表示該資源表示該資源數(shù)減數(shù)減1。若。若s.value0，則資源已用完，調(diào)用阻塞原語。此時的，則資源已

52、用完，調(diào)用阻塞原語。此時的s.value值不再是資源數(shù)量，而是值不再是資源數(shù)量，而是。 3）signal()表示釋放一個單位的資源。表示釋放一個單位的資源。 s.value+1表示該資表示該資源數(shù)加源數(shù)加1。若。若s.value1時，可看作一般的記錄型信號量。當(dāng)時，可看作一般的記錄型信號量。當(dāng)S=1時，即為互斥時，即為互斥信號量。信號量。l 3）Swait（S，1，0）下限為）下限為1，每次分配，每次分配0個資源。這是個資源。這是一種特殊的可作為開關(guān)的信號量。當(dāng)一種特殊的可作為開關(guān)的信號量。當(dāng)S1時，允許多個進(jìn)程時，允許多個進(jìn)程進(jìn)入。當(dāng)進(jìn)入。當(dāng)S1（S=0）時，阻止任何進(jìn)程進(jìn)入。）時，阻止任何

53、進(jìn)程進(jìn)入。幾種特殊情況：幾種特殊情況：第二章第二章 進(jìn)程管理進(jìn)程管理r 一個臨界資源一個臨界資源var mutex:semaphore:= parbegin process1: wait(mutex) CS signal(mutex) process2: wait(mutex) CS signal(mutex) parendl 1、識別臨界資源，一看是、識別臨界資源，一看是否否共享共享，二看是否，二看是否排他排他。l 2、wait(mutex)和和signal(mutex)必須必須成對出現(xiàn)成對出現(xiàn)，并分別緊靠并分別緊靠臨界段的頭尾部臨界段的頭尾部。（五）信號量應(yīng)用之一（五）信號量應(yīng)用之一缺少缺

54、少wait，則？缺少，則？缺少signal，則？，則？一個互斥信號量一個互斥信號量mutex實現(xiàn)進(jìn)程實現(xiàn)進(jìn)程P1和和P2互斥的描述為：互斥的描述為：第二章第二章 進(jìn)程管理進(jìn)程管理實例：三個進(jìn)程執(zhí)行中要共享變量實例：三個進(jìn)程執(zhí)行中要共享變量count。count屬于臨界資源，對其應(yīng)互斥訪問。屬于臨界資源，對其應(yīng)互斥訪問。 until false;end Var mutex:semaphore:=1;Begin parbegin process1:begin repeat until false; end process3:begin repeat until false; endParendEn

55、dprocess2:begin repeat -2.1P下一條語句下一條語句第二章第二章 進(jìn)程管理進(jìn)程管理（六）信號量應(yīng)用之二（六）信號量應(yīng)用之二 利用信號量可以控制進(jìn)程執(zhí)行的先后次序，以描述程序利用信號量可以控制進(jìn)程執(zhí)行的先后次序，以描述程序或語句間的前趨關(guān)系?；蛘Z句間的前趨關(guān)系。mutex第二章第二章 進(jìn)程管理進(jìn)程管理 parbegin begin S1；signal(a)；signal(b)；end； begin wait(a)；S2；signal(c)；signal(d)；end； begin wait(b)；S3；signal(e)；end； begin wait(c)；S4；sig

56、nal(f)；end； begin wait(d)；S5；signal(g)；end； begin wait(e)；wait(f)；wait(g)；S6；end； parendendvar a,b,c,d,e,f,g:semaphore:=0,0,0,0,0,0,0beginS1S5S2S3S6S4S3abcdfge第二章第二章 進(jìn)程管理進(jìn)程管理第二章第二章 進(jìn)程管理進(jìn)程管理例如：例如：計算進(jìn)程計算進(jìn)程、打印進(jìn)程打印進(jìn)程實現(xiàn)合作。實現(xiàn)合作。計算進(jìn)程計算進(jìn)程不斷把每次計算結(jié)不斷把每次計算結(jié)果果放入放入buf中，中，打印進(jìn)程打印進(jìn)程則則取出取出buf中的數(shù)據(jù)打印輸出，若不采取任中的數(shù)據(jù)打印輸出，若

57、不采取任何制約措施，這兩個進(jìn)程的起始執(zhí)行時間和執(zhí)行速度彼此獨立，相何制約措施，這兩個進(jìn)程的起始執(zhí)行時間和執(zhí)行速度彼此獨立，相應(yīng)的控制段描述為：應(yīng)的控制段描述為：Pc: A：local buf1計算計算Repeat buf1buf Until buf1=空空 Buf計算結(jié)果計算結(jié)果GoTo APp:B：local pri Repeat pribuf Until pri空空 打印打印buf中的數(shù)據(jù)中的數(shù)據(jù) 消除消除buf中的數(shù)據(jù)中的數(shù)據(jù)GoTo B問問 題：題：CPU時間的極大浪費時間的極大浪費（一）問題的提出（一）問題的提出第二章第二章 進(jìn)程管理進(jìn)程管理直接制約的進(jìn)程互給對方進(jìn)程直接制約的進(jìn)程互

58、給對方進(jìn)程，一旦收到制約進(jìn)程發(fā)來的信號即由等待開始執(zhí)行。，一旦收到制約進(jìn)程發(fā)來的信號即由等待開始執(zhí)行。 當(dāng)當(dāng)Pc將計算結(jié)果送入將計算結(jié)果送入buf后，后，給給Pp進(jìn)程發(fā)送一個進(jìn)程發(fā)送一個buf滿信號滿信號，Pp進(jìn)程等到滿信號即從進(jìn)程等到滿信號即從buf中取出結(jié)果去打印中取出結(jié)果去打印;當(dāng)當(dāng)Pp進(jìn)程把進(jìn)程把buf中數(shù)據(jù)取出打印后，中數(shù)據(jù)取出打印后，給給Pc進(jìn)程發(fā)送一個進(jìn)程發(fā)送一個buf空信號空信號，Pc等到空信號即可把下一個計算結(jié)果送入緩沖區(qū)。等到空信號即可把下一個計算結(jié)果送入緩沖區(qū)。 把各進(jìn)程之間發(fā)送的信號作為信號量看待。即把各進(jìn)程之間發(fā)送的信號作為信號量看待。即buf滿信號滿信號，buf空信

59、號空信號可用信號量表示?？捎眯盘柫勘硎?。（二）問題分析（二）問題分析同同 步步 機機 制制第二章第二章 進(jìn)程管理進(jìn)程管理 S Sempty empty ：是是PpPp進(jìn)程運行結(jié)束發(fā)送的信號量，是進(jìn)程運行結(jié)束發(fā)送的信號量，是PcPc運行運行需要等待的信號量，用于判斷需要等待的信號量，用于判斷BufBuf是否為空。若空則為是否為空。若空則為1 1，否則為，否則為0 0。 S Sfullfull：是是PcPc進(jìn)程運行結(jié)束發(fā)送的信號量，是進(jìn)程進(jìn)程運行結(jié)束發(fā)送的信號量，是進(jìn)程PpPp運行需要使用的信號量，用于判斷運行需要使用的信號量，用于判斷BufBuf中是否有數(shù)據(jù)。中是否有數(shù)據(jù)。有數(shù)據(jù)為有數(shù)據(jù)為1 1

60、，無數(shù)據(jù)為，無數(shù)據(jù)為0 0。 初始：初始： S Sempty empty 1 1， S Sfullfull 0 0設(shè)置兩個信號量：設(shè)置兩個信號量：Sempty 和和 Sfull第二章第二章 進(jìn)程管理進(jìn)程管理計算進(jìn)程計算進(jìn)程C打印進(jìn)程打印進(jìn)程P計計 算算P(Sempty)送緩沖區(qū)送緩沖區(qū)V(Sfull)從從Buffer中取數(shù)中取數(shù)P(Sfull)打印打印V(Sempty)第二章第二章 進(jìn)程管理進(jìn)程管理進(jìn)程進(jìn)程關(guān)系中，直接制約進(jìn)程之間發(fā)送的關(guān)系中，直接制約進(jìn)程之間發(fā)送的信號量，只與制約進(jìn)程及被制約進(jìn)程有關(guān)。信號量，只與制約進(jìn)程及被制約進(jìn)程有關(guān)。 一個進(jìn)程一個進(jìn)程PiPi的私有信號量是從制約進(jìn)程的私