Wielowątkowość i współbieżność w C++

Tematy

1. Teoria Wielowątkowości (multithreading theory)
2. Wątki (threads) - Test
3. Współdzielenie danych (data_sharing) - Test
4. Zmienne warunku (condition_variable) - Test
5. Zmienne atomowe i model pamięci (atomic) - Test
6. Jednokrotne wywołania (call_once) - Test
7. Komunikacja jednokierunkowa (future, promise) - Test
8. Zadania asynchroniczne (async, packaged_task) - Test
9. Problemy współbieżności ----------------┐
10. Współbieżne wzorce projektowe ---------┼- Test z 08, 09, 10
11. Testowanie programów współbieżnych ---┘

Ankieta oceniająca trenera - Mateusz Adamski

Nagrania

Nagrania z poprzedniej edycji

• 30.03.2019 - Teoria wielowątkowości, wątki, współdzielenie danych
• 06.04-2019 - Współdzielenie danych, promise/future, atomic
• 13.04.2019 - Zmienna warunku, jednokrotne wywołania, zadania asynchroniczne

Prace domowe

Zadanie 1

• (2 punkty za poziom) Zagraj w The Deadlock Empire i przejdź wszystkie poziomy :D Screenshot zaliczonych poziomów posłuży za dowód

Zadanie 2

(11 punktów, 1 za każdy podpunkt) Termin: 22.02.2020 23:59

Napisz równoległą wersję algorytmu std::accumulate, który będzie współbieżnie sumował fragmenty kontenera. Wyniki powinny zostać również zapisane w kontenerze.

• on empty returns init
• calculate number of threads - hardware_threads = hardware_concurrency() 0 ? hardware_concurrency() : 2
• divide on blocks according to the number of threads
• create vector of results
• run every thread in parallel
• put results in vector element passed by reference (threads cannot return value)
• join threads
• accumulate results from the result vector
• test on 1M elements and compare with standard std::accumulate
• compare with std::par execution policy in std::accumulate from C++17 ;)
• templatize algorithm on Iterator (depends on container) and type T sually int, double)

Podpowiedź

Rozwiązanie znajdziesz w książce *C++ Concurrency in Action, Anthony Williams*, listing 2.8. [Link do mojego rozwiązania opartego na ww](https://github.com/coders-school/multithreading/blob/solutions/homework/02_parallel_accumulate.cpp)

Zadanie 3

(20 punktów) Termin: 22.02.2020 23:59

Napisz współbieżną wersję algorytmu std::count_if. Zmierz czas działania i napisz testy, pokazujące, że zwraca ona takie same wyniki, jak std::count_if.

Zadanie 4

(24 punkty, 4 za każdy podpunkt) Termin: 29.02.2020 23:59

Zaimplementuj problem ucztujących filozofów z użyciem wątków i mutexów.

• Każdy filozof ma być kontrolowany przez oddzielny wątek.
• Każdy sztuciec ma być chroniony przez 1 mutex
• Postaraj się o wizualizację problemu na konsoli (np. F1- F2 -F3- F4 | F5 | oznacza, że filozof F3 ma oba sztućce, a F1 tylko jeden)
• Strzeż się zakleszczeń
• Pobaw się liczbą filozofów i zobacz czy zmienia się zachowanie programu. Opisz to w komendarzu
• Zadanie dodatkowe: Strzeż się zagłodzenia (starvation). Jest to sytuacja w której przynajmniej 1 wątek z powodu implementacji lub swojego niższego priorytetu nigdy nie dostanie wszystkich wymaganych zasobów. Doimplementuj w tym celu pewien mechanizm, który zapobiegnie zagłodzeniu.

Podpowiedź

https://mariusbancila.ro/blog/2017/01/16/dining-philosophers-in-cpp11/

https://mariusbancila.ro/blog/2017/01/20/dining-philosophers-in-c11-chandy-misra-algorithm/

Zadanie 5

(10 punktów) Termin: 29.02.2020 23:59

• Poszukaj informacji na temat zjawiska nazywanego fałszywym współdzielenim (false sharing). Jest to bardzo niemiłe zjawisko, wynikające z architektury współczesnych komputerów, które znacząco spowalnia równoległe wykonywanie programów.
• Napisz/przepisz/skopiuj sobie kawałek kodu, który ma ten problem i zmierz czas działania programu w zależności od wielkości danych wejściowych i liczby wątków
• Napraw problem false sharingu i zmierz czas działania programu również przy różnej wielkości danych wejściowych i liczbie wątków
• Wyciągnij i opisz w komentarzu wnioski jak pisać kod odporny na false sharing :)

Podpowiedź

Możesz spróbować zaimplementować algorytm std::fill

Zadanie 6

(20 punktów, 4 za każdy zrealizowany podpunkt) Termin: 07.03.2020 23:59

