系列文章：
4.页面置换算法
| 算法 | 注释 |
|---|---|
| 最优算法 | 不可实现，但可用作基准 |
| NRU(最近未使用)算法 | LRU的很粗糙的近似 |
| FIFO(先进先出)算法 | 可能抛弃重要页面 |
| 第二次机会算法 | 比FIFO有很大的改善 |
| 时钟算法 | 现实的 |
| LRU(最近最少使用)算法 | 很优秀，但很难实现 |
| NFU(最不经常使用)算法 | LRU的相对粗略的近似 |
| 老化算法 | 非常近似LRU的有效算法 |
| 工作集算法 | 实现起来开销很大 |
| 工作集时钟算法 | 好的有效算法 |
在系统运行工程中，当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存。那么怎么置换就十分重要了，我们想让它产生的缺页中断最少，算法的设计十分关键。
4.1最优页面置换算法
最好的算法，往往是不能实现。为什么不能，肯定是机器太笨，没有别的解释了。
最优页面置换算法，是当发生缺页中断时，我们就去寻找今后不用的页面或者用的最晚的那一个页面，将它替换出去。如果一个页面在100万条指令内不会被使用，另外一个页面在60万指令内不会被使用，则置换前一个页面，从而将缺页中断推迟，越久越好。
还是来个图简单解释一下吧，希望我能讲清楚。
当程序需要页面E的时候，发现页面B在后面不用了，那么就把页面B置换掉。需要页面F也是一样。
问题来了，怎么知道人家不用呢？跑一遍，拿个小本本记下来，想P呢！也许有用但没有必要！
4.2最近未使用页面置换算法（NRU)
既然不能预知未来，那么我们就回首过往。
在大部分的虚拟内存的计算机中，系统为每一个页面设置了两个状态位。当页面访问（读或写）时设置R位；当修改页面时设置W位，这些都需要包含在页表中。一个固定的时钟周期，去清零R位，区别最近没有被访问的页面和被访问的页面。
知识补充说明:
页表：就是页面的属性集合。
页表项结构：
页框号：最重要，页的映射就是要找到这个值
“在/不在”：标志页面在不在内存中。
保护位：一个页允许什么类型访问。（读/写）
修改位：标志该页面有没有被修改
访问位：标志该页面有没有被访问
修改位和访问位一般由硬件进行设置
高速缓存禁止位：禁止该页面被高速缓存
NRU(Not Recently Used)算法，在最近一个时钟周期内，淘汰一个没有被访问的已修改页面要比淘汰一个被频繁使用的“干净”页面好。
当产生页面中断时，操作系统会根据读写位把他们分成4类：
第0类：没有被访问，没有被修改
第1类：没有被访问，已被修改
第2类：已被访问，没有修改
第3类：已被访问，已被修改
第1类看起来不可能，其实在第3类，经过一个时钟周期，访问位被清零，就产生了该现象。
下面我们利用软件代码，模拟一下，该算法。
终于能够看到代码了！！！
页表项我们仅仅模拟修改位和访问位。
/*
* 页表项
* 仅用软件模拟 访问位R 和 修改位W
*/
template<class T>
class PageInfo
{
public:
PageInfo(T* dat);
~PageInfo();
const int getW() const; //获取访问位R
void setR_1(); //设置访问位R为1
void setR_0(); //设置访问位R为0
const int getR() const; //获取修改位W
void setW_1(); //设置修改位W为1
void setW_0(); //设置修改位W为0
T* data;
private:
int W, R;
};
模拟内存和设置需要页面
const int MAX = 4; //模拟内存能容忍最大页面
//模拟使用页面
PageInfo page_A(new string("A"));
PageInfo page_B(new string("B"));
PageInfo page_C(new string("C"));
PageInfo page_D(new string("D"));
PageInfo page_E(new string("E"));
PageInfo page_F(new string("F"));
void* Memery[MAX] = {nullptr}; //模拟内存
模拟时钟清零访问位
//模拟系统清零访问位
template<class T>
void ClearR()
{
std::this_thread::sleep_for(std::chrono::microseconds(20)); //设置时间间隔 20ms
while (1)
{
for (int i = 0; i < MAX; i++)
{
((PageInfo<T>*)Memery[i])->setR_0();
}
}
}
NRU算法实现
/*
* NUR 主要判断需不需要替换
* 根据NUR原则替换所需页面
* 传入所需页面&是否需要修改
*/
template<class T>
void NRU(PageInfo<T>& page,int W)
{
if (1 == W) //需要修改
{
page.setW_1();
}
page.setR_1();
int i = 0;
for (; i < MAX; i++) //判断页面是否存在
{
if (Memery[i] == (void*)&page)
{
break;
}
if (nullptr == ((PageInfo<T>*)Memery[i]))
{
cout << "缺页中断" << endl;
Memery[i] = (void*)&page;
break;
}
}
//如果不存在
if (i == MAX && ((PageInfo<T>*)Memery[MAX-1] != &page))
{
cout << "缺页中断" << endl;
int index = 0; //最佳替换的索引
PageInfo<T>* t = (PageInfo<T>*)Memery[0];
for (int i = 0; i < MAX; i++)
{
//该页面在一个时钟周期内，未被访问
if (0 == ((PageInfo<T>*)Memery[i])->getR() && 0 == ((PageInfo<T>*)Memery[i])->getW())
{
index = i;
break;
}
//判断谁被访问过，访问过优先
if (0 == ((PageInfo<T>*)Memery[i])->getW() && t->getR() == 1)
{
t = (PageInfo<T>*)Memery[i];
index = i;
continue;
}
//都被访问过，选择出未被修改过
if (1 == ((PageInfo<T>*)Memery[i])->getR() && t->getR() == 1)
{
if (((PageInfo<T>*)Memery[i])->getW() < t->getW())
{
t = ((PageInfo<T>*)Memery[i]);
index = i;
}
continue;
}
}
//替换之前 设置访问位R为0
((PageInfo<T>*)Memery[index])->setR_0();
if (((PageInfo<T>*)Memery[index])->getW() == 1)
{
//写回数据，设置修改位W为0
cout << *(((PageInfo<T>*)Memery[index])->data) << "页面被修改，写回......" << endl;
((PageInfo<T>*)Memery[index])->setW_0();
}
Memery[index] = (void*)&page;
}
}
测试函数：
/*
* data.txt
* 0 1
* 1 0
* 2 0
* 3 0
* 1 1
* 4 0
* 5 1
* 1 1
* 2 1
* 0 0
* 4 1
*/
//0，1，2，3，4，5 对应页面 page_A,page_B........
//W 为修改位，1 为修改 0 不修改
int main()
{
if (freopen("data.txt", "r", stdin) == NULL)
{
exit(0);
}
while (1)
{
int page = 0,W = 0;
cin >> page >> W;
switch (page)
{
case 0:
NRU(page_A, W);
break;
case 1:
NRU(page_B, W);
break;
case 2:
NRU(page_C, W);
break;
case 3:
NRU(page_D, W);
break;
case 4:
NRU(page_E, W);
break;
case 5:
NRU(page_F, W);
break;
default:
break;
}
}
std::thread thread_clear(ClearR<string>); //启动线程，按照时钟周期清零
thread_clear.join();
return 0;
}
NRU主要优点是易于理解和能够有效地被实现，虽然它的性能不是很好，但是已经够用了。