1、操作系統復習提要2021年題型往年的是非題20分，每題2分注意，錯題要糾錯！單項選擇題30分，每題3分簡答題 20分，每題5分計算、設計題30分 考試范圍前15章第七版重點113章Part 1: Overview 1. Introduction 2. Operating-System Structures Part 2: Process Management 3. Processes 4. Threads 5. CPU Scheduling 6. Process Synchronization 7. Deadlocks Part 3: Memory Management 8. Main Mem

2、ory 9. Virtual Memory Part 4: Storage Management 10. File-System Interface 11. File-System Implementation 12. Mass-Storage Structure 13. I/O Systems 14. Protection15. Security1 緒論Computer System StructureApplication programsOperating systemHardwareUsers1 緒論存儲結構程序方式/中斷/DMAMultiprogramming/ Timesharin

3、g (multitasking) 1 緒論例題名詞辨析：分時time-sharing與多道程序multi-programming核心態和用戶態判斷：分時time-sharing是為了在操作系統中支持同時運行多個程序，從而提高CPU的利用率而提出的。2 操作系統結構從三個角度用戶角度、程序員角度操作系統設計人員角度2 操作系統結構Operating System ServicesUser Operating System InterfaceSystem CallsSystem ProgramsOperating System Design and ImplementationOperating

4、System StructureVirtual MachinesOperating System GenerationSystem Bootmicrokernel進入操作系統的三種場景1. 中斷 Interrupt2. 異常 Exception3. 系統調用，System Call， Trap2 操作系統結構例題名詞辨析：微內核和模塊化內核在微內核結構的操作系統中，進程間通訊可以不在微內核內。錯。進程通訊是內核的核心功能，對微內核系統，也在微內核內實現。以下對操作系統內核的運行方式的描述，正確的選項是：DA. 操作系統是一個以內核態運行的獨立的進程；B. 操作系統內核運行時不能訪問其它進程的地

5、址空間；C. 只有在硬件中斷發生時，操作系統內核才會運行；D. 操作系統內核可以以內核態在用戶進程上下文中運行。3 進程進程概念進程調度進程操作進程協作進程間通信3 進程3 進程數據結構：PCB調度用的queue根本進程編程方法3 進程長程調度或作業調度 從作業池中選擇進程，并將它們裝入內存以執行。短程調度或CPU調度 從就緒可執行的進程中選擇進程，并為其中之一分配CPU。中程調度3 進程例題名詞辨析：長程調度long-term scheduling與中程調度mid-term scheduling4. 線程概述多線程模型假設干線程問題4. 線程根本概念特點與進程的關系，比較4. 線程例題1是非

6、：線程都保存有各自的棧信息和CPU狀態存放器、指令計數器等。2是非：在多進程多線程操作系統中，每個進程只需要維護一個棧stack；3 名詞辨析： 進程和線程5. CPU調度根本概念調度準那么/評估幾種調度算法FCFS，SJFSRTF優先級調度RR5. CPU調度例題是非題：在微內核結構的操作系統中，CPU調度必然在微內核內。名詞辨析：最短作業優先調度和最短剩余時間優先調度6進程同步概念生產者-消費者問題哲學家問題信號量6進程同步例題1是非：單CPU環境下由于任何時刻只有一個進程線程能夠運行，因此操作系統不需要實現同步與互斥支持。2選擇： 多CPU共享內存環境下，以下哪種實現臨界區的方法無效？A

7、. 使用test_and_set機器指令實現“忙等busy waitingB. Peterson算法C. 關中斷D. 使用swap機器指令實現“忙等7死鎖系統模型死鎖特點死鎖的4個條件資源分配圖死鎖？饑餓？死鎖處理方法死鎖預防死鎖防止死鎖檢測死鎖恢復平安狀態/死鎖銀行家算法矩陣7死鎖例題1選擇： 以下哪種情況仍然可能會發生死鎖？A. 資源都是可共享的；B. 每一種資源的數量都超過單個進程所需這類資源的最大值；C. 空閑資源能夠滿足任意一個進程還需要的資源需求；D. 每個進程必須一次申請、獲得所需的所有資源7死鎖例題2辨析：死鎖deadlock與饑餓starvation3)在搶占式preempt

