操作系统原理请求分页系统中的置换算法

本文主要是介绍操作系统原理请求分页系统中的置换算法，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

---

一、 题目要求

1.通过如下方法产生一指令序列，共320条指令。
A. 在[1,32k-2]的指令地址之间随机选取一起点M,访问M；
B. 顺序访问M+1；
C. 在[0,M-1]中随机选取M1，访问M1；
D. 顺序访问M1+1；
E. 在[M1+2,32k-2]中随机选取M2，访问M2；
F. 顺序访问M2+1；
G. 重复 A—F，直到执行320次指令。
2. 指令序列变换成页地址流设：（1）页面大小为1K；
（2）用户虚存容量为32K。
3. 计算并输出下述各种算法在不同内存页块(页块个数范围:8-32)下的命中率。
A. 先进先出（FIFO）页面置换算法
B. 最近最久未使用（LRU）页面置换算法
C. 最佳（Optimal）页面置换算法
（命中率=1-页面失效次数/页地址流长度）

二、程序功能及设计思路

程序功能：能随机产生指令序列，并实现三种置换算法。
设计思路：指令序列通过srand函数生成种子实现。
先进先出（FIFO）页面置换算法，比较简单，如果当前页块中没有当前调入的页面，则直接将最早进来的页面淘汰。通过vector自带的erase()和push_back()即可实现。
最近最久未使用（LRU）页面置换算法 ，需要将停留在页块中时间最久的页面淘汰。于是创建了一个PAGE结构体，结构体中含有页名和停留在页块中的时间两变量。每次添加新的页面时，停留在页块中的时间+1。如果添加的页面在页块中已经存在，则将该页面时间清零，否则则找出停留在页块中时间最大的页面，将其淘汰，添加新的页面。
最佳（Optimal）页面置换算法，该算法选择的被淘汰页面，将是以后永远不使用的，或许是在最长（未来）时间内不再被访问的页面，所以每次新的页面调入时，记录并比较停留在页块中页面再次调入页块的时间，选出时间最大的淘汰。

三、数据结构及算法设计

（1）设计：数据结构

页面描述

struct PAGE {int id;//页号int time;//自上次被访问以来所经历的时间t
};

（2）算法设计
产生指令序列

void generate() {int cnt = 0;srand(time(0));bool CF = 1;while (CF) {int M = rand() % max_add + 1;//在[1,32K-2]的指令地址之间随机选取一起点Mins[cnt++] = M;if (cnt >= N) { break; }ins[cnt++] = M + 1;//顺序访问M+1if (cnt >= N) { break; }int M1 = rand() % M;ins[cnt++] = M1;if (cnt >= N) { break; }ins[cnt++] = M1 + 1;//顺序访问M1+1if (cnt >= N) { break; }int M2 = rand() % (max_add - M1 - 1) + (M1 + 2);// 在[M1+2,32K-2]中随机选取M2ins[cnt++] = M2;if (cnt >= N)break;ins[cnt++] = M2 + 1;//顺序访问M2+1if (cnt >= N)break;}for (int i = 0; i < N; i++) {ins[i] = ins[i] / 1024;//得到页号}
}

先进先出（FIFO）页面置换算法

double FIFO(int page) {double hit_num = 0;double unhit_num = 0;vector<int>temp;for (int i = 0; i < page; i++) {temp.push_back(-1);}for (int i = 0; i < N; i++) {vector<int>::iterator it = find(temp.begin(), temp.end(), ins[i]);if (it == temp.end()) {temp.erase(temp.begin());temp.push_back(ins[i]);unhit_num++;}//未命中else {hit_num++;}}return 100 * (1 - unhit_num / N);
}

最近最久未使用（LRU）页面置换算法

double LRU(int page) {double hit_num = 0;double unhit_num = 0;vector<PAGE>temp;for (int i = 0; i < page; i++) {temp.push_back(PAGE{ -1,0 });}vector<PAGE>::iterator it;for (int i = 0; i < N; i++) {for (it = temp.begin(); it != temp.end(); it++) {it->time++;}bool flag = false;for (it = temp.begin(); it != temp.end(); it++) {if (it->id == ins[i]) {flag = true;it->time = 0;hit_num++;break;}   }if (!flag) {//找到一个最大的vector<node>::iterator max_it = temp.begin();for (it = temp.begin(); it != temp.end(); it++) {if (it->time > max_it->time) {max_it = it;}}temp.erase(max_it);unhit_num++;temp.push_back(node{ ins[i],0 });}}return 100 * (1 - unhit_num / N);
}

最佳（Optimal）页面置换算法

double OPT(int page) {vector<int>temp;double hit_num = 0;double unhit_num = 0;for (int i = 0; i < page; i++) {temp.push_back(-1);//初始化}for (int i = 0; i < N; i++) {vector<int>::iterator it = find(temp.begin(), temp.end(), ins[i]);if (it == temp.end()) {//如果没找到unhit_num++;int maxtime = -1;vector<int>::iterator ans;for (it = temp.begin(); it != temp.end(); it++) {int cur = 0x3f3f3f3f;for (int j = i + 1; j < N; j++) {if (ins[j] == *it) {cur = j;break;}}if (cur > maxtime) { //找到之后最长时间未使用的maxtime = cur;ans = it;}}temp.erase(ans);temp.push_back(ins[i]);}else {hit_num++;}}return 100*(1-unhit_num/N);
}

四、程序运行情况

五、遇到的困难及解决办法、实习心得或良好建议

遇到的困难：在计算命中率时总是出现不合理的结果，例如-1200，或者各种高于100的数字。
解决办法：将定义为全局变量的unhit_time当作局部变量放入三个算法中，并逐步调试发现LRU中unhit_time++的时机不对，应该放在erase（）那一块。
实习心得：这次实验难度并不高，但是考查的是对三种置换算法的理解。我课堂上并没能好好掌握该部分知识点，通过反复阅读ppt和做相关例题，终于明白了各种置换算法的实现步骤，学习能力得到提高。

这篇关于操作系统原理请求分页系统中的置换算法的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---