第4章内存管理

《第4章内存管理》由会员分享，可在线阅读，更多相关《第4章内存管理（51页珍藏版）》请在装配图网上搜索。

1、第4章内存管理 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第4章 内存管理 n本章介绍Linux内存管理子系统的整体概念，讨论存储层次结构、x86存储管理硬件和Linux虚存系统及相关系统工具。4.1存储层次结构和x86存储管理硬件 n n4.1.1内存管理基本框架n nLinux内核的设计要考虑到在各种不同的微处理器上的实现，所以不能仅仅针对i386结构来设计它的映射机制，而要以虚拟的微处理器和内存管理单元MMU(MemoryManagementUnit)为

2、基础，设计出一种通用的模式，再将其分别落实到具体的微处理器上。Linux在内存管理的软件实现方面，提供了不同的接口，可以用于各种各样不同地址线宽度的CPU。n nIntel Intel Intel Intel 的的的的80386803868038680386提供了两层影射的页式内存管理的件提供了两层影射的页式内存管理的件提供了两层影射的页式内存管理的件提供了两层影射的页式内存管理的件支持，一层是页面目录称为支持，一层是页面目录称为支持，一层是页面目录称为支持，一层是页面目录称为PGDPGDPGDPGD（Page DirectoryPage DirectoryPage DirectoryPage

3、 Directory），），），），另一层是页表称为另一层是页表称为另一层是页表称为另一层是页表称为PTPTPTPT（Page TablesPage TablesPage TablesPage Tables），），），），PTPTPTPT的表项称的表项称的表项称的表项称为为为为PTEPTEPTEPTE（Page Table ElementsPage Table ElementsPage Table ElementsPage Table Elements）。）。）。）。通过它们实现从通过它们实现从通过它们实现从通过它们实现从线性地址到物理地址的转换。这种两层影射方式对线性地址到物理地址的转换。这

4、种两层影射方式对线性地址到物理地址的转换。这种两层影射方式对线性地址到物理地址的转换。这种两层影射方式对于于于于32323232位地址线的位地址线的位地址线的位地址线的386386386386是很合适的。但是很合适的。但是很合适的。但是很合适的。但LinuxLinuxLinuxLinux要设计成要设计成要设计成要设计成可在不同的可在不同的可在不同的可在不同的CPUCPUCPUCPU下运行，考虑到大于下运行，考虑到大于下运行，考虑到大于下运行，考虑到大于32323232位地址线宽度位地址线宽度位地址线宽度位地址线宽度的的的的CPUCPUCPUCPU（例如例如例如例如64646464位的位的位的位

5、的CPUCPUCPUCPU），），），），LinuxLinuxLinuxLinux内核的映射机制被内核的映射机制被内核的映射机制被内核的映射机制被设计成设计成设计成设计成3 3 3 3层，在页面目录和页表之间增设了一层层，在页面目录和页表之间增设了一层层，在页面目录和页表之间增设了一层层，在页面目录和页表之间增设了一层“中中中中间目录间目录间目录间目录”PMDPMDPMDPMD（Page Mid-level DirectoryPage Mid-level DirectoryPage Mid-level DirectoryPage Mid-level Directory）在逻辑在逻辑在逻辑在逻辑

6、上，相应地也把线性地址从高到低分为上，相应地也把线性地址从高到低分为上，相应地也把线性地址从高到低分为上，相应地也把线性地址从高到低分为4 4 4 4个位段，各个位段，各个位段，各个位段，各占若干位，分别用作目录占若干位，分别用作目录占若干位，分别用作目录占若干位，分别用作目录PGDPGDPGDPGD的下标、中间目录的下标、中间目录的下标、中间目录的下标、中间目录PMDPMDPMDPMD的下标、页表中的下标和物理页面内的位移。如图的下标、页表中的下标和物理页面内的位移。如图的下标、页表中的下标和物理页面内的位移。如图的下标、页表中的下标和物理页面内的位移。如图4.14.14.14.1所示。所示

7、。所示。所示。PGDPGDPGDPGD、PMDPMDPMDPMD、PTPTPTPT都是数组。都是数组。都是数组。都是数组。Page FramePage FramePage FramePage Frame是最是最是最是最后得到的物理页。后得到的物理页。后得到的物理页。后得到的物理页。三层影射过程如下：（1）从控制寄存器CR3中找到页目录的基址。（2）以线性地址的最高位段作为下标在PGD中找到确定中间目录的表项的指针。（3）以线性地址的次位段作为下标在PMD中找到确定页面表的表项的指针。（4）在线性地址的接下来位段为下标在PTE中找到页的指针。（5）最后线性地址的位段中为在此页中偏移量。这样，最终

8、完成了线性地址到物理地址的转换。n n假如当要执行某个函数的第一个句子时，假如当要执行某个函数的第一个句子时，CPUCPU会通过会通过3232位地址线寻址（位地址线寻址（2 2的的3232次方，可以寻址次方，可以寻址4 4GG的线性地址空间）。通过的线性地址空间）。通过MMUMMU执行以上的影射过程，执行以上的影射过程，就会在计算机的内存中找到这个句子的物理地址，如果要找的那一句不在物就会在计算机的内存中找到这个句子的物理地址，如果要找的那一句不在物理页中，就会发生一次异常中断，使硬盘和内存发生交互。理页中，就会发生一次异常中断，使硬盘和内存发生交互。n n在在LinuxLinux原码的原码的

9、 include/asm-i386/gptable.hinclude/asm-i386/gptable.h定义了能够包容不同定义了能够包容不同CPUCPU的的接口：接口：n n#ifCONFIG_X86_PAE/ifCONFIG_X86_PAE/假如在假如在PAEPAE模式下，用三层影射结构模式下，用三层影射结构n n#includeincluden n#else#elsen n#include/#include/否则用两层否则用两层n n#endifendifn n在在pgtable-2level.hpgtable-2level.h中定义了中定义了PGDPGD，PMDPMD的结构。的结构。n

