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

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