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

2 Klasyczne problemy współbieżnościProblem producenta i konsumenta Problem czytelników i pisarzy Problem pięciu filozofów

3 Producent i konsument – sytuacja idealnaCzekam Produkuję dane Konsumuję dane Produkuję dane Czekam Konsumuję dane Produkuję dane Czekam Konsumuję dane Produkuję dane Czekam

4 Producent produkuje szybciej niż konsument konsumujeBufor Konsument Czekam Produkuję dane Produkuję dane Konsumuję dane Dane oczekujące Produkuję dane Konsumuję dane Dane oczekujące Produkuję dane Dane oczekujące Konsumuję dane

5 Problem wielkości buforaJeś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 pisarzyczytelnia musi być pusta, aby pisarz mógł pisać Pisarz Czytelnik Czytelnia Czytelnik Pisarz Czytelnik Pisarz wielu czytelników może czytać naraz

7 Rozwiązanie z możliwością zagłodzenia pisarzyCzytelnik 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ówPisarz Czytelnik T Czy czytelnia jest pusta? T Czy pisarz czeka na wejście? Czekam N N Czekam Wchodzę T Czy są w czytelni inni czytelnicy? N Wchodzę N Czy w czytelni jest pisarz? T Czekam

9 Rozwiązanie poprawne Pisarz CzytelnikCzy czytelnicy czekają na wejście? Wpuść wszystkich czytelników Czy pisarz czeka na wejście? Czekam N N 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

10 Problem pięciu filozofówmiska ryżu pałeczka każdy filozof do jedzenia potrzebuje dwóch pałeczek

11 Rozwiązanie z możliwością zakleszczeniaFilozof Czy lewa pałeczka jest wolna? N Czekam T Podnoszę lewą pałeczkę Czy prawa pałeczka jest wolna? N Czekam Myślę T Podnoszę prawą pałeczkę Jem Odkładam pałeczki

12 Rozwiązanie z możliwością zagłodzeniaFilozof Czy obie pałeczki są wolne? N Czekam T Podnoszę obie pałeczki Myślę Jem Odkładam pałeczki

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ść.