最近最久未使用（LRU）置换算法的C++实现

操作系统实验 最近最久未使用（LRU）置换算法

实验题目

  1. 最近最久未使用（LRU）置换算法原理就是：当需要淘汰某页面时，选择当前一段时间内最久未使用过的页先淘汰，即淘汰距当前最远的上次使用的页。

    • 例如: 分配给该进程的页块数为3，一个20位长的页面访问序列为:12560,36536,56042,70435，则缺页次数和缺页率按下图给出:

      image-20211207201735320

      注：原实验指导书上图示有误，该图为笔者制作。

  2. 假定分配给该进程的页块数为3，页面访问序列长度为20。本实验可以采用数组结构实现，首先随机产生页面序列，当发生请求调页时，若内存已满，则需要利用LRU算法，将当前一段时间内最久未使用过的页替换出去。

    • 模拟程序的算法如下图：

      image-20211207202046671

程序中使用的数据结构及符号说明

  1. 数组（数据结构）记录信息

    1
    2
    3
    4
    5
    6
    int memory[1001];      //记录进程内存中的页
    bool flag[1001];       //标记：访问的页面是否在内存中
    int l_time[1001];      //记录页面的最近使用时间
    int vis[1001];         //记录访问序列
    bool miss[1001];       //记录每次访问的缺页状态
    int state[1001][1001]; //记录每次访问后的进程的内存页面状态

  2. 整型变量

    1
    2
    3
    4
    5
    int n;                 //进程内存的页块数
    int now_num = 0;       //进程内存当前的页个数
    int now_time = 0;      //当前时间(访问次数)
    int m;                 //页面访问序列的长度
    int miss_num = 0;      //缺页次数

  3. 缺页率

    1
    double miss_rate;      //缺页率

  4. 自定义函数

    • void init()：初始化
    • void LRU(int a)：LRU算法的实现
    • void display()：输出信息

源程序及注释

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
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
#include <iostream>
#include <queue>
#include <iomanip>
using namespace std;

int n;                 //进程内存的页块数
int now_num = 0;       //进程内存当前的页个数
int now_time = 0;      //当前时间(访问次数)
int m;                 //页面访问序列的长度
int miss_num = 0;      //缺页次数
double miss_rate;      //缺页率
int memory[1001];      //记录进程内存中的页
bool flag[1001];       //标记：访问的页面是否在内存中
int l_time[1001];      //记录页面的最近使用时间
int vis[1001];         //记录访问序列
bool miss[1001];       //记录每次访问的缺页状态
int state[1001][1001]; //记录每次访问后的进程的内存页面状态

//初始化
void init()
{
	cout << "请输入分配给该进程的页块数：";
	cin >> n;
	cout << "请输入页面访问序列的长度：";
	cin >> m;
	cout << "请输入访问序列：";
	for (int i = 0; i < m; i++)
	{
		cin >> vis[i];
	}
	//进程的内存中刚开始没有页，初始化为-1
	for (int i = 0; i < n; i++)
	{
		memory[i] = -1;
	}
	//在内存中的标记初始化为false
	for (int i = 0; i < 1000; i++)
	{
		flag[i] = false;
	}
	//页面的最近使用时间初始化为0
	for (int i = 0; i < 1000; i++)
	{
		l_time[i] = 0;
	}
	return;
}

//LRU算法
void LRU(int a)
{
	//检查请求访问的页是否在进程的内存中
	if (flag[a] == false)
	{
		miss[now_time] = 1; //此次标记：缺页
		miss_num++;
		if (now_num == n) //内存已满
		{
			int min_time = 0x3f3f3f, min_num = -1;
			//在内存中的页中，最早被访问时间和最久未使用过的页在内存中的编号
			for (int i = 0; i < now_num; i++)
			{
				if (l_time[memory[i]] < min_time)
				{
					min_time = l_time[memory[i]];
					min_num = i;
				}
			}
			flag[a] = true;            //将当前访问的页“是否在内存中”的标记设为1
			flag[memory[min_num]] = 0; //将被替换的页“是否在内存中”的标记设为0
			memory[min_num] = a;       //当前页替换最久未使用过的页
		}
		else //内存未满
		{
			flag[a] = true;
			memory[now_num] = a; //当前页进入内存的下一个位置
			now_num++;           //内存中页的个数加1
		}
	}
	else
	{
		miss[now_time] = 0; //标记：未缺页
	}
	//保存内存中页面的序列
	for (int i = 0; i < n; i++)
	{
		state[now_time][i] = memory[i];
	}
	l_time[a] = now_time; //更新当前页的被访问时间为当前时间
	now_time++;           //访问完一个页面，当前时间加1
	return;
}

void display()
{
	//输出表头
	cout << "|访问|";
	int left = n - n / 2 - 1;
	int right = n / 2;
	while (left--)
		cout << "    ";
	cout << "序列";
	while (right--)
		cout << "    ";
	cout << "|是否缺页|" << endl;
	for (int i = 0; i < m; i++)
	{
		cout << "|" << setw(4) << vis[i] << "|";
		for (int j = 0; j < n; j++)
		{
			if (state[i][j] != -1)
				cout << setw(4) << state[i][j];
			else
				cout << "    ";
		}
		if (miss[i] == 1) //输出“是”和“否”比较丑
			cout << "|    1   |" << endl;
		else
			cout << "|    0   |" << endl;
	}
	cout << "缺页次数：" << miss_num << endl;
	miss_rate = (double)miss_num / m;
	cout << "缺页率：" << miss_num << "/" << m << "=" << setprecision(2) << miss_rate << endl;
	return;
}

int main()
{
	init();
	for (int i = 0; i < m; i++)
	{
		LRU(vis[i]);
	}
	display();
	return 0;
}

