Slab allocator

Der Slab allocator ist ein Verfahren zur Speicherverwaltung, das viele Betriebssysteme und auch Anwendungen verwenden. Der Algorithmus hat zum Ziel, dass bei der häufig vorkommenden Reservierung kleiner Speicherbereiche der vorhandene Arbeitsspeicher möglichst effizient, also mit wenig Verschwendung, genutzt wird.

Beteilige dich an der Diskussion!

Dieser Artikel wurde wegen inhaltlicher Mängel auf der Qualitätssicherungsseite der Redaktion Informatik eingetragen. Dies geschieht, um die Qualität der Artikel aus dem Themengebiet Informatik auf ein akzeptables Niveau zu bringen. Hilf mit, die inhaltlichen Mängel dieses Artikels zu beseitigen, und beteilige dich an der Diskussion! (+) Begründung: Überflüssige allg. Erläuterungen; Keine sinnvolle Artikelstruktur; Klare Definition fehlt. Der englische Artikel kann zur Ausbesserung verwendet werden.

Anmerkung: Einige Details der vorliegenden technischen Beschreibung des Slab allocators basieren auf der Implementierung im Linux-Kernel 2.6.10-rc2. Diese können sich von anderen Systemen unterscheiden und sind ggf. technisch nicht auf dem aktuellen Stand.

Geschichte

Entwickelt wurde der Slab allocator 1994 von Jeff Bonwick für SunOS 5.4. Da er seine Vorgehensweise öffentlich dokumentiert hat, wurde sie von vielen anderen Betriebssystemen (z. B. Linux) und Anwendungen (z. B. Perl) übernommen. Im Jahr 2001 veröffentlichte Bonwick eine deutlich verbesserte Version, die ebenso öffentlich dokumentiert wurde.

1999 hielt der Slab allocator Einzug in den Linux-Kernel. Die aktuelle Implementierung enthält bereits einige Elemente aus Bonwicks 2001er-Version, diese ist jedoch noch nicht vollständig umgesetzt.

Idee

Das Ziel einer Speicherverwaltung sollte es sein, den vorhandenen Speicher möglichst effizient zu nutzen und dabei eine schnelle Freigabe und Reservierung der benötigten Objekte zu ermöglichen. Dabei ist auch das Problem der Fragmentierung nicht zu vernachlässigen: Es sollten im Betrieb möglichst wenig kleine, ungenutzte Speicherbereiche zwischen den benutzten entstehen. Aus technischen Gründen wird der Speicher in großen (bei IA-32: 4096 Bytes) Speicherseiten organisiert, was jedoch nicht besonders effizient für dynamisch angeforderten Speicher ist.

Eigenschaften von Kernobjekten

Die meisten Objekte, die ein Betriebssystem verwendet, sind relativ klein und haben eine begrenzte Lebensdauer, werden also nach kurzer Zeit wieder an das System zurückgegeben. Außerdem werden häufig mehrere Objekte desselben Typs benötigt.

Private Caches

Bonwick distanziert sich in seiner Ausarbeitung von der Idee privater Caches, also Zwischenspeicher, die jeder Prozess bzw. jedes Kernelmodul im Betriebssystem selbst verwaltet. Zwar hat ein Prozess selbst den besten Überblick über den eigenen Speicherbedarf, jedoch hat er fast keinen Überblick über die Speichersituation im System als Ganzes und keinen über den Bedarf anderer Prozesse.

Clients & Central Allocator

Bonwick unterteilt die Speicherverwaltung folglich in zwei Teile. Der Central allocator stellt Funktionen bereit, um den Speicher zu verwalten. Er sorgt für die möglichst effiziente Nutzung. Dem gegenüber stehen die Clients. Diese beschreiben nur noch die benötigten Objekte und müssen sich nicht um Details kümmern.

Aufbau des Central Allocators

Folgender Aufbau wird nun von Bonwick vorgeschlagen:

• Objekte desselben Typs werden zu Slabs (englisch: Kachel, Fliese) zusammengefasst.
• Diese Slabs werden unter einem Cache organisiert, es werden also weitere Objekte desselben Typs auf Vorrat gehalten.
• Dieses Caching vermindert aufwändige Rückgriffe auf die darunter liegende Buddy-Speicherverwaltung, welche nur ganze Speicherseiten liefert.
• Die für Slabs und Caches benötigten Speicherseiten müssen vom Buddy-System geholt werden.

Mit anderen Worten: Der Slab allocator teilt den vom Buddy-System gelieferten Speicher weiter auf. Der Central Allocator bietet Schnittstellen (APIs) an, über die Clients Speicher anfordern können.

