1、1、請舉例說明單用戶單任務的操作系統與多用戶多任務的操作系統之間的區別？2、死鎖產生的 4 個必要條件是什么？它們是彼此獨立的嗎？3、當系統中的地址空間非常大時（例如32 位），會給頁表的設計帶來什么問題？請給出一個方案并分析其優缺點。4、文件在磁盤上存放的形式有幾種？它們與存取方法有何關系？5、試比較進程與程序的異同。6、脫機命令接口和聯機命令接口有什么不同？1、答案 ：DOS是單用戶單任務的操作系統，通常這種操作系統沒有進程調度，內存管理也比較簡單，只劃 分為系統區和用戶區，是單道的程序運行環境。 Unix 是多用戶多任務的操作系統，有進程管理，內存管理 也比較復雜。它們都具有設備管理系統

2、和文件管理系統，但功能也有差別。2、互斥，請求和保持，不剝奪，環路等待。 不是相互獨立的，前三個條件是必要條件，而環路等待實際上是在前三者基礎上的一種可能的結果，是死 鎖的一種現象。3、會導致頁表過長從而很難找到一塊連續的存儲空間存放頁表，此外如果頁表中的行不連續也會加大訪問頁表的查找時間。可以用多級頁表解決這個問題，將頁表分頁，離散地存儲在不同區域，同時建立另一張頁表映射原來 頁表的每一頁。優點是不需要大塊的連續空間，但并沒有減少頁表的空間，同時也增加了訪存次數。4、三種存儲結構的特點略。順序結構鏈接結構索引結構順序順序順序隨機隨機5、答案 ：進程與程序是緊密相關而又完全不同的兩個概念：1）

3、每個進程實體中包含了程序段和數據段這兩個部分，因此他們是緊密相關的。但從結構上看，進程實體中除了程序段和數據段外，還必須包含一個 數據結構，即進程控制塊 PCB。 2）進程是程序的一次執行過程，因此是動態的；動態性還表現在進程由創 建而產生、由調度而進行、由撤銷而消亡，即它具有一定的生命周期。而程序只是一組指令的有序集合， 并可以永久的駐留在某種介質上，其本身不具有運動的含義，是靜態的。3）多個進程實體可同時存放在內存中并發執行，其實這正是引入進程的目的。而程序的并發執行具有不可再現性，因此程序不能正確并發 執行。 4）進程是一個能夠獨立運行、獨立分配資源和獨立接受調度的基本單位，而程序不可能

4、在多道環境下獨立運行。 5）進程與程序不一一對應，同一個程序多次運行，將形成不同的進程；同一個程序的一次執 行也可以產生多個進程；而一個進程也可以執行多個程序。6、答案： 脫機命令接口是 OS提供給批處理作業用戶的作業控制語言。批處理用戶不能直接與自己的運行 作業進行交互，只能向系統提供用作業控制語言編寫的作業說明書，并委托系統按照作業說明書中的作業 控制命令來對它們的作業進行控制和管理。聯機命令接口則不要求用戶填寫作業說明書，此時，系統將向 用戶提供一組鍵盤命令或其他操作方式的命令，用戶可通過這些命令來交互的控制自己程序的運行并獲得 操作系統的服務。1、簡述分頁和分段的區別。2、用戶級線程與

5、內核級線程的區別是什么？3、死鎖產生的 4 個必要條件是什么？它們是彼此獨立的嗎？4、文件在磁盤上存放的形式有幾種？它們與存取方法有何關系？5、在什么情況下需要進行重定位？為什么要引入動態重定位？6、命令接口和圖形用戶接口分別有什么優缺點？1、答案 ：分頁和分段有許多相似之處， 但是在概念上兩者完全不通， 主要表現在： 頁是信息的物理單位， 分頁是為了系統管理內存的方便而進行的，故對用戶而言，分頁是不可見的，是透明的；段是信息的邏輯 單位，分段是作業邏輯上的要求，對用戶而言，分段是可見的。頁的大小是固定的，由系統決定；段的大小是不固定的，由用戶作業本身決定。 從用戶角度看，分頁的地址空間是一維

