《Linux原理与结构》课件第6章.ppt

1、1 1第六章 物理内存管理6.1 内存管理系统组成结构内存管理系统组成结构6.2 伙伴内存管理伙伴内存管理6.3 逻辑内存管理逻辑内存管理6.4 对象内存管理对象内存管理2 2在操作系统营造的虚拟社会中，除了被时钟管理部分管理的时间之外，另一个重要的基石就是空间。对空间的管理是操作系统的另一项核心工作。操作系统所管理的空间可大致分为内存空间和外存空间，其中内存空间可被处理器直接访问的，是最基础的空间。内存空间是计算机系统中的重要资源，操作系统中的进程运行在内存空间中，操作系统本身也运行在内存空间中，离开了内存空间，计算机系统将无法运行。另一方面，内存空间又是计算机系统中的紧缺资源，操作系统及其

2、管理的所有进程共享同一块物理内存空间，其容量似乎永远都无法满足进程对它的需求。因而有必要对内存空间实施严格的、精细的管理。3 3内存管理的工作艰巨而繁琐，可大致分成两大部分：物理内存管理部分管理系统中的物理内存空间，负责物理内存的分配、释放、回收等；虚拟内存管理部分管理进程的虚拟内存空间，负责虚拟内存的创建、撤销、换入、换出及虚拟地址到物理地址的转换等。物理内存管理的主要任务是快速、合理、高效地分配与回收物理内存资源以尽力提高其利用率；虚拟内存管理的主要任务是为进程模拟出尽可能大的内存空间并实现它们间的隔离与保护。在操作系统长期的发展过程中，内存管理部分由简到繁，不断演变，正逐步走向成熟。4

3、4为解决复杂的内存管理问题，Linux采用了分而治之的设计方法，将内存管理工作交给几个既相互独立又相互关联的管理器分别负责。这些内存管理器各司其职，互相配合，共同管理系统中的内存空间，如图6.1所示。6.1 内存管理系统组成结构内存管理系统组成结构5 5图6.1 内存管理系统的组成结构6 6Linux的物理内存管理子系统运行在内核空间，仅为内核提供服务。内核需要的物理内存通常是连续的，而且应该有内核线性地址(内核用线性地址访问物理内存)。如果按申请的规模划分，内核对物理内存的需求大致可分为中规模(几个物理上连续的页)、小规模(若干字节)和大规模(多个逻辑上连续的页)等几类。为了满足内核对物理内

4、存的不同需求，Linux将物理内存管理子系统进一步划分成三个管理器，即伙伴内存管理器、对象内存管理器和逻辑内存管理器。7 7伙伴内存管理器是物理内存的真正管理者，是物理内存管理的基础。伙伴内存管理器以页块(若干个连续的物理页)为单位分配、释放、回收物理内存，虽比较粗放，但极为快速、高效，且不会产生外部碎片。对象内存管理器建立在伙伴内存管理器之上，是一种细粒度的物理内存管理器。对象内存管理器将来自伙伴内存管理器的内存页块划分成小内存对象，以满足内核对小内存的需求，并负责将回收到的小内存对象组合成内存页块后还给伙伴内存管理器。8 8由于伙伴内存管理器只能提供物理上连续的内存，常常无法满足内核对大内

5、存的需求，因而Linux实现了逻辑内存管理器，专门为内核提供逻辑上连续、物理上可不连续的大内存服务。在系统初始化期间，Linux还提供了一个初始内存管理器Bootmem，用于向内核提供物理内存服务。但在伙伴内存管理器启动之后，Bootmem已让出管理权，被停止了工作。9 9除内核之外，内存管理的主要服务对象是进程。与内核不同，每个进程都需要一块容量足够大的独立的虚拟内存，用于暂存它的程序、数据、堆栈等。因而内存管理的另一个核心工作是利用有限的物理内存和外存设备为系统中的每个进程都模拟出一块连续的虚拟内存，并实现各虚拟内存之间的隔离与保护。Linux中负责进程内存管理工作的是虚拟内存管理器和用户

