計算機操作系統(tǒng)考研輔導--第二章

1、計算機操作系統(tǒng)計算機操作系統(tǒng)第二章第二章 進程同步與互斥進程同步與互斥2009年年1個選擇、個選擇、1個綜合應用題個綜合應用題2010年年3個選擇題個選擇題2011年年2個選擇，個選擇，1個綜合應用題個綜合應用題 進程管理是考試的熱門。這一章出題的靈活進程管理是考試的熱門。這一章出題的靈活性比較大，這部分考查的是操作系統(tǒng)性比較大，這部分考查的是操作系統(tǒng)5大管理功大管理功能之一：處理機管理，包括能之一：處理機管理，包括進程管理進程管理和和處理機調(diào)處理機調(diào)度度兩大塊的內(nèi)容，是考試的重點內(nèi)容，同時也是兩大塊的內(nèi)容，是考試的重點內(nèi)容，同時也是難點，因此對這部分除了要掌握基本的概念和基難點，因此對這部分

2、除了要掌握基本的概念和基本的原理外，還要求考生能運用這些基本原理去本的原理外，還要求考生能運用這些基本原理去分析和解決問題，其中分析和解決問題，其中P、V原語操作、同步問題原語操作、同步問題及死鎖問題都有可能出綜合應用題。及死鎖問題都有可能出綜合應用題。 進程同步與互斥是進程管理的重點，進程同步與互斥是進程管理的重點，也是操作系統(tǒng)學科的一個難點。這個考點的也是操作系統(tǒng)學科的一個難點。這個考點的知識，一般都會出現(xiàn)在考試試題中。具體包知識，一般都會出現(xiàn)在考試試題中。具體包括進程同步的基本概念、實現(xiàn)臨界區(qū)互斥的括進程同步的基本概念、實現(xiàn)臨界區(qū)互斥的基本方法基本方法(包括軟件實現(xiàn)方法、硬件實現(xiàn)方包括軟

3、件實現(xiàn)方法、硬件實現(xiàn)方法法)、信號量、信號量(P、V操作操作)、管程、經(jīng)典同步、管程、經(jīng)典同步問題問題(包括生產(chǎn)者包括生產(chǎn)者-消費者問題、讀者消費者問題、讀者-寫者問寫者問題、哲學家進餐問題等題、哲學家進餐問題等)。我們一定要掌握。我們一定要掌握P、V操作的概念、流程，以及操作的概念、流程，以及P、V操作在同步操作在同步問題、互斥問題中的應用。問題、互斥問題中的應用。 進程管理是操作系統(tǒng)的重要任務之一是使用進程管理是操作系統(tǒng)的重要任務之一是使用戶充分、有效地利用系統(tǒng)資源，這部分：戶充分、有效地利用系統(tǒng)資源，這部分： 首先要求掌握進程的概念，其中進程和程序首先要求掌握進程的概念，其中進程和程序這

4、兩個概念的區(qū)別和聯(lián)系一定要搞清楚；這兩個概念的區(qū)別和聯(lián)系一定要搞清楚； 第二要記住進程的三個基本狀態(tài)以及它們之第二要記住進程的三個基本狀態(tài)以及它們之間相互轉(zhuǎn)換條件，一定要記住不可能從就緒間相互轉(zhuǎn)換條件，一定要記住不可能從就緒狀態(tài)直接轉(zhuǎn)換到等待狀態(tài)；狀態(tài)直接轉(zhuǎn)換到等待狀態(tài)； 第三需要理解進程控制和原語這兩個概念，第三需要理解進程控制和原語這兩個概念，掌握進程的創(chuàng)建、撤銷、阻塞、喚醒的條件，掌握進程的創(chuàng)建、撤銷、阻塞、喚醒的條件，理解四種原語的執(zhí)行過程；理解四種原語的執(zhí)行過程； 第四理解什么是并發(fā)進程間的直接制約以及由直第四理解什么是并發(fā)進程間的直接制約以及由直接制約所引發(fā)的進程同步，分清什么是私

5、用信號接制約所引發(fā)的進程同步，分清什么是私用信號和公用信息，重點要掌握如何用和公用信息，重點要掌握如何用P、V原語操作實原語操作實現(xiàn)同步問題，要會利用現(xiàn)同步問題，要會利用P、V原語操作來解決經(jīng)典原語操作來解決經(jīng)典的同步問題；的同步問題； 第五是知道進程的通信方式及它們各自的特點；第五是知道進程的通信方式及它們各自的特點； 第六要理解進程和線程的異同以及多線程模型；第六要理解進程和線程的異同以及多線程模型； 最后一定要弄清楚什么是死鎖產(chǎn)生的必要條件以最后一定要弄清楚什么是死鎖產(chǎn)生的必要條件以及如何預防和避免死鎖。及如何預防和避免死鎖。第二章第二章 進程管理進程管理2.1 進程的基本概念進程的基本

6、概念2.2 進程控制進程控制2.3 進程同步進程同步2.4 經(jīng)典進程的同步問題經(jīng)典進程的同步問題2.5 進程通信進程通信2.6 線程線程基礎(chǔ)知識總結(jié)基礎(chǔ)知識總結(jié)實戰(zhàn)練習實戰(zhàn)練習綜合應用題綜合應用題 操作系統(tǒng)在管理進程與線程的過程中需要完成以操作系統(tǒng)在管理進程與線程的過程中需要完成以下工作：用戶和系統(tǒng)進程的創(chuàng)建和刪除；進程的下工作：用戶和系統(tǒng)進程的創(chuàng)建和刪除；進程的調(diào)度；為進程的同步、通信、死鎖處理提供機制。調(diào)度；為進程的同步、通信、死鎖處理提供機制。 多道程序設計的提出多道程序設計的提出 其基本思想是在主存中同時存放多個用戶的作其基本思想是在主存中同時存放多個用戶的作業(yè)，使之同時處于運行狀態(tài)而

7、共享系統(tǒng)資源。之業(yè)，使之同時處于運行狀態(tài)而共享系統(tǒng)資源。之所以采用多道程序設計技術(shù)，是由于中斷和通道所以采用多道程序設計技術(shù)，是由于中斷和通道技術(shù)的出現(xiàn)，技術(shù)的出現(xiàn)，CPU可以把直接控制輸入可以把直接控制輸入/輸出的工輸出的工作轉(zhuǎn)給通道作轉(zhuǎn)給通道 多道程序的目標、方法和主要問題多道程序的目標、方法和主要問題目標：是充分使用系統(tǒng)所有資源并盡可能地使它們目標：是充分使用系統(tǒng)所有資源并盡可能地使它們并行工作，這種技術(shù)可把硬件的代價交叉分布在并行工作，這種技術(shù)可把硬件的代價交叉分布在大量并行用戶之間，而使計算機系統(tǒng)的代價極小大量并行用戶之間，而使計算機系統(tǒng)的代價極小化?；７椒ǎ菏且粋€正在運行的程序不

