认识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的划分是与体系结构相关的，对于X86，ZONE可以划分为DMA区[0，16MB]、NORMAL区[16MB，min(memory length, 896MB)]和HIGHMEM区[min(memory length,896MB)，memory length]。对于ARM，ZONE划分为NORMAL区和HIGHMEM区。其中NORMAL区对应线性映射的物理内存，HIGHMEM区对应非线性映射的物理内存。其地址范围是：NORMAL[0,min(768MB，memory Length)] HIGHMEM[min(memory length,896MB)，memory length]。

图2. Memory Zone

2.       什么是Buddy System?
         Buddy System是Linux Kernel 进行物理内存页管理的一个子系统。在Buddy System中，管理的一个基本单位是block，每一个block有若干个连续的物理页组成，物理页的个数为2n，这个n在buddy system中被称为order。相同order的block，挂载一条双向链表上。当某个block空闲时，只要发现对应的伙伴也是空闲的，就和伙伴组成一个页数为2（n+1）的block，挂载在order为(n+1)的双向链表上，换句话说一个页数为2n的block，是由两个页数为2（n-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中，就代表了该页是空闲的，可以被分配。查找一个页数为2n的block的伙伴计算方法是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的双向链表非空，则把该双向链表上的第一个block从buddy system中脱链，同时更新该双向链表上的block的数量，完成内存分配。若该order的双向链表为空，则查找order+1的双向链表，如果order+1的双向链表为空，则查找order+2的双向链表，直到查找到。假设查找到了第n个双向链表(n>order)，由于查找到的连续物理内存页的数量大于order，因此将该block一分为二，将后半部分block挂载到2(n-1)的双向链表上，将前半部分再一分为二，将前半部分的后半部分挂载到2(n-2)的双向链表上，将前半部分的前半部分再一分为二。。。直到与请求的order相等为止。如图四。
在图四中，假如要申请order为1的页，但buddy System中只有order为5的页。分配示意图如下：

图4. Allocate Pages
 注： 从buddy的空闲页面组织方式中，可以得出，有时候即使buddy 系统中有连续的2^N个空闲页面，对2^N个空闲页面的申请也不一定会成功。这里（http://lwn.net/Articles/368869/）有一个例子，可以说明这一点。
4.       释放页到buddy System
当非空闲的页被进程释放后，需要把页放回到伙伴系统中。由于block是作为一个整体被申请的，因此其释放也是以block为单位。若该block有2n个连续的物理页，在释放的时候，根据buddy_index = page_index^(1<<n)查找该block的order为n的伙伴。若查找到伙伴，则将两个order为n的block合并为一个order为n+1的block。同时再查找order为n+1 block的伙伴，若找到则两个order为n+1的block继续合并…直到其不能合并为止，插入到最终order的双向链表的最前端。释放的迭代过程是分配页的逆过程.

5.       冷热页
对于multi-processors，由于多个core共享存储器，进程并发执行。在一个core上运行的进程需要从某个zone的伙伴系统中申请页必须首先锁住该zone，这样其他core上跑的进程需要申请页的时候就需要等待该zone的锁。为了提高buddy system的性能，Linux提出了冷热页的概念。冷热页是每CPU的。在每个core上对每个zone都维护了一条双向链表。该链表上链接的都是单个页，当进程申请order为0的页是，就需要先从该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



==全文完==

地点: 中国上海市浦东新区科苑路399号

