大題部分0s信科2016復(fù)習(xí)題

1、os復(fù)習(xí)題一. 選擇題(20分) 自己準(zhǔn)備，多為概念的理解，多數(shù)在平日講過的每章的題里能找到類似題。二. 判斷題(10分) 自己準(zhǔn)備，多為概念的理解，多數(shù)在平日講過的每章的題里能找到類似題。三.概念與簡述題（20分） 從下面的題里出，下面的題里大約考其中50%。1.并發(fā):是指兩個或多個事件在同一時間間隔內(nèi)發(fā)生。 2.并行:是指兩個或多個事件在同一時刻同時發(fā)生。3.裸機(jī):計算機(jī)系統(tǒng)中的硬件常被稱為裸機(jī)。4.虛擬機(jī):由計算機(jī)硬件和操作系統(tǒng)所組成的計算機(jī)系統(tǒng)稱為“虛擬機(jī)”。5.抖動現(xiàn)象:剛被調(diào)出的信息又被調(diào)入內(nèi)存，調(diào)入后不久又被調(diào)出內(nèi)存，又被調(diào)入內(nèi)存，調(diào)入后不久又被調(diào)出內(nèi)存，如此反復(fù)，這種現(xiàn)象就是抖

2、動現(xiàn)象。6.Belady現(xiàn)象:在未給作業(yè)分配滿足需要的主存塊數(shù)時，分配物理頁增多，缺頁次數(shù)反而升高的現(xiàn)象。該現(xiàn)象一般發(fā)生在先來先服務(wù)頁面置換算法中 7.設(shè)備的獨立性:采用“設(shè)備類、相對號”的方式使用設(shè)備時，用戶編制程序時不必指定特定的設(shè)備。在程序中使用由“設(shè)備類、相對號”定義的邏輯設(shè)備。程序執(zhí)行時系統(tǒng)根據(jù)用戶指定的邏輯設(shè)備轉(zhuǎn)換成與其對應(yīng)的具體物理設(shè)備，并啟動該物理設(shè)備工作。于是用戶編制程序時使用的設(shè)備與實際使用哪臺設(shè)備無關(guān)。把這種特性稱為“設(shè)備的獨立性”。8.微內(nèi)核技術(shù)：微內(nèi)核技術(shù)是指精心設(shè)計的、能實現(xiàn)現(xiàn)代操作系統(tǒng)核心功能的小型內(nèi)核，它短小精煉，不僅運行在核心態(tài)，而且開機(jī)后常駐內(nèi)存。微內(nèi)核中僅

3、包括操作系統(tǒng)中最主要、最基本、最底層的功能，它不是一個完整的操作系統(tǒng)，它為通用操作系統(tǒng)的開發(fā)提供底層支持，在此內(nèi)核的基礎(chǔ)上結(jié)合模塊化、層次化設(shè)計方法以及面向?qū)ο蠹夹g(shù)可以非常方便地開發(fā)出具有各種特點的操作系統(tǒng)。9.中斷：中斷是指計算機(jī)在執(zhí)行期間，系統(tǒng)內(nèi)發(fā)生非尋常的急需處理事件，使得CPU暫時中斷當(dāng)前正在執(zhí)行的程序而轉(zhuǎn)去執(zhí)行相應(yīng)的事件處理程序，待處理完畢后又返回原來被中斷處繼續(xù)執(zhí)行或選擇優(yōu)先級高的新的進(jìn)程執(zhí)行的過程。10.死鎖的4個必要條件：互斥，不剝奪，部分分配，環(huán)路條件。 11.畫出進(jìn)程3個基本狀態(tài)之間的轉(zhuǎn)換圖。寫出與進(jìn)程運行狀態(tài)改變有關(guān)的引發(fā)進(jìn)程調(diào)度的原因(至少3種)。答：（1） 當(dāng)前進(jìn)程執(zhí)

