名校操作系統(tǒng)歷年考研試題(共70頁)

1、精選優(yōu)質(zhì)文檔-傾情為你奉上名校操作系統(tǒng)考研試題與解答10.1北京大學1997年考研操作系統(tǒng)試題(一)名詞術語解釋(每小題5分,共30分)1.進程狀態(tài) 2.快表 3.目錄項4.系統(tǒng)調(diào)用 5.設備驅(qū)動程序 6.微內(nèi)核(二)填空(每小題1分,共10分)1.如果系統(tǒng)中有n個進程,則在等待隊列中進程的個數(shù)最多為_個。2.在操作系統(tǒng)中,不可中斷執(zhí)行的操作稱為_。3.如果系統(tǒng)中的所有作業(yè)是同時到達的,則使作業(yè)平均周轉(zhuǎn)時間最短的作業(yè)調(diào)度是_。4.如果信號量的當前值為-4,則表示系統(tǒng)中在該信號量上有_個等待進程。5.在有m個進程的系統(tǒng)中出現(xiàn)死鎖時,死鎖進程的個數(shù)k應該滿足的條件是_。6.不讓死鎖發(fā)生的策略可以分

2、為靜態(tài)和動態(tài)兩種,死鎖避免屬于_。7.在操作系統(tǒng)中,一種用空間換取時間的資源轉(zhuǎn)換技術是_。8.為實現(xiàn)CPU與外部設備的并行工作,系統(tǒng)引入了_硬件機制。9.中斷優(yōu)先級是由硬件規(guī)定的,若要調(diào)整中斷的響應次序可通過_。10.若使當前運行的進程總是優(yōu)先級最高的進程,應選擇_進程調(diào)度算法。(三)問答題(每小題15分,共30分)1.消息緩沖通信技術是一種高級通信機制,由Hansen首先提出。(1)試述高級通信機制與低級通信機制P、V原語操作的主要區(qū)別。(2)請給出消息緩沖機制(有界緩沖)的基本原理。(3)消息緩沖通信機制(有界緩沖)中提供發(fā)送原語Send(receiver,a),調(diào)用參數(shù)a表示發(fā)送消息的內(nèi)

3、存區(qū)首地址,試設計相應的數(shù)據(jù)結(jié)構(gòu),并用P、V原語操作實現(xiàn)Send原語。2.在虛擬段式存儲系統(tǒng)中,引入了段的動態(tài)鏈接。(1)試說明為什么引入段的動態(tài)鏈接。(2)請給出動態(tài)鏈接的一種實現(xiàn)方法。(四)(共10分)在實現(xiàn)文件系統(tǒng)時,為加快文件目錄的檢索速度,可利用"文件控制塊分解法"。假設目錄文件存放在磁盤上,每個盤塊為512字節(jié)。文件控制塊占64字節(jié),其中文件名占8字節(jié)。通常將文件控制塊分解成兩個部分,第一部分占10字節(jié)(包括文件名和文件內(nèi)部號),第二部分占56字節(jié)(包括文件內(nèi)部號和文件其他描述信息)。(1)假設某一目錄文件共有254個文件控制塊,試分別給出采用分解法前和分解法后

