操作系统-请求页式存储管理中常用页面置换算法模拟

（1）先进先出调度算法（FIFO）
先进先出调度算法根据页面进入内存的时间先后选择淘汰页面，先进入内存的页面先淘汰，后进入内存的后淘汰。本算法实现时需要将页面按进入内存的时间先后组成一个队列，每次调度队首页面予以淘汰。
（2）最近最少调度算法（LRU）
先进先出调度算法没有考虑页面的使用情况，大多数情况下性能不佳。根据程序执行的局部性特点，程序一旦访问了某些代码和数据，则在一段时间内会经常访问他们，因此最近最少用调度在选择淘汰页面时会考虑页面最近的使用，总是选择在最近一段时间以来最少使用的页面予以淘汰。算法实现时需要为每个页面设置数据结构记录页面自上次访问以来所经历的时间。
（3）最近最不常用调度算法（LFU）
由于程序设计中经常使用循环结构，根据程序执行的局部性特点，可以设想在一段时间内经常被访问的代码和数据在将来也会经常被访问，显然这样的页面不应该被淘汰。最近最不常用调度算法总是根据一段时间内页面的访问次数来选择淘汰页面，每次淘汰访问次数最少的页面。算法实现时需要为每个页面设置计数器，记录访问次数。计数器由硬件或操作系统自动定时清零。
（4）最优调度算法（OPT）
该算法所选择的被淘汰页面，将是以后永久不被访问，或者是在未来最长时间内不再被访问的页面。采用最优更新算法通常可以保证获得最低的缺页率。

页式虚拟存储器实现的一个难点是设计页面调度（置换）算法，即将新页面调入内存时，如果内存中所有的物理页都已经分配出去，就要按某种策略来废弃某个页面，将其所占据的物理页释放出来，供新页面使用。本实验的目的是通过编程实现几种常见的页面调度（置换）算法，加深读者对页面思想的理解

(1）设计程序实现以上三种页面调度算法，要求:

①.可以选择页面调度算法类型;

②.可以为进程设置分到物理页的数目，设置进程的页面引用情况，从键盘输入页面序列

③.随时计算当前的页面调度次数的缺页中断率;

④.使用敲键盘或响应WM-TIMER的形式模仿时间的流逝;

⑤.以直观的的形式将程序的执行情况显示在计算机屏幕上;

#include using namespace std;const int DataMax=100;const int BlockNum = 10;int DataShow[BlockNum][DataMax]; // 用于存储要显示的数组bool DataShowEnable[BlockNum][DataMax]; // 用于存储数组中的数据是否需要显示int Data[DataMax]; // 保存数据int Block[BlockNum]; // 物理块int count[BlockNum]; // 计数器int N ; // 页面个数int M;//最小物理块数int ChangeTimes;void DataInput(); // 输入数据的函数void DataOutput();void FIFO(); // FIFO 函数void Optimal(); // Optimal函数void LRU(); // LRU函数int main(int argc, char* argv[]) {	DataInput();	int menu;	while(true) {		cout<>menu;		switch(menu) {			case 1:				FIFO();				break;			case 2:				Optimal();				break;			case 3:				LRU();				break;			default:				break;		}		if(menu!=1&&menu!=2&&menu!=3) break;	}}//*/void DataInput() {	cout<<"请输入最小物理块数：";	cin>>M;	while(M > BlockNum) { // 大于数据个数		cout<<"物理块数超过预定值，请重新输入：";		cin>>M;	}	cout<<"请输入页面的个数：";	cin>>N;	while(N > DataMax) { // 大于数据个数		cout<<"页面个数超过预定值，请重新输入：";		cin>>N;	}	cout<<"请输入页面访问序列："<>Data[i];}void DataOutput() {	int i,j;	for(i=0; i 0){		cout<<"缺页调度次数: "<=3的块，替换后计数值置1，		// 同时其它的块计数值加1 ，成了（1 3 2 ），见下面先进先出程序段	}	for(i=0; i M ) { // 因为i是从0开始记，而M指的是个数，从1开始，所以i+1			//获得要替换的块指针			temp = 0;			for(j=0; j "<< endl;	DataOutput();}void Optimal() {	int i,j,k;	bool find;	int point;	int temp; // 临时变量，比较离的最远的时候用	ChangeTimes = 0;	for(j=0; j M ) { // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1			//获得要替换的块指针			temp = 0;			for(j=0; j "<< endl;	DataOutput();}void LRU() {	int i,j;	bool find;	int point;	int temp; // 临时变量	ChangeTimes = 0;	for(j=0; j M ) { // 因为i是从0开始记，而BlockNum指的是个数，从1开始，所以i+1			//获得要替换的块指针			temp = 0;			for(j=0; j "<< endl;	DataOutput();}

假定进程分配到3个物理块，对于下面的页面引用序列:

7-0-1-2-0-3-0-4-2-3-0-3-2-1-2-0-1-7-0-1

请分别用先进和先出调度算法，最近最少用调度算法，最优调度算法计算缺页中断次数，缺页中断率和缺页调度次数、缺页置换率。