SOP121/ćw - temat G

Problemy współbieżności; język BACI.

Mały przykład problemu współbieżności :
mamy zmienną "licznik" dostępną dla dwóch procesów P0 i P1;
początkowa wartość licznika wynosi 0;
procesy P0 i P1 100-krotnie zwiększa licznik o 1 przy pomocy następującego kodu:

licznik:= licznik + 1
  { co po przetłumaczeniu na assembler wygląda mniej więcej tak: }
l1:  ax= licznik
l2:  ax= ax + 1
l3:  licznik= ax

Definicje niektórych pojęć związanych ze współbieżnością :

zasoby krytyczne

Tylko jeden proces może mieć w danej chwili dostęp do danego zasobu krytycznego. Takim zasobem może być np lista elementów znajdująca się w pamięci operacyjnej, na której proces chce dokonywac operacji dodawania/usuwania elementów. Gdyby dwa procesy wykonywały takie operacje równocześnie to lista prawdopodobnie zostałaby uszkodzona (przy niekorzystnym zbiegu okoliczności).

sekcja krytyczna

Jest to fragment kodu, w którym dany proces używa zasobu krytycznego. Tak więc sekcja krytyczna jest zawsze związana z pewnym zasobem krytycznym (zauważmy że dwa procesy mogą równocześnie przebywać w sekcjach krytycznych różnych zasobów).

wzajemne wykluczanie

Mechanizm wzajemnego wykluczania musi zapewniać, że tylko jeden proces może przebywać w sekcji krytycznej związanej z danym zasobem. Zazwyczaj na początku i na końcu sekcji krytycznej dodaje się pewien protokół wstępny i protokół końcowy.

blokada

Inaczej zakleszczenie, deadlock. Wszystkie procesy są wstrzymane w oczekiwaniu na zdarzenie, które mogą spowodować właśnie te procesy.

zagłodzenie

Grupa procesów oczekuje na zdarzenie. Zdarzenie pojawia się wiele ale "nasz" proces nigdy nie jest wybierany. Mówimy o tym procesie, że został zagłodzony.

synchronizacja procesów lub wątków

Jest to wstrzymywanie działania procesu lub wątku aby nie dopuścić do "utraty spójności danych"; np gdy dwa procesy chcą wejść do sekcji krytycznej związanej z pewnym zasobem to jeden z nich musi być "wstrzymywany" tak długo aż drugi proces nie opuści sekcji krytycznej.

Język programowania współbieżnego BACI.

Wszystkie przykłady (pliki *.pm, *.cm i *.inc) jak i oprogramowanie BACI należy skopiować do własnego katalogu i tam wykonywać odpowiednie eksperymenty !

UWAGI od interpretera DOS-owego:
W sciezkach do katalogu nie powinno byc żadnych znaków zakazanych przez DOS.

Sposób kompilowania i uruchamiania:

Uruchomienie kompilatora dla pliku zródłowego "np00.pm":

bapas np00

bainterp np00

Język BACI może służyc do eksperymentów z semaforami i monitorami, ale także do tworzenia nowych "narzędzi" i do eksperymentalnego ich sprawdzania, a to dzięki takim elementom jak: procedury niepodzielne ze słowem kluczowym atomic (które nie mogą być wywłaszczone), funkcje specjalne takie jak: suspend(), revive(), which_proc(). W szczególności można tworzyć własne semafory o zmodyfikowanej definicji.

Język BACI jest bardzo realistycznym symulatorem współbieżnych procesów. Jeśli zachodzi potrzeba przełączenia procesora, to nowy proces jest wybierany drogą losowania, tak więc nie można nic zakładać co do "względnej prędkości" działania procesów. Mówiąc dokładniej, jeśli mamy procesy ProcA i ProcB wykonujące rozkazy A1,A2,A3,  B1,B2,B3 (odpowiednio) to rzeczywista kolejność wykonania tych rozkazów jest dowolna, np: A1,A2,B1,A3,B2,B3 lub A1,B1,B2,A2,A3,B3 (są to tzw "przeploty"; wszystkie przeploty są możliwe).

