Rozproszona pamięć

Rozproszona pamięć

współdzielona

współdzielona

(ang. distributed shared

(ang. distributed shared

memory)

memory)

Rozproszone

Rozproszone

systemy operacyjne

systemy operacyjne

Ogólna charakterystyka DSM

Ogólna charakterystyka DSM

Cel stosowania DSM

Dostarczenie abstrakcji w postaci wspólnej wirtualnej przestrzeni

adresowej, potencjalnie dostępnej dla wszystkich węzłów

systemu rozproszonego.

Zalety:

 wygodny dla programisty paradygmat programowania

równoległego (nie ma konieczności przekazywania

komunikatów),

 skalowalność i łatwość rozbudowy,

 dostępność wirtualnej przestrzeni adresowej obejmującej

pamięci fizyczne wszystkich węzłów,

 możliwość uruchomienia w środowisku rozproszonym

programów równoległych zaprojektowanych dla środowisk

wieloprocesorowych z pamięcią współdzieloną.

Obsługa błędu strony w systemie pamięci

Obsługa błędu strony w systemie pamięci

wirtualnej

wirtualnej

procesor

adres

logiczny

s o

s

s — numer strony
r — numer ramki
o — przesunięcie

s — numer strony
r — numer ramki
o — przesunięcie

tablica

stron

n

urządzenie

wymiany

pamięć

pułapka

system

operacyjny

p

błąd

strony

Obsługa błędu strony w systemie pamięci

Obsługa błędu strony w systemie pamięci

wirtualnej

wirtualnej

procesor

adres

logiczny

s o

adres

fizyczny

r o

s

s — numer strony
r — numer ramki
o — przesunięcie

s — numer strony
r — numer ramki
o — przesunięcie

tablica

stron

p

pamięć

Obsługa błędu strony w systemie wirtualnej

Obsługa błędu strony w systemie wirtualnej

pamięci rozproszonej

pamięci rozproszonej

procesor

adres

logiczny

s o

s

s — numer strony
r — numer ramki
o — przesunięcie

s — numer strony
r — numer ramki
o — przesunięcie

tablica

stron

n

pamięć

pułapka

system

operacyjny

n

błąd

strony

Koncepcje dostępu do danych

Koncepcje dostępu do danych

 Dostęp zdalny – każdy dostęp do współdzielonego obiektu,

zlokalizowanego fizycznie w pamięci lokalnej innego węzła,
odbywa się przez sieć.

 Relokacja – możliwa jest zmiana fizycznej lokalizacji

współdzielonego obiektu, czyli umieszczenie go w pamięci
lokalnej węzła, w którym pojawiło się żądanie dostępu.

 Replikacja – obiekt logiczny może być jednocześnie

zlokalizowany fizycznie w pamięci lokalnej wielu węzłów, co
umożliwia równoległy dostęp do tego obiektu w wielu
węzłach.

Dostęp lokalny

Dostęp lokalny

sieć

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

w

ę

ze

ł

w

ę

z

e

ł

węzeł

zarządc
a DSM

Dostęp zdalny

Dostęp zdalny

sieć

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

w

ę

ze

ł

w

ę

z

e

ł

węzeł

zarządc
a DSM

Zdalny dostęp – charakterystyka

Zdalny dostęp – charakterystyka

 Stosunkowo prosta realizacja

 Problem efektywności — duży

czas dostępu do danych w
zdalnych węzłach

Relokacja

Relokacja

sieć

procesor

procesor

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

w

ę

ze

ł

w

ę

z

e

ł

węzeł

zarządc
a DSM

Relokacja

Relokacja

sieć

procesor

procesor

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

w

ę

ze

ł

w

ę

z

e

ł

węzeł

zarządc
a DSM

Relokacja

Relokacja

sieć

procesor

procesor

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

w

ę

ze

ł

w

ę

z

e

ł

węzeł

zarządc
a DSM

