Linux存储管理（3）

[本博客连载并且会持续修正，转载请注明出处：http://blog.chinaunix.net/uid-26583089-id-5733647.html]

    类似网络中每台实际的电脑是资源，ip地址也是宝贵的资源。对内存的管理，整个系统使用的实际内存是资源，各个进程的虚拟地址也是资源。

    物理内存管理

    系统通过pglist_data结构链表管理所有物理内存信息，pglist_data结构可以简单理解为，主板上装了几根内存条，就有几个pglist_data结构。
    对于只装了一根内存的机器，则只会有1个pglist_data结构。系统启动时，会检测该内存条的大小，建立一个page结构数组mem_map[]。它与实际内存上的一个个“4KB区间”平行，用于记录相应位置物理页面的管理信息。所谓为某个进程“分配”内存，正是根据mem_map[]找到空闲的物理页面，建立它与该进程的关联，并改变page状态表示已经被占用。

    下面这段内容暂时不理解没关系，只要知道内核会将不同的物理内存区间，划分到不同的zone即可：
    实际内存除了被mem_map[]“划分”成一个个的page，还被zone_struct结构“划分”到ZONE_DMA、ZONE_NORMAL、ZONE_HIGHMEM管理区。拿地球来说，如果不把医院、学校划分到固定的场地，有人生病了，才到处找可以进行治疗的地方，到上课时间了，才到处找可以容纳全校师生的地方，显然很混乱，而且可能找不到，将内存划分区域也是同样的道理。
    内存紧张时，需要将部分长时间不用的内存换出到交换分区（后面即将学习），而I/O操作本身也需要内存，所以必须设置一个ZONE_DMA区域，保证任何情况下，都满足I/O操作对内存的要求；
    3~4GB内核空间，如果完全按偏移3GB的规则映射到0~1GB物理内存，内核就无法访问1GB以上的物理内存，所以又在3GB+896MB划分一条界限，3GB~3GB+896MB仍按照偏移3GB的规则映射，相应的，将896MB以下的物理内存划分到ZONE_NORMAL区域，3GB+896MB~4GB与896MB用于与896MB以上的物理内存“动态”映射，相应的，将896MB以上的物理内存划分到ZONE_HIGHMEM区域。另外ZONE_HIGHMEM又划分为vmalloc区、永久映射区、固定映射区。
    然而，用户虚拟空间有3G之大，通常都是与1GB以上物理内存建立映射，内核又有权限访问用户空间，如何理解“内核如果不划分3GB~3GB+896MB用于映射高端内存，就无法访问1GB以上的物理内存”？
    首先说明，从用户态切换到内核态，仅仅是指当前进程有访问内核空间（3~4GB范围的虚拟空间）的权限了，并且在切回用户态之前，必须按照内核代码的逻辑执行，仅此而已。从用户态切换到内核态，并不修改CR3寄存器，current_task()也还能获取到当前用户进程的task_struct结构（将来学完进程调度就会理解），要不然怎么切回来呢，是吧。
    用户态切换到内核态，“进程上下文”没变，不要误认为切换到内核进程了，系统中只有一个0号进程是内核进程。之前在论坛上看过一个问题：“中断处理函数为什么不能睡眠”，有些朋友提到“中断上下文”、“进程上下文”之类的。我个人理解，跟这些都没关系，只是为了减轻中断处理函数的实现负担而已，不用考虑可重入性。比如进程A进入中断处理函数并睡眠，与内核从其它地方进入睡眠并没有什么不同，都会导致一次进程调度，它唯一要考虑的是调度的进程B也可能进入该中断处理函数，进程A再次被调试时，也同样都是从睡眠的地方继续执行。
    回到问题上，内核指令访问一个1~3GB的虚拟地址时，仅仅是在内核态访问了一个映射给用户进程的私有物理地址，不是出于“公共事业”访问的。
    

    伙伴算法
    typedef struct free_area_struct {
        struct list_head free_list;
        unsigned int *map;
    } free_area_t;

    每个zone，使用free_area_t free_area[10]数组，管理自己地盘上的空闲pages。
    假设某个zone总共有16个页面（参考：http://www.cnblogs.com/zhaoyl/p/3695517.html）
 
    order(0)将原始页面两两划分，得到8对“伙伴”，order(1)将order(0)划分结果两两划分，得到4对“伙伴”，order(2)将order(1)划分结果两两划分，得到2对“伙伴”，order(3)将order(2)划分结果两两划分，得到1对“伙伴”。每对“伙伴”中，一个伙伴完全空闲（黑色数字），另一个不是（蓝色数字），则相应位为1，否则为0。
    显然，最初free_area[0]、free_area[1]、free_area[2]、free_area[3]的位图内容都为0，free_list链表都为空，整个页面块[0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]通过mem_map[0]挂在free_area[4].free_list链表上。

    1. free_area[n].free_list
    用于挂系统中所有2^n大小的连续空闲页面块，比如[8,9]为2个（2^1）连续空闲页面块，将mem_map[8]链入free_area[1].free_list；[12,13,14,15]为4个（2^2）连续空闲页面，将mem_map[12]链入free_area[2].free_list。

    [9,10]也是连续2个空闲页面，为什么不将mem_map[9]链入free_area[1].free_list？
    因为从0开始两两划分，只会出现[8,9]、[9,10]，不可能出现[9,10]这样的划分，这正是伙伴算法的一个缺点，碎片化严重，比如只剩下9、10两个空闲页面，却不能分配到连续的2个页面。

    [12,13]也是连续2个空闲页面，为什么不将mem_map[12]链入free_area[1].free_list？
    因为[12,13,14,15]作为一个更大的块，挂在free_area[2].free_list了，当需要分配2个连续页面，free_area[1].free_list又为空时，会通过切割这块大的，得到[12,13]或[14,15]。

    2. free_area[n].map
    先不防假设没有这个成员，想象最初状态下，分配2个连续页面再释放会出现什么样的情况。
    首先到free_area[1].free_list，尝试找到一个刚好大小的，显然找不到，就往更大块的区域找，结果在free_area[4].free_list上找到一个16页面，然后切成2个8页面，一份挂到free_area[3].free_list，一份再切成2个4页面，一份挂到free_area[2].free_list，一份再切成2个2页面，一份挂到free_area[1].free_list，一份作为分配到的内存。当释放这2个页面时，就是将它链入free_area[1].free_list。
    这样，经过一次分配释放的过程，16个页面本是连续的，却被算法本身切的七零八碎。所以，使用位图记录页面的连续信息，从而释放内存时，有依据将小块合并为大块。

    位图中，将“1”设计为“一个伙伴完全空闲，另一个不是”的含义，是非常值得体会的。
    特别注意的是，千万别将位图中的“1”误认为“伙伴中有可以分配的内存”。分配时并不依赖位图，只可能更新位图，释放时通过位图信息进行合并。
    比如order(0)对于[8,9]这对伙伴的标记为0，8、9页面却是空闲的，只是说不能按1个页面取走，否则就将它“打碎”了。显然1个页面更应该从[4,5]或[10,11]分配，即使没有[4,5]和[10,11]，确实需要将它“打碎”，也只能先“摘下大块”。

    虚拟空间管理
    明白虚拟地址也是资源这个道理，理解虚拟空间的管理也就不难了，它比物理页面的管理要简单的多。每个进程的虚拟地址使用，都是由mm_struct结构管理，记录哪些虚拟地址已经与物理地址建立映射，或即将与物理地址映射。如同Linux存储管理（1）举的“剧本+演员”例子，戏剧要想顺利拍摄出来，导演必须记录剧本里的哪些角色已经安排了哪位演员表演，哪些角色以后不再会出现，以及哪些角色即将上场等。