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

1、操作系統(tǒng)第2章進(jìn)程管理操作系統(tǒng)第2章進(jìn)程管理2.1 進(jìn)程的基本概念 2.1.1 程序的順序執(zhí)行及其特征 1. 程序的順序執(zhí)行 僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計(jì)算時(shí)，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。2022/9/21計(jì)算機(jī)科學(xué)系2.1 進(jìn)程的基本概念 2.1.1 程序的順序執(zhí)行及其特征 圖 2-1 程序的順序執(zhí)行 S1: a=x+y; S2: b=a-5; S3: c=b+1;2022/9/21計(jì)算機(jī)科學(xué)系圖 2-1 程序的順序執(zhí)行 S1: a=x+y; 2022. 程序順序執(zhí)行時(shí)的特征 順序性：(2) 封閉性： (3) 可再現(xiàn)性：

2、 2022/9/21計(jì)算機(jī)科學(xué)系2. 程序順序執(zhí)行時(shí)的特征 順序性：2022/9/19計(jì)算機(jī)2.1.2 前趨圖 前趨圖(Precedence Graph)是一個(gè)有向無循環(huán)圖，記為DAG(Directed Acyclic Graph)，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程，乃至一條語句；結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序(Partial Order)或前趨關(guān)系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可寫成PiPj，稱Pi是

3、Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(Initial Node)，把沒有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(Final Node)。2022/9/21計(jì)算機(jī)科學(xué)系2.1.2 前趨圖 前趨圖(Preceden 每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。 圖 2-2 前趨圖 2022/9/21計(jì)算機(jī)科學(xué)系 每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表對(duì)于圖 2-2(a)所示的前趨圖， 存在下述前趨關(guān)系： P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9

4、, P8P9或表示為： P=P1, P2, P3, P4, P5, P6, P7, P8, P9 = (P1, P2), (P1, P3), (P1, P4), (P2, P5), (P3, P5), (P4, P6), (P4, P7), (P5, P8), (P6, P8), (P7, P9), (P8, P9) 應(yīng)當(dāng)注意，前趨圖中必須不存在循環(huán)，但在圖2-2(b)中卻有著下述的前趨關(guān)系： S2S3, S3S2 2022/9/21計(jì)算機(jī)科學(xué)系對(duì)于圖 2-2(a)所示的前趨圖， 存在下述前趨關(guān)系： 2.1.3 程序的并發(fā)執(zhí)行及其特征 1. 程序的并發(fā)執(zhí)行 圖 2-3 并發(fā)執(zhí)行時(shí)的前趨圖 20

5、22/9/21計(jì)算機(jī)科學(xué)系2.1.3 程序的并發(fā)執(zhí)行及其特征 1. 程序的并發(fā)執(zhí)行 圖在該例中存在下述前趨關(guān)系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。2022/9/21計(jì)算機(jī)科學(xué)系在該例中存在下述前趨關(guān)系： 2022/9/19計(jì)算機(jī)科學(xué)系圖 2-4 四條語句的前趨關(guān)系對(duì)于具有下述四條語句的程序段： S1: a=x+2 S2: b=y+4 S3: c=a+b S4: d=c+b 2022/9/21計(jì)算機(jī)科學(xué)系圖 2-4 四條語句的前趨關(guān)系對(duì)于具有下述四條語句的程序段：2. 程序并發(fā)

6、執(zhí)行時(shí)的特征 間斷性2) 失去封閉性 3) 不可再現(xiàn)性 例如，有兩個(gè)循環(huán)程序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。 2022/9/21計(jì)算機(jī)科學(xué)系2. 程序并發(fā)執(zhí)行時(shí)的特征 間斷性 例如，有

7、兩個(gè)2.1.4 進(jìn)程的特征與狀態(tài) 1. 進(jìn)程的特征和定義結(jié)構(gòu)特征(程序段、數(shù)據(jù)段和進(jìn)程控制塊PCB)動(dòng)態(tài)性 （最基本的特征，與程序的區(qū)別）并發(fā)性（重要特征）獨(dú)立性 （運(yùn)行，分配資源，調(diào)度）異步性2022/9/21計(jì)算機(jī)科學(xué)系2.1.4 進(jìn)程的特征與狀態(tài) 1. 進(jìn)程的特征和定義2022 較典型的進(jìn)程定義有： (1) 進(jìn)程是程序的一次執(zhí)行。 (2) 進(jìn)程是一個(gè)程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時(shí)所發(fā)生的活動(dòng)。 (3) 進(jìn)程是程序在一個(gè)數(shù)據(jù)集合上運(yùn)行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。 在引入了進(jìn)程實(shí)體的概念后，本書把傳統(tǒng)OS中的進(jìn)程定義為：“進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和

8、調(diào)度的一個(gè)獨(dú)立單位”。 2022/9/21計(jì)算機(jī)科學(xué)系 較典型的進(jìn)程定義有： 2022/9/19計(jì)算機(jī)科進(jìn)程與程序的區(qū)別： (1) 程序是指令的有序集合，其本身沒有任何運(yùn)行的含義，是一個(gè)靜態(tài)的概念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過程，它是一個(gè)動(dòng)態(tài)的概念。(2) 程序可以作為一種軟件資料長(zhǎng)期存在，而進(jìn)程是有一定生命期的。程序是永久的，進(jìn)程是暫時(shí)的。(3) 進(jìn)程更能真實(shí)地描述并發(fā)，而程序不能(4) 程序是進(jìn)程的組成部分(5) 進(jìn)程具有創(chuàng)建其他進(jìn)程的功能，而程序沒有(6) 同一程序同時(shí)運(yùn)行于若干個(gè)數(shù)據(jù)集合上，它將屬于若干個(gè)不同的進(jìn)程。也就是說同一程序可以對(duì)應(yīng)多個(gè)進(jìn)程 2022/9/21計(jì)算機(jī)科學(xué)系

