Algorytm bliźniaków: Różnice pomiędzy wersjami
| [wersja nieprzejrzana] | [wersja nieprzejrzana] |
Usunięta treść Dodana treść
m drobne redakcyjne |
m dm. |
||
Linia 1:
'''Algorytm bliźniaków''' (ang. ''buddy algorithm'') - jest stosowaną w informatyce metodą [[alokacja pamięci|alokacji pamięci]], która charakteryzuje się dużą szybkością i łatwością implementacji oraz niską [[fragmentacja zewnętrzna|fragmentacją zewnętrzną]], kosztem jednak znaczącej [[fragmentacja wewnętrzna|fragmentacji wewnętrznej]].
W algorytmie zarządza się <math>2^n</math> blokami pamięci (wartość <math>n</math> zależy od implementacji). Początkowo cała pamięć jest wolna, traktowana jako ciągły obszar o rozmiarze <math>2^n</math> bloków. Gdy zachodzi potrzeba alokacji mniejszego obszaru, dokonywany jest [[rekurencja|rekurencyjny]] podział na dwie części wolnego obszaru aż do uzyskania najmniejszego fragmentu o rozmiarze <math>2^m</math> (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 [[stronicowanie pamięci|stronami]] pamięci.
==Zobacz też==
| |||