華南師范大學(xué)級操作系統(tǒng)總復(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) 進程具有并行特征，而程序沒有。由進程的定義可知，進程具有并行特征的兩個方面，即獨立性和異步性。 (3

2、) 進程是分配計算機系統(tǒng)資源的基本單位。(4) 不同的進程可以包含同一程序，只要該程序所對應(yīng)的數(shù)據(jù)集不同。l 進程控制塊是進程存在的標(biāo)志。l 線程是CPU調(diào)度的基本單位l 進程是資源分配的基本單位l 把系統(tǒng)態(tài)下執(zhí)行的某些具有特定功能的程序段稱為原語。l 用于進程控制的原語有：創(chuàng)建原語、撤消原語、阻塞原語、喚醒原語等。應(yīng)用題2應(yīng)用題1第3章 作業(yè)管理（這里我們將第二章的進程調(diào)度放在一起）l 衡量調(diào)度策略的最常用的幾個指標(biāo)是：周轉(zhuǎn)時間、吞吐率、響應(yīng)時間以及設(shè)備利用率等。l 周轉(zhuǎn)時間是指將一個作業(yè)提交給計算機系統(tǒng)后到該作業(yè)的結(jié)果返回給用戶所需要的時間。l 吞吐率是指在給定的時間內(nèi)，一個計算機系統(tǒng)所完

3、成的總工作量。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è)中去挑選作業(yè)，盡可能地使得使用不同資源的作業(yè)同時執(zhí)行。進程調(diào)度算法:1. 先來先服務(wù)2. 時間片輪轉(zhuǎn)法3. 優(yōu)先數(shù)調(diào)度算法4. 多級反饋隊列調(diào)度算法 第4章 存儲管理應(yīng)用題5-7應(yīng)用題4l 覆蓋與交換技術(shù)l 抖動(thrashin

4、g)現(xiàn)象。l Belady現(xiàn)象l 理想型淘汰算法OPTl 頁式管理的優(yōu)缺點l 段式與段頁式管理段式管理的基本思想是: 把程序按內(nèi)容或過程(函數(shù))關(guān)系分成段，每段有自己的名字。一個用戶作業(yè)或進程所包含的段對應(yīng)于一個二維線性虛擬空間，也就是一個二維虛擬存儲器。分頁和分段的區(qū)別第5章 設(shè)備管理 : 設(shè) 備 分 配了解設(shè)備分配流程圖l 數(shù)據(jù)傳送控制方式：程序控制方式，中斷控制方式，DMA控制方式，通道控制方式l 緩沖區(qū)用于緩沖CPU和外設(shè)之間的速度不匹配。l 緩沖的種類：根據(jù)系統(tǒng)設(shè)置的緩沖器的個數(shù)，可把緩沖技術(shù)分為單緩沖、雙緩沖和多緩沖以及緩沖池幾種。l 設(shè)備的相對性和獨立性。l 設(shè)備分為獨占設(shè)備和共

5、享設(shè)備兩種。l 在磁盤上確定分塊所在的位置必須給出的以下參數(shù)：柱面號、磁頭號、扇區(qū)號磁盤空間的管理 1空閑塊表法 2空閑塊鏈法 3位示圖法 4成組鏈接法 啟動磁盤完成一次輸入/輸出操作所花的時間包括：尋找時間、延遲時間和傳送時間。l 移臂調(diào)度：先來先服務(wù)，最短尋找時間優(yōu)先調(diào)度算法SSTF、電梯調(diào)度算法例題：假定在某移動臂磁盤上，剛剛處理了訪問75號柱面的請求，目前正在80號柱面上讀信息，并有下列請求序列等待訪問磁盤： 請求序列： l 2 3 4 5 6 7 8 欲訪問的柱面號：160 40 190 188 90 58 32 102 試用(1)電梯調(diào)度算法；(2)最短查找時間優(yōu)先算法，分別排出實

