操作系统 FIFO算法 LRU算法 OPT算法(C++)

题目

实验三 请求调页存储管理方式的模拟
1．实验目的
通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解。
2．实验内容
（1）假设每个页面中可存放10条指令，分配给作业的内存块数为4。
（2）用c语言模拟一个作业的执行过程，该作业共有320条指令，即它的地址空间为32页，目前它的所有页都还未调入内存。在模拟过程中，如果所访问的指令已在内存，则显示其物理地址，并转下一条指令。如果所访问的指令还未装入内存，则发生缺页，此时需记录缺页的次数，并将相应页调入内存。如果4个内存块均已装入该作业，则需进行页面置换，最后显示其物理地址，并转下一条指令。在所有320指令执行完毕后，请计算并显示作业运行过程中发生的缺页率。
（3）置换算法：采用先进先出（FIFO）、最近最久未使用（LRU）和最佳置换（OPT）算法置换算法。
（4）通过随机数产生一个指令序列，共320条指令。
1）指令的地址按下述原则生成：
① 50%的指令是顺序执行的；
② 25%的指令是均匀分布在前地址部分；
③ 25%的指令是均匀分布在后地址部分；
具体的实施方法是：
① 在[0，319]的指令地址之间随机选取一起点m；
② 顺序执行一条指令，即执行序号为m+1的指令；
③ 在前地址[0，m-1]中随机选取一条指令并执行，该指令的序号为m1；
④ 顺序执行一条指令，其序号为m1+1的指令；
⑤ 在后地址[m1+2，319]中随机选取一条指令并执行,该指令的序号为m2；
⑥ 顺序执行一条指令，其序号为m2+1的指令；
重复上述步骤①～⑥，直到执行320次指令。
2）将指令序列变换为页地址流
设页面大小为1K， 用户虚存容量为32K。在用户虚存中，按每K存放10条指令排列虚存地址，即320条指令在虚存中的存放方式为：
第0条～第9条指令为第0页（对应虚存地址为[0，9]）；
第10条～第19条指令为第1页（对应虚存地址为[10，19]）；
……
……
第310条～第319条指令为第31页（对应虚存地址为[310，319]）。
按以上方式，用户指令可组成32页。
3.思考
（1）如果增加分配给作业的内存块数，将会对作业运行过程中的缺页产生什么影响？
（2）为什么一般情况下，LRU具有比FIFO更好的性能？

首先要注意的是，实验文档那个获取随机指令的方法非常糟糕，很多种情况会导致程序奔溃或者获得的指令不在范围内，需要特判。

FIFO算法

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int cnt;                ///发生缺页的次数
const int maxn = 4;     ///内存块数的数目
const int maxn_n = 320;typedef struct Node{int a[10];bool is_empty = true;
}Node;
Node block[maxn];///结构体数组模拟队列，4个内存块维护页面int head = 0;
int tail = 0;
int instruction[maxn_n];    ///指令int search(int id){for(int i = 0; i < maxn; i++){if(!block[i].is_empty){for(int j = 0; j < 10; j++){if(block[i].a[j] == id){return 0 * printf("已存在，物理地址为：%d\n", i * 10 + j);}}}}return -1;
}void adjust(int id){if(tail < maxn){block[tail].is_empty = false;for(int i = 0; i < 10; i++){block[tail].a[i] = id / 10 * 10 + i;}printf("调入内存后物理地址为：%d\n", tail * 10 + id % 10);tail++;}else{for(int i = 0; i < 10; i++){block[head].a[i] = id / 10 * 10 + i;}printf("调入内存后物理地址为：%d\n", head * 10 + id % 10);head = (head + 1) % maxn;}
}void solve(int id){if(search(id) == -1){cnt++;adjust(id);}
}int main(){srand(int(time(0)));int n = 320;int cnt_n = 0;while(cnt_n < 320){int m = rand() % n;instruction[cnt_n++] = m + 1;if(m == 0)continue;int m1 = rand() % m;instruction[cnt_n++] = m1;instruction[cnt_n++] = m1 + 1;if(n - m1 - 2 <= 0)continue;int m2 = rand() % (n - m1 - 2) + m1 + 2;instruction[cnt_n++] = m2;instruction[cnt_n++] = m2 + 1;}for(int i = 0; i < 320; i++){solve(instruction[i]);}printf("缺页次数为：%d\n", cnt);printf("缺页率为：%f\n", 1.0 * cnt / 320);return 0;
}

