2015年碩士研究生入學考試：操作系統復習資料12014年計算機學科研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合考試大綱. 考試性質計算機學科專業基礎綜合考試是為高等院校和科研院所招收計算機科學與技術學科的碩士研究生而設置的具有選拔性質的聯考科目，其目的是科學、公平、有效地測試學生掌握計算機科學與技術學科大學本科階段專業基礎知識、基本理論、基本方法的水平和分析問題、解決問題的能力，評價的標準是高等院校計算機科學與技術學科優秀本科畢業生所能達到的及格或及格以上水平，以利于各高等院校和科研院所擇優選拔，確保碩士研究生的招生質量。. 考查目標計算機學科專業基礎綜合考試涵蓋數據結構、計算機組成原理、操作系統和計算機網絡等學科專業基礎課程。要求考生系統地掌握上述專業基礎課程的基本概念、基本原理和基本方法，能夠綜合運用所學的基本原理和基本方法分析、判斷和解決有關理論問題和實際問題。. 考試形式和試卷結構一、試卷滿分及考試時間本試卷滿分為150分，考試時間為180分鐘二、答題方式答題方式為閉卷、筆試三、試卷內容結構數據結構45分計算機組成原理45分操作系統35分計算機網絡25分四、試卷題型結構單項選擇題80分（40小題，每小題2分）綜合應用題70分. 考查內容操作系統【考查目標】1. 掌握操作系統的基本概念、基本原理和基本功能，理解操作系統的整體運行過程。2. 掌握操作系統進程、內存、文件和I/O管理的策略、算法、機制以及相互關系。3. 能夠運用所學的操作系統原理、方法與技術分析問題和解決問題，并能利用C語言描述相關算法。一、操作系統概述（一）操作系統的概念、特征、功能和提供的服務（二）操作系統的發展與分類（三）操作系統的運行環境1. 內核態與用戶態2. 中斷、異常3. 系統調用（四）操作系統體系結構二、進程管理（一）進程與線程1. 進程概念2. 進程的狀態與轉換3. 進程控制4. 進程組織5. 進程通信共享存儲系統，消息傳遞系統，管道通信。6. 線程概念與多線程模型（二）處理機調度1. 調度的基本概念2. 調度時機、切換與過程3. 調度的基本準則4. 調度方式5. 典型調度算法先來先服務調度算法，短作業（短進程、短線程）優先調度算法，時間片輪轉調度算法，優先級調度算法，高響應比優先調度算法，多級反饋隊列調度算法。（三）同步與互斥1. 進程同步的基本概念2. 實現臨界區互斥的基本方法軟件實現方法，硬件實現方法。3. 信號量4. 管程5. 經典同步問題生產者-消費者問題，讀者-寫者問題，哲學家進餐問題。（四）死鎖1. 死鎖概念2. 死鎖處理策略3. 死鎖預防4. 死鎖避免系統安全狀態，銀行家算法。5. 死鎖檢測和解除三、內存管理（一）內存管理基礎1. 內存管理概念程序裝入與鏈接，邏輯地址與物理地址空間，內存保護。2. 交換與覆蓋3. 連續分配管理方式4. 非連續分配管理方式分頁管理方式，分段管理方式，段頁式管理方式。（二）虛擬內存管理1. 虛擬內存基本概念2. 請求分頁管理方式3. 頁面置換算法最佳置換算法（OPT），先進先出置換算法（FIFO），最近最少使用置換算法（LRU），時鐘置換算法（CLOCK）。4. 頁面分配策略5. 工作集6. 抖動四、文件管理（一）文件系統基礎1. 文件概念2. 文件的邏輯結構順序文件，索引文件，索引順序文件。3. 目錄結構文件控制塊和索引節點，單級目錄結構和兩級目錄結構，樹形目錄結構，圖形目錄結構。4. 文件共享5. 文件保護訪問類型，訪問控制。（二）文件系統實現1. 文件系統層次結構2. 目錄實現3. 文件實現（三）磁盤組織與管理1. 磁盤的結構2. 磁盤調度算法3. 磁盤的管理五、輸入輸出（I/O）管理（一）I/O管理概述1. I/O控制方式2. I/O軟件層次結構（二）I/O核心子系統1. I/O調度概念2. 高速緩存與緩沖區3. 設備分配與回收4. 假脫機技術（SPOOLing）. 題型示例一、單項選擇題：第140小題，每小題2分，共80分。下列每題給出的四個選項中，只有一項是最符合題目要求的。操作系統1. 下列選項中，不可能在用戶態發生的事件是A. 系統調用B. 外部中斷C. 進程切換D. 缺頁2. 中斷處理和子程序調用都需要壓棧以保護現場，中斷處理一定會保存而子程序調用不需要保存其內容的是A. 程序計數器B. 程序狀態字寄存器C. 通用數據寄存器D. 通用地址寄存器/加1操作load R1,x /取x進到寄存器R1中inc R1store x, R1 /將R1的內容存入x/減1操作load R2,xdec R2store x, R23. 有兩個并發執行的進程P1和P2，共享初值為1的變量x。P1對x加1，P2對x減1。加1和減1操作的指令序列分別如下所示。兩個操作完成后，x的值A. 不可能是-1或3B. 只能為0C. 可能為0、1或2D. 可能為-1、0、1或24. 設與某資源關聯的信號量初值為3，當前值為1。若M表示該資源的可用個數，N表示等待該資源的進程數，則M、N分別是A. 0、1B. 1、0C. 1、2D. 2、05. 在支持多線程的系統中，進程P創建的若干個線程不能共享的是A. 進程P的代碼段B. 進程P中打開的文件C. 進程P的全局變量D. 進程P中某線程的棧指針6. 下列選項中，滿足短任務優先且不會發生饑餓現象的調度算法是（ ）A. 先來先服務B. 高響應比優先C. 時間片輪轉D. 非搶占式短任務優先7. 若某單處理器多進程系統中有多個就緒態進程，則下列關于處理機調度的敘述中，錯誤的是A. 在進程結束時能進行處理機調度B. 創建新進程后能進行處理機調度C. 在進程處于臨界區時不能進行處理機調度D. 在系統調用完成并返回用戶態時能進行處理機調度8. 在虛擬內存管理中，地址變換機構將邏輯地址變換為物理地址，形成該邏輯地址的階段是A. 編輯B. 編譯C. 鏈接D. 裝載9. 某計算機采用二級頁表的分頁存儲管理方式，按字節編址，頁大小為210字節，頁表項大小為2字節，邏輯地址結構為：頁目錄號頁號頁內偏移量邏輯地址空間大小為216頁，則表示整個邏輯地址空間的頁目錄表中包含表項的個數至少是A. 64B. 128C. 256D. 51210. 在缺頁處理過程中，操作系統執行的操作可能是. 修改頁表. 磁盤I/O. 分配頁框A. 僅、B. 僅C. 僅D. 、和11. 當系統發生抖動（thrashing）時，可以采取的有效措施是. 撤銷部分進程. 增加磁盤交換區的容量. 提高用戶進程的優先級A. 僅B. 僅C. 僅D. 僅、二、綜合應用題：第41 47小題，共70分。1假設計算機系統采用CSCAN（循環掃描）磁盤調度策略，使用2KB的內存空間記錄16,384個磁盤塊的空閑狀態。（1）請說明在上述條件下如何進行磁盤塊空閑狀態的管理。（2）設某單面磁盤旋轉速度為每分鐘6,000轉，每個磁道有100個扇區，相鄰磁道間的平均移動時間為1 ms。若在某時刻，磁頭位于100號磁道處，并沿著磁道號增大的方向移動（如下圖所示），磁道號請求隊列為50、90、30、120，對請求隊列中的每個磁道需要讀取1個隨機分布的扇區，則讀完這4個扇區總共需要多少時間？要求給出計算過程。（3）如果將磁盤替換為隨機訪問的Flash半導體存儲器（如U盤，SSD等），是否有比CSCAN更高效的磁盤調度策略？若有，給出磁盤調度策略的名稱并說明理由；若無，說明理由。2請求分頁管理系統中，假設某進程的頁表內容如下表所示： 頁號頁框（Page Frame）號有效位（存在位）磁盤地址0101H133AH10326H2254H1776H30120H頁面大小為4 KB，一次內存的訪問時間是100 ns，一次快表（TLB）的訪問時間是10 ns，換入一個頁面的平均時間為108 ns（已含更新TLB和頁表的時間）。進程的駐留集大小固定為2，采用最近最少使用置換算法（LRU）和局部淘汰策略（假設TLB初始為空，地址轉換時先訪問TLB，再訪問頁表；有效位為0表示頁面不在內存）。（1）依次訪問上述三個虛地址：2362H、1565H、25A5H，各需多少訪問時間？給出計算過程。（2）基于上述訪問序列，計算1565H的物理地址，并說明理由。附錄2012年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合試題（操作系統部分）一、單項選擇題：140小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。23. 下列選項中，不可能在用戶態發生的事件是A. 系統調用B. 外部中斷C. 進程切換D. 缺頁24. 中斷處理和子程序調用都需要壓棧以保護現場，中斷處理一定會保存而子程序調用不需要保存的是A. 程序計數器B. 程序狀態字寄存器C. 通用數據寄存器D. 通用地址寄存器25. 下列關于虛擬存儲器的敘述中，正確的是A. 虛擬存儲器只能基于連續分配技術B. 虛擬存儲器只能基于非連續分配技術C. 虛擬存儲器只受外存容量的限制D. 虛擬存儲器只受內存容量的限制26. 操作系統的I/O子系統通常由四個層次組成，每一層明確定義了與鄰近層次的接口，其合理的層次組織排列順序是A. 用戶級I/O軟件、設備無關軟件、設備驅動程序、中斷處理程序B. 用戶級I/O軟件、設備無關軟件、中斷處理程序、設備驅動程序C. 用戶級I/O軟件、設備驅動程序、設備無關軟件、中斷處理程序D. 用戶級I/O軟件、中斷處理程序、設備無關軟件、設備驅動程序27. 假設5個進程P0、P1、P2、P3、P4的共享3類資源R1、R2、R3，這些資源總數分別為18、6、22。T0時刻的資源分配情況如下表所示，此時存在的一個安全序列是進程已分配資源資源最大需求R1R2R3R1R2R3P03235510P1403536P24054011P3204425P4324424A. P0，P2，P4，P1，P3B. P1，P0，P3，P4，P2C. P2，P1，P0，P3，P4D. P3，P4，P2，P1，P028. 若一個用戶過程通過read系統調用讀取一個磁盤文件中的數據，則下列關于此過程的敘述中，正確的是. 若該文件的數據不在內存，則該進程進入睡眠等待狀態. 請求read系統調用會導致CPU從用戶態切換到核心態. read系統調用的參數應包含文件的名稱A. 僅、B. 僅、C. 僅、D. 、和29. 一個多道批處理系統中僅有P1和P2兩個作業，P2比P1晚5 ms到達。它們的計算和I/O操作順序如下：P1：計算60 ms，I/O 80 ms，計算20 msP2：計算120 ms，I/O 40 ms，計算40 ms若不考慮調度和切換時間，則完成兩個作業需要的時間最少是A. 240 msB. 260 msC. 340 msD. 360ms30. 若某單處理器多進程系統中有多個就緒態進程，則下列關于處理機調度的敘述中錯誤的是A. 在進程結束時能進行處理機調度B. 創建新進程后能進行處理機調度C. 在進程處于臨界區時不能進行處理機調度D. 在系統調用完成并返回用戶態時能進行處理機調度31. 下列關于進程和線程的敘述中，正確的是A. 不管系統是否支持線程，進程都是資源分配的基本單位B. 線程是資源分配的基本單位，進程是調度的基本單位C. 系統級線程和用戶級線程的切換都需要內核的支持D. 同一進程中的各個線程擁有各自不同的地址空間32. 下列選項中，不能改善磁盤設備I/O性能的是A. 重排I/O請求次序B. 在一個磁盤上設置多個分區C. 預讀和滯后寫D. 優化文件物理的分布二、綜合應用題：第41 47小題，共70分。45（7分）某請求分頁系統的頁面置換策略如下：系統從0時刻開始掃描，每隔5個時間單位掃描一輪駐留集（掃描時間忽略不計），本輪沒有被訪問過的頁框將被系統回收，并放入到空閑頁框鏈尾，其中內容在下一次被分配之前不被清空。當發生缺頁時，如果該頁曾被使用過且還在空閑頁框鏈表中，則重新放回進程的駐留集中；否則，從空閑頁框鏈表頭部取出一個頁框。假設不考慮其它進程的影響和系統開銷，初始時進程駐留集為空。目前系統空閑頁框鏈表中頁框號依次為：32、15、21、41。進程P依次訪問的是：、。請回答下列問題。（1）訪問時，對應的頁框號是什么？（2）訪問時，對應的頁框號是什么？說明理由。（3）訪問時，對應的頁框號是什么？說明理由。（4）該策略是否適合于時間局部性好的程序？說明理由。46（8分）某文件系統空間的最大容量為4 TB（1 T =240），以磁盤塊為基本分配單位，磁盤塊大小為1 KB。文件控制塊（FCB）包含一個512 B的索引表區。請回答下列問題。（1）假設索引表區僅采用直接索引結構，索引表區存放文件占用的磁盤塊號。索引表項中塊號最少占多少字節？可支持的單個文件最大長度是多少字節？（2）假設索引表區采用如下結構：第07字節采用格式表示文件創建時預分配的連續存儲空間，其中起始塊號占6 B，塊數占2 B；剩余504字節采用直接索引結構，一個索引項占6 B，則可支持的單個文件最大長度是多少字節？為了使單個文件的長度達到最大，請指出起始塊號和塊數分別所占字節數的合理值并說明理由。2013年全國碩士研究生入學統一考試計算機科學與技術學科聯考計算機學科專業基礎綜合試題（操作系統部分）一、單項選擇題：140小題，每小題2分，共80分。下列每題給出的四個選項中，只有一個選項是最符合題目要求的。23. 用戶在刪除某文件的過程中，操作系統不可能執行的操作是A. 刪除此文件所在的目錄B. 刪除與此文件關聯的目錄項C. 刪除與此文件對應的文件控制塊D. 釋放與此文件關聯的緩沖區24. 為支持CD-ROM中視頻文件的快速隨機播放，播放性能最好的文件數據塊組織方式是A. 連續結構B. 鏈式結構C. 直接索引結構D. 多級索引結構25. 用戶程序發出磁盤I/O請求后，系統的處理流程是：用戶程序系統調用處理程序設備驅動程序中斷處理程序。其中，計算數據所在磁盤的柱面號、磁頭號、扇區號的程序是A. 用戶程序B. 系統調用處理程序C. 設備驅動程序D. 中斷處理程序26. 若某文件系統索引節點（inode）中有直接地址項和間接地址項，則下列選項中，與單個文件長度無關的因素是A. 索引節點總數B. 間接地址索引的級數C. 地址項的個數D. 文件塊大小27.設系統緩沖區和用戶工作區均采用單緩沖，從外設讀入1個數據塊到系統緩沖區的時間為100，從系統緩沖區讀入1個數據塊到用戶工作區的時間為5，對用戶工作區的1個數據塊進行分析的時間為90。進程從外設讀入并分析2個數據塊的最短時間是A. 200B. 295C. 300D. 39028. 下列選項中，會導致用戶進程從用戶態切換到核心態的操作是. 整數除以零. sin（）函數調用. read系統調用A. 僅、B. 僅、C. 僅、D. 、和29. 計算機開機后，操作系統最終被加載到A. BIOSB. ROMC. EPROMD. RAM30. 若用戶進程訪問內存時產生缺頁，則下列選項中，操作系統可能執行的操作是處理越界錯置換頁 訪問內存A. 僅、B. 僅、C. 僅、D. 、和31. 某系統正在執行三個進程P1、P2和P3，各進程的計算（CPU）時間和I/O時間比例如下表所示。為提高系統資源利用率，合理的進程優先級設置應為A. P1P2P3B. P3P