Zaimplementuj grę w ping-ponga (zadanie 03_ping_pong.cpp z rozdziału o zmiennych warunku)

• 1 wątek wypisuje "ping" oraz kolejny numer
• 2 wątek wypisuje "pong" oraz kolejny numer
• Zaczyna wątek ping, a kończy zawsze pong. Wątki muszą pracować na przemian. Nie mogą być 2 pingi lub pongi po sobie. Program nie może zakończyć się pingiem, na który nie będzie odpowiedzi – ponga.
• Zakończenie działania programu ma nastąpić albo po wykonanej liczbie odbić albo po limicie czasowym, w zależności które wystąpi pierwsze. Powód zakończenia powinien zostać wyświetlony na ekranie
• Parametry programu:
  • liczba odbić
  • limit czasowy (w sekundach)

Zadanie 7

(15 punktów, 3 za każde zadanie) Termin: 07.03.2020 23:59

Rozwiąż zadania z użyciem promise i future od Ihora z katalogu 07_future_promise/homework

Zadanie 8

(20 punktów) Termin: 07.03.2020 23:59

Tak jak w zadaniu 2 - napisz równoległą wersję algorytmu std::accumulate, który będzie współbieżnie sumował fragmenty kontenera, ale użyj w tym celu zadań asynchronicznych

Zadanie 9 - Przetwarzanie obrazów

(36 punktów, 18 za każdy podpunkt) Termin: 21.03.2020 23:59

Zainstaluj sobie bibliotekę OpenCV - Instrukcja instalacji

Przerób algorytmy podane w dokumentacji na ich wielowątkowe wersje:

1. Wykrywanie wzorców.

   Każdy wątek sprawdza inny wzorzec. Możemy jednocześnie szukać kilku rzeczy na obrazku. Na koniec wyświetl na obrazku miejsca, gdzie wybrane wzorce najbardziej pasowały. Jeden wzorzec może występować w kilku miejscach.

2. Wykrywanie linii.

   Każdy wątek szuka linii pod innym kątem. Musisz stworzyć odpowiednie maski. Na koniec wyświetl na obrazku znalezione linie - każdy kąt innym kolorem. Możesz też dodać wyszukiwanie okręgów.

---

Projekt 1: Hardkorowi filozofowie

(68 punktów, 4 za każde wymaganie) Termin: 21.03.2020 23:59

Zaimplementuj trochę inną wersję algorytmu ucztujących filozofów. Polecam pracę w grupie.

• Chłop zadaje ważne egzystencjalnie pytanie 5 filozofom (wprowadź je z klawiatury)

• Każdy filozof posiada gotowy zestaw 10 odpowiedzi (każdy filozof ma inne odpowiedzi)

• Każdy filozof podczas myślenia ma zaimplementowany inny algorytm obliczający pewne wartości

• Algorytmy filozofów jako parametr wejściowy przyjmują pytanie (std::string) oraz odpowiedź (std::string) i zwracają liczbę int. Jeśli nie masz pomysłu na różne algorytmy oblicz kilkukrotny std::hash z zestawu pytanie + odpowiedź.

• Wszyscy filozofowie podczas myślenia korzystają także z bardzo mądrej księgi, która stanowi dla nich inspirację. Wielu filozofów może odczytywać księge jednocześnie. Wartości zapisane w księdze także mogą być brane pod uwagę w algorytmie.

• Każdy filozof musi przemyśleć każdą z 10 swoich odpowiedzi, która stanowi parametr wejściowy do jego algorytmu myślenia.

• Zadania do przemyślenia przez filozofów możesz zaimplementować jako pulę wątków (Thread Pool).

• Każdy filozof, aby przemyśleć pojednynczą odpowiedź musi być najedzony. Nie może więc rozpocząć myślenia bez jedzenia.

• Każdy filozof potrzebuje 2 sztućców, aby móc się najeść. Liczba szućców jest równa liczbie filozofów.

• Każdy filozof po przemyśleniu odpowiedzi zapisuje swoje rozważania w księdze. Tylko 1 filozof na raz może zapisywać rozważania i żaden inny nie może tym momencie korzystać z księgi.

• Przemyślenia w księdze mają następujący format:

  struct {
      string philosopher,
      string answer,
      int result,
      chrono::duration period,
      bool chosen = false,
  }

• Żaden filozof nie może się przejeść. Po posiłku musi on poczekać 3 sekundy zanim zacznie kolejny posiłek.

• Jeśli filozof nie jadł przez 20 sekund to umiera śmiercią głodą. Nie dopuść do tego!

• W czasie poszukiwania odpowiedzi, możesz usypiać filozofów. W tym celu musisz z klawiatury podać odpowiednią komendę w czasie działania programu (np. sleep Platon).

• Uśpiony filozof nie może myśleć ani jeść. Umiera on z głodu dopiero po 60 sekundach.

