操作系統(tǒng)第2章進程管理

1、第二章第二章 進程管理進程管理本章要點（本章要點（1/3） 目標：目標：建立起進程的概念，掌握好進程控制、建立起進程的概念，掌握好進程控制、進程同步和進程間通信的基本概念。進程同步和進程間通信的基本概念。 進程的基本概念進程的基本概念 為什么要引入進程 進程的基本特征 進程的狀態(tài) 進程控制塊 進程同步的基本概念進程同步的基本概念 臨界資源 臨界區(qū) 同步機制應(yīng)遵循的準則本章要點（本章要點（2/3） 信號量機制及其應(yīng)用信號量機制及其應(yīng)用 信號量的含義 信號量的物理意義 用信號量實現(xiàn)互斥 用信號量實現(xiàn)前趨關(guān)系 經(jīng)典進程的同步問題經(jīng)典進程的同步問題 生產(chǎn)者-消費問題 哲學(xué)家進餐問題 讀者-寫者問題這些

2、問題用于解決什么問題如何實現(xiàn)進程互斥如何實現(xiàn)進程同步本章要點（本章要點（3/3） 消息傳遞通信機制消息傳遞通信機制 什么是消息傳遞通信機制 消息傳遞通信機制的實現(xiàn)方式 如何協(xié)調(diào)發(fā)送進程和接收進程 消息緩沖隊列通信機制 線程的基本概念線程的基本概念 為什么要引入線程 線程的特征 創(chuàng)建和終止線程 內(nèi)核支持線程和用戶級線程內(nèi)核支持線程和用戶級線程 什么是內(nèi)核支持線程 什么是用戶級線程本章內(nèi)容本章內(nèi)容2.1 2.1 進程的基本概念進程的基本概念2.2 2.2 進程控制進程控制 2.3 2.3 進程同步進程同步2.4 2.4 經(jīng)典進程的同步問題經(jīng)典進程的同步問題2.5 2.5 進程通信進程通信2.6 2

3、.6 線程線程2.1 進程的基本概念進程的基本概念2.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征 圖圖 2-1 程序的順序執(zhí)行程序的順序執(zhí)行 I1C1P1I2C2P2(a) 程序的順序執(zhí)行程序的順序執(zhí)行S1S2S3(b) 三條語句的順序執(zhí)行三條語句的順序執(zhí)行1、程序的順序執(zhí)行、程序的順序執(zhí)行S1 : a : = x + y;S2 : b : = a - 5;S3 : c : = b + 1;I : 輸入操作輸入操作C : 計算操作計算操作P : 打印操作打印操作 順序性：順序性：處理機的操作必須嚴格按照程序所規(guī)定的順序執(zhí)行。 封閉性：封閉性：程序在執(zhí)行時獨占系統(tǒng)的全部資源，機器資源狀

4、態(tài)的改變只與執(zhí)行的程序有關(guān)，而與外界環(huán)境無關(guān)。 可再現(xiàn)性：可再現(xiàn)性：只要初始條件相同，一個程序的多次重復(fù)執(zhí)行，將得到相同的結(jié)果。 2、程序順序執(zhí)行的特征、程序順序執(zhí)行的特征2.1.2 前趨圖前趨圖 前趨圖前趨圖是一個有向無循環(huán)圖有向無循環(huán)圖，用于描述描述程序段或進程之間執(zhí)行的先后次序先后次序關(guān)系。圖中的結(jié)點結(jié)點用于描述一個程序段或一個進程，結(jié)點間的有向邊有向邊用于表示兩個結(jié)點之間存在的偏偏序序或前趨關(guān)系“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可寫成PiPj，稱Pi是Pj的直接前趨直接前趨，而稱Pj是Pi的直直

5、接后繼接后繼。在前趨圖中，把沒有前趨的結(jié)點稱為初始結(jié)點初始結(jié)點，把沒有后繼的結(jié)點稱為終止結(jié)點終止結(jié)點。 每個結(jié)點還具有一個重量重量，用于表示該結(jié)點所含有的程序量程序量或結(jié)點的執(zhí)行時間執(zhí)行時間。 圖圖 2-2 前趨圖前趨圖 P1P2P3P4P5P7P6P8P9(a)具有九具有九個結(jié)點的前趨圖個結(jié)點的前趨圖S1S2S3(b)具有循環(huán)的具有循環(huán)的圖圖圖圖 2-3 并發(fā)執(zhí)行時的前趨圖并發(fā)執(zhí)行時的前趨圖 2.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征 1、程序的并發(fā)執(zhí)行、程序的并發(fā)執(zhí)行I1I2I3I4C1C2C3C4P1P2P3P4例子： 對于具有下述四條語句的程序段 S1: a =x+2 S

6、2: b =y+4 S3: c =a+b S4: d =c+b 圖圖 2-4 四條語句的前趨關(guān)系四條語句的前趨關(guān)系S1S2S3S41、程序的并發(fā)執(zhí)行、程序的并發(fā)執(zhí)行 間斷性：間斷性：由于資源共享和相互合作，并發(fā)執(zhí)行的程序間形成了相互制約關(guān)系，導(dǎo)致程序的運行過程出現(xiàn)“執(zhí)行-暫停-執(zhí)行”的現(xiàn)象。 失去封閉性：失去封閉性：程序在執(zhí)行時與其他并發(fā)執(zhí)行的程序共享系統(tǒng)的資源，因此，資源狀態(tài)的改變還與其他程序有關(guān)，即程序本身的執(zhí)行環(huán)境要受到外界程序的影響。 不可再現(xiàn)性：不可再現(xiàn)性：同樣的初始條件，一個程序的多次重復(fù)執(zhí)行，可得到不同的結(jié)果。 2、程序并發(fā)執(zhí)行時的特征、程序并發(fā)執(zhí)行時的特征 例如，有兩個循環(huán)程序

7、A和B，它們共享一個變量N。程序A每執(zhí)行一次時，都要做N =N+1操作；程序B每執(zhí)行一次時，都要執(zhí)行Print(N)操作，然后再將N置成“0”。程序A和B以不同的速度運行。 (1) N =N+1在Print(N)和N =0之前，此時得到的N值分別為n+1, n+1, 0。 (2) N =N+1在Print(N)和N =0之后，此時得到的N值分別為n, 0, 1。 (3) N =N+1在Print(N)和N =0之間，此時得到的N值分別為n, n+1, 0。 2、程序并發(fā)執(zhí)行時的特征、程序并發(fā)執(zhí)行時的特征2.1.4 進程的特征與狀態(tài)進程的特征與狀態(tài)1、進程的特征和定義、進程的特征和定義 進程進程