8、使用某設備時，讓方法：是一個正在運行的程序不使用某設備時，讓另一程序去使用該設備。為了發(fā)揮多道程序設計另一程序去使用該設備。為了發(fā)揮多道程序設計的有效性，應選擇各種不同類型的作業(yè)同時執(zhí)行，的有效性，應選擇各種不同類型的作業(yè)同時執(zhí)行，讓資源處于忙碌狀態(tài)。讓資源處于忙碌狀態(tài)。多道程序設計實現(xiàn)的多道程序設計實現(xiàn)的3個問題：存儲保護、程序浮個問題：存儲保護、程序浮動、處理機和系統(tǒng)資源的管理和調(diào)度。動、處理機和系統(tǒng)資源的管理和調(diào)度。 多道程序系統(tǒng)所必須解決的問題多道程序系統(tǒng)所必須解決的問題（1）提出解決各種沖突的策略）提出解決各種沖突的策略（2）協(xié)調(diào)并發(fā)活動的關(guān)系）協(xié)調(diào)并發(fā)活動的關(guān)系（3）保證數(shù)據(jù)的一致

9、性）保證數(shù)據(jù)的一致性（4）實現(xiàn)數(shù)據(jù)的存取控制）實現(xiàn)數(shù)據(jù)的存取控制2.1 進程的基本概念進程的基本概念2.1.1 程序的順序執(zhí)行及其特征：順序性、封閉程序的順序執(zhí)行及其特征：順序性、封閉性、可再現(xiàn)性。性、可再現(xiàn)性。2.1.2 前趨圖：描述進程之間執(zhí)行的前后關(guān)系。前趨圖：描述進程之間執(zhí)行的前后關(guān)系。2.1.3 程序的并發(fā)執(zhí)行及其特征：間斷性程序的并發(fā)執(zhí)行及其特征：間斷性(制約制約性性)、失去封閉性、不可再現(xiàn)性。、失去封閉性、不可再現(xiàn)性。2.1.4 進程的特征與狀態(tài)進程的特征與狀態(tài) 引入進程的目的：引入進程的目的：是使多個程序能并發(fā)是使多個程序能并發(fā)執(zhí)行，提高資源利用率和系統(tǒng)吞吐量執(zhí)行，提高資源利用

10、率和系統(tǒng)吞吐量。進程的定義：進程包括程序代進程的定義：進程包括程序代碼（程序段或文本段）、堆碼（程序段或文本段）、堆棧段（臨時數(shù)據(jù)，如函數(shù)參棧段（臨時數(shù)據(jù)，如函數(shù)參數(shù)、返回地址和局部變量）、數(shù)、返回地址和局部變量）、數(shù)據(jù)段（包括全局變量）、數(shù)據(jù)段（包括全局變量）、堆（進行運行期間動態(tài)分配堆（進行運行期間動態(tài)分配的內(nèi)存）的內(nèi)存） 內(nèi)存中的進程如右圖示：內(nèi)存中的進程如右圖示：棧棧堆堆數(shù)據(jù)數(shù)據(jù)文本文本(1)特征：特征： 結(jié)構(gòu)特征：程序段、相關(guān)的數(shù)據(jù)段和結(jié)構(gòu)特征：程序段、相關(guān)的數(shù)據(jù)段和PCB構(gòu)成的進程實體。構(gòu)成的進程實體。 動態(tài)性：最基本。動態(tài)性：最基本。 并發(fā)性：并發(fā)性： 獨立性：獨立性： 異步性：

11、進程以各自獨立的，不可預先的速度向前推進。異步性：進程以各自獨立的，不可預先的速度向前推進?？赡軙斐刹徽_的情況出現(xiàn)，原因與進程占用處理器的可能會造成不正確的情況出現(xiàn)，原因與進程占用處理器的時間、執(zhí)行的速度以及外界的影響有關(guān)，都與時間有關(guān)。時間、執(zhí)行的速度以及外界的影響有關(guān)，都與時間有關(guān)。稱為與時間有關(guān)的錯誤。稱為與時間有關(guān)的錯誤。 進程的定義：進程是進程實體的運行過程，是系統(tǒng)進行進程的定義：進程是進程實體的運行過程，是系統(tǒng)進行資源分配和調(diào)度的一個獨立單位。資源分配和調(diào)度的一個獨立單位。簡述進程和程序的區(qū)別和聯(lián)系簡述進程和程序的區(qū)別和聯(lián)系 (1)每個進程實體中包含了程序段和數(shù)據(jù)段，還包含了一

12、個數(shù)每個進程實體中包含了程序段和數(shù)據(jù)段，還包含了一個數(shù)據(jù)結(jié)構(gòu)據(jù)結(jié)構(gòu)PCB(2)進程是程序的一次執(zhí)行過程，是動態(tài)的，是有生命周期的。進程是程序的一次執(zhí)行過程，是動態(tài)的，是有生命周期的。程序是靜態(tài)的，是可以長期保存的。程序是靜態(tài)的，是可以長期保存的。(3)多個進程實體可同時存放在內(nèi)存中并發(fā)執(zhí)行。多個進程實體可同時存放在內(nèi)存中并發(fā)執(zhí)行。(4)進程是一個能夠獨立運行、獨立分配資和獨立接受調(diào)度的進程是一個能夠獨立運行、獨立分配資和獨立接受調(diào)度的基本單位。基本單位。(5)進程和程序不是一一對應的。進程和程序不是一一對應的。1對多或?qū)Χ嗷?對對1,通過多次執(zhí)行，通過多次執(zhí)行，一個程序可對應多個進程，通過調(diào)用

13、關(guān)系，一個進程可包一個程序可對應多個進程，通過調(diào)用關(guān)系，一個進程可包括多個括多個 程序。程序。 系統(tǒng)內(nèi)的進程能并發(fā)執(zhí)行，允許并發(fā)執(zhí)行的系統(tǒng)內(nèi)的進程能并發(fā)執(zhí)行，允許并發(fā)執(zhí)行的理由：信息共享，加快計算，模塊化和方便性。理由：信息共享，加快計算，模塊化和方便性。(2)進程的三種基本狀態(tài)：進程的三種基本狀態(tài)： 就緒狀態(tài)：三種情況的進程就緒狀態(tài)：三種情況的進程 執(zhí)行狀態(tài)：當前進程執(zhí)行狀態(tài)：當前進程 阻塞狀態(tài)：等待狀態(tài)、封鎖狀態(tài)、睡眠狀態(tài)。阻塞狀態(tài)：等待狀態(tài)、封鎖狀態(tài)、睡眠狀態(tài)。三種基本狀態(tài)之間的轉(zhuǎn)換：三種基本狀態(tài)之間的轉(zhuǎn)換：兩個基本隊列：就緒隊列和等待隊列。入隊和出隊。兩個基本隊列：就緒隊列和等待隊列。

