可变分区分配与回收——采用最坏算法.doc

哈尔滨理工大学
课　程　设　计
（操作系统）

题　　目：　可变分区分配与回收—采用最坏算法

班　　级： 计算机科学与技术学院 计算机系　10-8班
姓　　名：　　　　　张兢 1004010813
指导教师：　　　　　　　高雪瑶
系主任： 林克正

2013年03月01日

哈尔滨理工大学课程设计报告
一、 课程设计目的
1、背景
主存是CPU可直接访问的信息空间，合理而有效的使用贮存将在很大程度上影响整个计算机系统的性能。
本课题要求模拟实现分区式主存管理机制。模拟实现各种分区管理方法以及相应的主存分配以及回收算法。
2、目的
通过该课题进一步加深对可变分区存储机制的理解。加深对存储器动态分区分配算法的认识。掌握“首次适应算法”、“下次适应算法”、“最佳适应算法发”、“最坏适应算法”的内存分配过程。掌握内存的回收策略。
二、 课题任务描述
1、设计可用的内存空闲空间，并能动态输入用户作业所需的内存大小。
2、编程模拟各种分配算法的实施过程，允许自行选择如“首次适应算法”、“下次适应算法”、“最佳适应算法发”、“最坏适应算法”等常用算法，要求实现不少于三种算法。
3、实现内存的回收。要求考虑回收时的内存合并问题。
三、 课题研发相关知识 （包含所用库函数的介绍）
1、 首次适应算法（first fit）
FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直至找到一个大小能男足要求的空闲分区位置；然后再按照作业的大小，从该分区中划出一块内存空间分配给请求者，余下的空闲分区仍留在空闲链中。若从链首直至链尾都不能找到一个能满足要求的分区，则此次内存分配失败，返回。但是，低址部分不断被划分，会留下许多难以利用的很小的空闲分区。
2、 最佳适应算法（best fit）
所谓“最佳”是指每次为作业分配内存时，总是把能满足要求、又是最小的空闲分区分配给作业，避免“大材小用”。为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成一空闲分区链。这样，第一次找到的能满足要求的空闲区，必然是最佳的。这样，在存储器中会留下许多难以利用的小空闲区。
3、 最坏适应算法（worst fit）
要扫描整个空闲分区表或链表，总是挑选一个最大的空闲区分割给作业使用，其优点是可使剩下的空闲区不至于太小，产生碎片的几率最小，对中小作业有力，查找效率很高。但是它会使存储器中缺乏大的空闲分区。
4、 回收内存
当进程运行完毕释放内存时，系统根据会收取的首址，从空闲区链中找到相应的插入点，并考虑回收区前后是否有空闲分区，如果有，则把两个分区合并成一个大的空闲分区。
5、库函数的介绍
1）stdio 就是指 “standard buffered input&output" 意思就是说带缓冲的标准输入输出！ 所以了，用到标准输入输出函数时，就要调用这个头文件！
2）Stdlib.h即standard library 标准库文件。Stdlib头文件里包含了C,C++语言的最常用的系统函数。Stdlib.h里面定义了五中类型，一些宏和通用工具函数。 类型例如：size_t ,wchar_t, div_t, ldiv_t,lldiv_t; 宏例如：EXIT_FALIRE,EXIT_SUCCESS,RAND_MAX和MB_CUR_MAX。
以下是一些常用的函数：dec 置基数为10 相当于"%d"；hex 置基数为16 相当于"%X"；oct 置基数为8 相当于"%o"；setw(n) 设域宽为n个字符
四、 课题设计：总体结构、所使用的数据结构、主要功能的流程图、程序的技术路线
1、 总体结构
本系统采用了首次适应算法、最佳适应算法和最坏适应算法模拟存储器动态分区。系统利用其中某种分配算法，从空闲分区链中找到满足请求内存大小的分区并分配内存给作业。假设总的内存大小为size，作业请求的内存大小为request,内存碎片最小为f。当request>size时，内存溢出，出现系统错误；当request<=size时，在内存中根据上述算法寻找最佳的内存分区分配给作业。寻找到合适的内存分区之后，如果size-request<=f,将此分区上的内存全部分配给作业；如果size-request>f，就在此分区上分割request大小的内存给作业，剩余内存继续留在当前的分区中。当进程运行完毕，系统找到该进程并释放其内存，根据所释放内存的位置对内存进行合并。

系统流程图：如图1

Y
N
N
Y
N
Y
开始
输入option
选择分配算法
option=3??
根据option的值选择相应算法，输入ope
ope=0?
ope=1?

