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

1、計(jì)算機(jī)操作系統(tǒng)(co zu x tn)第二章 進(jìn)程(jnchng)管理（進(jìn)程(jnchng)同步與互斥）共三百九十五頁(yè)2009年1個(gè)選擇、1個(gè)綜合應(yīng)用題2010年3個(gè)選擇2011年2個(gè)選擇，1個(gè)綜合應(yīng)用題2012年2個(gè)選擇2013年2個(gè)選擇,1個(gè)同步(tngb)算法設(shè)計(jì)題 進(jìn)程管理是本課程的重點(diǎn)章節(jié)，這部分介紹的是操作系統(tǒng)5大管理功能(gngnng)之一：處理機(jī)管理，包括進(jìn)程管理和處理機(jī)調(diào)度兩大塊的內(nèi)容。本章是學(xué)習(xí)和考試的重點(diǎn)內(nèi)容，同時(shí)也是難點(diǎn)。這部分除了要掌握基本的概念和基本的原理外，還要求能運(yùn)用這些基本原理去分析和解決問(wèn)題。共三百九十五頁(yè) 進(jìn)程同步與互斥是進(jìn)程管理的重點(diǎn)，也是操作系統(tǒng)學(xué)科的

2、一個(gè)難點(diǎn)。 具體包括:進(jìn)程同步的基本概念、實(shí)現(xiàn)臨界區(qū)互斥的基本方法(包括軟件實(shí)現(xiàn)方法、硬件實(shí)現(xiàn)方法)、信號(hào)量(P、V操作)、管程、經(jīng)典同步問(wèn)題(包括生產(chǎn)者-消費(fèi)者問(wèn)題、讀者-寫(xiě)者問(wèn)題、哲學(xué)家進(jìn)餐問(wèn)題等)。我們一定要掌握P、V操作的概念、流程(lichng)，以及P、V操作在同步問(wèn)題、互斥問(wèn)題中的應(yīng)用。 共三百九十五頁(yè)首先,要求掌握進(jìn)程的概念，其中進(jìn)程和程序這兩個(gè)概念的區(qū)別和聯(lián)系一定要搞清楚。第二,要記住進(jìn)程的三個(gè)基本狀態(tài)以及它們之間相互轉(zhuǎn)換條件，一定要記住不可能從就緒狀態(tài)直接轉(zhuǎn)換到等待(dngdi)狀態(tài)。第三,需要理解進(jìn)程控制和原語(yǔ)這兩個(gè)概念，掌握進(jìn)程的創(chuàng)建、撤銷(xiāo)、阻塞、喚醒的條件，理解四種原

3、語(yǔ)的執(zhí)行過(guò)程。共三百九十五頁(yè)第四,理解什么是并發(fā)進(jìn)程間的直接制約以及由直接制約所引發(fā)的進(jìn)程同步，重點(diǎn)要掌握如何用P、V原語(yǔ)操作實(shí)現(xiàn)同步問(wèn)題，要會(huì)利用P、V原語(yǔ)操作來(lái)解決經(jīng)典的同步問(wèn)題；第五(d w),了解進(jìn)程的通信方式及它們各自的特點(diǎn)；第六,要理解進(jìn)程和線(xiàn)程的異同以及多線(xiàn)程模型；共三百九十五頁(yè)第二章 進(jìn)程(jnchng)管理2.1 進(jìn)程的基本概念2.2 進(jìn)程控制2.3 進(jìn)程同步2.4 經(jīng)典進(jìn)程的同步問(wèn)題2.5 進(jìn)程通信2.6 線(xiàn)程基礎(chǔ)知識(shí)總結(jié)實(shí)戰(zhàn)(shzhn)練習(xí)綜合應(yīng)用題共三百九十五頁(yè)操作系統(tǒng)在管理進(jìn)程與線(xiàn)程的過(guò)程中需要完成以下工作：（1）用戶(hù)和系統(tǒng)進(jìn)程的創(chuàng)建和刪除；（2）進(jìn)程的調(diào)度；（3）

4、為進(jìn)程的同步、通信、死鎖處理提供機(jī)制。多道程序設(shè)計(jì)的提出 其基本思想是在主存中同時(shí)存放多個(gè)用戶(hù)的作業(yè)，使之同時(shí)處于運(yùn)行狀態(tài)而共享系統(tǒng)資源。宏觀(guān)上是并行運(yùn)行，微觀(guān)上是依次輪流迸發(fā)運(yùn)行的。操作系統(tǒng)的定義：操作系統(tǒng)是指控制和管理計(jì)算機(jī)的軟、硬件資源，合理地組織計(jì)算機(jī)的工作流程，為程序的運(yùn)行提供一個(gè)良好環(huán)境，方便用戶(hù)使用的程序集合。之所以采用多道程序設(shè)計(jì)技術(shù)，是由于中斷和通道(tngdo)技術(shù)的出現(xiàn)，CPU可以把直接控制輸入/輸出的工作轉(zhuǎn)給通道(tngdo)。共三百九十五頁(yè)多道程序的目標(biāo)、方法和主要問(wèn)題（1）目標(biāo)：是充分使用系統(tǒng)所有(suyu)資源并盡可能地使它們并行工作，這種技術(shù)可把硬件的代價(jià)交叉分

5、布在大量并行用戶(hù)之間，而使計(jì)算機(jī)系統(tǒng)的代價(jià)極小化。（2）方法：是一個(gè)正在運(yùn)行的程序不使用某設(shè)備時(shí)，讓另一程序去使用該設(shè)備。為了發(fā)揮多道程序設(shè)計(jì)的有效性，應(yīng)選擇各種不同類(lèi)型的作業(yè)同時(shí)執(zhí)行，讓資源處于忙碌狀態(tài)。（3）多道程序設(shè)計(jì)實(shí)現(xiàn)的3個(gè)問(wèn)題：存儲(chǔ)保護(hù)、程序浮動(dòng)、處理機(jī)和系統(tǒng)資源的管理和調(diào)度。 共三百九十五頁(yè)多道程序系統(tǒng)所必須解決(jiju)的問(wèn)題（1）提出解決各種沖突的策略（2）協(xié)調(diào)并發(fā)活動(dòng)的關(guān)系（3）保證數(shù)據(jù)的一致性（4）實(shí)現(xiàn)數(shù)據(jù)的存取控制共三百九十五頁(yè)2.1 進(jìn)程(jnchng)的基本概念2.1.1 程序的順序執(zhí)行及其特征：順序性、封閉性、可再現(xiàn)性。作業(yè)1：什么叫程序順序執(zhí)行的封閉性和可再現(xiàn)

6、性？封閉性：程序執(zhí)行得到的最終結(jié)果由給定的初始條件決定，不受外界因素(yn s)的影響?？稍佻F(xiàn)性：只要輸入的初始條件相同，則無(wú)論何時(shí)重復(fù)執(zhí)行該程序都會(huì)得到相同的結(jié)果。共三百九十五頁(yè)2.1.2 前趨圖：有向無(wú)循環(huán)圖，DAG（Directed Acyclic Graph），描述進(jìn)程之間執(zhí)行的前后關(guān)系。直接制約關(guān)系：同步間接(jin ji)制約關(guān)系：互斥2.1.3 程序的并發(fā)執(zhí)行及其特征：間斷性(制約性)、失去封閉性、不可再現(xiàn)性（不可重復(fù)，例：變量的共享）。2.1.4 進(jìn)程的特征與狀態(tài) 引入進(jìn)程的目的：是使多個(gè)程序能并發(fā)執(zhí)行，提高資源利用率和系統(tǒng)吞吐量。共三百九十五頁(yè)進(jìn)程(jnchng)的定義進(jìn)程的

