Alokacja pamięci znajomego

Technika alokacji pamięci znajomego to algorytm alokacji pamięci , który dzieli pamięć na partycje, aby spróbować jak najlepiej spełnić żądanie pamięci. Ten system wykorzystuje podział pamięci na połowy, aby spróbować jak najlepiej dopasować. Według Donalda Knutha system partnerski został wynaleziony w 1963 roku przez Harry'ego Markowitza , a po raz pierwszy został opisany przez Kennetha C. Knowltona (opublikowane w 1965). Alokacja pamięci Buddy jest stosunkowo łatwa do wdrożenia. Obsługuje ograniczone, ale wydajne dzielenie i łączenie bloków pamięci .

Algorytm

Istnieją różne formy systemu koleżeńskiego; te, w których każdy blok jest podzielony na dwa mniejsze bloki, są najprostszą i najczęstszą odmianą. Każdy blok pamięci w tym systemie ma kolejność , gdzie kolejność jest liczbą całkowitą z zakresu od 0 do określonej górnej granicy. Rozmiar bloku rzędu n jest proporcjonalny do 2 n , więc bloki są dokładnie dwa razy większe od bloków o jeden rząd niższych. Rozmiary bloków oparte na potędze dwóch sprawiają, że obliczanie adresu jest proste, ponieważ wszyscy kumple są wyrównani na granicach adresów pamięci, które są potęgami dwójki. Kiedy większy blok jest podzielony, jest on dzielony na dwa mniejsze bloki, a każdy mniejszy blok staje się unikalnym kumplem drugiego. Podzielony blok można połączyć tylko z jego unikalnym blokiem kumpla, który następnie przekształca większy blok, z którego został podzielony.

Na początku określany jest rozmiar najmniejszego możliwego bloku, tj. najmniejszego bloku pamięci, który można przydzielić. Gdyby w ogóle nie istniał żaden dolny limit (np. możliwe byłyby alokacje wielkości bitów), byłoby dużo pamięci i narzutu obliczeniowego dla systemu, aby śledzić, które części pamięci są przydzielone, a które nieprzydzielone. Jednak może być pożądane raczej niskie ograniczenie, tak aby zminimalizować średnie marnotrawstwo pamięci na alokację (dotyczącą alokacji, które pod względem rozmiaru nie są wielokrotnościami najmniejszego bloku). Zazwyczaj dolna granica byłaby wystarczająco mała, aby zminimalizować średnie marnowanie miejsca na alokację, ale wystarczająco duża, aby uniknąć nadmiernych narzutów. Najmniejszy rozmiar bloku jest następnie traktowany jako rozmiar bloku rzędu 0, tak że wszystkie wyższe rzędy są wyrażone jako potęga dwóch wielokrotności tego rozmiaru.

Programista musi następnie zdecydować lub napisać kod, aby uzyskać najwyższą możliwą kolejność, która zmieści się w pozostałej dostępnej przestrzeni pamięci. Ponieważ całkowita dostępna pamięć w danym systemie komputerowym może nie być wielokrotnością potęgi dwójki minimalnego rozmiaru bloku, największy rozmiar bloku może nie obejmować całej pamięci systemu. Na przykład, jeśli system miał 2000 K pamięci fizycznej, a rozmiar bloku rzędu 0 wynosił 4 K, górna granica rzędu wynosiłaby 8, ponieważ blok rzędu 8 (256 bloków rzędu 0, 1024 K) to największy blok, który zmieści się w pamięci. W związku z tym niemożliwe jest przydzielenie całej pamięci fizycznej w jednym kawałku; pozostałe 976 K pamięci musiałoby być przydzielane w mniejszych blokach.

Przykład

Poniżej przedstawiono przykład tego, co się dzieje, gdy program wysyła żądania dotyczące pamięci. Załóżmy, że w tym systemie najmniejszy możliwy blok ma rozmiar 64 kilobajtów, a górna granica rzędu to 4, co daje największy możliwy do przydzielenia blok, 2 4 razy 64 K = 1024 K. Poniżej przedstawiono możliwy stan systemu po różnych żądaniach pamięci.

