? ? ? ?選擇調(diào)出頁面的算法就稱為頁面置換算法。好的頁面置換算法應(yīng)有較低的頁面更換頻率，也就是說，應(yīng)將以后不會(huì)再訪問或者以后較長時(shí)間內(nèi)不會(huì)再訪問的頁面先調(diào)出。

常見的置換算法有以下四種（以下來自操作系統(tǒng)課本）。

1. 最佳置換算法(OPT)

最佳(Optimal, OPT)置換算法所選擇的被淘汰頁面將是以后永不使用的，或者是在最長時(shí)間內(nèi)不再被訪問的頁面,這樣可以保證獲得最低的缺頁率。但由于人們目前無法預(yù)知進(jìn)程在內(nèi)存下的若千頁面中哪個(gè)是未來最長時(shí)間內(nèi)不再被訪問的，因而該算法無法實(shí)現(xiàn)。

最佳置換算法可以用來評價(jià)其他算法。假定系統(tǒng)為某進(jìn)程分配了三個(gè)物理塊，并考慮有以下頁面號(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è)頁面依次裝入內(nèi)存。進(jìn)程要訪問頁面2時(shí)，產(chǎn)生缺頁中斷，根據(jù)最佳置換算法，選擇第18次訪問才需調(diào)入的頁面7予以淘汰。然后，訪問頁面0時(shí)，因?yàn)橐言趦?nèi)存中所以不必產(chǎn)生缺頁中斷。訪問頁面3時(shí)又會(huì)根據(jù)最佳置換算法將頁面1淘汰……依此類推，如圖3-26所示。從圖中可以看出釆用最佳置換算法時(shí)的情況。

可以看到，發(fā)生缺頁中斷的次數(shù)為9，頁面置換的次數(shù)為6。

訪問頁面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理塊1	7	7	7	2	?	2	?	2	?	?	2	?	?	2	?	?	?	7	?	?
物理塊2	?	0	0	0	?	0	?	4	?	?	0	?	?	0	?	?	?	0	?	?
物理塊3	?	?	1	1	?	3	?	3	?	?	3	?	?	1	?	?	?	1	?	?
缺頁否	√	?	√	√	?	√	?	√	?	?	√	?	?	√	?	?	?	√	?	?

圖3-26 ?利用最佳置換算法時(shí)的置換圖

2. 先進(jìn)先出(FIFO)頁面置換算法

優(yōu)先淘汰最早進(jìn)入內(nèi)存的頁面，亦即在內(nèi)存中駐留時(shí)間最久的頁面。該算法實(shí)現(xiàn)簡單，只需把調(diào)入內(nèi)存的頁面根據(jù)先后次序鏈接成隊(duì)列，設(shè)置一個(gè)指針總指向最早的頁面。但該算法與進(jìn)程實(shí)際運(yùn)行時(shí)的規(guī)律不適應(yīng)，因?yàn)樵谶M(jìn)程中，有的頁面經(jīng)常被訪問。

訪問頁面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理塊1	7	7	7	2	?	2	2	4	4	4	0	?	?	0	0	?	?	7	7	7
物理塊2	?	0	0	0	?	3	3	3	2	2	2	?	?	1	1	?	?	1	0	0
物理塊3	?	?	1	1	?	1	0	0	0	3	3	?	?	3	2	?	?	2	2	1
缺頁否	√	√	√	√	?	√	√	√	√	√	√	?	?	√	√	?	?	√	√	√

圖3-27 ?利用FIFO置換算法時(shí)的置換圖 這里仍用上面的實(shí)例，釆用FIFO算法進(jìn)行頁面置換。進(jìn)程訪問頁面2時(shí)，把最早進(jìn)入內(nèi)存的頁面7換出。然后訪問頁面3時(shí)，再把2, 0, 1中最先進(jìn)入內(nèi)存的頁換出。由圖?3-27可以看出，利用FIFO算法時(shí)進(jìn)行了?12次頁面置換，比最佳置換算法正好多一倍。

FIFO算法還會(huì)產(chǎn)生當(dāng)所分配的物理塊數(shù)增大而頁故障數(shù)不減反增的異常現(xiàn)象，這是由?Belady于1969年發(fā)現(xiàn)，故稱為Belady異常，如圖3-28所示。只有FIFO算法可能出現(xiàn)Belady?異常，而LRU和OPT算法永遠(yuǎn)不會(huì)出現(xiàn)Belady異常。

