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



Pobieranie 45,27 Kb.
Data23.02.2018
Rozmiar45,27 Kb.


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.






©operacji.org 2017
wyślij wiadomość

    Strona główna