操作系统_页面置换算法FIFO,OPT,LRU实现
操作系统第六次上机
在一个请求分页系统中，设页面大小占100个单元，假如系统分配给一个作业的物理块数为3，试求出用FIFO，LRU，OPT三种算法在程序访问过程中所发生的缺页次数及缺页率，每次中断时都需要打印出来或者标示出来。（假设最初页面都在外存）
1. 假定此作业的访问地址序列为202，313，252，111，546，217，444，544，365，223，398，111。
2. 输入任意的访问序列，也必须正确显示。
/*
代码尚需完善：
1.应由用户输入数组，且应根据题目要求对每个数/100，得到页块标号。
2.在动态输入的情况下，通过sizeof,获得数组长度，实现任意输入的处理。
3.FIFO算法实现，why？
4.在OPT实现中，mark属性设置，以及向后遍历的参数设置？
*/
//前三个页块单独处理，需注意前三个页块也可能重复。已做出修改！
#include
usingnamespace std;
int input[12] = { 2,3,2,1,5,2,4,5,3,2,3,1 };
class page
{
public:
int num;
int mark;
page()
{
num = 0;
mark = -1;
}
};
void FIFO()
{
cout<<"------FIFO-----------"< int error = 0; page frame[3]; //页帧 bool flag = true; int check = 0; for (int i = 0; i<3; i++) //处理前三个引用 { for (int k = 0; k if (input[i] == input[k]) flag = false; } if (flag == true) { frame[i].num = input[i]; frame[i].mark = i; error++; cout<< frame[i].num<<" | "; for (int j = 0; j <= i; j++) cout<< frame[j].num<<' '; cout< } else { check++; } } for (int i = 3-check; i<12; i++) { int j; for (j = 0; j<3; j++) if (input[i] == frame[j].num) { cout<< input[i] < break; } if (j == 3) { error++; frame[((error - 1) % 3)].num = input[i]; //换掉最旧的页//？？？？ cout<< input[i] <<" | "; for (int k = 0; k<3; k++) cout<< frame[k].num<<' '; cout< } } cout<<"FIFO:"< cout<<"Error次数:"<< error < cout<<"Frame Error:"<< (error/12.0) < void OPT() { cout<<"------OPT------------"< int error = 0; page frame[3]; bool flag = true; int check = 0; for (int i = 0; i<3; i++) //处理前三个引用{ for (int k = 0; k if (input[i] == input[k]) flag = false; } if (flag == true) { frame[i].num = input[i]; error++; cout<< frame[i].num<<" | "; for (int j = 0; j <= i; j++) cout<< frame[j].num<<' '; cout< } else { check++; } } for (int i = 3-check; i<12; i++) { int j; for (j = 0; j<3; j++) if (input[i] == frame[j].num) { cout<< input[i] < break; } if (j == 3) { error++; for (j = 0; j<3; j++) { frame[j].mark = 21; //？？？ for (int k =20; k >= i; k--) //向后遍历，找到最长时间不用的页//k =20？？？貌似修改后会出问题 { if (frame[j].num == input[k]) frame[j].mark = k; } } if (frame[0].mark>frame[1].mark&&frame[0].mark>frame[2].mark) frame[0].num = input[i]; elseif (frame[1].mark>frame[0].mark&&frame[1].mark>frame[2].mark) frame[1].num = input[i]; else frame[2].num = input[i]; cout<< input[i] <<" | "; for (int k = 0; k<3; k++) cout<< frame[k].num<<' '; cout< } } cout<<"OPT:"< cout<<"Error次数:"<< error < cout<<"Frame Error:"<< (error / 12.0) < } void LRU() { cout<<"------LRU------------"< int error = 0; page frame[3]; bool flag = true; int check = 0; for (int i = 0; i<3; i++)//处理前三个引用 { for (int k = 0; k if (input[i] == input[k]) flag = false; } if (flag == true) { frame[i].num = input[i]; error++; cout<< frame[i].num<<" | "; for (int j = 0; j <= i; j++) cout<< frame[j].num<<' '; cout< } else { check++; } } for (int i = 3-check; i<12; i++) { int j; for (j = 0; j<3; j++) if (input[i] == frame[j].num) { cout<< input[i] < break; } if (j == 3) { error++; for (j = 0; j<3; j++) { frame[j].mark = -1; for (int k = 0; k <= i; k++)//向前遍历，找到最近最少使用的 { if (frame[j].num == input[k]) frame[j].mark = k; } } if (frame[0].mark frame[0].num = input[i]; elseif (frame[1].mark else frame[2].num = input[i]; cout<< input[i] <<" | "; for (int k = 0; k<3; k++) cout<< frame[k].num<<' '; cout< } } cout<<"LRU:"< cout<<"Error次数:"<< error < cout<<"Frame Error:"<< (error / 12.0)< } int main() { FIFO(); OPT(); LRU(); }