《Linux Kernel核心中文手册 》pdf电子书免费下载
下载方式一：
百度网盘下载地址：https://pan.baidu.com/s/1YliS2toebQDMQcda_yxrBQ
百度网盘密码：1111
下载方式二：
http://ziliaoshare.cn/Download/ad_123557_ch_LinuxKernelHXZWSC.zip
|
|
作者：empty 出版社：empty |
《Linux Kernel核心中文手册》介绍
网易中文排行榜
Linux Kernel核心中文手册
来自：蓝森林自由软件
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 的 2 次幂是 10x10 ， 10 的 3 次幂是 10x10x10 ，依此类推。二进制 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 表示。例如，十六进制的 E 是十进制的 14 ，而十六进制的 2A 是十进制的 42 （ 2 个 16+10 ）。用 C 语言的表示法（本书一直使用），十六进制数字使用前缀“ 0x ”：十六进制的 2A 写做 0x2A 。
微处理器可以执行算术运算如加、乘和除，也可以执行逻辑操作例如“ X 是否大于 Y ”。
处理器的执行由外部时钟控制。这个时钟，即系统时钟，对处理器产生稳定的时钟脉冲，在每一个时钟脉冲里，处理器执行一些工作。例如，处理器可以在每一个时钟脉冲里执行一条指令。处理器的速度用系统时钟的频率来描述。一个 100Mhz 的处理器每秒钟接受到 100 ， 000 ， 000 次时钟脉冲。用时钟频率来描述 CPU 的能力是一种误解，因为不同的处理器在每一次时钟脉冲中执行的工作量不同。虽然如此，如果所有的条件同等，越快的时钟频率表示处理器的能力越强。处理器执行的指令非常简单，例如：“把内存位置 X 的内容读到寄存器 Y 中“。寄存器是微处理器的内部存储空间，用来存储数据并进行操作。执行的操作可能使处理器停止当前操作而转去执行内存中其他地方的指令。正是这些微小的指令集合在一起，赋予现代的微处理器几乎无限的能力，因为它每秒可以执行数百万甚至数十亿的指令。
执行指令时必须从内存中提取指令，指令自身也可能引用内存中的数据，这些数据也必须提取到内存中并在需要的时候保存到内存中去。
一个微处理器内部寄存器的大小、数量和类型完全决定于它的类型。一个 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 地址 0x3f0 读取一个字节到 X 寄存器“。这也是 CPU 通过读写系统硬件外设处于 I/O 地址空间的寄存器从而控制外设的方法。在地址空间中，普通外设（如 IDE 控制器，串行端口，软驱控制器等等）的寄存器在 PC 外设的多年发展中已经成了定例。 I/O 空间的地址 0x3f0 正是串行口（ COM1 ）的控制寄存器的地址。
有时控制器需要直接从系统内存读取大量内存，或直接写大量数据到系统内存中去。比如将用户数据写到硬盘上去。在这种情况下，使用直接内存存取（ DMA ）控制器，允许硬件设备直接存取系统内存，当然，这种存取必须在 CPU 的严格控制和监管下进行。
Timer( 时钟 )
所有操作系统需要知道时间，现代 PC 包括一个特殊的外设，叫做实时时钟（ RTC ）。它提供了两样东西：可靠的日期和精确的时间间隔。 RTC 有自己的电池，所以即使 PC 没有加电，它仍在运行。这也是为什么 PC 总是“知道”正确的日期和时间。时间间隔计时允许操作系统精确地调度基本工作。
网易中文排行榜
Linux Kernel核心中文手册
来自：蓝森林自由软件
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 核心的数据结构都包括一个和具体文件系统相关的例程地址，在安装文件系统时必须调用。
网易中文排行榜
Linux Kernel核心中文手册
来自：蓝森林自由软件
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.c shm_swap()
因为一个指定的系统 V 共享内存的虚拟页对应的物理页号包含在每一个共享这块虚拟内存的进程的页表中，所以核心交换进程必须修改所有的进程的页表来体现此页已经不在内存而在交换文件中。对于每一个交换出去的共享页，交换进程必须找到在每一个共享进程的页表中对应的此页的条目（通过查找每一个 vm_area_struct 指针）如果在一个进程页表中此共享内存页的条目有效，交换进程要把它变为无效，并且标记是交换页，同时将此共享页的在用数减 1 。交换出去的系统 V 共享页表的格式包括一个在 shmid_ds 数据结构组中的索引和在此共享内存区中页表条目的索引。
如果所有共享的内存都修改过，页的在用数变为 0 ，这个共享页就可以写到交换文件中。这个系统 V 共享内存区的 shmid_ds 数据结构指向的页表中此页的条目将会换成交换出的页表条目。交换出的页表条目无效但是包含一个指向打开的交换文件的索引和此页在此文件内的偏移量。这个信息用于将此页再取回物理内存中。
3.3 Swapping Out and Discarding Pages
交换进程轮流检查系统中的每一个进程是否可以用于交换。好的候选是可以交换的进程（有一些不行）并且有可以从内存中交换出去或废弃的一个或多个页。只有其他方法都不行的时候才会把页从物理内存交换到系统交换文件中。
参见 mm/vmscan.c swap_out()
来自于映像文件的执行映像的大部分内容可以从文件中重新读出来。例如：一个映像的执行指令不会被自身改变，所以不需要写到交换文件中。这些页只是被简单地废弃。如果再次被进程引用，可以从执行映像再次加载到内存中。
一旦要交换的进程确定下来，交换进程就查看它的所有虚拟内存区域，寻找没有共享或锁定的区域。 Linux 不会把选定进程的所有可以交换出去的页都交换出去，而只是去掉少量的页。如果页在内存中锁定，则不能被交换或废弃。
参见 mm/vmscan.c swap_out_vme() 跟踪进程 mm_struct 中排列的 vm_area_struct 结构中的 vm_next vm_nex 指针。
Linux 的交换算法使用了页的年龄。每一个页都有一个计数器（放在 mem_map_t 数据结构中），告诉核心交换进程此页是否值得交换出去。页不用时变老，访问时更新。交换进程只交换老的页。缺省地，页第一次分配时年龄赋值为 3 。每一次访问，它的年龄就增加 3 ，直到 20 。每一次系统交换进程运行时它将页的年龄减 1 使页变老。这个缺省的行为可以更改，所以这些信息（和其他相关信息）都存放在 swap_control 数据结构中。
如果页太老 ( 年龄 age = 0) ，交换进程会进一步处理。脏页可以交换出去， Linux 在描述此页的 PTE 中用一个和体系结构相关的位来描述这种页（见图 3.2 ）。但是，并非所有的脏页都需要写到交换文件。每一个进程的虚拟内存区域都可以拥有自己的交换操作（由 vm_area_struct 中的 vm_ops 指针指示），如果这样，交换进程会用它的这种方式。否则，交换进程会从交换文件中分配一页，并把此页写到该文件中。
此页的页表条目会用一个无效的条目替换，但是包括了此页在交换文件的信息：此页所在文件内的偏移和所用的交换文件。不管什么方式交换，原来的物理页被放回到 free_area 重释放。干净（或不脏）的页可以被废弃，放回到 free_area 中重用。
如果交换或废弃了足够的可交换进程的页，交换进程重新睡眠。下一次唤醒时它会考虑系统中的下一个进程。这样，交换进程轻咬去每一个进程的物理页，直到系统重新达到平衡。这种做法比交换出整个进程更公平。
3.9 The Swap Cache （交换缓存）
当把页交换到交换文件时， Linux 会避免写不必要写的页。有时可能一个页同时存在于交换文件和物理内存中。这发生于一页被交换出内存然后在进程要访问时又被调入内存的情况下。只要内存中的页没有被写过，交换文件中的拷贝就继续有效。
Linux 用 swap cache 来记录这些页。交换缓存是一个页表条目或者系统物理页的链表。一个交换页有一个页表条目，描述使用的交换文件和它在交换文件中的位置。如果交换缓存条目非 0 ，表示在交换文件中的一页没有被改动。如果此页后来被改动了（被写），它的条目就从交换缓存中删除）
当 Linux 需要交换一个物理页到交换文件的时候，它查看交换缓存，如果有此页的有效条目，它不需要把此页写到交换文件。因为内存中的此页从上次读到交换文件之后没有被修改过。
交换缓存中的条目是曾经交换出去的页表条目。它们被标记为无效，但是包含了允许 Linux 找到正确交换文件和交换文件中正确页的信息。
3.10 Swapping Page In （交换进）
保存在交换文件中的脏页可能又需要访问。例如：当应用程序要向虚拟内存中写数据，而此页对应的物理页交换到了交换文件时。访问不在物理内存的虚拟内存页会引发 page fault 。 Page fault 是处理器通知操作系统它不能将虚拟内存转换到物理内存的信号。因为交换出去后虚拟内存中描述此页的页表条目被标记为无效。处理器无法处理虚拟地址到物理地址的转换，将控制转回到操作系统，告诉它发生错误的虚拟地址和错误的原因。这个信息的格式和处理器如何把控制转回到操作系统是和处理器类型相关的。处理器相关的 page faule 处理代码必须定位描述包括出错虚拟地址的虚拟内存区的 vm_area_struct 的数据结构。它通过查找该进程的 vm_area_struct 数据结构，直到找到包含了出错的虚拟地址的那一个。这是对时间要求非常严格的代码，所以一个进程的 vm_area_struct 数据结构按照特定的方式排列，使这种查找花费时间尽量少。
参见 arch/i386/mm/fault.c do_page_fault()
执行了合适的和处理器相关的动作并找到了包括错误（发生）的虚拟地址的有效的虚拟内存， page fault 的处理过程又成为通用的，并可用于 Linux 能运行的所有处理器。通用的 page fault 处理代码查找错误虚拟地址的页表条目。如果它找到的页表条目是交换出去的页， Linux 必须把此页交换回物理内存。交换出去的页的页表条目的格式和处理器相关，但是所有的处理器都将这些页标为无效并在页表条目中放进了在交换文件中定位页的必要信息。 Linux 使用这种信息把此页调回到物理内存中。
参见 mm/memory.c do_no_page()
这时， Linux 知道了错误（发生）的虚拟地址和关于此页交换到哪里去的页表条目。 Vm_area_struct 数据结构可能包括一个例程的指针，用于把这块虚拟内存中的页交换回到物理内存中。这是 swapin 操作。如果这块内存中有 swapin 操作， Linux 会使用它。其实，交换出去的系统 V 的共享内存之所以需要特殊的处理因为交换的系统 V 的共享内存页的格式和普通交换页的不同。如果没有 swapin 操作， Linux 假定这是一个普通页，不需要特殊的处理。它分配一块空闲的物理页并将交换出去的页从交换文件中读进来。关于从交换文件哪里（和哪一个交换文件）的信息取自无效的页表条目。
参见 mm/page_alloc.c swap_in()
如果引起 page fault 的访问不是写访问，页就留在交换缓存中，它的页表条目标记为不可写。如果后来此页又被写，会产生另一个 page fault ，这时，此页被标志为脏页，而它的条目也从交换缓存中删除。如果此页没有被修改而又需要交换出来， Linux 就可以避免将此页写到交换文件，因为此页已经在交换文件中了。
如果将此页从交换文件调回的访问是写访问，这个页就从交换缓存中删除，此页的页表条目页标记为脏页和可写。
网易中文排行榜
Linux Kernel核心中文手册
来自：蓝森林自由软件
Chapter 4 Processes （进程）
本章描述进程是什么以及 Linux 如何创建、管理和删除系统中的进程。
进程执行操作系统中的任务。程序是存放在磁盘上的包括一系列机器代码指令和数据的可执行的映像，因此，是一个被动的实体。进程可以看作是一个执行中的计算机程序。它是动态的实体，在处理器执行机器代码指令时不断改变。处理程序的指令和数据，进程也包括程序计数器和其他 CPU 的寄存器以及包括临时数据（例如例程参数、返回地址和保存的变量）的堆栈。当前执行的程序，或者说进程，包括微处理器中所有的当前的活动。 Linux 是一个多进程的操作系统。进程是分离的任务，拥有各自的权利和责任。如果一个进程崩溃，它不应该让系统中的另一个进程崩溃。每一个独立的进程运行在自己的虚拟地址空间，除了通过安全的核心管理的机制之外无法影响其他的进程。
在一个进程的生命周期中它会使用许多系统资源。它会用系统的 CPU 执行它的指令，用系统的物理内存来存储它和它的数据。它会打开和使用文件系统中的文件，会直接或者间接使用系统的物理设备。 Linux 必须跟踪进程本身和它使用的系统资源以便管理公平地管理该进程和系统中的其他进程。如果一个进程独占了系统的大部分物理内存和 CPU ，对于其他进程就是不公平的。
系统中最宝贵的资源就是 CPU 。通常系统只有一个。 Linux 是一个多进程的操作系统。它的目标是让进程一直在系统的每一个 CPU 上运行，充分利用 CPU 。如果进程数多于 CPU （多数是这样），其余的进程必须等到 CPU 被释放才能运行。多进程是一个简单的思想：一个进程一直运行，直到它必须等待，通常是等待一些系统资源，等拥有了资源，它才可以继续运行。在一个单进程的系统，比如 DOS ， CPU 被简单地设为空闲，这样等待的时间就会被浪费。在一个多进程的系统中，同一时刻许多进程在内存中。当一个进程必须等待时操作系统将 CPU 从这个进程拿走，并将它交给另一个更需要的进程。是调度程序选择了
下一次最合适的进程。 Linux 使用了一系列的调度方案来保证公平。
Linux 支持许多不同的可执行文件格式， ELF 是其中之一， Java 是另一个。 Linux 必须透明地管理这些文件，因为进程使用系统的共享的库。
4.1 Linux Processes （ Linux 的进程）
Linux 中，每一个进程用一个 task_struct （在 Linux 中 task 和 process 互用）的数据结构来表示，用来管理系统中的进程。 Task 向量表是指向系统中每一个 task_struct 数据结构的指针的数组。这意味着系统中最大进程数受 task 向量表的限制，缺省是 512 。当新的进程创建的时候，从系统内存中分配一个新的 task_struct ，并增加到 task 向量表中。为了更容易查找，用 current 指针指向当前运行的进程。
参见 include/linux/sched.h
除了普通进程， Linux 也支持实时进程。这些进程必须对于外界事件迅速反应（因此叫做“实时”），调度程序必须和普通用户进程区分对待。虽然 task_struct 数据结构十分巨大、复杂，但是它的域可以分为以下的功能：
State 进程执行时它根据情况改变状态 (state) 。 Linux 进程使用以下状态：（这里漏掉了 SWAPPING ，因为看来没用到）
Running 进程在运行 ( 是系统的当前进程 ) 或者准备运行（等待被安排到系统的一个 CPU 上）
Waiting 进程在等待一个事件或资源。 Linux 区分两种类型的等待进程：可中断和不可中断的（ interruptible and uninterruptible ）。可中断的等待进程可以被信号中断，而不可中断的等待进程直接等待硬件条件，不能被任何情况中断。
Stopped 进程停止了，通常是接收到了一个信号。正在调试的进程可以在停止状态。
Zombie 终止的进程，因为某种原因，在 task 向量表重任旧有一个 task_struct 数据结构的条目。就想听起来一样，是一个死亡的进程。
Scheduling Information 调度者需要这个信息用于公平地决定系统中的进程哪一个更应该运行。
Identifiers 系统中的每一个进程都有一个进程标识符。进程标识符不是 task 向量表中的索引，而只是一个数字。每一个进程也都有用户和组（ user and group ）的标识符。用来控制进程对于系统中文件和设备的访问。
Inter-Process Communication Linux 支持传统的 UNIX-IPC 机制，即信号，
《Linux Kernel核心中文手册》目录
empty