Opis zadania

Celem zadania jest przeprowadzenie eksperymentów z programem współbieżnym. Pretekstem będzie budowa programu do przeprowadzania licytacji. Pojawia się pewna liczba uczestników licytacji, którzy składają oferty na wybrane przedmioty.

Parametry licytacji:
N_AGENTS=20 /* liczba uczestników */
N_ITEMS=20 /* liczba przedmiotów */
OPENING_BID=100 /* początkowa cena każdego przedmiotu */
MAX_RAISE=10 /* maksymalna wartość podbicia */
BIDDING_ROUNDS=1000000 /* liczba podbić wykonana przez każdego uczestnika */

Te wartości powinny być parametrami programu, to znaczy w programie powinny pojawiać się w postaci zmiennych (lub stałych symbolicznych), a nie konkretnych wartości liczbowych. W każdej chwili chcemy mieć możliwość zmiany danego parametru na inną wartość w nagłówku zadania, i po przekompilowaniu programu uruchomienia go ze zmienionymi parametrami.

Dodatkowo proszę zaimplementować możliwość, aby parametry BIDDING_ROUNDS, N_AGENTS, oraz N_ITEMS można było zadawać w argumentach wywołania programu (drugi argument funkcji main). To znaczy, jeśli w wywołaniu programu nie pojawią się żadne argumenty, to należy przyjąć wartości podane wyżej. Jeśli pojawi się jeden argument numeryczny, to należy przyjąć go jako wartość parametru BIDDING_ROUNDS (zamiast wartości domyślnej podanej wyżej). Jeśli ponadto pojawi się jeszcze drugi argument numeryczny, to należy przyjąć go jako wartość parametru N_AGENTS (liczba agentów licytujących). Trzeci argument wywołania - jeśli się pojawi - będzie przyjęty jako parametr N_ITEMS (liczba licytowanych towarów).

W trakcie uruchamiania zadania warto zawsze w pierwszym uruchomieniu zadać niewielką liczbę rund licytowania BIDDING_ROUNDS aby mieć pewność, że program wykona się szybko i nie wyświetli za dużo wyników. Po upewnieniu się, że program działa dobrze dla małej liczby rund licytowania, wykonujemy test zasadniczy z właściwą wartością tego parametru.

Przygotowanie do zajęć

Generacja liczb losowych

Istotnym elementem zadania będzie generacja liczb losowych. Do generacji liczb pseudolosowych na systemach uniksowych można użyć podstawowej funkcji rand, która generuje liczby nieujemne w pewnym zakresie. Do celów zadania potrzebna będzie liczba w zakresie 0..N-1, więc należy użyć operatora %

Aby uzyskać przypadkową sekwencję pseudolosową generator musi być zainicjalizowany funkcją srand. Tej funkcji należy dostarczyć jako argumentu jakąś przypadkową wartość aby uzyskać unikalną pseudolosową sekwencję. W internecie można znaleźć wiele przykładów wykorzystania do tego celu bieżącego czasu w sekundach (funkcja time). Jednak w tym zadaniu byłaby to zasadnicza pomyłka. Wiele procesów będzie tu uruchamianych (prawie) jednocześnie, i jeśli wszystkie one zainicjalizują swoje generatory liczb losowych aktualną liczbą sekund, to wszystkie zaczną generować tę samą sekwencję pseudolosową. W tym zadaniu o wiele lepszym sposobem inicjalizacji generatora liczb losowych będzie numer bieżącego procesu (funkcja getpid).

Generator liczb pseudolosowych implementowany przez funkcję rand ma słabe własności stochastyczne, i jeśli ktoś chciałby sprawdzić lepszą metodę, może zamiast niej użyć funkcji drand48. Do jej zainicjalizowania można użyć jednej z funkcji: srand48, seed48, lub lcong48.

Z punktu widzenia wykonania zadania nie ma znaczenia której z funkcji rand/drand48 użyjemy - poprawne użycie każdego z tych generatorów będzie akceptowalne.

Użycie pamięci współdzielonej

Niezbędny w zadaniu obszar pamięci wspólnej można stworzyć zgodnie ze standardem System V IPC funkcją shmget, co następnie wymaga włączenia jej do przestrzeni adresowej procesu funkcją shmat.

