极限首页 业界焦点 软件工程师之路 系统工程师之路 网络工程师之路 软件下载 技术社区
 bash编程学习笔记(一)
 RPM 打包技术与典型 SPEC
 Linux Kernel核心中文手册
 精通递归程序设计
 Linux Kernel核心中文手册
 Linux/Unix环境下的make命
 Linux Kernel核心中文手册
 bash编程学习笔记(二)
 Linux Kernel核心中文手册
 Linux操作系统内核编译详解
 bash编程学习笔记(一)
 RPM 打包技术与典型 SPEC
 Linux Kernel核心中文手册
 精通递归程序设计
 Linux Kernel核心中文手册
 Linux/Unix环境下的make命
 Linux Kernel核心中文手册
 bash编程学习笔记(二)
 Linux Kernel核心中文手册
 Linux操作系统内核编译详解

Shell 中文手册

Python 2.3 中文手册

Python 2.4 中文手册

Mysql 4.x 中文手册

PHP 4.x 中文手册

Apache 2.x 中文手册
更多手册

站内搜索:
当前位置:首页>>软件工程师之路>>编程进阶>>正文
Linux Kernel核心中文手册(1、2)
时间:2005-11-08 作者:未知 来源:未知

  Chapter 1

 

Hardware Basic(硬件基础知识)

 

一个操作系统必须和作为它的基础的硬件系统紧密配合。操作系统需要使用一些只有硬件才能提供的功能。为了完整的了解Linux,你需要了解底层硬件的基础知识。本章对于现代PC的硬件进行了。

1975年1月“Popular Electronics”杂志封面上印出了Altair 8080的图片,一场革命开始了。

Altair 8080,跟随早期的“Star Trek epsode”命名,只需要$397,就可由个人电子爱好者自己组装。它拥有Intel 8080处理器和256字节内存,但是没有屏幕和键盘。以今天的标准来衡量,它太简陋了。它的发明者,Ed Roberts,制造了名词“personal computer“来命名他的发明,但现在,PC这个名词已经用来命名几乎所有你可以不依靠帮助就可以自己运行起来的计算机。用这个定义,甚至一些十分强 大的Alpha AXP系统也是PC。

爱好者们看到了Altair的潜力,开始为它写软件,制造硬件。对于这些早期的先驱来讲,它代表着自由:从被神职人员控制和运行的大型批处理的主机 系统中逃脱出来的自由。你可以在自己家里甚至厨桌上拥有计算机,这使学院的退学生为此着迷并通宵达旦。与此同时出现大量硬件,在一定程度上各自不同,而软 件专家则乐于为这些新机器撰写软件。有讽刺意味的是,IBM在1981年发布了IBM PC并于1982年早期供货,从此定义了现代PC的模型。它拥有Intel 8088处理器,64K内存(可以扩充到256K),两个软驱和一个80x25的彩色图卡(CGA),用今天的标准衡量,它功能不算很强,但是它销售的不 错。1983年,紧接着推出的IBM PC-XT,则拥有一个豪华的10M硬盘。不久大批公司如Compaq开始制造IBM PC的复制品,PC的结构成为了事实的标准。这个事实的标准使大批硬件公司可以在这个不断增长的市场上一起竞争,反过来,可以遏制价格,让用户满意。现代 PC承袭了早期PC的许多系统体系特征。甚至基于最强大的Intel Pentium Pro的系统也可以运行Intel 8086的寻址模式。当Linus Torvalds开始开发后来的Linux时,他选择了当时最常见和价格最合理的硬件平台:一台Intel 80386 PC。

从PC的外面看,最明显的部件就是机箱、键盘、鼠标和显示器。在机箱的前面有一些按钮,一个小屏幕显示一些数字,还有一个软驱。现在的大多数系统还有一个CD-ROM期、驱动器。如果你需要保护你的数据,那么还会有一个备份用的磁带机。这些设备一律被看作外设。

虽然CPU管理整个系统,但它并不是唯一的智能设备。所有的外设控制器,例如IDE控制器,也都拥有一定程度的智能。在PC内部(图1.1),你可 以看到一个主板,包括CPU或微处理器、内存和一些ISA或PCI外设控制卡的槽位。其中一些控制器,如IDE磁盘控制器可能内置在系统主板上。

 


