5. ZAGADNIENIA KOORDYNACJI PROCESÓW

Przez koordynację procesów będziemy rozumieli ich synchronizację (czyli

uwzględnianie

wzajemnych uzależnień czasowych) oraz komunikację (czyli wzajemne

przekazywanie sobie

informacji).

Potrzeba synchronizacji jest na ogół związana z komunikacją - informacja nie może

zostać odczytana

przez jeden proces, jeśli nie została wcześniej zapisana przez inny proces.

Komunikacja pomiędzy

procesami może odbywać się przez kanał komunikacyjny (na przykład

realizowany jako bufor

współdzielonego pliku) lub przez pamięć dzieloną (segment pamięci fizycznej

udostępniony przez

system operacyjny obydwóm procesom).

Zapisy / odczyty do / z pamięci dzielonej mogą być dokonywane przez oba procesy

bez żadnych

ograniczeń, więc muszą być synchronizowane przez dodatkowe mechanizmy

systemowe.

Kanał komunikacyjny służy zazwyczaj tylko do komunikacji jednokierunkowej, a

mechanizmy

synchronizacji są zawarte w samych procedurach zapisu / odczytu do / z kanału.

Jeśli jeden proces tylko produkuje dane i umieszcza je w pewnym medium
komunikacyjnym, a drugi

proces tylko je stamtąd pobiera (w takiej samej kolejności, w jakiej zostały
włożone), mówimy, że te

procesy tworzą układ producent - konsument

(producer - consumer)

. Jeśli

medium komunikacyjne

posiada pewną pojemność (bufor), działania producenta są w pewnym stopniu
niezależne od działań

konsumenta - może on produkować dane „na zapas” i umieszczać je w buforze.
Konsument natomiast

nie może „konsumować” danych szybciej, niż dostarcza je producent.

Jeśli pojemność bufora jest nieskończenie duża, proces producenta jest
całkowicie niezależny od

procesu konsumenta. Jeśli pojemność bufora jest zerowa, musi zachodzić pełna
synchronizacja

pomiędzy produkcją i konsumpcją (włożenie i pobranie każdej danej musi
nastąpić w tej samej

chwili). Najbardziej typowym przypadkiem jest skończona, niezerowa pojemność
bufora. Bufor

skończony jest często realizowany jako tablica cykliczna.

produce
nt

konsument

bufor

Niektóre procesy systemowe pełnią rolę serwerów, czyli dostarczycieli
określonych usług (na

przykład obliczają jakąś funkcję, podają czas, wysyłają pliki pod podany adres
itp.). Serwery

przeważnie przebywają w stanie zawieszenia, oczekując na zgłoszenia procesów
potrzebujących

usługi, czyli klientów. Po zgłoszeniu zapotrzebowania klient zostaje przeważnie
zawieszony i czeka

na dostarczenie odpowiedzi przez serwer. Potem pobiera odpowiedź, a serwer
zostaje ponownie

zawieszony.

serwer

aktywność

klient
zawieszenie

t

Uwaga

1) Okresowo mogą występować spiętrzenia zgłoszeń klientów przysyłanych
szybciej, niż serwer

jest w stanie je obsłużyć. W takim przypadku są one wpisywane do kolejki
zgłoszeń serwera

i wybierane stamtąd w takiej samej kolejności, jak przybyły.

2) Serwery dzielą się na iteracyjne i współbieżne. Serwery iteracyjne same
(jako jeden proces)

zajmują się pobieraniem zgłoszeń z kolejki, obsługą i odesłaniem odpowiedzi.
Serwery współ-

bieżne pobierają tylko zgłoszenia, a następnie tworzą procesy potomne i im
zlecają całą dalszą

obsługę. Obecnie większość serwerów jest realizowanych jako współbieżne.

Przekazywanie informacji pomiędzy procesami powinno odbywać się w
określonych porcjach.

Byłoby niekorzystne, gdyby proces odczytujący pobrał tylko fragment
komunikatu przekazywanego

przez inny proces. Podobnie w przypadku aktualizacji zapisu pewnego rekordu w
bazie danych przez

jeden proces, inne procesy nie powinny w tym samym czasie próbować odczytać
tego rekordu, gdyż

mogłyby odczytać częściowo nową, a częściowo starą zawartość - otrzymałyby
wtedy niespójne dane.

Fragment kodu procesu, który wykonuje operację na współdzielonych danych
taką, że w tym samym

czasie żaden inny proces nie powinien operować na tych danych, nazywamy
sekcją krytyczną

(critical section)

tego procesu. Założenie, że w dowolnej chwili co najwyżej jeden

proces (spośród

grupy współpracujących procesów) może wykonywać swoją sekcję krytyczną,
nazywamy zasadą

wzajemnego wykluczania

(mutual exclusion)

.

Aby wzajemne wykluczanie mogło być zrealizowane, każde wykonanie sekcji
krytycznej musi być

poprzedzone wykonaniem sekcji wejściowej, w której proces zgłasza potrzebę
wejścia do sekcji

krytycznej (i czeka na zgodę), a po wykonaniu sekcji krytycznej musi nastąpić
wykonanie sekcji

