1、精選優質文檔-傾情為你奉上操作系統總復習及相關習題第一章 引論名詞解釋1操作系統操作系統是管理和控制計算機系統內各種硬件和軟件資源，有效地組織多道程序運行的系統軟件（或程序集合），是用戶與計算機之間的接口。2管態當執行操作系統程序時，處理機所處的狀態3目態當執行普通用戶程序時，處理機所處的狀態。4多道程序設計在這種設計技術下，內存中能同時存放多道程序，在管理程序的控制下交替的執行。這些作業共享CPU和系統中的其他資源。5并發是指兩個或多個活動在同一給定的時間間隔中進行。它是宏觀上的概念。6并行是指兩個或多個活動在同一時刻同時執行的情況。7吞吐量在一段給定的時間內，計算機所能完成的總工作量。8分

2、時就是對時間的共享。在分時系統中，分時主要是指若干并發程序對CPU時間的共享。9實時表示“及時”或“既時”。10系統調用是用戶在程序中能以“函數調用”形式調用的、由操作系統提供的子功能的集合。每一個子功能稱作一條系統調用命令。它是操作系統對外的接口，是用戶級程序取得操作系統服務的唯一途徑。11特權指令指指令系統中這樣一些指令，如啟動設備指令、設置時鐘指令、中斷屏蔽指令和清內存指令，這些指令只能由操作系統使用。12命令解釋程序其主要功能是接收用戶輸入的命令，然后予以解釋并且執行。13脫機I/O是指輸入/輸出工作不受主機直接控制，而由衛星機專門負責完成I/O，主機專門完成快速計算任務，從而二者可以

3、并行操作。14聯機I/O是指作業的輸入、調入內存及結果輸出都在cpu直接控制下進行。15資源共享是指計算機系統中的資源被多個進程所功用。例如，多個進程同時占用內存，從而對內存共享；它們并發執行時對cpu進行共享；各個進程在執行過程中提出對文件的讀寫請求，從而對磁盤進行共享等等。簡答題1什么是操作系統？它的主要功能是什么？答：操作系統是控制和管理計算機系統內各種硬件和軟件資源，有效地組織多道程序運行的系統軟件（或程序集合），是用戶與計算機之間的接口。操作系統的主要功能有5個方面，即存儲管理、處理機管理、設備管理、文件管理和用戶接口。 2推動操作系統形成和發展的主要動力是什么？答：推動操作系統發展

4、的因素很多，主要可歸結為兩大方面：硬件技術更新和應用需求擴大伴隨計算機器件的更新換代和計算機體系結構的發展，促使操作系統的性能和結構有了顯著發展。 應用需求促進了計算機技術的發展，也促進了操作系統的不斷更新升級。3操作系統的基本特征是什么？答：操作系統的基本特征是并發、共享和不確定。并發性是指兩個或多個活動在同一給定的時間間隔中進行；共享是指計算機系統中的資源被多個進程所共用；不確定性是指系統中各種事件發生順序的不可預測性。4多道程序和多重處理有何區別？答：多道程序是作業之間自動調度執行、共享系統資源，并不是真正的同時執行多個作業；而多重處理系統配置多個cpu，能真正同時執行多道程序。要有效使

5、用多重處理，必須采用多道程序設計技術，而多道程序設計原則上不一定要求多重處理系統的支持。5試說明多道程序設計和多任務系統之間的關系答：多道程序設計是利用外設與cpu能夠并行處理的特性，在主存同時存放多個程序，使之在系統中交叉地使用cpu，從而提高系統資源的利用率。而多任務系統主要指多進程交叉使用cpu。多道程序隱含了多任務處理，但多任務系統中不一定有多道程序。因為一個程序也可以采用多任務處理機制。6不同類型的操作系統提供不同的功能。假定有如下的應用環境，請你為它們選擇適合的操作系統。（1）飛機的導航，（2）辦公自動化系統，（3）航空訂票系統，（4）復雜的科學計算，（5）圖書檢索系統答：（1）飛

6、機的導航系統，應采用硬實時操作系統 （2）辦公自動化系統，應采用分時操作系統 （3）航空訂票系統，應采用軟實時操作系統 （4）復雜的科學計算，應采用批處理系統 （5）圖書檢索系統，應采用軟實時操作系統 7什么是批處理系統，它有什么特征？答：批處理系統：操作員把用戶提交的作業分類，把一批作業編成一個作業執行序列，由專門編制的監督程序自動依次處理。其主要特征是：用戶脫機使用計算機、成批處理、多道程序運行。8什么是分時系統，它有什么特征？答：分時系統：把處理機的運行時間分成很短的時間片，按時間片輪轉的方式，把處理機分配給各進程使用。其主要特征是：交互性、多用戶同時性、獨立性。9什么是實時系統？它有什

