頁面淘汰演算法

㈠ 頁面淘汰演算法

LRU（2個塊）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 3 3 2 2 5 5 2 2 2 2 7 7 3 3 1 1 3 3
2 2 4 4 1 1 6 6 1 1 3 3 6 6 2 2 2 2 6
缺頁中斷18次

LRU（4個塊）：
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 1 1 6 6 6 6 6 6 6
2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2
3 3 3 3 5 5 5 5 5 3 3 3 3 3 3 3 3 3
4 4 4 4 6 6 6 6 6 7 7 7 7 1 1 1 1
缺頁中斷次數10次

FIFO（2個塊）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 1 1 1 1 1 3 3 6 6 2 2 2 3 3
2 2 4 4 1 1 6 6 1 1 2 7 7 3 3 1 1 1 6
缺頁中斷次數18次

FIFO（4個塊）
1 2 3 4 2 1 5 6 2 1 2 3 7 6 3 2 1 2 3 6
————————————————————
1 1 1 1 1 1 5 5 5 5 5 3 3 3 3 3 1 1 1 1
2 2 2 2 2 2 6 6 6 6 6 7 7 7 7 7 7 3 7
3 3 3 3 3 3 2 2 2 2 2 6 6 6 6 6 6 6
4 4 4 4 4 4 1 1 1 1 1 1 2 2 2 2 2
缺頁中斷次數：14次

㈡ 最佳頁面淘汰演算法是怎樣計算的

<1> 先進先出調度演算法
先進先出調度演算法根據頁面進入內存的時間先後選擇淘汰頁面，先進入內存的頁面先淘汰，後進入內存的後淘汰。本演算法實現時需要將頁面按進入內存的時間先後組成一個隊列，每次調度隊首頁面予以淘汰。
<2>最近最少調度演算法
先進先出調度演算法沒有考慮頁面的使用情況，大多數情況下性能不佳。根據程序執行的局部性特點，程序一旦訪問了某些代碼和數據，則在一段時間內會經旅旅常訪問他們，因此最近最少用調度在選擇淘汰頁面時會考慮頁面最近的使用，總是選擇在最近一段時間以來最少使用的頁面予以淘汰。演算法實現時需要為每個頁面設置數據結構記錄頁面自上次訪問以來所經歷的時間。
<3>最近最不常用調度演算法
由於程序設計中經常使用循環結構，根據程序執行的局部性特點，可以設想在一段時間內經常被訪問的代碼和數據在將來也會經常被訪問，顯然這樣的頁面不應該被淘汰。最近最不常用調度演算法啟擾總是根據一段時間內頁面的訪問次數來選擇淘汰頁面，每次淘汰訪問次數最少的頁面。演算法實現時需要為每個頁面設置計數器，記錄訪問次數。計數器由硬體或操作系統自動定時清零。
（2）拆旁凳缺頁調度次數和缺頁中斷率、缺頁置換率計算
缺頁中斷次數是缺頁時發出缺頁中斷的次數。
缺頁中斷率=缺頁中斷次數/總的頁面引用次數*100%
缺頁調度次數是調入新頁時需要進行頁面調度的次數
缺頁置換率=缺頁調度次數/總的頁面引用次數*100%

㈢ 先進先出頁面淘汰演算法