10、 n#definePGDIR_SHIFT22/definePGDIR_SHIFT22/页目录是线性地址的页目录是线性地址的31223122位位n n#definePTRS_PER_PGD1024/definePTRS_PER_PGD1024/总共有总共有10241024个页目录个页目录n n#definePMDIR_SHIFT22/definePMDIR_SHIFT22/中间目录不用了中间目录不用了n n#definePTRS_PER_PMD1definePTRS_PER_PMD1n n#definePTRS_PER_PTE1024/#definePTRS_PER_PTE1024/每个页表有每

11、个页表有10231023页页n n在在3232位线性地址中的位线性地址中的4 4GG虚拟空间中虚拟空间中，其中有其中有1 1GG做为内核空间做为内核空间，从从0 0XC0000000XC0000000到到0 0XFFFFFFFFXFFFFFFFF。每个进程都有自己的每个进程都有自己的3 3GG用户空间，用户空间，它们共享它们共享1 1GG的内核空间。当一个进程从用户空间进入内核空间时，的内核空间。当一个进程从用户空间进入内核空间时，它就不在有自己的进程空间了。它就不在有自己的进程空间了。n n在物理空间中，内核总是从在物理空间中，内核总是从0 0地址开始的，而在虚拟空间中是丛地址开始的，而在虚

12、拟空间中是丛0 0XC0000000XC0000000开始的。内核中的影射是很简单的线性影射，所以开始的。内核中的影射是很简单的线性影射，所以0 0XC0000000XC0000000就是两者的偏移量。就是两者的偏移量。n n在在page.hpage.h中：中：n n#define_PAGE_OFFSET(0 xc0000000)define_PAGE_OFFSET(0 xc0000000)n n#definePAGE_OFFSET(unsignedlong)_PAGE_OFFSET)#definePAGE_OFFSET(unsignedlong)_PAGE_OFFSET)n n#defne_

13、pa(x)(unsignedlonsg)(x)PAGE_OFFSET)#defne_pa(x)(unsignedlonsg)(x)PAGE_OFFSET)n n/内核虚拟地址转换到物理地址内核虚拟地址转换到物理地址n n#define_va(x)(void*)(unsignedlong)(x)+define_va(x)(void*)(unsignedlong)(x)+PAGE_OFFSET)PAGE_OFFSET)n n/内核从物理地址到虚拟地址的转换内核从物理地址到虚拟地址的转换n n 对对i386i386微处理器来说，微处理器来说，CPUCPU实际上不是按实际上不是按3 3层而是按两层的模

14、型来进层而是按两层的模型来进行地址映射，这就需要将虚拟的行地址映射，这就需要将虚拟的3 3层映射落实到具体的两层的映射，层映射落实到具体的两层的映射，跳过中间的跳过中间的PMDPMD层次。层次。n n4.1.2地址映射的全过程地址映射的全过程n n80386有实方式和保护方式两种工作方式。尽管实方式下80386的功能较Intel先前的微处理器有很大的提高，但只有在保护方式下，80386才能真正发挥作用。在保护方式下，全部32根地址线有效，可寻址达4G字节的物理空间。扩充的存储器分段管理机制和可选的存储器分页管理机制，不仅为存储器共享和保护提供了硬件支持，而且为实现虚拟存储器提供了硬件支持；支持

15、多任务，能快速的进行任务切换和任务保护环境；4个特权级和完善的特权检查机制，既能实现资源共享又能保证代码及数据的安全和保密及任务的隔离；支持虚拟8086方式，便于执行8086代码。(1)80386 保护方式的寻址在保护方式下，当寻址扩展内存中的数据和程序时，仍然使用偏移地址访问位于存储器内的信息，但保护方式下的段地址不再像实方式那样有段寄存器提供，而是在原来存放段地址的段寄存器里含有一个选择子，用于选择描述符表内的一个描述符。描述符描述存储器的位置、长度和访问权限。保护方式下有两个描述符表：全局描述符表和局部描述符表。全局描述符表包含适用于所有程序的段定义，而局部描述符表通常用于唯一的应用程序

16、。每个描述符表包含8129个描述符，所以任何时刻应用程序最多可用16384个描述符。每个描述符长8字节，全局和局部描述符表每个最长为64kb。分页机制式存储管理机制的第二部分。分页机制在段机制之后进行操作，以完成虚拟地址到物理地址的转换。段机制把虚拟地址转换为线性地址，分页机制进一步把线性地址转换为物理地址。分页机制由微处理器中控制寄存器的内容控制。分页机制由CRO中的PG位启用。若PG=1，启用分页机制。PG=0，不用分页机制，直接把段机制生成的线性地址当作物理地址。软件生成的线性地址分为三部分，分别用于页目录项、页表项和页偏移地址寻址。(2)Linux所采用的方法i386微处理器一律对程序

17、中的地址先进行段式映射，然后才能进行页式映射。而Linux为了减小footprint，提高cache命中率，尽量避免使用段功能以提高可移植性。如通过使用基址为0的段，使逻辑地址等于线性地址。因此Linux所采用的方法实际上使i386的段式映射的过程不起作用。下面通过一个简单的程序来看看Linux下的地址映射的全过程：#includegreeting()printf(“Helloworld!”);main()greeing();该程序在主函数中调用greeting来显示“Helloworld!”，经过编译和反汇编的结果如下。08048568:8048568:55push1%ebp8048856b

