资源描述
*.
实验报告
实验二 动态分区分配与回收算法
一、实验目的
了解动态分区分配方式中使用的数据结构和分配算法，并进一步加深对动态分区存储管理方式及其实现过程的理解。
二、实验原理
算法思想：
1．分区的个数和大小不是固定不变的，而是可变的，随装入的作业动态划分，且不会产生内部碎片。
2.外部碎片：若存储块长度为N，在该系统所采用的调度算法下较长时间内无法选出一道长度不超过该块的进程，则称该块为外部碎片。
3.首次适应算法（FF）:
FF算法要求空闲分区链以地址递增的次序链接。在分配内存时，从链首开始顺序查找，直到找到一个大小能满足要求的空闲分区为止。该算法倾向于优先利用内存中低址部分的空闲分区，从而保留了高址部分的大空闲区，这为以后到达的大作业分配大的内存空间创造了条件。
4.最佳适应算法（BF）：
每次为作业分配内存时，BF总是把能满足要求、又是最小的空闲分区分配给作业，避免大材小用。为了加速寻找，该算法要求将所有的空闲分区按其容量从大到小的顺序形成一空闲分区链，自表头开始查找到第一个满足要求的自由分区分配。该算法保留大的空闲区，但造成许多小的空闲区。
分区分配中的内存回收有四种情况：
(1)回收区与插入点的前一个空闲分区相邻接。
(2)回收区与插入点的后一空闲分区相邻接。
(3)回收区同时与插入点的前、后两个空闲分区邻接。
(4)回收分区既不与前一个分区邻接，也不与后一个分区邻接。
另外，最佳适应算法不需要考虑多个进程，而首次适应算法需要考虑多道程序的大小，所以前两个程序只需要输入一个进程的信息，后者因为考虑多个程序的原因，所以需要输入两个进程的信息。
三、 实验步骤、数据记录及处理
1、 算法流程
抽象数据类型的定义：空闲分区结构体类型和结构体链表
typedef struct freespace
{
int num; //分区号
int size; //分区大小
int address; //分区首地址
status state; //分区状态，FREE和BUSY
};
typedef struct node
{
freespace data;
node *head;
node *next;
}*Linklist;
主程序的流程以及各程序模块之间的层次(调用)关系：主函数中先调用初始化函数，再调用菜单函数引导用户选择操作和相应的算法，用switch多选择结构来判断调用firstAlloc()，bestAlloc()，display()还是recycle()。
程序流程图：
2、 运行结果分析：
首次适应算法：分配结束后的空闲分区大小和起始地址与结果相同。
大小
起始地址
30K
150K
20K
280K
112K
400K
最佳适应算法：分配结束后的空闲分区大小和起始地址与结果相同。
大小
起始地址
30K
400K
42K
470K
90K
210K
西安工业大学实验报告
四、总结与体会
附录：源代码
#include
#include
using namespace std;
#define MAXSIZE 512
enum status { FREE, BUSY };//枚举类型
typedef struct freespace
{
int num; //分区号
int size; //分区大小
int address; //分区首地址
status state; //分区状态，FREE和BUSY
};
typedef struct node
{
freespace data;
node *head;
node *next;
}*Linklist;
Linklist first,last;
void init()
{
first = new node;
last = new node;
first->head = NULL;
first->next = last;
last->head = first;
last->next = NULL;
last->data.address = 0;
last->data.size = MAXSIZE;
last->data.num = 0;
last->data.state = FREE;
}
void display()
{
cout << "****************主内存分配情况****************" << endl;
node *p = first->next;
while (p)
{
cout << "分区号：";
if (p->data.num == 0)
{
cout << "空闲区" << " " << "起始地址：" << p->data.address << " " << "终止地址：" << p->data.address+p->data.size<<
" " << "分区大小：" <<
p->data.size << "KB" << " " << "状态:空闲" << endl;
}
else
{
cout << p->data.num;
cout << " " << "起始地址：" << p->data.address << " " << "终止地址：" << p->data.address + p->data.size << " "
"分区大小：" << p->data.size
<< "KB" << " " << "状态:";
if (p->data.state == FREE)
cout << "空闲" << endl;
else
if (p->data.state == BUSY)
cout << "占用" << endl;
}
p = p->next;
}
cout << "**********************************************" << endl << endl;
}
int firstAlloc()//首次分配
{
int num, size;
cout << "请输入作业号和分配的主存大小KB：" << endl;;
cin >> num >> size;
Linklist list = new node;
list->data.num = num;
list->data.size = size;
list->data.state = BUSY;
node *p = first->next;
while (p)
{
if (p->data.state == FREE&&p->data.size == size)//有大小刚好合适的空闲块
{
p->data.state = BUSY;
p->data.num = num;
display();
return 1;
}
if (p->data.state == FREE&&p->data.size > size)//有大小比他大的空闲块
{
list->head = p->head;
list->next = p;
list->data.address = p->data.address;
p->head->next = list;
p->head = list;
p->data.address = list->data.address + list->data.size;
p->data.size -= size;
display();
return 1;
}
p = p->next;
}
display();
return 0;
}
int bestAlloc()//最佳分配
{
int num, size;
cout << "请输入作业号和分配的主存大小KB：" << endl;;
cin >> num >> size;
int min_space=MAXSIZE;
Linklist list = new node;
list->data.num = num;
list->data.size = size;
list->data.state = BUSY;
node *p = first->next;
node *q = NULL;
while (p)//找到最佳位置
{
if ((p->data.size > size || p->data.size == size)&&p->data.state==FREE)
{
if (p->data.size - size < min_space)
{
q = p;
min_space = p->data.size - size;
}
}
p = p->next;
}
if (q == NULL)
{
return 0;
}
else
{
if (min_space == 0)
{
q->data.num = num;
q->data.state = BUSY;
display();
return 1;
}
else
{
list->head = q -> head;
list->next = q;
list->data.address = q->data.address;
q->head->next = list;
q->head = list;
q->data.address += size;
q->data.size -= size;
display();
return 1;
}
}
}
int recycle()//碎片整理
{
int num;
cout << "请输入你要回收内存的作业号：" << endl;
cin >> num;
node *p = first;
while (p)
{
if (p->data.num == num)
{
p->data.state = FREE;
p->data.num = 0;
if (p->head->data.state == FREE)//与前一块空闲区相邻，则合并
{
p->head->data.size += p->data.size;
p->head->next = p->next;
p->next->head = p->head;
}
if (p->next->data.state == FREE)//与后一块空闲区相邻，则合并
{
p->data.size += p->next->data.size;
p->next->next->head = p;
p->next = p->next->next;
}
break;
}
p = p->next;
}
display();
return 1;
}
void menu()
{
cout << "********************内存分配系统********************" << endl;
cout << " 1.首次适应算法分配内存 " << endl;
cout << " 2.最佳适应算法分配内存 " << endl;
cout << " 3.查看主存分配情况 " << endl;
cout << " 4.回收主存 " << endl;
cout << "请选择：" << endl;
}
void main()
{
init();
int choose;
menu();
while (1)
{
//menu();
cin >> choose;
switch (choose)
{
case 1:
firstAlloc();
break;
case 2:
bestAlloc();
break;
case 3:
display();
break;
case 4:
recycle();
break;
default :
cout << "输入错误！" << endl;
break;
}
}
}
展开阅读全文
相关搜索