【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