Jarosław Krupa

Radosław Kozłowski

4FDS - systemy i sieci komputerowe

POLITECHNIKA RZESZOWSKA

 

Systemy wieloprocesorowe z pamięcią dzieloną

 

Streszczenie

W opracowaniu tym znaleźć można informacje z szerokiej dziedziny dotyczącej systemów rozproszonych z pamięcią dzieloną. Przestudiowane zostaną różne kategorie wieloprocesorów. Z opracowania tego dowiedzieć można się także, czym w istocie jest pamięć dzielona i jak naprawdę działają wieloprocesory z pamięcią dzieloną. Przeanalizowana zostaje semantyka dzielenia oraz przestudiowane zostają różne modele spójności stosowane w systemach z pamięcią dzieloną. Opracowanie to zawiera także uproszczone informacje na temat projektowania systemów rozproszonej pamięci dzielonej. Ponieważ rozproszona pamięć dzielona może być ściśle powiązana z architekturą komputera, systemami operacyjnymi, systemami wsparcia wykonywania programów, a nawet z językami programowania, wszystkie te zagadnienia odegrają również znaczącą rolę w niniejszym opracowaniu. W ostatnim rozdziale przedstawione zostaną tendencje rozwojowe oraz kierunki rozwoju systemów wieloprocesorowych z pamięcią dzieloną.

 

Wprowadzenie

Systemy komputerowe przeżywają rewolucję. Od 1945 roku, kiedy to rozpoczęła się era nowoczesnych komputerów, aż do roku 1985 komputery były wielkie i drogie. Nawet minikomputery z reguły kosztowały dziesiątki tysięcy dolarów. Wskutek tego większość instytucji dysponowała skromną liczbą komputerów, które - z braku sposobów ich łączenia - działały niezależnie jeden od drugiego.

Od połowy lat osiemdziesiątych sytuacja ta zaczęła się zmieniać dzięki dwu osiągnięciom w technologii. Pierwszym było opracowanie mikroprocesorów o dużej mocy obliczeniowej. Z początku były to maszyny ośmiobitowe, lecz wkrótce upowszechniły się procesory szesnastobitowe, trzydziestodwubitowe, a nawet sześćdziesięcioczterobitowe. Wiele z nich miało moc obliczeniową porównywalną z mocą całkiem porządnego komputera głównego (tj. wielkiego) - a przy tym za ułamek ceny. Postęp w technologii komputerowej, jaki dokonał się w minionym półwieczu, jest oszałamiający i nie ma sobie równego w innych dziedzinach przemysłu. Od maszyny, która kosztowała 10 milionów dolarów i wykonywała jedną instrukcję na sekundę, technologia doszła do maszyn kosztujących 1000 dolarów i wykonujących 10 milionów instrukcji na sekundę, osiągając ponad tysiąc razy lepszy współczynnik cena/wydajność.

Drugim osiągnięciem było wynalezienie szybkich sieci komputerowych. Lokalne sieci komputerowe, czyli sieci LAN (ang. Local Area Network), umożliwiają łączenie w obrębie budynków nawet setek komputerów w taki sposób, że niewielkie ilości informacji mogą być przesyłane między maszynami w czasie tysięcznych części sekundy. Większe ilości danych mogą przemieszczać się między maszynami z szybkościami od 10 do 100 milionów bitów na sekundę, a niekiedy nawet szybciej . Rozległe sieci komputerowe, czyli sieci WAN (ang. Wide Area Networks), pozwalają łączyć miliony maszyn na całej kuli ziemskiej i przesyłać informacje z szybkościami od 64 kb/s do gigabitów na sekundę.

Dzięki tym technologiom wzajemne połączenie ze sobą - za pomocą szybkiej sieci - systemów komputerowych złożonych z wielu jednostek centralnych (CPU - ang. Central Processor Unit) jest obecnie nie tylko wykonalne, ale i łatwe. Nazywa się je zwykle systemami rozproszonymi (ang. distributed systems) w przeciwieństwie do poprzednich systemów scentralizowanych (ang. centralized systems), czyli jednoprocesorowych (ang. single-processor systems), złożonych z jednego procesora centralnego, jego pamięci, urządzeń zewnętrznych i pewnej liczby terminali. Systemy rozproszone wymagają jednak zupełnie odmiennego oprogramowania niż systemy scentralizowane. Co więcej - niezbędne dla nich systemy operacyjne zaczynają dopiero powstawać. Uczyniono już kilka kroków, lecz droga do przebycia jest jeszcze długa.

Chociaż wszystkie systemy rozproszone składają się z wielu jednostek centralnych, sprzęt ten można zorganizować na kilka sposobów, zwłaszcza pod względem wzajemnych połączeń i rodzajów komunikacji. W ciągu wielu lat proponowano rozmaite schematy klasyfikacji wieloprocesorowych systemów komputerowych, lecz w rzeczywistości żaden z nich nie przyjął się na dobre i nie wszedł do powszechnego użycia. Istotne w tym przypadku są dwie cechy: liczba strumieni instrukcji oraz liczba strumieni danych. Komputer z jednym strumieniem instrukcji i jednym strumieniem danych nosi nazwę SISD. Wszystkie tradycyjne komputery jednoprocesorowe (tj. mające tylko jedną jednostkę centralną) mieszczą się w tej kategorii - od komputerów osobistych aż po wielkie komputery główne.

Następną kategorią jest SIMD - jeden strumień instrukcji i zwielokrotniony strumień danych. Ten typ odnosi się do procesorów macierzowych z jedną jednostką wykonywania instrukcji, która pobiera instrukcję, a następnie zarządza wieloma jednostkami danych w sposób równoległy - każda z nich operuje na własnych danych. Maszyny tego rodzaju są użyteczne do obliczeń, w których powtarza się te same operacje na wielu zbiorach danych, na przykład przy dodawaniu wszystkich składowych 64 niezależnych wektorów. Niektóre superkomputery zalicza się do typu SIMD.

Kolejna kategoria zwie się MISD - zwielokrotniony strumień instrukcji i jeden strumień danych. Modelowi temu nie odpowiada żaden ze znanych komputerów. Ostatnią z kategorii stanowi MIMD, która w istocie oznacza grupę niezależnych komputerów zaopatrzonych we własne liczniki rozkazów, programy i dane. Wszystkie systemy rozproszone należą do kategorii MIMD, tym samym ta klasyfikacja nie jest nazbyt użyteczna do naszych celów.

Wszystkie komputery MIMD dzielą się na dwie grupy (RYS.1.): komputery wyposażone we wspólną pamięć, zazwyczaj nazywane wieloprocesorami (ang. multiprocessors) i komputery, które jej nie mają, czasami nazywane multikomputerami (ang. multicomputers). Zasadnicza różnica przedstawia się następująco: w wieloprocesorze istnieje jedna wirtualna przestrzeń adresowa dzielona przez wszystkie procesory centralne. Jeśli którakolwiek jednostka centralna zapisuje na przykład wartość 44 pod adresem 1000, to każda inna jednostka centralna, czytająca następnie spod swojego adresu 1000, otrzyma wartość 44. Wszystkie maszyny dzielą tę samą pamięć. Na odwrót, w multikomputerach każda z maszyn ma własną, prywatną pamięć. Jeśli jakaś jednostka centralna zapisuje wartość 44 pod adresem 1000, podczas gdy inna jednostka centralna czyta spod adresu 1000, to ta ostatnia dostanie wartość pamiętaną tam poprzednio. Zapisywanie wartości 44 zupełnie nie wpływa na zawartość jej własnej pamięci. Typowym przykładem multikomputera jest zbiór komputerów osobistych połączonych za pomocą sieci.

Rys. 1. Podział równoległych i rozproszonych systemów komputerowych.

Każdą z tych kategorii komputerów można dalej podzielić na podstawie architektury sieci wzajemnych połączeń. Kategorie te opisane zostały jako szynowe (ang. bus) i przełączane (ang. switched). Przez kategorię szynową rozumiemy istnienie pojedynczej sieci, tablicy połączeń, szyny, kabla lub innego nośnika łączącego wszystkie maszyny. Schematu takiego używa telewizja kablowa - firma okablowująca układa przewód wzdłuż ulicy, a wszyscy subskrybenci mają doprowadzenia biegnące do niego od ich odbiorników telewizyjnych. Systemy przełączane nie mają jednego szkieletu jak telewizja kablowa. Zamiast niego od maszyny do maszyny biegną pojedyncze przewody; stosuje się przy tym wiele różnych schematów okablowania. Komunikaty biegną po drutach, a przełączenia jawnie określane przy każdym kroku wytyczają ich trasę wzdłuż jednego z wyprowadzeń. Na tej zasadzie jest zorganizowany system światowej telefonii.

Odmiennym wymiarem tej taksonomii jest to, że w niektórych systemach maszyny są ściśle powiązane (ang. tightly coupled), a w innych są luźno powiązane (ang. loosely coupled). W ściśle powiązanym systemie obserwowane opóźnienie komunikatu wysłanego od jednego komputera do drugiego jest małe, a szybkość przesyłania danych jest duża, tzn. liczba bitów przesyłanych w ciągu sekundy jest wielka. W systemie luźno powiązanym zachodzi odwrotna sytuacja: międzymaszynowe opóźnienia komunikatów są duże, a szybkość przesyłania danych jest mała. Na przykład dwa jednoukładowe procesory centralne znajdujące się na tej samej płytce drukowanej i połączone wytrawionymi na niej ścieżkami są ściśle powiązane, podczas gdy dwa komputery połączone za pomocą modemu o szybkości 2400 bitów na sekundę poprzez system telefoniczny są luźno powiązane. Systemy ściśle powiązane są zazwyczaj używane jako systemy równoległe (do rozwiązywania pojedynczych problemów), systemy luźno powiązane stosuje się głównie w systemach rozproszonych (do prac nad wieloma osobnymi problemami), aczkolwiek nie zawsze musi to być prawdą. Słynnym kontrprzykładem jest projekt, w którym setki komputerów rozmieszczonych po całym świecie pracowały wspólnie nad rozłożeniem na czynniki olbrzymiej liczby (około stucyfrowej). Każdy komputer miał przydzielony inny zakres podzielników do wypróbowania i pracował nad zadaniem w swoim wolnym czasie, przesyłając gotowe wyniki za pomocą poczty elektronicznej. Ogólnie rzecz biorąc, wieloprocesory wykazują więcej ścisłych powiązań aniżeli multikomputery, ponieważ mogą wymieniać dane z szybkością działania pamięci, wszakże niektóre multikomputery zbudowane na światłowodach mogą też pracować z szybkościami działania pamięci.

 

Czym jest pamięć dzielona

W początkowym okresie wprowadzania obliczeń rozproszonych, było niejawnie zakładane, że programy na maszynach, które nie mają żadnej fizycznej pamięci dzielonej (tj. multikomputerach), w sposób oczywisty przebiegają w różnych przestrzeniach adresowych. Przy takim nastawieniu komunikację pojmowano w kategoriach przekazywania komunikatów między rozłącznymi przestrzeniami adresowymi. W roku 1986 zaproponowane zostało inne rozwiązanie, obecnie znane pod nazwą rozproszonej pamięci dzielonej (ang. distributed shared memory - DSM). Zaproponowane zostało użycie zbioru stacji roboczych połączonych za pomocą sieci lokalnej i mających jedną, stronicowaną, wirtualną przestrzeń adresową. W najprostszym wariancie każda strona występuje w dokładnie jednej maszynie. Odwołania do stron lokalnych są wykonywane sprzętowo z pełną szybkości pamięci. Próba odwołania do strony na innej maszynie powoduje zasygnalizowanie braku strony przez sprzęt i przejście do systemu operacyjnego. System operacyjny wysyła wówczas komunikat do zdalnej maszyny, która znajduje potrzebną stronę i wysyła ją zamawiającemu procesowi. Nieudana instrukcja zostaje wtedy ponowiona i może być wykonana do końca.

Projekt ten jest w istocie podobny do tradycyjnych systemów pamięci wirtualnej: gdy proces odwołuje się do strony nieobecnej, następuje przejście do systemu operacyjnego, który sprowadza stronę i umieszcza w pamięci. Różnica polega tu na tym, że system operacyjny zamiast pobierać stronę z dysku, pobiera ją od innego procesora za pośrednictwem sieci. Jednak dla procesów użytkowych system ten wygląda jak tradycyjny wieloprocesor z wieloma procesami, które mają swobodę czytania i zapisywania pamięci dzielonej. Cała komunikacja i synchronizacja może odbywać się przez pamięć, przy czym komunikacja jest niewidoczna dla procesów użytkowych. Opracowany został w rezultacie system łatwy zarówno do programowania (logicznie dzielona pamięć), jak i do zbudowania (brak fizycznie dzielonej pamięci). Chociaż ten system jest rzeczywiście łatwy do programowania i budowy, to jednak w wielu zastosowaniach marnie działa wskutek miotania się stron tam i z powrotem po sieci. Zachowanie to jest podobne do szamotania w jednoprocesorowych systemach z pamięcią wirtualną. W ostatnich latach prowadzono intensywne badania nad zwiększeniem wydajności takich systemów o rozproszonej pamięci dzielonej. Odkryto przy tym wiele nowych technik. Wszystkie one mają na celu zminimalizowanie ruchu w sieci i zredukowanie zwłoki między chwilą wykonania zamówienia pamięci a chwilą, w której zostaje ono spełnione.

Jedno z podejść polega na zrezygnowaniu z dzielenia całej przestrzeni adresowej na rzecz dzielenia wybranej jej części, a mianowicie tych zmiennych i struktur danych, które muszą być używane przez więcej niż jeden proces. W tym modelu zamiast myśleć o każdej maszynie, jako o mającej bezpośredni dostęp do zwykłej pamięci, rozważa się użycie przez nią zbioru dzielonych zmiennych, co daje wyższy poziom abstrakcji. Strategia ta nie tylko znacznie redukuje ilość danych do dzielenia, lecz również w większości przypadków udostępnia znaczne ilości informacji o dzielonych danych, takich jak ich typy, co może pomagać w optymalizowaniu implementacji. Jedną z możliwych optymalizacji jest zwielokrotnienie zmiennych dzielonych na wielu maszynach. Stosując dzielenie zwielokrotnionych zmiennych zamiast całych stron, problem symulacji multiprocesora zredukowano do zagadnienia utrzymywania spójności wielu kopii zbioru danych strukturalnych typów. Czytanie może się odbywać lokalnie, bez ruchu w sieci, a do zapisywania można wykorzystać protokół aktualizacji wielu kopii. Protokoły takie są w powszechnym użyciu w systemach rozproszonych baz danych, więc pomysły z tamtego obszaru mogą znaleźć tu zastosowanie.

Dalszym krokiem w kierunku strukturalizacji przestrzeni adresowej jest dzielenie obudowanych typów danych, nazywanych często obiektami (ang. objects). Różnią się one od zmiennych dzielonych tym, że każdy obiekt ma nie tylko dane, lecz również działające na nich procedury zwane metodami (ang. methods). Programy mogą manipulować danymi obiektu tylko za pomocą jego metod. Nie jest dozwolony bezpośredni dostęp do danych. Taki sposób ograniczania dostępu umożliwia nowe optymalizacje. Wykonywanie wszystkiego środkami programowymi ma inne zalety i wady niż wykonywanie tego za pomocą sprzętu stronicującego. Na ogół bardziej ogranicza to programistę, lecz może też polepszać działanie. Wiele z tych ograniczeń (np. działania na obiektach) uważa się za dobre obyczaje inżynierii programowania, pożądane jako wewnętrznie poprawne.

W pierwszej kolejności należy przeanalizować kilka rodzajów wieloprocesorów z pamięcią dzieloną, rozpoczynając od najprostszych, działających na pojedynczej szynie, a kończąc na zaawansowanych, o bardzo pomysłowych rozwiązaniach pamięci podręcznych. Poznanie tych maszyn jest ważne dla zrozumienia rozproszonej pamięci dzielonej (DSM), ponieważ większość prac nad pamięcią DSM było inspirowanych postępami w architekturze wieloprocesorów. Co więcej, wiele z tych algorytmów jest tak do siebie podobnych, że czasami trudno jest powiedzieć, czy zaawansowana maszyna jest wieloprocesorem, czy multikomputerem używającym sprzętowej realizacji rozproszonej pamięci dzielonej.

2.1. Pamięć układowa

Chociaż większość komputerów ma pamięć zewnętrzna, istnieją również samowystarczalne układy zawierające jednostkę centralną wraz z cały pamięcią. Produkuje się miliony takich układów i montuje się je w samochodach, w przyrządach, a nawet w zabawkach. W projekcie tego rodzaju część układu stanowiąca jednostkę centralną (CPU) jest bezpośrednio połączona liniami adresów i liniami danych z częścią stanowiącą pamięć (RYS.2a.).

Rys. 2. Pamięć układowa: a) komputer jednoukładowy, b) hipotetyczny wieloprocesor z pamięcią dzieloną.

Możliwe jest do wyobrażenia proste rozwinięcie tego układu z wieloma jednostkami centralnymi bezpośrednio dzielącymi tę samą pamięć (RYS.2b.). Choć zbudowanie takiego układu jest możliwe, byłby on skomplikowany, drogi i bardzo nietypowy. Skonstruowanie w ten sposób jednoukładowego wieloprocesora zawierającego np. 100 jednostek centralnych mających dostęp do tej samej pamięci byłoby z kolei niemożliwe z przyczyn inżynierskich. Konieczne było więc znalezienie innego podejścia do dzielenia pamięci.

2.2. Wieloprocesory szynowe

