认识Linux物理内存管理系统–Buddy System

原创文章,转载请注明出处.转载自: Li Haifeng's Blog
本文链接地址: 认识Linux物理内存管理系统–Buddy System

Agenda
1.       Linux 如何管理物理内存
2.       什么是Buddy System
3.       如何从Buddy System中分配内存
4.       如何释放页到Buddy System
5.       冷热页
6.       关于fall-back zone lists
1.       Linux如何管理物理内存
         为了有效的管理物理内存(分配、回收),Linux将整个物理内存划分为若干个页,对每一个页,都有相关的数据结构来记录该页的状态和使用信息。在Linux中,每个页的大小是4KB. 对于一个512MB的物理内存一共有(512*1024*1024/4*1024)个页。对于每一个页,在Linux中都有一个struct page数据结构来记录该物理页的使用情况。所有页的struct page结构组成一个连续的数组存放在物理内存的某个地方。某页在物理内存中的物理地址除以4KB,就得到该页是第几个物理页索引,然后索引就可以查询struct page数组得到该页的具体信息。

1. Memory Page
         除了使用struct page来记录某个4KB物理页的状态和使用信息外,Linux还将整个物理内存根据物理地址划分为不同的区域(zone)。zone的划分是与体系结构相关的,对于X86ZONE可以划分为DMA[016MB]NORMAL[16MBmin(memory length, 896MB)]HIGHMEM[min(memory length,896MB)memory length]。对于ARMZONE划分为NORMAL区和HIGHMEM区。其中NORMAL区对应线性映射的物理内存,HIGHMEM区对应非线性映射的物理内存。其地址范围是:NORMAL[0,min(768MBmemory Length)] HIGHMEM[min(memory length,896MB)memory length]

2. Memory Zone
2.       什么是Buddy System?
         Buddy SystemLinux Kernel 进行物理内存页管理的一个子系统。在Buddy System中,管理的一个基本单位是block,每一个block有若干个连续的物理页组成,物理页的个数为2n,这个nbuddy system中被称为order。相同orderblock,挂载一条双向链表上。当某个block空闲时,只要发现对应的伙伴也是空闲的,就和伙伴组成一个页数为2n+1block,挂载在order(n+1)的双向链表上,换句话说一个页数为2nblock,是由两个页数为2n-1的伙伴block组成的。因此,一个block的伙伴肯定是和这个block在物理地址上是连续的。在Linux中,order的默认的取值范围是[0,10]

3. Buddy Organize
buddy system中,存入一个页会进行一次伙伴整合的迭代操作,直到不能再合并为止。那么,如何查找某个block的伙伴呢?在Linux中,一个block的伙伴信息记录在该block的第一个物理页的struct page上。也就是说,假若一个页在伙伴系统中,page->private的值为n,则后面连续的2n-1个页面就在buddy system中。一个页面在buddy System中,就代表了该页是空闲的,可以被分配。查找一个页数为2nblock的伙伴计算方法是buddy_index=page_index^(1<<n)buddy_index 表示伙伴块首页的页索引,page_index是该block首页的页索引,n代表order
3.       buddy System中分配页
buddy System用来管理空闲的物理内存,接受进程的内存页申请。Linux提供给用户进程申请内存的接口函数中包含两个参数:一个是GFP_***,另一个是order。前者表示分配标志信息,从标志中可以知道进程要从哪个zone中申请物理内存,并在内存紧缺的情况下指导内存何时回收内存;后者表示需要分配2order个连续的物理页。
buddy system根据参数order,在要求的zone中查找对应的链表。若该order的双向链表非空,则把该双向链表上的第一个blockbuddy system中脱链,同时更新该双向链表上的block的数量,完成内存分配。若该order的双向链表为空,则查找order+1的双向链表,如果order+1的双向链表为空,则查找order+2的双向链表,直到查找到。假设查找到了第n个双向链表(n>order),由于查找到的连续物理内存页的数量大于order,因此将该block一分为二,将后半部分block挂载到2(n-1)的双向链表上,将前半部分再一分为二,将前半部分的后半部分挂载到2(n-2)的双向链表上,将前半部分的前半部分再一分为二。。。直到与请求的order相等为止。如图四。
在图四中,假如要申请order1的页,但buddy System中只有order5的页。分配示意图如下:

4. Allocate Pages
 注: 从buddy的空闲页面组织方式中,可以得出,有时候即使buddy 系统中有连续的2^N个空闲页面,对2^N个空闲页面的申请也不一定会成功。这里(http://lwn.net/Articles/368869/)有一个例子,可以说明这一点。
4.       释放页到buddy System
当非空闲的页被进程释放后,需要把页放回到伙伴系统中。由于block是作为一个整体被申请的,因此其释放也是以block为单位。若该block2n个连续的物理页,在释放的时候,根据buddy_index = page_index^(1<<n)查找该blockordern的伙伴。若查找到伙伴,则将两个ordernblock合并为一个ordern+1block。同时再查找ordern+1 block的伙伴,若找到则两个ordern+1block继续合并直到其不能合并为止,插入到最终order的双向链表的最前端。释放的迭代过程是分配页的逆过程.
5.       冷热页
对于multi-processors,由于多个core共享存储器,进程并发执行。在一个core上运行的进程需要从某个zone的伙伴系统中申请页必须首先锁住该zone,这样其他core上跑的进程需要申请页的时候就需要等待该zone的锁。为了提高buddy system的性能,Linux提出了冷热页的概念。冷热页是每CPU的。在每个core上对每个zone都维护了一条双向链表。该链表上链接的都是单个页,当进程申请order0的页是,就需要先从该cpu的冷热页链表上去拿页。关于冷热页的详细介绍,请猛击:认识Linux/ARM 中的冷热页
6.       关于Fall-back zone lists

当内存管理单元在某个zone分配可用内存页的时候,如果该zone中的空闲内存不足,则会到候补zone中进行分配。候补zone不止一个,特别是对于NUMA的存储架构。因此对于候补zone也有一个列表,排在最前面的作为第一候补,依照排队的顺序优先级逐步降低。关于fall-back zone lists的详细介绍,请猛击:How Linux/ARM initialize fallback-zone-lists

==全文完==

From Li Haifeng's Blog, post 认识Linux物理内存管理系统–Buddy System

Post Footer automatically generated by wp-posturl plugin for wordpress.

分享到: