pojecia_pamieci_wspolnej_i_spojnej [mgr Wiki]

[[pojecia_pamieci_wspolnej_i_spojnej]]
mgr Wiki

# Pojęcia pamięci wspólnej i spójnej.

Pamięć wspólna, to obszar pamięci, z którego może korzystać wiele procesów.

## Sposoby realizacji pamięci dzielonej w wieloprocesorach

### Wieloprocesor z pojedynczą szyną

Rysunek: Wieloprocesor z pojedynczą szyną (źródło: Tanenbaum, Distributed Systems)

Dostęp do pamięci poprzez szynę.
Rozstrzyganie konfliktów w dostępie do szyny.
Szyna potencjalnym wąskim gardłem (kłopoty ze skalowalnością) - do 64 CPU, zwykle raczej 4-8.

Podsłuchująca pamięć podręczna (ang. snooping cache - rozmiary pamięci podręcznych są od 512 KB do 1 MB bajtów, dają współczynnik trafień rzędu 90%. Wszystkie żądania dotyczące pamięci przechodzą przez pamięć podręczną. Protokoły zapewniające zgodność danych przechowywanych w pamięci podręcznej (ang. cache consistency protocol).

### Wieloprocesor z przełącznikami

Wieloprocesory z pojedynczą szyną nie skalują się do systemów z setkami lub tysiącami procesorów. Jedynym efektywnym sposobem zwiększenia skalowalności jest zwiększenie przepustowości łączy komunikacyjnych. Rozwiązanie może polegać na zmianie topologii połączeń - zamiast jednej szyny użyć dwóch lub siatki szyn.
Innym sposobem jest stworzenie architektury hierarchicznej. Pojedynczy klaster (ang. cluster) składa się z kilku CPU i pamięci połączonych szyną. System składa się z wielu takich klastrów połączonych ze sobą za pomocą specjalnej szyny (ang. intercluster bus). Dopóki większość CPU komunikuje się ze sobą głównie w ramach jednego klastra, dopóty ruch międzyklastrowy będzie niewielki. Jeśli zrobi się intensywny, to można rozbudowywać połączenia międzyklastrowe, tworząc np. siatkę takich połączeń.

### Wieloprocesor typu NUMA

Sprzętowe buforowanie w dużych wieloprocesorach jest kosztowne. Rozwiązaniem nie wymagającym wyrafinowanych technik buforowania są architektury wieloprocesorowe typu NUMA. Tak jak w tradycyjnych wieloprocesorach typu UMA (ang. Uniform Memory Access), w wieloprocesorach typu NUMA istnieje pojedyncza wirtualna przestrzeń adresowa widoczna przez wszystkie procesory. Wartość zapisana do komórki przez dowolny procesor jest natychmiast widoczna dla wszystkich pozostałych procesorów, kolejna operacja odczytu na pewno dostarczy tę właśnie wartość.
Różnica między NUMA i UMA nie leży w semantyce, tylko w wydajności. W NUMA dostęp do zdalnej pamięci jest dużo wolniejszy niż dostęp do lokalnej i nie próbuje się niwelować tej różnicy za pomocą sprzętowego buforowania (współczynnik jest rzędu 1:10).

W maszynach typu UMA lokalizacja strony nie ma kluczowego znaczenia (bo dzięki buforowaniu strona i tak zostanie przeniesiona tam, gdzie jest potrzebna).

W maszynach typu NUMA lokalizacja ma decydujące znaczenie dla wydajności systemu.

1. Strony mogą mieć z góry przypisane położenie.
2. Jeśli CPU odwołuje się do strony, która nie jest odwzorowana do jego przestrzeni adresowej, to jest generowany błąd braku strony. SO może wówczas podjąć decyzję o:
   - w przypadku strony tylko do czytania: utworzeniu lokalnej kopii strony lub odwzorowaniu adresu wirtualnego do pamięci zdalnej - wówczas wszystkie odwołania do tej strony będą realizowane zdalnie,
   - w przypadku strony do czytania i pisania: przesłaniu strony do procesora zgłaszającego żądanie (i unieważnieniu oryginalnej strony) lub odwzorowaniu adresu wirtualnego do pamięci zdalnej.
   - Niezależnie od przyjętego rozwiązania kolejne odwołania do tej strony odbywają się sprzętowo.
3. Zwykle specjalny proces demon (ang. page scanner) okresowo zbiera statystyki o odwołaniach lokalnych i zdalnych i ew. modyfikuje wcześniejsze decyzje. Może także “zamrozić” lokalizację strony na jakiś czas.

## Sposoby realizacji pamięci dzielonej w wielokomputerach

Rozproszona pamięć dzielona (ang. distributed shared memory, w skrócie DSM) jest abstrakcją używaną do określenia wspólnego użytkowania danych przez procesy, które nie dzielą pamięci fizycznej. Pamięć dzielona stanowi część przestrzeni adresowej procesów i mogą one z niej korzystać w standardowy sposób. Zadaniem systemu operacyjnego ew. systemu wykonawczego jest zapewnienie w sposób przezroczysty dostępu do wspólnych danych (emulowanie wspólnej pamięci fizycznej).

Głównym celem DSM jest zapewnienie programiście wygodnego dostępu do współdzielonych danych, bez konieczności korzystania z mechanizmu przekazywania komunikatów. Oczywiście w systemie rozproszonym nie da się całkowicie uniknąć przekazywania komunikatów - korzysta z niego system wsparcia działania pamięci DSM wysyłając aktualizacje między komputerami.

1. Wieloprocesor z pojedynczą szyną: obsługa pamięci dzielonej realizowana całkowicie sprzętowo.
2. Wieloprocesor z przełącznikami: sprzętowe buforowanie, ale programowe struktury danych przechowujące informacje o położeniu buforowanych bloków. Zgodność zachowuje się dzięki stosowaniu złożonych algorytmów zwykle realizowanych przez mikrokod MMU.
3. Maszyny typu NUMA: rozwiązanie hybrydowe. CPU może czytać/pisać z/do wspólnej wirtualnej przestrzeni adresowej, ale buforowanie (kopiowanie, migracja stron) jest kontrolowane programowo.
4. DSM - strony: CPU nie może bezpośrednio sięgać do pamięci zdalnej; obsługa błędów braku zdalnej strony odbywa się programowo (SO).
5. DSM - zmienne dzielone: nie ma pojedynczej pamięci wspólnej, informacje o dzielonych strukturach danych dostarcza użytkownik.
6. DSM - obiekty: zdalny dostęp tylko poprzez chronione metody (ułatwia zachowanie zgodności obiektów), wszystko realizowane programowo.

| Szyna | Przełączniki | NUMA | DSM-strona | DSM-zm.dz. | DSM-obiekty
Liniowa, dzielona wirtualna przestrzeń adresowa? | Tak | Tak | Tak | Tak | Nie | Nie
Możliwe operacje | Czyt/Pis | Czyt/Pis | Czyt/Pis | Czyt/Pis | Czyt/Pis | Ogólne
Kapsułkowanie i metody? | Nie | Nie | Nie | Nie | Nie | Tak
Czy zdalny dostęp jest możliwy w sprzęcie? | Tak | Tak | Tak | Nie | Nie | Nie
Kto zamienia zdalne żądania dostępu do pamięci na komunikaty? | MMU | MMU | MMU | SO | System wykonawczy j.p. | System wykonawczy j.p.
Środek transmisji? | Szyna | Szyna | Szyna | Sieć | Sieć | Sieć
Kto realizuje migrację danych? | Sprzęt | Sprzęt | Oprog. | Oprog. | Oprog. | Oprog.
Jednostka transmisji? | Blok | Blok | Strona | Strona | Zmienna dzielona | Obiekt

## Modele spójności

### Spójność - wprowadzenie

Ze względów wydajnościowych przy realizacji dostępu do pamięci dzielonej korzysta się z:

- lokalnych pamięci podręcznych - każdy proces ma lokalnego zarządcę kopii; w realizacji opartej na stronicowaniu rolę tę pełni jądro systemu operacyjnego, a w realizacji z dzielonymi obiektami - same procesy (kiedy wykonują kod procedur bibliotecznych),
- buforowania operacji pisania - amortyzując koszt komunikacji przez rozkładanie go na wiele operacji pisania.

W pewnych sytuacjach jest do przyjęcia pewien stopień niespójności danych. Najczęściej jednak aplikacje mają pewne oczekiwania co do sposobu, w jaki powinna się zachowywać pamięć.

Przykład (inicjalnie a = b = 0):
`Proces 1 Proces 2`
`br:=b; a := a+1;`
`ar:=a; b := b+1;`
`if (ar>=br) then`
`print(”OK”);`

Nie stosuje się żadnej synchronizacji na poziomie aplikacji.
Jakich kombinacji wartości można intuicyjnie oczekiwać:
`ar = 0, br = 0` `ar = 1, br = 0` `ar = 1, br = 1` Czyli zawsze ar >= br i proces 1 wydrukuje OK.
Realizacja pamięci dzielonej może jednak dopuszczać sytuację, gdy aktualizacja zmiennych a i b jest dostarczana zarządcy kopii używanych przez proces 1 w zmienionej kolejności.

Modele spójności pamięci różnią się odpowiedzią na następujące pytanie: jeśli ma nastąpić czytanie komórki pamięci, to które ze skutków zapisywania tej komórki kandydują ze swoimi wartościami jako możliwe wyniki czytania?
Model spójności jest zasadniczo kontraktem między procesami a pamięcią. Zgodnie z tym kontraktem jeśli procesy zgodzą się podporządkować pewnym zasadom, to pamięć obiecuje zachowywać się poprawnie.

### Spójnosć ścisła:

Najsilniejsza wersja modelu pamięci nosi nazwę spójności ścisłej i spełnia następujący warunek:
Wszystkie zapisywane wartości są natychmiast dostępne dla wszystkich procesów - czytanie dostarcza zawsze najnowszą zapisaną wartość istniejącą w chwili, kiedy jest wykonywane.

Do głównych modeli spójności dających się praktycznie urzeczywistniać w implementacjach pamięci dzielonej należą: spójność sekwencyjna i modele oparte na spójności słabej.

### Spójność sekwencyjna:

Wynik dowolnego wykonania operacji na pamięci jest równoważny temu, co otrzymuje się przy spełnieniu następujących warunków:

- operacje dotyczące pamięci i należące do różnych procesów są wykonywane w pewnej określonej kolejności;
- operacje każdego pojedynczego procesu są wykonywane w porządku określonym przez jego program.

Oznacza to w szczególności, że każdy przeplot operacji czytania i pisania pochodzących od poszczególnych procesów jest akceptowalnym zachowaniem, ale wszystkie procesy muszą widzieć dokładnie taki sam przeplot.
Taki model spójności pamięci można zrealizować za pomocą jednego serwera utrzymującego wszystkie dane dzielone i obsługującego żądania procesów dotyczące operacji czytania i pisania (serwer utrzymywałby globalne uporządkowanie operacji na pamięci).

### Spójność słaba:

1. W tym modelu zakłada się, że nie wszystkie operacje na pamięci muszą być spójne sekwencyjnie, wystarczy, że warunek ten będą spełniały operacje synchronizacyjne. Osłabienie spójności dotyczy więc typu dostępu.
2. Proces nie będzie dopuszczony do zmiennej synchronizacyjnej zanim wszędzie nie zakończy się wykonanie wszystkich poprzedzających operacji pisania.
3. Proces nie będzie dopuszczony do żadnej operacji czytania i pisania zanim nie zakończy się wykonanie wszystkich poprzedzających operacji na zmiennych synchronizacyjnych.

- Zgodnie z wymaganiem (1) wszystkie procesy widzą wszystkie operacje na zmiennych synchronizacyjnych w tej samej kolejności.
- Zgodnie z wymaganiem (2) synchronizacja flushes the pipeline - wymusza wszędzie dokończenie wszystkich rozpoczętych lub nawet gdzieś lokalnie zakończonych, ale nie wszędzie rozpropagowanych operacji pisania.
- Zgodnie z wymaganiem (3) kiedy wykonuje się operację na danych wszystkie wcześniejsze operacje synchronizacyjne musiały się już zakończyć.

W odróżnieniu od innych modeli spójności, słaba spójność wymusza spójność grupy operacji, a nie pojedynczych zapisów i odczytów.
Obiekty mogą mieć wartości niespójne podczas pobytu procesu w sekcji krytycznej, ale wtedy są niedostępne dla innych procesów.

### Spójność na wyjściu

Problem ze słabą spójnością polega na tym, że gdy ktoś sięga do zmiennej synchronizacyjnej to, nie wiadomo, czy robi to, gdyż skończył zapisywać współdzielone zmienne, czy też gdyż zaraz zacznie je czytać. W rezultacie trzeba wykonać akcję wymaganą w obu przypadkach, czyli rozpropagować operacje zapisu do wszystkich lokalnych kopii i zebrać wszystkie zapisy wykonane na lokalnych kopiach. W celu rozróżnienia tych dwóch przypadków potrzeba dwóch rodzajów zmiennych synchronizacyjnych lub operacji.
Zapewnia je spójność na wyjściu (lub zwalniania, ang. release consistency). Operacja `acquire` oznacza chęć wejścia do sekcji krytycznej, a operacja `release` wyjście z sekcji krytycznej.

### Spójność na wejściu

Zgodność na wejściu (ang. entry consistency) wymaga, aby KAŻDA zwykła zmienna dzielona była związana z pewną zmienną synchronizacyjną. Gdy na zmiennej synchronizacyjnej jest wykonywana operacja `acquire`, tylko dane związane z tą zmienną synchronizacyjną są uzgadniane.

### Podsumowanie modeli spójności

W tej tabeli opisano modele spójności nie korzystające z operacji synchronizacyjnych:

Spójność | Opis
--- | ---
Ścisła | Absolutne uporządkowanie w czasie wszystkich operacji na zmiennych dzielonych
Sekwencyjna | Wszystkie procesy widzą wszystkie operacje na zmiennych dzielonych w tej samej kolejności. Operacje te nie są uporządkowane w czasie

W tej tabeli opisano modele spójności korzystające z operacji synchronizacyjnych:

Spójność | Opis
--- | ---
Słaba | Można zakładać, że zmienne dzielone są uzgodnione jedynie po wykonaniu synchronizacji
Na wyjściu | Zmienne dzielone są uzgadniane podczas opuszczania sekcji krytycznej
Na wejściu | Zmienne dzielone związane z sekcją krytyczną są uzgadniane na wejściu do sekcji krytycznej

## Przydatne linki:

http://rainbow.mimuw.edu.pl/SO/Wyklady-html/13_dsm/
http://rainbow.mimuw.edu.pl/SO/Wyklady-html/14_dsm/

# Pobierz dokument

9.3.doc

pojecia_pamieci_wspolnej_i_spojnej.txt · Last modified: 2006/05/24 16:08 by 213.134.172.237