Strona główna

Zaawansowane Systemy Programowania


Pobieranie 119.75 Kb.
Data18.06.2016
Rozmiar119.75 Kb.

Zaawansowane Systemy Programowania




Wojciech Penczek, prof. AP

Celem wykładu jest przedstawienie fragmentu inżynierii oprogramowania, który zajmuje się komputerowo wspomaganymi technikami modelowania, opisu i projektowania oprogramowania systemów rozproszonych, ze szczególnym uwzględnieniem protokołów komunikacyjnych.
Omówione będą techniki, które zostały znormalizowane w ramach ISO (International Standards Organization) ze względu na bogate doświadczenie w praktyce projektowej i istniejące profesjonalne narzędzia komputerowe.
Zostaną omówione i porównane takie wyspecjalizowane techniki jak Estelle, SDL i LOTOS, ich typowe zastosowania i komputerowe środowiska wspomagające ich używanie.

Wykład będzie ilustrowany przykładami, a studenci będą mieć za zadanie wykonanie i przeanalizowanie niewielkiego projektu posługując się formalizmem Estelle i stosując dostępne narzędzia EDT: Estelle Development Toolset.




  1. Wprowadzenie do programowania współbieżnego.

  • Wzajemne wykluczanie

  • Bezpieczeństwo i żywotność

  • Blokada i zagłodzenie

  • Klasyczne problemy

  • Mechanizmy synchronizacji.




  1. Rozwiązania klasycznych problemów z użyciem arbitra pamięci i semaforów

  • Algorytm Dekkera

  • Algorytm dla 5 filozofów

  • Algorytm dla producenta i konsumenta




  1. Rozwiązania klasycznych problemów z użyciem semaforów i monitorów.

  • Algorytm dla 5 filozofów

  • Algorytm dla producenta i konsumenta




  1. Protokoły komunikacyjne

  • Pięć elementów protokołu,

  • Usługi,

  • Założenia o otoczeniu,

  • Komunikaty,

  • Kodowanie komunikatów,

  • Reguły procedury gwarantującej zgodność komunikatów,

  • Reguły projektowania.




  1. Metody formalne

  • Wprowadzenie i porównanie,

  • Estelle, LOTOS, SDL.




  1. Zaawansowane mechanizmy Estelle

  • Główne konstrukcje,

  • Nie-determinizm i priorytety,

  • Zależności czasowe.




  1. Przykładowe protokoły komunikacyjne

  • No flow,

  • X-on/X-off,

  • Ping-pong,

  • Window/Sliding Window,

  • Alternating Bit Protocol.



  1. Metodologia Estelle

  • Rendez vous,

  • Symulacja,

  • Walidacja,




  1. Maszyny skończenie stanowe

  • Definicja,

  • Przykłady,

  • Testowanie osiągalności,

  • Zmienne zegarowe.




  1. Przykłady specyfikacji protokołów w Estelle

  • Deamon Game,

  • Unreliable medium




  1. Dalsze przykłady specyfikacji protokołów w Estelle




  1. Specyfikacja wybranych protokołów w SDL

  • Deamon Game,

  • Unreliable medium.




  1. Specyfikacja wybranych protokołów w LOTOS

  • Deamon Game

  • Unreliable medium




  1. Semantyka Estelle.

  • Model zadań,

  • Model globalny,

  • Semantyka dla instrukcji.




  1. Automatyczna weryfikacja.

  • Specyfikacja własności: automaty, logika temporalna,

  • Przeszukiwanie przestrzeni stanów: algorytmy DFS i BFS,

  • Produkt automatów,

  • Testowanie niepustości produktu,

  • Problem ekspotencjalnej eksplozji stanów.

  • Symboliczne kodowanie przestrzeni stanów.


LITERATURA





  1. G..J. Holzmann, Design and Validation of Computer Protocols, Prentice-Hall International, 1991.




  1. K. J. Turner (ed.), Using Formal Description Techniques. An Introduction to Estelle, Lotos, and SDL, Wiley 1993.



  1. M. Ben-Ari, Podstawy Programowania Współbieżnego, WNT, 1989.




  1. W. Iszkowski, M. Maniecki, Programowanie Współbieżne, WNT, 1982.



  1. Z. Weiss, T. Gruźlewski, Programowanie Współbieżne i Rozproszone w przykładach i zadaniach, WNT, 1993.


