目录 问题 SGI版本空间配置器—std::alloc 一级空间配置器 二级空间配置器 Refill、chunkAlloc函数 最后，配置器封装的simple_alloc接口 问题 我们在日常编写C++程序时，常常会用到我们的STL标准库来帮助我们解决问题，这当中我们用得最多估计就是它里面的vector、list容器了，它们带来的便利不用多说（毕竟OJ、刷题什么的，基本全是它们的身影），而在日常学习中我们对STL中另一大组件—空间配置器 了解可能就相对较少了。不过它也是个有用的东西，之所以这么说，主要就在于它解决了在内存分配过程中出现的内存碎片问题，具体就是 如上，对于一块从堆上分配的内存，由于对该块内存的释放通常是不确定的，因为取决于用户，对于刚释放完的那32字节，虽归还给了os，但由于中间都是碎片化的内存，所以此时想利用那32字节再从os申请20字节内存便无法完成。 而在多线程环境下，这种内存碎片问题带来的影响就更大了，多个线程频繁的进行内存申请和释放，同时申请、释放的内存块有大有小；程序执行过程当中这些碎片的内存就有可能间接造成内存浪费，再一个os要对这样频繁的操作管理，势必会影响到它的效率。 SGI版本空间配置器—std::alloc STL中配置器总是隐藏在一切组间（具体说是，container）的背后，默默工作。但站在STL实现角度看，我们第一个需要搞清楚的就是空间配置器，因为我们操作所有STL对象基本都会存放容器当中，而容器一定需要配置空间来置放资料的，不弄清它的原理，定会影响以后对STL的深入学习。 而在SGI STL中，std::alloc 为默认的空间配置器： vector iv 是的，它的写法好像并不是标准的写法（标准写法应该是allocator），而且它也不接受参数，但这并不会给我们带来困扰，因为它是默认的，很少需要我们自行指定配置器名称。（至于为什么不用allocator这个更标准的写法，这源于它的效率问题。具体可以参考STL源码剖析），今天主要来看看alloc版本配置器实现原理，加深自己关于空间分配的理解。 配置器要完成的其实就是对象构造前的空间配置和对象析构后的空间释放。参考SGI中做法配置器对此设计要考虑： 向系统堆空间获取空间 考虑多线程状态 考虑内存不足时的应对措施 考虑过多“小型区块” 可能带来的内存碎片问题 基于此，alloc实现中设计了双层级配置器模型。一级配置器直接使用malloc和free，二级配置器则视情况采取不同的策略，具体来讲就是：当需求的内存块超过128字节时，就将其视为大块内存需求，便直接调用一级配置器来分配；当需要内存块< 128字节，便交由二级配置器来管理（这当中可能还联合一级配置器一起使用，具体原因在后面）。 一级空间配置器 首先，一级配置器STL默认名通常是__malloc_alloc_template<0>.在STL实现中将它typedef为了alloc。然后 要注意的是源于__USE_MALLOC通常未定义，它在STL中并不是默认的配置器。 一级配置器模拟实现： #pragma once #include #include using namespace std; //一级空间配置器 typedef void(*HANDLE_FUNC)(); template // inst为预留参数，方便以后扩展 class __MallocAllocTemplate { private: /*定义函数指针类型成员，方便回调执行用户 自定义的内存释放函数，该成员默认设置不执行*/ static HANDLE_FUNC __malloc_alloc_oom_handler; static void* OOM_Malloc(size_t n){ while (1){ if (0 == __malloc_alloc_oom_handler){ throw bad_alloc(); }else{ __malloc_alloc_oom_handler(); //释放内存 Sleep(200); void* ret = malloc(n); if (ret) return ret; } } } public: static void* Allocate(size_t n){ void *result = malloc(n); //malloc申请失败，执行OOM_Malloc再请求申请内存 if (0 == result) result = OOM_Malloc(n); cout<<"申请成功!"< HANDLE_FUNC __MallocAllocTemplate::__malloc_alloc_oom_handler = 0; //自定义的内存释放函数 static void FreeMemory(){ cout<<"执行用户自定义函数，开始释放内存..."< class __DefaultAllocTemplate { public: // 65 72 -> index=8 // 72 79 static size_t FREELIST_INDEX(size_t n){ return ((n + __ALIGN-1)/__ALIGN - 1); } // 65 72 -> 72 // 72 79 static size_t ROUND_UP(size_t bytes) { return (((bytes) + __ALIGN-1) & ~(__ALIGN - 1)); } static void* ChunkAlloc(size_t size, size_t& nobjs);//获取大块内存 static void* Refill(size_t bytes); //填充自由链表 static void* Allocate(size_t n); //分配返回小内存块 static void Deallocate(void* p, size_t n); //管理回收内存 private: enum {__ALIGN = 8 }; enum {__MAX_BYTES = 128 }; enum {__NFREELISTS = __MAX_BYTES/__ALIGN }; union Obj{ union Obj* _freelistlink; char client_data[1]; /* The client sees this. 用来调试用的*/ }; // 自由链表 static Obj* _freelist[__NFREELISTS]; // 内存池 static char* _startfree; static char* _endfree; static size_t _heapsize; }; //__DefaultAllocTemplate成员初始化 template typename __DefaultAllocTemplate::Obj* __DefaultAllocTemplate::_freelist[__NFREELISTS] = {0}; // 内存池 template char* __DefaultAllocTemplate::_startfree = NULL; template char* __DefaultAllocTemplate::_endfree = NULL; template size_t __DefaultAllocTemplate::_heapsize = 0; Refill、chunkAlloc函数 前面说了，当我们需求的内存块在所对自由链表的下标处没挂有内存块时，我们就必须调用refill去填充自由链表了。申请时一般一次性申请20个内存块大小的内存（可参加STL实现源码）。 那又从那里找呢？——当然内存池啦！分配这么大块内存到二级配置器就是现在来用的。可以通过移动startFree指针快速地从内存池内给“切割”出来这一段内存，然后按照大小切成小块挂在自由链表下面。在这个过程中可以直接将第一小块内存块返回给用户，其余的再挂在自由链表下，方便下次分配了。 基于这样思路就可以将refill实现如下： void* __DefaultAllocTemplate::Refill(size_t bytes) { size_t nobjs = 20; /*默认从内存池取20块对象，填充*/ //从内存池中拿到一大块内存 char* chunk = (char*)ChunkAlloc(bytes, nobjs); if (nobjs == 1) /*只取到了一块*/ return chunk; size_t index = FREELIST_INDEX(bytes); printf("返回一个对象，将剩余%u个对象挂到freelist[%u]下面\n", nobjs-1, index); Obj* cur = (Obj*)(chunk + bytes); _freelist[index] = cur; for (size_t i = 0; i < nobjs-2; ++i){ Obj* next = (Obj*)((char*)cur + bytes); cur->_freelistlink = next; cur = next; } cur->_freelistlink = NULL; return chunk; } 注：chunkAlloc向内存池索要内存 考虑一个问题 到此，我们好像就会有一个疑问。既然简单移动startfree就可以欢快的从内存池取到得一块内存返回，那为什么又要一次性取20块，返回一块，将剩下那19块挂到freelist对应位置下面呢？挨个挂上去还这么麻烦！每次都直接从内存池返回一块内存不是更欢快吗？在这里当然不用担心出现外碎片问题。因为在每次内存释放时，可以添加到我们维护的自由链表上，继续下次分配。 而在这里，其实是考虑了高并发的情况：这种的并发情况下，当从内存池取的一块需要的内存，无疑会有多个线程同时来操作，startfree执行加法返回一块内存也不是原子操作，所以在此必然就会涉及加锁解锁，同时这些线程取得内存块大小也不统一，所有这么多的线程必然会因为这里的锁而影响执行速度，影响效率。 一次性取上20块就能缓解这种状况，当多个线程要取的内存块不一样时，此时便不会锁住，因为是从不同链表上取；此时，锁只会锁在多个线程从同一个链表上取一块相同大小内存上。 虽然从内存池取一段内存操作也涉及着加锁，但由于调用Refill填充自由链表次数相对会少很多，所以上面这样一次性取20块做法是可以提高高并发下程序执行效率。 接下来就是chuncAlloc函数 它表示从内存池那一大块内存，同时也尽可能保证内存池像水池一样有时刻有“水”。具体它遵循4条方针: 内存池内存够多，直接“大方的”返回 内存池内存有些吃紧了，尽量返回调用方需求的内存 内存池“穷得吃土”了，需要求助os来malloc来为它补充“源头活水” os也“吃土”了，内存池“灵机一动”，打上了后面自由链表的主意。 都一无所获，内存池最后一搏，调用一级配置器 到最后一级配置器基于它的out-of-memory处理机制，或许有机会释放去其它的内存，然后拿来此处使用。如果可以那就成功“帮助”内存池，否则便发出bad_alloc异常通知使用者。 基于这样的思路，便可以模拟实现出ChunkAlloc函数 //function：从内存池申请一大块内存 template void* __DefaultAllocTemplate::ChunkAlloc(size_t size, size_t& nobjs) { size_t totalbytes = nobjs*size; size_t leftbytes = _endfree - _startfree; //a) 内存池中有足够内存 if (leftbytes >= totalbytes){ printf("内存池有足够%u个对象的内存块\n", nobjs); void* ret = _startfree; _startfree += totalbytes; return ret; //b) 内存池仅剩部分对象内存块 }else if (leftbytes > size){ nobjs = leftbytes/size; /*保存能够使用对象块数*/ totalbytes = size*nobjs; printf("内存池只有%u个对象的内存块\n", nobjs); void* ret = _startfree; _startfree += totalbytes; return ret; //c) 内存池中剩余内存不足一个对象块大小 }else{ // 1.先处理掉内存池剩余的小块内存，将其头插到对应自由链表上 if(leftbytes > 0){ size_t index = FREELIST_INDEX(leftbytes); ((Obj*)_startfree)->_freelistlink = _freelist[index]; _freelist[index] = (Obj*)_startfree; } // 2.调用malloc申请更大的一块内存放入内存池 size_t bytesToGet = totalbytes*2 + ROUND_UP(_heapsize>>4); _startfree = (char*)malloc(bytesToGet); printf("内存池没有内存，到系统申请%ubytes\n", bytesToGet); if (_startfree == NULL){ //3. malloc申请内存失败，内存池没有内存补给，到更大的自由链表中找 size_t index = FREELIST_INDEX(size); for (; index < __NFREELISTS; ++index){ //自由链表拿出一块放到内存池 if (_freelist[index]){ _startfree = (char*)_freelist[index]; //BUG ?? Obj* obj = _freelist[index]; _freelist[index] = obj->_freelistlink; return ChunkAlloc(size, nobjs); } } _endfree = NULL; /*in case of exception. ！！保证异常安全*/ //逼上梁山，最后一搏. 若内存实在吃紧，则一级配置器看看out-of-memory能否尽点力，不行就抛异常通知用户 _startfree = (char*)__MallocAllocTemplate<0>::Allocate(bytesToGet); } _heapsize += bytesToGet; _endfree = _startfree + bytesToGet; //递归调用自己，为了修正nobjs return ChunkAlloc(size, nobjs); } } 这里也还要注意一个点：就是_endfree= NULL这样一个操作 这句话很容易被我们忽略掉。这其实是十分重要的一个操作，这关乎到异常安全问题，在内存池穷山尽水之时，它取调用了一级配置器，希望一级配置器能否释放一些内存，在chunkAlloc内可以malloc成功，但通常这都是失败的，所以一级配置器便抛出了异常，然而异常抛出并不意味着程序结束，此时的endfree并不为NULL并且可能是较大的数，（endfree保持以前的值）此时的startfree指针是为NULL的。这两者的差值表示着内存池有着大块的内存，然而这已不属于内存池了。 整理一下配置器分配的流程 最后，配置器封装的simple_alloc接口 无论alloc被定义为第一级或第二级配置器，SGI还为它包装了一个接口Simple_alloc，使配置器接口符合STL规格： #ifdef __USE_MALLOC typedef __MallocAllocTemplate<0> alloc; #else typedef __DefaultAllocTemplate alloc; #endif template class SimpleAlloc { public: static T* Allocate(size_t n){ return 0 == n? 0 : (T*) Alloc::Allocate(n * sizeof (T)); } static T* Allocate(void){ return (T*) Alloc::Allocate(sizeof (T)); } static void Deallocate(T *p, size_t n){ if (0 != n) Alloc::Deallocate(p, n * sizeof (T)); } static void Deallocate(T *p){ Alloc::Deallocate(p, sizeof (T)); } }; 这里面内部四个成员函数其实都是单纯的转调用，调用传递给配置器的成员函数，这个接口时配置器的配置单位从bytes转为了个别元素的大小。SGI STL中容器全部使用simple_alloc接口，例如 template< class T, class Alloc= alloc> class vector{ protected: //专属空间配置器，每次配置一个元素大小 typedef simple_alloc data_allocator; void deallocate(){ if(...) data_allocator::deallocate(start, end_of_storage- start); } ... }; 为了将问题控制在一定复杂度内，到此以上的这些，仅仅处理了单线程的情况。对于并发的情况，它的处理过程会相对更复杂。我们可以查看STL中空间配置器的源码实现来进一步的学习，这当中又会体现出很多优秀的思想， 例如，在对chunk_alloc的操作加锁时，就采用了类似“智能指针”的机理。因为在多线程的情况下，在chunk_alloc分配内存时，可能会因为某个线程因异常终止而没有进行解锁的操作，进而使得其他线程阻塞，造成死锁问题，影响程序的执行。 STL中在这里加锁，用的是一个封装lock类对象，当这个对象出了作用域就会自动析构，实现解锁操作，保证了线程安全问题。 而这就是RAII（资源获得即初始化）思想的一种具体体现。 STL配置器还有许多其它优秀设计，这里只是本人对它的部分认识。为了加深理解，我们可以查看STL中源码进行更深入学习。 模拟整体实现：https://github.com/tp16b/project/tree/master/alloc/srchttps://www.cnblogs.com/tp-16b/p/9520226.html