取最大值的块为类的大小
简单分离存储,每个大小类的空闲链表包含大小相等的块,每个块的大小就是这个大小类中最大元素的大小。例如,如果某个大小类定义为 {17 ~ 32},那么这个类的空闲链表全由大小为 32 的块组成
分配一个给定大小的块,我们检査相应的空闲链表。如果链表非空,我们简单地分配其中第一块的全部(而不是刚刚好需要分配的大小,有冗余)
空闲块是不会分割以满足分配请求的
如果链表为空,分配器就向操作系统请求一个固定大小的额外内存片(通常是页大小的整数倍)
将这个片分成大小相等的块,并将这些块链接起来形成新的空闲链表
要释放一个块,分配器只要简单地将这个块插入到相应的空闲链表的前部。
这种简单的方法有许多优点。分配和释放块都是很快的常数时间操作。而且,每个片中都是大小相等的块,不分割,不合并,这意味着每个块只有很少的内存开销
由于每个片只有大小相同的块,那么一个已分配块的大小就可以从它的地址中推断出来,
因为没有合并,所以已分配块的头部就不需要一个已分配/空闲标记
因此已分配块不需要头部,同时因为没有合并,它们也不需要脚部。因为分配和释放操作都是在空闲链表的起始处操作,所以链表只需要是单向的,而不用是双向的
关键点在于,在任何块中都需要的唯一字段是每个空闲块中的一个字的 succ 指针,因此最小块大小就是一个字
一个显著的缺点是,简单分离存储很容易造成内部和外部碎片。因为空闲块是不会被分割的,所以可能会造成内部碎片。更糟的是,因为不会合并空闲块,所以某些引用模式会引起极多的外部碎片
练习题
描述一个在基于简单分离存储的分配器中会导致严重外部碎片的引用模式。描述一个在基于简单分离存储的分配器中会导致严重外部碎片的引用模式。
Note
这里有一个会引起外部碎片的模式:应用对第一个大小类做大量的分配和释放请求,然后对第二个大小类做大量的分配和释放请求,接下来是对第三个大小类做大量的分配和释放请求,以此类推。对于每个大小类,分配器都创建了许多不会被回收的存储器,因为分配器不会合并,也因为应用不会再向这个大小类再次请求块了。