Programowanie współbieżne i rozproszone/PWR Wykład 8

Model scentralizowany

Cechy

Przechodzimy teraz do mechanizmów synchronizacji w systemach ze wspólną pamięcią. Model ten różni się od dotychczasowych przede wszystkim tym, że można stosować zmienne współdzielone, czyli dostępne dla wielu procesów, i za ich pomocą wymieniać informacje.

Korzystanie ze zmiennych współdzielonych wymaga jednak dużej ostrożności, jak widzieliśmy to podczas pierwszego wykładu. Niekontrolowane niczym modyfikowanie takich zmiennych w wielu procesach jednocześnie może dawać niedające się przewidzieć efekty. Z tego powodu większość z omawianych w dalszym ciągu mechanizmów gwarantuje atomowość lub niepodzielność pewnych operacji.

Mechanizmy

W dalszej części wykładu omówimy szczegółowo dwie metody synchronizacji procesów w środowisku scentralizowanym: semafory i monitory. Wspomnimy także o mechanizmie zamków (muteksów). Zanim jednak to nastąpi na przykładzie wzajemnego wykluczania wspomnijmy o dwóch innych metodach synchronizacji.

Pierwsza z tym metod jest stosowana wtedy, gdy nie dysponujemy żadnym wsparciem ani ze strony sprzętu ani oprogramowania. Korzystając jedynie z wysokopoziomowych instrukcji języka programowania można zapewnić wzajemne wykluczanie w dostępie do sekcji krytycznej za pomocą m.in. algorytmu Petersona. Jego dokładne omówienie znalazło się w materiałach dotyczących pierwszych ćwiczeń. Przypomijmy jego wady: statycznie znana liczba procesów, koszt, a przede wszystkim aktywne oczekiwanie.

Czasem możemy liczyć na wsparcie sprzętowe. Może to być na przykład specjalny rozkaz maszynowy realizujący niepodzielny zapis i odczyt. Rozpatrzmy dla przykładu rozkaz Test_and_Set, który odczytuje pewien bit G i ustawia go na jeden. Działanie takiego rozkazu można by zapisać w wysokopoziomowym języku następująco:

procedure Test_and_Set (var L: 0..1);
{ Ta procedura jest atomowa! }
begin
  L := G;
  G := 1;
end   

Problem wzajemnego wykluczania można wówczas rozwiązać następująco:

var
  wolny: 0..1 := 0;

process P;
var
  i: 0..1;
begin
  repeat
    własne_sprawy;
    repeat
      Test_and_Set (i);
    until i = 0;
    sekcja_krytyczna;
    wolny := 0;
  until false
end; 

To rozwiązanie także nie jest pozbawione wad. Pierwszą z nich jest oczywiście aktywne oczekiwanie, drugą możliwość zagłodzenia procesu.

Semafory jako abstrakcyjny typ danych

Omówienie mechanizmów udostępnianych programowo rozpoczniemy od semaforów. Semafor jest to abstrakcyjny typ danych, na którym można wykonywać jedynie dwie operacje:

• operację P (w literaturze pojawia się też czasem nazwa wait)
• operację V (signal).

Powyższe operacje są niepodzielne i wzajemnie się wykluczają. Ponadto semafor można raz, poza procesami, zainicjować na dowolną wartość nieujemną.

O semaforze myślimy jak o pewnej zmiennej całkowitej o wartościach nieujemnych. Programista nie ma jednak dostępu do wartości tej zmiennej (poza początkową inicjacją), a operacje na niej wykonuje za pomocą operacji P i V. Ich działanie można zdefiniować na dwa sposoby.

Klasyczna definicja semafora

Klasyczna definicja semafora definiuje semantykę operacji P następująco:

P(S): 
zaczekaj aż wartość semafora S będzie dodatnia;
zmniejsz S o 1

Jeśli semafor S ma od razu wartość większą niż 0, to operacja P nie wstrzymuje wywołującego ją procesu. Jeśli S ma wartość równą 0, to proces wykonujący P jest wstrzymywany w sposób nieangażujący procesora. W czasie, gdy proces oczekuje inne procesy mogą rozpocząć wykonanie operacji P (i zostaną także wstrzymane) lub też wykonać operację V (co, jak za chwilę zobaczymy, powoduje zwiększenie wartości zmiennej semaforowej i w konsekwencji może doprowadzić do obudzenia jednego z oczekujących na operacji P procesów).

Operację V definiuje się po prostu tak:

 V(S):  
 S := S + 1

Powyższe definicje wymagają kilku wyjaśnień. Niepodzielność instrukcji V jest zrozumiała: zwiększenie semafora ma się po prostu odbyć w jednym kroku. Co jednak oznacza niepodzielność instrukcji P? Jeśli proces rozpoczyna wykonanie tej operacji i zastaje dodatnią wartość semafora, to zmniejsza jego wartość o 1, a niepodzielność gwarantuje, że operacja ta zostanie wykonana w całości zanim inny proces rozpocznie wykonanie V lub P. Jeśli jednak proces zastanie semafor równy zero to jest wstrzymany. Niepodzielność P nie gwarantuje zatem tego, że proces, który rozpoczął jej wykonanie zakończy je bez wstrzymania swojego działania. Jednak proces wstrzymany oddaje dostęp do operacji P i V, dzięki czemu inny proces może zwiększyć semafor. Któryś z oczekujących procesów (jeden z nich) może "zauważyć" tę zmianę (nie zajmujemy się sposobem implementacji tego mechanizmu) i wznowić wykonanie operacji P. I tutaj ponownie korzystamy z niepodzielności, która gwarantuje, że proces zmniejszy wartość semafora zanim ktokolwiek inny rozpocznie wykonanie P lub V.

Podkreślmy raz jeszcze: P i V to jedyne operacje na semaforze. W szczególności nie ma możliwości sprawdzenia wartości zmiennej semaforowej!.