os缺頁置換演算法

A. 操作系統頁面置換演算法

先進先出FIFO：（0代表未被佔用）
（1）1，0，0，0（2）1，2，0，0（3）1，2，3，0（4）1，2，3，4（5）1，2，3，4訪問2（6）1，2，3，4訪問1（7）5，2，3，4訪問5替換1（8）5，6，3，4訪問6替換2（9）5，6，2，4訪問2替換3（10）5，6，2，1訪問1替換4（11）5，6，2，1訪問2（12）3，6，2，1訪問3替換5（13）3，7，2，1訪問7替換6（14）3，7，6，1訪問6替換2（15）3，7，6，1訪問3（16）3，7，6，2訪問2替換1（16）1，7，6，2訪問1替換3（17）1，7，6，2訪問2（18）1，3，6，2訪問3替換7（20）1，3，6，2訪問6
缺頁率為：14/20=0.7

最近最久未使用LRU：（0代表未被佔用）
（1）1，0，0，0（2）1，2，0，0（3）1，2，3，0（4）1，2，3，4（5）1，2，3，4訪問2（6）1，2，3，4訪問1（7）1，2，5，4訪問5替換3（8）1，2，5，6訪問6替換4（9）1，2，5，6訪問2（10）1，2，5，6訪問1（11）1，2，5，6訪問2（12）1，2，3，6訪問3替換5（13）1，2，3，7訪問7替換6（14）6，2，3，7訪問6替換1（15）6，2，3，7訪問3（16）6，2，3，7訪問2（17）6，2，3，1訪問1替換7（18）6，2，3，1訪問2（19）6，2，3，1訪問3（20）6，2，3，1訪問6
缺頁率為：10/20=0.5

最佳置換演算法OPT：（0代表未被佔用）
（1）1，0，0，0（2）1，2，0，0（3）1，2，3，0（4）1，2，3，4（5）1，2，3，4訪問2（6）1，2，3，4訪問1（7）1，2，3，5訪問5替換4（8）1，2，3，6訪問6替換5（9）1，2，3，6訪問2（10)1，2，3，6訪問1（11）1，2，3，6訪問2（12）1，2，3，6訪問3（13）7，2，3，6訪問7替換1（14）7，2，3，6訪問6（15）7，2，3，6訪問3（16）7，2，3，6訪問2（17）1，2，3，6訪問1替換7（18）1，2，3，6訪問2（19）1，2，3，6訪問3（20）1，2，3，6訪問6
缺頁率為：8/20=0.4

B. 操作系統 頁面置換演算法LRU

這兩種方法都正確，LRU演算法有幾種實現，前一種是基於計數器的，需要統計之前的引用頁，後一種是基於隊列的調度，只調整隊列就能找到最近未使用的頁。
如果是考試的話可以說明一下用了哪種方法，個人感覺第二種方法比較合適
《操作系統概念》第七版·高等教育出版社P286

C. 求用c++程序設計的實驗:模擬分頁式存儲管理中硬體的地址轉換和用先進先出調度演算法(FIFO)處理缺頁中斷。

