Programowanie współbieżne

i rozproszone

• Współbieżność - składające się na nią zjawiska, czynności

lub działania odbywają się równocześnie.

• Proces - program (procedura) w trakcie wykonywania, który

może być skończony lub nieskończony.

• Program współbieżny - zbiór programów sekwencyjnych

wykonywanych równolegle, gdzie nie jest wymagane, aby
każdy proces był wykonywany przez fizycznie odrębny
procesor.

• Geneza – systemy operacyjne wielozadaniowe.

Termin programowanie współbieżne używa się do określenia

technik i notacji programistycznych służących do wyrażania
równoległości oraz rozwiązywania zagadnień związanych z powstałymi
przy tym problemami synchronizacji i komunikacji.

Programowanie współbieżne jest bardzo ważnym zagadnieniem, gdyż

pozwala zajmować się równoległością bez wdawania się w szczegóły
implementacyjne. Możliwość takiego abstrahowania okazała się na
tyle użyteczna przy pisaniu programów, że nowoczesne języki
programowania wyposażono już w mechanizmy programowania
współbieżnego.

Podstawowym problemem w programowaniu współbieżnym jest

wyłączność procesów do wspólnych zasobów.

Programowanie sekwencyjne a

współbieżne

 programowanie rozwiązań sekwencyjnych
jest prostsze

 prostsza analiza poprawności programu

 duża liczba problemów analizowanych i rozwiązywanych za pomocą

programu

sekwencyjnego będzie działała wolniej ,

Programowanie sekwencyjne :

Programowanie współbieżne:

 możliwość

tworzenia

systemów

komputerowych

(programów

współbieżnych) w sposób jak najbardziej efektywny,

 programowania

współbieżne

jest

znacznie

trudniejsze

niż

programowania sekwencyjne,

 trudniejsze jest dowodzenie poprawności programów współbieżnych

(skomplikowana analiza poprawności programu),

 współbieżność wymaga uwzględnienia trudnych do opisania zależności

czasowych występujących pomiędzy poszczególnymi procesami,

 brakuje metod testowych umożliwiających wykrywanie błędów

synchronizacji,

 konieczność specyfikacji (określenia) instrukcji, które mogą być

wykonywane jednocześnie (problem wzajemnego wykluczania,

sortowanie współbieżne tablic),

Problemy w programowaniu

współbieżnym

 problemy synchronizacji i komunikacji

 problemy związane z przydziałem procesora (priorytetowanie

procesów)

Przykład:

Złożoność obliczeniowa sekwencyjnego i równoległego algorytmu
sortowania tablic.

Rozmiar

tablicy

Sortowanie

przez

zamianę

Algorytm

równoległy

Algorytm

równoległy ze

współbieżnym

sortowaniem

N

n

2

/2

(n

2

/4)+n

(n

2

/8)+n

40

800

440

140

100

5000

2600

1350

1000

500 000

251 000

126 000

Sortowanie sekwencyjne n – elementowej tablicy (przez zamianę):

dla wewnętrznej pętli sortowania –
(n-1)+ (n-2)+...+1= n(n-1)/2= n

2

/2

Sortowanie równoległe

podział tablicy na dwie tablice po n/2 elementów

liczba operacji dla jednej tablicy (n/2)

2

/2 = n

2

/8

liczba operacji potrzebnych do posortowania 2 tablic n

2

/4

n operacji połączenia dwóch tablic

Program sekwencyjny jest poprawny, jeśli zatrzymuje się

oraz drukuje poprawną wartość (wartości). To twierdzenie jest
też słuszne dla pewnego rodzaju programów współbieżnych
takich jak sortowanie.

Cechą wielu programów współbieżnych (systemów

operacyjnych, systemów czasu rzeczywistego) jest to, że nigdy
się nie zatrzymują). Wówczas w abstrakcji współbieżności
wyróżnimy dwa typy własności dotyczących poprawności:

Poprawności programów

współbieżnych

Własność bezpieczeństwa – program współbieżny jest bezpieczny,

jeśli nigdy nie doprowadza do niepożądanego stanu.

Np.:

 problem wzajemnego wykluczania,

 problem producentów i konsumentów -

każda porcja zostanie skonsumowana w

kolejności ich produkowania.

Własność Żywotności – program współbieżny jest żywotny, jeśli

zapewnia, że każde pożądane zdarzenie w końcu zajdzie.

Przejawy braku żywotności

Brak żywotności globalnej - blokada (zastój, zakleszczenie, martwy

punkt) – występuje wtedy, gdy każdy proces z danego zbioru procesów
jest wstrzymany w oczekiwaniu na zdarzenie, które może być
spowodowane tylko przez jakiś inny proces z tego zbioru. Zjawisko
blokady może być również traktowane jako przejaw braku
bezpieczeństwa programu, jest bowiem stan niepożądany.

Brak żywotności lokalnej - zagłodzenie – występuje wtedy, gdy

proces nie zostaje wznowiony, mimo że zdarzenie, na które czeka,
występuje dowolną liczbę razy i za każdym razem, gdy proces ten
mógłby być wznowiony, jest wybierany jakiś inny czekający proces.
Pomiędzy całkowitym brakiem pojęcia czasu w koncepcji żywotności, a
wprowadzeniem czasu dokładnego znajduje się pojęcie uczciwości.

Cztery rodzaje

uczciwości :

 uczciwość słaba oznacza, że w przypadku nieprzerwanego zgłaszania

żądania dostępu do zasobu przez proces, zostanie ono kiedyś obsłużone,

 uczciwość mocna oznacza, że gdy proces zgłasza żądanie dostępu

nieskończenie wiele razy, zostanie ono kiedyś obsłużone,

 oczekiwanie liniowe oznacza, że jeśli proces zgłosi żądanie, zostanie

ono obsłużone zanim dowolny inny proces zostanie obsłużony więcej niż
jeden raz,

 kolejka FIFO (ang. First In, First Out) oznacza, że jeśli proces zgłosi

żądanie, zostanie ono obsłużone przed dowolnym innym żądanie
zgłoszonym później.

Własność uczciwości - program współbieżny jest uczciwy
(sprawiedliwy), jeśli podczas przydzielania zasobu dzielonego, w taki sam
sposób traktuje wszystkie procesy. Własność ta jest szczególnym
przykładem własności żywotności.

Poprawności programów

współbieżnych

Przeplot. Aby wykazać, że program współbieżny nie jest poprawny,

wystarczy wskazać ciąg akcji poszczególnych procesów, które
doprowadzają do stanu niepożądanego.

System scentralizowany i rozproszony

Programowanie współbieżne może dotyczyć systemów opartych na

wspólnej pamięci (systemy scentralizowane), lub architektury
wieloprocesorowej

połączonej

siecią

komputerową

(systemy

rozproszone), gdzie każdy procesor dysponuje swoją pamięcią.

System scentralizowany

KANAŁ KOMUNIKACYJNY

KANAŁ KOMUNIKACYJNY

PROCESOR

PROCESOR

PROCESOR

PROCESOR

WSPÓLNA PAMIĘĆ

WSPÓLNA PAMIĘĆ

System rozproszony

SIEĆ LOKALNA

SIEĆ LOKALNA

PROCESOR

PROCESOR

PROCESOR

PROCESOR

PAMIĘĆ

PAMIĘĆ

PAMIĘĆ

PAMIĘĆ

Problem wzajemnego

wykluczania

Zasób dzielony - wspólny obiekt, z którego może korzystać w

sposób wyłączny wiele procesów.

Zasób własny - obiekt, z którego korzysta (do którego ma

dostęp w dowolnym czasie) tylko jeden proces.

Sekcja krytyczna - fragment procesu (ciąg instrukcji), w którym

proces korzysta z zasobu dzielonego.

Sekcja lokalna - fragment procesu (ciąg instrukcji), w którym

proces korzysta z zasobu własnego.

Problem wzajemnego wykluczania polega na zsynchronizowaniu

N procesów, z których każdy w nieskończonej pętli na
przemian zajmuje się własnymi sprawami ( sekcja lokalna ) i
wykonuje sekcję krytyczną , w taki sposób, aby wykonywanie
sekcji krytycznych jakichkolwiek dwóch lub więcej procesów
nie pokrywało się w czasie.

Rozwiązanie problemu sprowadza się do specyfikacji zbioru reguł

(warunków) spełnienie, których jest konieczne do tego, aby dany
proces mógł wykorzystać zasób dzielony (unikając zagłodzenia).
Oznacza to, że należy dokonać specyfikacji i implementacji
następujących protokołów: protokołu wstępnego i protokołu
końcowego.

