1、第二章 進(jìn)程管理,2.1 進(jìn)程的基本概念 2.2 進(jìn)程控制 2.3 進(jìn)程同步 2.4 經(jīng)典進(jìn)程的同步問(wèn)題 2.5 管程機(jī)制 2.6 進(jìn)程通信 2.7 線程,2.1 進(jìn)程的基本概念,在無(wú)操作系統(tǒng)和單道程序系統(tǒng)中，程序的執(zhí)行是順序的。而隨著多道程序的出現(xiàn)，系統(tǒng)中程序執(zhí)行環(huán)境變化了，尤其當(dāng)出現(xiàn)同名程序并發(fā)執(zhí)行時(shí)，迫切需要一個(gè)實(shí)體來(lái)描述程序的執(zhí)行過(guò)程。 這個(gè)實(shí)體就是進(jìn)程。,2.1.1 程序的順序執(zhí)行及其特征,程序是存儲(chǔ)在存儲(chǔ)介質(zhì)上的（可執(zhí)行）文件。 程序是一個(gè)在時(shí)間上按嚴(yán)格次序前后相繼的操作序列，是一個(gè)靜態(tài)的概念。 程序體現(xiàn)了編程人員要求計(jì)算機(jī)完成所要求功能時(shí)應(yīng)該采取的順序步驟。 一般用戶在編寫(xiě)程序時(shí)

2、不考慮在自己的程序執(zhí)行過(guò)程中還有其他用戶程序存在。,1. 程序的順序執(zhí)行,通?？梢詫⒁粋€(gè)程序分成若干段，在各段之間必須按某種順序執(zhí)行，僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。也就是說(shuō)先后有順序關(guān)系。 例如，在進(jìn)行計(jì)算時(shí)，總須先輸入程序和數(shù)據(jù)，然后進(jìn)行計(jì)算，最后才能打印計(jì)算結(jié)果。 再如下述三條語(yǔ)句： S1: a=x+y; S2: b=a-5; S3: c=b+1; 也必須按順序執(zhí)行。,2. 程序順序執(zhí)行時(shí)的特征,(1) 順序性： 按程序規(guī)定的順序執(zhí)行。 (2) 封閉性： 不受外界干擾。 (3) 可再現(xiàn)性： 只要初始條件和環(huán)境相同，不論何時(shí)執(zhí)行，結(jié)果總是相同的。,2.1.2 前趨圖,前趨

3、圖（Precedence Graph）是一個(gè)有向無(wú)循環(huán)圖，記為DAG（Directed Acyclic Graph），用于描述進(jìn)程之間執(zhí)行的前后關(guān)系。 圖中的每個(gè)結(jié)點(diǎn)可用于描述一個(gè)程序段或進(jìn)程，乃至一條語(yǔ)句；結(jié)點(diǎn)間的有向邊則用于表示兩個(gè)結(jié)點(diǎn)之間存在的偏序（Partial Order）或前趨關(guān)系（Precedence Relation）“”。,前趨圖及相關(guān)概念,=（Pi，Pj）| Pi必須在 Pj開(kāi)始前執(zhí)行完畢，如果（Pi，Pj），可寫(xiě)成PiPj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。 在前趨圖中，把沒(méi)有前趨的結(jié)點(diǎn)稱為初始結(jié)點(diǎn)（Initial Node），把沒(méi)有后繼的結(jié)點(diǎn)稱為終止結(jié)點(diǎn)

4、（Final Node）。 每個(gè)節(jié)點(diǎn)還具有一個(gè)權(quán)重（Weight），用于表示該節(jié)點(diǎn)所含有程序的執(zhí)行時(shí)間。 前趨圖中必須不能有循環(huán)。 圖2-1中的前趨關(guān)系表示為 IiCiPi 和 S1S2S3,前趨圖的示例,前趨圖2-2a存在以下前趨關(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),

5、(P5, P8), (P6, P8), (P7, P9), (P8, P9) ,2.1.3 程序的并發(fā)執(zhí)行及其特征,1. 程序的并發(fā)執(zhí)行 在圖2-1a所示的IiCiPi前趨關(guān)系中，ICP必須是順序執(zhí)行的，但是并不存在PiIi+1關(guān)系，因此對(duì)此批程序的處理可以并發(fā)進(jìn)行。 由前趨圖可得前趨關(guān)系為： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1,并發(fā)示例,對(duì)于具有下述四條語(yǔ)句的程序段： S1: a :=x+2 S2: b :=y+4 S3: c :=a+b S4: d :=c+b S3要等待S1和S2執(zhí)行完畢才能進(jìn)行，S4要依賴于S3，但S1和S2沒(méi)有先后關(guān)系可以并發(fā)。于是可得前

6、趨關(guān)系圖。,2. 程序并發(fā)執(zhí)行時(shí)的特征,設(shè)有兩個(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)行?？赡艹霈F(xiàn)以下不同結(jié)果： N=N+1在Print(N)和N=0之前，N為：n+1, n+1, 0 N=N+1在Print(N)和N=0之后，N為：n, 0, 1 N=N+1在Print(N)和N=0之間，N為：n, n+1, 0,2. 程序并發(fā)執(zhí)行時(shí)的特征,1) 間斷性 2) 失去封閉性 3) 不可再現(xiàn)性,2.1.4 進(jìn)程的特征與狀態(tài),在多道程序環(huán)境下，程序的執(zhí)行將失去其

7、封閉性，從而導(dǎo)致不可再現(xiàn)性。這就決定了程序不能參與并發(fā)執(zhí)行，因此，程序的運(yùn)行就失去了意義。 于是引入了“進(jìn)程”的概念。,1. 進(jìn)程的特征和定義,1) 結(jié)構(gòu)特征：程序段+數(shù)據(jù)段+PCB（=進(jìn)程實(shí)體）。 2) 動(dòng)態(tài)性：進(jìn)程刻畫(huà)的是程序的執(zhí)行過(guò)程。 3) 并發(fā)性：進(jìn)程可以并發(fā)執(zhí)行。 4) 獨(dú)立性：進(jìn)程是搶占資源的基本單位，能獨(dú)立運(yùn)行、獨(dú)立申請(qǐng)資源、獨(dú)立進(jìn)行調(diào)度。 5) 異步性：各并發(fā)進(jìn)程彼此獨(dú)立，以不可預(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)行資源

8、分配和調(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)程的定義舉例,(1)進(jìn)程是可以并行/發(fā)執(zhí)行的計(jì)算部分(S.E.Madnick，J.T.Donovan)； (2)進(jìn)程是一個(gè)獨(dú)立的可以調(diào)度的活動(dòng)(E.Cohen，D.Jofferson)； (3)進(jìn)程是一抽象實(shí)體，當(dāng)它執(zhí)行某個(gè)任務(wù)時(shí)，將要分配和釋放各種資源(P.Denning)； (4)行為的規(guī)則叫程序，程序在處理機(jī)上執(zhí)行時(shí)的活動(dòng)稱為進(jìn)程(E.W.Dijkstra)； (5)一個(gè)進(jìn)程是一系列逐一執(zhí)行的操作，而操作的確切含義則有賴于以何種

9、詳盡程度來(lái)描述進(jìn)程(Brinch Hansen)。 他們突出了進(jìn)程是一個(gè)動(dòng)態(tài)的執(zhí)行過(guò)程。,2. 進(jìn)程的三種基本狀態(tài),1) 就緒(Ready)狀態(tài) 2) 執(zhí)行狀態(tài) 3) 阻塞狀態(tài),3.掛起狀態(tài),所謂進(jìn)程掛起是指暫時(shí)將某個(gè)進(jìn)程“凍結(jié)”,不讓其參與操作系統(tǒng)內(nèi)部的進(jìn)程調(diào)度而變?yōu)殪o止的狀態(tài)。,1)引入掛起狀態(tài)的原因,(1) 終端用戶的請(qǐng)求。 (2) 父進(jìn)程請(qǐng)求。 (3) 負(fù)荷調(diào)節(jié)的需要。 (4) 操作系統(tǒng)的需要。,2) 進(jìn)程狀態(tài)的轉(zhuǎn)換,引入掛起狀態(tài)后，又將增加從掛起到非掛起和從非掛起到掛起狀態(tài)的轉(zhuǎn)換。幾種可能情況如下： (1) 活動(dòng)就緒靜止就緒。 (2) 活動(dòng)阻塞靜止阻塞。 (3) 靜止就緒活動(dòng)就緒。

10、(4) 靜止阻塞活動(dòng)阻塞。,具有掛起狀態(tài)的進(jìn)程狀態(tài)圖,4. 進(jìn)程的創(chuàng)建和終止,在一個(gè)進(jìn)程的生命周期中，還存在著創(chuàng)建和終止?fàn)顟B(tài)。即進(jìn)程的出生與死亡。,1）創(chuàng)建狀態(tài),創(chuàng)建一個(gè)進(jìn)程要分作兩步： 為新進(jìn)程創(chuàng)建一個(gè)PCB結(jié)構(gòu)，并填寫(xiě)必要的信息。 其次是為其分配資源 一個(gè)進(jìn)程處于此兩步之間時(shí)的狀態(tài)就被稱為處于創(chuàng)建狀態(tài)。 引入創(chuàng)建狀態(tài)的目的是為了保證進(jìn)程調(diào)度必須在創(chuàng)建完成之后進(jìn)行，以確保對(duì)進(jìn)程控制塊操作的完整性。同時(shí)也增加了管理的靈活性。,2）終止?fàn)顟B(tài),當(dāng)一個(gè)進(jìn)程的執(zhí)行進(jìn)入正常結(jié)束或非正常結(jié)束，或被其它進(jìn)程所終止，進(jìn)程進(jìn)入終止?fàn)顟B(tài)。 進(jìn)程終止也分作兩步：釋放資源，釋放PCB。 當(dāng)一個(gè)進(jìn)程進(jìn)入終止?fàn)顟B(tài)后，不能

11、再執(zhí)行，且資源基本上都釋放，但還保留著PCB，其中保存著狀態(tài)碼和一些計(jì)時(shí)和統(tǒng)計(jì)信息，供其它進(jìn)程收集。一旦信息被收集完畢，則刪除PCB，進(jìn)程被徹底清除。,具有創(chuàng)建和終止的進(jìn)程的狀態(tài),具有創(chuàng)建、終止和掛起狀態(tài)的進(jìn)程狀態(tài)轉(zhuǎn)換圖,2.1.5 進(jìn)程控制塊,為了描述和控制進(jìn)程的活動(dòng)，系統(tǒng)為每個(gè)進(jìn)程定義并增加了個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)程控制塊PCB（Process Control Block），它是進(jìn)程實(shí)體的一部分，記錄操作系統(tǒng)所需的、用于描述進(jìn)程資源占用、當(dāng)前狀況以及控制進(jìn)程運(yùn)行的全部信息。 PCB集中反映一個(gè)進(jìn)程的動(dòng)態(tài)特征。 當(dāng)一個(gè)進(jìn)程完成其功能之后，系統(tǒng)則釋放PCB，進(jìn)程也隨之消亡。,1. 進(jìn)程控制塊的作用,PC

12、B是OS感知進(jìn)程存在的唯一實(shí)體。 進(jìn)程控制塊的作用是使一個(gè)在多道程序環(huán)境下不能獨(dú)立運(yùn)行的程序(含數(shù)據(jù))，成為一個(gè)能獨(dú)立運(yùn)行的基本單位，一個(gè)能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程。 或者說(shuō)，OS是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。,2. 進(jìn)程控制塊中的信息,PCB包含一個(gè)進(jìn)程的完整的描述信息、控制信息及資源信息，有些系統(tǒng)中還有進(jìn)程調(diào)度、等待所使用的現(xiàn)場(chǎng)保護(hù)區(qū)等信息。,1) 進(jìn)程標(biāo)識(shí)符,進(jìn)程標(biāo)識(shí)符用于惟一地標(biāo)識(shí)一個(gè)進(jìn)程。一個(gè)進(jìn)程通常有兩種標(biāo)識(shí)符： (1) 內(nèi)部標(biāo)識(shí)符。在所有的操作系統(tǒng)中，都為每一個(gè)進(jìn)程賦予一個(gè)惟一的數(shù)字標(biāo)識(shí)符，它通常是一個(gè)進(jìn)程的序號(hào)（PID）。 設(shè)置內(nèi)部標(biāo)識(shí)符主要是為了方便系統(tǒng)使用

13、。 (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)程的用戶。,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ù)器（PC/IP）：存放下一條要訪問(wèn)指令的地址； 程序狀態(tài)字PSW：含有狀態(tài)信息，如條件碼、執(zhí)行方式、 中斷屏蔽標(biāo)志等； 用戶棧指針：指每個(gè)用

14、戶進(jìn)程都有一個(gè)或若干個(gè)與之相關(guān)的棧，用于存放過(guò)程和系統(tǒng)調(diào)用參數(shù)及調(diào)用地址。棧指針指向該棧的棧頂。,3) 進(jìn)程調(diào)度信息, 進(jìn)程狀態(tài)：指明進(jìn)程的當(dāng)前狀態(tài)，作為進(jìn)程調(diào)度和對(duì)換時(shí)的依據(jù)； 進(jìn)程優(yōu)先級(jí)：用于描述進(jìn)程使用處理機(jī)的優(yōu)先級(jí)別的一個(gè)整數(shù)， 優(yōu)先級(jí)高的進(jìn)程應(yīng)優(yōu)先獲得處理機(jī)； 進(jìn)程調(diào)度所需的其它信息：它們與所采用的進(jìn)程調(diào)度算法有關(guān)，比如，進(jìn)程已等待CPU的時(shí)間總和、進(jìn)程已執(zhí)行的時(shí)間總和等； 事件：是指進(jìn)程由執(zhí)行狀態(tài)轉(zhuǎn)變?yōu)樽枞麪顟B(tài)所等待發(fā)生的事件，即阻塞原因。,4) 進(jìn)程控制信息, 程序和數(shù)據(jù)的地址：進(jìn)程的程序和數(shù)據(jù)所在的內(nèi)存或外存(首)地址，以便再調(diào)度到該進(jìn)程執(zhí)行時(shí)，能從PCB中找到其程序和數(shù)據(jù)；

15、進(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的首地址。,3. 進(jìn)程控制塊的組織方式,1）鏈接方式 2）索引方式,1）鏈接方式,2）索引方式,2.2 進(jìn) 程 控 制,進(jìn)程和處理機(jī)管理的一個(gè)重要任務(wù)是進(jìn)程控制。 所謂進(jìn)程控制，就是系統(tǒng)使用一些具有特殊功能的程序段來(lái)創(chuàng)建、撤消進(jìn)程以及完成進(jìn)程各狀態(tài)間的轉(zhuǎn)換，從而達(dá)到多進(jìn)程高效率并發(fā)執(zhí)行和協(xié)調(diào)工作，實(shí)現(xiàn)資源共享的目的。 進(jìn)程控

16、制是原語(yǔ)（Primitive）來(lái)實(shí)現(xiàn)的。,原語(yǔ),一般地，把系統(tǒng)態(tài)下的某些具有特定功能的程序段稱為原語(yǔ)。 原語(yǔ)執(zhí)行的是原子操作（Atomic Operation）。 原語(yǔ)共分為兩類： 機(jī)器指令級(jí)：其特點(diǎn)是執(zhí)行期間不允許中斷，正如在物理學(xué)中的原子一樣，在OS中它是不可分割的基本單元。 功能級(jí)的：其特點(diǎn)是作為原語(yǔ)的程序段不允許并發(fā)執(zhí)行。 這兩類原語(yǔ)都是在系統(tǒng)態(tài)下執(zhí)行，且都是為了完成某個(gè)系統(tǒng)管理所需要的功能和被高層軟件所調(diào)用。 在OS中，通常把進(jìn)程控制用程序段做成原語(yǔ)。用于進(jìn)程控制的原語(yǔ)有：創(chuàng)建，撤消，阻塞，喚醒等。,2.2.1 進(jìn)程的創(chuàng)建,進(jìn)程的創(chuàng)建就要為將要執(zhí)行的程序在系統(tǒng)中創(chuàng)建一個(gè)用于控制的執(zhí)行

17、實(shí)體。,1. 進(jìn)程關(guān)系圖,進(jìn)程關(guān)系圖(Process Graph)是用于描述系統(tǒng)內(nèi)進(jìn)程家族的有向圖。在該有向圖中，一條從Pi到Pj的有向邊說(shuō)明了他們之間的父子關(guān)系。 進(jìn)程間的父子、祖先、子孫等關(guān)系就構(gòu)成了一顆樹(shù)。 子進(jìn)程可以繼承父進(jìn)程的資源，但結(jié)束時(shí)要?dú)w還資源；（父進(jìn)程被撤銷(xiāo)也要撤銷(xiāo)其所有的子進(jìn)程。） 在PCB表設(shè)有進(jìn)程家族標(biāo)志。,2. 引起創(chuàng)建進(jìn)程的事件,(1) 用戶登錄 (2) 作業(yè)調(diào)度 (3) 提供服務(wù) (4) 應(yīng)用請(qǐng)求,3. 進(jìn)程的創(chuàng)建(Creation of Process),(1) 申請(qǐng)空白PCB。 (2) 為新進(jìn)程分配資源。 (3) 初始化進(jìn)程控制塊。 (4) 將新進(jìn)程插入就緒隊(duì)

18、列。 (5) 將新進(jìn)程插入家族鏈。,進(jìn)程的創(chuàng)建圖,2.2.2 進(jìn)程的終止,進(jìn)程終止(Termination of Process) ，就是要撤銷(xiāo)系統(tǒng)中某個(gè)正在執(zhí)行的進(jìn)程，并釋放其所占有的資源。,1. 引起進(jìn)程終止的事件,1) 正常結(jié)束 2) 異常結(jié)束 3) 外界干預(yù) 4) 祖先進(jìn)程要求撤消某個(gè)子進(jìn)程。 說(shuō)明： 無(wú)論哪一種情況導(dǎo)致進(jìn)程被撤消，進(jìn)程都必須釋放它所占用的各種資源和PCB結(jié)構(gòu)本身。 當(dāng)一個(gè)祖先進(jìn)程撤消某個(gè)子進(jìn)程時(shí)，還需審查該子進(jìn)程是否還有自己的子孫進(jìn)程，若有的話，還需撤消其子孫進(jìn)程的PCB結(jié)構(gòu)和釋放它們所占有的資源。,2. 進(jìn)程的終止過(guò)程,(1) 根據(jù)被終止進(jìn)程的標(biāo)識(shí)符，從PCB集合中

19、檢索出該進(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ì)列(或鏈表)中移出。,進(jìn)程終止流程圖,2.2.3 進(jìn)程的阻塞與喚醒,進(jìn)程的創(chuàng)建原語(yǔ)和撤消原語(yǔ)完成了進(jìn)程從無(wú)到有，從存在到消亡的變化。被創(chuàng)建后的進(jìn)程最初處于就緒狀態(tài)，然后經(jīng)調(diào)度程序選中后進(jìn)入執(zhí)行狀態(tài)。 進(jìn)程的阻塞與喚醒實(shí)現(xiàn)進(jìn)程的執(zhí)行狀態(tài)到等待狀態(tài)，又由

20、等待狀態(tài)到就緒狀態(tài)轉(zhuǎn)換。實(shí)現(xiàn)這種狀態(tài)轉(zhuǎn)換的是阻塞原語(yǔ)與喚醒原語(yǔ)。,1. 引起進(jìn)程阻塞和喚醒的事件,1) 請(qǐng)求系統(tǒng)服務(wù) 2) 啟動(dòng)某種操作 3) 新數(shù)據(jù)尚未到達(dá) 4) 無(wú)新工作可做,2. 進(jìn)程阻塞過(guò)程,一個(gè)進(jìn)程在期待某一事件發(fā)生，但發(fā)生條件尚不具備時(shí)，該進(jìn)程自己調(diào)用阻塞原語(yǔ)block來(lái)阻塞自己。 進(jìn)程阻塞是進(jìn)程自己主動(dòng)進(jìn)行的。,阻塞原語(yǔ)實(shí)現(xiàn)進(jìn)程阻塞的過(guò)程,阻塞原語(yǔ)在阻塞一個(gè)進(jìn)程時(shí)，應(yīng)先中斷CPU和保存該進(jìn)程的CPU現(xiàn)場(chǎng)。然后將被阻塞進(jìn)程置 “阻塞”狀態(tài)后插入等待隊(duì)列中，再轉(zhuǎn)進(jìn)程調(diào)度程序選擇新的就緒進(jìn)程投入運(yùn)行。,3. 進(jìn)程喚醒過(guò)程,當(dāng)?shù)却?duì)列中的進(jìn)程所等待的事件發(fā)生時(shí)，等待事件的進(jìn)程將被喚醒。

21、一個(gè)處于阻塞狀態(tài)的進(jìn)程不可能自己?jiǎn)拘炎约?。而是由有關(guān)進(jìn)程調(diào)用wakeup原語(yǔ)實(shí)施的。 喚醒一個(gè)進(jìn)程有兩種方法 一種是由系統(tǒng)喚醒：此時(shí)，系統(tǒng)進(jìn)程統(tǒng)一控制事件的發(fā)生并將“事件發(fā)生”這一消息通知等待進(jìn)程。從而使得該進(jìn)程因等待事件已發(fā)生而進(jìn)入就緒隊(duì)列。 另一種是由事件發(fā)生進(jìn)程喚醒：此時(shí)，事件發(fā)生進(jìn)程和被喚醒進(jìn)程之間是合作關(guān)系。,喚醒原語(yǔ)執(zhí)行過(guò)程,首先把被阻塞的進(jìn)程從等待該事件的阻塞隊(duì)列中移出，將其PCB中的現(xiàn)行狀態(tài)由阻塞改為就緒； 然后再將該P(yáng)CB插入到就緒隊(duì)列中。,2.2.4 進(jìn)程的掛起與激活,1. 進(jìn)程的掛起 當(dāng)出現(xiàn)了引起進(jìn)程掛起的事件時(shí)，比如，用戶進(jìn)程請(qǐng)求將自己掛起，或父進(jìn)程請(qǐng)求將自己的某個(gè)子進(jìn)

22、程掛起， 系統(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)程正在執(zhí)行，則轉(zhuǎn)向調(diào)度程序重新調(diào)度。,2. 進(jìn)程的激活,當(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)程激活。,進(jìn)程的激活過(guò)程,激活原語(yǔ)先將進(jìn)程從外存調(diào)入內(nèi)存，檢查該進(jìn)程的現(xiàn)行狀態(tài)，若是靜止就緒，便將之改為活動(dòng)就緒；若為靜

23、止阻塞便將之改為活動(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)程。,2.3 進(jìn) 程 同 步,引入OS后，雖然提高了資源的利用率，方便了客戶，但也帶來(lái)了自身控制的麻煩。例如：多進(jìn)程使同時(shí)用同一臺(tái)打印機(jī)時(shí)，可能造成輸出混亂；多進(jìn)程爭(zhēng)用同一變量等時(shí)，可能導(dǎo)致數(shù)據(jù)處理錯(cuò)誤；當(dāng)有先后順序關(guān)系執(zhí)行的進(jìn)程，如果先后順序錯(cuò)了也會(huì)導(dǎo)致結(jié)果錯(cuò)誤。 進(jìn)程同步的主要任務(wù)是：使并發(fā)執(zhí)行的諸進(jìn)程之間有效地共享資源，從而保證進(jìn)

24、程執(zhí)行有可再現(xiàn)性。,2.3.1 進(jìn)程同步的基本概念,1. 兩種形式的制約關(guān)系,(1) 間接相互制約關(guān)系 把由于共享某一公有資源而引起的不允許并發(fā)進(jìn)程交叉執(zhí)行的現(xiàn)象，稱為由共享公有資源而造成的并發(fā)進(jìn)程執(zhí)行速度的間接制約，簡(jiǎn)稱間接制約。 沒(méi)有先后關(guān)系。 兩進(jìn)程共享一臺(tái)打印機(jī)，一個(gè)使用時(shí)另個(gè)必須等待。 (2) 直接相互制約關(guān)系 由并發(fā)進(jìn)程互相共享對(duì)方的私有資源所引起的制約稱謂直接制約。 此種制約主要源自進(jìn)程間的合作關(guān)系，有先后關(guān)系。 比如命令ls -l | more將使命令ls -l和more具有合作關(guān)系，因?yàn)閙ore加工的是ls的輸出。,2. 臨界資源(Critical Resource),臨界資

25、源是指采用互斥方式共享的資源，比如打機(jī)、磁帶機(jī)等。而磁盤(pán)、網(wǎng)卡等則不是。,生產(chǎn)者-消費(fèi)者(producer-consumer)問(wèn)題,計(jì)算機(jī)系統(tǒng)中，每個(gè)進(jìn)程都申請(qǐng)使用和釋放各種不同類型的資源，這些資源既可以是像外設(shè)、內(nèi)存及緩沖區(qū)等硬件資源，也包括數(shù)據(jù)、例程等軟件資源。 把系統(tǒng)中使用某一類資源的進(jìn)程稱為該資源的消費(fèi)者。 把釋放同類資源的進(jìn)程稱為該資源的生產(chǎn)者。,生產(chǎn)者-消費(fèi)者問(wèn)題一般模型,把一個(gè)長(zhǎng)度為n的有界緩沖區(qū)（n0）與一群生產(chǎn)者進(jìn)程P1，P2， ，Pm和一群消費(fèi)者進(jìn)程C1，C2， ，Ck聯(lián)系起來(lái)的生產(chǎn)者-消費(fèi)者問(wèn)題如圖所示。,生產(chǎn)者和消費(fèi)者之間的關(guān)系,生產(chǎn)者-消費(fèi)者問(wèn)題是一個(gè)經(jīng)典同步問(wèn)題。生

26、產(chǎn)者和消費(fèi)者之間必須滿足如下條件： （1）消費(fèi)者想接收數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是滿的； （2）生產(chǎn)者想發(fā)送數(shù)據(jù)時(shí)，有界緩沖區(qū)中至少有一個(gè)單元是空的。,生產(chǎn)者-消費(fèi)者問(wè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； 用輸出指針out來(lái)指示下一個(gè)可從中獲取產(chǎn)品的滿緩沖區(qū)，每當(dāng)消費(fèi)者進(jìn)程取走一個(gè)產(chǎn)品后，輸出指針加1。 為使指針不越界且有實(shí)際意義，上面的加1可表示為： in= (in+1) mod n；out= (out+1) mod n。 當(dāng)(in+1) mod n=out

27、時(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。,所用變量,var n：integer; type item=; var buffer：array0, 1, , n-1 of item; in, out：0, 1, , n-1; counter：0, 1, , n; 說(shuō)明： 指針in和out初始化為0。counter初始化為0 no-op：空操作 nextp：生產(chǎn)者臨時(shí)變量，暫存剛生產(chǎn)出的產(chǎn)品 nextc：消費(fèi)者臨時(shí)變量

28、，存放將要消費(fèi)的產(chǎn)品,生產(chǎn)者,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;,消費(fèi)者,consumer: repeat while counter=0 do no-op; nextc := bufferout; out := (out+1) mod n; counter := counter-1; consumer the item in nextc; unt

29、il false;,問(wèn)題,雖然上面的生產(chǎn)者程序和消費(fèi)者程序，在分別看時(shí)都是正確的，而且兩者在順序執(zhí)行時(shí)其結(jié)果也會(huì)是正確的，但若并發(fā)執(zhí)行時(shí)，就會(huì)出現(xiàn)差錯(cuò)，問(wèn)題就在于這兩個(gè)進(jìn)程共享變量counter。(設(shè)counter=5，兩列順序執(zhí)行則結(jié)果正確)。 register1:=counter; | register2:=counter; register1:=register1+1; | register2:=register2-1; counter:=register1;| counter:=register2;,并發(fā)執(zhí)行時(shí)會(huì)出錯(cuò),仍設(shè)counter=5，讓程序交叉執(zhí)行 register1 :=co

30、unter;(register1=5) register1 :=register1+1; (register1=6) register2 :=counter;(register2=5) register2 :=register2-1; (register2=4) counter:=register1; (counter=6) counter:=register2; (counter=4),3. 臨界區(qū),把在每個(gè)進(jìn)程中訪問(wèn)臨界資源的代碼稱為臨界區(qū)/臨界部分(critical region) /臨界段(critical section) ?；虬巡辉试S多個(gè)并發(fā)進(jìn)程交叉執(zhí)行的一段程序稱為臨界區(qū)。 它是

31、由于不同并發(fā)進(jìn)程的程序段共享公用數(shù)據(jù)或公用數(shù)據(jù)變量而引起的。所以臨界區(qū)又被稱為訪問(wèn)公用數(shù)據(jù)的那段程序。 不論是硬件臨界資源，還是軟件臨界資源，多進(jìn)程并發(fā)訪問(wèn)時(shí)，必須互斥進(jìn)行。,臨界區(qū)的訪問(wèn),若能實(shí)現(xiàn)諸并發(fā)進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，便可實(shí)現(xiàn)諸進(jìn)程對(duì)臨界資源的正確訪問(wèn)。為此，每個(gè)進(jìn)程在進(jìn)入臨界區(qū)之前應(yīng)該對(duì)臨界資源進(jìn)行檢查，若無(wú)人訪問(wèn)則可進(jìn)入，否則只能等待。 為此需要在臨界區(qū)前、后各增加一個(gè)申請(qǐng)進(jìn)入和宣告退出臨界區(qū)代碼： “進(jìn)入臨界區(qū)”(entry section)：測(cè)試臨界資源是否被使用，若未被使用則設(shè)置已用標(biāo)志，然后進(jìn)入臨界區(qū)，否則等待； “退出臨界區(qū)”(exit section)：將占用標(biāo)志

32、清除，以供其它進(jìn)行使用。 程序中除了臨界區(qū)和此兩部分的部分稱為其余部分(remainder section)。,臨界區(qū)的訪問(wèn)框架,repeat critical section; remainder section; until false;,entry section /測(cè)試或申請(qǐng)進(jìn)入臨界區(qū),exit section /釋放或聲明退出臨界區(qū),4. 同步機(jī)制應(yīng)遵循的規(guī)則,為實(shí)現(xiàn)進(jìn)程互斥地進(jìn)入臨界區(qū)，可以使用軟件方法，更多的是在系統(tǒng)中設(shè)置專門(mén)同步機(jī)構(gòu)來(lái)協(xié)調(diào)進(jìn)程間的運(yùn)行。 所有同步機(jī)制都應(yīng)遵守以下四準(zhǔn)則： (1) 空閑讓進(jìn)。 (2) 忙則等待。 (3) 有限等待。 (4) 讓權(quán)等待。當(dāng)自己不能進(jìn)入

33、臨界區(qū)時(shí)，立即釋放處理機(jī)。,2.3.2 信號(hào)量機(jī)制,1965年，荷蘭學(xué)者Dijkstra提出了信號(hào)量(Semaphores)機(jī)制，這是一種卓有成效的進(jìn)程同步機(jī)制?，F(xiàn)在信號(hào)量機(jī)制已被廣泛地應(yīng)用于進(jìn)程同步控制中。常用的信號(hào)量有： 整形信號(hào)量 記錄型信號(hào)量 AND型信號(hào)量 信號(hào)量集,1. 整型信號(hào)量,最初由Dijkstra把整型信號(hào)量定義為一個(gè)整型量S，用來(lái)表示資源個(gè)數(shù)。 除初始化外，該信號(hào)量只能通過(guò)兩個(gè)標(biāo)準(zhǔn)的原子操作wait(S)和signal(S)來(lái)訪問(wèn)。wait和signal操作可描述為： wait(S): while S0 do no-op S :=S-1; signal(S): S :=S

34、+1; 此種信號(hào)量機(jī)制并未遵守“讓權(quán)等待”準(zhǔn)則，而是讓進(jìn)程處于“忙等”狀態(tài)。 wait(S)和signal(S)操作一直被分別稱為P和V操作。 P和V分別是荷蘭語(yǔ)Passeren和Verhoog的頭一個(gè)字母，相當(dāng)于英文的pass和increment的意思。,2. 記錄型信號(hào)量,記錄型信號(hào)量是因?yàn)椴捎糜涗浶蛿?shù)據(jù)結(jié)構(gòu)而得名的。其定義如下： type semaphore=record value：integer; L：list of process; end 其中：value代表資源數(shù)量，L用于鏈接等待使用資源的進(jìn)程。,記錄型信號(hào)量的操作,procedure wait(S) var S: semap

35、hore; begin S.value : =S.value-1; if S.value0 then block(S.L) end procedure signal(S) var S: semaphore; begin S.value:=S.value+1; if S.value0 then wakeup(S.L); end,記錄型信號(hào)量的操作描述,該機(jī)制遵循了“讓權(quán)等待”準(zhǔn)則：S.value的初值表示系統(tǒng)中某類資源的數(shù)目，對(duì)它的每次wait操作，意味著進(jìn)程請(qǐng)求一個(gè)單位的該類資源；當(dāng)S.value0時(shí)，表示該類資源已分配完畢，因此進(jìn)程應(yīng)調(diào)用block原語(yǔ)，進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號(hào)

36、量鏈表S.L中。此時(shí)S.value的絕對(duì)值表示在該信號(hào)量鏈表中已阻塞進(jìn)程的數(shù)目。 對(duì)信號(hào)量的每次signal操作，表示執(zhí)行進(jìn)程釋放一個(gè)單位資源，之后若仍有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)量。,3. AND型信號(hào)量,引例：進(jìn)程間的互斥是針對(duì)各進(jìn)程共享某一個(gè)臨界資源造成的。但也可能會(huì)出現(xiàn)，某些進(jìn)程需要多個(gè)臨界資源才能工作的例子。 設(shè)有A、B進(jìn)程，共享臨界資源D、E，且D、E同時(shí)得到后才能滿足工作條件。 解：設(shè)臨

37、界資源的D、E的信號(hào)量分別為Dmutex和Emutex，初始值均為1，若A、B分別對(duì)Dmutex和Emutex進(jìn)行以下操作： process A:| process B: wait(Dmutex);|wait(Emutex); wait(Emutex);|wait(Dmutex);,若進(jìn)程A和B按下述次序交替執(zhí)行wait操作： process A: wait(Dmutex); 于是Dmutex=0 process B: wait(Emutex); 于是Emutex=0 process A: wait(Emutex); 于是Emutex=-1 A阻塞 process B: wait(Dmutex

38、); 于是Dmutex=-1 B阻塞 最后，進(jìn)程A、B處于僵持狀態(tài)，在無(wú)外力作用下，兩者都無(wú)法推進(jìn)。此時(shí)我們稱進(jìn)程A、B進(jìn)入了死鎖狀態(tài)。,死鎖的概念,所謂死鎖，是指各并發(fā)進(jìn)程彼此互相等待對(duì)方所擁有的資源，且這些并發(fā)進(jìn)程在得到對(duì)方的資源之前不會(huì)釋放自己所擁有的資源。從而造成大家都想得到資源而又都得不到資源，各并發(fā)進(jìn)程不能繼續(xù)向前推進(jìn)的狀態(tài)。 如圖是兩個(gè)進(jìn)程發(fā)生死鎖時(shí)的例子。,AND同步機(jī)制的基本思想,將進(jìn)程在整個(gè)運(yùn)行過(guò)程中需要的所有資源，一次性全部地分配給進(jìn)程，待進(jìn)程使用完后再一起釋放。只要尚有一個(gè)資源未能分配給進(jìn)程，其它所有可能為之分配的資源，也不分配給他。 對(duì)若干個(gè)臨界資源的分配，采取原子操

39、作方式：要么全部分配到進(jìn)程，要么一個(gè)也不分配。 在wait操作中，增加了一個(gè)“AND”條件，故稱為AND同步，或稱為同時(shí)wait操作， 即Swait（Simultaneous wait）。,Swait的定義,Swait(S1, S2, , Sn) if Si1 and and Sn1 then for i:= 1 to n do Si:= Si-1; endfor else 將使第一個(gè)Si1的進(jìn)程送入等待隊(duì)列，并將進(jìn)程的程序計(jì)數(shù)設(shè)為Swait的開(kāi)始。 endif Ssignal(S1, S2, , Sn) for i : = 1 to n do Si := Si+1; 將所有與Si相關(guān)的等待隊(duì)

40、列的進(jìn)程送入就緒隊(duì)列 endfor,4. 信號(hào)量集,記錄信號(hào)量只能做+1或-1運(yùn)算，當(dāng)一次需要多個(gè)資源時(shí)，可能要進(jìn)行多次操作。有時(shí)對(duì)資源還有一個(gè)低限要求，當(dāng)?shù)陀谧钕奘蔷筒辉S再分配了。因此在每次分配之前，要檢查以上兩個(gè)因素?；诖耍梢詫?duì)AND信號(hào)量機(jī)制加以擴(kuò)充，形成一般化的信號(hào)量集機(jī)制。 設(shè)S為信號(hào)量，d為需要量，t為下限。Swait和Ssignal可以描述為：,Swait(S1, t1, d1, , Sn, tn, dn) if Sit1 and and Sntn then for i=1 to n do Si=Si-di; endfor else 將使第一個(gè)Siti的進(jìn)程送入等待隊(duì)列，并將