• Uśpionego filozofa można obudzić podając odpowiednią komendę z klawiatury (np. wakeup Platon).

• Na koniec każdy filozof odczytuje odpowiedź która została przez niego wybrana (oblicza max z działań result * period). W tym celu musi odczytać księgę, gdyż tam zapisał swoje rozważania. Przy wybranej odpowiedzi ustawia chosen = true.

MEGA PODPOWIEDŹ: Pracuj w TDD i używaj Thread Sanitizera :)

Projekt 2: Wielowątkowy raytracer

(40 punktów) Termin: 21.03.2020 23:59

Czym jest ray tracing? - wideo na YT Rozwiń algorytm śledzenia promieni, implementując jego współbieżną wersję, która wygeneruje jakąś statyczną scenę i zapisze ją w jako obrazek (najlepiej użyj sceny chessboard). Możesz wykorzystać ten kod.

• Zaimplementuj współbieżną wersję istniejącego algorytmu
• Podziel obraz na różne sposoby pomiędzy wiele zadań asynchronicznych
  • użyj async, future, promise i/lub packaged_task
• Zbadaj szybkość przetwarzania w zależności od rodzaju podziału (użyj std::chrono)
  • podział na wiersze
  • podział na kolumny
  • podział na prostokąty
• Zbadaj szybkość przetwarzania w zależności od liczby współbieżnych zadań

Organizacja

Tabela wyników

	SUMA	Punktualność	P1	P2	Z1	Z2	Z3	Z4	Z5	Z6	Z7	Z8	Z9	Testy	Inne
Adam	0
Adam Mierzwiak	48				38	10
Cypher	74	5			38	11	20
Hikarina	38				38
Jakub Zych	71	5			38	10	18
kamil waszkiewicz	38				38
kawapa	71	5			38	10	18
Krzysiek	41	5			10	10	16
matijaz	38				38
mkijew	74	5			38	11	20
MonikaZ	69	5			38	10	16
piotr.kowandy	43				38	8
RyszardH	38				38
Szafirmag	71	5			38	10	18

Punktacja

Kolumna	Max. punktów	Czynność
Punktualność	55	5 punktów za każde zadanie i projekt dostarczone przed wskazanym terminem
P1	68	Projekt 1 - Hardkorowi filozofowie
P2	40	Projekt 2 - Ray Tracing
Z1	38	Zadanie 1 - The Dragon Empire
Z2	11	Zadanie 2 - współbieżny std::accumulate
Z3	20	Zadanie 3 - współbieżny std::count_if
Z4	24	Zadanie 4 - problem ucztujących filozofów
Z5	10	Zadanie 5 - false sharing
Z6	20	Zadanie 6 - ping pong
Z7	15	Zadanie 7 - future i promise
Z8	20	Zadanie 8 - std::accumulate na zadaniach asynchronicznych
Z9	36	Zadanie 9 - przetwarzanie obrazów
Testy	24	3 punkty za każdy rozwiązany test
Inne	?	Inne nie przewidziane aktywności, np. zrobienie lub wrzucenie czegoś wartościowego, zrobienie Code Review innym osobom
RAZEM	381 + ?

Nagrody

• 0 punktów - notes z długopisem
• 60 punktów - zaślepka na kamerkę
• 120 punktów - certyfikat na zakończenie kursu
• 200 punktów - zniżka 50% na dowolny przyszły kurs w Coders School^*
• 260 punktów - książka Anthony Williams, C++ Concurrency in Action
• 325 punktów - kurs online w Coders School za darmo^* :)

^* _{wymaganymi dodatkowymi "kosztami" w przypadku zniżki lub darmowego kursu będzie: a) pay by tweet or share - udostępnienie informacji o kursie na swoich mediach społecznościowych, b) opinia o kursie z Wielowątkowości na Facebooku (lub LinkedInie w przypadku braku FB, ewentualnie po prostu mail z opinią i pozwoleniem na opublikowanie go na naszej stronie) Sorki, ale umiem w social media i liczę na to, że jakoś pomożecie mi dotrzeć do większej liczby zainteresowanych :)}

Zakończenie

Spotkanie na zakończenie z rozdaniem dyplomów i nagród odbędzie się w kwietniu. Dokładną datę podam później.

1. Wypełnij ankietę zadowolenia z kursu
2. Obserwuj Coders School na LinkedInie
3. Polub Coders School na Facebooku
4. Jeśli uważasz, że odwalam dobrą robotę to skrobnij parę słów na ten temat na FB, niech się niesie w świat ;)
5. Zachęcam też do potwierdzenia moich umiejętności i wystawienia mi rekomendacji na LinkedInie. Mogę odwdzięczyć się tym samym :)
6. Zapisz się na newsletter, jeśli chcesz otrzymywać informacje o przyszłych kursach.