Sr-8-wyk-1.0-Slajd24
IVY: Problem lokalizacji stron
System IVY był pierwszą realizacją koncepcji rozproszonej pamięci współdzielonej, zrealizowaną całkowicie programowo, bez wsparcia ze strony sprzętu. Realizacja ta pokazała, że idea DSM dla wielu aplikacji, szczególnie obliczeniowych, może umożliwiać proste i efektywne zrównoleglenie przetwarzania na wielu komputerach bez konieczności uciekania się do kłopotliwej wymiany komunikatów.
Jednym z istotnych problemów związanych z zarządzaniem rozproszoną pamięcią jest kwestia lokalizacji stron. W systemie IVY zaimplementowano i przetestowano trzy rozwiązania. Pierwsze, najprostsze, polega na zastosowaniu scentralizowanego zarządzania, w którym dedykowany węzeł przechowuje całość informacji o aktualnym położeniu poszczególnych stron pamięci. Rozwiązanie to sprawdza się dobrze, gdy w systemie działa taki dedykowany system i gdy liczba serwerów nie jest zbyt duża. Przy większej liczbie węzłów centralny serwer w sposób naturalny staje się wąskim gardłem.
Drugie rozwiązanie problemu lokalizacji polega na rozłożeniu zadania odwzorowywania stron na wiele serwerów. Rozkład ten jest statyczny: na podstawie numeru strony oblicza się identyfikator węzła, który jest zarządcą tej strony (np. modulo liczba węzłów). Dzięki temu rozwiązaniu każdy serwer wie do kogo wysyłać komunikat z zapytaniem o lokalizację strony. Statystycznie rzecz biorąc każdy węzeł powinien być podobnie obciążony zadaniem odwzorowywania stron. Lokalizacja wymaga w tym przypadku tyle samo komunikatów co w przypadku podejścia scentralizowanego. Wadą tego rozwiązania jest pewna jego statyczność: dodanie nowego serwera jest trudne do zrealizowania, bo wymagałoby zmiany przypisań stron do serwerów.
Trzecie rozwiązanie to zastosowanie dynamicznej lokalizacji. Jest to podejście oparte na wskaźnikach naprowadzających, opisywanych na wykładzie dotyczącym nazewnictwa. Każdy węzeł posiada tablicę odwzorowującą lokalizację poszczególnych stron. Tablica ta nie koniecznie zawiera aktualne i prawdziwe informacje. Jest to informacja o prawdopodobnej lokalizacji stron. Lokalizacja strony polega na wysłaniu zapytania do serwera, który jest podejrzewany o jej przechowywanie. Jeżeli jest to prawdą, odesłany zostanie komunikat z potwierdzeniem. Jeżeli nie, zapytanie zostanie przesłane do węzła, który jest podejrzewany przez węzeł właśnie odpytywany, itd. Na rysunku węzły oznaczone są etykietami w kwadratach. Węzeł S1 wysyła zapytanie do S2, bo podejrzewa właśnie S2 o posiadanie poszukiwanej strony. S2 jednak jej nie posiada i przekazuje zapytanie do S3, bo podejrzewa właśnie S3. S3 faktycznie stronę posiada i odpowiada węzłowi S1.
Wskaźniki naprowadzające sprawdzają się dobrze w przypadku niedużej liczby węzłów. Ponieważ ścieżki wskazujące ulegają skróceniu przy każdym odpytywaniu (S1 aktualizuje swoje wskazanie z S2 na S3), średnia długość ścieżki, którą w praktyce przebiegają zapytania pozostaje krótka. Wynika to również z częstego odwoływania się do stron.