wyjściowej, w której proces informuje inne o opuszczeniu sekcji krytycznej.
Pozostałą część kodu

procesu (nie należącą do żadnej z powyższych sekcji) nazywamy resztą.

Przyjęcie założenia o istnieniu sekcji krytycznych pociąga za sobą konieczność
spełnienia

następujących warunków:

1) wzajemne wykluczanie;

2) postęp

(progress)

- jeżeli w pewnym momencie żaden proces nie wykonuje

swojej sekcji

krytycznej, a pewna liczba procesów kandyduje do tego (weszła do swoich
sekcji wejściowych),

to wybór jednego z nich musi nastąpić w ograniczonym czasie;

3) jeżeli którykolwiek proces wszedł do swojej sekcji wejściowej, to przed
otrzymaniem przez niego

zgody na wejście do sekcji krytycznej tylko ograniczona liczba innych
procesów może taką zgodę

otrzymać.

Powyższe warunki związane są z unikaniem pewnych niekorzystnych zjawisk,
które mogą wystąpić

w przypadku niewłaściwej koordynacji procesów. Te zjawiska to blokada

(deadlock)

oraz głodzenie

(starvation)

procesów.

Blokada zachodzi, gdy pewna liczba procesów jest w stanie oczekiwania na
zdarzenie, które może być

wynikiem jedynie wykonywania (postępu) jednego z nich.

Przykład

Przepis prawny obowiązujący w stanie Kanzas na przełomie XIX i XX wieku:
„Jeżeli dwa pociągi

zbliżają się do siebie jadąc po krzyżujących się torach, to każdy z nich powinien
zatrzymać się i nie

ruszać, dopóki ten drugi nie odjedzie”.

Przykład

Jeśli cztery pojazdy dojadą jednocześnie z różnych stron do skrzyżowania dróg
równorzędnych,

każdy z nich powinien udzielić pierwszeństwa pojazdowi po jego prawej stronie.

Przykład

Problem ucztujących filozofów (por. następny slajd).

Problem ucztujących filozofów.

n =

5

Założenia:

a) każdy filozof może przebywać w dwóch stanach:

myślenie

i

jedzenie

;

b) każdy widelec jest zasobem współdzielonym przez dwóch sąsiadów na
zasadzie wyłączności

dostępu;

c) do jedzenia potrzebne są dwa widelce;

d) widelce muszą być brane sekwencyjnie (nie jednocześnie) przez jednego
filozofa;

e) czasy przebywania w stanach

myślenie

i

jedzenie

są zawsze skończone.

Jeżeli wszyscy filozofowie naraz podniosą np. lewe widelce, dojdzie do blokady.

F
0

F1

F2

F3

F4

w1

w2

w3

w4

w0

Warunki konieczne i dostateczne powstawania blokad:

1) wzajemne wykluczanie (niepodzielność pewnego zasobu - np. procesora lub
wybranej lokaty

w pamięci);

2) brak wywłaszczeń (system nie może „siłą” odbierać pewnych zasobów
procesom);

3) oczekiwanie cykliczne (musi istnieć zbiór procesów { P

1

, P

2

, ... , P

n

}, gdzie n

> 1, taki, że P

1

czeka

na zasób przetrzymywany przez P

2

, ... , P

n

czeka na zasób przetrzymywany

przez P

1

).

Wynika z tego, że każdy z procesów biorących udział w blokadzie musi mieć
przydzielony pewien

zasób i dodatkowo czekać jeszcze na przydzielenie pewnego innego zasobu.

Głodzenie zachodzi, gdy co najmniej jeden proces oczekuje w nieskończoność na
przydzielenie

pewnego zasobu (choć teoretycznie mógłby go otrzymać), podczas gdy inne
procesy wymieniają się

tym zasobem.

Przykład

Obsługa na zasadzie stosu

(last in, first servised)

.

Do zjawiska głodzenia procesów może doprowadzić niewłaściwie zorganizowany
system priorytetów

procesów (współczynników liczbowych przyporządkowanych procesom, które
wskazują, na ile

wykonywanie danego procesu jest pilne z punktu widzenia systemu
operacyjnego). Jeśli przez cały

czas pojawiają się w systemie procesy o wysokich priorytetach, może się zdarzyć,
że pewien proces

o niskim priorytecie nigdy nie będzie wybrany do wykonania. Metodą
zapobiegania takiemu zjawisku

jest system priorytetów zmiennych w czasie - priorytet każdego oczekującego
na wykonanie procesu

stopniowo rośnie, aż wreszcie w którymś momencie musi on uzyskać przydział
procesora. Takie

rozwiązanie jest zastosowane na przykład w systemie Unix.

W języku matematycznej teorii zarządzania procesami własność systemu
zapewniająca brak głodzenia

procesów oczekujących na przydział zasobów nazywana jest uczciwością

(fairness)

. Wyróżniane są

różne rodzaje uczciwości w zależności od tego, czy proces zgłasza
zapotrzebowanie na zasób przez