W przypadku pamięci układowej połączenie między jednostką centralną a pamięcią jest wiązką równoległych przewodów, z których część służy do przenoszenia adresu, pod którym jednostka centralna chce czytać lub pisać, inne są wykorzystywane do wysyłania lub odbierania danych, a reszta - do nadzorowania przesłań. Tego rodzaju zbiór przewodów zwie się szyną (ang. bus). Tutaj szyna jest wewnątrz układu, lecz w wielu systemach występują szyny zewnętrzne, które służą do łączenia płyt obwodów drukowanych zawierających jednostki centralne, pamięci oraz kontrolery wejścia-wyjścia. W komputerze stołowym szyna jest zazwyczaj wytrawiona na płycie głównej (płycie macierzystej), na której jest zamocowana jednostka centralna i część pamięci, i do której są przyłączone karty wejścia-wyjścia. W minikomputerach szyna stanowi czasami płaski kabel biegnący między procesorami, pamięciami i kontrolerami wejścia-wyjścia. Prostą, a jednocześnie praktyczną metodą budowy wieloprocesora jest zastosowanie w nim szyny, do której przyłączono więcej niż jedną jednostkę centralną (RYS.3a.). Gdy którakolwiek z jednostek centralnych chce przeczytać słowo z pamięci, umieszcza adres słowa w szynie i ustawia (włączając sygnał) linię sterującą na czytanie. Pamięć po pobraniu wymaganego słowa umieszcza je w szynie i ustawia inną linię sterującą, komunikując, że jest gotowa. Jednostka centralna czyta wówczas słowo. Zapisywanie przebiega analogicznie.

Rys. 3. Wieloprocesor szynowy: a) wyłącznie z pamięcią dzieloną, b) z pamięcią podręczną.

Aby uchronić dwa procesory (lub więcej) przed próbą dostępu do pamięci w tym samym czasie, jest potrzebny pewien rodzaj arbitrażu szyny. W użyciu są różne schematy. Na przykład, aby uzyskać dostęp do szyny, procesor musi ją najpierw zamówić przez ustawienie specjalnej linii zamówień. Dopiero po otrzymaniu pozwolenia będzie mu wolno posłużyć się szyn. Udzielanie zezwoleń może być wykonywane centralnie za pomocą szynowego urządzenia arbitrażowego lub w sposób zdecentralizowany, w którym pierwszy procesor zamawiający jednostkę centralną wzdłuż szyny zwycięża w każdym sporze. Wadą pojedynczej szyny jest to, że już w przypadku trzech lub czterech jednostek centralnych może ona ulec przeładowaniu. Typowy zabieg podejmowany w celu zredukowania obciążenia szyny polega na wyposażeniu każdej jednostki centralnej w podglądającą pamięć podręczną (ang. snooping cache lub snoopy cache), nazywaną tak dlatego, że "podpatruje" szynę (RYS.3b.). Istnieje wiele protokołów spójności pamięci podręcznej (ang. cache consistency protocols), tzn. reguły gwarantowania, że różne pamięci podręczne nie będą zawierać różnych wartości dla tej samej komórki pamięci. Jeden szczególnie prosty i popularny protokół nosi nazwy protokołu przepisywania (ang. write through) (TAB.1.). Gdy jednostka centralna czyta po raz pierwszy słowo z pamięci, wówczas słowo zostaje pobrane za pośrednictwem szyny i przechowane w tej pamięci podręcznej. Jeśli dane słowo będzie potrzebne znowu później, to jednostka centralna będzie mogła pobrać je ze swojej pamięci podręcznej bez składania zamówienia do pamięci operacyjnej, co zmniejsza ruch w szynie. W prostych systemach w pamięci podręcznej przechowuje się tylko zamawiane słowo, lecz w większości systemów przy pierwszym dostępie przesyła się i przechowuje do ewentualnego przyszłego użytku blok wielkości - 16 lub 32 słów.

Zdarzenie	Działanie podejmowane przez pamięć podręczną w odpowiedzi na zapotrzebowanie ze strony własnej jednostki centralnej	Działanie podejmowane przez pamięć podręczną w odpowiedzi na zapotrzebowanie za strony odległej jednostki centralnej
Chybione czytanie	Pobranie danych z pamięci operacyjnej i przechowanie ich w pamięci podręcznej	(bez potrzeby działania)
Trafione czytanie	Pobranie danych z lokalnej pamięci podręcznej	(bez potrzeby działania)
Chybione pisanie	Zaktualizowanie danych w pamięci operacyjnej i przechowanie ich w pamięci podręcznej	(bez potrzeby działania)
Trafione pisanie	Zaktualizowanie pamięci operacyjnej oraz pamięci podręcznej	Unieważnienie wpisu w pamięci podręcznej

Tab. 1. Protokół przepisywania służący do utrzymania spójności pamięci podręcznej.

Każda jednostka centralna przechowuje słowa w pamięci podręcznej niezależnie od innych. Może się więc zdarzyć, że jakieś słowo będzie przechowywane w pamięciach podręcznych dwu lub więcej procesorów w tym samym czasie. Rozważmy tedy, co się stanie w przypadku zapisywania. Jeśli żaden z procesorów nie ma w swojej pamięci podręcznej zapisywanego słowa, to uaktualnia się po prostu pamięć operacyjną, jakby w ogóle nie używano pamięci podręcznych. Operacja ta wymaga zwykłego cyklu szyny. Jeśli procesor wykonujący zapis ma jedyną kopię słowa, to szyna zostaje użyta do aktualizacji zarówno jego pamięci podręcznej, jak i pamięci operacyjnej. Kłopot powstaje wtedy, gdy jednostka centralna chce zapisać słowo przechowywane w pamięciach podręcznych dwu lub więcej jednostek centralnych. Jeśli słowo przebywa aktualnie w pamięci podręcznej jednostki wykonującej zapis, to następuje uaktualnienie wpisu w pamięci podręcznej. Niezależnie od tego czy słowo przebywa w pamięci podręcznej, czy nie, zapisuje się je również w szynie w celu aktualizowania pamięci operacyjnej. Operacja zapisywania jest widoczna dla wszystkich pozostałych pamięci podręcznych (ponieważ podglądają one szynę), które sprawdzają, czy występuje u nich modyfikowane słowo. Jeśli tak, to unieważniają zawierające je pozycje pamięci podręcznej, tak że po zakończeniu zapisywania pamięć operacyjna ma wartość aktualną i tylko jedna maszyna przechowuje nowo zapisane słowo w swojej pamięci podręcznej.

Zamiast unieważniać wpisy w innych pamięciach podręcznych można je wszystkie aktualizować. W większości przypadków aktualizacja jest wolniejsza od unieważniania. Do unieważnienia wystarczy podać unieważniany adres, natomiast aktualizacja wymaga dostarczenia również wartości nowego wpisu w pamięci podręcznej. Jeżeli te dwie jednostki muszą wystąpić w szynie jedna po drugiej, to będą potrzebne dodatkowe cykle. Nawet wówczas, gdy adres i dane można umieścić w szynie jednocześnie, do aktualizacji bloku pamięci podręcznej większego od jednego słowa potrzebnych jest wiele cykli szyny. Kwestia wyboru między unieważnianiem a aktualizowaniem pojawia się we wszystkich protokołach pamięci podręcznych, a także w systemach DSM (rozproszonej pamięci dzielonej). W przypadku protokołu przepisującego (TAB.1.) pamięć podręczna P (podglądająca) musi reagować tylko wtedy, gdy dostrzega, że inna jednostka centralna zapisała słowo, które P przechowuje u siebie (trafienie przy zapisie z punktu widzenia pamięci podręcznej P). Działanie pamięci podręcznej P polega wtedy na usunięciu danego słowa ze swojej kolekcji.

Protokół przepisywania jest łatwy do zrozumienia i zaimplementowania, lecz ma poważną wadę - do wszystkich zapisów trzeba używać szyny. Oczywiście, do pewnego stopnia zmniejsza on ruch w szynie, lecz mimo to liczba jednostek centralnych możliwych do podłączenia do jednej szyny jest ciągle za mała, by pozwolić na budowanie za pomocą tej metody wielkich wieloprocesorów. Na szczęście w wielu rzeczywistych programach, gdy jednostka centralna zapisze jakieś słowo, to prawdopodobnie będzie go znów potrzebować, a jednocześnie szansa na to, że będzie ono potrzebne innej jednostce centralnej jest niewielka. Ta sytuacja skłania do znalezienia sposobu nadawania jednostce centralnej czasowego "prawa własności" używanego słowa w celu uniknięcia konieczności uaktualniania pamięci przy kolejnych zapisach do chwili, gdy inna jednostka centralna przejawi nim zainteresowanie. Istnieją takie protokoły pamięci podręcznej, jak np. protokół zwany jednokrotnym zapisem (ang. write once). Protokół ten zaprojektowano jednak do pracy z już istniejącą szyną, został więc on bardziej skomplikowany, aniżeli to konieczne. Uproszczona wersja, typowa dla wszystkich protokołów uwłaszczania działa na blokach pamięci podręcznej, z których każdy może być w jednym z następujących trzech stanów:

unieważniony - blok pamięci podręcznej nie zawiera aktualnych danych,

czysty - zawartość bloku pamięci jest aktualna, blok może być w innych pamięciach podręcznych,

zabrudzony - zawartość bloku pamięci jest niepoprawna, żadne inne pamięci podręczne nie utrzymują tego bloku.

Zasadniczym pomysłem jest pozwolenie, by słowo czytane przez wiele jednostek centralnych mogło przebywać w ich pamięciach podręcznych. Słowo często zapisywane przez tylko jedną maszynę przechowuje się w jej pamięci podręcznej i nie posyła go z powrotem do pamięci operacyjnej przy każdym zapisie, aby zmniejszyć ruch w szynie. Wiele niedużych wieloprocesorów posługuje się protokołem spójności pamięci podręcznej podobnym do opisanego, zawierającym często niewielkie modyfikacje. Ma on trzy ważne cechy:

spójność osiąga się za pomocą podglądania szyny przez wszystkie pamięci podręczne,

protokół jest wbudowany w jednostkę zarządzającą pamięcią,

cały algorytm jest wykonany w ramach cyklu pamięci.

Niektórych z tych właściwości nie posiadają większe (przełączane) wieloprocesory, a rozproszona pamięć dzielona nie ma żadnej z nich.

2.3. Wieloprocesory pierścieniowe

Kolejnymi przedstawicielami grupy systemów z pamięcią dzieloną są wieloprocesory pierścieniowe reprezentowane przez system Memnet. W systemie Memnet przestrzeń adresowa dzieli się na część prywatną i część wspólną. Część prywatna dzieli się dalej na obszary, tak że każdej maszynie przypada fragment przestrzeni na stosy i inne nie dzielone dane oraz kod. Część wspólna należy do wszystkich maszyn (jest między nie rozdzielana) i jest utrzymywana w spójności za pomocą nadzoru sprzętowego podobnego do używanego w wieloprocesorach szynowych. Pamięć wspólna dzieli się na 32-bajtowe bloki, które są jednostkami transmisji dokonywanych między maszynami.

Wszystkie maszyny w systemie Memnet są ze sobą połączone w zmodyfikowany pierścień przekazywania żetonu (RYS.4a.). Pierścień składa się z 20 równoległych linii, pozwalających na przesyłanie co 100 ns 16 bitów danych i 4 bitów sterujących z szybkością rzędu 160 Mb/s. Interfejs pierścienia - MMU (ang. Memory Management Unit - jednostka zarządzania pamięcią), pamięć podręczna i część pamięci operacyjnej (RYS.4b.) są zintegrowane w urządzenie Memnet (ang. Memnet device). W odróżnieniu od wieloprocesorów szynowych, w systemie Memnet nie ma scentralizowanej, globalnej pamięci. Zamiast tego każdy 32-bajtowy blok w dzielonej (wspólnej) przestrzeni adresowej ma maszynę macierzystą, w której na stałe rezerwuje się dla niego pamięć fizyczną w polu pamięci macierzystej (RYS.4b.). Blok może być przechowywany w pamięci podręcznej innej maszyny niż macierzysta. Obszary pamięci podręcznej i pamięci macierzystej dzielą tę samą przestrzeń buforów, lecz z uwagi na drobne różnice w ich użytkowaniu traktujemy je tutaj jako osobne jednostki. Blok przeznaczony tylko do czytania może wystąpić na wielu maszynach. Blok przeznaczony do czytania i zapisywania. może wystąpić tylko na jednej maszynie. W obu przypadkach blok nie musi występować w swej maszynie macierzystej. Maszyna macierzysta gwarantuje jedynie miejsce na przechowanie bloku, jeśli żadna inna maszyna nie będzie chciała go przyjąć do swojej pamięci podręcznej. Cecha ta jest konieczna ze względu na brak pamięci globalnej. W rezultacie pamięć globalna została rozprzestrzeniona na wszystkie maszyny.

Rys. 4. Wieloprocesor pierścieniowy: a) pierścień systemu Memnet, b) pojedyncza maszyna, c) tablica bloków.

Urządzenie Memnet zawiera na każdej maszynie tablicę (RYS.4c.), która zawiera po jednej pozycji dla każdego bloku dzielonej przestrzeni adresowej i jest indeksowana za pomocą numeru bloku. Każda pozycja tablicy zawiera bit ważności, informujący czy blok znajduje się w pamięci podręcznej i czy jest aktualny, bit wyłączności, określający czy kopia lokalna (jeśli istnieje) jest jedyna, bit macierzysty, który jest ustawiany tylko na macierzystej maszynie bloku, bit przerwania, służący do wymuszania przerwań oraz pole lokalizacji, określające położenie bloku w pamięci podręcznej, jeśli jest w niej obecny i aktualny.

W systemie Memnet, gdy jednostka centralna potrzebuje przeczytać słowo z pamięci dzielonej, wówczas adres pamięci, spod którego ma nastąpić czytanie, jest przekazywany do urządzenia Memnet, a ono sprawdza, czy blok występuje w tablicy bloków. Jeśli tak, to zamówienie zostaje wykonane natychmiast. W przeciwnym razie urządzenie Memnet czeka do chwili, aż wychwyci krążący żeton, po czym umieszcza w pierścieniu pakiet z zamówieniem i zawiesza jednostkę centralną. Pakiet z zamówieniem zawiera potrzebny adres oraz puste pole wielkości 32 bitów. Gdy pakiet przechodzi wokół pierścienia, każde napotykane urządzenie Memnet sprawdza, czy ma potrzebny blok. Pierwsze urządzenie, które blok zawiera, umieszcza go w pustym polu i modyfikuje nagłówek pakietu, zakazując następnym maszynom robienia tego samego. Jeżeli blok miał ustawiony bit wyłączności, to następuje wyczyszczenie tego bitu. Ponieważ zamówiony blok musi gdzieś wystąpić, jest gwarantowane, że powracający do nadawcy pakiet będzie go zawierał. Wysyłające zamówienie urządzenie Memnet zapamiętuje wówczas blok i zwalnia jednostkę centralną, jako że zamówienie zostało spełnione.

Problem powstaje wówczas, gdy zamawiająca blok maszyna nie ma miejsca w pamięci podręcznej na jego przechowanie. Aby zrobić dla niego miejsce w pamięci podręcznej, maszyna wybiera z niej losowo inny blok i odsyła do komputera macierzystego, zwalniając w ten sposób przegródkę. Nigdy nie wybiera się bloków mających ustawiony bit macierzysty, ponieważ one są już u siebie.

Zapisywanie działa trochę inaczej niż czytanie. Rozróżnia się trzy przypadki. Jeśli blok zawierający słowo, które ma zostać zapisane, jest obecny i jest jedynym egzemplarzem w systemie (tzn. ma ustawiony bit wyłączności), to słowo zostaje po prostu zapisane lokalnie. Jeśli potrzebny blok jest obecny, lecz nie jest jedyną kopią, to najpierw wysyła się pakiet unieważniający wokół pierścienia, aby zmusić inne maszyny do usunięcia swoich kopii zapisywanego bloku. Gdy pakiet unieważniający powróci do nadawcy, ustawia się bit wyłączności danego bloku i dokonuje zapisu lokalnie. Jeśli blok jest nieobecny, to wysyła się pakiet będący kombinacją zamówienia czytania i unieważnienia. Pierwsza maszyna przechowująca blok przekopiowuje go do pakietu i usuwa własną kopię. Wszystkie następne maszyny po prostu usuwają blok ze swoich pamięci podręcznych. Po powrocie pakietu do nadawcy blok zostaje zapamiętany i zapisany.

System Memnet pod wieloma względami przypomina wieloprocesor szynowy. W obu przypadkach operacje czytania zawsze zwracają wartość zapisaną ostatnio. Również w obu projektach blok może być nieobecny w pamięci podręcznej, występować w wielu pamięciach podręcznych udostępniony do czytania lub tylko w jednej z nich, gdy chodzi o czytanie. Podobne są również protokoły, jednak system Memnet nie ma scentralizowanej pamięci globalnej. Największą różnicą między wieloprocesorami szynowymi a wieloprocesorami pierścieniowymi, takimi jak Memnet, jest ścisłe powiązanie tych pierwszych - ich jednostki centralne znajdują się zazwyczaj na jednej płycie montażowej. Maszyny w pierścieniu wieloprocesorów mogą natomiast być powiązane znacznie luźniej, w zasadzie mogą to być nawet komputery osobiste rozmieszczone na terenie budynku na podobieństwo sieci lokalnej LAN. Ponadto, w przeciwieństwie do wieloprocesorów szynowych, wieloprocesor pierścieniowy, taki jak Memnet, nie ma oddzielnej pamięci globalnej. Jedyne, co ma, to pamięć podręczna. Obie te różnice czynią z wieloprocesorów pierścieniowych niemalże realizację rozproszonej pamięci dzielonej środkami sprzętowymi.

2.4. Wieloprocesory przełączane

Choć wieloprocesory szynowe i wieloprocesory pierścieniowe działaj dobrze w małych systemach (do około 64 jednostek centralnych), to jednak nie dają się skalować do systemów z setkami lub tysiącami procesorów. W miarę dodawania jednostek centralnych przepustowość szyny lub pierścienia osiąga w którymś momencie wartość graniczną. Dalsze dodawanie jednostek centralnych przestaje poprawiać działanie systemu. Do problemu niewystarczającej przepustowości można podejść na dwa sposoby:

zmniejszając zapotrzebowanie na komunikację,

zwiększając pojemność łącz komunikacyjnych.

