report.md

Gildia Złodziei - Sprawozdanie

Autorzy

• 106593 - Szczepański Adam
• 106596 - Czajka Mateusz

Algorytm

Dla każdego procesu złodzieja możemy wyodrębnić 3 następujące po sobie czynności:

• dobór złodziei w pary
• papierkowa robota (przydzielenie domu)
• rabunek domu arystokracji

Stałe

P - liczba miejsc w urzędzie
Z - liczba złodziei
D - liczba domów

Dobór w pary

Z procesów może przebywać w sekcji krytycznej doboru parnetów. Procesy utrzymują kolejkę FIFO związaną z tą czynnością. W momencie trafienia na kolejkę proces z nieparzystą pozycją i na kolejce rozpoczyna nasłuchiwanie na wiadomość od procesu który trafi na nią z pozycją i + 1. Procesy które trafią na kolejkę z pozycją i + 1 wysyłają wymienioną wyżej wiadomość.

Papierkowa robota

2*floor(P/2) procesów może dokonywać papierkowej roboty w urzędzie (sekcja krytyczna). Wykorzystana jest ta sama kolejka co przy doborze w pary - nie ma potrzeby wysyłania dodatkowych komunikatów. Po zakończeniu dokumentowania proces z nieparzystą pozycją w kolejce wysyła komunikat o opuszczeniu sekcji krytycznej i oba procesy są usuwane z kolejki.

Rabowanie domu

Po przydzieleniu domu proces o nieparzystej pozycji w porzedniej kolejce ubiega się o dostęp do konkretnego domu - każdy dom to odzielna sekcja krytyczna (D kolejek). W sekcji krytycznej może przebywać tylko jeden proces jako, że dany dom może być rabowany tylko przez jedną parę złodzieji. Po rabunku dany dom jest oznaczony przez pewien czas jako niedostępny.

Algorytm rozwiązania

Założenia przyjętego modelu komunikacji

• asynchroniczny system z wymianą komunikatów
• topologia połączeń każdy z każdym
• kanały komunikacyjne typu FIFO

Omówienie algorytmu

Główna pętla

while (!koniec) {
  komunikacja();
  konkretny_stan();
  zwolnienie_zasobow();
}

Stany

1. Partnership_insert

• broadcast do pozostałych procesów z tagiem REQUEST_TAG (chęć wejście na kolejkę partnerów).
• rozpoczęcie nasłuchiwania na zgodę na wejście na ww. kolejkę CONFIRM_TAG
• przejście do stanu Partnership_wait_for_confirm

2. Partnership_wait_for_confirm

• sprawdzenie czy przyszła zgoda od wszytkich złodziei
• przejście do stanu Partnership_wait_for_top

3. Partnership_wait_for_top

• synchronizacja
• przejście do stanu Partnership_critical_section

5. Partnership_critical_section

• jeśli pozycja w kolejce jest nieparzysta
  • nasłuchuj na partnera, tag PARTNER_TAG
  • przejdź do stanu Partnership_wait_for_partner
• jeśli pozycja w kolejce jest parzysta
  • zapisz id złodzieja poprzedzającego w kolejce
  • przejdź do stanu Partnership_notify_partner

6. Partnership_wait_for_partner

• sprawdzaj aż nie przyjdzie wiadomość od partnera
• przejdź do stanu Docs_wait_for_top

7. Partnership_notify_partner

• powiadom partnera: tag PARTNER_TAG
• przejdź do stanu Docs_start_waiting_for_partner

8. Docs_wait_for_top

• oczekuj na wejście do sekcji krytycznej
• przejdź do stanu Docs_critical_section

9. Docs_critical_section

• po upływie czasu potrzebnego na wypełnienie dokumentów przejdź do stanu Partnership_release

10. Partnership_release

• wyślij do pozostałych złodziei informację o zwolnieniu pozycji w kolejce: tag RELEASE_TAG
• poinformuj partnera, że papierkowa robota jest zakończona, tag PARTNER_TAG
• przejdź do stanu House_start_waiting_for_partner

