1. Podaj przykłady techniki i notacji programistycznej służącej do wyrażania potencjalnej
równoległości co najmniej dwóch procesów sekwencyjnych.
Kapsułkowanie – abstrakcja programowania osiągana poprzez podział modułu programu na
publiczną specyfikację i wewnętrzną implementację. Programowanie współbieżne jest abstrakcją
umożliwiającą wnioskowanie o dynamicznym wykonywaniu programów. System rozproszony jest
systemem komputerowym złożonym z więcej niż jednego komputera. Wzajemne oddziaływanie
między procesami może przyjąć następujący charakter:
• Współzawodnictwo
• Komunikacja.
Współbieżność:
Klasyczne programowanie współbieżne - polega na dekompozycji problemu na wiele elementów
oprogramowania, które są wykonywane przez pewną liczbę procesorów z pamięcią współdzieloną,
tzw. systemy ściśle powiązane, inaczej systemy wieloprocesorowe.
Współbieżność rozproszona - polega na dekompozycji problemu na wiele elementów
oprogramowania, które są wykonywane przez pewną liczbę niezależnych procesorów (własny zegar
taktujący i pamięć operacyjna) komunikujących się poprzez sieć połączeń (np. sieć lokalna,
przełącznica krzyżowa, itp.), czyli tzw. systemy luźno powiązane, inaczej systemy rozproszone.
2. Co w praktyce oznacza własność żywotności programu współbieżnego ?
Jest to uogólnienie własności stopu na programy współbieżne. Program współbieżny jest żywotny,
jeśli zapewnia, że każde pożądane zdarzenie kiedyś zajdzie. W przypadku problemu wzajemnego
wykluczania własność żywotności oznacza, że jeśli jakiś proces czeka na wejście do swojej sekcji
krytycznej, to w końcu do niej wejdzie. Aby pokazać, że program nie ma własności żywotności, trzeba
podać szczególnie dobrany scenariusz synchronizacji przy którym nie da się osiągnąć pożądanej
sytuacji.
3. Wymień co najmniej 3 języki programowania współbieżnego z konstrukcją monitora procesów.
Pascal_C, Concurrent Pascal, Pascal Plus, Modula 2, Modula 3, Concurrent Euclid
4. Jeżeli w problemie czytelników i pisarzy może dojść do zagłodzenia, to scharakteryzuj
odpowiednią(e) sytuację(e).
W problemie czytelników i pisarzy może dojść do zagłodzenia zarówno pisarzy jak i czytelników, w
zależności od wybranego rozwiązania. Zgodnie z warunkami zadania czytelnik, który zapragnie wejść
do czytelni powinien móc to zrobić, jeśli jest ona pusta lub jeśli są w niej już inni czytelnicy. W
przeciwnym razie (tzn. gdy w czytelni jest już pisarz) powinien być wstrzymany do czasu, gdy zajdą
warunki pozwalające mu wejść. Pisarz, który chce wejść do czytelni, powinien być wstrzymany aż
będzie ona pusta.
Rozwiązanie z możliwością zagłodzenia pisarzy:
Czytelnicy na zawsze zawładną czytelnią. Wystarczy, że w każdej chwili będzie w niej przebywał co
najmniej jeden czytelnik, a pisarze nie doczekają się pustej czytelni. Ta sytuacja wymaga aby do
czytelni przychodził następny czytelnik zanim poprzedni zdąży czytelnie opuścić.
Rozwiązanie z możliwością zagłodzenia czytelników:
1
Wydaje się, że jeśli pisarze chcą coś zapisać, tp należy im to umożliwić najszybciej jak to możliwe, nie
ma sensu bowiem, aby czytelnicy odczytywali przestarzałe dane. Zatem jeśli jakiś pisarz czeka na
wejście do czytelni, bo są w niej jacyć czytelnicy, to nowo przybyły czytelnik powinien być
wstrzymany, gdy już żaden pisarz nie będzie czekał. Dzięki temu po pewnym czasie wszyscy czytelnicy
przebywający w czytelni ją opuszczą i będą mogli wejść pisarze. Wystarczy, że zawsze jakiś pisarz
będzie czekał na możliwość pisania, a żaden z czytelników nie będzie mógł wejść doc czytelni.
5. Wymień różnice miedzy semaforem zdefiniowanym przez Dijkstrę a semaforem dostępnym w
systemie SVR4.
Semafory w systemie Unix są uogólnieniem semaforów zaproponowanych przez Dijkstrę.
U D. Wartość początkową semafora określamy przy deklaracji, a w SVR4 przypisanie wartości
semaforowi jest możliwe w dowolnej chwili.
U D. operacje podniesienia i opuszczenia semafora polega na zwiększeniu/zmniejszeniu wartości
zmiennej semaforowej o 1, podczas gdy w Unixie można zmieniać o dowolną liczbę całkowitą.
Oprócz operacji P(opuść) i V(podnieś) dostępnych u D. w Unixie można wykonywać operację
przechodzenia pod opuszczonym semaforem (Z – wstrzymaj działanie procesy aż S będzie równe 0).
Dodatkowo w systemie Unix można wykonywać jednocześnie operacje na wielu semaforach, przy
czym każda z nich może być inna.
6. Dlaczego sekcja krytyczna powinna być "możliwie najkrótsza" w sensie czasu pobytu w niej
procesu sekwencyjnego
Ponieważ w trakcie wykonywania sekcji krytycznej jednego procesu inne procesy, które również chcą
wejść do sekcji krytycznej muszą oczekiwać na wyjście tego procesu z sekcji. Tracony jest przez to
czas (pozostałe procesy nic nie robią), zanika częściowo współbieżność programu i zaczyna on działać
jak zwykły program sekwencyjny, ponadto czekanie na zwolnienie sekcji krytycznej również pochłania
czas procesora (np. aktywne czekanie).
7. Wymień warunki konieczne do wystąpienia zakleszczenia procesów sekwencyjnych.
Wzajemne wykluczanie: przynajmniej jeden zasób musi być niepodzielny, tzn., że z zasobu tego może
korzystać w danym czasie tylko jeden proces. Jeśli inny proces zamawia dany zasób, to musi być
opóźniany, aż zasób zostanie zwolniony
Przetrzymywanie i oczekiwanie: Musi istnieć proces, któremu przydzielono co najmniej jeden zasób i
który oczekuje na przydział dodatkowego zasobu (zasobów), przetrzymywanego właśnie przez inny
proces.
Brak wywłaszczeń: zasoby nie podlegają wywłaszczeniu, tzn., że proces może zostać zwolniony tylko z
inicjatywy przetrzymującego go procesu, po zakończeniu pracy tego procesu.
Czekanie cykliczne: Musi istnieć zbiór {P0..Pn} procesów czekających, takich, że P0 czeka na zasób
przetrzymywany przez proces P1, P1 czeka na zasób przetrzymywany przez P2, .. a Pn na zasób
przetrzymywany przez P0.
8. Podaj podstawowe modele oddziaływania procesów sekwencyjnych.
Procesy niezależne od siebie
Rywalizacja (współzawodnictwo)
2
1. Wynik jednego procesu nie zależy od działań pozostałych
2. Możliwe jest oddziaływanie na tempo wykonywania procesu 1. Wzajemne wykluczanie
2. Blokowanie (zasoby wymienne)
3. Zagłodzenia
===============================
Procesy pośrednio zależne od siebie (poprzez obiekty współdzielone)Współpraca poprzez wspólne wykorzystywanie obiektów
1. Wynik jednego procesu może zależeć od danych otrzymanych od innych
2. Możliwy jest wpływ na tempo wykonywania procesu
1. Wzajemne wykluczanie
2. Blokowanie (zasoby wymienne)
3. Zagłodzenia
4. Zachowanie spójności danych
================================
Procesy bezpośrednio zależne od siebie (korzystanie z elementarnych procedur komunikacyjnych)Współpraca poprzez komunikację
1. Wynik jednego procesu może zależeć od danych otrzymanych od innych
2. Możliwy jest wpływ na tempo wykonywania procesu
1. Blokowanie (zasoby wyczerpywalne)
2. Zagłodzenia
9. Dlaczego operacja Wait(S), gdzie S jest semaforem, powinna być operacją atomową.
Opuszczenie semafora, czyli operacja wait(S) to wykonanie instrukcji:
Czekaj, aż S>0;
S:=S-1;
Jeśli proces rozpoczynający opuszczanie semafora stwierdzi, że jego wartość nie jest dodatnia, musi
zaczekać. Ale aby mógł on zakończyć opuszczenie semafora jakiś inny proces musi mieć możliwość
wykonania operacji podniesienia. W rzeczywistości w takim przypadku operacja opuszczania musi być
przerwana w trakcie sprawdzania warunku S>0. Podczas tej przerwy jakiś Iny proces może rozpocząć
opuszczanie semafora i ta operacja również musi zostać przerwana. W rezultacie można mieć wiele
rozpoczętych a nie zakończonych operacji opuszczenia. Jednak w chwili, gdy jakiś inny proces
zwiększy S, tylko jedna z tych operacji będzie mogła wykonać się do końca, ponieważ zakłada się, iż
stwierdzenie S>0 i wykonanie s:=S-1 to jedna niepodzielna operacja. W definicji klasyczne przyjmuje
się więc, że operacja opuszczenia semafora jest niepodzielna tylko wtedy, gdy sprawdzany w niej
warunek jest spełniony.
10. Określ powody, dlaczego próby I, II, III i IV prowadzące do algorytmu Dekkera były
rozwiązaniami niepoprawnymi.
I próba
W przypadku braku współzawodnictwa, tzn. gdy jeden z procesów utknie w swojej sekcji lokalnej
drugi proces może wejść do sekcji krytycznej tylko raz. Gdy jeden z procesów wchodzi do sekcji
krytycznej bardzo często a drugi bardzo rzadko rozwiązanie to wprowadza konieczność czekania
przez proces szybszy. Jest to spowodowane naprzemiennym przekazywaniem prawa wejścia do sekcji
krytycznej.
II próba
Druga próba nie spełniała nawet własności wzajemnego wykluczania. Poza tym wadą tego
rozwiązania jest również to, że proces po wyjściu z protokołu wstępnego nie może być powstrzymany
przed wejściem do sekcji krytycznej.
3
Może wystąpić blokada
Niestety już po kilku instrukcjach może nastąpić blokada. Przykładowy ciąg instrukcji udowadnia taką
możliwość:
a) P1 nadaje zmiennej K1 wartość 0.
b) P2 nadaje zmiennej K2 wartość 0.
c) P1 sprawdza wartość K2 i pozostaje w pętli.
d) P2 sprawdza wartość K1 i pozostaje w pętli.
IV próba
Niestety może dojść do zagłodzenia procesu. Przykładowy ciąg instrukcji udowadnia taką możliwość:
a) P1 przypisuje K1 wartość 0.
b) P2 przypisuje K2 wartość 0.
c) P2 sprawdza wartość K1 i przypisuje K2 wartość 1.
d) P1 wykonuje pełny obrót pętli:
e) - sprawdza wartość K2,
f) - wchodzi do sekcji krytycznej,
g) - przywraca wartość 1 zmiennej K1,
h) - wykonuje sekcję lokalną,
i) - przypisuje zmiennej K1 wartość 0.
j) P2 przypisuje zmiennej K2 wartość 0.
k) Jeżeli przejdziemy do kroku d) to mamy zagłodzenie procesu P2.
4