4、,查找該目錄文件的某一個文件控制塊的平均訪問磁盤次數(shù)。(2)一般地,若目錄文件分解前占用n個盤塊,分解后改用m個盤塊存放文件名和文件內(nèi)部號部分,請給出訪問磁盤次數(shù)減少的條件。(五)(共10分設系統(tǒng)中有三種類型的資源(A、B、C)和五個進程(P1、P2、P3、P4、P5),A資源的數(shù)量為17,B資源的數(shù)量為5,C資源的數(shù)量為20。在T0時刻系統(tǒng)狀態(tài)如表1和表2所示。系統(tǒng)采用銀行家算法實施死鎖避免策略。T0時刻是否為安全狀態(tài)? 若是,請給出安全序列。在T0時刻若進程P2請求資源(0,3,4),是否能實施資源分配? 為什么? 在的基礎上,若進程P4請求資源(2,0,1),是否能實施資源分配? 為什么

5、?在的基礎上,若進程請求資源(0,2,0),是否能實施資源分配? 為什么?表1 T0時刻系統(tǒng)狀態(tài)進程最大資源需求量已分配資源數(shù)量 A B C A B CP1P2P3P4P5 5 5 9 5 3 6 4 0 11 4 2 5 4 2 4 2 1 2 4 0 2 4 0 5 2 0 4 3 1 4表2 T0時刻系統(tǒng)狀態(tài)A B C剩余資源數(shù) 2 3 3(六)(共10分)某高校計算機系開設有網(wǎng)絡課并安排了上機實習,假設機房共有2m臺機器,有2n名學生選該課,規(guī)定:每兩個學生組成一組,各占一臺機器,協(xié)同完成上機實習；只有一組兩個學生到齊,并且此時機房有空閑機器時,該組學生才能進入機房；上機實習由一名教師

6、檢查,檢查完畢,一組學生同時離開機房。試用P、V操作模擬上機實習過程。北京大學1997年級研操作系統(tǒng)試題解答(一)名詞術語解釋(每小題5分,共30分)1.進程在其存在過程中,由于各進程并發(fā)執(zhí)行及相互制約,使得它們的狀態(tài)不斷發(fā)生變化。一般來說進程主要有三種基本狀態(tài),這三種基本狀態(tài)是:就緒狀態(tài)、運行狀態(tài)和阻塞狀態(tài)。2.在頁式存儲管理系統(tǒng)中的地址變換過程中,由于頁表是存放在內(nèi)存中的,CPU每訪問一個數(shù)據(jù)(或一條指令)至少要訪問內(nèi)存兩次,一次是訪問頁表,確定所取數(shù)據(jù)(或指令)的物理地址,第二次才根據(jù)該地址訪問數(shù)據(jù)(或指令)。為了提高查表速度,在地址變換機構(gòu)中加入了一個高速、小容量的聯(lián)想寄存器,構(gòu)成一張

7、快表。如果快表被命中,只要訪問內(nèi)存一次即可存取一個數(shù)據(jù)。3.在文件系統(tǒng)中,文件目錄記錄文件的管理信息,每個文件在目錄表中都有一個目錄項。文件目錄項主要包含下列信息:(1)有關文件的標識信息,例如文件的名稱符號。(2)有關文件結(jié)構(gòu)的信息,例如文件長度、文件存放在外存中的物理地址等。(3)有關文件的存取控制信息,例如文件屬性、文件主及共享用戶的標識、存取權限等。(4)有關文件的管理信息,例如文件建立的時間、保留時間、最新修改時間等。4.系統(tǒng)調(diào)用是用戶在程序中能用"訪管指令"調(diào)用的由操作系統(tǒng)提供的子功能的集合。每一個子功能稱為一條系統(tǒng)調(diào)用命令(或廣義指令)。系統(tǒng)調(diào)用是操作系統(tǒng)在程

8、序級給用戶提供的接口。系統(tǒng)調(diào)用與一般過程調(diào)用不同,其主要區(qū)別是:運行的狀態(tài)不同:進入的方式不同:代碼層次不同。5設備驅(qū)動程序也稱為I/O處理程序,是一種低級的系統(tǒng)例程,它向上與高級I/0操作原語相對應,向下與I/0硬設備相對應,完成兩者間的相互通信。它們一般是用匯編語言編寫,針對具體的I/0設備控制器,進行控制編碼或微程序操作。設備驅(qū)動程序早期是操作系統(tǒng)的一部分,后來將其中的公共部分作為高級I/O操作原語留在操作系統(tǒng)中,而把與物理設備有直接關系的部分脫離操作系統(tǒng),交給設備廠商和軟硬件開發(fā)商編制。因此,設備驅(qū)動程序己成為系統(tǒng)的選件,系統(tǒng)和用戶可以根據(jù)需要選擇配置設備,靈活地裝載、卸載驅(qū)動程序,從

9、而極大地增強了系統(tǒng)的開放性和可擴展性。6.操作系統(tǒng)有兩種內(nèi)核組織形式:強內(nèi)核(Monolithic kernel)和微內(nèi)核(Micro kernel)。微內(nèi)核結(jié)構(gòu)是一種新的結(jié)構(gòu)組織形式,它體現(xiàn)了操作系統(tǒng)結(jié)構(gòu)設計的新思想。其設計目標是使操作系統(tǒng)的內(nèi)核盡可能小,使其它所有操作系統(tǒng)服務都放在核外用戶級完成。微內(nèi)核僅僅提供以下四種服務:進程間通信機制:某些存儲管理:有限的低級進程管理和調(diào)度:低級I/0。微內(nèi)核的基本思想是良好的結(jié)構(gòu)化、模塊化,最小的公共服務。具有微內(nèi)核的操作系統(tǒng)稱為微內(nèi)核操作系統(tǒng)。(二)填空(每小題1分,共10分)1.n-1 2.原語 3.短作業(yè)優(yōu)先算法 4.四 5.km6.動態(tài)策略

10、7.緩沖區(qū)技術 8.中斷和通道 9.軟件實現(xiàn) 10.剝奪式優(yōu)先級(三)問答題(每小題15分,共30分)1.(見西安交大2000年考題中第五題的解答)2.(1)在作業(yè)裝入內(nèi)存運行前,應將各個目標程序定位后裝入作業(yè)的地址空間,形成可執(zhí)行程序的鏈接,稱為靜態(tài)鏈接。靜態(tài)鏈接常常因為目標程序個數(shù)多而花費大量的CPU時間,而實際運行時又常常只用到其中的部分模塊,因而也造成了存儲空間的浪費。動態(tài)鏈接是作業(yè)運行時先裝入主程序,運行過程中需要某模塊時,再將該模塊的目標程序調(diào)入內(nèi)存并進行鏈接,它克服了靜態(tài)鏈接的不足。(2)分段存儲管理就是最典型的動態(tài)鏈接。分段管理允許用戶將作業(yè)按邏輯關系進行自然分段,各段的大小可

11、以不同。邏輯段內(nèi)的地址是由兩部分組成的(s: 段號,d：段內(nèi)位移量),即分段地址空間是用戶定義的二維空間。內(nèi)存分配以段為單位,段可以在作業(yè)運行過程中根據(jù)請求而動態(tài)鏈接和裝入。(四)(共10分)利用"文件控制塊分解法"加快文件目錄的檢索速度,其原理是減少因查找文件內(nèi)部號而產(chǎn)生的訪問磁盤次數(shù)。因為在進行查找文件內(nèi)部號的過程中不需要把文件控制塊的所用內(nèi)容都讀入內(nèi)存,所以在查找過程中減少所需讀入的存儲塊就有可自色減少訪問磁盤的次數(shù)。但是,采用這種方法訪問文件,當找到匹配的文件控制塊后,還需要訪問一次磁盤,才能讀出全部的文件控制塊信息。這就是為何采用這種方法在一定條件下并不能減少訪問

12、磁盤的次數(shù)的原因。(1)采用分解法前,查找該目錄文件的某一個文件控制塊的平均訪問磁盤次數(shù)為:64×(254/2)/512=16采用分解法后,查找該目錄文件的某一個文件控制塊的平均訪問磁盤次數(shù)為:10×(254/2)/512+1=4(2)訪問磁盤次數(shù)減少的條件為 64×(x/2)/512 > 10×(x/2)/512+1，解不等式得x>=19時訪問磁盤的次數(shù)減少。(五)(共10分)T0時刻是安全狀態(tài),因為可以找到一個安全的序列(P4,P5,Pl,P2,P3)。不能分配。因為所剩余的資源數(shù)量不夠?？梢苑峙洹．敺峙渫瓿珊?系統(tǒng)剩余的資源向量為(0,

13、3,2),這時仍可找到一個安全的序列隊, (P4,P5,Pl,P2,P3)。不能分配。若分配完成后,系統(tǒng)剩余的資源向量為(0,3,勻,這時無法找到一個安全的序列。(六)(共10分)在本題中,為了保證系統(tǒng)的控制流程,增加了Monitor進程,用于控制學生的進入和計算機分配。從題目本身來看,雖然沒有明確寫出這一進程,但實際上這一進程是存在的。因此,在解決這類問題時,需要對題目加以認真分析,找出其隱蔽的控制機制。上機實習過程可描述如下: BEGINstudent,computer,enter,finish,check:semaaphore; studen:=0;computer:=2m; mter:

14、=0;finish :=O;check :=0;COBEGINProcess Procedure Student:beginV(student); 表示有學生到達P(computer); 獲取一臺計算機P(enter); 等待允許進入DO it with partner;V(finish); 表示實習完成P(check); 等待教師檢查V(computer); 釋放計算機資源endProcess Procedure Teacher:beginL1:P(finished); 等待學生實習完成P(finished); 等待另一學生實習完成check the work;V(check); 表示檢查完

15、成V(check); 表示檢查完成goto L1;endProcess Procedure MonitorbeginL2: P(student); 等待學生到達P(student); 等待另一學生到達V(enter); 允許學生進入V(enter); 允許學生進入endCoendEND10.2西安交通大學1999年考研操作系統(tǒng)試題(一)名詞解釋(30分,每小題5分)1.多道程序設計 2.工作目錄3.線程與進程 4.地址空間與存儲空間5.通道 6.系統(tǒng)調(diào)用(二)判斷、選擇與填空題(每題1分,共15分)1.程序的并發(fā)執(zhí)行是指同一時刻有兩個以上的程序,它們的指令在同一處理器上執(zhí)行。()2.對于請求分

16、頁式存儲管理系統(tǒng),若把頁面的大小增加一倍,則缺頁中斷次數(shù)會減少一半。()3.三個用戶在同一系統(tǒng)上同時對他們的C語言源程序進行編譯,此時系統(tǒng)應分別為各用戶創(chuàng)建一個C編譯進程及保留一份C編譯程序副本。()4.可順序存取的文件不一定能隨機存取,但是,凡可隨機存取的文件都可以順序存取。()5.緩沖技術是借用外存儲器的一部分區(qū)域作為緩沖池。()6.在操作系統(tǒng)中,P、V操作是一種_。(A)機器指令 (B)系統(tǒng)調(diào)用命令(C)作業(yè)控制命令 (D)低級進程通訊原語7.最佳適應算法的空白區(qū)是_。(A)按大小遞減順序排列的 (B)按大小遞增順序排列的(C)按地址由小到大排列的 (D)按地址由大到小排列的8.把作業(yè)地

17、址空間中使用的邏輯地址變成內(nèi)存中的物理地址稱為_。(A)加載 (B)重定位 (C)物理化 (D)邏輯化9.文件系統(tǒng)用_組織文件。(A)堆核 (B)指針 (C)目錄 (D)路徑10.磁盤是設備,磁帶是設備,顯示器是_設備。(A)輸入 (B)輸出 (C)輸入輸出 (D)虛擬11.并發(fā)進程中涉及相同變量的程序段叫做_,對這些程序段要執(zhí)行_。12.分區(qū)存儲管理方案不能實現(xiàn)虛擬的原因是_。13.目前認為邏輯文件有兩種類型,即_式文件與_式文件。14.進程調(diào)度算法采用等時間片輪轉(zhuǎn)法,時間片過大,就會使輪轉(zhuǎn)法轉(zhuǎn)化為_調(diào)度算法。15.采用交換技術獲得的好處是以犧牲_為代價的。(三)簡答題(每題10分,共50分

18、)1.試述分時系統(tǒng)與實時系統(tǒng),并比較它們的區(qū)別。2.何謂虛擬存儲器?舉一例說明操作系統(tǒng)是如何實現(xiàn)虛擬內(nèi)存的。3.什么是P、V操作? 試用P、V操作描述讀者一寫者問題。要求允許兒個閱讀者可以同時讀該數(shù)據(jù)集,而一個寫者不能與其他進程(不管是寫者還是讀者)同時訪問該數(shù)據(jù)集。4.磁盤請求的柱面按10,22,20,2,40,6,38的次序到達磁盤的驅(qū)動器,尋道時每個柱面移動需要6ms。計算按以下算法調(diào)度時的尋道時間:(1)先來先服務; (2)下一個最鄰近的柱面; (3)電梯算法。以上所有情況磁頭臂均起始于柱面20。5.對3種不同的保護機制,即權限,存取控制表以及UNIX操作系統(tǒng)的RWX位,簡述下面的情況

19、分別適用于哪些機制。(1)甲用戶希望除他的同事以外,任何人都能讀取他的文件;(2)乙用戶和丙用戶希望共享某些秘密文件;(3)丁用戶希望公開他的一些文件。西安交通大學1999年考研操作系統(tǒng)試題解答(一)名詞解釋(每小題5分,共30分)1.多道程序設計是指在主存中同時存放多道用戶作業(yè),它們都處于執(zhí)行的開始點和結(jié)束點之間。多道程序設計的特點如下:(1)多道。主存中有多道程序,它們在任一時刻必須處于就緒、運行、阻塞三種狀態(tài)之一。(2)宏觀上并行。從宏觀上看,它們在同時執(zhí)行。(3)微觀上串行。從微觀上看,它們在交替、穿插地執(zhí)行。采用多道程序設計后,減少了CPU時間的浪費。尤其對計算題的作業(yè),由于I/O操

20、作較少,CPIJ浪費的時間很少。2.文件系統(tǒng)如果采用多級樹型目錄,那么使用完整的路徑名來查找文件會感到很不方便,因此引入了"工作目錄"?？紤]到通常一個進程在一段時間內(nèi)所訪問的文件具有局部性,即在某一范圍之內(nèi),所以可在這一段時間內(nèi)指定某一目錄為工作目錄或值班目錄。以后的操作一般都是針對以工作目錄(也稱為當前目錄)為根的子目錄樹進行的。3.所謂線程(thread),從操作系統(tǒng)的管理角度看,就是指"進程的一個可調(diào)度實體",是處理機調(diào)度的基本單位:從編程邏輯看,線程是指"程序內(nèi)部的一個單一的順序控制流"。線程是進程的一個組成部分,每個進程在創(chuàng)

21、建時通常只有一個線程,由這個線程再創(chuàng)建其它進程。通常一個進程都有若干個線程,至少會有一個線程。進程和線程是構(gòu)造操作系統(tǒng)的兩個基本元素,兩者之間的主要區(qū)別是:(1)調(diào)度方面: 線程作為調(diào)度分派的基本單位。(2)并發(fā)性方面: 進程之間可以并發(fā)執(zhí)行。(3)擁有資源方面: 進程是擁有資源的基本單位,線程除少量必不可少的資源外,基本上不擁有資源,但它可以訪問其隸屬進程的資源。(4)系統(tǒng)開銷: 進程間切換時要涉及到進程環(huán)境的切換,開銷比較大。而線程間的切換只需保存和設置少量的寄存器內(nèi)容。因此進程問切換的系統(tǒng)開銷遠大于線程問切換的系統(tǒng)開銷。4.程序經(jīng)編譯和連接以后轉(zhuǎn)變?yōu)橄鄬Φ刂肪幹沸问?它是以0為基址的。相

