Linux 核心（The Linux Kernel）——第二章

作者：毕昕(等) 文章来源：《纯C论坛·电子杂志》点击数：

182 更新时间：2004-12-6

此文原刊发于：《纯C论坛·电子杂志》2004.11（总第二期）上

原著：David A Rusling

翻译：毕昕、胡宁宁、仲盛、赵振平、周笑波、李群、陈怀临

Chapter 2 Software Basics

A program is a set of computer instructions that perform a particular task. That program can be written in assembler, a very low level computer language, or in a high level, machine independent language such as the C programming language. An operating system is a special program which allows the user to run applications such as spreadsheets and word processors. This chapter introduces basic programming principles and gives an overview of the aims and functions of an operating system.

2.1 Computer Languages

2.1.1 Assembly Languages

The instructions that a CPU fetches from memory and executes are not at all understandable to human beings. They are machine codes which tell the computer precisely what to do. The hexadecimal number 0x89E5 is an Intel 80486 instruction which copies the contents of the ESP register to the EBP register. One of the first software tools invented for the earliest computers was an assembler, a program which takes a human readable source file and assembles it into machine code. Assembly languages explicitly handle registers and operations on data and they are specific to a particular microprocessor. The assembly language for an Intel X86 microprocessor is very different to the assembly language for an Alpha AXP microprocessor. The following Alpha AXP assembly code shows the sort of operations that a program can perform:

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

The first statement (on line 1) loads register 16 from the address held in register 15. The next instruction loads register 17 from the next location in memory. Line 3 compares the contents of register 16 with that of register 17 and, if they are equal, branches to label 100. If the registers do not contain the same value then the program continues to line 4 where the contents of r17 are saved into memory. If the registers do contain the same value then no data needs to be saved. Assembly level programs are tedious and tricky to write and prone to errors. Very little of the Linux kernel is written in assembly language and those parts that are written only for efficiency and they are specific to particular microprocessors.

2.1.2 The C Programming Language and Compiler

Writing large programs in assembly language is a difficult and time consuming task. It is prone to error and the resulting program is not portable, being tied to one particular processor family. It is far better to use a machine independent language like C. C allows you to describe programs in terms of their logical algorithms and the data that they operate on. Special programs called compilers read the C program and translate it into assembly language, generating machine specific code from it. A good compiler can generate assembly instructions that are very nearly as efficient as those written by a good assembly programmer. Most of the Linux kernel is written in the C language. The following C fragment:

if (x != y)

x = y ;

performs exactly the same operations as the previous example assembly code. If the contents of the variable x are not the same as the contents of variable y then the contents of y will be copied to x. C code is organized into routines, each of which perform a task. Routines may return any value or data type supported by C. Large programs like the Linux kernel comprise many separate C source modules each with its own routines and data structures. These C source code modules group together logical functions such as filesystem handling code.

C supports many types of variables, a variable is a location in memory which can be referenced by a symbolic name. In the above C fragment x and y refer to locations in memory. The programmer does not care where in memory the variables are put, it is the linker (see below) that has to worry about that. Some variables contain different sorts of data, integer and floating point and others are pointers.

Pointers are variables that contain the address, the location in memory of other data. Consider a variable called x, it might live in memory at address 0x80010000. You could have a pointer, called px, which points at x. px might live at address 0x80010030. The value of px would be 0x80010000: the address of the variable x.

C allows you to bundle together related variables into data structures. For example,

struct {

int i ;

char b ;

} my_struct ;

is a data structure called my_struct which contains two elements, an integer (32 bits of data storage) called i and a character (8 bits of data) called b.

2.1.3 Linkers

Linkers are programs that link together several object modules and libraries to form a single, coherent, program. Object modules are the machine code output from an assembler or compiler and contain executable machine code and data together with information that allows the linker to combine the modules together to form a program. For example one module might contain all of a program's database functions and another module its command line argument handling functions. Linkers fix up references between these object modules, where a routine or data structure referenced in one module actually exists in another module. The Linux kernel is a single, large program linked together from its many constituent object modules.

