3.1 虚拟存储器 3.2 内存管理方式 段页机制 3.4 Linux存储管理 3.5 小结 习题

Presentation on theme: "3.1 虚拟存储器 3.2 内存管理方式 段页机制 3.4 Linux存储管理 3.5 小结 习题"— Presentation transcript:

1 3.1 虚拟存储器 3.2 内存管理方式 3.3 80386段页机制 3.4 Linux存储管理 3.5 小结 习题
第3章 存 储 管 理 3.1 虚拟存储器 3.2 内存管理方式 段页机制 3.4 Linux存储管理 3.5 小结 习题

2 每一个要运行的程序，必须首先进入内存，然而，每一台计算机的内存容量都是有限而宝贵的。存储管理的任务是方便用户使用存储资源，在有限的物理空间内使更多的用户进程高效地获得和使用尽可能多的存储空间，从而提高系统的整体性能。 现代操作系统中普遍采用基于虚拟存储器的概念来统一管理内存和外存，实现逻辑上的大容量存储空间。

3 本章首先介绍虚拟存储器的基本概念及使用虚拟存储器的依据和出发点——局部性原理，即在程序的运行过程中，总是集中地访问某一个程序段。根据这样的原理，可以把物理内存按照一定的规则划分为小部分，每次只装入某个进程必要的一部分内容就开始运行，在运行过程中，再根据需要装入新的内容。不同的划分规则形成不同的存储管理技术，我们简单介绍分区、页式、段式和段页式管理的基本思想。接着介绍Intel 80386硬件存储管理机制，最后学习Linux系统在这种硬件平台的基本存储管理机制。

4 3.1 虚拟存储器 计算机系统的存储器分为内存（主存）和外存（硬盘）。内存的价格昂贵，速度高，存储容量有限；外存价格便宜，速度慢，存储容量很大，适合于存放大量数据。为了使更多的用户进程合理、充分地使用存储资源，操作系统统一管理内存和外存，即把内存中暂时不用的内容放在硬盘上，内存中就可以腾出一部分空间，可以从硬盘装入其他迫切需要的内容。因此，从效果上看，计算机系统好像为用户提供了一个其存储容量比实际主存大得多的存储器。人们称这个存储器为虚拟存储器。

5 局部性原理 实验证明，在几乎所有进程的执行过程中，某一个特定的时间段中，CPU不是随机地访问整个程序或数据，而是集中地访问程序或数据的某一个部分。进程的这种访问特性称为局部性原理。 与CPU访问该局部内的数据和代码的次数相比，局部段的变化很缓慢，正是基于这样的原理，我们才有可能实现虚拟存储管理。把进程的所有内容划分为一个个小的部分，首先只把系统所必需的部分数据装入内存，其余部分就放在外存中，开始运行之后，再把所需要的其他部分换入内存，同时把不再需要的部分从内存中换到硬盘或者清除掉。当然，与之相配合，实际的内存也要划分为对应的小部分。

6 这种内外存之间的数据交换对用户进程来讲是透明的。从用户进程的角度来看，系统好像提供了一个很大的内存一样，整个进程都能装进去而且正常运行，这种逻辑上的大容量存储空间就可以称为虚拟存储器。实际上，是操作系统的存储管理起了作用，用多次内外存数据交换的时间换来了大容量的并不真正存在的（虚拟的）内存。因此，可以想象，访问虚拟存储器的速度要比访问真正内存的速度要慢。

7 虚拟地址和虚拟地址空间 内存中同时存在多个进程，每个进程的地址都是以0地址作为起始地址的虚拟地址空间，这个虚地址空间可以是线性的（一维的），也可以是多维的，这要取决于系统采用的存储管理方式。进程中的每一个指令和数据在这样的虚地址空间中都有一个惟一确定的地址，即虚拟地址。 每一个进程都具有各自独立的虚拟地址空间，而整个系统只有一个物理地址空间。任何一个要执行的进程，都必须进入真正的内存中，在内存的物理空间中存在，这就需要在虚拟地址空间和物理地址空间之间建立适当的映射关系。通过这种映射关系，逐部分地把存在于虚拟地址空间中的进程要执行的

8 部分放在物理地址空间中，而其他暂时不执行的部分放在外部存储器中，内外存动态地传递数据，最终完成整个进程所执行的任务。这种映射，也称为地址变换，是操作系统在硬件的配合下实现的。
系统中的每一个进程，都有一个惟一的地址映射关系，也就是说，虚拟地址空间到物理地址空间是一个多对一的映射关系。这样，不同的进程有不同的虚拟地址空间和映射变换，可以方便地实现进程之间的存储保护，避免数据和程序遭受其他进程无意或者恶意的访问，同时，它们都映射到惟一的物理空间，可以通过多个进程同时映射同一个物理地址的方式实现数据和程序的共享。

9 3.2 内存管理方式 虚拟存储的每一个要运行的程序，都必须首先进入内存，但是，每一台计算机的内存容量都是有限而宝贵的。管理技术，通常是基于局部性原理的，即把整个进程的虚拟地址空间划分为小的部分，同时把内存也划分为小的部分，在虚拟地址空间和物理地址空间之间建立特定的映射关系，进程的内容分批分期进入内存中特定的位置，其余部分在外存中，在需要的时候再传递到内存，用内存和外存的统一管理来实现内存扩充。

10 在虚拟存储技术的发展过程中，使用了不同的地址空间划分方法和映射关系，这些不同的划分和映射对应于不同的存储管理方式，本节介绍几种能够实现虚拟存储的地址空间划分方式。
页 把进程的虚拟地址空间划分为相等大小的部分，每个部分称为页（page），同时把物理内存空间也按照页的大小划分为小的部分，称为页面（page frame，也称为页架或页框）。对于80386体系，页和页面的大小都为4K字节。

11 在页和页面之间建立一一映射关系，连续的一维虚拟地址空间可以分别存放在不同物理空间中，因此，物理存储中，每个页面内部地址连续，而页面之间的地址可以是不连续的。页和页面之间的映射关系记录在一个表格中，这样的表称为页表。每一个进程使用惟一的页表，页表的每一项数据称为页表项，表示虚拟空间中某一页和实际物理空间中某一页面的对应关系，页表也存储在物理空间内，如图3.1所示。

12 图3.1 页式管理:页表（左）及相应的页、页面对应关系（右）示意图

13 从上图可以看出，连续的一维虚拟空间经过变换，映射到物理空间中不连续的页面中。利用分页机制实现虚拟存储管理称为页式存储管理。管理过程中，内外存的数据传递是以页为单位。页式管理采用请求调页或者预调页技术实现内外存的统一管理，内存中同时只存放少量经常执行或者即将执行的页，而其他不经常使用或暂时不会执行的页，存放在外存中，等需要的时候再调入内存。 利用分页技术将一维连续虚拟空间划分为一个个页，进程的虚拟地址由两个部分组成：页号P和页内地址（偏移量）W。这两个部分的虚拟地址经过地址变换后，映射到物理内存的对应单元。具体的地址变换过程如图3.2所示。

14 图3.2 页式内存管理地址变换示意图

15 操作系统为每一个进程维护一个独立的页表，进程正在执行的时候，页表信息记录在页表控制寄存器中，系统根据寄存器的值得到该进程对应页表的地址，同时利用页号，就可以得到该页对应的页表项。查找页表，获得了页表所映射的页面号，由页面号和页内地址，就可以直接找到内存中的对应存储单元。 在整个变换过程中，需要两次访问物理内存，第一次是查找页表，第二次是获取数据。为了提高效率，硬件一般提供一个高速的联想寄存器，构成一个快表（translation lookaside buffer），把当前进程中经常使用的页表项放在快表中，地址变换过程中，首先访问快表，如果该页表项存在于快表中，就

