Algorytm bliźniaków: Różnice pomiędzy wersjami

[wersja nieprzejrzana][wersja nieprzejrzana]
Usunięta treść Dodana treść
m wstępna wersja
 
m drobne redakcyjne
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 dużejznaczą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>. Dwa mniejsze obszary powstałe przy podziale są nazywane ''bliźniaczymi''.
 
Zawsze rezerwuje się <math>2^k</math> bloków, co skutkuje fragmentacją wewnętrzną.
Początkowo cała pamięć jest wolna; 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^k</math>.
 
Z kolei przy dealokacji obszaru pamięci można bardzo łatwo stwierdzić, czy wolny jest też "bliźniaczy" obszar (powstały''bliźniaczy'' wcześnieji przyscalić podzialeje podczasw alokacji)jeden i scalić jewiększy; scalanie ma również charakter rekurencyjny.
 
==Zobacz też==