1、計算機(jī)操作系統(tǒng),南京工業(yè)大學(xué)信息學(xué)院,第二章 進(jìn)程管理, 進(jìn)程的基本概念 進(jìn)程控制 進(jìn)程同步 經(jīng)典進(jìn)程同步問題 進(jìn)程通信 線程,這一章介紹如下幾個問題：,2.1 進(jìn)程的基本概念(1),程序的順序執(zhí)行及其特征,順序執(zhí)行包含兩層含義： 對于多個用戶程序來說，所有程序是依次執(zhí)行的。（外部順序性） 對于一個程序來說，它的所有指令是按序執(zhí)行的。（內(nèi)部順序性）,2.1 進(jìn)程的基本概念(2),程序順序執(zhí)行的特征,（1）順序性：,處理機(jī)的操作嚴(yán)格按照程序所規(guī)定的順序執(zhí)行，即每一操作必須在下一操作開始之前結(jié)束（或者說下一操作必須在當(dāng)前操作結(jié)束后才能開始）。,（2）封閉性：,程序是在封閉的環(huán)境下執(zhí)行的。即 程序運(yùn)

2、行時獨占全機(jī)資源，資源的狀態(tài)（除初始態(tài)外）只有本程序才能改變它。 程序一旦開始執(zhí)行，其執(zhí)行結(jié)果不受外界影響。,（3）可再現(xiàn)性：,只要程序執(zhí)行時的環(huán)境和初始條件相同，當(dāng)程序重復(fù)執(zhí)行時，都將獲得相同的結(jié)果。,2.1 進(jìn)程的基本概念(3),程序的并發(fā)執(zhí)行及其特征,程序的并發(fā)執(zhí)行包括兩層含義：,對于一個程序來說，它的所有指令是按序執(zhí)行的。（內(nèi)部順序性） 對于多個程序（進(jìn)程）來說，所有進(jìn)程是交叉執(zhí)行的。（外部并發(fā)性）,2.1 進(jìn)程的基本概念(4),程序并發(fā)執(zhí)行時的特征,1）間斷性:,程序在并發(fā)執(zhí)行時，由于它們共享系統(tǒng)資源，以及為完成同一任務(wù)而相互合作，致使這些并發(fā)執(zhí)行的程序之間形成了相互制約的關(guān)系。（互

3、斥關(guān)系、同步關(guān)系）,相互制約導(dǎo)致并發(fā)執(zhí)行的程序具有“執(zhí)行暫停執(zhí)行”這種間斷性活動規(guī)律。,2）失去封閉性：,程序在并發(fā)執(zhí)行時，由于多個程序共享系統(tǒng)資源，因而這些資源的狀態(tài)將由多個程序來改變，致使程序的運(yùn)行已失去了封閉性。,某程序的執(zhí)行時，會受到其他程序的影響。,2.1 進(jìn)程的基本概念(5),程序并發(fā)執(zhí)行時的特征,3）不可再現(xiàn)性與時間有關(guān)的錯誤,程序在并發(fā)執(zhí)行時，由于失去了封閉性，也將導(dǎo)致其再失去可再現(xiàn)性。 例如：有兩個循環(huán)程序A和B，它們共享一個變量N。,L1：N = N+1； goto L1；,L2：print (N )； N = 0； goto L2；,程序A,程序B,程序A和B并發(fā)執(zhí)行時，

