中南大學(xué)操作系統(tǒng) 第二講 進程管理

1、第2章 進程(jnchng)管理 2.1 進程的基本概念2.2 進程控制2.3 進程同步2.4 經(jīng)典進程同步問題2.5 管程機制 實現(xiàn)互斥的軟件機制和硬件機制(補充(bchng)2.6 進程通信2.7 線程第一次課內(nèi)上機實驗1共二百二十四頁2.1 進程(jnchng)的基本概念程序的順序執(zhí)行及其特征(tzhng)程序的并發(fā)執(zhí)行及其特征進程的特征與狀態(tài)進程控制塊2共二百二十四頁2.1.1 程序(chngx)的順序執(zhí)行及其特征程序(chngx)的順序執(zhí)行僅當(dāng)前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作。例如，在進行計算時，總須先輸入用戶的程序和數(shù)據(jù)，然后進行計算，最后才能打印計算結(jié)果。 S1: a

2、=x+y; S2: b=a-5; S3: c=b+1;3共二百二十四頁2.1.1 程序的順序執(zhí)行(zhxng)及其特征順序執(zhí)行包含(bohn)兩層含義：對于多個用戶程序來說，所有程序是依次執(zhí)行的。（外部順序性） 對于一個程序來說，它的所有指令是按序執(zhí)行的。（內(nèi)部順序性）4共二百二十四頁程序順序(shnx)執(zhí)行的特征 （1）順序(shnx)性： 處理機的操作嚴格按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在下一操作開始之前結(jié)束（或者說下一操作必須在當(dāng)前操作結(jié)束后才能開始）。 （2）封閉性： 程序是在封閉的環(huán)境下執(zhí)行的。即程序運行時獨占全機資源，資源的狀態(tài)（除初始態(tài)外）只有本程序才能改變它。程序一旦開

3、始執(zhí)行，其執(zhí)行結(jié)果不受外界影響。 （3）可再現(xiàn)性： 只要程序執(zhí)行時的環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時，都將獲得相同的結(jié)果。 5共二百二十四頁程序的并發(fā)執(zhí)行(zhxng)包括兩層含義： 對于一個程序來說，它的所有(suyu)指令是按序執(zhí)行的。（內(nèi)部順序性） 對于多個程序（進程）來說，所有進程是交叉執(zhí)行的。（外部并發(fā)性） 2.1.3 程序的并發(fā)執(zhí)行及其特征 6共二百二十四頁前趨圖 前趨圖(Precedence Graph)是一個有向無循環(huán)圖，記為DAG(Directed Acyclic Graph)，用于描述(mio sh)進程之間執(zhí)行的前后關(guān)系。圖中的每個結(jié)點可用于描述(mio sh)一個程

4、序段或進程，乃至一條語句；結(jié)點間的有向邊則用于表示兩個結(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)。7共二百二十四頁前趨圖 每個結(jié)點(ji din)還具有一個重量(Weight)，用于表示該結(jié)點(ji din)所含有的程序量或結(jié)點

5、(ji din)的執(zhí)行時間。 IiCiPi和S1S2S3 8共二百二十四頁前趨圖對于(duy)圖 2-2(a)所示的前趨圖， 存在下述前趨關(guān)系： P1P2, P1P3, P1P4, P2P5, P3P5, P4P6, P4P7, P5P8, P6P8, P7P9, P8P9或表示(biosh)為： 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)注

6、意，前趨圖中必須不存在循環(huán)，但在圖2-2(b)中卻有著下述的前趨關(guān)系：S2S3, S3S2 9共二百二十四頁前趨圖 前趨圖(Precedence Graph)是一個有向無循環(huán)圖，記為DAG(Directed Acyclic Graph)，用于描述進程(jnchng)之間執(zhí)行的前后關(guān)系。圖中的每個結(jié)點可用于描述一個程序段或進程(jnchng)，乃至一條語句；結(jié)點間的有向邊則用于表示兩個結(jié)點之間存在的偏序(Partial Order)或前趨關(guān)系(Precedence Relation)“”。 =(Pi, Pj)|Pi must complete before Pj may start, 如果(Pi

7、, Pj),可寫成PiPj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。在前趨圖中，把沒有前趨的結(jié)點稱為初始結(jié)點(Initial Node)，把沒有后繼的結(jié)點稱為終止結(jié)點(Final Node)。10共二百二十四頁2.1.3 程序的并發(fā)(bngf)執(zhí)行及其特征 圖 2-3 并發(fā)(bngf)執(zhí)行時的前趨圖 11共二百二十四頁2.1.3 程序(chngx)的并發(fā)執(zhí)行及其特征 在該例中存在下述前趨關(guān)系： IiCi，IiIi+1, CiPi, CiCi+1，PiPi+1而Ii+1和Ci及Pi-1是重迭(zhn di)的，亦即在Pi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行。 對于具有下述四條語句的

8、程序段： S1: a=x+2 S2: b=y+4 S3: c=a+b S4: d=c+b 12共二百二十四頁1）間斷性: 程序在并發(fā)執(zhí)行時，由于它們(t men)共享系統(tǒng)資源，以及為完成同一任務(wù)而相互合作，致使這些并發(fā)執(zhí)行的程序之間形成了相互制約的關(guān)系。（互斥關(guān)系、同步關(guān)系） 相互制約導(dǎo)致并發(fā)執(zhí)行(zhxng)的程序具有“執(zhí)行暫停執(zhí)行”這種間斷性活動規(guī)律。 2）失去封閉性： 程序在并發(fā)執(zhí)行時，由于多個程序共享系統(tǒng)資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運行已失去了封閉性。 某程序的執(zhí)行時，會受到其他程序的影響。 13共二百二十四頁3）不可(bk)再現(xiàn)性與時間有關(guān)的錯誤 程序在并發(fā)