9、進(jìn)程與程序的區(qū)別： 2022/9/19計(jì)算機(jī)科學(xué)系思考？為什么引入進(jìn)程？2022/9/21計(jì)算機(jī)科學(xué)系思考？為什么引入進(jìn)程？2022/9/19計(jì)算2. 進(jìn)程的三種基本狀態(tài) (1)就緒(Ready)狀態(tài) (2)執(zhí)行狀態(tài) (3) 阻塞狀態(tài) 2022/9/21計(jì)算機(jī)科學(xué)系2. 進(jìn)程的三種基本狀態(tài) (1)就緒(Ready)狀態(tài) 20圖 2-5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 2022/9/21計(jì)算機(jī)科學(xué)系圖 2-5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 2022/9/19計(jì)3. 掛起狀態(tài) 引入掛起狀態(tài)的原因： 終端用戶的請(qǐng)求；父進(jìn)程請(qǐng)求；負(fù)荷調(diào)節(jié)的需要；操作系統(tǒng)的需要；對(duì)換需要。掛起狀態(tài)實(shí)際是暫時(shí)從內(nèi)存中被淘汰出去

10、的進(jìn)程。2022/9/21計(jì)算機(jī)科學(xué)系3. 掛起狀態(tài) 2022/9/19計(jì)算機(jī)科學(xué)系2) 進(jìn)程狀態(tài)的轉(zhuǎn)換 活動(dòng)就緒靜止就緒。 (2) 活動(dòng)阻塞靜止阻塞。 (3) 靜止就緒活動(dòng)就緒。 (4) 靜止阻塞活動(dòng)阻塞。 2022/9/21計(jì)算機(jī)科學(xué)系2) 進(jìn)程狀態(tài)的轉(zhuǎn)換 活動(dòng)就緒靜止就緒。 2022/9/1具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 2022/9/21計(jì)算機(jī)科學(xué)系具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 2022/9/19計(jì)算機(jī)科學(xué)系2五狀態(tài)進(jìn)程模型 引入創(chuàng)建狀態(tài)和終止?fàn)顟B(tài) （1）創(chuàng)建狀態(tài)作用 （2）終止?fàn)顟B(tài)作用等待條件滿足2022/9/21計(jì)算機(jī)科學(xué)系2五狀態(tài)進(jìn)程模型 引入創(chuàng)建狀態(tài)和終止?fàn)顟B(tài) 3掛起狀態(tài)進(jìn)程模型（）單掛

11、起狀態(tài)進(jìn)程模型2022/9/21計(jì)算機(jī)科學(xué)系3掛起狀態(tài)進(jìn)程模型（）單掛起狀態(tài)進(jìn)程模型2022/9/13掛起狀態(tài)進(jìn)程模型（）雙掛起狀態(tài)進(jìn)程模型2022/9/21計(jì)算機(jī)科學(xué)系3掛起狀態(tài)進(jìn)程模型（）雙掛起狀態(tài)進(jìn)程模型2022/9/1思考？1如果系統(tǒng)中有N個(gè)進(jìn)程，運(yùn)行的進(jìn)程最多幾個(gè)，最少幾個(gè)；就緒進(jìn)程最多幾個(gè)最少幾個(gè)；等待進(jìn)程最多幾個(gè)，最少幾個(gè)？2. 有沒有這樣的狀態(tài)轉(zhuǎn)換，為什么？ 等待運(yùn)行； 就緒等待2022/9/21計(jì)算機(jī)科學(xué)系思考？1如果系統(tǒng)中有N個(gè)進(jìn)程，運(yùn)行的進(jìn)程最課堂練習(xí)當(dāng)某個(gè)作業(yè)被作業(yè)調(diào)度程序選中，進(jìn)入內(nèi)存開始運(yùn)行時(shí)，作業(yè)的狀態(tài)為：.提交狀態(tài) .完成狀態(tài).執(zhí)行狀態(tài) .就緒狀態(tài)進(jìn)程在發(fā)出I/

12、O請(qǐng)求后，可能導(dǎo)致下列哪種進(jìn)程狀態(tài)演變？A. 就緒 執(zhí)行 B. 執(zhí)行 就緒C. 阻塞 執(zhí)行 D. 執(zhí)行 阻塞單處理機(jī)系統(tǒng)中，可并行的是I 進(jìn)程與進(jìn)程 II 處理機(jī)與設(shè)備III 處理機(jī)與通道 IV 設(shè)備與設(shè)備 AI、II和III B. I、II和IV C. I、III和IV D. II、III和IV2022/9/21計(jì)算機(jī)科學(xué)系課堂練習(xí)當(dāng)某個(gè)作業(yè)被作業(yè)調(diào)度程序選中，進(jìn)入內(nèi)存開始運(yùn)行時(shí)，作2.1.5 進(jìn)程控制塊 1. 進(jìn)程控制塊的作用 進(jìn)程控制塊的作用是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f，OS是根據(jù)PCB來對(duì)并發(fā)

13、執(zhí)行的進(jìn)程進(jìn)行控制和管理的。 為了描述一個(gè)進(jìn)程和其它進(jìn)程以及系統(tǒng)資源的關(guān)系，為了刻畫一個(gè)進(jìn)程在各個(gè)不同時(shí)期所處的狀態(tài)，人們采用了一個(gè)與進(jìn)程相聯(lián)系的數(shù)據(jù)塊，稱為進(jìn)程控制塊（PCB）。系統(tǒng)利用PCB來控制和管理進(jìn)程，所以PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志。 進(jìn)程與PCB是一一對(duì)應(yīng)的。2022/9/21計(jì)算機(jī)科學(xué)系2.1.5 進(jìn)程控制塊 1. 進(jìn)程控制塊的作用 2. 進(jìn)程控制塊中的信息 1) 進(jìn)程標(biāo)識(shí)符 進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程。一個(gè)進(jìn)程通常有兩種標(biāo)識(shí)符： (1) 內(nèi)部標(biāo)識(shí)符。在所有的操作系統(tǒng)中，都為每一個(gè)進(jìn) 程賦予一個(gè)惟一的數(shù)字標(biāo)識(shí)符，它通常是一個(gè)進(jìn)程的序號(hào)。 設(shè)置內(nèi)部標(biāo)識(shí)符主要是為了方便