CPU

 

CPU,或者说微处理器,是所有计算机系统的心脏。微处理器进行数学运算,逻辑操作并从内存中读取指令并执行指令,进而控制数据流向。计算机发展的 早期,微处理器的各种功能模块是由相互分离(并且尺寸上十分巨大)的单元构成。这也是名词“中央处理单元”的起源。现代的微处理器将这些功能模块集中在一 块非常小的硅晶片制造的集成电路上。在本书,名词CPU、微处理器和处理器交替使用。 微处理器处理二进制数据:这些数据由1和0组成。这些1和0对应电气开关的开或关。就好像42代表4个10和2个单元,二进制数字由一系列代表2的幂数的 数字组成。这里,幂数意味着一个数字用自身相乘的次数。10 的一次幂是10,10的2次幂是10x10,10的3次幂是10x10x10,依此类推。二进制0001是十进制1是十进制2,二进制0011是十进制 3,二进制0100是十进制4,等等。所以,十进制42是二进制101010或者(2+8+32或21+23+25)。在计算机程序除了使用二进制表示数 字之外,另一种基数,16进制,也经常用到。在这种进制中,每一位数字表示16的幂数。因为十进制数字只是从0到9,在十六进制中10到15分别用字母 A,B,C,D,E,F表示。例如,十六进制的E是十进制的14,而十六进制的2A是十进制的42(2个16+10)。用C语言的表示法(本书一直使 用),十六进制数字使用前缀“0x”:十六进制的2A写做0x2A。

 

微处理器可以执行算术运算如加、乘和除,也可以执行逻辑操作例如“X是否大于Y”。

处理器的执行由外部时钟控制。这个时钟,即系统时钟,对处理器产生稳定的时钟脉冲,在每一个时钟脉冲里,处理器执行一些工作。例如,处理器可以在每 一个时钟脉冲里执行一条指令。处理器的速度用系统时钟的频率来描述。一个100Mhz的处理器每秒钟接受到100,000,000次时钟脉冲。用时钟频率 来描述CPU的能力是一种误解,因为不同的处理器在每一次时钟脉冲中执行的工作量不同。虽然如此,如果所有的条件同等,越快的时钟频率表示处理器的能力越 强。处理器执行的指令非常简单,例如:“把内存位置X的内容读到寄存器Y中“。寄存器是微处理器的内部存储空间,用来存储数据并进行操作。执行的操作可能 使处理器停止当前操作而转去执行内存中其他地方的指令。正是这些微小的指令集合在一起,赋予现代的微处理器几乎无限的能力,因为它每秒可以执行数百万甚至 数十亿的指令。

 

执行指令时必须从内存中提取指令,指令自身也可能引用内存中的数据,这些数据也必须提取到内存中并在需要的时候保存到内存中去。

 

一个微处理器内部寄存器的大小、数量和类型完全决定于它的类型。一个Intel 80486处理器和一个Alpha AXP处理器的寄存器组完全不同。另外,Intel是32位宽而Alpha AXP是64位宽。但是,一般来讲,所有特定的处理器都会有一些通用目的的寄存器和少量专用的寄存器。大多数处理器拥有以下特殊用途的专用的寄存器:

 

Program Counter(PC)程序计数器

这个寄存器记录了下一条要执行的指令的地址。PC的内容在每次取指令的时候自动增加。

Stack Pointer(SP)堆栈指针

处理器必须能够存取用于临时存储数据的大容量的外部读写随机存取内存(RAM)。堆栈是一种用于在外部内存中存放和恢复临时数据的方法。通常,处理 器提供了特殊的指令用于将数据压在堆栈中,并在以后需要是取出来。堆栈使用LIFO(后进先出)的方式。换句话说,如果你压入两个值x和y到堆栈中,然后 从堆栈中弹出一个值,那么你会得到y的值。

一些处理器的堆栈向内存顶部增长,而另一些向内存的底部增长。还有一些处理器两种方式都可以支持,例如:ARM。

 

Processor Status(PS)

