动态分区分配方式的模拟 (2)

太原工业学院计算机工程系 操作系统实验报告（二）实验名称动态分区分配方式的模拟实验日期2016/12/3成绩姓 名班级学号实验目的了解动态分区分配方式中使用的数据结构和分配算法，进一步加深对动态分区存储管理方式及其实现过程的理解实验环境Windows8.1+Visual C+6.0实验内容用C或C+分别实现采用首次适应算法和最佳适应算法的动态分区分配过程和回收过程。设置初始状态，每次分配和回收后显示出空闲内存分区链的情况。实验步骤 首次适应算法； 从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。为适应这种算法，空闲分区表（空闲区链）中的空闲分区要按地址由低到高进行排序。该算法优先使用低址部分空闲区，在低址空间造成许多小的空闲区，在高地址空间保留大的空闲区。 最佳适应算法；它从全部空闲区中找出能满足作业要求的、且大小最小的空闲分区，这种方法能使碎片尽量小。为适应此算法，空闲分区表（空闲区链）中的空闲分区要按从小到大进行排序，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。核心代码； / 初始化空闲分区链void intSubArea() / 分配初始分区内存 subAreaNode *fir = (subAreaNode *)malloc(sizeof(subAreaNode); / 给首个分区赋值fir-n= 0; fir-addr = 0; fir-size = SIZE; fir-state = Free; fir-taskId = -1; fir-pre = &subHead; fir-nxt = NULL; / 初始化分区头部信息 subHead.pre = NULL; subHead.nxt = fir;/ 首次适应算法int firstFit(int taskId, int size) subAreaNode *p = subHead.nxt; while(p != NULL) if(p-state = Free & p-size = size) / 找到要分配的空闲分区 if(p-size - size state = Busy; p-taskId = taskId; else / 分配大小为size的区间 subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode); node-addr = p-addr + size; node-size = p-size - size; node-state = Free; node-taskId = -1; / 修改分区链节点指针 node-pre = p; node-nxt = p-nxt; if(p-nxt != NULL) p-nxt-pre = node; p-nxt = node; / 分配空闲区间 p-size = size; p-state = Busy; p-taskId = taskId;p-n=p-n+1; printf(内存分配成功！n); return 1; p = p-nxt; printf(找不到合适的内存分区，分配失败.n); return 0;/ 最佳适应算法int bestFit(int taskId, int size) subAreaNode *tar = NULL; int tarSize = SIZE + 1; subAreaNode *p = subHead.nxt; while(p != NULL) / 寻找最佳空闲区间 if(p-state = Free & p-size = size & p-size size; p = p-nxt; if(tar != NULL) / 找到要分配的空闲分区 if(tar-size - size state = Busy; tar-taskId = taskId; else / 分配大小为size的区间 subAreaNode *node = (subAreaNode *)malloc(sizeof(subAreaNode); node-addr = tar-addr + size; node-size = tar-size - size; node-state = Free; node-taskId = -1; / 修改分区链节点指针 node-pre = tar; node-nxt = tar-nxt; if(tar-nxt != NULL) tar-nxt-pre = node; tar-nxt = node; / 分配空闲区间 tar-size = size; tar-state = Busy; tar-taskId = taskId;p-n=p-n+1; printf(内存分配成功！n); return 1; else / 找不到合适的空闲分区 printf(找不到合适的内存分区，分配失败.n); return 0; / 回收内存int freeSubArea(int taskId) int flag = 0; subAreaNode *p = subHead.nxt, *pp; while(p != NULL) p-n+; if(p-state = Busy & p-taskId = taskId) flag = 1; if(p-pre != &subHead & p-pre-state = Free) & (p-nxt != NULL & p-nxt-state = Free) / 情况1：合并上下两个分区 / 先合并上区间 pp = p; p = p-pre; p-size += pp-size; p-nxt = pp-nxt; pp-nxt-pre = p; free(pp); / 后合并下区间 pp = p-nxt; p-size += pp-size; p-nxt = pp-nxt; if(pp-nxt != NULL) pp-nxt-pre = p; free(pp); else if(p-pre = &subHead | p-pre-state = Busy) & (p-nxt != NULL & p-nxt-state = Free) / 情况2：只合并下面的分区 pp = p-nxt; p-size += pp-size; p-state = Free; p-taskId = -1; p-nxt = pp-nxt; if(pp-nxt != NULL) pp-nxt-pre = p; free(pp); else if(p-pre != &subHead & p-pre-state = Free) & (p-nxt = NULL | p-nxt-state = Busy) / 情况3：只合并上面的分区 pp = p; p = p-pre; p-size += pp-size; p-nxt = pp-nxt; if(pp-nxt != NULL) pp-nxt-pre = p; free(pp); else / 情况4：上下分区均不用合并 p-state = Free; p-taskId = -1; p = p-nxt; if(flag = 1) / 回收成功 printf(内存分区回收成功.n); return 1; else / 找不到目标作业，回收失败 printf(找不到目标作业，内存分区回收失败.n); return 0; / 显示空闲分区链情况void showSubArea() printf(*n); printf(* 当前的内存分配情况如下： *n); printf(*n); printf(* 分区号 | 起始地址 | 空间大小 | 工作状态 | 作业号 *n); subAreaNode *p = subHead.nxt; while(p != NULL) printf(*-*n); printf(*); if(p-n 0) printf(%d |, p-n); else printf( ); printf(%d k |, p-addr); printf(%d k |, p-size); printf( %s |, p-state = Free ? Free : Busy); if(p-taskId 0) printf(%d , p-taskId); else printf( ); printf(*n); p = p-nxt; printf(*n);int main() int option, ope, taskId, size,n; / 初始化空闲分区链 intSubArea(); / 选择分配算法 while(1) printf(请选择要模拟的分配算法:0 表示首次适应算法，1 表示最佳适应算法n); scanf(%d, &option); if(option = 0) printf(你选择了首次适应算法，下面进行算法的模拟n); break; else if(option = 1) printf(你选择了最佳适应算法，下面进行算法的模拟n); break; else printf(错误：请输入 0/1nn); / 模拟动态分区分配算法 while(1) printf(n); printf(*n); printf(* 1: 分配内存 2: 回收内存 0: 退出 *n); printf(*n); scanf(%d, &ope); if(ope = 0) break; if(ope = 1) / 模拟分配内存 printf(请输入作业号： ); scanf(%d, &taskId); printf(请输入需要分配的内存大小(KB)： ); scanf(%d, &size); if(size = 0) printf(错误：分配内存大小必须为正值n); continue; / 调用分配算法 if(option = 0) firstFit(taskId, size); else bestFit(t