Model spójności - Consistency model

W informatyce , modele spójności są stosowane w systemach rozproszonych , jak rozproszonych pamięci wspólnej systemów lub sieciowy system plików (takich jak systemy plików , baz danych , optymistycznych replikacji systemów lub buforowania internetowej ). Mówi się, że system obsługuje dany model, jeśli operacje na pamięci podlegają określonym regułom. Model spójności danych określa kontrakt między programistą a systemem, w którym system gwarantuje, że jeśli programista przestrzega zasad, pamięć będzie spójna, a wyniki odczytu, zapisu lub aktualizacji pamięci będą przewidywalne. Różni się to od spójności, która występuje w systemach z pamięcią podręczną lub bez pamięci podręcznej i jest spójnością danych w odniesieniu do wszystkich procesorów. Spójność zajmuje się utrzymywaniem globalnego porządku, w którym zapisy do jednej lokalizacji lub pojedynczej zmiennej są widziane przez wszystkie procesory. Spójność dotyczy porządkowania operacji w wielu lokalizacjach w odniesieniu do wszystkich procesorów.

Języki wysokiego poziomu , takie jak C++ i Java , częściowo utrzymują kontrakt, tłumacząc operacje pamięciowe na operacje niskiego poziomu w sposób, który zachowuje semantykę pamięci . Aby dotrzymać umowy, kompilatory mogą zmienić kolejność niektórych instrukcji pamięci i wywołań bibliotek, takich jak pthread_mutex_lock()enkapsulacja wymaganej synchronizacji.

Weryfikacja spójności sekwencyjnej poprzez sprawdzanie modelu jest generalnie nierozstrzygnięta , nawet w przypadku protokołów koherencji pamięci podręcznej o skończonym stanie .

Modele spójności definiują reguły dla pozornej kolejności i widoczności aktualizacji oraz są na kontinuum z kompromisami.

Przykład

Załóżmy, że ma miejsce następujący przypadek:

  • Wiersz X jest replikowany w węzłach M i N
  • Klient A zapisuje wiersz X do węzła M
  • Po okresie czasu t klient B odczytuje wiersz X z węzła N

Model spójności musi określić, czy klient B widzi zapis wykonywany przez klienta A, czy nie.

Rodzaje

Istnieją dwie metody definiowania i kategoryzowania modeli spójności; wydanie i widok.

Wydanie
Metoda wystawiania opisuje ograniczenia, które definiują sposób, w jaki proces może wydawać operacje.
Pogląd
Metoda widoku definiująca kolejność operacji widocznych dla procesów.

Na przykład model spójności może określać, że proces nie może wydać operacji, dopóki wszystkie poprzednio wydane operacje nie zostaną zakończone. Różne modele spójności wymuszają różne warunki. Jeden model spójności można uznać za silniejszy niż inny, jeśli wymaga wszystkich warunków tego modelu i więcej. Innymi słowy, model z mniejszą liczbą ograniczeń jest uważany za model o słabszej spójności.

Modele te definiują sposób rozmieszczenia sprzętu i na wysokim poziomie, jak programista musi kodować. Wybrany model wpływa również na to, jak kompilator może zmienić kolejność instrukcji. Ogólnie rzecz biorąc, jeśli są uporządkowane zależności kontrolne między instrukcjami i jeśli są uporządkowane zapisy w tej samej lokalizacji, kompilator może zmienić kolejność zgodnie z wymaganiami. Jednak w przypadku modeli opisanych poniżej niektóre mogą umożliwiać zmianę kolejności zapisu przed załadowaniem, a niektóre nie.

Ścisła spójność

Ścisła spójność to najsilniejszy model spójności. W tym modelu zapis do zmiennej przez dowolny procesor musi być natychmiast widoczny dla wszystkich procesorów.

Diagram ścisłego modelu i diagramy modelu nieścisłego opisują ograniczenie czasowe – chwilowe. Można to lepiej zrozumieć tak, jakby obecny był zegar globalny, w którym każdy zapis powinien być odzwierciedlony we wszystkich pamięciach podręcznych procesora przed końcem tego okresu zegara. Następna operacja musi nastąpić dopiero w następnym okresie zegarowym.

Sekwencja Ścisły model Model nieścisły
P 1 P 2 P 1 P 2
1 W ( x )1 W ( x )1
2 R ( x )1 R ( x )0
3 R ( x )1

To najsztywniejszy model. W tym modelu oczekiwany wynik programisty będzie każdorazowo otrzymywany. Jest deterministyczny. Jego praktyczne znaczenie ogranicza się do eksperymentu myślowego i formalizmu, ponieważ natychmiastowa wymiana komunikatów jest niemożliwa. Nie pomaga w odpowiedzi na pytanie o rozwiązywanie konfliktów podczas współbieżnych zapisów do tego samego elementu danych, ponieważ zakłada, że ​​współbieżne zapisy są niemożliwe.

Spójność sekwencyjna

Model spójności sekwencyjnej zaproponował Lamport (1979). Jest to słabszy model pamięci niż model ścisłej spójności. Zapis do zmiennej nie musi być widoczny od razu, jednak zapisy do zmiennych przez różne procesory muszą być widziane w tej samej kolejności przez wszystkie procesory. Jak zdefiniował Lamport (1979), spójność sekwencyjna jest spełniona, jeśli „wynik dowolnego wykonania jest taki sam, jak gdyby operacje wszystkich procesorów były wykonywane w pewnej kolejności sekwencyjnej, a operacje każdego pojedynczego procesora pojawiają się w tej kolejności w porządek określony przez jego program."

Należy zachować kolejność programów w każdym procesorze i sekwencyjną kolejność operacji między procesorami. Aby zachować sekwencyjną kolejność wykonywania między procesorami, wszystkie operacje muszą wydawać się wykonywane natychmiastowo lub niepodzielnie w stosunku do każdego innego procesora. Operacje te wymagają jedynie „pozorów” do wykonania, ponieważ fizycznie niemożliwe jest natychmiastowe przesłanie informacji. Na przykład w systemie wykorzystującym pojedynczą, globalnie współdzieloną magistralę, po przesłaniu informacji do linii magistrali, gwarantuje się, że wszystkie procesory zobaczą informacje w tym samym momencie. W ten sposób przekazanie informacji do linii magistrali kończy wykonywanie w odniesieniu do wszystkich procesorów i wydaje się, że zostało wykonane. Architektury bez pamięci podręcznej lub architektury z pamięcią podręczną z sieciami połączeń, które nie są natychmiastowe, mogą zawierać powolną ścieżkę między procesorami a pamięciami. Te powolne ścieżki mogą powodować niespójność sekwencyjną, ponieważ niektóre pamięci odbierają nadawane dane szybciej niż inne.