7、么特征？答：實時系統：在被控對象允許時間范圍內做出響應 。其主要特征是：對實時信息分析處理速度要比進入系統快、要求安全可靠、資源利用率低。10什么是處理機的核心態和用戶態？為什么要設置這兩種不同的狀態？答：當執行操作系統程序時，處理機處于核心態。它有較高的特權，可以執行所有的指令，包括一般用戶程序中不能使用的特權指令，從而能對所有寄存器和內存進行訪問，啟動i/o操作等。 用戶程序是在用戶態下執行，它的權限較低，只能執行指令集中非特權指令。（2分）設置這兩種不同狀態的目的是為了保護操作系統程序（特別是其內核部分），防止受到用戶程序的損害。 11系統調用與過程調用在功能及實現上有什么相同點和不同點

8、？答：相同點：兩者都由程序代碼構成，可直接用高級程序設計語言（如C,C+和Perl語言）來編制；使用方式相同以函數調用的形式出現，調用時傳送參數。 不同點：代碼層次不同，過程調用不屬于操作系統的一部分，而系統調用是操作系統的一部分。運行狀態不同。過程調用只能在用戶態下運行，不能進入核心態，而系統調用是在核心態下運行的。進入方式不同。過程調用在用戶程序中調用，并直接在用戶空間內執行；而系統調用可以在用戶程序中調用，但是在用戶程序中執行到系統調用時，會產生異常事件。實現處理機狀態從用戶態到核心態的轉變，從而進入操作系統核心空間去執行系統調用的代碼。 12試說明特權指令和系統調用之間的區別與聯系。答

9、：特權指令是一類只能在核心態下執行的機器指令。而系統調用不是機器指令，它往往以函數調用的形式出現，實現操作系統提供的子功能，它是操作系統與用戶的編程接口 。在用戶程序中可以使用系統調用來獲得操作系統服務，在系統調用代碼中可以使用特權指令第二章 進程和線程名詞解釋1順序性是指順序程序所規定的每個動作都在上個動作結束后才開始的特性。2封閉性是指只有程序本身的動作才能改變程序的運行環境。3可再現性是指程序的執行結果與程序運行的速度無關。4進程程序在并發環境中的執行過程。5互斥在邏輯上本來完全獨立的進程，由于競爭同一個資源而產生的相互制約的關系。6同步是指進程間共同完成一項任務時直接發生相互作用的關系

10、。也就是說，這些具有伙伴關系的進程在執行次序上必須遵循確定的規律。7臨界資源一次僅允許一個進程使用的資源。8臨界區在每個進程中訪問臨界資源的那段程序。9線程線程是進程中實施調度和分派的基本單位。10管程管程是一種高級同步機制，一個管程定義一個數據結構和能為并發進程在其上執行的一組操作，這組操作能使進程同步和改變管程中的數據。11進程控制塊進程控制塊是進程存在的唯一標識，它保存了系統管理和控制進程所必須的信息，是進程動態特性的集中表現。12原語指操作系統中實現一些具有特定功能的程序段，這些程序段的執行過程是不可分割的，即其執行過程不允許被中斷。13就緒態進程已經獲得了除cpu之外的全部資源，等待

11、系統分配cpu，一旦獲得cpu，進程就可以變為運行態。14運行態正在cpu上執行的進程所處的狀態。在單cpu系統中，任何時候最多只能有一個進程處于運行狀態。15阻塞態又稱等待態，指正在運行的進程因等待某個條件發生而不能運行時所處的狀態。處于阻塞態的進程在邏輯上是不能運行的，即使cpu空閑，它也不能占用cpu。16進程通信是指進程間的信息交換。17同步機制同步機構是負責處理進程之間制約關系的機制，即操作系統中負責解決進程之間協調工作的同步關系（直接制約關系），以及共享臨界資源的互斥關系（間接制約關系）的執行機構。簡答題1在操作系統中為什么要引入進程概念？答: 由于多道程序并發執行時共享系統資源，

12、共同決定這些資源的狀態，因此系統中各程序在執行過程中就出現了相互制約的新關系，程序的執行出現“走走停停”的新狀態。用程序這個靜態的概念已不能如實反映程序并發執行過程中的這些特征。為此，人們引入了“進程（Process）”這一概念來描述程序動態執行過程的性質。 進程和程序是兩個完全不同的概念。然而，進程與程序之間存在密切關系，進程的功能是通過程序的運行得以實現的，進程活動的主體是程序。進程不能脫離開具體程序而獨立存在。 2有人說，一個進程是由偽處理機執行的一個程序，這話對嗎？為什么？答：對。 因為偽處理機的概念只有在執行時才存在，它表示多個進程在單處理機上并發執行的一個調度單位。因此，盡管進程是