9、執(zhí)行時，由于失去了封閉性，也將導(dǎo)致其失去可再現(xiàn)性。例如：有兩個循環(huán)(xnhun)程序A和B，它們共享一個變量NL1：N = N+1； goto L1； L2：print (N)； N = 0； goto L2； 程序A程序B程序A和B并發(fā)執(zhí)行時，可能出現(xiàn)下述三種情況(設(shè)N的值為10)：(1) N=N+1在print(N)和N=0之前，此時得到的N值分別為11,11,0。(2) N=N+1在print(N)和N=0之后，此時得到的N值分別為10,0,1。(3) N=N+1在print(N)和N=0之間，此時得到的N值分別為10,11,0。 上述三種情況中，(1)、(2)結(jié)果正確，(3)結(jié)果出錯。

10、可見計算結(jié)果已與并發(fā)程序的執(zhí)行速度(推進速度)有關(guān)，從而使程序執(zhí)行失去了可再現(xiàn)性。 14共二百二十四頁2.1.4 進程(jnchng)的特征與狀態(tài)1進程的定義(dngy)和特征 進程是程序在一個數(shù)據(jù)集上的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。 (傳統(tǒng)OS的定義)定義(1) 進程是程序的一次執(zhí)行。(2) 進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。(3)進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位”。 其他15共二百二十四頁為了描述(mio sh)和控制進程的運行，系統(tǒng)為每個進程定義了一個數(shù)據(jù)結(jié)構(gòu)進程控制塊。進程控制塊是進程實體的一部分，是操作系統(tǒng)中最

11、重要的記錄型數(shù)據(jù)結(jié)構(gòu)。 1. PCB作用(zuyng)： 使一個在多道程序環(huán)境下不能獨立運行的程序(含數(shù)據(jù))，成為一個能獨立運行的基本單位，一個能與其它進程并發(fā)執(zhí)行的進程?；蛘哒f，OS是根據(jù)PCB來對并發(fā)進程進行控制和管理的。 例如：進程調(diào)度；現(xiàn)場保護和恢復(fù)；進程同步和通信。PCB是進程存在的唯一標志2.1.5 進程控制塊（PCB） 16共二百二十四頁2進程控制(kngzh)塊中的信息 PCB中記錄了操作系統(tǒng)所需的、用于描述進程當(dāng)前情況以及控制進程運行(ynxng)的全部信息。具體包括下述四方面的信息： 1）進程標識符： 內(nèi)部標識符(進程號)；外部標識符(名)；父進程標識及子進程標識；用戶標識

12、 2）處理機狀態(tài)：處理機狀態(tài)信息主要由處理機的各種寄存器中的內(nèi)容組成的。寄存器包括：通用寄存器、指令計數(shù)器、程序狀態(tài)字（PSW）寄存器、用戶棧指針。(保護、恢復(fù)現(xiàn)場)當(dāng)處理機被中斷時，這些信息都必須保存到PCB中，以便該進程重新執(zhí)行時，能從斷點繼續(xù)執(zhí)行。 17共二百二十四頁3）進程(jnchng)調(diào)度信息：在PCB中還存放一些與進程調(diào)度和進程對換(du hun)有關(guān)的信息。包括： 進程狀態(tài)作為調(diào)度和對換時的依據(jù)。 進程優(yōu)先級由于描述進程使用處理機的優(yōu)先級別的一個整數(shù)，優(yōu)先級高的進程優(yōu)先獲得處理機。 進程調(diào)度所需的其它信息它們與所采用的進程調(diào)度算法有關(guān)。 事件即阻塞原因。 18共二百二十四頁4）

13、進程(jnchng)控制信息： 程序和數(shù)據(jù)的地址指程序和數(shù)據(jù)所在的內(nèi)存或外存首地址； 進程同步和通信機制如信號量、消息隊列指針等，它們可能全部或部分地存放在PCB中； 資源清單是一張列出了除CPU外的、進程所需的全部資源及已經(jīng)分配到該進程的資源的清單； 鏈接(lin ji)指針它給出本進程（PCB）所在隊列中下一個進程的PCB的首址。 19共二百二十四頁3進程控制(kngzh)塊的組織方式 常用(chn yn)的組織方式有兩種：鏈接方式和索引方式。 1）鏈接方式 把具有同一狀態(tài)的PCB，用其中的鏈接字鏈接成一個隊列。形成：就緒隊列、阻塞隊列、空白隊列等 20共二百二十四頁2）索引(suyn)方

14、式: 系統(tǒng)根據(jù)所有進程的狀態(tài)建立幾張索引(suyn)表。如， 就緒索引表 阻塞索引表等 索引表的首址記錄在專用單元中；每個索引表的表目中，記錄具有相應(yīng)狀態(tài)的某個PCB的首址。 21共二百二十四頁2.1.4 進程(jnchng)的特征與狀態(tài)1進程(jnchng)的特征1）結(jié)構(gòu)特征： 程序段、相關(guān)的數(shù)據(jù)段、PCB三部分構(gòu)成了進程實體。 2）動態(tài)性：進程的實質(zhì)是進程實體的一次執(zhí)行過程，故動態(tài)性是進程的最基本特征。 22共二百二十四頁4）獨立性 ：在傳統(tǒng)的OS中，獨立性是指進程實體是一個能獨立運行、獨立分配資源和獨立接受(jishu)調(diào)度的基本單位。 5）異步性 ：是指進程按各自獨立的、不可預(yù)知的速度

