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磁盘控制器可能内置在系统主板上。

1. 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或2¹+2³+2⁵）。在计算机程序除了使用二进制表示数字之外，另一种基数，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寄存器会纪录能够确定当前模式的那些信息。

　

2. Memory(内存)

　

所有系统都具有分级的内存结构，由位于不同级别的速度和容量不同的内存组成。

最快的内存是高速缓存存储器，就象它的名字暗示的一样-用于临时存放或缓存主内存的内容。这种内存非常快但是比较昂贵，因此多数处理器芯片上内置有少量的高速缓冲存储器，而大多数高速缓存存储器放在系统主板上。一些处理器用一块缓存内存同时缓存指令和数据，而另一些处理器有两块缓存内存-一个用于指令，另一个用于数据。Alpha AXP处理器有两个内置的内存高速缓存存储器：一个用于数据（D-Cache），另一个用于指令（I-Cache）。它的外部高速缓冲存储器（或B-Cache）将两者混在一起。

最后一种内存是主内存。相对于外部高速缓存存储器而言速度非常慢，对于CPU内置的高速缓存存储器，主内存简直是在爬。

高速缓存存储器和主内存必须保持同步（一致）。换句话说，如果主内存中的一个字保存在高速缓存存储器的一个或多个位置，那么系统必须保证高速缓存存储器和主内存的内容一样。使高速缓冲存储器同步的工作一部分是由硬件完成，另一部分则是由操作系统完成的。对于其它一些系统的主要任务，硬件和软件也必须紧密配合。

　

3. Buses（总线）

系统板的各个组成部分由被称为总线的连接系统互连在一起。系统总线分为三种逻辑功能：地址总线、数据总线和控制总线。地址总线指定了数据传输的内存位置（地址），数据总线保存了传输的数据。数据总线是双向的，它允许CPU读取，也允许CPU写。控制总线包含了各种信号线用于在系统中发送时钟和控制信号。有许多种不同的总线类型，ISA和PCI总线是系统用于连接外设的常用方式。

　

4. Controllers and Peripherals （控制器和外设）

　

外设指实在的设备，如由系统板或系统板插卡上的控制芯片所控制的图形卡或磁盘。IDE控制芯片控制IDE磁盘，而SCSI控制芯片控制SCSI磁盘。这些控制器通过不同的总线连接到CPU并相互连接。现在制造的大多数系统都是用PCI或ISA总线将系统的主要部件连接在一起。控制器本身也是象CPU一样的处理器，它们可以看作CPU的智能助手，CPU拥有系统的最高控制权。

　

所有的控制器都是不同的，但是通常它们都有用于控制它们的寄存器。CPU上运行的软件必须能够读写这些控制寄存器。一个寄存器可能包含描述错误的状态码，另一个寄存器可能用于控制用途，改变控制器的模式。一个总线上的每一个控制器都可以分别被CPU寻址，这样软件设备驱动程序就可以读写它的寄存器进而控制它。IDE电缆是一个好例子，它给了你分别存取总线上每一个驱动器的能力。另一个好例子是PCI总线，允许每一个设备（如图形卡）被独立存取。

　

5. 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的严格控制和监管下进行。

　

6. Timer(时钟)

所有操作系统需要知道时间，现代PC包括一个特殊的外设，叫做实时时钟（RTC）。它提供了两样东西：可靠的日期和精确的时间间隔。RTC有自己的电池，所以即使PC没有加电，它仍在运行。这也是为什么PC总是“知道”正确的日期和时间。时间间隔计时允许操作系统精确地调度基本工作。

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片断：

执行了和前面示例中汇编代码完全一样的操作。如果变量x的内容和变量y的内容不一样，变量y的内容被拷贝到变量x。C代码用例程（routine）进行组合，每一个例程执行一项任务。例程可以返回C所支持的任意的数值或数据类型。大型程序比如Linux核心分别由许多的C语言模块组成，每一个模块有自己的例程和数据结构。这些C源代码模块共同构成了逻辑功能比如文件系统的处理代码。

C支持多种类型的变量。一个变量是内存中的特定位置，可用符号名引用。上述的C片断中，x和y引用了内存中的位置。程序员不需要关心变量在内存中的具体位置，这是连接程序（下述）必须处理的。一些变量包含不同的数据例如整数、浮点数等和另一些则包含指针。

指针是包含其它数据在内存中的地址的变量。假设一个变量x，位于内存地址0x80010000， 你可能有一个指针px，指向x。 Px可能位于地址0x80010030。Px的值则是变量x的地址，0x80010000。

C允许你将相关的变量集合成为结构。例如：

} 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一样没有用处。

这里的$是登录的shell输出的提示符（此例是bash）：表示shell在等候你（用户）输入命令。输入ls引发键盘驱动程序识别输入的字符，键盘驱动程序将识别的字符传递给shell去处理。shell先查找同名的可执行映象，它找到了/bin/ls, 然后调用核心服务将ls执行程序加载到虚拟内存中并开始执行。ls执行程序通过执行核心的文件子系统的系统调用查找文件。文件系统可能使用缓存的文件系统信息或通过磁盘设备驱动程序从磁盘上读取文件信息,也可能是通过网络设备驱动程序同远程主机交换信息而读取本系统所访问的远程文件的详细信息（文件系统可以通过NFS网络文件系统远程安装）。不管文件信息是如何得到的，ls都将信息输出，通过显示驱动程序显示在屏幕上。

2.2.1 Memory management（内存管理）

2.2.2 Processes (进程)

进程可以看作一个在执行的程序，每一个进程都是正在运行的特定的程序的独立实体。如果你观察一下你的Linux系统，你会发现有很多进程在运行。例如：在我的系统上输入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的周期数。

链接表是常用的数据结构，但是游历链接表的效率可能并不高。如果你要寻找指定的元素， 可能必须查找完整个表才能找到。Linux使用另一种技术：Hashing 来解决这种局限。Hash table是指针的数组或者说向量表。数组或向量表是在内存中依次存放的对象。书架可以说是书的数组。数组用索引来访问，索引是数组中的偏移量。再来看书架的例子，你可以使用在书架上的位置来描述每一本书：比如第5本书。

Hash table是一个指向数据结构的指针的数组，它的索引来源于数据结构中的信息。如果你用一个数据结构来描述一个村庄的人口，你可以用年龄作为索引。要找出一个指定的人的数据，你可以用他的年龄作为索引在人口散列表中查找，通过指针找到包括详细信息的数据结构。不幸的是，一个村庄中可能很多人年龄相同，所以散列表的指针指向另一个链表数据结构，每一个元素描述同龄人。即使这样，查找这些较小的链表仍然比查找所有的数据结构要快。

Hash table可用于加速常用的数据结构的访问，在Linux里常用hash table来实现缓冲。缓冲是需要快速存取的信息，是全部可用信息的一个子集。数据结构被放在缓冲区并保留在那里，因为核心经常访问这些结构。使用缓冲区也有副作用，因为使用起来比简单链表或者散列表更加复杂。如果数据结构可以在缓冲区找到（这叫做缓冲命中），那么一切很完美。但是如果数据结构不在缓冲区中，那么必须查找所用的相关的数据结构，如果找到，那么就加到缓冲区中。增加新的数据结构到缓冲区中可能需要废弃一个旧的缓冲入口。Linux必须决定废弃那一个数据结构，风险在于废弃的可能使Linux下一个要访问的数据结构。

2.3.3 Abstract Interfaces（抽象接口）

Linux核心经常将它的接口抽象化。接口是以特定方式工作的一系列例程和数据结构。比如：所有的网络设备驱动程序都必须提供特定的例程来处理特定的数据结构。用抽象接口的方式可以用通用的代码层来使用底层特殊代码提供的服务（接口）。例如网络层是通用的，而它由底层符合标准接口的同设备相关的代码提供支持。

通常这些底层在启动时向高一层登记。这个登记过程常通过在链接表中增加一个数据结构来实现。例如，每一个连结到核心的文件系统在核心启动时进行登记（或者如果你使用模块，在文件系统第一次使用时向核心登记）。你可以查看文件/proc/filesystems来检查那些文件系统进行了登记。登记所用的数据结构通常包括指向函数的指针。这是执行特定任务的软件函数的地址。再一次用文件系统登记的例子，每一个文件系统登记时传递给Linux核心的数据结构都包括一个和具体文件系统相关的例程地址，在安装文件系统时必须调用。

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。这也演示了虚拟内存的一个有趣的副产品：虚拟内存页不必按指定顺序映射到物理内存中。

因为物理内存比虚拟内存少得多，操作系统必须避免无效率地使用物理内存。节省物理内存的一种方法是只加载执行程序正在使用的虚拟页。例如：一个数据库程序可能正在数据库上运行一个查询。在这种情况下，并非所有的数据必须放到内存中，而只需要正被检查的数据记录。如果这是个查找型的查询，那么加载程序中增加记录的代码就没什么意义。这种进行访问时才加载虚拟页的技术叫做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数据结构创建时，一组正确的虚拟内存操作就和它们关联在一起。

分是放在物理内存中，很快就会访问到还没有放在物理内存的虚拟空间区。当进程访问没有有效页表条目的虚拟地址的时候，处理器向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()

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，交换进程就恢复原来的时间间隔进行检查。

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数据结构指向的页表中此页的条目将会换成交换出的页表条目。交换出的页表条目无效但是包含一个指向打开的交换文件的索引和此页在此文件内的偏移量。这个信息用于将此页再取回物理内存中。

参见 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就可以避免将此页写到交换文件，因为此页已经在交换文件中了。

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机制，即信号，管道和信号灯（semaphores），也支持系统V的IPC机制，即共享内存、信号灯和消息队列。关于Linux支持的IPC机制在第5章中描述。

Links 在Linux系统中，没有一个进程是和其他进程完全无关的。系统中的每一个进程，除了初始的进程之外，都有一个父进程。新进程不是创建的，而是拷贝，或者说从前一个进程克隆的（cloned）。每一个进程的task_struct中都有指向它的父进程和兄弟进程（拥有相同的父进程的进程）以及它的子进程的的指针。在Linux系统中你可以用pstree命令看到正在运行的进程的家庭关系。

另外系统中的所有的进程信息还存放在一个task_struct数据结构的双向链表中，根是init进程。这个表让Linux可以查到系统中的所有的进程。它需要这个表以提供对于ps或者kill等命令的支持。

Times and Timers 在一个进程的生命周期中，核心除了跟踪它使用的CPU时间还记录它的其他时间。每一个时间片（clock tick），核心更新jiffies中当前进程在系统和用户态所花的时间综合。Linux也支持进程指定的时间间隔的计数器。进程可以使用系统调用建立计时器，在计时器到期的时候发送信号给自己。这种计时器可以是一次性的，也可是周期性的。

File system 进程可以根据需要打开或者关闭文件，进程的task_struct结构存放了每一个打开的文件描述符的指针和指向两个VFS I节点（inode）的指针。每一个VFS I节点唯一描述一个文件系统中的一个文件或目录，也提供了对于底层文件系统的通用接口。Linux下如何支持文件系统在第9章中描述。第一个I节点是该进程的根（它的主目录），第二个是它的当前或者说pwd目录。Pwd取自Unix命令：印出工作目录。这两个VFS节点本身有计数字段，随着一个或多个进程引用它们而增长。这就是为什么你不能删除一个进程设为工作目录的目录。

Virtual memory 多数进程都有一些虚拟内存（核心线程和核心守护进程没有），Linux核心必须知道这些虚拟内存是如何映射到系统的物理内存中的。

Processor Specific Context 进程可以看作是系统当前状态的总和。只要进程运行，它就要使用处理器的寄存器、堆栈等等。当一个进程暂停的时候，这些进程的上下文、和CPU相关的上下文必须保存到进程的task_struct结构中。当调度者重新启动这个进程的时候，它的上下文就从这里恢复。

4.2 Identifiers （标识）

Linux，象所有的Unix，使用用户和组标识符来检查对于系统中的文件和映像的访问权限。Linux系统中所有的文件都有所有权和许可，这些许可描述了系统对于该文件或目录拥有什么样的权限。基本的权限是读、写和执行，并分配了3组用户：文件属主、属于特定组的进程和系统中的其他进程。每一组用户都可以拥有不同的权限，例如一个文件可以让它的属主读写，它的组读，而系统中的其他进程不能访问。

Linux使用组来给一组用户赋予对文件或者目录的权限，而不是对系统中的单个用户或者进程赋予权限。比如你可以为一个软件项目中的所有用户创建一个组，使得只有他们才能够读写项目的源代码。一个进程可以属于几个组（缺省是32个），这些组放在每一个进程的task_struct结构中的groups向量表中。只要进程所属的其中一个组对于一个文件有访问权限，则这个进程就又对于这个文件的适当的组权限。

一个进程的task_struct中有4对进程和组标识符。

Uid,gid 该进程运行中所使用的用户的标识符和组的标识符

Effective uid and gid 一些程序把执行进程的uid和gid 改变为它们自己的（在VFS I节点执行映像的属性中）。这些程序叫做setuid程序。这种方式有用，因为它可以限制对于服务的访问，特别是那些用其他人的方式运行的，例如网络守护进程。有效的uid 和gid来自setuid程序，而uid和gid 仍旧是原来的。核心检查特权的时候检查有效 uid和gid。

File system uid and gid 通常和有效uid和gid相等，检查对于文件系统的访问权限。用于通过NFS安装的文件系统。这时用户态的NFS服务器需要象一个特殊进程一样访问文件。只有文件系统uid和gid改变（而非有效uid和gid）。这避免了恶意用户向NFS的服务程序发送Kill信号。Kill用一个特别的有效uid和gid发送给进程。

Saved uid and gid 这是POSIX标准的要求，让程序可以通过系统调用改变进程的uid和gid。用于在原来的uid和gid改变之后存储真实的uid和gid。

4.3 Scheduling （调度）

所有的进程部分运行与用户态，部分运行于系统态。底层的硬件如何支持这些状态各不相同但是通常有一个安全机制从用户态转入系统态并转回来。用户态比系统态的权限低了很多。每一次进程执行一个系统调用，它都从用户态切换到系统态并继续执行。这时让核心执行这个进程。Linux中，进程不是互相争夺成为当前运行的进程，它们无法停止正在运行的其它进程然后执行自身。每一个进程在它必须等待一些系统事件的时候会放弃CPU。例如，一个进程可能不得不等待从一个文件中读取一个字符。这个等待发生在系统态的系统调用中。进程使用了库函数打开并读文件，库函数又执行系统调用从打开的文件中读入字节。这时，等候的进程会被挂起，另一个更加值得的进程将会被选择执行。进程经常调用系统调用，所以经常需要等待。即使进程执行到需要等待也有可能会用去不均衡的CPU事件，所以Linux使用抢先式的调度。用这种方案，每一个进程允许运行少量一段时间，200毫秒，当这个时间过去，选择另一个进程运行，原来的进程等待一段时间直到它又重新运行。这个时间段叫做时间片。

