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

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 $M>0$ 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ę $M$ egzemplarzy krotki postaci ('A') i $N$ 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

process grupa1;
begin
  while true do
  begin
    wlasne_sprawy;
    input('A')
    korzystaj('A');
    output('A')
  end
end;

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

Proces grupy drugiej

Narzuca się następujące rozwiązanie. Proces próbuje pobrać A. Jeśli mu się to nie uda (funkcja try_input da w wyniku fałsz), to zasobu A nie ma i trzeba wziąć B

process grupa2;
var
  jaki: char;
begin
  while true do 
  begin
    wlasne_sprawy;
    if try_input('A') then
      jaki := 'A'
    else
    begin 
      input('B');
      jaki := 'B'
    end; 
    korzystaj(jaki);
    output(jaki)
  end
end;

Nie jest to jednak dobre rozwiązanie. Po tym, jak proces sprawdzi, że nie ma zasobów A, inny proces może taki zasób oddać. Jeśli ponadto nie ma już dostępnych zasobów B, to proces będzie czekał na B mając dostępny zasób A!

W prawidłowym rozwiązaniu proces po upewnieniu się, że nie ma dla niego zasobu A powinien oczekiwać na dostępność dowolnego zasobu:

process grupa2;
var
  jaki: char;
begin
  while true do 
  begin
    wlasne_sprawy;
    if try_input('A') then
      jaki := 'A'
    else 
      input(jaki: char);
    korzystaj(jaki);
    output(jaki)
  end
end;

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

<show>

process grupa3;
var 
  jaki: zasob;
begin
  while true do 
  begin
    wlasne_sprawy;
    if try_input('B') then 
    begin
       korzystaj('B');
       output ('B')
    end
    else if try_input(jaki: char) then
    begin
      korzystaj(jaki);
      output(jaki)
    end else
      praca_bez_zasobu
  end
end;

</show>

Rozwiązanie drugie

Rozwiązanie drugie polega na umieszczeniu w przestrzeni krotek jedynie dwóch krotek:

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

Spróbuj zapisać treści procesów przy takich założeniach. 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 $N>0$ drużyn. Każda drużyna składa się z $K>1$ 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 $\lceil N/2\rceil$. Zapisz w Lindzie treść procesu Zawodnik (dr: 1..N)

Sortowanie

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