6、際處理上述請求的次序。l 旋轉(zhuǎn)調(diào)度：記錄在磁道上的排列方式會影響I/O操作的時間。l 例題：某系統(tǒng)在對磁盤初始化時，把每個盤面分成8個扇區(qū)，有8個邏輯記錄被存放在同一個磁道上供處理程序使用。處理程序要求順序處理這8個記錄，每次請求從磁盤上讀一個記錄，然后對讀出的記錄要花5ms的時間進行處理，以后再讀下一個記錄進行處理，直至8個記錄全部處理結(jié)束。假定磁盤的轉(zhuǎn)速為20ms/周，現(xiàn)把這8個邏輯記錄依次存放在磁道上，如圖所示。處理這8個記錄所要花費的時間為： 8×(2.5+5)+10+7×15=175(ms) 如果把這8個邏輯記錄在磁道上的位置重新安排一下，圖b）是這8個邏輯記錄的

7、最優(yōu)分布示意圖。當(dāng)讀出一個記錄并處理后，讀/寫磁頭正好位于順序處理的下一個記錄位置，可立即讀出該記錄，不必花費等待延遲時間。于是，按圖b）的安排，處理這8個記錄所要花費的時間為： 10+8×(2.5+5)=70(ms)操作系統(tǒng)中實現(xiàn)聯(lián)機同時外圍設(shè)備操作功能的部分也稱為SPOOLing系統(tǒng)，SPOOLing系統(tǒng)主要由三部分程序組成，即“預(yù)輸入”程序、實現(xiàn)輸入井讀和輸出井寫的“井管理”程序和“緩輸出”程序。 SPOOLing系統(tǒng)將獨占型設(shè)備改造為共享型設(shè)備。第6章 文件系統(tǒng)應(yīng)用題8-9習(xí)題:一、設(shè)進程A和進程B, 它們都要求進入臨界區(qū)CS, 下面的設(shè)計就可以滿足進程的互斥要求: 進程B:

8、 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； cobegin producer； consumer； coend Procedure producer；begin while true do begin produce next product； P(SP)； put a product； V (SG)； endendprocedure consumer； 消費者進程 b

9、egin while true do begin p(SG) 查緩沖區(qū)足否已有新的產(chǎn)品 take a product 取產(chǎn)品 V(SP )； 通知生產(chǎn)者已取走產(chǎn)品 comsume the product 消費產(chǎn)品 end end；三、同步互斥混合假設(shè)有一個成品倉庫，總共能存放8臺成品，生產(chǎn)者進程生產(chǎn)產(chǎn)品放入倉庫，消費者進程從倉庫中取出成品消費。為了防止積壓，倉庫滿的時候就停止生產(chǎn)。由于倉庫搬運設(shè)備只有一套，故成品的存入和取出只能分別執(zhí)行，使用PV操作來實現(xiàn)該方案。答案:S:信號量,倉庫能放產(chǎn)品的個數(shù),初值=8S1: 信號量,用于互斥,初值=1S2: 信號量,倉庫現(xiàn)有產(chǎn)品的個數(shù),初值=0Proc

10、ess 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è)當(dāng)前的系統(tǒng)狀態(tài)如下，系統(tǒng)此時Available (1，1，2)： Claim Allocation needWork+allocation進程 R1 R2 R3 Rl R2 R3 Rl R2 R3 P1 3 2 2 1 0 0 2 2 2 P2 6 1 3 5 1 1 1 0 26 2 3 P3 3 l 4 2 1 1 1 0 38 3 4 P4 4 2 2 0 0 24 2 0(1)計算各個進程還需要的資源數(shù)(2)系統(tǒng)是

11、否處于安全狀態(tài)，為什么?(3)P2發(fā)出請求向量request2(1，0，1)，系統(tǒng)能把資源分給它嗎? Claim Allocation needWork+allocation進程 R1 R2 R3 Rl R2 R3 Rl R2 R3 P1 3 2 2 1 0 0 2 2 2 P2 6 1 3 6 0 2 0 0 16 2 3 P3 3 l 4 2 1 1 1 0 3 P4 4 2 2 0 0 24 2 0答：(1)P1，P2，P3，P4為：(2，2，2)、(1，0，2)、(4，2,0) (2)系統(tǒng)處于安全狀態(tài)，存在安全序列：P2，Pl，P3，P4 (3)可以分配，存在安全序列：P2，Pl，P3

12、，P4。返回應(yīng)用題31.設(shè)有四道作業(yè)，它們進入系統(tǒng)的時間及需要執(zhí)行的時間如下表所示，并規(guī)定當(dāng)?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)時間190070   294030   395010   410105   要求：分別采用先來先服務(wù)和最短執(zhí)

