計算機(jī)操作系統(tǒng)課件

“操作系統(tǒng)原理”課程

總復(fù)習(xí)（10級）

一、期末試卷組成題型分?jǐn)?shù)單項選擇題10分析解答題20應(yīng)用題60綜合題10合計100二、各教學(xué)單元比重引論(1章)5’處理機(jī)管理(2,3章)33’存儲器管理(4章)19’設(shè)備管理(5章)12’文件管理(6章)

19’操作系統(tǒng)接口(7章)

2’綜合

（全書）10’三、教材中刪除章節(jié)1.53.44.3.4-4.3.74.8.3-4.8.46.6-6.7第8章及以后四、需掌握的典型算法及應(yīng)用1.調(diào)度算法（范圍：先來先服務(wù)、短優(yōu)先、非剝奪式優(yōu)先級）2.銀行家算法3.頁面置換算法（范圍：先進(jìn)先出、理想型、最近最久未使用）4.頁式管理之地址變換5.磁盤調(diào)度算法（范圍：先來先服務(wù)、最短尋道時間優(yōu)先、SCAN）6.位示圖的分配回收7.FAT計算8.i結(jié)點混合索引

9.進(jìn)程同步控制—生產(chǎn)者-消費者問題及變形10.SPOLLING及應(yīng)用、成組鏈接法例1：4個進(jìn)程ABCD的到達(dá)時間和要求系統(tǒng)的服務(wù)時間如下表，請分析按照FCFS算法進(jìn)行調(diào)度時的執(zhí)行過程，并填寫下表。執(zhí)行過程如下進(jìn)程名到達(dá)時間服務(wù)時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A010111B110011011001C21101102100100D31001022021991.99ABCD0進(jìn)程時間1101102202Wi=Ti/TSTi=T完成i-T提交i答：例1：4個進(jìn)程ABCD的到達(dá)時間和要求系統(tǒng)的服務(wù)時間如下表，請分析按照SPF算法進(jìn)行調(diào)度時的執(zhí)行過程，并填寫下表。執(zhí)行過程如下進(jìn)程名到達(dá)時間服務(wù)時間開始執(zhí)行時間完成時間周轉(zhuǎn)時間帶權(quán)周轉(zhuǎn)時間A010111B110011011001C21101102100100D31001022021991.99ABCD0進(jìn)程時間1101102202Wi=Ti

/TSTi=T完成i-T提交i答：例2：考慮5個進(jìn)程P1P2P3P4P5如下表，規(guī)定進(jìn)程的優(yōu)先數(shù)越小優(yōu)先級越高，請分析按照非剝奪式優(yōu)先級調(diào)度算法時各進(jìn)程執(zhí)行過程，并計算采用每算法時的平均周轉(zhuǎn)時間（假設(shè)忽略進(jìn)程的調(diào)度時間）。非剝奪式HPF過程如下:391318進(jìn)程創(chuàng)建時刻運(yùn)行時間／ms優(yōu)先數(shù)P1033P2265P3441P4652P58240進(jìn)程時間P1P2P3P4P520T1＝3-0＝3T2＝9-2＝7T3＝13-4＝9T4＝18-6＝12T5＝20-8＝12T＝（3+7+9+12+12）／5＝8.60Ti=T完成i-T提交i答：例3：設(shè)系統(tǒng)中有三種類型的資源（A、B、C）和五個進(jìn)程（P1、P2、P3、P4、P5），當(dāng)前系統(tǒng)中出現(xiàn)下述資源分配情況：AllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656利用銀行家算法，試問：（要求寫出判斷過程）（1）該狀態(tài)是否安全？（2）如果進(jìn)程P2提出資源請求Request（1，2，2，2）后，系統(tǒng)能否將資源分配給它？1）此刻安全性分析情況：WorkNeedAllocationWork+AllocationFinishP01622001200321654TP31654065203321986TP419860656001419910TP1199101750100029910TP229910235613543121414T此時存在一個安全序列{P0，P3，P4，P1,P2},故該狀態(tài)是安全的。答：2）P2請求Request（1，2，2，2），按銀行家算法檢查：①

Request（1，2，2，2）≤Need（2，3，5，6）

②Request（1，2，2，2）≤Available（1，6，2，2）

答：

試分配,并修改相應(yīng)的數(shù)據(jù)結(jié)構(gòu)，資源分配情況如下：再利用安全性算法檢查系統(tǒng)狀態(tài)是否安全，可利用資源向量Available（0，4，0，0）已不能滿足任何進(jìn)程的需要，故系統(tǒng)進(jìn)入不安全狀態(tài)，所以系統(tǒng)不能將資源分配給它。