Caches

Aufgaben

Die Caches besitzen drei Aufgaben:

• Sie stellen Vorräte von oft benutzten Objekten fertig initialisiert zur Verfügung.
• Sie stellen allgemeine Vorräte an Objekten bestimmter Größen zur Verfügung (für weniger oft benötigte Objekte oder einzelne Speicherbereiche), unter Linux von $2^{5}=32$ bis $2^{17}=131072$ Bytes.
• Sie sollen die Hardwarecaches (TLB, L1-Cache) möglichst gut ausnutzen.

Aufbau

Jeder Cache wird durch eine Datenstruktur (unter Linux vom Typ: kmem_cache_s) repräsentiert. Diese enthält drei doppelt verkettete Listen (innerhalb der Unterstruktur list vom Typ kmem_list3), unter der die Slabs aufgereiht werden. Eine Liste enthält die Slabs, die nur mit ungebrauchten Objekten gefüllt sind („all free“), eine mit den vollständig in Benutzung befindlichen Objekten („all used“), und die dritte Liste enthält Slabs mit gebrauchten sowie derzeit nicht gebrauchten Objekten („mixed free/used“).

Des Weiteren gibt es (seit der 2001er Version von Bonwicks Ausarbeitung) einen Zwischenspeicher (vom Typ array_cache) für jeden Prozessor im System, der sich die zuletzt freigegebenen Objekte merkt. Diese Objekte werden auch zuerst wieder vergeben, da die Wahrscheinlichkeit sehr hoch ist, sie noch in einem der Prozessorcaches zu finden, die dadurch also besser ausgenutzt werden.

Beispiel: Informationen zu den Caches

Am Beispiel wird dieses Konzept deutlicher. Es gibt unter Linux Laufzeitinformationen zum Slab allocator in der Datei /proc/slabinfo. Die folgende beispielhafte Ausgabe ist stark gekürzt.

name	<active_objs>	<num_objs>	<objsize>	<objperslab>	<pagesperslab> : tunables	<batchcount>
raid5/md0	256	264	364	11	1 : tunables	54
reiser_inode_cache	2955	5650	376	10	1 : tunables	54
scsi_cmd_cache	2	11	352	11	1 : tunables	54
sgpool-128	32	32	2048	2	1 : tunables	24
sgpool-64	32	32	1024	4	1 : tunables	54
sgpool-32	32	32	512	8	1 : tunables	54
sgpool-16	32	45	256	15	1 : tunables	120
sgpool-8	32	62	128	31	1 : tunables	120
clip_arp_cache	0	0	160	25	1 : tunables	120
rpc_buffers	8	8	2048	2	1 : tunables	24
rpc_tasks	8	25	160	25	1 : tunables	120
rpc_inode_cache	0	0	416	9	1 : tunables	54
unix_sock	243	270	384	10	1 : tunables	54
size-128(DMA)	0	0	128	31	1 : tunables	120
size-128	4282	4402	128	31	1 : tunables	120
size-64(DMA)	0	0	64	61	1 : tunables	120
size-64	856	1403	64	61	1 : tunables	120
size-32(DMA)	0	0	32	119	1 : tunables	120
size-32	2176	8211	32	119	1 : tunables	120

Bedeutung der Spalten:

• name: Name des Caches
• <active_objs>: Anzahl der derzeit im Benutzung befindlichen Objekte
• <num_objs>: Anzahl aller Objekte
• <objsize>: Größe eines Objektes (in Bytes)
• <objperslab>: Anzahl der Objekte pro Slab
• <pagesperslab>: Anzahl der Speicherseiten pro Slab
• <batchcount>: Anzahl der Objekte, die auf einmal angelegt bzw. freigegeben werden (bei der Erstellung bzw. Freigabe eines Slabs)

Der erste Teil der Tabelle zeigt die bereits erwähnten Caches für bestimmte Objekte, der zweite Teil die Caches in allgemeinen Größen, je in einer Variante für DMA-fähigen Speicher und für nicht-DMA-fähigen Speicher.

Fragmentierung

Fragmentierung lässt sich in zwei Arten unterteilen: Interne und externe Fragmentierung.

Interne Fragmentierung

Interne Fragmentierung definiert Bonwick als „per buffers wasted space“, also den Platz, der pro Slab verschwendet wird. Ungenutzte Lücken entstehen durch:

1. Das Aufrunden der Objektgröße auf ein ganzzahliges Vielfaches der Wortgröße (sizeof (void *)) des verwendeten Prozessors. Dies beschleunigt dank ausgerichteter Adressen auf den meisten Architekturen den Zugriff (der Prozessor bietet optimierte Befehle für ausgerichtete Adressen an), kostet jedoch Speicherplatz.
2. Verschnitt am Ende des Slabs, denn in den seltensten Fällen ergeben die Objekte im Slab genau dessen Größe.

