Obliczenia Równoległe - Wybrane Problemy Przetwarzania Współbieżnego

Problem Sekcji Krytycznej

Definicja: Dotyczy dostępu do zasobów, które mogą być współdzielone przez ograniczoną liczbę procesów.
- Zasoby wielopodzielne: Dostęp może uzyskać ograniczona liczba procesów.
- Zasoby jednopodzielne (niepodzielne): Dostęp może uzyskać tylko jeden proces na raz.
Rozwiązanie: Polega na przydzielaniu dostępu do zasobu ograniczonej liczbie procesów jednocześnie.
Przykładowe zasoby jednopodzielne:
- Konsola wiersza poleceń (drukarka).
- Sektor dysku twardego.
- Komórka pamięci współdzielonej między procesami.
Uwagi praktyczne:
- W praktyce przydziałem niektórych zasobów niepodzielnych zajmuje się sprzęt lub system operacyjny.
- Odczyt współdzielonej komórki pamięci może sprawiać wrażenie dostępu do zasobu podzielnego.
- W modelach teoretycznych problem jest upraszczany.
Definicja sekcji krytycznej: Fragment zadania, w którym proces korzysta z zasobów jednopodzielnych.
Wzajemne wykluczanie: Gwarancja, że operacje w sekcjach krytycznych różnych procesów nie nakładają się w czasie.
Nakładanie się w czasie:
- Wykonanie równoległe: Jednoczesne wykonanie przez wiele procesów.
- Metoda przeplotu: Przerwanie wykonywania sekcji przez jeden proces i rozpoczęcie przez inny.
Przykład:

Globalne: zasób ▷ Pewien niepodzielny zasób

procedure A ▷ Proces A
    ▷ Operacje procesu A
    Rozpocznij sekcję krytyczną
        Wykorzystaj zasób ▷ Wzajemne wykluczenie
    Zakończ sekcję krytyczną
    ▷ Inne operacje procesu A
end procedure

procedure B ▷ Proces B
    ▷ Operacje procesu B
    Rozpocznij sekcję krytyczną
        Wykorzystaj zasób ▷ Wzajemne wykluczenie
    Zakończ sekcję krytyczną
    ▷ Inne operacje procesu B
end procedure

Semafory

Definicja semafora: Licznik przechowujący liczbę dostępnych zasobów z przyporządkowaną kolejką oczekujących procesów. Umożliwia operacje wait (P) i signal (V, notify).
Operacje na semaforze s:
- wait(s): jeśli s > 0, wykonaj s ← s - 1; w przeciwnym razie wstaw bieżący proces do kolejki i czekaj.
- signal(s): jeśli istnieje proces w kolejce, usuń go z kolejki i wznów; w przeciwnym razie wykonaj s ← s + 1.
Atomowość operacji: Operacje wait i signal są atomowe (niepodzielne).
Historia nazw: Nazwy P (probeer verlaag) oraz V (verhoog) są określeniami holenderskimi, wprowadzone przez Edsgera Dijkstrę.
Inicjalizacja semafora: Przypisanie początkowej wartości i przyporządkowanie pustej kolejki.
Rodzaje semaforów:
- Semafor ogólny: Może przyjmować dowolne wartości naturalne większe lub równe 0.
- Semafor binarny (muteks): Może przyjmować tylko wartości 0 i 1. Sytuacja, gdy s > 1, jest błędna.
Zastosowanie semaforów: Określanie liczby dostępnych zasobów danego typu.
Wykorzystanie semafora binarnego: Zapewnienie wzajemnego wykluczenia, traktując dostęp do sekcji krytycznej jako zasób niepodzielny.
Przykład użycia semafora binarnego:

Globalne: s = 1 ▷ Semafor binarny
Globalne: zasób ▷ Pewien niepodzielny zasób

procedure A ▷ Proces A
    ▷ Operacje procesu A
    wait(s)
        Wykorzystaj zasób ▷ Sekcja krytyczna — wzajemne wykluczenie
    signal(s)
    ▷ Inne operacje procesu A
end procedure

procedure B ▷ Proces B
    ▷ Operacje procesu B
    wait(s)
        Wykorzystaj zasób ▷ Sekcja krytyczna — wzajemne wykluczenie
    signal(s)
    ▷ Inne operacje procesu B
end procedure

Zakleszczenie i zagłodzenie: Niewłaściwe użycie semaforów może prowadzić do zakleszczeń lub zagłodzenia procesów.
- Zakleszczenie: Wzajemne oczekiwanie na zwolnienie zasobów przez co najmniej dwa wątki.
- Zagłodzenie: Nieudostępnienie zasobu procesowi pomimo oczekiwania "w nieskończoność".
Przykład zakleszczenia:

Globalne: s = 1, r = 1 ▷ Semafory binarne
Globalne: zasób1, zasób2 ▷ Pewne zasoby

procedure A ▷ Proces A
    wait(s)
    wait(r) ▷ Ryzyko zakleszczenia!
        Wykorzystaj zasób1 i zasób2 ▷ Sekcja krytyczna
    signal(s)
    signal(r)
