前言

LRU算比较经典，而且考的也比较多，LRU算法全称Least Recently Used，译为最近最少使用。用C模拟一下吧。

Buddy算法：操作系统学习之用C语言模拟伙伴(Buddy)算法
FIFO算法：操作系统学习之用C语言模拟FIFO算法
LRU算法：操作系统学习之用C语言模拟LRU算法
Clock算法：操作系统学习之用C语言模拟CLOCK算法
本源代码原创，转载请注明，同时由于本人才疏学浅，刚入门操作系统，如有错误敬请指教
本文原创，创作不易，转载请注明！！！
本文链接
个人博客：https://ronglin.fun/?p=202
PDF链接：见博客网站
CSDN: https://blog.csdn.net/RongLin02/article/details/117632296

算法模拟

教科书原图

算法解释

先来看看课本上的解释。
LRU策略置换内存中最长时间未被引用的页。根据局部性原理，这也是最近最不可能访问到的页。实际上，LRU策略的性能接近于OPT(OPTimal 最佳)策略。这种方法的问题是比较难实现。一种实现方法是给每页添加一个最后一次访问的时间戳，并在每次访问内存时更新这个时间戳。即使有支持这种方案的硬件，开销仍然非常大。另一种方法是维护一个关于访问页的栈，但开销同样很大。 ——操作系统-精髓与设计原理(第九版)P227

代码解释

简单的来说，就是LRU策略很好，但是实现起来比较复杂，我代码用的是添加时间戳的方式。定义了一个结构体，两个属性，一个用来存储数据(data)，另一个就是时间戳(time)。
在处理每一个到来的"进程"时，先判断其是否在队列中，如果在就更新时间戳，如果不在，就置换走时间戳最早的那个进程。

源代码

#include<stdio.h>
#define MAX_NUM 3
#define MAX_NUM_PROC 512


//进程结构体
struct LList
{
    int data;
    int time;
}LRU_list[MAX_NUM];

/*
12
2 3 2 1 5 2 4 5 3 2 5 2
*/

int main()
{
    for(int i=0;i<MAX_NUM;i++)
    {
       LRU_list[i].data = 0;
       LRU_list[i].time = 0;
    }

    int n;
    int a[MAX_NUM_PROC];
    printf("请输入个数:");
    scanf("%d",&n);
    printf("请输入%d个非零数字:\n",n);
    for(int i=0;i<n;i++)
    {
        scanf("%d",&a[i]);
    }

    for(int i=0;i<n;i++)
    {
        //先找原来的队列中是否存在
        int exist =0;
        for(int j=0;j<MAX_NUM;j++)
        {
            if(LRU_list[j].data == a[i])
            {
                exist = 1;
                LRU_list[j].time = i+1;//留下时间戳
                break;
            }
        }
        //不存在
        if(!exist)
        {
            int i_minn=0;
            for(int j=1;j<MAX_NUM;j++)
            {
                if(LRU_list[i_minn].time > LRU_list[j].time)
                {
                    i_minn = j;
                }
            }

            LRU_list[i_minn].data = a[i];
            LRU_list[i_minn].time = i+1;
        }

        printf("本次队列情况:");
        for(int j=0;j<MAX_NUM;j++)
        {
            printf("%d",LRU_list[j].data);
            if(j==MAX_NUM-1)
            {
                if(!exist)
                    printf(" F");
                printf("\n");
            }
            else
            {
                printf(" ; ");
            }
        }
    }
    return 0;
}

输出解释

请输入个数:12
请输入12个非零数字:
2 3 2 1 5 2 4 5 3 2 5 2
本次队列情况:2 ; 0 ; 0 F
本次队列情况:2 ; 3 ; 0 F
本次队列情况:2 ; 3 ; 0
本次队列情况:2 ; 3 ; 1 F
本次队列情况:2 ; 5 ; 1 F
本次队列情况:2 ; 5 ; 1
本次队列情况:2 ; 5 ; 4 F
本次队列情况:2 ; 5 ; 4
本次队列情况:3 ; 5 ; 4 F
本次队列情况:3 ; 5 ; 2 F
本次队列情况:3 ; 5 ; 2
本次队列情况:3 ; 5 ; 2

F表示缺页，为了方便，当询问LRU链表为空时也会被判定为缺页。
可以看到和教科书上的结果相同。
LRU我用的是增加时间戳，用变量i作为时间戳。

总结

LRU算法用C模拟起来比较简单，但是结合起硬件就比较麻烦了，维护其队列开销确实比较大。=w=

1.实验目的
用高级语言模拟页面置换算法LRU，加深对LRU算法的认识。 2.实验要求
用高级语言模拟页面置换算法LRU，加深对LRU算法的认识。
3.实验过程描述
原理（思路）
其基本原理为：当进程在CPU上运行时，如指令中涉及逻辑地址时，操作系统自动根据页表得到页号相关信息。 如果某一个页面被访问了，它很可能还要被访问；相反，如果它长时间不被访问，再最近未来是不大可能被访问的。

4.实验代码

package 实验四;
public class Lru {
    static int[][] LRU=new int[3][2];
    private static int[][] add(int i) {
        int max=-1;
        int index=0;
        if (NoExist(i)==-1){
            for (int j = 0; j < LRU.length ; j++) {
                if (LRU[j][1]>max){
                    index=j;
                    max=LRU[j][1];
                }
            }
            LRU[index]=new int[]{i,-1};
        }else {
            for (int j = 0; j < LRU.length ; j++) {
                if (LRU[j][0]==i){
                    LRU[j][1]=-1;
                    break;
                }
            }

        }
        for (int j = 0; j <LRU.length ; j++) {
            LRU[j][1]++;
        }
        return LRU;
    }

    private static int NoExist(int i) {
        for (int j = 0; j <LRU.length ; j++) {
            if (i==LRU[j][0])return j;
        }
        return -1;
    }
}
public static void main(String[] args) {
        int[] page_table={1,2,1,3,6,1,2,3,1,2,3,4,1,3};
        System.out.println("页号 页号 页号  ");
        for (int i :page_table) {
                LRU=add(i);
            for (int[] J: LRU) {
                System.out.print(J[0]+"   ");
            }
            System.out.println();
        }
    }

5.实验结果

上一篇操作系统 之 银行家算法 （java）

如果本文章对你有用 记得点赞哦 (￣∇￣)

操作系统LRU算法C语言实现

前言
本机为微软Surface pro4，为64位，所用操作系统为Windos 10。本机虚拟机版本为Oracle VM VirtualBox 6.1.8，所用操作系统是使用Ubuntu18.04，。Ubuntu的虚拟硬盘设置为200G，显存为128MB，内存为4G，CPU2个，所用镜像源为清华大学软件镜像源。所使用linux内核为linux-5.11.8。

注意事项
（1）本LRU算法的实现思路是借鉴网上的相关资源，并非原创。
（2）本篇博客代码只实现LRU算法的置换显示，采用了固定化的方式。

LRU算法介绍
LRU算法：是为虚拟页式存储管理服务的，LRU算法的提出，是基于这样一个事实：在前面几条指令中使用频繁的页面很可能在后面的几条指令中频繁使用。

Linux下C语言实现LRU算法的代码
1、使用文件编辑器在主目录下创建一个名为OS3的文件夹。

2、打开Geany程序，然后点击新建按钮，创建一个新文件。
（注：创建完成界面如下）

3、在新建的文件中书写程序。（注：程序如下）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 全局变量
char stack[5] ={0}; //栈
char visit_pages[11] = {'3', '5', '0', '5', '1', '0', '8', '2', '5', '1', '3'}; //访问轨迹

// 打印栈元素
void print_stack()
{
    int m;
    // 打印栈元素
    for (m=0; m<5; m++) {
        if (stack[m] == NULL) {
            printf("  -");
        } else {
            printf("  %c", stack[m]);
        }
    }
    printf("\n\n");
}

//移动栈值
void change_stack(int index, int i)
{
    int temp, k;
    //将栈底元素保存后，依次往前覆盖
    temp = stack[index];
    for (k=index; k<5; k++) { //相等下标值之后，往前覆盖
        if (index != 0) {//只有当栈不满时，可直接跳出循环
            if (stack[k+1] == NULL) {
                break;
            }
        }
        if (k+1 < 5) {
            stack[k] = stack[k+1];
        }
    }
    // 两种不同情况使用不同赋值
    if (index != 0) {
        if (k == 5) {
            k = 4;
        }
        stack[k] = temp; //冒泡到顶部
        stack[k] = visit_pages[i]; //替换顶部值
    } else {
        stack[4] = temp; //冒泡到顶部
        stack[4] = visit_pages[i]; //替换顶部值
    }
}

int main()
{
    int i, j, k;
    int index; //下标
    int temp; //值中间量

    //栈赋值
    for (i=0; i<5; i++) {
        stack[i] = NULL;
    }

    printf("初始值: \n");
    print_stack(); //初始栈打印
    for (i=0; i<strlen(visit_pages); i++) {
        for (j=0; j<5; j++) {
            if (stack[j] == NULL) {
                stack[j] = visit_pages[i];
                break;
            }
            if (stack[j] == visit_pages[i]) {//栈内有访问元素
                if (j+1 < 5 && stack[j+1] == NULL || j == 4) { //访问的元素为顶部元素，且其再顶部元素为NULL，or, 访问元素为栈顶元素，跳出循环
                    break;
                }
                change_stack(j, i); //移动栈值
            } else if (j == 4 && stack[j] != visit_pages[i]) {//栈内无访问元素
                change_stack(0, i); //移动栈值
            }
        }
        printf("---> %c:\n", visit_pages[i]);
        print_stack();
    }

    return 0;
}

4、将程序文件命名lru.c为保存到OS3文件下。（注：如图所示）

LRU算法实现效果如下
1、按如下图示中标明顺序点击按钮执行即可（注：效果图如下）