操作系統(tǒng)計(jì)算題綜合

操作系統(tǒng)計(jì)算題綜合第1頁(yè)/共48頁(yè)一、先來(lái)先服務(wù)（FCFS）調(diào)度算法例1：作業(yè)名到達(dá)時(shí)間服務(wù)時(shí)間

A0 1B1100C

21D3

100調(diào)度次序：ABCD→→→第2頁(yè)/共48頁(yè)作業(yè)名到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始執(zhí)行時(shí)間完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間A01B1100C21D3100周轉(zhuǎn)時(shí)間服務(wù)時(shí)間完成時(shí)間-到達(dá)時(shí)間開(kāi)始時(shí)間+服務(wù)時(shí)間上一個(gè)進(jìn)程的完成時(shí)間01111 101 1001101 102100100102 2021991.99第3頁(yè)/共48頁(yè)一、先來(lái)先服務(wù)（FCFS）調(diào)度算法例2：下面三個(gè)作業(yè)幾乎同時(shí)到達(dá)系統(tǒng)并立即進(jìn)行FCFS調(diào)度：作業(yè)名所需CPU時(shí)間作業(yè)128

作業(yè)29

作業(yè)33假設(shè)提交順序?yàn)?、2、3，則平均作業(yè)周轉(zhuǎn)時(shí)間T=若提交順序改為作業(yè)2、1、3，則T=若提交順序改為作業(yè)3、2、1，則T=FCFS調(diào)度算法的平均作業(yè)周轉(zhuǎn)時(shí)間與作業(yè)提交的順序有關(guān)。(28+37+40)/3=352918第4頁(yè)/共48頁(yè)作業(yè)到達(dá)時(shí)間服務(wù)時(shí)間開(kāi)始時(shí)間結(jié)束時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間周轉(zhuǎn)時(shí)間＝結(jié)束-到達(dá)帶權(quán)周轉(zhuǎn)時(shí)間＝周轉(zhuǎn)/服務(wù)

執(zhí)行順序：SJF/SPF__非搶占式舉例A033103ABCDE24686452B3971.1791131.51115112.751520142.8ECD7.61.84第5頁(yè)/共48頁(yè)進(jìn)程名ABCDE平均到達(dá)時(shí)間01234服務(wù)時(shí)間43524FCFS完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間SJF完成時(shí)間周轉(zhuǎn)時(shí)間帶權(quán)周轉(zhuǎn)時(shí)間471214184610111491225.53.52.84918613481639812.673.21.52.252.1FCFS：A→B→C→D→ESJF:A→D→B→E→CFCFS和的SJF比較第6頁(yè)/共48頁(yè)課堂練習(xí)練習(xí)：有如下四個(gè)進(jìn)程，它們的到達(dá)時(shí)間和服務(wù)時(shí)間如下所示，請(qǐng)分別計(jì)算在采用FCFS、SPF非搶占調(diào)度算法時(shí)的平均周轉(zhuǎn)時(shí)間和平均等待時(shí)間。

進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間

P1 0 7 P2 2 4 P3 4 1 P4 5 4第7頁(yè)/共48頁(yè)

進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間

P1 0 7

P2 2 4

P3 4 1

P4 5 4FCFSP142110P257P41612P3平均周轉(zhuǎn)時(shí)間=((7-0)+(11-2)+(12-4)+(16-5))/4=8.75平均等待時(shí)間=(0+(7-2)+(11-4)+(12-5))/4=4.75課堂練習(xí)第8頁(yè)/共48頁(yè)課堂練習(xí)

進(jìn)程 到達(dá)時(shí)間 服務(wù)時(shí)間

P1 0 7 P2 2 4 P3 4 1 P4 5 4SPF73160812P1P3P2P4平均周轉(zhuǎn)時(shí)間=((7-0)+(12-2)+(8-4)+(16-5))/4=8平均等待時(shí)間=((0-0)+(8-2)+(7-4)+(12-5))/4=4第9頁(yè)/共48頁(yè)FCFS非搶占SPF吞吐量0-7ms11平均周轉(zhuǎn)時(shí)間8.758平均等待時(shí)間4.754SPF與FCFS的比較第10頁(yè)/共48頁(yè)三、時(shí)間片輪轉(zhuǎn)調(diào)度算法—例(1)EG： 進(jìn)程

