操作系統(tǒng)原理重點知識點

1、注意：大題必看否則很難及格！1、 什么是操作系統(tǒng)：操作系統(tǒng)是配置在計算機硬件上帶第一層軟件，是對硬件系統(tǒng)的首次擴充。2、 操作系統(tǒng)的作用：OS 作為用戶與計算機硬件系統(tǒng)之間帶接口、OS 作為計算機系統(tǒng)資源帶管理者、 OS 實現(xiàn)啦對計算機資源帶抽象3、 操作系統(tǒng)的目標(biāo)：有效性、方便性、可擴充性、開放性4、 操作系統(tǒng)基本特征（并發(fā)性共享性 虛擬性 異步性）其中最重要的特征是并發(fā)性5、 操作系統(tǒng)帶主要功能：處理機管理存儲器管理設(shè)備管理文件管理用戶接口6、進(jìn)程的三種基本狀態(tài)：就緒- （進(jìn)程調(diào)度） - 執(zhí)行 -（ I/O請求） - 阻塞 -（ I/O完成）-就緒執(zhí)行 -（時間片用完） -就緒（ P38頁

2、）7、進(jìn)程的特征：動態(tài)性并發(fā)性 獨立性 異步性8、批處理系統(tǒng)帶特征：脫機多道 成批處理9、分時系統(tǒng)帶特征：多路性獨立性 及時性交互性10、常用 I/O 控制方式有：程序直接控制方式、中斷控制方式、DMA方式、通道方式 。11、為什么要引入緩沖區(qū)？(1) 緩和 CPU與 I/O設(shè)備間速度不匹配的矛盾。(2)減少對 CPU的中斷頻率，放寬對 CPU中斷響應(yīng)時間的限制。(3)提高 CPU和 I/O設(shè)備之間的并行性12、 SPOOLing 系統(tǒng)由哪幾部分組成？以打印機為例說明如何利用該技術(shù)實現(xiàn)多個進(jìn)程對打印機的共享？組成：輸人井和輸出井輸入緩沖區(qū)和輸出緩沖區(qū)輸入進(jìn)程和輸出進(jìn)程對所有提出輸出請求的用戶進(jìn)

3、程，系統(tǒng)接受它們的請求時，并不真正把打印機分配給它們，而是由輸出進(jìn)程在輸出井中為它申請一空閑緩沖區(qū)，并將要打印的數(shù)據(jù)卷入其中，輸出進(jìn)程再為用戶進(jìn)程申請一張空白的用戶打印請求表，并將用戶的打印請求填入表中，再將該表掛到打印機隊列上。這時，用戶進(jìn)程覺得它的打印過程已經(jīng)完成，而不必等待真正的慢速的打印過程的完成。當(dāng)打印機空閑時， 輸出進(jìn)程將從請求隊列隊首取出一張打印請求表，根據(jù)表中的要求將要打印的數(shù)據(jù)從輸出井傳到內(nèi)存輸出緩沖區(qū)，再由打印機進(jìn)行輸出打印。打印完后， 再處理打印隊列中的一個打印請求表，實現(xiàn)了對打印機的共享。13、什么是死鎖？產(chǎn)生死鎖的必要條件有哪些？處理死鎖的方法？所謂死鎖是指多個進(jìn)程在

4、運行過程中因爭奪資源而造成帶一種僵局，當(dāng)進(jìn)程處于這種僵持狀態(tài)時， 若無外力作用，他們都將無法再向前推進(jìn)。必要條件： 互斥條件請求和保持條件 不剝奪條件 環(huán)路等待條件處理方法：預(yù)防死鎖避免死鎖 檢驗死鎖解除死鎖以上為簡答題可能出帶部分以下全為計算題做題時照貓畫虎就差不多計算過程比較簡單有不懂得同學(xué)趕快在考試之前問一下懂的同學(xué)保證你考試能打60 分以上。 呵呵應(yīng)用題1、 調(diào)度算法（ FCFS/SPF 高度優(yōu)先權(quán)時間片輪轉(zhuǎn)）有 5 個進(jìn)程 P1、 P2、P3、P4、P5，它們的創(chuàng)建時刻、運行時間和優(yōu)先數(shù)見下表。規(guī)定進(jìn)程的優(yōu)先數(shù)越小其優(yōu)先級越高。 試描述在采用下述調(diào)度算法時， 各進(jìn)程的運行過程， 并計

