Abstrakcja programowania współbieżnego

Wprowadzenie do abstrakcji przetwarzania współbieżnego


Przetwarzanie w systemie współbieżnym polega na wykonywaniu instrukcji różnych procesów. Wykonanie instrukcji (akcja) skutkuje zmianą stanu procesu i określane jest jako zdarzenie.

Instrukcje wykonywane w systemie, niezależnie od procesu, wpływają również na stan systemu jako całości. Stan systemu stanowi pewne otoczenie każdego procesu (jest tym samym elementem stanu każdego z procesów), gdyż niektóre zasoby systemu są przez procesy współdzielone. W najprostszym przypadku można mówić o współdzielonych zmiennych, których wartości wynikają z wykonywania instrukcji różnych procesów. W ten sposób dochodzi do interakcji pomiędzy procesami.

W celu ujednolicenia opisu stan systemu będzie występował wyłącznie w kontekście procesu, a interakcja pomiędzy procesami będzie realizowana poprzez zmienne wejściowe i wyjściowe poszczególnych procesów.

Przedstawioną abstrakcję można również odwzorować na proces wielowątkowy. Proces taki odpowiadałby wówczas systemowi, udostępniając środowisko do wykonywania wątków. Zmiana stanu wynikałaby z realizacji instrukcji związanych z wątkami tego procesu.

Podstawowe definicje i oznaczenia


Programowanie współbieżne opiera się na dwóch zasadniczych pojęciach: instrukcji atomowej i przeplocie. Instrukcja atomowa to taka instrukcja, która wykonywana jest w sposób niepodzielny. W trakcie jej wykonywania nie są obsługiwane żadne przerwania.

W systemach z jedną jednostką przetwarzającą warunki te spełnia każdy rozkaz procesora, gdyż sprawdzanie wystąpienia przerwań oraz ewentualna ich obsługa wykonywana jest zawsze na końcu cyklu rozkazowego. Poza tym skutki wykonania takiej instrukcji są natychmiast widoczne dla instrukcji następnych.

W systemach wieloprocesorowych instrukcje mogą być wykonywane jednocześnie przez różne jednostki przetwarzające. Takie wykonanie instrukcji odbywa się w izolacji, co gwarantuje, że żadne częściowe (tymczasowe) wyniki nie są widoczne i tym samym nie wpływają na wykonanie innych instrukcji. Jeśli jednak jednocześnie wykonywane instrukcje operują na tych samych danych, konieczne jest najczęściej wykonanie ich w określonej sekwencji. W systemach wieloprocesorowych, opartych na wspólnej magistrali, efekt ten można uzyskać przez zablokowanie dostępu do magistrali systemowej na czas wykonywania instrukcji. W architekturach Intel, w tym celu przekazywany jest sygnał LOCK, który jest integralnie związany z cyklem rozkazowym w przypadku niektórych rozkazów (np. xchg) lub wynika z jawnego żądania ze strony wykonywanego programu, poprzez użycie prefiksu LOCK.

W przyjętych oznaczeniach ei (c , O ) oznacza wykonanie w ramach procesu Pi operacji c ∈C, w wyniku której czytane lub modyfikowane są operandy (argumenty) ze zbioru O = {o1 , o2 ,..., on} ⊆ D. Formalnie wykonanie operacji jest zatem elementem iloczynu kartezjańskiego C × 2D.

Stan procesu i zdarzenie


Z punktu widzenie współbieżnej i asynchronicznej realizacji przetwarzania przez wiele procesów istotne jest, kiedy jakaś instrukcja się wykona, zwłaszcza instrukcja, która wpływa na otoczenie procesu (potencjalnie zatem na inne procesy). Dlatego najbardziej istotny jest ten aspekt stanu procesu, który dotyczy wykonywania instrukcji i pośrednio wpływa na realizację innych procesów w systemie.

Na poziomie architektury procesora następną instrukcję do wykonania bezpośrednio wskazuje rejestr w procesorze, zwany licznikiem rozkazów lub wskaźnikiem instrukcji. Jednak następna wartość tego rejestru zależy od wykonywanego rozkazu oraz ustawienia flag w rejestrze, zwanym słowem stanu programu. Zawartość tego rejestru wynika z kolei z wcześniej wykonanych instrukcji oraz wartości ich operandów. Poza tym możliwość wykonania instrukcji uwarunkowana jest dostępnością takich zasobów jak pamięć, czy procesor.