14、入隊和出隊。(3)掛起狀態(tài)：終端用戶的請求，父進程請求，負荷掛起狀態(tài)：終端用戶的請求，父進程請求，負荷調(diào)節(jié)的需要，操作系統(tǒng)的需要。調(diào)節(jié)的需要，操作系統(tǒng)的需要。進程狀態(tài)的轉(zhuǎn)換：進程狀態(tài)的轉(zhuǎn)換：(4)創(chuàng)建狀態(tài)和終止狀態(tài)：創(chuàng)建狀態(tài)和終止狀態(tài)： 例例1：簡述三種基本狀態(tài)之間的轉(zhuǎn)換方向及原因：簡述三種基本狀態(tài)之間的轉(zhuǎn)換方向及原因：絕對不會出現(xiàn)的是從阻塞到執(zhí)行狀態(tài)的轉(zhuǎn)換。絕對不會出現(xiàn)的是從阻塞到執(zhí)行狀態(tài)的轉(zhuǎn)換。進程隊列：就緒隊列和等待隊列。入隊和出隊。進程隊列：就緒隊列和等待隊列。入隊和出隊。例例2：處于就緒隊列中的進程是由哪三種類型的進：處于就緒隊列中的進程是由哪三種類型的進程組成的程組成的解：解：（1

15、）新進程）新進程（2）因時間片用完而中斷運行的進程）因時間片用完而中斷運行的進程（3）因等待的條件發(fā)生而被喚醒的進程）因等待的條件發(fā)生而被喚醒的進程例例3：在一個只有單處理機的操作系統(tǒng)中，進程有運行、就緒、：在一個只有單處理機的操作系統(tǒng)中，進程有運行、就緒、等待三個基本狀態(tài)。假如某時刻操作系統(tǒng)中有等待三個基本狀態(tài)。假如某時刻操作系統(tǒng)中有10個進程并個進程并發(fā)執(zhí)行，且發(fā)執(zhí)行，且CPU以非核心態(tài)情況下，試問：以非核心態(tài)情況下，試問：（1）這時刻系統(tǒng)中處于運行狀態(tài)的進程數(shù)最多有幾個？最少）這時刻系統(tǒng)中處于運行狀態(tài)的進程數(shù)最多有幾個？最少有幾個？有幾個？（2）這時刻系統(tǒng)中處于就緒狀態(tài)的進程數(shù)最多有幾個

16、？最少）這時刻系統(tǒng)中處于就緒狀態(tài)的進程數(shù)最多有幾個？最少有幾個？有幾個？（3）這時刻系統(tǒng)中處于等待狀態(tài)的進程數(shù)最多有幾個？最少）這時刻系統(tǒng)中處于等待狀態(tài)的進程數(shù)最多有幾個？最少有幾個？有幾個？解：解：（1）因為系統(tǒng)中只有一個處理機，所以某時刻處于運行狀態(tài)）因為系統(tǒng)中只有一個處理機，所以某時刻處于運行狀態(tài)的進程數(shù)最多有的進程數(shù)最多有1個。而最少可能為個。而最少可能為0，此時其他，此時其他10個進程個進程一定全部排在各等待隊列中，在就緒隊列中沒有進程，在一定全部排在各等待隊列中，在就緒隊列中沒有進程，在實際的操作系統(tǒng)中，此時實際的操作系統(tǒng)中，此時CPU是在運行操作系統(tǒng)的空閑進是在運行操作系統(tǒng)的空閑

17、進程（程（System Idle Process）或線程。）或線程。（2）處于就緒狀態(tài)的進程數(shù)最多只有）處于就緒狀態(tài)的進程數(shù)最多只有9個，不可能個，不可能出現(xiàn)出現(xiàn)10個，因為一旦個，因為一旦CPU有空，調(diào)度程序馬上調(diào)有空，調(diào)度程序馬上調(diào)度；處于就緒狀態(tài)的進程數(shù)最少是度；處于就緒狀態(tài)的進程數(shù)最少是0個，個，1個進程個進程運行，運行，9個進程等待，或者個進程等待，或者10個進程全部等待。個進程全部等待。（3）處于等待狀態(tài)的進程數(shù)最多有）處于等待狀態(tài)的進程數(shù)最多有10個，等待狀個，等待狀態(tài)的進程最少是個。態(tài)的進程最少是個。例例3：某系統(tǒng)在：某系統(tǒng)在t0時刻，打印機剛剛打印完畢或者剛時刻，打印機剛剛打

18、印完畢或者剛剛開始打印，試問該時刻系統(tǒng)內(nèi)部發(fā)生了進程狀剛開始打印，試問該時刻系統(tǒng)內(nèi)部發(fā)生了進程狀態(tài)變化的情況如何？態(tài)變化的情況如何？2.1.5 進程控制塊：任務控制塊進程控制塊：任務控制塊1、PCB的作用：進程存在的惟一標志。的作用：進程存在的惟一標志。是使一個在多道是使一個在多道程序環(huán)境下不能獨立運行的程序，成為一個能獨程序環(huán)境下不能獨立運行的程序，成為一個能獨立運行的基本單位，一個能與其他進程并發(fā)執(zhí)行立運行的基本單位，一個能與其他進程并發(fā)執(zhí)行的進程。是進程存在的惟一標志。操作系統(tǒng)是根的進程。是進程存在的惟一標志。操作系統(tǒng)是根據(jù)據(jù)PCB來對并發(fā)執(zhí)行的進程進行控制和管理的。來對并發(fā)執(zhí)行的進程進

19、行控制和管理的。 2、PCB中的信息中的信息 (1)進程標識符：內(nèi)部和外部標識進程標識符：內(nèi)部和外部標識 (2)處理機狀態(tài)：通用寄存器、處理機狀態(tài)：通用寄存器、PC、PSW和用戶棧指針。和用戶棧指針。 (3)進程調(diào)度信息：進程狀態(tài)、進程優(yōu)先級、調(diào)度的其他信進程調(diào)度信息：進程狀態(tài)、進程優(yōu)先級、調(diào)度的其他信息、阻塞事件。息、阻塞事件。 (4)進程控制信息：程序和數(shù)據(jù)的地址、同步和通信機制、進程控制信息：程序和數(shù)據(jù)的地址、同步和通信機制、資源清單和鏈接指針。資源清單和鏈接指針。3、PCB的組織方式：鏈接和索引。的組織方式：鏈接和索引。進程上下文（進程上下文（Context）實際上是進程執(zhí)行活動全過程

20、的靜）實際上是進程執(zhí)行活動全過程的靜態(tài)描述。又稱進程映像。包括三個組成部分：態(tài)描述。又稱進程映像。包括三個組成部分：（1）用戶級上下文。由用戶程序代碼、用戶數(shù)據(jù)段（含共）用戶級上下文。由用戶程序代碼、用戶數(shù)據(jù)段（含共享數(shù)據(jù)塊）和用戶堆棧組成的進程地址空間。享數(shù)據(jù)塊）和用戶堆棧組成的進程地址空間。（2）系統(tǒng)級上下文。包括進程的標識信息、現(xiàn)場信息、控）系統(tǒng)級上下文。包括進程的標識信息、現(xiàn)場信息、控制信息、進程環(huán)境塊，以及系統(tǒng)堆棧等組成的進程地址空制信息、進程環(huán)境塊，以及系統(tǒng)堆棧等組成的進程地址空間。間。（3）寄存器上下文。由程序狀態(tài)字寄存器和各類控制寄存）寄存器上下文。由程序狀態(tài)字寄存器和各類控制

21、寄存器、地址寄存器、通用寄存器組成。器、地址寄存器、通用寄存器組成。Context switch發(fā)生在寄存器和內(nèi)存之間，依賴于內(nèi)存速度，發(fā)生在寄存器和內(nèi)存之間，依賴于內(nèi)存速度，復制的寄存器的數(shù)量，是否有特殊指令等。復制的寄存器的數(shù)量，是否有特殊指令等。 可再入程序是指一個能被多個用戶同時調(diào)用的程可再入程序是指一個能被多個用戶同時調(diào)用的程序：必須是純代碼，要求調(diào)用者提供工作區(qū)。序：必須是純代碼，要求調(diào)用者提供工作區(qū)。 中斷及中斷響應中斷及中斷響應 中斷是指中斷是指CPU對系統(tǒng)中發(fā)生的異步事件的響應或?qū)ο到y(tǒng)中發(fā)生的異步事件的響應或處理，異步事件是指無一定時序關(guān)系而隨機發(fā)生處理，異步事件是指無一定時

22、序關(guān)系而隨機發(fā)生的事件。的事件。 中斷的作用：充分發(fā)揮處理機的使用效率；提高中斷的作用：充分發(fā)揮處理機的使用效率；提高系統(tǒng)的實時處理的能力。系統(tǒng)的實時處理的能力。 中斷的功能：發(fā)現(xiàn)中斷源，提出中斷請求；保護中斷的功能：發(fā)現(xiàn)中斷源，提出中斷請求；保護現(xiàn)場；啟動并運行處理中斷事件的體育場。現(xiàn)場；啟動并運行處理中斷事件的體育場。 中斷優(yōu)先級是按中斷事件的重要性和緊迫中斷優(yōu)先級是按中斷事件的重要性和緊迫程序來確定的，是由硬件設計時固定下來程序來確定的，是由硬件設計時固定下來的。依次：的。依次：硬件故障中斷、自愿中斷、程硬件故障中斷、自愿中斷、程序性中斷、外部中斷和輸入序性中斷、外部中斷和輸入/輸出中斷

23、輸出中斷。 中斷屏蔽：中斷處理程序只能屏蔽比自己中斷屏蔽：中斷處理程序只能屏蔽比自己優(yōu)先級低的事件，并且不能屏蔽自愿中斷。優(yōu)先級低的事件，并且不能屏蔽自愿中斷。2.2 進程控制進程控制原語操作的定義：原語操作的定義：2.2.1 進程的創(chuàng)建進程的創(chuàng)建(1)進程圖：描述一個進程的家庭關(guān)系的有向圖。進程圖：描述一個進程的家庭關(guān)系的有向圖。(2)引起創(chuàng)建進程的事件：用戶登錄，作業(yè)調(diào)度，提引起創(chuàng)建進程的事件：用戶登錄，作業(yè)調(diào)度，提供服務和應用請求。供服務和應用請求。(3)進程的創(chuàng)建：申請空白進程的創(chuàng)建：申請空白PCB，為新進程分配資源，為新進程分配資源，初始化初始化PCB，將新進程插入就緒隊列。，將新進

24、程插入就緒隊列。(4)進程的創(chuàng)建請求系統(tǒng)為一個程序分配一個工作區(qū)進程的創(chuàng)建請求系統(tǒng)為一個程序分配一個工作區(qū)和建立一個進程控制塊和建立一個進程控制塊 當進程創(chuàng)建新進程時，有兩種執(zhí)行可能：當進程創(chuàng)建新進程時，有兩種執(zhí)行可能：（1）父進程與子進程并發(fā)執(zhí)行）父進程與子進程并發(fā)執(zhí)行（2）父進程等待，直到某個或全部子進程執(zhí)）父進程等待，直到某個或全部子進程執(zhí)行完。行完。 新進程的地址空間也有兩種可能新進程的地址空間也有兩種可能（1）子進程是父進程的復制品（具有與父進）子進程是父進程的復制品（具有與父進程相同的程序和數(shù)據(jù)）程相同的程序和數(shù)據(jù)）（2）子進程裝入另一個新程序）子進程裝入另一個新程序2.2.2 進

25、程的終止進程的終止(1)引起進程終止的事件：正常結(jié)束，異常結(jié)引起進程終止的事件：正常結(jié)束，異常結(jié)束和外界干預。束和外界干預。(2)進程的終止過程：檢索進程的終止過程：檢索PCB，判斷狀態(tài)，判斷狀態(tài)，撤銷子進程，歸還資源，清空撤銷子進程，歸還資源，清空PCB。(3)進程的撤消，系統(tǒng)收回該進程所用的工作進程的撤消，系統(tǒng)收回該進程所用的工作區(qū)，取消進程控制塊。區(qū)，取消進程控制塊。Exit()、TerminatePorcess() 父進程終止其子進程的原因父進程終止其子進程的原因（1）子進程使用了超過它所分配到的一些資）子進程使用了超過它所分配到的一些資源源（2）分配給子進程的任務已不再需要）分配給子

26、進程的任務已不再需要（3）父進程退出，如果父進程終止，操作系）父進程退出，如果父進程終止，操作系統(tǒng)不允許子進程繼續(xù)。級聯(lián)終止統(tǒng)不允許子進程繼續(xù)。級聯(lián)終止Cascading termination。VMS。2.2.3 進程的阻塞與喚醒進程的阻塞與喚醒(1)引起進程阻塞和喚醒的事件：請求系統(tǒng)服務，啟引起進程阻塞和喚醒的事件：請求系統(tǒng)服務，啟動某種操作，新數(shù)據(jù)尚未到達和無新工作可做。動某種操作，新數(shù)據(jù)尚未到達和無新工作可做。(2)進程阻塞過程：進程阻塞過程：(3)進程喚醒過程：進程喚醒過程：2.2.4 進程的掛起與激活進程的掛起與激活(1)進程的掛起進程的掛起(2)進程的激活過程進程的激活過程2.3

27、 進程同步與互斥進程同步與互斥2.3.1 進程同步的基本概念進程同步的基本概念并發(fā)進程間的關(guān)系可以是無關(guān)的，也可以是有交往的并發(fā)進程間的關(guān)系可以是無關(guān)的，也可以是有交往的。獨立進程或協(xié)作進程。獨立進程或協(xié)作進程。 1、兩種制約關(guān)系：、兩種制約關(guān)系： 間接制約關(guān)系：互斥間接制約關(guān)系：互斥 進程互斥是指當有若干個進程使用某一共享資源時，進程互斥是指當有若干個進程使用某一共享資源時，任何時刻最多只允許一個進程使用，而其他要使用任何時刻最多只允許一個進程使用，而其他要使用該資源的進程必須等待，直到占用資源者釋放該資該資源的進程必須等待，直到占用資源者釋放該資源。是進程間競爭共享資源的使用權(quán)，沒有固定的

