Cyfroteka.pl

klikaj i czytaj online

Cyfro
Czytomierz
00340 005072 14830047 na godz. na dobę w sumie
wyszukaj dokładnie | pobierz wtyczkę
Programowanie współbieżne. Systemy czasu rzeczywistego - książka
Programowanie współbieżne. Systemy czasu rzeczywistego - książka
Autor: Liczba stron: 320
Wydawca: Helion Język publikacji: polski
ISBN: 978-83-246-4302-8 Data wydania:
Lektor:
Kategoria: ebooki >> komputery i informatyka >> programowanie >> c++ - programowanie
Porównaj ceny (książka, ebook, audiobook).
Czytaj online.
Komentuj

Współbieżność to szybkość, efektywność i nowoczesność. Czy Ty też chcesz tak programować?

Coraz niższe ceny i powszechna dostępność sprzętu komputerowego o architekturze wieloprocesorowej powodują, że umiejętność projektowania i budowania aplikacji przetwarzających informacje współbieżnie staje się wręcz niezbędna każdemu zawodowemu programiście. W większości współczesnych języków programowania bezpośrednio zaimplementowano metody tworzenia zadań wykonywanych równolegle oraz wysokopoziomowe mechanizmy komunikacji i synchronizacji procesów.

Tworzenie efektywnych aplikacji współbieżnych wciąż jednak wymaga dużej, specjalistycznej wiedzy dotyczącej systemów operacyjnych oraz programowania nisko- i wysokopoziomowego, o czym przekonało się wielu studentów kierunków informatycznych i profesjonalnych programistów. Na szczęście teraz wszyscy mogą sięgnąć po książkę 'Programowanie współbieżne. Systemy czasu rzeczywistego'. Pomoże ona uniknąć wielu typowych błędów związanych z tworzeniem aplikacji współbieżnych i pokaże, jak rozwiązywać problemy specyficzne dla tej dziedziny. Lektura ułatwi też zdobycie praktycznej umiejętności projektowania architektury niezawodnego współbieżnego oprogramowania, a także przybliży wiedzę na temat mechanizmów i metod wykorzystywanych przy tworzeniu systemów równoległych czasu rzeczywistego.

Przyszłość informatyki to przetwarzanie współbieżne. Stać Cię na pozostanie w tyle?


Paweł Majdzik - od 1998 roku pracuje jako adiunkt w Instytucie Sterowania i Systemów Informatycznych Uniwersytetu Zielonogórskiego. Jest autorem bądź współautorem ponad trzydziestu opracowań naukowych - książek, artykułów, referatów wydanych w kraju i za granicą, a dotyczących informatyki, w szczególności związanych z analitycznymi metodami modelowania i projektowania systemów współbieżnych.

Znajdź podobne książki Ostatnio czytane w tej kategorii

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)

Gdzie kupić całą publikację:

Programowanie współbieżne. Systemy czasu rzeczywistego
Autor:
Sklep
Format
Cena
Helion.pl Helion.pl
książka
49,00 zł
Idź do sklepu »

Opinie na temat publikacji:

Inne popularne pozycje z tej kategorii:

Czytaj również:

Prowadzisz stronę lub blog? Wstaw link do fragmentu tej książki i współpracuj z Cyfroteką: