1. 实验目的

可变分区分配是一种重要的存储管理思想，目前流行的操作系统采用的分段存储管理的基本思想就源自该方法。本实验的目的是通过编程来模拟一个简单的可变分区分配存储管理系统，利用最先适应分配算法实现。经过实验者亲自动手编写管理程序，可以进一步加深对可变分区分配存储管理方案设计思想的理解。

2. 实验原理

固定分区分配按操作系统初始化时划定的分区方案为作业分配内存，由于各分区的位置和大小固定，因此作业所需的内存大小通常小于分到的实际内存的大小，造成存储空间的浪费。可变分区分配对此作了改进，它总是根据作业的实际需要分配刚好够用的连续存储空间，保证分配给作业的存储空间都是有用的，避免了零头的产生。

（1）   可变分区中的数据结构

建立描述作业的数据结构作业控制块，至少应包括：

   作业名称

   作业需要执行时间

   作业的内存需求

   作业调入主存时间

   作业执行结束时间

   作业所在分区的起始地址

建立描述内存已分配分区的数据结构；

建立描述内存未分配的空闲分区的数据结构；

空闲分区和已分配分区的信息可以使用分区表来描述。系统中所有空闲分区构成分区表，所有已分配分区构成分配分区表。

出于效率的考虑，也可使用分区链来记录分区信息。分区链是一种双向链表，链表的每个结点描述一个分区的信息。系统中所有空闲分区构成空闲分区链，所有已分配分区构成分配分区链。分配和回收分区时，需要在这两个链表中进行结点的查找和插入、删除与修改操作。为改进算法的执行效率，可以将分区链按特定的顺序排序。

分区链结点的数据结构为：

Struct Section {
          Section *pPre;  //前向指针，指向链表的前一个结点
          int nSart；     //分区的起始地址
     	    int nSize；     //分区的尺寸
          Section *pSuf； //后向指针，指向链表的后一个结点
}；

Ÿ   可变分区分配算法——最先适应分配算法

最先适应分配算法要求空闲分区按地址递增的顺序排列，在进行内存分配时，从低地址部分向高地址部分查找，直到找到一个能满足要求的空闲分区为止。然后按作业实际大小，从该空闲区划出一块空间给作业，剩下的继续留在记录空闲分区的数据结构中。

（1）   可变分区的回收算法

当作业运行完毕释放内存时，系统首先根据回收分区的首地址，在分配分区表（链）中找到相应的分区结点，摘下该结点并插入空闲分区表（链），插入时应该根据插入点附近空闲分区的情况进行处理，主要有以下几种情况：

Ÿ   回收区与插入点的前一分区相邻接，将这两个分区合并为一个；

Ÿ   回收区与插入点的后一分区相邻接，将这两个分区合并为一个；

Ÿ   回收区与插入点的前后分区均相邻接，将这三个分区合并为一个；

Ÿ   回收区与插入点的前后分区均不邻接，将这两个分区合并为一个。

3. 实验内容

（1）编程实现简单的可变分区分配存储管理系统。要求：

a)   建立描述作业和内存分区的数据结构。

b)   初始信息输入，包括内存初始大小、各作业信息、使用哪种分区分配算法等。这些信息可以直接从键盘上输入，也可以从文件读取。

c)   程序实现最先适应分配算法，程序初始化或运行过程中都应能指定算法。

d)   编程实现分区回收算法，对实验列出的几种分区回收情况都应该能处理。

（2）使用本程序执行下面的一批作业，观察内存的分配和回收情况。系统可用内存的大小为2560K。

4. 实验步骤

         i.      选用合适的实验程序开发环境。

        ii.      设计程序结构，规划程序功能。

        iii.      完成程序的编码与测试。

        iv.      设计实验数据。

         v.      针对实验数据运行程序，并将结果记录在实验报告上。

 5.实验代码：

