Zalety semaforów: -Nie wymagają aktywnego czekania - proces, który wykonał operację `Czekaj' na semaforze zostaje uśpiony. Nie sprawdza on w pętli warunku pozwalającego na dalszą pracę. -Implementacja efektywna czasowo - procesy zatrzymane na semaforze (uśpione) , zostają natychmiast wznowione po wykonaniu operacji `Sygnalizuj' na semaforze. - Operacje na semaforze są niepodzielne - dwa procesy nie mogą wykonać operacji na tym samym semaforze w tym samym czasie
Co zrobili różni ludzie: -Dekker - przedstawił rozwiązanie problemu wzajemnego wykluczania dla 2 procesów -Peterson - podał kolejne, prostsze rozwiązanie problemu wzajemnego wykluczania dla 2 procesów oraz dla n procesów, algorytm piekarniany -Lamport - rozwiązanie problemu wzajemnego wykluczania dla n procesów, algorytm piekarniany -Dijkstra - podał jako pierwszy definicję semaforów, problem ucztujących filozófów -Hansen - Definicja monitorów -Hoare - definicja monitorów (przedstawił ją prawie w tym samym czasie co Hansen ale były to dwie niezależne od siebie definicje) -Wirth - współtwórca Modula 2
Udogodnienia programowania współbieżnego: -zadaniowość - język nie zorientowany obiektowo przestawia 'taski' jako niezależny wykonywalny program, analogicznie do ciała nie współbieżnego programu. Język zorientowany obiektowo przedstawia 'taski' jako obiekt, jako interfejs ze zdefiniowanymi funcjami -komunikacyjność -statyczny typ kontroli -zakresy deklaracji - jesli 'taski' przypominają obiekty to powinny być możliwe do zadeklarowania tam gdzie można zadeklarować obiekty -bezpośrednia i pośrednia komunikacja - komunikacja 'tasków' może sie odbywać poprzez elementy pośrednie np. monitory. 'taski 'mogą także komunikować się bezpośrednio ze sobą -synchronizacja i wzajemne wykluczanie -synchroniczna i asynchroniczna komunikacja -kolejka zadań procesów
Języki programowania zawierające monitory procesów: (NIE JAVA!!!!) -Concurent Pascal -Modula 3 -Mesa -Pascal C
-Wzajemne wykluczanie - tylko jeden proces może mieć dostęp do danego zasobu w danej chwili. Żaden proces nie może dostać zasobu gdy inny z niego korzysta. -Wstrzymywanie i oczekiwanie - proces może wstrzymywać alokowane zasoby oczekując na przydzielenie innych potrzebnych mu zasobów. -Brak wywłaszczeń - żadne zasób nie może być odebrany procesowi który go przetrzymuje. Cykliczne czekanie istnieje zamknięty łańcuch procesów w którym każdy proces przechowuje przynajmniej jeden zasób prztrzebny innemu procesowi w łańcuch. Semafor - jest zmienną całkowitą przyjmującą wartości nieujemne. Na semaforze definiujemy dwie funkcje Wait(s) i Signal(s). Operacje te są atomowe. S>=0, S=s0+#sygnały - #oczekiwania, gdzie sygnały - liczba wykonanych Signal(S), Oczekiwania - liczba zakończonych Wait(s). Wady semaforów: -nie jest mechanizmem strukturalnym -jest mechanizmem pierwotnym niskiego poziomu -błędu w użyciu są bardzo trudne do wykrycia
Różne implementacje semaforów: -semafor ze zbiorem oczekującym. Wait(s) zmniejsza semafor lub zatrzymuje proces, Signal(S) powoduje wznowienie jednego z zatrzymanych procesów lub inkrementację semafora - może wystąpić zagłodzenie -Semafor z kolejką oczekujących. Wait(S) zmniejsza semafor lub zatrzymuje proces oraz przerzuca go na koniec kolejki FIFO, Signal(S) powoduje wznowienie jednego z zatrzymanych procesów lub inkrementację semafora - zagłodzenie nie wystąpi -Semafor z aktywnym czekaniem. Wait(S) wykonywane w pętli, operacja if sprawdzająca wartość jest atomowa, Signal(S) inkrementowany zawsze, nie kontroluje który proces wznowić - nieefektywne
Monitor procesów: Moduł synchronizujący wywołania procedur znajdujących się w jego interfejsie. Jego implementacja zapewnia wzajemne wykluczanie wykonań wykonywanych w nim procesów. -Składnia polega na inkapsulacji danych i procedur do operowania na tych danych. -Monitor jest mechanizmem strukturalnym. -Jeden synchronizuje najczęściej dostęp do jednego zasobu. -W monitorze może przybywać jeden proces na raz
|
Opisać 4 próby prowadzące do algorytmu dekkera, dlaczego są niepoprawne -1 próba: w pierwszej próbie procesy korzystają ze wspólnej zmiennej globalnej czyja_kolej. Może dojść do zakleszczenia w razie braku współzawodnictwa. Gdy jeden proces się zatrzyma w sekcji lokalnej to w tedy zmienna globalna czyja_kolej się już nie zmieni. Zakłada, że procesy działają z równą prędkością. -2 próba: w drugiej próbie program nie zapewnia wzajemności wzajemnego wykluczania. Procesy mogą w tej samej chwili badać swoją zmienna K i wejść do sekcji krytycznej. -3 próba: w programie juz po kilku instrukcjach może nastąpić blokada, jeśli będą się one wykonywały na przemian z każdego procesu. Zmienne obu procesów będą miały wartość 0. teraz program będzie jedynie sprawdzał warunki które cały czas pozostaną fałszywe. nastąpi sytuacja w której oba procesy będą chciały wejść do sekcji krytycznych ale żadnemu sie to nie uda -4 próba: istnieje ciąg wykonań instrukcji w którym p1 wchodzi do sekcji krytycznej nieskończenie wiele razy, a p2 pozostaje w nieskończoność w protokole wstępnym. Jeśli instrukcje będą wykonywane naprzemian w nieskończoność dojdzie do pół-blokady.
Różnica między accept poza selectem a accept w select: -Poza select nie pozwala na odmówienie spotkania(nie można ustawić dozoru np. z powodu pełnego buforu), wymusza ścisłe przeplatanie kolejnych instrukcji. Jeśli w kodzie są dwa accept jeden po drugim to najpierw wykonamy pierwszy a potem obligatoryjnie następuje oczekiwanie na wywołanie drugiego accept. -W select można wybrać które wejście będzie wykonane następnie, czyli może być accept PISZ accept PISZ a dopiero potem raz accept CZYTAJ. Ponadto możliwe jest używanie dozorów decydujących o tym czy można wykonać wejście czy nie
Problem zajętej łazienki: Zakładamy, że w hotelu jest jedna łazienka i wielu mieszkańców w pokojach. Niestety na korytarzu jest zimno i ludzie nie mogą stać przy wejściu do łazienki w kolejce. Muszą co jakiś czas wychodzić i sprawdzać czy łazienka jest wolna. Jaki pomysł podano w artykule? Założono, że każdy użytkownik ma swojego następnika, czyli osobę która może umyć się po nim. Jeśli jakaś osoba wejdzie do łazienki to po umyciu się zmienia na tabliczce swój numer pokoju na pokój kolejnego pokoju którego mieszkaniec może się umyć. I tak w kółko. Problem w tym, że jeśli jeden z mieszkańców wypadnie z obiegu to nastąpi blokada, gdyż nikt poza tą osobą nie będzie mógł wejść do łazienki, a osoba której nie ma nie może zwiększyć numeru na tabliczce, bo właśnie jej nie ma :-D Podać przykład techniki i notacji programistycznej do opisywania teoretycznej równoległości. - CSP - notacja synchroniczna, "program" w CSP jest zbudowany z deklaracji i instrukcji. Każda instrukcja może wykonać się poprawnie lub załamać się. Ponieważ traktujemy CSP jak notację, a nie język programowania, nie precyzujemy, co dokładnie oznacza załamanie instrukcji. Cechą charakterystyczną niektórych instrukcji CSP jest występujący w nich niedeterminizm. <instrukcja> ::= <instrukcja prosta> | <instrukcja strukturalna> <instrukcja prosta> ::= <instrukcja pusta> | <przypisanie> | <wejście> | <wyjście> <instrukcja strukturalna> ::= <alternatywa> | <iteracja> | <instrukcja równoległa> <instrukcja pusta> ::= skip Abstrakcja programowania współbieżnego -Dwie najważniejsze techniki stosowane przy tworzeniu abstrakcji programistycznych: a)Kapsułkowanie b)Współbieżność -Model wzajemnych oddziaływań procesów - procesy zazwyczaj oddziałują na siebie: a)Współzawodnictwo - ubiegają się o ten sam zasób, konieczne metody wzajemnego wykluczania b)Komunikacja - przesyłanie danych od jednego do drugiego, sama komunikacja może synchronizować -Instrukcje atomowe - zbiór rozkazów procesora realizujących algorytm programu współbieżnego. Są niepodzielne i nieprzerywalne. -Przeplot - kombinacja instrukcji atomowych wchodzących w skład procesów -Czas - w programowaniu współbieżnych upływ czasu jest ignorowany. Podczas działania programu brany pod uwagę jest ciąg instrukcji a nie upływ czasu -Poprawność programu - spełnianie własności bezpieczeństwa i żywotności, opis Synchroniczność - wymiana komunikatów wymaga współdziałania nadawcy i odbiorcy Asynchroniczność - wymiana nie wymaga komunikacji Symetryczność - nadawca i odbiorca znają swoje nazwy przed nawiązaniem komunikacji Asymetryczność - tylko nadawca wie z kim się komunikuje, odbiorca nie wie kto się z nim komunikuje
|
Jakie są rodzaje relacji pomiędzy procesami? -Proces potomny i macierzystymi -Procesy niezależne i współpracujące
Podać różnice miedzy semaforami Dijkstry a semaforami z System V Release 4. -Włączenie flag do klasyfikacji operacji, czyli istnienie flag które określają, że w razie niedostępności zasobu w -momencie chęci opuszczenia semafora przez proces możliwe są inne operacje, aby proces nie czekał bezczynnie -Możliwość niepodzielnego wykonania zdefiniowanej listy operacji -Możliwość zmiany wartości semafora o dowolną wartość całkowitoliczbową
Algorytm piekarniany Każdy proces musi dostać bilet, zmienną której wartość jest większa od wszystkich innych przyznanych dotąd biletów. Jeśli wartość jego biletu jest najmniejsza ze wszystkich oznacza to, że może wejść do swojej sekcji krytycznej. Algorytm ten zapewnia wszystkie potrzebne własności, jednak jest nieefektywny gdyż po pierwsze numeru biletów rosną nieograniczenie, a po drugie każdy proces musi pytać każdy inny proces o wartość jego biletu. Przy dużej ilości procesów jest to bardzo nieefektywne.
Algorytm bankiera Algorytm służący do lokacji zasobów w taki sposób, aby uniknąć zakleszczeń. Zapobiega on wystąpieniu zakleszczeń przez odmówienie lub zawieszenie dostępu do zasobu w przypadku, gdyby dostęp do tego zasobu mógł spowodować wejście systemu w stan niebezpieczny. Aby algorytm bankiera działał, potrzebne są następujące dane: -jakiej części każdego zasobu każdy proces może zażądać, -jakiej części każdego zasobu każdy proces aktualnie używa, -jaką część każdego zasobu system ma aktualnie dostępną. Monitory Hoare'a - zmienne warunkowe z blokowaniem. W zmiennych warunkowych z blokowaniem wątek powiadamiający jest blokowany do czasu, aż powiadomiony wątek oczekujący nie opuści monitora lub nie zatrzyma się w ponownym oczekiwaniu na warunek. Zakładamy, że występują dwie główne kolejki wątków: -e jest kolejką wejściową. -s jest kolejką wątków powiadamiających. Program współbieżny: -Jest zbiorem programów sekwencyjnych wykonywanych abstrakcyjnie równolegle -Każdy program sekwencyjny w programie współbieżnym to proces -Program oznacza zbiór procesów sekwencyjnych -Współbieżność może być rzeczywista lub pozorna. Rzeczywista jeśli liczba dostępnych procesorów >= liczba procesów Zmienna warunkowa Służy do synchronizacji wewnątrz monitora. Można na niej wykonać trzy operacje: Wait(C) Signal(C) oraz Is_not_empty(c) - jeśli kolejka związana ze zmienną warunkową jest niepusta zwraca true
Zaproponować rozwiązanie problemu budzenia wielu procesów zablokowanych na zmiennych warunkowych monitora procesów, gdy operacja Signal(C) nie jest ostatnią operacją procedury udostępnianej przez monitor? -Stasuje się technikę odraczania wznowienia procesu budzonego operacją Signal(C) do czasu opuszczenia monitora przez bieżący proces. -Co jeśli proces wykona wiele operacji Signal(C) i obudzi wiele procesów? -Procesy wchodzące do monitora ustawiane są w kolejce prostej i po wywołaniu przez pierwsza funkcję operacji Signal(C) wywoływany jest wait(C) w innym procesie który wstrzymuje wszystkie pozostałe procesy
Własność bezpieczeństwa -Wzajemne wykluczanie - dwa procesy nie mogą przeplatać pewnych ciągów instrukcji(sekcji krytycznej). -Brak blokad - system który nie kończy pracy musi zawsze być w stanie wykonywać użyteczną pracę. Nie może się zdarzyć, że system nie reaguje na żaden sygnał lub żądanie Własność żywotności -Brak zagłodzeń - proces który zgłosił żądanie dostępu do zasobu w końcu go dostanie(oczywiście w końcu jest pojęciem względnym, ale musi to być rozsądny czas a nie 1000 lat) -Własność uczciwości - jest to określenie sposoby przydziału zasobu przy współzawodnictwie o określony zasób. a)Słaba - jeśli proces zgłasza żądanie nieprzerwanie dostanie w końcu zasób b)Mocna - jeśli proces zgłasza żądanie nieskończenie wiele razy dostanie zasób c)Liniowa - żądanie zostanie obsłużone zanim dowolny inny proces zostanie obsłużony więcej niż raz d)FIFO - żądanie zostanie obsłużone przed innym żądaniem zgłoszonym później
|