Krok 64 k 64 k 64 k 64 k 64 k 64 k 64 k 64 k 64 k 64 k 64 k 64 k 64 k 64 k 64 k 64 k
1 2 4
2.1 2 3 2 3
2.2 2 2 2 2 2 3
2.3 2 1 2 1 2 2 2 3
2.4 20 20 2 1 2 2 2 3
2.5 O: 20 20 2 1 2 2 2 3
3 O: 20 20 B: 2 1 2 2 2 3
4 O: 20 C: 20 B: 2 1 2 2 2 3
5.1 O: 20 C: 20 B: 2 1 2 1 2 1 2 3
5.2 O: 20 C: 20 B: 2 1 D: 2 1 2 1 2 3
6 O: 20 C: 20 2 1 D: 2 1 2 1 2 3
7.1 O: 20 C: 20 2 1 2 1 2 1 2 3
7.2 O: 20 C: 20 2 1 2 2 2 3
8 20 C: 20 2 1 2 2 2 3
9.1 20 20 2 1 2 2 2 3
9.2 2 1 2 1 2 2 2 3
9.3 2 2 2 2 2 3
9.4 2 3 2 3
9.5 2 4

Alokacja ta mogła nastąpić w następujący sposób

  1. Sytuacja początkowa.
  2. Program A żąda pamięci 34 K, rząd 0.
    1. Brak dostępnych bloków rzędu 0, więc blok rzędu 4 jest dzielony, tworząc dwa bloki rzędu 3.
    2. Nadal nie ma dostępnych bloków rzędu 0, więc pierwszy blok rzędu 3 jest dzielony, tworząc dwa bloki rzędu 2.
    3. Nadal nie ma dostępnych bloków rzędu 0, więc pierwszy blok rzędu 2 jest dzielony, tworząc dwa bloki rzędu 1.
    4. Nadal nie ma dostępnych bloków rzędu 0, więc pierwszy blok rzędu 1 jest dzielony, tworząc dwa bloki rzędu 0.
    5. Teraz dostępny jest blok zamówienia 0, więc jest on przydzielony do A.
  3. Program B żąda pamięci 66 K, rząd 1. Dostępny jest blok rzędu 1, więc jest on przydzielony do B.
  4. Program C żąda pamięci 35 K, rząd 0. Dostępny jest blok rzędu 0, więc jest on przydzielony do C.
  5. Program D żąda pamięci 67 K, kolejność 1.
    1. Brak dostępnych bloków zamówienia 1, więc blok zamówienia 2 jest dzielony, tworząc dwa bloki zamówienia 1.
    2. Teraz dostępny jest blok zamówienia 1, więc jest on przydzielony do D.
  6. Program B zwalnia swoją pamięć, zwalniając jeden rozkaz 1 blok.
  7. Program D zwalnia swoją pamięć.
    1. Jedno zlecenie 1 blok zostaje zwolnione.
    2. Ponieważ blok kumpla nowo uwolnionego bloku jest również wolny, oba są łączone w jeden blok zamówienia 2.
  8. Program A zwalnia swoją pamięć, zwalniając jeden blok rzędu 0.
  9. Program C zwalnia swoją pamięć.
    1. Jeden blok zamówienia 0 zostaje zwolniony.
    2. Ponieważ blok znajomego nowo uwolnionego bloku jest również wolny, oba są łączone w jeden blok zamówienia 1.
    3. Ponieważ blok kumpla nowo utworzonego bloku zamówienia 1 jest również wolny, oba są łączone w jeden blok zamówienia 2.
    4. Ponieważ blok partnera nowo utworzonego bloku zamówienia 2 jest również wolny, oba są łączone w jeden blok zamówienia 3.
    5. Ponieważ blok kumpla nowo utworzonego bloku zamówienia 3 jest również wolny, oba są łączone w jeden blok zamówienia 4.