需要调度程序选择系统中所有可以运行的进程中最值得的进程。一个可以运行的进程是一个只等待CPU的进程。Linux使用合理而简单的基于优先级的调度算法在系统当前的进程中进行选择。当它选择了准备运行的新进程，它就保存当前进程的状态、和处理器相关的寄存器和其他需要保存的上下文信息到进程的task_struct数据结构中。然后恢复要运行的新的进程的状态（又和处理器相关），把系统的控制交给这个进程。为了公平地在系统中所有可以运行（runnable）的进程之间分配CPU时间，调度程序在每一个进程的task_struct结构中保存了信息：

参见 kernel/sched.c schedule()

policy 进程的调度策略。Linux有两种类型的进程：普通和实时。实时进程比所有其它进程的优先级高。如果有一个实时的进程准备运行，那么它总是先被运行。实时进程有两种策略：环或先进先出（round robin and first in first out）。在环的调度策略下，每一个实时进程依次运行，而在先进先出的策略下，每一个可以运行的进程按照它在调度队列中的顺序运行，这个顺序不会改变。

Priority 进程的调度优先级。也是它允许运行的时候可以使用的时间量（jiffies）。你可以通过系统调用或者renice命令来改变一个进程的优先级。

Rt_priority Linux支持实时进程。这些进程比系统中其他非实时的进程拥有更高的优先级。这个域允许调度程序赋予每一个实时进程一个相对的优先级。实时进程的优先级可以用系统调用来修改

Coutner 这时进程可以运行的时间量（jiffies）。进程启动的时候等于优先级（priority），每一次时钟周期递减。

调度程序从核心的多个地方运行。它可以在把当前进程放到等待队列之后运行，也可以在系统调用之后进程从系统态返回进程态之前运行。需要运行调度程序的另一个原因是系统时钟刚好把当前进程的计数器(counter)置成了0。每一次调度程序运行它做以下工作：

参见 kernel/sched.c schedule()

kernel work 调度程序运行bottom half handler并处理系统的调度任务队列。这些轻量级的核心线程在第11章详细描述

Current pocess 在选择另一个进程之前必须处理当前进程。

如果任务是可中断的而且它上次调度的时候收到过一个信号，它的状态变为RUNNING

如果当前进程超时，它的状态成为RUNNING

如果当前进程的状态为RUNNING则保持此状态

不是RUNNING或者INTERRUPTIBLE的进程被从运行队列中删除。这意味着当调度程序查找最值得运行的进程时不会考虑这样的进程。

Process Selection 调度程序查看运行队列中的进程，查找最值得运行的进程。如果有实时的进程（具有实时调度策略），就会比普通进程更重一些。普通进程的重量是它的counter，但是对于实时进程则是counter 加1000。这意味着如果系统中存在可运行的实时进程，就总是在任何普通可运行的进程之前运行。当前的进程，因为用掉了一些时间片（它的counter减少了），所以如果系统中由其他同等优先级的进程，就会处于不利的位置：这也是应该的。如果几个进程又同样的优先级，最接近运行队列前段的那个就被选中。当前进程被放到运行队列的后面。如果一个平衡的系统，拥有大量相同优先级的进程，那么回按照顺序执行这些进程。这叫做环型调度策略。不过，因为进程需要等待资源，它们的运行顺序可能会变化。

Swap Processes 如果最值得运行的进程不是当前进程，当前进程必须被挂起，运行新的进程。当一个进程运行的时候它使用了CPU和系统的寄存器和物理内存。每一次它调用例程都通过寄存器或者堆栈传递参数、保存数值比如调用例程的返回地址等。因此，当调度程序运行的时候它在当前进程的上下文运行。它可能是特权模式：核心态，但是它仍旧是当前运行的进程。当这个进程要挂起时，它的所有机器状态，包括程序计数器(PC)和所有的处理器寄存器，必须存到进程的task_struct数据结构中。然后，必须加载新进程的所有机器状态。这种操作依赖于系统，不同的CPU不会完全相同地实现，不过经常都是通过一些硬件的帮助。

如果前一个进程或者新的当前进程使用虚拟内存，则系统的页表需要更新。同样，这个动作适合体系结构相关。Alpha AXP处理器，使用TLT（Translation Look-aside Table）或者缓存的页表条目，必须清除属于前一个进程的缓存的页表条目。

4.3.1 Scheduling in Multiprocessor Systems（多处理器系统中的调度）

在Linux世界中，多CPU系统比较少，但是已经做了大量的工作使Linux成为一个SMP（对称多处理）的操作系统。这就是，可以在系统中的CPU之间平衡负载的能力。负载均衡没有比在调度程序中更重要的了。

在一个多处理器的系统中，希望的情况是：所有的处理器都繁忙地运行进程。每一个进程都独立地运行调度程序直到它的当前的进程用完时间片或者不得不等待系统资源。SMP系统中第一个需要注意的是系统中可能不止一个空闲（idle）进程。在一个单处理器的系统中，空闲进程是task向量表中的第一个任务，在一个SMP系统中，每一个CPU都有一个空闲的进程，而你可能有不止一个空闲CPU。另外，每一个CPU有一个当前进程，所以SMP系统必须记录每一个处理器的当前和空闲进程。

在一个SMP系统中，每一个进程的task_struct都包含进程当前运行的处理器编号（processor）和上次运行的处理器编号（last_processor）。为什么进程每一次被选择运行时不要在不同的CPU上运行是没什么道理的，但是Linux可以使用processor_mask把进程限制在一个或多个CPU上。如果位N置位，则该进程可以运行在处理器N上。当调度程序选择运行的进程的时候，它不会考虑processor_mask相应位没有设置的进程。调度程序也会利用上一次在当前处理器运行的进程，因为把进程转移到另一个处理器上经常会有性能上的开支。

4.4 Files（文件）

图4.1显示了描述系统每一个进程中的用于描述和文件系统相关的信息的两个数据结构。第一个fs_struct包括了这个进程的VFS I节点和它的umask。Umask是新文件创建时候的缺省模式，可以通过系统调用改变。

参见include/linux/sched.h

第二个数据结构，files_struct，包括了进程当前使用的所有文件的信息。程序从标准输入读取，向标准输出写，错误信息输出到标准错误。这些可以是文件，终端输入/输出或者世纪的设备，但是从程序的角度它们都被看作是文件。每一个文件都有它的描述符，files_struct包括了指向256个file数据结果，每一个描述进程形用的文件。F_mode域描述了文件创建的模式：只读、读写或者只写。F_pos记录了下一次读写操作在文件中的位置。F_inode指向描述该文件的I节点，f_ops是指向一组例程地址的指针，每一个地址都是一个用于处理文件的函数。例如写数据的函数。这种抽象的接口非常强大，使得Linux可以支持大量的文件类型。我们可以看到，在Linux中pipe也是用这种机制实现的。

每一次打开一个文件，就使用files_struct中的一个空闲的file指针指向这个新的file结构。Linux进程启动时有3个文件描述符已经打开。这就是标准输入、标准输出和标准错误，这都是从创建它们的父进程中继承过来的。对于文件的访问都是通过标准的系统调用，需要传递或返回文件描述符。这些描述符是进程的fd向量表中的索引，所以标准输入、标准输出和标准错误的文件描述符分别是0，1和2。对于文件的所有访问都是利用file数据结构中的文件操作例程和它的VFS I节点一起来实现的。

4.5 Virtual Memory（虚拟内存）

进程的虚拟内存包括多种来源的执行代码和数据。第一种是加载的程序映像，例如ls命令。这个命令，象所有的执行映像一样，由执行代码和数据组成。映像文件中包括将执行代码和相关的程序数据加载到进程地虚拟内存中所需要的所有信息。第二种，进程可以在处理过程中分配（虚拟）内存，比如用于存放它读入的文件的内容。新分配的虚拟内存需要连接到进程现存的虚拟内存中才能使用。第三中，Linux进程使用通用代码组成的库，例如文件处理。每一个进程都包括库的一份拷贝没有意义，Linux使用共享库，几个同时运行的进程可以共用。这些共享库里边的代码和数据必须连接到该进程的虚拟地址空间和其他共享该库的进程的虚拟地址空间。

在一个特定的时间，进程不会使用它的虚拟内存中包括的所有代码和数据。它可能包括旨在特定情况下使用的代码，比如初始化或者处理特定的事件。它可能只是用了它的共享库中一部分例程。如果把所有这些代码都加载到物理内存中而不使用只会是浪费。把这种浪费和系统中的进程数目相乘，系统的运行效率会很低。Linux改为使用demand paging 技术，进程的虚拟内存只在进程试图使用的时候才调入物理内存中。所以，Linux不把代码和数据直接加载到内存中，而修改进程的页表，把这些虚拟区域标志为存在但是不在内存中。当进程试图访问这些代码或者数据，系统硬件会产生一个page fault，把控制传递给Linux核心处理。因此，对于进程地址空间的每一个虚拟内存区域，Linux需要直到它从哪里来和如何把它放到内存中，这样才可以处理这些page fault。

Linux核心需要管理所有的这些虚拟内存区域，每一个进程的虚拟内存的内容通过一个它的task_struct指向的一个mm_struct　mm_struc数据结构描述。该进程的mm_struct数据结构也包括加载的执行映像的信息和进程页表的指针。它包括了指向一组vm_area_struct数据结构的指针，每一个都表示该进程中的一个虚拟内存区域。

这个链接表按照虚拟内存顺序排序。图4.2显示了一个简单进程的虚拟内存分布和管理它的核心数据结构。因为这些虚拟内存区域来源不同，Linux通过vm_area_struct指向一组虚拟内存处理例程（通过vm_ops）的方式抽象了接口。这样进程的所有虚拟内存都可以用一种一致的方式处理，不管底层管理这块内存的服务如何不同。例如，会有一个通用的例程，在进程试图访问不存在的内存时调用，这就是page fault 的处理。

当Linux为一个进程创建新的虚拟内存区域和处理对于不在系统物理内存中的虚拟内存的引用时，反复引用进程的vm_area_struct数据结构列表。这意味着它查找正确的vm_area_struct数据结构所花的事件对于系统的性能十分重要。为了加速访问，Linux也把vm_area_struct数据结构放到一个AVL（Adelson-Velskii and Landis）树。对这个树进行安排使得每一个vm_area_struct（或节点）都有对相邻的vm_area_struct结构的一个左和一个右指针。左指针指向拥有较低起始虚拟地址的节点，右指针指向一个拥有较高起始虚拟地址的节点。为了找到正确的节点，Linux从树的根开始，跟从每一个节点的左和右指针，直到找到正确的vm_area_struct。当然，在这个树中间释放不需要时间，而插入新的vm_area_struct需要额外的处理时间。

当一个进程分配虚拟内存的时候，Linux并不为该进程保留物理内存。它通过一个新的vm_area_struct数据结构来描述这块虚拟内存，连接到进程的虚拟内存列表中。当进程试图写这个新的虚拟内存区域的时候，系统会发生page fault。处理器试图解码这个虚拟地址，但是没有对应该内存的页表条目，它会放弃并产生一个page fault异常，让Linux核心处理。Linux检查这个引用的虚拟地址是不是在进程的虚拟地址空间， 如果是，Linux创建适当的PTE并为该进程分配物理内存页。也许需要从文件系统或者交换磁盘中加载相应的代码或者数据，然后进程从引起page fault的指令重新运行，因为这次该内存实际存在，可以继续。

4.6 Creating a Process（创建一个进程）

当系统启动的时候它运行在核心态，这时，只有一个进程：初始化进程。象所有其他进程一样，初始进程有一组用堆栈、寄存器等等表示的机器状态。当系统中的其他进程创建和运行的时候这些信息存在初始进程的task_struct数据结构中。在系统初始化结束的时候，初始进程启动一个核心线程（叫做init）然后执行空闲循环，什么也不做。当没有什么可以做的时候，调度程序会运行这个空闲的进程。这个空闲进程的task_struct是唯一一个不是动态分配而是在核心连接的时候静态定义的，为了不至于混淆，叫做init_task。

Init核心线程或进程拥有进程标识符1，是系统的第一个真正的进程。它执行系统的一些初始化的设置（比如打开系统控制它，安装根文件系统），然后执行系统初始化程序。依赖于你的系统，可能是/etc/init，/bin/init或/sbin/init其中之一。Init程序使用/etc/inittab作为脚本文件创建系统中的新进程。这些新进程自身可能创建新的进程。例如：getty进程可能会在用户试图登录的时候创建一个login的进程。系统中的所有进程都是init核心线程的后代。

新的进程的创建是通过克隆旧的进程，或者说克隆当前的进程来实现的。一个新的任务是通过系统调用创建的（fork或clone），克隆发生在核心的核心态。在系统调用的最后，产生一个新的进程，等待调度程序选择它运行。从系统的物理内存中为这个克隆进程的堆栈（用户和核心）分配一个或多个物理的页用于新的task_struct数据结构。一个进程标识符将会创建，在系统的进程标识符组中是唯一的。但是，也可能克隆的进程保留它的父进程的进程标识符。新的task_struct进入了task 向量表中，旧的（当前的）进程的task_struct的内容拷贝到了克隆的task_struct。

参见kernel/fork.c do_fork()

克隆进程的时候，Linux允许两个进程共享资源而不是拥有不同的拷贝。包括进程的文件，信号处理和虚拟内存。共享这些资源的时候，它们相应的count字段相应增减，这样Linux不会释放这些资源直到两个进程都停止使用。例如，如果克隆的进程要共享虚拟内存，它的task_struct会包括一个指向原来进程的mm_struct的指针，mm_struct的count域增加，表示当前共享它的进程数目。

克隆一个进程的虚拟内存要求相当的技术。必须产生一组vm_area_struct数据结构、相应的mm_struct数据结构和克隆进程的页表，这时没有拷贝进程的虚拟内存。这会是困难和耗时的任务，因为一部分虚拟内存可能在物理内存中而另一部分可能在交换文件中。替代底，Linux使用了叫做“copy on write”的技术，即只有两个进程中的一个试图写的时候才拷贝虚拟内存。任何不写入的虚拟内存，甚至可能写的，都可以在两个进程之间共享二部会有什么害处。只读的内存，例如执行代码，可以共享。为了实现“copy on write”，可写的区域的页表条目标记为只读，而描述它的vm_area_struct数据结构标记为“copy on write”。当一个进程试图写向着这个虚拟内存的时候会产生page fault。这时Linux将会制作这块内存的一份拷贝并处理两个进程的页表和虚拟内存的数据结构。

7. Times and Timer（时间和计时器）

　

核心跟踪进程的CPU时间和其他一些时间。每一个时钟周期，核心更新当前进程的jiffies来表示在系统和用户态下花费的时间总和。

　