8、ive操作系統中，進程不會因為申請、使用資源發生死鎖。4不平安狀態未必會導致死鎖的發生；始終處于平安狀態也不能保證死鎖一定不會發生。5問答：7死鎖例題. 10分現有以下實現有界緩存bounded buffer問題的偽代碼1. semaphore mutex = 1;2. semaphore full = 0;3. semaphore empty = 3; /buffer中允許3個item4. producer () 5. / produce an item6. wait (empty);7. wait (mutex);8. / add it to the buffer9. signal (mu

9、tex);10. signal (full);11.12.consumer() 13. wait (mutex);14. wait (full);15. / remove one from buffer16. signal (mutex);17. signal (empty);18. / consume the removed item19.a) 請問該代碼是否會引起死鎖？3分b) 如果不會引起死鎖，請證明死鎖證明死鎖的四個必要條件中有一個不成立；如果可能引起死鎖，請畫出資源分配圖信號量作為資源，指出代碼發生死鎖的原因，并進行改正。7分8主存管理背景交換連續內存分配分頁分段帶有分頁的分段8主存

10、管理例題是非：段表由各個進程自己管理，進程可在用戶態對段表進行更新。名詞辨析：段式內存管理和頁式內存管理9虛存管理背景按需demanding頁面調度進程創立頁面置換算法：FIFOBeladys；LRU，LFU，MFU幀分配系統顛簸 Thrashing 9虛存管理例題1是非： 微內核操作系統中，CPU調度和虛存管理功能必須在微內核中實現；2是非：在虛存管理時，采用先進先出FIFO頁面替換策略，必然會發生Belady異常即分配頁框越多，缺頁率反而越高；3選擇：當發生抖動或稱為顛簸，thrashing時，以下哪種現象不會出現？A. 處于等待waiting狀態的進程數增多B. CPU利用率增高C. 磁

11、盤I/O增多D. 長程調度long-term scheduling允許更多的進程進入就緒ready狀態9虛存管理例題4計算：采用按需調頁demand paging，現有3個頁框，分別存儲著頁面號2,3,4三個頁面。接下來的頁面訪問順序為1,2,3,4,1,2,5,1,2,3,4,5。使用時鐘算法clock algorithm作為頁面替換算法。10分請計算會發生的缺頁次數假設初始時在頁框內的頁面的引用位reference bit都是1，2/3/4三個頁面按序存放，初始時指針指向頁面2？7分請寫出這一訪問序列所對應的工作集。3分試簡述缺頁中斷處理的詳細過程從發生缺頁中斷開始至頁面調度結束，進程繼續

12、執行為止，并指明每一個步驟中，處理所處的上下文環境和模式。10文件系統接口文件概念訪問方法目錄結構文件系統安裝文件共享保護10文件系統接口例題1簡答：請簡述在一個支持有向無環圖目錄結構的文件系統中，刪除一個普通文件非目錄文件時操作系統需要執行哪些操作。5分11文件系統實現文件系統結構文件系統實現FCB目錄實現分配方法連續分配鏈接分配索引分配空閑空間管理恢復11文件系統實現例題1是非：在目錄文件中，必須保存文件名和文件控制塊信息。2選擇：以下哪種數據結構必須存放在持久存儲介質上？A. 進程控制塊B. 頁表C. 文件控制塊D. 翻開文件列表11文件系統實現例題3以下對于目錄及其實現的描述，錯誤的選

13、項是：A. 目錄是文件的集合，是一種邏輯概念，通常用文件實現B. 目錄文件中存放的就是目錄中文件的文件控制塊file control blockC. 目錄中可以有子目錄，形成嵌套結構D. 目錄中的“.和“.通常分別代表該目錄本身和其父目錄11文件系統實現例題415假設有文件系統使用i-node如下圖。其中一個磁盤塊大小為4KB，一個磁盤塊指針大小為32位4B，直接塊direct block大小為2KB，其它索引塊大小和一個磁盤塊一樣大小。假設有一個4MB大小的文件，其i-node已在內存中direct block也在內存中，文件的其它局部都在磁盤上，不考慮緩存。請問：a) 訪問其第一個字節，第

