轮子-sgi_stl二级空间配置器原理
- 分离存储策略 : 简单分离存储（我认为是）
一级空间配置器没有内存池。只是将对象的构造和内存的开辟分离开而已。
二级空间配置器就是 一级空间配置器 + 基于freelist实现的内存池的结合
SGI STL 二级空间配置器 原理
图示
-
template<typename T> class my_allocator{} - 整体
- _S_chunk_alloc
相关定义
- SGI STL包含了一级空间配置器和二级空间配置器，
- 其中一级空间配置器allocator采用malloc和free来管理内存，和C++标准库中提供的allocator是一样的，
- 但其二级空间配置器allocator采用了基于freelist（自由链表）原理的内存池机制实现内存管理。
- SGI STL二级空间配置器：线程安全
1 |
|
主要成员
内存池粒度信息
1
2
3enum {_ALIGN = 8}; // 内存对齐
enum {_MAX_BYTES = 128}; // 最大块大小 >128就不会放到内存池里了，也即不会用二级空间配置器。会用一级空间配置器
enum {_NFREELISTS = 16}; // 静态链表的成员个数 _MAX_BYTES/_ALIGN每一个内存chunk块的头信息
- chunk：数据块，区块。
1
2
3
4union _Obj {
union _Obj* _M_free_list_link;
char _M_client_data[1]; /* The client sees this. */
};
- chunk：数据块，区块。
自由链表数组。数组的每个成员是静态的_Obj*指针。_STL_VOLATILE是为了保证多线程安全（通过防止线程缓存？多线程中一般堆上和数据段都会加volatile）
1
2
3
4
5
6static _Obj* __STL_VOLATILE _S_free_list[_NFREELISTS];
template <bool __threads, int __inst>
typename __default_alloc_template<__threads, __inst>::_Obj* __STL_VOLATILE
__default_alloc_template<__threads, __inst> ::
_S_free_list[_NFREELISTS] = {0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, };Chunk allocation state. 记录内存chunk块的分配情况1
2
3
4
5
6
7
8
9
10
11// static：类内声明、类外定义。
static char* _S_start_free; // 空闲free内存的起始start位置 [
static char* _S_end_free; // 空闲free内存的结束end位置 ) (包括回收的吗？)
static size_t _S_heap_size; // 总共malloc过的内存大小（因为malloc是从堆heap上请求的，所以叫heapsize）
// 类外定义
template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_start_free = 0;
template <bool __threads, int __inst>
char* __default_alloc_template<__threads, __inst>::_S_end_free = 0;
template <bool __threads, int __inst>
size_t __default_alloc_template<__threads, __inst>::_S_heap_size = 0;我认为SGI STL二级空间配置器中的内存池，分为三部分
- 一部分给用户使用
- 一部分是用户还没使用的，已经形成chunk链表内存池
- 一部分是还没加入chunk链表内存池的原始空闲内存
重要辅助函数
- 将bytes上调至最邻近的_ALIGN = 8的倍数
1
2
3
4static size_t _S_round_up(size_t __bytes)
{
return (((__bytes) + (size_t) _ALIGN-1) & ~((size_t) _ALIGN - 1));
} - 分析
- 计组复习：
- 机器数的解释规则都是补码。也就是计算机里的数都是以补码形式存储的。
- 补码
- 正数：补码=原码=真值
- 负数：补码=~原码+1
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37枚举变量的取值为花括号内的任意一个值（有且只能有其中一个值），而这个值是int型的。
在X86系统中，所以sizeof(_ALIGN) = sizeof(int) = 4，也就是枚举变量的值为4
_ALIGN
00000000 | 00000000 | 00000000 | 00001000
_ALIGN - 1
00000000 | 00000000 | 00000000 | 00000111
~(ALIGN-1)
11111111 | 11111111 | 11111111 | 11111000
(size_t)_ALIGN
00000000 | 00000000 | 00000000 | 00000000 | 00000000 | 00000000 | 00000000 | 00001000
(size_t)_ALIGN-1
00000000 | 00000000 | 00000000 | 00000000 | 00000000 | 00000000 | 00000000 | 00000111
~((size_t)_ALIGN-1)
11111111 | 11111111 | 11111111 | 11111111 | 11111111 | 11111111 | 11111111 | 11111000
(size_t)_ALIGN-1 + bytes
000...| 00000111 +0
000...| 00001000 +1
000...| 00001001 +2
000...| 00001111 +8
// -> 8
000...| 00010000 +9
000...| 00010111 +16
// -> 16
000...| 00011000 +17
// -> 24
&
~((size_t)_ALIGN-1)
111...| 11111000
- 计组复习：
- 返回位于第几个内存块
- bytes >= 1 内存块号 >= 0
1
2
3
4
5
6
7
8// bytes >= 1 内存块号 >= 0
static size_t _S_freelist_index(size_t __bytes) {
// (bytes + 7)/(ALIGN = 8) - 1。（+7(ALIGN-1)：为了保证12345678位于同一组？
return (((__bytes) + (size_t)_ALIGN-1)/(size_t)_ALIGN - 1);
}
[1,8][9,16][17,24]
0 1 2
- bytes >= 1 内存块号 >= 0
- 例子
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
using namespace std;
enum { _ALIGN = 8 }; // 4
// 将bytes上调至最邻近的8的倍数
static size_t _S_round_up(size_t __bytes)
{
return (((__bytes)+(size_t)_ALIGN - 1) & ~((size_t)_ALIGN - 1));
}
// 返回位于第几个内存块
static size_t _S_freelist_index(size_t __bytes) {
return (((__bytes)+(size_t)_ALIGN - 1) / (size_t)_ALIGN - 1); // (bytes + 7)/8 -1;
}
int main() {
cout << sizeof(int) << endl; // 4
cout << sizeof(long long) << endl; // 8
cout << sizeof(unsigned long long) << endl; // 8
cout << sizeof(size_t) << endl; // 8
// size_t ：unsigned long long
cout << "=========================" << endl;
cout << sizeof(_ALIGN) << endl; // 4
cout << typeid(_ALIGN).name() << endl; // enum <unnamed-enum-_ALIGN>
cout << sizeof((size_t)_ALIGN) << endl; // 8
cout << typeid((size_t)_ALIGN).name() << endl; // unsigned __int64
cout << "===========================" << endl;
cout << _ALIGN << endl; // 8
cout << _ALIGN-1 << endl; // 7
cout << ~(_ALIGN - 1) << endl; // -8
cout << ((size_t)_ALIGN - 1) << endl; // 7
cout << (~(size_t)_ALIGN - 1) << endl; // 18446744073709551606
cout << "=============================" << endl;
cout << _S_round_up(0) << endl; // 0
cout << _S_round_up(1) << endl; // 8
cout << _S_round_up(7) << endl; // 8
cout << _S_round_up(8) << endl; // 8
cout << _S_round_up(9) << endl; // 16
cout << _S_round_up(16) << endl; // 16
cout << _S_round_up(17) << endl; // 24
cout << "=============================" << endl;
// cout << _S_freelist_index(0) << endl; bytes至少>=1
cout << _S_freelist_index(1) << endl; // 0
cout << _S_freelist_index(7) << endl; // 0
cout << _S_freelist_index(8) << endl; // 0
cout << _S_freelist_index(15) << endl; // 1
cout << _S_freelist_index(16) << endl; // 1
cout << _S_freelist_index(17) << endl; // 2
cout << _S_freelist_index(24) << endl; // 2
return 0;
}
allocate
- 概述：根据n大小，采取相应方式获取内存，并返回。
- n>128
- malloc_alloc::allocate(__n)。同一级空间配置器。开辟后返回
- n<128
- 根据n大小，借助free从freelist相应元素管理的内存池中取出相应大小内存块。当内存池不存在时，开辟内存池。
- 对于传入的请求内存大小n，n决定了请求那个freelist成员指向的内存池的内存块。
_Obj* __STL_VOLATILE* __my_free_list = _S_free_list + _S_freelist_index(__n)
- 如果相应的
freelist成员=nullptr的话，- 调用
_S_refill：__ret = _S_refill(_S_round_up(__n));- 开辟内存块数=nobjs(20)的内存池，内存池中的每个内存块的大小都是传入的
__nchar* __chunk = _S_chunk_alloc(__n, __nobjs);
- _S_refill根据传入的n大小，计算出开辟的内存池应该由哪个freelist成员管理。
__my_free_list = _S_free_list + _S_freelist_index(__n);
- 将内存池挂到freelist相应成员下，
- 并维护每个空闲内存块之间指向关系。（每个空闲内存块连接在一起组成内存池）
- 返回第一个内存块。
- 开辟内存块数=nobjs(20)的内存池，内存池中的每个内存块的大小都是传入的
- 调用
- n>128
- freelist[]（自由链表）是一个静态的链表
- 数组的每个元素指向一个内存池。
- 同一内存池的chunk内存块的大小一致。
- 不同内存池的chunk内存块大小不一致。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32/* __n must be > 0 */
static void* allocate(size_t __n) // 请求的一块大小为n的空间
{
void* __ret = 0;
// 如果>128bytes，那么调用malloc_alloc::allocate（同一级空间配置器的allocator的allocate一样)
if (__n > (size_t) _MAX_BYTES) {
__ret = malloc_alloc::allocate(__n);
}
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n); // 应当在哪个
// Acquire the lock here with a constructor call.
// This ensures that it is released in exit or during stack
// unwinding.
/*REFERENCED*/
_Lock __lock_instance; // 上锁
_Obj* __RESTRICT __result = *__my_free_list; // __RESTRICT线程安全
if (__result == 0)
// _S_round_up(n)（向上取8的倍数）。根据n的大小，计算出应该开辟多大内存。
// _S_refill：在相应freelist成员下开辟内存池，且内存池的每个内存块大小都为__n向上取8的倍数。并返回内存池的第一个内存块。
// 如何确定将内存池接在哪个freelist成员下？通过_S_freelist_index(n)计算出。
__ret = _S_refill(_S_round_up(__n)); // 开辟内存池
else {
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
}
return __ret;
};
_S_refill
- __n：内存池里每个内存块的大小。并且可以借助n计算出该内存池应该接在那个freelist成员下。
- 概述：当freelist的某个元素obj*=nullptr时，会调用_S_refill，(
_S_refill向下调用_S_chunk_alloc)开辟内存池，并返回内存池的第一个内存块。并且_S_refill内维护从原始内存中申请来的内存池中每个内存块chunk节点之间的指向关系。_S_chunk_alloc：分配指定大小的内存池- 静态链表：把每个chunk块通过Obj*里的指针连接起来
- allocate函数中调用_S_refill。n是传入的参数，代表allocate请求一个多大的内存块。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/* Returns an object of size __n, and optionally adds to size __n free list.*/
/* We assume that __n is properly aligned. */
/* We hold the allocation lock. */
template <bool __threads, int __inst>
void*
__default_alloc_template<__threads, __inst>::_S_refill(size_t __n) // n是一个chunk块的大小
{
// 分配指定大小的内存池 __nobjs：chunk内存块数量 ；这里的 __n：每个chunk内存块大小。
int __nobjs = 20;
char* __chunk = _S_chunk_alloc(__n, __nobjs);
_Obj* __STL_VOLATILE* __my_free_list;
_Obj* __result;
_Obj* __current_obj;
_Obj* __next_obj;
int __i;
// __nobjs：申请到的chunk块数量。当只申请到一个时，直接返回该内存块给上一级使用。无需建立各个chunk的连接关系，无需挂载到相应的freelist成员下。（因为只有一个）
if (1 == __nobjs) return(__chunk);
__my_free_list = _S_free_list + _S_freelist_index(__n); // 根据内存块大小求出内存池应该在由freelist第几个成员管理（指向）
// 静态链表：把每个chunk块通过Obj*里的指针连接起来
// 每个内存块，有一部分的内存时union联合体Obj，里面有一个Obj*指针，负责连接每个空闲内存块。
/* Build free list in chunk */
__result = (_Obj*)__chunk;
*__my_free_list = __next_obj = (_Obj*)(__chunk + __n); // __n：一个内存块的大小（因为第一个内存块要分配出去）
for (__i = 1; ; __i++) {
__current_obj = __next_obj;
__next_obj = (_Obj*)((char*)__next_obj + __n); // 维护内存块间的连接 char* 因此+__n是偏移n个bytes +n是为了一次跑一个chunk块
if (__nobjs - 1 == __i) { // 空闲内存块数为0?
__current_obj -> _M_free_list_link = 0;
break;
} else {
__current_obj -> _M_free_list_link = __next_obj;
}
}
return(__result); // 返回第一个内存块
}
_S_chunk_alloc
allocate(size_t n) -> _S_refill(size_t n) -> _S_chunk_alloc(size_t __size__,int &nobjs)- 将所有备用内存池都应用到，哪怕只剩下
8bytes（最小的块就是8bytes，将这些用不到的小内存块挂载到相应的freelist成员下。）。 chunk_alloc里可能malloc，也可能不malloc。- 从 【备用空闲内存池申请】 或者 【操作系统中开辟】 内存池。这个内存池中，每个
chunk大小为sizebytes，数量为_nobjs。将所申请的这一整个池子的首地址返回给上一级–_S_refill。在_S_refill中，负责将该池子中的每个chunk块建立起链表关系，并挂载到相应free-list成员下。并且_S_refill负责把一个size大小的chunk返回给上一级allocate。（用户调用请求函数）。 - 而在_S_chunk_alloc中，对于内存池子是从备用内存池请求，还是再从操统中开辟，又分以下情况讨论
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36template <bool __threads, int __inst>
char*
__default_alloc_template<__threads, __inst>::_S_chunk_alloc(size_t __size, int& __nobjs)
{
// 剩余的备用内存够支付本次请求的内存大小。
if(_bytes_left >= total_bytes){
...
return result; // total大小内存块
// 剩余的不够支付total，但起码能支付一个内存块。（因为要返回的至少是一个内存块大小）
}else if(__bytes_left >= __size){
...
return result; // 尽量return大点
// 剩余的free内存连一个内存块也不够支付
}else{
...
// 后半+的这个是为了malloc越来越大
// 计算要malloc多少内存s
bytes_to_get = 2*__total_bytes + _S_round_up(_S_heap_size >> 4);
// malloc内存
_S_start_free = (char*)malloc(__bytes_to_get);
// Try to make use of the left-over piece.
// 剩余的备用内存bytes_left,又不够本次请求的一个chunk块大小，就把这块内存挂载到他能所属的freelist成员下。（头插法）
if (__bytes_left > 0) {
// 头插法
// start_free头插接入_S_free_list + _S_freelist_index(__bytes_left)
}
_S_heap_size += __bytes_to_get; // _S_heap_size：迄今为止总共malloc了多少内存?
_S_end_free = _S_start_free + __bytes_to_get; // 移动_S_end_free指针。指向空闲内存块末尾
return(_S_chunk_alloc(__size, __nobjs)); // 递归调用
}
代码
1 | /* We allocate memory in large chunks in order to avoid fragmenting */ |
图示
什么时候调用chunk_alloc?当某个freelist成员的内存池为空时。（没分配过内存池或者内存池耗尽）
调用上下文
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15allocate中：static void* allocate(size_t __n)
_Obj* __RESTRICT __result = *__my_free_list;
// 当某个freelist成员的内存池为空时。（没分配过内存池或者内存池耗尽） 调用__S_chunk_alloc
if (__result == 0)
__ret = _S_refill(_S_round_up(__n));
else {
// 消耗内存池
*__my_free_list = __result -> _M_free_list_link;
__ret = __result;
}
return __ret;
S_refill中
1. char* __chunk = _S_chunk_alloc(__n, __nobjs);
2. 连接得到的chunk块
- 整体
- 我将图中形成链表的自由（空闲）内存节点们称为内存池。
- 将没有建立链表连接的称为原始内存（或者叫备用内存池）。
- 大体：
start-free==0时，就是一点 备用的 空闲的 内存也没有了- 备用内存：
- 优先是只进行了malloc的空闲原始内存，也就是没有被形成freelist某成员内存池的
- 如果没有，其次是已经参与形成内存链表池的空闲chunk块。
- 备用内存：
- 当没有备用内存(
bytes_left==0)时，正常从操统中malloc内存- 一小块返回给用户使用，
- 一部分返回给上一级加工成内存池（把chunk块之间连起来）
- 一部分在
[_start_free和_end_free)之间，用作备用内存（备用内存池/原始内存）。
- 当有备用内存时
- start和free之间malloc的原始内存，还没参与形成内存池
- [start，free) > size (nobjs>1)，则将这块内存挂给相应freelist成员
- 图中为空闲内存有160bytes，而上层申请16*20bytes内存
- 条件同上
- start和free之间malloc的原始内存，还没参与形成内存池
- nobjs = [start，free) / size = 1，则将这内存块返回。（因为只有一个，所以不必挂载形成内存池）
- 图中空闲内存为160bytes，而上层申请16*128bytes内存。
- 返回1个128bytes内存块
- 用户又接着申请32bytes
- 用户接着申请128bytes
- 第三张红圈的例子：解释如下。
- 只返回一个
128bytes块时，freelist的128bytes成员仍是空，因为返回的这一个直接就用作请求结果了，并没空闲内存块。 - 当上层(allocate)再次请求128Bytes时，_S_refill调用
chunk = _S_chunk_alloc(size_t __size = 128, int& __nobjs = 20)。由于剩下__bytes_left = 32bytes < size = 128bytes。故进入else。 - 剩余的
32bytes被freelist的32bytes成员管理（因为这个32bytes对于128bytes的chunk块来说无用）。再开辟bytes_to_get的内存。移动free_start。接下来的操作同一开始malloc内存。（再循环调用chunk_alloc...
- 只返回一个
- malloc失败
- 从别的freelist成员已经形成链表的内存池中，拿出一块chunk，给本次请求用
- 从别的freelist成员已经形成链表的内存池中，拿出一块chunk，给本次请求用
deallocate
- 功能概述：归还p指向的、大小为n的内存块，还给内存池链表。（n用于计算归还的该块内存应该在哪个freelist成员管理的内存之中）
- 将p头插入法插入内存池链表中。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/* __p may not be 0 */
static void deallocate(void* __p, size_t __n)
{
if (__n > (size_t) _MAX_BYTES) // n>128 同一级空间配置器
malloc_alloc::deallocate(__p, __n);
else {
_Obj* __STL_VOLATILE* __my_free_list
= _S_free_list + _S_freelist_index(__n); // 找到相应freelist成员
_Obj* __q = (_Obj*)__p; //
// acquire lock
/*REFERENCED*/
_Lock __lock_instance;
__q -> _M_free_list_link = *__my_free_list;
*__my_free_list = __q;
// lock is released here
}
}
__malloc_alloc_template
辅助__malloc_alloc_template的类
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41template <int __inst>
class __malloc_alloc_template {
private:
static void* _S_oom_malloc(size_t);
static void* _S_oom_realloc(void*, size_t);
static void (* __malloc_alloc_oom_handler)();
public:
// 申请nbytes。如果空间不足，则释放nbytes
static void* allocate(size_t __n)
{
void* __result = malloc(__n);
if (0 == __result) __result = _S_oom_malloc(__n);
return __result;
}
// 释放p
static void deallocate(void* __p, size_t /* __n */)
{
free(__p);
}
static void* reallocate(void* __p, size_t /* old_sz */, size_t __new_sz)
{
void* __result = realloc(__p, __new_sz);
if (0 == __result) __result = _S_oom_realloc(__p, __new_sz);
return __result;
}
static void (* __set_malloc_handler(void (*__f)()))()
{
void (* __old)() = __malloc_alloc_oom_handler;
__malloc_alloc_oom_handler = __f;
return(__old);
}
};malloc_alloc:
1
typedef __malloc_alloc_template<0> malloc_alloc;
malloc_alloc::allocate
- 功能概述
- 分配nbytes成功 返回result
- 分配失败，那么就调用预制好的_S_oom_malloc，释放nbytes空间，给result
1
2
3
4
5
6
7
8
9class __malloc_alloc_template {
public:
static void* allocate(size_t __n)
{
void* __result = malloc(__n);
if (0 == __result) __result = _S_oom_malloc(__n);
return __result;
}
}
- 调用上下文
- 在没有空间（不能malloc）的情况下，又必须进行malloc。
1
2
3
4
5
6
7_S_chunk_alloc(){
malloc = nullptr;
...
// 没有空间 却又只能allcoate
_S_end_free = 0; // In case of exception.
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get);
}
- 在没有空间（不能malloc）的情况下，又必须进行malloc。
malloc_alloc::_S_oom_malloc
- 功能概述：循环调用用户预制的回调函数，以期解决内存不够的问题，好拿出nbyte内存。
- oom：out of memory 内存耗尽
- 用户先前设置好回调函数
__malloc_alloc_oom_handler- 设置：那么这个回调函数必须实现 释放其他内存，使得可以给当前请求分配内存的功能。否则会陷入死循环，直到可以malloc内存。
returnmalloc的内存。 - 没设置：直接抛异常 throw bad_alloc
1
2
3
4
5
6
7
8
9
10
11
12
13
14template <int __inst>
void* __malloc_alloc_template<__inst>::_S_oom_realloc(void* __p, size_t __n)
{
void (* __my_malloc_handler)(); // 用于接收回调函数
void* __result;
for (;;) {
__my_malloc_handler = __malloc_alloc_oom_handler; // 设置回调函数
if (0 == __my_malloc_handler) { __THROW_BAD_ALLOC; }// 如果用户之前没设置回调函数，那么直接抛异常
(*__my_malloc_handler)(); // 调用回调函数
__result = realloc(__p, __n); //
if (__result) return(__result);
}
}
- 设置：那么这个回调函数必须实现 释放其他内存，使得可以给当前请求分配内存的功能。否则会陷入死循环，直到可以malloc内存。
reallocate
- 功能概述
- 为指针p重新分配指向的空间，大小为new_sz。并返回这块新内存的地址。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22template <bool threads, int inst>
void*
__default_alloc_template<threads, inst>::reallocate(void* __p,size_t__old_sz,size_t __new_sz)
{
void* __result;
size_t __copy_sz;
// old new都>128byets，那么用的就应当是和一级空间配置器一样的方法malloc
if (__old_sz > (size_t) _MAX_BYTES && __new_sz > (size_t) _MAX_BYTES) {
return(realloc(__p, __new_sz)); // 重新分配内存。释放p地址内存
}
// 如果即将分配的chunk块大小一致，那么不必，直接返回
if (_S_round_up(__old_sz) == _S_round_up(__new_sz)) return(__p);
// 重新从内存池中申请new_size大小内存，并拷贝数据到新申请来的内存里
__result = allocate(__new_sz);
__copy_sz = __new_sz > __old_sz? __old_sz : __new_sz;
memcpy(__result, __p, __copy_sz); // 拷贝数据
deallocate(__p, __old_sz); // 将p指向的内存还给内存池链表
return(__result);
}
- 为指针p重新分配指向的空间，大小为new_sz。并返回这块新内存的地址。
经典内存池优点
C/C++下内存管理是让几乎每一个程序员头疼的问题，分配足够的内存、追踪内存的分配、在不需要的时候释放内存——这个任务相当复杂。而直接使用系统调用malloc/free、new/delete进行内存分配和释放，有以下弊端：
利用默认的内存管理函数new/delete或malloc/free在堆上分配和释放内存会有一些额外的开销。系统在接收到分配一定大小内存的请求时，首先查找内部维护的内存空闲块表，并且需要根据一定的算法（例如分配最先找到的不小于申请大小的内存块给请求者，或者分配最适于申请大小的内存块，或者分配最大空闲的内存块等）找到合适大小的空闲内存块。如果该空闲内存块过大，还需要切割成已分配的部分和较小的空闲块。然后系统更新内存空闲块表，完成一次内存分配。类似地，在释放内存时，系统把释放的内存块重新加入到空闲内存块表中。如果有可能的话，可以把相邻的空闲块合并成较大的空闲块。
默认的内存管理函数还考虑到多线程的应用，需要在每次分配和释放内存时加锁，同样增加了开销。
可见，如果应用程序频繁地在堆上分配和释放内存，则会导致性能的损失。并且会使系统中出现大量的内存碎片，降低程序性能，降低内存的利用率。
默认的分配和释放内存算法自然也考虑了性能，然而这些内存管理算法的通用版本为了应付更复杂、更广泛的情况，需要做更多的额外工作。而对于某一个具体的应用程序来说，适合自身特定的内存分配释放模式的自定义内存池则可以获得更好的性能。
内存池（memory pool)是代替直接调用malloc/free、new/delete进行内存管理的常用方法，当我们申请内存空间时，首先到我们的内存池中查找合适的内存块，而不是直接向操作系统申请，优势在于：
- 比malloc/free进行内存申请/释放的方式快;
- 不会产生或很少产生堆碎片;
- 可避免内存泄漏;
普通内存池
1
2
3
4
5
6
7
8
9
10
11（1）先申请一块连续的内存空间，该段内存空间能够容纳一定数量的对象。
（2）每个对象连同一个指向下一个对象的指针一起构成一个内存节点（Memory Node）。各个空闲的内存节点通过指针来形成一个链表，链表的每一个内存节点都是一块可供分配的内存空间。
（3）某个内存节点一旦分配出去，就将从链表中去除。
（4）一旦释放了某个内存节点的空间，又将该节点重新加入自由内存节点链表。
（5）如果一个内存块的所有内存节点分配完毕，若程序继续申请新的对象空间，则会再次申请一个内存块来容纳新的对象。新申请的内存块会加入内存块链表中。
经典内存池的实现过程大致如上面所述，其形象化的过程如下图所示：
SGI STL 二级空间配置器优点
- 对于每一个字节数的chunk块分配，都是返回给用户一个使用的内存块，并给freelist一个内存池，，并留有另一部分作为备用内存池。这个备用可以给当前的字节数freelist成员使用，也可以给其他字节数的freelist成员使用。
- 对于备用内存池划分chunk块以后，如果还有剩余的很小的内存块，再次分配的时候，会把这些小的内存块再次分配出去，备用内存池使用的一滴不剩。
- 当指定bytes字节数内存分配失败以后，有一个异常处理的过程，bytes -> 128字节所有的chunk块进行查看，如果哪个freelist成员下的内存链表池中有chunk块，借一个出去。
- 如果操作失败，会调用
_S_start_free = (char*)malloc_alloc::allocate(__bytes_to_get)来malloc内存；allocate里面通过调用oom_malloc，来调用预先设置好的回调函数__malloc_alloc_oom_handler。用于处理malloc失败的情况
- 如果操作失败，会调用
缺点 我认为
- STL二级空间配置器虽然解决了外部碎片与提高了效率，但它同时增加了一些缺点：
- 1.因为自由链表的管理问题，它会把我们需求的内存块自动提升为8的倍数，这时若你需要1个字节，它 会给你8个字节，即浪费了7个字节，所以它又引入了内部碎片的问题，若相似情况出现很多次，就会造 成很多内部碎片；
- 二级空间配置器是在堆上申请大块的狭义内存池，然后用自由链表管理，供现在使用，在程序执行过 程中，它将申请的内存一块一块都挂在自由链表上，即不会还给操作系统，并且它的实现中所有成员全 是静态的，所以它申请的所有内存只有在进程结束才会释放内存，还给操作系统，由此带来的问题有：
- 1.即我不断的开辟小块内存，最后整个堆上的空间都被挂在自由链表上，若我想开辟大块内存就会失 败；
- 2.若自由链表上挂很多内存块没有被使用，当前进程又占着内存不释放，这时别的进程在堆上申请 不到空间，也不可以使用当前进程的空闲内存，由此就会引发多种问题。
问题解释
问题已解决 希望我能在8月份之前写下来。
1 | 灼夭. 10:11:37 |
内存碎片
https://blog.csdn.net/fdk_lcl/article/details/89482835
1 | round - 必应词典 |
- 计组
1
2
31.计算机里的数都是补码形式，因为CPU只会做加法，数的补码形式就可以用加法实现减法运算，进而以加法完成所有的运算。至于数以什么码的形式输入和输出，编程人员是可以控制的。
2.计算机里数码的位数是2的正整数次方，比如4位、8位、16位，因为CPU及周边电路一旦制成，一次处理数据位数、总线位数、各种寄存器位数就都固定下来，都是2的正整数次方位，这样选择的理由很多，可参照有关资料了解。
3.一个8位的补码数，它表示数的范围是-128~+127，原码表示数的范围是-127~+127，反码表示数的范围是-127~+127，就是因为最高位是符号位，实际数位只有7 位。
内存碎片是问题吗？
- 截
整体代码
1 |
|