14、系統(tǒng)使用。 (2) 外部標(biāo)識(shí)符。它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶(進(jìn)程)在訪問該進(jìn)程時(shí)使用。為了描述進(jìn)程的家族關(guān)系， 還應(yīng)設(shè)置父進(jìn)程標(biāo)識(shí)及子進(jìn)程標(biāo)識(shí)。此外，還可設(shè)置用戶標(biāo)識(shí)，以指示擁有該進(jìn)程的用戶。 2022/9/21計(jì)算機(jī)科學(xué)系 2. 進(jìn)程控制塊中的信息2022/9/19計(jì)算機(jī)科學(xué)系2) 處理機(jī)狀態(tài) 處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。 通用寄存器，又稱為用戶可視寄存器，它們是用戶程序可以訪問的，用于暫存信息， 在大多數(shù)處理機(jī)中，有 832 個(gè)通用寄存器，在RISC結(jié)構(gòu)的計(jì)算機(jī)中可超過 100 個(gè)； 指令計(jì)數(shù)器，其中存放了要訪問的下一條指令的地址； 程

15、序狀態(tài)字PSW，其中含有狀態(tài)信息，如條件碼、執(zhí)行方式、 中斷屏蔽標(biāo)志等； 用戶棧指針， 指每個(gè)用戶進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧，用于存放過程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。 2022/9/21計(jì)算機(jī)科學(xué)系2) 處理機(jī)狀態(tài) 2022/9/19計(jì)算機(jī)科學(xué)系3) 進(jìn)程調(diào)度信息 在PCB中還存放一些與進(jìn)程調(diào)度和進(jìn)程對(duì)換有關(guān)的信息，包括： 進(jìn)程狀態(tài)，指明進(jìn)程的當(dāng)前狀態(tài)， 作為進(jìn)程調(diào)度和對(duì)換時(shí)的依據(jù)； 進(jìn)程優(yōu)先級(jí)，用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)， 優(yōu)先級(jí)高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)； 進(jìn)程調(diào)度所需的其它信息，它們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時(shí)間總和、

16、 進(jìn)程已執(zhí)行的時(shí)間總和等； 事件，是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。 2022/9/21計(jì)算機(jī)科學(xué)系3) 進(jìn)程調(diào)度信息 2022/9/19計(jì)算機(jī)科學(xué)系4) 進(jìn)程控制信息 進(jìn)程控制信息包括： 程序和數(shù)據(jù)的地址， 是指進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存地(首)址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從PCB中找到其程序和數(shù)據(jù)； 進(jìn)程同步和通信機(jī)制，指實(shí)現(xiàn)進(jìn)程同步和進(jìn)程通信時(shí)必需的機(jī)制， 如消息隊(duì)列指針、信號(hào)量等，它們可能全部或部分地放在PCB中； 資源清單，是一張列出了除CPU以外的、進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單； 鏈接指針， 它給出了本進(jìn)程(PCB)所在隊(duì)列

17、中的下一個(gè)進(jìn)程的PCB的首地址。 2022/9/21計(jì)算機(jī)科學(xué)系4) 進(jìn)程控制信息 2022/9/19計(jì)算機(jī)科學(xué)系3. 進(jìn)程控制塊的組織方式 1) 鏈接方式 PCB鏈接隊(duì)列示意圖 2022/9/21計(jì)算機(jī)科學(xué)系3. 進(jìn)程控制塊的組織方式 1) 鏈接方式 PCB鏈接隊(duì)列示2) 索引方式 按索引方式組織PCB 2022/9/21計(jì)算機(jī)科學(xué)系2) 索引方式 按索引方式組織PCB 2022/9/19計(jì)算2.2 進(jìn) 程 控 制 進(jìn)程控制是進(jìn)程管理中最基本的功能。它用于創(chuàng)建一個(gè)新進(jìn)程，終止一個(gè)已完成的進(jìn)程，或終止一個(gè)因出現(xiàn)某事件而使其無法運(yùn)行下去的進(jìn)程，還可負(fù)責(zé)進(jìn)程運(yùn)行中的狀態(tài)轉(zhuǎn)換。進(jìn)程控制就是對(duì)系統(tǒng)中的

18、所有進(jìn)程實(shí)施管理，進(jìn)程控制一般有原語來實(shí)現(xiàn)。 所謂原語是一種特殊的系統(tǒng)功能調(diào)用，它可以完成一個(gè)特定的功能，其特點(diǎn)是原語執(zhí)行時(shí)不可被中斷，其作用是為了實(shí)現(xiàn)進(jìn)程的通信和控制。 常用原語：創(chuàng)建原語終止原語阻塞原語、喚醒原語2022/9/21計(jì)算機(jī)科學(xué)系2.2 進(jìn) 程 控 制 進(jìn)程控制是進(jìn)程管理中最2.2 進(jìn) 程 控 制 2.2.1 進(jìn)程的創(chuàng)建 1. 進(jìn)程圖(Process Graph) 進(jìn)程樹 2022/9/21計(jì)算機(jī)科學(xué)系2.2 進(jìn) 程 控 制 2.2.1 進(jìn)程的創(chuàng)建 1. 進(jìn)程圖2. 引起創(chuàng)建進(jìn)程的事件 用戶登錄。 (2) 作業(yè)調(diào)度。 (3) 提供服務(wù)。 （文件打?。?4) 應(yīng)用請(qǐng)求。 （輸入，