Alternatywnie, można użyć interfejsu pamięci wspólnej POSIX Realtime. W tym standardzie obszar pamięci wspólnej tworzony jest funkcją shm_open i istnieje on jako plik specjalny. Ten plik należy zainicjować na odpowiedni rozmiar funkcją ftruncate i następnie zmapować do przestrzeni pamięci procesu funkcją mmap.

Przykłady konfiguracji i użycia pamięci wspólnej w obu tych modelach były przedstawione na wykładzie. Pewne problemy mogą wynikać z powodu globalnego i trwałego istnienia utworzonych segmentów pamięci wspólnej w systemie, tworzenie tych segmentów przez wielu użytkowników (możliwe kolizje tworzonych identyfikatorów), i wielokrotne uruchamianie programów. Należy po pierwsze zapewnić sobie użycie unikalnej nazwy tworzonego segmentu pamięci wspólnej. W standardzie System V IPC pomocna do tego jest funkcja ftok tworząca unikalny klucz identyfikacyjny na podstawie nazwy pliku. Wykorzystując w tym celu np. plik bieżącego programu wykonywalnego, można mieć pewność uzyskania unikalnego klucza:

key_t shmkey = ftok(argv[0], 2);

Drugi argument funkcji ftok zwany numerem projektu pozwala uzyskać wiele różnych unikalnych kluczy dla tego samego pliku. Jest to przydatne przy tworzeniu kolejnych wersji programu (1,2,3,4,5,6) kompilowanych do tej samej nazwy pliku a.out.

Ponadto, ważne jest, by program na zakończenie pracy kasował utworzony segment pamięci wspólnej. Jeśli tego nie zrobi, to przy ponownym uruchomieniu próba utworzenia tego segmentu może napotkać błąd.

Obsługa błędów

W tym programie bardzo ważna będzie obsługa błędów w wywoływanych funkcjach systemowych. Jeśli funkcja zostanie wywołana, i wygeneruje ona błąd niefatalny, to funkcja normalnie wróci sygnalizując wystąpienie tego błędu przez swoją wartość. Na przykład, jeśli taki błąd powstanie w funkcji shmget tworzenia segmentu pamięci, to ten segment nie zostanie utworzony. Jeśli program nie zwróci na to uwagi, i pójdzie dalej tak jakby funkcja zadziałała poprawnie, to prawie na pewno wygeneruje błąd fatalny gdzieś dalej. Typowo będzie to błąd naruszenia pamięci (np. operacji na segmencie pamięci, którego nie ma) w instrukcji która sama w sobie jest poprawna, a błąd wynika z wcześniejszego błędu funkcji systemowej.

Dlatego jest bardzo wskazane, aby wszystkie wywołania funkcji systemowych obudować instrukcjami warunkowymi sprawdzającymi poprawność ich wykonania. W przypadku zwrócenia przez funkcję wartości wskazującej na błąd najlepszym rozwiązaniem jest natychmiastowe zatrzymanie programu, według schematu:

id = shmget(shmkey, sizeof(struct Wspolna), IPC_CREAT|0600);
if (id<0) {
  perror("shmget");
  exit(-1);
}
ptr=shmat(id,0,0);
if ((long int)ptr==-1) {
  perror("shmat");
  exit(-1);
}

Funkcja perror wyświetla komunikat zawierający PRZYCZYNĘ dla której powstał błąd i funkcja nie wykonała swojego zadania. Ten komunikat nie zawiera jednak nazwy funkcji (bo podobne błędy mogą powstawać w wielu różnych funkcjach, i komunikaty są współdzielone), zatem typowym rozwiązaniem jest wywoływanie funkcji perror z nazwą testowanej funkcji jako argumentem. Funkcja exit powoduje natychmiastowe zatrzymanie całego procesu. Jej argument określa status zakończonego procesu, i każda wartość różna od zera jest interpretowana jako zakończenie niepoprawne.

Pomiar czasu rzeczywistego i CPU

W dalszych częściach zadania potrzebne będzie mierzenie czasu wykonania całego programu, i to zarówno czasu rzeczywistego, jak i czasu CPU. Do odczytu aktualnego czasu rzeczywistego proszę wykorzystać funkcję clock_gettime z zegarem (pierwszy argument) CLOCK_REALTIME. Do pomiaru czasu CPU najlepiej wykorzystać funkcję times, która ma jednak szereg szczególnych własności. Na przykład, mierzy ona czas w specjalnych jednostkach tikach, które należy przeliczyć na sekundy wykorzystując parametr konfiguracyjny sysconf(_SC_CLK_TCK).

