操作系統(tǒng)大題

在銀專家算法中，若出現(xiàn)下述資源分派情：ProcessAllocationNeedAvailableP0003200121622P110001750P213542356P033206523P400140656試問：⑴該狀態(tài)能否安全？⑵若進度P2提出懇求Request(1，2，2，2)后，系統(tǒng)可否將資源分派給它？⑴該狀態(tài)是安全的，因為存在一個安全序列<P0P3P4P1P2>。下表為該時刻的安全序列表。資源情WorkNeedAllocatiWork+AllocatioFinis況onnh進度P01622001200321654trueP31654065203331987trueP419870656001419911trueP1199111750100029911trueP229911235613543121417true⑵若進度P2提出懇求Request(1，2，2，2)后，系統(tǒng)不可以將資源分派給它，若分派給進度P2，系統(tǒng)還剩的資源狀況為（0，4，0，0），此時系統(tǒng)中的資源將沒法知足任何一個進度的資源懇求，進而致使系統(tǒng)進入不安全狀態(tài)，簡單惹起死鎖的發(fā)生。第三章相關(guān)作業(yè)和進度調(diào)動算法的習題有一個擁有兩道作業(yè)的批辦理系統(tǒng)，作業(yè)調(diào)動采納短作業(yè)優(yōu)先的調(diào)動算法，進度調(diào)動采納搶占式的優(yōu)先級調(diào)動算法，在下表的作業(yè)序列，作業(yè)優(yōu)先數(shù)即為進度優(yōu)先數(shù)，優(yōu)先數(shù)越小優(yōu)先級越高。1）列出所有作業(yè)進入內(nèi)存時間及結(jié)束時間。2）計算這批作業(yè)的均勻周轉(zhuǎn)時間及均勻帶權(quán)周轉(zhuǎn)時間。解：作業(yè)履行過程以下：8:00A抵達，內(nèi)存空，A進入內(nèi)存，無競爭開始運轉(zhuǎn)；8:20B抵達，進入內(nèi)存，優(yōu)先數(shù)為2，因為A的優(yōu)先數(shù)為4，對比B優(yōu)先級低，被剝奪辦理器，B開始運轉(zhuǎn)；8:30A抵達，內(nèi)存滿，不行進入內(nèi)存；8:50B運轉(zhuǎn)結(jié)束，同時D抵達，同C搶奪內(nèi)存，因為D運轉(zhuǎn)時間短，依據(jù)短作業(yè)優(yōu)先的調(diào)動算法，D被調(diào)入內(nèi)存；D與A的優(yōu)先數(shù)對比，A的優(yōu)先級別高，獲取辦理器持續(xù)運轉(zhuǎn)；9:10

A運轉(zhuǎn)結(jié)束，C進入內(nèi)存，C的優(yōu)先級別高于

D，C開始運行；

10:00

C運轉(zhuǎn)結(jié)束，

D開始運轉(zhuǎn)；

10:20

D運轉(zhuǎn)結(jié)束。1）所有作業(yè)進入內(nèi)存時間及結(jié)束時間以下表所示：2）作業(yè)周轉(zhuǎn)時間=作業(yè)結(jié)束時間-作業(yè)抵達時間這批作業(yè)的均勻周轉(zhuǎn)時間=(70+30+90+90)/4=70分鐘這批作業(yè)的均勻帶權(quán)周轉(zhuǎn)時間=(7/4+1+9/5+9/2)/4=2.有一個四道作業(yè)的操作系統(tǒng)，若在一段時間內(nèi)先后抵達6個作業(yè)，它們的提交和預計運轉(zhuǎn)時間由下表給出：采納短作業(yè)優(yōu)先調(diào)動算法，作業(yè)被調(diào)入系統(tǒng)后半途不會退出，但作業(yè)運轉(zhuǎn)時可被更短作業(yè)搶占。（1）分別給出6個作業(yè)的開始履行時間、作業(yè)達成時間、作業(yè)周轉(zhuǎn)時間。（2）計算這批作業(yè)的平均周轉(zhuǎn)時間。解答：作業(yè)履行過程以下：8:00行；

J18:20

抵達，內(nèi)存空，無競爭,進入內(nèi)存開始運J1運轉(zhuǎn)20分鐘，節(jié)余40分鐘；J2

抵達，運轉(zhuǎn)時間為

35分鐘，小于

J1，代替

J1開始運轉(zhuǎn)。

8:25

J1剩

40分鐘，J2

剩

30分鐘；J3抵達，運轉(zhuǎn)時間為20分鐘，小于J2，代替J2開始運轉(zhuǎn)。8:30J1剩40分鐘，J2剩30分鐘；J3剩15分鐘；J4抵達，運轉(zhuǎn)時間為25分鐘，大于J3，J3持續(xù)運轉(zhuǎn)。8:35J3剩10分鐘；J5抵達，運轉(zhuǎn)時間為5分鐘，只管時間最短，可是內(nèi)存中已有四道作業(yè)，所以，J5，不行進入內(nèi)存，J3持續(xù)運轉(zhuǎn)。8:40行。