41、進(jìn)程的程序計(jì)數(shù)設(shè)為Swait的開(kāi)始。 endif; Ssignal(S1, d1, , Sn, dn) for i =1 to n do Si =Si+di; 將所有與Si相關(guān)的等待隊(duì)列的進(jìn)程送入就緒隊(duì)列 endfor;,一般“信號(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)量。 (3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號(hào)量操作。當(dāng)S1時(shí)，允許多個(gè)進(jìn)程進(jìn)入某特

42、定區(qū)；當(dāng)S變?yōu)?后，將阻止任何進(jìn)程進(jìn)入特定區(qū)。換言之，它相當(dāng)于一個(gè)可控開(kāi)關(guān)。,2.3.3 信號(hào)量的應(yīng)用,利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥 利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系,1. 利用信號(hào)量實(shí)現(xiàn)進(jìn)程互斥,為了實(shí)現(xiàn)多個(gè)進(jìn)程對(duì)臨界資源的互斥使用，只須為資源設(shè)置一互斥信號(hào)量mutex，并將其初始為1，然后將各進(jìn)程訪問(wèn)該資源的臨界區(qū)置于wait(mutex)和signal(mutex)之間就可以了。 在利用信號(hào)量處理互斥時(shí)應(yīng)注意： wait(mutex)和signal(mutex)必須成對(duì)出現(xiàn)； 缺少wait(mutex)，不能保證互斥訪問(wèn)； 缺少signal(mutex)，將導(dǎo)致臨界資源永遠(yuǎn)不被釋放。,框架性示例,Var

43、 mutex:semaphore := 1;/初始化信號(hào)量 begin parbegin process1: begin repeat wait(mutex);/申請(qǐng)資源 critical section signal(mutex);/釋放資源 remainder seetion until false; end parend,2. 利用信號(hào)量實(shí)現(xiàn)前趨關(guān)系,設(shè)有兩個(gè)進(jìn)程P1和P2，P1中有語(yǔ)句S1，P2中有語(yǔ)句S2。我們希望在S1執(zhí)行后再執(zhí)行S2。 為了實(shí)現(xiàn)這種前趨關(guān)系，可以為P1、P2設(shè)置公用信號(hào)量S，并將其初值賦為0。 將signal(S)放在S1的后面，將wait(S)放置在S2的前面。

44、即 在P1中：S1；signal(S)； 在P2中：wait(S) ；S2； 由于S被初始化為0，當(dāng)P2先執(zhí)行到wait(S);S2時(shí)必定被阻塞，只有當(dāng)P1先執(zhí)行完S1;signal(S);時(shí)S的值才變?yōu)?，相當(dāng)于釋放了資源，從而S2才能得到執(zhí)行。,示例,Var a,b,c,d,e,f,gsemaphore = 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);

45、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,2.3.4 管 程 機(jī) 制,信號(hào)量機(jī)制是一種方便、有效的同步機(jī)制，但是每個(gè)要訪問(wèn)臨界資源的進(jìn)程必須自備同步操作wait(S)和singal(S)。這就使得大量的同步機(jī)制分散在各進(jìn)程中，不僅給系統(tǒng)帶來(lái)了管理的麻煩，而且也可能造成死鎖。 于是就出現(xiàn)將這些分散在各進(jìn)程中的同步機(jī)制，統(tǒng)管進(jìn)來(lái)的措施管程。,2.5.1 管程的基本概念,1. 管程的定義（

46、Hansan） 一個(gè)管程定義了一個(gè)數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進(jìn)程所執(zhí)行（在該數(shù)據(jù)結(jié)構(gòu)上）的一組操作，這組操作能同步進(jìn)程和改變管程中的數(shù)據(jù)。 管程由三部分組成： 局部于管程的共享變量說(shuō)明。 對(duì)該數(shù)據(jù)結(jié)構(gòu)進(jìn)行操作的一組過(guò)程。 對(duì)局部于管程的數(shù)據(jù)設(shè)置初始值的語(yǔ)句。 管程內(nèi)部的條件變量。 此外，還須為管程賦予一個(gè)名字。,管程的示意圖,管程的示意圖,管程對(duì)進(jìn)程互斥的實(shí)現(xiàn),局部于管程的數(shù)據(jù)結(jié)構(gòu)只被局限于管程的過(guò)程訪問(wèn)；反過(guò)來(lái)，局部于管程的過(guò)程也只能訪問(wèn)管程內(nèi)的數(shù)據(jù)結(jié)構(gòu)。 管程相當(dāng)一個(gè)圍墻，把共享變量和對(duì)它進(jìn)行操作的若干過(guò)程圍起來(lái)，所有進(jìn)程要訪問(wèn)臨界資源時(shí)，都必須經(jīng)過(guò)管程（允許）才能進(jìn)入，而管程每次只能允許一個(gè)進(jìn)程