16 可以直接得到对应的页面号，如果不在快表中，再去查找页表得到页面号，快表的访问速度要比内存快得多，这样就可以提高内存的访问速度。
采用页式管理，实现了进程的程序和数据非连续存放，对内存和外存统一管理，得到更大的虚拟存储空间，可以同时容纳和运行更多的进程，有利于系统整体性能的提高。缺点是增加了系统开销，而且需要一定的硬件支持。由于虚拟空间是连续的，整个进程按照一维地址顺序排列，同一个程序段在分页的过程中，可能分别位于不同的页中，代码和数据的共享比较困难。

17 段 段式管理的基本思想是把整个程序按照逻辑结构划分为不同的段，每个段可以是一个函数（过程）或者数据，有自己的名称，段大小是不相等的，段与段之间不存在顺序关系。这样，进程具有一个二维的虚拟空间。 内存的管理以段为单位，把正在执行的段放在内存中，其他段暂时放在外存中，当需要执行时再传递到内存中。这样，也可以实现大容量的虚拟存储器。

18 段式管理中，进程的虚拟地址是二维的，由段号和段内偏移地址构成。与页式管理的区别在于，段号是不连续的，段的大小是可变的。在二维虚拟空间与物理空间之间需要建立一一映射关系，即地址
变换，这种变换关系记录在一个称为段表的表格中，系统为每一个进程维护一张段表，通过查找段表，就可以得到虚拟地址所对应的物理单元。 段式存储管理的优点在于使用了大小可变的虚拟地址空间划分方法，按照程序的固有逻辑关系来分段，便于进程之间存储共享。但是，地址变换关系更为复杂，需要更多的硬件支持，实现起来更为麻烦，同时也带来了更大的系统开销。

19 段页 段页式存储管理，综合利用段式和页式管理的思想，把整个二维虚拟空间先分段，然后在段内分页。以页为最小的存储管理单位来实现虚拟存储。一方面可以按照程序的逻辑关系来划分进程空间的段，另一方面使用页来存放每一个段的内容，内外存交换以统一格式和大小的页来进行。 这种管理模式下，虚拟地址要包括三个部分：段号、页号和页内偏移地址，地址变换也要经过两层次映射才能够实现，首先从二维虚拟空间映射到一个线性虚拟空间，然后再从线性空间映射到物理空间。可以想象，整个变换过程更为复杂，需要大量的硬件支持和系统开销。

20 段页机制 上一节，我们介绍了不同的存储管理方法：页式、段式和段页式。这些方法的依据都是局部性原理，区别在于存储空间的划分和映射方法。这些管理方法都需要一定的硬件支持。本节，针对Linux系统的主要平台之一Intel 80386（简称I386）系统，介绍该系统的段页式硬件支持机制。

21 实模式与保护模式 80386是Intel公司推出的32位CISC芯片，此后，该公司又相继推出80486、Pentium(P5)、Pentium Pro、PⅡ、PⅢ等一系列向下兼容的32位芯片。本节讨论的特点是针对以I386为代表的整个芯片系列。 I386有两种工作模式，实地址模式和虚拟地址模式，后者又称保护模式。实地址模式与早期的8086兼容，不能启用分页机制，不区分特权级，分段机制也受到限制，直接寻址方式，只能寻址1MB。

22 I386的保护模式支持分段机制，整个虚拟空间可以划分为16K个段，每个段的大小可变，最大能够达到4GB，每个段可以提供独立的段内保护，支持二级分页机制，每个页面4KB，提供段页式存储管理的硬件支持。同时，在同一个任务内部，还提供4种（0~3）保护特权级，某一级特权i只可以访问所有其他大于等于这一特权级（≥i）的程序段。

23 地址空间 在I386体系结构中，提供段页式存储管理的硬件支持，和内存管理有关的地址空间包括逻辑地址空间、线性地址空间和物理地址空间，在存储过程中，要经过相对独立的两级地址变换。第一级使用分段机制，把包含段地址和段内偏移地址的二维虚拟地址空间转换为一个线性地址空间（也是虚拟地址空间），第二级使用分页机制，把线性地址空间转换为物理地址空间。这种转换关系可以用图3.3来描述。