15、(sd)向前推進，或說進程實體按異步方式運行。 3）并發(fā)性：這是指多個進程實體同存于內(nèi)存中，且能在一段時間內(nèi)同時運行。 23共二百二十四頁進程(jnchng)的三種基本狀態(tài)： 1）就緒(jix)（Ready）狀態(tài)： 當(dāng)進程已分配到除CPU以外的所有資源后，只要再獲得CPU，便可立即執(zhí)行，進程這時的狀態(tài)稱為就緒狀態(tài)。 2）執(zhí)行（Running）狀態(tài): 進程已獲得CPU，其程序正在執(zhí)行。 3）阻塞（Blocked）狀態(tài): 正在執(zhí)行的進程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機而處于暫停狀態(tài)，亦即進程的執(zhí)行受到阻塞，把這種暫停狀態(tài)稱為阻塞狀態(tài)（或等待狀態(tài)）。 24共二百二十四頁進程的三種(s

16、n zhn)基本狀態(tài)的轉(zhuǎn)換：進程調(diào)度(diod)：就緒態(tài)執(zhí)行態(tài)時間片完：執(zhí)行態(tài)就緒態(tài) 請求I/O：執(zhí)行態(tài)阻塞態(tài) I/O完成：阻塞態(tài)就緒態(tài) 引起進程狀態(tài)轉(zhuǎn)換的典型事件：25共二百二十四頁掛起狀態(tài)(zhungti)：有些系統(tǒng)(xtng)除了進程的三種基本狀態(tài)外，還有掛起狀態(tài)。1）引入掛起狀態(tài)的原因： （1）終端用戶的請求： （2）父進程請求：（3）負荷調(diào)節(jié)的需要 ： （4）操作系統(tǒng)的需要 ： 當(dāng)終端用戶在自己的程序運行期間發(fā)現(xiàn)有可疑問題時，希望暫停執(zhí)行。希望考察和修改子進程，或協(xié)調(diào)各子進程間的活動時實時系統(tǒng)中工作負荷較重時，系統(tǒng)可把一些不重要的進程掛起。操作系統(tǒng)有時希望掛起某些進程，以便檢查運行中

17、的資源使用情況或進行記賬。26共二百二十四頁2）具有掛起狀態(tài)系統(tǒng)(xtng)的進程狀態(tài)的轉(zhuǎn)換 活動(hu dng)就緒靜止就緒 活動阻塞靜止阻塞 靜止就緒活動就緒 靜止阻塞活動阻塞掛起原語Suspend激活原語Active27共二百二十四頁創(chuàng)建(chungjin)狀態(tài)創(chuàng)建一個進程一般包括兩個(lin )步驟： 1)為一個新進程創(chuàng)建PCB,并填寫必要的管理信息。2）把該進程轉(zhuǎn)入就緒狀態(tài)并插入到就緒隊列中。 當(dāng)一個新進程被創(chuàng)建時，系統(tǒng)已經(jīng)為其分配了PCB,填寫了進程標識等信息，但是由于該進程所必須的資源或其他信息如主存資源等尚未分配，此時的進程已經(jīng)擁有了自己的PCB,但進程自身還未進入主存，即進程

18、創(chuàng)建工作尚未完成，進程不能被調(diào)度執(zhí)行，其所處的狀態(tài)就是創(chuàng)建狀態(tài)。28共二百二十四頁終止(zhngzh)狀態(tài)終止一個進程一般包括(boku)兩個步驟： 當(dāng)一個進程到達了自然結(jié)束點，或是出現(xiàn)了無法克服的錯誤，或是被操作系統(tǒng)所終結(jié)，或是被其他有終止權(quán)的進程所終結(jié)，它將進入終止狀態(tài)。 進入終止狀態(tài)的進程以后不能執(zhí)行，但在操作系統(tǒng)中依然保留一個記錄，其中保存狀態(tài)碼和一些計時統(tǒng)計數(shù)據(jù)，供其他進程收集。一旦其他進程完成了對終止狀態(tài)進程的信息提取之后，操作系統(tǒng)將刪除該進程。1) 回收資源2）刪除PCB 29共二百二十四頁終止(zhngzh)狀態(tài)圖2-2 具有創(chuàng)建(chungjin)、終止和掛起狀態(tài)的進程狀態(tài)圖

19、 30共二百二十四頁2.2 進程(jnchng)控制進程控制是進程管理中最基本的功能。 進程控制包括： 創(chuàng)建(chungjin)進程 終止進程 進程狀態(tài)轉(zhuǎn)換 進程控制是由OS的內(nèi)核完成的。 31共二百二十四頁2.2.1 進程(jnchng)的創(chuàng)建1引起創(chuàng)建進程(jnchng)的事件 用戶登錄 作業(yè)調(diào)度 提供服務(wù)當(dāng)用戶進程提出某種請求后，系統(tǒng)將專門創(chuàng)建一個進程來提供用戶所需的服務(wù)。如，文件打印。 上述三種情況，都是由系統(tǒng)內(nèi)核為它創(chuàng)建一個新進程。 應(yīng)用請求： 是基于應(yīng)用進程的需求，由應(yīng)用進程自己創(chuàng)建一個新進程，以便新進程以并發(fā)運行方式完成特定任務(wù)。 32共二百二十四頁2.2.1 進程(jnchng

20、)的創(chuàng)建圖 2-4 進程(jnchng)樹 33共二百二十四頁2進程(jnchng)的創(chuàng)建 調(diào)用進程創(chuàng)建原語Create（），按下述步驟(bzhu)創(chuàng)建一個進程： （1）申請空白PCB；（2）為新進程分配資源。主要是內(nèi)存空間。 （3）初始化PCB。包括： 初始化標識信息 初始化處理機狀態(tài)信息：程序計數(shù)器，堆棧指針等進程狀態(tài)就緒或靜止就緒、優(yōu)先級等。初始化處理機控制信息：（4）將新進程插入就緒隊列。 34共二百二十四頁1引起(ynq)進程終止的事件 正常(zhngchng)結(jié)束外界干預(yù) 越界錯誤 保護錯試圖訪問不允許訪問的資源或文件，或者以不適當(dāng)方式訪問 非法指令 特權(quán)指令錯用戶程序試圖執(zhí)行只允

21、許OS執(zhí)行的指令運行超時 等待超時算術(shù)運算錯被0除 I/O故障 操作員或操作系統(tǒng)干 預(yù)（如發(fā)生死鎖） 父進程請求 父進程終止 2.2.2 進程的終止異常結(jié)束 常見的異常 結(jié)束事件35共二百二十四頁2進程的終止(zhngzh)過程 OS調(diào)用(dioyng)終止原語，按下述過程終止進程：根據(jù)被終止進程的標識，從PCB集合中找除該進程的PCB，讀出該進程狀態(tài)。若被終止進程正處于執(zhí)行狀態(tài)，應(yīng)立即終止其執(zhí)行，并置調(diào)度標志為真，用于指示該進程被終止后應(yīng)重新進行調(diào)度。若該進程還有子孫進程，應(yīng)將其所有子孫進程終止，以防止它們成為不可控進程。將被終止進程的所有資源，或者歸還給其父進程，或者歸還給系統(tǒng)。將被終止進

