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

1、計(jì)算機(jī)操作系統(tǒng)第二章 進(jìn)程管理（進(jìn)程同步與互斥）2009年1個選擇、1個綜合應(yīng)用題2010年3個選擇2011年2個選擇，1個綜合應(yīng)用題2012年2個選擇2013年2個選擇,1個同步算法設(shè)計(jì)題 進(jìn)程管理是本課程的重點(diǎn)章節(jié)，這部分介紹的是操作系統(tǒng)5大管理功能之一：處理機(jī)管理，包括進(jìn)程管理和處理機(jī)調(diào)度兩大塊的內(nèi)容。本章是學(xué)習(xí)和考試的重點(diǎn)內(nèi)容，同時也是難點(diǎn)。這部分除了要掌握基本的概念和基本的原理外，還要求能運(yùn)用這些基本原理去分析和解決問題。 進(jìn)程同步與互斥是進(jìn)程管理的重點(diǎn)，也是操作系統(tǒng)學(xué)科的一個難點(diǎn)。 具體包括:進(jìn)程同步的基本概念、實(shí)現(xiàn)臨界區(qū)互斥的基本方法(包括軟件實(shí)現(xiàn)方法、硬件實(shí)現(xiàn)方法)、信號量(P

2、、V操作)、管程、經(jīng)典同步問題(包括生產(chǎn)者-消費(fèi)者問題、讀者-寫者問題、哲學(xué)家進(jìn)餐問題等)。我們一定要掌握P、V操作的概念、流程，以及P、V操作在同步問題、互斥問題中的應(yīng)用。 首先,要求掌握進(jìn)程的概念，其中進(jìn)程和程序這兩個概念的區(qū)別和聯(lián)系一定要搞清楚。第二,要記住進(jìn)程的三個基本狀態(tài)以及它們之間相互轉(zhuǎn)換條件，一定要記住不可能從就緒狀態(tài)直接轉(zhuǎn)換到等待狀態(tài)。第三,需要理解進(jìn)程控制和原語這兩個概念，掌握進(jìn)程的創(chuàng)建、撤銷、阻塞、喚醒的條件，理解四種原語的執(zhí)行過程。第四,理解什么是并發(fā)進(jìn)程間的直接制約以及由直接制約所引發(fā)的進(jìn)程同步，重點(diǎn)要掌握如何用P、V原語操作實(shí)現(xiàn)同步問題，要會利用P、V原語操作來解決經(jīng)

3、典的同步問題；第五,了解進(jìn)程的通信方式及它們各自的特點(diǎn)；第六,要理解進(jìn)程和線程的異同以及多線程模型；第二章 進(jìn)程管理2.1 進(jìn)程的基本概念2.2 進(jìn)程控制2.3 進(jìn)程同步2.4 經(jīng)典進(jìn)程的同步問題2.5 進(jìn)程通信2.6 線程基礎(chǔ)知識總結(jié)實(shí)戰(zhàn)練習(xí)綜合應(yīng)用題操作系統(tǒng)在管理進(jìn)程與線程的過程中需要完成以下工作：（1）用戶和系統(tǒng)進(jìn)程的創(chuàng)建和刪除；（2）進(jìn)程的調(diào)度；（3）為進(jìn)程的同步、通信、死鎖處理提供機(jī)制。多道程序設(shè)計(jì)的提出 其基本思想是在主存中同時存放多個用戶的作業(yè)，使之同時處于運(yùn)行狀態(tài)而共享系統(tǒng)資源。宏觀上是并行運(yùn)行，微觀上是依次輪流迸發(fā)運(yùn)行的。操作系統(tǒng)的定義：操作系統(tǒng)是指控制和管理計(jì)算機(jī)的軟、硬件

4、資源，合理地組織計(jì)算機(jī)的工作流程，為程序的運(yùn)行提供一個良好環(huán)境，方便用戶使用的程序集合。之所以采用多道程序設(shè)計(jì)技術(shù)，是由于中斷和通道技術(shù)的出現(xiàn)，CPU可以把直接控制輸入/輸出的工作轉(zhuǎn)給通道。多道程序的目標(biāo)、方法和主要問題（1）目標(biāo)：是充分使用系統(tǒng)所有資源并盡可能地使它們并行工作，這種技術(shù)可把硬件的代價交叉分布在大量并行用戶之間，而使計(jì)算機(jī)系統(tǒng)的代價極小化。（2）方法：是一個正在運(yùn)行的程序不使用某設(shè)備時，讓另一程序去使用該設(shè)備。為了發(fā)揮多道程序設(shè)計(jì)的有效性，應(yīng)選擇各種不同類型的作業(yè)同時執(zhí)行，讓資源處于忙碌狀態(tài)。（3）多道程序設(shè)計(jì)實(shí)現(xiàn)的3個問題：存儲保護(hù)、程序浮動、處理機(jī)和系統(tǒng)資源的管理和調(diào)度。

5、多道程序系統(tǒng)所必須解決的問題（1）提出解決各種沖突的策略（2）協(xié)調(diào)并發(fā)活動的關(guān)系（3）保證數(shù)據(jù)的一致性（4）實(shí)現(xiàn)數(shù)據(jù)的存取控制2.1 進(jìn)程的基本概念2.1.1 程序的順序執(zhí)行及其特征：順序性、封閉性、可再現(xiàn)性。作業(yè)1：什么叫程序順序執(zhí)行的封閉性和可再現(xiàn)性？封閉性：程序執(zhí)行得到的最終結(jié)果由給定的初始條件決定，不受外界因素的影響?？稍佻F(xiàn)性：只要輸入的初始條件相同，則無論何時重復(fù)執(zhí)行該程序都會得到相同的結(jié)果。2.1.2 前趨圖：有向無循環(huán)圖，DAG（Directed Acyclic Graph），描述進(jìn)程之間執(zhí)行的前后關(guān)系。直接制約關(guān)系：同步間接制約關(guān)系：互斥2.1.3 程序的并發(fā)執(zhí)行及其特征：間斷

6、性(制約性)、失去封閉性、不可再現(xiàn)性（不可重復(fù)，例：變量的共享）。2.1.4 進(jìn)程的特征與狀態(tài) 引入進(jìn)程的目的：是使多個程序能并發(fā)執(zhí)行，提高資源利用率和系統(tǒng)吞吐量。進(jìn)程的定義進(jìn)程的組成：進(jìn)程包括程序代碼（程序段或文本段）、堆棧段（臨時數(shù)據(jù)，如函數(shù)參數(shù)、返回地址和局部變量）、數(shù)據(jù)段（包括全局變量）、堆（進(jìn)行運(yùn)行期間動態(tài)分配的內(nèi)存）PCB：Process Control Block進(jìn)程表空間：PT進(jìn)程圖： 內(nèi)存中的進(jìn)程如右圖示：棧堆數(shù)據(jù)文本(1)特征： 動態(tài)性：最基本。 并發(fā)性： 獨(dú)立性：獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立接受調(diào)度。 異步性：進(jìn)程以各自獨(dú)立的，不可預(yù)先的速度向前推進(jìn)。 可能會造成不正確的

