最新要闻

广告

手机

又是一年开学季丨无缝接驳 直通高校 武汉贴心迎新

又是一年开学季丨无缝接驳 直通高校 武汉贴心迎新

 科锐国际廖萍： 数字化人才将成为VUCA时代企业人才战略的核心

科锐国际廖萍： 数字化人才将成为VUCA时代企业人才战略的核心

家电

  1. 首页
  2. 移动通信
  3. 内容

126.STL 之 空间配置器（allocator）

来源：博客园

126.STL 之 空间配置器（allocator）

1.SGI 标准的空间配置器，std::allocator

SGI也定义了一个符合部分标准，名为allocator的配置器，但是它自己不使用，也不建议我们使用，主要原因是效率不佳。

它只是把C++的操作符::operator new和::operator delete做了一层简单的封装而已。


【资料图】

2.SGI 特殊的空间配置器，std::alloc

由于SGI 标准的空间配置器只是把C++的操作符::operator new和::operator delete做了一层简单的封装，没有考虑到任何效率上的强化。

所以 SGI 出现了一个特殊的空间配置器，供 STL标准模板库使用。

通常，C++中用new操作符来分配内存都包括两个阶段：

（1）调用::operator new配置内存

（2）调用构造函数来构造对象内容

同理，delete操作也包括两个阶段：

（1）调用析构函数将对象析构

（2）调用::operator delete释放内存

为了精密分工，SGI STL allocator将两个阶段分开：

内存配置操作由alloc:allocate负责，内存释放由alloc:deallocate负责；对象构造操作由::contructor()负责，对象析构由::destroy()负责。

配置器定义在头文件中，它里面又包括两个文件：

#include         // 负责内存空间的配置和器释放  #include         // 负责对象的构造和析构

3.STL 空间配置器：

3.1STL 空间配置器解决的问题

1.内存碎片问题（外碎片）

内碎片：操作系统在分配给申请者未被利用的部分。产生原因：内存对齐（效率高）；

外碎片：内存充足时但分配不出大块内存。产生原因：由于多次分配小块内存，将大块内存分割成小块；

2.频繁系统分配，释放小块内存，调用 malloc，delete 系统调用产生性能问题；

STL 空间配置器的实现机制：

3.2双层级的配置器

注：

当需要开辟的空间大于 128 bytes 时，视为“足够大”，调用一级配置器，直接调用 malloc，free；

当需要开辟的空间小于 128 bytes 时，视为“过小”，为了降低额外负担，调用二级空间配置器

A.一级空间配置器

//以下是第第一级配置器template class __malloc_alloc_template {private:    //以下函数用来处理内存不足的情况    static void* oom_malloc(size_t);    static void* oom_realloc(void*, size_t);    static void (*__malloc_alloc_oom_handler)();public:    static void* allocate(size_t n)    {        void* result = malloc(n);                    //第一级配置器，直接使用malloc()        //如果内存不足，则调用内存不足处理函数oom_alloc()来申请内存        if (0 == result) result = oom_malloc(n);        return result;    }    static void deallocate(void* p, size_t /* n */)    {        free(p);            //第一级配置器直接使用 free()    }    static void* reallocate(void* p, size_t /* old_sz */, size_t new_sz)    {        void* result = realloc(p, new_sz);            //第一级配置器直接使用realloc()        //当内存不足时，则调用内存不足处理函数oom_realloc()来申请内存        if (0 == result) result = oom_realloc(p, new_sz);        return result;    }    //设置自定义的out-of-memory handle就像set_new_handle()函数    static void (*set_malloc_handler(void (*f)()))()    {        void (*old)() = __malloc_alloc_oom_handler;        __malloc_alloc_oom_handler = f;        return(old);    }};template void (*__malloc_alloc_template::__malloc_alloc_oom_handler)() = 0;　　//内存处理函数指针为空，等待客户端赋值template void* __malloc_alloc_template::oom_malloc(size_t n){    void (*my_malloc_handler)();    void* result;    for (;;)     {                                                     //死循环        my_malloc_handler = __malloc_alloc_oom_handler;            //设定自己的oom(out of memory)处理函数        if (0 == my_malloc_handler) { __THROW_BAD_ALLOC; }         //如果没有设定自己的oom处理函数，毫不客气的抛出异常        (*my_malloc_handler)();                                    //设定了就调用oom处理函数        result = malloc(n);                                        //再次尝试申请        if (result) return(result);    }}template void* __malloc_alloc_template::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; }    //如果自己没有定义oom处理函数，则编译器毫不客气的抛出异常        (*my_malloc_handler)();                                //执行自定义的oom处理函数        result = realloc(p, n);                                //重新分配空间        if (result) return(result);                            //如果分配到了，返回指向内存的指针    }}

上面代码看似繁杂，其实流程是这样的：

1.我们通过allocate()申请内存，通过deallocate()来释放内存，通过reallocate()重新分配内存。

2.当allocate()或reallocate()分配内存不足时会调用oom_malloc()或oom_remalloc()来处理。

3.当oom_malloc() 或 oom_remalloc()还是没能分配到申请的内存时，会转如下两步中的一步：

(a)调用用户自定义的内存分配不足处理函数(这个函数通过set_malloc_handler() 来设定)，然后继续申请内存！

(b)如果用户未定义内存分配不足处理函数，程序就会抛出bad_alloc异常或利用exit(1)终止程序。

看完这个流程，再看看上面的代码就会容易理解多了！

B.二级配置器 _ _default_alloc_template