13、動態概念，是程序的執行過程，但是，在多個進程并行執行時，仍然只有一個進程占據處理機執行，而其他并發進程則處于就緒或等待狀態。這些并發進程就相當于由偽處理機執行的程序。 3試比較進程和程序的區別答：（1）進程是一個動態的概念，而程序是一個靜態的概念，程序是指令的有序集合，無執行含義，進程則強調執行的過程。 （2）進程具有并行特征（獨立性、異步性），程序則沒有。 （3）不同的進程可以包含同一個程序，同一程序在執行中也可以產生多個進程。4進程的基本狀態有哪些？試描繪進程狀態轉換圖。答：進程至少有三種基本狀態：運行狀態、就緒狀態和阻塞狀態（或等待狀態） 。進程狀態轉換如下圖：運行態進程調度所需要的資源

14、未被滿足（如等待 I/O）時間片到所需資源得到滿足（如I/O完成）運行態運行態5并發進程間的制約有哪兩種？引起制約的原因是什么？答：并發進程所受的制約有兩種：直接制約和間接制約。 直接制約是由并發進程相互共享對方的私有資源所引起的；間接制約是由競爭共有資源而引起的。 6什么是進程間的互斥？什么是進程間同步？答：進程間的互斥是指：一組并發進程中的一個或多個程序段，因共享某一共有資源而導致它們必須以一個不許交叉執行的單位執行，即不允許兩個以上的共享該資源的并發進程同時進入臨界區。 進程間的同步是指：異步環境下的一組并發進程因直接制約相互發送消息而進行相互合作、相互等待，是各進程按一定的速度執行的過

15、程。7什么是臨界區和臨界資源？進程進入臨界區的調度原則是什么？答：臨界資源一次僅允許一個進程使用的資源臨界區在每個進程中訪問臨界資源的那段程序一個進程進入臨界區的調度原則是： 如果有若干進程要求進入空閑的臨界區，一次僅允許一個進程進入 任何時候，處于臨界區內的進程不可多于一個。如已有進程進入自己的臨界區，則其他所有試圖進入臨界區的進程必須等待 進入臨界區的進程要在有限的時間內退出，以便讓其他進程能及時進入自己的臨界區 如果進程不能進入自己的臨界區，則應讓出cpu，避免進程出現“忙等”現象.8簡述信號量的定義和作用。P，V操作原語是如何定義的？答：信號量一般是由兩個成員組成的數據結構，其中一個成

16、員是整型變量，表示該信號量的值，它與相應資源的使用情況有關；另一個是指向PCB的指針。當多個進程都等待同一信號量時，它們就排成一個隊列，由信號量的指針項指出該隊列的隊首。（2分）信號量通常可以簡單反映出相應資源的使用情況，它與P、V操作原語一起使用可實現進程的同步和互斥。（1分）P,V操作原語有如下定義。P(S)順序執行下述兩個動作（1分）：信號量的值減1，即S=S-1;如果S>=0,則該進程繼續執行。如果S<0,則把該進程的狀態置為阻塞態，把相應的PCB連入該信號量隊列的末尾，并放棄處理機，進行等待（直到其他進程在S上執行V操作，把它釋放出來為止）。V(S)順序執行下述兩個動作（

17、1分）：S值加1，即S=S+1;如果S>0,則該進程繼續運行；如果S<=0,則釋放信號量隊列上的第一個PCB所對應的進程（把阻塞態改為就緒態）,執行V操作的進程繼續運行。9什么是線程？它與進程有什么關系？答：線程是進程中實施調度和分派的基本單位。 線程和進程之間有如下關系： 一個進程可以有多個線程，但至少有一個線程；而一個線程只能在一個進程的地址空間內活動。 資源分配給進程，同一進程的所有線程共享該進程的所有資源。 處理機分給線程，即真正在處理機上運行的是線程。 線程在執行過程中，需要協作同步。不同進程的線程間要利用消息通信的辦法實現同步。10什么是管程？它由哪幾部分組成？有什么基

