Programowanie współbieżne

Wprowadzenie do programowania współbieżnego.

Podstawowe pojęcia programowania współbieżnego.

Prowadzący: dr inż. Dariusz Pierzchała

[e-mail]

Literatura przedmiotu

1. Literatura obowiązkowa
1.1. M. Ben-Ari: „Podstawy programowania współbieżnego i rozproszonego”, WNT, Warszawa 2009.
1.2. M. Ben-Ari: „Podstawy programowania współbieżnego i rozproszonego”, WNT, Warszawa 1996, sygn.

53403.

1.3. A. Karbowski, E. Niewiadomska-Szynkiewicz: „Programowanie równoległe i rozproszone”, Oficyna

Wydawnicza PW, Warszawa 2009.

1.4. Z. Weiss, T. Gruźlewski: „Programowanie współbieżne i rozproszone w przykładach i zadaniach”,

WNT, Warszawa 1993.

1.5. W. Stallings: „Systemy operacyjne. Struktura i zasady budowy”, PWN, Warszawa 2006 (niniejsza

książka została również wydana przez Wydawnictwo Robomatic w 2004 roku pt. „Systemy

operacyjne”).

1.6. A. Silberschatz, P. B. Galvin: „Podstawy systemów operacyjnych”, WNT, Warszawa 1993, 2000, 2005

- sygn. 56239, 51409 i in.

1.7. A.S. Tanenbaum: „Systemy operacyjne”, Helion, 2010.
1.8. B. Goetz i in.: „Java. Współbieżność dla praktyków”, Helion, 2007.
1.9. M. Herlihy, N. Shavit: „Sztuka programowania wieloprocesorowego”, PWN, 2010.

2. Literatura uzupełniająca
2.1. J. Berdychowski, G. Bliźniuk: „Techniki programowania”, skrypt WAT, sygn. S-53260.
2.2. G. Gębal: „Programowanie współbieżne w Adzie”, Wydawnictwo Stachowski, 1999.
2.3. B. Goodheart, J. Cox: „Sekrety magicznego ogrodu. UNIX® System V Wersja 4 od środka”, WNT,

Warszawa 2001.

2.4. U. Vahalia: „Jądro systemu UNIX. Nowe horyzonty”, WNT, Warszawa, 2001.
2.5. J. Richter: „Programowanie aplikacji dla Microsoft Windows”, Wydawnictwo RM, 2002.
2.6. C. Breshears: „The Art of Concurrency”, O’Reilly, 2009.
2.7. D. Harel: „Rzecz o istocie informatyki. Algorytmika”, WNT, 1992 i późn.
2.8. S. Wrycza, B. Marcinkowski, K. Wyrzykowski: „Język UML 2.0”, Helion, 2005.
2.9. J. Richter, Ch. Nasarre: „Windows via C/C++”, Microsoft Press, 2007.
2.10. J. Duffy: „Concurrent Programming on Windows”, Addison-Wesley, 2009.
2.11. Z. Huzar, Z. Fryźlewicz, I. Dubielewicz, B. Hnatk: „Ada 95”, Helion, Gliwice 1998.

Literatura przedmiotu

Podstawowe pojęcia programowania współbieżnego

4

Klasyczne (sekwencyjne) ujęcie

programu komputerowego



Program komputerowy składa się z opisu (deklaracji)
danych oraz wykonywalnych instrukcji (zapisanych w
języku programowania);



Instrukcje te wykonywane są przez procesor (komputer);



W trakcie wykonywania programu niezbędne do realizacji
dane przechowywane są w pamięci (podręcznej,
wewnętrznej, zewnętrznej);



Jak może (lub powinien) być
konstruowany program,
gdy mamy do dyspozycji
więcej niż jeden procesor?

Architektura wg von Neumanna



Spójrzmy na typowe zadania (logistyczne, matematyczne)



Podstawowe pojęcia programowania współbieżnego

5

Transport towarowy

1 auto x 25 ton x 5 godz.

czy…

5 aut x 25 ton x 1 godz.?

Podstawowe pojęcia programowania współbieżnego

6

Algorytmy obliczania całki

oznaczonej

sekwencyjny

czy

równoległy?

Każde pole może
być wyznaczone
przez jeden lub
wiele procesorów
(jednocześnie)

Każde pole może
być wyznaczone
przez jeden lub
wiele procesorów
(jednocześnie)

Podstawowe pojęcia programowania współbieżnego

7

Rodzaje równoległości



Równoległość procesowa - zbiór współpracujących
elementów, z których każdy jest dość złożony i działa w sposób
zbliżony, ale niekoniecznie identyczny z innymi;
Przykłady:



działanie supermarketu, banku, poczty - wiele kas (okienek),



budowa - wielu murarzy, malarzy, tynkarzy, itp.



transport – konwój ciężarówek jednocześnie wiozących
ładunek;



Obok równoległości procesowej wyróżnia się także:



równoległość tablicową (np. musztra, aerobik) - pełna
synchronizacja działań,



równoległość potokową (np. taśma produkcyjna) - jednoczesne
wykonywanie kolejnych etapów złożonego procesu

;

Podstawowe pojęcia programowania współbieżnego

8

„Równoległe” ujęcie procesu

(programu)



Podsumowując - z jednej strony wiemy, że:



Wiele problemów (z różnych dziedzin życia) jest ze swej
natury „równoległych”;



Jeśli programy komputerowe muszą oczekiwać na dane,
może to powodować wytracanie czasu procesora;



Z drugiej zaś strony:



Aktualne ceny i dostępność sprzętu o architekturze
wieloprocesorowej, a także szybkie sieci komputerowe
wymusiły rozwój algorytmów, protokołów, narzędzi, języków
pozwalających na „zrównoleglenie” części zadań – tym
samym przyspieszenie ich realizacji;



Niezbędne jest „zrównoleglenie” działania programów!

Pojęcie „równolegle” jest abstrakcyjnie – nadamy mu znaczenia w czasie zajęć.

Pojęcie „równolegle” jest abstrakcyjnie – nadamy mu znaczenia w czasie zajęć.

Podstawowe pojęcia programowania współbieżnego

9

Rodzaje równoległości (1/2)



Równoległość na poziomie bitów (ang. bit-level
parallelizm) –zwiększanie długości słowa procesora wpływa
na liczbę instrukcji potrzebnych do wykonania operacji na
zmiennych, których wielkość jest większa niż długość słowa.



Równoległość na poziomie instrukcji (ang. instruction
level parallelizm) – techniki implementowane zazwyczaj
przez kompilator i wykorzystujące specjalną budowę
mikroprocesorów, które umożliwiają uruchamianie niezależnych
od siebie instrukcji równocześnie – np. potokowość,
wykonywanie poza kolejnością, wykonywanie spekulatywne.



Równoległość na poziomie danych (ang. data
parallelizm) – ten sam zbiór instrukcji jest jednocześnie
wykonywany na wielu blokach danych – np. przetwarzanie
SIMD.

Podstawowe pojęcia programowania współbieżnego

10

Rodzaje równoległości (2/2)



Równoległość na poziomie pętli (ang. loop-level
parallelizm) –iteracje pętli w kodzie wykonywalnym
rozdzielane są między dostępnymi jednostkami
obliczeniowymi - np. model obliczeniowy OpenMP.