22、程（它的PCB）從所在隊列中移出，等待其他進程來搜索信息。 36共二百二十四頁2.2.2 進程的阻塞(zs)和喚醒1引起(ynq)進程阻塞和喚醒的事件 請求系統(tǒng)服務(wù)無新工作可做 當(dāng)執(zhí)行進程請求OS服務(wù)時，由于某種原因，OS并不立即滿足該進程的請求時，該進程只能轉(zhuǎn)變?yōu)樽枞麪顟B(tài)來等待。如，進程請求打印機， 系統(tǒng)往往設(shè)置一些具有特定功能的系統(tǒng)進程，每當(dāng)這種進程完成任務(wù)后，便把自己阻塞起來以等待新任務(wù)到來。如，系統(tǒng)中發(fā)送數(shù)據(jù)的進程， 啟動某種操作 當(dāng)進程啟動某種操作后，如果該進程必須在該操作完成后才能繼續(xù)執(zhí)行，則必須先使該進程阻塞，以等待操作完成。如，啟動了某I/O設(shè)備， 新數(shù)據(jù)尚未到達 對于相互合作

23、的進程，如果其中一個進程需要獲得另一個（合作）進程提供的數(shù)據(jù)才能運行以對數(shù)據(jù)進行處理，則只要其所需數(shù)據(jù)尚未到達，該進程只有阻塞（等待）。如， 37共二百二十四頁2進程阻塞(zs)過程 調(diào)用阻塞原語block把自己阻塞。（主動(zhdng)行為） 阻塞（block）過程： 立即停止執(zhí)行；把PCB中進程狀態(tài)由“執(zhí)行”改為“阻塞”； 將PCB插入具有相同事件的阻塞隊列； 轉(zhuǎn)進程調(diào)度程序，將處理機分配給某個就緒進程，并進行進程切換保留被阻塞進程的處理機狀態(tài)（在PCB中），再按新進程的PCB中處理機狀態(tài)設(shè)置CPU的環(huán)境。 38共二百二十四頁3進程(jnchng)喚醒過程 調(diào)用喚醒(hunxng)原語wa

24、keup( )，將等待事件的進程喚醒。 喚醒原語執(zhí)行過程： 將被喚醒進程的PCB從阻塞隊列移出； 將其PCB中進程狀態(tài)由“阻塞”改為“就緒”； 將改PCB插入到就緒隊列中。block（）和wakeup（）是成對的。 39共二百二十四頁1進程(jnchng)的掛起 當(dāng)出現(xiàn)了引起進程掛起的事件時(用戶進程請求將自己(zj)掛起，或父進程請求將子進程掛起)，系統(tǒng)將用掛起原語suspend( )將指定進程或處于阻塞狀態(tài)的進程掛起。 掛起原語的執(zhí)行過程： 檢查被掛起進程的狀態(tài)： 若處于活動就緒或執(zhí)行狀態(tài)，則將其轉(zhuǎn)為靜止就緒；若處于活動阻塞,則將其轉(zhuǎn)為靜止阻塞 把該進程的PCB復(fù)制到某指定內(nèi)存區(qū)域 為方便

25、用戶或父進程考查該進程的運行狀態(tài)。 若該進程正在執(zhí)行，則轉(zhuǎn)進程調(diào)度程序重新調(diào)度。 2.2.4 進程的掛起和激活40共二百二十四頁2進程(jnchng)的激活 當(dāng)發(fā)生激活進程(jnchng)的事件時(如父進程(jnchng)或用戶請求激活指定進程(jnchng)，而內(nèi)存中已有足夠空間時)，系統(tǒng)利用激活原語active( )將指定進程激活。 激活過程是： 將進程從外存調(diào)入內(nèi)存； 若是靜止就緒，則改為活動就緒； 若是靜止阻塞，則改為活動阻塞。 若采用的是搶占式調(diào)度策略，則應(yīng)檢查被激活就緒進程的優(yōu)先級，若其優(yōu)先級比先行執(zhí)行進程高，則應(yīng)將處理機分配給被激活進程。 檢查該進程現(xiàn)行狀態(tài)： 41共二百二十四頁

26、2.3 進程同步由于進程的異步性，尤其是它們競爭臨界資源(zyun)時，可能會給系統(tǒng)造成混亂。進程同步的主要任務(wù)，是使并發(fā)執(zhí)行的進程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。 2.3.1 進程同步的基本概念2.3.2 信號量機制(jzh)2.3.3 信號量的應(yīng)用42共二百二十四頁2.3.1 進程同步的基本概念1兩種形式的制約(zhyu)關(guān)系 （1）間接制約(zhyu)關(guān)系 間接制約關(guān)系源于資源共享。如，共享打印機。 進程互斥（2）直接制約關(guān)系 源于進程間的合作。如， 進程同步2臨界資源 在一段時間內(nèi)只允許一個進程訪問的資源，即僅當(dāng)一個進程訪問完并釋放該資源后，才允許另一個進

27、程訪問的資源，稱為臨界資源或獨占資源。 如，打印機、磁帶機、共享變量、隊列、 43共二百二十四頁生產(chǎn)者-消費者問題(wnt)【例】生產(chǎn)者-消費者問題(wnt)著名的進程同步問題 共享變量：臨界資源循環(huán)緩沖區(qū)生產(chǎn)者投放一個產(chǎn)品后，輸入指針in加1：in = ( in + 1 ) % n （n是緩沖區(qū)個數(shù)，整型常量），in初值為0； 消費者每取出一個產(chǎn)品，輸出指針out加1：out = ( out + 1 ) % n，out初值為0； 引入一個共享變量counter,初值為0。生產(chǎn)者投放一個產(chǎn)品，counter加1，counter = n時不能再投放產(chǎn)品 消費者每取一個產(chǎn)品，counter減1，c