8、=？程序？程序 一個進程比一個程序的內(nèi)容要多 程序只是進程狀態(tài)的一部分內(nèi)容 引入進程的目的：引入進程的目的：為了使程序能夠正確地并發(fā)執(zhí)行。 進程的特征：進程的特征： 結(jié)構(gòu)特征：結(jié)構(gòu)特征：進程實體 = 程序段 + 數(shù)據(jù)段 + PCB 動態(tài)性：動態(tài)性： 進程的實質(zhì)是進程實體的一次執(zhí)行過程 進程具有一定的生命周期：由創(chuàng)建而產(chǎn)生，由調(diào)度而執(zhí)行，由撤消而消亡。 并發(fā)性：并發(fā)性：多個進程實體同存于內(nèi)存中，且能在一段時間內(nèi)同時運行。 獨立性：獨立性：進程實體是一個能獨立運行、獨立分配資源和獨立接受調(diào)度的基本單位。 異步性：異步性：進程可按各自獨立的、不可預(yù)知的速度向前推進。1、進程的特征和定義、進程的特征和

9、定義 進程與程序的區(qū)別：進程與程序的區(qū)別： 程序程序是進程的靜態(tài)文本，進程進程是執(zhí)行程序的動態(tài)過程； 一個進程一個進程可以執(zhí)行一個或多個程序一個或多個程序，幾個進程幾個進程可以同時執(zhí)行一個程序一個程序； 程序程序可作為軟件資源長期保存，進程進程只是一次執(zhí)行過程，是暫時的； 進程進程是系統(tǒng)分配調(diào)度的獨立單位，能與其他進程并發(fā)執(zhí)行。 定義：定義：進程是一個可并發(fā)執(zhí)行的程序，在一個數(shù)據(jù)集合上的一次運行過程。它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。1、進程的特征和定義、進程的特征和定義 就緒狀態(tài)（就緒狀態(tài)（Ready） 執(zhí)行狀態(tài)（執(zhí)行狀態(tài)（Running） 阻塞狀態(tài)（阻塞狀態(tài)（Blocked）圖圖

10、2-5 進程的三種基本進程的三種基本 狀態(tài)及其轉(zhuǎn)換狀態(tài)及其轉(zhuǎn)換 2、進程的三種基本狀態(tài)、進程的三種基本狀態(tài) 對單個進程：對單個進程： 任何時刻，進程只能處理三種基本狀態(tài)之一； 隨著進程自身的推進和外界條件的變化，進程的狀態(tài)可以動態(tài)地轉(zhuǎn)換 對整個系統(tǒng)：對整個系統(tǒng)： 每個時刻允許同時有多個進程處于就緒/阻塞狀態(tài)； 對于執(zhí)行狀態(tài)的進程，每個處理機最多只允許有一個。就緒就緒執(zhí)行執(zhí)行阻塞阻塞進程調(diào)度進程調(diào)度I/O請求請求I/O完成完成時間片完時間片完 掛起：掛起：實質(zhì)是使進程不能繼續(xù)執(zhí)行 被掛起的進程處于靜止狀態(tài)； 沒被掛起的進程處于活動狀態(tài)。 引起掛起的原因：原因： 終端用戶的請求； 父進程請求； 負

11、荷調(diào)節(jié)的需要； 操作系統(tǒng)的需要；3、掛起狀態(tài)、掛起狀態(tài) 進程狀態(tài)的轉(zhuǎn)換SuspendSuspendActiveActive3、掛起狀態(tài)、掛起狀態(tài)靜止就緒(Readys)靜止阻塞(Blockeds)活動就緒(Readya) 活動阻塞(Blockeda) 活動就緒(Readya) 活動阻塞(Blockeda) 靜止就緒(Readys) 靜止阻塞(Blockeds)3、掛起狀態(tài)、掛起狀態(tài)圖圖 2-6 具有掛起狀態(tài)的進程狀態(tài)圖具有掛起狀態(tài)的進程狀態(tài)圖 執(zhí)行執(zhí)行靜止靜止就緒就緒靜止靜止阻塞阻塞活動活動就緒就緒活動活動阻塞阻塞請求請求I/O掛起掛起激活激活掛起掛起激活激活掛起掛起喚醒喚醒喚醒喚醒進程調(diào)度進

12、程調(diào)度時間片完時間片完 創(chuàng)建狀態(tài)創(chuàng)建狀態(tài) 為一個新進程創(chuàng)建PCB，并填寫必要的管理信息； 把該進程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列之中。 引入創(chuàng)建狀態(tài)的目的引入創(chuàng)建狀態(tài)的目的 為了保證進程的調(diào)度必須在創(chuàng)建工作完成后進行，確保進程控制塊操作的完整性。 增加管理的靈活性，操作系統(tǒng)可以根據(jù)系統(tǒng)性能或主存容量的限制，推遲創(chuàng)建狀態(tài)進程的提交。4、創(chuàng)建狀態(tài)和終止狀態(tài)、創(chuàng)建狀態(tài)和終止狀態(tài) 終止狀態(tài)終止狀態(tài) 首先等待操作系統(tǒng)進行善后處理； 然后將其PCB清零，并將PCB空間返還系統(tǒng)。 引起進程終止的事件引起進程終止的事件 自然結(jié)束； 出現(xiàn)無法克服的錯誤； 被操作系統(tǒng)終結(jié)，或其他有終止權(quán)的進程所終結(jié)。 終止進程的處理

13、過程終止進程的處理過程 進入終止狀態(tài)的進程以后不能被執(zhí)行，但在操作系統(tǒng)中保留有一個記錄，其中保存狀態(tài)碼和一些計時統(tǒng)計數(shù)據(jù)，供其他進程收集； 一旦其它進程完成了對終止狀態(tài)進程的信息提取后，操作系統(tǒng)將刪除該進程。4、創(chuàng)建狀態(tài)和終止狀態(tài)、創(chuàng)建狀態(tài)和終止狀態(tài) 增加創(chuàng)建狀態(tài)與終止狀態(tài)的狀態(tài)轉(zhuǎn)換圖增加創(chuàng)建狀態(tài)與終止狀態(tài)的狀態(tài)轉(zhuǎn)換圖4、創(chuàng)建狀態(tài)和終止狀態(tài)、創(chuàng)建狀態(tài)和終止狀態(tài)圖圖 2-7 進程的五種基本狀態(tài)及轉(zhuǎn)換進程的五種基本狀態(tài)及轉(zhuǎn)換 就緒就緒執(zhí)行執(zhí)行阻塞阻塞時間片完時間片完進程調(diào)度進程調(diào)度I/O請求請求I/O完成完成創(chuàng)建創(chuàng)建許可許可終止終止釋放釋放 增加創(chuàng)建狀態(tài)與終止狀態(tài)的狀態(tài)轉(zhuǎn)換圖增加創(chuàng)建狀態(tài)與終止狀態(tài)

