Intrusive linked lists: как Linux управляет процессами без лишних аллокаций
Интрузивные связные списки — это вариант списков, где узлы встроены прямо в структуры данных, что сокращает число выделений памяти и уменьшает промахи кэша. В статье объясняется, как они работают, включая двусвязные и циклические варианты, и как Linux использует их для управления задачами. Рассматривается реализация на основе struct list_head, макросы list_add и container_of, а также пример обработки сигналов через for_each_process.
В Linux узлы списка добавляются и удаляются гораздо чаще, чем происходит обход списка: анализ показал, что обходы составляют лишь 6% всех операций со списками.