1. 页面置换算法之LRU算法
三种常见的页面置换算法:FIFO、LFU、LRU
参考：
缓存算法（页面置换算法）-FIFO、LFU、LRU
LRU（Least Recently Used，最近最少使用）算法根据数据的历史访问记录来进行淘汰数据，其核心思想是： 如果一个数据在最近一段时间没有被访问到，那么在将来它被访问的可能性也很小 。也就是说，当限定的空间已存满数据时，应当把最久没有被访问到的数据淘汰。
假设 序列为 4 3 4 2 3 1 4 2
物理块有3个 则
首轮 4调入内存 4
次轮 3调入内存 3 4
之后 4调入内存 4 3
之后 2调入内存 2 4 3
之后 3调入内存 3 2 4
之后 1调入内存 1 3 2（因为最少使用的是4，所以丢弃4）
之后 4调入内存 4 1 3（原理同上）
最后 2调入内存 2 4 1
如果让我们设计一个LRU Cache的数据结构，它应该支持两个操作：
一种是采用数组来存储每个数据项，再对每个key关联一个时间戳，在cache中维护一个最大时间戳，其设计要点如下：
另一种是采用hashmap+双向链表的数据结构，其设计要点如下：
对比上一节的两种设计思路，不难发现，设计1需要为每个key维护一个时间戳，而且set和get操作的时间复杂度都是O(n)。显而易见，随着数据量的增大，set和get操作的速度越来越慢。而设计2通过采用hashmap+双向链表，set和get操作的时间复杂度只需O(1)，下面给出设计2的具体实现。
运行结果为：
参考：
LRU Cache
LRU原理和Redis实现——一个今日头条的面试题
2. c语言编写页面置换算法
//熬夜弄出来的，记得加分哦
#include<stdio.h>
void Print(int bc[],int blockCount)
{
for(int i=0;i<blockCount;i++)
{
printf("%d ",bc[i]);
}
printf("\n");
}
bool Travel(int bc[],int blockCount,int x)
{
bool is_found=false;
int i;
for(i=0;i<blockCount;i++)
{
if(bc[i]==x)
{
is_found=true;
break;
}
}
return is_found;
}
void FIFO(int pc[],int bc[],int pageCount,int blockCount)
{
printf("0：FIFO置换算法\n");
int i;
if(pageCount<=blockCount)
{
printf("缺页次数为0\n");
printf("缺页率为0\n");
}
else
{
int noPage=0;
int p=0;
for(i=0;i<pageCount;i++)
{
//printf("引用页：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
if(p==blockCount)
{
p=0;
}
bc[p]=pc[i];
p++;
}
noPage++;
//printf("物理块情况：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("FIFO缺页次数为:%d\n",noPage);
printf("FIFO缺页率为:%.2f%%\n",(float)noPage/pageCount*100);
}
}
int FoundMaxNum(int a[],int n)
{
int k,j;
k=a[0];
j=0;
for (int i=0;i<n;i++)
{
if(a[i]>=k)
{
k=a[i];
j=i;
}
}
return j;
}
void LRU(int pc[],int bc[],int pageCount,int blockCount)
{
printf("1：LRU置换算法\n");
if(pageCount<=blockCount)
{
printf("缺页次数为0\n");
printf("缺页率为0\n");
}
else
{
int noPage=0;
int i,j,m;
int bc1[100];
for(i=0;i<blockCount;i++)
{
bc1[i]=0;
}
for(i=0;i<pageCount;i++)
{
// printf("引用页：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
for(int p=0;p<=i;p++)
{
bc1[p]++;
}
}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
int k=FoundMaxNum(bc1,blockCount);
bc[k]=pc[i];
bc1[k]=1;
}
noPage++;
//printf("物理快情况：\n");
//Print(bc,blockCount);
}
else if(Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
for(j=0;j<=i;j++)
{
bc1[j]++;
}
for(m=0;m<=i;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];
}
else
{
for(j=0;j<blockCount;j++)
{
bc1[j]++;
}
for(m=0;m<blockCount;m++)
{
if(bc[m]==pc[i])
{
break;
}
}
bc1[m]=1;
bc[m]=pc[i];
}
}
//printf("\n");
}
printf("LRU缺页次数为:%d\n",noPage);
printf("LRU缺页率为:%.2f%%\n",(float)noPage/pageCount*100);
}
}
void Optiomal(int pc[],int bc[],int pageCount,int blockCount)
{
printf("2：最佳置换算法\n");
if(pageCount<=blockCount)
{
printf("缺页次数为0\n");
printf("缺页率为0\n");
}
else
{
int noPage=0;
int i,j,k;
for(i=0;i<pageCount;i++)
{
// printf("引用页：%d\n",pc[i]);
if(!Travel(bc,blockCount,pc[i]))
{
if(i<blockCount)
{
bc[i]=pc[i];
}
else
{
int max=0;
int blockIndex;;
for(j=0;j<blockCount;j++)
{
for(k=i;k<pageCount;k++)
{
if(bc[j]==pc[k])
{
break;
}
}
if(k>=max)
{
max=k;
blockIndex=j;
}
}
bc[blockIndex]=pc[i];
}
noPage++;
//printf("物理快情况：\n");
//Print(bc,blockCount);
}
//printf("\n");
}
printf("OPT缺页次数为:%d\n",noPage);
printf("OPT缺页率为:%.2f%%\n",(float)noPage/pageCount*100);
}
}
int main()
{
int pageCount,blockCount,i,pc[100];
printf("输入页面数\n");
scanf("%d",&pageCount);
printf("输入页面走向\n");
for(i=0;i<pageCount;i++)
{
scanf("%d",&pc[i]);
}
blockCount=3;//物理块数
int bc1[100];
printf("\n");
FIFO(pc,bc1,pageCount,blockCount);
int bc2[100];
printf("\n");
LRU(pc,bc2,pageCount,blockCount);
int bc3[100];
printf("\n");
Optiomal(pc,bc3,pageCount,blockCount);
return 0;
}
3. 页面置换算法
上文说到，请求分页管理方式中，当需要调入页面到内存中，但此时内存已满，就需要从内存中按照一定的置换算法决定将哪个页面取出将内存给调入的页面。本文将介绍几种页面置换算方法。
本文内容
算法思想：每次选择 淘汰的页面 将是 以后永不使用 ，或者 在最长时间内不再被访问的页面 ，这样可以保证最低的缺页率。
举例说明，假设系统为进程分配了三个内存块，并考虑到有以下页面号引用串（会依次访问这些页面）：7,0,1,2,0,3,0,4,2,3,0,3,2,1,2,0,1,7,0,1
....按照此算法依次执行，最后的结果如下
结果图
注：缺页时未必发生页面置换，若还有可用的空闲内存空间就不用进行页面置换。
最佳置换算法可以保证最低的缺页率，但是实际上，只有进程执行的过程中才能知道接下来会访问到的是哪个页面。操作系统无法提前预判页面的访问序列。因此， 最佳置换算法是无法实现的 。
算法思想：每次选择 淘汰的页面是最早进入内存的页面。
该算法很简单，每次淘汰最在内存中待时间最久的各个，下面分别给出系统为进程分为配三个内存块和四个内存块的执行情况图。访问序列为3,2,1,0,3,2,4,3,2,1,0,4
分配三个内存块的情况：
分配四个内存块的情况：
当为进程分配的物理块数增大时，缺页次数不减反增的异常现象称为 贝莱迪（Belay）异常 。
只有FIFO算法会产生Belay异常。 另外，FIFO算法虽然实现简单，但是该算法与进程实际运行时的规律不适应。因为先进入的页面也有可能最经常被访问。因此， 算法性能差。
算法思想： 每次淘汰的页面是最近最久未使用的页面。
实现方法：赋予每个页面对应的页表项中，用 访问字段记录该页面自上次被访问以来所经历的时间t。 当需要淘汰一个页面时，选择现有页面中t最大的页面，即最近最久未使用。
举例说明，加入某系统为某进程分配了四个内存块，并考虑到有以下页面号引用串：1,8,1,7,8,2,7,2,1,8,3,8,2,1,3,1,7,1,3,7
这里先直接给出答案
结果图
最佳置换算法那性能最好，但无法实现。先进先出置换算法实现简单，但是算法性能差。最近最久未使用置换算法性能好，是最接近OPT算法性能的，但是实现起来需要专门的硬件支持，算法开销大。 时钟置换算法 是一种 性能和开销均平衡 的算法。又称 CLOCK算法 ，或 最近未用算法 （ NRU ，Not Recently Used）
简单CLOCK算法 算法思想：为每个页面设置一个 访问位 ，再将内存中的页面都通过 链接指针链接成一个循环队列 。当某个页被访问时，其访问位置1.当需要淘汰一个页面时，只需检查页的访问位。如果是0，就选择该页换出；如果是1，暂不换出，将访问位改为0，继续检查下一个页面，若第一轮扫描中所有的页面都是1，则将这些页面的访问位一次置为0后，再进行第二轮扫描（第二轮扫描中一定会有访问位为0的页面，因此简单的CLOCK算法选择一个淘汰页面最多会经过 两轮扫描 ）。
这个算法指针在扫描的过程就像时钟一样转圈，才被称为时钟置换算法。
简单的时钟置换算法仅考虑到了一个页面最近是否被访问过。事实上，如果淘汰的页面没有被修改过，就不需要执行I/O操作写回外存。 只有淘汰的页面被修改过时，才需要写回外存。
因此，除了考虑一个页面最近有没有被访问过之外，操作系统还需要考虑页面有没有被修改过。
改进型时钟置换算法的 算法思想 ： 在其他在条件相同时，应该优先淘汰没有被修改过的页面， 从而来避免I/O操作。
为了方便讨论，用（访问位，修改位）的形式表示各页面的状态。如（1,1）表示一个页面近期被访问过，且被修改过。
算法规则 ：将所有可能被置换的页面排成一个循环队列
由于第二轮已将所有的页的访问位都设为0，因此第三轮、第四轮扫描一定会选中一个页，因此 改进型CLOCK置换算法最多会进行四轮扫描。
假设系统为进程分配了5个内存块，某时刻，各个页的状态如下图
如果此时有新的页要进入内存，开始第一轮扫描就找到了要替换的页，即最下面的状态为（0,0）的页。
某一时刻页面状态如下
如果此时有新的页要进入内存，开始第一轮扫描就发现没有状态为（0，0）的页，第一轮扫描后不修改任何标志位。所以各个页状态和上图一样。
然后开始第二轮扫描，尝试找到状态为（0,1）的页，并将扫描过后的页的访问位设为0，第二轮扫描找到了要替换的页。
某一时刻页面状态如下
第一轮扫描没有找到状态为（0,0）的页，且第一轮扫描不修改任何标志位，所以第一轮扫描后状态和上图一致。
然后开始第二轮扫描，尝试找状态为（0,1）的页，也没有找到，第二轮扫描需要将访问位设为1，第二轮扫描后，状态为下图
某一时刻页面状态如下
具体的扫描过程和上面相同，这里只给出最后的结果，如下图
所以，改进型的CLOCK置换算法最多需要四轮扫描确定要置换的页。从上面的分析可以看出，改进型的CLOCK置换算法
(1) 第一优先级淘汰的是 最近没有访问且没有修改 的页面。
(2) 第二优先级淘汰的是 最近没有访问但修改 的页面。
(3) 第三优先级淘汰的是 最近访问但没有修改 的页面。
(4) 第四优先级淘汰的是 最近访问且修改 的页面。