Přidělení paměti kamaráda - Buddy memory allocation

Alokace paměti kamarád technika je přidělování paměti algoritmus, který rozděluje paměť do oddílů se snaží uspokojit požadavek na paměti, jak vhodně, jak je to možné. Tento systém využívá rozdělení paměti na poloviny, aby se pokusil co nejlépe vyhovovat. Podle Donalda Knutha systém kamarádů vynalezl v roce 1963 Harry Markowitz a poprvé ho popsal Kenneth C. Knowlton (publikováno 1965). Alokace paměti Buddy je implementována relativně snadno. Podporuje omezené, ale efektivní rozdělení a splynutí paměťových bloků .

Algoritmus

Existují různé formy systému kamarádů; ty, ve kterých je každý blok rozdělen na dva menší bloky, jsou nejjednodušší a nejběžnější variantou. Každý paměťový blok v tomto systému má pořadí , kde pořadí je celé číslo v rozmezí od 0 do zadaného horního limitu. Velikost bloku řádu n je úměrná 2 ⁿ , takže bloky jsou přesně dvakrát větší než bloky o jeden řád nižší. Síla dvou bloků usnadňuje výpočet adresy, protože všichni kamarádi jsou zarovnáni na hranicích adres paměti, které jsou mocninami dvou. Když je větší blok rozdělen, je rozdělen na dva menší bloky a každý menší blok se stává pro druhého jedinečným kamarádem. Rozdělený blok lze sloučit pouze s jeho jedinečným blokem kamaráda, který poté reformuje větší blok, ze kterého byli rozděleni.

Na začátku se určí velikost nejmenšího možného bloku, tj. Nejmenšího bloku paměti, který lze přidělit. Pokud by vůbec neexistoval žádný dolní limit (např. Bylo možné přidělení bitové velikosti), systém by měl spoustu paměti a výpočetní režii, aby mohl sledovat, které části paměti jsou přiděleny a nepřiděleny. Může však být žádoucí poměrně nízký limit, takže je minimalizováno průměrné plýtvání pamětí na alokaci (týkající se alokací, jejichž velikost není násobkem nejmenšího bloku). Dolní limit by byl obvykle dostatečně malý, aby se minimalizovalo průměrné plýtvání prostorem na alokaci, ale dostatečně velký, aby se zabránilo nadměrné režii. Nejmenší velikost bloku je poté brána jako velikost bloku řádu 0, takže všechny vyšší řády jsou vyjádřeny jako síla dvou násobků této velikosti.

Programátor poté musí rozhodnout, nebo napsat kód, aby získal nejvyšší možné pořadí, které se vejde do zbývajícího dostupného paměťového prostoru. Protože celková dostupná paměť v daném počítačovém systému nemusí být dvojnásobkem minimální velikosti bloku, nemusí největší velikost bloku překlenout celou paměť systému. Například pokud by systém měl 2 000 K fyzické paměti a velikost bloku objednávky 0 byla 4 kB, horní limit objednávky by byl 8, protože blok řádu 8 (256 bloků řádu 0, 1024 K) je největší blok, který se vejde do paměti. V důsledku toho je nemožné alokovat celou fyzickou paměť do jednoho bloku; zbývajících 976 K paměti by muselo být přiděleno v menších blocích.

Příklad

Následuje příklad toho, co se stane, když program zadá požadavky na paměť. Řekněme, že v tomto systému má nejmenší možný blok velikost 64 kilobajtů a horní limit pro objednávku je 4, což má za následek největší možný přidělitelný blok, 2 ⁴ krát 64 K = 1024 K. Následující ukazuje možný stav systému po různých požadavcích na paměť.

