程序设计 - Linux 内核双链表的实现太精妙了

Question

通过设计前驱和后继两个指针域，双链表可以从两个方向遍历。如果打乱前驱、后继的依赖关系，就可以构成"二叉树"；如果再让首节点的前驱指向链表尾节点、尾节点的后继指向首节点（图中虚线部分），就构成了循环链表；如果设计更多的指针域，就可以构成各种复杂的树状数据结构。

这是 Linux 内核双链表，这个设计真是太牛了！

想了解一下，在操作系统内核具体实现中，还有哪些精妙的思想？站内各位大牛欢迎讨论

Answer 1

fork 函数 每次调用会返回两次
分别返回父进程 PID 和 0
来标示 父子进程
－－－－－
一切概念上等同为文件
处理文件标示符的I/O问题

Answer 2

如果你看过c++介绍stl的书，就不这样觉得了。这是很一般的做法。

Answer 3

个人觉得：
1） 虚拟文件系统VFS
2） 预读取算法
3） 基于epoll的IO处理
这几个设计比较强悍

Answer 4

双向链表不都是这么搞的吗，没看出来怎么个NB法。这个是常用的数据结构。

Answer 5

先前看过有道面试题: 讲二叉树改成双向链表，只能改变指针指向。这是逆过程吧。

对于楼上几位说很常规的做法 看了什么书就觉得一般，这角度不同把，刚接触觉得思路很棒，很好啊。

之前学数据结构从链表到指针就觉得二者很像，

struct ListNode{TYPE date,ListNode *next;}
struct BiTreeNode{TYPE date,BiTreeNode *left,*right;}
struct BiListNode{TYPE date,BiListNode *pre,*next;}

二叉树比单链表多一个指针域。
不考虑逻辑关系的定义，在实现上，二叉树和双链表的定义几乎相同不知道能否强制转换，毕竟数据的空间分配是相同的。
而在某些情况下，有猫腻！

Answer 6

单说水具结构的话
红黑树

Answer 7

在Linux内核里，中断处理用到了二分查找，垃圾收集用到了归并排序，字符串匹配用KMP，任务调度用红黑树。给你一个链接，你看看就知道了http://cstheory.stackexchange.com/questions/19759/core-algorithms-deployed/

Answer 8

一句：do while(0) 你可以研究一下。