Chapter 1
Hardware Basic(硬件基础知识)
操作系统必须与硬件系统紧密配合作为其基础。操作系统需要使用一些只能由硬件提供的功能。为了充分理解Linux，你需要了解底层硬件的基本知识。本章是现代的PC硬件进行了。
1975年1月“Popular Electronics印在杂志封面上Altair 一场革命开始了8080的照片。
Altair 8080，跟随早期的Star Trek epsode只需要命名$397，可由个人电子爱好者组装。它拥有Intel 8080处理器和256字节内存，但没有屏幕和键盘。以今天的标准来衡量，太简单了。它的发明者，Ed Roberts，制造名词personal computer命名他的发明，但现在，PC这个名词已经用来命名几乎所有你可以自己操作的计算机，而不需要帮助。有了这个定义，甚至有些非常强大Alpha AXP系统也是PC。
爱好者们看到了Altair的潜力，开始为它写软件，制造硬件。对于这些早期先驱来说，它代表着自由：逃离被神职人员控制和运行的大型批处理主机系统的自由。你可以在自己家里甚至厨桌上有一台电脑，这让学院的退学生着迷了一整夜。与此同时，大量的硬件在一定程度上是不同的，而软件专家愿意为这些新机器写软件。讽刺的是，IBM在1981年发布了IBM PC并在1982年早期定义了现代供应PC的模型。它拥有Intel 8088处理器，64K可扩展到256K），两个软驱和一个80x25的彩色图卡(CGA)，用今天的标准来衡量，它的功能不是很强大，但卖得很好。1983年，随后推出IBM PC-XT，拥有豪华的10M硬盘。很快就会有大量的公司Compaq开始制造IBM PC的复制品，PC结构已成为事实的标准。这一事实的标准使大量硬件公司能够在这个不断增长的市场上竞争，反过来又能够遏制价格，让用户满意。现代PC承袭了早期PC许多系统特征。甚至基于最强大的Intel Pentium Pro系统也可以运行Intel 8086寻址模式。当Linus Torvalds后来开始开发Linux当时他选择了最常见、最合理的硬件平台：一个Intel 80386 PC。
从PC从外面看，最明显的部件是底盘、键盘、鼠标和显示器。底盘前面有一些按钮，一个小屏幕显示一些数字和一个软驱动器。今天的大多数系统都有另一个CD-ROM期，驱动器。如果您需要保护您的数据，则将有备份磁带机。所有这些设备都被视为外设。
虽然CPU管理整个系统，但它不是唯一的智能设备。所有外部控制器，如IDE控制器，也有一定程度的智能。PC内部（图1.1)你可以看到主板，包括CPU或者微处理器，内存和一些ISA或PCI外部控制卡的槽位。其中一些控制器，如IDE磁盘控制器可能内置在系统主板上。
CPU
CPU，或者微处理器是所有计算机系统的心脏。微处理器进行数学操作，逻辑操作，从内存中读取指令并执行指令，然后控制数据流。在计算机开发的早期阶段，微处理器的各种功能模块由相互分离(而且尺寸非常大)的单元组成。这也是名词中央处理单位的起源。现代微处理器将这些功能模块集中在一个常小的硅晶片制成的集成电路上。这本书，名词CPU、交替使用微处理器和处理器。
由1和0组成的微处理器处理二进制数据。这些1和0对应电气开关的开或关。就像42代表4个10和2个单元，二进制数字由一系列代表2的幂数组成。在这里，幂数意味着一个数字乘以自己的次数。10 一次是10，10是10x10，10的3次幂是10x10x依此类推。二进制0001是十进制1，二进制数0010是十进制2，二进制0011是十进制3，二进制0100是十进制4，等等。因此，十进制42是二进制101010或(2) 8 32或21 23 25）。除了用二进制表示数字外，计算机程序还经常使用另一个基数，16进制。在这种进制中，每个数字表示16米。由于十进制数字仅从0到9，在十六进制中分别使用10到15个字母A，B，C，D，E，F表示。比如16进制的E是14，16进制的E是14，16进制的E是2A是十进制42(2) 10）。使用C语言表达法(本书一直使用)，前缀为00x十六进制2A写做0x2A。
微处理器可以执行算术操作，如算术操作，也可以执行逻辑操作，如X是否大于Y”。
外部时钟控制处理器的执行。此时钟，即系统时钟，对处理器产生稳定的时钟脉冲，处理器在每个时钟脉冲中执行一些工作。例如，处理器可以在每个时钟脉冲中执行指令。系统时钟的频率描述了处理器的速度。一个100Mhz处理器每秒接收1万次脉冲。描述时钟频率CPU由于是一种误解，因为每个时钟脉冲中不同处理器的工作量不同。尽管如此，如果所有条件相同，时钟频率越快，处理器的能力就越强。处理器执行的指令很简单，比如在寄存器Y中读取内存位置X的内容。存储器是存储数据并操作微处理器的内部存储空间。执行操作可能会使处理器停止当前操作，并将指令转移到内存中的其他地方。正是这些小指令聚集在一起，赋予现代微处理器几乎无限的能力，因为它每秒可以执行数百万甚至数十亿的指令。
执行指令时，指令必须从内存中提取，指令本身也可以引用内存中的数据，必要时必须提取到内存中并保存到内存中。
微处理器内寄存器的大小、数量和类型完全取决于其类型。一个Intel 80486处理器和一个Alpha AXP处理器的寄存器组完全不同。另外，Intel是32位宽而Alpha AXP是64位宽。然而，一般来说，所有特定的处理器都有一些通用目的寄存器和少量特殊的寄存器。大多数处理器都有以下特殊用途的专用寄存器：
Program Counter（PC）程序计数器
该寄存器记录了下一个要执行的指令的地址。PC每次取指令时，内容都会自动增加。
Stack Pointer（SP）堆栈指针
用于临时存储数据的大容量外读写处理器必须能够随机存取内存（RAM）。堆栈是存储和恢复外部内存中临时数据的一种方法。通常，处理器提供特殊指令将数据压入堆栈，并在将来取出。堆栈使用LIFO(后进先出)。换句话说，如果你压入两个值x和y去堆栈，然后从堆栈里弹出一个值，然后你就会得到y的值。
有的处理器堆栈向内存顶部增长，有的则向内存底部增长。有两种方法可以支持一些处理器，例如：ARM。
Processor Status（PS）
指令可能会产生结果。X寄存器的内容是否大于Y寄存器的内容？PS寄存器保留这些结果和其他处理器当前状态的信息。大多数处理器至少有两种模式：kernel(核心态)和user(用户态)，PS寄存器将记录能够确定当前模式的信息。
Memory(内存)
由不同速度和容量的内存组成，所有系统都有分级的内存结构。
最快的内存是高速缓存存储器，就像它的名字暗示的那样——用于临时存储或缓存主内存的内容。这种内存非常快但昂贵，所以大多数处理器芯片都有少量的高速缓冲存储器，而大多数高速缓冲存储器都放在系统的主板上。一些处理器同时使用缓存内存来缓存指令和数据，而另一些处理器有两个缓存内存——一个用于指令，另一个用于数据。Alpha AXP处理器有两个内置内存高速缓存器：一个用于数据（D-Cache），另一个用于指令（I-Cache）。其外部高速缓冲存储器(或B-Cache）两者混在一起。
最后一种内存是主内存。与外部高速缓存存储器相比，速度非常慢CPU内置高速缓存储器，主内存只是在爬行。
高速缓存器和主内存必须保持同步（一致）。换句话说，如果主内存中的一个单词存储在高速缓存器的一个或多个位置，系统必须确保高速缓存器的内容与主内存相同。高速缓冲器的部分工作由硬件完成，另一部分由操作系统完成。硬件和软件也必须密切配合其他系统的主要任务。
Buses（总线）
系统板的各个部件由称为总线的连接系统连接在一起。系统总线分为地址总线、数据总线和控制总线三个逻辑功能。地址总线指定了数据传输的内存位置地址)，数据总线保存传输数据。数据总线是双向的，允许CPU读，也许CPU写。控制总线包括在系统中发送时钟和控制信号的各种信号线。总线类型有很多种，ISA和PCI总线是系统连接外设的常用方式。
Controllers and Peripherals (控制器和外设)
外设是指由系统板或系统板插卡上的控制芯片控制的图形卡或磁盘。IDE控制芯片控制IDE磁盘，而SCSI控制芯片控制SCSI磁盘。这些控制器通过不同的总线连接到CPU并相互连接。目前制造的大多数系统都是使用的PCI或ISA总线连接系统的主要部件。控制器本身也是大象CPU它们可以被视为相同的处理器CPU智能助手，CPU拥有系统的最高控制权。
所有的控制器都不同，但它们通常用于控制寄存器。CPU运行在上面的软件必须能够读写这些控制寄存器。一个寄存器可能包含描述错误的状态码，另一个寄存器可能用于控制用途，改变控制器的模式。总线上的每个控制器都可以单独使用CPU搜索网站，这样软件设备驱动程序就可以读写它的寄存器来控制它。IDE电缆是一个很好的例子，它给了你分别访问总线上每个驱动器的能力。另一个好例子是PCI允许每个设备(如图形卡)独立访问总线。
Address Spaces(搜索空间)
连接CPU与主内存连接的系统总线CPU和系统硬件外设的总线是分离的。硬件外设所拥有的内存空间称为I/O空间。I/O空间本身可以进一步划分，但我们现在不讨论了。CPU可访问系统内存空间和I/O空间，控制器只能通过CPU间接访问系统内存。从设备的角度来看，如软驱动控制器，它只能看到控制寄存器的地址空间（ISA），而非系统内存。一个CPU访问内存和使用不同的指令I/O空间。例如，可能有一个指令是从I/O地址0x3f读一个字节到X寄存器。这也是CPU通过读写统硬件外设处于I/O地址空间的寄存器从而控制外设的方法。在地址空间中，普通外设（如IDE控制器，串行端口，软驱控制器等等）的寄存器在PC外设的多年发展中已经成了定例。I/O空间的地址0x3f0正是串行口（COM1）的控制寄存器的地址。
有时控制器需要直接从系统内存读取大量内存，或直接写大量数据到系统内存中去。比如将用户数据写到硬盘上去。在这种情况下，使用直接内存存取（DMA）控制器，允许硬件设备直接存取系统内存，当然，这种存取必须在CPU的严格控制和监管下进行。
Timer(时钟)
所有操作系统需要知道时间，现代PC包括一个特殊的外设，叫做实时时钟（RTC）。它提供了两样东西：可靠的日期和精确的时间间隔。RTC有自己的电池，所以即使PC没有加电，它仍在运行。这也是为什么PC总是“知道”正确的日期和时间。时间间隔计时允许操作系统精确地调度基本工作。
Chapter 2
Software Basic(软件基础)
程序是用于执行特定任务的计算机指令组合。程序可以用汇编语言，一种非常低级的计算机语言来编写，也可以使用和机器无关的高级语言，比如C语言编写。操作系统是一个特殊的程序，允许用户通过它运行应用程序，比如电子表和文字处理等等。本章介绍了基本的编程原理，并简介操作系统的目的和功能。
2.1 Computer Languages(计算机语言)
2.1.1.汇编语言
CPU从内存中读取和执行的指令对于人类来讲无法理解。它们是机器代码，精确的告诉计算机要做什么。比如十六进制数0x89E5，是Intel 80486的指令，将寄存器ESP的内容拷贝到寄存器EBP中。早期计算机中最初的软件工具之一是汇编程序，它读入人类可以阅读的源文件，将其装配成机器代码。汇编语言明确地处理对寄存器和对数据的操作，而这种操作对于特定的微处理器而言是特殊的。Intel X86微处理器的汇编语言和Alpha AXP微处理器的汇编语言完全不同。以下Alpha AXP汇编代码演示了程序可以执行的操作类型：
Ldr r16, (r15) ; 第一行
Ldr r17, 4(r15) ; 第二行
Beq r16,r17,100; 第三行
Str r17, (r15); 第四行
100: ; 第五行
第一条语句（第一行）将寄存器15指定的地址中的内容加载到寄存器16中。第二条指令将紧接着的内存中的内容加载到寄存器17中。第三行比较寄存器16和寄存器17，如果相等，分支到标号100，否则，继续执行第四行，将寄存器17的内容存到内存中。如果内存中的数据相同，就不必存储数据。编写汇编级的程序需要技巧而且十分冗长，容易出错。Linux系统的核心很少的一部分是用汇编语言编写，而这些部分之所以使用汇编语言只是为了提高效率，并且和具体的微处理器相关。
2.1.2 The C Programming Language and Compiler (C语言和编译器)
使用汇编语言编写大型程序十分困难，消耗时间，容易出错而且生成的程序不能移植，只能束缚在特定的处理器家族。更好的选择是使用和机器无关的语言，例如C。C允许你用逻辑算法描述程序和要处理的数据。被称为编译程序（compiler）的特殊程序读入C程序，并将它转换为汇编语言，进而产生机器相关的代码。好的编译器生成的汇编指令可以和好的汇编程序员编写的程序效率接近。大部分Linux核心是用C语言编写的。以下的C片断：
if (x != y)
x = y;
执行了和前面示例中汇编代码完全一样的操作。如果变量x的内容和变量y的内容不一样，变量y的内容被拷贝到变量x。C代码用例程（routine）进行组合，每一个例程执行一项任务。例程可以返回C所支持的任意的数值或数据类型。大型程序比如Linux核心分别由许多的C语言模块组成，每一个模块有自己的例程和数据结构。这些C源代码模块共同构成了逻辑功能比如文件系统的处理代码。
C支持多种类型的变量。一个变量是内存中的特定位置，可用符号名引用。上述的C片断中，x和y引用了内存中的位置。程序员不需要关心变量在内存中的具体位置，这是连接程序（下述）必须处理的。一些变量包含不同的数据例如整数、浮点数等和另一些则包含指针。
指针是包含其它数据在内存中的地址的变量。假设一个变量x，位于内存地址0x80010000， 你可能有一个指针px，指向x。 Px可能位于地址0x80010030。Px的值则是变量x的地址，0x80010000。
C允许你将相关的变量集合成为结构。例如：
Struct {
Int I;
Char b;
} my_struct;
是一个叫做my_struct的数据结构，包括两个元素：一个整数（32位）I和一个字符（8位数据）b。
2.1.3 Linkers（连接程序）
连接程序将几个目标模块和库文件连接在一起成为一个单独的完整程序。目标模块是汇编程序或编译程序的机器码输出，它包括机器码、数据和供连接程序使用的连接信息。比如：一个目标模块可能包括程序的所有数据库功能，而另一个目标模块则包括处理命令行参数的函数。连接程序确定目标模块之间的引用关系，即确定一个模块所引用的例程和数据在另一个模块中的实际位置。Linux核心是由多个目标模块连接而成的独立的大程序。
2.2 What is an Operating System（什么是操作系统？）
没有软件，计算机只是一堆发热的电子元件。如果说硬件是计算机的心脏，则软件就是它的灵魂。操作系统是允许用户运行应用程序的一组系统程序。操作系统将系统的硬件抽象，呈现在用户和应用程序之前的是一个虚拟的机器。是软件造就了计算机系统的特点。大多数PC可以运行一到多个操作系统，而每一个操作系统从外观和感觉上都大不相同。Linux由不同功能的部分构成，这些部分总体组合构成了Linux操作系统。Linux最明显的部分就是Kernel自身，但是如果没有shell或libraries一样没有用处。
为了了解什么是操作系统，看一看在你输入最简单的命令时发生了什么：
$ls
Mail c images perl
Docs tcl
$
这里的$是登录的shell输出的提示符（此例是bash）：表示shell在等候你（用户）输入命令。输入ls引发键盘驱动程序识别输入的字符，键盘驱动程序将识别的字符传递给shell去处理。shell先查找同名的可执行映象，它找到了/bin/ls, 然后调用核心服务将ls执行程序加载到虚拟内存中并开始执行。ls执行程序通过执行核心的文件子系统的系统调用查找文件。文件系统可能使用缓存的文件系统信息或通过磁盘设备驱动程序从磁盘上读取文件信息,也可能是通过网络设备驱动程序同远程主机交换信息而读取本系统所访问的远程文件的详细信息（文件系统可以通过NFS网络文件系统远程安装）。不管文件信息是如何得到的，ls都将信息输出，通过显示驱动程序显示在屏幕上。
以上的过程看起来相当复杂，但是它说明了即使是最简单的命令也是操作系统各个功能模块之间共同协作的结果，只有这样才能提供给你（用户）一个完整的系统视图。
2.2.1 Memory management（内存管理）
如果拥有无限的资源，例如内存，那么操作系统所必须做的很多事情可能都是多余的。所有操作系统的一个基本技巧就是让少量的物理内存工作起来好像有相当多的内存。这种表面看起来的大内存叫做虚拟内存，就是当软件运行的时候让它相信它拥有很多内存。系统将内存分为容易处理的页，在系统运行时将这些页交换到硬盘上。而应用软件并不知道，因为操作系统还使用了另一项技术：多进程。
2.2.2 Processes (进程)
进程可以看作一个在执行的程序，每一个进程都是正在运行的特定的程序的独立实体。如果你观察一下你的Linux系统，你会发现有很多进程在运行。例如：在我的系统上输入ps 显示了以下进程：
$ ps
PID TTY STAT TIME COMMAND
158 pRe 1 0:00 -bash
174 pRe 1 0:00 sh /usr/X11R6/bin/startx
175 pRe 1 0:00 xinit /usr/X11R6/lib/X11/xinit/xinitrc --
178 pRe 1 N 0:00 bowman
182 pRe 1 N 0:01 rxvt -geometry 120x35 -fg white -bg black
184 pRe 1 < 0:00 xclock -bg grey -geometry -1500-1500 -padding 0
185 pRe 1 < 0:00 xload -bg grey -geometry -0-0 -label xload
187 pp6 1 9:26 /bin/bash
202 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black
203 ppc 2 0:00 /bin/bash
1796 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black
1797 v06 1 0:00 /bin/bash
3056 pp6 3 < 0:02 emacs intro/introduction.tex
3270 pp6 3 0:00 ps
$
如果我的系统拥有多个CPU那么每个进程可能（至少在理论上如此）都在不同的CPU上运行。不幸的是，只有一个，所以操作系统又使用技巧，在短时间内依次运行每一个进程。这个时间段叫做时间片。这种技巧叫做多进程或调度，它欺骗了每一个进程，好像它们是唯一的进程。进程相互之间受到保护，所以如果一个进程崩溃或不能工作，不会影响其他进程。操作系统通过给每一个进程一个独立的地址空间来实现保护，进程只能访问它自己的地址空间。
2.2.3 Device Drivers（设备驱动程序）
设备驱动程序组成了Linux核心的主要部分。象操作系统的其他部分一样，它们在一个高优先级的环境下工作，如果发生错误，可能会引发严重问题。设备驱动程序控制了操作系统和它控制的硬件设备之间的交互。比如：文件系统向IDE磁盘写数据块是使用通用块设备接口。驱动程序控制细节，并处理和设备相关的部分。设备驱动程序和它驱动的具体的控制器芯片相关，所以，如果你的系统有一个NCR810的SCSI控制器，那么你需要NCR810的驱动程序。
2.2.4 The Filesystems（文件系统）
象Unix一样，在Linux里，系统对独立的文件系统不是用设备标示符来存取（比如驱动器编号或驱动器名称），而是连接成为一个树型结构。Linux在安装新的文件系统时，把它安装到指定的安装目录，比如/mnt/cdrom，从而合并到这个单一的文件系统树上。Linux的一个重要特征是它支持多种不同的文件系统。这使它非常灵活而且可以和其他操作系统良好共存。Linux最常用的文件系统是EXT2，大多数Linux发布版都支持。
文件系统将存放在系统硬盘上的文件和目录用可以理解的统一的形式提供给用户，让用户不必考虑文件系统的类型或底层物理设备的特性。Linux透明的支持多种文件系统（如MS-DOS和EXT2），将所有安装的文件和文件系统集合成为一个虚拟的文件系统。所以，用户和进程通常不需要确切知道所使用的文件所在的文件系统的类型，用就是了。
块设备驱动程序掩盖了物理块设备类型的区别（如IDE和SCSI）。对于文件系统来讲，物理设备就是线性的数据块的集合。不同设备的块大小可能不同，如软驱一般是512字节，而IDE设备通常是1024字节，同样，对于系统的用户，这些区别又被掩盖。EXT2文件系统不管它用什么设备，看起来都是一样的。
2.3 Kernet Data Structures（核心数据结构）
操作系统必须纪录关于系统当前状态的许多信息。如果系统中发生了事情，这些数据结构就必须相应改变以反映当前的实际情况。例如：用户登录到系统中的时候，需要创建一个新的进程。核心必须相应地创建表示此新进程的数据结构，并和表示系统中其他进程的数据结构联系在一起。
这样的数据结构多数在物理内存中，而且只能由核心和它的子系统访问。数据结构包括数据和指针（其他数据结构或例程的地址）。乍一看，Linux核心所用的数据结构可能非常混乱。其实，每一个数据结构都有其目的，虽然有些数据结构在多个的子系统中都会用到，但是实际上它们比第一次看到时的感觉要简单的多。
理解Linux核心的关键在于理解它的数据结构和核心处理这些数据结构所用到的大量的函数。本书以数据结构为基础描述Linux核心。论及每一个核心子系统的算法，处理的方式和它们对核心数据结构的使用。
2.3.1 Linked Lists（连接表）
Linux使用一种软件工程技术将它的数据结构连接在一起。多数情况下它使用链表数据结构。如果每一个数据结构描述一个物体或者发生的事件的单一的实例，比如一个进程或一个网络设备，核心必须能够找出所有的实例。在链表中，根指针包括第一个数据结构或单元的地址，列表中的每一个数据结构包含指向列表下一个元素的指针。最后元素的下一个指针可能使0或NULL，表示这是列表的结尾。在双向链表结构中，每一个元素不仅包括列表中下一个元素的指针，还包括列表中前一个元素的指针。使用双向链表可以比较容易的在列表中间增加或删除元素，但是这需要更多的内存存取。这是典型的操作系统的两难情况：内存存取数还是CPU的周期数。
2.3.2 Hash Tables
链接表是常用的数据结构，但是游历链接表的效率可能并不高。如果你要寻找指定的元素， 可能必须查找完整个表才能找到。Linux使用另一种技术：Hashing 来解决这种局限。Hash table是指针的数组或者说向量表。数组或向量表是在内存中依次存放的对象。书架可以说是书的数组。数组用索引来访问，索引是数组中的偏移量。再来看书架的例子，你可以使用在书架上的位置来描述每一本书：比如第5本书。
Hash table是一个指向数据结构的指针的数组，它的索引来源于数据结构中的信息。如果你用一个数据结构来描述一个村庄的人口，你可以用年龄作为索引。要找出一个指定的人的数据，你可以用他的年龄作为索引在人口散列表中查找，通过指针找到包括详细信息的数据结构。不幸的是，一个村庄中可能很多人年龄相同，所以散列表的指针指向另一个链表数据结构，每一个元素描述同龄人。即使这样，查找这些较小的链表仍然比查找所有的数据结构要快。
Hash table可用于加速常用的数据结构的访问，在Linux里常用hash table来实现缓冲。缓冲是需要快速存取的信息，是全部可用信息的一个子集。数据结构被放在缓冲区并保留在那里，因为核心经常访问这些结构。使用缓冲区也有副作用，因为使用起来比简单链表或者散列表更加复杂。如果数据结构可以在缓冲区找到（这叫做缓冲命中），那么一切很完美。但是如果数据结构不在缓冲区中，那么必须查找所用的相关的数据结构，如果找到，那么就加到缓冲区中。增加新的数据结构到缓冲区中可能需要废弃一个旧的缓冲入口。Linux必须决定废弃那一个数据结构，风险在于废弃的可能使Linux下一个要访问的数据结构。
2.3.3 Abstract Interfaces（抽象接口）
Linux核心经常将它的接口抽象化。接口是以特定方式工作的一系列例程和数据结构。比如：所有的网络设备驱动程序都必须提供特定的例程来处理特定的数据结构。用抽象接口的方式可以用通用的代码层来使用底层特殊代码提供的服务（接口）。例如网络层是通用的，而它由底层符合标准接口的同设备相关的代码提供支持。
通常这些底层在启动时向高一层登记。这个登记过程常通过在链接表中增加一个数据结构来实现。例如，每一个连结到核心的文件系统在核心启动时进行登记（或者如果你使用模块，在文件系统第一次使用时向核心登记）。你可以查看文件/proc/filesystems来检查那些文件系统进行了登记。登记所用的数据结构通常包括指向函数的指针。这是执行特定任务的软件函数的地址。再一次用文件系统登记的例子，每一个文件系统登记时传递给Linux核心的数据结构都包括一个和具体文件系统相关的例程地址，在安装文件系统时必须调用。
Chapter 3
Memory Management （内存管理）
内存管理子系统是操作系统的重要部分。从计算机发展早期开始，就存在对于大于系统中物理能力的内存需要。为了克服这种限制，开发了许多种策略，其中最成功的就是虚拟内存。虚拟内存通过在竞争进程之间共享内存的方式使系统显得拥有比实际更多的内存。
虚拟内存不仅仅让你的计算机内存显得更多，内存管理子系统还提供：
Large Address Spaces（巨大的地址空间）操作系统使系统显得拥有比实际更大量的内存。虚拟内存可以比系统中的物理内存大许多倍。
Protection（保护）系统中的每一个进程都有自己的虚拟地址空间。这些虚拟的地址空间是相互完全分离的，所以运行一个应用程序的进程不会影响另外的进程。另外，硬件的虚拟内存机制允许对内存区写保护。这可以防止代码和数据被恶意的程序覆盖。
Memory Mapping（内存映射）内存映射用来将映像和数据映射到进程的地址空间。用内存映射，文件的内容被直接连结到进程的虚拟地址空间。
Fair Physics Memory Allocation（公平分配物理内存）内存管理子系统允许系统中每一个运行中的进程公平地共享系统的物理内存
Shared Virtual Memory（共享虚拟内存）虽然虚拟内存允许进程拥有分离（虚拟）的地址空间，有时你也需要进程之间共享内存。例如，系统中可能有多个进程运行命令解释程序bash。虽然可以在每一个进程的虚拟地址空间都拥有一份bash的拷贝，更好的是在物理内存中只拥有一份拷贝，所有运行bash的进程共享代码。动态连接库是多个进程共享执行代码的另一个常见例子。共享内存也可以用于进程间通讯(IPC)机制，两个或多个进程可以通过共同拥有的内存交换信息。Linux系统支持系统V的共享内存IPC机制。
3.1 An Abstract Model of Virtual Memory（虚拟内存的抽象模型）
在考虑Linux支持虚拟内存的方法之前，最好先考虑一个抽象的模型，以免被太多的细节搞乱。
在进程执行程序的时候，它从内存中读取指令并进行解码。解码指令也许需要读取或者存储内存特定位置的内容，然后进程执行指令并转移到程序中的下一条指令。进程不管是读取指令还是存取数据都要访问内存。
在一个虚拟内存系统中，所有的地址都是虚拟地址而非物理地址。处理器通过操作系统保存的一组信息将虚拟地址转换为物理地址。
为了让这种转换更简单，将虚拟内存和物理内存分为适当大小的块，叫做页（page）。页的大小一样。（当然可以不一样，但是这样一来系统管理起来比较困难）。Linux在Alpha AXP系统上使用8K字节的页，而在Intel x86系统上使用4K字节的页。每一页都赋予一个唯一编号：page frame number(PFN 页编号)。在这种分页模型下，虚拟地址由两部分组成：虚拟页号和页内偏移量。假如页大小是4K，则虚拟地址的位11到0包括页内偏移量，位12和以上的位是页编号。每一次处理器遇到虚拟地址，它必须提取出偏移和虚拟页编号。处理器必须将虚拟页编号转换到物理的页，并访问物理页的正确偏移处。为此，处理器使用了页表（page tables）。
图3.1显示了两个进程的虚拟地址空间，进程X和进程Y，每一个进程拥有自己的页表。这些页表将每一个进程的虚拟页映射到内存的物理页上。图中显示进程X的虚拟页号0映射到物理页号1，而进程Y的虚拟页编号1映射到物理页号4。理论上页表每一个条目包括以下信息：
有效标志 表示页表本条目是否有效
本页表条目描述的物理页编号
访问控制信息 描述本页如何使用：是否可以写？是否包括执行代码？
页表通过虚拟页标号作为偏移来访问。虚拟页编号5是表中的第6个元素（0是第一个元素）
要将虚拟地址转换到物理地址，处理器首先找出虚拟地址的页编号和页内偏移量。使用2的幂次的页尺寸，可以用掩码或移位简单地处理。再一次看图3.1，假设页大小是0x2000（十进制8192），进程Y的虚拟地址空间的地址是0x2194，处理器将会把地址转换为虚拟页编号1内的偏移量0x194。
处理器使用虚拟页编号作为索引在进程的页表中找到它的页表的条目。如果该条目有效，处理器从该条目取出物理的页编号。如果本条目无效，就是进程访问了它的虚拟内存中不存在的区域。在这种情况下，处理器无法解释地址，必须将控制权传递给操作系统来处理。
处理器具体如何通知操作系统进程在访问无法转换的无效的虚拟地址，这个方式是和处理器相关的。处理器将这种信息（page fault）进行传递，操作系统得到通知，虚拟地址出错，以及出错的原因。
假设这是一个有效的页表条目，处理器取出物理页号并乘以页大小，得到了物理内存中本页的基础地址。最后，处理器加上它需要的指令或数据的偏移量。
再用上述例子，进程Y的虚拟页编号1映射到了物理页编号4（起始于0x8000 ， 4x 0x2000），加上偏移0x194，得到了最终的物理地址0x8194。
通过这种方式将虚拟地址映射到物理地址，虚拟内存可以用任意顺序映射到系统的物理内存中。例如，图3.1 中，虚拟内存X的虚拟页编号映射到了物理页编号1而虚拟页编号7虽然在虚拟内存中比虚拟页0要高，却映射到了物理页编号0。这也演示了虚拟内存的一个有趣的副产品：虚拟内存页不必按指定顺序映射到物理内存中。
3.1.1 Demand Paging
因为物理内存比虚拟内存少得多，操作系统必须避免无效率地使用物理内存。节省物理内存的一种方法是只加载执行程序正在使用的虚拟页。例如：一个数据库程序可能正在数据库上运行一个查询。在这种情况下，并非所有的数据必须放到内存中，而只需要正被检查的数据记录。如果这是个查找型的查询，那么加载程序中增加记录的代码就没什么意义。这种进行访问时才加载虚拟页的技术叫做demand paging。
当一个进程试图访问当前不在内存中的虚拟地址的时候处理器无法找到引用的虚拟页对应的页表条目。例如：图3.1中进程X的页表中没有虚拟页2 的条目，所以如果进程X试图从虚拟页2中的地址读取时，处理器无法将地址转换为物理地址。这时处理器通知操作系统发生page fault。
如果出错的虚拟地址无效意味着进程试图访问它不应该访问的虚拟地址。也许是程序出错，例如向内存中任意地址写。这种情况下，操作系统会中断它，从而保护系统中其他的进程。
如果出错的虚拟地址有效但是它所在的页当前不在内存中，操作系统必须从磁盘映像中将相应的页加载到内存中。相对来讲磁盘存取需要较长时间，所以进程必须等待直到该页被取到内存中。如果当前有其他系统可以运行，操作系统将选择其中一个运行。取到的页被写到一个空闲的页面，并将一个有效的虚拟页条目加到进程的页表中。然后这个进程重新运行发生内存错误的地方的机器指令。这一次虚拟内存存取进行时，处理器能够将虚拟地址转换到物理地址，所以进程得以继续运行。
Linux使用demand paging技术将可执行映像加载到进程的虚拟内存中。当一个命令执行时，包含它的文件被打开，它的内容被映射到进程的虚拟内存中。这个过程是通过修改描述进程内存映射的数据结构来实现，也叫做内存映射（memory mapping）。但是，实际上只有映像的第一部分真正放在了物理内存中。映像的其余部分仍旧在磁盘上。当映像执行时，它产生page fault，Linux使用进程的内存映像表来确定映像的那一部分需要加载到内存中执行。
3.1.2 Swapping（交换）
如果进程需要将虚拟页放到物理内存中而此时已经没有空闲的物理页，操作系统必须废弃物理空间中的另一页，为该页让出空间。
如果物理内存中需要废弃的页来自磁盘上的映像或者数据文件，而且没有被写过所以不需要存储，则该页被废弃。如果进程又需要该页，它可以从映像或数据文件中再次加载到内存中。
但是，如果该页已经被改变，操作系统必须保留它的内容以便以后进行访问。这种也叫做dirty page，当它从物理内存中废弃时，被存到一种叫做交换文件的特殊文件中。因为访问交换文件的速度和访问处理器以及物理内存的速度相比很慢，操作系统必须判断是将数据页写到磁盘上还是将它们保留在内存中以便下次访问。
如果决定哪些页需要废弃或者交换的算法效率不高，则会发生颠簸（thrashing）。这时，页不断地被写到磁盘上，又被读回，操作系统过于繁忙而无法执行实际的工作。例如在图3.1中，如果物理页号1经常被访问，那么就不要将它交换到硬盘上。进程正在使用的也叫做工作集(working set)。有效的交换方案应该保证所有进程的工作集都在物理内存中。
Linux使用LRU（Least Recently Used最近最少使用）的页面技术来公平地选择需要从系统中废弃的页面。这种方案将系统中的每一页都赋予一个年龄，这个年龄在页面存取时改变。页面访问越多，年纪越轻，越少访问，年纪越老越陈旧。陈旧的页面是交换的好候选。
3.1.3 Shared Vitual Memory（共享虚拟内存）
虚拟内存使多个进程可以方便地共享内存。所有的内存访问都是通过页表，每一个进程都有自己的页表。对于两个共享一个物理内存页的进程，这个物理页编号必须出现在两个进程的页表中。
图3.1显示了两个共享物理页号4的进程。对于进程X虚拟页号是4，而对于进程Y虚拟页号是6。这也表明了共享页的一个有趣的地方：共享的物理页不必存在共享它的进程的虚拟内存空间的同一个地方。
3.1.4 Physical and Vitual Addressing Modes（物理和虚拟寻址模式）
对于操作系统本身而言，运行在虚拟内存中没有什么意义。如果操作系统必须维护自身的页表，这将会是一场噩梦。大多数多用途的处理器同时支持物理地址模式和虚拟地址模式。物理寻址模式不需要页表，处理器在这种模式下不需要进行任何地址转换。Linux核心运行在物理地址模式。
Alpha AXP处理器没有特殊的物理寻址模式。它将内存空间分为几个区，将其中两个指定为物理映射地址区。核心的地址空间叫做KSEG地址空间，包括从0xfffffc0000000000向上的所有地址。为了执行连接在KSEG的代码（核心代码）或者访问那里的数据，代码必须在核心态执行。Alpha 上的Linux核心连接到从地址0xfffffc0000310000执行。
3.1.5 Access Control（访问控制）
页表条目也包括访问控制信息。当处理器使用页表条目将进程的虚拟地址映射到物理地址的时候，它很容易利用访问控制信息控制进程不要用不允许的方式进行访问。
有很多原因你希望限制对于内存区域的访问。一些内存，比如包含执行代码，本质上是只读的代码，操作系统应该禁止进程写它的执行代码。反过来，包括数据的页可以写，但是如果试图执行这段内存应该失败。大多数处理器有两种执行状态：核心态和用户态。你不希望用户直接执行核心态的代码或者存取核心数据结构，除非处理器运行在核心态。
访问控制信息放在PTE（page table entry）中，而且和具体处理器相关。图3.2显示了Alpha AXP的PTE。各个位意义如下：
V 有效，这个PTE是否有效
FOE “Fault on Execute” 试图执行本页代码时，处理器是否要报告page fault，并将控制权传递给操作系统。
ＦＯＷ “Fault on Write” 如上，在试图写本页时产生page fault
FOR “fault on read” 如上，在试图读本页时产生page fault
ASM 地址空间匹配。用于操作系统清除转换缓冲区中的部分条目
KRE 核心态的代码可以读本页
URE 用户态的代码可以读本页
GII 间隔因子，用于将一整块映射到一个转换缓冲条目而非多个。
KWE 核心态的代码可以写本页
UWE 用户态的代码可以写本页
Page frame number 对于V位有效的PTE，包括了本PTE的物理页编号；对于无效的PTE，如果不是0，包括了本页是否在交换文件的信息。
以下两位由Linux定义并使用
_PAGE_DIRTY 如果设置，本页需要写到交换文件中。
_PAGE_ACCESSED Linux 使用，标志一页已经访问过
3.2 Caches（高速缓存）
如果你用以上理论模型来实现一个系统，它可以工作，但是不会太高效率。操作系统和处理器的设计师都尽力让系统性能更高。除了使用更快的处理器、内存等，最好的方法是维护有用信息和数据的高速缓存，这会使一些操作更快。Linux使用了一系列和高速缓存相关的内存管理技术：
Buffer Cache： Buffer cache 包含了用于块设备驱动程序的数据缓冲区。这些缓冲区大小固定（例如512字节），包括从块设备读出的数据或者要写到块设备的数据。块设备是只能通过读写固定大小的数据块来访问的设备。所有的硬盘都是块设备。块设备用设备标识符和要访问的数据块编号作为索引，用来快速定位数据块。块设备只能通过buffer cache存取。如果数据可以在buffer cache中找到，那就不需要从物理块设备如硬盘上读取，从而使访问加快。
参见fs/buffer.c
Page Cache 用来加快对磁盘上映像和数据的访问。它用于缓存文件的逻辑内容，一次一页，并通过文件和文件内的偏移来访问。当数据页从磁盘读到内存中时，被缓存到page cache中。
参见mm/filemap.c
Swap Cache 只有改动过的（或脏dirty）页才存在交换文件中。只要它们写到交换文件之后没有再次修改，下一次这些页需要交换出来的时候，就不需要再写到交换文件中，因为该页已经在交换文件中了，直接废弃该页就可以了。在一个交换比较厉害的系统，这会节省许多不必要和高代价的磁盘操作。
参见mm/swap_state.c mm/swapfile.c
Hardware Cache:硬件高速缓存的常见的实现方法是在处理器里面：PTE的高速缓存。这种情况下，处理器不需要总是直接读页表，而在需要时把页转换表放在缓存区里。CPU里有转换表缓冲区(TLB Translation Look-aside Buffers)，放置了系统中一个或多个进程的页表条目的缓存的拷贝。
当引用虚拟地址时，处理区试图在TLB中寻找。如果找到了，它就直接将虚拟地址转换到物理地址，进而对数据执行正确的操作。如果找不到，它就需要操作系统的帮助。它用信号通知操作系统，发生了TLB missing。一个和系统相关的机制将这个异常转到操作系统相应的代码来处理。操作系统为这个地址映射生成新的TLB条目。当异常清除之后，处理器再次尝试转换虚拟地址，这一次将会成功因为TLB中该地址有了一个有效的条目。
高速缓存的副作用（不管是硬件或其他方式的）在于Linux必须花大量时间和空间来维护这些高速缓存区，如果这些高速缓存区崩溃，系统也会崩溃。
3.3 Linux Page Tables（Linux页表）
Linux假定了三级页表。访问的每一个页表包括了下一级页表的页编号。图3.3显示了一个虚拟地址如何分为一系列字段：每一个字段提供了在一个页表中的偏移量。为了将虚拟地址转换为物理地址，处理器必须取得每一级字段的内容，转换为包括该页表的物理页内的偏移，然后读取下一级页表的页编号。重复三次直到包括虚拟地址的物理地址的页编号找到为止。然后用虚拟地址中的最后一个字段：字节偏移量，在页内查找数据。
Linux运行的每一个平台都必须提供转换宏，让核心处理特定进程的页表。这样，核心不需要知道页表条目的具体结构或者如何组织。通过这种方式，Linux成功地使用了相同的页表处理程序用于Alpha和Intel x86处理器，其中Alpha使用三级页表，而Intel使用二级页表。
参见include/asm/pgtable.h
3.4 Page Allocation and Deallocation (页的分配和回收)
系统中对于物理页有大量的需求。例如，当程序映像加载到内存中的时候，操作系统需要分配页。当程序结束执行并卸载时需要释放这些页。另外为了存放核心相关的数据结构比如页表自身，也需要物理页。这种用于分配和回收页的机制和数据结构对于维护虚拟内存子系统的效率也许是最重要的。
系统中的所有的物理页都使用mem_map数据结构来描述。这是一个mem_map_t结构的链表，在启动时进行初始化。每一个mem_map_t（容易混淆的是这个结构也被称为page 结构）结构描述系统中的一个物理页。重要的字段（至少对于内存管理而言）是：
参见include/linux/mm.h
count 本页用户数目。如果本页由多个进程共享，计数器大于1。
Age 描述本页的年龄。用于决定本页是否可以废弃或交换出去。
Map_nr mem_map_t描述的物理页编号。
页分配代码使用free_area向量来查找空闲的页。整个缓冲管理方案用这种机制来支持。只要用了这种代码，处理器使用的页的大小和物理页的机制就可以无关。
每一个free_area单元包括页块的信息。数组中的第一个单元描述了单页，下一个是2页大小的块，下一个是4页大小的块，以此类推，依次向上都是2的倍数。这个链表单元用作队列的开头，有指向mem_map数组中页的数据结构的指针。空闲的页块在这里排队。Map是一个跟踪这么大小的页的分配组的位图。如果页块中的第N块空闲，则位图中的第N位置位。
图3.4显示了free_area结构。单元0有一个空闲页（页编号0），单元2有2个4页的空闲块，第一个起始于页编号4，第二个起始于页编号56。
3.4.1 Page Allocation (页分配)
参见mm/page_alloc.c get_free_pages()
Linux使用Buddy算法有效地分配和回收页块。页分配代码试图分配一个由一个或多个物理页组成的块。页分配使用2的幂数大小的块。这意味着可以分配1页大小，2页大小，4页大小的块，依此类推。只要系统有满足需要的足够的空闲页（nr_free_pages > min_free_pages），分配代码就会在free_area中查找满足需要大小的一个页块。Free_area中的每一个单元都有描述自身大小的页块的占用和空闲情况的位图。例如，数组中的第2个单元拥有描述4页大小的块的空闲和占用的分配图。
这个算法首先找它请求大小的内存页块。它跟踪free_area数据结构中的list单元队列中的空闲页的链表。如果请求大小的页块没有空闲，就找下一个尺寸的块（2倍于请求的大小）。继续这一过程一直到遍历了所有的free_area或者找到了空闲页块。如果找到的页块大于请求的页块，则该块将被分开成为合适大小的块。因为所有的块都是2的幂次的页数组成，所以这个分割的过程比较简单，你只需要将它平分就可以了。空闲的块则放到适当的队列，而分配的页块则返回给调用者。
例如在图3.4中，如果请求2页的数据块，第一个4页块（起始于页编号4）将会被分为两个2页块。起始于页号4的第一个2页块将会被返回给调用者，而第二个2页块（起始于页号6）将会排在free_area数组中的单元1中2页空闲块的队列中。
3.4.2 Page Deallocation（页回收）
分配页块的过程中将大的页块分为小的页块，将会使内存更为零散。页回收的代码只要可能就把页联成大的页块。其实页块的大小很重要（2的幂数），因为这样才能很容易将页块组成大的页块。
只要一个页块回收，就检查它的相邻或一起的同样大小的页块是否空闲。如果是这样，就把它和新释放的页块一起组成以一个新的下一个大小的空闲页块。每一次两个内存页块组合成为更大的页块时，页回收代码都要试图将页块合并成为更大的块。这样，空闲的页块就会尽可能的大。
例如，在图3.4，如果页号1释放，那么它会和已经空闲的页号0一起组合并放在free_area的单元1中空闲的2页块队列中。
3.5 Memory Mapping （内存映射）
当一个映像执行时，执行映像的内容必须放在进程的虚拟地址空间中。对于执行映像连接到的任意共享库，情况也是一样。执行文件实际并没有放到物理内存，而只是被连接到进程的虚拟内存。这样，只要运行程序引用了映像的部分，这部分映像就从执行文件中加载到内存中。这种映像和进程虚拟地址空间的连接叫做内存映射。
每一个进程的虚拟内存用一个mm_struct 数据结构表示。这包括当前执行的映像的信息（例如bash）和指向一组vm_area_struct结构的指针。每一个vm_area_struct的数据结构都描述了内存区域的起始、进程对于内存区域的访问权限和对于这段内存的操作。这些操作是一组例程，Linux用于管理这段虚拟内存。例如其中一种虚拟内存操作就是当进程试图访问这段虚拟内存时发现（通过page fault）内存不在物理内存中所必须执行的正确操作，这个操作叫做 nopage 操作。Linux请求把执行映像的页加载到内存中的时候用到nopage操作。
当一个执行映像映射到进程的虚拟地址空间时，产生一组vm_area_struct数据结构。每一个vm_area_struct结构表示执行映像的一部分：执行代码、初始化数据（变量）、未初始化数据等等。Linux支持一系列标准的虚拟内存操作，当vm_area_struct数据结构创建时，一组正确的虚拟内存操作就和它们关联在一起。
3.6 Demand Paging
只要执行映像映射到进程的虚拟内存中，它就可以开始运行。因为只有映像的最开始的部
分是放在物理内存中，很快就会访问到还没有放在物理内存的虚拟空间区。当进程访问没有有效页表条目的虚拟地址的时候，处理器向Linux报告page fault。Page fault描述了发生page fault的虚拟地址和内存访问类型。
Linux必须找到page fault 发生的空间区所对应的vm_area_struct数据结构（用Adelson-Velskii and Landis AVL树型结构连接在一起）。如果找不到这个虚拟地址对应的vm_area_struct结构，说明进程访问了非法的虚拟地址。Linux将向该进程发信号，发送一个SIGSEGV信号，如果进程没有处理这个信号，它就会退出。
参见 handle_mm_fault() in mm/memory.c
Linux然后检查page faul的类型和该虚拟内存区所允许的访问类型。如果进程用非法的方式访问内存，比如写一个它只可以读的区域，也会发出内存错的信号。
现在Linux确定page fault是合法的，它必须进行处理。Linux必须区分在交换文件和磁盘映像中的页，它用发生page fault的虚拟地址的页表条目来确定。
参见do_no_page() in mm/memory.c
如果该页的页表条目是无效的但非空，此页是在交换文件中。对于Alpha AXP页表条目来讲，有效位置位但是PFN域非空。这种情况下PFN域存放了此页在交换文件（以及那一个交换文件）中的位置。页在交换文件中如何处理在本章后面讨论。
并非所有的vm_area_struct数据结构都有一整套虚拟内存操作，而且那些有特殊的内存操作的也可能没有nopang操作。因为缺省情况下，对于nopage操作，Linux会分配一个新的物理页并创建有效的页表条目。如果这一段虚拟内存有特殊的nopage操作，Linux会调用这个特殊的代码。
通常的Linux nopage操作用于对执行映像的内存映射，并使用page cache将请求的映像页加载到物理内存中。虽然在请求的页调入的物理内存中以后，进程的页表得到更新，但是也许需要必要的硬件动作来更新这些条目，特别是如果处理器使用了TLB。既然page fault得到了处理，就可以扔在一边，进程在引起虚拟内存访问错误的指令那里重新运行。
参见mm/filemap.c 中filemap_nopage()
3.7 The Linux Page Cache
Linux的page cache的作用是加速对于磁盘文件的访问。内存映射文件每一次读入一页，这些页被存放在page cache中。图3.6显示了page cache，包括一个指向mem_map_t数据结构的指针向量：page_hash_table。Linux中的每一个文件都用一个VFS inode的数据结构标示（在第9章描述），每一个VFS I节点都是唯一的并可以完全确定唯一的一个文件。页表的索引取自VFS 的I节点号和文件中的偏移。
参见linux/pagemap.h
当一页的数据从内存映射文件中读出，例如当demand paging时需要放到内存中的时候，此页通过page cache中读出。如果此页在缓存中，就返回一个指向mem_map_t数据结构的指针给page fault 的处理代码。否则，此页必须从存放此文件的文件系统中加载到内存中。Linux分配物理内存并从磁盘文件中读出该页。如果可能，Linux会启动对文件下一页的读。这种单页的超前读意味着如果进程从文件中顺序读数据的话，下一页数据将会在内存中等待。
当程序映像读取和执行的时候page cache 不断增长。如果页不在需要，将从缓存中删除。比如不再被任何进程使用的映像。当Linux使用内存的时候，物理页可能不断减少，这时Linux可以减小page cache。
3.8 Swapping out and Discarding Pages（交换出去和废弃页）
当物理内存缺乏的时候，Linux内存管理子系统必须试图释放物理页。这个任务落在核心交换进程上（kswapd）。核心交换守护进程是一种特殊类型的进程，一个核心线程。核心线程是没有虚拟内存的进程，以核心态运行在物理地址空间。核心交换守护进程名字有一点不恰当，因为它不仅仅是将页交换到系统交换文件上。它的任务是保证系统有足够的空闲页，使内存管理系统有效地运行。
核心交换守护进程（kswapd）在启动时由核心的init 进程启动，并等待核心的交换计时器到期。每一次计时器到期，交换进程检查系统中的空闲页数是否太少。它使用两个变量：free_pages_high和free_pages_low来决定是否释放一些页。只要系统中的空闲页数保持在free_pages_high之上，交换进程什么都不做。它重新睡眠直到它的计时器下一次到期。为了做这种检查，交换进程要考虑正在向交换文件中写的页数，用nr_async_pages来计数：每一次一页排到队列中等待写到交换文件中的时候增加，写完的时候减少。Free_page_low和free_page_high是系统启动时间设置的，和系统中的物理页数相关。如果系统中的空闲页数小于free_pages_high或者比free_page_low还低，核心交换进程会尝试三种方法来减少系统使用的物理页数：
参见mm/vmscan.c 中的kswapd()
减少buffer cache 和page cache的大小
将系统V的共享内存页交换出去
交换和废弃页
如果系统中的空闲页数低于free_pages_low，核心交换进程将试图在下一次运行前释放6页。否则试图释放3页。以上的每一种方法都要被尝试直到释放了足够的页。核心交换进程记录了它上一次使用的释放物理页的方法。每一次运行时它都会首先尝试上一次成功的方法来释放页。
释放了足够的页之后，交换进程又一次睡眠，直到它的计时器又一次过期。如果核心交换进程释放页的原因是系统空闲页的数量少于free_pages_low，它只睡眠平时的一半时间。只要空闲页数大于free_pages_low，交换进程就恢复原来的时间间隔进行检查。
3.8.1 Reducing the size of the Page and Buffer Caches
page 和buffer cache中的页是释放到free_area向量中的好选择。Page Cache，包含了内存映射文件的页，可能有不必要的数据，占去了系统的内存。同样，Buffer Cache ，包括了从物理设备读或向物理设备写的数据，也可能包含了无用的缓冲。当系统中的物理页将要耗尽的时候，废弃这些缓存区中的页相对比较容易，因为它不需要向物理设备写（不象将页从内存中交换出去）。废弃这些页不会产生多少有害的副作用，只不过使访问物理设备和内存映射文件时慢一点。虽然如此，如果公平地废弃这些缓存区中的页，所有的进程受到的影响就是平等的。
每一次当核心交换进程要缩小这些缓存区时，它要检查mem_map页矢量中的页块，看是否可以从物理内存中废弃。如果系统空闲页太低（比较危险时）而核心交换进程交换比较厉害，这个检查的页块大小就会更大一些。页块的大小进行循环检查：每一次试图减少内存映射时都用一个不同的页块大小。这叫做clock算法，就象钟的时针。整个mem_map页向量都被检查，每次一些页。
参见mm/filemap.c shrink_map()
检查的每一页都要判断缓存在page cache 或者buffer cache中。注意共享页的废弃这时不考虑，一页不会同时在两个缓存中。如果该页不在这两个缓冲区中，则mem_map页向量表的下一页被检查。
缓存在buffer cache ch中的页（或者说页中的缓冲区被缓存）使缓冲区的分配和释放更有效。缩小内存映射的代码试图释放包含检查过的页的缓冲区。如果缓冲区释放了，则包含缓冲区的页也被释放了。如果检查的页是在Linux的page cache 中，它将从page cache 中删除并释放。
参见 fs/buffer.c free_buffer()
如果这次尝试释放了足够的页，核心交换进程就会继续等待直到下一次被周期性地唤醒。因为释放的页不属于任何进程的虚拟内存（只是缓存的页），因此不需要更新进程的页表。如果废弃的缓存页仍然不够，交换进程会试图交换出一些共享页。
3.8.2 Swapping Out System V Shared Memory Pages（交换出系统V的共享内存页）
系统V的共享内存是一种进程间通讯的机制，通过两个或多个进程共享虚拟内存交换信息。进程间如何共享内存在第5章详细讨论。现在只要讲讲每一块系统V共享内存都用一个shmid_ds的数据结构描述就足够了。它包括一个指向vm_area_struct链表数据结构的指针，用于共享此内存的每一个进程。Vm_area_struct数据结构描述了此共享内存在每一个进程中的位置。这个系统V的内存中的每一个vm_area_struct结构都用vm_next_shared和vm_prev_shared指针连接在一起。每一个shmid_ds数据结构都有一个页表条目的链表，每一个条目都描述一个共享的虚拟页和物理页的对应关系。
核心交换进程将系统V的共享内存页交换出去时也用clock算法。它每一次运行都记录了上一次交换出去了那一块共享内存的那一页。它用两个索引来记录：第一个是shmid_ds数据结构数组中的索引，第二个是这块共享内存区的页表链中的索引。这样可以共享内存区的牺牲比较公平。
参见ipc/shm.