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.
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.
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.
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.
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).
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
.
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.
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
.
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.
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.
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).
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.
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.
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ęć.
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
.
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 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