第2章

1、第二章進第二章進 程程 管管 理理12.1進程的基本概念進程的基本概念 2.2進程控制進程控制 2.3進程同步進程同步 2.4經(jīng)典進程的同步問題經(jīng)典進程的同步問題 2.5 進程通信進程通信 2.6線程線程 22.1進程的基本概念進程的基本概念 一、程序的順序執(zhí)行及其特征1. 程序的順序執(zhí)行3順序執(zhí)行：順序執(zhí)行：一個應(yīng)用程序一個應(yīng)用程序分成若干個程序段，在各程序段之間，必須按照某種先后次序順序執(zhí)行，僅當前一操作(程序段)執(zhí)行完后，才能執(zhí)行后繼操作?；蜃鳂I(yè)之間的順序性。例：程序的三部分：輸入操作（I），計算操作（C）， 打印操作（P）程序的執(zhí)行過程：I C P作業(yè)執(zhí)行順序性 ： I1 C1 P1

2、I2 C2 P24語句的順序性：S1: a:=x+y；S2: b:=a-5；S3: c:=b+1； 其中：S1、S2、S2為語句標號 “：= ”：賦值運算符 語句的執(zhí)行過程：S1S2 S22. 程序順序執(zhí)行時的特征程序順序執(zhí)行時的特征(1)順序性每一操作（或作業(yè)）必須在上一個操作結(jié)束之后開始。5(2) 封閉性程序是在封閉的環(huán)境下執(zhí)行的，即程序運行時獨占全機資源，資源的狀態(tài)(除初始狀態(tài)外)只有本程序才能改變它。程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界因素影響。(3) 可再現(xiàn)性只要程序執(zhí)行時的環(huán)境和初始條件相同，當程序重復(fù)執(zhí)行時，不論它是從頭到尾不停頓地執(zhí)行，還是“停停走走”地執(zhí)行，都將獲得相同的結(jié)果

3、。二、前趨圖二、前趨圖 （重點）（重點）：前趨圖是一個有向無循環(huán)圖，記為DAG，用于描述進程之間執(zhí)行的前后關(guān)系。6前趨圖的組成：結(jié)點、有向邊“”結(jié)點：描述一條語句或一個程序段或進程有向邊“”：表示兩個結(jié)點之間存在的偏序(偏序關(guān)系)或前趨關(guān)系說明：l前趨關(guān)系的表示=(Pi，Pj)|Pi must complete before Pj may startl(Pi，Pj)或PiPj，稱Pi是Pj的直接前趨，而稱Pj是Pi的直接后繼。l初始結(jié)點：沒有前趨的結(jié)點l終止結(jié)點：沒有后繼的結(jié)點l重量：每個結(jié)點還具有一個重量，用于表示該結(jié)點所含有的程序量或結(jié)點的執(zhí)行時間。78(a ) 程序的順序執(zhí)行(b ) 三

4、條語句的順序執(zhí)行I1C1P1I2C2P2S1S2S3P34圖 2-1程序的順序執(zhí)行 (a)、(b )圖即為前趨圖，描述如下前趨關(guān)系： 圖（a）的前趨關(guān)系:IiCiPi 圖（b）的前趨關(guān)系:S1S2S3 9P1P3P8P9P4P2P5P6P7S1S2S3(a) 具有九個結(jié)點的前趨圖(b) 具有循環(huán)的圖例：根據(jù)前趨圖寫出前趨關(guān)系前趨圖中不能存在循環(huán)，該圖為錯誤的。初始結(jié)點終止結(jié)點圖(a)的前趨關(guān)系：注意按結(jié)點的順序依次寫出前趨關(guān)系，以免有遺漏。P1P2，P1P3，P1P4，P2P5，P3P5，P4P6，P4P7，P5P8，P6P8，P7P9，P8P910或表示為：結(jié)點集合+前趨關(guān)系集合P=P1，P

5、2，P3，P4，P5，P6，P7，P8，P9 （結(jié)點集合）=(P1，P2)，(P1，P3)，(P1，P4)，(P2，P5)，(P3，P5)，(P4，P6)，(P4，P7)，(P5，P8)，(P6，P8)，(P7，P9)，(P8，P9) （前趨關(guān)系集合）三、程序的并發(fā)執(zhí)行及其特征三、程序的并發(fā)執(zhí)行及其特征1程序的并發(fā)執(zhí)行分析程序運行過程中使用的系統(tǒng)設(shè)備： 輸入I: 輸入設(shè)備計算操作C： CPU 輸出P: 輸出設(shè)備可以并發(fā)執(zhí)行的情況？1112P1P2P3P4I1I2I3I4C1C2C3C4輸入 例：4個作業(yè)并發(fā)執(zhí)行的前趨圖 P36圖2-3 輸入計算輸入計算輸出輸入計算輸出計算輸出輸出：設(shè)備使用的順

