Patryk Czarnik

Laboratorium Programowania Współbieżnego - program zaliczeniowy

1. Opis rozwiązania.

Rozwiązanie jest zgodne ze specyfikacją zadania. Krata NxN procesów realizuje wyspecyfikowany algorytm ewolucyjny, komunikując się między sobą jednym z trzech mechanizmów komunikacji: kolejkami FIFO, kolejkami komunikatów IPC lub za pomocą segmentów pamięci dzielonej IPC.
Pierwszy proces utworzy kratę, wyśle komunikat koordynujący działania, i gdy dowie się, że wszystkie kanały są już utworzone, rozpocznie pracę zgodnie z algorytmem. Po wykonaniu zadanej liczby powtórzeń pierwszy proces wyśle komunikat mówiący o zakończeniu pracy. Procesy kraty, które otrzymają taki komunikat prześlą go dalej, zamkną otwarte kanały i usuną kanały, z których czytały, a następnie zakończą pracę. Proces pierwszy poczeka, aż komunikat dojdzie do niego, zaczeka na zakończenie procesów kraty, wypisze wynik i też się skończy.

1.1 Algorytm.

Algorytm jest taki jak w specyfikacji zadania. Optymalnym genotypem jest genotyp, który na parzystych pozycjach ma zera, a na nieparzystych jedynki. Funkcja przystosowania zwraca różnicę między liczbą prawidłowo ustawionych pozycji a liczbą pozycji nieprawidłowych, lub jeden gdy ta różnica nie jest dodatnia. Prawdopodobieństwo mutacji jest stałą ustawianą w pliku geny.h.

1.2 Komunikacja abstrakcyjnie.

Funkcje do komunikacji między procesami są zadeklarowane w pliku komunikacja.h, a zdefiniowane, w zależności od używanych mechanizmów, w plikach: kom_fifo.c, kom_msg.c, kom_shm.c.

Komunikacja odbywa się za pomocą "kanałów komunikacyjnych", proces korzystający z nich identyfikuje je i ma do nich dostęp za pomocą zmiennych typu Kanal. Kanały są pojęciem abstrakcyjnym, umożliwiającym napisanie programu korzystającego z biblioteki komunikacja.h bez wiedzy o tym, który z mechanizmów komunikacji zostanie akurat użyty.
Kanał służy do jednokierunkowej komunikacji między procesami, działa jak jednoelementowy bufor, blokując czytanie z pustego i potencjalnie pisanie do pełnego. "Jednoelementowy" nie oznacza "jednobajtowy", ale to, że jednorazowo można do niego zapisać jedną porcję danych o rozmiarze podanym w momencie zapisywania, a następnie ta porcja musi zostać (jednorazowo, w całości) odczytana, aby znowu można było zapisywać. Proces odczytujący musi znać rozmiar porcji danych, którą chce przeczytać. Kolejne porcje mogą mieć różne rozmiary, nie większe od maksymalnego, podanego przy otwieraniu kanału. Przesyłane mogą być różne dane, jedna porcja musi znajdować się w spójnym obszarze pamięci, którego cztery pierwsze bajty nie są częścią przesyłanych danych i mogą być zmieniane przez funkcje komunikacji. Proces czytający z kanału musi mieć miejsce na przyjęcie danych, także z czterema bajtami na początku, które nie będą częścią odczytanych danych. Wynika to z implementacji biblioteki (konkretnie msg).
Aby proces mógł korzystać z kanału, musi w zmiennej typu Kanal ustawić pole klucz na dodatnią długą liczbę całkowitą jednoznacznie określającą kanał, do którego chce mieć dostęp. Z tak ustawioną zmienną wywołać funkcję otworz_do_czytania/otworz_do_pisania. Pisze się funkcją pisz, czyta funkcją czytaj. Gdy proces nie będzie już używał kanału, powinien wywołać funkcję zwolnij, a gdy wszystkie procesy zwolnią dany kanał, jeden z procesów powinien wywołać usun.
Wszystkie funkcje są typu void, w przypadku błędu do grupy procesów zostaje wysłany sygnał SIGINT (zmieniłem err.c).

1.3 Komunikacja - fifo.

W tej implementacji każdy kanał komunikacyjny jest łączem nazwanym. W skład nazwy łącza wchodzi klucz i na tej podstawie łącza są rozróżniane. Otwieranie kanału polega na stworzeniu nowego łącza nazwanego jeśli go jeszcze nie ma, a następnie otwarcia go w sposób blokujący do odczytu lub zapisu. Po otwarciu w polu id1 struktury Kanal zapamiętywany jest numer deskryptora, pod którym proces ma otwarte to łącze. Pisanie to normalne pisanie do łącza określonej liczby bajtów, czytanie odbywa się w sposób blokujący, także jeśli łącze jest puste, czytelnik czeka na pisarza. Możliwe jest tu natomiast zapisanie kilku porcji bez czekania na czytelnika.
Funkcja zwolnij zamyka otwarte łącze, natomiast usun usuwa łącze z systemu.

