1、最佳頁面置換算法 （Optimal） （非常專業(yè)）評價一個算法的優(yōu)劣 ,可通過在一個特定的 存儲訪問序列（頁面走向 ）上運行它， 并計算缺頁數(shù)量來實現(xiàn)。 1 先入先出法（ FIFO）最簡單的頁面置換算法是先入先出（FIFO）法。這種算法的實質(zhì)是，總是選擇在 主存中停留時間最長（即最老）的一頁置換，即 先進入內(nèi)存的頁，先退出內(nèi)存 。 理由是：最早調(diào)入內(nèi)存的頁，其不再被使用的可能性比剛調(diào)入內(nèi)存的可能性大。建立一個FIFO隊列，收容所有在內(nèi)存中的頁。被置換頁面總是在隊列頭上進行。 當(dāng)一個頁面被放入內(nèi)存時，就把它插在隊尾上。這種算法只是 在按線性順序訪問地址空間時才是理想的 ，否則效率不高。 因為那

2、些常被訪問的頁， 往往在主存中也停留得最久， 結(jié)果它們因變“老”而不得不被 置換出去。FIFO的另一個缺點是，它有一種異常現(xiàn)象，即在增加存儲塊的情況下，反而使 缺頁中斷率增加了。當(dāng)然，導(dǎo)致這種異常現(xiàn)象的頁面走向?qū)嶋H上是很少見的。現(xiàn)在來看下 4 塊的情況：0 1 2 3 2 1 3 2 5 2 3 6 2 1 4 2【解答】剛開始內(nèi)存并沒有這個作業(yè)，所以發(fā)生缺頁中斷一次。作業(yè)的 0 號頁進入內(nèi)存。 （1 次缺頁中斷 ）而頁 1 又不在內(nèi)存，又發(fā)生缺頁中斷一次。作業(yè)頁 1 進入內(nèi)存。 （2 次缺頁中斷 ） 頁2不在內(nèi)存，發(fā)生缺頁中斷。頁 2進入內(nèi)存。 （3 次缺頁中斷 ） 頁3不在內(nèi)存，發(fā)生缺頁中

3、斷。頁 3進入內(nèi)存。 （4 次缺頁中斷 ） 接下來調(diào)入頁 2，頁 1，頁 3，頁 2。由于都在內(nèi)存中，并不發(fā)生缺頁中斷。 頁5不在內(nèi)存，發(fā)生缺頁中斷。頁 5進入內(nèi)存，頁 5置換頁 0。 （5 次缺頁中斷 ） 接下來調(diào)入頁 2，頁 3。由于都在內(nèi)存中，并不發(fā)生缺頁中斷。頁6不在內(nèi)存，發(fā)生缺頁中斷。頁 6進入內(nèi)存。頁 6置換頁 1。 （6 次缺頁中斷 ） 頁 2 在內(nèi)存，不發(fā)生缺頁中斷。頁 1 不在內(nèi)存 （在發(fā)生第 6 次缺頁中斷時被置換了 ），發(fā)生缺頁中斷。頁 1進入內(nèi)存，頁 2被置換。 （7 次缺頁中斷 ）頁 4置換頁 3，頁 4進入內(nèi)存。 （8 次缺頁中斷 ）現(xiàn)在調(diào)入頁 2，但頁 2在發(fā)生第

4、 7次缺頁中斷時被置換掉了。現(xiàn)在頁 2 進入內(nèi)存， 其置換頁 5。 （因為這個時候是頁 5最先進入內(nèi)存。 ）（9 次缺 頁中斷）2 最優(yōu)置換算法（ OPT）最優(yōu)置換（ Optimal Replacement ）是在理論上 提出的一種算法。其 實質(zhì)是：當(dāng) 調(diào)入新的一頁而必須預(yù)先置換某個老頁時，所選擇的老頁應(yīng)是將來不再被使用， 或者是在最遠的將來才被訪問。采用這種頁面置換算法，保證有最少的缺頁率。 但是最優(yōu)頁面置換算法的實現(xiàn)是困難的， 因為它需要人們預(yù)先就知道一個進程整 個運行過程中頁面走向的全部情況。 不過， 這個算法可用來衡量（如通過模擬實驗分析或理論分析） 其他算法的優(yōu)劣用最佳頁面置換法計算