#include<iostream.h>
#include<stdlib.h>
#include<iomanip.h>
#include"windows.h"
#include"os.h"
#define n 64//實驗中假定主存的長度
#define m 4//實驗中假定每個作業分得主存塊塊數
int p[m];//定義頁
struct
{
short int lnumber;//頁號
short int flag;//表示該頁是否在主存，「1」表示在主存，「0」表示不在主存
short int pnumber;//該頁所在主存塊的塊號
short int write;//該頁是否被修改過，「1」表示修改過，「0」表示沒有修改過
short int dnumber;//該頁存放在磁碟上的位置，即磁碟塊號
short int times;//被訪問的次數，用於LRU演算法
}page[n];//定義頁表
//各個函數的實現如下：
computer::computer()
{
int i;
for(i=0;i<n;i++)
{
page[i].lnumber = i;
page[i].flag = 0;
page[i].pnumber = 10000;//用10000表示為空
page[i].write = 0;
page[i].dnumber = i;
page[i].times = 0;
}//初始化頁表

for(i=0;i<m;i++)
{
page[i].pnumber = i;
}

for(i=0;i<m;i++)
{
p[i] = i;
page[i].flag = 1;
}//初始化頁
}
void computer::showpagelist()
{
int i;
cout<<"頁號"<<"\t"<<"是否在主存中"<<"\t"<<"塊 號"<<"\t"<<"是否被修改過"<<"\t"<<"磁碟塊號"<<"\t"<<"訪問次數"<<endl;
for(i=0;i<n;i++)
{
cout<<page[i].lnumber<<"\t"<<page[i].flag<<" "<<page[i].pnumber<<"\t"<<page[i].write<<" "<<page[i].dnumber<<" \t"<<page[i].times<<endl;
}
}
void computer::showpage()
{
int i;
for(i=0;i<m;i++)
{
cout<<"\t"<<p[i];
}
cout<<endl;
}
void computer::transformation()
{
unsigned logicAddress,logicNumber,innerAddress,physicsAddress,physicsNumber;
int i,head=0,fail = 0;
int method,temppage=0;
short int times = 10000;
cout<<"請輸入一個邏輯地址（四位十六進制數）:";
cin>>hex>>logicAddress;//讀入邏輯地址
logicNumber = logicAddress >> 10;//得到頁號
cout<<"頁號為:"<<logicNumber<<endl;
innerAddress = logicAddress & 0x03ff;//得到頁內地址
cout<<"頁內地址為:"<<innerAddress<<endl;
for(i=0;i<n;i++)
{
if(logicNumber==(unsigned)page[i].lnumber)
{
if(page[i].flag == 1)
{
cout<<"請求的頁面在主存中!"<<endl;
page[i].times++;
physicsNumber = page[i].pnumber;//由頁號得到塊號
cout<<"請求的主存塊號為:"<<physicsNumber<<endl;
physicsAddress = physicsNumber << 10 |innerAddress;//得到物理地址
cout<<"請求的物理地址為:"<<physicsAddress<<endl;//輸出物理地址
break;
}
else
{

cout<<"請求的頁面不在主存中! 將進行缺頁中斷處理!"<<endl<<"請選擇演算法!"<<endl;
cout<<"1.先進先出"<<endl<<"2.最近最少用"<<endl<<"請選擇置換演算法:";
cin>>method;
if(method == 1) //採用先進先出演算法
{
cout<<"採用先進先出演算法!"<<endl;
fail = p[head];
cout<<"第"<<fail<<"頁將被替換!"<<endl;
p[head] = logicNumber;
head = (head+1) % m;
if(page[fail].write == 1)
cout<<"第"<<fail<<"頁曾被修改過!"<<endl;
page[fail].flag = 0;
page[logicNumber].flag = 1;
page[logicNumber].write = 0;
page[logicNumber].pnumber = page[fail].pnumber;
page[fail].pnumber = 10000;
page[logicNumber].times++;
break;
}
else if(method == 2) //採用最近最少用演算法
{
cout<<"採用最近最少用演算法!"<<endl;
for(i=0;i<n;i++)
{
if(page[i].flag == 1)
{
if(page[i].times<times)
{
times = page[i].times;
temppage = page[i].lnumber;
}
}
}
cout<<"第"<<temppage<<"頁將被替換!"<<endl;
for(i=0;i<m;i++)
{
if(p[i] == temppage)
{
p[i] = logicNumber;
}
}
if(page[temppage].write == 1)
cout<<"第"<<temppage<<"頁曾被修改過!"<<endl;
page[temppage].flag = 0;
page[logicNumber].flag = 1;
page[logicNumber].write = 0;
page[logicNumber].pnumber = page[temppage].pnumber;
page[temppage].pnumber = 10000;
page[logicNumber].times++;
break;
}
else
{ cout<<"你輸入有誤，即將退出!";
exit(1);
}
}
}
}
}
void main()
{
char c,d;
computer os;
cout<<"頁表正在初始化中...，3秒鍾後為你顯示頁和頁表！"<<endl;
Sleep(3000);
os.showpage();
os.showpagelist();
T:
os.transformation();
cout<<"是否顯示頁和頁表？（Y/N）";
cin>>c;
switch(c)
{
case 'y':
os.showpage();
os.showpagelist();
case 'n':
cout<<"是否繼續進行請求分頁？（Y/N）";
cin>>d;
if (d=='Y'||d=='y')
goto T;
else if (d=='N'||d=='n')
exit(1);
else
cout<<"輸入錯誤！"<<endl;
default:cout<<"輸入錯誤！"<<endl;
}

}

D. 操作系統 頁式管理中的置換演算法 怎麼看缺頁

