Sr-5-wyk-1.0-Slajd33
Identyfikowanie jednostek nieosiągalnych
W systemie rozproszonym może istnieć grupa obiektów, które wzajemnie na siebie wskazują, ale nie są osiągalne z zewnątrz. Takie obiekty również powinny zostać usunięte, ale metody przedstawione dotąd nie gwarantują ich usunięcia. Trzeba zastosować w tym przypadku odśmiecanie ze śledzeniem (ang. tracing-based garbage collection ). Metody te są kosztowne i słabo skalowalne ponieważ wymagają śledzenia wszystkich jednostek w systemie.
W systemach scentralizowanych stosuje się kolektory typu znakuj i zamiataj (ang. mark-and-sweep ). Kolektor działa w dwóch fazach. W pierwszej fazie wychodząc od obiektów ze zbioru głównego przechodzi rekurencyjnie wszystkie odniesienia znacząc obiekty, które odwiedza na czarno. W drugiej fazie obiekty, które nie zostały oznaczone są usuwane. W podejściu trójkolorowym kolor szary wykorzystuje się do zaznaczenia obiektów, które zostały już osiągnięte, ale dla których nie sprawdzono jeszcze wszystkich odniesień. Odwiedzenie wszystkich odniesień obiektu powoduje zmianę koloru na czarny.
Rozproszone znakowanie i zamiatanie odbywa się w sposób zrównoleglony. Odwiedzone obiekty po przetworzeniu lokalnym kolektorem stają się szare do czasu sprawdzenia wszystkich odwołań do zdalnych obiektów. Sprawdzanie odwołań do zdalnych obiektów powoduje wysłanie komunikatu do zdalnego obiektu informującego o osiągalności. Po przetworzeniu wszystkich odniesień w obiekcie zdalnym odsyłane jest potwierdzenie. Przetworzenie wszystkich odniesień do obiektów zdalnych powoduje zmianę koloru na czarny.
Podstawową wadą znakowania i zamiatania jest konieczność całkowitego zablokowania przetwarzania na czas odśmiecania. W systemie rozproszonym oznacza to konieczność synchronizacji wszystkich rozproszonych procesów, co może być nieakceptowalne dla użytkowników. Rozwiązaniem może być zastosowanie odśmiecaczy przyrostowych. Niestety nie są one dobrze skalowalne. Działają one współbieżnie z aplikacjami, modyfikującymi graf osiągalności, co powoduje częste znakowanie obiektów kolorem szarym i komunikację między węzłami, która jednak nie prowadzi do efektywnego wykrywania nieosiągalnych obiektów.
