Wspólny rejestr - Shared register

W obliczeniach rozproszonych systemy pamięci współdzielonej i systemy przekazywania wiadomości to dwa sposoby komunikacji międzyprocesowej, które zostały intensywnie zbadane. W systemach z pamięcią współdzieloną procesy komunikują się poprzez dostęp do współdzielonych struktur danych. Dzielone (odczyt / zapis) zarejestrować , czasami nazywany po prostu rejestr, jest podstawowym rodzajem wspólną strukturę danych, która przechowuje wartość i ma dwie operacje: odczytu , która zwraca wartość przechowywaną w rejestrze i zapisu , który aktualizuje wartość przechowywane. Inne typy współdzielonych struktur danych obejmują odczyt-modyfikację-zapis, testowanie i ustawianie, porównanie i zamiana itp. Lokalizacja pamięci, do której uzyskuje się jednocześnie dostęp, jest czasami nazywana rejestrem.

Klasyfikacja

Rejestry można klasyfikować według warunku spójności, jaki spełniają przy równoczesnym dostępie, dziedziny możliwych wartości, które mogą być przechowywane, oraz liczby procesów, które mogą uzyskać dostęp za pomocą operacji odczytu lub zapisu , co prowadzi do łącznie 24 typów rejestrów.

Gdy odczyt i zapis odbywają się jednocześnie, wartość zwracana przez read może nie być jednoznacznie określona. Lamport zdefiniował trzy typy rejestrów: rejestry bezpieczne, rejestry regularne i rejestry atomowe . Operacja odczytu bezpiecznego rejestru może zwrócić dowolną wartość, jeśli jest współbieżna z operacją Write, i zwraca wartość zapisaną przez najnowszą operację zapisu , jeśli operacja odczytu nie nakłada się na żadną operację write . Zwykły rejestr różni się od bezpiecznego rejestru tym, że operacja odczytu może zwrócić wartość zapisaną przez ostatnio ukończoną operację zapisu lub operację zapisu, z którą się nakłada. Rejestr atomowy spełnia silniejszy warunek linearyzacji .

Rejestry można scharakteryzować liczbą procesów, do których można uzyskać dostęp za pomocą operacji odczytu lub zapisu . Rejestr z jednym zapisem (SW) może być zapisany tylko przez jeden proces, a rejestr z wieloma zapisami (MW) może być zapisany przez wiele procesów. Podobnie rejestr pojedynczego czytnika (SR) może być odczytywany tylko przez jeden proces, a rejestr wielokrotnego czytnika (MR) może być odczytywany przez wiele procesów. W przypadku rejestru SWSR nie jest konieczne, aby proces zapisu i proces odczytu były takie same.

Konstrukcje

Poniższy rysunek ilustruje konstrukcje krok po kroku od implementacji rejestru SWSR w asynchronicznym systemie przekazywania komunikatów do implementacji rejestru MWMR przy użyciu obiektu SW Snapshot . Ten rodzaj konstrukcji jest czasami nazywany symulacją lub emulacją. Na każdym etapie (z wyjątkiem Etapu 3) typ obiektu po prawej stronie może być zaimplementowany przez prostszy typ obiektu po lewej stronie. Konstrukcje poszczególnych etapów (z wyjątkiem Etapu 3) zostały pokrótce przedstawione poniżej. Istnieje artykuł, który omawia szczegóły konstruowania obiektów migawkowych .

${\displaystyle {\ce {{\operatorname {przekazywanie wiadomości} \atop (MP)~System}->[][{\tekst{etap 1}}]SWSR~atomowy->[][{\tekst{etap 2}}]SWMR->[][{\text{Etap 3}}]SW~snapshot->[][{\text{Etap 4}}]MWMR}}}$
 

Wspólny rejestr Etapy budowy

Implementację można linearyzować, jeśli dla każdego wykonania istnieje kolejność linearyzacji, która spełnia następujące dwie właściwości:

1. gdyby operacje były wykonywane sekwencyjnie w kolejności ich linearyzacji, zwróciłyby ten sam wynik, co w przypadku współbieżnego wykonania.
2. Jeśli operacja op1 kończy się przed rozpoczęciem operacji op2, to op1 pojawia się przed operacją op2 w linearyzacji.

Implementacja atomowego rejestru SWSR w systemie przekazywania komunikatów

Atomowy (linearyzowany) rejestr SWSR można zaimplementować w asynchronicznym systemie przekazywania komunikatów, nawet jeśli procesy mogą ulec awarii. Procesy nie mają limitu czasu na dostarczanie komunikatów do odbiorców lub wykonywanie lokalnych instrukcji. Innymi słowy, procesy nie potrafią odróżnić procesów, które reagują powoli lub po prostu ulegają awarii.

