Programowanie współbieżne i rozproszone

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

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

/4)+n

/8)+n

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

Sortowanie równoległe

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

liczba operacji dla jednej tablicy (n/2)

/2 = n

liczba operacji potrzebnych do posortowania 2 tablic n

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

PROCESOR

WSPÓLNA PAMIĘĆ

System rozproszony

SIEĆ LOKALNA

PROCESOR

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;

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

, ... , P

}. 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;
           }
}

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

zmniejsz

Czekaj

)

(

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

prawda

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ś

Czekaj

)

(

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=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

,...,I

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

region v do I

;...; I

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

;...; await W

;

. . .

, I

i+1

;...; await W

;

. . .

N-1

; I

end

Działanie instrukcji await, gdzie W

jest wyrażeniem logicznym

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

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

, również związanej z

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

mogą po

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

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

...

SEKCJA

KRYTYCZNA

...

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

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

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

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

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

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;

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

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

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:

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

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

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

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);
}

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

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

}

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

Document Outline