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