到達(dá)時(shí)間

服務(wù)時(shí)間

P1 0 7

P2 2 4

P3 4 1

P4 5 4RR（時(shí)間片為4）P1P2045678

910111213141516P1P3P4平均周轉(zhuǎn)時(shí)間

=((16-0)+(8-2)+(9-4)+(13-5))/4 =8.75平均等待時(shí)間=(9+2+4+4)/4=4.75第11頁(yè)/共48頁(yè)非搶占式優(yōu)先權(quán)算法—例1EG1： 進(jìn)程

到達(dá)時(shí)間

服務(wù)時(shí)間

優(yōu)先數(shù)

P1 0 73 P2 2 42 P3 414 P4 541Gantt圖平均周轉(zhuǎn)時(shí)間

=((7-0)+(15-2)+(16-4)+(11-5))/4=9.5平均等待時(shí)間=(0+9+11+2)/4=5.5P1P202457111516P4P3優(yōu)先數(shù)越小優(yōu)先級(jí)越高第12頁(yè)/共48頁(yè)搶占式優(yōu)先權(quán)算法—例2EG2： 進(jìn)程

到達(dá)時(shí)間

服務(wù)時(shí)間

優(yōu)先數(shù)

P1 0 73 P2 2 42 P3 4 14 P4 5 41Gantt圖平均周轉(zhuǎn)時(shí)間

=((15-0)+(10-2)+(16-4)+(9-5))/4=9.75平均等待時(shí)間=(8+4+11+0)/4=5.75P1P202459101516P4P3P2P1第13頁(yè)/共48頁(yè)各種算法結(jié)果值的比較FCFSSJFRR-4優(yōu)先權(quán)-非搶占式優(yōu)先權(quán)-搶占式平均周轉(zhuǎn)時(shí)間8.7588.759.59.75平均等待時(shí)間4.7544.755.55.75返回第14頁(yè)/共48頁(yè)五、高響應(yīng)比優(yōu)先權(quán)調(diào)度算法HRP優(yōu)先權(quán)的變化為

為響應(yīng)比。如等待時(shí)間相同,則要求服務(wù)時(shí)間愈短,其優(yōu)先權(quán)愈高--SPF.如要求服務(wù)時(shí)間相同,優(yōu)先權(quán)決定于等待時(shí)間----FCFS。對(duì)長(zhǎng)作業(yè),若等待時(shí)間足夠長(zhǎng)，優(yōu)先權(quán)也高，也能獲得CPU。第15頁(yè)/共48頁(yè)算法HRP示例

HRP的調(diào)度性能作業(yè)到達(dá)時(shí)間Tin服務(wù)時(shí)間Tr開(kāi)始時(shí)間Ts結(jié)束時(shí)間Tc

=2.14039151339132015TA=3TB=7TC=9TD=14TE=7=8.008364522046ABCDE→→→→WE=3.50WA=1WB=1.17WC=2.25WD=2.80ECDAB周轉(zhuǎn)時(shí)間T=結(jié)束時(shí)間Tc-到達(dá)時(shí)間Tin=3-0=3周轉(zhuǎn)時(shí)間T帶權(quán)周轉(zhuǎn)時(shí)間W=周轉(zhuǎn)時(shí)間T/服務(wù)時(shí)間Tr=3/3=1帶權(quán)周轉(zhuǎn)時(shí)間W平均=[(9-4)+4]/4=2.25=[(9-6)+5]/5=1.6=[(9-8)+2]/2=1.5RCRDRERD=[(13-6)+5]/5=2.4RE=[(13-8)+2]/2=3.5第16頁(yè)/共48頁(yè)五、高響應(yīng)比優(yōu)先權(quán)調(diào)度算法HRP不同調(diào)度算法對(duì)同一個(gè)作業(yè)/進(jìn)程的性能分析:作業(yè)到達(dá)時(shí)間Tin服務(wù)時(shí)間Tr從平均周轉(zhuǎn)時(shí)間及其平均帶權(quán)周轉(zhuǎn)時(shí)間來(lái)看，HRP剛好介于FCFS與SJP之間，即好于FCFS，次于SJP。

