操作系统2

操作系统 实验报告（二）

实验名称 姓 名 实 验 目 的 实 验 环 境 实 验 内 容 动态分区分配方式的模拟 柳伟强 实验日期 班级学号 2016.12.14 142054141 成绩 了解动态分区分配方式中使用的数据结构和分配算法，进一步加深对动态分区存储管理方式及其实现过程的理解 VC++6.0 用C或C++分别实现采用首次适应算法和最佳适应算法的动态分区分配过程和回收过程。 设置初始状态，每次分配和回收后显示出空闲内存分区链的情况。 #include #include #include #define SIZE 700 // 内存初始大小 #define MINSIZE 5 // 碎片最小值 enum STATE { Free, Busy }; 实 验 步 骤 struct DiAreaNode { int addr; // 起始地址 int size; // 分区大小 int taskNum; // 作业号 STATE state; // 分区状态 DiAreaNode *pre; // 分区前向指针 DiAreaNode *next; // 分区后向指针 }subHead; // 初始化空闲分区链 void intSubArea() { // 分配初始分区内存 DiAreaNode *fir = (DiAreaNode *)malloc(sizeof(DiAreaNode)); // 给首个分区赋值 fir->addr = 20; fir->size = SIZE; fir->state = Free; fir->taskNum = -1; fir->pre = &subHead; fir->next = NULL; // 初始化分区头部信息 subHead.pre = NULL; subHead.next = fir; } // 首次适应算法 int firstFit(int taskNum, int size) { DiAreaNode *p = subHead.next;//从链首开始查找，找到一个满足要求的空闲分区 while(p != NULL) { if(p->state == Free && p->size >= size) { // 找到要分配的空闲分区 if(p->size - size <= MINSIZE) { // 整块分配 p->state = Busy; p->taskNum = taskNum; } else { // 分配大小为size的区间 DiAreaNode *)malloc(sizeof(DiAreaNode)); node->addr = p->addr + size; *node = (DiAreaNode node->size = p->size - size; node->state = Free; node->taskNum = -1; // 修改分区链节点指针 node->pre = p; node->next = p->next; if(p->next != NULL) { p->next->pre = node; } p->next = node; // 分配空闲区间 p->size = size; p->state = Busy; p->taskNum = taskNum; } cout<<\"内存分配成功！\\n\"; return 1; } p = p->next; } cout<<\"找不到合适的内存分区，分配失败！\\n\"; return 0; } // 最佳适应算法 int bestFit(int taskNum, int size) { DiAreaNode *tar = NULL; int tarSize = SIZE + 1; DiAreaNode *p = subHead.next; while(p != NULL) { // 寻找最佳空闲区间 if(p->state == Free && p->size >= size && p->size < tarSize) { tar = p; tarSize = p->size; } p = p->next; } if(tar != NULL) { // 找到要分配的空闲分区 if(tar->size - size <= MINSIZE) { // 整块分配 tar->state = Busy; tar->taskNum = taskNum; } else { // 分配大小为size的区间 DiAreaNode *)malloc(sizeof(DiAreaNode)); node->addr = tar->addr + size; node->size = tar->size - size; node->state = Free; node->taskNum = -1; // 修改分区链节点指针 node->pre = tar; node->next = tar->next; if(tar->next != NULL) { tar->next->pre = node; } tar->next = node; // 分配空闲区间 tar->size = size; tar->state = Busy; tar->taskNum = taskNum; } cout<<(\"内存分配成功！\\n\"); return 1; *node = (DiAreaNode } else { cout<<\"找不到合适的内存分区，分配失败！\\n\"; return 0; } } // 回收内存 int freeSubArea(int taskNum) { int flag = 0; DiAreaNode *p = subHead.next, *q; while(p != NULL) { if(p->state == Busy && p->taskNum == taskNum) { flag = 1; if((p->pre != &subHead && p->pre->state == Free) && (p->next != NULL && p->next->state == Free)) { // 情况1：回收区同时与插入点的前后两个分区相连，合并上下两个分区 // 先合并上区间 q = p; p = p->pre; p->size += q->size; p->next = q->next; q->next->pre = p; free(q); // 后合并下区间 q = p->next; p->size += q->size; p->next = q->next; if(q->next != NULL) { q->next->pre = p; } free(q); } else if((p->pre == &subHead || p->pre->state == Busy) && (p->next != NULL && p->next->state == Free)) { // 情况2：只合并下面的分区 q = p->next; p->size += q->size; p->state = Free; p->taskNum = -1; p->next = q->next; if(q->next != NULL) { q->next->pre = p; } free(q); } else if((p->pre != &subHead && p->pre->state == Free) && (p->next == NULL || p->next->state == Busy)) { // 情况3：只合并上面的分区 q = p; p = p->pre; p->size += q->size; p->next = q->next; if(q->next != NULL) { q->next->pre = p; } free(q); } else { // 情况4：上下分区均不用合并 p->state = Free; p->taskNum = -1; } } p = p->next; } if(flag == 1) { printf(\"内存分区回收成功!\\n\"); return 1; } else { // 找不到目标作业，回收失败 printf(\"找不到目标作业，内存分区回收失败!\\n\"); return 0; } } // 显示空闲分区链情况 void showSubArea() { printf(\"*********************************************\\n\"); printf(\"** 当前的内存分配情况如下： **\\n\"); printf(\"*********************************************\\n\"); printf(\"** 起始地址 | 空间大小 | 工作状态 | 作业号 **\\n\"); DiAreaNode *p = subHead.next; while(p != NULL) { printf(\"**-----------------------------------------**\\n\"); printf(\"**\"); printf(\"%d k |\ printf(\"%d k |\ printf(\" %s |\ if(p->taskNum > 0) { printf(\"%d \ } else { printf(\" \"); } printf(\"**\\n\"); p = p->next; } printf(\"*********************************************\\n\"); } int main() { int option, ope, taskNum, size; // 初始化空闲分区链 intSubArea(); // 选择分配算法 while(1) { printf(\"*** 请在下面选择你需要的分配算法 *********\\n\"); printf(\"** 0 表示首次适应算法，1 表示最佳适应算法 *****\\n\"); printf(\"请输入以上序号： \"); scanf(\"%d\ if(option == 0) { printf(\"你选择了首次适应算法，下面进行算法演示\\n\"); break; } else if(option == 1) { printf(\"你选择了最佳适应算法，下面进行算法演示\\n\"); break; } else { printf(\"输入错误：请输入 0或1\\n\\n\"); } } // 动态分区分配算法 while(1) { printf(\"\\n\"); printf(\"*********************************************\\n\"); printf(\"** 1: 分配内存 2: 回收内存 0: 退出 **\\n\"); printf(\"*********************************************\\n\"); printf(\"请输入以上序号： \"); scanf(\"%d\ if(ope == 0) break; if(ope == 1) { // 分配内存 printf(\"请输入作业号： \"); scanf(\"%d\ printf(\"请输入需要分配的内存大小(KB)： \"); scanf(\"%d\ if(size <= 0) { printf(\"错误：分配内存大小必须为正值\\n\"); continue; } if(size >= SIZE) { printf(\"错误：分配内存大小必须小于初始化内存\\n\"); } continue; // 调用分配算法 if(option == 0) { firstFit(taskNum, size); } else { bestFit(taskNum, size); } // 显示空闲分区链情况 showSubArea(); } else if(ope == 2) { // 模拟回收内存 printf(\"请输入要回收的作业号： \"); scanf(\"%d\ freeSubArea(taskNum); // 显示空闲分区链情况 showSubArea(); } else { printf(\"错误：请输入 0/1/2\\n\"); } } printf(\"分配算法结束\\n\"); return 0; } 总 结