5、算平均周轉(zhuǎn)時間（假設(shè)忽略進(jìn)程的調(diào)度時間，時間單位為ms）。（1）先來先服務(wù)算法。（ 2）剝奪式優(yōu)先級調(diào)度算法。 （此問可去掉。增加非剝奪式）進(jìn)程創(chuàng)建時刻運行時間優(yōu)先數(shù)P1033P2265P3441P4652P5824答：1）先來先服務(wù)調(diào)度算法：程序的運行過程如下圖：可知：每個進(jìn)程的周轉(zhuǎn)時間為：T1=3ms；T2=9-2=7ms；T3=13-4=9ms；T4=18-6=12ms；T5=20-8=12ms。系統(tǒng)平均周轉(zhuǎn)時間為：T=（ 3+7+9+12+12） /5=8.6ms2）剝奪式優(yōu)先級調(diào)度算法：程序的運行過程如下圖：時間（ ms）可知：每個進(jìn)程的周轉(zhuǎn)時間為：T1=3-0=3ms；T2=20-

6、2=18ms；T3=8-4=4ms；T4=13-6=7ms；T5=15-8=7ms系統(tǒng)平均周轉(zhuǎn)時間為：T=（ 3+18+4+7+7）/5=7.8ms2、 銀行家算法在銀行家算法中，T 時刻的狀態(tài)如下表，試問：（ 1） T 時刻是否安全？（ 2）若 P2 提出請求（ 1， 2，2， 2）后，系統(tǒng)能否分配資源？要求：寫出判斷的過程。進(jìn)程AllocationNeedAvailableP000320012P110001750P2135423561622P303320652P400140656答：（ 1）利用安全性算法對上面的狀態(tài)進(jìn)行分析：workNeedAllocationWork+ Allocati

7、onfinishP01622001200321654TP31654065203321986TP11986175010002986TP22986235613543121310TP43121310065600143121414T找到一個安全序列P0,P3， P1, P2,P4 ，所以 T 時刻系統(tǒng)是安全的。（ 2） P2發(fā)出請求向量Request(1,2,2,2)后，系統(tǒng)按銀行家算法進(jìn)行檢查： Request(1,2,2,2) Need(2,3,5,6) Request(1,2,2,2) Available(1,6,2,2)系統(tǒng)進(jìn)行資源的試分配，并修改相應(yīng)變量的值A(chǔ)vailable (0,4,0,

8、0)Allocation（ 2,5,7,6）Need=(1,1,3,4)進(jìn)行安全性檢查：此時對所有進(jìn)程Need Available(0,4,0,0)都不成立，系統(tǒng)進(jìn)入不安全狀態(tài)。系統(tǒng)不能將資源分配給P2。3、 動態(tài)分區(qū). 對下圖所示的內(nèi)存分配情況（空白部分表示空閑塊）若要申請一塊 40K 的內(nèi)存，按照最先適應(yīng)算法、 最佳適應(yīng)算法、 最差適應(yīng)算法分配的首地址分別為什么？能使首地址最大的分配策略是什么？答： 最先適應(yīng)算法分配的首地址為：100KB最佳適應(yīng)算法分配的首地址為：330KB空閑區(qū)大小80K最差適應(yīng)算法分配的首地址為：410KB空閑區(qū)大小90K能使首地址最大的分配策略是最差適應(yīng)算法空閑區(qū)大

9、小60K空閑區(qū)大小102K4、 基本分頁 / 段儲存管理1. 某分頁系統(tǒng)的用戶空間共有32 個頁面，每頁 1KB，主存空間為 16KB，試問：1） 邏輯地址的有效位是多少？格式如何？物理地址需多少二進(jìn)制位表示？.2）假定某時刻系統(tǒng)為用戶的第0、 1、2、 3 頁分別分配的物理塊號為2、 10、4、 7，試將邏輯地址1023（十進(jìn)制）轉(zhuǎn)換為對應(yīng)的物理地址？并以邏輯地址1023（十進(jìn)制）為例畫出地址變換過程。答： 1）法一：用戶空間共有32 個頁面，故邏輯地址中的頁號須用5 位來描述。 ( 頁號范圍 :031); 每頁 1KB，故頁內(nèi)地址須用 10 位描述。 ( 頁內(nèi)地址范圍 :01023)所以邏

