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

1、第六章：設(shè)備管理4假設(shè)一個磁盤由200個磁道，編號從0199。當前磁頭正在143道上服務(wù)，并且剛剛完成了125道的請求。如果尋道請求隊列的順序是：86，147，91，177，94，150，102，175，130 問：為完成上述請求，下列算法各自磁頭移動的總量是多少？ FCFS SSTF 解：FCFS磁頭移動順序:143 86 147 91 177 94 150 102 175 130 (2) 57 61 56 86 83 56 48 73 45磁頭移動總量: 57+61+56+86+83+56+48+73+45=565 (3)SSTF磁頭移動順序143 147 150 130 102 94 9

2、1 86 175 177 (2) 4 3 20 28 8 3 5 89 2磁頭移動總量: 4+3+20+28+8+3+5+89+2=162 ( 3)5什么是I/O控制？,I/O操作的四種控制方式是什么？答：I/O控制是指從用戶進程的輸入/輸出請求開始，給用戶進程分配設(shè)備和啟動有關(guān)設(shè)備進行I/O操作，并在I/O操作完成之后響應(yīng)中斷,直至善后處理為止的整個系統(tǒng)控制過程 。I/O操作的四種控制方式分別是：程序直接控制方式、中斷I/O控制方式、DMA控制方式、I/O通道控制方式 。第四章：進程的同步互斥和死鎖1計算機系統(tǒng)中產(chǎn)生死鎖的根本原因是什么?死鎖發(fā)生的四個基本條件是什么？答: 計算機系統(tǒng)中產(chǎn)生死

3、鎖的根本原因是：資源有限且操作不當 。死鎖發(fā)生的四個基本條件有互斥條件、請求保持條件（占有且等待條件）、非剝奪條件（不可搶占條件）和環(huán)路條件（循環(huán)等待條件） 。2簡述發(fā)生死鎖的四個必要條件?答： 四個必要條件是：互斥條件、占有且等待條件（請求保持條件）、不可搶占條件（非剝奪條件）和循環(huán)等待條件（環(huán)路條件）。 互斥條件某個資源在一段時間內(nèi)只能由一個進程占有，不能同時被兩個及其以上的進程占有。 占有且等待條件進程至少已經(jīng)占有一個資源，但又申請新的資源。 不可搶占條件一個進程所占有的資源再用完之前，其他進程不能強行奪走資源，只能由該進程用完之后主動釋放。 循環(huán)等待條件存在一個進程等待序列P1,P2,

4、Pn，其中，P1等待P2所占有的某個資源，P2等待P3所占有的某個資源，而Pn等待P1所占有的某個資源，從而形成一個進程循環(huá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)資源分配？為什么?

5、表3-9 T0時刻系統(tǒng)狀態(tài)進程最大資源需求量已分配資源數(shù)量系統(tǒng)剩余資源數(shù)量 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時刻是安全狀態(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），這時無法找到一個安全

6、序列。(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)是否安全(給出詳細的檢查過程)?2） 如果進程依次有如下資源請求p1:資源請求Request(1,0,2)?p4:資源請求Request(3,3,0)?p0:資源請求Request(0,1,0)?則系統(tǒng)如何進行資源分配，才能避免死鎖？解:1)該系統(tǒng)狀態(tài)是否安全,主要看能否找到一個進程完成

