操作系統(tǒng)試題及復(fù)習(xí)資料

1、名詞解釋1 操作系統(tǒng) 操作系統(tǒng)是管理和控制計算機系統(tǒng)內(nèi)各種硬件和軟件資源，有效地組織多道程序運行的系統(tǒng)軟件（或程序 集合），是用戶與計算機之間的接口。2 管態(tài) 當(dāng)執(zhí)行操作系統(tǒng)程序時，處理機所處的狀態(tài)3 目態(tài) 當(dāng)執(zhí)行普通用戶程序時，處理機所處的狀態(tài)。4 多道程序設(shè)計 在這種設(shè)計技術(shù)下，內(nèi)存中能同時存放多道程序，在管理程序的控制下交替的執(zhí)行。這些作業(yè)共享 CPU 和 系統(tǒng)中的其他資源。5 并發(fā) 是指兩個或多個活動在同一給定的時間間隔中進行。它是宏觀上的概念。6 并行 是指兩個或多個活動在同一時刻同時執(zhí)行的情況。7 吞吐量 在一段給定的時間內(nèi)，計算機所能完成的總工作量。8 分時 就是對時間的共享。在

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

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

4、發(fā)展的主要動力是什么？ 答：推動操作系統(tǒng)發(fā)展的因素很多，主要可歸結(jié)為兩大方面：硬件技術(shù)更新和應(yīng)用需求擴大伴隨計算機器件的更新?lián)Q代和計算機體系結(jié)構(gòu)的發(fā)展， 促使操作系統(tǒng)的性能和結(jié)構(gòu)有了顯著發(fā)展。 應(yīng)用需求促進了計算 機技術(shù)的發(fā)展，也促進了操作系統(tǒng)的不斷更新升級。3 操作系統(tǒng)的基本特征是什么？ 答：操作系統(tǒng)的基本特征是并發(fā)、共享和不確定。并發(fā)性是指兩個或多個活動在同一給定的時間間隔中進 行；共享是指計算機系統(tǒng)中的資源被多個進程所共用；不確定性是指系統(tǒng)中各種事件發(fā)生順序的不可預(yù)測 性。4 多道程序和多重處理有何區(qū)別？ 答：多道程序是作業(yè)之間自動調(diào)度執(zhí)行、共享系統(tǒng)資源，并不是真正的同時執(zhí)行多個作業(yè)；而

5、多重處理系 統(tǒng)配置多個 cpu ，能真正同時執(zhí)行多道程序。要有效使用多重處理，必須采用多道程序設(shè)計技術(shù)，而多道 程序設(shè)計原則上不一定要求多重處理系統(tǒng)的支持。5 試說明多道程序設(shè)計和多任務(wù)系統(tǒng)之間的關(guān)系 答：多道程序設(shè)計是利用外設(shè)與 cpu 能夠并行處理的特性，在主存同時存放多個程序，使之在系統(tǒng)中交叉 地使用cpu ,從而提高系統(tǒng)資源的利用率。 而多任務(wù)系統(tǒng)主要指多進程交叉使用cpu。多道程序隱含了多任務(wù)處理，但多任務(wù)系統(tǒng)中不一定有多道程序。因為一個程序也可以采用多任務(wù)處理機制。6 不同類型的操作系統(tǒng)提供不同的功能。假定有如下的應(yīng)用環(huán)境，請你為它們選擇適合的操作系統(tǒng)。（1）飛機的導(dǎo)航， （2）辦

6、公自動化系統(tǒng)， （3）航空訂票系統(tǒng)， （ 4）復(fù)雜的科學(xué)計算， （5）圖書檢索系統(tǒng) 答：（1）飛機的導(dǎo)航系統(tǒng)，應(yīng)采用硬實時操作系統(tǒng)（2）辦公自動化系統(tǒng)，應(yīng)采用分時操作系統(tǒng)（3）航空訂票系統(tǒng)，應(yīng)采用軟實時操作系統(tǒng)（4）復(fù)雜的科學(xué)計算，應(yīng)采用批處理系統(tǒng)（5）圖書檢索系統(tǒng)，應(yīng)采用軟實時操作系統(tǒng)7 什么是批處理系統(tǒng)，它有什么特征？ 答：批處理系統(tǒng)：操作員把用戶提交的作業(yè)分類，把一批作業(yè)編成一個作業(yè)執(zhí)行序列，由專門編制的監(jiān)督 程序自動依次處理。其主要特征是：用戶脫機使用計算機、成批處理、多道程序運行。8 什么是分時系統(tǒng)，它有什么特征？ 答：分時系統(tǒng)：把處理機的運行時間分成很短的時間片，按時間片輪轉(zhuǎn)的方式

7、，把處理機分配給各進程使 用。其主要特征是：交互性、多用戶同時性、獨立性。9 什么是實時系統(tǒng)？它有什么特征？ 答：實時系統(tǒng)：在被控對象允許時間范圍內(nèi)做出響應(yīng) 。其主要特征是：對實時信息分析處理速度要比進入 系統(tǒng)快、要求安全可靠、資源利用率低。i/o 操作等。（ 2 分） ，防止受到用戶程序的損害。10 什么是處理機的核心態(tài)和用戶態(tài)？為什么要設(shè)置這兩種不同的狀態(tài)？ 答：當(dāng)執(zhí)行操作系統(tǒng)程序時，處理機處于核心態(tài)。它有較高的特權(quán)，可以執(zhí)行所有的指令，包括一般用戶 程序中不能使用的特權(quán)指令，從而能對所有寄存器和內(nèi)存進行訪問，啟動 用戶程序是在用戶態(tài)下執(zhí)行，它的權(quán)限較低，只能執(zhí)行指令集中非特權(quán)指令。 設(shè)置