W przypadku pierwszego sposobu uzupełniające prace na tym polu mogą się koncentrować na poprawianiu protokołów obsługi pamięci podręcznych, optymalizowaniu rozmiarów bloków, reorganizowaniu programów w celu uzyskania większej lokalności odwołań do pamięci itp. Niemniej jednak, dochodzi w końcu do sytuacji, w której każdy sposób został już wypróbowany, a wciąż istnieje konieczność dołączenia dalsze jednostki centralne, natomiast w szynie nie ma już na to miejsca. Jedynym wyjściem jest zwiększenie przepustowości szyny. Jeden ze sposobów polega na zmianie topologii i przejściu na przykład od jednej szyny do dwu, trzech lub siatki szyn. Zmieniając topologię połączeń sieciowych, można powiększyć ich przepustowość.

Inna metoda polega na zbudowaniu systemu w postaci hierarchii. Nadal umieszcza się pewną liczbę procesorów w pojedynczej szynie, uważając obecnie całą tę jednostkę (procesory i szynę) za grono. System powstaje z wielu gron połączonych dodatkowymi szynami (RYS.5a.). Dopóki większość procesorów komunikuje się przede wszystkim w obrębie swojego grona, dopóty ruch między gronami będzie względnie mały. Jeżeli jedna szyna między gronami jest niewystarczająca, to dodaje się drugą szynę lub organizuje grona w drzewo lub siatkę. Jeśli nadal istnieje potrzeba poszerzania pasma przesyłania, to zbiera się szynę, drzewo lub siatkę gron w jedno supergrono i dzieli system na wiele supergron. Supergrona mogą być połączone za pomocą szyny, drzewa lub siatki itp. (RYS.5b.).

Rys. 5. Wieloprocesor przełączany: a) trzy grona połączone za pomocą szyny tworzące supergrono,
b) dwa supergrona wraz z łączącą je szyną.

Maszyna o nazwie Dash powstała jako projekt badawczy (projekt hierarchiczny, oparty na siatce gron). Jest ona prototypem, złożonym z 64 jednostek centralnych (RYS.6a.). Jej uproszczony obraz składa się ona z 16 gron, z których każde zawiera szynę, cztery jednostki centralne, 16 MB globalnej pamięci i jakieś wyposażenie wejścia-wyjścia (dyski itd.). W celu uproszczenia rysunku, nie zamieszczono na nim wyposażenia wejścia-wyjścia oraz dwu procesorów w każdym gronie. Każda jednostka centralna może podglądać swoje lokalną szynę, ale nie inne. Łączna przestrzeń adresowa dostępna w prototypie wynosi 256 MB i jest podzielona na 16 obszarów po 16 MB każdy. Pamięć globalna grona 0 ma adresy od 0 do 16 MB. Pamięć globalna grona 1 ma adresy od 16 MB do , 32 MB itd. Pamięć działa na zasadzie pamięci podręcznej przenoszącej bloki wielkości 16 bajtów, zatem każde grono ma w swojej przestrzeni adresowej 1 M (tzn. 1 048 576) bloków pamięci.

Rys. 6. Maszyna Dash: a)uproszczony obraz architektury, b) katalog prototypu.

Katalogi

Każde grono ma katalog (ang. directory) utrzymujący informacje o tym, w których gronach znajdują się obecnie kopie jego bloków. Ponieważ każde grono ma 1 M bloków pamięci, więc jego katalog zawiera 1 M pozycji - po jednej na blok. Każda pozycja zawiera mapę bitów z jednym bitem przypadającym na grono, który informuje, czy dane grono przechowuje blok w pamięci podręcznej, czy nie. Wpis katalogowy ma również dwubitowe pole określające stan bloku. Katalogi mają istotne znaczenie dla działania maszyny Dash. Sama nazwa Dash wywodzi się od słów "Directory Architecture for Shared Memory" (architektura katalogu dzielonej pamięci).

Rozporządzanie 1 M wpisów - po 18 bitów każdy - oznacza, że ogólny rozmiar każdego katalogu wynosi ponad 2 MB. Przy 16 gronach łączna pamięć katalogowa przekracza 36 MB, czyli około 14 procent z 256 MB. Mimo zwiększania liczby jednostek centralnych w gronie wielkość pamięci katalogu nie ulega zmianie. Tak więc trzymanie większej liczby jednostek centralnych w gronie pozwala rozłożyć koszt katalogu na więcej procesorów i zredukować koszt przypadający na jeden procesor. Teoretycznie projekt zakłada poprawne działanie w przypadku jednego procesora w gronie, lecz koszt katalogu i sprzętu szynowego przypadający na jednostkę centralną staje się wówczas większy.

Mapa bitów nie jest jedynym sposobem pamiętania, które grono utrzymuje które bloki w pamięci podręcznej. Inne podejście polega na zorganizowaniu każdego wpisu katalogowego w postaci jawnej listy, określającej, które grona przechowują dany blok pamięci. Jeżeli ilość wspólnych informacji jest niewielka, to rozwiązanie listowe zajmuje mało bitów. Duża ilość dzielonych informacji wymaga więcej bitów. Listy mają też tę wadę, że są strukturami danych o zmiennej długości, jednak te problemy dają się rozwiązać. Na przykład wieloprocesor Alewife używa w katalogach map bitów zamiast list i obsługuje nadmiary katalogowe za pomocą oprogramowania.

Każde grono w maszynie Dash jest przyłączone do interfejsu, który umożliwia mu komunikowanie się z innymi gronami. Interfejsy są połączone za pomocą łącz między gronami (uproszczonych szyn) w prostokątną siatkę (RYS.6a.). Przy dodawaniu do systemu większej liczby gron dokłada się również więcej łącz między gronami, dzięki czemu szerokość pasma przesyłania rośnie wraz ze zmianą skali systemu. W systemie łącz między gronami wytycza się trasy techniką robaczych dziur (ang. wormhole routing), co oznacza, że pierwsza część pakietu może być przekazywana jeszcze przed otrzymaniem całego pakietu, zmniejszając opóźnienie przy każdym przeskoku. W rzeczywistości są dwa zbiory połączeń między gronami: jeden dla pakietów zamówień, a drugi dla pakietów odpowiedzi. Łącz między gronami nie można podglądać.

Wykorzystanie pamięci podręcznych

Pamięci podręczne są wykonane na dwu poziomach: pamięć podręczna pierwszego poziomu oraz większa pamięć podręczna drugiego poziomu. Pamięć podręczna pierwszego poziomu jest podzbiorem pamięci drugiego poziomu. Każda pamięć podręczna (drugiego poziomu) nadzoruje lokalną szynę za pomocą protokołu podobnego nieco do protokołu uwłaszczania pamięci podręcznej. Każdy blok pamięci podręcznej może znajdować się w jednym z trzech następujących stanów:

nie przechowany - w danej pamięci zna j duj e się jedyny egzemplarz bloku,

czysty - zawartość bloku pamięci jest aktualna; blok może znajdować się w innych pamięciach podręcznych,

zabrudzony - zawartość bloku pamięci jest niepoprawna, tylko jedna pamięć podręczna utrzymuje dany blok.

Stan każdego bloku pamięci podręcznej przechowuje się w polu "stan" odpowiadającego mu wpisu katalogowego (RYS.6b.).

Protokoły

Protokoły maszyny Dash są oparte na uwłaszczaniu i unieważnianiu. W każdej chwili każdy blok pamięci podręcznej ma niepowtarzalny numer. Właścicielami bloków nie przechowanych lub czystych są ich grona macierzyste. Właścicielami bloków zabrudzonych są grona utrzymujące ich jedyne egzemplarze. Zapisanie bloku czystego wymaga najpierw odnalezienia i unieważnienia wszystkich istniejących jego kopii. Tu właśnie przydają się katalogi. Jednostka centralna sprawdza najpierw własną pamięć podręczną. Jeśli nigdzie nie ma danego słowa, to wydaje zamówienie do szyny lokalnego grona, aby sprawdzić, czy inna jednostka centralna w gronie ma blok zawierający to słowo. Jeżeli któryś z bloków je zawiera, to następuje transmisja bloku między pamięciami podręcznymi, aby umieścić go w pamięci podręcznej zamawiającej jednostki centralnej. Jeśli blok jest czysty, to wykonuje się jego kopię. Jeżeli jest zabrudzony, to macierzysty katalog otrzymuje informację, że blok jest obecnie czysty i dzielony. W każdym przypadku natrafienie na słowo w jednej z pamięci podręcznych załatwia zapotrzebowanie, lecz nie wpływa na mapę bitów żadnego z katalogów. Jeśli blok nie występuje w żadnej z pamięci podręcznych grona, to wysyła się pakiet z zamówieniem do jego grona macierzystego, które można ustalić według czterech starszych bitów adresu pamięci. Grono macierzyste może być równie dobrze gronem zamawiającym, wówczas nie ma fizycznego przesłania komunikatu. Sprzęt zarządzający katalogiem w gronie macierzystym sprawdza jego tablice, aby określić stan bloku. Jeśli blok jest nie przechowany lub czysty, to sprzęt pobiera go ze swojej pamięci globalnej i odsyła gronu zamawiającemu. Następnie aktualizuje katalog, zaznaczając blok jako przechowany w pamięci podręcznej grona zamawiającego (jeśli nie miał dotąd takiego oznaczenia). Jeżeli jednak potrzebny blok jest zabrudzony, to sprzęt katalogowy identyfikuje utrzymujące go grono i tam kieruje zamówienie. Grono przechowujące zabrudzony blok wysyła go wtedy do grona zamawiającego i oznacza swojak kopię jako czystą, ponieważ jest ona odtąd dzielona. Wysyła ono również kopię z powrotem do grona macierzystego, aby można było zaktualizować pamięć i zmienić stan bloku na czysty.

Zapisywanie odbywa się inaczej. Zanim zapis stanie się możliwy, wykonująca go jednostka centralna musi mieć pewność, że jest właścicielką jedynego egzemplarza bloku przechowywanego w systemie. Jeżeli blok znajduje się już w pamięci podręcznej na jej płycie i jest zabrudzony, to zapisu można dokonać natychmiast. Jeżeli blok, który ona ma, jest czysty, to najpierw wysyła się do grona macierzystego pakiet z prośbą o odnalezienie i unieważnienie wszystkich kopii bloku. Jeśli zamawiająca jednostka centralna nie ma bloku w pamięci podręcznej, to kieruje na lokalną szynę zamówienie sprawdzenia, czy ma go któryś z sąsiadów. Jeśli tak, to następuje transmisja między pamięciami podręcznymi (lub między pamięcią operacyjną a podręczną). Jeżeli blok jest czysty, to wszystkie ewentualne jego kopie muszą zostać przez grono macierzyste unieważnione. Jeśli lokalne poszukiwania spełzną na niczym, bo blok jest umiejscowiony gdzie indziej, to wysyła się pakiet do grona macierzystego. Można wtedy wyróżnić trzy przypadki. Jeśli blok jest nie przechowany, to zostaje oznaczony jako zabrudzony i wysłany do zamawiającego. Jeśli jest czysty, to unieważnia się wszystkie kopie, po czym wykonuje się procedurę dla bloku nie przechowanego. Jeśli jest zabrudzony, to kieruje się zamówienie do zdalnego grona, będącego aktualnie w posiadaniu bloku (jeśli potrzeba). Grono to unieważnia swoje własny kopię i spełnia zamówienie.

Utrzymywanie spójności pamięci w maszynie Dash (lub dowolnym wielkim wieloprocesorze) jest o wiele bardziej złożone niż w prostym modelu. Pojedynczy dostęp do pamięci może wymagać wysyłki pokaźnej liczby pakietów. Ponadto, aby utrzymać spójność pamięci, dostęp nie może zostać zakończony przed potwierdzeniem pakietów, co może mieć poważny wpływ na działanie. Aby obejść te problemy, w maszynie Dash użyto wielu specjalnych technik, takich jak dwa zbiory łącz między gronami, potokowe zapisy oraz innej, niż można by się spodziewać, semantyki pamięci. Ta realizacja "pamięci dzielonej" wymaga wielkiej bazy danych (katalogi), sporo mocy obliczeniowej (sprzęt zarządzający katalogami) oraz - potencjalnie - wysyłania i potwierdzania wielkiej liczby pakietów.

2.5. Wieloprocesory standardu NUMA

Sprzętowe organizowanie pamięci podręcznych w wielkich wieloprocesorach nie jest proste. Sprzęt musi obsługiwać złożone struktury danych, a kontroler pamięci podręcznej lub układ MMU (jednostka zarządzająca pamięci) musi mieć wbudowane zawiłe protokoły. Nieuniknionym tego skutkiem jest duży koszt wielkich wieloprocesorów i ich mała popularność. Włożono sporo wysiłku w poszukiwanie innych rozwiązań projektowych, nie wymagających pracochłonnych schematów obsługi pamięci podręcznych. Jedną z takich architektur jest wieloprocesor NUMA (ang. Non Uniform Memory Access - niejednolity dostęp do pamięci). Podobnie jak tradycyjny wieloprocesor UMA (ang. Uniform Memory Access - jednolity dostęp do pamięci), maszyna NUMA ma jedną wirtualną przestrzeń adresową widoczną dla wszystkich jednostek centralnych. Gdy jakakolwiek jednostka centralna zapisuje komórkę a, inna jednostka centralna, czytając następnie a, otrzyma ostatnio zapisaną wartość.

Różnica między maszynami UMA i NUMA leży nie w semantyce, lecz w działaniu. W maszynie NUMA dostęp do pamięci odległej jest znacznie wolniejszy niż dostęp do pamięci lokalnej i nie próbuje się ukrywać tego faktu za pomocą sprzętowej obsługi pamięci podręcznych. Iloraz czasu zdalnego dostępu do czasu lokalnego wynosi na ogół 10:1, a współczynnik 2 odchylenia w każdą stronę nie jest niczym niezwykłym. Tak więc jednostka centralna może bezpośrednio wykonywać program rezydujący w pamięci odległej, lecz wówczas jego działanie może być o rząd wolniejsze od działania w przypadku, gdyby znajdował się w pamięci lokalnej.

Maszyna BBN Butterfly jest przykładem maszyny NUMA. W tym projekcie każda jednostka centralna jest skojarzona dokładnie z jedni pamięcią operacyjną. Każdy z małych kwadratów (RYS.7.) reprezentuje parę: jednostka centralna plus pamięć. Jednostki centralne po prawej stronie rysunku są tymi samymi, co jednostki po lewej. Jednostki centralne są połączone za pośrednictwem ośmiu przełączników, z których każdy ma cztery porty wejściowe i cztery porty wyjściowe. Lokalne zamówienia na pamięć są obsługiwane natychmiast. Zdalne zamówienia przekształca się w pakiety zamówień i wysyła do odpowiedniej pamięci za pomocą sieci przełączającej. Również tutaj jest możliwe zdalne wykonywanie programów, lecz pod karą straszliwego pogorszenia działania.

Rys. 7. System BBN Butterfly.

Cechy wieloprocesorów NUMA

Maszyny NUMA mają trzy interesujące nas właściwości:

jest możliwy dostęp do pamięci odległej,

dostęp do pamięci odległej jest wolniejszy od dostępu do pamięci lokalnej,

czas dostępu do pamięci odległej nie jest ukrywany za pomocą pamięci podręcznych.

W maszynie Dash i większości współczesnych wieloprocesorów UMA dostęp zdalny jest także wolniejszy od dostępu lokalnego. Cechę tę zwalcza się poprzez obecność pamięci podręcznych. Gdy następuje kontakt z odległym słowem, otaczający je blok pamięci zostaje sprowadzony do pamięci podręcznej zamawiającego procesora, tak że następne odwołania przebiegają z pełną szybkością. Choć obsługa braku słowa w pamięci podręcznej powoduje małe opóźnienie, wykonywanie programów z pamięci odległych może być tylko o ułamek droższe od wykonywania ich w pamięci lokalnej. Obserwacja ta prowadzi do wniosku, że nie ma istotnego znaczenia, w której pamięci są utrzymywane strony: kod i dane są automatycznie przemieszczane przez sprzęt tam, gdzie są potrzebne (choć zły wybór grona macierzystego dla każdej strony w maszynie Dash powoduje dodatkowe koszty). Maszyny NUMA nie mają tej właściwości, toteż rozmieszczenie stron w poszczególnych pamięciach (czyli na różnych maszynach) nabiera wielkiego znaczenia. Kluczowe zagadnienie w oprogramowaniu maszyn NUMA stanowią decyzje o lokalizacji poszczególnych stron w celu maksymalizowania wydajności.

Gdy program rozpoczyna działanie w maszynie NUMA, strony mogą, ale nie musza, być rozmieszczone wstępnie w pewnych jej procesorach (procesorach macierzystych). W każdym przypadku, gdy jednostka centralna próbuje sięgnąć do strony znajdującej się aktualnie poza jej przestrzenią adresową, następuje błąd strony. System operacyjny przechwytuje ten błąd i musi podjąć decyzję. Jeśli jest to strona przeznaczona tylko do czytania, to wybiera się jej zwielokrotnienie (tzn. tworzy lokalną kopię bez naruszania oryginału) lub dokonuje odwzorowania strony wirtualnej w pamięci odległej, co zmusza do zdalnego dostępu dla wszystkich adresów na stronie. Jeśli strona służy zarówno do czytania, jak i do zapisu, to wybiera się jej przeniesienie do procesora sygnalizującego brak strony (z unieważnieniem oryginalnej strony) lub odwzorowanie strony wirtualnej w pamięci odległej.