10、輯地址共有：5+10=15 位。法二：用戶空間大小為32 頁 *1KB/ 頁 =32 KB，32 KB=215 B，所以邏輯地址共有 15位。其格式為： 14 10 90頁號 P頁內(nèi)地址 W內(nèi)存空間大小為16KB， 16 KB=214 B，所以物理地址共有14 位。2) 邏輯地址（ 1023）D頁號 =int(1023/1024)=0頁內(nèi)地址 =1023%1024=1023，由頁表得， P=0 對應(yīng)的 P =2其物理地址 =1024*2+1023=3071（注：若求出的頁號超過頁表長度，則可以直接判斷是非法的邏輯地址）越 界 中頁表寄存器頁表始址頁表>邏輯地址 1023+0頁 號內(nèi) 存0

11、22110物理地址 307124以邏輯地址371023 為例的地址變換過程如圖：2、在一段式存儲管理系統(tǒng)中，段表如下，試求出下列邏輯地址對應(yīng)的物理地址？段號內(nèi)存始址段長02105001235020210090313505904193895（ 0， 430）（ 1， 10）（ 2， 500） （ 3， 400）（ 4， 122）（ 5，132）答：邏輯地址（0， 430）或?qū)懗?0 ， 430 的物理地址 =210+430=640邏輯地址（ 1， 10）的物理地址 =2350+10=2360邏輯地址（ 2， 500）的物理地址 =100+500=600因為 500>90，所以屬于段內(nèi)地址越

12、界引起的非法地址訪問邏輯地址（ 3， 400）的物理地址=1350+400=1750邏輯地址（ 4， 122），因為 122>95，所以屬于段內(nèi)地址越界引起的非法地址訪問邏輯地址（ 5， 132），因為 5>4，所以屬于段號越界引起的非法地址訪問5、 頁面置換算法（OPT/FIFO/LUR最佳置換 / 先進(jìn)先出 / 最近最久未使用）在一個請求分頁中若一個作業(yè)的頁面訪問順序為：432143543215 ，當(dāng)系統(tǒng)分配給該作業(yè)的物理塊數(shù) M分別為 3 和 4（且初始均為空） 時，分別采用 FIFO 置換法和 OPT置換法求缺頁中斷率，并比較得到的結(jié)果。 （此類題要注意初始時，內(nèi)存塊是否為

13、空？還是預(yù)先調(diào)入若干頁。）答案：（ 1）FIFO 法 (M=3):注意：若初始時，預(yù)先調(diào)入 4，3， 2 頁，則前 3 次不缺頁。（視具體調(diào)入的頁號與訪問序列而定）（ 2） OPT法： (M=3)（ 3） OPT法： m=3時，缺頁中斷 7 次， m=4時，缺頁中斷 6 次，可見，增加分配給作業(yè)的內(nèi)存塊數(shù)，可降低缺頁率。FIFO 法： m=3時，缺頁中斷9 次， m=4時，缺頁中斷10 次，可見，增加分配給作業(yè)的內(nèi)存塊數(shù)，反而提高了缺頁率。FIFO 頁面淘汰算法會產(chǎn)生異常現(xiàn)象，對特定的訪問序列，當(dāng)分配給進(jìn)程的物理頁面數(shù)增加時，缺頁次數(shù)反而也增加。稱為Belady 異常。注：如何判斷一個頁是否在

14、內(nèi)存- 根據(jù)擴充頁表的狀態(tài)位P?？梢杂嬎忝糠N算法下調(diào)頁耗費的時間：次數(shù)* 每頁調(diào)入的時間。6、 磁盤調(diào)度算法(FCFS/SSTF/SCAN/CSCAN先來先服務(wù) / 最短尋道時間優(yōu)先/ 掃描算法 / 循環(huán)掃描 )某一磁盤先后有4 個進(jìn)程提出了磁盤訪問請求，按申請到達(dá)的先后順序依次為：43，66，26， 88。系統(tǒng)中磁頭停留在磁道號為68 的磁道上，且移動臂正沿磁道號遞減的方向移動。求出分別采用FCFS、SSTF和 SCAN磁盤調(diào)度算法時，磁道的訪問順序及其所需尋道長度（走過多少柱面）。 ( 會描述對應(yīng)的算法思想)答： 1） FCFS磁盤調(diào)度算法：順序： 43， 66， 26， 88尋道長度：（

