[操作系统]页面置换算法(详解)，部分算法有代码实现，仅供学习_页面置换算法代码

系列文章：

1.储存管理

2.虚拟内存

4.页面置换算法

​ 在系统运行工程中，当发生缺页中断时，操作系统必须在内存中选择一个页面将其换出内存。那么怎么置换就十分重要了，我们想让它产生的缺页中断最少，算法的设计十分关键。

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;
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

模拟内存和设置需要页面

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};		//模拟内存
1
2
3
4
5
6
7
8
9
10
11

模拟时钟清零访问位

//模拟系统清零访问位
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();
		}
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13

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;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71

测试函数：

/*
* 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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

​ NRU主要优点是易于理解和能够有效地被实现，虽然它的性能不是很好，但是已经够用了。