ope=2?

ope=3?

N
N
退出
分配内存
回收内存
返回上一级
输入错误
Y
Y
图1

系统框架图：如图2
存储器动态分区分配模拟系统
首次适应算法
最佳适应算法
最坏适应算法
退出系统
分配内存
回收内存
返回上一级菜单
图2

2、 数据结构
（1）定义的全局变量：
#define SIZE 1000 // 内存初始大小
#define MINSIZE 5 // 碎片最小值
enum STATE { Free, Busy }//枚举类型，记录分区是否空闲的状态量
（2）定义的结构体：struct subAreaNode。记录分区的主要数据。
（3）函数
1）void intSubArea()：分配初始分区内存。
2）int firstFit(int taskId, int size)：首次适应算法实现函数，taskId为作业名，size为作业申请的内存大小。
3）int bestFit(int taskId, int size)：最佳适应算法实现函数，taskId为作业名，size为作业申请的内存大小。
4）int worstFit(int taskId, int size)：最坏适应算法实现函数，taskId为作业名，size为作业申请的内存大小。
5）int freeSubArea(int taskId)：内存回收函数，该函数主要用于实现内存的回收，根据回收内存的位置对分区进行合并操作。其中taskId为所需回收内存的作业号。
6）void showSubArea()：显示空闲分区链情况。包括起始地址 ，空间大小 。工作状态 。作业号。
7）int main()：主函数，主要用于显示操作界面，调用各个子函数等功能。

3、主要功能的流程图
（1）首次适应算法First_fit(int,int); 流程图（图3）
图3
N
Y
Y
开始
p = subHead.nxt，从链表的第一个节点开始寻找
p是否为空
p是否空闲，p->size大小是否满足作业需求
p->size与作业需求大小之差是否小于等于内存碎片
p中内存大小全部分配给作业
N
执行完毕
结束
Y
分割分区p，并把剩余内存存入新的结点
N

（2）最佳适应算法Best_fit(int,int); 流程图（图4）
图4
Y
Y
N
开始
subAreaNode*p= subHead.nxt
P是否空
P是否满足最佳分配空间
Y
N
p=p->nxt
tar=p
tar为空？
N
tar->size-size是否小于等于内存碎片
tar全部分配给作业
结束
Y
切割tar，分配给作业，并把剩余内存重新链入链表
N

（3）最坏适应算法Worst_fit(int,int); 流程图（图5）

N
Y
Y
N
开始
subAreaNode*p= subHead.nxt
mm=1
P是否空且mm==1
P是否满足最佳分配空间
Y
N
p=p->nxt
tar=p,mm=0
tar为空？
tar->size-size是否小于等于内存碎片
tar全部分配给作业
结束
Y
切割tar，分配给作业，并把剩余内存重新链入链表
N
遍历空闲链表，p=subHead.nxt寻找最大的空闲分区，tar=p;
图5
Y
Y