14、的狀態(tài)轉(zhuǎn)換圖4、創(chuàng)建狀態(tài)和終止狀態(tài)、創(chuàng)建狀態(tài)和終止狀態(tài)圖圖 2-8 具有創(chuàng)建、終止和掛起狀態(tài)的進程狀態(tài)圖具有創(chuàng)建、終止和掛起狀態(tài)的進程狀態(tài)圖 執(zhí)行執(zhí)行靜止靜止就緒就緒靜止靜止阻塞阻塞活動活動就緒就緒活動活動阻塞阻塞請求請求I/O掛起掛起激活激活掛起掛起激活激活掛起掛起喚醒喚醒喚醒喚醒進程調(diào)度進程調(diào)度時間片完時間片完創(chuàng)建創(chuàng)建許可許可終止終止釋放釋放許可許可2.1.5 進程控制塊進程控制塊1、進程控制塊中的信息、進程控制塊中的信息PCB程序段程序段私有私有數(shù)據(jù)數(shù)據(jù)進程名進程名當(dāng)前狀態(tài)當(dāng)前狀態(tài)優(yōu)先數(shù)優(yōu)先數(shù)現(xiàn)場保留區(qū)現(xiàn)場保留區(qū)指示處于同一狀態(tài)指示處于同一狀態(tài)進程的鏈指針進程的鏈指針資源清單資源清單進程

15、起始地址進程起始地址家族關(guān)系家族關(guān)系其他其他（a）進程示意圖）進程示意圖（b）進程控制塊的基本內(nèi)容）進程控制塊的基本內(nèi)容 PCB是進程存在的唯一標志是進程存在的唯一標志。創(chuàng)建進程時，創(chuàng)建PCB；進程結(jié)束時，系統(tǒng)將撤消其PCB。 進程控制塊進程控制塊PCB（Process Control Block）：是進程實體的一部分是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)記錄了操作系統(tǒng)所需的、用于描述進程當(dāng)前情況以及控制進程運行的全部信息 PCB的作用：的作用：將程序變成可并發(fā)執(zhí)行的進程 PCB必須長駐內(nèi)存必須長駐內(nèi)存2、進程控制塊的作用、進程控制塊的作用 調(diào)度進程執(zhí)行時調(diào)度進程執(zhí)行時,需要從該進程的需要從該進程

16、的PCB中查出其現(xiàn)中查出其現(xiàn)行狀態(tài)及優(yōu)先級；行狀態(tài)及優(yōu)先級； 調(diào)度到某進程后調(diào)度到某進程后，根據(jù)，根據(jù)PCB中所保存的處理機狀態(tài)中所保存的處理機狀態(tài)信息，設(shè)置該進程恢復(fù)運行的現(xiàn)場，并根據(jù)信息，設(shè)置該進程恢復(fù)運行的現(xiàn)場，并根據(jù)PCB中中的程序和數(shù)據(jù)的內(nèi)存始址，找到其程序和數(shù)據(jù)；的程序和數(shù)據(jù)的內(nèi)存始址，找到其程序和數(shù)據(jù)； 進程在執(zhí)行過程中進程在執(zhí)行過程中，當(dāng)需要和與之合作的進程實現(xiàn)，當(dāng)需要和與之合作的進程實現(xiàn)同步、通信或訪問文件時，也需要訪問同步、通信或訪問文件時，也需要訪問PCB； 當(dāng)進程由于某種原因而當(dāng)進程由于某種原因而暫停執(zhí)行時暫停執(zhí)行時，又須將斷點的，又須將斷點的處理機環(huán)境保存在處理機環(huán)境

17、保存在PCB中。中。2、進程控制塊的作用、進程控制塊的作用 進程標識符進程標識符 處理機狀態(tài)處理機狀態(tài) 進程調(diào)度信息進程調(diào)度信息 進程控制信息進程控制信息3、進程控制塊中的信息、進程控制塊中的信息3.1、進程標識符、進程標識符進程標識符進程標識符用于唯一地標識一個進程。用于唯一地標識一個進程。（1）內(nèi)部標識符。在所有的操作系統(tǒng)中，）內(nèi)部標識符。在所有的操作系統(tǒng)中，都為每一個進程賦予一個唯一的數(shù)字標識都為每一個進程賦予一個唯一的數(shù)字標識符，它通常是一個進程的序號。符，它通常是一個進程的序號。（2）外部標識符）外部標識符 由創(chuàng)建者提供，通常是由創(chuàng)建者提供，通常是由用戶在訪問該進程時使用。由用戶在訪

18、問該進程時使用。進程標識符進程標識符3.2、處理機狀態(tài)、處理機狀態(tài)處理機狀態(tài)信息處理機狀態(tài)信息主要是由處理機的各種寄存器中的主要是由處理機的各種寄存器中的內(nèi)容組成的。內(nèi)容組成的。 處理機運行時，許多信息都存放在寄處理機運行時，許多信息都存放在寄存器中。當(dāng)處理機被中斷時，所有這些信息都必須存器中。當(dāng)處理機被中斷時，所有這些信息都必須保存在保存在PCB中，以便該進程重新執(zhí)行時，能從斷點中，以便該進程重新執(zhí)行時，能從斷點繼續(xù)執(zhí)行。這些寄存器包括：繼續(xù)執(zhí)行。這些寄存器包括：通用寄存器通用寄存器：用戶可視寄存器，用于暫存信息，用戶程序可：用戶可視寄存器，用于暫存信息，用戶程序可以訪問；以訪問；指令計數(shù)器

19、指令計數(shù)器：存放了要訪問的下一條指令的地址；：存放了要訪問的下一條指令的地址；程序狀態(tài)字程序狀態(tài)字PSW:其中包含了狀態(tài)信息，如條件碼、執(zhí)行方式、其中包含了狀態(tài)信息，如條件碼、執(zhí)行方式、終端屏蔽標志等；終端屏蔽標志等；用戶棧指針用戶棧指針：每個用戶進程都有一個或若干個與之相關(guān)的系：每個用戶進程都有一個或若干個與之相關(guān)的系統(tǒng)棧，用于存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指統(tǒng)棧，用于存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向棧頂。向棧頂。3.3、進程調(diào)度信息、進程調(diào)度信息在在PCB中還存放一些與進程調(diào)度和進程對換有關(guān)的中還存放一些與進程調(diào)度和進程對換有關(guān)的信息，包括：信息，包括：進程狀態(tài)進程狀

20、態(tài) 指明進程的當(dāng)前狀態(tài)，作為進程調(diào)度和對指明進程的當(dāng)前狀態(tài)，作為進程調(diào)度和對換時的依據(jù)；換時的依據(jù)；進程優(yōu)先級進程優(yōu)先級 優(yōu)先級高的進程應(yīng)先獲得處理機優(yōu)先級高的進程應(yīng)先獲得處理機進程調(diào)度所需的其它信息進程調(diào)度所需的其它信息 與所采用的進程調(diào)度算法與所采用的進程調(diào)度算法有關(guān)，比如，進程已等待有關(guān)，比如，進程已等待CPU的時間總和、進程已的時間總和、進程已執(zhí)行的時間總和等；執(zhí)行的時間總和等；事件事件 即阻塞原因，指進程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪罴醋枞颍高M程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件。態(tài)所等待發(fā)生的事件。3.4、進程控制信息、進程控制信息程序和數(shù)據(jù)的地址程序和數(shù)據(jù)的地址: 指進程的程

