Programowanie współbieżne
Wprowadzenie do programowania współbieżnego.
Podstawowe pojęcia programowania współbieżnego.
Prowadzący: dr inż. Dariusz Pierzchała
dariusz.pierzchala@wat.edu.pl
Programowanie współbieżne
Wprowadzenie do programowania współbieżnego.
Podstawowe pojęcia programowania współbieżnego.
Prowadzący: dr inż. Dariusz Pierzchała
dariusz.pierzchala@wat.edu.pl
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).