28、ounter = 0時不能再取出產(chǎn)品 前面交通觀察站例子亦然。以下是軟件臨界資源的例子。44共二百二十四頁process producer：while （condition） produce an item in nextp；while(counter=n) no-op；/no-op表示(biosh)空操作bufferin = nextp；in = (in + 1)% n ；counter = counter + 1 ；生產(chǎn)者進程(jnchng)算法如下：45共二百二十四頁process consumer：struct item nextc ；while （condition） while （

29、counter = 0）no-op ；nextc = bufferout ；out = （out + 1）% n ；counter = counter 1 ；consume the item in nextc ；消費者進程算法(sun f)如下：46共二百二十四頁上面的生產(chǎn)者程序和消費者程序，在順序執(zhí)行時其結(jié)果是正確的。但若并發(fā)執(zhí)行時，可能會出現(xiàn)差錯，問題在于(ziy)這兩個進程共享變量counter。生產(chǎn)者做counter=counter+1操作，消費者做counter= counter-1操作，這兩個操作在機器語言實現(xiàn)時，?？捎孟旅娴男问矫枋觯?生產(chǎn)者執(zhí)行(zhxng)的操作： regis

30、ter1 = counter ； register1 = register1 + 1; counter = register1； 消費者執(zhí)行的操作： register2 = counter ； register2 = register2 - 1 ； counter = register2； 47共二百二十四頁假設(shè)某一時刻counter的值為5，生產(chǎn)者和消費者同時對counter操作，按下述順序(shnx)執(zhí)行： register1 = counter; (生產(chǎn)者取得counter的當(dāng)前(dngqin)值為5) register1 = register1 + 1; (生產(chǎn)者將該值增1變?yōu)?)re

31、gister2 = counter; (消費者取得counter的當(dāng)前值為5)register2 = register2 1; (消費者將該值減1變?yōu)?)counter = register2; (消費者保存counter的新值4)counter = register1; (生產(chǎn)者保存counter的新值6)最終counter的值為6，正確的值應(yīng)是5，出現(xiàn)了差錯。學(xué)生考慮：什么情況會出現(xiàn)counter最終值為4的情況。 解決此問題的關(guān)鍵，是應(yīng)將變量counter作為臨界資源處理，亦即讓生產(chǎn)者進程和消費者進程互斥地訪問變量counter。48共二百二十四頁2.3.1 進程同步的基本概念3臨界(l

32、n ji)區(qū)（critical section） 每個進程(jnchng)中訪問臨界資源的那段代碼稱為臨界區(qū)。 不論是硬件臨界資源，還是軟件臨界資源，多個進程必須互斥地對它們訪問。 顯然，若能保證諸進程互斥地進入自己的臨界區(qū)，便可實現(xiàn)諸進程對臨界區(qū)的互斥訪問。為此，每個進程在進入臨界區(qū)之前，應(yīng)先對欲訪問的臨界資源進行檢查，看是否正被訪問，如果此刻該資源未被訪問，便可進入臨界區(qū)對該臨界資源進行訪問，并設(shè)置它正被訪問的標志；如果此刻它正被訪問，則本進程不能進入臨界區(qū)。 定義：進程互斥的定義：進程互斥不允許兩個或兩個以上進程同時訪問同一個臨界資源。進程互斥不允許兩個或兩個以上進程同時進入相關(guān)臨界區(qū)。

33、49共二百二十四頁因此必須在臨界區(qū)前增加一段用于上述檢查的代碼，把這段代碼稱為進入(jnr)區(qū)(entry section)相應(yīng)地，在臨界區(qū)后面也要加上一段稱為退出區(qū)(exit section)的代碼，用于將臨界區(qū)正被訪問的標志恢復(fù)為未被訪問的標志。 repeat非臨界區(qū)進入(jnr)區(qū)臨界區(qū)退出區(qū)非臨界區(qū)until false一般結(jié)構(gòu)“進入?yún)^(qū)”和“退出區(qū)”的不同構(gòu)成方法，形成了各種不同的同步機制。50共二百二十四頁4同步機制(jzh)應(yīng)遵循的原則 為了實現(xiàn)各進程互斥地進入自己的臨界區(qū)，一般是在系統(tǒng)中設(shè)置(shzh)專門的同步機制來協(xié)調(diào)各進程間的運行。 我們把異步環(huán)境下的一組并發(fā)進程因直接制約

34、而互相發(fā)送消息、進行互相合作、互相等待，使得各進程按一定的速度執(zhí)行的過程稱為進程間的同步。具有同步關(guān)系的一組并發(fā)進程稱為合作進程，合作進程間互相發(fā)送的信號稱為消息或事件。 51共二百二十四頁4同步(tngb)機制應(yīng)遵循的原則 所有同步機制都應(yīng)遵循(zn xn)如下四條準則： 空閑讓進當(dāng)無進程處于臨界區(qū)時，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個請求進入臨界區(qū)的進程立即進入自己的臨界區(qū)，以便有效地利用臨界資源?？臻e讓進、忙則等待、有限等待、讓權(quán)等待。52共二百二十四頁有限(yuxin)等待讓權(quán)等待(dngdi)對要求訪問臨界資源的進程，應(yīng)保證在有限的時間內(nèi)能進入自己的臨界區(qū)，以免陷入“死鎖”狀態(tài)。不

35、死等。不互相阻塞。當(dāng)進程不能進入自己的臨界區(qū)時，應(yīng)立即釋放處理機，以免進程陷入“忙等”。不忙碌等待。忙則等待當(dāng)已有進程進入臨界區(qū)時，表明臨界資源正在被訪問，因而其他試圖進入臨界區(qū)的進程必須等待，以保證對臨界資源的互斥訪問。53共二百二十四頁2.3.2 信號量機制(jzh)信號量(Semaphores)機制是一種卓有成效(zhu yu chng xio)的進程同步工具。信號量機制已被廣泛應(yīng)用于單處理機和多處理機系統(tǒng)以及計算機網(wǎng)絡(luò)中。 信號量機制的發(fā)展：整型信號量 記錄型信號量 AND型信號量 信號量集 (重點介紹) 54共二百二十四頁1、整型信號量 最初由Dijkstra把整型信號量定義為一個整