end procedure

procedure B ▷ Proces B
    wait(r)
    wait(s) ▷ Ryzyko zakleszczenia!
        Wykorzystaj zasób1 i zasób2 ▷ Sekcja krytyczna
    signal(s)
    signal(r)
end procedure

*   **Scenariusz zakleszczenia**:
    1.  Wykonanie `wait(s)` procesu A.
    2.  Wykonanie `wait(r)` procesu B.
    3.  Wykonanie `wait(r)` procesu A powoduje czekanie procesu A.
    4.  Wykonanie `wait(s)` procesu B powoduje czekanie procesu B.

Przykład zagłodzenia:

Globalne: i = 0 : Integer
Globalne: s = 1 ▷ Semafor binarny

procedure Dzialaj1
    while true do
        wait(s)
        i ← i + 1
        signal(s)
        Oblicz
        wait(s)
        i ← i - 1
        gotowe ← true
        signal(s)
    end while
end procedure

procedure Dzialaj2
    while true do
        wait(s)
        i ← i + 1
        signal(s)
        Oblicz
        wait(s)
        i ← i - 1
        gotowe ← true
        signal(s)
    end while
end procedure

procedure Reaguj
    while true do
        wait(s)
        ▷ Ryzyko zagłodzenia
        if i = 0 then
            Wypisz("Gotowe")
            gotowe ← false
        end if
        signal(s)
    end while
end procedure

*   **Scenariusz zagłodzenia**: 
    1.  Wykonanie procesu Dzialaj1 do linii 5.
    2.  Wykonanie procesu Reaguj (być może wcześniej czekającego) — wypisanie nie następuje.
    3.  Wykonanie procesu Dzialaj2 do linii 17.
    4.  Wykonanie procesu Reaguj (być może wcześniej czekającego) — wypisanie nie następuje.
    5.  Dalsze powtarzanie się analogicznego ciągu.

Problem Producenta i Konsumenta

Opis problemu:
- Proces producenta generuje dane.
- Proces konsumenta wykorzystuje te dane.
- Dane są buforowane ze względu na różną szybkość pracy procesów.
- Konsument może pobrać dane tylko, gdy są dostępne.
Przykład - nieskończony bufor:

Globalne: buf[0..∞] : Integer; pocz=0, kon=0 : Integer
Globalne: s = 0 ▷ Semafor — czy są dane?

procedure Producent
    while true do
        dane ← Produkuj
        buf[kon] ← dane
        kon ← kon+1
        signal(s)
    end while
end procedure

procedure Konsument
    while true do
        wait(s)
        dane ← buf[pocz]
        pocz ← pocz+1
        Konsumuj(dane)
    end while
end procedure

*   Semafor służy nie tylko do osłaniania sekcji krytycznej.
*   Pełni rolę synchronizacji warunku - pozwala na warunkowe wykonanie, gdy zostaną spełnione czynniki wynikające z pracy innego procesu.
*   Odwołanie do współdzielonego zasobu (np. wartości `buf[i]`) odbywa się tylko dwa razy, w określonej kolejności.

Przykład - skończony bufor:

Globalne: buf[0..N - 1] : Integer; pocz=0, kon=0 : Integer ▷ N — stała
Globalne: d = 0, m = N ▷ Semafory — czy są dane, czy jest miejsce?

procedure Producent
    while true do
        dane ← Produkuj
        wait(m)
        buf[kon] ← dane
        kon ← (kon+1) mod N
        signal(d)
    end while
end procedure

procedure Konsument
    while true do
        wait(d)
        dane ← buf[pocz]
        pocz ← (pocz+1) mod N
        signal(m)
        Konsumuj(dane)
    end while
end procedure

*   Spełniony jest warunek (niezmiennik):  $0 \le d + m \le N$ .
*   Grupy semaforów, których sumy wartości nie przekraczają pewnej wartości, nazywamy semaforami rozdzielnymi.

Zmienne Warunków

Zastosowanie: Gdy kontynuacja procesu wymaga spełnienia pewnego warunku, zależnego od innego procesu.
Definicja zmiennej warunków: Obiekt sygnalizujący spełnienie warunku, z przyporządkowaną kolejką procesów oczekujących na jego spełnienie. Umożliwia wykonanie operacji waitC i signalC.
Operacje dla zmiennej warunków c:
- waitC(m, c): Wykonaj signal(m), wstrzymaj proces i umieść go w kolejce.
- signalC(c): Jeśli istnieje jakiś proces w kolejce, wznów go i wykonaj wait(m) we wznowionym procesie.
- Semafor m jest semaforem binarnym, osłaniającym zasoby, których dotyczą warunki.
- Obowiązkiem jest zapewnienie, aby semafor był w prawidłowym stanie przy wywołaniu waitC.
Przykład:

Globalne: m = 1 ▷ Semafor binarny
Globalne: c ▷ Zmienna warunków
Globalne: i = 0 ▷ Zmienna, której wartość powinna i ∈ <10, 20>

