赞
踩
(1)data.txt文本文件:
图1 输入文件
将页面引用串输入到名为data.txt的文本文件中,以空格隔开。
(2)各种置换算法的输出结果:
图2 OPT页面置换算法运行结果
图3 FIFO页面置换算法运行结果
图4 LRU页面置换算法运行结果
图5 Clock页面置换算法运行结果
图6 LRU页面置换算法运行结果
#include <iostream> #include <vector> #include <string> #include <fstream> #define random(a,b) (rand()%(b-a)+a) using namespace std; // 总虚页数 int t; // 实页数 int size; // 序列 vector<int> v; // 7 0 1 2 0 3 0 4 2 3 0 3 2 1 2 0 1 7 0 1 void print(vector<pair<int, vector<int>>> res, int lackPageNum, int totalNum){ for (int i = 0; i < size; ++i) { // 遍历每一个序列的第i个数 for (int j = 0; j < res.size(); ++j) { printf("|"); pair<int, vector<int>> cur = res[j]; int isLack = cur.first; vector<int> v = cur.second; if(!isLack || v.size() < (i + 1)){ printf(" "); }else{ printf("%3d", v[i]); } printf(" "); } puts("|"); } printf("缺页数为:%d\n", lackPageNum); printf("命中数:%d\n", (totalNum - lackPageNum)); printf("缺页率为:%.3f%%\n", (lackPageNum * 100.0 / totalNum)); printf("命中率为:%.3f%%\n", ((totalNum - lackPageNum) * 100.0 / totalNum)); } void FIFO(){ // 结果<是否缺页,页面> vector<pair<int, vector<int>>> res; // 上一页 vector<int> pre; // 判断是否缺页的 bool flag; int lackPageNum = 0; for(int num: v){ flag = true; // 是否缺页 for (int i = 0; i < pre.size(); ++i) { if(num == pre[i]){ flag = false; } } if(!flag){ res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end()))); continue; } lackPageNum++; if(pre.size() < size){ pre.push_back(num); }else{ // 缺页则换出队头 pre.erase(pre.begin()); pre.push_back(num); } res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end()))); } printf("FIFO(先进先出)算法:\n"); print(res, lackPageNum, t); puts(""); puts(""); } void LRU(){ // <是否缺页,页面> vector<pair<int, vector<int>>> res; // 上一页 vector<int> pre; // 判断是否缺页的 bool flag; // 缺页数 int lackPageNum = 0; // 当前页在队中那个位置 int idx = 0; for(int num: v){ flag = true; // 是否缺页 for (int i = 0; i < pre.size(); ++i) { if(num == pre[i]){ flag = false; idx = i; } } if(!flag){ // 换到队头 pre.erase(pre.begin() + idx); pre.insert(pre.begin(), num); res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end()))); continue; } lackPageNum++; if(pre.size() < size){ pre.insert(pre.begin(), num); }else{ // 缺页则换出队尾 pre.erase(pre.end()-1); pre.insert(pre.begin(), num); } res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end()))); } printf("LRU(最近最久未使用)算法:\n"); print(res, lackPageNum, t); puts(""); puts(""); } void OPT(){ // <是否缺页,页面> vector<pair<int, vector<int>>> res; // 上一页 vector<int> pre; // 判断是否缺页的 bool flag; // 缺页数 int lackPageNum = 0; for(int k = 0; k < v.size(); k++){ int num = v[k]; flag = true; // 是否缺页 for (int i = 0; i < pre.size(); ++i) { if(num == pre[i]){ flag = false; } } if(!flag){ res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end()))); continue; } lackPageNum++; if(pre.size() < size){ pre.push_back(num); }else{ // 最后面的数在v中的位置 int last = -1; // 最后面的数在pre中的位置 int idx; // 当前pre[i] 是否存在与v中 bool isExit; // 缺页则换出pre中在v序列最后面的或者不在后面的序列的 for (int i = 0; i < pre.size(); ++i) { isExit = false; for (int j = k + 1; j < v.size(); ++j) { if(pre[i] == v[j]){ isExit = true; if(j > last){ idx = i; last = j; } break; } } // 当前pre[i] 根本不在v中,则直接退出循环 if(!isExit){ idx = i; break; } } pre.erase(pre.begin() + idx); pre.insert(pre.begin()+ idx, num); } res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end()))); } printf("OPT(最佳)置换算法:\n"); print(res, lackPageNum, t); puts(""); puts(""); } void setToOne(int &num, int idx){ num = num + (1 << idx); } // 统一右移 void rightMove(vector<pair<int, int>> & visNum){ // puts(""); for(pair<int, int> &p: visNum){ // printf("%d ", p.second); p.second = p.second >> 1; } // puts(""); } // 判断是否在visNum中 bool isExit(vector<pair<int, int>> & visNum, int num){ for(pair<int, int> &p: visNum){ if(p.first == num){ return true; } } return false; } // 找到某个数在队列中的索引 int findIdx(vector<pair<int, int>> & visNum, int num){ for (int i = 0; i < visNum.size(); ++i) { pair<int, int> p = visNum[i]; if(p.first == num){ return i; } } return -1; } // 找到 freq 最小的在 pre 中的位置 int findMinIdx(vector<pair<int, int>> visNum, vector<int> pre){ int id = -1; int min = (1 << 31) - 1; for (int i = 0; i < pre.size(); ++i) { for (int j = 0; j < visNum.size(); ++j) { pair<int, int> p = visNum[j]; if(pre[i] == p.first && p.second < min){ id = i; min = p.second; } } } return id; } void LFU(){ vector<pair<int, vector<int>>> res; vector<int> pre; // 记录访问频率<数, 频率> vector<pair<int, int>> visNum; int lackPageNum = 0; for (int num: v) { bool flag = true; rightMove(visNum); for (int i = 0; i < pre.size(); ++i) { if(pre[i] == num){ flag = false; } } if(!flag){ int idx = findIdx(visNum, num); setToOne(visNum[idx].second, 30); res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end()))); continue; } lackPageNum++; bool isEx = isExit(visNum, num); if(pre.size() < size){ pre.push_back(num); visNum.push_back({num, (1 << 30)}); }else{ if(!isEx){ visNum.push_back({num, (1 << 30)}); }else{ int idx = findIdx(visNum, num); setToOne(visNum[idx].second, 30); } int idx = findMinIdx(visNum, pre); pre.erase(pre.begin() + idx); pre.push_back(num); } res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end()))); } printf("LFU(最少使用)置换算法:\n"); print(res, lackPageNum, t); puts(""); puts(""); } // 1 3 4 2 5 6 3 4 7 void CLK(){ vector<pair<int, vector<int>>> res; vector<int> pre; int vis[t + 5]; int lackPageNum = 0; bool flag; // 指针 int idx = 0; for (int num: v) { flag = true; for (int i = 0; i < pre.size(); ++i) { if(pre[i] == num){ vis[i] = 1; flag = false; } } if(!flag){ res.push_back(make_pair(0, vector<int>(pre.begin(), pre.end()))); continue; } lackPageNum++; if(pre.size() < size){ pre.push_back(num); vis[pre.size()-1] = 1; }else{ while (true){ if(!vis[idx]){ pre.erase(pre.begin() + idx); pre.insert(pre.begin() + idx, num); vis[idx] = 1; idx = (idx + 1) % size; break; } vis[idx] = 0; idx = (idx + 1) % size; } } res.push_back(make_pair(1, vector<int>(pre.begin(), pre.end()))); } printf("NRU(最近未用)置换算法:\n"); print(res, lackPageNum, t); puts(""); puts(""); } void init1(){ printf("可用物理块大小:"); scanf("%d", &size); printf("调入序列长度:"); scanf("%d", &t); int num; printf("请输入调入页面序列:"); printf(""); for (int i = 0; i < t; ++i) { scanf("%d", &num); v.push_back(num); } } void init2(){ ifstream df("../data.txt"); if (!df.is_open()){ cout << "Error opening file"; exit (1); } df >> size; df >> t; int num; for (int i = 0; i < t; ++i) { df >> num; v.push_back(num); } df.close(); } void init3(){ int a = 1, b = 10; size = 3; t = 20; int num; for (int i = 0; i < t; ++i) { num = random(a, b); v.push_back(num); } } int main(){ // int num = 1; // setToOne(num, 4); // cout << num; // init1(); init2(); // init3(); printf("\n\n\n访问序列:"); for (int i = 0; i < v.size(); ++i) { printf("%d ", v[i]); } puts(""); FIFO(); LRU(); OPT(); LFU(); CLK(); // Test // vector<pair<int, int>> vp; // vp.push_back({3, 8}); // rightMove(vp); // setToOne(vp[0].second, 30); // cout << vp[0].second; return 0; }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。