青岛市黄岛区城市建设局网站,企业网站建设单位,wordpress995,办公室隔断目录
1.什么是空间配置器
2.为什么需要空间配置器
3.SGI-STL空间配置器实现原理
3.1一级空间配置器
3.2二级空间配置器
3.2.1内存池
3.2.2 SGI-STL中二级空间配置器设计
3.3 空间配置器的默认选择
4.空间配置器与容器的结合 1.什么是空间配置器
空间配置器#xff0…目录
1.什么是空间配置器
2.为什么需要空间配置器
3.SGI-STL空间配置器实现原理
3.1一级空间配置器
3.2二级空间配置器
3.2.1内存池
3.2.2 SGI-STL中二级空间配置器设计
3.3 空间配置器的默认选择
4.空间配置器与容器的结合 1.什么是空间配置器
空间配置器顾名思义就是为各个容器高效的管理空间(空间的申请与回收)的配置器在默默地工作。下图是空间配置器、malloc的关系图 空间配置器相当于是小灶malloc是大食堂。空间配置器会为各个容器管理内存空间即各个容器不需要去malloc那里拿内存空间。
2. 为什么需要空间配置器
在前面的博文中我写了vector、list等等的容器的实现在需要空间的地方都是通过new申请的虽然在代码完成之后代码可以正常运行但是对于其中的内存空间有以下不足 ①空间申请与释放需要用户自己管理容易造成内存泄漏。 ②频繁向系统申请小块内存块容易造成内存碎片。 ③频繁向系统申请小块内存影响程序运行效率。 ④直接使用malloc与new进行申请每块空间前有额外空间浪费。 ⑤申请空间失败怎么应对。 ⑥代码结构比较混乱代码复用率不高。 ⑦未考虑线程安全问题。 对于这些问题C为容器设计了一块高效的内存管理机制----空间配置器。
3.SGI-STL空间配置器的实现原理
以上提到的几点不足之处最主要还是频繁向系统申请小块内存造成的。那什么才算是小块内 存SGI-STL以128字节作为小块内存与大块内存的分界线将空间配置器其分为两级结构一级空间配置器处理大块内存二级空间配置器处理小块内存。即申请的空间大小大于128字节那么就使用一级空间配置器小于等于128字节就使用二级空间配置器。 3.1一级空间配置器
一级空间配置器原理非常简单直接对malloc与free进行了封装并增加了C中set_new_handle思想。一级空间配置器在申请空间的时候如果失败了会直接抛异常。
template int inst
class __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 (0 result)result oom_malloc(n);return result;}// 对free的封装static void deallocate(void* p, size_t /* n */){free(p);}// 模拟set_new_handle// 该函数的参数为函数指针返回值类型也为函数指针// void (* set_malloc_handler( void (*f)() ) )()static void (*set_malloc_handler(void (*f)()))(){void (*old)() __malloc_alloc_oom_handler;__malloc_alloc_oom_handler f;return(old);}
};
// malloc申请空间失败时代用该函数
template int inst
void* __malloc_alloc_templateinst::oom_malloc(size_t n)
{void (*my_malloc_handler)();void* result;for (;;){// 检测用户是否设置空间不足应对措施如果没有设置抛异常模式new的方式my_malloc_handler __malloc_alloc_oom_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内存池
内存池就是先申请一块比较大的内存块已做备用当需要内存时直接到内存池中去去当池中空间不够时再向内存中去取当用户不用时直接还回内存池即可。避免了频繁向系统申请小块内存所造成的效率低、内存碎片以及额外浪费的问题。 在源码中是由两个指针指向一块空间这块空间便是内存池它是二级配置器向malloc申请出来的。
3.2.2 SGI-STL中二级空间配置器设计
SGI-STL中的二级空间配置器使用了内存池技术并且为了更方便更好的管理内存二级空间配置器采用了哈希桶的方式。具体流程是这样的
当需要申请128字节以内的内存的时候二级空间配置器就会从内存池中拿到若干块内存这个内存的大小为8的整数倍。然后分配给需要的地方当使用完后归还内存并不是直接归还到内存池中而是使用哈希桶将内存块链接起来方便后续的使用
举个例子我申请12字节大小的空间若干个那么二级配置器就会从哈希桶中拿过来但是如果此时的哈希桶是空的那么就会去内存池中申请如果内存池也是空的内存池会去malloc申请一大块然后内存池截取诺干个16个字节的内存块分配给用户剩下的若干个链接到哈希桶中因为内存池一般会截取几个内存块出来。
然后当用户使用完后就会将这些内存块重新链接到哈希桶中。 那么为什么内存块都是8的整数倍呢
当内存池已经空了但是我需要申请一块空间大小为16字节的。但是在哈希桶中没有16字节的内存块但是内存池已经空了此时二级空间配置器不会放弃任何给你内存的希望它会从后面的空闲着的内存块截取16字节拿过来然剩下的字节的内存块也会被链接到前面对应字节数的桶中。
比如我需要16字节但是发现哈希桶里没有于是我拿24字节的截取了16字节还剩下8字节这八字节就会被链接在8字节的桶中这就是为什么要8的整数倍因为可以在内存池空了的情况下通过截取更大字节的内存块来分配给需要较小字节内存块的用户然后可以将剩下的字节内存块链接去更小的桶中。
3.3 空间配置器的默认选择
GI-STL默认使用一级还是二级空间配置器通过USE_MALLOC宏进行控制
#ifdef __USE_MALLOC
typedef malloc_alloc alloc;
typedef malloc_alloc single_client_alloc;
#else// 二级空间配置器定义
#endif
在SGI_STL中该宏没有定义因此默认情况下SGI_STL使用二级空间配置器。
4.与容器结合
使用list作为例子看下面代码
//typedef __default_alloc_template__NODE_ALLOCTOR_THREADS, 0 alloc;
template class T, class Alloc alloc
class list
{// ...// 实例化空间配置器typedef simple_alloclist_node, Alloc list_node_allocator;// ...
protected:link_type get_node(){// 调用空间配置器接口先申请节点的空间return list_node_allocator::allocate();}// 将节点归还给空间配置器void put_node(link_type p){list_node_allocator::deallocate(p);}// 创建节点1. 申请空间 2. 完成节点构造link_type create_node(const T x){link_type p get_node();construct(p-data, x);return p;}// 销毁节点 1. 调用析构函数清理节点中资源 2. 将节点空间归还给空间配置器void destroy_node(link_type p){destroy(p-data);put_node(p);}// ...iterator insert(iterator position, const T x){link_type tmp create_node(x);tmp-next position.node;tmp-prev position.node-prev;(link_type(position.node-prev))-next tmp;position.node-prev tmp;return tmp;}iterator erase(iterator position){link_type next_node link_type(position.node-next);link_type prev_node link_type(position.node-prev);prev_node-next next_node;next_node-prev prev_node;destroy_node(position.node);return iterator(next_node);}// ...
};
