C++編寫的頁面淘汰算法OPT
C++編寫的頁面淘汰算法OPT
//OPT
/算法思想：1.求出當前頁架中那個是可以置換的，這就要求分析匹配當前頁架中的頁面和訪問序列，
看訪問序列中接下來頁面中最近訪問的位置是哪，然后比較大小。/
include<iostream>
include<iomanip>
using namespace std;
void discard(int Array[][19],int page[],int pagenumber[],int max);//置換頁面函數
int OPT(int pagenumber[],int order);//判斷當前頁架有沒有當前訪問頁面
int selectPage(int page[],int pagenumber[],int now,int max);//選擇可置換的頁面
int main()
{
int Array[4][19];//用來存放頁面訪問的詳細信息
int page[19] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0};//頁面訪問次序數組
int pagenumber[3] = {-1,-1,-1};//頁架
int max = 19;//頁面的數量
cout<<"頁面訪問序列如下："<<endl;
for(int i = 0;i < 19;i++){
Array[3][i] = -1;//將頁面是否中斷全部設置成缺頁中斷
cout<<setw(3)<<page[i];
}
discard( Array,page,pagenumber,max);
cout<<endl;
cout<<endl;
//輸出頁面訪問詳細過程
cout<<"輸出結果如下表（-2）代表沒有缺頁中斷！"<<endl;
int LackPageNumber = 0;
for(int j = 0; j < 4;j++){
for(int k = 0; k < 19;k++){
cout<<setw(3)<<Array[j][k];
if(j == 3){
if(Array[j][k] != -2)
LackPageNumber++;
}
}
cout<<endl;
}
cout<<"缺頁次數："<<LackPageNumber<<endl<<endl;
return 0;
}
void discard(int Array[][19],int page[],int pagenumber[],int max)//置換頁面函數
{
for(int i = 0;i < max;i++){
if(i<3){
pagenumber[2] = pagenumber[1];
pagenumber[1] = pagenumber[0];
pagenumber[0] = page[i];
Array[0][i] = pagenumber[0];
Array[1][i] = pagenumber[1];
Array[2][i] = pagenumber[2];
Array[3][i] = -1;//表示缺頁
}else{
if(OPT(pagenumber,page[i])>-1){
Array[0][i] = pagenumber[0];
Array[1][i] = pagenumber[1];
Array[2][i] = pagenumber[2];
Array[3][i] = -2;//表示非缺頁
}else
{//選擇最遠使用的頁面，將這個頁面置換掉
pagenumber[selectPage(page,pagenumber, i,max)] = page[i];
Array[0][i] = pagenumber[0];
Array[1][i] = pagenumber[1];
Array[2][i] = pagenumber[2];
Array[3][i] = -1;//表示缺頁
}
}
}
}
int OPT(int pagenumber[],int order)
{//判斷當前訪問的頁面是否在頁架中
if(pagenumber[0] == order)
return 0;
else if(pagenumber[1] == order)
return 1;
else if(pagenumber[2] == order)
return 2;
else
return -1;
}
int selectPage(int page[],int pagenumber[],int now,int max)
{//選擇可置換的頁面
int aay[3] = {-1,-1,-1};
//存放 pagenumber[]中頁面最近一次使用的位置，用來判斷哪個頁面是最佳置換的頁面
//（這個數組設置的非常好，應為必須每次都應重算頁架中頁面下次下次訪問的位置，在這定義并初始化）
for(int i = now;i <max;i++){
//判斷是從當前位置往后找，所以其實位置就是當前位置
if(pagenumber[0] == page[i]){
aay[0] = i;
break;
}
}
for(int j = now;j <max;j++){
if(pagenumber[1] == page[j]){
aay[1] = j;
break;
}
}
for(int k = now;k <max;k++){
if(pagenumber[2] == page[k]){
aay[2] = k;
break;
}
}
/*這里最重要，有了這個可以簡化discard函數，可以去掉if(i <3)這個條件，
如果aay的值是-1，則表明接下來的訪問序列中沒有頁架中當前的頁面，所以可以直接結束后面的判斷，返回這個位置
*/
if(aay[0] == -1)
return 0;
else if(aay[1] == -1)
return 1;
else if(aay[2] == -1)
return 2;
/*都不等于-1的時候就要判斷哪個的下次訪問位置最遠，就將這個序列置換
*/
int tmp = aay[0],lo=0;
for(int t = 1;t < 3;t++){
if(tmp <aay[t]){
tmp = aay[t];
lo = t;
}
}
return lo;
}</pre>
//OPT
/算法思想：1.求出當前頁架中那個是可以置換的，這就要求分析匹配當前頁架中的頁面和訪問序列，
看訪問序列中接下來頁面中最近訪問的位置是哪，然后比較大小。/
include<iostream>
include<iomanip>
using namespace std;
void discard(int Array[][19],int page[],int pagenumber[],int max);//置換頁面函數
int OPT(int pagenumber[],int order);//判斷當前頁架有沒有當前訪問頁面
int selectPage(int page[],int pagenumber[],int now,int max);//選擇可置換的頁面
int main()
{
int Array[4][19];//用來存放頁面訪問的詳細信息
int page[19] = {7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0};//頁面訪問次序數組
int pagenumber[3] = {-1,-1,-1};//頁架
int max = 19;//頁面的數量
cout<<"頁面訪問序列如下："<<endl;
for(int i = 0;i < 19;i++){
Array[3][i] = -1;//將頁面是否中斷全部設置成缺頁中斷
cout<<setw(3)<<page[i];
}
discard( Array,page,pagenumber,max);
cout<<endl;
cout<<endl;
//輸出頁面訪問詳細過程
cout<<"輸出結果如下表（-2）代表沒有缺頁中斷！"<<endl;
int LackPageNumber = 0;
for(int j = 0; j < 4;j++){
for(int k = 0; k < 19;k++){
cout<<setw(3)<<Array[j][k];
if(j == 3){
if(Array[j][k] != -2)
LackPageNumber++;
}
}
cout<<endl;
}
cout<<"缺頁次數："<<LackPageNumber<<endl<<endl;
return 0;
}
void discard(int Array[][19],int page[],int pagenumber[],int max)//置換頁面函數
{
for(int i = 0;i < max;i++){
if(i<3){
pagenumber[2] = pagenumber[1];
pagenumber[1] = pagenumber[0];
pagenumber[0] = page[i];
Array[0][i] = pagenumber[0];
Array[1][i] = pagenumber[1];
Array[2][i] = pagenumber[2];
Array[3][i] = -1;//表示缺頁
}else{
if(OPT(pagenumber,page[i])>-1){
Array[0][i] = pagenumber[0];
Array[1][i] = pagenumber[1];
Array[2][i] = pagenumber[2];
Array[3][i] = -2;//表示非缺頁
}else
{//選擇最遠使用的頁面，將這個頁面置換掉
pagenumber[selectPage(page,pagenumber, i,max)] = page[i];
Array[0][i] = pagenumber[0];
Array[1][i] = pagenumber[1];
Array[2][i] = pagenumber[2];
Array[3][i] = -1;//表示缺頁
}
}
}
}
int OPT(int pagenumber[],int order)
{//判斷當前訪問的頁面是否在頁架中
if(pagenumber[0] == order)
return 0;
else if(pagenumber[1] == order)
return 1;
else if(pagenumber[2] == order)
return 2;
else
return -1;
}
int selectPage(int page[],int pagenumber[],int now,int max)
{//選擇可置換的頁面
int aay[3] = {-1,-1,-1};
//存放 pagenumber[]中頁面最近一次使用的位置，用來判斷哪個頁面是最佳置換的頁面
//（這個數組設置的非常好，應為必須每次都應重算頁架中頁面下次下次訪問的位置，在這定義并初始化）
for(int i = now;i <max;i++){
//判斷是從當前位置往后找，所以其實位置就是當前位置
if(pagenumber[0] == page[i]){
aay[0] = i;
break;
}
}
for(int j = now;j <max;j++){
if(pagenumber[1] == page[j]){
aay[1] = j;
break;
}
}
for(int k = now;k <max;k++){
if(pagenumber[2] == page[k]){
aay[2] = k;
break;
}
}
/*這里最重要，有了這個可以簡化discard函數，可以去掉if(i <3)這個條件，
如果aay的值是-1，則表明接下來的訪問序列中沒有頁架中當前的頁面，所以可以直接結束后面的判斷，返回這個位置
*/
if(aay[0] == -1)
return 0;
else if(aay[1] == -1)
return 1;
else if(aay[2] == -1)
return 2;
/*都不等于-1的時候就要判斷哪個的下次訪問位置最遠，就將這個序列置換
*/
int tmp = aay[0],lo=0;
for(int t = 1;t < 3;t++){
if(tmp <aay[t]){
tmp = aay[t];
lo = t;
}
}
return lo;
}</pre>