[stl] SGI STL的空间配置器

时间:2022-03-11 05:29:38

第一级空间配置器

  第一级配置以malloc(), free(), realloc()等c函数执行实际的内存配置,释放、重配置操作,并实现出类似c++ new handler的机制。它不能直接使用c++ new handler机制,因为它并非使用::operator new来配置内存。

  所谓的c++ new handler机制,就是你可以要求系统在内存配置需求无法被满足时,调用一个你所指定的函数。换句话说,一旦::operator new无法完成任务,在丢出std::bad_alloc异常状态之前,会调用一个由客户端指定的处理例程。该处理例程被称为c++ new handler。new handler解决内存不足的做法有特定的模式。

  //oom指:out of memory

  SGI以malloc而不是::operator new来配置内存,因此SGI不能直接使用C++的set_new_handler(),必须仿真一个类似的set_new_handler()。SGI低一级配置器的allocate()和realloc() 都是在调用malloc()和realloc()不成功之后,改调用oom_malloc()和oom_realloc()。后两者都有内循环,不断调用“内存不足处理例程”,期望在某次调用之后获得足够的内存圆满完成任务。但是如果“内存不足处理例程”并未被客户端设定,oom_malloc()和oom_realloc()便会调用_THROW_BAD_ALLOC,丢出bad_alloc异常信息,或利用二线exit(1)直接终止程序。

第二级空间配置器

  第二级配置器多了一些机制,避免太多小额区块造成内存的碎片。小额区块带来的其实不仅仅是内存碎片,配置时的额外负担(overhead系统开销(计算机网络)overhead,在计算机网络帧结构中,除了有用数据以外,还有很多控制信息,这些控制信息用来保证通信的完成。这些控制信息被称作系统开销。)也是一个大问题。额外负担永远无法避免,毕竟系统要靠这多出来的空间来管理内存。

  SGI第二级配置器的做法是,如果区块够大,超过128bytes时,就移交给第一级配置器处理。当区块小于128bytes时,则以内存池(memory pool)的方式管理,此法又称之为层次配置(sub_allocation):每次配置一大块内存,并维护对应的*链表(free list)。下次若再有相同大小的内存需求,就直接从free-lists中拨出。如果客户端释放了小额区块,也负责回收。为了方便管理,SGI第二级配置器会主动将任何小区块的内存需求量上调至8的倍数(如需求为30bytes,自动调整为32bytes)。并维护16(128/8=16)个free-lists,各自管理的大小为8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128的小额区块。

  free-lists的结构如下:

union obj{

union obj * free_list_link;

char client_data[1];   /*the client sees this.*/

    }

  大家可能会想为了维护链表,每个节点都需要额外的指针指向下一个节点,这不又造成了另一种额外负担么?但是请注意,上述obj所用的是union,所以从其第一个字段来看,obj可以被当做一个指向形式相同的另一个obj的指针;从第二个字段来看,可以把它看做指向实际区块的指针。

内存分配策略:

叙述之前做一下约定:

req_size ,表示用户请求的内存大小。

_round_up(size_t size),表示对用户请求的内存大小,向上调整为8的倍数。

例如:req_size = 14 , 那么_round_up(req_size ) 的返回值是16。

_pool_watermark(size_t size),表示用户请求的内存在head_list中的下标。

例如:req_size = 14 , 那么_pool_watermark(req_size ) 的返回值是1。

具体策略:
1)如果用户申请超过128字节的内存,则直接调用第一级简单空间配置器;否则,执行2)。

2)小于128bytes就检测对应的free-lists,如果free list之内有可用的区块,就直接返回给用户。如果没有可用区块,就将区块大小上调至8的倍数边界,然后调用refill(),准备为free list重新填充空间。

内存池取空间操作

从内存池中取空间给free
list,是chunk_alloc()的工作。其工作流程如下:

chunk_alloc()中以end_free
– start_free 来判断内存池是的剩余内存。

1, 
如果内存充足,则直接调出20个区块返回给对应的free list。

2, 
如果内存不足,但是end_free – start-free的值仍然大于size,即可以提供一个以上的区块,就提供这不足20的区块出去,这时候pass by reference 的nobjs参数将被修改为实际供应的区块个数。

3, 
如果剩余内存不足提供一个区块,则调用malloc从heap中分配内存给内存池。

  a) 如果heap足够,则分配20*2+n(n为附加量,随着分配次数的增加而增加)的内存块给内存池,其中第一个给用户,19个给free list维护,剩余的20+n个给内存池维护。

  b) 如果heap也没了,malloc失败,chunk alloc()就搜寻整儿free list看是否有“尚未利用的区块,且区块足够大”,如果有则分配给用户。

  c) 如果没搜寻到,则调用第一级空间配置器。第一级空间配置器也采用的是malloc,但是第一级空间配置器有out of memory处理机制(类似new handler处理机制),或许有机会释放出内存,如果可以就成功,否则抛出bad_alloc异常。

内存释放策略

如果释放的内存超过128字节,则调用“简单空间配置器”的内存释放函数。否则,找出对应的free list,将区块收回。