11. Docs_start_waiting_for_partner

• rozpocznij oczekiwanie na partnera, tag PARTNER_TAG
• przejdź do stanu Docs_wait_for_partner

12. Docs_wait_for_partner

• w momencie otrzymania potwierdzenia od partnera (PARTNER_TAG) przejdź do stanu House_request_entry

13. House_request_entry

• wyślij do wszystkich złodziei informację o chęci wejścia do danego domu, tag: REQUEST_TAG
• rozpocznij oczekiwanie na potwierdzenie ww. wiadomości (CONFIRM_TAG)
• przejdź do stanu House_wait_for_confirm

14. House_wait_for_confirm

• w momencie otrzymania potwierdzenia wejdź do sekcji krytycznej danego domu - przejdź do stanu House_critical_section

15. House_critical_section

• zrabuj dom (oczekuj aż minie określony czas)
• dodaj dom na kolejkę zasobów do zwolnienia (z określonym czasem wygaśnięcia - HOUSE_QUARANTINE_DURATION)
• przejdź do stanu House_notify_partner

16. House_notify_partner

• poinformuj partnera że, kradzież została zakończona (PARTNER_TAG)
• przejdź do stanu Partnership_insert

17. House_start_waiting_for_partner

• rozpocznij nasłuchiwanie na wiadomość o zakończeniu kradzieży (PARTNER_TAG)
• przejdź do stanu House_wait_for_partner

18. House_wait_for_partner

• sprawdzaj czy kradzież została zakończona
• przejdź do stanu Partnership_insert

Złożoność komunikacyjna

Komunikacja pojdeńczego procesu wysyła w czasie jednego cyklu:

Proces który wejdzie na kolejkę partnerów jako nieparzysty

1. wysłanie n-1 REQUEST_TAG - wejście na kolejkę partnerów
2. odbiór n-1 CONFIRM_TAG - zgoda na wejście na kolejkę partnerów
3. odbiór 1 PARTNER_TAG - potwierdzenie przydzielenia patnera
4. wysłanie n-1 RELEASE_TAG - zwolnienie miejsca na kolejce patnerów
5. wysłanie 1 PARTNER_TAG - informacja o zakończeniu wypełniania dokumentów
6. otrzymanie 1 PARTNER_TAG - informacja o zakończeniu kradzieży

Proces który wejdzie na kolejkę partnerów jako nieparzysty

1. wysłanie n-1 REQUEST_TAG - wejście na kolejkę partnerów
2. odbiór n-1 CONFIRM_TAG - zgoda na wejście na kolejkę partnerów
3. wysłanie 1 PARTNER_TAG - potwierdzenie przydzielenia patnera
4. otrzymanie 1 PARTNER_TAG - informacja o zakończeniu wypełniania dokumentów
5. wysłanie n-1 REQUEST_TAG - wejście na kolejkę danego domu
6. otrzymanie n-1 CONFIRM_TAG - zgoda na wejście na kolejkę danego domu
7. wysłanie 1 PARTNER_TAG - informacja o zakończeniu kradzieży

Łącznie dla procesu który wejdzie na kolejkę partnerów jako nieparzysty otrzymujemy 3 * (n-1) + 3 = 3n komunikacji.

Dla procesu który wejdzie na kolejkę partnerów jako parzysty otrzymujemy 4 * (n-1) + 3 = 4n - 1 komunijacji.

Złożoność czasowa

Dla proces który wejdzie na kolejkę partnerów jako nieparzysty złożoność czasowa wynosi 6, natomiast dla dla procesu który wejdzie jako parzysty złożoność czasowa wynosi 7.

Wzajemne wykluczanie

W celu realizacji pierwszej sekcji krytycznej wykorzystany jest algorytm Lamporta, dla drugiej jest to algorytm Ricarta-Agrawalli.

Wnioski

Dzięki wprowadzonym modyfikacjom w stosunku do pierwotnej wersji (połączenie kolejek do doboru partnerów i dokumentacji) udało się znacznie ograniczyć liczbę komunikacji.