Koordynowanie procesów

Wykład 4

SO

Koordynowanie procesów

Aby procesy mogły być wykonywane w sposób uporządkowany, w systemie muszą znajdować się mechanizmy do synchronizowania i komunikowania się procesów.

Zatem koordynacja procesów polega na (A)synchronizacji +

(B)komunikacji.

Synchronizacja

Problem sekcji krytycznej

Prawidłowość przebiegu procesów wymaga odpowiedniej formy synchronizacji.

Załóżmy, że każdy z grupy synchronizowanych procesów ma segment kodu, zwany sekcją krytyczną (zmiana wspólnych zmiennych, itp..). Gdy jeden z procesów wykonuje swoją sekcję krytyczną, wówczas żaden inny proces nie może wykonywać swojej sekcji krytycznej. Wykonanie sekcji krytycznych podlega wzajemnemu wyłączaniu w czasie.

Każdy proces musi prosić o pozwolenie wejścia do swojej sekcji krytycznej.

Ten fragment kodu nazywa się sekcją wejściową. Po sekcji krytycznej może występować sekcja wyjściowa. Pozostały kod - reszta.

Ogólna struktura typowego procesu

repeat
sekcja wejściowa;
sekcja krytyczna;
sekcja wyjściowa;
reszta

until false;

Aby prawidłowo skoordynować procesy (czyli rozwiązać problem sekcji krytycznej) muszą być spełnione 3 warunki:

0. wzajemne wyłączanie (W danym momencie tylko jeden proces może działać w sekcji krytycznej.)

1. postęp (Do wejścia do sekcji krytycznej mogą kandydować procesy nie wykonujące swoich reszt; wybór nie może być odwlekany w nieskończoność.)

2. ograniczone czekanie (Istnieje graniczna wartość liczby wejść innych procesów do ich sekcji krytycznych po tym, gdy dany proces zgłosił chęć wejścia do sekcji krytycznej i zanim uzyskał na to pozwolenie.)

Zakłada się, że każdy proces jest wykonywany z prędkością niezerową. Natomiast nie czyni się żadnych założeń o względnej prędkości każdego z procesów.

Praktyczne rozwiązania problemu sekcji krytycznej

0. sprzętowe środki synchronizacji, np. rozkazy sprzętowe wykonywane jako niepodzielne jednostki pozwalające sprawdzać i zmieniać zawartość słowa,

1. semafory,

2. regiony krytyczne,

3. monitory.

Semafory

Semafor jest zmienną całkowitą, dostępną tylko za pomocą dwu standardowych, niepodzielnych operacji:

0. czekaj,

1. sygnalizuj.

Gdy jeden proces modyfikuje wartość semafora, wówczas żaden inny proces nie może jednocześnie tej wartości zmieniać. Dla czekaj(S) nie może wystąpić przerwanie podczas sprawdzania wartości zmiennej całkowitej S (S<=0) i ewentualnego dokonywania jej zmiany.

Operacje na semaforze:

Czekaj (S) : while s<=0 do nic;

s:=s-1;

Sygnalizuj(S): s:=s+1;

Semafory znajdują zastosowanie w rozwiązywaniu problemu sekcji krytycznej
z udziałem n procesów.

Semafor S ma początkowo wartość 1.

Każdy proces jest zorganizowany następująco:

repeat

czekaj(S);

sekcja krytyczna;

sygnalizuj(S);

reszta

until false;

Taka organizacja procesu jest implementacją wzajemnego wyłączania za pomocą semaforów.

Wadą przedstawionych rozwiązań jest konieczność aktywnego czekania przez procesy. Podczas, gdy jeden proces jest w sekcji krytycznej, pozostałe procesy usiłujące wejść do sekcji krytycznych muszą nieustannie wykonywać instrukcje sekcji wejściowych.

Aktywne czekanie marnuje cykle procesora, które mogłyby być produktywnie zużytkowane przez inne procesy. Semafor tego rodzaju bywa też nazywany wirującą blokadą (oczekujący proces wiruje w miejscu).

Aby ominąć konieczność aktywnego czekania można zmodyfikować operacje czekaj i sygnalizuj. Proces, który wykonuje operację czekaj i zastaje niedodatnią wartość semafora, musi czekać. Zamiast czekać aktywnie proces może się zablokować. Operacja blokowania umieszcza proces w kolejce związanej z danym semaforem i powoduje przełączenie stanu procesu na czekanie. Następnie sterowanie zostaje przekazane do programu planującego przydział procesora, który wybiera do wykonania inny proces.