8、這兩種不同狀態(tài)的目的是為了保護操作系統(tǒng)程序（特別是其內(nèi)核部分）C,C+轎口 Perl語言）來編制；使用11 系統(tǒng)調(diào)用與過程調(diào)用在功能和實現(xiàn)上有什么相同點和不同點？ 答：相同點：兩者都由程序代碼構(gòu)成，可直接用高級程序設(shè)計語言（如 方式相同以函數(shù)調(diào)用的形式出現(xiàn)，調(diào)用時傳送參數(shù)。不同點：代碼層次不同，過程調(diào)用不屬于操作系統(tǒng)的一部分，而系統(tǒng)調(diào)用是操作系統(tǒng)的一部分。 運行狀態(tài)不同。過程調(diào)用只能在用戶態(tài)下運行，不能進入核心態(tài)，而系統(tǒng)調(diào)用是在核心態(tài)下運行的。進 入方式不同。 過程調(diào)用在用戶程序中調(diào)用， 并直接在用戶空間內(nèi)執(zhí)行； 而系統(tǒng)調(diào)用可以在用戶程序中調(diào)用， 但是在用戶程序中執(zhí)行到系統(tǒng)調(diào)用時，會產(chǎn)生異常事

9、件。實現(xiàn)處理機狀態(tài)從用戶態(tài)到核心態(tài)的轉(zhuǎn)變，從而 進入操作系統(tǒng)核心空間去執(zhí)行系統(tǒng)調(diào)用的代碼。12 試說明特權(quán)指令和系統(tǒng)調(diào)用之間的區(qū)別與聯(lián)系。 答：特權(quán)指令是一類只能在核心態(tài)下執(zhí)行的機器指令。而系統(tǒng)調(diào)用不是機器指令，它往往以函數(shù)調(diào)用的形 式出現(xiàn)， 實現(xiàn)操作系統(tǒng)提供的子功能， 它是操作系統(tǒng)與用戶的編程接口 。在用戶程序中可以使用系統(tǒng)調(diào)用 來獲得操作系統(tǒng)服務(wù)，在系統(tǒng)調(diào)用代碼中可以使用特權(quán)指令1 順序性 是指順序程序所規(guī)定的每個動作都在上個動作結(jié)束后才開始的特性。2 封閉性 是指只有程序本身的動作才能改變程序的運行環(huán)境。3 可再現(xiàn)性 是指程序的執(zhí)行結(jié)果與程序運行的速度無關(guān)。4 進程程序在并發(fā)環(huán)境中的執(zhí)行

10、過程。5 互斥 在邏輯上本來完全獨立的進程，由于競爭同一個資源而產(chǎn)生的相互制約的關(guān)系。6 同步 是指進程間共同完成一項任務(wù)時直接發(fā)生相互作用的關(guān)系。也就是說，這些具有伙伴關(guān)系的進程在執(zhí)行次 序上必須遵循確定的規(guī)律。7 臨界資源 一次僅允許一個進程使用的資源。8 臨界區(qū) 在每個進程中訪問臨界資源的那段程序。9 線程 線程是進程中實施調(diào)度和分派的基本單位。10 管程 管程是一種高級同步機制，一個管程定義一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程在其上執(zhí)行的一組操作，這組操作 能使進程同步和改變管程中的數(shù)據(jù)。11 進程控制塊 進程控制塊是進程存在的唯一標(biāo)識，它保存了系統(tǒng)管理和控制進程所必須的信息，是進程動態(tài)特性的集

11、中 表現(xiàn)。12 原語 指操作系統(tǒng)中實現(xiàn)一些具有特定功能的程序段，這些程序段的執(zhí)行過程是不可分割的，即其執(zhí)行過程不允 許被中斷。13 就緒態(tài)進程已經(jīng)獲得了除cpu之外的全部資源，等待系統(tǒng)分配 cpu，旦獲得cpu,進程就可以變?yōu)檫\行態(tài)。14 運行態(tài)正在 cpu 上執(zhí)行的進程所處的狀態(tài)。在單 cpu 系統(tǒng)中，任何時候最多只能有一個進程處于運行狀態(tài)。15 阻塞態(tài) 又稱等待態(tài)，指正在運行的進程因等待某個條件發(fā)生而不能運行時所處的狀態(tài)。處于阻塞態(tài)的進程在邏輯 上是不能運行的，即使 cpu 空閑，它也不能占用 cpu。16 進程通信 是指進程間的信息交換。17 同步機制 同步機構(gòu)是負(fù)責(zé)處理進程之間制約關(guān)系