14、1K個字節，第1M個字節，第2M個字節，第3M個字節，和最后一個字節分別需要訪問幾個磁盤塊2x5=10？b) 該文件系統最大能支持多大的文件(5)？11文件系統實現例題5計算、設計題15設有一個文件系統，文件數據塊磁盤塊大小為4KB，每個文件數據塊指針大小為4B32位。該文件系統需要支持以下操作：int read (int fd, int pos, int len, int *buf);int write (int fd, int pos, int len, int *buf);int insert (int fd, int pos, int len, int *buf);其中，fd為文件句柄

15、handle，pos為讀寫插入位置，以上三個函數會按照pos x 4KB為實際位置讀寫插入buf中len x 4KB的數據，即每次數據操作必然讀寫插入一個磁盤塊大小的數據，且插入位置的偏移量正好是4KB的整數倍。a) 請分別詳細描述如何在連續磁盤塊分配、鏈接分配、索引分配情況下實現插入操作3x3；b) 不考慮緩存，不考慮連續分配時空間不夠的情況，請詳細分析以上三種實現每次讀寫插入操作需要訪問多少次磁盤2x3；c) 請問以上哪種方式最不適合這一場景？哪種方式最適合這一場景？為什么？2x2d) 假設在FCB中，還剩余256B的空間，請參考UNIX文件系統的i-node結構，設計一個多級的包含直接塊

16、和間接索引的塊管理方式，并分析該方式與以上三種方式相比的優缺點。3現有如下代碼int pos10; /* 和用戶交互，為posi賦值 */int fd = open (“/home/us001/test.txt, O_WRONLY); /*以只寫方式翻開文件*/for (int i = 0; i 10; i +) fseek (fd, posi, SEEK_CUR); /* 文件指針定位到當前位置+posi */ fprint (fd, “pos %dn, i); /* 寫文件 */close (fd); /*關閉文件 */a請解釋第2、第4、第5、第6行代碼執行時，操作系統分別需要進行哪些操

17、作？8分b請問第4、第5行代碼的寫操作屬于順序訪問還是隨機訪問？2分c請問對于這種訪問方式，采用何種文件塊組織方式較適宜？為什么？5分。11文件系統實現例題12 海量存儲磁盤調度多級存儲12 海量存儲例題1. 以下哪個操作不是磁盤格式化進行的？A. 劃分扇區和磁道B. 建立空閑FCB列表C. 建立空閑塊列表D. 設定根目錄文件2辨析：二級存儲secondary storage與三級存儲tertiary storage3簡答:請簡述磁盤訪問效率由哪些局部決定，并分析如何提高文件系統中順序訪問文件的效率。512 海量存儲例題磁盤訪問隊列98, 183, 37, 122, 14, 124, 65,

18、67標號為柱面號，當前磁頭位置為53。10分a) 請寫出一種最優的磁頭移動序列，并計算磁頭移動距離。5分b)請問這一序列和哪種調度算法的結果是一致的？2分c)請問這種調度算法能否保證在任意情況下是最優的？為什么？3分12 海量存儲例題10設現有磁頭訪問請求隊列98，83，137，122，14，124，67，65，當前磁頭位置為50。請：a) 分別計算最短尋道時間優先SSTF算法和SCAN算法所需的磁頭移動距離3x2b) 請比較以上兩種方法的優缺點4。12 海量存儲例題假設磁盤磁頭當前在磁道100，磁道請求隊列為：:1. 請計算FIFO先進先出策略下的尋道總長度(包括過程)4分2. 請計算SSTF最近尋道時間優先策略下的尋道總長度(包括過程)4分3. 請問：SSTF是否一定是總尋道長度最短的，為什么？2分13 I/O系統Polling/ Interrupt/ DMA13 I/O系統1是非：對于鍵盤這樣的低速字符設備，采用DMA方式進行數據交換是不適宜的；2)是非：塊設備一定是快速設備，且一定既能支持順序訪問又能支持隨機訪問。3辨析：程序控制輸入輸出programmed I/O與直接內存訪問DMA選擇：以下哪種設備常用假脫機方式spool