4、可能出現(xiàn)下述三種情況（設(shè)某時刻N(yù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。,計算結(jié)果已與并發(fā)程序的執(zhí)行速度有關(guān)，從而使程序執(zhí)行失去了可再現(xiàn)性。,2.1 進(jìn)程的基本概念(6),進(jìn)程的特征與狀態(tài),1進(jìn)程的定義和特征,進(jìn)程是程序在一個數(shù)據(jù)集上的運(yùn)行過程，是系統(tǒng)進(jìn)行資源分配和調(diào)度的一個獨立單位。 (傳統(tǒng)OS的定義),定義,1）結(jié)構(gòu)特征：,進(jìn)程的特征,程序段、相關(guān)的數(shù)據(jù)段、PCB

5、三部分構(gòu)成了進(jìn)程實體。,通常的程序是不能并發(fā)執(zhí)行的，為使程序（含數(shù)據(jù)）能獨立運(yùn)行，應(yīng)為之配置一進(jìn)程控制塊（即PCB）。,在許多情況下所說的進(jìn)程，實際上是指進(jìn)程實體。如，所謂創(chuàng)建進(jìn)程，,2）動態(tài)性：,進(jìn)程的實質(zhì)是進(jìn)程實體的一次執(zhí)行過程，故動態(tài)性是進(jìn)程的最基本特征。,3）并發(fā)性：,這是指多個進(jìn)程實體同存于內(nèi)存中，且能在一段時間內(nèi)同時運(yùn)行。,2.1 進(jìn)程的基本概念(7),進(jìn)程的特征與狀態(tài),4）獨立性 ：,進(jìn)程的特征：,在傳統(tǒng)的OS中，獨立性是指進(jìn)程實體是一個能獨立運(yùn)行、獨立分配資源和獨立接受調(diào)度的基本單位。,5）異步性 ：,是指進(jìn)程按各自獨立的、不可預(yù)知的速度向前推進(jìn)，或說進(jìn)程實體按異步方式運(yùn)行。,

6、2.1 進(jìn)程的基本概念(8),進(jìn)程的特征與狀態(tài),進(jìn)程的三種基本狀態(tài)：,1）就緒（Ready）狀態(tài)：,當(dāng)進(jìn)程已分配到除CPU以外的所有資源后，只要再獲得CPU，便可立即執(zhí)行，進(jìn)程這時的狀態(tài)稱為就緒狀態(tài)。,系統(tǒng)中處于就緒狀態(tài)的進(jìn)程可能有多個，通常將它們排成一個隊列，稱為就緒隊列。,2）執(zhí)行（Running）狀態(tài):,進(jìn)程已獲得CPU，其程序正在執(zhí)行。,3）阻塞（Blocked）狀態(tài):,正在執(zhí)行的進(jìn)程由于發(fā)生某事件而暫時無法繼續(xù)執(zhí)行時，便放棄處理機(jī)而處于暫停狀態(tài)，亦即進(jìn)程的執(zhí)行受到阻塞，把這種暫停狀態(tài)稱為阻塞狀態(tài)（或等待狀態(tài)）。,使進(jìn)程阻塞的典型事件：請求I/O，申請緩沖空間等等。,2.1 進(jìn)程的基本

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

8、有時希望掛起某些進(jìn)程，以便檢查運(yùn)行中的資源使用情況或進(jìn)行記賬。,2.1 進(jìn)程的基本概念(11),進(jìn)程的特征與狀態(tài),掛起狀態(tài)：,2）進(jìn)程狀態(tài)的轉(zhuǎn)換,活動就緒靜止就緒,活動阻塞靜止阻塞,靜止就緒活動就緒,靜止阻塞活動阻塞,掛起原語Suspend,激活原語Active,2.1 進(jìn)程的基本概念(12),進(jìn)程控制塊（PCB）,為了描述和控制進(jìn)程的運(yùn)行，系統(tǒng)為每個進(jìn)程定義了一個數(shù)據(jù)結(jié)構(gòu)進(jìn)程控制塊。 進(jìn)程控制塊是進(jìn)程實體的一部分，是操作系統(tǒng)中最重要的記錄型數(shù)據(jù)結(jié)構(gòu)。,1. PCB作用：,使一個在多道程序環(huán)境下不能獨立運(yùn)行的程序（含數(shù)據(jù)），成為一個能獨立運(yùn)行的基本單位，一個能與其它進(jìn)程并發(fā)執(zhí)行的進(jìn)程?；蛘哒f，

9、OS是根據(jù)PCB來對并發(fā)進(jìn)程進(jìn)行控制和管理的。,例如：進(jìn)程調(diào)度；現(xiàn)場保護(hù)和恢復(fù)；進(jìn)程同步和通信。,PCB是進(jìn)程存在的唯一標(biāo)志,2.1 進(jìn)程的基本概念(13),進(jìn)程控制塊（PCB）,2進(jìn)程控制塊中的信息,PCB中記錄了操作系統(tǒng)所需的、用于描述進(jìn)程當(dāng)前情況以及控制進(jìn)程運(yùn)行的全部信息。具體包括下述四方面的信息：,1）進(jìn)程標(biāo)識符：,內(nèi)部標(biāo)識符(進(jìn)程號)；外部標(biāo)識符(名)； 父進(jìn)程標(biāo)識及子進(jìn)程標(biāo)識；用戶標(biāo)識,2）處理機(jī)狀態(tài)：,處理機(jī)狀態(tài)信息主要由處理機(jī)的各種寄存器中的內(nèi)容組成的。寄存器包括：通用寄存器、指令計數(shù)器、程序狀態(tài)字（PSW）寄存器、用戶棧指針。(保護(hù)、恢復(fù)現(xiàn)場),當(dāng)處理機(jī)被中斷時，這些信息都必

10、須保存到PCB中，以便該進(jìn)程重新執(zhí)行時，能從斷點繼續(xù)執(zhí)行。,2.1 進(jìn)程的基本概念(14),進(jìn)程控制塊（PCB）,2進(jìn)程控制塊中的信息,3）進(jìn)程調(diào)度信息：,在PCB中還存放一些與進(jìn)程調(diào)度和進(jìn)程對換有關(guān)的信息。包括：,進(jìn)程狀態(tài)作為調(diào)度和對換時的依據(jù)。 進(jìn)程優(yōu)先級由于描述進(jìn)程使用處理機(jī)的優(yōu)先級別的一個整數(shù)，優(yōu)先級高的進(jìn)程優(yōu)先獲得處理機(jī)。 進(jìn)程調(diào)度所需的其它信息它們與所采用的進(jìn)程調(diào)度算法有關(guān)。 事件即阻塞原因。,2.1 進(jìn)程的基本概念(15),進(jìn)程控制塊（PCB）,2進(jìn)程控制塊中的信息,4）進(jìn)程控制信息：,程序和數(shù)據(jù)的地址指程序和數(shù)據(jù)所在的內(nèi)存或外存首地址； 進(jìn)程同步和通信機(jī)制如信號量、消息隊列指針

11、等，它們可能全部或部分地存放在PCB中； 資源清單是一張列出了除CPU外的、進(jìn)程所需的全部資源及已經(jīng)分配到該進(jìn)程的資源的清單； 鏈接指針?biāo)o出本進(jìn)程（PCB）所在隊列中下一個進(jìn)程的PCB的首址。,2.1 進(jìn)程的基本概念(16),進(jìn)程控制塊（PCB）,3進(jìn)程控制塊的組織方式(1),常用的組織方式有兩種：鏈接方式和索引方式。,1）鏈接方式,把具有同一狀態(tài)的PCB，用其中的鏈接字鏈接成一個隊列。形成：就緒隊列、阻塞隊列、空白隊列等,2.1 進(jìn)程的基本概念(17),進(jìn)程控制塊（PCB）,3進(jìn)程控制塊的組織方式(2),2）索引方式:,系統(tǒng)根據(jù)所有進(jìn)程的狀態(tài)建立幾張索引表。如， 就緒索引表 阻塞索引表等,

12、索引表的首址記錄在專用單元中； 每個索引表的表目中，記錄具有相應(yīng)狀態(tài)的某個PCB的首址。,2.2 進(jìn)程控制(1),進(jìn)程控制是進(jìn)程管理中最基本的功能。 進(jìn)程控制包括： 創(chuàng)建進(jìn)程 終止進(jìn)程 進(jìn)程狀態(tài)轉(zhuǎn)換,進(jìn)程控制是由OS的內(nèi)核完成的。,2.2 進(jìn)程控制(2),2.2.1 進(jìn)程的創(chuàng)建,1引起創(chuàng)建進(jìn)程的事件,用戶登錄 作業(yè)調(diào)度 提供服務(wù),當(dāng)用戶進(jìn)程提出某種請求后，系統(tǒng)將專門創(chuàng)建一個進(jìn)程來提供用戶所需的服務(wù)。如，文件打印。,上述三種情況，都是由系統(tǒng)內(nèi)核為它創(chuàng)建一個新進(jìn)程。,應(yīng)用請求：,是基于應(yīng)用進(jìn)程的需求，由應(yīng)用進(jìn)程自己創(chuàng)建一個新進(jìn)程，以便新進(jìn)程以并發(fā)運(yùn)行方式完成特定任務(wù)。,2.2 進(jìn)程控制(3),2.

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