Wdrożenie Atomowego Rejestru SWSR w MP System

Implementacja podana przez Attiyę, Bar-Noya i Doleva wymaga n > 2 f , gdzie n to całkowita liczba procesów w systemie, a f to maksymalna liczba procesów, które mogą ulec awarii podczas wykonywania. Algorytm wygląda następująco:

WRITE(v)
  t++
  send (v,t) to all processes
  wait until getting (n-f) acknowledgements

READ()
  send read request to all processes
  wait until getting (n-f) responses of them
  choose v with the biggest t

Kolejność operacji jest linearyzacja: zlinearyzować zapisu S w kolejności, w jakiej występują i włóż odczyt po zapisie którego wartość powraca. Możemy sprawdzić, czy implementacja jest linearyzowalna. Możemy sprawdzić właściwość 2, zwłaszcza gdy op1 to write, op2 to read , a read następuje zaraz po zapisie . Możemy pokazać przez sprzeczność. Załóżmy, że odczyt nie widzi zapisu , a następnie zgodnie z implementacją musimy mieć dwa rozłączne zestawy rozmiarów ( n - f ) wśród n procesów. Czyli 2 * ( n - f ) ≤ n prowadzi do n ≤ 2 f , co przeczy faktowi , że n > 2 f . Czyli odczyt musi odczytać co najmniej jedną wartość zapisaną przez ten zapis .

Implementacja rejestru SWMR z rejestrów SWSR

Rejestr SWMR może być zapisywany tylko przez jeden proces, ale może być odczytywany przez wiele procesów.

Implementacja rejestru SWMR z wykorzystaniem rejestrów SWSR

Czytelnicy Pisarze	${\displaystyle R_{1}}$	${\displaystyle R_{2}}$	⋯	${\displaystyle R_{1}}$
${\displaystyle R_{1}}$	A[1,1]	A[1,2]	...	A[1,n]
${\displaystyle R_{2}}$	A[2,1]	A[2,2]	...	A[2,n]
⋮	...	...	...	...
${\ Displaystyle R_ {n}}$	A[n,1]	A[n,2]	...	A[n,n]
w	A[n+1,1]	A[n+1,2]	...	A[n+1,n]

Niech n będzie liczbą procesów, które mogą odczytać rejestr SWMR. Niech R _i , 0 < i ≤ n , odnoszą się do czytników rejestru SWMR. Niech w będzie pojedynczy pisarz SWMR. Rysunek po prawej pokazuje konstrukcję rejestru SWMR przy użyciu tablicy n ( n + 1) rejestrów SWSR. Tablicę oznaczamy przez A . Każdy rejestr SWSR A[ i , j ] jest zapisywalny przez R _{i ,} gdy 0 < i ≤ n i jest zapisywalny przez w , gdy i = n + 1 . Każdy rejestr SWSR A[ i , j ] jest odczytywany przez R _j . Poniżej przedstawiono implementacje odczytu i zapisu .

for j = i..n 
    t++
    write (v,t) in A[n+1,j]
end for

for k = 1..(n+1)
    (V[k],T[k]) <- read A[k,i]
end for
take k such that for all l, T[k] >= T[l]
r <- V[k]
t <- T[k]
for j=1..n
    write (r,t) in A[i,j]
end for
return r

Wartość t operacji jest wartością t, którą zapisuje, a operacje są linearyzowane przez wartości t. Jeśli zapis i odczyt mają tę samą wartość t, zamów zapis przed odczytem . Jeśli kilka odczytów ma te same wartości t, uporządkuj je według czasu rozpoczęcia.

Implementacja rejestru MWMR z obiektu SW Snapshot

Możemy użyć obiektu SW Snapshot o rozmiarze n do skonstruowania rejestru MWMR.

((v1, t1), ..., (vn, tn)) <- V.SCAN()
let t = max(t1, ..., tn) + 1
V.UPDATE(i, (v, t))

V.SCAN
return value with largest timestamp, in the result of the scan

Kolejność linearyzacji jest następująca. Uporządkuj operacje zapisu według wartości t. Jeśli kilka zapisów ma tę samą wartość t, uporządkuj operację z małym identyfikatorem procesu na początku. Wstaw odczyty zaraz po zapisie, których wartość zwracają, rozbijając powiązania według identyfikatora procesu, a jeśli nadal są powiązane, przerywaj powiązanie według czasu rozpoczęcia.

Zobacz też

• Rejestr sprzętu
• Rozproszona pamięć współdzielona
• Udostępnione obiekty migawkowe

Bibliografia