OPT, LRU, FIFO页面调度算法的模拟

矫情吗；* 2022-06-06 06:56 155阅读 0赞

#include <iostream>
    #include <cstdlib>
    #include <ctime>
    #include <deque>
    #include <map>
    #include <algorithm>
    
    using namespace std;
    int findLRU(map<int, int> managedMap);
    deque<int> fifo;
    map<int, int> lru;
    map<int, int>opt;
    
    
    const int LEN = 1000;		//要访问的页面总数
    const int BLOCKNO = 3;  //物理块数
    const int INF = 999999; //用于opt算法中在后续找不到该元素所用
    
    int main() {
    	//初始化测试以数据
    	srand((unsigned)time(NULL));
    	int testData[LEN];
    	//int testData[LEN] = {2,3,2,1,5,2,4,5,3,2,5,2};
    	for (int i = 0; i < LEN; i++) {
    		testData[i] = rand() % 5 + 1;
    	}
    
    	//初始化测试数据完毕
    
    	int success=0;	//命中次数
    	int fail = 0;	//缺页次数 + 物理块数
    
    	//FIFO算法
    	for (int i = 0; i < LEN; i++) {
    		auto pos = find(fifo.cbegin(), fifo.cend(), testData[i]);
    		if (pos != fifo.cend())
    			success++;
    		else {
    			fail++;
    			if (fifo.size() < BLOCKNO) {
    				fifo.push_back(testData[i]);
    			}
    			else {
    				fifo.pop_front();
    				fifo.push_back(testData[i]);
    			}
    		}
    	}
    	cout << "测试数据：[" << testData[0];
    	for (int i = 1; i <= LEN-1; i++) {
    		cout << ", " << testData[i];
    	}
    	cout << "]" << endl<<endl;
    	cout << "使用"<<BLOCKNO<<"个物理块"<<endl;
    	cout << "FIFO算法" << endl;
    	cout << "\t缺页数：" << fail - BLOCKNO;
    	cout << "\t缺页率" << (double)fail / LEN;
    	cout << "\t命中率" << (double)success / LEN<<endl<<endl;
    
    	success = 0;
    	fail = 0;
    
    	//LRU算法 lru的map，map->first代表页面值，每过一个循环map->second全部都会+1，那么越久没用到的它的second就越大，那么替换的时候
    	//就把second最大的替换出去
    	for (int i = 0; i < LEN; i++) {
    		auto pos = lru.find(testData[i]);
    		if (pos != lru.end()) {
    			success++;
    			lru[testData[i]] = 0;
    		}
    		else {
    			fail++;
    			if (!(lru.size() < BLOCKNO)) {
    				lru.erase(findLRU(lru));
    				
    			}
    			
    				
    			lru[testData[i]] = 0;
    			
    		}
    		map<int, int>::iterator it=lru.begin();
    		for (; it != lru.end(); it++) {
    			it->second++;
    		}
    	
    		
    	}
    	
    
    	cout << "LRU算法" << endl;
    	cout << "\t缺页数：" << fail - BLOCKNO;
    	cout << "\t缺页率" << (double)fail / LEN;
    	cout << "\t命中率" << (double)success / LEN<<endl<<endl;
    
    	success = 0;
    	fail = 0;
    
    	//OPT算法   与lru相同这个也用map实现，first含义与lru相同，second代表的是下一个相同的页面出现的位置，这个位置越远那么他越先被
    	//替换，这个算法是命中率最高的，但在实际情况中是无法实现的。我们只能假装模拟一下
    	for (int i = 0; i < LEN; i++) {
    		auto pos = opt.find(testData[i]);
    		if (pos != opt.end()) {
    			success++;
    		}
    		else {
    			fail++;
    			if (!(opt.size() < BLOCKNO)) {
    				opt.erase(findLRU(opt));
    			}
    		}
    		//更新second数据
    		int nextPos = -1;
    		for (int j = i + 1; j < LEN; j++) {
    			if (testData[j] == testData[i]) {
    				nextPos = j;
    				break;
    			}
    		}
    		if (nextPos == -1)
    			nextPos = INF;
    		opt[testData[i]] = nextPos;
    
    	}
    
    
    	cout << "OPT算法" << endl;
    	cout << "\t缺页数：" << fail - BLOCKNO;
    	cout << "\t缺页率" << (double)fail / LEN;
    	cout << "\t命中率" << (double)success / LEN;
    
    
    	return 0;
    }
    
    int findLRU(map<int, int> managedMap) {
    	int max = -1;
    	int index;
    	map<int, int> ::iterator it=managedMap.begin();
    	for (; it != managedMap.end(); it++) {
    		if (it->second > max) {
    			max = it->second;
    			index = it->first;
    		}
    	}
    	return index;
    }