4. TEORETYCZNE MODELE PROCESÓW WSPÓŁBIEŻNYCH

Teoretyczne modele uwzględniają wybrane cechy rzeczywistych procesów,
stanowiąc kompromis

pomiędzy łatwością i jakością modelowania. Konstruując model obliczeń
należy mieć na

względzie:

1) czy korzystamy z pamięci dzielonej, czy z przesyłania komunikatów (raczej
nie miesza sie

tych dwóch rzeczy);

2) jakie akcje uznajemy za elementarne, to jest wykonywane niepodzielnie
- niezależnie od

akcji innych procesów.

Przykład (Z. Manna, A. Pnueli)

Obliczyć wartość dwumianu Newtona dla n, k naturalnych, n  k.
n! n · (n - 1) · ... · (n - k + 1)

( k

czynników )

k! (n - k)! 1  2 · ... · k

( k

czynników )

Wartość tego wyrażenia jest zawsze liczbą naturalną dla n, k takich, że n  k.

)

(

n
k

)

(

n
k





Sposób obliczenia: współbieżnie wykonujemy mnożenia w liczniku i
mianowniku, i na bieżąco

wykonujemy dzielenia - wtedy, kiedy tylko jest to możliwe (ten sposób jest
dobry, gdyż możemy

uniknąć przekroczenia zakresu arytmetyki komputera, pomimo że licznik i
mianownik oddzielnie

mogłyby ten zakres przekroczyć).

n, k - dane

l, m - zmienne pomocnicze, przyjmujące odpowiednio wartości

l : n, n-1, ... , n - k + 1

m: 1,2, ... , k

b - wartość ułamka (na początku b = 1)

Proces P

1

mnoży b przez kolejne wartości l, proces P

2

dzieli b przez kolejne

wartości m, ale

dopiero wtedy, kiedy jest to wykonalne: w żadnej chwili liczba wykonanych
dzieleń nie może

przekroczyć liczby wykonanych mnożeń, czyli musi zachodzić m  n - l, aby

można było

wykonać dzielenie, zatem warunkiem wykonania dzielenia jest l + m  n.

{ n, k : dane }

l : n ;
m : 1 ;
b : 1 ;

while l  n - k do while m  k do
begin begin

P

1

: b : b  l ; || P

2

: await ( l + m ) 

n ;

l : l - 1 b : b div m ;
end ; m : m + 1
end;

{ b : wynik }

Założenia: 1) zmienne n, k, b umieszczone są w pamięci wspólnej i oba
procesy używają dla nich

takich samych nazw;

2) sprawdzenia warunków oraz instrukcje podstawienia
wykonywane są niepodzielnie.

Instrukcja await (wb), gdzie wb jest wyrażeniem boolowskim, zawiesza
wykonywanie procesu do

momentu, gdy zacznie zachodzić wb = true. Gdyby działanie await (wb) było
interpretowane jako:

wb ?

T F

byłoby to tak zwane aktywne czekanie (ciągłe sprawdzanie wartości wb
absorbuje moc oblicze-

niową procesora). W praktyce częściej następuje zawieszenie wykonywania
procesu przez system

operacyjny tak, aby nie marnować mocy procesora, więc bardziej adekwatnym
schematem byłby

schemat:

wb ?

T F

Działanie programów sekwencyjnych często przedstawiane jest za pomocą
schematów blokowych.

Dla programów współbieżnych dogodniejszą formą ilustracji ich działania są
diagramy przejść.

stan przejście

c ?
instr

warunek logiczny instrukcja

(strażnik przejścia) wykonywana
niepodzielnie

Jeżeli dla każdego stanu zachodzi, że wszystkie przejścia wychodzące z tego
stanu mają warunki

parami wykluczające się, program nazywamy procesowo
deterministycznym.

Omawiany przykład jest procesowo deterministyczny.

s

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 5

m = 1

b = 1

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 5

m = 1

b = 1

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 5

m = 1

b = 1

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 5

m = 1

