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

1、 Process Management 在傳統(tǒng)操作系統(tǒng)中，資源分配和獨(dú)立運(yùn)行的基本單在傳統(tǒng)操作系統(tǒng)中，資源分配和獨(dú)立運(yùn)行的基本單位是位是。OSOS的四大特征也都是基于進(jìn)程而形成的。的四大特征也都是基于進(jìn)程而形成的。 的主要功能是把處理機(jī)分配給進(jìn)程以及協(xié)的主要功能是把處理機(jī)分配給進(jìn)程以及協(xié)調(diào)各個(gè)進(jìn)程之間的相互關(guān)系。由調(diào)各個(gè)進(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ī)制管程機(jī)制 進(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é)點(diǎn)表示一條語句、一個(gè)程序段）。結(jié)點(diǎn)表示一條語句、一個(gè)程序段或進(jìn)程?；蜻M(jìn)程。 結(jié)點(diǎn)間的有向邊表示結(jié)點(diǎn)間存在的結(jié)點(diǎn)間的有向邊表示結(jié)點(diǎn)間存在的偏序偏序(Partial Relation)或前趨關(guān)系或前趨關(guān)系(Precedence Relation) ” 。 例：例：Fig2-1 前趨圖示例前趨圖示例第二章第二章 進(jìn)程管理進(jìn)程管理 二、程序順序執(zhí)行二、程序順序執(zhí)行(Sequential

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

4、 )1 思想：思想：以輸入、計(jì)算、打印三個(gè)操作為例：以輸入、計(jì)算、打印三個(gè)操作為例： 對(duì)于某一作業(yè)的三個(gè)操作必存在順序關(guān)系，但多個(gè)作對(duì)于某一作業(yè)的三個(gè)操作必存在順序關(guān)系，但多個(gè)作業(yè)之間并不一定。其前趨圖可表示為：業(yè)之間并不一定。其前趨圖可表示為： I1 I2 I3 I4 C1 C2 C3 C4 P1 P2 P3 P4 由此圖可以看出，多個(gè)此類作業(yè)是可以并發(fā)執(zhí)行的。由此圖可以看出，多個(gè)此類作業(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í)刻；設(shè)某時(shí)刻N(yù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條件條件：若兩個(gè)程序（進(jìn)程）若兩個(gè)程序（進(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可理解為：可理解為： 兩程序互不把對(duì)方的結(jié)果作為輸入，且兩程序互不把對(duì)方的結(jié)果作為輸入，且不改變同一個(gè)量。不改變同一個(gè)量。例例第二章第二章 進(jìn)程管理進(jìn)程管理（一）進(jìn)程的引入（一）進(jìn)程的引入 用戶角度看，作業(yè)由若干子任務(wù)組成，只有子任務(wù)被執(zhí)行時(shí)才能用戶角度看，作業(yè)由若干子任務(wù)組成，只有子任務(wù)被執(zhí)

8、行時(shí)才能體現(xiàn)任務(wù)的功能。體現(xiàn)任務(wù)的功能。 “任務(wù)任務(wù)”和和“任務(wù)的執(zhí)行任務(wù)的執(zhí)行”截然不同。前者是任務(wù)的靜態(tài)描述，截然不同。前者是任務(wù)的靜態(tài)描述，后者體現(xiàn)了任務(wù)的動(dòng)態(tài)行為。后者體現(xiàn)了任務(wù)的動(dòng)態(tài)行為。同一段正文（同一段正文（2kB），分別加工兩批（），分別加工兩批（8kB，4kB）不同的數(shù)據(jù)，）不同的數(shù)據(jù)，執(zhí)行兩次。第執(zhí)行兩次。第1次執(zhí)行用打印機(jī)報(bào)告某些出錯(cuò)信息，占用次執(zhí)行用打印機(jī)報(bào)告某些出錯(cuò)信息，占用10kB內(nèi)存；內(nèi)存；第第2次執(zhí)行中無出錯(cuò)數(shù)據(jù)，不用打印機(jī)，但至少需要次執(zhí)行中無出錯(cuò)數(shù)據(jù)，不用打印機(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 一個(gè)任務(wù)的一個(gè)任務(wù)的一次執(zhí)行一次執(zhí)行對(duì)應(yīng)對(duì)應(yīng)一個(gè)進(jìn)程一個(gè)進(jìn)程。第二章第二章 進(jìn)程管理進(jìn)程管理r (dynamic) ：是進(jìn)程最基本的特征。進(jìn)程有一定生命周期。是進(jìn)程最基本的特征。進(jìn)程有一定生命周期。程序是指一組有序指令集合，是靜態(tài)實(shí)體。程序是指一組有序指令集合，是靜態(tài)實(shí)體。r (concurrent) ：一段時(shí)間內(nèi)，多個(gè)進(jìn)程實(shí)體在內(nèi)存中可同時(shí)一段時(shí)間內(nèi)，多個(gè)進(jìn)程實(shí)體在內(nèi)存中可同時(shí)運(yùn)行。引入進(jìn)程的目的是為了能并發(fā)。程序不能并發(fā)。運(yùn)行。引入進(jìn)程

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

11、，稱為進(jìn)程控制塊（PCB）。）。如：鍵盤鍵入命令如：鍵盤鍵入命令 $date（二）（二） 進(jìn)程的特征進(jìn)程的特征動(dòng)態(tài)性動(dòng)態(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便可運(yùn)行?？山M成就緒隊(duì)列。便可運(yùn)行?？山M成就緒隊(duì)列。 2）執(zhí)行狀態(tài)）執(zhí)行狀態(tài)(Running)：已獲得：已獲得CPU正在運(yùn)行。在單處理機(jī)正在運(yùn)行。在單處理機(jī)系統(tǒng)中只能有一個(gè)。系統(tǒng)中只能有一個(gè)。 3）阻塞狀態(tài)）阻塞狀態(tài)(Blocked) ：因發(fā)生某事件（如：因發(fā)生某事件（如I/O、申請(qǐng)

12、緩沖區(qū)、申請(qǐng)緩沖區(qū)等）而暫停執(zhí)行。（等待、睡眠）?？捎卸鄠€(gè)此狀態(tài)進(jìn)程組等）而暫停執(zhí)行。（等待、睡眠）?？捎卸鄠€(gè)此狀態(tài)進(jìn)程組成一個(gè)或多個(gè)（由阻塞原因劃分）阻塞隊(duì)列。成一個(gè)或多個(gè)（由阻塞原因劃分）阻塞隊(duì)列。（三）進(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)程剛被建立，尚未送入就緒隊(duì)列的狀態(tài)。處于此狀態(tài)的進(jìn)程是不完全的，當(dāng)創(chuàng)建新進(jìn)隊(duì)列的狀態(tài)。處于此狀態(tài)的進(jìn)程是不完全的，當(dāng)創(chuàng)建新進(jìn)程的所有工作（分配進(jìn)程控制塊、分配內(nèi)存空間、對(duì)程的所有工作（分

13、配進(jìn)程控制塊、分配內(nèi)存空間、對(duì)PCB初始化等）完成后，操作系統(tǒng)就把該進(jìn)程送入就緒隊(duì)列。初始化等）完成后，操作系統(tǒng)就把該進(jìn)程送入就緒隊(duì)列。 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已將它從就緒隊(duì)列已將它從就緒隊(duì)列中移出時(shí)的狀態(tài)。處于該狀態(tài)的進(jìn)程不能再被調(diào)度執(zhí)行，中移出時(shí)的狀態(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)度(時(shí)間片到時(shí)間片到)I/O完完成成等等

14、I/O請(qǐng)請(qǐng)求求等等中斷中斷執(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)稱為 “活動(dòng)活動(dòng)” (active) ，掛起，掛起后稱為后稱為“靜止靜止” (static) 。有：。有：執(zhí)行執(zhí)行、活動(dòng)就緒活動(dòng)就緒、活動(dòng)阻塞活動(dòng)阻塞、靜止就緒靜止就緒、靜止阻塞靜止阻塞幾種狀態(tài)。由幾種狀態(tài)。由“活動(dòng)活動(dòng)”到到“靜止靜止”的操的操作稱為作稱為“掛起掛起”，由，由“靜止靜止”到到“活動(dòng)活動(dòng)”的操作稱為的操作稱為“激激活活”。見見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)先級(jí)優(yōu)先級(jí)阻塞原因阻塞原因程序地址程序地址同步機(jī)制同步機(jī)制資源清單資源清單鏈接指針鏈接指針第二章第二章 進(jìn)程管理進(jìn)程管理暫停暫停（斷點(diǎn)的處理（斷點(diǎn)的處理機(jī)環(huán)境保存）機(jī)環(huán)境保存）調(diào)度調(diào)度（查（查PC

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

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

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

20、進(jìn)程所在隊(duì)列的下一個(gè)進(jìn)程的一個(gè)進(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)程同時(shí)建立，同時(shí)撤消。與進(jìn)程同時(shí)建立，同時(shí)撤消。第二章第二章 進(jìn)程管理進(jìn)程管理 由于由于PCB經(jīng)常被系統(tǒng)訪問，尤其是被運(yùn)行頻率很高的進(jìn)經(jīng)常被系統(tǒng)訪問，尤其是被運(yùn)行頻率很高的進(jìn)程調(diào)度及分派程序訪問，故程調(diào)度及分派程序訪問，故PCB應(yīng)常駐內(nèi)存應(yīng)常駐內(nèi)存。系統(tǒng)將所有的。系統(tǒng)將所有的PCB組成若干鏈表（或隊(duì)列），存放在組成若干鏈表（或隊(duì)列），存放在OS中專門

21、開辟的中專門開辟的PCB區(qū)內(nèi)。區(qū)內(nèi)。 在一個(gè)系統(tǒng)中，常常含有固定數(shù)目的在一個(gè)系統(tǒng)中，常常含有固定數(shù)目的PCB。對(duì)它們要進(jìn)行。對(duì)它們要進(jìn)行有效的組織與管理。有效的組織與管理。 常用的方式為：常用的方式為：r 鏈接方式鏈接方式r 索引方式索引方式（三）（三） PCB的組織方式的組織方式(The organization way of PCB )第二章第二章 進(jìn)程管理進(jìn)程管理1）鏈接方式）鏈接方式：相同狀態(tài)的：相同狀態(tài)的PCB鏈接成一個(gè)隊(duì)列。鏈接成一個(gè)隊(duì)列。阻塞隊(duì)列指針阻塞隊(duì)列指針就緒隊(duì)列指針就緒隊(duì)列指針執(zhí)行指針執(zhí)行指針空閑隊(duì)列指針空閑隊(duì)列指針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)程控制的職能就是對(duì)系統(tǒng)中的全部進(jìn)程實(shí)行有效的進(jìn)程控制的職能就是對(duì)系統(tǒng)中的全部進(jìn)程實(shí)行有效的管理，是進(jìn)程管理中最基本的功能。管理，是進(jìn)程管理中最基本的功能。 其主要表現(xiàn)為：進(jìn)程的創(chuàng)建、撤銷以及進(jìn)程運(yùn)行中的其主要表現(xiàn)為

23、：進(jìn)程的創(chuàng)建、撤銷以及進(jìn)程運(yùn)行中的狀態(tài)轉(zhuǎn)換。狀態(tài)轉(zhuǎn)換。 進(jìn)程控制一般是由進(jìn)程控制一般是由中的中的實(shí)現(xiàn)。實(shí)現(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） 用戶登錄（如分時(shí)系統(tǒng)中）；用戶登錄（如分時(shí)系統(tǒng)中）； 作業(yè)調(diào)度（如批處理系統(tǒng)中）；作業(yè)調(diào)度（如批處理系統(tǒng)中）； 提供服務(wù)（運(yùn)行中的用戶程序提出某種請(qǐng)求，則系統(tǒng)提供服務(wù)（運(yùn)行中的用戶程

24、序提出某種請(qǐng)求，則系統(tǒng)創(chuàng)建進(jìn)程以完成請(qǐng)求，創(chuàng)建進(jìn)程以完成請(qǐng)求，如：打印文件如：打印文件）；）； 應(yīng)用請(qǐng)求（應(yīng)用進(jìn)程根據(jù)需要，為自己創(chuàng)建進(jìn)程）應(yīng)用請(qǐng)求（應(yīng)用進(jìn)程根據(jù)需要，為自己創(chuàng)建進(jìn)程）第二章第二章 進(jìn)程管理進(jìn)程管理 用于描述進(jìn)程家族關(guān)系（創(chuàng)建關(guān)系）的有向樹。結(jié)點(diǎn)代表用于描述進(jìn)程家族關(guān)系（創(chuàng)建關(guān)系）的有向樹。結(jié)點(diǎn)代表進(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)程被撤消時(shí)，必須歸還。撤消父進(jìn)程時(shí)，須先撤消其所有的子進(jìn)程。時(shí)，必須歸還。撤消父進(jìn)程時(shí)

25、，須先撤消其所有的子進(jìn)程。PCB中有家族關(guān)系表項(xiàng)，以標(biāo)識(shí)自己的父、子進(jìn)程。中有家族關(guān)系表項(xiàng)，以標(biāo)識(shí)自己的父、子進(jìn)程。（Process Graph）第二章第二章 進(jìn)程管理進(jìn)程管理0#1#p1p2p3p4Pn是系統(tǒng)引導(dǎo)自動(dòng)是系統(tǒng)引導(dǎo)自動(dòng)生成的進(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)中的第一個(gè)內(nèi)核化系統(tǒng)，創(chuàng)建系統(tǒng)中的第一個(gè)內(nèi)核態(tài)進(jìn)程（態(tài)進(jìn)程（idle進(jìn)程進(jìn)程，0號(hào)進(jìn)程）。號(hào)進(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的時(shí)候，調(diào)度程的時(shí)候，調(diào)度程序會(huì)選擇序會(huì)選擇0號(hào)進(jìn)程運(yùn)行號(hào)進(jìn)程運(yùn)行。0號(hào)進(jìn)程創(chuàng)號(hào)進(jìn)程創(chuàng)建建第一個(gè)用戶態(tài)進(jìn)程第一個(gè)用戶態(tài)進(jìn)程init進(jìn)程進(jìn)程(1#進(jìn)程進(jìn)程)m1# 它創(chuàng)建和監(jiān)控其他進(jìn)程的活動(dòng)它創(chuàng)建和監(jiān)控其他進(jìn)程的活動(dòng)。使用宏。使用宏INIT-TASK定義了進(jìn)程控定義了進(jìn)程控制塊，實(shí)現(xiàn)了進(jìn)程模型。制塊，實(shí)現(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)程號(hào)進(jìn)程號(hào) 功能功能：創(chuàng)建一個(gè)具有指定標(biāo)識(shí)符的進(jìn)程。構(gòu)造創(chuàng)

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

28、 Process）第二章第二章 進(jìn)程管理進(jìn)程管理q 正常結(jié)束（有一條表示進(jìn)程結(jié)束的指令）；正常結(jié)束（有一條表示進(jìn)程結(jié)束的指令）；q 異常結(jié)束（運(yùn)行中出現(xiàn)錯(cuò)誤或故障。如越界錯(cuò)誤、申異常結(jié)束（運(yùn)行中出現(xiàn)錯(cuò)誤或故障。如越界錯(cuò)誤、申請(qǐng)的內(nèi)存超過了系統(tǒng)所能提供的最大量等。）；請(qǐng)的內(nèi)存超過了系統(tǒng)所能提供的最大量等。）；q 外界干預(yù)（應(yīng)外界的請(qǐng)求而終止。如操作員或操作系外界干預(yù)（應(yīng)外界的請(qǐng)求而終止。如操作員或操作系統(tǒng)干預(yù)、父進(jìn)程請(qǐng)求、父進(jìn)程終止）統(tǒng)干預(yù)、父進(jìn)程請(qǐng)求、父進(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)程號(hào)進(jìn)程號(hào)返回：返回：成功或失敗標(biāo)記成功或失敗標(biāo)記功能：功能：撤銷指定進(jìn)程的撤銷指定進(jìn)程的PCB，收回該進(jìn)程擁有的全部資源。，收回該進(jìn)程擁有的全部資源。步驟：步驟：n1）由標(biāo)識(shí)符，在）由標(biāo)識(shí)符，在PCB集中檢索其集中檢索其PCB，讀取狀態(tài)；，讀取狀態(tài)；n2）若）若“執(zhí)行執(zhí)行”則終止運(yùn)行，并進(jìn)行進(jìn)程調(diào)度。則終止運(yùn)行，并進(jìn)行進(jìn)程調(diào)度。n3）查其子孫進(jìn)程，若有則對(duì)其）查其子孫進(jìn)程，若有則對(duì)其Destroy（）；（）；n4）歸還資源給父進(jìn)程或系統(tǒng)；）歸還資源給父進(jìn)程或系統(tǒng)；n5）將被終止進(jìn)程的）將

30、被終止進(jìn)程的PCB從所在隊(duì)列中移出；從所在隊(duì)列中移出；第二章第二章 進(jìn)程管理進(jìn)程管理u 請(qǐng)求系統(tǒng)服務(wù)。若請(qǐng)求請(qǐng)求系統(tǒng)服務(wù)。若請(qǐng)求未滿足，則阻塞；當(dāng)資源可以滿足未滿足，則阻塞；當(dāng)資源可以滿足時(shí)，由釋放該資源的進(jìn)程將阻塞進(jìn)程喚醒；時(shí)，由釋放該資源的進(jìn)程將阻塞進(jìn)程喚醒；u 啟動(dòng)某種操作啟動(dòng)某種操作。等待其完成。等待其完成。u 新數(shù)據(jù)未到達(dá)。多進(jìn)程合作時(shí)，本進(jìn)程要用的其它進(jìn)程的新數(shù)據(jù)未到達(dá)。多進(jìn)程合作時(shí)，本進(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（）（）實(shí)現(xiàn)。實(shí)現(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)阻塞隊(duì)列；，插入相應(yīng)阻塞隊(duì)列；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)后列入阻塞隊(duì)狀態(tài)后列入阻塞隊(duì)

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

33、查、修改狀態(tài)。）檢查、修改狀態(tài)。“活動(dòng)就緒活動(dòng)就緒”“靜止就緒靜止就緒”；“活動(dòng)活動(dòng)阻塞阻塞” “靜止阻塞靜止阻塞”；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（）（）實(shí)現(xiàn)。實(shí)現(xiàn)。q 1）將進(jìn)程調(diào)入內(nèi)存，改狀態(tài)。）將進(jìn)程調(diào)入內(nèi)存，改狀態(tài)?！办o止靜止” “活動(dòng)活動(dòng)”;q 2）若新狀態(tài)為）若新狀態(tài)為“活動(dòng)就緒活動(dòng)就緒”則根據(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)程管理 同處于一個(gè)系統(tǒng)中的進(jìn)程間可能存在兩種關(guān)系：同處于一個(gè)系統(tǒng)中的進(jìn)程間可能存在兩種關(guān)系：1）間接相互制約關(guān)系：間接相互制約關(guān)系：因多進(jìn)程共享某資源而產(chǎn)生。此時(shí)進(jìn)因多進(jìn)程共

35、享某資源而產(chǎn)生。此時(shí)進(jìn)程同步要保證進(jìn)程能互斥地訪問臨界資源。為此資源要由系統(tǒng)程同步要保證進(jìn)程能互斥地訪問臨界資源。為此資源要由系統(tǒng)統(tǒng)一分配。統(tǒng)一分配。 進(jìn)程互斥時(shí)他們的執(zhí)行順序是可以任意的，通過共享資源進(jìn)程互斥時(shí)他們的執(zhí)行順序是可以任意的，通過共享資源實(shí)現(xiàn)相互制約實(shí)現(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)生。此時(shí)進(jìn)程同步要保證進(jìn)程在執(zhí)行次序上的協(xié)調(diào)。時(shí)進(jìn)程同步要保證進(jìn)程在執(zhí)行次序上的協(xié)調(diào)。 進(jìn)程同步指進(jìn)程同步指

36、并發(fā)進(jìn)程，其各自執(zhí)行結(jié)果互為對(duì)方的執(zhí)并發(fā)進(jìn)程，其各自執(zhí)行結(jié)果互為對(duì)方的執(zhí)行條件，從而限制各進(jìn)程執(zhí)行速度。行條件，從而限制各進(jìn)程執(zhí)行速度。進(jìn)程進(jìn)程。進(jìn)程進(jìn)程。相互清相互清楚對(duì)方的存在及其作用，交換信息。楚對(duì)方的存在及其作用，交換信息。計(jì)算進(jìn)程計(jì)算進(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)程時(shí)間次序上受到某種限制時(shí)間次序上受到某種限制競爭到某一物理資源時(shí)不允許進(jìn)程競爭到某一物理資源時(shí)不允許進(jìn)程工作工作相互清楚對(duì)方的存在及作用，相互清楚對(duì)方的存在及作用，交換信息交換信息不一定清

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

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

39、化為：（R表示寄存器，設(shè)表示寄存器，設(shè)count初值為初值為1）例例1： 兩個(gè)并發(fā)執(zhí)行的進(jìn)程兩個(gè)并發(fā)執(zhí)行的進(jìn)程A、B。A：R1=count R1=R1+1 count=R1B：R2=count R2=R2-1 count=R2n若執(zhí)行次序?yàn)椋喝魣?zhí)行次序?yàn)椋篈(1) A(2) A(3) B(1) B(2) B(3) 則則count=1n若執(zhí)行次序?yàn)椋喝魣?zhí)行次序?yàn)椋篈(1) B(1) A(2) A(3) B(2) B(3) 則則count=0n若執(zhí)行次序?yàn)椋喝魣?zhí)行次序?yàn)椋篈(1) B(1) B(2) B(3) A(2) A(3) 則則count=2第二章第二章 進(jìn)程管理進(jìn)程管理?xiàng)Ｖ羔槥闂Ｖ羔槥閠o

