Algorytm bliźniaków

Z Wikipedii, wolnej encyklopedii
Skocz do: nawigacji, wyszukiwania

Algorytm bliźniaków (ang. buddy algorithm) - jest stosowaną w informatyce metodą alokacji pamięci, która charakteryzuje się dużą szybkością i łatwością implementacji oraz niską fragmentacją zewnętrzną, kosztem jednak znaczącej fragmentacji wewnętrznej.

W algorytmie zarządza się 2^n blokami pamięci (wartość n zależy od implementacji). Początkowo cała pamięć jest wolna, traktowana jako ciągły obszar o rozmiarze 2^n bloków. Gdy zachodzi potrzeba alokacji mniejszego obszaru, dokonywany jest rekurencyjny podział na dwie części wolnego obszaru aż do uzyskania najmniejszego fragmentu o rozmiarze 2^m (zawsze jest to potęga dwójki, co skutkuje dużą fragmentacją wewnętrzną). Dwa mniejsze obszary powstałe przy podziale są nazywane bliźniaczymi.

Z kolei przy dealokacji pamięci można bardzo łatwo stwierdzić, czy wolny jest też obszar bliźniaczy i scalić je w jeden większy; scalanie ma również charakter rekurencyjny.

Algorytm jest używany m.in. w jądrze systemu Linux do zarządzania stronami pamięci.

Zobacz też[edytuj | edytuj kod]

Bibliografia[edytuj | edytuj kod]

  • System bloków bliźniaczych. W: Donald Ervin Knuth: Sztuka programowania. T. 1: Algorytmy podstawowe. Warszawa: Wydawnictwa Naukowo-Techniczne, 2002, s. 460-462. ISBN 83-204-2540-9.