2.2 What is an Operating System?

Without software a computer is just a pile of electronics that gives off heat. If the hardware is the heart of a computer then the software is its soul. An operating system is a collection of system programs which allow the user to run application software. The operating system abstracts the real hardware of the system and presents the system's users and its applications with a virtual machine. In a very real sense the software provides the character of the system. Most PCs can run one or more operating systems and each one can have a very different look and feel. Linux is made up of a number of functionally separate pieces that, together, comprise the operating system. One obvious part of Linux is the kernel itself; but even that would be useless without libraries or shells.

In order to start understanding what an operating system is, consider what happens when you type an apparently simple command:

$ ls

Mail c images perl

docs tcl

The $ is a prompt put out by a login shell (in this case bash). This means that it is waiting for you, the user, to type some command. Typing ls causes the keyboard driver to recognize that characters have been typed. The keyboard driver passes them to the shell which processes that command by looking for an executable image of the same name. It finds that image, in /bin/ls. Kernel services are called to pull the ls executable image into virtual memory and start executing it. The ls image makes calls to the file subsystem of the kernel to find out what files are available. The filesystem might make use of cached filesystem information or use the disk device driver to read this information from the disk. It might even cause a network driver to exchange information with a remote machine to find out details of remote files that this system has access to (filesystems can be remotely mounted via the Networked File System or NFS). Whichever way the information is located, ls writes that information out and the video driver displays it on the screen.

All of the above seems rather complicated but it shows that even most simple commands reveal that an operating system is in fact a co-operating set of functions that together give you, the user, a coherent view of the system.

2.2.1 Memory management

With infinite resources, for example memory, many of the things that an operating system has to do would be redundant. One of the basic tricks of any operating system is the ability to make a small amount of physical memory behave like rather more memory. This apparently large memory is known as virtual memory. The idea is that the software running in the system is fooled into believing that it is running in a lot of memory. The system divides the memory into easily handled pages and swaps these pages onto a hard disk as the system runs. The software does not notice because of another trick, multi-processing.

2.2.2 Processes

A process could be thought of as a program in action, each process is a separate entity that is running a particular program. If you look at the processes on your Linux system, you will see that there are rather a lot. For example, typing ps shows the following processes on my system:

第二章软件基础

程序就是一组执行特定任务的计算机指令。程序既可以用非常低级的计算机语言——汇编语言，也可以用高级的、独立于机器的语言如C语言来编写。操作系统是一种特殊的程序，它允许用户运行各种应用程序如制表程序和字处理程序。本章介绍基本的程序设计原理，并对操作系统的目标和功能做一综述。

2.1 计算机语言

2.1.1 汇编语言

CPU从内存中取出并运行的指令对人来说根本无法理解。它们是精确指示机器如何操作的机器代码。例如，十六进制数0x89E5是Intel 80486的一条指令，它指示把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核心只有很少的一点用汇编语言编写，目的是为了效率，或者用在一些与特定处理器相关的地方。

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支持很多类型的变量。所谓变量，就是内存中的一个位置，可以用符号名字来引用。在以上C片段中，x和y指引了内存中的位置。程序员不关心变量究竟存放在内存中的何处，这是连接器（见下面所述）的任务。一些变量含有不同类型的数据，整数和浮点数，另一些则是指针。

指针就是包含地址——其它数据在内存中的位置——的变量。考虑叫做x的变量，它可能处于内存地址0x80010000。你可以有一个指针，叫做px，指向x。px可能处于地址0x80010030，而px的值是0x80010000，即变量x的地址。

C允许你把相关的变量绑在一起，形成数据结构。例如，

struct {

int i ;

char b ;

} my_struct ;

是一个叫做my_struct的数据结构，它包含两个元素：一个叫做i的整数（32位数据）和一个叫做b的字符（8位数据）。

2.1.3 连接器

