当前课程知识点：Linux 内核分析与应用 > 第4章 内存管理 > 4.4 物理内存分配与回收机制（下） > Video
大家好 今天我们来讲一下内存分配
回收机制的第二讲
从这个图我们可以看出呢
从用户进程发出内存分配请求开始
到内核最终分配出物理内存
这中间内核要做大量的工作
那么上一讲我们概要的介绍了Vmalloc和Kmalloc
最终它们都要调用伙伴算法
通过get_free_page内核函数获得物理内存
那么目前呢有两种类型的计算机
分别以不同的方法来管理物理内存
它们分别是NUMA（non-uniform memory access）计算机
这是一种多处理器的计算机
是每个CPU拥有各自的本地内存
这样的划分使每个CPU呢
都能以较快的速度访问本地内存
而各个CPU之间通过总线连接起来
这样也可以访问其它CPU的本地内存
只不过呢速度比较慢而已
另外一种计算机叫UMA（uniform memory access）计算机
将可用内存以连续的方式组织起来 如图所示
为了兼容UMA模型呢 内核引入了内存节点
那么每个节点就关联了一个CPU
而各个节点又被划分为几个内存区
每个内存区中又包含了若干个页框
物理内存在逻辑上呢就
被划分为三级结构
分别使用三个数据结构pg_data_t zone和page来描述
节点 区和页框
UMA计算机中每个CPU的物理内存呢
我们称为一个内存节点
内核通过pg_data_t数据结构来描述
那么系统内的所有的节点就形成了一个双链表
UMA模型的物理内存只对应一个节点 也就是说
整个物理内存形成一个节点
因此上述的节点链表中也只有一个元素
关于内存管理区的话 我们说呢
各个节点划分为若干个区
也就是说物理内存的进一步细分
那么通过下面几个宏来标记物理内存的不同区
一个是ZONE_DMA
标识适合DMA的内存区
ZONE_NORMAL可以直接映射到内核空间的物理内存
ZONE_HIGHMEM叫做高端物理内存
那么32位和64位操作系统
对内存区管理上有什么差异呢
最大的区别是64位操作系统呢
不再有高端内存的概念
可以支持大于4GB的内存寻址
而且ZONE_NORMAL的空间将扩展到
64GB或者128GB
而且64位系统上的映射就变得更加的简单了
那么这三种数据结构之间它有什么关系呢
首先物理内存被划分为内存的节点
用pg_data_t来表示
那么每个节点实际上是关联了一个CPU
那么对于NUMA结构来说呢
因为有多个节点 因此各个节点就形成了一个链表
而每个节点又被划分成了几个内存管理区
在一个内存管理区中则是一个个的页框
页框是内存管理的基本单位
它可以存放任何类型的数据
下面我们对伙伴算法先进行一个概述
那么物理内存如何进行分配
Linux内核主要采用了伙伴算法
为什么叫伙伴算法呢 实际上呢就是
大小相同
物理地址连续的两个页框就被称为伙伴
那么Linux的伙伴算法把所有的空闲页面呢
分为多个块链表 如图所示
这个链表的个数呢默认值为11
每个链表中的一个块含有2的幂次个页面
也就是页块或者简称为块
比如说第一个链表里面是2的零次方个
页面 第二个是2的1次方个那么就分别是一个页面
两个页面 每个链表中的页块的大小呢它是不一样的
那么与伙伴算法有关的数据结构是什么呢
我们说每个物理页框它是要对应一个struct page实例
这是页框的描述数据结构
而每个内存区关联的是怎么样的一个数据结构呢
是struct zone的实例
那么该结构使用什么数据结构来描述空闲的页框呢
用free_area来描述
下面我们来对伙伴算法的分配原理给一个简要的解说
伙伴算法的分配原理是什么呢
就是说如果要分配阶为n的页框块的话
那么先从第n条页框链表中呢
查找是否存在这么大小的空闲页块
如果有的话那就分配
否则的话则在第n+1条链表中继续查找
直到找到为止
如果申请大小为8的页块的话
那么分配阶就是为3
但却在页块大小为32的链表中找到了空闲块
则先将这32个页面呢
对半等分
而前一半呢作为分配使用
另一半作为新元素插入下一
级大小为16的链表中
继续将前一半大小为16的页块等分
一半分配 另一半插入大小为8的链表中
那么页框的分配到底是怎么样来实现的呢
在这里我们主要介绍两个函数
第一个函数__rmqueue_smallest()是在指定的内存区上呢
从所请求的分配阶呢
对应的链表开始查找所需大小的空闲块
如果不成功则从高一阶的链表上继续查找
那么第二个函数expand()为分裂函数
如果所得到的内存块呢
大于所请求的内存块 则按照伙伴算法的分配原理呢
将大的页框块分裂成小的页框块
那么这是我们第一个函数的实现的源码
下面我们对这个函数的主要语句给予简单的介绍
实际上这个函数的实现是比较简单的
从当前指定的分配阶呢
到最高分配阶依次先进行遍历
在每次遍历分配阶的链表中呢
根据参数迁移类型呢
选择正确的迁移队列
根据以上的限定条件
当选定一个页块链表后呢
只要该链表不为空
就说明可以分配该阶对应的页块
一旦选定在当前遍历的分配阶链表上分配页框
那么就通过list_entry将该页块从链表中移除
以上这个过程通过rmv_page_order()完成
此外还要更新页块链表nr_free的值
那么下面是分裂函数expand（）
这是这个函数的源代码
那么分裂函数的实现也是显而易见的
它完全遵照伙伴算法的分裂原理
这里有两个分配阶 一个呢是申请页框时指定的低阶（low）
一个是在上级函数中遍历时所选定的高阶(high)
该函数从高阶(high)分配阶开始
递减向低阶（low）遍历也就是说呢从
较大的页块开始呢依次分裂
那么什么是物理内存分配器呢
基于伙伴算法 每CPU高速缓存
和slab高速缓存形成了两种内存分配器
那么第一种呢是分区页框分配器（zoned page frame allocator）
处理对连续页框的内存分配请求
那么第二种呢是slab分配器
我们在上一讲已经讲到了
它将各种分配对象分组放进高速缓存中
也就是说每个高速缓存都对同类型分配对象的一种“储备”
如图所示是分区页框分配器
那么分区页框管理器分为两大部分
前端的管理区分配器和伙伴系统
管理区分配器
负责搜索一个能满足请求页框大小的管理区
在每个管理区中具体的页框分配工作呢是由伙伴系统负责的
为了达到更好的系统性能呢
单个页框的申请工作呢
直接通过每CPU页框高速缓存来完成
下面我们来给出页框分配函数的关系图
内核中有六个稍有差别的函数和宏来请求页框
那么图中四个绿色和两个蓝色来表示这六个函数
它们将核心的分配函数
也就是最底层的那个函数__alloc_pages_nodemask进行分装
从而形成满足不同分配需求的分配函数
那么通过上面的介绍我们来一个总结
从用户态到内核态的内存分配过程
当用户程序通过系统调用
申请内存的时候首先陷入内核
建立虚拟内存空间的映射
获得一块虚拟内存区VMA
当进程对这块虚存区进行访问的时候呢
如果物理内存尚未分配
那么此时发生一个缺页异常
通过get_free_page申请一个或者多个物理页面
并将此物理内存和虚拟内存的映射关系写入页表
通过前面的介绍我们对物理内存的分配过程呢
进行了一个比较系统的介绍
那么这个介绍还依然是比较简单的
如果要深入了解的话 我们需要看相关的参考资料
那么同样的我们需要查看《深入理解Linux内核》的第三版的第八章
还有http://edsionte.com/techblog/本博客中
“内存管理那些事儿”这个栏目里呢
有比较详细的关于内存管理的系列文章
同样呢我们来带着思考离开
在物理内存为1G的计算机中呢
能否malloc（1.6G）呢 那么
我们要给出“能”是为什么 “不能”为什么
本讲呢我们就讲到这里
谢谢大家
-1.1 Linux操作系统概述
-1.2 Linux内核结构以及内核模块编程
--Video
-1.3 Linux内核源码中的双链表结构
--Video
-1.4 源码分析-内核中的哈希表
--Video
-1.5 动手实践-Linux内核模块的插入和删除
--Video
-第1章 概述--章节测验
-2.1 内存管理之内存寻址
--Video
-2.2 段机制
--Video
-2.3分页机制
--Video
-2.4 动手实践-把虚拟地址转换成物理地址
--Video
-第2章 内存寻址--章节测验
-3.1 进程概述
--Video
-3.2 Linux进程创建
--Video
-3.3 Linux进程调度
--Video
-3.4 动手实践-打印进程描述符task_struct中的字段
--Video
-3.5工程实践-基于内核模块的负载监控
--Video
-第3章 进程管理--章节测验
-4.1 Linux内存管理机制
--Video
-4.2 进程用户空间管理机制
--Video
-4.3 物理内存分配与回收机制（上）
--Video
-4.4 物理内存分配与回收机制（下）
--Video
-4.5 动手实践-Linux内存映射基础（上）
--Video
-4.6 动手实践-Linux内存映射实现（中）
--Video
-4.7 动手实践-Linux内存映射测试（下）
--Video
-4.8 初学者对内存管理的常见疑惑
-第4章 内存管理--章节测验
-5.1 中断机制概述
--Video
-5.2 中断处理机制
--Video
-5.3 中断下半部处理机制
--Video
-5.4 时钟中断机制
--Video
-5.5 动手实践-中断上半部的代码分析及应用
--Video
-5.6 动手实践-中断下半部的代码分析及应用
--Video
-第5章 中断--章节测验
-6.1 Linux中的各种API
--Video
-6.2 系统调用机制
--Video
-6.3 动手实践-添加系统调用（系统调用日志收集系统）
--Video
-第6章 系统调用--章节测验
-7.1 内核同步概述
--Video
-7.2 内核同步机制
--Video
-7.3 动手实践-内核多任务并发实例（上）
--Video
-7.4 动手实践-内核多任务并发实例（下）
--Video
-第7章 内核同步--章节测验
-8.1 虚拟文件系统的引入
--Video
-8.2 虚拟文件系统的主要数据结构
--Video
-8.3 文件系统中的各种缓存
--Video
-8.4 页高速缓存机制以及读写
--Video
-8.5 动手实践-编写一个文件系统（上）
--Video
-8.6 动手实践-编写一个文件系统（中）
--Video
-8.7 动手实践-编写一个文件系统（下）
--Video
-第8章 文件系统--章节测验
-9.1 设备驱动概述
--Video
-9.2 I/O空间管理
--Video
-9.3 设备驱动模型
--Video
-9.4 字符设备驱动程序简介
--Video
-9.5 块设备驱动程序简介
--Video
-9.6 动手实践-编写字符设备驱动程序
--Video
-9.7工程实践-编写块设备驱动的基础（上）
--Video
-9.8 工程实践-块设备驱动程序分析（中）
--Video
-9.9 工程实践-块设备驱动程序实现（下）
--Video
-第9章 设备驱动--章节测验
-致谢与说明
--Video