7、序列.若能找到,系統(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, 10, 1, 1P44, 3, 30, 0, 24, 3, 1系統(tǒng)剩余資源向量A=(3,2,2)，在進程剩余資源請求矩陣中找，是否有一行，其值都小于或等于A.若有，選進程P1，滿足它的全部資源請求，它在有限時間內(nèi)能釋放全部資源，并標記它為完成使系統(tǒng)剩余

8、資源向量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=

9、(2,1,0)。之后，系統(tǒng)仍可以找到一個進程完成序列P1,P4,P0,P4,P2。故可以滿足它的請求。 (2)第七章：文件操作系統(tǒng)1什么是文件、文件系統(tǒng)？文件系統(tǒng)有哪些功能？答：在計算機系統(tǒng)中，文件被解釋為一組賦名的相關(guān)字符流的集合，或者是相關(guān)記錄的集合。文件系統(tǒng)是操作系統(tǒng)中與管理文件有關(guān)的軟件和數(shù)據(jù)。文件系統(tǒng)的功能是為用戶建立文件，撤銷、讀寫修改和復(fù)制文件，以及完成對文件的按名存取和進行存取控制。3什么是文件的邏輯結(jié)構(gòu)，什么是記錄？答：文件的邏輯結(jié)構(gòu)就是用戶可見的結(jié)構(gòu)，可分為字符流式的無結(jié)構(gòu)文件和記錄式的有結(jié)構(gòu)文件兩大類。 記錄是一個具有特定意義的信息單位，它由該記錄在文件中的邏輯地址（相對

10、位置）與記錄名所對應(yīng)的一組關(guān)鍵字，屬性及其屬性值所組成。5文件系統(tǒng)中目錄結(jié)構(gòu)主要有哪幾種？分別說明各自的實現(xiàn)思想？答：文件系統(tǒng)中的目錄結(jié)構(gòu)主要有：單級目錄結(jié)構(gòu)，二級目錄結(jié)構(gòu)，樹形目錄結(jié)構(gòu)和非循環(huán)圖目錄結(jié)構(gòu)。 單級目錄結(jié)構(gòu)在這種組織方式下，全部文件都登記在同一目錄中。 二級目錄結(jié)構(gòu)在主文件目錄中登載了各個用戶的名稱，每個用戶有自己的用戶文件目錄。 樹形目錄結(jié)構(gòu)在這種結(jié)構(gòu)中，只有一個根目錄，每一級目錄可以是下級目錄的說明，也可以是包含文件的說明。從根開始一層一層地擴展下去，就形成一個樹形層次結(jié)構(gòu)。 非循環(huán)圖目錄結(jié)構(gòu)樹形目錄結(jié)構(gòu)的自然推廣就是非循環(huán)圖目錄結(jié)構(gòu)，它允許一個文件或目錄可在多個父目錄中占有

11、項目，但并不構(gòu)成環(huán)路 第1章 ：緒論1操作系統(tǒng)操作系統(tǒng)是管理和控制計算機系統(tǒng)內(nèi)各種硬件和軟件資源，有效地組織多道程序運行的系統(tǒng)軟件（或程序集合），是用戶與計算機之間的接口。4多道程序設(shè)計在這種設(shè)計技術(shù)下，內(nèi)存中能同時存放多道程序，在管理程序的控制下交替的執(zhí)行。這些作業(yè)共享CPU和系統(tǒng)中的其他資源。5并發(fā)是指兩個或多個活動在同一給定的時間間隔中進行。它是宏觀上的概念。6并行是指兩個或多個活動在同一時刻同時執(zhí)行的情況。8分時就是對時間的共享。在分時系統(tǒng)中，分時主要是指若干并發(fā)程序?qū)PU時間的共享。9實時表示“及時”或“既時”。10系統(tǒng)調(diào)用是用戶在程序中能以“函數(shù)調(diào)用”形式調(diào)用的、由操作系統(tǒng)提供的

12、子功能的集合。每一個子功能稱作一條系統(tǒng)調(diào)用命令。它是操作系統(tǒng)對外的接口，是用戶級程序取得操作系統(tǒng)服務(wù)的唯一途徑。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ā)展的主要動力是什么

13、？答：推動操作系統(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ā)、共享。第5章 ：存儲管理1物理地址內(nèi)存中各存儲單元的地址由統(tǒng)一的基地址順序編址，這種地址稱為物理地址。2邏輯地址用戶程序經(jīng)編譯之后的每個目標模塊都以0為基地址順序編址，這種地址稱為邏輯地址。3邏輯地址空間由程序中邏輯地址組成的地址范圍叫做邏輯地址空間。4物理地址空間由內(nèi)存中的一系列存儲單元所限定的地址范圍稱