Na potrzeby dalszej analizy zakłada się, że określony stan procesu jest unikalny, tzn. ten sam stan nigdy się nie powtórzy, pomimo że stan przetwarzania (stan rejestrów procesora, pamięci) będzie dokładnie taki sam jak wcześniej. Można przyjąć, że elementem stanu procesu jest rzeczywisty czas ostatniego zdarzenia lub licznik wykonanych instrukcji, który będzie się monotonicznie zwiększał.

  • Stan procesu obejmuje te elementy (wartości zmiennych, rejestrów, stan zasobów), które między innymi determinują następną instrukcję do wykonania.
  • Wykonanie instrukcji określane jest jako zdarzenie lub akcja.
  • Zbiór instrukcji do wykonania oraz zależności pomiędzy nimi określone są przez program procesu.
  • Zajście zdarzenia zdeterminowane jest zatem przez program oraz bieżący stan procesu.

Proces sekwencyjny


Przedstawiona definicja jest nieco bardziej sformalizowaną postacią definicji przedstawionej wcześniej na potrzeby zarządzania zasobami systemu.

Odwzorowanie L zdefiniowane jest przez program dla procesu, zakładając, że program jest deterministyczny. Odzwierciedla ono fakt, że zajście zdarzenia w określonym stanie prowadzi do następnego stanu. Opisując to z drugiej strony można stwierdzić, że stan następny uwarunkowany jest zajściem zdarzenia i stanem poprzedzającym to zajście. Odwzorowanie to nie jest określonej dla każdej pary ze zbioru Si ×Ei. W przetwarzaniu sekwencyjnym stan determinuje następne zdarzenie, np. licznik rozkazów wskazuje następny rozkaz do wykonania.

Jak już zasygnalizowano na poprzednim slajdzie, użycie pojęcia wątek, obok powszechnie używanego w tym kontekście pojęcia proces, podkreśla fakt, że realizacja współbieżnego przetwarzania przebiega we wspólnej przestrzeni adresowej, czyli przy dostępie do współdzielonych danych. W tym module pojęcia proces i wątek będą utożsamiane.

  • Proces (wątek) sekwencyjny jest wykonaniem ciągu instrukcji, opisanych przez program dla tego procesu (procedurę dla wątku), w taki sposób, że następna akcja nie rozpocznie się, zanim nie skończy się poprzednia.
  • Zdarzenie (akcja) w procesie Pi oznacza zmianę stanu tego procesu, co formalnie opisane jest poprzez odwzorowanie (przejście, tranzycję):
    L: Si × EiSi, gdzie
    Si — zbiór stanów procesu Pi
    Ei — zbiór zdarzeń w procesie Pi

Relacja lokalnego porządku


Przetwarzanie sekwencyjne oznacza następstwo stanów i zdarzeń. Zarówno zdarzenia, jak i stany w procesie sekwencyjnym są liniowo uporządkowane zgodnie z kolejnością ich wystąpienia.

slajd 7

Współbieżna realizacja zbioru procesów


Na potrzeby analizy systemu współbieżnego przyjęte zostaje założenie, że zdarzenia zachodzą w sposób natychmiastowy i pojedynczo, stan natomiast może trwać przez pewien interwał czasu. Oznacza to, że operacje wykonywane są sekwencyjnie, co odpowiada systemowi współbieżnemu z jedną jednostką przetwarzającą.

Zakładając, że w systemie z kilkoma równolegle działającymi procesorami operacje jednoczesne (nakładające się w czasie, ang. overlapping) nie powoduję konfliktu w dostępie do danych, model taki jest w dalszym ciągu adekwatny. Można pokazać, że przetwarzanie z jednoczesnym wykonaniem pewnych instrukcji jest równoważne wykonaniu sekwencyjnemu.

Jeśli występuje konflikt w dostępie do danych, tzn. dwie (lub więcej) instrukcje wykonywane jednocześnie mają wspólny operand, przy czym przynajmniej jedna z nich go modyfikuje, konieczne jest ich uszeregowanie w czasie. W wyniku tego uszeregowania instrukcje „w konflikcie” będą wykonane w pewnej sekwencji.

Niezależnie zatem od sposobu realizacji przetwarzania, instrukcje różnych procesów będą analizowane tak, jak gdyby przeplatały się one w czasie.

