C语言操作系统——页面置换算法（FIFO/LRU）

由于本学期学习操作系统所以需要用代码实现一些算法，本人大二由于对C语言掌握的不太好，所以一直逼着自己用C语言写代码，还好写出来了，在这里与大家分享。

首先建立一个工程文件，本人喜欢建立一个头文件，一个功能文件和一个主函数文件。

头文件，page_replace.h

#include
#include


typedef struct Page
{
int num;//固定每一行
int mark;//几次换页未使用的次数
}Page;


void FIFO(int input[],int sum,int count);//先进先出置换算法
void LRU(int input[],int sum,int count);//最久未使用置换算法

功能文件，page_replace.cpp

#include \"page_replace.h\"
#define MAX 20


void FIFO(int input[],int sum,int count)//先进先出置换算法
{
printf(\"\\n____________FIFO算法_____________\\n\");
int sub=0;//substitution置换次数
Page frame[MAX];//页帧（物理块可以放的页数）
for(int i=0;i {
frame[i].num=input[i]; 
        //sub++; 
printf(\"%d\",frame[i].num);
printf(\" | \");
for(int j=0;j<=i;j++)
printf(\"%d \",frame[j].num);
Sleep(500);
printf(\"\\n\");
}
for(i=sum;i {
int j;
for(j=0;j {
if(input[i]==frame[j].num)//在物理块中找到需要的页
{
printf(\"%d\\n\",input[i]);
Sleep(500);
break;
}
}
if(j==sum)//在当前物理块中没有匹配的页
{
sub++;
frame[(sub-1)%sum].num=input[i];//换掉最旧的页
printf(\"%d\",input[i]);
printf(\" | \");
for(int k=0;k printf(\"%d \",frame[k].num);//打印最新的物理块中的页
Sleep(500);
printf(\"\\n\");
}
}
printf(\"FIFO算法页面置换的次数为：%d\\n\\n\",sub);
}


void LRU(int input[],int sum,int count)//最久未使用置换算法
{
printf(\"____________LRU算法_____________\\n\");
int sub=0;
Page frame[MAX];
for(int i=0;i {
frame[i].num=input[i]; 
printf(\"%d\",frame[i].num);
printf(\" | \");
for(int j=0;j<=i;j++)
printf(\"%d \",frame[j].num);
Sleep(500);
printf(\"\\n\");
}
for(i=sum;i {
int j;
for(j=0;j {
if(input[i]==frame[j].num)
{
printf(\"%d\\n\",input[i]);
Sleep(500);
break;
}
}
if(j==sum)//在当前物理块中没有找到合适的页
{
sub++;
for(j=0;j {
frame[j].mark=0;//初始化
for(int k=0;k<=i;k++)//向前遍历，找到最近最少使用的 
{
if(frame[j].num==input[k])
frame[j].mark=k;//会被最近使用的一次给覆盖掉，记录一个页面是第几次换页使用的,k为下标，如果k越小说明最近很少使用
}
}
for(int d=0;d {
int x=0;
for(j=0;j {
if(frame[d].mark<=frame[j].mark)//求最小的数
x++ ;
}
if(x==sum)
{
frame[d].num=input[i];
break;
}


}
printf(\"%d\",input[i]);
printf(\" | \");
for(int k=0;k printf(\"%d \",frame[k].num);
Sleep(500);
printf(\"\\n\");
}
}
printf(\"LRU算法页面置换的次数为：%d\\n\",sub);

}

主函数文件，page_replace_test.cpp

#include \"page_replace.h\"
#define MAX 50


void main()
{
printf(\"_____________页面置换算法______________\\n\");
int sum=0;//物理块数
int input[MAX];//输入的0-9数字串流
char ch;
int flag=1;
int i=0;
printf(\"请输入物理块数（正整数）：\\n\");
scanf(\"%d\",&sum);
printf(\"请输入0-9的数字代表页面号，以#结束：\\n\");
while(flag)
{
scanf(\"%c\",&ch);
if(ch!=\'#\' && ch!=\'\\n\')
{
input[i]=(int)ch-48;
i++;
}
else if(ch==\'#\')
flag=0;
}
int count=i;//记录页面个数
FIFO(input,sum,count);
LRU(input,sum,count);
}

代码到此结束，最后的运行结果是这样子滴：

谢谢大家观看，后续还会有分享。