Relokacja – charakterystyka

Relokacja – charakterystyka

 Problem lokalizacji

 Problem rozmiaru i struktury

jednostki podlegającej relokacji

 Problem migotania (ang.

trashing,
ping-pong effect)

Replikacja

Replikacja

sieć

procesor

procesor

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

w

ę

ze

ł

w

ę

z

e

ł

węzeł

zarządc
a DSM

Replikacja

Replikacja

sieć

procesor

procesor

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

w

ę

ze

ł

w

ę

z

e

ł

węzeł

zarządc
a DSM

Replikacja

Replikacja

sieć

procesor

procesor

procesor

procesor

pamię

ć

lokaln

a

pamię

ć

lokaln

a

procesor

procesor

w

ę

ze

ł

w

ę

z

e

ł

węzeł

zarządc
a DSM

Replikacja - charakterystyka

Replikacja - charakterystyka

 Problem lokalizacji

 Problem rozmiaru i struktury

jednostki podlegającej replikacji

 Problem migotania

(ang. trashing,
ping-pong effect)

 Problem spójności

kopii (replik)

Struktura jednostki podlegającej replikacji

Struktura jednostki podlegającej replikacji

lub relokacji

lub relokacji

 Strona – fizyczne połączenie kilku odrębnych obiektów

logicznych w jedną jednostkę udostępnianą jako całość
przez DSM (problem fałszywego współdzielenia).

 Pojedyncza zmienna – duży jednostkowy koszt relokacji i

utrzymywania spójności.

 Obiekt (hermetyczna struktura danych udostępniana tylko

przez zdefiniowane metody) – możliwość optymalizacji w
strategii utrzymywania spójności w związku ze ściśle
określonym sposobem dostępu (poprzez metody).

Fałszywe współdzielenie

Fałszywe współdzielenie

Problem spójności replik - protokół

Problem spójności replik - protokół

koherencji

koherencji

 Protokół unieważniania danych (ang. invalidation protocol)

– niespójne repliki są usuwane z pamięci lokalnej.

 Protokół aktualizacji danych (ang. update protocol) –

niespójne repliki są aktualizowane.

Problem lokalizacji stron – system

Problem lokalizacji stron – system

IVY

IVY

 Statyczny scentralizowany mechanizm lokalizacji stron –

jeden zarządca stron.

 Statyczny rozproszony mechanizm lokalizacji stron –

identyfikacja zarządcy na podstawie numeru strony.

 Dynamiczny mechanizm lokalizacji stron – bazuje na

informacji o prawdopodobnych właścicielach stron. W razie
błędu strony wysyłane jest żądanie do prawdopodobnego
właściciela strony. Jeżeli odbiorca żądania nie jest
właścicielem strony, to przekazuje on żądanie do swojego
prawdopodobnego właściciela strony.

Podstawowe pojęcia i struktury danych –

Podstawowe pojęcia i struktury danych –

system

system

IVY

IVY

 Właściciel strony – węzeł, na którym była wykonywana

ostatnia operacja zapisu danej strony.

 Zbiór kopii (copyset) – zawiera identyfikatory węzłów

posiadających kopię strony (przechowywana przez właściciela
strony).

 Zarządca (w podejściu statycznym) – węzeł, który przechowuje

dane o właścicielach poszczególnych stron.

 Tablica właścicieli stron – dla każdej strony zawiera

identyfikator jej właściciela (przechowywany przez zarządców).

 Prawdopodobny właściciel (w podejściu dynamicznym) –

tablica zawierająca dla każdej strony w systemie identyfikator
węzła, o którym wiadomo, że był kiedyś (lub jeszcze jest)
właścicielem danej strony; przechowywana przez każdy węzeł.

Statyczny scentralizowany mechanizm

Statyczny scentralizowany mechanizm

lokalizacji

lokalizacji

stron – odczyt

stron – odczyt

#1
{}
#2
{}