连接器是一种程序，它可以把几个目标模块和库连接在一起，产生一个独立的、连贯的程序。目标模块是汇编器或编译器生成的机器代码输出，含有可执行的机器代码和数据，以及允许连接器把模块连接起来的信息。例如一个模块可能含有程序中所有的数据库函数，而另外一个则含有命令行参数处理函数。连接器负责解决目标模块之间的引用，例如一个模块中引用的例程或数据结构事实上在另外一个模块之中。Linux核心就是一个与很多成员目标模块连接在一起的独立的大程序。

2.2 什么是操作系统？

没有软件的计算机就是一堆发热的电子器件。如果说硬件是计算机的核心，那么软件就是计算机的灵魂。所谓操作系统，就是允许用户在其上运行应用软件的一组系统程序。操作系统对系统的真正硬件进行抽象，向系统的用户和应用程序给出一个虚拟机。在很现实的意义上说，软件提供了系统的特点。绝大部份PC能运行一个或多个操作系统，每一个操作系统都有一个完全不同的外观和风格。Linux是由一批功能上分离的部件组成，其中明显的一个是核心本身。但是即使是核心，如果脱离库和外壳程序（编者注：其实就是Shell程序，这里编者认为不译最好，但考虑到不少材料都将其译成外壳程序，也为了尊重原作者故而未做改动。另外本文不少地方将Kernel译为核心，其实就是常说的内核）也是没有用的。

为了开始理解什么是操作系统，请考虑当你敲入以下的简单命令时会发生的情况：

$ ls

Mail c images perl

docs tcl

这里$是由登录外壳程序（在此例为bash）给出的提示符。这意味着它在等待你——用户——敲入命令。敲入ls后，键盘驱动程序识别出已经有字符输入。键盘驱动程序把这些字符传给外壳程序，外壳程序则通过寻找可执行程序的映像来处理这个命令。它在/bin/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

If my system had many CPUs then each process could (theoretically at least) run on a different CPU. Unfortunately, there is only one so again the operating system resorts to trickery by running each process in turn for a short period. This period of time is known as a time-slice. This trick is known as multi-processing or scheduling and it fools each process into thinking that it is the only process. Processes are protected from one another so that if one process crashes or malfunctions then it will not affect any others. The operating system achieves this by giving each process a separate address space which only they have access to.

2.2.3 Device drivers

Device drivers make up the major part of the Linux kernel. Like other parts of the operating system, they operate in a highly privileged environment and can cause disaster if they get things wrong. Device drivers control the interaction between the operating system and the hardware device that they are controlling. For example, the filesystem makes use of a general block device interface when writing blocks to an IDE disk. The driver takes care of the details and makes device specific things happen. Device drivers are specific to the controller chip that they are driving which is why, for example, you need the NCR810 SCSI driver if your system has an NCR810 SCSI controller.

2.2.4 The Filesystems

In Linux, as it is for Unix, the separate filesystems that the system may use are not accessed by device identifiers (such as a drive number or a drive name) but instead they are combined into a single hierarchical tree structure that represents the filesystem as a single entity. Linux adds each new filesystem into this single filesystem tree as they are mounted onto a mount directory, for example /mnt/cdrom. One of the most important features of Linux is its support for many different filesystems. This makes it very flexible and well able to coexist with other operating systems. The most popular filesystem for Linux is the EXT2 filesystem and this is the filesystem supported by most of the Linux distributions.

A filesystem gives the user a sensible view of files and directories held on the hard disks of the system regardless of the filesystem type or the characteristics of the underlying physical device. Linux transparently supports many different filesystems (for example MS-DOS and EXT2) and presents all of the mounted files and filesystems as one integrated virtual filesystem. So, in general, users and processes do not need to know what sort of filesystem that any file is part of, they just use them.