19、處理，打?。┫到y(tǒng)內(nèi)核用戶自己2022/9/21計(jì)算機(jī)科學(xué)系2. 引起創(chuàng)建進(jìn)程的事件 用戶登錄。 系統(tǒng)內(nèi)核用戶自己2023. 進(jìn)程的創(chuàng)建(Creation of Progress) (1)申請(qǐng)空白PCB。 (2) 為新進(jìn)程分配資源。 (3) 初始化進(jìn)程控制塊。 (4) 將新進(jìn)程插入就緒隊(duì)列，如果進(jìn)程就緒隊(duì)列能夠接納新進(jìn)程， 便將新進(jìn)程插入就緒隊(duì)列。 2022/9/21計(jì)算機(jī)科學(xué)系3. 進(jìn)程的創(chuàng)建(Creation of Progress)2.2.2 進(jìn)程的終止 1. 引起進(jìn)程終止(Termination of Process)的事件 1) 正常結(jié)束 在任何計(jì)算機(jī)系統(tǒng)中，都應(yīng)有一個(gè)用于表示進(jìn)程已經(jīng)

20、運(yùn)行完成的指示。例如，在批處理系統(tǒng)中，通常在程序的最后安排一條Halt指令或終止的系統(tǒng)調(diào)用。當(dāng)程序運(yùn)行到Halt指令時(shí)，將產(chǎn)生一個(gè)中斷，去通知OS本進(jìn)程已經(jīng)完成。2022/9/21計(jì)算機(jī)科學(xué)系2.2.2 進(jìn)程的終止 1. 引起進(jìn)程終止(T 2) 異常結(jié)束 在進(jìn)程運(yùn)行期間，由于出現(xiàn)某些錯(cuò)誤和故障而迫使進(jìn)程終止。這類異常事件很多，常見的有：越界錯(cuò)誤保護(hù)錯(cuò)非法指令特權(quán)指令錯(cuò)運(yùn)行超時(shí)等待超時(shí)算術(shù)運(yùn)算錯(cuò)I/O故障2022/9/21計(jì)算機(jī)科學(xué)系 2) 異常結(jié)束 2022/9/19計(jì)算機(jī)科學(xué) 3) 外界干預(yù) 外界干預(yù)并非指在本進(jìn)程運(yùn)行中出現(xiàn)了異常事件，而是指進(jìn)程應(yīng)外界的請(qǐng)求而終止運(yùn)行。這些干預(yù)有： 操作員或

21、操作系統(tǒng)干預(yù) 父進(jìn)程請(qǐng)求父進(jìn)程終止 2022/9/21計(jì)算機(jī)科學(xué)系 3) 外界干預(yù) 2022/9/19計(jì)算機(jī)科學(xué)系 2. 進(jìn)程的終止過程 (1) 根據(jù)被終止進(jìn)程的標(biāo)識(shí)符，從PCB集合中檢索出該進(jìn)程的PCB，從中讀出該進(jìn)程的狀態(tài)。 (2) 若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止該進(jìn)程的執(zhí)行，并置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。 (3) 若該進(jìn)程還有子孫進(jìn)程，還應(yīng)將其所有子孫進(jìn)程予以終止，以防他們成為不可控的進(jìn)程。 (4) 將被終止進(jìn)程所擁有的全部資源，或者歸還給其父進(jìn)程， 或者歸還給系統(tǒng)。 (5) 將被終止進(jìn)程(它的PCB)從所在隊(duì)列(或鏈表)中移出， 等待其他程序來搜集信息

22、。 2022/9/21計(jì)算機(jī)科學(xué)系 2. 進(jìn)程的終止過程 2022/9/19計(jì)算機(jī)2.2.3 進(jìn)程的阻塞與喚醒1. 引起進(jìn)程阻塞和喚醒的事件 請(qǐng)求系統(tǒng)服務(wù) 啟動(dòng)某種操作新數(shù)據(jù)尚未到達(dá)無新工作可做 2022/9/21計(jì)算機(jī)科學(xué)系2.2.3 進(jìn)程的阻塞與喚醒1. 引起進(jìn)程阻塞和喚醒的事件 2. 進(jìn)程阻塞過程 正在執(zhí)行的進(jìn)程，當(dāng)發(fā)現(xiàn)上述某事件時(shí)，由于無法繼續(xù)執(zhí)行，于是進(jìn)程便通過調(diào)用阻塞原語block把自己阻塞。可見，進(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為。進(jìn)入block過程后，由于此時(shí)該進(jìn)程還處于執(zhí)行狀態(tài)，所以應(yīng)先立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞，并將PCB插入阻塞隊(duì)列。如果系統(tǒng)

23、中設(shè)置了因不同事件而阻塞的多個(gè)阻塞隊(duì)列，則應(yīng)將本進(jìn)程插入到具有相同事件的阻塞(等待)隊(duì)列。 最后，轉(zhuǎn)調(diào)度程序進(jìn)行重新調(diào)度，將處理機(jī)分配給另一就緒進(jìn)程，并進(jìn)行切換，亦即，保留被阻塞進(jìn)程的處理機(jī)狀態(tài)(在PCB中)，再按新進(jìn)程的PCB中的處理機(jī)狀態(tài)設(shè)置CPU的環(huán)境。 2022/9/21計(jì)算機(jī)科學(xué)系 2. 進(jìn)程阻塞過程 2022/9/19計(jì)算機(jī) 3. 進(jìn)程喚醒過程 當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時(shí)，如I/O完成或其所期待的數(shù)據(jù)已經(jīng)到達(dá)，則由有關(guān)進(jìn)程(比如，用完并釋放了該I/O設(shè)備的進(jìn)程)調(diào)用喚醒原語wakeup( )，將等待該事件的進(jìn)程喚醒。喚醒原語執(zhí)行的過程是：首先把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列

24、中移出，將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒，然后再將該P(yáng)CB插入到就緒隊(duì)列中。 2022/9/21計(jì)算機(jī)科學(xué)系 3. 進(jìn)程喚醒過程 2022/9/19計(jì)算機(jī)2.2.4 進(jìn)程的掛起與激活 1. 進(jìn)程的掛起 當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí)，比如，用戶進(jìn)程請(qǐng)求將自己掛起，或父進(jìn)程請(qǐng)求將自己的某個(gè)子進(jìn)程掛起， 系統(tǒng)將利用掛起原語suspend( )將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。掛起原語的執(zhí)行過程是：首先檢查被掛起進(jìn)程的狀態(tài)，若處于活動(dòng)就緒狀態(tài)，便將其改為靜止就緒；對(duì)于活動(dòng)阻塞狀態(tài)的進(jìn)程，則將之改為靜止阻塞。 為了方便用戶或父進(jìn)程考查該進(jìn)程的運(yùn)行情況而把該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域。最后，