21、序和數(shù)據(jù)所在的內(nèi)存指進程的程序和數(shù)據(jù)所在的內(nèi)存或外存地址，以便再調(diào)度到該程序執(zhí)行時，能從或外存地址，以便再調(diào)度到該程序執(zhí)行時，能從PCB中找到其程序和數(shù)據(jù)；中找到其程序和數(shù)據(jù)；進程同步和通信機制進程同步和通信機制:指實現(xiàn)進程同步和通信必需的指實現(xiàn)進程同步和通信必需的機制，如消息隊列指針、信號量等；機制，如消息隊列指針、信號量等；資源清單資源清單：是一張列出了使用：是一張列出了使用CPU以外的、進程所以外的、進程所需的全部資源及已經(jīng)分配到該進程的資源的清單；需的全部資源及已經(jīng)分配到該進程的資源的清單；鏈接指針鏈接指針：它給出了本進程（：它給出了本進程（PCB）所在隊列中的）所在隊列中的下一個進程

22、的下一個進程的PCB的首地址。的首地址。 鏈接方式：鏈接方式：把具有同一狀態(tài)的PCB，用其中的鏈接字鏈接成一個隊列4、進程控制塊的組織方式、進程控制塊的組織方式執(zhí)行指針執(zhí)行指針就緒隊列指針就緒隊列指針阻塞隊列指針阻塞隊列指針空閑隊列指針空閑隊列指針PCB14PCB23PCB30PCB48PCB5PCB67PCB79PCB80PCB915P5正在執(zhí)行；正在執(zhí)行；就緒進程有：就緒進程有：P1,P4,P8阻塞進程有：阻塞進程有：P2,P3其余為空閑進程控制塊其余為空閑進程控制塊PCB 索引方式：索引方式：系統(tǒng)根據(jù)所有進程的狀態(tài)建立幾張索引表，并把各索引表在內(nèi)存的首地址記錄在內(nèi)存的一些專用單元中。在每

23、個索引表的表目中，記錄具有相應(yīng)狀態(tài)的某個PCB在PCB表中的地址。3、進程控制塊的組織方式、進程控制塊的組織方式PCB1執(zhí)行指針執(zhí)行指針就緒表指針就緒表指針阻塞表指針阻塞表指針就緒索引表就緒索引表阻塞索引表阻塞索引表PCB2PCB3PCB4PCB5PCB6PCB72.2 進程控制進程控制2.2 進程控制進程控制 進程控制進程控制是進程管理中最基本的功能： 創(chuàng)建和撤消進程 對進程在整個生命期中各種狀態(tài)之間的轉(zhuǎn)換進行有效控制。 進程控制是操作系統(tǒng)的內(nèi)核通過原語來實現(xiàn)的。 原語：原語：是指由若干條指令組成，用來實現(xiàn)某個特定操作的一個過程。 原語的執(zhí)行具有原子性； 原語常駐內(nèi)存，且在系統(tǒng)狀態(tài)下執(zhí)行。

24、2.2 進程控制進程控制 系統(tǒng)狀態(tài)系統(tǒng)狀態(tài)和用戶狀態(tài)用戶狀態(tài)是處理機的兩種執(zhí)行狀態(tài)，用于防止用戶程序破壞操作系統(tǒng)內(nèi)核代碼和數(shù)據(jù)。 系統(tǒng)狀態(tài)：系統(tǒng)狀態(tài)：也叫管態(tài)或核心狀態(tài)，它具有較高的特權(quán)，能執(zhí)行一切指令，訪問所有寄存器和存儲區(qū)。 通常操作系統(tǒng)內(nèi)核就運行在系統(tǒng)狀態(tài)。 用戶狀態(tài)：用戶狀態(tài)：也叫目態(tài)，是一種具有較低特權(quán)的執(zhí)行狀態(tài)，它只能執(zhí)行規(guī)定的指令、訪問規(guī)定的寄存器和存儲區(qū)。 通常用戶程序都是運行在用戶狀態(tài)。圖圖 2-9 進程樹進程樹 2.2.1 進程的創(chuàng)建進程的創(chuàng)建1、進程圖（、進程圖（Process Graph） 進程圖：進程圖：用于描述一個進程的家庭關(guān)系的有向樹。 父進程 子進程 祖先進程

25、祖先 子進程可以繼承父子進程可以繼承父進程所擁有的資源進程所擁有的資源ABCDEFGHIJKLM(1) 用戶登錄用戶登錄。 (2) 作業(yè)調(diào)度作業(yè)調(diào)度。 (3) 提供服務(wù)提供服務(wù)。 (4) 應(yīng)用請求應(yīng)用請求。 2、引起創(chuàng)建進程的事件、引起創(chuàng)建進程的事件由系統(tǒng)內(nèi)核創(chuàng)建新進程由應(yīng)用程序創(chuàng)建新進程創(chuàng)建原語創(chuàng)建原語Creat()： 功能：功能：創(chuàng)建進程控制塊PCB 入口信息：入口信息：進程標識符、優(yōu)先級、進程開始地址、初始CPU狀態(tài)、資源清單等 實現(xiàn)過程：實現(xiàn)過程： 申請空白PCB； 為新進程分配資源； 初始化進程控制塊 將新進程插入就緒隊列 3、進程的創(chuàng)建、進程的創(chuàng)建(Creation of Prog

26、ress) 開始開始申請空白申請空白PCB為新進程分配資源為新進程分配資源初始化進程控制塊初始化進程控制塊將新進程插入就緒隊列將新進程插入就緒隊列2.2.2 進程的終止進程的終止 1) 正常結(jié)束正常結(jié)束 2) 異常結(jié)束異常結(jié)束 越界錯誤 保護錯 非法指令 特權(quán)指令錯 運行超時 等待超時 算術(shù)運算錯 I/O故障 3)外界干預(yù)外界干預(yù) 操作員或操作系統(tǒng)干預(yù) 父進程請求 父進程終止1、引起進程終止、引起進程終止(Termination of Process)的事件的事件終止原語：終止原語： 功能：功能：終止一個指定的進程 入口信息：入口信息：被終止的進程名 實現(xiàn)過程：實現(xiàn)過程： 根據(jù)被終止進程的標識

27、符，從PCB集合中檢索進程的PCB。 若被終止進程正在執(zhí)行，則終止它的執(zhí)行，并置重新調(diào)度標志。 終止屬于該進程的所有子孫進程。 釋放被終止進程所擁有的全部資源。 將終止進程移出它所在隊列并收回PCB。2、進程的終止過程、進程的終止過程開始開始檢索檢索PCB，讀出進程狀態(tài)，讀出進程狀態(tài)若是執(zhí)行，置調(diào)度標志為真若是執(zhí)行，置調(diào)度標志為真若有子孫進程，終止其子孫進程若有子孫進程，終止其子孫進程將所擁有的資源歸還給父進程或系統(tǒng)將所擁有的資源歸還給父進程或系統(tǒng)將將PCB從所在隊列移出從所在隊列移出2.2.3 進程的阻塞與喚醒進程的阻塞與喚醒請求系統(tǒng)服務(wù)請求系統(tǒng)服務(wù) 啟動某種操作啟動某種操作 新數(shù)據(jù)尚未到達

