侵入式链表：Linux 内核如何管理进程
来源：www.data-structures-in-practice.com · 64 分
📋 概述
这篇教程讲解侵入式链表的原理及其在 Linux 中的运用：链表的 next/prev 指针直接内嵌在被链接对象本身，而非放在独立节点里。相比非侵入式链表，它少一次内存分配、缓存抖动更少；Linux 用这种环形双向链表把每个 task_struct 串成任务列表，配合 container_of 宏从节点地址反推出对象基址。
🔑 核心要点
- 侵入式链表把链接指针内嵌进被链接对象本身，不另设数据指针。
- 创建对象只需一次内存分配，节点错误处理概率减半。
- 遍历时少一次解引用，缓存命中率更高、抖动更小。
- Linux 用内嵌 list_head 的环形双向链表管理 task_struct 任务列表。
- list_entry/container_of 通过减去成员偏移量反推出对象基址。
💡 金句
Linux 大量使用侵入式链表——通常用在列表很短或很少被遍历的地方。
👍 0
👎 0
← 返回 Hacker News 首页