algorytm bliźniaków - Buddy memory allocation

Algorytm bliźniaków technika jest alokacja pamięci algorytm, który dzieli pamięć na partycje, aby spróbować zaspokoić żądania pamięci, odpowiednio, jak to możliwe. System ten sprawia, że korzystanie z pamięci łupania na połówki, aby spróbować dać najlepsze dopasowanie. Według Donald Knuth , system kolego wynaleziono w 1963 roku przez Harry Markowitz i został po raz pierwszy opisany przez Kennetha C Knowlton (opublikowany w 1965). Algorytm bliźniaków jest stosunkowo łatwe do wdrożenia. Obsługuje on ograniczony, ale efektywne dzielenie i koalescencyjne bloków pamięci .

Jak to działa

Istnieją różne formy systemu buddy; w których każdy blok jest dzielony na dwa mniejsze bloki są najprostszy i najczęściej odmiany. Każdy blok pamięci w tym systemie jest to kolejność , w której kolejność jest liczbą całkowitą w zakresie od 0 do określonej górnej granicy. Rozmiar bloku rzędu n jest proporcjonalna do 2 ^N , tak że bloki są dokładnie dwa razy większa od bloków, które są o rząd niższą. Power-of-dwa rozmiary bloku dokonać obliczeń adres proste, ponieważ wszyscy kumple są wyrównane w pamięci granice adresowych, które są potęgami dwójki. Kiedy większy blok jest podzielony, jest ona podzielona na dwa mniejsze bloki, a każdy mniejszy blok staje się wyjątkowy kumpel do drugiego. Blok podziału może zostać połączone tylko z unikalną bloku kolego, który następnie reformy większy blok oni podzielić z.

Ruszanie, wielkość najmniejszej bloku jest określona, czyli najmniejszego bloku pamięci, które mogą być przydzielone. Jeśli istniał żaden dolna granica w ogóle (np przydziały bitowe wielkości było możliwe), nie byłoby dużo pamięci i napowietrznych obliczeniowej dla systemu, aby śledzić, które części pamięci są przydzielone i nieprzydzielone. Jednakże dość niska wartość graniczna może być pożądane, tak, że średnia strata pamięci na przydział (dotyczące alokacji, która jest w wielkości, nie wielokrotność najmniejszej bloku) jest zminimalizowane. Zwykle dolna granica wystarczy, aby zmniejszyć średnią zmarnowane miejsce podziału za małe, ale na tyle duża, aby uniknąć nadmiernego narzutu. Najmniejszy rozmiar bloku jest następnie traktowane jako wielkości zlecenia-0 bloku, tak, że wszystkie wyższych rzędów są wyrażone jako moc dwójki wielokrotności tej wielkości.

Programista musi wtedy zdecydować się na, lub napisać kod, aby uzyskać najwyższy możliwy porządek, który zmieści się w pozostałej dostępnej pamięci. Ponieważ całkowita ilość dostępnej pamięci w danym systemie komputerowym mogą być wielokrotnością minimalnego rozmiaru bloku zasilania dwójki, największy rozmiar bloku może rozciągać się na całej pamięci systemu. Na przykład, jeśli system ma 2000 K pamięci fizycznej i kolejność-0 rozmiarem bloku wynosiła 4 K, przy czym górna granica rzędu byłaby 8, ponieważ w zamówieniu 8 bloku (256 zleceniem 0 blokach, 1024 k) największy blok, który zmieści się w pamięci. W związku z tym niemożliwe jest przeznaczyć całą pamięć fizyczną w jednym kawałku; pozostałe 976 K pamięci musiałyby zostać przydzielone w mniejszych bloków.

W praktyce