40、p，設(shè)有兩個(gè)程序段設(shè)有兩個(gè)程序段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隨機(jī) a b e f第二章第二章 進(jìn)程管理進(jìn)程管理 對(duì)對(duì)臨界資源，多進(jìn)程必須互斥訪問。把每個(gè)進(jìn)程臨界資源，多進(jìn)程必須互斥訪問。把每個(gè)進(jìn)程的那段的那段稱為稱為CS。 對(duì)臨界資源的互斥訪問即為多進(jìn)程互斥進(jìn)入各自的臨對(duì)臨界資源的互

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;為實(shí)現(xiàn)進(jìn)程互斥進(jìn)入為實(shí)現(xiàn)進(jìn)程互斥進(jìn)入自己的臨界區(qū)，采用自己的臨界區(qū)，采用進(jìn)行協(xié)調(diào)。進(jìn)行協(xié)調(diào)。第二章第二章 進(jìn)程管理進(jìn)程管理 OS利用同步機(jī)制提供互斥工具才能保證進(jìn)程互斥的進(jìn)入臨界利用同步機(jī)制提供互斥工具才能保證進(jìn)程互斥的進(jìn)入臨界區(qū)，互斥工具應(yīng)能保證如下幾點(diǎn)：區(qū)，互斥工具應(yīng)能保證如下幾點(diǎn)：1）：若臨界資源空閑，則允許一個(gè)請(qǐng)求進(jìn)程進(jìn)入自己的臨界區(qū)。若臨界資源空閑，則允許一個(gè)請(qǐng)求進(jìn)程進(jìn)入自己的臨界區(qū)。2）：若臨界資源正被使用，則其它申請(qǐng)?jiān)撡Y源的進(jìn)程