7、情況出現(xiàn)，原因與進(jìn)程占用處理器的時間、執(zhí)行的速度以及外界的影響有關(guān)，都與時間有關(guān)。稱為與時間有關(guān)的錯誤。又稱競爭條件， Race Condition結(jié)構(gòu)特征：程序段、相關(guān)的數(shù)據(jù)段和PCB構(gòu)成的進(jìn)程實(shí)體。定義：一個程序段在一個數(shù)據(jù)段上的一次執(zhí)行過程。作業(yè)2：簡述進(jìn)程和程序的區(qū)別和聯(lián)系 進(jìn)程和程序是既有聯(lián)系又有區(qū)別的兩個概念（1）程序是指令的集合，靜態(tài)概念，進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過程，動態(tài)概念。（2）程序是長期存在的，進(jìn)程有生命周期，有創(chuàng)建、活動、消亡。（3）程序僅是指令的有序集合，而進(jìn)程則由程序、數(shù)據(jù)和進(jìn)程控制塊組成。（4）進(jìn)程與程序之間不是一一對應(yīng)的，即同一程序同時運(yùn)行于若干不同的數(shù)據(jù)

8、集合上，它將屬于若干個不同的進(jìn)程，而一個進(jìn)程可以執(zhí)行多個程序。 系統(tǒng)內(nèi)的進(jìn)程能并發(fā)執(zhí)行，允許并發(fā)執(zhí)行的理由：信息共享，加快計(jì)算，模塊化和方便性。(2)進(jìn)程的三種基本狀態(tài)： 就緒狀態(tài)：三種情況的進(jìn)程構(gòu)成了就緒隊(duì)列 執(zhí)行狀態(tài)：當(dāng)前進(jìn)程，至少一個 阻塞狀態(tài)：等待狀態(tài)、封鎖狀態(tài)、睡眠狀態(tài)、休眠狀態(tài)。作業(yè)3：畫出三種基本狀態(tài)之間的轉(zhuǎn)換方向并標(biāo)明每一種轉(zhuǎn)換的原因：這個時候，需要進(jìn)行重新調(diào)度，會發(fā)生進(jìn)程上下文內(nèi)容的切換。兩個基本隊(duì)列：就緒隊(duì)列和等待隊(duì)列。隊(duì)列管理模塊：入隊(duì)和出隊(duì)。中斷處理過程（1）喚醒被阻塞的驅(qū)動程序進(jìn)程。（2）保護(hù)被中斷進(jìn)程的CPU環(huán)境。程序是指令在N位置時被中斷的，程序計(jì)數(shù)器中的內(nèi)容為N

9、+1，所有寄存器的內(nèi)容都被保留在中斷保留區(qū)（棧）中。（3）分析中斷原因、轉(zhuǎn)入相應(yīng)的設(shè)備中斷處理程序。（4）進(jìn)行中斷處理。不同的設(shè)備有不同的中斷處理程序。（5）恢復(fù)被中斷進(jìn)程的現(xiàn)場。處理機(jī)再執(zhí)行本程序時，從N+1開始?；謴?fù)的內(nèi)容：包括第N+1條指令的地址（IR寄存器或PC計(jì)數(shù)器）、處理機(jī)狀態(tài)字PSW(標(biāo)志寄存器)、通用寄存器和段寄存器的內(nèi)容注：此處與第四章中的缺頁中斷和缺段中斷相區(qū)別(3)掛起狀態(tài)：終端用戶的請求，父進(jìn)程請求，負(fù)荷調(diào)節(jié)的需要，操作系統(tǒng)的需要。進(jìn)程狀態(tài)的轉(zhuǎn)換：(4)創(chuàng)建狀態(tài)和終止?fàn)顟B(tài)： 例1：簡述三種基本狀態(tài)之間的轉(zhuǎn)換方向及原因：絕對不會出現(xiàn)的是從阻塞到執(zhí)行狀態(tài)的轉(zhuǎn)換。進(jìn)程隊(duì)列：就

10、緒隊(duì)列和等待隊(duì)列。入隊(duì)和出隊(duì)。例2：處于就緒隊(duì)列中的進(jìn)程是由哪三種類型的進(jìn)程組成的解：（1）新進(jìn)程（2）因時間片用完而中斷運(yùn)行的進(jìn)程（3）因等待的條件發(fā)生而被喚醒的進(jìn)程例3：在一個只有單處理機(jī)的操作系統(tǒng)中，進(jìn)程有運(yùn)行、就緒、等待三個基本狀態(tài)。假如某時刻操作系統(tǒng)中有10個進(jìn)程并發(fā)執(zhí)行，且CPU以非核心態(tài)情況下，試問：（1）這時刻系統(tǒng)中處于運(yùn)行狀態(tài)的進(jìn)程數(shù)最多有幾個？最少有幾個？（2）這時刻系統(tǒng)中處于就緒狀態(tài)的進(jìn)程數(shù)最多有幾個？最少有幾個？（3）這時刻系統(tǒng)中處于等待狀態(tài)的進(jìn)程數(shù)最多有幾個？最少有幾個？解：（1）因?yàn)橄到y(tǒng)中只有一個處理機(jī)，所以某時刻處于運(yùn)行狀態(tài)的進(jìn)程數(shù)最多有1個。而最少可能為0，此時

11、其他10個進(jìn)程一定全部排在各等待隊(duì)列中，在就緒隊(duì)列中沒有進(jìn)程，在實(shí)際的操作系統(tǒng)中，此時CPU是在運(yùn)行操作系統(tǒng)的空閑進(jìn)程（System Idle Process）或線程。（2）處于就緒狀態(tài)的進(jìn)程數(shù)最多只有9個，不可能出現(xiàn)10個，因?yàn)橐坏〤PU有空，調(diào)度程序馬上調(diào)度；處于就緒狀態(tài)的進(jìn)程數(shù)最少是0個，1個進(jìn)程運(yùn)行，9個進(jìn)程等待，或者10個進(jìn)程全部等待。（3）處于等待狀態(tài)的進(jìn)程數(shù)最多有10個，等待狀態(tài)的進(jìn)程最少是個。例3：某系統(tǒng)在t0時刻，打印機(jī)剛剛打印完畢或者剛剛開始打印，試問該時刻系統(tǒng)內(nèi)部發(fā)生了進(jìn)程狀態(tài)變化的情況如何？2.1.5 進(jìn)程控制塊：任務(wù)控制塊1、PCB的作用：將程序變成可并發(fā)執(zhí)行的進(jìn)程，