Równoległość na poziomie zadania (ang. task
parallelizm) –obliczenia realizowane są przez wiele
jednostek obliczeniowych realizujących różne procesy
sekwencyjne na tych samych lub różnych danych.

Podstawowe pojęcia programowania współbieżnego

11

Równoległość na poziomie

(pod)zadania

Algorytm sekwencyjny:

Algorytm równoległy:

START

STOP

Krok_1

Krok_2

Krok_4

Krok_6

Krok_3

Krok_5

START

STOP

Krok_1

Krok_2

Krok_3

Krok_4

Krok_5

Krok_6

Krok_2 i
Krok_4 nie
mogą być od
siebie
zależne!

Podstawowe pojęcia programowania współbieżnego

12

Przykład - pierwiastki równania

kwadratowego

START

STOP

=b

2

-4ac

x

1

=(-b-sqrt())/2a

x

2

=(-b+sqrt())/2a

Wypisz x

1

, x

2

START

STOP

=b

2

-4ac

x

1

=(-b-sqrt())/2a

x

2

=(-b+sqrt())/2a

Wypisz x

1

, x

2

Algorytm sekwencyjny: Algorytm

równoległy:

Podstawowe pojęcia programowania współbieżnego

13

Przykład – sortowanie tablicy N liczb

Algorytm sekwencyjny:

Algorytm sekwencyjny:

procedure sort (i, j)
begin
...
m := (i+j) div 2;

sort (i, m);
sort (m+1, j);

merge (i, m, j);
end

Algorytm równoległy:

procedure sort (i, j)
begin
...
m := (i+j) div 2;

cobegin

sort (i, m);
sort (m+1, j);

coend

merge (i, m, j);
end



„

cobegin

” i „

coend

” - specjalne instrukcje – kod między nimi wykonuje się

współbieżnie

Podstawowe pojęcia programowania współbieżnego

14

Programowanie współbieżne



Programowanie współbieżne (M. Ben-Ari) - zbiór technik i
notacji programistycznych służących do wyrażania potencjalnej
równoległości oraz do rozwiązywania zagadnień związanych
z powstającymi przy tym problemami: synchronizacji i
komunikacji.



Programowanie współbieżne pozwala rozważać równoległość
algorytmu obliczeniowego bez wdawania się w szczegóły
implementacyjne

(liczba procesorów, model procesu, model pamięci,

implementacja obiektów synchronizacji, algorytm wznawiania
procesów, mechanizmy komunikacji, itp.)

.



W istocie implementacja rzeczywistej równoległości
(programowanie równoległe) jest zagadnieniem związanym z
zasobami systemu komputerowego i w zasadzie niezależnym
od programowania współbieżnego.

Podstawowe pojęcia programowania współbieżnego

15

Programowanie:

- współbieżne, - równoległe, -

rozproszone

PROGRAMOWANIE

ROZPROSZONE

(distributed)

PROGRAMOWANIE

RÓWNOLEGŁE

(parallel)

PROGRAMOWANIE

WSPÓŁBIEŻNE

(concurrent)

Podstawowe pojęcia programowania współbieżnego

16

Programowanie:

- współbieżne, - równoległe, -

rozproszone

- Architektura sprzętowa

Systemy z pamięcią

współdzieloną

Wieloprocesory

Systemy ściśle powiązane

Systemy rozproszone

Multikomputery

Systemy luźno powiązane

Podstawowe pojęcia programowania współbieżnego

17

Odmiany programowania

współbieżnego

(z pominięciem programowania równoległego)

Programowanie współbieżne

Klasyczne

programowanie współbieżne

(systemy z pamięcią współdzieloną)

Współbieżność rozproszona

(systemy wieloprocesorowe

z pamięcią lokalną -

systemy rozproszone)

Podstawowe pojęcia programowania współbieżnego

18

Współbieżność klasyczna i

rozproszona



Klasyczne programowanie współbieżne - polega na
dekompozycji problemu na wiele elementów
oprogramowania, które są wykonywane przez pewną liczbę
procesorów z pamięcią współdzieloną, tzw. systemy ściśle
powiązane, inaczej systemy wieloprocesorowe.



Współbieżność rozproszona - polega na dekompozycji
problemu na wiele elementów oprogramowania, które są
wykonywane przez pewną liczbę niezależnych procesorów
(własny zegar taktujący
i pamięć operacyjna) komunikujących się poprzez sieć
połączeń
(np. sieć lokalna, przełącznica krzyżowa, itp.), czyli tzw.
systemy luźno powiązane, inaczej systemy rozproszone.

Podstawowe pojęcia programowania współbieżnego

19

Programowanie współbieżne

na tle innych dziedzin informatyki

Języki
programowania

Języki
programowania

Systemy

Systemy

operacyjne

operacyjne

Systemy

Systemy

operacyjne

operacyjne

Programowanie

Programowanie

współbieżne

współbieżne

• Większość języków programowania nie posiada mechanizmów

programowania współbieżnego (równoległego);

• Pra–język C także nie został zaprojektowany do programowania

zadań do współbieżnej realizacji - jednakże jako język systemu
Unix może wywoływać funkcje systemowe;

• Pierwszym językiem dedykowanym była Ada (~1980r.);

• Kolejnym istotnie ważnym językiem (poza laboratoryjnymi

rozwiązaniami) stała się Java;

• Większość języków programowania nie posiada mechanizmów

programowania współbieżnego (równoległego);

• Pra–język C także nie został zaprojektowany do programowania

zadań do współbieżnej realizacji - jednakże jako język systemu
Unix może wywoływać funkcje systemowe;

• Pierwszym językiem dedykowanym była Ada (~1980r.);

• Kolejnym istotnie ważnym

językiem (poza laboratoryjnymi

rozwiązaniami)

stała się Java

;

Podstawowe pojęcia programowania współbieżnego

20

Języki i środowiska programowania współbieżnego

Z konstrukcjami programowania

współbieżnego -

Concurrent Pascal, Concurrent C, CSP, Ada,

Modula, Java, C#, Linda, Occam, Orca

Umożliwiające programowanie

współbieżne (C/C++, Delphi Pascal).

Język programowania nie zawiera

mechanizmów synchronizacji procesów, lecz

pozwala wykorzystywać obiekty synchronizacji

dostarczane przez system operacyjny

Środowiska i biblioteki programowania

równoległego i rozproszonego -

PVM, MPI, OpenMP, CUDA

Podstawowe pojęcia programowania współbieżnego

21

Program sekwencyjny – program

współbieżny

Podstawowe pojęcia programowania współbieżnego

22

Program sekwencyjny



Program sekwencyjny:



realizacja pojedynczego ciągu instrukcji;



zbiór operacji całkowicie uporządkowany w czasie.



Działanie programu sekwencyjnego polega na wykonywaniu
kolejnych kroków obliczeń zgodnie z przyjętym algorytmem
rozwiązania, przy czym warunkiem koniecznym wykonania
następnego kroku jest zakończenie kroku poprzedniego.



W dowolnej chwili czasu jest wykonywany dokładnie jeden i
tylko jeden krok (instrukcja) algorytmu.



Należy zwrócić uwagę, że wyniki procesów sekwencyjnych można

zawsze odtworzyć na podstawie danych wejściowych.
„Ta własność procesów sekwencyjnych wraz z ich szczególną
prostotą powoduje że są one ważnymi składnikami służącymi do
budowy obliczeń współbieżnych.” –