14、作內(nèi)存空間。5 連續(xù)空間分配包括：單道連續(xù)分配 多道固定分區(qū)法 多道連續(xù)可變分區(qū)法8內(nèi)部碎片在一個分區(qū)內(nèi)部出現(xiàn)的碎片（即被浪費的空間）稱作內(nèi)部碎片。如固定分區(qū)法會產(chǎn)生內(nèi)部碎片。9外部碎片在所有分區(qū)之外新產(chǎn)生的碎片稱作外部碎片，如在動態(tài)分區(qū)法實施過程中出現(xiàn)的越來越多的小空閑塊，由于它們太小，無法裝入一個小進程，因而被浪費掉。10碎片在分區(qū)法中，內(nèi)存出現(xiàn)許多容量太小、無法被利用的小分區(qū)稱作“碎片”。17抖動頁面抖動是系統(tǒng)中頻繁進行頁面置換的現(xiàn)象。即如果一個進程沒有一定數(shù)量的內(nèi)存塊，它很快就發(fā)生缺頁。此時，它必須淘汰某頁。由于所有這些頁面都正在使用，所以剛被淘汰出去的頁很快又被訪問，因而要把它重新調(diào)

15、入?？墒钦{(diào)入不久又再被淘汰出去，這樣再訪問，再調(diào)入，如此反復(fù)，使得整個系統(tǒng)的頁面替換非常頻繁，以致大部分機器時間都用在來回進行的頁面調(diào)度上，只有一小部分時間用于進程的實際運算方面。12什么是頁面抖動？系統(tǒng)怎樣檢測是否出現(xiàn)抖動？一旦檢測到抖動？系統(tǒng)如何消除它？答：頁面抖動是系統(tǒng)頻繁進行頁面置換的現(xiàn)象。整個系統(tǒng)的頁面替換非常頻繁，以致大部分機器時間都用在來回進行的頁面調(diào)度上，只有一小部分時間用于進程的實際運算方面。 操作系統(tǒng)監(jiān)督每個進程的工作集，并給它分配工作集所需的內(nèi)存塊。若有足夠多的額外塊，就可以裝入并啟動另外的進程。如果工作集增大了，超出可用塊的總數(shù)，即系統(tǒng)中全部進程對內(nèi)存塊的總請求量大于可

16、用內(nèi)存塊的總量，將出現(xiàn)抖動，因為某些進程得不到足夠的內(nèi)存塊。 一旦檢測到抖動，操作系統(tǒng)要選擇一個進程讓它掛起，把它的頁面寫出去，把它占用的內(nèi)存塊分給別的進程。被掛起的進程將在以后適當時機重新開始執(zhí)行。頁面替換策略例題：（駐留集固定的替換策略） 1 FIFO：先進先出 伴隨belady現(xiàn)象； 2 OPT：是最優(yōu)策略；淘汰下次訪問距離當前最遠的那些頁中序號最小的一頁 3 LRU：淘汰上次使用距離當前最遠的頁1考慮下面頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6 當內(nèi)存塊數(shù)量分別為3時，試問LRU,FIFO,OPT三種置換算法的缺頁次數(shù)各是多少？（注意，所

17、有內(nèi)存最初都是空的，凡第1次用到的頁面都產(chǎn)生一次缺頁）答：LRU12342156212376321236111444555111777222222222111222226661116333336666333333333(2)FIFO12342156212376321236111444466663333222262222111222277771111333355511116666633(2)OPT12342156212376321236111111111113333333332222222222277722222344456666666661116 (2)內(nèi)存塊數(shù)置換算法FIFOLRUOPT31

18、61511 (3)2考慮下面存儲訪問序列，該程序大小為460字：10，11，104，170，73，309，185，245，246，434，458，364 設(shè)頁面大小是100字，請給出該訪問序列的頁面走向。又設(shè)該程序基本可用內(nèi)存是200字，采用FIFO置換算法，求出缺頁率。如果采用LRU算法，缺頁率是多少？如果采用最優(yōu)淘汰算法，其缺頁率又是多少？解: 該序列的頁面走向為：0、1、0、3、1、2、4、3。 (1)FIFO01031243000333421111223 (2)LRU01031243000011441133223 (2)OPT01031243000333331111244(2)算法FI

19、FOLRUOPT缺頁次數(shù)675缺頁率6/12=0.57/12=0.5835/12=0.417 (3)第3章 ：進程與處理機管理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的工作。4處理機調(diào)度一般分為哪三級？其中哪

20、一級調(diào)度必不可少？為什么？答：處理機調(diào)度一般可分為高級調(diào)度（作業(yè)調(diào)度）、中級調(diào)度和低級調(diào)度（進程調(diào)度） 。其中進程調(diào)度必不可少 。 進程只有在得到CPU之后才能真正活動起來，所有就緒進程經(jīng)由進程調(diào)度才能獲得CPU的控制權(quán)。實際上，進程調(diào)度完成一臺物理的CPU轉(zhuǎn)變成多臺虛擬機（或邏輯）的CPU的工作，進程調(diào)度的實現(xiàn)策略往往決定了操作系統(tǒng)的類型，其算法優(yōu)劣直接影響整個系統(tǒng)的性能。 5作業(yè)調(diào)度與進程調(diào)度之間有什么差別？二者間如何協(xié)調(diào)工作？答：作業(yè)調(diào)度與進程調(diào)度之間的差別主要是：作業(yè)調(diào)度是宏觀調(diào)度，它所選擇的作業(yè)只是具有獲得處理機的資格，但尚未占有處理機，不能立即在其上實際運行；而進程調(diào)度是微觀調(diào)度，

21、動態(tài)地把處理機實際地分配給所選擇的進程，使之真正活動起來。另外，進程調(diào)度相當頻繁，而作業(yè)調(diào)度執(zhí)行的次數(shù)一般很少。 作業(yè)調(diào)度從外存的后背隊列中選擇一批作業(yè)調(diào)入內(nèi)存，為它們創(chuàng)建進程，這些進程被送入就緒隊列。進程調(diào)度從就緒隊列中選出一個進程來，并把它的狀態(tài)改為運行態(tài)，把cpu分配給它。當運行進程要等待某一事件時，就讓出cpu，進入相應(yīng)的阻塞隊列，并進行進程調(diào)度。運行進程完成后，由作業(yè)調(diào)度進行善后處理工作。 6：進程的三狀態(tài)模型：進程的創(chuàng)建和結(jié)束。進程的狀態(tài)變化模型。進程的掛起。調(diào)度算法：2先來先服務(wù)算法：按照進程進入就緒隊列的先后次序進行選擇3優(yōu)先級調(diào)度算法： 根據(jù)優(yōu)先級大小來調(diào)度4時間片輪轉(zhuǎn)算法：

22、 5短進程優(yōu)先調(diào)度算法： 挑選所需運行時間最短的進程先進行 6最短剩余時間優(yōu)先調(diào)度算法： 讓 進程運行到完成所用時最短的進程 優(yōu)先7最高響應(yīng)比優(yōu)先調(diào)度算法： 響應(yīng)比作業(yè)響應(yīng)時間作業(yè)執(zhí)行時間 =(作業(yè)執(zhí)行時間+作業(yè)等待時間)作業(yè)執(zhí)行時間 =1+作業(yè)等待時間作業(yè)執(zhí)行時間 哪個高就優(yōu)先哪個 1假定在單CPU條件下要執(zhí)行的作業(yè)如下表所示。表 作業(yè)列表作 業(yè)運 行 時 間優(yōu) 先 級1103211323414552作業(yè)到來的時間是按作業(yè)編號順序進行的（即后面作業(yè)依次比前一個作業(yè)遲到一個時間單位）。用一個執(zhí)行時間圖描述使用非搶占式優(yōu)先級算法時各自執(zhí)行這些作業(yè)的情況：對于該算法，各個作業(yè)的周轉(zhuǎn)時間是多少?平均

23、周轉(zhuǎn)時間是多少？對于該算法，各個作業(yè)的帶權(quán)周轉(zhuǎn)時間是多少？平均帶權(quán)周轉(zhuǎn)時間是多少？解：非搶占式優(yōu)先級 J1 J4 J3 J5 J20 10 11 13 18 19(3)和非搶占式優(yōu)先級 (7=1*7)JOBtstrteTWJ101010101J211191818J32213115.5J4311188.0J54518142.8 12.2 2.062在一個有兩道作業(yè)的批處理系統(tǒng)中，作業(yè)調(diào)度采用短作業(yè)優(yōu)先級調(diào)度算法，進程調(diào)度采用搶占式優(yōu)先級調(diào)度算法。設(shè)作業(yè)序列如表4-9所示。表4-9 作業(yè)列表作業(yè)名到達時間預(yù)估計時間（分鐘）優(yōu)先數(shù)A8:004010B8:20305C8:30508D8:502012其

24、中給出的作業(yè)優(yōu)先數(shù)即為相應(yīng)進程的優(yōu)先數(shù)。其數(shù)值越小，優(yōu)先級越高。要求：列出所有作業(yè)進入內(nèi)存的時間及結(jié)束時間。計算平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間。解：D C B A8:00 8:20 8:30 8:50 9:10 10:00 10:20(4) (6=1*6)JOBtstsrteTA8:008:009:1070B8:208:208:5030C8:309:1010:0090D8:508:5010:2090702.26253有A、B、C、D、E，共5個待運行作業(yè)，各自估計的運行時間為9，6，3，5，x。試問采用哪種運行次序使得平均響應(yīng)時間為最短？（答案依賴于x）解答：由于短作業(yè)優(yōu)先調(diào)度算法可以使作業(yè)的

25、平均周轉(zhuǎn)時間最短，同樣使作業(yè)的平均響應(yīng)時間為最短。 (5) 下面對x的取值進行討論：(5=1*5) 當0x=3時，作業(yè)的運行順序應(yīng)為E(x),C(3),D(5),B(6),A(9); 當3x5時，作業(yè)的運行順序應(yīng)為C(3),E(x),D(5),B(6),A(9); 當5=x=6時，作業(yè)的運行順序應(yīng)為C(3),D(5),E(x),B(6),A(9); 當6x9，作業(yè)的運行順序應(yīng)為C(3),D(5),B(6),A(9),E(x)4有一個具有如下作業(yè)流的批處理處理系統(tǒng)，作業(yè)調(diào)度采用短作業(yè)優(yōu)先，進程調(diào)度采用基于優(yōu)先數(shù)的搶先式調(diào)度算法。下表給出的是作業(yè)序列和相應(yīng)進程的優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。 作業(yè)

26、名 到達時間 估計運行時間/min 優(yōu)先數(shù) 1 8:00 40 4 2 8:20 30 2 3 8:30 50 3 4 8:50 20 5(1) 列出所有作業(yè)進入內(nèi)存時間及完成時間(2) 計算作業(yè)的平均周轉(zhuǎn)時間和平均帶權(quán)周轉(zhuǎn)時間解答：(1)作業(yè)進入內(nèi)存時間與結(jié)束時間如下所示：(4=1*4) 作業(yè)名 進入內(nèi)存時間 結(jié)束時間 1 8:00 9:10 2 8:20 8:50 3 9:10 10:00 4 8:50 10:20 (2)各作業(yè)的周轉(zhuǎn)時間為： (4=1*4)作業(yè)A：9:10 8:00 = 70 min作業(yè)B：8:50 8:20 = 30 min作業(yè)C：10:00 8:30 = 90 min作業(yè)D：10:20 8:50 = 90