WYKŁAD I:

Wprowadzenie do programowania współbieżnego.


  • Wzajemne wykluczanie

  • Bezpieczeństwo i żywotność

  • Blokada i zagłodzenie

  • Klasyczne problemy

  • Mechanizmy synchronizacji.

Programowanie współbieżne jest dziedziną programowania, która dotychczas nie poddaje się łatwo automatyzacji.


Metody specyfikacji, weryfikacji i dowodzenia poprawności są dla tego typu programowania dużo bardziej skomplikowane niż dla programowania sekwencyjnego.
Współbieżność wymaga uwzględnienia trudnych do opisania zależności czasowych między programami (procesami).
Nadal pracuje się nad opracowaniem metod testowania i weryfikacji, które mogłyby być zastosowane dla profesjonalnych programów.
Programowanie współbieżne stosuje się w projektowaniu:

  • Systemów operacyjnych

  • Systemów zarządzania bazami danych

  • Systemów czasu rzeczywistego (sterowanie procesami technologicznymi, pracą elektrowni, lotem samolotu, itd.)

  • Protokołów komunikacyjnych

  • Gier komputerowych  i innych.

Zastosowanie w projektowaniu sieci komputerowych i systemów rozproszonych.


Programowanie rozproszone a programowanie współbieżne.
Powszechność procesów współbieżnych.
PROCES – program sekwencyjny (w trakcie wykonywania); czyli sekwencja zmian systemu komputerowego zgodnie z realizowanym algorytmem.
Zmian dokonuje PROCESOR, a kod przechowywany jest w pamięci operacyjnej.
Procesy mogą być skończone i nieskończone.
Poprawne procesy też mogą być nieskończone np. system operacyjny, procesy w systemach czasu rzeczywistego, protokoły komunikacyjne i inne.
Procesy są współbieżne, jeśli jeden z nich zaczyna się zanim zakończy się drugi.
W systemach jednoprocesorowych współbieżność realizuje się dzięki zasadzie podziału czasu.

Czas procesora jest dzielony pomiędzy wykonywane współbieżnie procesy.


Współbieżność oznacza jednoczesność jak również naprzemienne wykonywanie.
Obiektem naszego zainteresowania są procesy, których wykonania są od siebie uzależnione.
Procesy mogą ze sobą współpracować jak również współzawodniczyć o uzyskanie zasobu.
Współpraca wymaga komunikowania się procesów.
Uporządkowanie w czasie akcji komunikacyjnych nazywa się synchronizacją.
Program współbieżny to zbiór synchronizujących się współbieżnych procesów.
Głównym problemem w programowaniu współbieżnym jest projektowanie mechanizmów komunikacji i synchronizacji między procesami.
Procesy a wątki.

Procesy wykonywane we wspólnej przestrzeni adresowej nazywa się wątkami.


Środowisko, w którym wykonuje się wątek nazywa się zadaniem.
Wzajemne wykluczanie
Wspólny obiekt nazywa się zasobem dzielonym, a fragment programu, w którym z niego się korzysta nazywa się sekcją krytyczna.
Przykłady:

Zasoby: łazienka, budka telefoniczna, koszyk itd.

Fragmenty procesu: mycie, telefonowanie, zakupy.
Problem wzajemnego wykluczania polega na zsynchronizowaniu N procesów, korzystających z tego samego zasobu, tak, żeby ich sekcje krytyczne nie były współbieżne (tzn. nie pokrywały się w czasie.)
Realizacja polega na wprowadzeniu protokołu wstępnego i końcowego.
Wymagania czasowe satysfakcjonującego rozwiązania:


  • Proces nie może wykonywać swojej sekcji krytycznej nieskończenie długo.




  • Zachowanie procesów poza sekcją krytyczną nie może być ograniczone.




  • Procesy mogą się wykonywać z różnymi prędkościami.