Istnieją tu proste skrajności. Jeśli wykona się kopię lokalną (zwielokrotnienie lub przeniesienie) i strona nie będzie zbyt często używana, to znaczna ilość czasu zostanie zmarnowana na niepotrzebne sprowadzenie strony. Jeśli nie wykona się kopii i strona zostanie odwzorowana zdalnie, po czym nastąpią liczne do niej dostępy, to będą one za wolne. Systemowi operacyjnemu przypada w udziale zgadywać, czy strona będzie intensywnie używana w przyszłości. Jeśli odgadnie źle, to poniesie karę w postaci pogorszenia działania. Niezależnie od powziętego kroku strona zostaje odwzorowana lokalnie lub zdalnie i nieudana instrukcja wznowiona. Następne odwołania do tej strony dokonują się sprzętowo, bez angażowania oprogramowania. Jeśli nie zostanie podjęte żadne inne działania, to źle podjęta decyzja może nigdy nie zostać cofnięta.

Algorytmy NUMA

Aby umożliwić naprawianie błędów i adaptowanie systemu do zmieniających się schematów odwołań, systemy NUMA wykorzystują zazwyczaj wykonywany drugoplanowo proces-demon, zwany analizatorem stron (ang. page scanner). Okresowo (np. co 4 sekundy) analizator stron zbiera informacje statystyczne o występowaniu lokalnych i zdalnych odwołań, w czym pomaga mu sprzęt. Przy każdym
n-tym uaktywnieniu analizator stron dokonuje przewartościowania swoich wcześniejszych decyzji odnośnie do kopiowania stron lub odwzorowywania ich w pamięci odległej. Jeśli statystyka użycia wykazuje, że strona jest źle umiejscowiona, to analizator stron cofa odwzorowanie, a to spowoduje błąd przy następnym odwołaniu do strony i umożliwi podjęcie nowej decyzji o lokalizacji. Jeśli strona jest przemieszczana zbyt często w krótkim przedziale czasu, to analizator stron może jad oznaczyć jako zamrożoną (ang. frozen), zakazując dalszych przemieszczeń do czasu wystąpienia określonego zdarzenia (np. upłynięcia pewnej liczby sekund).

Dla maszyn NUMA zaproponowano liczne strategie różniące się algorytmem używanym przez analizator do unieważniania stron oraz algorytmem podejmowania decyzji o umieszczaniu strony po wykryciu jej braku. Jeden z możliwych algorytmów analizatora polega na unieważnianiu dowolnej strony, dla której wystąpiło więcej odwołań zdalnych niż lokalnych. Silniejszy test unieważnia stronę tylko wtedy, gdy licznik odwołań zdalnych przekroczył odwołania lokalne w ciągu ostatnich
k uaktywnień analizatora. Inne możliwości to odmrażanie stron po upływie t sekund lub gdy liczba odwołań zdalnych przekroczy liczbę odwołań lokalnych o pewną wielkość, względnie przez pewien czas. Po wystąpieniu braku strony możliwe są różne algorytmy - zawsze uwzględniające zwielokrotnianie lub przenoszenie bądź nie korzystające z tego nigdy. Bardziej wyszukany polega na wykonywaniu zwielokrotnień lub przeniesień dopóty, dopóki strona nie jest zamrożona. Można także brać pod uwagę kryteria ostatniego użycia strony oraz fakt przebywania lub nieprzebywania strony w jej maszynie "macierzystej".

2.6. Porównanie systemów pamięci dzielonej

Istnieje szerokie spektrum systemów z pamięcią dzieloną - od systemów zapewniających spójność wyłącznie za pomocą sprzętu do takich, które robią to w całości programowo (RYS.8.). Na najniższym poziomie całego spektrum maszyn z pamięcią dzieloną stoją wieloprocesory jednoszynowe z pamięciami podręcznymi nadzorowanymi sprzętowo, utrzymywanymi w spójności za pomocą podglądania szyny. Są to najprostsze maszyny z pamięcią dzieloną, działające całkowicie sprzętowo. Do tej kategorii należą różne maszyny produkowane przez firmę Sequent i dostarczane przez innych sprzedawców oraz eksperymentalna stacja robocza DEC Firefly (pięć komputerów VAX na wspólnej szynie). Projekt tego rodzaju sprawuje się dobrze dla małej lub średniej liczby jednostek centralnych, lecz ulega gwałtownej degradacji, gdy przepustowość szyny osiąga wartość graniczną.

Rys. 8. Spektrum maszyn z pamięcią dzieloną.

Kolejny etap stanowią wieloprocesory przełączane, takie jak maszyna Dash ze Stanford lub maszyna Alewife z MIT. One również posiadają pamięć podręczną nadzorowaną sprzętowo, lecz używają katalogów i innych struktur danych do pilnowania, które jednostki centralne lub grona mają które bloki w pamięciach podręcznych. Do utrzymywania spójności stosuje się złożone algorytmy, lecz z uwagi na ich pamiętanie w mikrokodowanych jednostkach MMU (z potencjalną programową obsługą wyjątków) zalicza się te maszyny do implementacji w przeważającej części "sprzętowych".

W dalszej kolejności występują maszyny NUMA. Są one efektem wymieszania sterowania sprzętowego i programowego. Podobnie jak w wieloprocesorach każda jednostka centralna NUMA może mieć dostęp do każdego słowa wspólnej przestrzeni adresowej, czytać je lub zapisywać. W odróżnieniu od wieloprocesora obsługa pamięci podręcznych (tj. zastępowanie i wędrówka stron) należy do oprogramowania (systemu operacyjnego), a nie do sprzętu (jednostek MMU). Przykładami maszyn NUMA są Cm* oraz BBN Butterfly.

Podążając dalej wzdłuż spektrum, pojawiają się maszyny wykonujące system stronicowanej rozproszonej pamięci dzielonej. Są nimi IVY i Mirage. Każda z jednostek centralnych w takim systemie ma własną, prywatną pamięć operacyjną i - w odróżnieniu od maszyn NUMA i wieloprocesorów UMA - nie może bezpośrednio odwoływać się do pamięci odległej. Gdy jednostka centralna zaadresuje słowo w przestrzeni adresowej reprezentowanej przez stronę aktualnie położoną w innej maszynie, wówczas następuje przejście do systemu operacyjnego i wymagana strona musi zostać sprowadzona przez oprogramowanie. System operacyjny uzyskuje niezbędną stronę, wysyłając komunikat z prośbą do maszyny, w której strona aktualnie przebywa. Tak więc zarówno rozmieszczenie stron, jak i dostęp do nich odbywa się tutaj programowo.

Kolejnymi maszynami są maszyny dzielące tylko wybraną część ich przestrzeni adresowych, a mianowicie - wspólne zmienne i inne struktury danych. W ten sposób pracują systemy Munin oraz Midway. Do określenia, które zmienne są wspólne, a które nie, są potrzebne informacje dostarczone przez użytkownika. W tych systemach punkt ciężkości przenosi się z prób udawania, że istnieje jedna wspólna pamięć, na zagadnienie utrzymywania zbioru zwielokrotnionych, rozproszonych struktur danych i ich spójności przy wszelkich aktualizacjach, być może pochodzących ze wszystkich maszyn używających danych dzielonych. W pewnych przypadkach sprzęt stronicujący wykrywa zapisy, co może pomagać w utrzymaniu spójności. Kiedy indziej sprzęt stronicujący nie jest wykorzystywany do zarządzania spójnością.

Na samym końcu spektrum pojawiają się systemy pracujące z obiektową rozproszony pamięcią dzieloną. Inaczej niż we wszystkich innych systemach, tutaj programom nie pozwala się na zwyczajny dostęp do danych dzielonych. Musza to robić za pomocą chronionych metod, co oznacza, że system wsparcia ich działania zawsze przejmuje nadzór nad każdym dostępem, pomagając w utrzymywaniu spójności. Wszystko dokonuje się tutaj za pomocą oprogramowania, bez jakiegokolwiek wsparcia sprzętowego. Przykład takiego projektu stanowi system Orca oraz system Linda.

Różnice między tymi sześcioma typami systemów (TAB.2.) zależą od ściśle powiązanego sprzętu, po do luźno powiązanego oprogramowania. Pierwsze cztery typy mają do zaoferowania model pamięci złożonej ze standardowej, stronicowanej, liniowej, wirtualnej przestrzeni adresowej. Pierwsze dwa są regularnymi wieloprocesorami, a w następnych dwu uczyniono wszystko co możliwe, aby je naśladować. Ponieważ te cztery typy działają jak wieloprocesory, jedynymi możliwymi operacjami są czytanie i pisanie. W piątej kolumnie zmienne dzielone są czymś specjalnym, lecz dostęp do nich odbywa się wciąż za pomocą normalnego czytania i pisania. Systemy obiektowe ze swoimi zintegrowanymi danymi i metodami mogą zaoferować więcej ogólnych działań, reprezentując wyższy poziom abstrakcji niż surowa pamięć.

	Wieloprocesory			Systemy DSM
Jednostka	Pojedyncza szyna	Przełączanie	NUMA	Stronicowanie	Zmienne dzielone	Obiekty
Liniowa, dzielona, wirtualna przestrzeń adresowa ?	tak	tak	tak	tak	nie	nie
Możliwe operacje	czytanie pisanie	czytanie pisanie	czytanie pisanie	czytanie pisanie	czytanie pisanie	ogólne
Obudowa danych i metody obiektowe ?	nie	nie	nie	nie	nie	tak
Dostęp zdalny organizowany sprzętowo ?	tak	tak	tak	nie	nie	nie
Możliwość pamięci nieprzydzielonej ?	tak	tak	tak	nie	nie	nie
Co zmienia zamówienia dostępu do zdalnej pamięci w komunikaty ?	MMU	MMU	MMU	OS	system wsparcia	system wsparcia
Nośnik przesyłania	szyna	szyna	szyna	sieć	sieć	sieć
Organizacja wędrówki danych	sprzęt	sprzęt	program	program	program	program
Jednostka przesyłania	blok	blok	strona	strona	zmienna dzielona	obiekt

Tab. 2. Porównanie sześciu typów systemów pamięci dzielonej.

Rzeczywista różnica między wieloprocesorami a systemami DSM leży w tym, czy dane zdalne mogą być osiągane po prostu za pomocą odwoływania się do ich adresów, czy też nie. Dla wszystkich wieloprocesorów odpowiedź brzmi - tak. W systemach DSM (rozproszonej pamięci dzielonej) odpowiedź jest negatywna: zawsze potrzebna jest interwencja oprogramowania. Podobnie, nie przydzielona, globalna pamięć, tj. pamięć nie skojarzona z żadną konkretną jednostką centralną jest możliwa w przypadku wieloprocesorów, lecz nie w systemach DSM (ponieważ te ostatnie są zbiorami osobnych komputerów połączonych siecią).

W wieloprocesorach po wykryciu odwołania zdalnego następuje wysłanie komunikatu do pamięci odległej, co jest wykonywane za pomocą kontrolera pamięci podręcznej lub jednostki MMU. W systemie DSM wysyłkę tę wykonuje system operacyjny lub system wsparcia wykonywania programu. Używa się również różnych nośników przesyłania: szyny o dużej szybkości (lub zbioru szyn) w przypadku wieloprocesorów i konwencjonalnej sieci lokalnej (zazwyczaj) w systemach DSM (choć niekiedy różnica między "szyn" a "siecią" jest dyskusyjna i dotyczy głównie liczby przewodów).

Następny punkt dotyczy przenoszenia danych w przypadku powstania takiej konieczności. Pod tym względem maszyny NUMA są podobne do systemów DSM - w obu przypadkach za przemieszczanie danych z maszyny do maszyny odpowiada oprogramowanie, a nie sprzęt. W tych sześciu typach systemów stosuje się też różne jednostki przesyłania danych: w przypadku wieloprocesorów ITMA są to bloki pamięci podręcznych, w maszynach NUMA i stronicowanym systemie DSM - strony, a w dwu ostatnich systemach - zmienne lub obiekty.

 

Modele spójności

Ze względu na fakt, iż dopuszczenie wielu kopii ułatwia rozwiązanie problemu efektywności działania, gdyż wystarczy zaktualizować kopię, lecz postępowanie takie wprowadza nowy problem: jak utrzymywać spójność wszystkich kopii? Utrzymywanie doskonałej spójności jest szczególnie trudne, gdy różne kopie znajdują się w różnych maszynach, mogących się kontaktować jedynie za pomocą wysyłania komunikatów przez wolną (w porównaniu do szybkości pamięci) sieć. W niektórych systemach DSM (a także wieloprocesorowych) stosuje się rozwiązanie polegające na zaakceptowaniu niepełnej spójności jako ceny lepszego działania. Precyzowanie, co dokładnie należy rozumieć przez spójność oraz jak można ją osłabić bez powodowania nieprzezwyciężalnych trudności w programowaniu, stanowi szczególnie ważny problem badawczy w przypadku systemów rozproszonej pamięci dzielonej (DSM).

Model spójności (ang. consistency model) jest pewnego rodzaju kontraktem między oprogramowaniem a pamięcią. Mówi on, że jeśli oprogramowanie będzie przestrzegać pewnych reguł, to pamięć zapewni poprawne działanie. Jeżeli oprogramowanie łamie te reguły, to wszelkie układy ulegają zerwaniu i nie gwarantuje się poprawności działań na pamięci. Opracowano szeroki wachlarz tego rodzaju kontraktów, poczynając od umów nakładających na oprogramowanie tylko niewielkie ograniczenia, a kończąc na takich, które prawie uniemożliwiają normalne programowanie.

3.1. Spójność ścisła

Najostrzejszy model spójności zwie się spójnością ścisłą (ang. strict consistency). Zdefiniowany jest on przez warunek postaci:

Każde czytanie komórki pamięci x zwraca wartość zapamiętaną przez ostatnio wykonaną operację zapisania x.

Jest to definicja naturalna i oczywista, zakłada się w niej niejawnie istnienie absolutnego, globalnego czasu, dzięki czemu określenie "ostatnio" jest jednoznaczne. Ścisłą spójność występuje w tradycyjnych jednoprocesorach i programiści jednoprocesorów są skłonni oczekiwać tego zachowania jako czegoś bardzo oczywistego. Jeśli pamięć jest więc ściśle spójna, to wszystkie zapisy są natychmiast widoczne dla wszystkich procesów i korzysta się z globalnego uporządkowania czasu. Zmiana komórki pamięci powoduje, że wszystkie następujące po niej operacje czytania tej komórki będą miały do czynienia z nową wartością, niezależnie od tego, w jakim odstępie czasu od zmiany dokonuje się tych odczytów oraz które procesy wykonują czytania i gdzie się znajdują. Aktualną wartość otrzymuje się podczas czytania także niezależnie od tego, jak szybko po nim wystąpi następny zapis.

3.2. Spójność sekwencyjna

Spójność sekwencyjna (ang. sequential consistency) jest nieco "słabszym" modelem pamięci od spójności ścisłej. Jest ona spójnością, która spełnia następujący warunek:

Wynik dowolnego wykonania jest taki sam, jak gdyby operacje wszystkich procesów zostały wykonane w pewnym porządku jedna po drugiej, przy czym operacje każdego poszczególnego procesu wystąpiły w tym ciągu w kolejności określonej przez program.

Definicja ta oznacza, że jeśli procesy wykonują się równolegle na różnych maszynach (lub choćby nibyrównolegle w systemie z podziałem czasu), to każdy dozwolony ich przeplot stanowi zachowanie możliwe do przyjęcia, ale "wszystkie procesy muszą oglądać ten sam ciąg odwołań do pamięci". Pamięć, w której jeden proces (lub procesor) dostrzega pewien przeplot, a drugi proces widzi inny, nie jest spójna sekwencyjnie. W tym kontekście proces "widzi" zapisy dokonane przez wszystkie procesy, natomiast odczyty - tylko własne.

3.3. Spójność przyczynowa

Model spójności przyczynowej (ang. casual consistency) stanowi osłabienie spójności sekwencyjnej, polegające na tym, że rozróżnia się zdarzenia, które mogą być powiązane przyczynowo i nie powiązane. Aby pamięć można było uważać za spójną przyczynowo, musi ona spełniać następujący warunek:

Zapisy potencjalnie powiązane przyczynowo muszą być widziane przez wszystkie procesy w takim samym porządku. Zapisy współbieżne mogą być na różnych maszynach oglądane w różnej kolejności.

W spójności przyczynowej dopuszcza się, aby na różnych maszynach współbieżne zapisy były oglądane w różnym porządku, natomiast te, które są powiązane przyczynowo, muszą być widoczne dla wszystkich maszyn w jednakowym porządku. W implementacji spójności przyczynowej należy utrzymywać informacje o tym, które zapisy były oglądane przez które procesy. Prowadzi to do konieczności konstruowania i utrzymywania grafu zależności jednych operacji od innych.

3.4. Spójność PRAM oraz spójność procesorowa

Następnym krokiem osłabiania pamięci jest uchylenie wymagania, które występuje w przypadku spójności przyczynowe - konieczność widoczności zapisów powiązanych przyczynowo w jednakowym porządku przez wszystkie maszyny. Zgoda na to prowadzi do spójności PRAM (ang. Pipelined RAM) określonej warunkiem:

Zapisy wykonywane przez jeden proces są otrzymywane przez wszystkie inne procesy w porządku, w którym powstawały, lecz zapisy pochodzące od różnych procesów mogą być przez różne procesy widziane w różnym porządku.

Skrót PRAM pochodzi od terminu Pipelined RAM (potokowa pamięć swobodnego dostępu), ponieważ zapisy jednego procesu mogą tworzyć potok, tzn. proces nie musi się blokować w oczekiwaniu na zakończenie każdego z nich przed rozpoczęciem następnego. Spójność PRAM jest interesująca ze względu na łatwość jej implementacji. W efekcie nie daje ona żadnej gwarancji co do porządku, w którym różne procesy oglądają zapisy, z wyjątkiem tego, że dwa (lub więcej) zapisy pochodzące z jednego źródła muszą nadchodzić po kolei, tak jakby znajdowały się w potoku. W tym modelu wszystkie zapisy wygenerowane przez różne procesy są współbieżne.

Model nazywany spójnością procesorową (ang. processor consistency) jest bardzo bliski spójności PRAM. Uważane są one wręcz za te same modele. Dodatkowo jednak na spójność procesorową nałożony jest dodatkowy warunek. Dla każdej komórki pamięci x ma istnieć globalne porozumienie co do kolejności zapisywań x. Zapisy do różnych komórek nie muszą być oglądane przez różne procesy w tym samym porządku.