25、若被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度。 2022/9/21計(jì)算機(jī)科學(xué)系2.2.4 進(jìn)程的掛起與激活 1. 進(jìn)程的 2. 進(jìn)程的激活過程 當(dāng)發(fā)生激活進(jìn)程的事件時(shí)，例如，父進(jìn)程或用戶進(jìn)程請(qǐng)求激活指定進(jìn)程，若該進(jìn)程駐留在外存而內(nèi)存中已有足夠的空間時(shí)，則可將在外存上處于靜止就緒狀態(tài)的進(jìn)程換入內(nèi)存。這時(shí)，系統(tǒng)將利用激活原語active( )將指定進(jìn)程激活。 激活原語先將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)，若是靜止就緒，便將之改為活動(dòng)就緒；若為靜止阻塞便將之改為活動(dòng)阻塞。假如采用的是搶占調(diào)度策略，則每當(dāng)有新進(jìn)程進(jìn)入就緒隊(duì)列時(shí)，應(yīng)檢查是否要進(jìn)行重新調(diào)度，即由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行

26、優(yōu)先級(jí)的比較，如果被激活進(jìn)程的優(yōu)先級(jí)更低，就不必重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運(yùn)行，把處理機(jī)分配給剛被激活的進(jìn)程。 2022/9/21計(jì)算機(jī)科學(xué)系 2. 進(jìn)程的激活過程 2022/9/19計(jì)算課堂練習(xí)24、下列選項(xiàng)中，導(dǎo)致創(chuàng)進(jìn)新進(jìn)程的操作是（C） I用戶成功登陸 II設(shè)備分配 III啟動(dòng)程序執(zhí)行A：僅I和II B：僅II和IIIC：僅I和III D：I，II，III2022/9/21計(jì)算機(jī)科學(xué)系課堂練習(xí)24、下列選項(xiàng)中，導(dǎo)致創(chuàng)進(jìn)新進(jìn)程的操作是（C）202思考？為什么創(chuàng)建進(jìn)程要用原語來實(shí)現(xiàn)？ 2 阻塞進(jìn)程在什么情況下會(huì)被喚醒？誰來喚醒它？2022/9/21計(jì)算機(jī)科學(xué)系思考？為什么創(chuàng)建進(jìn)程要用

27、原語來實(shí)現(xiàn)？202.3 進(jìn) 程 同 步 2.3.1 進(jìn)程同步的基本概念 1. 兩種形式的制約關(guān)系 間接相互制約關(guān)系。 (2) 直接相互制約關(guān)系。 2022/9/21計(jì)算機(jī)科學(xué)系2.3 進(jìn) 程 同 步 2.3.1 進(jìn)程同步的基本概念 1.2. 臨界資源(Critical Resouce) 生產(chǎn)者-消費(fèi)者(producer-consumer)問題是一個(gè)著名的進(jìn)程同步問題。它描述的是：有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費(fèi)者進(jìn)程去消費(fèi)。 為使生產(chǎn)者進(jìn)程與消費(fèi)者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個(gè)具有n個(gè)緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個(gè)緩沖區(qū)中； 消費(fèi)者進(jìn)程可從一個(gè)緩沖區(qū)

28、中取走產(chǎn)品去消費(fèi)。 盡管所有的生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程都是以異步方式運(yùn)行的，但它們之間必須保持同步，即不允許消費(fèi)者進(jìn)程到一個(gè)空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進(jìn)程向一個(gè)已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。 2022/9/21計(jì)算機(jī)科學(xué)系2. 臨界資源(Critical Resouce) 我們可利用一個(gè)數(shù)組來表示上述的具有n個(gè)(0，1，n-1)緩沖區(qū)的緩沖池。用輸入指針in來指示下一個(gè)可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個(gè)產(chǎn)品后，輸入指針加1；用一個(gè)輸出指針out來指示下一個(gè)可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品后，輸出指針加1。 由于這里的緩沖池是組織成循環(huán)緩沖的，故應(yīng)

29、把輸入指針加1表示成 in=(in+1)mod n；輸出指針加1表示成out=(out+1) mod n。當(dāng)(in+1) mod n=out時(shí)表示緩沖池滿；而in=out則表示緩沖池空。2022/9/21計(jì)算機(jī)科學(xué)系 我們可利用一個(gè)數(shù)組來表示上述的具有n個(gè)(0，1，此外，還引入了一個(gè)整型變量counter, 其初始值為0。每當(dāng)生產(chǎn)者進(jìn)程向緩沖池中投放一個(gè)產(chǎn)品后，使counter加1；反之，每當(dāng)消費(fèi)者進(jìn)程從中取走一個(gè)產(chǎn)品時(shí)， 使counter減1。2022/9/21計(jì)算機(jī)科學(xué)系此外，還引入了一個(gè)整型變量counter, 其初始值為0。每生產(chǎn)者和消費(fèi)者兩進(jìn)程共享下面的變量：var n, integ

30、er; type item=; var buffer:array0, 1, , n-1 of item; in, out: 0, 1, , n-1; counter: 0, 1, , n; 指針in和out初始化為1。在生產(chǎn)者和消費(fèi)者進(jìn)程的描述中，no-op是一條空操作指令，while condition do no-op語句表示重復(fù)的測(cè)試條件(condication)，重復(fù)測(cè)試應(yīng)進(jìn)行到該條件變?yōu)閒alse(假)，即到該條件不成立時(shí)為止。在生產(chǎn)者進(jìn)程中使用一局部變量nextp，用于暫時(shí)存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費(fèi)者進(jìn)程中，則使用一個(gè)局部變量nextc,用于存放每次要消費(fèi)的產(chǎn)品。 2022