Process P1( ) Process P2( ) ......................... Process Pn()
{ while (TRUE) { while (TRUE) { while (TRUE )
{ sekcja_lokalna; { sekcja_lokalna; { sekcja_lokalna;
protokół_wstępny;

protokół_wstępny;

protokół_wstępny;

sekcja_krytyczna; sekcja_krytyczna;
sekcja_krytyczna;

protokół_końcowy; protokół_końcowy;
protokół_końcowy;

} } }

} } {

Schemat procesu

Sekcja

lokalna

Protokół

wstępny

Sekcja

krytyczna

Protokół

końcowy

Problem wzajemnego

wykluczania

Dany jest zbiór N współbieżnych procesów cyklicznych, N = {P

1

,

P

2

, ... , P

n

}. Każdy z procesów w nieskończonej pętli, na przemian,

wykonuje pracę: na zasobie własnym i zasobie dzielonym lub tylko
na zasobach dzielonych. Ograniczenie w pracy systemu polega na
tym, że w tym samym czasie tylko zbiór m procesów (m  ||M||,

gdzie M jest podzbiorem zbioru N; M  N oraz moc ||M|| jest równa

pojemności zasobu dzielonego) może wykorzystywać zasób
dzielony.

Warunki poprawnego rozwiązania

problemu wzajemnego wykluczania:

 procesy muszą być traktowane jako równoważne, nie mogą mieć

przypisanych im statycznych priorytetów (sprawiedliwe decyzje)

 żaden proces nie może wykonywać swej sekcji krytycznej

nieskończenie długo, nie może ulec awarii podczas wykonywania sekcji
krytycznej). Taki sam warunek dotyczy protokołów wstępnego i
końcowego

 jeżeli więcej niż jeden proces chce wejść do sekcji krytycznej, to

decyzja o tym, który proces zostanie wybrany musi być podjęta w
skończonym czasie. Natomiast, jeżeli żaden z procesów nie wykonuje
sekcji krytycznej, to przy zgłoszeniu się dowolnego procesu musi być
mu umożliwione wejście do sekcji krytycznej

 zachowanie się procesów poza sekcją krytyczną nie powinno być w

żaden sposób ograniczone (luźne powiązanie procesów). Zatrzymanie
się jakiegoś procesu w poza sekcją krytyczną nie może prowadzić do
blokowania innych procesów

 Procesy mogą się wykonywać z różnymi prędkościami. W rozwiązaniu

nie wolno czynić żadnych założeń dotyczących względnej szybkości
procesów.

 Żywotność globalna i lokalna programu - brak blokady i zagłodzenia.

 Bezpieczeństwo programu.

Modele komunikacji między procesami:

model pamięci współdzielonej - systemy scentralizowanych
model przesyłania komunikatów - systemy rozproszone

W modelu pamięci współdzielonej rolę łącza komunikacyjnego pomiędzy

procesami spełnia pamięć dzielona:

wymiana informacji poprzez zapisywanie i odczytywanie wartości

zmiennej

dzielonej
udogodnienie sprzętowe - arbiter pamięci, zapewnia wyłączność odczytu
lub zapisu informacji z danej komórki pamięci

W modelu przesyłania komunikatów rolę łącza spełnia kanał komunikacyjny:

wymiana informacji jest realizowana poprzez wysyłanie komunikatów –
nadaj( komunikat ) i odbierz( komunikat ).

Problem wzajemnego wykluczanie w środowisku

scentralizowanym poniższy algorytm nadaje się do
wykorzystania na każdym komputerze niezależnie od
zainstalowanego na nim systemu operacyjnego. Używa on
wyłącznie instrukcji języka maszynowego udostępnionych
przez komputer bez korzystania z mechanizmów wysokiego
poziomu, takich jak semafory czy monitory.

Program 1
 
int czyja_kolej=1;
 
proces_P1 ( )
{
while (1)

{
while (czyja_kolej =2); // aktywne oczekiwanie

sekcja_krytyczna_P1;
czyja_kolej =1; // protokół końcowy
sekcja_lokalna_P1;
}
}
//////////////////////////////
proces_P2 ( )
{
while (1)

{
while (czyja_kolej =1); // aktywne oczekiwanie

sekcja_krytyczna_P2;
czyja_kolej =2; // protokół końcowy
sekcja_lokalna_P2;
}
}

Własności programu

 program jest bezpieczny,

 brak zagłodzenia,

 procesy nie są luźno powiązane, pozwolenie jest przekazywane

wprost od procesu do procesu, stąd:

 awaria procesu w sekcji lokalnej -> blokada systemu

 procesy wykorzystują zasób naprzemiennie

Program 2
 
int k1=1, k2 =1;
 
proces_P1 ( )
{
while (1)

{
while (k2 =0); // aktywne oczekiwanie

k1=0;
sekcja_krytyczna_P1;
k1=1; // protokół końcowy
sekcja_lokalna_P1;
}
}
//////////////////////////////
proces_P2 ( )
{
while (1)

{
while (k1 =0); // aktywne oczekiwanie

k2=0;
sekcja_krytyczna_P2;
k2=1; // protokół końcowy
sekcja_lokalna_P2;
}
}

Własności programu

 program nie jest bezpieczny,
 brak zagłodzenia,

 procesy są luźno powiązane, pozwolenie jest przekazywane

bezpośrednio od procesu do procesu, stąd:

 awaria procesu w sekcji lokalnej umożliwia realizacje drugiemu

procesowi

 procesy nie wykorzystują zasobu naprzemiennie

Program 3
 
int k1=1, k2 =1;
 
proces_P1 ( )
{
while (1)

{

k1=0;

while (k2 =0); // aktywne oczekiwanie

sekcja_krytyczna_P1;
k1=1; // protokół końcowy
sekcja_lokalna_P1;
}
}
//////////////////////////////
proces_P2 ( )
{
while (1)

{

k2=0;

while (k1 =0); // aktywne oczekiwanie

sekcja_krytyczna_P2;
k2=1; // protokół końcowy
sekcja_lokalna_P2;
}
}

Własności programu

   

program jest bezpieczny,

 

brak zagłodzenia,
możliwość wystąpienia blokady

Program 4
 
int k1=1, k2 =1;
 
proces_P1 ( )
{
while (1)

{

k1=0;

while (k2 =0)

{
k1=1;
delay(n); //czasowa rezygnacja z wejścia do sekcji
//aby P2 mógł wejść
k1=0
}
sekcja_krytyczna_P1;
k1=1; // protokół końcowy
sekcja_lokalna_P1;
}
}

//////////////////////////////
proces_P2 ( )
{
while (1)

{

k2=0;

while (k1 =0)

{
k2=1;
delay(n); //czasowa rezygnacja z wejścia do sekcji
//aby P1 mógł wejść
k2=0
}
sekcja_krytyczna_P2;
k2=1; // protokół końcowy
sekcja_lokalna_P2;
}
}

Własności programu

 program jest bezpieczny,

 możliwość wystąpienia ciągłego zagłodzenia dwóch procesów, co

prowadzi do blokady

Rozwiązanie poprawne - algorytm Dekkera - rozwiązuje problem

wzajemnego wykluczania dla dwóch procesów konkurujących ze sobą
o dostęp do zasobu dzielonego przy użyciu trzech zmiennych.

Własności algorytmu

Dekkera

 własność bezpieczeństwa: wzajemnego wykluczania,
 nie występuje w nim blokada,
 żaden proces w nim nie zostanie zagłodzony
 przy braku współzawodnictwa proces może natychmiast wejść do

swojej sekcji krytycznej

 posiada możliwość zastosowania na każdym komputerze

WADA: wymaga on aktywnego oczekiwania, czyli pracy procesu w

pętli w oczekiwaniu na zmianę lokacji w pamięci, co jest bardzo
niepożądane ze względu na marnotrawstwo czasu procesora.

W algorytmie tym prawo do nalegania na wejście do sekcji krytycznej

jest jawnie przekazywane między procesami za pomocą zmiennych K1 i
K2. Zmienne te zapewniają już wzajemne wykluczanie, ale po wykryciu
współzawodnictwa proces np. P1 sprawdza w dodatkowej zmiennej
globalnej czyja_kolej , czy teraz jest jego kolej na wejście do sekcji
krytycznej. Jeśli nie to przywraca początkową wartość zmiennej K1
ustępując w ten sposób procesowi P2 i przechodzi w pętlę oczekiwania
na swoją kolej. Gdy P2 kończy swoją sekcję krytyczną zmienia zmienną
czyja_kolej na 1, dopuszczając proces P1 do jego sekcji krytycznej.
Nawet, gdy proces P2 natychmiast zgłosi swoje żądanie na ponowne
wejście do sekcji krytycznej, zostanie on powstrzymany przez zmienną
czyja_kolej, gdy tylko P1 ponownie zgłosi swoje żądanie. Jeżeli jednak
proces P2 pierwszy opuści swoją sekcję lokalną przed procesem P1
(proces P1 jeszcze nie nalega na wejście do sekcji krytycznej, tzn. jest
jeszcze w swojej sekcji lokalnej - nie wykonał jeszcze instrukcji K1=0;)
może on wejść do swojej sekcji krytycznej, pomimo że nie była to jego
kolej.

Wysokopoziomowe mechanizmy

synchronizacji

Semafory

Semafor - abstrakcyjny typ danych zdefiniowany przez Dijkstrę.
Semafor s jest zmienną przyjmującą (w zależności od rodzaju) wartości

całkowite

nieujemne lub wartości logiczne.
nadanie wartości początkowej zmiennej całkowitej (semaforowej),
podnoszenie semafora
opuszczanie semafora

Wszystkie operacje semafora są atomowe, co oznacza, iż nie mogą być
wykonywane w tym samym czasie przez więcej, niż jeden proces.

















procesu

wykonanie

zawie

ś

s

s

zmniejsz

s

s

Czekaj

0

0

)

(

Oznaczenie operacji:
- Nadanie wartości początkowej(s) : sem s=1 //{0,1}
              - Czekaj(s) : wait (s), P(s)
              - Sygnalizuj(s) : signal(s), V(s)
 
Operacja Czekaj(s) (zwana również z ang. Wait(s)) określona jest

następująco:

Znaczenie operacji “zmniejsz s” określone jest w zależności od rodzaju

semafora.

Operacja Sygnalizuj(s): (Signal(s)):

 jeżeli istnieją procesy zawieszone przez semafor (na skutek wykonania

operacji Czekaj(s)), to wznów jeden z nich

 w przeciwnym przypadku zwiększ wartość s.

Definicja nie określa, który proces zostanie wznowiony. Znaczenie operacji

“zwiększ

s” określone jest w zależności od rodzaju semafora.

Ogólny schemat działania semafora

Istnieją procesy zawieszone

przez semafor

Wznów jeden z

zawieszonych

procesów

Wygeneruj błąd

Zwiększ S

S po zwiększeniu przekraczałoby

maksymalną dopuszczalną

wartość

Semafor binarny

Przyjmuje tylko wartości logiczne: prawda oraz fałsz.



















procesu

wykonanie

zawieś

fałsz

s

fałsz

s

prawda

s

s

Czekaj )