Choć spójność PRAM i spójność procesorowa mogą dać lepszą wydajność od modeli silniejszych, to jednak są one wciąż zbytnio ograniczające w przypadku wielu zastosowań, gdyż wymagają, by zapisy powstające w jednym procesie były wszędzie widziane po kolei. Nie wszystkie zastosowania jednak wymagają nawet oglądania wszystkich zapisów, nie mówiąc już o oglądaniu ich w uporządkowaniu.

3.5. Spójność słaba

Definicja modelu zwanego spójnością słabą (ang. weak consistency) jest określona przez trzy jego cechy następującej postaci:

Dostępy do zmiennych synchronizujących są spójne sekwencyjnie.

Wykonanie dostępu do zmiennej synchronizującej jest zabronione dopóty, dopóki wszystkie poprzednie zapisy nie zostaną wszędzie ukończone.

Dostęp do danych (czytanie lub pisanie) jest zabroniony dopóty, dopóki nie zostaną wykonane wszystkie poprzednie dostępy do zmiennych synchronizujących.

Cecha pierwsza oznacza, iż wszystkie procesy widzą wszystkie dostępy do zmiennych synchronizujących w tym samym porządku. Zamiar dostępu do zmiennej synchronizującej musi być tedy ogłoszony światu i w żadnym innym procesie dostęp do innej zmiennej synchronizującej nie może nastąpić przed globalnym zakończeniem tego jednego dostępu. Kolejna cecha oznacza, że dostęp do zmiennej synchronizującej "opróżnia potok". Następuje wymuszenie globalnego zakończenia wszystkich zapisów będących w toku, częściowo zakończonych lub zakończonych w pewnych pamięciach, ale w innych nie. Po wykonaniu dostępu synchronizacyjnego gwarantuje się, że wszystkie poprzednie zapisy zostały również wykonane. Poprzez wykonanie synchronizacji po uaktualnieniu danych dzielonych proces może wymóc wyprowadzenie nowych wartości do wszystkich pamięci. Ostatnia cecha oznacza, że w przypadku dostępu do zwykłych zmiennych (nie służących synchronizacji), czy to do czytania, czy też do pisania, zostaną wpierw wykonane wszystkie poprzednie synchronizacje. Dzięki wykonaniu synchronizacji przed przeczytaniem danych proces może mieć pewność, że otrzyma wartości najnowsze.

Za słowem "wykonane" kryje się tutaj i wszędzie w kontekście DSM pewna złożoność. Powiada się, że czytanie zostało wykonane, gdy żaden następny zapis nie może naruszyć zwróconej wartości. Operacja zapisu jest wykonana wówczas, gdy wszystkie następne odczyty zwracają wartość przez nią zapisana. Synchronizacja jest wykonana wtedy, gdy wszystkie zmienne dzielone zostały zaktualizowane. Można też rozróżniać operacje wykonane lokalnie i globalnie.

Jeżeli kontrakt między oprogramowaniem a pamięcią głosi, że pamięć należy uaktualnić tylko przy dostępie do zmiennej synchronizującej, to nowa operacja pisania może się rozpocząć przed zakończeniem poprzedniego, a w pewnych przypadkach zapisów można w ogóle uniknąć. Oczywiście, kontrakt taki nakłada większy ciężar na programistę, lecz przewidywanym zyskiem jest sprawniejsze działanie. W odróżnieniu od poprzednich modeli pamięci wymusza on spójność na grupie operacji, a nie na poszczególnych odczytach i zapisach. Model ten jest najużyteczniejszy, gdy odizolowane dostępy do zmiennych dzielonych są rzadkie, natomiast większość z nich występuje grupowo (wiele dostępów w krótkim okresie, a potem brak jakichkolwiek dostępów przez długi czas).

W przypadku spójności słabej występuje jednak problem polegający na tym, że przy dostępie do zmiennej synchronizującej pamięć nie ma orientacji, czy zrobiono to z tego powodu, że proces zakończył zapisywanie zmiennych dzielonych, czy też dlatego, że zaczyna je czytać. Muszą więc być podejmowane działania wymagane w obu przypadkach, tj. upewnienie się, że wszystkie rozpoczęte lokalnie zapisy zostały zakończone (czyli przeniesione do wszystkich innych maszyn), jak również zgromadzenie wszystkich zapisów z innych maszyn.

3.6. Spójność zwalniania

Gdyby pamięć w przypadku spójności słabej mogła rozpoznać różnicę między wchodzeniem do sekcji krytycznej a jej opuszczaniem, to można by opracować wydajniejszą realizację. Aby dostarczyć tych informacji, są potrzebne dwa rodzaje zmiennej lub operacji synchronizującej zamiast jednego. Tych dwu rodzajów dostarcza spójność zwalniania (ang. release consistency). W celu powiadomienia systemu pamięci o planowanym wejściu do sekcji krytycznej dostępuje się do niej w trybie nabywania (ang. acquire). O wyjściu z sekcji krytycznej informuje zwolnienie (ang. release). Oba odniesienia można zrealizować jako zwykłe operacje na specjalnych zmiennych lub jako operacje specjalne. W obu przypadkach programista jest odpowiedzialny za jawne określenie w programie, kiedy mają one zostać wykonane.

Do realizacji spójności zwalniania można też zamiast sekcji krytycznych wykorzystać zapory. Zapora (ang. barrier) jest mechanizmem synchronizacji, który zabrania procesowi wejścia w n+1 fazę programu dopóty, dopóki wszystkie procesy nie zakończą fazy n. Proces, który dotarł do zapory, musi czekać na wszystkie pozostałe procesy. Gdy ostatni proces dojdzie do zapory, synchronizuje się wszystkie zmienne dzielone i podejmuje dalsze wykonywanie procesów. Opuszczenie zapory funkcjonuje jako nabycie, a dotarcie do niej stanowi zwolnienie.

Ogólnie biorąc, rozproszona pamięć dzielona ma spójność zwalniania, jeśli spełnia następujące warunki:

Przed wykonaniem zwykłego dostępu do zmiennej dzielonej muszą zostać pomyślnie zakończone w procesie wszystkie poprzednie operacje nabycia.

Zanim wolno będzie wykonać zwolnienie, należy zakończyć w procesie wszystkie poprzednie operacje czytania i pisania.

Operacje nabywania i zwalniania muszą mieć spójność procesorową (nie wymaga się spójności sekwencyjnej).

Jeśli wszystkie powyższe warunki są spełnione i procesy wykonują właściwie operacje nabywania i zwalniania (tj. w parach: nabycie-zwolnienie), to wyniki dowolnych wykonań nie będą inne niż uzyskiwane w przypadku spójności sekwencyjnej. Dzięki działaniom nabywania i zwalniania bloki operacji na zmiennych dzielonych stają się niepodzielne, co chroni przed przeplotami.

Odmienną implementacją spójności zwalniania jest leniwa spójność zwalniania (ang. lazy release consistency). W zwykłej spójności zwalniania, którą nazywana jest także pilną spójnością zwalniania (ang. eager release consistency), aby odróżnić ją od wariantu leniwego, wykonujący zwolnienie procesor przenosi wszystkie zmodyfikowane dane do wszystkich innych procesorów, które utrzymywały kopie tych danych w pamięciach podręcznych, a więc być może będą ich potrzebować. Nie ma sposobu poinformowania, czy któryś z procesorów rzeczywiście będzie tych danych potrzebował, zatem na wszelki wypadek wszystkie procesory otrzymują wszystko, co tylko się zmieniło. Choć przenoszenie tym sposobem wszystkich danych jest proste, na ogół jest też mało wydajne. W leniwej spójności zwalniania w chwili zwalniania nie posyła się nigdzie niczego. W zamian procesor. próbujący dokonać nabycia musi pobrać większość najnowszych wartości zmiennych od przechowującej je maszyny (lub maszyn). W celu określenia, które dane należy przetransrnitować, można zastosować protokół ze znacznikami czasu.

W wielu programach sekcje krytyczne występują wewnątrz pętli. W przypadku pilnej spójności zwalniania podczas każdego przejścia przez pętlę dokonuje się zwolnień, a zmodyfikowane dane muszą być przenoszone do wszystkich procesorów utrzymujących ich kopie. Taki algorytm marnuje przepustowość i wprowadza niepotrzebne opóźnienia. Stosując leniwą spójność zwalniania, przy zwalnianiu nie robi się niczego. Przy następnym nabywaniu procesor stwierdza, że ma już wszystkie potrzebne dane, więc również tutaj nie powstają żadne komunikaty. Sieciowym rezultatem zastosowania leniwej spójności zwalniania jest niewytwarzanie żadnego ruchu w sieci dopóty, dopóki inny procesor nie zechce czegoś nabyć. Powtarzanie operacji nabycie-zwolnienie przez ten sam procesor, gdy nie ma rywalizacji z zewnątrz, przebiega swobodnie.

3.7. Spójność wejścia

Jeszcze innym modelem spójności zaprojektowanym do wykorzystania w sekcjach krytycznych jest spójność wejścia (ang. entry consistency). Podobnie jak oba warianty spójności zwalniania wymaga ona od programisty (lub kompilatora) posługiwania się operacją nabywania i zwalniania odpowiednio na początku i końcu każdej sekcji krytycznej. Jednak w odróżnieniu od spójności zwalniania, spójność wejścia wymaga, aby każda zwykła zmienna dzielona została skojarzona ze zmienną synchronizującą, taką jak zamek lub zapora. Jeżeli zachodzi potrzeba niezależnego, równoległego dostępu do elementów tablicy, to różnym elementom tablicy muszą odpowiadać różne zamki. Po nabyciu zmiennej synchronizującej zapewnia się spójność tylko tym zwykłym zmiennym dzielonym, które są strzeżone przez taką zmienną synchronizującą. Spójność wejścia różni się od leniwej spójności zwalniania tym, że ta ostatnia nie kojarzy zmiennych dzielonych z zamkami ani zaporami i podczas nabywania trzeba doświadczalnie określać, które zmienne są potrzebne.

Skojarzenie z każdą zmienną synchronizującą listy zmiennych dzielonych zmniejsza koszt powodowany przez nabywanie i zwalnianie zmiennych synchronizujących, ponieważ synchronizacji podlega niewiele zmiennych dzielonych. Umożliwia to również jednoczesne wykonywanie wielu sekcji krytycznych z rozłącznymi zmiennymi dzielonymi, co zwiększa stopień równoległości działań. Płaconą za to cena są dodatkowe koszty i złożoność kojarzenia każdej zmiennej i danej dzielonej z pewną zmienną synchronizującą. Programowanie tą metodą jest również bardziej skomplikowane i podatne na błędy. Zmiennych synchronizujących używa się w następujący sposób. Każda zmienna synchronizująca ma bieżącego właściciela, a mianowicie proces, który ją ostatnio nabył. Właściciel może cyklicznie wchodzić i wychodzić z sekcji krytycznych, bez wysyłania siecią jakichkolwiek komunikatów. Proces nie posiadający aktualnie zmiennej synchronizującej, lecz chcący ją nabyć, musi wysłać komunikat do bieżącego właściciela z prośby o nadanie prawa własności skojarzonych zmiennych i udostępnienie ich bieżących wartości. Jest również możliwe, aby kilka procesów jednocześnie miało zmienną synchronizującą w trybie nie wyłączającym, co oznacza, że mogą one czytać skojarzone z nią zmienne z danymi, lecz nie mogą ich zapisywać. W pojęciu formalnym pamięć przejawia spójność wejścia, jeśli spełnia następujące warunki:

Nabycie zmiennej synchronizującej nie może w procesie nastąpić dopóty, dopóki nie zostaną w nim wykonane wszystkie aktualizacje strzeżonych danych dzielonych procesu.

Zanim zezwoli się na wyłączny dostęp do zmiennej synchronizującej w procesie, należy zagwarantować, że żaden inny proces nie będzie utrzymywał tej zmiennej - nawet w trybie nie wyłączającym.

Po wykonaniu wyłącznego dostępu do zmiennej synchronizującej żaden inny proces nie może wykonać do niej nie wyłączającego dostępu bez uzgodnienia tego z właścicielem zmiennej.

Pierwszy warunek oznacza, że gdy proces ubiega się o nabycie, to może się ono nie zakończyć (tj. nie nastąpi zwrot sterowania do następnej instrukcji) do czasu, aż wszystkie strzeżone zmienne dzielone zostaną zaktualizowane. Innymi słowy, przy nabywaniu wszystkie zdalne zmiany strzeżonych danych muszą stać się widoczne. Drugi warunek oznacza, że przed uaktualnieniem zmiennej dzielonej proces musi wejść do sekcji krytycznej w trybie wyłączającym, aby zagwarantować, że żaden inny proces nie będzie próbował zaktualizować jej w tym samym czasie. Ostatni warunek oznacza, że jeśli proces chce wejść do sekcji krytycznej w trybie nie wyłączającym, to pobranie najnowszych kopii strzeżonych zmiennych dzielonych musi skonsultować z właścicielem zmiennej synchronizującej, która strzeże sekcji krytycznej.

3.8. Podsumowanie modeli spójności

Wszystkie przedstawione modele spójności różnią się stopniem wprowadzanych ograniczeń, złożonością implementacji, łatwością programowania oraz efektywnością działania (TAB.3.). Najwięcej ograniczeń wprowadza spójność ścisła, lecz ze względu na to, że jej realizacja w systemie DSM jest w zasadzie niemożliwa - nie używa się jej nigdy. Spójność sekwencyjną daje się urzeczywistnić, jest ona popularna wśród programistów i szeroko stosowana. Istnieje jednak problem z nią związany mała wydajność. Środkiem zaradczym jest tutaj osłabienie spójności. Spójności: przyczynowa, procesorowa oraz PRAM są modelami spójności, w których nie obowiązuje już globalna zgoda co do kolejności występowania operacji. Różne procesy mogą oglądać różne ciągi działań. Wymienione trzy spójności różnią się pod względem dopuszczalnych ciągów operacji, natomiast we wszystkich przypadkach programista musi zważać, aby nie robić rzeczy dozwolonych tylko w przypadku pamięci spójnej sekwencyjnie.

Spójność	Opis	Operacje synchronizujące
Ścisła	Absolutne uporządkowanie czasowe wszystkich spraw dotyczących dzielonych dostępów	nie
Sekwencyjna	Wszystkie procesy oglądają wszystkie dzielone dostępy w tym samym porządku	nie
Przyczynowa	Wszystkie procesy oglądają w tym samym porządku dostępy dzielone, powiązane przyczynowo	nie
PRAM	Wszystkie procesy widzą operacje zapisu każdego procesora w tym samym porządku, w jakim zostały wydane. Operacje zapisu pochodzące z różnych procesorów mogą nie być zawsze widoczne w tym samym porządku	nie
Procesorowa	Spójność PRAM + zgodność pamięci	nie
Słaba	Dane dzielone można uważać za spójne tylko po wykonaniu synchronizacji	tak
Zwalniania	Dane dzielone stają się spójne po wyjściu z sekcji krytycznej	tak
Wejścia	Dane dzielone z sekcji krytycznej stają się spójne po wejściu do sekcji krytycznej	tak

Tab. 3. Porównanie modeli spójności.

Inne podejście polega na wprowadzeniu jawnych zmiennych synchronizujących jako spójności słabej, spójności zwalniania i spójności wejścia. Jeżeli proces działa na zwykłych zmiennych dzielonych, to nie ma pewności, kiedy będą one widoczne dla innych procesów. Zmiany są przenoszone tylko w wyniku dostępu do zmiennej synchronizującej. Te trzy modele różnią się sposobami działania synchronizacji, lecz we wszystkich przypadkach proces może wykonać wiele operacji czytania i zapisywania w sekcji krytycznej bez wywoływania ruchu danych. Po zakończeniu wykonywania sekcji krytycznej końcowy wynik przenosi się do innych procesów lub czyni gotowym do przeniesienia. Spójność słaba, spójność zwalniania oraz spójność wejścia wymagają dodatkowych konstrukcji programowych, które - używane zgodnie z regułami - pozwalają uważać pamięć za spójna sekwencyjnie, podczas gdy w rzeczywistości taką nie jest. Te trzy modele, używające jawnych synchronizacji, powinny zasadniczo zapewniać najlepsze działanie, lecz może się zdarzyć, że różne zastosowania dadzą zupełnie różne rezultaty.

 

Rozproszona pamięć dzielona

Systemy te stanowią nadbudowę multikomputerów tj. procesorów połączonych za pomocą specjalizowanych sieci przekazywania komunikatów stacji roboczych w sieciach lokalnych lub podobnych projektów. Istotnym elementem jest tu niemożność bezpośredniego dostępu dowolnego procesora do jakiegokolwiek innego procesora. Systemy takie nazywa się niekiedy NORMA (ang. NO Remote Memory Access - brak dostępu do pamięci zdalnej), aby odróżnić je od systemów NUMA.

Największa różnica między systemami NUMA i NORMA jest taka, że w tych pierwszych każdy procesor może bezpośrednio odwołać się do dowolnego słowa globalnej przestrzeni adresowej - po prostu czytając je lub zapisując. Strony mogą być rozmieszczone losowo w różnych pamięciach, co nie wpływa na wyniki działania programów. Gdy procesor zwraca się do zdalnej strony, system ma możliwość wyboru między jej sprowadzeniem a zdalnym użyciem. Decyzja ta wpływa na sprawność, ale nie zależy od niej poprawność. Stacje robocze w sieciach lokalnych zasadniczo różnią się od wieloprocesorów. Procesory mają dostęp tylko do własnych, lokalnych pamięci. Nie istnieje pojęcie globalnej pamięci dzielonej, jak w wieloprocesorach NUMA lub UMA. Celem systemu rozproszonej pamięci dzielonej (DSM) jest wszakże umożliwienie za pomocą środków programowych wykonywania programów wieloprocesorowych na multikomputerach. Tak więc, jeżeli procesor odwoła się do jakiejś zdalnej strony, to musi ona być mu dostarczona.

