|
進(jìn)程運(yùn)行時(shí)，若其訪問的頁(yè)面不在內(nèi)存而需將其調(diào)入，但內(nèi)存已無空閑空間時(shí)，就需要從內(nèi)存中調(diào)出一頁(yè)程序或數(shù)據(jù)，送入磁盤的對(duì)換區(qū)。 選擇調(diào)出頁(yè)面的算法就稱為頁(yè)面置換算法。好的頁(yè)面置換算法應(yīng)有較低的頁(yè)面更換頻率，也就是說，應(yīng)將以后不會(huì)再訪問或者以后較長(zhǎng)時(shí)間內(nèi)不會(huì)再訪問的頁(yè)面先調(diào)出。 常見的置換算法有以下四種。 1. 最佳置換算法(OPT)最佳(Optimal, OPT)置換算法所選擇的被淘汰頁(yè)面將是以后永不使用的，或者是在最長(zhǎng)時(shí)間內(nèi)不再被訪問的頁(yè)面,這樣可以保證獲得最低的缺頁(yè)率。但由于人們目前無法預(yù)知進(jìn)程在內(nèi)存下的若千頁(yè)面中哪個(gè)是未來最長(zhǎng)時(shí)間內(nèi)不再被訪問的，因而該算法無法實(shí)現(xiàn)。最佳置換算法可以用來評(píng)價(jià)其他算法。假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下頁(yè)面號(hào)引用串： 7, 0, 1, 2, 0, 3, 0, 4, 2, 3, 0, 3, 2, 1, 2, 0, 1, 7, 0, 1 進(jìn)程運(yùn)行時(shí)，先將7, 0, 1三個(gè)頁(yè)面依次裝入內(nèi)存。進(jìn)程要訪問頁(yè)面2時(shí)，產(chǎn)生缺頁(yè)中斷，根據(jù)最佳置換算法，選擇第18次訪問才需調(diào)入的頁(yè)面7予以淘汰。然后，訪問頁(yè)面0時(shí)，因?yàn)橐言趦?nèi)存中所以不必產(chǎn)生缺頁(yè)中斷。訪問頁(yè)面3時(shí)又會(huì)根據(jù)最佳置換算法將頁(yè)面1淘汰……依此類推，如圖3-26所示。從圖中可以看出釆用最佳置換算法時(shí)的情況。 可以看到，發(fā)生缺頁(yè)中斷的次數(shù)為9，頁(yè)面置換的次數(shù)為6。
圖3-26 利用最佳置換算法時(shí)的置換圖
2. 先進(jìn)先出(FIFO)頁(yè)面置換算法優(yōu)先淘汰最早進(jìn)入內(nèi)存的頁(yè)面，亦即在內(nèi)存中駐留時(shí)間最久的頁(yè)面。該算法實(shí)現(xiàn)簡(jiǎn)單，只需把調(diào)入內(nèi)存的頁(yè)面根據(jù)先后次序鏈接成隊(duì)列，設(shè)置一個(gè)指針總指向最早的頁(yè)面。但該算法與進(jìn)程實(shí)際運(yùn)行時(shí)的規(guī)律不適應(yīng)，因?yàn)樵谶M(jìn)程中，有的頁(yè)面經(jīng)常被訪問。
圖3-27 利用FIFO置換算法時(shí)的置換圖 這里仍用上面的實(shí)例，釆用FIFO算法進(jìn)行頁(yè)面置換。進(jìn)程訪問頁(yè)面2時(shí)，把最早進(jìn)入內(nèi)存的頁(yè)面7換出。然后訪問頁(yè)面3時(shí)，再把2, 0, 1中最先進(jìn)入內(nèi)存的頁(yè)換出。由圖 3-27可以看出，利用FIFO算法時(shí)進(jìn)行了 12次頁(yè)面置換，比最佳置換算法正好多一倍。 FIFO算法還會(huì)產(chǎn)生當(dāng)所分配的物理塊數(shù)增大而頁(yè)故障數(shù)不減反增的異常現(xiàn)象，這是由 Belady于1969年發(fā)現(xiàn)，故稱為Belady異常，如圖3-28所示。只有FIFO算法可能出現(xiàn)Belady 異常，而LRU和OPT算法永遠(yuǎn)不會(huì)出現(xiàn)Belady異常。
圖 3-28 Belady 異常
3. 最近最久未使用(LRU)置換算法選擇最近最長(zhǎng)時(shí)間未訪問過的頁(yè)面予以淘汰，它認(rèn)為過去一段時(shí)間內(nèi)未訪問過的頁(yè)面，在最近的將來可能也不會(huì)被訪問。該算法為每個(gè)頁(yè)面設(shè)置一個(gè)訪問字段，來記錄頁(yè)面自上次被訪問以來所經(jīng)歷的時(shí)間，淘汰頁(yè)面時(shí)選擇現(xiàn)有頁(yè)面中值最大的予以淘汰。再對(duì)上面的實(shí)例釆用LRU算法進(jìn)行頁(yè)面置換，如圖3-29所示。進(jìn)程第一次對(duì)頁(yè)面2訪問時(shí)，將最近最久未被訪問的頁(yè)面7置換出去。然后訪問頁(yè)面3時(shí)，將最近最久未使用的頁(yè)面1換出。
圖3-29 LRU頁(yè)面置換算法時(shí)的置換圖 在圖3-29中，前5次置換的情況與最佳置換算法相同，但兩種算法并無必然聯(lián)系。實(shí)際上，LRU算法根據(jù)各頁(yè)以前的情況，是“向前看”的，而最佳置換算法則根據(jù)各頁(yè)以后的使用情況，是“向后看”的。 LRU性能較好，但需要寄存器和棧的硬件支持。LRU是堆棧類的算法。理論上可以證明，堆棧類算法不可能出現(xiàn)Belady異常。FIFO算法基于隊(duì)列實(shí)現(xiàn)，不是堆棧類算法。 4. 時(shí)鐘(CLOCK)置換算法LRU算法的性能接近于OPT,但是實(shí)現(xiàn)起來比較困難，且開銷大；FIFO算法實(shí)現(xiàn)簡(jiǎn)單，但性能差。所以操作系統(tǒng)的設(shè)計(jì)者嘗試了很多算法，試圖用比較小的開銷接近LRU的性能，這類算法都是CLOCK算法的變體。簡(jiǎn)單的CLOCK算法是給每一幀關(guān)聯(lián)一個(gè)附加位，稱為使用位。當(dāng)某一頁(yè)首次裝入主存時(shí)，該幀的使用位設(shè)置為1;當(dāng)該頁(yè)隨后再被訪問到時(shí)，它的使用位也被置為1。對(duì)于頁(yè)替換算法，用于替換的候選幀集合看做一個(gè)循環(huán)緩沖區(qū)，并且有一個(gè)指針與之相關(guān)聯(lián)。當(dāng)某一頁(yè)被替換時(shí)，該指針被設(shè)置成指向緩沖區(qū)中的下一幀。當(dāng)需要替換一頁(yè)時(shí)，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一幀。每當(dāng)遇到一個(gè)使用位為1的幀時(shí)，操作系統(tǒng)就將該位重新置為0；如果在這個(gè)過程開始時(shí)，緩沖區(qū)中所有幀的使用位均為0，則選擇遇到的第一個(gè)幀替換；如果所有幀的使用位均為1,則指針在緩沖區(qū)中完整地循環(huán)一周，把所有使用位都置為0，并且停留在最初的位置上，替換該幀中的頁(yè)。由于該算法循環(huán)地檢查各頁(yè)面的情況，故稱為CLOCK算法，又稱為最近未用(Not Recently Used, NRU)算法。 CLOCK算法的性能比較接近LRU，而通過增加使用的位數(shù)目，可以使得CLOCK算法更加高效。在使用位的基礎(chǔ)上再增加一個(gè)修改位，則得到改進(jìn)型的CLOCK置換算法。這樣，每一幀都處于以下四種情況之一：
算法執(zhí)行如下操作步驟：
改進(jìn)型的CLOCK算法優(yōu)于簡(jiǎn)單CLOCK算法之處在于替換時(shí)首選沒有變化的頁(yè)。由于修改過的頁(yè)在被替換之前必須寫回，因而這樣做會(huì)節(jié)省時(shí)間。 |
|
|