Bezpieczeństwo i żywotność

Dla programów sekwencyjnych dowodziliśmy częściowej i całkowitej poprawności.


Dla programów współbieżnych odpowiednikiem częściowej poprawności jest własność bezpieczeństwa.
Program jest bezpieczny, jeśli nigdy nie znajdzie się w niepożądanym stanie tzn. zawsze znajduje się w stanie pożądanym.
Dla problemu wzajemnego wykluczania oznacza to, że żadne dwa procesy nie znajdą się jednocześnie w swoich sekcjach krytycznych.
Metody dowodzenia bezpieczeństwa
Metoda inwariantów.
Metoda przetestowania wszystkich możliwych wykonań.
Dla programów współbieżnych odpowiednikiem całkowitej poprawności jest własność żywotności.
Program współbieżny jest żywotny, jeśli każdy pożądany stan zostanie w końcu osiągnięty.
Dla problemu wzajemnego wykluczania oznacza to, że jeśli proces oczekuje na wejście do sekcji krytycznej, to w końcu się w niej znajdzie.
Metody dowodzenia żywotności
Udowodnienie, że każdy skończony ciąg akcji doprowadza w końcu do pożądanej sytuacji.

Sprawiedliwość

Własność zapewniająca, że procesy będą traktowane jednakowo uczciwe.


Dla problemu wzajemnego wykluczania oznacza to, że jeśli proces oczekuje na wejście do sekcji krytycznej, to w końcu się w niej znajdzie i dla każdego procesu czas oczekiwania jest taki sam.

Blokada i zagłodzenie

Zbiór procesów znajduje się w stanie blokady, jeśli każdy z tych procesów jest wstrzymany w oczekiwaniu na zdarzenie, które może być spowodowane tylko przez jakiś inny proces z tego zbioru.


Blokada jest przykładem niespełnionej własności bezpieczeństwa.
Możliwość wystąpienia blokady nie oznacza, że wystąpi ona w każdym wykonaniu programu współbieżnego.
Dlatego testowanie nie jest dobrą metodą jej wykrywania.

Zagłodzenie występuje wtedy, gdy proces nie jest wznowiony, mimo że zdarzenie, na które czeka występuje dowolną liczbę razy.

Blokada jest przykładem niespełnionej własności żywotności.



Klasyczne problemy współbieżności


Problem producenta i konsumenta polega na zsynchronizowaniu dwóch procesów: producenta, który cyklicznie produkuje porcje danych, a następnie przekazuje je do konsumpcji, i konsumenta, który cyklicznie te dane pobiera i konsumuje.
Producent musi być wstrzymany, jeśli nie może przekazać wyprodukowanych porcji, a konsument, jeśli nie może ich pobrać.
Porcje powinny być konsumowane w kolejności ich wyprodukowania (to nie zawsze jest wymagane).
Rozwiązania:

Synchronizacja przez N elementowy bufor (N od 1 do nieskończoności).


Efektywność rozwiązania zależy od wielkości bufora i zależności czasowych realizacji produkcji i konsumpcji.
Problem ten jest abstrakcją wielu rzeczywistych problemów pojawiających się w protokołach komunikacyjnych i systemach czasu rzeczywistego.
Problem czytelników i pisarzy polega na zsynchronizowaniu dwóch grup cyklicznych procesów konkurujących o dostęp do wspólnej czytelni.
Proces czytelnik odczytuje informacje zgromadzone w czytelni i może to robić razem z innymi czytelnikami. Proces pisarz cyklicznie zapisuje informacje i może to robić tylko sam przebywając w czytelni.
Czytanie i pisanie trwa skończenie długo.
Problem ten jest abstrakcją problemu synchronizacji procesów korzystających ze wspólnej bazy danych.
Rozwiązanie z możliwością zagłodzenia pisarzy:

Czytelnik może wejść do czytelni, gdy jest pusta lub są w niej inni czytelnicy.


Gdy w czytelni jest pisarz czytelnik jest wstrzymany.
Gdy czytelnia nie jest pusta, to pisarz jest wstrzymany.
Rozwiązanie z możliwością zagłodzenia czytelników:

Jeśli pisarz czeka na wejście do czytelni, to nie może już do niej wejść żaden nowy czytelnik


Rozwiązanie bez zagłodzenia: do czytelni wpuszczani są na przemian czytelnicy i pisarze. Z tym, że wraz z każdym czytelnikiem wchodzą wszyscy inni oczekujący czytelnicy.

Problem pięciu filozofów polega na zsynchronizowaniu działań pięciu filozofów, którzy siedzą przy okrągłym stole i cyklicznie myślą i jedzą, korzystając z talerza i dwóch widelców.
Przed każdym filozofem stoi talerz, a pomiędzy każdymi dwoma talerzami leży jeden widelec.
Zakłada się, że jeśli filozof podniósł oba widelce, to w skończonym czasie je odłoży.

Rozwiązanie gwarantuje, że każdy filozof, który poczuje się głodny, będzie mógł się w końcu najeść.


Ponadto wszyscy filozofowie powinni być traktowani jednakowo.
Jest to wzorcowy przykład obrazujący zjawiska zagłodzenia i blokady.
Rozwiązanie z możliwością blokady: głodny filozof czeka, aż będzie wolny lewy widelec, podnosi go i czeka na prawy i także go podnosi. Po zjedzeniu odkłada oba widelce.
Rozwiązanie z możliwością zagłodzenia: filozof czeka, aż oba widelce będą wolne i wtedy podnosi je jednocześnie.
Rozwiązanie poprawne: wykorzystany jest zewnętrzny arbiter (lokaj), który zapewnia, że jednocześnie nie więcej niż czterech (4) filozofów chciałoby jeść, to znaczy konkuruje o widelce. Jeśli pięciu (5) filozofów chciałoby jeść naraz, to lokaj powstrzyma jednego z nich.

Mechanizmy niskopoziomowe

Przerwania:


Każdy procesor wyposażony jest w mechanizm przerwań, a pamięć w arbiter pamięci.
Umożliwia to programowanie współbieżne na niskim poziomie.
Przerwanie umożliwia przełączenie procesora na wykonywanie innego procesu.

Maskowanie przerwań umożliwia zablokowanie następnych przerwań.

Efektywny tylko dla architektur jednoprocesorowych.

Arbiter pamięci zapewnia wzajemne wykluczanie przy zapisie lub odczycie pojedynczej komórki pamięci.



Algorytm Dekkera – wykorzystanie arbitra pamięci i trzech zmiennych.
Inne instrukcje:
Test&Set(X,R) – przepisanie komórki X do lokalnego rejestru R wraz z jednoczesnym wyzerowaniem.
Na początku wspólna zmienna X : =1.

Przed wejściem do sekcji krytycznej proces wykonuje:

R := 0; while R = 0 do Test&Set(X,R)

Po wyjściu ustawia X na 1.



Mechanizmy wysokiego poziomu

Mechanizmy synchronizacji w językach wysokiego poziomu.


Semafory (Dijkstra 1968) – zmienna całkowita, na której wykonuje się dwie operacje odpowiadające podnoszeniu i opuszczaniu semafora.
Prowadzi do niestrukturalnego programowania.
Monitory (uogólnienie regionów krytycznych i warunkowych regionów krytycznych) zajmuje się nadzorowaniem pracy wybranego zasobu, o który ubiegają się procesy.
Inne mechanizmy: liczniki zdarzeń, wyrażenia ścieżkowe i inne.

Mechanizmy komunikacji i synchronizacji



Spotkania (rendez-vous): CSP, ADA
Przestrzeń krotek – zawiera wszystkie wyniki działania procesów. Procesy sięgają do przestrzeni po informacje.

Linda
Potoki: pliki, na których wiele procesów może wykonywać operacje czytania i pisania (dopowiadające obsłudze bufora): UNIX, MS-DOS.


Komunikaty i kanały: uogólnienie potoku bez ograniczeń na strukturę, kierunek przesyłania i typ przesyłanych informacji: Estelle, SDL, LOTOS.
Zdalne wywołanie procedury (RPC)