12、是進(jìn)程存在的惟一標(biāo)志。操作系統(tǒng)是根據(jù)PCB來對并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。常駐內(nèi)存。系統(tǒng)會集中存儲所有進(jìn)程的PCB，構(gòu)成進(jìn)程表空間PT。 2、PCB中的信息 (1)進(jìn)程標(biāo)識符：內(nèi)部和外部標(biāo)識 (2)處理機(jī)狀態(tài)：通用寄存器、PC、PSW（標(biāo)志寄存器）和用戶棧指針。 (3)進(jìn)程調(diào)度信息：進(jìn)程狀態(tài)、進(jìn)程優(yōu)先級、調(diào)度的其他信息、阻塞事件。 (4)進(jìn)程控制信息：程序和數(shù)據(jù)的地址、同步和通信機(jī)制、資源清單和鏈接指針。3、PCB的組織方式：鏈接和索引。作業(yè)4：試從進(jìn)程管理、中斷處理、文件管理、存儲管理、設(shè)備管理的角度設(shè)計(jì)進(jìn)程控制塊應(yīng)包含的項(xiàng)目。（北京大學(xué)1999年研究生試題）解：1、從進(jìn)程管理的角度考慮

13、，PCB應(yīng)包含進(jìn)程標(biāo)識符、進(jìn)程狀態(tài)、CPU狀態(tài)信息（包括程序計(jì)數(shù)器、程序狀態(tài)字、棧指針、通用寄存器等）、進(jìn)程調(diào)度信息（進(jìn)程的優(yōu)先數(shù)）、鏈接指針（用于將PCB鏈入各種隊(duì)列）等項(xiàng)信息。2、從進(jìn)程通信的角度考慮，PCB中應(yīng)包含消息隊(duì)列指針、實(shí)現(xiàn)消息隊(duì)列互斥訪問的互斥信號量、描述消息隊(duì)列中消息個數(shù)的資源信號量。3、從中斷處理的角度考慮，PCB中應(yīng)包含CPU狀態(tài)信息。4、從文件管理的角度考慮，PCB中應(yīng)包含用戶文件描述符表，用來登記用戶打開的各個文件，并可以通過它找到在內(nèi)存的相應(yīng)文件的FCB5、從存儲管理的角度考慮，應(yīng)保存進(jìn)程的程序、數(shù)據(jù)、堆棧在內(nèi)存和外存的地址和各部分長度等信息。6、從設(shè)備管理角度考慮

14、，應(yīng)有該進(jìn)程所需資源和已分配到的資源清單。進(jìn)程上下文（Context）實(shí)際上是進(jìn)程執(zhí)行活動全過程的靜態(tài)描述。又稱進(jìn)程映像。包括三個組成部分：（1）用戶級上下文。由用戶程序代碼、用戶數(shù)據(jù)段（含共享數(shù)據(jù)塊）和用戶堆棧組成的進(jìn)程地址空間。（2）系統(tǒng)級上下文。包括進(jìn)程的標(biāo)識信息、現(xiàn)場信息、控制信息、進(jìn)程環(huán)境塊，以及系統(tǒng)堆棧等組成的進(jìn)程地址空間。（3）寄存器上下文。由程序狀態(tài)字寄存器和各類控制寄存器、地址寄存器、通用寄存器組成。Context Switch發(fā)生在寄存器和內(nèi)存之間，依賴于內(nèi)存速度，復(fù)制的寄存器的數(shù)量，是否有特殊指令等。 可再入程序是指一個能被多個用戶同時調(diào)用的程序：必須是純代碼，要求調(diào)用者

15、提供工作區(qū)。2.2 進(jìn)程控制作業(yè)5：原語操作的定義：是指由若干條指令組成、用來實(shí)現(xiàn)某個特定操作的一個過程，其執(zhí)行具有原子性，即原語在執(zhí)行過程中不允許被中斷，常駐內(nèi)存，在核心態(tài)下運(yùn)行。2.2.1 進(jìn)程的創(chuàng)建：fork()、CreateProcess()(1)進(jìn)程圖：描述一個進(jìn)程的家族關(guān)系的有向圖。(2)引起創(chuàng)建進(jìn)程的事件：用戶登錄，作業(yè)調(diào)度，提供服務(wù)和應(yīng)用請求。(3)進(jìn)程的創(chuàng)建：申請空白PCB，為新進(jìn)程分配資源，初始化PCB，將新進(jìn)程插入就緒隊(duì)列。(4)進(jìn)程的創(chuàng)建請求系統(tǒng)為一個程序分配一個工作區(qū)和建立一個進(jìn)程控制塊。2013.3.22 計(jì)算機(jī)當(dāng)進(jìn)程創(chuàng)建新進(jìn)程時，有兩種執(zhí)行可能：（1）父進(jìn)程與子進(jìn)

16、程并發(fā)執(zhí)行（2）父進(jìn)程等待，直到某個或全部子進(jìn)程執(zhí)行完。新進(jìn)程的地址空間也有兩種可能（1）子進(jìn)程是父進(jìn)程的復(fù)制品（具有與父進(jìn)程相同的程序和數(shù)據(jù)）（2）子進(jìn)程裝入另一個新程序2.2.2 進(jìn)程的終止(1)引起進(jìn)程終止的事件：正常結(jié)束，異常結(jié)束和外界干預(yù)。(2)進(jìn)程的終止過程：檢索PCB，判斷狀態(tài)，撤銷子進(jìn)程，歸還資源，清空PCB。(3)進(jìn)程的撤消，系統(tǒng)收回該進(jìn)程所用的工作區(qū)，取消進(jìn)程控制塊。Exit()、TerminatePorcess()父進(jìn)程終止其子進(jìn)程的原因（1）子進(jìn)程使用了超過它所分配到的一些資源（2）分配給子進(jìn)程的任務(wù)已不再需要（3）父進(jìn)程退出，如果父進(jìn)程終止，操作系統(tǒng)不允許子進(jìn)程繼續(xù)。

17、級聯(lián)終止Cascading termination。VMS。2.2.3 進(jìn)程的阻塞與喚醒sleep()和wakeup()(1)引起進(jìn)程阻塞和喚醒的事件：請求系統(tǒng)服務(wù)，啟動某種操作，新數(shù)據(jù)尚未到達(dá)和無新工作可做。(2)進(jìn)程阻塞過程：是正在執(zhí)行的進(jìn)程的一種主動行為。(3)進(jìn)程喚醒過程：2.2.4 進(jìn)程的掛起與激活:交換進(jìn)程(0號進(jìn)程，sched)(1)進(jìn)程的掛起；從內(nèi)存置換到外存。(2)進(jìn)程的激活過程：重新調(diào)入內(nèi)存。2.3 進(jìn)程同步與互斥2.3.1 進(jìn)程同步的基本概念并發(fā)進(jìn)程間的關(guān)系可以是無關(guān)的，也可以是有交往的。獨(dú)立進(jìn)程或協(xié)作進(jìn)程。 1、兩種制約關(guān)系： 間接制約關(guān)系：互斥進(jìn)程互斥是指當(dāng)有若干個進(jìn)