Spójność sekwencyjna może dawać wyniki niedeterministyczne. Dzieje się tak, ponieważ sekwencja kolejnych operacji między procesorami może być różna podczas różnych uruchomień programu. Wszystkie operacje pamięciowe muszą odbywać się w kolejności programu.

Linearyzacja (znana również jako spójność atomowa) może być zdefiniowana jako spójność sekwencyjna z ograniczeniem czasu rzeczywistego.

Spójność przyczynowa

Spójność przyczynowa to osłabiający model spójności sekwencyjnej poprzez kategoryzację zdarzeń na te, które są powiązane przyczynowo i te, które nie są. Definiuje, że tylko operacje zapisu, które są powiązane przyczynowo, muszą być widziane w tej samej kolejności przez wszystkie procesy.

Model ten rozluźnia spójność sekwencyjną w przypadku współbieżnych zapisów przez procesor oraz zapisów, które nie są powiązane przyczynowo. Dwa zapisy mogą stać się powiązane przyczynowo, jeśli jeden zapis do zmiennej jest zależny od poprzedniego zapisu do dowolnej zmiennej, jeśli procesor wykonujący drugi zapis właśnie odczytał pierwszy zapis. Te dwa zapisy mogły zostać wykonane przez ten sam procesor lub przez różne procesory.

Podobnie jak w przypadku spójności sekwencyjnej, odczyty nie muszą odzwierciedlać zmian natychmiast, jednak muszą odzwierciedlać wszystkie zmiany zmiennej w sposób sekwencyjny.

Sekwencja P 1 P 2
1 W 1 ( x )3
2 W 2 (x) 5
3 R 1 ( x ) 3

W 1 nie jest związany przyczynowo z W 2 . R1 byłby kolejno niespójny, ale jest przyczynowo zgodny .

Sekwencja P 1 P 2 P 3 P 4
1 W(x)1 R(x)1 R(x)1 R(x)1
2 W(x)2
3 W(x)3 R(x)3 R(x)2
4 R(x)2 R(x)3

W(x)1 i W(x)2 są powiązane przyczynowo ze względu na odczyt dokonany przez P2 do x przed W(x)2.

Spójność procesora

W celu zachowania spójności danych i uzyskania skalowalnych systemów procesorowych, w których każdy procesor ma własną pamięć, opracowano model spójności procesora . Wszystkie procesory muszą być spójne w kolejności, w jakiej widzą zapisy wykonane przez jeden procesor oraz w sposób, w jaki widzą zapisy dokonywane przez różne procesory w tej samej lokalizacji (zachowana jest spójność). Jednak nie muszą być spójne, gdy zapisy są dokonywane przez różne procesory w różnych lokalizacjach.

Każdą operację zapisu można podzielić na kilka zapisów podrzędnych do wszystkich pamięci. Odczyt z jednej takiej pamięci może nastąpić przed zakończeniem zapisu do tej pamięci. Dlatego odczytywane dane mogą być nieaktualne. Tak więc procesor pod PC może wykonać młodsze obciążenie, gdy starszy sklep musi zostać zatrzymany. Przeczytaj przed zapisem, przeczytaj po przeczytaniu i napisz przed zapisem Kolejność jest nadal zachowana w tym modelu.

Model spójności procesora jest podobny do modelu spójności PRAM z silniejszym warunkiem, który definiuje wszystkie zapisy w tej samej lokalizacji pamięci, muszą być widziane w tej samej kolejności sekwencyjnej przez wszystkie inne procesy. Spójność procesora jest słabsza niż spójność sekwencyjna, ale silniejsza niż model spójności PRAM.

System wieloprocesorowy Stanford DASH implementuje odmianę spójności procesora, która jest nieporównywalna (ani słabsza, ani silniejsza) z definicjami Goodmana. Wszystkie procesory muszą być spójne w kolejności, w jakiej widzą zapisy jednego procesora oraz w sposób, w jaki widzą zapisy różnych procesorów w tej samej lokalizacji. Jednak nie muszą być spójne, gdy zapisy są dokonywane przez różne procesory w różnych lokalizacjach.

Spójność potokowej pamięci RAM lub spójność FIFO

Spójność potokowego RAM ( spójność PRAM) została przedstawiona przez Liptona i Sandberga w 1988 roku jako jeden z pierwszych opisanych modeli spójności. Ze względu na swoją nieformalną definicję, w rzeczywistości istnieją co najmniej dwie nieznacznie różne implementacje, jedna autorstwa Ahamada i in. i jeden przez Mosberger.

W spójności PRAM wszystkie procesy przeglądają operacje pojedynczego procesu w tej samej kolejności, w jakiej zostały wydane przez ten proces, podczas gdy operacje wydawane przez różne procesy mogą być przeglądane w różnej kolejności z różnych procesów. Spójność PRAM jest słabsza niż spójność procesora. PRAM łagodzi potrzebę utrzymywania spójności lokalizacji we wszystkich swoich procesorach. Tutaj odczyty do dowolnej zmiennej mogą być wykonywane przed zapisami w procesorze. Przeczytaj przed zapisem, przeczytaj po przeczytaniu i napisz przed zapisem Kolejność jest nadal zachowana w tym modelu.

Sekwencja P 1 P 2 P 3 P 4
1 W(x)1
2 R(x)1
3 W(x)2
4 R(x)1 R(x)2
5 R(x)2 R(x)1

Spójność pamięci podręcznej

Spójność pamięci podręcznej wymaga, aby wszystkie operacje zapisu w tej samej lokalizacji pamięci były wykonywane w pewnej kolejności sekwencyjnej. Spójność pamięci podręcznej jest słabsza niż spójność procesora i nieporównywalna ze spójnością PRAM.

Powolna konsystencja

Wolna pamięć

Przy powolnej spójności, jeśli proces odczytuje wartość wcześniej zapisaną w lokalizacji pamięci, nie może później odczytać żadnej wcześniejszej wartości z tej lokalizacji. Zapisy wykonywane przez proces są natychmiast widoczne dla tego procesu. Powolna spójność jest słabszym modelem niż spójność PRAM i pamięci podręcznej.

Przykład: diagram wolnej pamięci przedstawia przykład wolnej spójności. Pierwszy proces zapisuje 1 do komórki pamięci X, a następnie zapisuje 1 do komórki pamięci Y. Drugi proces odczytuje 1 z Y, a następnie odczytuje 0 z X, mimo że X zostało zapisane przed Y.

Hutto, Phillip W. i Mustaque Ahamad (1990) ilustrują, że przez odpowiednie programowanie powolna pamięć (spójność) może być ekspresyjna i wydajna. Wspominają, że wolna pamięć ma dwie cenne właściwości; lokalność i wspomaganie redukcji z pamięci atomowej. Proponują dwa algorytmy do przedstawienia wyrazistości wolnej pamięci.