22、對地址也叫邏輯地址或虛地址。地址空間是邏輯地址的集合。計算機系統(tǒng)實際的內(nèi)存地址是絕對地址。絕對地址又叫物理地址或?qū)嵉刂?。存儲空間是物理地址的集合。5.通道又稱I/O處理機,它使主機擺脫了管理I/O的工作,徹底實現(xiàn)了主機和外設的并行操作。具有通道結(jié)構(gòu)的計算機系統(tǒng),主存、通道、控制器和設備之間采用四級連接,實施三級控制。這樣,I/O系統(tǒng)就由通道、控制器、設備三級構(gòu)成。一個CPU可以連接多個通道,一個通道可以連接多個控制器,一個控制器可以連接同類型的多臺設各。另一方面,也允許將一臺設備連接到幾個控制器上,或一個控制器連接到幾個通道上。按信息交換方式和連接的設備類型不同,可以將通道分為三種類型:(1)

23、字節(jié)多路通道；(2)選擇通道；(3)數(shù)組多路通道 6.系統(tǒng)調(diào)用是用戶在程序中能用"訪管指令"調(diào)用的由操作系統(tǒng)提供的子功能的集合。每一個子功能稱為一條系統(tǒng)調(diào)用命令或廣義指令。系統(tǒng)調(diào)用是操作系統(tǒng)在程序級給用戶提供的接口。(二)判斷、選擇與填空題(每題1分,共15分)1.錯 2.錯 3.錯 4.對 5.錯 6.(D)7.(B) 8.(B) 9.(C) 10.(C)和(D),(C),(B)11.臨界區(qū) 互斥 12.作業(yè)的地址空間不能超過存儲空間 13.有結(jié)構(gòu)的記錄 無結(jié)構(gòu)的流 14.先來先服務(FCFS)15.CPU時間(三)簡答題(每題10分,共50分)1.所謂分時系統(tǒng),就是在一

