mu建站工具,wordpress 文章美化,重庆百度搜索优化,wordpress账号密码前言 空间配置器#xff0c;顾名思义就是为了各个容器高效的管理空间#xff08;空间的申请与回收#xff09;的#xff0c;在默默的工作的。虽然在常规上使用STL时#xff0c;可能用不上它#xff0c;但是站在学习研究的角度#xff0c;学习它的实现原理对我们有很大的…前言 空间配置器顾名思义就是为了各个容器高效的管理空间空间的申请与回收的在默默的工作的。虽然在常规上使用STL时可能用不上它但是站在学习研究的角度学习它的实现原理对我们有很大的帮助。
目录
1.为什么需要空间配置器
2.SGI—STL空间配置器实现原理
3.一级空间配置器实现原理 3.1 一级空间配置器 3.2 二级空间配置器 3.2.1内存池 3.2.2 SGI-STL中二级空间配置器设计 3.3 SGI-STL二级空间配置器之空间申请 3.3.1前期的准备 3.3.2申请空间 3.3.2.1填充内存块 3.3.2.2向内存池中索要空间 3.3.3空间的回收 3.4 空间配置器的默认选择 3.5 空间配置器的再次封装 3.6 对象的构造和释放 1.为什么需要空间配置器 new申请的空间虽然可以使用但是有以下不足之处 1.空间申请与释放需要用户自己管理容易造成内存泄露 2.频繁向系统申请小块内存块容易造成内存碎片 3.频繁向系统系统申请小块内存影响程序运行效率 4.直接使用malloc和new进行申请每块空间前有额外空间浪费 5.申请失败如何应对 6.代码结构比较混乱代码复用率不高 7.未考虑线程安全问题 由于存在这些问题因此需要一块高效的的内存管理机制。
2.SGI—STL空间配置器实现原理 频繁的向系统申请小块内存会有很多的问题那么怎么样的内存算是小块内存呢 SGI-STL以128作为大内存和小内存的分界线将空间配置器分为两级结构一级空间配置器处理大块内存二级空间配置器处理小块内存。
3.一级空间配置器实现原理 3.1 一级空间配置器 一级空间配置器的原理非常简单直接对malloc和free进行了封装并增加了C中set_new_handle思想。
namespace qyy
{template int instclass __malloc_alloc_template{private:static void* oom_malloc(size_t);public://对malloc进行封装static void* allocate(size_t n){//申请空间成功直接返回失败了交给oom_malloc处理void* result malloc(n);if (result 0){result oom_malloc(n);}return result;}//对free进行封装static void* deallocate(void* p, size_t){free(p);}//模拟实现set_malloc_handler//该函数参数为函数指针返回值也是函数指针//void(*set_malloc_handler(void*(f*)( ) )) ()static void (*set_malloc_hander(void (*f)()))(){void (*old)() __malloc_alloc_oom_handler;__malloc_alloc_oom_handler f;return (old);}};//malloc空间申请失败时调用该函数templateint instvoid* __malloc_alloc_templateinst::oom_malloc(size_t){void(*my_malloc_handler)();void* result;for (;;){//检测用户是否设置空间不足应对措施如果没有设置抛异常模拟new的方式my_malloc_handler __malloc_alloc_handler;if (0 my_malloc_handler){__THROW_BAD_ALLOC;}//如果设置了执行用户提供空间不足应对措施(*my_malloc_handler)();//继续申请空间可能就会成功result malloc(n);if (result)return (result);}}typedef __malloc_alloc_template0 malloc_alloc;} 3.2 二级空间配置器 二级空间配置器是专门负责处理小于128字节的小块空间。如何才能提升小块内存的的申请和释放的方式呢SGI-STL采用了内存池的技术来提高申请空间的速度以及减少额外的空间的浪费采用哈希桶的方式来提高用户获取空间的速度与高效管理。 3.2.1内存池 内存池就是先申请一块比较大的内存当做备用当需要内存时直接去内存池中拿内存就好了当内存池中的空间不够时再向内存中取当用户不用时直接还回内存池即可。避免了频繁的向系统申请小块内存所造成的效率低内存碎片以及额外浪费的问题。 3.2.2 SGI-STL中二级空间配置器设计 SGI-STL中的二级空间配置器使用了内存池技术但是没有采用链表的方式对用户已归还的空间进行管理因为用户申请空间时是在查找合适的小块内存时效率较低而采取哈系桶的方式进行管理。那么是否128个桶来管理已归还的空间呢答案是不需要的因为用户申请空间基本上都是按照4的整数倍来申请的其他大小的空间基本很少用到因此SGI-STL将用户申请的内存块向上对其到了8的整数倍。 3.3 SGI-STL二级空间配置器之空间申请 3.3.1前期的准备
namespace qyy
{templateint instclass __default_alloc_template{private:enum {__ALIGN 8};//如果用户需要的内存不是8的整数倍向上对其到8的整数倍enum {__MAX_BYTES 128};//大小块内存的分界线enum { __NFREELISTS __MAX_BYTES / __ALIGN };//采用哈希桶保存小块内存时所需要的内存个数static size_t ROUND_UP(size_t bytes){return (((bytes)__ALIGN - 1) ~(ALIGN - 1));}private://用联合图来维护链表结构union obj{union obj* free_list_link;char client_data[1];};private:static obj* free_list[__NFREELISTS];//哈希函数根据用户提供的字节数找到对应的桶号static size_t FREELIST_INDEX(size_t bytes){return (((bytes)__ALIGN - 1) / ALING - 1);}//start_free 和end_free用来标记内存池中大块内存的起始和末尾位置static char* start_free;static char* end_free;//用来记录该空间配置器已经向系统索要了多少的块内存static size_t heap_size;///...};
} 3.3.2申请空间 //函数功能向空间配置器索要空间//参数n所需要的空间字节数//返回值返回空间的首地址static void* allocate(size_t n){obj* __VOLATILE* my_free_list;obj* __RESTRICT result;//检测用户所需要的空间是否在超过128字节(即是否为小块内存if (n (size_t)__MAX_BYTES){//不是小块内存交给一级空间配置器来处理return (malloc_alloc::allocate(n));}//根据用户所需要的字节找到对应的桶号my_free_list free_list FREELIST_INDEX(n);result *my_free_list;//如果桶里面没有内存块向桶里面补充内存块if (result 0){//n将向上对齐到8的整数倍,保证向桶里面补充内存块时内存块一定是8的整数倍void* r refill(ROUND_UP(n));return r;}//维护桶里面剩余内存块的链式关系*my_free_list result-free_lsit_link;return (result);} 3.3.2.1填充内存块 //函数功能向哈系桶里面补充空间//参数n小块内存//首个小块内存的首地址templateint instvoid* __default_alloc_templateinst::refill(size_t n){//一次性向内存池索要20个n字节的空间int nobjs 20;char* chunk chunk_alloc(n, nobjs);obj** my_free_list;obj* result;obj* current_obj, * next_obj;int i;//如果只有一块直接返回给用户if (1 nobjs)return (chunk);//找到对应的桶号my_free_list free_list FREELIST_INDEX(n);//将第一块返回给用户去其他的挂到哈系桶中result (obj*)chunk;*my_free_list next_obj (obj*)(chunk n);for (i 1;;i){current_obj next_obj;next_obj (obj*)((char*)next_obj n);if (nobjs - 1 i){current_obj-free_list_link 0;break;}else{current_obj-free_list_link next_obj;}}return (result);} 3.3.2.2向内存池中索要空间 templateint instchar* __default_alloc_tempalteinst::chunk_alloc(size_t size, int nobjs){//计算nobjs个size字节内存块的总大小以及内存池中剩余空间的总大小char* result;size_t total_bytes size * nobjs;size_t bytes_left end_free - start_free;//如果内存池可以提供total_bytes字节返回if (bytes_left tatal_bytes){result start_free;start_free tatal_bytes;return (result);}else if (bytes_left size){//nobjs块无法提供但是至少可以提供1块size字节的内存块提供后返回nobjs bytes_left / size;tatal_byte size * nobjs;result start_free;start_free tatal_bytes;return (result);}else{//内存池空间不够连一小块内存都没有。//向系统堆求助往内存池中补充空间//计算向内存中补充空间的大小本次空间总大小的两倍 向系统申请总大小/16size_t bytes_to_get 2 * tatal_byte ROUND_UP(heap_size 4);//如果内存池有剩余空间该空间一定是8的整数倍将该空间挂到对应的哈希桶中if (bytes_left 0){//找到对应的哈系桶obj** my_free_list free_list FREELIST_INDEX(bytes_left);((obj*)start_free)-free_list_link *my_free_list; )* my_ree_list (obj*)start_free;}//通过系统堆向内存池补充空间如果补充成功递归继续分配start_free (char*)malloc(bytes_to_get);if (0 start_free){//通过系统堆补充失败在哈系桶中寻找是否有没有使用的较大块内存int i;obj** my_free_list, * p;for (i size; i __MAX_BYTES;i __ALIGN){my_free_list free_list FREELIST_INDEX(i);p *my_free_list;//如果有将该内存块补充进内存池递归继续分配if (0 ! p){*my_free_list p-free_list_link;start_free (char*)p;end_free start_free i;return (chunk_alloc(size, nobjs));}}//山穷水尽只能向一级空间配置器求助//注意此处一定要将end_free置空因为一级空间配置器一旦抛异常就会出问题end_free 0;start_free (char*)malloc_alloc::allocate(bytes_to_get);}heap_size bytes_to_get;end_free start_free bytes_to_get;return (chunk_alloc(size, nobjs));}} 3.3.3空间的回收 //函数功能用户将空间归还给空间配置器//参数p空间首地址 n空间总大小static void deallocate(void* p, size_t n){obj* q (obj*)p;obj** my_free_list;if (n (size_t)__MAX_BYTES){malloc_alloc::deallocate(p, n);return;}//找到对应的哈系桶将内存挂到哈系桶中my_free_listfree_list FREELIST_INDEX(n);q-free_list_link *my_free_list;*my_free_list q;} 3.4 空间配置器的默认选择 SIG_STL默认使用一级空间配置器 还是二级空间配置器是通过宏开关USE_MALLOC宏进行控制的。 在SGI_STL中没有定义这个宏所以默认情况下SGI_STL使用二级空间配置器。 3.5 空间配置器的再次封装 在C中用户所需要的空间可能是任意类型的有单个对象的空间有连续空间每一次都让用户自己计算空间的总大小不是很友好因此SGI_STL将空间配置器重新封装了一层。
templateclass T,class ALLOCclass simlpe_alloc{public://申请n个T类型对象大小的空间static T* allocate(size_t n){return 0 n ? 0 : (T*)ALLOC::allocte(n * sizeof(T));}//申请一个T类型对象大小的空间static T* allocate(void){return (T*)ALLOC::allocate(sizeof(T));}//释放n个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));} 3.6 对象的构造和释放 因为效率的需要SGI_STL决定将空间的申请和释放和对象的构造析构两个过程分离因为有些对象的构造不需要调用构造函数销毁时不需要调用析构函数将该过程分离可以提高程序的性能。 //归还空间时先调用析构函数进行资源的清理template class Tinline void destory(T* pointer){pointer-~T();}//空间申请好后调用该函数利用placement-new完成对对象的构造templateclass T1,class T2inline void construct(T1* p, const T2 value){new(p)T1(value);} 注意在释放对象时需要根据对象的类型来确定是否需要调用析构函数类型萃取 对象的类型可以通过迭代器萃取到。 这些内容难度较大作为了解就可以了。对于初学者来说
