Подтвердить что ты не робот

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

Ядро Linux использует связанный список для TCP и дерево RB для планирования процесса.

В терминах алгоритмической эффективности это имеет смысл. Вы будете получать кучу пакетов по одному, поэтому добавление O (1) в конце списка приятно.

При планировании процессов, Полностью справедливый планировщик использует дерево Red Black, с O (1) временем для выбора задач.

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

Из того, что я видел, местность кэшей часто перевешивает алгоритмическую эффективность.

Есть ли что-то о наборе данных, который запрограммирован для Linux, что делает алгоритмическую эффективность этих структур перевесом эффективности кэша других?

Я что-то не понимаю? Кто-нибудь профилировал?

Ответ 1

У меня есть частичный ответ на использование связанных списков, и я считаю, что вы найдете интересную информацию в этой странице о планировщике CFS, в частности он упоминает, как красно-черное дерево has good worst-case time for operations such as insert, search, and delete, которое действительно кажется очень желательным свойством для планировщика.

Я бы пообещал, что да, ядро провело довольно много профилирования, и эти структуры данных, похоже, хорошо работают в реальном мире.

В этом сообщении в блоге есть интересные данные об использовании связанных с ядром списков. Эти данные, по-видимому, собирались в течение 3 дней обычного использования, сохраняя при этом счетчики каждой операции.

+--------------------+-----------+
|     Operation      | Frequency |
+--------------------+-----------+
|     Empty Test     | 45%       |
|       Delete       | 25%       |
|        Add         | 23%       |
|   Iterate Start    | 3.5%      |
|   Iterate Next     | 2.5%      |
|     Replace        | 0.76%     |
| Other Manipulation | 0.0072%   |
+--------------------+-----------+

Как вы можете видеть, что операции, фактически получающие доступ к элементам, составляют 6% от общей суммы, в то время как вставка и удаление составляют почти половину. Это пример использования, когда связанные списки начинают иметь гораздо больше смысла. Обратите внимание, что данные были собраны по всему ядру, а не только по TCP-коду, поэтому логическое обоснование для связанного списка может быть не одинаковым при каждом его использовании, но совокупные данные говорят о том, что все они были разумными.

Я думаю, что также важно иметь в виду, что дизайн ядра должен иметь возможность масштабировать от самых маленьких встроенных устройств до суперкомпьютеров, обрабатывающих огромные объемы данных, и в этот момент эффективность алгоритмического анализа может серьезно перевесить проблемы кэширования.