#include "iostream"
#include"stdlib.h" 
using namespace std;
#define Free 0 // 空闲状态
#define Busy 1 // 已分配状态
#define OK 1 // 分配成功
#define ERROR 0 // 分配出错
#define MAX_length 1024 // 最大内存空间为 1024
int flag;
typedef struct freeSpace // 定义一个空闲区表结构
{
long size; // 分区大小
long address; // 分区首地址
int state; // 分区分配状态
}ElemType;
// 线性表的双向链表存储结构
typedef struct DuLNode
{
ElemType data;
struct DuLNode *prior; // 前趋指针
struct DuLNode *next; // 后继指针
}
DuLNode ,*DuLinkList;
DuLinkList head_Node; // 头结点
DuLinkList end_Node; // 尾结点
int alloc(int); // 内存分配选择
int free(int); // 内存回收
int First_fit(int); // 首次适应算法
void show(); // 查看分配
int Initblock(); // 初始化空间表

int Initblock() // 初始化带头结点的内存空间
{
head_Node=(DuLinkList)malloc(sizeof(DuLNode));// 动态分配头节点内

end_Node=(DuLinkList)malloc(sizeof(DuLNode));// 动态分配尾节点内存

if(head_Node!=NULL)//动态内存申请成功 
{
head_Node->prior=NULL; // 头结点的前驱指针指向空
head_Node->next=end_Node; // 头结点的后继指针指向尾

end_Node->prior=head_Node; // 尾结点的前驱指针指向头

end_Node->next=NULL; // 尾结点的后继指针指向空
end_Node->data.address=0; // 尾结点的地址是 0
end_Node->data.size=MAX_length; // 分区大小是最大分区
end_Node->data.state=Free; // 状态是空
return OK;
}
else
return ERROR;
}
//主函数  
int main()
{
int ch;
Initblock(); // 设置初始空间表
int choice; // 操作标记
while(1)
{  cout<<"\n1:  分配内存 \t2:  回收内存 \t3: 内存使用情况显示 \t4:  退出\n\n";
cout<<" 请选择您的操作： ";
cin>>choice;
if(choice==1)
{
alloc(ch);
}//  分配内存
else if(choice==2) //  内存回收
{
int flag;
cout<<" 请输入您要释放的分区号： ";
cin>>flag;
free(flag);
}
else if(choice==3)
show();
else if(choice==4)
exit(0); // 退出
else // 输入操作有误
{
cout<<" 输入有误，请重试 !"<<endl;
continue;
}
}
} 

// 分配主存
int alloc(int ch)
{
int need;
cout<<"\n\n 请输入需要分配的空间大小 :";
cin>>need;
if(need<=0)
{
cout<<"\n\n 请重新输入分配大小 !"<<endl;
return ERROR;
}
if(First_fit(need)==OK)//调用首次适应算法 
cout<<" 分配成功 !"<<endl;
else
cout<<" 内存不足，分配失败 !"<<endl;
return OK;
}
// 首次适应算法
int First_fit(int need)
{
DuLinkList temp=(DuLinkList)malloc(sizeof(DuLNode)); 

temp->data.size=need; // 设置新申请空间的大小
temp->data.state=Busy; // 设置新申请空间的状态 

DuLNode *p=head_Node->next;
while(p)
{
if(p->data.state==Free && p->data.size==need) // 现有的空闲

{
p->data.state=Busy; // 修改该空闲块的状态为已分配
return OK;
break;
}
if(p->data.state==Free && p->data.size>need) // 现有的空闲

{
temp->prior=p->prior; // 修改双向链

temp->next=p;
temp->data.address=p->data.address;
p->prior->next=temp;
p->prior=temp;
p->data.address+=need;//修改剩余空闲区的首地址 
p->data.size-=need;//修改剩余空闲区的大小 
return OK;
break;
}
p=p->next;
}
return ERROR;
}

// 回收算法
int free(int flag)
{
DuLNode *p=head_Node;
for(int i= 0; i <= flag; i++)
if(p!=NULL)
p=p->next;
else
return ERROR;
p->data.state=Free;
if(p->prior!=head_Node && 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!=end_Node  && 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==end_Node && 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 主存分配情况 :\n";
cout<<"++++++++++++++++++++++++++++++++++++++++++++++\n\n";
DuLNode *p=head_Node->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";
}