(

Sygnalizuj(s):
 jeżeli istnieją procesy zawieszone przez semafor, to wznów jeden z

nich, w przeciwnym przypadku nadaj s wartość prawda

Semafor ogólny
Wartość początkowa jest liczbą nieujemną. Operacje elementarne

przyjmują postać:

Sygnalizuj(S):
 jeżeli istnieją procesy zawieszone przez semafor, to wznów jeden z

nich, w przeciwnym przypadku zwiększ wartość s o jeden (s = s + 1)

Sposoby realizacji wznawiania procesów zawieszonych na semaforze.





















procesu

wykonanie

zawieś

s

s

s

s

s

Czekaj

0

1

0

)

(

Semafory ze zbiorem oczekujących

Procesy zawieszone umieszczane są w zbiorze zawieszonych

procesów. Wznowienie procesu nie określa, który z nich ma
kontynuować działanie. Semafor tego typu łatwo może więc
doprowadzić do zagłodzenia przy obecności co najmniej trzech
procesów. Zaletą tego semafora jest prostota realizacji i nieznacznie
większa szybkość w porównaniu z semaforem z kolejką oczekujących.

Semafory z kolejką oczekujących
Procesy zawieszone umieszczane są w kolejce FIFO. O kolejności

wznawiania decyduje pozycja w tej kolejce – najpóźniej zawieszony
proces zostaje wznowiony. Zaletą tego semafora jest brak możliwości
zagłodzenia jakiegokolwiek procesu.

Zastosowanie semafora
Semafor znajduje zastosowanie do wzajemnego wykluczania procesów

przy próbie wejścia do sekcji krytycznej, umożliwiając jej wykonanie w
danym czasie tylko określonej (przez wartość początkową) liczbie
procesów. Jest on również wykorzystywany w celu wymiany informacji
między procesami.

Zasadę działania operacji semaforowych można przedstawić na rysunku:

Proces A

Proces B

P(S)

V(S)

S:=S-1

S:=S-1

S=0

Ktoś czeka

Zasada działania operacji semaforowych

Strukturalne mechanizmy synchronizacji

Rejony krytyczne

Rejony krytyczne (ang. critical regions) zaproponowali niezależnie
Hoare i Brinch Hansen. Stanowią one czyste przemodelowanie operacji
semaforowych Dijkstry P i V w kierunku strukturalizacji.
Punktem wyjścia do ustalenia odpowiedniej notacji językowej było
stworzenie instrukcji, którą obejmowałaby sekcję krytyczną,
zapewniając dla niej wykluczenie wzajemne. Sekcja krytyczna
najczęściej służy do wykonania operacji na pewnym zasobie, a mówiąc
językiem „programowania" — na pewnej zmiennej określonego typu.
Co więcej zazwyczaj jest niedopuszczalne operowanie na tym obiekcie
poza sekcją krytyczną.

Struktura rejonu krytycznego

Obiekt typu T, na którym są wykonywane operacje wewnątrz sekcji

krytycznej,

nazywamy zmienną dzieloną (ang. shared variable). Jej deklaracja w postaci

var v: shared T;

oznacza zadeklarowanie zmiennej v typu T, która może być używana

wyłącznie w

określonych sekcjach krytycznych. Instrukcja strukturalna, tworząca sekcję
krytyczną dla instrukcji I

1

,...,I

N

związuje ją jednocześnie ze zmienną dzieloną v

region v do I

1

;...; I

N

end

Instrukcję tę nazywamy instrukcją rejonu krytycznego (lub krócej rejonem
krytycznym).

Założenia dotyczące rejonu krytycznego są określone

trzema

warunkami:

(1) Wykonywanie instrukcji wewnątrz rejonów związanych z tą samą

zmienną dzieloną w tym samym czasie przez dwa lub więcej procesów
jest wykluczające się (inaczej mówiąc wewnątrz związanych ze sobą
rejonów krytycznych może pracować co najwyżej jeden proces).

(2) Proces może przebywać wewnątrz rejonu krytycznego w skończonym

czasie, czyli instrukcje operujące na zmiennej dzielonej muszą mieć
możliwość kończenia się.

(3) Wejście do rejonu krytycznego musi być umożliwione dowolnemu

procesowi w skończonym czasie.

Warto zauważyć, że powyższa notacja pozwala kompilatorowi języka, w

którym zostałaby zastosowana, na sprawdzenie, czy odwołania do
zmiennych dzielonych są dokonywane wyłącznie z instrukcji zawartych
wewnątrz odpowiednich rejonów krytycznych.

Rejony krytyczne mogą być wewnątrz siebie zagłębiane na podobnych

zasadach

jak instrukcje cyklu w większości języków programowania.

var z1, z2; shared resource;
procedure p;
begin

region z1 do

. . .

region z2 do
. . .
end; (*z2*)
end (*z1*)

end; (*p*)

Zastosowanie rejonów krytycznych

Przeznaczeniem rejonów krytycznych jest zapewnienie wykluczenia

wzajemnego

procesów, które korzystają z tego samego zasobu.

PRZYKŁAD

Synchronizacja dostępu do zasobów

Należy zsynchronizować dostęp N procesów współbieżnych do zasobu R.

var R: shared resource;
procedure pp;
begin

cycle

przetwarzanie-A;

region R do
request R;
hold(t);

release R

end;

przetwarzanie-B

end

end;
process ( 1..N) pp end.

PRZYKŁAD Producent—konsument
Dla uproszczenia przyjmiemy, że operowanie na buforze dla wszystkich

procesów

producenta i konsumenta powinno odbywać się wewnątrz sekcji krytycznej.

 
 

const N = MAX

var R shared record
buf: array [1..N] of buffer;

lp, lk: integer :=1,1

end;

pełny, pusty: semaphore :=0, N;
procedure producent;

begin
cycle

(* przygotowywanie wiadomości*)

hold(t1);

(*wysłanie wiadomości*)

P (pusty);

region R do

fill buf [lp];

hold(t2);

release buf [Ip]:

lp := lp mod N+1

end;

V (pełny)
end
end; (*producent*)
procedure konsument;

begin

cycle

(* odebranie wiadomości*)
P (pełny);
region R do

quit buf [lk];

hold(t3);

release buf [lk];

lk := lk mod N+1

end;
V (pusty);

(*przetwarzanie *)

hold(t4)

end
end; (*konsument*)
process (1 .. P) producent;
(1 .. K) konsument
end.

Warunkowe rejony krytyczne

Niekompletność rejonów krytycznych, polegająca na braku
prostej komunikacji między procesami, spowodowała rozwój
prac nad ich uzupełnieniem o odpowiednie mechanizmy
komunikacyjne. Pierwsze postulaty rozszerzeń zaproponował
Hoare , natomiast szerokiego ich rozwinięcia i wzbogacenia o
nowe elementy dokonał Brinch Hansen. Powstałe w ten sposób
konstrukcje, jakkolwiek mające często różny zapis, otrzymały
nazwę warunkowych rejonów krytycznych (ang. conditional
critical regions).

Struktura warunkowych rejonów

krytycznych

Ogólna postać warunkowego rejonu krytycznego dopuszcza

wystąpienie między instrukcjami umieszczonymi wewnątrz tego rejonu
(dowolną liczbę razy i w dowolnych miejscach) instrukcji synchronizacji
await

var R:shared T;

. . .

region R do

I

1

; I

2

;...; await W

1

;

. . .

I

i

, I

i+1

;...; await W

j

;

. . .

I

N-1

; I

N

end

Działanie instrukcji await, gdzie W

j

jest wyrażeniem logicznym

(najczęściej zależnym od zmiennej R), polega na tym, że w
czasie jej
wykonywania jest sprawdzany warunek W

j

. Jeżeli jest on

spełniony, to
proces przechodzi do wykonania następnej instrukcji,
natomiast w
przypadku przeciwnym zostaje zawieszony do czasu spełnienia
warunku z jednoczesnym zwolnieniem dostępu do sekcji
krytycznej.

Przyjmując zasadę, że rejony krytyczne powinny być krótkie,
służyć sprawdzaniu i zmienianiu warunków, natomiast inne
operacje (Jak np. wpisywanie do buforu) powinny odbywać się
poza nimi (oczywiście jednak z zapewnieniem wszelkiej
ochrony). Stosując się do tych postulatów przed operacjami
związanymi z buforem, należy za pomocą warunkowego rejonu
krytycznego sprawdzić, czy proces może wykonać dane
operacje i czy nie ma żadnego innego procesu już je
wykonującego. Po zakończeniu działania na buforze Procesy
dokonują wewnątrz rejonu krytycznego zmiany odpowiednich
warunków.

const N = MAX;
var R: shared record
np: integer := 0; (*liczba producentów*)
nk: integer := 0; (*liczba konsumentów*)
m: integer := 0; (*liczba porcji nieodebranych*)
end;
buf: array [1..N] of buffer;
lp, lk: integer := 1,1;
procedure producent;
begin
cycle

( * przygotowanie wiadomości *)
hold(t1);

(*wysłanie wiadomości*)

region R do

await np = 0 and m < N;
np := np +1
end;

fill buf [lp];

hold(t2);
release buf[lp];
lp := lp mod N+1;
region R do
np := np -l;
m := m+1
end
end
end; (*producent*)
procedure konsument;
begin
cycle
(* odebranie wiadomości*)
region R do
await nk = 0 and m > 0;
nk:= nk+1
end;

quit buf[lk];

hold(t3);
release buf [lk];
lk:= lk mod N+1;
region R do
nk := nk— l;
m := m—1
end;
(* przetwarzanie *)
hold{t4)
end
end; (*konsument*)
process (1..P) producent;
(1..K) konsument
end.

PRZYKŁAD

Czytający-piszący

W przykładzie podamy rozwiązanie drugiej wersji tego problemu.
Opierać się ona będzie na sprawdzeniu relacji między liczbą procesów
czytających, które wykonują operację czytania (lc) i liczbą procesów
piszących, które chciałyby pisać (lp). Warto zauważyć, jak przez
zmianę kolejności operacji wewnątrz rejonu krytycznego można
pewnej grupie procesów zapewnić priorytet w stosunku do procesów
drugiej grupy.

var R : shared record
lc, lp: integer := 0,0

end;

Z: resource;
W: shared boolean := true;

procedure czytanie;
begin
cycle
region R do
await lp = 0;
lc:=lc+1
end;
request Z;
(* czytanie*)
release Z;
region R do
lc:=lc-1
end
end

end; (*czytanie*)

procedure pisanie;

begin
cycle
region R do
lp:=lp+1;
await lc = 0
end;
region W do
request Z;
(*pisanie*)
release Z
end;
region R do
lp:=lp-1
end
end
end;( *pisanie*)
process (1.. N) czytanie;

(1..M) pisanie

end.

Łatwo zauważyć, że rejon krytyczny związany ze zmienną dzieloną W służy do

wykluczenia między sobą procesów piszących w czasie pisania.

Implementacja warunkowych rejonów

krytycznych

Warunkowe rejony krytyczne są naturalnym mechanizmem komunikacji

między procesami, dostosowanym do potrzeb języków wysokiego poziomu.

Pozwalają one na jawne przedstawienie faktu oczekiwania przez dany

proces na spełnienie pewnego warunku dotyczącego zmiennej dzielonej.

Ceną za niewątpliwe zalety tej metody synchronizacji są znaczne

utrudnienia realizacyjne.
Pierwszą propozycję implementacji warunkowych rejonów krytycznych

podał Brinch Hansen . Proces wywołując instrukcję rejonu krytycznego w

zależności od tego, czy sekcja objęta tym rejonem jest wolna czy nie,

przechodzi do wykonania instrukcji rejonu lub jest zawieszany w kolejce

wejściowej związanej z daną zmienną dzieloną (RYS). Wykonując instrukcję

await przy niespełnionym warunku, proces opuszcza czasowo sekcję

krytyczną i zostaje umieszczony w kolejce warunku Q

E

, również związanej z

daną zmienną dzieloną. W tym czasie inne procesy z kolejki Q

V

mogą po

kolei wchodzić do sekcji krytycznej, natomiast procesy z kolejki Q

E

powinny

okresowo sprawdzać, czy nie został spełniony warunek zawieszenia. W

chwili, gdy sekcja krytyczna zostaje zwolniona, a obie kolejki są niepuste,

występuje konflikt dwóch procesów, które powinny wejść do sekcji

krytycznej. W takiej sytuacji musi być podjęta jednoznaczna decyzja i

jednocześnie programista musi być jej świadomy. Propozycją Brinch

Hansena jest, aby wyższy priorytet nadać procesom z kolejki warunku.

RYS. Schemat wykonywania rejonu krytycznego (a) i warunkowego
rejonu
krytycznego (b)

...

SEKCJA

KRYTYCZNA

a)