36、型量，除初始化外，僅能通過兩個標準(biozhn)的原子操作(Atomic Operation) wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為P、V操作。 wait和signal操作可描述為： wait(S): while S0 do no-op S:=S-1;signal(S): S:=S+1;55共二百二十四頁1、整型信號量 最初由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標準的原子(yunz)操作(Atomic Operation) wait(S)和signal(S)來訪問。這兩個操作一直被分別稱為P、V操作。 wait和signal操作

37、可描述為： wait(S): while S0 do no-op S:=S-1;signal(S): S:=S+1;56共二百二十四頁process producer：while （condition） produce an item in nextp；while(counter=n) no-op；/no-op表示(biosh)空操作bufferin = nextp；in = (in + 1)% n ； wait(s); counter = counter + 1 ； signal(s);生產(chǎn)者進程算法如下(rxi)(加入整型信號量）：57共二百二十四頁process consumer：str

38、uct item nextc ；while （condition） while （counter = 0）no-op ；nextc = bufferout ；out = （out + 1）% n ；wait(s); counter = counter 1 ； signal(s);consume the item in nextc ；消費者進程(jnchng)算法如下（加入整型信號量）：58共二百二十四頁1、整型信號量 最初(zuch)由Dijkstra把整型信號量定義為一個整型量，除初始化外，僅能通過兩個標準的原子操作(Atomic Operation) wait(S)和signal(S)來訪

39、問。這兩個操作一直被分別稱為P、V操作。 wait和signal操作可描述為： wait(S): while S0 do no-op S:=S-1;signal(S): S:=S+1;“忙等”，未遵循(zn xn)“讓權(quán)等待”準則59共二百二十四頁2、記錄(jl)型信號量 需要一個用于代表臨界資源數(shù)目的整型變量value；還要一個在該資源上阻塞的隊列（鏈表）指針L。故信號量應(yīng)采用(ciyng)記錄型（C語言中為結(jié)構(gòu)型）的結(jié)構(gòu)： struct semaphore int value ； struct semphore *L ； ； 記錄型信號量的結(jié)構(gòu)定義信號量除初始化外，只能通過兩個原子操作(稱

40、為原語)wait(S)和signal(S)來訪問。它們以前被稱為P、V操作。下頁介紹wait和signal操作。 60共二百二十四頁wait和signal操作可用C/C+語言(yyn)描述如下：void wait( semaphore S) S.value = S.value 1 ; if (S.value 0 ) block (S.L ) ; /* 讓權(quán)等待(dngdi) */ void signal (semaphore S ) S.value = S.value + 1 ;if ( S.value = 0 ) wakeup ( S.L ) ; /*喚醒第一個等待的進程 */ P(S)V(

41、S)S.value的初值表示系統(tǒng)中某類資源的數(shù)目。 61共二百二十四頁wait和signal操作的物理(wl)意義：對信號量S的每次wait操作，意味著進程請求一個該類臨界資源，因此描述為S.value=S.value-1；當(dāng)S.value=1 & . & Sn=1 then for i=1 to n doSi=Si-1; else 進程進入第一個滿足Si=t1 & . & Sn=tn then for i=1 to n doSi=Si-di; else 進程進入第一個遇到的滿足Siti條件的Si信號 量隊列等待，同時(tngsh)將該進程的程序計數(shù)器地 址回退，置為Swait操作處。Ssig

42、nal(S1,d1,S2,d2,.,Sn,dn) for i=1 to n do Si=Si+di; 從所有Si等待隊列中移出進程并置入就緒隊列。66共二百二十四頁4、信號量集一般“信號量集”的幾種特殊情況： (1) Swait(S, d, d)。 此時在信號量集中只有一個(y )信號量S， 但允許它每次申請d個資源，當(dāng)現(xiàn)有資源數(shù)少于d時，不予分配。 (2) Swait(S, 1, 1)。 此時的信號量集已蛻化為一般的記錄型信號量(S1時)或互斥信號量(S=1時)。 (3) Swait(S, 1, 0)。這是一種很特殊且很有用的信號量操作。當(dāng)S1時，允許多個進程進入某特定區(qū)；當(dāng)S變?yōu)?后，將阻

43、止任何進程進入特定區(qū)。換言之，它相當(dāng)于一個可控開關(guān)。 67共二百二十四頁2.3.3 信號量的應(yīng)用(yngyng)1利用信號量實現(xiàn)(shxin)進程互斥 方法要點： 為每個臨界資源設(shè)置一個互斥信號量mutex，其初值為1； 各進程訪問該資源前執(zhí)行wait(mutex)操作，離開臨界區(qū)時執(zhí)行signal (mutex)操作。 請看下頁的例子 非臨界區(qū) wait(mutex) /進入?yún)^(qū) 臨界區(qū) signal(mutex) /退出區(qū) 非臨界區(qū)68共二百二十四頁利用(lyng)信號量實現(xiàn)進程互斥的簡單例子某交通路口設(shè)置了一個自動(zdng)計數(shù)系統(tǒng)，該系統(tǒng)由“觀察者”進程和“報告者”進程組成。觀察者進程

44、能識別卡車，并對通過的卡車計數(shù)；報告者進程定時（可設(shè)為每隔1小時，準點時）將觀察者的計數(shù)值打印輸出，每次打印后把計數(shù)值清“0”。兩個進程的并發(fā)執(zhí)行可完成對每小時中卡車流量的統(tǒng)計。這兩個進程的功能如下： process observer while (condition) observe a lorry; wait（S）; count = count + 1; signal（S）; 臨界區(qū) process reporter wait（S）; print（count）; count = 0； signal（S）; 臨界區(qū)semaphore S ；int count = 0 ；S.value = 1