24 图3.3 地址映射关系示意图

25 虚拟地址空间到线性地址空间的转换关系由段描述符表（简称段表）来描述，段表的每一个数据项记录一个段到线性地址的关系，段表存放在线性地址空间中。线性地址空间到物理空间的转换关系由页表描述，页表存放在物理地址空间中。 每个虚拟地址空间（16K个段）可以分为相等的两个部分，一半称为全局虚拟地址空间，由全局段描述符表（Global Descriptor Label， GDT）映射，另一半称为局部虚拟地址空间，由局部段描述符表（Local Descriptor Label， LDT）映射。

26 系统中所有进程共享一个全局段表（GDT），而每一个进程都有自己的局部段表（LDT）。当进程发生切换时，GDT不变，而LDT更新为正在执行进程的LDT，因此，所有进程共享GDT所映射的物理地址空间，每一个进程都有自己单独的地址空间（由LDT描述）。 线性地址空间划分为大小相等的页，每页为4KB，与之对应的物理地址空间划分为大小相等的页面，页面的大小也是4KB。I386体系结构采用二级分页机制，线性地址到物理地址的映射使用一个二级页表，二级表中的第一级称为页目录，每个页目录项指向一个二级表，这个二级表就是一个页表，每一个表项记录该表对应的表架的基地址，这个基地址和偏移量一起就构成整个物理地址。

27 3.4 Linux存储管理 Linux系统本身采用段页式存储管理，使用最小限度的段机制和三级分页机制。在I386保护模式下，系统可以获得大容量的虚拟存储，并且在各进程之间实现有效的存储共享和保护。 段页设置 Linux系统最低限度地使用I386体系的分段机制，把整个虚拟地址空间直接映射为线性地址空间，一个虚拟空间只包含一个段，段的大小为4GB。也就是说，一个进程最大可以占有4GB的空间。

28 Linux 及以前的版本，在全局段表（GDT）中，每一个进程（每一个虚拟地址空间）有两个静态的表项，其中一项是进程的任务状态段（Task Status Segment，TSS），这项记录着进程切换过程中的CPU现场状态，另外一项是局部段表（LDT），LDT项是这个进程对应的局部段表的入口。而每个进程的局部段表中只有三个表项，一个空表项、一个用户数据段和一个用户代码段，用户数据和代码都从地址0开始，大小为3GB，称为用户空间。所有进程的3GB～4GB线性空间，都由系统共享，存放系统数据段和系统代码段，称为内核空间。

29 Linux系统使用I386提供的四级保护机制中的两级，0级由系统内核使用，而3级由用户程序使用。Linux内核存储在内核空间。用户进程有各自的虚拟地址空间，都使用从0～3GB的线性空间，而内核空间映射到每一个用户线性空间的3GB～4GB的地方，由所有进程共享。 根据硬件提供的保护机制，处于内核空间的内核代码可以访问正在执行进程的用户空间。用户空间的代码只能访问本空间的内容，不能直接访问内核空间的内容，用户进程只能通过中断或者系统调用访问内核空间，这时，触发硬件的特权级转换（由3级转换为0级），操作系统转入内核空间中执行，

30 执行完毕后，依靠硬件设置实现再次切换，重新进入用户空间。用户空间之间除了特定的共享空间之外，不可以相互访问，这就比较方便地实现了存储共享和保护。
整个线性空间通过分页的方式映射到物理空间。每页大小为4KB，因此整个4GB的线性空间可以分为1K（1024）个页（page），Linux系统采用三级分页机制，对页建立三级索引，分别称为页目录（page directory）页中间目录（page middle directory）和页表（page table）。由于I386体系结构的限制，在I386平台上的Linux系统采用两级页索引，页目录和页中间目录合二为一。