18、程使用某一共享資源時，任何時刻最多只允許一個進(jìn)程使用，而其他要使用該資源的進(jìn)程必須等待，直到占用資源者釋放該資源。是進(jìn)程間競爭共享資源的使用權(quán)，沒有固定的必然關(guān)系。利用公用信號量直接制約關(guān)系：同步進(jìn)程同步是指并發(fā)進(jìn)程之間存在一種制約關(guān)系，一個進(jìn)程的執(zhí)行依賴另一個進(jìn)程的消息，當(dāng)一個進(jìn)程沒有得到另一個進(jìn)程的消息時應(yīng)等待，直到消息到達(dá)才被喚醒。涉及共享資源的并發(fā)進(jìn)程之間有一種必然的依賴關(guān)系。利用私用信號量。作業(yè)6：進(jìn)程間同步和互斥的含義各是什么？不允許兩個以上共享臨界資源的并發(fā)進(jìn)程同時進(jìn)入臨界區(qū)的現(xiàn)象稱為互斥。進(jìn)程同步是指在異步環(huán)境下的一組并發(fā)進(jìn)程因直接制約而相互發(fā)送消息導(dǎo)致的各個進(jìn)程相互使用、相互

19、等待，使得各個進(jìn)程按一定的速度執(zhí)行的現(xiàn)象稱為進(jìn)程間的同步 同步與互斥的混合問題：進(jìn)程的互斥是進(jìn)程間競爭共享資源的使用權(quán)，這種競爭沒有固定的必然關(guān)系；進(jìn)程同步，涉及共享資源的并發(fā)進(jìn)程之間有一種必然的依賴關(guān)系。 race condition競爭條件：多個內(nèi)核進(jìn)程同時活動，會發(fā)生競爭條件。如打開文件的內(nèi)核數(shù)據(jù)結(jié)構(gòu)，內(nèi)存分配的數(shù)據(jù)結(jié)構(gòu)，維護(hù)進(jìn)程列表及處理中斷處理程序的數(shù)據(jù)結(jié)構(gòu)。 非搶占內(nèi)核式的系統(tǒng)中不會導(dǎo)致競爭條件，搶占內(nèi)核的系統(tǒng)可能會導(dǎo)致競爭條件。搶占內(nèi)核比非搶占內(nèi)核更受歡迎。Windows XP和Windows 2000為非搶占式內(nèi)核，傳統(tǒng)的Unix和Linux 2.6以前的內(nèi)核也是非搶占式的。L

20、inux 2.6以后，商用Unix、Solaris是搶占內(nèi)核2、臨界資源：一次只允許一個進(jìn)程使用的資源。打印機(jī)、磁帶機(jī)、消息緩沖隊(duì)列、變量、數(shù)組、緩沖區(qū)等。又稱獨(dú)享資源。 3、臨界區(qū)：實(shí)現(xiàn)互斥的方法：軟件和硬件方法1965年Dijkstra(狄克斯特拉)提出的臨界段設(shè)計(jì)原則4、同步機(jī)制的規(guī)則：空閑讓進(jìn)，忙則等待，有限等待和讓權(quán)等待。（在單處理機(jī)系統(tǒng)中是必須的，在多處理機(jī)系統(tǒng)中不是必須的） 實(shí)現(xiàn)同步的幾種方法1、禁止中斷：只適合單處理器環(huán)境，會出現(xiàn)餓死。2、TestAndSet Lock指令：不可分的原子操作,可適用于多處理器環(huán)境。Boolean TestAndSet(boolean locke

21、d) if(locked) return true; else locked=true; return false; TSL算法Enter_region: TSL REGISTER,LOCK復(fù)制樂到寄存器并將鎖設(shè)為1 CMP REGISTER,#0 JNE enter_region若不是0,說明鎖已被設(shè)置，所以循環(huán) RET 返回調(diào)用者，進(jìn)入了臨界區(qū)Leave_region: MOVE LOCK,#0 在鎖中存入0 RET 返回調(diào)用者3、Swap指令 boolean void Swap(boolean a,boolean b) boolean temp; temp=b; b=a; a=temp;

22、 Swap算法Do key=TRUE; swap(&lock,&key); critical section; lock=FALSE; remainder section; while(TRUE);4、Dekker算法和Peterson算法：基于軟件的兩個進(jìn)程間的通信。 Bakery算法，用于N個進(jìn)程間的通信Peterson解法#define FALSE 0#define TRUE 1#define N 2 ;進(jìn)程數(shù)量Int turn;現(xiàn)在輪到誰Int interestedN;所有值初始化為0,即FALSE；Void enter_region(int process);進(jìn)程是0或1 int o

23、ther;其他進(jìn)程號 other=1-process;另一方進(jìn)程 interestedprocess=TRUE;表明所感興趣的 turn=process;設(shè)置標(biāo)志 while(turn=process&interestedother=TRUE)； Void leave_region(int process)進(jìn)程：誰離開？ interestedprocess=FALSE;表示離開臨界區(qū)Peterson算法中Pi的結(jié)構(gòu)Do flagi=TRUE; turn=j; while(flagj&turn=j); 臨界區(qū)； flagi=FALSE; 剩余區(qū)； while(TRUE);2.3.2 信號量機(jī)制

24、1、整型信號量：P、V操作 wait(s):while s=0 do nothing; s=s-1;信號量的值不可能取負(fù)值。 signal(s):s=s+1;又稱簡單信號量，二元信號量，二進(jìn)制信號量，互斥鎖。缺點(diǎn)：忙等待方式busy waiting,自旋鎖（優(yōu)點(diǎn)：不進(jìn)行上下文切換，常用于多處理系統(tǒng)）2013.3.24網(wǎng)絡(luò)2、記錄型信號量： struct semaphore int:value; struct process *L; s; wait(s): s.value=s.value-1; if s.value0 then block(s.L);信號量的遞減和測試次序的互換，其值可取負(fù)值。

25、signal(s):s.value=s.value+1; if s.value=0 then wakeup(s.L);又稱計(jì)數(shù)信號量，資源信號量，用來控制m個進(jìn)程訪問某一類n個臨界資源。作業(yè)7:記錄型信號量的物理含義：例：設(shè)有n個進(jìn)程共享一個程序段，對于如下兩種情況：（1）如果每次只允許一個進(jìn)程進(jìn)入該程序段。（2）如果每次最多允許m個進(jìn)程（m0)個單元的緩沖區(qū)。P1每次用produce()生成一個正整數(shù)并用put()送入緩沖區(qū)某一空單元中；P2每次用getodd()從該緩沖區(qū)中取出一個奇數(shù)并用countodd()統(tǒng)計(jì)奇數(shù)個數(shù)；P3每次用geteven()從該緩沖區(qū)中取出一個偶數(shù)并countev