Funkcja times jest szczególnie przydatna, ponieważ dostarcza ona również sumarycznych czasów CPU wykonania ZAKOŃCZONYCH JUŻ potomków procesu bieżącego, a właśnie potomki procesu głównego będą w tym programie wykonywały zasadniczą pracę (milion operacji podbić licytacji), podczas gdy proces główny nie będzie nic robił, poza inicjalizacją struktur, uruchomieniem potomków i podsumowaniem wyników.

Wszystkie pomierzone czasy należy wyświetlać w sekundach z rozsądnie zaokrągloną częścią ułamkową (np. trzy cyfry znaczące).

Zastosowanie semafora do ochrony sekcji krytycznej

W dalszych krokach ćwiczenia potrzebne będzie zastosowanie semafora i wykorzystanie funkcji sem_post i sem_wait do ochrony całego globalnego obszaru danych przed niepoprawnym dostępem przez podprocesy.

Semafor należy utworzyć w obszarze pamięci wspólnej, i przed użyciem zainicjalizować go funkcją sem_init.

Wykonanie ćwiczenia

W kolejnych krokach zadania tworzone będą kolejne wersje programu. Aby rozpocząć pracę nad następnym krokiem zadania, przekopiuj ostatnią wersję uruchomioną i przetestowaną w poprzednim kroku. Zachowaj i nie zmieniaj przetestowanych wersji z wszystkich kroków. Będą potrzebne do: porównania z innymi wersjami, zademonstrowania prowadzącemu, a wersje z punktów 3, 4, 5, i 6 trzeba będzie również oddzielnie wysłać na zaliczenie zadania.

1. Generacja podbić licytacji

Proszę napisać program licytuj1.c, który najpierw zainicjalizuje ceny wszystkich przedmiotów w tablicy ofert o nazwie Bids typu long int na podaną wartość (OPENING_BID), a następnie wygeneruje zadaną liczbę BIDDING_ROUNDS podbić licytacji. W każdym kroku program wybierze losowo jeden z przedmiotów licytacji, jak również wygeneruje losową wartość podbicia licytacji w przedziale 0..MAX_RAISE, po czym zwiększy ofertę na ten przedmiot w tablicy Bids o tę wartość podbicia, a także zinkrementuje licznik podbić wybranego przedmiotu w tablicy NBids.

Po zakończeniu licytacji należy wyświetlić wyniki w postaci wartości ofert końcowych na wszystkie przedmioty, oraz ich sumy (która powinna być równa sumie cen początkowych plus sumie wszystkich wygenerowanych podbić) i sumarycznej liczby podbić wszystkich przedmiotów.

Obie tablice Bids i NBids wykorzystywane w tej części zadania powinny być zwykłymi zmiennymi lokalnymi funkcji main. W terminologii ANSI C są to tzw. zmienne automatic.

2. Użycie pamięci współdzielonej

W drugim kroku należy napisać program licytuj2.c, który utworzy obszar pamięci wspólnej o odpowiednim rozmiarze, i umieści w niej obie tablice wyników (Bids i NBids). W tym celu należy zadeklarować w programie strukturę zawierającą obie te tablice, ale tylko jako typ, bez przydziału pamięci. Po utworzeniu segmentu pamięci współdzielonej, i odwzorowaniu jej do przestrzeni adresowej procesu, powstanie w procesie blok pamięci na tę strukturę i zawarte w niej tablice, dostępne przez wskaźnik do pamięci wspólnej. Taki schemat można znaleźć na stronach 21 i 21 PDF-u z wykładu na temat komunikacji międzyprocesowej.

Wynikiem powinien być program działający identycznie jak w poprzednim kroku, tylko wykorzystujący obszar pamięci wspólnej, zamiast zwykłej tablicy w zmiennej lokalnej.

3. Współbieżność wieloprocesowa

