LRU算法 C语言实现以及时间戳优化

• C语言实现LRU算法以及采用记录时间戳的方法进行优化

一般遍历方法

基本思想

遍历将要存入页表的页号，同时判断该页号是否在页表中且页表当前是满状态还是空状态，如果不在页表中且页表有空位，则存入空位；

如果在页表中则跳过本次循环；如果页表满且不在页表中，则将页表维护数据删除，其他数据依次后挪，将该页号放在数组头部；

同时，页表满情况下如果遇到已存在的页号，则把该页号提前到table表的首位。

代码

#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#define n 4
void shed(int *t,int num){
    int i;
    for(i=n-1;i>0;i--){
        t[i] = t[i-1];
    }
    t[0] = num;
}
void fun(int *t,int nn){
    int i,j,tine;
    tine = t[nn];
    // table长度等于2或3且只有两个数
    if(((n==3&&(t[n-3]==-1))||(n==2))&&(t[n-1]!=-1)&&(t[n-2]!=-1)){
        t[n-1] = t[n-2];
        t[n-2] = tine;
    }
    else{  // 长度足够
        for(i=n-1;i>-1;i--){  // 检测是否为满
            if(t[i]==-1)  // 防止数组不满如-1 3 1 2
                break;     // i = 0, nn =2
        }  // i最小-1
        if(t[n-1]==t[nn]){ // 满，数组尾，调动数组首
            for(j=n-1;j>i;j--){  //-1 -1 3 1
                t[j] = t[j-1];
            }
        }
        else{
            // 此时，不在数组首尾且长度大于2
            for(j=nn;j>i;j--){  // -1 -1 3 2
                t[j] = t[j-1];
            }
        }
        t[i+1] = tine;
    }
}
int pd(int *t,int nn){ //判断是否在数组中
    int i = 0,j;
    for(;i<n;i++){
        if(t[i]==nn){
            if((t[n-1]!=-1)&&(t[n-2]==-1)){
                return 0;  // 存在数组中且只有一个数
            }
            else if((i!=0)&&(t[i-1] == -1)){ // 在表中,未满状态，且在数组首(相对),说明最近使用，不调整
                return 0;
            }
            else if(t[0] == nn){ // 绝对满，数组首，不调整
                return 0;
            }
            else{  // 复杂情况，多位数
                fun(t,i);
                return 0;
            }
        }
    }
    return 1;  // 继续
}
int null(int *s){ // 数组是否满状态
    int i = n-1;
    for(;i>=0;i--){
        if(s[i]==-1){
            return i;  // 存在空位立刻返回空位位置
        }
    }
    return -n;  // 满状态码 -n
}
int main(){
    if(n<1){
        printf("table表设置错误\n");
        system("pause");
        exit(0);
    }
    int num,i,j=0,*arr; // 为输入whlie必须指定值
    int table[n];  // 页表
    for(i=0;i<n;i++){  // 置-1
        table[i]=-1;
    }
    //while(1){
        printf("输入进程数量");
        scanf("%d",&num);
        arr=(int*)calloc(num,sizeof(int)); //正常存储

        for(i=0;i<num;i++){  // 输入页号
            scanf("%d",&arr[i]);
        }

        if(n==1){
            printf("内容为：%d\n",arr[num-1]);
            system("pause");
            exit(0);
        }

        for(i=0;i<num;i++){ // 处理逻辑
            if(pd(table, arr[i])){ //是否在数组中
                int status = null(table);  // 判断空，返回空位值位置
                if(status!=-n){  // 存在空位，记录队列值
                    if(status==(n-1)){  // 首位
                        table[n-1] = arr[i];
                    }
                    else{  // 其他位置
                        table[status] = arr[i];
                    }
                }else{  // 已满，栈思想
                    // 压入栈底（数组首）,挤掉栈首(数组尾)
                    shed(table,arr[i]);
                }
            }
        }
        printf("表内目前存储的页号为(无书写逻辑顺序，需要自行调整)：\n");
        for(i=0;i<n;i++){
            if(table[i]!=-1)
                printf("%d ",table[i]);
        }
        //system("pause");
        //system("cls");
    //}
    return 0;
}

优化办法——时间戳

基本思想

从第一个页号存入页表开始记录时间戳，初始值为1，每次存入或置换均将页表内其他页号时间戳加一。

若新页号已存在页表中，则将该页号的时间戳置为1；若发生置换，其他页号时间戳加1，该页号时间戳置1。

而确定置换的位置只需要找到时间戳最大的那个就可以了。

代码

#include <stdio.h>
#include <stdlib.h>
#include<stdbool.h>
#define t_len 4
// 空状态
bool status = false;

int null(int (*s)[t_len])  // 数组是否满状态
{
    int i = 0;
    for(i=0; i<t_len; i++)
        printf("%d ",s[0][i]);
    printf("\n");

    for(i=0; i<t_len; i++)
    {
        if(s[0][i]==0)
        {
            return i;  // 存在空位立刻返回空位位置
        }
    }
}

int pd(int (*a)[t_len],int nn)
{
    int j;
    for(j=0; j<t_len; j++)
    {
        if(nn==a[0][j])
        {
            a[1][j] == 1;
            return 1;  // 时间戳置为1，同时结束
        }
    }
    return 0;
}

void add(int (*a)[t_len],int sta,int fla)
{
    int j;
    if(fla>0)
    {
        for(j=0; j<sta; j++)
            a[1][j]++;
    }
    else
    {
        for(j=0; j<sta; j++)
        {
            if(j==fla)
                continue;
            a[1][j]++;
        }
    }
}

int main()
{
    int len = 0,max=0; // max是用来存下标的
    int i,j;
    printf("请输入, 以-1结束: ");
    /* 动态输入 */
    int *arr = (int*)malloc(sizeof(int)*1);
    while(1)
    {
        scanf("%d",arr+len);
        if(*(arr+len)==-1)
            break;
        len++;
        arr = realloc(arr,sizeof(int)*(len+1)); //拓展长度，注意空间不连续
    }

    int table[2][t_len];
    for(i=0; i<2; i++)
        for(j=0; j<t_len; j++)
            table[i][j]=0;

    table[0][0] = arr[0];
    table[1][0] = 1;
    for(i=1; i<len; i++)
    {
        if(pd(table,arr[i]))  // 存在
        {
            add(table,t_len,i);
            printf("%d存在table表中\n");
            continue;
        }
        else  // 不存在
        {
            if(!status)  // 空状态
            {
                int sta = null(table); // 寻找空位,分支
                if(sta == t_len-1)
                    status = true; // 标记满状态
                table[0][sta]=arr[i];  // 存入
                table[1][sta]=1;       // 时间戳置为1
                printf("找到空位%d, 将%d存入该位置\n",sta,arr[i]);
                //其他加时
                add(table,sta,-1);
            }
            else   // 满状态
            {
                //搜索最大时间戳替换，同时增加其他时间戳
                for(j=0; j<t_len; j++)
                {
                    if(table[0][j]>max)
                        max=j;
                }
                printf("找到最远未使用%d, 位置在%d, 使用%d替换\n",table[0][max],max,arr[i]);
                table[0][max] = arr[i];
                table[1][max] = 1;
                add(table,t_len,max);
            }

        }
    }

    printf("\n开始输出：\n");
    for(i=0; i<t_len; i++)
        printf("%d ",table[0][i]);

    return 0;
}