去年學過，現在記憶殘缺，盡量回答
FIFO演算法是先入先出演算法吧，首先是有三個頁面，所以一列只有三行
再者，根據先入先出的規則，後面讀取的串替代內存中進來時間最久的串，若當前讀取的串內存中已經有了，則內存中的頁面不變
缺頁就是沒有重復的頁面，即沒有重復的頁面共有10頁，就缺頁10次
LRU LFU就是看訪問串前面或者後面會不會有使用到，具體哪個我忘了，把FIFO看明白了你就曉得了
FIFO：
7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1
7 7 7 2 2 2 2 4 4 4 0 0 0 0 0 0 0
空0 0 0 0 3 3 3 2 2 2 2 2 1 1 1 1
空空1 1 1 1 0 0 0 3 3 3 3 3 2 2 2
你的打錯了吧
PS:我上面說缺頁10頁是隨便舉的例子，題目中的缺頁數是12，缺頁不是很好計算的么，就是沒有內容重復的內存頁，數一下就知道了，還不知道就留言我吧

E. 頁面置換演算法的常見的置換演算法

最簡單的頁面置換演算法是先入先出（FIFO）法。這種演算法的實質是，總是選擇在主存中停留時間最長（即最老）的一頁置換，即先進入內存的頁，先退出內存。理由是：最早調入內存的頁，其不再被使用的可能性比剛調入內存的可能性大。建立一個FIFO隊列，收容所有在內存中的頁。被置換頁面總是在隊列頭上進行。當一個頁面被放入內存時，就把它插在隊尾上。
這種演算法只是在按線性順序訪問地址空間 時才是理想的，否則效率不高。因為那些常被訪問的頁，往往在主存中也停留得最久，結果它們因變「老」而不得不被置換出去。
FIFO的另一個缺點是，它有一種異常現象，即在增加存儲塊的情況下，反而使缺頁中斷率增加了。當然，導致這種異常現象的頁面走向實際上是很少見的。
FIFO演算法和OPT演算法之間的主要差別是，FIFO演算法利用頁面進入內存後的時間長短作為置換依據，而OPT演算法的依據是將來使用頁面的時間。如果以最近的過去作為不久將來的近似，那麼就可以把過去最長一段時間里不曾被使用的頁面置換掉。它的實質是，當需要置換一頁時，選擇在之前一段時間里最久沒有使用過的頁面予以置換。這種演算法就稱為最久未使用演算法（Least Recently Used，LRU）。
LRU演算法是與每個頁面最後使用的時間有關的。當必須置換一個頁面時，LRU演算法選擇過去一段時間里最久未被使用的頁面。
LRU演算法是經常採用的頁面置換演算法，並被認為是相當好的，但是存在如何實現它的問題。LRU演算法需要實際硬體的支持。其問題是怎麼確定最後使用時間的順序，對此有兩種可行的辦法：
1.計數器。最簡單的情況是使每個頁表項對應一個使用時間欄位，並給CPU增加一個邏輯時鍾或計數器。每次存儲訪問，該時鍾都加1。每當訪問一個頁面時，時鍾寄存器的內容就被復制到相應頁表項的使用時間欄位中。這樣我們就可以始終保留著每個頁面最後訪問的「時間」。在置換頁面時，選擇該時間值最小的頁面。這樣做， 不僅要查頁表，而且當頁表改變時（因CPU調度）要 維護這個頁表中的時間，還要考慮到時鍾值溢出的問題。
2.棧。用一個棧保留頁號。每當訪問一個頁面時，就把它從棧中取出放在棧頂上。這樣一來，棧頂總是放有目前使用最多的頁，而棧底放著目前最少使用的頁。由於要從棧的中間移走一項，所以要用具有頭尾指針的雙向鏈連起來。在最壞的情況下，移走一頁並把它放在棧頂上需要改動6個指針。每次修改都要有開銷，但需要置換哪個頁面卻可直接得到，用不著查找，因為尾指針指向棧底，其中有被置換頁。
因實現LRU演算法必須有大量硬體支持，還需要一定的軟體開銷。所以實際實現的都是一種簡單有效的LRU近似演算法。
一種LRU近似演算法是最近未使用演算法（Not Recently Used，NUR）。它在存儲分塊表的每一表項中增加一個引用位，操作系統定期地將它們置為0。當某一頁被訪問時，由硬體將該位置1。過一段時間後，通過檢查這些位可以確定哪些頁使用過，哪些頁自上次置0後還未使用過。就可把該位是0的頁淘汰出去，因為在之前最近一段時間里它未被訪問過。
4）Clock置換演算法（LRU演算法的近似實現）
5）最少使用（LFU）置換演算法
在採用最少使用置換演算法時，應為在內存中的每個頁面設置一個移位寄存器，用來記錄該頁面被訪問的頻率。該置換演算法選擇在之前時期使用最少的頁面作為淘汰頁。由於存儲器具有較高的訪問速度，例如100 ns，在1 ms時間內可能對某頁面連續訪 問成千上萬次，因此，通常不能直接利用計數器來記錄某頁被訪問的次數，而是採用移位寄存器方式。每次訪問某頁時，便將該移位寄存器的最高位置1，再每隔一定時間(例如100 ns)右移一次。這樣，在最近一段時間使用最少的頁面將是∑Ri最小的頁。
LFU置換演算法的頁面訪問圖與LRU置換演算法的訪問圖完全相同；或者說，利用這樣一套硬體既可實現LRU演算法，又可實現LFU演算法。應該指出，LFU演算法並不能真正反映出頁面的使用情況，因為在每一時間間隔內，只是用寄存器的一位來記錄頁的使用情況，因此，訪問一次和訪問10 000次是等效的。
6）工作集演算法
7）工作集時鍾演算法
8）老化演算法（非常類似LRU的有效演算法）
9）NRU(最近未使用）演算法
10）第二次機會演算法
第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，檢查它的訪問位。如果是 0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。
第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個 存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。

F. 操作系統頁面置換演算法題，誰會

第二次機會演算法：

與FIFO、OPT、LRU、NRU等同為操作系統中請求分頁式管理方式的頁面置換演算法。

第二次機會演算法的基本思想是與FIFO相同的，但是有所改進，避免把經常使用的頁面置換出去。當選擇置換頁面時，依然和FIFO一樣，選擇最早置入內存的頁面。但是二次機會法還設置了一個訪問狀態位。所以還要檢查頁面的的訪問位。如果是0，就淘汰這頁；如果訪問位是1，就給它第二次機會，並選擇下一個FIFO頁面。當一個頁面得到第二次機會時，它的訪問位就清為0，它的到達時間就置為當前時間。如果該頁在此期間被訪問過，則訪問位置為1。這樣給了第二次機會的頁面將不被淘汰，直至所有其他頁面被淘汰過（或者也給了第二次機會）。因此，如果一個頁面經常使用，它的訪問位總保持為1，它就從來不會被淘汰出去。

第二次機會演算法可視為一個環形隊列。用一個指針指示哪一頁是下面要淘汰的。當需要一個存儲塊時，指針就前進，直至找到訪問位是0的頁。隨著指針的前進，把訪問位就清為0。在最壞的情況下，所有的訪問位都是1，指針要通過整個隊列一周，每個頁都給第二次機會。這時就退化成FIFO演算法了。

G. 頁面置換演算法中的缺頁率如何計算

很簡單，把每次有新頁面走向進入時記錄下來。如果下一次進入時改變原先頁面的佔有情況，則算一次缺頁。一般情況下如果頁面為3則前三次都算缺頁。

H. 幾種頁面置換演算法的基本原理及實現方法

收藏推薦 在多道程序的正常運行過程中,屬於不同進程的頁面被分散存放在主存頁框中,當正在運行的進程所訪問的頁面不在內存時,系統會發生缺頁中斷,在缺頁中斷服務程序中會將所缺的頁面調入內存,如內存已無空閑頁框,缺頁中斷服務程序就會調用頁面置換演算法,頁面置換演算法的目的就是選出一個被淘汰的頁面.把內存和外存統一管理的真正目的是把那些被訪問概率非常高的頁存放在內存中.因此,置換演算法應該置換那些被訪問概率最低的頁,將它們移出內存.1最佳置換演算法基本原理:淘汰以後不再需要的或最遠的將來才會用到的頁面.這是1966年Belady提出的理想演算法,但無法實現,主要用於評價其他置換演算法.例:分配給某進程的內存頁面數是3頁,頁面地址流如下:7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,其內存動態分配過程如下:7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 17 7 7 2 2 2 2 2 2 2 2 2 2 2 2 2 20 0 0 0 0 0 4 4 4 0 0 0 0 0 0 01 1 1 3 3 3 3 3 3 3 3 1 1 1 12先進先出置換......(本文共計2頁) 如何獲取本文>>

I. 計算機操作系統頁面置換演算法

我的理解，圖中為頁面的請求序列，首次請求1，3，2，5這四個頁面時，均沒有命中緩存，產生了一個缺頁異常，操作系統載入相應的頁面後，下次再請求時就為命中狀態。12次請求，有4次缺頁，缺頁率為4/12=1/3