The block device drivers hide the differences between the physical block device types (for example, IDE and SCSI) and, so far as each filesystem is concerned, the physical devices are just linear collections of blocks of data. The block sizes may vary between devices, for example 512 bytes is common for floppy devices whereas 1024 bytes is common for IDE devices and, again, this is hidden from the users of the system. An EXT2 filesystem looks the same no matter what device holds it.

2.3 Kernel Data Structures

The operating system must keep a lot of information about the current state of the system. As things happen within the system these data structures must be changed to reflect the current reality. For example, a new process might be created when a user logs onto the system. The kernel must create a data structure representing the new process and link it with the data structures representing all of the other processes in the system.

Mostly these data structures exist in physical memory and are accessible only by the kernel and its subsystems. Data structures contain data and pointers: addresses of other data structures or the addresses of routines. Taken all together, the data structures used by the Linux kernel can look very confusing. Every data structure has a purpose and although some are used by several kernel subsystems, they are more simple than they appear at first sight.

Understanding the Linux kernel hinges on understanding its data structures and the use that the various functions within the Linux kernel makes of them. This book bases its description of the Linux kernel on its data structures. It talks about each kernel subsystem in terms of its algorithms, its methods of getting things done, and their usage of the kernel's data structures.

2.3.1 Linked Lists

Linux uses a number of software engineering techniques to link together its data structures. On a lot of occasions it uses linked or chained data structures. If each data structure describes a single instance or occurrence of something, for example a process or a network device, the kernel must be able to find all of the instances. In a linked list a root pointer contains the address of the first data structure, or element, in the list and each data structure contains a pointer to the next element in the list. The last element's next pointer would be 0 or NULL to show that it is the end of the list. In a doubly linked list each element contains both a pointer to the next element in the list but also a pointer to the previous element in the list. Using doubly linked lists makes it easier to add or remove elements from the middle of list although you do need more memory accesses. This is a typical operating system trade off: memory accesses versus CPU cycles.

2.3.2 Hash Tables

Linked lists are handy ways of tying data structures together but navigating linked lists can be inefficient. If you were searching for a particular element, you might easily have to look at the whole list before you find the one that you need. Linux uses another technique, hashing to get around this restriction. A hash table is an array or vector of pointers. An array, or vector, is simply a set of things coming one after another in memory. A bookshelf could be said to be an array of books. Arrays are accessed by an index, the index is an offset into the array. Taking the bookshelf analogy a little further, you could describe each book by its position on the shelf; you might ask for the 5th book.

A hash table is an array of pointers to data structures and its index is derived from information in those data structures. If you had data structures describing the population of a village then you could use a person's age as an index. To find a particular person's data you could use their age as an index into the population hash table and then follow the pointer to the data structure containing the person's details. Unfortunately many people in the village are likely to have the same age and so the hash table pointer becomes a pointer to a chain or list of data structures each describing people of the same age. However, searching these shorter chains is still faster than searching all of the data structures.

As a hash table speeds up access to commonly used data structures, Linux often uses hash tables to implement caches. Caches are handy information that needs to be accessed quickly and are usually a subset of the full set of information available. Data structures are put into a cache and kept there because the kernel often accesses them. There is a drawback to caches in that they are more complex to use and maintain than simple linked lists or hash tables. If the data structure can be found in the cache (this is known as a cache hit), then all well and good. If it cannot then all of the relevant data structures must be searched and, if the data structure exists at all, it must be added into the cache. In adding new data structures into the cache an old cache entry may need discarding. Linux must decide which one to discard, the danger being that the discarded data structure may be the next one that Linux needs.

2.3.3 Abstract Interfaces

The Linux kernel often abstracts its interfaces. An interface is a collection of routines and data structures which operate in a particular way. For example all network device drivers have to provide certain routines in which particular data structures are operated on. This way there can be generic layers of code using the services (interfaces) of lower layers of specific code. The network layer is generic and it is supported by device specific code that conforms to a standard interface.