6、内存管理器。10 10用户内存管理器运行在用户空间中，负责进程虚拟内存(在堆中)的动态分配、释放与回收(如库函数malloc()、free()等)。用户内存管理器一般在函数库(如Libc)中实现，不属于内核的组成部分，但需要内核中的虚拟内存管理器为其提供帮助。本章主要分析Linux的物理内存管理部分，虚拟内存管理部分将在第8章中讨论。11 11伙伴内存管理器管理系统中的物理内存，因采用伙伴算法而得名。所谓物理内存就是计算机系统中实际配置的内存。根据处理器与物理内存的组织关系可将计算机系统分成两大类。在UMA(Uniform Memory Access)系统中，每个处理器都可以访问到所有的物理内

7、存，且访问速度都相同。在NUMA(Non-Uniform Memory Access)系统中，处理器虽可访问到所有的物理内存，但访问速度略有差异。6.2 伙伴内存管理伙伴内存管理12 12事实上，一个NUMA系统由多个节点组成，每个节点都有自己的处理器和物理内存，处理器对节点内部内存的访问速度较快，对其它节点的内存访问速度较慢。UMA是NUMA的特例，只有一个节点的NUMA就是UMA。计算机系统中的物理内存被统一编址，其中的每个字节都有一个物理地址，只有通过物理地址才能访问到物理内存单元。在一个计算机系统中，可以使用的所有物理地址的集合称为物理地址空间。物理地址空间的大小取决于地址线的位数。1

8、3 13物理地址空间中的地址除可用于访问物理内存之外，还可用于访问固件中的ROM(如BIOS)及设备中的寄存器(如APIC中的寄存器等)。不能访问任何实体的物理地址区间称为空洞，空洞中的物理地址是无效的。在初始化时，系统已经通过BIOS int 15 h的e820服务获得了物理地址空间的布局信息，并已利用该信息完成了伙伴内存管理器的初始化。14 146.2.1 伙伴内存管理结构伙伴内存管理结构物理内存的管理方法很多，如静态分区法、动态分区法、伙伴算法等，衡量算法好坏的标准主要是效率和利用率，影响的因素主要是管理粒度。细粒度的管理具有较高的利用率，但算法比较复杂；粗粒度的管理具有较高的效率，但利

9、用率不高。伙伴内存管理器采用伙伴算法管理它的物理内存，管理的最小粒度是1页(4 KB)。为了实现页粒度的内存管理，需要一种数据结构来描述每一个物理页的使用情况。伙伴内存管理器为每个物理页准备了一个32字节的page结构，其格式如图6.2所示。15 15图6.2 page结构16 16在Linux的发展过程中，page结构在不断演变，最重要的是其中的三项：(1)标志flags是一个4字节的位图，用于描述物理页的属性或状态。常用的属性如表6.1所示。flags的前端还记录着页所属的节点和管理区的编号。(2)引用计数_count用于记录物理页的当前用户数，_count为0的页是空闲的。(3)通用链表

10、节点lru用于将page结构链入到需要的队列中。另外，page结构中还包含几个复用域，如index、freelist和free共用同一个域，它们的意义随应用场合的不同而变化。复用域的使用使page结构既可满足不同的应用需求，又不至于变得太大。17 17表6.1 物理页的属性18 18续表 19 19毫无疑问，系统中存在很多page结构，必须另外建立一种结构来组织、管理它们。最简单的管理方法是定义一个page结构数组。由于计算机系统中的物理内存页数不是固定的，因而只能在检测到物理内存大小之后动态地建立该数组。page结构数组可能很大，为节约物理内存，应尽量压缩page结构的大小。早期的Linux

11、仅在系统初始化时建立了一个page结构数组，称为mem_map。由于需要支持NUMA系统，新版本的Linux将物理内存划分成多个节点，并为每个节点建立了一个page结构数组。Linux的节点由一个名字古怪的结构描述，其主要内容如下：2020typedef struct pglist_data struct zone node_zonesMAX_NR_ZONES;/所有管理区 struct zonelist node_zonelistsMAX_ZONELISTS;/尝试序列 int nr_zones;/节点中的管理区数 struct page*node_mem_map;/page结构数组21 2

12、1 unsigned long node_start_pfn;/开始页号 unsigned long node_present_pages;/总页数，不含空洞 unsigned long node_spanned_pages;/总页数，含空洞 wait_queue_head_tkswapd_wait;/回收进程等待队列 struct task_struct*kswapd;/物理内存回收进程2222 int kswapd_max_order;/上次回收的尺寸 pg_data_t;一个pglist_data结构描述一个节点内部的物理内存，对应物理地址空间中的一块连续的地址区间，其开始页号是node

