2010-2011字牛弟1字期考誡誡題（B）卷課程名稱 《操作系統(tǒng)》出題教師簽名任課教師簽名審題教師簽名考試方式 （閉）卷適用專業(yè) 計算機各專業(yè)考試時間 （ 120）分鐘題號— 四五六總分得分評卷人一、單項選擇題（每小題2分，共20分））下執(zhí)行。只能在用戶態(tài)不能在管態(tài)，也不能在用戶態(tài)）下執(zhí)行。只能在用戶態(tài)不能在管態(tài)，也不能在用戶態(tài)A.只能在管態(tài) B.C.可在管態(tài)，也可在用戶態(tài) D.實時操作系統(tǒng)必須在內(nèi)完成來自外部的事件。A.響應時間 B.周轉(zhuǎn)時間 C■規(guī)定時間 D.調(diào)度時間3.最適合分時系統(tǒng)的進程調(diào)度算法是3.最適合分時系統(tǒng)的進程調(diào)度算法是A.FCFSB.SSJFC. 優(yōu)先數(shù)法 D.輪轉(zhuǎn)法進程從運行狀態(tài)進入就緒狀態(tài)的原因可能是oA?被選中占有處理機 B.等待某一事件C?等待的事件已發(fā)生D.時間片用完設(shè)有五個進程共享一個互斥段，在同一時間最多允許一個進程進入互斥段 ，則所采用的互斥信號量初值應該是oA.5 B.2 C.1 D.0銀行家算法在解決死鎖問題中是用于的。A.預防死鎖 B.避免死鎖C. 檢測死鎖 D.解除死鎖在下列存儲管理方案中，不適應于多道程序設(shè)計的是oA.單一連續(xù)分配 B.固定式分區(qū)分配C.可變式分區(qū)分配 D.段頁式存儲管理UNIX文件的目錄結(jié)構(gòu)采用oA.簡單目錄 B.二級目錄C?系統(tǒng)目錄 D.帶交叉勾鏈的樹型目錄文件系統(tǒng)的主要目的是oA?實現(xiàn)對文件的按名存取 B.實現(xiàn)虛擬存儲C.提高外存的讀寫速度 D. 用于存儲系統(tǒng)文件下列算法中用于磁盤移臂調(diào)度的是。A時間片輪轉(zhuǎn)法 BXRU算法C.最短尋找時間優(yōu)先算法D.優(yōu)先級高者優(yōu)先算法二、判斷題（每小題2分，共10分）采用多道程序設(shè)計的系統(tǒng)中，系統(tǒng)的程序道數(shù)越多，系統(tǒng)的效率就越高。2作業(yè)的聯(lián)機控制方式適用于終端作業(yè)。時間片越小，系統(tǒng)的響應時間就越小，系統(tǒng)的效率就越高。程序的并發(fā)執(zhí)行是指同一時刻有兩個以上的程序 ，它們的指令在同一處理器上執(zhí)行。按最先適應算法分配的分區(qū)，一定與作業(yè)要求的容量大小最接近。三、填空題（每小題2分，共10分）1.為實現(xiàn)CPU與外部設(shè)備的并行工作，系統(tǒng)引入了硬件機制。UNIX系統(tǒng)采用結(jié)構(gòu)存放文件物理塊的地址。文件的符號名與物理地址的轉(zhuǎn)換是通過實現(xiàn)的。用戶編程時使用地址，處理機執(zhí)行程序時使用地址。采用資源有序分配算法可以死鎖的發(fā)生。四、 簡答題（每小題5分，共20分）1.請介紹在文件存儲空間的管理中幾種常用的技術(shù)。為什么要引入SPOOLing系統(tǒng)？SPOOLing系統(tǒng)可帶來哪些好處？進程和線程的主要區(qū)別是什么？4產(chǎn)生死鎖有四個必要條件？五、 計算題（40分）在一個飛機訂票系統(tǒng)中，多個用戶共享一個數(shù)據(jù)庫。多用戶同時查詢是可以接收的指但若一個用戶要訂票需更新數(shù)據(jù)庫時，其余所有用戶都不可以訪問數(shù)據(jù)庫。請畫出用戶查詢與訂票的邏輯框圖。要求：當一個用戶訂票而需要更新數(shù)據(jù)庫時，不能因有查詢者的到來而使他長期等待。 （15分）2.統(tǒng)中，一個程序的頁面走向為2.統(tǒng)中，一個程序的頁面走向為試分別求出采用FCFS和LRU頁面置（要求給出頁面置換的過程）。（15分）4、3、2、1、4、3、5、4、3、2、1、52殳分配給該程序的存儲塊數(shù)為換算法時，發(fā)生缺頁中斷的次數(shù)和缺頁中斷率3. 磁盤請求的柱面按 10,22,20,2,40,6,38的次序到達磁盤的驅(qū)動器，尋道時每個柱面移動需要6ms計算按以下算法調(diào)度時的尋道時間 ：（1）先來先服務；（2）下一個最鄰近的柱面；（3）電梯算法。假設(shè)以上所有情況磁頭臂均起始于柱面 20,并剛剛完成了19號柱面的請求。（10分）操作系統(tǒng)試卷B答案、單項選擇題（每空2分，共20分）12345678910ACDDCBADAC、判斷題（5*2分）1.錯2.對3.錯4.錯[5?錯三、填空題（5*2分）中斷和通道索引文件目錄邏輯物理預防四、簡答題（4*5分）1.由于文件存儲設(shè)備是分成若干個大小相等的物理塊 ，并以塊為單位來交換信息的，因此,文件存儲空間的管理實質(zhì)上是空閑塊的組織和管理問題 ，它包括空閑塊的組織、空為所有的空閑文件建立一個單獨的目錄表。每個表目對應一個空閑文件 ，記錄該空閑文件的起始塊號和塊數(shù)?？臻e文件的分配與回收算法與內(nèi)存管理中的可變式分區(qū)管理的方法相似，同樣可以采用最先適應算法、最佳適應算法、最壞適應算法等。閑塊的分配與回收等。下面是三種在文件存儲空間的管理中常用的技術(shù) ：(1)空閑文件目錄。一個空閑文件是由文件存儲器上連續(xù)的空閑塊組成的。系統(tǒng)空閑塊鏈。空閑塊鏈把文件存儲設(shè)備上的所有空閑塊鏈接在一起。當申請者需要空閑塊時，分配程序從鏈首取下所需的空閑塊 ，然后調(diào)整鏈首指針。反之，當回收空閑塊時，把釋放的空閑塊逐個插入空閑鏈上。這種方法的優(yōu)點是分配和回收一個空閑塊的過程都非常簡單，缺點是空閑塊鏈可能很長。改進的辦法是采用空閑盤區(qū)鏈接法或成組鏈接法。位示圖。位示圖利用一個二進制位來記載一個物理塊的使用情況。系統(tǒng)為每個文件存儲設(shè)備建立一張位示圖，反映文件存儲設(shè)備所有物理塊的使用情況。每個物理塊對應位示圖上的一位，如果該位為0,則表示所對應的塊是空閑的：反之，則表示所對應的塊已被分配。利用位圖來進行空閑塊分配時 ，只需查找圖中為0的位，并將其置1；反之，回收時只需把相應的位由1改為0。由于位示圖很小，可以將它保存在內(nèi)存中。2.所有字符設(shè)備都是獨享設(shè)備并屬于慢速設(shè)備 ，本質(zhì)上屬于順序存取設(shè)備。因此，一個進程在某臺字符設(shè)各上進行數(shù)據(jù)交換時 ，往往要等待較長時間，并且在該數(shù)據(jù)交換完成之前，其他進程不能同時訪問這臺設(shè)備。而且動態(tài)分配也不能真正提高這類設(shè)備的利用率，當一個進程正在使用這類設(shè)備進行一次較大量的數(shù)據(jù)交換時 ，其他需要同時訪問該設(shè)備的進程就要等待較長的時間，從而降低了整個系統(tǒng)的并發(fā)能力。 SPOOLing技術(shù)正是針對上述問題提出的一種設(shè)備管理技術(shù)。SPOOLing系統(tǒng)可帶來的好處如下：字符設(shè)備和各虛擬設(shè)備之間的數(shù)據(jù)交換由 SPOOLing進程統(tǒng)一調(diào)度實施，而切這種數(shù)據(jù)交換以并行方式進行，系統(tǒng)呈現(xiàn)出高度的并行性：用戶使用的是虛擬設(shè)備，可以減少用戶進程的等待時間。在多道程序系統(tǒng)中，用程序模擬脫機輸入/輸出時外圍控制機的功能，這樣便可在主機的直接控制下實現(xiàn)脫機輸入/輸出功能。此時的外圍操作與CPU對數(shù)據(jù)的處理同時進行，這種在聯(lián)機情況下實現(xiàn)的外圍設(shè)備同時操作稱為 SPOOLing,也稱偽脫機。SPOOLing系統(tǒng)的核心思想是利用一臺可共享、高速、大容量的塊設(shè)備(磁盤)來模擬獨占設(shè)備的操作，使一臺獨占設(shè)備變成多臺可并行使用的虛擬設(shè)備。 SPOOLing系統(tǒng)主要由輸入井和輸出井、輸入緩沖區(qū)和輸出緩沖區(qū)、輸入進程和輸出進程三部分組成。它的好處是提高了I/O操作的速度，將獨占設(shè)備改造為共享設(shè)備，實現(xiàn)了虛擬設(shè)備的功能。3.進程和線程是構(gòu)造操作系統(tǒng)的兩個基本元素 ，兩者之間的主要區(qū)別是:(1)調(diào)度方面：線程作為調(diào)度分派的基本單位。并發(fā)性方面：進程之間可以并發(fā)執(zhí)行。擁有資源方面：進程是擁有資源的基本單位本上不擁有資源，但它可以訪問其隸屬進程的資源。(4)到進程環(huán)境的切換，線程除少量必不可少的資源外，基P(S)__一— H4-t正票者｛y.系統(tǒng)開銷：進程間切換時要涉及，開銷比較大：而線程間切換只需保存和設(shè)置少量的寄存器內(nèi)容，因此進程間切換的系統(tǒng)開銷遠大于線程間切換的系統(tǒng)開銷。4.互斥控制。進程對所要求的資源進行排它控制一個進程使用。不可剝奪控制。進程所獲得的資源在未釋放前，在一段時間內(nèi)一個資源僅能被，不能被其它進程剝奪。即使該，只有等待占有該資源的進程釋進程處于阻塞態(tài)，它所占資源也不能被其它進程使用放后才能給別的進程使用。請求和保持。為了提高資源利用率，進程在運行過程中可隨時提出對各種資源的請求，當進程因請求資源而阻塞時，對已獲得的資源保持不放。環(huán)路等待條件。在發(fā)生死鎖時，進程的資源狀態(tài)圖必構(gòu)成環(huán)路，即前一進程保存著后一進程所要求的資源。P(Src)rc=rc+1rc=1?YP(Srw)P(Src)P(S)在數(shù)據(jù)庫中查詢所需的信息P(S「c)Rc=ro1Rc=ro1五、計算(40分)1.(15分)本題是典型的讀者一寫者問題。查詢操作是讀者 ，訂票操作是寫者，而且要求寫者優(yōu)先。為了達到這一控制效果，可以引入一個變量 rc,用于記錄當前正在運行的讀者進程數(shù)。每個讀者進程進入系統(tǒng)后需對 rc值加1。當rc值由O變?yōu)?時，說明是第一個讀者進程進入，因此需要該讀者進程對控制寫者進程的信號量 Srw進行P操作，以便與寫者進程互斥運行：當rc值由非0值增加時，說明不是第一個讀者進程，此時控制寫者進程的信號量已經(jīng)過P操作控制禁止寫者進程進入，因此不需要再次對該信號量進行 P操作。當讀者進程退出時，需對rc做減1操作。如發(fā)現(xiàn)減1后m值變?yōu)?,說明是最后一個讀者進程退出，因此需要該讀者進程對控制寫者進程的信號量 Srw進行V操作，以便使寫者進程能夠進入。資源計數(shù)變量 rc也是一個臨界資源，需要用信號量Src對它進行互斥訪問控制。為了提高寫者的優(yōu)先級 ，我們還增加了一個信號量 S,用以在寫進程到達時封鎖其后續(xù)的讀者進程。用戶查詢與訂票的邏輯框圖如圖所示。查詢者V(Srw)LV(頃c)用戶查詢與訂票的邏輯框圖(15分)⑴FCFS算法的頁面置換如下:時刻123456789101112頁面走向432143543215M=44+3+2+1+115+4+3+2+1+5+43222154321433321543244④③①⑤④3標志++++++++++缺頁次數(shù)F=10,缺頁中斷率10/12=83%⑵LRLI算法的頁面置換如下:時刻123456789101112貞而走向432143543215M=44+3+2+1+435+432+1+5+43214354321432143543243②111⑤④3標心++++++++缺頁次數(shù)F=8,缺頁中斷率8/12=67%（10分）該題的解題方法是先計算出每種算法的柱面移動總量。因為每個柱面移動需要 6ms,所以，尋道時間=柱面移動總量x6ms⑴先到先服務算法的調(diào)度順序為 ：10,2