Přidělení desek - Slab allocation - Wikipedia

Nesmí být zaměňována s Deska (jednotka).

Přidělení desek je správa paměti mechanismus určený pro efektivní alokaci paměti objektů. Ve srovnání s dřívějšími mechanismy se snižuje fragmentace způsobené alokacemi a deallokacemi. Tato technika se používá k uchování přidělené paměti, která obsahuje datový objekt určitého typu, pro opětovné použití při následném přidělení objektů stejného typu. Je to analogické s fond objektů, ale týká se pouze paměti, nikoli jiných zdrojů.

Přidělení desek bylo poprvé představeno v Solaris 2.4 jádro Jeff Bonwick.[1] To je nyní široce používáno mnoha Unix a Unix-like operační systémy včetně FreeBSD[2] a Linux.[3]

Základ

Primární motivací pro alokaci desky je to, že náklady (v čase CPU) na inicializaci a zničení datových objektů jádra mohou převážit náklady na přidělení paměti pro ně.[1] Jelikož jádro často vytváří a maže objekty, režijní náklady inicializace mohou mít za následek výrazné poklesy výkonu. Ukládání do mezipaměti objektů vede k méně častému vyvolání funkcí, které inicializují stav objektu: když je objekt přidělený desce uvolněn po použití, systém přidělení desky ji obvykle uloží do mezipaměti (místo aby ji zničil) připravenou k opětovnému použití příště je potřebný objekt tohoto typu (čímž se zabrání konstrukci a inicializaci nového objektu).

S alokací desky má mezipaměť pro určitý typ nebo velikost datového objektu řadu předem přidělených „desek“ paměti; uvnitř každé desky jsou bloky paměti pevné velikosti vhodné pro objekty.[4] Deskový alokátor sleduje tyto bloky, takže když obdrží požadavek na přidělení paměti pro datový objekt určitého typu, obvykle může uspokojit požadavek s volným slotem (blokem) ze stávající desky. Když je alokátor požádán o uvolnění paměti objektu, pouze přidá slot do seznamu volných (nepoužitých) slotů obsahujícího slab. Další volání k vytvoření objektu stejného typu (nebo přidělení paměti stejné velikosti) vrátí tento paměťový slot (nebo nějaký jiný volný slot) a odebere jej ze seznamu volných slotů. Tento proces eliminuje potřebu hledat vhodný paměťový prostor a výrazně snižuje fragmentaci paměti. V tomto kontextu je deska jednou nebo více souvislými stránkami v paměti obsahujícími předem přidělené bloky paměti.

Implementace

Pochopení algoritmu alokace desek vyžaduje definování a vysvětlení některých pojmů:

  1. Mezipaměti: cache představuje malé množství velmi rychlé paměti. Mezipaměť je úložiště pro konkrétní typ objekt, jako semafory, proces deskriptory, soubor předměty atd.
  2. Deska: deska představuje souvislou část paměti, obvykle vyrobenou z několika fyzicky sousedících stránek. Deska je skutečný kontejner dat spojených s objekty konkrétního druhu obsahující mezipaměť.

Když program nastaví mezipaměť, přidělí počet objektů do desek přidružených k této mezipaměti. Toto číslo závisí na velikosti přidružených desek.

Desky mohou existovat v jednom z následujících stavů:

  1. prázdný - všechny objekty na desce označené jako volné
  2. částečný - deska se skládá z použitých i volných předmětů
  3. úplný - všechny objekty na desce označené jako použité

Zpočátku systém označí každou desku jako „prázdnou“. Když proces vyžaduje nový objekt jádra, systém se pokusí najít volné umístění pro tento objekt na částečné desce v mezipaměti pro tento typ objektu. Pokud takové umístění neexistuje, systém přidělí novou desku ze souvislých fyzických stránek a přiřadí ji do mezipaměti. Nový objekt bude přidělen z této desky a jeho umístění bude označeno jako „částečné“.

Alokace probíhá rychle, protože systém sestavuje objekty předem a snadno je alokuje z desky.

Desky

Deska je množství, o které může mezipaměť růst nebo zmenšovat se. Představuje jedno přidělení paměti do mezipaměti ze stroje a jehož velikost je obvykle násobkem velikost stránky. Deska musí obsahovat seznam volných Nárazníky (nebo bufctls), stejně jako seznam bufctls, které byly přiděleny (v případě velké velikosti desky).[Citace je zapotřebí ]

Velké desky

Jedná se o mezipaměti, které ukládají objekty, které mají alespoň 1/8 velikosti stránky pro daný stroj. Důvodem toho, že velké desky mají jiné rozložení než malé desky, je to, že umožňuje, aby se velké desky lépe zabalily do jednotek velikosti stránky, což pomáhá při fragmentaci. Deska obsahuje seznam bufctlů, které jsou jednoduše řadiči pro každou vyrovnávací paměť, kterou lze přidělit (vyrovnávací paměť je paměť, kterou by používal alokátor desky).

Malé desky

Malé desky obsahují objekty, které jsou menší než 1/8 velikosti stránky pro daný stroj. Tyto malé desky je třeba dále optimalizovat z logického rozvržení tím, že se vyhneme použití bufctls (které by byly stejně velké jako samotná data a způsobily by mnohem větší využití paměti). Malá deska je přesně jedna stránka a má definovanou strukturu, která umožňuje vyhnout se bufctlům. Poslední část stránky obsahuje „záhlaví desky“, což jsou informace potřebné k zachování desky. Počínaje první adresou této stránky existuje tolik vyrovnávacích pamětí, kolik je možné přidělit, aniž by došlo ke spuštění do záhlaví slab na konci stránky.

Namísto použití bufctlů používáme samotné vyrovnávací paměti k uchování odkazů na bezplatný seznam. To umožňuje obejít bufctl malé desky.[1]

Systémy využívající alokaci desek

Viz také

Poznámky

  1. ^ A b C Jeff Bonwick,Slab Allocator: An Object-Caching Kernel Memory Allocator (1994)
  2. ^ Příručka pro vývojáře jádra FreeBSD
  3. ^ M. Tim Jones, Anatomie linuxového deskového alokátoru Archivováno 2. října 2013 v Wayback Machine
  4. ^ Abraham Silberschatz et al.: Koncepty operačních systémů. Wiley: 2004. ISBN  0-471-69466-5
  5. ^ „Dokumentace alokátoru Gnu Macha“.
  6. ^ „Zabezpečení konzoly - přepínač (34c3)“. media.ccc.de. Citováno 28. prosince 2017.
  7. ^ Chris Cooper a Chris Moore, Interní zařízení HP-UX 11i, Upper Saddle River, New Jersey: Prentice Hall PTR, 2004, ISBN  0-13-032861-8, str. 334.
  8. ^ Hutchings, Ben (29. března 2012). "Re: CONFIG_SLAB = y v jádře 3.2".
  9. ^ „Perl5-Porters Weekly: 2012 June 17“. Citováno 18. listopadu 2012.
  10. ^ Bonwick, Jeff. „Magazines and Vmem: Extension the Slab Allocator to Many CPUs and arbitre resources“. USENIX 2001. Citováno 18. listopadu 2012.

externí odkazy