操作系統(tǒng)基礎(chǔ)復(fù)習(xí)題綱

1、操作系統(tǒng)基礎(chǔ)（2000級(jí)） 掌握計(jì)算機(jī)軟件的分類、操作系統(tǒng)的概念、微 程序、命令解釋器、操作系統(tǒng)的工作狀態(tài)、用戶軟件 的工作狀態(tài)、操作系統(tǒng)的作用、進(jìn)程、文件、虛擬機(jī)、 系統(tǒng)調(diào)用以及系統(tǒng)結(jié)構(gòu)等基本概念；并在掌握操作系 統(tǒng)概念的基礎(chǔ)上能夠區(qū)分哪些指令是特權(quán)指令、哪些 指令是非特權(quán)指令；CPU狀態(tài)：管理狀態(tài)與用戶狀態(tài)。 第一部分引言 第二部分進(jìn)程 掌握進(jìn)程的基本概念、進(jìn)程的特點(diǎn)、進(jìn)程的狀態(tài)以及狀 態(tài)之間的轉(zhuǎn)化關(guān)系、線程的概念、線程實(shí)現(xiàn)的兩種方式 以及相應(yīng)的特點(diǎn)；掌握進(jìn)程通信中的基本概念內(nèi)容包括 競爭條件、臨界區(qū)、互斥、臨界區(qū)的求解原則、信號(hào)量、 進(jìn)程調(diào)度所需要考慮的因素、具體的各種進(jìn)程調(diào)度算法 （先

2、來先服務(wù)、時(shí)間片輪轉(zhuǎn)、優(yōu)先級(jí)調(diào)度、多重隊(duì)列、 最短作業(yè)優(yōu)先算法）等； 能夠運(yùn)用所學(xué)的進(jìn)程通信的知識(shí)，分析軟件算法中所存 在的問題，并能夠在分析問題的基礎(chǔ)上能運(yùn)用相應(yīng)的知 識(shí)解決實(shí)際應(yīng)用中的相應(yīng)問題； 第三部分輸入/輸出系統(tǒng) 掌握：I/O設(shè)備的硬件軟件原理，能夠區(qū)分相關(guān)的I/O操 作具體是在拿一軟件層次上完成。了解死鎖的定義、 死鎖發(fā)生的必要條件以及處理死鎖的策略，針對(duì)于這 些處理策略有哪些相應(yīng)的算法來解決；磁盤軟件以及 磁盤臂調(diào)度算法、磁盤出錯(cuò)的處理等，掌握時(shí)鐘軟件 所完成的任務(wù) 運(yùn)用：根據(jù)系統(tǒng)給出的資源分配圖能夠分析判斷系統(tǒng) 的狀態(tài)；根據(jù)實(shí)際的情況能夠?qū)/O設(shè)備的處理進(jìn)行優(yōu) 化設(shè)置； 第四

3、部分存儲(chǔ)器管理 存儲(chǔ)器的重定位和保護(hù)； 固定分區(qū)與可變分區(qū)的概念； 可變分區(qū)的內(nèi)存管理以及使用鏈表的內(nèi)存管理中的 分配算法； 分頁的虛擬存儲(chǔ)器的實(shí)現(xiàn)過程，虛擬地址到物理地 址的轉(zhuǎn)化過程； 頁面的替換算法； 分頁系統(tǒng)中的設(shè)計(jì)問題； 第五部分文件系統(tǒng) 文件系統(tǒng)的基本概念：文件命名、文件結(jié)構(gòu)、文件類型、 文件存儲(chǔ)、文件屬性、文件操作、層次目錄系統(tǒng)、路徑 名稱、目錄操作；掌握文件系統(tǒng)的實(shí)現(xiàn)（文件的實(shí)現(xiàn)、 目錄實(shí)現(xiàn)）、磁盤空間的管理、文件系統(tǒng)的可靠性、文 件系統(tǒng)的性能；安全性 判斷個(gè)判斷個(gè) 個(gè)大題（分）個(gè)大題（分） 算法應(yīng)用算法應(yīng)用 應(yīng)用理論應(yīng)用理論 編程應(yīng)用編程應(yīng)用 作業(yè)調(diào)度作業(yè)調(diào)度 進(jìn)程調(diào)度進(jìn)程調(diào)度

