頁(yè)面淘汰算法

頁(yè)面淘汰算法2頁(yè)面置換算法的介紹關(guān)于頁(yè)面置換算法的一些基本概念及思想目錄1關(guān)于頁(yè)面置換算法的一些基本概念及思想01part網(wǎng)絡(luò)存儲(chǔ)與討論

頁(yè)面置換算法主要是記錄內(nèi)存的忙閑狀態(tài)。為進(jìn)程分配和釋放內(nèi)存。當(dāng)主存的空間太小而無(wú)法裝入所有的進(jìn)程時(shí)．就需要在內(nèi)存和硬盤之間進(jìn)行調(diào)度操作。多數(shù)操作系統(tǒng)只采用某種特定的頁(yè)面置換算法進(jìn)行置換．無(wú)法預(yù)先探測(cè)當(dāng)前運(yùn)行進(jìn)程的頁(yè)面訪問(wèn)模式。因此不能根據(jù)不同的頁(yè)面訪問(wèn)模式，選用不同的頁(yè)面置換算法。當(dāng)然，如果能對(duì)不同的訪問(wèn)模式選取相應(yīng)的頁(yè)面置換算法。將提高操作系統(tǒng)的調(diào)度能力。進(jìn)而提高整個(gè)系統(tǒng)的性能。 在進(jìn)程中運(yùn)行過(guò)程中，若所要訪問(wèn)的頁(yè)面不在內(nèi)存中，需要調(diào)入頁(yè)面時(shí)，選擇內(nèi)存中的那個(gè)物理頁(yè)面將其調(diào)出。通常只能再局部性原理指導(dǎo)下，把未來(lái)不再使用的頁(yè)面調(diào)出。如何選擇調(diào)度策略即頁(yè)面置換算法至關(guān)重要，置換算法的好壞，直接影響著系統(tǒng)的性能，因此有必要將常見(jiàn)的FIFO、LRU、OPT三種算法進(jìn)行比較，分析性能。因此我們需要選擇一種好的算法來(lái)對(duì)內(nèi)存虛擬擴(kuò)充的一種有效方法，提高內(nèi)存利用率。頁(yè)面置換算法的介紹02part01先進(jìn)先出頁(yè)面置換(FIFO)02最近最少使用頁(yè)面置換(LRU)03最佳（Optimal）置換

在操作系統(tǒng)的運(yùn)行過(guò)程中，若發(fā)現(xiàn)內(nèi)存已無(wú)空閑的空間。為了確保系統(tǒng)中的進(jìn)程能正常運(yùn)行，就涉及到內(nèi)存和磁盤的程序或數(shù)據(jù)交換。然而將哪些頁(yè)面調(diào)入和調(diào)出，就需要根據(jù)算法來(lái)確定。這些算法被稱為頁(yè)面置換算法(page

replacement

algorithms)。網(wǎng)絡(luò)存儲(chǔ)與討論網(wǎng)絡(luò)存儲(chǔ)與討論先進(jìn)先出頁(yè)面置換(FIFO)

先進(jìn)先出算法（FIFO）。FIFO算法認(rèn)為先調(diào)入內(nèi)存的也不再被訪問(wèn)的可能性比其他頁(yè)大，因此最先調(diào)入內(nèi)存的頁(yè)面換出。.時(shí)刻123456789101112P432143543215M432143555211432143335224321444355F+++++++++Belady現(xiàn)象

一般來(lái)說(shuō)，對(duì)于任意進(jìn)程，如果給他分配的內(nèi)存頁(yè)面數(shù)越接近于她所要求的頁(yè)面數(shù)，缺頁(yè)率的次數(shù)會(huì)越少。在極限情況下，這個(gè)推論是成立的，因?yàn)槿绻o一個(gè)進(jìn)程分配了她所要求的全部頁(yè)面，則不會(huì)出現(xiàn)卻也現(xiàn)象。

但是，試用FIFI算法是，在未給出進(jìn)程分配足她所要求的頁(yè)面數(shù)時(shí)，又是會(huì)出現(xiàn)分配的頁(yè)面數(shù)增多，卻也次數(shù)份兒增加的奇怪現(xiàn)象。這種現(xiàn)象稱為Belady現(xiàn)象。網(wǎng)絡(luò)存儲(chǔ)與討論網(wǎng)絡(luò)存儲(chǔ)與討論Belady現(xiàn)象

。網(wǎng)絡(luò)存儲(chǔ)與討論Belady現(xiàn)象

。網(wǎng)絡(luò)存儲(chǔ)與討論最近最少使用頁(yè)面置換(LRU)

最近最少使用(least

recently

used，LRU)算法的基本思想是：依據(jù)物理塊中最近使用頁(yè)面情況預(yù)測(cè)未來(lái)使用情況。

FIFO置換算法性能之所以較差，是因?yàn)樗罁?jù)的條件是各個(gè)頁(yè)面調(diào)入內(nèi)存的時(shí)間，而頁(yè)面調(diào)入的先后并不能反映頁(yè)面的使用情況。最近最久未使用LRU）的頁(yè)面置換算法，是根據(jù)頁(yè)面調(diào)入內(nèi)存后的使用情況進(jìn)行決策的。LRU置換算法是選擇最近最久未使用的頁(yè)面予以淘汰。該算法賦予每個(gè)頁(yè)面一個(gè)訪問(wèn)字段，用來(lái)記錄一個(gè)頁(yè)面自上次被訪問(wèn)以來(lái)所經(jīng)歷的時(shí)間t，當(dāng)須淘汰一個(gè)頁(yè)面時(shí)，選擇現(xiàn)有頁(yè)面中其t值最大的，即最近最久未使用的頁(yè)面予以淘汰網(wǎng)絡(luò)存儲(chǔ)與討論最近最少使用頁(yè)面置換(LRU)

時(shí)刻123456789101112P432143543215M432143543215432143543214321435432F++++++++++網(wǎng)絡(luò)存儲(chǔ)與討論最佳（Optimal）置換 最佳置換算法是由Belady于1966年提出的一種理論上的算法。其所選擇的被淘汰的頁(yè)面，將是以后永不使用的，或是在最長(zhǎng)（未來(lái)）時(shí)間內(nèi)不再被訪問(wèn)的頁(yè)面。采用最佳置換算法，通?？杀ＷC獲得最低的缺頁(yè)率。但由于人們目前還無(wú)法預(yù)知一個(gè)進(jìn)程在內(nèi)存的若干個(gè)頁(yè)面中，哪一個(gè)頁(yè)面是將來(lái)最長(zhǎng)時(shí)間內(nèi)不再訪問(wèn)的，因而該算法時(shí)無(wú)法實(shí)現(xiàn)的。網(wǎng)絡(luò)存儲(chǔ)與討論

總結(jié)

操作系統(tǒng)的頁(yè)面調(diào)度算法還有很多種，每種算法的效率在不同的作業(yè)進(jìn)程中都可能不同，這些算法的實(shí)現(xiàn)各不相同，算法的復(fù)雜度也不一樣，但并不是算法越復(fù)雜它的效果最好。FIFO是最簡(jiǎn)單的一種算法，但有些時(shí)候它的效率也有可能是最好的。所以，判斷一個(gè)算法的好壞還有從實(shí)際情況出發(fā)，不能輕易下結(jié)論。

LRU算法的優(yōu)點(diǎn)是其最接近最優(yōu)的頁(yè)面置換算法，即它缺頁(yè)率是比較低的，缺點(diǎn)是實(shí)現(xiàn)LR