Program watki nalezy wywolac z jednym parametrem - rozmiarem listy (n). Program tworzy liste o rozmiarze n. Kolejne wezly sa przy tym zapisane w spojnej tablicy, ktorej poczatkiem jest pierwszy wezel. Umozliwia to latwiejsza kontrole watkow, ktorych zmienne moga byc dzieki temu zapisane w tej samej strukturze, oraz wypisanie wynikow. Wezel listy zawiera nastepujace pola: int wart; - wartosc wykorzystywana w algorytmie int flaga; - mowi w jakim stanie jest wezel w danej chwili int krok; - mowi ile krokow algorytmu wykonal juz watek skojarzony z tym wezlem pthread_mutex_t mut; - mutex chroniacy zmienne flaga i krok pthread_cond_t czytanie; - tutaj oczekuja watki chcace odczytywac wartosci wezla pthread_cond_t pisanie; - tutaj oczekuja watki chcace zapisywac (moze to byc tylko jeden watek - skojarzony z tym wezlem pthread_t watek; - watek skojarzony z tym wezlem struct sWezel *nast; - nastepny wezel na liscie Kazdy watek po zapisaniu inicjalnej wartosci ustawia krok na 1. flaga moze miec nastepujace wartosci: F_ZAPIS teraz watek moze zmienic wartosci w swoim wezle F_ODCZYT teraz poprzednik moze czytac z tego wezla F_PIERWSZY pierwszy wezel na liscie - nikt nie bedzie z niego czytal F_ZAKONCZONY ostatni wezel na liscie - jego watek juz nie dziala i nie jest modyfikowane pole krok. Oczywiscie utworzenie listy i wypisanie wynikow ma liniowy koszt czasowy (nie twierdze, ze nie da sie tego zrobic lepiej), ale samo policzenie liczby nastepnikow ma dzialac w czasie O(log n) na komputerze o n procesorach. Gdyby synchronizacje zapewnic przy pomocy stalej liczby zasobow (muteksow, ...), i zliczac na jakiejs zmiennej procesy, ktore zakonczyly juz dana faze algorytmu, koszt czasowy stalby sie liniowy, ze wzgledu na wylaczny dostep do tych zasobow dla pojedynczych watkow. Dlatego zdecydowalem sie na rozwiazanie, w ktorym ilosc muteksow i conditionali jest liniowa, a synchronizacja nastepuje tylko miedzy watkami obslugujacymi sasiednie wezly na liscie. Watek nie odczyta wartosci z nastepnika, dopoki nastepnik bedzie w fazie F_ZAPIS lub nie dojdzie do tego samego kroku algorytmu. Jesli nastepnik jest juz zakonczony, jego krok nie bedzie brany pod uwage. Dopoki warunki nie beda spelnione, watek bedzie czekal na zmiennej warunkowej czytanie. Gdy przejdzie warunki albo zostanie obudzony, przeczyta wartosci nastepnika, w sekcji krytycznej zwiazanej z mutexem nastepnika, a nastepnie zmieni jego flage, po czym obudzi watek ewentualnie czekajacy na zapis w nastepniku. Flaga zostaje zmieniona na F_ZAPIS lub F_PIERWSZY, jesli nastepnik bedzie w nastepnym kroku pierwszym wezlem nowej listy (tak jest gdy biezacy wezel jest pierwszy). To, ze sekcja krytyczna nie jest zwalniana na czas odczytu wartosci nie psuje zlozonosci algorytmu, gdyz i tak w jednym kroku z wezla czytaja tylko watek danego wezla (on nie potrzebuje mutexa) oraz poprzednik, ktory wlasnie mutexa posiada. Przed zapisem jest sprawdzane, czy flaga wezla nie jest ustawiona na ODCZYT, nie jest tu sprawdzany krok, gdyz juz w fazie odczytu poprzednik porownal swoj krok z naszym i ewentualnie na nas poczekal. Natomiast "my" nie przejdziemy do fazy zapisu dopoki poprzednik nie odczytal i nie ustawil nam flagi. Zapis obywa sie w sekcji krytycznej zwiazanej z mutexem danego wezla. Po zapisie jest zwiekszany licznik krokow. Flaga zostaje zmieniona na F_ODCZYT, chyba ze nast == NULL, wtedy na F_ZAKONCZONY. Pierwszy wezel na liscie dziala o tyle inaczej, ze nie czeka na to, az poprzednik (ktorego nie ma) cos zrobi. Odczyt wlasnych wartosci (wart, nast, krok) nie musi odbywac sie w sekcji krytycznej, gdyz tylko wlascicel moze modyfikowac te wartosci, a gdy czyta to ich nie modyfikuje :)