第4章 内存管理

第4章 内存管理 本章介绍Linux内存管理子系统的整体概念，讨论存储层次结构、x86存储管理硬件和Linux虚存系统及相关系统工具。

4.1存储层次结构和x86存储管理硬件 4.1.1内存管理基本框架 Linux内核的设计要考虑到在各种不同的微处理器上的实现，所以不能仅仅针对i386结构来设计它的映射机制，而要以虚拟的微处理器和内存管理单元MMU(Memory Management Unit)为基础，设计出一种通用的模式，再将其分别落实到具体的微处理器上。Linux在内存管理的软件实现方面，提供了不同的接口，可以用于各种各样不同地址线宽度的CPU。

Intel 的80386提供了两层影射的页式内存管理的件支持，一层是页面目录称为PGD（Page Directory），另一层是页表称为PT（Page Tables），PT的表项称为PTE（Page Table Elements）。通过它们实现从线性地址到物理地址的转换。这种两层影射方式对于32位地址线的386是很合适的。但Linux要设计成可在不同的CPU下运行，考虑到大于32位地址线宽度的CPU（例如64位的CPU），Linux内核的映射机制被设计成3层，在页面目录和页表之间增设了一层“中间目录”PMD（Page Mid-level Directory）在逻辑上，相应地也把线性地址从高到低分为4个位段，各占若干位，分别用作目录PGD的下标、中间目录PMD的下标、页表中的下标和物理页面内的位移。如图4.1所示。PGD、PMD、PT都是数组。Page Frame是最后得到的物理页。

三层影射过程如下： （1）从控制寄存器CR3中找到页目录的基址。 （2） 以线性地址的最高位段作为下标在PGD中找到确定中间目录的表项的指针。 （3） 以线性地址的次位段作为下标在PMD中找到确定页面表的表项的指针。 （4） 在线性地址的接下来位段为下标在PTE中找到页的指针。 （5）  最后线性地址的位段中为在此页中偏移量。 这样，最终完成了线性地址到物理地址的转换。

假如当要执行某个函数的第一个句子时，CPU会通过32位地址线寻址（2的32次方，可以寻址4G的线性地址空间）。通过MMU执行以上的影射过程，就会在计算机的内存中找到这个句子的物理地址，如果要找的那一句不在物理页中，就会发生一次异常中断，使硬盘和内存发生交互。 在Linux原码的 include/asm-i386/gptable.h 定义了能够包容不同CPU的接口： # if CONFIG_X86_PAE //假如在PAE模式下，用三层影射结构 #include <asm/pgtable-3level.h> #else #include<asm/pgtable-2level.h> //否则用两层 #endif 在pgtable-2level.h中定义了PGD，PMD的结构。 #define PGDIR_SHIFT 22 //页目录是线性地址的31~22位 #define PTRS_PER_PGD 1024 //总共有1024个页目录 #define PMDIR_SHIFT 22 //中间目录不用了 #define PTRS_PER_PMD 1 #define PTRS_PER_PTE1024 //每个页表有1023页

在32位线性地址中的4G虚拟空间中，其中有1G做为内核空间，从0XC0000000到0XFFFFFFFF。每个进程都有自己的3G用户空间，它们共享1G的内核空间。当一个进程从用户空间进入内核空间时，它就不在有自己的进程空间了。 在物理空间中，内核总是从0地址开始的，而在虚拟空间中是丛0XC0000000开始的。内核中的影射是很简单的线性影射，所以0XC0000000就是两者的偏移量。 在page.h中： #define__PAGE_OFFSET (0xc0000000) #definePAGE_OFFSET ((unsigned long ) __PAGE_OFFSET ) #defne __pa(x) ( (unsigned lonsg) (x) – PAGE_OFFSET) // 内核虚拟地址转换到物理地址 #define __va(x) ((void *) ((unsigned long) (x) + PAGE_OFFSET)) // 内核从物理地址到虚拟地址的转换  对i386微处理器来说，CPU实际上不是按3层而是按两层的模型来进行地址映射，这就需要将虚拟的3层映射落实到具体的两层的映射，跳过中间的PMD层次。

4.1.2地址映射的全过程 80386有实方式和保护方式两种工作方式。尽管实方式下80386的功能较Intel先前的微处理器有很大的提高，但只有在保护方式下，80386才能真正发挥作用。在保护方式下，全部32根地址线有效，可寻址达4G字节的物理空间。扩充的存储器分段管理机制和可选的存储器分页管理机制，不仅为存储器共享和保护提供了硬件支持，而且为实现虚拟存储器提供了硬件支持；支持多任务，能快速的进行任务切换和任务保护环境；4个特权级和完善的特权检查机制，既能实现资源共享又能保证代码及数据的安全和保密及任务的隔离；支持虚拟8086方式，便于执行8086代码。

(1) 80386 保护方式的寻址 在保护方式下，当寻址扩展内存中的数据和程序时，仍然使用偏移地址访问位于存储器内的信息，但保护方式下的段地址不再像实方式那样有段寄存器提供，而是在原来存放段地址的段寄存器里含有一个选择子，用于选择描述符表内的一个描述符。描述符描述存储器的位置、长度和访问权限。 保护方式下有两个描述符表：全局描述符表和局部描述符表。全局描述符表包含适用于所有程序的段定义，而局部描述符表通常用于唯一的应用程序。每个描述符表包含8129个描述符，所以任何时刻应用程序最多可用16384个描述符。 每个描述符长8字节，全局和局部描述符表每个最长为64kb。 分页机制式存储管理机制的第二部分。分页机制在段机制之后进行操作，以完成虚拟地址到物理地址的转换。段机制把虚拟地址转换为线性地址，分页机制进一步把线性地址转换为物理地址。 分页机制由微处理器中控制寄存器的内容控制。分页机制由CRO中的PG位启用。若PG=1，启用分页机制。PG=0，不用分页机制，直接把段机制生成的线性地址当作物理地址。 软件生成的线性地址分为三部分，分别用于页目录项、页表项和页偏移地址寻址。