28、新數(shù)據(jù)尚未到達 無新工作可做無新工作可做 1、引起進程阻塞和喚醒的事件、引起進程阻塞和喚醒的事件阻塞原語（阻塞原語（block()）：）： 功能：功能：將進程從執(zhí)行狀態(tài)轉(zhuǎn)換成阻塞狀態(tài) 入口信息：入口信息：可省略 實現(xiàn)過程：實現(xiàn)過程： 停止進程執(zhí)行，將其狀態(tài)改為阻塞狀態(tài)； 將其PCB插入相應(yīng)的阻塞隊列； 轉(zhuǎn)調(diào)度程度進行重新調(diào)度。 進程的阻塞是進程的主動進程的阻塞是進程的主動行為行為 2、進程的阻塞過程、進程的阻塞過程開始開始將將CPU當(dāng)前狀態(tài)存入當(dāng)前狀態(tài)存入PCB設(shè)置進程狀態(tài)為阻塞狀態(tài)設(shè)置進程狀態(tài)為阻塞狀態(tài)將將PCB置入阻塞隊列置入阻塞隊列轉(zhuǎn)處理機調(diào)度轉(zhuǎn)處理機調(diào)度喚醒原語（喚醒原語（wakeup

29、()）：）： 功能：功能：當(dāng)被阻塞進程所等待的事件完成時，喚醒某一處于等待隊列當(dāng)中的進程。 入口信息：入口信息：被喚醒進程的名字 實現(xiàn)過程：實現(xiàn)過程： 將被阻塞的進程從等待該事件的阻塞隊列中移出； 將其PCB中的狀態(tài)由阻塞改為就緒； 將該PCB插入到就緒隊列中。3、進程喚醒過程、進程喚醒過程開始開始從阻塞隊列刪除該從阻塞隊列刪除該PCB設(shè)置進程狀態(tài)為就緒狀態(tài)設(shè)置進程狀態(tài)為就緒狀態(tài)將將PCB置入就緒隊列置入就緒隊列結(jié)束結(jié)束2.2.4 進程的掛起與激活進程的掛起與激活掛起原語（掛起原語（suspend()）：）： 功能：功能：將指定進程掛起 實現(xiàn)過程：實現(xiàn)過程：掛起進程處于活動就緒狀態(tài)，將其轉(zhuǎn)換為

30、靜止就緒；掛起進程處于活動阻塞狀態(tài)，將其轉(zhuǎn)換為靜止阻塞；把被掛起的進程的PCB復(fù)制到某指定的內(nèi)存區(qū)域；若被掛起的進程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度。如果掛起是為了對換，則在掛起進程時還必須將它換出到外存1、進程的掛起、進程的掛起激活原語（激活原語（active()）：）： 功能：功能：使處于靜止狀態(tài)的進程變?yōu)榛顒?執(zhí)行過程：執(zhí)行過程：若進程處于靜止阻塞狀態(tài)，則將它轉(zhuǎn)換成活動阻塞狀態(tài)；若進程為靜止就緒狀態(tài)，則將它轉(zhuǎn)換為活動就緒狀態(tài)；若進程轉(zhuǎn)換成活動就緒狀態(tài)，而系統(tǒng)又采用搶占調(diào)度策略，則應(yīng)檢查該進程是否有權(quán)搶占CPU，若有則應(yīng)進行進程調(diào)度；如果掛起是為了對換，則在激活被掛起的進程時還必須將它調(diào)入

31、內(nèi)存。2、進程的激活、進程的激活2.3 進程同步進程同步 進程同步問題的提出進程同步問題的提出 進程異步推進可能造成混亂 混亂可能導(dǎo)致不可再現(xiàn) 進程同步目標進程同步目標2.3 進程同步進程同步 間接相互制約關(guān)系（進程互斥進程互斥）：這種制約源于資源共享。 直接相互制約關(guān)系（進程同步進程同步）：這種制約源于進程間合作。 2.3.1 進程同步的基本概念進程同步的基本概念同同 步步互互 斥斥進程-進程進程-資源-進程時間次序上受到某種限制未競爭到物理資源的進程處于阻塞狀態(tài)相互清楚對方的存在及作用，交換信息不一定清楚其他進程情況往往指有幾個進程共同完成一個任務(wù)往往指多個任務(wù)多個進程間通訊制約例：生產(chǎn)與

32、消費之間，發(fā)送與接受之間，作者與讀者之間，供者與用者之間例：交通十字路口，單軌火車的撥道岔口1、兩種形式的制約關(guān)系、兩種形式的制約關(guān)系 臨界資源：臨界資源：在一段時間內(nèi)只允許一個進程訪問的資源。臨界資源的訪問要求互斥的訪問。 物理設(shè)備，如輸入機、打印機、磁帶機 軟件資源，如公用變量、數(shù)據(jù)、表格、隊列等 為了使多個進程有效地共享臨界資源，并使程序的執(zhí)行具有可再現(xiàn)性，系統(tǒng)必須保證它們互斥地互斥地使用臨界資源使用臨界資源。2、臨界資源、臨界資源(Critical Resource) 3、生產(chǎn)者生產(chǎn)者消費者問題消費者問題放產(chǎn)品放產(chǎn)品取產(chǎn)品取產(chǎn)品一次只能放一個產(chǎn)品；一次只能放一個產(chǎn)品；一次只能取走一個產(chǎn)

33、品；一次只能取走一個產(chǎn)品；緩沖區(qū)滿則生產(chǎn)者不能放產(chǎn)品；緩沖區(qū)滿則生產(chǎn)者不能放產(chǎn)品；緩沖區(qū)空則消費者不能取產(chǎn)品；緩沖區(qū)空則消費者不能取產(chǎn)品；生產(chǎn)者進程生產(chǎn)者進程消費者進程消費者進程并發(fā)并發(fā)012345 n-1生產(chǎn)者消費者緩沖池inoutcounter數(shù)據(jù)結(jié)構(gòu)：var n:integer; /*具有n個緩沖區(qū)的緩沖池*/ type item=; var buffer:array0,1,n-1 of item; in,out:0,1,n-1; /*指向緩沖區(qū)的指針*/ counter:0,1,n; /*緩沖區(qū)中的消息數(shù)*/3、生產(chǎn)者生產(chǎn)者消費者問題消費者問題register2:=counter;re

34、gister2:=register2-1;counter:= register2;producer: repeat producer an item in nextp while counter=n do no-op; bufferin:=nextp; in:=(in+1)mod n counter:=counter+1; until false;consumer: repeat while counter=0 do no-op; nextc:=bufferout; out:=(out+1)mod n counter:=counter-1; consume the item in nextc;