A03B26C44D65E82FCFS8.602.56SJF7.601.84HRP8.002.14返回第17頁(yè)/共48頁(yè)銀行家算法的例子假定系統(tǒng)中有5個(gè)進(jìn)程3類(lèi)資源及數(shù)量分別為10、5、7，T0時(shí)刻的資源分配情況。MaxAllocationNeedAvailableABCABCABCABCP0753010743332P1322200122P2902302600P3222211011P4433002431第18頁(yè)/共48頁(yè)WorkABCNeedABCAllocationABCWork+AllocationABCFinishP1332122200532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057true（1）T0時(shí)刻的安全性T0時(shí)刻存在著一個(gè)安全序列{P1P3P4P2P0}，故系統(tǒng)是安全的。銀行家算法的例子第19頁(yè)/共48頁(yè)(2)P1請(qǐng)求資源Request1(1,0,2)執(zhí)行銀行家算法銀行家算法的例子P1請(qǐng)求資源時(shí)的資源分配表MaxAllocationNeedAvailableABCABCABCABCP0753010743332(230)P1322200122(302)(020)P2902302600P3222211011P4433002431第20頁(yè)/共48頁(yè)WorkABCNeedABCAllocationABCWork+AllocationABCFinishP1230020302532trueP3532011211743trueP4743431002745trueP27456003021047trueP010477430101057trueP1請(qǐng)求資源時(shí)的安全性檢查表存在著一個(gè)安全序列{P1P3P4P2P0}，故系統(tǒng)是安全的，可以立即將P1所申請(qǐng)的資源分配給它。銀行家算法的例子第21頁(yè)/共48頁(yè)（3）P4請(qǐng)求資源Request4(3,3,0)P4發(fā)出請(qǐng)求向量Request4(3,3,0)，系統(tǒng)按銀行家算法進(jìn)行檢查:1)Request4(3,3,0)≤Need4(4,3,1)2)Request4(3,3,0)>Available(2,3,0),表示資源不夠,則讓P4等待銀行家算法的例子第22頁(yè)/共48頁(yè)(4)P0請(qǐng)求資源Request0(0,2,0)銀行家算法的例子MaxAllocationNeedAvailableABCABCABCABCP0753010743332[030][723](230)[210]P1322200122(302)(020)P2902302600P3222211011P4433002431P0請(qǐng)求資源時(shí)的資源分配表Available＝(2,1,0)不能滿(mǎn)足任何進(jìn)程需要，所以系統(tǒng)進(jìn)入不安全狀態(tài)，P0的請(qǐng)求不能分配返回目錄第23頁(yè)/共48頁(yè)三、地址結(jié)構(gòu)例題例：設(shè)有一頁(yè)式存儲(chǔ)管理系統(tǒng)，向用戶(hù)提供的邏輯地址空間最大為16頁(yè)，每頁(yè)2048B，內(nèi)存總共有8個(gè)存儲(chǔ)塊，試問(wèn)邏輯地址至少應(yīng)為多少位？?jī)?nèi)存空間有多大？解：（1）頁(yè)式存儲(chǔ)管理系統(tǒng)的邏輯地址為：其中頁(yè)內(nèi)地址表每頁(yè)的大小即2048B=2*1024B=211B，所以頁(yè)內(nèi)地址為11位；頁(yè)號(hào)表最多允許的頁(yè)數(shù)即16頁(yè)=24頁(yè)，所以頁(yè)號(hào)為4位。故邏輯地址至少應(yīng)為15位。（2）物理地址為：其中塊內(nèi)地址表每塊的大小與頁(yè)大小相等，所以塊內(nèi)地址也為11位；其中塊號(hào)表內(nèi)存空間最多允許的塊數(shù)即8塊=23塊，所以塊號(hào)為3位。故內(nèi)存空間至少應(yīng)為14位，即214=16KB。頁(yè)號(hào)p位移量w返回塊號(hào)b塊內(nèi)偏移d第24頁(yè)/共48頁(yè)四、地址變換例題1例1：若在一分頁(yè)存儲(chǔ)管理系統(tǒng)中，某作業(yè)的頁(yè)表如下表所示，已知頁(yè)面大小為1024B，試將邏輯地址1011，2148，5012轉(zhuǎn)化為相應(yīng)的物理地址？畫(huà)出其地址轉(zhuǎn)換圖。頁(yè)號(hào)塊號(hào)02132136第25頁(yè)/共48頁(yè)四、地址變換例題解：由題知邏輯地址為：物理地址為：（1）邏輯地址1011（十進(jìn)制）的二進(jìn)制表示為：

