Wikipedia

Algorytm Cheneya

algorytm

Algorytm Cheneya, opisany po raz pierwszy w 1970 w artykule stowarzyszenia ACM przez C.J. Cheneya, jest metodą odśmiecania pamięci w systemach softwarowych. W tym schemacie sterta jest podzielona na dwie połowy, z których w danym momencie tylko jedna jest w użyciu. Odśmiecanie pamięci odbywa się poprzez kopiowanie żywych obiektów z pierwszej połowy do drugiej, która następnie staje się nową stertą. Cała stara sterta zostaje odrzucona w jednym kawałku.

Algorytm Cheneya odzyskuje elementy w następujący sposób:

  • Referencje do obiektów na stosie. Sprawdzane są referencje do obiektów na stosie. Zostaje podjęte jedno z dwóch następujących działań dla każdej referencji do obiektu, która wskazuje na obiekt na starej stercie:
    • Jeśli obiekt nie został jeszcze przeniesiony do nowej sterty, jest to realizowane poprzez stworzenie identycznej kopii na nowej stercie, a następnie zastąpienie wersji ze starej sterty przekierowującym wskaźnikiem do kopii. Następnie aktualizowana jest referencja obiektu aby odnosiła się do nowej wersji w nowej stercie.
    • Jeśli obiekt został już przeniesiony do nowej sterty, po prostu aktualizuje się odwołanie według przekierowującego wskaźnika ze starej sterty.
  • Obiekty w nowej stercie. Garbage collector sprawdza wszystkie odniesienia do obiektów w obiektach, które już zostały przeniesione do nowej sterty i wykonuje na nich jedno z dwóch powyższych działań.

Gdy wszystkie odniesienia z nowej sterty zostały sprawdzone i zaktualizowane, odśmiecanie pamięci jest ukończone.

Algorytm nie potrzebuje stosu i tylko dwa wskaźniki: wskaźnik do początku wolnego miejsca i wskaźnik następnego obiektu potrzebującego sprawdzenia, oba w nowej stercie. Z tego powodu jest on czasem nazywany „kolektorem o dwóch palcach” – wymaga jedynie „dwóch palców” wskazujących na nową stertę aby śledzić swój stan. Dane między dwoma palcami reprezentują pozostałą do zrobienia pracę.

Kiedy jest już znalezione odniesienie do obiektu w nowej stercie (więc mające przekierowujący wskaźnik w starej stercie), odniesienie może być zaktualizowane szybko i prosto przez aktualizację wskaźnika według wskaźnika przekierowującego.

Kod edytuj 

type
  PBlock = ^TBlock;
  TBlock = array[0..1] of PBlock;
  TSpace = array[0..1,0..5] of TBlock;

var
  roots: array[0..1] of TBlock;
  Spaces: TSpace;

procedure ProcOne(var p:PBlock);
begin
  if p=nil then
  begin
    writeln('jest nil');
    exit;
  end;
  if PChar(p^[0])<PChar(@Spaces[1]) then
  begin
    writeln('nie przeniesione');
    Spaces[1,newPtr]:=p^;
    p^[0]:=@Spaces[1,newPtr];
    p:=@Spaces[1,newPtr];
    inc(newPtr);
  end else
  begin
    writeln('przeniesione');
    p:=p^[0];
  end;
end;

procedure Process;
var
  i,j: integer;
begin
  newPtr:=0;
  for i:=0 to High(roots) do
  for j:=0 to 1 do
    ProcOne(roots[i,j]);
  procPtr:=0;
  while procPtr<newPtr do
  begin
    for j:=0 to 1 do
      ProcOne(Spaces[1,procPtr,j]);
    inc(procPtr);
  end;
end;

Semispace edytuj

Cheney oparł swoją pracę na algorytmie odśmiecania pamięci semispace, który został opublikowany rok wcześniej przez R.R Fenichela i J.C. Yochelsona.

Równoważność do trójkolorowej abstrakcji edytuj

Pierwszym elementem szarego zbioru jest sam stos. Obiekty referowane na stosie są kopiowane do nowej sterty, która zawiera elementy zbiorów czarnych i szarych.

Algorytm przenosi białe obiekty (odpowiedniki obiektów w starej stercie bez przekierowujących wskaźników) do szarego zbioru, kopiując je do nowej sterty. Obiekty, które są między wskaźnikiem skanowania i wskaźnika wolnego miejsca należą do szarego zbioru i nadal będą skanowane. Obiekty poniżej wskaźnika skanowania należą do czarnego zbioru. Obiekty są przenoszone do czarnego zbioru, po prostu poprzez przesuwanie wskaźnika skanowania nad nimi.

Kiedy wskaźnik skanowania osiągnie pozycję wskaźnika wolnego miejsca, szary zbiór stanie się pusty i algorytm się skończy.

Linki zewnętrzne edytuj

Źródło: „https://pl.wikipedia.org/w/index.php?title=Algorytm_Cheneya&oldid=71504705”