对页面置换算法的一些实现

吐槽

​ 写了好几天（其实是因为这几天放假出去van导致进程无限等待系统调用了······）

​ 然后反复思考就是不同算法之间的差异，以及如何实现。实现的时候完全没有查阅CSDN，是按照自己的想法以及算法的思路直接实现的。其实、貌似、写这个也没有很难，就是自己老是吓自己，怀疑自己是不是写错了，然后持续debug······

​ 果然还是在4.6号（清明假放完后的第一个工作日）完成了（乐

页面置换算法

是因为出现了缺页异常，需要调入新页面且内存已满，置换算法选择被置换的物理页面。

在此强调一下，这里不介绍算法的详细知识，这里只是实现。

分类

局部页面置换算法

【分配给一个进程的物理页面数已确定】

1. 最优页面置换算法（需要预知未来，难以实现）

2. 先进先出算法（FIFO）

3. 最近最久未使用算法（LRU）

4. clock算法（FIFO和LRU的折中）

5. 最不常用算法

全局页面置换算法

【置换页面的选择范围是所有可换出的页面】

工作集算法

缺页率算法

【虽然最优页面置换算法难以实现，但是它可以作为评价其他置换算法性能的一个依据。比较最有毕竟代表的是最佳的solution】

FIFO-队列实现

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100;
int n, a[N];

//FIFO--施工完成
bool Search(queue<int> q, int value) {//检查value是否在queue内
	bool flag = false;
	for (int i = 0; i < q.size(); i++) {
		if (q.front() == value && !flag) flag = true;
        else {
			int a = q.front();
			q.push(a);
			q.pop();
		}
	}
	return flag;
}


void FIFO(int *a, int frame_size, int a_size) {
	int lack = 0;
	queue<int> q;
	for (int i = 0; i < a_size; i++) {
		if (!Search(q, a[i])) { //该元素不在q内且目前队列中运行的页帧小于限定
			if (q.size() == frame_size )q.pop();
			q.push(a[i]);
			lack++;
		}
	}
	cout << "缺页次数:" << lack ;
}

int Input() {
	int sum = 0, i = 0;
	char c;
	//输入是资源的一个物理帧号列表+访问页表的一个顺序
	cout << "该进程分配了几个页帧？" << endl;
	cin >> n;
	cout << "其访问序列是？" << endl;
	getchar();
	while (scanf("%c", &c) ) {
		char c0;
		if (c0 >= '0' && c0 <= '9') {
			sum = sum * 10 + (c0 - '0');
			if (c < '0' || c > '9') {
				a[i] = sum;
				sum = 0;
				i++;
			}
		}
		if (c == '\n')break;
		c0 = c;
	}
	return i;
}

int main() {
	int size = Input();
	FIFO(a, n, size);
	return 0;
}

LRU-队列实现

其实实现比较简单，但是因为自己写错了show（）函数，然后不断怀疑自己是不是写错了QAQ，然后就调试了挺久。。。

这个show（）函数就是显示队列 q 的元素。

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
const int N = 100;
int n, a[N];
//LRU--施工完成

void LRU(int *a, int frame_size, int a_size) {
	int lack = 0;
	queue<int> q;
	for (int i = 0; i < a_size; i++) {
		if (!Search(q, a[i])) { //该元素不在q内
			if (q.size() == frame_size)q.pop();
			q.push(a[i]);
			lack++;
		} else { //该元素在queue内，把其提到queue的队尾
			const int elem = a[i];
			for (int j = 0; j <= q.size(); j++) {
				int num = q.front();
				q.pop();
				if (num == elem) continue;
				q.push(num);
			}
			q.push(elem);
		}
	}
	cout << "缺页次数:" << lack ;
}

int main() {
	int size = Input();//FIFO中提及
	LRU(a, n, size);
	return 0;
}

当时直接在FIFO的cpp文件上修改得到，所以cpp文件名是FIFO。

LFU/NFU算法（改进Aging算法）

LFU/NFU：Least/Not frequently uesd

均最不常用算法。这里的实现是改进后的老化算法。

老化算法记录了访问频率以及历史信息；同时其计数器count只有有限位数。为贴合书上的一个字节，选择char类型（-127·128）



2

8

2^8







2










8












。

问题就是，它的时钟滴答会一次性访问好几个页面（那我的理解就是把 将使用的页面序列 按照 T = n 分为不同的组）

【一些在实现时的笨蛋问题】

：

1. 何时发生缺页中断？

   莫非是分为每时钟滴答一下，看看访问几个页；
   
   【给定一个列表，和上述一样】
   

   再根据T是多少，看这几个时钟滴答内是否有无页没有访问？