6、序性 ：作業(yè)自身的順序性并發(fā)執(zhí)行？l前趨關(guān)系一般地： IiCi ， IiIi+1 一般地： CiCi+1 ，CiPi， 一般地： PiPi+1 lPi-1和Ci以及Ii+1之間，可以并發(fā)執(zhí)行13例：四條語句的程序段如下S1: a:=x+2S2: b:=y+4S3: c:=a+bS4: d:=c+b 14S1S2S3S4四條語句的前趨關(guān)系： P81 習(xí)題2前趨圖 2 2程序并發(fā)執(zhí)行時的特征程序并發(fā)執(zhí)行時的特征（1）間斷性由于對資源的共享，并發(fā)執(zhí)行的程序之間，形成了相互制約的關(guān)系，這種相互制約導(dǎo)致了并發(fā)程序具有“執(zhí)行暫停執(zhí)行”這種間斷性的活動規(guī)律（2）失去封閉性程序不是在封閉的環(huán)境下執(zhí)行的，即程序

7、運行時不再獨占全機資源，資源的狀態(tài)(除初始狀態(tài)外)并非本程序才能改變它。程序執(zhí)行過程中，其執(zhí)行結(jié)果受外界因素影響。15（3） 不可再現(xiàn)性程序在并發(fā)執(zhí)行時，由于失去了封閉性，也將導(dǎo)致其失去可再現(xiàn)性。例：有兩個循環(huán)程序A和B，它們共享一個變量N。假設(shè)初值為n。 程序A： 程序B N:=N+1操作 Print(N) N:=0 16N:=N+1在Print(N)和N:=0之前，N值分別為n+1，n+1，0。（程序A先改變N的值，程序B再使用） N:=N+1在Print(N)和N:=0之后，N的值分別為n，0，1。（程序B先使用N，程序A再使用） N:=N+1在Print(N)和N:=0之間，此時得到的

8、N值分別為n，n+1，0。（程序A、B交叉使用N。）程序在并發(fā)執(zhí)行時，由于失去了封閉性，使程序的執(zhí)行失去了可再現(xiàn)性，雖然它們執(zhí)行時的環(huán)境和初始條件相同，但得到的結(jié)果卻各不相同。 四、進程的特征與狀態(tài)四、進程的特征與狀態(tài)1、進程的特征和定義 （4個特征） 進程的組成：（3部分） 程序、數(shù)據(jù)、PCB（進程控制塊） 進程控制塊（PCB）的作用： 記錄進程的屬性信息，以便OS對進程進行控制管理。 說明：創(chuàng)建進程，實質(zhì)上是創(chuàng)建進程實體中的PCB；而撤消進程，實質(zhì)上是撤消進程的PCB。PCB 隨進程的 產(chǎn)生而產(chǎn)生，隨進程的撤銷而撤銷。l特征1動態(tài)性 進程是具有一定獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活

9、動。它可創(chuàng)建，可調(diào)度執(zhí)行，可以撤消而消亡。進程實體有一定的生命期。 17l特征2并發(fā)性 多個進程實體同存于內(nèi)存中，且能在一段時間內(nèi)同時運行。也是操作系統(tǒng)中引入進程的目的。l特征2獨立性 在傳統(tǒng)的OS中，獨立性是指進程實體是一個能獨立運行、獨立分配資源和獨立接受調(diào)度的基本單位。凡未建立PCB的程序都不能作為一個獨立的單位參與運行。在現(xiàn)代操作系統(tǒng)中引入了線程，獨立接受調(diào)度的基本單位是線程。l特征2異步性 指進程按各自獨立的、 不可預(yù)知的速度運行，或說進程實體按異步方式運行。18關(guān)于進程的幾種定義：（1）進程是程序的一次執(zhí)行。（2）進程是一個程序及其數(shù)據(jù)在處理機上順序執(zhí)行時所發(fā)生的活動。（3）進程是

10、程序在一個數(shù)據(jù)集合上運行的過程，它是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。（4）進程是具有一定獨立功能的程序關(guān)于某個數(shù)據(jù)集合的一次運行活動。 (補充)19進程的定義：P382. 2. 進程的三種基本狀態(tài)進程的三種基本狀態(tài) （重點）（重點）l執(zhí)行（運行）狀態(tài) 進程正在處理器上運行。l就緒狀態(tài) 進程獲得了除處理器外一切資源。l阻塞（等待或封鎖）狀態(tài) 進程正在等待某一事件的發(fā)生。說明：一個系統(tǒng)中處于就緒狀態(tài)、阻塞狀態(tài)的進程可能有多個，通常將它們排成一個隊列，形成就緒隊列、阻塞隊列。 2021就緒阻塞執(zhí)行時間片完進程調(diào)度I/O完成I/O請求進程的三種基本狀態(tài)轉(zhuǎn)換關(guān)系圖： 創(chuàng)建進程注意狀態(tài)之間的轉(zhuǎn)換和轉(zhuǎn)

