原創
上一篇部落格寫了先進先出算法（FIFO）——頁面置換：http://www.cnblogs.com/chiweiming/p/9058438.html
此篇介紹最近最少使用算法（LRU）——頁面置換，與上一篇的代碼大同小異，隻是用了不同的方法從頁面隊列
中選出需要淘汰出的頁面。（題目闡述看我上一篇部落格）
還是辣個栗子：
現記憶體頁面為： 15 31 24 17 18 5 9 26 4 21
部分位址流為： 4 31 24 17 18 26 17 5 5 9 31 18 18 21 15 8
頁面 8 為下一個需要調入進去的頁面，由于記憶體頁面已滿，需要使用LRU調出一個最近未被使用頁面。
尋找淘汰頁面的方式如下：
從頁面 8 往前看，遇到與記憶體頁面中相同的頁面即把它移除（即不淘汰它），等到移除了 max_page-1 個頁面之
後，剩下最後一個未被移除的頁面即是需要淘汰出去的。
在上面例子中，依次将 15 21 18 31 9 5 17 26 24 （已經9個），剩下最後一個 4 即是需要淘汰出去的頁面。
可以用這樣的僞代碼去實作：用一個數組 flag 來備份記憶體頁塊号中的頁面，從 8 往前看，依次将之前的數和數組
裡的數比較，若比對成功，則将數組裡面此位置 -1 ，等到置了 max_page-1 個 -1 後跳出；再從 flag 中篩選出不
是 -1 的值（即要淘汰出的頁面），再拿此值和目前記憶體頁面隊列中的值比較，比對成功則将此頁面調出去，将頁
面 8 調入。
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define max_page 10 //記憶體頁面數
int Page[320]={0}; //虛拟存儲區,存儲320條指令,32個頁面
int Page_flu[320]={0}; //存儲320個頁位址流
int count=0; //計算随機産生的指令條數
double lack_page=0; //記錄缺頁數
int count_page=max_page; //計算隊列空頁面個數
int flag[max_page+1]={0}; //存儲記憶體塊中的頁面号
int ff=0;
struct Memo{ //用結構體存儲記憶體頁面塊
int num; //給每個頁面編号,友善将其從隊列中找到并調出
int a;
struct Memo *next;
};
int Judge_Page(int value){ //輸入指令,傳回指令對面的頁面号
return value/10;
}
int scan_queen(struct Memo *hear,int value){ //value代表頁面号,掃描隊列,缺頁傳回0,否則傳回1
struct Memo *move;
move=hear->next;
while(move!=NULL){
if(move->a==value){
return 1;
}
move=move->next;
}
return 0;
}
void print(struct Memo *hear){ //輸出記憶體頁面
struct Memo *move;
move=hear->next;
printf("目前頁面隊列為： ");
while(move!=NULL){
printf("%d ",move->a);
move=move->next;
}
printf("
");
}
void insert(struct Memo *hear,int value,int ZL,int x){ //将頁面value調入記憶體,ZL為對應指令,x為頁面value在頁位址流中的序号
if(count_page>=1){ //記憶體頁面空間充足
struct Memo *move;
move=hear->next;
while(move->a!=-1){
move=move->next;
}
move->a=value; //将頁面調入
count_page--;
printf("頁面 %d 被調入————對應指令為: %d
",value,ZL);
}
else{ //記憶體空間不足，使用LRU選出需調出的頁面後，将頁面value後調入
struct Memo *move;
move=hear->next;
int i=0;
for(i=1;i<=max_page;i++){
flag[i]=move->a; //将記憶體塊中的頁面号放入flag備份
move=move->next;
}
int t=0;
for(t=x-1;t>=0;t--){ //循環結束後flag裡面隻有一個不為0,把此頁面調出即可
for(i=max_page;i>=1;i--){
if(Page_flu[t]==flag[i]){
flag[i]=-1;
ff++;
break;
}
}
if(ff==max_page-1){
break;
}
}
for(i=1;i<=max_page;i++){ //選出被淘汰出的頁面号
if(flag[i]!=-1){
ff=flag[i]; //備份要淘汰出的頁面号
break;
}
}
move=hear->next;
while(move!=NULL){
if(move->a==ff){
int j=0;
printf("前20個位址流為：");
for(j=x-20;j<=x-1;j++){
printf("%d ",Page_flu[j]);
}
printf("
");
printf("頁面 %d 被調出,頁面 %d 被調入----指令為：%d
",ff,value,ZL);
move->a=value; //将頁面插入
break;
}
move=move->next;
}
}
ff=0;
print(hear); //調入後輸出記憶體隊列
}
void LRU(struct Memo *hear){
int i=0;
for(i=0;i<=319;i++){ //循環掃描頁面
if( scan_queen(hear,Page_flu[i])==0){ //判斷是否缺頁
lack_page++;
insert(hear,Page_flu[i],Page[i],i); //缺頁将頁面調入記憶體
}
else{ //不缺頁
printf("指令 %d 對應頁面 %d 已在記憶體
",Page[i],Page_flu[i]);
}
//不缺頁無需操作
}
}
void Pro_Page(){ //形成頁位址流函數
int m=0; //在[0,319]的指令位址之間随機選取一起點m
m=rand()%320;
Page[count]=m;
count++;
if(count==320){
return;
}
int m_=0; //在前位址[0,m+1]中随機選取一條指令并執行
m_=rand()%(m+1);
Page[count]=m_;
count++;
if(count==320){
return;
}
Page[count]=m_+1;
count++;
if(count==320){
return;
}
int m__=0;
m__=(m_+2)+rand()%( 319-(m_+2)+1 ); //在後位址[m_+2,319]的指令位址之間随機選取一條指令并執行
Page[count]=m__;
count++;
if(count==320){
return;
}
Pro_Page();
}
void Flu(){ //将指令轉換為頁位址流
int i=0;
for(i=0;i<=319;i++){
Page_flu[i]=Judge_Page( Page[i] );
}
}
int main(){
struct Memo Stu[max_page+1];
struct Memo *hear;
hear=&Stu[0];
//*************************************
int i=0;
for(i=0;i<=max_page;i++){ //形成記憶體頁面隊列
if(i==max_page){
Stu[i].a=-1;
Stu[i].next=NULL;
Stu[i].num=i;
break;
}
Stu[i].next=&Stu[i+1];
Stu[i].a=-1;
Stu[i].num=i;
}
//*************************************
srand(time(0)); //放在Pro_Page函數外面
Pro_Page(); //形成頁位址流
Flu(); //形成頁位址流
/*
printf("頁位址流：
");
for(i=0;i<=319;i++){ //輸出頁位址流
printf("%d ",Page[i]);
if(i%3==0 && i!=0){
printf("
");
}
}
printf("
");
*/
//*************************************
LRU(hear);
printf("缺頁次數為： %0.0lf
",lack_page);
printf("命中率為：%lf
",1-lack_page/320);
return 0;
} （部分結果截圖）
08:31:06
2018-05-22