湖南现在有什么网站做农副产品,济南网站优化分析,网站设计评价指标,WordPress 手机编辑空间配置器
1.什么是空间配置器
为各个容器高效的管理空间(空间的申请与回收)的
2.为什么需要空间配置器
各种容器-----可以存放元素----底层需要空间
new 申请空间
operator new ----malloc调用构造函数------完成对象的构造
动态内存管理总结
前面的容器…空间配置器
1.什么是空间配置器
为各个容器高效的管理空间(空间的申请与回收)的
2.为什么需要空间配置器
各种容器-----可以存放元素----底层需要空间
new 申请空间
operator new ----malloc调用构造函数------完成对象的构造
动态内存管理总结
前面的容器中每次开辟空间都用的是new但是用new有一些不好的地方
空间申请与释放需要用户自己管理容易造成内存泄漏频繁向系统申请小块内存块容易造成内存碎片例如:结点频繁向系统申请小块内存影响程序运行效率直接使用malloc与new进行申请每块空间前有额外空间浪费 (malloc会在申请的空间前后添加新的东西)申请空间失败怎么处理代码结构比较混乱代码复用率不高未考虑线程安全问题
高效的内存管理方式
3.SGI–STL空间配置器如何实现
小块内存
大于128字节-----大块内存小于等于128字节-----小块内存
一级空间配置器处理大块内存二级空间配置器处理小块内存。
一级空间配置器
mallocfree-----set_new_handle
_malloc_alloc_template:
申请空间
void * allocate(size_t n)
{// 申请空间成功直接返回失败交由oom_malloc处理void * result malloc(n);if(nullptr result)result oom_malloc(n);return result;
}释放空间
static void deallocate(void *p, size_t /* n */)
{ free(p);
}malloc失败后的处理oom_malloc
接受函数指针(调用set_new_handle)验证该函数指针是否为空 是直接抛异常 调用该函数指针对应的函数调用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);}
}set_new_handle
返回值类型以及参数类型都是void*()函数指针
// 该函数的参数为函数指针返回值类型也为函数指针
// 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);
}二级空间配置器
频繁向系统申请小的内存块造成的缺陷 SGI—STL采用了内存池的技术来提高申请空间的速度以及减少额外空间的浪费采用哈希桶的方式来提高用户获取空间的速度与高效管理。
内存池
内存池就是先申请一块比较大的内存块已做备用当需要内存时直接到内存池中去去当池中空间不够时再向内存中去取当用户不用时直接还回内存池即可。避免了频繁向系统申请小块内存所造成的效率低、内存碎片以及额外浪费的问题
char* _start,*finish申请空间
现在已经归还的内存块中找合适的块找到----是否需要分割----不需要----直接分配 需要-----再对内存块进行分割未找到-----去内存池中申请
申请空间的缺陷
链表查找合适内存块需要遍历效率低分割
注意问题
当用户需要空间时能否直接从内存池中大块空间中直接截取为什么 答:优先从链表中选先从大块中拿如果用户需要大块的空间可能就给不了了对用户归还的空间能否直接拼接在大块内存前 答:不行对用户归还的空间如何进行管理 答:用链表连接起来不断切割会有什么后果 答:内存碎片
二级空间配置器的设计
SGI-STL中的二级空间配置器使用了内存池技术但没有采用链表的方式对用户已经归还的空间进行管理(因为用户申请空间时在查找合适的小块内存时效率比较低)而是采用了哈希桶的方式进行管理效率更高。那是否需要128桶个空间来管理用户已经归还的内存块呢答案是不需要因为用户申请的空间基本都是4的整数倍其他大小的空间几乎很少用到。因此SGI-STL将用户申请的内存块向上对齐到了8的整数倍 32位系统用4的倍数 64位系统用8的倍数 每个链表中肯定必须有一个指针32位指针是4个字节64位下是8个字节
template int inst
class __default_alloc_template
{
private:enum { __ALIGN 8 }; // 如果用户所需内存不是8的整数倍向上对齐到8的整数倍enum { __MAX_BYTES 128 }; // 大小内存块的分界线enum { __NFREELISTS __MAX_BYTES / __ALIGN }; // 采用哈希桶保存小块内存时所需桶的个数// 如果用户所需内存块不是8的整数倍向上对齐到8的整数倍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]; /* The client sees this. */};
private:static obj * free_list[__NFREELISTS];// 哈希函数根据用户提供字节数找到对应的桶号static size_t FREELIST_INDEX(size_t bytes){return (((bytes)__ALIGN - 1) / __ALIGN - 1);}// start_free与end_free用来标记内存池中大块内存的起始与末尾位置static char *start_free;static char *end_free;// 用来记录该空间配置器已经想系统索要了多少的内存块static size_t heap_size;// ...跨平台操作封装锁申请空间方式等
};二级空间配置器的管理空间 void allocate(size_t n) { if(n128) ; //调用一级空间配置器 1. 用n计算桶号 2. 检测该桶中是否有结点(内存块) 有:使用头删法将第一个内存块返回 没有return refill(Round_up(n)); } void refill(size_t/已经是8的整数倍/) { size_t nobjs 20; char* chunk chunk_alloc(n,nobjs); if(nobjs 1) //只要了一块 return chunk; //1nobjs20 将第一个内存保存最后要返回给外部用户 将剩余nobjs-1个内存块挂接到对应的桶中 } void * chunk_alloc(size_t size,size_t nobjs//20) { size_t totalBytes nobjs*size; size_t leftBytes finish-start; void * res null; if(leftBytes totalBytes) //内存池空间足以提供20 {res start;starttotalBytes;return res;} else if(leftBytessize)//不够20至少提供1块 {nobjs leftBytes/size;resstart;startnobjssize;return res;}//实际能提供多少块 else //内存池的空间也不足连一块也提供不了 { //1.将内存池中剩余的内存—挂接到相应桶中 //total_get 2total_bytesRoundUP(heap_size4); } } 申请空间
// 函数功能向空间配置器索要空间
// 参数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_list_link;return (result);
};回收空间 二级空间配置器中没有释放空间
// 函数功能用户将空间归还给空间配置器
// 参数p空间首地址 n空间总大小
static void deallocate(void *p, size_t n)
{obj *q (obj *)p;obj ** my_free_list;// 如果空间不是小块内存交给一级空间配置器回收if (n (size_t)__MAX_BYTES) //超过128按照一级空间配置进行释放{malloc_alloc::deallocate(p, n);return;}//没到128// 找到对应的哈希桶将内存挂在对应哈希桶中my_free_list free_list FREELIST_INDEX(n);q-free_list_link *my_free_list;*my_free_list q;
}向内存中补充空间 template int inst
char* __default_alloc_templateinst::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 total_bytes){result start_free;start_free total_bytes;return(result);}else if (bytes_left size){// nobjs块无法提供但是至少可以提供1块size字节内存块提供后返回nobjs bytes_left / size;total_bytes size * nobjs;result start_free;start_free total_bytes;return(result);}else{// 内存池空间不足连一块小块村内都不能提供// 向系统堆求助往内存池中补充空间// 计算向内存中补充空间大小本次空间总大小两倍 向系统申请总大小/16size_t bytes_to_get 2 * total_bytes 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;//end_free作用是标记内存池空间的末尾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));}
}空间配置器的默认选择
SGI-STL默认使用一级还是二级空间配置器通过USE_MALLOC宏进行控制
#ifdef __USE_MALLOCtypedef malloc_alloc alloc;typedef malloc_alloc single_client_alloc;
#else// 二级空间配置器定义
#endif在SGI_STL中该宏没有定义因此默认情况下SGI_STL使用二级空间配置器
空间配置器的再次封装
在C中用户所需空间可能是任意类型的有单个对象空间有连续空间每次让用户自己计算所需空间总大小不是很友好因此SGI-STL将空间配置器重新再封装了一层
templateclass T, class Alloc
class simple_alloc
{
public:// 申请n个T类型对象大小的空间static T *allocate(size_t n){return 0 n ? 0 : (T*)Alloc::allocate(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));}// 释放一个T类型对象大小的空间static void deallocate(T *p){Alloc::deallocate(p, sizeof (T));}
};对象构造与释放
一切为了效率考虑SGI-STL决定将空间申请释放和对象的构造析构两个过程分离开因为有些对象的构造不需要调用析构函数销毁时不需要调用析构函数将该过程分离开可以提高程序的性能
// 归还空间时先先调用该函数将对象中资源清理掉
template class T
inline void destroy(T* pointer)
{pointer-~T();
}
// 空间申请好后调用该函数利用placement-new完成对象的构造
template class T1, class T2
inline void construct(T1* p, const T2 value)
{new (p)T1(value);
}
