中国科学技术大学计算机系 陈香兰（0512－87161312） xlanchen@ustc.edu.cn Autumn 2009 Linux操作系统分析 中国科学技术大学计算机系 陈香兰（0512－87161312） xlanchen@ustc.edu.cn Autumn 2009
内存管理
内存管理 在前面已经提到： RAM的其余部分称为动态存储器（dynamic memory） Linux如何有效地利用x86的分段和分页机制把逻辑地址转换为物理地址 RAM的某些部分永久地分配给内核，用以存放内核代码以及静态数据 RAM的其余部分称为动态存储器（dynamic memory） 2018/12/7 Linux OS Analysis
Linux内核的前512个页框（假定内核所需内存<1MB，from ULK2） 不可用的页框 可用的页框 内核代码 初始化过的内核数据 未初始化过的内核数据 2018/12/7 Linux OS Analysis
动态存储器 进程和内核都需要动态存储器 属于稀缺资源 整个系统的性能取决于如何有效地管理动态存储器 对动态存储器的使用要进行优化 原则： 对于动态存储器要尽可能做到： 按需分配，不需要时释放 2018/12/7 Linux OS Analysis
主要内容 内核如何给自己分配动态存储器 页框管理 小内存管理 非连续存储区管理 2018/12/7 Linux OS Analysis
1、页框管理 Linux采用页作为内存管理的基本单位 Linux采用的标准的页框大小为4KB 例如：512M的物理内存对应于？？？个页框？ 由分页单元引发的缺页异常很容易得到解释 4KB是大多数磁盘块大小的倍数 传输效率高 管理方便 例如：512M的物理内存对应于？？？个页框？ 2018/12/7 Linux OS Analysis
内核必须记录每个页框的当前状态 哪些属于进程，哪些存放了内核代码/数据 对于动态存储器中的页框：是否空闲，即是否可用 如果一个页框不可用，内核需要知道是谁在用这个页框 用户态进程、动态分配的内核数据结构、静态的内核代码、页面cache、设备驱动程序缓冲的数据等等 2018/12/7 Linux OS Analysis
页描述符 内核使用页描述符来跟踪管理物理内存 每个物理页框都用一个页描述符表示 页描述符用struct page的结构描述 参见mm_types.h 所有物理页框的描述符，组织在mem_map的数组中 2018/12/7 Linux OS Analysis
mem_map数组 相当于物理内存的一个缩影 每个物理页框，使用一个struct page表示，它们组织在mem_map数组中 2018/12/7 Linux OS Analysis
页描述符中的各个字段将在用到时再逐步介绍，首先看一下 count：页的使用引用计数器 0：空闲 >0：页已经分配给一个或多个进程或用户某些内核数据结构 flags：页框状态，最多可以有32个，每个使用一个位表示 2018/12/7 Linux OS Analysis
页框状态 2018/12/7 Linux OS Analysis
页描述符将会占用很大的一段空间 由于每个struct page结构小于64个字节，因此1MB的内存需要使用约4个页面来存放mem_map数组 2018/12/7 Linux OS Analysis
关于NUMA 不考虑 物理内存被划分为若干个node 存取时间不等 考虑CPU局部性 Node使用数据结构pg_data_t描述 每个node被划分成若干个zone 2018/12/7 Linux OS Analysis
存储区(Memory Zones) 在一个理想的体系结构中，一个页框就是一个物理存储单元，可以用于任何事情，例如 存放内核数据/用户数据/缓存磁盘数据等 实际上存在硬件制约：一些页框由于自身的物理地址的原因不能被一些任务所使用，例如 ISA总线的DMA控制器只能对ram的前16M寻址 在一些具有大容量ram的32位计算机中，CPU不能直接访问所有的物理存储器，因为线性地址空间不够 2018/12/7 Linux OS Analysis
ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM 为了应付这种限制，Linux把具有同样性质的物理内存划分成——区(zones) Linux把物理存储器划分为4个区 ZONE_DMA ZONE_DMA32 (未见用） ZONE_NORMAL ZONE_HIGHMEM 参见枚举类型zone_type 896MB 16MB MAX ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM 物理内存 2018/12/7 Linux OS Analysis
ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM ZONE_DMA 和ZONE_NORMAL区 包含存储器的“常规”页，通过把它们映射到线性地址空间的3GB以上，内核就可直接访问 而ZONE_HIGHMEN区 中包含的存储器页面不能由内核直接访问 3GB 3GB+16MB 3GB+896MB 4GB <3G 线性空间 × ZONE_DMA ZONE_NORMAL ZONE_HIGHMEM 物理内存 16MB 896MB MAX 2018/12/7 Linux OS Analysis
每个zone使用struct zone表示 关键：free_area 小结： Mem_map、node、zone之间的关系 2018/12/7 Linux OS Analysis
动态内存 内存布局： 动态内存及引用它的一些值 2018/12/7 Linux OS Analysis
请求页框 内核实现了一种底层的内存分配机制，并提供了几个接口供其他内核函数调用。 分配： 释放 alloc_pages/alloc_page/alloc_pages_node/alloc_pages_current/… __get_free_pages/__get_free_page/__get_dma_pages/get_zeroed_page 释放 free_pages/__free_pages/free_page/__free_page 2018/12/7 Linux OS Analysis
调用关键函数：get_page_from_freelist 2018/12/7 Linux OS Analysis 调用关键函数：get_page_from_freelist
类似alloc_pages，但是返回第一个 所分配页框的线性地址 分配一个页框，返回值同上 用来分配适用于DMA的页框 2018/12/7 Linux OS Analysis
这个函数与__get_free_page基本等价， 差别在于它把所分配页框中的页面数据 全部清0。 这在给用户态的空间分配页框时候很有 用。因为这个页框虽然是可被分配的， 但是里面的数据可能包含了内核的一些 敏感信息。 清0，可以避免信息泄露 2018/12/7 Linux OS Analysis
关于unsigned int gfp_mask 指明可在何处并以何种方式查找空闲的页框 GFP_ATOMIC， 这种分配是高优先级的并且不能睡眠。一般在中断处理程序，下半部分和其他不能睡眠的场合下使用 GFP_KERNEL， 这是普通的分配模式，允许睡眠。一般在用户进程可能调用到的内核函数中使用，这个时候进程是可以安全的睡眠的 GFP_DMA， 设备驱动程序需要DMA内存时使用 2018/12/7 Linux OS Analysis
关于gfp_mask的进一步解释 标志位及其含义 2018/12/7 Linux OS Analysis
2018/12/7 Linux OS Analysis
等等 2018/12/7 Linux OS Analysis
释放页框 如果page对应的页框不是被保留的页框(PG_reserved标志为0)，就 把描述符的count字段减1。如果count变为0，就调用释放 与上一个函数类似，只是第一个参数是要释放的 第一个页框的线性地址addr 2018/12/7 Linux OS Analysis
在内核中释放页框时要非常小心，必须确保只释放了所请求的页框，否则内核可能会崩溃 page = __get_free_page(GFP_KERNEL,3); If (!page){ /*如果内存不足，分配失败，必须在这里处理这个失败*/ } /*现在’page’变量指向了8个连续页框的起始线性地址*/ free_pages(page,3); /*现在页框被释放，不应该再对page中存放的线性地址进行操作*/ 2018/12/7 Linux OS Analysis
页框的管理 内核要为分配一组连续的页框建立一种稳定、高效的分配策略 这种策略要解决（外部）碎片问题： 频繁的请求和释放不同大小的一组连续页框，必然导致在物理页框中分散许多小块的空闲页框 这样，即使有足够的空闲页框满足请求，但要分配一个大块的连续页框可能就无法满足了 2018/12/7 Linux OS Analysis
基于下面的原因，Linux内核首选第二种方法 有两种办法可以避免这样的碎片 利用MMU把一组非连续的物理空闲页框映射到连续的线性地址空间 使用一种适当的技术来记录现存的空闲连续页框的情况，以尽量避免为满足对小块的请求而把大块的空闲块进行分割 基于下面的原因，Linux内核首选第二种方法 在某些情况下，必须使用连续的页框，如DMA 尽量少的修改内核页表 2018/12/7 Linux OS Analysis
buddy算法（伙伴算法） Linux使用著名的伙伴算法来解决碎片问题。 每个块的第一个页框的物理地址是该块大小的整数倍 例如：大小为16个页框的块，其起址是16×4KB的倍数 2018/12/7 Linux OS Analysis
伙伴的定义 例如：0和1是伙伴，1和2不是伙伴 两个伙伴的大小必须相同，物理地址必须连续 事实上伙伴是通过对大块的物理内存划分获得的 假定伙伴的大小为b 那么第一个伙伴的物理地址必须是2×b×4KB对齐 事实上伙伴是通过对大块的物理内存划分获得的 假如从第0个页面开始到第3个页面结束的内存 每次都对半划分，那么第一次划分获得大小为2页的伙伴 进一步划分，可以获得大小为1页的伙伴，例如0和1，2和3 1 2 3 1 2 3 2018/12/7 Linux OS Analysis
数据结构 Linux为每个zone使用各自独立的伙伴系统 每个伙伴系统使用的主要数据结构为： 空闲内存管理数组free_area 2018/12/7 Linux OS Analysis
mem_map数组 空闲内存管理数组 前面介绍过的页描述符数组 每个页描述符描述一个物理页框 整个mem_map数组描述整个zone中的所有的物理内存 空闲内存管理数组 空闲内存按照伙伴管理的方法进行组织 使用free_area结构 2018/12/7 Linux OS Analysis
伙伴 当两个伙伴都为空闲的时候，就合并成一个更大的块 该过程将一直进行，直到找不到可以合并的伙伴为止 寻找伙伴 给定一个要释放的空闲块 找到其伙伴 查看其状态：合并 or 不合并 2018/12/7 Linux OS Analysis
举例 假设有128MB的ram。 假设要请求一个大小为128个页框的块(0.5MB)。 128MB最多可以分成215=32768个页框，214=16384个8KB（2页）的块 或213=8192个16KB（4页）的块，直至64个大小为512个页的块 假设要请求一个大小为128个页框的块(0.5MB)。 算法先free_area[7]中检查是否有空闲块（块大小为128个页框） 若没有，就到free_area[8]中找一个空闲块（块大小为256个页框） 若存在这样的块，内核就把256个页框分成两等份，一半用作满足 请求，另一半插入free_area[7]中 如果在free_area[8]中也没有空闲块，就继续找free_area[9]中是否有 空闲块。 2018/12/7 Linux OS Analysis
如果free_area[9]也没有空闲块，内存不够，返回一个错误 信号 若有，先将512分成伙伴，一个插入free_area[8]中，另一 个进一步划分成伙伴，取其一插入free_area[7]中，另一个 分配出去 如果free_area[9]也没有空闲块，内存不够，返回一个错误 信号 2018/12/7 Linux OS Analysis
内存的分配与回收 阅读相关代码 关键：nr_free __free_one_page __rmqueue __free_pages __free_pages_ok free_one_page mm/page_alloc.c buffered_rmqueue get_page_from_freelist __alloc_pages_internal __alloc_pages 2018/12/7 Linux OS Analysis
2018/12/7 Linux OS Analysis
2018/12/7 Linux OS Analysis
页框管理小结 页描述符 Mem_map数组 Zone 空闲页框的管理 空闲页框管理 伙伴算法 Zone_dma 空闲页框管理 Zone_normal Zone_highmem 空闲页框管理 Mem_map 数 组 物理内存：highmem 物理内存： DMA 物理内存： Normal 线性空间(<3GB) 线 性 空 间 ( 3GB~4GB) 2018/12/7 Linux OS Analysis
2、内存区管理(memory area) 单单分配页面的分配器肯定是不能满足要求的 内核中大量使用各种数据结构，大小从几个字节到几十上百k不等，都取整到2的幂次个页面那是完全不现实的 早期内核的解决方法是提供大小为2,4,8,16,...,131056字节的内存区域 需要新的内存区域时，内核从伙伴系统申请页面，把它们划分成一个个区域，取一个来满足需求 如果某个页面中的内存区域都释放了，页面就交回到伙伴系统 2018/12/7 Linux OS Analysis
但这种分配方法有许多值得改进的地方： 不同的数据类型用不同的方法分配内存可能提高效率。比如需要初始化的数据结构，释放后可以暂存着，再分配时就不必初始化了 内核的函数常常重复地使用同一类型的内存区，缓存最近释放的对象可以加速分配和释放 对内存的请求可以按照请求频率来分类，频繁使用的类型使用专门的缓存，很少使用的可以使用通用缓存 使用2的幂次大小的内存区域时硬件高速缓存冲突的概率较大，有可能通过仔细安排内存区域的起始地址来减少硬件高速缓存冲突 缓存一定数量的对象可以减少对buddy系统的调用，从而节省时间并减少由此引起的硬件高速缓存污染 2018/12/7 Linux OS Analysis
Linux2.6.26中 SLOB Allocator: Simple List Of Blocks Slab Slub：slab的一个变种 NUMA Slab Slub：slab的一个变种 Kmalloc/kfree 本课介绍基本的slab算法 2018/12/7 Linux OS Analysis
slab分配器 slab分配器体现了这些改进思想 slab分配器把内存区看成对象 slab分配器把对象分组放进高速缓存。 每个高速缓存都是同种类型内存对象的一种“储备” 例如当一个文件被打开时，存放相应“打开文件”对象所需的内存是从一个叫做filp(file pointer)的slab分配器的高速缓存中得到的 也就是说每种对象类型对应一个高速缓存 2018/12/7 Linux OS Analysis
每个高速缓存被分成多个slabs，每个slab由一个或多个连续的页框组成，其中包含一定数目的对象 2018/12/7 Linux OS Analysis
每个slab有三种状态：全满，半满，全空 半满介于两者之间 当内核函数需要一个新的对象时， 优先从半满的slab满足这个请求 否则从全空的slab中取一个对象满足请求 如果没有空的slab则向buddy系统申请页面生成一个新的slab 2018/12/7 Linux OS Analysis
高速缓存描述符和slab描述符之间的关系 2018/12/7 Linux OS Analysis
普通和专用高速缓存 每个高速缓存使用kmem_cache表示 普通高速缓存根据大小分配内存 专用高速缓存根据类型分配 26个，2组（一组用于DMA分配，另一组用于常规分配） 每组13个，大小从25=32个字节，到217=132017个字节 数据结构cache_sizes 数组：malloc_sizes 专用高速缓存根据类型分配 2018/12/7 Linux OS Analysis
阅读文件kmalloc_sizes.h 2018/12/7 Linux OS Analysis
2018/12/7 Linux OS Analysis
slab分配器提供的接口 创建专用高速缓存：kmem_cache_create 撤销专用高速缓存：kmem_cache_destroy 从专用高速缓冲中分配和释放 从高速缓存中分配/释放一个内存对象 kmem_cache_alloc/kmem_cache_free 从普通高速缓存中分配和释放 kmalloc/kfree 举例说明使用情况 2018/12/7 Linux OS Analysis
slab分配器和伙伴系统的接口 slab分配器调用kmem_getpages()来获取一组连续的空闲页框 相应的有kmem_freepages()来释放分配给slab分配器的页框 2018/12/7 Linux OS Analysis
如果编写的内核模块有许多创建和释放数据结构的操作，可以考虑调用前面所述的slab分配器的接口创建一个高速缓存 这样可以大大减少内存的访问时间 2018/12/7 Linux OS Analysis
3、非连续存储区管理 把线性空间映射到一组连续的页框是很好的选择 有时候不得不将线性空间映射到一组不连续的页框 优点：避免碎片 2018/12/7 Linux OS Analysis
为非连续内存区保留的线性地址空间 VMALLOC_START~VMALLOC_END 2018/12/7 Linux OS Analysis
非连续存储区的描述符vm_struct Vmalloc等分配一个非连续存储区 Vfree释放非连续线性区间 include/linux/vmalloc.h mm/vmalloc.c 2018/12/7 Linux OS Analysis
页框管理、内存区管理、非连续存储区管理之间的关系 使用分配到缓冲区 使用分配到线性区 直接使用分配到的 页框，例如进程描述符 使用slab算法，以若干 个字节为单位进行管理 非连续存储区，映射 到非连续的物理页框上 分配出 一些页框 分配出 一些页框 物理内存：页框管理，以页框为单位进行管理 2018/12/7 Linux OS Analysis
作业 Linux的页框管理采用什么算法？简述该算法。 Linux中的slab算法的用途是什么？简述该算法。 什么是非连续内存区？ 2018/12/7 Linux OS Analysis