#1
{}
#2
{}

w

ę

ze

ł

A

#4

#4

w

ę

ze

ł

B

#3 {}
#4
{B}

#3 {}
#4
{B}

w

ę

ze

ł

C

#1 A
#2 A
#3 C
#4 C

#1 A
#2 A
#3 C
#4 C

za

rz

ą

d

c

a

A}

Odczyt strony #4:

1. uzyskanie
repliki

2. wykonanie
operacji

#4

Statyczny scentralizowany mechanizm

Statyczny scentralizowany mechanizm

lokalizacji

lokalizacji

stron – zapis

stron – zapis

#1
{}
#2
{}

#1
{}
#2
{}

w

ę

ze

ł

A

#4

#4

w

ę

ze

ł

B

#3
{}
#4
{B}

#3
{}
#4
{B}

w

ę

ze

ł

C

#1 A
#2 A
#3 C
#4 C

#1 A
#2 A
#3 C
#4 C

za

rz

ą

d

c

a

Zapis strony #4:

1. uzyskanie
własności

2. unieważnienie
repliki

#4 {B}

3. wykonanie
operacji

}

A

Dynamiczny mechanizm lokalizacji stron –

Dynamiczny mechanizm lokalizacji stron –

odczyt

odczyt

#1
{}
#2
{}

#1
{}
#2
{}

w

ę

ze

ł

A

#4

#4

w

ę

ze

ł

B

#3 {}
#4 {B}

#3 {}
#4 {B}

w

ę

ze

ł

C

#1 A
#2 A
#3 C
#4 B

#1 A
#2 A
#3 C
#4 B

A}

Odczyt strony #4:

1. uzyskanie
repliki

2. wykonanie
operacji

#4

#1 A
#2 A
#3 C
#4 C

#1 A
#2 A
#3 C
#4 C

#1 A
#2 A
#3 C
#4 C

#1 A
#2 A
#3 C
#4 C

C

Dynamiczny mechanizm lokalizacji stron –

Dynamiczny mechanizm lokalizacji stron –

zapis

zapis

#1
{}
#2
{}

#1
{}
#2
{}

w

ę

ze

ł

A

#4

#4

w

ę

ze

ł

B

#3 {}
#4 {B}

#3 {}
#4 {B}

w

ę

ze

ł

C

#1 A
#2 A
#3 C
#4 B

#1 A
#2 A
#3 C
#4 B

Zapis strony #4:

#1 A
#2 A
#3 C
#4 C

#1 A
#2 A
#3 C
#4 C

#1 A
#2 A
#3 C
#4 C

#1 A
#2 A
#3 C
#4 C

1. uzyskanie
własności

2. unieważnienie
repliki

3. wykonanie
operacji

A

#4 {B}

}

A

A

Model spójności

Model spójności

Model spójności określa gwarancje dotyczące
spójności replik, dawane aplikacji (równoległej)
przez system DSM.

Model spójności określa własności

Model spójności określa własności

gwarantowane przez system DSM

gwarantowane przez system DSM

W jaki sposób definiować model
spójności?
W jaki sposób określić gwarancje dla
aplikacji?
Kiedy i w jaki sposób egzekwować te
gwarancje?

???

Modele spójności replik

Modele spójności replik

 Modele spójności przy dostępie ogólnym - swobodnym

(ang. general access consistency models) – doprowadzenie
do spójności replik realizowane jest przy każdej modyfikacji
DSM.

 Modele spójności przy dostępie synchronizowanym

(ang. synchronisation access consistency models) –
doprowadzenie do spójności replik realizowane jest tylko
przy wykonywaniu operacji synchronizujących, które są
rozpoznawane przez system DSM.

Modele spójności przy dostępie ogólnym

Modele spójności przy dostępie ogólnym