Poniższe modele wymagają specyficznej synchronizacji przez programistów.

Słabe zamówienie

Kolejność i niepodzielność programu jest utrzymywana tylko na grupie operacji, a nie na wszystkich odczytach i zapisach. Wynikało to ze zrozumienia, że ​​pewne operacje pamięciowe – takie jak te przeprowadzane w sekcji krytycznej – nie muszą być widoczne dla wszystkich procesorów – na przykład po zakończeniu wszystkich operacji w sekcji krytycznej. Wykorzystuje również fakt, że programy napisane do wykonania w systemie wieloprocesorowym zawierają wymaganą synchronizację, aby upewnić się, że wyścigi danych nie występują, a wyniki SC są generowane zawsze. W związku z tym w przypadku słabej kolejności operacje inne niż operacje synchronizacji można sklasyfikować jako operacje na danych .

P 1 P 2
X = 1;
ogrodzenie
 
xgotowy = 1;
ogrodzenie
while (!xready) {}; 
 
ogrodzenie
 
y = 2;

Operacje synchronizacji sygnalizują procesorowi, aby upewnić się, że zakończył i widział wszystkie poprzednie operacje wykonane przez wszystkie procesory. Aby zachować słabą kolejność, operacje zapisu przed operacją synchronizacji muszą być wykonywane globalnie przed operacją synchronizacji. Operacje obecne po operacji synchronizacji powinny być również wykonywane dopiero po zakończeniu operacji synchronizacji. Dlatego dostęp do zmiennych synchronizacji jest sekwencyjnie spójny i każdy odczyt lub zapis powinien być wykonywany dopiero po zakończeniu poprzednich operacji synchronizacji. W tym modelu spójność nie jest rozluźniona. Po spełnieniu tych wymagań można zmienić kolejność wszystkich innych operacji „na danych”.

Program w dużym stopniu polega na jawnej synchronizacji. W przypadku modeli o słabym uporządkowaniu programista musi używać instrukcji blokowania atomowego, takich jak test-and-set, fetch-and-op, store conditional, load linked lub musi etykietować zmienne synchronizacji lub używać barier.

Spójność uwalniania

Model spójności wydania rozluźnia model słabej spójności, rozróżniając operację synchronizacji wejścia od operacji synchronizacji wyjścia. W przypadku słabego uporządkowania, gdy ma być widoczna operacja synchronizacji, wszystkie operacje we wszystkich procesorach muszą być widoczne przed wykonaniem operacji synchronizacji i kontynuowaniem działania procesora. Jednak w modelu spójności wydań, podczas wejścia do sekcji krytycznej, określanej jako „pozyskaj”, wszystkie operacje dotyczące zmiennych pamięci lokalnej muszą zostać zakończone. Podczas wyjścia, określanego jako „zwolnienie”, wszystkie zmiany wprowadzone przez lokalny procesor powinny być propagowane do wszystkich innych procesorów. Spójność jest nadal utrzymywana.

Operacja pozyskiwania to ładowanie/odczyt wykonywane w celu uzyskania dostępu do sekcji krytycznej. Operacja wydania to zapis/zapis wykonywany w celu umożliwienia innym procesorom korzystania ze wspólnych zmiennych.

Wśród zmiennych synchronizacji można zachować spójność sekwencyjną lub spójność procesora. Używając SC, wszystkie konkurujące zmienne synchronizacji powinny być przetwarzane w kolejności. Jednak w przypadku komputerów PC para konkurujących zmiennych musi być zgodna tylko z tą kolejnością. Młodsze przejęcia mogą mieć miejsce przed starszymi wydaniami.

Spójność wejścia

Jest to wariant modelu spójności wydania. Wymaga również użycia instrukcji nabywania i zwalniania w celu wyraźnego określenia wejścia lub wyjścia do sekcji krytycznej. Jednak w ramach spójności wpisów do każdej współdzielonej zmiennej przypisywana jest specyficzna dla niej zmienna synchronizacji. W ten sposób tylko wtedy, gdy akwizycja jest zmienna x, wszystkie operacje związane z x muszą być wykonane w odniesieniu do tego procesora. Pozwala to na jednoczesne wykonywanie różnych krytycznych sekcji różnych współdzielonych zmiennych. Nie można zobaczyć współbieżności dla operacji krytycznych na tej samej zmiennej udostępnionej. Taki model spójności przyda się, gdy jednocześnie można przetwarzać różne elementy macierzy.

Ogólna spójność

W ogólnej spójności wszystkie kopie lokalizacji pamięci są ostatecznie identyczne po zakończeniu zapisu wszystkich procesów.

Lokalna spójność

W spójności lokalnej każdy proces wykonuje swoje własne operacje w kolejności określonej przez jego program. Nie ma ograniczeń co do kolejności, w której wydają się być wykonywane operacje zapisu innych procesów. Spójność lokalna jest najsłabszym modelem spójności w systemach pamięci współdzielonej.

Inne modele konsystencji

Niektóre inne modele spójności są następujące:

Kilka innych modeli spójności zostało opracowanych w celu wyrażenia ograniczeń w odniesieniu do porządkowania lub widoczności operacji lub do radzenia sobie z określonymi założeniami dotyczącymi błędów.

Zrelaksowane modele spójności pamięci

Niektóre różne modele spójności można zdefiniować, rozluźniając jedno lub więcej wymagań w spójności sekwencyjnej, zwanych modelami zrelaksowanej spójności. Te modele spójności nie zapewniają spójności pamięci na poziomie sprzętu. W rzeczywistości programiści są odpowiedzialni za implementację spójności pamięci poprzez zastosowanie technik synchronizacji. Powyższe modele są klasyfikowane na podstawie czterech kryteriów i są szczegółowo omówione.

Istnieją cztery porównania określające zrelaksowaną konsystencję:

