linux 通讯数据缓冲区用动态链表好吗

一个缓冲头结构中标志了对应缓冲块的相关性质，采用缓冲头结构组来对整个缓冲区的缓冲块进行管理， *** 作方便。在缓冲区中，低端存储区存放的是对应缓冲头结构，高端区对应的是缓冲区数据结构，这是在进行缓冲区初始化过程中，初始化程序从整个缓冲区的两端开始，分别同时设置缓冲区头结构和对应的缓冲区。即第一个缓冲区头结构所对应的是最后一个缓冲数据块，如此递推下去。（缓冲块是1024个字节的块）

缓冲头结构的结构分析：

设备号、块号、状态（含有当前缓冲区状态）以及其他一些算法所需要的数据。

高速缓冲块采用hash表和包含所有缓冲区块的链表来进行管理 *** 作。

1块缓冲区即1024个字节，低端（对应各缓冲块的缓冲头结构）分别建立起对应各缓冲块的缓冲头结构buffer_head,这些缓冲头连接成链表，从而对整个缓冲区进行 *** 控。

下面这个是linux0.11内核中所定义的缓冲区头结构：

struct buffer_header{

char *b_data

unsigned short b_dev

unsigned char b_uptodate

unsigned char b_dirt

unsigned chart b_count

unsigned char b_lock

struct task_struct * b_wait

struct buffer_head *b_prev

struct buffer_head *b_next

struct buffer_head *b_prev_free

struct buffer_head *b_next_free

}

(我们所研究的缓冲区是磁盘块在主存中的拷贝，一个缓冲区的数据与文件系统上一个逻辑磁盘块中的数据想对应，并且内核是通过考察缓冲区头部中的标识字符来识别缓冲区内容的。缓冲区的内容并不是永久存在的，而是每隔一定时间间断就会发生更新的区域。)

b_block锁定标志，表示驱动程序正在对该缓冲区内容进行 *** 作，此时该缓冲区不能被第二者访问。这里可以发现，对缓冲区的直接 *** 作是驱动程序，而不是应用程序，应用程序通过调用系统调用来对缓冲区进行相应的 *** 作。

思考：向缓冲块中写数据的写 *** 作不由CPU控制，CPU起到 的只是控制管理功能而已。而缓冲块中写数据写 *** 作则是由硬件来完成，如何为完成？？？

b_count缓冲buffer使用之计数值，表示相应缓冲块正被各个进程使用的次数，主要用于对缓冲块的程序引用计数管理，所谓空闲块指b_count＝0的块。

b_update是数据更新标志，说明缓冲块中数据是否有效。b_dirt和b_update标志的应用是很重要的，同时一很容易弄混淆，b_dirt所起到的作用是当缓冲区中的数据被改变时，相应的b_dir被赋值为1，表明此时缓冲区中的数据与磁盘块中的数据是不同的，这就意味着磁盘中的数据需要重新写，即更新，所使用的是延迟写。而b_update说明缓冲块中的数据是否有效。当我们将释放块时，这两个值被赋为0，表明该缓冲区中的数据无效，这里的释放块指的是将缓冲区的数据进行了释放更新，缓冲区中的数据已经不再被当前进程使用，而磁盘中的数据并没有丢失，只是缓冲区中的数据丢失了而已。当b_dir比指明为1时，用通俗的话说这个块脏了，需要将其中的内容写入磁盘块中，但是此时还没有将其放入到磁盘中，所以数据是无效的。只有当数据被写入到磁盘设备或者是从块设备中读入缓冲块时，数据才是变为有效的。

接下来，来看看缓冲头结构buffer_head结构中字段类型为buffer_head的几个字段的用法,下面这个函数是从linux0.11内核代码中摘录下来的，主要是使用了buffer_head这几个字段来进行 *** 作，很容易理解：

函数的功能是：将缓冲块插入空闲链表尾部，同时放入hash队列中。

static inline void insert_info_queues(struct buffer_head * bh)

{

bh->b_next_free=free_list//将bh指向的下一个节点指定为free_list,即空闲表的头指针；

bh->b_prev_free=free_list->b_prev_free//将bh的后指针指向为之前空闲表的最后一个节点；

free_list->b_prev_free->b_next_free=bh

free_list->b_prev_free=bh

bh->b_prev=NULL

bh->b_next=NULL

if(!bh->b_dev)

return

bh->b_next=hash(bh->b_dev,bh->b_blocknr)

hash(bh->b_dev,bh->b_blocknr)=bh

bh->b_next->b_prev=bh

}

以上的代码程序就是对buffer_head中buffer_head字段的使用，这就是这些字段作用之一，有趣吧!

现在来分析缓冲区所使用的两个数据结构：散列表和空闲表。

缓冲区中的所有块是通过散列表进行管理和 *** 作的，对于磁盘而言，如果要使用散列表来进行管理，其散列表是不变的。但是，高速缓冲区中的散列表是变化着的。散列表的控制 *** 作是由对应的散列函数进行实施的。要注意的是，缓冲块所存在的散列表并不是规定的，可以结合实际来安排，当然，系统所追求的是一种均衡的分配方式，这样做只是为了更好地对缓冲块进行管理，同时效率也是很高的！

一个缓冲块可以存在于两个链表中：散列表或者是空闲表。如果我们需要寻找一个特定的缓冲块，我们可以在散列表中寻找，举个例子：在一个 *** 作系统中，有多个进程在执行着，现在进程1在使用一个缓冲块，此时进程2也需要访问相应的块，那么进程2就会在散列表中进行寻找，而不是到空闲表中寻找。

而buffer_head结构的字段：b_next、b_prev、b_prev_free、b_next_free就是用来对散列表和空闲表进行 *** 作的。

这仅仅是对缓冲区头结构进行的一个简单的学习总结，还有相应算法会频繁使用到这些字段，相应的总结将在后面的总结中列出。

如果相对高速缓冲有更直接的认识，了解内存结构是很有好处的，所以，要把内存管理弄明白。呵呵！

在linux内核中，有大量的数据结构需要用到双循环链表，例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式，需要为这些数据结构维护各自的链表，并且为每个链表都要设计插入、删除等 *** 作函数。因为用来维持链表的next和prev指针指向对应类型的对象，因此一种数据结构的链表 *** 作函数不能用于 *** 作其它数据结构的链表。

*** 作系统可能包含许多关于系统当前状态的信息。当系统发生变化时，这些数据结构必须做相应的改变以反映这些情况。例如，当用户登录进系统时将产生一个新的进程。核心必须创建表示新进程的数据结构，同时 将它和系统中其他进程的数据结构连接在一起。 大多数数据结构存在于物理内存中并只能由核心或者其子系统来访问。数据结构包括数据和指针；还有其他数据结构的地址或者子程序的地址。它们混在一起让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文件系统连接时使用的一些相关函数的地址传入。

---