18、:89e5mov1%esp,%ebp804856b:6804940408push1$0 x80484048048570:e8fffeffffcall80484748048575:83c404add1$0 x4,%esp8048578:c9leave8048579:c3ret804857a:89f6mov1%esi,%esi0804857c:804857c:55push1%ebp804857d:89e5mov1%esp,%ebp804857f:e8e4ffffffcall80485688048584:c9leave8048585:c3ret8048586:90nop8048587:90nop从上

19、面可以看出，greeting()的地址为0 x8048568。在elf格式的可执行代码中，总是在0 x8000000开始安排程序的“代码段”，对每个程序都是这样。程序在main中执行到了“call8048568”这条指令，要转移到虚拟地址8048568去。首先是段式映射阶段。地址8048568是一个程序的入口，更重要的是在执行的过程中由CPU的EIP所指向的，所以在代码段中。I386cpu使用CS的当前值作为段式映射的选择子。内核在建立一个进程时都要将它的段寄存器设置好，把DS、ES、SS都设置成_USER_DS,而把CS设置成_USER_CS,这也就是说，在Linux内核中堆栈段和代码段是不

20、分的。IndexTIDPL#define_KERNEL_CS0 x100000000000010|0|00#define_KERNEL_DS0 x180000000000011|0|00#define_USER_CS0 x230000000000100|0|11#define_USER_DS0 x2B0000000000101|0|11_KERNEL_CS:index=2,TI=0,DPL=0_KERNEL_DS:index=3,TI=0,DPL=0_USERL_CS:index=4,TI=0,DPL=3_USERL_DS:index=5,TI=0,DPL=3TI全都是0，都使用全局描述表。内

21、核的DPL都为最高级别0；用户的DPL都是最低级别3。_USER_CS在GDT表中是第4项，初始化GDT内容的代码如下：ENTRY(gdt-table).quad0 x0000000000000000/NULLdescriptor.quad0 x0000000000000000/notused.quad0 x00cf9a00000ffff/0 x10kernel4GBcodeat0 x00000000.quad0 x00cf9200000ffff/0 x18kernel4GBdataat0 x00000000.quad0 x00cffa00000ffff/0 x23user4GBcodeat0

22、 x00000000.quad0 x00cff200000ffff/0 x2buser4GBdataat0 x00000000GDT表中第1、2项不用，第3至第5项共4项对应于前面的4个段寄存器的数值。将这4个段描述项的内容展开：K_CS:0000000011001111100110100000000000000000000000001111111111111111K_DS:0000000011001111100100100000000000000000000000001111111111111111U_CS:000000001100111111111101000000000000000000

23、00000001111111111111111U_DS:0000000011001111111100100000000000000000000000001111111111111111这4个段描述项的下列内容都是相同的。BO-B15/B16-B31都是0基地址全为0LO-L15、L16-L19都是1段的界限全是0 xfffffG位都是1段长均为4KBD位都是132位指令P位都是1四个段都在内存中不同之处在于权限级别不同，内核的为0级，用户的为3级。由此可知，每个段都是从地址0开始的整个4GB地虚存空间，虚地址到线性地址的映射保持原值不变。再回到greeting的程序中来，通过段式映射把地址80

24、48568映射到自身，得到了线性地址。每个进程都有自身的页目录PGD，每当调度一个进程进入运行时，内核都要为即将运行的进程设置好控制寄存器CR3，而MMU硬件总是从CR3中取得当前进程的页目录指针。当程序要转到地址0 x8048568去的时候，进程正在运行中，CR3已经设置好了，指向本进程的页目录了。8048568：00001000000001001000010101101000按照线性地址的格式，最高10位0000100000，十进制的32，就以下标32去页目录表中找其页目录项。这个页目录项的高20位后面添上12个0就得到该页面表的指针。找到页表后，再看线性地址的中间10位001001000

25、，十进制的72。就以72为下标在找到的页表中找到相应的表项。页面表项重的高20位后添上12个0就得到了物理内存页面的基地址。线性地址的底12位和得到的物理页面的基地址相加就得到要访问的物理地址。4.1.3 地址映射的效率分析地址映射的效率分析在页式映射的过程中，CPU要访问内存3次，第1次是页面目录，第2次是页面表，第3次才是真正要访问的目标。这样，把原来不用分页机制一次访问内存就能得到的目标，变为3次访问内存才能得到，执行分页机制在效率上的牺牲太大。为了减少这种开销，最近被执行过的地址转换结果会被保留在MMU的转换后备缓存（TranslationLook-asideBuffer,TLB）中。

26、虽然在第一次用到具体的页面目录和页面表时要到内存中读取，但一旦装入了TLB中，就不需要再到内存中去读取了，而且这些都是由硬件完成的，因此速度很快。TLB对应权限大于0级的程序来说是不可见的，只有处于系统0层的程序才能对其进行操作。当控制寄存器CR3的内容变化时，TLB中的所有内容会被自动变为无效。Linux中的_flush_TLB宏就是利用这点工作的。_flush_TLB只是两条汇编指令，把CR3的值保存在临时变量tmpreg里，然后立刻把tmpreg的值拷贝回CR3，这样就将TLB中的全部内容置为无效。除了无效所有的TLB中的内容，还能有选择的无效TLB中某条记录，这就要用到INVLPG指令

27、。2x86的地址逻辑地址：出现在机器指令中，用来制定操作数的地址，由段和偏移表示。线性地址：逻辑地址经过分段单元处理后得到线性地址，这是一个32位的无符号整数，可用于定位4G个存储单元。物理地址：线性地址经过页表查找后得出物理地址，这个地址将被送到地址总线上指示所要访问的物理内存单元。3x86的段保护模式下的段使用“选择子+描述符”的方式。不仅仅是一个基地址的原因是为了提供更多的信息：保护、长度限制、类型等。描述符存放在一张表中(GDT或LDT)，选择子可以认为是表的索引。段寄存器中存放的是选择子，在段寄存器装入的同时，描述符中的数据被装入一个不可见的寄存器以便CPU快速访问。保护模式下使用的