5、缺頁次數(shù)6 5 4 3 5 4 3 6 5 4 56 6 6 3 3 3 3 6 6 6 65 5 5 5 5 5 5 5 5 54 4 4 4 4 4 4 4 4僅僅第四列 3 和第八列 6處, 缺頁.第四列處 :opt 算法中，頁面發(fā)生沖突時，被替換的頁面是未來訪問最靠后的頁面 例子中，第 4 列處， 6 的再次訪問最靠后，因而 6 被替換。之后，第 8 列處， 3 被替換是因為 3，4，5 中未來被訪問的頁是 4， 5 所以， 3 被替換。3 最久未使用算法（ LRU）FIFO算法和OPT算法之間的主要 差別是，F(xiàn)IFO算法利用頁面進入內(nèi)存后的時間 長短作為置換依據(jù)，而OPT算法的依據(jù)是

6、將來使用頁面的時間。 如果以最近的過 去作為不久將來的近似， 那么就可以把過去最長一段時間里不曾被使用的頁面置 換掉。它的 實質(zhì)是，當(dāng)需要置換一頁時， 選擇在最近一段時間里最久沒有使用過 的頁面予以置換 。這種算法就稱為 最久未使用算法（ Least Recently Used， LRU）。 LRU算法是與每個頁面最后使用的時間有關(guān)的。當(dāng)必須置換一個頁面時，LRU算法選擇過去一段時間里最久未被使用的頁面。LRU算法是經(jīng)常米用的頁面置換算法，并被認(rèn)為是相當(dāng)好的，但是存在如何實現(xiàn) 它的問題。LRU算法需要實際硬件的支持。其問題是怎么確定最后使用時間的順 序，對此有兩種可行的辦法： （1）計數(shù)器。最

7、簡單的情況是使每個頁表項對應(yīng)一個使用時間字段，并給CPU增加一個邏輯時鐘或計數(shù)器。每次存儲訪問，該時鐘都加1。每當(dāng)訪問一個頁面時，時鐘寄存器的內(nèi)容就被復(fù)制到相應(yīng)頁表項的使用時間字段中。 這樣我們就可 以始終保留著每個頁面最后訪問的“時間”。 在置換頁面時， 選擇該時間值最小 的頁面。這樣做，不僅要查頁表，而且當(dāng)頁表改變時（因 CPU調(diào)度）要維護這個 頁表中的時間，還要考慮到時鐘值溢出的問題。（2）棧。用一個棧保留頁號。每當(dāng)訪問一個頁面時，就把它從棧中取出放在棧 頂上。這樣一來， 棧頂總是放有目前使用最多的頁， 而棧底放著目前最少使用的 頁。由于要從棧的中間移走一項， 所以要用具有頭尾指針的雙向

8、鏈連起來。 在最 壞的情況下， 移走一頁并把它放在棧頂上需要改動 6個指針。每次修改都要有開 銷，但需要置換哪個頁面卻可直接得到，用不著查找，因為尾指針指向棧底，其 中有被置換頁。因?qū)崿F(xiàn)LRU算法必須有大量硬件支持，還需要一定的軟件開銷。所以實際實現(xiàn)的 都是一種簡單有效的LRU近似算法。一種LRU近似算法是最近未使用算法（Not Recently Used, NUR。它在存儲分 塊表的每一表項中增加一個引用位，操作系統(tǒng)定期地將它們置為 0。當(dāng)某一頁被 訪問時，由硬件將該位置 1。過一段時間后，通過檢查這些位可以確定哪些頁使 用過，哪些頁自上次置 0 后還未使用過。 就可把該位是 0 的頁淘汰出

