使用C语言编程模拟实现先进先出算法(FIFO)以及最近最久未使用页面置换算法（LRU）带注释

港控/mmm° 2024-02-17 10:48 19阅读 0赞

两种算法的基本原理：

（1）先进先出算法(FIFO)当要进行分页替换时，就把队列最前端的分页换出，再把要调入的分页放到队列的末端。使用链表将所有在内存的页面按照进入时间的早晚链接起来，然后每次置换链表头上的页面就行了,新加进来的页面则挂在链表的末端。

（2）最近最久未使用算法（LRU）选择最近最久未使用的页面予以淘汰。利用页表中的访问字段，记录页面自上次被访问以来所经历的时间t，需要淘汰页面时，选择在内存页面中t值最大的，即最近最久未使用的页面予以淘汰。

先进先出算法FIFO的代码实现：

#include <stdio.h>
    #include <stdlib.h>
    void sort(int a[3],int t)
     //输入t（即将进入内存的进程）顶替内存的第一个页面
    {
        a[0]=a[1];
        a[1]=a[2];
        a[2]=t;//全部前移 即a[0]页面被置换
    }
    int IN(int a[3],int t) //找出即将进来的进程是否在内存的三个页面中
    {
        int i;
        int flag=0;//初始值表示不存在内存中
        for(i=0; i<3; i++) //进行循环
        {
            if(a[i]==t)//逐一比较
            {
                flag=1;//表示比对成功即已经存在内存中
                break;//跳出for循环
            }
        }
        return flag;//返回比较结果
    }
    void print(int a[3],int t)//内存中的数组a[3] 即将进入内存的页面b
    {
        if(IN(a,t)==0)
        {
            //调用IN函数判断即将进入内存的进程是否已经存在
            sort(a,t);
            //flag==0表示不存在则调用sort函数进行排序
        }
        printf("现在内存中的3个页面为：%d %d %d\n",a[0],a[1],a[2]);
    }
    
    int main()
    {
        int i;
        int a[3],b[100],n;
        //设有内存中有3个页面a[0],a[1],a[2]
        //b是即将进入内存的页面，
        //n是即将进入内存页面的数量
        for(i=0; i<3; i++)
            //现将内存中的三个页面输入
        {
            printf("请输入第%d个页面:",i+1);
            scanf("%d",&a[i]);
        }
        printf("现在内存中的3个页面为：%d %d %d\n",a[0],a[1],a[2]);
        //输出内存中现存页面
        printf("请输入即将进入内存的页面数:");
        scanf("%d",&n);
        for(i=0; i<n; i++)//对要访问的页面进行循环
        {
            printf("请输入要访问的页面；");
            scanf("%d",&b[i]);
            print(a,b[i]);//调用print函数
        }
    }

流程图

![e7c146d1ac9949ed9c74e32f4f3ee5f6.png][]

运行结果图：

![e6005338c9e9acc71787317fefe09177.png][]

最近最久未使用算法（LRU）代码实现：

#include <stdio.h>
    #include <stdlib.h>
    struct P//定义页面结构体
    {
        int time;//已经待的时间
        //页面每被访问一次 其等待时间置0 其他页面等待时间+1
        int number;//页面序号
    };
    int long_max(struct P a[3]) //寻找在内存中时间最长的页面，并对其time进行修改
    {
        int index=0;
        int min_time=a[0].time;//将内存第一个页面的等待时间设为初始值
        //既为内存中等待时间的最大值(页面b进入之前)
        int i;
        for(i=1;i<3;i++) //找出最大的time以及对应的页面
        {
            if(a[i].time>min_time)//将页面的等待时间分别与初始值进行比较
            {
                min_time=a[i].time;//确保初始值最大
                index=i;//得出等待时间最长的页面序号i
            }
        }
        if(index==0) //第1个页面等待时间最长
        {
            a[1].time++;//其余页面等待时间+1
            a[2].time++;
        }
        if(index==1) //第2个页面等待时间最长
        {
            a[0].time++;//其余页面等待时间+1
            a[2].time++;
        }
        if(index==2) //第3个页面等待时间最长
        {
            a[1].time++;//其余页面等待时间+1
            a[0].time++;
        }
        a[index].time=0;//将被顶替出的页面时间置位0，因为其是刚进来
        return index;
    }
    
    int IN(struct P a[3],int t) //找出即将进入的页面b是否在内存中
    {
        int flag=3;//flag为是否存在相同的页面,如果为3说明不在
        int i;
        for(i=0; i<3; i++)//进行循环对比
        {
            if(a[i].number==t)//若存在则找出对应页面i
            {
                flag=i;//内存中存在b页面
                break;//跳出循环
            }
        }
        return flag;//返回比较结果
    }
    void print(struct P a[3],int t)//内存中的数组a[3] 即将进入内存的页面b
    {
        int index,m;
        index=IN(a,t);//判断是页面b否在里面 若存在返回对应页面
        if(index!=3) //如果内存中存在b页面
        {
            a[index].time=0;//将该页面的已等待时间置0
            if(index==0)//第一个页面被访问
            {
                a[1].time++;//其余等待时间均+1
                a[2].time++;
            }
            if(index==1)//第二个页面被访问
            {
                a[0].time++;//其余等待时间均+1
                a[2].time++;
            }
            if(index==2)//第三个页面被访问
            {
                a[1].time++;//其余等待时间均+1
                a[0].time++;
            }
        }
        else //如果b不在，则页面序号需要变化
        {
            m=long_max(a);//找出需要变化页面的索引
            a[m].number=t;//页面a[m]被页面b置换
        }
        printf("现在内存的三个页面为%d %d %d\n",a[0].number,a[1].number,a[2].number);
    }
    int main()
    {
        struct P a[3];//内存中的三个页面结构体
        struct P b[100];//即将被调入内存的页面b的结构体
        int n,i;
        for(i=0; i<3; i++)//进行循环输入内存中的3个页面
        {
            printf("请输入第%d个页面：",i+1);
            scanf("%d",&a[i].number);
            a[i].time=3-i;//即前三个时间分别设为3,2,1
        }
        printf("现在内存的三个页面为%d %d %d\n",a[0].number,a[1].number,a[2].number);
        //对现存页面进行输出
        printf("请输入即将进入内存的页面数目：");
        scanf("%d",&n);
        for(i=0; i<n; i++)//对要访问的页面b进行循环
        {
            printf("请输入要访问的页面序号：");
            scanf("%d",&b[i].number);
            print(a,b[i].number);//调用print函数
        }
    }

流程图

![f57344029d1146faa6292774e86bcb09.png][]

运行结果图：

![43ee2562d3cf31d317a6d92bad3059f2.png][]

[e7c146d1ac9949ed9c74e32f4f3ee5f6.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/62dd9a5d93964d919d614487400fb9b4.png
[e6005338c9e9acc71787317fefe09177.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/ff97bd31c6cd4b3f83588935f6065f29.png
[f57344029d1146faa6292774e86bcb09.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/b51ae2f5a9534618a5e7f79b491a7048.png
[43ee2562d3cf31d317a6d92bad3059f2.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/02/06/2c4958ba05f844efbd761e37c05f634a.png