Poniżej jest przykład tego, co dzieje się, gdy program sprawia, że wnioski o pamięci. Załóżmy, że w tym systemie, jak najmniejsza bloku wynosi 64 kilobajtów wielkości, a górna granica jest rzędu 4, która prowadzi do największego możliwego allocatable bloku, 2 ⁴ razy 64 K = 1024 K, pod względem wielkości. Poniżej przedstawiono możliwy stan systemu po różnych żądań pamięci.

Krok	64k	64k	64k	64k	64k	64k
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 ⁴

Ten podział może mieć miejsce w sposób następujący

Początkowa sytuacja.
Program A prosi pamięci 34 K, porządek 0.
1. Żadne zamówienie 0 bloki są dostępne, więc rozkaz 4 blok jest podzielona, tworząc dwa zamówienia 3 bloki.
2. Nadal nie ma order 0 bloki dostępne, więc pierwszego rzędu 3 blok jest podzielony, tworząc dwie zamówienie 2 bloki.
3. Nadal nie ma order 0 bloki dostępne, więc pierwszego rzędu 2 blok jest podzielony, tworząc dwie zamówienie 1 bloków.
4. Nadal nie ma order 0 bloki dostępne, więc pierwsze zamówienie 1 blok jest podzielony, tworząc dwie zamówienie 0 bloków.
5. Teraz rozkaz 0 blok jest dostępny, więc to jest alokowana do A.
Program B żądania pamięci 66 k kolejności: 1. Rozkaz jeden blok jest dostępne, to jest przeznaczona do B.
Program C żądania pamięci 35 K, porządek 0. Zlecenie 0 blok jest dostępny, więc to jest alokowana do C.
Program D żąda pamięci 67 K, porządek 1.
1. Brak zamówienie 1 bloki są dostępne, więc rozkaz 2 blok jest podzielona, tworząc dwie zamówienie 1 bloków.
2. Teraz zamówienie 1 blok jest dostępny, więc to jest alokowana do D.
Program B uwalnia pamięć, uwalniając jedno zamówienie 1 blok.
Program D uwalnia swoją pamięć.
1. Jeden rząd jeden blok jest zwolniona.
2. Ponieważ blok kolego nowo uwolniona bloku jest wolny, oba są połączone do jednego rzędu dwóch bloków.
Program A uwalnia pamięć, uwalniając jednym zamówieniu 0 blok.
Program C uwalnia swoją pamięć.
1. Jeden rząd 0 blok jest zwolniona.
2. Ponieważ blok kolego nowo uwolniona bloku jest wolny, dwa są połączone w jeden rząd 1 bloku.
3. Ponieważ blok kolego nowo utworzonego celu blok 1 jest wolna, oba są połączone do jednego rzędu dwóch bloków.
4. Ponieważ blok kolego nowo utworzonego rzędu 2 kostki jest również wolny, dwa są połączone w jeden rząd trzech bloków.
5. Ponieważ blok kolego nowo utworzonego rzędu 3 bloku jest wolny, dwa są połączone w jeden rząd 4 bloku.

Jak widać, co się dzieje, gdy żądanie pamięci składa się następująco:

Jeśli pamięć jest przydzielane

Sprawdzić gniazda pamięci o odpowiednim rozmiarze (na minimalnym 2 ^k bloku, który jest większy lub równy od żądanej pamięci)
1. Jeżeli okaże się, że jest przeznaczona na realizację programu
2. Jeśli nie, to próbuje dokonać odpowiedniego gniazda pamięci. System działa tak, próbując co następuje:
  1. Podzielone wolne gniazdo pamięci większej niż wnioskowanej wielkości pamięci w połowie
  2. Jeśli zostanie osiągnięta dolna granica, a następnie przeznaczyć taką ilość pamięci
  3. Wrócić do punktu 1 (patrz na gnieździe pamięci o odpowiedniej wielkości)
  4. Powtarzanie tego procesu, dopóki odpowiednie gniazdo pamięci znajduje się

Jeśli pamięć zostanie zwolniona

