操作系統(tǒng)課件o第二章

1、第二章第二章 進(jìn)程管理進(jìn)程管理 Process Management 在傳統(tǒng)操作系統(tǒng)中，資源分配和獨(dú)立運(yùn)行的基本單在傳統(tǒng)操作系統(tǒng)中，資源分配和獨(dú)立運(yùn)行的基本單位是位是進(jìn)程進(jìn)程。OSOS的四大特征也都是基于進(jìn)程而形成的。的四大特征也都是基于進(jìn)程而形成的。 進(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)容組成。 學(xué)習(xí)目標(biāo) 在多道程序環(huán)境下，程序不能獨(dú)立運(yùn)行。作為資源分配和在多道程序環(huán)境下，程序不能獨(dú)立運(yùn)行。作為資源分配和獨(dú)立運(yùn)

2、行的基本單位是進(jìn)程。操作系統(tǒng)所有的特征都是基獨(dú)立運(yùn)行的基本單位是進(jìn)程。操作系統(tǒng)所有的特征都是基于進(jìn)程而體現(xiàn)的。所以，本章的主要問(wèn)題是：于進(jìn)程而體現(xiàn)的。所以，本章的主要問(wèn)題是： 進(jìn)程的概念進(jìn)程的概念進(jìn)程的實(shí)體、狀態(tài)及狀態(tài)的演變進(jìn)程的實(shí)體、狀態(tài)及狀態(tài)的演變進(jìn)程的控制與調(diào)度進(jìn)程的控制與調(diào)度進(jìn)程之間的關(guān)系協(xié)調(diào)進(jìn)程之間的關(guān)系協(xié)調(diào)進(jìn)程的通信進(jìn)程的通信死鎖問(wèn)題及解決死鎖問(wèn)題及解決本章主要內(nèi)容 進(jìn)程的基本概念進(jìn)程的基本概念 進(jìn)程控制進(jìn)程控制 進(jìn)程同步進(jìn)程同步 經(jīng)典進(jìn)程同步問(wèn)題經(jīng)典進(jìn)程同步問(wèn)題 管程機(jī)制管程機(jī)制 進(jìn)程通信進(jìn)程通信 線程線程進(jìn)程引入 操作系統(tǒng)的基本特性是并發(fā)與共享，即在系統(tǒng)中操作系統(tǒng)的基本特性是并

3、發(fā)與共享，即在系統(tǒng)中（內(nèi)存）同時(shí)存在幾個(gè)相互獨(dú)立的程序，這些程（內(nèi)存）同時(shí)存在幾個(gè)相互獨(dú)立的程序，這些程序在系統(tǒng)中既交叉地運(yùn)行，又要共享系統(tǒng)中的資序在系統(tǒng)中既交叉地運(yùn)行，又要共享系統(tǒng)中的資源，這就會(huì)引起一系列的問(wèn)題，包括：對(duì)資源的源，這就會(huì)引起一系列的問(wèn)題，包括：對(duì)資源的競(jìng)爭(zhēng)、運(yùn)行程序之間的通信、程序之間的合作與競(jìng)爭(zhēng)、運(yùn)行程序之間的通信、程序之間的合作與協(xié)同等。協(xié)同等。 要解決這些問(wèn)題，用程序的概念已經(jīng)不能描述程要解決這些問(wèn)題，用程序的概念已經(jīng)不能描述程序在內(nèi)存中運(yùn)行的狀態(tài)，必須引入新的概念序在內(nèi)存中運(yùn)行的狀態(tài)，必須引入新的概念進(jìn)程。進(jìn)程。2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The