31 地址映射 Linux系统的虚拟空间分为连续的段，分别为用户空间和内核空间，直接映射到线性空间中。在地址变换过程中，主要考虑线性空间到物理空间的映射关系。 在I386平台上的Linux系统采用两级页索引，为页目录和页表。线性空间的页和物理空间的基本单位页面（page frame）之间存在对应关系，这种关系用页表（page table）来描述，每个页在页表中占一项，每一项为4字节，要描述整个线性空间，页表要4MB。把所有页表也划分为4KB为单位的页，共有1K个这样的页，这些页的地址采用页目录（page directory）来记录，页目录的每一项描述

32 存放页表的一个页与实际页面的对应关系，每一项也占用4字节。这样，描述整个线性地址空间需要的页目录占用一页。
线性地址由三个部分组成，分别为页目录索引、页表索引和页内偏移地址。第一部分页目录索引描述要访问地址在页目录表中的位置，通过这个索引，就可以得到一个记录页表的内存单元；第二部分页表索引描述待访问地址在页表中的位置，通过查找页表，就得到待访问地址所在的页面；第三个部分页内偏移地址，描述待访问地址相对于页面基地址的偏移量。根据这三部分资料，就可以访问到内存中相应的内容。整个线性地址包括32位，其中页

33 目录索引和页表索引各占10位，寻址范围为1K，正好是页表和页目录表的大小，而页内偏移地址占12位，寻址范围为4K，等于页的大小。这种地址变换可以参看图3.4。

34 图3.4 Linux在I386平台的地址变换

35 从上面的描述可以看到，要访问内存中的某一内容，通过地址变换，首先查找页目录表，接着查找页表，最后才能访问到真正存放的数据，整个过程要三次访问物理内存，因此，记录一个进程中经常访问页的地址的快表（translation lookaside buffer）是必不可少的。地址变换过程中，首先访问快表，如果该页表项存在于快表中，就可以直接得到对应的页面号，如果不在快表中，再去查找页目录表和页表。

36 共享与保护 Linux系统的每一个进程拥有4GB的虚拟空间，这个空间也就是线性空间，在I386系统下，对应为1K个大小为4KB的页。其中0~767个页对应的3GB空间为用户空间。而3GB～4GB的区域映射为系统空间。 实际上，整个物理内存被映射到从3G（0xc ）开始的一段线性空间中，在启动过程中，这个区域的页目录和页表首先建立，也就是说，整个物理内存从启动开始就处于内核态，由系统所控制。所有物理内存可以由内核页目录和内核页表来寻址，这种关系是固定不变的，而且对于每一个虚拟空间都相同，这一方面保证了系统对物理

37 内存的快速访问和有效控制，另一方面也保证了所有进程可以共享系统空间。
进程对系统空间的共享是在严格的限制下进行的，这种限制利用了I386提供的特权级保护机制。进程的虚拟空间包括了系统（内核）空间和用户空间两个部分，它们分别处于不同的特权级。内核空间特权级为0，进程执行这个空间的指令，称为处于内核态（或者系统态）；用户空间的特权级为3，进程执行这个空间的指令，称为处于用户态。用户态和核心态是同一进程的两种不同运行模式，进程在用户态和核心态执行时分别访问位于用户空间和核心空间的堆栈和数据结构。处于内核态的进程可以访问同一进程的用户空间，反之则不可以访问。

38 一个进程可以在这两种不同的特权级之间切换，用户态通过中断或函数调用就可以转入系统态，执行内核空间的指令。而从系统态切换到用户态，则需要一定的硬件支持。
在进程建立之后，首先建立页目录，然后系统根据实际需要，动态地分配一部分物理内存，建立用户页表、页表项以及相应的页目录项，进程在用户空间中将根据这些值来寻址，访问物理内存。在获得一部分内存之后，用户进程即可以开始执行，执行的过程中，当进程访问到还没有映射在内存中的页时，进程发出页面请求，操作系统才根据需要把放在外存中的页的内容传送到内存，同时建立内存页面与进程页的映射关系。