12、的機制，即操作系統(tǒng)中負(fù)責(zé)解決進程之間協(xié)調(diào)工作的同步關(guān)系（直 接制約關(guān)系），以和共享臨界資源的互斥關(guān)系（間接制約關(guān)系）的執(zhí)行機構(gòu)。簡答題1在操作系統(tǒng)中為什么要引入進程概念？答：由于多道程序并發(fā)執(zhí)行時共享系統(tǒng)資源，共同決定這些資源的狀態(tài)，因此系統(tǒng)中各程序在執(zhí)行過程中就岀現(xiàn)了相互制約的新關(guān)系，程序的執(zhí)行岀現(xiàn)“走走停?！钡男聽顟B(tài)。用程序這個靜態(tài)的概念已不能如實反映程序并發(fā)執(zhí)行過程中的這些特征。為此，人們引入了 “進程(Process )”這一概念來描述程序動態(tài)執(zhí)行過程的性質(zhì)。進程和程序是兩個完全不同的概念。然而，進程與程序之間存在密切關(guān)系，進程的功能是通過程序的運行得以實現(xiàn)的，進程活動的主體是程序。進

13、程不能脫離開具體程序而獨立存在。2有人說，一個進程是由偽處理機執(zhí)行的一個程序，這話對嗎？為什么？答：對。因為偽處理機的概念只有在執(zhí)行時才存在，它表示多個進程在單處理機上并發(fā)執(zhí)行的一個調(diào)度單位。因此，盡管進程是動態(tài)概念，是程序的執(zhí)行過程，但是，在多個進程并行執(zhí)行時，仍然只有一個進程占據(jù)處理機執(zhí)行，而其他并發(fā)進程則處于就緒或等待狀態(tài)。這些并發(fā)進程就相當(dāng)于由偽處理機執(zhí)行的程序。3試比較進程和程序的區(qū)別答：(1)進程是一個動態(tài)的概念，而程序是一個靜態(tài)的概念，程序是指令的有序集合，無執(zhí)行含義，進程則強調(diào)執(zhí)行的過程。(2) 進程具有并行特征(獨立性、異步性)，程序則沒有。(3) 不同的進程可以包含同一個程

14、序，同一程序在執(zhí)行中也可以產(chǎn)生多個進程。4進程的基本狀態(tài)有哪些？試描繪進程狀態(tài)轉(zhuǎn)換圖。答：進程至少有三種基本狀態(tài)：運行狀態(tài)、就緒狀態(tài)和阻塞狀態(tài)(或等待狀態(tài))。進程狀態(tài)轉(zhuǎn)換如下圖:5并發(fā)進程間的制約有哪兩種？引起制約的原因是什么？答：并發(fā)進程所受的制約有兩種：直接制約和間接制約。直接制約是由并發(fā)進程相互共享對方的私有資源所引起的；間接制約是由競爭共有資源而引起的。6什么是進程間的互斥？什么是進程間同步？答：進程間的互斥是指：一組并發(fā)進程中的一個或多個程序段，因共享某一共有資源而導(dǎo)致它們必須以一 個不許交叉執(zhí)行的單位執(zhí)行，即不允許兩個以上的共享該資源的并發(fā)進程同時進入臨界區(qū)。進程間的同步是指：異步

15、環(huán)境下的一組并發(fā)進程因直接制約相互發(fā)送消息而進行相互合作、相互等待，是 各進程按一定的速度執(zhí)行的過程。7什么是臨界區(qū)和臨界資源？進程進入臨界區(qū)的調(diào)度原則是什么？答：臨界資源一一一次僅允許一個進程使用的資源臨界區(qū)一一在每個進程中訪問臨界資源的那段程序一個進程進入臨界區(qū)的調(diào)度原則是： 如果有若干進程要求進入空閑的臨界區(qū)，一次僅允許一個進程進入 任何時候，處于臨界區(qū)內(nèi)的進程不可多于一個。如已有進程進入自己的臨界區(qū)，則其他所有試圖進入臨界區(qū)的進程必須等待 進入臨界區(qū)的進程要在有限的時間內(nèi)退出，以便讓其他進程能和時進入自己的臨界區(qū) 如果進程不能進入自己的臨界區(qū)，則應(yīng)讓出cpu,避免進程出現(xiàn)“忙等”現(xiàn)象.

16、8簡述信號量的定義和作用。P, V操作原語是如何定義的？答：信號量一般是由兩個成員組成的數(shù)據(jù)結(jié)構(gòu)，其中一個成員是整型變量，表示該信號量的值，它與相應(yīng)資源的使用情況有關(guān)；另一個是指向PCB的指針。當(dāng)多個進程都等待同一信號量時，它們就排成一個隊列，由信號量的指針項指出該隊列的隊首。（ 2 分）信號量通?？梢院唵畏从吵鱿鄳?yīng)資源的使用情況，它與P、V操作原語一起使用可實現(xiàn)進程的同步和互斥。（ 1 分）P,V 操作原語有如下定義。P（S）順序執(zhí)行下述兩個動作（1分）：信號量的值減 1，即 S=S-1;如果 S>=0, 則該進程繼續(xù)執(zhí)行。如果S<0,則把該進程的狀態(tài)置為阻塞態(tài)，把相應(yīng)的PCB連