Q

V

...

SEKCJA

KRYTYCZNA

...

b)

Q

V

Q

E

await

Z powyższego schematycznego algorytmu implementacji
widać od razu kolejną jego wadę. Przy każdorazowym
zwolnieniu sekcji krytycznej należy sprawdzać, czy nie został
spełniony

warunek

dla

któregokolwiek

z

procesów

oczekujących w kolejce warunku, chociaż do rejonu
krytycznego będzie mógł wejść tylko jeden proces, a pozostałe
ponownie zostaną zawieszone. Jest to oczywiście wysoce
nieefektywne, zwłaszcza w przypadku, gdy wiele procesów
może być zawieszonych w tym samym czasie.

PRZYKŁAD Implementacja warunkowych rejonów krytycznych

Celem naszym jest pokazanie realizacji rejonów krytycznych w postaci:
var v: shared T;
. . .
region v do ... await W ... end;
W czasie translacji instrukcji rejonów krytycznych dokonywane jest ich
przekształcenie w instrukcje języka sekwencyjnego, uzupełnione
procedurami realizującymi algorytm działania rejonów. Przekształcenie
to przedstawimy kolejno dla poszczególnych elementów struktury.
(1) Uzupełnienie deklaracji zmiennej dzielonej deklaracją:

var vv: record

v: T;
r: rejon
end;

gdzie pole r typu rejon jest przeznaczone dla potrzeb implementacji.

(2) Zastąpienie instrukcji wejścia do rejonu (region...) instrukcją:
with vv.v do wejscie(vv.r);
 
(3) Zastąpienie instrukcji await instrukcją:

while not W do oczekiwanie(vv.r) end;

(4) Poprzedzenie instrukcji wyjścia z rejonu (end) instrukcją:

wyjście (vv.r) end (* zamyka instrukcję with vv ... *);

W pierwszej wersji implementacji procedur wykorzystamy znane już
operacje kolejkach i procesach. Struktura danych typu rejon ma postać:

type rejon = record

stan: Boolean := false; (*dostępność rejonu*)
Qv, Qe: queue := nil, nil; (*kolejka wejściowa i warunku*)
lqe: integer := 0; (*licznik procesów zawieszonych w Qe*)

pr: proc

end;

Monitory

Monitor jest składnikiem programu, złożonym z deklaracji zmiennych

wspólnych, dzielonych przez kooperujące ze sobą procesy, oraz ze

zbioru wszystkich procedur działających na tych zmiennych. Zazwyczaj

monitor deklaruje się jako zmienną specjalnego typu monitorowego.

Schematyczna postać deklaracji monitora wygląda następująco:

var identyfikator-monitora: monitor

deklaracje-zmiennych;
procedury;
lista-udostępnionych-na-zewnątrz-nazw-procedur
end.

Na zmiennych monitora mogą być wykonywane operacje wyłącznie w

procedurach monitora, przy czym niektóre z tych ostatnich (lub

wszystkie) mogą być wywołane ze środowiska zewnętrznego (np. z

procesów lub innych monitorów). Wywołując procedurę monitora,

należy podać jego identyfikator, nazwę procedury i listę jej

parametrów aktualnych.

identyfikator-monitora.nazwa-procedury(parametry aktualne)

var M: monitor
var R: resource;

procedure A;

begin
. . .
(* operacja A na zasobie R*)
. . .
end; (*A*)

procedure Z;

begin
. . .
(* operacja Z na zasobie R*)
. . .
end;(*Z*)

export A,..., Z

end;(*M*)
. . .
(*proces 1*)
. . .
M.A;
. . .
(*proces N*)
. . .
  M.Z;
. . .

Z kolejką są związane jeszcze dwie pomocnicze operacje:

clear(kol) — procedura przywracająca pierwotny stan kolejki — pusty

(przy powstawaniu monitora kolejki są zawsze puste),

empty(kol) — funkcja sprawdzająca czy kolejka jest

pusta (wartość true), czy nie (wartość false).

Zastosowanie monitorów

PRZYKŁAD Producent-konsument

var bufor: monitor

const N = MAX;

var buf: array [1..N] of buffer;

pełny, pusty: queue;
lp, lk: integer := 1, 1;
m: integer := 0; (*liczba nieodebranych zapełnionych pól buforowych*)

procedure wpisz;
begin

if m = N then delay (pełny) end;
fill buf[lp];

hold(t2);

release buf[lp];

lp := lp mod N+1;

m := m+1;

continue (pusty)

end; (*wpisz*)
procedure pobierz;
begin

if m = 0 then delay (pusty) end;
quit buf[lk];
hold(t3);
release buf [lk];
lk := lk mod N+1;
m := m—1;
continue (pełny)

end; (*pobierz*)

export wpisz, pobierz
end; (*bufor*)
procedure producent;
begin

cycle

(* przygotowanie wiadomości*)

hold(t1)

(* wysłanie wiadomości*)

bufor.wpisz

end
end; (*producent*)

procedure konsument
begin

cycle

(* odebranie wiadomości *)

bufor. pobierz;

(*przetwarzanie*)

hold(t4)

end
end; (*konsument*)
process (1 . .P) producent;
(1 . .K) konsument
end.

Wyrażenia ścieżkowe

Wyrażenia ścieżkowe (ang. path expressions), będące koncepcyjnie
odmiennym mechanizmem synchronizacji procesów współbieżnych,
zostały wprowadzone przez Campbella i Habermanna. Zaproponowana
przez nich metoda opisuje synchronizację na poziomie procedur.
Oznacza to, że każda akcja, która ma podlegać synchronizacji, musi
wystąpić w programie w postaci oddzielnej procedury.
Wzajemne powiązania między tymi procedurami są opisywane przy
użyciu specjalnych operatorów, ustalając warunki, jakie muszą być
spełnione, aby po wywołaniu dana procedura mogła być wykonana.

Zapis wyrażeń ścieżkowych

 

Podstawowymi

powiązaniami

występującymi

w

wyrażeniach

ścieżkowych są sekwencja i selekcja akcji (przez termin akcja
będziemy w tym rozdziale rozumieli wykonanie przez proces
procedury, które, zgodnie z uprzednią definicją pojęcia akcji, będzie
traktowane jako czynność jednostkowa, niepodzielna).

Omówione podstawowe elementy wyrażeń ścieżkowych mogą być
łączone, tworząc bardziej skomplikowane ścieżki. Na przykład ścieżka

p;(q, r);s

 

synchronizuje cztery akcje. Pierwszą z nich musi być wykonanie
procedury p, następnie jednej z procedur q lub r , po czym kolejną
akcją może być tylko wykonanie procedury s. A więc powyższa ścieżka
określa dwie możliwe serie wykonań wymienionych procedur: p-q-s lub
p-r-s (RYS.). W podanym przykładzie zostały  użyte dodatkowe nawiasy
okrągłe; ich znaczenie jest takie samo, jak w wyrażeniach
arytmetycznych. Pozwalają one na sprecyzowanie kolejności
analizowania operatorów w ramach ścieżki (w pracy Campbella i
Habermanna założono jednakowy priorytet wszystkich operatorów
występujących w wyrażeniach ścieżkowych).

RYS. Graf pierwszeństwa dla ścieżki p; (q, r); s

q

p

r

s

Kolejnym elementem sterowania wykonaniem procedur jest ich
równoczesność. Pozwala ona na równoległe wykonywanie danej
procedury lub fragmentu wyrażenia ścieżkowego przez kilka procesów.
Operatorami równoczesności są nawiasy kątowe <i> (oryginalnie
zaproponowano nawiasy {i}, które jednak zazwyczaj nie występują
wśród

znaków

w

urządzeniach

peryferyjnych).

Przykładem

zastosowania równoczesności może być ścieżka

<q; s>

Przykładem bardziej skomplikowanej ścieżki może być wyrażenie

path n,(p; <q ; s>) end

Zastosowanie wyrażeń ścieżkowych

Wyrażenia ścieżkowe są jasną i zwięzłą metodą opisu synchronizacji

dla szerokiej klasy problemów. Zasady stosowania wyrażeń

ścieżkowych pokażemy na podstawie kilku wersji przykładu współpracy

procesów czytających i piszących.

PRZYKŁAD Czytający-piszący
Najprostszą synchronizację obu grup procesów można przedstawić

następująco:

var

R: resource;

procedure czytanie;
begin
reguest R;
(* czy tanie*)
release R

end; (*czytanie*)

procedure pisanie;

begin

request R;
(*pisanie*)

release R
end; (*pisanie*)
procedure czyt;
begin
cycle
czytanie
end

end;(*czyt*)

procedure pisz;
begin

cycle

pisanie
end
end; (*pisz*)
path czytanie, pisanie end;
process (1..N) czyt;
(1..M) pisz
end.

Zastosowane wyrażenie ścieżkowe synchronizuje wykonywanie
procedur czytanie i pisanie w taki sposób, że w każdej chwili może być
realizowana tylko jedna z nich przez dokładnie jeden proces.
Wyrażenie to nie określa również kolejności wykonywania obu tych
procedur.
Wymiana użytej ścieżki przez

path <czytanie>, pisanie end;

powoduje, że procedura czytanie może być realizowana równocześnie
przez kilka procesów. Jeżeli jakiś proces rozpoczął czytanie, to dostęp
do tej procedury będzie natychmiastowy dla innych procesów tale
długo jak długo procedura ta będzie wykonywana przez co najmniej
jeden proces (priorytet czytania jest wyższy niż pisania).

W celu wyrównania priorytetów obu operacji czytania i pisania należy
poprzednią ścieżkę zastąpić wyrażeniem

path <czytanie>, <pisanie> end;
path pisanie end

 

Pierwsza ścieżka zapewnia równość priorytetów obu operacji,
natomiast druga wykluczenie wzajemne wykonania procedury pisanie.
Analiza tego rozwiązania pokazuje, że jego wadą jest blokowanie
dostępu do zasobu — jeżeli jakiś proces zacznie czytać (lub pisać), to
ze względu na równoczesność przez pewien czas może być blokowany
dostęp dla zapisu (odczytu).
Zlikwidowanie blokowania jest możliwe przez dodanie do poprzedniego
rozwiązania procedury pustej zgłoszenie-czytania

procedure zgłoszenie-czytania,
begin end;

zmienienie procedury czyt;

procedure czyt;
begin
cycle
zgloszenie-czytania;
czytanie
end
end; (*czytanie*)
oraz wymianę wyrażenia ścieżkowego na
path zgłoszenie-czytania, pisanie end;
path <zgłoszenie-czytania; czytanie>, pisanie end;
 
 

Proces czytający musi obecnie wykonać sekwencję procedur
zgłoszenie-czytania i czytanie. Pierwsza z nich jest procedurą
pomocniczą,

której

jedyną

funkcją

jest

zapewnienie

pojedynczego przyjmowania żądań czytania lub pisania w
czasie wykonywania tych operacji. Tak więc pierwsza ścieżka
powoduje, że szanse startu operacji czytania i pisania są
równe. Jeżeli została wykonana procedura zgłoszenie-czytania,
to druga ścieżka powoduje, że pisanie będzie mogło być
realizowane dopiero po wykonaniu procedury czytanie.
Równoczesność w drugiej ścieżce pozwala na równoległe
czytanie przez wiele procesów czytających pod warunkiem, że
nie nadeszły żadne żądania zapisu informacji.

Powyższe rozwiązanie odpowiadało pierwszemu problemowi

piszących i czytających. Rozwiązanie drugiego problemu, w
którym procesy piszące mają wyższy priorytet, wymaga
pewnej modyfikacji wyrażenia ścieżkowego do postaci

path zgłoszenie-czytania end;

path zgłoszenie-czytania, <pisanie> end;
path <zgłoszenie-czytania; czytanie>, pisanie end;

Mechanizmy komunikacji i synchronizacji w

systemie Unix

Współbieżność procesów w systemie Unix

Unix jest systemem wielozadaniowym i wielodostępnym, co oznacza,
że w jednym momencie z jednego komputera może korzystać wielu
użytkowników, oraz że każdy użytkownik może uruchomić w danej
chwili więcej niż jeden proces. Proces jest to środowisko wykonania
programu, które składa się z segmentu instrukcji, segmentu danych
użytkowych oraz segmentu danych systemowych, podczas gdy
program jest to plik zawierający instrukcje i dane służące do inicjacji
segmentu instrukcji oraz segmentu danych użytkowych procesu.
Pojęcie jednoczesnego (współbieżnego) wykonywania wielu procesów
na maszynie jednoprocesorowej jest w znacznym stopniu umowne i
oznacza ono podział czasu procesora pomiędzy wykonywane procesy.

Jednym z dobrodziejstw systemu operacyjnego Unix jest możliwość

rozwidlania

procesów.

Rozwidlający

proces

zwany

procesem

macierzystym tworzy procesy potomne, podczas gdy każdy z procesów

potomnych ma możliwość tworzenia następnych procesów. Pozwala to

nam na współbieżne wykonywanie np. procedur obliczeniowych, co

zwłaszcza przy maszynach wieloprocesorowych lub podziale obowiązków

na kilka komputerów korzystnie może wpłynąć na czas trwania obliczeń.

Mówiąc o rozwidlaniu procesów nie można nie wspomnieć o metodach

komunikacji i synchronizacji międzyprocesowej. O tym jak ważne jest to

zagadnienie niech świadczy poniższy przykład. Niech zagadnieniem

procesu P1 będzie odjęcie z zasobu dzielonego wartości 5 (student

podejmuje pieniądze na książki z konta bankowego). W tym celu

odczytuje aktualną wartość konta np. 5,00 , odejmuje od niej wartość 5 i

otrzymaną różnicę (0,00) właśnie chce zapisać jako nowy stan kąta. Lecz

w tym momencie proces P2 (dział ds. stypendiów naukowych ) przelewa

na konto stypendium w wysokości 20. W tym celu odczytuje wartość 5,00

(ciągle jest tam niezmieniona wartość) i dodaje do niej 20. Cały przelew

trwał „ułamek sekundy” , nowa wartość to 25,00. Proces P1 dokańcza

operację zapisu nowej wartości (tej początkowej pomniejszonej o 5) i stan

kąta wynosi 0,00. W wyniku tych operacji konto studenta posiada

nieprawidłową wartość.

Jednak system operacyjny Unix dostarcza nam całą gamę

przeróżnych

mechanizmów

komunikacji

i

synchronizacji

międzyprocesowej. W systemach unixowych, które poprzedzały
System III, procesy mogły komunikować się między sobą za pomocą
dzielonych wskaźników do plików, sygnałów, śledzenia procesów,
plików oraz łączy komunikacyjnych – potoków. W Systemie III
zastosowano kolejki proste FIFO (łącza nazwane). W Systemie V
pojawiły się semafory, komunikaty oraz pamięć dzielona, potem
zdalne wywołanie procedur w systemie Unix BSD.

Dzielone wskaźniki do pliku są rzadko używane do komunikacji.
Teoretycznie, jeden proces może ustawić wskaźnik do pliku (na pewne
fikcyjne miejsce na pliku), a drugi może sprawdzić, co ten wskaźnik
wskazuje. To miejsce w pliku stanowiłoby obszar komunikacji.

Sygnały są używane, gdy proces potrzebuje tylko dać znak innemu
procesowi. Za ich pomocą nie można jednak przekazać tylu
informacji, aby mogły być one przydatne w większości zastosowań.
Wadą sygnałów jest to, że powoduje on przerwanie wykonywania
procesu, do którego jest on skierowany. Sygnały służą głównie do
kończenia wykonywania procesów.

Śledzenie procesów służy do kontrolowania przez proces swoich

potomków. Proces macierzysty może czytać oraz pisać w obszarze danych
swego potomka, co pozwala im na wspólną komunikację.

Pliki są najbardziej powszechną metodą komunikacji międzyprocesowej,

nie są jednak odpowiednie dla procesów wykonywanych współbieżnie.

Mechanizm łączy komunikacyjnych skutecznie rozwiązuje problemy

synchronizacji między procesami. Pomimo, że łącze, podobnie jak plik, ma
swój i-ty węzeł to dowiązania do niego nie istnieją. Jeżeli proces czytający
wyprzedzi proces piszący, to musi on czekać na następne dane. Jeżeli
proces piszący wyprzedzi proces czytający, to zostanie on wstrzymany, aż
dogoniony zostanie przez proces czytający.

Kolejka FIFO jest plikiem specjalnym, który może zostać otwarty do

czytania lub pisania przez każdy proces mający odpowiednie uprawnienia.
Zagwarantowana jest również niepodzielność wykonywanych operacji.
Bajty danych zapisywane lub odczytywane podczas jednego wywołania
funkcji systemowej tworzą zawsze spójny blok.

Komunikat jest to niewielka liczba danych, którą można przesłać do

kolejki komunikatów. Komunikaty mogą być różnych typów. Proces mający
odpowiednie uprawnienia, może pobierać komunikaty z kolejki.

Przy rozwiązywaniu problemów programowania współbieżnego w tej

pracy

wykorzystane zostały następujące mechanizmy:

- mechanizmy IPC Systemu V :
- semafory,
- pamięć dzielona,
- zdalne wywołanie procedur (RPC- Remote Procedurę Cali, wersja Sun

RPC).

Aby rozwidlić proces w systemie Unix należy w kodzie programu
wywołać funkcję
int fork()

Funkcja fork() tworzy kopię procesu, który tę funkcję wywołał.

Proces wywołujący funkcję fork() nazywa się procesem
macierzystym lub przodkiem (rodzicem) nowego procesu,
nowy zaś proces - procesem potomnym lub potomkiem
(dzieckiem). Funkcja systemowa fork() wywołana raz (przez
proces

macierzysty)

przekazuje

wartość

dwukrotnie

(przodkowi i potomkowi). Te wartości różnią się tym, że w
przypadku

procesu

macierzystego

jest

to

numer

identyfikacyjny nowo utworzonego procesu potomnego, a
wartością przekazywaną procesowi potomnemu jest zero. Gdy
funkcji for k () nie uda się wykonać pomyślnie, wówczas jej
wynikiem jest -1. Jeśli proces potomny chce uzyskać numer
identyfikacyjny swojego przodka, to może wywołać funkcję
systemową getppid () .

Przykład:

main ()

