LRU算法实现

LRU算法实现

/*++

Copyright (c) 2007 YourCompany

Module Name:

    http://blog.csdn.net/wangjiaoni/archive/2007/06/18/1656000.aspx

Abstract:

 LRU置换算法是选择Cache中最近最久未使用的页面予以置换。该算法赋予每个页面一个
 访问字段，用来记录一个页面自上次被访问以来经历的时间T，当须淘汰一个页面 时，
 选择现有页面中T值最大的，即最近最久没有访问的页面。这是一个比较合理的置换算法。

Author:

    YourName (YourEmail) 2007-06-12

Revision History:

--*/
/**///////////////////////////////////////////////////////////////

#include



//#define MAX_LEN  20
//#define MAX  5
#define true 1
#define false 0

//定义全局变量
typedef struct{
        int state;        //块状态true满，false为空
        int value;        //块内的页面号
        int count;         //块计数器标志块据现在的时间   
    }Cache;
Cache cache[]{{false,-1,0},      //初始化块信息
                {false,-1,0},
                {false,-1,0},
                {false,-1,0}};   //cache中有四块
   
int walk_sort[]={1,1,2,4,3,5,2,1,6,7,1,3};  //页面访问序列

int m=4;  //cache 块的个数
int n=12;  //访问序列的长度
//int n=strlen(walk_sort);  //页面置换访问序列的个数??????? strlen 用法??????????????


/**///////////////////////////////////////////////////////////////////////
void delay(); //声明

// cache更新算法,LRU
void up_cache(Cache cache[],int walk_sort[])
{
    int i=0;  //i为访问序列数组的下标
    int x;
    int k;
    int kk;
    //n=strlen(walk_sort);    //??????????  strlen 和数组的类型有关吗？
    while(i    {
        int j=0;  //J为cache块的下标
        //满么?
        while(j        {
            if((cache[j].state==false)&&(walk_sort[i]!=cache[j].value))  //装入一块
            {
                cout<<"cache有空闲块,不考虑是否要置换."<                cout<                cache[j].value=walk_sort[i++];
                cache[j].state=true;
                cache[j].count=0;
                int kk=0;
               
           
                for (x=0;x                cout<<"cache块"<                cout<               
                //更新其它cache块没使用时间
                while(kk                {
                    if(kk!=j&&cache[kk].value!=(-1))
                    cache[kk].count++;
                    kk++;
                }
                delay();
                break;
            }
           
          
            if(cache[j].value==walk_sort[i])   //命中
            {
                cout<                cout<                for (x=0;x                cout<<"cache块"<                cout<                int kk=0;
                i++;
                cache[j].count=0;
                //更新其它cache块没使用时间
                while(kk                    {
                        if(kk!=j&&cache[kk].value!=(-1))
                        cache[kk].count++;
                        kk++;
                    }
            }
           
            j++;  //块下标加一
        }
       
        if(j==m)   //考虑cache块已经满的情况
        {
            cout<<"cache已经满了,考虑是否置换."<            cout<            int k=0; //块下标
            while(k            {
                if(cache[k].value==walk_sort[i])
                {
                    cout<                    cout<                    for (x=0;x                    cout<<"cache块"<                    i++;
                    cache[k].count=0;
                    int kk=0;
                    //更新其它cache块没使用时间
                    while(kk                    {
                        if(kk!=k)
                        cache[kk].count++;
                        kk++;
                    }
                    break;
                }
                k++;
            }
           
            if(k==m)//cache满且没有命中的情况，考虑置换那一块.
            {
                int ii=0;
                int t=0;//要替换的cache块号.
                int max=cache[ii].count;
                ii++;
                while(ii                {
                    if(cache[ii].count>max)
                    {
                        max=cache[ii].count;
                        t=ii;
                    }
                    ii++;
                }
                //置换
                cout<                cache[t].value=walk_sort[i++];
                cache[t].count=0;
                for (x=0;x                cout<<"cache块"<                int kk=0;
                //更新其它cache块没使用时间
                while(kk                    {
                        if(kk!=t)
                        cache[kk].count++;
                        kk++;
                    }
                delay();
            }
        }
    }
}

void delay()
{
    int i;
    for(i=0;i<100;i++)
    ;
}


void main(int argc, char* argv[])
{
    cout<<"Cache更新LRU置换算法"<    up_cache(cache,walk_sort);
}