4、行完（2） 當(dāng)前進(jìn)程由執(zhí)行態(tài)進(jìn)入阻塞態(tài)。（3） 當(dāng)前執(zhí)行的進(jìn)程所分配的時間片用完。12. 在磁盤上有一個文件系統(tǒng)，磁盤每塊512字。假定每個文件在目錄中占有一個目錄項，該目錄項給出了文件名、第一個索引塊的地址、文件長度（塊數(shù)）。在索引塊中（包括第一個索引塊）前面511個字指向文件塊，即第i個索引項（i=0，1，2，510）指向文件的第i塊，索引塊中最后一個字指向下一個索引塊，最后一個索引塊中最后一個字為null。假定目錄在存儲器中，每個文件的邏輯塊號均從0開始編號，邏輯塊與物理塊長相同。對這樣的索引物理結(jié)構(gòu)，該系統(tǒng)應(yīng)如何將邏輯塊號變換成物理塊號？(采用舉例、畫圖等方式進(jìn)行描述)答：根據(jù)邏輯塊號

5、確定該邏輯塊所在的索引塊和在索引塊中的位置，方法：邏輯塊號除以511得到的整數(shù)部分為所在的索引塊號，余數(shù)部分為在索引塊中的位置；然后在索引塊的鏈中，找到邏輯塊所在的索引塊，并讀入內(nèi)存，分離出邏輯塊所在物理塊號。假設(shè)邏輯塊號是788，該邏輯塊所在的索引塊號=788/511=1 ，索引塊中的位788%511=277，在文件的目錄項中找到首個索引塊(第0個索引塊)的地址，把該索引塊讀入內(nèi)存，把最后一項分離出來，即第1索引塊所在的物理塊號，把該物理塊讀入內(nèi)存，分離出277項，即為所求的物理塊號。四分析計算題(50分) 從下面的題里出同類型類似題，考試時所有題都要算出最終結(jié)果，不能象下面一些例子只擺式子

6、，另外下例不保證答題過程和答案完全正確，僅供參考題型和解題思路。1.分頁管理，訪問虛擬頁序列是7,0,1,2,0,3,0,4,2,3,0,3， 分配到3個物理頁面， 畫出不同頁面置換算法結(jié)果，得出缺頁率。(1) 先進(jìn)先出FIFO (2) 最近最久未使用頁面置換算法LRU (3) 理想型淘汰算法OPT （缺頁率能化簡的要化簡，下例中的沒化簡）(4)假設(shè)訪問一次內(nèi)存100ns，缺頁中斷處理時間20ms，求LRU算法中這些頁面的平均訪問時間。(以ns為單位)（1）FIFO，缺頁10次， 所以缺頁率10/1270120304230317772222444002000033322223111100033

7、3是否缺頁是是是是否是是是是是是否（2）LRU, 缺頁9次， 所以缺頁率9/12（這里沒對每列重新排序，你可以象書上那樣對頁面重新排序，把需要替換的排到最下面）701203042303177722224440020000000033331113332222是否缺頁是是是是否是否是是是是否（3）OPT，缺頁7次， 所以缺頁率7/12701203042303177722222222220000004440031113333333是否缺頁是是是是否是否是否否是否（4）200ns*3/12+(200ns+20*106ns)*9/122.某操作系統(tǒng)的存儲管理采用頁式管理系統(tǒng)，系統(tǒng)的物理地址空間大小為4M

8、B，頁的大小是1KB，假定該系統(tǒng)中進(jìn)程空間的大小為16MB，問：（1）邏輯頁號和頁內(nèi)地址各多少位（2）物理頁號和頁內(nèi)地址各多少位（3）一共有多少個物理頁（4）采用位示圖管理內(nèi)存空間，問位示圖要占多少字節(jié)？答：1KB=210字節(jié)，所以頁內(nèi)地址占10個二進(jìn)制位4MB=222字節(jié)，頁內(nèi)地址占了10位,所以物理頁號占12位16MB=224字節(jié)，頁內(nèi)地址占了10位,所以邏輯頁號占14位一共有222/210=212頁每頁占位示圖中1bit，一共有212頁，所以位示圖需要212/8=29字節(jié)。 綜上以上分析 （1） 14位, 10位 （2） 12位，10位 （3） 212個物理頁 （4） 位示圖占29字節(jié)。