W języku BACI posługujemy się pojęciem "proces" chociaż bardziej odpowiednie byłoby pojęcie "wątek", gdyż tym słowem posługuje się instrukcja obsługi.

Język BACI (bapas.exe) jest bardzo podobny do uproszczonego języka Pascal.
patrz: dokumentacja !!!
 

Uruchamianie wspólbieżnych procesów:

program np00;

atomic procedure pisz(nr, i:integer);
begin
  writeln( nr, ":", i); i:=i+1;
end;

procedure proc(nr:integer);
var i:integer;
begin
  i:=0;
  while true do
  begin
    pisz(nr, i); i:=i+1;
  end;
end;

begin
  cobegin
    proc(1); 
    proc(2); 
    proc(3);
  coend;
end.

Powyższy kod powoduje uruchomienie 3 współbieżnie działających procesów z których każdy wykonuje pętle wyświetlającą napis nr_procesu:nr_iteracji.

Zadanie 90

Semafory.

Problem pięciu filozofów. Pięciu głodnych filozofów siedzi przy okrągłym stole, przy talerzach z rybą. Aby jeść rybę potrzebne są 2 widelce, jednak między dwoma sąsiednimi filozofami leży tylko 1 widelec. Wszyscy filozofowie na przemian myślą i jedzą (w pętli). Zauważ że wprowadzenie wzajemnego wykluczania dla każdego widelca nie rozwiązuje problemu: może się zdarzyć że wszyscy filozofowie zaczną podnosić widelce począwszy od lewego - wtedy nie beda mogli podnieść prawego widelca - wystąpi tzw blokada ... Druga uwaga: w problemie tym robi się zazwyczaj zalożenie że filozofowie NIE są ponumerowani "po kolei" w kolejności krzeseł przy stole, gdyż w takim wypadku rozwiązanie jest łatwe (można wykorzystać ten numer).

Co należy rozumieć przez rozwiązanie problemu ?
Rozważmy to na przykładzie "problemu pięciu filozofów".
Mamy 5 procesów wykonujących funkcje Filozof():

int Jem[5]; // ta tablica zawiera informacje o tym 
            // który filozof je w danej chwili

void Filozof(int Nr) // Nr=0..4
{
   while(1) {

     // filozof mysli

     Jem[Nr]=1;
     // filozof je
     Jem[Nr]=0;
   }
}

void procesKontrolny()
{
  while(1) {
    cout <<Jem[0]<<Jem[1]<<Jem[2]<<Jem[3]<<Jem[4]<< endl;
  }
}

Jednym z narzędzi do rozwiązywania problemów współbieżności (wynalezionym przez Dijkstrę w 1965) jest semafor.

Definicja semafora ogólnego (wg Ben-Ariego):
Semafor to zmienna całkowita "S", na której można wykonywać następujące (niepodzielne) operacje:

Przykład: sekcja krytyczna chroniona przy pomocy semaforów ...

semaphore sem=1; // semafor ogólny, zainicjowany jedynką

void proc()
{
  while(1) {
    wait(sem); // protokół wstępny
    // 
    // sekcja krytyczna
    // 
    signal(sem); // protokół końcowy
    // 
    // pozostałe czynności
    //
  }
}

main()
{
  cobegin {
    proc(); proc();
  }
}

Zadanie 91

Zadanie 91b

Definicja semafora binarnego:
Semafor binarny to zmienna "S", przyjmująca wartości 0 i 1, na której można wykonywać następujące (niepodzielne) operacje:

Uwaga !!!: w języku BACI jeśli S=1 to signal(S) powoduje błąd! (jest to odstępstwo od tradycyjnej definicji semafora binarnego mające na celu ułatwienie debugowania)

Zasada programowania z użyciem semaforów:  1. Interpretacja wartości semafora powinna być tak dobrana, aby operacje wait() i signal() były dla nas przydatne i wygodne.  2. Interpretacja ta powinna być zapisana w komentarzu obok deklaracji semafora.

 