(elementarne

(elementarne

)

)

 Spójność atomowa (ang. atomic consistency)

 Spójność sekwencyjna (ang. sequential consistency)

 Spójność przyczynowa (ang. causal consistency)

 Spójność PRAM (ang. pipelined RAM consistency)

 Koherencja (ang. coherence)

 Spójność procesorowa (ang. processor consistency)

Modele spójności przy dostępie

Modele spójności przy dostępie

synchronizowanym

synchronizowanym

 Spójność słaba (ang. weak consistency)

 Spójność zwalniania (ang. release consistency)

 Spójność wejścia (ang. entry consistency)

 Spójność zakresu (ang. scope consistency)

Definicja modeli spójności – podstawowe

Definicja modeli spójności – podstawowe

założenia

założenia

 W skład systemu DSM wchodzą:

 zbiór sekwencyjnych procesów P = {p

1

, p

2

, …, p

n

}

 zbiór współdzielonych zmiennych X = {x

1

, x

2

, …}

 Każdy proces ma własną replikę całego zbioru X
 Proces p

i

może realizować na zmiennej x  X dwie operacje:

 zapisu wartości v – w

i

(x)v

 odczytu wartości v – r

i

(x)v

 Realizacja operacji przebiega w dwóch fazach:

 żądanie operacji (ang. operation issue)
 wykonanie operacji (ang. operation execution)

Definicja modeli spójności – oznaczenia

Definicja modeli spójności – oznaczenia

w

i

(x)v

operacja zapisu wartości v w zmiennej x, wykonana
przez proces p

i

r

i

(x)v

operacja odczytu wartości v zmiennej x, wykonana
przez proces p

i

O

zbiór wszystkich operacji w systemie

O

i

zbiór operacji procesu p

i

(żądanych przez p

i

)

OW

zbiór wszystkich operacji zapisu w systemie

O|x

zbiór wszystkich operacji na zmiennej x



i

lokalny porządek operacji procesu p

i

(lokalny porządek

zgłaszania żądań przez procesu p

i

)



przyczynowy porządek operacji procesu p

i

(przyczynowy porządek zgłaszania żądań przez
procesu p

i

)



i

porządek (uszeregowanie, ang. serialisation), zgodnie
z którym operacje postrzegane są przez proces p

i

(zgodnie z którym operacje wykonywane są na replice
procesu p

i

)

Definicja porządku przyczynowego

Definicja porządku przyczynowego

[

]

1,02

1, 2,

( 1

2

1

2)

( )

( )

( 1

2)

1

2

i

i

o

O

x X

o o o O

o

o

o

o

w x v

r x v

o

o o

o

o

o

�

�

�

"��

"

�

�"

ٮ

Definicja uszeregowania legalnego

Definicja uszeregowania legalnego

Uszeregowanie



i

jest legalne





































v

x

r

u

x

o

v

x

w

v

u

v

x

r

v

x

w

i

i

OW

O

u

x

o

i

O

v

x

r

OW

v

x

w

i

i

)

(

)

(

)

(

)

(

)

(

)

(

)

(

,

)