28、源。是進程間競爭共享資源的使用權(quán)，沒有固定的必然關(guān)系。利用公用信號量必然關(guān)系。利用公用信號量 直接制約關(guān)系：同步直接制約關(guān)系：同步 進程同步是指并發(fā)進程之間存在一種制約進程同步是指并發(fā)進程之間存在一種制約關(guān)系，一個進程的執(zhí)行依賴另一個進程的關(guān)系，一個進程的執(zhí)行依賴另一個進程的消息，當一個進程沒有得到另一個進程的消息，當一個進程沒有得到另一個進程的消息時應等待，直到消息到達才被喚醒。消息時應等待，直到消息到達才被喚醒。涉及共享資源的并發(fā)進程之間有一種必然涉及共享資源的并發(fā)進程之間有一種必然的依賴關(guān)系。利用私用信號量。的依賴關(guān)系。利用私用信號量。 同步與互斥的混合問題：進程的互斥是進程同步與互斥的

29、混合問題：進程的互斥是進程間競爭共享資源的使用權(quán)，這種競爭沒有固定的間競爭共享資源的使用權(quán)，這種競爭沒有固定的必然關(guān)系；進程同步，涉及共享資源的并發(fā)進程必然關(guān)系；進程同步，涉及共享資源的并發(fā)進程之間有一種必然的依賴關(guān)系。之間有一種必然的依賴關(guān)系。 race condition競爭條件：多個內(nèi)核進程同時競爭條件：多個內(nèi)核進程同時活動，會發(fā)生競爭條件。如打開文件的內(nèi)核數(shù)據(jù)活動，會發(fā)生競爭條件。如打開文件的內(nèi)核數(shù)據(jù)結(jié)構(gòu)，內(nèi)存分配的數(shù)據(jù)結(jié)構(gòu)，維護進程列表及處結(jié)構(gòu)，內(nèi)存分配的數(shù)據(jù)結(jié)構(gòu)，維護進程列表及處理中斷處理程序的數(shù)據(jù)結(jié)構(gòu)。理中斷處理程序的數(shù)據(jù)結(jié)構(gòu)。 非搶占內(nèi)核式的系統(tǒng)中不會導致競爭非搶占內(nèi)核式的系統(tǒng)

30、中不會導致競爭條件，搶占內(nèi)核的系統(tǒng)可能會導致競爭條條件，搶占內(nèi)核的系統(tǒng)可能會導致競爭條件。搶占內(nèi)核比非搶占內(nèi)核更受歡迎。件。搶占內(nèi)核比非搶占內(nèi)核更受歡迎。Windows XP和和Windows 2000為非搶占式為非搶占式內(nèi)核，傳統(tǒng)的內(nèi)核，傳統(tǒng)的Unix和和Linux 2.6以前的內(nèi)核以前的內(nèi)核也是非搶占式的。也是非搶占式的。Linux 2.6以后，商用以后，商用Unix、Solaris是搶占內(nèi)核是搶占內(nèi)核2、臨界資源：一次只允許一個進程使用的資源。打、臨界資源：一次只允許一個進程使用的資源。打印機、磁帶機、消息緩沖隊列、變量、數(shù)組、緩沖印機、磁帶機、消息緩沖隊列、變量、數(shù)組、緩沖區(qū)等。又稱獨

31、享資源。區(qū)等。又稱獨享資源。 3、臨界區(qū)：實現(xiàn)互斥的方法：軟件和硬件方法、臨界區(qū)：實現(xiàn)互斥的方法：軟件和硬件方法4、同步機制的規(guī)則：空閑讓進，忙則等待，有限等、同步機制的規(guī)則：空閑讓進，忙則等待，有限等待和讓權(quán)等待。（在單處理機系統(tǒng)中是必須的，在待和讓權(quán)等待。（在單處理機系統(tǒng)中是必須的，在多處理機系統(tǒng)中不是必須的）多處理機系統(tǒng)中不是必須的） 實現(xiàn)同步的幾種方法實現(xiàn)同步的幾種方法1、禁止中斷：只適合單處理器環(huán)境，會出現(xiàn)餓死。、禁止中斷：只適合單處理器環(huán)境，會出現(xiàn)餓死。2、TestAndSet指令：不可分的原子操作指令：不可分的原子操作,可適用于可適用于多處理器環(huán)境。多處理器環(huán)境。Boolean

32、TestAndSet(boolean locked) if(locked) return true; else locked=true; return false; 3、Swap指令指令 boolean void Swap(boolean a,boolean b) boolean temp; temp=b; b=a; a=temp; 4、Dekker算法和算法和Peterson算法：基于軟件算法：基于軟件的兩個進程間的通信。的兩個進程間的通信。 Bakery算法，用于算法，用于N個進程間的通信個進程間的通信2.3.2 信號量機制信號量機制 1、整型信號量：、整型信號量：P、V操作操作 wait

33、(s):while s=0 do nothing; s=s-1;信號量的值不可能取負值。信號量的值不可能取負值。 signal(s):s=s+1; 又稱簡單信號量，二元信號量，二進制信號量，互又稱簡單信號量，二元信號量，二進制信號量，互斥鎖。斥鎖。缺點：忙等待方式缺點：忙等待方式busy waiting,自旋鎖（優(yōu)點：不自旋鎖（優(yōu)點：不進行上下文切換，常用于多處理系統(tǒng)）進行上下文切換，常用于多處理系統(tǒng)）2、記錄型信號量：、記錄型信號量： struct semaphore int:value; struct process *L; s; wait(s): s.value=s.value-1; i

34、f s.value0 then block(s.L); 信號量的遞減和測試次序的互換，其值可取負值。信號量的遞減和測試次序的互換，其值可取負值。 signal(s):s.value=s.value+1; if s.value=0 then wakeup(s.L);又稱計數(shù)信號量，資源信號量，用來控制又稱計數(shù)信號量，資源信號量，用來控制m個進程訪問某一個進程訪問某一類類n個臨界資源。個臨界資源。例例1記錄型信號量的物理含義：記錄型信號量的物理含義：例例2：設有：設有n個進程共享一個程序段，對于如個進程共享一個程序段，對于如下兩種情況：下兩種情況：（1）如果每次只允許一個進程進入該程序段。）如果每

35、次只允許一個進程進入該程序段。（2）如果每次最多允許）如果每次最多允許m個進程（個進程（m0)個單元的緩沖區(qū)。個單元的緩沖區(qū)。P1每次用每次用produce()生成一個正整數(shù)并用生成一個正整數(shù)并用put()送入緩送入緩沖區(qū)某一空單元中；沖區(qū)某一空單元中；P2每次用每次用getodd()從從該緩沖區(qū)中取出一個奇數(shù)并用該緩沖區(qū)中取出一個奇數(shù)并用countodd()統(tǒng)計奇數(shù)個數(shù)；統(tǒng)計奇數(shù)個數(shù)；P3每次用每次用geteven()從該緩從該緩沖區(qū)中取出一個偶數(shù)并沖區(qū)中取出一個偶數(shù)并counteven()統(tǒng)計偶統(tǒng)計偶數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程數(shù)個數(shù)。請用信號量機制實現(xiàn)這三個進程的同步與互斥活動，