18、本特性?答：一個管程定義了一個數據結構和能為并發進程在其上執行的一組操作，這組操作能同步進程和改變管程中的數據。 一個管程由四個部分組成，它們是管程名稱、局部與管程的共享數據的說明、對數據進行操作的一組過程和對該共享數據賦初值的語句。 管程具有以下特性： 管程內部的局部數據變量只能被管程內定義的過程所訪問，不能被管程外面聲明的過程直接訪問 進程要想進入管程，必須調用管程內的某個過程 一次只能有一個進程在管程內執行，而其余調用該管程的進程都被掛起，等待該管程成為可用的。就是說，管程自身能有效地實現互斥。綜合題1如下圖所示的工作模型中，有三個進程p0,p1,p2和三個緩沖區B0,B1,B2. 進程

19、之間借助于相鄰緩沖區進行消息傳遞：每個進程每次從緩沖區中取一條消息，經加工處理后送入另一個緩沖區中，三個緩沖區分別可存放3,2,2個消息。初始時，僅緩沖區0有一個消息。試用P、V操作寫出三個進程之間的同步及互斥流程。答：這是一個生產者/消費者問題，而且每個進程既是生產者，也是消費者。(2)為此，應設置6個信號量：B0S1,B0S2,B1S1,B1S2,B2S1,B2S2,分別代表B0,B1,B2中是否有空緩沖和有數據。B0S1,B0S2,B1S1,B1S2,B2S2:semaphore;B0S1=2;B0S2=1;B1S1=2;B1S2=0;B2S1=2;B2S2=0; (2)Cobegin

20、(6=2*3)P0P1P2beginbeginbeginP(B0S2)P(B1S2)P(B2S2)從B0取一個數據從B1取一個數據從B2取一個數據V(B0S2)V(B1S1)V(B2S1)加工加工加工P(B1S1)P(B2S1)P(B0S1)將加工結果送B1將加工結果送B2將加工結果送B0V(B1S2)V(B2S2)V(B0S2)endendendcoend這道題也可以增加互斥信號量，以便P0與P1之間互斥使用B0緩沖區，P1與P2之間互斥使用B1緩沖區，P2與P0之間互斥使用B0緩沖區。這里主要描述它們之間的同步關系。若考慮互斥共享緩沖區，請自己加上。2設用三個隊列管理緩沖區池的使用情況，分

21、別為空白緩沖隊列em，輸入緩沖隊列in，以及輸出緩沖隊列out。過程add_buf(type,numb)和take_buf(type,numb)分別用來把緩沖區numb插入type隊列和從type隊列中取出緩沖區numb。試描述進程從任一緩沖隊列中得到一個緩沖區的過程get_buf(type,numb)和釋放一個緩沖區numb進入緩沖隊列的過程put_buf(type,numb)。答：假定用信號量s代表任一隊列的可用緩沖區個數。假定三個隊列的初值分別為n1,n2,n3。對任一隊列的操作必須互斥。因此再引入一個互斥使用任一隊列的信號量mutex，其初值為1。這里type代表隊列的類型，它的取值為

22、輸入、輸出和空白。(4)當有進程希望從任一隊列取一個緩沖區時，過程get_buf(type,numb)的動作如下：get_buf(type,numb) (3)beginp(s)p(mutex)numb=take_buf(type,numb)v(mutex)end當有進程希望向任一隊列送一個緩沖區時，過程put_buf(type,numb)的動作如下：put_buf(type,numb) (3)beginp(mutex)add_buf(type,numb)v(mutex)v(s)end. 3設有一個售票廳，可容納100人購票。如果廳內不足100人則允許進入，進入后購票，購票后退出。如果廳內已有1

23、00人，則在廳外等候。試問：1） 購票者之間是同步還是互斥？用P、V操作表達購票者的工作過程。解：1）購票者之間是互斥關系。(2)2） 一個售票廳可容納100人購票，說明最多允許100個購票者共享售票廳；可引入一個信號量empty，其初值為100。由于購票者必須互斥地進行購票，故應再設一個mutex，其初值為1。(4)用P、V操作表達購票者的工作過程如下：(4)empty,mutex:semaphore;empty:=100; mutex:=1;beginp(empty)p(mutex)進入廳內購票,購票后退出v(empty)v(mutex)end. 4某招待所有100個床位，住宿者入住要先登