{
int pid_potomka;
if ((pid_potomka=fork())==-1)
perror(„Błąd fork" ) ;
else
if(pid_potomka==0)
/ /proces potomny
printf(„Potomek: pid potomka=%d, pid przodka=

%d\n",getpid(),

getppid());
else
/ /proces macierzysty
printf(„Przodek:pid potomka=%d, pid przodka=%d\n",pid

potomka,

getpid());

Aby zakończyć wykonywanie procesu należy wywołać funkcję

systemową exit()

void exit (int stan)
Argument stan jest wartością stanu końcowego procesu wywołującego

funkcję exit().

Powrót z tej funkcji nigdy nie następuje. Przyjmuje się, że zerowy stan

oznacza poprawne zakończenie procesu, niezerowy zaś (najczęściej -1)
oznacza wystąpienie błędu.

Proces macierzysty procesu kończącego działanie otrzymuje jego kod
stanu przy pomocy funkcji systemowej wait().

int wait(int *stan)

Argument *stan jest miejscem, pod które wstawiony zostanie kod

wyjścia procesu potomnego (argument funkcji exit () ). Funkcja
zwraca identyfikator procesu lub -1 w przypadku błędu.

Jeżeli istnieją procesy potomne, to funkcja systemowa wait() czeka na
zakończenie jednego z nich. Nie można zlecić czekania na określony
proces potomny. Potomek, który pierwszy zakończy działanie,
powoduje „odwieszenie" rodzica, który wywołał wait().Jeśli wskaźnik
stan ma wartość NULL, stan zakończenia procesu potomnego nie jest
nigdzie zapamiętany.

Semafory
W systemie UNIX operacje semaforowe (chociaż w dalszym ciągu
najważniejsze to nadanie wartości początkowej, zwiększenie i
zmniejszenie) nie wyglądają już tak prosto.
Operacji P(S) (opuszczenie) odpowiada wywołanie funkcji
semop() z następującymi argumentami:

struct sembuf sem_lock={0,-1,0};
semop(sid,&sem_lock,1);

Aby używać semaforów w programach pisanych w języku C

należy do ich treści dołączyć za pomocą dyrektywy #include

następujące pliki:

#include <sys/types.h>
#include <sys/ipc.h>
#include <sys/sem.h>

Oto funkcja zablokuj() odpowiadająca operacji P(S). Argument

sid jest numerem identyfikacyjnym zestawu semaforów

zwróconym przez funkcję semget(), zaś numer_semafora jest

kolejnym numerem semafora w zestawie licząc od zera.

void zablokuj (int sid, int numer_semafora)
{

int wartosc;
struct sembuf sem_lock={numer_semafora,-1,0};
wartosc=semctl(sid,numer_semafora,GETVAL,0);
if(!wartosc)

{
fprintf(stderr,"PID:%d-Proces wstrzymany na semaforze !\n",getpid());

fflush(stdout);

}

i f ( ( semop (sid, &sem_lock, 1) ) ==-1)

{

fprintf (stderr, "PID: %d-Blokowanie nie powiodlo sie!\n", getpid ());

f flush (stdout) ;

exit (EXIT_FAILURE) ;

}

else
printf ( "PID : %d-Semafor opuszczony do wartosci %d\n",
getpid ( ) , wartosc) ;
}

Wywołanie wartosc=semctl (sid,numer_semafora,GETVAL, 0)

nadaje zmiennej wartość aktualną wartość semafora o
numerze podanym jako drugi argument.

Natomiast operacji V(S) - podniesienie ,odpowiada wywołanie

funkcji semop() z następującymi argumentami:

struct sembuf sem_lock={0,1,0};
semop(sid,&sem lock,1);

Oto funkcja odblokuj() odpowiadająca operacji V(S).

void odblokuj (int sid, int numer_semafora)
{

struct sembuf sem_unlock={numer_semafora,1,0};
int wartosc;

i f ( (semop (sid, &sem_unlock, 1) ) ==-1)

{

fprintf (stderr, "PID: %d-0dblokowanie nie powiodlo sie!

\n",getpid() ) ;
fflush (stdout) ;
exit (EXIT_FAILURE) ;
}
else
}

wartosc=getval (sid, numer_semafora) ;

printf ( "PID: %d-Semafor opuszczony do wartosci %d\n",
getpid(), wartosc );
}

}

System UNIX daje nam możliwość wykonywania jednoczesnych

operacji semaforowych, przy czym każda z nich może być inna.
Wykonanie operacji jednoczesnej wtedy kończy się sukcesem,
gdy zostaną wykonane wszystkie jej operacje składowe.

Poniższy kod wykonuje zablokowanie semafora o numerze

SEMAFOR_PELNE (element sem_num struktury sembuf ustawiony
na -1) z jednoczesnym odblokowaniem semafora o numerze
SEMAFOR_CK (element ten ustawiony na 1) z zestawu semaforów
identyfikowanego przez zmienną sid (wartość zwrócona przez
semget()). Operacja ta będzie blokująca, tzn. w przypadku
zajętych zasobów proces będzie tak długo czekał z wywołaniem
funkcji semop() dopóki jakiś inny proces ich nie zwolni (element
sem_flg struktury sembuf nie jest ustawiony na IPC_NOWAIT).

struct sembuf sops[2];

sops[0].sem_num=SEMAFOR_PELNE;
sops[0].sem_op=-1;
sops[0].sem_flg=0;
sops[1].sem_num=SEMAFOR_CK;
sops[1].sem_op=1;
sops[1].sem_flg=0;

if((semop(sid,sops,2)==-1)

{

fprintf(stderr,"PID:%d-Blokowanie nie powiodlo sie!\n",getpid());

exit(EXIT_FAILURE);

}

Funkcje systemowe Unixa dotyczące semaforów:

1.

key_t ftok (char *ścieżka, char projekt)

Funkcja ftok () przekształca nazwę ścieżki i identyfikator projektu na

klucz, używany w komunikacji międzyprocesowej. Klucze służą do
identyfikowania kolejek komunikatów, semaforów i pamięci dzielonej.
Typ danych key_t znajduje się w pliku <sys/types . h> .

Procesy, które korzystają z jednej lub kilku metod komunikacji

międzyprocesowej powinny mieć uzgodnioną nazwę ścieżki oraz
identyfikator projektu aby mieć pewność, że procesy korzystają z tego
samego kanału komunikacyjnego /tego samego zestawu semaforów
/tego samego obszaru pamięci dzielonej.

Funkcja zwraca nową wartość klucza na podstawie kombinacji numeru

i-węzła i podrzędnego numeru urządzenia z pliku podanego w
argumencie ścieżka wraz z identyfikatorem projektu podanym jako
drugi argument, lub -1 w przypadku błędu. Może to nastąpić np. gdy
nazwa ścieżki określona argumentem ścieżka nie istnieje, lub gdy nie
jest dostępna dla procesu wywołującego funkcję ftok () .

Przykład:
key_t klucz; klucz=ftok(".",'S')
printf("Wartość klucza wygenerowanego przy pomocy ftok() :%x\n"

,klucz);

Efekt działania programu:
[root@localhost /root]# Wartość klucza wygenerowanego przy pomocy

ftok():53454d55

2.
int semget(key_t klucz, int nsems, int semflg)

Wywołanie systemowe semget () tworzy nowy zestaw semaforów lub
uzyskuje dostęp do już istniejącego. Zwraca identyfikator IPC zestawu semaforów
przy pomyślnym wykonaniu lub -1 w przypadku błędu.

Argument klucz jest wartością zwróconą przez funkcję f tok () .
Argument nsems określa liczbę semaforów ,które zostaną utworzone dla nowego
zestawu. W przypadku otwarcia już istniejącego zestawu semaforów argument

ten

jest ignorowany, możemy nadać temu argumentowi wartość 0.

Argument semflg mówi o tym, czy ma być utworzony nowy zestaw,

czy też będzie używany już istniejący.

Gdy semflg jest równe:

IPC_CREAT - zostanie utworzony nowy zestaw semaforów jeżeli do tej
pory nie istniał. Semget () zwraca identyfikator zestawu, który został
utworzony lub identyfikator już istniejącego, który posiada podaną
wartość klucza. IPC_CREAT|IPC_EXCL - zostanie utworzony nowy
zestaw semaforów lub semget () zwróci błąd. Gwarantuje to, że nie
będzie używany już istniejący zestaw.

Przykład:

semid=semget(klucz,l,0666|IPC_CREAT|IPC_EXCL)

Wynikiem takiego wywołania będzie nadanie zmiennej semid numeru

identyfikacyjnego nowoutworzonego zestawu semaforów złożonego z
jednego semafora (drugi argument funkcji) lub -1 w przypadku, gdy
zestaw semaforów o wartości klucza równej parametrowi klucz już
istnieje. Nowoutworzony zestaw będzie posiadał prawa czytania i
pisania dla właściciela, grupy oraz innych użytkowników (prawa 0666).

3.

int semop(int semid, struct sembuf *sops, unsigned nsops)
Wywołanie systemowe semop () umożliwia wykonywanie
operacji na semaforach, zwraca 0 gdy sukces, -1 w przeciwnym
wypadku.
Argument semid jest numerem identyfikacyjnym zestawu semaforów
zwróconym przez semget().
Argument sops jest wskaźnikiem do tablicy operacji, które mają zostać
przeprowadzone na grupie semaforów. Wskazuje to na tablicę
następujących struktur zdefiniowanych w <sys/sem.h>:

struct sembuf
{
ushort sem_num; //numer semafora

short sem_op;

//operacja (dodatnia, ujemna lub

zero)

short sem_flg;

//flagi operacji

}

Gdy sem_op jest ujemny jego wartość zostaje odjęta od

wartości semafora. Odpowiada to zajęciu (zablokowaniu)
zasobów. Jeżeli nie ustawiono semjlg na IPC_NOWAIT proces
wywołujący funkcję semop() śpi do czasu aż wymagana
liczba będzie dostępna.

Gdy sem__op jest dodatni jego wartość jest dodawana do

semafora. Odpowiada to zwolnieniu (odblokowaniu) zasobów.

Gdy sem_op jest równy zero to proces wywołujący funkcję

semop() będzie czekał, aż wartością semafora będzie zero.

Argument nsops jest liczbą operacji w tablicy (liczba

elementów tablicy struktur).

Przykład:
void locksem(int sid)
{
struct sembuf sem_lock={0,-1, 0 };
if((semop(sid,&sem_lock,1))==-!)

{
fprintf(stderr,"PID:%d-Blokowanie semafora nie powiodło sie!\n",
getpid());

fflush(stdout);

exit(EXIT FAILURE);
}

}
Funkcja ta powoduje opuszczenie (zablokowanie) semafora o numerze 0 z

zestawu identyfikowanego przez sid (parametr zwrócony przez funkcję
semget ())

4.

int semctl(int semid, int semnum, int cmd, imion semun arg)

Wywołanie systemowe semctl() używane jest do kontrolowania zestawu

semaforów,

zwraca 0 gdy sukces, -1 w przeciwnym wypadku.
Argument semid jest numerem identyfikacyjnym zestawu semaforów zwróconym
przez semget().
Argument semnum jest numerem semafora w zestawie (liczonym od zera).
Argument cmd jest komendą, która ma zostać wykonana:

IPC_STAT - pobiera strukturę semid_ds i zachowuje ją pod adresem buf
argumentu semun.

IPC_SET - ustawia wartość ipc_perm struktury semid_ds. Wartość pobiera z buf

unii semun.
IPC_RMID - usuwa zestaw z jądra.
GETALL - Używany do pobierania wartości wszystkich semaforów z zestawu.

Wartości całkowite przechowywane są w tablicy unsigned short int wskazanej przez
array - członka unii semun.

GETNCNT - zwraca ilość procesów oczekujących na zasoby.

GETPID - zwraca PID procesu, który jako ostatni wywołał semop().
GETYAL - zwraca wartość pojedynczego semafora z zestawu.
SETALL - ustawia wartości wszystkich semaforów wartościami z
tablicy array zawartej w unii semun.
SETY AL - ustawia wartość jednego semafora z zestawu. Wartość
pobiera z val zawartego w unii semun.

Argument arg jest elementem typu semun.Typ ten jest unią

zadeklarowaną w <sys/sem.h>

union semun {

int val;

/* wartość dla SETVAL */

struct semid_ds *buf; /* bufor dla IPC_STAT i IPC_SET */
unsigned short int *array; /* tablica dla GETALL i SETALL
*/
struct seminfo * _buf; /* bufor dla IPC INFO */

}

Przykład:

semval = semctl(sid,0,GETVAL, 0) ;

Funkcja zwróci wartość semafora o numerze 0 z zestawu

identyfikowanego przez sid (parametr zwrócony przez funkcję semget
() ).

union semun unia_sem;

if (semctl(semid, 0,IPC_RMID,unia_sem)==-1)
fprintf(stderr, "Nie udało sie usunac semafora\n");
else

printf("Semafor został usuniety\n");

Funkcja semctl () w tym przypadku usunie zestaw semaforów
identyfikowany przez semid (parametr zwrócony przez funkcję
semget()), złożony z jednego semafora ( drugi argument).

Dla każdego zestawu semaforów w systemie przydzielona jest jedna

struktura semid_ds.
struct semid_ds {
struct ipc_perm sem_perm;
time_t sem_otime;
time_t sem_ctime;
struct sem *sem_base;
struct wait_queue *eventn;
struct wait_queue *eventz;
struct sem_undo *undo;
ushort sem nsems;

};
Najważniejsze z elementów struktury to:
sem_perm -jest to struktura typu ipc_perm, który jest zdefiniowany w sys/ipc

. h.

Przechowuje prawa dostępu, oraz informacje o twórcy i właścicielu zestawu;
sem_otime - czas ostatniej operacji semop ();
sem_ctime - czas ostatniej zmiany struktury. Np. zmiana praw;
sem nsems - liczba semaforów w zestawie.

Aby pobrać strukturę semid_ds należy wywołać funkcję semctl()

z parametrem IPC_STAT:

union semun semopts;
struct semid_ds moja_ds;

semopts.buf=&moja_ds; //pobranie aktualnej wartości

struktury

semctl(sid,0,IPC_STAT,semopts);
printf(„Stare prawa dostępu :%o\n", semopts.guf->sem_perm.mode);

Aby zapisać zmiany w strukturze należy wywołać funkcję semctl() z

parametrem IPC_SET:

sscanf(nowe_prawa,"%ho",&semopts.buf->sem_perm.mode);
semctl(sid,O,IPC SET,semopts);

Pamięć dzielona.

Pamięć dzielona jest najszybszym z mechanizmów IPC, ponieważ nie
istnieje żaden pośrednik. Dane w niej umieszczone przez proces piszący
stają się natychmiast dostępne dla innych procesów. Pamięć dzielona
pozwala na dostęp do tej samej, logicznej pamięci kilku nie
spokrewnionym procesom. Jest bardzo wydajną metodą przekazywania
danych.
Pamięć dzielona jest specjalnym zakresem adresów, tworzonych prze
IPC na użytek jednego procesu i pojawiającym się w jego przestrzeni
adresowej. Inne procesy mogą następnie dołączyć segment pamięci
dzielonej do swojej przestrzeni adresowej. Segment pamięci dzielonej
może zostać utworzony przez jeden proces, a korzystać z niego może
dowolna liczba procesów. Wszystkie procesy mogą używać pamięci
dzielonej tak samo, jakby została ona przydzielona funkcją malloc().
Dokonanie zapisu do pamięci dzielonej prze jeden z procesów
spowoduje, że będą one widoczne również dla innych procesów
mających do niej dostęp. Może istnieć kilka segmentów pamięci
dzielonej, z których każdy jest dzielony przez określony podzbiór
aktywnych procesów. Każdy proces może mieć dostęp do kilku
segmentów pamięci dzielonej.

Pamięć dzielona nie udostępnia żadnych mechanizmów synchronizacji

procesów. Nie ma możliwości, aby automatycznie zapobiegać
odczytywaniu pamięci przez jeden proces, zanim inny nie zakończy jej
zapisywać. W tym celu należy samemu zapobiec takiej sytuacji, np. tak
jak to zostało zrobione w tej pracy, używając semaforów.

Funkcje systemowe Unixa dotyczące pamięci dzielonej.
1.
int shmget(key t klucz, int size, int shmflg)

Wywołanie systemowe shmget () tworzy nowy segment pamięci

dzielonej lub uzyskuje dostęp do już istniejącego. Zwraca identyfikator
IPC segmentu pamięci przy pomyślnym wykonaniu lub -1 w przypadku
błędu.

Argument klucz jest wartością zwróconą przez funkcję f tok () .
Argument size określa rozmiar nowotworzonego obszaru pamięci
dzielonej.
Argument shmflg mówi o tym, czy ma być utworzony nowy segment,
czy też będzie używany już istniejący.

Gdy shmflg jest równe:
IPC CREAT - zostanie utworzony nowy segment pamięci dzielonej jeżeli
do tej pory nie istniał. Shmget () zwraca identyfikator segmentu,
który został utworzony lub identyfikator już istniejącego, który
posiada podaną wartość klucza.
IPC_CREAT|IPC_EXCL - zostanie utworzony nowy segment pamięci
lub shmget () zwróci błąd. Gwarantuje to, że nie będzie używany już
istniejący obszar.

Przykład:

shmid=shmget(klucz,100,0666 IPC CREAT IPC EXCL)

Wynikiem takiego wywołania będzie nadanie zmiennej shmid numeru
identyfikacyjnego nowoutworzonego obszaru pamięci dzielonej o
wielkości 100 bajtów (drugi argument funkcji) lub -l w przypadku, gdy
obszar pamięci o wartości klucza równej parametrowi klucz już istnieje.
Nowoutworzony segment będzie posiadał prawa czytania i pisania dla
właściciela, grupy oraz innych użytkowników (prawa 0666).

2.

int shmat(int shmid, char *shmaddr, int shmflg)

Wywołanie systemowe shmat () służy do podłączenia (mapowania)
segmentu pamięci dzielonej w obszar adresowy. Shmat () zwraca adres
pod którym segment został przyłączony do procesu lub -1 w przypadku
błędu.
Argument shmid jest numerem identyfikacyjnym segmentu
pamięci dzielonej zwróconym przez shmget () .

Argument shmadrr powinien być ustawiony na 0. W takim przypadku
jądro wybiera adres dla procesu wywołującego. W innym przypadku
musimy zrobić to sami. Jeżeli nie chcemy wymuszać stronicowego
wyrównania adresu (zaokrąglenia w dół do najbliższego rozmiaru
strony) ani nie chcemy aby segment został wmapowany jako
"tylko_do_odczytu" (SHM_RDONLY) argument shmflg ustawiamy na
zero.

Przykład:

if((segptr=shmat(shmid,0,0))==-1)

{
perror(”shmat”);
return(1);
}

3.

int shmctl(int shmid, int cmd, struct shmid ds *buf)

Wywołanie systemowe shmctl () używane jest do kontrolowania
segmentu pamięci dzielonej, zwraca 0 gdy sukces, -l w przeciwnym
wypadku. Argument shmid jest numerem identyfikacyjnym obszaru
pamięci zwróconym przez shmget(). Argument cmd jest komendą,
która ma zostać wykonana:
IPC_STAT - pobiera strukturę shmid_ds i zachowuje ją pod adresem buf.

IPC_SET - ustawia wartość ipc_perm struktury shmid_ds. Wartość pobiera z
argumentu buf.
IPC_RMID - zaznacza segment do usunięcia.
Argument buf jest wskaźnikiem do elementu typu shmid_ds. Typ ten jest

strukturą

zadeklarowaną w <sys/shm.h>
Podanie komendy IPC_RMID nie usuwa segmentu, lecz go tylko zaznacza do
usunięcia. Ostateczne usunięcie segmentu następuje po odłączeniu segmentu
przez ostatni proces. Przykład:
Aby zaznaczyć do usunięcia segment należy wywołać funkcję

shmctl() z

parametrem IPC_RMID

shmctl(shmid,IPC_RMID,0);

Aby pobrać strukturę semid_ds należy wywołać funkcję shmctl () z
parametrem IPC STAT:
char *prawa;
struct shmid_ds struktura_ds;
shmctl(shmid,IPC_STAT,&struktura_ds);
printf("Stare prawa dostępu: %o\n" , struktura__ds . shm_perm.mode) ;

Aby zapisać zmiany w strukturze należy wywołać funkcję shmctl() z
parametrem IPC_SET:

printf("Podaj nowe prawa :");
scanf("%o",prawa);
struktura__ds . shm_perm.mode=*prawa;
if((shmctl(shmid,IPC_SET,&struktura_ds))==-1)
printf("Błąd shmctl\n"};
else
printf("Zaktualizowano prawa dostępu..\n",struktura ds.shm
perm.mode ) ;

4.

int shmdt(char *shmaddr)

Wywołanie systemowe shmdt () odłącza segment pamięci dzielonej,
zwraca 0 gdy sukces, -1 w przeciwnym wypadku.

Argument shmaddr jest wskaźnikiem do obszaru pamięci dzielonej
(wartość zwrócona przez shmat () ).

Aby zobaczyć aktualnie istniejące mechanizmy IPC należy z linii
komend wydać polecenie ipcs. Uzyskamy w ten sposób informacje na
temat istniejącego klucza, numeru identyfikacyjnego utworzonych
mechanizmów IPC, właściciela mechanizmu, prawach dostępu do
niego, liczby bajtów segmentu oraz liczby procesów z niego
korzystających w przypadku pamięci dzielonej, liczby semaforów w
zestawie.

Przykładowy wynik wykonania polecenia ipcs na ekranie

terminala:

—— Shared Memory Segments ———

key shmid owner perms bytes nattch status
0x53454d55 1 root 666 50 0

—— Semaphore Arrays ——

key semid owner perms nsems status
0x53454d550 root 666 6

—— Message Queues ———
key msqid owner perms used-bytes messages

Rozwiązywanie problemów wzajemnego

wykluczania za pomocą semaforów

Dzięki semaforom w prosty sposób można zrealizować wzajemne

wykluczanie. Wystarczy do tego jeden semafor binarny.

binarny_semafor S=1; // wartość początkowa semafora ustawiona na 1
process P
{

while (TRUE)
{
sekcja_lokalna;
P(S); // opuszczenie ( zablokowanie ) semafora
sekcja_krytyczna; // korzystanie z zasobu dzielonego
V(S);

// podniesienie ( odblokowanie ) semafora

}

}
 

Ponieważ wartość początkowa semafora jest równa 1 tylko
jeden proces będzie mógł wykonać P(S) natychmiast.
Pozostałe procesy będą musiały poczekać, aż proces ten
wykona operację V(S), inaczej mówiąc pozostałe procesy będą
wstrzymane na semaforze S.

Wzajemne wykluczanie
Funkcja proces(czas_kryt,
czas_lok)

Początkowa wartość
semafora:
SEMAFOR_WW=1;

Protokół
wstępny

Zablokuj(SEMAFOR_WW)

Wyświetl(znak)

Czekaj(czas_kryt)

Wyświetl(znak)

odblokuj(SEMAFOR_WW)

Czekaj(czas_lok)

Sekcja
krytyczna

Protokół
końcowy

Sekcja
lokalna

Rozwiązywanie problemu wzajemnego

wykluczania z tablicą czasów trwania sekcji

za pomocą semaforów

Aby do rozwiązania problemu wzajemnego wykluczania za pomocą

semaforów wprowadzić możliwość podawania z klawiatury czasów
przebywania procesów w ich sekcji lokalnej i krytycznej, należało te
procesy w jednoznaczny sposób zidentyfikować.
Każdy proces w systemie Unix otrzymuje od niego numer nazywany
numerem identyfikacyjnym procesu (PID). Daje to programiście
możliwość kontroli nad rozwidlonymi procesami. Aby uruchomić
funkcję proces() z parametrami czas_krytyczny i czas_lokalny należało
najpierw (po rozwidleniu procesu macierzystego na liczbę procesów
podanych przez użytkownika) gdzieś zapisać PID-y każdego z
procesów. Posłużyła do tego pamięć dzielona. Przez ograniczenie liczby
procesów do 10 otrzymano rozmiar pamięci dzielonej 10*sizeof(int) .

Numery procesów zostały zapisane w kolejności zgłoszenia się. Do
zapewnienia wzajemnego wykluczania procesów chcących zapisać
swój PID do obszaru pamięci dzielonej należało zastosować tradycyjnie
jeden semafor (w programie został on nazwany SEMAFOR_CZASY ). Do
indeksacji miejsca wstawiania PIDu użyto także semafora
( SEMAFOR_INDEX ). (patrz rys. Funkcja zapisz_pid( ) ) Następnie
każdemu z procesów przyporządkowany został zestaw danych
składający się z dwóch liczb zmiennopozycyjnych odpowiadających
kolejno czasowi przebywania procesu w sekcji krytycznej i w sekcji
lokalnej. Mając już zestaw potrzebnych parametrów uruchomiono
funkcję

proces(czas_kryt,

czas_lok)

(patrz

rys.

Funkcja

proces(czas_kryt, czas_lok) ).

‘p
’

‘u’

START

Generowanie

klucza

klucz=ftok()

Menu()

Zainicjuj_zestaw_semaforów_i_pamięć_dzieloną(rozmiar_m
agazynu,klucz)

Usuń_semafor_i_p

amięć_dzieloną()

Otwórz_zestaw_semaforów_i_

pamięć_dzieloną(klucz)

Otwórz_zestaw_semaforów_i_

pamięć_dzieloną(klucz)

Liczba
procesów ?

Wczytaj tablicę

czasów

Wybierz czasy kryt. i lokal. z tablicy
odpowiadające indeksowi PID-u w
pamięci dzielonej

Rozwidl (liczba_procesów)

Zapisz PID do pamięci

dzielonej

Uruchom proces(czas_kryt,

czas_lok)

............
....

.............
...

‘i
’

EXIT

Wybierz czasy kryt. i lokal. z tablicy
odpowiadające indeksowi PID-u w
pamięci dzielonej

Zapisz PID do pamięci

dzielonej

Uruchom proces(czas_kryt,

czas_lok)

Rozwiązanie problemu wzajemnego
wykluczania z tablicą czasów trwania sekcji
za pomocą semaforów