(







UWAGA

W celu uproszczenia definicji zakłada się, że
każda operacja zapisu danej zmiennej zapisuje
unikalną wartość, co umożliwia identyfikowanie
operacji zapisu poprzez tą wartość.

Definicja historii

Definicja historii

Historia lokalna (procesu p

i

)

Zbiór uporządkowany h

i

= (O

i

, 

i

), gdzie 

i

jest relacją

porządku lokalnego.

Historia globalna

Zbiór uporządkowany h = (O, ), gdzie  jest relacją porządku

przyczynowego.

Obraz historii h w procesie p

i

Zbiór uporządkowany hv

i

= (O

i

 OW, 

i

), gdzie 

i

jest legalnym

uszeregowaniem.

Obraz historii h

Kolekcja obrazów poszczególnych procesów: hv =  hv

1

, hv

2

, ...,

hv

n

.

Modele spójności — definicja spójności

Modele spójności — definicja spójności

sekwencyjnej

sekwencyjnej

Obraz hv historii h musi spełniać następujące warunki:









































2

1

2

1

..

1

2

,

1

o

o

o

o

i

j

n

j

OW

O

o

o

i





























1

2

2

1

..

1

..

1

2

,

1

w

w

w

w

i

n

i

i

n

i

OW

w

w





Spójność sekwencyjna – przykład

Spójność sekwencyjna – przykład

w

2

(x)1

p

2

p

1

w

2

(x)2

r

1

(x)1

w

2

(x)1



1

w

2

(x)2



1

r

1

(x)1

w

2

(x)1 

2

w

2

(x)2

hv

2

:

hv

1

:

Spójność sekwencyjna – protokół koherencji

Spójność sekwencyjna – protokół koherencji

(1)

(1)

read(x



X)

return M

i

[x]

write(x



X, v)

atomic_broadcast U(x,
v)
wait
return

on receipt of U(x, v)
from p

k

M

i

[x] : v

if k  i

signal
end if

Algorytm fast-read dla procesu p

i

:

Spójność sekwencyjna — protokół koherencji

Spójność sekwencyjna — protokół koherencji

(2)

(2)

read(x



X)

if num

i

 0

wait
end if
return M

i

[x]

write(x



X, v)

num

i

: num

i

 1

FIFO_atomic_broadcast U(x, v)
return

on receipt of U(x, v)
from p

k

M

i

[x] : v

if k  i

num

i

: num

i

 1

if num

i

 0

signal
end if
end if

Algorytm fast-write dla procesu p

i

:

Modele spójności — definicja spójności

Modele spójności — definicja spójności

atomowej

atomowej

Obraz hv historii h musi spełniać następujące warunki:









































2

1

2

1

..

1

2

,

1

o

o

o

o

i

RT

n

j

OW

O

o

o

i





























1

2

2

1

..

1

..

1

2

,

1

w

w

w

w

i

n

i

i

n

i

OW

w

w





2

1

o

o

RT



o1 kończy się w czasie
rzeczywistym, zanim zaczyna się
o2

Spójność atomowa — przykład

Spójność atomowa — przykład

w

2

(x)1

p

2

p

1

w

2

(x)2

r

1

(x)1

r

1

(x)2

Modele spójności — definicja spójności

Modele spójności — definicja spójności

przyczynowej

przyczynowej

Obraz hv historii h musi spełniać warunek:





2

1

2

1

2

,

1

o

o

o

o

i

OW

O

o

o

i













Spójność przyczynowa — przykład

Spójność przyczynowa — przykład

w

2

(x)1

p

2

p

1

r

2

(y)1

r

1

(x)1

w

1

(x)2 w

1

(y)1

r

2

(x)2

w

1

(x)

2



1

w

2

(x)1



1

w

1

(y)1

w

2

(x)1 

2

w

1

(x)2

hv

2

:

hv

1

:



1

r

1

(x)1



2

r

2

(y)1



2

w

1

(y)1



2

r

2

(x)2

Spójność przyczynowa — protokół koherencji

Spójność przyczynowa — protokół koherencji

read(x



X)

return M

i

[x]

write(x



X, v)

M

i

[x] : v

causal_broadcast U(x,
v)
return

on receipt of U(x, v)
from p

k

if k  i

M

i

[x] : v

end if

Algorytm dla procesu p

i

:

Modele spójności — definicja spójności

Modele spójności — definicja spójności

PRAM

PRAM

Obraz hv historii h musi spełniać warunek:









































2

1

2

1

..

1

2

,

1

o

o

o

o

i

j

n

j

OW

O

o

o

i



Spójność PRAM — przykład

Spójność PRAM — przykład

p

2

p

1

r

2

(y)1

w

1

(x)1 w

1

(y)1

w

2

(x)2

p

3

r

3

(x)2 r

3

(x)1

w

2

(x)2 

3

r

3

(x)2

hv

3

:



3

r

3

(x)1



3

w

1

(x)1



3

w

1

(y)1

Spójność PRAM — protokół koherencji

Spójność PRAM — protokół koherencji

read(x



X)

return M

i

[x]

write(x  X, v)

M

i

[x] : v

FIFO_broadcast U(x, v)
return

on receipt of U(x, v)
from p

k

if k  i

M

i

[x] : v

end if

Algorytm dla procesu p

i

:

Modele spójności — definicja koherencji

Modele spójności — definicja koherencji

Obraz hv historii h musi spełniać warunek:

































1

2

2

1

..

1

..

1

|

2

,

1

w

w

w

w

i

n

i

i

n

i

x

O

OW

w

w

X

x





Koherencja — przykład

Koherencja — przykład

w

2

(x)1

p

2

p

1

r

2

(y)1

r

1

(x)1w

1

(x)2

w

1

(y)1

r

2

(x)1

r

1

(x)2

r

2

(x)2

w

2

(x)

1



2

w

1

(y)1

hv

2

:



2

r

2

(x)1



2

r

2

(y)1



2

w

1

(x)2

w

2

(x)

1



1

r

1

(x)1

hv

1

:



1

r

1

(x)2



1

w

1

(x)2



1

w

1

(y)1



2

r

2

(x)2

Koherencja (model spójności) — protokół

Koherencja (model spójności) — protokół

koherencji (1)

koherencji (1)

read(x



X)

return M

i

[x]

write(x



X, v)

atomicx_broadcast
U(x, v)
wait
return

on receipt of U(x, v)
from p

k

M

i

[x] : v

if k  i

signal
end if

Algorytm fast-read dla procesu p

i

:

Koherencja (model spójności) — protokół

Koherencja (model spójności) — protokół

koherencji (2)

koherencji (2)

read(x



X)

if num

i

[x]  0

wait

end if

return M

i

[x]

write(x



X, v)

num

i

[x] : num

i

[x]  1

FIFOx_atomicx_broadcast U(x, v)

return

on receipt of U(x, v)
from p

k

M

i

[x] : v

if k  i

num

i

[x] : num

i

[x]  1

if num

i

[x]  0

signal
end if
end if

Algorytm fast-write dla procesu p

i

:

Modele spójności — definicja spójności

Modele spójności — definicja spójności

procesorowej

procesorowej

Obraz hv historii h musi spełniać następujące warunki

(PRAM + koherencja):









































2

1

2

1

..

1

2

,

1

o

o

o

o

i

j

n

j

OW

O

o

o

i



































1

2

2

1

..

1

..

1

|

2

,

1

w

w

w

w

i

n

i

i

n

i

x

O

OW

w

w

X

x





Spójność procesorowa — przykład

Spójność procesorowa — przykład

w

2

(x)1

p

2

p

1

r

2

(y)1

r

1

(x)1

w

1

(x)2 w

1

(y)1

r

2

(x)1

w

1

(x)

2



1

w

1

(y)1

hv

1

:



1

r

1

(x)1



1

w

2

(x)1

w

1

(x)

2



2

w

2

(x)1

hv

2

:



2

r

2

(y)1



2

w

1

(y)1



2

r

2

(x)1

r

1

(x)2



1

r

1

(x)2

r

2

(y)0



2

r

2

(y)0

Spójność procesorowa — protokół koherencji

Spójność procesorowa — protokół koherencji

read(x



X)

if num

i

[x]  0

wait

end if

return M

i

[x]

write(x



X, v)

num

i

[x] : num

i

[x]  1

FIFO_atomicx_broadcast U(x, v)

return

on receipt of U(x, v)
from p

k

M

i

[x] : v

if k  i

num

i

[x] : num

i

[x]  1

if num

i

[x]  0

signal
end if
end if

Algorytm fast-write dla procesu p

i

:

Spójność procesorowa — przykład

Spójność procesorowa — przykład

naruszenia porządku przyczynowego

naruszenia porządku przyczynowego

r

2

(x)1

p

2

p

1

r

3

(y)1

w

1

(x)2

w

2

(y)1

p

3

r

3

(x)1 r

3

(x)2

w

1

(x)1

r

2

(x)2

w

1

(x)1  w

1

(x)2 

w

2

(y)1

hv

3

: w

2

(y)1  r

3

(y)1  w

1

(x)1  r

3

(x)1  w

1

(x)2 

r

3

(x)2

Relacje pomiędzy modelami spójności

Relacje pomiędzy modelami spójności









































2

1

2

1

..

1

2

,

1

o

o

o

o

i

j

n

j

OW

O

o

o

i







2

1

2

1

2

,

1

o

o

o

o

i

OW

O

o

o

i





















































2

1

2

1

..

1

2

,

1

o

o

o

o

i

RT

n

j

OW

O

o

o

i





























1

2

2

1

..

1

..

1

2

,

1

w

w

w

w

i

n

i

i

n

i

OW

w

w





PRAM

przyczynow
a

koherencj
a

p

ro

c

e

s

o

ro

w

a

sekwencyjna

atomowa

































1

2

2

1

..

1

..

1

|

2

,

1

w

w

w

w

i

n

i

i

n

i

x

O

OW

w

w

X

x





Definicja modeli spójności przy dostępie

Definicja modeli spójności przy dostępie

synchronizowanym — założenia

synchronizowanym — założenia

 W skład systemu DSM wchodzą:

 zbiór sekwencyjnych procesów P = {p

1

, p

2

, …, p

n

}

 zbiór współdzielonych zmiennych X = {x

1

, x

2

, …}

 zbioru obiektów synchronizujących S = {s

1

, s

2

, ...}

 Wyróżnia się (najczęściej) dwa rodzaje obiektów

synchronizujących:

 zamek (ang. lock), na którym wykonywane są operacje:

 acquire — nabycie zamka
 release — zwolnienie zamka

 bariera (ang. barrier) z operacją

 synchronizacja na barierze

Spójność słaba

Spójność słaba

(ang.

(ang.

weak consistency

weak consistency

)

)

 Wyróżnia się dwa rodzaje operacji dostępu:

 operacje dostępu do globalnych danych

(współdzielonych),

 operacje dostępu do zmiennych synchronizujących.

 Definicja modelu:

 operacje dostępu do zmiennych synchronizujących są

spójne atomowo (w nowszym podejściu sekwencyjnie),

 nie można wykonać (zakończyć) operacji dostępu do

zmiennej synchronizującej przed globalnym
zakończeniem wcześniejszych operacji dostępu do
zmiennych współdzielonych,

 nie można wykonać (zakończyć) operacji dostępu do

zmiennej współdzielonej przed globalnym
zakończeniem wcześniejszych operacji dostępu do
zmiennych synchronizujących.

Spójność słaba — przykład

Spójność słaba — przykład

w

2

(x)1

p

2

p

1

synch

2

(s)

r

1

(x)1

synch

1

(s)

r

2

(x)2

w

1

(x)2

r

2

(x)0

wartość początkowa x = 0

Spójność zwalniania

Spójność zwalniania

(ang.

(ang.

release

release

consistency

consistency

)

)

 Dwa rodzaje synchronizacji są możliwe:

 wzajemne wykluczanie (acquire-release),
 synchronizacja na barierze.

 Operacje synchronizujące są spójne procesorowo, a

pozostałe operacje są spójne w sensie PRAM.

 Repliki są doprowadzane do stanu spójnego przy operacji

bariery oraz przy

 release w przypadku spójności eager release,
 acquire w przypadku spójności lazy release.

 Doprowadzanie do stanu spójnego polega na:

 unieważnianiu replik w przypadku protokołu

unieważniania,

 aktualizacji replik w przypadku protokołu aktualizacji.

Spójność zwalniania — przykład

Spójność zwalniania — przykład

r

2

(x)0

p

2

p

1

acq

1

(lock)

w

1

(x)1rel

1

(lock)

r

2

(x)1

acq

1

(lock)

W przypadku protokołu

unieważniania operacje

spowodują błąd strony

w

1

(y)1

r

2

(y)0

r

2

(y)1

Spójność zakresu

Spójność zakresu

(ang.

(ang.

scope consistency

scope consistency

)

)

 Operacje acquire i release odpowiednio otwierają i

zamykają zakres.

 Operacja bariery zamyka zakres globalny i otwiera następny

zakres globalny.

 Istnieją jawne operacje otwarcia i zamknięcia zakresu:

open_scope i close_scope.

 Po otwarciu zakresu aktualizowane/unieważnianie są

wszystkie repliki zmodyfikowane w czasie poprzedniego
otwarcia zakresu (poprzedni zakres musi być zamknięty).

Spójność zakresu — przykład

Spójność zakresu — przykład

r

2

(x)0

p

2

p

1

acq

1

(lock)

w

1

(x)1rel

1

(lock)

r

2

(x)1

acq

1

(lock)

w

1

(y)1

r

2

(y)0

r

2

(y)0

Spójność wejścia

Spójność wejścia

(ang.

(ang.

entry consistency

entry consistency

)

)

 Spójność wejścia zbliżona jest do spójności zakresu.

 Są dwa rodzaje operacji acquire: współdzielona i wyłączna.

 Z każdym globalnym obiektem związana jest zmienna

synchronizująca, na której wykonywana jest odpowiednia
operacja przed dostępem do zmiennej.

Własność lokalności

Własność lokalności

Lokalność jest cechą spójności atomowej i

koherencji.

Własność

Własność

P

P

systemu współbieżnego jest

systemu współbieżnego jest

lokalna wówczas, gdy system jako całość

lokalna wówczas, gdy system jako całość

posiada własność

posiada własność

P

P

, jeśli każdy pojedynczy

, jeśli każdy pojedynczy

obiekt posiada własność

obiekt posiada własność

P

P

.

.

Własność lokalności — przykład

Własność lokalności — przykład

r

2

(x1)1

p

2

p

1

r

2

(y1)1

r

1

(y2)1

w

1

(x1)1

w

1

(y1)1

r

2

(x2)1

w

1

(x1)

1



1

w

2

(y1)1



1

w

1

(x2)1

w

1

(x1)1



2

w

1

(x2)1

hv

2

:

hv

1

:



1

w

1

(y2)1



2

r

2

(y1)1



2

w

1

(y1)1



2

r

2

(x2)0

w

1

(x2)1

w

1

(y2)1

r

2

(x2)0



2

r

2

(x1)1



2

r

2

(x2)1



2

r

2

(y2)1



2

w

1

(y2)1

Własność lokalności — przykład

Własność lokalności — przykład

r

2

(x1)1

p

2

p

1

w

1

(x1)1

r

2

(x2)1

w

1

(x1)

1



1

w

1

(x2)1

w

1

(x1)1



2

w

1

(x2)1

hv

2

:

hv

1

:



2

r

2

(x2)0

w

1

(x2)1

r

2

(x2)0



2

r

2

(x1)1



2

r

2

(x2)1

Własność lokalności — przykład

Własność lokalności — przykład

p

2

p

1

r

2

(y1)1

r

1

(y2)1

w

1

(y1)1

w

2

(y1)

1

hv

2

:

hv

1

:



1

w

1

(y2)1



2

r

2

(y1)1

w

1

(y1)

1

w

1

(y2)1



2

r

2

(y2)1



2

w

1

(y2)1

Koniec

Koniec

...

i żyli długo

i

szczęśliwie