9、3.假定某磁盤的旋轉(zhuǎn)速度是每圈20毫秒，格式化時每個盤面被分成個10扇區(qū)，現(xiàn)有個10邏輯記錄存放同一在磁盤上，安排如圖1所示。處理程序要順序處理這些記錄，每讀出一條記錄后處理程序要花4毫秒的時間進(jìn)行處理，然后再順序讀下一條記錄并進(jìn)行處理，知道處理完成這些記錄，回答（1） 順序處理完這10條記錄總共花費了多少時間？（2） 請給一種記錄優(yōu)化分布的方案，使處理程序能在短時間內(nèi)處理完這10條記錄，并計算優(yōu)化分布時需要花費的時間。（3） 假設(shè)每個磁盤塊大小為1KB,問該磁盤的數(shù)據(jù)傳輸率為多少（單位KB/S）12345678910起點 圖1 邏輯記錄的存放次序答：（1）磁盤旋轉(zhuǎn)一個扇區(qū)所需時間=20/10

10、=2ms則讀出并處理一條記錄所需時間=2+4=6ms, 共10條記錄需要60ms.轉(zhuǎn)到下個需要處理的扇區(qū)需要花費20-4=16ms，這樣的等待時間需要9次，共16*9=144ms所以一共花費 60+144=204ms。（2）一種記錄優(yōu)化分布的方案如圖2所示。這種記錄優(yōu)化分使處理程序在處理完前一條邏輯記錄時磁頭正好旋轉(zhuǎn)到下一條邏輯記錄所在的扇區(qū)，處理所需的時間最短，處理完這10條記錄需要花費的時間=10*（2+4）+9*0=60ms點圖2 邏輯記錄優(yōu)化環(huán)分布（3）20ms轉(zhuǎn)一圈，讀出10個扇區(qū)，每個扇區(qū)1KB, 即20ms讀出了10KB，10KB/20ms= 500KB

11、/S。4. 分頁系統(tǒng)，快表命中率60%，一次內(nèi)存存取時間為1ns，缺頁時要發(fā)生置換，如果無頁面修改標(biāo)記，一個缺頁中斷要8000ns，有修改標(biāo)記的，一個缺頁中斷要20000ns，兩種情況各占40%，60%，為保證有效訪問時間不超過5ns，求允許的最大缺頁率f是多少EAT=a(&+t)+(1-a)(1-f)(&+t+&+t)+f(&+t+t1+&+t)<=5ns其中a=60%, t=1ns, &=0, t1=8000*40%+20000*60% 代入即可解得f 。5.設(shè)存在三個過程get、copy和put分別對緩沖區(qū)S和T進(jìn)行操作，其中g(shù)et負(fù)

12、責(zé)將數(shù)據(jù)塊存入緩沖區(qū)S，copy負(fù)責(zé)從緩沖區(qū)S讀出數(shù)據(jù)并復(fù)制到緩沖區(qū)T中，put負(fù)責(zé)從緩沖區(qū)T中讀出數(shù)據(jù)并打印，如圖所示。請用P、V操作描述上述三個過程。getcopyput緩沖區(qū)S緩沖區(qū)T輸入緩沖輸出問題設(shè)信號量：sempty: 表示S允許存入（為1表示允許），初值為1; sfull ：表示S允許取出（為1表示允許），初值為0; tempty : 表示T允許存入（為1表示允許），初值為1;tfull: 表示T允許取出（為1表示允許），初值為0;對進(jìn)程的描述：Main()CobeginGet();Copy();Put();CoendGet() While (1) 獲取一數(shù)據(jù)x; P(sempt

13、y); buff(S)=x; V(sfull);copy() While (1) P(sfull); y=buff(S); V(sempty); p(tempty); buff(T)=y;v(tfull);put() While (1) P(tfull);z= buff(T); V(tempty);輸出數(shù)據(jù)z;6.P1、P2、P3互斥使用一個N單元的緩沖區(qū)， P1用produce()生成一個正整數(shù)， 用put(x)把該數(shù)放入緩沖區(qū)某一空單元； P2用getodd()從緩沖區(qū)取出一個奇數(shù)，用countodd()統(tǒng)計奇數(shù)個數(shù)；P3用geteven()從緩沖區(qū)取出一個偶數(shù)，用counteven()統(tǒng)