35、 until false;說明：nextp:局部變量，用于暫時存放每次生產(chǎn)出的消息。 nextc:局部變量，用于存放每次要消費的消息。register1:=counter;register1:=register1+1;counter:= register1;3、生產(chǎn)者生產(chǎn)者消費者問題消費者問題inout012345673、生產(chǎn)者生產(chǎn)者消費者問題消費者問題register 1:=counter; register 1:=register+1; counter:=register 1; register 2:=counter；register 2: =register 2 -1;counter:=

36、 register 2 按什么順序執(zhí)行時，按什么順序執(zhí)行時，counter的值是的值是6？register 1:=counter;register 1:=register 1+1;register 2:=counter;register 2:=register 2-1;counter:=register 2;counter:=register 1;register 1=5register 1=6register 2=5register 2=4counter=4counter=6假設(shè)假設(shè)counter的當(dāng)前值為的當(dāng)前值為5為了解決以上問題，可將為了解決以上問題，可將counter作為臨界資源作為

37、臨界資源不論是硬件臨界資源，還是軟件臨界資源，多個進程不論是硬件臨界資源，還是軟件臨界資源，多個進程必須互斥地對它進行訪問。必須互斥地對它進行訪問。臨界區(qū)定義：臨界區(qū)定義：每個進程中訪問臨界資源的那段代碼；4、臨界區(qū)、臨界區(qū)(critical section) P1P2P3臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)臨界區(qū)4、臨界區(qū)、臨界區(qū)(critical section) repeatentry sectionexit sectioncritical sectionremainder section;until false;用于對臨界資源進用于對臨界資源進行檢查行檢查將臨界區(qū)正被訪將臨界區(qū)正被訪問的標志

38、恢復(fù)為問的標志恢復(fù)為未被訪問的標志未被訪問的標志(1)空閑讓進空閑讓進(2) 忙則等待忙則等待 (3) 有限等待有限等待 (4) 讓權(quán)等待讓權(quán)等待 5、同步機制應(yīng)遵循的規(guī)則、同步機制應(yīng)遵循的規(guī)則 人與人之間的合作6、牛奶過剩問題、牛奶過剩問題時間時間A先生先生B先生先生3：00看電冰箱，沒有牛奶了3：05去商店3：10到達商店看電冰箱，沒有牛奶了3：15買牛奶去商店3：20回家，將牛奶拿出到達商店3：25買牛奶3：30回家，將牛奶拿出 使用便條避免購買太多的牛奶 在去購買前留下一張便條（類似“加鎖”） 購買回來后拿走便條（類似“解鎖”） 如果看到便條則不去購買（等待） 假定用一臺計算機去實現(xiàn)這

39、項工作：if (noMilk) if (noNote) leave Note;buy milk;remove note;6、牛奶過剩問題、牛奶過剩問題解決方案解決方案1結(jié)果會是什么呢？結(jié)果會是什么呢？ 仍然存在牛奶過剩的情況，但只是偶爾而已6、牛奶過剩問題、牛奶過剩問題解決方案解決方案1間歇性地失敗！間歇性地失?。?用先放便條的方法試著修正間歇性失敗的問題leave Note;if (noMilk) if (noNote) buy milk;remove note; 這時會發(fā)生什么？ 很好，對人而言，可能沒什么問題 但對計算機而言：就會再也沒人去購買牛奶6、牛奶過剩問題、牛奶過剩問題解決方案解

40、決方案1 fix 使用帶標記的便條 現(xiàn)在我們可以在檢查前留下便條6、牛奶過剩問題、牛奶過剩問題解決方案解決方案2這樣會正常運轉(zhuǎn)嗎？這樣會正常運轉(zhuǎn)嗎？ 可能兩個線程都不去買牛奶！6、牛奶過剩問題、牛奶過剩問題解決方案解決方案2這種情況稱為這種情況稱為“饑餓饑餓” 雙便條解決方案 這樣會正常運轉(zhuǎn)嗎？6、牛奶過剩問題、牛奶過剩問題解決方案解決方案3 在X處 如果沒有便條B，A去購買是安全的 否則等待，查找發(fā)生什么事情了 在Y處 如果沒有便條A，B去購買是安全的 否則，A要么購買，要么等待B退出臨界區(qū)臨界區(qū)忙等忙等A的代碼不同于的代碼不同于B的代碼的代碼如果如果有很多個線程，那又怎么辦呢？有很多個線程

41、，那又怎么辦呢？2.3.2 信號量機制信號量機制信號量機制的基本概念 信號量信號量(Semaphores) 信號量機制是進程同步工具 信號量是對具體物理資源的抽象 不同類的資源用不同名稱的信號量代表 同類資源的個數(shù)用 0的信號量值表示 信號量值為 0 或 1 的信號量表示臨界資源 信號量：信號量：Dijkstra把整型信號量定義為一個整型量S。 特性：特性：除初始化外，僅能通過兩個標準的原子操作原子操作wait(s)（P操作）和signal(s)（V操作）來訪問。描述如下： wait(S): while S0 do no-op； S = S 1； signal(S): S = S + 1； 存

42、在問題：存在問題：只要S=0，wait操作就會不斷地測試，沒能做到“讓權(quán)等待讓權(quán)等待” 1、整型信號量、整型信號量 引入進程阻塞機制，解決了引入進程阻塞機制，解決了“忙等忙等”問題。問題。 在信號量里增加對阻塞進程的記錄在信號量里增加對阻塞進程的記錄 在信號量機制中，除了需要一個用于代表資源數(shù)目的整型變量value外，還增加一個等待隊列指針L，記錄型的數(shù)據(jù)結(jié)構(gòu)描述如下： type semaphore = record value: integer; /*代表資源數(shù)目*/ L: list of process;/*等待進程鏈表*/ end2、記錄型信號量、記錄型信號量2、記錄型信號量、記錄型信號

43、量 wait(S)和和signal(S)操作描述：操作描述： procedure wait(S) var S: semaphore; begin S.value := S.value 1; if S.value 0 then block(S.L) endprocedure signal(S) var S: semaphore; begin S.value := S.value + 1; if S.value 0時，可進行資源預(yù)留 di：申請個數(shù) 一次可申請一種資源的多個4、信號量集、信號量集 信號量集流程信號量集流程 1 1）將正在執(zhí)行的進程移入第一）將正在執(zhí)行的進程移入第一個個S Si i