7、組成：進(jìn)程包括程序代碼（程序段或文本段）、堆棧段（臨時(shí)(ln sh)數(shù)據(jù)，如函數(shù)參數(shù)、返回地址和局部變量）、數(shù)據(jù)段（包括全局變量）、堆（進(jìn)行運(yùn)行期間動(dòng)態(tài)分配的內(nèi)存）PCB：Process Control Block進(jìn)程表空間：PT進(jìn)程圖： 內(nèi)存中的進(jìn)程如右圖示：棧堆數(shù)據(jù)文本共三百九十五頁(yè)(1)特征： 動(dòng)態(tài)性：最基本。 并發(fā)性： 獨(dú)立性：獨(dú)立運(yùn)行、獨(dú)立分配資源和獨(dú)立接受調(diào)度。 異步性：進(jìn)程以各自獨(dú)立的，不可預(yù)先的速度向前推進(jìn)。 可能會(huì)造成不正確的情況出現(xiàn)，原因與進(jìn)程占用處理器的時(shí)間、執(zhí)行的速度以及外界的影響有關(guān)，都與時(shí)間有關(guān)。稱(chēng)為(chn wi)與時(shí)間有關(guān)的錯(cuò)誤。又稱(chēng)競(jìng)爭(zhēng)條件， Race Con

8、dition結(jié)構(gòu)特征：程序段、相關(guān)的數(shù)據(jù)段和PCB構(gòu)成的進(jìn)程實(shí)體。定義：一個(gè)程序段在一個(gè)數(shù)據(jù)段上的一次執(zhí)行過(guò)程。共三百九十五頁(yè)作業(yè)2：簡(jiǎn)述進(jìn)程和程序(chngx)的區(qū)別和聯(lián)系 進(jìn)程和程序(chngx)是既有聯(lián)系又有區(qū)別的兩個(gè)概念（1）程序是指令的集合，靜態(tài)概念，進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過(guò)程，動(dòng)態(tài)概念。（2）程序是長(zhǎng)期存在的，進(jìn)程有生命周期，有創(chuàng)建、活動(dòng)、消亡。（3）程序僅是指令的有序集合，而進(jìn)程則由程序、數(shù)據(jù)和進(jìn)程控制塊組成。（4）進(jìn)程與程序之間不是一一對(duì)應(yīng)的，即同一程序同時(shí)運(yùn)行于若干不同的數(shù)據(jù)集合上，它將屬于若干個(gè)不同的進(jìn)程，而一個(gè)進(jìn)程可以執(zhí)行多個(gè)程序。 系統(tǒng)內(nèi)的進(jìn)程能并發(fā)執(zhí)行，允許并

9、發(fā)執(zhí)行的理由：信息共享，加快計(jì)算，模塊化和方便性。共三百九十五頁(yè)(2)進(jìn)程的三種基本狀態(tài)： 就緒狀態(tài)：三種情況的進(jìn)程構(gòu)成了就緒隊(duì)列 執(zhí)行狀態(tài)：當(dāng)前進(jìn)程，至少一個(gè) 阻塞狀態(tài)：等待狀態(tài)、封鎖狀態(tài)、睡眠狀態(tài)、休眠狀態(tài)。作業(yè)3：畫(huà)出三種基本狀態(tài)之間的轉(zhuǎn)換方向并標(biāo)明每一種轉(zhuǎn)換的原因：這個(gè)時(shí)候，需要進(jìn)行重新調(diào)度，會(huì)發(fā)生進(jìn)程上下文內(nèi)容的切換(qi hun)。兩個(gè)基本隊(duì)列：就緒隊(duì)列和等待隊(duì)列。隊(duì)列管理模塊：入隊(duì)和出隊(duì)。共三百九十五頁(yè)中斷處理過(guò)程（1）喚醒被阻塞的驅(qū)動(dòng)程序進(jìn)程。（2）保護(hù)被中斷進(jìn)程的CPU環(huán)境。程序是指令在N位置時(shí)被中斷的，程序計(jì)數(shù)器中的內(nèi)容為N+1，所有寄存器的內(nèi)容都被保留在中斷保留區(qū)（棧）中

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

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

12、時(shí)刻處于運(yùn)行狀態(tài)的進(jìn)程數(shù)最多有1個(gè)。而最少可能為0，此時(shí)(c sh)其他10個(gè)進(jìn)程一定全部排在各等待隊(duì)列中，在就緒隊(duì)列中沒(méi)有進(jìn)程，在實(shí)際的操作系統(tǒng)中，此時(shí)(c sh)CPU是在運(yùn)行操作系統(tǒng)的空閑進(jìn)程（System Idle Process）或線(xiàn)程。共三百九十五頁(yè)（2）處于就緒狀態(tài)的進(jìn)程數(shù)最多只有9個(gè)，不可能出現(xiàn)10個(gè)，因?yàn)橐坏〤PU有空，調(diào)度程序馬上調(diào)度；處于就緒狀態(tài)的進(jìn)程數(shù)最少是0個(gè)，1個(gè)進(jìn)程運(yùn)行，9個(gè)進(jìn)程等待(dngdi)，或者10個(gè)進(jìn)程全部等待(dngdi)。（3）處于等待狀態(tài)的進(jìn)程數(shù)最多有10個(gè)，等待狀態(tài)的進(jìn)程最少是個(gè)。例3：某系統(tǒng)在t0時(shí)刻，打印機(jī)剛剛打印完畢或者剛剛開(kāi)始打印，試問(wèn)該

13、時(shí)刻系統(tǒng)內(nèi)部發(fā)生了進(jìn)程狀態(tài)變化的情況如何？共三百九十五頁(yè)2.1.5 進(jìn)程控制塊：任務(wù)控制塊1、PCB的作用(zuyng)：將程序變成可并發(fā)執(zhí)行的進(jìn)程，是進(jìn)程存在的惟一標(biāo)志。操作系統(tǒng)是根據(jù)PCB來(lái)對(duì)并發(fā)執(zhí)行的進(jìn)程進(jìn)行控制和管理的。常駐內(nèi)存。系統(tǒng)會(huì)集中存儲(chǔ)所有進(jìn)程的PCB，構(gòu)成進(jìn)程表空間PT。 共三百九十五頁(yè)2、PCB中的信息 (1)進(jìn)程標(biāo)識(shí)(biozh)符：內(nèi)部和外部標(biāo)識(shí)(biozh) (2)處理機(jī)狀態(tài)：通用寄存器、PC、PSW（標(biāo)志寄存器）和用戶(hù)棧指針。 (3)進(jìn)程調(diào)度信息：進(jìn)程狀態(tài)、進(jìn)程優(yōu)先級(jí)、調(diào)度的其他信息、阻塞事件。 (4)進(jìn)程控制信息：程序和數(shù)據(jù)的地址、同步和通信機(jī)制、資源清單和鏈接指

