内存分配

利用教师提供的图形包代码，编写程序，实现内存的分配算法（最佳适配和邻近适配）。

二、实验内容

（1）在所提供的程序基础之上实现最佳适配和邻近适配算法。 （2）增加测试案例，验证程序的正确性

——删除掉一个分配的进程（进程3） ——重新分配一个进程，假设进程6大小为100 （3）利用VC++6.0实现上述程序设计和调试操作。 （4）通过阅读和分析实验程序，熟悉内存分配算法。

三、实验步骤

1、创建结构体

本次实验将待分配的进程和内存空间视作整体进行操作，则应构造两个结构体分别用来表示。各结构体的参数以及注解如下所示： /*内存块结构，可以表示主存空间占用情况（链表形式）*/ typedef struct MemoryBlock {

long StartAddr; long BlockLength; int JobIndex;

//内存块起始地址(单位 KB) //内存块长度(单位 KB)

//属于那个作业。nBelongToJob=0 表示“空闲”

//指向下一个MemoryBlock //指向上一个MemoryBlock

MemoryBlock * nextPointer; MemoryBlock * prePointer; };

/*作业控制块信息结构*/ typedef struct JCBInfo{

char* JobName; int JobIndex; int JobLength;

//作业名 //作业序号 //作业大小 //页表首地址 //指向下一个JCBInfo //指向上一个JCBInfo

int* JobPageTable;

JCBInfo * nextPointer; JCBInfo * prePointer; };

2、首次适配算法

首次适配算法是指在分配给进程内存的时候，始终将进程分配给第一个可以装下该进程的空间。算法的实质是遍历整个内存，找到当前未被分配的空间并与内存的大小进行比较，如空间大小大于进程的大小则直接装入。

分配时，创建一个进程大小的新空间tmpMemBlock（指针），新空间的信息由进程的的信息以及被分配的空间的信息构成。然后将新空间装入被分配的空间中，prePointer指向被分配的空间prePointer指针指向的模块，nextPointer指针指向分配的空间；同时改变被分配的空间的初始地址和长度，并将其prePointer指针指向新空间。当然还要考虑被分配的进程是不是被放在内存的第一个空间块这一情况。

3、最佳适配算法

最佳适配算法与首次适配算法的不同是，系统选择所有能容纳进程的空间中最小的那个来存放该进程。因此，需定义变量BestArea_Size和Wantted_Position，分别用来保存当前最适配空间的大小和保存当前最适配空间的地址，在遍历整个内存的同时，不断刷新两个变量的值以找到可以存放进程的最小空间。

分配时，创建一个进程大小的新空间tmpMemBlock（指针），新空间的信息由进程的的信息以及被分配的空间的信息构成。然后将新空间装入被分配的空间

中，prePointer指向被分配的空间prePointer指针指向的模块，nextPointer指针指向分配的空间；同时改变被分配的空间的初始地址和长度，并将其prePointer指针指向新空间。当然还要考虑被分配的进程是不是被放在内存的第一个空间块这一情况。

4、下次适配算法

下次适配算法类似于首次适配算法，也是将进程分配给第一个可以装下该进程的空间。不同的是下次适配算法每次是从上一次分配的地址出开始遍历内存，因此需要设置一个全局变量MarkPoint，用来标记当前分配后指定的位置，注意当MarkPoint的值变成NULL时，要重新赋值使其跳转到内存的链表头部。除此之外的步骤与首次适配算法相同。

分配时，创建一个进程大小的新空间tmpMemBlock（指针），新空间的信息由进程的的信息以及被分配的空间的信息构成。然后将新空间装入被分配的空间中，prePointer指向被分配的空间prePointer指针指向的模块，nextPointer指针指向分配的空间；同时改变被分配的空间的初始地址和长度，并将其prePointer指针指向新空间。当然还要考虑被分配的进程是不是被放在内存的第一个空间块这一情况。

5、内存释放算法

因为内存的大小只有1024KB，所以如果不对进程进行释放，很快就会空间不足的情况。对于内存释放算法，最基本的操作是将该内存块的JobIndex改为0（空闲状态），但是仅此是不够的，我们还需要考虑的多种的情况来进一步合并空闲空间，下面做一一阐述，假定被释放块的指针为p： （1）被释放的位置在内存的顶部

这种情况的只需要在考虑下一个内存块是否处于空闲状态。如果不处于被占用的状态则释放完成；否则，需要改变p的BlockLength值（空间合并）和nextPointer值（指向下一个内存块的nextPointer所指向的模块），其他的值不变。

（2）被释放的位置在内存的底部

这种情况只需考虑上一个内存块是否处于空闲状态。如果不处于被占用的状态则释放完成；否则，需要改变p的BlockLength值（空间合并）和prePointer值（指向下一个内存块的prePointer所指向的模块），还有p的StartAddr（由于向上合并指针上移），其他的值不变。

（3）被释放的位置在内存的底部

这种情况最为复杂，需要考虑的是上下两个内存是否处于空闲状态。如果不处于被占用的状态则释放完成，否则，若上一块处在占用状态，需要改变p的BlockLength值（空间合并）和prePointer值（指向下一个内存块的prePointer所指向的模块），还有p的StartAddr（由于向上合并指针上移）；若下一块处在占用状态，需要改变p的BlockLength值（空间合并）和nextPointer值（指向下一个内存块的nextPointer所指向的模块），其他的值不变。

四、系统截图

1、初始界面（已用首次适配方法）

2、删除第一个作业和第三个作业（为测试所用）

3、测试最佳适配的代码段（插入大小为20,186,20的作业）

4、测试下次适配的代码段（插入大小为190,170,50的作业）

5、测试释放算法（多种情况的展示，先加上大小为208的作业成全满状态）

（1）先删除作业2再删除作业1的情况

（2）先删除作业2和作业4再删除作业3的情况

（3）删除最后一个作业的情况

（4）删除第一个作业的情况

五、遇到的问题

由于这次的代码涉及到了MFC的内容，而这一块的知识点我并不了解，所以在显示结果方面遇到了比较大的麻烦，程序比较挫，每次想看不同的结果只能退出整个程序。

其实内存分配算法在本质上来说是对指针的操作，只需要注意指针与指针之间的关系以及不要出现空指针即可，另外已经有了首次适配参考的代码，所以要实现起来并不是特别的困难。

相比之下释放内存的算法中要考虑比较多的可能性，不过细心一点并与是由进行过讨论也可以基本上很顺利的写出来，程序给出了五种可能的结果并附有详细的注解。

在原来给出的首次算法中发现了一个问题，就是程序没有考虑分配的进程与空闲控制块大小刚好相等的情况，这样一来一定会出现较多的内部碎片，考虑到内存一共只有1MB，因此这是不能忽视的问题。当然因为程序的写法不能单纯地加一个等号了事，可以巧妙地直接修改空闲块的信息达到同样的效果。

在下次适配算法的实现中定义了一个MarkPoint指针来指向最后一次分配的地址位置。这里就要注意是如果再执行释放算法时，要先判断释放的位置是不是刚好处在MarkPoint指针所在的位置，如果是，则释放完内存后紧接着运行下次适配算法则会出现问题。要在每次的释放算法中向上合并的过程中加上对MarkPoint指针值的修改。

本来已经写好了内存压缩的算法，但是最后还是在显示结果的地方出了问题，还是比较遗憾的。