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

 两种算法的基本原理：

（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函数
    }
}

流程图

运行结果图：

最近最久未使用算法（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函数
    }
}

流程图

运行结果图：