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

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

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

3、Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結(jié)點稱為初始結(jié)點(Initial Node)，把沒有后繼的結(jié)點稱為終止結(jié)點(Final Node)。2022/9/21計算機科學系2.1.2 前趨圖 前趨圖(Preceden 每個結(jié)點還具有一個重量(Weight)，用于表示該結(jié)點所含有的程序量或結(jié)點的執(zhí)行時間。 圖 2-2 前趨圖 2022/9/21計算機科學系 每個結(jié)點還具有一個重量(Weight)，用于表對于圖 2-2(a)所示的前趨圖， 存在下述前趨關系： 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) 應當注意，前趨圖中必須不存在循環(huán)，但在圖2-2(b)中卻有著下述的前趨關系： S2S3, S3S2 2022/9/21計算機科學系對于圖 2-2(a)所示的前趨圖， 存在下述前趨關系： 2.1.3 程序的并發(fā)執(zhí)行及其特征 1. 程序的并發(fā)執(zhí)行 圖 2-3 并發(fā)執(zhí)行時的前趨圖 20

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

29、把輸入指針加1表示成 in=(in+1)mod n；輸出指針加1表示成out=(out+1) mod n。當(in+1) mod n=out時表示緩沖池滿；而in=out則表示緩沖池空。2022/9/21計算機科學系 我們可利用一個數(shù)組來表示上述的具有n個(0，1，此外，還引入了一個整型變量counter, 其初始值為0。每當生產(chǎn)者進程向緩沖池中投放一個產(chǎn)品后，使counter加1；反之，每當消費者進程從中取走一個產(chǎn)品時， 使counter減1。2022/9/21計算機科學系此外，還引入了一個整型變量counter, 其初始值為0。每生產(chǎ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)者和消費者進程的描述中，no-op是一條空操作指令，while condition do no-op語句表示重復的測試條件(condication)，重復測試應進行到該條件變?yōu)閒alse(假)，即到該條件不成立時為止。在生產(chǎn)者進程中使用一局部變量nextp，用于暫時存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費者進程中，則使用一個局部變量nextc,用于存放每次要消費的產(chǎn)品。 2022

31、/9/21計算機科學系生產(chǎn)者和消費者兩進程共享下面的變量：2022/9/19計算機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計算機科學系producer: repeat 2022/9/19計算機科 雖然上面的生產(chǎn)者程序和消費者程序，在分別看時都是正確的，而且兩者在順序執(zhí)行時其結(jié)果也會是正確的，但若并發(fā)執(zhí)行時，就會出現(xiàn)差錯，問題就在于這兩個進程共享變量counter。生產(chǎn)者對它做加1操作，消費者對它做減1操作，這兩個操作在用機器語言實現(xiàn)時， 常可用下面的形式描述：register 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計算機科學系 雖然上面的生產(chǎn)者程序和消費者程序，在分別看時 假設：counter的當前值是5。如果生產(chǎn)者進程先執(zhí)行左列的三條機器語言語句，然后消費者進程再執(zhí)行右列的三條語句， 則最后共享變量counter的值仍為5；反之，如果讓消費者進程先執(zhí)行右列的三條語句，然后再讓生產(chǎ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計算機科學系 假設：counter的當前值是5。如果生產(chǎn)者進3. 臨界區(qū)(critical section) 可把一個訪問臨界資源的循環(huán)進程描述如下： repeat critical section; remainder section; until false; entry sectionexit section2022/9/21計算機科學系3.

35、臨界區(qū)(critical section) 可把一個訪4. 同步機制應遵循的規(guī)則 空閑讓進。(2) 忙則等待。 (3) 有限等待。 (4) 讓權等待。 2022/9/21計算機科學系4. 同步機制應遵循的規(guī)則 空閑讓進。2022/9/19計算2.3.2 信號量機制 1. 整型信號量 最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標準的原子操作(Atomic Operation) wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為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計算機科學系2.3.2 信號量機制 1. 整型信號量 2. 記錄型信號量 在整型信號量機制中的wait操作，只要是信號量S0， 就會不斷地測試。因此，該機制并未遵循“讓權等待”的準則， 而是使進程處于“忙等”的狀態(tài)。記錄型信號量機制，則是一種不存在“忙等”現(xiàn)象的進程同步機制。但在采取了“讓權等待”的策略后，又會出現(xiàn)多個進程等待訪問同一臨界資源的情況。為此，在信號量機制中，除了需要一個用于代表資源數(shù)目的整型變量value外，還應增加一個進程鏈表L，用于鏈接上述的所有等待進程。記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)

