为什么Linux内核使用它所做的数据结构？

Question

Linux内核使用TCP的链表和RB树进行进程调度.

就算法效率而言,这些都是有意义的.你将一次收到一堆数据包,所以在列表末尾的O(1)插入很好.

通过进程调度,Completely Fair Scheduler使用红黑树,有O(1)时间来选择任务.

据我所知,这些都不是以"平面"方式实现的 - 链表是一堆节点,指向其他节点,就像树一样.这意味着,据我所知,这些结构的位置应该很差.

从我所看到的缓存局部性往往超过算法效率.

是否有关于Linux编程的数据集的某些内容使得这些结构的算法效率超过了其他结构的缓存效率？

我误会了什么吗？有人描述过吗？

Answer 1

我对链表的使用有一个部分答案,我相信你会在这个页面中找到一些有关CFS调度程序的有趣信息,特别是它提到了一个红黑树has good worst-case time for operations such as insert, search, and delete,它确实看起来像一个非常理想的调度程序属性.

我敢打赌,是的,内核已经看到了很多分析,这些数据结构似乎在现实世界中表现良好.

这篇博文有一些关于内核链表用法的精彩数据.通过保持每个操作的计数器,显然在正常使用的3天内收集该数据.

+--------------------+-----------+
|     Operation      | Frequency |
+--------------------+-----------+
|     Empty Test     | 45%       |
|       Delete       | 25%       |
|        Add         | 23%       |
|   Iterate Start    | 3.5%      |
|   Iterate Next     | 2.5%      |
|     Replace        | 0.76%     |
| Other Manipulation | 0.0072%   |
+--------------------+-----------+

正如您所看到的,实际访问元素的操作占总数的6%,而插入和删除几乎占了一半.这是链接列表开始变得更有意义的用例.请注意,数据是在整个内核中收集的,而不是特定于TCP代码,因此链接列表的基本原理可能在每次使用时都不一样,但总数据确实表明这些是整体的理智选择.

我认为同样重要的是要记住,内核的设计必须能够从最小的嵌入式设备扩展到处理大量数据的超级计算机,此时算法效率可能会开始严重超过缓存问题.