Often these lower layers register themselves with the upper layer at boot time. This registration usually involves adding a data structure to a linked list. For example each filesystem built into the kernel registers itself with the kernel at boot time or, if you are using modules, when the filesystem is first used. You can see which filesystems have registered themselves by looking at the file /proc/filesystems. The registration data structure often includes pointers to functions. These are the addresses of software functions that perform particular tasks. Again, using filesystem registration as an example, the data structure that each filesystem passes to the Linux kernel as it registers includes the address of a filesystem specific routine which must be called whenever that filesystem is mounted.

如果我的系统有很多CPU，每个进程（至少在理论上）可以运行在一个不同的CPU上。不幸的是，我只有一个CPU，所以系统只能求助于让每个进程轮流运行一小段时间的办法。这一小段时间称为时间片。这种技巧称为多道处理或者调度，它使得每个进程以为自己是唯一的进程。在进程之间进行保护，以便当一个进程崩溃或者错误时，不会影响其它进程。操作系统给每个进程一个单独的、只有它自己能存取的地址空间，以达到这样的目的。

2.2.3 设备驱动程序

设备驱动程序构成了Linux核心的主要部份。就像操作系统的其它部份一样，设备驱动程序在高特权级的环境下运行，一旦发生错误就可能造成危险。设备驱动程序控制操作系统和其控制的硬件设备之间的互相作用。例如，在把块写到IDE硬盘时，文件系统使用一个通用块设备接口。驱动程序负责细节，控制与设备相关的事情。设备驱动程序是针对其控制的特定芯片的，所以如果你有一个NCR810 SCSI控制器，那么你就需要一个NCR810 SCSI驱动程序。

2.2.4 文件系统

在Linux中，就像在Unix中一样，系统可以使用的不同的文件系统，并非通过设备标识来存取（例如驱动器号或驱动器名），而是被组织在一个单一的分层树结构里，每个文件系统用一个实体来表示。文件系统通过把新的文件系统mount在某个目录下——例如/mnt/cdrom，从而把新的文件系统加入树中。Linux的最重要特点之一是支持多个不同的文件系统，这使得其灵活性好，易于与其它操作系统共存。最广为人知的Linux文件系统是EXT2，受到所发行的绝大部份的Linux的支持。

文件系统屏蔽了下层物理设备或文件系统类型的细节，给予用户察看硬盘上文件和目录的一个清楚视角。Linux透明地支持多种不同文件系统（例如MS-DOS和EXT2），并把所有mount上的文件和文件系统都组织在一个虚拟文件系统之中。所以，一般而言，用户和进程并不需要知道哪个文件在哪个文件系统之中，只需要直接去用它就可以了。

块设备驱动程序隐藏了物理块设备类型之间的差别（例如IDE和SCSI的差别），从文件系统的角度来看，物理设备只是数据块的线形聚集。不同设备的块大小不同，例如软盘通常是512字节，而IDE设备通常是1024字节，但是系统的用户是看不到这一点的。无论放在什么设备上，EX2文件系统看起来都一样。

2.3 核心数据结构

操作系统必须保存关于系统当前状态的很多信息。在系统中发生了事情之后，这些数据结构必须修改，以反映当前的真实状况。例如，在一个用户登录到系统之后，可能会创建一个新的进程。核心必须创建表示新进程的数据结构，并把它和表示系统中所有其它进程的数据结构连接在一起。

通常这些数据结构存在于物理内存之中，只能由核心及其子系统存取。数据结构包括数据和指针——其它数据结构的地址或例程的地址。总而言之，Linux使用的数据结构看起来很复杂难懂。虽然其中某些可能为几个核心子系统所使用，但是每个数据结构都有其目的，所以这些数据结构事实上比刚看起来要简单。（以上一句是根据译者的理解翻译，未必正确和符合原文——译者注）

理解Linux核心依赖于理解其数据结构以及核心中各种函数对数据结构的使用。本书对Linux核心的描述就是基于其数据结构的。本书讨论了每个核心子系统的算法、完成工作的方法和对核心数据结构的使用。

