c++大作业--动态内存分区分配方式模拟
(2011-02-05 22:55:25)
标签:
动态内存分配it |
分类: 程序人生 |
假设初始态下,可用内存空间为640K,并有下列请求序列,请分别用首次适应算法和最佳适应算法为作业分配和回收内存块,并显示出每次分配和回收后的空闲分区链的情况来以及内存占用情况图。
......
一、算法的基本思想
首次适应算法中,空闲分区链是按地址递增的次序链接的,当要分配内存空间时,就在所有空闲分区中查找满足大小要求的可用块,只要找到第一个足以满足要求的空间就停止查找,并把它分配给请求者,如果该空闲空间与所需空间大小一样,则将该分区的状态改为1,表明已被分配,若还有剩余,则将剩余空间重新划为一个空闲分区,有新的起始地址,状态为0。如果从头到尾找不到,则分配失败。
最佳适应算法的空闲链是按照空闲块的大小为序、所有空闲区按容量从小到大的顺序形成空闲分区链。在进行内存分配时候,它在满足需要的前提下,尽量分配最小的空闲块,这样每次查找分配时,从链首开始查找,第一次找到的能满足要求的必然的最佳的,若空闲空间大小与要分配的大小相同时,可直接将其状态改为1即可,若有剩余,则将剩余空闲空间重新划分为一个空闲区,然后根据空闲区的大小对链表进行重新排序,这里对空闲分区大小排序采用了快速排序算法。
首次适应算法的分区回收过程相对简单,因为分区链是按照地址顺序链接的,因此释放内存时只需要判断要释放的分区前后是否也为空闲区,如果前后有空闲分区,则需要进行合并,合并的原则是排在后面的分区合并到前面的分区中,如果前后分区都已分配,则直接将该分区状态改为0即可。
最佳适应算法分区回收时,因为它的空闲分区链是按照空间大小排列的,因此不仅要看要释放分区前后是否为空闲,还要判断其地址是否前后相接,若地址不相接,则即使要释放分区前后均为空闲区,也不能进行合并,而且每次释放后要根据释放空间的大小对链表进行重新排序,同样采用快速排序算法进行重新排序。
二、空闲分区链的结构
struct SubareaNode
{
}
三、通用算法分配内存
通用算法分配内存原理是首先判断申请内存的大小能否在空闲分区中找到适合的,如果找到分两种情况,一是刚好大小一致,二是空闲分区比申请内存大小大,则需要划分空闲分区,剩余的空间为新的分区。
四、首次算法回收内存
五、最佳算法回收内存
最佳算法回收内存主要是实现对内存回收,关键点是根据地址判断前后分区有否空闲,如果有需要合并。在回收后,需要重新排序空闲分区。
六、空闲分区的重新排序
空闲分区的重新排序,需要定义一个空闲分区指针数组,一个空闲分区的空间大小数组,然后调用快速排序函数,根据空间大小进行排序,排序完成后,空闲分区指针数组相应也进行了重新排序,接着是根据指针数组对原来的空闲分区链表排序。
七、快速排序
快速排序是在待排序n个记录中任取一个作为“基准”,将其余记录分为两组,第一组中各记录的值均小于或等于基准的值,第二组中各记录的值均大于或等于基准的值。对所分成两组分别重复上述方法,直到所有记录排在合适位置上。
Parr[]是空闲分区链表指针数组,arr[]是记录每个分区空间大小的整形数组。所以使用快速算法对每个分区空间大小排序,排序的同时也相应调整空闲分区链表指针的先后顺序,这样在排序后,可以利用Parr[]对原来的分区链表进行重新定义。
八、执行截图:
附注:完整程序代码查看地址:
http://blog.csdn.net/raymentblog/archive/2011/02/05/6173073.aspx