14、運(yùn)行超時 等待超時算術(shù)運(yùn)算錯被0除 I/O故障,操作員或操作系統(tǒng)干預(yù)（如發(fā)生死鎖） 父進(jìn)程請求 父進(jìn)程終止,2.2 進(jìn)程控制(5),2.2.2 進(jìn)程的終止,2進(jìn)程的終止過程,OS調(diào)用終止原語，按下述過程終止進(jìn)程：,（1）根據(jù)被終止進(jìn)程的標(biāo)識，從PCB集合中找除該進(jìn)程的PCB，讀出該進(jìn)程狀態(tài)。 （2）若被終止進(jìn)程正處于執(zhí)行狀態(tài)，應(yīng)立即終止其執(zhí)行，并置調(diào)度標(biāo)志為真，用于指示該進(jìn)程被終止后應(yīng)重新進(jìn)行調(diào)度。若該進(jìn)程還有子孫進(jìn)程，應(yīng)將其所有子孫進(jìn)程終止，以防止它們成為不可控進(jìn)程。 （3）將被終止進(jìn)程的所有資源，或者歸還給其父進(jìn)程，或者歸還給系統(tǒng)。 （4）將被終止進(jìn)程（它的PCB）從所在隊列中移出，等待其

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

16、）進(jìn)程提供的數(shù)據(jù)才能運(yùn)行以對數(shù)據(jù)進(jìn)行處理，則只要其所需數(shù)據(jù)尚未到達(dá)，該進(jìn)程只有阻塞（等待）。如，,2.2 進(jìn)程控制(7),2.2.2進(jìn)程的阻塞和喚醒,2進(jìn)程阻塞過程,調(diào)用阻塞原語block把自己阻塞。（主動行為）,阻塞（block）過程：,立即停止執(zhí)行； 把PCB中進(jìn)程狀態(tài)由“執(zhí)行”改為“阻塞”； 將PCB插入具有相同事件的阻塞隊列； 轉(zhuǎn)進(jìn)程調(diào)度程序，將處理機(jī)分配給某個就緒進(jìn)程，并進(jìn)行進(jìn)程切換保留被阻塞進(jìn)程的處理機(jī)狀態(tài)（在PCB中），再按新進(jìn)程的PCB中處理機(jī)狀態(tài)設(shè)置CPU的環(huán)境。,2.2 進(jìn)程控制(8),2.2.2進(jìn)程的阻塞和喚醒,3進(jìn)程喚醒過程,調(diào)用喚醒原語wakeup( )，將等待事件的

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

18、程考查該進(jìn)程的運(yùn)行狀態(tài)。,若該進(jìn)程正在執(zhí)行，則轉(zhuǎn)進(jìn)程調(diào)度程序重新調(diào)度。,2.2 進(jìn)程控制(10),2.2.4 進(jìn)程的掛起和激活,2進(jìn)程的激活,當(dāng)發(fā)生激活進(jìn)程的事件時(如父進(jìn)程或用戶請求激活指定進(jìn)程，而內(nèi)存中已有足夠空間時)，系統(tǒng)利用激活原語active( )將指定進(jìn)程激活。,激活過程是：,將進(jìn)程從外存調(diào)入內(nèi)存；,若是靜止就緒，則改為活動就緒； 若是靜止阻塞，則改為活動阻塞。,若采用的是搶占式調(diào)度策略，則應(yīng)檢查被激活就緒進(jìn)程的優(yōu)先級，若其優(yōu)先級比先行執(zhí)行進(jìn)程高，則應(yīng)將處理機(jī)分配給被激活進(jìn)程。,檢查該進(jìn)程現(xiàn)行狀態(tài)：,2.3 進(jìn)程同步,由于進(jìn)程的異步性，尤其是它們競爭臨界資源時，可能會給系統(tǒng)造成混亂

19、。 進(jìn)程同步的主要任務(wù)，是使并發(fā)執(zhí)行的進(jìn)程之間能有效地共享資源和相互合作，從而使程序的執(zhí)行具有可再現(xiàn)性。,2.3 進(jìn)程同步(2),2.3.1 進(jìn)程同步的基本概念,1兩種形式的制約關(guān)系,（1）間接制約關(guān)系,間接制約關(guān)系源于資源共享。如，共享打印機(jī)。,進(jìn)程互斥,（2）直接制約關(guān)系,源于進(jìn)程間的合作。如，,進(jìn)程同步,2臨界資源,在一段時間內(nèi)只允許一個進(jìn)程訪問的資源，即僅當(dāng)一個進(jìn)程訪問完并釋放該資源后，才允許另一個進(jìn)程訪問的資源，稱為臨界資源或獨占資源。,如，打印機(jī)、磁帶機(jī)、共享變量、隊列、,2.3 進(jìn)程同步(3),2.3.1 進(jìn)程同步的基本概念,【例】生產(chǎn)者-消費(fèi)者問題著名的進(jìn)程同步問題,共享變量：

20、 臨界資源,循環(huán)緩沖區(qū),生產(chǎn)者投放一個產(chǎn)品后，輸入指針in加1：in = ( in + 1 ) % n （n是緩沖區(qū)個數(shù)，整型常量），in初值為0； 消費(fèi)者每取出一個產(chǎn)品，輸出指針out加1：out = ( out + 1 ) % n，out初值為0；,引入一個共享變量counter,初值為0。 生產(chǎn)者投放一個產(chǎn)品，counter加1，counter = n時不能再投放產(chǎn)品 消費(fèi)者每取一個產(chǎn)品，counter減1，counter = 0時不能再取出產(chǎn)品,前面交通觀察站例子亦然。,process producer： while （condition） produce an item in nex

21、tp； while(counter=n) no-op；/no-op表示空操作 bufferin = nextp； in = (in + 1)% n ； counter = counter + 1 ； ,生產(chǎn)者進(jìn)程算法如下：,process consumer： struct item nextc ； while （condition） while （counter = 0）no-op ； nextc = bufferout ； out = （out + 1）% n ； counter = counter 1 ； consume the item in nextc ； ,消費(fèi)者進(jìn)程算法如下：,上面

22、的生產(chǎn)者程序和消費(fèi)者程序，在順序執(zhí)行時其結(jié)果也是正確的。但若并發(fā)執(zhí)行時，可能會出現(xiàn)差錯，問題在于這兩個進(jìn)程共享變量counter。生產(chǎn)者對它做加1操作，消費(fèi)者對它做減1操作，這兩個操作在機(jī)器語言實現(xiàn)時，?？捎孟旅娴男问矫枋觯?生產(chǎn)者執(zhí)行的操作： register1 = counter ； register1 = register1 + 1 ； counter = register1；,消費(fèi)者執(zhí)行的操作： register2 = counter ； register2 = register2 - 1 ； counter = register2；,假設(shè)counter當(dāng)前的值為5，按下述順序執(zhí)行：,