Relaks
Jednym ze sposobów kategoryzacji rozluźnionej konsystencji jest zdefiniowanie, które wymagania konsystencji sekwencyjnej są złagodzone. Możemy mieć mniej rygorystyczne modele, rozluźniając albo porządek programu, albo wymagania atomowości zapisu zdefiniowane przez Adve i Gharachorloo, 1996. Kolejność programu gwarantuje, że każdy proces wysyła żądanie pamięci uporządkowane przez jego program, a atomowość zapisu określa, że ​​żądania pamięci są obsługiwane na podstawie kolejności jednej kolejki FIFO. W rozluźniającej kolejności programu można złagodzić dowolną lub wszystkie kolejność par operacji, zapis po zapisie, odczyt po zapisie lub odczyt/zapis po odczycie. W zrelaksowanym modelu niepodzielności zapisu proces może wyświetlać własne zapisy przed innymi procesorami.
Synchronizacja a brak synchronizacji
Model synchronizujący można zdefiniować, dzieląc dostępy do pamięci na dwie grupy i przypisując każdej grupie różne ograniczenia spójności, biorąc pod uwagę, że jedna grupa może mieć słaby model spójności, podczas gdy druga potrzebuje bardziej restrykcyjnego modelu spójności. Natomiast model niezsynchronizowany przypisuje ten sam model spójności do typów dostępu do pamięci.
Problemy a oparte na widokach
Metoda Issue zapewnia sekwencyjną symulację spójności poprzez zdefiniowanie ograniczeń dla procesów w zakresie wydawania operacji pamięciowych. Natomiast metoda widoku opisuje ograniczenia widoczności kolejności zdarzeń dla procesów.
Względna siła modelu
Niektóre modele spójności są bardziej restrykcyjne niż inne. Innymi słowy, modele ścisłej spójności wymuszają więcej ograniczeń jako wymagania dotyczące spójności. Siłę modelu można określić za pomocą porządku programu lub złagodzenia atomowości, a także można porównać siłę modeli. Niektóre modele są bezpośrednio powiązane, jeśli stosują te same lub więcej rozluźnień. Z drugiej strony modele, które rozluźniają różne wymagania, nie są bezpośrednio powiązane.

Spójność sekwencyjna ma dwa wymagania: porządek programu i atomowość zapisu. Różne modele zrelaksowanej konsystencji można uzyskać, rozluźniając te wymagania. Odbywa się to tak, że wraz z rozluźnionymi ograniczeniami wydajność wzrasta, ale programista jest odpowiedzialny za implementację spójności pamięci poprzez zastosowanie technik synchronizacji i musi dobrze rozumieć sprzęt.

Potencjalne relaksacje:

  • Napisz, aby odczytać kolejność programu
  • Napisz, aby napisać kolejność programu
  • Czytaj, aby czytać i czytać, aby pisać rozkazy programu

Modele relaksacyjne

Poniższe modele to niektóre modele o swobodnej konsystencji:

Zrelaksowany pisz do czytania

Podejściem do poprawy wydajności na poziomie sprzętowym jest rozluźnienie PO zapisu, po którym następuje odczyt, który skutecznie ukrywa opóźnienia operacji zapisu. Optymalizacja, na której opiera się ten rodzaj relaksacji, polega na tym, że kolejne odczyty mogą być w swobodnej kolejności w stosunku do poprzednich zapisów z procesora. Z powodu tego rozluźnienia niektóre programy, takie jak XXX, mogą nie dawać wyników SC z powodu tego rozluźnienia. Podczas gdy programy takie jak YYY nadal powinny dawać spójne wyniki ze względu na egzekwowanie pozostałych ograniczeń kolejności programów.

Do tej kategorii należą trzy modele. Model IBM 370 to najbardziej rygorystyczny model. Odczyt może być zakończony przed wcześniejszym zapisem na inny adres, ale zabrania się zwracania wartości zapisu, chyba że wszystkie procesory widziały zapis. Model SPARC V8 total store ordering model (TSO) częściowo rozluźnia model IBM 370, umożliwia odczytowi zwrócenie wartości zapisu własnego procesora w stosunku do innych zapisów do tej samej lokalizacji, tj. zwraca wartość własnego zapisu przed inni to widzą. Podobnie jak w poprzednim modelu, nie może zwrócić wartości zapisu, chyba że wszystkie procesory widziały zapis. Model spójności procesora (PC) jest najbardziej zrelaksowanym z trzech modeli i łagodzi oba ograniczenia tak, że odczyt może zakończyć się przed wcześniejszym zapisem, nawet zanim stanie się widoczny dla innych procesorów.

W przykładzie A wynik jest możliwy tylko w IBM 370, ponieważ odczyt(A) nie jest wysyłany do czasu zakończenia zapisu(A) w tym procesorze. Z drugiej strony wynik ten jest możliwy w TSO i PC, ponieważ umożliwiają one odczyty flag przed zapisem flag w pojedynczym procesorze.

W przykładzie B wynik jest możliwy tylko z komputerem PC, ponieważ pozwala P2 zwrócić wartość zapisu, zanim będzie on widoczny dla P3. W pozostałych dwóch modelach nie będzie to możliwe.

Aby zapewnić sekwencyjną spójność w powyższych modelach, do ręcznego wymuszenia ograniczenia używa się siatek bezpieczeństwa lub ogrodzeń. Model IBM370 ma kilka wyspecjalizowanych instrukcji serializacji, które są ręcznie umieszczane między operacjami. Instrukcje te mogą składać się z instrukcji pamięciowych lub instrukcji nie-pamięciowych, takich jak rozgałęzienia. Z drugiej strony modele TSO i PC nie zapewniają sieci bezpieczeństwa, ale programiści mogą nadal używać operacji odczytu-modyfikacji-zapisu, aby wyglądało na to, że porządek programu jest nadal utrzymywany między zapisem a kolejnym odczytem. W przypadku OSP, PO wydaje się być utrzymana, jeśli R lub W, które są już częścią R-modyfikacja-W, jest zastępowane przez R-modyfikacja-W, wymaga to, aby W w R-modyfikacja-W była 'dummy', który zwraca odczytaną wartość. Podobnie dla PC, PO wydaje się być utrzymany, jeśli odczyt jest zastąpiony zapisem lub jest już częścią R-modify-W.

Optymalizacji kompilatora nie można jednak przeprowadzić po skorzystaniu z samej relaksacji. Optymalizacje kompilatora wymagają pełnej elastyczności zmiany kolejności dowolnych dwóch operacji w PO, więc możliwość zmiany kolejności zapisu względem odczytu nie jest w tym przypadku wystarczająco pomocna.

Przykład A
P 1 P 2
A = flaga1 = flaga2 = 0
flaga1 = 1 flaga2 = 1
A = 1 A = 2
reg1 = A reg3 = A
reg2 = flaga2 reg4 = flaga1
reg1 = 1; reg3 = 2, reg2 = reg4 = 0
Przykład B
P 1 P 2 P 3
A = B = 0
A = 1
jeśli (A == 1)
B = 1 jeśli (B == 1)
reg1 = A
B = 1, reg1 = 0

Zrelaksowany pisz do czytania i pisz do pisania

