Очереди в ядре 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) с реализацией (связанный список). Они не являются взаимоисключающими - на самом деле очереди чаще всего реализуются как связанные списки - нет «надежды на лучшее».