11、換條件3. 3. 掛起狀態(tài)掛起狀態(tài)（1）引入掛起狀態(tài)的原因 （4方面）l終端用戶的請求 由于某些原因進程希望暫停運行。（如自檢、調(diào)試）l父進程請求 有時父進程希望掛起自己的某個子進程，以便考查和修改該子進程，或者協(xié)調(diào)各子進程間的活動。22進程之間的關(guān)系樹型結(jié)構(gòu)祖先進程：原始進程 祖先進程父進程：子進程：族系：注：進程只能由父進程創(chuàng)建，不能自生自滅。當子進程創(chuàng)建時子進程繼承父進程所擁有的資源；當子進程撤消時將從父進程那里繼承的資源歸還給父進程。23l負荷調(diào)節(jié)的需要負荷調(diào)節(jié)的需要 當實時系統(tǒng)中的工作負荷較重，已可能影響到當實時系統(tǒng)中的工作負荷較重，已可能影響到對實時任務(wù)的控制時，可由系統(tǒng)把一些不重

12、要對實時任務(wù)的控制時，可由系統(tǒng)把一些不重要的進程掛起，以保證系統(tǒng)能正常運行。的進程掛起，以保證系統(tǒng)能正常運行。l操作系統(tǒng)的需要操作系統(tǒng)的需要 操作系統(tǒng)有時希望掛起某些進程，以便檢查運操作系統(tǒng)有時希望掛起某些進程，以便檢查運行中的資源使用情況或進行記賬。行中的資源使用情況或進行記賬。24綜上：綜上：由于某些原因進程希望暫停運行由于某些原因進程希望暫停運行掛起掛起 待問題解決后，再恢復(fù)進程的原來狀態(tài)待問題解決后，再恢復(fù)進程的原來狀態(tài)解除掛起解除掛起說明：進入掛起狀態(tài)的進程并非不具備當前的狀態(tài)要求。 如：排隊買飯。每個同學(xué)為一個就緒的進程。25活動就緒靜止就緒執(zhí)行掛起激活釋放掛起活動阻塞靜止阻塞掛起

13、激活釋放請求I/O調(diào)度具有掛起狀態(tài)的進程狀態(tài)圖 4創(chuàng)建狀態(tài)和終止狀態(tài)l創(chuàng)建狀態(tài) 創(chuàng)建一個進程一般要通過兩個步驟：首先，為一個新進程創(chuàng)建PCB，并填寫必要的管理信息；其次，把該進程轉(zhuǎn)入就緒狀態(tài)并插入就緒隊列之中。 引入創(chuàng)建狀態(tài)，是為了保證進程的調(diào)度必須在創(chuàng)建工作完成后進行，處于創(chuàng)建狀態(tài)的進程，獲得了其所必需的資源，以及對其PCB初始化工作完成后，進程狀態(tài)便可由創(chuàng)建狀態(tài)轉(zhuǎn)入就緒狀態(tài)。 26l 終止狀態(tài) 進程的終止通過兩個步驟：首先等待操作系統(tǒng)進行善后處理（如監(jiān)督程序的作用），然后將其PCB清零，并將PCB空間返還系統(tǒng)。 什么時候進入終止狀態(tài)？ 自然結(jié)束、出現(xiàn)了無法克服的錯誤、被操作系統(tǒng)所終結(jié)、被其

14、他有終止權(quán)的進程所終結(jié)。27進入終止態(tài)的進程以后不能再執(zhí)行，若需要運行須重新創(chuàng)建。28創(chuàng)建就緒阻塞執(zhí)行終止許可I/O請求釋放I/O完成時間片完進程調(diào)度含有創(chuàng)建狀態(tài)和終止狀態(tài)的五種狀態(tài)轉(zhuǎn)換關(guān)系圖：29創(chuàng)建終止執(zhí)行活動就緒活動阻塞靜止阻塞靜止就緒許可許可請求I/O釋放激活掛起釋放掛起激活掛起釋放具有創(chuàng)建、終止和掛起狀態(tài)的進程狀態(tài)具有創(chuàng)建、終止和掛起狀態(tài)的進程狀態(tài)轉(zhuǎn)換關(guān)系圖：轉(zhuǎn)換關(guān)系圖： （了解）（了解）進程五狀態(tài)轉(zhuǎn)換，需要增加考慮的問題：P40 自讀內(nèi)容30五、進程控制塊1進程控制塊的作用進程控制塊是什么？ 31進程控制塊PCB(Process Control Block)是一種數(shù)據(jù)結(jié)構(gòu)，它是進程

