Pojedynczy read i write

Rozwiązania, w których zamiana odbywa się poprzez pojedyncze wykonanie operacji write i read, miały być błędne. Chciałem, aby niezbędne było pisanie i czytanie w pętli. Niestety, podałem tak małą wielkość tablicy z danymi, że to jednak działa (FIFO jest wystarczająco pojemne).

Liczba IPC proporcjonalna do wielkości macierzy

Przy ograniczeniu do N=10 można sobie pozwolić na używanie N kolejek IPC, chociaż w ogólności lepiej gdy liczba kolejek jest ograniczona przez stałą.

Nie blokowanie sygnałów w krytycznych momentach

Poprawne programy powinny blokować obsługę sygnałów na czas wykonywania zmian w globalnych strukturach po to, aby procedura obsługi sygnału zawsze korzystała ze spójnego stanu zmiennych globalnych.

Jednak nie sprawdzałem dokładnie tego warunku, ponieważ wymagałoby to bardzo dokładnej analizy kodu.

Jedna kolejka do poleceń i żetonów/synchronizacji

W czasie gdy dwa węzły wymieniają się danymi, do kolejki może napłynąć dużo poleceń przeznaczonych dla tego węzła, który ma potem zwrócić żeton. Kolejka się przepełni i nie będzie możliwy zwrot żetonu – blokada. Podobnie z komunikatami synchronizacyjnymi – nie mogą iść przez tą samą kolejkę co polecenia.

Błąd ten występował także w rozwiązaniach ze scentralizowanym zarządcą FIFO, gdy wysyłał on komunikaty do węzłów tą samą drogą, co użytkownik polecenia.

Nieatomowe pobieranie dwóch żetonów

Gdy wiele procesów rywalizuje o żetony, pobieranie dwóch osobnych żetonów (przez jednego partnera albo po jednym przez każdego z partnerów) prowadzi do blokady. Jeśli rozwiązanie używa dwóch łącz FIFO do jednej zamiany, jeden żeton powinien reprezentować dwa łącza.

Błąd ten nie zachodzi jeśli żetony pobiera użytkownik / zarządca FIFO.

Pobieranie żetonu przed synchronizacją z partnerem

Jeśli żeton pobiera jeden z węzłów, musi robić to już po zsynchronizowaniu się z partnerem. Pobieranie przed synchronizacją grozi blokadą.

Przykład poleceń:

Z 2 2 3 3
Z 1 1 2 2

Niepoprawny przeplot:

1. uzytkownik czyta polecenia i wstawia do IPC.
2. Polecenie odczytuje najpierw 1 1.
3. 1 1 pobiera żeton i oczekuje na synchronizację z 2 2.
4. Polecenie odczytuje 2 2.
5. 2 2 próbuje pobrać żeton (który posiada 1 1).

Polecenie Zakończ tylko do jednego uczestnika

Jeśli polecenie zamiany przekazywane jest tylko do jednego z uczestników, który sam informuje partnera, może dojść do zmiany kolejności u drugiego uczestnika.

Przykład poleceń:

Z 1 1 3 3
Z 2 2 3 3

Niepoprawny przeplot (3 3 wykonuje zamiany w innej kolejności niż podana na wejściu):

1. uzytkownik czyta polecenia i wstawia do IPC.
2. 2 2 synchronizuje się z 3 3 i wykonuje zamianę.
3. 1 1 synchronizuje się z 3 3 i wykonuje zamianę.

Za mało wait-ów

Bo wykonaniu polecenia zaKończ, zamknięciu wejścia lub wysłaniu sygnałów należało wykonać N² wywołań wait lub wcześniej ustawić ignorowanie śmierci dzieci. Wykonywanie tylko jednego wait powodowało pozostawanie procesów „zombie”, które przy nieskończonej pętli w końcu przepełniały zasoby systemowe.

Problemy z pamięcią

Po co mam robić free, skoro zamknięcie programu i tak zwalnia pamięć?

Choćby po to, żeby wyrobić sobie dobry nawyk i nie robić takich błędów, jakie pojawiły się w kilku rozwiązaniach, gdzie malloc bez free występował wewnątrz pętli, co oczywiście prowadziło do wycieku pamięci. W szczególności takim błędem było alokowanie pamięci w Uruchom i nie zwalnianie w zaKończ (ale mogłem takie błędy przeoczyć :(

Przy zwalnianiu pamięci pojawiały się też błędy double free or corruption spowodowane przez zwalnianie już zwolnionej pamięci albo „przesunięcie” wskaźnika.

Problemy z deskryptorami FIFO

Po co mam robić close, skoro zamknięcie programu i tak zamyka deskryptory?

Jak wyżej, pojawiały się rozwiązania, gdzie deskryptory były otwierane w pętli, co prowadziło do przepełnienia tablicy otwartych deskryptorów. Usuwanie FIFO (unlink) nie zwalnia deskryptora!

Problemy z odczytem i parsowaniem danych

Najelegantsze było chyba czytanie po jednym wierszu fgets-em i parsowanie polecenia sscanf-em. Niepoprawne użycie scanf lub ręczne parsowanie napisu powodowały różne problemy, zwłaszcza w poleceniu Wypełnij.

Użytkownik czeka na żeton

Polecenia inne niż Zamiana mogłyby się odbywać bez oczekiwania na żeton.

Dwa FIFO do zamiany

Stosowanie dwóch łącz FIFO do zamiany jest uzasadnione tylko wtedy, jeśli zwiększa to współbieżność. Jeśli zamiana jest i tak sekwencyjna (najpierw używamy jednego, potem drugiego łącza), równie dobrze (ale oszczędniej) można było użyć jednego.

Wysyłanie sygnałów w pętli

Zamiast pamiętać pidy wszystkich węzłów i wysyłać do nich sygnały w pętli, można wysłać sygnał do grupy procesów.

Niepotrzebny koszt operacji na napisach, funkcja strcat

Zawsze należy brać pod uwagę, że w C większość funkcji na napisach (nawet tak niewinne jak strlen) ma koszt liniowy względem długości napisu. Umieszczanie ich w pętli proporcjonalnej do długości napisu daje koszt kwadratowy.

Powtarzało się takie rozwiązanie wypełniania tablicy napisem:

blok[0] = '\0';
while (rozmiarBloku-strlen(blok) >= strlen(komunikat.napis))
  strcat(blok, komunikat.napis);
strncat(blok, komunikat.napis, rozmiarBloku-strlen(blok));
				

Operacja str(n)cat przegląda cały dotychczas utworzony napis, podobnie jak strlen.

Niezależnie od tej sytuacji i tego zadania funkcja strlen jest nadużywana. Często rozmiar napisu jest stały (BTW, makra w C tylko wklejają kod!), często można raz go policzyć i wielokrotnie używać, zamiast powtarzać wywołania funkcji. Pamiętajcie, że (w C i C++) ma ona koszt liniowy!