Ponieważ w programach napisanych dla wieloprocesorów na ogół zakłada się spójność sekwencyjną pamięci, we wstępnych pracach nad systemami DSM starannie zadbano, aby zapewnić spójność sekwencyjną pamięci, dzięki czemu stare programy wieloprocesorowe mogą działać bez modyfikacji. Dalsze doświadczenia wykazały, że znaczne polepszenie działania można osiągnąć w drodze osłabiania spójności pamięci za cenę przeprogramowania istniejących zastosowań oraz pisania nowych, w odmiennym stylu.

4.1. Stronicowana rozproszona pamięć dzielona

Pomysł na system rozproszonej pamięci dzielonej (DSM) jest prosty - należy emulować pamięć podręczną wieloprocesora za pomocą jednostki zarządzania pamięcią (MMU) i oprogramowania systemu operacyjnego. W systemie DSM przestrzeń adresowa dzieli się na kawałki rozprzestrzenione po wszystkich procesorach. Gdy procesor odwołuje się do adresu nielokalnego, następuje przejście do systemu i oprogramowanie DSM sprowadza kawałek pamięci, który zawiera potrzebny adres, po czym wznawia niedokończoną instrukcję i wykonuje ją do końca poprawnie (RYS.9a.).

Rys. 9. Stronicowana rozproszona pamięć dzielona:
a) kawałki przestrzeni adresowej rozmieszczone w czterech maszynach,
b) sytuacja po odwołaniu się przez procesor 1 do kawałka 10,
c) kawałek 10 jest przeznaczony tylko do czytania i zastosowano zwielokrotnianie.

Jeżeli w tym przykładzie procesor l odwoła się do instrukcji lub danych zawartych w kawałkach 0, 2, 5 lub 9, to odwołania zostaną wykonane lokalnie. Odwołania do innych kawałków powodują przejście do systemu. Na przykład odwołanie do adresu w kawałku 10 spowoduje przejście do oprogramowania systemu DSM, które przemieści kawałek 10 z maszyny 2 do maszyny l (RYS.9b.).

Zwielokrotnianie

Ulepszeniem podstawowego systemu, które może znacznie poprawić jego sprawność, jest zwielokrotnienie kawałków przeznaczonych tylko do czytania, na przykład wznawialnego kodu programu, stałych i innych struktur danych tego rodzaju. Na przykład, jeśli kawałek 10 (RYS.9.) jest modułem wznawialnego kodu programu, to jego wykorzystanie przez procesor l może spowodować przesłanie do procesora l kopii bez naruszania zawartości oryginału w pamięci procesora 2 (RYS.9c.). Dzięki temu zarówno procesor l, jak i 2 mogą odwoływać się do kawałka 10 tak często, jak tego potrzebują, nie powodując konieczności sprowadzania brakujących fragmentów pamięci.

Inna możliwość polega na zwielokrotnianiu wszystkich kawałków, a nie tylko kawałków przeznaczonych do czytania. Dopóki wykonuje się czytanie, dopóty nie ma różnicy między zwielokrotnieniem kawałka przeznaczonego tylko do czytania a zwielokrotnieniem kawałka służącego do odczytu i zapisu. Jednak gdy zwielokrotniony kawałek zostanie nagle zmodyfikowany, to trzeba będzie podjąć specjalne działania, aby zapobiec powstawaniu wielu niespójnych kopii.

Ziarnistość

Systemy DSM pod kilkoma zasadniczymi względami są podobne do wieloprocesorów. W obu rodzajach systemów odwołanie do słowa z nielokalnej pamięci powoduje sprowadzenie kawałka pamięci zawierającego to słowo z jego bieżącego miejsca pobytu do maszyny wykonującej odwołanie (jej pamięci operacyjnej lub podręcznej - stosownie do potrzeb). Ważnym zagadnieniem projektowym jest ustalenie wielkości takiego kawałka. Można brać tu pod uwagę słowo, blok (kilka słów), stronę lub segment (wiele stron). Jeżeli proces odwołuje się do nieobecnego słowa, to skutkiem jest błąd-brak strony. Oczywistym wyborem jest sprowadzenie całej potrzebnej strony.

Innym możliwym wyborem jest natomiast sprowadzenie większej jednostki - obszaru złożonego z 2, 4 lub 8 stron, zawierającego potrzebną stronę. Takie postępowanie symuluje większy rozmiar strony. Większe rozmiary kawałków rozproszonej pamięci dzielonej mają swoje zalety i wady. Największa zaleta wynika z tego, że przygotowanie do transmisji poprzez sieć zajmuje sporo czasu. Dzięki przesyłaniu danych w dużych porcjach można często zaoszczędzić na liczbie transmisji przy przemieszczaniu wielkich fragmentów przestrzeni adresowej. Jest to ważne szczególnie z tego powodu, że wiele programów przejawia lokalność odwołań, co oznacza, że jeśli program skorzystał z jakiegoś słowa na stronie, to prawdopodobnie w najbliższej przyszłości odwoła się do innych słów na tej samej stronie.

Z drugiej strony, długie transmisje wiążą sieć na dłużej, co blokuje zgłoszenia braków stron innych procesów. Zbyt duży efektywny rozmiar strony wprowadza nowy problem zwany "fałszywym dzieleniem" (ang. false sharing), istnieć więc może np. strona zawierająca dwie nie związane ze sobą zmienne A i B (RYS.10.). Procesor l używa intensywnie zmiennej A, czytając ją i zapisując. Procesor 2 podobnie używa zmiennej B. W tych warunkach strona zawierająca obie zmienne będzie ustawicznie podróżować tam i z powrotem od jednej maszyny do drugiej. Problem polega na tym, że choć zmienne nie są ze sobą związane, to wskutek ich przypadkowego wystąpienia na tej samej stronie użycie przez pewien proces jednej z nich powoduje również zabranie drugiej. Im większy efektywny rozmiar strony, tym częściej może pojawiać się fałszywe dzielenie.

Rys. 10. Fałszywe dzielenie strony zawierającej dwie nie związane ze sobą zmienne.

Osiąganie spójności sekwencyjnej

Jeśli strony nie są zwielokrotniane, to problem osiągania spójności nie istnieje. Każda strona występuje dokładnie w jednym egzemplarzu i jest przemieszczana gdzie trzeba, stosownie do potrzeb. Zwielokrotnienie stron przeznaczonych tylko do czytania również nie powoduje kłopotów. Strony takie nigdy nie są zmieniane, więc wszystkie kopie są zawsze takie same. Strony do czytania i zapisywania utrzymuje się w pojedynczych egzemplarzach, więc również one nie mogą stać się przyczyną niespójności. W wielu systemach DSM próba przeczytania przez proces zdalnej strony powoduje utworzenie lokalnej kopii, ponieważ system nie wie, co znajduje się na strome lub czy jest ona do zapisywania.. Dopóki wszystkie odwołania są operacjami czytania, dopóty wszystko jest w porządku. Jednak gdy jakikolwiek proces spróbuje zapisać zwielokrotnioną stronę, powstaje problem ewentualnej niespójności, gdyż zmiana jednej kopii i pozostawienie innych swojemu losowi jest nie do przyjęcia.

Ogólnie biorąc, w wieloprocesorach stosuje się dwa podejścia: aktualizowanie i unieważnianie. Przy aktualizowaniu dopuszcza się lokalne zapisy, lecz w tej samej chwili adres oraz nowa wartość zmodyfikowanego słowa zostają rozgłoszone wszystkim innym pamięciom podręcznym. Każda z pamięci podręcznych, przechowująca słowo o danym adresie, spostrzegłszy jego zmianę, aktualizuje je, zastępując starą wartość nową, pobraną z szyny. W efekcie wszystkie pamięci podręczne, które przechowywały słowo przed jego aktualizacją, przechowują je również potem, nabywając nową jego wartość.

Wieloprocesory mogą także dokonywać unieważnień. Strategia ta polega na rozgłaszaniu w szynie samego adresu aktualizowanego słowa bez jego nowej wartości. Jeśli pamięć podręczna stwierdzi. że któreś z jej słów podlega aktualizacji, to unieważnia swój blok zawierający to słowo, co jest równoznaczne z jego usunięciem. W efekcie doprowadza się do tego, że tylko jedna pamięć podręczna przechowuje zmodyfikowane słowo, dzięki czemu unika się problemu spójności. Jeżeli któryś z procesorów obecnie utrzymujących unieważnioną kopię bloku pamięci podręcznej spróbuje go użyć, to dostanie sygnał o braku danych w pamięci podręcznej i sprowadzi blok z procesora, który przechowuje ważną kopię. Podczas wykonywania programu stan strony może się zmieniać. W dowolnej chwili może być ona w stanie R (zdatna do czytania) albo w stanie W (zdatna do czytania i zapisu). Każda strona ma właściciela, tj. proces, który ostatnio ją zapisywał. Gdy strona jest w stanie W, wówczas istnieje tylko jedna jej kopia, odwzorowana w przestrzeni adresowej właściciela w trybie pisanie-czytanie. Kopia strony w stanie R znajduje się u właściciela (odwzorowana jako zdatna tylko do czytania), lecz mogą ją mieć także inne procesy.

Odnajdywanie właściciela

Najprostsze rozwiązanie polega na ogłoszeniu komunikatu z prośbą o zgłoszenie się właściciela. Oczywiście najkorzystniej byłoby, aby nie tylko prosić o zgłoszenie się właściciela, lecz również przekazać wiadomość, czy nadawca chce czytać, czy pisać oraz czy potrzebuje kopii strony. Właściciel może wówczas w jednym komunikacie przekazać w razie potrzeby prawo własności oraz samą stronę.

Wadą rozgłaszania jest powodowanie przerwań na wszystkich procesorach, co zmusza je do sprawdzania pakietu z zamówieniem. Z wyjątkiem właściciela obsługa takiego przerwania jest dla wszystkich pozostałych procesorów marnowaniem czasu. Rozgłaszanie może zużywać znaczną część szerokości pasma sieci, zależnie od sprzętu.

Istnieje wiele innych możliwości. W jednej z nich jeden proces zostaje wyznaczony do funkcji zarządcy stron. Do jego zadań należy pamiętanie, kto jest właścicielem każdej ze stron. Jeżeli proces P chce czytać stronę, której nie ma, lub zapisywać stronę, której nie jest właścicielem, to wysyła komunikat do zarządcy stron, informując go, jaką chce wykonać operację i na której stronie. Zarządca odsyła mu w odpowiedzi informację o tym, kto jest właścicielem strony. Wówczas proces P kontaktuje się z właścicielem w celu pobrania strony i - stosownie do potrzeb - prawa własności. Protokół taki wymaga czterech komunikatów. W przypadku optymalizacji tego lokalizowania prawa własności (RYS.11.), zarządca stron kieruje tu zamówienie bezpośrednio do właściciela, który odpowiada wtedy bezpośrednio procesowi P, przez co oszczędza się na jednym komunikacie. Problemem w tym protokole jest zakładane duże obciążenie zarządcy stron, który obsługuje wszystkie nadchodzące komunikaty. Trudność tę można zmniejszyć, posługując się kilkoma zarządcami stron zamiast jednym.

Rys. 11. Lokalizowanie prawa własności za pomocą centralnego zarządcy:
a) protokół czterokomunikatowy, b) protokół trzykomunikatowy.

Istnieje także inny algorytm polegający na utrzymywaniu przez każdy proces informacji o prawdopodobnym właścicielu każdej strony. Zamówienia praw własności są kierowane do prawdopodobnego właściciela, który przekazuje je dalej, jeśli właściciel się zmienił. Jeśli właściciel zmienił się kilkakrotnie, to komunikat z zamówieniem musi zostać przesłany również kilkakrotnie. Na początku wykonania programu i po każdych n zmianach własności należy ogłosić położenie nowego właściciela, aby umożliwić wszystkim procesom zaktualizowanie tablic prawdopodobnych właścicieli.

Odnajdywanie kopii

Innym ważnym szczegółem jest odnalezienie wszystkich kopii, które należy unieważnić. Istnieją kilka możliwości. Pierwszą z nich jest ogłoszenie komunikatu podającego numer strony i proszącego wszystkie procesory utrzymujące stronę o tym numerze o jej unieważnienie. Można to zastosować tylko wówczas, gdy wszystkie komunikaty są przesyłane niezawodnie i nigdy nie giną.

Druga możliwość polega na utrzymywaniu przez właściciela lub zarządcę stron wykazu lub zbioru kopii (ang. copyset) określającego, które procesory przechowują które strony (RYS.12.). Na przykład strona 4 jest tutaj własnością procesu z jednostki centralnej l, co uwidoczniono za pomocą podwójnej ramki wokół cyfry 4. Zbiór kopii składa się z liczb 2 i 4, ponieważ kopie strony 4 można odnaleźć na maszynach o tych numerach.

Rys. 12. Właściciel każdej strony utrzymuje zbiór kopii określający,
które z innych jednostek centralnych przechowują daną stronę.

Gdy zajdzie konieczność unieważnienia strony, stary właściciel, nowy właściciel lub zarządca strony wysyła komunikat do każdego procesora przechowującego tę stronę i czeka na jego potwierdzenie. Po potwierdzeniu wszystkich komunikatów unieważnienie jest zakończone.

Zastępowanie stron

W systemie DSM, jak w każdym systemie z pamięcią wirtualną, może się zdarzyć, że w pamięci brakuje wolnej ramki na przechowanie potrzebnej strony. W celu zrobienia dla niej miejsca należy w takiej sytuacji wyrzucić jakąś stronę. Rodzi to natychmiast dwa podproblemy: którą stronę wyeksmitować i dokąd. Wyboru strony do wyrzucenia można w większości przypadków dokonać za pomocą tradycyjnych algorytmów pamięci wirtualnej, zbliżonych do algorytmu najdawniej używanych stron (LRU). W systemie rozproszonej pamięci dzielonej (DSM) utrudnieniem są wystąpienia spontanicznych unieważnień stron (będących wynikiem działania innych procesów). Podobnie jak w konwencjonalnych algorytmach, warto utrzymywać informacje o "czystości" lub "zabrudzeniu" stron. W kontekście systemu DSM zawsze pierwsza do usunięcia jest strona zwielokrotniona, będąca własnością innego procesu, ponieważ wiadomo, że istnieje jej kopia. Jeżeli do utrzymywania informacji o kopiach używa się schematu katalogowego, to właściciel lub zarządca stron musi być o tym poinformowany. Jeżeli strony lokalizuje się za pomocą rozgłaszania, to stronę można po prostu usunąć. Drugą bardzo dobrą możliwością wyboru strony do wyeksmitowania jest wytypowanie zwielokrotnionej strony będącej własnością wyrzucającego procesu. Wystarczy przekazać prawo własności jednej z innych kopii, informując o tym dany proces, zarządcę stron lub obu - zależnie od implementacji. Nie trzeba przenosić samej strony i dzięki temu komunikat jest krótszy. Jeżeli nie można wybrać odpowiedniej kandydatki spośród stron zwielokrotnionych, to trzeba dokonać wyboru strony nie zwielokrotnionej, na przykład najdawniej używanej i ważnej. Można się jej pozbyć dwoma sposobami. Pierwszy polega na zapisaniu jej na dysku, jeśli taki istnieje. Drugi sposób polega na przekazaniu strony innemu procesorowi.

Synchronizacja

Podobnie jak w wieloprocesorze, w systemie DSM procesy wymagają często synchronizowania działań. Typowym przykładem jest wzajemne wyłączanie, przy którym w danym czasie tylko jeden proces może wykonywać pewien fragment kodu. W wieloprocesorze do realizowania wzajemnego wyłączania używa się często instrukcji TSL (ang. test-and-set-lock). W systemie DSM kod taki jest nadal poprawny, lecz grozi dotkliwym spadkiem wydajności. Jeśli jakiś proces A znajduje się w sekcji krytycznej i inny proces B (na innej maszynie) chce do niej wejść, to B zaczyna powtarzać ciasną pętlę testowania zmiennej, czekając na jej wyzerowanie. Strona zawierająca tę zmienną pozostaje w maszynie procesu B. Gdy proces A wyjdzie z sekcji krytycznej i spróbuje zapisać 0 pod zmienną, napotka brak strony i sprowadzi stronę zawierającą tę zmienną. Momentalnie w procesie B również powstanie brak strony, co pociągnie za sobą sprowadzenie strony z powrotem. Problem powstaje wówczas, gdy kilka innych procesów chce także wejść do sekcji krytycznej. Instrukcja TSL zmienia pamięć (zapisując wartość l w zmiennej synchronizującej) przy każdym wykonaniu. Zatem za każdym razem, gdy proces wykonuje instrukcję TSL, musi nastąpić pobranie całej strony zawierającej zmienną synchronizującą, gdziekolwiek by się ona znajdowała. Gdy wiele procesów wykonuje instrukcję TSL co kilkaset nanosekund, ruch w sieci może stać się nie do zniesienia. Z tego powodu synchronizacja wymaga często dodatkowego mechanizmu. Jedną możliwością jest zarządca synchronizacji (lub zarządcy), akceptujący komunikaty z prośbami o wejście i wyjście z sekcji krytycznych, zajmowanie i zwalnianie zmiennych itd. oraz odsyłający odpowiedzi po wykonaniu zadania. Jeśli wejście do sekcji nie jest możliwe lub zmiennej nie można wynająć, to nie następuje natychmiastowe wysłanie odpowiedzi, co powoduje blokowanie się nadawcy. Gdy sekcja staje się dostępna lub zmienna może zostać wynajęta, wysyła się komunikat. W ten sposób można dokonywać synchronizacji przy minimalnym ruchu w sieci, lecz za cenę scentralizowanej kontroli wynajmów.

4.2. Rozproszona pamięć dzielona ze zmiennymi dzielonymi