1.3 Komunikacja - kolejki komunikatów IPC.

W tej implementacji każdy kanał jest kolejką komunikatów. Klucz jest kluczem IPC, dla różnych kluczy otwarte zostaną różne kolejki. Pole id1 struktury Kanal będzie zawierało identyfikator kolejki. Obie funkcje otwierające łącze wywołują funkcję msgget z opcją IPC_CREAT. Pisanie polega na wysłaniu komunikatu do kolejki, czytanie na pobraniu komunikatu. Jako parametr funkcji msgsnd i msgrcv podaje się zrzutowały odpowiednio wskaźnik do początku obszaru pamięci z/do którego czyta/pisze się. Ponieważ cztery pierwsze bajty traktowane są jako typ komunikatu, pierwsze cztery bajty przesyłanych danych nie powinny zawierać właściwych danych (zostaną zamazane). Także w tym rozwiązaniu możliwe jest zapisanie większej liczby porcji danych w sposób nie blokujący. Niewykorzystywane są tu fakt, że komunikacja nie musi tutaj być jednokierunkowa, oraz dodatkowe możliwości, jakie dają typy komunikatów.
Funkcja zwolnij nie robi nic, a funkcja usun usuwa kolejkę z systemu.

1.4 Komunikacja - pamięć dzielona.

Tutaj na kanał komunikacyjny składają się blok pamięci dzielonej i zestaw dwóch semaforów. Klucz jest kluczem IPC. Otwieranie polega na stworzeniu, jeśli nie ma, i uzyskaniu dostępu do tych zasobów funkcjami shmget i semget z opcją IPC_CREAT. To tutaj do otwarcia kanału niezbędna jest (przynajmniej w takiej implementacji) informacja o maksymalnym rozmiarze porcji danych. W id1 i id2 będą odpowiednio zapamiętane identyfikatory pamięci i semaforów. Następnie funkcją shmat pobierany jest wskaźnik do segmentu pamięci dzielonej i zapamiętywany w polu pamiec struktury Kanal. Przy otwieraniu do pisania dodatkowo inicjowane są semafory. Jako pierwszy działać będzie mógł pisarz (producent). Pisanie to przepisywanie danych z podanego obszaru pamięci do segmentu pamięci dzielonej i odpowiednia operacja na semaforach. Czytanie to przepisywanie z segmentu pamięci dzielonej do miejsca przeznaczenia i także operacja na semaforach. Semafory pełnią tutaj rolę semaforów z klasycznego rozwiązania problemu producent-konsument dla jednoelementowego bufora.
W tej implementacji blokujące jest zarówno czytanie, jak i pisanie, operacje te muszą być wykonywane na przemian. Segment pamięci dzielonej wykorzystywany jest jako bufor między dwoma procesami. Procesy nie operują na tej pamięci, nie mają do niej dostępu, jedynie funkcje pisz i czytaj z niej korzystają. Przesłanie danych między dwoma procesami wymaga dwukrotnego kopiowania. Tymczasem procesy, mając wspólny dostęp do pamięci, mogłyby to uczynić w jednym kopiowaniu. Jednak program używający pamięci dzielonej różniłby się wtedy bardzo od programów używających kolejek FIFO bądź IPC, nie dałoby się wyabstrahować pojęcia kanału, jak to ma miejsce w rozwiązaniu z dwukrotnym kopiowaniem, dlatego zdecydowałem się na takie rozwiązanie.
Funkcja zwolnij odłącza segment pamięci dzielonej (shmdt), a usun usuwa z systemu segment i zbiór semaforów.

2. Kompilacja i używanie programu.

Kompilację należy przeprowadzić, w zależności od wybranego mechanizmu komunikacji, jednym z poleceń:
make fifo
make msg
make shm.

Zmiana mechanizmu komunikacji nie wymaga ponownej kompilacji tekstu programów, a jedynie dołączenia innego pliku .o w czasie "linkowania".

Po skompilowaniu dostępne są dwa pliki wykonywalne: pierwszy i krata. Aby uruchomić program, należy wywołać pierwszy z następującymi parametrami:
rozmiar kraty (liczba procesów na jednym boku),
długość genotypu,
liczba powtórzeń.

3. Testy.

