1 Mechanizmy pracy równoległejJarosław Kuchta Mechanizmy pracy równoległej
2 Zagadnienia Algorytmy wzajemnego wykluczania Mechanizmy niskopoziomowealgorytm Dekkera Mechanizmy niskopoziomowe przerwania mechanizmy ochrony pamięci instrukcje specjalne Mechanizmy wysokopoziomowe mechanizmy synchronizacji semafory, monitory mechanizmy komunikacji sygnały, komunikaty, zdarzenia, potoki, gniazda, zdalne wywołania procedur, usługi sieciowe Rodzaje komunikacji i synchronizacji
3 Algorytmy wzajemnego wykluczania
4 Algorytmy wzajemnego wykluczania (1)2 P1 Czyja kolej {1/2} P1 =1? P2 =2? P2 1
5 Kod algorytmu 1 void P1() { do while (czyja_kolej ==2) do ;sekcja_krytyczna_1(); czyja_kolej = 2; sekcja_lokalna_1(); } while (true); } void P2() { do while (czyja_kolej ==1) do ; sekcja_krytyczna_2(); czyja_kolej = 1; sekcja_lokalna_2(); } while (true); }
6 Wady algorytmu 1 Częstotliwość pracy P1 i P2 muszą być równe.Jeśli P1 zawiesi się w swojej sekcji krytycznej (albo poza nią), to P2 nie będzie już mógł działać.
7 Algorytmy wzajemnego wykluczania (2)P2 =N? P1 w sekcji krytycznej {T/N} N T P1 P2 T N P2 w sekcji krytycznej {T/N} =N? P1
8 Kod algorytmu 2 void P1() { do while (c2) do ; c1 = true;sekcja_krytyczna_1(); c1 = false; sekcja_lokalna_1(); } while (true); } void P2() { do while (c1) do ; c2 = true; sekcja_krytyczna_2(); c2 = false; sekcja_lokalna_2(); } while (true); }
9 Wada algorytmu 2 Nie zabezpiecza przed blokadą P1 w sekcji krytycznej?Stan początkowy N P1 sprawdza c2 P2 sprawdza c1 P1 ustawia c1 T P2 ustawia c2 P1 wchodzi do sekcji krytycznej P2 wchodzi do sekcji krytycznej
10 Algorytm 3 – ustawianie c1 i c2 przed oczekiwaniemvoid P1() { do c1 = true; while (c2) do ; sekcja_krytyczna_1(); c1 = false; sekcja_lokalna_1(); } while (true); } void P2() { do c2 = true; while (c1) do ; sekcja_krytyczna_2(); c2 = false; sekcja_lokalna_2(); } while (true); }
11 Wada algorytmu 3 Również nie zabezpiecza przed blokadąP1 w sekcji krytycznej? (c1) P2 w sekcji krytycznej? (c2) Stan początkowy N P1 ustawia c1 T P2 ustawia c2 P1 sprawdza c2 P2 sprawdza c1 …
12 Algorytm 4 – wydłużone oczekiwanievoid P1() { do c1 = true; while (c2) do c1 = false; wait_for_some_time(delay); } sekcja_krytyczna_1(); sekcja_lokalna_1(); } while (true); void P2() { do c2 = true; while (c1) do c2 = false; wait_for_some_time(delay); } sekcja_krytyczna_2(); sekcja_lokalna_2(); } while (true);
13 Wada algorytmu 4 W specyficznej sytuacji nie zabezpiecza przed blokadąP1 w sekcji krytycznej? (c1) P2 w sekcji krytycznej? (c2) Stan początkowy N P1 ustawia c1 T P2 ustawia c2 P1 sprawdza c2 P2 sprawdza c1 P1 kasuje c1 P2 kasuje c2
14 Algorytm Dekkera – połączenie algorytmu 1. i 4.void P1() { do c1 = true; while (c2) do if (czyja_kolej == 2) c1 = false; while (czyja_kolej == 2) do; } sekcja_krytyczna_1(); czyja_kolej = 2; sekcja_lokalna_1(); } while (true); void P2() { do c2 = true; while (c2) do if (czyja_kolej == 1) c2 = false; while (czyja_kolej == 1) do; } sekcja_krytyczna_2(); czyja_kolej = 1; sekcja_lokalna_2(); } while (true);
15 Mechanizmy niskopoziomowe
16 Przerwania wątek podstawowy przerwanie o niższym priorytecieprzerwanie o wyższym priorytecie
17 Przerwania maskowalnewątek podstawowy czas maskowania przerwań obsługa przerwań zgłoszenia przerwań
18 Przerwania niemaskowalnewątek podstawowy czas maskowania przerwań obsługa przerwań zgłoszenia przerwań
19 Przerwania w systemie równoległymWykorzystanie maskowania do ochrony sekcji krytycznej W systemie wieloprocesorowym brak gwarancji ochrony sekcji krytycznej
20 Mechanizmy ochrony pamięciArbitraż dostępu do pamięci Nieznana kolejność dostępu
21 Instrukcje specjalne Na poziomie procesora Na poziomie języka (C#)BTC – Bit Test and Complement BTS – Bit Test and Set BTR – Bit Test and Reset Na poziomie języka (C#) lock(object) { … }
22 Mechanizmy wysokopoziomowe
23 Semafor Zmienna całkowita Wada: podnoszenie opuszczanieprogramowanie niestrukturalne
24 Monitor Nadzoruje dostęp do wspólnego zasobu.Tylko jeden proces ma dostęp w danej chwili.
25 Sygnał Zmienna systemowa do komunikacji między procesami.Proces 1. czeka na sygnał. Proces 2. ustawia sygnał. Ustawienie sygnału powoduje wznowienie procesu 1. i jednoczesne skasowanie sygnału.
26 Komunikat Informacja przekazywana od procesu 1. do procesu 2.Komunikat trafia do kolejki komunikatów procesu 2. Proces 2. co pewien czas sprawdza, czy ma jakieś komunikaty w kolejce. Odbiera komunikat z kolejki i obsługuje go.
27 Zdarzenie Proces 1. definiuje zdarzenie jako procedurę obsługi.Proces 2. wywołuje procedurę obsługi zdarzenia w procesie 1. Procedura obsługi jest wykonywana w wątku procesu 2, ale ma dostęp do danych procesu 1.
28 Potok (pipe) umożliwia wymianę danych między dwoma procesamipotok nienazwany łączy standardowe wyjście jednego procesu ze standardowym wejściem drugiego procesu potok nazwany – plik do którego jeden proces pisze, a drugi proces czyta
29 Gniazdo (socket) dwukierunkowy punkt końcowy połączeniaumożliwia wysyłanie i przyjmowanie danych wykorzystywane przez aplikacje do komunikacji międzyprocesowej przez sieć (Internet)
30 Zdalne wywołanie procedur (RPC)Remote Procedure Call Standard RFC 1057 Protokół: Serwer nasłuchuje na wybranym porcie. Klient nawiązuje łączność z serwerem przez sieć komputerową i wysyła żądanie usługi (dane) Serwer wykonuje usługę i zwraca potwierdzenie lub kod błędu. Protokoły (RPC, CORBA, DCOM, czy XML-RPC) ukrywają mechanizm wywołania usługi. Dla programisty zdalne wywołanie procedury ma taką samą postać jak wywołanie każdej innej lokalnej procedury.
31 Usługa sieciowa (WebService)Niezależna od platformy sprzętowo-programowej i sposobu implementacji. Opisywana przez język opisu usług WSDL (Web Services Description Language) Opublikowana i wyszukiwana w rejestrze usług za pomocą standardowego mechanizmu (UDDI) Wywołana zdalnie przez zdefiniowany interfejs.
32 Rodzaje usług sieciowychSynchroniczne (jak RPC) Asynchroniczne (np. RIA) Po stronie serwera usługa jak zwykła funkcja. Po stronie klienta: zdefiniowanie operacji, określenie danych wejściowych i procedury zwrotnej (callback), asynchroniczne wywołanie – wysłanie żądania wykonania do serwera, asynchroniczne wywołanie procedury zwrotnej przez serwer – potwierdzenie wykonania, przekazanie żądanych danych, stwierdzenie błędu wykonania.
33 Rodzaje komunikacji i synchronizacjiKomunikacja synchroniczna – nadawca wysyła komunikat i czeka na odpowiedź od odbiorcy. wywołanie procedury zdarzenia zdalne wywołanie procedur Komunikacja asynchroniczna – nadawca wysyła komunikat i kontynuuje działanie. Odbiorca odbiera i obsługuje komunikat, po czym wysyła komunikat potwierdzenia. kolejki komunikatów niektóre usługi sieciowe