2. 如何理解时钟滴答？

   书上的示例中每个时钟滴答的访问页面数都是不一样的。

   下面显示的页面也是所有的页号的count，我是真的不知道什么时候发生缺页中断。

3. 设置List数组-按照frame_size设置？

   这个疑问也是和缺页中断息息相关。按理说每一个页号都会有一个List，那么类似于往常那样的缺页中断（就是依据L_size判定在List内的是否有访问的页面）就不可能实现了。
   
   【像往常那样写就太短了，完全不能显示其算法的特征】
   

想法：缺页是置换访问次数最小的页面

方法：每个页面设置访问计数，缺页时置换计数最小的页面

#include <iostream>
#include <algorithm>
#include <bitset>
using namespace std;
const int N = 100;

struct List {
	int data;
	unsigned char count;
};

struct Clock {
	int data[N];//访问了哪些页号，默认设置为次数为1.
	int size;//该时钟滴答访问的页号数
};

int L_size;//L的大小
int Clock_size;//多少个时钟滴答
List L[N];//存储访问的页号
Clock Cl[N];//存储每一次时钟滴答会访问的页面


void Input() {
	cout << "List的大小是？(假设初始时已装满List)" << endl; //这表明该算法是在中间时刻开始计算
	cin >> L_size;

	cout << "现在装载的数据是？ （页号+count）" << endl;
	for (int i = 0; i < L_size; i++) {
		L[i].data = i;
		L[i].count = 0;
	}

	cout << "一共有多少次时钟滴答？" << endl; //我不知道该不该写这个？
	cin >> Clock_size;
	for (int i = 0; i < Clock_size; i++) {
		cout << "第" << i + 1 << "次:" ;
		cin >> Cl[i].size; //每次时钟滴答会访问哪些页面，默认访问一次
		for (int j = 0; j < Cl[i].size; j++)cin >> Cl[i].data[j];
	}
}

int Search(int value) {
	for (int i = 0; i < L_size; i++) {
		if (value == L[i].data)
			return i;//返回找到的地址
	}
	return -1;
}

void RightSet() {
	for (int i = 0; i < L_size; i++) {
		cout << "L[" << i << "]:" << L[i].data << "  cnt:" << bitset<8>(L[i].count) << endl;
		L[i].count >>= 1;
	}
	cout << "================================" << endl;
}

int FindMin(Clock *Cl, int i) {
	int min = Cl[i].data[0];
	int k;
	for (k = 0; k < L_size; k++) {
		if (Cl[i].data[k] < min)
			min = Cl[i].data[k];
	}
	return k;//返回最小值的地址
}

void Aging() {
	int lack = 0;
	for (int i = 0; i < Clock_size; i++) {
		for (int j = 0; j < Cl[i].size; j++) {
			int opt = Search( Cl[i].data[j]);
			if (opt >= 0) {
				L[opt].count += 128; //2^7
			} else {
				lack++;//缺页发生 找到List中最小的并替换
				int min_add = FindMin(Cl, i);
				L[min_add].data = Cl[i].data[j];
				L[min_add].count = 128;
			}
		}
		RightSet();
	}
}

int main() {
	Input();
	Aging();
	return 0;
}
/*一组输入
6
5
4
0 2 4 5
3
0 1 4
4
0 1 3 5
2
0 4
2
1 2
*/

得到的结果也是想配合书上的答案啦。

Clock-结构体实现

#include <iostream>
#include <algorithm>
#include <stack>
#include <queue>
using namespace std;
const int N = 100;

int n, a[N], ptr = 0; //模仿指针
//Clock--施工完成
//环形链表利用数组实现，但是这个指针的变换，或许可以使用全局变量构造
//找到该数组内包含a[i]--不会发生中断，将R[a[i]]置为1.
//不包含a[i]--找到目前指针所指的位置，若是0，就更换data为a[i];1就置1为0，指针指向下一个

struct List {
	int data;//存值
	int R;// 0/1
};

int Search(List *L, int L_size, int value) {
	for (int i = 0; i < L_size; i++) {
		if (L[i].data == value)return i;
	}return -1;
}

