公務(wù)員-計算機類 操作系統(tǒng)總復(fù)習及相關(guān)習題.doc

本文由jingang520644貢獻 doc文檔可能在WAP端瀏覽體驗不佳。建議您優(yōu)先選擇TXT，或下載源文件到本機查看。 操作系統(tǒng)總復(fù)習及相關(guān)習題 操作系統(tǒng)總復(fù)習及相關(guān)習題 第一章 第一章 名詞解釋 1 操作系統(tǒng) 操作系統(tǒng)是管理和控制計算機系統(tǒng)內(nèi)各種硬件和軟件資源， 有效地組織多道程序運行的系統(tǒng) 軟件（或程序集合） ，是用戶與計算機之間的接口。 引論 2 管態(tài) 當執(zhí)行操作系統(tǒng)程序時，處理機所處的狀態(tài) 3 目態(tài) 當執(zhí)行普通用戶程序時，處理機所處的狀態(tài)。 4 多道程序設(shè)計 在這種設(shè)計技術(shù)下，內(nèi)存中能同時存放多道程序，在管理程序的控制下交替的執(zhí)行。這些作 業(yè)共享 CPU 和系統(tǒng)中的其他資源。 5 并發(fā) 是指兩個或多個活動在同一給定的時間間隔中進行。它是宏觀上的概念。 6 并行 是指兩個或多個活動在同一時刻同時執(zhí)行的情況。 7 吞吐量 在一段給定的時間內(nèi)，計算機所能完成的總工作量。 8 分時 就是對時間的共享。在分時系統(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)星機專門負責完成 I/O，主機專門完成快速計 算任務(wù)，從而二者可以并行操作。 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)形成和發(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è)； 而多重處理系統(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）飛機的導航， （2）辦公自動化系統(tǒng)， （3）航空訂票系統(tǒng)， （4）復(fù)雜的科學計算， （5） 圖書檢索系統(tǒng) 答： （1）飛機的導航系統(tǒng)，應(yīng)采用硬實時操作系統(tǒng) （2）辦公自動化系統(tǒng)，應(yīng)采用分時操作系統(tǒng) （3）航空訂票系統(tǒng)，應(yīng)采用軟實時操作系統(tǒng) （4）復(fù)雜的科學計算，應(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)的方式，把處理機分 配給各進程使用。其主要特征是：交互性、多用戶同時性、獨立性。 9 什么是實時系統(tǒng)？它有什么特征？ 答：實時系統(tǒng)：在被控對象允許時間范圍內(nèi)做出響應(yīng) 。其主要特征是：對實時信息分析處 理速度要比進入系統(tǒng)快、要求安全可靠、資源利用率低。 10 什么是處理機的核心態(tài)和用戶態(tài)？為什么要設(shè)置這兩種不同的狀態(tài)？ 答：當執(zhí)行操作系統(tǒng)程序時，處理機處于核心態(tài)。它有較高的特權(quán)，可以執(zhí)行所有的指令， 包括一般用戶程序中不能使用的特權(quán)指令，從而能對所有寄存器和內(nèi)存進行訪問，啟動 i/o 操作等。 用戶程序是在用戶態(tài)下執(zhí)行，它的權(quán)限較低，只能執(zhí)行指令集中非特權(quán)指令。 分） （2 設(shè)置這兩種不同狀態(tài)的目的是為了保護操作系統(tǒng)程序（特別是其內(nèi)核部分） ，防止受到用戶 程序的損害。 11 系統(tǒng)調(diào)用與過程調(diào)用在功能及實現(xiàn)上有什么相同點和不同點？ 答：相同點：兩者都由程序代碼構(gòu)成，可直接用高級程序設(shè)計語言（如 C,C+和 Perl 語言） 來編制；使用方式相同以函數(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)生異 常事件。 實現(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í)行過程。 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 進程控制塊 進程控制塊是進程存在的唯一標識， 它保存了系統(tǒng)管理和控制進程所必須的信息， 是進程動 態(tài)特性的集中表現(xiàn)。 12 原語 指操作系統(tǒng)中實現(xiàn)一些具有特定功能的程序段， 這些程序段的執(zhí)行過程是不可分割的， 即其 執(zhí)行過程不允許被中斷。 13 就緒態(tài) 進程已經(jīng)獲得了除 cpu 之外的全部資源，等待系統(tǒng)分配 cpu，一旦獲得 cpu，進程就可以變 為運行態(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)是負責處理進程之間制約關(guān)系的機制， 即操作系統(tǒng)中負責解決進程之間協(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)的， 進程活動的主體是程序。 進程不能脫離開具體程序而獨立存 在。 2 有人說，一個進程是由偽處理機執(zhí)行的一個程序，這話對嗎？為什么？ 答：對。 因為偽處理機的概念只有在執(zhí)行時才存在， 它表示多個進程在單處理機上并發(fā)執(zhí)行的一 個調(diào)度單位。因此，盡管進程是動態(tài)概念，是程序的執(zhí)行過程，但是，在多個進程并行執(zhí)行 時，仍然只有一個進程占據(jù)處理機執(zhí)行，而其他并發(fā)進程則處于就緒或等待狀態(tài)。這些并發(fā) 進程就相當于由偽處理機執(zhí)行的程序。 3 試比較進程和程序的區(qū)別 答： （1）進程是一個動態(tài)的概念，而程序是一個靜態(tài)的概念，程序是指令的有序集合，無執(zhí) 行含義，進程則強調(diào)執(zhí)行的過程。 （2）進程具有并行特征（獨立性、異步性） ，程序則沒有。 （3）不同的進程可以包含同一個程序，同一程序在執(zhí)行中也可以產(chǎn)生多個進程。 4 進程的基本狀態(tài)有哪些？試描繪進程狀態(tài)轉(zhuǎn)換圖。 答：進程至少有三種基本狀態(tài)：運行狀態(tài)、就緒狀態(tài)和阻塞狀態(tài)（或等待狀態(tài)） 。進程狀 態(tài)轉(zhuǎn)換如下圖： 運行態(tài) 進程調(diào)度 時間片到 所需資源得到滿足 所需要的資源未被滿足 （如等待 I/O） 運行態(tài) （如 I/O 完成） 運行態(tài) 5 并發(fā)進程間的制約有哪兩種？引起制約的原因是什么？ 答：并發(fā)進程所受的制約有兩種：直接制約和間接制約。 直接制約是由并發(fā)進程相互共享對方的私有資源所引起的； 間接制約是由競爭共有資源而引 起的。 6 什么是進程間的互斥？什么是進程間同步？ 答：進程間的互斥是指：一組并發(fā)進程中的一個或多個程序段，因共享某一共有資源而導致 它們必須以一個不許交叉執(zhí)行的單位執(zhí)行， 即不允許兩個以上的共享該資源的并發(fā)進程同時 進入臨界區(qū)。 進程間的同步是指：異步環(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)象. 8 簡述信號量的定義和作用。P，V 操作原語是如何定義的？ 答：信號量一般是由兩個成員組成的數(shù)據(jù)結(jié)構(gòu)，其中一個成員是整型變量，表示該信號量的 值，它與相應(yīng)資源的使用情況有關(guān)；另一個是指向 PCB 的指針。當多個進程都等待同一信號 量時，它們就排成一個隊列，由信號量的指針項指出該隊列的隊首。 分） （2 信號量通?？梢院唵畏从吵鱿鄳?yīng)資源的使用情況，它與 P、V 操作原語一起使用可實現(xiàn) 進程的同步和互斥。 分） （1 P,V 操作原語有如下定義。 P(S)順序執(zhí)行下述兩個動作（1 分） ： 信號量的值減 1，即 S=S-1; 如果 S=0,則該進程繼續(xù)執(zhí)行。 如果 S0,則該進程繼續(xù)運行； 如果 SN begin V(S1); goto L; end /同方向過河的人站滿橋墩時,重新申請計數(shù) R=R+1; If R=1 P(S); /申請過河 V(S1); /釋放計數(shù)器的使用權(quán) (3) 占有一個橋墩,并順序過河到對岸; P(S1); R=R-1; If R=0 V(S); /如果已經(jīng)無同向的人過河,釋放占用權(quán) V(S1); (3) end. 7 在一個飛機訂票系統(tǒng)中，多個用戶共享一個數(shù)據(jù)庫。各用戶可以同時查詢信息，若有一個 用戶要訂票，須更新數(shù)據(jù)庫時，其余所有用戶都不可以訪問數(shù)據(jù)庫。請用 P,V 操作設(shè)計一個 同步算法，實現(xiàn)用戶查詢與訂票功能。要求：當一個用戶訂票而需要更新數(shù)據(jù)庫時，不能因 不斷有查詢者到來而使其長時間等待。利用信號量機制保證其正常執(zhí)行。 解：這是典型的讀者寫者問題，查詢信息的用戶是讀者，訂票用戶是寫者，并且要求寫 者優(yōu)先。(2) 變量說明：(2) 計數(shù)變量 rc正在運行的查詢者進程數(shù)目，初值為 0. 信號量 Sw控制訂票者進程的活動，初值為 1. Src互斥使用 rc 變量，初值為 1. S當訂票者到達時封鎖后續(xù)的讀進程，初值為 1. 讀者進程 P(S) P(Src) rc=rc+1 if (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) 更新數(shù)據(jù)庫內(nèi)容 V(Sw) V(S) 8 某車站售票廳，任何時刻最多可容納 20 名購票者進入，當售票廳中少于 20 名購票者時， 則廳外的購票者可立即進入，否則需在外面等待。若把一個購票者看作一個進程，請回答下 列問題： (1)用 PV 操作管理這些并發(fā)進程時，應(yīng)怎樣定義信號量，寫出信號量的初值以及信號量 各種取值的含義。 (2)根據(jù)所定義的信號量， 把應(yīng)執(zhí)行的 PV 操作填入下述空格中，以保證進程能夠正確地 并發(fā)執(zhí)行。 COBEGIN PROCESS PI(I=1，2，) begin 進入售票廳； 購票； 退出； end COEND (3)若欲購票者最多為 n 個人，寫出信號量可能的變化范圍(最大值和最小值)。 答：(1)定義一信號量 S，初始值為 20。 (1) 意義：(3=1*3) S0 S 的值表示可繼續(xù)進入售票廳的人數(shù) S=0 表示售票廳中已有 20 名顧客(購票者) S0 |S|的值為等待進入售票廳的人數(shù) (2)上空格為 P(S) (2) ；下空格為 V(S) (2) (3)S 的最大值為 20 (1 )；S 的最小值為 20n (1 ) 9 在公共汽車上，司機和售票員各行其職，司機負責開車和到站停車；售票員負責售票和開 門關(guān)門，當售票員關(guān)好車門后，駕駛員才能開車行使。試用 P/V 操作實現(xiàn)司機與售票員間 的同步。 解答：semaphore mutex1=0,mutex2=0; (2) main() cobegin driver() busman() coend (2) driver() while(true) p(mutex1) 啟動公共汽車 正常開車 到站停車 v(mutex2) (3) busman() while(true) 關(guān)車門 v(mutex1) 售票 p(mutex2) 開車門 上下乘客 (3) 10 并發(fā)問題：設(shè)有兩個優(yōu)先級相同的進程 p1, p2 如下。令信號 s1, s2 的初值為 0，已知 z=2， 試問 p1, p2 并發(fā)運行結(jié)束后 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）從結(jié)果來看，兩個進程無論誰先誰后，結(jié)果都是一樣的。(2) x = 5; y = 12; z = 9 (6) 11 試用信號量機制來描述下述前趨圖 M1 M5 M4 M2 M3 M7 M6 M8 解答：首先定義信號量 S12,S13,S14,S26,S36,S47,S57,S38,S78 的初值都為 0，分別表示相對 應(yīng)的進程是否完成：(2) COBEGIN (8=1*8) Process M1: begin V(S12) V(S13) V(S14) end Process M2: begin P(S12) V(26) end Process M3: begin P(S13) V(S36) V(S38) end Process M4: begin P(S14) V(S47) end Process M5: begin V(S57) end Process M6: begin P(S26) P(S36) end Process M7: begin P(S47) P(S57) P(S78) end Process M8: begin P(S38) P(S78) end COEND 12 試用信號量機制來描述下述前趨圖 M1 M3 M2 M4 M5 M6 解答：首先定義信號量 S12,S13,S24,S25,S56,S46,S36 的初值都為 0，分別表示相對應(yīng)的進程 是否完成(2)： COBEGIN (6=1*6) Process M1: begin V(S12) V(S13) end Process M2: begin P(S12) V(24) V(25) end Process M3: begin P(S13) V(S36) end Process M4: begin P(S14) V(S46) end Process M5: begin P(S25) V(S56) end Process M6: begin P(S36) P(S46) P(S56) end COEND 13 設(shè)系統(tǒng)有三個并發(fā)進程 R,C,P，共享一個能存放 n 個數(shù)據(jù)的環(huán)形緩沖區(qū) buf。進程 R 負責 從輸入設(shè)備上讀數(shù)據(jù)， 每讀一個后把它存放在緩沖區(qū) buf 的一個單元中； 進程 C 負責從緩沖 區(qū)讀數(shù)據(jù)并進行處理，之后將處理結(jié)果再送入緩沖區(qū)的一個單元中；進程 P 負責從緩沖區(qū) 讀進程 C 處理的結(jié)果并打印。請用 P、V 操作為三進程的正確執(zhí)行寫出同步算法。 解答：解決同步問題需設(shè)一個互斥信號量 mux，用于控制三個進程互斥使用緩沖區(qū)，初值為 1；再設(shè)三個同步信號量，用于控制對緩沖區(qū)的空閑數(shù)量和不同數(shù)據(jù)個數(shù)的記錄。S0 表示緩 沖區(qū)空閑個數(shù)，初值為 n；S1 表示緩沖區(qū)中輸入數(shù)據(jù)的個數(shù)，初值為 0；S2 表示緩沖區(qū)中 輸出數(shù)據(jù)的個數(shù)，初值為 0。(4) 算法描述如下：(6=2*3) 進程 R 進程 C 進程 P L1: L2: L3: P(S0) P(S1) 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ā)的事件而 無限期地僵持下去的局面。 2 饑餓 在系統(tǒng)中， 每個資源占有者都在有限時間內(nèi)釋放它所占有的資源， 但資源中存在某些申請者 由于某種原因卻永遠得不到資源的一種錯誤現(xiàn)象。 3 死鎖防止 要求進程申請資源時遵循某種協(xié)議， 從而打破產(chǎn)生死鎖的四個必要條件中的一個或幾個， 保 證系統(tǒng)不會進入死鎖狀態(tài)。 4 死鎖避免 對進程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查， 并根據(jù)檢查結(jié)果決定是否進行資源分 配。就是說，在資源分配過程中若預(yù)測有發(fā)生死鎖的可能性，則加以避免。這種方法的關(guān)鍵 是確定資源分配的安全性。 5 安全序列 針對當前分配狀態(tài)來說， 系統(tǒng)至少能夠按照某種次序為每個進程分配資源 （直至最大需求） ， 并且使他們依次成功地運行完畢，這種進程序列p1,p2,pn就是安全序列。 簡答題 1 計算機系統(tǒng)中產(chǎn)生死鎖的根本原因是什么?死鎖發(fā)生的四個基本條件是什么？ 答: 計算機系統(tǒng)中產(chǎn)生死鎖的根本原因是：資源有限且操作不當 。死鎖發(fā)生的四個基本條 件有互斥條件、請求保持條件（占有且等待條件） 、非剝奪條件（不可搶占條件）和環(huán)路條 件（循環(huán)等待條件） 。 2 簡述發(fā)生死鎖的四個必要條件? 答： 四個必要條件是：互斥條件、占有且等待條件（請求保持條件） 、不可搶占條件（非剝 奪條件）和循環(huán)等待條件（環(huán)路條件） 。 互斥條件某個資源在一段時間內(nèi)只能由一個進程占有， 不能同時被兩個及其以上的進程 占有。 占有且等待條件進程至少已經(jīng)占有一個資源，但又申請新的資源。 不可搶占條件一個進程所占有的資源再用完之前， 其他進程不能強行奪走資源， 只能由 該進程用完之后主動釋放。 循環(huán)等待條件存在一個進程等待序列P1,P2,Pn，其中，P1 等待 P2 所占有的某個 資源，P2 等待 P3 所占有的某個資源，而 Pn 等待 P1 所占有的某個資源，從而形成一 個進程循環(huán)等待。 3 什么是死鎖？解決死鎖的方法一般有那幾種? 答: 死鎖是指在一個進程集合中的每個進程都在等待僅由該集合中的另一個進程才能引發(fā) 的事件而無限期地僵持下去的局面。 解決死鎖問題的一般方法為：死鎖的預(yù)防、死鎖的避免、死鎖的檢測和恢復(fù)。 4 死鎖預(yù)防的基本思想是什么?死鎖避免的基本思想是什么? 答:死鎖預(yù)防的基本思想是:要求進程申請資源是遵循某種協(xié)議,從而打破產(chǎn)生思索的四個必 要條件中的一個或幾個,保證系統(tǒng)不會進入死鎖狀態(tài). 死鎖避免的基本思想是:對進程所發(fā)出的每一個申請資源命令加以動態(tài)地檢查,并根據(jù) 檢查結(jié)果決定是否進行資源分配.就是說,在資源分配過程中若預(yù)測有發(fā)生死鎖的可能性,則 加以避免.這種方法的關(guān)鍵是確定資源分配的安全性. 5 什么是死鎖的安全序列?何謂系統(tǒng)是安全的？ 答：進程的安全序列P1,P2,PN是這樣組成的：若對于每個進程 Pi（1=I=n） ，它需要的 附加資源可以被系統(tǒng)中當前可用資源加上所有進程 Pj（ji）當前占有資源之和所滿足，則 P1,P2,PN 為一個安全序列。 “系統(tǒng)是安全的” 是指系統(tǒng)中的所有進程能夠按照某種次序分配資源， 并且依次運行完 畢。即系統(tǒng)中的進程處于安全序列中。 6 資源按序分配法為什么能夠預(yù)防死鎖？ 證明：采用反證法來證明。 若存在循環(huán)等待， 設(shè)在環(huán)路上的一組進程為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) 顯然，這是不可能的，因而，上述假設(shè)不成立，表明不會出現(xiàn)循環(huán)等待條件。 7 死鎖和“饑餓”之間的主要差別是什么? 答：死鎖：多個并發(fā)進程相互等待對方占用的資源而產(chǎn)生的錯誤現(xiàn)象。 餓死：在系統(tǒng)中，由于系統(tǒng)采用的資源分配算法不當，雖然每個資源占有者都在有限時間內(nèi) 釋放它所占的資源，但仍然使一些進程永遠得不到資源的一種錯誤現(xiàn)象。 綜合題 1 設(shè)系統(tǒng)中有三種類型的資源（A,B,C）和五個進程（P1,P2,P3,P4,P5）,A 資源的數(shù)量為 17， B 資源的數(shù)量為 5，C 資源的數(shù)量為 20。在 T0 時刻系統(tǒng)狀態(tài)如表 3-9 所試。系統(tǒng)采用銀行 家算法來避免死鎖。 T0 時刻是否為安全狀態(tài)？若試，請給出安全序列。 在 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ù)量 A B C A B C A B C P1 5 5 9 2 1 2 2 3 3 P2 5 3 6 4 0 2 P3 4 0 11 4 0 5 P4 4 2 5 2 0 4 P5 4 2 4 3 1 4 解： T0 時刻是安全狀態(tài)，因為存在一個安全序列P4,P5,P1,P2,P3 (2) 不能實現(xiàn)資源分配，因為所剩余的資源數(shù)量不夠。 (2) 可以分配。當分配完成后，系統(tǒng)剩余的資源向量為（0，3，2） ，這時，仍可找到一個安全 序列P4,P5,P1,P2,P3 (3) 不能分配。如果分配的話，則系統(tǒng)剩余的資源向量為（0，1，2） ，這時無法找到一個安全 序列。(3) 2 在銀行家算法中，系統(tǒng)有 5 個進程和 3 個資源。若出現(xiàn)以下資源分配情況： 進程 資源最大請求 已分配資源 p0 7, 5, 3 0, 1, 0 p1 3, 2, 2 2, 1, 0 p2 9, 0, 2 3, 0, 2 p3 2, 2, 2 2, 1, 1 p4 4, 3, 3 0, 0, 2 系統(tǒng)剩余資源數(shù)量為(3,2,2)。 1） 該狀態(tài)是否安全(給出詳細的檢查過程)? 2） 如果進程依次有如下資源請求 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)就是不安全的.為此,可先求 出進程的剩余請求矩陣. 進程 資源最大需求 已分配資源 剩余資源請求 P0 7, 5, 3 0, 1, 0 7, 4, 3 P1 3, 2, 2 2, 1, 0 1, 1, 2 P2 9, 0, 2 3, 0, 2 6, 0, 0 P3 2, 2, 2 2, 1, 1 0, 1, 1 P4 4, 3, 3 0, 0, 2 4, 3, 1 系統(tǒng)剩余資源向量 A=(3,2,2)，在進程剩余資源請求矩陣中找，是否有一行，其值都小 于或等于 A.若有，選進程 P1，滿足它的全部資源請求，它在有限時間內(nèi)能釋放全部資源， 并標記它為完成使系統(tǒng)剩余資源向量 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). (2) p4:資源請求 Request(3,3,0)時，由于系統(tǒng)剩余資源向量 A=(2,2,0)，顯然不能滿足它的請求， 因為系統(tǒng)剩余資源向量 A 小于 P4 的請求 (2) p0:資源請求 Request(0,1,0)時，由于系統(tǒng)剩余資源向量 A=(2,2,0)，若滿足它的請求，使得系 統(tǒng)剩余資源向量 A=(2,1,0)。之后，系統(tǒng)仍可以找到一個進程完成序列 P1,P4,P0,P4,P2。故可 以滿足它的請求。 (2) 3 系統(tǒng)有同類資源 10 個，進程 p1、p2 和 p3 需要該類資源的最大數(shù)量分別為 8，6，7。它們 使用資源的次序和數(shù)量如下圖所示。 1） 試給出采用銀行家算法分配資源時，進行第 5 次分配后各進程的狀態(tài)及各進程占用資源 情況。 2） 在以后的申請中，那次的申請可以得到最先滿足?給出一個進程完成序列。 次序 進程 申請量 次序 進程 申請量 1 P1 3 5 P2 2 2 P2 2 6 P1 3 3 P3 4 7 P3 3 4 P1 2 8 P2 2 解：1）計算第 5 次分配后進程的狀態(tài)和占用資源情況：(5=1*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)的分配情況如下： p1 分配 5 個后正在運行，p2 分配 2 個后等待分配 2 個，p3 等待分配 4 個，系統(tǒng)還剩 3 個。 2）p1 接著運行，p1 申請 3 個可滿足(2)。P1 運行完成后，釋放資源，使系統(tǒng)的資源數(shù)量變 為 8 個。首先將 p3 喚醒，滿足它的 4 個資源，系統(tǒng)還剩 4 個，可以喚醒 p2，滿足它的 2 個 請求。系統(tǒng)還剩 2 個。 P3 申請 3 個，不能滿足，等待。 P2 申請 2 個，系統(tǒng)滿足它，p2 接著運行；p2 完成，釋放資源，使系統(tǒng)資源變?yōu)?6 個。 系統(tǒng)喚醒 p3，滿足它的資源請求，最終 p3 完成，釋放資源，使資源數(shù)量恢復(fù)為 10 個。 找到的進程完成序列為 p1,p2,p3。 (3) 4 設(shè)系統(tǒng)中有 150 個可用的同類資源。 在某時刻系統(tǒng)中的進程已獲得的資源和最大請求資源 如下所示，請用銀行家算法分別判斷完成下列請求時，系統(tǒng)是否安全？若安全，請給出進程 的完成序列。如不安全，請說明原因。 進程 最大需求量 當前已分配量 p1 70 25 p2 60 40 p3 60 45 p4 60 0 (1) 進程 p4 當前請求 25 個資源； (2) 之后 p4 又提出 35 個資源的請求。 解答：系統(tǒng)當前剩余資源量為：150 25 40 45 = 40 (2) (1) 可以滿足(2)，假定先分配 p4 的 25 個資源，系統(tǒng)還剩 15 個。將這 15 個資源可先分配 給 p3，p3 達到最大請求，釋放 60 個；之后可以分配給其他任何進程，系統(tǒng)中的進程都 能順利完成。由此可見，p2 請求的 25 個資源可以滿足，且能找到完成序列：p3，p1， p2，p4，(4) (2) 當 p4 再提出 35 個資源請求時，系統(tǒng)還剩 15，顯然不能滿足它的請求，讓其阻塞等待。 (2) 5 系統(tǒng)中有五個進程，分別為 p1p2p3p4p5，四類資源分別為 r1r2r3r4。某一時刻，系統(tǒng) 剩余資源向量 A=(1，2，3，0)。 （1） 用銀行家算法試判斷系統(tǒng)當前狀態(tài)是否安全？ （2） 當進程 p3 提出對資源 r3 的剩余請求時，能否滿足她？ （3） 系統(tǒng)初始配置的各類資源分別為多少？ 1 ?1 ? MAX = ?2 ? ?0 ?0 ? ?1 ?0 ? NEED = ?1 ? ?0 ?0 ? 2 1 2? 7 5 0? ? 3 5 6? ? 8 5 2? 6 3 6? ? 2 7 2 2 0? 0? ? 2? ? 0? 6 2 2? ? 0 5 1 2 0 ?1 ? ， ?1 ? ?0 ?0 ? 0 1 2? 0 0 0? ? 1 4 4? ? 6 3 2? 0 1 4? ? . 解答：系統(tǒng)剩余資源向量 A=(1, 2, 3, 0) ?，F(xiàn)在需求出各進程的剩余資源請求矩陣: (2) (1) 詳細步驟省略。由于系統(tǒng)存在一個進程完成的安全序列 P1P3P4P2P5(2)，故系統(tǒng)狀態(tài) 是安全的(2)。 (2) 進程 P3 提出對資源 R3 的剩余請求為 1，由于系統(tǒng)剩余資源向量 A=(1,2, 3, 0)，故可以 假定分配給它。如果能找到一個安全序列，就可以真正進行分配。當分配給 P3 一個資 源時，系統(tǒng)剩余資源向量 A=(1 ,2 ,2 , 0)。由此可見，仍然可以找到一個與(1)相同的安全 序列。故可以滿足 P3 的請求。(3) (3) 系統(tǒng)初始配置的各類資源分別為(3 ,9 , 12 , 12 )。(1) 第四章 調(diào)度 名詞解釋 1 作業(yè) 用戶在一次上機過程中要求計算機系統(tǒng)所做工作的集合。 2 周轉(zhuǎn)時間 是指從作業(yè)進入系統(tǒng)開始，到作業(yè)退出系統(tǒng)所經(jīng)歷的時間。 3 響應(yīng)時間 是分時系統(tǒng)的一個技術(shù)指標，指從用戶輸入命令到系統(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í)行。引入交換調(diào)度 的目的是為了解決主存緊張和提高主存的利用效率。 7 剝奪式調(diào)度 當一個進程正在執(zhí)行時， 系統(tǒng)基于某種策略強行將處理機從占有者進程剝奪而分配給另一個 進程的調(diào)度。