为什么 Linux 内核使用循环双向链表来存储进程列表？
Why does the Linux kernel use circular doubly linked lists to store the lists of processes?
Linux 内核将进程列表存储在循环双向链表中，称为任务列表。其背后的原因是什么？为什么使用循环双向链表？使用这种数据结构有什么好处？创造者试图通过使用这种数据结构来实现什么？
灵活性，例如，如果您知道您正在搜索的内容可能在您后面，您可以使用 list_for_each_entry_reverse 宏而不是通常的前向宏。
"you use linked lists when iterating over the whole list is important and the dynamic addition and removal of elements is required ... Using this type of linked list provides the greatest flexibility"
并且没有重复代码
"In the old days, there were multiple implementations of linked lists in the kernel. A single, powerful linked list implementation was needed to remove duplicate code. During the 2.1 kernel development series, the official kernel linked-list implementation was introduced."
资料来源：罗伯特·洛夫。 "Linux Kernel Development"（第 3 版）。第 87-94 页
在大多数情况下，任务列表根本没有使用。内核通过例如到达任务结构thread_info 结构中的指针（它通过堆栈指针到达后者）或通过 current_task，一个指向（咳咳）当前任务的全局指针。
仅在需要遍历任务列表时才使用（这种操作很少见，而且本质上是低效的操作，因为任务列表是可变长度的，因此在大型机器上它可以增长到数十万甚至数百万条目）使用 linked 列表。在这种情况下，从列表中的任何一点开始并继续前进直到回到开始的地方（即循环列表）是很方便的。为什么它被双重 linked，我不确定，但我想 link 只会向一个已经很大的结构添加几个字节，并且以任何一种方式遍历它的灵活性都是值得的。
编辑：实际上，正如@thrig 在另一个答案中指出的那样，原因是内核中有一个 linked 列表的实现 everybody 使用（没有奇怪的错误，因为有人使用了他们自己的），这恰好是双重 linked 列表实现，正是因为它的一些用户需要灵活性。
具有某种形式的对象（例如进程）列表的原因是有时内核需要枚举所有这些对象，即依次遍历每个对象。这意味着必须有一种方法可以找到该类型的所有对象。如果可以一次创建和删除一个对象，那么链表是最简单的解决方案。
列表需要双向链接才能支持删除对象。当移除一个对象时，代码需要更新所有指向这个对象的指针。因此，该对象需要包含指向指向它的所有其他对象的指针（或者至少需要有一个从对象本身开始的指针链）。使用单向链表，要从 A→B→C 中删除 B，没有办法找到需要更新其指针的 A，除非遍历所有对象直到找到正确的对象。使用双向链表，要从 A↔B↔C 中删除 B，您可以跟随从 B 到 A 的指针，并将 A 指向 B 的指针改为指向 C，C 也是如此。
作为Gilles points out，
有时内核需要遍历所有进程
（例如，在处理 kill(-1, <i>sig</i>) 时，
向每个进程发送 sig
调用进程有权为其发送信号，
除了流程 1——见 kill(2)）。
好久没看这段代码了；
但是，在 Unix 的早期版本中，进程 table 是一个数组——
一些固定数量的连续 proc 结构
（有时称为“进程槽”）。例如，
查看所有进程循环可能看起来像这样：
for (i = 0; i < PROC_MAX; i++) // This would probably really have started with i = 1
{ // so as not to look at proc[0], i.e., PID 1.
if (proc[i].flags & IS_AN_ACTIVE_PROCESS)
do something with the process
}
所以它必须查看 PROC_MAX（可能有数千个）
处理槽只是为了找到其中有实际进程的槽——
可能是一个小得多的数字。
将进程放入 linked 列表
允许内核对每个进程做一些事情
无需通过海绵状过程进行搜索 table.
此外，如果所有内容都与 linked 列表放在一起，
拥有动态大小的进程变得可行 table。
If/when 初始默认静态进程 table 已满，
只需分配更多（非连续）内存并将它们 link 在一起。
P.S。我相信可能有多个进程列表：
- 整体，
- 一个用于 运行 可用的进程（处于“运行”状态），
- 一个用于当前实际 运行ning 的进程
在（至少）一个处理器上，
- 一个用于等待事件的进程
（例如，完成 I/O 请求），
- 等等
在黑暗时代（30 年前），每当用户按下 Enter
（当时叫Return），
内核可能不得不搜索
通过 1000 个条目的过程 table
找到等待来自那个 tty 的输入的进程。
Linux 内核将进程列表存储在循环双向链表中，称为任务列表。其背后的原因是什么？为什么使用循环双向链表？使用这种数据结构有什么好处？创造者试图通过使用这种数据结构来实现什么？
灵活性，例如，如果您知道您正在搜索的内容可能在您后面，您可以使用 list_for_each_entry_reverse 宏而不是通常的前向宏。
"you use linked lists when iterating over the whole list is important and the dynamic addition and removal of elements is required ... Using this type of linked list provides the greatest flexibility"
并且没有重复代码
"In the old days, there were multiple implementations of linked lists in the kernel. A single, powerful linked list implementation was needed to remove duplicate code. During the 2.1 kernel development series, the official kernel linked-list implementation was introduced."
资料来源：罗伯特·洛夫。 "Linux Kernel Development"（第 3 版）。第 87-94 页
在大多数情况下，任务列表根本没有使用。内核通过例如到达任务结构thread_info 结构中的指针（它通过堆栈指针到达后者）或通过 current_task，一个指向（咳咳）当前任务的全局指针。
仅在需要遍历任务列表时才使用（这种操作很少见，而且本质上是低效的操作，因为任务列表是可变长度的，因此在大型机器上它可以增长到数十万甚至数百万条目）使用 linked 列表。在这种情况下，从列表中的任何一点开始并继续前进直到回到开始的地方（即循环列表）是很方便的。为什么它被双重 linked，我不确定，但我想 link 只会向一个已经很大的结构添加几个字节，并且以任何一种方式遍历它的灵活性都是值得的。 编辑：实际上，正如@thrig 在另一个答案中指出的那样，原因是内核中有一个 linked 列表的实现 everybody 使用（没有奇怪的错误，因为有人使用了他们自己的），这恰好是双重 linked 列表实现，正是因为它的一些用户需要灵活性。
具有某种形式的对象（例如进程）列表的原因是有时内核需要枚举所有这些对象，即依次遍历每个对象。这意味着必须有一种方法可以找到该类型的所有对象。如果可以一次创建和删除一个对象，那么链表是最简单的解决方案。
列表需要双向链接才能支持删除对象。当移除一个对象时，代码需要更新所有指向这个对象的指针。因此，该对象需要包含指向指向它的所有其他对象的指针（或者至少需要有一个从对象本身开始的指针链）。使用单向链表，要从 A→B→C 中删除 B，没有办法找到需要更新其指针的 A，除非遍历所有对象直到找到正确的对象。使用双向链表，要从 A↔B↔C 中删除 B，您可以跟随从 B 到 A 的指针，并将 A 指向 B 的指针改为指向 C，C 也是如此。
作为Gilles points out，
有时内核需要遍历所有进程
（例如，在处理 kill(-1, <i>sig</i>) 时，
向每个进程发送 sig
调用进程有权为其发送信号，
除了流程 1——见 kill(2)）。
好久没看这段代码了；
但是，在 Unix 的早期版本中，进程 table 是一个数组——
一些固定数量的连续 proc 结构
（有时称为“进程槽”）。例如，
查看所有进程循环可能看起来像这样：
for (i = 0; i < PROC_MAX; i++) // This would probably really have started with i = 1
{ // so as not to look at proc[0], i.e., PID 1.
if (proc[i].flags & IS_AN_ACTIVE_PROCESS)
do something with the process
}
所以它必须查看 PROC_MAX（可能有数千个）
处理槽只是为了找到其中有实际进程的槽——
可能是一个小得多的数字。
将进程放入 linked 列表
允许内核对每个进程做一些事情
无需通过海绵状过程进行搜索 table.
此外，如果所有内容都与 linked 列表放在一起， 拥有动态大小的进程变得可行 table。 If/when 初始默认静态进程 table 已满， 只需分配更多（非连续）内存并将它们 link 在一起。
P.S。我相信可能有多个进程列表：
- 整体，
- 一个用于 运行 可用的进程（处于“运行”状态），
- 一个用于当前实际 运行ning 的进程 在（至少）一个处理器上，
- 一个用于等待事件的进程 （例如，完成 I/O 请求），
- 等等
在黑暗时代（30 年前），每当用户按下 Enter （当时叫Return）， 内核可能不得不搜索 通过 1000 个条目的过程 table 找到等待来自那个 tty 的输入的进程。