可变分区存储管理的内存分配算法模拟实现----最佳适应算法

操作系统实验可变分区内存分配首次适应算法模拟(总6页)--本页仅作为文档封面，使用时请直接删除即可----内页可以根据需求调整合适字体及大小--题目可变分区内存分配首次适应算法模拟姓名：学号：专业：学院：指导教师：林夕二零一八年十一月一、实验目的主存的分配和回收的实现与主存储器的管理方式有关的，通过本实验帮助学生理解在可变分区管理方式下应怎样实现主存空间的分配和回收。

二、实验内容及原理编写一个内存动态分区分配模拟程序，模拟内存的分配和回收的完整过程。

模拟在可变分区管理方式下采用最先适应算法实现主存分配和回收。

可变分区方式是按作业需要的主存空间大小来分割分区的。

当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。

随着作业的装入、撤离，主存空间被分成许多个分区，有的分区被作业占用，而有的分区是空闲的。

当进程运行完毕释放内存，系统根据回收区的首址，从空闲区链表中找到相应的插入点，此时可能出现以下4种情况之一：1.回收区与插入点的前一个空闲分区F1相邻接，此时将两个分区合并2.回收区与插入点的后一个空闲分区F2相邻接，此时将两个分区合并3.回收区与插入点的前，后两个空闲分区相邻接，此时将三个分区合并4.回收区既不与F1相邻接，又不与F2相邻接，此时应为回收区单独建立一个新表项三、程序设计1.算法流程3.详细设计（1）定义两个结构体struct kongxian ength>=len) tart=kongxian[i].start;zuoye[n2].end=zuoye[n2].start+len;zuoye[n2].length=len;n2++; ength==len) tart=kongxian[j+1].start;kongxian[j].end=kongxian[j+1].end;kongxian[j].length=kongxian[j+1].length;}n1--;}else tart+=len;kongxian[i].length-=len;}}（3）回收作业：printf("输入要回收的作业ID ");scanf("%d",&id);front=middle=behind=0;for(i=0;i<n1;i++){if(kongxian[i].start>zuoye[id].end)break;if(kongxian[i].end==zuoye[id].start) tart==zuoye[id].end)tart-(*(struct kongxian *)b).start;}int cmp2(const void *a,const void *b){return (*(struct zuoye *)a).start-(*(struct zuoye *)b).start;}void init(){n1=1; tart=0;kongxian[0].end=1023;kongxian[0].length=1024;}void print1() tart,kongxian[i].end,kongxian[i].length);}void print2() tart,zuoye[i].end,zuoye[i].length);}int main(){int i,j,k,t,len,flag,id;int front,middle, behind;int t1,t2;init();print1();printf("输入1装入新作业，输入0回收作业，输入-1结束\n");while(scanf("%d",&t)!=EOF){if(t==1) ength>=len) tart=kongxian[i].start;zuoye[n2].end=zuoye[n2].start+len;zuoye[n2].length=len;n2++; ength==len) tart=kongxian[j+1].start;kongxian[j].end=kongxian[j+1].end;kongxian[j].length=kongxian[j+1].length;}n1--;}else tart+=len;kongxian[i].length-=len;}}}else if(t==0){printf("输入要回收的作业ID ");scanf("%d",&id);front=middle=behind=0;for(i=0;i<n1;i++){if(kongxian[i].start>zuoye[id].end)break;if(kongxian[i].end==zuoye[id].start)tart==zuoye[id].end) tart=zuoye[id].start;kongxian[n1].end=zuoye[id].end;kongxian[n1].length=zuoye[id].length;n1++; tart=zuoye[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}if(front &&behind) nd+=zuoye[id].length;kongxian[t1].length+=zuoye[id].length;for(j=id;j<n2-1;j++) tart=zuoye[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}if(middle) nd=kongxian[t2].end;kongxian[t1].length+=(zuoye[id].length+kongxian[t2].length);tart=kongxian[j+1].start;kongxian[j].end=kongxian[j+1].end;kongxian[j].length=kongxian[j+1].length;}n1--;for(j=id;j<n2-1;j++) tart=zuoye[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}if(behind &&!middle) tart-=zuoye[id].length;kongxian[t2].length+=zuoye[id].length;for(j=id;j<n2-1;j++) tart=zuoye[j+1].start;zuoye[j].end=zuoye[j+1].end;zuoye[j].length=zuoye[j+1].length;}n2--;}}else{printf("操作结束\n");break;}print1();print2();}return 0;}。

《操作系统》课程设计说明书题目：模拟实现可变分区存储管理班级：学号：姓名：指导老师：1．目的和要求在熟练掌握计算机分区存储管理方式的原理的基础上，利用一种程序设计语言模拟实现操作系统的可变分区存储管理的功能，一方面加深对原理的理解，另一方面提高学生通过编程根据已有原理解决实际问题的能力，为学生将来进行系统软件开发和针对实际问题提出高效的软件解决方案打下基础。

2．设计内容设计合理的数据结构来描述存储空间：对于未分配出去的部分，可以用空闲分区队列或空闲分区链表来描述，对于已经分配出去的部分，由装入内存的作业占据，可以将作业组织成链表或数组。

实现分区存储管理的内存分配功能，实现两种适应算法：首次适应算法，最坏适应算法。

实现分区存储管理的内存回收算法：要求能够正确处理回收分区与空闲分区的四种邻接关系。

当碎片产生时，能够进行碎片的拼接。

