復習題綱-read

1、復習題綱,操作系統(tǒng)基礎（2000級）,掌握計算機軟件的分類、操作系統(tǒng)的概念、微程序、命令解釋器、操作系統(tǒng)的工作狀態(tài)、用戶軟件的工作狀態(tài)、操作系統(tǒng)的作用、進程、文件、虛擬機、系統(tǒng)調用以及系統(tǒng)結構等基本概念；并在掌握操作系統(tǒng)概念的基礎上能夠區(qū)分哪些指令是特權指令、哪些指令是非特權指令；CPU狀態(tài)：管理狀態(tài)與用戶狀態(tài)。,第一部分 引言,第二部分 進程,掌握進程的基本概念、進程的特點、進程的狀態(tài)以及狀態(tài)之間的轉化關系、線程的概念、線程實現的

2、兩種方式以及相應的特點；掌握進程通信中的基本概念內容包括競爭條件、臨界區(qū)、互斥、臨界區(qū)的求解原則、信號量、進程調度所需要考慮的因素、具體的各種進程調度算法（先來先服務、時間片輪轉、優(yōu)先級調度、多重隊列、最短作業(yè)優(yōu)先算法）等；能夠運用所學的進程通信的知識，分析軟件算法中所存在的問題，并能夠在分析問題的基礎上能運用相應的知識解決實際應用中的相應問題；,第三部分 輸入/輸出系統(tǒng),掌握：I/O設備的硬件軟件原理，能夠區(qū)分相關的I/O操作具體

3、是在拿一軟件層次上完成。了解死鎖的定義、死鎖發(fā)生的必要條件以及處理死鎖的策略，針對于這些處理策略有哪些相應的算法來解決；磁盤軟件以及磁盤臂調度算法、磁盤出錯的處理等，掌握時鐘軟件所完成的任務運用：根據系統(tǒng)給出的資源分配圖能夠分析判斷系統(tǒng)的狀態(tài)；根據實際的情況能夠對I/O設備的處理進行優(yōu)化設置；,第四部分 存儲器管理,存儲器的重定位和保護；固定分區(qū)與可變分區(qū)的概念；可變分區(qū)的內存管理以及使用鏈表的內存管理中的分配算法；分頁的虛擬

4、存儲器的實現過程，虛擬地址到物理地址的轉化過程；頁面的替換算法；分頁系統(tǒng)中的設計問題；,第五部分 文件系統(tǒng),文件系統(tǒng)的基本概念：文件命名、文件結構、文件類型、文件存儲、文件屬性、文件操作、層次目錄系統(tǒng)、路徑名稱、目錄操作；掌握文件系統(tǒng)的實現（文件的實現、目錄實現）、磁盤空間的管理、文件系統(tǒng)的可靠性、文件系統(tǒng)的性能；安全性,一、考試題型,１．判斷２０個２．５個大題（８０分）　　?。保惴☉谩　　。玻畱美碚摗　　。常幊虘?/p>

5、用,二、復習綱要,１．作業(yè)調度２．進程調度,,＞,FCFS.SJF.RR(Round Robin),時間片輪轉,3.內外存交換調度（頁面置換）　　OPT ?（clock policy） FIFO、LRU ?　　　　　Second—chance?變境強型（NUR） P３１９頁4.磁盤空白塊管理算法　?、傥粓D　　②鏈表 FF.NF.BF.WF.　?、刍锇?５．磁盤讀寫臂調度算法

6、　　　　FCFS、SSTF、SCAN、LOOK.６．地址映射與轉換 虛地址與實地址，地址轉換圖,７．UNIX文件系統(tǒng)結構與i結點。８．P.V操作、讀寫者問題（讀者優(yōu)先）？9 ．資源管理，死鎖分析與研究,三、例題講解,例１．假設系統(tǒng)由相同類型的m個資源組成，系統(tǒng)有n個進程，每個進程至少請求一個資源，證明：當n個進程最多需要的資源之和小于m+n時，該系統(tǒng)無死鎖。,解：,證明：假設當n個進程最多需要的資源之和

