- Klasyczne problemy współbieżności
- Problem producenta i konsumenta
- Problem ucztujących filozofów
- Debugger BACI
- Rozwiązywanie problemu ucztujących filozofów
- Zadania domowe
Klasyczne problemy współbieżności
W teorii współbieżności rozważa się kilka klasycznych problemów, mających ilustrować typowe sytuacje konkurowania procesów o dostęp do ograniczonych zasobów. Na dzisiejszych zajęciach będziemy szukać rozwiązań dla problemu producenta i konsumenta oraz problemu ucztujących filozofów.
Problem producenta i konsumenta
Polega na zsynchronizowaniu dwóch procesów: producenta, który cyklicznie produkuje jedną porcję informacji a następnie przekazuje ją do skonsumowania, i konsumenta, który cyklicznie pobiera porcję i konsumuje ją. Jeśli w danej chwili producent nie może zbyć wyprodukowanej porcji, musi czekać. Podobnie, jeśli konsument nie może pobrać porcji, także musi czekać. Porcje powinny być konsumowane w kolejności wyprodukowania.
Praca domowa z poprzednich zajęć polegała na rozwiązaniu tego problemu używając do komunikacji pojedynczej zmiennej - po wyprodukowaniu każdej porcji, producent musiał czekać, aż konsument skonsumuje poprzednią. W przypadku bardziej ogólnym chcemy użyć N-elementowego bufora, w którym przechowywane będą wyprodukowane porcje - producent i konsument nie muszą wtedy działać w sposób aż tak zsynchronizowany - np. gdy konsument odczytuje element w jednej pozycji bufora, producent może równolegle zapisywać w innej.
Zadanie 1
Oto gotowy kod prostej struktury danych - kolejki FIFO (first in - first out). Do operacji na kolejce (dodawania i pobierania elementów) należy używać wyłącznie funkcji queue_add i queue_get (niestety BACI nie udostępnia struktur ani klas, więc zmiennych ani funkcji nie można zawrzeć w osobnej strukturze, stąd zarówno zmienne stanowiące implementacje kolejki, jak i jej interfejs - funkcje służące do jej obsługi - muszą być globalne).
// Prosta N-elementowa kolejka FIFO
// Kolejka nie sprawdza czy jest wolne miejsce lub element do pobrania!
const int N = 5;
int buffer[N];
int write_pos = 0;
int read_pos = 0;
void queue_add(int item)
{
buffer[write_pos] = item;
write_pos = (write_pos + 1) % N;
}
int queue_get()
{
int item;
item = buffer[read_pos];
read_pos = (read_pos + 1) % N;
return item;
}
Użyj podanego kodu, aby zaimplementować rozwiązanie problemu producenta i konsumenta dla n-elementowego bufora - producent generuje wiele (np. 50) liczb i zapisuje je w buforze o niewystarczającej wielkości (np. 10). Konsument ma za zadanie wypisać wszystkie 50 liczb w kolejności, w jakiej zostały wyprodukowane. Aby upewnić się, że program działa poprawnie, zamiast losowo generowanych liczb każ producentowi produkować kolejne liczby całkowite (np. od 1 do 50) - łatwiej będzie sprawdzić, czy np. konsument nie pominął żadnego elementu.
Problem ucztujących filozofów
Polega na zsynchronizowaniu działań pięciu filozofów, którzy siedzą przy okrągłym stole i myślą. Jest to ich główne zajęcie. Jednak od czasu do czasu każdy filozof głodnieje i aby móc dalej myśleć, musi się najeść. Przed każdym filozofem stoi talerz, a pomiędzy kolejnymi dwoma talerzami leży jeden widelec. Na środku stołu stoi półmisek spaghetti. Aby rozpocząć jedzenie, filozof musi mieś do dyspozycji oba widelce. Podnosząc leżące przy nim widelce filozof uniemożliwia jedzenie swoim sąsiadom. Zakłada się, że jeśli filozof podniósł już oba widelce, to w skończonym czasie naje się i odłoży je na stół.
Zadanie 2
Zaprogramuj rozwiązanie problemu ucztujących filozofów, reprezentując widelce przy użyciu semaforów binarnych. Pięć procesów (filozofów) będzie konkurować o pozyskanie semaforów (widelców). Gdy filozof uzyska oba potrzebne widelce, powinien wypisać na standardowe wyjście komunikat, symbolizujący proces jedzenia i odłożyć widelce. Każdy filozof powinien jeść wielokrotnie (np. 1000 razy) - pozwoli to zwiększyć pewność, czy program działa poprawnie.
Przykładowy fragment rezultatu wykonania programu:
Jestem filozofem o numerze 1 i myślę.
Jestem filozofem o numerze 3 i myślę.
Jestem filozofem o numerze 4 i myślę
Jestem filozofem o numerze 1 i najadłem się po raz 1.
Jestem filozofem o numerze 2 i myślę.
Jestem filozofem o numerze 3 i najadłem się po raz 1.
Jestem filozofem o numerze 1 i myślę.
Jestem filozofem o numerze 2 i najadłem się po raz 1.
Jestem filozofem o numerze 1 i najadłem się po raz 2.
Jestem filozofem o numerze 4 i najadłem się po raz 1.
...
Możesz spróbować zaimplementować poniższy pseudokod:
filozof o indeksie i (z zakresu 0-4) wykonuje:
potwórz 1000 razy:
myśl (wyświetl komunikat)
czekaj na widelec i
czekaj na widelec (i+1)%5
zjedz (wyświetl komunikat)
oddaj widelec i
oddaj widelec (i+1)%5
Debugger BACI
Debugger BACI to program, który pozwala na wykonanie testowanego programu w szczególny sposób i zapewniając dodatkowe informacje. Program można wykonywać krokowo, obserwując stan procesów i zmiennych po wykonaniu każdej instrukcji. Można też zażądać przerwania wykonania programu przy każdej zmianie procesu, albo w momencie wykonywania określonej instrukcji. Wszystko to ma na celu pomoc w zrozumieniu działania programu oraz znajdowaniu i poprawianiu błędów.
Jak używać debuggera
Na wydziałowych linuxach zainstalowany jest graficzny debugger BACI. Uruchamia się go poleceniem:
baci-dbg
Jeśli chcesz skorzystać z niego na swoim prywatnym komputerze, to ściągnij plik https://turing.cs.hbg.psu.edu/~null/baci/baci.jar. Jeżeli plik znajduje się w katalogu roboczym terminala, to program można uruchomić komendą
java -jar baci.jar
Najbardziej użyteczne polecenia debuggera:
- File->Open pozwala załadować skompilowany program BACI w formacie .pco
- Run rozpoczyna wykonywanie programu
- Control->Restart resetuje program (kolejne wywołanie Run wykona program od początku). Z powodu niedoskonałości debuggera, konieczne może być wybranie opcji Restart dwukrotnie (raz po razie)
- Step Source i Step Pcode pozwala wykonywać instrukcje w programie jedna po drugiej, przerywając działanie po wykonaniu każdej instrukcji. Step Source wykonuje kolejne instrukcje kodu źródłowego C--, a Step Pcode - kolejne instrukcje skompilowanego kodu "maszynowego"
- Window->Console/Globals/History otwiera okna z wyjściem konsoli, stanem zmiennych globalnych, i listą ostatnio wykonanych instrukcji kodu Pcode
- Dwukrotne kilknięcie na nazwę procesu w oknie Processes powoduje otwarcie okna z kodem i zmiennymi procesu.
Najbardziej użyteczne opcje debuggera:
- Options->Pause on process swap - wykonanie programu zatrzymuje się za każdym razem, gdy następuje zmiana aktualnie wykonywanego procesu
- Options->Show active window - na wierzchu zawsze wyświetlone jest okno z kodem aktualnie wykonywanego procesu
Uwaga: wskaźnik aktualnej instrukcji w oknie kodu procesu zawsze wskazuje na kolejną instrukcję do wykonania. Zatem, jeżeli wykonywanie procesu zatrzymało się na jakiejś instrukcji (np. instrukcji wait, która może uśpić proces), to wskaźnik będzie pokazywał na kolejną instrukcję po instrukcji wait.
Zadanie 3
Używając debuggera spróbuj ustalić, co powoduje, że rozwiązanie z zadania 2 nie jest poprawne. Jednym z komunikatów, jakie możesz otrzymać podczas wykonywania programu, jest "A deadlock occured". Sprawdź czym jest deadlock (zakleszczenie) i spróbuj ustalić w jakich dokładnie okoliczności może on zachodzić w tym przypadku.
Rozwiązywanie problemu ucztujących filozofów
Zaproponowano wiele rozwiązań problemu ucztujących filozofów, o różnych własnościach i różnym stopniu skomplikowania. My zaimplementujemy dwa proste rozwiązania: jedno w zadaniu 4, drugie w zadaniu domowym.
Najbardziej trywialne rozwiązanie tego problemu to objęcie całego procesu jedzenia (weź widelce, jedz, odłóż widelce) jedną sekcją krytyczną. Jest to jednak rozwiązanie mało satysfakcjonujące - jeżeli jeden filozof je, to żaden inny nie może jeść, nawet jeżeli nie siedzą koło siebie. Oznacza to, że zasoby nie są wykorzystwane optymalnie.
Zadanie 4
Jednym z możliwych rozwiązań jest pozwolić co najwyżej czterem filozofom naraz próbować się najeść, tzn. jeżeli czterej filozofowie chcą jeść i zabiegają o widelce, to piąty musi się powstrzymać i poczekać. W ten sposób, przynajmniej jeden z czterech zabiegających o widelce filozofów zawsze będzie w stanie zdobyć oba widelce, najeść się i odłożyć widelce (pozwalając tym samym najeść się innym). Takie rozwiązanie można zrealizować przy użyciu jednego dodatkowego semafora.
Zadania domowe
Zadanie domowe 1
Rozszerz program z zadania 1 o kolejnego producenta. Dwaj producenci produkują teraz N liczb, a konsument odbiera i wypisuje 2N liczb na standardowe wyjście. Znów, aby ułatwić sobie testowanie rozwiązania, każ jednemu z producentów generować liczby (przykładowo) od 1 do 50, a drugiemu od 101 do 150.
Zadanie domowe 2
Innym możliwym rozwiązaniem problemu ucztujących filozofów jest zmiana kolejności, w jakiej poszczególni filozofowie próbują pozyskać oba potrzebne widelce. Jeżeli co drugi filozof zaczyna pozyskiwanie widelców od prawego, a nie od lewego, to czy zakleszczenie wspomniane w zadaniu 3 może wystąpić? Zaimplementuj takie rozwiązanie.