Poniżej znajdują się zadania dotyczące semaforów.
Nieco trudniejsze zadania będą oznaczone przez (*) i (**).
 

Zadanie 92

1) N=0, Zwloka=0, konsument wychodzi ze swojej sekcji krytycznej
2) producent wykonuje całą swoją sekcje krytyczną (zmieniając wartość m.in. N !)
3) N=1, Zwloka=1, konsument wykonuje "if( N==0 ) ..."

void Producent()
{
  int atrapa;

  while(1) {
    wait(S); // poczatek sekcji kryt.
    Produkuj();
    N++;
    if( N==1 ) signal(Zwloka);
    signal(S); // koniec sekcji kryt.

    atrapa=321;
    atrapa=321;
    atrapa=321;
  }
}

void Konsument()
{
  int atrapa; string[20] str;

  wait(Zwloka);
  while(1) {
    wait(S); // poczatek sekcji kryt.
    Konsumuj();
    N--;
    signal(S); // koniec sekcji kryt.

    atrapa=123;
    atrapa=321;
    atrapa=123;

    if( N==0 ) wait(Zwloka);
  }
}

Zadanie 93

Zadanie 93a

Zadanie 93b (*)

1 0 0 | 0 0 0 0 0 0 0 0 0 0
0 0 0 | 1 0 1 0 0 0 0 0 0 0
0 0 0 | 1 0 1 0 1 1 1 1 0 0
0 1 0 | 0 0 0 0 0 0 0 0 0 0
............................
# jest 3 pisarzy  i 10 czytelników; pokazujemy kto w danej chwili jest w czytelni
# na koncu dodatkowo "statystyka" ile razy dana osoba była w czytelni
10 10 9 | 11 10 10 10 12 9 8 10 11 12

Zadanie 95

001000001000100
000011001000100
000000000100101
.............................
# to jest eksperyment z 15-ma filozofami ...
# 1 oznacza ze filozof "je", 0 oznacza ze filozof "myśli"
# jak widać w rozwiązaniu jest błąd bo 3 i 4 filozof w pewnym momencie równocześnie jedzą !

Wskazówka: Można uniknąć blokady ograniczając liczbę filozofów którzy chcą równocześnie jeść.
Uwaga: "Nr" filozofa może być używany wyłącznie do uzyskiwania dostępu do odpowiedniego widelca!

Zadanie 96 (**)

void test(i)
{
  // .....................
  
  if( (state[i]==HUNGRY)
  &&  (state[LEFT]!=EATING)
  &&  (state[RIGHT]!=EATING) )
  { 
    state[i]=EATING; signal(s[i]);
  }
}

Przedstaw ogólne rozwiązanie dla N-filozofów. Proces kontrolny powinien pokazywać co w bieżącej chwili robią wszyscy filozofowie (jedzą czy myślą). Porównaj to rozwiązanie z rozwiązaniem poprzedniego zadania pod kątem równoległości obliczeń (należy porównać wydruki generowane przez oba rozwiązania). Aby zobaczyć efekt zwiększonej "równoległości jedzenia" spowoduj aby jedzenie trwało długo (100 x atrapa=123), a myślenie krótko (2 x atrapa=123).

Monitory

Teraz omówimy następne "narzędzie" do rozwiązywania problemów współbieżności - tzw monitor - podobno jest on lepszy od semafora gdyż jest mniejsze prawdopodobieństwo błędnego programowania.
   Dygresja: W jaki sposób s.o. udostępnia monitory skoro wydaje się że monitor stanowi część języka programowania ? Odp: s.o. udostępnia pewne elementarne funkcje, które pozwalają skonstruować monitor wykorzystując jako podstawowe tworzywo np klasy C++ ... (patrz: Linux/Unix i biblioteka Pthread).

Oto przykład monitora o nazwie "Konta":

monitor Konta {
  int konto1=12345, konto2=0;

  void DokonajPrzelewu(int przelew)
  {
    konto1=konto1-przelew;
    konto2=konto2+przelew;
  }
}

