Linux 内核双链表的实现太精妙了

0 0

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

图片描述

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

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

9 years, 9 months ago

败走少年之歌 9 years, 9 months ago

单说水具结构的话
红黑树

answered 10 years, 2 months ago

bt中的蝌蚪 answered 10 years, 2 months ago

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

answered 10 years, 2 months ago

为了福利.. answered 10 years, 2 months ago

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

answered 10 years, 2 months ago

爱上百合的狮子 answered 10 years, 2 months ago

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

answered 10 years ago

朝田龙太郎 answered 10 years ago

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

answered 10 years ago

其实我是你爸 answered 10 years ago

单说水具结构的话
红黑树

answered 10 years ago

jumbo answered 10 years ago

answered 10 years ago

影子dē逆袭 answered 10 years ago