We współbieżnej realizacji zakłada się, że procesy działają asynchronicznie, tzn. liczba instrukcji poszczególnych procesów, wykonana w jednostce czasu, może być dla każdego z nich inna. Oznacza to, że nie ma pewności, w jakiej kolejności instrukcje różnych procesów będą następowały po sobie, chyba że kolejność tę wymuszą zastosowane mechanizmy synchronizacji.

  • Zdarzenie w systemie współbieżnym, złożonym z procesów sekwencyjnych Pv P2, .... Pn, oznacza zajście zdarzenia w jednym z procesów.
  • Zdarzenie, zmieniając stan jednego procesu, zmienia stan całego systemu, co formalnie opisane jest poprzez odwzorowanie (przejście, tranzycję):
    G: ∑ x A → ∑ , gdzie
    ∑ ⊆ S1 x S 2 x ... x Sn — zbiór stanów systemu
    A = E1, ∪ E2 ∪ ... ∪ En — zbiór zdarzeń w systemie

Relacja globalnego porządku


Kontynuując rozumowanie, przedstawione na poprzednich slajdach, można powiedzieć, że na stan przetwarzania współbieżnego składają się stany poszczególnych procesów, a zmiana tego stanu spowodowana jest zdarzeniem w jednym z tych procesów.

Na stan początkowy przetwarzania składają się stany początkowe poszczególnych procesów.

Podobnie jak odwzorowanie L, odwzorowanie G nie jest określone dla każdej pary ze zbioru Σ × Δ. Nie każde zdarzenie może zatem wystąpić w określonym stanie przetwarzania współbieżnego. W przeciwieństwie do stanu procesu sekwencyjnego stan przetwarzania współbieżnego nie determinuje jednak jednoznacznie następnego zdarzenia, gdyż potencjalnie jakieś zdarzenie może wystąpić w każdym ze współbieżnych procesów. Liczba możliwych zdarzeń może być zredukowana poprzez zastosowanie mechanizmów synchronizacji.

  • Przetwarzanie współbieżne zbioru procesów sekwencyjnych P1 P2, ..... Pn jest ciągiem (skończonym lub nieskończonym) następujących po sobie naprzemiennie stanów systemu i zdarzeń

    σ0, e1, σ1, e2, σ2 ..... gdzie:
    σ0 — stan początkowy (s10, s20, ..... , sn0)
    k≥0 σk ∈ ∑
    k>0 ek ∈ A
    k≥0 G(σk, ek+1) = σk+1
  • Relacja porządku w systemie — odzwierciedlająca kolejność stanów i zdarzeń w ciągu — nazywana będzie globalnym porządkiem i oznaczana symbolem →

Niedeterminizm przetwarzania


Analizując konkretną realizację przetwarzania można określić jakie stany i jakie zdarzenia miały miejsce, kiedy miały miejsce (w jakiej kolejności). Analizując program dla przetwarzania współbieżnego, pewne stany i zdarzenia należy przewidzieć, gdyż każde wykonanie takiego programu może przebiegać nieco inaczej. Ponieważ w większości przypadków dopuszczalnych jest wiele zdarzeń różnych procesów, w przypadku przetwarzania asynchronicznego nie wiadomo, które dokładnie zdarzenie zajdzie jako kolejne. Stąd niedeterminizm takiego przetwarzania.

W niektórych przypadkach kolejność wystąpienia zdarzeń nie ma znaczenia, osiągamy ostatecznie taki sam stan. Są jednak przypadki, w których wystąpienie określonego zdarzenia na tyle istotnie wpływa na stan przetwarzania współbieżnego, że sterowanie w niektórych procesach może przebiegać zupełnie inną ścieżką. Zjawisko, w którym w zależności od kolejności pewnych zdarzeń system osiąga różne stany, określa się jako hazard (ang. race condition).

  • Zdarzenie, które może pojawić się w określonym stanie przetwarzania, określane jest jako zdarzenie dopuszczalne.
  • W przetwarzaniu współbieżnym z każdym sekwencyjnym procesem w danym stanie związane jest jedno zdarzenie. W stanie całego przetwarzania jest zatem zbiór zdarzeń dopuszczalnych.
  • W zależności od dostępności zasobów (procesora, magistrali systemowej) oraz decyzji planisty, wykonywany będzie jeden z procesów gotowych. Należy więc przyjąć, że zajście jednego ze zdarzeń dopuszczalnych ma charakter losowy.