b = 5

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 4

m = 1

b = 5

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 4

m = 1

b = 5

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 4

m = 1

b = 5

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 4

m = 1

b = 20

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 4

m = 1

b = 20

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 4

m = 2

b = 20

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 4

m = 2

b = 20

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 3

m = 2

b = 20

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 3

m = 2

b = 20

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 3

m = 2

b = 20

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 3

m = 2

b = 10

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 3

m = 2

b = 30

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 2

m = 2

b = 30

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 2

m = 3

b = 30

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 2

m = 3

b = 30

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 2

m = 3

b = 30

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 2

m = 3

b = 10

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 2

m = 3

b = 10

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 2

m = 4

b = 10

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

l  n - k

?

l  n - k ?

m  k ?

m:m

+1

l:l -1

n = 5 k
= 3

l = 2

m = 4

b = 10

p

0

p

1

p

2

p

3

r

0

r

1

r

2

r

3

r

4

b:b  l

m  k ?

l + m  n ?

b : b div

m

W powyższym diagramie pojedyncze strzałki odpowiadają pojedynczym
operacjom niepodziel-

nym. Wielkość jednostek syntaktycznych programu, o których możemy
założyć, że będą wyko-

nane niepodzielnie, nazywamy ziarnistością

(granularity)

.

Przedstawiony program charakteryzuje się niedeterminizmem wykonania,
gdyż jego wykonanie

może być modelowane przez różne przeploty operacji niepodzielnych obu
procesów, np.

P

1

P

1

P

2

P

1

P

2

P

1

...........

lub P

1

P

1

P

1

P

2

P

1

P

2

...........

Natomiast pomimo to stan końcowy programu (wektor wartości zmiennych i
wskaźników

instrukcji) jest w każdym przypadku taki sam, niezależnie od wykonanego
przeplotu - taki

program nazywamy zdeterminowanym (wszystkie współbieżne programy
transformacyjne

powinny posiadać tę cechę).

W przypadku korzystania ze wspólnej pamięci efekt wykonania programu
współbieżnego może

zależeć od ziarnistości.

Przykład

{y = 1 - wartość początkowa}

P

1

: y = y + 1 P

2

: y = y - 1

Jeżeli założymy, że instrukcje podstawienia wykonywane są niepodzielnie, to
zarówno dla prze-

plotu P

1

P

2

, jak i P

2

P

1

wynikiem wykonania będzie y = 1. W praktyce

kompilator może

przełożyć te instrukcje na następujące ciągi rozkazów maszynowych:

LOAD Rejestr1, y LOAD Rejestr2, y

P

1

: ADD Rejestr1, #1 P

2

: SUB Rejestr2, #1

STORE Rejestr1, y STORE Rejestr2,
y

(Zakładamy, że każdy proces używa swojego lokaknego rejestru).

Zakładając, że wszystkie przeploty rozkazów z przekładów P

1

i P

2

są

dopuszczalne, otrzymujemy

trzy różne wyniki dla różnych przeplotów:

P

1

P

1

P

1

P

2

P

2

P

2

y = 1

Liczba wszystkich

przeplotów ciągu

P

1

P

1

P

2

P

1

P

2

P

2

y = 2

m - elementowego z ciągiem

n - elementowym

P

1

P

2

P

1

P

2

P

2

P

1

y = 3

(m + n) !

m !  n !

(inne przeploty dałyby jeden z tych trzech wyników). Zmniejszenie ziarnistości
spowodowało

zatem, że program przestał być zdeterminowany.

W języku inżynierskim zjawisko, kiedy wynik zależy od przypadkowych czasów
wykonania (lub,

dla układów scalonych, od przypadkowych różnic w czasach propagacji
sygnałów elektrycznych)

nazywane jest hazardem.

Nie należy projektować niczego, czego efekt wykonania mógłby zależeć od
hazardu !

wynosi

Powyższy przykład był prosty, bo wszystkie występujące w nim rozkazy
maszynowe co najwyżej

