【应用C】C语言模拟虚拟内存基本页面置换算法FIFO、OPT和LRU并比较效率(+源代码)

文章目录


  虚拟内存的核心原理是局部原理,作业在某个时间段内只运行在某一段代码范围内,于是不必要把整个作业都调入内存运行,只需要部分即可。
  虚拟内存管理一般采用按页管理,内存和作业都以页为单位,可以先调用作业的一部分页面进入内存运行,当作业所需要的页面不存在内存的时候就请求页调入或者页置换

01 - 页面置换算法

  基本的页面置换算法为OPT、FIFO和LRU,详细介绍有更加优秀的博客和书籍,在此只作简介

1.1 - FIFO

  FIFO(先入先出置换算法)是淘宝占用内存时间最久的页面,这是一种局部策略,单纯以作业的先后次序作为置换根据,非常容易实现的算法
  FIFO算法的作业结构体以及运行流程如下

typedef struct FIFO_BLOCO_STRUCT
{
	int old;                //指向最先进入队列的指针
	int top;                //指向当前位置的指针
	bool isEmpty;           //物理块是否为空
	int queue[BLOCO_LEN];   //物理块队列
} FIFO_blocoType;

【应用C】C语言模拟虚拟内存基本页面置换算法FIFO、OPT和LRU并比较效率(+源代码)

1.2 - OPT

  OPT(最佳页面置换算法)是淘汰以后不再访问或距现在最长时间后要访问的页面,这是一种全局策略,是一种理论算法,本质上是不可能实现的,因为需要预测程序的页面引用串,这是无法预知的,但是由于算法产生的缺页次数是最少的,所以可以作为衡量其它算法的标准
  OPT算法的作业结构体以及运行流程如下

typedef struct OPT_BLOCO_STRUCT
{
	int old;                //指向最先进入队列的指针
	int top;                //指向当前位置的指针
	bool isEmpty;            //物理块是否为空
	int queue[BLOCO_LEN];   //物理块队列
	int time[BLOCO_LEN];    //未来第一次访问的时间
} OPT_blocoType;

【应用C】C语言模拟虚拟内存基本页面置换算法FIFO、OPT和LRU并比较效率(+源代码)

1.3 - LRU

  LRU(最近最少使用置换算法)是淘汰占用时间最长和使用次数最少的页面,这是一种局部策略,是可以具体实现的
  LRU算法的作业结构体以及运行流程如下

typedef struct LRU_BLOCO_STRUCT
{
	int old;                //指向最先进入队列的指针
	int top;                //指向当前位置的指针
	bool isEmpty;            //物理块是否为空
	int stack[BLOCO_LEN];   //物理块队列
} LRU_blocoType;

【应用C】C语言模拟虚拟内存基本页面置换算法FIFO、OPT和LRU并比较效率(+源代码)

02 - 效率比较

  例程中有一个比较程序main.c,进行100,000次测试,得出平均命中率进行比较
  main.c运行结果如下(运行时间大概为5s)

FIFO ave 0.357536, LRU ave 0.361196,OPT ave 0.639699

03 - 源码下载

  链接:百度网盘 提取码:i0ml

04 - 总结

  • OPT是一个理论算法,可以作为标准
  • FIFO和LRU相差并不是太大
  • 例程是一个比较简单的模拟,只是为了计算命中率
上一篇:【新知识】队列&bfs【洛谷p1996约瑟夫问题&洛谷p1451求细胞数量】(没


下一篇:基于MSP430F5438A的OV7670简单驱动程序