大地保险网站/东莞seo外包公司

页面置换模拟程序设计

1、通过软件模拟页面置换过程，加深对请求页式存储管理实现原理的理解
2、理解和掌握OPT、FIFO和LRU三种页面置换算法，深入分析三者之间的优缺点。

#include<stdio.h>
#include<stdlib.h>#define VM_PAGE 7      /*假设每个页面可以存放10条指令,则共有32个虚页*/
#define PM_PAGE 4         /*分配给作业的内存块数为4*/
#define TOTAL_INSERT 18
typedef struct
{int vmn;int pmn;int exist;int time;
}vpage_item;
vpage_item page_table[VM_PAGE];vpage_item* ppage_bitmap[PM_PAGE];int vpage_arr[TOTAL_INSERT] = { 1,2,3,4,2,6,2,1,2,3,7,6,3,2,1,2,3,6 };void init_data() //数据初始化
{for (int i = 0; i < VM_PAGE; i++){page_table[i].vmn = i + 1;  //虚页号page_table[i].pmn = -1;    //实页号page_table[i].exist = 0;page_table[i].time = -1;}for (int i = 0; i < PM_PAGE; i++) /*最初4个物理块为空*/{ppage_bitmap[i] = NULL;}
}void FIFO()/*FIFO页面置换算法*/
{int k = 0;int i;int sum = 0;int missing_page_count = 0;int current_time = 0;bool isleft = true;   /*当前物理块中是否有剩余*/while (sum < TOTAL_INSERT){if (page_table[vpage_arr[sum] - 1].exist == 0){missing_page_count++;if (k < 4){if (ppage_bitmap[k] == NULL) /*找到一个空闲物理块*/{ppage_bitmap[k] = &page_table[vpage_arr[sum] - 1];ppage_bitmap[k]->exist = 1;ppage_bitmap[k]->pmn = k;ppage_bitmap[k]->time = current_time;k++;}}else{int temp = ppage_bitmap[0]->time;	/*记录物理块中作业最早到达时间*/int j = 0;                    /*记录应当被替换的物理块号*/for (i = 0; i < PM_PAGE; i++){if (ppage_bitmap[i]->time < temp){temp = ppage_bitmap[i]->time;j = i;}}ppage_bitmap[j]->exist = 0;ppage_bitmap[j] = &page_table[vpage_arr[sum] - 1];      /*更新页表项*/ppage_bitmap[j]->exist = 1;ppage_bitmap[j]->pmn = j;ppage_bitmap[j]->time = current_time;}}current_time++;sum++;}printf("FIFO算法缺页次数为:%d\t缺页率为:%f\t置换次数为:%d\t置换率为:%f", missing_page_count, missing_page_count / (float)TOTAL_INSERT, missing_page_count - 4, (missing_page_count - 4) / (float)TOTAL_INSERT);
}
void LRU()
{int k = 0;int i;int sum = 0;int missing_page_count = 0;int current_time = 0;bool isleft = true;   /*当前物理块中是否有剩余*/while (sum < TOTAL_INSERT) {if (page_table[vpage_arr[sum] - 1].exist == 0) {missing_page_count++;if (k < 4){if (ppage_bitmap[k] == NULL) /*找到一个空闲物理块*/{ppage_bitmap[k] = &page_table[vpage_arr[sum] - 1];ppage_bitmap[k]->exist = 1;ppage_bitmap[k]->pmn = k;ppage_bitmap[k]->time = current_time;k++;}}else {int temp = ppage_bitmap[0]->time;	/*记录物理块中作业最早到达时间*/int j = 0;                    /*记录应当被替换的物理块号*/for (i = 0; i < PM_PAGE; i++){if (ppage_bitmap[i]->time < temp){temp = ppage_bitmap[i]->time;j = i;}}ppage_bitmap[j]->exist = 0;ppage_bitmap[j] = &page_table[vpage_arr[sum] - 1];      /*更新页表项*/ppage_bitmap[j]->exist = 1;ppage_bitmap[j]->pmn = j;ppage_bitmap[j]->time = current_time;}}else {for (i = 0; i < PM_PAGE; i++) {if (ppage_bitmap[i]->vmn == page_table[vpage_arr[sum] - 1].pmn){ppage_bitmap[i]->time = current_time;break;}}}current_time++;sum++;}printf("LRU算法缺页次数为:%d\t缺页率为:%f\t置换次数为:%d\t置换率为:%f", missing_page_count, missing_page_count / (float)TOTAL_INSERT, missing_page_count - 4, (missing_page_count - 4) / (float)TOTAL_INSERT);
}
void OPT()
{int k = 0;int sum = 0;int missing_page_count = 0;int current_time = 0;bool isleft = true;   /*当前物理块中是否有剩余*/while (sum < TOTAL_INSERT) {if (page_table[vpage_arr[sum] - 1].exist == 0) {missing_page_count++;if (k < 4){if (ppage_bitmap[k] == NULL) /*找到一个空闲物理块*/{ppage_bitmap[k] = &page_table[vpage_arr[sum] - 1];ppage_bitmap[k]->exist = 1;ppage_bitmap[k]->pmn = k;ppage_bitmap[k]->time = current_time;k++;}}else {int used[VM_PAGE] = { 0 };int count = 0;for (int i = sum+1; i < TOTAL_INSERT; i++) {if (page_table[vpage_arr[i] - 1].exist == 1) {used[page_table[vpage_arr[i] - 1].vmn-1] = 1;}int count = 0;for (int l = 0; l < VM_PAGE; l++) {if (used[l] == 1) {count++;}}if (count == 3) {break;}}for (int i = 0; i < PM_PAGE; i++) {if (used[ppage_bitmap[i]->vmn-1] == 0) {ppage_bitmap[i]->exist = 0;ppage_bitmap[i] = &page_table[vpage_arr[sum] - 1];ppage_bitmap[i]->exist = 1;ppage_bitmap[i]->pmn = i;ppage_bitmap[i]->time = current_time;}}}}current_time++;sum++;}printf("OPT算法缺页次数为:%d\t缺页率为:%f\t置换次数为:%d\t置换率为:%f", missing_page_count, missing_page_count / (float)TOTAL_INSERT, missing_page_count - 4, (missing_page_count - 4) / (float)TOTAL_INSERT);
}int main()
{int a;printf("请输入需要选择的页面置换算法：1.FIFO\t2.LRU\t3.OPT\t输入0结束\n");do{scanf_s("%d", &a);switch (a){case 1:init_data();FIFO();break;case 2:init_data();LRU();break;case 3:init_data();OPT();break;}} while (a != 0);return 0;
}