指令可能产生结果。例如:“X寄存器的内容是否大于Y寄存器的内容?“可能产生真或假的结果。PS寄存器保留这些结果以及处理器当前状态的其他信息。多数处理器至少有两种模式:kernel(核心态)和user(用户态),PS寄存器会纪录能够确定当前模式的那些信息。

 


Memory(内存)

 

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

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

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

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

 


Buses(总线)

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

 


Controllers and Peripherals (控制器和外设)

 

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

 

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

 


Address Spaces(寻址空间)

 

连接CPU和主内存的系统总线以及连接CPU和系统硬件外设的总线是分离的。硬件外设所拥有的内存空间称为I/O空间。I/O空间本身可以再进一步 划分,但是我们现在先不讨论。CPU可以访问系统内存空间和I/O空间,而控制器只能通过CPU间接访问系统内存。从设备的角度来看,比如软驱控制器,它 只能看到它的控制寄存器所在的地址空间(ISA),而非系统内存。一个CPU用不同的指令去访问内存和I/O空间。例如,可能有一条指令是“从I/O地址 0x3f0读取一个字节到X寄存器“。这也是CPU通过读写系统硬件外设处于I/O地址空间的寄存器从而控制外设的方法。在地址空间中,普通外设(如 IDE控制器,串行端口,软驱控制器等等)的寄存器在PC外设的多年发展中已经成了定例。I/O空间的地址0x3f0正是串行口(COM1)的控制寄存器 的地址。

 

有时控制器需要直接从系统内存读取大量内存,或直接写大量数据到系统内存中去。比如将用户数据写到硬盘上去。在这种情况下,使用直接内存存取(DMA)控制器,允许硬件设备直接存取系统内存,当然,这种存取必须在CPU的严格控制和监管下进行。

 


Timer(时钟)

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

 

 

Chapter 2

 

Software Basic(软件基础)

程序是用于执行特定任务的计算机指令组合。程序可以用汇编语言,一种非常低级的计算机语言来编写,也可以使用和机器无关的高级语言,比如C语言编 写。操作系统是一个特殊的程序,允许用户通过它运行应用程序,比如电子表和文字处理等等。本章介绍了基本的编程原理,并简介操作系统的目的和功能。

 

2.1 Computer Languages(计算机语言)

 

2.1.1.汇编语言

 

CPU从内存中读取和执行的指令对于人类来讲无法理解。它们是机器代码,精确的告诉计算机要做什么。比如十六进制数0x89E5,是Intel 80486的指令,将寄存器ESPEBP中。早期计算机中最初的软件工具之一是汇编程序,它读入人类可以阅读的源文件,将其装配成机器代码。汇编语言明确 地处理对寄存器和对数据的操作,而这种操作对于特定的微处理器而言是特殊的。Intel X86微处理器的汇编语言和Alpha AXP微处理器的汇编语言完全不同。以下Alpha AXP汇编代码演示了程序可以执行的操作类型:

 

Ldr r16, (r15) ; 第一行

Ldr r17, 4(r15) ; 第二行

Beq r16,r17,100; 第三行

Str r17, (r15); 第四行

100: ; 第五行

 

第一条语句(第一行)将寄存器15指定的地址中的内容加载到寄存器16中。第二条指令将紧接着的内存中的内容加载到寄存器17中。第三行比较寄存器 16和寄存器17,如果相等,分支到标号100,否则,继续执行第四行,将寄存器17的内容存到内存中。如果内存中的数据相同,就不必存储数据。编写汇编 级的程序需要技巧而且十分冗长,容易出错。Linux系统的核心很少的一部分是用汇编语言编写,而这些部分之所以使用汇编语言只是为了提高效率,并且和具 体的微处理器相关。

 

2.1.2 The C Programming Language and Compiler (C语言和编译器)

 

使用汇编语言编写大型程序十分困难,消耗时间,容易出错而且生成的程序不能移植,只能束缚在特定的处理器家族。更好的选择是使用和机器无关的语言, 例如C。C允许你用逻辑算法描述程序和要处理的数据。被称为编译程序(compiler)的特殊程序读入C程序,并将它转换为汇编语言,进而产生机器相关 的代码。好的编译器生成的汇编指令可以和好的汇编程序员编写的程序效率接近。大部分Linux核心是用C语言编写的。以下的C片断:

if (x != y)