24、記（在登記表上填寫姓名和床位號）離去時要注銷登記（在登記表上刪去姓名和床位號）請給出住宿登記及注銷過程的算法描述答：某招待所有100個床位，為了正確管理，引入一個信號量empty代表空床位數，初值為100；住宿者入住要先登記（在登記表上填寫姓名和床位號），顯然，登記表是一個臨界資源，必須互斥訪問，引入一個mutex，其初值為1。(4)住宿登記及注銷過程的算法描述如下：住宿登記：(3)beginp(empty) /檢查有無床位p(mutex) /申請登記 找出一個空床位將名字登入表中v(mutex)end注銷過程：(3)beginp(mutex) /申請退房找出自己的登記項，并刪除該項的登記v(

25、mutex)v(empty)end. 5有一個閱覽室，共有100個座位。為了很好地利用它，讀者進入時必須先在登記表上進行登記。該表表目設有座位號和讀者姓名；離開時再將其登記項擦除。試問：為描述讀者的動作，應編寫幾個程序，應設幾個進程、它們之間的關系怎樣？并請用P、V操作描述進程之間的同步算法。解：為了描述閱覽室，用一個登記表來記錄其使用情況。表中共有100項。每當有讀者進入閱覽室時，為了正確地登記，各讀者應互斥使用(1)。為此設兩個信號量：mutex為互斥信號量，用來制約各讀者互斥地進行登記，其初值為1；empty為同步信號量，用來制約各讀者能同時進入閱覽室的數量，其初值為100 (2)。下面

26、用兩個過程描述對表格應執行的動作：登記過程：(2)擦除過程：(2)beginbeginP(empty)P(mutex)P(mutex)找到自己的登記項擦除 找到一個登記項登記V(mutex)V(mutex)V(empty)endend為了正確地描述讀者的動作，可以將讀者看成進程。若干讀者希望進入閱覽室時，調用登記過程，退出閱覽室時，調用擦除過程(1)。可見，一個程序可對應多個讀者。可設的進程數由讀者數決定，其動作如下：(2)begin調用登記過程進入閱覽室閱讀準備退出調用擦除過程end. 6一條河上架設了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而不能向后退。過

27、河時，只要對岸無人過，就可以過；但不允許河對岸的兩個人同時過，以防止出現死鎖。請給出兩個方向的人順利過河的同步算法。解：假設一座橋由N個橋墩，也即最多允許有N個人同向過河，用一個計數器R記錄同時過河的人數(2)。用S1信號量保護計數器，其初值為1，R的初值為0；互斥使用橋的信號量用S表示，其初值為1。(2)同步算法描述如下：procedure goriver()beginL:P(S1);/為同時過河,申請對計數器計數 If R>N begin V(S1); goto L; end /同方向過河的人站滿橋墩時,重新申請計數 R=R+1; If R=1 P(S);/申請過河V(S1); /釋

28、放計數器的使用權 (3)占有一個橋墩,并順序過河到對岸;P(S1); R=R-1; If R=0 V(S);/如果已經無同向的人過河,釋放占用權V(S1); (3)end. 7在一個飛機訂票系統中，多個用戶共享一個數據庫。各用戶可以同時查詢信息，若有一個用戶要訂票，須更新數據庫時，其余所有用戶都不可以訪問數據庫。請用P,V操作設計一個同步算法，實現用戶查詢與訂票功能。要求：當一個用戶訂票而需要更新數據庫時，不能因不斷有查詢者到來而使其長時間等待。利用信號量機制保證其正常執行。解：這是典型的讀者寫者問題，查詢信息的用戶是讀者，訂票用戶是寫者，并且要求寫者優先。(2)變量說明：(2)計數變量rc正

29、在運行的查詢者進程數目，初值為0.信號量Sw控制訂票者進程的活動，初值為1.Src互斥使用rc變量，初值為1.S當訂票者到達時封鎖后續的讀進程，初值為1.讀者進程 P(S)P(Src)rc=rc+1if (rc=1) P(Sw)V(Src)V(S) (2)查詢庫當中的信息P(Src)rc=rc-1;if (rc=0) V(Sw)V(Src) (2) 寫者進程 (2)P(S)P(Sw)更新數據庫內容V(Sw)V(S)8某車站售票廳，任何時刻最多可容納20名購票者進入，當售票廳中少于20名購票者時，則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答下列問題：(1)用PV

30、操作管理這些并發進程時，應怎樣定義信號量，寫出信號量的初值以及信號量各種取值的含義。(2)根據所定義的信號量，把應執行的PV操作填入下述空格中，以保證進程能夠正確地并發執行。COBEGINPROCESSPI(I=1，2，) begin進入售票廳； 購票； 退出； endCOEND(3)若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值)。答：(1)定義一信號量S，初始值為20。(1)意義：(3=1*3)S>0S的值表示可繼續進入售票廳的人數S=0表示售票廳中已有20名顧客(購票者)S<0|S|的值為等待進入售票廳的人數(2)上空格為P(S) (2) ；下空格為V(S)