訪問頁面	1	2	3	4	1	2	5	1	2	3	4	5
物理塊1	1	1	1	4	4	4	5	?	?	5	5	?
物理塊2	?	2	2	2	1	1	1	?	?	3	3	?
物理塊3	?	?	3	3	3	2	2	?	?	2	4	?
缺頁否	√	√	√	√	√	√	√	?	?	√	√	?
?	?	1	1	1	?	?	5	5	5	5	4	4
物理塊2*	?	2	2	2	?	?	2	1	1	1	1	5
物理塊3*	?	?	3	3	?	?	3	3	2	2	2	2
物理塊4*	?	?	?	4	?	?	4	4	4	3	3	3
缺頁否	√	√	√	?	?	?	√	√	√	√	√	√

圖?3-28 ??Belady?異常

3. 最近最久未使用(LRU)置換算法

選擇最近最長時(shí)間未訪問過的頁面予以淘汰，它認(rèn)為過去一段時(shí)間內(nèi)未訪問過的頁面，在最近的將來可能也不會(huì)被訪問。該算法為每個(gè)頁面設(shè)置一個(gè)訪問字段，來記錄頁面自上次被訪問以來所經(jīng)歷的時(shí)間，淘汰頁面時(shí)選擇現(xiàn)有頁面中值最大的予以淘汰。

再對上面的實(shí)例釆用LRU算法進(jìn)行頁面置換，如圖3-29所示。進(jìn)程第一次對頁面2訪問時(shí)，將最近最久未被訪問的頁面7置換出去。然后訪問頁面3時(shí)，將最近最久未使用的頁面1換出。

訪問頁面	7	0	1	2	0	3	0	4	2	3	0	3	2	1	2	0	1	7	0	1
物理塊1	7	7	7	2	?	2	?	4	4	4	0	?	?	1	?	1	?	1	?	?
物理塊2	?	0	0	0	?	0	?	0	0	3	3	?	?	3	?	0	?	0	?	?
物理塊3	?	?	1	1	?	3	?	3	2	2	2	?	?	2	?	2	?	7	?	?
缺頁否	√	√	√	√	?	√	?	√	√	√	√	?	?	√	?	√	?	√	?	?

圖3-29 ?LRU頁面置換算法時(shí)的置換圖
在圖3-29中，前5次置換的情況與最佳置換算法相同，但兩種算法并無必然聯(lián)系。實(shí)際上，LRU算法根據(jù)各頁以前的情況，是“向前看”的，而最佳置換算法則根據(jù)各頁以后的使用情況，是“向后看”的。

LRU性能較好，但需要寄存器和棧的硬件支持。LRU是堆棧類的算法。理論上可以證明，堆棧類算法不可能出現(xiàn)Belady異常。FIFO算法基于隊(duì)列實(shí)現(xiàn)，不是堆棧類算法。

4. 時(shí)鐘(CLOCK)置換算法

LRU算法的性能接近于OPT,但是實(shí)現(xiàn)起來比較困難，且開銷大；FIFO算法實(shí)現(xiàn)簡單，但性能差。所以操作系統(tǒng)的設(shè)計(jì)者嘗試了很多算法，試圖用比較小的開銷接近LRU的性能，這類算法都是CLOCK算法的變體。

簡單的CLOCK算法是給每一幀關(guān)聯(lián)一個(gè)附加位，稱為使用位。當(dāng)某一頁首次裝入主存時(shí)，該幀的使用位設(shè)置為1;當(dāng)該頁隨后再被訪問到時(shí)，它的使用位也被置為1。對于頁替換算法，用于替換的候選幀集合看做一個(gè)循環(huán)緩沖區(qū)，并且有一個(gè)指針與之相關(guān)聯(lián)。當(dāng)某一頁被替換時(shí)，該指針被設(shè)置成指向緩沖區(qū)中的下一幀。當(dāng)需要替換一頁時(shí)，操作系統(tǒng)掃描緩沖區(qū)，以查找使用位被置為0的一幀。每當(dāng)遇到一個(gè)使用位為1的幀時(shí)，操作系統(tǒng)就將該位重新置為0；如果在這個(gè)過程開始時(shí)，緩沖區(qū)中所有幀的使用位均為0，則選擇遇到的第一個(gè)幀替換；如果所有幀的使用位均為1,則指針在緩沖區(qū)中完整地循環(huán)一周，把所有使用位都置為0，并且停留在最初的位置上，替換該幀中的頁。由于該算法循環(huán)地檢查各頁面的情況，故稱為CLOCK算法，又稱為最近未用(Not Recently Used, NRU)算法。

