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

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

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

一、期末試卷組成題型分?jǐn)?shù)單項(xiàng)選擇題10分析解答題20應(yīng)用題60綜合題10合計(jì)100二、各教學(xué)單元比重引論(1章)5’處理機(jī)管理(2,3章)33’存儲(chǔ)器管理(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)先級(jí)）2.銀行家算法3.頁(yè)面置換算法（范圍：先進(jìn)先出、理想型、最近最久未使用）4.頁(yè)式管理之地址變換5.磁盤調(diào)度算法（范圍：先來先服務(wù)、最短尋道時(shí)間優(yōu)先、SCAN）6.位示圖的分配回收7.FAT計(jì)算8.i結(jié)點(diǎn)混合索引

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

/TSTi=T完成i-T提交i答：例2：考慮5個(gè)進(jìn)程P1P2P3P4P5如下表，規(guī)定進(jìn)程的優(yōu)先數(shù)越小優(yōu)先級(jí)越高，請(qǐng)分析按照非剝奪式優(yōu)先級(jí)調(diào)度算法時(shí)各進(jìn)程執(zhí)行過程，并計(jì)算采用每算法時(shí)的平均周轉(zhuǎn)時(shí)間（假設(shè)忽略進(jìn)程的調(diào)度時(shí)間）。非剝奪式HPF過程如下:391318進(jìn)程創(chuàng)建時(shí)刻運(yùn)行時(shí)間／ms優(yōu)先數(shù)P1033P2265P3441P4652P58240進(jìn)程時(shí)間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）和五個(gè)進(jìn)程（P1、P2、P3、P4、P5），當(dāng)前系統(tǒng)中出現(xiàn)下述資源分配情況：AllocationNeedAvailableP0003200121622P110001750P213542356P303320652P400140656利用銀行家算法，試問：（要求寫出判斷過程）（1）該狀態(tài)是否安全？（2）如果進(jìn)程P2提出資源請(qǐng)求Request（1，2，2，2）后，系統(tǒng)能否將資源分配給它？1）此刻安全性分析情況：WorkNeedAllocationWork+AllocationFinishP01622001200321654TP31654065203321986TP419860656001419910TP1199101750100029910TP229910235613543121414T此時(shí)存在一個(gè)安全序列{P0，P3，P4，P1,P2},故該狀態(tài)是安全的。答：2）P2請(qǐng)求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：請(qǐng)求分頁(yè)系統(tǒng)中一進(jìn)程P共有10頁(yè)，系統(tǒng)為其在內(nèi)存中分配三個(gè)物理塊，初始均為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。當(dāng)采用FIFO置換算法時(shí)，計(jì)算訪問過程中發(fā)生的缺頁(yè)中斷率。內(nèi)存缺頁(yè)？4，3，2，1，4，3，5，4，3，2，1，5443432132214143321是是是是是是是435否435435否是352是521否521共缺頁(yè)中斷9次，缺頁(yè)中斷率為：9／12＝75％為了方便找出先進(jìn)來的那個(gè)頁(yè)，采用模擬隊(duì)列的寫法更方便例4：請(qǐng)求分頁(yè)系統(tǒng)中一進(jìn)程P共有10頁(yè)，系統(tǒng)為其在內(nèi)存中分配三個(gè)物理塊，初始均為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。當(dāng)采用OPT置換算法時(shí)，計(jì)算訪問過程中發(fā)生的缺頁(yè)中斷率。內(nèi)存缺頁(yè)？4，3，2，1，4，3，5，4，3，2，1，5443432431431431是是是是否否是435否435435否是235是215否215共缺頁(yè)中斷7次，缺頁(yè)中斷率為：7／12＝58.3％例4：請(qǐng)求分頁(yè)系統(tǒng)中一進(jìn)程P共有10頁(yè)，系統(tǒng)為其在內(nèi)存中分配三個(gè)物理塊，初始均為空，頁(yè)面走向?yàn)?，3，2，1，4，3，5，4，3，2，1，5。當(dāng)采用LRU置換算法時(shí)，計(jì)算訪問過程中發(fā)生的缺頁(yè)中斷率。內(nèi)存缺頁(yè)？4，3，2，1，4，3，5，4，3，2，1，5443432132142143是是是是是是是543否543543否是243是213是215共缺頁(yè)中斷10次，缺頁(yè)中斷率為：10／12＝83.3％例5：一個(gè)分頁(yè)式存儲(chǔ)管理系統(tǒng)中，用戶虛擬空間共有32個(gè)頁(yè)面，每頁(yè)1KB，假定某時(shí)刻用戶的第0，1，2，3頁(yè)分別分配的物理塊號(hào)為10，8，4，17，求：（1）邏輯地址的有效位是多少？并給出邏輯地址的結(jié)構(gòu)。（2）將邏輯地址（2500）D轉(zhuǎn)換為物理地址。答：1）邏輯地址的有效位數(shù)是15位。

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

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

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

例6：針對(duì)某盤面的磁盤服務(wù)請(qǐng)求順序如下:55,58,39,18,90,160,150,38,184號(hào)磁道(當(dāng)前磁頭在100號(hào)磁道上且向增加方向移動(dòng)).分析按先來先服務(wù)、最短尋道時(shí)間優(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滿足請(qǐng)求的次序是150，160，184，90，58，55，39，38，18

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

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

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

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

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

FATA的FCB

112325文件名：A首塊號(hào)：11............

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

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

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