31、/9/21計(jì)算機(jī)科學(xué)系生產(chǎn)者和消費(fèi)者兩進(jìn)程共享下面的變量：2022/9/19計(jì)算機(jī)producer: repeat produce 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; consumer the item in

32、nextc; until false; 2022/9/21計(jì)算機(jī)科學(xué)系producer: repeat 2022/9/19計(jì)算機(jī)科 雖然上面的生產(chǎn)者程序和消費(fèi)者程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的，但若并發(fā)執(zhí)行時(shí)，就會(huì)出現(xiàn)差錯(cuò)，問題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對(duì)它做加1操作，消費(fèi)者對(duì)它做減1操作，這兩個(gè)操作在用機(jī)器語言實(shí)現(xiàn)時(shí)， ?？捎孟旅娴男问矫枋觯簉egister 1=counter; register1=register 1+1; counter=register 1;register 2=counter;register 2=registe

33、r 2-1; counter=register 2; 2022/9/21計(jì)算機(jī)科學(xué)系 雖然上面的生產(chǎn)者程序和消費(fèi)者程序，在分別看時(shí) 假設(shè)：counter的當(dāng)前值是5。如果生產(chǎn)者進(jìn)程先執(zhí)行左列的三條機(jī)器語言語句，然后消費(fèi)者進(jìn)程再執(zhí)行右列的三條語句， 則最后共享變量counter的值仍為5；反之，如果讓消費(fèi)者進(jìn)程先執(zhí)行右列的三條語句，然后再讓生產(chǎn)者進(jìn)程執(zhí)行左列的三條語句，counter值也還是5，但是，如果按下述順序執(zhí)行： register1=counter; (register1=5) register1=register1+1; (register1=6) register2=counter;

34、 (register2=5) register2 =register2-1; (register2=4) counter=register1; (counter=6) counter=register2; (counter=4) 2022/9/21計(jì)算機(jī)科學(xué)系 假設(shè)：counter的當(dāng)前值是5。如果生產(chǎn)者進(jìn)3. 臨界區(qū)(critical section) 可把一個(gè)訪問臨界資源的循環(huán)進(jìn)程描述如下： repeat critical section; remainder section; until false; entry sectionexit section2022/9/21計(jì)算機(jī)科學(xué)系3.

35、臨界區(qū)(critical section) 可把一個(gè)訪4. 同步機(jī)制應(yīng)遵循的規(guī)則 空閑讓進(jìn)。(2) 忙則等待。 (3) 有限等待。 (4) 讓權(quán)等待。 2022/9/21計(jì)算機(jī)科學(xué)系4. 同步機(jī)制應(yīng)遵循的規(guī)則 空閑讓進(jìn)。2022/9/19計(jì)算2.3.2 信號(hào)量機(jī)制 1. 整型信號(hào)量 最初由Dijkstra把整型信號(hào)量定義為一個(gè)整型量，除初始化外，僅能通過兩個(gè)標(biāo)準(zhǔn)的原子操作(Atomic Operation) wait(S)和signal(S)來訪問。這兩個(gè)操作一直被分別稱為P、V操作。 wait和signal操作可描述為： wait(S): while S0 do no-op S=S-1; s

36、ignal(S): S=S+1; (1) 原子操作(2) 忙等待2022/9/21計(jì)算機(jī)科學(xué)系2.3.2 信號(hào)量機(jī)制 1. 整型信號(hào)量 2. 記錄型信號(hào)量 在整型信號(hào)量機(jī)制中的wait操作，只要是信號(hào)量S0， 就會(huì)不斷地測(cè)試。因此，該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則， 而是使進(jìn)程處于“忙等”的狀態(tài)。記錄型信號(hào)量機(jī)制，則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了“讓權(quán)等待”的策略后，又會(huì)出現(xiàn)多個(gè)進(jìn)程等待訪問同一臨界資源的情況。為此，在信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表L，用于鏈接上述的所有等待進(jìn)程。記錄型信號(hào)量是由于它采用了記錄型的數(shù)據(jù)結(jié)

37、構(gòu)而得名的。它所包含的上述兩個(gè)數(shù)據(jù)項(xiàng)可描述為： 2022/9/21計(jì)算機(jī)科學(xué)系 2. 記錄型信號(hào)量 2022/9/19計(jì)算type semaphore=record value:integer; L:list of process; end 相應(yīng)地，wait(S)和signal(S)操作可描述為： procedure wait(S) var S: semaphore; begin S.value =S.value-1; if S.value0 then block(S,L) end procedure signal(S) var S: semaphore; begin S.value =S.v

38、alue+1; if S.value0 then wakeup(S,L); end 2022/9/21計(jì)算機(jī)科學(xué)系type semaphore=record 2022/9/1 在記錄型信號(hào)量機(jī)制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目， 因而又稱為資源信號(hào)量。對(duì)它的每次wait操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類資源，因此描述為S.value=S.value-1；當(dāng)S.value0時(shí)，表示該類資源已分配完畢，因此進(jìn)程應(yīng)調(diào)用block原語，進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號(hào)量鏈表S.L中?？梢姡摍C(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。 此時(shí)S.value的絕對(duì)值表示在該信號(hào)量鏈表中已阻塞進(jìn)程的數(shù)

39、目。 對(duì)信號(hào)量的每次signal操作，表示執(zhí)行進(jìn)程釋放一個(gè)單位資源，故S.value=S.value+1操作表示資源數(shù)目加1。若加1后仍是S.value0，則表示在該信號(hào)量鏈表中，仍有等待該資源的進(jìn)程被阻塞，故還應(yīng)調(diào)用wakeup原語，將S.L鏈表中的第一個(gè)等待進(jìn)程喚醒。如果S.value的初值為1，表示只允許一個(gè)進(jìn)程訪問臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量。2022/9/21計(jì)算機(jī)科學(xué)系 在記錄型信號(hào)量機(jī)制中，S.value的初值表示3. AND型信號(hào)量 在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex和Emutex的操作， 即process A: process B: wait(Dmutex);

40、wait(Emutex); wait(Emutex); wait(Dmutex); 若進(jìn)程A和B按下述次序交替執(zhí)行wait操作： process A: wait(Dmutex); 于是Dmutex=0 process B: wait(Emutex); 于是Emutex=0 process A: wait(Emutex); 于是Emutex=-1 A阻塞 process B: wait(Dmutex); 于是Dmutex=-1 B阻塞 2022/9/21計(jì)算機(jī)科學(xué)系3. AND型信號(hào)量 在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過程中需要的所有資源，一次

41、性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。 由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)wait操作， 即Swait(Simultaneous wait)定義如下： 2022/9/21計(jì)算機(jī)科學(xué)系 AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行Swait(S1, S2, , Sn) if Si1 and and Sn1 then for i =1 to