14、針。3、PCB的組織方式：鏈接和索引。共三百九十五頁(yè)作業(yè)4：試從進(jìn)程(jnchng)管理、中斷處理、文件管理、存儲(chǔ)管理、設(shè)備管理的角度設(shè)計(jì)進(jìn)程(jnchng)控制塊應(yīng)包含的項(xiàng)目。（北京大學(xué)1999年研究生試題）解：1、從進(jìn)程管理的角度考慮，PCB應(yīng)包含進(jìn)程標(biāo)識(shí)符、進(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ì)列互斥訪(fǎng)問(wèn)的互斥信號(hào)量、描述消息隊(duì)列中消息個(gè)數(shù)的資源信號(hào)量。3、從中斷處理的角度考慮，PCB中應(yīng)包含CPU狀態(tài)信息。共

15、三百九十五頁(yè)4、從文件管理的角度考慮，PCB中應(yīng)包含用戶(hù)文件描述符表，用來(lái)登記用戶(hù)打開(kāi)的各個(gè)文件，并可以通過(guò)它找到在內(nèi)存的相應(yīng)文件的FCB5、從存儲(chǔ)管理的角度考慮，應(yīng)保存進(jìn)程的程序、數(shù)據(jù)、堆棧在內(nèi)存和外存的地址和各部分長(zhǎng)度等信息(xnx)。6、從設(shè)備管理角度考慮，應(yīng)有該進(jìn)程所需資源和已分配到的資源清單。共三百九十五頁(yè)進(jìn)程上下文（Context）實(shí)際上是進(jìn)程執(zhí)行活動(dòng)(hu dng)全過(guò)程的靜態(tài)描述。又稱(chēng)進(jìn)程映像。包括三個(gè)組成部分：（1）用戶(hù)級(jí)上下文。由用戶(hù)程序代碼、用戶(hù)數(shù)據(jù)段（含共享數(shù)據(jù)塊）和用戶(hù)堆棧組成的進(jìn)程地址空間。（2）系統(tǒng)級(jí)上下文。包括進(jìn)程的標(biāo)識(shí)信息、現(xiàn)場(chǎng)信息、控制信息、進(jìn)程環(huán)境塊，以及

16、系統(tǒng)堆棧等組成的進(jìn)程地址空間。（3）寄存器上下文。由程序狀態(tài)字寄存器和各類(lèi)控制寄存器、地址寄存器、通用寄存器組成。共三百九十五頁(yè)Context Switch發(fā)生在寄存器和內(nèi)存之間，依賴(lài)于內(nèi)存速度，復(fù)制的寄存器的數(shù)量，是否(sh fu)有特殊指令等。 可再入程序是指一個(gè)能被多個(gè)用戶(hù)同時(shí)調(diào)用的程序：必須是純代碼，要求調(diào)用者提供工作區(qū)。共三百九十五頁(yè)2.2 進(jìn)程(jnchng)控制作業(yè)5：原語(yǔ)操作的定義：是指由若干條指令組成、用來(lái)實(shí)現(xiàn)某個(gè)特定操作的一個(gè)過(guò)程，其執(zhí)行具有原子性，即原語(yǔ)在執(zhí)行過(guò)程中不允許被中斷，常駐內(nèi)存，在核心(hxn)態(tài)下運(yùn)行。共三百九十五頁(yè)2.2.1 進(jìn)程的創(chuàng)建：fork()、Cre

17、ateProcess()(1)進(jìn)程圖：描述一個(gè)進(jìn)程的家族關(guān)系的有向圖。(2)引起創(chuàng)建進(jìn)程的事件：用戶(hù)登錄，作業(yè)調(diào)度，提供服務(wù)和應(yīng)用請(qǐng)求。(3)進(jìn)程的創(chuàng)建：申請(qǐng)(shnqng)空白PCB，為新進(jìn)程分配資源，初始化PCB，將新進(jìn)程插入就緒隊(duì)列。(4)進(jìn)程的創(chuàng)建請(qǐng)求系統(tǒng)為一個(gè)程序分配一個(gè)工作區(qū)和建立一個(gè)進(jìn)程控制塊。2013.3.22 計(jì)算機(jī)共三百九十五頁(yè)當(dāng)進(jìn)程創(chuàng)建新進(jìn)程時(shí)，有兩種執(zhí)行可能：（1）父進(jìn)程與子進(jìn)程并發(fā)執(zhí)行（2）父進(jìn)程等待，直到某個(gè)或全部(qunb)子進(jìn)程執(zhí)行完。新進(jìn)程的地址空間也有兩種可能（1）子進(jìn)程是父進(jìn)程的復(fù)制品（具有與父進(jìn)程相同的程序和數(shù)據(jù)）（2）子進(jìn)程裝入另一個(gè)新程序共三百九十五

18、頁(yè)2.2.2 進(jìn)程的終止(1)引起進(jìn)程終止的事件：正常結(jié)束，異常結(jié)束和外界干預(yù)(gny)。(2)進(jìn)程的終止過(guò)程：檢索PCB，判斷狀態(tài)，撤銷(xiāo)子進(jìn)程，歸還資源，清空PCB。(3)進(jìn)程的撤消，系統(tǒng)收回該進(jìn)程所用的工作區(qū)，取消進(jìn)程控制塊。Exit()、TerminatePorcess()共三百九十五頁(yè)父進(jìn)程終止其子進(jìn)程的原因（1）子進(jìn)程使用了超過(guò)它所分配(fnpi)到的一些資源（2）分配給子進(jìn)程的任務(wù)已不再需要（3）父進(jìn)程退出，如果父進(jìn)程終止，操作系統(tǒng)不允許子進(jìn)程繼續(xù)。級(jí)聯(lián)終止Cascading termination。VMS。共三百九十五頁(yè)2.2.3 進(jìn)程(jnchng)的阻塞與喚醒sleep()和

19、wakeup()(1)引起進(jìn)程阻塞和喚醒的事件：請(qǐng)求系統(tǒng)服務(wù)，啟動(dòng)某種操作，新數(shù)據(jù)尚未到達(dá)和無(wú)新工作可做。(2)進(jìn)程阻塞過(guò)程：是正在執(zhí)行的進(jìn)程的一種主動(dòng)行為。(3)進(jìn)程喚醒過(guò)程：2.2.4 進(jìn)程的掛起與激活:交換進(jìn)程(0號(hào)進(jìn)程，sched)(1)進(jìn)程的掛起；從內(nèi)存置換到外存。(2)進(jìn)程的激活過(guò)程：重新調(diào)入內(nèi)存。共三百九十五頁(yè)2.3 進(jìn)程同步與互斥2.3.1 進(jìn)程同步的基本概念并發(fā)進(jìn)程間的關(guān)系可以(ky)是無(wú)關(guān)的，也可以(ky)是有交往的。獨(dú)立進(jìn)程或協(xié)作進(jìn)程。 1、兩種制約關(guān)系： 間接制約關(guān)系：互斥進(jìn)程互斥是指當(dāng)有若干個(gè)進(jìn)程使用某一共享資源時(shí)，任何時(shí)刻最多只允許一個(gè)進(jìn)程使用，而其他要使用該資源的

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

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