2.3.1 链表

Linux使用一系列软件工程技术来把数据结构连接起来。在很多情况下要使用链式的数据结构。如果每个数据结构描述某事物的一个实例或一次发生，例如一个进程或一个网络设备，那么核心就必须能够找到所有的实例。在链表中，根指针含有表中第一个数据结构，或者称为“元素”的地址，而每个数据结构都含有一个指向表中下一个元素的next指针。最后一个元素的next指针为0或NULL，以示它已经是表尾。在双链表中，每个元素含有指向表中下一个元素的next指针和指向表中前一个元素的previous指针。使用双链表方便了增加或删除表中间的元素，当然，内存的存取也增加了。这是一个典型的操作系统中的折中：消耗内存存取与消耗CPU周期的折中。

2.3.2 Hash表

链表可以方便地把数据结构绑在一起，但是浏览链表效率很低。如果你想查找特定的一个元素，很可能不得不看完全表才找到需要的那个。Linux使用Hash技术来避开这个限制。所谓Hash表，是一个指针的数组或者向量。这里说的数组或者向量，是指内存中的一组顺序存放的东西。因此，书架可以说成是书的数组。数组使用索引进行存取，而索引就是数组中位置的偏移量。把书架的比喻继续下去，你可以通过在书架上的位置来描述每本书。例如，你可以要求拿第5本书。

所谓Hash表，是指向数据结构的指针数组，采用数据结构中的信息作为Hash表的索引。如果你有描述村庄人口的数据结构，那么你可以采用人的年龄作为索引。为了寻找某个特定人的数据，你可以采用年龄作为人口Hash表的索引，然后按照指针找到含有此人详细情况的数据结构。（这里的指针相当于普通教科书上所说的Hash函数：Hash(ad)=“*ad”，——译者注）不幸的是，很可能村中的许多人年龄相同，所以Hash表的指针成了指向一个数据结构链的指针，链上的每个数据结构描述相同年龄的一个人。然而，搜索这些短链还是比搜索全部数据结构要快。

由于Hash表加快了普通数据的存取，Linux经常使用Hash表来实现cache。cache通常是总体信息的一部份，被抽出来需要加速存取。操作系统常用的数据结构常常放在cache中保存。cache的不利之处在于使用和维护都比简单链表或Hash表更加复杂。假如能在cache 中找到数据结构（称为“命中”），那么好得很。假如找不到，那么所有相关数据结构都要被搜索，如果最终能找到，那么该数据结构将被加入cache中。把新的数据结构加入cache，可能会需要淘汰cache中一项旧的数据结构。Linux必须决定到底淘汰哪一个才好，以尽可能避免恰恰淘汰出下闪马上要用的数据结构。

2.3.3 抽象接口

Linux核心经常对接口进行抽象。所谓接口，是例程和数据结构的集合，它通过某种特定方式进行操作。例如，所有的网络设备驱动程序必须提供操作某些特定数据结构的某些特定例程。在这种方式下，存在一些使用低层特殊代码提供的服务（接口）的通用代码层。例如网络层是通用的，受到遵循标准接口的与设备相关的代码的支持。(编者注：这几句话直译不太好理解，其实就是说下面的底层代码是与硬件相关的，但他们提供的服务却是标准化了的，与硬件无关的，这种服务就是一种被抽象了的接口。)

通常这些低层在启动时注册到高层。注册时一般要把一个数据结构加到一个链表中。例如，核心中内置的每个文件系统在启动时或者（如果使用模块的话）首次使用时注册到核心。通过查看文件

/proc/filesystems能够看到哪些文件系统已经注册了。注册的数据结构通常包含函数指针。这些函数指针都是进行特定任务的软件函数的地址。再次用文件系统注册作为一个例子，每个文件系统在注册时传给Linux核心的数据结构包含与文件系统相关的函数地址，这些函数在该文件系统mount时必须被调用。

【未完待续·责任编辑：iamxiaohan@hitbbs】