15、實體的一部分。PCB中記錄了操作系統(tǒng)所需的、用于描述進程的當前情況以及控制進程運行的全部信息。進程控制塊的作用：記錄進程的屬性信息，OS根據(jù)PCB對并發(fā)執(zhí)行的進程進行控制和管理的。注意：lPCB隨進程的創(chuàng)建而建立，隨進程的撤消而消失。lPCB唯一標識著進程，它標識著進程的存在。322 2進程控制塊中的信息進程控制塊中的信息（1）進程標識符（2）處理機狀態(tài)（3）進程調(diào)度信息（4）進程控制信息33（1）進程標識符用于唯一地標識一個進程。一個進程通常有兩種標識符：l內(nèi)部標識符 在所有的操作系統(tǒng)中，都為每一個進程賦予了一個唯一的數(shù)字標識符，通常是一個進程的序號。設(shè)置內(nèi)部標識符主要是為了方便系統(tǒng)使用。l

16、外部標識符 它由創(chuàng)建者提供，通常是由字母、數(shù)字組成，往往是由用戶(進程)在訪問該進程時使用。34（2）處理機狀態(tài)35處理機狀態(tài)信息主要是由處理機的各種寄存器中的內(nèi)容組成的。處理機在運行時，許多信息都放在寄存器中。當處理機被中斷時，所有這些信息都必須保存在PCB中，以便在該進程重新執(zhí)行時，能從斷點繼續(xù)執(zhí)行。（3）進程調(diào)度信息 進程狀態(tài)，指明進程的當前狀態(tài) 進程優(yōu)先級 進程調(diào)度所需的其它信息，如進程已等待CPU的時間總和、進程已執(zhí)行的時間總和等； 事件（阻塞原因）（4）進程控制信息36 程序和數(shù)據(jù)的地址 進程同步和通信機制； 資源清單 鏈接指針3. 3. 進程控制塊的組織方式進程控制塊的組織方式l

17、鏈接方式 l索引方式37把具有同一狀態(tài)的PCB，用其中的鏈接字鏈接成一個隊列。形成的隊列有就緒隊列、若干個阻塞隊列（根據(jù)阻塞的原因）和空白隊列等。PCB14PCB2PCB3PCB4PCB5PCB6PCB7PCB8PCB93087901執(zhí)行指針就緒隊列指針阻塞隊列指針空閑隊列指針不同隊列的頭指針各個隊列l(wèi)索引方式 根據(jù)所有進程的狀態(tài)建立幾張索引表。這樣就形成了就緒索引表、阻塞索引表等，每個索引表的表目，記錄具有相應(yīng)狀態(tài)的某個進程PCB在PCB表中的地址。38執(zhí)行指針就緒索引表PCB1PCB2PCB3PCB4PCB5PCB6PCB7阻塞索引表就緒表指針阻塞表指針PCB表索引表記錄：進程標識及PCB

18、在PCB表中的地址2.2進程控制進程控制 39DEFGBCIJKMALH進程之間的關(guān)系樹型結(jié)構(gòu)（進程圖）注：圖的構(gòu)成進程只能由父進 程創(chuàng)建，不能自 生自滅。1 1引起創(chuàng)建進程的事件引起創(chuàng)建進程的事件在多道程序環(huán)境中，只有進程才能在系統(tǒng)中運行。因此，為使程序運行，就必須為它創(chuàng)建進程。何時需要創(chuàng)建進程？（1）用戶登錄在分時系統(tǒng)中，用戶在終端鍵入登錄命令后，如果是合法用戶，系統(tǒng)將為該終端建立一個進程，并把它插入就緒隊列中。40有4類事件發(fā)生時(2) 作業(yè)調(diào)度在批處理系統(tǒng)中，當作業(yè)調(diào)度程序按一定的算法調(diào)度到某作業(yè)時，便將該作業(yè)裝入內(nèi)存，為它分配必要的資源，并立即為它創(chuàng)建進程，再插入就緒隊列中。(3)

19、提供服務(wù)當運行中的用戶程序提出某種請求后，系統(tǒng)將專門創(chuàng)建一個進程來提供用戶所需要的服務(wù)，例如，用戶程序要求進行文件打印，操作系統(tǒng)將為它創(chuàng)建一個打印進程，這樣可使打印進程與該用戶進程并發(fā)執(zhí)行。41以上為系統(tǒng)內(nèi)核為用戶創(chuàng)建一個新進程的事件(4) 應(yīng)用請求則是基于應(yīng)用進程的需求，由它自己創(chuàng)建一個新進程（子進程），以便使新進程以并發(fā)運行方式完成特定任務(wù)。例如：某應(yīng)用程序需要不斷地從鍵盤終端輸入數(shù)據(jù)，繼而又要對輸入數(shù)據(jù)進行相應(yīng)的處理，然后，再將處理結(jié)果以表格形式在屏幕上顯示。該應(yīng)用進程為使這3個操作能并發(fā)執(zhí)行，以加速任務(wù)的完成，可以分別建立鍵盤輸入進程、處理進程、表格輸出進程。42創(chuàng)建一個新進程需要做哪

20、些工作？創(chuàng)建進程請求調(diào)用創(chuàng)建進程原語Creat()申請PCB、分配進程ID為進程分配資源初始化PCB將進程放進就緒隊列為新進程分配一個唯一的進程ID,并申請一個空白的PCB。為進程的程序代碼、數(shù)據(jù)用戶棧分配內(nèi)存空間。（1）將系統(tǒng)分配的進程ID、父進程ID寫入PCB。（2）將程序計數(shù)器指向程序的入口地址、棧指針指向棧頂。（3）設(shè)置進程狀態(tài)、優(yōu)先級等。2 2進程的創(chuàng)建進程的創(chuàng)建調(diào)用進程創(chuàng)建原語Creat( )創(chuàng)建一個進程。創(chuàng)建一個新進程需要完成的任務(wù)（創(chuàng)建過程）：43二、進程的終止二、進程的終止1引起進程終止的事件 （什么時候要終止一個進程呢？）l正常結(jié)束l異常結(jié)束（1）越界錯誤；（2）保護錯；

21、（3）特權(quán)指令；（4）非法指令；（5）運行超時；（6）等待超時；（7）算術(shù)溢出；（8）I/O故障；l外界干擾（1）OS/操作員終止；（2）父進程請求；（3）父進程終止。 44三大類事件引發(fā)進程的終止事件調(diào)用進程終止原語Destroy()從PCB集中檢索出該進程的PCB讀出進程的狀態(tài)在Running狀態(tài)：終止執(zhí)行、設(shè)置調(diào)度狀態(tài)為真。有子進程：終止所有的子孫進程。將進程擁有的資源歸還給父進程把對應(yīng)的PCB設(shè)成空2 2進程的終止過程進程的終止過程 OS調(diào)用進程終止原語Destroy()終止進程。45三、進程的阻塞與喚醒三、進程的阻塞與喚醒進程出現(xiàn)某事件無法繼續(xù)執(zhí)行調(diào)用Block()原語停止進程的執(zhí)行

22、運行狀態(tài) 阻塞狀態(tài)把PCB插入到Blocked隊列保留處理機的狀態(tài)轉(zhuǎn)調(diào)度程序進行新的調(diào)度1、請求系統(tǒng)服務(wù)2、啟動某種操作3、新數(shù)據(jù)沒有達到4、無新的工作可做進程阻塞46參照狀態(tài)轉(zhuǎn)換圖理解進程進入阻塞/喚醒/掛起/激活狀態(tài)的過程。 進程喚醒進程喚醒所期望的事件出現(xiàn)調(diào)用喚醒原語Wakeup()從阻塞隊列移出在PCB中把BlockedReady把進程插入到就緒隊列如I/O完成、期望的數(shù)據(jù)到達、有新的任務(wù)要執(zhí)行等等。47四、進程的掛起與激活四、進程的掛起與激活進程的掛起進程的掛起出現(xiàn)掛起事件調(diào)用掛起原語suspend()正在執(zhí)行?轉(zhuǎn)入靜止就緒活動阻塞?轉(zhuǎn)入靜止阻塞活動就緒?轉(zhuǎn)入靜止就緒轉(zhuǎn)向調(diào)度程序重新

23、調(diào)度是否是否是把進程駐留到外存48進程的激活進程的激活發(fā)生激活事件檢查內(nèi)存空間調(diào)用激活原語Active()把進程從外存調(diào)入到內(nèi)存檢查進程狀態(tài)靜止就緒?轉(zhuǎn)入活動就緒靜止阻塞?轉(zhuǎn)入活動阻塞492.3進程同步進程同步 50l在多道程序系統(tǒng)中，進程間存在：資源共享資源共享和相相互協(xié)作互協(xié)作的關(guān)系。l資源共享資源共享：進程相互不知道對方的存在。進程共享系統(tǒng)的資源。l協(xié)作關(guān)系協(xié)作關(guān)系：有些進程之間存在相互依賴關(guān)系。l進程同步的任務(wù)進程同步的任務(wù)：保證系統(tǒng)中的進程互斥地訪問系統(tǒng)臨界資源。保證協(xié)作進程前后執(zhí)行順序的協(xié)調(diào)。一、進程同步的基本概念進程同步的基本概念1 1兩種形式的制約關(guān)系兩種形式的制約關(guān)系在多道程