22、非搶占式內(nèi)核，傳統(tǒng)的Unix和Linux 2.6以前的內(nèi)核也是非搶占式的。Linux 2.6以后，商用Unix、Solaris是搶占內(nèi)核共三百九十五頁(yè)2、臨界資源：一次只允許一個(gè)進(jìn)程使用的資源。打印機(jī)、磁帶機(jī)、消息緩沖隊(duì)列、變量、數(shù)組、緩沖區(qū)等。又稱(chēng)獨(dú)享資源。 3、臨界區(qū)：實(shí)現(xiàn)(shxin)互斥的方法：軟件和硬件方法1965年Dijkstra(狄克斯特拉)提出的臨界段設(shè)計(jì)原則4、同步機(jī)制的規(guī)則：空閑讓進(jìn)，忙則等待，有限等待和讓權(quán)等待。（在單處理機(jī)系統(tǒng)中是必須的，在多處理機(jī)系統(tǒng)中不是必須的） 共三百九十五頁(yè)實(shí)現(xiàn)同步(tngb)的幾種方法1、禁止中斷：只適合單處理器環(huán)境，會(huì)出現(xiàn)餓死。2、TestA

23、ndSet Lock指令：不可分的原子操作(cozu),可適用于多處理器環(huán)境。Boolean TestAndSet(boolean locked) if(locked) return true; else locked=true; return false; 共三百九十五頁(yè)TSL算法(sun f)Enter_region: TSL REGISTER,LOCK復(fù)制樂(lè)到寄存器并將鎖設(shè)為1 CMP REGISTER,#0 JNE enter_region若不是0,說(shuō)明鎖已被設(shè)置，所以循環(huán) RET 返回調(diào)用者，進(jìn)入(jnr)了臨界區(qū)Leave_region: MOVE LOCK,#0 在鎖中存入0 R

24、ET 返回調(diào)用者共三百九十五頁(yè)3、Swap指令(zhlng) boolean void Swap(boolean a,boolean b) boolean temp; temp=b; b=a; a=temp; 共三百九十五頁(yè)Swap算法(sun f)Do key=TRUE; swap(&lock,&key); critical section; lock=FALSE; remainder section; while(TRUE);共三百九十五頁(yè)4、Dekker算法(sun f)和Peterson算法(sun f)：基于軟件的兩個(gè)進(jìn)程間的通信。 Bakery算法，用于N個(gè)進(jìn)程間的通信共三百九十五

25、頁(yè)P(yáng)eterson解法(ji f)#define FALSE 0#define TRUE 1#define N 2 ;進(jìn)程數(shù)量Int turn;現(xiàn)在輪到誰(shuí)Int interestedN;所有值初始化為0,即FALSE；Void enter_region(int process);進(jìn)程是0或1 int other;其他進(jìn)程號(hào) other=1-process;另一方進(jìn)程 interestedprocess=TRUE;表明所感興趣的 turn=process;設(shè)置標(biāo)志(biozh) while(turn=process&interestedother=TRUE)； Void leave_region

26、(int process)進(jìn)程：誰(shuí)離開(kāi)？ interestedprocess=FALSE;表示離開(kāi)臨界區(qū)共三百九十五頁(yè)P(yáng)eterson算法(sun f)中Pi的結(jié)構(gòu)Do flagi=TRUE; turn=j; while(flagj&turn=j); 臨界(ln ji)區(qū)； flagi=FALSE; 剩余區(qū)； while(TRUE);共三百九十五頁(yè)2.3.2 信號(hào)量機(jī)制 1、整型信號(hào)量：P、V操作 wait(s):while s=0 do nothing; s=s-1;信號(hào)量的值不可能取負(fù)值。 signal(s):s=s+1;又稱(chēng)簡(jiǎn)單信號(hào)量，二元信號(hào)量，二進(jìn)制信號(hào)量，互斥鎖。缺點(diǎn)(qudin)

27、：忙等待方式busy waiting,自旋鎖（優(yōu)點(diǎn)：不進(jìn)行上下文切換，常用于多處理系統(tǒng)）2013.3.24網(wǎng)絡(luò)共三百九十五頁(yè)2、記錄型信號(hào)量： struct semaphore int:value; struct process *L; s; wait(s): s.value=s.value-1; if s.value0 then block(s.L);信號(hào)量的遞減和測(cè)試次序的互換，其值可取(kq)負(fù)值。 signal(s):s.value=s.value+1; if s.value=0 then wakeup(s.L);又稱(chēng)計(jì)數(shù)信號(hào)量，資源信號(hào)量，用來(lái)控制m個(gè)進(jìn)程訪(fǎng)問(wèn)某一類(lèi)n個(gè)臨界資源。共三

28、百九十五頁(yè)作業(yè)7:記錄型信號(hào)量的物理含義(hny)：例：設(shè)有n個(gè)進(jìn)程共享一個(gè)程序段，對(duì)于如下兩種情況：（1）如果每次只允許一個(gè)進(jìn)程進(jìn)入該程序段。（2）如果每次最多允許m個(gè)進(jìn)程（m0)個(gè)單元的緩沖區(qū)。P1每次用produce()生成一個(gè)正整數(shù)并用put()送入緩沖區(qū)某一空單元中；P2每次用getodd()從該緩沖區(qū)中取出一個(gè)奇數(shù)并用countodd()統(tǒng)計(jì)奇數(shù)個(gè)數(shù)；P3每次用geteven()從該緩沖區(qū)中取出一個(gè)偶數(shù)并counteven()統(tǒng)計(jì)偶數(shù)個(gè)數(shù)。請(qǐng)用信號(hào)量機(jī)制實(shí)現(xiàn)這三個(gè)進(jìn)程的同步與互斥活動(dòng)，并說(shuō)明所定義信號(hào)量的含義。要求用偽代碼描述。 共三百九十五頁(yè)答案：定義信號(hào)量S1控制P1與P2之間

29、的同步；S2控制P1與P3之間的同步；empty控制生產(chǎn)者與消費(fèi)者之間的同步；mutex控制進(jìn)程間互斥使用緩沖區(qū)。程序(chngx)如下： Var s1=0,s2=0,empty=N,mutex=1; Parbegin P1:begin X=produce(); /*生成一個(gè)數(shù)*/ P(empty);/*判斷緩沖區(qū)是否有空單元*/ P(mutex); /*緩沖區(qū)是否被占用*/ put(x); If x%2=0 V(s2); /*如果是偶數(shù)，向P3發(fā)出信號(hào)*/ else V(s1); /*如果是奇數(shù)，向P2發(fā)出信號(hào)*/ V(mutex); /*使用完緩沖區(qū)，釋放*/ 共三百九十五頁(yè)P(yáng)2：begi

