操作系统页面置换算法

前言什么是页面置换算法解决方法先进先出页面置换算法（fifo）最佳置换算法（opt）LRU算法

前言

不多说废话了，不是很了解这个算法是干啥的，现在开冲。

什么是页面置换算法

很简单，咱们还是看看严格的定义好了。 在地址映射过程中，若在页面中发现所要访问的页面不在内存中，则产生缺页中断。当发生缺页中断时，如果操作系统内存中没有空闲页面，则操作系统必须在内存选择一个页面将其移出内存，以便为即将调入的页面让出空间。而用来选择淘汰哪一页的规则叫做页面置换算法。 很显然，这是进程遇到的困难，是操作系统帮助完成的事情。缺页中断也就清楚是咋回事了吧。

解决方法

先进先出页面置换算法（fifo）

这个就非常好理解了。fifo大家都知道对吧，操作系统维护一个fifo，然后刚产生的（基本上是从磁盘被置换出来的）页表就放在fifo后面，而前面的页表就面临着被放到磁盘上去的风险。 这个置换算法实在无脑，它的想法是，存在时间越久的页表，被使用到的概率就越小。我真的一脸懵逼。这是啥道理？

最佳置换算法（opt）

看到名称是不是也就放心了？ 这是一种理想情况下的页面置换算法，但实际上是不可能实现的。该算法的基本思想是：发生缺页时，有些页面在内存中，其中有一页将很快被访问（也包含紧接着的下一条指令的那页），而其他页面则可能要到10、100或者1000条指令后才会被访问，每个页面都可以用在该页面首次被访问前所要执行的指令数进行标记。最佳页面置换算法只是简单地规定：标记最大的页应该被置换。这个算法唯一的一个问题就是它无法实现。当缺页发生时，操作系统无法知道各个页面下一次是在什么时候被访问。虽然这个算法不可能实现，但是最佳页面置换算法可以用于对可实现算法的性能进行衡量比较。 嘿嘿嘿，是不是有点失望？继续。

LRU算法

这个可是咱们的老朋友了对吧，之前也介绍过。 LRU需要硬件的配合，这个要怎么理解？因为呢，操作系统并没有使用一个fifo一样的结构，而是使用的朴素的线性队列，然后用一个计时器不断在跑，当遇到一个页表被使用时，就将这个计时器的数值写到页表的附带参数上。