Stronicowana, rozproszona pamięć dzielona stanowi zwykłą liniową przestrzeń adresową i umożliwia dynamiczną wędrówkę stron poprzez sieć, dokonywaną na żądanie. Procesy mają dostęp do całej pamięci za pomocą zwykłych instrukcji czytania i pisania i nie są świadome występowania braków stron lub transmisji sieciowych. Dostępy do zdalnych danych są wykrywane i przejmowane przez jednostkę zarządzania pamięcią (MMU). Podejściem bardziej strukturalnym jest dzielenie tylko poszczególnych zmiennych i struktur danych potrzebnych w więcej niż jednym procesie. Wskutek tego zamiast problemu stronicowania za pośrednictwem sieci pojawia się pytanie o utrzymywanie zwielokrotnionej, rozproszonej bazy danych złożonej ze zmiennych dzielonych. Można tu zastosować różne techniki, często znacznie usprawniające działanie. Jeśli zwielokrotnia się zmienne dzielone, to zakładając wyizolowanie zapisów poszczególnych zmiennych dzielonych, zyskuje się więcej możliwości użytkowania algorytmu aktualizacji niż w stronicowanym systemie DSM. Użytkowanie osobno zarządzanych zmiennych dzielonych tworzy też sprzyjające warunki do eliminowania fałszywego dzielenia. Jeśli można uaktualnić pewną zmienną bez oddziaływania na inne zmienne, to fizyczne rozmieszczanie zmiennych na stronach staje się mniej ważne.

System Munin

Munin jest systemem rozproszonej pamięci dzielonej opartym na obiektach programowych, z których każdy może być umieszczony na osobnej stronie, więc do wykrywania dostępów do obiektów dzielonych można wykorzystać sprzętową jednostkę zarządzania pamięcią. Podstawowy model zastosowany w systemie Munin składa się z wielu procesorów, a każdy z nich jest wyposażony w stronicowaną, liniową przestrzeń adresową, w której jeden lub więcej wątków wykonuje nieco zmodyfikowany program wieloprocesorowy. W projekcie systemu Munin przyjęto za cel, aby po wykonaniu niewielkich adaptacji można było wydajnie wykonywać istniejące programy wieloprocesorowe w systemach multikomputerowych przy użyciu pewnej formy rozproszonej pamięci dzielonej. Dobre działanie osiąga się za pomocą rozmaitych technik. W celu wykonania programu na jednym z procesorów rozpoczyna działanie proces główny. Proces ten może generować nowe procesy na innych procesorach, które odtąd działają równolegle z procesem głównym, komunikując się z nim i między sobą za pomocą zmiennych dzielonych, tak jak to robią zwykłe programy wieloprocesorowe. Proces raz rozpoczęty na pewnym procesorze nie może być z niego przeniesiony.

Zmienne dzielone są osiągalne za pomocą zwykłych instrukcji czytania i pisania z listy rozkazów jednostki centralnej. Nie stosuje się żadnych specjalnych metod ochrony. Próba użycia nieobecnej zmiennej dzielonej powoduje wystąpienie błędu braku strony i przejęcie sterowania przez system Munin.

Synchronizacja wzajemnego wyłączania jest wykonywana w specjalny sposób, pozostający w ścisłym związku z modelem spójności pamięci. Można deklarować zmienne zamykające, jak również korzystać z bibliotecznych procedur ich domykania (zajmowania) i otwierania. Istnieje również możliwość wykorzystania zapór, zmiennych warunkowych i innych zmiennych synchronizujących.

Spójność zwalniania

System Munin jest oparty na programowej realizacji (pilnej) spójności zwalniania. System Munin dostarcza użytkownikom narzędzi strukturalizacji programów wokół sekcji krytycznych, definiowanych dynamicznie za pomocą wywołań operacji nabywania (wejścia) i zwalniania (wyjścia). Zapisywanie zmiennych dzielonych musi występować wewnątrz sekcji krytycznych; czytanie może występować wewnątrz lub na zewnątrz. Gdy proces działa w sekcji krytycznej, system nie daje żadnych gwarancji odnośnie do spójności zmiennych dzielonych, lecz przy wyjściu z sekcji krytycznej zmienne dzielone, zmodyfikowane od czasu ostatniego zwolnienia, zostają uaktualnione na wszystkich maszynach. W programach przestrzegających takiego modelu programowania rozproszona pamięć dzielona zachowuje się jak pamięć spójna sekwencyjnie.

System Munin wyróżnia trzy klasy zmiennych:

zmienne zwykłe,

zmienne z danymi dzielonymi,

zmienne synchronizujące.

Zmienne zwykłe nie są dzielone i mogą być czytane i zapisywane tylko przez proces, który je utworzył. Zmienne z danymi dzielonymi są widoczne dla wielu procesów jako sekwencyjnie spójne, pod warunkiem że wszystkie procesy używają ich tylko w sekcjach krytycznych. Zmienne synchronizujące, takie jak zamki i zapory, należą do specjalnej kategorii i są dostępne tylko za pomocą procedur zawartych w systemie. Procedury te są odpowiedzialne za działanie rozproszonej pamięci dzielonej.

Zasadę działania spójności zwalniania w systemie Munin można zobrazować w prosty sposób np. dla trzech współpracujących procesów wykonywanych na różnych maszynach (RYS.13.). W pewnej chwili proces l chce wejść do krytycznego fragmentu kodu chronionego przez zamek Z (wszystkie sekcje krytyczne muszą być chronione przez jakąś zmienną synchronizującą). Instrukcja zamknij zapewnia, że żaden inny, poprawnie się zachowujący proces nie będzie wykonywał obecnie tej sekcji krytycznej. Trzy dzielone zmienne a, b i c są wtedy dostępne za pomocą zwykłych instrukcji maszynowych. Na koniec wywołuje się operację otwórz i wyniki zostają przekazane do wszystkich maszyn utrzymujących kopie zmiennych a, b i c. Zmiany są upakowywane w minimalną liczbę komunikatów. Sięganie po te zmienne na innych maszynach podczas przebywania procesu l w sekcji krytycznej powoduje nieokreślone wyniki.

Rys. 13. Spójność zwalniania w systemie Munin.

Wielość protokołów

Oprócz spójności zwalniania w systemie Munin zastosowano inne techniki poprawiające działanie. Główna z nich polega na umożliwieniu programiście zaliczenia deklaracji zmiennych dzielonych do jednej z czterech następujących kategorii:

tylko do czytania,

wędrowna,

dzielony zapis,

konwencjonalna.

Każda maszyna utrzymuje katalog z wykazem wszystkich zmiennych, zawierający m.in. kategorię, do której należy każda z nich. Dla każdej kategorii używa się odmiennego protokołu. Odwołanie do zmiennej tylko do czytania powoduje błąd braku strony, system Munin poszukuje jej w katalogach zmiennych, odnajduje jej właściciela i prosi go o kopię wymaganej strony. Ponieważ strony ze zmiennymi przeznaczonymi tylko do czytania nie ulegają zmianom (po nadaniu im początkowych wartości), nie ma problemów ze spójnością. Zmienne przeznaczone tylko do czytania są chronione przez sprzętową jednostkę MMU. Próba zapisania którejś z nich spowoduje nieusuwalny błąd.

Do wędrownych zmiennych dzielonych używa się protokołu nabywania i zwalniania. Są one stosowane w sekcjach krytycznych i należy je chronić za pomocą zmiennych synchronizujących. Pomysł polega na wędrówce tych zmiennych od maszyny do maszyny w ślad za rozpoczynanymi i kończonymi sekcjami krytycznymi. Nie są one zwielokrotniane. Zmienną do dzielonego zapisu stosuje się wtedy, gdy programista zaznaczy, że może ona być bezpiecznie zapisywana w tym samym czasie przez dwa procesy (lub więcej) - jak w przypadku tablicy, w której różne procesy mogą współbieżnie działać na różnych jej fragmentach. Początkowo strony zawierające zmienne do dzielonego zapisywania są oznaczane jako tylko do czytania, być może na kilku maszynach jednocześnie. Kiedy nastąpi pisanie, procedura obsługi błędu tworzy kopię strony zwaną stroną bliźniaczą (ang. twin), zaznacza stronę jako zabrudzoną i ustawia jednostkę MMU tak, aby umożliwić dalsze zapisy. Po dokonaniu zwolnienia system Munin porównuje każdą zabrudzoną stronę dzielonego zapisu z jej bliźniaczką słowo po słowie i posyła wykaz różnic (wraz ze wszystkimi stronami wędrownymi) do wszystkich procesów, którym są potrzebne te dane. Następnie przywraca ochronę strony jako przeznaczonej tylko do czytania.

Proces odbierający wykaz różnic sprawdza każdą stronę, czy także ją zmodyfikował. Jeśli strona nie została zmodyfikowana, to akceptuje się nadchodzące zmiany. Jeśli jednak strona została lokalnie zmodyfikowana, to lokalna kopia, jej bliźniaczką oraz odpowiednia strona nadchodząca zostają porównane słowo po słowie. Jeśli słowo zmodyfikowano lokalnie, ale nadchodzące słowo nie uległo zmianie, to przesłane słowo zastępuje słowo lokalne. Jeśli zarówno słowo lokalne, jak i nadchodzące uległy modyfikacji, to sygnalizuje się błąd wykonania. Gdy nie ma takich sprzeczności, lokalna strona zostaje zastąpiona połączoną i wykonywanie jest kontynuowane.

Zmienne dzielone nie zaopatrzone w adnotacje odnośnie do ich przynależności do którejś z powyższych kategorii są traktowane jak w konwencjonalnych, stronicowanych systemach rozproszonej pamięci dzielonej: dopuszcza się tylko jedną kopię każdej strony tylko do pisania i przemieszcza ją od procesu do procesu na żądanie. Strony przeznaczone tylko do czytania są zwielokrotniane stosownie do potrzeb.

Synchronizacja

W celu zapewnienia synchronizacji w systemie Munin stosuje się koncepcję zamków, które zdają się wskazywać na ich scentralizowane działanie, jednak w rzeczywistości używa się implementacji rozproszonej, aby unikać zbytniego ruchu przesyłek do poszczególnych maszyn. Gdy proces chce nabyć zamek, sprawdza najpierw, czy sam nie jest jego właścicielem. Jeśli jest właścicielem zamka i zamek jest wolny, to nabycie dochodzi do skutku. Jeśli zamek jest wolny, to zezwala się na jego wykorzystanie. Jeśli jest zajęty, to zamawiający zostaje ustawiony na końcu kolejki. Dzięki temu każdy proces zna identyfikację procesu następującego po nim w kolejce. Po zwolnieniu zamka właściciel przekazuje go następnemu procesowi na liście.

Zapory realizuje się za pomocą centralnego serwera. Gdy zapora jest tworzona, otrzymuje licznik procesów, które muszą przy niej oczekiwać, zanim nastąpi zwolnienie ich wszystkich. Kiedy proces skończy pewną fazę obliczeń, wtedy może wysłać do serwera zapory komunikat z prośbą o dozór nad jego oczekiwaniem. Gdy zbierze się odpowiednia liczba procesów oczekujących, wtedy do każdego z nich zostanie wysłany komunikat uwalniający.

System Midway

Midway jest systemem rozproszonej pamięci dzielonej opartym na dzieleniu poszczególnych struktur danych. Pod pewnymi względami przypomina system Munin, lecz ma także sporo nowych właściwości. Jego zadaniem jest umożliwienie wykonywania na multikomputerach istniejących i nowych programów wieloprocesorowych przy niewielkich zmianach kodu.

Programy w systemie Midway to w zasadzie konwencjonalne programy wzbogacone przez programistę pewnymi uzupełniającymi informacjami. Do wyrażania równoległości programy w systemie Midway używają pakietu wątków C systemu Mach. Wątek może się rozwidlać w dwa lub więcej wątków. Wątki pochodne (dzieci) wykonują się równolegle z wątkiem rodzicielskim oraz ze sobą nawzajem, nie wykluczone, że na osobnych maszynach (tj. każdy wątek jako osobny proces). Wszystkie wątki dzielą tę samą, liniową przestrzeń adresową, która zawiera zarówno dane prywatne, jak i dane dzielone. Zadaniem systemu Midway jest utrzymywanie spójności zmiennych dzielonych

Spójność wejścia

System Midway realizuje spójność wejścia w następujący sposób. Aby sięgnąć do zmiennej dzielonej, proces zazwyczaj wchodzi do sekcji krytycznej, wywołując procedurę biblioteczną "zamknij" (ang. lock) ze zmienną zamykającą jako parametrem. Przy wywołaniu operacji "zamknij" system wsparcia Midway nabywa zamek i jednocześnie uaktualnia wszystkie związane z nim zmienne dzielone. Wykonanie tego może wymagać wysłania komunikatów do innych procesów w celu otrzymania najnowszych wartości. Po otrzymaniu wszystkich odpowiedzi następuje przekazanie zamka i proces rozpoczyna wykonanie sekcji krytycznej. Gdy proces zakończy działania w sekcji krytycznej, zwalnia zamek.

Aby zapewnić działanie spójności wejścia, system Midway wymaga, by programy miały trzy cechy nie występujące w programach wieloprocesorowych:

zmienne dzielone muszą być deklarowane za pomocą nowego słowa kluczowego shared,

każda zmienna dzielona musi być skojarzona z zamkiem lub zaporą,

dostęp do zmiennych dzielonych może się odbywać tylko w sekcjach krytycznych.

4.3. Rozproszona pamięć dzielona oprata na obiektach

W wielu językach programowania dane są zorganizowane w obiekty, pakiety, moduły lub inne struktury, z których każda istnieje niezależnie od innych. Jeżeli proces odwołuje się do części obiektu, to w wielu przypadkach będzie potrzebny cały obiekt, toteż sensowne staje się przenoszenie danych przez sieć w jednostkach będących obiektami, a nie stronami.

Podejście wyodrębniające dzielone zmienne, zastosowane w systemach Munin lub Midway, stanowi krok w kierunku organizowania pamięci dzielonej w sposób bardziej strukturalny, lecz jest to tylko pierwszy krok. W obu systemach programista musi dostarczać informacje o tym, które zmienne są dzielone, a które nie, jak również dotyczące protokołów w systemie Munin i powiązań w systemie Midway.

Obiekty

Obiekt (ang. object) jest zdefiniowaną przez programistę zamkniętą strukturą danych. Składa się on z danych wewnętrznych, czyli stanu obiektu (ang. objęct stałe), i oddziaływających na stan obiektu procedur zwanych metodami lub operacjami (ang. methods, operations). Aby mieć dostęp do stanu wewnętrznego lub móc na niego oddziaływać, program musi wywołać jedną z metod. Metoda może zmienić stan wewnętrzny, zwrócić go (lub jego część) albo oddziałać jeszcze inaczej. Nie jest dozwolony bezpośredni dostęp do stanu wewnętrznego. Ta cecha jest nazywana ukrywaniem informacji (ang. information hiding). Wymuszanie, by wszystkie odwołania do danych obiektu dokonywały się za pomocą metod, pomaga w nadawaniu programowi struktury modularnej. W rozproszonej pamięci dzielonej opartej na obiektach procesy na wielu maszynach dzielą abstrakcyjną przestrzeń wypełnioną dzielonymi obiektami (RYS.14.).

Rys. 14. W rozproszonej pamięci dzielonej opartej na obiektach procesy komunikują się przez wywołanie metod na obiektach dzielonych.

Odnajdywanie obiektów i zarządzanie nimi jest wykonywane automatycznie za pomocą systemu wsparcia działania programu. Każdy proces może wywoływać metody dowolnego obiektu niezależnie od swojego położenia i położenia obiektu. Zapoczątkowanie działania metody należy do zadań systemu operacyjnego i systemu wsparcia - niezależnie od miejsca pobytu procesu i obiektu. Ponieważ proces nie może bezpośrednio wnikać w stan wewnętrzny żadnego z dzielonych obiektów, powstają możliwości rozmaitych optymalizacji, nieosiągalnych (lub co najmniej znacznie trudniejszych) w stronicowanych systemach DSM. Dzięki ścisłej kontroli dostępu do stanu wewnętrznego można na przykład osłabić protokół spójności pamięci bez uświadamiania tego programiście.

Z chwilą zapadnięcia decyzji o strukturalizacji pamięci dzielonej w formie zbioru osobnych obiektów zamiast liniowej przestrzeni adresowej powstaje wiele innych kwestii wymagających rozstrzygnięcia. Być może jednym z najważniejszych jest problem zwielokrotniania obiektów. Jeżeli nie ma zwielokrotniania, to wszystkie dostępy do obiektu odbywają się z użyciem jedynej jego kopii, co jest proste, lecz powodować może słabe działanie. Pozwalając na wędrowanie obiektów między maszynami wedle potrzeb, można ograniczyć spadek wydajności przez przemieszczanie obiektów tam, gdzie się ich oczekuje. Zwielokrotnienie obiektów prowadzi z kolei do pytania, co należałoby zrobić, gdy nastąpi aktualizacja jednej z kopii. Jedna możliwość polega na unieważnieniu wszystkich pozostałych kopii, tak aby pozostała tylko kopia aktualna. Dodatkowe kopie można tworzyć potem, na żądanie i stosownie do potrzeb. Alternatywna możliwość polega na uaktualnieniu kopii zamiast ich unieważniania. Systemy DSM ze zmiennymi dzielonymi także stosują tę możliwość, natomiast w stronicowanych systemach DSM jedynym realnym wyborem jest unieważnianie. Obiektowe systemy rozproszonej pamięci dzielonej, podobnie jak systemy DSM ze zmiennymi dzielonymi, eliminują większość fałszywych dzieleń. Podsumowując, można stwierdzić, że rozproszona pamięć dzielona oparta na obiektach ma w porównaniu z innymi metodami trzy zalety:

jest bardziej modularna od innych technik,

wskutek kontrolowania dostępów implementacja zyskuje na elastyczności,

możliwe jest czyste połączenie synchronizacji i dostępu.