Per Brinch Hansen „Podstawy systemów

operacyjnych”, WNT 1979, str. 44

Podstawowe pojęcia programowania współbieżnego

23

Program sekwencyjny – sekwencja

procesów

czas

Proces 4

t

4P

P.. 3

t

3P

Proces 2

t

2P

Proces 1

t

1Z

=

t

1P

t

2Z

t

iZ

– czas żądania uruchomienia procesu

t

iP

– czas rozpoczęcia wykonywania procesu

gdzie i - numer procesu

t

3Z

t

4Z

t

S

= t

1

+ t

2

+ t

3

+ t

4

t

1

t

2

t

3

t

4

Podstawowe pojęcia programowania współbieżnego

24

Program sekwencyjny



Program sekwencyjny może być:



skończony – osiąga stan końcowy w czasie
skończonym:



typowy proces usługowy, np. wyliczenie wartości zmiennej;



nieskończony – realizuje algorytm dopóty, dopóki np.
pracuje sprzęt i środowisko operacyjne (na którym został
uruchomiony) lub nie został spełniony określony
warunek końcowy :



interaktywny program reagujący na polecenia użytkownika
napływające w losowych chwilach;



system operacyjny;



proces w błędnie zdefiniowanej nieskończonej pętli;

Podstawowe pojęcia programowania współbieżnego

25

Program współbieżny



Program współbieżny jest zbiorem programów sekwencyjnych
wykonywanych abstrakcyjnie „równolegle”.



Każdy program sekwencyjny wchodzący w skład programu
współbieżnego będziemy nazywali procesem sekwencyjnym.



Każdy proces sekwencyjny może być realizowany na abstrakcyjnym
(wirtualnym) procesorze – fizycznie występują różne architektury;



Mówimy, że dwa (lub więcej) procesy są współbieżne, jeśli jeden z
nich rozpoczyna się przed zakończeniem drugiego;



W świetle tej definicji proces nieskończony jest współbieżny ze
wszystkimi procesami, które rozpoczęły się od niego później;



Powyższa definicja mówi jedynie o potencjalnej równoległości.

Na poziomie sprzętu równoległość może być rzeczywista lub pozorna.
Gdy liczba procesorów dorównuje lub przewyższa liczbę procesów
sekwencyjnych, to mówimy o równoległości rzeczywistej.
W przeciwnym przypadku mówimy o równoległości pozornej.

Podstawowe pojęcia programowania współbieżnego

26

Program współbieżny

czas

Proces 4

P.. 3

Proces 2

Proces 1

t

1ZP

t

2ZP

t

3ZP

t

4ZP

t

W

<= t

1

+ t

2

+ t

3

+ t

4

t

1

t

2

t

3

t

4

Podstawowe pojęcia programowania współbieżnego

27

Wieloprogramowość - wielozadaniowość

Podstawowe pojęcia programowania współbieżnego

28

Wieloprogramowość i

wielozadaniowość

(z punktu widzenia programowania

współbieżnego)



Wieloprogramowość - jest współbieżnym wykonywaniem
wielu niezależnych programów na jednym procesorze.



Obejmuje ona przełączanie procesora do innego programu,
gdy aktualnie wykonywany zamówi operację WE/WY oraz
systemu
z podziałem czasu procesora.



Pojawienie się wieloprogramowości stworzyło konieczność
synchronizacji pracy programów.



Wielozadaniowość (multitasking) - rozwiązywanie problemu
przez jego dekompozycję na wiele procesów współbieżnych.



Wielozadaniowość jest metodą rozwiązania problemu.



Ziarnistość współbieżności;



Należy zwrócić uwagę na różnice w definicjach powyższych pojęć w

programowaniu współbieżnym oraz systemach operacyjnych.

Podstawowe pojęcia programowania współbieżnego

29

Wieloprogramowość i

wielozadaniowość

Ziarnistość programowania współbieżnego



Ziarnistość obliczeń nie jest pojęciem ścisłym - opisuje liczbę
operacji obliczeniowych między punktami synchronizacji
procesów oraz synchronizacji dostępu do danych (na maszynach
z pamięcią wspólną) lub komunikacji (na maszynach z pamięcią
lokalną).



W przypadku programowania współbieżnego zlicza się operacje
między kolejnymi chwilami synchronizacji lub wymiany
komunikatów.



Im większa jest liczba operacji, tym większa ziarnistość (grube
ziarno, gruboziarnistość - ang. coarse grain).



Ziarnistość mała (drobnoziarnistość - ang. fine grain)
występuje, gdy mała liczba danych przypada na procesor,
natomiast jest duża częstotliwość komunikacji i synchronizacji.



Im „mniejsze” procesy, tym więcej możliwej współbieżności,
ale także większy narzut czasu obsługi.

Podstawowe pojęcia programowania współbieżnego

30

Prawo Amdahl’a (1967)

http://en.wikipedia.org/wiki/File:AmdahlsLaw.svg

Potencjalne możliwe przyśpieszenie S algorytmu jest równe:

n – liczba procesów,
T

1

– czas wykonania (n=1),

T

n

– czas wykonania dla n

procesów,
F – udział części nierównoległej.



Główny zarzut: prawo

Amdahl’a ma zastosowanie
tylko dla aplikacji z
niezmiennym rozmiarem
zadania

Podstawowe pojęcia programowania współbieżnego

31

Zasady: (1) dekompozycji, (2)

abstrakcji

(3) sprzyjania naturalnym ludzkim

własnościom



„Dostatecznie zadawalający model

funkcjonowania obiektów i systemów świata

rzeczywistego”

powstaje poprzez zastosowanie zasad:



Zasada dekompozycji - rozdzielenie złożonego problemu na podproblemy,

które można rozpatrywać i rozwiązywać niezależnie od siebie i niezależnie od

całości  procesy sekwencyjne;



Zasada abstrakcji - eliminacja, ukrycie lub pominięcie mniej istotnych

szczegółów rozważanego przedmiotu lub mniej istotnej informacji;

wyodrębnianie cech wspólnych i niezmiennych dla pewnego zbioru bytów i

wprowadzaniu pojęć lub symboli oznaczających takie cechy

 stany i oddziaływania procesów;



Zasada sprzyjania naturalnym ludzkim własnościom - dopasowanie

modeli pojęciowych i modeli realizacyjnych systemów do wrodzonych ludzkich

własności psychologicznych, instynktów oraz mentalnych mechanizmów

percepcji i rozumienia świata.



Powyższe zasady + (4-ta) zasada ponownego użycia



podstawowe

zasady inżynierii oprogramowania!

Podstawowe pojęcia programowania współbieżnego

32

Abstrakcja programowania

współbieżnego (1/2)



Dwiema najważniejszymi technikami stosowanymi przy
tworzeniu abstrakcji programistycznych są:



modularność (hermetyzacja, enkapsulacja),



współbieżność.



Programowanie współbieżne jest abstrakcją stworzoną w
celu modelowania i wnioskowania o dynamicznym
zachowaniu programów.



Abstrakcja programowania współbieżnego polega na
modelowaniu i badaniu przeplatanych ciągów wykonań
atomowych instrukcji procesów sekwencyjnych.

Podstawowe pojęcia programowania współbieżnego

33

Abstrakcja programowania

współbieżnego (2/2)

Abstrakcja programowania współbieżnego obejmuje:

1.

model wzajemnych oddziaływań procesów,

2.

instrukcje atomowe,

3.

czas,

4.

przeplot,

5.

poprawność programu.

Podstawowe pojęcia programowania współbieżnego

34

Proces a wątek (1/2)



Abstrakcja procesu sekwencyjnego jest fizycznie realizowana
przez:



Proces (systemu operacyjnego):



program z danymi wykonywany pod kontrolą systemu
operacyjnego, posiadający przydzielone zasoby (pamięć,
urządzenia we/wy) i rywalizujący o dostęp do procesora; 



Wątek (thread) – lekki proces (lightweight process):



część programu, która może być wykonywana niezależnie od
innych części;



kod i dane są często współdzielone między wątkami;



każdy wątek posiada własny wirtualny procesor;



pracą wątków steruje planista wątków (thread scheduler);



wiąże się z tym pojęcie wielowątkowści (multithreading);



Uwaga – np. w Java każdy program jest wielowątkowy!

Podstawowe pojęcia programowania współbieżnego

35

Proces a wątek 2/2

W

ą

te

k

g

łó

w

n

y

Proces

W

ą

te

k

W

ą

te

k

W

ą

te

k

W

ą

te

k

Zasoby

Zasoby

W

ą

te

k

Zasoby

I/O

Gotowy do uruchomienia (ang. ready to run)

Zawieszony (ang. suspended)

Wznowiony (ang. resumed)

Zablokowany (ang. blocked)

Zakończony (ang. terminated)

Działający (ang. running)

Zazwyczaj jest również wątkiem kończącym wykonywanie

programu

Jest to wątek, od którego pochodzą inne wątki

„potomne”

Podstawowe pojęcia programowania współbieżnego

36

Model wzajemnych oddziaływań

procesów (1/4)



Zajmujemy się abstrakcjami, w których procesy ze sobą
współpracują lub między sobą współzawodniczą;



Współpraca wymaga od procesów komunikowania się –
wykonanie jednego wymaga informacji wytworzonej w innym;



Współzawodnictwo wymaga wzajemnego wykluczania;



W ogólności różne procesy wykonywane jednocześnie na wielu

niepołączonych procesorach (komputerach), niezależnie od
siebie, także można nazwać współbieżnymi
– takie przypadki nie są jednak dla nas interesujące, gdyż nie
wymagają dodatkowych mechanizmów ani na wielu procesorach
ani na jednym (wystarcza cykliczne przełączanie przez system
operacyjny);

Podstawowe pojęcia programowania współbieżnego

37

Model wzajemnych oddziaływań

procesów (2/4)



Powyższy rysunek odpowiada teoretycznemu spojrzeniu na

program współbieżny. Rzeczywisty obraz programu jest uzależniony
od zastosowanego języka programowania, systemu operacyjnego,
bibliotek i/lub obiektów synchronizacji.

proces

sekwencyjny

proces

sekwencyjny

proces

sekwencyjny

proces

sekwencyjny

program współbieżny

…

współdzielony

zasób

komunikat

próba

zajęcia

próba

zajęcia

Podstawowe pojęcia programowania współbieżnego

38

Model wzajemnych oddziaływań

procesów (3/4)

(

wg M. Ben-Ari

)



Komunikacja (kooperacja):



występuje, gdy procesy realizują oddzielne zadania, lecz w sumie
działają, aby osiągnąć wspólny cel;



w trakcie działania procesy mogą chcieć przesłać dane;



wymaga to uporządkowania w czasie (synchronizowania), np.
dane procesu P1 muszą być utworzone zanim zostaną wykorzystane w
P2;



Współzawodnictwo:



dwa procesy ubiegają się o ten sam zasób – np. obliczeniowy,
dostęp do pewnej komórki pamięci lub kanału komunikacyjnego;



współzawodnictwo zawsze wymaga synchronizacji, w tym
rozwiązania problemu wzajemnego wykluczania;



Synchronizacja w komunikacji nie musi wymagać wzajemnego
wykluczania;

Podstawowe pojęcia programowania współbieżnego

39

Wzajemne oddziaływania procesów

(4/4)

(

William Stalling „Systemy operacyjne”, Wyd.

Robomatic, 2004

)

Stopień zależności

Relacje

Wpływ jednego

procesu na inny

Potencjalne

sposoby

sterowania

Procesy niezależne od
siebie

Rywalizacja
(współzawodnictwo)

1. Wynik jednego procesu
nie zależy od działań
pozostałych
2. Możliwe jest
oddziaływanie na tempo
wykonywania procesu

1. Wzajemne
wykluczanie
2. Blokowanie (zasoby
wymienne)
3. Zagłodzenia

Procesy pośrednio
zależne od siebie
(poprzez obiekty
współdzielone)

Współpraca poprzez
wspólne
wykorzystywanie
obiektów

1. Wynik jednego procesu
może zależeć od danych
otrzymanych od innych
2. Możliwy jest wpływ na
tempo wykonywania
procesu

1. Wzajemne
wykluczanie
2. Blokowanie (zasoby
wymienne)
3. Zagłodzenia
4. Zachowanie spójności
danych

Procesy bezpośrednio
zależne od siebie
(korzystanie z
elementarnych procedur
komunikacyjnych)

Współpraca poprzez
komunikację

1. Wynik jednego procesu
może zależeć od danych
otrzymanych od innych
2. Możliwy jest wpływ na
tempo wykonywania
procesu

1. Blokowanie (zasoby
wyczerpywalne)
2. Zagłodzenia

Podstawowe pojęcia programowania współbieżnego

40

Instrukcje atomowe (1/3)



Przez instrukcje atomowe rozumie się podzbiór wybranych
rozkazów procesora realizujących algorytm współbieżny.



Wymaganie atomowości instrukcji odnosi się do koncepcji, w
której operacje na obiekcie wykonuje się jako sekwencje,
charakteryzujące się dwiema cechami:

1.

niepodzielności – stan „przed” i stan „po”,

2.

nieprzerywalności – jeżeli się rozpoczęła, to musi się

zakończyć.



Atomowość instrukcji oznacza, że niezależnie od sposobu
implementacji instrukcji w procesorze jest ona wykonywana
w całości.



W trakcie jej wykonywania nie są obsługiwane żadne
przerwania.



Instrukcje atomowe są bardzo ważnym założeniem
programowania współbieżnego, gdyż pozwalają osiągnąć
jednoznaczność wyniku instrukcji.

Podstawowe pojęcia programowania współbieżnego

41

Instrukcje atomowe – przykłady -

poziom CPU (2/3)



Procesor UltraSPARC:

-

ldstub (load and store unsigned byte),

-

cas (compare and swap),

-

swap (swap byte locations).



Procesor Intel Pentium:

-

cmpxchgl (compare/exchange long; CAS – compare-and-

swap).



Procesor Alpha AXP:

-

ldl_l/stl_c (load-linked/store-conditioanal LL/SC).



Procesor IBM PowerPC:

-

lwarx/stwcx (load-linked/store-conditioanal LL/SC).



Procesor MIPS:

-

ll/sc (load-linked/store-conditioanal LL/SC).



Procesor ARM:

-

ldrex/strex (load-linked/store-conditioanal LL/SC).

Podstawowe pojęcia programowania współbieżnego

42

Instrukcje atomowe – przykłady

– języki programowania (3/3)



W języku Java pakiet java.util.concurrent.atomic
dostarcza atomowych typów danych:
AtomicBoolean,
AtomicInteger,
AtomicLong,
AtomicReference



Metoda compareAndSet() w Java implementuje prymityw
synchronizacyjny CAS (porównaj aktualną wartość z zadaną
i jeśli są równe, to podstaw nową wartość);



C# dostarcza analogiczną funkcjonalność poprzez metodę
Interlocked.CompareExchange;

Podstawowe pojęcia programowania współbieżnego

43

Czas



Czas wykonania instrukcji na różnych procesorach może
być różny;



Abstrakcja programowania współbieżnego zakłada
ignorowanie czasu;



Niedopuszczalna jest zależność czasowa między
procesami!



Interesuje nas poprawność wykonania ciągu instrukcji;



Na wynik analizy poprawności algorytmu nie ma i nie
może mieć wpływu rzeczywisty upływ czasu;

czas

pobier
z

dodaj

mnóż

zapamięt
aj

pobier
z

dodaj

mnóż

zapamięt
aj

realnie różne czasy
wykonania
modelowo równe
(jednostkowe) czasy
wykonania

Podstawowe pojęcia programowania współbieżnego

44

Przeplot (interleave) (1/3)



Instrukcje atomowe wchodzące w skład wszystkich
procesów programu współbieżnego przeplatają się
między sobą;



Możliwe są dowolne kombinacje ciągu wykonań instrukcji;



Jeżeli rozważymy przypadek dwóch instrukcji I1 i I2 w
dwóch procesach P1 i P2, to muszą one spełniać warunek:

koniec(I1) <= początek(I2)

(„Przypadek 1”)



Wykluczamy „Przypadek 2”

początek(I2) < koniec(I1)

,

gdyż wynik dwu jednocześnie wykonywanych instrukcji
musi być taki sam, jak wynik każdego z dwu możliwych
ciągów uzyskanych przez wykonanie tych instrukcji jedna
po drugiej;

I1

I2

I1

I2

czas

Przypadek 2

Przypadek 1

Podstawowe pojęcia programowania współbieżnego

45

Przeplot (interleave) (2/3)



Procesory, które przetwarzają procesy programu współbieżnego
mogą działać z różną szybkością - powoduje to losowość przeplotu;



Poprawnie skonstruowany program współbieżny musi być
poprawny przy wszystkich przeplotach powstałych na różnych
procesorach;



Niech algorytm procesu sekwencyjnego P1 składa się z instrukcji:
P_1:

i11, i12, i13



Niech algorytm procesu sekwencyjnego P1 składa się z instrukcji:
P_2:

i21, i22, i23



Możliwe są przeploty:
PRZ_1:

i11, i21, i12, i22, i13, i23

PRZ_2:

i21, i22, i11, i12, i13, i23



Przeplot:
PRZ_3:

i11, i22, i21, i12, i23, i13

jest niedopuszczalny (błędny). Dlaczego?

Nie wszystkie przeploty współbieżnych procesów są
dopuszczalne z punktu widzenie oczekiwanego
wyniku.

Stąd potrzeba zarządcy procesów współbieżnych
(planisty) odpowiedzialnego za sterowanie
procesami.

Mając ciągi instrukcji przynależne do zbioru
procesów ma on zadanie skonstruowania
poprawnego przeplotu.

Nie wszystkie przeploty współbieżnych procesów są
dopuszczalne z punktu widzenie oczekiwanego
wyniku.

Stąd potrzeba zarządcy procesów współbieżnych
(planisty) odpowiedzialnego za sterowanie
procesami.

Mając ciągi instrukcji przynależne do zbioru
procesów ma on zadanie skonstruowania
poprawnego przeplotu.

Podstawowe pojęcia programowania współbieżnego

46

Przeplot (interleave) (3/3)



Uwaga:



poprawny program współbieżny działa dobrze dla
każdego przeplotu;



program współbieżny nie działa poprawnie, gdy istnieje
co najmniej jeden przeplot, przy którym dochodzi do
sytuacji błędnej;



Istnienie przeplotu w programach współbieżnych:



implikuje konieczność specyfikacji zbioru poprawnych
przeplotów;



jest przyczyną trudności w badaniu poprawności
programu: formalnym (teoretycznym) oraz praktycznym;

Podstawowe pojęcia programowania współbieżnego

47

Poprawność programu

Podstawowe pojęcia programowania współbieżnego

48

Poprawność programów

(sekwencyjnych)



Pojęcie poprawności programów sekwencyjnych jest następujące:
Program jest poprawny, jeśli:



kończy się (zatrzymuje)



oraz zwraca poprawny wynik;



W przypadku programów współbieżnych jest to słuszne w
ograniczonych przypadkach (np. sortowanie), gdyż cechą wielu
programów współbieżnych (np. systemów operacyjnych, systemów
czasu rzeczywistego) jest to, że działają w nieskończonej pętli;



Istnieją dwie definicje poprawności dla programów sekwencyjnych,
różniące się podejściem co do zakończenia programu.



Przyjmijmy, że:



zmienne wejściowe

x

spełniają warunek P(

x

) – tzw. precondition,



zmienne wejściowe

x

i wyjściowe

y

spełniają warunek Q(

x

,

y

).

Podstawowe pojęcia programowania współbieżnego

49

Częściowa poprawność



Dla dowolnych wartości

a

zmiennych wejściowych definiujemy

Poprawność częściową (lokalną) – partial correctness

:



Jeśli zachodzi P(

a

)



i jeżeli program uruchomiony z

a

jako wartościami zmiennych

wejściowych

x

zatrzymuje się,



to zachodzi Q(

a

,

b

), gdzie

b

są poprawnymi wartościami

zmiennych wyjściowych w chwili jego zakończenia.



Częściowa poprawność zakłada, że jeśli program zatrzyma się,
to odpowiedzi muszą być „poprawne”.



Przy badaniu poprawności częściowej nie bierze się pod uwagę, czy
program się zakończył czy nie!



Analogią dla częściowej poprawności jest tzw. własność
bezpieczeństwa (safety) programu współbieżnego - musi być
zawsze spełniona!

Podstawowe pojęcia programowania współbieżnego

50

Całkowita poprawność



Poprawność całkowita (globalna) – total correctness

:



Każde wykonanie programu kończy się



oraz spełnione są P(

a

) i Q(

a

,

b

);



Całkowita poprawność określa zatem, że program zakończy
swoje działanie i wyniki będą „poprawne” (spełnią
warunek Q).



Kończenie się programu dla wszystkich prawidłowych danych
wejściowych (spełniających P(a)) nazywane jest także
warunkiem stopu (stop condition).



W praktyce dowodzi się częściową poprawność programu oraz
spełnienie warunku stopu;



Analogią dla całkowitej poprawności jest tzw. własność
żywotności (liveness) programu współbieżnego – musi być
kiedyś spełniona (teraz lub w przyszłości);

Podstawowe pojęcia programowania współbieżnego

51

Poprawność programu

współbieżnego

(wg M. Ben-Ari, „Podstawy programowania

współbieżnego i rozproszonego”, WNT, Warszawa 1996 )



Własność bezpieczeństwa

określa własności statyczne

poprawnego
programu współbieżnego – zawsze muszą być spełnione;



Własność żywotności

dotyczy własności dynamicznych –

kiedyś muszą
być spełnione;

poprawność

własność

bezpieczeństwa

wzajemne wykluczanie

(mutual exclusion)

własność żywotności

wykluczenie zagłodzenia

(starvation)

własność uczciwości

(fairness)

brak zakleszczeń

(deadlock)

Podstawowe pojęcia programowania współbieżnego

52

Poprawność programu

współbieżnego

(m. in. po uwzględnieniu zmian w terminologii)

Zakleszczenie nazywane jest również blokadą (M. Ben-Ari: „Podstawy programowania
współbieżnego i rozproszonego”, WNT, 1996; M. Ben-Ari: „Podstawy programowania
współbieżnego”, WNT, 1989; A. Silberschatz i in.: „Podstawy systemów operacyjnych”, WNT,
1993), impasem (W. Stallings: „Systemy operacyjne. Struktura i zasady budowy”, PWN, 2006),
zastojem (A.S. Tanenbaum: „Rozproszone systemy operacyjne”, PWN, 1997) a nawet martwym
punktem (Z. Weiss, T. Gruźlewski: „Programowanie współbieżne i rozproszone”, WNT, 1993).

poprawność

własność

bezpieczeństwa

wzajemne wykluczanie

własność żywotności

wykluczenie zagłodzenia

własność uczciwości

brak zakleszczeń

(zastojów, impasów,
blokad)

brak lokalnych i/lub
globalnych blokad i
in. (np. livelock -
uwięzień)

Podstawowe pojęcia programowania współbieżnego

53

Poprawność – bezpieczeństwo i

żywotność



Ilustracją dla własności bezpieczeństwa i żywotności może być
sytuacja na skrzyżowaniu drogowym:



Własność bezpieczeństwa: na poprawnie działającym
skrzyżowaniu nigdy jednocześnie nie znajdą się pojazdy
jadące w kierunkach „wschód-zachód” i „północ-południe”;



Własność żywotności: każdy pojazd, który zamierza
przejechać przez skrzyżowanie, kiedyś przez nie przejedzie;

Podstawowe pojęcia programowania współbieżnego

54

Poprawność – bezpieczeństwo i

żywotność



Dowodzenie poprawności nawet bardzo prostych programów
nie jest rzeczą łatwą, ale dowodzenie własności
bezpieczeństwa i żywotności jest jeszcze trudniejsze.



Metody dowodzenia poprawności wykorzystują techniki znane z
dowodzenia poprawności algorytmów:



oparte o logikę:



własność częściowej poprawności (logika pierwszego rzędu),



logika Hoare’go,



własność stopu (tzw. całkowita poprawność)



oraz inne:



logiki: temporalna (algorytmy i programy reaktywne), modalna,



specyfikacja algebraiczna,



wykorzystanie modeli abstrakcyjnych (programowanie
obiektowe).

Podstawowe pojęcia programowania współbieżnego

55

Podstawowe problemy synchronizacji w

programowaniu współbieżnym

Podstawowe pojęcia programowania współbieżnego

56

Wykluczanie, zakleszczenia,

zagłodzenia i blokady

w programach współbieżnych



W życiu codziennym powszechna jest rywalizacja o wspólne
zasoby, oczekiwanie aktywne lub pasywne na, rezygnacja z nich
lub zaprzestanie działania w przypadku ich braku;



Np. dwie osoby chcą jednocześnie wykorzystać wspólną łazienka,
telefon, skrzyżowanie, obsługa w okienku (a raczej jej działanie);



Brak rozwiązania tego problemu wyklucza wspólne
funkcjonowanie:

1.

naprzemienne wykonywanie (przeplot) niektórych czynności,

2.

naprzemienne korzystanie z tego samego zasobu;



Rozwiązaniem jest stosowanie:



zwykłej uczciwości i uprzejmości;



dobrych obyczajów i reguł niesformalizowanych;



przepisów, zasad, regulaminów, etc;



stosowanie wzajemnego wykluczania;

Podstawowe pojęcia programowania współbieżnego

57

Wykluczanie, zakleszczenia,

zagłodzenia i blokady

w programach

współbieżnych



Skupmy się na problemach synchronizacji podstawowych
dla teorii i praktyki programowania współbieżnego:



wykluczanie procesu współbieżnego (ang. lockout)



zakleszczenie procesu współbieżnego (ang. deadlock,
tackle)



zagłodzenie procesu współbieżnego (ang. starvation)



blokada procesu współbieżnego (ang. blockade, lock),

Podstawowe pojęcia programowania współbieżnego

58

Problem wzajemnego wykluczania



Problem (i potrzeba) wzajemnego wykluczania w programowaniu
współbieżnym występuje, gdy co najmniej dwa procesy nie mogą:

1.

przeplatać pewnych ciągów instrukcji,

2.

jednocześnie korzystać z tego samego zasobu.



Wspólny zasób nosi nazwę krytycznego;



Schemat pracy procesów współbieżnych wyglądać może następująco:



begin



while true do



begin

• lokalne_obliczenia;
• protokół_wstępny;
•

sekcja_krytyczna;

• protokół_końcowy;



end



end;



Sekcja_krytyczna to fragment programu, który może być
jednocześnie wykonywany przez co najwyżej jeden proces.

Podstawowe pojęcia programowania współbieżnego

59

Problem wzajemnego wykluczania



Zatem problem wzajemnego wykluczania można zdefiniować:



Zsynchronizować N procesów, z których każdy



w nieskończonej pętli na przemian zajmuje się własnymi obliczeniami



a następnie wykonuje działania na części współdzielonej,

• w taki sposób, aby wykonanie tej części w dwóch lub więcej procesach nie

pokrywało się w czasie;



Należy zapewnić spełnienie zasad:



W sekcji krytycznej może przebywać co najwyżej jeden proces
jednocześnie (bezpieczeństwo).



Każdy proces, który chce wykonać sekcję krytyczną, w
skończonym czasie powinien do niej wejść (żywotność).



Protokoły wstępny i końcowy korzysta z dostępnych mechanizmów
synchronizacyjnych;



W przypadku braku wsparcia ze strony systemu operacyjnego należy
zastosować algorytmy synchronizacyjne, np. algorytm Petersona;

Podstawowe pojęcia programowania współbieżnego

60

Zakleszczenia procesów

współbieżnych



Warunkiem zakleszczenia procesu współbieżnego jest
procesu żądania równoczesnego dostępu do więcej niż
jednego współdzielonego zasobu przez jeden proces.



Proces współbieżny po zajęciu jednego z zasobów
bezskutecznie usiłuje zająć pozostałe z potrzebnych mu
zasobów równocześnie nie zwalniając uprzednio zajętego
zasobu(ów).



W tym czasie każdy z zasobów, który został wywłaszczony
przez zakleszczony proces współbieżny jest blokowany
dla pozostałych procesów oczekujących na ten zasób.



Wyróżnia się:



zakleszczenia symetryczne,



cykle zakleszczeń symetrycznych.

Podstawowe pojęcia programowania współbieżnego

61

Warunki Coffmana – Warunki

konieczne dla wystąpienia

zakleszczenia procesów



Wzajemne wykluczanie (Mutual exclusion condition)



