页面置换算法（LRU算法）

LRU

• LRU是一种页面置换算法，在对于内存中但是又不用的数据块，叫做LRU，操作系统会根据那些数据属于LRU而将其移出内存而腾出空间来加载另外的数据
• LRU算法：最近最少使用，简单来说就是将数据块中，每次使用过的数据放在数据块的最前端，然后将存在的时间最长的，也就是数据块的末端的数据剔除掉这就是LRU算法
• 如果进程被调度，该进程需要使用的外存页（数据）不存在于数据块中，这个现象就叫做缺页。如果这个数据此时不在，就会将这个数据从加入到数据块首部
• 数据块插入与剔除：每次有新数据到来时，会将其放入数据块首部，当数据每次被访问时，将这个数据插入数据块的首部如果数据块满了，每次新进的数据都会将数据块尾部的数据挤出数据块

为什么要使用LRU

• 关于操作系统内存管理，如何节省利用容量不大的内存多的进程提供资源。而内存的虚拟存储管理是现在最通用，最成功的方式。在内存有限的情况下，扩展一部分外存作为虚拟内存，真正的内存只存储当前运行时所用到的信息，极大的扩充了内存的功能，极大提高计算机的并发度，虚拟页式存储管理，则是将进程所需空间划分为多个页面，内存中只存放当前所需页面，将其余页面放入外存的管理方式
• 虚拟页式存储管理增加了进程所需的内存空间，却也带来了运行时间变长这一缺点，运行过程中，需要将外存中存放的信息和内存中已有的进行交换，由于外存的低速，影响了运行时间因此，应当采取尽量好的算法以减少读取外存的次数
• 对于虚拟页式存储，内外存信息替换是以页面为单位进行的，当需要一个外存中的页面是 将它调入内存，同时为了保持原有空间大小，我们需要不断地剔除掉一些存页面。数据块大小有限，因此我们需要每次调用外存数据时，都能准确的命中。这时就需要一个较好的页面管理算法。

使用方法：

如下题

假如现在有一组进程：进程编号为1,2,3,4,5

虚拟页式存储管理的数据块大小为3（也就是这个页式存储区的大小，能放置3个页面）。

假如进程被调度顺序为3.4.2.1.4.5.3.4.5.1.2。

问：在该访问中发生的缺页次数是多少？

解法：

1. 开始时，数据块中为空，因此第一个进程被调度时，未命中缓存，此时发生缺页。然后将进程对应数据放入数据块中

2. 第二步调用进程4，此时数据块中也没有进程4数据，因此未命中数据块缓存，也发生缺页0

3. 同理，发生缺页，但是此时数据块已经存满了数据，下一步如果加入新数据，将会剔除掉数据块尾部的数据

4. 插入新进程的数据1，此时将队尾的数据剔除掉。当然这个数据1也未命中，发生缺页

5. 调用到数据4，此时数据4在数据块缓存中，所以没有发生缺页。然后将数据4重新插入到数据块的首部。

如下图：

以此类推;得到最后的结果，缺页次数为8次。