原创
上一篇博客写了先进先出算法（FIFO）——页面置换：
此篇介绍最近最少使用算法（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#include #include #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("\n");}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 \n",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("\n"); printf("页面 %d 被调出,页面 %d 被调入----指令为：%d \n",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 已在内存\n",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("页地址流：\n"); for(i=0;i<=319;i++){ //输出页地址流 printf("%d ",Page[i]); if(i%3==0 && i!=0){ printf("\n"); } } printf("\n"); */ //************************************* LRU(hear); printf("缺页次数为： %0.0lf\n",lack_page); printf("命中率为：%lf\n",1-lack_page/320); return 0;}
（部分结果截图）
08:31:06
2018-05-22