23、register1 = counter; (5) register1 = register1 + 1; (6) register2 = counter; (5) register2 = register2 1; (4) counter = register1; (6) counter = register2; (4),最終counter的值為4，正確的counter值應(yīng)是5，出現(xiàn)了差錯。,學(xué)生可以考慮出現(xiàn)6的情況。,解決此問題的關(guān)鍵，是應(yīng)將變量counter作為臨界資源處理，亦即讓生產(chǎn)者進(jìn)程和消費(fèi)者進(jìn)程互斥地訪問變量counter。,2.3 進(jìn)程同步(4),2.3.1 進(jìn)程同步的基本概念,3臨

24、界區(qū)（critical section）,每個進(jìn)程中訪問臨界資源的那段代碼稱為臨界區(qū)。,不論是硬件臨界資源，還是軟件臨界資源，多個進(jìn)程必須互斥地對它們訪問。,顯然，若能保證諸進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，便可實現(xiàn)諸進(jìn)程對臨界區(qū)的互斥訪問。為此，每個進(jìn)程在進(jìn)入臨界區(qū)之前，應(yīng)先對欲訪問的臨界資源進(jìn)行檢查，看是否正被訪問，如果此刻該資源未被訪問，便可進(jìn)入臨界區(qū)對該臨界資源進(jìn)行訪問，并設(shè)置它正被訪問的標(biāo)志；如果此刻它正被訪問，則本進(jìn)程不能進(jìn)入臨界區(qū)。,因此必須在臨界區(qū)前增加一段用于上述檢查的代碼，把這段代碼稱為進(jìn)入?yún)^(qū)（entry section）； 相應(yīng)地，在臨界區(qū)后面也要加上一段稱為退出區(qū)（exit

25、section）的代碼，用于將臨界區(qū)正被訪問的標(biāo)志恢復(fù)為未被訪問的標(biāo)志。,定義：,進(jìn)程互斥不允許兩個或兩個以上進(jìn)程同時訪問同一個臨界資源。 進(jìn)程互斥不允許兩個或兩個以上進(jìn)程同時進(jìn)入相關(guān)臨界區(qū)。,2.3 進(jìn)程同步(5),2.3.1 進(jìn)程同步的基本概念,4同步機(jī)制應(yīng)遵循的原則,為了實現(xiàn)各進(jìn)程互斥地進(jìn)入自己的臨界區(qū)，一般是在系統(tǒng)中設(shè)置專門的同步機(jī)制來協(xié)調(diào)各進(jìn)程間的運(yùn)行。,所有同步機(jī)制都應(yīng)遵循如下四條準(zhǔn)則：,空閑讓進(jìn),忙則等待,當(dāng)無進(jìn)程處于臨界區(qū)時，表明臨界資源處于空閑狀態(tài)，應(yīng)允許一個請求進(jìn)入臨界區(qū)的進(jìn)程立即進(jìn)入自己的臨界區(qū)，以便有效地利用臨界資源。,有限等待,當(dāng)已有進(jìn)程進(jìn)入臨界區(qū)時，表明臨界資源正在

26、被訪問，因而其他試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待，以保證對臨界資源的互斥訪問。,讓權(quán)等待,對要求訪問臨界資源的進(jìn)程，應(yīng)保證在有限的時間內(nèi)能進(jìn)入自己的臨界區(qū)，以免陷入“死鎖”狀態(tài)。不死等。,當(dāng)進(jìn)程不能進(jìn)入自己的臨界區(qū)時，應(yīng)立即釋放處理機(jī)，以免進(jìn)程陷入“忙等”。不忙碌等待。,2.3 進(jìn)程同步(6),2.3.2 信號量機(jī)制,信號量（Semaphores）機(jī)制是一種卓有成效的進(jìn)程同步工具。信號量機(jī)制已被廣泛應(yīng)用于單處理機(jī)和多處理機(jī)系統(tǒng)以及計算機(jī)網(wǎng)絡(luò)中。,信號量機(jī)制的發(fā)展：,整型信號量,記錄型信號量,AND型信號量,信號量集,“忙等”，未遵循“讓權(quán)等待”準(zhǔn)則。,后邊重點介紹。,學(xué)生在深刻理解記錄型信號量后自

27、學(xué)。,2.3 進(jìn)程同步(7),2.3.2 信號量機(jī)制,記錄型信號量,需要一個用于代表臨界資源數(shù)目的整型變量value；還要一個在該資源上阻塞的隊列（鏈表）指針L)。故信號量應(yīng)采用記錄型（C語言中為結(jié)構(gòu)型）的結(jié)構(gòu)：,struct semaphore int value ； struct semphore *L ； ；,記錄型信號量的結(jié)構(gòu)定義,信號量除初始化外，只能通過兩個原子操作(稱為原語)wait（S）和signal（S）來訪問。它們以前被稱為P、V操作。下頁介紹wait和signal操作。,2.3 進(jìn)程同步(8),2.3.2 信號量機(jī)制,wait和signal操作可用C/C+語言描述如下：,

28、void wait（S） struct semaphore S; S.value = S.value 1 ; if (S.value 0 ) block (S.L ) ; /* 讓權(quán)等待 */ ,void signal ( S ) struct semaphore S ; S.value = S.value + 1 ; if ( S.value = 0 ) wakeup ( S.L ) ; /*喚醒第一個等待的進(jìn)程 */ ,P(S),V(S),S.value的初值表示系統(tǒng)中某類資源的數(shù)目。資源信號量。,2.3 進(jìn)程同步(9),2.3.2 信號量機(jī)制,wait和signal操作的物理意義：,對信

29、號量S的每次wait操作，意味著進(jìn)程請求一個該類臨界資源，因此描述為S.value=S.value-1；當(dāng)S.value0時，表示該類資源已分配完，因此進(jìn)程應(yīng)調(diào)用block原語進(jìn)行自我阻塞，放棄處理機(jī)，并插入到信號量鏈表S.L(阻塞隊列)中?？梢娫摍C(jī)制遵循了“讓權(quán)等待”準(zhǔn)則。 類似地，可以解釋signal操作,S.value的初值表示系統(tǒng)中某類資源的數(shù)目。資源信號量。 S.value的初值為1，表示只允許一個進(jìn)程訪問，此時信號量轉(zhuǎn)化為互斥信號量。,2.3 進(jìn)程同步(10),2.3.3 信號量的應(yīng)用,1利用信號量實現(xiàn)進(jìn)程互斥,方法要點：,為臨界資源設(shè)置一個互斥信號量mutex，其初值為1； 各進(jìn)