6、的，而段的地址空間是二維的。2、答案 ：比較如下： 程的調度與切換速度；對于內核級線程， OS負責以線程為單位的調度，對于用戶級線程，OS的調度單位是進程，同一個進程內部的線程切換是自己完成的。 統調用；內核級線程的系統調用時只會引起該線程的阻塞，用戶級線程的系統調用將引起整個進程的 阻塞。線程執行時間； 內核級線程執行時間以線程為單位， 用戶級線程執行時間以進程為單位， 內部線程共享。3、答案 ：互斥，請求和保持，不剝奪，環路等待。不是相互獨立的，前三個條件是必要條件，而環路等待 實際上是在前三者基礎上的一種可能的結果，是死鎖的一種現象。4、答案 ：三種存儲結構的特點如下表：順序結構鏈接結構

7、索引結構順序順序順序隨機隨機5、答案：源程序經過編譯產生的目標模塊一般總是從 0 開始編址的， 其中的地址都是相對于起始地址的相 對地址。在將目標模塊經過鏈接裝入內存時，其分配到的內存空間的起始地址通常不為 0，因此指令和數 據的實際物理地址與裝入模塊中的相對地址是不同的。此時，為了使程序能夠正確執行，必須將相對地址 轉換成物理地址，即進行重定位。進程在運行過程中經常要在內存中移動位置，引入動態重定位的目的就是為了滿足程序的這種需要， 動態重定位的實現需要一定的硬件支持， 重定位的過程是由硬件地址變換機構在程序執行每條指令時 自動完成的。6、答案 ：命令接口的優點：功能強，速度快，靈活性好，屏

8、幕開銷小；缺點：顯示不直觀，難學，難記。 圖形用戶接口的優點：顯示直觀，操作簡便，易學；缺點：實現的代碼規模大，對內外存容量、 CPU 速度 和顯示器的要求較高。1、何謂死鎖？為什么將所有資源按類型賦予不同的序號，并規定所有進程按資源序號遞增的順序申請資 源后，系統便不會產生死鎖？2、簡述分頁和分段的區別。3、簡述分時系統的特征？4、一個比較完善的文件系統應該具備哪些功能？5、微內核結構具有哪些優點？6、請說明中斷驅動 I/O 方式和 DMA 方式有什么不同？1、答案 ：死鎖是指多個進程在運行過程中因競爭資源而造成的一種僵局，若無外力作用，這些進程都將無 法再向前推進。原因是死鎖的必要條件環路

9、等待條件不可能成立。因為多個進程之間只可能存在占據較低 序號資源的進程等待占據較高序號資源的進程釋放資源的情況，但不可能存在反向的等待，因此不能形成 循環等待鏈。2、答案 ：分頁和分段有許多相似之處，但是在概念上兩者完全不通，主要表現在：頁是信息的物理單位， 分頁是為了系統管理內存的方便而進行的， 故對用戶而言， 分頁是不可見的， 是透明的；段是信息的邏輯單位，分段是作業邏輯上的要求，對用戶而言，分段是可見的。頁的大小是固定的，由系統決定；段的大小是不固定的，由用戶作業本身決定。 從用戶角度看，分頁的地址空間是一維的，而段的地址空間是二維的。3、答案 ：多路性；允許一臺主機連接多臺終端，系統按

10、分時原則為每個用戶服務，每個用戶以時間片為單 位輪流運行。獨立性；每個用戶各占一個終端，彼此獨立操作互不干擾。及時性；用戶的請求能在很短的時間內得到響應，用戶可以接受。 交互性；用戶可通過終端與系統進行人機對話。4、答案 ：文件存儲空間的管理；目錄管理；文件的讀寫管理；文件的安全性管理；提供用戶接口。5、答案 ：微內核結構的優點如下： 1）提高了系統的靈活性和可擴充性。在微內核結構中，OS的大部分功能都是相對獨立的服務器來實現的，用戶可以根據需要選配器中的部分或全部服務器，還可以隨著計算機 硬件和 OS技術的發展，相應的更新若干服務器或增加一些新的服務器。2）提高了 OS的可靠性。由于所有的服

11、務器都是運行在用戶態，它們不能直接訪問硬件，因此，當某個服務器出現錯誤時，通常只會影響到 它自己，但不會引起內核和其他服務器的損壞和崩潰。3）適用于分布式系統。對用戶進程而言，如果它通過消息傳遞與服務器通信，那么他只須發送一個請求，然后等待服務器發來的響應，而無須知道這條消息 是在本地機就處理還是通過網絡送給遠地機上的服務器。6、答案 ：不同之處主要有： 1）中斷頻率。在中斷方式中，每當輸入數據緩沖寄存器中裝滿輸入數據或將 輸出數據緩沖寄存器中的數據輸出之后，設備控制器便發生一次中斷。由于設備控制器中配置的數據緩沖 寄存器通常較小，因此中斷比較頻繁；而DMA方式下，在 DMA控制器的控制下，一

12、次能完成一批連續數據的傳輸，并在整批數據傳送完后才發生一次中斷，因此可大大減少CPU處理 I/O 中斷的時間。 2）數據的傳送方式。在中斷方式下，由 CPU直接將輸入數據寫入控制器的數據緩沖寄存器供設備輸出，或在中斷發生 后直接從數據緩沖寄存器中取出輸入數據供進程處理，即數據傳送必須經過CPU；而在 DMA方式中，數據的傳輸在 DMA控制器的控制下直接在內存和 I/O 設備間進行， CPU只需將數據傳輸的磁盤地址、內存地址 和字節數傳給 DMA控制器即可。1. 設備分配與那些因素有關？（ 4 分）2. 某系統中磁盤的每個盤塊大小為 1KB，外存分配方法采用中的混合索引結構， 其中索引節點中直接

13、地址 6 項，一級索引地址 2 項，二級索引地址 1 項，每個盤塊號占用 4 個字節，請問 該系統中允許的文件最大長度是多少？（ 6 分）3為了能夠查找到文件的位置， 在采用連續文件、 鏈接文件和索引文件時， 在目錄中需要登記那些內容？ （6 分）4某采用分頁存儲管理的系統中，物理地址占20 位，邏輯地址中頁號占 6 位，頁大小為 1KB，問：該系統的內存空間大小為多少？每塊的大小為多少？邏輯地址共幾位，每個作業最大長度為多少？若 0 頁放在 3 塊中， 1 頁放在 7 塊中， 2 頁放在 9 塊中，邏輯地址 0420H 對應的物理地址是多少？（ 5 分）5. 試述缺頁中斷與一般中斷的主要區別

14、。 （4 分）6. 進程的基本狀態包括哪幾種？并畫出其狀態轉換圖。7. 在一個批處理單道系統中，采用響應比高者優先的作業調度算法。當一個作業進入系統后就可以開始調度，假定作業都是僅計算，忽略調度花費的時間。現有三個作業，進入系統的時間和需要計算的時間如表所示：作業進入系統時間需要計算時間開始時間完成時間周轉時間19:0060 分鐘9:0029:1045 分鐘39:1525 分鐘求出每個作業的開始時間、完成時間及周轉時間并填入表中1. 答案：設備分配策略與下列因素有關：（1）I/O 設備的固有屬性，對于獨占設備，共享設備、虛擬設備等具有不同屬性的設備，通常采用相應的 分配算法。（2）設備分配算法

15、，常見的有先來先服務算法、優先級高者優先算法（3）設備分配的安全性，即避免死鎖的產生。（4）設備獨立性，設備獨立性指應用程序獨立于具體使用的物理設備。 評分標準：共 4 個要點，每個要點 1 分2、答案 ：66054KB 解題步驟及其評分標準： 直接地址可用的磁盤空間為 1KB66KB（1 分）；1 級索引項可用的磁盤空間為 1KB256 2=512KB（2 分）；2 級索引項可用的磁盤空間為 1KB256 256=64MB（2 分）；求和： 6KB+512KB+64MB=66054KB3、答案 ：連續文件：第一個磁盤塊的塊號和文件長度；鏈接文件：第一個磁盤塊的塊號；索引文件：索引 盤塊號。4