Der Verschnitt am Ende ist kleiner als ${\frac {1}{\text{Objektanzahl}}}$ der Slabgröße, er kann also durch die Größe des Slabs beeinflusst werden: Je größer der Slab, desto mehr Objekte enthält er und desto kleiner ist der Verschnitt. Des Weiteren wird dieser Verschnitt für das sogenannte Colouring verwendet, auf das weiter unten eingegangen wird.

Externe Fragmentierung

Externe Fragmentierung definiert Bonwick als „unused buffers in the freelist“, also ungenutzte Objekte in den Slabs. Wie bereits in der Tabelle weiter oben zu erkennen ist, existiert bei diesem Verfahren externe Fragmentierung. Sie ist jedoch relativ gering.

Dadurch, dass gleiche Objekte ähnliche Lebensdauern haben, entstehen wenige nur teilweise genutzte Slabs. Die meisten Slabs sind entweder vollständig oder gar nicht belegt. Die Ausnahme hierbei sind die Caches in bestimmten Größen, diese werden jedoch nicht so häufig verwendet.

Des Weiteren wird der Speicher nicht weiter aufgeteilt, wie es andere Verfahren (z. B. das Buddy-Verfahren) tun. Denn je mehr Objekte ein Slab enthält, desto höher wird die externe Fragmentierung, da die Wahrscheinlichkeit, einen Slab vollkommen leer zu bekommen, sinkt.

Colouring

Das Colouring versucht, durch unterschiedliche Ausrichtung gleicher Objekte in verschiedenen Slabs die CPU-Caches besser zu nutzen.

Dazu wird der Verschnitt am Ende des Slabs genommen und Teile davon vor dem ersten Objekt im Slab eingefügt. Somit liegen die Objekte im Vergleich zu einem anderen Slab „versetzt“. Durch geschicktes Ausrichten an Vielfachen der Cachelinegröße kann dadurch ein gegenseitiges Verdrängen der Objekte aus dem Cache sowie der Adressen aus dem TLB vermindert werden.

Ablauf einer Speicheranforderung

Aus dem bisherigen ergibt sich der typische Ablauf einer Speicheranforderung:

1. Es wird versucht, ein Objekt aus dem per-CPU-Cache zu entnehmen.
2. Schlägt dies fehl, wird ein Objekt aus einem bereits bestehenden Slab geliefert.
3. Falls auch keine freien Objekte mehr in den Slabs vorhanden sind, muss ein neuer Slab angelegt werden, mit dem Umweg über das übergeordnete Buddy-System.

Der negative Einfluss auf die Caches und somit auf die Performance steigt dabei von Punkt zu Punkt.

Slabs

Aufbau

Ein Slab besteht aus

1. einem Verwaltungskopf, der Informationen enthält wie das erste Objekt im Slab, den Index des ersten freien Objekts, die Zahl der belegten Objekte, die Verschiebung für das Colouring (Farbraum) dieses Slabs sowie eine Verknüpfung zu dem vorherigen und nächsten Slab in der Liste der freien/belegten/teilweise genutzten Slabs,
2. einer Verwaltungsstruktur für die freien Objekte,
3. den Objekten, aufgerundet auf ein ganzzahliges Vielfaches der Wortgröße des Prozessors,
4. dem restlichen Verschnitt, falls vorhanden.

Die Verwaltung freier Objekte

Die Verwaltung der freien Objekte verläuft im Linux-Kern über eine Liste von Ganzzahlen. Sie enthält eben so viele Zahlen wie Slab-Objekte. Jedes Zahlenfeld hat nur eine Bedeutung, wenn das entsprechende Objekt nicht benutzt wird, und gibt dann den Index des nächsten freien Objektes an. Durch die Information über das erste freie Objekt im Kopf des Slabs kann somit schnell das nächste ermittelt und zurückgegeben werden.

Literatur

• Wolfgang Mauerer: Linux Kernelarchitektur. Hanser, 2004, ISBN 3-446-22566-8
• Andrew S. Tanenbaum: Modern Operating Systems. Prentice Hall, 2001. Englisch, ISBN 0-13-092641-8

Weblinks

• Bonwicks Beschreibung des Slab allocators, 1994 (PostScript)
• Bonwicks Beschreibung des Slab allocators, 2001 (PDF; 131 kB)
• Vortrag über den Linux Slab allocator Sven Krohlas, Uni Karlsruhe, WS 2004/2005