30、程訪問該資源的臨界區(qū)置于wait（mutex）和signal（mutex）之間即可。,wait（mutex）進(jìn)入?yún)^(qū) signal（mutex）退出區(qū),請看下頁的例子,利用信號量實現(xiàn)進(jìn)程互斥的簡單例子,某交通路口設(shè)置了一個自動計數(shù)系統(tǒng)，該系統(tǒng)由“觀察者”進(jìn)程和“報告者”進(jìn)程組成。觀察者進(jìn)程能識別卡車，并對通過的卡車計數(shù)；報告者進(jìn)程定時（可設(shè)為每隔1小時，準(zhǔn)點時）將觀察者的計數(shù)值打印輸出，每次打印后把計數(shù)值清“0”。兩個進(jìn)程的并發(fā)執(zhí)行可完成對每小時中卡車流量的統(tǒng)計。這兩個進(jìn)程的功能如下：,process observer while (condition) observe a lorry; wai

31、t（S）; count = count + 1; signal（S）; ,臨界區(qū),process reporter wait（S）; print（count）; count = 0； signal（S）; ,臨界區(qū),struct semaphore S ；int count = 0 ；S.value = 1 ；,【注意】wait（S）和signal（S）必須成對出現(xiàn),利用信號量實現(xiàn)前趨關(guān)系,【例】利用信號量，按語句的前趨關(guān)系（見圖2-6）,寫出一個可并發(fā)執(zhí)行的程序。,圖中表示： 進(jìn)程P1中有語句S1； 進(jìn)程P2中有語句S2； 語句S1執(zhí)行后才能執(zhí)行語句S2和語句S3； 語句S2執(zhí)行后才能執(zhí)行語

32、句S4和S5； 語句S3、S4和S5執(zhí)行后，才能執(zhí)行語句S6。,P1執(zhí)行完應(yīng)通知P2、P3； P2得到通知后才開始執(zhí)行；P2執(zhí)行完應(yīng)通知P4、P5；,struct semaphore a，b，c，d，e，f，g ； a.value=b.value=c.value=0; d.value=e.value=g.value=0;,程序描述如下：,初始化,parbegin /*parbegin表示并發(fā)執(zhí)行開始*/ process P1： S1；signal（a）；signal（b）； process P2： wait（a）；S2；signal（c）；signal（d）； process P3： wait

33、（b）；S3；signal（e）； process P4： wait（c）；S4；signal（f）； process P5： wait（d）；S5；signal（g）； process P6： wait（e）；wait（f）；wait（g）；S6； parend /*用parend表示并發(fā)執(zhí)行結(jié)束 */,2.4 經(jīng)典進(jìn)程同步問題,生產(chǎn)者-消費(fèi)者問題 讀者-寫者問題 哲學(xué)家進(jìn)餐問題,在多道程序環(huán)境下，進(jìn)程同步問題十分重要，引起了不少學(xué)者對它進(jìn)行研究，由此產(chǎn)生了一系列經(jīng)典的進(jìn)程同步問題，其中較有代表性的是：,通過對這些問題的研究和學(xué)習(xí)，可以幫助我們更好地理解進(jìn)程同步概念及實現(xiàn)方法。,2.4 經(jīng)典

34、進(jìn)程同步問題(2),2.4.1 生產(chǎn)者-消費(fèi)者問題,前面已經(jīng)對生產(chǎn)者-消費(fèi)者問題做了一些描述，但是未考慮進(jìn)程的互斥和同步問題，因而造成了共享變量counter的不確定性。 生產(chǎn)者-消費(fèi)者問題是相互合作進(jìn)程關(guān)系的一種抽象，例如，,先介紹最簡單的P-C問題,生產(chǎn)者-消費(fèi)者問題從特殊到一般(從易到難)可以分3種形式：,一個生產(chǎn)者、一個消費(fèi)者、一個緩沖區(qū)的問題； 一個生產(chǎn)者、一個消費(fèi)者、n個緩沖區(qū)的問題； k個生產(chǎn)者、m個消費(fèi)者、n個緩沖區(qū)的問題；,2.4 經(jīng)典進(jìn)程同步問題(3),最簡單的生產(chǎn)者-消費(fèi)者問題,一個生產(chǎn)者、一個消費(fèi)者、一個緩沖區(qū)的問題如右圖所示。,當(dāng)緩沖區(qū)空時，生產(chǎn)者可將產(chǎn)品存入緩沖區(qū)；

35、當(dāng)緩沖區(qū)滿時，生產(chǎn)者必須等待 (阻塞)，待消費(fèi)者取走產(chǎn)品后將其喚醒后，才能將產(chǎn)品存入。 當(dāng)緩沖區(qū)滿時，消費(fèi)者可從緩沖區(qū)取出產(chǎn)品進(jìn)行消費(fèi)；當(dāng)緩沖區(qū)空時，消費(fèi)者必須等待(阻塞)，待生產(chǎn)者存入產(chǎn)品后將其喚醒后，才能再從緩沖區(qū)取產(chǎn)品。,用信號量機(jī)制解決進(jìn)程同步問題的基本方法：,1為生產(chǎn)者設(shè)置1個私有信號量empty，其初值為1，表示有1個空緩沖區(qū)；為消費(fèi)者設(shè)置1個私有信號量full，其初值為0，表示開始時沒有空緩沖區(qū)；（由物理意義確定） 2生產(chǎn)者將產(chǎn)品存入緩沖區(qū)之前，應(yīng)先測試緩沖區(qū)是否空：執(zhí)行wait(empty)操作；離開臨界區(qū)(存入產(chǎn)品)后，應(yīng)通知(可能會喚醒)消費(fèi)者：執(zhí)行signal(full)

36、操作； 3消費(fèi)者從緩沖區(qū)取產(chǎn)品之前，應(yīng)先測試緩沖區(qū)是否滿：執(zhí)行wait(full)操作；離開臨界區(qū)(取走產(chǎn)品)后，應(yīng)通知(可能會喚醒)生產(chǎn)者：執(zhí)行signal(empty)操作,2.4 經(jīng)典進(jìn)程同步問題(4),最簡單的生產(chǎn)者-消費(fèi)者問題,一個生產(chǎn)者、一個消費(fèi)者、一個緩沖區(qū)的生產(chǎn)者-消費(fèi)者問題的算法描述如下所示：,semaphore empty,full; empty=1;full=0; parbegin process Producer: . produce an item in nextp; wait(empty);/測試 buffer=nextp; signal(full);/通知消費(fèi)者

