計算機(jī)操作系統(tǒng)課件

1、第二章 進(jìn) 程 管 理 第二章第二章 進(jìn)程管理進(jìn)程管理 2.1 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 2.2 2.2 進(jìn)程控制進(jìn)程控制 2.3 2.3 進(jìn)程同步進(jìn)程同步 2.4 2.4 經(jīng)典進(jìn)程的同步問題經(jīng)典進(jìn)程的同步問題 2.5 2.5 管程機(jī)制管程機(jī)制 2.6 2.6 進(jìn)程通信進(jìn)程通信 2.7 2.7 線程線程 第二章 進(jìn) 程 管 理 2.1 進(jìn)程的基本概念進(jìn)程的基本概念 2.1.1 程序的順序執(zhí)行及其特征程序的順序執(zhí)行及其特征 1. 程序的順序執(zhí)行程序的順序執(zhí)行 僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進(jìn)行計算時，總須先輸入用戶的程序和數(shù)據(jù)，然后進(jìn)行計算，最后才能打印計

2、算結(jié)果。 S1: a =x+y; S2: b =a-5; S3: c =b+1;第二章 進(jìn) 程 管 理 圖 2-1 程序的順序執(zhí)行 (a) 程序的順序執(zhí)行(b) 三條語句的順序執(zhí)行I1C1P1I2C2P2S1S2S3第二章 進(jìn) 程 管 理 2. 程序順序執(zhí)行時的特征程序順序執(zhí)行時的特征 順序性：(2) 封閉性： (3) 可再現(xiàn)性： 第二章 進(jìn) 程 管 理 2.1.2 前趨圖前趨圖 前趨圖(Precedence Graph)是一個有向無循環(huán)圖，記為DAG(Directed Acyclic Graph)，用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。圖中的每個結(jié)點可用于描述一個程序段或進(jìn)程，乃至一條語句；結(jié)點間

3、的有向邊則用于表示兩個結(jié)點之間存在的偏序(Partial Order)或前趨關(guān)系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可寫成PiPj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結(jié)點稱為初始結(jié)點(Initial Node)，把沒有后繼的結(jié)點稱為終止結(jié)點(Final Node)。第二章 進(jìn) 程 管 理 每個結(jié)點還具有一個重量(Weight)，用于表示該結(jié)點所含有的程序量或結(jié)點的執(zhí)行時間。 IiCiPi和S1S2S3 圖 2-2 前趨圖 P

4、1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九個結(jié)點的前趨圖(b) 具有循環(huán)的前趨圖第二章 進(jìn) 程 管 理 對于圖 2-2(a)所示的前趨圖， 存在下述前趨關(guān)系： P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, 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

5、, P9) 應(yīng)當(dāng)注意，前趨圖中必須不存在循環(huán)，但在圖2-2(b)中卻有著下述的前趨關(guān)系：S2S3, S3S2 第二章 進(jìn) 程 管 理 2.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征 1. 程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行 圖 2-3 并發(fā)執(zhí)行時的前趨圖 P1P2P3P4I1I2I3I4C1C2C3C4第二章 進(jìn) 程 管 理 在該例中存在下述前趨關(guān)系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。 對于具有下述四條語句的程序段： S1: a =x+2 S2: b =y+4 S3: c

6、 =a+b S4: d =c+b 第二章 進(jìn) 程 管 理 圖 2-4 四條語句的前趨關(guān)系S1S2S3S4第二章 進(jìn) 程 管 理 2. 程序并發(fā)執(zhí)行時的特征程序并發(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,

7、1。 (3) N =N+1在Print(N)和N =0之間，此時得到的N值分別為n, n+1, 0。 第二章 進(jìn) 程 管 理 2.1.4 進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài) 1. 進(jìn)程的特征和定義進(jìn)程的特征和定義 結(jié)構(gòu)特征2) 動態(tài)性 3) 并發(fā)性 4) 獨立性 5) 異步性 第二章 進(jìn) 程 管 理 較典型的進(jìn)程定義有： (1) 進(jìn)程是程序的一次執(zhí)行。 (2) 進(jìn)程是一個程序及其數(shù)據(jù)在處理機(jī)上順序執(zhí)行時所發(fā)生的活動。 (3) 進(jìn)程是程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位。 在引入了進(jìn)程實體的概念后，我們可以把傳統(tǒng)OS中的進(jìn)程定義為：“進(jìn)程是進(jìn)程實體的運行過程，是

