第2章教材習(xí)題解答

第2章 進(jìn)程管理“練習(xí)與思考”解答1 基本概念和術(shù)語(yǔ)進(jìn)程、進(jìn)程互斥、進(jìn)程同步、臨界資源、臨界區(qū)、死鎖進(jìn)程是程序在并發(fā)環(huán)境中的執(zhí)行過(guò)程。進(jìn)程互斥：各個(gè)進(jìn)程彼此不知道對(duì)方的存在，邏輯上沒(méi)有關(guān)系，由于競(jìng)爭(zhēng)同一資源（如打印機(jī)、文件等）而發(fā)生相互制約。 進(jìn)程同步：各個(gè)進(jìn)程不知對(duì)方的名字，但通過(guò)對(duì)某些對(duì)象（如I/O緩沖區(qū)）的共同存取來(lái)協(xié)同完成一項(xiàng)任務(wù)。臨界資源：一次僅允許一個(gè)進(jìn)程使用的資源。 臨界區(qū)：在每個(gè)進(jìn)程中訪問(wèn)臨界資源的那段程序。死鎖是指在一個(gè)進(jìn)程集合中的每個(gè)進(jìn)程都在等待僅由該集合中的另一個(gè)進(jìn)程才能引發(fā)的事件而無(wú)限期地僵持下去的局面。2 基本原理和技術(shù)（1） 在操作系統(tǒng)中為什么要引入進(jìn)程概念？它與程序的區(qū)別和聯(lián)系是什么？在操作系統(tǒng)中，由于多道程序并發(fā)執(zhí)行時(shí)共享系統(tǒng)資源，共同決定這些資源的狀態(tài)，因此系統(tǒng)中各程序在執(zhí)行過(guò)程中就出現(xiàn)了相互制約的新關(guān)系，程序的執(zhí)行出現(xiàn)“走走停?！钡男?tīng)顟B(tài)。這些都是在程序的動(dòng)態(tài)過(guò)程中發(fā)生的。用程序這個(gè)靜態(tài)概念已不能如實(shí)反映程序并發(fā)執(zhí)行過(guò)程中的這些特征。為此，人們引入“進(jìn)程”這一概念來(lái)描述程序動(dòng)態(tài)執(zhí)行過(guò)程的性質(zhì)。 進(jìn)程與程序的主要區(qū)別是： 進(jìn)程是動(dòng)態(tài)的；程序是靜態(tài)的。 進(jìn)程有獨(dú)立性，能并發(fā)執(zhí)行；程序不能并發(fā)執(zhí)行。 二者無(wú)一一對(duì)應(yīng)關(guān)系。 進(jìn)程異步運(yùn)行，會(huì)相互制約；程序不具備此特征。但進(jìn)程與程序又有密切的聯(lián)系：進(jìn)程不能脫離具體程序而虛設(shè)，程序規(guī)定了相應(yīng)進(jìn)程所要完成的動(dòng)作。（2） 進(jìn)程的基本狀態(tài)有哪幾種？通常在操作系統(tǒng)中，進(jìn)程至少要有三種基本狀態(tài)。這三種基本狀態(tài)是：運(yùn)行態(tài)、就緒態(tài)和阻塞態(tài)（或等待態(tài)）。圖3-23 進(jìn)程狀態(tài)轉(zhuǎn)換圖（3） 用如圖3-23所示的進(jìn)程狀態(tài)轉(zhuǎn)換圖能夠說(shuō)明有關(guān)處理機(jī)管理的大量?jī)?nèi)容。試回答： 什么事件引起每次顯著的狀態(tài)變遷？ 下述狀態(tài)變遷因果關(guān)系能否發(fā)生？為什么？ （A）21 （B）32 （C）41就緒運(yùn)行：CPU空閑，就緒態(tài)進(jìn)程被調(diào)度程序選中。運(yùn)行就緒：正在運(yùn)行的進(jìn)程用完了本次分配給它的CPU時(shí)間片。運(yùn)行阻塞：運(yùn)行態(tài)進(jìn)程因某種條件未滿足而放棄對(duì)CPU的占用，如等待讀文件。阻塞就緒：阻塞態(tài)進(jìn)程所等待的事件發(fā)生了，例如讀數(shù)據(jù)的操作完成。 下述狀態(tài)變遷：（A）21：可以。運(yùn)行進(jìn)程用完了本次分配給它的時(shí)間片，讓出CPU，從就緒隊(duì)列中選一個(gè)進(jìn)程投入運(yùn)行。（B）32：不可以。任何時(shí)候一個(gè)進(jìn)程只能處于一種狀態(tài)，它既然由運(yùn)行態(tài)變?yōu)樽枞麘B(tài)，就不能再變?yōu)榫途w態(tài)。（C）41：可以。某一阻塞態(tài)進(jìn)程等待的事件出現(xiàn)了，而且此時(shí)就緒隊(duì)列為空，該進(jìn)程進(jìn)入就緒隊(duì)列后馬上又被調(diào)度運(yùn)行。（4） PCB的作用是什么？它是怎樣描述進(jìn)程的動(dòng)態(tài)性質(zhì)的？進(jìn)程控制塊PCB是進(jìn)程組成中最關(guān)鍵的部分。每個(gè)進(jìn)程有唯一的進(jìn)程控制塊；操作系統(tǒng)根據(jù)PCB對(duì)進(jìn)程實(shí)施控制和管理，進(jìn)程的動(dòng)態(tài)、并發(fā)等特征是利用PCB表現(xiàn)出來(lái)的；PCB是進(jìn)程存在的唯一標(biāo)志。PCB中有表明進(jìn)程狀態(tài)的信息：該進(jìn)程的狀態(tài)是運(yùn)行態(tài)、就緒態(tài)還是阻塞態(tài)，利用狀態(tài)信息來(lái)描述進(jìn)程的動(dòng)態(tài)性質(zhì)。（5） PCB表的組織方式主要有哪幾種？分別簡(jiǎn)要說(shuō)明。PCB表的組織方式主要有：線性方式、鏈接方式和索引方式。 線性方式是把所有進(jìn)程的PCB都放在一個(gè)表中。 鏈接方式按照進(jìn)程的不同狀態(tài)把它們分別放在不同的隊(duì)列中。 索引方式是利用索引表記載相應(yīng)狀態(tài)進(jìn)程的PCB地址。（6） 進(jìn)程進(jìn)入臨界區(qū)的調(diào)度原則是什么？ 一個(gè)進(jìn)程進(jìn)入臨界區(qū)的調(diào)度原則是： 如果有若干進(jìn)程要求進(jìn)入空閑的臨界區(qū)，一次僅允許一個(gè)進(jìn)程進(jìn)入。 任何時(shí)候，處于臨界區(qū)內(nèi)的進(jìn)程不可多于一個(gè)。如已有進(jìn)程進(jìn)入自己的臨界區(qū)，則其它所有試圖進(jìn)入臨界區(qū)的進(jìn)程必須等待。 進(jìn)入臨界區(qū)的進(jìn)程要在有限時(shí)間內(nèi)退出，以便其它進(jìn)程能及時(shí)進(jìn)入自己的臨界區(qū)。 如果進(jìn)程不能進(jìn)入自己的臨界區(qū)，則應(yīng)讓出CPU，避免進(jìn)程出現(xiàn)“忙等”現(xiàn)象。（7） 簡(jiǎn)述信號(hào)量的定義和作用。P、V操作原語(yǔ)是如何定義的？信號(hào)量一般是由兩個(gè)成員組成的數(shù)據(jù)結(jié)構(gòu)，其中一個(gè)成員是整型變量，表示該信號(hào)量的值，它是與相應(yīng)資源的使用情況有關(guān)的；另一個(gè)是指向PCB的指針。當(dāng)多個(gè)進(jìn)程都等待同一信號(hào)量時(shí)，它們就排成一個(gè)隊(duì)列，由信號(hào)量的指針項(xiàng)指出該隊(duì)列的頭。信號(hào)量通?？梢院?jiǎn)單反映出相應(yīng)資源的使用情況，它與P、V操作原語(yǔ)一起使用可實(shí)現(xiàn)進(jìn)程的同步和互斥。 P、V操作原語(yǔ)的定義： P(S)：順序執(zhí)行下述兩個(gè)動(dòng)作：信號(hào)量的值減1，即S=S-1；如果S0，則該進(jìn)程繼續(xù)執(zhí)行；如果S0，則把該進(jìn)程的狀態(tài)置為阻塞態(tài)，把相應(yīng)的PCB連入該信號(hào)量隊(duì)列的末尾，并放棄處理機(jī)，進(jìn)行等待（直至其它進(jìn)程在S上執(zhí)行V操作，把它釋放出來(lái)為止）。 V(S)：順序執(zhí)行下述兩個(gè)動(dòng)作：S值加1，即S=S+1；如果S0，則該進(jìn)程繼續(xù)運(yùn)行； 如果S0，則釋放信號(hào)量隊(duì)列上的第一個(gè)PCB（即信號(hào)量指針項(xiàng)所指向的PCB）所對(duì)應(yīng)的進(jìn)程（把阻塞態(tài)改為就緒態(tài)），執(zhí)行V操作的進(jìn)程繼續(xù)運(yùn)行。（8） 計(jì)算機(jī)系統(tǒng)中產(chǎn)生死鎖的根本原因是什么？計(jì)算機(jī)系統(tǒng)中產(chǎn)生死鎖的根本原因是：資源有限且操作不當(dāng)。此外，進(jìn)程推進(jìn)順序不合適也可以引發(fā)的死鎖。（9） 發(fā)生死鎖的四個(gè)必要條件是什么？發(fā)生死鎖的四個(gè)必要條件是：互斥條件，不可搶占條件，占有且申請(qǐng)條件，循環(huán)等待條件。（10） 一般解決死鎖的方法有哪三種？一般解決死鎖的方法有：死鎖的預(yù)防、死鎖的避免、死鎖的檢測(cè)與恢復(fù)。3 思考題（1） 是否所有的共享資源都是臨界資源？為什么？不是所有的共享資源都是臨界資源。因?yàn)榕R界資源是一次僅允許一個(gè)進(jìn)程使用的資源，而系統(tǒng)中有很多資源可以讓多個(gè)進(jìn)程同時(shí)使用，例如硬盤、正文段等。（2） 系統(tǒng)中只有一臺(tái)打印機(jī)，有三個(gè)用戶的程序在執(zhí)行過(guò)程中都要使用打印機(jī)輸出計(jì)算結(jié)果。設(shè)每個(gè)用戶程序?qū)?yīng)一個(gè)進(jìn)程。問(wèn)：這三個(gè)進(jìn)程間有什么樣的制約關(guān)系？試用P、V操作寫出這些進(jìn)程使用打印機(jī)的算法。因?yàn)榇蛴C(jī)是一種臨界資源，所以這三個(gè)進(jìn)程只能互斥使用這臺(tái)打印機(jī)，即一個(gè)用戶的計(jì)算結(jié)果打印完之后，另一個(gè)用戶再打印。 設(shè)三個(gè)進(jìn)程分別為A、B和C。 設(shè)一個(gè)互斥信號(hào)量mutex，其初值為1。 進(jìn)程A 進(jìn)程B 進(jìn)程C P(mutex) P(mutex) P(mutex) 使用打印機(jī) 使用打印機(jī) 使用打印機(jī) V(mutex) V(mutex) V(mutex) （3） 判斷下列同步問(wèn)題的算法是否正確？若有錯(cuò)，請(qǐng)指出錯(cuò)誤原因并予以改正。 設(shè)A，B兩個(gè)進(jìn)程共用一個(gè)緩沖區(qū)Q，A向Q寫入信息，B從Q讀出信息，算法框圖如圖3-24所示。 設(shè)A，B為兩個(gè)并發(fā)進(jìn)程，它們共享一個(gè)臨界資源。其運(yùn)行臨界區(qū)的算法框圖如圖3-25所示。 圖3-24 進(jìn)程A, B的算法框圖 圖3-25 兩個(gè)并發(fā)進(jìn)程臨界區(qū)的算法框圖 這個(gè)算法不對(duì)。因?yàn)锳、B兩個(gè)進(jìn)程共用一個(gè)緩沖區(qū)Q，如果A先運(yùn)行，且信息數(shù)量足夠多，那么緩沖區(qū)Q中的信息就會(huì)發(fā)生后面的沖掉前面的，造成信息丟失，B就不能從Q中讀出完整的信息。改正：A、B兩進(jìn)程要同步使用緩沖區(qū)Q。為此，設(shè)立兩個(gè)信號(hào)量：empty表示緩沖區(qū)Q為空，初值為1；full表示緩沖區(qū)Q為滿，初值為0。 算法框圖如圖1所示。 這個(gè)算法不對(duì)。因?yàn)锳、B兩個(gè)進(jìn)程是并發(fā)的，它們共享一個(gè)臨界資源，所以二者應(yīng)互斥地使用該臨界資源，在進(jìn)入臨界區(qū)時(shí)不存在先A后B的時(shí)序關(guān)系，而是哪個(gè)進(jìn)程先到一步就先進(jìn)入自己的臨界區(qū)。改正：A、B兩個(gè)進(jìn)程應(yīng)互斥地進(jìn)入臨界區(qū)。為此，設(shè)立一個(gè)信號(hào)量：互斥信號(hào)量mutex，其初值為1。 算法框圖如圖2所示。 A進(jìn)程 B進(jìn)程 A進(jìn)程 B進(jìn)程 P(empty) P(full) P(mutex) P(mutex) 向Q寫入信息 從Q中讀出信息 臨界區(qū)代碼CSa 臨界區(qū)代碼CSb V(full) V(empty) V(mutex) V(mutex) 圖1 圖 2 （4） 設(shè)有一臺(tái)計(jì)算機(jī)，有兩條I/O通道，分別接一臺(tái)卡片輸入機(jī)和一臺(tái)打印機(jī)?？ㄆ瑱C(jī)把一疊卡片逐一輸入到緩沖區(qū)B1中，加工處理后再搬到緩沖區(qū)B2中，并在打印機(jī)上打印結(jié)果。問(wèn)： 系統(tǒng)要設(shè)幾個(gè)進(jìn)程來(lái)完成這個(gè)任務(wù)？各自的工作是什么？ 這些進(jìn)程間有什么樣的相互制約關(guān)系？ 用P、V操作寫出這些進(jìn)程的同步算法。系統(tǒng)可設(shè)三個(gè)進(jìn)程來(lái)完成這個(gè)任務(wù)：R進(jìn)程負(fù)責(zé)從卡片輸入機(jī)上讀入卡片信息，輸入到緩沖區(qū)B1中；C進(jìn)程負(fù)責(zé)從緩沖區(qū)B1中取出信息，進(jìn)行加工處理，之后將結(jié)果送到緩沖區(qū)B2中；P進(jìn)程負(fù)責(zé)從緩沖區(qū)B2中取出信息，并在打印機(jī)上印出。R進(jìn)程受C進(jìn)程影響，B1放滿信息后R進(jìn)程要等待等C進(jìn)程將其中信息全部取走，才能繼續(xù)讀入信息；C進(jìn)程受R進(jìn)程和P進(jìn)程的約束：B1中信息放滿后C進(jìn)程才可從中取出它們，且B2被取空后，C進(jìn)程才可將加工結(jié)果送入其中；P進(jìn)程受C進(jìn)程的約束：B2中信息放滿后P進(jìn)程才可從中取出它們,進(jìn)行打印。信號(hào)量含義及初值：B1full 緩沖區(qū)B1滿，初值為0；B1empty緩沖區(qū)B1空，初值為0；B2full 緩沖區(qū)B2滿，初值為0；B2empty緩沖區(qū)B2空，初值為0； R進(jìn)程 C進(jìn)程 P進(jìn)程 輸入信息寫入緩沖區(qū)B1 P(B1full) P(B2full) V(B1full) 從B1中取出信息 從B2中取出信息進(jìn)行打印 P(B1empty) 加工信息 V(B2empty) 結(jié)果送入B2 V(B1empty) V(B2full) P(B2empty) （5） 設(shè)有無(wú)窮多個(gè)信息，輸入進(jìn)程把信息逐個(gè)寫入緩沖區(qū)，輸出進(jìn)程逐個(gè)從緩沖區(qū)中取出信息。針對(duì)下述兩種情況： 緩沖區(qū)是環(huán)形的，最多可容納n個(gè)信息； 緩沖區(qū)是無(wú)窮大的。試分別回答下列問(wèn)題： 輸入、輸出兩組進(jìn)程讀/寫緩沖區(qū)需要什么條件？ 用P、V操作寫出輸入、輸出兩組進(jìn)程的同步算法，并給出信號(hào)量含義及初值。 針對(duì)容量為n的環(huán)形緩沖區(qū)，輸入、輸出兩組進(jìn)程讀/寫緩沖區(qū)需要的條件為： 輸入進(jìn)程和輸出進(jìn)程需同步執(zhí)行，即輸入進(jìn)程寫緩沖區(qū)后，輸出進(jìn)程才可以讀； 由于緩沖區(qū)容量有限，因此任一時(shí)刻所有輸入進(jìn)程存放信息的單元數(shù)不能超過(guò)緩沖區(qū)的總?cè)萘浚╪）； 同理，所有輸出進(jìn)程取出信息的總量不能超過(guò)所有輸入進(jìn)程當(dāng)前寫入信息的總數(shù)。設(shè)緩沖區(qū)的編號(hào)為0n-1，in和out分別是輸入進(jìn)程和輸出進(jìn)程使用的指針，指向下面可用的緩沖區(qū)，初值都是0。為使兩類進(jìn)程實(shí)行同步操作，應(yīng)設(shè)置三個(gè)信號(hào)量：兩個(gè)計(jì)數(shù)信號(hào)量full和empty，一個(gè)互斥信號(hào)量mutex。full：表示放有信息的緩沖區(qū)數(shù)，其初值為0。empty：表示可供使用的緩沖區(qū)數(shù)，其初值為n。mutex：互斥信號(hào)量，初值為1，表示各進(jìn)程互斥進(jìn)入臨界區(qū)，保證任何時(shí)候只有一個(gè)進(jìn)程使用緩沖區(qū)。下面是解決這個(gè)問(wèn)題的算法描述。輸入進(jìn)程Input： while (TRUE) P(empty); P(mutex); 信息送往buffer(in); in=(in+1)mod N; /*以N為模*/ V(mutex); V(full); 輸出進(jìn)程Output：while (TRUE) P(full); P(mutex);從buffer(out)中取出信息; out=(out+1)mod N; /*以N為模*/V(mutex);V(empty); 當(dāng)緩沖區(qū)是無(wú)窮大時(shí)，輸入進(jìn)程存放信息的單元數(shù)不再受緩沖區(qū)總?cè)萘康南拗疲虼?，可以不設(shè)信號(hào)量em