操作系统FIFO算法C语言实现

前言
本机为微软Surface pro4，为64位，所用操作系统为Windos 10。本机虚拟机版本为Oracle VM VirtualBox 6.1.8，所用操作系统是使用Ubuntu18.04，。Ubuntu的虚拟硬盘设置为200G，显存为128MB，内存为4G，CPU2个，所用镜像源为清华大学软件镜像源。所使用linux内核为linux-5.11.8。

注意事项
（1）本FIFO算法的实现思路是借鉴网上的相关资源，并非原创。
（2）本篇博客代码实现FIFO算法的命中率和置换显示。

FIFO算法介绍
FIFO算法：它的思想是先进先出（FIFO，队列），这是最简单、最公平的一种思想，即 如果一个数据是最先进入的，那么可以认为在将来它被访问的可能性很小。.空间满的时候，最先进入的数据会被最早置换（淘汰）掉 。

Linux下C语言实现FIFO算法的代码
1、使用文件编辑器在主目录下创建一个名为OS2的文件夹。

2、打开Geany程序，然后点击新建按钮，创建一个新文件。
（注：创建完成界面如下）

3、在新建的文件中书写程序。（注：程序如下）

#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页地址 程序第二步，将指令序列变换为页地址流，产生了32个指令页 
{     
	for(int i=0;i<320;i++)  
	{     
	printf("%3d   ",page[i]=num[i]/10);        
	if((i+1)%10==0) printf("\n");  //每行输出10个数 
	} 
}
 
//FIFO算法实现 
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;
}

4、将程序文件命名fifo.c为保存到OS2文件下。（注：如图所示）

FIFO算法实现效果如下
1、按如下图示中标明顺序点击按钮执行即可（注：效果图如下）

FIFO算法

FIFO算法是最简单的页面置换算法。FIFO算法为每个页面记录了调到内存的时间。当必须置换页面的时候，选择最旧的页面。

通俗来说，每次进入主存的时候

• 如果主存中不存在这个页面，那么最先进入的页面出队。
• 如果主存存在这个页面，那么内存不动。

下面是C++面向对象写法代码。
这个说明一下为什么不用容器Queue。是因为queue并没有迭代器，所以无法去寻找里面是否含有某块页面。
直接使用线性表即可，方便简单且快速。

// 在分页式虚拟存储管理中，要求通过键盘输入分配给一个作业的物理块数和作业依次访问的10个页面号，
// 采用先进先出（FIFO）页面置换后
// ，顺序输出缺页中断时所淘汰的页面号，并计算缺页中断率。
#include <iostream>

using namespace std;
#define MAX 20
class Work
{
public:
    void seta()
    {
        int c, i = 1;
        cout << "输入10个页面号,以任意符号结尾" << endl;
        cin >> c;
        a[0] = c;
        while (cin >> c)
        {

            a[i] = c;
            i++;
        }
    }
    void geta()
    {
        cout << "10个页面号分别为:  ";
        for (int i = 0; i < 10; i++)
        {
            cout << a[i] << " ";
        }
        cout << endl;
    }
    int index(int i)
    {
        return a[i];
    }
~Work(){
    cout<<"work 已被释放"<<endl;
}
private:
    int a[10];
};

class space
{
public:    
    // 初始化构造函数，把除了物理块大小的其他空间都设置成其他值
    // 将初始化空间设置成-1
    space(int i)
    {
        size=i;
        for (int j = 0; j < i; j++)
        {
            s[j] = -1;
        }
        s[i] = -999;
    }

    // 显示物理块现在的状态
    void getSpace(){
        int i=0;
        cout<<"-------------物理块现在的状态是-------------"<<endl;
        
        while(s[i]!=-999){
            if(s[i]==-1){
                cout<<"NaN"<<"     -||-      ";
                i++;
                continue;
            }
            cout<<s[i]<<"     -||-      ";
            i++;
        }
        cout<<endl;
        cout<<"------------------------------------------"<<endl;
    }
    int find(int n){
        for(int i=0;i<size;i++){
            if(s[i]==n){
                return i;
            }
        }
        return -1;
    }

    // 先进先出，去掉第一个物理块，改变最后一个物理块。
    void change(int n){
        for(int i=0;i<size;i++){
            s[i]=s[i+1];
        }
        s[size-1]=n;

    }

    ~space(){
        cout<<"space 已被释放"<<endl;
    }
private:
    int s[MAX];
    int size;
};


void FIFO(Work &a,space &s){
    int i=0;
    int local;
    int count=0;
    while(i<10){
        if(s.find(a.index(i))==-1){
            // 如果在物理块里面找不到作业
            s.change(a.index(i));
            // 那么就将物理块改变
            s.getSpace();
            count+=1;
        }else{
            s.getSpace();
        }
        i++;
    }
    double q;
    q=(double)count/10;
    cout<<"----------------------------------"<<endl;
    cout<<"缺页中断的次数为： "<<count<<endl;
    cout<<"缺页终端率为： "<<q<<endl;
    cout<<"----------------------------------"<<endl;

}

int main()
{
    Work a;
    int num=0;
    cout<<"输入物理块数的个数"<<endl;
    cin>>num;  
    space s(num);  
    a.seta();
    a.geta();
    FIFO(a,s);
 

    return 0;
}