Następnie napisz wieloprocesowy program licytuj3.c. Zadaniem procesu głównego będzie tylko utworzenie podprocesów reprezentujących agentów licytujących. Podprocesy agentów będą się zajmowały tylko licytowaniem zgodnie z wersją licytuj2.c. Wszystkie wyniki będą od razu zapisywane do tablic Bids i NBids w pamięci współdzielonej, i wszystkie procesy powinny indywidualnie uzyskiwać dostęp do tego obszaru pamięci wspólnej.

Proces główny po wygenerowaniu wszystkich podprocesów powinien przejść do oczekiwania na zakończenie ich wszystkich wywołując odpowiednią liczbę razy funkcję wait. Po zakończeniu wszystkich podprocesów proces główny powinien ruszyć dalej, i wyświetlić sumaryczne wyniki licytacji.

Po starannym zdebugowaniu programu przeprowadź z nim szereg eksperymentów, obserwując otrzymane wyniki (porównanie sumy końcowych wartości ofert na wszystkie przedmioty z sumą ofert wygenerowaną przez agentów). W razie potrzeby tymczasowo zmniejsz liczbę rund licytacji (parametru BIDDING_ROUNDS, np. do 1000 albo nawet do 100), i/lub liczbę agentów (parametr N_AGENTS np. do 5). Ponieważ liczba agentów oznacza liczbę równolegle pracujących podprocesów, można tę liczbę skoordynować z liczbą fizycznych procesorów lub rdzeni obliczeniowych używanego komputera. Mniejsza liczba agentów niż liczba procesorów może skutkować rzeczywiście fizycznie równoległym wykonaniem procesów, podczas gdy liczba agentów większa niż liczba fizycznych procesorów gwarantuje, że podprocesy nie będą wykonywane naprawdę równolegle (ale będą wykonywane quasi-równolegle).

Należy się spodziewać, że przy równoczesnej pracy wielu procesów, i wielu rundach jednoczesnego licytowania wystąpi wiele razy zjawisko wyścigów, i łączna suma podbić licytacji zarejestrowanych przez procesy nie będzie równa sumie osiągniętych wartości. Proszę odnotować wynik tego porównania w raporcie. W razie potrzeby należy zwiększyć liczbę rund licytowania. Można też uruchomić program na innym systemie.

UWAGA: jeśli wyścigi nie występują i suma ofert zgadza się, to może oznaczać, że program został uruchomiony na komputerze nie posiadającym żadnej sprzętowej współbieżności, albo że został źle napisany (szeregowa a nie równoległa praca podprocesów). Przy dostatecznie długiej serii, nawet przy braku współbieżności sprzętowej powinny pojawić się wyścigi.

4. Pomiar czasów wykonania

Ponieważ w kolejnych punktach zadania istotny stanie się czas wykonywania programu, chcemy dodać pomiar czasu: zarówno czasu rzeczywistego jak i czasu wirtualnego (CPU). Proszę napisać kolejny program licytuj4.c, który zmierzy czas fazy licytowania towarów. Ponieważ program główny w tym zadaniu robi bardzo niewiele, a rzeczywistą pracę wykonują jego potomki, należy obliczyć i podać łączny czas CPU dla wszystkich potomków (po ich zakończeniu i odczytaniu ich statusów przez proces główny funkcją wait/waitpid).

W raporcie proszę podać uzyskane czasy pracy tego programu (CPU i RT). Czasy proszę podać w prawidłowo przeskalowanych jednostkach (sekundy lub milisekundy), rozsądnie zaokrąglone (2-3 cyfry znaczące).

5. Ochrona sekcji krytycznej semaforem

Aby rozwiązać problem wyścigów występujących przy równoczesnym dostępie do pamięci i wynikających z nich błędów w obliczaniu wartości ofert napisz kolejny program licytuj5.c, wprowadzając semafor chroniący cały globalny obszar danych (funkcje sem_wait i sem_post). Po wprowadzeniu ochrony sekcji krytycznej programu (rejestracja podbić licytacji w tablicy w obszarze pamięci wspólnej) proszę przeprowadzić serię eksperymentów, żeby upewnić się, że obliczanie ofert działa teraz poprawnie (brak wyścigów, czyli zgodność sumy podbić licytacji obliczonych przez agentów z sumą wartości zarejestrowanych w globalnej tablicy Bids).