J38:45

剩

5分鐘；J6抵達，同理不行進入內(nèi)存，J3持續(xù)運J3運轉(zhuǎn)結(jié)束；J5最短，進入內(nèi)存并開始履行。8:50J5開始履行。

運轉(zhuǎn)結(jié)束；J6進入內(nèi)存，運轉(zhuǎn)時間10分鐘，為最短，9:00J6運轉(zhuǎn)結(jié)束，J1剩40分鐘，J2剩30分鐘；J4剩25分鐘；J4最短，開始運轉(zhuǎn)。9:25J4運轉(zhuǎn)結(jié)束，J2最短，開始運轉(zhuǎn)。9:55J2運行結(jié)束，J1開始運轉(zhuǎn)。10:35J1運轉(zhuǎn)結(jié)束。1）所有作業(yè)的開始履行時間、作業(yè)達成時間、作業(yè)周轉(zhuǎn)時間，以下表所示：2）作業(yè)周轉(zhuǎn)時間=作業(yè)結(jié)束時間-作業(yè)抵達時間這批作業(yè)的均勻周轉(zhuǎn)時間=(155+95+20+55+15+20)/6=60分鐘這批作業(yè)的均勻帶權(quán)周轉(zhuǎn)時間=(155/60+195/35+1+11/5+3+2)/4=為何要進行頁面置換在懇求分頁儲存管理系統(tǒng)中，因為使用了虛構(gòu)儲存管理技術(shù)，使得所有的進度頁面不是一次性地所有調(diào)入內(nèi)存，而是部分頁面裝入。這就有可能出現(xiàn)下邊的狀況：要接見的頁面不在內(nèi)存，這時系統(tǒng)產(chǎn)生缺頁中止。操作系統(tǒng)在辦理缺頁中止時，要把所需頁面從外存調(diào)入到內(nèi)存中。假如這時內(nèi)存中有安閑塊，就能夠直接調(diào)入該頁面；如果這時內(nèi)存中沒有安閑塊，就一定先裁減一個已經(jīng)在內(nèi)存中的頁面，騰出空間，再把所需的頁面裝入，即進行頁面置換。有助于理解的重點詞有：懇求分頁、虛構(gòu)儲存、缺頁中止、頁面置換。常用的頁面置換算法教材中介紹的常用頁面置換算法有：先進先出法（FIFO）、最正確置換法（OPT）和近來最少使用置換法（LRU）。（1）先進先出法（FIFO）算法描繪：因為以為最早調(diào)入內(nèi)存的頁不再被使用的可能性要大于剛調(diào)入內(nèi)存的頁，所以，先進先出法老是裁減在內(nèi)存中逗留時間最長的一頁，即先進入內(nèi)存的頁，先被換出。先進先出法把一個進度所有在內(nèi)存中的頁按進入內(nèi)存的序次排隊，裁減頁面老是在隊首進行。假如一個頁面剛被放入內(nèi)存，就把它插在隊尾?！纠?】教材第4章課后習題?？紤]下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。當內(nèi)存塊數(shù)目分別為3，5時，試問先進先出置換算法（FIFO）的缺頁次數(shù)是多少？（注意，所有內(nèi)存塊最先都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁。）解：當內(nèi)存塊數(shù)目分別為3時，F(xiàn)IFO算法的履行過程以以下圖所示。頁面塊1塊2221112227771112塊333555111666333缺頁打叉的表示發(fā)生了缺頁，共缺頁16次。提示：當FIFO算法履行到藍色的4號頁面時，這時內(nèi)存中有三個頁面，分別是1，2，3。依據(jù)FIFO算法，在內(nèi)存中逗留時間最長的頁面被裁減。三個頁面在內(nèi)存中的逗留時間用綠色地區(qū)標志出來了，可見，1號頁面是逗留時間最長的，所以要裁減1號頁面。當內(nèi)存塊數(shù)目分別為5時，共缺頁10次。FIFO算法的履行過程以下。頁面塊11111666661塊2222211112塊333332223塊44444334塊5555575缺頁優(yōu)弊端：先進先出法（FIFO）簡單易于實現(xiàn)，可是性能不好，存在Belady現(xiàn)象。比如關(guān)于以下頁面：1，2，3，4，1，2，5，1，2，3，4，5，當內(nèi)存塊為3時，出現(xiàn)9次缺頁中止；當內(nèi)存塊為4時，出現(xiàn)10次缺頁中止。缺頁率跟著內(nèi)存塊增添而增添的現(xiàn)象，稱為Belady現(xiàn)象。有興趣的同學能夠試一試，看看能否是這樣的。（2）最正確置換法（OPT）算法描繪：最正確置換算法（OPT）在為調(diào)入新頁面而一定早先淘汰某個老頁面時，所選擇的老頁面應在未來不被使用，或許是在最遠的未來才被接見。采納這類算法，能保證有最小缺頁率?！纠?】教材第4章課后習題?？紤]下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。當內(nèi)存塊數(shù)目分別為3，5時，試問最正確置換法（OPT）的缺頁次數(shù)是多少？（注意，所有內(nèi)存塊最先都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁。）解：當內(nèi)存塊數(shù)目分別為3時，OPT算法的履行過程以以下圖所示。頁面塊1塊22222272222塊3456666113缺頁打叉的表示發(fā)生了缺頁，共缺頁11次。提示：當OPT算法履行到藍色的4號頁面時，這時內(nèi)存中有三個頁面，分別是1，2，3。依據(jù)OPT算法，在最遠的未來才被接見的頁面先裁減。這三個頁面在未來頁面走向序列的地點用綠色地區(qū)標志出來了，可見，3號頁面是最晚被接見到的，所以要裁減3號頁面。到了最后一個6號頁面時，因為沒有后續(xù)的頁面序列了，能夠隨機選擇一個頁面裁減。當內(nèi)存塊數(shù)目分別為5時，共缺頁7次。OPT算法的履行過程如下。頁面塊11111111塊2222222塊333333塊44664塊5575缺頁優(yōu)弊端：OPT算法因為要需要早先知道一個進度在整個運轉(zhuǎn)過程中頁面走向的所有狀況，所以不過一種理想狀態(tài)，實質(zhì)是行不通的。一般用算法來權(quán)衡（如經(jīng)過模擬實驗剖析或理論剖析）其余算法的好壞。（3）近來最少使用置換法（LRU）算法描繪：近來最少使用置換法（LRU）是選擇在近來一段時間里最久沒有使用過的頁面予以裁減。借鑒FIFO算法和OPT算法，以“近來的過去”作為“不久未來”的近似。【例3】教材第4章課后習題?？紤]下述頁面走向：1，2，3，4，2，1，5，6，2，1，2，3，7，6，3，2，1，2，3，6。當內(nèi)存塊數(shù)目分別為3，5時，試問近來最少使用置換法（LRU）的缺頁次數(shù)是多少？（注意，所有內(nèi)存塊最先都是空的，凡第一次用到的頁面都產(chǎn)生一次缺頁。）解：當內(nèi)存塊數(shù)目分別為3時，LRU算法的履行過程以以下圖所示。頁面塊1塊222226663333332塊33111222266113缺頁打叉的表示發(fā)生了缺頁，共缺頁15次。提示：當LRU算法履行到藍色的4號頁面時，這時內(nèi)存中有三個頁面，分別是1，2，3。依據(jù)LRU算法，在近來一段時間里最久沒有使用過的頁面予以裁減。這三個頁面在4號頁面以前的頁面走向序列中的地點用綠色地區(qū)標志出來了，可見，1號頁面是最久沒有被使用過的，所以要裁減1號頁面。當內(nèi)存塊數(shù)目分別為5時，共缺頁8次。LRU算法的履行過程如下。頁面塊111111111塊22222222塊3336663塊444334塊55575缺頁優(yōu)弊端：LRU算法是常常采納的頁面置換算法。弊端是實現(xiàn)上需要大批的硬件支持。需要注意的問題1）不要把儲存管理的頁面置換算法與辦理機調(diào)動算法混雜。有的同學可能會將FIFO和FCFS弄混，F(xiàn)IFO是先進先出頁面置換算法，F(xiàn)CFS是先來先服務的作業(yè)調(diào)換算法，固然道理相像，卻用在不一樣的地方。2）缺頁率。教材中提到了缺頁率，沒有給出它的觀點。缺頁率=缺頁次數(shù)/頁面總數(shù)。以上邊3個例題為例，缺頁率以下：算法FIFOOPTLRU內(nèi)存塊為316/20=80%11/20=55%15/20=75%內(nèi)存塊為510/20=50%7/20=35%8/20=40%影響缺頁率的要素有分派給進度的內(nèi)存塊數(shù)和頁面尺寸等。一般來說，內(nèi)存塊數(shù)多，頁面增大，使得發(fā)生缺頁的可能性降落?？墒沁@不是絕對的，還存在著Belady現(xiàn)象。3）權(quán)衡頁面置換算法利害的標準是：好的算法能適合減少缺頁率，防止系統(tǒng)“顫動”。說明：以上內(nèi)容僅作為教課指導資料，不作為查核內(nèi)容。設(shè)正在辦理器上履行的一個進度的頁表以下表所示，表中的虛頁號和物理塊號是十進制數(shù)，開端頁號（塊號）均為0。所有的地點均是儲存器字節(jié)地點。頁的大小為1024字節(jié)。（7分）①詳述在設(shè)有快表的懇求分頁儲存管理系統(tǒng)中，一個虛地點變換成物理內(nèi)存地點的過程。②以下虛地點對應于什么物理地點：5499，2221。進度的頁表虛頁號狀態(tài)