15、 68-43 ） +（ 66-43 ） +（ 66-26 ）+（ 88-26 ） =150 2） SSTF算法：順序： 66， 88， 43， 26尋道長度：（ 68-66 ） +（ 88-66 ） +（ 88-43 ）+（ 43-26 ） =863） SCAN算法：順序： 66， 43， 26， 88尋道長度：（ 68-66 ） +（ 66-43 ） +（ 43-26 ）+（ 88-26 ） =1047、 外存分配（顯示連接FAT/NTFS 索引分配）(a) 索引分配 : 存放在某個磁盤上的文件系統(tǒng), 采用混合 索引分配方式 (13 個地址項 , 同UNIX 系統(tǒng)的i 結(jié)點結(jié)構(gòu) ), 若每個

16、盤塊大小為512 字節(jié) , 磁盤塊需用3 個字節(jié)描述 , 則 :1) 該文件系統(tǒng)允許文件的最大長度是多少?析： 512 3 170 余 2，每個盤塊最多存放170 個盤塊地址，所以索引表中表項最多170 個。文件限制最大長度 （ 10 170 1702 1703 ）塊 512 字節(jié) 2471040KB 2）將文件的字節(jié)偏移量 5000， 15000， 150000 轉(zhuǎn)換為物理塊號和塊內(nèi)偏移量。析： 5000 512 9 余 392，所以字節(jié)偏移量 5000 對應(yīng)邏輯塊號為 9（從 0 開始算的），塊內(nèi)偏移量為392，由于 9<10，故可以直接從文件的FCB 的第 9 個地址項處得到物理盤

17、塊號，塊內(nèi)偏移量為392。15000 512 29 余 152，所以字節(jié)偏移量15000 對應(yīng)邏輯塊號為29（從 0 開始算的），塊內(nèi)偏移量為1592，由于10<=29<10+170，而 29-10=19 ，故可以直接從文件的 FCB 的第 10 個地址項處得到一次間址塊的地址，并從次間址塊的第19 項（即該塊的第5759 這 3 個字節(jié)處）中獲得對應(yīng)得物理盤塊號，塊內(nèi)偏移量為152。（有關(guān) 150000 ，略）3) 假定某文件的 FCB已在內(nèi)存 , 但其它信息均在外存， 試分析 : 為訪問該文件中某個位置的內(nèi)容 , 最少需要幾次啟動磁盤 ?最多需要幾次啟動磁盤 ?析：由于文件的F

18、CB已在內(nèi)存， 為訪問文件中的某個位置，最少需要1 次啟動磁盤 （直接地址）；最多需要4 次啟動磁盤（三次間址）。注：若文件所有信息均在外存？則查找FCB 操作也要算一次啟盤。故最少需要2次啟動磁盤（直接地址）；最多需要5 次啟動磁盤（三次間址）。(b) 某文件系統(tǒng)中，如果磁盤容量為12GB，盤塊大小為4KB，采用顯式鏈接分配方式時，問：（ 1）每個 FAT表項需占幾個字節(jié)（ FAT 表項的長度取字節(jié)的整數(shù)倍）？答：盤塊數(shù) =12G/4KB=3M=3KKB每個 FAT 表項需占 3 個字節(jié)（ 2）其 FAT 需占用多少存儲空間？答： FAT需占用 3B*3M=9MB（ 3）如果文件A 依次占用3、5、7 號三個盤塊，畫出A 中各盤塊間的鏈接情況及的情況。P217 頁圖（超簡單必看）FAT8、 位示圖法某計算機系統(tǒng)采用位示圖法（行號、列號和盤塊號都從1 開始編號）來管理文件存儲空間 , 且 0 表示盤塊空閑。對于32MB的磁盤，每個盤塊的大小為1KB，試具體說明如何為某文件分配一個盤塊？（回收？） 該系統(tǒng)的位示圖容量有多大？（注意： 行號、列號也可以從0 開始）答：為某文件分配一個盤塊的過程如下：1）順序檢索位示圖，從中找到一個值為0 的二進(jìn)制位。2）設(shè)行號i 列號 j ，計算出相應(yīng)的盤塊號b 為： b n× (i