37、,process Consumer: wait(full); /測試 nextc=buffer; signal(empty); /通知 consume the item in nextc; parend,2.4 經(jīng)典進(jìn)程同步問題(5),一個生產(chǎn)者、一個消費(fèi)者、n個緩沖區(qū)的P-C問題,信號量empty=n(初值),信號量full=0(初值),資源信號量,semaphore empty,full; empty=n;full=0; int in=0,out=0; /下標(biāo) parbegin process Producer: . produce an item in nextp; wait(empty

38、);/測試 bufferin=nextp; in=(in+1)%n; signal(full);/通知消費(fèi)者 ,資源信號量,process Consumer: wait(full); /測試 nextc=bufferout; out=(out+1)%n; signal(empty); /通知 consume the item in nextc; parend,與前不同,本題中in和out不是共享變量，無需互斥訪問。,2.4 經(jīng)典進(jìn)程同步問題(6),2.4.1 生產(chǎn)者-消費(fèi)者問題,下面介紹生產(chǎn)者-消費(fèi)者問題一般形式：k個生產(chǎn)者、m個消費(fèi)者、n個緩沖區(qū)的問題。 一般形式的生產(chǎn)者-消費(fèi)者問題的圖示如

39、下：,2.4.1 生產(chǎn)者-消費(fèi)者問題,用互斥信號量mutex對緩沖區(qū)(共享變量in和out)的互斥使用，互斥信號量mutex初值為1； 用資源信號量empty表示多緩沖中空緩沖區(qū)的數(shù)目，empty的初值為n； 用資源信號量full表示多緩沖中滿緩沖區(qū)的數(shù)目，full的初值為0； 只要多緩沖未滿，生產(chǎn)者便可將消息送入緩沖區(qū)； 只要多緩沖不空，消費(fèi)者便可從緩沖區(qū)取走一個消息。 生產(chǎn)者用共享變量in作為下標(biāo)訪問緩沖區(qū)，mutex為其互斥信號量；消費(fèi)者用共享變量out作為下標(biāo)訪問緩沖區(qū)，其互斥信號量也用mutex。,parbegin /并發(fā)執(zhí)行開始 process produceri (i=1,2,k

40、） item nextp ； while （condition） produce an item in nextp； wait（empty）； wait（mutex）； bufferin = nextp ； in = （in + 1）% n ； signal（mutex）； signal（full）； ,生產(chǎn)者-消費(fèi)者問題可描述如下：,process consumerj (j=1,2,m） item nextc ； while （condition） wait（full）； wait（mutex）； nextc = bufferout ； out = （out + 1）% n ； signal

41、（mutex）； signal（empty）； consume the item in nextc ； parend /并發(fā)執(zhí)行結(jié)束,臨界區(qū),在每個進(jìn)程中，實現(xiàn)互斥的wait（mutex）和signal（mutex）必須成對出現(xiàn)； 對資源信號量empty和full的wait和signal操作也要成對地出現(xiàn)，但它們處于不同的進(jìn)程中。 在每個進(jìn)程中的多個wait操作順序不能顛倒，應(yīng)先執(zhí)行對資源信號量（也稱私有信號量）的wait操作，然后執(zhí)行對互斥信號量（公有信號量）的wait操作，否則可能引起進(jìn)程死鎖。(Why?),semaphore mutex,empty,full ; item buffern

42、 ; int in = 0，out = 0 ； mutex.value = 1; empty.value = n，full.value = 0;,初始化,臨界區(qū),2.4 經(jīng)典進(jìn)程同步問題(7),2.4.2 哲學(xué)家進(jìn)餐問題,Dijkstra提出并解決的哲學(xué)家就餐問題是經(jīng)典的進(jìn)程同步問題。哲學(xué)家就餐問題描述如下：,有5個哲學(xué)家共用一張圓桌，分別坐在周圍的5張椅子上，在圓桌上有5個碗和5只筷子，他們的生活方式是交替地進(jìn)行思考和進(jìn)餐。平時，每個哲學(xué)家進(jìn)行思考，饑餓時便試圖拿起其左右最靠近他的筷子，只有在他拿到兩只筷子時才能進(jìn)餐。進(jìn)餐完畢，放下筷子繼續(xù)思考。圖2-7是其示意圖。,2.4 經(jīng)典進(jìn)程同步問題

43、(8),利用記錄型信號量解決哲學(xué)家進(jìn)餐問題,桌子上的筷子f0，f1，f4是臨界資源，應(yīng)互斥使用，可用一個信號量表示一只筷子，5只筷子的5個信號量構(gòu)成信號量數(shù)組，所有信號量的初值均為1。,struct semaphore chopstick5 ； chopstick0.value=chopstick1.value=1; chopstick2.value=chopstick3.value=1 ; chopstick4.value=1 ;,初始化,每個哲學(xué)家算法流程為,(1) 拿起左、右筷子； (2) 吃面條； (3) 放下左、右筷子； (4) 思考問題； (5) 返回(1)。,2.4 經(jīng)典進(jìn)程同步

44、問題(9),第i個哲學(xué)家的活動可描述如下：,parbegin process Pi（i = 0，1，2，3，4） while （logical） wait（chopsticki）； /拿起左邊筷子 wait（chopstick（i + 1）%5）； /拿起右邊筷子 eating ； signal（chopsticki）； /放下左邊筷子 signal（chopstick（i+1）%5）；/放下右邊筷子 thinking ； parend,此算法雖然能保證相鄰哲學(xué)家對筷子的訪問互斥，但可能引起死鎖。(Why?),2.4 經(jīng)典進(jìn)程同步問題(10),對上述哲學(xué)家算法的死鎖問題，可采取下面幾種解決方法

45、之一：,（1）至多允許4個哲學(xué)家同時取左邊的筷子，這樣能至少保證一個哲學(xué)家能就餐，并在用畢后釋放他用過的兩只筷子，從而使更多的哲學(xué)家能夠進(jìn)餐。（請學(xué)生考慮算法的描述） （2）僅當(dāng)哲學(xué)家左右兩只筷子均可用時，才允許他拿起筷子進(jìn)餐。（用AND信號量機(jī)制） （3）規(guī)定奇數(shù)號哲學(xué)家先拿左邊筷子，然后再拿右邊筷子；而偶數(shù)號哲學(xué)家先拿右邊筷子，然后再拿左邊筷子。 （4）規(guī)定每個哲學(xué)家先拿序號小的筷子按序號分配。請學(xué)生考慮算法的描述。,2.4 經(jīng)典進(jìn)程同步問題(11),2.4.3 讀者-寫者問題,一個數(shù)據(jù)文件或記錄，可被多個進(jìn)程共享，我們把只要求讀該文件的進(jìn)程稱為“讀者進(jìn)程”，其他進(jìn)程稱為“寫者進(jìn)程”。,允

46、許多個讀者進(jìn)程同時讀一個共享文件，因為讀操作不會使數(shù)據(jù)文件混亂； 不允許兩個或兩個以上寫者進(jìn)程同時訪問共享文件，因為這種訪問將會引起混亂； 不允許一個寫者進(jìn)程和其他讀者進(jìn)程同時訪問共享文件，因為這種訪問將會引起混亂。,所謂“讀者-寫者問題”是指保證一個Writer進(jìn)程必須與其它進(jìn)程互斥地訪問共享對象的同步問題。,2.4 經(jīng)典進(jìn)程同步問題(12),利用記錄型信號量解決讀者-寫者問題,【算法分析】, 為實現(xiàn)Reader進(jìn)程和Writer進(jìn)程間的互斥，設(shè)置一個互斥信號量Wmutex，其初值為1； 設(shè)置一個整型變量Rcounter，記錄正在讀的讀者進(jìn)程數(shù)。其初值為0； 由于只要有一個Reader進(jìn)程在

47、讀，便不允許Writer進(jìn)程去寫，因此第一個讀者進(jìn)程需要執(zhí)行wait（Wmutex）操作，即當(dāng)Rcounter =0時，Reader進(jìn)程才需要執(zhí)行wait（Wmutex）操作。若wait（Wmutex）操作成功（表示此時無Writer進(jìn)程在寫），Reader進(jìn)程便可去讀，同時做Rcounter+1的操作。若wait（Wmutex）操作成功（表示此時無Writer進(jìn)程在寫），Reader進(jìn)程便可去讀，同時做Rcounter+1的操作。, 同理，最后一個Reader進(jìn)程離開時(Rcounter-1后變?yōu)?)應(yīng)執(zhí)行signal（mutex）操作，以便讓W(xué)riter進(jìn)程寫。 Rcounter是被多個R

48、eader進(jìn)程訪問的臨界資源，為了對它互斥訪問，應(yīng)為它設(shè)置一個互斥信號量Rmutex。,2.4 經(jīng)典進(jìn)程同步問題(13),根據(jù)前面分析，讀者-寫者問題可描述如下：,semaphore Wmutex，Rmutex; int Rcounter = 0; Wmutex.value=Rmutex.value=1; parbegin process Readeri (i = 1，2，) wait(Rmutex); if(Rcounter=0) wait(Wmutex); Rcounter = Rcounter + 1; signal(Rmutex); Reading; wait(Rmutex); Rco

49、unter = Rcounter 1; if(Rcounter=0)signal(Wmutex); signal(Rmutex); ,process Writerj (j=1，2，) wait(Wmutex); Writing; signal(Wmutex); parend,【分析】當(dāng)?shù)谝粋€讀者在讀文件時，后續(xù)讀者也可進(jìn)入臨界區(qū)讀該文件，后續(xù)寫者不能寫(在Wmutex上阻塞)；待所有讀者退出時，由最后退出的讀者喚醒一個寫者。 當(dāng)有一個寫者在寫時，后續(xù)寫者不能寫，在Wmutex上阻塞；后續(xù)讀者不能讀，其中第一個讀者在Wmutex上阻塞，其余讀者在Rmutex上阻塞。該寫者退出時，喚醒一個寫者或讀

