Synchronizacja procesów (lub jej brak)
Prowadzący
Robert Obryk
Opis
Zapewne używasz w tej chwili programu wielowątkowego (przeglądarki, w której to czytasz), który najpewniej ma do dyspozycji ponad jeden fizyczny core procesora. Być może kiedyś się zastanawiałeś, jak to działa, że wszystkie te wątki robią zależne od siebie rzeczy (np. jeden czyta stronę z socketa sieciowego, a inny ją rysuję) i jakoś się ze sobą komunikują, a czasem na siebie czekają; wszystko to bez deptania sobie po stopach. Na tych zajęciach będziemy poznawać mechanizmy, których takie programy używają; wymyślać, jak je zaimplementować na "gołym metalu" i faktycznie je implementować. Poza mechanizmami służącymi do czystej komunikacji będziemy próbować stworzyć struktury danych, do których może mieć dostęp wiele wątków na raz.
Program zajęć
Program może ulec zmianom zarówno w zakresie tempa, jak i tematyki (jeśli np. będziecie chcieli myśleć nad innymi strukturami). Podział na dni jest tylko orientacyjny.
- Wstęp, jak działa pamięć współdzielona, synchronizacja za pomocą mutexów (de facto wpierw spinlocków), implementujemy spin lock.
- Jak wątki śpią, piszemy prawdziwy mutex i staramy się go uczynić szybkim. Myślimy nad strukturami typu semafor, rwmutex, once.
- W zależności od chęci dowolny podzbiór:
- Struktury danych (typu stos, kolejka, drzewo binarne, …), które można naprawdę współbieżnie zmieniać
- Jak naprawdę działa dostęp do pamięci (czym są bariery i jak się zupełnie zdezorientować przyspieszając nasze strukturki o kilka procent).
- Jak szukać błędów w programach wielowątkowych.
Wymagania
Będziemy pisać w C++, więc należy znać ten język. Starczy jednak znajomość bardzo podstawowa (jeśli umiesz rozwiązać zadania kwalifikacyjne to jest OK) i zupełnie nie trzeba wiedzieć niczego o wielowątkowości w C++.
Zadania kwalifikacyjne
Nie przestraszcie się tych zadań. Na pewno nie trzeba będzie zrobić wszystkich, aby się zakwalifikować. Rozwiązania częściowe też są dla mnie ciekawe (jeśli nie jesteś pewien, czy to co masz jest rozwiązaniem częściowym to jest). Jeśli jest w nich coś niejasnego, to piszcie (robryk@gmail.com).
Zadanie 1
Napisz program w C++, który:
- wczyta ze standardowego wejścia trzy liczby
- wypisze na standardowe wyjście `TAK` gdy jedna z nich jest dwukrotnością którejś innej, bądź `NIE` w przeciwnym przypadku.
Opis do zadań 2-5
Zadania te polegają na wyobrażeniu sobie, jak działają programy wielowątkowe. W każdym z nich mamy parę programów, które będą się
wykonywać jednocześnie. Przez "wykonywać jednocześnie" rozumiemy, że wykonujemy je po jednej linijce: po wykonaniu każdej linijki wykonujemy kolejną linijkę z tego samego lub drugiego programu.
Przykład
Mamy zmienną globalną X (początkowo 0) i następujące dwa programy:
Program A:
a = X
X = a + 1
Program B:
b = X
X = b + 1
Po ich wykonaniu zmienna X może przyjmować wartość 1 lub 2, w zależności od tego, jak się one podzielą na kawałki.
Jeśli wykonają się w następującej kolejności:
A1 a = X (0)
A2 X = a + 1 (1)
B1 b = X (1)
B2 X = b + 1 (2)
to X będzie miał na końcu wartość 2. Jeśli natomiast wykonają się w takiej kolejności:
A1 a = X (0)
B1 b = X (0)
B2 X = b + 1 (1)
A2 X = a + 1 (1)
to X będzie miał na końcu wartość 1.
Zadanie 2
Mamy dwie zmienne globalne: X i Y. Początkowo obie są równe 0. Mamy następujące dwa programy:
Program A:
Y = 1
print("A:" X)
Program B:
X = 1
print("B:" Y)
Co te programy mogą wypisać, jeśli uruchomimy je oba na raz (możesz zignorować kolejność linijek na wyjściu)? Dla każdej z czterech możliwości uzasadnij, czemu może lub nie może ona nastąpić.
Zadanie 3
Często w programach wielowątkowych nie chcemy, żeby pewne dwie rzeczy mogły dziać się na raz. To i kolejne zadania dotyczą (być może błędnych) sposobów powodowania tego.
Mamy dwie zmienne globalne: Chce0 i Chce1, początkowo równe 0. Mamy następujące dwa programy:
Program 0:
Chce0 = 1
loop forever
if Chce1 == 0 break
print("foo0")
print("bar0")
Chce0 = 0
Program 1:
Chce1 = 1
loop forever
if Chce0 == 0 break
print("foo1")
print("bar1")
Chce1 = 0
- Czy może się zdarzyć, że w wyniku ich działania zostanie wypisane "foo0 foo1 bar0 bar1"?
- Czy może się zdarzyć, że wynikiem ich działania może być coś innego niż wypisanie "foo0 bar0 foo1 bar1" lub "foo1 bar1 foo0 bar0"?
Swoje odpowiedzi krótko uzasadnij.
Zadanie 4
Mamy jedną zmienną globalną: Kto, początkowo równą 0. Mamy dwa programy:
Program 0:
loop forever
if Kto == 0 break
print("foo0")
print("bar0")
Kto = 1
Program 1:
loop forever
if Kto == 1 break
print("foo1")
print("bar1")
Kto = 0
- Czy może się zdarzyć, że w wyniku ich działania zostanie wypisane "foo0 foo1 bar0 bar1"?
- Czy może się zdarzyć, że wynikiem ich działania może być coś innego niż wypisanie "foo0 bar0 foo1 bar1" lub "foo1 bar1 foo0 bar0"?
Swoje odpowiedzi krótko uzasadnij.
Zadanie 5[1]
Mamy trzy zmienne globalne: Kto, Chce0, Chce1, początkowo wszystkie równe 0. Mamy dwa programy:
Program 0:
Chce0 = 1
loop forever
if Kto == 0 LUB Chce1 == 0 break
Kto = 0
print("foo0")
print("bar0")
Chce0 = 0
Kto = 1
Program 1:
Chce1 = 1
loop forever
if Kto == 1 LUB Chce0 == 0 break
Kto = 1
print("foo1")
print("bar1")
Chce1 = 0
Kto = 0
Czy może się zdarzyć, że w wyniku ich działania zostanie wypisane "foo0 foo1 bar0 bar1"?
Swoją odpowiedź uzasadnij.
Dodatkowe informacje
Jeśli jakichś chcesz, to napisz (mail: robryk@gmail.com).
Footnotes
- ^ To zadanie jest istotnie trudniejsze. Na pewno nie będzie ono konieczne do zakwalifikowania się na warsztaty.