CLOCK算法的性能比較接近LRU，而通過增加使用的位數(shù)目，可以使得CLOCK算法更加高效。在使用位的基礎(chǔ)上再增加一個(gè)修改位，則得到改進(jìn)型的CLOCK置換算法。這樣，每一幀都處于以下四種情況之一：

最近未被訪問，也未被修改(u=0, m=0)。

最近被訪問，但未被修改(u=1, m=0)。

最近未被訪問，但被修改(u=0, m=1)。

最近被訪問，被修改(u=1, m=1)。

算法執(zhí)行如下操作步驟：

從指針的當(dāng)前位置開始，掃描幀緩沖區(qū)。在這次掃描過程中，對使用位不做任何修改。選擇遇到的第一個(gè)幀(u=0, m=0)用于替換。

如果第1)步失敗，則重新掃描，查找(u=0, m=1)的幀。選擇遇到的第一個(gè)這樣的幀用于替換。在這個(gè)掃描過程中，對每個(gè)跳過的幀，把它的使用位設(shè)置成0。

如果第2)步失敗，指針將回到它的最初位置，并且集合中所有幀的使用位均為0。重復(fù)第1步，并且如果有必要，重復(fù)第2步。這樣將可以找到供替換的幀。

改進(jìn)型的CLOCK算法優(yōu)于簡單CLOCK算法之處在于替換時(shí)首選沒有變化的頁。由于修改過的頁在被替換之前必須寫回，因而這樣做會(huì)節(jié)省時(shí)間。