8、系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位”。 第二章 進(jìn) 程 管 理 2. 進(jìn)程的三種基本狀態(tài)進(jìn)程的三種基本狀態(tài) 就緒(Ready)狀態(tài) 2) 執(zhí)行狀態(tài) 3) 阻塞狀態(tài) 第二章 進(jìn) 程 管 理 圖 2-5 進(jìn)程的三種基本狀態(tài)及其轉(zhuǎn)換 就緒阻塞執(zhí)行時間片完進(jìn)程調(diào)度I/O完成I/O請求第二章 進(jìn) 程 管 理 3. 掛起狀態(tài)掛起狀態(tài)引入掛起狀態(tài)的原因引入掛起狀態(tài)的原因 終端用戶的請求。 (2) 父進(jìn)程請求。 (3) 負(fù)荷調(diào)節(jié)的需要。 (4) 操作系統(tǒng)的需要。 第二章 進(jìn) 程 管 理 2) 進(jìn)程狀態(tài)的轉(zhuǎn)換 活動就緒靜止就緒。 (2) 活動阻塞靜止阻塞。 (3) 靜止就緒活動就緒。 (4) 靜止阻塞活動阻塞

9、。 第二章 進(jìn) 程 管 理 圖 2-6 具有掛起狀態(tài)的進(jìn)程狀態(tài)圖 活動就緒靜止就緒執(zhí)行掛起激活釋放掛起活動阻塞靜止阻塞掛起激活釋放請求I/O第二章 進(jìn) 程 管 理 2.1.5 進(jìn)程控制塊進(jìn)程控制塊 1. 進(jìn)程控制塊的作用進(jìn)程控制塊的作用 進(jìn)程控制塊的作用是使一個在多道程序環(huán)境下不能獨立運行的程序(含數(shù)據(jù))，成為一個能獨立運行的基本單位，一個能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f，OS是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。第二章 進(jìn) 程 管 理 2. 進(jìn)程控制塊中的信息進(jìn)程控制塊中的信息 1) 進(jìn)程標(biāo)識符 進(jìn)程標(biāo)識符用于惟一地標(biāo)識一個進(jìn)程。一個進(jìn)程通常有兩種標(biāo)識符： (1) 內(nèi)部標(biāo)識符。在

10、所有的操作系統(tǒng)中，都為每一個進(jìn) 程賦予一個惟一的數(shù)字標(biāo)識符，它通常是一個進(jìn)程的序號。 設(shè)置內(nèi)部標(biāo)識符主要是為了方便系統(tǒng)使用。 (2) 外部標(biāo)識符。它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶(進(jìn)程)在訪問該進(jìn)程時使用。為了描述進(jìn)程的家族關(guān)系， 還應(yīng)設(shè)置父進(jìn)程標(biāo)識及子進(jìn)程標(biāo)識。此外，還可設(shè)置用戶標(biāo)識，以指示擁有該進(jìn)程的用戶。 第二章 進(jìn) 程 管 理 2) 處理機(jī)狀態(tài) 處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。 通用寄存器，又稱為用戶可視寄存器，它們是用戶程序可以訪問的，用于暫存信息， 在大多數(shù)處理機(jī)中，有 832 個通用寄存器，在RISC結(jié)構(gòu)的計算機(jī)中可超過 100 個；

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

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

13、3. 進(jìn)程控制塊的組織方式進(jìn)程控制塊的組織方式 1) 鏈接方式 圖 2-7 PCB鏈接隊列示意圖 PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901執(zhí)行指針就緒隊列指針阻塞隊列指針空閑隊列指針第二章 進(jìn) 程 管 理 2) 索引方式 圖 2-8 按索引方式組織PCB 執(zhí)行指針就緒索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就緒表指針阻塞表指針第二章 進(jìn) 程 管 理 2.2 進(jìn)進(jìn) 程程 控控 制制 2.2.1 進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建 1. 進(jìn)程圖(Process Graph) 圖 2-9 進(jìn)程樹 DEFGHBCIJKLMA第二章 進(jìn)

14、程 管 理 2. 引起創(chuàng)建進(jìn)程的事件引起創(chuàng)建進(jìn)程的事件 用戶登錄。 (2) 作業(yè)調(diào)度。 (3) 提供服務(wù)。 (4) 應(yīng)用請求。 第二章 進(jìn) 程 管 理 3. 進(jìn)程的創(chuàng)建進(jìn)程的創(chuàng)建(Creation of Progress) (1)申請空白PCB。 (2) 為新進(jìn)程分配資源。 (3) 初始化進(jìn)程控制塊。 (4) 將新進(jìn)程插入就緒隊列，如果進(jìn)程就緒隊列能夠接納新進(jìn)程， 便將新進(jìn)程插入就緒隊列。 第二章 進(jìn) 程 管 理 2.2.2 進(jìn)程的終止進(jìn)程的終止 1. 引起進(jìn)程終止引起進(jìn)程終止(Termination of Process)的事件的事件 1) 正常結(jié)束 在任何計算機(jī)系統(tǒng)中，都應(yīng)有一個用于表示進(jìn)