(2) Linux所采用的方法 i386微处理器一律对程序中的地址先进行段式映射，然后才能进行页式映射。而Linux为了减小footprint，提高cache命中率，尽量避免使用段功能以提高可移植性。如通过使用基址为0的段，使逻辑地址等于线性地址。因此Linux所采用的方法实际上使i386的段式映射的过程不起作用。 下面通过一个简单的程序来看看Linux下的地址映射的全过程： #include greeting() { printf(“Hello world!”); } main() greeing();

该程序在主函数中调用greeting 来显示“Hello world!”，经过编译和反汇编的结果如下。 08048568: 8048568: 55push1 %ebp 8048856b:89 e5 mov1 %esp,%ebp 804856b: 68 04 94 04 08push1 $0x8048404 8048570: e8 ff fe ff ffcall 8048474 <_init+0x84> 8048575: 83 c4 04add1 $0x4,%esp 8048578: c9leave 8048579: c3ret 804857a: 89 f6 mov1 %esi,%esi 0804857c : 804857c: 55push1 %ebp 804857d: 89 e5 mov1 %esp,%ebp 804857f: e8 e4 ff ff ffcall 8048568 8048584: c9leave 8048585: c3ret 8048586: 90nop 8048587: 90nop

从上面可以看出，greeting()的地址为0x8048568。在elf格式的可执行代码中，总是在0x8000000开始安排程序的“代码段”，对每个程序都是这样。 程序在main中执行到了“call 8048568”这条指令，要转移到虚拟地址8048568去。 首先是段式映射阶段。地址8048568是一个程序的入口，更重要的是在执行的过程中由CPU的EIP所指向的，所以在代码段中。I386cpu使用CS的当前值作为段式映射的选择子。 内核在建立一个进程时都要将它的段寄存器设置好，把DS、ES、SS都设置成_USER_DS,而把CS设置成_USER_CS,这也就是说，在Linux内核中堆栈段和代码段是不分的。 Index TI DPL #define_KERNEL_CS 0x100000 0000 0001 0|0|00 #define_KERNEL_DS 0x180000 0000 0001 1|0|00 #define_USER_CS 0x230000 0000 0010 0|0|11 #define_USER_DS 0x2B0000 0000 0010 1|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=3

TI全都是0，都使用全局描述表。内核的DPL都为最高级别0；用户的DPL都是最低级别3。_USER_CS在GDT表中是第4项，初始化GDT内容的代码如下：   ENTRY(gdt-table) .quad 0x0000000000000000 // NULL descriptor .quad 0x0000000000000000 // not used .quad 0x00cf9a00000ffff // 0x10 kernel 4GB code at 0x00000000 .quad 0x00cf9200000ffff // 0x18 kernel 4GB data at 0x00000000 .quad 0x00cffa00000ffff // 0x23 user 4GB code at 0x00000000 .quad 0x00cff200000ffff // 0x2b user 4GB data at 0x00000000 GDT 表中第1、2项不用，第3至第5项共4项对应于前面的4个段寄存器的数值。将这4个段描述项的内容展开： K_CS:0000 0000 1100 1111 1001 1010 0000 0000 0000 0000 0000 0000 1111 1111 1111 1111 K_DS:0000 0000 1100 1111 1001 0010 0000 0000 U_CS:0000 0000 1100 1111 11111 1010 0000 0000 U_DS:0000 0000 1100 1111 1111 0010 0000 0000 这4个段描述项的下列内容都是相同的。

·BO-B15/B16-B31 都是0 基地址全为0 ·LO-L15、L16-L19都是1 段的界限全是0xfffff ·G位都是1 段长均为4KB ·D位都是1 32位指令 ·P位都是1 四个段都在内存中 不同之处在于权限级别不同，内核的为0级，用户的为3级。 由此可知，每个段都是从地址0开始的整个4GB地虚存空间，虚地址到线性地址的映射保持原值不变。 再回到greeting 的程序中来，通过段式映射把地址8048568映射到自身，得到了线性地址。 每个进程都有自身的页目录PGD，每当调度一个进程进入运行时，内核都要为即将运行的进程设置好控制寄存器CR3，而MMU硬件总是从CR3中取得当前进程的页目录指针。 当程序要转到地址0x8048568去的时候，进程正在运行中，CR3已经设置好了，指向本进程的页目录了。 8048568： 0000 1000 0000 0100 1000 0101 0110 1000 按照线性地址的格式，最高10位 0000100000，十进制的32，就以下标32去页目录表中找其页目录项。这个页目录项的高20位后面添上12个0就得到该页面表的指针。找到页表后，再看线性地址的中间10位001001000，十进制的72。就以72为下标在找到的页表中找到相应的表项。页面表项重的高20位后添上12个0就得到了物理内存页面的基地址。线性地址的底12位和得到的物理页面的基地址相加就得到要访问的物理地址。