42、n do Si=Si-1; endfor else place the process in the waiting queue associated with the first Si found with Si1, and set the program count of this process to the beginning of Swait operation endif Ssignal(S1, S2, , Sn) for i =1 to n do Si=Si+1; Remove all the process waiting in the queue associated wit

43、h Si into the ready queue. endfor; 2022/9/21計(jì)算機(jī)科學(xué)系Swait(S1, S2, , Sn) 2022/9/194. 信號(hào)量集 Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i=1 to n do Si=Si-di; endfor else Place the executing process in the waiting queue of the first Si with Siti and set its program counter to the beginni

44、ng of the Swait Operation. endif signal(S1, d1, , Sn, dn) for i=1 to n do Si =Si+di; Remove all the process waiting in the queue associated with Si into the ready queue endfor; 2022/9/21計(jì)算機(jī)科學(xué)系4. 信號(hào)量集 Swait(S1, t1, d1, , S 一般“信號(hào)量集”的幾種特殊情況： (1) Swait(S, d, d)。 此時(shí)在信號(hào)量集中只有一個(gè)信號(hào)量S， 但允許它每次申請(qǐng)d個(gè)資源，當(dāng)現(xiàn)有資源數(shù)少于d時(shí)

45、，不予分配。 (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)。 2022/9/21計(jì)算機(jī)科學(xué)系 一般“信號(hào)量集”的幾種特殊情況： 2022/2.3.3 信號(hào)量的應(yīng)用 1. 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥的進(jìn)程可描述如下： Var mutex:semaphore =1; begin parbegin process 1: begin

46、repeat wait(mutex); critical section signal(mutex); remainder seetion until false; end 2022/9/21計(jì)算機(jī)科學(xué)系2.3.3 信號(hào)量的應(yīng)用 1. 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥 利用process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend 2022/9/21計(jì)算機(jī)科學(xué)系process 2: begin 2022/9/19計(jì)算機(jī)科2. 利用信號(hào)量實(shí)現(xiàn)前趨

47、關(guān)系 圖 2-10 前趨圖舉例 2022/9/21計(jì)算機(jī)科學(xué)系2. 利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系 圖 2-10 前趨圖舉例 20 Var a,b,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(b); S3; signal(e); end; begin wait(c); S4; signal(f); end; begin wait(d); S5; signal(

48、g); end; begin wait(e); wait(f); wait(g); S6; end; parend end 2022/9/21計(jì)算機(jī)科學(xué)系 Var a,b,c,d,e,f,g; semaphore2.3.4 管 程 機(jī) 制 1. 管程的定義 管程由四部分組成： 局部于管程的共享變量說明； 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程； 對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語句;還須為管程賦予一個(gè)名字2022/9/21計(jì)算機(jī)科學(xué)系2.3.4 管 程 機(jī) 制 1. 管程的定義 管程圖 2-11 管程的示意圖 2022/9/21計(jì)算機(jī)科學(xué)系圖 2-11 管程的示意圖 2022/9/19計(jì)算機(jī)科學(xué)系管程的

49、語法如下： type monitor-name=monitor variable declarations procedure entry P1(); begin end; procedure entry P2(); begin end; procedure entry Pn(); begin end; begin initialization code; end 2022/9/21計(jì)算機(jī)科學(xué)系管程的語法如下： 2022/9/19計(jì)算機(jī)科學(xué)系2. 條件變量 管程中對(duì)每個(gè)條件變量，都須予以說明，其形式為：Var x, y:condition。該變量應(yīng)置于wait和signal之前，即可表示為X.

50、wait和X.signal。例如，由于共享數(shù)據(jù)被占用而使調(diào)用進(jìn)程等待，該條件變量的形式為：nonbusy:condition。此時(shí)， wait原語應(yīng)改為nonbusy.wait，相應(yīng)地，signal應(yīng)改為nonbusy.signal。 應(yīng)當(dāng)指出，X.signal操作的作用，是重新啟動(dòng)一個(gè)被阻塞的進(jìn)程，但如果沒有被阻塞的進(jìn)程，則X.signal操作不產(chǎn)生任何后果。這與信號(hào)量機(jī)制中的signal操作不同。因?yàn)?，后者總是要?zhí)行s =s+1操作，因而總會(huì)改變信號(hào)量的狀態(tài)。 2022/9/21計(jì)算機(jī)科學(xué)系2. 條件變量 管程中對(duì)每個(gè)條件變量，都須予接收進(jìn)程就緒隊(duì)列1就緒隊(duì)列2.就緒隊(duì)列n超時(shí)事件1發(fā)生事

51、件2發(fā)生等事件1等事件2.處理機(jī)終止進(jìn)程事件m發(fā)生等事件m2022/9/21計(jì)算機(jī)科學(xué)系接收進(jìn)程就緒隊(duì)列1就緒隊(duì)列2.就緒隊(duì)列n超時(shí)事件1發(fā)生事 如果有進(jìn)程Q處于阻塞狀態(tài)， 當(dāng)進(jìn)程P執(zhí)行了X.signal操作后，怎樣決定由哪個(gè)進(jìn)行執(zhí)行，哪個(gè)等待，可采用下述兩種方式之一進(jìn)行處理： (1) P等待，直至Q離開管程或等待另一條件。 (2) Q等待，直至P離開管程或等待另一條件。 采用哪種處理方式， 當(dāng)然是各執(zhí)一詞。 但是Hansan卻采用了第一種處理方式。 2022/9/21計(jì)算機(jī)科學(xué)系 如果有進(jìn)程Q處于阻塞狀態(tài)， 當(dāng)進(jìn)程P執(zhí)行了X2.4 經(jīng)典進(jìn)程的同步問題 生產(chǎn)者1生產(chǎn)者2生產(chǎn)者n消費(fèi)者1消費(fèi)者2