Definicja Monitora.
Monitor jest zbiorem procedur i zmiennych, spełniającym następujące warunki:

1. Zmienne są widoczne tylko wewnątrz monitora (tj wewnątrz bloku monitora), natomiast procedury są widoczne na zewnątrz. Tak więc dostęp do zmiennych monitora jest możliwy tylko poprzez procedury monitora.
2. W danej chwili tylko jeden proces może przebywać w monitorze (tj wykonywać jego procedurę), co umożliwia prostą realizację wzajemnego wykluczania.
3. Istnieją dwa rodzaje kolejek zawierających wstrzymane procesy: kolejka procesów zewnętrznych (próbujących uruchomić procedurę monitora) oraz kolejki związane ze zmiennymi typu conditon.
4. Gdy monitor jest zajęty (pewien proces wykonuje jedną z jego procedur) i nastąpi próba wywołania procedury monitora przez inny proces, to ten inny proces zostanie wstrzymany i umieszczony na końcu kolejki procesów zewnętrznych. Gdy monitor zostanie zwolniony, to wtedy wznawiany jest pierwszy proces z kolejki procesów zewnętrznych.
5. Istnieje możliwość wstrzymywania i wznawiania procesów wewnątrz monitora przy pomocy zmiennych typu condition, na których można wykonywać operacje "waitc()" oraz "signalc()".
6. Po wykonaniu waitc(c,p) gdzie "c" jest zmienna typu conditon a "p" jest priorytetem (liczbą całkowitą) proces jest usypiany i umieszczany w kolejce związanej ze zmienną "c" (priorytet też jest zapamiętywany). Monitor jest zwalniany, może go zając inny proces. Wykonanie "waitc(c)" to to samo co "waitc(c,10)".
7. Po wykonaniu signalc(c) budzony jest jeden z procesów z najwyższym priorytetem (najmniejsza liczba), wybrany losowo, w kolejce zmiennej "c", a proces który wykonał "signalc()" jest usypiany i umieszczany na początku kolejki procesów zewnętrznych.
8. Istnieje możliwość sprawdzenia, czy kolejka zmiennej "c" jest pusta przy pomocy "empty(c)".

To jest przykład użycia monitora do wzajemnego wykluczania (np06.cm+np02.inc).
To jest przykład implementacji semafora ogólnego przy pomocy monitora (np07.cm+np02.inc).

UWAGA 1: powyższa def monitora pochodzi z książki Weiss/Gruźlewski; wydaje się że monitory języka BACI są nieco inne: procesy z "kolejki procesów zewnętrznych" są wybierane losowo tak że nie ma znaczenia czy proces jest umieszczana na końcu czy początku tej kolejki ...

UWAGA 2: jeśli proces kontrolny ma pokazywać wartości rozmaitych zmiennych (np ilosc czytelników czy pisarzy w czytelni) to te zmienne należy umieścić poza monitorem, przynajmniej w czasie testowanie programu.
 

Zadanie 99

 
Zadanie 100

Zadanie 101 (*)

Co się może stać jeśli nie uwzględnimy tekstu zapisanego na czerwono ? (opisz dokładnie przeplot zdarzeń prowadzący do błędu).  
 
 

Mechanizmy niskiego poziomu.

Będziemy się teraz zajmować konstruowaniem "narzędzi niskiego poziomu" do wzajemnego wykluczania (bardziej elementarnych niż semafory).
 

Zadanie 102

int flag[2]; // elementy przyjmują wartości 0 i 1
int turn; // przyjmuje wartości 0 i 1

Mamy 2 procesy "P0" i "P1".

// proces P0
Prolog0();
// sek kryt
Epilog0();

// proces P1
Prolog1();
// sek kryt
Epilog1();

UWAGA: kolejność modyfikowania zmiennych turn i flag[] przed sek kryt ma duże znaczenie !. Sprawdź eksperymentalnie która kolejność jest prawidłowa (i dołącz wydruki do sprawozdania).