深入分析 Linux 内核链表_SyBase_学习笔记★闵涛★计算机学习电脑编程软硬件技巧


	转至繁体中文版	\| 网站首页 \| 图文教程 \| 资源下载 \| 站长博客 \| 图片素材 \| 武汉seo \| 武汉网站优化 \|

深入分析 Linux 内核链表

作者：闵涛文章来源：闵涛的学习笔记点击数：1356 更新时间：2009/4/22 23:07:44

前面介绍了用于链表遍历的几个宏，它们都是通过移动 pos 指针来达到遍历的目的。但如果遍历的操作中包含删除 pos 指针所指向的节点，pos 指针的移动就会被中断，因为 list_del(pos) 将把 pos 的 next、prev 置成 LIST_POSITION2 和 LIST_POSITION1 的特殊值。

当然，调用者完全可以自己缓存 next 指针使遍历操作能够连贯起来，但为了编程的一致性，Linux 链表仍然提供了两个对应于基本遍历操作的 "_safe" 接口：list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member)，它们要求调用者另外提供一个与 pos 同类型的指针n，在 for 循环中暂存 pos 下一个节点的地址，避免因 pos 节点被释放而造成的断链。

四、扩展

1. hlist

图 6 list 和 hlist

精益求精的 Linux 链表设计者（因为 list.h 没有署名，所以很可能就是 Linus Torvalds）认为双头（next、prev）的双链表对于 HASH 表来说 "过于浪费"，因而另行设计了一套用于 HASH 表应用的 hlist 数据结构--单指针表头双循环链表，从上图可以看出， hlist 的表头仅有一个指向首节点的指针，而没有指向尾节点的指针，这样在可能是海量的 HASH 表中存储的表头就能减少一半的空间消耗。

因为表头和节点的数据结构不同，插入操作如果发生在表头和首节点之间，以往的方法就行不通了：表头的 first 指针必须修改指向新插入的节点，却不能使用类似 list_add() 这样统一的描述。为此，hlist 节点的 prev 不再是指向前一个节点的指针，而是指向前一个节点（可能是表头）中的 next（对于表头则是 first）指针（struct list_head **pprev），从而在表头插入的操作可以通过一致的 "*(node->pprev)" 访问和修改前驱节点的 next（或 first）指针。

2. read-copy update
在 Linux 链表功能接口中还有一系列以 "_rcu" 结尾的宏，与以上介绍的很多函数一一对应。RCU（Read-Copy Update）是 2.5/2.6 内核中引入的新技术，它通过延迟写操作来提高同步性能。

我们知道，系统中数据读取操作远多于写操作，而 rwlock 机制在 smp 环境下随着处理机增多性能会迅速下降（见参考资料 4）。针对这一应用背景，IBM Linux 技术中心的 Paul E. McKenney 提出了 "读拷贝更新" 的技术，并将其应用于 Linux 内核中。RCU 技术的核心是写操作分为写-更新两步，允许读操作在任何时候无阻访问，当系统有写操作时，更新动作一直延迟到对该数据的所有读操作完成为止。Linux 链表中的 RCU 功能只是 Linux RCU 的很小一部分，对于 RCU 的实现分析已超出了本文所及，有兴趣的读者可以自行参阅本文的参考资料；而对 RCU 链表的使用和基本链表的使用方法基本相同。

五、示例
附件中的程序除了能正向、反向输出文件以外，并无实际作用，仅用于演示 Linux 链表的使用。

为了简便，例子采用的是用户态程序模板，如果需要运行，可采用如下命令编译：

 
gcc -D__KERNEL__ -I/usr/src/linux-2.6.7/include pfile.c -o pfile

因为内核链表限制在内核态使用，但实际上对于数据结构本身而言并非只能在核态运行，因此，在笔者的编译中使用 "-D__KERNEL__" 开关 "欺骗" 编译器。

参考资料
1. 维基百科 http://zh.wikipedia.org，一个在 GNU Documentation License 下发布的网络辞典，自由软件理念的延伸，本文的 "链表" 概念即使用它的版本。
2. 《Linux 内核情景分析》，毛德操先生的这本关于 Linux 内核的巨著几乎可以回答绝大部分关于内核的问题，其中也包括内核链表的几个关键数据结构。
3. Linux 内核 2.6.7 源代码，所有不明白的问题，只要潜心看代码，总能清楚。
4. Kernel Korner: Using RCU in the Linux 2.5 Kernel，RCU 主要开发者 Paul McKenney 2003 年 10 月发表于 Linux Journal 上的一篇介绍 RCU 的文章。在 http://www.rdrop.com/users/paulmck/rclock/ 上可以获得更多关于 RCU 的帮助。

关于作者
杨沙洲，目前在国防科技大学计算机学院攻读软件方向博士学位。对文中存在的技术问题，欢迎向 pubb@163.net 质疑。

全文出自 : IBM developerWorks 中国网站

上一页 [1] [2]

[C语言系列]C# 和 Linux 时间戳转换  [Web开发]PHP flock文件锁介绍
[Web开发]flock() Linux下的文件锁  [电脑应用]Linux下的六个免费的虚拟主机管理系统介绍
[电脑应用]Linux数据库大比拚  [操作系统]在Windows中玩转Linux操作系统
[办公软件]在RedHat Linux 9里安装gaim0.80  [办公软件]掌握 Linux 调试技术
[办公软件]理解 Linux 配置文件  [聊天工具]Real10 & Xpdf installation on Linux Box

教程录入：mintao 责任编辑：mintao

上一篇教程： (转载)Linux下源代码阅读工具lxr安装使用说明

下一篇教程：在 Linux 上进行自动备份

【字体：小大】【发表评论】【加入收藏】【告诉好友】【打印此文】【关闭窗口】

注：本站部分文章源于互联网，版权归原作者所有！如有侵权，请原作者与本站联系，本站将立即删除！本站文章除特别注明外均可转载，但需注明出处！ [MinTao学以致用网]

　网友评论：（只显示最新10条。评论内容只代表网友观点，与本站立场无关！）

同类栏目

· Sql Server  · MySql
· Access  · ORACLE
· SyBase  · 其他

热门推荐

没有教程

赞助链接

闵涛博文

500 - 内部服务器错误。

您查找的资源存在问题，因而无法显示。

鄂公网安备 42011102001154号

站长：MinTao ICP备案号：鄂ICP备11006601号-18

闵涛站盟:医药大全-武穴网。A打造B、C、D……