計(jì)算機(jī)操作系統(tǒng)第三版第2章

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

2、 圖 2-1 程序的順序執(zhí)行 (a) 程序的順序執(zhí)行(b) 三條語(yǔ)句的順序執(zhí)行I1C1P1I2C2P2S1S2S3第二章 進(jìn) 程 管 理 2. 程序順序執(zhí)行時(shí)的特征程序順序執(zhí)行時(shí)的特征 順序性：(2) 封閉性： (3) 可再現(xiàn)性： 第二章 進(jìn) 程 管 理 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

3、 Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi, Pj),可寫成PiPj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒(méi)有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)(Initial Node)，把沒(méi)有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)(Final Node)。第二章 進(jìn) 程 管 理 每個(gè)結(jié)點(diǎn)還具有一個(gè)重量(Weight)，用于表示該結(jié)點(diǎn)所含有的程序量或結(jié)點(diǎn)的執(zhí)行時(shí)間。 IiCiPi和S1S2S3 圖 2-2 前趨圖 P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九個(gè)結(jié)點(diǎn)的前趨圖(b) 具有循環(huán)的前趨圖第二

4、章 進(jìn) 程 管 理 對(duì)于圖 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, P9) 應(yīng)當(dāng)注意，前趨圖中必須不存在循環(huán)，但在圖2-2(b)中卻有著下述的前趨關(guān)系：S2S3, S

5、3S2 第二章 進(jìn) 程 管 理 2.1.3 程序的并發(fā)執(zhí)行及其特征程序的并發(fā)執(zhí)行及其特征 1. 程序的并發(fā)執(zhí)行程序的并發(fā)執(zhí)行 圖 2-3 并發(fā)執(zhí)行時(shí)的前趨圖 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í)行。 對(duì)于具有下述四條語(yǔ)句的程序段： S1: a =x+2 S2: b =y+4 S3: c =a+b S4: d =c+b 第二章 進(jìn) 程 管 理 圖 2-4 四條語(yǔ)句的前趨關(guān)系S1S2S3S

6、4第二章 進(jìn) 程 管 理 2. 程序并發(fā)執(zhí)行時(shí)的特征程序并發(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。

7、第二章 進(jìn) 程 管 理 2.1.4 進(jìn)程的特征與狀態(tài)進(jìn)程的特征與狀態(tài) 1. 進(jìn)程的特征和定義進(jìn)程的特征和定義 結(jié)構(gòu)特征2) 動(dòng)態(tài)性 :生命周期3) 并發(fā)性 4) 獨(dú)立性：基本單位 5) 異步性 ：不可預(yù)知第二章 進(jìn) 程 管 理 較典型的進(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í)體的概念后，我們可以把傳統(tǒng)OS中的進(jìn)程定義為：“進(jìn)程是進(jìn)程實(shí)體的運(yùn)行過(guò)程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個(gè)獨(dú)立單位”。 第二章 進(jìn) 程 管 理 2.

8、進(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í)行時(shí)間片完進(jìn)程調(diào)度I/O完成I/O請(qǐng)求第二章 進(jìn) 程 管 理 3. 掛起狀態(tài)掛起狀態(tài)引入掛起狀態(tài)的原因引入掛起狀態(tài)的原因 終端用戶的請(qǐng)求。 (2) 父進(jìn)程請(qǐng)求。 (3) 負(fù)荷調(diào)節(jié)的需要。 1) (4) 操作系統(tǒng)的需要。 第二章 進(jìn) 程 管 理 2) 進(jìn)程狀態(tài)的轉(zhuǎn)換 活動(dòng)就緒靜止就緒。 (2) 活動(dòng)阻塞靜止阻塞。 (3) 靜止就緒活動(dòng)就緒。 (4) 靜止阻塞活動(dòng)阻塞。 第二章 進(jìn) 程 管 理 圖 2-6 具有掛起狀態(tài)的進(jìn)程狀態(tài)圖

9、活動(dòng)就緒靜止就緒執(zhí)行掛起激活釋放掛起活動(dòng)阻塞靜止阻塞掛起激活釋放請(qǐng)求I/O第二章 進(jìn) 程 管 理 2.1.5 進(jìn)程控制塊進(jìn)程控制塊 1. 進(jìn)程控制塊的作用進(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)行控制和管理的。第二章 進(jìn) 程 管 理 2. 進(jìn)程控制塊中的信息進(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í)符，它通常