13、行時間優(yōu)先調(diào)度算法時的調(diào)度次序和作業(yè)平均周轉(zhuǎn)時間。答案:先來先服務(wù): 調(diào)度次序1à2à3à4作業(yè)號進入系統(tǒng)時間需執(zhí)行時間（分鐘）開始時間完成時間周轉(zhuǎn)時間190070 9:00 10:10 70294030 10:10 10:40 60395010 10:40 10:50 60410105 10:50 10:55 45作業(yè)平均周轉(zhuǎn)時間(70+60+60+45)/4=58.75最短執(zhí)行時間優(yōu)先: 調(diào)度次序1à4à3à2作

14、業(yè)號進入系統(tǒng)時間需執(zhí)行時間（分鐘）開始時間完成時間周轉(zhuǎn)時間190070 9:00 10:10 70294030 10:25 10:55 75395010 10:15 10:25 35410105 10:10 10:15 5作業(yè)平均周轉(zhuǎn)時間(70+75+35+5)/4=46.25結(jié)論:最短執(zhí)行時間優(yōu)先比先來先服務(wù)效率高.2. 有一多道程序設(shè)計系統(tǒng)，采用不允許移動的可變分區(qū)式管理主存空間，設(shè)主存空間為100KB，采用最先適應(yīng)分配算法分配主存，作業(yè)調(diào)度和進程調(diào)度均采用先來先服務(wù)算法

15、，今有如下作業(yè)序列，計算作業(yè)的平均周轉(zhuǎn)時間。 10.1 1à后備à就緒àCPU 10.4結(jié)束10.3 2à就緒10.4 1結(jié)束 2àCPU 10.8結(jié)束10.5 3à后備10.6 4à就緒10.7 5-à就緒執(zhí)行順序: 1->2à4à5-à3作業(yè)提交運行開始結(jié)束周轉(zhuǎn)110.10.310.110.40.3210.30.510.410.90.6310.50.411.511.91.4410.60.410.911.30.7510.70.211.311.50.8平均周轉(zhuǎn)時間=0.76返回應(yīng)

16、用題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)存利用率最高?應(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è)按

17、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 100K 其中j5沒有分配. BF算法，空閑分區(qū)表情況如表A-4所示，5個作業(yè)J1。J2，J3，J4，J5全部裝入內(nèi)存。 表A-4分配后的空閑分區(qū)表(BF)分區(qū)號大小 1 4K 2 0K 3 4K 4 5K 5 100K返回應(yīng)用題5分頁式存儲空間的分配由于塊的大小是固定的，可以用一張位示圖(Bit map)來構(gòu)成主存分配表?，F(xiàn)設(shè)主存

18、有8192塊，可用字長為32位的256個字作為位示圖。若塊號，字號，位號(從高位到低位)分別從1、0、0開始，試問5999塊對應(yīng)的字號和位號?199字的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答案: (1)2*2048+100=4196 (2)5*2048+569=10809 (3)3*2048+

19、1000=7144在一個分頁虛存系統(tǒng)中，用戶編程空間32個頁，頁長1KB，主存為16KB。如果用戶程序有10頁長，若己知虛頁0、1、2、3，已分配到主存8、7、4、10物理塊中，試把虛地址0AC5H和1AC5H轉(zhuǎn)換成對應(yīng)的物理地址。答：0AC5H對應(yīng)的物理地址為12C51AC5會發(fā)生缺頁中斷，由系統(tǒng)另行分配主存空間。應(yīng)用題7在一個請求頁式存儲管理中，一個程序的頁面走向為4,3,2,1,4,3,5,4,3,2,1,5，并采用LRU算法。設(shè)分配給該程序的存儲塊數(shù)M分別為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；

20、M=4，F(xiàn)=10 D：M=3，F(xiàn)=7；M=4，F(xiàn)=6答案:B段表給定段表如下：段號段首址段長02196001230014290100313275804195296給定地址為段號和位數(shù)，試求出對應(yīng)的主存物理地址。（1）0，430 （2）3，400 （3）1，1 （4）2，500 （5）4，42答：（1）649 （2）1727 （3）2301 （4）越界 （5）1994返回應(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個邏輯記錄，每個邏輯記錄的長