30、n P(s1); /*收到P1發(fā)來(lái)的信號(hào)(xnho)，已產(chǎn)生一個(gè)奇數(shù)*/ P(mutex); /*緩沖區(qū)是否被占用*/ Getodd(); Countodd():=coutodd()+1; V(mutex); /*釋放緩沖區(qū)*/ V(empty); /*向P1發(fā)信號(hào)，多出一個(gè)空單元*/ End. 共三百九十五頁(yè)P(yáng)3:begin P(s2); /*收到P1發(fā)來(lái)的信號(hào)，已產(chǎn)生一個(gè)偶數(shù)*/ P(mutex); /*緩沖區(qū)是否被占用(zhn yn)*/ Geteven(); Counteven():=counteven()+1; V(mutex); /* 釋放緩沖區(qū)*/ V(empty); /*向P1

31、發(fā)信號(hào)，多出一個(gè)空單元*/End.Parend.共三百九十五頁(yè)2.4.2 讀者和寫(xiě)者問(wèn)題：一直用來(lái)測(cè)試幾乎所有新的同步原語(yǔ)。多個(gè)用戶(hù)(yngh)共享數(shù)據(jù)庫(kù)系統(tǒng)的建模問(wèn)題。有多種不同的策略，都與優(yōu)先級(jí)有關(guān)。 1、讀者優(yōu)先：第一讀者-寫(xiě)者問(wèn)題，寫(xiě)者可能饑餓。 2、排隊(duì)策略或先來(lái)先服務(wù) 3、寫(xiě)者優(yōu)先：第二讀者-寫(xiě)者問(wèn)題，讀者可能饑餓。 4、某個(gè)進(jìn)程即是寫(xiě)者又是讀者的問(wèn)題共三百九十五頁(yè)例：設(shè)有P1,P2,P3三個(gè)進(jìn)程共享某一資源F，P1對(duì)F只讀不寫(xiě)，P2對(duì)F只寫(xiě)不讀，P3對(duì)F先讀后寫(xiě)。當(dāng)一個(gè)(y )進(jìn)程寫(xiě)F時(shí)，其他進(jìn)程對(duì)F不能進(jìn)行讀寫(xiě)，但多個(gè)進(jìn)程同時(shí)讀F是允許的。試用P、V操作正確實(shí)現(xiàn)P1,P2,P3

32、的同步互斥。要求：（1）正常運(yùn)行時(shí)不產(chǎn)生死鎖（2）使用F的并發(fā)度要高。（北京大學(xué)1996年研究生試題） 共三百九十五頁(yè)解：本題實(shí)際上是一個(gè)讀者和寫(xiě)者問(wèn)題，P1是一個(gè)讀者，P2是一個(gè)寫(xiě)者，為了使F的并發(fā)度較高，將P3先看成讀者，當(dāng)其完成讀操作后，再將其看成寫(xiě)者。 定義(dngy)如下變量： int readcount=0; semaphore rmutex=1,mutex=1; 共三百九十五頁(yè)P(yáng)1( ) While(1) P(rmutex); If(readcount=0)P(mutex); Readcount+; V(rmutex); 讀F； P（rmutex）; Readcount-; If

33、(readcount=0)V(mutex); V(rmutex);共三百九十五頁(yè)P(yáng)2() While(1) P(mutex); 寫(xiě)F； V（mutex）;共三百九十五頁(yè)P(yáng)3() 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); 寫(xiě)F； V(mutex); 共三百九十五頁(yè)2.4.3 哲學(xué)家進(jìn)餐問(wèn)題：是一個(gè)并發(fā)控制問(wèn)題，在多個(gè)進(jìn)程之間分配(fnpi)多個(gè)資源且不會(huì)出現(xiàn)死

34、鎖和饑餓的問(wèn)題。方法： 1、同時(shí)允許四個(gè)哲學(xué)家提出進(jìn)餐要求 2、同時(shí)去拿起兩邊的筷子 3、使用非對(duì)稱(chēng)解決方法，奇數(shù)號(hào)哲學(xué)家先拿左邊的筷子，偶數(shù)號(hào)哲學(xué)家先拿右邊的筷子注意：沒(méi)有死鎖的解決方案并不能消除餓死的可能性。共三百九十五頁(yè)2.4.4 理發(fā)師嗜睡問(wèn)題 一個(gè)理發(fā)店由一個(gè)有N張椅子的等候室和一個(gè)放有一張理發(fā)椅的理發(fā)室組成。若沒(méi)有要理發(fā)的顧客，則理發(fā)師就去睡覺(jué)，若一個(gè)顧客走進(jìn)理發(fā)店且所有的椅子都被占用了，則該顧客就離開(kāi)理發(fā)店，若理發(fā)師正在為人理發(fā)，則該顧客就找一張空椅子坐下等待，若理發(fā)師在睡覺(jué)，則顧客就喚醒他。 試用(shyng)信號(hào)量設(shè)計(jì)一個(gè)協(xié)調(diào)理發(fā)師和顧客的程序。（西安電子科技大學(xué)2000年研

35、究生試題） 共三百九十五頁(yè)解：本題中，顧客進(jìn)程和理發(fā)師進(jìn)程之間存在著多種同步(tngb)關(guān)系：（1）只有在理發(fā)椅空閑時(shí)，顧客才能坐到理發(fā)椅上等待理發(fā)師理發(fā)，否則顧客便必須等待；只有當(dāng)理發(fā)椅上有顧客時(shí)，理發(fā)師才可以開(kāi)始理發(fā)，否則他也必須等待。這種同步關(guān)系類(lèi)似于單緩沖（理發(fā)椅）的生產(chǎn)者和消費(fèi)者問(wèn)題中的同步關(guān)系，故可以通過(guò)信號(hào)量empty(初值為1)和full(初值為0)來(lái)控制。（2）理發(fā)師為顧客理發(fā)時(shí)，顧客必須等待理發(fā)的完成，并在理發(fā)完成后由理發(fā)師喚醒他，這可單獨(dú)使用一個(gè)信號(hào)量cut來(lái)控制，初值為0。 共三百九十五頁(yè)（3）顧客理完發(fā)后必須向理發(fā)師付費(fèi)，并等理發(fā)師收費(fèi)后顧客才能離開(kāi)；而理發(fā)師則需等待

36、顧客付費(fèi)，并在收費(fèi)后喚醒顧客以允許他離開(kāi)，這可分別通過(guò)兩個(gè)信號(hào)量payment和receipt來(lái)控制，初值都為0。（4）等候室中的N張沙發(fā)是顧客進(jìn)程競(jìng)爭(zhēng)的資源，故還需為它們?cè)O(shè)置了一個(gè)資源信號(hào)量sofa，初值為n（5）為了控制顧客的人數(shù)(rn sh)，使顧客能在所有的沙發(fā)都被占用時(shí)離開(kāi)理發(fā)店，還必須設(shè)置一個(gè)整型變量count來(lái)對(duì)理發(fā)店中的顧客進(jìn)行計(jì)數(shù)，該變量將被多個(gè)顧客進(jìn)程互斥地訪(fǎng)問(wèn)并修改，這可通過(guò)一個(gè)互斥信號(hào)量mutex來(lái)實(shí)現(xiàn)，初值為1共三百九十五頁(yè)Guestbegin wait(mutex); if(countN)then begin signal(muetx); 離開(kāi)(l ki)理發(fā)店;

37、end else begin共三百九十五頁(yè) count=count+1; if(count1) then begin wait(sofa); 在沙發(fā)(shf)中就座; wait(empty); 從沙發(fā)上起來(lái); signal(sofa); end else /*count=1*/ wait(empty); 在理發(fā)椅上就座; signal(full); wait(cut);共三百九十五頁(yè) 理發(fā)(l f)； 付費(fèi)； signal(payment); wait(receipt); 從理發(fā)椅上起來(lái); signal(empty); wait(mutex); count=count-1; signal(mu

38、tex); 離開(kāi)理發(fā)店; end end共三百九十五頁(yè)barber:begin repeat wait(full); 替顧客(gk)理發(fā); signal(cut); wait(payment); 收費(fèi); signal(receipt); until false; endparendend 共三百九十五頁(yè)2.4.5 “吸煙者”問(wèn)題。假設(shè)一個(gè)系統(tǒng)有3個(gè)吸煙者（smoker）進(jìn)程和一個(gè)供貨商（Agent）進(jìn)程。每個(gè)吸煙者連續(xù)不斷地制造香煙并吸掉它。 但是，制造一支香煙需要3種材料煙、紙、火柴。一個(gè)吸煙者進(jìn)程有紙，另一個(gè)有煙，第三個(gè)有火柴。供貨商進(jìn)程可以無(wú)限地提供這3種材料。供貨商將這這兩種材料一起放