9、去， 因為在 最近一段時間里它未被訪問過。4 第二次機會算法（ SCR）第二次機會算法的基本思想是與 FIFO相同的，但是有所改進，避免把經(jīng)常使用 的頁面置換出去 。當(dāng)選擇置換頁面時， 檢查它的訪問位。 如果是 0，就淘汰這頁； 如果訪問位是1,就給它第二次機會，并選擇下一個 FIFO頁面。當(dāng)一個頁面得 到第二次機會時，它的訪問位就清為 0，它的到達時間就置為當(dāng)前時間。如果該 頁在此期間被訪問過，則訪問位置 1。這樣給了第二次機會的頁面將不被淘汰， 直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經(jīng) 常使用，它的訪問位總保持為 1，它就從來不會被淘汰出去。 第二次機會算法可

10、視為一個環(huán)形隊列。用一個指針指示哪一頁是下面要淘汰的。 當(dāng)需要一個存儲塊時， 指針就前進， 直至找到訪問位是 0 的頁。隨著指針的前進， 把訪問位就清為 0。在最壞的情況下，所有的訪問位都是 1，指針要通過整個隊 列一周，每個頁都給第二次機會。這時就退化成 FIFO 算法了。頁面置換算法還有很多變種，如考慮到被置換頁是否修改過、按 FIFO 算法選中 的頁正在使用等情況，都需要硬件、軟件協(xié)同實現(xiàn)。部分的頁面在虛擬內(nèi)存， 部分在物理內(nèi)存， 操作系統(tǒng)需要訪問的頁面在物理內(nèi)存 找不到則會把物理內(nèi)存的某個頁面置換下來， 最佳置換算法的解決方法就是看物 理內(nèi)存中的哪一個頁面在將來最遲需要訪問，就置換它。

11、如物理內(nèi)存里是 0， 7， 6，訪問到 5時產(chǎn)生缺頁中斷，檢查物理內(nèi)存，發(fā)現(xiàn) 0 在 將來第 14 個訪問到，顯然置換 0 是最佳方案！using namespace std;#include <iostream>#define MAX 20int arrMAX=0,7,6,5,7,4,7,3,5,4,7,4,5,6,5,7,6,0,7,6; int tarrMAX;int Num=0;class Templistfriend class Opclass;private:Templist* next;int data;int count;public:Templist()next=

12、NULL;Templist(int data)this->data=data;next=NULL; Templist()public:int GetCount()return count;int GetData()return data;Templist* GetNext()return next;class Opclassprivate:Templist* head;public:Opclass()head=new Templist;Opclass(int size)head=new Templist;for(int i=0;i<size;i+)Templist* newnode

13、=new Templist; newnode->data=-1; newnode->next=head->next; head->next=newnode;Opclass()void Optimal();int Count(int data,int n);void Display(Templist* temp);int Opclass:Count(int data,int n)int count=0;for(int i=n;i<MAX;i+)count+;if(arri=data)break;return count;void Opclass:Optimal()i

14、nt Max=0;bool bl=false;Templist *temp=head->next,*p=NULL;for(int i=0;i<MAX;i+)if(temp=NULL)p=head->next;while(p!=NULL)if(p->data=arri)bl=true;break;p=p->next;if(bl=true)continue;p=head->next;while(p!=NULL) p->count=Count(p->data,i+1); if(Max<p->count) Max=p->count;p=

15、p->next;p=head->next;while(p!=NULL)if(p->count=Max)p->data=arri;tarrNum+=i+1;break;elsetemp->data=arri;temp=temp->next;cout<<" 物理塊狀態(tài)： "p=head->next;Display(p);void Opclass:Display(Templist* temp)while(temp!=NULL)cout<<temp->data<<" "temp=temp->next;cout<<endl;int main(int argc, _TCHAR* argv)Opclass opclass(3);cout<<" 分配了 3 個物理塊 "<<endl;cout<<" 頁面訪問順序： "for(int i=0;i<MAX;i+)cout<<" 第 "<<i+1<<" ： "<<arri<<" "cout