-
-
手机阅读
操作系统必须保持许多关于系统当前状态的信息。随着系统中事件的发生，这些数据结
构也要被改变以反映当前现实。例如，当一个用户登录系统时，一个进程可能被创建。内核
必须创建一个表示这个进程的数据结构并把它链接到表示系统中其它所有进程的数据结构上。
通常这些数据结构存在于物理内存中，并且只能被内核及其子系统访问。数据结构包含
数据和指针，其它数据结构或例程的地址。
放在一起，L i n u x内核使用的数据结构看起来会很迷惑。每个数据结构有自己的用途。尽
管有些是被几个内核子系统使用，但它们比乍一看起来要简单得多。
理解L i n u x内核关键是理解它的数据结构及L i n u x内核用它们所完成的功能。本书把对
L i n u x内核的描述建立在其数据结构的基础上。本书通过算法、完成功能的方法以及对数据结
构的使用等来讨论每个内核子系统。
1. 链表
L i n u x使用一些软件工程技巧来把数据结构链接在一起。在许多情况下它使用链接的
( l i n k e d )或链状的( c h a i n e d )数据结构。若每个数据结构描述某个事物的单个实例或出现，内核
必须能够找到所有的实例。在链表中一个根指针包含表中第一个数据即元素的地址，而每个
数据结构包含一个指针指向表中下一个元素。最后一个元素的下一个指针为空，这意味着它
是表中的最后一个元素。双向链表包含一个指针指向表中下一个元素，同时包含一个指针指
向表中前一个元素。使用双向链表使得在表的中间添加或删除元素变得容易，尽管需要更多
访存操作。这是一个典型的操作系统折衷：以内存访问换取C P U周期。
2. 散列表
链表是一种把数据结构链在一起的简便方法，但查找链表的效率会很低。如果你正在搜
索一个特定元素，可能看完整个表才找到所需要的。L i n u x使用另一种技巧—散列( h a s h i n g )
来解除这种限制。一个散列表是一个指针的数组或向量。数组或向量就是在内存中一个换一
个的事物的简单集合。一个书架(上的书)可以说是一个书的数组。数组通过索引来访问，索引
就是数组的偏移。进一步拿书架作类比，你可以通过它在书架上的位置来描述每本书，比如
你可能要第5本书。
散列表是数据结构指针的数组，而它的索引是通过这些数据结构中的信息导出的。如果
你用一个数据结构描述一个村子的人口，那么就可以人的年龄作为索引。为了找到一个特定
的人的数据就可以用他的年龄作为人口散列表的索引，然后沿着指针找到包含该人的细节的
数据结构。不幸的是一个村的许多人很可能具有相同的年龄，所以散列表中的指针成为指向
数据结构链或表的指针，每个数据结构描述同年龄的一个人。搜索这些短的链仍比搜索全部
数据结构快得多。
因为散列表加速了对经常使用的数据结构的访问， L i n u x经常使用散列表来实现高速缓存，
高速缓存是需要快速访问的信息，并且通常是可以得到的完整信息集合的一个子集。数据结
构被放进高速缓存并保留在那里，因为内核要经常访问它们。高速缓存有一个缺点就是它们
在使用和维护上比简单链表或散列表更复杂。如果数据结构能在高速缓存中找到(即高速缓存
命中)，那一切都好。否则，所有相关的数据结构都要被搜索，并且，如果该数据结构确实存
在，它就必须被加入到高速缓存中。在向高速缓存中加入新数据结构时，一个老的数据结构
可能会被淘汰出去。L i n u x必须决定淘汰哪一个，而危险在于淘汰的数据结构可能正是L i n u x
下一个所需要的。
3. 抽象接口
L i n u x内核经常抽象其接口。接口是按特定方式操作的例程和数据结构的集合。例如所有
的网络设备驱动程序必须提供一定的例程，在这些例程中操作特定的数据结构。在这种方式
下可以有使用专用代码的低层的服务(接口)的通用层代码。网络层是通用的，它被遵守标准接
口的设备专用代码支持。
通常这些低层在启动时向高层注册( r e g i s t e r )。这种注册通常涉及向一个链表中加入一个数
据结构。例如，内核中每个文件系统在启动时向内核注册自己；或者，如果你在使用模块，
当该文件系统首次被使用时注册。通过查看文件/ p r o c / f i l e s y s t e m s你可以发现哪些文件系统注
册了自己。注册数据结构通常包含函数指针。它们就是完成特定任务的软件函数的地址。再
一次以文件系统注册为例，每个文件系统在注册时传给内核的数据结构包含文件系统专用例
程的地址，当文件系统被安装时，这些例程将被调用。