Klasyfikacja mechanizmów synchronizacji



System scentralizowany – wszystkie procesory mają dostęp do wspólnej pamięci.

Mechanizmy synchronizacji: Semafory, monitory, potoki, komunikaty unixowe, przestrzeń krotek.


System rozproszony – każdy procesor ma dostęp do swojej własnej pamięci, a pomiędzy procesorami są łącza umożliwiające przesyłanie danych.

Mechanizmy synchronizacji: komunikaty i kanały, spotkania, RPC.


Ze względu na powiązania czasowe mechanizmy komunikacji dzielimy na synchroniczne i asynchroniczne.
Synchroniczne – nadawca komunikatu musi poczekać na jego odebranie.
Asynchroniczne – komunikat może być zawsze wysłany bez względu na to co robi odbiorca.
Rodzaje programów współbieżnych:
Ze względu na rodzaj komunikacji:


  • Rozgłaszanie (broadcasting)




  • Bicie serca (heartbeating)




  • Przekazywanie żetonu (token passing)




  • Wspólny worek (common bag)

Rozgłaszanie: wysyłanie komunikatu do wszystkich.

Bicie serca: wysyłanie komunikatu do najbliższych sąsiadów wszystkich.
Przekazywanie żetonu: komunikat przekazywany kolejno od procesu do procesu.
Wspólny worek zawiera zbiór komunikatów z opisem i parametrami działań do wykonania; pobierane przez procesy.
Układ klient-proces obsługujący (server)

Klient wysyła żądania, a serwer je obsługuje.


Warianty:
Jeden klient – jeden proces obsługujący

Wielu klientów - jeden proces obsługujący

Wielu klientów - wiele procesów obsługujących

Hierarchia – proces obsługujący jest klientem procesu wyższego poziomu.

Interakcja – zamiana rolami.

WYKŁAD II: Rozwiązania klasycznych problemów (zmienne dzielone i semafory)

  • Algorytm Dekkera i Petersena

  • Algorytm dla producenta i konsumenta

Współbieżny Pascal-S


Mechanizm synchronizacji: zmienne dzielone.
cobegin P1;P2;...,Pn coend
(bez możliwości zagnieżdżania)
P1,..,Pn – procedury Pascalowe.
Algorytm Dekkera dla problemu wzajemnego wykluczania dwóch procesów, korzystający z arbitra pamięci (zmiennych dzielonych).
Każdy z dwóch procesów P1 i P2 wykonuje w nieskończonej pętli program składający się z dwóch części: sekcji krytycznej (kryt1 i kryt2) oraz sekcji lokalnej (lok1 i lok2).
Wykonywanie kryt1 i kryt2 nie może odbywać się jednocześnie.

I próba


program pp1;

var czyjakolej: integer;


procedure p1;

begin


repeat

1: while czyjakolej = 2 do (* NIC*);

2: kryt1;

3: czyjakolej := 2;

4: lok1

until 0


end;
procedure p2;

begin


repeat

1: while czyjakolej = 1 do (* NIC*);

2: kryt2;

3: czyjakolej := 1;

4: lok2

until 0


end;

begin (*program główny)

czyjakolej := 1;

cobegin p1;p2

coend

end.



Stan (lokacja1,lokacja2,czyjakolej)

(1,1,1)  (2,1,1)  (3,1,2)  (4,1,2)  (1,1,2)  (1,2,1)

 (1,2,2)  (1,3,1)
 (3,2,2)  (1,2,2) 

 (3,3,1)  (4,3,1)

Spełnia wymagania, ale ma dwie wady:
Oba procesy wchodzą do sekcji krytycznej dokładnie tyle samo razy bez względu na to ile razy chcą to zrobić.
Jeśli jeden z procesów zakończy awaryjnie działanie, to drugi nie będzie już mógł wejść do sekcji krytycznej.
Taki system programowania nazywa się współprogramami.
Procesy otrzymają własne klucze do sekcji krytycznej.
Jeśli klucz drugiego procesu jest ustawiony na 1 tzn. ze nie przebywa on w sekcji krytycznej.