28、专用寄存器有：GDTR(包含全局描述附表的首地址)、LDTR（当前进程的段描述附表首地址）和TSR（指向当前进程的任务状态段）。4Linux使用的段_KERNEL_CS：内核代码段。范围0-4G。可读、执行。DPL=0。_KERNEL_DS：内核代码段。范围0-4G。可读、写。DPL=0。_USER_CS：内核代码段。范围0-4G。可读、执行。DPL=3。_USER_DS：内核代码段。范围0-4G。可读、写。DPL=3。TSS(任务状态段)：存储进程的硬件上下文，进程切换时使用。（因为x86硬件对TSS有一定支持，所有有这个特殊的段和相应的专用寄存器。）default_ldt：理论上每个进程都

29、可以同时使用很多段，这些段可以存储在自己的LDT段中，但实际Linux极少利用x86的这些功能，多数情况下所有进程共享这个段，它只包含一个空描述符。还有一些特殊的段用在电源管理等代码中。在2.2以前，每个进程的LDT和TSS段都存在GDT中，而GDT最多只能有8192项，因此整个系统的进程总数被限制在4090左右。2.4里不再把它们存在GDT中，从而取消了这个限制。_USER_CS和_USER_DS段都是被所有在用户态下的进程共享的。注意不要把这个共享和进程空间的共享混淆：虽然大家使用同一个段，但通过分页机制使用不同的页表，保证了进程空间仍然是独立的。5x86的分页机制x86硬件支持两级页表，

30、奔腾Pro以上的型号还支持硬件支持模式（PhysicaladdressExtensionMode）和3级页表。所谓硬件支持模式包括一些特殊寄存器(cr0-cr4)、以及CPU能够识别页表项中的一些标志位并根据访问情况做出反应等等。例如：在读写Present位为0的页或者写Read/Write位为0的页将引起CPU发出pagefault异常，访问完页面后自动设置accessed位等。Linux采用的是一个体系结构无关的三级页表模型，使用一系列的宏来掩盖各种平台的细节。例如，通过把PMD看作只有一项的表并存储在PGD表项中（通常PGD表项中存放的应该是PMD表的首地址），页表的中间目录(PMD)被

31、巧妙地折叠到页表的全局目录(PGD)，从而适应了二级页表硬件。6.TLB转换后备缓存TLB（TranslationLook-asideBuffer），用来加速页表查找。如果操作系统更改了页表内容，它必须相应的刷新TLB以使CPU不会误用过时的表项。7.CacheCache 基本上是对程序员透明的，但是不同的使用方法可以导致大不相同的性能。Linux有许多关键的地方对代码做了精心优化，其中很多就是为了减少对cache不必要的污染。例如把只有出错情况下用到的代码放到.fixupsection，把频繁同时使用的数据集中到一个cache行（如structtask_struct），减少一些函数的foot

32、print，在slab分配器里头的slabcoloring等。另外，当新map/remap一页到某个地址、页面换出、页保护改变、进程切换等，也即当cache对应的那个地址的内容或含义有所变化时，cache要无效。当然在很多情况下不需要无效整个cache，只需要无效某个地址或地址范围即可。实际上，Intel在这方面做得非常好，cache的一致性完全由硬件维护。8Linux的相关实现这一部分的代码和体系结构紧密相关，因此大多位于arch子目录下，而且大量以宏定义和inline函数形式存在于头文件中。在i386平台中，主要的文件包括：（1）page.h页大小、页掩码定义：PAGE_SIZE、PAGE

33、_SHIFT和PAGE_MASK。对页的操作，如清除页内容clear_page、拷贝页copy_page、页对齐page_align。还有内核虚地址的起始点：著名的PAGE_OFFSET:)和相关的内核中虚实地址转换的宏_pa和_va.。virt_to_page从一个内核虚地址得到该页的描述结构structpage*。所有物理内存都由一个memmap数组来描述。这个宏就是计算给定地址的物理页在这个数组中的位置。另外这个文件也定义了一个简单的宏检查一个页是不是合法：VALID_PAGE：如果page离memmap数组的开始太远以至于超过了最大物理页面应有的距离则是不合法的。页表项的定义pgd_t

34、,pmd_t,pte_t和存取它们值的宏xxx_val也放在这里。（2）pgtable.h、pgtable-2level.h和pgtable-3level.h这些文件就是处理页表的，它们提供了一系列的宏来操作页表。pgtable-2level.h和pgtable-2level.h则分别对应x86二级、三级页表的需求。首先当然是表示每级页表有多少项的定义不同了。而且在PAE模式下，地址超过32位，页表项pte_t用64位来表示(pmd_t,pgd_t不需要变)，一些对整个页表项的操作也就不同。共有如下几类：pte/pmd/pgd_ERROR：出措时要打印项的取值，64位和32位当然不一样。set

35、_pte/pmd/pgd：设置表项值pte_same：比较pte_page从pte得出所在的memmap位置pte_none：是否为空。_mk_pte：构造ptepgtable.h中的宏很多，但也比较直观，通常从名字就可以看出宏的意义。如pte_xxx宏的参数是pte_t，而ptep_xxx的参数是pte_t*。pgtable.h里除了页表操作的宏外，还有cache和TLB刷新操作，这也比较合理，因为他们常常是在页表操作时使用。这里的TLB操作是以_开始的，也就是说，内部使用的，真正对外接口在pgalloc.h中（分开的原因，可能是因为在SMP版本中TLB的刷新函数和单机版本区别较大，有些不再