15、程已經(jīng)運行完成的指示。例如，在批處理系統(tǒng)中，通常在程序的最后安排一條Holt指令或終止的系統(tǒng)調(diào)用。當(dāng)程序運行到Holt指令時，將產(chǎn)生一個中斷，去通知OS本進(jìn)程已經(jīng)完成。 在分時系統(tǒng)中，用戶可利用Logs off去表示進(jìn)程運行完畢， 此時同樣可產(chǎn)生一個中斷，去通知OS進(jìn)程已運行完畢。 第二章 進(jìn) 程 管 理 2) 異常結(jié)束 在進(jìn)程運行期間，由于出現(xiàn)某些錯誤和故障而迫使進(jìn)程終止。這類異常事件很多，常見的有： 越界錯誤。這是指程序所訪問的存儲區(qū)，已越出該進(jìn)程的區(qū)域； 保護(hù)錯。進(jìn)程試圖去訪問一個不允許訪問的資源或文件，或者以不適當(dāng)?shù)姆绞竭M(jìn)行訪問，例如，進(jìn)程試圖去寫一個只讀文件； 非法指令。程序試圖去執(zhí)

16、行一條不存在的指令。出現(xiàn)該錯誤的原因，可能是程序錯誤地轉(zhuǎn)移到數(shù)據(jù)區(qū)，把數(shù)據(jù)當(dāng)成了指令； 特權(quán)指令錯。用戶進(jìn)程試圖去執(zhí)行一條只允許OS執(zhí)行的指令； 運行超時。進(jìn)程的執(zhí)行時間超過了指定的最大值； 等待超時。進(jìn)程等待某事件的時間， 超過了規(guī)定的最大值； 算術(shù)運算錯。進(jìn)程試圖去執(zhí)行一個被禁止的運算，例如，被0除； I/O故障。這是指在I/O過程中發(fā)生了錯誤等。 第二章 進(jìn) 程 管 理 3) 外界干預(yù) 外界干預(yù)并非指在本進(jìn)程運行中出現(xiàn)了異常事件，而是指進(jìn)程應(yīng)外界的請求而終止運行。這些干預(yù)有： 操作員或操作系統(tǒng)干預(yù)。 由于某種原因，例如，發(fā)生了死鎖， 由操作員或操作系統(tǒng)終止該進(jìn)程； 父進(jìn)程請求。 由于父進(jìn)

17、程具有終止自己的任何子孫進(jìn)程的權(quán)利， 因而當(dāng)父進(jìn)程提出請求時，系統(tǒng)將終止該進(jìn)程； 父進(jìn)程終止。 當(dāng)父進(jìn)程終止時，OS也將他的所有子孫進(jìn)程終止。 第二章 進(jìn) 程 管 理 2. 進(jìn)程的終止過程進(jìn)程的終止過程 (1) 根據(jù)被終止進(jìn)程的標(biāo)識符，從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)程

18、(它的PCB)從所在隊列(或鏈表)中移出， 等待其他程序來搜集信息。 第二章 進(jìn) 程 管 理 2.2.3 進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒1. 引起進(jìn)程阻塞和喚醒的事件引起進(jìn)程阻塞和喚醒的事件 請求系統(tǒng)服務(wù) 2) 啟動某種操作 3) 新數(shù)據(jù)尚未到達(dá) 4) 無新工作可做 第二章 進(jìn) 程 管 理 2. 進(jìn)程阻塞過程進(jìn)程阻塞過程 正在執(zhí)行的進(jìn)程，當(dāng)發(fā)現(xiàn)上述某事件時，由于無法繼續(xù)執(zhí)行，于是進(jìn)程便通過調(diào)用阻塞原語block把自己阻塞?？梢?，進(jìn)程的阻塞是進(jìn)程自身的一種主動行為。進(jìn)入block過程后，由于此時該進(jìn)程還處于執(zhí)行狀態(tài)，所以應(yīng)先立即停止執(zhí)行，把進(jìn)程控制塊中的現(xiàn)行狀態(tài)由“執(zhí)行”改為阻塞，并將PCB插

19、入阻塞隊列。如果系統(tǒng)中設(shè)置了因不同事件而阻塞的多個阻塞隊列，則應(yīng)將本進(jìn)程插入到具有相同事件的阻塞(等待)隊列。 最后，轉(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)境。 第二章 進(jìn) 程 管 理 3. 進(jìn)程喚醒過程進(jìn)程喚醒過程 當(dāng)被阻塞進(jìn)程所期待的事件出現(xiàn)時，如I/O完成或其所期待的數(shù)據(jù)已經(jīng)到達(dá)，則由有關(guān)進(jìn)程(比如，用完并釋放了該I/O設(shè)備的進(jìn)程)調(diào)用喚醒原語wakeup( )，將等待該事件的進(jìn)程喚醒。喚醒原語執(zhí)行的過程是：首先把被阻塞的進(jìn)程從等待該事件的阻塞隊列中移出，將其PCB中的

