1.简介
有的地方比较多余
2.源码
//命中率=1-页面失效次数/页地址流长度。 /*地址按下述原则生成：①50%的指令是顺序执行的； ②25%的指令是均匀分布在(跳转到)前地址部分； ③25%的指令是均匀分布在(跳转到)后地址部分； #具体的实施方法是： A.在[0，119]的指令地址之间随机选取一起点M; B.顺序执行一条指令，即执行地址为M+1的指令； C.在前地址[0，M+1]中随机选取一条指令(跳转到)并执行，该指令的地址为M’; D.顺序执行一条指令，其地址为M’+1； E.在后地址[M’+2，119]中随机选取一条指令(跳转到)并执行； F.重复A—E，直到执行150次指令。*/ #include <iostream> using namespace std; #include <stdlib.h> #include <time.h> typedef struct PAGE { int page; PAGE* next; }PAGE; class List { public: PAGE* head, *tail, *temp, *table; int m; List() { m = 0;table = new(PAGE);head = table;tail = table;temp = table; } void InitList(); int setm(int m); }; void List::InitList() { table = new (PAGE); head = table; table->page = -1; temp = table; for (int i = 2;i <= m;i++) { table = new(PAGE); table->page = -1; temp->next = table; temp = table; if (i == m)table->next = NULL; } tail = table; } int List::setm(int m) { List::m = m; return List::m; } class AddrStream { public: int count, pageNum[150], pageN, i, addr; AddrStream() { count = 0;i = 0;addr = 0;pageN = 0;for (i;i<150;i++) pageNum[i] = 0; }; void Generate(); void outStream(); }; void AddrStream::Generate() { srand((unsigned)time(NULL)); count = 0; i = 0; while (i<150) { if (count == 0) { addr = (int)(120 * rand() / (RAND_MAX + 1)); addr = (addr + 1) % 120; pageN = (int)addr / 10; } if (count == 1) { addr = (int)((addr + 1)*rand() / (RAND_MAX + 1)); pageN = (int)addr / 10; } if (count == 2) { addr = (addr + 1) % 120; pageN = (int)addr / 10; } if (count == 3) { addr = (int)(/*120 - ((120 - (addr + 2))*rand() / (RAND_MAX + 1))*/ rand() % (120 - (addr + 2)) + addr + 2); addr = addr % 120; pageN = (int)addr / 10; } ++count; pageNum[i] = pageN; if (count == 4) { count = 0; } i++; } } void AddrStream::outStream() { for (i = 0;i<150;i++) { cout << pageNum[i] << " "; } cout << endl; } int main() { int False, answer, m, flag;int hit;int a; PAGE* tail, *output, *temp, *table, *t; False = 0; List list; AddrStream address; cout << "请输入用户页面数："; cin >> a; m = list.setm(a); list.InitList(); address.Generate(); address.outStream(); for (int i = 0;i<150;i++) { hit = 0; flag = 0; answer = 1; //answer置1代表队满 tail = list.tail; temp = list.head; t = list.head; table = list.head; output = list.head; while (table != NULL) { if (table->page == -1) { answer = 0; }//answer=0代表队未满 table = table->next; } if (answer == 0) { while (temp != NULL) // 遍历 { if (temp->page == address.pageNum[i]) { hit = 1; //命中则置一 } temp = temp->next; } if (hit == 0) //hit为0则缺页 { False++; int flag2 = 0; do { if (t->page == -1) { t->page = address.pageNum[i]; flag2 = 1; } t = t->next; } while (flag2 != 1); } } if (answer == 1) { while (temp != NULL) { if (temp->page == address.pageNum[i]) { flag = 1;//flag置1代表有命中，置0代表没有命中 } temp = temp->next; } if (flag == 0) { False++; //没有命中则缺页加一 while (t != NULL) { if(t->next!=NULL) t->page = t->next->page; //队列每个元素都前移 t = t->next; } tail->page = address.pageNum[i]; //插入缺的页 } } for (output;output != NULL;output = output->next) cout << output->page << " "; cout << endl; } double sum = 1.0 - False / 120.0; cout << "FIFO算法的命中率为：" << sum << " " << endl; return 0; }