Aby ocenić efektywność różnych mechanizmów komunikacji, przeprowadziłem serię testów. Testowany był program w wersji takiej, jak przesłana jako rozwiązanie zadania, z pełnym algorytmem ewolucyjnym. Mierzony był czas wykonania głównej pętli w pierwszym procesie (a więc bez inicjalizacji i zamykania kanałów). Testy przeprowadziłem na jednym z komputerów w Lab 6, bez uruchomionych innych programów (co jednak nie gwarantuje, że komputer poświęcał cały czas na mój program). Dla każdych parametrów wykonałem trzy pomiary i podaję ich średnią, czas jest podany w mikrosekundach.

4. Analiza.

Należy zwrócić uwagę na to, że sama praca algorytmu ewolucyjnego daje narzut czasu pracy liniowy w stosunku do długości genotypu, więc liniowy wzrost czasu wraz ze wzrostem długości genotypu nie musi świadczyć o tym, że przesyłanie komunikatów jest liniowe względem ich rozmiaru. Na podstawie tych wyników nie da się, moim zdaniem, ocenić funkcjonowania komunikacji dla różnych rozmiarów danych, można jedynie porównywać między sobą różne mechanizmy komunikacji dla różnych parametrów.

Od razu rzucają się w oczy najgorsze wyniki dla segmentów pamięci dzielonej. Wraz ze wzrostem długości genotypu wyniki te są jednak proporcjonalnie coraz bliższe dwóm pozostałym mechanizmom. Może to świadczyć o wysokim koszcie operacji na semaforach, lub wynikać z liniowego narzutu na algorytm ewolucyjny.
Ten wynik nie świadczy, moim zdaniem, o tym, że segmenty pamięci dzielonej z synchronizacją za pomocą semaforów, są złym mechanizmem komunikacji. Jak już napisałem w opisie rozwiązania, dla segmentów pamięci dzielonej da się zapisać algorytm (także ten z kratą procesów) bardziej efektywnie, jednak cały program musiałby być napisany z myślą o tym konkretnym mechanizmie komunikacji. W skrócie wyglądałoby to tak, że każdy proces miałby bezpośredni dostęp do segmentów wspólnych dla niego i jego sąsiadów, a przepisywanie byłoby jednoczesne z mutacją genotypu - wymagałoby to tylko jednego kopiowania pamięci, co na pewno znacznie obniżyłoby koszt czasowy. Jednak trudno takie rozwiązanie zapisać tak, aby proces mógł wykonywać tylko abstrakcyjne funkcje komunikacji, takie same jak dla FIFO i MSG.
Segmenty pamięci dzielonej znacznie lepiej nadają się do innych problemów, kiedy różne procesy rzeczywiście operują na wspólnej pamięci (coś na kształt monitorów?) i nie jest konieczne ciągłe kopiowanie pamięci.

Z dwóch pozostałych mechanizmów komunikacji, które w naturalny sposób nadają się do przesyłania danych między procesami, łącza nazwane są znacznie szybsze dla krótkich komunikatów, natomiast dla coraz dłuższych coraz lepsze są kolejki komunikatów IPC, które przy długości rzędu 1000 bajtów uzyskują już przewagę nad kolejkami FIFO. Należy jednak pamiętać, że maksymalną długością komunikatu w kolejkach IPC jest (ok.) 4000 bajtów, a więc stosunkowo niewiele ponad owe 1000. Poza tym w systemie Linux można mieć otwartych co najwyżej 128 różnych kolejek (co i tak stanowi znaczne rozszerzenie w stosunku do standardu Systemu V).

5. Podsumowanie.

Wydaje mi się, że do takiego zadania, w którym komunikacja następuje zawsze między dwoma procesami i tylko w jedną stronę, najlepiej użyć kolejek FIFO. Rozwiązanie takie jest najbardziej efektywne dla krótkich komunikatów, a niewiele ustępuje w przypadku rozmiarów rzędu 1000 bajtów, umożliwia natomiast stworzenie większej liczby połączeń niż mechanizmy IPC i przesyłanie dłuższych komunikatów. Jest także rozwiązaniem bardziej uniwersalnym, gdyż łącza nazwane są standardowym mechanizmem UNIXa, w odróżnieniu od mechanizmów IPC, które na ogół są dostępne, ale w różnych systemach różne są ich możliwości (w szczególności ilość zasobów, które można zająć).
Kolejki IPC nadają się lepiej do komunikacji między wieloma procesami, a nie tylko parami. Mogą pełnić rolę zbliżoną do przestrzeni krotek w Lindzie, umożliwiać adresowanie komunikatów do konkretnych procesów lub odczytanie niekoniecznie pierwszego komunikatu z kolejki (typy komunikatów).
Segmenty pamięci dzielonej natomiast są najlepsze w sytuacji, gdy wiele procesów operuje na wspólnych danych, ale dane te nie są kopiowane do lokalnej pamięci poszczególnych procesów.