4、basic concept of process一、前趨圖一、前趨圖 (Precedence Graph) 有向有向（DAG）。結(jié)點(diǎn)表示一條語(yǔ)句、一個(gè)程序段）。結(jié)點(diǎn)表示一條語(yǔ)句、一個(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 前趨圖示例前趨圖示例 二、程序順序執(zhí)行二、程序順序執(zhí)行(Sequential Execution of Program) 程序執(zhí)行時(shí)，僅當(dāng)前一操作完成后，才能執(zhí)行后繼操作。程序執(zhí)行時(shí)，僅當(dāng)前一操作

5、完成后，才能執(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) 三、程序并發(fā)執(zhí)行三、程序并發(fā)執(zhí)行(Concurrent Execution of Program )1 思想：思想：以輸入、計(jì)算、打印三個(gè)操作為例：以輸入、計(jì)算、打印三個(gè)操作為例： 對(duì)于某一作業(yè)的三個(gè)操作必存在順序關(guān)系，但多個(gè)作對(duì)于某一作業(yè)的三個(gè)

6、操作必存在順序關(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 例：例：s1：a:=x+2 s2：b:=y+1 s3： c:=a+b s4：d:=c+6 S1S4S3S22 特征特征：間斷性；：間斷性； 失去封閉性；失去封閉性；如果程序執(zhí)行的結(jié)果是一個(gè)與時(shí)間無(wú)關(guān)如果程序執(zhí)行的結(jié)果是一個(gè)與時(shí)間無(wú)關(guān)的

7、函數(shù)，即具有封閉性。的函數(shù)，即具有封閉性。 不可再現(xiàn)性。不可再現(xiàn)性。S1、S2可并發(fā)執(zhí)行可并發(fā)執(zhí)行例：有程序例：有程序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 12.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The basic concept of proce

8、ss四、并發(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()= R()W()=x Bernstein條件條件：若兩個(gè)程序（進(jìn)程）若兩個(gè)程序（進(jìn)程）p1、p2能滿足下述條能滿足下述條件，則它

9、們便能并發(fā)執(zhí)行，且具有可再現(xiàn)性：件，則它們便能并發(fā)執(zhí)行，且具有可再現(xiàn)性： R(p1)W(p2)R(p2) W(p1) W(p1) W(p2) = 可理解為：可理解為： 兩程序互不把對(duì)方的結(jié)果作為輸入，且兩程序互不把對(duì)方的結(jié)果作為輸入，且不改變同一個(gè)量。不改變同一個(gè)量。例例（一）進(jìn)程的引入（一）進(jìn)程的引入 用戶角度看，作業(yè)由若干子任務(wù)（子任務(wù)的指令或命令描述稱用戶角度看，作業(yè)由若干子任務(wù)（子任務(wù)的指令或命令描述稱為為正文段正文段）組成，只有子任務(wù)被執(zhí)行時(shí)才能體現(xiàn)任務(wù)的功能。）組成，只有子任務(wù)被執(zhí)行時(shí)才能體現(xiàn)任務(wù)的功能。 “任務(wù)任務(wù)”和和“任務(wù)的執(zhí)行任務(wù)的執(zhí)行”截然不同。前者是任務(wù)的靜態(tài)描述，截然

10、不同。前者是任務(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í)行中無(wú)出錯(cuò)數(shù)據(jù)，不用打印機(jī)，但至少需要次執(zhí)行中無(wú)出錯(cuò)數(shù)據(jù)，不用打印機(jī)，但至少需要6kB主存。主存。 五、進(jìn)程的描述五、進(jìn)程的描述 (The description of process)2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The basic concept of proce

11、ssr 一個(gè)任務(wù)的一個(gè)任務(wù)的一次執(zhí)行一次執(zhí)行對(duì)應(yīng)對(duì)應(yīng)一個(gè)進(jìn)程一個(gè)進(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)程的目的是為了能并發(fā)。程序不能并發(fā)。r 獨(dú)立性獨(dú)立性(independent) ：進(jìn)程是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立獲得資源、獨(dú)進(jìn)程是一個(gè)能獨(dú)立運(yùn)行、獨(dú)立獲得資源、獨(dú)立調(diào)度的基本單位。程序

12、不能做為一個(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)，稱為進(jìn)程控制塊（PCB）。）。進(jìn)程實(shí)體進(jìn)程實(shí)體=數(shù)據(jù)段數(shù)據(jù)段+程序段程序段+PCB如：鍵盤鍵入命令如：鍵盤鍵入命令 $date（二）（二） 進(jìn)程的特征進(jìn)程的特征動(dòng)態(tài)性動(dòng)態(tài)性并發(fā)

13、性并發(fā)性1 三種基本狀態(tài)：三種基本狀態(tài)： 1）就緒狀態(tài)）就緒狀態(tài)(Ready )：進(jìn)程已分配到除：進(jìn)程已分配到除CPU外的所有資源。外的所有資源。只等只等CPU便可運(yùn)行。可組成就緒隊(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)緩沖區(qū)、申請(qǐng)緩沖區(qū)等）而暫停執(zhí)行。（等待、睡眠）?？捎卸鄠€(gè)此狀態(tài)進(jìn)程組等）而暫停執(zhí)行。（等待、睡眠）?？捎卸鄠€(gè)此狀態(tài)進(jìn)程組成一個(gè)或多個(gè)（由阻塞原因劃分）阻塞

14、隊(duì)列。成一個(gè)或多個(gè)（由阻塞原因劃分）阻塞隊(duì)列。（三）進(jìn)程的基本狀態(tài)（三）進(jìn)程的基本狀態(tài) (The basic states of process )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ì)程的所有工作（分配進(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 sta

15、te) ：指進(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)程調(diào)度進(jìn)程調(diào)度(時(shí)間片到時(shí)間片到)I/O完完成成等等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)三種基本狀態(tài)的變換體現(xiàn)了三種基本狀態(tài)的變換體現(xiàn)了OS的資源管理作用。

16、的資源管理作用。進(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)換： 1） 進(jìn)程掛起的原因進(jìn)程掛起的原因（reasons for process suspenson）4 進(jìn)程的掛起狀態(tài)進(jìn)程的掛起狀態(tài)(The suspended state of process) 2) 狀態(tài)的轉(zhuǎn)換狀態(tài)的轉(zhuǎn)換 引入掛起狀態(tài)后，原狀態(tài)稱為引入掛起狀態(tài)后，原狀態(tài)稱為 “活動(dòng)活動(dòng)” (active) ，掛起，掛起后稱為后稱為“靜止靜止” (static) 。有：。有