II próba
program pp2;

var c1,c2: integer;
procedure p1;

begin


repeat

while c2 = 0 do (* NIC*);

c1 := 0;

kryt1;


c1 := 1;

lok1


until 0

end;
procedure p2;

begin

repeat


while c1 = 0 do (* NIC*);

c2 := 0;


kryt2;

c2 := 1;


lok2

until 0


end;

begin (*program główny)

c1 := 1;

c2 := 1;


cobegin p1;p2

coend


end.
Program nie spełnia zasady wzajemnego wykluczania: jest niepoprawny.

III próba


Wcześniej zostanie wykonane przypisanie w taki sposób, że równość c1 = 0 oznacza, że P1 już jest w sekcji krytycznej, zanim nawet sprawdzi c2.

program pp3;

var c1,c2: integer;
procedure p1;

begin


repeat

c1 := 0;


while c2 = 0 do (* NIC*);

kryt1;


c1 := 1;

lok1


until 0

end;


procedure p2;

begin


repeat

c2 := 0;


while c1 = 0 do (* NIC*);

kryt2;


c2 := 1;

lok2


until 0

end;
begin (*program główny)

c1 := 1;

c2 := 1;


cobegin p1;p2

coend


end.
Powyższy program spełnia zasadę wzajemnego wykluczania, ale się blokuje.
W kolejnej próbie proces czasowo rezygnuje z chęci wejścia do sekcji krytycznej, aby dać szansę drugiemu procesowi.
Proces P1 zapisuje 0 na c1, ale potem sprawdza c2 i jeśli też jest 0, to zmienia c1 na 1.

Po kilku chwilach przywraca wartość c1 na 0.

IV próba

program pp4;

var c1,c2: integer;
procedure p1;

begin


repeat

c1 := 0;


while c2 = 0 do

begin


c1 := 1;

(* NIC nie rób przez kilka chwil*);

c1 := 0;

end;


kryt1;

c1 := 1;


lok1

until 0


end;
procedure p2;

begin


repeat

c2 := 0;


while c1 = 0 do

begin


c2 := 1;

(* NIC nie rób przez kilka chwil*);

c2 := 1;

end;


kryt2;

c2 := 1;


lok2

until 0


end;
begin (*program główny*)

c1 := 1;


c2 := 1;

cobegin p1;p2

coend

end.
Powyższy program spełnia zasadę wzajemnego wykluczania, ale nie zapewnia żadnemu procesowi wejścia do sekcji krytycznej.


Możemy to zaklasyfikować jako zagłodzenie.

Algorytm Dekkera jest pomysłową kombinacją I i IV próby


program pp4;

var czyjakolej: integer;

c1,c2: integer;
procedure p1;

begin


repeat

c1 := 0;


while c2 = 0 do

if czyjakolej = 2 then

begin

c1 := 1;


while czyjakolej = 2 do;

c1 := 0;


end;

kryt1;


czyjakolej :=2;

c1 := 1;


lok1

until 0


end;
procedure p2;

begin


repeat

c2 := 0;


while c1 = 0 do

if czyjakolej = 1 then

begin

c2 := 1;


while czyjakolej = 1 do;

c2 := 0;


end;

kryt2;


czyjakolej := 1;

c2 := 1;


lok2

until 0


end;
begin (*program główny)

c1 := 1;


c2 := 1;

czyjakolej := 1;

cobegin p1;p2

coend


end.


Semafory jako abstrakcyjny typ danych

Na semaforze oprócz określenia stanu początkowego można wykonać:


Podniesienie semafora

Opuszczenie semafora


Operacje są niepodzielne, tzn. w danej chwili może być wykonana tylko jedna z nich.

Zakłada się, że implementacja semafora powinna być żywotna.


Definicja klasyczna:

Semafor S jest zmienną całkowitą.