24、臺計算機上,連接多個終端,用戶通過各自的終端和終端命令把作業(yè)送入計算機,計算機又通過終端向各用戶報告其作業(yè)的運行情況,這種計算機能分時輪流地為各終端用戶服務并能及時對用戶服務請求予以響應,這就構(gòu)成了分時系統(tǒng)。分時系統(tǒng)設計的主要目標是使用戶能與系統(tǒng)交互作用,對用戶的請求及時響應,并在可能的條件下盡量提高系統(tǒng)資源的利用率。實時系統(tǒng)是為了能對特定輸入做出及時響應,并在規(guī)定的時間內(nèi)完成對該事件的處理而引入的。實時系統(tǒng)分為兩大類z實時控制系統(tǒng)和實時信息處理系統(tǒng)。(1)實時控制系統(tǒng): 在這類應用中要求計算機系統(tǒng)實時采集測量系統(tǒng)的數(shù)據(jù),對被測量的數(shù)據(jù)及時進行加工處理及輸出。它主要用于軍事和生產(chǎn)過程中的自動控

25、制領域。(2)實時信息處理系統(tǒng)：在這類應用中要求計算機系統(tǒng)能對用戶的服務請求及時作出回答,并能及時修改、處理系統(tǒng)中的數(shù)據(jù)。它主要用于像飛機票的預定、銀行儲蓄的財務管理等大量數(shù)據(jù)處理的實時系統(tǒng)中。實時系統(tǒng)與分時系統(tǒng)的主要區(qū)別如下:系統(tǒng)的設計目標不同。分時系統(tǒng)的設計目標是提供一種隨時可供多個用戶使用的通用性很強的系統(tǒng):而實時系統(tǒng)則大多數(shù)都是具有某種特殊用途的專用系統(tǒng)。響應時間的長短不同。分時系統(tǒng)的響應時間通常為秒級:而實時系統(tǒng)的響應時間通常為毫秒級甚至是微秒級。交互性的強弱不同。分時系統(tǒng)的交互性強,而實時系統(tǒng)的交互性相對較弱。2.在操作系統(tǒng)中,通過一些硬件和軟件的措施為用戶提供了一個其容量比實際主

26、存大得多的存儲器,稱為虛擬存儲器。操作系統(tǒng)要實現(xiàn)虛擬內(nèi)存,必須把主存和輔存統(tǒng)一管理起來,即大作業(yè)程序在執(zhí)行時,有一部分地址空間在主存,另一部分在輔存,當訪問的信息不在主存時,由操作系統(tǒng)將其調(diào)入主存并實現(xiàn)自動覆蓋功能,使用戶在編寫程序時不再受主存容量的限制。例如在請求分頁存儲管理系統(tǒng)中,用戶作業(yè)的所有頁面并不一定都在實存,在作業(yè)運行過程中再請求調(diào)入所用的虛頁。為了實現(xiàn)從邏輯地址空間到物理地址空間的變換,在硬件上必須提供一套地址變換機構(gòu),動態(tài)地址變換機構(gòu)自動地將所有的邏輯地址劃分為頁號和頁內(nèi)地址兩部分,并利用頁表將頁號代之以塊號,把塊號和頁內(nèi)地址拼接就得到了內(nèi)存的物理地址,從而實現(xiàn)了虛擬存儲器。3

