Sr-5-wyk-1.0-Slajd31

From Studia Informatyczne

Zaawansowane zliczanie odniesień

Zaawansowane zliczanie odniesień


Problemu wyścigu (ang. race condition ) występującego w zliczaniu odniesień można uniknąć poprzez wyeliminowanie komunikatów zwiększających licznik odwołań. Ważone zliczanie odniesień (ang. weighted reference counting ) polega na ustaleniu początkowej liczby całkowitej dla każdego obiektu i dzielenie jej przy każdym tworzeniu nowego odniesienia. Przykładowo: jeżeli przypisano obiektowi wagę 128, to po skopiowaniu odniesienia oryginał i kopia będą miały wagę równą 64. Jeżeli odniesienie-kopia utworzy kolejną kopię to będą one miały wagi równe 32. Usuwanie odniesień powoduje przesłanie informacji o znikającej wadze. Jeżeli waga osiągnie wartość 0, oznacza to, że wszystkie odniesienia zostały usunięte i obiekt może być też usunięty.

Podstawową wadą tego podejścia jest ograniczona liczba kopii odniesień, które można utworzyć. Jeżeli waga osiąga wartość 1, to dalsze dzielenie nie będzie mogło być przeprowadzone. Rozwiązaniem jest wtedy wprowadzenie dodatkowego sztucznego odniesienia (wskaźnika naprowadzającego) do nowego obiektu-pośrednika, który będzie miał ustawioną wagę znów na dużą wartość. Usunięcie wszystkich odniesień do tego obiektu-pośrednika będzie powodować dopiero wysłanie komunikatu o usunięciu odniesienia do głównego obiektu. Podstawową wadą tej metody jest wydłużenie czasu dostępu przy długich łańcuchach wskaźników. Im dłuższy łańcuch tym większe jest również prawdopodobieństwo awarii.

Innym rozwiązaniem opartym na pośredniości jest pokoleniowe zliczanie odniesień (ang. generation reference counting ). Każde odniesienie jest opatrzone podwójnym licznikiem, gdzie pierwsza wartość oznacza liczbę kopii utworzonych na podstawie tego odniesienia, a druga oznacza generację odniesienia. Jeżeli na podstawie odniesienia P tworzona jest kopia Q, to licznik kopii w odniesieniu P jest zwiększany, a numer generacji kopii Q jest inicjowany na wartość o jeden większą od licznika generacji w P. Usuwając odniesienie wysyłane są obie wartości liczbowe. Serwer obiektu przechowuje tablicę G, w której pozycja i-ta oznacza liczbę kopii i-tej generacji. Usuwając odniesienie z parą (i , k ) zmniejszana jest o 1 wartość na pozycji G[i ] i jednocześnie zwiększana o k na pozycji G[i+1 ]. Obiekt można usunąć gdy cała tablica G zostanie wyzerowana. Zaletą tego rozwiązania jest brak konieczności kontaktowania się z serwerem obiektu podczas tworzenia nowego odniesienia.

Wszystkie przedstawione tu rozwiązania zakładają niezawodną komunikację.


<< Poprzedni slajd | Spis treści | Następny slajd >>