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

1、第二章第二章 進(jìn)程管理進(jìn)程管理本章要點(diǎn)（本章要點(diǎn)（1/3） 目標(biāo)：目標(biāo)：建立起進(jì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)程的狀態(tài) 進(jìn)程控制塊 進(jìn)程同步的基本概念進(jìn)程同步的基本概念 臨界資源 臨界區(qū) 同步機(jī)制應(yīng)遵循的準(zhǔn)則本章要點(diǎn)（本章要點(diǎn)（2/3） 信號(hào)量機(jī)制及其應(yīng)用信號(hào)量機(jī)制及其應(yīng)用 信號(hào)量的含義 信號(hào)量的物理意義 用信號(hào)量實(shí)現(xiàn)互斥 用信號(hào)量實(shí)現(xiàn)前趨關(guān)系 經(jīng)典進(jìn)程的同步問(wèn)題經(jīng)典進(jìn)程的同步問(wèn)題 生產(chǎn)者-消費(fèi)問(wèn)題 哲學(xué)家進(jìn)餐問(wèn)題 讀者-寫者問(wèn)題這些

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

33、品；一次只能取走一個(gè)產(chǎn)品；緩沖區(qū)滿則生產(chǎn)者不能放產(chǎn)品；緩沖區(qū)滿則生產(chǎn)者不能放產(chǎn)品；緩沖區(qū)空則消費(fèi)者不能取產(chǎn)品；緩沖區(qū)空則消費(fèi)者不能取產(chǎn)品；生產(chǎn)者進(jìn)程生產(chǎn)者進(jìn)程消費(fèi)者進(jìn)程消費(fèi)者進(jìn)程并發(fā)并發(fā)012345 n-1生產(chǎn)者消費(fèi)者緩沖池inoutcounter數(shù)據(jù)結(jié)構(gòu)：var n:integer; /*具有n個(gè)緩沖區(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)者消費(fèi)者問(wèn)題消費(fèi)者問(wè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;說(shuō)明：nextp:局部變量，用于暫時(shí)存放每次生產(chǎn)出的消息。 nextc:局部變量，用于存放每次要消費(fèi)的消息。register1:=counter;register1:=register1+1;counter:= register1;3、生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題inout012345673、生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題register 1:=counter; register 1:=register+1; counter:=register 1; register 2:=counter；register 2: =register 2 -1;counter:=

36、 register 2 按什么順序執(zhí)行時(shí)，按什么順序執(zhí)行時(shí)，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為了解決以上問(wèn)題，可將為了解決以上問(wèn)題，可將counter作為臨界資源作為

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

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

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

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

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

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

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時(shí)，可進(jìn)行資源預(yù)留 di：申請(qǐng)個(gè)數(shù) 一次可申請(qǐng)一種資源的多個(gè)4、信號(hào)量集、信號(hào)量集 信號(hào)量集流程信號(hào)量集流程 1 1）將正在執(zhí)行的進(jìn)程移入第一）將正在執(zhí)行的進(jìn)程移入第一個(gè)個(gè)S Si i

44、t ti i的等待隊(duì)列中；的等待隊(duì)列中；2 2）將程序指針指向該進(jìn)程中）將程序指針指向該進(jìn)程中SwaitSwait操作開始處操作開始處4、信號(hào)量集、信號(hào)量集 信號(hào)量集流程信號(hào)量集流程將與將與S Si i相關(guān)的等待隊(duì)列相關(guān)的等待隊(duì)列中的所有進(jìn)程移到準(zhǔn)備中的所有進(jìn)程移到準(zhǔn)備隊(duì)列隊(duì)列4、信號(hào)量集、信號(hào)量集4、信號(hào)量集、信號(hào)量集應(yīng)用應(yīng)用61A52B41C到達(dá)順序：P1，P2，P3，P4資源申請(qǐng)向量：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四個(gè)進(jìn)程對(duì)應(yīng)的代碼段為：四個(gè)進(jìn)程對(duì)應(yīng)的代碼段為：4、信號(hào)量集、信號(hào)量集應(yīng)用應(yīng)用61A

46、52B41C到達(dá)順序：P1，P2，P3，P4資源申請(qǐng)向量：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到達(dá)333P2到達(dá)112P3到達(dá), S2t2阻塞阻塞P4到達(dá), S2t2阻塞阻塞P1執(zhí)行完成，釋放資源433P3 P4都被喚醒322P3 申請(qǐng)到資源P4 申請(qǐng)到資源211 (1) Swait(S, d, d)。 此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量S， 但允許它每次申請(qǐng)d個(gè)資源，

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

48、進(jìn)程互斥利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的進(jì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、利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥、利用信號(hào)量實(shí)現(xiàn)進(jìn)程

49、互斥wait(mutex)和和signal(mutex)必須成對(duì)出現(xiàn)必須成對(duì)出現(xiàn) 保證進(jìn)程間的前驅(qū)、后繼關(guān)系2、利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系、利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系Pi代表進(jìn)程；Si代表Pi中的語(yǔ)句；s為具有前驅(qū)關(guān)系的兩進(jìn)程的公用信號(hào)量，其初值為0。var s:semaphore:=0;begin parbegin begin S1; signal(s);end; begin wait(s); S2; end; parendendS1S2sp1p22、利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系、利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系2、利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系、利用信號(hào)量實(shí)現(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 管程機(jī)制管程機(jī)制信號(hào)量同步的缺點(diǎn)信號(hào)量同步的缺點(diǎn)

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

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

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

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

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

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

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

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

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

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