3．设计环境Windows操作系统、DEV C++C语言4．程序概要（1）数据结构和全局变量int type = 0; //算法类型//空闲分区struct freelink {int len; //len为分区长度int address; //address为分区起始地址struct freelink *next;};//占用分区struct busylink {char name; //作业或进程名,name='S' 表示OS占用int len;int address;struct busylink *next;};struct freelink *free_head = NULL; //自由链队首指针struct busylink *busy_head = NULL, //占用区队首指针*busy_tail = NULL; //占用区队尾指针（2）功能模块划分大体上可以将整个程序的模块划分成如下几个部分：1）主模块：主要是初始化（设置物理内存的用户区的大小，选取适应算法）和界面，界面参考如下：2）内存分配算法（实现两种适应算法：最坏适应算法，首次适应算法）3）内存回收算法（考虑四种邻接情况，尤其是采用最佳（坏）适应算法时的分区合并）4）碎片拼接算法5）空闲分区队列显示6）占用分区队列显示（3）各函数调用关系（4）主要函数流程图allocateMemoByWF();//两种算法分配回收大致相同，在这里只列举一种compactMemo()freeMemoByWF()5. 源代码#include <stdio.h>#include <stdlib.h>#define MAX_SIZE 512 //系统能分配的最大内存#define FALSE 0#define TRUE 1int type = 0; //算法类型//空闲分区struct freelink {int len; //len为分区长度int address; //address为分区起始地址struct freelink *next;};//占用分区struct busylink {char name; //作业或进程名,name='S' 表示OS占用int len;int address;struct busylink *next;};struct freelink *free_head = NULL; //自由链队列（带头结点）队首指针struct busylink *busy_head = NULL, //占用区队列队（带头结点）首指针*busy_tail = NULL; //占用区队列队尾指针//初始化void init() {struct freelink *p;struct busylink *q;free_head = (struct freelink*)malloc(sizeof(struct freelink));free_head->next = NULL; // 创建自由链头结点busy_head = busy_tail = (struct busylink*)malloc(sizeof(struct busylink));busy_head->next = NULL; // 创建占用链头结点p = (struct freelink *)malloc(sizeof(struct freelink));p->address = 64;p->len = MAX_SIZE - 64; //（OS占用了64K）p->next = NULL;free_head->next = p;q = (struct busylink *)malloc(sizeof(struct busylink));q->name = 'S'; //S表示操作系统占用q->len = 64;q->address = 0;q->next = NULL;busy_head->next = q;busy_tail = q;}//紧凑struct freelink* compactMemo(int require) {int sum = 0;struct freelink *fNode = free_head->next;while (fNode != NULL) {sum += fNode->len;fNode = fNode->next;}printf("\n");if (sum < require) {return NULL;}//删除空闲区所有节点struct freelink *p = free_head->next; //让p一直指向第一个数据节点while (p != NULL) {free_head->next = p->next;free(p);p = free_head->next;}//创建新的分区struct freelink *node = (struct freelink*)malloc(sizeof(struct freelink));node->address = 0;node->len = MAX_SIZE;free_head->next = node;node->next = NULL;//修改占用区作业内存地址struct busylink *q = busy_head->next;while (q != NULL) {q->address = node->address;node->len -= q->len;node->address += q->len;q = q->next;}return node;}//最坏（佳）适应算法在分区合并和分割后需要调整分区位置int adjust(struct freelink *node) {struct freelink *p = free_head;//合并后链表中只剩一个分区if (p->next == NULL) {free_head->next = node;node->next = NULL;return TRUE;}while (p->next != NULL && node->len <= p->next->len) { p = p->next;}if (p->next == NULL) {p->next = node;node->next = NULL;}else {node->next = p->next;p->next = node;}return TRUE;}//最坏适应算法int allocateMemoByWF() {int require;printf("请输入作业所需内存大小：");scanf("%d", &require);//判断第一个空闲分区大小是否满足需求struct freelink *p = free_head->next;if (p->len < require) {printf("没有分区满足要求,正在尝试碎片拼接...\n");//判断所有分区容量总和是否满足要求if ((p = compactMemo(require)) == NULL) {return FALSE;}}//将第一个空闲分区切割require分配给该作业struct busylink *q = (struct busylink *)malloc(sizeof(struct busylink));printf("请输入作业名称：");getchar(); //输入require之后有一个换行符，用getchar吃掉scanf("%c", &q->name);//检查是否重名struct busylink *temp = busy_head->next;while (temp != NULL && temp->name != q->name) {temp = temp->next;}if (temp != NULL) {printf("该作业名已存在！\n");return FALSE;}q->len = require;q->address = p->address;q->next = NULL;//将作业按地址递增的顺序插入到作业队列中temp = busy_head;while(temp->next != NULL && q->address > temp->next->address) { temp = temp->next;}if (temp->next == NULL) {temp->next = q;q->next = NULL;}else {q->next = temp->next;temp->next = q;}//分割空闲分区if (p->len == require) {free(p);return TRUE;}else {p->address += require;p->len -= require;}//把第一个分区从空闲区中拿出来if (p->next != NULL) {free_head->next = p->next;}else return TRUE; //空闲队列中是否只存在一个节点//将分割后的分区放到合适的位置adjust(p);return TRUE;}//首次适应算法int allocateMemoByFF() {int require;printf("请输入作业所需内存大小：");scanf("%d", &require);struct freelink *p = free_head->next;struct freelink *pre = free_head;while (p != NULL && p->len < require) {pre = p;p = p->next;}if (p == NULL) {printf("没有分区满足要求,正在尝试碎片拼接...\n");//判断所有分区容量总和是否满足要求if ((p = compactMemo(require)) == NULL) {return FALSE;}}//将第一个满足条件的分区分割合适的内存分配给作业struct busylink *q = (struct busylink *)malloc(sizeof(struct busylink));printf("请输入作业名称：");getchar(); //输入require之后有一个换行符，用getchar吃掉scanf("%c", &q->name);//检查是否重名struct busylink *temp = busy_head->next;while (temp != NULL && temp->name != q->name) {temp = temp->next;}if (temp != NULL) {printf("该作业名已存在！\n");return FALSE;}q->len = require;q->address = p->address;q->next = NULL;//将作业按地址递增的顺序插入到作业队列中temp = busy_head;while(temp->next != NULL && q->address > temp->next->address) { temp = temp->next;}if (temp->next == NULL) {temp->next = q;q->next = NULL;}else {q->next = temp->next;temp->next = q;}//分割空闲分区if (p->len == require) {pre->next = p->next;free(p);return TRUE;}else {p->address += require;p->len -= require;return TRUE;}}//匹配节点并创建回收分区struct freelink* matchName(char name) {struct busylink *q = busy_head;struct freelink *node = (struct freelink *)malloc(sizeof(struct freelink));//找到匹配节点的前一个while (q->next != NULL && q->next->name != name) {q = q->next;}if (q->next == NULL) {printf("%c进程不存在\n",name);return NULL;}//接收匹配节点的内存信息node->len = q->next->len;node->address = q->next->address;//在占用分区中删除匹配的节点struct busylink *temp = q->next;if (q->next == busy_tail) {busy_tail = q;q->next = NULL;}else {q->next = q->next->next;}free(temp);return node;}int freeMemoByWF() {printf("请输入作业名称:");char name;getchar();scanf("%c", &name);printf("\n");//将内存(即node节点)放回空闲区struct freelink *node;if ((node = matchName(name)) == NULL) {return FALSE;}struct freelink *p = free_head->next;struct freelink *pre = free_head;//三种邻接情况(合并后需要重新根据大小排序)while (p != NULL) {//与下一分区邻接if (node->address + node->len == p->address) {//与上一分区邻接if (p->next != NULL&&p->next->address + p->next->len == node->address) {struct freelink* temp = p->next;temp->len = temp->len + p->len + node->len;free(node);pre->next = temp->next;free(p);adjust(temp);printf("回收成功!\n");return TRUE;}else {p->address = node->address;p->len += node->len;free(node);pre->next = p->next; //把合并后分区取出来adjust(p);printf("回收成功!\n");return TRUE;}}//与上一分区邻接if (p->address + p->len == node->address) {//同时与下一分区邻接if (p->next != NULL &&node->address + node->len == p->next->address) {p->len = p->len + node->len + p->next->len;pre->next = p->next->next;free(p->next);free(node);adjust(p);printf("回收成功!\n");return TRUE;}else {p->len += node->len;free(node);pre->next = p->next;adjust(p);printf("回收成功!\n");return TRUE;}}pre = p;p = p->next;}//不邻接adjust(node);printf("回收成功!\n");return TRUE;}int freeMemoByFF() {printf("请输入作业名称:");char name;getchar();scanf("%c", &name);printf("\n");//将内存(node节点)放回空闲区struct freelink *node;if ((node = matchName(name)) == FALSE) {return FALSE;}struct freelink *p = free_head->next;//三种邻接情况while (p != NULL) {//与下一分区邻接if (node->address + node->len == p->address) {p->address = node->address;p->len += node->len;free(node);printf("回收成功!\n");return TRUE;}//与上一分区邻接if (p->address + p->len == node->address) {//同时与下一分区邻接if (p->next != NULL &&node->address + node->len == p->next->address) {p->len = p->len + node->len + p->next->len;struct freelink* temp = p->next;p->next = p->next->next;free(temp);free(node);printf("回收成功!\n");return TRUE;}else {p->len += node->len;free(node);printf("回收成功!\n");return TRUE;}}p = p->next;}//不邻接p = free_head;while (p->next != NULL && node->address > p->next->address) { p = p->next;}if (p->next == NULL) {p->next = node;node->next = NULL;}/*回收分区是分区链中地址最大的一个*/else {node->next = p->next;p->next = node;}printf("回收成功!\n");return TRUE;}//输出空闲分区void printFreeLink() {struct freelink *p = free_head->next;printf("空闲分区：\n");while (p != NULL) {printf("分区起始地址:%d ", p->address);printf("分区大小:%d\n", p->len);p = p->next;}printf("\n");}//输出占用分区void printBusyLink() {struct busylink *q = busy_head->next;printf("占用分区：\n");while (q != NULL) {printf("进程名：%c ", q->name);printf("起始地址：%d ", q->address);printf("占用内存大小：%d\n", q->len);q = q->next;}printf("\n");}void WF() {while(1) {printf("----------------------------------------------------------------\n");printf("1. 初始化\n\n");printf("2. 作业进入内存\n\n");printf("3. 作业完成\n\n");printf("4. 显示当前自由分区\n\n");printf("5. 显示当前作业占用分区\n\n");printf("6. 退出\n");printf("----------------------------------------------------------------\n");int m;scanf("%d", &m);printf("\n");switch(m) {case 1: init(); break;case 2: allocateMemoByWF(); break;case 3: freeMemoByWF(); break;case 4: printFreeLink(); break;case 5: printBusyLink(); break;case 6: return;}}}void FF() {while(1) {printf("----------------------------------------------------------------\n");printf("1. 初始化\n\n");printf("2. 作业进入内存\n\n");printf("3. 作业完成\n\n");printf("4. 显示当前自由分区\n\n");printf("5. 显示当前作业占用分区\n\n");printf("6. 退出\n");printf("----------------------------------------------------------------\n");int m;scanf("%d", &m);printf("\n");switch(m) {case 1: init(); break;case 2: allocateMemoByFF(); break;case 3: freeMemoByFF(); break;case 4: printFreeLink(); break;case 5: printBusyLink(); break;case 6: return;}}}int main() {while(1) {printf("----------------------------------------------------------------\n");printf("1. 首次适应算法\n\n");printf("2. 最坏适应算法\n\n");printf("3. 退出\n");printf("----------------------------------------------------------------\n");int m;scanf("%d", &m);printf("\n");switch(m) {case 1: FF(); break;case 2: WF(); break;case 3: exit(0);}}}6. 实验结果：1.最坏适应算法：A(16), B(32), C(64), D(128)分配（成功）：分配失败（重名）：当前空闲区和占用区情况：free(A)//不邻接回收成功:回收失败（不存在该进程）：当前空闲区和占用区情况：free(C)当前空闲区情况：free(B)//与上下分区邻接当前空闲区情况：E(100)当前空闲区情况：F(200)没有分区满足时尝试碎片拼接当前空闲区和占用区情况：最坏适应算法有一种情况：A(40), B(50), C(60), D(50)free(A), free(C)与首次适应分配不同，最坏适应算法可能高地址在低地址前free(B)2. 首次适应算法：A(16), B(32), C(64), D(128),E(10),F(5),free(F)free(A), free(C)free(B)G(200)在分配内存过程中，将作业加入到占用队列时是按地址递增的顺序排列，保证了拼凑算法后各作业的相对位置不变化7. 实验总结：a)以前对链表操作有一些误操作，比如排序时，一般使用冒泡法。