W raporcie proszę odnotować, czy zarejestrowana suma ofert była tym razem poprawna, czyli zgodna z liczbą ofert złożonych. Proszę również podać czasy wykonywania tej wersji programu, porównać ją z wersją poprzednią, i wyjaśnić różnice. W przypadku, gdyby czas wzrósł dramatycznie, można roboczo zmniejszyć liczbę ofert składanych przez uczestnika (np. do 100000). Jednak dla celów pomiaru i porównania czasów działania programu do raportu proszę zastosować zadaną liczbę ofert.

6. Użycie wielu semaforów

Usprawnieniem przyspieszającym poprawne liczenie ofert będzie utworzenie oddzielnych semaforów dla poszczególnych przedmiotów. Dzięki temu każdy semafor chroni tylko licznik i wartość pojedynczego przedmiotu, zatem oferty różnych przedmiotów mogą być podbijane równolegle. Należy stworzyć kolejną wersję programu licytuj6.c, i ponownie przeprowadzić z nią eksperymenty: potwierdzenie poprawności obliczania ocen, oraz pomiar czasów. Głównie interesuje nas teraz skrócenie czasu rzeczywistego RT, ale w raporcie proszę porównać również czasy CPU.

Praca na zajęciach - I termin

Minimalny wynik: w pełni uruchomiony i przetestowany program licytuj1.c (2 punkty).

Pożądany wynik: w pełni uruchomiony i przetestowany program licytuj2.c (+1 punkt).

Uwaga: przed przystąpieniem do realizacji II terminu zajęć program licytuj2.c musi być do końca uruchomiony i przetestowany. W przypadku problemów z pełnym uruchomieniem tego programu w domu, proszę o pilny kontakt z prowadzącym na konsultacjach przed terminem kolejnych zajęć.

Praca na zajęciach - II termin

Minimalny wynik: w pełni uruchomiony i przetestowany program licytuj3.c (2 punkty). Konieczne jest powtarzalne uzyskiwanie wyścigów (niezgodności sum wylicytowanych wartości obliczonych przez podprocesu i proces główny).

Pożądany wynik: w pełni uruchomiony i przetestowany program licytuj4.c (+1 punkt).

Uwaga: w przypadku niepowodzenia uruchomienia programu licytuj4.c ćwiczenie można kontynuować na kolejnych zajęciach (III termin) wykorzystując wersję licytuj3.c i mierząc czasy RT i CPU na potrzeby opracowania raportu programem time.

Praca na zajęciach - III termin

Minimalny wynik: w pełni uruchomiony i przetestowany program licytuj5 (2 punkty).

Pożądany wynik: w pełni uruchomiony i przetestowany program licytuj6 (+1 punkt).

Raport

Raport z wykonania zadania, wysłany jednorazowo po jego zakończeniu całego zadania powinien zawierać podsumowanie uzyskanych wyników i/lub uwagi na temat ewentualnych problemów.

Pomiary czasów wykonania ostatnich trzech wersji programu (z wyścigami, z pojedynczym semaforem, i z wieloma semaforami) należy przeprowadzić dla właściwych wartości parametrów podanych na początku zadania. Jedynie gdy czasy wykonania wersji z pojedynczym semaforem okazałby się niepraktyczny (więcej niż 10 minut), można odpowiednio zmniejszyć liczbę tur licytowania (BIDDING_ROUNDS).

W przypadku niemożności uruchomienia wersji licytuj4.c czasy wykonania programu można zmierzyć zewnętrznym programem time (tylko w celu porównania, brak punktów za takie rozwiązanie).

W raporcie z wykonania zadania proszę porównać czasy wykonania (CPU+RT) ostatnich trzech programów (licytuj3 lub licytuj4 oraz licytuj5 i licytuj6). Czasy proszę podać w prawidłowych jednostkach (sekundy lub milisekundy), rozsądnie zaokrąglone (2-3 cyfry znaczące). Jakie wnioski można wyciągnąć z tego porównania?

Przykładowa literatura:
1. Posługiwanie się pamięcią współdzieloną: https://beej.us/guide/bgipc/html/multi/shm.html
https://wazniak.mimuw.edu.pl/images/7/72/Sop11lab.pdf
2. Pomiar czasów wirtualnych (CPU) procesów: https://pubs.opengroup.org/onlinepubs/9699919799/functions/times.html
3. Wykorzystanie muteksów do realizacji blokad wyłączności: https://docs.oracle.com/cd/E19455-01/806-5257/6je9h032p/index.html