操作系統(tǒng)：08級總復(fù)習(xí)

1、l 操作系統(tǒng)中引入多道程序設(shè)計的好處一是提高了CPU的利用率， 二是提高了內(nèi)存和I/O設(shè)備的利用率， 三是改進了系統(tǒng)的吞吐率， 四是充分發(fā)揮了系統(tǒng)的并行性。 其主要缺點是:作業(yè)周轉(zhuǎn)時間延長。l 試從獨立性、多路性、交互性和及時性等方面比較批處理系統(tǒng)、分時系統(tǒng)、實時系統(tǒng)，并分別說明它們各自適用于什么場合？l 分布式操作系統(tǒng)系統(tǒng)中的若干臺機器可互相協(xié)作完成同一個任務(wù)，具有較好的容錯性和健壯性第二章 了解第三章l 進程和程序是兩個既有聯(lián)系又有區(qū)別的概念：(1) 進程是一個動態(tài)概念，而程序則是一個靜態(tài)概念。(2) 進程具有并行特征，而程序沒有。由進程的定義可知，進程具有并行特征的兩個方面，即獨立性和異

2、步性。 (3) 進程是分配計算機系統(tǒng)資源的基本單位。(4) 不同的進程可以包含同一程序，只要該程序所對應(yīng)的數(shù)據(jù)集不同。l 作業(yè)和進程的關(guān)系(1) 作業(yè)是用戶向計算機提交任務(wù)的任務(wù)實體。作業(yè)在外存中的作業(yè)等待隊列中等待執(zhí)行。而進程則是完成用戶任務(wù)的執(zhí)行實體，是向系統(tǒng)申請分配資源的基本單位。進程在于內(nèi)存中。(2) 一個作業(yè)可由多個進程組成。且必須至少由一個進程組成，但反過來不成立。(3) 作業(yè)的概念主要用在批處理系統(tǒng)中。而進程的概念則用在幾乎所有的多道系統(tǒng)中。l 把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。l 用于進程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等。應(yīng)用題2應(yīng)用題1第

3、4章 處理機調(diào)度l 衡量調(diào)度策略的最常用的幾個指標是：周轉(zhuǎn)時間、吞吐率、響應(yīng)時間以及設(shè)備利用率等。l 周轉(zhuǎn)時間是指將一個作業(yè)提交給計算機系統(tǒng)后到該作業(yè)的結(jié)果返回給用戶所需要的時間。l 吞吐率是指在給定的時間內(nèi)，一個計算機系統(tǒng)所完成的總工作量。l 響應(yīng)時間則是指從用戶向計算機發(fā)出一個命令到計算機把相應(yīng)的執(zhí)行結(jié)果返回給用戶所需要的時間。l 設(shè)備利用率主要指輸入輸出設(shè)備的使用情況。l 要求熟悉常用的作業(yè)調(diào)度和進程調(diào)度算法.作業(yè)調(diào)度:1.先來先服務(wù)應(yīng)用題32.計算時間短的作業(yè)優(yōu)先算法3.響應(yīng)比高者優(yōu)先算法 響應(yīng)比=等待時間/計算時間+14.優(yōu)先級調(diào)度算法5.均衡調(diào)度算法作業(yè)調(diào)度輪流從不同類的作業(yè)中去挑

4、選作業(yè)，盡可能地使得使用不同資源的作業(yè)同時執(zhí)行。第5章 存儲管理應(yīng)用題4應(yīng)用題5-7l 覆蓋與交換技術(shù)l 抖動(thrashing)現(xiàn)象。l Belady現(xiàn)象l 理想型淘汰算法OPTl 頁式管理的優(yōu)缺點l 段式與段頁式管理段式管理的基本思想是: 把程序按內(nèi)容或過程(函數(shù))關(guān)系分成段，每段有自己的名字。一個用戶作業(yè)或進程所包含的段對應(yīng)于一個二維線性虛擬空間，也就是一個二維虛擬存儲器。工作集-“在未來的時間間隔 內(nèi)，一個進程運行時所需訪 問的頁面集”。第8章 文件系統(tǒng)應(yīng)用題8-9設(shè)備管理 : 設(shè) 備 分 配了解圖8.13 設(shè)備分配流程圖數(shù)據(jù)傳送控制方式緩沖的種類根據(jù)系統(tǒng)設(shè)置的緩沖器的個數(shù)，可把緩沖

5、技術(shù)分為單緩沖、雙緩沖和多緩沖以及緩沖池幾種。習(xí)題:一、設(shè)進程A和進程B, 它們都要求進入臨界區(qū)CS, 下面的設(shè)計就可以滿足進程的互斥要求: 進程B: P（S）; CS2; V（S）; coend S1; /* 定義信號量并確定初值*/ cobegin進程A: P（S）; CS1; V（S）; 二、生產(chǎn)者和消費者Begin SP,SG:semaphore； mutex：semaphore； SP：=1： SG:=0； mutex：=1： cobegin producer； consumer； coend Procedure producer；begin while true do begin