13、_start_pfn，大小是node_spanned_pages页。由于空洞的存在，节点中的实际物理页数node_present_pages可能小于node_spanned_pages。节点内部的page结构数组是node_mem_map，2323其中的每个page结构描述节点内的一个物理页，包括空洞页。系统中所有的节点结构被组织在数组node_data中。struct pglist_data*node_dataMAX_NUMNODES _read_mostly;在基于X86的个人计算机或服务器上，尽管可能配置有多个处理器，但其内存访问模型通常是UMA，因而系统中仅有一个节点，称为contig

14、_page_data。即使属于同一个节点，物理页的特性也可能不同，如有些物理页有永久性的内核线性地址而另一些物理页没有，有些物理页可用作ISA DMA而另一些物理页不能等。不同特性的物理页有着不同的用处，应采用不同的管理方法，或者说应区别对待一个节点内部的物理内存。2424伙伴内存管理器将一个节点内部的物理内存进一步划分成管理区。每个节点都可以定义2到4个管理区，其中ZONE_DMA区管理的是16 MB以下的物理内存，可供老式DMA使用；ZONE_DMA32区管理的是可供32位设备做DMA使用的物理内存(4 GB以下)，仅用于64位系统；ZONE_NORMAL区管理的是除ZONE_DMA之外的

15、低端物理内存，可供常规使用；ZONE_HIGHMEM区管理的是没有内核线性地址的高端物理内存，可供特殊使用；ZONE_MOVABLE区是虚拟的，它管理的内存来自其它几个区，都是可动态迁移的物理页，用于内存的热插拔(Memory Hotplug)和紧缩，2525其大小由命令行参数指定，缺省情况下为空。32位系统中没有ZONE_DMA32区，64位系统中没有ZONE_HIGHMEM区。内存管理区由结构zone描述，其主要内容包括如下几个：(1)开始页号zone_start_pfn表示管理区的开始位置。(2)总页数spanned_pages表示管理区的大小，含空洞。(3)可分配页数present_p

16、ages表示管理区中的可用物理内存总页数，不含空洞。(4)基准线watermark描述管理区中空闲内存的三个基准指标。2626(5)空闲页块队列free_area用于组织不同大小的空闲页块。(6)LRU队列lru用于描述区内各类物理页的最近使用情况。(7)热页队列pageset用于暂存刚被释放的单个物理页。(8)迁移类型位图pageblock_flags用于描述各页组的迁移类型。(9)预留空间总量lowmem_reserve用于记录应为其它管理区预留的内存页数。一个管理区管理一块连续的物理地址空间，其中可能包含空洞。图6.3是物理内存的一种划分方式。2727图6.3 物理内存空间的划分2828

17、图6.3中的物理内存空间由2个节点构成，其中节点1被划分成3个管理区，节点2被划分成2个管理区。两个节点间有一块空洞，节点1的第3个管理区中也有一块空洞。由于page结构数组所占空间无法再做它用，因而也被算做空洞。伙伴内存管理器以管理区为单位管理物理内存，包括单个物理页及多个连续物理页的分配、释放、回收等。虽然利用page结构数组能够实现单个物理页的管理，但却难以进行多个连续物理页的分配。为解决连续物理页的管理问题，Linux引入了页块的概念。一个页块(pageblock)就是一组连续的物理页。2929为规范起见，Linux规定页块的大小必须是2i(i=0,1,10)页，页块中起始页的编号必须

18、是页块大小的倍数。页块是一个动态管理单元，相邻的小页块可以组合成大页块，大页块也可拆分成小页块。页块以起始页为代表，起始页的编号就是整个页块的编号，起始页的page结构中记录着整个页块的管理信息。3030伙伴内存管理器以页块为单位管理各区中的物理内存，因而需要为每一种大小的空闲页块准备一个队列。Linux为每个管理区都定义了一个free_area数组，用于组织区内的空闲页块。大小为2i页的空闲页块被组织在free_area的第i队列中。第i队列中的1个大小为2i页的页块可以被划分成2个大小为2i-1页的小页块(伙伴)并挂在第i-1队列中；第i-1队列中的2个小伙伴可以被合并成大小为2i页的页块