例4：請求分頁系統(tǒng)中一進(jìn)程P共有10頁，系統(tǒng)為其在內(nèi)存中分配三個物理塊，初始均為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5。當(dāng)采用FIFO置換算法時，計算訪問過程中發(fā)生的缺頁中斷率。內(nèi)存缺頁？4，3，2，1，4，3，5，4，3，2，1，5443432132214143321是是是是是是是435否435435否是352是521否521共缺頁中斷9次，缺頁中斷率為：9／12＝75％為了方便找出先進(jìn)來的那個頁，采用模擬隊列的寫法更方便例4：請求分頁系統(tǒng)中一進(jìn)程P共有10頁，系統(tǒng)為其在內(nèi)存中分配三個物理塊，初始均為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5。當(dāng)采用OPT置換算法時，計算訪問過程中發(fā)生的缺頁中斷率。內(nèi)存缺頁？4，3，2，1，4，3，5，4，3，2，1，5443432431431431是是是是否否是435否435435否是235是215否215共缺頁中斷7次，缺頁中斷率為：7／12＝58.3％例4：請求分頁系統(tǒng)中一進(jìn)程P共有10頁，系統(tǒng)為其在內(nèi)存中分配三個物理塊，初始均為空，頁面走向為4，3，2，1，4，3，5，4，3，2，1，5。當(dāng)采用LRU置換算法時，計算訪問過程中發(fā)生的缺頁中斷率。內(nèi)存缺頁？4，3，2，1，4，3，5，4，3，2，1，5443432132142143是是是是是是是543否543543否是243是213是215共缺頁中斷10次，缺頁中斷率為：10／12＝83.3％例5：一個分頁式存儲管理系統(tǒng)中，用戶虛擬空間共有32個頁面，每頁1KB，假定某時刻用戶的第0，1，2，3頁分別分配的物理塊號為10，8，4，17，求：（1）邏輯地址的有效位是多少？并給出邏輯地址的結(jié)構(gòu)。（2）將邏輯地址（2500）D轉(zhuǎn)換為物理地址。答：1）邏輯地址的有效位數(shù)是15位。

邏輯地址結(jié)構(gòu)表示：

例5：一個分頁式存儲管理系統(tǒng)中，用戶虛擬空間共有32個頁面，每頁1KB，假定某時刻用戶的第0，1，2，3頁分別分配的物理塊號為10，8，4，17，求：（1）邏輯地址的有效位是多少？并給出邏輯地址的結(jié)構(gòu)。（2）將邏輯地址（2500）D轉(zhuǎn)換為物理地址。答：2）對邏輯地址（2500）D：P＝int（2500／1K）＝2W＝2500％1K＝452由已知，頁號P＝2對應(yīng)的頁面號P’＝4，邏輯（2500）D對應(yīng)物理地址＝P’×1K＋W＝（4548）D

例6：針對某盤面的磁盤服務(wù)請求順序如下:55,58,39,18,90,160,150,38,184號磁道(當(dāng)前磁頭在100號磁道上且向增加方向移動).分析按先來先服務(wù)、最短尋道時間優(yōu)先、掃描算法執(zhí)行的順序及平均尋道距離?？倢さ谰嚯x如下:|55-100|+|58-55|+|39-58|+|18-39|+|90-18|+|160-90|+|150-160|+|38-150|+|184-38|=498平均尋道距離:498/9=55.3先來先服務(wù)滿足請求的次序是55，58，39，18，90，160，150，38，184

總尋道距離如下:|90-100|+|58-90|+|55-58|+|39-55|+|38-39|+|18-38|+|150-18|+|160-150|+|184-160|=248平均尋道距離:248/9=27.55例6：針對某盤面的磁盤服務(wù)請求順序如下:55,58,39,18,90,160,150,38,184號磁道(當(dāng)前磁頭在100號磁道上且向增加方向移動).分析按先來先服務(wù)、最短尋道時間優(yōu)先、掃描算法執(zhí)行的順序及平均尋道距離。最短尋道時間優(yōu)先滿足請求的次序是90，58，55，39，38，18，150，160，184

例6：針對某盤面的磁盤服務(wù)請求順序如下:55,58,39,18,90,160,150,38,184號磁道(當(dāng)前磁頭在100號磁道上且向增加方向移動).分析按先來先服務(wù)、最短尋道時間優(yōu)先、掃描算法執(zhí)行的順序及平均尋道距離。掃描算法總尋道距離如下:|150-100|+|160-150|+|184-160|+|90-184|+|58-90|+|55-58|+|39-55|+|38-39|+|18-38|=250平均尋道距離:250/9=27.8滿足請求的次序是150，160，184，90，58，55，39，38，18