001111110011，由此可知邏輯地址1011的頁(yè)號(hào)0，查頁(yè)表知該頁(yè)放在第2物理塊中；其物理地址的二進(jìn)制表示為：0101111110011，所以邏輯地址1011對(duì)應(yīng)的物理地址為0BF3H。其地址轉(zhuǎn)換圖如后所示。頁(yè)號(hào)2位位移量w10位塊號(hào)b3位塊內(nèi)位移d10位第26頁(yè)/共48頁(yè)四、地址變換例題1（2）邏輯地址2148（十進(jìn)制）的二進(jìn)制為：

100001100100，由此可知邏輯地址2148的頁(yè)號(hào)是2，查頁(yè)表知該頁(yè)放入物理塊1中；其物理地址的二進(jìn)制是：0010001100100，所以邏輯地址2148對(duì)應(yīng)的物理地址是0464H。（3）邏輯地址5012（十進(jìn)制）的二進(jìn)制表示為：

1001110010100，可知該邏輯地址的頁(yè)號(hào)為4，查頁(yè)表知該頁(yè)為不合法頁(yè)，則產(chǎn)生越界中斷。第27頁(yè)/共48頁(yè)地址變換過(guò)程+<頁(yè)表長(zhǎng)度頁(yè)表始址3F30頁(yè)表寄存器邏輯地址1011（03F3H）物理地址0BF3H越界中斷頁(yè)合法頁(yè)號(hào)塊號(hào)0213213623F3四、地址變換例題1第28頁(yè)/共48頁(yè)例1、在一個(gè)段式存儲(chǔ)管理系統(tǒng)中，其段表為：段號(hào)內(nèi)存起始地址段長(zhǎng)

02105001235020210090313505904193895試求右表中邏輯地址對(duì)應(yīng)的物理地址是什么？解：邏輯地址為：邏輯地址對(duì)應(yīng)的物理地址為：210+430=640。邏輯地址因?yàn)槎蝺?nèi)地址120>段長(zhǎng)90，所為該段為非法段。段號(hào)段內(nèi)地址0430212004302120分段地址變換例題1由段表可知段號(hào)為3位，段內(nèi)地址為10位。第29頁(yè)/共48頁(yè)分段地址變換例題2例2、某段表的內(nèi)容如下：段號(hào)段首址段長(zhǎng)度

0120K40K1760K30K2480K20K3370K20K對(duì)于邏輯地址2154，它對(duì)應(yīng)的物理地址為多少？解：邏輯地址為：由段表可知段號(hào)為2位，段內(nèi)地址為16位，段允許的最大長(zhǎng)度為216=210*26=1024*64=65536。所以邏輯地址2154（二進(jìn)制為100001101010）的段號(hào)為0，查段表知其對(duì)應(yīng)的物理地址為：120K+2154=125034段號(hào)段內(nèi)地址第30頁(yè)/共48頁(yè)地址變換例題

