Slab allocator - Versionsgeschichte

Aka: /* Literatur */ Komma ergänzt

2024-08-12T16:37:01Z

Literatur: Komma ergänzt

← Nächstältere Version		Version vom 12. August 2024, 18:37 Uhr
Zeile 155:		Zeile 155:

	== Literatur ==		== Literatur ==
	* Wolfgang Mauerer: ''Linux Kernelarchitektur.'' Hanser, 2004. ISBN 3-446-22566-8		* 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		* Andrew S. Tanenbaum: ''Modern Operating Systems.'' Prentice Hall, 2001. Englisch, ISBN 0-13-092641-8

93.207.79.166 am 8. November 2023 um 08:17 Uhr

2023-11-08T08:17:02Z

← Nächstältere Version		Version vom 8. November 2023, 10:17 Uhr
Zeile 1:		Zeile 1:
	{{QS-Informatik\|Überflüssige allg. Erläuterungen; Keine sinnvolle Artikelstruktur; Klare Definition fehlt. Der englische Artikel kann zur Ausbesserung verwendet werden.\|Knacknüsse=1}}		{{QS-Informatik\|Überflüssige allg. Erläuterungen; Keine sinnvolle Artikelstruktur; Klare Definition fehlt. Der englische Artikel kann zur Ausbesserung verwendet werden.\|Knacknüsse=1}}

	Der '''Slab allocator''' ist ein Verfahren zur [[Speicherverwaltung]], das viele [[Betriebssystem]]e und auch [[Anwendungsprogramm\|Anwendungen]] verwenden. Der Algorithmus hat zum Ziel, dass bei der häufig ~~vorkommender~~ Reservierung kleiner Speicherbereiche der vorhandene Arbeitsspeicher möglichst effizient, also mit wenig [[Externe Fragmentierung\|Verschwendung]], genutzt wird.		Der '''Slab allocator''' ist ein Verfahren zur [[Speicherverwaltung]], das viele [[Betriebssystem]]e und auch [[Anwendungsprogramm\|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 [[Externe Fragmentierung\|Verschwendung]], genutzt wird.

	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.		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.

93.207.79.166 am 8. November 2023 um 08:16 Uhr

2023-11-08T08:16:30Z

← Nächstältere Version		Version vom 8. November 2023, 10:16 Uhr
Zeile 1:		Zeile 1:
	{{QS-Informatik\|Überflüssige allg. Erläuterungen; Keine sinnvolle Artikelstruktur; Klare Definition fehlt. Der englische Artikel kann zur Ausbesserung verwendet werden.\|Knacknüsse=1}}		{{QS-Informatik\|Überflüssige allg. Erläuterungen; Keine sinnvolle Artikelstruktur; Klare Definition fehlt. Der englische Artikel kann zur Ausbesserung verwendet werden.\|Knacknüsse=1}}

	Der '''Slab allocator''' ist ein Verfahren zur [[Speicherverwaltung]], das viele [[Betriebssystem]]e und auch [[Anwendungsprogramm\|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 [[Externe Fragmentierung\|Verschwendung]], genutzt wird.		Der '''Slab allocator''' ist ein Verfahren zur [[Speicherverwaltung]], das viele [[Betriebssystem]]e und auch [[Anwendungsprogramm\|Anwendungen]] verwenden. Der Algorithmus hat zum Ziel, dass bei der häufig vorkommender Reservierung kleiner Speicherbereiche der vorhandene Arbeitsspeicher möglichst effizient, also mit wenig [[Externe Fragmentierung\|Verschwendung]], genutzt wird.

	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.		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.

Trustable: Einleitung

2022-01-09T16:27:09Z

Einleitung

← Nächstältere Version		Version vom 9. Januar 2022, 18:27 Uhr
Zeile 1:		Zeile 1:
	{{QS-Informatik\|Überflüssige allg. Erläuterungen; Keine sinnvolle Artikelstruktur; Klare Definition fehlt. Der englische Artikel kann zur Ausbesserung verwendet werden.\|Knacknüsse=1}}		{{QS-Informatik\|Überflüssige allg. Erläuterungen; Keine sinnvolle Artikelstruktur; Klare Definition fehlt. Der englische Artikel kann zur Ausbesserung verwendet werden.\|Knacknüsse=1}}

	Der '''Slab allocator''' ist ein Verfahren zur ~~Verwaltung von~~ [[~~Arbeitsspeicher~~]], das viele [[Betriebssystem]]e und auch [[Anwendungsprogramm\|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 [[Externe Fragmentierung\|Verschwendung]], genutzt wird.		Der '''Slab allocator''' ist ein Verfahren zur [[Speicherverwaltung]], das viele [[Betriebssystem]]e und auch [[Anwendungsprogramm\|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 [[Externe Fragmentierung\|Verschwendung]], genutzt wird.

	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.		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 ==		== Geschichte ==
	Entwickelt wurde der Slab allocator [[1994]] von [[Jeff Bonwick]] für [[Solaris (Betriebssystem)\|SunOS]] 5.4. Da er seine Vorgehensweise öffentlich dokumentiert hat, wurde sie von vielen anderen Betriebssystemen (z. B. [[Linux]]) und Anwendungen (z. B. [[Perl (Programmiersprache)\|Perl]]) übernommen. Im Jahr [[2001]] veröffentlichte Bonwick eine deutlich verbesserte Version, die ebenso öffentlich dokumentiert wurde.		Entwickelt wurde der Slab allocator 1994 von [[Jeff Bonwick]] für [[Solaris (Betriebssystem)\|SunOS]] 5.4. Da er seine Vorgehensweise öffentlich dokumentiert hat, wurde sie von vielen anderen Betriebssystemen (z. B. [[Linux]]) und Anwendungen (z. B. [[Perl (Programmiersprache)\|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.		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.

YMS: QS-Link-Fix

2021-06-11T22:49:30Z

QS-Link-Fix

Zero Thrust: HC: Entferne Kategorie:Betriebssystemtheorie

2021-04-10T05:06:32Z

HC: Entferne Kategorie:Betriebssystemtheorie

← Nächstältere Version		Version vom 10. April 2021, 07:06 Uhr
Zeile 164:		Zeile 164:
	[[Kategorie:Unix-Betriebssystemkomponente]]		[[Kategorie:Unix-Betriebssystemkomponente]]
	[[Kategorie:Speicherverwaltung]]		[[Kategorie:Speicherverwaltung]]
	[[Kategorie:Betriebssystemtheorie]]

Zero Thrust: HC: −Kategorie:Datenstruktur; +Kategorie:Speicherverwaltung; +Kategorie:Betriebssystemtheorie

2021-04-10T05:06:14Z

HC: −Kategorie:Datenstruktur; +Kategorie:Speicherverwaltung; +Kategorie:Betriebssystemtheorie

← Nächstältere Version		Version vom 10. April 2021, 07:06 Uhr
Zeile 161:		Zeile 161:

	[[Kategorie:Algorithmus]]		[[Kategorie:Algorithmus]]
⚫	[[Kategorie:~~Datenstruktur~~]]
	[[Kategorie:Linux-Betriebssystemkomponente]]		[[Kategorie:Linux-Betriebssystemkomponente]]
	[[Kategorie:Unix-Betriebssystemkomponente]]		[[Kategorie:Unix-Betriebssystemkomponente]]
		⚫	[[Kategorie:Speicherverwaltung]]
			[[Kategorie:Betriebssystemtheorie]]

Zero Thrust: /* Aufbau des Central Allocators */

2021-04-10T04:57:37Z

Aufbau des Central Allocators

← Nächstältere Version		Version vom 10. April 2021, 06:57 Uhr
Zeile 28:		Zeile 28:
	* Objekte desselben Typs werden zu '''Slabs''' (englisch: Kachel, Fliese) zusammengefasst.		* 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.		* 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 ~~darüber~~ liegende [[Buddy-Speicherverwaltung]], welche nur ganze Speicherseiten liefert.		* 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.		* 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.		Mit anderen Worten: Der Slab allocator teilt den vom Buddy-System gelieferten Speicher weiter auf.
	Der Central Allocator bietet Schnittstellen ([[Application Programming Interface\|APIs]]) an, über ~~die~~ die Clients Speicher anfordern können.		Der Central Allocator bietet Schnittstellen ([[Application Programming Interface\|APIs]]) an, über die Clients Speicher anfordern können.

	== Caches ==		== Caches ==

Crazy1880: prettytable > wikitable

2019-09-13T19:19:44Z

prettytable > wikitable

← Nächstältere Version		Version vom 13. September 2019, 21:19 Uhr
Zeile 50:		Zeile 50:
	Es gibt unter Linux Laufzeitinformationen zum Slab allocator in der Datei /proc/slabinfo. Die folgende beispielhafte Ausgabe ist stark gekürzt.		Es gibt unter Linux Laufzeitinformationen zum Slab allocator in der Datei /proc/slabinfo. Die folgende beispielhafte Ausgabe ist stark gekürzt.

	{\| class="~~prettytable~~"		{\| class="wikitable"
			\|-
	! name \|\| <active_objs> \|\| <num_objs> \|\| <objsize> \|\| <objperslab> \|\| <pagesperslab> : tunables \|\| <batchcount>		! name \|\| <active_objs> \|\| <num_objs> \|\| <objsize> \|\| <objperslab> \|\| <pagesperslab> : tunables \|\| <batchcount>
	\|-		\|-
Zeile 152:		Zeile 153:
	== Literatur ==		== Literatur ==
	* Wolfgang Mauerer: ''Linux Kernelarchitektur.'' Hanser, 2004. ISBN 3-446-22566-8		* Wolfgang Mauerer: ''Linux Kernelarchitektur.'' Hanser, 2004. ISBN 3-446-22566-8
	* Andrew S. Tanenbaum: ''Modern Operating Systems.'' Prentice Hall, 2001. Englisch, ISBN 0-~~130~~-~~92641~~-8		* Andrew S. Tanenbaum: ''Modern Operating Systems.'' Prentice Hall, 2001. Englisch, ISBN 0-13-092641-8

	== Weblinks ==		== Weblinks ==

78.43.53.90: /* Interne Fragmentierung */

2019-04-24T13:07:44Z

Interne Fragmentierung

← Nächstältere Version		Version vom 24. April 2019, 15:07 Uhr
Zeile 115:		Zeile 115:
	# Verschnitt am Ende des Slabs, denn in den seltensten Fällen ergeben die Objekte im Slab genau dessen Größe.		# 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 <math>\frac{1}{Objektanzahl}</math> 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.		Der Verschnitt am Ende ist kleiner als <math>\frac{1}{\text{Objektanzahl}}</math> 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 ====

← Nächstältere Version		Version vom 12. Juni 2021, 00:49 Uhr
Zeile 1:		Zeile 1:
	{{QS-Informatik\|Überflüssige allg. Erläuterungen; Keine sinnvolle Artikelstruktur; Klare Definition fehlt. Der englische Artikel kann zur Ausbesserung verwendet werden.}}		{{QS-Informatik\|Überflüssige allg. Erläuterungen; Keine sinnvolle Artikelstruktur; Klare Definition fehlt. Der englische Artikel kann zur Ausbesserung verwendet werden.\|Knacknüsse=1}}

	Der '''Slab allocator''' ist ein Verfahren zur Verwaltung von [[Arbeitsspeicher]], das viele [[Betriebssystem]]e und auch [[Anwendungsprogramm\|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 [[Externe Fragmentierung\|Verschwendung]], genutzt wird.		Der '''Slab allocator''' ist ein Verfahren zur Verwaltung von [[Arbeitsspeicher]], das viele [[Betriebssystem]]e und auch [[Anwendungsprogramm\|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 [[Externe Fragmentierung\|Verschwendung]], genutzt wird.

Zeile 26:		Zeile 27:
	=== Aufbau des Central Allocators ===		=== Aufbau des Central Allocators ===
	Folgender Aufbau wird nun von Bonwick vorgeschlagen:		Folgender Aufbau wird nun von Bonwick vorgeschlagen:

	* Objekte desselben Typs werden zu '''Slabs''' (englisch: Kachel, Fliese) zusammengefasst.		* 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.		* Diese Slabs werden unter einem '''Cache''' organisiert, es werden also weitere Objekte desselben Typs auf Vorrat gehalten.
Zeile 37:		Zeile 39:
	=== Aufgaben ===		=== Aufgaben ===
	Die Caches besitzen drei Aufgaben:		Die Caches besitzen drei Aufgaben:

	* Sie stellen Vorräte von oft benutzten Objekten fertig initialisiert zur Verfügung.		* 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 <math>2^5 = 32</math> bis <math>2^{17} = 131072</math> Bytes.		* 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 <math>2^5 = 32</math> bis <math>2^{17} = 131072</math> Bytes.
Zeile 42:		Zeile 45:

	=== Aufbau ===		=== 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"~~).		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.		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.
Zeile 157:		Zeile 160:
	== Weblinks ==		== Weblinks ==
	* [http://www.usenix.org/publications/library/proceedings/bos94/full_papers/bonwick.ps Bonwicks Beschreibung des Slab allocators, 1994] ([[PostScript]])		* [http://www.usenix.org/publications/library/proceedings/bos94/full_papers/bonwick.ps Bonwicks Beschreibung des Slab allocators, 1994] ([[PostScript]])
	* [http://www.usenix.org/event/usenix01/full_papers/bonwick/bonwick.pdf Bonwicks Beschreibung des Slab allocators, 2001] ([[Portable Document Format\|PDF]]; 131 kB)		* [http://www.usenix.org/event/usenix01/full_papers/bonwick/bonwick.pdf Bonwicks Beschreibung des Slab allocators, 2001] ([[Portable Document Format\|PDF]]; 131 kB)
	* [http://krohlas.de/computing/ Vortrag über den Linux Slab allocator] Sven Krohlas, Uni Karlsruhe, WS 2004/2005		* [http://krohlas.de/computing/ Vortrag über den Linux Slab allocator] Sven Krohlas, Uni Karlsruhe, WS 2004/2005