文章目录

• 01 - 页面置换算法
• 1.1 - FIFO
• 1.2 - OPT
• 1.3 - LRU
• 02 - 效率比较
• 03 - 源码下载
• 04 - 总结

---

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

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;

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;

1.3 - LRU

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

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

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相差并不是太大
• 例程是一个比较简单的模拟，只是为了计算命中率