raz wykonywały cykl pamięciowy. Jego analiza odnosi się więc zarówno do
wykonania z przeplo-

tem (drobnoziarnistym) na pojedynczym procesorze, jak i do wykonania
równoległego na dwóch

procesorach mających dostęp do wspólnej pamięci. Różnica mogłaby wystąpić
w przypadku,

gdyby dwa procesory równolegle wykonywały rozkazy wymagające dwóch
odwołań do pamięci -

np. rozkaz dodania zawartości akumulatora do zawartości komórki pamięci z
pozostawieniem

wyniku w pamięci. W takim przypadku do modelowania należałoby stosować
jeszcze drobniejszą

ziarnistość - na poziomie mikrorozkazów (operacjami niepodzielnymi są
odczyt / zapis z /do

pamięci i wykonanie operacji na samych rejestrach).

5. NISKOPOZIOMOWE MECHANIZMY ZAPEWNIANIA
NIEPODZIELNOŚCI

OPERACJI

Możliwość zapewnienia niepodzielności operacji (będących ciągami operacji
elementarnych) na

komórkach pamięci wspólnej jest w programowaniu współbieżnym sprawą o
zasadniczym zna-

czeniu. Szczególnie w przypadku rzeczywistej równoległości widoczna jest
potrzeba zabezpiecze-

nia pojedynczym procesom prawa wyłączności dostępu (na pewien czas) do
zmiennych dzielonych,

ale w przypadku drobnoziarnistego przeplotu też to jest istotne. Ciąg instrukcji
programu operujących

na współdzielonych zasobach (pamięci dzielonej, wspólnych plikach itp.),
który powinien być wyko-

nany niepodzielnie, nazywamy sekcją krytyczną programu. Jakie są sposoby
zabezpieczania sekcji

krytycznych ?

Jeżeli współbieżność jest symulowana na pojedynczym procesorze przez system
operacyjny i sekcje

krytyczne nie są związane z pamięcią wspólną, ale innymi zasobami (pliki,
kolejki), proste operacje

na tych zasobach są dostępne w postaci wywołań funkcji systemowych.
Funkcje systemowe są

wykonywane przez jądro systemu na zamówienie procesu i niepodzielność ich
wykonania jest

zapewniana przez system operacyjny.

Jeżeli mają być wykonywane operacje na pamięci wspólnej, lub bardziej złożone
operacje na

dowolnych zasobach, programista musi sam zadbać o ich zabezpieczenie.
Najprostszym mecha-

nizmem abstrakcyjnym służącym do tego celu są semafory. Podstawowym
rodzajem semafora

jest semafor binarny, będący obiektem, którego jedyne pole może przyjmować
tylko wartości

0 i 1, a jedyne operacje, jakie można na nim wykonać, to:

P (czekaj)

V (sygnalizuj)

Definicje tych operacji jest następująca:

P(S) - jeżeli S>0, to zmniejsz S o 1, w przeciwnym razie wstrzymaj
wykonywanie procesu;

V(S) - jeżeli są jakieś procesy wstrzymane przez semafor S, to wznów jeden z
nich, w przeciwnym

razie jeśli S=0, to zwiększ S o 1.

Uwaga.

1) Skutek próby otwarcia otwartego semafora binarnego zależy od
implementacji. Dojście do

takiej sytuacji świadczy o błędzie w programie (i system operacyjny
zazwyczaj reaguje

sygnalizacją błędu).

2) Same operacje na semaforach muszą być wykonywane niepodzielnie. W
systemach z przeplo-

tem realizowane są jako funkcje systemowe, natomiast w sytuacji
rzeczywistej równoległości

ich implementacja musi być wspierana przez odpowiedni sprzęt
(procesory z niepodzielnymi

rozkazami typu test-and-set).

3) Niedeterminizm uruchamiania procesów czekających pod semaforem
może podlegać różnym

ograniczeniom (pojęcia związane z szeregowaniem wykonywania
procesów będą omówione

na następnym wykładzie).