19、并挂在第i队列中。在早期的版本中，伙伴内存管理器为每一种大小的空闲页块准备了一个队列。然而，新版本的伙伴内存管理器需要面对内存迁移问题，为每一种大小的空闲页块准备一个队列已无法满足需要。31 31所谓内存迁移就是将页块从一个物理位置移动到另一个物理位置，也就是将一个页块的内容拷贝到另一个页块中，并保持移动前后的虚拟或线性地址不变。内存迁移的需求主要来自两个方面：为了加快NUMA内存的访问速度，需要将处理器经常访问的内存迁移到离它最近的节点中；为了解决内存碎化问题，需要进行物理内存紧缩，将分散的小空闲页块合并成大页块。为了实现内存迁移，需要进一步区分页块的迁移属性。事实上，可将物理内存页块大致分

20、成五种类型，不可迁移型(MIGRATE_UNMOVABLE)页块只能驻留在物理内存的固定位置(如内核页)，不能移动；3232可回收型(MIGRATE_RECLAIMABLE)页块中的内容可先被释放而后再在新的位置上重新生成(如来自映像文件的页)；可迁移型(MIGRATE_MOVABLE)页块中的内容可被拷贝到新的位置而不改变其虚拟或线性地址(如用户进程中的虚拟页)；预留型(MIGRATE_RESERVE)页块是留给内存不足时应急使用的；孤立型(MIGRATE_ISOLATE)页块用于在NUMA的节点间迁移，不可分配。显然，同一类型的页块应集中在一起，不同类型的页块不应相互交叉。不加限制的页块分

21、配会影响页块的合并，如图6.4所示，由于第13页不可迁移，前16个空闲页就不能合并成大页块。3333图6.4 不可迁移页影响页块合并的情况3434如果可迁移型页块内部不存在不可迁移的页，那么将其中的非空闲页迁移出去之后即可合并成大的空闲页块。为了聚合同一类型的页块，伙伴内存管理器预先将区中的物理内存划分成了大小为1024页的页组，并为每个页组指定了一个迁移类型。页块的分配按照迁移类型进行。如此以来，在可迁移型页组中就不太可能再出现其它类型的页块。管理区中的位图pageblock_flags(3位一组)用于标识各页组的迁移类型，如图6.5所示。3535图6.5 页块的迁移类型3636每个物理页都

22、属于一个页组，都有一个确定的迁移类型，不管它是空闲的还是正在被使用的。当然，页组的迁移类型是可以改变的。区分页组的迁移类型与定义ZONE_MOVABLE区的作用一样，但更加精细。划分了迁移类型之后，就应为每一种类型的空闲页块准备一个队列。新版本的伙伴内存管理器为每一种大小的空闲页块准备了5个队列，分别用于组织5种不同迁移类型的空闲页块。结构free_area的定义如下：3737struct free_area truct list_head free_listMIGRATE_TYPES;/5个空闲页块队列 unsigned long nr_free;/空闲页块数;图6.6是一个管理区中的空闲页

23、块队列示意图。左边是早期的free_area，每种大小的空闲页块1个队列。右边是新的free_area，每种大小的空闲页块5个队列。3838图6.6 free_area数组与空闲页块队列39396.2.2 伙伴内存初始化伙伴内存初始化在系统初始化期间，已经进行了大量的内存初始化工作，如检测出了物理内存的布局结构，确定了系统中的节点数及各节点的管理区数，设置了伙伴内存管理器所需的节点结构、管理区结构及所有的page结构，并已将所有的空闲页块都转移到了free_area数组的MOVABLE队列中。下面几件是伙伴内存管理器专有的初始化工作。40401.确定管理区尝试序列确定管理区尝试序列伙伴内存管理

24、器管理着一到多个节点，每个节点中又包含着多个管理区。通常情况下，物理内存的申请者应告诉管理器自己想从哪个节点的哪个管理区中申请内存。伙伴内存管理器应尽量按照申请者的要求为其分配内存。当指定的管理区无法满足请求时，伙伴内存管理器可以返回失败信息，也可以尝试其它的管理区。如果允许尝试其它管理区，则应预先确定一个管理区的尝试顺序，或者说管理区的分配优先级。41 41管理区排序的基本原则是先“便宜”后“贵重”。DMA区容量有限且有特定用途，其它区中的内存无法替代，因而最为贵重。NORMAL区的容量有限，而且内核仅能使用NORMAL和DMA区中的内存(只有这两个区中的内存有内核线性地址)，因而比较贵重。