Każdy z zasobów jest w stanie: wolny albo zajęty (przez dokładnie jeden
proces);



Szeregowanie bez wywłaszczania (No prememption condition)



Zasoby nie podlegają wywłaszczeniu - zasób zajęty przez pewien
proces może być zwolniony tylko przez ten sam proces;



Częściowy przydział - przetrzymywanie i oczekiwanie (Wait and hold
condition)



Proces posiadający pewien zasób może żądać innego zasobu;



Wzajemne czekanie - oczekiwanie cykliczne (Circular wait condition)



Musi istnieć zamknięty łańcuch procesów oczekujących na zasób
zajęty przez następnika (‚1’ na ‚2’…‚i’ na ‚i+1’…‚N’ na ‚1’)



Zapobieganie zakleszczeniom jest możliwe, jeśli jeden lub więcej z

warunków koniecznych nigdy nie będzie spełniony.

Podstawowe pojęcia programowania współbieżnego

62

Przykładowe powody braku

żywotności (1/4)

Ac1

Ac2

R1

R2

dostęp

dostęp

żądanie

proces

zakleszczony:

Ac1

Podstawowe pojęcia programowania współbieżnego

63

Przykładowe powody braku

żywotności (2/4)

Symetryczne zakleszczenia procesów



Zakleszczenie symetryczne jest uważane za
klasyczny przykład zakleszczenia:

Ac1

Ac2

R1

R2

żądanie

dostęp

dostęp

procesy

zakleszczone:

Ac1, Ac2

Podstawowe pojęcia programowania współbieżnego

64

Przykładowe powody braku

żywotności (3/4)

procesy

zakleszczone:

Ac1, Ac2, Ac3

Acp

Ac1

R1

R2

Ac2

R3

Ac3

Rp

dostęp

żądanie

Podstawowe pojęcia programowania współbieżnego

65

Przykładowe powody braku

żywotności (4/4)

Cykl zakleszczeń procesów

procesy

zakleszczone:

Ac1, Ac2,

Ac3, ..., Acn

Acn

Ac1

R1

R2

Ac2

R3

Ac3

Rn

żądanie

dostęp

Podstawowe pojęcia programowania współbieżnego

66

Wykluczanie się procesów

współbieżnych



W czasie wykonywania się programu współbieżnego działa
tzw. planista (zarządca);



Jest to składowa oprogramowania systemowego
odpowiedzialna za sprawiedliwe (uczciwe) dopuszczanie do
zasobów procesów oczekujących na ich usługi;



Jeżeli jednak w działającym programie współbieżnym
występują takie procesy, które pomimo dopełnienia
wszelkich warunków niezbędnych dla poinformowania
planisty o tym, że oczekują one na dostęp do zasobów
współdzielonych, takiego dostępu nie otrzymują, to mówi
się o nich, że są wykluczane;



Inaczej o takich procesach mówi się, że są głodzone;

Podstawowe pojęcia programowania współbieżnego

67

Efekt (zjawisko) zagłodzenia

procesu współbieżnego



Głodzenie procesów współbieżnych może być spowodowane
brakiem uczciwości w działaniu planisty lub zakleszczeniami
procesów współbieżnych;



Końcowym stanem nieskończonego wstrzymywania
(blokowania, głodzenia) procesu jest efekt zagłodzenia
(starvation), lub inaczej wykluczenia.



Mimo że możliwość zagłodzenia świadczy o niepoprawności
programu, to czasami jest akceptowane (na przykład
wszędzie tam, gdzie stosuje się kolejkę priorytetową).



Wynika to z faktu, że zagłodzenie jest zwykle mało
prawdopodobne.

Podstawowe pojęcia programowania współbieżnego

68

Oczekiwanie procesu na

wywłaszczenie zasobu

współdzielonego

Blokada procesu



Występują dwa sposoby oczekiwania procesu

współbieżnego na udostępnienie przez „planistę”

współdzielonego zasobu:



aktywne czekanie (ang. busy-waiting) – proces

samoczynnie co pewien interwał czasowy ponawia

swoje żądanie dostępu do zasobu:



trwałe aktywne czekanie – proces ponawia żądania

dostępu aż do skutecznego wywłaszczenia zasobu,



nietrwałe aktywne czekanie – proces ponawia żądanie

dostępu do zasobu określoną liczbę razy, po czym

przechodzi do pasywnego czekania.



pasywne czekanie – proces jednorazowo wysyła do

„planisty” żądanie dostępu do zasobu, po czy przestaje

być aktywny. Jedynie planista jest w stanie ponownie

uaktywnić ten proces.

Podstawowe pojęcia programowania współbieżnego

69

Globalna blokada programu

współbieżnego



Globalna blokada programu współbieżnego (ang. global
deadlock) występuje wtedy, gdy w programie nie ma takiego
procesu współbieżnego, który nie występowałby w stanie
zagłodzenia albo w stanie zakleszczenia.



Nie można wtedy zidentyfikować w systemie żadnego
procesu współbieżnego, który wykonywałby sensowną pracę.



Zablokowany program współbieżny nie jest poprawny
(bezpieczny, żywotny).

Podstawowe pojęcia programowania współbieżnego

70

Własność uczciwości - rodzaje



Uczciwość słaba - jeżeli proces nieprzerwanie zgłasza
żądanie, to kiedyś będzie ono obsłużone.



Uczciwość mocna - jeżeli proces zgłasza żądanie
nieskończenie wiele razy, to kiedyś będzie ono obsłużone.



Oczekiwanie liniowe - jeżeli proces zgłasza żądanie, to
będzie ono obsłużone zanim dowolny inny proces zostanie
obsłużony więcej niż raz.



FIFO (pierwszy wszedł, pierwszy wyjdzie) - jeżeli proces
zgłasza żądanie, to będzie ono obsłużone przed dowolnym
żądaniem zgłoszonym później.



Uczciwość słaba i mocna ma znaczenie teoretyczne.



W praktyce jest stosowane oczekiwanie liniowe lub FIFO.



Obydwa mogą być implementowane w systemach
scentralizowanych - w systemach rozproszonych występują
problemy z realizacją algorytmu FIFO.

Podstawowe pojęcia programowania współbieżnego

71

Zalecenia i przykłady

Podstawowe pojęcia programowania współbieżnego

72

8 reguł projektowania aplikacji

współbieżnych

(C. Breshears: „The Art of Concurrency”)



Reguła 1 – Zidentyfikuj naprawdę niezależne obliczenia



Reguła 2 – Implementuj współbieżność w możliwie

najwyższej warstwie systemu komputerowego



Reguła 3 – Od początku planuj skalowanie aplikacji, aby

wyzyskiwać możliwość zwiększenia liczby CPU



Reguła 4 – Wykorzystuj biblioteki bezpieczne wątkowo

(ang. thread-safe libraries) gdziekolwiek to możliwe



Reguła 5 – Użyj właściwego modelu wątków (explicit vs.

implicit thread model) – preferuj model typu „implicit”



Reguła 6 – Nigdy nie zakładaj określonego porządku

wykonywania instrukcji



Reguła 7 – Używaj zmiennych lokalnych w wątkach lub

kojarz blokady (ang. locks) do określonych danych



Reguła 8 – Odważ się zmienić algorytm dla zwiększenia