31、(2)(3)S的最大值為20 (1 )；S的最小值為20n(1 )9在公共汽車上，司機和售票員各行其職，司機負責開車和到站停車；售票員負責售票和開門關門，當售票員關好車門后，駕駛員才能開車行使。試用P/V操作實現司機與售票員間的同步。解答：semaphore mutex1=0,mutex2=0; (2) main() cobegin driver() busman()coend (2)driver() while(true) p(mutex1) 啟動公共汽車 正常開車 到站停車 v(mutex2) (3)busman() while(true) 關車門 v(mutex1) 售票 p(mutex

32、2) 開車門 上下乘客 (3)10并發問題：設有兩個優先級相同的進程p1, p2如下。令信號s1, s2的初值為0，已知z=2，試問p1, p2并發運行結束后x=? y=? z=? 進程p1 進程p2 y := 1 x := 1 y := y+2 x := x+1 v(s1) p(s1) z := y+1 x := x+y p(s2) v(s2) y := z+y z := x+z 解答：（分析過程略 2）從結果來看，兩個進程無論誰先誰后，結果都是一樣的。(2) x = 5; y = 12; z = 9 (6)11 M8M7M6M5M4M3M2試用信號量機制來描述下述前趨圖M1 解答：首先定義

33、信號量S12,S13,S14,S26,S36,S47,S57,S38,S78的初值都為0，分別表示相對應的進程是否完成：(2)COBEGIN (8=1*8)Process M1:begin V(S12) V(S13) V(S14) endProcess M2:begin P(S12) V(26) endProcess M3:begin P(S13) V(S36) V(S38) endProcess M4:begin P(S14) V(S47) endProcess M5:begin V(S57) endProcess M6:begin P(S26) P(S36) endProcess M7:b

34、egin P(S47) P(S57) P(S78) endProcess M8:begin P(S38) P(S78) end COEND12 M6M4M3M5M2試用信號量機制來描述下述前趨圖M1 解答：首先定義信號量S12,S13,S24,S25,S56,S46,S36的初值都為0，分別表示相對應的進程是否完成(2)：COBEGIN (6=1*6)Process M1:begin V(S12) V(S13) endProcess M2:begin P(S12) V(24) V(25) endProcess M3:begin P(S13) V(S36) endProcess M4:begin

35、 P(S14) V(S46) endProcess M5:begin P(S25) V(S56) endProcess M6:begin P(S36)P(S46) P(S56) end COEND13設系統有三個并發進程R,C,P，共享一個能存放n個數據的環形緩沖區buf。進程R負責從輸入設備上讀數據，每讀一個后把它存放在緩沖區buf的一個單元中；進程C負責從緩沖區讀數據并進行處理，之后將處理結果再送入緩沖區的一個單元中；進程P負責從緩沖區讀進程C處理的結果并打印。請用P、V操作為三進程的正確執行寫出同步算法。解答：解決同步問題需設一個互斥信號量mux，用于控制三個進程互斥使用緩沖區，初值為1

36、；再設三個同步信號量，用于控制對緩沖區的空閑數量和不同數據個數的記錄。S0表示緩沖區空閑個數，初值為n；S1表示緩沖區中輸入數據的個數，初值為0；S2表示緩沖區中輸出數據的個數，初值為0。(4)算法描述如下：(6=2*3) 進程R 進程C 進程P L1: L2: L3:P(S0) P(S1) P(S2)P(mux) P(mux) P(mux)讀一個數據 從緩沖區中取一個 從緩沖區中讀 送緩沖區 數據處理后放回去 輸出數據V(mux) V(mux) V(mux)V(S1) V(S2) V(S0) 打印gotoL1: gotoL2: gotoL3:第三章 死鎖名詞解釋1死鎖是指在一個進程集合中的每

37、個進程都在等待僅由該集合中的另一個進程才能引發的事件而無限期地僵持下去的局面。2饑餓在系統中，每個資源占有者都在有限時間內釋放它所占有的資源，但資源中存在某些申請者由于某種原因卻永遠得不到資源的一種錯誤現象。3死鎖防止要求進程申請資源時遵循某種協議，從而打破產生死鎖的四個必要條件中的一個或幾個，保證系統不會進入死鎖狀態。4死鎖避免對進程所發出的每一個申請資源命令加以動態地檢查，并根據檢查結果決定是否進行資源分配。就是說，在資源分配過程中若預測有發生死鎖的可能性，則加以避免。這種方法的關鍵是確定資源分配的安全性。5安全序列針對當前分配狀態來說，系統至少能夠按照某種次序為每個進程分配資源（直至最大

