第二章 软件基础
程序是执行某个特定任务的计算机指令集合。程序可以用多种程序语言来编写：从
低级计算机语言-汇编语言到高级的、与机器本身无关的语言入C程序语言。操作系
统是一个允许用户运行如电子表格或者字处理软件等应用程序的特殊程序。本章将
介绍程序设计的基本原则，同时给出操作系统设计目标与功能的概述。
2.1 计算机编程语言
2.1.1 汇编语言
那些CPU从主存读取出来执行的指令对人类来说是根本不可理解的。它们是告诉计算
机如何准确动作的机器代码。在Intel 80486指令中16进制数0x89E5表示将ESP寄存
器的内容拷入EBP寄存器。为最早的计算机设计的工具之一就是汇编器，它可以将人
们可以理解的源文件汇编成机器代码。汇编语言需要显式的操作寄存器和数据，并
且与特定处理器相关。比如说Intel X86微处理器的汇编语言与Alpha AXP微处理器
的汇编语言决然不同。以下是一段Alpha AXP汇编指令程序：
ldr r16, (r15) ; Line 1
ldr r17, 4(r15) ; Line 2
beq r16,r17,100 ; Line 3
str r17, (r15) ; Line 4
100: ; Line 5
第一行语句将寄存器15所指示的地址中的值加载到寄存器16中。接下来将邻接单元内
容加载到寄存器17中。第三行语句比较寄存器16和寄存器17中的值，如果相等则跳转
到标号100处，否则继续执行第四行语句：将寄存器17的内容存入内存中。如果寄存器
中值相等则无须保存。汇编级程序一般冗长并且很难编写，同时还容易出错。Linux核
心中只有很少一部分是用汇编语言编写，并且这些都是为了提高效率或者是需要兼容
不同的CPU。
2.1.2 C编程语言和编译器
用汇编语言编写程序是一件困难且耗时的工作。同时还容易出错并且程序不可移植：
只能在某一特定处理器家族上运行。而用C语言这样的与具体机器无关的语言就要好得
多。C程序语言允许用它所提供的逻辑算法来描叙程序同时它提供编译器工具将C程序
转换成汇编语言并最终产生机器相关代码。好的编译器能产生和汇编语言程序相接近
的效率。Linux内核中大部分用C语言来编写，以下是一段C语言片段：
if (x != y)
x = y ;
它所执行的任务和汇编语言代码示例中相同。如果变量X的值和变量Y的不相同则将Y
的内容赋予X。C代码被组织成子程序，单独执行某一任务。子程序可以返回由C支持
的任何数据类型的值。较庞大的程序如Linux核心由许多单独的C源代码模块组成，每
个模块有其自身的子程序与数据结构。这些C源代码模块将相关函数组合起来完成如
文件处理等功能。C支持许多类型的变量，变量是一个通过符号名称引用的内存位置。
在以上的例子中，X和Y都是内存中的位置。程序员并不关心变量放在什么地方，这些
工作由连接程序来完成。有些变量包含不同类型的数据，整数和浮点数，以及指针。
指针是那些包含其他数据内存位置或者地址的变量。假设有变量X，位于内存地址
0x80010000处。你可以使用指针变量px来指向X，则px的值为0x80010000。C语言允
许相关变量组合起来形成数据结构，例如：
struct {
int i ;
char b ;
} my_struct ;
这是一个叫做my_struct的结构，它包含两个元素，一个是32位的整数i,另外一个是
8位的字符b。
2.1.3 连接程序
连接程序是一个将几个目标模块和库过程连接起来形成单一程序的应用。目标模块是
从汇编器或者编译器中产生的机器代码，它包含可执行代码和数据，模块结合在一起
形成程序。例如一个模块可能包含程序中所有的数据库函数而另一个主要处理命令行
参数。连接程序修改目标模块之间的引用关系，使得在某一模块中引用的数据或者子
程序的确存在于其他模块中。Linux核心是由许多目标模块连接形成的庞大程序。
2.2 操作系统概念
如果没有软件，计算机只不过是一堆发热的电子器件。如果将硬件比做计算机的心脏
则软件就是它的灵魂。操作系统是一组系统程序的集合，它提供给用户运行应用软件
的功能。操作系统对系统硬件进行抽象，它提供给系统用户一台虚拟的机器。大多数
PC可以运行一种或者多种操作系统，每个操作系统都有不同的外观。Linux由许多独
立的功能段组成。比如Linux内核，如果没有库函数和外壳程序，内核是没有什么用的。
为了理解操作系统到底是什么，思考一下当你敲入一个简单命令时，系统中发生了什么：
$ ls
Mail c images perl
docs tcl
$
$符号是由用户登录外壳(这里指Bash)提供的提示符。它表示正在等待用户敲入一些命
令。敲入ls命令，首先键盘驱动程序识别出敲入的内容。然后键盘驱动将它们传递给
外壳程序，由外壳程序来负责查找同名的可执行程序(ls)。
如果在/bin/ls目录中找到了ls，则调用核心服务将ls的可执行映象读入虚拟内存并开
始执行。ls调用核心的文件子系统来寻找那些文件是可用的。文件系统使用缓冲过的
文件系统信息，或者调用磁盘设备驱动从磁盘上读取信息。当然ls还可能引起网络驱
动程序和远程机器来交换信息以找出关于系统要访问的远程文件系统信息(文件系统可
以通过网络文件系统或者NFS进行远程安装)。当得到这些信息后，ls将这些信息通过
调用视频驱动写到显示器屏幕上。
以上这些听起来十分复杂。这个非常简单命令的处理过程告诉我们操作系统是一组协
同工作的函数的集合，它们给所有的用户对系统有一致的印象。
2.2.1 内存管理
由于资源的有限，比如内存，操作系统处理事务的过程看起来十分冗长。操作系统的
一个基本功能就是使一个只有少量物理内存的系统工作起来象有多得多的内存一样。
这个大内存叫为虚拟内存。其思想就是欺骗系统中运行的软件，让它们认为有大量内
存可用。系统将内存划分成易于处理的页面，在系统运行时将这些页面交换到硬盘上
去。由于有另外一个技巧:多处理的存在，这些软件更加感觉不到系统中真实内存的
大小。
2.2.2 进程
进程可以认为是处于执行状态的程序，每个进程有一个特定的程序实体。观察以下
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上。不幸的是，大多数系
统中只有一个CPU。这样操作系统将轮流运行几个程序以产生它们在同时运行的假
象。这种方式叫时间片轮转。同时这种方法还骗过了进程使它们都认为只有自己在
运行。进程之间被隔离开，以便某个进程崩溃或者误操作不会影响到别的进程。操
作系统通过为每个进程提供分立的地址空间来作到这一点。
2.2.3 设备驱动
设备驱动组成了Linux核心的主要部分。象操作系统的其他部分一样，它们运行在
高权限环境中且一旦出错将引起灾难性后果。设备驱动控制操作系统和硬件设备
之间的相互操作。例如当文件系统通过使用通用块设备接口来对IDE磁盘写入数据
块。设备驱动负责处理所有设备相关细节。设备驱动与特定的控制器芯片有关，
如果系统中有一个NCR810 SCSI控制卡则需要有NCR810 SCSI的驱动程序。
2.2.4 文件系统
Linux和Unix一样，系统中的独立文件系统不是通过设备标志符来访问，而是通过
表示文件系统的层次树结构来访问。当Linux添加一个新的文件系统到系统中时，
会将它mount到一个目录下，比如说/mnt/cdrom。
Linux的一个重要特征就是支持多种文件系统。这使得它非常灵活并且可与其他操
作系统并存。Linux中最常用的文件系统是EXT2文件系统，它在大多数Linux分发版
本中都得到了支持。
文件系统提供给用户一个关于系统的硬盘上文件和目录的总体映象，而不管文件的
类型和底层物理设备的特性。
Linux透明地支持多种文件系统并将当前安装的所有文件和文件系统集成到虚拟文
件系统中去。所以，用户和进程一般都不知道某个文件位于哪种文件系统中，他们
只是使用它。
块设备驱动将物理块设备类型（例如IDE和SCSI）和文件系统中的差别隐藏起来，
物理设备只是数据块的线性存储集合。设备的不同导致块大小的不同，从软盘设
备的512字节到IDE磁盘的1024字节。这些都隐藏了起来，对系统用户来说这都是
不可见的。不管设备类型如何，EXT2文件系统看起来总是一样。
2.3 核心数据结构
操作系统可能包含许多关于系统当前状态的信息。当系统发生变化时，这些数据结
构必须做相应的改变以反映这些情况。例如，当用户登录进系统时将产生一个新的
进程。核心必须创建表示新进程的数据结构，同时将它和系统中其他进程的数据结
构连接在一起。
大多数数据结构存在于物理内存中并只能由核心或者其子系统来访问。数据结构包
括数据和指针；还有其他数据结构的地址或者子程序的地址。它们混在一起让Linux
核心数据结构看上去非常混乱。尽管可能被几个核心子系统同时用到，每个数据结
构都有其专门的用途。理解Linux核心的关键是理解它的数据结构以及Linux核心中
操纵这些数据结构的各种函数。本书把Linux核心的描叙重点放在数据结构上，主
要讨论每个核心子系统的算法，完成任务的途径以及对核心数据结构的使用。
2.3.1 连接列表
Linux使用的许多软件工程的技术来连接它的数据结构。在许多场合下，它使用
linked或者chained数据结构。每个数据结构描叙某一事物，比如某个进程或网络
设备，核心必须能够访问到所有这些结构。在链表结构中，个根节点指针包含第一
个结构的地址，而在每个结构中又包含表中下一个结构的指针。表的最后一项必须
是0或者NULL，以表明这是表的尾部。在双向链表中，每个结构包含着指向表中前
一结构和后一结构的指针。使用双向链表的好处在于更容易在表的中部添加与删除
节点，但需要更多的内存操作。这是一种典型的操作系统开销与CPU循环之间的折中。
2.3.2 散列表
链表用来连接数据结构比较方便，但链表的操作效率不高。如果要搜寻某个特定内
容，我们可能不得不遍历整个链表。Linux使用另外一种技术:散列表来提高效率。
散列表是指针的数组或向量，指向内存中连续的相邻数据集合。散列表中每个指针
元素指向一个独立链表。如果你使用数据结构来描叙村子里的人，则你可以使用年
龄作为索引。为了找到某个人的数据，可以在人口散列表中使用年龄作为索引，找
到包含此人特定数据的数据结构。但是在村子里有很多人的年龄相同，这样散列表
指针变成了一个指向具有相同年龄的人数据链表的指针。搜索这个小链表的速度显
然要比搜索整个数据链表快得多。
由于散列表加快了对数据结构的访问速度，Linux经常使用它来实现Caches。Caches
是保存经常访问的信息的子集。经常被核心使用的数据结构将被放入Cache中保存。
Caches的缺点是比使用和维护单一链表和散列表更复杂。寻找某个数据结构时，如
果在Cache中能够找到（这种情况称为cache命中），这的确很不错。但是如果没有
找到，则必须找出它，并且添加到Cache中去。如果Cache空间已经用完则Linux必
须决定哪一个结构将从其中抛弃，但是有可能这个要抛弃的数据就是Linux下次要
使用的数据。
2.3.3 抽象接口
Linux核心常将其接口抽象出来。接口指一组以特定方式执行的子程序和数据结构的
集合。例如，所有的网络设备驱动必须提供对某些特定数据结构进行操作的子程序。
通用代码可能会使用底层的某些代码。例如网络层代码是通用的，它得到遵循标准
接口的特定设备相关代码的支持。
通常在系统启动时，底层接口向更高层接口注册(Register)自身。这些注册操作包
括向链表中加入结构节点。例如，构造进核心的每个文件系统在系统启动时将其自
身向核心注册。文件/proc/filesysems中可以看到已经向核心注册过的文件系统。
注册数据结构通常包括指向函数的指针，以文件系统注册为例，它向Linux核心注册
时必须将那些mount文件系统连接时使用的一些相关函数的地址传入。