4、 FCFS.SJF.RR(Round Robin) 時(shí)間片輪轉(zhuǎn) 3.3.內(nèi)外存交換調(diào)度（頁面置換）內(nèi)外存交換調(diào)度（頁面置換） OPT OPT （clock policyclock policy） FIFOFIFO、LRU LRU SecondSecondchancechance變境強(qiáng)型（變境強(qiáng)型（NURNUR） P P頁頁 4.4.磁盤空白塊管理算法磁盤空白塊管理算法 位圖位圖鏈表鏈表 FF.NF.BF.WF.FF.NF.BF.WF.伙伴伙伴 磁盤讀寫臂調(diào)度算法磁盤讀寫臂調(diào)度算法 FCFSFCFS、SSTFSSTF、SCANSCAN、LOOK.LOOK. 地址映射與轉(zhuǎn)換地址映射與轉(zhuǎn)換 虛地址與

5、實(shí)地址，地址轉(zhuǎn)換圖虛地址與實(shí)地址，地址轉(zhuǎn)換圖 UNIXUNIX文件系統(tǒng)結(jié)構(gòu)與文件系統(tǒng)結(jié)構(gòu)與i i結(jié)點(diǎn)。結(jié)點(diǎn)。 P.VP.V操作、讀寫者問題（讀者優(yōu)先）？操作、讀寫者問題（讀者優(yōu)先）？ 9 9 資源管理，死鎖分析與研究資源管理，死鎖分析與研究 例例假設(shè)系統(tǒng)由相同類型的m個(gè)資源組成，系 統(tǒng)有n個(gè)進(jìn)程，每個(gè)進(jìn)程至少請(qǐng)求一個(gè)資源， 證明：當(dāng)n個(gè)進(jìn)程最多需要的資源之和小于m+n 時(shí)，該系統(tǒng)無死鎖。 解：解： 證明：假設(shè)當(dāng)n個(gè)進(jìn)程最多需要的資源之和小 于m+n，系統(tǒng)死鎖。 n i i nm 1 max 最多需求 n i n i n i iii LoanNeed 111 max 還需求 已占有 因?yàn)橄到y(tǒng)死鎖

6、 mLoani nmnmNeedi)( 至少在一個(gè)Pi 其Needi=0，此時(shí)Pi不死鎖， 與假設(shè)題意矛盾，所以系統(tǒng)不死鎖。 2.某系統(tǒng)中有六臺(tái)打印機(jī)，N個(gè)進(jìn)程共享打 印機(jī)資源，每個(gè)進(jìn)程要求兩臺(tái)，試問N取 哪些值時(shí)，系統(tǒng)才不會(huì)發(fā)生死鎖？ 解：解：由上可知 證：n個(gè)進(jìn)程最多需要的資源之和小于6+n 時(shí)，該系統(tǒng)無死鎖，即2n6+n，n6時(shí)系統(tǒng)也會(huì)出現(xiàn)死鎖。 而n=5時(shí)，最糟情況下也會(huì)有 P1P5 此時(shí)可化簡為完全可化簡圖，不死鎖。 同理1n5時(shí)也不死鎖， n取值為1，2，3，4，5。 例題例題2. 設(shè)某系統(tǒng)有一設(shè)某系統(tǒng)有一256k的空白區(qū)，現(xiàn)有的空白區(qū)，現(xiàn)有 以下作業(yè)序列和對(duì)內(nèi)存的要求：以下作業(yè)序

7、列和對(duì)內(nèi)存的要求： 作業(yè)1要140k，作業(yè)2要求16k，作業(yè)3要 求80k，作業(yè)1完成，作業(yè)3完成，作業(yè)4要求 70k，作業(yè)5要求128k。 試用首次適應(yīng)和最佳適應(yīng)算法對(duì)上述作 業(yè)進(jìn)行可變分區(qū)存貯分配(繪圖)并討論。 解：解： job1 (140k) job2(16k) job3(80k) 140k 156k 236k 256k job5(128k) job2(16k) 128k 140k 156k job4(70k) 226k 256k job4(70k) 70k 86k 214k job2(16k) job5(128k) 256k 浮動(dòng) FF BF job4(70k) job2(16k)

8、70k 140k 156k job5無法分配 256k 例題例題3. 在一個(gè)請(qǐng)求頁式存儲(chǔ)系統(tǒng)中，一程序的在一個(gè)請(qǐng)求頁式存儲(chǔ)系統(tǒng)中，一程序的 頁面走向?yàn)轫撁孀呦驗(yàn)?.3.2.1.4.3.5.4.3.2.1.5采取采取LRU頁頁 面置換算法，設(shè)分配給該程序的存儲(chǔ)塊數(shù)面置換算法，設(shè)分配給該程序的存儲(chǔ)塊數(shù)M 分別為分別為3和和4時(shí)，請(qǐng)求出在訪問過程中發(fā)生的時(shí)，請(qǐng)求出在訪問過程中發(fā)生的 缺頁次數(shù)和缺頁率，并比較所得結(jié)果，從中缺頁次數(shù)和缺頁率，并比較所得結(jié)果，從中 可得到什么啟發(fā)？可得到什么啟發(fā)？ 解：解：當(dāng)M3時(shí) 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1