38、需求），并且使他們依次成功地運行完畢，這種進程序列p1,p2,pn就是安全序列。簡答題1計算機系統中產生死鎖的根本原因是什么?死鎖發生的四個基本條件是什么？答: 計算機系統中產生死鎖的根本原因是：資源有限且操作不當 。死鎖發生的四個基本條件有互斥條件、請求保持條件（占有且等待條件）、非剝奪條件（不可搶占條件）和環路條件（循環等待條件） 。2簡述發生死鎖的四個必要條件?答： 四個必要條件是：互斥條件、占有且等待條件（請求保持條件）、不可搶占條件（非剝奪條件）和循環等待條件（環路條件）。 互斥條件某個資源在一段時間內只能由一個進程占有，不能同時被兩個及其以上的進程占有。 占有且等待條件進程至少已經

39、占有一個資源，但又申請新的資源。 不可搶占條件一個進程所占有的資源再用完之前，其他進程不能強行奪走資源，只能由該進程用完之后主動釋放。 循環等待條件存在一個進程等待序列P1,P2,Pn，其中，P1等待P2所占有的某個資源，P2等待P3所占有的某個資源，而Pn等待P1所占有的某個資源，從而形成一個進程循環等待。 3什么是死鎖？解決死鎖的方法一般有那幾種?答: 死鎖是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能引發的事件而無限期地僵持下去的局面。 解決死鎖問題的一般方法為：死鎖的預防、死鎖的避免、死鎖的檢測和恢復。 4死鎖預防的基本思想是什么?死鎖避免的基本思想是什么?答:死鎖

40、預防的基本思想是:要求進程申請資源是遵循某種協議,從而打破產生思索的四個必要條件中的一個或幾個,保證系統不會進入死鎖狀態. 死鎖避免的基本思想是:對進程所發出的每一個申請資源命令加以動態地檢查,并根據檢查結果決定是否進行資源分配.就是說,在資源分配過程中若預測有發生死鎖的可能性,則加以避免.這種方法的關鍵是確定資源分配的安全性. 5什么是死鎖的安全序列?何謂系統是安全的？答：進程的安全序列P1,P2,PN是這樣組成的：若對于每個進程Pi（1<=I<=n），它需要的附加資源可以被系統中當前可用資源加上所有進程Pj（j<i）當前占有資源之和所滿足，則 P1,P2,PN 為一個安全

41、序列。 “系統是安全的”是指系統中的所有進程能夠按照某種次序分配資源，并且依次運行完畢。即系統中的進程處于安全序列中。 6資源按序分配法為什么能夠預防死鎖？證明：采用反證法來證明。 若存在循環等待，設在環路上的一組進程為P0,P1,P2,Pn，這里Pi等待進程Pi+1占有資源Ri（下角標取模運算，從而，Pn等待p0占有的資源）。由于Pi+1占有資源Ri,又申請資源Ri+1,從而一定存在F(i)<F(i+1), 該式對所有的i都成立。于是就有： F(R0)<F(R1)<<F(Rn)<F(R0) 由傳遞性得到： F(R0)<F(R0) 顯然，這是不可能的，因而，

42、上述假設不成立，表明不會出現循環等待條件。7死鎖和“饑餓”之間的主要差別是什么?答：死鎖：多個并發進程相互等待對方占用的資源而產生的錯誤現象。 餓死：在系統中，由于系統采用的資源分配算法不當，雖然每個資源占有者都在有限時間內釋放它所占的資源，但仍然使一些進程永遠得不到資源的一種錯誤現象。 綜合題1設系統中有三種類型的資源（A,B,C）和五個進程（P1,P2,P3,P4,P5）,A資源的數量為17，B資源的數量為5，C資源的數量為20。在T0時刻系統狀態如表3-9所試。系統采用銀行家算法來避免死鎖。T0時刻是否為安全狀態？若試，請給出安全序列。在T0時刻，若進程P2請求資源（0，3，4），能否實

43、現資源分配？為什么？在的基礎上，若進程P4請求資源（2，0，1），能否實現資源分配？為什么?在的基礎上，若進程P1請求資源（0，2，0），能否實現資源分配？為什么?表3-9 T0時刻系統狀態進程最大資源需求量 已分配資源數量系統剩余資源數量 A B C A B C A B CP1 5 5 9 2 1 2 2 3 3P2 5 3 6 4 0 2P3 4 0 11 4 0 5P4 4 2 5 2 0 4P5 4 2 4 3 1 4解：T0時刻是安全狀態，因為存在一個安全序列P4,P5,P1,P2,P3 (2)不能實現資源分配，因為所剩余的資源數量不夠。 (2)可以分配。當分配完成后，系統剩余的資源