44、t ti i的等待隊列中；的等待隊列中；2 2）將程序指針指向該進程中）將程序指針指向該進程中SwaitSwait操作開始處操作開始處4、信號量集、信號量集 信號量集流程信號量集流程將與將與S Si i相關(guān)的等待隊列相關(guān)的等待隊列中的所有進程移到準備中的所有進程移到準備隊列隊列4、信號量集、信號量集4、信號量集、信號量集應(yīng)用應(yīng)用61A52B41C到達順序：P1，P2，P3，P4資源申請向量：P1(3,2,1)，P2(2,2,1)，P3(1,1,1)，P4(1,1,1)Var S1,S2,S3:semaphore:=6,5,4;BeginParbeginProcess P1:Swait(S1,1

45、,3,S2,2,2,S3,1,1); use the critical resource;Ssignal(S1,3,S2,2,S3,1);endProcess P2:Swait(S1,1,2,S2,2,2,S3,1,1); use the critical resource;Ssignal(S1,2,S2,2,S3,1);endProcess P3:Swait(S1,1,1,S2,2,1,S3,1,1); use the critical resource;Ssignal(S1,1,S2,1,S3,1);end四個進程對應(yīng)的代碼段為：四個進程對應(yīng)的代碼段為：4、信號量集、信號量集應(yīng)用應(yīng)用61A

46、52B41C到達順序：P1，P2，P3，P4資源申請向量：P1(3,2,1)，P2(2,2,1)，P3(1,1,1)，P4(1,1,1)Process P4:Swait(S1,1,1,S2,2,1,S3,1,1); use the critical resource;Ssignal(S1,1,S2,2,S3,1);endP1到達333P2到達112P3到達, S2t2阻塞阻塞P4到達, S2t2阻塞阻塞P1執(zhí)行完成，釋放資源433P3 P4都被喚醒322P3 申請到資源P4 申請到資源211 (1) Swait(S, d, d)。 此時在信號量集中只有一個信號量S， 但允許它每次申請d個資源，

47、當(dāng)現(xiàn)有資源數(shù)少于d時，不予分配。 (2) Swait(S, 1, 1)。 此時的信號量集已蛻化為一般的記錄型信號量(S1時)或互斥信號量(S=1時)。 (3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號量操作。當(dāng)S1時，允許多個進程進入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進程進入特定區(qū)。換言之，它相當(dāng)于一個可控開關(guān)。 4、信號量集、信號量集特殊情況特殊情況S=2Swait(S,1,0) 臨界區(qū)臨界區(qū)P1 P2 P3 PnS=0Swait(S,1,0)臨界區(qū)臨界區(qū)P1 P2P3Pn2.3.3 信號量的應(yīng)用信號量的應(yīng)用對競爭資源的互斥訪問過程1、利用信號量實現(xiàn)進程互斥、利用信號量實現(xiàn)

48、進程互斥利用信號量實現(xiàn)進程互斥的進程可描述如下：Var mutex:semaphore =1; begin parbegin process 1: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; endparend 1、利用信號量實現(xiàn)進程互斥、利用信號量實現(xiàn)進程

49、互斥wait(mutex)和和signal(mutex)必須成對出現(xiàn)必須成對出現(xiàn) 保證進程間的前驅(qū)、后繼關(guān)系2、利用信號量實現(xiàn)前趨關(guān)系、利用信號量實現(xiàn)前趨關(guān)系Pi代表進程；Si代表Pi中的語句；s為具有前驅(qū)關(guān)系的兩進程的公用信號量，其初值為0。var s:semaphore:=0;begin parbegin begin S1; signal(s);end; begin wait(s); S2; end; parendendS1S2sp1p22、利用信號量實現(xiàn)前趨關(guān)系、利用信號量實現(xiàn)前趨關(guān)系2、利用信號量實現(xiàn)前趨關(guān)系、利用信號量實現(xiàn)前趨關(guān)系S1S2S5S3S4S6abcdgfeVar a,b,

50、c,d,e,f,g: semaphore:=0,0,0,0,0,0,0;begin parbegin begin S1;signal(a);signal(b);end; begin wait(a);S2;signal(c);signal(d);end; begin wait(c);S3;signal(e);end; begin wait(d);S4;signal(f);end; begin wait(b);S5;signal(g);end; begin wait(e);wait(f);wait(g);S6;end; parendend2.3.4 管程機制管程機制信號量同步的缺點信號量同步的缺點

51、 同步操作分散：同步操作分散：信號量機制中，同步操作分散在信號量機制中，同步操作分散在各個進程中，使用不當(dāng)就可能導(dǎo)致各進程死鎖（各個進程中，使用不當(dāng)就可能導(dǎo)致各進程死鎖（如如P P、V V操作的次序錯誤、重復(fù)或遺漏）操作的次序錯誤、重復(fù)或遺漏） 易讀性差：易讀性差：要了解對于一組共享變量及信號量的要了解對于一組共享變量及信號量的操作是否正確，必須通讀整個系統(tǒng)或者并發(fā)程序操作是否正確，必須通讀整個系統(tǒng)或者并發(fā)程序 不利于修改和維護：不利于修改和維護：各模塊的獨立性差，任一組各模塊的獨立性差，任一組變量或一段代碼的修改都可能影響全局變量或一段代碼的修改都可能影響全局 正確性難以保證：正確性難以保證

52、：操作系統(tǒng)或并發(fā)程序通常很大操作系統(tǒng)或并發(fā)程序通常很大，很難保證這樣一個復(fù)雜的系統(tǒng)沒有邏輯錯誤，很難保證這樣一個復(fù)雜的系統(tǒng)沒有邏輯錯誤 管程：管程：代表共享資源的數(shù)據(jù)結(jié)構(gòu)，以及由對該共享數(shù)據(jù)結(jié)構(gòu)實施操作的一組過程所組成的資源管理程序，共同構(gòu)成了一個操作系統(tǒng)的資源管理模塊。 管程的組成：管程的組成： 管程的名稱 局部于管程內(nèi)部的共享數(shù)據(jù)結(jié)構(gòu)說明； 對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程； 對局部于管程內(nèi)部的共享數(shù)據(jù)設(shè)置初始值的語句。1、管程（、管程（Monitors）的定義）的定義Hansen圖圖 2-13 管程的示意圖管程的示意圖 1、管程的定義、管程的定義初始化代碼初始化代碼一組操作過程一組操作過程

53、共享數(shù)據(jù)共享數(shù)據(jù)條件（不忙）隊列條件（不忙）隊列進入隊列進入隊列 管程的語法：管程的語法： type monitor_name=monitor define ; use ; procedure (); begin end; function (): 值類型; begin end; begin ; end 1、管程的定義、管程的定義管程名：monitor_name局部于管程的共享變量說明；對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程；對局部于管程的數(shù)據(jù)設(shè)置初始值的語句1、管程的定義、管程的定義 管程的特點：管程的特點： 局部性：局部性：管程內(nèi)的局部變量只能被局部于管程內(nèi)的過程所訪問；反之亦然，即局部于管程內(nèi)的

54、過程只能訪問管程內(nèi)的變量； 訪問接口：訪問接口：任何進程只能通過調(diào)用管程提供的過程入口進入管程 互斥性：互斥性：任一時刻，最多只能有一個進程在管程中執(zhí)行注：注：保證進程互斥地進入管程是由編譯器負責(zé)的。即管程是一 種編程語言的構(gòu)件，它的實現(xiàn)需要得到編譯器的支持。1、管程的定義、管程的定義 管程的特性（從語言角度看）：管程的特性（從語言角度看）： 模塊化：模塊化：管程是一個基本程序單位，可以單獨編譯。 抽象數(shù)據(jù)類型：抽象數(shù)據(jù)類型：管程中不僅有數(shù)據(jù)，而且有對數(shù)據(jù)的操作。 信息：信息：管程中的數(shù)據(jù)結(jié)構(gòu)只能被管程中的過程訪問，這些過程也是在管程內(nèi)部定義的，供管程外的進程調(diào)用，而管程中的數(shù)據(jù)結(jié)構(gòu)以及過程（

55、函數(shù)）的具體實現(xiàn)外部不可見。1、管程的定義、管程的定義 管程和進程的區(qū)別：管程和進程的區(qū)別： 定義的數(shù)據(jù)結(jié)構(gòu)：定義的數(shù)據(jù)結(jié)構(gòu)：進程定義的是私有數(shù)據(jù)結(jié)構(gòu)PCB；管程定義的是公共數(shù)據(jù)結(jié)構(gòu)； 數(shù)據(jù)結(jié)構(gòu)上的操作：數(shù)據(jù)結(jié)構(gòu)上的操作：進程由順序程序執(zhí)行有關(guān)操作；管程主要進行同步操作和初始化操作； 設(shè)置的目的：設(shè)置的目的：設(shè)置進程的目的在于實現(xiàn)系統(tǒng)的并發(fā)性；管程的設(shè)置則是解決共享資源的互斥使用問題； 工作方式：工作方式：進程通過調(diào)用管程中的過程對共享數(shù)據(jù)結(jié)構(gòu)實行操作，因此進程是主動工作方式，管程是被動工作方式； 并發(fā)性：并發(fā)性：進程之間能并發(fā)執(zhí)行，而管程則不能與其調(diào)用者并發(fā)； 進程具有動態(tài)性，由創(chuàng)建而生，由

56、撤消而亡；而管程是操作系統(tǒng)的一個資源管理模塊，供進程調(diào)用。 實現(xiàn)要素實現(xiàn)要素 管程中的共享變量在管程外部是不可見的，外部只能通過管程中的共享變量在管程外部是不可見的，外部只能通過調(diào)用管程中所說明的調(diào)用管程中所說明的外部過程外部過程（函數(shù)）來間接地訪問管程（函數(shù)）來間接地訪問管程中的共享變量；中的共享變量； 為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定為了保證管程共享變量的數(shù)據(jù)完整性，規(guī)定管程互斥進入管程互斥進入； 管程通常是用來管理資源的，因而在管程中應(yīng)當(dāng)設(shè)有管程通常是用來管理資源的，因而在管程中應(yīng)當(dāng)設(shè)有進程進程等待隊列等待隊列以及相應(yīng)的以及相應(yīng)的等待及喚醒操作等待及喚醒操作； 訪問控制訪問控制 局

57、部于管程內(nèi)部的數(shù)據(jù)結(jié)構(gòu)，僅能被局部于管程的過程所局部于管程內(nèi)部的數(shù)據(jù)結(jié)構(gòu)，僅能被局部于管程的過程所訪問，任何管程外的過程都不能訪問它；訪問，任何管程外的過程都不能訪問它； 局部于管程的過程也僅能訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)局部于管程的過程也僅能訪問管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)2、管程的設(shè)計與實現(xiàn)、管程的設(shè)計與實現(xiàn) 管程的設(shè)計管程的設(shè)計 必須設(shè)置同步工具，如操作原語必須設(shè)置同步工具，如操作原語wait和和signal，來保證對，來保證對臨界資源的正確訪問；臨界資源的正確訪問； 引入條件變量，解決進程調(diào)用管程過程中被阻塞或掛起時，引入條件變量，解決進程調(diào)用管程過程中被阻塞或掛起時，釋放管程的相關(guān)控制；釋放管程的相關(guān)控