26、en()統(tǒng)計(jì)偶數(shù)個數(shù)。請用信號量機(jī)制實(shí)現(xiàn)這三個進(jìn)程的同步與互斥活動，并說明所定義信號量的含義。要求用偽代碼描述。 答案：定義信號量S1控制P1與P2之間的同步；S2控制P1與P3之間的同步；empty控制生產(chǎn)者與消費(fèi)者之間的同步；mutex控制進(jìn)程間互斥使用緩沖區(qū)。程序如下： Var s1=0,s2=0,empty=N,mutex=1; Parbegin P1:begin X=produce(); /*生成一個數(shù)*/ P(empty);/*判斷緩沖區(qū)是否有空單元*/ P(mutex); /*緩沖區(qū)是否被占用*/ put(x); If x%2=0 V(s2); /*如果是偶數(shù)，向P3發(fā)出信號*/

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

28、)+1; V(mutex); /* 釋放緩沖區(qū)*/ V(empty); /*向P1發(fā)信號，多出一個空單元*/End.Parend.2.4.2 讀者和寫者問題：一直用來測試幾乎所有新的同步原語。多個用戶共享數(shù)據(jù)庫系統(tǒng)的建模問題。有多種不同的策略，都與優(yōu)先級有關(guān)。 1、讀者優(yōu)先：第一讀者-寫者問題，寫者可能饑餓。 2、排隊(duì)策略或先來先服務(wù) 3、寫者優(yōu)先：第二讀者-寫者問題，讀者可能饑餓。 4、某個進(jìn)程即是寫者又是讀者的問題例：設(shè)有P1,P2,P3三個進(jìn)程共享某一資源F，P1對F只讀不寫，P2對F只寫不讀，P3對F先讀后寫。當(dāng)一個進(jìn)程寫F時，其他進(jìn)程對F不能進(jìn)行讀寫，但多個進(jìn)程同時讀F是允許的。試用

29、P、V操作正確實(shí)現(xiàn)P1,P2,P3的同步互斥。要求：（1）正常運(yùn)行時不產(chǎn)生死鎖（2）使用F的并發(fā)度要高。（北京大學(xué)1996年研究生試題） 解：本題實(shí)際上是一個讀者和寫者問題，P1是一個讀者，P2是一個寫者，為了使F的并發(fā)度較高，將P3先看成讀者，當(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(re

30、adcount=0)V(mutex); V(rmutex);P2() While(1) P(mutex); 寫F； V（mutex）;P3() While(1) P(rmutex); 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)餐問題：是一個并發(fā)控制問題，在多個進(jìn)程之間分配多個資源且不會出現(xiàn)死鎖和饑餓的問題。方法： 1、同時允許四個哲學(xué)家提出進(jìn)餐要求

31、2、同時去拿起兩邊的筷子 3、使用非對稱解決方法，奇數(shù)號哲學(xué)家先拿左邊的筷子，偶數(shù)號哲學(xué)家先拿右邊的筷子注意：沒有死鎖的解決方案并不能消除餓死的可能性。2.4.4 理發(fā)師嗜睡問題 一個理發(fā)店由一個有N張椅子的等候室和一個放有一張理發(fā)椅的理發(fā)室組成。若沒有要理發(fā)的顧客，則理發(fā)師就去睡覺，若一個顧客走進(jìn)理發(fā)店且所有的椅子都被占用了，則該顧客就離開理發(fā)店，若理發(fā)師正在為人理發(fā)，則該顧客就找一張空椅子坐下等待，若理發(fā)師在睡覺，則顧客就喚醒他。 試用信號量設(shè)計(jì)一個協(xié)調(diào)理發(fā)師和顧客的程序。（西安電子科技大學(xué)2000年研究生試題） 解：本題中，顧客進(jìn)程和理發(fā)師進(jìn)程之間存在著多種同步關(guān)系：（1）只有在理發(fā)椅空

32、閑時，顧客才能坐到理發(fā)椅上等待理發(fā)師理發(fā)，否則顧客便必須等待；只有當(dāng)理發(fā)椅上有顧客時，理發(fā)師才可以開始理發(fā)，否則他也必須等待。這種同步關(guān)系類似于單緩沖（理發(fā)椅）的生產(chǎn)者和消費(fèi)者問題中的同步關(guān)系，故可以通過信號量empty(初值為1)和full(初值為0)來控制。（2）理發(fā)師為顧客理發(fā)時，顧客必須等待理發(fā)的完成，并在理發(fā)完成后由理發(fā)師喚醒他，這可單獨(dú)使用一個信號量cut來控制，初值為0。 （3）顧客理完發(fā)后必須向理發(fā)師付費(fèi)，并等理發(fā)師收費(fèi)后顧客才能離開；而理發(fā)師則需等待顧客付費(fèi)，并在收費(fèi)后喚醒顧客以允許他離開，這可分別通過兩個信號量payment和receipt來控制，初值都為0。（4）等候室中

33、的N張沙發(fā)是顧客進(jìn)程競爭的資源，故還需為它們設(shè)置了一個資源信號量sofa，初值為n（5）為了控制顧客的人數(shù)，使顧客能在所有的沙發(fā)都被占用時離開理發(fā)店，還必須設(shè)置一個整型變量count來對理發(fā)店中的顧客進(jìn)行計(jì)數(shù)，該變量將被多個顧客進(jìn)程互斥地訪問并修改，這可通過一個互斥信號量mutex來實(shí)現(xiàn)，初值為1Guestbegin wait(mutex); if(countN)then begin signal(muetx); 離開理發(fā)店; end else begin count=count+1; if(count1) then begin wait(sofa); 在沙發(fā)中就座; wait(empty);

34、 從沙發(fā)上起來; signal(sofa); end else /*count=1*/ wait(empty); 在理發(fā)椅上就座; signal(full); wait(cut); 理發(fā)； 付費(fèi)； signal(payment); wait(receipt); 從理發(fā)椅上起來; signal(empty); wait(mutex); count=count-1; signal(mutex); 離開理發(fā)店; end endbarber:begin repeat wait(full); 替顧客理發(fā); signal(cut); wait(payment); 收費(fèi); signal(receipt);

35、until false; endparendend 2.4.5 “吸煙者”問題。假設(shè)一個系統(tǒng)有3個吸煙者（smoker）進(jìn)程和一個供貨商（Agent）進(jìn)程。每個吸煙者連續(xù)不斷地制造香煙并吸掉它。 但是，制造一支香煙需要3種材料煙、紙、火柴。一個吸煙者進(jìn)程有紙，另一個有煙，第三個有火柴。供貨商進(jìn)程可以無限地提供這3種材料。供貨商將這這兩種材料一起放在桌上，持有另一種材料的吸煙者即可制造一支香煙并吸掉它。當(dāng)此吸煙者抽香煙時，它發(fā)出一個信號通知供貨商進(jìn)程，供貨商馬上給出另外兩種材料，如此循環(huán)往復(fù)。試編寫一個程序使供貨商和吸煙者同步執(zhí)行。解法：semaphore smoker30; 三個吸煙者sema

36、phore material30; 三種原料semaphore agent1; 供應(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); coend;變型1抽煙問題：有一個煙草代理和三個抽煙者。抽煙者若要抽