4.1.3 地址映射的效率分析 在页式映射的过程中，CPU要访问内存3次，第1次是页面目录，第2次是页面表，第3次才是真正要访问的目标。这样，把原来不用分页机制一次访问内存就能得到的目标，变为3次访问内存才能得到，执行分页机制在效率上的牺牲太大。 为了减少这种开销，最近被执行过的地址转换结果会被保留在MMU的转换后备缓存（Translation Look-aside Buffer,TLB）中。虽然在第一次用到具体的页面目录和页面表时要到内存中读取，但一旦装入了TLB中，就不需要再到内存中去读取了，而且这些都是由硬件完成的，因此速度很快。 TLB对应权限大于0级的程序来说是不可见的，只有处于系统0层的程序才能对其进行操作。 当控制寄存器CR3的内容变化时，TLB中的所有内容会被自动变为无效。Linux中的_flush_TLB宏就是利用这点工作的。_flush_TLB只是两条汇编指令，把CR3的值保存在临时变量tmpreg里，然后立刻把tmpreg的值拷贝回CR3，这样就将TLB中的全部内容置为无效。除了无效所有的TLB中的内容，还能有选择的无效TLB中某条记录，这就要用到INVLPG指令。

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

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

5 x86的分页机制 x86硬件支持两级页表，奔腾Pro以上的型号还支持硬件支持模式（Physical address Extension Mode）和3级页表。所谓硬件支持模式包括一些特殊寄存器(cr0-cr4)、以及CPU能够识别页表项中的一些标志位并根据访问情况做出反应等等。例如：在读写Present位为0的页或者写Read/Write位为0的页将引起CPU发出page fault异常，访问完页面后自动设置accessed位等。 Linux采用的是一个体系结构无关的三级页表模型，使用一系列的宏来掩盖各种平台的细节。例如，通过把PMD看作只有一项的表并存储在PGD表项中（通常PGD表项中存放的应该是PMD表的首地址），页表的中间目录(PMD)被巧妙地‘折叠’到页表的全局目录(PGD)，从而适应了二级页表硬件。 6. TLB 转换后备缓存TLB（Translation Look-aside Buffer），用来加速页表查找。如果操作系统更改了页表内容，它必须相应的刷新TLB以使CPU不会误用过时的表项。

7. Cache Cache 基本上是对程序员透明的，但是不同的使用方法可以导致大不相同的性能。Linux有许多关键的地方对代码做了精心优化，其中很多就是为了减少对cache不必要的污染。例如把只有出错情况下用到的代码放到.fixup section，把频繁同时使用的数据集中到一个cache行（如struct task_struct），减少一些函数的footprint，在slab分配器里头的slab coloring等。 另外，当新map/remap一页到某个地址、页面换出、页保护改变、进程切换等，也即当cache对应的那个地址的内容或含义有所变化时，cache要无效。当然在很多情况下不需要无效整个cache，只需要无效某个地址或地址范围即可。实际上，Intel在这方面做得非常好，cache的一致性完全由硬件维护。 8． Linux 的相关实现 这一部分的代码和体系结构紧密相关，因此大多位于arch子目录下，而且大量以宏定义和inline函数形式存在于头文件中。在i386平台中，主要的文件包括：

（1）page.h 页大小、页掩码定义：PAGE_SIZE、PAGE_SHIFT和PAGE_MASK。 对页的操作，如清除页内容clear_page、拷贝页copy_page、页对齐page_align。 还有内核虚地址的起始点：著名的PAGE_OFFSET:)和相关的内核中虚实地址转换的宏_pa和_va.。 virt_to_page从一个内核虚地址得到该页的描述结构struct page *。所有物理内存都由一个memmap数组来描述。这个宏就是计算给定地址的物理页在这个数组中的位置。另外这个文件也定义了一个简单的宏检查一个页是不是合法： VALID_PAGE：如果page离memmap数组的开始太远以至于超过了最大物理页面应有的距离则是不合法的。 页表项的定义pgd_t,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_[pte/pmd/pgd]：设置表项值 pte_same：比较 pte_page 从pte得出所在的memmap位置 pte_none：是否为空。 _mk_pte：构造pte pgtable.h中的宏很多，但也比较直观，通常从名字就可以看出宏的意义。如pte_xxx宏的参数是pte_t，而ptep_xxx的参数是pte_t *。 pgtable.h里除了页表操作的宏外，还有cache和TLB刷新操作，这也比较合理，因为他们常常是在页表操作时使用。这里的TLB操作是以_开始的，也就是说，内部使用的，真正对外接口在pgalloc.h中（分开的原因，可能是因为在SMP版本中TLB的刷新函数和单机版本区别较大，有些不再是内嵌函数和宏了）。 （3） pgalloc.h 包括页表项的分配和释放宏/函数,值得注意的是表项高速缓存的使用： pgd/pmd/pte_quicklist 内核中有许多地方使用类似的技巧来减少对内存分配函数的调用，加速频繁使用的分配。如buffer cache中buffer_head和buffer，vm区域中最近使用的区域，还有上面提到的TLB刷新的接口等。 （4） segment.h 定义 _KERNEL_CS[DS] _USER_CS[DS]

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

使用2的幂次大小的内存区域时高速缓存冲突的概率较大，有可能通过仔细安排内存区域的起始地址来减少高速缓存冲突。 缓存一定数量的对象可以减少对buddy系统的调用，从而节省时间并减少由此引起的高速缓存污染。Linux2.2内核实现的slab分配器体现了这些改进思想。 主要数据结构有： kmem_cache_create/kmem_cache_destory kmem_cache_grow/kmem_cache_reap //增长/缩减某类缓存的大小 kmem_cache_alloc/kmem_cache_free //从某类缓存分配/释放一个对象 kmalloc/kfree //通用缓存的分配、释放函数。 相关代码见slab.c。 vmalloc/vfree主要进行物理地址不连续，虚地址连续的内存管理。它使用kernel页表。位于文件vmalloc.c，相对来说比较简单。

