博客

LRU的简单实现

LRU是Least Recently Used的缩写，即最近最少使用，常用于页面置换算法，是为虚拟页式存储管理服务的。

为了尽量减少与理想算法的差距，产生了各种精妙的算法，最少使用页面置换算法便是其中一个。LRU算法的提出，是基于这样一个事实:在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。反过来说，已经很久没有使用的页面很可能在未来较长的一段时间内不会被用到。这个，就是著名的局部性原理–比内存速度还要快的cache，也是基于同样的原理运行的。因此，我们只需要在每次调换时，找到最近最久未使用的那个页面调出内存。这就是LRU算法的全部内容。

#include<iostream>
#define N 3
using namespace std;
int main()
{
    int ym[]={7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1};
    int lru[N]={1,0,7};
    int len[N]={0,0,0};
    int allchagetimes=0;
     for(int t=0;t<N;t++)
       {
           cout<<lru[t]<<"  ";
       }
       cout<<endl;

   for(int i=3;i<20;i++)
   {
       int flag=0;
       int j=0;
       int sum=0;
       for(;j<N;j++)
       {
           if(ym[i]==lru[j])
           {
               flag=1;
               break;
           }
           else if(ym[i]!=lru[j])
           {
               sum++;
               if(sum==3)
               {
                   flag=0;
                   break;
               }
           }


       }

       if(flag==1)
       {
           int temp=lru[0];
         if(j==0)
         {

         }
         else if(j==1)
         {
            lru[0]=lru[j];

             lru[2]=lru[2];
             lru[1]=temp;
         }

         else if(j==2)
         {
             lru[0]=lru[j];

             lru[2]=lru[1];
             lru[1]=temp;

         }

       }
       else if(flag==0)
       {
           allchagetimes++;
           lru[2]=lru[1];
           lru[1]=lru[0];
           lru[0]=ym[i];


       }

       for(int t=0;t<N;t++)
       {
           cout<<lru[t]<<"  ";
       }
       cout<<endl;
   }

   cout<<"缺页"<<allchagetimes+3 <<"次，置换"<<allchagetimes<<"次"<<endl;

}