20、現(xiàn)行狀態(tài)由阻塞改為就緒，然后再將該PCB插入到就緒隊列中。 第二章 進(jìn) 程 管 理 2.2.4 進(jìn)程的掛起與激活進(jìn)程的掛起與激活 1. 進(jìn)程的掛起進(jìn)程的掛起 當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時，比如，用戶進(jìn)程請求將自己掛起，或父進(jìn)程請求將自己的某個子進(jìn)程掛起， 系統(tǒng)將利用掛起原語suspend( )將指定進(jìn)程或處于阻塞狀態(tài)的進(jìn)程掛起。掛起原語的執(zhí)行過程是：首先檢查被掛起進(jìn)程的狀態(tài)，若處于活動就緒狀態(tài)，便將其改為靜止就緒；對于活動阻塞狀態(tài)的進(jìn)程，則將之改為靜止阻塞。 為了方便用戶或父進(jìn)程考查該進(jìn)程的運行情況而把該進(jìn)程的PCB復(fù)制到某指定的內(nèi)存區(qū)域。最后，若被掛起的進(jìn)程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度。

21、 第二章 進(jìn) 程 管 理 2. 進(jìn)程的激活過程進(jìn)程的激活過程 當(dāng)發(fā)生激活進(jìn)程的事件時，例如，父進(jìn)程或用戶進(jìn)程請求激活指定進(jìn)程，若該進(jìn)程駐留在外存而內(nèi)存中已有足夠的空間時，則可將在外存上處于靜止就緒狀態(tài)的進(jìn)程換入內(nèi)存。這時，系統(tǒng)將利用激活原語active( )將指定進(jìn)程激活。 激活原語先將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)，若是靜止就緒，便將之改為活動就緒；若為靜止阻塞便將之改為活動阻塞。假如采用的是搶占調(diào)度策略，則每當(dāng)有新進(jìn)程進(jìn)入就緒隊列時，應(yīng)檢查是否要進(jìn)行重新調(diào)度，即由調(diào)度程序?qū)⒈患せ钸M(jìn)程與當(dāng)前進(jìn)程進(jìn)行優(yōu)先級的比較，如果被激活進(jìn)程的優(yōu)先級更低，就不必重新調(diào)度；否則，立即剝奪當(dāng)前進(jìn)程的運

22、行，把處理機(jī)分配給剛被激活的進(jìn)程。 第二章 進(jìn) 程 管 理 2.3 進(jìn)進(jìn) 程程 同同 步步 2.3.1 進(jìn)程同步的基本概念進(jìn)程同步的基本概念 1. 兩種形式的制約關(guān)系兩種形式的制約關(guān)系 間接相互制約關(guān)系。 (2) 直接相互制約關(guān)系。 第二章 進(jìn) 程 管 理 2. 臨界資源臨界資源(Critical Resouce) 生產(chǎn)者-消費者(producer-consumer)問題是一個著名的進(jìn)程同步問題。它描述的是：有一群生產(chǎn)者進(jìn)程在生產(chǎn)產(chǎn)品，并將這些產(chǎn)品提供給消費者進(jìn)程去消費。為使生產(chǎn)者進(jìn)程與消費者進(jìn)程能并發(fā)執(zhí)行，在兩者之間設(shè)置了一個具有n個緩沖區(qū)的緩沖池，生產(chǎn)者進(jìn)程將它所生產(chǎn)的產(chǎn)品放入一個緩沖區(qū)中

23、； 消費者進(jìn)程可從一個緩沖區(qū)中取走產(chǎn)品去消費。盡管所有的生產(chǎn)者進(jìn)程和消費者進(jìn)程都是以異步方式運行的，但它們之間必須保持同步，即不允許消費者進(jìn)程到一個空緩沖區(qū)去取產(chǎn)品；也不允許生產(chǎn)者進(jìn)程向一個已裝滿產(chǎn)品且尚未被取走的緩沖區(qū)中投放產(chǎn)品。 第二章 進(jìn) 程 管 理 我們可利用一個數(shù)組來表示上述的具有n個(0，1，n-1)緩沖區(qū)的緩沖池。用輸入指針in來指示下一個可投放產(chǎn)品的緩沖區(qū)，每當(dāng)生產(chǎn)者進(jìn)程生產(chǎn)并投放一個產(chǎn)品后，輸入指針加1；用一個輸出指針out來指示下一個可從中獲取產(chǎn)品的緩沖區(qū)，每當(dāng)消費者進(jìn)程取走一個產(chǎn)品后，輸出指針加1。 由于這里的緩沖池是組織成循環(huán)緩沖的，故應(yīng)把輸入指針加1表示成 in =(

24、in+1)mod n；輸出指針加1表示成out =(out+1) mod n。當(dāng)(in+1) mod n=out時表示緩沖池滿；而in=out則表示緩沖池空。此外，還引入了一個整型變量counter, 其初始值為0。每當(dāng)生產(chǎn)者進(jìn)程向緩沖池中投放一個產(chǎn)品后，使counter加1；反之，每當(dāng)消費者進(jìn)程從中取走一個產(chǎn)品時， 使counter減1。生產(chǎn)者和消費者兩進(jìn)程共享下面的變量： 第二章 進(jìn) 程 管 理 Var n, integer;type item=;var buffer:array0, 1, , n-1 of item;in, out: 0, 1, , n-1;counter: 0, 1,