36、是内嵌函数和宏了）。（3）pgalloc.h包括页表项的分配和释放宏/函数,值得注意的是表项高速缓存的使用：pgd/pmd/pte_quicklist内核中有许多地方使用类似的技巧来减少对内存分配函数的调用，加速频繁使用的分配。如buffercache中buffer_head和buffer，vm区域中最近使用的区域，还有上面提到的TLB刷新的接口等。（4）segment.h定义_KERNEL_CSDS_USER_CSDS4.1.4 连续物理区域管理连续物理区域管理1.Linux的Slab分配器 单单分配页面的分配器是不能满足要求的。内核中大量使用各种数据结构，大小从几个字节到几十上百K不等，都

37、取整到2的幂次个页面那是完全不现实的。2.0的内核的解决方法是提供大小为2、4、8、16、.、131056字节的内存区域。需要新的内存区域时，内核从伙伴系统申请页面，把它们划分成一个个区域，取一个来满足需求；如果某个页面中的内存区域都释放了，页面就交回到伙伴系统。这样做的效率不高。有许多地方可以改进：不同的数据类型用不同的方法分配内存可能提高效率。比如需要初始化的数据结构，释放后可以暂存着，再分配时就不必初始化了。内核的函数常常重复地使用同一类型的内存区，缓存最近释放的对象可以加速分配和释放。对内存的请求可以按照请求频率来分类，频繁使用的类型使用专门的缓存，很少使用的可以使用类似2.0中的取整

38、到2的幂次的通用缓存。使用2的幂次大小的内存区域时高速缓存冲突的概率较大，有可能通过仔细安排内存区域的起始地址来减少高速缓存冲突。缓存一定数量的对象可以减少对buddy系统的调用，从而节省时间并减少由此引起的高速缓存污染。Linux2.2内核实现的slab分配器体现了这些改进思想。主要数据结构有：kmem_cache_create/kmem_cache_destorykmem_cache_grow/kmem_cache_reap /增长/缩减某类缓存的大小kmem_cache_alloc/kmem_cache_free /从某类缓存分配/释放一个对象kmalloc/kfree /通用缓存的分配

39、、释放函数。相关代码见slab.c。vmalloc/vfree主要进行物理地址不连续，虚地址连续的内存管理。它使用kernel页表。位于文件vmalloc.c，相对来说比较简单。2.基于区的伙伴系统的设计和物理页面的管理Linux2.4中的内存管理有很大的变化。在物理页面管理上实现了基于区的伙伴系统（zonebasedbuddysystem）。区(zone)的是根据内存的不同使用类型划分的。对不同区的内存使用单独的伙伴系统(buddysystem)管理，而且独立地监控空闲页等。内存分配的两大问题是：分配效率及碎片问题。一个好的分配器应该能够快速的满足各种大小的分配要求，同时不能产生大量的碎片浪

40、费空间。伙伴系统是一个常用的比较好的算法。引入区的概念是为了区分内存的不同使用类型（方法），以便更有效地利用。Linux2.4有三个区：DMA、Normal和HighMem。前两个在Linux2.2中实际上也是由独立的buddysystem管理的，但Linux2.2中还没有明确的zone的概念。DMA区在x86体系结构中通常是小于16兆的物理内存区，因为DMA控制器只能使用这一段的内存。而HighMem是物理地址超过某个值(通常是约900M)的高端内存。其他的是Normal区内存。在Linux实现中，高地址的内存不能直接被内核使用。内核使用一种特殊的办法，即使用CONFIG_HIGHMEM选项