39 每个进程虚拟空间中的0~3GB分别采用不同的映射关系，映射到不同的物理空间，虚拟空间之间是不可以互相访问的，这就起到对进程内的数据和程序保护的作用。
进程之间的共享是必不可少的，如果我们同时开两个vi的编辑窗口，它们都运行同样的程序代码，分别属于两个不同的进程，对应于不同的编辑文本（操作数据），如果分别给两个进程开两块存储空间，存放同样的程序代码，显然是对有限内存资源的极大浪费，不同的进程共享使用相同的内存代码是最好的解决办法。 Linux进程间的共享是通过把不同虚拟空间中不同的页映射到物理空间中同一页面来实现的，参看图3.5。

40 图3.5 Linux页面共享结构示意图

41 在图3.5中，两个进程分别拥有自己的页目录和页表，而页表中，对应于不同进程的页号指向内存中同样的页面，这样，同一个物理页面映射为不同虚拟空间中不同的页，两个进程都可以根据自己的地址映射关系访问同一块内存，实现了内存的共享。这样的共享方式实现简单，易于理解，也不占额外的物理内存，但是，一旦共享页面的状态或者内容发生变化，所有共享该页面的进程的页表都要修改，这就需要多次访问内存，影响系统的效率。 Linux系统还采用保护技术，实现进程用户空间内部不同存储段之间的保护。

42 在系统运行期间，进程之间存储共享可以节约大量的存储空间，同时可以提高系统的整体效率，但是，共享必须在保证安全的前提下进行，这就需要必要的保护措施。虚拟空间划分为系统空间和用户空间，按照一定的映射规则与物理空间建立联系，系统多个进程之间共享整个系统空间，多个用户进程也可以共享一段物理内存。在Linux系统中，用户空间和系统空间的共享、不同进程用户空间之间的共享以及进程用户空间的虚拟存储段，都可以得到有效的保护。

43 分配与回收 系统开始运行时，整个物理内存都映射到内核空间，由内核根据需要进行物理内存页面的分配或释放。用户进程建立时，分配相应的内存页面并建立用户进程虚拟空间与所分配页面的映射关系，在进程执行过程中，还要针对实际情况，动态地分配和回收页面，进程进入僵死状态后，除了进程控制块（PCB）所占据的页面之外的所有内存都释放，最后PCB释放，进程终止。因此，物理页面的分配和释放机制及其相关数据结构是操作系统虚拟存储管理的关键部分。

44 在执行过程中，每一个进程要记录自己使用的所有页面以及它们的映射关系（页表和页目录），这些信息以指针的形式记录在进程的PCB中。同时，系统对所有内存的使用情况也要做精确的记录，这是内存进一步分配和回收的依据。 1. 空闲页面表示 Linux主要采用Buddy（伙伴）算法有效分配和释放物理页面。系统的页面分配和回收都是以2的k次幂（0≤k≤NR-MEM-LISTS-1，整数）个页面为单位，称为页块，也就是说以1页、2页，直到2NR-MEM-LISTS-1页大小的页块为单位连续分配。具体来讲，对于I386系统，在2.2.16版本中，NR-

45 MEM-LISTS默认值等于10，在文件mm/page-alloc
MEM-LISTS默认值等于10，在文件mm/page-alloc.c中定义，每个页面大小固定（为4KB），所以，内存分配的最小单位是4KB，最大为2MB（29×4KB）。 Linux的空闲物理页面分配采用链表和位图结合的记录方法。系统定义了一个称为free-area 的数组，数组的大小为NR-MEM-LISTS。 free-area数组的每一个元素都包含一个空闲页块双向链表的头指针和一个位图map，描述某一种页块的空闲情况。每一个数组元素对应的链表，记录2k大小页块的信息，k为数组元素的下标。具体来讲，第一个元素（下标为0）描述单个空闲页的信息，第二个元素（下标为1）则描述以2个页为一个块的

46 空闲页块，第三个元素（下标为2）描述以4个页为一个块的页块信息。free-area数组的元素记录双向链表的头指针，而双向链表的每个节点包含空闲页块的起始物理页帧编号。free-area数组的元素中包含的位图map记录这种页块的具体分配使用情况，位图中的某一位置1，则表示对应的页块被使用。这样，所有单个空闲页面组成的双向链表挂在free-area数组的0号元素之后，所有2k页面大小的空闲块组成的双向链表挂在free-area数组的k号元素之后，同时，每一个空闲块的使用情况可以通过对应的位图描述。这种关系示意性地描述在图3.6的左半部分。

47 图3.6 Linux系统空闲内存示意图

48 在图3.6中，如果物理内存中某一部分的空闲情况如图右半部分所示，free-area数组的0号元素描述大小为1页的空闲页块，那么第8号页面就是free-area数组的0号元素所对应的双向链表的头接点。同理，第5号和第0号页面分别是free-area数组的1号元素和2号元素所对应的双向链表的头接点。free-area数组的k号元素所对应的第N位为1，则表明该元素对应的链表中第N个页块是空闲的，这个页块的大小就是2k个页面。从图中也可以看到，free-area数组的各元素所记录的页块大小各不相同，从小到大依次是两倍的关系，同时对应用来记录页块分配情况的位图大小也各不相同，free-area数组元素号越大，页块越大，页块的数目就越小，而相应的位图也越小。

49 2. 页面分配与回收 Linux采用Buddy算法来分配和回收物理页面，每次处理都是以2k（0≤k≤NR-MEM-LISTS-1，整数）个页面为单位。分配页面采用最先适应算法，当要分配一块内存时，首先确定需要内存的大小，如果需要的内存在2k到2k+1（0≤k≤NR-MEM-LISTS-1，整数）个页面大小之间时，系统要为它分配的页面就是2k+1个，系统在free-area数组中搜索从第k+1个元素对应的双向链表中开始搜索，找不到时再搜索第k+2个元素对应的双向链表，直到找到大于或等于要求尺寸的最小块的信息。如果找到的空闲块正好是2k+1个页面时，直接从free-area删除该块，返回首地址，如果找到的空闲块大于所

50 需要的页面，则把空闲块一分为二，前半部分插入free-area数组前一个元素所指的链表中，取后半部分，如果后半部分还大，继续对半划分，直到分得的后半部分等于需要的页面为止。页面分配之后，对应的各位图的位也要相应设置。Linux采用的这种分配算法称为最先适应算法。 随着页块的不断分配，系统的内存逐步被划分为一个个小的块，这些块有些正在使用，而另外一部分则是空闲块，但是连续可用的块却越来越少，这种情况称为内存的碎片化。因此，物理页块使用完之后要及时回收，而在回收空闲块的同时，还应当将小的空闲页块重新组合成大的页块。Linux系统回收空闲块时，根据位图表对应的值判断回收块相邻

51 位置的页块是否空闲，如果和回收的页块大小相等的相邻页块刚好是空闲的，则可以把这两个页块组合成一个大的页块，这一过程一直继续，直到这个大页块的相邻块不等于这个块或者正在使用为止，这时还要修改对应的位图值，并把这个大的页块插入到free-area数组对应元素所指的链表中。 Linux采用的Buddy算法可以实现内存的快速分配和回收，同时也能够有效地处理内存碎片化问题，总体效率比较高。但是，它对内存的快速分配是建立在内存需求量是2的整数幂个页面的基础上的，如果很不巧，我们需要的内存量是33KB，根据Buddy算法，在I386系统中，实际分配的是16个连续的页面（64KB），大约50%的内存就浪费掉了。

52 在整个分配过程中，这样隐性的内存浪费量是相当惊人的。因此，可以说，这种算法内存分配和回收的高效率是通过牺牲系统内存资源的利用率换来的。

