空闲空间管理

Monday, October 28, 2019

空闲空间管理

如果要管理的空间由大小不同的单元构成,管理就会变得困难,随着不断的分配和释放,会出现外部碎片问题,空间被切割成不同大小的小块,成为碎片。后续需要请求大的内存就会失败,因为没有一片足够大的连续空间。

分割与合并

假设我们有一段0-30字节区域的空间,只有10-20是被使用了,如下图所示。 OS17.1

空闲列表如下图所示: OS17.2

从图中我们可以知道,如果申请一个大于10字节的空间,会失败,因为没有连续的空间足以分配超过10字节的空间。

如果申请一个小于10字节的空间,则会将空闲空间的切割出来,一部分拿来分配,另一部分留在空闲列表。

另外也有合并机制,假如有一块被释放了,如果相邻的也是空闲空间,则会合并在一起。

追踪已分配空间的大小

大多数分配程序都会在头块(header)保存一些额外的信息来加速空间的释放,所以在释放时,实际释放的是头块大小加上分配给用户的空间的大小。

让堆增长

大多数程序一开始会分配很小的堆开始,当空间耗尽,再像操作系统申请更大的你空间,操作系统会找到空闲的物理内存页,将他们映射到进程的地址空间去,并返回新的堆的末尾地址。

基本策略

最优匹配

遍历整个空闲列表,找到和请求一样大小或更大的空闲块,找到最小的那一块,这就是最优匹配。缺点是遍历查找要付出较高的性能代价。

最差匹配

找到最大的空闲块,然后切割出需要的那一部分,将剩余的块加入回空闲列表。但是大多数研究表明效果非常差。

首次匹配

找到一个足够大的块,然后将空间返回给用户,将剩余的部分返回给空闲列表。优势是速度快,但是会让空闲列表开头的部分有很多小块。如何管理空闲列表的顺序就会变得很重要,一种方式基于地址排序,通过保持空闲块按地址有序,合并操作会很容易,减少了内存碎片。

下次匹配

不同于首次匹配,下次匹配算法会多维护一个指针,指向上次查找结束的位置,避免了对列表开头的频繁分割,性能与首次匹配很接近。

分离空闲列表

用一个独立的列表,专门管理几种固定大小的内存分配

伙伴系统

主要为了让合并变得简单,利用二分法,找到最小的一块能满足用户的空间。

OS

分页

内存分段