6、produce next product； P(SP)； P(mutex)； put a product； v(mutex)； v (SG)； endendprocedure consumer； 消費者進程 begin while true do begin p(SG) 查緩沖區(qū)足否已有新的產(chǎn)品 P(mutex)； 能否使用臨界資源：緩沖區(qū) take a product 取產(chǎn)品 V(mutex) 釋放緩沖區(qū)資源 V(SP )； 通知生產(chǎn)者已取走產(chǎn)品 comsume the product 消費產(chǎn)品 end end；三、同步互斥混合假設(shè)有一個成品倉庫，總共能存放8臺成品，生產(chǎn)者進程生產(chǎn)產(chǎn)品放入倉

7、庫，消費者進程從倉庫中取出成品消費。為了防止積壓，倉庫滿的時候就停止生產(chǎn)。由于倉庫搬運設(shè)備只有一套，故成品的存入和取出只能分別執(zhí)行，使用PV操作來實現(xiàn)該方案。答案:S:信號量,倉庫能放產(chǎn)品的個數(shù),初值=8S1: 信號量,用于互斥,初值=1S2: 信號量,倉庫現(xiàn)有產(chǎn)品的個數(shù),初值=0Process producerP(S)生產(chǎn)產(chǎn)品P(S1)放入倉庫V(S1)V(S2)Process consumerP(S2)P(S1)取出成品消費V(S1)V(S)返回應(yīng)用題2設(shè)當前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時Availableffi(0，1，1)： Claim Allocation need進程 R1 R2 R3

8、Rl R2 R3 Rl R2 R3 P1 3 2 2 1 0 0 3 2 2 P2 6 1 3 6 1 2 0 0 1 P3 3 l 4 2 1 1 1 0 3 P4 4 2 2 0 0 24 2 0(1)計算各個進程還需要的資源數(shù)(2)系統(tǒng)是否處于安全狀態(tài)，為什么?執(zhí)行順序：p2,執(zhí)行完資源個數(shù)：1，1，2+5，1，1=6，2，3P3,執(zhí)行完資源個數(shù)：6,2,3+2,1,1=8,3,4P4,執(zhí)行完資源個數(shù)：P1,執(zhí)行完資源個數(shù)：執(zhí)行完畢，說明系統(tǒng)安全(3)P2發(fā)出請求向量request2(1，0，1)，系統(tǒng)能把資源分給它嗎?答：(1)P1，P2，P3，P4為：(2，2，2)、(1，0，2)、

9、(4，2,0) (2)系統(tǒng)處于安全狀態(tài)，存在安全序列：P2，Pl，P3，P4 (3)可以分配，存在安全序列：P2，Pl，P3，P4。返回應(yīng)用題31.設(shè)有四道作業(yè)，它們進入系統(tǒng)的時間及需要執(zhí)行的時間如下表所示，并規(guī)定當?shù)谝粋€作業(yè)進入系統(tǒng)后立即調(diào)度，忽略調(diào)度的時間開銷。表列出了A、B、C和D共4個作業(yè)到達系統(tǒng)的時間、運行時間、開始時間及各自完成的時間，采用FCFS算法，計算各自的周轉(zhuǎn)時間和帶權(quán)周轉(zhuǎn)時間和等待時間，分析結(jié)果可以得出什么結(jié)論？ 作業(yè)號進入系統(tǒng)時間需執(zhí)行時間（分鐘）開始時間完成時間周轉(zhuǎn)時間190070294030395010410105要求：分別采用先來先服務(wù)和最短執(zhí)行時間優(yōu)先調(diào)度算法時

10、的調(diào)度次序和作業(yè)平均周轉(zhuǎn)時間。答案:先來先服務(wù): 調(diào)度次序1234作業(yè)號進入系統(tǒng)時間需執(zhí)行時間（分鐘）開始時間完成時間周轉(zhuǎn)時間1900709:0010:107029403010:1010:406039501010:4010:506041010510:5010:5545作業(yè)平均周轉(zhuǎn)時間(70+60+60+45)/4=58.75最短執(zhí)行時間優(yōu)先: 調(diào)度次序1432作業(yè)號進入系統(tǒng)時間需執(zhí)行時間（分鐘）開始時間完成時間周轉(zhuǎn)時間1900709:0010:107029403010:2510:557539501010:1510:253541010510:1010:155作業(yè)平均周轉(zhuǎn)時間(70+75+35+5

11、)/4=46.25結(jié)論:最短執(zhí)行時間優(yōu)先比先來先服務(wù)效率高.2. 有一多道程序設(shè)計系統(tǒng)，采用不允許移動的可變分區(qū)式管理主存空間，設(shè)主存空間為100KB，采用最先適應(yīng)分配算法分配主存，作業(yè)調(diào)度和進程調(diào)度均采用先來先服務(wù)算法，今有如下作業(yè)序列，計算作業(yè)的平均周轉(zhuǎn)時間。 10.1 1后備就緒CPU 10.4結(jié)束10.3 2就緒10.4 1結(jié)束 2CPU 10.8結(jié)束10.5 3后備10.6 4就緒10.7 5-就緒執(zhí)行順序: 1-245-3作業(yè)提交運行開始結(jié)束周轉(zhuǎn)110.10.310.110.40.3210.30.510.410.90.6310.50.411.511.91.4410.60.410.9