2. 基于区的伙伴系统的设计和物理页面的管理 Linux2.4中的内存管理有很大的变化。在物理页面管理上实现了基于区的伙伴系统（zone based buddy system）。区(zone)的是根据内存的不同使用类型划分的。对不同区的内存使用单独的伙伴系统(buddy system)管理，而且独立地监控空闲页等。 内存分配的两大问题是：分配效率及碎片问题。一个好的分配器应该能够快速的满足各种大小的分配要求，同时不能产生大量的碎片浪费空间。伙伴系统是一个常用的比较好的算法。 引入区的概念是为了区分内存的不同使用类型（方法），以便更有效地利用。 Linux2.4有三个区：DMA、Normal和HighMem。前两个在Linux2.2中实际上也是由独立的buddy system管理的，但Linux2.2中还没有明确的zone的概念。DMA区在x86体系结构中通常是小于16兆的物理内存区，因为DMA控制器只能使用这一段的内存。而HighMem是物理地址超过某个值(通常是约900M)的高端内存。其他的是Normal区内存。

在Linux实现中，高地址的内存不能直接被内核使用。内核使用一种特殊的办法，即使用CONFIG_HIGHMEM选项，来使用高地址的内存。HighMem只用于页面高速缓冲和用户进程。这样分开的结果，是可以更有针对性地使用内存，不至于出现把DMA可用的内存大量给无关的用户进程使用，导致驱动程序没法得到足够的DMA内存等情况。此外，每个区都独立地监控本区内存的使用情况。在分配时，系统综合考虑用户的要求和系统现状，判断从哪个区分配比较合适。2.4里分配页面时可能会和高层的VM代码交互(分配时根据空闲页面的情况，内核可能从伙伴系统里分配页面，也可能直接把已经分配的页收回（reclaim）等。 实际上，在更高一层还有NUMA (None Uniformed Memory Access)的支持。在一般的机器中，CPU对每个内存单元（动态随机存取存储器DRAM）的存取速度是一样的。而NUMA是一种体系结构，对系统里的每个处理器来说，不同的内存区域可能有不同的存取时间(一般是由内存和处理器的距离决定)。NUMA中访问速度相同的一个内存区域称为一个节点（node），NUMA的主要任务就是要尽量减少node之间的通信，使得每个处理器要用到的数据尽可能放在对它来说最快的node中。2.4内核中node的相应数据结构是pg_data_t，每个node拥有自己的memmap数组，把自己的内存分成几个zone，每个zone再用独立的伙伴系统管理物理页面。

整个分配器的主要接口是下面的函数（参看mm.h 及page_alloc.c）： struct page * alloc_pages(int gfp_mask, unsigned long order)：根据gftp_mask的要求，从适当的区分配2^order个页面，返回第一个页的描述符。 #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) get_free_page：分配一个已清零的页面。 _free_page(s) 和free_page(s)释放页面（一个/多个）前者以页面描述符为参数，后者以页面地址为参数。

4.2 Linux虚存系统 虚拟内存的基本思想是，在计算机中运行的程序，其代码、数据和堆栈的总量可以超过实际内存的大小，操作系统只将当前使用的程序块保留在内存中，其余的程序块则保留在磁盘上。必要时，操作系统负责在磁盘和内存之间交换程序块。 4.2.1 使用虚存的优点 Linux 也采用虚拟内存管理机制，使用虚拟内存有如下优点： （1）大地址空间。对运行在系统中的进程而言，可用的内存总量可以超过系统的物理内存总量，甚至可以达到好几倍。运行在 i386 平台上的 Linux 进程，其地址空间可达 4GB。 （2）进程保护。每个进程拥有自己的虚拟地址空间，这些虚拟地址对应的物理地址完全和其他进程的物理地址隔离，从而避免进程之间的互相影响。 （3）内存映射。利用内存映射，可以将程序影像或数据文件映射到进程的虚拟地址空间中，对程序代码和数据的访问与访问内存单元一样。

（4）公平的物理内存分配。虚拟内存机制可保证系统中运行的进程平等分享系统中的物理内存。 （5）共享虚拟内存。利用虚拟内存可以方便隔离各进程的地址空间，但是，如果将不同进程的虚拟地址映射到同一物理地址，则可实现内存共享。这就是共享虚拟内存的本质，利用共享虚拟内存不仅可以节省物理内存的使用（如果两个进程的部分或全部代码相同，只需在物理内存中保留一份相同的代码即可），而且可以实现所谓“共享内存”的进程间通讯机制（两个进程通过同一物理内存区域进行数据交换）。 图 4.2虚拟地址到物理地址的映射模型 图 4.2虚拟地址到物理地址的映射模型

Linux 中的虚拟内存采用所谓的“分页”机制。分页机制将虚拟地址空间和物理地址空间划分为大小相同的块，这样的块称为“内存页”或简称为“页”。通过虚拟内存地址空间的页与物理地址空间中的页之间的映射，分页机制可实现虚拟内存地址到物理内存地址之间的转换。图 4.2 说明了两个进程的虚拟地址空间的部分页到物理地址空间的部分页之间的映射关系。 i386 平台上的 Linux 页大小为 4K 字节，而在 Alpha AXP 系统中使用 8K 字节的页。不管是虚拟内存页还是物理内存页，它们均被给定一个唯一的“页帧编号”（Page Frame Number ，PFN）。在上述映射模型中，虚拟内存地址由两部分组成，其中一部分就是页帧编号，而另一部分则是偏移量。CPU 负责将虚拟页帧编号翻译为相应的物理页帧编号。物理页帧编号实际是物理地址的高位，也称为页基地址，页基地址加上偏移量就是物理内存地址（这和 DOS 64K 段基地址及段偏移量类似）。为此，CPU 利用“页表”实现虚拟页帧编号到物理页帧编号的转换。

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

一般来说，页故障的原因可能是因为进程访问了非法的虚拟地址，也可能是因为进程要访问的物理地址当前不在物理内存中，这时，操作系统负责将所需的内存页装入物理内存。 上面就是虚拟内存的抽象模型，但 Linux 中的虚拟内存机制要更复杂一些。从性能的角度考虑，如果内核本身也需要进行分页，并要为内核代码和数据页维护一个页表的话，则系统的性能会下降很多。为此，Linux 的内核运行在所谓的“物理地址模式”，CPU 不必在这种模式下进行地址转换，物理地址模式的实现和实际的 CPU 类型有关。 4.3 Linux 的内存页表 在 i386 系统中，虚拟地址空间的大小是 4G，因此，全部的虚拟内存空间划分为 1M 页。如果用一个页表描述这种映射关系，那么这一映射表就要有 1M 个表项，当每个表项占用 4 个字节时，全部表项占用的字节数就为 4M，为了避免占用如此巨大的内存资源来存储页表，i386 系列 CPU 采用两级页表，Alpha AXP 系统使用三级页表。Linux 为了避免硬件的不同细节影响内核的实施，假定有三级页表。如图 4.3 所示，一个虚拟地址可分为多个域，不同域的数据指出了对应级别页表中的偏移量。为了将一个虚拟地址转换为物理地址，处理器根据这三个级别域，每次将一个级别域中

的值转换为对应页表的物理页偏移量，然后从中获得下一级页表的页帧编号。如此进行3次，就可以找出虚拟内存对应的实际物理内存。不同 CPU 的页级数目不同，Linux 内核源代码则利用 C 语言的宏将具体的硬件差别隐藏了起来。例如，对 i386 的 Linux 内核代码来说，三级的页表转换宏实际只有两个在起作用。 4.3.1内存页的分配和释放 系统运行过程中，经常需要进行物理内存页的分配或释放。例如，执行程序时，操作系统需要为相应的进程分配页，而进程终止时，则要释放这些物理页。再如，页表本身也需要动态分配和释放。物理页的分配和释放机制及其相关数据结构是虚拟内存子系统的关键部分。

一般而言，有两种方法可用来管理内存的分配和释放。一种是采用位图，另外一种是采用链表。 图 4.4多级页表示意图 一般而言，有两种方法可用来管理内存的分配和释放。一种是采用位图，另外一种是采用链表。 利用位图可记录内存单元的使用情况。例如，如果某个系统有 1024 字节内存，而内存的分配单元是 4 字节，则可以利用 1024/（4*8） = 32 个字节来记录使用情

况。这 32 个字节的每个位分别代表相应分配单元的使用情况。如果位图中某个位为 1，则对应的分配单元是空闲的。利用这一办法，内存的分配就可以通过对位值的检测来简化。如果一次要分配 5 个单元的空间，内存管理程序就需要找出 5 个连续位值均为 1 的位图位置，但这种操作比较慢，因为连续的位有时要跨越字节边界。 利用链表则可以分别记录已分配的内存单元和空闲的内存单元。通常这些内存单元设计为双向链表结构，从而可加速空闲内存的搜索或链表的处理。这种方法相对位图方法要好一些，也更加有效。 Linux 的物理页分配采用链表和位图结合的方法，如图 4.4所示。Linux 内核定义了一个称为 free_area 的数组，该数组的每一项描述某一种页块的信息。第一个元素描述单个页的信息，第二个元素则描述以 2 个页为一个块的页块信息，第三个元素描述以 4 个页为一个块的页块信息，依此类推，所描述的页块大 小描述以 4 个页为一个块的页块信息，依此类推，所描述的页块大小以 2 的倍数增加。free_area 数组的每项包含两个元素：list 和 map。list 是一个双向链表的头指针，该双向链表的每个节点包含空闲页块的起始物理页帧编号；而 map 则是记录这种页块组分配情况的位图，例如，位图的第 N 位为 1，则表明第 N 个页块是空闲的。从图中也可以看到，用来记录页块组分配情况的位图大小各不相同，显然页块越小，位图越大。

图 4.5 中，free_area 数组的元素 0包含了一个空闲页（页帧编号为 0）；而元素 2 则包含了两个以 4 页为大小的空闲页块，第一个页块的起始页帧编号为 4，而另一个页块的起始页帧编号为 56。 图 4.5 Linux 物理页块的分配示意

Linux 采用 Buddy 算法有效分配和释放物理页块。按照上述数据结构，Linux 可以分配的内存大小只能是 1 个页块，2 个页块或 4 个页块等等。在分配物理页块时，Linux 首先在 free_area 数组中搜索大于或等于要求尺寸的最小页块信息，然后在对应的 list 双向链表中寻找空闲页块，如果没有空闲页块，Linux 则继续搜索更大的页块信息，直到发现一个空闲的页块为止。如果搜索到的页块大于满足要求的最小页块，则只需将该页块剩余的部分划分为小的页块并添加到相应的 list 链表中。 页块的分配会导致内存的碎片化，而页块的释放则可以将页块重新组合成大的页块。如果和被释放的页块大小相等的相邻页块是空闲的，则可以将这两个页块组合成一个大的页块，这一过程一直继续到把所有可能的页块组合成尽可能大的页块为止。知道了上述原理，读者可以自己想象系统启动时，初始的 free_area 数组中的信息。

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

合。例如，当进程试图访问的虚拟内存当前不在物理内存当中时（通过页故障），Linux 就可以利用操作集中的一个例程执行正确的操作，在这种情况下为 nopage 操作。 当可执行影像映射到进程的虚拟地址空间时，将产生一组 vm_area_struct 结构来描述虚拟内存区域的起始点和终止点，每个 vm_struct 结构代表可执行影像的一部分，可能是可执行代码，也可能是初始化的变量或未初始化的数据。随着 vm_area_struct结构的生成，这些结构所描述的虚拟内存区域上的标准操作函数也由 Linux 初始化。 某个可执行影像映射到进程虚拟内存中并开始执行时，因为只有很少一部分装入了物理内存，因此很快就会访问尚未装入物理内存的虚拟内存区域。这时，处理器将向 Linux 报告一个页故障及其对应的故障原因。 这种页故障的出现原因有两种，一是程序出现错误，例如向随机物理内存中写入数据，这种情况下，虚拟内存是无效的，Linux 将向程序发送 SIGSEGV 信号并终止程序的运行；另一种情况是，虚拟地址有效，但其所对应的页当前不在物理内存中，这时，操作系统必须从磁盘影像或交换文件中将内存装入物理内存。 如前所述，Linux 利用 vm_area_struct 数据结构描述进程的虚拟内存空间，为了查找出现页故障虚拟内存相应的 vm_area_struct 结构的位置，Linux 内核同时维护一个由 vm_area_struct 结构形成的 AVL（Adelson-Velskii and Landis）树。利用 AVL 树，可快速寻找发生页故障的虚拟地址所在的内存页区域。Linux在页故障发生时，如果搜索不到这一内存区域，则说明该虚拟地址是无效的，否则该虚拟地址是有效的。 也有可能因为进程在虚拟地址上进行的操作非法而产生页故障，例如在只读页中写入数据。这时操作系统会同样发送内存错误信号到该进程。有关页的访问控制信息（只读页、只写页、可读可写页、可执行代码页等）包含在页表项中。

对有效的虚拟地址，Linux 必须区分页所在的位置，即判断页是在交换文件中，还是在可执行映像中。为此，Linux 通过页表项中的信息区分页所在的位置。如果该页的页表项是无效的，但非空，则说明该页处于交换文件中，操作系统要从交换文件装入页（有关内存交换的内容在下一节中讲述）。否则，默认情况下，Linux 会分配一个新的物理页并建立一个有效的页表项；对于影像的内存映射来讲，则会分配新的物理页，更新页表项属性信息，并从影像中装入页。 这时，所需的页装入了物理内存，页表项也同时被更新，然后进程就可以继续执行了。这种只在必要时才将虚拟页装入物理内存的处理称为“需求分页”。 在处理页故障的过程中，因为要涉及到磁盘访问等耗时操作，因此操作系统会选择另外一个进程进入执行状态。

4.3.3 Linux 页缓存 经内存映射的文件每次只读取一页内容，读取后的页保存在页缓存中，利用页缓存，可提高文件的访问速度。如图 4.7 所示，页缓存由 page_hash_table 组成，它是一个 mem_map_t 数据结构的指针向量。页缓存的结构是 Linux 内核中典型的哈希表结构。众所周知，对计算机内存的线性数组的访问是最快速的访问方法，因为线性数组中的每一个元素的位置都可以利用索引值直接计算得到，而这种计算是简单的线性计算。但是，如果要处理大量数据，有时由于受到存储空间的限制，采用线性结构是不切合实际的。但如果采用链表等非线性结构，则元素的检索性能又会大打折扣。哈希表则是一种折衷的方法，它综合了线性结构和非线性结构的优点，可以在大量数据中进行快速的查找。哈希表的结构有多种，在 Linux 内核中，常见的哈希结构和图 4.7 的结构类似。要在这种哈希表中访问某个数据，首先要利用哈希函数以目标元素的某个特征值作为函数自变量生成哈希值作为索引，然后利用该索引访问哈希表的线性指针向量。哈希线性表中的指针代表一个链表，该链表所包含的所有节点均具有相同的哈希值，在该链表中查找可访问到指定的数据。哈希函数的选择非常重要，不恰当的哈希函数可能导致大量数据映射到同一哈希值，这种情况下，元素的查找将相当耗时。但是，如果选择恰当的哈希函数，则可以在性能和空间上得到均衡效果。

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

4.4 内存交换与高速缓存 4.4.1内存交换 当物理内存出现不足时，Linux 内存管理子系统需要释放部分物理内存页。这一任务由内核的交换守护进程 kswaped 完成，该内核守护进程实际是一个内核线程，它的任务就是保证系统中具有足够的空闲页，从而使内存管理子系统能够有效运行。 在系统启动时，这一守护进程由内核的 init 进程启动。当内核的交换定时器到期时，该进程开始运行。如果 kswaped 发现系统中的空闲页很少，该进程将按照下面的三种方法减少系统使用的物理页： 1．减少缓冲区和页高速缓存的大小。页高速缓存中包含内存映射文件的页，可能包含一些系统不再需要的页，类似地，缓冲区高速缓存中也可能包含从物理设备中读取的或写入物理设备的数据，这些缓冲区也可能不再需要，因此，这两个高速缓存可用来释放出空闲页。但是，同时处于这两个高速缓存中的页是不能丢弃的。Linux 利用“时钟”算法从系统中选择要丢弃的页，也即每次循环检查 mem_map 页向量中不同的页块，象时钟的分针循环转动一样。时钟算法的原理见图 4.8。每次内核的交换进程运行时，根据对物理内存的需求而选择不同页块大小的 mem_map 向量进行检查。如果发现某页块处于上述两个高速缓存中，则释放相应的缓冲区，并将页块重新收入 free_area 结构。

图 4.8页交换的时钟算法 2.将System V 共享内存页交换出物理内存。System V 共享内存页实际是一种进程间通讯机制，系统通过将共享内存页交换到交换文件而释放物理内存。Linux 同样使用时钟算法选择要交换出物理内存的页。 3.将页交换出物理内存或丢弃。kswaped 首先选择可交换的进程，或其中某些页可从内存中交换出或丢弃的进程。可执行影像的大部分内容可从磁盘影像中获取，因此，这些页可丢弃。选定要交换的进程之后，Linux 将把该进程的一小部分页交换出内存，而大部分不会被交换，被锁定的页也不会被交换。Linux 利用页的寿命信息选择要交换的页，也即所谓“最近最少使用（Least-Recently-Used，LRU）”算法。

页的寿命信息保存在 mem_map_t 结构中。最初分配某个页时，页的寿命为 3，每次该页被访问，其寿命增加 3，直到 20 为至；而当内核的交换进程运行时，页寿命减 1。如果某个页的寿命为 0，则该页可作为交换候选页。如果是“脏”页（该信息保存在页表项中），则可将该页交换出物理内存。但是，进程的虚拟内存区域可具有自己的交换操作例程（定义在虚拟内存操作集中），这时，将利用该例程执行交换操作，否则，交换守护进程在交换文件中分配页，并将该页写入交换文件。 当某物理页交换到交换文件之后，该页对应的页表项被标志为无效，同时包换该页在交换文件中的位置信息；而被释放出的物理页则被收回到 free_area 数据结构中。 根据被释放的页数目，kswaped 会自动调节交换定时器的间隔，以便能够有足够的时间释放更多的页而保证足够的空闲页。 交换文件中的页是经过修改的页（通过在页表项中设置相应的位而标志该页为“脏”页），则当进程再次访问该页时，操作系统必须从交换文件中将该页交换到物理内存。

4.4.2高速缓存 不管在硬件设计还是软件设计中，高速缓存是获得高性能的常用手段。Linux 使用了多种和内存管理相关的高速缓存： （1）缓冲区高速缓存：缓冲区高速缓存中包含了由块设备使用的数据缓冲区。这些缓冲区中包含了从设备中读取的数据块或写入设备的数据块。缓冲区高速缓存由设备标识号和块标号索引，因此可以快速找出数据块。如果数据能够在缓冲区高速缓存中找到，则系统就没有必要在物理块设备上进行实际的读操作。 （2）页高速缓存：这一高速缓存用来加速对磁盘上的影像和数据的访问。它用来缓存某个文件的逻辑内容，并通过文件的 VFS 索引节点和偏移量访问。当页从磁盘上读到物理内存时，就缓存在页高速缓存中。 （3）交换高速缓存：只有修改后（脏）的页才保存在交换文件中。修改后的页写入交换文件后，如果该页再次被交换但未被修改时，就没有必要写入交换文件，相反，只需丢弃该页。交换高速缓存实际包含了一个页表项链表，系统的每个物理页对应一个页表项。对交换出的页，该页表项包含保存该页的交换文件信息，以及该页在交换文件中的位置信息。如果某个交换页表项非零，则表明保存在交换文件中的对应物理页没有被修改。如果这一页在后续的操作中被修改，则处于交换缓存中的页表项被清零。当 Linux 需要从物理内存中交换出某个页时，它首先分析交换缓存中的信息，如果缓存中包含该物理页的一个非零页表项，则说明该页交换出内存后还没有被修改过，这时，系统只需丢弃该页。 （4）硬件高速缓存：常见的硬件缓存是对页表项的缓存，这一工作实际由处理器完成，其操作和具体的处理器硬件有关。

4.5相关系统工具 Linux 可以利用文件系统中通常的文件作为交换文件，也可以利用某个分区进行交换操作，因此，通常把交换文件或交换分区称为“交换空间”。在交换分区上的交换操作较快，而利用交换文件可方便改变交换空间大小。Linux 还可以使用多个交换分区或交换文件进行交换操作。本节主要讲述有关交换空间的系统工具。 4.5.1建立交换空间 作为交换空间的交换文件实际就是通常的文件，但文件的扇区必须是连续的，也即，文件中必须没有“洞”，另外，交换文件必须保存在本地硬盘上。 由于内核要利用交换空间进行快速的内存页交换，因此，它不进行任何文件扇区的检查，而认为扇区是连续的。由于这一原因，交换文件不能包含洞。可用下面的命令建立无洞的交换文件： $ dd if=/dev/zero of=/extra-swap bs=1024 count=2048 2048+0 records in 2048+0 records out 上面的命令建立了一个名称为 extra-swap，大小为 2048K 字节的交换文件。对 i386 系统而言，由于其页尺寸为 4K，因此最好建立一个大小为 4K 倍数的交换文件；对 Alpha AXP 系统而言，最好建立大小为 8K 倍数的交换文件。 交换分区和其他分区也没有什么不同，可象建立其他分区一样建立交换分区。但该分区不包含任何文件系统。分区类型对内核来讲并不重要，但最好设置为 Linux Swap 类型（即类型 82）。

建立交换文件或交换分区之后，需要在文件或分区的开头写入签名，写入的签名实际是由内核使用的一些管理信息。写入签名的命令为 mkswap，如下所示： $ mkswap /extra-swp 2048 Setting up swapspace, size = 2088960 bytes $ 这时，新建立的交换空间尚未开始使用。使用 mkswap 命令时必须小心，因为该命令不会检查文件或分区内容，因此极有可能覆盖有用的信息，或破坏分区上的有效文件系统信息。 Linux 内存管理子系统将每个交换空间的大小限制在 127M （实际为 (4096-10)*8*4096 = 133890048 Byte = 127.6875Mb）。可以在系统中同时使用 16 个交换空间，从而使交换空间总量达到 2GB。 4.5.2使用交换空间 利用 swapon 命令可将经过初始化的交换空间投入使用。如下所示： $ swapon /extra-swap $ 如果在 /etc/fstab 文件中列出交换空间，则可自动将交换空间投入使用： /dev/hda5 noneswap sw00 /extra-swapnoneswap sw00 实际上，启动脚本会运行 swapon -a 命令，从而将所有出现在 /etc/fstab 文件中的交换空间投入使用。

利用 free 命令，可查看交换空间的使用。如下所示： total used free shared buffers Mem: 15152 14896 256 12404 2528-/+ buffers: 12368 2784 Swap: 32452 6684 25768 $ 该命令输出的第一行（Mem: ） 显示了系统中物理内存的使用情况。total 列显示的是系统中的物理内存总量；used 列显示正在使用的内存数量；free 列显示空闲的内存量；shared 列显示由多个进程共享的内存量，该内存量越多越好；buffers 显示了当前的缓冲区高速缓存的大小。 输出的最后一行 （Swap: ） 显示了有关交换空间的类似信息。如果该行的内容均为 0，表明当前没有活动的交换空间。 利用top命令或查看/proc文件系统中的 /proc/meminfo 文件可获得相同的信息。 利用 swapoff 命令可移去使用中的交换空间。但该命令应只用于临时交换空间，否则有可能造成系统崩溃。 swapoff –a 命令按照 /etc/fstab 文件中的内容移去所有的交换空间，但任何手工投入使用的交换空间保留不变。

4.5.3分配交换空间 大多数人认为，交换空间的总量应该是系统物理内存量的两倍，实际上这一规则是不正确的，正确的交换空间大小应按如下规则确定： (1) 估计需要的内存总量。运行想同时运行的所有程序，并利用free或ps程序估计所需的内存总量（只需大概估计）。 (2) 增加一些安全性余量。 (3) 减去已有的物理内存数量，然后将所得数据圆整为MB，这就是应当分配的交换空间大小。 (4) 如果得到的交换空间大小远远大于物理内存量，则说明需要增加物理内存数量，否则系统性能会因为过分的页交换而下降。 当计算的结果说明不需要任何交换空间时，也有必要使用交换空间。Linux 从性能的角度出发，会在磁盘空闲时将某些页交换到交换空间中，以便减少必要时的交换时间。另外，如果在不同的磁盘上建立多个交换空间，有可能提高页交换的速度，这是因为某些硬盘驱动器可同时在不同的磁盘上进行读写操作。 4.5.4缓冲区高速缓存的守护进程 Linux 采用了缓冲区高速缓存机制，因此有可能出现写磁盘的命令已经返回，但实际的写操作还未执行的情况。因此，应当使用正常的关机命令关机，而不应直接关掉计算机的电源。用户也可以使用 sync 命令刷新缓冲区高速缓存。在 Linux 系统中，除了传统的 update 守护进程之外，还有一个额外的守护进程 dbflush，这一进程可在一定的时间间隔强迫把“buffer cache”中的内容刷新至硬盘，并更新超级块。 dbflush 在 Linux 系统中由 update 启动。如果由于某种原因该进程僵死了，则内核会发送警告信息，这时需要手工启动该进程（/sbin/update）。

思考与练习 1. 什么是虚拟存储器，它的容量如何确定？最大是多少？ 2. 为什么把虚存分成几个区域？ 3. 在Windows 98或OS/2中你使用过哪些有关虚存的API？你当时为什么要那么做？ 4. 为什么要进行地址变换？有无不变换的情况？如有请说明。 5. 试从集合论角度给地址变换下定义。 6. 在固定分区中每个分区的大小必须是不相同的吗？分区的个数是固定的吗？能否把一个进程空间分割到两个分区中？如能，怎么做？如不能请说明理由。 7. 静态重定位，动态重定位，静态链接，动态链接各有什么作用？ 8. 基址／限长寄存器，上／下界寄存器，存储键各有什么作用 9.自由区初始状态为：从0地址开始有10000个空闲单元，按可变分区首次适应策略，写出分配与回收算法 10.能否把页式管理看成是固定分区的推广？为什么？ 11. 你认为页面是长好呢还是短好呢？理由呢？ 12. 为什么被共享的页面在两个共享进程空间中必须有相同页号？在什么条件下可以打破这个限制？ 13. 页式管理主存总容量576K，平均每个进程占用32K，若页表每行使用一个单元，试求①最佳页面尺寸，②支持页式管理的空间开销。 14. 在请求页式管理中有哪些页面置换算法(不限于教材)？分析它们的优缺点。

15. 什么叫做程序的局部性？操作系统怎样利用局部性？局部性对你的编程有什么启示？ 16. 为什么要设置“正在传输”的页面状态？若不设置它将会产生什么问题？你有什么解决办法？ 17. “扩充主存”有哪几种办法？比较它们的优缺点。 18. 被动态链接的分段一定不在主存吗？为什么？ 19. 请求段页式有什么优缺点？当前最流行的是哪一种存储管理方案？ 20.Linux的系统页表和进程页表之间有什么关系？虚存页表中究竟有无内容？