cały czas, czy też okresowo, i od tego, czy czas oczekiwania na przydział jest
zależny od liczby innych

procesów ubiegających się o ten sam zasób.

W programowaniu procesów współbieżnych istotną rolę odgrywa pojęcie
niepodzielności operacji.

W przypadku wykonywania sekcji krytycznej chcemy mieć zapewnione, że
proces będzie mógł ją

wykonać jako całość, bez przerywania wykonania przez inne procesy. Jeśli
operacja na zasobach

jest wykonywana przez pojedyncze wywołanie funkcji systemowej, to
niepodzielność jej wykonania

jest gwarantowana przez system operacyjny (procesy wykonywane w trybie
jądra systemu nie

podlegają wywłaszczaniu). Przykładami takich operacji są pojedyncze zapisy i
odczyty do / z

kanału komunikacyjnego (na przykład kolejki komunikatów).

Gwarancji niepodzielności nie ma natomiast w przypadku operowania na
pamięci wspólnej.

Pojedyncze instrukcje w językach wyższego poziomu, takie jak na przykład x =
y + z ; w języku C,

gdzie x, y, z są nazwami zmiennych, którym zostały przyporządkowane lokaty
w segmencie

pamięci wspólnej, są tłumaczone na cały ciąg rozkazów maszynowych, którego
wykonywanie może

być przeplatane z wykonaniami innych procesów (być może również
operujących na tych

zmiennych) w dowolny sposób.

Jeżeli mają być wykonywane operacje na pamięci wspólnej, lub bardziej złożone
operacje na

dowolnych zasobach, programista musi sam zadbać o ich zabezpieczenie.
Najprostszym mecha-

nizmem abstrakcyjnym służącym do tego celu są semafory. Podstawowym
rodzajem semafora

jest semafor binarny, będący obiektem, którego jedyne pole może przyjmować
tylko wartości

0 i 1, a jedyne operacje, jakie można na nim wykonać, to:

P (czekaj)

V (sygnalizuj)

Definicje tych operacji jest następująca:

P(S) - jeżeli S>0, to zmniejsz S o 1, w przeciwnym razie wstrzymaj
wykonywanie procesu;

V(S) - jeżeli są jakieś procesy wstrzymane przez semafor S, to wznów jeden z
nich, w przeciwnym

razie jeśli S=0, to zwiększ S o 1.

Uwaga.

1) Skutek próby otwarcia otwartego semafora binarnego zależy od
implementacji. Dojście do

takiej sytuacji świadczy o błędzie w programie (i system operacyjny
zazwyczaj reaguje

sygnalizacją błędu).

2) Same operacje na semaforach muszą być wykonywane niepodzielnie. W
systemach z przeplo-

tem realizowane są jako funkcje systemowe, natomiast w sytuacji
rzeczywistej równoległości

ich implementacja musi być wspierana przez odpowiedni sprzęt (procesory
z niepodzielnymi

rozkazami typu test-and-set).

3) Niedeterminizm uruchamiania procesów czekających pod semaforem może
podlegać różnym

ograniczeniom. Wyróżniamy na przykład semafor ze zbiorem
oczekujących, gdzie wybór

procesu spośród oczekujących pod semaforem jest zupełnie przypadkowy, i
semafor z kolejką

oczekujących, gdzie procesy są uwalniane spod semafora w takiej samej
kolejności, w jakiej

do niego przybyły.

Jednym z klasycznych problemów programowania współbieżnego jest tak
problem czytelników

i pisarzy. Problem ten jest abstrakcją problemu dostępu do wielodostępnej bazy
danych. Każdy

proces aktualizujący dane (pisarz) musi mieć wyłączność dostępu do danych
(czytelni), ale procesy,

które tylko czytają (czytelnicy), mogą pracować jednocześnie.

Problem ten jest możliwy, ale trudny do rozwiązania przy użyciu tak
elementarnych narzędzi, jak

semafory. Typowe rozwiązania opierają się na wysokopoziomowych
mechanizmach synchronizacji,

takich jak na przykład monitory lub regiony (dostępnych w językach wysokiego
poziomu przeznaczo-

nych do programowania współbieżnego - na przykład w języku ADA).

Idea rozwiązania:

(gwarantującego niemożliwość głodzenia zarówno

czytelników, jak i pisarzy)

Przybywający pisarze ustawiani są w kolejkę prostą, przybywający czytelnicy
gromadzeni są

w zbiorze. Mechanizm koordynujący wpuszcza na przemian pojedynczych
pisarzy i cały zbiór

zgromadzonych czytelników. Wpuszczenie może mieć miejsce dopiero po
opuszczeniu czytelni

przez poprzednich użytkowników / użytkownika. Jeżeli kolejka oczekujących
pisarzy jest pusta,

a w czytelni przebywają czytelnicy, każdy nowo przybyły czytelnik jest od razu
wpuszczany.

Jeśli w zbiorze nie oczekują żadni czytelnicy, kolejno przybywający pisarze są
wpuszczani po

zakończeniu pobytu w czytelni przez poprzednika.

kolejka pisarzy

zbiór
czytelników

czytelnia