17、入該信號量隊列的末尾，并放棄處理機，進行等待（直到其他進程在 S上執(zhí)行V操作，把它釋放出來為止）。V（S） 順序執(zhí)行下述兩個動作（ 1 分）：S值加1，即S=S+1;如果 S>0, 則該進程繼續(xù)運行；如果S<=0,則釋放信號量隊列上的第一個PCB所對應(yīng)的進程（把阻塞態(tài)改為就緒態(tài)），執(zhí)行V操作的進程繼續(xù)運行。9 什么是線程？它與進程有什么關(guān)系？ 答：線程是進程中實施調(diào)度和分派的基本單位。線程和進程之間有如下關(guān)系： 一個進程可以有多個線程，但至少有一個線程；而一個線程只能在一個進程的地址空間內(nèi)活動。 資源分配給進程，同一進程的所有線程共享該進程的所有資源。 處理機分給線程，即真正在處理

18、機上運行的是線程。 線程在執(zhí)行過程中，需要協(xié)作同步。不同進程的線程間要利用消息通信的辦法實現(xiàn)同步。 10什么是管程？它由哪幾部分組成？有什么基本特性 ?答：一個管程定義了一個數(shù)據(jù)結(jié)構(gòu)和能為并發(fā)進程在其上執(zhí)行的一組操作，這組操作能同步進程和改變管 程中的數(shù)據(jù)。一個管程由四個部分組成，它們是管程名稱、局部與管程的共享數(shù)據(jù)的說明、對數(shù)據(jù)進行操作的一組過程 和對該共享數(shù)據(jù)賦初值的語句。管程具有以下特性： 管程內(nèi)部的局部數(shù)據(jù)變量只能被管程內(nèi)定義的過程所訪問，不能被管程外面聲明的過程直接訪問 進程要想進入管程，必須調(diào)用管程內(nèi)的某個過程 一次只能有一個進程在管程內(nèi)執(zhí)行， 而其余調(diào)用該管程的進程都被掛起， 等

19、待該管程成為可用的。 就是 說，管程自身能有效地實現(xiàn)互斥。綜合題1如下圖所示的工作模型中，有三個進程p0,p1,p2和三個緩沖區(qū)B0,B1,B2.進程之間借助于相鄰緩沖區(qū)進行消息傳遞：每個進程每次從緩沖區(qū)中取一條消息，經(jīng)加工處理后送入另一個緩沖區(qū)中，三個緩沖區(qū)分別 可存放3,2,2個消息。初始時，僅緩沖區(qū) 0有一個消息。試用P、V操作寫出三個進程之間的同步和互斥流 程。答：這是一個生產(chǎn)者 /消費者問題，而且每個進程既是生產(chǎn)者，也是消費者。（2'）為此，應(yīng)設(shè)置6個信號量：B0S1,B0S2,B1S1,B1S2,B2S1,B2S2,分別代表B0,B1,B2中是否有空緩沖和有數(shù)據(jù)。B0S1,

20、B0S2,B1S1,B1S2,B2S2:semaphore;B0S1=2;B0S2=1;B1S1=2;B1S2=0;B2S1=2;B2S2=0;（2'）Cobegin （'6 '2*3）P0P1P2beginbeginbeginP(B0S2)P(B1S2)P(B2S2)從 B0 取一個數(shù)據(jù)從 B1 取一個數(shù)據(jù)從 B2 取一個數(shù)據(jù)V(B0S2)V(B1S1)V(B2S1)加工加工加工P(B1S1)P(B2S1)P(B0S1)將加工結(jié)果送 B1將加工結(jié)果送 B2將加工結(jié)果送 B0V(B1S2)V(B2S2)V(B0S2)endendendcoend這道題也可以增加互斥信號量

21、，以便P0 與 P1 之間互斥使用B0 緩沖區(qū)， P1 與 P2 之間互斥使用 B1 緩沖區(qū)，P2與P0之間互斥使用B0緩沖區(qū)。這里主要描述它們之間的同步關(guān)系。若考慮互斥共享緩沖區(qū)，請自己加上。2設(shè)用三個隊列管理緩沖區(qū)池的使用情況，分別為空白緩沖隊列 em,輸入緩沖隊列in，以和輸出緩沖隊列 out。過程add_buf(type,numb)和take_buf(type,numb)分別用來把緩沖區(qū) numb插入type隊列和從type隊列中 取出緩沖區(qū)numb。試描述進程從任一緩沖隊列中得到一個緩沖區(qū)的過程get_buf(type,numb)和釋放一個緩沖區(qū) numb 進入緩沖隊列的過程 put