10、是一個(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)程的用戶。 第二章 進(jìn) 程 管 理 2) 處理機(jī)狀態(tài) 處理機(jī)狀態(tài)信息主要是由處理機(jī)的各種寄存器中的內(nèi)容組成的。 通用寄存器，又稱為用戶可視寄存器，它們是用戶程序可以訪問(wèn)的，用于暫存信息， 在大多數(shù)處理機(jī)中，有 832 個(gè)通用寄存器，在RISC結(jié)構(gòu)的計(jì)算機(jī)中可超過(guò) 100 個(gè)； 指令計(jì)數(shù)器，其中存放了要訪問(wèn)的下一條指令的地址； 程序狀態(tài)字PSW

11、，其中含有狀態(tài)信息，如條件碼、執(zhí)行方式、 中斷屏蔽標(biāo)志等； 用戶棧指針， 指每個(gè)用戶進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的系統(tǒng)棧，用于存放過(guò)程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。 第二章 進(jìn) 程 管 理 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)所

12、等待發(fā)生的事件，即阻塞原因。 第二章 進(jìn) 程 管 理 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的首地址。 第二章 進(jìn) 程 管 理 3. 進(jìn)程控制塊的組織方式進(jìn)程控制塊的組織方式 1) 鏈接方式 圖

13、 2-7 PCB鏈接隊(duì)列示意圖 PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901執(zhí)行指針就緒隊(duì)列指針阻塞隊(duì)列指針空閑隊(duì)列指針第二章 進(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)程樹(shù) DEFGHBCIJKLMA第二章 進(jìn) 程 管 理 2. 引起創(chuàng)建進(jìn)程的事件引起創(chuàng)建進(jìn)程的事件 用戶登錄。

14、 (2) 作業(yè)調(diào)度。 (3) 提供服務(wù)。 (4) 應(yīng)用請(qǐng)求。 第二章 進(jìn) 程 管 理 3. 進(jìn)程的創(chuàng)建進(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ì)列。 第二章 進(jìn) 程 管 理 2.2.2 進(jìn)程的終止進(jìn)程的終止 1. 引起進(jìn)程終止引起進(jìn)程終止(Termination of Process)的事件的事件 1) 正常結(jié)束 在任何計(jì)算機(jī)系統(tǒng)中，都應(yīng)有一個(gè)用于表示進(jìn)程已經(jīng)運(yùn)行完成的指示。例如，在批處理系統(tǒng)中，通常在程序的最后安排一

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

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

17、將終止該進(jìn)程； 父進(jìn)程終止。 當(dāng)父進(jìn)程終止時(shí)，OS也將他的所有子孫進(jìn)程終止。 第二章 進(jìn) 程 管 理 2. 進(jìn)程的終止過(guò)程進(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)搜集信息

18、。 第二章 進(jìn) 程 管 理 2.2.3 進(jìn)程的阻塞與喚醒進(jìn)程的阻塞與喚醒1. 引起進(jìn)程阻塞和喚醒的事件引起進(jìn)程阻塞和喚醒的事件 請(qǐng)求系統(tǒng)服務(wù)：服務(wù)未滿足 2) 啟動(dòng)某種操作 ：典型I/O操作3) 新數(shù)據(jù)尚未到達(dá)： 4) 無(wú)新工作可做：等待 第二章 進(jìn) 程 管 理 2. 進(jìn)程阻塞過(guò)程進(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è)置了因

19、不同事件而阻塞的多個(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)境。 第二章 進(jìn) 程 管 理 3. 進(jìn)程喚醒過(guò)程進(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)由阻塞改為就緒，然后再

20、將該P(yáng)CB插入到就緒隊(duì)列中。 第二章 進(jìn) 程 管 理 2.2.4 進(jìn)程的掛起與激活進(jìn)程的掛起與激活 1. 進(jìn)程的掛起進(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)度。 第二章 進(jìn) 程 管 理 2.

21、 進(jìn)程的激活過(guò)程進(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)

22、程。 第二章 進(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)者-消費(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)程可從