36、并說明所定義信號量的同步與互斥活動，并說明所定義信號量的含義。要求用偽代碼描述。的含義。要求用偽代碼描述。 答案：定義信號量答案：定義信號量S1控制控制P1與與P2之間的同步；之間的同步；S2控制控制P1與與P3之間的同步；之間的同步；empty控制生產(chǎn)者與消費者之間的同步；控制生產(chǎn)者與消費者之間的同步；mutex控制進程間互斥使用緩沖區(qū)?？刂七M程間互斥使用緩沖區(qū)。程序如下：程序如下： Var s1=0,s2=0,empty=N,mutex=1; Parbegin P1:begin X=produce(); /*生成一個數(shù)生成一個數(shù)*/ P(empty);/*判斷緩沖區(qū)是否有空單元判斷緩沖區(qū)是

37、否有空單元*/ P(mutex); /*緩沖區(qū)是否被占用緩沖區(qū)是否被占用*/ put(x); If x%2=0 V(s2); /*如果是偶數(shù)，向如果是偶數(shù)，向P3發(fā)出信號發(fā)出信號*/ else V(s1); /*如果是奇數(shù)，向如果是奇數(shù)，向P2發(fā)出信號發(fā)出信號*/ V(mutex); /*使用完緩沖區(qū)，釋放使用完緩沖區(qū)，釋放*/ P2：begin P(s1); /*收到收到P1發(fā)來的信號，已產(chǎn)生一個奇數(shù)發(fā)來的信號，已產(chǎn)生一個奇數(shù)*/ P(mutex); /*緩沖區(qū)是否被占用緩沖區(qū)是否被占用*/ Getodd(); Countodd():=coutodd()+1; V(mutex); /*釋放緩

38、沖區(qū)釋放緩沖區(qū)*/ V(empty); /*向向P1發(fā)信號，多出一個空單元發(fā)信號，多出一個空單元*/ End. P3:begin P(s2); /*收到收到P1發(fā)來的信號，已產(chǎn)生一個偶數(shù)發(fā)來的信號，已產(chǎn)生一個偶數(shù)*/ P(mutex); /*緩沖區(qū)是否被占用緩沖區(qū)是否被占用*/ Geteven(); Counteven():=counteven()+1; V(mutex); /* 釋放緩沖區(qū)釋放緩沖區(qū)*/ V(empty); /*向向P1發(fā)信號，多出一個空單元發(fā)信號，多出一個空單元*/End.Parend.2.4.2 讀者和寫者問題：一直用來測試幾乎所有新讀者和寫者問題：一直用來測試幾乎所有新

39、的同步原語。多個用戶共享數(shù)據(jù)庫系統(tǒng)的建模問的同步原語。多個用戶共享數(shù)據(jù)庫系統(tǒng)的建模問題。有多種不同的策略，都與優(yōu)先級有關(guān)。題。有多種不同的策略，都與優(yōu)先級有關(guān)。 1、讀者優(yōu)先：第一讀者、讀者優(yōu)先：第一讀者-寫者問題，寫者可能饑餓。寫者問題，寫者可能饑餓。 2、排隊策略或先來先服務、排隊策略或先來先服務 3、寫者優(yōu)先：第二讀者、寫者優(yōu)先：第二讀者-寫者問題，讀者可能饑餓。寫者問題，讀者可能饑餓。 4、某個進程即是寫者又是讀者的問題、某個進程即是寫者又是讀者的問題例：設有例：設有P1,P2,P3三個進程共享某一資源三個進程共享某一資源F，P1對對F只讀不寫，只讀不寫，P2對對F只寫不讀，只寫不讀，

40、P3對對F先讀后寫。當一個進程寫先讀后寫。當一個進程寫F時，其他進程對時，其他進程對F不能進行讀寫，但多個進程同時讀不能進行讀寫，但多個進程同時讀F是允是允許的。試用許的。試用P、V操作正確實現(xiàn)操作正確實現(xiàn)P1,P2,P3的的同步互斥。要求：同步互斥。要求：（1）正常運行時不產(chǎn)生死鎖）正常運行時不產(chǎn)生死鎖（2）使用）使用F的并發(fā)度要高。（北京大學的并發(fā)度要高。（北京大學1996年研究生試題）年研究生試題） 解：本題實際上是一個讀者和寫者問題，解：本題實際上是一個讀者和寫者問題，P1是一個讀者，是一個讀者，P2是一個寫者，為了使是一個寫者，為了使F的并的并發(fā)度較高，將發(fā)度較高，將P3先看成讀者，

41、當其完成讀先看成讀者，當其完成讀操作后，再將其看成寫者。操作后，再將其看成寫者。 定義如下變量：定義如下變量： int readcount=0; semaphore rmutex=1,mutex=1; P1( ) While(1) P(rmutex); If(readcount=0)P(mutex); Readcount+; V(rmutex); 讀讀F； P（rmutex）; Readcount-; If(readcount=0)V(mutex); V(rmutex);P2() While(1) P(mutex); 寫寫F； V（mutex）;P3() While(1) P(rmtex);

42、If(readcount=0)P(mutex); Readcount+; V(rmutex); 讀讀F； P（rmutex）; Readcount-; If(readcount=0)V（mutex）; V(rmutex); P(mutex); 寫寫F； V（mutex）; 2.4.3 哲學家進餐問題：是一個并發(fā)控制問題，在多哲學家進餐問題：是一個并發(fā)控制問題，在多個進程之間分配多個資源且不會出現(xiàn)死鎖和饑餓的個進程之間分配多個資源且不會出現(xiàn)死鎖和饑餓的問題。問題。方法：方法： 1、同時允許四個哲學家提出進餐要求、同時允許四個哲學家提出進餐要求 2、同時去拿起兩邊的筷子、同時去拿起兩邊的筷子 3、

43、使用非對稱解決方法，奇數(shù)號哲學家先拿左邊、使用非對稱解決方法，奇數(shù)號哲學家先拿左邊的筷子，偶數(shù)號哲學家先拿右邊的筷子的筷子，偶數(shù)號哲學家先拿右邊的筷子注意：沒有死鎖的解決方案并不能消除餓死的可能性。注意：沒有死鎖的解決方案并不能消除餓死的可能性。2.4.4 理發(fā)師嗜睡問題理發(fā)師嗜睡問題 一個理發(fā)店由一個有一個理發(fā)店由一個有N張椅子的等候室和一張椅子的等候室和一個放有一張理發(fā)椅的理發(fā)室組成。若沒有要理發(fā)個放有一張理發(fā)椅的理發(fā)室組成。若沒有要理發(fā)的顧客，則理發(fā)師就去睡覺，若一個顧客走進理的顧客，則理發(fā)師就去睡覺，若一個顧客走進理發(fā)店且所有的椅子都被占用了，則該顧客就離開發(fā)店且所有的椅子都被占用了，