9、 5 4 3 2 1 4 3 5 4 3 2 1 4 3 2 1 4 3 5 4 3 2 + + + + + + + + + 初值 缺頁10次，缺頁中斷率為%3 .83%100 12 10 當(dāng)M4時(shí) 缺頁7次，缺頁中斷率為 %6 .66%100 12 8 在LRU算法下，當(dāng)M增大時(shí)，缺頁次數(shù)減少， 缺頁中斷率也減少。 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1 5 4 3 2 1 4 3 5 4 3 2 1 4 3 2 1 4 3 5 4 3 2 + + + + + 4 3 2 1 1 1 5 4 3 初值 + 例題4.假定五個(gè)作業(yè)AE提交時(shí)間相

10、同，且實(shí)際需要 運(yùn)行的時(shí)間分別是10、6、2、4和8分鐘，外部分配 的優(yōu)先級(jí)數(shù)分別是3、5、2、1和4，(設(shè)數(shù)值大的優(yōu) 先數(shù)高)。忽略CPU的切換時(shí)間，分別就下列幾種調(diào) 度 算 法 計(jì) 算 作 業(yè) 的 平 均 周 轉(zhuǎn) 時(shí) 間 。 a. 輪轉(zhuǎn)法； b. 優(yōu)先級(jí)調(diào)度； c. SJF 解：解： 運(yùn)行t 優(yōu)先級(jí) 106248 35214 (a) 輪轉(zhuǎn)法：輪轉(zhuǎn)法：(時(shí)間片以及時(shí)間片以及CPU切換時(shí)間都切換時(shí)間都 較小可忽略較小可忽略) C完成：25=10分鐘 D完成：10+(42)4=18分鐘 調(diào)度次序：CDBEA E完成：24+(86)2=28分鐘 A完成：28+(108)1=30分鐘 )(22 5

11、3028241810 分鐘 T B完成：18+(64)3=24分鐘 (b) 優(yōu)先級(jí)調(diào)度優(yōu)先級(jí)調(diào)度 5 ) 421086 () 21086 ()1086 () 86 (6 T 5 302624146 )(20 分鐘 調(diào)度次序：BEACD (c) SJF 5 )108642() 8642() 642() 42(2 T 5 30201262 )(14 分鐘 調(diào)度次序：CDBEA 例題5.設(shè)有一個(gè)數(shù)據(jù)區(qū)，有若干進(jìn)程要去讀或?qū)懰?遵循下列原則： 寫是互斥的，當(dāng)一進(jìn)程正在寫時(shí)，其它進(jìn)程既 不能寫，也不能讀； 讀可同時(shí)進(jìn)行，只要沒有進(jìn)程正在寫，則任何 進(jìn)程都可以讀，請(qǐng)用P，V操作寫出讀寫過程的 同步算法(

12、要給出信號(hào)量物理意義以及初值) 答：答：var mutex,wrt:Semaphore; readcount:integer; mutex:=wrt:=1; readcount:=0; parbegin Readeri:begin Wait(mutex); readcount:=readcount+1; ifreadcount=1thenWait(wrt); Signal(mutex); 讀數(shù)據(jù)集； Wait(mutex); readcount:=readcount1; ifreadcount=0thenSignal(wrt); Signal(mutex); end Writeri:begin Wait(wrt); 寫數(shù)據(jù)集; Signal(wrt); end coend 例題6.有一閱覽室，讀者進(jìn)入時(shí)必須先在一張登 記表上進(jìn)行登記，該表為每一座位列一表目， 包括座號(hào)和讀者姓名。讀者離開時(shí)要消掉登記 信號(hào)，閱覽室中共有100個(gè)座位，請(qǐng)問： (1)為描述讀者的動(dòng)作，應(yīng)編寫幾個(gè)程序？設(shè) 置幾個(gè)進(jìn)程？進(jìn)程與程序間的對(duì)應(yīng)關(guān)系如 何？ (2)用類Pascal語言和Wait,Signal操作寫出這 些進(jìn)程間的同步算法。 答：答：(1)應(yīng)編寫1個(gè)程序；設(shè)置2個(gè)進(jìn)程； 進(jìn)程與程序間的對(duì)應(yīng)關(guān)系是：多對(duì)多對(duì)1。 (2) begin