LRU算法 发表于 2006-04-27 | 更新于: 2017-10-12 | | 123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145//LRU algorithm//author:chillyCreator//in the page_information, the bigger number means the newer page.//if the number in the page_information is -1, it means no page is in this position. #include<iostream>using namespace std;bool isNotIn(int p_page_num);bool isNotFull(int& position);void insert(int p_page_num,int position);int delOldPage();const int MAX_INT = 32767;int process_num;//the total number of process pagesint page_size;//the total number of pagesint page_num=0;//the number of page which in the page array int miss=0;//int* page_information;//the page information arrayint* page;//the page arrayint old=0;//how old is a page?int main(){ cout << "how many pages of processes ?"<<endl; cin >> process_num ; cout << "how many pages in the memory?"<<endl; cin >> page_size; page_information = new int[page_size]; page = new int[page_size]; int i; for(i=0; i<page_size; i++) { page[i] = -1; page_information[i] = -1; } int user_test; cout << "input 1 is user test, 2 is auto test"<<endl; cin >> user_test; switch(user_test) { case 1: for(i=0; i < process_num; i++) { int process_page_num; cin >> process_page_num; cout <<"input process page num is :" <<process_page_num<<endl; if(isNotIn(process_page_num)) { miss++; int temp_position; if(isNotFull(temp_position)) { insert(process_page_num,temp_position); page_num++; } else { temp_position = delOldPage(); insert(process_page_num,temp_position); } } } break; default: for(i=0; i < process_num; i++) { int process_page_num = rand(); cout << process_page_num<<endl; if(isNotIn(process_page_num)) { miss++; int temp_position; if(isNotFull(temp_position)) { insert(process_page_num,temp_position); page_num++; } else { temp_position = delOldPage(); insert(process_page_num,temp_position); } } } break; } cout <<"miss is " <<miss << "/t the total process num is "<<process_num<<endl; cout << endl; cout <<"the miss percentage is miss/process_num = "<<double(miss)/process_num<<endl; return 0;}//the process page is in the page array?;bool isNotIn(int p_page_num){ for(int i=0; i<page_size; i++) { if(page[i]==p_page_num) return false; } return true;}//the page array is full or not.//and return the empty positionbool isNotFull(int& position){ if(page_size <= page_num) return false; int i; for(i=0; i<page_size; i++) { if(page_information[i]==-1) break; } position = i; return true;}//insert a process page to the page in an empty position.//and the function protect the primite: old from flowover error. void insert(int p_page_num,int position){ old++; if(old==MAX_INT) { old = 1; for(int i=0; i<page_size; i++) { if(page_information[i]!=-1) page_information[i] = old; } } old++; page[position] = p_page_num; page_information[position] = old;}int delOldPage(){ int i; int min=page_information[0],min_i=0; for(i=1; i<page_size; i++) { if(min > page_information[i]) { min = page_information[i]; min_i = i; } } return min_i;} 本文作者: 帐前卒 本文链接: http://chillyc.info/2006/679953/ 版权声明: 本博客所有文章除特别声明外,只能复制超链接地址,且必须注明出处!