void Clock(int *a, int frame_size, int a_size) {
	int lack = 0, L_size = 0;
	List L[frame_size];
	for (int i = 0, j = 0; i < a_size; i++) {
		//cout << endl << endl;
		int opt = Search(L, L_size, a[i]);
		//cout << "---Search --a[i] " << a[i] << " ：result " << opt << endl;
		if (opt != -1)
			L[opt].R = 1;//找到了
		else { //不包含a[i]
			//cout << "L size:" << L_size << endl;
			lack++;
			if (L_size < frame_size) {
				L[j].data = a[i];
				L[j].R = 1;
				L_size++;
				j++;
			} else if (L_size == frame_size) { //满了且不包含
				while (true) {
					if (ptr == L_size )ptr = 0;
					if (L[ptr].R == 0) {
						L[ptr].data = a[i];
						L[ptr].R = 1;
						ptr++;
						break;
					} else L[ptr].R = 0;
					ptr++;
				}
			}
		}
	}
	cout << "缺页次数：" << lack;
}

int main() {
	int size = Input();
	Clock(a, n, size);
	return 0;
}

工作集页面置换算法-队列实现

方法：换出不在工作集

#include <iostream>
#include <queue>
using namespace std;
//工作集页面置换算法
const int N = 100;
int T = 0, a[N] = {0};

struct frame {
	int data;
	int lasting_time;//存活时间
};

int Input() {
	int sum = 0, i = 0;
	char c;
	//输入是资源的一个物理帧号列表+访问页表的一个顺序
	cout << "该进程窗口大小是？" << endl;
	cin >> T;
	cout << "其访问序列是？" << endl;
	getchar();
	while (scanf("%c", &c) ) {
		char c0;
		if (c0 >= '0' && c0 <= '9') {
			sum = sum * 10 + (c0 - '0');
			if (c < '0' || c > '9') {
				a[i] = sum;
				sum = 0;
				i++;
			}
		}
		if (c == '\n')break;
		c0 = c;
	}
	return i;
}

bool Search(queue<frame> q, int value) {//检查value是否在queue内
	bool flag = false;
	for (int i = 0; i < q.size(); i++) {
		//cout << "Data: " << q.front().data << " lasting time: " << q.front().lasting_time << endl;
		if (q.front().data == value && !flag) flag = true;
		else {
			frame a = q.front();
			q.push(a);
			q.pop();
		}
	}
	return flag;
}

void Lasting_time(queue<frame> &q) {//减少时间、重组队列
	for (int i = 0; i < q.size(); i++) {
		frame b = q.front();
		q.pop();
		b.lasting_time -= 1;

		if (b.lasting_time > 0)q.push(b);
	}
}

void WorkingSet(const int &window_size, const int &a_size) {
	int lack = 0;
	queue<frame>q;
	for (int i = 0; i < a_size; i++) {
		if (Search(q, a[i])) { //把队列中的某值取出放在队尾，并修改lasting_time
			for (int j = 0; j < q.size(); j++) {
				if (q.front().data != a[i]) {
					frame b = q.front();
					q.push(b);
				}
				q.pop();//所有进入该语句的都要pop
			}
		} elselack++;//发生缺页：

		Lasting_time(q);//所有进入循环的都要让这个元素进入队列
		frame c;
		c.data = a[i];
		c.lasting_time = 3;
		q.push(c);
	}
	cout << "Lack:" << lack;
}

int main() {
	int a_size = Input();
	WorkingSet(T, a_size);
}

缺页率页面置换算法-string实现

因为想着如果是string的话，可以非常方便的利用库函数进行生成子串，查找子串···

#include <iostream>
#include <cstring>
using namespace std;
//工作集页面置换算法
const int N = 100;
int current = 0, last = 0, T = 0;
char a[N];

void Input() {
	char c;
	int i = 0;
	cout << "窗口时间：";
	cin >> T;
	getchar();//这个非常重要、不要忘记、不然你就寄了
	cout << "访问序列：";
	scanf("%c", &c);
	while (c != '\n') {
		if (c >= '0' && c <= '9') {
			a[i] = c;
			i++;
		}
		scanf("%c", &c);
	}
}

void FrameDefaultRate() {
	int lack = 0;
	string s(a);
	string vis_frame;
	for (int i = 0; i < strlen(a); i++) {
		if (vis_frame.find(a[i]) == vis_frame.npos) { //未查找到
			lack++;
			current = i;

			if ((current - last) > T) { //置换在这段时间内未引用的页
				vis_frame = s.substr(last, current - last + 1);
			} else { //增加缺失页到常驻集中
				string ssr(1, a[i]);
				vis_frame += ssr;
			}
			last = current;
		}
	}
	cout << "Lack：" << lack;
}

int main() {
	Input();
	FrameDefaultRate();
}

【但是这么做的话会有一个问题：假如以数字为页号，最多是0-9】

所以解决的方法是：

老方法

！设置int数组（可以表示A-Z、a-z以及数字）

但是都差不多，有兴趣自己实现哈


(虽然这么说但是基本上是一句废话）