procedure CzekajNaZakres
    wait(m)
    while i ∉ <10, 20> do
        waitC(m, c)
    end while
    Wypisz("Teraz zmienna ma prawidlowa wartosc")
    signal(m)
end procedure

procedure Generuj
    while true do
        j ← Losuj(0, 100)
        wait(m)
        i ← j
        signalC(c)
        signal(m)
    end while
end procedure

Problem Ucztujących Filozofów

Opis problemu: Pięciu filozofów korzysta ze wspólnych zasobów (widelców) do jedzenia spaghetti.
- Do jedzenia potrzebne są dwa widelce.
- Filozofowie siedzą przy okrągłym stole, rozdzieleni widelcami.
- Każdy widelec jest dzielony między dwóch filozofów, ale tylko jeden może z niego korzystać w danej chwili.
- Filozofowie jedzą na przemian z myśleniem; podczas jedzenia podnoszą najpierw jeden, a potem drugi widelec.
- Gdy widelec jest niedostępny, filozof czeka.
Przykład (nieprawidłowe rozwiązanie):

Globalne: s[0..4] = (1,1,1,1,1) ▷ Semafory binarne widelców

procedure Filozof(i) ▷ i ∈ 0..4 — numer filozofa
    while true do
        Mysl
        wait(s[i]) ▷ Weź widelec
        wait(s[(i + 1) mod 5]) ▷ Weź widelec
        Jedz
        signal(s[i])
        signal(s[(i + 1) mod 5])
    end while
end procedure

*   Ryzyko zakleszczenia: Jeśli każdy filozof w tej samej chwili weźmie pierwszy widelec.

Rozwiązanie 1: Ograniczenie liczby ucztujących filozofów do 4 (w praktyce nawet do $⌊n/2⌋$ , gdzie n to liczba filozofów).

Globalne: sa miejsca = 4 ▷ Semafor liczby jedzących
Globalne: s[0..4] = (1,1,1,1,1) ▷ Semafory binarne widelców

procedure Filozof(i) ▷ i ∈ 0..4 — numer filozofa
    while true do
        Mysl
        wait(sa miejsca) ▷ Zajmij miejsce
        wait(s[i]) ▷ Weź widelec
        wait(s[(i+1) mod 5]) ▷ Weź widelec
        Jedz
        signal(s[i])
        signal(s[(i+1) mod 5])
        signal(sa miejsca)
    end while
end procedure

Rozwiązanie 2: Zastosowanie odwrotnej kolejności brania widelców przez co najmniej jednego filozofa.

Globalne: s[0..4] = (1,1,1,1,1) ▷ Semafory binarne widelców

procedure Filozof(i) ▷ i ∈ 0..4 — numer filozofa
    if i mod 2 = 0 then
        p ← i
        q ← (i + 5) mod 2
    else
        p ← (i + 5) mod 2
        q ← i
    end if
    while true do
        Mysl
        wait(s[p]) ▷ Weź widelec
        wait(s[q]) ▷ Weź widelec
        Jedz
        signal(s[p])
        signal(s[q])
    end while
end procedure

Inne rozwiązania:
- Wykrywanie i wywłaszczanie w przypadku zakleszczenia.
- Metoda zarządcy i wykonawców (kelner).
- Określenie hierarchii zasobów (widelców) - kolejność ich brania.

Inne Problemy

Problem czytelników i pisarzy:
- Zasób (baza danych) jest współdzielony między czytelników (niemodyfikujących zasobu) i pisarzy (modyfikujących zasób).
- Dostęp czytelników jest wielopodzielny (wielu czytelników jednocześnie).
- Dostęp pisarzy jest niepodzielny (tylko jeden pisarz na raz, wyklucza dostęp innych procesów).
- Problem synchronizacji warunku: pisanie może być wykonywane tylko gdy nie są wykonywane zadania czytelników.
- Rozwiązanie: semafor, ograniczający dostęp do zapisu tylko dla jednego procesu; inkrementacja semafora tylko, gdy nie ma odczytu (i zapisu).
- Ryzyko zagłodzenia czytelników lub pisarzy w zależności od podejścia.
Problem śpiącego golibrody:
- Zasób (golibroda) jest współdzielony między klientów.
- Gdy nie ma klientów, golibroda zasypia; budzi go wchodzący klient.
- Kolejni klienci czekają w poczekalni (o ograniczonej liczbie miejsc), gdy golibroda jest zajęty.
- Golibroda, po zakończeniu pracy, woła kolejnego klienta z poczekalni.
- Problem wyścigu:
  - Klient widzi zajętego golibrodę i idzie do (pustej) poczekalni, ale w tym czasie golibroda kończy pracę i idzie do pustej poczekalni.
  - Dwóch klientów idzie jednocześnie do poczekalni, gdzie jest jedno wolne miejsce.
  - Problem wyścigu: różne procesy wykonują czynności w nieokreślonej kolejności.