除了这些记账的计时器，Linux还支持进程指定的间隔计时器（interval timer）。进程可以使用这些计时器在这些计时器到期的时候发送给自身信号。支持三种间隔计时器：

参见kernel/itimer.c

　

Real 这个计时器使用实时计时，当计时器到期，发送给进程一个SIGALRM信号。

Virtual 这个计时器只在进程运行的时候计时，到期的时候，发送给进程一个SIGVTALARM信号。

Profile 在进程运行的时候和系统代表进程执行的时候都及时。到期的时候，会发送SIGPROF信号。

　

可以运行一个或者所有的间隔计时器，Linux在进程的task_struct数据结构中记录所有的必要信息。可以使用系统调用建立这些间隔计时器，启动、停止它们，读取当前的数值。虚拟和profile计时器的处理方式相同：每一次时钟周期，当前进程的计时器递减，如果到期，就发出适当的信号

参见kernel/sched.c do_it_virtual()， do_it_prof()

　

实时间隔计时器稍微不同。Linux使用计时器的机制在第11章描述。每一个进程都有自己的timer_list数据结构，当时使用实时计时器的时候，使用系统的timer表。当它到期的时候，计时器后半部分处理把它从队列中删除并调用间隔计时器处理程序。它产生SIGALRM信号并重启动间隔计时器，把它加回到系统计时器队列。

参见：kernel/iterm.c it_real_fn()

　

8. Executing Programs （执行程序）

　

在Linux中，象Unix一样，程序和命令通常通过命令解释器执行。命令解释程序是和其他进程一样的用户进程，叫做shell（想象一个坚果，把核心作为中间可食的部分，而shell包围着它，提供一个接口）。Linux中有许多shell，最常用的是sh、bash和tcsh。除了一些内部命令之外，比如cd和pwd，命令是可执行的二进制文件。对于输入的每一个命令，shell在当前进程的搜索路径指定的目录中（放在PATH环境变量）查找匹配的名字。如果找到了文件，就加载并运行。Shell用上述的fork机制克隆自身，并在子进程中用找到的执行映像文件的内容替换它正在执行的二进制映像（shell）。通常shell等待命令结束，或者说子进程退出。你可以通过输入control-Z发送一个SIGSTOP信号给子进程，把子进程停止并放到后台，让shell重新运行。你可以使用shell命令bg让shell向子进程发送SIGCONT信号，把子进程放到后台并重新运行，它会持续运行直到它结束或者需要从终端输入或输出。

　



执行文件可以由许多格式甚至可以是一个脚本文件（script file）。脚本文件必须用合适的解释程序识别并运行。例如/bin/sh解释shell script。可执行的目标文件包括了执行代码和数据以及足够的其他信息，时的操作系统可以把它们加载到内存中并执行。Linux中最常用的目标文件类型是ELF，而理论上，Linux灵活到足以处理几乎所有的目标文件格式。

好像文件系统一样，Linux可以支持的二进制格式也是在核心连接的时候直接建立在核心的或者是可以作为模块加载的。核心保存了支持的二进制格式（见图4.3）的列表，当试图执行一个文件的时候，每一个二进制格式都被尝试，直到可以工作。通常，Linux支持的二进制文件是a.out和ELF。可执行文件不需要完全读入内存，而使用叫做demand loading的技术。当进程使用执行映像的一部分的时候它才被调入内存，未被使用的映像可以从内存中废弃。

参见fs/exec.c do_execve()

　



1. ELF

　

ELF（Executable and Linkable Format 可执行可连接格式）目标文件，由Unix系统实验室设计，现在成为Linux最常用的格式。虽然和其他目标文件格式比如ECOFF和a.out相比，有性能上的轻微开支，ELF感觉更灵活。ELF可执行文件包括可执行代码（有时叫做text）和数据（data）。执行映像中的表描述了程序应该如何放到进程的虚拟内存中。静态连接的映像是用连接程序（ld）或者连接编辑器创建的，单一的映像中包括了运行该映像所需要的所有的代码和数据。这个映像也描述了该映像在内存中的布局和要执行的第一部分代码在映像中的地址。

　

图4.4象是了静态连接的ELF可执行映像的布局。这是个简单的C程序，打印“hello world”然后退出。头文件描述了它是一个ELF映像，有两个物理头（e_phnum是2），从映像文件的开头第52字节开始（e_phoff）。第一个物理头描述映像中的执行代码，在虚拟地址0x8048000，有65532字节。因为它是静态连接的，所以包括输出“hello world”的调用printf（）的所有的库代码。映像的入口，即程序的第一条指令，不是位于映像的起始位置，而在虚拟地址0x8048090（e_entry）。代码紧接着在第二物理头后面开始。这个物理头描述了程序的数据，将会加载到虚拟内存地址0x8059BB8。这块数据可以读写。你会注意到文件中数据的大小是2200字节（p_filesz）而在内存中的大小是4248字节。因为前2200字节包括预先初始化的数据，而接着的2048字节包括会被执行代码初始化的数据。

参见include/linux/elf.h

　

当Linux把ELF可执行映像加载到进程的虚拟地址空间的时候，它不是实际的加载映像。它设置虚拟内存数据结构，即进程的vm_area_struct和它的页表。当程序执行了page fault的时候，程序的代码和数据会被放到物理内存中。没有用到的程序部分将不会被放到内存中。一旦ELF 二进制格式加载程序满足条件，映像是一个有效的ELF可执行映像，它把进程的当前可执行映像从它的虚拟内存中清除。因为这个进程是个克隆的映像（所有的进程都是），旧的映像是父进程执行的程序的映像（例如命令解释程序shell bash）。清除旧的可执行映像会废弃旧的虚拟内存的数据结构，重置进程的页表。它也会清除设置的其他信号处理程序，关闭打开的文件。在清除过程的最后，进程准备运行新的可执行映像。不管可执行映像的格式如何，进程的mm_struct中都要设置相同的信息。包括指向映像中代码和数据起始的指针。这些数值从ELF可执行映像的物理头中读入，它们描述的部分也被映射到了进程的虚拟地址空间。这也发生在进程的vm_area_struct数据结构建立和页表修改的时候。mm_struct数据结构中也包括指针，指向传递给程序的参数和进程的环境变量。

　

ELF Shared Libraries（ELF共享库）

　

动态连接的映像，反过来，不包含运行所需的所有的代码和数据。其中一些放在共享库并在运行的时候连接到映像中。当运行时动态库连接到映像中的时候，动态连接程序（dynamic linker）也要使用ELF共享库的表。Linux使用几个动态连接程序，ld.so.1，libc.so.1和ld-linux.so.1，都在/lib目录下。这些库包括通用的代码，比如语言子例程。如果没有动态连接，所有的程序都必须有这些库的独立拷贝，需要更多的磁盘空间和虚拟内存。在动态连接的情况下，ELF映像的表中包括引用的所有库例程的信息。这些信息指示动态连接程序如何定位库例程以及如何连接到程序的地址空间。

　

2. Scripts Files

脚本文件是需要解释器才能运行的可执行文件。Linux下有大量的解释器，例如wish、perl和命令解释程序比如tcsh。Linux使用标准的Unix约定，在脚本文件的第一行包括解释程序的名字。所以一个典型的脚本文件可能开头是：

脚本文件加载器试图找出文件所用的解释程序。它试图打开脚本文件第一行指定的可执行文件。如果可以打开，就得到一个指向该文件的VFS I 节点的指针，然后执行它去解释脚本文件。脚本文件的名字成为了参数0（第一个参数），所有的其他参数都向上移动一位（原来的第一个参数成为了第二个参数等等）。加载解释程序和Linux加载其他可执行程序一样。Linux依次尝试各种二进制格式，直到可以工作。这意味着理论上你可以把几种解释程序和二进制格式堆积起来，让Linux的二进制格式处理程序更加灵活。

参见fs/binfmt_script.c do_load_script()

Interprocess Communication Mechanisms（进程间通讯机制）

进程之间互相通讯并和核心通讯，协调它们的行为。Linux支持一些进程间通讯（IPC）的机制。信号和管道是其中的两种，Linux还支持系统V IPC（用首次出现的Unix的版本命名）的机制。

5.1 Signals（信号）

信号是Unix系统中使用的最古老的进程间通讯的方法之一。用于向一个或多个进程发送异步事件的信号。信号可以用键盘终端产生，或者通过一个错误条件产生，比如进程试图访问它的虚拟内存中不存在的位置。Shell也使用信号向它的子进程发送作业控制信号。

有一些信号有核心产生，另一些可以由系统中其他有权限的进程产生。你可以使用kill命令（kill –l）列出你的系统的信号集，在我的Linux Intel系统输出：

在Alpha AXP Linux系统上编号不同。进程可以选择忽略产生的大多数信号，有两个例外：SIGSTOP（让进程停止执行）和SIGKILL（让进程退出）不可以忽略，虽然进程可以选择它如何处理信号。进程可以阻塞信号，如果它不阻塞信号，它可以选择自己处理或者让核心处理。如果核心处理，将会执行该信号的缺省行为。例如，进程接收到SIGFPE（浮点意外）的缺省动作是产生core并退出。信号没有固有的优先级，如果一个进程同时产生了两个信号，它们会以任意顺序出现在进程中并按任意顺序处理。另外，也没有机制可以处理统一种类的多个信号。进程无法知道它接收了1还是42个SIGCONT信号。

Linux用进程的task_struct中存放的信息来实现信号机制。支持的信号受限于处理器的字长。32位字长的处理器可以有32中信号，而64位的处理器，比如Alpha AXP可以有多达64种信号。当前待处理的信号放在signal域，blocked域放着要阻塞的信号掩码。除了SIGSTOP和SIGKILL，所有的信号都可以被阻塞。如果产生了一个被阻塞的信号，它一直保留待处理，直到被解除阻塞。Linux也保存每一个进程如何处理每一种可能的信号的信息，这些信息放在一个sigaction的数据结构数组中，每一个进程的task_struct都有指针指向对应的数组。这个数组中包括处理这个信号的例程的地址，或者包括一个标志，告诉Linux该进程是希望忽略这个信号还是让核心处理。进程通过执行系统调用改变缺省的信号处理，这些调用改变适当的信号的sigaction和阻塞的掩码。

并非系统中所有的进程都可以向其他每一个进程发送信号，只有核心和超级用户可以。普通进程只可以向拥有相同uid和gid或者在相同进程组的进程发送信号。通过设置task——struct的signal中适当的位产生信号。如果进程不阻塞信号，而且正在等待但是可以中断（状态是Interruptible），那么它的状态被改为Running并确认它在运行队列，通过这种方式把它唤醒。这样调度程序在系统下次调度的时候会把它当作一个运行的候选。如果需要缺省的处理，Linux可以优化信号的处理。例如如果信号SIGWINCH（X window改变焦点）发生而使用缺省的处理程序，则不需要做什么事情。

信号产生的时候不会立刻出现在进程中，它们必须等到进程下次运行。每一次进程从系统调用中退出的时候都要检查它的signal和blocked域，如果有任何没有阻塞的信号，就可以发送。这看起来好像非常不可靠，但是系统中的每一个进程都在调用系统调用，比如向终端写一个字符的过程中。如果愿意，进程可以选择等待信号，它们挂起在Interruptible状态，直到有了一个信号。Linux信号处理代码检查sigaction结构中每一个当前未阻塞的信号。

如果信号处理程序设置为缺省动作，则核心会处理它。SIGSTOP信号的缺省处理是把当前进程的状态改为Stopped，然后运行调度程序，选择一个新的进程来运行。SIGFPE信号的缺省动作是让当前进程产生core（core dump），让它退出。变通地，进程可以指定自己的信号处理程序。这是一个例程，当信号产生的时候调用而且sigaction结构包括这个例程的地址。Linux必须调用进程的信号处理例程，至于具体如何发生是和处理器相关。但是，所有的CPU必须处理的是当前进程正运行在核心态，并正准备返回到调用核心或系统例程的用户态的进程。解决这个问题的方法是处理该进程的堆栈和寄存器。进程程序计数器设为它的信号处理程序的地址，例程的参数加到调用结构或者通过寄存器传递。当进程恢复运行的时候显得信号处理程序是正常的调用。

Linux是POSIX兼容的，所以进程可以指定调用特定的信号处理程序的时候要阻塞的信号。这意味着在调用进程的信号处理程序的时候改变blocked掩码。信号处理程序结束的时候，blocked掩码必须恢复到它的初始值。因此，Linux在收到信号的进程的堆栈中增加了对于一个整理例程的调用，把blocked掩码恢复到初始值。Linux也优化了这种情况：如果同时几个信号处理例程需要调用的时候，就在它们堆积在一起，每次退出一个处理例程的时候就调用下一个，直到最后才调用整理例程。

5.2 Pipes（管道）

普通的Linux shell都允许重定向。例如：

把列出目录文件的命令ls的输出通过管道接到pr命令的标准输入上进行分页。最后，pr命令的标准输出通过管道连接到lpr命令的标准输入上，在缺省打印机上打印出结果。管道是单向的字节流，把一个进程的标准输出和另一个进程的标准输入连接在一起。没有一个进程意识到这种重定向，和它平常一样工作。是shell建立了进程之间的临时管道。在Linux中，使用指向同一个临时VFS I节点（本身指向内存中的一个物理页）的两个file数据结构来实现管道。图5.1显示了每一个file数据结构包含了不同的文件操作例程的向量表的指针：一个用于写，另一个从管道中读。这掩盖了和通用的读写普通文件的系统调用的不同。当写进程向管道中写的时候，字节拷贝到了共享的数据页，当从管道中读的时候，字节从共享页中拷贝出来。Linux必须同步对于管道的访问。必须保证管道的写和读步调一致，它使用锁、等待队列和信号（locks，wait queues and signals）。

参见include/linux/inode_fs.h

当写进程向管道写的时候，它使用标准的write库函数。这些库函数传递的文件描述符是进程的file数据结构组中的索引，每一个都表示一个打开的文件，在这种情况下，是打开的管道。Linux系统调用使用描述这个管道的file数据结构指向的write例程。这个write例程使用表示管道的VFS I 节点存放的信息，来管理写的请求。如果有足够的空间把所有的字节都写导管到中，只要管道没有被读进程锁定，Linux为写进程上锁，并把字节从进程的地址空间拷贝到共享的数据页。如果管道被读进程锁定或者空间不够，当前进程睡眠，并放在管道I节点的等待队列中，并调用调度程序，运行另外一个进程。它是可以中断的，所以它可以接收信号。当管道中有了足够的空间写数据或者锁定解除，写进程就会被读进程唤醒。当数据写完之后，管道的VFS I 节点锁定解除，管道I节点的等待队列中的所有读进程都会被唤醒。

参见fs/pipe.c pipe_write()