25、内核不直接访问HIGHMEM区中的内存，该区对内核的影响不大，最为便宜。一般情况下，节点间管理区的尝试顺序应该是先本地后外地，节点内管理区的尝试顺序应该是MOVABLEHIGHMEMNORMALDMA32DMA。4242当然，由于节点性质的不同，其管理区的尝试顺序也可能会有所变化。结构pglist_data的域node_zonelists中包含一个数组_zonerefs，其中记录着管理区的尝试序列。单节点上的管理区尝试序列如图6.7所示。如申请者申请DMA内存，那么仅能从DMA区中为其分配，但如果申请者申请高端内存，那么可以从HIGHMEM、NORMAL或DMA区中为其分配。4343图6.7

26、管理区尝试序列44442.预留空闲内存预留空闲内存物理内存，尤其是低端物理内存，是十分紧缺的资源，如果不加控制的话，很容易全部耗尽。一旦物理内存被耗尽，很多紧急工作将无法正常开展。当物理内存回收程序也无法正常运行时，物理内存资源将无法被回收，系统有可能不稳定甚至崩溃。因而，在任何情况下，都应该预留一部分空闲的物理内存以备急需。需要预留的空闲物理内存量记录在变量min_free_kbytes中，其大小取决于低端物理内存的总量，但不得小于128 KB，也不应大于64 MB。Linux用以下公式计算预留的最小物理内存量：4545min_free_kbytes=sqrt(lowmem_kbytes*1

27、6)其中lowmem_kbytes是低端物理内存(包括DMA和NORMAL区)总量。预留的物理内存应按比例分布在各个低端管理区内。为安全起见，高端管理区中也应适当预留一部分内存。为各管理区设定的预留物理内存量会影响到伙伴内存管理器的分配行为。一旦管理区中的空闲内存出现紧张(接近预留量)迹象，就应设法为其回收物理内存。紧张的标志是根据min_free_kbytes算出的基准线，记录在zone的watermark数组中。基准线包括三条，MINLOWRECLAIMABLEMOVABLERESERVE。可回收型：5050RECLAIMABLEUNMOVABLEMOVABLERESERVE。可迁移型：M

28、OVABLERECLAIMABLEUNMOVABLERESERVE。预留型：RESERVERESERVERESERVERESERVE，即只许分配预留页。51 514.建立热页管理队列建立热页管理队列伙伴内存管理器采用伙伴算法管理内存页块的分配和释放。分配时可能拆分页块，释放时会尽力合并页块。经典伙伴算法的问题是过于频繁的拆分与合并降低了管理器的性能。在新版本的管理区结构中，为每个处理器都增加了一个热页队列(或者说热页缓存)，用于暂存各处理器新释放的单个物理页，试图通过延迟热页的合并时机来提高伙伴内存管理器的性能。5252热页(hot page)是位于处理器Cache中的页，冷页(cold pa

29、ge)是不在处理器Cache中的页。处理器对热页的访问速度要快于冷页。管理区结构zone中的pageset是热页队列，每个处理器一个。一个热页队列由一个per_cpu_pageset结构描述，其定义如下：struct per_cpu_pageset struct per_cpu_pages pcp;s8 stat_threshold;s8 5353vm_stat_diffNR_VM_ZONE_STAT_ITEMS;_cacheline_aligned_in_smp;真正的队列在结构per_cpu_pages中，其定义如下：struct per_cpu_pages int count;/队列中的

30、页数 int high;/基准线 int batch;/批的大小 struct list_head lists3;/前三种迁移类型各有一个热页队列;5454如果新释放的单个空闲页(散页)不是MIGRATE_ISOLATE类型，伙伴内存管理器会先将其加入到热页队列(预留页与可迁移页共用一个队列)而不是free_area数组中，因而暂时不会被合并。当热页数量(count)超过基准线high时，再一次性地将其中batch个空闲页转给free_area(可能被合并)。batch大致是区中内存页数的1/4096，但必须在1到32之间，high的初值是6倍的batch。热页队列的平均长度是4*batch，

31、大约是管理区大小的千分之一，基本与处理器的L2 cache的大小相当。5555伙伴内存管理器总是试图从热页队列中分配单个物理页。当热页队列为空或缺少指定类型的页时，伙伴内存管理器会从free_area中一次性批发过来batch个指定类型的页。56566.2.3 物理页块分配物理页块分配伙伴内存管理器采用伙伴算法，以页块(2order页)为单位从free_area中分配物理内存。满足下列条件的两个页块互称为伙伴：(1)大小相等，都是2order页；(2)位置相邻，起始页编号分别是B1、B2，且|B1-B2|=2order；(3)编号的第order位相反，B2=B1 (1 order)，B1=B2

