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

1、操作系统课程实验报告实验名称：动态分区存储管理姓 名：王子瑜学号： 541413450235地点： 四教楼指导老师：放美专业班级： 软件工程（测试技术 14-02）实验成绩：、实验要求：熟悉并掌握动态分区分配的各种算法。 熟悉并掌握动态分区中分区回收的各种情况，并能够实现分区合并。、实验容 ：用高级语言模拟实现动态分区存储管理，要求：1、分区分配算法至少实现首次适应算法、 最佳适应算法和最坏适应算法中的至 少一种。熟悉并掌握各种算法的空闲区组织方式。2、分区的初始化可以由用户输入初始分区的大小。（初始化后只有一个空闲分区，起始地址为 0，大小是用户输入的大小）3、分区的动态分配过程：由用户输入

2、作业号和作业的大小，实现分区过程。4、分区的回收：用户输入作业号，实现分区回收，同时，分区的合并要体现出 来。（注意：不存在的作业号要给出错误提示！ ）5、分区的显示：任何时刻，可以查看当前存的情况（起始地址是什么，大小多 大的分区时空闲的，或者占用的，能够显示出来）要求考虑：（ 1）存空间不足的情况，要有相应的显示；（ 2）作业不能同名，但是删除后可以再用这个名字；（ 3）作业空间回收是输入作业名， 回收相应的空间，如果这个作业名不存在，也 要有相应的提示。三、实验代码#include<stdio.h>#include<stdlib.h>#define SIZE 64

3、0/ 存初始大小#define MINSIZE 5/ 碎片最小值enum STATE Free, Busy ;struct subAreaNode int addr;int size;/ 起始地址/ 分区大小subAreaNode *pre;subAreaNode *nxt;subHead;/ 分区前向指针/ 分区后向指针/ 初始化空闲分区链void intSubArea()/ 分配初始分区存subAreaNode *fir = (subAreaNode *)malloc(sizeof(subAreaNode);/ 给首个分区赋值fir->addr = 0;fir->size =

4、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-&g

5、t;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

6、 = 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 = NUL

7、L;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

8、= Busy;tar->taskId = taskId; else 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

9、->pre = node;tar->nxt = node;/ 分配空闲区间tar->size = size;tar->state = Busy;tar->taskId = taskId;printf(" 存分配成功！ n");return 1; else / 找不到合适的空闲分区.n");printf(" 找不到合适的存分区，分配失败return 0;/ 回收存int freeSubArea(int taskId)int flag = 0;subAreaNode *p = subHead.nxt, *pp;while(p !

10、= 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

11、;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：只合并下面的分区p

12、p = 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) pp = p;p = p-

13、>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 return 0;/ 显示空闲分区链情况void showSubArea（）printf(&quo

14、t;*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("

15、; %s |", p->state = Free ? "Free" : "Busy");if(p->taskId > 0) else printf(" ");printf("*n");p = p->nxt;*n");printf(" int main()int option, ope, taskId, size;/ 初始化空闲分区链intSubArea();/ 选择分配算法while(1)printf(" 请选择要模拟的分配算法：0 表示首次适应算法，

16、 1 表示最佳适应算法 n");scanf("%d", &option);if(option = 0) break; else if(option = 1) printf(" 你选择了最佳适应算法，下面进行算法的模拟break; else printf(" 错误：请输入 0/1nn");n");/ 模拟动态分区分配算法while(1)printf("n");printf(*n");printf("* 1: 分配存 2: 回收存 0: 退出 *n");printf(*n

17、");scanf("%d", &ope);if(ope = 0) break;if(ope = 1) / 模拟分配存printf(" 请输入作业号： ");scanf("%d", &taskId);scanf("%d", &size);if(size <= 0) n");printf(" 错误：分配存大小必须为正值continue;/ 调用分配算法if(option = 0) firstFit(taskId, size); else bestFit(tas

18、kId, size);/ 显示空闲分区链情况showSubArea(); else if(ope = 2) / 模拟回收存printf(" 请输入要回收的作业号： ");scanf("%d", &taskId);freeSubArea(taskId);/ 显示空闲分区链情况showSubArea(); else printf（" 分配算法模拟结束 n"）;return 0;运行结果：当前的內存分配情况如下，-起始地址:空间大小：工作状态：作业号*«-*0k !50k !Busyi i150k !70k 1Busy!3120k !100k !Bus yii2* »* *220300kMBk! 80!105k ! k !BusyBusy1 OHB MMMM11