x = y;

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

 

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

 

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

 

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

Struct {

Int I;

Char b;

} my_struct;

是一个叫做my_struct的数据结构,包括两个元素:一个整数(32位)I和一个字符(8位数据)b。

 

2.1.3 Linkers(连接程序)

 

连接程序将几个目标模块和库文件连接在一起成为一个单独的完整程序。目标模块是汇编程序或编译程序的机器码输出,它包括机器码、数据和供连接程序使 用的连接信息。比如:一个目标模块可能包括程序的所有数据库功能,而另一个目标模块则包括处理命令行参数的函数。连接程序确定目标模块之间的引用关系,即 确定一个模块所引用的例程和数据在另一个模块中的实际位置。Linux核心是由多个目标模块连接而成的独立的大程序。

 

2.2 What is an Operating System(什么是操作系统?)

 

没有软件,计算机只是一堆发热的电子元件。如果说硬件是计算机的心脏,则软件就是它的灵魂。操作系统是允许用户运行应用程序的一组系统程序。操作系 统将系统的硬件抽象,呈现在用户和应用程序之前的是一个虚拟的机器。是软件造就了计算机系统的特点。大多数PC可以运行一到多个操作系统,而每一个操作系 统从外观和感觉上都大不相同。Linux由不同功能的部分构成,这些部分总体组合构成了Linux操作系统。Linux最明显的部分就是Kernel自 身,但是如果没有shell或libraries一样没有用处。

 

为了了解什么是操作系统,看一看在你输入最简单的命令时发生了什么:

 

$ls

Mail c images perl

Docs tcl

$

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

 

以上的过程看起来相当复杂,但是它说明了即使是最简单的命令也是操作系统各个功能模块之间共同协作的结果,只有这样才能提供给你(用户)一个完整的系统视图。

 

2.2.1 Memory management(内存管理)

 

如果拥有无限的资源,例如内存,那么操作系统所必须做的很多事情可能都是多余的。所有操作系统的一个基本技巧就是让少量的物理内存工作起来好像有相 当多的内存。这种表面看起来的大内存叫做虚拟内存,就是当软件运行的时候让它相信它拥有很多内存。系统将内存分为容易处理的页,在系统运行时将这些页交换 到硬盘上。而应用软件并不知道,因为操作系统还使用了另一项技术:多进程。

 

2.2.2 Processes (进程)

 

进程可以看作一个在执行的程序,每一个进程都是正在运行的特定的程序的独立实体。如果你观察一下你的Linux系统,你会发现有很多进程在运行。例如:在我的系统上输入ps 显示了以下进程:

$ ps

PID TTY STAT TIME COMMAND

158 pRe 1 0:00 -bash

174 pRe 1 0:00 sh /usr/X11R6/bin/startx

175 pRe 1 0:00 xinit /usr/X11R6/lib/X11/xinit/xinitrc --

178 pRe 1 N 0:00 bowman

182 pRe 1 N 0:01 rxvt -geometry 120x35 -fg white -bg black

184 pRe 1 < 0:00 xclock -bg grey -geometry -1500-1500 -padding 0

185 pRe 1 < 0:00 xload -bg grey -geometry -0-0 -label xload

187 pp6 1 9:26 /bin/bash

202 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black

203 ppc 2 0:00 /bin/bash

1796 pRe 1 N 0:00 rxvt -geometry 120x35 -fg white -bg black

1797 v06 1 0:00 /bin/bash

3056 pp6 3 < 0:02 emacs intro/introduction.tex

3270 pp6 3 0:00 ps

$

 

如果我的系统拥有多个CPU那么每个进程可能(至少在理论上如此)都在不同的CPU上运行。不幸的是,只有一个,所以操作系统又使用技巧,在短时间 内依次运行每一个进程。这个时间段叫做时间片。这种技巧叫做多进程或调度,它欺骗了每一个进程,好像它们是唯一的进程。进程相互之间受到保护,所以如果一 个进程崩溃或不能工作,不会影响其他进程。操作系统通过给每一个进程一个独立的地址空间来实现保护,进程只能访问它自己的地址空间。  

2.2.3 Device Drivers(设备驱动程序)

 

