资料出处：http://www.cppblog.com/bangle/archive/2008/08/26/59915.html
linux内存管理策略
linux低层采用三层结构，实际使用中可以方便映射到两层或者三层结构，以适用不同的硬件结构。最下层的申请内存函数get_free_page。之上有三种类型的内存分配函数
（1）kmalloc类型。内核进程使用，基于slab技术，用于管理小于内存页的内存申请。思想出发点和应用层面的内存缓冲池同出一辙。但它针对内核结构，特别处理，应用场景固定，不考虑释放。不再深入探讨。
（2）vmalloc类型。内核进程使用。用于申请不连续内存。
（3）brk/mmap类型。用户进程使用。malloc/free实现的基础。
有关详细内容，推荐http://www.kerneltravel.net/journal/v/mem.htm。http://www.kerneltravel.net上有不少内核相关知识。
malloc系统的内存管理策略
malloc系统有自己的内存池管理策略，malloc的时候，检测池中是否有足够内存，有则直接分配，无则从内存中调用brk/mmap函数分配，一般小于等于128k（可设置）的内存，使用brk函数，此时堆向上（有人有的硬件或系统向下）增长，大于128k的内存使用mmap函数申请，此时堆的位置任意，无固定增长方向。free的时候，检测标记是否是mmap申请，是则调用unmmap归还给操作系统，非则检测堆顶是否有大于128k的空间，有则通过brk归还给操作系统，无则标记未使用，仍在glibc的管理下。glibc为申请的内存存储多余的结构用于管理，因此即使是malloc(0)，也会申请出内存(一般16字节，依赖于malloc的实现方式），在应用程序层面，malloc(0)申请出的内存大小是0，因为malloc返回的时候在实际的内存地址上加了16个字节偏移，而c99标准则规定malloc（0）的返回行为未定义。除了内存块头域，malloc系统还有红黑树结构保存内存块信息，不同的实现又有不同的分配策略。频繁直接调用malloc，会增加内存碎片，增加和内核态交互的可能性，降低系统性能。linux下的glibc多为Doug Lea实现
应用层面的内存池管理
1：不定长内存池。
典型的实现有apr_pool。优点是不需要为不同的数据类型创建不同的内存池，缺点是造成分配出的内存不能回收到池中。这是由于这种方案以session为粒度，以业务处理的层次性为设计基础。
apr_pool中的内存池并不是仅仅一个内存池，相反而是存在多个内存池，这些内存池之间形成层次结构。根据处理阶段的周期长短引出了子内存池的概念，与之对应的是父内存池以及根内存池的概念，它们的唯一区别就是存在的周期的不同而已。比如对于HTTP连接而言，包括两种内存池：连接内存池和请求内存池。由于一个连接可能包含多个请求，因此连接的生存周期总是比一个请求的周期长，为此连接处理中所需要的内存则从连接内存池中分配，而请求则从请求内存池中分配。而一个请求处理完毕后请求内存池被释放，一个连接处理后连接内存池被释放。根内存池在整个Apache运行期间都存在,因此apr_pool比较适合用于内存使用的生命期有明显层次的情况.
2:定长内存池
典型的实现有BOOST,LOKI。特点是为不同类型的数据结构分别创建内存池，需要内存的时候从相应的内存池中申请内存，优点是可以在使用完毕立即把内存归还池中，可以更为细粒度的控制内存块。
伪代码分析LOKI内存池:
// char型的firstAvailableBlock_所以没办法存储大于255的位置
struct Chunk
{
void Init(std::size_t blockSize,unsigned char blocks);
void Release();
void* Allocate(std::size_t blockSize);
void Deallocate(void* p,std::size_t blockSize);
unsigned char* pData_;
unsigned char firstAvailableBlock_, blocksAvailable_; //第一个可用block块和可用block块总数
} ;
// 得益于char的小所以可以分配很小的block出来,且在需要对齐的情况下不会出现问题
void Chunk::Init(std::size_t blockSize,unsigned char blocks)
{
pData_ = new unsigned char(blockSize*blocks);
firstAvailableBlock_ = 0; //上次分配的块的序列号
blocksAvailable_ = blocks;
unsigned char i = 0;
unsigned char *p = pData_;
for (;i != blocks; p += blockSize)
{
*p = ++i;
}
}
// 分配blockSize单位固定大小的内存
void * Chunk::Allocate(std::size_t blockSize)
{
if (!blocksAvailable_)
{
return 0;
}
unsigned char* pResult = pData_ +(firstAvailableBlock_ * blockSize); //得到该块的序列号,第一个位置存储的为序列号
firstAvailableBlock_ = *pResult;
--blocksAvailable_;
return pResult;
}
void Chunk::Deallocate( void * p,std::size_t blockSize)
{
ASSERT(p >= pData_); //归还的内存必须大于分配起始内存
unsigned char* toRelese = static_cast<unsigned char*>(p); //强制转换,静态，不检测运行态
*toRelese = firstAvailableBlock_;
firstAvailableBlock_ = static_cast<unsigned char>((toRelese - pData_)/blockSize);
ASSERT(firstAvailableBlock_ == (toRelese - pData_)/blockSize);
++blockSize;
}
#include " pool.h "
class FixedAllocator
{
public:
void* Allocate(std::size_t blockSize_);
private:
std::size_t blocksize_;
unsigned char numBlocks_;
typedef std::vector<Chunk> Chunks;
Chunks Chunks_;
Chunk* allocChunk_; //上一次分配的Chunks
Chunk* deallocChunk_;
} ;
//
void * FixedAllocator::Allocate(std::size_t blockSize_)
{
if (allocChunk_ ==0 || allocChunk_.blocksAvailable_ == 0)
{
Chunks::iterator i = Chunks.begin();
for (;;++i)
{
if (i == Chunks_.end())
{
Chunks_.push_back(Chunk());
Chunk& newChunk = Chunks_.back();
newChunk.Init(blockSize_,Blocks);
allocChunk_ = newChunk;
deallocChunk_ = &Chunks_.front();
}
if (i->blocksAvailable_)
{
allocChunk_ = &*i;
break;
}
}
}
ASSERT(allocChunk_ != 0);
ASSERT(allocChunk_->blocksAvailable_ > 0);
return allocChunk_->Allocate(blockSize_);
}
class SmallObjAllocator
{
public:
SmallObjAllocator(std::size_t chunkSize,std::size_t maxObjectSize); //chunk的预设大小,超过maxObjectSize大小的用new申请
void* Allocate(std::size_t numBytes);
void Deallocate(void* p, std::size_t size);
private:
std::vector<FixedAllocator> pool_;
FixedAllocator* pLastAlloc_; //最后一次分配用的FixedAllocator
FixedAllocator* pLastDealloc_;
} ;
class SmallObject
{
//重载new，delete,设计为模板函数等
} ;
(2)boost::pool系列。boost 的内存池最低层是simple_segregated_storage，类似于Loki中的chunk，在其中申请释放block（boost中把 block称为chunk，晕死，这里还是称其为block）采用了和loki的chunk中同样的算法，不同的是 simple_segregated_storage使用void*保存block的块序号，loki中使用char，因此boost中的 simple_segregated_storage没有255的上限限制，自然也就不需要再其上再封装一层类似与FixedAllocator的层面。另boost没有屏蔽块的大小，直接提供定长的接口给用户，省掉了SmallObjAllocator层面。因此boost的内存池申请释放block的时间复杂度都是O(1)（object_pool和pool_allocator除外），另避免的小内存的浪费，同时boost不能象loki那样在将 block归还给内存池的时候根据chunk的空闲数量释放内存归还给系统，只能显式调用释放内存函数或者等内存池销毁的时候，基本上和内存池生命周期内永不释放没什么区别。
boost的最低层是simple_segregated_storage,主要算法和loki中的chunk一样，不多说了。这里说下影响上层接口的两类实现：add_block/malloc/free、add_ordered_block/malloc/ordered_free，两种低层实现造成 boost上层设计的成功与失败,前者效率高，和loki一样直接增加释放,时间复杂度O(1)，后者扫描排序，时间复杂度O(n)。
boost提供了四种内存池模型供使用：pool、object_pool、singleton_pool、pool_allocator/fast_pool_allocator。
1）pool
基本的定长内存池
#include < boost / pool / pool.hpp >
typedef struct student_st
{
char name[10];
int age;
} CStudent;
int main()
{
boost::pool<> student_pool(sizeof(CStudent));
CStudent * const obj=(CStudent *)student_pool.malloc();
student_pool.free(obj);
return 0;
}
pool的模版参数只有一个分配子类型，boost提供了两种 default_user_allocator_new_delete/default_user_allocator_malloc_free，指明申请释放内存的时候使用new/delete，还是malloc/free，默认是default_user_allocator_new_delete。构造函数有2个参数：nrequested_size,nnext_size。nrequested_size是block的大小（因为void*保存序号，因此boost内置了block的最小值，nrequested_size过小则取内置值），nnext_size是 simple_segregated_storage中内存不足的时候，申请的block数量，默认是32。最全面的实例化pool类似这样： boost::pool<boost::default_user_allocator_malloc_free> student_pool(sizeof(CStudent),255);
pool提供的函数主要有：
| malloc/free | 基于add_block/malloc/free实现，高效 |
| ordered_malloc/ordered_free | 基于add_ordered_block/malloc/ordered_free实现，在pool中无任何意义，切勿使用。 |
| release_memory/purge_memory | 前者释放池中未使用内存，后者释放池中所有内存。另池析构也会释放内存 |
2）object_pool
#include < boost / pool / object_pool.hpp >
class A {
public:
A():data_(0){}
private:
int data_;
} ;
int main()
{
boost::object_pool<A> obj_pool;
A *const pA=obj_pool.construct();
obj_pool.destroy(pA);
return 0;
}
object_pool继承至pool，有两个模版参数，第一个就是对象类型，第二个是分配子类型，默认同pool是 default_user_allocator_new_delete。构造函数参数只有nnext_size，意义以及默认值同pool。最全面的实例化object_pool类似这样：boost::pool<A,boost:: default_user_allocator_malloc_free> obj_pool(255);
object_pool提供的函数主要有（继承至父类的略）：
| malloc/free | 复写pool的malloc/free，add_ordered_block/malloc/ordered_free实现 |
| construct/destroy | 基于本类的malloc/free实现，额外调用默认构造函数和默认析构函数。 |
| ~object_pool | 若析构的时候有对象未被destroy，可以检测到，释放内存前对其执行destroy |
object_pool 主要着眼于“自动析构”，在没有gc的情况下，达到提高效率和自动管理内存的目的。而且它也特别适合于“多次申请，一次释放”的情况.所以它甚至是鼓励你忽略使用destroy（从它的例子就可以看出来）。
destroy函数并没有提高复杂度，因为内部链表始终处于有序状态（由于使用order_malloc,order_free)，所以不论是逐个释放，还是成批释放，它的复杂度都是O(N)
3）singleton_pool
pool的加锁版本。
#include < boost / pool / singleton_pool.hpp >
typedef struct student_st
{
char name[10];
int age;
} CStudent;
typedef struct singleton_pool_tag {} singleton_pool_tag;
int main()
{
typedef boost::singleton_pool<singleton_pool_tag,sizeof(CStudent)> global;
CStudent * const df=(CStudent *)global::malloc();
global::free(df);
return 0;
}
singleton_pool为单例类，是对pool的加锁封装，适用于多线程环境，其中所有函数都是静态类型。它的模版参数有5个，tag：标记而已，无意义；RequestedSize：block的长度；UserAllocator：分配子，默认还是 default_user_allocator_new_delete；Mutex：锁机制，默认值最终依赖于系统环境，linux下是 pthread_mutex，它是对pthread_mutex_t的封装；NextSize：内存不足的时候，申请的block数量，默认是32。最全面的使用singleton_pool类似这样：typedef boost::singleton_pool<singleton_pool_tag,sizeof(CStudent),default_user_allocator_new_delete,details::pool::default_mutex,200> global;
它暴露的函数和pool相同。
4）pool_allocator/fast_pool_allocator
stl::allocator的替换方案。两者都是基于singleton_pool实现，实现了stl::allocator要求的接口规范。两者的使用相同，区别在于pool_allocator的实现调用ordered_malloc/ordered_free， fast_pool_allocator的实现调用malloc/free，因此推荐使用后者。
#include < boost / pool / pool_alloc.hpp >
#include < vector >
typedef struct student_st
{
char name[10];
int age;
} CStudent;
int main()
{
std::vector<CStudent *,boost::fast_pool_allocator<CStudent *> > v(8);
CStudent *pObj=new CStudent();
v[1]=pObj;
boost::singleton_pool<boost::fast_pool_allocator_tag,sizeof(CStudent *)>::purge_memory();
return 0;
}
fast_pool_allocator的模版参数有四个：类型，分配子，锁类型，内存不足时的申请的block数量，后三者都有默认值，不再说了。它使用的singleton_pool的tag是boost::fast_pool_allocator_tag。