存储管理算法设计之【内存空间的分配和回收】
设计⼀内存空间的分配和回收
【实验⽬的】
通过本实验，帮助学⽣理解存储管理的功能，掌握动态异长分区的存储分配与回收算法。
【实验内容】
模拟动态异长分区的分配算法、回收算法。
【实验要求】
常⽤的动态异长分区的分配算法有：最先适应算法、最佳适应算法和最坏适应算法。要求选择任意⼀种算法，设计相应的数据结构，模拟内存空间的分配和回收。实验报告中给出程序中使⽤的数据结构及流程图。
【实验原理】
⾸次适应算法（First Fit）
该算法从空闲分区链⾸开始查找，直⾄找到⼀个能满⾜其⼤⼩要求的空闲分区为⽌。然后再按照作业的⼤⼩，从该分区中划出⼀块内存分配给请求者，余下的空闲分区仍留在空闲分区链中。空闲分区以地址递增次序排列。
缺点：低地址部分不断被划分，留下许多难以利⽤、很⼩的空闲区，⽽每次查找⼜都从低地址部分开始，会增加查找的开销。
优点：开销较⼩，回收分区⼀般⽆需对空闲分区队列重新排序。该算法倾向于使⽤内存中低地址部分的空闲区，在⾼地址部分的空闲区很少被利⽤，从⽽保留了⾼地址部分的⼤空闲区。显然为以后到达的⼤作业分配⼤的内存空间创造了条件。
最佳适应算法（Best Fit）
该算法总是把既能满⾜要求，⼜是最⼩的空闲分区分配给作业。为了加速查找，该算法要求将所有的空闲区按容量递增顺序排成⼀个空⽩链。这样每次找到的第⼀个满⾜要求的空闲区，必然是最优的。
缺点：因为每次分配后剩余的空间⼀定是最⼩的，所以内存中留下许多难以利⽤的⼩的空闲区（外部碎⽚）；开销⼤，回收后可能要重新排序。
优点：每次分配给⽂件的都是最合适该⽂件⼤⼩的分区。有更多⼤分区被保留。
最坏适应算法（Worst Fit）
空闲区按容量递减次序排列，每次优先分配最⼤连续空闲区。
缺点：较⼤空闲分区被迅速⽤完，绝⼤多数时候都会造成资源的严重浪费甚⾄是完全⽆法实现分配；开销⼤，回收后可能要重新排序。
优点：尽可能地利⽤存储器中⼤的空闲区，减少了难以利⽤的⼩碎⽚。
【数据结构设计】
（1）数据结构设计
为了实现存储资源的分配和回收，操作系统需要记录内存资源使⽤情况，即哪些区域尚未分配，哪些区域已经分配以及分配给哪些进程等。为此⼀般需要两个表，⼀个为分配表, 另外⼀个为空闲区域表。前者记录已经分配的区域, 后者记录着所有当前未被进程占⽤的空闲区域，如图1所⽰。
空闲区域⾸英语教师
空闲区域长度
址
……
addr size
rattlesnake……
图1 空闲区域表
显然, 没有记录于表中的区域即为已被进程所占⽤的⾮空闲区域，在实际的操作系统中，这些区域登记在进程的PCB中。⽽PCB中除了关于内存资源的信息外，还有其它⼤量信息。
由于本实验是对存储管理算法的模拟，所以⽤⼀个线程来代表⼀个进程，⽤线程驻留区域表来描述线程占⽤的内存空间，如图2所⽰。
线程名称驻留区始
址
驻留区
⼤⼩
a010
b2020
………………
图2 线程驻留区表 同时，需要⼀张表来记录各个线程对内存的请求信息，如图3所⽰。
线程名称请求⼤⼩
(KB)
预计驻留时间(
秒)
thread_1204
thread_2105
…
……………
图3 内存申请表
（2）设计并分析测试数据
假设初始内存布局如图4，图中的起始地址以及⼤⼩都以KB来衡量。
由图4可见，初始时共有五个线程驻留在内存，它们是a,b,c,d,e，线程驻留区表如图5；还有五个空闲区，空闲区域表如图6。
假设现在有三个线程提出内存申请，申请情况见图7。经过分析我们得到在每种分配算法下这三个线程所申请到的内存情况。图8是最先适应算法分配情况，图9是最佳适应算法分配情况，图10是最坏适应算法分配情况。
【算法设计】
宏定义：
#define Free 0 //空闲状态
#define Busy 1 //已⽤状态
#define OK 1 //完成
#define ERROR 0 //出错
#define MAX_length 640 //定义最⼤主存信息640KB
六⼤函数:
①status Alloc(int)：内存分配函数。对于选择的⾸次适应算法或者是最佳适应算法判断分配完成状态，说明是否实现分配或者是分配错误。
②status free(int)：内存回收函数。主要涉及合并内存的三种情况：
该空闲块与前⾯的空闲块相连的主存回收，表⽰为：
if (p->prior != block_first && p->prior->data.state == Free)
{
p->prior->data.size += p->data.size;//空间扩充，合并为⼀个
p->prior->next = p->next;//去掉原来被合并的p
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;
}
该空闲块与最后的空闲块相连，表⽰为：
blunt的反义词if (p->next == block_last && p->next->data.state == Free) {
p->data.size += p->next->data.size;
p->next = NULL;
}
③status First_fit(int)：⾸次适应算法，只需要将地址由⼩到⼤排列好，从头指针开始遍历，逐个检验，找到第⼀个空间＞=所申请的空间时，给予分配。 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;
④status Best_fit(int)：对由⼩到⼤的空闲区排列的空闲区，与所申请的内存⼤⼩相⽐，取两者差最⼩的给予分配，插⼊。初始化最⼩空间和最佳位置，⽤ch来记录最⼩位置。
⑤void show()：查看分配。
⑥status Initblock()：开创带头结点的内存空间链表。
2017年2月18日
【程序代码】
#include<iostream>
#include<stdlib.h>
using namespace std;
#define Free 0 //空闲状态
#define Busy 1 //已⽤状态
#define OK 1 //完成
#define ERROR 0 //出错
#define MAX_length 640 //定义最⼤主存信息640KB
typedef int Status;
int flag;//标志位 0为空闲区 1为已分配的⼯作区
reallyint flag;//标志位 0为空闲区 1为已分配的⼯作区
typedef struct FreAarea//定义⼀个空闲区说明表结构
{
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));
decke
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)："<<endl;
cin >> request;
if (request<0 || request == 0)
{
cout << "分配⼤⼩不合适，请重试！" << endl;inrtinto
return ERROR;
英语面试对话}
if (ch == 2) //选择最佳适应算法
{
if (Best_fit(request) == OK) cout << "分配成功！" << endl; el cout << "内存不⾜，分配失败！" << endl;
return OK;
}
if (ch == 3) //选择最差适应算法
{
if (Worst_fit(request) == OK) cout << "分配成功！" << endl; el cout << "内存不⾜，分配失败！" << endl;
return OK;
秋天如何保养皮肤
}
el //默认⾸次适应算法
{
if (First_fit(request) == OK) cout << "分配成功！" << endl;