17、：執(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 State Transition Diagram with Suspend States第二章第二章 進(jìn)程管理進(jìn)程管理六、進(jìn)程控制塊六、進(jìn)程控制塊( Process Control Block)（一）（一）PCB的作用的作用作用：作用：使一個(gè)在多道程序環(huán)境下不能獨(dú)立使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序

18、，變成一個(gè)能獨(dú)立運(yùn)行的基本運(yùn)行的程序，變成一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。 PCB是是OS中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。它記錄了它記錄了OS所需的用于描述進(jìn)程情況及控制所需的用于描述進(jìn)程情況及控制進(jìn)程運(yùn)行的全部信息。進(jìn)程運(yùn)行的全部信息。pid進(jìn)程狀態(tài)進(jìn)程狀態(tài)現(xiàn)場(chǎng)現(xiàn)場(chǎng)優(yōu)先級(jí)優(yōu)先級(jí)阻塞原因阻塞原因程序地址程序地址同步機(jī)制同步機(jī)制資源清單資源清單鏈接指針鏈接指針2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 The basic concept of process暫停暫停（斷點(diǎn)的處理（斷點(diǎn)的處理機(jī)環(huán)境保存）機(jī)環(huán)境保存

19、）調(diào)度調(diào)度（查（查PCB的優(yōu)先的優(yōu)先級(jí)及現(xiàn)場(chǎng)狀態(tài)）級(jí)及現(xiàn)場(chǎng)狀態(tài)）執(zhí)行執(zhí)行（查（查PCB中處理機(jī)的狀中處理機(jī)的狀態(tài)信息，恢復(fù)現(xiàn)場(chǎng)）態(tài)信息，恢復(fù)現(xiàn)場(chǎng)）執(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)。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)成，便于

20、記憶。外部標(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)場(chǎng)。可有通用寄存器、指令計(jì)數(shù)器、程序狀態(tài)字復(fù)現(xiàn)場(chǎng)?？捎型ㄓ眉拇嫫?、指令計(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)程優(yōu)先級(jí)

21、、事件、與調(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)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ì)列的下部資源及已分配的資源）、鏈接指針（本進(jìn)程所在隊(duì)列的下一個(gè)進(jìn)程的一個(gè)進(jìn)程的P

22、CB首址）。首址）。說(shuō)明：說(shuō)明：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í)撤消。 由于由于PCB經(jīng)常被系統(tǒng)訪問(wèn)，尤其是被運(yùn)行頻率很高的進(jìn)經(jīng)常被系統(tǒng)訪問(wèn)，尤其是被運(yùn)行頻率很高的進(jìn)程調(diào)度及分派程序訪問(wèn)，故程調(diào)度及分派程序訪問(wèn)，故PCB應(yīng)常駐內(nèi)存應(yīng)常駐內(nèi)存。系統(tǒng)將所有的。系統(tǒng)將所有的PCB組成若干鏈表（或隊(duì)列），存放在組成若干鏈表（或隊(duì)列），存放在OS中專門開辟的中專門開辟的PCB區(qū)內(nèi)。區(qū)內(nèi)。 在一個(gè)系統(tǒng)中，常常含有固定數(shù)目

23、的在一個(gè)系統(tǒng)中，常常含有固定數(shù)目的PCB。對(duì)它們要進(jìn)行。對(duì)它們要進(jìn)行有效的組織與管理。有效的組織與管理。 常用的方式為：常用的方式為：r 鏈接方式鏈接方式r 索引方式索引方式（三）（三） PCB的組織方式的組織方式(The organization way of PCB )1）鏈接方式）鏈接方式：相同狀態(tài)的：相同狀態(tài)的PCB鏈接成一個(gè)隊(duì)列。鏈接成一個(gè)隊(duì)列。阻塞隊(duì)列指針阻塞隊(duì)列指針就緒隊(duì)列指針就緒隊(duì)列指針執(zhí)行指針執(zhí)行指針空閑隊(duì)列指針空閑隊(duì)列指針PCB2PCB3PCB4PCB5PCB1PCB6PCB7PCB8PCB9430917082）索引方式）索引方式：相同狀態(tài)的：相同狀態(tài)的PCB建立一張索引表

24、。建立一張索引表。執(zhí)行指針執(zhí)行指針就緒表指針就緒表指針阻塞表指針阻塞表指針PCB1PCB7PCB2PCB3PCB4PCB5PCB6就緒索引表就緒索引表阻塞索引表阻塞索引表2.2 進(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)為：進(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)程創(chuàng)建一、進(jìn)程創(chuàng)建（The creating of

