Algorytm bliźniaków: Różnice pomiędzy wersjami
| [wersja przejrzana] | [wersja przejrzana] |
Usunięta treść Dodana treść
drobne redakcyjne |
25 interwiki |
||
Linia 1:
'''Algorytm bliźniaków''' ({{ang.|buddy algorithm}}) – metoda [[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.
| |||