图中展示了一个总长度为 100 的内存区域,已经分割成 16、16、20、16、16、16 六个
小的内存块。其中着色部分,也就是第一、第三和第五块内存是已经分配出去的,正在使
用的内存,而白色区域则是尚未分配的内存。图的上半部分代表空闲链表,每一块未分配
的内存都会由一个空闲链表的节点进行管理。结点中记录了这块空闲内存区域的起始位置
和长度。
当分配内存的请求到达以后,我们就通过遍历 free list 来查找可用的空闲内存区域,在找
到合适的空闲区域以后,就将这一块区域从链表中摘下来。比如要请求的大小是 m,就将
这个结点从链表中取下,把起始位置向后移动 m,大小也相应的减小 m。将修改后的结点
重新挂到链表上。
在释放的时候,将这块区域按照起始起址的排序放回到链表里,并且检查它的前后是否有
空闲区域,如果有就合并成一个更大的空闲区。
这种算法所使用的数据结构比较简单,算法也很直接,我们把这种算法称为简单算法
(Naive Algorithm)。我们举个例子说明简单算法的运行过程,假如在算法开始时,内存的
情况如下图所示: