Synchronizacja wątków i tworzenie programów równoległych

Przygotowanie do wykonania zadania

Przypomnij sobie wiadomości o programowaniu wątków z wykorzystaniem biblioteki Pthread. W szczególności zapoznaj się z dokumentacją funkcji:

• pthread_mutex_init: inicjuje obiekt mutexu, który służy do synchronizacji dostępu do zasobów współdzielonych.
• pthread_mutex_lock i pthread_mutex_unlock: blokują i odblokowują mutex, aby zapewnić ekskluzywny dostęp do chronionego obszaru kodu.

Przypomnij sobie również czym jest sekcja krytyczna, do czego służy muteks i semafor. Następnie zapoznaj się z dokumentacją funkcji:

• pthread_cond_init, która służy do inicjalizacji zmiennej warunkowej
• pthread_cond_wait, która służy do oczekiwania na sygnał na zmiennej warunkowej
• pthread_cond_signal, która służy do wysyłania sygnału na zmiennej warunkowej do jednego z wątków oczekujących na tej samej zmiennej warunkowej. Po otrzymaniu sygnału, wątek, który oczekiwał na zmiennej warunkowej (pthread_cond_wait), zostaje wznowiony

Zadania do wykonania

Zad.1. (1 punkt - na zajęciach) Operacje ze stosem

• Przejrzyj, skompiluj i uruchom program bug2.c.
• Co się dzieje? Dlaczego? Jak to naprawić?
• Dla porównania uruchom program bug2fix.c.

Zad.2. (3 punkty - na zajęciach) Zmienne warunkowe

(a) Przejrzyj, skompiluj i uruchom program condvar.c. Obserwuj wyjścia trzech wątków.

(b) Teraz przejrzyj, skompiluj i uruchom program bug1.c. Obserwuj wyjścia pięciu wątków. Co się dzieje? Czy potrafisz wyjaśnić dlaczego? Jak naprawić problem?

(c) Program bug4.c to kolejny przykład tego, co może pójść źle przy użyciu zmiennych warunkowych. Przejrzyj go, skompiluj i uruchom. Zaobserwuj wyjście i spróbuj naprawić program.

Zad.3. (6 punktów - na zajęciach, lub 3 punkty - w domu)

Książe Dipontelini zmarł podczas polowania na jelenie w pobliskim lasku. Książe miał wielu synów (N) - bardzo zachłannych młodzieńców. Jego włości stanowią X * Y działek, na których znajdują się cenne zasoby, zwierzyna, wioski oraz zamki. Każdy z synów pragnie zawładnąć największą liczbą terenów. Rejent Sir Vivaldini ma niemałą zagwostkę jak pogodzić zwaśnionych synów.

Stwórz symulację tej sytuacji zachowując następujące zasady:

• istnieje jeden wątek Rejent oraz N wątków Syn
• każdy Syn ma dokładnie S szans na zdobycie terytorium - losuje w tym celu współrzędne miejsca w tablicy terytoriów: jeśli miejsce jest wolne zajmuje je, jeśli miejsce jest zajęte, traci tą szansę
• kiedy wątek wykorzysta S szans wysyła sygnał (zmienna warunkowa) do Rejenta, który blokuje tablicę i zlicza liczbę terytoriów zdobytych przez syna i wypisuje zdobycze syna na ekranie
• kiedy wszyscy synowie skończą działanie wątek Rejent zlicza ile terytoriów nie zostało zajętych i wypisuje tę informację na tablicy

Przetestuj rozwiązanie na różnych zestawach danych N, X, Y oraz S.
Dla sensownego testowania te wartości powinny spełniać warunek N*S==X*Y (ale w programie nie można nic takiego zakładać).
W raporcie podaj przykładowe wyniki dla trzech wybranych zestawów danych.

UWAGA: do wygenerowania wartości losowej można wykorzystać funkcję drand48(), która ma lepsze własności niż podstawowa funkcja rand(). Przed użyciem każdej z tych funkcji konieczne jest zainicjowanie generatora liczb losowych wartością przypadkową, tzw. ziarnem. Jako wartości przypadkowej można użyć aktualnego czasu w sekundach (time()), numeru bieżącego procesu (getpid()), lub kombinacji tych wartości, albo jeszcze jakiejś innej funkcji.