24、序環(huán)境下，當程序并發(fā)執(zhí)行時，由于資源共享和進程合作，使同處于一個系統(tǒng)中的諸進程之間可能存在著以下兩種形式的制約關(guān)系。51間接相互制約關(guān)系同處于一個系統(tǒng)中的進程，通常都共享著某種系統(tǒng)資源，如共享CPU、共享I/O設(shè)備等。所謂間接相互制約即源于這種資源共享。(2) 直接相互制約關(guān)系由于進程間的合作產(chǎn)生的相互制約關(guān)系。例：輸入進程A寫入數(shù)據(jù)緩沖區(qū)輸出進程B讀取數(shù)據(jù) （空、滿兩種狀態(tài)）2. 2. 臨界資源臨界資源在系統(tǒng)中每次只能一個（有限個）進程訪問的資源，如打印機、磁帶機等?？刂婆R界資源的訪問是進程同步解決的問題。52著名的進程同步問題生產(chǎn)者-消費者(producer-consumer)問題lPro

25、ducer-Consumer: Producer:inConsumer:out消費數(shù)據(jù)生產(chǎn)數(shù)據(jù)5354生產(chǎn)者和消費者問題：消費者：使用數(shù)據(jù)者。生產(chǎn)者：存人數(shù)據(jù)者。假設(shè)：（1）n個大小相等的緩沖區(qū)用于存放數(shù)據(jù)； 每次生產(chǎn)、消費一個數(shù)據(jù)。（2）兩類緩沖區(qū) 空緩沖區(qū)：指針in指向區(qū)頭。 滿緩沖區(qū)：指針out指向區(qū)頭。 in、 out的使用？ 如何控制 in、 out的合理移動和緩沖區(qū)的使用？55Var n，integer；type item=； /緩沖區(qū)類型var buffer: array0，1，n-1 of item；in，out: 0，1，n-1；counter: 0，1，n； /記錄滿緩沖區(qū)

26、數(shù)56producer: /生產(chǎn)者進程 repeat produce an item in nextp； /局部變量 while counter=n do no-op； /重復(fù)測試條件 bufferin:=nextp； /將局部變量的內(nèi)容放入in指向的空緩沖區(qū) in:=in+1 mod n； /in指向下一個空緩沖區(qū) counter:=counter+1；/滿緩沖區(qū)數(shù)加1 until false； consumer: /消費者進程 repeat while counter=0 do no-op； /重復(fù)測試條件 nextc:=bufferout； /將滿緩沖區(qū)頭存入局部變量 out:=(out

27、+1) mod n； / out指向下一個滿緩counter:=counter-1； /滿緩沖數(shù)減1consumer the item in nextc；/消費數(shù)據(jù)until false； 57算法與存在問題算法與存在問題設(shè)緩沖區(qū)n個單元，共享變量counter記錄滿緩沖區(qū)數(shù)，則基本算法：Producer進程:當counter= =n時等待。in:=(in+1)mod ncounter=counter+1Consumer進程:當counter= =0時等待out:=(out+1)mod ncounter=counter-1存在問題：共享內(nèi)存變量counter引起的。register1:=cou

28、nter;register1:=register1+1;counter:=register1;register2:=counter;register2:=register-1;counter:=register2;5859假設(shè)：counter初值為5register1:=counter； (register1=5)register2:=counter； (register2=5)register1:=register1+1； (register1=6)register2:=register2-1； (register2=4)counter:=register1； (counter=6)coun

29、ter:=register2； (counter=4) 實際counter的值應(yīng)該為5生產(chǎn)者和消費者并發(fā)執(zhí)行時：產(chǎn)生問題的原因：一個進程對共享變量的操作沒有結(jié)束，另一個進程便開始對共享變量進行操作。60如何解決產(chǎn)生問題 如何控制共享變量的并發(fā)使用3.臨界區(qū)臨界區(qū)l臨界區(qū):把每個進程中訪問臨界資源的那段代碼叫臨界區(qū)。只要每個進程互斥進入臨界區(qū)、便可以實現(xiàn)對臨界資源的互斥訪問。l實現(xiàn)算法實現(xiàn)算法repeatentry sectioncritical section;exit sectionremainder section;until false;進入?yún)^(qū)：用于檢查臨界資源是否空閑。退出區(qū)：用于釋放