szansy na współbieżne wykonywanie

Podstawowe pojęcia programowania współbieżnego

73

Całkowanie numeryczne (numerical

integration)

static long num_rects = 100000;
void main () {
int i;
double mid, height, width, sum = 0.0;
double area;

width = 1.0/(double) num_rects;
for (i = 0; i < num_rects; i++) {

mid = (i + 0.5) * width;
height = 4.0/(1.0 + mid * mid);
sum += height;

}

area = width * sum;

printf("Computed pi = %f\n", area);
}

dx

x







1

0

2

1

4



Podstawowe pojęcia programowania współbieżnego

74

Implicit Threading – ukryta

współbieżność

np. Open MP, Intel Threading

Building Blocks (TBB)

static long num_rects = 100000;

int main(int argc, char* argv[]) {
double mid, height, width, sum = 0.0;
int i;
double area;

width = 1.0/(double) num_rects;

#pragma omp parallel for private(mid, height) reduction(+:sum)

for (i = 0; i < num_rects; i++) {

mid = (i + 0.5) * width;
height = 4.0/(1.0 + mid * mid);
sum += height;

}

area = width * sum;
printf("Computed pi = %f\n", area);
return 0;
}

Zmienna środowiskowa OMP_NUM_THREADS określa liczbę wątków.

Podstawowe pojęcia programowania współbieżnego

75

Explicit Threading – jawna

współbieżność

np. POSIX threads (Pthreads),

Windows Threads

#include <stdio.h>
#include <pthreads.h>

#define NUM_RECTS 100000
#define NUM_THREADS 4

double gArea = 0.0;
pthread_mutex_t gLock;

void *threadFunction(void *pArg) {
int myNum = *((int *) pArg);
double partialHeight = 0.0, lWidth = 1.0 / NUM_RECTS, x;

for (int i = myNum; i < NUM_RECTS; i += NUM_THREADS) {

x = (i + 0.5f) / NUM_RECTS;
partialHeight += 4.0f / (1.0f + x * x);

}

pthread_mutex_lock(&gLock);

gArea += partialHeigth * lWidth;

pthread_mutex_unlock(&gLock);
}

/* cd. następny slajd */

Podstawowe pojęcia programowania współbieżnego

76

Explicit Threading – jawna

współbieżność

np. POSIX threads (Pthreads) – cd.

/* cd. poprzedniego slajdu */
void main () {
pthread_t tHandles[NUM_THREADS];
int tNum[NUM_THREADS];

pthread_mutex_init(&gLock, NULL);
for (int i = 0; i < NUM_THREADS; i++) {

tNum[i] = i;

pthread_create(&tHandles[i], NULL, threadFunction, (void *)&tNum[i]);

}

for (int j=0; j < NUM_THREADS; j++) {

pthread_join(tHandles[j], NULL);

}

pthread_mutex_destroy(&gLock);
printf("Computed pi = %f\n", gArea);
}

Podstawowe pojęcia programowania współbieżnego

77

Podsumowanie

Podstawowe pojęcia programowania współbieżnego

78

Zalety obliczeń współbieżnych



Przyspieszenie obliczeń - możliwość szybszego uzyskania
wyniku niż na najszybszej maszynie sekwencyjnej.



Zwiększenie niezawodności działania lub dokładności
obliczeń.



Możliwość rozwiązania zadań zbyt dużych dla maszyn
sekwencyjnych.



Obliczenia współbieżne pozwalają na lepsze
(efektywniejsze) wykorzystanie instalacji maszyny cyfrowej,
gdyż synchronizacyjne ograniczenia między fizycznymi
składowymi są zredukowane do minimum.



Dostatecznie zadawalający model funkcjonowania
obiektów
i systemów świata rzeczywistego.

Podstawowe pojęcia programowania współbieżnego

79

Wady obliczeń współbieżnych



Konieczność dekompozycji problemu na niezależne od
siebie części mogące być wykonywane równolegle.



Mechanizmy synchronizacji wprowadzają dodatkowy narzut
czasowy na ich obsługę, co przy ich nieumiejętnej
implementacji lub użyciu może nawet doprowadzić do
zwiększenia czasu wykonania obliczeń.



Złożone testowanie programu wymagające uwzględnienia
dynamiki zmian stanów procesów.



Wyniki obliczeń współbieżnych mogą być zależną od czasu
funkcją danych wejściowych. Powtórzenie błędnego
obliczenia, w celu umiejscowienia i poprawienia błędów,
jest prawie niemożliwe.

Podstawowe pojęcia programowania współbieżnego

80

Materiał dodatkowy

Rozwój architektury komputerów

Podstawowe pojęcia programowania współbieżnego

82

Inne definicje blokad

Podstawowe pojęcia programowania współbieżnego

83

Deadlock

, Livelock, Starvation

(wg Richard H. Carver, Kuo-Chung Tai: Modern

Multithreading,

John Wiley&Sons, 2006)



Deadlock – wymaga jednego lub większej liczby na stałe

zablokowanych procesów.



Proces P jest zablokowany jeśli się nie wykonuje i czeka na

zajście pewnego zdarzenia, które nigdy nie zajdzie.



Ex: Załóżmy, że na końcu pracy programu współbieżnego CP

istnieje proces P, który spełnia warunki:

a) proces P jest zablokowany podczas wykonywania pewnego

kodu służącego synchronizacji (np. oczekiwanie na odebranie

wiadomości),

b) proces P pozostaje zablokowany na zawsze, niezależnie od

tego co zrobią inne procesy;

 Proces P jest zakleszczony (ang. deadlocked) a w programie

CP wystąpiło zakleszczenie (ang. deadlock).

Podstawowe pojęcia programowania współbieżnego

84

Deadlock,

Livelock

, Starvation

(wg Richard H. Carver, Kuo-Chung Tai: Modern

Multithreading,

John Wiley&Sons, 2006)



Livelock – analogiczna sytuacja do deadlock’a z aktywnym
czekaniem.



Proces P wykonuje się (albo jest gotowy do działania), nie jest
zablokowany, ale nigdy nie wykona żadnego postępu w
realizacji algorytmu.



Ex: Załóżmy, że istnieje przeplot S programu współbieżnego
CP, dla którego proces P spełnia warunki:

a) proces P nie jest zablokowany ani zakleszczony (ang.

deadlock),

b) proces P nigdy nie wykonana postępu;
 Proces P jest wstrzymywany (ang. livelocked) a w programie

CP wystąpiła blokada (ang. livelock).

Podstawowe pojęcia programowania współbieżnego

85

Deadlock, Livelock,

Starvation

(wg Richard H. Carver, Kuo-Chung Tai: Modern

Multithreading,

John Wiley&Sons, 2006)



Starvation - zagłodzenie.



Ex: Załóżmy, że w programie współbieżnym CP istnieje
przeplot S, dla którego na koniec cyklu są spełnione trzy
warunki:

a) przeplot S zakończył się nieskończenie powtarzanym

wykonaniem kodu spełniającego zasadę uczciwości,

b) istnieje niezakończony proces P, który nie wykonuje postępu

w realizacji alorytmu,

c) proces P nie jest zakleszczony (ang. deadlock), ani

wstrzymywany (ang. livelock);

 Proces P jest zagłodzony (ang. starved) a w programie CP

wystąpiło zagłodzenie (ang. starvation).