linux - Linux 内核中的队列

Question

我一直在寻找有关队列的通用内核实现的信息，即先进先出数据结构。我认为可能有一个，因为它可能是常用的东西，并且有一个链接列表的标准（以 list_head 结构的形式）。是否有一些我找不到的标准队列实现，或者只是使用链表作为队列并希望最好的做法可能是常见的做法？

Answer 1

您在寻找 include/linux/kfifo.h 吗？从标题：

一个简单的内核 FIFO 实现。

无论如何，它还是相当新的，因此不难找到链表的直接用法。此外，它们有完全不同的实现（FIFO 被实现为循环缓冲区），因此它们有不同的应用。

另请注意，它们在设计时考虑了多线程使用（考虑生产者/消费者队列），但您可以在不使用 __kfifo_put/__kfifo_get 锁定的情况下使用它们。

顺便说一句：我记得我是在 lwn.net 上了解它们的 - 将此添加为书签：lwn.net/Kernel/Index，并阅读有关 kfifo 的条目 :-)。

来自您的前内核开发人员 Blaisorblade

Answer 2

没错，Linux 内核通常使用链表来实现队列。这是有道理的，因为链表提供了所需的行为。请参阅 kernel/workqueue.c 中的此示例：

  INIT_LIST_HEAD(&wq->list);
  // ...
   case CPU_UP_CANCELED:
            list_for_each_entry(wq, &workqueues, list) {
                    if (!per_cpu_ptr(wq->cpu_wq, hotcpu)->thread)

Answer 3

您似乎将抽象（fifo 队列）与实现（链表）混淆了。它们不是相互排斥的——事实上队列最常被实现为链表——没有“希望最好”。