欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言实现页面置换 先进先出算法(FIFO)

程序员文章站 2022-03-15 09:48:21
本文实例为大家分享了c语言实现页面置换算法的具体代码,供大家参考,具体内容如下一、设计目的加深对请求页式存储管理实现原理的理解,掌握页面置换算法中的先进先出算法。二、设计内容设计一个程序,有一个虚拟存...

本文实例为大家分享了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<stdio.h>
#include<stdlib.h>
#define n 320
int num[n]; //存放随机数 
int page[n]; //存放页地址流 
int mc[33]; //memory capacity内存容量 ,并初始化为0 
 
void randomnumber()//random number随机数 程序第一步,产生320个指令序列 
{ 
 int pc;
 int flag=0; 
 scanf("%d",&pc); 
 printf("\n在0-319之间产生的320个随机数如下:\n"); 
 for(int i=0;i<320;i++) 
 { 
 num[i]=pc; 
 if(flag%2==0) pc=++pc%320; //flag=0||2 50%的指令是顺序执行的 
 if(flag==1) pc=rand()% (pc-1); //flag=1 25%的指令是均匀分布在前地址部分 
 if(flag==3) pc=pc+1+(rand()%(320-(pc+1))); //flag=3 25%的指令是均匀分布在后地址部分 
 flag=++flag%4; 
 printf("%3d ",num[i]); 
 if((i+1)%10==0) printf("\n"); //每行输出10个数 
 } 
} 
 
void pageaddress() //pageaddress页地址 程序第二步,将指令序列变换为页地址流 
{ 
 for(int i=0;i<320;i++) 
 { 
 printf("%3d ",page[i]=num[i]/10); 
 if((i+1)%10==0) printf("\n"); //每行输出10个数 
 } 
}
 
int fifo(int capacity)
{
 int j,x,y,m;
 int sum=0; //mc中分配的个数 
 int exist=0; //命中次数 
 int flag; //标志是否命中 flag=0没命中 flag=1命中 
 int ep=1; //elimination position淘汰位置 
 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) //还有空块 
 {for(x=1;x<=capacity;x++) //查找内存块中第一个空块 
 if(mc[x]==-1) {
 mc[x]=page[j];
 sum++;
 printf(" %2d加入 \t",page[j]);
 for(m=1;m<=capacity;m++) //输出当前内存块的存储情况 
 printf("%2d ",mc[m]);
 printf("\n");
 break;}
 }
 else if(sum>=capacity)
 {
 int t=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);
} 
int main()
{
 int capacity; //内存块数 
 printf("请输入第一条指令号(0~319):");
 randomnumber();
 printf("\n指令序列对应的页地址流:\n"); 
 pageaddress(); 
 printf("\n\n\n\t\t先进先出算法(fifo):\n\n");
 printf("请输入内存块数(4-32):");
 scanf("%d",&capacity);
 for(int i=1;i<=32;i++) //给数组赋初值 
 mc[i]=-1;
 fifo(capacity); 
 return 0;
}

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