39、在桌上，持有另一種材料的吸煙者即可制造一支香煙并吸掉它。當(dāng)此吸煙者抽香煙時(shí)，它發(fā)出一個(gè)信號(hào)通知供貨商進(jìn)程，供貨商馬上給出另外兩種材料，如此循環(huán)往復(fù)(xn hun wng f)。試編寫(xiě)一個(gè)程序使供貨商和吸煙者同步執(zhí)行。共三百九十五頁(yè)解法：semaphore smoker30; 三個(gè)吸煙者semaphore material30; 三種(sn zhn)原料semaphore agent1; 供應(yīng)商int turn=0;輪到誰(shuí)Main()CobeginAgent While(1) P(agent); 放原料； V(smokerturn); V(material(turn+1)%3); V(mater

40、ial(turn+2)%3); turn=(turn+1)%3共三百九十五頁(yè)Smoker_i While(1) P(smokeri); P(material(i+1)%3); P(material(i+2)%3); 制作(zhzu)香煙； 吸煙； V(agent); coend;共三百九十五頁(yè)變型(bin xn)1抽煙問(wèn)題：有一個(gè)煙草代理和三個(gè)抽煙者。抽煙者若要抽煙，必須具有煙葉、煙紙和火柴。三個(gè)抽煙者中，一人缺煙葉、一人缺煙紙、一人缺火柴。煙草代理會(huì)源源不斷地分別供應(yīng)煙葉、煙紙和火柴，并將它們放在桌上。如果放的是煙葉，則缺煙葉的抽煙者拾起煙葉，制作香煙，然后(rnhu)抽煙；其他類(lèi)推。試用信

41、號(hào)量同步煙草代理和三個(gè)抽煙者。共三百九十五頁(yè)解法：semaphore smoker30; 三個(gè)吸煙者semaphore material30; 三種原料semaphore agent1; 供應(yīng)商int turn=0;輪到誰(shuí)Agent While(1) P(agent); 放原料； V(smokerturn); V(material(turn+1)%3); 制作(zhzu)香煙； 吸煙； turn=(turn+1)%3共三百九十五頁(yè)Smoker_i While(1) P(smokeri); P(material(i+1)%3); 制作(zhzu)香煙； 吸煙； V(agent); 共三百九十五頁(yè)

42、變型(bin xn)2有一間酒吧里有3個(gè)音樂(lè)愛(ài)好者隊(duì)列，第1隊(duì)的音樂(lè)愛(ài)好者只有隨身聽(tīng)，第2隊(duì)只有音樂(lè)磁帶，第3隊(duì)只有電池。而要聽(tīng)音樂(lè)就必須隨身聽(tīng)、音樂(lè)磁帶和電池這3種物品俱全。酒吧老板一次出售這3種物品中的任意兩種。當(dāng)一名音樂(lè)愛(ài)好者得到這3種物品并聽(tīng)完一首樂(lè)曲后，酒吧老板才能再一次出售這3種物品中的任意兩種，于是第2名音樂(lè)愛(ài)好者得到這3種物品，并開(kāi)始(kish)聽(tīng)樂(lè)曲。全部買(mǎi)賣(mài)就這樣進(jìn)行下去。試用P、V操作正確解決這一買(mǎi)賣(mài)。（北京大學(xué)1999年研究生試題）共三百九十五頁(yè)變型(bin xn)3（桔子汁生產(chǎn)線(xiàn)問(wèn)題）現(xiàn)有三個(gè)生產(chǎn)者P1 、P2 、P3 ，他們都要生產(chǎn)水，每個(gè)生產(chǎn)者都已分別購(gòu)得兩種不同

43、原料，待購(gòu)得第三種原料后就可配制成桔子水，裝瓶出售。有一供應(yīng)商能源源不斷地供應(yīng)糖、水、桔子精，但每次只拿出一種原料放入容器(rngq)中供給生產(chǎn)者。當(dāng)容器(rngq)中有原料時(shí)需要該原料的生產(chǎn)者可取走，當(dāng)容器(rngq)空時(shí)供應(yīng)商又可放入一種原料。假定：生產(chǎn)者P1已購(gòu)得糖和水；生產(chǎn)者P2 已購(gòu)得水和桔子精；生產(chǎn)者P3 已購(gòu)得糖和桔子精；試用：信號(hào)量與P 、V 操作，寫(xiě)出供應(yīng)商和三個(gè)生產(chǎn)者之間能正確同步的程序 共三百九十五頁(yè)2.4.6 銀行排隊(duì)問(wèn)題(北京大學(xué)2000）銀行有n個(gè)柜員,每個(gè)顧客(gk)進(jìn)入銀行后先取一個(gè)號(hào),并且等著叫號(hào),當(dāng)一個(gè)柜員空閑后，就叫下一個(gè)號(hào)。解：將顧客號(hào)碼排成一個(gè)隊(duì)列,顧

44、客進(jìn)入銀行領(lǐng)取號(hào)碼后,將號(hào)碼由隊(duì)尾插入;柜員空閑時(shí),從隊(duì)首取得顧客號(hào)碼,并且為這個(gè)顧客服務(wù),由于隊(duì)列為若干進(jìn)程共享, 所以需要互斥.柜員空閑時(shí),若有顧客,就叫下一個(gè)顧客為之服務(wù).因此,需要設(shè)置一個(gè)信號(hào)量來(lái)記錄等待服務(wù)的顧客數(shù).共三百九十五頁(yè)Cobegin var mutex=1,customer_count=0:semaphore; cobegin process customer begin repeat 取號(hào)碼； p(mutex); 進(jìn)入(jnr)隊(duì)列； v(mutex); v(customer_count); until false; end共三百九十五頁(yè)process servers_

45、i(i=1,.,n)begin repeat p(customer_count); p(mutex); 從隊(duì)列(duli)中取下一個(gè)號(hào)碼； v(mutex); 為該號(hào)碼持有者服務(wù)； until falseendCoend共三百九十五頁(yè)變型(bin xn)-面包師問(wèn)題面包店有很多面包，由n個(gè)銷(xiāo)售人員推銷(xiāo)。每個(gè)顧客進(jìn)店后先取一個(gè)號(hào)，并且等待叫號(hào)。當(dāng)一個(gè)銷(xiāo)售人員空閑下來(lái)(xi li)時(shí)，就叫下一個(gè)號(hào)。試設(shè)計(jì)一個(gè)使銷(xiāo)售人員和顧客同步的算法。共三百九十五頁(yè)2.4.7 交通(jiotng)問(wèn)題有橋如圖示：（北京大學(xué)(bi jn d xu)1992年研究生試題）橋北南共三百九十五頁(yè)車(chē)流如箭頭(jintu)所

46、示。橋上不允許兩車(chē)交會(huì)，但允許同方向車(chē)輛依次通行（即橋上可以有多個(gè)同方向的車(chē)）。用P、V操作實(shí)現(xiàn)交通管理以防止橋上堵塞。解：設(shè)置countA和countB表示由南往北、由北 往南已在橋上行駛的汽車(chē)數(shù)目，初值為0,設(shè)置SA表示對(duì)countA的互斥，初值為1 ，設(shè)置SB表示對(duì)countB的互斥，初值為1,設(shè)置mutex表示對(duì)橋的互斥，初值為1共三百九十五頁(yè)P(yáng)1：由南往北行駛(xngsh)到橋頭； P（SA）;If(countA=0)P(mutex);countA+;V(SA);過(guò)橋；P(SA); countA-; if(countA=0)V(mutex);V(SA);共三百九十五頁(yè)P(yáng)2：由北往南行

47、駛(xngsh)到橋頭； P（SB）;If(countB=0)P(mutex);countB+;V(SB);過(guò)橋；P(SB); countB-; if(countB=0)V(mutex);V(SB);共三百九十五頁(yè)管程機(jī)制(jzh)（略）1、管程的定義：是由一組局部的變量對(duì)局部變量進(jìn)行(jnxng)操作的一組過(guò)程以及對(duì)局部變量進(jìn)行(jnxng)初始化的語(yǔ)句序列構(gòu)成的一個(gè)軟件模塊?？捎脕?lái)實(shí)現(xiàn)進(jìn)程同步。Type monitor_name=monitor variable declarations; procedure entry P1(); begin end; procedure entry P