Działanie procesu zablokowanego pod semaforem S powinno zostać wznowione wskutek wykonywania operacji sygnalizuj przez jakiś inny proces. Wznowienie oznacza przejście ze stanu oczekiwania na gotowość za pomocą operacji budzenia.

Aby zaimplementować semafor odpowiadający tym założeniom można określić go jako rekord

type semafor = record

wart : integer;

L: list of proces;

end;

Każdy semafor ma wartość całkowitą i listę procesów. Kiedy proces musi czekać pod semaforem, wtedy dołącza się go do listy procesów. Operacja sygnalizuj usuwa jeden proces z listy oczekujących procesów i budzi go.

Operacje semaforowe można zatem tak zdefiniować

Czekaj(S): S.wart := S.wart – 1;

if S.wart < 0

then begin

dołącz dany proces do S.L;

blokuj;

end;

Sygnalizuj(S): S.wart := S.wart + 1;

if S.wart <= 0

then begin

usuń jakiś proces P z S.L;

budzenie(P);

end;

Operacja blokuj wstrzymuje wykonywanie procesu, który ją wywołuje. Operacja budzenie (P) wznawia działanie zablokowanego procesu P. Obie operacje są wykonywane za pośrednictwem funkcji podstawowych S.O.

W powyższej implementacji semafory mogą przyjmować wartości ujemne (sprzecznie z klasyczną definicją). Jeśli wartość semafora jest ujemna, to jej moduł określa liczbę procesów czekających na ten semafor. Wynika to ze zmiany porządku instrukcji zmniejszania i sprawdzania wartości zmiennej w implementacji operacji czekaj.

Listę procesów można zaimplementować dodając pole dowiązań bloku kontrolnego każdego procesu. Każdy semafor zawiera wartość całkowitą i wskaźnik do listy bloku kontrolnego procesu.

Decydującym aspektem poprawnego działania semaforów jest niepodzielne wykonywanie związanych z nimi operacji. Należy zagwarantować, że żadne dwa procesy nie wykonują operacji czekaj ani sygnalizuj na tym samym semaforze w tym samym czasie.

Ten wymóg łatwo spełnić w środowisku jednoprocesorowym. Wtedy należy zabronić wykonywania przerwań podczas operacji czekaj i sygnalizuj.

Blokada

Wadą implementacji semafora z kolejką oczekujących procesów jest niebezpieczeństwo oczekiwania w nieskończoność na zdarzenie sygnalizuj wykonane przez jeden z procesów. O procesach mówi się wtedy, że uległy blokadzie.

Zbiór procesów jest w stanie blokady wówczas, gdy każdy proces w tym zbiorze oczekuje na zdarzenie (czyli pozyskanie i zwolnienie zasobów), które może być spowodowane tylko przez inny proces tego zbioru.

Blokowanie nieskończone (głodzenie) - gdy procesy czekają w nieskończoność pod semaforem. (np. kolejka LIFO)

Regiony krytyczne

Konstrukcja regionu krytycznego strzeże przed popełnianiem przez programistę pewnych prostych błędów związanych z rozwiązywaniem problemu sekcji krytycznej za pomocą semaforów.

Niech v – zmienna typu T określa zmienną dzieloną przez wiele procesów:

var v: shared T;

Zmienna będzie dostępna tylko w obrębie instrukcji region:

region v do S;

Konstrukcja ta oznacza, że dopóki trwa wykonanie instrukcji S, dopóty żaden inny proces nie ma dostępu do zmiennej v.

Zatem jeśli dwie instrukcje:

region v do S1;

region v do S2;

są wykonywane współbieżnie w różnych procesach sekwencyjnych, to wynik będzie równoważny sekwencyjnemu wykonaniu „S1 przed S2” lub „S2 przed S1”.

Monitory

Monitory to przykład konstrukcji w języku wysokiego poziomu służącej do synchronizacji, zobowiązującej programistów do jawnego deklarowania danych i zasobów dzielonych oraz wymuszającej wzajemne wyłączanie dostępu do obiektów dzielonych.

Monitor składa się ze zbioru operacji zdefiniowanych przez programistę i zawiera:

- zbiór deklaracji zmiennych globalnych,

- zbiór procedur, które można wywoływać w celu uzyskania dostępu z zewnątrz do monitora,

- fragment programu inicjującego wykonywany tylko raz przy nadawaniu wartości początkowych zmiennym monitora.

Kompilator języka zawierającego monitory musi zapewniać spełnienie warunku, że dostęp do obiektu dzielonego jest możliwy jedynie poprzez wywołanie procedury odpowiedniego monitora. Twórcy kompilatora muszą również zadbać o to, by procedury każdego monitora były realizowane jako wzajemnie wyłączające się sekcje krytyczne. Odpowiedzialność za wzajemne wyłączanie spada z programisty na kompilator.

Mechanizm monitora zrealizowano w językach: Concurrent Pascal, Pascal Plus, Mesa.

Komunikacja

Komunikacja międzyprocesowa

Komunikacja międzyprocesowa stanowi mechanizm umożliwiający procesom wzajemne informowanie się i synchronizowanie działań. Komunikację międzyprocesową realizuje się za pomocą systemu komunikatów lub pamięci dzielonej. Oba te schematy mogą być używane jednocześnie w obrębie jednego S.O.

Systemy z pamięcią dzieloną

W systemach z pamięcią dzieloną procesy współużytkują pewne zmienne, za pomocą których odbywa się wymiana informacji. Odpowiedzialność za organizowanie komunikacji spoczywa na programistach zastosowań. S.O. dostarcza tylko środków do dzielenia pamięci.

Metoda systemu komunikatów

Metoda systemu komunikatów pozwala procesom na wymianę komunikatów. Odpowiedzialność za organizowanie komunikacji spada na sam system operacyjny. Jeśli procesy P i Q chcą się komunikować ze sobą, to muszą nadawać i odbierać komunikaty – musi istnieć między nimi łącze komunikacyjne.

W przypadku procesów o rozłącznych przestrzeniach adresów logicznych, w skład narzędzi komunikacji międzyprocesowej wchodzą dwie podstawowe operacje:

0. nadaj

1. odbierz

Komunikacja może być bezpośrednia lub pośrednia.

W komunikacji bezpośredniej każdy proces, który chce nadać lub odebrać komunikat musi jawnie nazwać odbiorcę lub nadawcę uczestniczącego w tej wymianie informacji. W tym przypadku operacje nadaj i odbierz są zdefiniowane następująco:

nadaj(P,komunikat) czyli nadaj komunikat do procesu P.

odbierz(Q,komunikat) czyli odbierz komunikat od procesu Q.

W komunikacji pośredniej komunikaty są nadawane i odbierane poprzez skrzynki pocztowe. Skrzynka pocztowa jest obiektem, w którym procesy mogą umieszczać komunikaty i z którego komunikaty mogą być pobierane.

Proces może komunikować się z innymi procesami za pomocą różnych skrzynek pocztowych.

Skrzynka pocztowa może być własnością procesu albo systemu. Jeśli skrzynka należy do procesu (tzn. jest przypisana lub zdefiniowana jako część procesu), to rozróżnia się jej właściciela (który może tylko odbierać komunikaty) i użytkownika (który może tyko nadawać komunikaty). Kiedy proces będący właścicielem skrzynki pocztowej, kończy działanie, wtedy skrzynka znika.

S.O. dostarcza mechanizmów pozwalających na:

- tworzenie nowej skrzynki,

- nadawanie i odbieranie komunikatów,

- likwidowanie skrzynki.

System komunikatów jest szczególnie użyteczny w środowisku rozproszonym, w którym procesy mogą rezydować na różnych maszynach.

Sytuacje wyjątkowe w przetwarzaniu komunikatów

S.O. powinien poradzić sobie z następującymi sytuacjami:

- zakończenie procesu (gdy zakończy się proces przed zakończeniem przetwarzania komunikatu) Proces może oczekiwać na komunikat od procesu, który już zakończył działanie lub może wysłać komunikat do procesu, który zakończył działanie,

- utrata komunikatów (np. awaria sprzętu) S.O. musi to wykryć i ponownie nadać komunikat lub powiadomić o tym proces nadawczy że zaistniał błąd - by powtórnie przesłał komunikat,

- zniekształcenia komunikatów.