43、應(yīng)該等待。若臨界資源正被使用，則其它申請(qǐng)?jiān)撡Y源的進(jìn)程應(yīng)該等待。3）：保證進(jìn)程可在有限時(shí)間內(nèi)進(jìn)入自己的臨界區(qū)，防止保證進(jìn)程可在有限時(shí)間內(nèi)進(jìn)入自己的臨界區(qū)，防止“死等死等”。4）：當(dāng)進(jìn)程需臨界資源不能滿足而等待時(shí)，應(yīng)釋放當(dāng)進(jìn)程需臨界資源不能滿足而等待時(shí)，應(yīng)釋放CPU，防止，防止“忙等忙等” 互斥工具有軟件、硬件和信號(hào)量幾種方法?；コ夤ぞ哂熊浖?、硬件和信號(hào)量幾種方法。（三）同步機(jī)制應(yīng)遵循的原則（三）同步機(jī)制應(yīng)遵循的原則第二章第二章 進(jìn)程管理進(jìn)程管理設(shè)兩個(gè)進(jìn)程設(shè)兩個(gè)進(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)程管理例：例：利用鎖變量方法實(shí)現(xiàn)兩個(gè)進(jìn)程利用鎖變量方法實(shí)現(xiàn)兩個(gè)進(jìn)程A A、B B互斥互斥共享共享打印機(jī)打印機(jī)。進(jìn)程進(jìn)程ALock(W);打印信息打印信息S；/*CS區(qū)區(qū)*/Unlock(W);進(jìn)程進(jìn)程BLock(W);打印信息打印信息S；/*CS區(qū)區(qū)*/Unlock(W);：簡單；：簡單；：不安全，因?yàn)殛P(guān)鎖和開鎖操作不具有不安全，因?yàn)殛P(guān)鎖和開鎖操作不具有原子性