37、煙，必須具有煙葉、煙紙和火柴。三個抽煙者中，一人缺煙葉、一人缺煙紙、一人缺火柴。煙草代理會源源不斷地分別供應(yīng)煙葉、煙紙和火柴，并將它們放在桌上。如果放的是煙葉，則缺煙葉的抽煙者拾起煙葉，制作香煙，然后抽煙；其他類推。試用信號量同步煙草代理和三個抽煙者。解法：semaphore smoker30; 三個吸煙者semaphore material30; 三種原料semaphore agent1; 供應(yīng)商int turn=0;輪到誰Agent While(1) P(agent); 放原料； V(smokerturn); V(material(turn+1)%3); 制作香煙； 吸煙； turn=(t

38、urn+1)%3Smoker_i While(1) P(smokeri); P(material(i+1)%3); 制作香煙； 吸煙； V(agent); 變型2有一間酒吧里有3個音樂愛好者隊(duì)列，第1隊(duì)的音樂愛好者只有隨身聽，第2隊(duì)只有音樂磁帶，第3隊(duì)只有電池。而要聽音樂就必須隨身聽、音樂磁帶和電池這3種物品俱全。酒吧老板一次出售這3種物品中的任意兩種。當(dāng)一名音樂愛好者得到這3種物品并聽完一首樂曲后，酒吧老板才能再一次出售這3種物品中的任意兩種，于是第2名音樂愛好者得到這3種物品，并開始聽樂曲。全部買賣就這樣進(jìn)行下去。試用P、V操作正確解決這一買賣。（北京大學(xué)1999年研究生試題）變型3（桔子

39、汁生產(chǎn)線問題）現(xiàn)有三個生產(chǎn)者P1 、P2 、P3 ，他們都要生產(chǎn)水，每個生產(chǎn)者都已分別購得兩種不同原料，待購得第三種原料后就可配制成桔子水，裝瓶出售。有一供應(yīng)商能源源不斷地供應(yīng)糖、水、桔子精，但每次只拿出一種原料放入容器中供給生產(chǎn)者。當(dāng)容器中有原料時需要該原料的生產(chǎn)者可取走，當(dāng)容器空時供應(yīng)商又可放入一種原料。假定：生產(chǎn)者P1已購得糖和水；生產(chǎn)者P2 已購得水和桔子精；生產(chǎn)者P3 已購得糖和桔子精；試用：信號量與P 、V 操作，寫出供應(yīng)商和三個生產(chǎn)者之間能正確同步的程序 2.4.6 銀行排隊(duì)問題(北京大學(xué)2000）銀行有n個柜員,每個顧客進(jìn)入銀行后先取一個號,并且等著叫號,當(dāng)一個柜員空閑后，就叫

40、下一個號。解：將顧客號碼排成一個隊(duì)列,顧客進(jìn)入銀行領(lǐng)取號碼后,將號碼由隊(duì)尾插入;柜員空閑時,從隊(duì)首取得顧客號碼,并且為這個顧客服務(wù),由于隊(duì)列為若干進(jìn)程共享, 所以需要互斥.柜員空閑時,若有顧客,就叫下一個顧客為之服務(wù).因此,需要設(shè)置一個信號量來記錄等待服務(wù)的顧客數(shù).Cobegin var mutex=1,customer_count=0:semaphore; cobegin process customer begin repeat 取號碼； p(mutex); 進(jìn)入隊(duì)列； v(mutex); v(customer_count); until false; endprocess servers

41、_i(i=1,.,n)begin repeat p(customer_count); p(mutex); 從隊(duì)列中取下一個號碼； v(mutex); 為該號碼持有者服務(wù)； until falseendCoend變型-面包師問題面包店有很多面包，由n個銷售人員推銷。每個顧客進(jìn)店后先取一個號，并且等待叫號。當(dāng)一個銷售人員空閑下來時，就叫下一個號。試設(shè)計(jì)一個使銷售人員和顧客同步的算法。2.4.7 交通問題有橋如圖示：（北京大學(xué)1992年研究生試題）橋北南車流如箭頭所示。橋上不允許兩車交會，但允許同方向車輛依次通行（即橋上可以有多個同方向的車）。用P、V操作實(shí)現(xiàn)交通管理以防止橋上堵塞。解：設(shè)置coun

42、tA和countB表示由南往北、由北 往南已在橋上行駛的汽車數(shù)目，初值為0,設(shè)置SA表示對countA的互斥，初值為1 ，設(shè)置SB表示對countB的互斥，初值為1,設(shè)置mutex表示對橋的互斥，初值為1P1：由南往北行駛到橋頭； P（SA）;If(countA=0)P(mutex);countA+;V(SA);過橋；P(SA); countA-; if(countA=0)V(mutex);V(SA);P2：由北往南行駛到橋頭； P（SB）;If(countB=0)P(mutex);countB+;V(SB);過橋；P(SB); countB-; if(countB=0)V(mutex);V(

43、SB);管程機(jī)制（略）1、管程的定義：是由一組局部的變量對局部變量進(jìn)行操作的一組過程以及對局部變量進(jìn)行初始化的語句序列構(gòu)成的一個軟件模塊?？捎脕韺?shí)現(xiàn)進(jìn)程同步。Type monitor_name=monitor variable declarations; procedure entry P1(); begin end; procedure entry Pn(); begin end;Begin initialization code;end管程的特點(diǎn)1、管程內(nèi)的局部變量只能被局限于管程內(nèi)的過程所訪問；反之亦然，即局部于管程內(nèi)的過程只能訪問管程內(nèi)的變量。2、任何進(jìn)程只能通過調(diào)用管程提供的過程入口

44、進(jìn)入管程3、任一時刻，最多只能有一個進(jìn)程在管程中執(zhí)行。 保證進(jìn)程互斥進(jìn)入管程是由編譯器負(fù)責(zé)，即管程是一種編程語言的構(gòu)件，它的實(shí)現(xiàn)需要編譯器的支持。管程解決生產(chǎn)者消費(fèi)者問題先建立一個管程。Type P_C=monitor var in,out,count:integer; buffer:array0.n-1 of item; notfull,notempty:condition; procedure entry put(var product:item) begin if count=n then notfull.wait bufferin:=product; in:=(in+1) mod n;

45、 count:=count+1; notempty.signal end procedure entry get(var product:item) begin if count0，該進(jìn)程繼續(xù)執(zhí)行；若S0，則阻塞該進(jìn)程，并把它插入該信號量對應(yīng)的阻塞隊(duì)列中，重新進(jìn)程調(diào)度。10、敘述進(jìn)程和程序的主要區(qū)別。解：進(jìn)程和程序是既有聯(lián)系又有區(qū)別的兩個概念，它們的主要區(qū)別如下：（1）程序是指令的有序集合，其本身沒有任何運(yùn)行的含義，它是一個靜態(tài)的概念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過程，它是一個動態(tài)概念。（2）程序的存在是永久的。而進(jìn)程是有生命期的，它因創(chuàng)建而產(chǎn)生，因調(diào)度而執(zhí)行，因得不到資源而暫停，因撤消而

