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

復(fù)習(xí)題綱操作系統(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)容包括競(jìng)爭(zhēng)條件、臨界區(qū)、互斥、臨界區(qū)的求解原則、信號(hào)量、進(jìn)程調(diào)度所需要考慮的因素、具體的各種進(jìn)程調(diào)度算法（先來先服務(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è)置；第四部分存儲(chǔ)器管理存儲(chǔ)器的重定位和保護(hù)；固定分區(qū)與可變分區(qū)的概念；可變分區(qū)的內(nèi)存管理以及使用鏈表的內(nèi)存管理中的分配算法；分頁(yè)的虛擬存儲(chǔ)器的實(shí)現(xiàn)過程，虛擬地址到物理地址的轉(zhuǎn)化過程；頁(yè)面的替換算法；分頁(yè)系統(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è)大題（８０分）１．算法應(yīng)用２．應(yīng)用理論３．編程應(yīng)用二、復(fù)習(xí)綱要１．作業(yè)調(diào)度２．進(jìn)程調(diào)度＞FCFS.SJF.RR(RoundRobin)時(shí)間片輪轉(zhuǎn)3.內(nèi)外存交換調(diào)度（頁(yè)面置換）

OPT（clockpolicy）

FIFO、LRU

Second—chance變境強(qiáng)型（NUR）

P３１９頁(yè)4.磁盤空白塊管理算法

①位圖②鏈表FF.NF.BF.WF.

③伙伴５．磁盤讀寫臂調(diào)度算法

FCFS、SSTF、SCAN、LOOK.６．地址映射與轉(zhuǎn)換

虛地址與實(shí)地址，地址轉(zhuǎn)換圖７．UNIX文件系統(tǒng)結(jié)構(gòu)與i結(jié)點(diǎn)。８．P.V操作、讀寫者問題（讀者優(yōu)先）？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)死鎖。最多需求還需求已占有因?yàn)橄到y(tǒng)死鎖至少在一個(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)無死鎖，即2n<6+n，n<6。n取值為1，2，3，4，5另證：如下圖所示：當(dāng)n=6時(shí)，最糟情況有：P1P2P3P4P5P6每一進(jìn)程已占有一個(gè)資源，還申請(qǐng)一個(gè)資源，此時(shí)死鎖。同理n>6時(shí)系統(tǒng)也會(huì)出現(xiàn)死鎖。而n=5時(shí)，最糟情況下也會(huì)有P1P5……此時(shí)可化簡(jiǎn)為完全可化簡(jiǎn)圖，不死鎖。同理1<n<5時(shí)也不死鎖，n取值為1，2，3，4，5。例題2.設(shè)某系統(tǒng)有一256k的空白區(qū)，現(xiàn)有以下作業(yè)序列和對(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)140k156k236k256kjob5(128k)job2(16k)128k140k156kjob4(70k)226k256kjob4(70k)70k86k214kjob2(16k)job5(128k)256k浮動(dòng)FFBFjob4(70k)job2(16k)70k140k156kjob5無法分配256k例題3.在一個(gè)請(qǐng)求頁(yè)式存儲(chǔ)系統(tǒng)中，一程序的頁(yè)面走向?yàn)?.3.2.1.4.3.5.4.3.2.1.5采取LRU頁(yè)面置換算法，設(shè)分配給該程序的存儲(chǔ)塊數(shù)M分別為3和4時(shí)，請(qǐng)求出在訪問過程中發(fā)生的缺頁(yè)次數(shù)和缺頁(yè)率，并比較所得結(jié)果，從中可得到什么啟發(fā)？解：當(dāng)M＝3時(shí)432143543215432143543215432143543214321435432++++++++++初值缺頁(yè)10次，缺頁(yè)中斷率為當(dāng)M＝4時(shí)缺頁(yè)7次，缺頁(yè)中斷率為在LRU算法下，當(dāng)M增大時(shí)，缺頁(yè)次數(shù)減少，缺頁(yè)中斷率也減少。432143543215432143543215432143543214321435432+++++++432111543初值+例題4.假定五個(gè)作業(yè)A～E提交時(shí)間相同，且實(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í)10624835214(a)輪轉(zhuǎn)法：(時(shí)間片以及CPU切換時(shí)間都較小可忽略)C完成：2×5=10分鐘D完成：10+(4–2)×4=18分鐘調(diào)度次序：CDBEAE完成：24+(8–6)×2=28分鐘A完成：28+(10–8)×1=30分鐘B完成：18+(6–4)×3=24分鐘(b)優(yōu)先級(jí)調(diào)度調(diào)度次序：BEACD(c)SJF調(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操作寫出讀寫過程的同步算法(要給出信號(hào)量物理意義以及初值)答：varmutex,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:=readcount–1;

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ì)1。(2) begin

S1:=100(有100個(gè)座位)

S2:=0(有沒閱讀者)

mutex:=1

cobegin

P1:repeat

P(S1);

P(