某虛擬存儲(chǔ)器的用戶(hù)空間共有32個(gè)頁(yè)面，每頁(yè)1KB，主存16KB。假定某時(shí)刻系統(tǒng)為用戶(hù)的第0、1、2、3頁(yè)分別分配的物理塊號(hào)為5、10、4、7，試將虛擬地址0A5C和093C變換為物理地址。解：虛擬地址為：頁(yè)號(hào)5位（25=32），頁(yè)內(nèi)位移10位（110=1024）；物理地址為：物理塊號(hào)4位（24=16），塊內(nèi)位移（110=1024）10位。虛擬地址0A5C對(duì)應(yīng)的二進(jìn)制為：000101001011100，即虛擬地址0A5C的頁(yè)號(hào)為2，頁(yè)內(nèi)位移為1001011100，由題意知對(duì)應(yīng)的物理地址為：01001001011100即125C。同理求093C的物理地址為293C。略第31頁(yè)/共48頁(yè)最佳置換算法(Optimal,OPT)例

假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，進(jìn)程運(yùn)行時(shí)的頁(yè)面走向?yàn)?,2,3,4,1,2,5,1,2,3,4,5，開(kāi)始時(shí)3個(gè)物理塊均為空，計(jì)算采用最佳置換頁(yè)面淘汰算法時(shí)的缺頁(yè)率？返回注：實(shí)際上這種算法無(wú)法實(shí)現(xiàn)，因頁(yè)面訪問(wèn)的未來(lái)順序很難精確預(yù)測(cè)，但可用該算法評(píng)價(jià)其它算法的優(yōu)劣。頁(yè)面走向123412512345物理塊1物理塊2物理塊3缺頁(yè)1缺缺缺缺缺缺缺12312121212121212333444442555555(7/12)第32頁(yè)/共48頁(yè)先進(jìn)先出置換算法(FIFO)例題1、假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，進(jìn)程運(yùn)行時(shí)的頁(yè)面走向?yàn)?,2,3,4,1,2,5,1,2,3,4,5，開(kāi)始時(shí)3個(gè)物理塊均為空，計(jì)算采用先進(jìn)先出頁(yè)面淘汰算法時(shí)的缺頁(yè)率？頁(yè)面走向123412512345物理塊1111444555555物理塊222211111333物理塊33332222244缺頁(yè)缺缺缺缺缺缺缺缺缺(9/12)第33頁(yè)/共48頁(yè)先進(jìn)先出置換算法例題2、假定系統(tǒng)為某進(jìn)程分配了4個(gè)物理塊，進(jìn)程運(yùn)行時(shí)的頁(yè)面走向?yàn)?,2,3,4,1,2,5,1,2,3,4,5，開(kāi)始時(shí)4個(gè)物理塊均為空，計(jì)算采用先進(jìn)先出頁(yè)面淘汰算法時(shí)的缺頁(yè)率？頁(yè)面走向123412512345物理塊1111111555544物理塊222222211115物理塊33333332222物理塊4444444333缺頁(yè)缺缺缺缺缺缺缺缺缺缺(10/12)第34頁(yè)/共48頁(yè)先進(jìn)先出置換算法例題3、假定系統(tǒng)為某進(jìn)程分配了5個(gè)物理塊，進(jìn)程運(yùn)行時(shí)的頁(yè)面走向?yàn)?,2,3,4,1,2,5,1,2,3,4,5，開(kāi)始時(shí)3個(gè)物理塊均為空，計(jì)算采用先進(jìn)先出頁(yè)面淘汰算法時(shí)的缺頁(yè)率？頁(yè)面走向123412512345物理塊1111111111111物理塊222222222222物理塊33333333333物理塊4444444444物理塊5555555缺頁(yè)缺缺缺缺缺(5/12)第35頁(yè)/共48頁(yè)先進(jìn)先出置換算法_注1：1、該算法的出發(fā)點(diǎn)是最早調(diào)入內(nèi)存的頁(yè)面，其不再被訪問(wèn)的可能性會(huì)大一些。2、FIFO算法易于理解與編程，但它的效率不高。被置換的頁(yè)可能存有一個(gè)初始化程序段，很早前用過(guò)后再也不會(huì)用到；但也可能存有一組經(jīng)常訪問(wèn)的全局變量，初始化時(shí)被調(diào)入內(nèi)存，在整個(gè)程序運(yùn)行過(guò)程中都將會(huì)用到。頁(yè)面走向123412512345物理塊1111444555555物理塊222211111333物理塊33332222244缺頁(yè)缺缺缺缺缺缺缺缺缺第36頁(yè)/共48頁(yè)先進(jìn)先出置換算法_注2：3、先進(jìn)先出算法存在一種異?，F(xiàn)象，即在某些情況下會(huì)出現(xiàn)分配給進(jìn)程的物理塊數(shù)增多，缺頁(yè)次數(shù)有時(shí)增加，有時(shí)減少的奇怪現(xiàn)象，這種現(xiàn)象稱(chēng)為Belady現(xiàn)象。如前述幾例：物理塊數(shù)345缺頁(yè)次數(shù)9105返回“Belady異?！迸c其說(shuō)是一種奇怪現(xiàn)象，不如說(shuō)是一個(gè)重要提示。它對(duì)學(xué)習(xí)操作系統(tǒng)來(lái)說(shuō)的實(shí)際意義是起警示作用：即操作系統(tǒng)是一個(gè)復(fù)雜的機(jī)構(gòu)，直觀的感覺(jué)是靠不住的。第37頁(yè)/共48頁(yè)最近最久未使用算法例例：假定系統(tǒng)為某進(jìn)程分配了3個(gè)物理塊，進(jìn)程運(yùn)行時(shí)的頁(yè)面走向?yàn)?,2,3,4,1,2,5,1,2,3,4,5，開(kāi)始時(shí)3個(gè)物理塊均為空，計(jì)算采用最近最久未使用頁(yè)面淘汰算法時(shí)的缺頁(yè)率？頁(yè)面走向123412512345物理塊1111444555333物理塊222211111144物理塊33332222225缺頁(yè)缺缺缺缺缺缺缺缺缺缺(10/12)第38頁(yè)/共48頁(yè)2、磁盤(pán)調(diào)度算法磁盤(pán)調(diào)度算法早期的磁盤(pán)調(diào)度算法先來(lái)先服務(wù)FCFS最短尋道時(shí)間優(yōu)先SSTF掃描算法掃描(SCAN)/電梯(LOOK)算法循環(huán)掃描(CSCAN)算法返回例：假設(shè)一個(gè)請(qǐng)求序列：98、183、37、122、14、124、65、67，磁頭當(dāng)前的位置在53。第39頁(yè)/共48頁(yè)FCFS先來(lái)先服務(wù)按進(jìn)程請(qǐng)求訪問(wèn)磁盤(pán)的先后次序進(jìn)行調(diào)度下磁道移道數(shù)9845183853714612285141081241106559672總道數(shù)640平均80第40頁(yè)/共48頁(yè)最短尋道時(shí)間優(yōu)先（SSTF）選擇從當(dāng)前磁頭位置所需尋道時(shí)間最短的請(qǐng)求。下磁道移道數(shù)651267237301423988412224124218359總道數(shù)236平均29.5第41頁(yè)/共48頁(yè)掃描算法（SCAN）假定：磁頭向磁道號(hào)增加的方向移動(dòng)。下磁道移道數(shù)651267298311222412421835919916371621423總道數(shù)331平均41.4第42頁(yè)/共48頁(yè)假定：磁頭向磁道號(hào)增加的方向移動(dòng)。下磁道移道數(shù)6512672983112224124218359371461423總道數(shù)299平均37.4Look算法（電梯算法）第43頁(yè)/共48頁(yè)循環(huán)掃描算法（CSCAN）特點(diǎn)：消除了對(duì)兩端磁道請(qǐng)求的不公平。下磁道移道數(shù)6512672983112224124218359141693723總道數(shù)322平均40.3返回第44頁(yè)/共48頁(yè)練習(xí)題1例1：設(shè)某系統(tǒng)的磁盤(pán)有500塊，塊號(hào)為：0，1，2，3，…，499。（1）若用位示圖法