58、制； 管程關(guān)于進程同步互斥的保證管程關(guān)于進程同步互斥的保證 管程每次只準許一個進程進入以保證互斥管程每次只準許一個進程進入以保證互斥 原語原語wait與與signal2、管程的設(shè)計與實現(xiàn)、管程的設(shè)計與實現(xiàn) 條件變量：條件變量：是局部于管程的變量，用于區(qū)分不同的是局部于管程的變量，用于區(qū)分不同的阻塞原因阻塞原因 格式格式： Var x, y:condition。 條件變量是一種條件變量是一種抽象數(shù)據(jù)類型抽象數(shù)據(jù)類型，每個條件變量保存，每個條件變量保存了一個了一個鏈表鏈表。 條件變量的操作：條件變量的操作： x.wait操作操作：將執(zhí)行進程掛到與條件變量：將執(zhí)行進程掛到與條件變量x相應(yīng)的等待隊列相

59、應(yīng)的等待隊列上，并釋放管程，如果沒有等待進程，上，并釋放管程，如果沒有等待進程，x.signal不起任何作不起任何作用。用。 signal操作操作：喚醒與：喚醒與x相應(yīng)的等待隊列上的一個進程，如果相應(yīng)的等待隊列上的一個進程，如果存在多個這樣的進程，則選擇其中的一個，但如果沒有被存在多個這樣的進程，則選擇其中的一個，但如果沒有被阻塞的進程，則阻塞的進程，則x.signal操作不產(chǎn)生任何后果。操作不產(chǎn)生任何后果。3、條件變量、條件變量2.4 經(jīng)典進程的同步問題經(jīng)典進程的同步問題2.4.1 生產(chǎn)者生產(chǎn)者消費者問題消費者問題消息緩沖池消息緩沖池 生產(chǎn)者產(chǎn)生的消息放入緩沖池內(nèi)； 消費者從緩沖池內(nèi)取走消息

60、消費； 消費者消費后的空白消息塊放進空白緩沖池內(nèi)供生產(chǎn)者使用。23121 算法分析算法分析 兩類進程兩類進程：生產(chǎn)者進程和消費者進程 （1）進程間的關(guān)系）進程間的關(guān)系 生產(chǎn)者生產(chǎn)消息后消費者消費 消費者消費后的空白緩沖塊由生產(chǎn)者生產(chǎn)消息 （2）隊列的操作）隊列的操作 兩個共享隊列： 消息緩沖隊列 空白緩沖隊列 多個進程共享一個隊列 是否需要保護 進程間的關(guān)系進程間的關(guān)系 生產(chǎn)者生產(chǎn)消息 后 消費者消費的合作關(guān)系 消費者消費 后 的空白緩沖塊由生產(chǎn)者生產(chǎn)消息的合作關(guān)系 進程間在隊列操作上的互斥關(guān)系 信號量信號量 full：私有信號量，表示緩沖池中滿緩沖區(qū)數(shù)量 empty：私有信號量，表示緩沖池中