30、臨界資源。執(zhí)行臨界區(qū)代碼4同步機制應(yīng)遵循的規(guī)則62空閑讓進空閑讓進 當臨界資源空閑時，允許一個進程進入臨界區(qū)。忙則等待忙則等待 臨界資源正被訪問時，其它進程必須等待。有限等待有限等待 應(yīng)保證進程能在有限時間內(nèi)能進入自己的 臨界區(qū)。讓權(quán)等待讓權(quán)等待 如果進程不能進入自己的臨界區(qū)、應(yīng)立即 釋放處理機。二、信號量機制二、信號量機制 （重點、難點）（重點、難點）1整型信號量用于解決進程的互斥與同步問題。創(chuàng)始人：荷蘭 E.W.Dijkstra 1965整型信號量：是一個僅能初始化、用兩個原子操作對其進行操作的整形變量。值用于表示資源的數(shù)目。6364關(guān)于信號量關(guān)于信號量s的的3個操作：個操作：（1）初始化

31、）初始化 初始化為一個初始化為一個非負數(shù)非負數(shù)。（2）wait（s）操作（）操作（或或P操作）操作） 0：該進程進入：該進程進入等待狀態(tài)等待狀態(tài) s 將其插入到信號量的等待隊列將其插入到信號量的等待隊列 0：s:=s-1,該進程繼續(xù)執(zhí)行該進程繼續(xù)執(zhí)行（3）signal（s）操作（）操作（或或V操作）操作） s:=s+1 Wait(S)和signal(S)操作的描述：wait(S)： while S=0 do no-op； /重復(fù)檢測S:=S-1；signal(S)： S:=S+1； 6566注意：(1)wait(s)和signal(s)為原子操作。(2)信號量保存在內(nèi)核中，供系統(tǒng)的所有進程使用

32、，占用系統(tǒng)資源。(3)沒有用的信號量應(yīng)及時刪除。2記錄型信號量記錄型信號量l整型信號量存在問題 進程在wait(s)、當S0時處于“忙等”，不能遵守“讓權(quán)等待”準則。l記錄型信號量結(jié)構(gòu)67type semaphore=record begin value:integer; /表示資源數(shù) L:list of process; /鏈接所有等待進程 end不存在“忙等”現(xiàn)象記錄型信號量記錄型信號量wait()和和signal()lWait(s)操作描述 signal(s)操作描述Procedure wait(s) var s:semaphore; /定義信號量 begin s.value:=s.va

33、lue-1; if s.value=n then notfull.wait； /沒有空緩進入條件變量notfull的等待隊列 buffer(in):=nextp； in:=(in+1) mod n； count:=count+1； if notempty.queue then notempty.signal； /如果非空隊列有進程，則喚醒 end91PC管程描述：管程描述：procedure entry get(item) / 消費數(shù)據(jù)過程beginif count=0 then notempty.wait；nextc:=buffer(out)；out:=(out+1) mod n；count

34、:=count-1；if notfull.quene then notfull.signal； /如果非滿隊列有進程，則喚醒endbegin in:=out:=0；count:=0； end 92生產(chǎn)者和消費者的描述：producer: beginrepeat produce an item in nextp； PC.put(item)；/調(diào)用管程的過程until false；endconsumer: beginrepeat PC.get(item)； /調(diào)用管程的過程 consume the item in nextc；until false；end932.4經(jīng)典進程的同步問題經(jīng)典進程的同步

35、問題l生產(chǎn)者消費者問題l讀者寫者問題l哲學(xué)家就餐問題 9495閱讀者Reader ：讀數(shù)據(jù)進程。寫入者Writer：修改數(shù)據(jù)進程。要求：（1）n個閱讀者可以同時讀數(shù)據(jù)集（臨界段代碼）； 描述為：RN（2）一個寫入者不能與其他進程同時訪問數(shù)據(jù)集。解決方法：l有一個寫入者訪問數(shù)據(jù)集時，其他進程等待。l有一個閱讀者訪問數(shù)據(jù)集時，允許其他閱讀者 訪問數(shù)據(jù)集,但拒絕寫入者進程進入。讀者讀者寫者問題寫者問題如:讀者和圖書管理員1利用記錄型信號量解決讀者寫者問題說明：（1）互斥信號量 rmutex：控制對readcount的改寫。 wmutex: 控制寫入者。（2）共享變量 readcount記錄閱讀者數(shù)。

36、96讀者寫者問題描述:/初始化定義Var rmutex，wmutex: semaphore:=1,1；Readcount: integer:=0；98begin parbegin Reader: begin repeat wait(rmutex)； if readcount=0 then wait(wmutex)； Readcount:=Readcount+1； signal(rmutex)； perform read operation； wait(rmutex)； readcount:=readcount-1； if readcount=0 then signal(wmutex)； sig