Przykład

Użycie semafora binarnego do zabezpieczenia sekcji krytycznej w przypadku
dwóch procesów.

{na początku S=1}

while true do while true
do

begin begin

niekrytyczna1;
niekrytyczna2;

P

1

: czekaj(S); || P

2

:

czekaj(S);

krytyczna1;
krytyczna2;

sygnalizuj(S)
sygnalizuj(S)

end end

Uwaga.

Przyjmujemy założenie, że każde wykonanie zarówno sekcji krytycznej, jak i
niekrytycznej zajmuje

skończony czas (procesy nie zapętlają się w nich ani nie zawieszają).

{ S = 1 }

niekrytyczna1

krytyczna1

S > 0 ? S
= 0

S :=
S+1

niekrytyczna2

S > 0 ? S
= 0

krytyczna2

S =

S+1

Uwaga.

Gdyby w powyższym przykładzie zrównoleglić trzy takie procesy lub więcej,
wzajemne wykluczanie

byłoby dalej zapewnione, ale jeden z procesów mógłby zostać zagłodzony.

Uogólnienia semafora binarnego:

1) semafor ogólny - różni się od binarnego tym, że może przyjmować dowolne
wartości naturalne,

zaś operacja V, jeżeli nie czeka żaden proces, zwiększa zawsze wartość S o 1;

2) semafor ograniczony - może przyjmować wartości naturalne z zakresu od 0
do pewnego n.

Zawieszenie procesu powoduje zarówno próba zmniejszenia wartości
semafora poniżej 0, jak

i próba zwiększenia powyżej n ;

3) semafor wielokrotny - pozwala na wykonywanie niepodzielnych operacji na
wielu wartościach

jednocześnie (będzie omówiony przy okazji opisu implementacji w systemie
Linux).

Uwaga.

W językach programowania dysponujących standardowymi zestawami instrukcji
wszystkie rodzaje

semaforów są wzajemnie zastępowalne. Do rozwiązania konkretnych problemów
jedne rodzaje mogą

jednak być wygodniejsze, niż inne.

Przykład

Jeżeli w sieci lokalnej jest 5 ogólnodostępnych drukarek, to dostęp wielu
procesów do nich można

skoordynować przy użyciu semafora przyjmującego wartości 0 ... 5.

Przykład

Problem producenta i konsumenta z n - miejscowym buforem cyklicznym.

while true do while true do

begin begin

produkuj(e);
czekaj(elementy);

czekaj(miejsca); e :=
bufor(wy);

P

1

: bufor(we) := e; P

2

: wy :=

(wy + 1) mod n;

we := (we + 1) mod n;
sygnalizuj(miejsca);

sygnalizuj(elementy)
konsumuj(e)

end end

produce
nt

konsument

bufor

W przypadku komunikacji przez kanał przyjmujemy, że dostępne są
niepodzielnie wykonywane

funkcje send(, expr) i receive(, e), gdzie e jest zmienną, expr jest wyrażeniem

tego samego typu,

co e, a  jest kanałem mogącym pomieścić ciąg elementów tego samego typu, co

e. Kanał może mieć

pojemność skończoną (w szczególnym przypadku 0) lub nieskończoną. Funkcja
send zawiesza wyko-

nywanie procesu, jeśli kanał jest pełny, funkcja receive zawiesza proces przy
próbie pobrania z kanału

pustego.

Przykład

Rozwiązanie problemu producenta i konsumenta przy użyciu kanału.

while true do while true do

begin begin

P

1

: produkuj(e); P

2

:

receive(, e);
send(, e)

konsumuj(e)

end end

Monitory są „deklarowalnymi” obiektami mającymi zagwarantowaną
niepodzielność wykonywania

ich metod. Jest zatem niemożliwe współbieżne wykonanie operacji w jednym
monitorze, ale możliwe

w kilku różnych monitorach. Monitory są bardzo naturalnym mechanizmem
ochrony sekcji krytycz-

nych.