44、則該顧客就離開理發(fā)店，若理發(fā)師正在為人理發(fā)，則該顧客就找理發(fā)店，若理發(fā)師正在為人理發(fā)，則該顧客就找一張空椅子坐下等待，若理發(fā)師在睡覺，則顧客一張空椅子坐下等待，若理發(fā)師在睡覺，則顧客就喚醒他。就喚醒他。 試用信號量設計一個協(xié)調(diào)理發(fā)師和顧客的程序。試用信號量設計一個協(xié)調(diào)理發(fā)師和顧客的程序。（西安電子科技大學（西安電子科技大學2000年研究生試題）年研究生試題） 解：本題中，顧客進程和理發(fā)師進程之間存在著多解：本題中，顧客進程和理發(fā)師進程之間存在著多種同步關(guān)系：種同步關(guān)系：（1）只有在理發(fā)椅空閑時，顧客才能坐到理發(fā)椅）只有在理發(fā)椅空閑時，顧客才能坐到理發(fā)椅上等待理發(fā)師理發(fā)，否則顧客便必須等待；只有

45、上等待理發(fā)師理發(fā)，否則顧客便必須等待；只有當理發(fā)椅上有顧客時，理發(fā)師才可以開始理發(fā)，當理發(fā)椅上有顧客時，理發(fā)師才可以開始理發(fā)，否則他也必須等待。這種同步關(guān)系類似于單緩沖否則他也必須等待。這種同步關(guān)系類似于單緩沖（理發(fā)椅）的生產(chǎn)者和消費者問題中的同步關(guān)系，（理發(fā)椅）的生產(chǎn)者和消費者問題中的同步關(guān)系，故可以通過信號量故可以通過信號量empty(初值為初值為1)和和full(初值為初值為0)來控制。來控制。（2）理發(fā)師為顧客理發(fā)時，顧客必須等待理發(fā)的）理發(fā)師為顧客理發(fā)時，顧客必須等待理發(fā)的完成，并在理發(fā)完成后由理發(fā)師喚醒他，這可單完成，并在理發(fā)完成后由理發(fā)師喚醒他，這可單獨使用一個信號量獨使用一個信

46、號量cut來控制，初值為來控制，初值為0。 （3）顧客理完發(fā)后必須向理發(fā)師付費，并等理發(fā)師收費后）顧客理完發(fā)后必須向理發(fā)師付費，并等理發(fā)師收費后顧客才能離開；而理發(fā)師則需等待顧客付費，并在收費后顧客才能離開；而理發(fā)師則需等待顧客付費，并在收費后喚醒顧客以允許他離開，這可分別通過兩個信號量喚醒顧客以允許他離開，這可分別通過兩個信號量payment和和receipt來控制，初值都為來控制，初值都為0。（4）等候室中的）等候室中的N張沙發(fā)是顧客進程競爭的資源，故還需為張沙發(fā)是顧客進程競爭的資源，故還需為它們設置了一個資源信號量它們設置了一個資源信號量sofa，初值為，初值為n（5）為了控制顧客的人數(shù)

47、，使顧客能在所有的沙發(fā)都被占）為了控制顧客的人數(shù)，使顧客能在所有的沙發(fā)都被占用時離開理發(fā)店，還必須設置一個整型變量用時離開理發(fā)店，還必須設置一個整型變量count來對理來對理發(fā)店中的顧客進行計數(shù)，該變量將被多個顧客進程互斥地發(fā)店中的顧客進行計數(shù)，該變量將被多個顧客進程互斥地訪問并修改，這可通過一個互斥信號量訪問并修改，這可通過一個互斥信號量mutex來實現(xiàn)，初來實現(xiàn)，初值為值為1Guestbegin wait(mutex); if(countN)then begin signal(muetx); 離開理發(fā)店; end else begin count=count+1; if(count1) t

48、hen begin wait(sofa); 在沙發(fā)中就座在沙發(fā)中就座; wait(empty); 從沙發(fā)上起來從沙發(fā)上起來; signal(sofa); end else /*count=1*/ wait(empty); 在理發(fā)椅上就座在理發(fā)椅上就座; signal(full); wait(cut); 理發(fā)；理發(fā)； 付費；付費； signal(payment); wait(receipt); 從理發(fā)椅上起來從理發(fā)椅上起來; signal(empty); wait(mutex); count=count-1; signal(mutex); 離開理發(fā)店離開理發(fā)店; end endbarber:be

49、gin repeat wait(full); 替顧客理發(fā)替顧客理發(fā); signal(cut); wait(payment); 收費收費; signal(receipt); until false; endparendend 2.4.5 “吸煙者吸煙者”問題。假設一個系統(tǒng)有問題。假設一個系統(tǒng)有3個吸煙者個吸煙者（smoker）進程和一個供貨商（）進程和一個供貨商（Agent）進程。）進程。每個吸煙者連續(xù)不斷地制造香煙并吸掉它。每個吸煙者連續(xù)不斷地制造香煙并吸掉它。 但是，制造一支香煙需要但是，制造一支香煙需要3種材料種材料煙、紙、煙、紙、火柴。一個吸煙者進程有紙，另一個有煙，第三個火柴。一個吸煙

50、者進程有紙，另一個有煙，第三個有火柴。供貨商進程可以無限地提供這有火柴。供貨商進程可以無限地提供這3種材料。種材料。供貨商將這這兩種材料一起放在桌上，持有另一種供貨商將這這兩種材料一起放在桌上，持有另一種材料的吸煙者即可制造一支香煙并吸掉它。當此吸材料的吸煙者即可制造一支香煙并吸掉它。當此吸煙者抽香煙時，它發(fā)出一個信號通知供貨商進程，煙者抽香煙時，它發(fā)出一個信號通知供貨商進程，供貨商馬上給出另外兩種材料，如此循環(huán)往復。試供貨商馬上給出另外兩種材料，如此循環(huán)往復。試編寫一個程序使供貨商和吸煙者同步執(zhí)行。編寫一個程序使供貨商和吸煙者同步執(zhí)行。解法：解法：semaphore smoker30; 三個

51、吸煙者三個吸煙者semaphore material30; 三種原料三種原料semaphore agent1; 供應商供應商int turn=0;輪到誰輪到誰Main()CobeginAgent While(1) P(agent); 放原料；放原料； V(smokerturn); V(material(turn+1)%3); V(material(turn+2)%3); turn=(turn+1)%3Smoker_i While(1) P(smokeri); P(material(i+1)%3); P(material(i+2)%3); 制作香煙；制作香煙； 吸煙；吸煙； V(agent);

52、coend;參考算法參考算法供應者供應者seller隨即產(chǎn)生兩樣東西，提供它們，這里用普通變量隨即產(chǎn)生兩樣東西，提供它們，這里用普通變量來表示來表示（1） 吸煙者進程吸煙者進程smoker根據(jù)其排號不同，擁有不同的一件東根據(jù)其排號不同，擁有不同的一件東西。假設西。假設1號吸煙者擁有煙草號吸煙者擁有煙草tobacco，2號吸煙者擁有紙?zhí)栁鼰熣邠碛屑坧aper，3號吸煙者擁有火柴號吸煙者擁有火柴match。其他號碼錯誤返回。其他號碼錯誤返回。（2） 吸煙者的序號代表他們擁有的東西，用他們的序號和供吸煙者的序號代表他們擁有的東西，用他們的序號和供應者產(chǎn)生的兩樣東西比較，如果都不相等，則說明他擁有的應

