内存管理再探究
前言
这段时间在准备找实习,在看到STL的时候,有说到内存管理(allocator)。正好以前写HelloOs的时候有讲到这点,最为项目回顾,所以打算横向总结一波,这一扒拉,又找到不少好东西。
以前的我天真的认为内存管理只是OS的责任,OS之上不会涉及到内存管理的方面。 后来才了解到,在OS之上(如运行库、函数库、应用层等)也会涉及到内存管理,如下图所示。
本文主要从操作系统层面、运行库层面和C++标准库方面谈谈其中涉及到的一些内存管理方案,主要包括以下内容:
(1)、buddy系统(OS level)
(2)、Slab分配器(OS level)
(3)、堆内存管理(malloc 、free ; crt level)
(4)、stl中的一种alloctor(C++ standard lib lib)
注:本文意在横向对比总结各个内存管理方案的异同,对于各个内存方案只会大体介绍,不会涉及过多细节,有兴趣的同学可以参照文后的参考进行深入探究。
一、buddy系统
一般来说,现在的内核都把内存按照页(page)进行统一管理(底层分配、回收大都是以页为单位),以页为单位虽然没有内部碎片,但是很容易出现大量的外部碎片。伙伴(buddy)系统就是为了缓解内存分配过程中的外部碎片问题而出现的。
1.1 buddy系统的工作原理
简要说说buddy系统的工作原理吧。
从逻辑上来看,物理内存被分成几个档次大小(一般都是包含2的整数次方个page)的buddy。
在分配时选择和目标大小最接近的一个buddy进行分配,同时把剩下的(选择的buddy可能大于需求的buddy)部分递归进行拆分,拆分的原则就是二分法,每次拆分一半分配到其对应空闲的档次中去,直到拆分完毕。(这也是为什么选择的档次一般都包含2的整数次方个page的原因)。
在回收时,需要将待回收的buddy和前后进行比较,如果前后都是空闲的则进行合并 (这个在我看来就是buddy系统中能够降低外部碎片的核心),并将合并后的buddy放到最终的档次中去。
我懂的,文字有点枯燥,下面来几张图。
buddy系统的逻辑分配示意图:
buddy系统的物理分配示意图:
具体的物理分配过程这里就不说了,具体的可以参照【2】【3】【4】
1.2 buddy系统的优缺点
优点:
1、降低内存的外部碎片
缺点:
1、针对大内存设计,不适合分配小于1个page的大小(如几十、几百个字节)
2、算法的复杂度有点高,因为其会涉及到递归的分配和回收合并
不过瑕不掩瑜,buddy系统还是有很多OS在使用的。
二、Slab(缓存)分配器
在内核中对于大内存分配可以采用上述的buddy系统,但是如果涉及到小内存的分配(以byete为单位的分配)就不适合使用以page为管理单位的buddy系统了。
同时,内核中有对相同对象频繁分配和回收的需求(如对进程描述符、内存描述符、inode结点描述结构体),这种情况下也需要一种小单元的内存管理系统。
slab系统应运而生。
2.1 slab的工作原理
说slab系统应运而生有点夸张了,本质上slab缓存就相当于一个空闲链表,它可以对对象(各种大小固定的数据结构体)进行高速缓存,以便内核在需要的时候可以快速的获取或者释放。
为了更具有通用性,前辈们在内核中设计了slab缓存层。说其是缓存因为其底层需要具体的物理内存管理系统(如buddy系统)来支持,也就是说它需要的物理内存是从底层的内存管理系统中来获取的(一次可能获取一个或几个页)。 其基本结构如下图所示。
基本的原理也很简单,就是提前从较为底层的页分配器中获取一定数量的页(一般是1页或者几页),然后按照固定的大小空间以空闲链表的方式进行组织,留待后续的分配和回收。
在分配时,slab分配其中的一项;回收时,把目标项放入其中。(注意,这里为了简单叙述,没有按照linux slab分配器那样又把每个告诉缓存系统分为空的、部分满的、全满的slab)
具体的操作过程和链表很类似,这里就不赘述了。有兴趣的可以参照【5】【4】【6】。
稍微多提一点,在linux下 一个高速缓存用kmem_cache结构体来表示。其初始化后有点类似下面的示意图(下图中的kmem_cache和标准的linux上不太相同)。
2.2 slab系统的优缺点
优点:
1、针对小内存进行分配
2、可以对相同的对象结构进行高速缓存
缺点:
嗯嗯,我们一般不谈它的缺点。^ _ ^||| 如果非要说的话,大概是每一种大小的数据结构或者说内存需求就需要一种高速缓存(kmem_cache),这有些浪费。
三、堆内存管理(RTL level)
这儿主要是介绍malloc、free等的内存分配方式。从整个计算机体系来看,这已经跨过了OS内核的这道坎,到了所谓的上层。说是上层,其实也不太准确,这毕竟不是正儿八经的application,而是提供给app运行的库函数。
为何在这个层面的malloc还需要进行内存管理呢?
答曰:OS之上,向内核“要”内存就不是一件容易的事了,这个过程中会需要经过“系统调用”这个东东,而这个东东,你懂得,费时费力。 所以为了减少上层应用在内存分配、回收时的频繁系统调用,在OS之上又进行了一层内存管理机制(从某种程度上说类似slab系统的作用)。
3.1 堆内存管理的工作原理
关于malloc堆内存的管理方案,有很多种方案,不同的平台、内核采取的malloc算法也不尽相同。 如下图所示为几种常见的算法。
malloc算法相对来说比较复杂,我也只是从宏观上理解了一部分,并不是是否透彻,这里就不详述了。具体的可以参照【1】中侯捷老师所说的vc6.0中的堆内存管理、还有后文的几篇参考博客【7】、【8】、【9】。
3.2 关于堆内存管理中一些要注意的点
这里要注意几点:
(1)、堆内存管理针对的是虚拟的内存空间管理。具体的物理内存还需要通过底层的内存管理系统(如buddy系统)进行分配、回收。
(2)、malloc在向系统申请内存的时候使用的是brk() 或者mmap() 等。 其中前者是推移堆指针brk,后者是开辟一个新的线性地址空间(在进程的mapping区域(堆以上栈以下)进行)。
如下图所示
malloc系统调用示意图
进程的用户地址空间
四、stl中的一种alloctor(standard lib level)
在gnu的stl中默认的分配器使用的只是简单的allocator,其内存的分配和回收(利用C++ 的new和delete)只是简单的调用底层的malloc和free。大概是由于malloc已经做了一层内存管理了,所以malloc的效率也挺高。
但是按照侯捷老师的说法,以前gnu stl(2.9 版本) 中默认使用的一个alloctor分配器又在malloc之上做了一层内存管理(__default_alloc_template:第二层配置器),这种做法虽然又多了一层复杂性,但是可以显著减少每次malloc的空间浪费(每次malloc都会带有一定的cookie,用来描述这个块,具体的可以参照malloc分配算法)。
4.1 __default_alloc_template 分配器的工作原理
老实说,学完了前面的内存管理,再看这个就有点小巫见大巫了。 原理类似,细节不同。这里就没有啥新颖的东西可说了。
布置个任务,回去自己看吧。 请参照【1】、【11】。 (好吧,说实话是我累了,偷个懒,不介意吧,(* ^ ▽ ^ * ))
放一张复杂的图,留当课后作业,如何?
五、总结
好了,最后总结一波。
两点内容:
(1)、关于内存管理的元数据
大部分的内存管理都需要记录一些元数据,如块的大小,是否分配等属性,这些元数据该放在哪呢? 一般来说,有两种选择,要么放在一个单独的区域,元数据和其对应的内存以某种方式对应起来。如buddy系统中page结构体和具体的页。 另一种方式是和具体的内存绑定在一起,放在具体的内存块相邻之处,如malloc中的堆内存分配和上面介绍的stl分配器。
(2)、关于内存管理的套路
学习了上面几种内存管理方案,抽象出了一点共同的特点:
1、先分档:按照不同的大小分为不同的档次(有的系统可能还需要在分档之前在分个类)
2、初始化:在不同的档次上挂上对应大小的内存块(有的系统是在具体分配的时候才进行初始化),利用链表串起来
3、分配:对照需求的内存块选择具体的档次,从中选取一块;如果有剩余,则放入其他对应的档次中
4、回收:将目标内存块放入对应的档次中,如果有必要的话则进行合并。
ok,就到这儿吧。
参考
【1】、C++内存管理-侯捷
【2】、HelloOs总结之内存管理(中)
【3】、buddy系统
【4】、Linux内核内存管理算法Buddy和Slab
【5】、HelloOs总结之内存管理(下)
【6】、《Linux 内核设计与实现》
【7】、Linux 堆内存管理深入分析
【8】、Linux堆内存管理深入分析(上)
【9】、Linux堆内存管理深入分析下
【10】、Linux Malloc分析-从用户空间到内核空间
【11】、《STL源码剖析》
文章评论