西安電子科技大學(xué)出版社操作系統(tǒng)第2章進(jìn)程管理.ppt

《西安電子科技大學(xué)出版社操作系統(tǒng)第2章進(jìn)程管理.ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《西安電子科技大學(xué)出版社操作系統(tǒng)第2章進(jìn)程管理.ppt（152頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

2019/12/1,計(jì)算機(jī)科學(xué)系,第二章 進(jìn)程管理,2.1 進(jìn)程的基本概念 2.2 進(jìn)程控制 2.3 進(jìn)程同步 2.4 經(jīng)典進(jìn)程的同步問(wèn)題 2.5 管程機(jī)制 2.6 進(jìn)程通信 2.7 線程,本章主要內(nèi)容,2019/12/1,計(jì)算機(jī)科學(xué)系,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é)果。,2019/12/1,計(jì)算機(jī)科學(xué)系,圖 2-1 程序的順序執(zhí)行,S1: a∶=x+y; S2: b∶=a-5; S3: c∶=b+1;,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 程序順序執(zhí)行時(shí)的特征,順序性： (2) 封閉性： (3) 可再現(xiàn)性：,2019/12/1,計(jì)算機(jī)科學(xué)系,2.1.2 前趨圖,前趨圖(Precedence Graph)是一個(gè)有向無(wú)循環(huán)圖，記為DAG(Directed Acyclic Graph)，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程，乃至一條語(yǔ)句；結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序(Partial Order)或前趨關(guān)系(Precedence Relation)“→”。 →={(Pi, Pj)|Pi must complete before Pj may start}, 如果(Pi, Pj)∈→,可寫成Pi→Pj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒(méi)有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(Initial Node)，把沒(méi)有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(Final Node)。,2019/12/1,計(jì)算機(jī)科學(xué)系,每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。,圖 2-2 前趨圖,2019/12/1,計(jì)算機(jī)科學(xué)系,對(duì)于圖 2-2(a)所示的前趨圖， 存在下述前趨關(guān)系：,P1→P2, P1→P3, P1→P4, P2→P5, P3→P5, P4→P6, P4→P7, P5→P8, P6→P8, P7→P9, P8→P9 或表示為： 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)系： S2→S3, S3→S2,2019/12/1,計(jì)算機(jī)科學(xué)系,2.1.3 程序的并發(fā)執(zhí)行及其特征,1. 程序的并發(fā)執(zhí)行,圖 2-3 并發(fā)執(zhí)行時(shí)的前趨圖,2019/12/1,計(jì)算機(jī)科學(xué)系,在該例中存在下述前趨關(guān)系： Ii→Ci，Ii→Ii+1, Ci→Pi, Ci→Ci+1，Pi→Pi+1 而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。,2019/12/1,計(jì)算機(jī)科學(xué)系,圖 2-4 四條語(yǔ)句的前趨關(guān)系,對(duì)于具有下述四條語(yǔ)句的程序段： S1: a∶=x+2 S2: b∶=y+4 S3: c∶=a+b S4: d∶=c+b,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 程序并發(fā)執(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。,2019/12/1,計(jì)算機(jī)科學(xué)系,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)度） 異步性,2019/12/1,計(jì)算機(jī)科學(xué)系,較典型的進(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)行的過(guò)程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位。 在引入了進(jìn)程實(shí)體的概念后，本書(shū)把傳統(tǒng)OS中的進(jìn)程定義為：“進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位”。,2019/12/1,計(jì)算機(jī)科學(xué)系,進(jìn)程與程序的區(qū)別： (1) 程序是指令的有序集合，其本身沒(méi)有任何運(yùn)行的含義，是一個(gè)靜態(tài)的概念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過(guò)程，它是一個(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)程的功能，而程序沒(méi)有 (6) 同一程序同時(shí)運(yùn)行于若干個(gè)數(shù)據(jù)集合上，它將屬于若干個(gè)不同的進(jìn)程。也就是說(shuō)同一程序可以對(duì)應(yīng)多個(gè)進(jìn)程,2019/12/1,計(jì)算機(jī)科學(xué)系,思考？,為什么引入進(jìn)程？,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 進(jìn)程的三種基本狀態(tài),(1)就緒(Ready)狀態(tài) (2)執(zhí)行狀態(tài) (3) 阻塞狀態(tài),2019/12/1,計(jì)算機(jī)科學(xué)系,圖 2-5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換,2019/12/1,計(jì)算機(jī)科學(xué)系,3. 掛起狀態(tài) 引入掛起狀態(tài)的原因： 終端用戶的請(qǐng)求； 父進(jìn)程請(qǐng)求； 負(fù)荷調(diào)節(jié)的需要； 操作系統(tǒng)的需要； 對(duì)換需要。 掛起狀態(tài)實(shí)際是暫時(shí)從內(nèi)存中被淘汰出去的進(jìn)程。,2019/12/1,計(jì)算機(jī)科學(xué)系,2) 進(jìn)程狀態(tài)的轉(zhuǎn)換,活動(dòng)就緒→靜止就緒。 (2) 活動(dòng)阻塞→靜止阻塞。 (3) 靜止就緒→活動(dòng)就緒。 (4) 靜止阻塞→活動(dòng)阻塞。,2019/12/1,計(jì)算機(jī)科學(xué)系,具有掛起狀態(tài)的進(jìn)程狀態(tài)圖,2019/12/1,計(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)作用,等待條件滿足,2019/12/1,計(jì)算機(jī)科學(xué)系,3．掛起狀態(tài)進(jìn)程模型（Ⅰ）,單掛起狀態(tài)進(jìn)程模型,2019/12/1,計(jì)算機(jī)科學(xué)系,3．掛起狀態(tài)進(jìn)程模型（Ⅱ）,雙掛起狀態(tài)進(jìn)程模型,2019/12/1,計(jì)算機(jī)科學(xué)系,思考？,1．如果系統(tǒng)中有N個(gè)進(jìn)程，運(yùn)行的進(jìn)程最多幾個(gè)，最少幾個(gè)；就緒進(jìn)程最多幾個(gè)最少幾個(gè)；等待進(jìn)程最多幾個(gè)，最少幾個(gè)？ 2. 有沒(méi)有這樣的狀態(tài)轉(zhuǎn)換，為什么？ 等待—運(yùn)行； 就緒—等待,2019/12/1,計(jì)算機(jī)科學(xué)系,課堂練習(xí),當(dāng)某個(gè)作業(yè)被作業(yè)調(diào)度程序選中，進(jìn)入內(nèi)存開(kāi)始運(yùn)行時(shí)，作業(yè)的狀態(tài)為： Ａ.提交狀態(tài) Ｂ.完成狀態(tài) Ｃ.執(zhí)行狀態(tài) Ｄ.就緒狀態(tài) 進(jìn)程在發(fā)出I/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è)備 A．I、II和III B. I、II和IV C. I、III和IV D. II、III和IV,2019/12/1,計(jì)算機(jī)科學(xué)系,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(shuō)，OS是根據(jù)PCB來(lái)對(duì)并發(fā)執(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來(lái)控制和管理進(jìn)程，所以PCB是系統(tǒng)感知進(jìn)程存在的唯一標(biāo)志。 進(jìn)程與PCB是一一對(duì)應(yīng)的。,2019/12/1,計(jì)算機(jī)科學(xué)系,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í)符主要是為了方便系統(tǒng)使用。 (2) 外部標(biāo)識(shí)符。它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶(進(jìn)程)在訪問(wè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)程的用戶。,2019/12/1,計(jì)算機(jī)科學(xué)系,2) 處理機(jī)狀態(tài) 處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。① 通用寄存器，又稱為用戶可視寄存器，它們是用戶程序可以訪問(wèn)的，用于暫存信息， 在大多數(shù)處理機(jī)中，有 8~32 個(gè)通用寄存器，在RISC結(jié)構(gòu)的計(jì)算機(jī)中可超過(guò) 100 個(gè)；② 指令計(jì)數(shù)器，其中存放了要訪問(wèn)的下一條指令的地址；③ 程序狀態(tài)字PSW，其中含有狀態(tài)信息，如條件碼、執(zhí)行方式、 中斷屏蔽標(biāo)志等； ④ 用戶棧指針， 指每個(gè)用戶進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧，用于存放過(guò)程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。,2019/12/1,計(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í)間總和、 進(jìn)程已執(zhí)行的時(shí)間總和等；④ 事件，是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。,2019/12/1,計(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ì)列中的下一個(gè)進(jìn)程的PCB的首地址。,2019/12/1,計(jì)算機(jī)科學(xué)系,3. 進(jìn)程控制塊的組織方式,1) 鏈接方式,PCB鏈接隊(duì)列示意圖,2019/12/1,計(jì)算機(jī)科學(xué)系,2) 索引方式,按索引方式組織PCB,,2019/12/1,計(jì)算機(jī)科學(xué)系,2.2 進(jìn) 程 控 制,進(jìn)程控制是進(jìn)程管理中最基本的功能。它用于創(chuàng)建一個(gè)新進(jìn)程，終止一個(gè)已完成的進(jìn)程，或終止一個(gè)因出現(xiàn)某事件而使其無(wú)法運(yùn)行下去的進(jìn)程，還可負(fù)責(zé)進(jìn)程運(yùn)行中的狀態(tài)轉(zhuǎn)換。進(jìn)程控制就是對(duì)系統(tǒng)中的所有進(jìn)程實(shí)施管理，進(jìn)程控制一般有原語(yǔ)來(lái)實(shí)現(xiàn)。 所謂原語(yǔ)是一種特殊的系統(tǒng)功能調(diào)用，它可以完成一個(gè)特定的功能，其特點(diǎn)是原語(yǔ)執(zhí)行時(shí)不可被中斷，其作用是為了實(shí)現(xiàn)進(jìn)程的通信和控制。 常用原語(yǔ)： 創(chuàng)建原語(yǔ) 終止原語(yǔ) 阻塞原語(yǔ)、喚醒原語(yǔ),2019/12/1,計(jì)算機(jī)科學(xué)系,2.2 進(jìn) 程 控 制,2.2.1 進(jìn)程的創(chuàng)建,1. 進(jìn)程圖(Process Graph),進(jìn)程樹(shù),2019/12/1,計(jì)算機(jī)科學(xué)系,2. 引起創(chuàng)建進(jìn)程的事件,用戶登錄。 (2) 作業(yè)調(diào)度。 (3) 提供服務(wù)。 （文件打?。?(4) 應(yīng)用請(qǐng)求。 （輸入，處理，打?。?,系統(tǒng)內(nèi)核,用戶自己,2019/12/1,計(jì)算機(jī)科學(xué)系,3. 進(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ì)列。,2019/12/1,計(jì)算機(jī)科學(xué)系,2.2.2 進(jìn)程的終止,1. 引起進(jìn)程終止(Termination of Process)的事件 1) 正常結(jié)束 在任何計(jì)算機(jī)系統(tǒng)中，都應(yīng)有一個(gè)用于表示進(jìn)程已經(jīng)運(yùn)行完成的指示。例如，在批處理系統(tǒng)中，通常在程序的最后安排一條Halt指令或終止的系統(tǒng)調(diào)用。當(dāng)程序運(yùn)行到Halt指令時(shí)，將產(chǎn)生一個(gè)中斷，去通知OS本進(jìn)程已經(jīng)完成。,2019/12/1,計(jì)算機(jī)科學(xué)系,2) 異常結(jié)束 在進(jìn)程運(yùn)行期間，由于出現(xiàn)某些錯(cuò)誤和故障而迫使進(jìn)程終止。這類異常事件很多，常見(jiàn)的有： 越界錯(cuò)誤 保護(hù)錯(cuò) 非法指令 特權(quán)指令錯(cuò) 運(yùn)行超時(shí) 等待超時(shí) 算術(shù)運(yùn)算錯(cuò) I/O故障,2019/12/1,計(jì)算機(jī)科學(xué)系,3) 外界干預(yù) 外界干預(yù)并非指在本進(jìn)程運(yùn)行中出現(xiàn)了異常事件，而是指進(jìn)程應(yīng)外界的請(qǐng)求而終止運(yùn)行。這些干預(yù)有： 操作員或操作系統(tǒng)干預(yù) 父進(jìn)程請(qǐng)求 父進(jìn)程終止,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 進(jìn)程的終止過(guò)程 (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ì)列(或鏈表)中移出， 等待其他程序來(lái)搜集信息。,2019/12/1,計(jì)算機(jī)科學(xué)系,2.2.3 進(jìn)程的阻塞與喚醒,1. 引起進(jìn)程阻塞和喚醒的事件,請(qǐng)求系統(tǒng)服務(wù) 啟動(dòng)某種操作 新數(shù)據(jù)尚未到達(dá) 無(wú)新工作可做,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 進(jìn)程阻塞過(guò)程 正在執(zhí)行的進(jìn)程，當(dāng)發(fā)現(xiàn)上述某事件時(shí)，由于無(wú)法繼續(xù)執(zhí)行，于是進(jìn)程便通過(guò)調(diào)用阻塞原語(yǔ)block把自己阻塞?？梢?jiàn)，進(jìn)程的阻塞是進(jìn)程自身的一種主動(dòng)行為。進(jìn)入block過(guò)程后，由于此時(shí)該進(jìn)程還處于執(zhí)行狀態(tài)，所以應(yīng)先立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞，并將PCB插入阻塞隊(duì)列。如果系統(tǒng)中設(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)境。,2019/12/1,計(jì)算機(jī)科學(xué)系,3. 進(jìn)程喚醒過(guò)程 當(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)用喚醒原語(yǔ)wakeup( )，將等待該事件的進(jìn)程喚醒。喚醒原語(yǔ)執(zhí)行的過(guò)程是：首先把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出，將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒，然后再將該P(yáng)CB插入到就緒隊(duì)列中。,2019/12/1,計(jì)算機(jī)科學(xué)系,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)將利用掛起原語(yǔ)suspend( )將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。掛起原語(yǔ)的執(zhí)行過(guò)程是：首先檢查被掛起進(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ū)域。最后，若被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度。,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 進(jìn)程的激活過(guò)程 當(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)將利用激活原語(yǔ)active( )將指定進(jìn)程激活。 激活原語(yǔ)先將進(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)行優(yōu)先級(jí)的比較，如果被激活進(jìn)程的優(yōu)先級(jí)更低，就不必重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運(yùn)行，把處理機(jī)分配給剛被激活的進(jìn)程。,,2019/12/1,計(jì)算機(jī)科學(xué)系,課堂練習(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和III C：僅I和III D：I，II，III,2019/12/1,計(jì)算機(jī)科學(xué)系,思考？,１．為什么創(chuàng)建進(jìn)程要用原語(yǔ)來(lái)實(shí)現(xiàn)？ 2 ．阻塞進(jìn)程在什么情況下會(huì)被喚醒？誰(shuí)來(lái)喚醒它？,2019/12/1,計(jì)算機(jī)科學(xué)系,2.3 進(jìn) 程 同 步,2.3.1 進(jìn)程同步的基本概念,1. 兩種形式的制約關(guān)系,間接相互制約關(guān)系。 (2) 直接相互制約關(guān)系。,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 臨界資源(Critical Resouce),生產(chǎn)者-消費(fèi)者(producer-consumer)問(wèn)題是一個(gè)著名的進(jìn)程同步問(wè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ū)中取走產(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)品。,2019/12/1,計(jì)算機(jī)科學(xué)系,我們可利用一個(gè)數(shù)組來(lái)表示上述的具有n個(gè)(0，1，…，n-1)緩沖區(qū)的緩沖池。 用輸入指針in來(lái)指示下一個(gè)可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個(gè)產(chǎn)品后，輸入指針加1； 用一個(gè)輸出指針out來(lái)指示下一個(gè)可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品后，輸出指針加1。 由于這里的緩沖池是組織成循環(huán)緩沖的，故應(yīng)把輸入指針加1表示成 in∶=(in+1)mod n；輸出指針加1表示成out∶=(out+1) mod n。 當(dāng)(in+1) mod n=out時(shí)表示緩沖池滿；而in=out則表示緩沖池空。,2019/12/1,計(jì)算機(jī)科學(xué)系,此外，還引入了一個(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。,2019/12/1,計(jì)算機(jī)科學(xué)系,生產(chǎn)者和消費(fèi)者兩進(jìn)程共享下面的變量： var n, integer; type item=…; var buffer:array［0, 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語(yǔ)句表示重復(fù)的測(cè)試條件(condication)，重復(fù)測(cè)試應(yīng)進(jìn)行到該條件變?yōu)閒alse(假)，即到該條件不成立時(shí)為止。在生產(chǎn)者進(jìn)程中使用一局部變量nextp，用于暫時(shí)存放每次剛生產(chǎn)出來(lái)的產(chǎn)品；而在消費(fèi)者進(jìn)程中，則使用一個(gè)局部變量nextc,用于存放每次要消費(fèi)的產(chǎn)品。,2019/12/1,計(jì)算機(jī)科學(xué)系,producer: repeat … produce an item in nextp; … while counter=n do no-op; buffer［in］:=nextp; in∶= in+1 mod n; counter: = counter+1; until false; consumer: repeat while counter=0 do no-op; nextc∶ =buffer［out］; out∶ =(out+1) mod n; counter∶ =counter-1; consumer the item in nextc; until false;,2019/12/1,計(jì)算機(jī)科學(xué)系,雖然上面的生產(chǎn)者程序和消費(fèi)者程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的，但若并發(fā)執(zhí)行時(shí)，就會(huì)出現(xiàn)差錯(cuò)，問(wèn)題就在于這兩個(gè)進(jìn)程共享變量counter。生產(chǎn)者對(duì)它做加1操作，消費(fèi)者對(duì)它做減1操作，這兩個(gè)操作在用機(jī)器語(yǔ)言實(shí)現(xiàn)時(shí)， ?？捎孟旅娴男问矫枋觯?register 1∶=counter; register1∶=register 1+1; counter∶=register 1; register 2∶=counter; register 2∶=register 2-1; counter∶=register 2;,2019/12/1,計(jì)算機(jī)科學(xué)系,假設(shè)：counter的當(dāng)前值是5。如果生產(chǎn)者進(jìn)程先執(zhí)行左列的三條機(jī)器語(yǔ)言語(yǔ)句，然后消費(fèi)者進(jìn)程再執(zhí)行右列的三條語(yǔ)句， 則最后共享變量counter的值仍為5；反之，如果讓消費(fèi)者進(jìn)程先執(zhí)行右列的三條語(yǔ)句，然后再讓生產(chǎn)者進(jìn)程執(zhí)行左列的三條語(yǔ)句，counter值也還是5，但是，如果按下述順序執(zhí)行： register1∶=counter; (register1=5) register1∶=register1+1; (register1=6) register2∶=counter; (register2=5) register2∶ =register2-1; (register2=4) counter∶=register1; (counter=6) counter∶=register2; (counter=4),2019/12/1,計(jì)算機(jī)科學(xué)系,3. 臨界區(qū)(critical section),可把一個(gè)訪問(wèn)臨界資源的循環(huán)進(jìn)程描述如下： repeat critical section; remainder section; until false;,entry section,exit section,2019/12/1,計(jì)算機(jī)科學(xué)系,4. 同步機(jī)制應(yīng)遵循的規(guī)則,空閑讓進(jìn)。 (2) 忙則等待。 (3) 有限等待。 (4) 讓權(quán)等待。,2019/12/1,計(jì)算機(jī)科學(xué)系,2.3.2 信號(hào)量機(jī)制,1. 整型信號(hào)量 最初由Dijkstra把整型信號(hào)量定義為一個(gè)整型量，除初始化外，僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作(Atomic Operation) wait(S)和signal(S)來(lái)訪問(wèn)。這兩個(gè)操作一直被分別稱為P、V操作。 wait和signal操作可描述為： wait(S): while S≤0 do no-op S∶=S-1; signal(S): S∶=S+1; (1) 原子操作 (2) 忙等待,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 記錄型信號(hào)量 在整型信號(hào)量機(jī)制中的wait操作，只要是信號(hào)量S≤0， 就會(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)程等待訪問(wèn)同一臨界資源的情況。為此，在信號(hào)量機(jī)制中，除了需要一個(gè)用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個(gè)進(jìn)程鏈表L，用于鏈接上述的所有等待進(jìn)程。記錄型信號(hào)量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。它所包含的上述兩個(gè)數(shù)據(jù)項(xiàng)可描述為：,2019/12/1,計(jì)算機(jī)科學(xué)系,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.value＜0 then block(S,L) end procedure signal(S) var S: semaphore; begin S.value∶ =S.value+1; if S.value≤0 then wakeup(S,L); end,2019/12/1,計(jì)算機(jī)科學(xué)系,在記錄型信號(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.value＜0時(shí)，表示該類資源已分配完畢，因此進(jìn)程應(yīng)調(diào)用block原語(yǔ)，進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號(hào)量鏈表S.L中。可見(jiàn)，該機(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。 此時(shí)S.value的絕對(duì)值表示在該信號(hào)量鏈表中已阻塞進(jìn)程的數(shù)目。 對(duì)信號(hào)量的每次signal操作，表示執(zhí)行進(jìn)程釋放一個(gè)單位資源，故S.value∶=S.value+1操作表示資源數(shù)目加1。若加1后仍是S.value≤0，則表示在該信號(hào)量鏈表中，仍有等待該資源的進(jìn)程被阻塞，故還應(yīng)調(diào)用wakeup原語(yǔ)，將S.L鏈表中的第一個(gè)等待進(jìn)程喚醒。 如果S.value的初值為1，表示只允許一個(gè)進(jìn)程訪問(wèn)臨界資源，此時(shí)的信號(hào)量轉(zhuǎn)化為互斥信號(hào)量。,2019/12/1,計(jì)算機(jī)科學(xué)系,3. AND型信號(hào)量,在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)Dmutex和Emutex的操作， 即 process A: process B: wait(Dmutex); 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阻塞,2019/12/1,計(jì)算機(jī)科學(xué)系,AND同步機(jī)制的基本思想是：將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。 由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)wait操作， 即Swait(Simultaneous wait)定義如下：,2019/12/1,計(jì)算機(jī)科學(xué)系,Swait(S1, S2, …, Sn) if Si≥1 and … and Sn≥1 then for i∶ =1 to n do Si∶=Si-1; endfor else place the process in the waiting queue associated with the first Si found with Si＜1, 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 with Si into the ready queue. endfor;,2019/12/1,計(jì)算機(jī)科學(xué)系,4. 信號(hào)量集,Swait(S1, t1, d1, …, Sn, tn, dn) if Si≥t1 and … and Sn≥tn 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 Si＜ti and set its program counter to the beginning 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;,2019/12/1,計(jì)算機(jī)科學(xué)系,一般“信號(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í)，不予分配。 (2) Swait(S, 1, 1)。 此時(shí)的信號(hào)量集已蛻化為一般的記錄型信號(hào)量(S＞1時(shí))或互斥信號(hào)量(S=1時(shí))。 (3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng)S≥1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開(kāi)關(guān)。,2019/12/1,計(jì)算機(jī)科學(xué)系,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 repeat wait(mutex); critical section signal(mutex); remainder seetion until false; end,2019/12/1,計(jì)算機(jī)科學(xué)系,process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系,圖 2-10 前趨圖舉例,2019/12/1,計(jì)算機(jī)科學(xué)系,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(g); end; begin wait(e); wait(f); wait(g); S6; end; parend end,2019/12/1,計(jì)算機(jī)科學(xué)系,2.3.4 管 程 機(jī) 制,1. 管程的定義,管程由四部分組成： 局部于管程的共享變量說(shuō)明； 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程； 對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句; 還須為管程賦予一個(gè)名字,2019/12/1,計(jì)算機(jī)科學(xué)系,圖 2-11 管程的示意圖,2019/12/1,計(jì)算機(jī)科學(xué)系,管程的語(yǔ)法如下： 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,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 條件變量,管程中對(duì)每個(gè)條件變量，都須予以說(shuō)明，其形式為：Var x, y:condition。該變量應(yīng)置于wait和signal之前，即可表示為X.wait和X.signal。例如，由于共享數(shù)據(jù)被占用而使調(diào)用進(jìn)程等待，該條件變量的形式為：nonbusy:condition。此時(shí)， wait原語(yǔ)應(yīng)改為nonbusy.wait，相應(yīng)地，signal應(yīng)改為nonbusy.signal。 應(yīng)當(dāng)指出，X.signal操作的作用，是重新啟動(dòng)一個(gè)被阻塞的進(jìn)程，但如果沒(méi)有被阻塞的進(jìn)程，則X.signal操作不產(chǎn)生任何后果。這與信號(hào)量機(jī)制中的signal操作不同。因?yàn)椋笳呖偸且獔?zhí)行s∶ =s+1操作，因而總會(huì)改變信號(hào)量的狀態(tài)。,2019/12/1,計(jì)算機(jī)科學(xué)系,2019/12/1,計(jì)算機(jī)科學(xué)系,如果有進(jìn)程Q處于阻塞狀態(tài)， 當(dāng)進(jìn)程P執(zhí)行了X.signal操作后，怎樣決定由哪個(gè)進(jìn)行執(zhí)行，哪個(gè)等待，可采用下述兩種方式之一進(jìn)行處理： (1) P等待，直至Q離開(kāi)管程或等待另一條件。 (2) Q等待，直至P離開(kāi)管程或等待另一條件。 采用哪種處理方式， 當(dāng)然是各執(zhí)一詞。 但是Hansan卻采用了第一種處理方式。,2019/12/1,計(jì)算機(jī)科學(xué)系,2.4 經(jīng)典進(jìn)程的同步問(wèn)題,2019/12/1,計(jì)算機(jī)科學(xué)系,,,,,,,,,,,生產(chǎn)者,,,,消費(fèi)者,緩沖池,共享N個(gè)緩沖區(qū),P1 P2 … Pm C1 C2 …Cn,2019/12/1,計(jì)算機(jī)科學(xué)系,1. 利用記錄型信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題 假定在生產(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)者便可從緩沖池中取走一個(gè)消息。對(duì)生產(chǎn)者—消費(fèi)者問(wèn)題可描述如下：,2019/12/1,計(jì)算機(jī)科學(xué)系,Var mutex, empty, full:semaphore∶=1,n,0; buffer:array［0, …, 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(full); until false; end,2019/12/1,計(jì)算機(jī)科學(xué)系,consumer: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)位置是否可以互換會(huì)？,2019/12/1,計(jì)算機(jī)科學(xué)系,在生產(chǎn)者—消費(fèi)者問(wèn)題中應(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操作，然后再執(zhí)行對(duì)互斥信號(hào)量的wait操作，否則可能引起進(jìn)程死鎖。,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 利用AND信號(hào)量解決生產(chǎn)者—消費(fèi)者問(wèn)題,ar mutex, empty, full:semaphore∶ =1, n, 0; buffer:array［0, …, 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; Ssignal(mutex, full); until false; end,2019/12/1,計(jì)算機(jī)科學(xué)系,consumer: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ū)無(wú)限大，生產(chǎn)者-消費(fèi)者問(wèn)題又該如何解決？,2019/12/1,計(jì)算機(jī)科學(xué)系,3 利用管程解決生產(chǎn)者-消費(fèi)者問(wèn)題,在利用管程方法來(lái)解決生產(chǎn)者-消費(fèi)者問(wèn)題時(shí)， 首先便是為它們建立一個(gè)管程，并命名為Producer-Consumer, 或簡(jiǎn)稱為PC。其中包括兩個(gè)過(guò)程：,2019/12/1,計(jì)算機(jī)科學(xué)系,(1) put(item)過(guò)程。 生產(chǎn)者利用該過(guò)程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中， 并用整型變量count來(lái)表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)count≥n時(shí)，表示緩沖池已滿，生產(chǎn)者須等待。 (2) get(item)過(guò)程。消費(fèi)者利用該過(guò)程從緩沖池中取出一個(gè)產(chǎn)品，當(dāng)count≤0時(shí)，表示緩沖池中已無(wú)可取用的產(chǎn)品， 消費(fèi)者應(yīng)等待。,2019/12/1,計(jì)算機(jī)科學(xué)系,type producer-consumer=monitor Var in,out,count:integer; buffer:array［0,…,n-1］ of item; notfull, notempty:condition; procedure entry put(item) begin if count≥n then notfull.wait; buffer(in)∶ =nextp; in∶ =(in+1) mod n; count∶ =count+1; if notempty.queue then notempty.signal; end,2019/12/1,計(jì)算機(jī)科學(xué)系,procedure entry get(item) begin if count≤0 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,2019/12/1,計(jì)算機(jī)科學(xué)系,在利用管程解決生產(chǎn)者-消費(fèi)者問(wèn)題時(shí)， 其中的生產(chǎn)者和消費(fèi)者可描述為：,producer:begin repeat produce an item in nextp; PC.put(item); until false; end consumer:begin repeat PC.get(item); consume the item in nextc; until false; end,2019/12/1,計(jì)算機(jī)科學(xué)系,2.4.2 哲學(xué)家進(jìn)餐問(wèn)題,4,1,計(jì)算機(jī)科學(xué)系,,,,,,,,,,,,,,,,,,,,哲學(xué)家,筷子,盤子,哲學(xué)家1號(hào),哲學(xué)家5號(hào),哲學(xué)家4號(hào),哲學(xué)家2號(hào),哲學(xué)家3號(hào),1,5,3,2,4,未就餐時(shí)示意圖,2019/12/1,計(jì)算機(jī)科學(xué)系,,,,,,,,,,,,,,,,哲學(xué)家1號(hào),哲學(xué)家4號(hào),哲學(xué)家2號(hào),哲學(xué)家3號(hào),1,5,3,2,4,,哲學(xué)家5號(hào),先拿左,拿到后再拿右,成功后進(jìn)餐.吃完后先放左再放右.雖可保證不會(huì)有相鄰的同時(shí)進(jìn)餐,但可能死鎖,如動(dòng)畫所示.,此時(shí)沒(méi)有一個(gè)哲學(xué)家可以完成進(jìn)餐.,2019/12/1,計(jì)算機(jī)科學(xué)系,,,,,,,,,,,,,,,,哲學(xué)家1號(hào),哲學(xué)家4號(hào),哲學(xué)家2號(hào),哲學(xué)家3號(hào),1,5,3,2,4,,哲學(xué)家5號(hào),此時(shí)5號(hào)哲學(xué)家被禁止拿筷子.1號(hào)哲學(xué)家拿起他右邊即5號(hào)哲學(xué)家左邊的筷子.,解決方法一:至多只允許四位哲學(xué)家同時(shí)去拿左邊的筷子,1號(hào)哲學(xué)家開(kāi)始進(jìn)餐,完成后放下筷子,其它哲學(xué)家開(kāi)始進(jìn)餐,2019/12/1,計(jì)算機(jī)科學(xué)系,,,,,,,,,,,,,,,,哲學(xué)家1號(hào),哲學(xué)家4號(hào),哲學(xué)家2號(hào),哲學(xué)家3號(hào),,哲學(xué)家5號(hào),解決方法二:僅當(dāng)哲學(xué)家左右兩邊筷子都能用才允許拿筷子,設(shè)1號(hào)進(jìn)餐,則 3,4兩位哲學(xué) 家可以拿筷子,1號(hào)進(jìn)餐完畢,放下筷子,先左后右.,1號(hào)放下左邊筷子的同時(shí),3號(hào)可拿起右邊筷子,3號(hào)開(kāi)始進(jìn)餐,同時(shí)1號(hào)放下右邊的筷子,此時(shí)4號(hào)條件不再滿足,放下筷子.,此時(shí)5號(hào)條件滿足,可在下一時(shí)鐘周期拿左筷子,2019/12/1,計(jì)算機(jī)科學(xué)系,,,,,,,,,,,,,,,,哲學(xué)家4號(hào),哲學(xué)家1號(hào),哲學(xué)家2號(hào),哲學(xué)家3號(hào),1,5,2,4,,哲學(xué)家5號(hào),解決方法三:奇數(shù)先拿左邊,偶數(shù)先拿右邊,這種方法將出現(xiàn)1,2號(hào)哲學(xué)家單鍵1號(hào)筷子,3,4號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子的情況.,而5號(hào)沒(méi)有人與他競(jìng)爭(zhēng),得到左邊的筷子,若4號(hào)在與3號(hào)的競(jìng)爭(zhēng)中得到筷子,則與5號(hào)競(jìng)爭(zhēng)4號(hào)筷子.,無(wú)論4號(hào)5號(hào)誰(shuí)得到4號(hào)筷子,都有一個(gè)可以進(jìn)餐,若4號(hào)在與3號(hào)的競(jìng)爭(zhēng)中沒(méi)有得到筷子,則5號(hào)得到4號(hào)筷子,進(jìn)餐,2019/12/1,計(jì)算機(jī)科學(xué)系,1. 利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問(wèn)題 經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時(shí)間內(nèi)只允許一位哲學(xué)家使用。為了實(shí)現(xiàn)對(duì)筷子的互斥使用，可以用一個(gè)信號(hào)量表示一只筷子，由這五個(gè)信號(hào)量構(gòu)成信號(hào)量數(shù)組。其描述如下： Var chopstick: array［0, …, 4］ of semaphore;,2019/12/1,計(jì)算機(jī)科學(xué)系,所有信號(hào)量均被初始化為1， 第i位哲學(xué)家的活動(dòng)可描述為： repeat wait(chopstick［i］); wait(chopstick［(i+1) mod 5］); … eat; … signal(chopstick［i］); signal(chopstick［(i+1) mod 5］); … think; until false;,,是否存在問(wèn)題？如何解決？,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題 在哲學(xué)家進(jìn)餐問(wèn)題中，要求每個(gè)哲學(xué)家先獲得兩個(gè)臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問(wèn)題，故用AND信號(hào)量機(jī)制可獲得最簡(jiǎn)潔的解法。 Var chopsiick array ［0, …, 4］ of semaphore∶=(1,1,1,1,1); processi repeat think; Sswait(chopstick［(i+1) mod 5］, chopstick ［i］); eat; Ssignat(chopstick［(i+1) mod 5］, chopstick ［i］); until false;,2019/12/1,計(jì)算機(jī)科學(xué)系,可采取以下幾種解決方法： (1) 至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時(shí)能釋放出他用過(guò)的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。 (2) 僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。 (3) 規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反。（自己思考如何用信號(hào)量解決）,2019/12/1,計(jì)算機(jī)科學(xué)系,2.4.3 讀者-寫者問(wèn)題,1. 利用記錄型信號(hào)量解決讀者-寫者問(wèn)題 為實(shí)現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r(shí)的互斥而設(shè)置了一個(gè)互斥信號(hào)量Wmutex。 另外，再設(shè)置一個(gè)整型變量Readcount表示正在讀的進(jìn)程數(shù)目。由于只要有一個(gè)Reader進(jìn)程在讀，便不允許Writer進(jìn)程去寫。 因此，僅當(dāng)Readcount=0, 表示尚無(wú)Reader進(jìn)程在讀時(shí)，Reader進(jìn)程才需要執(zhí)行Wait(Wmutex)操作。若wait(Wmutex)操作成功，Reader進(jìn)程便可去讀，相應(yīng)地，做Readcount+1操作。同理，僅當(dāng)Reader進(jìn)程在執(zhí)行了Readcount減1操作后其值為0時(shí)，才須執(zhí)行signal(Wmutex)操作，以便讓W(xué)riter進(jìn)程寫。又因?yàn)镽eadcount是一個(gè)可被多個(gè)Reader進(jìn)程訪問(wèn)的臨界資源，因此，應(yīng)該為它設(shè)置一個(gè)互斥信號(hào)量rmutex。,2019/12/1,計(jì)算機(jī)科學(xué)系,Var rmutex, wmutex:semaphore∶ =1,1; Readcount:integer∶ =0; begin parbegin Reader:begin repeat wait(rmutex); if readcount=0 then wait(wmutex); Readcount∶ =Readcount+1; signal(rmutex); perform read operation; wait(rmutex); readcount∶ =readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false; end,2019/12/1,計(jì)算機(jī)科學(xué)系,writer:begin repeat wait(wmutex); perform write operation; signal(wmutex); until false; end parend end,2019/12/1,計(jì)算機(jī)科學(xué)系,2. 利用信號(hào)量集機(jī)制解決讀者-寫者問(wèn)題,Var RN integer; L, mx:semaphore∶ =RN,1; begin parbegin reader:begin repeat Swait(L,1,1); Swait(mx,1,0); … perform read operation; …,2019/12/1,計(jì)算機(jī)科學(xué)系,Ssignal(L,1); until false; end writer:begin repeat Swait(mx,1,1; L,RN,0); perform write operation; Ssignal(mx,1); until false; end parend end,2019/12/1,計(jì)算機(jī)科學(xué)系,1.有三個(gè)進(jìn)程PA，PB，PC協(xié)作解決文件打印問(wèn)題：PA將文件記錄從磁盤讀入內(nèi)存的緩沖區(qū)1中，每執(zhí)行一次讀一個(gè)記錄；PB將緩沖區(qū)1中的內(nèi)容復(fù)制到緩沖區(qū)2中，每執(zhí)行一次復(fù)制一個(gè)記錄；PC將緩沖區(qū)2中的內(nèi)容打印出來(lái)，每執(zhí)行一次打印一個(gè)記錄。緩沖區(qū)的大小與記錄大小一樣。清用信號(hào)量來(lái)保證文件的正確打印。,經(jīng)典進(jìn)程同步問(wèn)題,2019/12/1,計(jì)算機(jī)科學(xué)系,2、有兩個(gè)生產(chǎn)者進(jìn)程A,B和一個(gè)消費(fèi)者進(jìn)程C，共享一個(gè)無(wú)限大倉(cāng)庫(kù)，可以存放A、B兩種產(chǎn)品，生產(chǎn)者每次生產(chǎn)一個(gè)產(chǎn)品放入倉(cāng)庫(kù)宮消費(fèi)者消費(fèi)，消費(fèi)者每次取一個(gè)產(chǎn)品消費(fèi)，要求： 每次只能存入一種產(chǎn)品（A或B）； A產(chǎn)品數(shù)量－B產(chǎn)品數(shù)量M； B產(chǎn)品數(shù)量－A產(chǎn)品數(shù)量N； 其中M、N是正整數(shù)，使用P、V操作描述A，B，C的工作流程。,2019/12/1,計(jì)算機(jī)科學(xué)系,3、一組生產(chǎn)者進(jìn)程和一組消費(fèi)者進(jìn)程共享10個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)可以存放一個(gè)整數(shù)；生產(chǎn)者進(jìn)程每次一次性向3個(gè)緩沖區(qū)寫入3個(gè)整數(shù)，消費(fèi)者進(jìn)程每次從緩沖區(qū)取出一個(gè)整數(shù)。用信號(hào)量實(shí)現(xiàn)進(jìn)程的同步關(guān)系。,2019/12/1,計(jì)算機(jī)科學(xué)系,4、桌子上有一個(gè)空盤子，允許存放一只水果，爸爸可以向盤中放蘋果，媽媽向盤子中放橘子，女兒專門吃盤子中的蘋果，兒子專門吃盤子中的橘子。規(guī)定當(dāng)盤子空的時(shí)