22、_buf(type,numb) 。答：假定用信號量s代表任一隊列的可用緩沖區(qū)個數(shù)。 假定三個隊列的初值分別為 n1,n2,n3。對任一隊列的 操作必須互斥。因此再引入一個互斥使用任一隊列的信號量mutex，其初值為1。這里type代表隊列的類型，它的取值為輸入、輸出和空白。(4')當(dāng)有進程希望從任一隊列取一個緩沖區(qū)時，過程 get_buf(type,numb) 的動作如下：get_buf(type,numb) ('3'beginp(s)p(mutex)numb=take_buf(type,numb)v(mutex)end當(dāng)有進程希望向任一隊列送一個緩沖區(qū)時，過程 put

23、_buf(type,numb) 的動作如下：put_buf(type,numb)('3')beginp(mutex)add_buf(type,numb)v(mutex)v(s)end.3 設(shè)有一個售票廳，可容納 100 人購票。如果廳內(nèi)不足 100 人則允許進入，進入后購票，購票后退出。如 果廳內(nèi)已有 100 人，則在廳外等候。試問：1 ) 購票者之間是同步還是互斥？用 P、V 操作表達購票者的工作過程。解： 1)購票者之間是互斥關(guān)系。(2')2) 一個售票廳可容納 100 人購票，說明最多允許 100 個購票者共享售票廳；可引入一個信號量 empty， 其初值為100

24、。由于購票者必須互斥地進行購票，故應(yīng)再設(shè)一個mutex，其初值為1。(4'用 P、V 操作表達購票者的工作過程如下：('4')empty,mutex:semaphore;empty:=100; mutex:=1;beginp(empty)p(mutex)進入廳內(nèi)購票 ,購票后退出v(empty)v(mutex)end.4 某招待所有 100 個床位，住宿者入住要先登記(在登記表上填寫姓名和床位號) 登記表上刪去姓名和床位號) 請給出住宿登記和注銷過程的算法描述 答：某招待所有 100 個床位，為了正確管理，引入一個信號量 empty 代表空床位數(shù)，初值為 入住要先登記(

25、在登記表上填寫姓名和床位號) ，顯然，登記表是一個臨界資源，必須互斥訪問，離去時要注銷登記(在100；住宿者引入一個mutex，其初值為1。(4 '住宿登記和注銷過程的算法描述如下：住宿登記： ('3')beginp(empty) / 檢查有無床位 p(mutex) / 申請登記 找出一個空床位將名字登入表中v(mutex)end注銷過程： ('3')beginp(mutex) / 申請退房找出自己的登記項，并刪除該項的登記v(mutex) v(empty)end.5 有一個閱覽室，共有 100 個座位。為了很好地利用它，讀者進入時必須先在登記表上進行登

26、記。 目設(shè)有座位號和讀者姓名；離開時再將其登記項擦除。 試問：為描述讀者的動作，應(yīng)編寫幾個程序，應(yīng)設(shè)幾個進程、它們之間的關(guān)系怎樣？并請用 述進程之間的同步算法。 解：為了描述閱覽室，用一個登記表來記錄其使用情況。表中共有100 項。每當(dāng)有讀者進入閱覽室時，為了正確地登記，各讀者應(yīng)互斥使用 (1 ')。為此設(shè)兩個信號量： mutex 為互斥信號量，用來制約各讀者互斥地 進行登記，其初值為1;empty為同步信號量，用來制約各讀者能同時進入閱覽室的數(shù)量，其初值為100 (2')。下面用兩個過程描述對表格應(yīng)執(zhí)行的動作：該表表P、 V 操作描登記過程： ('2')beg

27、in擦除過程：begin('2 'P(empty)P(mutex)找到一個登記項登記P(mutex)找到自己的登記項擦除V(mutex)endV(mutex)V(empty)end為了正確地描述讀者的動作，可以將讀者看成進程。若干讀者希望進入閱覽室時，調(diào)用登記過程，退出閱覽室時，調(diào)用擦除過程 (1') 。 可見，一個程序可對應(yīng)多個讀者?？稍O(shè)的進程數(shù)由讀者數(shù)決定，其動作如下：('2')begin調(diào)用登記過程 進入閱覽室閱讀 準(zhǔn)備退出 調(diào)用擦除過程end.6 一條河上架設(shè)了由若干個橋墩組成的一座橋。若一個橋墩只能站一個人，過河的人只能沿著橋向前走而 不能向后

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

29、=R-1;If R=0 V(S);V(S1);/為同時過河 ,申請對計數(shù)器計數(shù)/同方向過河的人站滿橋墩時,重新申請計數(shù)/申請過河/釋放計數(shù)器的使用權(quán)(3')/如果已經(jīng)無同向的人過河,釋放占用權(quán)end.7 在一個飛機訂票系統(tǒng)中，多個用戶共享一個數(shù)據(jù)庫。各用戶可以同時查詢信息，若有一個用戶要訂票， 須更新數(shù)據(jù)庫時，其余所有用戶都不可以訪問數(shù)據(jù)庫。請用 P,V 操作設(shè)計一個同步算法，實現(xiàn)用戶查詢與 訂票功能。要求：當(dāng)一個用戶訂票而需要更新數(shù)據(jù)庫時，不能因不斷有查詢者到來而使其長時間等待。利 用信號量機制保證其正常執(zhí)行。解：這是典型的讀者寫者問題，查詢信息的用戶是讀者，訂票用戶是寫者，并且要求

30、寫者優(yōu)先。(2')變量說明： ('2')計數(shù)變量rc正在運行的查詢者進程數(shù)目，初值為0.信號量Sw控制訂票者進程的活動，初值為 1.Src互斥使用rc變量，初值為1.S當(dāng)訂票者到達時封鎖后續(xù)的讀進程，初值為1.讀者進程P(S)P(Src)rc=rc+1if (rc=1) P(Sw)V(Src)V(S)(2)查詢庫當(dāng)中的信息P(Src)rc=rc-1;if (rc=0) V(Sw)V(Src)(2')寫者進程 (、2')P(S)P(Sw)更新數(shù)據(jù)庫內(nèi)容V(Sw)V(S)8某車站售票廳，任何時刻最多可容納20名購票者進入，當(dāng)售票廳中少于20名購票者時，則廳外

31、的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答下列問題：(1) 用PV操作管理這些并發(fā)進程時，應(yīng)怎樣定義信號量，寫岀信號量的初值以和信號量各種取值的含義。(2) 根據(jù)所定義的信號量，把應(yīng)執(zhí)行的PV操作填入下述空格中，以保證進程能夠正確地并發(fā)執(zhí)行。COBEGIN PROCESS Pl(l=1，2，)begin進入售票廳； 購票;退出；endCOEND若欲購票者最多為n個人，寫出信號量可能的變化范圍(最大值和最小值)。 答：定義一信號量S,初始值為20。(T)意義：(、3 '=1 'S>0 S的值表示可繼續(xù)進入售票廳的人數(shù)S=0表示售票廳中已有20名

32、顧客(購票者)S<0|S|的值為等待進入售票廳的人數(shù)(2) 上空格為P(S) (2)；下空格為 V(S). (2)(3) S的最大值為20_ (T); S的最小值為20- n (T)9在公共汽車上，司機和售票員各行其職，司機負(fù)責(zé)開車和到站停車；售票員負(fù)責(zé)售票和開門關(guān)門，當(dāng)售 票員關(guān)好車門后，駕駛員才能開車行使。試用P/V操作實現(xiàn)司機與售票員間的同步。解答：semaphore mutex仁0,mutex2=0;(2')main()cobegindriver()busman()coenddriver()while(true) p(mutexl) 啟動公共汽車 正常開車 到站停車v(m

33、utex2)(3'busman()while(true)關(guān)車門v(mutex1)售票p(mutex2)開車門上下乘客(3'10并發(fā)問題：設(shè)有兩個優(yōu)先級相同的進程p1, p2如下。令信號s1, s2的初值為0,已知z=2，試問p1, p211試用信號量機制來描述下述前趨圖M1M5M4M2M3M7M6M8解答：首先定義信號量相對應(yīng)的進程是否完成：(2'并發(fā)運行結(jié)束后x=? y=? z=?進程p1y := 1y := y+2 v(s1)z := y+1 p(s2)進程p2x := 1x := x+1p(s1)x := x+yv(s2)y := z+y解答：(分析過程略z :=

34、 x+z2 '從結(jié)果來看，兩個進程無論誰先誰后，結(jié)果都是一樣的。(2 'x = 5; y = 12; z = 9(6')S12,S13,S14,S26,S36,S47,S57,S38,S78的初值都為 0,分別表示COBEGIN(、8 '=1 '*8)Process M1:beginV(S12)V(S13)V(S14)endProcess M2:beginP(S12) V(26)endProcess M3:beginP(S13) V(S36)V(S38)endProcess M4:beginP(S14)V(S47)endProcess M5:beginV

35、(S57)endProcess M6:beginP(S26)P(S36)endProcess M7:beginP(S47)P(S57) P(S78)endProcess M8:beginP(S38)P(S78)endCOEND12試用信號量機制來描述下述前趨圖Process M1: beginV(S12)V(S13) end Process M2:beginP(S12)V(24)V(25) end Process M3: beginP(S13)V(S36) end Process M4: beginP(S14)V(S46) end Process M5: beginP(S25)V(S56) e

36、nd Process M6:beginP(S36)P(S46)P(S56) end COEND13設(shè)系統(tǒng)有三個并發(fā)進程 R,C,P,共享一個能存放n個數(shù)據(jù)的環(huán)形緩沖區(qū) buf。進程R負(fù)責(zé)從輸入設(shè)備上讀 數(shù)據(jù)，每讀一個后把它存放在緩沖區(qū) buf 的一個單元中；進程 C 負(fù)責(zé)從緩沖區(qū)讀數(shù)據(jù)并進行處理，之后將 處理結(jié)果再送入緩沖區(qū)的一個單元中；進程P負(fù)責(zé)從緩沖區(qū)讀進程 C處理的結(jié)果并打印。請用 P、V操作為三進程的正確執(zhí)行寫出同步算法。解答：解決同步問題需設(shè)一個互斥信號量 mux，用于控制三個進程互斥使用緩沖區(qū)，初值為 1 ;再設(shè)三個 同步信號量,用于控制對緩沖區(qū)的空閑數(shù)量和不同數(shù)據(jù)個數(shù)的記錄。S0

37、 表示緩沖區(qū)空閑個數(shù),初值為 n；S1 表示緩沖區(qū)中輸入數(shù)據(jù)的個數(shù)，初值為算法描述如下：('6 '2 '3)進程 R進程 CL1: L2:P(S0)P(S1)0； S2 表示緩沖區(qū)中輸出數(shù)據(jù)的個數(shù)，初值為0。 (4')進程 PL3:P(S2)P(mux)P(mux)P(mux)讀一個數(shù)據(jù)從緩沖區(qū)中取一個從緩沖區(qū)中讀送緩沖區(qū)數(shù)據(jù)處理后放回去輸出數(shù)據(jù)V(mux)V(mux)V(mux)V(S1)V(S2)V(S0) 打印gotoL1:gotoL2:gotoL3:名詞解釋1 死鎖 是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能引發(fā)的事件而無限期地僵

38、持下 去的局面。2 饑餓 在系統(tǒng)中，每個資源占有者都在有限時間內(nèi)釋放它所占有的資源，但資源中存在某些申請者由于某種原因 卻永遠(yuǎn)得不到資源的一種錯誤現(xiàn)象。3 死鎖防止 要求進程申請資源時遵循某種協(xié)議，從而打破產(chǎn)生死鎖的四個必要條件中的一個或幾個，保證系統(tǒng)不會進 入死鎖狀態(tài)。4 死鎖避免 對進程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查，并根據(jù)檢查結(jié)果決定是否進行資源分配。就是說， 在資源分配過程中若預(yù)測有發(fā)生死鎖的可能性，則加以避免。這種方法的關(guān)鍵是確定資源分配的安全性。5 安全序列針對當(dāng)前分配狀態(tài)來說， 系統(tǒng)至少能夠按照某種次序為每個進程分配資源 （直至最大需求） ，并且使他們依 次成功地運行完

39、畢，這種進程序列p1,p2,pn就是安全序列。簡答題1 計算機系統(tǒng)中產(chǎn)生死鎖的根本原因是什么?死鎖發(fā)生的四個基本條件是什么？答: 計算機系統(tǒng)中產(chǎn)生死鎖的根本原因是：資源有限且操作不當(dāng)。死鎖發(fā)生的四個基本條件有互斥條件、請求保持條件（占有且等待條件） 、非剝奪條件（不可搶占條件）和環(huán)路條件（循環(huán)等待條件） 。2 簡述發(fā)生死鎖的四個必要條件 ?答： 四個必要條件是：互斥條件、占有且等待條件（請求保持條件） 、不可搶占條件（非剝奪條件）和循 環(huán)等待條件（環(huán)路條件） 。互斥條件某個資源在一段時間內(nèi)只能由一個進程占有，不能同時被兩個和其以上的進程占有。 占有且等待條件進程至少已經(jīng)占有一個資源，但又申請新

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

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

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

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

44、。 在 T0 時刻，若進程 P2 請求資源( 0， 3， 4)，能否實現(xiàn)資源分配？為什么？ 在的基礎(chǔ)上，若進程 P4請求資源(2, 0，1)，能否實現(xiàn)資源分配？為什么 ？ 在的基礎(chǔ)上，若進程 P1請求資源(0, 2，0)，能否實現(xiàn)資源分配？為什么 ？表 3-9 T0 時刻系統(tǒng)狀態(tài)進程最大資源需求量已分配資源數(shù)量系統(tǒng)剩余資源數(shù)量ABCABCABCP1559212233P2536402P34011405P4425204P5424314解： T0時刻是安全狀態(tài)，因為存在一個安全序列P4,P5,P1,P2,P3 (2' 不能實現(xiàn)資源分配，因為所剩余的資源數(shù)量不夠。(2') 可以分配。當(dāng)

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

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

47、10, 1, 1P44, 3, 30, 0, 24, 3, 1系統(tǒng)剩余資源向量 A=(3,2,2) ，在進程剩余資源請求矩陣中找，是否有一行，其值都小于或等于有，選進程P1,滿足它的全部資源請求，它在有限時間內(nèi)能釋放全部資源，并標(biāo)記它為完成使系統(tǒng)剩余資A.若源向量 A=(5,3,2). 之后再重復(fù)上述過程，從而找到了一個進城完成序列為：P1,P3,P4,P2,P0(2')。由此可見，系統(tǒng)狀態(tài)是安全的 (2')。2)p1:資源請求Request(1,0,2)時，由1)可知，可以立即滿足它，使得A=(2,2,0),P1 的分配向量為 (3,1,2)，其剩余向量變?yōu)?(0,1,0).

48、(2')p4:資源請求Request(3,3,0)時，由于系統(tǒng)剩余資源向量源向量A小于P4的請求 (2Jp0:資源請求Request(0,1,0)時，由于系統(tǒng)剩余資源向量A=(2,1,0)。之后，系統(tǒng)仍可以找到一個進程完成序列A=(2,2,0)，顯然不能滿足它的請求，因為系統(tǒng)剩余資A=(2,2,0) ，若滿足它的請求， 使得系統(tǒng)剩余資源向量P1,P4,P0,P4,P2故可以滿足它的請求。(2)3系統(tǒng)有同類資源10個，進程pl、p2和p3需要該類資源的最大數(shù)量分別為8，6, 7。它們使用資源的次序和數(shù)量如下圖所示。1) 試給出采用銀行家算法分配資源時，進行第 5 次分配后各進程的狀態(tài)和各

49、進程占用資源情況。2) 在以后的申請中，那次的申請可以得到最先滿足?給出一個進程完成序列。次序進程申請量次序進程申請量1P135P222P226P133P347P334P128P22解：1)計算第5次分配后進程的狀態(tài)和占用資源情況：('5 =T*5) p1 申請 3 個，滿足，系統(tǒng)還剩 7 個 p2申請2個，滿足(因為系統(tǒng)的 7個可以使p2運行完)，系統(tǒng)還剩5個 p3申請4個，因為若滿足它的請求，可能使以后的任何進程都不能運行完，故p3等待 p1申請2個，滿足(系統(tǒng)還剩 5個可以滿足p1的最大請求)，系統(tǒng)還剩3個 p2 申請 2 個，不能滿足，等待。此時系統(tǒng)的分配情況如下：pl分配5個

50、后正在運行，p2分配2個后等待分配2個，p3等待分配4個，系統(tǒng)還剩3個。2) pl接著運行，pl申請3個可滿足(2 '。P1運行完成后，釋放資源，使系統(tǒng)的資源數(shù)量變?yōu)?個。首先將p3喚醒，滿足它的4個資源，系統(tǒng)還剩4個，可以喚醒p2，滿足它的2個請求。系統(tǒng)還剩2個。P3申請3個，不能滿足，等待。P2申請2個，系統(tǒng)滿足它，p2接著運行；p2完成，釋放資源，使系統(tǒng)資源變?yōu)?個。系統(tǒng)喚醒p3,滿足它的資源請求，最終 p3 完成，釋放資源，使資源數(shù)量恢復(fù)為10個。找到的進程完成序列為 p1,p2,p3。(3')4 設(shè)系統(tǒng)中有 150 個可用的同類資源。在某時刻系統(tǒng)中的進程已獲得的資源和

51、最大請求資源如下所示，請用銀行家算法分別判斷完成下列請求時，系統(tǒng)是否安全？若安全，請給出進程的完成序列。如不安全，請說明原因。進程最大需求量當(dāng)前已分配量p17025p26040p36045p4600(1) 進程 p4 當(dāng)前請求 25 個資源；(2) 之后 p4 又提出 35 個資源的請求。解答：系統(tǒng)當(dāng)前剩余資源量為：150 -25 -40 -45 = 40 (2 ' 可以滿足(2'，假定先分配p4的25個資源，系統(tǒng)還剩15個。將這15個資源可先分配給 p3, p3達到 最大請求，釋放 60 個；之后可以分配給其他任何進程，系統(tǒng)中的進程都能順利完成。由此可見，p2請求的25個資源

52、可以滿足，且能找到完成序列：p3，p1，p2，p4，(4'(2) 當(dāng) p4 再提出 35 個資源請求時，系統(tǒng)還剩 15，顯然不能滿足它的請求，讓其阻塞等待。(2')5系統(tǒng)中有五個進程，分別為 p1p2p3p4p5，四類資源分別為r1r2r3r4。某一時刻，系統(tǒng)剩余資源向量A=(1 ， 2， 3， 0)。(1 )用銀行家算法試判斷系統(tǒng)當(dāng)前狀態(tài)是否安全？(2) 當(dāng)進程p3提出對資源r3的剩余請求時，能否滿足她？(3) 系統(tǒng)初始配置的各類資源分別為多少？解答：系統(tǒng)剩余資源向量A=(1, 2, 3, 0) ?，F(xiàn)在需求出各進程的剩余資源請求矩陣:12000750NEED 1212(2&#

53、39;)02200622(1) 詳細(xì)步驟省略。由于系統(tǒng)存在一個進程完成的安全序列P1P3P4P2P5(2')，故系統(tǒng)狀態(tài)是安全的 (2 '。 進程P3提出對資源R3的剩余請求為1，由于系統(tǒng)剩余資源向量 A=(1,2, 3, 0)，故可以假定分配給它 如果能找到一個安全序列，就可以真正進行分配。當(dāng)分配給P3 一個資源時，系統(tǒng)剩余資源向量A=(1 ,2 ,2,0)。由此可見，仍然可以找到一個與相同的安全序列。故可以滿足P3的請求。(3'(3) 系統(tǒng)初始配置的各類資源分別為 (3 ,9 , 12 , 12 )。 (1') 名詞解釋1 作業(yè) 用戶在一次上機過程中要求計算

54、機系統(tǒng)所做工作的集合。2 周轉(zhuǎn)時間 是指從作業(yè)進入系統(tǒng)開始，到作業(yè)退出系統(tǒng)所經(jīng)歷的時間。3 響應(yīng)時間 是分時系統(tǒng)的一個技術(shù)指標(biāo)，指從用戶輸入命令到系統(tǒng)對命令開始執(zhí)行和顯示所需要的時間。4 作業(yè)調(diào)度 作業(yè)調(diào)度的主要任務(wù)是完成作業(yè)從后備狀態(tài)到執(zhí)行狀態(tài)和從執(zhí)行狀態(tài)到完成狀態(tài)的轉(zhuǎn)換。5 進程調(diào)度 也稱低級調(diào)度程序，它完成進程從就緒狀態(tài)到運行狀態(tài)的轉(zhuǎn)化。實際上，進程調(diào)度完成一臺物理的 cpu 轉(zhuǎn) 變成多臺虛擬（或邏輯）的 cpu 的工作。6 交換調(diào)度 是基于系統(tǒng)確定的某個策略，將主存中處于等待狀態(tài)或就緒狀態(tài)的某個或某些進程交換到外存交換區(qū)中， 以便將外存交換區(qū)上具備運行條件的進程換入主存，準(zhǔn)備執(zhí)行。引入交換調(diào)度的目的是為了解決主存緊張 和提高主存的利用效率。7 剝奪式調(diào)度 當(dāng)一個進程正在執(zhí)行時，系統(tǒng)基于某種策略強行將處理機從占有者進程剝奪而分配給另一個進程的調(diào)度。 這種調(diào)度方式系統(tǒng)開銷大，但系統(tǒng)能和時響應(yīng)請求。8 非剝奪式調(diào)度系統(tǒng)一旦把處理機分配給某個進程之后， 該進程