Podniesienie: S := S +1;
Opuszczenie: czekaj, aż S > 0; S := S – 1;
Definicja praktyczna:
Podniesienie: jeśli są procesy wstrzymane w wyniku wykonywania operacji opuszczania, to wznów jeden z nich, w przeciwnym razie S := S +1;
Opuszczenie: jeśli S > 0; to S := S – 1; w przeciwnym razie wstrzymaj działanie procesu.
Wybór procesu: w sposób nie powodujący zagłodzenia czekających procesów.
var S: semaphore : = 1;
V(S) – podniesienie semafora
P(S) – opuszczenie semafora


Semafor binarny

Semafor binarny jest zmienną logiczną


Definicja praktyczna:
Podniesienie: jeśli są procesy wstrzymane w wyniku wykonywania operacji opuszczania, to wznów jeden z nich, w przeciwnym razie S := 1;
Opuszczenie: jeśli S = 1; to S := 0; w przeciwnym razie wstrzymaj działanie procesu.
var S: binary semaphore : = 1;
VB(S) – podniesienie semafora

PB(S) – opuszczenie semafora

W celu uniknięcia niejednoznaczności zakłada się, że podnoszenie podniesionego semafora jest błędem.

Rozwiązania klasycznych problemów z użyciem semaforów.


Program wzajemne wykluczanie:

var S: binary semaphore := 1;

procedure p1;

begin


while true do

begin


lok1;

PB(S);


kryt1;

VB(S);


end

end;


procedure p2;

begin


while true do

begin


lok2;

PB(S);


kryt2;

VB(S);


end

end;


begin (*program główny*)

cobegin


p1;p2

coend


end.

Program producentkonsument:

const N = ?;

var WOLNE: semaphore := N;

PELNE: semaphore := 0;

bufor: array[1..N] of integer;
procedure producent;

var p: integer;

j: 1..N := 1;

begin


while true do begin

produkuj(p);

P(WOLNE);

bufor[j] := p;

j := j mod N + 1;

V(PELNE)


end

end;


procedure konsument;

var p: integer;

k: 1..N := 1;

begin


while true do begin

P(PELNE);

p := bufor[k];

k := k mod N + 1;

V(WOLNE);

konsumuj(p);

end

end;
begin (*program główny*)



cobegin

producent; konsument;

coend

end.
Wartość j nigdy nie jest równa k.



Zatem wstawianie i pobieranie z bufora odbywa się z jego różnych elementów.

Powyższe rozwiązanie wymaga modyfikacji, żeby mogło być stosowane dla wielu producentów i konsumentów.



WYKŁAD III: Rozwiązania klasycznych problemów (semafory i monitory)

  • Algorytm dla 5 filozofów

  • Algorytm dla czytelników i pisarzy

  • Algorytm wzajemnego wykluczania

  • Algorytm dla producentów i konsumentów


program 5filozofow;

var WIDELEC :

array[0..4] of binary semaphore := (1,1,1,1,1);

LOKAJ : semaphore := 4;

procedure filozof(i: 0..4);

begin


while true begin

myslenie(i);

P(LOKAJ);

PB(WIDELEC[i]);

PB(WIDELEC{(i+1) mod 5]);

jedzenie(i);

VB(WIDELEC[i]);

VB(WIDELEC{(i+1) mod 5]);

V(LOKAJ);

end


end;

begin (*program główny*)

cobegin

filozof(0);...;filozof(4);



coend

end.


Algorytm dla czytelników i pisarzy.
const M = ?; {liczba czytelników}

P = ?; {liczba pisarzy}

var WOLNE: semaphore := M; {liczba miejsc}

W: binary semaphore := 1; {do wzajemnego

wykluczania pisarzy}
process CZYTELNIK(i: 1..M);

begin


while true do begin

lokalne-dla-czytelnika;

P(WOLNE);

Czytanie;

V(WOLNE)

end


end;
process PISARZ(i: 1..P);

var j: integer;

begin

while true do begin



lokalne-dla-pisarza;

PB(W);


for j := 1 to M do P(WOLNE);

pisanie;


for j := 1 to M do V(WOLNE);

VB(W);


end

end;


const M = ?;

P = ?;

var ac: integer := 0; {aktywni czytelnicy}

dc: integer := 0; {działający czytelnicy}

ap: integer := 0; {aktywni pisarze}