第二级配置器的代码很多，这里我们只贴出其中的 allocate() 和 dellocate()函数的实现和工作流程(参考侯捷先生的《STL源码剖析》)，而在看函数实现代码之前，我大致的描述一下第二层配置器配置内存的机制。

我们之前说过，当申请的内存大于 128 bytes时就调用第一层配置器。当申请的内存小于 128bytes时才会调用第二层配置器。第二层配置器如何维护128bytes一下内存的配置呢？ SGI 第二层配置器定义了一个 free-lists，这个free-list是一个数组，如下图：

这数组的元素都是指针，用来指向16个链表的表头。这16个链表上面挂的都是可以用的内存块。只是不同链表中元素的内存块大小不一样，16个链表上分别挂着大小为8,16,24,32,40,48,56,64,72,80,88,96,104,112,120,128 bytes的小额区块，图如下：

就是这样，现在我们来看allocate()代码：

static void* allocate(size_t n){    obj* __VOLATILE* my_free_list;    obj* __RESTRICT result;    //要申请的空间大于128bytes就调用第一级配置    if (n > (size_t)__MAX_BYTES)     {        return(malloc_alloc::allocate(n));    }    //寻找 16 个free lists中恰当的一个    my_free_list = free_list + FREELIST_INDEX(n);    result = *my_free_list;    if (result == 0)    {        //没找到可用的free list，准备新填充free list        void* r = refill(ROUND_UP(n));        return r;    }    *my_free_list = result->free_list_link;    return (result);};

其中有两个函数我来提一下，一个是ROUND_UP()，这个是将要申请的内存字节数上调为8的倍数。因为我们free-lists中挂的内存块大小都是8的倍数嘛，这样才知道应该去找哪一个链表。另一个就是refill()。这个是在没找到可用的free list的时候调用，准备填充free lists。意思是：参考上图，假设我现在要申请大小为 56bytes 的内存空间，那么就会到free lists 的第 7 个元素所指的链表上去找。如果此时 #6元素所指的链表为空怎么办？这个时候就要调用refill()函数向内存池申请N(一般为20个)个大小为56bytes的内存区块，然后挂到 #6 所指的链表上。这样，申请者就可以得到内存块了。当然，这里为了避免复杂，误导读者我就不讨论refill()函数了。allocate()过程图如下：

学过链表的操作的人不难理解上图，我就不再讲解。下面看deallocate()，代码如下：

static void deallocate(void* p, size_t n){    obj* q = (obj*)p;    obj* __VOLATILE* my_free_list;    //如果要释放的字节数大于128，则调第一级配置器    if (n > (size_t)__MAX_BYTES)     {        malloc_alloc::deallocate(p, n);        return;    }    //寻找对应的位置    my_free_list = free_list + FREELIST_INDEX(n);    //以下两步将待释放的块加到链表上    q->free_list_link = *my_free_list;    *my_free_list = q;}

deallocate()函数释放内存的步骤如下图：

其实这就是一个链表的插入操作，也很简单。不再赘述！上面忘了给链表结点的结构体定义了，如下：

union obj{    union obj * free_list_link;    char client_date[1]; };

4.标准库allocator类及其算法

allocator a定义了一个名为a的allocator对象，它可以为类型为T的对象分配内存
a.allocate(n)分配一段原始的、未构造的内存，保存n个类型为T的对象
a.deallocate(p, n)释放从T*指针p中地址开始的内存，这块内存保存了n个类型为T的对象，调用deallocate前，用户必须对每个在这块内存中创建的对象调用destroy
a.construct(p, args)args被传递给类型为T的构造函数，用来在p指向的内存中构造一个对象
a.destory(p)p为T*类型的指针，此算法对p指向的对象执行析构函数
#include #include using namespace std;class Example{public:    Example()     {        cout << "Example default constructor..." << endl;    }    Example(int x) : a(x)     {        cout << "Example constructor..." << endl;    }    ~Example()     {        cout << "Example destructor..." << endl;    }    int a = 0;};int main() {    allocator alloc;    // 使用allocate函数分配一块能够存放5个Example对象的内存空间    Example* p = alloc.allocate(5);    // 使用construct函数在第一个位置构造一个Example对象    alloc.construct(p, 1);    // 使用construct函数在第二个位置构造一个Example对象    alloc.construct(p + 1, 2);    // 使用destroy函数销毁第一个位置的Example对象    alloc.destroy(p);    // 使用deallocate函数释放分配的内存空间    alloc.deallocate(p, 5);    return 0;}

输出：

Example constructor...Example constructor...Example destructor...

在这个例子中，我们首先创建了一个名为alloc的allocator对象，用于分配Example对象所需的内存。

然后，我们使用alloc.allocate(5)函数分配了一块能够存放5个Example对象的内存空间，并将返回的指针赋值给指针变量p。

接下来，我们使用alloc.construct()函数在刚刚分配的内存空间中构造了两个Example对象。第一个对象使用带参数的构造函数进行构造，并将参数值设置为1；第二个对象也使用带参数的构造函数进行构造，并将参数值设置为2。

然后，我们使用alloc.destroy()函数销毁了第一个位置的Example对象。最后，我们使用alloc.deallocate()函数释放了分配的内存空间。

需要注意的是，在使用allocator类进行内存分配和对象构造时，必须使用alloc.construct()函数来显式地调用构造函数进行对象的构造，并使用alloc.destroy()函数来显式地调用析构函数进行对象的销毁。

参考：STL 之 空间配置器（allocator）

浅析STL allocator

关键词：