Klasyczne problemy współbieżności i ich rozwiązania

1. Klasyczne problemy współbieżności i ich rozwiązania

Jarosław Kuchta
Klasyczne problemy
współbieżności i ich
rozwiązania

2. Klasyczne problemy współbieżności

Problem producenta i konsumenta
Problem czytelników i pisarzy
Problem pięciu filozofów

3. Producent i konsument – sytuacja idealna

Producent
Produkuję dane
Konsument
Czekam
Konsumuję dane
Produkuję dane
Czekam
Konsumuję dane
Produkuję dane
Czekam
Konsumuję dane
Produkuję dane
Czekam

4. Producent produkuje szybciej niż konsument konsumuje

Producent
Bufor
Czekam
Produkuję dane
Produkuję dane
Produkuję dane
Produkuję dane
Konsument
Konsumuję dane
Dane oczekujące
Dane oczekujące
Dane oczekujące
Konsumuję dane
Konsumuję dane

5. Problem wielkości bufora

Jeśli średni czas konsumpcji jest krótszy od średniego czasu
produkcji – bufor może być niepotrzebny.
Jeśli średni czas konsumpcji jest dłuższy od średniego czasu
produkcji – w nieskończonym czasie dowolnej wielkości bufor
może być za krótki.
Jeśli średni czas konsumpcji jest równy od średniemu czasowi
produkcji – ustala się tak wielkość bufora, aby wystarczył na
pewien czas.
Wniosek – jeśli nie możemy zagwarantować, że średni czas
konsumpcji będzie mniejszy lub równy średniemu czasowi
produkcji, to zawsze jakaś porcja danych może zostać utracona.

6. Problem czytelników i pisarzy

czytelnia musi być pusta, aby pisarz mógł pisać
Pisarz
Pisarz
Czytelnik
Czytelnia
Czytelnik
Czytelnik
Pisarz
wielu czytelników może czytać naraz

7. Rozwiązanie z możliwością zagłodzenia pisarzy

Pisarz
Czytelnik
Czy czytelnia jest
pusta?
T
T
Czy są w czytelni
inni czytelnicy?
N
N
Czekam
Wchodzę
Wchodzę
N
Czy w czytelni
jest pisarz?
T
Czekam

8. Rozwiązanie z możliwością zagłodzenia czytelników

Pisarz
Czytelnik
Czy czytelnia jest
pusta?
Czy pisarz czeka
na wejście?
T
N
Czekam
T
Czekam
N
Wchodzę
T
Wchodzę
Czy są w czytelni
inni czytelnicy?
N
N
Czy w czytelni
jest pisarz?
T
Czekam

9. Rozwiązanie poprawne

Pisarz
Czy czytelnicy
czekają na
wejście?
Czytelnik
T
N
Czy czytelnia
jest pusta?
T
Wpuść
wszystkich
czytelników
Czy pisarz czeka
na wejście?
T
Czekam
N
T
Czy są w czytelni
inni czytelnicy?
N
N
Czekam
Wchodzę
Wchodzę
N
Czy w czytelni
jest pisarz?
T
Czekam

10. Problem pięciu filozofów

filozof
miska ryżu
pałeczka
każdy filozof do jedzenia potrzebuje dwóch pałeczek

11. Rozwiązanie z możliwością zakleszczenia

Filozof
Czy lewa pałeczka
jest wolna?
N
Czekam
T
Podnoszę lewą pałeczkę
Myślę
Czy prawa pałeczka
jest wolna?
T
Podnoszę prawą pałeczkę
Jem
Odkładam pałeczki
N
Czekam

12. Rozwiązanie z możliwością zagłodzenia

Filozof
Czy obie pałeczki
są wolne?
T
Myślę
Podnoszę obie pałeczki
Jem
Odkładam pałeczki
N
Czekam

13. Rozwiązanie poprawne

Możliwe tylko przy wprowadzeniu arbitra (służącego)
Służący ma dbać o to, aby najwyżej czterech filozofów
naraz konkurowało o pałeczki.
Jeśli piąty filozof, chce podnieść pałeczkę, to służący go
powstrzymuje do czasu, aż pozostałych czterech
skończy jeść.