Wolny blok pamięci
Spójrz w sąsiednim bloku - jest to zbyt wolne?
Jeżeli tak, to połączenie tych dwóch, i powrót do kroku 2, i powtórzyć tę czynność, aż osiągnie albo górna granica (wszystkie pamięć zwolniona), albo do bloku bez wolnej sąsiada napotkaniu

Wdrożenie i efektywność

W porównaniu do innych prostych technik, takich jak dynamicznej alokacji system pamięci kolego ma niewielkie rozdrobnienie zewnętrznych i umożliwia zagęszczania pamięci o małym obciążeniu. Metoda kumpel uwalniając pamięć jest szybka, z maksymalnej liczby wymaganych do zagęszczania równy log ₂ (najwyższy porządek). Zazwyczaj system algorytm bliźniaków jest realizowany przy użyciu binarnego drzewa do reprezentują wykorzystane lub nie podzielonych bloków pamięci. W „kumpel” z każdego bloku można znaleźć ze związkiem wykluczająca z adresu bloku i rozmiaru bloku.

Jednak wciąż istnieje problem fragmentacji wewnętrznej - pamięć zmarnowane, ponieważ żądana pamięć jest trochę większy niż w małym bloku, ale dużo mniejszy niż w dużym bloku. Ze względu na sposób technika algorytm bliźniaków działa, program, który żąda 66 K pamięci zostanie przydzielone 128 K, co skutkuje stratą 62 K pamięci. Problem ten może być rozwiązany przez przydział płyty , który nanosi się warstwą w górnej części bardziej gruboziarnistej znajomych programu przydzielającego w celu zapewnienia bardziej precyzyjną przyporządkowania.

Jedna z wersji algorytmu alokacji kumpel został szczegółowo opisany przez Donald Knuth w tomie 1 Sztuka programowania . Kernel wykorzystuje również układ stary, z dalszymi modyfikacjami minimalizacji rozdrobnienia zewnętrznego, wraz z różnymi innymi podzielników zarządzać pamięcią w blokach.

jemalloc Jest to nowoczesny podzielnik pamięci, który wykorzystuje m.in. technikę kolego.

Zobacz też

Referencje

^ Kenneth C Knowlton. A Duża przechowywania podzielnik. Communications of the ACM 8 (10): 623-625, październik 1965. również Kenneth C Knowlton. Opis programisty od L6. Communications of the ACM , 9 (8): 616-625, sierpień 1966 [patrz także: książki Google [1] na stronie 85]
^ Knuth Donald (1997). Podstawowe algorytmy . Sztuka programowania . 1 (drugie wyd.). Reading, Massachusetts: Addison-Wesley. ss. 435-455. ISBN 0-201-89683-4 .
^ Mauerer, Wolfgang (październik 2008). Profesjonalne Linux Kernel Architecture . Wrox Prasa . ISBN 978-0-470-34343-2 .
^ Evans, Jason (16 kwietnia 2006), skalowalną Jednoczesne Realizacja dla FreeBSD (PDF) , str. 4-5 malloc(3)

[1] Kenneth C Knowlton. A Duża przechowywania podzielnik. Communications of the ACM 8 (10): 623-625, październik 1965. również Kenneth C Knowlton. Opis programisty od L6. Communications of the ACM , 9 (8): 616-625, sierpień 1966 [patrz także: książki Google [1] na stronie 85]

[2] Knuth Donald (1997). Podstawowe algorytmy . Sztuka programowania . 1 (drugie wyd.). Reading, Massachusetts: Addison-Wesley. ss. 435-455. ISBN 0-201-89683-4 .

[3] Mauerer, Wolfgang (październik 2008). Profesjonalne Linux Kernel Architecture . Wrox Prasa . ISBN 978-0-470-34343-2 .

[4] Evans, Jason (16 kwietnia 2006), skalowalną Jednoczesne Realizacja dla FreeBSD (PDF) , str. 4-5 malloc(3)

Languages

In other projects