52、消費(fèi)者n2022/9/21計(jì)算機(jī)科學(xué)系2.4 經(jīng)典進(jìn)程的同步問題 生產(chǎn)者1生產(chǎn)者2生產(chǎn)者n消費(fèi)者1生產(chǎn)者消費(fèi)者緩沖池共享N個(gè)緩沖區(qū)P1 P2 Pm C1 C2 Cn2022/9/21計(jì)算機(jī)科學(xué)系生產(chǎn)者消費(fèi)者緩沖池共享N個(gè)緩沖區(qū)P1 P2 Pm 20 1. 利用記錄型信號(hào)量解決生產(chǎn)者消費(fèi)者問題 假定在生產(chǎn)者和消費(fèi)者之間的公用緩沖池中，具有n個(gè)緩沖區(qū)，這時(shí)可利用互斥信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用；同步：利用信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費(fèi)者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費(fèi)者便可從緩沖池

53、中取走一個(gè)消息。對(duì)生產(chǎn)者消費(fèi)者問題可描述如下： 2022/9/21計(jì)算機(jī)科學(xué)系 1. 利用記錄型信號(hào)量解決生產(chǎn)者消費(fèi)者問題Var mutex, empty, full:semaphore=1,n,0; buffer:array0, , n-1 of item; in, out: integer=0, 0; begin parbegin proceducer:begin repeat producer an item nextp; wait(empty); wait(mutex); buffer(in)=nextp; in=(in+1) mod n; signal(mutex); signal(

54、full); until false; end 2022/9/21計(jì)算機(jī)科學(xué)系Var mutex, empty, full:semaphoconsumer:begin repeat wait(full); wait(mutex); nextc =buffer(out); out =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end wait(empty)和wait(mutex)位置是否可以互換會(huì)？signal(full)和signal(mutex

55、)位置是否可以互換會(huì)？2022/9/21計(jì)算機(jī)科學(xué)系consumer:begin wait(empty)和wai 在生產(chǎn)者消費(fèi)者問題中應(yīng)注意：在每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn)； 對(duì)用于同步的資源信號(hào)量empty和full的wait和signal操作，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在計(jì)算進(jìn)程中，而signal(empty)則在打印進(jìn)程中，計(jì)算進(jìn)程若因執(zhí)行wait(empty)而阻塞， 則以后將由打印進(jìn)程將它喚醒；在每個(gè)程序中的多個(gè)wait操作順序不能顛倒。應(yīng)先執(zhí)行對(duì)資源信號(hào)量的wait操作，然

56、后再執(zhí)行對(duì)互斥信號(hào)量的wait操作，否則可能引起進(jìn)程死鎖。2022/9/21計(jì)算機(jī)科學(xué)系 在生產(chǎn)者消費(fèi)者問題中應(yīng)注意：2022/9/2. 利用AND信號(hào)量解決生產(chǎn)者消費(fèi)者問題 ar mutex, empty, full:semaphore =1, n, 0; buffer:array0, , n-1 of item; in out:integer =0, 0; begin parbegin producer:begin repeat produce an item in nextp; Swait(empty, mutex); buffer(in) =nextp; in =(in+1)mod n

57、; Ssignal(mutex, full); until false; end 2022/9/21計(jì)算機(jī)科學(xué)系2. 利用AND信號(hào)量解決生產(chǎn)者消費(fèi)者問題 ar muteconsumer:begin repeat Swait(full, mutex); nextc =buffer(out); out =(out+1) mod n; Ssignal(mutex, empty); consumer the item in nextc; until false; end parend end 如果緩沖區(qū)無限大，生產(chǎn)者-消費(fèi)者問題又該如何解決？2022/9/21計(jì)算機(jī)科學(xué)系consumer:begin

58、 如果緩沖區(qū)無限大，生產(chǎn)者-消費(fèi)3 利用管程解決生產(chǎn)者-消費(fèi)者問題 在利用管程方法來解決生產(chǎn)者-消費(fèi)者問題時(shí)， 首先便是為它們建立一個(gè)管程，并命名為Producer-Consumer, 或簡(jiǎn)稱為PC。其中包括兩個(gè)過程： 2022/9/21計(jì)算機(jī)科學(xué)系3 利用管程解決生產(chǎn)者-消費(fèi)者問題 在利用管 (1) put(item)過程。 生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中， 并用整型變量count來表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)countn時(shí)，表示緩沖池已滿，生產(chǎn)者須等待。 (2) get(item)過程。消費(fèi)者利用該過程從緩沖池中取出一個(gè)產(chǎn)品，當(dāng)count0時(shí)，表示緩沖池中已無可取用的產(chǎn)

59、品， 消費(fèi)者應(yīng)等待。 2022/9/21計(jì)算機(jī)科學(xué)系 (1) put(item)過程。 生產(chǎn)者利用該type producer-consumer=monitor Var in,out,count:integer; buffer:array0,n-1 of item; notfull, notempty:condition; procedure entry put(item) begin if countn then notfull.wait; buffer(in) =nextp; in =(in+1) mod n; count =count+1; if notempty.queue then

60、notempty.signal; end 2022/9/21計(jì)算機(jī)科學(xué)系type producer-consumer=monitor procedure entry get(item) begin if count0 then notempty.wait; nextc= buffer(out); out =(out+1) mod n; count =count-1; if notfull.quene then notfull.signal; end begin in := out := 0; count :=0; end 2022/9/21計(jì)算機(jī)科學(xué)系 procedure entry get(