从管道中读取数据和写数据非常相似。进程允许进行非阻塞的读（依赖于它们打开文件或者管道的模式），这时，如果没有数据可读或者管道被锁定，会返回一个错误。这意味着进程会继续运行。另一种方式是在管道的I节点的等待队列中等待，直到写进程完成。如果管道的进程都完成了操作，管道的I节点和相应的共享数据页被废弃。

参见fs/pipe.c pipe_read()

Linux也可以支持命名管道，也叫FIFO，因为管道工作在先入先出的原则下。首先写入管道的数据是首先被读出的数据。不想管道，FIFO不是临时的对象，它们是文件系统中的实体，可以用mkfifo命令创建。只要有合适的访问权限，进程就可以使用FIFO。FIFO的大开方式和管道稍微不同。一个管道（它的两个file数据结构，VFS I节点和共享的数据页）是一次性创建的，而FIFO是已经存在，可以由它的用户打开和关闭的。Linux必须处理在写进程打开FIFO之前打开FIFO读的进程，以及在写进程写数据之前读的进程。除了这些，FIFO几乎和管道的处理完全一样，而且它们使用一样的数据结构和操作。

3. Sockets

　

注意：写网络篇的时候加上去

　

1. System V IPC mechanisms （系统V IPC机制）

　

Linux支持三种首次出现在Unix 系统V（1983）的进程间通讯的机制：消息队列、信号灯和共享内存（message queues， semaphores and shared memory）。系统V IPC机制共享通用的认证方式。进程只能通过系统调用，传递一个唯一的引用标识符到核心来访问这些资源。对于系统V IPC对象的访问的检查使用访问许可权，很象对于文件访问的检查。对于系统V IPC对象的访问权限由对象的创建者通过系统调用创建。每一种机制都使用对象的引用标识符作为资源表的索引。这不是直接的索引，需要一些操作来产生索引。

　

系统中表达系统V IPC对象的所有Linux数据结构都包括一个ipc_perm的数据结构，包括了创建进程的用户和组标识符，对于这个对象的访问模式（属主、组和其他）和IPC对象的key。Key 用作定位系统V IPC对象的引用标识符的方法。支持两种key：公开和四有的。如果key是公开的,那么系统中的任何进程,只要通过了权限检查,就可以找到对应的系统V IPC对象的引用标识符。系统V IPC对象不能使用key引用，必须使用它们的引用标识符。

参见include/linux/ipc.h

　

2. Message Queues（消息队列）

　

消息队列允许一个或多个进程写消息，一个或多个进程读取消息。Linux维护了一系列消息队列的msgque 向量表。其中的每一个单元都指向一个msqid_ds的数据结构，完整描述这个消息队列。当创建消息队列的时候，从系统内存中分配一个新的msqid_ds的数据结构并插入到向量表中

　

每一个msqid_ds数据结构都包括一个ipc_perm的数据结构和进入这个队列的消息的指针。另外，Linux保留队列的改动时间，例如上次队列写的时间等。Msqid_ds队列也包括两个等待队列：一个用于向消息队列写，另一个用于读。

参见include/linux/msg.h



每一次一个进程试图向写队列写消息，它的有效用户和组的标识符就要和队列的ipc_perm数据结构的模式比较。如果进程可以想这个队列写，则消息会从进程的地址空间写到msg数据结构，放到消息队列的最后。每一个消息都带有进程间约定的，应用程序指定类型的标记。但是，因为Linux限制了可以写的消息的数量和长度，可能会没有空间容纳消息。这时，进程会被放到消息队列的写等待队列，然后调用调度程序选择一个新的进程运行。当一个或多个消息从这个消息队列中读出去的时候会被唤醒。

　

从队列中读是一个相似的过程。进程的访问权限一样被检查。一个读进程可以选择是不管消息的类型从队列中读取第一条消息还是选择特殊类型的消息。如果没有符合条件的消息，读进程会被加到消息队列的读等待进程，然后运行调度程序。当一个新的消息写到队列的时候，这个进程会被唤醒，继续运行。

　

3. Semaphores（信号灯）

　

信号灯最简单的形式就是内存中一个位置，它的取值可以由多个进程检验和设置。检验和设置的操作，至少对于关联的每一个进程来讲，是不可中断或者说有原子性：只要启动就不能中止。检验和设置操作的结果是信号灯当前值和设置值的和，可以是正或者负。根据测试和设置操作的结果，一个进程可能必须睡眠直到信号灯的值被另一个进程改变。信号灯可以用于实现重要区域（critical regions），就是重要的代码区，同一时刻只能有一个进程运行。

　

比如你有许多协作的进程从一个单一的数据文件读写记录。你可能希望对文件的访问必须严格地协调。你可以使用一个信号灯，初始值1，在文件操作的代码中，加入两个信号灯操作，第一个检查并把信号灯的值减小，第二个检查并增加它。访问文件的第一个进程试图减小信号灯的数值，如果成功，信号灯的取值成为0。这个进程现在可以继续运行并使用数据文件。但是，如果另一个进程需要使用这个文件，现在它试图减少信号灯的数值，它会失败因为结果会是-1。这个进程会被挂起直到第一个进程处理完数据文件。当第一个进程处理完数据文件，它会增加信号灯的数值成为1。现在等待进程会被唤醒，这次它减小信号灯的尝试会成功。

　



　

每一个系统V IPC信号灯对象都描述了一个信号灯数组，Linux使用semid_ds数据结构表达它。系统中所有的semid_ds数据结构都由semary指针向量表指向。每一个信号灯数组中都有sem_nsems，通过sem_base指向的一个sem数据结构来描述。所有允许操作一个系统V IPC信号灯对象的信号灯数组的进程都可以通过系统调用对它们操作。系统调用可以指定多种操作，每一种操作多用三个输入描述：信号灯索引、操作值和一组标志。信号灯索引是信号灯数组的索引，操作值是要增加到当前信号灯取值的数值。首先，Linux检查所有的操作是否成功。只有操作数加上信号灯的当前值大于0或者操作值和信号灯的当前值都是0，操作才算成功。如果任意信号灯操作失败，只要操作标记不要求系统调用无阻塞，Linux会挂起这个进程。如果进程要挂起，Linux必须保存要进行的信号灯操作的状态并把当前进程放到等待队列重。它通过在堆栈中建立一个sem_queue的数据结构并填满它来实现上述过程。这个新的sem_queue数据结构被放到了这个信号灯对象的等待队列的结尾（使用sem_pending和sem_pending_last指针）。当前进程被放到了这个sem_queue数据结构的等待队列中（sleeper），调用调度程序，运行另外一个进程。

参见include/linux/sem.h

如果所有的信号灯操作都成功，当前的进程就不需要被挂起。Linux继续向前并把这些操作应用到信号灯数组的合适的成员上。现在Linux必须检查任何睡眠或者挂起的进程，它们的操作现在可能可以实施。Linux顺序查找操作等待队列（sem_pending）中的每一个成员，检查现在它的信号灯操作是否可以成功。如果可以它就把这个sem_queue数据结构从操作等待表中删除，并把这种信号灯操作应用到信号灯数组。它唤醒睡眠的进程，让它在下次调度程序运行的时候可以继续运行。Linux从头到尾检查等待队列，直到不能执行信号灯操作无法唤醒更多的进程为止。

　

在信号灯操作中有一个问题：死锁（deadlock）。这发生在一个进程改变了信号灯的值进入一个重要区域（critical region）但是因为崩溃或者被kill而没有离开这个重要区域的情况下。Linux通过维护信号灯数组的调整表来避免这种情况。就是如果实施这些调整，信号灯就会返回一个进程的信号灯操作前的状态。这些调整放在sem_undo数据结构中，排在sem_ds数据结构的队列中，同时排在使用这些信号灯的进程的task_struct数据结构的队列中。

　

每一个独立的信号灯操作可能都需要维护一个调整动作。Linux至少为每一个进程的每一个信号灯数组都维护一个sem_undo的数据结构。如果请求的进程没有，就在需要的时候为它创建一个。这个新的sem_undo数据结构同时在进程的task_struct数据结构和信号灯队列的semid_ds数据结构的队列中排队。对信号灯队列中的信号灯执行操作的时候，和这个操作值相抵消的值加到这个进程的sem_undo数据结构的调整队列这个信号灯的条目上。所以，如果操作值为2，那么这个就在这个信号灯的调整条目上增加-2。

　

当进程被删除，比如退出的时候，Linux遍历它的sem_undo数据结构组，并实施对于信号灯数组的调整。如果删除信号灯，它的sem_undo数据结构仍旧停留在进程的task_struct队列中，但是相应的信号灯数组标识符标记为无效。这种情况下，清除信号灯的代码只是简单地废弃这个sem_undo数据结构。

　

4. Shared Memory（共享内存）

共享内存允许一个或多个进程通过同时出现在它们的虚拟地址空间的内存通讯。这块虚拟内存的页面在每一个共享进程的页表中都有页表条目引用。但是不需要在所有进程的虚拟内存都有相同的地址。象所有的系统V IPC对象一样，对于共享内存区域的访问通过key控制，并进行访问权限检查。内存共享之后，就不再检查进程如何使用这块内存。它们必须依赖于其他机制，比如系统V的信号灯来同步对于内存的访问。

每一个新创建的内存区域都用一个shmid_ds数据结构来表达。这些数据结构保存在shm_segs向量表中。Shmid_ds数据结构描述了这个共享内存取有多大、多少个进程在使用它以及共享内存如何映射到它们的地址空间。由共享内存的创建者来控制对于这块内存的访问权限和它的key是公开或私有。如果有足够的权限它也可以把共享内存锁定在物理内存中。

参见include/linux/sem.h

每一个希望共享这块内存的进程必须通过系统调用粘附（attach）到虚拟内存。这为该进程创建了一个新的描述这块共享内存的vm_area_struct数据结构。进程可以选择共享内存在它的虚拟地址空间的位置或者由Linux选择一块足够的的空闲区域。

这个新的vm_area_struct结构放在由shmid_ds指向的vm_area_struct列表中。通过vm_next_shared和vm_prev_shared把它们连在一起。虚拟内存在粘附的时候其实并没有创建，而发生在第一个进程试图访问它的时候。

在一个进程第一次访问共享虚拟内存的其中一页的时候，发生一个page fault。当Linux处理这个page fault的时候，它找到描述它的vm_area_struct数据结构。这里包含了这类共享虚拟内存的处理例程的指针。共享内存的page fault处理代码在这个shmid_ds的页表条目列表中查找，看是否存在这个共享虚拟内存页的条目。如果不存在，它就分配一个物理页，并为它创建一个页表条目。这个条目不但进入当前进程的页表，也存到这个shmid_ds。这意味着当下一个进程试图访问这块内存并得到一个page fault的时候，共享内存错误处理代码也会让这个进程使用这个新创建的物理页。所以，是第一个访问共享内存页的进程使得这一页被创建，而随后访问的其他进程使得此页被加到它们的虚拟地址空间。

当进程不再需要共享虚拟内存的时候，它们从中分离（detach）出来。只要仍旧有其他进程在使用这块内存，这种分离只是影响当前的进程。它的vm_area_struct从shmid_ds数据结构中删除，并释放。当前进程的页表也进行更新，使它共享过的虚拟内存区域无效。当共享这块内存的最后一个进程从中分离出的时候，共享内存当前在物理内存中的页被释放，这块共享内存的shmid_ds数据结构也被释放。

如果共享的虚拟内存没有被锁定在物理内存中的话会更加复杂。在这种情况下，共享内存的页可能在系统大量使用内存的时候交换到了系统的交换磁盘。共享内存如何交换初和交换入物理内存在第3章中有描述。

Peripheral Component Interconnect（PCI），好像它的名字暗示的一样，是描述如何通过一个结构化和可控制的方式把系统中的外设组件连接起来的一个标准。标准的PCI Local Bus规范描述了系统组件电气连接的方法和它们行为的方法。本章探讨Linux核心如何初始化系统的PCI总线和设备。

图6.1是一个PCI基础的系统的逻辑图。PCI总线和PCI-PCI桥（bridge）是系统组件联系在一起的粘合剂。CUP和video设备连在主要的PCI总线，PCI总线0。一个特殊的PCI设备，PCI-PCI桥把主总线连接到次PCI总线，PCI总线1。按照PCI规范的术语，PCI总线1描述成为PCI-PCI桥的下游而PCI总线0是桥的上游。连接在次PCI总线上的是系统的SCSI和以太网设备。物理上桥、次要PCI总线和这两种设备可以在同一块PCI卡上。系统中的PCI-ISA桥支持老的、遗留的ISA设备，本图显示了一个超级I/O控制芯片，控制键盘、鼠标和软驱。

6.1 PCI Address Space（PCI地址空间）

CPU和PCI设备需要访问它们所共享的内存。这些内存让设备驱动程序控制这些PCI设备并在它们之间传递信息。一般地共享的内存包括设备的控制和状态寄存器。这些寄存器用于控制设备和读取它的状态。例如：PCI SCSI设备驱动程序可以读取SCSI设备的状态寄存器，判断它是否可以向SCSI磁盘写一块信息。或者它可以写入控制寄存器让它关闭的设备开始运行。

CPU的使用的系统内存可以用作这种共享内存，但是如果这样的话，每一次PCI设备访问内存，CPU都不得不停顿，等待PCI设备完成。对于内存的访问通常有限制，同一时间只能有一个系统组件允许访问。这会使得系统速度降低。允许系统的外部设备在一个不受控的方式下访问主内存也不是一个好主意。这会非常危险：一个恶意的设备会让系统非常不稳定。

外部设备由它们自己的内存空间。CPU可以访问这些空间，但是设备对于系统内存的访问受到严格的控制，必须通过DMA（Direct Memory Access直接内存存取）通道。ISA设备可以访问两种地址空间：ISA I/O（输入/输出）和ISA内存。PCI由三中：PCI I/O、PCI内存和PCI配置空间（configuration space）。CPU可以访问所有的地址空间其中PCI I/O和PCI内存地址空间由设备驱动程序使用而PCI配置空间由Linux和心中的PCI初始化代码使用。

Alpha AXP处理器没有对于除了系统地址空间之外的地址空间的天生的访问模式。它需要使用支持芯片来访问象PCI配置空间这样的其他地址空间。它使用了一个地址空间的映射方案，从巨大的虚拟地址空间中偷出一部分映射到PCI地址空间。

6.2 PCI Configuration Headers（PCI配置头）

系统中的每一个PCI设备，包括PCI-PCI桥都由一个配置数据结构，位于PCI配置地址空间中。PCI配置头允许系统识别和控制设备。这个头位于PCI配置地址空间的确切位置依赖于设备使用的PCI拓扑。例如，插在PC主板一个PCI槽位的一个PCI显示卡配置头会在一个位置，而如果它被插到另一个PCI槽位则它的头会出现在PCI配置内存中的另一个位置。但是不管这些PCI设备和桥在什么位置，系统都可以发现并使用它们配置头中的状态和配置寄存器来配置它们。