47、進(jìn)入，從而實(shí)現(xiàn)了進(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,2. 條件變量,在對(duì)共享資源進(jìn)行互斥訪問(wèn)時(shí)，會(huì)造成進(jìn)程的等待。造成等待的因素是多方面的，為了區(qū)分它們，需要引入條件變量。 管程中對(duì)每個(gè)條件變量，都須予以說(shuō)明，其

48、形式為：Var x, y：condition。該變量應(yīng)置于wait和signal之前，即可表示為x.wait和x.signal。 x.signal與signal操作是不同的： 前者的作用是啟動(dòng)一個(gè)被阻塞的進(jìn)程，當(dāng)沒(méi)有進(jìn)程被阻塞時(shí)，則不產(chǎn)生任何作用。而后者總是執(zhí)行s:=s+1，因而總會(huì)改變信號(hào)量的狀態(tài)。,如果有進(jìn)程Q處于阻塞狀態(tài)， 當(dāng)進(jìn)程P執(zhí)行了x.signal操作后，怎樣決定由哪個(gè)進(jìn)行執(zhí)行，哪個(gè)等待呢？可采用下述兩種方式之一進(jìn)行處理： (1) P等待，直至Q離開(kāi)管程或等待另一條件。 (2) Q等待，直至P離開(kāi)管程或等待另一條件。 采用哪種處理方式， 當(dāng)然是各執(zhí)一詞。 但是Hansan卻采用了第

49、一種處理方式。,2.4 經(jīng)典的進(jìn)程同步問(wèn)題,生產(chǎn)者消費(fèi)者問(wèn)題 哲學(xué)家進(jìn)餐問(wèn)題 讀者-寫(xiě)者問(wèn)題,2.4.1 生產(chǎn)者消費(fèi)者問(wèn)題,利用記錄型信號(hào)量 利用AND信號(hào)量,1. 利用記錄型信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題,設(shè)公用緩沖池中有n個(gè)緩沖區(qū)，可利用互斥信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖池的互斥使用；利用信號(hào)量empty和full分別表示緩沖池中空緩沖區(qū)和滿緩沖區(qū)的數(shù)量。變量定義如下： Var mutex, empty, full:semaphore=1，n，0; buffer：array0, , n-1 of item; in, out：integer=0, 0;,生產(chǎn)者,proceducer：begin

50、 repeat producer an item nextp; wait(empty); wait(mutex); buffer(in)= nextp; in= (in+1) mod n; signal(mutex); signal(full); until false; end,消費(fèi)者,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 fals

51、e; end,生產(chǎn)者消費(fèi)者問(wèn)題的注意事項(xiàng),首先，在每個(gè)程序中用于實(shí)現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對(duì)地出現(xiàn)； 其次，對(duì)資源信號(hào)量empty和full的wait和signal操作，同樣需要成對(duì)地出現(xiàn)，但它們分別處于不同的程序中。例如，wait(empty)在生產(chǎn)者進(jìn)程中，而signal(empty)則在消費(fèi)者進(jìn)程中； 最后，在每個(gè)程序中的多個(gè)wait操作順序不能顛倒。應(yīng)先執(zhí)行對(duì)資源信號(hào)量的wait操作，然后再執(zhí)行對(duì)互斥信號(hào)量的wait操作，否則可能引起進(jìn)程死鎖。,2. 利用AND信號(hào)量解決生產(chǎn)者消費(fèi)者問(wèn)題,在記錄型信號(hào)量的基礎(chǔ)上，也可以通過(guò)AND信號(hào)量解決生產(chǎn)者消

52、費(fèi)者問(wèn)題。 具體做法是將wait(empty)；wait(mutex);用Swait(empty, mutex)代替；將signal(mutex)；signal(full);用Ssignal(mutex, full);來(lái)代替， 變量定義同前。,生產(chǎn)者,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,消費(fèi)者,consumer：begin repeat Swai

53、t(full, mutex); nextc= buffer(out); out= (out+1) mod n; Ssignal(mutex, empty); consumer the item in nextc; until false; end,3. 利用管程解決生產(chǎn)者-消費(fèi)者問(wèn)題,首先為其建立一個(gè)管程，并命名為PC。其中包括兩個(gè)過(guò)程： (1) put(item)過(guò)程。生產(chǎn)者利用該過(guò)程將自己生產(chǎn)的產(chǎn)品投放到緩沖池中，并用整型變量count來(lái)表示在緩沖池中已有的產(chǎn)品數(shù)目，當(dāng)countn時(shí)， 表示緩沖池已滿， 生產(chǎn)者須等待。 (2) get(item)過(guò)程。消費(fèi)者利用該過(guò)程從緩沖池中取出一個(gè)產(chǎn)品

54、，當(dāng)count0時(shí)，表示緩沖池中已空， 消費(fèi)者應(yīng)等待。,變量聲明,type PC=monitor var in，out，count：integer; buffer：array0,n-1 of item; notfull, notempty：condition; 初始化 begin in= out= 0；count = 0 end,put(item),procedure entry put(item) begin if countn then notfull.wait; buffer(in)= nextp; in= (in+1) mod n; count= count+1; if notempt

55、y.queue then notempty.signal; end,get(item),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,利用管程解決生產(chǎn)者-消費(fèi)者問(wèn)題,producer:begin repeat produce an item in nextp; PC.put(item); until false; end

56、consumer:begin repeat PC.get(item); consume the item in nextc; until false; end,2.4.2 哲學(xué)家進(jìn)餐問(wèn)題,設(shè)有5個(gè)哲學(xué)家，共享一張放有五把椅子的桌子，每人分得一把椅子。但是，桌子上，總共只有5支筷子，在每人兩邊分開(kāi)各放一支。哲學(xué)家們?cè)陴囸I時(shí)才試圖分兩次從兩邊拾起筷子就餐。條件: (1)只有拿到兩支筷子時(shí)，哲學(xué)家才能吃飯。 (2)如果筷子已在他人手上，則該哲學(xué)家必須等待到他人吃完之后才能拿到筷子。 (3)任一哲學(xué)家在自己未拿到兩支筷子吃飯之前，決不放下自己手中的筷子。 試解決以下問(wèn)題： (1)描述一個(gè)保證不會(huì)出現(xiàn)兩

57、個(gè)鄰座同時(shí)要求吃飯的算法。 (2)描述一個(gè)既沒(méi)有兩鄰座同時(shí)吃飯，又沒(méi)有人餓死(永遠(yuǎn)拿不到筷子)的算法。,問(wèn)題(1)分析,桌子上的筷子為臨界資源，每根筷子在任一時(shí)刻只能個(gè)人使用?？蔀槊扛曜釉O(shè)置一個(gè)信號(hào)量，五根筷子的信號(hào)量就構(gòu)成信號(hào)量數(shù)組。 定義變量： Var chopstick: array0, , 4 of semaphore; 初始化：每個(gè)變量初始化為1. 規(guī)定：每個(gè)哲學(xué)家總是先拿左邊的，拿到后再拿右邊的。放筷子時(shí)也按此順序。,第i位哲學(xué)家的進(jìn)餐描述,repeat wait(chopsticki); wait(chopstick(i+1) mod 5); eat; signal(chops

58、ticki); signal(chopstick(i+1) mod 5); until false; 注：此算法不能解決每個(gè)人只拿到一根筷子，則出現(xiàn)的死鎖問(wèn)題，從而導(dǎo)致有人會(huì)被餓死。,問(wèn)題(2)或沒(méi)有死鎖問(wèn)題的解,可采取以下幾種解決方法： 至多只允許有四位哲學(xué)家同時(shí)去拿左邊的筷子，最終能保證至少有一位能夠進(jìn)餐，并在用畢時(shí)能釋放他用過(guò)的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。 僅當(dāng)哲學(xué)家的左、右兩只筷子均可用時(shí)，才允許他拿起筷子進(jìn)餐。 規(guī)定奇數(shù)號(hào)哲學(xué)家先拿他左邊的筷子，然后再去拿右邊的筷子；而偶數(shù)號(hào)哲學(xué)家則相反。當(dāng)然也可以奇數(shù)人先拿右邊，而偶數(shù)數(shù)先拿左邊的筷子。,針對(duì)的解,repeat if i mod 2=0 then wait(chopsticki; wait(chopstick(i+1)mod 5); eat; signal(chopsticki); signal(chopstick(i+1) mod 5); else wait(chopstick(i+1) mod 5);wait(chopsticki) eat signal(chopstick(i+1)mod 5); signal(chopsticki); until