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

Question

Ядро Linux хранит списки процессов в виде круговых двусвязных списков, называемых списком задач. В чем причина этого? Почему использовались круглые двусвязные списки? В чем преимущество использования этой структуры данных? Чего пытались достичь создатели, используя эту структуру данных?

Answer 1

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

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

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

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

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

Answer 2

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

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

Answer 3

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

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

Answer 4

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

 for (i = 0; i сделать что-то с процессом
} 

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

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

---

PS Я полагаю, что существует несколько списков процессов:

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

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