48、n(); begin end;Begin initialization code;end共三百九十五頁(yè)管程的特點(diǎn)(tdin)1、管程內(nèi)的局部變量只能被局限于管程內(nèi)的過(guò)程所訪(fǎng)問(wèn)；反之亦然，即局部于管程內(nèi)的過(guò)程只能訪(fǎng)問(wèn)管程內(nèi)的變量。2、任何(rnh)進(jìn)程只能通過(guò)調(diào)用管程提供的過(guò)程入口進(jìn)入管程3、任一時(shí)刻，最多只能有一個(gè)進(jìn)程在管程中執(zhí)行。 保證進(jìn)程互斥進(jìn)入管程是由編譯器負(fù)責(zé)，即管程是一種編程語(yǔ)言的構(gòu)件，它的實(shí)現(xiàn)需要編譯器的支持。共三百九十五頁(yè)管程解決(jiju)生產(chǎn)者消費(fèi)者問(wèn)題先建立(jinl)一個(gè)管程。Type P_C=monitor var in,out,count:integer; buffe

49、r: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; count:=count+1; notempty.signal end共三百九十五頁(yè) procedure entry get(var product:item) begin if count0，該進(jìn)程繼續(xù)執(zhí)行；若S0，則阻塞該進(jìn)程，并把它插入該信號(hào)量對(duì)應(yīng)的阻塞隊(duì)列中，重新進(jìn)程調(diào)度

50、。共三百九十五頁(yè)10、敘述進(jìn)程和程序的主要區(qū)別。解：進(jìn)程和程序是既有聯(lián)系又有區(qū)別的兩個(gè)概念，它們的主要區(qū)別如下：（1）程序是指令的有序集合，其本身沒(méi)有任何運(yùn)行的含義，它是一個(gè)靜態(tài)的概念。而進(jìn)程是程序在處理機(jī)上的一次執(zhí)行過(guò)程，它是一個(gè)動(dòng)態(tài)概念。（2）程序的存在是永久的。而進(jìn)程是有生命期的，它因創(chuàng)建而產(chǎn)生，因調(diào)度(diod)而執(zhí)行，因得不到資源而暫停，因撤消而消亡。（3）程序僅是指令的有序集合。而進(jìn)程則由程序、數(shù)據(jù)和進(jìn)程控制塊組成。（4）進(jìn)程與程序之間不是一一對(duì)應(yīng)的，即同一程序同時(shí)運(yùn)行若干個(gè)不同的數(shù)據(jù)集合上，它將屬于若干個(gè)不同的進(jìn)程；而一個(gè)進(jìn)程可以執(zhí)行多個(gè)程序。共三百九十五頁(yè)1、桌上有一空盤(pán)，允許

51、存放一只水果。爸爸可向盤(pán)中放蘋(píng)果，也可向盤(pán)中放桔子，兒子專(zhuān)等吃盤(pán)中的桔子，女兒專(zhuān)等吃盤(pán)中的蘋(píng)果。 規(guī)定:當(dāng)盤(pán)空時(shí)一次只能(zh nn)放一只水果供吃者取用，請(qǐng)用P、V原語(yǔ)實(shí)現(xiàn)爸爸、兒子、女兒三個(gè)并發(fā)進(jìn)程的同步。共三百九十五頁(yè)分析：本題中，爸爸、兒子、女兒共用一個(gè)盤(pán)子，且盤(pán)中一次只能放一個(gè)水果。當(dāng)盤(pán)子為空時(shí)，爸爸可將一個(gè)水果放入果盤(pán)中。若放入果盤(pán)中的是桔子，則允許兒子吃，女兒必須等待，若放入果盤(pán)中的是蘋(píng)果(pnggu)，則允許女兒吃，兒子必須等待。本題實(shí)際是生產(chǎn)者消費(fèi)者問(wèn)題的一種變形。這里，生產(chǎn)者放入緩沖區(qū)產(chǎn)品有兩類(lèi)，消費(fèi)者也有兩類(lèi)，每類(lèi)消費(fèi)者只消費(fèi)其中固定的一類(lèi)產(chǎn)品。共三百九十五頁(yè)解：本題中，

52、應(yīng)設(shè)置三個(gè)信號(hào)量s,so,sa，信號(hào)量s表示盤(pán)子(pn zi)是否為空，其初值為1，信號(hào)量so表示盤(pán)中是否有桔子，其初值為0，信號(hào)量sa表示盤(pán)中是否有蘋(píng)果，其初值為0。同步描述如下： var s,sa,so:integer=1,0,0; father:begin p(s); 將水果放入盤(pán)中； if(放入的是桔子)v(so); else v(sa); end;共三百九十五頁(yè) son:begin p(so); 從盤(pán)中取出桔子； v(s); 吃桔子； end共三百九十五頁(yè) daughter:begin p(sa); 從盤(pán)中取出蘋(píng)果(pnggu)； v(s); 吃蘋(píng)果； end共三百九十五頁(yè)2、(北京

53、大學(xué)94年試題) 進(jìn)程A1，A2，An1通過(guò)(tnggu)m個(gè)緩沖區(qū)向進(jìn)程B1，B2，Bn2不斷地發(fā)送消息。發(fā)送和接收工作遵循如下規(guī)則：(1)每個(gè)發(fā)送進(jìn)程一次發(fā)送一個(gè)消息，寫(xiě)入一個(gè)緩沖區(qū)，緩沖區(qū)大小等于消息長(zhǎng)度；共三百九十五頁(yè)(2)對(duì)每一個(gè)消息，B1，B2，Bn2都必須各接收一次，讀入各自的數(shù)據(jù)區(qū)內(nèi)。(3)m個(gè)緩沖區(qū)都滿(mǎn)時(shí)，發(fā)送進(jìn)程等待，沒(méi)有可讀的消息時(shí)，接收進(jìn)程等待。試用P、V操作組織正確(zhngqu)的發(fā)送和接收工作。共三百九十五頁(yè)分析：本題是生產(chǎn)者消費(fèi)者問(wèn)題的一個(gè)變形，一組生產(chǎn)者和一組消費(fèi)者共用m個(gè)緩沖區(qū)，每個(gè)緩沖區(qū)只要寫(xiě)一次，但需要讀n2次。所以，我們可以把這一組緩沖區(qū)看成n2組緩沖