评论

  1. Unknown2012年9月5日 08:43

    1)若查找到伙伴，则将两个order为n的block合并为一个order为2n的block。同时再查找order为2n block的伙伴，若找到则两个order为2n的block继续合并…
    为什么不是合并为order 为 n+1 的bock?
    2) linux 中有没有维护着对应于 zone 的抽象数据类型，还是体现到 其他数据结构里了？

    回复删除
    回复
    1. hfli02012年9月5日 08:49

      1)若查找到伙伴，则将两个order为n的block合并为一个order为2n的block。同时再查找order为2n block的伙伴，若找到则两个order为2n的block继续合并…
      为什么不是合并为order 为 n+1 的bock?

      Sorry, 笔误。谢谢兄弟。

      2) linux 中有没有维护着对应于 zone 的抽象数据类型，还是体现到其他数据结构里了？

      没明白，能再具体一些吗？

      删除
    2. Unknown2012年9月5日 09:44

      关于 zone 想知道是否有一个 struct zone {...};这样的东西吗？
      还是说 zone 只是一个建议性的抽象概念，linux 实现上根本就不理会。
      比如某个物理地址区间只供 DMA 操作使用，而至于这个地址区间叫做什么是无关紧要的.

      还有关于MMU的一些小问题，都是以前看《深入Linux内核》积累的，我整理一下，
      你有空的时候再请指教。

      删除
    3. hfli02012年9月5日 18:27

      兄弟悟性高啊。

      struct zone{...} 是存在的。每个zone都对自己管辖的物理页维护了一个order从0到10的空闲块链表。在ARM中，有两个有意义的zone，一个是 NORMAL，一个是HIGHMEM. 其中，后者是需要配置才会有的。在向伙伴系统申请空闲页的时候需要指定从哪个zone中申请。一般情况，对于Kernel本身的内存，需要在Normal zone申请，对于用户进程申请的内存，由page fault负责从HIGHMEM去申请。

      DMA zone,在x86上存在，其范围是0~16MB, 用於DMA。 在ARM中，DMA zone不存在，如果需要申请DMA页就从NORMAL zone 申请。

      删除

发表评论

此博客中的热门博文

提交了30次才AC －－－【附】POJ 2488解题报告

NND,这道题目，竟然提交了30次，搞的我晕过去了都！花费了将近12个小时！！ 感一下，叹一声！如今的ACM，不仅锻炼编程，还锻炼了心理承受能力！！ 1、注意格式，后面有一个空行 2、注意输出的时候的字典序－－什么叫字典序，要弄清楚 3、注意国际象棋的棋盘－－ 横的是字母，竖的是数字－－ 一定要按照这个格式，否则即使是答案对，也WA 有26次，全部栽在第3点上 3次栽在第二点上 1次栽在第一点上 PS:因为是字典序，所以，可以肯定只需要从（1，1）开始即可。不需要注意那句话：start at any position of the chessboard. Source Code Problem: 2488 User: omycle Memory: 192K Time: 360MS Language: C++ Result: Accepted Source Code #include <iostream> #include <string> using namespace std ; bool ok = false ; int col = 0 ; int row = 0 ; int zoufa [ 8 ][ 2 ]= {{ - 2 ,- 1 } , { - 2 , 1 } , { - 1 ,- 2 } , { - 1 , 2 } , { 1 ,- 2 } , { 1 , 2 } , { 2 ,- 1 } , { 2 , 1 }} ; // int flag [ 50 ][ 50 ]; //第0行的，第零列的全不要 typedef struct { int x ; int y ; } Step ; Step step [ 100 ]; //记录路径呀 Step step_c [ 100 ]; int Count = 0 ; void print ( int n ); //数组比较函数 bool cmpint () { int i = 0 ; while ( i < col * row ) { if ( step_c [ i ]. x < step [ i ]. x ) return false ; //不用 if ( step_c [ i ]. y < step [ i ]...
阅读全文

n个进程共享m个资源得死锁问题证明

         n个进程共享M个资源，每个进程一次只能申请/释放一个资源，每个进程最多需要M个资源，所有进程总共的资源需求少于M+N个，证明该系统此时不会产生死锁。 答：设max （i）表示第i个进程的最大资源需求量，need(i)表示第i个进程还需要的资源量，alloc(i)表示第i个进程已分配的资源量。由题中所给条件可知：       max(1)+┅+max(n)=(need(1)+┅+need(n))+((alloc(1)+┅+alloc(n))<m+n 如果在这个系统中发生了死锁，那么一方面m个资源应该全部分配出去，       alloc(1)+ ┅+alloc(n)=m 另一方面所有进程将陷入无限等待状态。可以推出       need(1)+ ┅+need(n)<n 上式表示死锁发生后，n个进程还需要的资源量之和小于n， 这意味着此刻至少存在一个进程i,need(i)=0 ,即它已获得了所需要的全部资源。既然该进程已获得了它所需要的全部资源，那么它就能执行完成并释放它占有的资源，这与前面的假设矛盾，从而证明在这个系统中不可能发生死锁。
阅读全文