32、 (1=order)中选择页块。如果iorder，需要将所选的大页块拆分成小伙伴。在大页块拆分出来的两个小伙伴中，大序号的伙伴被插入到free_area的队列中，被选中的总是序号最小的伙伴。6464 如果整个管理区中都没有与请求者要求类型一致的页块，则从其它类型中迁移1个尽可能大的页块到要求类型的队列中，而后再次选择页块。这里的“其它类型”由迁移类型尝试序列决定，但不含RESERVE类型。如果迁移过来的页块足够大(超过半个页组)，则将整个页组改成要求类型，相当于从其它类型中迁移过来一个页组；否则保持页组的类型不变，相当于在一种类型的页组中强行分配一个其它类型的小页块。如果无法从其它类型中迁移页

33、块，则尝试从RESERVE类型中选择页块。6565(4)设置页块的管理结构，将其分配给请求者。找到所选页块中起始页的page结构，将它的private清0，_count置1。如果需要，将页块的内容全部清0。如果所选页块超过1页且请求者提出了要求，则将其组织成复合页。复合页(compound)的起始页称为头页，其余页称为尾页。在复合页中，所有页的first_page都指向起始页的page结构，第一个尾页的lru.prev中记录页块的大小、lru.next中记录页块的解构函数。6666(5)如果分配过程失败，说明系统中的物理内存出现了紧缺现象。唤醒在节点上等待的守护进程kswapd，让它去回收物理

34、内存。这些守护进程在后台运行。放松检查条件，如仅检查MIN基准线或根本不再检查基准线，而后再次尝试分配内存。如果仍然失败，则直接回收物理内存，并回收当前处理器的热页，而后再次尝试分配内存。6767 如果仍然失败，说明内存真的耗尽了(Out of Memory)，则启动进程杀手(killer)尝试停止一些进程来回收物理内存，而后再次尝试分配内存。如果仍然失败，则显示信息，通报内存分配失败。Linux的伙伴内存管理器提供了多个物理内存分配函数，其中alloc_pages()类的函数得到的是起始页的page结构，而_get_free_pages()类的函数得到的是起始页的内核线性地址。68686.2

35、.4 内核线性地址分配内核线性地址分配页块分配操作所分配的物理内存页块可能属于低端内存，也可能属于高端内存。内核可能需要访问这些内存页块，也可能不需要访问它们(仅给用户进程使用)。由于系统未为高端内存预分配内核线性地址，因而当内核需要访问来自高端的内存页块时，伙伴内存管理器必须临时为它们分配内核线性地址。Linux在内核线性地址空间(3 GB4 GB)中为高端内存预留了1024页的kmap区间(起始线性地址是PKMAP_BASE)，6969专门用于为高端内存临时指派内核线性地址。在系统初始化时，Linux已为kmap区间建立了1个页表pkmap_page_table。所谓为一个内存页分配临时的

36、内核线性地址实际就是在页表pkmap_page_table中找一个空的页表项，将其中的页基地址(Page Base Address)改为内存页的物理地址。内核线性地址的分配以页为单位，一次一页。由多个页组成的页块可能会分配到不连续的内核线性地址。7070为了管理临时线性地址的分配，Linux定义了数组pkmap_count来记录kmap区间中各页的使用情况，如下：int pkmap_countLAST_PKMAP;/LAST_PKMAP=1024数组pkmap_count的某元素为0表示与之对应的内核线性地址当前是空闲的，可以将其分配给新的内存页。为内存页分配内核线性地址之后，通过页表pkma

37、p_page_table可以方便地将线性地址转换成物理地址，但却难以将物理地址转换成线性地址。为了方便查找物理页的内核线性地址，Linux又定义了结构page_address_map来记录物理页与内核线性地址的对应关系，并定义了Hash表page_address_htable，如图6.9所示。71 71struct page_address_map struct page*page;/内存页的管理结构 void*virtual;/内核线性地址 struct list_head list;struct page_address_map page_address_mapsLAST_PKMAP;st