46、原子性。 出現(xiàn)出現(xiàn)“忙等忙等”，軟件算法不能完全解決多個(gè)進(jìn)程互斥問題，算法復(fù)雜，效率較軟件算法不能完全解決多個(gè)進(jìn)程互斥問題，算法復(fù)雜，效率較低。低。以變量以變量W表示鎖，置初值表示鎖，置初值為為0。兩個(gè)進(jìn)程的部分代碼如下。兩個(gè)進(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實(shí)現(xiàn)進(jìn)程互斥實(shí)現(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è)資源可用。缺點(diǎn)缺點(diǎn)：不能：不能“讓權(quán)等待讓權(quán)等待”，是一種是一種“忙等忙等” 更好的方法是當(dāng)臨界資源不可用時(shí)，就阻塞該進(jìn)程，直更好的方法是當(dāng)臨界資源不可用時(shí)，就阻塞該

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

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

50、Semaphore） 記錄型信號(hào)量所含內(nèi)容記錄型信號(hào)量所含內(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為一個(gè)進(jìn)程鏈表為一個(gè)進(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)有兩臺(tái)打印機(jī)，有多個(gè)需要執(zhí)行打印操作的進(jìn)例：系統(tǒng)有兩臺(tái)打印機(jī)，有多個(gè)需要執(zhí)行打印操作的進(jìn)程，描述各個(gè)進(jìn)程的執(zhí)行。程，描述各個(gè)進(jìn)程的執(zhí)行。 s第二章第二章 進(jìn)程管理進(jìn)程管理 1）s.value的的。s.L表示該表示該資源的阻塞隊(duì)列。資源的阻塞隊(duì)列。 2）wait()表示請(qǐng)求一個(gè)單位的資源。表示請(qǐng)求一個(gè)單位的資源。s.value-1表示該資源表示該資源數(shù)減數(shù)減1。若。若s.value0，則資源已用完，調(diào)用阻塞原語。此時(shí)的，則資源已

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

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

54、少wait，則？缺少，則？缺少signal，則？，則？一個(gè)互斥信號(hào)量一個(gè)互斥信號(hào)量mutex實(shí)現(xiàn)進(jìn)程實(shí)現(xiàn)進(jìn)程P1和和P2互斥的描述為：互斥的描述為：第二章第二章 進(jìn)程管理進(jìn)程管理實(shí)例：三個(gè)進(jìn)程執(zhí)行中要共享變量實(shí)例：三個(gè)進(jìn)程執(zhí)行中要共享變量count。count屬于臨界資源，對(duì)其應(yīng)互斥訪問。屬于臨界資源，對(duì)其應(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)程管理（六）信號(hào)量應(yīng)用之二（六）信號(hào)量應(yīng)用之二 利用信號(hào)量可以控制進(jìn)程執(zhí)行的先后次序，以描述程序利用信號(hào)量可以控制進(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ì)算進(jìn)程計(jì)算進(jìn)程、打印進(jìn)程打印進(jìn)程實(shí)現(xiàn)合作。實(shí)現(xiàn)合作。計(jì)算進(jìn)程計(jì)算進(jìn)程不斷把每次計(jì)算結(jié)不斷把每次計(jì)算結(jié)果果放入放入buf中，中，打印進(jìn)程打印進(jìn)程則則取出取出buf中的數(shù)據(jù)打印輸出，若不采取任中的數(shù)據(jù)打印輸出，若

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

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

59、號(hào)空信號(hào)可用信號(hào)量表示?？捎眯盘?hào)量表示。（二）問題分析（二）問題分析同同 步步 機(jī)機(jī) 制制第二章第二章 進(jìn)程管理進(jìn)程管理 S Sempty empty ：是是PpPp進(jìn)程運(yùn)行結(jié)束發(fā)送的信號(hào)量，是進(jìn)程運(yùn)行結(jié)束發(fā)送的信號(hào)量，是PcPc運(yùn)行運(yùn)行需要等待的信號(hào)量，用于判斷需要等待的信號(hào)量，用于判斷BufBuf是否為空。若空則為是否為空。若空則為1 1，否則為，否則為0 0。 S Sfullfull：是是PcPc進(jìn)程運(yùn)行結(jié)束發(fā)送的信號(hào)量，是進(jìn)程進(jìn)程運(yùn)行結(jié)束發(fā)送的信號(hào)量，是進(jìn)程PpPp運(yùn)行需要使用的信號(hào)量，用于判斷運(yùn)行需要使用的信號(hào)量，用于判斷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è)置兩個(gè)信號(hào)量：設(shè)置兩個(gè)信號(hào)量：Sempty 和和 Sfull第二章第二章 進(jìn)程管理進(jìn)程管理計(jì)算進(jìn)程計(jì)算進(jìn)程C打印進(jìn)程打印進(jìn)程P計(jì)計(jì) 算算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ā)送的信號(hào)量，只與制約進(jìn)程及被制約進(jìn)程有關(guān)。信號(hào)量，只與制約進(jìn)程及被制約進(jìn)程有關(guān)。 一個(gè)進(jìn)程一個(gè)進(jìn)程PiPi的私有信號(hào)量是從制約進(jìn)程的私