程序运行时的初值及运行结果

初值

分配给该进程的页块数：3

页面访问序列的长度：20

访问序列：1 2 5 6 0 3 6 5 3 6 5 6 0 4 2 7 0 4 3 5

运行结果

image-20211221083746165

思考题

  • 比较LRU和其他置换算法各自的优缺点，能够实现其他置换算法模拟设计，分析内存页面数的变化对各种置换算法命中率。

FIFO算法

与前文LRU算法的实现不同的是，在FIFO算法中，l_time[1001]记录页面进入内存的时间。算法实现如下：

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
//FIFO算法
void FIFO(int a)
{
	//检查请求访问的页是否在进程的内存中
	if (flag[a] == false)
	{
		miss[now_time] = 1; //此次标记：缺页
		miss_num++;
		if (now_num == n) //内存已满
		{
			int min_time = 0x3f3f3f, min_num = -1; //被替换的页的入内存时间最早的页和位置
			//在内存中的页中，先进先出（将入内存时间最早的页移出内存）
			for (int i = 0; i < now_num; i++)
			{
				if (l_time[memory[i]] < min_time)
				{
					min_time = l_time[memory[i]];
					min_num = i;
				}
			}
			flag[a] = true;            //将当前访问的页“是否在内存中”的标记设为1
			flag[memory[min_num]] = 0; //将被替换的页“是否在内存中”的标记设为0
			memory[min_num] = a;       //当前页替换最早入内存的页
		}
		else //内存未满
		{
			flag[a] = true;
			memory[now_num] = a; //当前页进入内存的下一个位置
			now_num++;           //内存中页的个数加1
		}
		l_time[a] = now_time; //更新当前页的入内存时间为当前时间
	}
	else
	{
		miss[now_time] = 0; //标记：未缺页
	}
	//保存内存中页面的序列
	for (int i = 0; i < n; i++)
	{
		state[now_time][i] = memory[i];
	}
	now_time++; //访问完一个页面，当前时间加1
	return;
}

运行结果

image-20211221084045884

NRU算法（CLOCK）

简单的NRU算法是给每一帧关联一个附加位，称为使用位。当某一页首次装入主存时，该帧的使用位设置为1；当该页随后再被访问到时，它的使用位置为0。

对于页替换算法，用于替换的候选帧集合看做一个循环缓冲区，并且有一个指针与之相关联。当某一页被替换时，该指针被设置成指向缓冲区中的下一帧。当需要替换一页时，操作系统扫描缓冲区，以查找使用位被置为0的一帧。每当遇到一个使用位为1的帧时，操作系统就将该位重新置为0；如果在这个过程开始时，缓冲区中所有帧的使用位均为0，则选择遇到的第一个帧替换；如果所有帧的使用位均为1,则指针在缓冲区中完整地循环一周，把所有使用位都置为0，并且停留在最初的位置上，替换该帧中的页。

1
2
int u[1001];      	   //记录页面的使用位
int point; 			   //指针

算法实现如下：

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
//NRU算法
void NRU(int a)
{
	//检查请求访问的页是否在进程的内存中
	if (flag[a] == false)
	{
		miss[now_time] = 1; //此次标记：缺页
		miss_num++;
		int num; //被替换的页的位置
		if (now_num == n) //内存已满
		{
			//指针遍历内存
			while (1)
			{
				if (u[memory[point]] == 1)
				{
					u[memory[point]] = 0; //将使用位为1的页面置为0
				}
				else //若使用位为0，被替换
				{
					num = point;
					flag[a] = true;        //将当前访问的页“是否在内存中”的标记设为1
					flag[memory[num]] = 0; //将被替换的页“是否在内存中”的标记设为0
					memory[num] = a;       //当前页替换最久未使用过的页
					break;
				}
				point++;
				if (point >= n - 1)
				{
					point %= (n - 1);
				}
			}
		}
		else //内存未满
		{
			flag[a] = true;
			memory[now_num] = a; //当前页进入内存的下一个位置
			u[now_num] = 1;	     //使用位：置为1
			now_num++;           //内存中页的个数加1
			point = now_num; 		 //指针指向下一位置
		}
	}
	else
	{
		miss[now_time] = 0; //标记：未缺页
		u[now_num] = 0;	//使用位：置为0
	}
	//保存内存中页面的序列
	for (int i = 0; i < n; i++)
	{
		state[now_time][i] = memory[i];
	}
	now_time++;           //访问完一个页面，当前时间加1
	return;
}

运行结果

image-20211221092549071

最佳置换算法（OPT）（理想置换算法）

无法预知一个进程中的若干页面哪一个最长时间不被访问，故无法实现。

各算法优缺点

最近最久未使用（LRU）

优点：由于考虑程序访问的时间局部性，一般能有较好的性能；实际应用多。
缺点：实现需要较多的硬件支持，会增加硬件成本。

先进先出（FIFO）

优点：先进先出算法实现简单，是最直观的一个算法。
缺点：先进先出的性能最差，因为与通常页面的使用规则不符合，所以实际应用少。

最近不用算法（NRU/CLOCK）

优点：近似于LRU算法，考虑了时间局部性，一般性能比LRU好。
缺点：同样需要较多的硬件支持，会增加硬件成本。

最佳置换算法（OPT）（理想置换算法）

缺点：最佳置换算法是一种理想化算法，具有较好的性能，但是实际上无法实现（无法预知一个进程中的若干页面哪一个最长时间不被访问）；
优点：最佳置换算法可以保证获得最低的缺页率

操作系统课程实验
操作系统实验

本博客所有文章除特别声明外，均为博客作者本人编写整理，转载请联系作者！