设备驱动程序组成了Linux核心的主要部分。象操作系统的其他部分一样,它们在一个高优先级的环境下工作,如果发生错误,可能会引发严重问题。设 备驱动程序控制了操作系统和它控制的硬件设备之间的交互。比如:文件系统向IDE磁盘写数据块是使用通用块设备接口。驱动程序控制细节,并处理和设备相关 的部分。设备驱动程序和它驱动的具体的控制器芯片相关,所以,如果你的系统有一个NCR810的SCSI控制器,那么你需要NCR810的驱动程序。

 

2.2.4 The Filesystems(文件系统)

 

象Unix一样,在Linux里,系统对独立的文件系统不是用设备标示符来存取(比如驱动器编号或驱动器名称),而是连接成为一个树型结构。 Linux在安装新的文件系统时,把它安装到指定的安装目录,比如/mnt/cdrom,从而合并到这个单一的文件系统树上。Linux的一个重要特征是 它支持多种不同的文件系统。这使它非常灵活而且可以和其他操作系统良好共存。Linux最常用的文件系统是EXT2,大多数Linux发布版都支持。

 

文件系统将存放在系统硬盘上的文件和目录用可以理解的统一的形式提供给用户,让用户不必考虑文件系统的类型或底层物理设备的特性。Linux透明的 支持多种文件系统(如MS-DOS和EXT2),将所有安装的文件和文件系统集合成为一个虚拟的文件系统。所以,用户和进程通常不需要确切知道所使用的文 件所在的文件系统的类型,用就是了。

 

块设备驱动程序掩盖了物理块设备类型的区别(如IDE和SCSI)。对于文件系统来讲,物理设备就是线性的数据块的集合。不同设备的块大小可能不 同,如软驱一般是512字节,而IDE设备通常是1024字节,同样,对于系统的用户,这些区别又被掩盖。EXT2文件系统不管它用什么设备,看起来都是 一样的。

 

2.3 Kernet Data Structures(核心数据结构)

 

操作系统必须纪录关于系统当前状态的许多信息。如果系统中发生了事情,这些数据结构就必须相应改变以反映当前的实际情况。例如:用户登录到系统中的时候,需要创建一个新的进程。核心必须相应地创建表示此新进程的数据结构,并和表示系统中其他进程的数据结构联系在一起。  

这样的数据结构多数在物理内存中,而且只能由核心和它的子系统访问。数据结构包括数据和指针(其他数据结构或例程的地址)。乍一看,Linux核心 所用的数据结构可能非常混乱。其实,每一个数据结构都有其目的,虽然有些数据结构在多个的子系统中都会用到,但是实际上它们比第一次看到时的感觉要简单的 多。

 

理解Linux核心的关键在于理解它的数据结构和核心处理这些数据结构所用到的大量的函数。本书以数据结构为基础描述Linux核心。论及每一个核心子系统的算法,处理的方式和它们对核心数据结构的使用。

 

2.3.1 Linked Lists(连接表)

 

Linux使用一种软件工程技术将它的数据结构连接在一起。多数情况下它使用链表数据结构。如果每一个数据结构描述一个物体或者发生的事件的单一的 实例,比如一个进程或一个网络设备,核心必须能够找出所有的实例。在链表中,根指针包括第一个数据结构或单元的地址,列表中的每一个数据结构包含指向列表 下一个元素的指针。最后元素的下一个指针可能使0或NULL,表示这是列表的结尾。在双向链表结构中,每一个元素不仅包括列表中下一个元素的指针,还包括 列表中前一个元素的指针。使用双向链表可以比较容易的在列表中间增加或删除元素,但是这需要更多的内存存取。这是典型的操作系统的两难情况:内存存取数还 是CPU的周期数。

 

2.3.2 Hash Tables

 

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

 

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

 

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

 

2.3.3 Abstract Interfaces(抽象接口)

 

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

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

推荐】【 】【关闭


关于极限 | 站内地图 | 意见反馈 | 广告服务 | 数据服务 | 联系我们
本站所刊登的文章,技术资料,软件均整理于网络资源或本站原创,转载请务必联系原作者或本站。
Copyright ? 2001-2004 UPLinux.com All Rights Reserved.
本站唯一联系信箱:
京ICP备05010519