操作系统_页面置换算法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算法实现。

4.在OPT实现中，mark属性设置，以及向后遍历的参数设置。

代码如下：

#include

using namespace 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-----------" << endl;

int error = 0;

page frame[3];  //页帧  

bool flag = true;

int check = 0;

for (int i = 0; i<3; i++)   //处理前三个引用  

{

for (int k = 0; k < i; 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 << endl;

}

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] << endl;

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 << endl;

}

}

cout << "FIFO:" << endl;

cout << "Error次数:" << error << endl;

cout << "Frame Error:" << (error/12.0) << endl << endl;

}

void OPT()

{

cout << "------OPT------------" << endl;

int error = 0;

page frame[3];

bool flag = true;

int check = 0;

for (int i = 0; i<3; i++)   //处理前三个引用  

{

for (int k = 0; k < i; 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 << endl;

}

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] << endl;

break;

}

if (j == 3)

{

error++;

for (j = 0; j<3; j++)

{

frame[j].mark = 21;  //？？？

for (int k =20; k >= i; k--)  //

{

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];

else if (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 << endl;

}

}

cout << "OPT:" << endl;

cout << "Error次数:" << error << endl;

cout << "Frame Error:" << (error / 12.0) << endl << endl;

}

void LRU()

{

cout << "------LRU------------" << endl;

int error = 0;

page frame[3];

bool flag = true;

int check = 0;

for (int i = 0; i<3; i++)//  

{

for (int k = 0; k < i; 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 << endl;

}

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] << endl;

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];

else if (frame[1].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 << endl;

}

}

cout << "LRU:" << endl;

cout << "Error次数:" << error << endl;

cout << "Frame Error:" << (error / 12.0)<< endl << endl;

}

int main()

{

FIFO();

OPT();

LRU();

}

（以上为实现页面置换算法FIFO,OPT,LRU的代码）