23、一個(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)品。 第二章 進(jìn) 程 管 理 我們可利用一個(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

24、n；輸出指針加1表示成out =(out+1) mod n。當(dāng)(in+1) mod n=out時(shí)表示緩沖池滿；而in=out則表示緩沖池空。此外，還引入了一個(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。生產(chǎn)者和消費(fèi)者兩進(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, , n; 指針in

25、和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)品。 第二章 進(jìn) 程 管 理 producer: repeat produce an item in nextp; while counter=n do no-op; bufferin =nextp; in =i

26、n+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)者程序和消費(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ì)它做減

27、1操作，這兩個(gè)操作在用機(jī)器語(yǔ)言實(shí)現(xiàn)時(shí)， 常可用下面的形式描述： 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ī)器語(yǔ)言語(yǔ)句，然后消費(fèi)者進(jìn)程再執(zhí)行右列的三條語(yǔ)句， 則最后共享變量counter的值仍為5；反之，如果讓消費(fèi)者進(jìn)程先執(zhí)行右列的三條語(yǔ)句，然后再讓生產(chǎn)者進(jìn)程執(zhí)行左列的三條語(yǔ)句，co

28、unter值也還是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) 可把一個(gè)訪問(wèn)臨界資源的循環(huán)進(jìn)程

29、描述如下：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) 有限等待：有限時(shí)間 (4) 讓權(quán)等待：不能忙等 第二章 進(jìn) 程 管 理 2.3.2 信號(hào)量機(jī)制信號(hào)量機(jī)制 1. 整型信號(hào)量整型信號(hào)量 最初由Dijkstra把整型信號(hào)量定義為一個(gè)整型量，除初始化外，僅能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作(Atomic Operation) wait(S)和signal(S)來(lái)訪問(wèn)。這兩個(gè)操作一直

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

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

32、lue =S.value+1; if S.value0 then wakeup(S.L); end 第二章 進(jìn) 程 管 理 在記錄型信號(hào)量機(jī)制中，S.value的初值表示系統(tǒng)中某類資源的數(shù)目， 因而又稱為資源信號(hào)量，對(duì)它的每次wait操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類資源，因此描述為S.value =S.value-1； 當(dāng)S.value0時(shí)，表示該類資源已分配完畢，因此進(jìn)程應(yīng)調(diào)用block原語(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)

33、程釋放一個(gè)單位資源，故S.value =S.value+1操作表示資源數(shù)目加1。 若加1后仍是S.value0，則表示在該信號(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)量。 第二章 進(jìn) 程 管 理 3. AND型信號(hào)量型信號(hào)量 在兩個(gè)進(jìn)程中都要包含兩個(gè)對(duì)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)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。亦即，對(duì)若干個(gè)臨界資源的分配，采取原子操作方式：要

35、么全部分配到進(jìn)程，要么一個(gè)也不分配。 由死鎖理論可知，這樣就可避免上述死鎖情況的發(fā)生。為此，在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)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. 信號(hào)量集信號(hào)量集 Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn

37、 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 associat

38、ed with Si into the ready queue endfor; 第二章 進(jìn) 程 管 理 一般“信號(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)量(S1時(shí))或互斥信號(hào)量(S=1時(shí))。 (3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng)S1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開(kāi)關(guān)。 第二章 進(jìn) 程 管 理 2

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

40、ction until false; end parend 第二章 進(jìn) 程 管 理 2. 利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系利用信號(hào)量實(shí)現(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); S4

41、; signal(f); end; begin wait(d); S5; signal(g); end; begin wait(e); wait(f); wait(g); S6; end; parend end 第二章 進(jìn) 程 管 理 2.3.4 管管 程程 機(jī)機(jī) 制制 2.4.1 管程的基本概念管程的基本概念 1. 管程的定義管程的定義 管程由三部分組成： 局部于管程的共享變量說(shuō)明； 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程； 對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句。此外，還須為管程賦予一個(gè)名字。 第二章 進(jìn) 程 管 理 圖 2-11 管程的示意圖 共享數(shù)據(jù)一組操作過(guò)程初始化代碼進(jìn)入隊(duì)列條件(不忙)隊(duì)列第

