- Teoria Wielowątkowości (multithreading theory)
- Wątki (threads) - Test
- Współdzielenie danych (data_sharing) - Test
- Zmienne warunku (condition_variable) - Test
- Zmienne atomowe i model pamięci (atomic) - Test
- Jednokrotne wywołania (call_once) - Test
- Komunikacja jednokierunkowa (future, promise) - Test
- Zadania asynchroniczne (async, packaged_task) - Test
- Problemy współbieżności ----------------┐
- Współbieżne wzorce projektowe ---------┼- Test z 08, 09, 10
- Testowanie programów współbieżnych ---┘
Ankieta oceniająca trenera - Mateusz Adamski
- 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
- (2 punkty za poziom) Zagraj w The Deadlock Empire i przejdź wszystkie poziomy :D Screenshot zaliczonych poziomów posłuży za dowód
(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)
(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.
(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/
(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
(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)
(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
(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
(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:
-
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.
-
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.
(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 kilkukrotnystd::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 ustawiachosen = true
.
MEGA PODPOWIEDŹ: Pracuj w TDD i używaj Thread Sanitizera :)
(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ń
SUMA | Punktualność | P1 | P2 | Z1 | Z2 | Z3 | Z4 | Z5 | Z6 | Z7 | Z8 | Z9 | Testy | Inne | |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Adam | 0 | ||||||||||||||
Adam Mierzwiak | 38 | 38 | |||||||||||||
Cypher | 52 | 38 | 14 | ||||||||||||
Hikarina | 38 | 38 | |||||||||||||
jzych | 0 | ||||||||||||||
kamil waszkiewicz | 0 | ||||||||||||||
kawapa | 38 | 38 | |||||||||||||
Krzysiek | 0 | ||||||||||||||
matijaz | 0 | ||||||||||||||
mkijew | 0 | ||||||||||||||
MonikaZ | 38 | 38 | |||||||||||||
piotr.kowandy | 38 | 38 | |||||||||||||
RyszardH | 38 | 38 | |||||||||||||
Szafirmag | 0 |
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 + ? |
- 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 :)
Spotkanie na zakończenie z rozdaniem dyplomów i nagród odbędzie się w kwietniu. Dokładną datę podam później.
- Wypełnij ankietę zadowolenia z kursu
- Obserwuj Coders School na LinkedInie
- Polub Coders School na Facebooku
- Jeśli uważasz, że odwalam dobrą robotę to skrobnij parę słów na ten temat na FB, niech się niesie w świat ;)
- Zachęcam też do potwierdzenia moich umiejętności i wystawienia mi rekomendacji na LinkedInie. Mogę odwdzięczyć się tym samym :)
- Zapisz się na newsletter, jeśli chcesz otrzymywać informacje o przyszłych kursach.