河北联合大学20XX-20XX学年第二学期操作系统课程上机实验报告班级学号姓名成绩指导教师卢朝辉信息工程学院计算机系实验2：可变分区存储管理程序模拟实验目的：编写程序来模拟计算机的四种调度方式：（1）最佳适应算法（2）最坏适应算法（3）首次适应算法（4）下次适应算法程序设计：因为该实验室在上个个实验的基础上写的对类做了以下调整：Job类：加了一个属性int needSize; //所需内存大小jobList类：给needSize赋初值sortm类：该类是新加的，用于管理内存。

public class sortm{int jobId; int start; int end;}程序算法介绍：(1)进内存函数算法图：（2）首次适应、最坏适应、首次适应、下次适应算法图中给出的是最差适应，worstfitposition的值指的是下个作业放在谁后面。

图中作业job13进入内存时，最好位置为10，最坏为2，因为是最坏算法。

所以Job13去列表第2的后面。

排在3的位置。

程序源码：public static void inlist_1(int currentTime,ArrayList jobl){ Iterator it= jobl.iterator(); //遍历当前已经生成的作业int delnum=0; //记录进内存的作业数while(it.hasNext()){ Job l=(Job)it.next(); //取第一条作业if(currentTime==0) //当前时间为0，去第一条作业，推出循环。

{ sortjworst(l);jl.add(l);//wei//System.out.println("add"+l.jobId);delnum++;break;}if(l.createTime<currentTime) //当前作业时间小于创建时间{ if(sortjworst(l)) //看能否进内存{jl.add(l); //进内存，进就绪队列delnum++; //数目加1else //不能进退出循环{break; }}else{if(jl.size()==0) //大于当前时间，就绪队列没作业{sortjworst(l); //进内存，进就绪队列jl.add(l);delnum++;} //数目加1else{break; } //不能进退出}}for(int i=0;i<delnum;i++) //删除等待队列已经进就绪的作业{jobl.remove(0); }}。

在可变分区存储管理中,最优适应分配算法
最优适应分配算法(optimal fit algorithm)是可变分区存储管理中常用的算法，它是以一种有效而实用方式来利用磁盘存储空间的技术，目的是使用最小的空间来存放最多的文件。

一、算法简介
最优适应分配算法是在可变分区存储管理系统中应用最多的一种有效算法。

它通过寻找和利用未被利用的空间，有效地管理存储空间，减少内存的浪费。

此算法的基本原理是比较进程的内存空间需求和当前空闲分区的剩余空间，选择一个空闲分区分配给进程，使得分配的这块空间刚好能够满足进程的内存空间需求。

二、算法的优势
1、空间利用率高：最优适应分配算法做了色样的优化，通过对比空闲区和进程大小，可以在多个空闲区中选择一个最合适的空间来分配，这就有效地将空闲分区完全利用起来。

2、降低内存碎片：最优适应分配算法在进行存储空间的分配时，给每一个进程的存储空间要求满足有效利用完可用的空闲分区，这样就可以有效地降低内存碎片的影响。

3、处理时间短暂：最优适应分配算法虽然空间利用率高，但是相对地，其耗费的时间是少的，因此，这种算法可以满足时间要求，确保效率。

三、应用情况
最优适应分配算法主要用于可变分区存储管理技术，这种技术可以有效地管理大量文件，而不会浪费空间。

而且现在，这种算法已经被广泛应用于嵌入式系统中，专家们尤其是在嵌入式系统设计中广泛地使用最优适应分配算法，以在CPU装入的程序数量、运行程序数量不变的情况下，达到最大的利用空间效果。

可变分区存储管理方式的最先适应分配算法设计与实现一、引言可变分区存储管理方式是操作系统中一种常用的内存分配策略，它能够高效地管理内存空间，提高计算机系统的内存利用率。

而最先适应分配算法作为可变分区存储管理方式的一种重要实现方式，被广泛应用于操作系统中。

本文将围绕任务主题，从算法设计与实现的角度，对最先适应算法进行全面、详细、完整且深入地探讨。

二、最先适应分配算法概述最先适应分配算法是一种基于可变分区存储管理方式的内存分配算法。

其核心思想是从内存空闲区域中找到第一个大小能够满足作业需求的分区进行分配。

具体步骤如下： 1. 从内存区域起始地址开始顺序查找，找到第一个大小能够满足作业需求的空闲区域。

2. 如果找到了满足需求的空闲区域，则将作业分配到该分区，并对其进行划分。

若剩余空间大于一个最小分区大小，将剩余空闲区域插入到空闲区链表中。

3. 如果找不到满足需求的空闲区域，则内存空间不足，需等待释放空间后进行分配。

三、最先适应分配算法的设计与实现最先适应分配算法的设计主要涉及以下几个关键步骤：空闲区管理、作业分配和释放空间等。

下面将分别进行详细介绍。

3.1 空闲区管理在最先适应分配算法中，空闲区的管理与分配密切相关。

通常采用链表的形式来管理空闲区，每个节点记录该空闲区的起始地址和大小。

在作业分配时，需要遍历链表找到第一个满足要求的空闲区进行分配。

在释放空间时，需要将释放的空间节点加入链表并进行合并操作，以减少碎片化问题。

3.2 作业分配作业分配是最先适应分配算法中的核心操作，其实现步骤如下： 1. 获取作业的大小。

2. 遍历空闲区链表，找到第一个大小能够满足作业需求的空闲区。

3. 如果找到了合适的空闲区，则进行分配。

将该空闲区划分为已分配区域和剩余空闲区域。

如果剩余空闲区域大小大于最小分区大小，将其插入到空闲区链表中。

4. 如果找不到满足作业需求的空闲区，则内存空间不足，需等待释放空间后进行分配。

实验题目：最佳适应算法模拟实现内存分配与回收目录一、概述 (3)1．设计目的 (3)2．开发环境 (3)3．任务分配 (3)二、需求分析 (3)三、实验基本原理 (4)1．可变分区存储管理之最优适应分配算法的概念 (4)2．关于最优适应分配算法的一些基本原理 (4)四、数据结构设计 (4)1．内存块与作业块 (4)2．程序流程图 (5)2.1．整体程序流程图 (5)2.2．内存分配allocate()流程图 (6)2.3．内存回收callback()流程图 (7)五、算法的实现 (7)1．程序主要功能函数设计思想 (7)2．源程序清单 (8)3．测试用例与程序运行结果截图 (18)六、总结 (21)1．经验总结 (21)2．心得与体会 (21)七、参考文献 (22)1一、概述1、设计目的（1）了解多道程序系统中，多个进程并发执行的内存资源分配。

（2）模拟可变分区存储管理算法实现分区管理的最佳适应分配算法（3）利用最佳适应算法动态实现内存分配与回收（3）通过实现最佳算法来进一步了解动态分区模式的优缺点。

（4）掌握最佳适应分配算法，深刻了解各进程在内存中的具体分配策略。

2、开发环境PC机DOS;WINDOWS环境Visual C++6.0 for Windows二、需求分析克服固定分区中的主存资源的浪费，有利于多道程序设计，提高主存资源的利用率。

三、实验基本原理１、可变分区存储管理之最优适应算法分配的概念：分区存储管理是给内存中的进程划分适当大小的存储区，以连续存储各进程的程序和数据，使各进程能并发地执行。

最优适应分配算法扫描整个未分配区表或链表，从空闲区中挑选一个能满足用户进程要求的最小分区进行分配。

2、关于最优适应的一些基本原理：在可变分区模式下，在系统初启且用户作业尚未装入主存储器之前，整个用户区是一个大空闲分区，随着作业的装入和撤离，主存空间被分成许多分区，有的分区被占用，而有的分区时空闲的。

实验4 可变分区的内存分配算法模拟1.实验目的通过模拟可变分区的以下内存分配算法，掌握连续分配存储器管理的特点，掌握以下四种分配算法的优缺点并进行对比。

（1）首次适应分配算法；（2）循环适应分配算法；（3）最佳适应分配算法；（4）最坏适应分配算法。

2.实验环境装有操作系统Windows XP和开发工具VC++6.0，内存在256M以上的微机；或者：装有Linux(Fedora 7)操作系统和gcc编译器，内存在256M以上的微机。

3.实验内容（1）用户可用的内存空间为64K，按下面的现有分区情况进行初始化，可在屏幕上显示（2）接收用户进程的内存申请格式为：作业名、申请空间的大小。

按照上述的一种分配算法进行分配，修改空闲分区表，并在屏幕上显示分配后的内存状态。

（3）用户进程执行完成后，或者从外部撤销用户进程，将内存进行回收，修改空闲分区表，并在屏幕上显示回收后的内存状态。

4.实验要求(1)将四种算法的源程序及程序执行结果写入实验报告；(2)将四种算法的工作机理写入实验报告。

代码：#include<iostream.h>#include<stdlib.h>#define Free 0 //空闲状态#define Busy 1 //已用状态#define OK 1 //完成#define ERROR 0 //出错#define MAX_length 64 //最大内存空间为64KB typedef int Status;int flag;typedef struct freearea//定义一个空闲区说明表结构{long size; //分区大小long address; //分区地址int state; //状态}ElemType;// 线性表的双向链表存储结构typedef struct DuLNode{ElemType data;struct DuLNode *prior; //前趋指针struct DuLNode *next; //后继指针}DuLNode,*DuLinkList;DuLinkList block_first; //头结点DuLinkList block_last; //尾结点Status alloc(int);//内存分配Status free(int); //内存回收Status First_fit(int);//首次适应算法Status Best_fit(int); //最佳适应算法Status Worst_fit(int); //最差适应算法void show();//查看分配Status Initblock();//开创空间表Status Initblock()//开创带头结点的内存空间链表{block_first=(DuLinkList)malloc(sizeof(DuLNode));block_last=(DuLinkList)malloc(sizeof(DuLNode));block_first->prior=NULL;block_first->next=block_last;block_last->prior=block_first;block_last->next=NULL;block_last->data.address=0;block_last->data.size=MAX_length;block_last->data.state=Free;return OK;}//分配主存Status alloc(int ch){int request = 0;cout<<"请输入需要分配的主存大小(单位:KB)：";cin>>request;if(request<0 ||request==0){cout<<"分配大小不合适，请重试！"<<endl;return ERROR;}if(ch==2) //选择最佳适应算法{if(Best_fit(request)==OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;return OK;}if(ch==3) //选择最差适应算法{if(Worst_fit(request)==OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;return OK;}else //默认首次适应算法{if(First_fit(request)==OK) cout<<"分配成功！"<<endl;else cout<<"内存不足，分配失败！"<<endl;return OK;}}//首次适应算法Status First_fit(int request){//为申请作业开辟新空间且初始化DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;while(p){if(p->data.state==Free && p->data.size==request){//有大小恰好合适的空闲块p->data.state=Busy;return OK;break;}if(p->data.state==Free && p->data.size>request){//有空闲块能满足需求且有剩余temp->prior=p->prior;temp->next=p;temp->data.address=p->data.address;p->prior->next=temp;p->prior=temp;p->data.address=temp->data.address+temp->data.size;p->data.size-=request;return OK;break;}p=p->next;}return ERROR;}//最佳适应算法Status Best_fit(int request){int ch; //记录最小剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; //记录最佳插入位置while(p) //初始化最小空间和最佳位置{if(p->data.state==Free && (p->data.size>=request) ){if(q==NULL){q=p;ch=p->data.size-request;}else if(q->data.size > p->data.size){q=p;ch=p->data.size-request;}}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else if(q->data.size==request){q->data.state=Busy;return OK;}else{temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.size=ch;return OK;}return OK;}//最差适应算法Status Worst_fit(int request){int ch; //记录最大剩余空间DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode));temp->data.size=request;temp->data.state=Busy;DuLNode *p=block_first->next;DuLNode *q=NULL; //记录最佳插入位置while(p) //初始化最大空间和最佳位置{if(p->data.state==Free && (p->data.size>=request) ){if(q==NULL){q=p;ch=p->data.size-request;}else if(q->data.size < p->data.size){q=p;ch=p->data.size-request;}}p=p->next;}if(q==NULL) return ERROR;//没有找到空闲块else if(q->data.size==request){q->data.state=Busy;return OK;}else{temp->prior=q->prior;temp->next=q;temp->data.address=q->data.address;q->prior->next=temp;q->prior=temp;q->data.address+=request;q->data.size=ch;return OK;}return OK;}//主存回收Status free(int flag){DuLNode *p=block_first;for(int i= 0; i <= flag; i++)if(p!=NULL)p=p->next;elsereturn ERROR;p->data.state=Free;if(p->prior!=block_first && p->prior->data.state==Free)//与前面的空闲块相连{p->prior->data.size+=p->data.size;p->prior->next=p->next;p->next->prior=p->prior;p=p->prior;}if(p->next!=block_last && p->next->data.state==Free)//与后面的空闲块相连{p->data.size+=p->next->data.size;p->next->next->prior=p;p->next=p->next->next;}if(p->next==block_last && p->next->data.state==Free)//与最后的空闲块相连{p->data.size+=p->next->data.size;p->next=NULL;}return OK;}//显示主存分配情况void show(){int flag = 0;cout<<"\n主存分配情况:\n";cout<<"++++++++++++++++++++++++++++++++++++++++++++++\n\n";DuLNode *p=block_first->next;cout<<"分区号\t起始地址\t分区大小\t状态\n\n";while(p){cout<<" "<<flag++<<"\t";cout<<" "<<p->data.address<<"\t\t";cout<<" "<<p->data.size<<"KB\t\t";if(p->data.state==Free) cout<<"空闲\n\n";else cout<<"已分配\n\n";p=p->next;}cout<<"++++++++++++++++++++++++++++++++++++++++++++++\n\n"; }//主函数void main(){int ch;//算法选择标记cout<<"请输入所使用的内存分配算法：\n";cout<<"(1)首次适应算法\n(2)最佳适应算法\n(3)最差适应算法\n";cin>>ch;while(ch<1||ch>3){cout<<"输入错误，请重新输入所使用的内存分配算法：\n";cin>>ch;}Initblock(); //开创空间表int choice; //操作选择标记while(1){show();cout<<"请输入您的操作：";cout<<"\n1: 分配内存\n2: 回收内存\n0: 退出\n";cin>>choice;if(choice==1) alloc(ch); // 分配内存else if(choice==2) // 内存回收{int flag;cout<<"请输入您要释放的分区号：";cin>>flag;free(flag);}else if(choice==0) break; //退出else //输入操作有误{cout<<"输入有误，请重试！"<<endl;continue;}}}结果：首次适应算法（First Fit）：从空闲分区表的第一个表目起查找该表，把最先能够满足要求的空闲区分配给作业，这种方法目的在于减少查找时间。

c模拟内存分配算法（⾸次适应算法，最佳适应算法，最坏适应算法）#include<bits/stdc++.h>using namespace std;/*定义内存的⼤⼩为100*/#define MEMSIZE 100/*如果⼩于此值，将不再分割内存*/#define MINSIZE 2/*内存分区空间表结构*/typedef struct _MemoryInfomation{/*起始地址*/int start;/*⼤⼩*/int Size;/*状态 F:空闲(Free) U:占⽤(Used) E 结束(End)*/char status;} MEMINFO;/*内存空间信息表*/MEMINFO MemList[MEMSIZE];/*显⽰内存状态*/void Display(){int i,used=0;//记录可以使⽤的总空间量printf("\n---------------------------------------------------\n");printf("%5s%15s%15s%15s","Number","start","size","status");printf("\n---------------------------------------------------\n");for(i=0; i<MEMSIZE&&MemList[i].status!='e'; i++){if(MemList[i].status=='u'){used+=MemList[i].Size;}printf("%5d%15d%15d%15s\n",i,MemList[i].start,MemList[i].Size,MemList[i].status=='u'?"USED":"FREE");}printf("\n----------------------------------------------\n");printf("Totalsize:%-10d Used:%-10d Free:%-10d\n",MEMSIZE,used,MEMSIZE-used);}/*初始化所有变量*/void InitMemList(){int i;MEMINFO temp= {0,0,'e'};//初始化空间信息表for(i=0; i<MEMSIZE; i++){MemList[i]=temp;}//起始地址为0MemList[0].start=0;//空间初始为最⼤MemList[0].Size=MEMSIZE;//状态为空闲MemList[0].status='f';}/*最先适应算法*//*算法原理分析：将空闲的内存区按其在储存空间中的起始地址递增的顺序排列，为作业分配储存空间时，从空闲区链的始端开始查找，选择第⼀个满⾜要求的空闲区，⽽不管它究竟有多⼤优点:1.在释放内存分区的时候，如果有相邻的空⽩区就进⾏合并，使其成为⼀个较⼤的空⽩区2.此算法的实质是尽可能的利⽤储存器的低地址部分，在⾼地址部分则保留多的或较⼤的空⽩区，以后如果需要较⼤的空⽩区，就容易满⾜缺点：1.在低地址部分很快集中了许多⾮常⼩的空⽩区，因⽽在空⽩区分配时，搜索次数增加，影响⼯作效率。

可变分区存储管理的内存分配算法模拟实现----最佳适应算法-回复可变分区存储管理是一种常用的内存分配算法，用于管理计算机系统中的内存空间。

其中，最佳适应算法是其中一种经典的实现方式。

本文将围绕最佳适应算法展开，详细介绍其原理、实现方法以及优缺点。

首先，我们需要明确什么是可变分区存储管理。

在计算机系统中，内存是被划分为多个可用的分区，每个分区有不同的大小。

当一个程序需要内存时，系统会选择一个适合该程序大小的分区进行分配。

使用可变分区存储管理算法，系统可以灵活地分配和回收内存，并提高内存的利用率。

最佳适应算法是可变分区存储管理中的一种常用算法。

其核心思想是始终选择最小但足够容纳所需内存的分区进行分配。

这样可以最大程度地减少内存碎片的产生，提高系统内存利用率。

下面我们将一步一步来模拟实现最佳适应算法。

首先，我们需要创建一个数据结构来表示内存分区。

我们可以使用一个链表来存储每个分区的信息，每个节点包含分区的起始地址、结束地址和大小。

初始时，整个内存空间被视为一个大的可用分区。

接下来，当一个程序需要内存时，我们需要遍历整个分区链表，找到一个大小不小于所需内存的最小分区。

我们可以使用一个变量来记录当前找到的最小分区的大小，以及一个指针来指向该分区节点。

在遍历过程中，如果找到一个分区的大小恰好等于所需内存，那么直接分配给程序，并将该节点从链表中删除即可。

如果找到的分区的大小大于所需内存，我们需要进行分割操作。

即将该分区分成两个部分，一个部分分配给程序，另一个部分保留未分配状态，并将其添加到链表中。

同时，我们需要更新原有分区节点的起始地址和大小。

最后，当一个程序终止并释放内存时，我们需要将该内存块归还给系统，并进行合并操作。

即将释放的内存块与相邻的空闲内存块进行合并，以减少内存碎片。

通过以上步骤，我们可以实现最佳适应算法来管理内存分配。

但是，最佳适应算法也有其优缺点。

首先，最佳适应算法相对于其他算法来说，可以更好地减少内存碎片的产生。

一．实验目的经过编写和调试储存管理的模拟程序以加深对储存管理方案的理解，熟习可变分区储存管理的内存分派和回收。

二．实验内容1．确立内存空间分派表；2．采纳最优适应算法达成内存空间的分派和回收；3．编写主函数对所做工作进行测试。

三．实验背景资料因为可变分区的大小是由作业需求量决定的，故分区的长度是早先不固定的，且分区的个数也随内存分派和回收改动。

总之，所有分区状况随时可能发生变化，数据表格的设计一定和这个特色相适应。

因为分区长度不一样，所以设计的表格应当包含分区在内存中的开端地点和长度。

因为分派时安闲区有时会变为两个分区：安闲区和已分分区，回收内存分区时，可能会集并安闲分区，这样假如整个内存采纳一张表格记录己分分区和安闲区，就会使表格操作繁琐。

分派内存时查找安闲区进行分派，而后填写己分派区表，主要操作在安闲区；某个作业履行完后，将该分区变为安闲区，并将其与相邻的安闲区归并，主要操作也在安闲区。

因而可知，内存的分派和回收主假如对安闲区的操作。

这样为了便于对内存空间的分派和回收，就成立两张分区表记录内存使用状况，一张表格记录作业占用分区的“己分分区表”；一张是记录安闲区的“安闲区表”。

这两张表的实现方法一般有两种：一种是链表形式，一种是次序表形式。

在实验中，采纳次序表形式，用数组模拟。

因为次序表的长度一定提早固定，所以不论是“已分分区表”仍是“安闲区表”都一定早先确立长度。

它们的长度一定是系统可能的最大项数。

“已分分区表”的构造定义#define n 10 // 假设系统同意的最大作业数目为nstruct{ float address; // 已分分区开端地点float length; // 已分分区长度、单位为字节int flag;// 已分分区表登记栏标记，“ 0表”示空栏目，实验中只支持一个字符的作业名}used_table[n]; // 已分分区表“安闲区表”的构造定义#define m 10 // 假设系统同意的安闲区最大为mstruct{ float address; // 安闲区开端地点float length; // 安闲区长度、单位为字节int flag; // 安闲区表登记栏标记，“ 0表”示空栏目，“ 1表”示未分派}used_table[n]; // 安闲区表第二，在设计的数据表格基础上设计内存分派。

合肥学院计算机科学与技术系实验报告2009～2010学年第一学期课程操作系统原理实验名称模拟实现一个简单的固定（可变）分区存储管理系统学生姓名朱海燕、汪小白、秦月、程美玲专业班级07计本（1）班指导教师屠菁2009年12月1．实验目的通过本次课程设计，掌握了如何进行内存的分区管理，强化了对首次适应分配算法和分区回收算法的理解。

2．实验内容（1）建立相关的数据结构，作业控制块、已分配分区及未分配分区（2）实现一个分区分配算法，如最先适应算法、最优或最坏适应分配算法（3）实现一个分区回收算法（4）给定一个作业/进程，选择一个分配或回收算法，实现分区存储的模拟管理3．实验步骤首先，初始化函数initial（）将分区表初始化并创建空闲分区列表，空闲区第一块的长度是30，以后的每个块长度比前一个的长度长20。

frees[0].length=30第二块的长度比第一块长20，第三块比第二块长30，以此类推。

frees[i].length=frees[i-1].length+20;下一块空闲区的首地址是上一块空闲区的首地址与上一块空闲区长度的和。

frees[i].front=frees[i-1].front+frees[i-1].length;分配区的首地址和长度都初始化为零occupys[i].front=0;occupys[i].length=0;显示函数show（）是显示当前的空闲分区表和当前的已分配表的具体类容，分区的有起始地址、长度以及状态，利用for语句循环输出。

有一定的格式，使得输出比较美观好看。

assign（）函数是运用首次适应分配算法进行分区，从链首开始顺序查找，直至找到一个大小能满足要求的空闲分区为止；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。

若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。

这个算法倾向于优先利用内存中低址部分被的空闲分区，从而保留了高址部分的的大空闲区。

实验、可变分区存储管理系统模拟——最先适应分配算法1. 实验⽬的可变分区分配是⼀种重要的存储管理思想，⽬前流⾏的操作系统采⽤的分段存储管理的基本思想就源⾃该⽅法。

本实验的⽬的是通过编程来模拟⼀个简单的可变分区分配存储管理系统，利⽤最先适应分配算法实现。

经过实验者亲⾃动⼿编写管理程序，可以进⼀步加深对可变分区分配存储管理⽅案设计思想的理解。

2. 实验原理固定分区分配按操作系统初始化时划定的分区⽅案为作业分配内存，由于各分区的位置和⼤⼩固定，因此作业所需的内存⼤⼩通常⼩于分到的实际内存的⼤⼩，造成存储空间的浪费。

可变分区分配对此作了改进，它总是根据作业的实际需要分配刚好够⽤的连续存储空间，保证分配给作业的存储空间都是有⽤的，避免了零头的产⽣。

（1）可变分区中的数据结构建⽴描述作业的数据结构作业控制块，⾄少应包括：作业名称作业需要执⾏时间作业的内存需求作业调⼊主存时间作业执⾏结束时间作业所在分区的起始地址建⽴描述内存已分配分区的数据结构；建⽴描述内存未分配的空闲分区的数据结构；空闲分区和已分配分区的信息可以使⽤分区表来描述。

系统中所有空闲分区构成分区表，所有已分配分区构成分配分区表。

出于效率的考虑，也可使⽤分区链来记录分区信息。

分区链是⼀种双向链表，链表的每个结点描述⼀个分区的信息。

系统中所有空闲分区构成空闲分区链，所有已分配分区构成分配分区链。

分配和回收分区时，需要在这两个链表中进⾏结点的查找和插⼊、删除与修改操作。

为改进算法的执⾏效率，可以将分区链按特定的顺序排序。

分区链结点的数据结构为：Struct Section {Section *pPre; //前向指针，指向链表的前⼀个结点int nSart； //分区的起始地址int nSize； //分区的尺⼨Section *pSuf； //后向指针，指向链表的后⼀个结点}；可变分区分配算法——最先适应分配算法最先适应分配算法要求空闲分区按地址递增的顺序排列，在进⾏内存分配时，从低地址部分向⾼地址部分查找，直到找到⼀个能满⾜要求的空闲分区为⽌。

实验3 内存管理一、实验内容选择一种算法在可变分区管理方式下对内存进行管理 二、实验目的掌握可变分区内存管理方式，能熟练运用内存管理的各种算法对内存进行分配和回收。

三、实验题目在可变分区管理方式下采用最先适应算法实现主存分配与回收 [提示]：可变分区方式是按作业需要的主存空间大小来分割分区的。

当要装入一个作业时，根据作业需要的主存量查看是否有足够的空闲空间，若有，则按需要量分割一个分区分配给该作业；若无，则作业不能装入。

随着作业的装入、撤离，主为了说明哪些区是空闲的，可以用来装入新作业，必须要有一张空闲区说明表，格式如下：第一栏 第二栏其中，起址——指出一个空闲区的主存起始地址。

长度——指出从起始地址开始的一个连续空闲的长度。

状态——有两种状态，一种是“未分配”状态，指出对应的由起址指出的某个长度的区域是空闲区；另一种是“空表目”状态，表示表中对应的登记项目是空白（无效），可用来登记新的空闲区（例如，作业撤离后，它所占的区域就成了空闲区，应找一个“空表目”栏登记归还区的起址和长度且修改状态）。

由于分区的个数不定，所以空闲区说明表中应有适量的状态为“空表目”的登记栏目，否则造成表格“溢出”无法登记。

上述的这张说明表的登记情况是按提示（1）中的例所装入的三个作业占用的主存区域后填写的。

(2) 当有一个新作业要求装入主存时，必须查空闲区说明表，从中找出一个足够大的空闲区。

有时找到的空闲区可能大于作业需要量，这时应把原来的空闲区变成两部分：一部分分给作业占用；另一部分又成为一个较小的空闲区。

为了尽量减少由于分割造成的空闲区，而尽量保存高地址部分有较大的连续空闲区域，以利于大型作业的装入。

为此，在空闲区说明表中，把每个空闲区按其地址顺序登记，即每个后继的空闲区其起始地址总是比前者大。

为了方便查找还可使表格“紧缩”，总是让“空表目”栏集中在表格的后部。

(3) 采用最先适应算法（顺序分配算法）分配主存空间。

编写程序模拟实现内存的动态分区法存储管理。

内存空闲区使用自由链管理，采用最坏适应算法从自由链中寻找空闲区进行分配，内存回收时要与相邻空闲区的合并。

初始状态信息：假定系统的内存共640K，初始状态为操作系统本身占用64K。

将要申请内存的作业信息（存储在document/job.txt文件中），当前时间是0。

输入：用户打开document/job.txt文件，输入作业信息。

处理：模拟时间逐歩增加，每次加1.采用先来先服务算法调度作业，模拟作业运行，用最坏适应算法进行内存的分配。

且进行内存的回收，注意与空闲分区的合并。

直到所以作业运行完成程序结束。

输出：把当前时间为0，为1，为2......的内存分配状况和作业信息写入文件document/information.txt。

设计思路4.1 结点定义//空闲区结点描述typedef struct FreeNode{int length; // 分区长度int address; // 分区起始地址}FreeNode,*PFreeNode;//空闲区自由链表的描述typedef struct FreeLink{FreeNode freeNode;struct FreeLink * next;}FreeLink,*PFreeLink;//内存占用区链表描述typedef struct BusyNode{char name[20];//标明此块内存被哪个进程所占用int length; // 分区长度int address; // 分区起始地址}BusyNode,*PBusyNode;//内存占用区忙碌链表的描述typedef struct BusyLink{BusyNode busyNode;struct BusyLink * next;}BusyLink,*PBusyLink;//作业控制块的结点描述typedef struct JCBNode{char name[20]; //作业名称int length; //作业申请的内存大小int start_time; //作业申请内存的时间，即到达后备作业队列的时间int use_time; //作业占用内存的时间，随着该作业的运行逐渐减小，int state; //作业内存分配描述：//0表示未申请内存，此时作业在后备队列//1表示申请内存成功，作业进入就绪队列//2表示申请内存失败,此时作业插入到后备队列队尾//3表示该作业占用cpu，正在运行//4表示作业运行完成，释放占用的内存}JCBNode,*PJCBNode;//作业队列的描述,用带头结点的循环链表实现typedef struct JCBQueue{JCBNode jcbNode;struct JCBQueue* next;}JCBQueue,*PJCBQueue;4.2 全局变量定义//全局变量#define ALL_MEMORY 640 //系统总内存#define OS_MEMORY 64 //操作系统占用的内存#define SIZE 2 //门限值PFreeLink freeLink; //空闲区自由链表PBusyLink busyLink; //内存占用区链表PJCBQueue jcbQueue; //外存中待分配内存的作业队列PJCBQueue readyQueue; //已分配内存的就绪队列PJCBQueue finishQueue; //已完成的作业队列PJCBNode currentJCB; //当前正在执行的进程(作业)int current_time; //当前时间4.3 算法流程图（已上传，在此没贴出）1.程序总算法流程图如下：此流程图描述了作业从外存进入内存，再到进程完毕的过程。

/*（二）可变分区存储管理方案中的内存分配可变分区调度算法有:最先适应分配算法,最优适应分配算法,最坏适应算法用户提出内存空间的申请；系统根据申请者的要求，按照一定的分配策略分析内存空间的使用情况，找出能满足请求的空闲区，分给申请者；当程序执行完毕或主动归还内存资源时，系统要收回它所占用的内存空间或它归还的部分内存空间。

1．程序运行时首先接收输入：空闲区数据文件，包括若干行，每行有两个数据项：起始地址、长度（均为整数），各数据项以space隔开。

2．建立空闲区表并在屏幕上显示输出空闲区表内容，空闲区表中记录了内存中可供分配的空闲区的始址和长度，用标志位指出该分区是否是未分配的空闲区。

3．从用户界面根据用户提示接收一个内存申请，格式为：作业名、申请空间的大小。

4．按照最差（最坏）适配算法选择一个空闲区，分割并分配，修改相应的数据结构（空闲区表），填写内存已分配区表（起始地址、长度、标志位），其中标志位的一个作用是指出该区域分配给哪个作业。

5．重复3、4，直到输入为特殊字符（0）。

6．在屏幕上显示输出新的空闲区表和已分配区表的内容。

本程序包括:FIFO,最优适应分配算法,最坏适应算法input file:freememory.txtdata:10 1530 550 2080 12120 25160 18200 8VC++调试通过*/#include <stdio.h>#include <string.h>#include <iostream.h>#include <iomanip.h>const int MAXJOB=100;//定义表最大记录数typedef struct node{int start;int length;char tag[20];}job;job frees[MAXJOB];//定义空闲区表int free_quantiry;//空闲区域的个数job occupys[MAXJOB];//定义已分配区表int occupy_quanity;//初始化函数void initial(){int i;for (i=0;i<MAXJOB;i++){frees[i].start=-1;frees[i].length=0;strcpy(frees[i].tag,"free");occupys[i].start=-1;occupys[i].length=0;strcpy(occupys[i].tag,"");}free_quantiry=0;occupy_quanity=0;}//读数据函数int readData(){FILE *fp;char fname[20];cout<<"请输入初始空闲表文件名:"<<endl;cin>>fname;if ((fp=fopen(fname,"r"))==NULL){cout<<"错误，文件打不开，请检查文件名"<<endl;}else{while(!feof(fp)){fscanf(fp,"%d %d",&frees[free_quantiry].start,&frees[free_quantiry].length);free_quantiry++;}return 1;}return 0;}//sortvoid sort()//按空闲区起始地址排序{int i,j,p;for (i=0;i<free_quantiry;i++){p=i;for (j=i+1;j<free_quantiry;j++){if (frees[j].start<frees[p].start){p=j;}}if (p!=i){frees[free_quantiry]=frees[i];frees[i]=frees[p];frees[p]=frees[free_quantiry];}}}//显示函数void view(){int i;cout<<endl<<"----------------------------------------------------------"<<endl;cout<<"当前空闲表:"<<endl;cout<<"起始地址长度状态"<<endl;for(i=0;i<free_quantiry;i++){cout.setf(2);cout.width(12);cout<<frees[i].start;cout.width(10);cout<<frees[i].length;cout.width(8);cout<<frees[i].tag<<endl;}cout<<endl<<"-----------------------------------------------"<<endl;cout<<"当前已分配表:"<<endl;cout<<"起始地址长度占用作业名"<<endl;for (i=0;i<occupy_quanity;i++){cout.setf(2);cout.width(12);cout<<occupys[i].start;cout.width(10);cout<<occupys[i].length;cout.width(8);cout<<occupys[i].tag<<endl;}}//最优适应分配算法void best_fit(){char job_name[20];int job_length;int i,j,flag,t;cout<<"请输入新申请内存空间的作业名和空间大小:"<<endl;cin>>job_name;cin>>job_length;flag=0;for (i=0;i<free_quantiry;i++){if (frees[i].length>=job_length){flag=1;}}if (flag==0){cout<<"Sorry,当前没有能满足你申请长度的空闲内存,请稍候再试"<<endl; }else{t=0;i=0;while(t==0){if (frees[i].length>=job_length){t=1;}i++;}i--;for (j=0;j<free_quantiry;j++){if ((frees[j].length>=job_length)&&frees[j].length<frees[i].length){i=j;}}occupys[occupy_quanity].start=frees[i].start;strcpy(occupys[occupy_quanity].tag,job_name);occupys[occupy_quanity].length=job_length;occupy_quanity++;if (frees[i].length>job_length){frees[i].start+=job_length;frees[i].length-=job_length;}else{for (j=i;j<free_quantiry-1;j++){frees[j]=frees[j+1];}free_quantiry--;cout<<"内存分配成功"<<endl;}}}//撤销作业void finished(){char job_name[20];int i,j,flag,p=0;int start;int length;cout<<"请输入要撤销的作业名:"<<endl;cin>>job_name;flag=-1;for (i=0;i<occupy_quanity;i++){if (!strcmp(occupys[i].tag,job_name)){flag=i;start=occupys[i].start;length=occupys[i].length;}}if (flag==-1){cout<<"没有这个作业"<<endl;}else{for (i=0;i<free_quantiry;i++){if ((frees[i].start+frees[i].length)==start){if (((i+1)<free_quantiry)&&(frees[i+1].start==start+length)){frees[i].length=frees[i].length+frees[i+1].length;for (j=i+1;j<free_quantiry;j++){frees[j]=frees[j+1];}free_quantiry--;p=1;}else{frees[i].length+=length;p=1;}}if (frees[i].start==(start+length)){frees[i].start=start;frees[i].length+=length;p=1;}}if (p==0){frees[free_quantiry].start=start;frees[free_quantiry].length=length;free_quantiry++;}for (i=flag;i<occupy_quanity;i++){occupys[i]=occupys[i+1];}occupy_quanity--;}}//显示版权信息函数void version(){cout<<endl<<endl;cout<<" ┏━━━━━━━━━━━━━━━━━━━━━━━┓"<<endl;cout<<" ┃可变分区存储管理方案中的内存分配┃"<<endl;cout<<" ┠───────────────────────┨"<<endl;cout<<" ┃siqingyang ┃"<<endl;cout<<" ┃version 2011 build 0520┃"<<endl;cout<<" ┗━━━━━━━━━━━━━━━━━━━━━━━┛"<<endl;cout<<endl<<endl;}void main(){int flag=0;int t=1;int chioce=0;version();initial();flag=readData();view();while(flag==1){sort();cout<<endl<<endl<<"================================================== ======="<<endl;cout<<" 可变分区存储管理模拟系统"<<endl;cout<<"========================================================="<<e ndl;cout<<" 1.best fit申请空间2.撤消作业0.退出"<<endl;cout<<"请选择:";cin>>chioce;switch(chioce){case 1:best_fit();view();break;case 2:finished();view();break;case 0:flag=0;break;default:cout<<"选择错误!"<<endl;}}}。

存储管理上机作业——最佳适应算法以最佳适应为例，给出可变式分区的分配回收算法。

源程序如下：#include<stdio.h>#define N 5struct freearea{int startaddress;int size;int state;}freeblock[N]={{20,20,1},{80,30,1},{160,10,1},{200,40,0},{250,50,1}};int allocate(int applyarea){int i,tag=0;for(i=0;i<N;i++){if(freeblock[i].size>applyarea&&freeblock[i].state==1){freeblock[i].startaddress=freeblock[i].startaddress+applyarea;freeblock[i].size=freeblock[i].size-applyarea;tag=1;//有满足条件的分区时，tag置1return freeblock[i].startaddress-applyarea;}else if(freeblock[i].size==applyarea&&freeblock[i].state==1){freeblock[i].state=0;tag=1;//有满足条件的分区时，tag置1return freeblock[i].startaddress;}}if(tag==0)return -1;}void set_free(){int i,j,s,l,tag1=0,tag2=0,tag3=0;printf("please input the start address you want to set free:\n");scanf("%d",&s);printf("please input the size:\n");scanf("%d",&l);for(i=0;i<N;i++){if(freeblock[i].startaddress+freeblock[i].size==s&&freeblock[i].state==1)//释放区与某一空闲块的高地址相邻接{l=freeblock[i].size+l;tag1=1;//释放区与某一空闲块的高地址相邻接for(j=0;j<N;j++)//内层循环用于检测释放区是否同时与两个空闲块相邻接{if(freeblock[j].startaddress==freeblock[i].startaddress+l&&freeblock[j].state==1) {freeblock[j].size=l+freeblock[j].size;freeblock[j].startaddress=freeblock[i].startaddress;freeblock[i].state=0;tag2=1;//标记同时与两个空闲块相接break;}}if(tag2==0){freeblock[i].startaddress=s;freeblock[i].size=l;break;}}}//forif(tag1==0)//不与空闲块的高地址相接{for(i=0;i<N;i++)//检测是否与某空闲块的低地址相接{if(s+l==freeblock[i].startaddress&&freeblock[i].state==1){freeblock[i].startaddress=s;freeblock[i].size=freeblock[i].size+l;tag3=1;break;}if(tag3==0)//不与任何空闲块相接{for(j=0;j<N;j++){if(freeblock[j].state==0){freeblock[j].startaddress=s;freeblock[j].size=l;freeblock[j].state=1;break;}}}}}}void adjust(){int i,j;struct freearea temp;for(i=0;i<N;i++){for(j=i;j<N;j++){if(freeblock[i].size>freeblock[j].size){temp.size=freeblock[i].size;temp.startaddress=freeblock[i].startaddress;temp.state=freeblock[i].state;freeblock[i].size=freeblock[j].size;freeblock[i].startaddress=freeblock[j].startaddress; freeblock[i].state=freeblock[j].state;freeblock[j].size=temp.size;freeblock[j].startaddress=temp.startaddress;freeblock[j].state=temp.state;}}}for(i=0;i<N;i++){if(freeblock[i].state==0&&freeblock[i+1].state==1){temp.size=freeblock[i].size;temp.startaddress=freeblock[i].startaddress;temp.state=freeblock[i].state;freeblock[i].size=freeblock[i+1].size;freeblock[i].startaddress=freeblock[i+1].startaddress;freeblock[i].state=freeblock[i+1].state;freeblock[i+1].size=temp.size;freeblock[i+1].startaddress=temp.startaddress;freeblock[i+1].state=temp.state;}}}void print(){int i;printf("%5s%15s%13s%12s","block_id","start_address","size","state");printf("\n");for(i=0;i<N;i++)printf("%5d%15d%15d%10d\n",i,freeblock[i].startaddress,freeblock[i].size,freeblock [i].state);}void main(){int start;int choice;int applyarea;while(1){printf("********************************\n");printf("1:I want to request for memory.\n");printf("2:I want to set free some memory.\n");printf("3:exit.\n");printf("Please input your choice:\n");printf("********************************\n");scanf("%d",&choice);if(choice==1){printf("At first the free memory table is:\n");print();printf("Please input the request memory size:\n");scanf("%d",&applyarea);adjust();start=allocate(applyarea);if(start==-1){printf("There is not enough memory,please wait.\n");}else{printf("Your request is being submitted.job size is :%d\n",applyarea);printf("job is running.job's start address is:%d\n",start);printf("After allocation,the memory table is:\n");adjust();print();}}if(choice==2){set_free();printf("After setfree,the memory table is:\n");adjust();print();}if(choice==3)break;}}进入程序主界面如下：测试用例如下：当输入选择1时，进入内存请求界面，并且显示现在的空闲块分布情况如下（state为零标记该空闲内存块不可用）：输入请求的内存空间大小（例如大小为5）：由最佳适应算法把起始地址为160，大小为5的内存分配给请求进程，分配后的内存表如上图，同时返回程序的主界面；输入选择为2时，提示输入将要释放区间的起始地址与大小，举例输入将要释放的区间起始地址为110，大小为20，将释放的空闲区与已有的空闲区合并，内存分配表如下图：继续输入选择为2，输入要释放的区间起始地址为180，大小为15，释放之后的内存分配表如下图：输入选择为2，释放区间起始地址为60，大小为20，释放之后的内存分配表如下：此时输入选择为1，请求的内存空间大小为10，分配后的内存如分配表如下：此时输入3，程序结束退出。