12、11.30.7510.70.211.311.50.8平均周轉(zhuǎn)時間=0.76返回應(yīng)用題4在可變分區(qū)管理下，假定內(nèi)存中按地址順序，依次有5個空閑區(qū)，空閑區(qū)的大小分別為32K，10K，5K，228K，100K現(xiàn)有5個作業(yè)J1，J2，J3，J4，J5它們各需要內(nèi)存1K，10K，108K，28K，115K若采用FF算法，能將這5個作業(yè)按J1，J2，J3，J4，J5的順序全部裝入內(nèi)存嗎?你認為按怎樣的次序裝入這5個作業(yè)可使內(nèi)存利用率最高?解：按FF算法，空閑分區(qū)表情況如表A-3所示，作業(yè)J5沒有裝入內(nèi)存。表A-3分配后的空閑分區(qū)表(BF)分區(qū)號大小 1 21K 2 10K 3 5K 4 92K 5 100

13、K BF算法要求空閑分區(qū)按大小遞增的次序排列，在進行內(nèi)存分配時，總是從空閑分區(qū)表首開始查找一個能滿足其大小要求的最小空閑分區(qū)。 BF算法，空閑分區(qū)表情況如表A-4所示，5個作業(yè)J1。J2，J3，J4，J5全部裝入內(nèi)存。 表A-4分配后的空閑分區(qū)表(BF)分區(qū)號大小 1 32K 2 0K 3 4K 4 5K 5 100K WF算法要求空閑分區(qū)按大小遞減的次序排列，在進行內(nèi)存分配時，總是從空閑分區(qū)表首開始查找一個能滿足其大小要求的最大空閑分區(qū)。 按WF算法，空閑分區(qū)表情況如表A-5所示(略)，作業(yè)J5沒有裝入內(nèi)存。分區(qū)號大小 1 32K 2 10K 3 5K 4 81K 5 100K返回應(yīng)用題5分

14、頁式存儲空間的分配由于塊的大小是固定的，可以用一張位示圖(Bit map)來構(gòu)成主存分配表。現(xiàn)設(shè)主存有8192塊，可用字長為32位的256個字作為位示圖。若塊號，字號，位號(從高位到低位)分別從1、0、0開始，試問5999塊對應(yīng)的字號和位號?99字的19位對應(yīng)哪一塊? 答：187字14位 6388塊 應(yīng)用題6一個由3個頁面(頁號為0、l、2)每頁有2048個字節(jié)組成的程序每把它裝入一個由8 個物理塊(塊號為0、l、2、3、4、5、6、7)組成的存儲器中，裝入情況如下表： 給出下列邏輯地址，請根據(jù)頁表計算出對應(yīng)的絕對地址。 (1)100 (2)2617 (3)5196頁號塊號021523答案:

15、(1)2*2048+100=4196 (2)5*2048+569=10809 (3)3*2048+1000=7144應(yīng)用題7在一個請求頁式存儲管理中，一個程序的頁面走向為432143543215，并采用LRU算法。設(shè)分配給該程序的存儲塊數(shù)M分別為3和4，在該訪問中發(fā)生的缺頁次數(shù)F為 ( ) AM=3。F=8；M=4，F(xiàn)=5 BM=3，F(xiàn)=10；M=4，F(xiàn)=8 CM=3，F(xiàn)=9；M=4，F(xiàn)=10 D：M=3，F(xiàn)=7；M=4，F(xiàn)=6答案:B返回第8章應(yīng)用題8-9應(yīng)用題8假設(shè)用戶甲要用到文件A、B、C、E，用戶乙要用到文件A、D、E、F。已知：用戶甲的文件A與用戶乙的文件A實際上不是同一文件；用戶甲與用戶乙又分別用文件名C和F共享同一文件；甲、乙兩用戶的文件E是同一個文件。請回答下列問題：（1）系統(tǒng)應(yīng)采用怎樣的目錄結(jié)構(gòu)才能使兩用戶在使用文件時不致于造成混亂？（2）畫出這個目錄結(jié)構(gòu)。（3）兩個用戶使用了幾個共享文件？寫出它們的文件名。 答案:應(yīng)用題9.某用戶文件共10個邏輯記錄，每個邏輯記錄的長度為480個字符，現(xiàn)把該文件存放到磁帶上，若磁帶的記錄密度為800字符/英寸，塊與塊之間的間隙為0.6英寸，回答下列問題：(1)不采用記錄成組操作時磁空間的利用率為_。(2)采用記錄成組操作且塊因子為5時，磁帶空間的利用率為_。(3)當按上述方式