46、消亡。（3）程序僅是指令的有序集合。而進(jìn)程則由程序、數(shù)據(jù)和進(jìn)程控制塊組成。（4）進(jìn)程與程序之間不是一一對應(yīng)的，即同一程序同時運(yùn)行若干個不同的數(shù)據(jù)集合上，它將屬于若干個不同的進(jìn)程；而一個進(jìn)程可以執(zhí)行多個程序。1、桌上有一空盤，允許存放一只水果。爸爸可向盤中放蘋果，也可向盤中放桔子，兒子專等吃盤中的桔子，女兒專等吃盤中的蘋果。 規(guī)定:當(dāng)盤空時一次只能放一只水果供吃者取用，請用P、V原語實(shí)現(xiàn)爸爸、兒子、女兒三個并發(fā)進(jìn)程的同步。分析：本題中，爸爸、兒子、女兒共用一個盤子，且盤中一次只能放一個水果。當(dāng)盤子為空時，爸爸可將一個水果放入果盤中。若放入果盤中的是桔子，則允許兒子吃，女兒必須等待，若放入果盤中的

47、是蘋果，則允許女兒吃，兒子必須等待。本題實(shí)際是生產(chǎn)者消費(fèi)者問題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)產(chǎn)品有兩類，消費(fèi)者也有兩類，每類消費(fèi)者只消費(fèi)其中固定的一類產(chǎn)品。解：本題中，應(yīng)設(shè)置三個信號量s,so,sa，信號量s表示盤子是否為空，其初值為1，信號量so表示盤中是否有桔子，其初值為0，信號量sa表示盤中是否有蘋果，其初值為0。同步描述如下： var s,sa,so:integer=1,0,0; father:begin p(s); 將水果放入盤中； if(放入的是桔子)v(so); else v(sa); end; son:begin p(so); 從盤中取出桔子； v(s); 吃桔子； end

48、 daughter:begin p(sa); 從盤中取出蘋果； v(s); 吃蘋果； end2、(北京大學(xué)94年試題) 進(jìn)程A1，A2，An1通過m個緩沖區(qū)向進(jìn)程B1，B2，Bn2不斷地發(fā)送消息。發(fā)送和接收工作遵循如下規(guī)則：(1)每個發(fā)送進(jìn)程一次發(fā)送一個消息，寫入一個緩沖區(qū)，緩沖區(qū)大小等于消息長度；(2)對每一個消息，B1，B2，Bn2都必須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)。(3)m個緩沖區(qū)都滿時，發(fā)送進(jìn)程等待，沒有可讀的消息時，接收進(jìn)程等待。試用P、V操作組織正確的發(fā)送和接收工作。分析：本題是生產(chǎn)者消費(fèi)者問題的一個變形，一組生產(chǎn)者和一組消費(fèi)者共用m個緩沖區(qū)，每個緩沖區(qū)只要寫一次，但需要讀n2次

49、。所以，我們可以把這一組緩沖區(qū)看成n2組緩沖區(qū)，每個發(fā)送者需要同時寫n2組緩沖區(qū)中相應(yīng)的n2個緩沖區(qū)，而每一個接收者只需讀它自己對應(yīng)的那組緩沖區(qū)中的對應(yīng)單元。解：本題中，應(yīng)設(shè)置一個信號量mutex實(shí)現(xiàn)諸進(jìn)程對緩沖區(qū)的互斥訪問；兩個信號量數(shù)組emptyn2和fulln2描述n2組緩沖區(qū)的使用情況。mutex的初值為1；數(shù)組empty中的元素初值為m;數(shù)組full中的元素初值為0。其同步描述如下： var mutex,emptyn2=m,fulln2=0:integer; mutex=1; for(i=0;i=n2-1;i+) emptyi=m; fulli=0; send:begin for(i

50、=0;i=n2-1;i+) p(emptyi); p(mutex); 將消息放入緩沖區(qū)； v(mutex); for(i=0;i=n2-1;i+) v(fulli); end; receive_i:begin p(fulli); p(mutex); 將消息從緩沖區(qū)取出； v(mutex); v(emptyi); end; Ai:begin repeat send(); until false; end Bi:begin repeat receive(i); until false; end3、(北京大學(xué)90年試題)(略) (1)寫出P、V操作的定義 (2)有三個進(jìn)程PA、PB和PC合作解決文件

51、打印問題：PA將文件記錄從磁盤讀入主存的緩沖區(qū)1，每執(zhí)行一次讀一個記錄；PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)2，每執(zhí)行一次，復(fù)制一個記錄；PC將緩沖區(qū)2的內(nèi)容打印出來，每執(zhí)行一次打印一個記錄。緩沖區(qū)的大小等于一個記錄大小。請用P、V操作來保證文件的正確打印。解：(2)本題中：進(jìn)程PA、PB和PC之間的關(guān)系為：PA與PB共用一個單緩沖區(qū)，而PB又與PC共用一個單緩沖區(qū)，其合作方式如圖示： 從磁盤讀入復(fù)制緩沖區(qū)1緩沖區(qū)2PAPCPB打印 當(dāng)緩沖區(qū)1為空時，PA可將一個記錄讀入其中，若緩沖區(qū)1中有數(shù)據(jù)且緩沖區(qū)2為空，PB可將記錄從緩沖區(qū)1復(fù)制到緩沖區(qū)2中；若緩沖區(qū)2中有數(shù)據(jù)，則進(jìn)程PC可打印記錄。其他條

52、件下，相應(yīng)進(jìn)程必須等待。實(shí)際上，這是一個生產(chǎn)者消費(fèi)者問題。(PB既是生產(chǎn)者又是消費(fèi)者) 為遵循這一同步規(guī)則。應(yīng)設(shè)置四個信號量empty1、empty2、full1、full2，信號量empty1和empty2分別表示緩沖區(qū)1及緩沖區(qū)2是否為空，其初值為1；信號量full1和full2分別表示緩沖區(qū)1和緩沖區(qū)2是否有記錄可供處理，其初值為0。其同步描述如下： 初始化； PA:begin repeat 從磁盤讀一個記錄； p(empty1); 將記錄存入緩沖區(qū)1； v(full1); until false; end PB:begin repeat p(full1); 從緩沖區(qū)1取出記錄； v(e

53、mpty1); p(empty2); 將記錄存入緩沖區(qū)2； v(full2); until false; endPC:begin repeat p(full2); 從緩沖區(qū)2中取出記錄； v(empty2); 打印記錄； until false end中國礦大20044、P、V操作實(shí)現(xiàn)進(jìn)程同步與互斥(40分)(1)P、V操作是原語，用類似C(或C+，或Pascal，或Java)寫出信號量和V操作的定義(5分)(2)針對您寫出的V操作，說明為什么V操作要求是原語？(10分)(3)使用P、V操作實(shí)現(xiàn)臨界區(qū)的管理，S是信號量，說明S初始值為1，S值小于0，等于0的物理意義(5分)(4)有三個并發(fā)進(jìn)程