38、atic struct page_address_slot 7272 struct list_head lh;/page_address_map结构队列 spinlock_t lock;/队列保护锁 _cacheline_aligned_in_smp page_address_htable1PA_HASH_ORDER;7373图6.9 高端内存页的内核线性地址7474当需要为某高端内存页分配内核线性地址时，Linux首先从数组pkmap_count中找一个空闲的页表项，得到一个空闲的内核线性地址，而后修改页表pkmap_page_table，将其映射到指定的内存页，同时填写一个page_add

39、ress_map结构，并将该结构插入到Hash表page_address_htable中。此后，用页的物理地址查Hash表page_address_htable即可得到它的内核线性地址。7575在图6.9中，为内存页j分配的内核线性地址是：PKMAP_BASE+i*PAGE_SIZE。当内核不再使用高端页时，应该释放它占用的线性地址，包括清除它的页表项、删除它在Hash表page_address_htable中的page_address_map结构等。如果在分配过程中发现已没有空闲的页表项，则请求者必须等待。为了满足无法等待的请求者的需要，Linux在“Fixed Virtual Addres

40、s”区间为每个处理器预留了8页的内核线性地址，用于应急。7676Linux提供了一组函数，用于管理高端内存页的线性地址，其中kmap()为高端内存页分配内核线性地址，kunmap()释放高端内存页的内核线性地址，kmap_atomic()将一个高端内存页映射到“Fixed Virtual Address”区间的一个固定位置，kunmap_atomic()清除高端内存页到“Fixed Virtual Address”的映射。77776.2.5 物理页块释放物理页块释放如果正在使用的物理页块又变成空闲的，那么应该将其还给伙伴内存管理器，这一过程称为物理页块的释放。释放是分配的逆过程。一般情况下，被

41、释放的页块应该插入到free_area数组的某个空闲页块队列中，队列位置由页块的大小和迁移类型决定。与分配过程相反，在释放过程中应该尽可能地将小页块合并成大页块。如果被释放页块的伙伴也是空闲的，就应该将它们合并，而后插入到free_area的更高阶队列中。合并的过程可能是递归的，一个小页块的释放可能会引起一连串的合并。7878页块释放过程中需要解决的问题主要有两个，一是确定伙伴的编号，二是确定伙伴是否在指定的队列中。根据页块的大小和编号，可以比较容易地算出其伙伴的编号。确定伙伴是否在指定队列的方法要稍微麻烦一点。在早期的版本中，Linux为free_area的每个队列准备了一个位图，两个伙伴合

42、用其中的一位，0表示伙伴不在队列中，1表示伙伴在队列中。随着内存的增大、队列的增多，位图的开销变得难以承受，因而在新版本中，Linux取消了队列位图，改用page结构来判断伙伴的位置。7979为此Linux做了如下约定：当将空闲页块插入free_area时，要在其起始页的flags上设置PG_buddy标志，并在private中记录页块的大小(即order)。除起始页之外，空闲页块的其余页上均不能设置PG_buddy标志，其private也应被清0。确定伙伴是否在指定队列的方法如下：(1)根据页块的编号B1和大小2order，算出其伙伴的编号B2=B1 (1 order)。(2)如果B2在空洞

43、中，那么B1的伙伴不在指定队列中。(3)如果B2和B1不在一个管理区中，那么B1的伙伴不在指定队列中。8080(4)如果B2的flags上有PG_buddy标志且其private等于order，则B1的伙伴在指定队列中。假如要释放页块属于zone管理区，其大小是2order页，迁移类型是migratetype，那么页块应被插入到zone的free_areaorder.free_listmigratetype队列中。如果页块的伙伴不在该队列中，则应先设置起始页上的标志，而后再将其直接插入队列。如果页块的伙伴在该队列中，则应将它的伙伴从队列中摘下，清除伙伴起始页上的标志，将它们合并成大小为2ord

44、er+1页的页块，而后再将其插入到free_areaorder+1.free_listmigratetype中。81 81当然，此次插入仍需要判断其伙伴是否在队列中，并在可能的情况下进行页块合并。如果页块的大小达到了最大(如210页)，则不需要再合并。上述释放算法的好处是总能得到大的空闲页块，大页块可以满足未来更多的需要，问题是合并过于积极。过于积极的合并会导致未来不必要的拆分，带来额外的系统开销。新版本的Linux增加了热页队列，试图将合并工作向后推迟。如果要释放的是单个物理页，直接将其加入到当前处理器的热页队列的队头即可，不需要将其与伙伴合并。8282当然，合并推迟不是无限制的，如果热页队