37、nal(rmutex)； until false；end 控制Readcount 增1 控制Readcount 減1控制寫著99 writer: begin repeat wait(wmutex)；？ perform write operation；/什么情況下執(zhí)行此操作 signal(wmutex)；？ until false； end parendend 1002.5 進進 程程 通通 信信 l進程通信：進程間的信息傳遞。l進程通信常見的類型：共享內(nèi)存消息傳遞管道通信1011.共享內(nèi)存系統(tǒng)l共享數(shù)據(jù)結(jié)構(gòu)的通信方式進程間共用某些數(shù)據(jù)結(jié)果，通過這些數(shù)據(jù)結(jié)構(gòu)實現(xiàn)進程間的通信。這種方式系統(tǒng)僅提供存

38、儲區(qū)，進程間的通信、數(shù)據(jù)結(jié)構(gòu)設(shè)置全部由程序員負責。如：中間結(jié)果。存在問題： 效率低下。l共享存儲區(qū)的通信方式在系統(tǒng)中劃出一塊存儲區(qū)作為共享存儲區(qū)，進程可以對共享存儲區(qū)的數(shù)據(jù)進行讀/寫，以實現(xiàn)進程間的通信。102l在進程間的數(shù)據(jù)交換以消息（message)為單位(在計算機網(wǎng)絡(luò)中叫報文)。l消息傳遞系統(tǒng)按實現(xiàn)方式分為：消息傳遞系統(tǒng)按實現(xiàn)方式分為：直接通信方式發(fā)送進程直接將消息發(fā)送給接收進程，并將接收進程掛在消息隊列上，接收進程從消息緩沖隊列中接收消息。2.消息傳遞系統(tǒng)間接通信方式發(fā)送進程把消息發(fā)送到某中介上（郵箱），接收進程從中介中獲取消息郵箱通信方式。在網(wǎng)絡(luò)中的應(yīng)用電子郵件系統(tǒng)。1033.管道通

39、信l管道：用于連接一個讀進程和一個寫進程、實現(xiàn)兩個進程間通信的共享文件pipe文件。l管道通信：利用管道進行通信。l管道通信提供給進程間三種協(xié)調(diào)能力：互斥同步檢測對方是否存在，存在進行通信，否則不進行寫進程Pipe文件讀進程104二、消息傳遞通信的實現(xiàn)方法二、消息傳遞通信的實現(xiàn)方法1.直接通信方式指發(fā)送進程利用OS所提供的發(fā)送命令，直接把消息發(fā)送給目標進程。此時，要求發(fā)送進程和接收進程都以顯式方式提供對方的標識符。兩條原語通信命令：Send(Receiver，message) 發(fā)送一個消息給接收進程；Receive(Sender，message)或Receive (id，message)；例如

40、：原語Send(P2，m1)表示將消息m1發(fā)送給接收進程P2；原語Receive(P1，m1)則表示接收由P1發(fā)來的消息m1。 通信方式解決生產(chǎn)者消費者問題略l間接通信方式：進程間的通信是通過共享數(shù)據(jù)結(jié)構(gòu)的實體(信箱)來實現(xiàn)的。Sender 1Sender n信 箱Receiver 1Receiver n 要進行通信關(guān)于信箱需要： (1)創(chuàng)建 (2)發(fā)送與接收 自讀內(nèi)容 (3)撤消信箱的類型：私有信箱公共信箱共享信箱發(fā)送者和接收者：1n個2間接通信方式間接通信方式（理解通信方式，了解細節(jié)）（理解通信方式，了解細節(jié)）106三、消息傳遞系統(tǒng)實現(xiàn)中的若干問題三、消息傳遞系統(tǒng)實現(xiàn)中的若干問題(自讀內(nèi)容自讀內(nèi)容) 四、消息隊列通信機制四、消息隊列通信機制 （理解）（理解）1.消息緩沖隊列通信機制中數(shù)據(jù)結(jié)構(gòu)消息緩沖隊列通信機制中數(shù)據(jù)結(jié)構(gòu) （1）消息緩沖區(qū)消息緩沖隊列通信方式利用消息緩沖區(qū)（數(shù)據(jù)結(jié)構(gòu)）進行消息傳遞。描述如下：type message buffer=record sender；發(fā)送者進程標識符 size； 消息長度 text； 消息正文 next； 指向下一個消息緩沖 end 區(qū)的指針107（2） PCB中有關(guān)通信的數(shù)據(jù)項PCB中增加消息隊列隊首指針，用于對消息隊列進行操作，以及用于實現(xiàn)同步的互斥信號量mutex和資源信號量sm。PCB中增加的數(shù)據(jù)項描述如下： ty