54、：R負(fù)責(zé)從輸入設(shè)備讀入信息單元逐個放到緩沖區(qū)B1，B1由兩個單元構(gòu)成；M負(fù)責(zé)從B1緩沖區(qū)逐個讀出信息單元，對信息加工處理后放入緩沖區(qū)B2，B2由兩個單元構(gòu)成；P負(fù)責(zé)從緩沖區(qū)B2逐個打印輸出信息單元。使用P、V操作實(shí)現(xiàn)它們之間的同步。(20分)(設(shè)置您需要的信號量，指出它們的初始值，畫出利用P、V操作實(shí)現(xiàn)它們的同步的流程)中國礦大20035、 有一個盆子可以放兩個水果(兩個蘋果、或兩個桃子、或一個蘋果和一個桃子)。父親不停地向盆子每次只放一個蘋果，母親不停地向盆子每次只放一個桃子；兒子從盆子只取一個蘋果，消費(fèi)完繼續(xù)取一個蘋果消費(fèi)；女兒從盆子只取一個桃子，消費(fèi)完繼續(xù)取一個桃子消費(fèi)。 用P、V操作實(shí)

55、現(xiàn)上述四個人的同步與互斥。中國礦大20056、 有10個計(jì)算進(jìn)程P1，P2，P10，它們負(fù)責(zé)各自的計(jì)算，計(jì)算完成后必須把一個單元的計(jì)算結(jié)果依次寫入緩沖區(qū)B的一個單元，然后，繼續(xù)循環(huán)地計(jì)算，寫緩沖區(qū)工作。進(jìn)程P0負(fù)責(zé)循環(huán)地從緩沖區(qū)B依次取出數(shù)據(jù)單元打印。緩沖區(qū)B有依次排列的5個單元組成。問：1(10分)用P、V操作實(shí)現(xiàn)它們的同步。2(10分)你設(shè)置的信號量各自可能的最大值、最小值是多少？它們有何物理意義？7、 有兩個優(yōu)先級相同的并發(fā)進(jìn)程m1,m2，各自計(jì)算過程如下所示。它們利用信號量s1,s2同步，信號量s1,s2初始值設(shè)置為0。X,y,z是它們共享的變量。問m1,m2運(yùn)行結(jié)束后，x,y,z在理

56、論上可能的值分別是多少?進(jìn)程m1 進(jìn)程m2 x=1 y=2 V(s1) P(s1) z=x+1 z=y+1 P(s2) V(s2) x=z+x y=y+z蘇州大學(xué)20078、(15分)設(shè)有五個哲學(xué)家，他們花費(fèi)一生中的時光思考和吃飯。這些哲學(xué)家共用一個圓桌，每個哲學(xué)家都有一把椅子。桌子中央是一碗米飯。桌上總共有6根筷子，在每個兩邊分開各放一根，桌子中央還有一根。當(dāng)一個哲學(xué)家思考時，他與其他同事不交互，一個哲學(xué)家一次只能拿起一根筷子，顯然他不能從其他哲學(xué)家手里搶走筷子，吃完后放下所有的筷子。哲學(xué)家只有在饑餓時才試圖從兩邊或者桌子中央取2根筷子進(jìn)餐。試問：(1)用P、V操作描述滿足上述要求的哲學(xué)家進(jìn)

57、程，要求不能產(chǎn)生死鎖。(2)分析上述解決方案的利弊。9、某數(shù)據(jù)庫有一個寫進(jìn)程，多個讀進(jìn)程，它們之間讀、寫操作的交互要求是： 寫進(jìn)程正在寫該數(shù)據(jù)庫時不能有其他進(jìn)程讀該數(shù)據(jù)庫，也不能有其他進(jìn)程寫該數(shù)據(jù)庫；讀進(jìn)程之間不互斥，可以同時讀該數(shù)據(jù)庫。 請用信號量及P、V操作描述這一組進(jìn)程的工作過程。解：本題中，允許讀進(jìn)程同時讀數(shù)據(jù)庫，但寫進(jìn)程正在寫數(shù)據(jù)庫時不允許其他進(jìn)程讀數(shù)據(jù)庫，也不允許其他進(jìn)程寫該數(shù)據(jù)庫。 為了解決讀、寫進(jìn)程之間的同步，應(yīng)設(shè)置兩個信號量和一個共享變量；讀互斥信號量rmutex，用于使讀進(jìn)程互斥地訪問共享變量count，其初值為1，寫互斥信號量wmutex，用于實(shí)現(xiàn)寫進(jìn)程與讀進(jìn)程的互斥及寫

58、進(jìn)程與寫進(jìn)程的互斥，其初值為1；共享變量count，用于記錄當(dāng)前正在讀數(shù)據(jù)庫的讀進(jìn)程數(shù)目，初值為0。其工作過程如下：同教材。10、(中國科學(xué)院軟件研究所95年試題) 多個進(jìn)程共享一個文件，其中只讀文件的稱為讀者，只寫文件的稱為寫者。讀者可以同時讀，但寫者只能獨(dú)立寫。請：(1)說明進(jìn)程間的相互制約關(guān)系，應(yīng)設(shè)置哪些信號量？(2)用P、V操作寫出其同步算法。(3)修改上述的同步算法，使得它對寫者優(yōu)先，即一旦有寫者到達(dá)，后續(xù)的讀者必須等待。而無論是否有讀者在讀文件。解：(1)進(jìn)程間的相互制約關(guān)系有三類： 一是讀者之間允許同時讀； 二是讀者與寫者之間須互斥； 三是寫者之間須互斥。 為解決讀者、寫者之間的

59、同步，應(yīng)設(shè)置兩個信號量和一個共享變量：讀互斥信號量rmutex，用于使讀者互斥地訪問共享變量count，其初值為1，寫互斥信號量wmutex，用于實(shí)現(xiàn)寫者與讀者的互斥及寫者及寫者的互斥，其初值為1，共享變量count，用于記錄當(dāng)前正在讀文件的讀者數(shù)目，初值為0。(2)進(jìn)程間的控制算法如下： reader:begin repeat p(rmutex); if(count=0)p(wmutex); count:=count+1; v(rmutex); 讀文件； p(rmutex); count:=count-1; if(count=0)v(wmutex); v(rmutex); until fal

60、se endWriter:begin repeat p(wmutex); 寫文件； v(wmutex); until false; end(3)為了提高寫者的優(yōu)先級，增加一個信號量s，其初值為1，表示未有寫進(jìn)程正在寫。用于在寫進(jìn)程到達(dá)后封鎖后續(xù)的讀者。 其過程如下：Reader:begin repeat p(s); p(rmutex); if(count=0)p(wmutex); count:=count+1; v(rmutex); v(s); 讀文件； p(rmutex); count:=count-1; if(count=0)v(wmutex); v(rmutex); until fals