25、 ProcessThe creating of Process）（reasons for process creation） 用戶登錄（如分時(shí)系統(tǒng)中，合法用戶進(jìn)入，則系統(tǒng)為用戶登錄（如分時(shí)系統(tǒng)中，合法用戶進(jìn)入，則系統(tǒng)為之創(chuàng)建進(jìn)程）；之創(chuàng)建進(jìn)程）； 作業(yè)調(diào)度（如批處理系統(tǒng)中）；作業(yè)調(diào)度（如批處理系統(tǒng)中）； 提供服務(wù)（運(yùn)行中的用戶程序提出某種請(qǐng)求，則系統(tǒng)提供服務(wù)（運(yùn)行中的用戶程序提出某種請(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)程家族關(guān)系（創(chuàng)建關(guān)系）的有向

26、樹。結(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í)，須先撤消其所有的子進(jìn)程。PCB中有家族關(guān)系表項(xiàng)，以標(biāo)識(shí)自己的父、子進(jìn)程。中有家族關(guān)系表項(xiàng)，以標(biāo)識(shí)自己的父、子進(jìn)程。（Process Graph）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)中的

27、進(jìn)程樹 Linux內(nèi)核被加載在內(nèi)存后，開始內(nèi)核被加載在內(nèi)存后，開始初始化系統(tǒng)，為運(yùn)行進(jìn)程搭好各種平初始化系統(tǒng)，為運(yùn)行進(jìn)程搭好各種平臺(tái)，創(chuàng)建系統(tǒng)中的第一個(gè)內(nèi)核態(tài)進(jìn)程臺(tái)，創(chuàng)建系統(tǒng)中的第一個(gè)內(nèi)核態(tài)進(jìn)程（idle進(jìn)程進(jìn)程，0號(hào)進(jìn)程）。號(hào)進(jìn)程）。p 0#是所有進(jìn)程的祖先。由它執(zhí)行是所有進(jìn)程的祖先。由它執(zhí)行cpu_idle()函數(shù)，當(dāng)沒(méi)有其他進(jìn)程處于函數(shù)，當(dāng)沒(méi)有其他進(jìn)程處于TASK_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)程)。p1# 它創(chuàng)建和監(jiān)控其他進(jìn)程的活動(dòng)它創(chuàng)建和監(jiān)控其他進(jìn)程的

28、活動(dòng)。使用宏使用宏INIT-TASK定義了進(jìn)程控制塊定義了進(jìn)程控制塊，實(shí)現(xiàn)了進(jìn)程模型。，實(shí)現(xiàn)了進(jìn)程模型。 由進(jìn)程由進(jìn)程創(chuàng)建原語(yǔ)創(chuàng)建原語(yǔ)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)建一個(gè)具有指定標(biāo)識(shí)符的進(jìn)程。構(gòu)造PCB，使該，使該P(yáng)CB進(jìn)入就緒隊(duì)列，使用進(jìn)入就緒隊(duì)列，使用Creat原語(yǔ)的進(jìn)程即為新進(jìn)程的父進(jìn)程。原語(yǔ)的進(jìn)程即為新進(jìn)程的父進(jìn)程。 步驟步驟：1）申請(qǐng)空白）申請(qǐng)空白PCB：分配唯一標(biāo)識(shí)符，并從：分配唯一標(biāo)識(shí)符，并從PCB集合

29、中索取一空集合中索取一空白白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 Process）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)存超過(guò)了系統(tǒng)所能提供的最大量等。）；請(qǐng)的內(nèi)存超過(guò)了系統(tǒng)所

30、能提供的最大量等。）；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)由進(jìn)程由進(jìn)程終止原語(yǔ)終止原語(yǔ)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)程擁有的全部資源步驟：步驟：1）由標(biāo)識(shí)符，在）由標(biāo)識(shí)符，在PCB集中檢索其集中

31、檢索其PCB，讀取狀態(tài)；，讀取狀態(tài)；2）若）若“執(zhí)行執(zhí)行”則終止運(yùn)行，并進(jìn)行進(jìn)程調(diào)度。則終止運(yùn)行，并進(jìn)行進(jìn)程調(diào)度。3）查其子孫進(jìn)程，若有則對(duì)其）查其子孫進(jìn)程，若有則對(duì)其Destroy（）；（）；4）歸還資源給父進(jìn)程或系統(tǒng)；）歸還資源給父進(jìn)程或系統(tǒng)；5）將被終止進(jìn)程的）將被終止進(jìn)程的PCB從所在隊(duì)列中移出；從所在隊(duì)列中移出；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)程要用