25、, n; 指針in和out初始化為1。在生產(chǎn)者和消費者進(jìn)程的描述中，no-op是一條空操作指令，while condition do no-op語句表示重復(fù)的測試條件(condication)，重復(fù)測試應(yīng)進(jìn)行到該條件變?yōu)閒alse(假)，即到該條件不成立時為止。在生產(chǎn)者進(jìn)程中使用一局部變量nextp，用于暫時存放每次剛生產(chǎn)出來的產(chǎn)品；而在消費者進(jìn)程中，則使用一個局部變量nextc,用于存放每次要消費的產(chǎn)品。 第二章 進(jìn) 程 管 理 producer: repeat produce an item in nextp; while counter=n do no-op; bufferin =nex

26、tp; 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 nextc; until false; 第二章 進(jìn) 程 管 理 雖然上面的生產(chǎn)者程序和消費者程序，在分別看時都是正確的，而且兩者在順序執(zhí)行時其結(jié)果也會是正確的，但若并發(fā)執(zhí)行時，就會出現(xiàn)差錯，問題就在于這兩個進(jìn)程共享變量counter。生產(chǎn)者對它做加1操

27、作，消費者對它做減1操作，這兩個操作在用機(jī)器語言實現(xiàn)時， ?？捎孟旅娴男问矫枋觯?register 1 =counter; register 2 =counter; register1 =register 1+1; register 2 =register 2-1; counter =register 1; counter =register 2; 第二章 進(jìn) 程 管 理 假設(shè)：counter的當(dāng)前值是5。如果生產(chǎn)者進(jìn)程先執(zhí)行左列的三條機(jī)器語言語句，然后消費者進(jìn)程再執(zhí)行右列的三條語句， 則最后共享變量counter的值仍為5；反之，如果讓消費者進(jìn)程先執(zhí)行右列的三條語句，然后再讓生產(chǎn)者進(jìn)程執(zhí)行左

28、列的三條語句，counter值也還是5，但是，如果按下述順序執(zhí)行： register 1 =counter; (register 1=5) register 1 =register 1+1; (register 1=6) register 2 =counter; (register 2=5) register 2 =register 2-1; (register 2=4) counter =register 1; (counter=6) counter =register 2; (counter=4) 第二章 進(jìn) 程 管 理 3. 臨界區(qū)臨界區(qū)(critical section) 可把一個訪問

29、臨界資源的循環(huán)進(jìn)程描述如下：repeat critical section; remainder section;until false; entry sectionexit section第二章 進(jìn) 程 管 理 4. 同步機(jī)制應(yīng)遵循的規(guī)則同步機(jī)制應(yīng)遵循的規(guī)則 空閑讓進(jìn)。(2) 忙則等待。 (3) 有限等待。 (4) 讓權(quán)等待。 第二章 進(jìn) 程 管 理 2.3.2 信號量機(jī)制信號量機(jī)制 1. 整型信號量整型信號量 最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標(biāo)準(zhǔn)的原子操作(Atomic Operation) wait(S)和signal(S)來訪問。這兩個操作一

30、直被分別稱為P、V操作。 wait和signal操作可描述為： wait(S): while S0 do no-op S =S-1; signal(S): S =S+1; 第二章 進(jìn) 程 管 理 2. 記錄型信號量記錄型信號量 在整型信號量機(jī)制中的wait操作，只要是信號量S0， 就會不斷地測試。因此，該機(jī)制并未遵循“讓權(quán)等待”的準(zhǔn)則， 而是使進(jìn)程處于“忙等”的狀態(tài)。記錄型信號量機(jī)制，則是一種不存在“忙等”現(xiàn)象的進(jìn)程同步機(jī)制。但在采取了“讓權(quán)等待”的策略后，又會出現(xiàn)多個進(jìn)程等待訪問同一臨界資源的情況。為此，在信號量機(jī)制中，除了需要一個用于代表資源數(shù)目的整型變量value外，還應(yīng)增加一個進(jìn)程鏈表

31、L，用于鏈接上述的所有等待進(jìn)程。記錄型信號量是由于它采用了記錄型的數(shù)據(jù)結(jié)構(gòu)而得名的。它所包含的上述兩個數(shù)據(jù)項可描述為： 第二章 進(jìn) 程 管 理 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.v

32、alue =S.value+1; if S.value0 then wakeup(S,L); end 第二章 進(jìn) 程 管 理 在記錄型信號量機(jī)制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目， 因而又稱為資源信號量，對它的每次wait操作，意味著進(jìn)程請求一個單位的該類資源，因此描述為S.value =S.value-1； 當(dāng)S.value0時，表示該類資源已分配完畢，因此進(jìn)程應(yīng)調(diào)用block原語，進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號量鏈表S.L中。可見，該機(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。 此時S.value的絕對值表示在該信號量鏈表中已阻塞進(jìn)程的數(shù)目。 對信號量的每次signal操作，表示執(zhí)行

33、進(jìn)程釋放一個單位資源，故S.value =S.value+1操作表示資源數(shù)目加1。 若加1后仍是S.value0，則表示在該信號量鏈表中，仍有等待該資源的進(jìn)程被阻塞，故還應(yīng)調(diào)用wakeup原語，將S.L鏈表中的第一個等待進(jìn)程喚醒。如果S.value的初值為1，表示只允許一個進(jìn)程訪問臨界資源，此時的信號量轉(zhuǎn)化為互斥信號量。 第二章 進(jìn) 程 管 理 3. AND型信號量型信號量 在兩個進(jìn)程中都要包含兩個對Dmutex和Emutex的操作， 即process A: process B:wait(Dmutex); wait(Emutex);wait(Emutex); wait(Dmutex);若進(jìn)程A

34、和B按下述次序交替執(zhí)行wait操作：process A: wait(Dmutex); 于是Dmutex=0process B: wait(Emutex); 于是Emutex=0process A: wait(Emutex); 于是Emutex=-1 A阻塞process B: wait(Dmutex); 于是Dmutex=-1 B阻塞 第二章 進(jìn) 程 管 理 AND同步機(jī)制的基本思想是：將進(jìn)程在整個運行過程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對若干個臨界資源的分配，采取原子操作方式：

35、要么全部分配到進(jìn)程，要么一個也不分配。 由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個“AND”條件，故稱為AND同步，或稱為同時wait操作， 即Swait(Simultaneous wait)定義如下： 第二章 進(jìn) 程 管 理 Swait(S1, S2, , Sn) if Si1 and and Sn1 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 Si1,

36、 and set the program count of this process to the beginning of Swait operation endifSsignal(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; 第二章 進(jìn) 程 管 理 4. 信號量集信號量集 Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Snt

37、n 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 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 associa

38、ted with Si into the ready queue endfor; 第二章 進(jìn) 程 管 理 一般“信號量集”的幾種特殊情況： (1) Swait(S, d, d)。 此時在信號量集中只有一個信號量S， 但允許它每次申請d個資源，當(dāng)現(xiàn)有資源數(shù)少于d時，不予分配。 (2) Swait(S, 1, 1)。 此時的信號量集已蛻化為一般的記錄型信號量(S1時)或互斥信號量(S=1時)。 (3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號量操作。當(dāng)S1時，允許多個進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個可控開關(guān)。 第二章 進(jìn) 程 管 理

39、2.3.3 信號量的應(yīng)用信號量的應(yīng)用 1. 利用信號量實現(xiàn)進(jìn)程互斥利用信號量實現(xiàn)進(jìn)程互斥 利用信號量實現(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; 第二章 進(jìn) 程 管 理 end process 2: begin repeat wait(mutex); critical section signal(mutex); remainder s

40、ection until false; end parend 第二章 進(jìn) 程 管 理 2. 利用信號量實現(xiàn)前趨關(guān)系利用信號量實現(xiàn)前趨關(guān)系 圖 2-10 前趨圖舉例 S4S5S3S1S6S2第二章 進(jìn) 程 管 理 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); S

41、4; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; parend end 第二章 進(jìn) 程 管 理 2.4 經(jīng)典進(jìn)程的同步問題經(jīng)典進(jìn)程的同步問題 2.4.1 生產(chǎn)者生產(chǎn)者消費者問題消費者問題 前面我們已經(jīng)對生產(chǎn)者消費者問題(The proceducer-consumer problem)做了一些描述，但未考慮進(jìn)程的互斥與同步問題，因而造成了數(shù)據(jù)Counter的不定性。由于生產(chǎn)者消費者問題是相互合作的進(jìn)程關(guān)系的一種抽象，例如， 在輸入時，輸入進(jìn)程是生產(chǎn)者，計算

42、進(jìn)程是消費者；而在輸出時，則計算進(jìn)程是生產(chǎn)者，而打印進(jìn)程是消費者， 因此，該問題有很大的代表性及實用價值。 第二章 進(jìn) 程 管 理 1. 利用記錄型信號量解決生產(chǎn)者利用記錄型信號量解決生產(chǎn)者消費者問題消費者問題 假定在生產(chǎn)者和消費者之間的公用緩沖池中，具有n個緩沖區(qū)，這時可利用互斥信號量mutex實現(xiàn)諸進(jìn)程對緩沖池的互斥使用；利用信號量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。又假定這些生產(chǎn)者和消費者相互等效，只要緩沖池未滿，生產(chǎn)者便可將消息送入緩沖池；只要緩沖池未空，消費者便可從緩沖池中取走一個消息。對生產(chǎn)者消費者問題可描述如下： 第二章 進(jìn) 程 管 理 Var mute

43、x, 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(full); until false; end 第二章 進(jìn) 程 管 理 consumer:begin repeat wait(fu

44、ll); wait(mutex); nextc =buffer(out); out =(out+1) mod n; signal(mutex); signal(empty); consumer the item in nextc; until false; end parend end 第二章 進(jìn) 程 管 理 在生產(chǎn)者消費者問題中應(yīng)注意：首先，在每個程序中用于實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對地出現(xiàn)； 其次，對資源信號量empty和full的wait和signal操作，同樣需要成對地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在計算進(jìn)程中，而

45、signal(empty)則在打印進(jìn)程中，計算進(jìn)程若因執(zhí)行wait(empty)而阻塞， 則以后將由打印進(jìn)程將它喚醒；最后，在每個程序中的多個wait操作順序不能顛倒。應(yīng)先執(zhí)行對資源信號量的wait操作，然后再執(zhí)行對互斥信號量的wait操作，否則可能引起進(jìn)程死鎖。第二章 進(jìn) 程 管 理 2. 利用利用AND信號量解決生產(chǎn)者信號量解決生產(chǎn)者消費者問題消費者問題 ar mutex, empty, full:semaphore =1, n, 0; buffer:array0, , n-1 of item; in out:integer =0, 0; begin parbegin producer:b

46、egin repeat produce an item in nextp; Swait(empty, mutex); buffer(in) =nextp; in =(in+1)mod n; Ssignal(mutex, full); until false; end 第二章 進(jìn) 程 管 理 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 pare

47、nd end 第二章 進(jìn) 程 管 理 2.4.2 哲學(xué)家進(jìn)餐問題哲學(xué)家進(jìn)餐問題 1. 利用記錄型信號量解決哲學(xué)家進(jìn)餐問題利用記錄型信號量解決哲學(xué)家進(jìn)餐問題 經(jīng)分析可知，放在桌子上的筷子是臨界資源，在一段時間內(nèi)只允許一位哲學(xué)家使用。為了實現(xiàn)對筷子的互斥使用，可以用一個信號量表示一只筷子，由這五個信號量構(gòu)成信號量數(shù)組。其描述如下： Var chopstick: array0, , 4 of semaphore;第二章 進(jìn) 程 管 理 所有信號量均被初始化為1， 第i位哲學(xué)家的活動可描述為： repeat wait(chopsticki); wait(chopstick(i+1) mod 5); e

48、at; signal(chopsticki); signal(chopstick(i+1) mod 5); think; until false; 第二章 進(jìn) 程 管 理 可采取以下幾種解決方法： (1) 至多只允許有四位哲學(xué)家同時去拿左邊的筷子，最終能保證至少有一位哲學(xué)家能夠進(jìn)餐，并在用畢時能釋放出他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。 (2) 僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時，才允許他拿起筷子進(jìn)餐。 (3) 規(guī)定奇數(shù)號哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號哲學(xué)家則相反。按此規(guī)定，將是1、 2號哲學(xué)家競爭1號筷子；3、4號哲學(xué)家競爭3號筷子。即五位哲學(xué)家都先競爭奇數(shù)

49、號筷子，獲得后，再去競爭偶數(shù)號筷子，最后總會有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。 第二章 進(jìn) 程 管 理 2. 利用利用AND信號量機(jī)制解決哲學(xué)家進(jìn)餐問題信號量機(jī)制解決哲學(xué)家進(jìn)餐問題 在哲學(xué)家進(jìn)餐問題中，要求每個哲學(xué)家先獲得兩個臨界資源(筷子)后方能進(jìn)餐，這在本質(zhì)上就是前面所介紹的AND同步問題，故用AND信號量機(jī)制可獲得最簡潔的解法。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

50、(chopstick (i+1) mod 5, chopstick i); until false; 第二章 進(jìn) 程 管 理 2.4.3 讀者讀者-寫者問題寫者問題 1. 利用記錄型信號量解決讀者利用記錄型信號量解決讀者-寫者問題寫者問題 為實現(xiàn)Reader與Writer進(jìn)程間在讀或?qū)憰r的互斥而設(shè)置了一個互斥信號量Wmutex。另外，再設(shè)置一個整型變量Readcount表示正在讀的進(jìn)程數(shù)目。由于只要有一個Reader進(jìn)程在讀，便不允許Writer進(jìn)程去寫。因此，僅當(dāng)Readcount=0, 表示尚無Reader進(jìn)程在讀時，Reader進(jìn)程才需要執(zhí)行Wait(Wmutex)操作。若wait(Wm

51、utex)操作成功，Reader進(jìn)程便可去讀，相應(yīng)地，做Readcount+1操作。同理，僅當(dāng)Reader進(jìn)程在執(zhí)行了Readcount減1操作后其值為0時，才須執(zhí)行signal(Wmutex)操作，以便讓W(xué)riter進(jìn)程寫。又因為Readcount是一個可被多個Reader進(jìn)程訪問的臨界資源，因此，應(yīng)該為它設(shè)置一個互斥信號量rmutex。 第二章 進(jìn) 程 管 理 讀者-寫者問題可描述如下：Var rmutex, wmutex:semaphore =1,1; Readcount:integer =0; begin parbegin Reader:begin repeat wait(rmutex

52、); if readcount=0 then wait(wmutex); Readcount =Readcount+1; signal(rmutex); perform read operation; 第二章 進(jìn) 程 管 理 wait(rmutex); readcount =readcount-1; if readcount=0 then signal(wmutex); signal(rmutex); until false; end writer:begin repeat wait(wmutex); perform write operation; signal(wmutex); until

53、 false; end parend end 第二章 進(jìn) 程 管 理 2. 利用信號量集機(jī)制解決讀者利用信號量集機(jī)制解決讀者-寫者問題寫者問題 Var RN integer; L, mx:semaphore =RN,1; begin parbegin reader:begin repeat Swait(L,1,1); Swait(mx,1,0); perform read operation; 第二章 進(jìn) 程 管 理 Ssignal(L,1); until false; end writer:begin repeat Swait(mx,1,1; L,RN,0); perform write o

54、peration; Ssignal(mx,1); until false; end parend end 第二章 進(jìn) 程 管 理 2.5 管管 程程 機(jī)機(jī) 制制 2.5.1 管程的基本概念管程的基本概念 1. 管程的定義管程的定義 管程由三部分組成： 局部于管程的共享變量說明； 對該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過程； 對局部于管程的數(shù)據(jù)設(shè)置初始值的語句。此外，還須為管程賦予一個名字。 第二章 進(jìn) 程 管 理 圖 2-11 管程的示意圖 共享數(shù)據(jù)一組操作過程初始化代碼進(jìn)入隊列條件(不忙)隊列第二章 進(jìn) 程 管 理 管程的語法如下： type monitor-name=monitor variable

55、declarations procedure entry P1(); begin end; procedure entry P2(); begin end; procedure entry Pn(); begin end; begin initialization code; end 第二章 進(jìn) 程 管 理 2. 條件變量條件變量 管程中對每個條件變量，都須予以說明，其形式為：Var x, y:condition。該變量應(yīng)置于wait和signal之前，即可表示為X.wait和X.signal。例如，由于共享數(shù)據(jù)被占用而使調(diào)用進(jìn)程等待，該條件變量的形式為：nonbusy:condition。此

56、時， wait原語應(yīng)改為nonbusy.wait，相應(yīng)地，signal應(yīng)改為nonbusy.signal。 應(yīng)當(dāng)指出，X.signal操作的作用，是重新啟動一個被阻塞的進(jìn)程，但如果沒有被阻塞的進(jìn)程，則X.signal操作不產(chǎn)生任何后果。這與信號量機(jī)制中的signal操作不同。因為，后者總是要執(zhí)行s =s+1操作，因而總會改變信號量的狀態(tài)。 第二章 進(jìn) 程 管 理 如果有進(jìn)程Q處于阻塞狀態(tài)， 當(dāng)進(jìn)程P執(zhí)行了X.signal操作后，怎樣決定由哪個進(jìn)行執(zhí)行，哪個等待，可采用下述兩種方式之一進(jìn)行處理： (1) P等待，直至Q離開管程或等待另一條件。 (2) Q等待，直至P離開管程或等待另一條件。 采用

57、哪種處理方式， 當(dāng)然是各執(zhí)一詞。 但是Hansan卻采用了第一種處理方式。 第二章 進(jìn) 程 管 理 2.5.2 利用管程解決生產(chǎn)者利用管程解決生產(chǎn)者-消費者問題消費者問題 在利用管程方法來解決生產(chǎn)者-消費者問題時， 首先便是為它們建立一個管程，并命名為Proclucer-Consumer, 或簡稱為PC。其中包括兩個過程： (1) put(item)過程。生產(chǎn)者利用該過程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中，并用整型變量count來表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)countn時， 表示緩沖池已滿， 生產(chǎn)者須等待。 第二章 進(jìn) 程 管 理 (1) put(item)過程。 生產(chǎn)者利用該過程將自己生產(chǎn)的

58、產(chǎn)品投放到緩沖池中， 并用整型變量count來表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)countn時，表示緩沖池已滿，生產(chǎn)者須等待。 (2) get(item)過程。消費者利用該過程從緩沖池中取出一個產(chǎn)品，當(dāng)count0時，表示緩沖池中已無可取用的產(chǎn)品， 消費者應(yīng)等待。 第二章 進(jì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 t

59、hen notfull.wait; buffer(in) =nextp; in =(in+1) mod n; count =count+1; if notempty.queue then notempty.signal; end第二章 進(jìn) 程 管 理 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

60、=0; count =0 end 第二章 進(jìn) 程 管 理 在利用管程解決生產(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 第二章 進(jìn) 程 管 理 2.6 進(jìn)進(jìn) 程程 通通 信信 2.6.1 進(jìn)程通信的類型進(jìn)程通信的類型 1. 共享存儲器系統(tǒng)共享存儲器系統(tǒng)(Shared-Mem