1 Commits (develop)

Author	SHA1	Message	Date
Pullaway11	61c72e1182	#include <stdio.h> ... #include <stdlib.h> #include <time.h> #include <string.h> #define maxn 320 // 序列个数 #define max (maxn + 20) // 数组大小 #define maxp (max / 10) // 最大页数 int inst[max]; // 指令序列 int page[max]; // 页地址流 int size; // 内存能容纳的页数 int in[maxp]; // 该页是否在内存里，提高效率 int pin[maxp]; // 现在在内存里的页 void welcome() { printf("******************************************\n"); printf("** 操作系统模拟实验\t\t**\n"); printf("** 页式存储管理\t\t**\n"); printf("******************************************\n\n"); } void input_hint() { printf("\n1--创建新指令序列 2--设置内存页数(4到32)\n"); printf("3--使用FIFO算法求解 4--使用LRU算法求解\n"); printf("5--使用OPT算法求解 0--退出\n"); printf("*********请输入您的选择: "); } /*通过随机数产生一个指令序列，共320条指令*/ void produce_inst() { int m, n; int num = 0; while (num < maxn) { m = rand() % maxn; inst[num++] = (m + 1) % maxn; if (num == maxn) break; m = (m + 2) % maxn; if (m == 0) m = 160; n = rand() % m; inst[num++] = (n + 1) % maxn; if (num == maxn) break; n = (n + 2) % maxn; m = maxn - n; if (m == 0) m = 160; m = rand() % m + n; inst[num++] = m; } } /*将指令序列变换成为页地址流*/ void turn_page_address() { for (int i = 0; i < maxn; i++) { page[i] = inst[i] / 10; } } void FIFO_solve() { memset(in, 0, sizeof(in)); int fault_n = 0; // 缺页次数 int ptr, i; // 预调页填满空间 ptr = 0; // 下一个要放的位置 for (i = 0; i < maxn && ptr < size; i++) if (!in[page[i]]) { pin[ptr++] = page[i]; in[page[i]] = 1; fault_n++; } // 继续执行剩下的指令 ptr = 0; // 队列里最先进来的位置，即下一个要被替换的位置 for (; i < maxn; i++) if (!in[page[i]]) { /*--------------*/ // 请补全该部分 in[pin[ptr]] = 0; in[page[i]] = 1; pin[ptr] = page[i]; fault_n++; ptr = (ptr + 1) % size; /*--------------*/ } printf("\n使用FIFO算法，缺页次数为: %d\n", fault_n); printf(" 命中率为: %.2lf\n", (1 - (fault_n + 0.0) / 320.0)); } void LRU_solve() { int ltu[maxp]; // 最后使用时间 (last_time_use) int ti = 1; // 模拟时间 int fault_n = 0; memset(ltu, 0, sizeof(ltu)); memset(in, 0, sizeof(in)); memset(pin, -1, sizeof(pin)); int min, ptr, i, j; for (i = 0; i < maxn; i++) { if (!in[page[i]]) { // 寻找LRU页面 min = 1000000; ptr = 0; for (j = 0; j < size; j++) { if (ltu[j] < min) { /*--------------*/ // 请补全该部分 min = ltu[j]; ptr = j; /*--------------*/ } } // 替换或写入 /*--------------*/ // 请补全该部分 in[pin[ptr]] = 0; pin[ptr] = page[i]; in[page[i]] = 1; /*--------------*/ fault_n++; ltu[ptr] = ti++; } else // 已经在内存里则只需修改最近使用时间 { for (j = 0; j < size; j++) if (pin[j] == page[i]) { ltu[j] = ti++; break; } } } printf("\n使用LRU算法，缺页次数为: %d\n", fault_n); printf(" 命中率为: %.2lf\n", (1 - (fault_n + 0.0) / 320.0)); } void OPT_solve() { int ntu[maxp]; // 下次使用时间 (next_time_use) int fault_n = 0; int i, j; memset(in, 0, sizeof(in)); memset(ntu, -1, sizeof(ntu)); // 预调页填满 int ptr = 0; for (i = 0; i < maxn && fault_n < size; i++) { if (!in[page[i]]) { in[page[i]] = 1; pin[ptr] = page[i]; fault_n++; ptr++; } } // 初始化ntu数组 ptr = 0; for (j = i; j < maxn && ptr < 32; j++) { if (ntu[page[j]] == -1) { /*--------------*/ // 请补全该部分 ntu[page[j]] = j; /*--------------*/ } } int temp; for (; i < maxn; i++) { if (!in[page[i]]) { temp = 0; ptr = 0; for (j = 0; j < size; j++) { if (ntu[pin[j]] == -1) { ptr = j; break; } if (ntu[pin[j]] > temp) { /*--------------*/ // 请补全该部分 temp = ntu[pin[j]]; ptr = j; /*--------------*/ } } in[pin[ptr]] = 0; in[page[i]] = 1; pin[ptr] = page[i]; fault_n++; } ntu[page[i]] = -1; for (j = i + 1; j < maxn; j++) if (page[j] == page[i]) { ntu[page[i]] = j; break; } } printf("\n使用OPT算法，缺页次数为: %d\n", fault_n); printf(" 命中率为: %.2lf\n", (1 - (fault_n + 0.0) / 320.0)); } int main() { srand(100); welcome(); int choice; while (1) { input_hint(); scanf("%d", &choice); printf("\n"); if (choice == 0) { printf("再见!!!\n"); break; } if (choice == 1) { produce_inst(); turn_page_address(); printf("新页地址序列设置成功!!!\n"); } else if (choice == 2) { printf("请输入内存页数: "); scanf("%d", &size); } else if (choice == 3) FIFO_solve(); else if (choice == 4) LRU_solve(); else if (choice == 5) OPT_solve(); else printf("输入错误 !!! \n"); } return 0; }	2 months ago