16、、答案 ：內存空間大小為 1MB；每塊的大小為 1KB；每個作業最大長度為 64KB; 邏輯地址 0420H 對應的物 理地址是 1C20H.解題步驟及其評分標準： 邏輯地址 0420H對應的頁號為 1，主存塊號為 7，頁內地址 20H，得到物理地址 1C20H。5、答案 ：缺頁中斷與一般中斷的主要區別：在指令執行期間產生和處理中斷信號。一條指令在執行期間，可能產生多次缺頁中斷。評分標準：共 2 個要點，每個要點 2 分6、答案 ：進程的三種基本狀態：就緒狀態執行狀態阻塞狀態運行態進程調度 落選 發生等待事件就緒態阻塞態等待事件結束評分標準：基本狀態 2 分，進城轉換圖 4 分7、答案： 10

17、：0060分鐘 10： 25 11:10 120 分鐘10：0010：2570分鐘1簡述具有通道的系統中獨占設備的一般分配過程。（3 分）2比較電梯調度算法和最短尋找時間優先調度算法。（6 分）3. 為了實現虛擬頁式存儲管理，頁表應該包含哪些內容？（ 4 分）4. 簡述一種 LRU頁面置換算法的實現方案。 （5分）6.列舉引起進程創建的事件。簡述進程創建的過程。 （6 分）7. 若系統有某類資源 mn+1 個，允許進程執行過程中動態申請該類資源，但在該系統上運行的每一個進 程對該資源的占有量任何時刻都不會超過m+1個。當進程申請資源時只要有資源尚未分配完則滿足它的申請，但用限制系統中可同時執行

18、的進程數來防止發生死鎖，你認為進程調度允許同時執行的最大進程數應 該是多少？并證明之。 （7 分）1、答案 ：可按下述步驟進行設備分配：分配設備。分配控制器。分配通道。2、答案 ：“電梯調度”與“最短尋找時間優先”都是要盡量減少移動臂移動時所花的時間；不同的是 “最短尋找時間優先”不考慮臂的移動方向，總是選擇離當前讀寫磁頭最近的那個柱面的訪問者，這種選 擇可能導致移動臂來回改變移動方向； “電梯調度” 是沿著臂的移動方向去選擇離當前讀寫磁頭最近的那個 柱面的訪問者，僅當沿臂移動方向無等待訪問者時才改變臂的移動方向；由于移動臂改變方向是機械動 作，速度相對較謾。相比之下，電梯調度算法是一種簡單、

19、實用且高效的調度算法。但是，在實現時除了 要記住讀寫磁頭的當前位置外，還必須記住移動臂的移動方向。3、答案：在分頁虛擬存儲管理時使用的頁表， 最少包括以下內容：物理塊號、 狀態位、 修改位、外存地址4、答案 ：方案多個，下面僅是其一：為了實現LRU，必須在主存維護一張作業所有頁的鏈表，表中各項按訪問時間先后排序，最近訪問的頁排在表頭，最久末用的頁排在表尾，這就是所謂的棧式算法。每當要置 換一頁時，必須對鏈表中的各項進行修改。若被訪問的頁在主存，則將其移到表頭，調整相應項。若不在 主存，則將新調的頁放表頭，其它項依次后移，將表尾一項擠掉。6、答案 ：引起進程創建的典型事件有分時系統中的用戶登錄、

20、批處理系統中的作業調度、系統提供服務、應用進程本身的應用請求等。創建進程：申請空白PCB。為新進程分配資源。初始化進程控制塊。將新進程插入就緒隊列。7、答案：假設系統中有 x個進程的進程，則資源至少要有 mx+1 個，由于系統資源有 m n+1個，則可列 出不等式： mx+1mn+1 解不等式，得到 xn，所以系統允許同時執行的最大進程數為n。證明：假設在系統允許同時執行的最大進程數為 n 時，仍然出現了死鎖，此時應該存在一組進程進程都在 等待資源， 而且系統已無資源可用。 則此時該組進程最多 n 個，每個進程沒有執行完時最多占用 m個資源， 所以現在系統分配出去的資源最多 m n，少于系統資