Niektóre modele jeszcze bardziej rozluźniają porządek programu, rozluźniając nawet ograniczenia porządkowe między zapisami w różnych lokalizacjach. Model częściowego zamawiania w sklepie SPARC V8 (PSO) jest jedynym przykładem takiego modelu. Zdolność do potoku i nakładania zapisów w różnych lokalizacjach z tego samego procesora jest kluczową optymalizacją sprzętu, którą umożliwia PSO. PSO jest podobny do TSO pod względem wymagań atomowych, ponieważ umożliwia procesorowi odczytanie wartości własnego zapisu i uniemożliwia innym procesorom odczytanie zapisu innego procesora, zanim zapis będzie widoczny dla wszystkich innych procesorów. Porządek programu między dwoma zapisami jest utrzymywany przez PSO przy użyciu wyraźnej instrukcji STBAR. STBAR jest umieszczany w buforze zapisu w implementacjach z buforami zapisu FIFO. Licznik jest używany do określenia, kiedy wszystkie zapisy przed instrukcją STBAR zostały zakończone, co wyzwala zapis do systemu pamięci w celu zwiększenia licznika. Potwierdzenie zapisu zmniejsza licznik, a gdy licznik osiągnie 0, oznacza to, że wszystkie poprzednie zapisy zostały zakończone.

W przykładach A i B PSO dopuszcza oba te niesekwencyjnie spójne wyniki. Sieć bezpieczeństwa, którą zapewnia PSO, jest podobna do sieci TSO, narzuca porządek programu od zapisu do odczytu i wymusza atomowość zapisu.

Podobnie jak w poprzednich modelach, złagodzenia dozwolone przez PSO nie są wystarczająco elastyczne, aby były przydatne do optymalizacji kompilatora, która wymaga znacznie bardziej elastycznej optymalizacji.

Relaksujące czytanie i czytanie, aby pisać rozkazy programu

W niektórych modelach wszystkie operacje w różnych lokalizacjach są zrelaksowane. Odczyt lub zapis można zmienić w odniesieniu do innego odczytu lub zapisu w innej lokalizacji. Słaby zamawiania mogą być klasyfikowane w tej kategorii, a dwa typy modeli konsystencji uwalnianiu (RCsc i RCpc) pochodzić również pod tym modelu. W ramach tej kategorii relaksu proponowane są również trzy komercyjne architektury: modele Digital Alpha, SPARC V9 zrelaksowany porządek pamięci (RMO) oraz modele IBM PowerPC. Wszystkie te modele umożliwiają zmianę kolejności odczytów do tej samej lokalizacji, z wyjątkiem Digital Alpha. Modele te naruszają kolejność sekwencyjną w przykładach A i B. Dodatkowe złagodzenie dozwolone w tych modelach, którego nie ma w poprzednich modelach, polega na tym, że operacje pamięciowe po operacji odczytu mogą nakładać się i zmieniać kolejność względem odczytu. Wszystkie te modele, oczekuj RCpc i PowerPC, pozwalają odczytowi zwrócić wartość wcześniejszego zapisu innego procesora. Z perspektywy programisty wszystkie te modele muszą zachować iluzję atomowości zapisu, nawet jeśli pozwalają procesorowi na wczesne odczytanie własnego zapisu.

Modele te można podzielić na dwie kategorie w zależności od rodzaju dostarczonej siatki bezpieczeństwa. Widać tutaj konieczność starannie pisanych programów. Charakter synchronizacji pomaga kategoryzować modele o słabym uporządkowaniu, RCsc i RCpc. Modele Alpha, RMO i PowerPC udostępniają instrukcje ogrodzenia, dzięki czemu porządek programu może być narzucony między różnymi operacjami pamięci.

Słabe zamówienie

Przykładem modelu, który rozluźnia większość powyższych ograniczeń (z wyjątkiem wczesnego czytania cudzych tekstów) jest słabe porządkowanie. Klasyfikuje operacje pamięciowe na dwie kategorie: operacje na danych i operacje synchronizacji . Aby wymusić porządek programu, programista musi znaleźć przynajmniej jedną operację synchronizacji w programie. Założenie, przy którym to działa, jest takie, że zmiana kolejności operacji pamięciowych na regiony danych między operacjami synchronizacji nie wpływa na wynik programu. Działają one po prostu jako siatka bezpieczeństwa do egzekwowania porządku programu. Sposób, w jaki to działa, polega na tym, że licznik śledzi liczbę operacji na danych i dopóki ten licznik nie osiągnie zera, operacja synchronizacji nie zostanie wydana. Co więcej, nie są wykonywane żadne dalsze operacje na danych, dopóki wszystkie poprzednie synchronizacje nie zostaną zakończone. Operacje pamięciowe pomiędzy dwiema zmiennymi synchronizacji mogą się nakładać i zmieniać ich kolejność bez wpływu na poprawność programu. Model ten zapewnia, że ​​atomowość zapisu jest zawsze zachowana, dlatego nie jest wymagana dodatkowa siatka bezpieczeństwa w przypadku słabego uporządkowania.

Spójność uwalniania: RCsc i RCpc

Istnieją dwa typy spójności wydań: spójność wydań ze spójnością sekwencyjną (RCsc) oraz spójność wydań ze spójnością procesora (RCpc). Ten ostatni typ oznacza, jaki rodzaj spójności jest stosowany do operacji wymienionych poniżej jako specjalne.

Istnieją specjalne (por. zwykłe) operacje pamięciowe, które same składają się z dwóch klas operacji: operacji synchronizacji lub nsync . Te ostatnie są operacjami niewykorzystywanymi do synchronizacji; te pierwsze są i składają się z operacji nabycia i wydania . Pozyskiwanie jest w rzeczywistości operacją odczytu pamięci wykorzystywaną do uzyskania dostępu do pewnego zestawu współdzielonych lokalizacji. Z drugiej strony Release jest operacją zapisu, która jest wykonywana w celu udzielenia pozwolenia na dostęp do udostępnionych lokalizacji.

W przypadku spójności sekwencyjnej (RCsc) ograniczenia są następujące:

  • nabyć → wszystkie,
  • wszystkie → zwolnienie,
  • specjalny → specjalny.

Dla spójności procesora (RCpc) porządek zapisu do odczytu programu jest rozluźniony, mając ograniczenia:

  • nabyć → wszystkie,
  • wszystkie → zwolnienie,
  • specjalne → specjalne (z wyjątkiem sytuacji, gdy po specjalnym zapisie następuje specjalny odczyt).

Uwaga: powyższa notacja A → B implikuje, że jeśli operacja A poprzedza B w kolejności programu, to kolejność programu jest wymuszana.

Alpha, RMO i PowerPC

Te trzy komercyjne architektury zawierają wyraźne instrukcje dotyczące ogrodzenia jako sieci bezpieczeństwa. Model Alpha udostępnia dwa typy instrukcji ogrodzenia: barierę pamięci (MB) i barierę pamięci zapisu (WMB). Operacja MB może być użyta do utrzymania porządku programu dowolnej operacji pamięci przed MB z operacją pamięci za barierą. Podobnie WMB utrzymuje porządek programu tylko wśród zapisów. Model SPARC V9 RMO udostępnia instrukcję MEMBAR, którą można dostosować, aby uporządkować poprzednie odczyty i zapisy w odniesieniu do przyszłych operacji odczytu i zapisu. Nie ma potrzeby używania odczytu-modyfikacji-zapisu, aby osiągnąć tę kolejność, ponieważ instrukcja MEMBAR może być użyta do uporządkowania zapisu w odniesieniu do kolejnego odczytu. Model PowerPC wykorzystuje pojedynczą instrukcję ogrodzenia zwaną instrukcją SYNC. Jest ona podobna do instrukcji MB, ale z małym wyjątkiem, że odczyty mogą wystąpić poza kolejnością programu, nawet jeśli SYNC jest umieszczony między dwoma odczytami w tej samej lokalizacji. Model ten różni się również od Alpha i RMO pod względem atomowości. Pozwala to na zobaczenie zapisu przed zakończeniem odczytu. Kombinacja operacji odczytu, modyfikacji i zapisu może być wymagana, aby stworzyć iluzję niepodzielności zapisu.

Modele pamięci transakcyjnej

Model pamięci transakcyjnej to połączenie modeli spójności pamięci podręcznej i spójności pamięci jako modelu komunikacji dla systemów pamięci współdzielonej obsługiwanych przez oprogramowanie lub sprzęt; model pamięci transakcyjnej zapewnia zarówno spójność pamięci, jak i spójność pamięci podręcznej. Transakcja to sekwencja operacji wykonywanych przez proces, który przekształca dane z jednego spójnego stanu w inny. Transakcja albo zostaje zatwierdzona, gdy nie ma konfliktu, albo zostaje przerwana. W zatwierdzeniach wszystkie zmiany są widoczne dla wszystkich innych procesów po zakończeniu transakcji, a przerwania odrzucają wszystkie zmiany. W porównaniu ze zrelaksowanymi modelami spójności model transakcyjny jest łatwiejszy w użyciu i może zapewnić wyższą wydajność niż model spójności sekwencyjnej.

Spójność i replikacja

Tanenbaum i in., 2007 określają dwa główne powody replikacji; niezawodność i wydajność. Niezawodność w zreplikowanym systemie plików można osiągnąć, przełączając się na inną replikę w przypadku awarii bieżącej repliki. Replikacja chroni również dane przed uszkodzeniem, udostępniając wiele kopii danych w różnych replikach. Poprawia również wydajność poprzez dzielenie pracy. Chociaż replikacja może poprawić wydajność i niezawodność, może powodować problemy ze spójnością między wieloma kopiami danych. Wiele kopii jest spójnych, jeśli operacja odczytu zwraca tę samą wartość ze wszystkich kopii, a operacja zapisu jako pojedyncza operacja niepodzielna (transakcja) aktualizuje wszystkie kopie przed wykonaniem jakiejkolwiek innej operacji. Tanenbaum, Andrew i Maarten Van Steen, 2007 określają ten rodzaj spójności jako ścisłą spójność zapewnianą przez synchroniczną replikację. Jednak stosowanie synchronizacji globalnych w celu zachowania spójności wszystkich kopii jest kosztowne. Jednym ze sposobów zmniejszenia kosztów globalnej synchronizacji i poprawy wydajności może być osłabienie ograniczeń spójności.

Modele spójności zorientowane na dane

Tanenbaum i in., 2007 definiuje model spójności jako kontrakt pomiędzy oprogramowaniem (procesy) a implementacją pamięci (magazyn danych). Ten model gwarantuje, że jeśli oprogramowanie przestrzega pewnych zasad, pamięć działa poprawnie. Ponieważ w systemie bez zegara globalnego zdefiniowanie ostatniej operacji wśród zapisów jest trudne, można nałożyć pewne ograniczenia na wartości, które mogą zostać zwrócone przez operację odczytu.

Konsekwentne porządkowanie operacji

Niektóre modele spójności, takie jak sekwencyjne i przyczynowe modele spójności, zajmują się kolejnością operacji na udostępnionych replikowanych danych w celu zapewnienia spójności. W tych modelach wszystkie repliki muszą uzgodnić spójną globalną kolejność aktualizacji.

Spójność sekwencyjna

Celem modeli spójności zorientowanych na dane jest zapewnienie spójnego widoku magazynu danych, w którym procesy mogą przeprowadzać współbieżne aktualizacje. Jednym z ważnych modeli spójności zorientowanych na dane jest spójność sekwencyjna zdefiniowana przez Lamporta (1979). Tanenbaum et al., 2007 definiuje spójność sekwencyjną w następujących warunkach:

Wynik każdego wykonania jest taki sam, jak gdyby operacje (odczytu i zapisu) przez wszystkie procesy w magazynie danych zostały wykonane w pewnej kolejności sekwencyjnej, a operacje każdego pojedynczego procesu pojawiają się w tej kolejności w kolejności określonej przez jego program.

Adve i Gharachorloo, 1996 definiują dwa wymagania do wdrożenia spójności sekwencyjnej; porządek programu i atomowość zapisu.

  • Kolejność programu: Kolejność programu gwarantuje, że każdy proces wysyła żądanie pamięci uporządkowane przez jego program.
  • Niepodzielność zapisu: Niepodzielność zapisu definiuje, że żądania pamięci są obsługiwane na podstawie kolejności pojedynczej kolejki FIFO.

W spójności sekwencyjnej nie ma pojęcia czasu ani ostatnich operacji zapisu. Istnieje kilka operacji przeplatania, które są takie same dla wszystkich procesów. Proces może zobaczyć operacje zapisu wszystkich procesów, ale może tylko zobaczyć własne operacje odczytu.

Linearyzowalność (pamięć atomowa) można zdefiniować jako sekwencyjną spójność z ograniczeniem czasu rzeczywistego, biorąc pod uwagę czas rozpoczęcia i czas zakończenia dla każdej operacji. Wykonanie można zlinearyzować, jeśli każda operacja odbywa się w linearyzowanej kolejności, umieszczając punkt między jej czasem rozpoczęcia a czasem zakończenia i gwarantuje spójność sekwencyjną.

Spójność przyczynowa

Konsystencja przyczynowy zdefiniowane przez Hutto i Ahamad 1990 jest słabszy niż spójność modelu sekwencyjnego konsystencji poprzez dokonanie rozróżnienia pomiędzy przyczynowo związane operacji i tych, które nie są powiązane. Na przykład, jeśli zdarzenie b zaczyna obowiązywać od wcześniejszego zdarzenia a, spójność przyczynowa gwarantuje, że wszystkie procesy widzą zdarzenie b po zdarzeniu a.

Tanenbaum i in., 2007 określają, że magazyn danych jest uważany za zgodny przyczynowo pod następującym warunkiem:

Zapisy, które są potencjalnie powiązane przyczynowo, muszą być widziane przez wszystkie procesy w tej samej kolejności. Współbieżne zapisy mogą być wyświetlane w różnej kolejności na różnych komputerach.

