Intrusive Listen: Wie Linux Prozesse mit eingebetteten Zeigern verwaltet

Intrusive Linked Lists

Intrusive verkettete Listen unterscheiden sich von herkömmlichen Listen dadurch, dass die Verkettungszeiger direkt in die Datenstruktur eingebettet sind. Dieser Artikel erklärt das Konzept anhand von C-Code und zeigt, wie Linux damit Prozesse verwaltet. Durch die Vermeidung separater Knoten-Allokationen reduzieren intrusive Listen Speicherbedarf und Cache-Misses. Linux nutzt zirkuläre doppelt verkettete Listen (struct list_head), die in Strukturen wie task_struct eingebettet sind. Die Makros LIST_HEAD_INIT, list_add und container_of ermöglichen effiziente Listenoperationen. Eine Analyse zeigt, dass Traversierungen nur 6% der Listenoperationen ausmachen, weshalb die Effizienz der Iteration selten kritisch ist.