C语言实现页面置换算法

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

操作系统实验

页面置换算法(FIFO、LRU、OPT)

概念:

1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面;如无这样的页面存在,则选择最长时间不需要访问的页面。于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率。
2.先进先出置换算法(FIFO):是最简单的页面置换算法。这种算法的基本思想是:当需要淘汰一个页面时,总是选择驻留主存时间最长的页面进行淘汰,即先进入主存的页面先淘汰。其理由是:最早调入主存的页面不再被使用的可能性最大。
3.最近最久未使用(LRU)算法:这种算法的基本思想是:利用局部性原理,根据一个作业在执行过程中过去的页面访问历史来推测未来的行为。它认为过去一段时间里不曾被访问过的页面,在最近的将来可能也不会再被访问。所以,这种算法的实质是:当需要淘汰一个页面时,总是选择在最近一段时间内最久不用的页面予以淘汰。

题目:

编写一个程序,实现本章所述的FIFO、LRU和最优页面置换算法。首先,生成一个随机的页面引用串,其中页码范围为0-9.将这个随机页面引用串应用到每个算法,并记录每个算法引起的缺页错误的数量。实现置换算法,一遍页面帧的数量可以从1~7。

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

int numbers[20]={7,0,1,2,
     0,3,0,4,
     2,3,0,3,
     2,1,2,0,
     1,7,0,1};//本地数据,与课本一致,方便测试
int nums=0;//输入栈的个数,为了方便使用,
int stack[20][7]={10};

void begin();
void randomnum();//用于产生随机数
void init();//初始化
void FIFO();//FIFO算法
void LRU();//LRU算法
void OPT();//最优页面置换算法(OPT)
void print();//输出

int main() {
 begin();
 FIFO();
 LRU();
 OPT();
 return 0;
}
void begin()//开始菜单界面
{
 int i,j,k;
 printf("请输入页面帧的数量(1-7):");
 scanf("%d",&nums);
 for(k=0;;k++)
 {
  printf("是否使用随机数产生输入串(0:是,1:否)");
  scanf("%d",&j);
  if(j==0)
  {
   randomnum();
   break;
  }
  else if(j==1)
  {
   break;
  }
  else
  {
   printf("请输入正确的选择!\n");
  }
 }

 printf("页面引用串为:\n");
 for(i=0;i<20;i++)
 {
  printf("%d ",numbers[i]);
 }
 printf("\n");
 init();
}
void randomnum()//如果需要使用随机数生成输入串,调用该函数
{
 srand(time(0));//设置时间种子
 for(int i = 0; i < 20; i++) {
  numbers[i] = rand() % 10;//生成区间0`9的随机页面引用串
 }
}
void init()//用于每次初始化页面栈中内容,同时方便下面输出的处理
{
 int i,j;
 for(i=0;i<20;i++)
  for(j=0;j<nums;j++)
   stack[i][j]=10;
}

void print()//输出各个算法的栈的内容
{
 int i,j;
 for(i=0;i<nums;i++)
 {
  for(j=0;j<20;j++)
  {
   if(stack[j][i]==10)
    printf("* ");
   else
    printf("%d ",stack[j][i]);
  }
  printf("\n");
 }

}

void FIFO()//FIFO算法
{
 init();
 int i,j=1,n=20,k,f,m;
 stack[0][0]=numbers[0];

 for(i=1;i<20;i++)
 {
  f=0;
  for(m=0;m<nums;m++)
  {
   stack[i][m]=stack[i-1][m];
  }
  for(k=0;k<nums;k++)
  {
   if(stack[i][k]==numbers[i])
   {
    n--;
    f=1;
    break;
   }
  }
  if(f==0)
  {
   stack[i][j]=numbers[i];
   j++;
  }
  if(j==nums)
   j=0;
 }
 printf("\n");
 printf("FIFO算法:\n");
 print();
 printf("缺页错误数目为:%d\n",n);
}