50、者。,讀者 優(yōu)先,2.4 經(jīng)典進(jìn)程同步問題(14),上述算法實際上是“優(yōu)先讀者”算法，當(dāng)有讀者正在讀，且后續(xù)讀者源源不斷到來時，寫者將長期得不到服務(wù)。寫者“餓死”。 為此，可以考慮“優(yōu)先寫者”的算法當(dāng)有寫者要寫時，待目前正在讀的讀者讀完后，立即讓寫者去寫（即一旦有寫者到達(dá)，后續(xù)的讀者都必須等待，而無論是否有讀者在讀文件）。請學(xué)生思考，寫出該算法的描述。,可以增加一個互斥信號量W，用于在寫進(jìn)程到達(dá)時封鎖后續(xù)的讀者進(jìn)程:讀者進(jìn)程進(jìn)入時訪問Rcouter時,增加執(zhí)行wait(W)和signal(W)；寫者進(jìn)入臨界區(qū)時，增加執(zhí)行wait(W)和signal(W)。,2.4 經(jīng)典進(jìn)程同步問題(15),復(fù)

51、習(xí)思考題,1若一只盤子一次只能放一個水果，A只往盤中放蘋果，B只往盤中放梨子，C只從盤中取蘋果，D只從盤中取梨子。試用P、V操作寫出同步算法。 2有三個進(jìn)程PA、PB、PC共享兩個緩沖器B1和B2。緩沖器B1中可存放n件產(chǎn)品，緩沖器B2中可存放m件產(chǎn)品。進(jìn)程PA每次生產(chǎn)一件產(chǎn)品并將其存入緩沖器B1中；進(jìn)程PB每次從緩沖器B1中取出一件產(chǎn)品后再把它送到緩沖器B2中；進(jìn)程PC每次從緩沖器B2中取出一件產(chǎn)品去消費(fèi)。為防止把產(chǎn)品存入已滿的緩沖器、或從空的緩沖器取產(chǎn)品、或重復(fù)取產(chǎn)品，試用PV操作實現(xiàn)它們之間的制約。(先考慮m=n=1的特例) 3今有一個文件F供進(jìn)程共享，現(xiàn)把這些進(jìn)程分成A、B兩組，規(guī)定同

52、組的進(jìn)程可以同時讀文件F；但當(dāng)有A組（或B組）的進(jìn)程在讀文件F時就不允許B組（或A組）的進(jìn)程讀文件F。試用P、V操作（記錄型信號量）來進(jìn)行管理。,進(jìn)程同步復(fù)習(xí)思考題(續(xù)),4生產(chǎn)者-消費(fèi)者問題中，如果將wait（full）和wait（mutex）互相置換，或者將signal（mutex）和signal（empty）互相置換，結(jié)果會如何？ 5試?yán)糜涗浶托盘柫繉懗鲆粋€不會出現(xiàn)死鎖的哲學(xué)家進(jìn)餐問題的算法。 6. 設(shè)自行車生產(chǎn)車間有兩個貨架，貨架A可以存放8個車架，貨架B可以存放20個車輪；又設(shè)有4個工人，他們的活動是重復(fù)勞動，分別為：工人1 加工一個車架放入貨架A中；工人2、3分別加工車輪放入貨架