dp: integer := 0; {działający pisarze}

CZYT: semaphore := 0; {wstrzymuje czytelników}

PIS: semaphore := 0; {wstrzymuje pisarzy}

CHRON: binary semaphore := 1; {do zmiennych}

W : binary semaphore := 1; {do wykluczania pisarzy}
process CZYTELNIK(i: 1..M);

begin

while true do begin

lokalne;

PB(CHRON);

ac := ac+1;

if ap = 0 then

while dc < ac do begin

dc := dc + 1;

V(CZYT)

end;

VB(CHRON);

P(CZYT);

czytanie;

PB(CHRON);

dc := dc –1;

ac := ac – 1;

if dc = 0 then

while dp < ap do begin

dp := dp + 1;

V(PIS)

end;

VB(CHRON)

end

end;
process PISARZ(i: 1..M);

begin

while true do begin

lokalne;

PB(CHRON);

ap := ap +1;

if ac = 0 then

while dp < ap do begin

dp := dp + 1;

V(PIS)

end;

VB(CHRON);

P(PIS);

PB(W);

pisanie;

VB(W);

PB(CHRON);

dp := dp –1;

ap := ap – 1;

if dp = 0 then

while dc < ac do begin

dc := dc + 1;

V(CZYT)

end;

VB(CHRON)

end

end;

Monitory
Pomysł Brinch Hansena 1979 i C.A.R. Hoare 1974
Monitor to zebrane w jednej konstrukcji programowej pewne wyróżnione zmienne, procedury i funkcje działające na tych zmiennych.
Tylko wywołanie funkcji i procedur umożliwia procesom dostęp do zmiennych ukrytych wewnątrz monitora.
Wykonanie procedury monitora jest sekcją krytyczną wykonującego ja procesu.
Czyli tylko jeden proces może ja wykonywać.
Można wstrzymywać i wznawiać procesy wewnątrz procedury monitorowej. Służą do tego zmienne specjalne typu condition:


  • Wait(c) – wstrzymanie procesu, wstawienie na koniec kolejki zmiennej c i zwolnienie monitora.




  • Signal(c) – wznowienie procesu z kolejki c. Proces wykonujący jest wstrzymywany, aż wznowiony zwolni monitor.




  • Empty(c) – testowanie kolejki związanej ze zmienną c.

Procesy czekające na dostęp do monitora czekają w trzech różnych kolejkach.




  • Wejściowa – chcą rozpocząć wykonywanie procedury monitora




  • Kolejki związane ze zmiennymi typu condition,




  • Wstrzymane po wykonaniu operacji signal (są odkładane na stos)

Wykorzystano w językach: Pascal_C, Concurrent Pascal, Pascal Plus, Modula 2, Modula 3, Concurrent Euclid.


Przykład wzajemnego wykluczania w Pascalu_C.
monitor WYKLUCZANIE;

var zasob : typ_zasobu;


export procedure DOSTEP;

begin


{działanie na zasobie}

end; {DOSTEP}


begin

end; {WYKLUCZANIE}

process P;

begin


while true do begin

lokalne;


WYKLUCZANIE.DOSTEP

end


end; {P}
Producenci i konsumenci

Monitor BUFOR;

const N = ?

var bufor : array[0..N-1] of integer;

ile, do_włożenia, do_wyjęcia: integer;

PRODUCENCI, KONSUMENCI: condition;


export procedure WSTAW(element: integer);

begin


if ile = N then wait(PRODUCENCI);

do_włożenia := (do_włożenia + 1) mod N;

bufor[do_włożenia] := element;

ile := ile +1;

signal(KONSUMENCI)

end;{WSTAW}

export procedure POBIERZ(var element: integer);

begin


if ile = 0 then wait(KONSUMENCI);

do_wyjęcia := (do_wyjęcia + 1) mod N;

element := bufor[do_wyjęcia];

ile := ile - 1;

signal(PRODUCENCI)

end;{POBIERZ}


begin

ile := 0;

do_włożenia := 0;

do_wyjęcia := 0;



end; {BUFOR}






©snauka.pl 2016
wyślij wiadomość