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

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

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