Krok	64 K.	64 K.	64 K.	64 K.	64 K.	64 K.
1	2 ⁴
2.1	2 ³					2 ³
2.2	2 ²			2 ²		2 ³
2.3	2 ¹		2 ¹	2 ²		2 ³
2.4	2 ⁰	2 ⁰	2 ¹	2 ²		2 ³
2.5	A: 2 ⁰	2 ⁰	2 ¹	2 ²		2 ³
3	A: 2 ⁰	2 ⁰	B: 2 ¹	2 ²		2 ³
4	A: 2 ⁰	C: 2 ⁰	B: 2 ¹	2 ²		2 ³
5.1	A: 2 ⁰	C: 2 ⁰	B: 2 ¹	2 ¹	2 ¹	2 ³
5.2	A: 2 ⁰	C: 2 ⁰	B: 2 ¹	D: 2 ¹	2 ¹	2 ³
6	A: 2 ⁰	C: 2 ⁰	2 ¹	D: 2 ¹	2 ¹	2 ³
7.1	A: 2 ⁰	C: 2 ⁰	2 ¹	2 ¹	2 ¹	2 ³
7.2	A: 2 ⁰	C: 2 ⁰	2 ¹	2 ²		2 ³
8	2 ⁰	C: 2 ⁰	2 ¹	2 ²		2 ³
9.1	2 ⁰	2 ⁰	2 ¹	2 ²		2 ³
9.2	2 ¹		2 ¹	2 ²		2 ³
9.3	2 ²			2 ²		2 ³
9.4	2 ³					2 ³
9.5	2 ⁴

K této alokaci mohlo dojít následujícím způsobem

Počáteční situace.
Program A požaduje paměť 34 K, objednávka 0.
1. Nejsou k dispozici žádné bloky pořadí 0, takže blok objednávky 4 je rozdělen a vytvoří dva bloky objednávky 3.
2. Stále nejsou k dispozici žádné bloky pořadí 0, takže blok 3 prvního řádu je rozdělen a vytvoří dva bloky 2 řádu.
3. Stále nejsou k dispozici žádné bloky pořadí 0, takže blok 2 prvního řádu je rozdělen a vytvoří dva bloky řádu 1.
4. Stále nejsou k dispozici žádné bloky pořadí 0, takže první blok 1 řádu je rozdělen a vytvoří dva bloky 0 řádu.
5. Nyní je k dispozici blok objednávky 0, takže je přidělen A.
Program B požaduje paměť 66 K, objednávka 1. Blok objednávky 1 je k dispozici, takže je přidělen B.
Program C požaduje paměť 35 K, objednávka 0. Blok objednávky 0 je k dispozici, takže je přidělen C.
Program D požaduje paměť 67 K, objednávka 1.
1. Nejsou k dispozici žádné bloky řádu 1, takže blok objednávky 2 je rozdělen a vytvoří dva bloky řádu 1.
2. Nyní je k dispozici blok 1 objednávky, takže je přidělen D.
Program B uvolní svou paměť a uvolní jeden blok 1 objednávky.
Program D uvolní svoji paměť.
1. Jeden blok 1 objednávky je uvolněn.
2. Jelikož buddy blok nově uvolněného bloku je také volný, dva jsou sloučeny do jednoho řádu 2 bloku.
Program A uvolní svoji paměť a uvolní jeden blok 0 objednávky.
Program C uvolní svoji paměť.
1. Jeden blok 0 objednávky je uvolněn.
2. Protože buddy blok nově uvolněného bloku je také volný, dva jsou sloučeny do jednoho řádu 1 blok.
3. Protože buddy blok nově vytvořeného bloku řádu 1 je také volný, dva jsou sloučeny do jednoho bloku řádu 2.
4. Jelikož buddy blok nově vytvořeného bloku řádu 2 je také volný, dva jsou sloučeny do jednoho bloku řádu 3.
5. Protože buddy blok nově vytvořeného bloku řádu 3 je také volný, dva jsou sloučeny do jednoho bloku řádu 4.

Jak vidíte, co se stane, když se vytvoří požadavek na paměť, je následující:

Pokud má být přidělena paměť

