Darmowy fragment publikacji:
Wszelkie prawa zastrzeżone. Nieautoryzowane rozpowszechnianie całości lub fragmentu niniejszej
publikacji w jakiejkolwiek postaci jest zabronione. Wykonywanie kopii metodą kserograficzną,
fotograficzną, a także kopiowanie książki na nośniku filmowym, magnetycznym lub innym
powoduje naruszenie praw autorskich niniejszej publikacji.
Wszystkie znaki występujące w tekście są zastrzeżonymi znakami firmowymi
bądź towarowymi ich właścicieli.
Autor oraz Wydawnictwo HELION dołożyli wszelkich starań, by zawarte w tej książce informacje
były kompletne i rzetelne. Nie biorą jednak żadnej odpowiedzialności ani za ich wykorzystanie, ani
za związane z tym ewentualne naruszenie praw patentowych lub autorskich. Autor oraz
Wydawnictwo HELION nie ponoszą również żadnej odpowiedzialności za ewentualne szkody
wynikłe z wykorzystania informacji zawartych w książce.
Redaktor prowadzący: Michał Mrowiec
Projekt okładki: Studio Gravite / Olsztyn
Obarek, Pokoński, Pazdrijowski, Zaprucki
Wydawnictwo HELION
ul. Kościuszki 1c, 44-100 GLIWICE
tel. 32 231 22 19, 32 230 98 63
e-mail: helion@helion.pl
WWW: http://helion.pl (księgarnia internetowa, katalog książek)
Drogi Czytelniku!
Jeżeli chcesz ocenić tę książkę, zajrzyj pod adres
http://helion.pl/user/opinie?prowsp
Możesz tam wpisać swoje uwagi, spostrzeżenia, recenzję.
ISBN: 978-83-246-4302-8
Copyright © Helion 2012
Printed in Poland.
• Kup książkę
• Poleć książkę
• Oceń książkę
• Księgarnia internetowa
• Lubię to! » Nasza społeczność
Spis treĈci
Rozdziaä 1. Wstöp .............................................................................................. 7
1.1. Geneza ksiąĪki ........................................................................................................... 7
1.2. Cele ............................................................................................................................ 9
Rozdziaä 2. Programowanie wspóäbieĔne ........................................................... 11
2.1. Wprowadzenie ......................................................................................................... 12
2.2. Podstawowe pojĊcia ................................................................................................ 22
2.2.1. Proces, zasób, procesy wspóábieĪne .............................................................. 23
2.2.2. Program wspóábieĪny .................................................................................... 24
2.3. Synchronizacja i komunikacja ................................................................................. 25
2.4. Podsumowanie ......................................................................................................... 27
2.5. ûwiczenia i zadania ................................................................................................. 28
Rozdziaä 3. PoprawnoĈè programów wspóäbieĔnych ........................................... 29
3.1. Wprowadzenie ......................................................................................................... 29
3.2. Wzajemne wykluczanie ........................................................................................... 32
3.3. ĩywotnoĞü globalna ................................................................................................. 34
3.3.1. Warunki konieczne wystąpienia blokady ...................................................... 41
3.3.2. Metody wykrywania i likwidacji blokad ....................................................... 44
3.3.3. Metody zapobiegania blokadom .................................................................... 46
3.3.4. Metody unikania blokad ................................................................................ 49
3.4. ĩywotnoĞü lokalna ................................................................................................... 50
3.5. Podsumowanie ......................................................................................................... 52
3.6. ûwiczenia i zadania ................................................................................................. 53
Rozdziaä 4. Zadania ......................................................................................... 57
4.1. Wprowadzenie ......................................................................................................... 58
4.2. Deklaracja typu zadaniowego .................................................................................. 62
4.3. Tworzenie zadaĔ ...................................................................................................... 66
4.4. Aktywacja, wykonanie, finalizacja i likwidacja zadaĔ ............................................ 74
4.4.1. Fazy aktywacji i wykonania zadaĔ ................................................................ 75
4.4.2. Fazy finalizacji i likwidacji zadaĔ ................................................................. 77
4.4.3. BáĊdy kreacji i aktywacji zadaĔ ..................................................................... 79
4.5. Hierarchiczna struktura zadaĔ ................................................................................. 81
4.5.1. Fazy kreacji, aktywacji i wykonania zadaĔ ................................................... 81
4.5.2. Fazy finalizacji i likwidacji zadaĔ ................................................................. 83
4.6. Podsumowanie ......................................................................................................... 91
4.7. ûwiczenia i zadania ................................................................................................. 91
4
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
Rozdziaä 5. Zmienne dzielone i semafory ........................................................... 95
5.1. Wprowadzenie ......................................................................................................... 95
5.2. Zmienne dzielone .................................................................................................... 96
5.3. Semafory ............................................................................................................... 104
5.3.1. Definicje semaforów ................................................................................... 105
5.3.2. Wzajemne wykluczanie ............................................................................... 106
5.4. ûwiczenia i zadania ............................................................................................... 112
Rozdziaä 6. Spotkania .................................................................................... 115
6.1. Wprowadzenie ....................................................................................................... 115
6.2. Instrukcja selektywnego wyboru — select ............................................................ 122
6.2.1. Selektywne oczekiwanie .............................................................................. 123
6.2.2. Dozory wejĞü ............................................................................................... 128
6.2.3. GaáĊzie delay, else, terminate ...................................................................... 131
6.2.4. Wyjątek Program_Error .............................................................................. 139
6.3. Warunkowe i terminowe wywoáanie wejĞcia ........................................................ 141
6.4. ZagnieĪdĪone spotkania ......................................................................................... 144
6.5. Pakiety ................................................................................................................... 147
6.6. Podsumowanie ....................................................................................................... 150
6.7. ûwiczenia i zadania ............................................................................................... 151
Rozdziaä 7. Monitory i obiekty chronione ........................................................ 155
7.1. Wprowadzenie........................................................................................................ 155
7.2. Monitory................................................................................................................. 156
7.2.1. Zmienne warunkowe .................................................................................... 157
7.2.2. Przykáady programów .................................................................................. 163
7.3. Obiekt chroniony .................................................................................................... 166
7.3.1. Specyfikacja typu chronionego..................................................................... 167
7.3.2. Synchronizacja warunkowa.......................................................................... 171
7.3.3. Semantyka wykonaĔ metod skáadowych...................................................... 172
7.3.4. Rodzina wejĞü .............................................................................................. 176
7.3.5. Przykáady programów — obiekt chroniony.................................................. 180
7.4. Instrukcja rekolejkowania....................................................................................... 181
7.4.1. Problem alokacji zasobów............................................................................ 181
7.4.2. Skáadnia instrukcji requeue .......................................................................... 192
7.4.3. Problem alokacji zasobów w systemach czasu rzeczywistego .................... 193
7.5. Instrukcja abort....................................................................................................... 197
7.6. Asynchroniczna zmiana sterowania........................................................................... 198
7.7. Podsumowanie........................................................................................................ 218
7.8. ûwiczenia i zadania................................................................................................ 219
Rozdziaä 8. Problemy programowania wspóäbieĔnego ....................................... 223
8.1. Problem konsumenta i producenta ......................................................................... 223
8.1.1. Semafory ..................................................................................................... 226
8.1.2. Spotkania ..................................................................................................... 230
8.1.3. Monitory ...................................................................................................... 231
8.1.4. Obiekty chronione ....................................................................................... 232
8.1.5. Podsumowanie ............................................................................................. 233
8.2. Problem piĊciu filozofów ...................................................................................... 236
8.2.1. Semafory ..................................................................................................... 238
8.2.2. Monitory ...................................................................................................... 240
8.2.3. Obiekty chronione ....................................................................................... 242
8.2.4. Spotkania ..................................................................................................... 247
8.2.5. Podsumowanie ............................................................................................. 251
Spis treĈci
5
8.3. Problem pisarzy i czytelników ............................................................................... 252
8.3.1. Semafory ..................................................................................................... 253
8.3.2. Spotkania ..................................................................................................... 254
8.3.3. Monitory ...................................................................................................... 255
8.3.4. Obiekty chronione ....................................................................................... 256
8.3.5. Podsumowanie ............................................................................................. 258
8.4. ûwiczenia i zadania ............................................................................................... 258
Rozdziaä 9. Programowanie systemów czasu rzeczywistego .............................. 261
9.1. Wprowadzenie ....................................................................................................... 261
9.2. Metoda ustalonego priorytetu ................................................................................ 267
9.2.1. Priorytety bazowe ........................................................................................ 269
9.2.2. Problem inwersji priorytetu ......................................................................... 270
9.3. Szeregowanie zadaĔ w kolejkach wejĞü ................................................................ 274
9.4. Metoda szeregowania bez wywáaszczenia ............................................................. 276
9.5. Metoda Round-Robin ............................................................................................ 276
9.6. Metoda EDF .......................................................................................................... 278
9.6.1. Reprezentacja terminów .............................................................................. 278
9.6.2. Szeregowanie zadaĔ .................................................................................... 280
9.6.3. Metoda EDF i protokóá ICPP ...................................................................... 281
9.7. Priorytety dynamiczne ........................................................................................... 288
9.8. Synchroniczne i asynchroniczne sterowanie zadaniami ........................................ 289
9.8.1. Synchroniczne sterowanie zadaniami .......................................................... 290
9.8.2. Asynchroniczne sterowanie zadaniami ........................................................ 290
9.9. Podsumowanie ....................................................................................................... 291
9.10. ûwiczenia i zadania ............................................................................................. 292
Dodatek A. Przykäady programów ..................................................................... 293
Literatura ........................................................................................................ 311
Skorowidz ....................................................................................................... 313
6
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
Rozdziaä 8.
Problemy programowania
wspóäbieĔnego
Do klasycznych problemów programowania wspóábieĪnego naleĪą problem produ-
centa i konsumenta, problem pisarzy i czytelników oraz problem piĊciu filozofów.
W poprzednich rozdziaáach, przy okazji prezentacji metod weryfikacji poprawnoĞci
programów wspóábieĪnych oraz opisu róĪnych mechanizmów synchronizacji, czĊĞü
tych problemów zostaáa mniej lub bardziej szczegóáowo omówiona. Celem tego roz-
dziaáu jest nie tylko szczegóáowe przedstawienie wymagaĔ dotyczących zasad wspóá-
pracy procesów w klasycznych problemach wspóábieĪnych, ale przede wszystkim przed-
stawienie róĪnych rozwiązaĔ (przy zastosowaniu róĪnych mechanizmów synchronizacji)
oraz ocena ich efektywnoĞci.
Ten rozdziaá stanowi pewne podsumowanie dotychczas prezentowanych rozwiązaĔ
problemów programowania wspóábieĪnego oraz przede wszystkim mechanizmów
synchronizacji, zarówno tych dostĊpnych w Adzie (obiekty chronione i spotkania), jak
i klasycznych mechanizmów synchronizacji (monitory, semafory)1. Dlatego teĪ w tym
miejscu pozwolono sobie na przypomnienie struktury niektórych juĪ zaprezentowanych
rozwiązaĔ i ich uproszczoną implementacjĊ, jednak skupiono szczególną uwagĊ na
tych rozwiązaniach, które bĊdą prezentowane po raz pierwszy.
8.1. Problem konsumenta i producenta
Problem producenta i konsumenta jest abstrakcją wielu rzeczywistych problemów
wystĊpujących w systemach operacyjnych i w szczególnoĞci w wielomarszrutowych
systemach produkcyjnych. Przykáadem moĪe byü wspóápraca procesów w systemach
1 Czytelnik zapewne zauwaĪyá, Īe choü obiekt chroniony jest jednym z dwóch podstawowym mechanizmów
synchronizacji zadaĔ w Adzie, to w poprzednich rozdziaáach w sposób bardziej szczegóáowy omówiono
instrukcjĊ rekolejkowania i mechanizm asynchronicznej zamiany sterowania zadaniem. W tym rozdziale
jest miejsce na wiele przykáadów rozwiązaĔ problemów wspóábieĪnych opartych na obiekcie chronionym.
224
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
operacyjnych, w których programy uĪytkowe dokonują analizy i przetwarzania pewnych
zestawieĔ danych, które z kolei muszą byü zinterpretowane przez inne procesy uĪytkow-
nika lub procesy systemu operacyjnego, m.in. prosty program obsáugi danych z urządze-
nia wejĞciowego (np. klawiatura), który jest konsumowany przez program uĪytkowy.
W problemie producenta i konsumenta producent cyklicznie produkuje porcjĊ danych
i przekazuje ją konsumentowi, który konsumuje ją w swojej sekcji lokalnej. Struktura
procesów konsumenta i producenta jest nastĊpująca:
-- sekcja lokalna
task Producent;
task body Producent is
info: Integer := 1;
begin
loop
Produkuj;
Protokóđ_wstúpny; -- sprawdza, czy są wolne miejsca
Umieszcza_dane_w_buforze; -- lub przekazuje bezpoĞrednio konsumentowi
Protokóđ_koēcowy; -- sygnalizuje umieszczenie danych w buforze
end loop;
end Producent;
task Konsument;
task body Konsument is
info: Integer := 1;
begin
loop
Protokóđ_wstúpny; -- sprawdza, czy są dane w buforze
Pobiera_dane_z_bufora; -- lub otrzymuje bezpoĞrednio od producenta
Protokóđ_koēcowy; -- sygnalizuje o zwolnieniu miejsca w buforze
Konsumuj; -- sekcja lokalna
end loop;
end Konsument;
W literaturze rozwaĪa siĊ implementacje dla róĪnych rozmiarów bufora:
bufor jednostkowy (o pojemnoĞci równej 1);
bufor nieskoĔczony;
bufor ograniczony (n-elementowy).
Najprostszy przypadek problemu producenta i konsumenta sprowadza siĊ do synchro-
nizowania dwóch procesów: producenta i konsumenta. Producent cyklicznie produkuje
jedną porcjĊ danych i przekazuje ją bezpoĞrednio konsumentowi. W przypadku ko-
munikacji synchronicznej porcja danych bĊdzie przekazana, gdy producent jest gotów do
wysáania danych, a konsument do ich odebrania. JeĞli jeden z procesów nie jest gotowy
do wysáania lub pobrania danych, to zostaje zawieszony w oczekiwaniu na drugi, co ozna-
cza, Īe reprezentacja bufora w tym rozwiązaniu jest zbĊdna.
WiĊkszą elastycznoĞü wykonywania procesów zapewnia komunikacja asynchroniczna
pomiĊdzy producentem a konsumentem, uzyskiwana poprzez wprowadzenie bufora.
W tym przypadku producent po wyprodukowaniu danych umieszcza je w buforze i moĪe
wykonywaü kolejne operacje bez wzglĊdu na to, czy konsument w danej chwili moĪe
pobraü porcje, czy teĪ nie.
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
225
Bufor stanowi listĊ zawierającą dane wyprodukowane przez producenta, który umiesz-
cza dane na koĔcu listy (dokáadnie w pierwszym wolnym miejscu w buforze), konsu-
ment natomiast pobiera dane z początku listy (dokáadnie z pierwszego miejsca, w którym
zostaáy umieszczone dane). Takie rozwiązanie zapewnia, Īe porcje bĊdą konsumowane
w kolejnoĞci ich wyprodukowania, co jest jednym z zaáoĪeĔ dotyczących wspóápracy
procesów w rozwaĪanym problemie. Producent moĪe w dowolnej chwili umieĞciü porcje
danych w niepeánym buforze, konsument natomiast w dowolnej chwili moĪe pobraü dane
z niepustego bufora.
Bufor nieskoĔczony nie ma praktycznego zastosowania i jego implementacja moĪe
byü wstĊpem dla poprawnej implementacji buforów skoĔczonych2.
W rzeczywistych systemach mamy do czynienia najczĊĞciej z buforem ograniczonym
i to on bĊdzie podmiotem prezentowanych w tym rozdziale rozwiązaĔ. CiągáoĞü wyko-
nywania procesów producenta i konsumenta zaleĪy od rozmiaru bufora. Z kolei wy-
znaczenie odpowiedniego rozmiaru bufora zaleĪy od wzglĊdnej liczby producentów
i konsumentów oraz od wzglĊdnej prĊdkoĞci wykonania procedur produkcji i kon-
sumpcji. ZauwaĪmy, Īe jeĪeli producenci szybciej produkują, niĪ konsumenci konsu-
mują dane, to dowolny rozmiar bufora okaĪe siĊ po pewnym czasie za maáy, a w sytuacji
odwrotnej, kiedy to konsumenci szybciej konsumują, niĪ producenci produkują, dowolny
rozmiar bufora okaĪe siĊ nadmiarowy. àatwo zauwaĪyü, Īe wiĊkszy rozmiar bufora
minimalizuje (lub w szczególnym przypadku likwiduje) czas oczekiwania producentów
na wolne miejsca w buforze. Jednak w rzeczywistych systemach rozmiar bufora ma
wpáyw na koszty budowy systemu, stąd problem okreĞlenia satysfakcjonującego rozmiaru
bufora jest jednym z gáównych problemów stojących przed projektantami Elastycznych
Systemów Produkcyjnych — w tych systemach bufory mogą reprezentowaü magazyny
lub liczbĊ podajników w danym gnieĨdzie albo stacji montaĪowej3.
Implementacje bufora jednoelementowego oraz nieskoĔczonego są szczególnymi przy-
padkami implementacji n-elementowego bufora i dlatego nie bĊdą przedmiotem roz-
waĪaĔ. Reprezentacją w programie n-elementowego bufora moĪe byü bufor cykliczny
(rysunek 8.1). Jest on prosty i wygodny w implementacji, ale ma zastosowanie jedynie
w systemach, w których rozmiar bufora jest staáy. Implementacja problemu producenta
i konsumenta z buforem o zmiennym rozmiarze lub z pulą buforów są przedmiotem zadaĔ
do wykonania dla Czytelników.
Ponadto oprócz klasycznego wariantu, w którym wystĊpują tylko dwa procesy — jeden
proces producenta oraz jeden proces konsumenta — czĊsto problem dotyczy synchro-
nizacji wielu producentów i wielu konsumentów. NaleĪy podkreĞliü, Īe poprawnoĞü
prezentowanych rozwiązaĔ nie zaleĪy od wzglĊdnej liczby producentów i konsumentów
oraz od prĊdkoĞci wykonywania.
2 àatwo zauwaĪyü, Īe w przypadku implementacji bufora nieskoĔczonego programiĞci muszą jedynie
skupiü siĊ na synchronizacji procesów konsumenta, tak aby nie pobieraáy one porcji z pustego bufora.
Te reguáy synchronizacji mogą byü bezpoĞrednio przeniesione do implementacji bufora nieskoĔczonego,
rozszerzone o reguáy synchronizacji producentów.
3 W przypadku ogólnym problem okreĞlenia optymalnego rozmiaru bufora naleĪy do klasy problemów
NP-zupeánych.
226
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
Rysunek 8.1.
Bufor cykliczny
Efektywne rozwiązanie problemu producenta i konsumenta umoĪliwia jednoczesne
pobieranie i wstawianie danych — odpowiednio — przez konsumenta i producenta do
róĪnych elementów ograniczonego bufora. Takie przetwarzanie danych zwiĊksza sto-
pieĔ rzeczywistego, równolegáego wykonywania procesów. Ten stopieĔ równolegáoĞci
wykonywania procesów bĊdzie jednym z podstawowych kryteriów prezentowanych
rozwiązaĔ.
8.1.1. Semafory
Na początku rozwaĪmy najbardziej klasyczny przypadek problemu producenta i kon-
sumenta z reprezentacją n-elementowego bufora. W poniĪszym przykáadzie zastosowano
bufor cykliczny, zatem indeks elementu bufora, do którego producent moĪe wstawiü lub
z którego konsument moĪe pobraü dane, jest obliczany jako modulo rozmiaru bufora.
NaleĪy zauwaĪyü, Īe procesy producenta i konsumenta muszą mieü wáasny wskaĨnik
okreĞlający — odpowiednio — pierwsze wolne miejsce w buforze i miejsce najwczeĞniej
umieszczonych danych4.
with Semafory; use Semafory;
procedure ProducentKonsument is
task Producent;
task Konsument;
n: constant Integer := 10; -- rozmiar bufora
Miejsca, Dane: Sem; -- wartoĞü początkowa semaforów, odpowiednio, równa n i 0
Bufor: array(1..n) of Integer;
task body Producent is
wskP: Integer := 0;
info: Integer := 0;
begin
loop
produkuje_Dane;
Miejsca.wait;
wskP := (wskP mod n) + 1;
4 We wszystkich rozwiązaniach opartych na semaforach są stosowane typy Sem, SemBin oraz Sem_ograniczony
zdefiniowane w pakiecie Semafory opisanym w podrozdziale 6.5.
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
227
Bufor(wskP) := info;
Dane.signal;
end loop;
end Producent;
task body Konsument is
wskK: Integer := 0;
info: Integer := 0;
begin
loop
Dane.wait;
wskK := (wskK mod n) + 1;
info := Bufor(wskK);
Miejsca.signal;
konsumuje_Dane;
end loop;
end Konsument;
begin
Miejsca.init(n); -- ustawienie wartoĞci początkowej semaforów
Dane.init(0);
end ProducentKonsument;
WartoĞü semafora ogólnego Miejsca, o wartoĞci początkowej równej rozmiarowi bufora,
okreĞla liczbĊ wolnych miejsc w buforze, a wartoĞü semafora Dane, o wartoĞci początko-
wej równej 0, okreĞla liczbĊ danych w buforze. Operacja Miejsca.wait (stanowi protokóá
wstĊpny) jest wykonywana przez producenta przed wstawieniem porcji danych do bu-
fora, operacja Dane.signal (stanowi protokóá koĔcowy) jest natomiast wykonywana
przez producenta po umieszczeniu porcji danych i ma na celu powiadomienie konsu-
menta o nowej porcji danych w buforze. Analogicznie operacja Dane.wait jest wykony-
wana przez konsumenta przed pobraniem porcji danych z bufora i jest moĪliwa do wyko-
nania, jeĞli w buforze są jakiekolwiek dane. Operacja Miejsca.signal jest natomiast
wykonywana przez konsumenta po pobraniu danych z bufora i powiadamia producenta
o zwolnieniu miejsca w buforze.
JeĞli wartoĞü semafora Miejsca jest równa 0, to producent umieĞciá kolejno n porcji
danych, bez przeplotu operacji pobierania danych przez konsumenta. W tym stanie bufora,
jeĪeli producent chce umieĞciü kolejną porcjĊ danych, zostaje zawieszony na semaforze
Miejsca do czasu, aĪ proces konsumenta pobierze porcjĊ danych i tym samym zwolni
miejsce w buforze (konsument sygnalizuje to wykonaniem operacji Miejsca.signal).
Z kolei wartoĞü semafora Dane równa 0 oznacza, Īe nie ma porcji danych w buforze i pro-
ces konsumenta, który chce pobraü dane, jest zawieszony na tym semaforze do czasu,
aĪ w buforze pojawi siĊ nowa porcja danych (producent sygnalizuje to wykonaniem
operacji Dane.signal).
NaleĪy jeszcze wykazaü, Īe w tym samym czasie producenci i konsumenci nie bĊdą
odpowiednio wstawiaü i pobieraü danych z tego samego miejsca w buforze. ZauwaĪmy,
Īe po kaĪdym umieszczeniu lub pobraniu porcji danych z bufora (procesy wykonują
swoje sekcje lokalne) suma wartoĞci semafora Miejsca i Dane jest zawsze równa n. KaĪ-
demu opuszczeniu semafora Miejsca (zmniejszenie o 1) przed umieszczeniem porcji
danych towarzyszy podniesienie semafora Dane po umieszczeniu porcji (zwiĊkszenie o 1).
Analogiczna sytuacja ma miejsce, gdy konsument pobiera porcjĊ danych, wykonując
Dane.wait, i sygnalizuje o wolnym miejscu wykonaniem operacji Miejsca.signal.
228
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
Ponadto wartoĞci zmiennych wskP i wskK są równe (tzn. wskaĨniki wskP i wskK wskazują
to samo miejsce w buforze) tylko wtedy, gdy bufor jest pusty lub peány. Oznacza to, Īe
gdy wskP = wskK, to jeden z pary semaforów Miejsca lub Dane ma wartoĞü 0, co jednocze-
Ğnie uniemoĪliwia wykonanie dwóch operacji: pobrania danych przez konsumenta i wsta-
wienia danych przez producenta. W przypadku gdy wartoĞci semaforów Miejsca i Dane są
róĪne od zera, jest zapewnione, Īe jednoczesne pobieranie i umieszczanie porcji danych
dotyczy róĪnych elementów bufora.
Implementacja bufora dla wielu producentów i konsumentów wymaga deklaracji zmien-
nych globalnych wskP i wskK, poniewaĪ te zmienne muszą byü wspóádzielone przez
producentów i konsumentów. Jednak samo przeksztaácenie zmiennych lokalnych wskP i wskK
na zmienne globalne nie gwarantuje poprawnej synchronizacji procesów w dostĊpie do
bufora.
RozwaĪmy stan programu, w którym bufor ma co najmniej dwa miejsca wolne oraz pro-
cesy Producent1 i Producent2 chcą w tym samym czasie umieĞciü w nim porcje danych.
KaĪdy z producentów moĪe wykonaü operacjĊ opuszczania semafora Miejsca.wait,
poniewaĪ wartoĞü semafora Miejsca jest równa co najmniej 2. Wówczas moĪliwy jest
nastĊpujący przeplot operacji (zaáoĪono, Īe wskP = 1, zatem wolny jest drugi i trzeci
element bufora):
Producent1 wykonuje operacjĊ okreĞlenia wolnego miejsca w buforze
— wskP := (wskP mod n) + 1, wiĊc wskP := 2;
Producent2 wykonuje operacjĊ okreĞlenia wolnego miejsca w buforze
wskP := (wskP mod n) + 1, wiĊc wskP := 3;
Producent2 wstawia dane do trzeciego elementu bufora, Bufor(wskP) := info;
Producent1 wstawia dane do trzeciego elementu bufora, Bufor(wskP) := info.
Po wykonaniu powyĪszego przeplotu operacji jeden z konsumentów bĊdzie pobieraü
dane z drugiego, pustego elementu bufora. Ponadto dane wyprodukowane przez pierw-
szego producenta zostaáy nieskonsumowane i nadpisane danymi wygenerowanymi
przez drugiego producenta. W przypadku gdy umieszczane w buforze dane stanowią sto-
sunkowo duĪą strukturĊ, to istnieje duĪe prawdopodobieĔstwo, Īe instrukcje procedury
zapisu danych do bufora wykonywane przez dwóch producentów bĊdą równieĪ przepla-
tane. Oznacza to, Īe czĊĞü danych umieszczona w trzecim elemencie bufora jest wypro-
dukowana przez proces Producent1, a pozostaáa przez proces Producent2. Analogiczna
sytuacja moĪe wystąpiü w przypadku jednoczesnego pobierania danych z bufora przez
dwóch lub wiĊcej konsumentów.
Rozwiązanie tego problemu sprowadza siĊ do zapewnienia — osobno dla producen-
tów i konsumentów — wzajemnego wykluczania w dostĊpie do danego elementu bufora.
W poniĪszym rozwiązaniu zastosowano dwa semafory binarne: jeden dla wzajemnego
wykluczania producentów, drugi dla wzajemnego wykluczania konsumentów5.
5 Przedstawiona implementacja jest kompletna (gotowa do kompilacji), a liczba producentów i konsumentów
jest okreĞlana podczas wykonywania programu (alokacja dynamiczna zadaĔ).
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
229
with ADA.Text_IO; use ADA.Text_IO;
with ADA.Integer_Text_IO; use ADA.Integer_Text_IO;
with Semafory; use Semafory;
procedure ProducentKonsument is
Max:Integer := 50;
LProducentow: Integer := 5; LKonsumentow: Integer := 5;
task type Producent(nr: Integer := 0);
task type Konsument(nr: Integer := 0);
type WskProducent is access Producent;
type WskKonsument is access Konsument;
producenci: array(1..LProducentow) of WskProducent;
konsumenci: array(1..LKonsumentow) of WskKonsument;
SP, SK: SemBin; Miejsca, Dane: Sem;
n: constant Integer := 10;
Bufor: array(1..n) of Integer;
wskP, wskK: Integer := 0;
task body Producent is
info: Integer := 1;
begin
loop
Put( produkuje producent nr : ); Put(nr); New_Line;
Miejsca.wait;
SP.wait;
wskP := (wskP mod n) + 1;
Bufor(wskP) := info;
SP.signal;
Dane.signal;
end loop;
end Producent;
task body Konsument is
info: Integer := 1;
begin
loop
Dane.wait;
SK.wait;
wskK := (wskK mod n) + 1;
info := Bufor(wskK);
SK.signal;
Miejsca.signal;
Put( konsumpcja konsumenta nr : ); Put(nr);
end loop;
end Konsument;
procedure start is
i, j: Integer;
begin
for i in 1..LProducentow loop
producenci(i) := new Producent(i); end loop;
for j in 1..LKonsumentow loop
konsumenci(j) := new Konsument(j); end loop;
end start;
begin
Miejsca.init(n); -- wartoĞü początkowa N
Miejsca.init(0); -- wartoĞü początkowa 0, bo bufor pusty
Start;
end ProducentKonsument;
230
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
8.1.2. Spotkania
Ostatnie rozwiązanie przypomina problem symulacji semafora dwustronnie ograni-
czonego (zob. podrozdziaá 6.5) w oparciu o mechanizm spotkaĔ. Innymi sáowy, pro-
cedury umieszczania porcji danych oraz pobierania porcji danych mogáyby byü prze-
niesione w przestrzeĔ adresową poniĪszego zadania, wykonującego instrukcjĊ select
z dwoma wejĞciami Wstaw i Pobierz. Dozory wejĞü zapewniają, Īe dane nie bĊdą umiesz-
czane w peánym buforze i pobierane z pustego.
n: constant Integer := 10;
task Bufor is
entry Wstaw (X: in Typ);
entry Pobierz(X: out Typ);
end Bufor;
task body Bufor is
Buf: array (1..n) of Typ;
wskP, wskK: Integer := 1;
licznik: Integer := 0;
begin
loop
select
when licznik n =
accept Wstaw (X: in Typ) do
Buf(wskP) := X;
wskP := (wskP mod n) + 1;
licznik := licznik + 1;
end Wstaw;
or
when licznik 0 =
accept Pobierz(X: out Typ) do
X := Buf(wskK);
wskK := (wskK mod n) + 1;
licznik := licznik - 1;
end Pobierz;
end select;
end loop;
end Bufor;
Procesy producenta i konsumenta wstawiają i pobierają dane podczas spotkania z za-
daniem Bufor odpowiednio w wejĞciu Wstaw i Pobierz.
task body Producent is
info: Typ;
begin
loop
Produkuje_dane;
Bufor.Wstaw(info);
end loop;
end Producent;
task body Konsument is
info: Typ;
begin
loop
Bufor.Pobierz(info);
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
231
Konsumuje_dane;
end loop;
end Konsument;
PowyĪsze rozwiązanie ma jedną podstawową wadĊ — w tym samym czasie zadanie
Bufor moĪe realizowaü spotkanie tylko z jednym z zadaĔ, co w konsekwencji unie-
moĪliwia jednoczesny dostĊp producenta i konsumenta do róĪnych elementów bufora.
Z tego powodu w tym rozwiązaniu uzyskano mniejszy stopieĔ równolegáego wyko-
nania procesów w porównaniu z rozwiązaniem opartym na semaforach ogólnych i bi-
narnych. Rozwiązanie oparte na semaforach zyskuje na znaczeniu wtedy, gdy dotyczy
sytuacji, w której zadania przetwarzają duĪe porcje danych, tzn. czas wzglĊdny wsta-
wiania i pobierania porcji danych w stosunku do czasu realizacji operacji semaforo-
wych jest znacznie wiĊkszy.
8.1.3. Monitory
Sekwencyjne wykonanie operacji pobierania i umieszczania danych w buforze ma takĪe
miejsce wtedy, gdy wsparciem dla implementacji jest mechanizm monitora i obiektu
chronionego. Zastosowanie mechanizmu monitora w implementacji n-elementowego
bufora zilustrowano w poniĪszym kodzie6:
monitor Bufor is
procedure Wstaw(X: in Typ);
procedure Pobierz(X: out Typ);
n: constant Integer := 10;
bufor: array(0..n - l) of Typ;
ile: Integer := 0; WskP, WskK: Integer := 0;
Miejsca, Dane: Warunek;
end Bufor;
monitor body Bufor is
procedure Wstaw(X: in Typ) is
begin
if ile = n then wait(Miejsca); end if;
WskP := (WskP + 1) mod n;
bufor(WskP) := X;
ile := ile + 1;
if not empty(Dane) then signal(Dane); end if;
end Wstaw;
procedure Pobierz(X: out Typ) is
begin
if ile = 0 then wait(Dane); end if;
WskK := (WskK + 1) mod n;
X := bufor(WskK);
ile := ile - 1;
if not empty(Miejsca) then signal(Miejsca); end if;
end Pobierz;
end Bufor;
6 Operacje na zmiennych warunkowych wait(...), signal(...), empty(...) zostaáy opisane w punkcie 7.2.1
„Zmienne warunkowe”. Uproszczoną symulacjĊ dziaáania mechanizmu monitora w Adzie wraz
z implementacją powyĪszych operacji zawiera dodatek A.
232
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
Producenci i konsumenci, którzy chcą — odpowiednio — umieĞciü lub pobraü porcje
danych z bufora, wywoáują procedury monitora Bufor.Wstaw(...) i Bufor.Pobierz(...).
Zmienne warunkowe Miejsca i Dane pozwalają na wywáaszczenie z monitora produ-
centów (operacja wait(Miejsca)), jeĪeli bufor jest peány, oraz konsumentów (operacja
wait(Porcje)), jeĪeli bufor jest pusty. Producenci są zawieszeni w kolejce zmiennej
warunkowej Miejsca, konsumenci natomiast w kolejce zmiennej warunkowej Dane.
Ostatnie instrukcje procedur Wstaw i Pobierz wznawiają potencjalnie zawieszone pro-
cesy w kolejkach zmiennych warunkowych, wykonując operacje — odpowiednio —
signal(Dane), która wznawia jednego z konsumentów, i signal(Miejsca), która wzna-
wia jednego z producentów. Funkcja empty(Miejsca) zapewnia, Īe operacja wznawia-
nia producentów zawieszonych w kolejce zmiennej jest wykonywana tylko wówczas,
gdy ta kolejka nie jest pusta. Analogiczne znaczenie ma funkcja empty(Dane) w stosunku
do konsumentów.
8.1.4. Obiekty chronione
Rozwiązanie problemu producenta i konsumenta oparte na mechanizmie obiektu chro-
nionego jest nastĊpujące:
type Elementy is array(Integer range ) of Element;
n: constant Integer := 10;
protected type Bufor(n: Integer) is
entry Pobierz(E: out Element);
entry Wstaw(E: in Element);
private
IndexWej, IndexWyj: Integer := 0;
Ile: Integer := 0; -- liczba porcji danych w buforze
Buf: Elementy(1..n);
end Bufor;
protected body Bufor is
entry Pobierz(E: out Element) when Ile 0 is
begin
IndexWyj := (IndexWyj mod n) + 1;
E := Buf(IndexWyj);
Ile := Ile - 1;
end Pobierz;
entry Wstaw(E: in Element) when Ile n is
begin
Buf(IndexWej) := E;
IndexWej := (IndexWej mod n) + 1;
Ile := Ile + 1;
end Wstaw;
end Bufor;
procedure producenciKonsumenci is
B1: Bufor(5);
task type Producent;
task body Producent is
X:Element := 1;
begin
loop
-- produkuje
B1.Wstaw(X);
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
233
end loop;
end Producent;
task type Konsument;
task body Konsument is
X: Element;
begin
loop
B1.Pobierz(X);
-- konsumuje
end loop;
end Konsument;
end producenciKonsumenci;
W powyĪszym rozwiązaniu bariery zdefiniowane dla wejĞü Wstaw i Pobierz gwarantują
speánienie zaáoĪeĔ dotyczących wspóápracy producentów i konsumentów. Na tym etapie
wiedzy Czytelnika, szczególnie po uwzglĊdnieniu tematyki rozdziaáu 6. i 7., przykáad
ten jest na tyle prosty, Īe pominiemy jego szczegóáowy opis.
Zaletą mechanizmu monitora i obiektu chronionego jest moĪliwoĞü enkapsulacji i w re-
zultacie hermetyzacji zmiennych wspóádzielonych (bufor) i metod operujących na
tych zmiennych. OczywiĞcie hermetyzacja przynosi te same korzyĞci co w przypadku
programowania obiektowego. ZwiĊksza elastycznoĞü (adaptowalnoĞü) zaimplementowa-
nych programów, tzn. obiekt czy monitor moĪe byü bezpoĞrednio wykorzystany w wielu
aplikacjach, poniewaĪ zmiana implementacji monitora (lub obiektu chronionego), przy za-
chowaniu nazw metod skáadowych (interfejsu), nie wpáywa na modyfikacje kodu w apli-
kacjach, w których obiekt chroniony lub monitor zostaá juĪ wczeĞniej zastosowany.
Porównując implementacjĊ w oparciu o mechanizm monitora i obiektu chronionego,
widaü przewagĊ obiektu chronionego. Obliczanie barier dla wejĞü obiektu chronionego
odbywa siĊ przed ich wywoáaniem i w niektórych zastosowaniach jest efektywniejszym
rozwiązaniem w porównaniu ze zmiennymi warunkowymi monitora. W celu ilustracji
rozwaĪmy stan systemu, w którym bufor jest peány i jeden z producentów wywoáuje
wejĞcie lub procedurĊ — odpowiednio — obiektu chronionego i monitora7. W przypadku
obiektu chronionego zostanie wykonana jedna operacja sprawdzenia warunku bariery
i proces producenta zostanie zawieszony w kolejce do wejĞcia Wstaw. W przypadku
mechanizmu monitora natomiast producent wejdzie do monitora, wykonując procedurĊ
Wstaw (blokuje przy tym dostĊp innym procesom do metod skáadowych monitora), na-
stĊpnie sprawdzi stan bufora, wykona operacjĊ wait(Miejsca), co spowoduje jego wy-
wáaszczenie z metody monitora, i zostanie zawieszony w kolejce warunku Miejsca.
8.1.5. Podsumowanie
Gáównym celem niniejszego podrozdziaáu byáo pokazanie moĪliwoĞci rozwiązaĔ tego
samego problemu w oparciu o róĪne mechanizmy synchronizacji, a dokáadniej rzecz
ujmując, chodziáo o ilustracjĊ efektywnoĞci implementacji tego samego algorytmu w oparciu
7 Nie moĪna tych wniosków uogólniaü do kaĪdego problemu programowania wspóábieĪnego. Ilustrowaáy
to przykáady rozwiązaĔ problemu alokacji zasobów w podrozdziale 7.4. RównieĪ kolejne przykáady
problemów wspóábieĪnych pokaĪą, Īe to uogólnienie nie jest uzasadnione.
234
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
o róĪne mechanizmy synchronizacji zadaĔ. Do oceny efektywnoĞci proponowanych
rozwiązaĔ (i w konsekwencji wyboru odpowiedniego mechanizmu synchronizacji)
przyjĊto trzy kryteria:
stopieĔ zrównoleglenia wykonania procesów (w przypadku Ğrodowiska
wieloprocesorowego rzeczywistego zrównoleglenia);
zdolnoĞü adaptacji przyjĊtego rozwiązania w innych programach, czyli elastycznoĞü
implementacji rozumianą jako áatwoĞü dokonania zmian oraz ich weryfikacji
w kontekĞcie poprawnoĞci programów (np. liczba skutków ubocznych
modyfikacji kodu);
liczbĊ wykonywanych operacji związanych z protokoáami synchronizacji
procesów.
KaĪde z prezentowanych rozwiązaĔ ma swoje wady i zalety. Zostaáy one opisane
i wyjaĞnione przy prezentacji kaĪdego z nich. PoniĪsze podsumowanie pokazuje, Īe
nie ma rozwiązania bez pewnych wad. NaleĪy podkreĞliü, Īe wady i zalety danej im-
plementacji nie wynikaáy z przyjĊtego algorytmu synchronizacji procesów (w kaĪdym
przypadku byá stosowany ten sam algorytm), lecz z cech poszczególnych mechanizmów
synchronizacji.
Podsumowując, na podstawie prezentowanych rozwiązaĔ problemu producenta i kon-
sumenta moĪna sformuáowaü dwa podstawowe wnioski:
1. Mechanizm semafora — najwiĊkszy stopieĔ zrównoleglenia wykonywania
procesów, poniewaĪ w tym samym czasie producent i konsument moĪe pobieraü
porcje z bufora. W przypadku spotkaĔ, monitora i obiektu chronionego operacje
pobierania i wstawiania wykluczają siĊ wzajemnie.
2. Obiekty chronione i monitory — áatwa adaptacja implementacji bufora w innych
programach oraz elastycznoĞü wynikająca z moĪliwoĞci enkapsulacji metod
i danych w jednej strukturze. Konsekwencje dotyczące wydajnoĞci metod
testowania i weryfikacji programu dla strukturalnych mechanizmów są znane
i wystĊpują nie tylko w programach wspóábieĪnych (por. programowanie
obiektowe).
Na zakoĔczenie przedstawiono jeszcze jeden przykáad rozwiązania problemu produ-
centa i konsumenta w oparciu o mechanizm semafora. Celem tego rozwiązania jest
zwiĊkszenie stopnia równolegáego wykonania procesów. Ponadto ten przykáad uĞwiadomi
Czytelnikowi, Īe rozwiązania uzyskujące wiĊkszy stopieĔ zrównoleglenia wykony-
wania determinują znaczny wzrost moĪliwych przeplotów operacji atomowych, które
z kolei komplikują proces weryfikacji poprawnoĞci programów wspóábieĪnych.
Poprzednie rozwiązanie umoĪliwiaáo zadaniom producenta i konsumenta — odpowied-
nio — wstawianie i pobieranie danych z bufora w tym samym czasie. ZaáoĪeniem po-
niĪszego rozwiązania jest umoĪliwienie jednoczesnego wstawiania porcji danych do
róĪnych elementów bufora przez wielu producentów i analogicznie pobierania porcji
danych z róĪnych elementów przez konsumentów.
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
235
-- definicje bufora, semaforów ogólnych i binarnych
-- oraz ich początkowa inicjalizacja jak w poprzednich przykáadach
task body Producent is
wsklok: Integer := 0;
info: Typ;
begin
loop
Produkuje;
Miejsca.wait;
SP.wait;
wskP := (wskP mod n) + 1;
wsklok := wskP;
SP.signal;
-- semafor nie wyklucza jednoczesnego wstawiania danych do róĪnych elementów bufora
Bufor(wsklok) := info;
Dane.signal;
end loop;
end Producent;
task body Konsument is
wsklok: Integer := 0;
info: Typ;
begin
loop
Dane.wait;
SK.wait;
wskK := (wskK mod n) + 1;
wsklok := wskK;
SP.signal;
-- semafor nie obejmuje operacji pobierania porcji
Info := Bufor(wskK);
Miejsca.signal;
Konsumuje;
end loop;
end Konsument;
DuĪą rolĊ w tym rozwiązaniu peánią zmienne lokalne. Gwarantują one zapamiĊtanie
przez kaĪdego z producentów indeksu wolnego miejsca w buforze oraz przez konsu-
menta indeksu miejsca, w którym są zapisane dane. RozwaĪmy stan programu, w którym
dwóch producentów Producent1 i Producent2 próbuje jednoczeĞnie umieszczaü porcje
danych w buforze. ZaáóĪmy, Īe drugi i trzeci element bufora jest wolny, stąd w rozwaĪa-
nym stanie wskP = 1, tzn. wskazuje na pierwszy element bufora.
Przeplot operacji wykonywanych przez zadania Producent1 i Producent2 moĪe byü
nastĊpujący:
zadanie Producent1 przypisuje wskP = 2 oraz zapamiĊtuje wartoĞü wskP w zmiennej
lokalnej wsklok = wskP (semafor gwarantuje niepodzielnoĞü tych dwóch operacji);
zadanie Producent1 rozpoczyna operacjĊ zapisywania danych do bufora
— Bufor(2);
zadanie Producent2 przypisuje wskP = 3 oraz zapamiĊtuje wartoĞü zmiennej
wskP w zmiennej lokalnej wsklok = wskP;
236
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
zadanie Producent2 rozpoczyna operacjĊ zapisywania danych do bufora
— Bufor(2).
àatwo zauwaĪyü, Īe implementacja oparta jedynie na jednej zmiennej globalnej wskP
naruszaáaby wáasnoĞü wzajemnego wykluczania w dostĊpie do poszczególnych elemen-
tów bufora. Analogiczny przeplot operacji ma miejsce w przypadku jednoczesnego
pobierania porcji danych przez dwóch konsumentów. Zmienne lokalne pozwalają za-
pamiĊtaü indeks elementu bufora, do którego dane zadanie wstawia lub z którego po-
biera dane. OczywiĞcie zysk wynikający z równolegáoĞci operacji wstawiania i pobiera-
nia danych z bufora jest tym wiĊkszy, im wiĊksza jest róĪnica pomiĊdzy czasem zapisu
danych a czasem wykonania operacji przypisania wsklok = wskP.
Jednak poniĪsze rozwiązanie jest prawidáowe w szczególnych przypadkach. Przeana-
lizujmy poprawnoĞü wykonania powyĪszego programu w heterogenicznym, wieloproce-
sorowym systemie záoĪonym z procesorów o róĪnych prĊdkoĞciach. W takim systemie
prĊdkoĞü wykonywania operacji przez procesy jest zaleĪna od tego, który procesor
zostaá przydzielony do ich wykonania.
RozwaĪmy stan, w którym bufor jest pusty i jeden z konsumentów jest zawieszony na
operacji opuszczania semafora Dane. Dwóch producentów Producent1 i Producent2
realizuje powyĪej opisany przeplot operacji i jednoczeĞnie umieszcza porcje — od-
powiednio — w pierwszym i drugim elemencie bufora. ZauwaĪmy, Īe w przypadku gdy
proces Producent2 szybciej zapisuje dane do bufora (w wyniku przydziaáu szybszego
procesora) niĪ proces Producent1, to Producent2 moĪe podnieĞü semafor Dane umoĪli-
wiający dostĊp konsumenta do bufora. Jednak w wyniku takiego przeplotu operacji kon-
sument bĊdzie pobieraá dane z elementu bufora, w którym są jeszcze zapisywane dane przez
proces Producent1.
Dodatkowym zabezpieczeniem w powyĪszym rozwiązaniu mogą byü dynamicznie
zmieniające siĊ priorytety zadaĔ w zaleĪnoĞci od operacji wykonywanej przez okreĞlone
zadanie — np. to, które wczeĞniej zaczĊáo wykonywaü operacje protokoáu wstĊpnego
(czyli wczeĞniej przypisze zmiennej lokalnej numer wolnego miejsca), ma wyĪszy
priorytet. Jednak to projektujący aplikacje musi okreĞliü, czy zastosowanie dodatkowego
algorytmu nadawania priorytetu poszczególnym procesom jest uzasadnione w porów-
naniu z zyskiem związanym ze zwiĊkszeniem stopnia zrównoleglenia operacji.
8.2. Problem piöciu filozofów
Problem ucztujących filozofów naleĪy do klasycznych problemów programowania
wspóábieĪnego. Zostaá on omówiony w podrozdziale 3.3 „ĩywotnoĞü globalna” w kon-
tekĞcie wspóázawodnictwa procesów, które moĪe prowadziü do stanu braku ĪywotnoĞci
globalnej programu. Jednak do tej pory nie przedstawiono poprawnej implementacji
tego problemu, co stanowi gáówny cel tego podrozdziaáu. O ile w poprzednim podroz-
dziale skupiono siĊ na uzyskaniu efektywnej implementacji tego samego algorytmu
synchronizacji procesów, stosując róĪne mechanizmy synchronizacji, o tyle celem ni-
niejszego jest ocena mechanizmu synchronizacji w kontekĞcie przyjĊtego algorytmu
rozwiązania tego samego problemu wspóábieĪnego.
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
237
KaĪdy z filozofów wykonuje naprzemiennie dwie operacje — myĞlenie i jedzenie.
Struktura procesu filozofa jest nastĊpująca:
task Filozof;
task body Filozof is
begin
loop
Filozof_myħli;
Protokóđ_wstúpny;
Filozof_je;
Protokóđ_koēcowy;
end loop;
end Filozof;
Przed kaĪdym z piĊciu filozofów stoi talerz oraz leĪą dwa widelce. Filozof potrzebuje
dwóch widelców (dwóch zasobów), aby móc rozpocząü operacjĊ „jedzenie”, która stanowi
sekcjĊ krytyczną. Problem polega na zsynchronizowaniu dostĊpu filozofów do widelców
(kaĪdy widelec jest wspóádzielony przez dwóch filozofów siedzących obok siebie)
gwarantującego ĪywotnoĞü lokalną i globalną programu.
Wspóádzielenie widelców przez sąsiadujących filozofów wymusza wzajemne wyklucza-
nie w ich uĪytkowaniu. Naturalnym mechanizmem gwarantującym wzajemne wyklucza-
nie jest semafor binarny, dlatego w pierwszym rozwiązaniu problemu dostĊp do kaĪdego
widelca bĊdzie synchronizowany przez semafor binarny. KaĪdy filozof, aby rozpocząü je-
dzenie, musi wykonaü operacjĊ opuszczania dwóch semaforów binarnych. Przy wyjĞciu
z sekcji krytycznej filozof oddaje widelce, realizując operacjĊ signal — kolejno dla
widelca z prawej, a nastĊpnie z lewej strony.
Widelce: array(1..5) of SemBin;
task type Filozof(Nr: Integer);
task body Filozof is
begin
loop
Filozof_myħli;
Widelce(Nr).wait;
Widelce((Nr mod 5) + 1).wait;
Filozof_je;
Widelce(nr).signal;
Widelce((Nr mod 5) + 1).signal;
end loop;
end Filozof;
àatwo zauwaĪyü, Īe rozwiązanie umoĪliwiające filozofom kompletowanie widelców
przez ich sekwencyjne pobieranie moĪe doprowadziü do blokady w przypadku, gdy
kaĪdy z filozofów podniesie lewy widelec i blokując dostĊp do niego, oczekuje na prawy
widelec. Problem blokady procesów filozofów zostaá szczegóáowo przedstawiony w pod-
rozdziale 3.3. Omówiono metody unikania blokady i zapobiegania blokadzie oparte na
negacji jednego z czterech warunków koniecznych wystąpienia blokady: wzajemnego
wykluczania, wywáaszczania procesów z zasobów dzielonych, czĊĞciowego przydziaáu
zasobów oraz cyklicznego oczekiwania procesów.
Z wymagaĔ zaáoĪonych na wspóápracĊ procesów w problemie piĊciu filozofów wynika,
Īe nie moĪna zwiĊkszyü liczby dostĊpnych zasobów, dlatego negacja warunku wza-
jemnego wykluczania nie bĊdzie podstawą poniĪszych implementacji. Negacja warunku
238
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
wywáaszczania procesów wymaga dodatkowego procesu, który identyfikowaáby wy-
stąpienie blokady i czasowo wywáaszczaá jeden z procesów (filozofów) z zasobu dzielo-
nego (oddanie widelca przez filozofa). To podejĞcie bazuje na nieefektywnych metodach
wykrywania i likwidacji blokad i takĪe zostanie pominiĊte.
Prezentowane w tym podrozdziale rozwiązania zapobiegają wystąpieniu stanu blokady
w wyniku negacji jednego z dwóch warunków: warunku czĊĞciowego przydziaáu za-
sobów — w czasie oczekiwania na zajĊty zasób proces nie zwalnia zasobu przydzielonego
w poprzedniej operacji, oraz warunku czekania cyklicznego — istnieje zamkniĊty áaĔcuch
procesów, z których kaĪdy oczekuje na zasoby przetrzymywane przez poprzednika.
W problemie piĊciu filozofów potencjalne speánienie warunku czĊĞciowego przydziaáu
wynika z nastĊpującego zaáoĪenia: filozof przetrzymuje widelec w oczekiwaniu na kolejny
widelec. Potencjalne speánienie warunku cyklicznego oczekiwania wynika natomiast
ze struktury, jaką tworzą procesy filozofa i widelce, poniewaĪ pierwszy widelec jest wy-
korzystywany przez pierwszego i piątego filozofa.
Negacja jednego z dwóch warunków wystąpienia blokady jest osiągana dziĊki konstrukcji
co najmniej dwóch róĪnych algorytmów synchronizacji procesów. PoniĪej przedsta-
wiono implementacjĊ tych algorytmów w oparciu o mechanizm semafora, monitora,
obiektu chronionego oraz mechanizm spotkaĔ.
8.2.1. Semafory
W pierwszym rozwiązaniu wyróĪniono dwa rodzaje procesów filozofa. Filozofowie
z numerami nieparzystymi bĊdą kolejno podnosiü prawy, a nastĊpnie lewy widelec,
a filozofowie o numerach parzystych podnoszą widelce w odwrotnej kolejnoĞci. Takie
postĊpowanie filozofów gwarantuje, Īe nie bĊdzie speániony warunek cyklicznego czekania,
poniewaĪ nie moĪe powstaü zamkniĊty áaĔcuch ĪądaĔ zasobowych (ĪądaĔ dostĊpu do
widelców) procesów (punkt 3.3.4).
Widelce: array(1..5) of SemBin;
task type FilozofN(Nr: Integer);
task type FilozofP(Nr: Integer);
task body FilozofP is -- dotyczy filozofów o nr 2 i 4
begin
loop
Filozof_myħli;
Widelce((Nr mod 5) + 1).wait;
Widelce(Nr).wait;
Filozof_je;
Widelce(nr).signal;
Widelce((Nr mod 5) + 1).signal;
end loop;
end FilozofP;
task body FilozofN is -- dotyczy filozofów o nr 1, 3 i 5
begin
loop
Filozof_myħli;
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
239
Widelce(Nr).wait;
Widelce((Nr mod 5) + 1).wait;
Filozof_je;
Widelce((Nr mod 5) + 1).signal;
Widelce(nr).signal;
end loop;
end FilozofN;
W tym rozwiązaniu są speánione wáasnoĞci ĪywotnoĞci lokalnej i globalnej. RozwaĪmy
najbardziej niebezpieczny stan, w którym kaĪdy z procesów w tym samym czasie chce
podnieĞü swój pierwszy widelec: FilozofN1 podnosi prawy widelec o numerze 1, FilozofP2
podnosi lewy widelec o numerze 3, FilozofN3 nie moĪe podnieĞü prawego widelca
o numerze 3; FilozofP4 podnosi swój lewy widelec o numerze 5, FilozofN5 nie moĪe
podnieĞü zajĊtego lewego widelca. Widelce o numerach 2 i 4 są wolne i FilozofN1 oraz
FilozofP4 mogą podnieĞü widelce i rozpocząü jedzenie. àatwo pokazaü, Īe jakikolwiek
przeplot operacji podnoszenia widelców w powyĪszym programie pozostawia dwa
wolne widelce, co gwarantuje zarówno brak blokady, jak i zagáodzenia procesów.
NajczĊĞciej prezentowane w literaturze symetryczne (ze wzglĊdu na jednakową strukturĊ
procesów filozofa) rozwiązanie, gdzie kaĪdy proces filozofa podnosi prawy, a nastĊpnie
lewy widelec, polega na ograniczeniu do czterech liczby filozofów jednoczeĞnie wspóá-
zawodniczących o dostĊp do widelców. To ograniczenie uzyskano poprzez definicjĊ
semafora ogólnego Jadalnia o wartoĞci początkowej równej 4. Nawet w szczególnym
przypadku jednoczesnego wspóázawodnictwa czterech filozofów jeden z nich bĊdzie
miaá moĪliwoĞü podniesienia dwóch widelców i wykonania sekcji krytycznej „jedzenie”.
procedure Filozofow5 is
task type Filozof(Nr: Integer := 0);
type wskF is access Filozof;
Filozofowie: array(1..5) of wskF;
Widelce: array(1..5) of SemBin;
Jadalnia: Sem; -- wartoĞü początkowa semafora 4
task body Filozof is
begin
loop
Filozof_myħli;
Jadalnia.wait;
Widelce(Nr).wait;
Widelce((Nr mod 5) + 1).wait;
Filozof_je;
Widelce(nr).signal;
Widelce((Nr mod 5) + 1).signal;
Jadalnia.signal;
end loop;
end Filozof;
begin
Jadalnia.init(4);
for i in 1..5 loop Filozofowie(i) := new Filozof(i);
end loop;
end Filozofow5;
240
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
8.2.2. Monitory
Kolejne rozwiązanie jest oparte na mechanizmie monitora. WáasnoĞü mechanizmu mo-
nitora pozwala w naturalny sposób zanegowaü warunek czĊĞciowego przydziaáu. Filozo-
fowie podnoszą widelce tylko w przypadku, gdy oba są wolne.
monitor Jadalnia;
Wolne: array(0..4) of Integer range 0..2 := (others = 2);
jedzenie: array(0..4) of Warunek;
procedure BioreWidelce(I: Integer) is
begin
if Wolne(I) 2 then wait(jedzenie(i));
end if;
Wolne((I + 4) mod 5) := Wolne((I + 4) mod 5) - 1;
Wolne((I + 1) mod 5) := Wolne((I + 1) mod 5) - 1;
end BioreWidelce;
procedure OddajeWidelce(I: Integer) is
begin
Wolne((I + 4) mod 5) := Wolne((I + 4) mod 5) + 1;
Wolne((I + 1) mod 5) := Wolne((I + 1) mod 5) + 1;
if Wolne((I + 1) mod 5) = 2 then
if not empty(Signal(jedzenie((I + 1) mod 5)))
then Signal(jedzenie((I + 1) mod 5)); end if;
end if;
if Wolne((I + 4) mod 5) = 2 then
if not empty(Signal(jedzenie((I + 4) mod 5)))
Signal(jedzenie((I + 4) mod 5)); end if;
end if;
end OddajeWidelce;
end Jadalnia;
task type Filozof(Nr: Integer);
task body Filozof is
begin
loop
Filozof_myħli;
BioreWidelece(Nr);
Filozof_myħli;
OddajeWidelce(Nr);
end loop;
end Filozof;
I-ty element tablicy Wolne okreĞla liczbĊ dostĊpnych widelców dla i-tego filozofa. Dodat-
kowo zdefiniowano tablicĊ jedzenie typu Warunek, która stanowi deklaracjĊ piĊciu
zmiennych warunkowych. Zmienne warunkowe umoĪliwiają zawieszenie procesów
filozofa w oczekiwaniu na wolne widelce. Wykonanie powyĪszego programu jest nastĊ-
pujące: i-ty filozof wywoáuje procedurĊ monitora BioreWidelce i sprawdza w niej stan
i-tego elementu tablicy Wolne. JeĪeli nie są dostĊpne dwa widelce (Wolne(i) 2), to wy-
konuje operacjĊ wait(jedzenie(i)) i zostaje zawieszony w kolejce warunku jedzenie(i),
a jednoczeĞnie odblokowuje dostĊp do monitora dla innych procesów. Sąsiadujący filozof,
który odáoĪy drugi z brakujących widelców, wykonuje operacjĊ signal(jedzenie(i))
i wznawia wykonanie procesu zawieszonego w kolejce do zmiennej warunkowej
jedzenie(i). Krytyczna dla poprawnoĞci i efektywnoĞci powyĪszego rozwiązania jest
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
241
wáasnoĞü mechanizmu monitora, która gwarantuje, Īe procesy zawieszone w kolejkach
zmiennych warunkowych są wznawiane w pierwszej kolejnoĞci w stosunku do procesów
oczekujących w kolejce wejĞciowej monitora (punkt 7.2.1).
Efektywne rozwiązanie oparte na semaforach — negujące warunek czĊĞciowego
przydziaáu — jest trudne do realizacji, poniewaĪ zadanie nie moĪe wycofaü siĊ z operacji
opuszczania semafora. MoĪe jedynie wielokrotnie testowaü wartoĞci elementów tablicy
Wolne.
Wolne: array(0..4) of Integer range 0..2 := (others = 2);
s: SemBin;
procedure BioreWidelce(I: Integer) is
begin
loop
s.wait; -- wielokrotnie ta operacja moĪe mieü efekt pusty
if Wolne(I) 2 then
s.signal;
else begin
Wolne((I + 4) mod 5) := Wolne((I + 4) mod 5) - 1;
Wolne((I + 1) mod 5) := Wolne((I + 1) mod 5) - 1;
s.signal;
end;
end if;
end loop;
end BioreWidelce;
Filozof wywoáuje procedurĊ BioreWidelce, w sekcji krytycznej tej procedury sprawdza
stan widelców i w przypadku, gdy co najmniej jeden z widelców jest zajĊty, opuszcza
sekcjĊ krytyczną (podnosi semafor s), co umoĪliwia innym zadaniom sprawdzenie
dostĊpnoĞci widelców. Maáa efektywnoĞü tego rozwiązania jest związana z aktywnym
oczekiwaniem zadaĔ na dostĊp do widelców, co sprowadza siĊ do wielokrotnego wy-
konywania operacji opuszczania i podnoszenia semafora binarnego s w przypadku, gdy
widelce są zajĊte. àatwo zauwaĪyü, Īe to rozwiązanie dopuszcza moĪliwoĞü zagáodzenia
jednego z filozofów, nawet wtedy, gdy semafor s ma zaimplementowaną kolejkĊ typu
FIFO dla zadaĔ oczekujących na operacjĊ opuszczania semafora.
Lepszym rozwiązaniem jest implementacja podobna do symulacji dziaáania monitora za
pomocą semaforów. Jednak w tym przypadku liczba semaforów oraz liczba dodatko-
wych zmiennych (okreĞlających to, ilu filozofów oczekuje na moĪliwoĞü podniesienia
dwóch widelców) jest zaleĪna od liczby filozofów. Dla klasycznego przypadku piĊciu
filozofów potrzebujemy: piĊciu semaforów dla kaĪdego widelca, piĊciu zmiennych
okreĞlających liczbĊ zawieszonych zadaĔ na kaĪdym z semaforów i dodatkowo semafor
binarny gwarantujący wzajemne wykluczanie w dostĊpie do tablicy Wolne. W tym po-
dejĞciu procedura BioreWidelce moĪe byü zapisana w nastĊpujący sposób:
Wolne: array(0..4) of Integer range 0..2 := (others = 2);
jedzenie: array(0..4) of SemBin;
-- dla zdefiniowanego pakietu w podrozdziale 6.5 inicjalizacja powinna byü
-- w programie gáównym := (others = 0)
licznik: array(0..4) of Integer := (others = 0);
s: SemBin;
-- semafor binarny dla ochrony dostĊpu do tablicy Wolne
procedure BioreWidelce(I: Integer) is
242
Programowanie wspóäbieĔne. Systemy czasu rzeczywistego
begin
loop
s.wait;
if Wolne(I) 2 then czekaj(I); end if;
Wolne((I + 4) mod 5) := Wolne((I + 4) mod 5) - l;
Wolne((I + 1) mod 5) := Wolne((I + 1) mod 5) - l;
s.signal;
end loop;
end BioreWidelce;
........
-- analogiczna procedura OddajeWidelce
procedure Czekaj(I: Integer) is
begin
licznik(I) := licznik(I) + 1;
s.signal;
jedzenie(I).wait;
licznik(I) := licznik(I) - 1;
end Czekaj;
procedure Sygnalizuj(I: Integer) is
begin
if licznik(I) 0 then
jedzenie(I).signal;
else
s.signal;
end if;
end Sygnalizuj;
Semafor s zapewnia wzajemne wykluczanie w dostĊpie do tablicy Wolne. Na początku
procedury BioreWidelce i-ty filozof, opuszczając semafor s, blokuje moĪliwoĞü
sprawdzenia przez pozostaáe zadania dostĊpnoĞci widelców (analogicznie jak w mo-
nitorze). JeĪeli widelce nie są dostĊpne, wywoáuje procedurĊ Czekaj(I), w której jest za-
wieszany na operacji opuszczania semafora jedzenie(I). Z kolei j-ty filozof, odkáadając
swoje widelce, sprawdza dostĊpnoĞü widelców swoich sąsiadów i ewentualnie podnosi
semafory jedzenie((J + 1) mod 5) i/lub jedzenie((J - 1) mod 5) — w przypadku
gdy są dostĊpne oba widelce oraz gdy są na tych semaforach zawieszone zadania filo-
zofów. LiczbĊ zawieszonych zadaĔ na semaforze jedzenie(I) okreĞla zmienna licz-
nik(I). àatwo zauwaĪyü, Īe operacja Czekaj(I) i Sygnalizuj(I) są podobne do operacji
wznawiania signal i wstrzymywania wait zadaĔ zawieszonych w kolejkach zmien-
nych warunkowych.
To doĞü skomplikowane rozwiązanie jest efektywne, poniewaĪ nie ma aktywnego
oczekiwania (poprzez wielokrotne podnoszenie i opuszczanie semafora) na speánienie wa-
runku dostĊpu do dwóch widelców. W porównaniu do rozwiązania opartego na me-
chanizmie monitora, w którym byáa zdefiniowana tylko jedna lokalna tablica warunków
(wewnątrz monitora), w powyĪszym rozwiązaniu musimy zdefiniowaü dwie globalne
tablice liczników dla kaĪdego oczekującego filozofa oraz tablicĊ semaforów.
8.2.3. Obiekty chronione
Rozwiązanie problemu piĊciu filozofów oparte na mechanizmie obiektu chronionego jest
zdecydowanie trudniejsze niĪ w przypadku monitora, w szczególnoĞci gdy rozwiąza-
nie ma zapewniaü negacjĊ warunku czĊĞciowego przydziaáu zasobów oraz hermetyzacjĊ
Rozdziaä 8. i Problemy programowania wspóäbieĔnego
243
w jednym obiekcie chronionym zasobów dzielonych (widelców) oraz zmiennych syn-
chronizujących zadania filozofów. Wynika to stąd, Īe w warunku dozoru danego wej-
Ğcia moĪna jedynie korzystaü ze zmiennych globalnych lub zdefiniowanych wewnątrz
obiektu chronionego. Oznacza to, Īe nie jest moĪliwy nastĊpujący zapis.
type Tablica is array(Integer range ) of Integer;
protected type Jadalnia is
entry BioreWidelce(I: in Integer);
entry OddajeWidelce(I: in Integer);
private
Wolne: Tablica(0..4) := (others = 2);
end Jadalnia;
protected body Jadalnia is
entry BioreWidelce(I: in Integer)
when Wolne(I) = 2 is -- báąd - niedostĊpne w Adzie
-- parametr aktualny wywoáywania wejĞcia nie moĪe byü testowany
Pobierz darmowy fragment (pdf)