1

Koordynowanie

procesów

Wykład 4

SO

2

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.

3

Synchronizacja

4

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.

5

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.

6

Ogólna struktura typowego

procesu

repeat

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

until false;

7

Aby prawidłowo skoordynować

procesy (czyli rozwiązać problem

sekcji krytycznej) muszą być

spełnione 3 warunki:

1. wzajemne wyłączanie

(W danym momencie tylko

jeden proces może działać w sekcji krytycznej.)

2. 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ść.)

3. 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.

8

Praktyczne rozwiązania

problemu sekcji krytycznej

• sprzętowe środki synchronizacji, np.

rozkazy sprzętowe wykonywane jako

niepodzielne jednostki pozwalające

sprawdzać i zmieniać zawartość

słowa,

• semafory,
• regiony krytyczne,
• monitory.

9

Semafory

Semafor jest zmienną całkowitą, dostępną tylko za

pomocą dwu standardowych, niepodzielnych

operacji:

• czekaj,

• 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;

10

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.

11

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).

12

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.

13

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.

14

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.

15

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;

16

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.

17

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.

18

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)

19

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”.

20

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.

21

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.

22

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.

23

Komunikacja

24

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.

25

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.

26

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:

•

nadaj

•

odbierz

27

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.

28

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.

29

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.

30

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.

31

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

.