#include <iostream> #include<map> #include<set> #include <algorithm> #include<cstdio> #include<cstring> #include<cmath> #define N 200 using namespace std; int page[N];//頁面引用號(hào) int block[N];//物理塊，內(nèi)存 int dist[N][N];//表示第i次訪問內(nèi)存的時(shí)候，內(nèi)存中的頁面j 在以后被訪問的最小時(shí)間 int n;//頁面引用號(hào)個(gè)數(shù) int m;//物理塊數(shù)目 int page_max;//最大頁面號(hào) int pre[N];//page[i]在page中的索引 int opt(){//最佳頁面置換算法 int page_lack = 0;memset(pre, 0, sizeof(pre));memset(dist, 0x3f, sizeof(dist));memset(block, -1, sizeof(block));for(int i=n; i>=1; --i){for(int j=0; j<=page_max; ++j) if(pre[j])dist[i][j] = pre[j] - i;pre[page[i]] = i; }for(int i=1; i<=n; ++i){//開始訪問頁面，初始是內(nèi)存中沒有分頁 int j;int max_dist = 0, p; for(j=1; j<=m; ++j){if(block[j] == -1){//改塊沒有放入頁面，則直接放入, 產(chǎn)生缺頁 block[j] = page[i]; cout<<"頁面"<<page[i]<<"不在內(nèi)存，直接放入物理塊"<<j<<"中!"<<endl;page_lack++;break;} else if(block[j] == page[i])//頁面存在內(nèi)存中 break;if(max_dist < dist[i][block[j]]){max_dist = dist[i][block[j]];//說明block[j] 對應(yīng)的頁面以后會(huì)長時(shí)間不會(huì)用到 p = j;//block[] 第j個(gè)頁面會(huì)被替換掉 }}if(j > m){//此時(shí)內(nèi)存中不能在放入新的分頁，而且沒有找到page[i]對應(yīng)的分頁，接下來進(jìn)行頁面替換 cout<<"頁面"<<page[i]<<"不在內(nèi)存，將物理塊"<<p<<"中的頁面" <<block[p]<<"替換掉!"<<endl;block[p] = page[i];page_lack++; }cout<<endl<<"當(dāng)前內(nèi)存中頁面的情況:"<<endl; for(int k=1; k<=m; ++k)//內(nèi)存中頁面加載情況 cout<<block[k]<<" ";cout<<endl<<endl;}return page_lack;//返回缺頁次數(shù) } int lru(){//最近最久未使用算法和opt算法差不多，只不過是lru是向前看， opt是向后看 int page_lack = 0;memset(pre, 0, sizeof(pre));memset(dist, 0x3f, sizeof(dist));memset(block, -1, sizeof(block));for(int i=1; i<=n; ++i){for(int j=0; j<=page_max; ++j) if(pre[j])dist[i][j] = i - pre[j];pre[page[i]] = i; }for(int i=1; i<=n; ++i){//開始訪問頁面，初始是內(nèi)存中沒有分頁 int j;int max_dist = 0, p; for(j=1; j<=m; ++j){if(block[j] == -1){//改塊沒有放入頁面，則直接放入, 產(chǎn)生缺頁 block[j] = page[i]; cout<<"頁面"<<page[i]<<"不在內(nèi)存，直接放入物理塊"<<j<<"中!"<<endl;page_lack++;break;} else if(block[j] == page[i])//頁面存在內(nèi)存中 break;if(max_dist < dist[i][block[j]]){max_dist = dist[i][block[j]];//說明block[j] 對應(yīng)的頁面以后會(huì)長時(shí)間不會(huì)用到 p = j;//block[] 第j個(gè)頁面會(huì)被替換掉 }}if(j > m){//此時(shí)內(nèi)存中不能在放入新的分頁，而且沒有找到page[i]對應(yīng)的分頁，接下來進(jìn)行頁面替換 cout<<"頁面"<<page[i]<<"不在內(nèi)存，將物理塊"<<p<<"中的頁面" <<block[p]<<"替換掉!"<<endl;block[p] = page[i];page_lack++; }cout<<endl<<"當(dāng)前內(nèi)存中頁面的情況:"<<endl; for(int k=1; k<=m; ++k)//內(nèi)存中頁面加載情況 cout<<block[k]<<" ";cout<<endl<<endl;}return page_lack;//返回缺頁次數(shù) } set<int>page_set; int fifo(){//先進(jìn)先出頁面置換算法int page_lack = 0; memset(block, -1, sizeof(block));int index = 1;for(int i=1; i<=n; ++i){if(index > m) index = 1;set<int>::iterator it;it = page_set.find(page[i]); if(it == page_set.end()){if(block[index] != -1)page_set.erase(block[index]);page_set.insert(page[i]);block[index++] = page[i];++page_lack;} for(int k=1; k<=m; ++k)cout<<block[k]<<" ";cout<<endl;} return page_lack; }int nru[N];//表示 物理塊 i 最近時(shí)候被訪問過 int page_in_block[N];//頁面 i 在 block的下標(biāo)索引 int clock(){int index = 1;int page_lack = 0;memset(block, -1, sizeof(block));for(int i=1; i<=n; ++i){if(page_in_block[page[i]]){//如果page[i]已經(jīng)在內(nèi)存中 nru[page_in_block[page[i]]] = 1;//重新標(biāo)記這個(gè)物理塊中的頁面被訪問過了 cout<<endl<<"第"<<i<<"次: 頁面"<<page[i]<<"已經(jīng)存在物理塊"<< page_in_block[page[i]] << "中!"<<endl;}else {while(true){if(index > m) index = 1;if(block[index] == -1) {nru[index] = 1;page_in_block[page[i]] = index;block[index++] = page[i];++page_lack;break;}if(block[index] == page[i]){nru[index++] = 1;break;} else {if(nru[index] == 0){//替換該頁面 nru[index] = 1;page_in_block[block[index]] = 0;cout<<endl<<"第"<<i<<"次: 物理塊"<<index<<"中的頁面"<< block[index] <<"最近未被使用，將要被頁面"<<page[i]<<"替換!"<<endl;page_in_block[page[i]] = index;block[index++] = page[i];++page_lack;break;} elsenru[index++] = 0;}} }for(int k=1; k<=m; ++k) cout<<block[k]<<" ";cout<<endl;}return page_lack; }int main(){cin>>n>>m;for(int i=1; i<=n; ++i){ cin>>page[i];page_max = max(page_max, page[i]) ;} cout<<"opt缺頁中斷次數(shù):"<<opt()<<endl;cout<<"***********************************"<<endl;cout<<"lru缺頁中斷次數(shù):"<<lru()<<endl;cout<<"***********************************"<<endl;cout<<"fifo缺頁中斷次數(shù):"<<fifo()<<endl;cout<<"***********************************"<<endl;cout<<"clock缺頁中斷次數(shù):"<<clock()<<endl;return 0; } /* 20 3 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 112 3 2 3 2 1 5 2 4 5 3 2 5 2 */

?

轉(zhuǎn)載于:https://www.cnblogs.com/hujunzheng/p/4831007.html

總結(jié)

以上是生活随笔為你收集整理的操作系统页面置换算法(opt,lru,fifo,clock)实现的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。