計(jì)算機(jī)操作系統(tǒng)考研輔導(dǎo)--第二章

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

30、中不會(huì)導(dǎo)致競爭條件，搶占內(nèi)核的系統(tǒng)可能會(huì)導(dǎo)致競爭條條件，搶占內(nèi)核的系統(tǒng)可能會(huì)導(dǎo)致競爭條件。搶占內(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、臨界資源：一次只允許一個(gè)進(jìn)程使用的資源。打、臨界資源：一次只允許一個(gè)進(jìn)程使用的資源。打印機(jī)、磁帶機(jī)、消息緩沖隊(duì)列、變量、數(shù)組、緩沖印機(jī)、磁帶機(jī)、消息緩沖隊(duì)列、變量、數(shù)組、緩沖區(qū)等。又稱獨(dú)

31、享資源。區(qū)等。又稱獨(dú)享資源。 3、臨界區(qū)：實(shí)現(xiàn)互斥的方法：軟件和硬件方法、臨界區(qū)：實(shí)現(xiàn)互斥的方法：軟件和硬件方法4、同步機(jī)制的規(guī)則：空閑讓進(jìn)，忙則等待，有限等、同步機(jī)制的規(guī)則：空閑讓進(jìn)，忙則等待，有限等待和讓權(quán)等待。（在單處理機(jī)系統(tǒng)中是必須的，在待和讓權(quán)等待。（在單處理機(jī)系統(tǒng)中是必須的，在多處理機(jī)系統(tǒng)中不是必須的）多處理機(jī)系統(tǒng)中不是必須的） 實(shí)現(xiàn)同步的幾種方法實(shí)現(xiàn)同步的幾種方法1、禁止中斷：只適合單處理器環(huán)境，會(huì)出現(xiàn)餓死。、禁止中斷：只適合單處理器環(huán)境，會(huì)出現(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算法：基于軟件算法：基于軟件的兩個(gè)進(jìn)程間的通信。的兩個(gè)進(jìn)程間的通信。 Bakery算法，用于算法，用于N個(gè)進(jìn)程間的通信個(gè)進(jìn)程間的通信2.3.2 信號(hào)量機(jī)制信號(hào)量機(jī)制 1、整型信號(hào)量：、整型信號(hào)量：P、V操作操作 wait

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

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

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

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

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

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

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

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

41、當(dāng)其完成讀先看成讀者，當(dāng)其完成讀操作后，再將其看成寫者。操作后，再將其看成寫者。 定義如下變量：定義如下變量： 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 哲學(xué)家進(jìn)餐問題：是一個(gè)并發(fā)控制問題，在多哲學(xué)家進(jìn)餐問題：是一個(gè)并發(fā)控制問題，在多個(gè)進(jìn)程之間分配多個(gè)資源且不會(huì)出現(xiàn)死鎖和饑餓的個(gè)進(jìn)程之間分配多個(gè)資源且不會(huì)出現(xiàn)死鎖和饑餓的問題。問題。方法：方法： 1、同時(shí)允許四個(gè)哲學(xué)家提出進(jìn)餐要求、同時(shí)允許四個(gè)哲學(xué)家提出進(jìn)餐要求 2、同時(shí)去拿起兩邊的筷子、同時(shí)去拿起兩邊的筷子 3、

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

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

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

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

47、，使顧客能在所有的沙發(fā)都被占）為了控制顧客的人數(shù)，使顧客能在所有的沙發(fā)都被占用時(shí)離開理發(fā)店，還必須設(shè)置一個(gè)整型變量用時(shí)離開理發(fā)店，還必須設(shè)置一個(gè)整型變量count來對(duì)理來對(duì)理發(fā)店中的顧客進(jìn)行計(jì)數(shù)，該變量將被多個(gè)顧客進(jìn)程互斥地發(fā)店中的顧客進(jìn)行計(jì)數(shù)，該變量將被多個(gè)顧客進(jìn)程互斥地訪問并修改，這可通過一個(gè)互斥信號(hào)量訪問并修改，這可通過一個(gè)互斥信號(hào)量mutex來實(shí)現(xiàn)，初來實(shí)現(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ā)； 付費(fèi)；付費(fèi)； 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); 收費(fèi)收費(fèi); signal(receipt); until false; endparendend 2.4.5 “吸煙者吸煙者”問題。假設(shè)一個(gè)系統(tǒng)有問題。假設(shè)一個(gè)系統(tǒng)有3個(gè)吸煙者個(gè)吸煙者（smoker）進(jìn)程和一個(gè)供貨商（）進(jìn)程和一個(gè)供貨商（Agent）進(jìn)程。）進(jìn)程。每個(gè)吸煙者連續(xù)不斷地制造香煙并吸掉它。每個(gè)吸煙者連續(xù)不斷地制造香煙并吸掉它。 但是，制造一支香煙需要但是，制造一支香煙需要3種材料種材料煙、紙、煙、紙、火柴。一個(gè)吸煙者進(jìn)程有紙，另一個(gè)有煙，第三個(gè)火柴。一個(gè)吸煙

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

51、吸煙者三個(gè)吸煙者semaphore material30; 三種原料三種原料semaphore agent1; 供應(yīng)商供應(yīng)商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;參考算法參考算法供應(yīng)者供應(yīng)者seller隨即產(chǎn)生兩樣?xùn)|西，提供它們，這里用普通變量隨即產(chǎn)生兩樣?xùn)|西，提供它們，這里用普通變量來表示來表示（1） 吸煙者進(jìn)程吸煙者進(jìn)程smoker根據(jù)其排號(hào)不同，擁有不同的一件東根據(jù)其排號(hào)不同，擁有不同的一件東西。假設(shè)西。假設(shè)1號(hào)吸煙者擁有煙草號(hào)吸煙者擁有煙草tobacco，2號(hào)吸煙者擁有紙?zhí)栁鼰熣邠碛屑坧aper，3號(hào)吸煙者擁有火柴號(hào)吸煙者擁有火柴match。其他號(hào)碼錯(cuò)誤返回。其他號(hào)碼錯(cuò)誤返回。（2） 吸煙者的序號(hào)代表他們擁有的東西，用他們的序號(hào)和供吸煙者的序號(hào)代表他們擁有的東西，用他們的序號(hào)和供應(yīng)者產(chǎn)生的兩樣?xùn)|西比較，如果都不相等，則說明他擁有的應(yīng)

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

54、fiag1 , flag2 , fiag3 : Boolean ;fiag1:=flag2:=flag3:=true;cobeginprocess 供應(yīng)者供應(yīng)者beginrepeatP(S) ;取兩樣香煙原料放桌上，由取兩樣香煙原料放桌上，由flagi標(biāo)記；標(biāo)記；/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抽煙問題：有一個(gè)煙草代理和三個(gè)抽煙者。抽煙問題：有一個(gè)煙草代理和三個(gè)抽煙者。抽煙者若要抽煙，必須具有煙葉、

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

57、ial30; 三種原料三種原料semaphore agent1; 供應(yīng)商供應(yīng)商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個(gè)音樂愛好者隊(duì)列，第個(gè)音樂愛好者隊(duì)列，第1隊(duì)的音樂隊(duì)的音樂愛好者只有隨身聽，第愛好

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

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

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