#include<stdio.h>
#include<stdlib.h>
#define max 30
typedef struct{
int visit_number;//要訪問的頁面號
}nu,number[max];
int *memoryblock;//主存中有三個主存塊，可裝三個頁面
void init_memoryblock(int n)//初始化主存塊
{
int i=1;
memoryblock=(int*)malloc(sizeof(int));//分配空間
for(i=1;i<=n;i++)
{
memoryblock[i]=-1;//開始時候沒有頁面進入，初始為-1
}
}
void init_visitpage(number num,int n)//n表示要訪問的頁面的個數
{
int i=0;
int j=3;
printf("輸入要訪問的頁面號: ");
for(i=1;i<=n;i++)
{
scanf("%d",&num[i].visit_number);
}
printf("\n");
}
void FIFO_page_dispatch(number num,int n)//FIFO頁面調度演算法
{
int i,j=3,temp,counter=0;
for(i=1;i<=n;i++)
{
//----------------------------頁面在主存中-------------------------------
for(j=3;j>=1;j--)
{
if(num[i].visit_number==memoryblock[j])//////要訪問的頁面在主存中
{
printf("(%d)頁面在主存塊中，換出和換進都是%d號頁面:\n",i,memoryblock[j]);
}
break;
}
//-----------------------------------------------------------------------
//----------------------------頁面不在主存中-----------------------------
if(num[i].visit_number!=memoryblock[1]&&num[i].visit_number!=memoryblock[2]&&
num[i].visit_number!=memoryblock[3])/////////////[ 1 ]
/*內存中沒有要訪問的頁面，中斷*/
{
if(memoryblock[1]!=-1&&memoryblock[2]!=-1&&memoryblock[3]!=-1)
{
temp=memoryblock[3];
memoryblock[3]=memoryblock[2];
memoryblock[2]=memoryblock[1];
memoryblock[1]=num[i].visit_number;
//---------------------------------
printf("(%d)——頁面發生置換:",i);
printf("換出(%d號)頁面—",temp);
printf("換進(%d)號頁面\n",num[i].visit_number);
counter++;
}
for(j=3;j>=1;j--)//////////////[ 2 ]
{
if(memoryblock[j]==-1)//還有空閑主存塊
{
printf("(%d)有空閑主存塊，%d號頁面直接調入:\n",i,i);
memoryblock[j]=num[i].visit_number;
break;
}

}
//-----------------------------移動主存塊-------------------
}
//------------------------------------------------------------------------
}
printf("\n共產生 %d 次頁面置換:",counter);
}
void main()
{
number num;
int m,n;
printf("輸入要訪問頁面串的個數(<30)和內存塊個數：");
{
scanf("%d%d",&n,&m);
getchar();
}
init_memoryblock(m);//初始化主存塊
init_visitpage(num,n);//輸入要訪問的頁面號順序
FIFO_page_dispatch(num,n);//FIFO調度
printf("\n");
}

㈣ 最佳頁面淘汰演算法是怎樣計算的

1;
50%指令順序執行
2;25%指令均勻散步在前地址部分
3;25%指令均勻散步在後地址部分
題目中選用:命中率=1-頁面失敗次數(只選用2的兄弊冪次)/葉地址流長度
演算法:opt
fifo
rlu(定義)(至少用兩個演算法)程序流程圖開始:產生給定長度符合假定的指令地址流->為散納每一個指令地址羨掘族的成對應的訪問頁號->置初算size=1~8(1,2,4,8)(頁面大上)實存
=4~32(4,8,16,32)->輸入淘汰演算法->A->ALG=FIFO(OR)(LRU)->FIFO->用FIFO計算命中率->用LRU計算命中率->輸出結果->結束演算法定義:理想淘汰演算法--最佳頁面演算法(OPT)
淘汰以後不再需要的或最遠的將來才會用到的頁面
先進先出頁面淘汰演算法(FIFO)
選擇在內存中駐留時間最長的頁並淘汰之
最近最少使用頁面淘汰演算法(LRU)
選擇最後一次訪問時間距離當前時間最長的一頁並淘汰之即淘汰沒有使用的時間最長的頁.

㈤ 儲存管理中,分頁式虛擬儲存管理的頁面淘汰演算法有

儲存管理中，分頁式虛擬儲存管理的頁面淘汰鏈森演算法有先進先出法，最近最少使用頁面陸櫻先淘汰，最優淘汰演算法。最優淘汰演算法(OPT)：系統預測作業今後要訪問的頁面，淘汰頁是將來不被訪問的頁面或者在最長時間早喚叢後才被訪問的頁面。它保證有最少的缺頁率，但它實現困難，只能通過理論分析用來衡量其它演算法的優劣。