41、，来使用高地址的内存。HighMem只用于页面高速缓冲和用户进程。这样分开的结果，是可以更有针对性地使用内存，不至于出现把DMA可用的内存大量给无关的用户进程使用，导致驱动程序没法得到足够的DMA内存等情况。此外，每个区都独立地监控本区内存的使用情况。在分配时，系统综合考虑用户的要求和系统现状，判断从哪个区分配比较合适。2.4里分配页面时可能会和高层的VM代码交互(分配时根据空闲页面的情况，内核可能从伙伴系统里分配页面，也可能直接把已经分配的页收回（reclaim）等。实际上，在更高一层还有NUMA(NoneUniformedMemoryAccess)的支持。在一般的机器中，CPU对每个内存单

42、元（动态随机存取存储器DRAM）的存取速度是一样的。而NUMA是一种体系结构，对系统里的每个处理器来说，不同的内存区域可能有不同的存取时间(一般是由内存和处理器的距离决定)。NUMA中访问速度相同的一个内存区域称为一个节点（node），NUMA的主要任务就是要尽量减少node之间的通信，使得每个处理器要用到的数据尽可能放在对它来说最快的node中。2.4内核中node的相应数据结构是pg_data_t，每个node拥有自己的memmap数组，把自己的内存分成几个zone，每个zone再用独立的伙伴系统管理物理页面。整个分配器的主要接口是下面的函数（参看mm.h及page_alloc.c）：st

43、ruct page*alloc_pages(int gfp_mask,unsigned long order)：根据gftp_mask的要求，从适当的区分配2order个页面，返回第一个页的描述符。#define alloc_page(gfp_mask)alloc_pages(gfp_mask,0)unsigned long _get_free_pages(int gfp_mask,unsigned long order)：其工作与alloc_page.s相同，但返回首地址。#define _get_free_page(gfp_mask)_get_free_pages(gfp_mask,0)g

44、et_free_page：分配一个已清零的页面。_free_page(s)和free_page(s)释放页面（一个/多个）前者以页面描述符为参数，后者以页面地址为参数。4.2 Linux虚存系统虚拟内存的基本思想是，在计算机中运行的程序，其代码、数据和堆栈的总量可以超过实际内存的大小，操作系统只将当前使用的程序块保留在内存中，其余的程序块则保留在磁盘上。必要时，操作系统负责在磁盘和内存之间交换程序块。4.2.1 使用虚存的优点使用虚存的优点Linux 也采用虚拟内存管理机制，使用虚拟内存有如下优点：（1）大地址空间。对运行在系统中的进程而言，可用的内存总量可以超过系统的物理内存总量，甚至可以达

45、到好几倍。运行在i386平台上的Linux进程，其地址空间可达4GB。（2）进程保护。每个进程拥有自己的虚拟地址空间，这些虚拟地址对应的物理地址完全和其他进程的物理地址隔离，从而避免进程之间的互相影响。（3）内存映射。利用内存映射，可以将程序影像或数据文件映射到进程的虚拟地址空间中，对程序代码和数据的访问与访问内存单元一样。（4）公平的物理内存分配。虚拟内存机制可保证系统中运行的进程平等分享系统中的物理内存。（5）共享虚拟内存。利用虚拟内存可以方便隔离各进程的地址空间，但是，如果将不同进程的虚拟地址映射到同一物理地址，则可实现内存共享。这就是共享虚拟内存的本质，利用共享虚拟内存不仅可以节省物理

46、内存的使用（如果两个进程的部分或全部代码相同，只需在物理内存中保留一份相同的代码即可），而且可以实现所谓“共享内存”的进程间通讯机制（两个进程通过同一物理内存区域进行数据交换）。图4.2虚拟地址到物理地址的映射模型图4.2虚拟地址到物理地址的映射模型Linux 中的虚拟内存采用所谓的“分页”机制。分页机制将虚拟地址空间和物理地址空间划分为大小相同的块，这样的块称为“内存页”或简称为“页”。通过虚拟内存地址空间的页与物理地址空间中的页之间的映射，分页机制可实现虚拟内存地址到物理内存地址之间的转换。图4.2说明了两个进程的虚拟地址空间的部分页到物理地址空间的部分页之间的映射关系。i386 平台上的

47、Linux页大小为4K字节，而在AlphaAXP系统中使用8K字节的页。不管是虚拟内存页还是物理内存页，它们均被给定一个唯一的“页帧编号”（PageFrameNumber，PFN）。在上述映射模型中，虚拟内存地址由两部分组成，其中一部分就是页帧编号，而另一部分则是偏移量。CPU负责将虚拟页帧编号翻译为相应的物理页帧编号。物理页帧编号实际是物理地址的高位，也称为页基地址，页基地址加上偏移量就是物理内存地址（这和DOS64K段基地址及段偏移量类似）。为此，CPU利用“页表”实现虚拟页帧编号到物理页帧编号的转换。在图4.3中，操作系统可以为不同的进程准备进程的私有页表，每个页表项包含物理页帧编号、页

48、表项的有效标志以及相应的物理页访问控制属性，访问控制属性指定了页是只读页、只写页、可读可写页还是可执行代码页，这有利于进行内存保护（例如进程不能向代码页中写入数据）。图4.3给出了i386系统中的页表项格式。参照图4.2，CPU利用虚拟页帧编号作为访问进程页表的索引来检索页表项，如果当前页表项是有效的，处理器就可以从该页表项中获得物理页帧编号，进而获得物理内存中的页基地址，加上虚拟内存中的偏移量就是要访问的物理地址；如果当前页表项无效，则说明进程访问了一个不存在的虚拟内存区，在这种情况下，CPU将会向操作系统报告一个“页故障”，操作系统则负责对页故障进行处理。图4.3i386系统中的页表项格式

49、一般来说，页故障的原因可能是因为进程访问了非法的虚拟地址，也可能是因为进程要访问的物理地址当前不在物理内存中，这时，操作系统负责将所需的内存页装入物理内存。上面就是虚拟内存的抽象模型，但Linux中的虚拟内存机制要更复杂一些。从性能的角度考虑，如果内核本身也需要进行分页，并要为内核代码和数据页维护一个页表的话，则系统的性能会下降很多。为此，Linux的内核运行在所谓的“物理地址模式”，CPU不必在这种模式下进行地址转换，物理地址模式的实现和实际的CPU类型有关。4.3 Linux 的内存页表在i386系统中，虚拟地址空间的大小是4G，因此，全部的虚拟内存空间划分为1M页。如果用一个页表描述这种

50、映射关系，那么这一映射表就要有1M个表项，当每个表项占用4个字节时，全部表项占用的字节数就为4M，为了避免占用如此巨大的内存资源来存储页表，i386系列CPU采用两级页表，AlphaAXP系统使用三级页表。Linux为了避免硬件的不同细节影响内核的实施，假定有三级页表。如图4.3所示，一个虚拟地址可分为多个域，不同域的数据指出了对应级别页表中的偏移量。为了将一个虚拟地址转换为物理地址，处理器根据这三个级别域，每次将一个级别域中的值转换为对应页表的物理页偏移量，然后从中获得下一级页表的页帧编号。如此进行3次，就可以找出虚拟内存对应的实际物理内存。不同CPU的页级数目不同，Linux内核源代码则利

51、用C语言的宏将具体的硬件差别隐藏了起来。例如，对i386的Linux内核代码来说，三级的页表转换宏实际只有两个在起作用。4.3.1内存页的分配和释放内存页的分配和释放系统运行过程中，经常需要进行物理内存页的分配或释放。例如，执行程序时，操作系统需要为相应的进程分配页，而进程终止时，则要释放这些物理页。再如，页表本身也需要动态分配和释放。物理页的分配和释放机制及其相关数据结构是虚拟内存子系统的关键部分。图4.4多级页表示意图一般而言，有两种方法可用来管理内存的分配和释放。一种是采用位图，另外一种是采用链表。利用位图可记录内存单元的使用情况。例如，如果某个系统有1024字节内存，而内存的分配单元是

52、4字节，则可以利用1024/（4*8）=32个字节来记录使用情况。这32个字节的每个位分别代表相应分配单元的使用情况。如果位图中某个位为1，则对应的分配单元是空闲的。利用这一办法，内存的分配就可以通过对位值的检测来简化。如果一次要分配5个单元的空间，内存管理程序就需要找出5个连续位值均为1的位图位置，但这种操作比较慢，因为连续的位有时要跨越字节边界。利用链表则可以分别记录已分配的内存单元和空闲的内存单元。通常这些内存单元设计为双向链表结构，从而可加速空闲内存的搜索或链表的处理。这种方法相对位图方法要好一些，也更加有效。Linux 的物理页分配采用链表和位图结合的方法，如图4.4所示。Linux

53、内核定义了一个称为free_area的数组，该数组的每一项描述某一种页块的信息。第一个元素描述单个页的信息，第二个元素则描述以2个页为一个块的页块信息，第三个元素描述以4个页为一个块的页块信息，依此类推，所描述的页块大小描述以4个页为一个块的页块信息，依此类推，所描述的页块大小以2的倍数增加。free_area数组的每项包含两个元素：list和map。list是一个双向链表的头指针，该双向链表的每个节点包含空闲页块的起始物理页帧编号；而map则是记录这种页块组分配情况的位图，例如，位图的第N位为1，则表明第N个页块是空闲的。从图中也可以看到，用来记录页块组分配情况的位图大小各不相同，显然页块越

54、小，位图越大。图4.5中，free_area数组的元素0包含了一个空闲页（页帧编号为0）；而元素2则包含了两个以4页为大小的空闲页块，第一个页块的起始页帧编号为4，而另一个页块的起始页帧编号为56。图4.5Linux物理页块的分配示意Linux 采用Buddy算法有效分配和释放物理页块。按照上述数据结构，Linux可以分配的内存大小只能是1个页块，2个页块或4个页块等等。在分配物理页块时，Linux首先在free_area数组中搜索大于或等于要求尺寸的最小页块信息，然后在对应的list双向链表中寻找空闲页块，如果没有空闲页块，Linux则继续搜索更大的页块信息，直到发现一个空闲的页块为止。如果

55、搜索到的页块大于满足要求的最小页块，则只需将该页块剩余的部分划分为小的页块并添加到相应的list链表中。页块的分配会导致内存的碎片化，而页块的释放则可以将页块重新组合成大的页块。如果和被释放的页块大小相等的相邻页块是空闲的，则可以将这两个页块组合成一个大的页块，这一过程一直继续到把所有可能的页块组合成尽可能大的页块为止。知道了上述原理，读者可以自己想象系统启动时，初始的free_area数组中的信息。4.3.2内存映射和需求分页内存映射和需求分页当某个程序影像开始运行时，可执行影像必须装入进程的虚拟地址空间。如果该程序用到了任何一个共享库，则共享库也必须装入进程的虚拟地址空间。实际上，Linu

56、x并不将影像装入物理内存，相反，可执行文件只是被链接到进程的虚拟地址空间中。随着程序的运行，被引用的程序部分会由操作系统装入物理内存。这种将影像链接到进程地址空间的方法称为“内存映射”。图4.6vm_area_struct数据结构示意图每个进程的虚拟内存由一个mm_struct结构代表。该结构中实际包含了当前执行影像的有关信息，并包含了一组指向vm_area_struct结构的指针。如图4.6所示，每个vm_area_struct描述了一个虚拟内存区域的起点和终点、进程对内存的访问权限以及一个对内存的操作例程集。操作例程集是Linux操作该内存区域时所使用的例程集合。例如，当进程试图访问的虚拟

57、内存当前不在物理内存当中时（通过页故障），Linux就可以利用操作集中的一个例程执行正确的操作，在这种情况下为nopage操作。当可执行影像映射到进程的虚拟地址空间时，将产生一组vm_area_struct结构来描述虚拟内存区域的起始点和终止点，每个vm_struct结构代表可执行影像的一部分，可能是可执行代码，也可能是初始化的变量或未初始化的数据。随着vm_area_struct结构的生成，这些结构所描述的虚拟内存区域上的标准操作函数也由Linux初始化。某个可执行影像映射到进程虚拟内存中并开始执行时，因为只有很少一部分装入了物理内存，因此很快就会访问尚未装入物理内存的虚拟内存区域。这时，处

58、理器将向Linux报告一个页故障及其对应的故障原因。这种页故障的出现原因有两种，一是程序出现错误，例如向随机物理内存中写入数据，这种情况下，虚拟内存是无效的，Linux将向程序发送SIGSEGV信号并终止程序的运行；另一种情况是，虚拟地址有效，但其所对应的页当前不在物理内存中，这时，操作系统必须从磁盘影像或交换文件中将内存装入物理内存。如前所述，Linux利用vm_area_struct数据结构描述进程的虚拟内存空间，为了查找出现页故障虚拟内存相应的vm_area_struct结构的位置，Linux内核同时维护一个由vm_area_struct结构形成的AVL（Adelson-Velskiia

59、ndLandis）树。利用AVL树，可快速寻找发生页故障的虚拟地址所在的内存页区域。Linux在页故障发生时，如果搜索不到这一内存区域，则说明该虚拟地址是无效的，否则该虚拟地址是有效的。也有可能因为进程在虚拟地址上进行的操作非法而产生页故障，例如在只读页中写入数据。这时操作系统会同样发送内存错误信号到该进程。有关页的访问控制信息（只读页、只写页、可读可写页、可执行代码页等）包含在页表项中。对有效的虚拟地址，Linux必须区分页所在的位置，即判断页是在交换文件中，还是在可执行映像中。为此，Linux通过页表项中的信息区分页所在的位置。如果该页的页表项是无效的，但非空，则说明该页处于交换文件中，操

60、作系统要从交换文件装入页（有关内存交换的内容在下一节中讲述）。否则，默认情况下，Linux会分配一个新的物理页并建立一个有效的页表项；对于影像的内存映射来讲，则会分配新的物理页，更新页表项属性信息，并从影像中装入页。这时，所需的页装入了物理内存，页表项也同时被更新，然后进程就可以继续执行了。这种只在必要时才将虚拟页装入物理内存的处理称为“需求分页”。在处理页故障的过程中，因为要涉及到磁盘访问等耗时操作，因此操作系统会选择另外一个进程进入执行状态。4.3.3 Linux 页缓存页缓存经内存映射的文件每次只读取一页内容，读取后的页保存在页缓存中，利用页缓存，可提高文件的访问速度。如图4.7所示，页

61、缓存由page_hash_table组成，它是一个mem_map_t数据结构的指针向量。页缓存的结构是Linux内核中典型的哈希表结构。众所周知，对计算机内存的线性数组的访问是最快速的访问方法，因为线性数组中的每一个元素的位置都可以利用索引值直接计算得到，而这种计算是简单的线性计算。但是，如果要处理大量数据，有时由于受到存储空间的限制，采用线性结构是不切合实际的。但如果采用链表等非线性结构，则元素的检索性能又会大打折扣。哈希表则是一种折衷的方法，它综合了线性结构和非线性结构的优点，可以在大量数据中进行快速的查找。哈希表的结构有多种，在Linux内核中，常见的哈希结构和图4.7的结构类似。要在这

62、种哈希表中访问某个数据，首先要利用哈希函数以目标元素的某个特征值作为函数自变量生成哈希值作为索引，然后利用该索引访问哈希表的线性指针向量。哈希线性表中的指针代表一个链表，该链表所包含的所有节点均具有相同的哈希值，在该链表中查找可访问到指定的数据。哈希函数的选择非常重要，不恰当的哈希函数可能导致大量数据映射到同一哈希值，这种情况下，元素的查找将相当耗时。但是，如果选择恰当的哈希函数，则可以在性能和空间上得到均衡效果。图4.7Linux页缓存示意图在Linux页缓存中，访问page_hash_table的索引由文件的VFS（虚拟文件系统）索引节点inode和内存页在文件中的偏移量生成。有关VFS索

63、引节点的内容将在今后讲述，在这里，应知道每个文件的VFS索引节点inode是唯一的。当系统要从内存映射文件中读取某页时，首先在页缓存中查找，如果发现该页保存在缓存中，则可以免除实际的文件读取，而只需从页缓存中读取，这时，指向mm_map_t数据结构的指针被返回到页故障的处理代码；如果该页不在缓存中，则必须从实际的文件系统影像中读取页，Linux内核首先分配物理页然后从磁盘读取页内容。如果可能，Linux还会预先读取文件中下一页内容，这样，如果进程要连续访问页，则下一页的内容不必再次从文件中读取了，而只需从页缓存中读取。随着影像的读取和执行，页缓存中的内容可能会增多，这时，Linux可移走不再需

64、要的页。当系统中可用的物理内存量变小时，Linux也会通过缩小页缓存的大小而释放更多的物理内存页。4.4 内存交换与高速缓存4.4.1内存交换内存交换当物理内存出现不足时，Linux内存管理子系统需要释放部分物理内存页。这一任务由内核的交换守护进程kswaped 完成，该内核守护进程实际是一个内核线程，它的任务就是保证系统中具有足够的空闲页，从而使内存管理子系统能够有效运行。在系统启动时，这一守护进程由内核的init进程启动。当内核的交换定时器到期时，该进程开始运行。如果kswaped发现系统中的空闲页很少，该进程将按照下面的三种方法减少系统使用的物理页：1减少缓冲区和页高速缓存的大小。页高速

65、缓存中包含内存映射文件的页，可能包含一些系统不再需要的页，类似地，缓冲区高速缓存中也可能包含从物理设备中读取的或写入物理设备的数据，这些缓冲区也可能不再需要，因此，这两个高速缓存可用来释放出空闲页。但是，同时处于这两个高速缓存中的页是不能丢弃的。Linux利用“时钟”算法从系统中选择要丢弃的页，也即每次循环检查mem_map页向量中不同的页块，象时钟的分针循环转动一样。时钟算法的原理见图4.8。每次内核的交换进程运行时，根据对物理内存的需求而选择不同页块大小的mem_map向量进行检查。如果发现某页块处于上述两个高速缓存中，则释放相应的缓冲区，并将页块重新收入free_area结构。图4.8页

66、交换的时钟算法 2.将SystemV共享内存页交换出物理内存。SystemV共享内存页实际是一种进程间通讯机制，系统通过将共享内存页交换到交换文件而释放物理内存。Linux同样使用时钟算法选择要交换出物理内存的页。3.将页交换出物理内存或丢弃。kswaped 首先选择可交换的进程，或其中某些页可从内存中交换出或丢弃的进程。可执行影像的大部分内容可从磁盘影像中获取，因此，这些页可丢弃。选定要交换的进程之后，Linux将把该进程的一小部分页交换出内存，而大部分不会被交换，被锁定的页也不会被交换。Linux利用页的寿命信息选择要交换的页，也即所谓“最近最少使用（Least-Recently-Used，LRU）”算法。n n页的寿命信息保存在页的寿命信息保存在 mem_map_tmem_map_t结构中。最结构中。最初分配某个页时，页的寿命为初分配某个页时，页的寿命为33，每次该页被访，每次该页被访问，其寿命增加问，其寿命增加33，直到，直到2020为至；而当内核的为至；而当内核的交换进程运行时，页寿命减交换进程运行时，页寿命减11。如果某个页的寿。如果某个页的寿命为命为00，则该页可作为交换