Programowanie współbieżne i rozproszone/PWR Ćwiczenia Linda

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Zasoby dwóch typów

Zadanie to pochodzi z książki Z.Weiss, T.Gruźlewski Programowanie współbieżne i rozproszone.

W systemie znajdują się dwa typy nierozróżnialnych zasobów A i B. Jest egzemplarzy zasobu A oraz N>0 egzemplarzy zasobu B. W takim systemie działają trzy grupy procesów. Procesy z grupy pierwszej cyklicznie wykonują własne sprawy, po czym żądają jednego egzemplarza zasobu A, w razie potrzeby czekając aż będzie on dostępny. Procesy z drugiej grupy żądają jednego egzemplarza zasobu A ale jeśli nie jest on dostępny czekają na zasób dowolny. Procesy z trzeciej grupy żądają jednego egzemplarza dowolnego zasobu, ale nie czekają, jeśli żaden nie jest dostępny. Zapisz treść poszczególnych procesów w Lindzie.

Rozwiązanie pierwsze

Załóżmy, że początkowo w przestrzenie krotek znajduje się egzemplarzy krotki postaci ('A') i egzemplarzy krotki ('B'). Procesy grupy pierwszej muszą dostać zasób A, zabierają więc z przestrzeni jeden egzemplarz krotki ('A'). Po skorzystaniu z zasobu, krotka jest oddawana do przestrzeni. Spróbuj zapisać proces pierwszej grupy.

Treść procesu grupy pierwszej

Procesy drugiej grupy chcą otrzymać dowolny zasób preferując jednak A. Spróbuj zapisać proces drugiej grupy.

Proces grupy drugiej

Procesy grupy trzeciej działają bardzo podobnie do procesów grupy drugiej z tym, że pobieranie z przestrzeni krotek jest nieblokujące.

Treść procesu grupy trzeciej

Rozwiązanie drugie

Rozwiązanie drugie polega na umieszczeniu w przestrzeni krotek postaci:

  • ('A', wolnychA), gdzie wolnychA jest liczbą aktualnie dostępnych zasobów typu A
  • ('B', wolnychB), gdzie wolnychB jest liczbą aktualnie dostępnych zasobów typu B




W razie potrzeby możesz rozbudować powyższe krotki o dodatkowe elementy.

Synchronizacja grupowa

Treść tego zadania przedstawimy w formie anegdoty. Z zespołu boisk korzysta drużyn. Każda drużyna składa się z zawodników, przy czym zawodnik jest na stałe przypisany do konkretnej drużyny. Każdy zawodnik cyklicznie (tj. w pętli nieskończonej):

  • załatwia własne sprawy,
  • udaje się na boisko,
  • oczekuje aż zbierze się jego drużyna,
  • oczekuje aż zbierze się jakaś inna drużyna,
  • rozgrywa mecz.

Po przyjściu na boisko zawodnik oczekuje na przyjście wszystkich zawodników z jego drużyny oraz na skompletowanie się innej drużyny. Gdy tylko są dwie kompletne drużyny rozpoczyna się mecz. Każdy zawodnich z tych drużyn wywołuje wówczas predefiniowaną procedurę mecz (z_kim: 1..N), gdzie z_kim jest numerem drużyny przeciwnej. Zawodnik może w każdej chwili zejść z boiska (zakończyć wykonanie procedury mecz). Pozostali zawodnicy kontynuują wówczas grę, nawet jeśli na boisku pozostanie tylko jeden zawodnik. Zawodnik, który zakończył grę nie może jednak wrócić na boisko, tzn. aby ponownie rozpocząć mecz musi najpierw poczekać aż ponownie zbiorą się wszyscy gracze jego drużyny oraz pewna drużyna przeciwna. Zakładamy, że boisk jest co najmniej . Zapisz w Lindzie treść procesu Zawodnik (dr: 1..N)

Sortowanie

Zapisz w Lindzie algorytm sortowania liczb naturalnych. Załóż, że początkowo proces Inicjator umieszcza w przestrzeni ponumerowanych liczb naturalnych, korzystając z predefiniowanej funkcji losuj przekazującej w wyniku liczby naturalne z przedziału [1,n]. Sortowanie wykonywane jest przez procesów, z których każdy w kolejnym cyklu dokonuje jednego porównania i w razie potrzeby zamienia ich kolejność.