21、源 mn+1，所以不可能有死所出現。 因此，系統允許同時執行的最大進程數為n 時系統不會有死鎖發生1、有一個具有兩道作業的批處理系統，有如下表所示的作業序列（表中所列作業優先級即為進程優先級，數值越小優先級越高） 。分別列出下面兩種情況下所有作業進入內存時刻及結束時刻， 并計算其平均周轉時 間。作業名到達時刻估計運行時間（分）優先級A10：00405B10：20303C10：30504D10：40206假設采用短作業優先的調度算法，進程調度采用優先級為基礎的剝奪式算法。（6分）10：00 A 到達，無競爭， A 開始運行10：20 B 到達，進入內存， B的優先級高于 A，A停止， B運行（

22、1 分）10： 30 C 到達，不能進入內存（ 1 分）10：40 D 到達，不能進入內存10：50 B 運行結束， C和 D競爭進入內存， D進入， A運行（ 1 分）11：10 A 運行結束， C進入內存， C 運行（ 1 分）12：00 C運行結束， D運行12： 20 全部結束T（ 703090100）/4 72.5 分鐘（ 2 分）2、在一分頁存儲管理系統中，邏輯地址長度為16 位，頁面大小為 4096 字節，現有一邏輯地址為 2F6AH，且第 0、1、2 頁依次存放在物理塊 5、10、11 中，問相應的物理地址為多少？（ 6分） 由題意可知，本頁式系統的邏輯地址結構為： （3 分）

23、頁號 P頁內位移 W15 12 11 0邏輯地址 2F6AH的二進制表示： （1 分） 頁號為 2，在第 11 塊中，故物理地址為 BF6AH。（2 分）3、有一個倉庫，可以存放 A 和 B 兩種產品，但要求： 1）每次只能存入一種產品（ A或 B）；2）-NA 產品 數量 B產品數量1， 即 N/2 M/21，故 MN 2。 （3 分）7、若在一分頁存儲管理系統中， 某作業的頁表如下表所示。 已知頁面大小為 1024 字節，試將邏輯地址 1011、 2148、3000、 4000 轉化為相應的物理地址。 （4分）頁號塊號02132136解題步驟及其評分標準：設頁號為 P，頁內位移為 W，邏輯

24、地址為 A，頁面大小為 L，則：P=int （A/L） W=A mod L1011 有： P=int （ 1011/1024 ）=0 W=1011 mod 1024=1011第0 頁在第 2塊，故物理地址： 30592148 有： P=int （ 2148/1024 ）=2 W=2148 mod 1024=100第2 頁在第 1塊，故物理地址： 11243000 有： P=int （ 3000/1024 ）=2 W=3000 mod 1024=952第2 頁在第 1塊，故物理地址： 19764000 有： P=int （ 4000/1024 ）=3 W=4000 mod 1024=928第3

25、頁在第 6塊，故物理地址： 70728、現有四個進程 R1、 R2、 W1、 W2，它們共享可以存放一個數的緩沖器B。進程 R1 每次把來自鍵盤的一個數存入緩沖器 B 中，供進程 W1打印輸出； 進程 R2 每次從磁盤上讀一個數存放到緩沖器B中，供進程 W2打印輸出。為防止數據的丟失和重復打印，問怎樣用信號量操作來協調這四個進程的并發執行。（13 分）1、目的：考查學生對同步問題的掌握；滿分值：13 分；答案：四個進程可如下描述：Semaphore sb=1,sx=0,sy=0;wait(sx);Item B;k:=B;Void R1( )signal(sb);Void W2( )打印 k 中