LRU算法

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;int cnt;                ///发生缺页的次数
int now_time;           ///当前时间
const int maxn = 4;     ///内存块数的数目
const int maxn_n = 320 + 20;typedef struct Node{int id;                 ///块序号int a[10];int passage = -1;       ///页int recent_time = -1;   ///上次使用的时间，越大说明越接近现在我们所处的时间
}Node;
Node block[maxn];///结构体数组模拟队列，4个内存块维护页面int instruction[maxn_n];    ///指令bool search(int id, int passage){for(int i = 0; i < maxn; i++){if(block[i].passage == passage){block[i].recent_time = now_time;printf("已存在，物理地址为：%d\n", block[i].id * 10 + id % 10);return true;}}return false;
}bool cmp(Node a, Node b){return a.recent_time < b.recent_time;///从小到大排序，小的离现在最久远
}void adjust(int id, int passage){sort(block, block + maxn, cmp);for(int i = 0; i < 10; i++){block[0].a[i] = id / 10 * 10 + i;}block[0].passage = passage;block[0].recent_time = now_time;printf("调入内存后，物理地址为：%d\n", block[0].id * 10 + id % 10);
}void solve(int id){if(!search(id, id / 10)){///找不到该页cnt++;adjust(id, id / 10);}now_time++;
}int main(){srand(int(time(0)));int n = 320, cnt_n = 0;while(cnt_n < 320){int m = rand() % n;instruction[cnt_n++] = m + 1;if(m == 0)continue;int m1 = rand() % m;instruction[cnt_n++] = m1;instruction[cnt_n++] = m1 + 1;if(n - m1 - 2 <= 0)continue;int m2 = rand() % (n - m1 - 2) + m1 + 2;instruction[cnt_n++] = m2;instruction[cnt_n++] = m2 + 1;}for(int i = 0; i < maxn; i++){block[i].id = i;}for(int i = 0; i < n; i++){solve(instruction[i]);}printf("缺页次数为：%d\n", cnt);printf("缺页率为：%f\n", 1.0 * cnt / n);return 0;
}

OPT算法

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
int now;
int cnt;                ///发生缺页的次数
const int maxn = 4;     ///内存块数的数目
const int maxn_n = 320 + 20;
const int INF = 0x3f3f3f3f;typedef struct Node{int id;                 ///块序号int a[10];int passage = -1;       ///页int next_use = INF;     ///这个页面下次要用到的位置
}Node;
Node block[maxn];///结构体数组模拟队列，4个内存块维护页面int next_use[maxn];         ///第i条指令所处的页面下次要使用到的位置
int instruction[maxn_n];    ///指令bool search(int pos, int id, int passage){for(int i = 0; i < maxn; i++){if(block[i].passage == passage){block[i].next_use = next_use[pos];printf("已存在，物理地址为：%d\n", block[i].id * 10 + id % 10);return true;}}return false;
}bool cmp(Node a, Node b){return a.next_use - now > b.next_use - now;///大到小排序，最晚用到的替代掉
}void adjust(int pos,int id, int passage){sort(block, block + maxn, cmp);if(block[3].next_use - pos <= 0){for(int i = 0; i < 10; i++){block[3].a[i] = id / 10 * 10 + i;}block[3].passage = passage;block[3].next_use = next_use[pos];printf("调入内存后，物理地址为：%d\n", block[3].id * 10 + id % 10);}else{for(int i = 0; i < 10; i++){block[0].a[i] = id / 10 * 10 + i;}block[0].passage = passage;block[0].next_use = next_use[pos];printf("调入内存后，物理地址为：%d\n", block[0].id * 10 + id % 10);}
}void solve(int pos, int id){if(!search(pos, id, id / 10)){///找不到该页cnt++;adjust(pos, id, id / 10);}
}int main(){srand(int(time(0)));int n = 320, cnt_n = 0;while(cnt_n < 320){int m = rand() % n;instruction[cnt_n++] = m + 1;if(m == 0)continue;int m1 = rand() % m;if(m1 + 1 >= n)continue;instruction[cnt_n++] = m1;instruction[cnt_n++] = m1 + 1;if(n - m1 - 2 <= 0)continue;int m2 = rand() % (n - m1 - 2) + m1 + 2;instruction[cnt_n++] = m2;instruction[cnt_n++] = m2 + 1;}//预处理出多久后会再使用for(int i = 0; i < n; i++){for(int j = i + 1; j <= n; j++){if(j == n){next_use[i] = INF;break;}if(instruction[i] >= instruction[j] / 10 * 10 && instruction[i] < (instruction[j] / 10 + 1) * 10){next_use[i] = j;break;}}}for(int i = 0; i < maxn; i++){block[i].id = i;}for(int i = 0; i < n; i++){now = i;solve(i, instruction[i]);}printf("缺页次数为：%d\n", cnt);printf("缺页率为：%f\n", 1.0 * cnt / n);return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！