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;
第一步：（第13周完成）
完成程序数据结构的创建，初始化内存分配情况，创建空闲分区表和已分配分区表。
源代码：
#include <stdio.h>
#include<conio.h>
#include<string.h>
#define MAX 100
struct partition{
char pn[10];
int begin;
int size;
int end;
char status;
};
typedef struct partition PART;
PART p[MAX];
int n;
void init()//初始化
{
p[0].begin = 0;
p[0].end = 100;
strcpy(p[0].pn, "SYSTEM");
p[0].size = 100;
p[0].status = 'u';
p[1].begin = 100;
p[1].end = 1024;
strcpy(p[1].pn, "-----");
p[1].size = p[1].end - p[1].begin;
p[1].status = 'f';
n = 2;
}
void show()//显示分区
{
int x = 1;
printf("空闲区表Free：\n");
printf("\tNo.\tproname\tbegin\tsize\tstatus\n");
for(int i = 0; i < n; i++)
{
if(p[i].status=='f')
printf("\tNo.%d\t%s\t%4d\t%4d\t%4c\n", x++, p[i].pn, p[i].begin, p[i].size, p[i].status);
}
printf("\n\n=========================================================\n");
printf("已分配分区表Used：\n");
printf("\tNo.\tproname\tbegin\tsize\tstatus\n");
for(i = 0, x = 1; i < n; i++)
{
if(p[i].status=='u')
printf("\tNo.%d\t%s\t%4d\t%4d\t%4c\n", x++, p[i].pn, p[i].begin, p[i].size, p[i].status);
}
printf("\n\n=========================================================\n");
printf("内存使用情况：\nprintf sorted by address:\n");
printf("\tNo.\tproname\tbegin\tsize\tstatus\n");
printf("\t--------------------------------------\n");
for(i = 0, x = 1; i < n; i++)
{
printf("\tNo.%d\t%s\t%4d\t%4d\t%4c\n", x++, p[i].pn, p[i].begin, p[i].size, p[i].status);
}
}
void Input()//输入作业
{
int x = 1;
while(x)
{
printf("\n\n请输入进程名称：");
scanf("%s", &p[n].pn);
for(int i = 0; i < n; i++)
{
x = 0;
if(strcmp(p[n].pn, p[i].pn) == 0)
{
x = 1;
printf("进程名称已存在，请重新输入!");
break;
}
}
}
x = 1;
while(x)
{
printf("\n请输入进程需要的空间大小：");
scanf("%d", &p[n].size);
for(int i = 0; i < n; i++)
{
if(p[i].size >=p[n].size)
{
x = 0;
break;
}
}
if(x)
printf("找不到适合的空间，请重新输入!");
}
}
void jisuan(int i)
{
int x=0;
p[i].end = p[i].begin+p[i].size;
p[i-1].end=p[i-1].begin+p[i-1].size;
if(p[i+1].status=='f' && p[i].end==p[i+1].begin)
{ x=1;
p[i+1].begin=p[i].begin;
p[i+1].size=p[i].size+p[i+1].size;
for(int j=i;j<n;j++)
{
p[j]=p[j+1];
}
n=n-1;
}
if(p[i-1].status=='f' && p[i-1].end==p[i].begin)
{ x=1;
p[i].begin=p[i-1].begin;
p[i].size=p[i-1].size+p[i].size;
strcpy(p[i].pn, "-----");
p[i].status = 'f';
for(int k=i;k<n;k++)
{
p[k-1]=p[k];
}
n=n-1;
}
if(x==0)
{
strcpy(p[i].pn, "-----");
p[i].status = 'f';
}
}
void recycle()//循环
{
char name[50];
int x = 1;
while(x)
{
printf("\n请输入进程名称：");
scanf("%s", &name);
for(int i = 0; i < n; i++)
{
if(strcmp(name, p[i].pn) == 0)
{
x = 0;
jisuan(i);
break;
}
}
if(x==1)
{
printf("没找到请重新输入\n");
}
}
}
void first_comfortable()//首次适应
{
PART temp[MAX];
for(int i = 0;i < n; i++)
{
if(p[i].status=='f')
{
if(p[i].size >= p[n].size)
{
temp[0]=p[i];
p[i]=p[n];
p[n]=temp[0];
p[i].end=p[n].begin+p[i].size;
p[i].status='u';
p[i].begin=p[n].begin;
p[n].begin=p[i].end;
p[n].end=temp[0].end;
p[n].status='f';
p[n].size=p[n].size-p[i].size;
n++;
break;
}
}
}
}
void best_comfortable()//最佳适应算法
{
int min=10000;
int a;
PART temp[MAX];
for(int i=0;i<n;i++)
{
if(p[i].status=='f' && p[i].size >= p[n].size)
{
if(p[i].size < min)
{
min = p[i].size;
a=i;
}
}
}
if(p[a].size >= p[n].size)
{
temp[0]=p[a];
p[a]=p[n];
p[n]=temp[0];
p[a].end=p[n].begin+p[a].size;
p[a].status='u';
p[a].begin=p[n].begin;
p[n].begin=p[a].end;
p[n].end=temp[0].end;
p[n].status='f';
p[n].size=p[n].size-p[a].size;
n++;
}
}
void bad_comfortable()//最坏适应算法
{
int max=0;
int a;
PART temp[MAX];
for(int i=0;i<n;i++)
{
if(p[i].status=='f')
{
if(p[i].size > max)
{
max = p[i].size;
a=i;
}
}
}
if(p[a].size >= p[n].size)
{
temp[0]=p[a];
p[a]=p[n];
p[n]=temp[0];
p[a].end=p[n].begin+p[a].size;
p[a].status='u';
p[a].begin=p[n].begin;
p[n].begin=p[a].end;
p[n].end=temp[0].end;
p[n].status='f';
p[n].size=p[n].size-p[a].size;
n++;
}
}
int menu1()
{
int x;
printf("\n(1)首次适应算法");
// printf("\n(2)循环首次适应算法");
printf("\n(2)最佳适应算法");
printf("\n(3)最坏适应算法");
printf("\n请选择一种分配方式：");
scanf("%d", &x);
while(x < 1 || x > 4)
{
printf("\n输入错误!");
printf("\n请选择一种分配方式：");
scanf("%d", &x);
}
return x;
}
int main(void)
{
int a1,a2;
printf("初始化：设置内存总容量为 1024k\n系统从低地址部分开始占用 100k\n\n");
init();
show();
while(1)
{
printf("1.分配内存 \n");
printf("2.回收内存 \n");
printf("3.结束 \n");
printf("请选择:");
scanf("%d",&a1);
if(a1==1)
{
Input();
a2=menu1();
if(a2==1)
{
first_comfortable();
}
if(a2==2)
{
best_comfortable();
}
if(a2==3)
{
bad_comfortable();
}
show();
}
if(a1==2)
{
recycle();
show();
}
if(a1==3)
break;
}
return 0;
}
结果截图：