Ostateczna spójność

Ewentualna konsekwencja jest słabym modelem spójność systemu z braku jednoczesnej aktualizacji. Określa, że ​​jeśli żadna aktualizacja nie trwa bardzo długo, wszystkie repliki w końcu stają się spójne.

Większość współdzielonych zdecentralizowanych baz danych posiada ostateczny model spójności, albo BASE: w zasadzie dostępny; stan miękki; ostatecznie spójne lub połączenie KWASU i ZASADY czasami nazywane SÓL: sekwencyjne; Zgoda; księgowane; odporny na manipulacje, a także symetryczny; bez administratora; księgowane; i zgodne z czasem.

Operacje grupujące

W operacji grupowania dostępy do zmiennych synchronizacji są sekwencyjnie spójne. Proces może uzyskać dostęp do zmiennej synchronizacji, że wszystkie poprzednie zapisy zostały zakończone. Innymi słowy, dostęp do zmiennych synchronizacji nie jest dozwolony, dopóki wszystkie operacje na zmiennych synchronizacji nie zostaną całkowicie wykonane.

Ciągła spójność

Ciągła spójność jest zdefiniowana później w sekcji protokołu spójności.

Modele spójności zorientowane na klienta

W systemach rozproszonych zachowanie sekwencyjnej spójności w celu kontrolowania współbieżnych operacji jest niezbędne. W niektórych specjalnych magazynach danych bez równoczesnych aktualizacji modele spójności zorientowane na klienta mogą radzić sobie z niespójnościami w mniej kosztowny sposób. Poniższe modele to niektóre modele spójności zorientowane na klienta:

Monotoniczna spójność odczytu

Tanenbaum et al., 2007 definiuje monotoniczną spójność odczytu w następujący sposób:

„Jeśli proces odczytuje wartość elementu danych x, każda kolejna operacja odczytu x przez ten proces zawsze zwróci tę samą lub nowszą wartość”.

Monotoniczna spójność odczytu gwarantuje, że po odczytaniu przez proces wartości elementu danych x w czasie t, nigdy nie zobaczy starszej wartości tego elementu danych.

Monotoniczna spójność zapisu

Warunek spójności zapisu monotonicznego jest zdefiniowany przez Tanenbauma i in., 2007 w następujący sposób:

"Operacja zapisu przez proces na elemencie danych X jest zakończona przed jakąkolwiek kolejną operacją zapisu na X przez ten sam proces."

Spójność odczytu i zapisu

Wartość zapisana przez proces na elemencie danych X będzie zawsze dostępna dla kolejnej operacji odczytu wykonywanej przez ten sam proces na elemencie danych X.

Pisze-podąża-odczytuje spójność

W przypadku spójności zapisów, które następują po odczytach, aktualizacje są propagowane po wykonaniu poprzednich operacji odczytu. Tanenbaum et al., 2007 definiuje następujący warunek spójności zapisy-podążanie-odczyty:

„Operacja zapisu przez proces na elemencie danych x po poprzedniej operacji odczytu na x przez ten sam proces ma gwarantowane przeprowadzenie na tej samej lub nowszej wartości x, która została odczytana”.

Protokoły spójności

Implementacja modelu spójności jest zdefiniowana przez protokół spójności. Tanenbaum et al., 2007 ilustruje niektóre protokoły spójności dla modeli zorientowanych na dane.

Ciągła spójność

Ciągła spójność wprowadzona przez Yu i Vahdat (2000). W tym modelu semantyka spójności aplikacji jest opisana za pomocą conits w aplikacji. Ponieważ wymagania dotyczące spójności mogą się różnić w zależności od semantyki aplikacji, Yu i Vahdat (2000) uważają, że predefiniowany model jednolitej spójności może nie być odpowiednim podejściem. Wniosek powinien określać wymagania dotyczące spójności, które spełniają semantykę aplikacji. W tym modelu aplikacja określa każde wymaganie spójności jako conits (skrót jednostek spójności). Konit może być konsystencją fizyczną lub logiczną i służy do pomiaru konsystencji. Tanenbaum et al., 2007 opisuje pojęcie konika na przykładzie.

Istnieją trzy niespójności, które mogą być tolerowane przez aplikacje.

Odchylenie wartości liczbowych
Odchylenie liczbowe ogranicza różnicę między wartością conit a wartością względną ostatniej aktualizacji. Do zapisów można przypisać wagę, która określa ważność zapisów w określonej aplikacji. Całkowite wagi niewidocznych zapisów dla conit można zdefiniować jako odchylenie liczbowe w aplikacji. Istnieją dwa różne rodzaje odchyleń liczbowych; bezwzględne i względne odchylenie liczbowe.
Odchylenie w zamawianiu
Odchylenie uporządkowania to rozbieżność między lokalną kolejnością zapisów w replice a ich względną kolejnością w ostatecznym obrazie końcowym.
Odchylenie nieaktualności między replikami
Odchylenie nieaktualności definiuje ważność najstarszego zapisu poprzez ograniczenie różnicy między czasem bieżącym a czasem najstarszego zapisu na obszarze niewidocznym lokalnie. Każdy serwer ma lokalną kolejkę o niepewnym zapisie, która jest wymagana do ustalenia i zastosowania rzeczywistej kolejności na conit. Maksymalna długość niepewnej kolejki zapisów to granica odchylenia kolejności. Gdy liczba zapisów przekroczy limit, zamiast akceptować nowy przesłany zapis, serwer będzie próbował dokonać niepewnych zapisów, komunikując się z innymi serwerami w oparciu o kolejność wykonywania zapisów.

Jeśli wszystkie trzy granice odchyleń są ustawione na zero, model ciągłej spójności jest silną spójnością.

Protokoły oparte na podstawach

Podstawowy protokół kopii zapasowej
Protokół podstawowej kopii zapasowej (zapis lokalny)

Protokoły oparte na podstawach można uznać za klasę protokołów spójności, które są prostsze do zaimplementowania. Na przykład porządkowanie sekwencyjne jest popularnym modelem spójności, gdy bierze się pod uwagę spójne porządkowanie operacji. Kolejność sekwencyjna można określić jako protokół oparty na podstawowym. W tych protokołach dla każdego elementu danych w magazynie danych istnieje powiązana podstawa, która koordynuje operacje zapisu na tym elemencie danych.

Protokoły zdalnego zapisu

W najprostszym protokole podstawowym obsługującym replikację, znanym również jako protokół podstawowej kopii zapasowej, operacje zapisu są przekazywane do jednego serwera, a operacje odczytu mogą być wykonywane lokalnie.