53、B中（每人每次放入1個車輪）；工人4從貨架A中取一個車架，再從貨架B中取兩個車輪，組裝成一輛自行車。試用PV操作實現(xiàn)四個工人的合作。,2.6 進(jìn)程通信,進(jìn)程通信進(jìn)程之間的信息交換。 進(jìn)程之間的互斥和同步，交換的信息量少低級通信。 信號量機(jī)制作為通信工具不夠理想，表現(xiàn)在： 效率低； 通信對用戶不透明。 本節(jié)介紹進(jìn)程高級通信是指用戶可直接利用OS所提供的一組通信命令，高效地傳送大量數(shù)據(jù)的一種通信方式。 高級通信過程對用戶是透明的。大大減少了通信程序編制的復(fù)雜性。,2.6 進(jìn)程通信(2),2.6.1 進(jìn)程通信的類型 高級通信機(jī)制可歸結(jié)為三類： 共享存儲器通信； 管道通信(共享文件)； 消息傳遞通信。

54、 直接通信方式 間接通信方式信箱通信,單機(jī)(集中式),適合單機(jī)或網(wǎng)絡(luò),2.6.1 進(jìn)程通信的類型,1共享存儲器系統(tǒng)（Shared-Memory System ）,（1）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式 如生產(chǎn)者-消費(fèi)者問題中，是用有界緩沖區(qū)這種數(shù)據(jù)結(jié)構(gòu)來實現(xiàn)通信的。 公用數(shù)據(jù)結(jié)構(gòu)的設(shè)置及對進(jìn)程間同步的處理，都是程序員的職責(zé)，增加了程序員的負(fù)擔(dān)，而操作系統(tǒng)只需提供共享存儲器。低效的通信方式（低級通信）,2.6.1 進(jìn)程通信的類型,先向系統(tǒng)申請共享存儲區(qū)中的一個分區(qū)，并指定該分區(qū)的關(guān)鍵字； 若系統(tǒng)已經(jīng)將該分區(qū)分配給其它進(jìn)程，則將其描述符返回給申請者； 申請者將獲得的共享存儲分區(qū)連接到本進(jìn)程上； 此后，便

55、可象讀寫普通存儲器那樣地讀寫該公用存儲分區(qū)。UNIX/LINUX與之有關(guān)的系統(tǒng)調(diào)用有4個,1共享存儲器系統(tǒng)（Shared-Memory System ）,（2）基于共享數(shù)據(jù)結(jié)構(gòu)的通信方式：在存儲區(qū)中劃出一塊共享存儲區(qū)，諸進(jìn)程可通過對共享存儲區(qū)中數(shù)據(jù)的讀和寫來實現(xiàn)通信。屬于高級通信方式。,2.6 進(jìn)程通信(3),2管道（pipe）通信,管道用于連接一個讀進(jìn)程和一個寫進(jìn)程以實現(xiàn)它們之間通信的一個共享文件，又稱pipe文件。,首創(chuàng)于UNIX系統(tǒng),寫進(jìn)程以字節(jié)流的形式將大量數(shù)據(jù)送入管道； 讀進(jìn)程從管道中接收（讀）數(shù)據(jù)。,由于發(fā)送進(jìn)程和接收進(jìn)程是通過管道進(jìn)行通信的，故稱為管道通信。,為協(xié)調(diào)雙方的通信，管

56、道機(jī)制必須提供以下三方面的協(xié)調(diào)能力：,互斥,當(dāng)一個進(jìn)程正在對pipe執(zhí)行讀/寫操作時，其它進(jìn)程必須等待；,同步,確定對方是否存在,當(dāng)寫進(jìn)程把一定數(shù)據(jù)寫入pipe，便去睡眠等待，直至讀進(jìn)程取走數(shù)據(jù)后，再把它喚醒；當(dāng)讀進(jìn)程讀一空pipe時，也應(yīng)睡眠等待，直至寫進(jìn)程將數(shù)據(jù)寫入pipe后，再把它喚醒。,只有確定對方以存在時，才能進(jìn)行通信。,2.6 進(jìn)程通信(4),2消息傳遞系統(tǒng)(Message passing system),消息傳遞機(jī)制單機(jī)系統(tǒng)、多機(jī)系統(tǒng)、計算機(jī)網(wǎng)絡(luò)，用得最廣泛的一種高級通信機(jī)制。 進(jìn)程間的數(shù)據(jù)交換,是以格式化的消息(message)為單位的。 計算機(jī)網(wǎng)絡(luò)中，message又稱為報文

57、。 利用系統(tǒng)提供的一組通信命令（原語）進(jìn)行通信。 OS隱蔽了通信實現(xiàn)細(xì)節(jié)，大大簡化了通信程序編制的復(fù)雜性，因而得到廣泛應(yīng)用。,其通信方式,直接通信方式 間接通信方式,2.6 進(jìn)程通信(5),2.6.2 消息傳遞通信的實現(xiàn)方法,1. 直接通信方式,是指發(fā)送進(jìn)程利用OS所提供的命令，直接把消息發(fā)送給目標(biāo)進(jìn)程。,要求發(fā)送和接收進(jìn)程都以顯式方式提供對方的標(biāo)識符。兩條通信原語為：,send（Receiver，message）；,發(fā)送一個消息message給接收進(jìn)程Receiver,receive（Sender，message）；,接收Sender發(fā)來的消息message,有時，接收進(jìn)程可能與多個發(fā)送進(jìn)程

58、通信，故不可能事先知道發(fā)送進(jìn)程。對于這樣的應(yīng)用，接收原語中的源進(jìn)程參數(shù)，是完成通信后的返回值。接收原語可表示為： receive（id，message）； id是返回值（標(biāo)識符）,2.6 進(jìn)程通信(6),2.6.2 消息傳遞通信的實現(xiàn)方法,2. 間接通信方式,是指進(jìn)程之間的通信，需要通過作為共享數(shù)據(jù)結(jié)構(gòu)的實體信箱。, 信箱暫存發(fā)送進(jìn)程發(fā)送給目標(biāo)進(jìn)程的消息； 接收進(jìn)程從信箱中取出對方發(fā)給自己的消息。,既可實現(xiàn)實時通信，也可實現(xiàn)非實時通信。,2.6 進(jìn)程通信(6),2.6.2 消息傳遞通信的實現(xiàn)方法,2. 間接通信方式,系統(tǒng)為信箱通信提供了若干條原語： （1）信箱的創(chuàng)建和撤消。信箱可由OS創(chuàng)建， 也可由用戶用OS命令創(chuàng)建。 （2）消息的發(fā)送和接收。,send（mailbox，message）； r