void LRU()//LRU算法
{
 int i,j,m,k,sum=1;
 int sequence[7]={0};//记录序列
 init();
 stack[0][0]=numbers[0];
 sequence[0]=nums-1;
 for(i=1;i<nums;i++)//前半部分,页面空置的情况
 {
  for(j=0;j<nums;j++)
  {
   stack[i][j]=stack[i-1][j];
  }
  for(j=0;j<nums;j++)
  {
   if(sequence[j]==0)
   {
    stack[i][j]=numbers[i];
    break;
   }
  }
  for(j=0;j<i;j++)//将之前的优先级序列都减1
  {
   sequence[j]--;
  }
  sequence[i]=nums-1;//最近使用的优先级列为最高
  sum++;
 }
 for(i=nums;i<20;i++)//页面不空,需要替换的情况
 {
  int f;
  f=0;
  for(j=0;j<nums;j++)
  {
   stack[i][j]=stack[i-1][j];
  }
  for(j=0;j<nums;j++)//判断输入串中的数字,是否已经在栈中
  {
   if(stack[i][j]==numbers[i])
   {
    f=1;
    k=j;
    break;
   }
  }
  if(f==0)//如果页面栈中没有,不相同
  {
   for(j=0;j<nums;j++)//找优先序列中为0的
   {
    if(sequence[j]==0)
    {
     m=j;
     break;
    }
   }
   for(j=0;j<nums;j++)
   {
    sequence[j]--;
   }
   sequence[m]=nums-1;
   stack[i][m]=numbers[i];
   sum++;
  }
  else//如果页面栈中有,替换优先级
  {
   if(sequence[k]==0)//优先级为最小优先序列的
   {
    for(j=0;j<nums;j++)
    {
     sequence[j]--;
    }
    sequence[k]=nums-1;
   }
   else if(sequence[k]==nums-1)//优先级为最大优先序列的
   {
    //无需操作
   }
   else//优先级为中间优先序列的
   {
    for(j=0;j<nums;j++)
    {
     if(sequence[k]<sequence[j])
     {
      sequence[j]--;
     }
    }
    sequence[k]=nums-1;
   }
  }
 }
 printf("\n");
 printf("LRU算法:\n");
 print();
 printf("缺页错误数目为:%d\n",sum);
}

void OPT()//OPT算法
{
 int i,j,k,sum=1,f,q,max;
 int seq[7]={0};//记录序列
 init();
 stack[0][0]=numbers[0];
 seq[0]=nums-1;
 for(i=1;i<nums;i++)//前半部分,页面空置的情况
 {
  for(j=0;j<nums;j++)
  {
   stack[i][j]=stack[i-1][j];
  }
  for(j=0;j<nums;j++)
  {
   if(seq[j]==0)
   {
    stack[i][j]=numbers[i];
    break;
   }
  }
  for(j=0;j<i;j++)//将之前的优先级序列都减1
  {
   seq[j]--;
  }
  seq[i]=nums-1;//最近使用的优先级列为最高
  sum++;
 }
 for(i=nums;i<20;i++)//后半部分,页面栈中没有空的时候情况
 {
  //k=nums-1;//最近的数字的优先级
  for(j=0;j<nums;j++)//前面的页面中内容赋值到新的新的页面中
  {
   stack[i][j]=stack[i-1][j];
  }
  for(j=0;j<nums;j++)
  {
   f=0;
   if(stack[i][j]==numbers[i])
   {
    f=1;
    break;
   }
  }
  if(f==0)//页面中没有,需要替换的情况
  {
   for(q=0;q<nums;q++)//优先级序列中最大的就是最久未用的,有可能出现后面没有在用过的情况
   {
    seq[q]=20;
   }
   for(j=0;j<nums;j++)//寻找新的优先级
   {
    for(q=i+1;q<20;q++)
    {
     if(stack[i][j]==numbers[q])
     {
      seq[j]=q-i;
      break;
     }
    }
   }
   max=seq[0];
   k=0;
   for(q=0;q<nums;q++)
   {
    if(seq[q]>max)
    {
     max=seq[q];
     k=q;
    }
   }
   stack[i][k]=numbers[i];
   sum++;
  }
  else
  {
   //页面栈中有需要插入的数字,无需变化,替换的优先级也不需要变化
  }
 }
 printf("\n");
 printf("OPT算法:\n");
 print();
 printf("缺页错误数目为:%d\n",sum);
}

运行结果截图:


这个代码能在linux上跑通的,在windows上肯定也没得问题

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

(0)

