Projekt 2: Algorytm wzajemnego wykluczania

• Termin oddania 9.05 / 16.05
• Przekroczenie terminu skutkuje obniżeniem oceny: 0.1 * liczba_dni_spoźnienia
• Zadanie do przygotowania w oparciu o bibliotekę MPJ Express.
• Warunek konieczny - sprawozdanie w formie papierowej
• Maksymalna ilość kodu w sprawozdaniu - pół strony

Projekt polega na zaprojektowaniu oraz implementacji rozproszonego algorytmu wzajemnego wykluczania. Należy przygotować program demonstrujący działanie algorytmu w środowisku MPJ Express - dla zdefiniowanej liczby procesów n ubiegających się o dostęp do sekcji krytycznej (w sposób losowy).

Algorytm będzie oceniany pod kątem poprawności (patrz punkt 2 sprawozdania), wydajności (patrz punk 1 sprawozdania), odporności na awarie procesów (rozwiązania rozproszone preferowane nad scentralizowane). [usunąłem: odporności na błędy procesów.]

Należy przygotować conajmniej dwa poziomy szczegółowości logów. Pierwszy powinien wypisywać jedynie komunikaty:

• P <id> want's to enter CS,
• P <id> enters CS,
• P <id> leaves CS,

natomiast drugi (i pozostałe) zawierać dokładniejsze informacje, np. o wiadomościach wysyłanych przez algorytm.

W sprawozdaniu należy zawrzeć:

1. Opis algorytmu

   • Opis złożoności pakietowej oraz czasowej algorytmu. Tzn. ilu rozesłanych pakietów wymaga algorytm, by dopuścić/zwolnić proces do sekcji krytycznej; po ilu krokach algorytmu proces zostanie dopuszczony/zwolni do sekcji krytycznej. Jeżeli jest to konieczne, podane złożoności powinny być zależne od liczby procesów współbieżnie ubiegających się o wejści do sekcji krytycznej.

2. Wykazanie poprawności algorytmu, z uwzględnieniem własności (jeżeli algorytm takie spełnia):

   • bezpieczeństwa (safety),
   • postępu (liveness),
   • sprawiedliwości (fairness).

3. Wnioski i możliwe ulepszenia

Parametry symulacji (opóźnienia oraz zakresy wartości losowych) można dobrać samodzielnie, byle były sensowne, a wyniki interpretowalne. Symulacja może być przeprowadzona w konfiguracji multi core