32、的其它進(jìn)程的新數(shù)據(jù)未到達(dá)。多進(jìn)程合作時(shí)，本進(jìn)程要用的其它進(jìn)程的結(jié)果尚未到來(lái)。結(jié)果尚未到來(lái)。u 無(wú)新工作可做。某些系統(tǒng)進(jìn)程，等待工作的到達(dá)。無(wú)新工作可做。某些系統(tǒng)進(jìn)程，等待工作的到達(dá)。三三、進(jìn)程的阻塞與喚醒、進(jìn)程的阻塞與喚醒(TheThe block and wakeup of Process )由由阻塞原語(yǔ)阻塞原語(yǔ)Block（）（）實(shí)現(xiàn)。實(shí)現(xiàn)。正在執(zhí)行的進(jìn)程本身調(diào)用正在執(zhí)行的進(jìn)程本身調(diào)用BlockBlock， 1）停止進(jìn)程的執(zhí)行；）停止進(jìn)程的執(zhí)行； 2）改狀態(tài)）改狀態(tài)“執(zhí)行執(zhí)行”為為“阻塞阻塞”，插入相應(yīng)阻塞隊(duì)列；，插入相應(yīng)阻塞隊(duì)列； 3）重新調(diào)度（進(jìn)行切換，即保留現(xiàn)場(chǎng)，重設(shè)現(xiàn)場(chǎng)）。）重新調(diào)度

33、（進(jìn)行切換，即保留現(xiàn)場(chǎng)，重設(shè)現(xiàn)場(chǎng)）。 BLOCK( ) 輸入?yún)?shù)：輸入?yún)?shù)：無(wú)無(wú) 返回：返回：轉(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ì)列 由由喚醒原語(yǔ)喚醒原語(yǔ)Wakeup（）（）實(shí)現(xiàn)。實(shí)現(xiàn)。 由和由和阻塞原因相關(guān)阻塞原因相關(guā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從阻

34、塞隊(duì)列摘下，改狀態(tài)為就緒，從阻塞隊(duì)列摘下，改狀態(tài)為就緒，插入就緒隊(duì)列插入就緒隊(duì)列 注：注：BlockBlock和和WakeupWakeup是一對(duì)是一對(duì)的的 原語(yǔ)，兩者應(yīng)在原語(yǔ)，兩者應(yīng)在中中出現(xiàn)。出現(xiàn)。 即在某進(jìn)程中用到了阻塞，在與之相關(guān)即在某進(jìn)程中用到了阻塞，在與之相關(guān) 的另一進(jìn)程中一定要有喚醒。的另一進(jìn)程中一定要有喚醒。由由掛起原語(yǔ)掛起原語(yǔ)Suspend（）（）實(shí)現(xiàn)。實(shí)現(xiàn)。q 1）檢查、修改狀態(tài)。）檢查、修改狀態(tài)?！盎顒?dòng)就緒活動(dòng)就緒”“靜止就緒靜止就緒”；“活動(dòng)活動(dòng)阻塞阻塞” “靜止阻塞靜止阻塞”；q 2）若原狀態(tài)為）若原狀態(tài)為“執(zhí)行執(zhí)行”，則，則“執(zhí)行執(zhí)行” “靜止就緒靜止就緒”，并調(diào)，并

35、調(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ū)域;由由激活原語(yǔ)激活原語(yǔ)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)程的掛起與激活四、進(jìn)程的掛起與激活(The Suspend and Active of Process)2.3 進(jìn)程同步 Process Synchronization 進(jìn)程同步的主要任務(wù)是使并發(fā)執(zhí)行的諸進(jìn)程進(jìn)程同

36、步的主要任務(wù)是使并發(fā)執(zhí)行的諸進(jìn)程間能有效地共享資源和相互合作，從而使程序的間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。執(zhí)行具有可再現(xià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)程共享某資源而產(chǎn)生。此時(shí)進(jìn)程同步要保證進(jìn)程能互斥地訪問(wèn)臨界資源。為此資源要由系統(tǒng)程同步要保證進(jìn)程能互斥地訪問(wèn)臨界資源。為此資源要由系統(tǒng)統(tǒng)一分配。統(tǒng)一分配。進(jìn)程互斥進(jìn)程互斥 進(jìn)程互斥時(shí)他們的執(zhí)行順序是可以任意的，通過(guò)共享資源進(jìn)程互斥時(shí)他們的執(zhí)行順序是可以任意的，通過(guò)共享資源實(shí)現(xiàn)相互制約

37、實(shí)現(xià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)程同步 進(jìn)程同步指進(jìn)程同步指并發(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)程

