操作系统实验页面调度（内含可运行C/C++代码）

更新了 更新了，都支楞起来

1. 首先，生成一个随机的页面引用串，其中页码的范围为0~9。
2. 将这个随机页面引用串应用到每个算法，记录每个算法引起的缺页次数，列出每次页面置换的换出页序号，计算缺页率。
3. 系统分配给用户的页面帧的数量可选：3~7，具体分配策略可自行定义。
4. 假设采用请求分页（按需调页）。

老规矩，先上代码

#include 
#include 

using namespace std;

//封装页面帧
struct Tem {
	int data;
	int sign;
};
//计算缺页率
double count(double sum,int num) {
	//其中sum为缺页总次数,num为引用串页面的总数
	return sum / num * 100;//将其乘以100，得到百分比的大小
}
//FIFO页面置换算法
double fifo(int* page, Tem* tem, int num, int size) {
	//page数组表示页帧块组，tem数组表示页面引用串
	//num表示页面引用串的页面总数，size表示页面帧的数量
	int n = 0, s = 0,res,flag;
	//n用来记录已占用的页面帧的数量，s用来给页面的标志位赋值，代表来到页面帧的顺序
	//flag标志在页面帧中是否存在，1表示存在，0表示不存在;
	//res用来表示当页面帧满时，FIFO页面置换算法将要换掉的页面帧标号
	double sum = 0;//sum为缺页总数，先初始化为0
	for (int i = 0; i < num; i++) {
		flag = 0;
		//当已占用的页面帧的数量为0，不用去判断页面是否存在
		if (n == 0) {            
			tem[i].data = page[i];
			tem[i].sign = s;
			n++;
			s++;
			cout << endl << "此时存在一些页帧为空,页面" << page[i] << "放入第" << n << "个页帧中" << endl;
			sum++;
		}
		else {//页面帧中已有页面存在
			//循环遍历看页面是否已存在
			for (int j = 0; j < n; j++) {
				if (tem[j].data == page[i]) {
					flag = 1;
					cout << endl << "页面" << page[i] << "已存在" << endl;
					break;
				}
			}
			//页面不在页面帧中
			if (flag == 0) {
				//判断页面帧是否还有空
				if (n < size) {  //页面帧中还有空余帧
					tem[n].data = page[i];
					tem[n].sign = s;
					n++;
					s++;
					cout << endl << "此时存在一些页帧为空,页面" << page[i] << "放入第" << n << "个页帧中" << endl;
					sum++;
				}
				else {//页面帧没有空余帧，需要进行换页
					Tem* t = new Tem;
					int min=1000;
					//循环遍历页面帧中页面的标志位，标志越小表示越早到达页面帧
					for (int p = 0; p < n ; p++) {
						if (tem[p].sign < min) {
							min=tem[p].sign;
							res = p;
						}
						t = &tem[res];
					}
					cout << endl << "此时各页帧均满，换出页面" << t->data << "，并将页面" << page[i] << "放入第" << res + 1 << "个页帧中" << endl;
					sum++;
					t->data = page[i];
					t->sign = s;
					s++;
				}
			}
		}
	}
	return sum;
}
//OPT页面置换算法
double opt(int* page, Tem* tem, int num, int size) {
	//page数组表示页帧块组，tem数组表示页面引用串
	//num表示页面引用串的页面总数，size表示页面帧的数量
	int n = 0, s = 0, flag;
	//n用来记录已占用的页面帧的数量，s用来给页面的标志位赋值，代表来到页面帧的顺序
	//flag标志在页面帧中是否存在，1表示存在，0表示不存在;
	double sum = 0;
	for (int i = 0; i < num; i++) {
		//当已占用的页面帧的数量为0，不用去判断页面是否存在
		flag = 0;
		if (n == 0) {
			tem[i].data = page[i];
			n++;
			cout << endl << "此时存在一些页帧为空,页面" << page[i] << "放入第" << n << "个页帧中" << endl;
			sum++;
		}
		else {//页面帧中已有页面存在
			//循环遍历看页面是否已存在
			for (int j = 0; j < n; j++) {
				if (tem[j].data == page[i]) {
					flag = 1;
					cout << endl << "页面" << page[i] << "已存在" << endl;
					break;
				}
			}
			//页面不在页面帧中
			if (flag == 0) {
				//判断页面帧是否还有空
				if (n = 0; q--) {
						for (m = 0; m < size; m++) {
							//比较页面串和页面帧中的数据是否相等且标志位是否为0
							if (page[q] == tem[m].data && tem[m].sign == 0) {
								tem[m].sign = 1;
								ren++;
								break;
							}
						}
						//当发现页面帧中的某个页面是页面串之前最早使用到的，退出循环遍历
						if (ren == size)
							break;
					}
					//当遍历循环结束，发现页面帧中的某些页面是页面串中之前没有使用到的
				if (ren < size) {
						//循环遍历页面帧中第一个在之前没有使用到的页面
						for (m = 0; m < size; m++) {
							if (tem[m].sign == 0)
								break;
						}
					}
					cout << endl << "此时各页帧均满，换出页面" << tem[m].data << "，并将页面" << page[i] << "放入第" << m + 1 << "个页帧中" << endl;
					tem[m].data = page[i];
					sum++;
				}
			}
		}
	}
	return sum;
}

