《网络操作系统》
课程设计报告书
题目：最佳适应算法
学号： 121007335 学生姓名：张梦思
专业：网络工程
指导教师：余建国
2014年5月31日
目录
1 功能描述 (3)
1.1总体思想........................................................................................... 错误！未定义书签。

1.2算法分析.................................................................................. 错误！未定义书签。

2 系统设计 (3)
3 系统实现 (5)
4 系统测试与分析 (7)
教师评分表 (10)
1 功能描述
1.1 总体思想
最佳适应算法是动态分区分配的一种内存分配算法。

所谓最佳是指每次为作业分配内存时，总是把能满足要求，又是最小的空闲分区分配给作业，避免“大材小用”。

为了加速寻找，该算法要求将所有的空闲分区按其容量以从小到大的顺序形成以空闲分区链。

这样，第一次找到的能满足要求的空闲区，必然是最佳的。

1.2算法分析
按空闲分区大小从小到大排列；
每次变换后，按空闲分区大小从小到大排列。

2 系统设计
2.1最佳适应算法的实现有好多种，比如链表，本次程序中使用数组来实现，实现了最基本的功能，没有考虑到内存的回收问题。

3 系统实现
这个程序是通过vc6.0软件用c语言编译而成，为了实现最佳适应算法，使用了数组，直接选择排序
程序代码
#include<stdio.h>
void main()
{
int m,n,i,j,j0,k,k0,A[30][3],B[30];
printf("请输入空闲分区块数：");
scanf("%d",&m);
printf("\t分区号\t\t大小\t\t起始地址\n");
for(i=0;i<m;i++)
for(j=0;j<3;j++)
scanf("%d",&A[i][j]);
for(i=0;i<m-1;i++)
{
k0=i;
for(k=i+1;k<m;k++)
if(A[k][1]<A[k0][1])
k0=k;
if(k0!=i)
{
for(j=0;j<3;j++)
{
int t;
t=A[k0][j];
A[k0][j]=A[i][j];
A[i][j]=t;
}
}
}
printf("\n--------最佳适应算法按地址从小到大排列后空闲区-------\n");
printf("\t分区号\t\t大小\t\t起始地址\n");
for(i=0;i<m;i++)
for(j=0;j<3;j++)
{
printf("\t%d\t",A[i][j]);
if(j==2)
printf("\n");
}
printf("\n请输入要分配的作业数：");
scanf("%d",&n);
printf("请输入作业大小：");
for(j0=0;j0<n;j0++)
scanf("%d",&B[j0]);
i=j0=0;
do
{
while(A[i][j]<B[j0] && i<m)
i++;
if(i==m)
printf("\n内存不足，%d大小的作业需要等待内存资源！\n",B[j0]);
if(i<m)
{
A[i][1]=A[i][1]-B[j0];
A[i][2]=A[i][2]+B[j0];
}
j0++;
for(i=0;i<m-1;i++)
{
k0=i;
for(k=i+1;k<m;k++)
if(A[k][1]<A[k0][1])
k0=k;
if(k0!=i)
{
for(j=0;j<3;j++)
{
int t;
t=A[k0][j];
A[k0][j]=A[i][j];
A[i][j]=t;
}
}
}
i=0;
}while(j0<n);
printf("\n------最佳适应算法分配后的空闲区------\n");
printf("\t分区号\t\t大小\t\t起始地址\n");
for(i=0;i<m;i++)
for(j=0;j<3;j++)
{
if(A[i][1])
printf("\t%d\t",A[i][j]);
if(j==2)
printf("\n");
}
}
4 系统测试与分析
1、运行程序，系统提示输入空闲分块数
2、建立分区后，最佳适应算法将空闲分区按从小到大的顺序排列
3,、输入要分配的作业数及作业大小
4、最佳适应算法分配后的空闲区情况
5、作业需要等待的情况
教师评分表。