38、B同步與互斥比較同步與互斥比較同同 步步互互 斥斥進(jìn)程進(jìn)程 -進(jìn)程進(jìn)程進(jìn)程進(jìn)程 -資源資源 - 進(jìn)程進(jìn)程時(shí)間次序上受到某種限制時(shí)間次序上受到某種限制競(jìng)爭(zhēng)到某一物理資源時(shí)不允許進(jìn)程競(jìng)爭(zhēng)到某一物理資源時(shí)不允許進(jìn)程工作工作相互清楚對(duì)方的存在及作用，相互清楚對(duì)方的存在及作用，交換信息交換信息不一定清楚其進(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米接力，米接力，工廠流水線。工廠流水線。例：例：交通十字路口，籃球搶

39、籃板，交通十字路口，籃球搶籃板，進(jìn)程爭(zhēng)搶打印機(jī)。進(jìn)程爭(zhēng)搶打印機(jī)。（一）臨界資源（一）臨界資源( Critical resource) 若多進(jìn)程共享某臨界資源，則應(yīng)對(duì)其進(jìn)行同步控制，以若多進(jìn)程共享某臨界資源，則應(yīng)對(duì)其進(jìn)行同步控制，以實(shí)現(xiàn)對(duì)臨界資源的互斥訪問(wèn)。實(shí)現(xiàn)對(duì)臨界資源的互斥訪問(wèn)。 臨界資源可有硬、軟資源。臨界資源可有硬、軟資源。 硬件資源如：打印機(jī)等。硬件資源如：打印機(jī)等。諸進(jìn)程要互斥使用這些資源。諸進(jìn)程要互斥使用這些資源。 軟件資源如：共享變量等。軟件資源如：共享變量等。對(duì)共享變量應(yīng)作為臨界資源對(duì)共享變量應(yīng)作為臨界資源處理。即要對(duì)它進(jìn)行互斥訪問(wèn)。處理。即要對(duì)它進(jìn)行互斥訪問(wèn)。 進(jìn)程進(jìn)程A：生

40、產(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ì)化為：（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)

41、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例例2：abef a b e f隨機(jī) a b e f 對(duì)對(duì)臨界資源，多進(jìn)程必須互斥訪問(wèn)。把每個(gè)進(jìn)程臨界資源，多進(jìn)程必須互斥訪問(wèn)。把每個(gè)進(jìn)程訪問(wèn)訪問(wèn)臨界資源臨界資源的那段的那段代碼代碼稱為稱為臨界區(qū)臨界區(qū)CS。 對(duì)臨界資源的互斥訪問(wèn)即為多進(jìn)程互斥進(jìn)入各自的臨對(duì)臨界資源的互斥訪問(wèn)即為多進(jìn)程互斥進(jìn)入各自的臨界區(qū)操作。為保證互斥訪問(wèn)，在進(jìn)入前必需先檢測(cè)臨界資界區(qū)操作。為保證互斥訪問(wèn)，在進(jìn)入前必需先檢測(cè)臨界資源的狀態(tài)。源的狀態(tài)。(Entry section)

42、：進(jìn)程中在臨界區(qū)前用于檢查臨界：進(jìn)程中在臨界區(qū)前用于檢查臨界資源是否正被訪問(wèn)的代碼。資源是否正被訪問(wèn)的代碼。(Exit section) ：進(jìn)程中在臨界區(qū)后的一段代碼，用：進(jìn)程中在臨界區(qū)后的一段代碼，用于標(biāo)記該臨界資源已被釋放。于標(biāo)記該臨界資源已被釋放。 （二）、臨界區(qū)（二）、臨界區(qū)(Critical Section)Entry sectionExit section remainder section;until false;訪問(wèn)臨界資源的循環(huán)進(jìn)程描述如下訪問(wèn)臨界資源的循環(huán)進(jìn)程描述如下：repeatcritical section;為實(shí)現(xiàn)進(jìn)程互斥進(jìn)入為實(shí)現(xiàn)進(jìn)程互斥進(jìn)入自己的臨界區(qū)，采用自己的

