Почему ядро ​​Linux использует циклические дважды связанные списки для хранения списков процессов?

Ответ 1

Гибкость, поэтому, если вы знаете, например, то, что вы ищете, вероятно, позади вас, вы можете использовать макрос list_for_each_entry_reverse вместо обычного переадресации.

"вы используете связанные списки, когда итерация по всему списку важна, и требуется динамическое добавление и удаление элементов... Использование такого типа связанного списка обеспечивает максимальную гибкость

и без дублирования кода

"В старые времена в ядре было множество реализаций связанных списков. Для удаления дублированного кода была необходима единственная мощная реализация связанных списков. Во время серии разработки ядра 2.1 была введена официальная реализация связанного списка ядра."

Источник: Роберт Любовь. "Linux Kernel Development" (3-е издание). p.87-94

Ответ 2

Причиной иметь список объектов (например, процессов) в какой-то форме является то, что иногда ядро ​​должно перечислять все эти объекты, т.е. проходить через каждый из них по очереди. Это означает, что должен быть способ найти все объекты этого типа. Если объекты можно создавать и удалять по одному, то связанный список является самым простым решением.

Чтобы поддерживать удаление объекта, список должен быть дважды привязан. При удалении объекта код должен обновить все указатели, указывающие на этот объект. Поэтому объект должен содержать указатель на все остальные объекты, указывающие на него (или, по крайней мере, должна быть цепочка указателей, начинающихся с самого объекта). С односвязным списком, чтобы удалить B из A → B → C, нет способа обнаружить A, указатель которого нужно обновить, не пройдя все объекты до тех пор, пока не будет найден правильный. С двусвязным списком, чтобы удалить B из A↔B↔C, вы следуете указателю от B до A и изменяете указатель на B, чтобы указать вместо C, а также на C.

Ответ 3

В большинстве случаев список задач не используется вообще. Ядро достигает структур задач через, например, указатель в структуре thread_info (и он попадает к последнему через указатель стека) или через current_task, глобальный указатель на (ах) текущую задачу.

Только когда список задач должен быть пройден (редкая и по сути неэффективная операция, потому что список задач имеет переменную длину, поэтому он может вырасти до сотен тысяч или даже миллионов записей на большой машине), что используется связанный список. В этом случае удобно начинать в любой точке списка и продолжать движение до тех пор, пока вы не вернетесь в то место, откуда вы начали (т.е. Круговой список). Почему это вдвойне связано, я не знаю точно, но я думаю, что ссылка добавляет несколько байтов к уже большой структуре, и гибкость в ее перемещении в любом случае стоила того. EDIT: на самом деле, как указывает @thrig в другом ответе, причина в том, что в ядре используется одна реализация связанных списков в ядре, которые все используют (нет странных ошибок, потому что кто-то их использовал), и это, оказывается, двусвязный список реализации, именно потому, что некоторые пользователи этого хотят гибкости.

Ответ 4

Как указывает Гилл, иногда ядру необходимо перебирать все процессы (например, при обработке kill(-1, sig), который отправляет sig в каждый процесс для которого вызывающий процесс имеет разрешение на отправку сигналов, кроме процесса 1 - см. kill (2)). Я долго не смотрел на этот код; но в ранних версиях Unix таблица процессов была массивом - некоторое фиксированное число смежных структур proc (иногда называемых "слотами процесса" ). Например, цикл look-at-all-processes может выглядеть примерно так:

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 (потенциально тысячи) чтобы найти те, которые имели в них фактический процесс - возможно, намного меньшее число. Включение процессов в связанный список позволяет ядру делать что-то с каждым процессом без необходимости выполнять поиск по кавернозной таблице процессов.

Кроме того, если все удерживается вместе со связанными списками, становится возможным иметь таблицу процессов с динамическим размером. Если /, когда статическая таблица статических параметров по умолчанию заполнена, просто выделите еще одну (несмежную) память и соедините их вместе.

P.S. Я считаю, что есть, вероятно, несколько списков процессов:

• общий,
• один для процессов, которые выполняются (в состоянии "run" ),
• один для процессов, которые в настоящее время выполняются (по крайней мере) одного процессора,
• один для процессов, ожидающих события (например, завершение запроса ввода-вывода),
• и др.

В темные века (30 лет назад) всякий раз, когда пользователь нажал Enter (называемый тогда Return), ядру, возможно, пришлось бы искать через таблицу обработки за 1000 дней найти процесс (ы), ожидающий ввода из этого tty.