26、數 ;while(1)while(1)接收來自鍵盤的數 ;wait(sy);x=接收的數 ;Void R2( )j:=B;wait(sb);wait(sb);B:=x;while(1)打印 j 中數 ;Signal(sx);從磁盤上讀一個數 ;y:= 讀入的數 ;Void w1( )wait(sb);main()B:=y;while(1)Signal(sy);cobegin(R2();W2();R1();W1();9、試設計在虛擬存儲環境下實現簡單的clock 頁面置換的可行方案。 （12 分）使用 Clock 算法時，只須為每頁設置一個訪問位。在將內存中的所有頁面都通過鏈接指針鏈成一個循環隊

27、列（4 分）。當某頁被訪問時，其訪問位置 1。置換算法在選擇一頁淘汰時，只須檢查其訪問位，如果是0，就選擇該頁換出； 若為 1，則重新將它復 0、暫不換出而給該頁第二次駐留內存的機會 （4 分）。再按照 FIFO 算法檢查下一個頁面。當檢查到隊列中的最后個頁面時，若其訪問值仍為1、則再返回到隊首再去檢查第一個頁面 （4 分）10、某系統采用空閑區鏈結構對內存的空閑區進行說明，用UPT表結構說明內存的占用情況。 UPT表和空閑鏈結構分別如下所示：#define true 1*/int size; /*分區長度 */#define false 0typedef struct /*已分分區UTABL

28、Em;FREGION;表結構 */Typedef struct /*空閑分區FREGION *free;/* 空閑鏈表結構 */分區鏈表頭指針 */int address; /*分區起始UTABLE UPT;/* 已分分區表地址 */FREGION *forward; /* 上一個*/int size; /*分區長度 */分區起始地址 */函數過程：int flag ； /*表目狀態， 1FREGION *back;/* 下一個分區表示有用登記項，0 表示空表目起始地址 */司機與售票員問題：12 分）11、表示門關著，1 表示車停，初始狀態0；售票員void Process設信號量 so，s

29、c ，so1void Process_ 司機while（1）while（1）wait （ so）；關門；開車；signalso）；行車；賣票；停車；waitsc）；開門；signal （ sc）；main（） cobeginProcess_ 司機； Process_ 售票員； 12、假定磁盤轉速為 6000r/min ，磁盤格式化時每個盤面被分為 8 個扇區讀取一個扇區的時間是 （60/6000）/8=1.25ms ，讀出該文件全部內容所需時間為：1.25 8 2.5 7 7.5 7 80ms（ 3 分）采用交錯試存儲（圖略） ，讀出全部文件的時間為：1.25 8 2.5 7 27.5ms（

30、3 分） 假定某頁式虛擬系統中，某進程的頁面訪問蹤跡為： 面數為 3。（6 分）按 FIFO 頁面置換算法，計算缺頁率并畫圖示意； 按 OPT頁面置換算法，計算缺頁率并畫圖示意； 按 LRU頁面置換算法，計算缺頁率并畫圖示意。4，3，2，1，4，3，5，4，3，2，1，5，它的實際頁（ 2 分）2 分）2 分）缺頁率 75%頁面 14 4 4 1 1 1 5 5 5 5 5 5頁面 23 3 3 4 4 4 4 4 2 2 2頁面 32 2 2 3 3 3 3 3 1 1作業頁面4 3 2 1 4 3 5 4 3 2 1 5缺頁否y y y y y y y y y缺頁率 58%頁面 14 4

31、4 4 4 4 4 4 4 2 2 2頁面 23 3 3 3 3 3 3 3 3 1 1頁面 32 1 1 1 5 5 5 5 5 5作業頁面4 3 2 1 4 3 5 4 3 2 1 5是否缺頁y y y y y y y 缺頁率 83%頁面 14 4 4 1 1 1 5 5 5 2 2 2頁面 23 3 3 4 4 4 4 4 4 1 1頁面 32 2 2 3 3 3 3 3 3 5作業頁面4 3 2 1 4 3 5 4 3 2 1 5是否缺頁y y y y y y y y y y13、在一個批處理單道系統中，采用響應比高者優先的作業調度算法答案： 10： 0060分鐘 10： 2511:10 120分鐘 10 ：0010： 25 70分鐘1、寫算法：（35 分）有一個可以存放 n 整數的循環緩沖，今有 m 個輸入進程，每個次 semaphoremutexP=1,mutexC=1,empty=n,full=0;item buffern