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

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

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

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

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

5、技術(shù)分為單緩沖、雙緩沖和多緩沖以及緩沖池幾種。習(xí)題:一、設(shè)進(jìn)程A和進(jìn)程B, 它們都要求進(jìn)入臨界區(qū)CS, 下面的設(shè)計(jì)就可以滿足進(jìn)程的互斥要求: 進(jìn)程B: P（S）; CS2; V（S）; coend S1; /* 定義信號(hào)量并確定初值*/ cobegin進(jìn)程A: P（S）; CS1; V（S）; 二、生產(chǎn)者和消費(fèi)者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； 消費(fèi)者進(jìn)程 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 消費(fèi)產(chǎn)品 end end；三、同步互斥混合假設(shè)有一個(gè)成品倉(cāng)庫(kù)，總共能存放8臺(tái)成品，生產(chǎn)者進(jìn)程生產(chǎn)產(chǎn)品放入倉(cāng)

7、庫(kù)，消費(fèi)者進(jìn)程從倉(cāng)庫(kù)中取出成品消費(fèi)。為了防止積壓，倉(cāng)庫(kù)滿的時(shí)候就停止生產(chǎn)。由于倉(cāng)庫(kù)搬運(yùn)設(shè)備只有一套，故成品的存入和取出只能分別執(zhí)行，使用PV操作來實(shí)現(xiàn)該方案。答案:S:信號(hào)量,倉(cāng)庫(kù)能放產(chǎn)品的個(gè)數(shù),初值=8S1: 信號(hào)量,用于互斥,初值=1S2: 信號(hào)量,倉(cāng)庫(kù)現(xiàn)有產(chǎn)品的個(gè)數(shù),初值=0Process producerP(S)生產(chǎn)產(chǎn)品P(S1)放入倉(cāng)庫(kù)V(S1)V(S2)Process consumerP(S2)P(S1)取出成品消費(fèi)V(S1)V(S)返回應(yīng)用題2設(shè)當(dāng)前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時(shí)Availableffi(0，1，1)： Claim Allocation need進(jìn)程 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)計(jì)算各個(gè)進(jìn)程還需要的資源數(shù)(2)系統(tǒng)是否處于安全狀態(tài)，為什么?執(zhí)行順序：p2,執(zhí)行完資源個(gè)數(shù)：1，1，2+5，1，1=6，2，3P3,執(zhí)行完資源個(gè)數(shù)：6,2,3+2,1,1=8,3,4P4,執(zhí)行完資源個(gè)數(shù)：P1,執(zhí)行完資源個(gè)數(shù)：執(zhí)行完畢，說明系統(tǒng)安全(3)P2發(fā)出請(qǐng)求向量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è)，它們進(jìn)入系統(tǒng)的時(shí)間及需要執(zhí)行的時(shí)間如下表所示，并規(guī)定當(dāng)?shù)谝粋€(gè)作業(yè)進(jìn)入系統(tǒng)后立即調(diào)度，忽略調(diào)度的時(shí)間開銷。表列出了A、B、C和D共4個(gè)作業(yè)到達(dá)系統(tǒng)的時(shí)間、運(yùn)行時(shí)間、開始時(shí)間及各自完成的時(shí)間，采用FCFS算法，計(jì)算各自的周轉(zhuǎn)時(shí)間和帶權(quán)周轉(zhuǎn)時(shí)間和等待時(shí)間，分析結(jié)果可以得出什么結(jié)論？ 作業(yè)號(hào)進(jìn)入系統(tǒng)時(shí)間需執(zhí)行時(shí)間（分鐘）開始時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間190070294030395010410105要求：分別采用先來先服務(wù)和最短執(zhí)行時(shí)間優(yōu)先調(diào)度算法時(shí)

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

11、)/4=46.25結(jié)論:最短執(zhí)行時(shí)間優(yōu)先比先來先服務(wù)效率高.2. 有一多道程序設(shè)計(jì)系統(tǒng)，采用不允許移動(dòng)的可變分區(qū)式管理主存空間，設(shè)主存空間為100KB，采用最先適應(yīng)分配算法分配主存，作業(yè)調(diào)度和進(jìn)程調(diào)度均采用先來先服務(wù)算法，今有如下作業(yè)序列，計(jì)算作業(yè)的平均周轉(zhuǎn)時(shí)間。 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è)提交運(yùn)行開始結(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)時(shí)間=0.76返回應(yīng)用題4在可變分區(qū)管理下，假定內(nèi)存中按地址順序，依次有5個(gè)空閑區(qū)，空閑區(qū)的大小分別為32K，10K，5K，228K，100K現(xiàn)有5個(gè)作業(yè)J1，J2，J3，J4，J5它們各需要內(nèi)存1K，10K，108K，28K，115K若采用FF算法，能將這5個(gè)作業(yè)按J1，J2，J3，J4，J5的順序全部裝入內(nèi)存嗎?你認(rèn)為按怎樣的次序裝入這5個(gè)作業(yè)可使內(nèi)存利用率最高?解：按FF算法，空閑分區(qū)表情況如表A-3所示，作業(yè)J5沒有裝入內(nèi)存。表A-3分配后的空閑分區(qū)表(BF)分區(qū)號(hào)大小 1 21K 2 10K 3 5K 4 92K 5 100

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

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

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