通过对页面、页表、地址转换和页面置换过程的模拟，加深对请求调页系统的原理和实现过程的理解
1 当前需要执行的指令所在的页面在内存中则打印物理块编号来模拟真实物理地址的计算
2 不在内存中，但是内存中有空物理块则将页面直接调入内存，并打印物理块编号来模拟真实物理地址的计算
3 不在内存中，内存中也没有空物理块，则通过OPT、FIFO、LRU 三种置换算法来进行置换操作，置换完成后打印物理块编号来模拟真实物理地址的计算
4一些被注释的代码是作者调试时使用，读者可根据需要取消注释进行调试
// 当前需要执行的指令所在的页面在内存中则打印物理块编号来模拟真实物理地址的计算
// 不在内存中，但是内存中有空物理块则将页面直接调入内存，并打印物理块编号来模拟真实物理地址的计算
// 不在内存中，内存中也没有空物理块，则通过OPT、FIFO、LRU 三种置换算法来进行置换操作，置换完成后打印物理块编号来模拟真实物理地址的计算
// 一些被注释的代码是作者调试时使用，读者可根据需要取消注释进行调试 @Author-chenzhuo
#include <iostream>
#include<stdio.h>
#include <queue> //队列头文件
#include<time.h>
#define INSTR_NUM 320 // 指令条数
#define MEMORY_BLOCK_NUM 4 // 物理内存被划分的块数
#define INSTR_NUM_PER_PAGE 10 // 每个页面的指令条数
using namespace std;
typedef struct Block {
int page_id;
int next; // 在最佳替换算法中OPT使用,FIFO和LRU 均用队列来辅助实现
}Block;
int _index=0;
int instr[INSTR_NUM]; // 随机产生的指令执行序列数组
int lack_num; // 缺页次数，不同算法中将该值重置为0
Block memory_block[MEMORY_BLOCK_NUM]; // 内存物理块
// 返回某范围的随机数
int getRandom(int start, int end) {
int t = rand()%(end-start+1) + start;
int j;
for (j=0; j<_index ;j++) {
if (instr[j] == t) {
break;
}
}
if (_index == j) {
instr[_index++] = t;
}
int k;
for (k=0;k<_index;k++) {
if (instr[k] == t+1) {
break;
}
}
if (_index == k && t+1 < INSTR_NUM) {
instr[_index++] = t+1;
}
return t;
}
// 初始化，给指令执行数组赋值
void init() {
// 得到指令执行顺序，存入数组
int t = getRandom(0, INSTR_NUM-1);
while (_index<INSTR_NUM) {
if(t==1 && _index == 2) {
instr[_index++] = t-1;
}
if(t > 1) {
int forword = getRandom(0, t-1);
}
if (t <= INSTR_NUM-3) {
int last = getRandom(t+2, INSTR_NUM-1);
}
}
// 内存置空
for (int i=0; i<MEMORY_BLOCK_NUM; i++) {
memory_block[i].page_id = -1;
}
}
// 当前页面是否已经调入页框
int isExistInMemory(int curr_page) {
// 不存在内存中，返回-1 ，存在 返回所在物理块位置
int is_exist = -1;
for (int i=0; i<MEMORY_BLOCK_NUM; i++) {
if (memory_block[i].page_id == curr_page) {
is_exist = i;
break;
}
}
return is_exist;
}
// 是否有空闲页框
Block* findEmpty() {
Block* empty = NULL;
for (int i=0; i<MEMORY_BLOCK_NUM; i++) {
if (memory_block[i].page_id == -1) {
empty = & memory_block[i];
break;
}
}
return empty;
}
// 在OPT中使用，找到应该被替换的页框
int findReplace() {
int pos = 0;
for(int i=0; i<MEMORY_BLOCK_NUM; i++) {
if(memory_block[i].next >memory_block[pos].next)
pos = i;//找到应予置换页面，返回BLOCK中位置
}
return pos;
}
// 返回最佳被置换的页面
void findBeReplaceBlockByOPT(int index_) {
for(int i=0; i<MEMORY_BLOCK_NUM; i++) {
for(int j=index_+1; j<320; j++) {
if(memory_block[i].page_id != instr[j]/INSTR_NUM_PER_PAGE){
memory_block[i].next = 1000; //最近此块并没有指令要被访问
} else { //将来不会用，设置为一个很大数
memory_block[i].next = j; //最近此块内要被访问的指令
break;
}
}
}
}
// 显示当前页的物理块（页框）编号，模拟真实物理地址的计算
void show(int curr_page) {
// printf("物理地址分别是:\n");
for (int i=0; i<MEMORY_BLOCK_NUM; i++) {
if(memory_block[i].page_id == curr_page) {
// printf("第%d页所在物理块编号:%d ", curr_page, i);
// printf("物理地址:%d ", i);
printf("%d ", i);
break;
}
}
}
// 最佳页面替换算法
void OPT() {
int pc;
int curr_page;
int is_exist;
int position;
lack_num = 0;
Block* empty;
printf("OPT:\n\n");
for (int i=0; i<INSTR_NUM; i++) {
pc = instr[i];
// 指令是否在内存块中，在则打印，不在则调入
curr_page = pc/INSTR_NUM_PER_PAGE; // 当前指令所在的页面编号
is_exist = isExistInMemory(curr_page); // 当前页面是否在内存中 -1 表示不存在
if(is_exist == -1) {
lack_num++;
// printf("第%d页不在内存\n", curr_page);
// 内存是否还有剩余空间，有则直接调入，没有则根据OPT算法找到最合适的页面调出
empty = findEmpty();
if(empty != NULL) {
// printf("将%d页调入内存\n",curr_page);
empty -> page_id = curr_page;
} else {
// printf("将%d置换内存\n",curr_page);
findBeReplaceBlockByOPT(i);
position = findReplace();
memory_block[position].page_id = curr_page;
}
}
show(curr_page);
}
printf("\n缺页率:%.2f %%\n",lack_num/320.0*100) ;
}
// 最近最少使用页面替换算法
void LRU() {
int pc;
int curr_page;
int is_exist;
Block* empty;
lack_num = 0;
queue<int> queue_;
printf("LRU:\n\n");
for (int i=0; i<INSTR_NUM; i++) {
queue<int> tempQueue;
pc = instr[i];
// 指令是否在内存块中，在则打印，不在则调入
curr_page = pc/INSTR_NUM_PER_PAGE; // 当前指令所在的页面编号
is_exist = isExistInMemory(curr_page); // 当前页面是否在内存中 -1 表示不存在
if(is_exist == -1) {
lack_num++;
// printf("第%d页不在内存,缺页次数:%d\n", curr_page, lack_num);
// 内存是否还有剩余空间，有则直接调入，没有则根据FIFO算法找到最合适的页面调出
empty = findEmpty();
if(empty != NULL) {
// printf("将%d页调入内存\n",curr_page);
empty -> page_id = curr_page;
queue_.push(curr_page);
} else {
// 没有空块则置换
int first = queue_.front();
// printf("将%d页与内存中第%d页置换\n", curr_page, first);
for(int j=0; j<MEMORY_BLOCK_NUM; j++) {
if(memory_block[j].page_id == first) {
memory_block[j].page_id = curr_page;
break;
}
}
queue_.pop();
queue_.push(curr_page);
}
} else {
// 存在则放到栈顶
// printf("将%d页放到栈顶\n", curr_page);
int temp = -1;
while (queue_.size() != 0) {
// printf("当前队列大小:%lu\n", queue_.size());
int first = queue_.front();
if (first == curr_page ) {
temp = first;
queue_.pop();
} else {
tempQueue.push(first);
queue_.pop();
}
}
if (temp != -1) {
tempQueue.push(temp);
}
queue_ = tempQueue;
}
show(curr_page);
}
printf("\n缺页率:%.2f %%\n",lack_num/320.0*100) ;
}
// 先入先出页面替换算法
void FIFO() {
int pc;
int curr_page;
int is_exist;
Block* empty;
lack_num = 0;
queue<int> queue_;
printf("FIFO:\n\n");
printf("物理地址:\n");
for (int i=0; i<INSTR_NUM; i++) {
pc = instr[i];
// 指令是否在内存块中，在则打印，不在则调入
curr_page = pc/INSTR_NUM_PER_PAGE; // 当前指令所在的页面编号
is_exist = isExistInMemory(curr_page); // 当前页面是否在内存中 -1 表示不存在
if(is_exist == -1) {
lack_num++;
// printf("第%d页不在内存,缺页次数:%d\n", curr_page, lack_num);
// 内存是否还有剩余空间，有则直接调入，没有则根据FIFO算法找到最合适的页面调出
empty = findEmpty();
if(empty != NULL) {
// printf("将%d页调入内存\n",curr_page);
empty -> page_id = curr_page;
queue_.push(curr_page);
} else {
int first = queue_.front();
// printf("将%d页与内存中第%d页置换\n", curr_page, first);
for(int j=0; j<MEMORY_BLOCK_NUM; j++) {
if(memory_block[j].page_id == first) {
memory_block[j].page_id = curr_page;
break;
}
}
queue_.pop();
queue_.push(curr_page);
}
}
show(curr_page);
}
printf("\n缺页率:%.2f %%\n",lack_num/320.0*100) ;
}
int main(){
// 以时间作为随机数种子
srand((unsigned)time(NULL));
init();
printf("\n随机产生的指令执行序号:\n");
for(int i=0;i<INSTR_NUM;i++) {
printf("%d ", instr[i]);
}
printf("\n\n");
// 每次只能使用一种算法
// OPT();
// FIFO();
LRU();
return 0;
}