通常，系统的设计使得每一个PCI槽位的PCI配置头都有一个和它在板上的槽位相关的偏移量。所以，举例来说，板上的第一个槽位的PCI配置可能位于偏移0而第二个槽位的在偏移256（所有的头都一样长度，256字节），依此类推。定义了系统相关的硬件机制使得PCI配置代码可以尝试检查一个给定的PCI总线上的所有可能的PCI配置头，试图读取头中的一个域（通常是Vendor Identification 域）得到一些错误，从而知道那些设备存在而那些设备不存在。PCI Local Bus规范描述了一种可能的错误信息：试图读取一个空的PCI槽位的Verdor Identification和Device Indentification域时候返回0xFFFFFFFF。

图6.2显示了256字节的PCI配置头的布局。它包括以下域：

参见include/linux/pci.h

Vendor Identification 唯一的数字，描述这个PCI设备的发明者。Digital的PCI Vendor Identification 是0x1011而Intel是0x8086。

Device Identification 描述设备自身的唯一数字。例如Digital的21141快速以太网设备的设备标识符是0x0009。

Status 此域给除了设备的状态，它的位的含义由PCI Local Bus规范规定。

Command 系统通过写这个域控制这个设备。例如：允许设备访问PCI I/O内存。

Class Code 标识了设备的类型。对于每一种设备都有标准分类：显示、SCSI等等。对于SCSI的类型编码是0x0100。

Base Address Registers 这些寄存器用于确定和分配设备可以使用的PCI I/O和PCI内存的类型、大小和位置。

Interrupt Pin PCI卡的物理管脚中的4个用于向PCI总线传递中断。标准中把它们标记为A、B、C和D。Interrupt Pin域描述了这个PCI设备使用那个管脚。通常对于一个设备来说这时硬件决定的。就是说每一次系统启动的时候，这个设备都使用同一个中断管脚。这些信息允许中断处理子系统管理这些设备的中断。

Interrupt Line PCI配置头中的Interrupt Line域用于在PCI初始化代码、设备驱动程序和Linux的中断处理子系统之间传递中断控制。写在这里的数字对于设备驱动程序来讲是没有意义的，但是它可以让中断处理程序正确地把一个中断从PCI设备发送到Linux操作系统中正确的设备驱动程序的中断处理代码处。Linux如何处理中断参看第7章。

6.3 PCI I/O and PCI Memory Address（PCI I/O和PCI内存地址）

这两种地址空间用于设备和CPU上运行的Linux核心的它们的设备驱动程序通讯。例如：DECchip 21141快速以太网设备把它的内部寄存器映射到了PCI I/O空间。然后它的Linux设备驱动程序通过读写这些寄存器来控制设备。显示驱动程序通常使用大量的PCI内存空间来放置显示信息。

直到PCI系统建立起来并使用PCI配置头中的Command域打开了设备对于这些地址空间的访问为止，设备都无法访问这些空间。应该注意的是只有PCI配置代码读写PCI配置地址，Linux的设备驱动程序只是读写PCI I/O和PCI内存地址。

6.4 PCI-ISA Bridges（PCI-ISA桥）

这种桥把对于PCI I/O和PCI内存地址空间的访问转换成为ISA I/O和ISA内存访问，用来支持ISA设备。现在销售的多数系统都包括几个ISA总线插槽和几个PCI总线插槽。这种向后的兼容的需要会不断减少，将来会有只有PCI的系统。在早期的Intel 8080基础的PC时代，系统中的ISA设备的ISA 地址空间（I/O和内存）就被固定下来。甚至一个S5000 Alpha AXP基础的计算机系统的ISA软驱驱动器的ISA I/O地址也会和第一台IBM PC一样。PCI规范保留了PCI I/O和PCI内存的地址空间中的较低的区域保留给系统中的ISA外设并使用一个PCI-ISA桥把所有对于这些区域的PCI内存访问转换为ISA访问。

6.5 PCI-PCI Bridges（PCI-PCI桥）

PCI-PCI桥是特殊的PCI设备，把系统中的PCI总线粘和在一起。简单系统中只有一个PCI总线，当时单个PCI总线可以支持的PCI设备的数量有电气限制。使用PCI-PCI桥增加更多的PCI总线允许系统支持更多的PCI设备。这对于高性能的服务器尤其重要。当然，Linux完全支持使用PCI-PCI桥的使用。

PCI-PCI桥只向下游传递对于PCI I/O和PCI内存读和写的一个子集。例如在图6.1中，只有读和写的地址属于SCSI或者以太网设备的时候PCI-PCI桥才会把读写的地址从PCI总线0传递到总线1，其余的都被忽略。这种过滤阻止了不必要的地址信息遍历系统。为了达到这个目的，PCI-PCI桥必须编程设置它们必须从主总线向次总线通过的PCI I/O和PCI内存地址空间访问的基础（base）和限制。一旦系统中的PCI-PCI桥设置好，只要Linux设备驱动程序只是通过这些窗口存取PCI I/O和PCI内存空间，PCI-PCI桥是不可见的。这是个重要的特性，使得Linux的PCI设备驱动程序的作者的日子好过了。但是它也让Linux下的PCI-PCI桥在一定程度上需要技巧才能配置，我们不久就会看到。

6.5.2 PCI-PCI Bridges: PCI Configuration Cycles and PCI Bus Numbering（PCI-PCI桥：PCI配置cycle和PCI总线编号）

既然CPU的PCI初始化代码可以定位不在主PCI总线上的设备，必须有一种机制使得桥可以决定是否把配置cycle从它的主接口传递到次接口上。一个cycle就是它显示在PCI总线上的地址。PCI规范定义了两种PCI地址配置格式：类型0和类型1，分别在图6.3和图6.4中显示。类型0的PCI配置cycle不包含总线号，被这个PCI总线上的所有的PCI设备解释用于PCI地址配置。配置cycle的位32：11看作是设备选择域。设计系统的一个方法是让每一个位选择一个不同的设备。这种情况下为11可能选择槽位0的PCI设备，位12选择槽位1的PCI设备，依此类推。另一种方法是把设备的槽位号直接写到位31：11中。一个系统使用哪一种机制依赖于系统的PCI内存控制器。

类型1的PCI配置cycle包括一个PCI总线号，这种配置循环被除了PCI-PCI桥之外的所有PCI设备忽略。所有看到了类型1的PCI配置cycle的PCI-PCI桥都可以把这些信息向它们的下游传送。一个PCI-PCI桥是否忽略PCI配置循环或者向它的下游传递，依赖于这个桥是如何配置的。每一个PCI-PCI桥都有一个主总线接口号和一个次总线接口号。主总线接口离CPU最近而次总线接口是离CPU最远的。每一个PCI-PCI桥都还有一个附属总线编号，这是在第二个总线接口之外可以桥接的最大的PCI总线数目。或者说，附属总线编号是PCI-PCI桥下游的最大的PCI总线编号。当PCI-PCI桥看到一个类型1的PCI配置cycle的时候，它做以下事情：

如果指定的总线编号和桥的次总线编号符合就把它转变成为类型0的配置命令

所以，如果我们希望寻址图6.9的拓扑中总线3上的设备1，我们必须从CPU生成一个类型1的配置命令。桥1不改变地传递到总线1，桥2忽略它但是桥3把它转换成一个类型0的配置命令，并把它发送到总线3，使设备1响应它。

每一个独立的操作系统负责在PCI配置阶段分配总线编号，但是不管使用哪一种编码方案，对于系统中所有的PCI-PCI桥，以下陈述都必须是正确的：

所有位于一个PCI-PCI桥后面的PCI总线的编码都必须在次总线编号和附属总线编号之间（包含）

如果违背了这条规则，则PCI-PCI桥将无法正确地传递和转换类型1的PCI配置cycle，系统无法成功地找到并初始化系统中的PCI设备。为了完成编码方案，Linux按照特定的顺序配置这些特殊设备。参看6.6.2节对于Linux PCI桥和总线编码方案的描述以及一个可以工作的例子。

6.6 Linux PCI Initialization（Linux PCI初始化过程）

Linux中PCI初始化代码分为三个逻辑部分：

PCI Device Driver 这个伪设备驱动程序从总线0开始查找PCI系统，定位系统中所有的PCI设备和桥。它建立一链接的数据结构的列表，描述系统的拓扑。另外，它还为系统中所有的桥编码。

参见drivers/pci/pci.c and include/linux/pci.h

PCI BIOS 这个软件层提供了PCI BIOS ROM规范中描述的服务。即使Alpha AXP没有BIOS服务，在Linux核心也有提供了相同的功能的等价代码。

参见arch/*/kernel/bios32.c

PCI Fixup 系统相关的整理代码，整理和系统相关的在PCI初始化最后的内存疏松的情况。

参见arch/*/kernel/bios32.c

6.6.1 Linux Kernel PCI Data Structures（Linux核心的PCI数据结构）

当Linux核心初始化PCI系统的时候它建立反映系统真实的PCI拓扑结构的数据结构。图6.5显示了数据结构之间的关系，它用来描述了图6.1中示例的PCI系统。

每一个PCI设备（包括PCI-PCI桥）都用一个pci_dev的数据结构描述。每一个PCI总线用一个pci_bus的数据结构描述。结果是一个PCI总线的树型结构，每一个总线上有粘附着一些子PCI设备。因为一个PCI总线只能通过PCI-PCI桥达到（除了主PCI总线，总线0），每一个pci_bus都包括一个它要通过的PCI设备的指针（这个PCI-PCI桥）。这个PCI设备是这个PCI总线的父总线的一个子设备。

图6.5中没有显示的还有一个指向系统中所有的PCI设备的指针：pci_devices。系统中所有的PCI设备的pci_dev的数据结构都排在这个队列中。Linux核心使用这个队列快速查找系统中所有的PCI设备。

6.6.2 The PCI Device Driver（PCI 设备驱动程序）

PCI设备驱动程序完全不是一个真正的设备驱动程序，只是系统初始化的时候操作系统调用的一个函数。PCI初始化代码必须扫描系统中所有的PCI总线，查找系统中所有的PCI设备（包括PCI-PCI桥接设备）。它使用PCI BIOS代码来查看它当前扫描的PCI总线上的每一个可能的槽位是否被占用。如果这个PCI槽位占用，它就建立一个描述这个设备的pci_dev数据结构，并把它链接到已知PCI设备的列表中（由pci_deivices指向）。

参见drivers/pci/pci.c Scan_bus()

PCI初始化代码从PCI总线0开始扫描。它试图读出每一个可能的PCI槽位中每一个可能的PCI设备的Vendor Identification和Device Identification域。当它找到了占用的槽位它就建立一个pci_dev数据结构来描述它。PCI初始化代码所建立的所有的pci_dev数据结构（包括所有的PCI-PCI桥）都链接到一个链接表：pci_devices。

如果找到的设备是一个PCI-PCI桥，则建立一个pci_bus的数据结构，并链接到pci_root指向的由pci_bus和pci_dev数据结构组成的树上。PCI的初始代码可以判断PCI设备是否PCI-PCI桥，因为它的分类编码（class code）是0x060400。然后Linux核心配置它刚刚找到的PCI-PCI桥的另一端的PCI总线（下游）。如果找到更多的PCI-PCI桥，它们都一样被配置。这个过程成为深度（depthwize）算法：系统在宽度搜索之前先在深度展开。看图6.1，Linux会首先配置PCI总线1和它的以太网和SCSI设备，然后配置PCI总线0上的显示设备。

在Linux向下游查找PCI总线的时候它必须配置介入的PCI-PCI桥的次总线和附属总线编号。这些在下面的6.6.2节详细描述：

Configuring PCI-PCI Bridges – Assigning PCI Bus Numbers（配置PCI-PCI桥-分配PCI总线编号）

对于传送通过它们进行的PCI I/O、PCI内存或者PCI配置地址空间的读写，PCI-PCI桥必须直到以下：

Primary Bus Number 刚好在PCI-PCI桥上游的总线编号

Secondary Bus Number 刚好在PCI-PCI桥下游的总线编号

Subordinate Bus Number 从这个桥向下可以达到的所有总线中最高的总线编号。

PCI I/O and PCI Memory Windows 从这个PCI-PCI桥向下的所有的地址的PCI I/O地址空间和PCI 内存空间的窗口的base和size。

问题是当你希望配置任何指定的PCI-PCI桥的时候你并不知道这个桥的附属总线数目。你不知道是否下游还有其他PCI-PCI桥。就算知道，你也不知道它们将会被分配什么编号。答案是使用一个深度递归算法（depthwise recursive algorithm）。在每一个总线上找到任何PCI-PCI桥的时候都就给它们分配编号。对于找到的每一个PCI-PCI桥，就给它的次总线分配编号，并给它分配临时的附属总线编号0xFF，并扫描它的下游所有的PCI-PCI桥并分配编号。这看起来相当复杂，但是下面的实际例子能使这个过程更清楚。

PCI-PCI Bridge Numbering： Step 1 参考图6.6中的拓扑，扫描找到的第一个桥是桥1（Bridge1）。桥1下游的PCI总线编号为1，桥1分配一个次总线号1和一个临时的附属总线编号0xFF。这意味着指定PCI总线1或更高的所用的类型1的PCI配置地址会穿过桥1到达PCI总线1。如果它们的总线编号是1，就转换成为类型0的配置cycle，否则对于其他的总线编号就不变。这也正是Linux PCI初始化代码需要做的，这样才能访问并扫描PCI总线1。

PCI-PCI Bridge Numbering： Step 2 Linux使用深度算法，所以初始化代码开始扫描PCI总线1。这是它找到了PCI-PCI桥2，桥2之外没有其他的PCI-PCI桥，所以它的附属总线编号成为2，和它的次接口一样。图6.7显示了总线和PCI-PCI桥这时是如何编码的。

PCI-PCI Bridge Numbering：Step 3 PCI初始化代码回来扫描PCI总线1，找到了另一个PCI-PCI桥3。它的主总线接口赋值1而它的次总线接口是3，它的附属总线编号是0xFF。图6.8显示了系统这时是如何配置的。带有总线编号1、2或3的类型1的PCI配置cycle现在可以正确地传送到适当的PCI总线。

6.6.3 PCI BIOS Functions（PCI BIOS函数）

PCI BIOS函数是通用的跨平台的一系列标准例程。例如，它们对于Intel和Alpha AXP系统都是一样的。它们允许CPU控制对于所有PCI地址空间的访问。只有Linux核心和设备驱动程序需要使用它们。