42、二章 進(jìn) 程 管 理 管程的語(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 第二章 進(jìn) 程 管 理 2. 條件變量條件變量 管程中對(duì)每個(gè)條件變量，都須予以說(shuō)明，其形式為：Var x, y:condition。該變量應(yīng)置于wait和signal之前，即可表示為X.wait和X.si

43、gnal。例如，由于共享數(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)。 第二章 進(jìn) 程 管 理 如果有進(jìn)程Q處于阻塞狀態(tài)， 當(dāng)進(jìn)程P執(zhí)行了X.signal操作后，怎樣決定由哪個(gè)進(jìn)行執(zhí)行，哪個(gè)等待，可采用下述兩種方式之一進(jìn)

44、行處理： (1) P等待，直至Q離開(kāi)管程或等待另一條件。 (2) Q等待，直至P離開(kāi)管程或等待另一條件。 采用哪種處理方式， 當(dāng)然是各執(zhí)一詞。 但是Hansan卻采用了第一種處理方式。 第二章 進(jìn) 程 管 理 2.4 經(jīng)典進(jìn)程的同步問(wèn)題經(jīng)典進(jìn)程的同步問(wèn)題 2.4.1 生產(chǎn)者生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wèn)題 前面我們已經(jīng)對(duì)生產(chǎn)者消費(fèi)者問(wèn)題(The proceducer-consumer problem)做了一些描述，但未考慮進(jìn)程的互斥與同步問(wèn)題，因而造成了數(shù)據(jù)Counter的不定性。由于生產(chǎn)者消費(fèi)者問(wèn)題是相互合作的進(jìn)程關(guān)系的一種抽象，例如， 在輸入時(shí)，輸入進(jìn)程是生產(chǎn)者，計(jì)算進(jìn)程是消費(fèi)者；而在輸出時(shí)，則

45、計(jì)算進(jìn)程是生產(chǎn)者，而打印進(jìn)程是消費(fèi)者， 因此，該問(wèn)題有很大的代表性及實(shí)用價(jià)值。 第二章 進(jìn) 程 管 理 1. 利用記錄型信號(hào)量解決生產(chǎn)者利用記錄型信號(hào)量解決生產(chǎn)者消費(fèi)者問(wè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)題可描述如下： 第二章 進(jìn) 程 管 理 Var mutex, empty, full

46、: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(full); wait(mute

47、x); 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)者消費(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)則