27、.讀者一寫者問題是經(jīng)常出現(xiàn)的一種同步問題。計算機系統(tǒng)中的數(shù)據(jù)(文件、記錄)常被多個進程共享,但其中某些進程可能只要求讀數(shù)據(jù)(稱為Reader):另一些進程則要求修改數(shù)據(jù)(稱為Writer)。就共享數(shù)據(jù)而言,Reader和Writer是兩種不同類型的進程。一般地,兩個或兩個以上的Reader進程同時訪問共享數(shù)據(jù)時不會產(chǎn)生副作用,但若某個Writer和其它進程(Reader或Writer)同時訪問共享數(shù)據(jù)時,則可能產(chǎn)生錯誤。為了避免錯誤,同時盡可能地讓讀者進程和寫者進程并發(fā)運行,只要保證任何一個寫者進程能與其它進程互斥訪問共享數(shù)據(jù)即可。這個問題稱為讀者一寫者問題。下面使用信號量機構(gòu)來描述這一問題。

28、P、V操作是定義在信號量s上的兩條原語,它是解決進程同步與互斥的有效手段。定義下列信號量: 互斥信號量rmutex,初值為1,用于使讀者互斥地訪問讀者計數(shù)器,共享變量rcount: 互斥信號量wmutex,初值為1,用于實現(xiàn)寫者之間以及寫者與讀者之間互斥地訪問共享數(shù)據(jù)集。則用信號量和P、V操作描述讀者一寫者問題如下:Beginrmutex wmutex:semaphore;rcount:Integer;rmutex=wmutex=1;rcount=0;CobeginProcess procedure Readerbeginrepeat P(rmutex);rcount:=rcount+1if

29、rcount=l then P(rmutex);V(rmutex);perfonn read operations;P(rmutex);rcount:=rcount-1;if rcount=O then V(rmutex);V(rmutex);until fa1se;endProcess procedure Writerbeginrepeat P(wmutex);perform write operations;V(wmutex);until false;endCoendEnd4.該題的解題方法是先計算出每種算法的柱面移動總量。因為每個柱面移動需要6ms,所以,尋道時間=柱面移動總量×

30、;6ms。(1)先到先服務算法的調(diào)度順序為:10,22,20,2,40,6,38柱面移動總量為:146尋道時間為:146×6ms=876ms(2)下一個最鄰近柱面算法調(diào)度順序為:20,22,10,6,2,38,40柱面移動總量為:60尋道時間為:60×6ms=360ms(3)電梯算法調(diào)度順序為:20,22,38,40,10,6,2柱面移動總量為:58尋道時間為58×6ms=348ms5.第(1)種情況只適合用存取控制表實現(xiàn)保護機制。第(2)種情況適合用權限或存取控制表實現(xiàn)保護機制。第(3)種情況適合用存取控制表或RWX位或權限實現(xiàn)保護機制。10.3西安交通大學20

31、00年考研操作系統(tǒng)試題(一)名詞解釋(15分)1.線程 2.分時系統(tǒng) 3.系統(tǒng)調(diào)用4.地址再定位 5.多道程序設計(二)簡答題(32分) 1.覆蓋技術與虛擬存儲技術有何本質(zhì)不同?交換技術與虛存中使用的調(diào)入/調(diào)出技術有何相同與不同之處?2.文件順序存取與隨機存取的主要區(qū)別是什么?它們對有結(jié)構(gòu)文件與無結(jié)構(gòu)文件的操作有何不同?3.死鎖和競爭有何關系? 4.何請?zhí)摂M設備? 請說明SPOOLing系統(tǒng)是如何實現(xiàn)虛擬設備的。(三)(10分)有5個任務A,B,C,D,E,它們幾乎同時到達,預計它們的運行時間為10,6,2,4,8mn。其優(yōu)先級分別為3,5,2,1和4,這里5為最高優(yōu)先級。對于下列每一種調(diào)度算

32、法,計算其平均進程周轉(zhuǎn)時間(進程切換開銷可不考慮)。(1)先來先服務(按A,B,c,D,E)算法。(2)優(yōu)先級調(diào)度算法。(3)時間片輪轉(zhuǎn)算法。(四)(10分)在虛擬頁式存儲系統(tǒng)中引入了缺頁中斷。1.試說明為什么引入缺頁中斷。2.缺頁中斷的實現(xiàn)由哪幾部分組成?并分別給出其實現(xiàn)方法。(五)(13分)消息緩沖通信技術是一種高級通信機制,由HANSEN首先提出。1.試敘述高級通信機制與低級通信機制P、V原語操作的區(qū)別。2.請給出消息緩沖通信機制(有界緩沖)的基本工作原理。3.試設計相應的數(shù)據(jù)結(jié)構(gòu),并用P、V原語操作實現(xiàn)Send和Receive原語。西安交通大學2000年考研操作系統(tǒng)試題解答(一)名詞解

33、釋(15分)1.所謂線程(thread),從操作系統(tǒng)管理角度看線程是指"進程的一個可調(diào)度實體",是處理機調(diào)度的基本單位: 從編程邏輯看線程是指"程序內(nèi)部的一個單一的順序控制流"。線程是進程的一個組成部分。2.所謂分時系統(tǒng),就是指在一臺計算機上,連接多個終端,用戶通過各自的終端和終端命令把作業(yè)送入計算機,計算機又通過終端向各用戶報告其作業(yè)的運行情況。這種計算機能分時輪流地為各終端用戶服務并能及時對用戶服務請求予以響應,這就構(gòu)成了分時系統(tǒng)。分時系統(tǒng)設計的主要目標是使用戶能與系統(tǒng)交互作用,對用戶的請求及時響應,并在可能的條件下盡量提高系統(tǒng)資源的利用率。分時系統(tǒng)

34、的主要特征是:同時性:若干個終端用戶按照系統(tǒng)提供的各種服務,在各自終端進行操作,同時使用一臺計算機資源。宏觀上看是各用戶在并行工作,微觀上看是各用戶輪流使用計算機。獨立性:用戶間可以相互獨立地操作,互不干涉,系統(tǒng)保證各用戶程序運行的完整性,不會發(fā)生相互混淆或破壞現(xiàn)象。及時性:系統(tǒng)可對用戶的輸入及時作出響應。分時系統(tǒng)性能的主要指標之一是響應時間,它是指從終端發(fā)出命令到系統(tǒng)予以應答所需的時間。交互性:用戶可根據(jù)系統(tǒng)對請求的響應結(jié)果,進一步向系統(tǒng)提出新的請求,即能使用戶和系統(tǒng)進行人一機對話的工作方式,所以分時系統(tǒng)也被稱之為交互式系統(tǒng)。3.系統(tǒng)調(diào)用是指用戶在程序中能用"訪管指令"調(diào)