位示圖利用一個二進(jìn)制位反映磁盤空間中每個塊的分配使用情況。每個物理塊對應(yīng)一個Bit位,一般，已分配物理塊為1，未分配為0。

m×n大小的位示圖可以表示的磁盤總塊數(shù)為m╳n。位示圖可以用二維數(shù)組描述：map[m,n]1.盤塊的分配

(1)順序掃描位示圖，從中找出一個或一組其值為“0”的二進(jìn)制位(“0”表示空閑時)。(2)將所找到的一個或一組二進(jìn)制位，轉(zhuǎn)換成與之相應(yīng)的盤塊號。假定找到的其值為“0”的二進(jìn)制位，位于位示圖的第i行、第j列，則其相應(yīng)的盤塊號應(yīng)按下式計算：b=n(i-1)+j式中，n代表每行的位數(shù)。(3)修改位示圖，令map［i,j］=1。位示圖2.盤塊的回收

(1)將回收盤塊的盤塊號轉(zhuǎn)換成位示圖中的行號和列號。轉(zhuǎn)換公式為：

i=(b-1)DIVn+1j=(b-1)MODn+1(2)修改位示圖。令map［i,j］=0。位示圖

b=n×i+j+1

i=(b-1)DIVn

j=(b-1)MODn位示圖注意：若行列號均從0開始編號，盤塊號從1開始編號。則：例7:某文件系統(tǒng)采用半字節(jié)尋址方式，如果磁盤容量為500MB，盤塊大小為1KB，采用顯式鏈接分配方式時，問：1）每個FAT表項需占多少二進(jìn)制位？其FAT需占多少存儲空間？2）如果文件A依次占用11、23、25號盤塊，畫出A中各盤塊間的鏈接情況及FAT的情況。答：1）盤塊個數(shù)為500MB/1KB＝500K（個）由FAT表項個數(shù)與磁盤塊個數(shù)的對應(yīng)關(guān)系可知，F(xiàn)AT共有500K個表項（表項編號為0～500K-1）

256K<500K<512K,每個FAT表項最少用19位二進(jìn)制表示，若系統(tǒng)限定采用半字節(jié)尋址，則可擴(kuò)展為20位。FAT表空間大?。?0b/8b×500K=1250KBFAT表每項位數(shù)需擴(kuò)展到8的倍數(shù)，即24位二進(jìn)制表示請你思考：若系統(tǒng)限定采用單字節(jié)尋址呢？

FATA的FCB

112325文件名：A首塊號：11............

2325EOF......答：2）圖示如下：例7:某文件系統(tǒng)采用半字節(jié)尋址方式，如果磁盤容量為500MB，盤塊大小為1KB，采用顯式鏈接分配方式時，問：1）每個FAT表項需占多少二進(jìn)制位？其FAT需占多少存儲空間？2）如果文件A依次占用11、23、25號盤塊，畫出A中各盤塊間的鏈接情況及FAT的情況。例8:存放在某磁盤上的文件系統(tǒng)采用混合索引分配方式，文件的FCB中共有13個地址項，其中第0—9項是直接地址，第10、11、12項分別是一次、二次、三次間接地址。設(shè)每個盤塊的大小為1K字節(jié)，一個盤塊號占4字節(jié)。問：1）該系統(tǒng)允許一個文件最多可以占用多少個磁盤塊的空間？2）若文件所有信息均在外存，描述訪問文件中字節(jié)偏移量為263168的信息的過程？并指出該過程中需要啟動磁盤幾次？答：1）每個盤塊最多存放1KB/4B=256個盤塊地址該系統(tǒng)允許一個文件最多可以使用磁盤塊的個數(shù)為：

10+256+2562+2563塊2）若文件所有信息均在外存，描述訪問文件中字節(jié)偏移量為263168的信息的過程？并指出該過程中需要啟動磁盤幾次？偏移量263168/1024=257

所以字節(jié)偏移量263168對應(yīng)邏輯塊號為257，塊內(nèi)偏移量為0，由于10<257<266，而257-10=247，故可以直接從文件的FCB的第10個地址項處得到一次間址塊的地址，并從一次間址塊的第247項中獲得對應(yīng)得物理盤塊號，到該塊塊內(nèi)偏移量為0處訪問即可。該過程中需要啟動磁盤3次。例9:操作系統(tǒng)在鍵盤管理中引入了鍵盤緩沖區(qū)，鍵盤緩沖區(qū)采用循環(huán)隊列，鍵盤輸入進(jìn)程pin負(fù)責(zé)將用戶鍵入的字符存入緩沖區(qū)，鍵盤輸出進(jìn)程pout負(fù)責(zé)從緩沖區(qū)