14、計偶數(shù)個數(shù)，寫出P1、P2、P3的偽代碼。答：定義信號量empty，表示空單元個數(shù)，初值為N；定義信號量odd表示放奇數(shù)單元的個數(shù)，初值為0；定義信號量even表示放偶數(shù)單元的個數(shù)，初值為0；定義信號量mutex， 用于實現(xiàn)緩沖區(qū)互斥，初值為1。P1(): Begin L1: x=produce() p(empty) p(mutex) put(x) v(mutex) if x%2=1 then v(odd) else v(even) goto L1endP2(): Begin L2:P(odd)P(mutex)Getodd()v(mutex)v(empty)countodd() goto L2

15、endP3(): Begin L3:P(even)P(mutex)Geteven()v(mutex)v(empty)counteven() goto L3end7.各作業(yè)情況如下：作業(yè)號到達(dá)時刻開始時刻運行需時結(jié)束時刻次序優(yōu)先級別1024215932814338優(yōu)先級為小值優(yōu)先，求平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間?1. 先來先服務(wù) 2.短作業(yè)優(yōu)先 3.靜態(tài)優(yōu)先(小的優(yōu)先)答：1. 先來先服務(wù)作業(yè)號到達(dá)時刻開始時刻運行需時結(jié)束時刻次序優(yōu)先級別10022142125729327815314315318480時刻只有作業(yè)1到達(dá)， 所以先執(zhí)行1；2時刻作業(yè)2和3都到達(dá)，2先到所以執(zhí)行2；7時刻作業(yè)3和作

16、業(yè)4都到達(dá)，3先所以執(zhí)行3，再執(zhí)行4平均周轉(zhuǎn)時間=(2-0)+(7-1)+(15-2)+(18-3)/4=9平均帶權(quán)周轉(zhuǎn)時間=(2-0)/2+(7-1)/5+(15-2)/8+(18-3)/3/42. 短作業(yè)優(yōu)先作業(yè)號到達(dá)時刻開始時刻運行需時結(jié)束時刻次序優(yōu)先級別10022142125729321081841437310380時刻只有作業(yè)1到達(dá)，所以先執(zhí)行1；2時刻作業(yè)2和3都到達(dá)，2短所以先執(zhí)行2；7時刻作業(yè)3和4都到達(dá)，4短所以執(zhí)行4，最后執(zhí)行3平均周轉(zhuǎn)時間=(2-0)+(7-1)+(18-2)+(10-3)/4=7.75平均帶權(quán)周轉(zhuǎn)時間=(2-0)/2+(7-1)/5+(18-2)/8+(

17、10-3)/3/43. 靜態(tài)優(yōu)先級作業(yè)號到達(dá)時刻開始時刻運行需時結(jié)束時刻次序優(yōu)先級別1002214211351849322810214310313380時刻只有作業(yè)1到達(dá)，所以先執(zhí)行1；2時刻作業(yè)2和3都到達(dá)，3優(yōu)先值小所以先執(zhí)行3；10時刻作業(yè)2和4都到達(dá)，4優(yōu)先值小所以執(zhí)行4，最后執(zhí)行2平均周轉(zhuǎn)時間=(2-0)+(18-1)+(10-2)+(13-3)/4=9.25平均帶權(quán)周轉(zhuǎn)時間=(2-0)/2+(18-1)/5+(10-2)/8+(13-3)/3/48.系統(tǒng)中磁頭停留在磁道號為70的磁道上，這時先后有4個進(jìn)程提出了磁盤訪問請求，要訪問磁盤的磁道號按申請到達(dá)的先后順序依次為45,68,2