45、列的长度超过了预设的基准(high)线，则要一次性地将其中batch个空闲页归还给free_area。归还的物理页全部位于热页队列的队尾，基本已属于冷页。缓存而后批量处理是Linux经常采用的Lazy策略，基于Lazy策略的分配与释放算法可有效地减少拆分与合并的次数，提高伙伴内存管理的性能。Linux的伙伴内存管理器提供了多个物理内存释放函数，其中free_pages()类函数的参数是起始页的page结构，而_free_pages()类函数的参数是起始页的内核线性地址。8383伙伴内存管理器十分有效，但它只能分配物理上连续的内存页块。虽然伙伴内存管理器会尽力合并小页块，但随着系统的运行，内存页

46、块仍然有碎化的趋势。当碎化严重时，伙伴内存管理器虽能回收到足够的空闲内存，却无法将它们合并成大的页块，无法满足请求者的需求。为解决这一问题，Linux在伙伴内存管理器的基础上又提供了逻辑内存管理器，试图向它的用户提供仅在逻辑上连续的大块内存。6.3 逻辑内存管理逻辑内存管理8484事实上，在启动分页机制之后，不管是操作系统内核还是应用程序，在访问内存时使用的都是逻辑或线性地址，因而只要逻辑上连续就已足够，并不需要真正的物理连续。逻辑内存管理器就建立在这一事实之上，它利用内核中一块连续的线性地址空间为其用户模拟出逻辑上连续的大内存块。由多个逻辑上连续的内存页构成的页块称为逻辑页块，逻辑页块的大小

47、不用遵循2的指数次方的约定，可以由任意多个页构成。8585为实现逻辑内存管理，Linux已在初始化时专门预留了128 MB的内核线性地址空间，其开始地址为VMALLOC_START，终止地址为VMALLOC_END(见图3.4)。利用这块内核线性地址空间可实现逻辑页块的分配，其步骤大致如下：(1)在VMALLOC_START和VMALLOC_END之间找一块足够大的线性地址区间。(2)向伙伴内存管理器申请一组物理页，每次1页，不要求物理上连续。8686(3)修改第0号进程的页目录、页表，建立内核线性地址到物理地址的映射。步骤的后两步比较容易实现，困难的是线性地址区间的分配。虽然可以用伙伴算法管

48、理这块线性地址空间，但逻辑内存管理器选用了更为简单的动态分区法，即根据请求者的需要动态地从预留的内核线性地址空间中划出小区间。为了实现区间的动态划分，避免交叉重叠，逻辑内存管理器需要知道预留空间的使用情况，如哪些部分是空闲的、哪些部分已分配出去等。Linux用结构vm_struct描述已分配的线性地址区间，如下：8787struct vm_struct struct vm_struct*next;void*addr;/区间开始线性地址 unsigned long size;/区间大小 unsigned long flags;/标志 struct page*pages;/组成逻辑内存页块的物理内

49、存页 unsigned intnr_pages;/区间的页数 unsigned long phys_addr;/映射的I/O物理地址;8888一个vm_struct结构描述预留线性地址空间中的一段连续的区间，它由若干个逻辑页组成，其中的每个逻辑页又被映射到一个物理页，形成了一个逻辑上连续的内存页块，即逻辑页块，如图6.10所示。系统中所有的vm_struct结构组成一个单向的有序队列，vmlist是队头，如图6.11所示。队列中的vm_struct结构按addr排列，从小到大，逻辑页块间至少有1页的隔离带。8989图6.10 结构vm_struct描述的逻辑内存块9090图6.11 vmlis

50、t队列与逻辑页块91 91两个相邻逻辑页块之间的空隙是隔离带。在早期的实现中，逻辑内存管理器采用最先适应算法分配逻辑页块，即顺序搜索vmlist队列(或者说顺序搜索空闲页块队列)，从第一个满足要求的空闲页块中划出需要的页数，组成新的逻辑页块并将其分配给请求者。在新版本中，为了加快查找和分配的速度，Linux另外定义了一个vmap_area结构。与vm_struct一样，vmap_area描述的也是已分配的线性地址区间，但与vm_struct不同，9292系统中的vmap_area结构被组织成一棵红黑树。结构vm_struct与vmap_area关联在一起，通过搜索红黑树可以快速找到vm_str