48、在打印進(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)程死鎖。第二章 進(jìn) 程 管 理 2. 利用利用AND信號(hào)量解決生產(chǎn)者信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題消費(fèi)者問(wè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 pr

49、oduce 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 parend end 第二章 進(jìn) 程

50、 管 理 2.4.2 哲學(xué)家進(jìn)餐問(wèn)題哲學(xué)家進(jìn)餐問(wèn)題 1. 利用記錄型信號(hào)量解決哲學(xué)家進(jìn)餐問(wèn)題利用記錄型信號(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: array0, , 4 of semaphore;第二章 進(jìn) 程 管 理 所有信號(hào)量均被初始化為1， 第i位哲學(xué)家的活動(dòng)可描述為： repeat wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal(cho

51、psticki); signal(chopstick(i+1) mod 5); think; until false; 第二章 進(jìn) 程 管 理 死鎖產(chǎn)生后，可采取以下幾種解決方法： (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é)家則相反。按此規(guī)定，將是1、 2號(hào)哲學(xué)家競(jìng)爭(zhēng)1號(hào)筷子；3、4號(hào)哲學(xué)家競(jìng)爭(zhēng)3號(hào)筷子。即五位哲學(xué)家都先競(jìng)爭(zhēng)奇數(shù)號(hào)筷子，獲得后，

52、再去競(jìng)爭(zhēng)偶數(shù)號(hào)筷子，最后總會(huì)有一位哲學(xué)家能獲得兩只筷子而進(jìn)餐。 第二章 進(jìn) 程 管 理 2. 利用利用AND信號(hào)量機(jī)制解決哲學(xué)家進(jìn)餐問(wèn)題信號(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(chopsti

53、ck (i+1) mod 5, chopstick i); until false; 第二章 進(jìn) 程 管 理 2.4.3 讀者讀者-寫者問(wèn)題寫者問(wèn)題 1. 利用記錄型信號(hào)量解決讀者利用記錄型信號(hào)量解決讀者-寫者問(wèn)題寫者問(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)操作成

54、功，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。 第二章 進(jìn) 程 管 理 讀者-寫者問(wèn)題可描述如下：Var rmutex, wmutex:semaphore =1,1; Readcount:integer =0; begin parbegin Reader:begin repeat wait(rmutex); if re

55、adcount=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 false;

56、end parend end 第二章 進(jìn) 程 管 理 2. 利用信號(hào)量集機(jī)制解決讀者利用信號(hào)量集機(jī)制解決讀者-寫者問(wèn)題寫者問(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; 第二章 進(jìn) 程 管 理 Ssignal(L,1); until false; end writer:begin repeat Swait(mx,1,1; L,RN,0); perform write operation

57、; Ssignal(mx,1); until false; end parend end 第二章 進(jìn) 程 管 理 2.5 進(jìn)進(jìn) 程程 通通 信信 2.5.1 進(jìn)程通信的類型進(jìn)程通信的類型 1. 共享存儲(chǔ)器系統(tǒng)共享存儲(chǔ)器系統(tǒng)(Shared-Memory System) 基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式。 (2) 基于共享存儲(chǔ)區(qū)的通信方式。 第二章 進(jìn) 程 管 理 2. 消息傳遞系統(tǒng)消息傳遞系統(tǒng)(Message passing system) 不論是單機(jī)系統(tǒng)、多機(jī)系統(tǒng)，還是計(jì)算機(jī)網(wǎng)絡(luò)，消息傳遞機(jī)制都是用得最廣泛的一種進(jìn)程間通信的機(jī)制。在消息傳遞系統(tǒng)中，進(jìn)程間的數(shù)據(jù)交換，是以格式化的消息(message)

58、為單位的；在計(jì)算機(jī)網(wǎng)絡(luò)中，又把message稱為報(bào)文。程序員直接利用系統(tǒng)提供的一組通信命令(原語(yǔ))進(jìn)行通信。操作系統(tǒng)隱藏了通信的實(shí)現(xiàn)細(xì)節(jié)，大大減化了通信程序編制的復(fù)雜性，而獲得廣泛的應(yīng)用。消息傳遞系統(tǒng)的通信方式屬于高級(jí)通信方式。又因其實(shí)現(xiàn)方式的不同而進(jìn)一步分成直接通信方式和間接通信方式兩種。 第二章 進(jìn) 程 管 理 3. 管道管道(Pipe)通信通信 所謂“管道”，是指用于連接一個(gè)讀進(jìn)程和一個(gè)寫進(jìn)程以實(shí)現(xiàn)他們之間通信的一個(gè)共享文件，又名pipe文件。向管道(共享文件)提供輸入的發(fā)送進(jìn)程(即寫進(jìn)程)， 以字符流形式將大量的數(shù)據(jù)送入管道；而接受管道輸出的接收進(jìn)程(即讀進(jìn)程)，則從管道中接收(讀)數(shù)

59、據(jù)。由于發(fā)送進(jìn)程和接收進(jìn)程是利用管道進(jìn)行通信的，故又稱為管道通信。這種方式首創(chuàng)于UNIX系統(tǒng)，由于它能有效地傳送大量數(shù)據(jù)，因而又被引入到許多其它操作系統(tǒng)中。 第二章 進(jìn) 程 管 理 為了協(xié)調(diào)雙方的通信，管道機(jī)制必須提供以下三方面的協(xié)調(diào)能力： 互斥，即當(dāng)一個(gè)進(jìn)程正在對(duì)pipe執(zhí)行讀/寫操作時(shí)，其它(另一)進(jìn)程必須等待。 同步，指當(dāng)寫(輸入)進(jìn)程把一定數(shù)量(如4 KB)的數(shù)據(jù)寫入pipe，便去睡眠等待， 直到讀(輸出)進(jìn)程取走數(shù)據(jù)后，再把他喚醒。當(dāng)讀進(jìn)程讀一空pipe時(shí)，也應(yīng)睡眠等待，直至寫進(jìn)程將數(shù)據(jù)寫入管道后，才將之喚醒。 確定對(duì)方是否存在，只有確定了對(duì)方已存在時(shí)，才能進(jìn)行通信。 第二章 進(jìn) 程

60、 管 理 2.5.2 消息傳遞通信的實(shí)現(xiàn)方法消息傳遞通信的實(shí)現(xiàn)方法 1. 直接通信方式直接通信方式 這是指發(fā)送進(jìn)程利用OS所提供的發(fā)送命令，直接把消息發(fā)送給目標(biāo)進(jìn)程。此時(shí)，要求發(fā)送進(jìn)程和接收進(jìn)程都以顯式方式提供對(duì)方的標(biāo)識(shí)符。通常，系統(tǒng)提供下述兩條通信命令(原語(yǔ))： Send(Receiver, message); 發(fā)送一個(gè)消息給接收進(jìn)程； Receive(Sender, message); 接收Sender發(fā)來(lái)的消息；例如，原語(yǔ)Send(P2, m1)表示將消息m1發(fā)送給接收進(jìn)程P2; 而原語(yǔ)Receive(P1，m1)則表示接收由P1發(fā)來(lái)的消息m1。 第二章 進(jìn) 程 管 理 在某些情況下，接