Hledejte paměťový slot vhodné velikosti (minimální blok 2 ^k, který je větší nebo stejný jako blok požadované paměti)
1. Pokud je nalezen, je přidělen programu
2. Pokud ne, pokusí se vytvořit vhodný paměťový slot. Systém tak učiní vyzkoušením následujícího:
  1. Rozdělte volný paměťový slot větší než požadovaná velikost paměti na polovinu
  2. Pokud je dosaženo dolní meze, přidělte toto množství paměti
  3. Vraťte se ke kroku 1 (vyhledejte paměťový slot vhodné velikosti)
  4. Tento postup opakujte, dokud nenajdete vhodný paměťový slot

Pokud má být uvolněna paměť

Uvolněte blok paměti
Podívejte se na sousední blok - je to také zdarma?
Pokud je, zkombinujte je a vraťte se ke kroku 2 a opakujte tento proces, dokud nedosáhnete horní hranice (uvolní se veškerá paměť) nebo dokud nenarazíte na nesvobodný sousední blok.

Implementace a účinnost

Ve srovnání s jinými jednoduššími technikami, jako je dynamická alokace , má systém paměti kamaráda malou vnější fragmentaci a umožňuje zhutnění paměti s malou režií. Buddy metoda uvolnění paměti je rychlá, s maximálním počtem požadovaných zhutnění rovným log ₂ (nejvyššího řádu). Obvykle je systém přidělování paměti kamaráda implementován pomocí binárního stromu, který představuje použité nebo nepoužívané bloky rozdělené paměti. „Kamaráda“ každého bloku lze najít s výhradním NEBO adresou bloku a velikostí bloku.

Stále však existuje problém vnitřní fragmentace - zbytečná paměť, protože požadovaná paměť je o něco větší než malý blok, ale mnohem menší než velký blok. Kvůli způsobu, jakým funguje technika alokace paměti kamaráda, bude programu, který požaduje 66 K paměti, přiděleno 128 K, což má za následek ztrátu 62 K paměti. Tento problém lze vyřešit alokací desek , které mohou být navrstveny na hrubší alokátor kamaráda, aby poskytly jemnější alokaci.

Jedna verze algoritmu přidělování kamarádů byla podrobně popsána Donaldem Knuthem ve svazku 1 Umění počítačového programování . Linux kernel rovněž používá Buddy System, s dalšími modifikacemi, aby se minimalizovalo vnější fragmentace, společně s různými jinými allocators ke správě paměti uvnitř bloků.

jemalloc je moderní alokátor paměti, který mimo jiné využívá techniku buddy.

Viz také

Reference

^ Kenneth C. Knowlton. Rychlý alokátor úložiště. Sdělení ACM 8 (10): 623-625, říjen 1965. také Kenneth C Knowlton. Programátorský popis L6. Sdělení ACM , 9 (8): 616-625, srpen 1966 [viz také: Knihy Google [1] strana 85]
^ Knuth, Donald (1997). Základní algoritmy . Umění počítačového programování . 1 (druhé vydání). Reading, Massachusetts: Addison-Wesley. 435–455. ISBN 0-201-89683-4 .
^ Mauerer, Wolfgang (říjen 2008). Profesionální architektura Linuxového jádra . Wrox Press . ISBN 978-0-470-34343-2 .
^ Evans, Jason (16. dubna 2006), škálovatelná souběžná implementace pro FreeBSD (PDF) , str. 4–5 malloc(3)

[1] Kenneth C. Knowlton. Rychlý alokátor úložiště. Sdělení ACM 8 (10): 623-625, říjen 1965. také Kenneth C Knowlton. Programátorský popis L6. Sdělení ACM , 9 (8): 616-625, srpen 1966 [viz také: Knihy Google [1] strana 85]

[2] Knuth, Donald (1997). Základní algoritmy . Umění počítačového programování . 1 (druhé vydání). Reading, Massachusetts: Addison-Wesley. 435–455. ISBN 0-201-89683-4 .

[3] Mauerer, Wolfgang (říjen 2008). Profesionální architektura Linuxového jádra . Wrox Press . ISBN 978-0-470-34343-2 .

[4] Evans, Jason (16. dubna 2006), škálovatelná souběžná implementace pro FreeBSD (PDF) , str. 4–5 malloc(3)

Languages

In other projects