int main() {
	int num, size;
	double sum, percent;
	cout << "请输入页面应用串的大小：";
	cin >> num;
	int page[30];
	Tem tem[7];
	srand((unsigned int)time(NULL));
	for (int i = 0; i < num; i++) {
		page[i] = rand() % 10;
	}
	cout << "随机产生的页面引用串为：";
	for (int i = 0; i < num; i++)
		cout << page[i] << " ";
	cout <> size;
	cout << endl << "*****************FIFO页面置换算法******************" << endl;
	sum=fifo(page, tem, num, size);
	cout << endl << "缺页次数为：" << sum << endl;
	cout << endl << "缺页率为：" << count(sum, num) <<"%"<< endl;
	cout << endl << "*****************OPT页面置换算法******************" << endl;
	sum = opt(page, tem, num, size);
	cout << endl << "缺页次数为：" << sum << endl;
	cout << endl << "缺页率为：" << count(sum, num) << "%" << endl;
	cout << endl << "*****************LRU页面置换算法******************" << endl;
	sum = lru(page, tem, num, size);
	cout << endl << "缺页次数为：" << sum << endl;
	cout << endl << "缺页率为：" << count(sum, num) << "%" << endl;
	return 0;
}

1、数据类型封装

在后续页面置换中均可采用标志位去 实现，为了简化代码、提高代码的复用性，故封装一个名为Tem的结构体，表示每一个页面帧，其中有页面号，页面标志位。

2、FIFO页面置换算法

FIFO页面置换算法为每一个页面记录了调到内存的时间，当必须置换页面时，选择最旧的页面进行置换。

     假设现在存在一个页面引用串大小为num，存在数量为size的页面帧。可用整型数组去存储页面引用串，即page数组；可用结构体Tem数组去存储页面帧，即tem数组。用一个浮点型变量sum去存储缺页总次数，并作为函数的返回值。

从页面引用串的开始依次遍历，每取到一个页面都先去判断页面帧中是否有被占有。若没有被占有，即每一个页面帧均为空，缺页总次数sum加1，该页面直接进入第一个页面帧中，并进行相应输出。若有被占有，则对已被占有页面帧进行循环遍历看该页面是否在。若存在则输出该页面已存在，不存在则判断当前所有的页面帧是否全部被占有。若未全部占有，缺页总次数sum加1，该页面进入第一个空页面帧中，并进行相应输出。若全部被占有，则通过标志位循环遍历找出最早进入页面帧的页面，将其置换出来，再将缺页总次数sum加1，该页面进入当前的空页面帧中，并进行相应输出。

此时标志位的设置就尤为重要，我是通过一个整型变量s来对标志位进行赋值，s的初值为0，并且在每一个页面进入页面帧后s都会进行自动加1。这样一来，标志位就可以作为页面帧中页面进入的时间。最后返回缺页总次数sum。

3、OPT页面置换算法

  OPT页面置换算法当必须置换页面时，选择最长时间不会使用的页面进行置换。

     假设现在存在一个页面引用串大小为num，存在数量为size的页面帧。可用整型数组去存储页面引用串，即page数组；可用结构体Tem数组去存储页面帧，即tem数组。用一个浮点型变量sum去存储缺页总次数，并作为函数的返回值。