4. 程序的技术路线
本程序采用C语言编写，在windows下的Visual C++中编译，模拟可变分区存储管理方式的内存分配与回收。假定系统的最大内存空间为1000kb，判断是否划分空闲区的最小限值为MINSIZE=5。初始化用户可占用内存区的首地址为0，大小为0B。定义一个结构体及其对象subHead实现内存的分配回收及分配表和空闲表的登记。用最佳分配算法实现动态分配时，调用int bestFit(int taskId, int size)内存分配函数，设定循环条件查找最佳空闲分区，根据找到的空闲区大小和作业大小判断是整个分配给作业还是切割空闲区后再分配给作业，并在“内存分配表”和“空闲分区表”中作登记。调用int freeSubArea(int taskId)函数实现内存的回收。顺序循环“内存分配表”找到要回收的作业，设置标志位flag，当flag=1时表示回收成功。回收内存时需考虑内存的4种合并方式，即合并上下分区、合并上分区、合并下分区、上下分区都不合并。
五、 带有详细注解的源程序
#include<stdio.h>
#include<time.h>
#include<stdlib.h>
#define SIZE 1000 // 内存初始大小
#define MINSIZE 5 // 碎片最小值
enum STATE { Free, Busy };
static int ss=0,ee=0;
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 worstFit(int taskId, int size)
{
subAreaNode *tar = NULL;
int tarSize;
int mm=1;
subAreaNode *p = subHead.nxt;
while(p != NULL&&mm==1)
{ // 寻找最佳空闲区间
if(p->state == Free && p->size >= size) {
tar = p;
tarSize = p->size;
mm=0;
}
else
p = p->nxt;
}
p=subHead.nxt;
while(p != NULL)
{
// 寻找最大空闲区间
if(p->state == Free && p->size >= tarSize && p->size>=size) {
tar = p;
tarSize = p->size;//遍历找到最大空闲区间
p=p->nxt;
}
else
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;
}
}
/* int start(int task)
{
clock_t s;
s=(int)clock();
return s;
}
int end(int task)
{
clock_t s;
s=(int)clock();
return s;
}*/
// 显示空闲分区链情况
void showSubArea()
{
printf("*********************************************\n");
printf("** 当前的内存分配情况如下： **\n");
printf("*********************************************\n");
printf("** 起始地址 | 空间大小 | 工作状态 | 作业号 **\n");
subAreaNode *p = subHead.nxt;
while(p != NULL)
{
printf("**-----------------------------------------**\n");
printf("**");
printf("%5d k |", p->addr);
printf("%5d k |", p->size);
printf(" %5s |", p->state == Free ? "Free" : "Busy");
if(p->taskId > 0) {
printf("%5d ", p->taskId);
} else {
printf(" ");
}
printf("**\n");
p = p->nxt;
}
printf("*********************************************\n");
}
int main()
{
int option, ope, taskId, size;
// 初始化空闲分区链
intSubArea();
// 选择分配算法
l1: while(1)
{
printf("**********************\n");
printf("请选择要模拟的分配算法:\n0 表示首次适应算法\n1 表示最佳适应算法\n2 表示最坏适应算法\n3 退出\n");
printf("**********************\n");
scanf("%d", &option);
system("cls");
if(option == 0) {
printf("你选择了首次适应算法，下面进行算法的模拟\n");
break;
} else if(option == 1) {
printf("你选择了最佳适应算法，下面进行算法的模拟\n");
break;
} else if(option == 2) {
printf("你选择了最坏适应算法，下面进行算法的模拟\n");
break;
}
else if(option == 3){
exit(0);
}
else {
printf("错误：请输入 0/1\n\n");
}
}
// 模拟动态分区分配算法
while(1)
{
printf("\n");
printf("*********************************************\n");
printf(" 1: 分配内存\n 2: 回收内存\n 3: 返回上一级菜单\n 0: 退出 \n\n");
printf("*********************************************\n");
scanf("%d", &ope);
system("cls");
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 if(option==1){
bestFit(taskId, size);
}
else
worstFit(taskId, size);
// 显示空闲分区链情况
showSubArea();
} else if(ope == 2) {
// 模拟回收内存
printf("请输入要回收的作业号： ");
scanf("%d", &taskId);
freeSubArea(taskId);
// 显示空闲分区链情况
showSubArea();
} else if(ope==3){
goto l1;
}
else {
printf("错误：请输入 0/1/2\n");
}
}
printf("分配算法模拟结束\n");
return 0;
}
六、 运行与测试（调试通过的程序，主要测试用例和运行界面截图）
1.测试数据：预设总的内存大小为100k。选择首次适应算法，分别输入作业号及作业的大小（1，200k),(2,200k),(3,155k),(4，445k)，然后回收作业2和作业4,最后退出系统。
2. 运行截图如下：

1. 主界面：图6

图6
2.选择首次适应算法：图7

图7

3.利用首次适应算法分配内存：图8

图8

4. 回收内存：图9

图9

5.退出系统：图10

图10
七、 收获及改进意见
每一次的实践，都会有很大的收获。做这个题目的时候，就针对此题要解决的几个问题反复思考，重新翻开教科书把相关内容特别是算法原理认真细致的看了一遍，设想会遇到的问题。在内存动态分配程序设计中，最佳适应算法比首次要难一些，要加上对分配后该分区是否能最好地利用的判断。再一个问题是回收时候的合并，对地址的修改不是很有把握。着手写程序后，半天才理清回收的内存和上下邻合并的条件与关系，写此处的代码时，逻辑上比较混乱，反复错误反复修改了很多次才调试正确，这也是花了最多时间才得以正确实现的部分。之前大多用的c语言，对结构体，对象等知识淡忘了很多，这一次的实践让我找回了很多学过的知识点，也弥补了很多的不足之处。逻辑思维也得到了锻炼，写代码也不再像初学的时候那么繁琐，自己都能感觉到那一点点的进步，顿时也觉得充实起来。还有一个难点就是为作业找到最佳空闲区，此处是参照了一些资料后，理清了条件，然后用一个while（）两个if（）语句循环嵌套就实现了此功能。实践中也发现自身很多的不足，比如上理论课时认为已经理解