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

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

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

这是 Linux 内核双链表,这个设计真是太牛了!

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

回答

fork 函数 每次调用会返回两次

分别返回父进程 PID 和 0

来标示 父子进程

-----

一切概念上等同为文件

处理文件标示符的I/O问题

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

个人觉得:

1) 虚拟文件系统VFS

2) 预读取算法

3) 基于epoll的IO处理

这几个设计比较强悍

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

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

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

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

struct ListNode{TYPE date,ListNode *next;}

struct BiTreeNode{TYPE date,BiTreeNode *left,*right;}

struct BiListNode{TYPE date,BiListNode *pre,*next;}

二叉树比单链表多一个指针域。

不考虑逻辑关系的定义,在实现上,二叉树和双链表的定义几乎相同不知道能否强制转换,毕竟数据的空间分配是相同的。

而在某些情况下,有猫腻!

单说水具结构的话

红黑树

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

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

以上是 【linux】Linux 内核双链表的实现太精妙了 的全部内容, 来源链接: utcz.com/a/84847.html

回到顶部