实验二动态高优先权优先调度算法-王子瑜.doc

word一、 实验要求：熟悉并掌握动态分区分配的各种算法。熟悉并掌握动态分区中分区回收的各种情况，并能够实现分区合并。二、实验容：用高级语言模拟实现动态分区存储管理，要求：1、 分区分配算法至少实现首次适应算法、最优适应算法和最坏适应算法中的至少一种。熟悉并掌握各种算法的空闲区组织方式。2、 分区的初始化可以由用户输入初始分区的大小。初始化后只有一个空闲分区，起始地址为0，大小是用户输入的大小3、 分区的动态分配过程：由用户输入作业号和作业的大小，实现分区过程。4、 分区的回收：用户输入作业号，实现分区回收，同时，分区的合并要表现出来。注意：不存在的作业号要给出错误提示！5、 分区的显示：任何时刻，可以查看当前存的情况起始地址是什么，大小多大的分区时空闲的，或者占用的，能够显示出来要求考虑：1存空间不足的情况，要有相应的显示；2作业不能同名，但是删除后可以再用这个名字； 3作业空间回收是输入作业名，回收相应的空间，如果这个作业名不存在，也要有相应的提示。三、实验代码#include<stdio.h>#include<stdlib.h>#define SIZE 640 / 存初始大小#define MINSIZE 5 / 碎片最小值enum STATE Free, Busy ;struct subAreaNode int addr; / 起始地址 int size; / 分区大小 int taskId; / 作业号 STATE state; / 分区状态 subAreaNode *pre; / 分区前向指针 subAreaNode *nxt; / 分区后向指针subHead;/ 初始化空闲分区链void intSubArea() / 分配初始分区存 subAreaNode *fir = (subAreaNode *)malloc(sizeof(subAreaNode); / 给首个分区赋值 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 <= MINSIZE) / 整块分配 p->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; 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 < tarSize) tar = p; tarSize = p->size; p = p->nxt; if(tar != NULL) / 找到要分配的空闲分区 if(tar->size - size <= MINSIZE) / 整块分配 tar->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; printf("存分配成功！n"); return 1; else / 找不到适宜的空闲分区 printf("找不到适宜的存分区，分配失败.n"); return 0; / 回收存int freeSubArea(int taskId) int flag = 0; subAreaNode *p = subHead.nxt, *pp; while(p != NULL) 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("*"); 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; / 初始化空闲分区链 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(taskId, size); / 显示空闲分区链情况 showSubArea(); else if(ope = 2) / 模拟回收存 printf("请输入要回收的作业号： "); scanf("%d", &taskId); freeSubArea(taskId); / 显示空闲分区链情况 showSubArea(); else printf("错误：请输入 0/1/2n"); printf("分配算法模拟完毕n"); return 0;运行结果：五、实验总结注意：1.标题格式黑体4号加粗，正文宋体小四 3.实验总结是通过这次实验你学到的与不足的等方面的容。每个实验一个文件夹,文件夹命名方式:实验一等,里边至少两个文件,即实验报告的Word文档和程序文件.五个实验的文件夹再放到以"学号_"命名的文件夹中，压缩后提交。实验次序：实验一作业调度 实验二动态高优先权优先调度算法 实验三时间片轮转调度算法 实验四动态分区分配管理 实验五根本分页存储管理17 / 17