C语言实现页面置换先进先出算法（FIFO）

2023-07-07 16:06:03 80

本文实例为大家分享了C语言实现页面置换算法的具体代码，供大家参考，具体内容如下

一、设计目的

加深对请求页式存储管理实现原理的理解，掌握页面置换算法中的先进先出算法。

二、设计内容

设计一个程序，有一个虚拟存储区和内存工作区，实现下述三种算法中的任意两种，计算访问命中率（命中率=1-页面失效次数/页地址流长度）。附加要求：能够显示页面置换过程。

该系统页地址流长度为320，页面失效次数为每次访问相应指令时，该指令对应的页不在内存的次数。
程序首先用srand()和rand()函数分别进行初始化、随机数定义和产生指令序列，然后将指令序列变换成相应的页地址流，并针对不同的算法计算出相应的命中率。

通过随机数产生一个指令序列。共320条指令，指令的地址按下述原则生成：

（1）50%的指令是顺序执行的。
（2）25%的指令是均匀分布在前地址部分。
（3）25%的指令是均匀分布在后地址部分。

具体的实施方法如下：

在【0，319】的指令地址之间随机选取一起点m。
顺序执行一条指令，即执行地址为m+1的指令。
在前地址【0,m+1】中随机选取一条指令并执行，该指令的地址为m'。
顺序执行一条指令，其地址为m'+1。
在后地址【m'+2,319】中随机选取一条指令并执行。
重复步骤（1）-（5），直到320次指令。
将指令序列变换为页地址流。

设：

页面大小为1KB。
用户内存容量4页到32页。
用户虚存容量为32KB。
在用户虚存中，按每K存放10条指令虚存地址，即320条指令在虚存中的存放方式为：
第0条～9条指令为第0页（对应虚存地址为【0，9】）。
第10条～19条指令为第1页（对应虚存地址为【10，19】）。
……
第310条～319条指令为第31页（对应虚拟地址为【310，319】）。
按以上方式，用户指令可组成32页。
计算每种算法在不同内存容量下的命中率。

三、程序结构

首先，用srand()和rand()函数分别进行初始化、随机数定义和产生指令序列；
接着，将指令序列变换成相应的页地址流；
然后，并针先进先出算法计算出相应的命中率和输出页面置换过程。

源程序：

#include
#include
#defineN320
intnum[N];//存放随机数
intpage[N];//存放页地址流
intmc[33];//memorycapacity内存容量，并初始化为0

voidrandomnumber()//randomnumber随机数程序第一步，产生320个指令序列
{
intpc;
intflag=0;
scanf("%d",&pc);
printf("\n在0-319之间产生的320个随机数如下:\n");
for(inti=0;i<320;i++)
{
num[i]=pc;
if(flag%2==0)pc=++pc%320;//flag=0||250%的指令是顺序执行的
if(flag==1)pc=rand()%(pc-1);//flag=125%的指令是均匀分布在前地址部分
if(flag==3)pc=pc+1+(rand()%(320-(pc+1)));//flag=325%的指令是均匀分布在后地址部分
flag=++flag%4;
printf("%3d",num[i]);
if((i+1)%10==0)printf("\n");//每行输出10个数
}
}

voidpageaddress()//pageaddress页地址程序第二步，将指令序列变换为页地址流
{
for(inti=0;i<320;i++)
{
printf("%3d",page[i]=num[i]/10);
if((i+1)%10==0)printf("\n");//每行输出10个数
}
}

intFIFO(intcapacity)
{
intj,x,y,m;
intsum=0;//mc中分配的个数
intexist=0;//命中次数
intflag;//标志是否命中flag=0没命中flag=1命中
intep=1;//eliminationposition淘汰位置
mc[1]=page[0];
printf("%2d加入\t",page[0]);
for(m=1;m<=capacity;m++)//输出当前内存块的存储情况
printf("%2d",mc[m]);
printf("\n");
sum+=1;
for(j=1;j<320;j++)
{
flag=0;
for(y=1;y<=sum;y++)//判断这个页地址流是否命中
if(mc[y]==page[j]){
exist++;
flag=1;
printf("%2d命中\t",page[j]);
for(m=1;m<=capacity;m++)//输出当前内存块的存储情况
printf("%2d",mc[m]);
printf("\n");
break;}
//没命中
if(flag==0)
{
if(sum=capacity)
{
intt=mc[ep];
mc[ep]=page[j];
printf("%2d置换%2d\t",page[j],t);
for(m=1;m<=capacity;m++)//输出当前内存块的存储情况
printf("%2d",mc[m]);
printf("\n");
ep+=1;
if(ep==capacity+1)ep=1;
}
}
}
printf("\nexist=%d\n命中率=%lf",exist,exist/320.0);
}
intmain()
{
intcapacity;//内存块数
printf("请输入第一条指令号(0~319):");
randomnumber();
printf("\n指令序列对应的页地址流:\n");
pageaddress();
printf("\n\n\n\t\t先进先出算法(FIFO):\n\n");
printf("请输入内存块数（4-32）：");
scanf("%d",&capacity);
for(inti=1;i<=32;i++)//给数组赋初值
mc[i]=-1;
FIFO(capacity);
return0;
}

以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持毛票票。

C语言实现页面置换 先进先出算法（FIFO）

一、设计目的

二、设计内容

三、程序结构

热门推荐

随机推荐

C语言实现页面置换先进先出算法（FIFO）