54、區(qū)，每個(gè)發(fā)送者需要同時(shí)寫(xiě)n2組緩沖區(qū)中相應(yīng)(xingyng)的n2個(gè)緩沖區(qū)，而每一個(gè)接收者只需讀它自己對(duì)應(yīng)的那組緩沖區(qū)中的對(duì)應(yīng)單元。共三百九十五頁(yè)解：本題中，應(yīng)設(shè)置一個(gè)(y )信號(hào)量mutex實(shí)現(xiàn)諸進(jìn)程對(duì)緩沖區(qū)的互斥訪(fǎng)問(wèn)；兩個(gè)信號(hào)量數(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; 共三百九十五頁(yè) send:begin

55、 for(i=0;i=n2-1;i+) p(emptyi); p(mutex); 將消息(xio xi)放入緩沖區(qū)； v(mutex); for(i=0;i=n2-1;i+) v(fulli); end;共三百九十五頁(yè) receive_i:begin p(fulli); p(mutex); 將消息(xio xi)從緩沖區(qū)取出； v(mutex); v(emptyi); end; 共三百九十五頁(yè)Ai:begin repeat send(); until false; end Bi:begin repeat receive(i); until false; end共三百九十五頁(yè)3、(北京大學(xué)90年

56、試題)(略) (1)寫(xiě)出P、V操作的定義 (2)有三個(gè)進(jìn)程PA、PB和PC合作(hzu)解決文件打印問(wèn)題：PA將文件記錄從磁盤(pán)讀入主存的緩沖區(qū)1，每執(zhí)行一次讀一個(gè)記錄；PB將緩沖區(qū)1的內(nèi)容復(fù)制到緩沖區(qū)2，每執(zhí)行一次，復(fù)制一個(gè)記錄；PC將緩沖區(qū)2的內(nèi)容打印出來(lái)，每執(zhí)行一次打印一個(gè)記錄。緩沖區(qū)的大小等于一個(gè)記錄大小。請(qǐng)用P、V操作來(lái)保證文件的正確打印。共三百九十五頁(yè)解：(2)本題(bnt)中：進(jìn)程PA、PB和PC之間的關(guān)系為：PA與PB共用一個(gè)單緩沖區(qū)，而PB又與PC共用一個(gè)單緩沖區(qū)，其合作方式如圖示： 從磁盤(pán)讀入復(fù)制緩沖區(qū)1緩沖區(qū)2PAPCPB打印共三百九十五頁(yè) 當(dāng)緩沖區(qū)1為空時(shí)，PA可將一個(gè)記

57、錄讀入其中，若緩沖區(qū)1中有數(shù)據(jù)且緩沖區(qū)2為空，PB可將記錄從緩沖區(qū)1復(fù)制到緩沖區(qū)2中；若緩沖區(qū)2中有數(shù)據(jù)，則進(jìn)程PC可打印記錄。其他條件下，相應(yīng)進(jìn)程必須等待(dngdi)。實(shí)際上，這是一個(gè)生產(chǎn)者消費(fèi)者問(wèn)題。(PB既是生產(chǎn)者又是消費(fèi)者)共三百九十五頁(yè) 為遵循這一同步規(guī)則。應(yīng)設(shè)置四個(gè)信號(hào)量empty1、empty2、full1、full2，信號(hào)量empty1和empty2分別表示緩沖區(qū)1及緩沖區(qū)2是否為空，其初值為1；信號(hào)量full1和full2分別表示緩沖區(qū)1和緩沖區(qū)2是否有記錄可供處理，其初值為0。其同步描述(mio sh)如下： 初始化；共三百九十五頁(yè) PA:begin repeat 從磁盤(pán)

58、讀一個(gè)(y )記錄； p(empty1); 將記錄存入緩沖區(qū)1； v(full1); until false; end共三百九十五頁(yè) PB:begin repeat p(full1); 從緩沖區(qū)1取出記錄(jl)； v(empty1); p(empty2); 將記錄存入緩沖區(qū)2； v(full2); until false; end共三百九十五頁(yè)P(yáng)C:begin repeat p(full2); 從緩沖區(qū)2中取出記錄(jl)； v(empty2); 打印記錄； until false end共三百九十五頁(yè)中國(guó)(zhn u)礦大20044、P、V操作實(shí)現(xiàn)進(jìn)程同步與互斥(40分)(1)P、V操作是

59、原語(yǔ)，用類(lèi)似C(或C+，或Pascal，或Java)寫(xiě)出信號(hào)量和V操作的定義(5分)(2)針對(duì)您寫(xiě)出的V操作，說(shuō)明(shumng)為什么V操作要求是原語(yǔ)？(10分)(3)使用P、V操作實(shí)現(xiàn)臨界區(qū)的管理，S是信號(hào)量，說(shuō)明S初始值為1，S值小于0，等于0的物理意義(5分)共三百九十五頁(yè)(4)有三個(gè)并發(fā)進(jìn)程：R負(fù)責(zé)從輸入設(shè)備讀入信息單元逐個(gè)放到緩沖區(qū)B1，B1由兩個(gè)單元構(gòu)成；M負(fù)責(zé)從B1緩沖區(qū)逐個(gè)讀出信息單元，對(duì)信息加工處理后放入緩沖區(qū)B2，B2由兩個(gè)單元構(gòu)成；P負(fù)責(zé)從緩沖區(qū)B2逐個(gè)打印輸出信息單元。使用P、V操作實(shí)現(xiàn)它們之間的同步。(20分)(設(shè)置您需要的信號(hào)量，指出它們的初始值，畫(huà)出利用(lyn

60、g)P、V操作實(shí)現(xiàn)它們的同步的流程)共三百九十五頁(yè)中國(guó)(zhn u)礦大20035、 有一個(gè)盆子可以放兩個(gè)水果(兩個(gè)蘋(píng)果、或兩個(gè)桃子、或一個(gè)蘋(píng)果和一個(gè)桃子)。父親不停地向盆子每次只放一個(gè)蘋(píng)果，母親不停地向盆子每次只放一個(gè)桃子；兒子從盆子只取一個(gè)蘋(píng)果，消費(fèi)(xiofi)完繼續(xù)取一個(gè)蘋(píng)果消費(fèi)(xiofi)；女兒從盆子只取一個(gè)桃子，消費(fèi)(xiofi)完繼續(xù)取一個(gè)桃子消費(fèi)(xiofi)。 用P、V操作實(shí)現(xiàn)上述四個(gè)人的同步與互斥。共三百九十五頁(yè)中國(guó)(zhn u)礦大20056、 有10個(gè)計(jì)算進(jìn)程P1，P2，P10，它們負(fù)責(zé)各自的計(jì)算，計(jì)算完成后必須把一個(gè)單元的計(jì)算結(jié)果依次寫(xiě)入緩沖區(qū)B的一個(gè)單元，然后，繼