Rozproszona pamięć dzielona oparta na obiektach ma również wady. Po pierwsze, nie nadaje się do wykonywania starych, "zakurzonych" programów wieloprocesorowych, zakładających istnienie dzielonej, liniowej przestrzeni adresowej, którą każdy proces może dowolnie czytać i zapisywać. Jednak wieloprocesory są stosunkowo nowe, więc ilość istniejącego dla nich oprogramowania, na którym mogłoby komuś zależeć, jest mała. Drugą możliwą wadą jest dodatkowy koszt, który wynika z konieczności wywoływania metod obiektów przy wszystkich dostępach do obiektów dzielonych. Nie występuje on w przypadku stron dzielonych, do których można sięgać bezpośrednio. Skądinąd, wielu ekspertów od inżynierii oprogramowania zaleca obiekty jako narzędzie strukturalizacji nawet dla poszczególnych komputerów i uważa, że warto ponieść dodatkowe koszty.

4.4. Porównanie i podsumowanie

Systemy komputerowe z wieloma jednostkami centralnymi dzielą się na dwie klasy: systemy mające pamięć dzieloną i takie, które jej nie mają. Maszyny z pamięcią dzieloną (wieloprocesory) są łatwiejsze do programowania, lecz trudniej jest je budować. Z kolei maszyny bez pamięci dzielonej (multikomputery) trudniej jest programować, ale są łatwiejsze do zbudowania. Rozproszona pamięć dzielona stanowi technikę ułatwiającą programowanie multikomputerów przez symulowanie na nich pamięci dzielonej. Małe wieloprocesory są często oparte na szynie, natomiast ich wielkie modele są przełączane. Protokoły używane przez duże wieloprocesory do utrzymywania spójności pamięci podręcznych wymagają złożonych struktur danych i algorytmów. Wieloprocesory NUMA omijają tę złożoność poprzez wymuszanie podejmowania przez oprogramowanie wszelkich decyzji odnośnie do rozmieszczania stron na maszynach.

Jest możliwa prosta implementacja rozproszonej pamięci dzielonej (DSM), taka jak w systemie IVY, lecz jej działanie jest często znacznie gorsze od wieloprocesora. Z tego powodu badacze przeanalizowali rozmaite modele pamięci w poszukiwaniu poprawy wydajności. Standardem służącym do oceny wszystkich modeli jest spójność sekwencyjna, która oznacza, że wszystkie procesy oglądają wszystkie odwołania do pamięci w takim samym porządku. Spójność przyczynowa, spójność PRAM oraz spójność procesorowa w mniejszym stopniu wymagają, aby procesy rejestrowały wszystkie odwołania do pamięci w tym samym porządku. Inne podejście prezentują spójności: słaba, zwalniania i wejścia, w których pamięć nie jest spójna przez cały czas, ale programista może wymusić jej uspójnienie za pomocą pewnych działań, takich jak wchodzenie lub wychodzenie z sekcji krytycznej.

Do tworzenia rozproszonej pamięci dzielonej stosuje się trzy ogólne techniki. Pierwszą jest symulacja modelu pamięci wieloprocesora, dająca każdemu procesowi liniową pamięć stronicowaną. Strony są przemieszczane między maszynami stosownie do potrzeb. Druga technika wykorzystuje zwykłe języki programowania z dodatkowymi opisami zmiennych dzielonych. Trzecia jest oparta na modelach programowania wysokopoziomowego, takich jak krotki i obiekty.

System IVY działa zasadniczo jak pamięć wirtualna, w której brakujące strony przenosi się z maszyny do maszyny. System Munin używa wielu protokołów i spójności zwalniania, pozwalając na dzielenie indywidualnych zmiennych. System Midway jest podobny do systemu Munin z wyjątkiem tego, że zamiast spójności zwalniania używa spójności wejścia jako zwykłego przypadku. Przedstawiciel grupy z rozproszoną pamięcią dzieloną opartą na obiektach - system Linda z abstrakcyjną przestrzenią krotek, wolną od szczegółów stronicowania, znajduje się na drugim końcu spektrum. Drugi przedstawiciel tej grupy - system Orca dostarcza modelu, w którym na wielu maszynach są zwielokrotniane obiekty danych, a dostęp do nich odbywa się za pomocą chronionych metod, które sprawiają, że obiekty stają się dla programisty spójne sekwencyjnie.

 

Tendencje rozwojowe

Postęp w prowadzonych badaniach nad wieloprzetwarzaniem pamięci współdzielonej doprowadził do uznania go za klucz technologiczny dla programów posiadających podobne wspomaganie decyzji systemowych i procesów multimedialnych. Chociaż procesory muszą co roku przetwarzać o 50 procent więcej danych, naukowcy uznali że rachunkowe potrzeby tych programów nie mogą być spełnione przez obecne mikroprocesory. Ponieważ taki programy często mają tkwiącą równoległość, równoległe przetwarzanie jest efektywnym sposobem spełnienia rachunkowych potrzeb.

Podobnie jak procesory, obecnie wieloprzetwarzanie w pamięciach współdzielonych jest często budowane z mikroprocesorów o wysokim poziomie, więc istnieje czyste przejście drogi od pojedynczych procesorów do multiprocesorów realizowanych programowo. Kwestionowanie kłamstw w robieniu tych przejść tak gładko jak to jest możliwe, zarówno działanie jak i programowanie wymaga osiągnięcia tego. Pierwszy krok w spełnieniu tego wyzwania ma na celu zwrócenia uwagi w badaniach nad aktualnie używanymi pamięciami współdzielonymi mikroprocesorów i dojściu do inteligentnych planów w przyszłości, głównie opartymi na programach i technologicznych dążeniach. Następnym krokiem jest rozpoczęcie wypełniania luki w programowaniu modelowym i architekturach z wieloprzetwarzaniem pamięci współdzielonej. Ostatecznie i możliwie jednocześnie z drugim krokiem, badacze muszą szukać dróg dla tworzących się kierunków postępu analogicznego z bardziej prawdopodobnym oprogramowaniem, włączając postęp kompilatorów i narzędzi.

5.1. Obszary aplikacji

Badania skupiają się na fachowych programach czasami z uszczerbkiem na pozostałych ważnych dziedzinach. Programy handlowe były bardzo zaniedbywane. Większa część użytkowników nie rozwijała ich we własnych programach, głównie dla tego że nie posiadają stosownych narzędzi, a paradygmat w programowaniu pamięci współdzielonej jest daleki do łatwego opanowania.

Poszukiwane wieloprzetwarzania w pamięciach współdzielonych zaczęło skupiać się ostatnio na inżynierii i aplikacjach naukowych uruchamianych na setkach procesorów. Podczas gdy nacisk kładziono na skalowalność w tym obszarze pojawił się interesujący problem, ten obszar nie pokazuje jak serwery są użytkowane. Maszyny powyżej 1 miliona dolarów reprezentują jedynie trzy procent rynku serwerów dla prac inżynieryjnych i fachowych programów. Ponadto, roczny wzrost od 1995 do 2000 jest spodziewany na jedynie 14 procent dla tego rozmiaru serwerów - zaś niższy wzrost cen wszystkich pozostałych kategorii serwerów. To sugeruje wzrost działalności naukowej ma na celu inne programy i mniejsze serwery, które mogły by odzwierciedlać 97 procent rynku. W porównaniu z naukowymi i inżynieryjnymi programami używanymi w badaniach, typowo komercyjne programy mają większy rozmiar kodu, a wiele większy zakres złożoności, mniej operacji na liczbach rzeczywistych, różne gałęzie zachowań, więcej użytkowników, wyższy użycie sytemu operacyjnego, więcej przełączeń kontekstowych i wyższych prędkości układów wejścia/wyjścia. Ponieważ niezawodność jest ważne w serwerach handlowych, wspólne badania muszą rozpocząć się kierować nie jedynie na koncentrowaniu rezultatów, ale także na niezawodności, dostępności i użyteczności.

Inną przeszkodą jest w niskim stopniu analizowana efektywność systemu operacyjnego. NAS i Splash są jedynie dwoma przykładami jednej ścieżki z naciskiem na naukowe i inżynieryjne badania programów. Ten nacisk jest potrzebny dla bardziej realistycznej oceny struktury badań nad wieloprzetwarzaniem z pamięcią współdzieloną.

5.2. Modele i architektura

Analogiczne programowanie modeli i wychodzący sprzęt stają się coraz bardziej rozłączne. Wiele fabrycznych komputerów produkowanych jest w oparciu na pamięci współdzielonej wzorowanej czasami tak samo jak wiele analogicznych programów początek oparło na informacjach łączących modele. Obecnie, wspólnota wydaje się być mylona z tym jak zdefiniować gładkie linie z równoległych algorytmów, programowanie modelowe jest implementowane i realizowane w systemach o tej architekturze. Dodatkowym problemem jest brak standardu dla podstaw aplikacji spośród systemów z pamięcią współdzieloną.

Programowanie modeli jest interfejsem pomiędzy programistą a maszyną. Architektura jest podwładna strukturze samych maszyn. Wybór specyfikacji modelowego programowania określa, jak programista widzi maszynę, niezależność aktualnej struktury maszyny. Na przykład, w dystrybucji pamięci współdzielonej architektury takie jak Stanford DASH i Silicon Graphics Origin, pamięć jest fizycznie rozdzielona spośród procesorów. Sprzęt przesyła wiadomości automatycznie zapewniając pamięci podręcznej łączność pod warunkiem dopóki istnieje złudzenie o pojedynczym podziale globalnego miejsca adresowego przez programistów. W konsekwencji każdy procesor używa tej samej nazwy odnośnie do tej samej globalnej lokacji w pamięci, co dzieli dane po między względnie samodzielne procesory. W programowaniu modeli przesyłania wiadomości, każdy procesor ma swój własne miejsce adresowe. Żeby procesory dzieliły dane programista musi jasno włączyć aplikacje przesyłania i otrzymywania kodu źródłowego. Tak więc jest możliwy do wykonania modelu przesyłania wiadomości na szczycie maszyn z pamięcią współdzieloną i vice versa.

Osiągnięcia są ogólnie wyższe kiedy programowanie modelowe dostosowane jest do architektury, ale architekci mogą pisać programy dla poszczególnych architektur, sprawiając że są nieczułe na warianty postępu do wstrzymanej pamięci. Chociaż pisanie programów dla specjalnych architektur jest czasochłonne i w wielkiej mierze uniemożliwia łatwość użycia jaka jest z możliwości użycia pamięci dzielonej (zapisany raz i egzekwowany wiele razy), projektanci mogą chcieć wydobyć tak dużo działania jak to jest możliwe przez zharmonizowanie kodu w ten sposób.

Model pamięci współdzielonej umożliwia wzrost równoległości w zmiennych poziomach ziarnistości. Ponieważ ten model cechuje się niskim dostępem do utajenia, programiści skutecznie robią równoległe pętle zawierające bardzo krótki okres czasu. W rzeczywistości, projektanci byli zdolni do dużej sterowności, zapisu legalnych programów do systemów pamięci współdzielonych. Jednak dużo mniejsza skalowalność często oznacza osiągnięcie powiększenia i w rezultacie przyspieszeń pożądanych dla wielu użytkowników.

Wysoka skalowalność modelu przesyłania wiadomości jest często przypisywana do nowych wersji kodu. Jakkolwiek, zrównoleglenie kodu zwykle narzuca rozległe zmiany algorytmiczne do osiągnięcia skalowalności - zmiany które mogą być zarówno implementowane z modelem pamięci współdzielonej. W rzeczywistości, model przesyłania wiadomości w maszynie z pamięcią współdzieloną może oferować zarówno dobre działanie jak i przenośność.

5.3. Rozwinięte równoległe oprogramowanie

Aby stało się łatwiejsze rozwijanie równoległego oprogramowania, badania muszą rozszerzyć prace na automatyczne (kompilacje) dla techniki równoległości i w rozwijaniu narzędzi do pomagania w harmonizacji działania. Chociaż manualnie otwarta równoległość pozostaje najbardziej wspólnym znaczeniem eksploatowanej równoległości, automatyczny kompilator równoległości zbliża się do rzeczywistości. Kilka znaczących wyzwań jednak pozostaje.

Dotychczasowe kompilatory mają wiele interesujących naukowych typów kodu. Rozpoznają także równoległość wzrastającej liczby programów, które zawierają kody z tymi pętlami. Jakkolwiek, rozszerzenie programu, zawierającego inne komercyjne kody okazuje się być trudnym do zrealizowania zadaniem Taki kod jest często kilka razy bardziej ważniejszy od pętli ukierunkowanych i dużo bardziej złożonych. Dodatkowo, duże kategorie programów takie jak bazy danych, telekomunikacja, systemy informacji geograficznej, asortyment i alternatywne systemy wymiany uruchamiane są kolejno na maszynach z równoległą pamięcią współdzieloną. Niektóre z nich nie posiadają struktury charakterystycznej dla programów naukowych i inżynieryjnych, tak więc paralelizacja ich może być dużo bardziej kwestionowana.

Jednym z problemów jest zidentyfikowanie równoległości, co obejmuje procedurę rozszerzenia. To wymaga zagmatwanego włączenia dostępów do pamięci przez wskazanie zależnych danych do analizy. Jak odkryć zależne dane, gdzie wskazówki są zawikłane, pozostaje najbardziej znaczącą przeszkodą do pełnego zidefinkowania równoległości programów. Pewne kroki zostały poczynione w analizie programów C ze wskazówkami, ale pętle z bardzo dynamicznym dostępem pozostają nierównoległe. W takich przypadkach technika interakcyjnej równoległości może wydać się obiecująca. W tych technikach kompilatory pytają użytkowników o wyższy poziom informacji programów, może to być pomocne w identyfikacji równoległości lub w dedukcji spostrzeżonych zależności, nie muszących hamować równoległość.

Niektóre eksperymentalne i komercyjne kompilatory rozwiązują problem równoległości przez stosowanie analizy przepływów interproceduralnych. Z techniką taką, jak robienie prywatnych tablic i prowadzenie interproceduralnych analiz, badacze mogą zidentyfikować gruboziarnistą równoległość w kodzie, co może zredukować synchronizację kodu i koszty pamięci. Inną metodą równoległości używaną przez programistów jest rozpoznawczy algorytm i zastępowanie. Wiele z linearnych algorytmów ma interesujące warianty równoległości. Kompilatory często wykonują niektóre prostsze zadania przez optymalizację sumy redukcji. Kompilator powinien rozważyć identyfikację kilku przykładów rozpoznania i zastąpienia nie tylko dla naukowego obliczania.

W wielu sprawach kompilatory mogą z powodzeniem identyfikować odpowiednie równoległości w głównych pętlach programów. Jakkolwiek, niektóre z programów ukazują doskonałe przyspieszenie, niektóre posiadają własności takie, jak zachowanie pamięci i limit przyspieszenia. Równoległe kompilatory często agresywnie paralelizują tyle pętli ile jest możliwych, co może powodować drobno ziarnistość pętli będących drogami równoległymi, które prowadzą do ostatecznej prawdy lub fałszu. W niektórych przypadkach równoległe pętle ze współdzielonymi problemami działają znacznie gorzej aniżeli pętle wykonywane sekwencyjnie. Lepsze analizy pamięci i kombinacje komunikacji oraz analiza obliczania może ograniczyć liczbę wyborów równoległości. W niektórych przypadkach kompilator może adekwatnie analizować zachowanie pamięci. Zwykle jest to jednak nieodpowiednia kontrola hierarchii w pamięci. Architektoniczne sposoby instrukcji pozwalają kompilatorom mięć lepszą kontrolę nad pamięciami podręcznymi i mogą polepszyć zachowanie pamięci.

Tak więc, chociaż równoległe kompilatory mogą stać się całkiem dobre w identyfikacji równoległości, są mniej biegłe ustanawianiu stopnia tej równoległości. Jako rezultat równoległości kompilatora, programy mogą wykonywać obliczenia na większej ilości procesorów niż może być efektywnie użytych. Nie tylko zużywają procesory, które mogłyby być użyte do bardziej pożytecznych prac, ale czasem nawet spowalniają jego obliczenia. To marnotrawstwo źródeł obliczeniowych staje się bardziej zaostrzone dla dysponowanej liczby procesorów, szczególnie dla komputerów równoległych, używanych jako wieloprogramowe serwery obliczeniowe. Wstępne prace ukazują obietnice adaptacji procesu w działaniu programu. Pomysłem jest ograniczenie procesów zgodnych z załadowanym systemem i programowo dostępnej równoległości. Taki dostęp pozwala systemowi używać tak wielu procesorów jak jest to możliwe, bez przeciążenia.

Nawet z ustalonymi normami technologicznymi, automatyczna równoległość dużych programów nie jest do końca praktyczna. Tak więc, kompilatory powinny dostarczać sprzężenia zwrotnego dla użytkownika aby ręcznie mógł wspomóc równoległość. Na przykład, kompilator gromadzi dużo użytecznych informacji o zachowaniu pamięci i zależnościach. Nawet jeśli nie jest to skuteczne w automatycznej równoległości, informacje zgromadzone podczas analizy mogą pomóc programiście ręcznie sparalelizować lub zoptymalizować program. Oficjalne mechanizmy, które przenoszą stosowne informacje z analizy mogą być również użyteczne.

Inną kwestią dotyczącą zarówno przenośności, jak i łatwości użycia, jest potrzeba standaryzowania dyrektyw kompilatorów. Wbrew różnicom wieloprzetwarzania pamięci współdzielonych, żaden standard dla dyrektyw wieloprzetwarzania pamięci współdzielonych lub flagi kompilatorów nie istnieje. Podział pamięci w maszynach odniósł sukces ze standardami takimi, jak Message-Passing Interface (MPI). Takie prace powinny być kontynuowane.

 

Literatura

G. Coulouris, J. Dollimore, T. Kindberg: Systemy rozproszone - podstawy i projektowanie - WNT, Warszawa 1996.

A. S. Tanenbaum: Rozproszone systemy operacyjne - PWN, Warszawa 1997.

P. Stenström, E. Hagersten, D.J. Lilja, M. Martonosi, M.Venugopal: Trends in Shared Memory Multiprocessing - Computer 12'97, s. 44-50.

Internet.

---