7、小于m+n，系統(tǒng)死鎖。,因為系統(tǒng)死鎖,? 至少在一個Pi 其Needi=0，此時Pi不死鎖，與假設題意矛盾，所以系統(tǒng)不死鎖。,2. 某系統(tǒng)中有六臺打印機，N個進程共享打印機資源，每個進程要求兩臺，試問N取哪些值時，系統(tǒng)才不會發(fā)生死鎖？,解：由上可知,證：n個進程最多需要的資源之和小于6+n時，該系統(tǒng)無死鎖，即2n<6+n，n<6。,? n取值為1，2，3，4，5,另證：如下圖所示：,當n=6時，最糟情況有：,每一進程已占有一

8、個資源，還申請一個資源，此時死鎖。,同理n>6時系統(tǒng)也會出現死鎖。,而n=5時，最糟情況下也會有,此時可化簡為完全可化簡圖，不死鎖。,同理1<n<5時也不死鎖， ? n取值為1，2，3，4，5。,例題2. 設某系統(tǒng)有一256k的空白區(qū)，現有以下作業(yè)序列和對內存的要求：,作業(yè)1要140k，作業(yè)2要求16k，作業(yè)3要求80k，作業(yè)1完成，作業(yè)3完成，作業(yè)4要求70k，作業(yè)5要求128k。,試用首次適應和最佳適應算法對上述

9、作業(yè)進行可變分區(qū)存貯分配(繪圖)并討論。,解：,例題3. 在一個請求頁式存儲系統(tǒng)中，一程序的頁面走向為4.3.2.1.4.3.5.4.3.2.1.5采取LRU頁面置換算法，設分配給該程序的存儲塊數M分別為3和4時，請求出在訪問過程中發(fā)生的缺頁次數和缺頁率，并比較所得結果，從中可得到什么啟發(fā)？,解：,當M＝3時,? 缺頁10次，缺頁中斷率為,當M＝4時,? 缺頁7次，缺頁中斷率為,在LRU算法下，當M增大時，缺頁次數減少，缺頁中斷率也減少

10、。,例題4. 假定五個作業(yè)A～E提交時間相同，且實際需要運行的時間分別是10、6、2、4和8分鐘，外部分配的優(yōu)先級數分別是3、5、2、1和4，(設數值大的優(yōu)先數高)。忽略CPU的切換時間，分別就下列幾種調度算法計算作業(yè)的平均周轉時間。a. 輪轉法；b. 優(yōu)先級調度；c. SJF,解：,(a) 輪轉法：(時間片以及CPU切換時間都較小可忽略),C完成：2×5=10分鐘,D完成：10+(4–2)×4=18分鐘,調度

11、次序：C ? D ? B ? E ? A,E完成：24+(8–6)×2=28分鐘,A完成：28+(10–8)×1=30分鐘,B完成：18+(6–4)×3=24分鐘,(b) 優(yōu)先級調度,調度次序：B ? E ? A ? C ? D,(c) SJF,調度次序：C ? D ? B ? E ? A,例題5. 設有一個數據區(qū)，有若干進程要去讀或寫它，遵循下列原則：,? 寫是互斥的，當一進程正在寫時，其它進程既不能寫，

12、也不能讀；,? 讀可同時進行，只要沒有進程正在寫，則任何進程都可以讀，請用P，V操作寫出讀寫過程的同步算法(要給出信號量物理意義以及初值),答：var mutex, wrt: Semaphore;readcount: integer;mutex: = wrt: = 1;readcount: = 0;parbeginReaderi: beginWait (mutex);readcount: = r

13、eadcount + 1; if readcount = 1 then Wait (wrt);Signal (mutex);讀數據集；Wait (mutex);readcount: = readcount – 1; if readcount = 0 then Signal (wrt);Signal (mutex);endWriteri: begin Wait

14、(wrt);寫數據集;Signal (wrt);endcoend,例題6. 有一閱覽室，讀者進入時必須先在一張登記表上進行登記，該表為每一座位列一表目，包括座號和讀者姓名。讀者離開時要消掉登記信號，閱覽室中共有100個座位，請問：,(1) 為描述讀者的動作，應編寫幾個程序？設置幾個進程？進程與程序間的對應關系如何？,(2) 用類Pascal語言和Wait, Signal操作寫出這些進程間的同步算法。,答：(1)

15、 應編寫1個程序；設置2個進程；進程與程序間的對應關系是：多對1。,(2)beginS1:=100 (有100個座位)S2:=0 (有沒閱讀者)mutex: =1cobeginP1: repeatP(S1);P(mutex);登記信息;V(muetx);V(S2)就座，閱讀； until false coenden