操作系统实验——页面置换模拟程序设计

#include <iostream> #include <stdlib.h> #include <time.h> using namespace std; #define VM_PAGE 32 /*假设每个页面可以存放10条指令,则共有32个虚页*/ #define PM_PAGE 4 /*分配给作业的内存块数为4*/ #define TOTAL_INSERT 320 typedef struct { int vmn; int pmn; int exist; int time; int number; }vpage_item; vpage_item page_table[VM_PAGE]; vpage_item* ppage_bitmap[PM_PAGE]; int vpage_arr[TOTAL_INSERT]; 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; page_table[i].number = 0; } 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 < PM_PAGE) { 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\n", 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 < PM_PAGE) { 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 { page_table[vpage_arr[sum] - 1].time = current_time; } current_time++; sum++; } printf("LRU算法缺页次数为:%d\t缺页率为:%f\t置换次数为:%d\t置换率为:%f\n", 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 i; int sum = 0; int missing_page_count = 0; int current_time = 0; while (sum < TOTAL_INSERT) { if (page_table[vpage_arr[sum] - 1].exist == 0) { missing_page_count++; if (k < PM_PAGE) { 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; ppage_bitmap[k]->number = vpage_arr[sum]; k++; } } else { int i, k; int j = 0;/*记录应当被替换的物理块号*/ int distance[PM_PAGE] = {0}; int count = 0; for (i = sum + 1; i < TOTAL_INSERT; i++) { for (k = 0; k < PM_PAGE; k++) { if (vpage_arr[i] == ppage_bitmap[k]->number&&distance[k] == 0) { distance[k] = i - sum; count++; break; } } if (count == 3) { for (k = 0; k < PM_PAGE; k++) { if (distance[k] == 0) { j = k; break; } } break; } } 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; ppage_bitmap[j]->number = vpage_arr[sum]; } } current_time++; sum++; } printf("OPT算法缺页次数为:%d\t缺页率为:%f\t置换次数为:%d\t置换率为:%f\n", missing_page_count, missing_page_count / (float)TOTAL_INSERT, missing_page_count - 4, (missing_page_count - 4) / (float)TOTAL_INSERT); } int main() { int a, n, m, count = -1; int live[TOTAL_INSERT] = {0}; srand((unsigned)time(NULL)); while (count < TOTAL_INSERT - 1) { //产生随机数n,0至319 n = rand() % 320; if (live[n] == 0) { live[n] == 1; count++; } else continue; m = n / 10 + 1;//m为页面号，每10个指令为一个页面 vpage_arr[count] = m;//页面号存入 } 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; }