44、向量為（0，3，2），這時，仍可找到一個安全序列P4,P5,P1,P2,P3 (3)不能分配。如果分配的話，則系統剩余的資源向量為（0，1，2），這時無法找到一個安全序列。(3)2在銀行家算法中，系統有5個進程和3個資源。若出現以下資源分配情況：進程資源最大請求已分配資源p07, 5, 30, 1, 0p13, 2, 22, 1, 0p29, 0, 23, 0, 2p32, 2, 22, 1, 1p44, 3, 30, 0, 2系統剩余資源數量為(3,2,2)。1） 該狀態是否安全(給出詳細的檢查過程)?2） 如果進程依次有如下資源請求p1:資源請求Request(1,0,2)?p4:資源請求

45、Request(3,3,0)?p0:資源請求Request(0,1,0)?則系統如何進行資源分配，才能避免死鎖？解:1)該系統狀態是否安全,主要看能否找到一個進程完成序列.若能找到,系統只要按照這個序列為進程分配資源,所有進程就都可順利完成;若找不到,系統狀態就是不安全的.為此,可先求出進程的剩余請求矩陣.進程資源最大需求已分配資源剩余資源請求P07, 5, 30, 1, 07, 4, 3P13, 2, 22, 1, 01, 1, 2P29, 0, 23, 0, 26, 0, 0P32, 2, 22, 1, 10, 1, 1P44, 3, 30, 0, 24, 3, 1系統剩余資源向量A=(3

46、,2,2)，在進程剩余資源請求矩陣中找，是否有一行，其值都小于或等于A.若有，選進程P1，滿足它的全部資源請求，它在有限時間內能釋放全部資源，并標記它為完成使系統剩余資源向量A=(5,3,2).之后再重復上述過程，從而找到了一個進城完成序列為：P1,P3,P4,P2,P0 (2)。由此可見，系統狀態是安全的(2)。2）p1:資源請求Request(1,0,2)時，由1）可知，可以立即滿足它，使得A=(2,2,0),P1的分配向量為(3,1,2)，其剩余向量變為(0,1,0). (2)p4:資源請求Request(3,3,0)時，由于系統剩余資源向量A=(2,2,0)，顯然不能滿足它的請求，因為

47、系統剩余資源向量A小于P4的請求 (2)p0:資源請求Request(0,1,0)時，由于系統剩余資源向量A=(2,2,0)，若滿足它的請求，使得系統剩余資源向量A=(2,1,0)。之后，系統仍可以找到一個進程完成序列P1,P4,P0,P4,P2。故可以滿足它的請求。 (2)3系統有同類資源10個，進程p1、p2和p3需要該類資源的最大數量分別為8，6，7。它們使用資源的次序和數量如下圖所示。1） 試給出采用銀行家算法分配資源時，進行第5次分配后各進程的狀態及各進程占用資源情況。2） 在以后的申請中，那次的申請可以得到最先滿足?給出一個進程完成序列。次序進程申請量次序進程申請量1P135P22

48、2P226P133P347P334P128P22解：1）計算第5次分配后進程的狀態和占用資源情況：(5=1*5) p1申請3個，滿足，系統還剩7個p2申請2個，滿足（因為系統的7個可以使p2運行完），系統還剩5個p3申請4個，因為若滿足它的請求，可能使以后的任何進程都不能運行完，故p3等待p1申請2個，滿足（系統還剩5個可以滿足p1的最大請求），系統還剩3個 p2申請2個，不能滿足，等待。此時系統的分配情況如下：p1分配5個后正在運行，p2分配2個后等待分配2個，p3等待分配4個，系統還剩3個。2）p1接著運行，p1申請3個可滿足(2)。P1運行完成后，釋放資源，使系統的資源數量變為8個。首先

49、將p3喚醒，滿足它的4個資源，系統還剩4個，可以喚醒p2，滿足它的2個請求。系統還剩2個。P3申請3個，不能滿足，等待。P2申請2個，系統滿足它，p2接著運行；p2完成，釋放資源，使系統資源變為6個。系統喚醒p3，滿足它的資源請求，最終p3完成，釋放資源，使資源數量恢復為10個。找到的進程完成序列為p1,p2,p3。 (3)4設系統中有150個可用的同類資源。在某時刻系統中的進程已獲得的資源和最大請求資源如下所示，請用銀行家算法分別判斷完成下列請求時，系統是否安全？若安全，請給出進程的完成序列。如不安全，請說明原因。 進程 最大需求量 當前已分配量 p1 70 25 p2 60 40 p3 60 45 p4 60 0(1) 進程p4當前請求25個資源；(2) 之后p4又提出35個資源的請求。解答：系統當前剩余資源量為：150 25 40 45 = 40 (2)(1) 可以滿足(2)，假定先分配p4的25個資源，系統還剩15個。將這15個資源可先分配給p3，p3達到最大請求