Jak widać, co się dzieje, gdy wysyłane jest żądanie pamięci, wygląda następująco:

  • Jeśli pamięć ma być przydzielona
  1. Poszukaj gniazda pamięci o odpowiednim rozmiarze (minimalny blok 2 k , który jest większy lub równy żądanej pamięci)
    1. Jeśli zostanie znaleziony, zostanie przydzielony do programu
    2. Jeśli nie, próbuje utworzyć odpowiednie gniazdo pamięci. System robi to, próbując wykonać następujące czynności:
      1. Podziel wolne gniazdo pamięci większe niż żądany rozmiar pamięci na pół
      2. Jeśli dolny limit zostanie osiągnięty, przydziel tę ilość pamięci
      3. Wróć do kroku 1 (poszukaj gniazda pamięci o odpowiednim rozmiarze)
      4. Powtarzaj ten proces, aż zostanie znalezione odpowiednie gniazdo pamięci
  • Jeśli pamięć ma zostać uwolniona
  1. Zwolnij blok pamięci
  2. Spójrz na sąsiedni blok – czy tam też jest za darmo?
  3. Jeśli tak, połącz oba i wróć do kroku 2 i powtarzaj ten proces, aż zostanie osiągnięta górna granica (cała pamięć zostanie zwolniona) lub do napotkania niewolnego sąsiedniego bloku

Implementacja i efektywność

W porównaniu z innymi prostszymi technikami, takimi jak alokacja dynamiczna , system pamięci kumpla charakteryzuje się niewielką fragmentacją zewnętrzną i umożliwia zagęszczanie pamięci przy niewielkim nakładzie pracy. Metoda kumpelska zwalniania pamięci jest szybka, a maksymalna wymagana liczba zagęszczeń jest równa log 2 (najwyższy rząd). Zazwyczaj system alokacji pamięci kumpla jest realizowany przy użyciu drzewa binarnego do reprezentowania używanych lub nieużywanych podzielonych bloków pamięci. Adres „kumpla” bloku jest równy bitowej wyłącznej LUB (XOR) adresu bloku i rozmiaru bloku.

Jednak nadal istnieje problem wewnętrznej fragmentacji – marnowanie pamięci, ponieważ żądana pamięć jest trochę większa niż mały blok, ale dużo mniejsza niż duży blok. Ze względu na sposób działania techniki alokacji pamięci przez kumpla, programowi żądającemu 66 KB pamięci zostanie przydzielone 128 KB, co spowoduje stratę 62 KB pamięci. Ten problem można rozwiązać przez przydział płytowy , który można nałożyć warstwami na bardziej zgrubny alokator znajomych, aby zapewnić bardziej szczegółowy przydział.

Jedna z wersji algorytmu alokacji znajomych została szczegółowo opisana przez Donalda Knutha w pierwszym tomie The Art of Computer Programming . Jądro Linuksa korzysta również z systemu buddy, z dalszymi modyfikacjami w celu zminimalizowania zewnętrznej fragmentacji, wraz z różnymi innymi alokatorami do zarządzania pamięcią w blokach.

jemalloc to nowoczesny alokator pamięci, który wykorzystuje m.in. technikę buddy.

Zobacz też

  1. Bibliografia _ Szybki alokator pamięci masowej. Komunikaty ACM 8 (10): 623–625, październik 1965. także Kenneth C Knowlton. Opis programisty L6. Communications of the ACM , 9(8):616–625, sierpień 1966 [patrz też: Googlebooks [1] strona 85]
  2. ^   Knuth, Donald (1997). Podstawowe algorytmy . Sztuka programowania komputerowego . Tom. 1 (wyd. Drugie). Reading, Massachusetts: Addison-Wesley. s. 435–455. ISBN 0-201-89683-4 .
  3. ^   Mauerer, Wolfgang (październik 2008). Profesjonalna architektura jądra Linuksa . Wrox Press . ISBN 978-0-470-34343-2 .
  4. ^ Evans, Jason (16 kwietnia 2006), A Scalable Concurrent malloc (3) Implementation for FreeBSD (PDF) , s. 4–5
Pobrano z „ https://en.wikipedia.org/w/index.php?title=Buddy_memory_allocation&oldid=1137024966 ”