从页面引用串的开始依次遍历，每取到一个页面都先去判断页面帧中是否有被占有。若没有被占有，即每一个页面帧均为空，缺页总次数sum加1，该页面直接进入第一个页面帧中，并进行相应输出。若有被占有，则对已被占有页面帧进行循环遍历看该页面是否在。若存在则输出该页面已存在，不存在则判断当前所有的页面帧是否全部被占有。若未全部占有，缺页总次数sum加1，该页面进入第一个空页面帧中，并进行相应输出。若全部被占有，则通过标志位循环遍历找出当前页面之后最近不使用的页面进入页面帧的页面，将其置换出来，再将缺页总次数sum加1，该页面进入当前的空页面帧中，并进行相应输出。

此时标志位的设置就尤为重要，我是将所有页面帧中的页面标志位均置为0，默认在将来不使用。除了标志位外，还应考虑页面帧中的页面可能在将来使用也可能不使用。我设置了一个循环，从当前页面的后面一直遍历到页面引用串结束，当发现页面帧中的某个页面是页面串中将来最晚使用到的，提前结束循环遍历。或者当遍历循环结束，发现页面帧中的某些页面是页面串中之后没有使用到的，则还需通过循环遍历页面帧中第一个在之后没有使用到的页面。最后返回缺页总次数sum。

4、LRU页面置换算法

 LRU页面置换算法当必须置换页面时，选择最近最少使用的页面进行置换。

   假设现在存在一个页面引用串大小为num，存在数量为size的页面帧。可用整型数组去存储页面引用串，即page数组；可用结构体Tem数组去存储页面帧，即tem数组。用一个浮点型变量sum去存储缺页总次数，并作为函数的返回值。

从页面引用串的开始依次遍历，每取到一个页面都先去判断页面帧中是否有被

占有。若没有被占有，即每一个页面帧均为空，缺页总次数sum加1，该页面直接进入第一个页面帧中，并进行相应输出。若有被占有，则对已被占有页面帧进行循环遍历看该页面是否在。若存在则输出该页面已存在，不存在则判断当前所有的页面帧是否全部被占有。若未全部占有，缺页总次数sum加1，该页面进入第一个空页面帧中，并进行相应输出。若全部被占有，则通过标志位循环遍历找出当前页面之前最近没有使用的页面进入页面帧的页面，将其置换出来，再将缺页总次数sum加1，该页面进入当前的空页面帧中，并进行相应输出。

   此时标志位的设置就尤为重要，我是将所有页面帧中的页面标志位均置为0，默认在之前不使用。除了标志位外，还应考虑页面帧中的页面可能在之前使用也可能不使用。我设置了一个循环，从当前页面的前面面一直遍历到页面引用串开始，当发现页面帧中的某个页面是页面串中之前最晚使用到的，提前结束循环遍历。或者当遍历循环结束，发现页面帧中的某些页面是页面串中之前没有使用到的，则还需通过循环遍历页面帧中第一个在之前没有使用到的页面。最后返回缺页总次数sum。

5、缺页率计算函数

将各页面置换算法返回的缺页总数sum和页面引用串的大小num作为函数参数，通过返回 (sum/num)*100 得到缺页率的百分比。

1、随机产生一个页面引用串并设置页帧数量，如下图所示

2、FIFO页面置换算法

页面引用串为5 3 3 3 8 6 1 1 9 3 9 0 8 2 9，页帧数量为4

       实验结果正如FIFO页面置换算法的原理一样，当出现各页帧已满需要换出页面时，换掉先进入页帧的页面。例如：在一开始是页面5先进入第一个页帧，当各页帧满时，换出页面5将页面1换进。

3、OPT页面置换算法

页面引用串为5 3 3 3 8 6 1 1 9 3 9 0 8 2 9，页帧数量为4

   实验结果正如OPT页面置换算法的原理一样，当出现各页帧已满需要换出页面时，换掉各页帧中将来最近不使用的页面。例如：页帧中页面5和页面6在将来均不使用，当各页帧满时，通过遍历第一个，故换出页面5将页面1换进。

4、LRU页面置换算法

页面引用串为5 3 3 3 8 6 1 1 9 3 9 0 8 2 9，页帧数量为4

实验结果正如LRU页面置换算法的原理一样，当出现各页帧已满需要换出页面时，换掉各页帧中之前最近不使用的页面。例如：页帧中页面5相比于其他页面是最长时间未使用的，当各页帧满时，换出页面5将页面1换进。