35、用的由操作系統(tǒng)提供的子功能的集合。每一個子功能稱為一條系統(tǒng)調(diào)用命令(或廣義指令)。系統(tǒng)調(diào)用是操作系統(tǒng)在程序級給用戶提供的接口。4.所謂地址再定位,就是當一個程序裝入到與其地址空間不一致的存儲空間而進行的地址變換過程,即將地址空間給出的邏輯地址映射到內(nèi)存的物理地址。地址重定位有靜態(tài)重定位和動態(tài)重定位兩種方式。5.多道程序設計是指在主存中同時存放多道用戶作業(yè),它們都處于執(zhí)行的開始點和結(jié)束點之間。多道程序設計的特點如下:(1)多道。主存中有多道程序,它們在任一時刻必須處于就緒、運行、阻塞三種狀態(tài)之一。(2)宏觀上并行。從宏觀上看,它們在同時執(zhí)行。(3)微觀上串行。從微觀上看,它們在交替、穿插地執(zhí)行。

36、采用多道程序設計后,減少了CPU時間的浪費。尤其對計算題的作業(yè),由于I/O操作較少,CPU浪費的時間很少。(二)簡答題(32分)1.覆蓋技術與虛擬存儲技術最本質(zhì)的不同在于覆蓋的程序段的最大長度要受到物理內(nèi)存容量的限制,而虛擬存儲器的最大長度不受物理內(nèi)存容量的限制,只受計算機地址結(jié)構(gòu)的限制。另外,使用覆蓋技術要求程序員必須精心地設計程序及其數(shù)據(jù)結(jié)構(gòu),使得要覆蓋的段具有相對獨立性,不存在直接聯(lián)系或相互交叉訪問。而虛擬存儲技術對用戶的程序段之間沒有此要求。交換技術與虛存中使用的調(diào)入/調(diào)出技術的主要相同點是都要在內(nèi)存與外存之間交換信息。交換技術與虛存中使用的調(diào)入/調(diào)出技術的主要區(qū)別在于:交換技術換進換