43、臨界區(qū)，采用同步機(jī)構(gòu)同步機(jī)構(gòu)進(jìn)行協(xié)調(diào)。進(jìn)行協(xié)調(diào)。 OS利用同步機(jī)制提供互斥工具才能保證進(jìn)程互斥的進(jìn)入臨利用同步機(jī)制提供互斥工具才能保證進(jìn)程互斥的進(jìn)入臨界區(qū)，互斥工具應(yīng)能保證如下幾點(diǎn)：界區(qū)，互斥工具應(yīng)能保證如下幾點(diǎn)：1）空閑讓進(jìn)空閑讓進(jìn)：若臨界資源空閑，則允許一個(gè)請(qǐng)求進(jìn)程進(jìn)入自己的臨界區(qū)。若臨界資源空閑，則允許一個(gè)請(qǐng)求進(jìn)程進(jìn)入自己的臨界區(qū)。2）忙則等待忙則等待：若臨界資源正被使用，則其它申請(qǐng)?jiān)撡Y源的進(jìn)程應(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）讓權(quán)等

44、待讓權(quán)等待：當(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)遵循的原則設(shè)兩個(gè)進(jìn)程設(shè)兩個(gè)進(jìn)程PiPi、 PjPj并發(fā)執(zhí)行，共享某臨界資源。描述為：并發(fā)執(zhí)行，共享某臨界資源。描述為： beginbegin parbegin parbegin Pi Pi； PjPj； parendparend end end 利用軟件方法解決進(jìn)程互斥問(wèn)題，方法之一利用軟件方法解決進(jìn)程互斥問(wèn)題，方法之一 -。 。檢查鎖狀態(tài)，若為關(guān)。檢

45、查鎖狀態(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; W=0;為為每類臨界區(qū)每類臨界區(qū)設(shè)置一把設(shè)置一把“鎖鎖”，有，有打開打開和和關(guān)閉關(guān)閉兩種狀態(tài)?？蓛煞N狀態(tài)?？捎米兞勘硎炬i（軟件鎖），值為用變量表示鎖（軟件鎖），值為0表示打開，為表示打開，為1表示關(guān)閉。表示關(guān)閉。例：例

46、：利用鎖變量方法實(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);：簡(jiǎn)單；：簡(jiǎn)單；：不安全，因?yàn)殛P(guān)鎖和開鎖操作不具有不安全，因?yàn)殛P(guān)鎖和開鎖操作不具有原子性原子性。 出現(xiàn)出現(xiàn)“忙等忙等”，軟件算法不能完全解決多個(gè)進(jìn)程互斥問(wèn)題。軟件算法不能完全解決多個(gè)進(jìn)程互斥問(wèn)題。以變量以變量W表示鎖，置初值表示鎖，置初值為為0。兩個(gè)進(jìn)程的部分代碼如下。兩個(gè)進(jìn)程的部分代碼如下。 1）指令：）指令：boolean TS(b

47、oolean *lock) boolean old; old = lock; lock = TRUE; return old;lock值表示資源使用情況。值表示資源使用情況。為為false，表示空閑（初，表示空閑（初值）；為值）；為true，表示正用。，表示正用。 利用硬件方法解決進(jìn)程互斥問(wèn)題有利用硬件方法解決進(jìn)程互斥問(wè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，否則，否則繼

48、續(xù)檢測(cè)。退出臨界區(qū)，繼續(xù)檢測(cè)。退出臨界區(qū)，重設(shè)資源可用。重設(shè)資源可用。缺點(diǎn)缺點(diǎn)：不能：不能“讓權(quán)等待讓權(quán)等待”，是一種是一種“忙等忙等” 更好的方法是當(dāng)臨界資源不可用時(shí)，就阻塞該進(jìn)程，直更好的方法是當(dāng)臨界資源不可用時(shí)，就阻塞該進(jìn)程，直到臨界資源可用時(shí)繼續(xù)。到臨界資源可用時(shí)繼續(xù)。 該指令的具體實(shí)現(xiàn)該指令的具體實(shí)現(xià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)。（四

49、）信號(hào)量機(jī)制（四）信號(hào)量機(jī)制（Integer SemaphoreInteger Semaphore） wait(s)： while s0表示一個(gè)或多表示一個(gè)或多個(gè)資源，個(gè)資源，0沒(méi)有資源。沒(méi)有資源。r 信號(hào)量操作的信號(hào)量操作的： 信號(hào)量可以初始化為一個(gè)非信號(hào)量可以初始化為一個(gè)非負(fù)值；負(fù)值；除初始化外，僅能由除初始化外，僅能由原語(yǔ)原語(yǔ)wait( )和和signal( )訪問(wèn)信號(hào)量訪問(wèn)信號(hào)量。即即P和和V操作。操作。signal(s): s:=s+1 其他進(jìn)程可獲得處理機(jī)，會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問(wèn)同一其他進(jìn)程可獲得處理機(jī)，會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問(wèn)同一臨界資源。臨界資源。 放棄處理機(jī)放棄處理機(jī)“阻塞阻塞

50、”等待，等待，“讓權(quán)等待讓權(quán)等待”。整型信號(hào)量整型信號(hào)量的的： 未遵循未遵循“讓權(quán)等待讓權(quán)等待”，出現(xiàn)，出現(xiàn)“忙等忙等”。每個(gè)同學(xué)可使用該教室，都可看教室是否可用，但存在不公每個(gè)同學(xué)可使用該教室，都可看教室是否可用，但存在不公平現(xiàn)象（自發(fā)檢查造成），解決方法是設(shè)立一個(gè)記錄表。平現(xiàn)象（自發(fā)檢查造成），解決方法是設(shè)立一個(gè)記錄表。 (1)記錄申請(qǐng)使用教室而未能如愿的學(xué)生名字或教室情況。記錄申請(qǐng)使用教室而未能如愿的學(xué)生名字或教室情況。 (2)釋放教室的學(xué)生查記錄表，通知等待學(xué)生進(jìn)入。釋放教室的學(xué)生查記錄表，通知等待學(xué)生進(jìn)入。 該記錄表即該記錄表即（Record-type Semaphore）整型信號(hào)量

51、機(jī)制整型信號(hào)量機(jī)制: (1) 獲得使用該教室的權(quán)利；獲得使用該教室的權(quán)利； (2) 不斷測(cè)試是否可用；不斷測(cè)試是否可用； (3) 直到他進(jìn)門后為止。此期間其他同學(xué)無(wú)權(quán)。直到他進(jìn)門后為止。此期間其他同學(xué)無(wú)權(quán)。如：某個(gè)學(xué)生想用某個(gè)人人都可用且不規(guī)定使用時(shí)間的教室。如：某個(gè)學(xué)生想用某個(gè)人人都可用且不規(guī)定使用時(shí)間的教室。（Record-type 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：li

52、st of process; -L為一個(gè)進(jìn)程鏈表為一個(gè)進(jìn)程鏈表 endprocedure signal(s) var s:semaphore; begin s.value:=s.value+1 if s.value=0 then wakeup(s.L) endprocedure wait(s)var s :semaphore;begin s.value:=s.value-1； if s.value0 then block(s.L)；end例：系統(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 1）s.

53、value的的。s.L表示該表示該資源的阻塞隊(duì)列。資源的阻塞隊(duì)列。 2）wait()表示請(qǐng)求一個(gè)單位的資源。表示請(qǐng)求一個(gè)單位的資源。s.value-1表示該資源表示該資源數(shù)減數(shù)減1。若。若s.value0，則資源已用完，調(diào)用阻塞原語(yǔ)。此時(shí)的，則資源已用完，調(diào)用阻塞原語(yǔ)。此時(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）S

54、wait（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í)，阻止任何進(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í)別臨界資源，一看是否否

55、共享共享，二看是否，二看是否排他排他。l 2、wait(mutex)和和signal(mutex)必須必須成對(duì)出現(xiàn)成對(duì)出現(xiàn)，并分別緊靠并分別緊靠臨界段的頭尾部臨界段的頭尾部。（五）信號(hào)量應(yīng)用之一（五）信號(hào)量應(yīng)用之一缺少缺少wait，則？缺少，則？缺少signal，則？，則？一個(gè)互斥信號(hào)量一個(gè)互斥信號(hào)量mutex實(shí)現(xiàn)進(jìn)程實(shí)現(xiàn)進(jìn)程P1和和P2互斥的描述為：互斥的描述為：實(shí)例：三個(gè)進(jìn)程執(zhí)行中要共享變量count。count屬于臨界資源，對(duì)其應(yīng)互斥訪問(wèn)。屬于臨界資源，對(duì)其應(yīng)互斥訪問(wèn)。 until false;end Var mutex:semaphore:=1;Begin parbegin proce

56、ss1:begin repeat until false; end process3:begin repeat until false; endParendEndprocess2:begin repeat -2.1P下一條語(yǔ)句下一條語(yǔ)句（六）信號(hào)量應(yīng)用之二（六）信號(hào)量應(yīng)用之二 利用信號(hào)量可以控制進(jìn)程執(zhí)行的先后次序，以描述程序利用信號(hào)量可以控制進(jìn)程執(zhí)行的先后次序，以描述程序或語(yǔ)句間的前趨關(guān)系。或語(yǔ)句間的前趨關(guān)系。mutex parbegin begin S1；signal(a)；signal(b)；end； begin wait(a)；S2；signal(c)；signal(d)；end； be

57、gin wait(b)；S3；signal(e)；end； begin wait(c)；S4；signal(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ì)算進(jìn)程計(jì)算進(jìn)程、打印進(jìn)程打印進(jìn)程通過(guò)緩沖區(qū)通過(guò)緩沖區(qū)buf實(shí)現(xiàn)合作。實(shí)現(xiàn)合作。計(jì)算進(jìn)程計(jì)算進(jìn)程不斷不斷把每次計(jì)算結(jié)果把每次計(jì)算結(jié)果放入放入buf中，中，打印進(jìn)程打印進(jìn)程

58、則則取出取出buf中的數(shù)據(jù)打印輸出，中的數(shù)據(jù)打印輸出，若不采取任何制約措施，這兩個(gè)進(jìn)程的起始執(zhí)行時(shí)間和執(zhí)行速度彼若不采取任何制約措施，這兩個(gè)進(jìn)程的起始執(zhí)行時(shí)間和執(zhí)行速度彼此獨(dú)立，相應(yīng)的控制段描述為：此獨(dú)立，相應(yīng)的控制段描述為：Pc: A：local buf1 Repeat buf1buf Until buf1=空空 計(jì)算計(jì)算 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問(wèn)問(wèn) 題：題：CPU時(shí)間的極大浪費(fèi)時(shí)間的極大浪費(fèi)直接制約的進(jìn)程互給對(duì)方進(jìn)程直接制約

59、的進(jìn)程互給對(duì)方進(jìn)程，一旦收到制約進(jìn)程發(fā)來(lái)的信號(hào)即由等待開始執(zhí)行。，一旦收到制約進(jìn)程發(fā)來(lái)的信號(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)，b

60、uf空信號(hào)空信號(hào)可用信號(hào)量表示?？捎眯盘?hào)量表示。 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，無(wú)數(shù)據(jù)為，無(wú)數(shù)據(jù)為0 0。 初始：初始： S Semptyempty