相关推荐

  • Linux页面置换算法的C语言实现

    Linux页面置换算法的C语言实现 编写算法,实现页面置换算法FIFO.LRU.OPT:针对内存地址引用串,进行页面置换算法进行页面置换. 其中,算法所需的各种参数由输入产生(手工输入或者随机数产生):输出内存驻留的页面集合,缺页次数以及缺页率. #include <stdio.h> //#include <conio.h> #include <stdlib.h> #include <time.h>//随机数 #define Myprintf printf(

  • C语言实现页面置换算法

    本文实例为大家分享了C语言实现页面置换算法的具体代码,供大家参考,具体内容如下 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面:如无这样的页面存在,则选择最长时间不需要访问的页面.于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率. 2.先进先出置换算法(FIFO):是最简单的页面置换算法.这种算法的基本思想是:当需要淘汰一个页面时,总是选择驻留主存时

  • C语言实现页面置换算法(FIFO、LRU)

    目录 1.实现效果 2.实现源代码  1.实现效果 2.实现源代码  #include<iostream> #include<process.h> #include<stdlib.h> #include<ctime> #include<conio.h> #include<stdio.h> #include<string.h> using namespace std; #define Myprintf printf(&quo

  • 利用C语言实现页面置换算法的详细过程

    目录 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 题目: 代码 总结 操作系统实验 页面置换算法(FIFO.LRU.OPT) 概念: 1.最佳置换算法(OPT)(理想置换算法):从主存中移出永远不再需要的页面:如无这样的页面存在,则选择最长时间不需要访问的页面.于所选择的被淘汰页面将是以后永不使用的,或者是在最长时间内不再被访问的页面,这样可以保证获得最低的缺页率. 2.先进先出置换算法(FIFO):是最简单的页面置换算法.这种算法的基本思想是:当需要淘汰一个页面时,总是选择

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

    本文实例为大家分享了C语言实现页面置换算法的具体代码,供大家参考,具体内容如下 一.设计目的 加深对请求页式存储管理实现原理的理解,掌握页面置换算法中的先进先出算法. 二.设计内容 设计一个程序,有一个虚拟存储区和内存工作区,实现下述三种算法中的任意两种,计算访问命中率(命中率=1-页面失效次数/页地址流长度).附加要求:能够显示页面置换过程. 该系统页地址流长度为320,页面失效次数为每次访问相应指令时,该指令对应的页不在内存的次数.    程序首先用srand()和rand()函数分别进行初

  • 通过代码实例了解页面置换算法原理

    页面置换算法:本质是为了让有限内存能满足无线进程. 先说明一下处理缺页错误的过程: 分页硬件在通过页表转换地址时会注意到无效位被设置,从而陷入操作系统,这种陷阱是因为操作系统未能将所需要的页面调入内存引起的. 处理缺页错误: 1.检查这个进程的内部表,确定该引用是否为有效的内存访问(可以理解为这个内存能被当前进程使用),如果无效那么直接终止进程:如果有效但是尚未调入页面,就将该页面调入内存. 2.然后从空闲帧链表上找到一个空闲帧. 3.调度磁盘将进程所需要的内存读入页帧中, 4.磁盘读取完成,修

  • java实现页面置换算法

    本文实例为大家分享了java实现页面置换算法的具体代码,供大家参考,具体内容如下 原理就不说了,直接上代码 FIFO import java.util.ArrayList; import java.util.List; import utils.ListUtils; /** * * * @author cnkeysky * */ public class FIFO { public void run() { String[] inputStr = {"1", "2"

  • java语言实现权重随机算法完整实例

    前言 现在app就是雨后春笋,嗖嗖的往外冒啊,有经验的.没经验的.有资历的.没资历的都想着创业,创业的90%以上都要做一个app出来,好像成了创业的标配. 做了app就得推广啊,怎么推,发券送钱是最多用的被不可少的了,现在好多产品或者运营都要求能够随机出优惠券的金额,但是呢又不能过于随机,送出去的券都是钱吗,投资人的钱,是吧. 所以,在随机生成的金额中就要求,小额度的几率要大,大额度的几率要小,比如说3元的70%,5块的25%,10块的5%,这个样子的概率去生成优惠券,这个怎么办呢? 对于上述的

  • 基于Go和PHP语言实现爬楼梯算法的思路详解

    爬楼梯(Climbing-Stairs) 题干: 假设你正在爬楼梯.需要 n 阶你才能到达楼顶.每次你可以爬 1 或 2 个台阶.你有多少种不同的方法可以爬到楼顶呢?注意:给定 n 是一个正整数.示例 1:  输入: 2  输出: 2  解释: 有两种方法可以爬到楼顶.  1. 1 阶 + 1 阶  2. 2 阶示例 2:  输入: 3  输出: 3  解释: 有三种方法可以爬到楼顶.  1. 1 阶 + 1 阶 + 1 阶  2. 1 阶 + 2 阶  3. 2 阶 + 1 阶来源:力扣 这题

  • R语言关于随机森林算法的知识点详解

    在随机森林方法中,创建大量的决策树. 每个观察被馈入每个决策树. 每个观察的最常见的结果被用作最终输出. 新的观察结果被馈入所有的树并且对每个分类模型取多数投票. 对构建树时未使用的情况进行错误估计. 这称为OOB(袋外)误差估计,其被提及为百分比. R语言包"randomForest"用于创建随机森林. 安装R包 在R语言控制台中使用以下命令安装软件包. 您还必须安装相关软件包(如果有). install.packages("randomForest") 包&qu

随机推荐