37、出整個進程(proc結(jié)構(gòu)和共享正文段除外,因此一個進程的大小受物理存儲器的限制:而虛存中使用的調(diào)入/調(diào)出技術在內(nèi)存和外存之間來回傳遞的是存儲頁或存儲段,而不是整個進程,從而使得進程的地址映射具有了更大的靈活性,且允許進程的大小比可用的物理存儲空間大得多。2.順序存取法就是嚴格按物理記錄排列的順序依次存取:隨機存取法允許隨意存取文件中的任何一個物理記錄,而不管上次存取了哪一個記錄。順序存取法對有結(jié)構(gòu)文件的操作是設置一個訪問指針ptr,令它總是指向"下一次"要訪問的記錄首址。每訪問完一個記錄后,對ptr住進行相應的修改。對于定長記錄:ptr=ptr+L(L為文件的物理記錄長度)

38、:對于變長記錄:Ptr=ptr+Li+1(其中1是存放記錄長度Li的字節(jié)數(shù))。順序存取法對無結(jié)構(gòu)文件的操作是按讀寫位移(offset)從當前位置開始讀寫,即每讀寫完一段信息后,讀寫位移自動力日上這段的長度,然后再根據(jù)該位移讀寫下面的信息。隨機存取法對有結(jié)構(gòu)文件的操作也是設置一個訪問指針pt,對于定長記錄文件,欲訪問第I個記錄。(I=0,1,2,)的首址為: ptr=offset+I*L(其中,offest是該文件的首址,L為記錄長度):對于變長記錄,隨機存取法是十分低效的。隨機存取法對無結(jié)構(gòu)文件的操作必須事先用有關的命令把讀寫位移移到欲讀寫的信息開始處,然后再進行讀寫。3.死鎖是指多個進程因競

39、爭資源而造成的一種僵局,若無外力的作用,這些進程都將永遠不能再向前推進。所以,死鎖是由于系統(tǒng)中多個進程所共享的資源不足以同時滿足需要時,引起對資源的競爭而產(chǎn)生的。但競爭資源不定都會產(chǎn)生死鎖,因為只要進程推進順序合法,就不會產(chǎn)生死鎖。4.所謂虛擬設備,是指利用SPOOLing系統(tǒng)把低速的獨占設備改造成為共享的設備,或利用軟件方法把共享的設備分割為若干臺虛擬設備。SPOOLing系統(tǒng)的核心思想是利用一臺可共享的、高速大容量的塊設備(磁盤)來模擬獨占設各的操作,使一臺獨占設備變成多臺可并行使用的虛擬設備。SPOOLing系統(tǒng)主要由輸入井和輸出井、輸入緩沖區(qū)和輸出緩沖區(qū)、輸入進程和輸出進程三部分組成。

40、它的特點是提高了I/O操作的速度:將獨占設備改造為共享設備;實現(xiàn)了虛擬設備功能。(三)(10分)(1)采用FCFS的調(diào)度算法時,各任務在系統(tǒng)中的執(zhí)行情況如下表所示:執(zhí)行次序運行時間優(yōu)先數(shù)等待時間周轉(zhuǎn)時間A103010B651016C221618D411822E842230所以,進程的平均周轉(zhuǎn)時間為:T=(10+16+18+22+3O)/5=19.2 min(2)采用優(yōu)先級調(diào)度算法時,各任務在系統(tǒng)中的執(zhí)行情況如下表所示:執(zhí)行次序運行時間優(yōu)先數(shù)等待時間周轉(zhuǎn)時間B6506E84614A1031424C222426D112627所以,進程的平均周轉(zhuǎn)時間為:T=(6+14+24+26+27)/5=19.

41、4 min(3)采用時間片輪轉(zhuǎn)算法時,假定時間片為2min,各任務的執(zhí)行情況是:(A,B,C,D,E),(A,B,D,E),(A,B,E),(A,E),(A)。設AE五個進程的周轉(zhuǎn)時間依次為T1T5,顯然,T1=3Omin, T2=22min, T3=6min,T4=16min,T5=28min所以,進程的平均周轉(zhuǎn)時間為:T=(30+22+6+16+28)/5=20.4min(四)(10分)1.因為虛擬頁式存儲系統(tǒng)中允許作業(yè)的一部分頁面在內(nèi)存,只有引入缺頁中斷,才能將不在內(nèi)存的信息頁從外存調(diào)入內(nèi)存,中斷恢復后可以繼續(xù)執(zhí)行。2.缺頁中斷的實現(xiàn)由硬件和軟件兩部分組成。其實現(xiàn)方法如下:每當CPU要執(zhí)

42、行一條指令時,首先形成操作數(shù)的有效地址,在計算頁號和頁內(nèi)地址,檢查頁表看該頁在實存嗎。如在,則進行地址變換,按變換后的地址取出操作數(shù),完成該指令的功能,然后繼續(xù)進行下一條指令; 如不在,則引起缺頁中斷,進入缺頁中斷處理程序。在中斷處理程序中,首先利用存儲器分塊表(MBT)檢查實存是否有空閑頁面,如無,則選擇某頁淘汰。若該頁被修改過還需寫入輔存,并修改PMT和MBT,此時便出現(xiàn)了空閑實頁。如有空閑實頁,則根據(jù)輔助頁表提供的磁盤地址調(diào)入所需的頁面,修改PMT和MBT。最后再重新執(zhí)行被中斷的指令。(五)(13分)1.高級通信機制與低級通信機制P、V原語操作的主要區(qū)別是:(1)交換信息量方面:利用p、

43、v原語操作作為進程間的同步互斥工具是理想的,但進程間只能交換一些信息,基本上只能是控制信息,缺乏傳輸消息的能力。而高級通信不僅能較好地解決進程間的同步互斥問題,且能很好交換大量消息,是理想的進程通信工具。(2)通信對用戶透明方面:用戶要用P、V原語進行進程間的通信必須在程序中增加p、V編程,這樣做不但增加了編程的復雜性,不便對程序有直觀的理解,同時由于編程不當,有可能出現(xiàn)死鎖,難以查找其原因。而高級通信機制不但能高效傳輸大量信息,且操作系統(tǒng)隱藏了進程通信的實現(xiàn)細節(jié),即通信過程對用戶是透明的。這樣就大大地簡化了通信程序編制上的復雜性。2.所謂消息(Message),是指一組信息,消息緩沖區(qū)是含有

44、如下信息的緩沖區(qū):指向發(fā)送進程的指針:Sptr指向下一信息緩沖區(qū)的指針:Nptr;消息長度: Size;消息正文: Text;消息緩沖通信機制的基本工作原理是:把消息緩沖區(qū)作為進程通訊的一個基本單位,為了實現(xiàn)進程之間的通訊,系統(tǒng)提供了發(fā)送原語Send(A)和接收原語Receive(B)。每當發(fā)送進程欲發(fā)送消息時,發(fā)送進程用Send(A)原語把欲發(fā)送的消息從發(fā)送區(qū)復制到消息緩沖區(qū),并將它掛在接收進程的消息隊列末尾。如果該接收進程因等待消息而處于阻塞狀態(tài),則將其換醒。而每當接收進程欲讀取消息時,就用接收原語Receive(B)從消息隊列頭取走一個消息放到自己的接收區(qū)。3.消息緩沖通信機制中,消息隊

45、列屬于臨界資源,故在PCB中設置了一個用于互斥的信號量mutex,而每當有進程要進入消息隊列時,應對信號量mutex施行P操作,退出消息隊列后,應對信號量mutex施行V操作。由于接受進程可能會收到幾個進程發(fā)來的消息,故應將所有的消息緩沖區(qū)鏈成一個隊列,其隊頭由接收進程PCB中的隊列頭指針Hptr指出。為了表示隊列中的消息的數(shù)目,在PCB中設置了信號量旬,每當發(fā)送進程發(fā)來一個消息,并將它掛在接收進程的消息隊列上時,便在Sn上執(zhí)行V操作:而每當接收進程從消息隊列上讀取一個消息時,先對Sn執(zhí)行P操作,再從隊列上移出要讀取的消息。用P、V原語操作實現(xiàn)Send原語和Receive原語的處理流程如下:P

46、rocedure Send(receiver,Ma) 發(fā)送原語begingetbuf(Ma, size,i); 申請消息緩沖區(qū)i.sender:=Ma.Sender; 將發(fā)送區(qū)的信息發(fā)送到消息緩沖區(qū)i.size:=Ma.Size;i.text:=Ms.text;i.next:=0;getid(PCB set,receive,j); 獲得接收進程的內(nèi)部標識符P(j.mutex);insert(j.Hptr,i); 消息緩沖區(qū)插入到消息隊列首V(j.Sn);V(j.mutex); endProcedure Receive(Mb) 接收原語 beginj:internal name; 接收進程內(nèi)部標

47、識符P(j.Sn);P(j.mutex);remove(j.Hptr,i); 從消息隊列中移出第一個消息V(j.mutex);Mb.Sender:=i.Sender; 將消息緩沖區(qū)中的信息復制到接收區(qū)Mb.Size:=i.Size:Mb.text:=i.text:End10.4 西安電子科技大學2000年考研操作系統(tǒng)試題(一)單項選擇題(10分)1.分頁式虛擬存儲管理系統(tǒng)中,一般來說頁面的大小與可能產(chǎn)生缺頁中斷的次數(shù)_。A.成正比 B.成反比 C.無關 D.成固定比值2.實時操作系統(tǒng)必須在_內(nèi)完成來自外部的事件。A.響應時間 B.周轉(zhuǎn)時間 C.規(guī)定時間 D.調(diào)度時間3.早期UNIX操作系統(tǒng)的存

48、儲管理采用_方案。A.段式管理 B.請求分頁C.可變式分區(qū)管理 D.固定式分區(qū)管理4.在下列語言中屬于脫機作業(yè)控制語言的是_。A.作業(yè)控制語言 B.匯編語言C.會話式程序設計語言 D.解釋BASIC語言5.MS-DOS中的文件物理結(jié)構(gòu)采用_。A.連續(xù)結(jié)構(gòu) B.鏈接結(jié)構(gòu) C.索引結(jié)構(gòu) D.哈希表6.在請求分頁存儲管理方案中,如果所需的頁面不在內(nèi)存中,則產(chǎn)生缺頁中斷,它屬于_中斷。A.硬件故障 B.I/O C.外 D.程序中斷7.設有四個作業(yè)同時到達,每個作業(yè)的執(zhí)行時間均為2小時,它們在一臺處理機上按單道方式運行,則平均周轉(zhuǎn)時間為_。A.1小時 B.5小時 C.2.5小時 D.8小時8.在關于SP

49、OOLING的敘述中,_描述是不正確的。A.SPOOLING系統(tǒng)中不需要獨占設備B.SPOOLING系統(tǒng)加快了作業(yè)執(zhí)行的速度C.SPOOLING系統(tǒng)使獨占設備變成共享設備D.SPOOLBNG系統(tǒng)利用了處理器與通道并行工作的能力。9.頁式虛擬存儲管理的主要特點是_。A.不要求將作業(yè)裝入到主存的連續(xù)區(qū)域 B.不要求將作業(yè)同時全部裝入到主存的連續(xù)區(qū)域C.不要求進行缺頁中斷處理D.不要求進行頁面置換10.下列文件中屬于邏輯結(jié)構(gòu)的文件是A.連續(xù)文件 B.系統(tǒng)文件 C.散列文件 D.流式文件(二)改錯題(對錯誤的命題,請說明原因)(10分)1.采用多道程序設計的系統(tǒng)中,系統(tǒng)的程序道數(shù)越多,系統(tǒng)的效率就越高

50、。2.特權指令只能在管態(tài)下執(zhí)行,而不能在算態(tài)下執(zhí)行。3.采用資源的靜態(tài)分配算法可以預防死鎖的發(fā)生。4.一個虛擬的存儲器,其地址空間的大小等于輔存的容量加上主存的容量。5.一個作業(yè)由若干個作業(yè)步組成,在多道程序設計的系統(tǒng)中這些作業(yè)步可以并發(fā)執(zhí)行。6.作業(yè)調(diào)度是處理機的高級調(diào)度,進程調(diào)度是處理機的低級調(diào)度。7.I/O交通管理程序的主要功能是管理主存、控制器和通道。8.移臂調(diào)度的目標是使磁盤旋轉(zhuǎn)周數(shù)最小。9.進程是一個獨立的運行單位,也是系統(tǒng)進行資源分配和調(diào)度的基本單位。10.作業(yè)的聯(lián)機控制方式適用于終端作業(yè)。(三)、填空題(9分)1.UNIX操作系統(tǒng)在結(jié)構(gòu)上分為兩個部分:_和_。2.把作業(yè)裝入內(nèi)存

51、中隨即進行地址變換的方式稱為_,而在作業(yè)執(zhí)行期間,當訪問到指令或數(shù)據(jù)時才進行地址變換的方式稱為_。3.死鎖產(chǎn)生的四個必要條件是:互斥控制、_、_、_。4.多道程序設計的引入給存儲管理提出了新的課題,應考慮的三個問題是_、_、_。5.在存儲管理方案中,可用上下限地址寄存器存儲保護的是_。6.在UNIX文件管理系統(tǒng)中,為了對磁盤空間的空閑塊進行有效的管理,采用的方法_。7.為了記錄設備的分配情況,操作系統(tǒng)應設置一張_和三個控制塊: 設備控制塊、_、_。8.I/O設備處理進程平時處于_狀態(tài),當_和_出現(xiàn)時被喚醒。(四)綜合題(21分)1.什么叫"可再入"程序? 它有什么特征?2.

52、簡述UNIX的進程調(diào)度的公式和算法。3.給出UNDE進程的調(diào)度狀態(tài),當子進程終止時,處于什么狀態(tài)?4.假設有4個記錄A、B、C、D存放在磁盤的某個磁道上,該磁道劃分為4塊,每塊存放一個記錄,安排如下表所示:塊號 1 2 3 4記錄號 A B C D現(xiàn)在要順序處理這些記錄,如果磁盤旋轉(zhuǎn)速度為2Oms轉(zhuǎn)一周,處理程序每讀出一個記錄后花5ms的時間進行處理。試問處理完這4個記錄的總時間是多少?為了縮短處理時間應進行優(yōu)化分布,試問應如何安排這些記錄?并計算處理的總時間。5.有一個理發(fā)師,一把理發(fā)椅和n把供等候理發(fā)的顧客坐的椅子。如果沒有顧客,則理發(fā)師便在理發(fā)椅子上睡覺:當一個顧客到來時,必須喚醒理發(fā)師

53、,進行理發(fā)；如果理發(fā)師正在理發(fā)時,又有顧客來到,則如果有空椅子可坐,他就坐下來等,如果沒有空椅子,他就離開。為理發(fā)師和顧客各編一段程序描述他們的行為,要求不能帶有競爭條件。西安電子科技大學2000考研操作系統(tǒng)試題答案(一)單項選擇題(10分)1.B 2.C 3.C 4.A 5.B 6.D 7.B 8.C 9.B 10.D(二)改錯題(對錯誤的命題,請說明原因)(10分)1.錯,系統(tǒng)的程序道數(shù)越多,并不能說明效率就越高。2.對3.對4.錯,虛存大小與地址總線的位數(shù)有關。5.錯,作業(yè)之間并發(fā)執(zhí)行。6.對 7.錯,I/0交通管理程序管理設備、控制器、通道的全部狀態(tài)信息等,但它不管理主存。8.錯,移臂調(diào)度以減少移臂時間為目的。9.對10.對(三)填空題（9分)1.外殼 內(nèi)核2.靜態(tài)地址再定位 動態(tài)地址再定位3.非剝奪控制 零散請求 環(huán)路條件4.存儲器分配 虛存管理 存