参见arch/*/kernel/bios32.c

Alpha AXP系统上的PCI整理代码比Intel（基本不做任何事情）要做更多的工作。对于Intel系统，启动时候运行的系统BIOS，已经完全配置了PCI系统。Linux不需要做更多的事情，只是映射PCI的配置。对于非Intel系统，需要做更多的配置：

参见arch/kernel/bios32.c

对于每一个设备分配PCI I/O和PCI内存空间

对于系统重的每一个PCI-PCI桥必须配置PCI I/O和PCI内存地址窗口

对于设备产生Interrupt Line值，这些控制设备的中断处理

（找出一个设备需要多少PCI I/O和PCI内存空间）

查询找到的每一个PCI设备，找出它需要多少PCI I/O和内存地址空间。为此，把每一个Base Address Register都写成1然后读出来。设备会在不关心的地址位返回1，有效地指定了需要的地址空间。

用两个基本的基础地址寄存器（Base Address Register），第一种指示设备的寄存器以及PCI I/O和PCI 内存空间必须在哪一个地址空间。这通过寄存器的0位表示。图6.10显示了PCI 内存和PCI I/O的基础地址寄存器的两种形式。

为了找出每一个给定的基础地址寄存器需要多少地址空间，需要向所有的寄存器写并读出来。设备会把不关心的地址位设为0，这样就有效地指明了需要的地址空间。这种设计暗示了使用的所有的地址空间都是2的指数，本质上是对齐的。

例如，在你初始化DECChip 21142 PCI快速以太网设备的时候，它告诉你在PCI I/O或PCI内存空间它需要0x100字节的地址。初始化代码为它分配空间。在它分配空间之后，21142的控制和状态寄存器就可以在这些地址见到。

（为PCI-PCI桥和设备分配PCI I/O和PCI内存）

象所有的内存一样，PCI I/O和PCI内存空间是有限的，其中有一些相当紧缺。对于非Intel系统的PCI整理代码（和Intel系统的BIOS代码）必须有效地为每一个设备分配它需要的内存量。分配给一个设备的PCI I/O和PCI内存的分配必须自然对齐。例如，如果一个设备请求PCI I/O地址0xB0，那么分配的地址就必须是0xB0的倍数。另外，分配给任何桥的PCI I/O和PCI内存地址的基础必须分别对齐4K和1M的边界。下游的设备给定的地址空间必须位于它所有的上游的PCI-PCI桥的内存范围中间。所以有效地分配地址空间是有比较困难的问题。

Linux使用的算法依赖于用PCI设备驱动程序建立的总线/设备树所描述的每一个设备，它按照PCI I/O内存递增的顺序分配地址空间。又是使用递归算法，遍历PCI初始化代码所建立的pci_bus和pci_dev数据结构。BIOS整理代码从PCI总线的根（pci_root所指）开始：

分别把当前的全局PCI I/O和内存的基础分别对齐在4K和1M的边界

对于当前总线上的每一个设备（按照需要的PCI I/O内存顺序排列）

-分配它的PCI I/O和/或PCI内存

-将全局的PCI I/O和内存的基础按照合适的量移动

-允许设备使用给定的PCI I/O和PCI内存

分别为当前总线下游的所有总线分配空间，注意这会改变全局的PCI I/O和内存基础。

分别把当前的全局PCI I/O和内存的基础对齐在4K和1M的边界，同时指出当前的PCI-PCI桥所需要的PCI I/O和PCI内存的窗口的基础和大小

对于连接在当前总线上的PCI-PCI桥，设置它的PCI-PCI I/O和PCI内存地址和限制。

打开PCI-PCI桥上桥接PCI I/O和PCI内存访问的功能。这意味着如果任何在桥的主PCI总线上看到的PCI I/O和PCI内存地址如果位于它的PCI I/O和PCI内存地址窗口的话就会被桥接到它的次总线。

以图6.1的PCI系统作为PCI整理代码的例子：

Align the PCI base （初始的）PCI I/O是0x4000，PCI内存是0x100000。这样允许PCI-ISA桥把所有低于此的地址都转换到ISA地址。

The Video Device 请求0x200000的PCI内存，因为必须按照要求的大小对齐，所以我们从PCI内存0x200000开始分配，PCI内存基础地址移到了0x400000，而PCI I/O地址仍旧是0x4000。

The PCI-PCI Bridges 我们现在穿过PCI-PCI桥，在那里分配内存。注意因为我们不需要对其基础地址因为它们已经正确对齐了。

The Ethernet Device 它在PCI I/O和PCI内存空间都请求0xB0字节。它被分配在PCI I/O地址0x4000，PCI内存0x400000。PCI内存的基础移到了0x4000B0，PCI I/O的基础成为0x40B0。

The SCSI Device 它请求0x1000的PCI内存，所以它在对齐之后分配在0x401000。而PCI I/O的基础地址还是0x40B0，PCI内存的基础移到了0x402000。

The PCI-PCI Bridge’s PCI I/O and Memory Windows 我们现在返回到桥，把它的PCI I/O窗口设置成为0x4000和0x40B0之间，它的PCI内存窗口在0x400000和0x402000之间。这意味着PCI-PCI桥会忽略对于显示设备的PCI内存访问，如果是对以太网或者SCSI设备的访问就可以通过。

Chapter 7 Interrupts and Interrupt Handling（中断和中断处理）

本章探讨Linux核心如何处理中断。虽然核心有用于处理中断的通用机制和接口，大部分中断处理的细节还是和体系结构相关的。

Linux使用大量不同的硬件来完成许多不同的任务。显示设备驱动显示器，IDE设备驱动磁盘等等。你可以同步地驱动这些设备，就是你可以发出一个请求执行一些操作（比如把一块内存写到磁盘）然后等待操作结束。这种方式，虽然可以工作，但是非常没有效率，操作系统当它等待每一个操作完成的时候会花费大量时间“忙于什么也不做”（busy doing nothing）。一个好的，更有效的方法是做出了请求然后去作其他更有用的事情，然后当设备完成请求的时候被设备中断。在这种方案下，系统中同一时刻可能有许多设备的请求在同时发生。

让设备中断CPU当前的工作必须有一些硬件的支持。大多数，如果不是所有的话，通用目的的处理器比如Alpha AXP都使用相似的方法。CPU的一些物理管脚的电路只要改变电压（例如从+5V到-5V）就会让CPU停止正在做的工作，开始执行处理中断的特殊代码：中断处理代码。这些管脚之一可能连接一个内部适中，每一个1000分之一秒就接收一个中断，其他的也许连接到系统的其他设备，比如SCSI控制器。

系统通常使用一个中断控制器把设备的中断集合在一起，然后把信号传送到CPU的一个单一的中断管脚。这可以节省CPU的中断管教，也给设计系统带来了灵活性。中断控制器有掩码和状态寄存器，用于控制这些中断。设置掩码寄存器的位可以允许和禁止中断，状态寄存器返回系统中当前的中断。

一些系统中的中断可能是硬连接的，例如实时时钟的内部时钟可能永久地连接到中断控制器的第3管脚。但是，另一些管脚连接什么可能由在特定的ISA或者PCI槽位插入什么控制卡决定。例如，中断控制器的第4管脚可能和PCI槽位0相连，可能某一天有一个以太网卡，当时后来可能是一块SCSI控制卡。每一个系统都有它自己的中断中转机制，操作系统必须足够灵活才能处理。

大多数现代的通用目的微处理器用相同的方式处理中断。发生硬件中断的时候，CPU停止它正在运行的指令，跳到内存中一个位置运行，这里或者包含中断处理代码或者是跳到中断处理代码的指令。这种代码通常在CPU的特殊模式下工作：中断模式，通常，这种模式下其他中断不能产生。这里也有例外：一些CPU将中断划分级别，更高级别的中断可以发生。这意味着写第一级的中断处理程序必须非常小心。中断处理程序通常都有自己的堆栈，用来存放CPU的执行状态（CPU所有的通用寄存器和上下文）并处理中断。一些CPU有一组只在中断模式下存在的寄存器，中断处理代码可以使用这些寄存器来存储它需要保存的大部分上下文信息。

当处理完中断，CPU的状态恢复，中断结束。CPU会继续做它在中断发生之前做的事情。重要的事中断处理程序必须尽可能地有效，通常操作系统不能经常或者长时间阻塞中断。

7.1 Programmable Interrupt Controllers（可编程中断控制器）

系统设计师可以任意使用他们希望用的中断体系结构，但是IBM PC都使用Intel 82C59A-2 CMOS可编程中断控制器或者它的衍生物。这种控制器在PC最初的时候就使用了。它可通过寄存器编程，这些寄存器在ISA地址空间的众所周知的位置。甚至很现代的逻辑芯片组都在ISA内存的相同位置保留了等价的寄存器。非Intel的系统，例如Alpha AXP PC不受这些体系限制，通常使用不同的中断控制器。

图7.1显示了两个串联在一起的8位控制器：每一个都有一个掩码和一个中断状态寄存器，PIC1和PIC2。掩码寄存器位于地址0x21和0xA1，而状态寄存器位于0x20和0xA0。在掩码寄存器的一个特殊位写1允许一种中断，写0可以禁止它。所以向位3写1允许中断3，写0会禁止它。不幸的是（也是让人气恼的），中断掩码寄存器只可以写，你无法读回你所写的值。这意味着Linux必须为它设置的掩码（mask）寄存器保留一份本地拷贝。它在中断允许和禁止的例程中修改这些保存的掩码，每一次都要把整个掩码写到寄存器中。

当产生中断信号，中断处理程序读取两个中断状态寄存器（ISR）。它把0x20的ISR看作16位的中断寄存器的第8位，0xA0中的ISR看作高8位。所以，发生在0xA0的ISR的第1位的中断被看作是中断9。PCI1的第2位不可用，因为它用作串联PIC2的中断，任何PIC2的中断都会使PIC1的第2位置位。

7.2 Initializing the Interrupt Handling Data Structures（初始化中断处理数据结构）

当设备驱动程序要求控制系统的中断的时候建立核心的中断处理数据结构。为此，设备驱动程序使用一系列Linux核心服务，用来请求一个中断、允许它和禁止它。这些设备驱动程序调用这些例程来登记它们的中断处理例程的地址。

参见arch/*/kernel/irq.c request_irq() enable_irq() and disable_irq()

PC体系结构为了方便把一些中断固定下来，所以驱动程序在初始化的时候只需要简单地请求它的中断。软盘设备驱动程序就是这样：它总是请求中断6。但是也可能一个设备驱动程序不知道设备会使用什么中断。对于PCI设备驱动程序这不是问题，因为它们总是知道它们的中断编号。不幸的是对于ISA设备没有什么简单的办法找到它们的中断号码，Linux允许设备驱动程序探查它们的中断来解决这个问题。

首先，设备驱动程序让设备产生中断，然后系统中所有没有分配的中断都允许了。这意味着设备等待处理的中断现在会通过可编程中断控制器传递。Linux读取中断状态寄存器然后把它的内容返回到设备驱动程序。非0 的结果表示在探查中发生了一或多个中断。驱动程序现在关闭探查，并禁止所有位分配的中断。如果ISA设备驱动程序成功地找到了它的IRQ号，它就可以想平常一样地请求控制它。