53 3.5小结 Linux操作系统可以统一管理内存和外存，实现逻辑上的大容量虚拟存储空间。利用这样的技术，系统有限的物理存储区域中可以存放更多的进程，这些进程轮流使用处理机，实现系统整体效率的大幅度提高。 进程的执行过程中，某一个特定的时间段中，CPU总是集中地访问程序或数据的某一个部分，这种规律称为局部性原理，这个原理是虚拟存储实现的依据。根据这一原理，把进程的虚拟空间划分为一个个小的部分，首先只把系统所必需的部分数据装入内存，其余部分就放在外存中，开始运行之后，再根据进程执行情况把所需要的其他部分换入内存，

54 同时把不再需要的部分从内存中换到硬盘或者清除掉。与这样的方式相配合，物理内存也划分为对应的小部分。
不同的虚拟空间和物理空间划分方法得到不同的存储管理方法，常用的能够实现虚拟存储的划分方法有页式、段式和段页式。页式管理把虚拟空间和物理空间划分为大小相等的部分，分别称为页和页面，以页和页面为单位进行存储管理；段式管理把虚拟空间按照程序固有的逻辑关系划分为大小不等的段，每一个段对应程序的一个逻辑单位，以段为单位进行存储管理；段页式管理对虚拟空间先分段，再分页，最小单位是页，同时具有段式和页式管理的优点，但是整个管理的系统开销增大，而且还需要有硬件的支持。

55 以I386为代表的向下兼容的一系列芯片在保护模式下，提供段页式存储管理的硬件支持。一个虚拟空间可以划分为16个段，最大的段可以达到4GB，同时支持分页功能，页面大小为4K，提供两级页表。同时提供0~3四个特权级，对不同特权级运行的进程实现保护。 Linux最低限度地使用I386系统的分段机制，使用0（系统级）和3（用户级）两个特权级。每个虚拟空间是线性的，大小为4GB，分成用户空间0~3GB和系统空间3GB~4GB两个部分。所有系统空间都映射到同一段物理内存，实现系统段共享，操作系统位于系统空间，以0级特权运行，用户进程位于用户空间，以3级特权运行，使用页目录、页表这两级分页机制。

56 利用I386提供的硬件机制，Linux系统可以方便地实现系统空间和用户空间之间、不同进程用户空间之间以及同一进程用户空间不同虚拟存储段之间的共享和保护。
Linux系统的空闲物理内存的管理采取Buddy算法，管理内存的最小单位是2的整数次幂个页面大小，利用位图和链表相结合的办法记录空闲内存信息，内存分配采用最先适应算法，可以快速分配和回收空闲内存页面，同时也能够有效处理内存碎片化问题。 以此为基础，下一章我们进一步学习虚拟存储管理中内存外存之间数据传递——交换调度的基本算法与过程。

57 习题 3-1 计算机系统中，虚拟地址空间和物理地址空间分 别对应着什么？ 3-2 分页和分段式内存管理有什么区别？
3-1 计算机系统中，虚拟地址空间和物理地址空间分 别对应着什么？ 3-2 分页和分段式内存管理有什么区别？ 3-3 为什么提出段页式管理?它与页式、段式管理有何区别？ 3-4 段页式管理的主要缺点是什么？有什么改进办法？ 3-5 Linux系统中如何利用I386的段页机制？ 3-6 Linux中，系统空间和用户空间之间、不同进程用户空间之间以及同一进程用户空间不同虚拟存储段之间如何实现共享和保护？各需要什么硬件支持？

58 3-7 Linux系统的内存分配与回收采用什么算法？有什么优点？有什么缺点？提出你的改进思路。
3-8 考虑如下的程序段： #include <stdlib.h> #include <stdio.h> int main(void) { printf("AAA"); sleep(6); return 1; }

59 在Linux系统中，运行这个程序所建立的进程的虚拟空间为多大？其中系统空间、用户空间各多大？进程实际占用的物理内存是多少？分别用来存储什么内容？运行这个程序，利用系统命令查看实际使用的内存量。