实验四 主存空间的分配和回收
专业：商业软件工程一班 姓名：张鑫相 学号：201406114109
1. 目的和要求
1.1. 实验目的
用高级语言完成一个主存空间的分配和回收程序，以加深对动态分区分配方式及其算法的理解。
1.2. 实验要求
采用连续分配方式之动态分区分配存储管理，使用首次适应算法、循环首次适应算法、最佳适应算法和最坏适应算法4种算法完成设计。
（1）**设计一个作业申请队列以及作业完成后的释放顺序，实现主存的分配和回收。采用分区说明表进行。
（2）或在程序运行过程，由用户指定申请与释放。
（3）设计一个空闲区说明表，以保存某时刻主存空间占用情况。
把空闲区说明表的变化情况以及各作业的申请、释放情况显示。
2. 实验内容
根据指定的实验课题，完成设计、编码和调试工作，完成实验报告。
3. 实验环境
可以选用Visual C++作为开发环境。也可以选用Windows下的VB，CB或其他可视化环境，利用各种控件较为方便。自主选择实验环境。
4. 参考数据结构：
#include<stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 24
struct partition{
char pn[10];
int begin;
int size;
int end; ////////
char status; //////////
};
typedef struct partition PART;
5、源代码
#include<stdio.h>
#include<stdlib.h>
#include <conio.h>
#define nil -1
#define NULL 0
#define maxisize 600 //用户的空闲区空间最大值
#define minisize 4
#define getspace(type) (type*)malloc(sizeof(type)) //分配空间
struct partition{
char pn; //作业标号
float begin; //分区起始地址
float size; //分区长度，单位为字节
int status; //分区表的状态位
struct partition *FRlink; //前向指针
struct partition *RElink; //后向指针
}*free_partition=NULL,*place; //已分配分区表,空闲分区表
typedef struct partition PART;
PART *init(PART *td) //空间分区链表初始化
{
td->FRlink=NULL;
td->pn=nil;
td->begin=1064;
td->size=1664;
td->status=0;
td->RElink=NULL;
return td;
}
//主存分配函数，为作业pn分配大小为xk的分区空间
void allocate(char pn,float xk,int choice)
{
PART *td,*link;
int k=0;
float temp=600;
if (free_partition->FRlink==NULL&&free_partition->RElink==NULL)
{//给首个作业分配空间，改写分区链表
free_partition->pn=pn;
free_partition->size=xk;
free_partition->status=1;
if (xk<maxisize)
{
td=getspace(PART);
free_partition->RElink=td;
td->FRlink=free_partition;
td->pn=nil;
td->begin=1064+xk;
td->size=maxisize-xk;
td->status=0;
}
if (choice==2)
{//链接成循环链表
free_partition->FRlink=td;
td->RElink=free_partition;
place=td;
}
else
{
free_partition->FRlink=NULL;
if (xk<maxisize)
td->RElink=NULL;
}
k=1;
}
else
{
if (2==choice)
td=place;//采用CFF时将ta定位到上次找到的合适空间分区的下个空间分区
else
td=free_partition;
while(td!=NULL)
{
if (3==choice)
{
while(td!=NULL)
{
if (td->size>=xk&&td->status==0)
if (td->size<temp)
{
place=td;temp=td->size;
} //选择最适合空间
td=td->RElink;
}
td=place;
}
if (td->size>=xk&&td->status==0)
if (td->size-xk<=minisize)
{//当搜索到的空间大小<=xk+minisize时，将空间全部分配给作业
td->pn=pn;
td->status=1;
place=td->RElink;
k=1;
break;
}
else
{//当搜索到的空间大小>xk+minisize时，将空间划分，再分配给作业
link=getspace(PART);
link->size=td->size-xk;
td->pn=pn;
td->size=xk;
td->status=1;
link->RElink=td->RElink;
if (NULL!=td->RElink)
td->RElink->FRlink=link;
td->RElink=link;
link->FRlink=td;
link->pn=nil;
link->begin=td->begin+xk;
link->status=0;
place=link;
k=1;
break;
}
td=td->RElink;
}
}
if (0==k)
{//未寻找到合适的空间分区，返回
printf("空间申请失败!
");
return;
}
}
void reclaim(char pn,int choice) //主存回收函数，回收作业pn所占用的分区空间
{
int bool1=0,bool2=0;
PART *td,*link;
td=free_partition;
if (2==choice)
link=td;
else
link=NULL;
do
{
if (pn==td->pn&&1==td->status)
break;
td=td->RElink;
if (td==link)
{
printf("
抱歉，作业不存在%c!
",pn);
return;
}
}
while(td!=link);
bool1=(NULL==td->FRlink||td->FRlink==td->RElink)? 1:td->FRlink->status;
bool2=(NULL==td->RElink||td->FRlink==td->RElink)? 1:td->RElink->status;
if (bool1&&bool2)
{
td->pn=nil;
td->status=0;
}
else if ((NULL==td->FRlink||1==td->FRlink->status)&&0==td->RElink->status)
{
link=td->RElink;
td->pn=nil;
td->size+=link->size;
td->status=0;
td->RElink=link->RElink;
if (NULL!=link->RElink)
link->RElink->FRlink=td;
free(link);
}
else if (0==td->FRlink->status&&1==td->RElink->status)
{
link=td->FRlink;
link->size+=td->size;
link->RElink=td->RElink;
td->RElink->FRlink=link;
if (free_partition==td)
free_partition=link;
free(td);
}
else if (0==td->FRlink->status&&0==td->RElink->status)
{
link=td->FRlink;
link->size=link->size+td->size+td->RElink->size;
link->RElink=td->RElink->RElink;
if (NULL!=td->RElink->RElink)
td->RElink->RElink->FRlink=link;
if (free_partition==td)
free_partition=link;
free(td);
free(td->RElink);
}
}
//显示空间分区链表
void display(PART *td,int choice)
{
PART *temp;
if (2==choice)
temp=td;
else
temp=NULL;
printf("
作业 分区首地址 分区大小(KB) 状态
");
printf("
sys 1024.00 40.00 1
");
do
{
printf("
%c %.2f %.2f %d
",td->pn,td->begin,td->size,td->status);
td=td->RElink;
}while(temp!=td);
}
//主函数
int main()
{
int i,a,choice;
float xk;
char pn;
PART *ta=getspace(PART);
free_partition=init(ta);
do
{
printf("--------------------------------------------");
printf("
分区分配算法:
1 - 首次适应算法(FF)
2 - 循环首次适应算法(CFF)
0 - 退出(Exit)
");
printf("--------------------------------------------
");
printf("请选择相应的算法(0-2):");
scanf("%d",&choice);
if (0==choice)
exit(0);
}while(0>choice&&2<choice);
while(1)
{
printf("--------------------------------------------");
printf("
菜单:
1 - 申请空间(Allocation)
2 - 回收空间(Reclaim)
0 - 退出(Exit)
");
printf("--------------------------------------------
");
printf("请选择你的操作(0-2):");
scanf("%d",&a);
switch(a)
{
case 0:
exit(0); //a=0,程序结束
case 1: //a=1,分配主存空间
printf("请输入作业标号和所需要申请的空间:");
scanf("%*c%c%f",&pn,&xk);
allocate(pn,xk,choice);
display(free_partition,choice);
break;
case 2: //a=2,回收主存空间
printf("请输入你想回收的作业的相应标号:");
scanf("%*c%c",&pn);
reclaim(pn,choice);
display(free_partition,choice);
break;
default:printf("出错了，没有此项选择!
");
}
}
}
六、实验截图
