软件工程:STL设计思想之内存管理

 　open source是一个不错的单词,发音很不错,念起来很上口.而且简写操作系统OS(operation system),呵呵,有点歪打正着的感觉,其实open source是和OS一样cool的一个单词.
　　最近开始研究STL,当然还只是很初步,看过了allocator,uninitialzed,config也算吧,这是一个open source软件,不过不是GPL软件,GPL是open source的鼻祖,open source是GPL的发扬光大.
　　allocator看的是SGI的版本,应用了两级内存分配,其中默认情况下以内存池(memory pool)策略解决内存碎片(fragment)问题,不过内存池(memory pool)在我看来只是众多软件者的一个终极梦想.
　　下面就对allocator的理解说下它的问题.读SGI STL代码是通过侯捷先生的加上SGI STL code进行的.
　　SGI STL(一下简称SGI),的SGI的分配器(allocator)在文件stl_alloc.h中定义,内部定义了4个类:
　　1.template class __malloc_alloc_template:底层应用c的malloc实现,同时定义了应对内存告罄的处理办法,使用了一个句柄 (handler),及时模仿标准new里面的set_new_handler让客户端(client)自己来处理内存不足的问题.template class simple_alloc:这是一个外部接口,只是进行了简单的封装template class debug_alloc:这也是一个外部接口,只是进行了简单的封装template class __default__alloc_template:从名字上也知道这就是默认的allocator.通过定义__USE_MALLOC来设置其为默认.这个类也是应用了momory pool策略的.
　　memory pool在解决内存碎片(fragment),节约内存方面有突出贡献,这个对于C++程序员来说有着巨大的吸引力,C++一直是秉承着高效的运行效率而 著称的,可以像C一样直接操纵内存,通过伟大的malloc CRT(C Runtime Liberary)函数.直接操纵内存,如果通过单步调试,就可以看到malloc底层是通过汇编代码来执行的.不远扯了,说下SGI的memory pool策略.
　　内存池(memory pool)的最大问题是客户端(client),所需要的内存大小是不一样的,比如客户端(client)或许需要4个字节,或许需要17个字节,这些都 是不可预知的,如果上面的两个对象都要放到内存池中,内存就要负责维护这两个对象的大小(size_t),以方面在删除的时候使用,但是内存池的设计初衷 就是要节省空间,如何维护这个size_呢?那么我定义两个列表,非别维护4个字节的对象和17个字节的对象,这样同一个列表的对象就可以共享这个 size_t了,但是问题是如果客户端(client)还需要一个8个字节的对象呢?再来一个存放8个字节的列表?如果还需要9个字节呢?似乎这个方法是 行不通的.
　　SGI的方法是将其整话,SGI的内存池有16个列表,非别维护8、16、24--128个字节的对象，当用户需要调用 allocator的时候，我将用户所需要的size_t上调为8的整数倍.这样我只要16个列表就可以解决用户1~128个字节的内存需求了.而且用户 的对象通常是8的倍数的,或者说概论比较大,另一个方面每个列表事先存放好了20个本列表规定大小的内存块(SGI将其作为char*存储).
　　同时SGI的内存池遵循的策略是有需求的时候才初始化本列表,如果用户从来没有使用过128字节的对象,那么SGI的内存池内就不会有相应的列表,或者说相应的相应的列表为空.
　　上面用文字说明了下SGI的策略,下面从code的角度出发.
　　一 个标准STL的alloctor应该有接口有:allocate,deallocate,construce,deconstruce.SGI的 simple没有符合标准STL,没有construct,deconstruct.SGI只有他们的全局静态版本.而且,SGI的 __default_alloc_template和__malloc_alloc_template不光接口不一样,类型也与标准STL不一致,他们不 需要客户端(client)的型别参数,既是其template class具体化的时候不需要调用者的型别,只需要size_t,似乎不错,我们可以轻松点,不过他的simple_alloc包装的时候,有加上了这个 而外的型别需求,绕来绕去总是逃不了该做的事情...哎~~~~~~
　　SGI的allocator首先接受用户所需要的size_t,然后 调用allocate(其实是客户端这么写objalloc.allocate(n);),allocate向 freelist(__defalut_malloc_template的一个数据成员,型别为一个obj* volalite freelist[16],既是存储这16个列表的那个家伙),如果freelist没有内存(或者说它是空的,为初始化)那么调用 refill,refill从真正的SIG memory pool中取内存,取出做多20个客户端所需要的size_t大小的内存块,通过chunk_alloc,取出来后将其妆扮好(就是想这20块内存连接为 一个链表),上交给allocate享用.真正的劳动人民是chunk_alloc,为了表彰其奉献精神,我将其大名共只余下:
　　template 
　　char* 
　　__default_alloc_template::_S_chunk_alloc(size_t __size, 
　　int& __nobjs)
　　默 认情况下__nobjs实参为20,而且是一个地址传递(引用传递).他做的工作可是相当相当的伟大.原始社会的时候,一切资源都相当的丰富(原始人从来 不担心石油危机),chunk_alloc从内存里面取出20块size_t大小的内存上交给refill,refill将其装配后,上交 freelist,allocate从freelist中取出一块上交给我(^_^),其实是我想allocate要内存,结果没有,allocate想 refill要内存,refill马上把chunk_alloc找来,于是内存有了.
　　当然内存要节约使用,第一次我想要一个32字节的内 存,chunk_alloc找来了2*20*32个字节的内存,其中的20块上交给了refill,refill填充 freelist,freelist存储其中19个,上交给客户端(我)一个.下一次我要一个8字节的内存,chunk_alloc又要找内存了, 不过上次找来的内存还没有用完(上次交了20*24,剩余20*24,也就是剩余480字节),而且足够上交refill的了(需要8*20=160), 他们我上交给他所需要的内存,不从系统堆(heap)里面取用内存(只有chunk_alloc这样的劳动人民知道花钱小心翼翼).这样美好的日子一直持 续着,突然有一天,chunk_alloc发现系统内存重要用完了,怎么办?怎么向refill交差?refill一再压迫 chunk_alloc.chunk_alloc于是去找freelist,freelist内部存储上尚未陪客户端(client)取走的内存,比如 freelist,中还有10块没有用完,也就是说有160个字节的内存,那么chunk_alloc看看内不能满足refill的最小需求(1块 size_t),然后毫无保留的上交上去.如果连freelist都没有内存了,chunk_alloc于是向同门兄弟 __malloc_default_alloc求助(调用它的allocate),再那里有内存不足的处理情况,或许就要std::bad_alloc 了!
　　诚实的讲SGI的策略已经是异常的完美了,但是作为一个STL,只能是最完美的,其中还是存在一些不足,因为一个完美的memory_pool实在是很有难度的!