45、 ； 【注意】wait (S)和signal (S)必須成對出現(xiàn) 69共二百二十四頁利用信號量實現(xiàn)(shxin)前趨關(guān)系 【例】利用信號量，描述(mio sh)語句的前趨關(guān)系（見圖2-12）寫出一個可并發(fā)執(zhí)行的程序。圖中表示： 進程P1中有語句S1； 進程P2中有語句S2；P1執(zhí)行完應(yīng)通知P2、P3；P2得到通知后才開始執(zhí)行；P2執(zhí)行完應(yīng)通知P4、P5；語句S1執(zhí)行后才能執(zhí)行語句S2和語句S3；語句S2執(zhí)行后才能執(zhí)行語句S4和S5；語句S3、S4和S5執(zhí)行后，才能執(zhí)行語句S6。S1S2S3S4S5S6圖2-12 前趨圖舉例P1P2P3P4P5P670共二百二十四頁semaphore S12,S

46、13,S24,S25,S36,S46,S56;S12.value=S13.value=0;S24.value=S25.value=0;S36.value=S46.value=S56.value=0;程序描述(mio sh)如下：初始化parbegin / parbegin表示(biosh)并發(fā)執(zhí)行開始process P1： 執(zhí)行S1; signal(S12); signal(S13); process P2： wait(S12); 執(zhí)行S2; signal(S24); signal(S25); process P3： wait(S13); 執(zhí)行S3; signal(S36); process

47、P4： wait(S24); 執(zhí)行S4; signal(S46); process P5： wait(S25); 執(zhí)行S5; signal(S56); process P6： wait(S36); wait(S46); wait(S56); 執(zhí)行S6; parend / 用parend表示并發(fā)執(zhí)行結(jié)束71共二百二十四頁2.4 經(jīng)典(jngdin)進程同步問題 生產(chǎn)者-消費者問題(wnt) 讀者-寫者問題 哲學(xué)家進餐問題 在多道程序環(huán)境下，進程同步問題十分重要，引起了不少學(xué)者對它進行研究，由此產(chǎn)生了一系列經(jīng)典的進程同步問題，其中較有代表性的是：通過對這些問題的研究和學(xué)習(xí)，可以幫助我們更好地理解進

48、程同步概念及實現(xiàn)方法。72共二百二十四頁2.4.1 生產(chǎn)者-消費者問題(wnt) 前面已經(jīng)對生產(chǎn)者-消費者問題做了一些描述，但是未考慮進程的互斥和同步(tngb)問題，因而造成了共享變量counter的不確定性。 生產(chǎn)者-消費者問題是相互合作進程關(guān)系的一種抽象，例如，先介紹最簡單的P-C問題生產(chǎn)者-消費者問題從特殊到一般(從易到難)可以分3種形式：一個生產(chǎn)者、一個消費者、一個緩沖區(qū)的問題；一個生產(chǎn)者、一個消費者、n個緩沖區(qū)的問題； k個生產(chǎn)者、m個消費者、n個緩沖區(qū)的問題；73共二百二十四頁用信號量機制解決P-C問題的基本(jbn)方法：為生產(chǎn)者設(shè)置1個私有信號量empty，其初值為1，表示有

49、1個空緩沖區(qū)；為消費者設(shè)置1個私有信號量full，其初值為0，表示開始(kish)時沒有滿緩沖區(qū)；（信號量初值由物理意義確定）生產(chǎn)者將產(chǎn)品存入緩沖區(qū)之前，應(yīng)先測試緩沖區(qū)是否空：執(zhí)行wait(empty)操作；離開臨界區(qū)(存入產(chǎn)品)后，應(yīng)通知(可能會喚醒)消費者：執(zhí)行signal(full)操作；消費者從緩沖區(qū)取產(chǎn)品之前，應(yīng)先測試緩沖區(qū)是否滿：執(zhí)行wait(full)操作；離開臨界區(qū)(取走產(chǎn)品)后，應(yīng)通知(可能會喚醒)生產(chǎn)者：執(zhí)行signal(empty)操作74共二百二十四頁信號量機制解決(jiju)進程同步問題的一般方法：為同步雙方設(shè)置各自的信號量，初值為其初始狀態(tài)可用的資源數(shù)(故該信號量稱

50、為資源信號量或私有信號量)；同步雙方任一進程在進入臨界區(qū)之前，應(yīng)先對自己(zj)的信號量執(zhí)行wait()操作，以測試是否有自己可用的資源。若有資源可用，則進入臨界區(qū)，否則阻塞；同步雙方任一進程離開臨界區(qū)后，應(yīng)對合作方 (對方)的信號量執(zhí)行signal()操作，以通知(若對方處于阻塞狀態(tài)，則喚醒它)對方已有資源可用(對方已可進入臨界區(qū))。75共二百二十四頁最簡單(jindn)的生產(chǎn)者-消費者問題緩沖區(qū)PC一個(y )生產(chǎn)者、一個(y )消費者、一個(y )緩沖區(qū)的問題如右圖所示。當(dāng)緩沖區(qū)空時，生產(chǎn)者可將產(chǎn)品存入緩沖區(qū)；當(dāng)緩沖區(qū)滿時，生產(chǎn)者必須等待 (阻塞)，待消費者取走產(chǎn)品后將其喚醒后，才能將產(chǎn)

51、品存入。當(dāng)緩沖區(qū)滿時，消費者可從緩沖區(qū)取出產(chǎn)品進行消費；當(dāng)緩沖區(qū)空時，消費者必須等待(阻塞)，待生產(chǎn)者存入產(chǎn)品后將其喚醒后，才能再從緩沖區(qū)取產(chǎn)品。76共二百二十四頁最簡單(jindn)的生產(chǎn)者-消費者問題一個生產(chǎn)者、一個消費者、一個緩沖區(qū)的生產(chǎn)者-消費者問題的算法(sun f)描述如下所示：semaphore empty,full;empty=1;full=0;parbeginprocess Producer: . produce an item in nextp; wait(empty);/測試 buffer=nextp; signal(full);/通知消費者process Consume

52、r: wait(full); /測試 nextc=buffer; signal(empty); /通知 consume the item in nextc;parend77共二百二十四頁生產(chǎn)者-消費者問題的第二種特殊(tsh)情況一個(y )生產(chǎn)者、一個(y )消費者、n個緩沖區(qū)的P-C問題n-1543210PC循環(huán)緩沖區(qū)為生產(chǎn)者設(shè)置一個資源信號量empty，其初值為生產(chǎn)者的可用資源數(shù)(空緩沖區(qū)的個數(shù))n，即empty=n。為消費者設(shè)置一個資源信號量full，其初值為消費者的可用資源數(shù)(滿緩沖區(qū)的個數(shù))0，即full=0。empty=nfull=078共二百二十四頁semaphore empt

53、y,full;empty=n;full=0;int in=0,out=0; /下標parbeginprocess Producer: . produce an item in nextp; wait(empty);/測試(csh) bufferin=nextp; in=(in+1)%n; signal(full);/通知消費者與前不同(b tn)79共二百二十四頁process Consumer: wait(full); /測試(csh) nextc=bufferout; out=(out+1)%n; signal(empty); /通知 consume the item in nextc;p

54、arend本題中in和out不是共享變量(因為只有(zhyu)一個生產(chǎn)者和一個消費者)，無需互斥訪問。80共二百二十四頁生產(chǎn)者-消費者問題的一般(ybn)形式下面(xi mian)介紹生產(chǎn)者-消費者問題一般形式：k個生產(chǎn)者、m個消費者、n個緩沖區(qū)的問題。一般形式的生產(chǎn)者-消費者問題的圖示如下： 0 1 2 3 4 5 n-1P1P2P3PKC1C2C3Cm生產(chǎn)者消費者n個緩沖區(qū)的循環(huán)緩沖圖2-5 生產(chǎn)者-消費者問題示意圖81共二百二十四頁設(shè)置生產(chǎn)者的資源信號量empty，其初值為n，表示(biosh)開始時有n個空緩沖區(qū)；設(shè)置消費者的資源信號量full，其初值為0，表示開始時有0個滿緩沖區(qū)；只

55、要有空的緩沖區(qū)，生產(chǎn)者便可將消息送入緩沖區(qū)；只要有滿的緩沖區(qū)，消費者便可從緩沖區(qū)取走一個消息。用互斥信號量mutex對緩沖區(qū)(共享變量in和out)的互斥使用，互斥信號量mutex初值為1； 生產(chǎn)者用共享變量in作為下標訪問緩沖區(qū)，mutex為其互斥信號量；消費者用共享變量out作為下標訪問緩沖區(qū)，其互斥信號量也用mutex。82共二百二十四頁生產(chǎn)者-消費者問題(wnt)可描述如下： semaphore mutex,empty,full ;item buffern ;int in = 0，out = 0 ；mutex.value = 1;empty.value=n；full.value=0;初

56、始化83共二百二十四頁parbegin /并發(fā)執(zhí)行開始 process produceri (i=1,2,k) /生產(chǎn)者進程(jnchng) item nextp ； while (true) produce an item nextp； wait(empty) ;/測試 wait(mutex);/互斥 bufferin = nextp ； in = (in + 1)% n ； signal(mutex) ;/成對 signal(full) ;/交叉成對 臨界(ln ji)區(qū)84共二百二十四頁process consumerj (j=1,2,m） item nextc ； while (tru

57、e) wait(full); wait(mutex); nextc = bufferout ； out = (out + 1)% n ； signal(mutex); signal(empty); consume the item in nextc ; parend /并發(fā)(bngf)執(zhí)行結(jié)束 臨界(ln ji)區(qū)85共二百二十四頁在每個進程中，實現(xiàn)互斥的wait(mutex)和signal(mutex)必須成對出現(xiàn)；對資源信號量empty和full的wait和signal操作也要成對地出現(xiàn)，但它們處于不同的進程中(交叉成對)。 在每個進程中的多個wait操作順序不能顛倒，應(yīng)先執(zhí)行對資源信號量

58、（也稱私有(syu)信號量）的wait操作，然后執(zhí)行對互斥信號量（公有信號量）的wait操作，否則可能引起進程死鎖。(Why?) 注意(zh y)：86共二百二十四頁重申信號量解決(jiju)同步問題的要點：為同步雙方設(shè)置各自的信號量，初值為其初始狀態(tài)可用的資源數(shù)(故該信號量稱為資源信號量或私有信號量)；同步雙方任一進程在進入(jnr)臨界區(qū)之前，應(yīng)先對自己的信號量執(zhí)行wait()操作，以測試是否有自己可用的資源。若有資源可用，則進入臨界區(qū)，否則阻塞；同步雙方任一進程離開臨界區(qū)后，應(yīng)對合作方 (對方)的信號量執(zhí)行signal()操作，以通知(若對方處于阻塞狀態(tài)，則喚醒它)對方已有資源可用(對方

59、已可進入臨界區(qū))。87共二百二十四頁2.4.2 哲學(xué)家進餐(jn cn)問題Dijkstra提出并解決(jiju)的哲學(xué)家就餐問題是經(jīng)典的進程同步問題。哲學(xué)家就餐問題描述如下： 有5個哲學(xué)家共用一張圓桌，分別坐在周圍的5張椅子上，在圓桌上有5個碗和5只筷子，他們的生活方式是交替地進行思考和進餐。平時，每個哲學(xué)家進行思考，饑餓時便試圖拿起其左右最靠近他的筷子，只有在他拿到兩只筷子時才能進餐。進餐完畢，放下筷子繼續(xù)思考。圖2-7是其示意圖。 P0P1P2P3P4f4f0f1f2f3圖2-7 哲學(xué)家進餐問題88共二百二十四頁利用記錄型信號量解決(jiju)哲學(xué)家進餐問題 桌子上的筷子f0，f1，f4

60、是臨界資源，應(yīng)互斥使用，可用一個信號量表示一只筷子，5只筷子的5個信號量構(gòu)成(guchng)信號量數(shù)組，所有信號量的初值均為1。 semaphore chopstick5 ；chopstick0.value=chopstick1.value=1;chopstick2.value=chopstick3.value=1 ;chopstick4.value=1 ; 初始化每個哲學(xué)家算法流程為(1) 拿起左、右筷子；(2) 吃面條；(3) 放下左、右筷子；(4) 思考問題；(5) 返回(1)。89共二百二十四頁哲學(xué)家Pi(i=0,1,2,3,4)的活動(hu dng)可描述如下： parbeginpr