Przykład: Tanenbaum et al., 2007 podaje przykład protokołu podstawowej kopii zapasowej. Schemat protokołu podstawowej kopii zapasowej przedstawia przykład tego protokołu. Gdy klient żąda zapisu, żądanie zapisu jest przekazywane do serwera głównego. Serwer główny wysyła żądanie do kopii zapasowych w celu wykonania aktualizacji. Serwer następnie otrzymuje potwierdzenie aktualizacji ze wszystkich kopii zapasowych i wysyła potwierdzenie zakończenia zapisów do klienta. Każdy klient może lokalnie odczytać ostatnią dostępną aktualizację. Wadą tego protokołu jest to, że klient, który wysyła żądanie aktualizacji, może być zmuszony do czekania tak długo, aby otrzymać potwierdzenie, aby kontynuować. Ten problem można rozwiązać, przeprowadzając aktualizacje lokalnie, a następnie prosząc inne kopie zapasowe o wykonanie aktualizacji. Nieblokujący protokół podstawowej kopii zapasowej nie gwarantuje spójności aktualizacji na wszystkich serwerach kopii zapasowych. Poprawia jednak wydajność. W protokole podstawowej kopii zapasowej wszystkie procesy będą widzieć tę samą kolejność operacji zapisu, ponieważ ten protokół porządkuje wszystkie przychodzące zapisy na podstawie globalnie unikalnego czasu. Protokoły blokujące gwarantują, że procesy wyświetlają wynik ostatniej operacji zapisu.
Protokoły zapisu lokalnego

W protokołach zapisu lokalnego opartego na podstawowym systemie kopia podstawowa przemieszcza się między procesami, które chcą wykonać aktualizację. Aby zaktualizować element danych, proces najpierw przenosi go do jego lokalizacji. W rezultacie w tym podejściu kolejne operacje zapisu mogą być wykonywane lokalnie, podczas gdy każdy proces może odczytywać swoją lokalną kopię elementów danych. Po zakończeniu aktualizacji podstawowej aktualizacja jest przesyłana do innych replik i wszystkie wykonują aktualizację lokalnie. To nieblokujące podejście może prowadzić do poprawy. Diagram protokołu zapisu lokalnego przedstawia podejście do zapisu lokalnego w protokołach opartych na podstawowym systemie. Proces żąda operacji zapisu w elemencie danych x. Bieżący serwer jest uważany za nowy podstawowy dla elementu danych x. Operacja zapisu jest wykonywana i po zakończeniu żądania serwer podstawowy wysyła żądanie aktualizacji do innych serwerów zapasowych. Każda kopia zapasowa wysyła potwierdzenie do serwera podstawowego po zakończeniu operacji aktualizacji.

Replikowane protokoły zapisu

W protokołach zapisu replikowanego, w przeciwieństwie do protokołu podstawowego, wszystkie aktualizacje są przeprowadzane we wszystkich replikach.

Aktywna replikacja

W aktywnej replikacji z każdą repliką związany jest proces, który wykonuje operację zapisu. Innymi słowy, aktualizacje są wysyłane do każdej repliki w formie operacji w celu wykonania. Wszystkie aktualizacje muszą być wykonywane w tej samej kolejności we wszystkich replikach. W rezultacie wymagany jest całkowicie uporządkowany mechanizm multiemisji. Istnieje problem ze skalowalnością implementacji takiego mechanizmu multiemisji w dużych systemach rozproszonych. Istnieje inne podejście, w którym każda operacja jest wysyłana do centralnego koordynatora (sekwencer). Koordynator najpierw przypisuje numer kolejny każdej operacji, a następnie przekazuje operację do wszystkich replik. Drugie podejście nie może również rozwiązać problemu skalowalności.

Protokoły oparte na kworum

Głosowanie może być innym podejściem w protokołach z replikowanym zapisem. W tym podejściu klient żąda i otrzymuje uprawnienia od wielu serwerów w celu odczytu i zapisu zreplikowanych danych. Jako przykład załóżmy, że w rozproszonym systemie plików plik jest replikowany na N serwerach. Aby zaktualizować plik, klient musi wysłać żądanie do co najmniej N/2 + 1 w celu wyrażenia zgody na wykonanie aktualizacji. Po zawarciu umowy zmiany są stosowane do pliku, a do zaktualizowanego pliku zostaje przypisany nowy numer wersji. Podobnie, w przypadku odczytu zreplikowanego pliku, klient wysyła żądanie do N/2 + 1 serwerów w celu otrzymania skojarzonego numeru wersji z tych serwerów. Operacja odczytu jest zakończona, jeśli wszystkie otrzymane numery wersji są najnowszą wersją.

Protokoły spójności pamięci podręcznej

W zreplikowanym systemie plików protokół spójności pamięci podręcznej zapewnia spójność pamięci podręcznej, podczas gdy pamięci podręczne są generalnie kontrolowane przez klientów. W wielu podejściach spójność pamięci podręcznej jest zapewniana przez podstawowy sprzęt. Niektóre inne podejścia w systemach rozproszonych opartych na oprogramowaniu pośredniczącym stosują rozwiązania programowe w celu zapewnienia spójności pamięci podręcznej.

Modele spójności pamięci podręcznej mogą różnić się strategiami wykrywania spójności, które definiują, kiedy występują niespójności. Istnieją dwa podejścia do wykrycia niespójności; rozwiązania statyczne i dynamiczne. W rozwiązaniu statycznym kompilator określa, które zmienne mogą powodować niespójność pamięci podręcznej. Tak więc kompilator wymusza instrukcję, aby uniknąć problemu niespójności. W rozwiązaniu dynamicznym serwer sprawdza w czasie wykonywania pod kątem niespójności, aby kontrolować spójność danych w pamięci podręcznej, które uległy zmianie po ich zbuforowaniu.

Strategia wymuszania spójności jest kolejnym protokołem spójności pamięci podręcznej. Określa, jak zapewnić spójność w pamięciach podręcznych przy użyciu kopii znajdujących się na serwerze. Jednym ze sposobów zachowania spójności danych jest nigdy nie buforowanie udostępnionych danych. Serwer może przechowywać dane i zastosować pewien protokół spójności, taki jak protokoły podstawowe, aby zapewnić spójność współdzielonych danych. W tym rozwiązaniu tylko dane prywatne mogą być buforowane przez klientów. W przypadku, gdy współdzielone dane są buforowane, istnieją dwa podejścia w celu wymuszenia spójności pamięci podręcznej.

W pierwszym podejściu, gdy współdzielone dane są aktualizowane, serwer przekazuje unieważnienie do wszystkich pamięci podręcznych. W drugim podejściu propagowana jest aktualizacja. Większość systemów pamięci podręcznej stosuje te dwa podejścia lub dynamicznie wybiera między nimi.

Zobacz też

Bibliografia

Dalsza lektura

Zewnętrzne linki