53、者產(chǎn)生的兩樣東西比較，如果都不相等，則說明他擁有的東西和供應者產(chǎn)生的東西匹配，它可以吸煙。如果其中一個東西和供應者產(chǎn)生的東西匹配，它可以吸煙。如果其中一個相等，則推出，繼續(xù)排隊。相等，則推出，繼續(xù)排隊。（3） mutex信號量代表一個只能進入的門，每次只有一個吸信號量代表一個只能進入的門，每次只有一個吸煙者可以進入進行比較和吸煙。煙者可以進入進行比較和吸煙。（4） 每個吸煙者在吸煙完畢之后出門之前要叫醒供應者，調(diào)每個吸煙者在吸煙完畢之后出門之前要叫醒供應者，調(diào)用用seller進程。進程。vars , S1 ,S2 , S3 ; semaphore ;S:=1 ; S1:=S2:=S3:=0 ;

54、fiag1 , flag2 , fiag3 : Boolean ;fiag1:=flag2:=flag3:=true;cobeginprocess 供應者供應者beginrepeatP(S) ;取兩樣香煙原料放桌上，由取兩樣香煙原料放桌上，由flagi標記；標記；/nago1 、nage2 、nage3 代表煙草、紙、火柴代表煙草、紙、火柴if flag2 & flag3 then V(S1) ; /供紙和火柴供紙和火柴else if flag1 & fiag3 then V(S2); /供煙草和火柴供煙草和火柴else V(S3) ; /供煙草和紙供煙草和紙untile false ;end

55、process 吸煙者吸煙者1beginrepeatP(S1) ;取原料；取原料；做香煙；做香煙；V(S) ;吸香煙；吸香煙；untile false ;endprocess 吸煙者吸煙者2beginrepeatp(S2);取原料；取原料；做香煙；做香煙；V(S) ;吸香煙；吸香煙；untile false ;endprocess 吸煙者吸煙者3beginrepeatP(S3);取原料；取原料；做香煙；做香煙；V(S);吸香煙；吸香煙；untile false ;endcoend變型變型1抽煙問題：有一個煙草代理和三個抽煙者。抽煙問題：有一個煙草代理和三個抽煙者。抽煙者若要抽煙，必須具有煙葉、

56、煙紙和抽煙者若要抽煙，必須具有煙葉、煙紙和火柴。三個抽煙者中，一人缺煙葉、一人火柴。三個抽煙者中，一人缺煙葉、一人缺煙紙、一人缺火柴。煙草代理會源源不缺煙紙、一人缺火柴。煙草代理會源源不斷地分別供應煙葉、煙紙和火柴，并將它斷地分別供應煙葉、煙紙和火柴，并將它們放在桌上。如果放的是煙葉，則缺煙葉們放在桌上。如果放的是煙葉，則缺煙葉的抽煙者拾起煙葉，制作香煙，然后抽煙；的抽煙者拾起煙葉，制作香煙，然后抽煙；其他類推。試用信號量同步煙草代理和三其他類推。試用信號量同步煙草代理和三個抽煙者。個抽煙者。解法：解法：semaphore smoker30; 三個吸煙者三個吸煙者semaphore mater

57、ial30; 三種原料三種原料semaphore agent1; 供應商供應商int turn=0;輪到誰輪到誰Agent While(1) P(agent); 放原料；放原料； V(smokerturn); V(material(turn+1)%3); 制作香煙；制作香煙； 吸煙；吸煙； turn=(turn+1)%3Smoker_i While(1) P(smokeri); P(material(i+1)%3); 制作香煙；制作香煙； 吸煙；吸煙； V(agent); 變型變型2有一間酒吧里有有一間酒吧里有3個音樂愛好者隊列，第個音樂愛好者隊列，第1隊的音樂隊的音樂愛好者只有隨身聽，第愛好

58、者只有隨身聽，第2隊只有音樂磁帶，第隊只有音樂磁帶，第3隊隊只有電池。而要聽音樂就必須隨身聽、音樂磁帶只有電池。而要聽音樂就必須隨身聽、音樂磁帶和電池這和電池這3種物品俱全。酒吧老板一次出售這種物品俱全。酒吧老板一次出售這3種種物品中的任意兩種。當一名音樂愛好者得到這物品中的任意兩種。當一名音樂愛好者得到這3種物品并聽完一首樂曲后，酒吧老板才能再一次種物品并聽完一首樂曲后，酒吧老板才能再一次出售這出售這3種物品中的任意兩種，于是第種物品中的任意兩種，于是第2名音樂愛名音樂愛好者得到這好者得到這3種物品，并開始聽樂曲。全部買賣種物品，并開始聽樂曲。全部買賣就這樣進行下去。就這樣進行下去。試用試用

59、P、V操作正確解決這一買賣。（北京大學操作正確解決這一買賣。（北京大學1999年研究生試題）年研究生試題）變型變型3（桔子汁生產(chǎn)線問題）現(xiàn)有三個生產(chǎn)者（桔子汁生產(chǎn)線問題）現(xiàn)有三個生產(chǎn)者P1 、P2 、P3 ，他們都要生產(chǎn)水，每個生產(chǎn)者都已分別購得，他們都要生產(chǎn)水，每個生產(chǎn)者都已分別購得兩種不同原料，待購得第三種原料后就可配制成兩種不同原料，待購得第三種原料后就可配制成桔子水，裝瓶出售。有一供應商能源源不斷地供桔子水，裝瓶出售。有一供應商能源源不斷地供應糖、水、桔子精，但每次只拿出一種原料放入應糖、水、桔子精，但每次只拿出一種原料放入容器中供給生產(chǎn)者。當容器中有原料時需要該原容器中供給生產(chǎn)者。當

60、容器中有原料時需要該原料的生產(chǎn)者可取走，當容器空時供應商又可放入料的生產(chǎn)者可取走，當容器空時供應商又可放入一種原料。假定：生產(chǎn)者一種原料。假定：生產(chǎn)者P1已購得糖和水；生產(chǎn)已購得糖和水；生產(chǎn)者者P2 已購得水和桔子精；生產(chǎn)者已購得水和桔子精；生產(chǎn)者P3 已購得糖和已購得糖和桔子精；試用：信號量與桔子精；試用：信號量與P 、v 操作，寫出供應操作，寫出供應商和三個生產(chǎn)者之間能正確同步的程序商和三個生產(chǎn)者之間能正確同步的程序 2.4.6 銀行排隊問題銀行排隊問題(北京大學北京大學2000）銀行有）銀行有n個柜個柜員員,每個顧客進入銀行后先取一個號每個顧客進入銀行后先取一個號,并且等著叫并且等著叫號