参见arch/*/kernel/irq.c irq_probe_*()

PCI系统比ISA系统更加动态。ISA设备的中断通常用硬件设备上的跳线来设置，对于设备驱动程序是固定的。反过来，PCI设备的中断是在系统启动的时候由PCI BIOS或者PCI子系统在PCI初始化的时候分配的。每一个PCI设备可以使用4个中断管脚其中之一：A、B、C或D。这时设备制造的时候确定的，大多数设备缺省用中断管脚A。每一个PCI槽位的PCI中断线（interrupte line）A、B、C和D都转到中断控制器。所以槽位4的管脚A可能转到了中断控制器的第6管脚，槽位4的管脚B可能转到了中断控制器的管脚7，依此类推。

PCI中断如何被转发（路由route）完全是和系统相关的，必须有一些理解这种PCI中断路由拓扑的设置代码。在Intel PC上，这是启动的时候的系统BIOS代码完成的。但是对于没有BIOS的系统（例如Alpha AXP系统），Linux进行这种设置。PCI设置代码把中断控制器的管脚编号写到每一个设备的PCI配置头中。它使用它知道的PCI中断路有拓扑和设备的PCI槽位以及它正在使用的PCI中断管脚来决定中断管脚（或者说IRQ）编号。设备使用的中断管脚就确定下来并放到PCI配置头的一个域。它把这个信息写到中断线（interrupte line）域（这是为此目的保留的）。当设备驱动程序运行的时候，它读取这个信息，并使用它向Linux核心请求对中断的控制。

参见arch/alpha/kernel/bios32.c

系统中可能使用许多PCI中断资源。例如，当使用PCI-PCI桥的时候。中断来源的数目可能超过系统的可编程中断控制器的管脚数目。这种情况下，PCI设备可以共享中断：中断控制器上的一个管脚接收来自多于一个PCI设备的中断。Linux让第一个请求一个中断的源宣称（declare）它是否可以共享，这样来支持中断共享。共享中断结果是irq_action向量表中的一个条目可以指向几个irqaction的数据结构。当发生了一个共享的中断的时候，Linux会调用这个源的所有的中断处理程序。所有可以共享中断的设备驱动程序（都应该是PCI设备驱动程序）必须预备在没有中断服务的时候被调用。

7.3 Interrupt Handling（中断处理）

Linux中断处理子系统的一个主要任务是把中断转送到（route）正确的中断处理代码段。这种代码必须了解系统的中断拓扑。例如，如果软驱控制器在中断控制器的管脚6发生中断，它必须可以识别出中断是来自软驱，并把它转送到软驱设备驱动程序的中断处理程序代码。Linux使用一系列数据结构的指针，包含了处理系统中断的例程的地址。这些例程属于系统中的设备的设备驱动程序，每一个设备驱动程序必须负责在驱动程序初始化的时候请求它想要的中断。图7.2显示了irq_action是一个指向irqaction数据结构的指针的向量表。每一个irqaction数据结构都包括了这个中断处理程序的信息，包括中断处理例程的地址。不同体系的中断数目和如何处理是不同的，通常，不同系统之间，Linux中断处理代码是和体系结构相关的。这意味着irq_action向量表的大小依赖于中断源的数目而不同。

当发生中断的时候，Linux必须首先通过读取系统的可编程中断控制器的状态寄存器确定它的来源。然后把这个来源转换成irq_action向量表中的偏移。例如，从软驱控制器来的中断控制器管脚6的中断会转为中断处理程序向量表中的第7个指针。如果发生的中断没有对应的中断处理程序，Linux核心会记录下一个错误，否则，它会调用这个中断源的所有的irqaction数据结构中的中断处理例程。

当Linux核心调用设备驱动程序的中断处理例程的时候，它必须有效地判断为什么被中断，并进行响应。为了找出中断的原因，设备驱动程序会读取中断设备的状态寄存器。设备可能回应：发生了一个错误或者完成了一个请求的操作。例如软驱控制器可能报告它已经把软驱的读磁头定位到了软盘正确的扇区。一旦确定了中断的原因，设备驱动程序可能还需要做更多的工作。如果是这样，Linux核心有机制允许延迟这个操作稍候进行。这可以避免让CPU在中断模式下花费太多时间。详细描述参见设备驱动程序章（第8章）

Device Drivers（设备驱动程序）

操作系统其中一个目的就是向用户掩盖系统硬件设备的特殊性。例如，虚拟文件系统呈现了安装的文件系统的一个统一的试图，而和底层的物理设备无关。本章描述Linux核心是如何管理系统中的物理设备的。

CPU不是系统中唯一的智能设备，每一个物理设备都由它自己的硬件控制器。键盘、鼠标和串行口由SuperIO芯片控制，IDE磁盘由IDE控制器控制，SCSI磁盘由SCSI控制器控制，等等。每一个硬件控制器都由自己的控制和状态控制器（CSR），不同的设备之间是不同的。一个Adaptec 2940 SCSI控制器的CSR和NCR 810 SCSI控制器的完全不同。CSR用于启动和停止设备，初始化设备和诊断它的问题。管理这些硬件控制器的代码不是放在每一个应用程序里边，而是放在Linux核心。这些处理或者管理硬件控制器的软件脚做设备驱动程序。Linux核心的设备驱动程序本质上是特权的、驻留内存的低级的硬件控制例程的共享库。是Linux的设备驱动程序在处理它们管理的设备的特质。

UN*X的一个基本特点是它抽象了设备的处理。所有的硬件设备都象常规文件一样看待：它们可以使用和操作文件相同的、标准的系统调用来进行打开、关闭和读写。系统中的每一个设备都用一个设备特殊文件代表。例如系统中第一个IDE硬盘用/dev/had表示。对于块（磁盘）和字符设备，这些设备特殊文件用mknod命令创建，并使用主（major）和次（minor）设备编号来描述设备。网络设备也用设备特殊文件表达，但是它们由Linux在找到并初始化系统中的网络控制器的时候创建。同一个设备驱动程序控制的所有设备都由一个共同的major设备编号。次设备编号用于在不同的设备和它们的控制器之间进行区分。例如，主IDE磁盘的不同分区都由一个不同的次设备编号。所以，/dev/hda2，主IDE磁盘的第2个分区的主设备号是3，而次设备号是2。Linux使用主设备号表和一些系统表（例如字符设备表chrdevs）把系统调用中传递的设备特殊文件（比如在一个块设备上安装一个文件系统）映射到这个设备的设备驱动程序中。

参见fs/devices.c

Linux支持三类的硬件设备：字符、块和网络。字符设备直接读写，没有缓冲区，例如系统的串行端口/dev/cua0和/dev/cua1。块设备只能按照一个块（一般是512字节或者1024字节）的倍数进行读写。块设备通过buffer cache访问，可以随机存取，就是说，任何块都可以读写而不必考虑它在设备的什么地方。块设备可以通过它们的设备特殊文件访问，但是更常见的是通过文件系统进行访问。只有一个块设备可以支持一个安装的文件系统。网络设备通过BSD socket接口访问，网络子系统在网络章（第10章）描述。

Linux有许多不同的设备驱动程序（这也是Linux的力量之一）但是它们都具有一些一般的属性：

Kernel code 设备驱动程序和核心中的其他代码相似，是kenel的一部分，如果发生错误，可能严重损害系统。一个写错的驱动程序甚至可能摧毁系统，可能破坏文件系统，丢失数据。

Kenel interfaces 设备驱动程序必须向Linux核心或者它所在的子系统提供一个标准的接口。例如，终端驱动程序向Linux核心提供了一个文件I/O接口，而SCSI设备驱动程序向SCSI子系统提供了SCSI设备接口，接着，向核心提供了文件I/O和buffer cache的接口。

Kernel mechanisms and services 设备驱动程序使用标准的核心服务例如内存分配、中断转发和等待队列来完成工作

Loadable Linux大多数的设备驱动程序可以在需要的时候作为核心模块加载，在不再需要的时候卸载。这使得核心对于系统资源非常具有适应性和效率。

Configurable Linux设备驱动程序可以建立在核心。哪些设备建立到核心在核心编译的时候是可以配置的。

Dynamic 在系统启动，每一个设备启动程序初始化的时候它查找它管理的硬件设备。如果一个设备驱动程序所控制的设备不存在并没有关系。这时这个设备驱动程序只是多余的，占用很少的系统内存，而不会产生危害。

8.1 Poling and Interrupts（轮询和中断）

每一次给设备命令的时候，例如“把读磁头移到软盘的第42扇区“，设备驱动程序可以选择它如何判断命令是否执行结束。设备驱动程序可以轮询设备或者使用中断。

轮询设备通常意味着不断读取它的状态寄存器，直到设备的状态改变指示它已经完成了请求。因为设备驱动程序是核心的一部分，如果驱动程序一直在轮询，核心在设备完成请求之前不能运行其他任何东西，会是损失惨重的。所以轮询的设备驱动程序使用一个系统计时器，让系统在晚些时候调用设备驱动程序中的一个例程。这个定时器例程会检查命令的状态，Linux的软盘驱动程序就是这样工作的。使用计时器进行轮询是一种最好的接近，而更加有效的方法是使用中断。

中断设备驱动程序在它控制的硬件设备需要服务的时候会发出一个硬件中断。例如：一个以太网设备驱动程序会在设备在网络上接收到一个以太网报文的时候被中断。Linux核心需要有能力把中断从硬件设备转发到正确的设备驱动程序。这通过设备驱动程序向核心登记它所使用的中断来实现。它登记中断处理程序例程的地址和它希望拥有的中断编号。你通过/proc/interrupts可以看到设备驱动使用了哪些中断和每一类型的中断使用了多少次：

对于中断资源的请求发生在驱动程序初始化的时间。系统中的一些中断是固定的，这是IBM PC体系结构的遗留物。例如软驱磁盘控制器总是用中断6。其他中断，例如PCI设备的中断，在启动的时候动态分配。这时设备驱动程序必须首先找出它所控制的设备的中断号，然后才能请求拥有这个中断（的处理权）。对于PCI中断，Linux支持标准的PCI BIOS回调（callback）来确定系统中设备的信息，包括它们的IRQ。

一个中断本身是如何转发到CPU依赖于体系结构。但是在大多数的体系上，中断都用一种特殊的模式传递，而停止系统中发生其他中断。设备驱动程序在它的中断处理例程中应该做尽可能少的工作，使得Linux核心可以结束中断并返回到它中断之前的地方。收到中断后需要做大量工作的设备驱动程序可以使用核心的bottom half handler或者任务队列把例程排在后面，以便在以后调用。

8.2 Direct Memory Access （DMA）

当数据量比较少的时候用中断驱动的设备驱动程序向设备或者通过设备传输数据工作地相当好。例如，一个9600波特率的modem每一毫秒（1/1000秒）大约可以传输一个字符。如果中断延迟，就是从硬件设备发出中断到开始调用设备驱动程序中的中断处理程序所花的时间比较少（比如2毫秒），那么数据传输对系统整体的映像就非常小。9600波特率的modem数据传出只会占用0.002%的CPU处理时间。但是对于高速的设备，比如硬盘控制器或者以太网设备，数据传输速率相当高。一个SCSI设备每秒可以传输高达40M字节的信息。

直接内存存取，或者说DMA，就是发明来解决这个问题的。一个DMA控制器允许设备不需要处理器的干预而和系统内存创树数据。PC的ISA DMA控制器由8个DMA通道，其中7个可用于设备驱动程序。每一个DMA通道都关联一个16位的地址寄存器和一个16位的计数寄存器（count register）。为了初始化一次数据传输，设备驱动程序需要建立DMA通道的地址和计数寄存器，加上数据传输的方向，读或写。当传输结束的时候，设备中断PC。这样，传输发生的时候，CPU可以作其他事情。

使用DMA的时候设备驱动程序必须小心。首先，所有的DMA控制器都不了解虚拟内存，它只能访问系统中的物理内存。因此，需要进行DMA传输的内存必须是物理内存中连续的块。这意味着你不能对于一个进程的虚拟地址空间进行DMA访问。但是你可以在执行DMA操作的时候把进程的物理也锁定到内存中。第二：DMA控制器无法访问全部的物理内存。DMA通道的地址寄存器表示DMA地址的首16位，跟着的8位来自于页寄存器（page register）。这意味着DMA请求限制在底部的16M内存中。

DMA通道是稀少的资源，只有7个，又不能在设备驱动程序之间共享。象中断一样，设备驱动程序必须有能力发现它可以使用哪一个DMA通道。象中断一样，一些设备有固定的DMA通道。比如软驱设备，总是用DMA通道2。有时，设备的DMA通道可以用跳线设置：一些以太网设备用这种技术。一些更灵活的设备可以告诉它（通过它们的CSR）使用哪一个DMA通道，这时，设备驱动程序可以简单地找出一个可用的DMA通道。

Linux使用dma_chan数据结构向量表（每一个DMA通道一个）跟踪DMA通道的使用。Dma_chan数据结构只有两个玉：一个字符指针，描述这个DMA通道的属主，一个标志显示这个DMA通道是否被分配。当你cat /proc/dma的时候显示的就是dma_chan向量表。

8.3 Memory（内存）

设备驱动程序必须小心使用内存。因为它们是Linux核心的一部分，它们不能使用虚拟内存。每一次设备驱动程序运行的时候，可能是接收到了中断或者调度了一个buttom half handler或任务队列，当前的进程都可能改变。设备驱动程序不能依赖于一个正在运行的特殊进程。象核心中其他部分一样，设备驱动程序使用数据结构跟踪它控制的设备。这些数据结构可以在设备驱动程序的代码部分静态分配，但是这会让核心不必要地增大而浪费。多数设备驱动程序分配核心的、不分页的内存存放它们的数据。

Linux核心提供了核心的内存分配和释放例程，设备驱动程序正是使用了这些例程。核心内存按照2的幂数的块进行分配。例如128或512字节，即使设备驱动程序请求的数量没有这么多。设备驱动程序请求的字节数按照下一个块的大小取整。这使得核心的内存回收更容易，因为较小的空闲块可以组合成更大的块。

请求核心内存的时候Linux还需要做更多的附加工作。如果空闲内存的总数太少，物理页需要废弃或者写到交换设备。通常，Linux 会挂起请求者，把这个进程放到一个等待队列，直到有了足够的物理内存。不是所有的设备驱动程序（或者实际是Linux的核心代码）希望发生这样的事情，核心内存分配例程可以请求如果不能立刻分配内存就失败。如果设备驱动程序希望为DMA访问分配内存，它也需要指出这块内存是可以进行DMA的。因为需要让Linux核心明白系统中哪些是连续的可以进行DMA的内存，而不是让设备驱动程序决定。

8.4 Interfacing Device Drivers with the Kernel（设备驱动程序和核心接口）

Linux核心必须能够用标准的方式和它们作用。每一类的设备驱动程序：字符、块和网络，都提供了通用的接口供核心在需要请求它们的服务的时候使用。这些通用的接口意味着核心可以完全相同地看待通常是非常不同的设备和它们的设备驱动程序。例如，SCSI和IDE磁盘的行为非常不同，但是Linux核心对它们使用相同的接口。

Linux非常地动态，每一次Linux核心启动，它都可能遇到不同的物理设备从而需要不同的设备驱动程序。Linux允许你在核心建立的时间通过配置脚本包含设备驱动程序。当启动的时候这些设备驱动程序初始化，它们可能没发现它们可以控制的任何硬件。其他驱动程序可以在需要的时候作为核心模块加载。为了处理设备驱动程序的这种动态的特质，设备驱动程序在它们初始化的时候向核心登记。Linux维护已经登记的设备驱动程序列表，作为和它们接口的一部分。这些列表包括了例程的指针和支持这一类设备的接口的信息。

8.4.1 Character Devices（字符设备）

字符设备，Linux最简单的设备，象文件一样访问。应用程序使用标准系统调用打开、读取、写和关闭，完全好像这个设备是一个普通文件一样。甚至连接一个Linux系统上网的PPP守护进程使用的modem，也是这样的。当字符设备初始化的时候，它的设备驱动程序向Linux核心登记，在chrdevs向量表增加一个device_struct数据结构条目。这个设备的主设备标识符（例如对于tty设备是4），用作这个向量表的索引。一个设备的主设备标识符是固定的。Chrdevs向量表中的每一个条目，一个device_struct数据结构，包括两个元素：一个登记的设备驱动程序的名称的指针和一个指向一组文件操作的指针。这块文件操作本身位于这个设备的字符设备驱动程序中，每一个都处理特定的文件操作比如打开、读、写和关闭。/proc/devices中字符设备的内容来自chrdevs向量表

参见include/linux/major.h

当代表一个字符设备（例如/dev/cua0）的字符特殊文件打开，核心必须做一些事情，从而去掉用正确的字符设备驱动程序的文件操作例程。和普通文件或目录一样，每一个设备特殊文件都用VFS I节点表达。这个字符特殊文件的VFS inode（实际上所有的设备特殊文件）都包括设备的major和minor标识符。这个VFS I节点由底层的文件系统（例如EXT2），在查找这个设备特殊文件的时候根据实际的文件系统创建。

参见fs/ext2/inode.c ext2_read_inode()

每一个VFS I节点都联系着一组文件操作，依赖于I节点所代表的文件系统对象不同而不同。不管代表一个字符特殊文件的VFS I节点什么时候创建，它的文件操作被设置成字符设备的缺省操作。这只有一种文件操作：open操作。当一个应用程序打开这个字符特殊文件的时候，通用的open文件操作使用设备的主设备标识符作为chrdevs向量表中的索引，取出这种特殊设备的文件操作块。它也建立描述这个字符特殊文件的file数据结构，让它的文件操作指向设备驱动程序中的操作。然后应用程序所有的文件系统操作都被映射到字符设备的文件操作。

参见fs/devices.c chrdev_open() def_chr_fops

8.4.2 Block Devices（块设备）

块设备也支持象文件一样被访问。这种为打开的块特殊文件提供正确的文件操作组的机制和字符设备的十分相似。Linux用blkdevs向量表维护已经登记的块设备文件。它象chrdevs向量表一样，使用设备的主设备号作为索引。它的条目也是device_struct数据结构。和字符设备不同，块设备进行分类。SCSI是其中一类，而IDE是另一类。类向Linux核心登记并向核心提供文件操作。一种块设备类的设备驱动程序向这种类提供和类相关的接口。例如，SCSI设备驱动程序必须向SCSI子系统提供接口，让SCSI子系统用来对核心提供这种设备的文件操作

参见fs/devices.c

每一个块设备驱动程序必须提供普通的文件操作接口和对于buffer cache的接口。每一个块设备驱动程序填充blk_dev向量表中它的blk_dev_struct数据结构。这个向量表的索引还是设备的主设备号。这个blk_dev_struct数据结构包括一个请求例程的地址和一个指针，指向一个request数据结构的列表，每一个都表达buffer cache向设备读写一块数据的一个请求。

参见drivers/block/ll_rw_blk.c include/linux/blkdev.h

每一次buffer cache希望读写一块数据到或从一个登记的设备的时候它就在它的blk_dev_struc中增加一个request数据结构。图8.2显示了每一个request都有一个指针指向一个或多个buffer_head数据结构，每一个都是一个读写一块数据的请求。这个buffer_head数据结构被锁定（buffer cache），可能会有一个进程在等待这个缓冲区的阻塞进程完成。每一个request结构都是从一个静态表，all_request表中分配的。如果这个request增加到一个空的request列表，就调用驱动程序的request函数处理这个request队列。否则，驱动程序只是简单地处理request队列中的每一个请求。

一旦设备驱动程序完成了一个请求，它必须把每一个buffer_head结构从request结构中删除，标记它们为最新的，然后解锁。对于buffer_head的解锁会唤醒任何正在等待这个阻塞操作完成的进程。这样的例子包括文件解析的时候：必须等待EXT2文件系统从包括这个文件系统的块设备上读取包括下一个EXT2目录条目的数据块，这个进程将会在将要包括目录条目的buff_head队列中睡眠，直到设备驱动程序唤醒它。这个request数据结构会被标记为空闲，可以被另一个块请求使用。

8.5 Hard Disks（硬盘）

一个磁盘驱动器由一个或多个磁碟组成，每一个都用相当光滑的玻璃或者陶瓷制成，并覆盖上一层精细的金属氧化物。磁碟放在一个中心轴上面，并按照稳定的速度转动。转动速度根据型号不同从3000到1000RPM（转/每分钟）。磁盘的读/写磁头负责读写数据，每一个磁碟有一对，每一面一个。读/写磁头和磁碟表面并没有物理的接触，而是在一个很薄的空气垫（十万分之一英寸）上面漂浮。读写磁头通过一个驱动器在磁碟表面移动。所有的磁头都粘在一起，一起在磁碟表面移动。

每一个磁碟的表面都分成多个狭窄的同心环，叫做磁道（track）。磁道0是最外面的磁道，最高编号的磁道是最接近中心轴的磁道。一个柱面（cylinder）是相同编号磁道的组合。所以每一个磁碟的每一面的所有的第5磁道就是第5柱面。因为柱面数和磁道数相同，所以磁盘的尺寸常用柱面来描述。每一个磁道分成扇区。一个扇区是可以从硬盘读写的最小数据单元，也就是磁盘的块大小。通常扇区大小是512字节，扇区大小通常是在制造磁盘的时候进行格式化的时候设定的。

磁盘通常用它的尺寸（geometry）描述：柱面数、磁头数和扇区数。例如，启动的时候Linux这样描述我的IDE磁盘：

这意味着它由1050柱面（磁道），16头（8个磁碟）和63个扇区/磁道。对于512字节的扇区或块大小，磁盘的容量是529200K字节。这和磁盘声明的516M的存储能力不符合，因为一些扇区用作存储磁盘的分区信息。一些磁盘可以自动找出坏的扇区，对其进行重新索引。

硬盘可以再分为分区。一个分区是分配用于特定目的的一大组扇区。对磁盘分区允许磁盘用于几个操作系统或多个目的。大多数单个磁盘的Linux系统都由3个分区：一个包含DOS文件系统，另一个是EXT2文件系统，第三个是交换分区。硬盘的分区用分区表描述，每一个条目用磁头、扇区和柱面号描述分区的起止位置。对于用fdisk格式化的DOS磁盘，可以有4个主磁盘分区。不是分区表所有的4个条目都必须用到。Fdisk支持三种类型的分区：主分区、扩展分区和逻辑分区。扩展分区不是真正的分区，它可以包括任意数目的逻辑分区。发明扩展分区和逻辑分区是为了突破4个主分区的限制。下面是一个包括2个主分区的磁盘的fdisk的输出：

它显示了第一个分区开始于柱面或磁道0，磁头1和扇区1，直到柱面477，扇区32和磁头63。因为一个磁道由32个扇区和64个读写磁头，这个分区的柱面都是完全包括的。Fdisk缺省把分区对齐在柱面的边界。它从最外面的柱面（0）开始向内，朝向中心轴，扩展478个柱面。第2个分区，交换分区，开始于下一个柱面（478）并扩展到磁盘最里面的柱面。

在初始化的时候Linux映射系统中的硬盘的拓扑结构。它找出系统中有多少个硬盘以及硬盘的类型。Linux还找出每一个磁盘如何分区。这些都是由gendisk_head指针列表指向的一组gendisk数据结构的列表表达。对于每一个磁盘子系统，例如IDE，初始化的时候生成gendisk数据结构表示它找到的磁盘。这个过程和它登记它的文件操作和在blk_dev数据结构中增加它的条目发生在同一时间。每一个gendisk数据结构都由一个唯一的主设备号，和块特殊设备的相同。例如，SCSI磁盘子系统会创建一个独立的gendisk条目（“sd”），主设备号是8（所有SCSI磁盘设备的主设备号）。图8.3显示了两个gendisk条目，第一个是SCSI磁盘子系统，第二个是IDE磁盘控制器。这里是ide0，主IDE控制器。

虽然磁盘子系统在初始化的时候会建立相应的gendisk条目，Linux只是在进行分区检查的时候才用到。每一个磁盘子系统必须维护自己的数据结构，让它自己可以把设备的主设备号和次设备号映射到物理磁盘的分区上。不管什么时候读写块设备，不管是通过buffer cache或者文件操作，核心都根据它在块特殊设备文件（例如/dev/sda2）中找到的主设备号和次设备号把操作定向到合适的设备。是每一个设备驱动程序或子系统把次设备号映射到真正的物理设备上。

8.5.1 IDE Disks（IDE磁盘）

今天Linux系统中最常用的磁盘是IDE磁盘（Integrated Disk Electronic）。IDE和SCSI一样是一个磁盘接口而不是一个I/O总线。每一个IDE控制器可以支持最多2个磁盘，一个是master，另一个是slave。Master和slave通常用磁盘上的跳线设置。系统中的第一个IDE控制器叫做主IDE控制器，下一个叫从属控制器等等。IDE可以从/向磁盘进行3.3M/秒的传输，IDE磁盘的最大尺寸是538M字节。扩展IDE或EIDE把最大磁盘尺寸增加到8.6G字节，数据传输速率高达16.6M/秒。IDE和EIDE磁盘比SCSI磁盘便宜，大多数现代PC都有一个或更多的主板上的IDE控制器。

Linux按照它发现的控制器的顺序命名IDE磁盘。主控制器上的主磁盘是/dev/had，slave磁盘是/dev/hdb。/dev/hdc是次IDE控制器上的master磁盘。IDE子系统向Linux登记IDE控制器而不是磁盘。主IDE控制器的主标识符是3，次IDE控制器的标识符是22。这意味着如果一个系统有两个IDE控制器，那么在blk_dev和blkdevs向量表中在索引3和22会有IDE子系统的条目。IDE磁盘的块特殊文件反映了这种编号：磁盘/dev/had和/dev/hdb，都连接在主IDE控制器上，主设备号都是3。核心使用主设备标识符作为索引，对于这些块特殊文件的IDE子系统进行的所有的文件或者buffer cache操作都被定向到相应的IDE子系统。当执行一个请求的时候，IDE子系统负责判断这个请求是针对哪一个IDE磁盘。为此，IDE子系统使用设备特殊文件中的次设备号，这些信息允许它把请求定向到正确的磁盘的正确的分区。/dev/hdb，主IDE控制器上的slave IDE磁盘的设备标识符是（3，64）。它的第一个分区（/dev/hdb1）的设备标识符是（3，65）。

8.5.2 Initializing the IDE Subsystem（初始化IDE子系统）

IBM PC的大部分历史中都有IDE磁盘。这期间这些设备的接口发生了变化。这让IDE子系统的初始化过程比它第一次出现的时候更加复杂。

Linux可以支持的最大IDE控制器数目是4。每一个控制器都用一个ide_hwifs向量表中的一个ide_hwif_t数据结构表示。每一个ide_hwif_t数据结构包含两个ide_drive_t数据结构，分别表示可能支持的master和slave IDE驱动器。在IDE子系统初始化期间，Linux首先查看在系统的CMOS内存中记录的磁盘的信息。这种用电池做后备的内存在PC关机的时候不会丢失它的内容。这个CMOS内存实际上在系统的实时时钟设备里面，不管你的PC开或者关，它都在运行。CMOS内存的位置由系统的BIOS设置，同时告诉Linux系统中找到了什么IDE控制器和驱动器。Linux从BIOS中获取找到的磁盘的尺寸（geometry），用这些信息设置这个驱动器的ide_hwif_t的数据结构。大多数现代PC使用PCI芯片组例如Intel的82430 VX芯片组，包括了一个PCI EIDE控制器。IDE子系统使用PCI BIOS回调（callback）定位系统中的PCI （E）IDE控制器。然后调用这些芯片组的询问例程。

一旦发现一个IDE接口或者控制器，就设置它的ide_hwif_t来反映这个控制器和上面的磁盘。操作过程中IDE驱动程序向I/O内存空间的IDE命令寄存器写命令。主IDE控制器的控制和状态寄存器的缺省的I/O地址是0x1F0-0x1F7。这些地址是早期的IBM PC约定下来的。IDE驱动程序向Linux的buffer cache和VFS登记每一个控制器，分别把它加到blk_dev和blkdevs向量表中。IDE驱动程序也请求控制适当的中断。同样，这些中断也有约定，主IDE控制器是14，次IDE控制器是15。但是，象所有的IDE细节一样，这些都可以用核心的命令行选项改变。IDE驱动程序在启动的时候也为每一个找到的IDE控制器在gendisk列表中增加一个gendisk条目。这个列表稍后用于查看启动时找到的所有的硬盘的分区表。分区检查代码明白每一个IDE控制器可以控制两个IDE磁盘。

8.5.3 SCSI Disks（SCSI磁盘）

SCSI（Small Computer System Interface小型计算机系统接口）总线是一种有效的点对点的数据总线，每个总线支持多达8个设备，每个主机可以有一或者多个。每一个设备都必须由一个唯一的标识符，通常用磁盘上的跳线设置。数据可以在总线上的任意两个设备之间同步或者异步传输，可以用32位宽的数据传输，速度可能高达40M/秒。SCSI总线可以在设备之间传输数据和状态信息，发起者（initiator）和目标（target）之间的事务会涉及多达8个不同的阶段。你可以通过SCSI总线上的5种信号判断出当前的阶段。这8个阶段是：

BUS FREE 没有设备有总线的控制权，当前没有发生任何事务。

ARBITRATION （仲裁）一个SCSI设备试图得到SCSI总线的控制权，它在地址管脚上声明（assert）它的SCSI标识符。最高编号的SCSI标识符成功。

SELECTION 一个设备通过仲裁成功地得到了SCSI总线的控制权，现在它必须向它要发送命令的SCSI目标发送信号。它在地址管脚上声明目标的SCSI标识符。

RESELECTION SCSI设备在处理请求的过程中可能断线，目标会重新选择发起者。并非所有的SCSI设备都支持这一阶段。

COMMAND 6、10或者12字节的命令可以从发起者发送到目标。

DATA IN，DATA OUT在这一阶段，数据在发起者和目标之间传输。

STATUS 在完成了所有的命令，进入这一阶段。允许目标向发起者发送一个状态字节，表示成功或失败。

MESSAGE IN，MESSAGE OUT在发起者和目标之间传递的附加信息。

Linux SCSI子系统由两个基本元素组成，每一个都用数据结构表示：

Host 一个SCSI host是一个物理的硬件，一个SCSI控制器。NCR810 PCI SCSI控制器是一个SCSI host的例子。如果一个Linux系统有多于一个同类型的SCSI控制器，每一个实例都分别用一个SCSI host表示。这意味着一个SCSI设备驱动程序可能控制多于一个控制器的实例。SCSI host通常总是SCSI命令的发起者（initiator）。

Device SCSI设备通常是磁盘，但是SCSI标准支持多种类型：磁带、CD-ROM和通用（generic）SCSI设备。SCSI设备通常都是SCSI命令的目标。这些设备必须不同地对待。例如可移动介质如CD-ROM或磁带，Linux需要探测介质是否取出。不同的磁盘类型有不同的主设备编号，允许Linux把块设备请求定向到合适的SCSI类型。

Initializing the SCSI Subsystem（初始化SCSI子系统）

初始化SCSI子系统相当复杂，反映出SCSI总线和设备的动态的实质。Linux在启动的时候初始化SCSI子系统：它查找系统中的SCSI控制器（SCSI host），并探测每一个SCSI总线，查找每一个设备。然后初始化这些设备，让Linux核心的其余部分可以通过普通的文件和buffer cache块设备操作访问它们。这个初始化过程有四个阶段：

首先，Linux找出核心建立的时候建立到核心的哪一个SCSI host适配器或控制器有可以控制的硬件。每一个内建的SCSI host在buildin_scsi_hosts向量表中都有一个Scsi_Host_Template的条目。这个Scsi_Host_Template数据结构包括例程的指针，这些例程可以执行和SCSI host相关的动作例如探测这个SCSI host上粘附了什么SCSI设备。这些例程在SCSI子系统配置期间被调用，是支持这种host类型的SCSI设备驱动程序的一部分。每一个查到的SCSI控制器（有真实的SCSI设备粘附），它的Scsi_Host_Template数据结构都加到scsi_hosts列表中，表示有效的SCSI host。每一个探测到的host类型的每一个实例都用scsi_hostlist列表中的一个Scsi_Host数据结构表示。例如一个系统有两个NCR810 PCI SCSI控制器，在这个列表中会有两个Scsi_Host条目，每一个控制器一个。每一个Scsi_Host指向的Scsi_Host_Template表示它的设备驱动程序。

现在每一个SCSI host都找到了，SCSI子系统必须找到每一个host总线上的所有的SCSI设备。SCSI设备编号从0到7，每一个设备编号或者SCSI标识符在它所粘附的SCSI总线上都是唯一的。SCSI标识符通常用设备上的跳线设置。SCSI初始化代码通过向每一个设备发送TEST_UNIT_READY命令来查找一个SCSI总线上的每一个SCSI设备。当一个设备回应，再向它发送一个ENQUIRY命令来完成它的判别。这向Linux给出Vendor的名称和设备的型号和修订号。SCSI命令用一个Scsi_Cmnd数据结构来表示，这些命令通过调用这个SCSI host的Scsi_Host_Template数据结构中的设备驱动程序例程传递给设备驱动程序。每一个找到的SCSI设备用一个Scsi_Device数据结构表示，每一个都指向它的父Scsi_Host。所有的Scsi_Device数据结构都加到scsi_devices列表中。图8.4显示了主要的数据结构和其他数据结构的关系。