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 キュー) と実装 (リンクされたリスト) を混同しているようです。それらは相互に排他的ではありません。実際、キューはリンクされたリストとして実装されるのが最も一般的です。「最善を期待する」ことはありません。