37、構(gòu)而得名的。它所包含的上述兩個數(shù)據(jù)項可描述為： 2022/9/21計算機科學系 2. 記錄型信號量 2022/9/19計算type semaphore=record value:integer; L:list of process; end 相應地，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計算機科學系type semaphore=record 2022/9/1 在記錄型信號量機制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目， 因而又稱為資源信號量。對它的每次wait操作，意味著進程請求一個單位的該類資源，因此描述為S.value=S.value-1；當S.value0時，表示該類資源已分配完畢，因此進程應調(diào)用block原語，進行自我阻塞，放棄處理機，并插入到信號量鏈表S.L中。可見，該機制遵循了“讓權等待”準則。 此時S.value的絕對值表示在該信號量鏈表中已阻塞進程的數(shù)

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

40、wait(Emutex); wait(Emutex); wait(Dmutex); 若進程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計算機科學系3. AND型信號量 在兩個進程中都要包含兩個對Dmutex AND同步機制的基本思想是：將進程在整個運行過程中需要的所有資源，一次

41、性全部地分配給進程，待進程使用完后再一起釋放。只要尚有一個資源未能分配給進程，其它所有可能為之分配的資源，也不分配給他。亦即，對若干個臨界資源的分配，采取原子操作方式：要么全部分配到進程，要么一個也不分配。 由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個“AND”條件，故稱為AND同步，或稱為同時wait操作， 即Swait(Simultaneous wait)定義如下： 2022/9/21計算機科學系 AND同步機制的基本思想是：將進程在整個運行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計算機科學系Swait(S1, S2, , Sn) 2022/9/194. 信號量集 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計算機科學系4. 信號量集 Swait(S1, t1, d1, , S 一般“信號量集”的幾種特殊情況： (1) Swait(S, d, d)。 此時在信號量集中只有一個信號量S， 但允許它每次申請d個資源，當現(xiàn)有資源數(shù)少于d時

45、，不予分配。 (2) Swait(S, 1, 1)。 此時的信號量集已蛻化為一般的記錄型信號量(S1時)或互斥信號量(S=1時)。 (3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號量操作。當S1時，允許多個進程進入某特定區(qū)；當S變?yōu)?后，將阻止任何進程進入特定區(qū)。換言之，它相當于一個可控開關。 2022/9/21計算機科學系 一般“信號量集”的幾種特殊情況： 2022/2.3.3 信號量的應用 1. 利用信號量實現(xiàn)進程互斥 利用信號量實現(xià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計算機科學系2.3.3 信號量的應用 1. 利用信號量實現(xiàn)進程互斥 利用process 2: begin repeat wait(mutex); critical section signal(mutex); remainder section until false; end parend 2022/9/21計算機科學系process 2: begin 2022/9/19計算機科2. 利用信號量實現(xiàn)前趨

47、關系 圖 2-10 前趨圖舉例 2022/9/21計算機科學系2. 利用信號量實現(xià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計算機科學系 Var a,b,c,d,e,f,g; semaphore2.3.4 管 程 機 制 1. 管程的定義 管程由四部分組成： 局部于管程的共享變量說明； 對該數(shù)據(jù)結(jié)構(gòu)進行操作的一組過程； 對局部于管程的數(shù)據(jù)設置初始值的語句;還須為管程賦予一個名字2022/9/21計算機科學系2.3.4 管 程 機 制 1. 管程的定義 管程圖 2-11 管程的示意圖 2022/9/21計算機科學系圖 2-11 管程的示意圖 2022/9/19計算機科學系管程的

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計算機科學系管程的語法如下： 2022/9/19計算機科學系2. 條件變量 管程中對每個條件變量，都須予以說明，其形式為：Var x, y:condition。該變量應置于wait和signal之前，即可表示為X.

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

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

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

53、中取走一個消息。對生產(chǎn)者消費者問題可描述如下： 2022/9/21計算機科學系 1. 利用記錄型信號量解決生產(chǎn)者消費者問題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計算機科學系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)位置是否可以互換會？signal(full)和signal(mutex

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

56、后再執(zhí)行對互斥信號量的wait操作，否則可能引起進程死鎖。2022/9/21計算機科學系 在生產(chǎn)者消費者問題中應注意：2022/9/2. 利用AND信號量解決生產(chǎn)者消費者問題 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計算機科學系2. 利用AND信號量解決生產(chǎn)者消費者問題 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)者-消費者問題又該如何解決？2022/9/21計算機科學系consumer:begin

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

59、品， 消費者應等待。 2022/9/21計算機科學系 (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計算機科學系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計算機科學系 procedure entry get(