18、8,90.移動臂的運動方向：沿磁道號遞減的方向移動。若分別采用FCFS磁盤調(diào)度算法、SSTF算法、SCAN算法時，磁頭移動的順序和所需尋道長度分別是多少？如果每移動一個柱面需要3ms，移動時間分別是多少？FCFS： 70-45-68-28-90 尋道長度=(70-45)+(68-45)+(68-28)+(90-28)=150 , 移動時間150*3msSSTF： 70-68-90-45-28尋道長度=(70-68)+(90-68)+(90-45)+(45-28)=86，移動時間86*3msSCAN：70-68-45-28-90尋道長度=(70-68)+(68-45)+(45-28)+(90-2

19、8)=104, 移動時間104*3ms因為題里給出移動方向，所以電梯調(diào)度只有這一種，否則應(yīng)為兩種答案如果做CSCAN(單項掃描，也叫循環(huán)掃描)：方向規(guī)定為從外向里，在本題里訪問次序應(yīng)為70-90-28-45-68尋道長度等自己算9現(xiàn)有四個進(jìn)程P1，P2，P3，P4共享R1，R2，R3三類資源，資源分配情況如表1所示，采用銀行家算法(1)目前系統(tǒng)是否處于安全狀態(tài)？(2)現(xiàn)在如果進(jìn)程P2提出申請資源數(shù)量為(1,0,1)，能否為它分配？(3)P2申請資源后，若P1再請求(1,0,1)，能否為它分配？(4)P1申請資源后，若P3再請求(0,0,1)，能否為它分配?表1系統(tǒng)當(dāng)前資源分配表進(jìn)程Max R1

20、 R2 R3Allocation R1 R2 R3 NeedR1 R2 R3AvailableR1 R2 R31 2P2613511102P3314211103P4422002420MAX表示各進(jìn)程最大需求資源數(shù)，Allocation表示已經(jīng)分配的資源數(shù)，Need表示仍需要的資源數(shù)，Available表示現(xiàn)在可用的資源數(shù)。這幾項不需要都給出，要注意表里給出的是什么。以下為簡答：(1)通過分析，舉出一個安全序列， P2、P3、P4、P1，說明系統(tǒng)能夠按這一次序執(zhí)行完所有進(jìn)程，那么就說明當(dāng)前系統(tǒng)處于安全狀態(tài)。(需要具體說明為什么有這個安全序列)(2) 分配給P2后剩下資源

21、為(0,1,1)，P2此時需求變?yōu)?0,0,1)，仍可以使P2執(zhí)行完畢，即仍存在(1)中的安全序列，因此可以分配。(3) 此時剩余資源是(0,1,1)，不能滿足P1的請求(1,0,1)，因此P1進(jìn)入阻塞狀態(tài)，不能進(jìn)行分配。(4) P1申請資源后進(jìn)入阻塞狀態(tài)，此時剩余資源仍是(0,1,1)，若分配給P3(0,0,1)，則剩余(0,1,0)，不足以滿足任何進(jìn)程執(zhí)行完，此時不存在安全序列，因此不能分配。10.各進(jìn)程情況如下：進(jìn)程號到達(dá)時刻開始時刻運行需時結(jié)束時刻次序103226344465582采用最高響應(yīng)比優(yōu)先算法，求平均周轉(zhuǎn)時間和帶權(quán)平均周轉(zhuǎn)時間? 答：最高響應(yīng)比優(yōu)先進(jìn)程號到達(dá)時刻開始時刻運行需時結(jié)束時刻次序100331223692349413346155205581321540時刻只有進(jìn)程1到達(dá)，所以先執(zhí)行1；3時刻只有進(jìn)程2到達(dá)，所以執(zhí)行2；9時刻進(jìn)程3、4、5都到達(dá), 進(jìn)程3此時響應(yīng)比是1+(9-4)/4=2.25, 進(jìn)程4此時響應(yīng)比是1+(9-