J. U

łasiewicz Programowanie aplikacji współbieżnych 1

Podstawowe definicje i poj

ęcia współbieżności

1.1 Dlaczego zajmujemy si

ę współbieżnością ?

Wspó

łczesne systemy i aplikacje charakteryzują się coraz większą

z

łożonością. Typowe aplikacje:

1. wiele

procesów

wykonywanych

w

środowisku

systemu

pracuj

ącego z podziałem czasu

2. wiele procesów wykonywanych na komputerze wieloprocesowym
3. wiele procesów wykonywanych na wielu powi

ązanych w jeden

system maszynach (ang. Cluster).

W systemach takich stosuje si

ę podział zadania na procesy gdyż

zapewnia to okre

ślone korzyści:

1. polepszenie wykorzystania systemu,
2. zmniejszenie czasu przetwarzania
3. u

łatwienia w projektowaniu oprogramowania.

1.2 Czym jest proces ?

Proces jest czym

ś innym niż program. Program jest zapisem algorytmu

wraz ze strukturami danych na których algorytm ten operuje. Algorytm
zapisany bywa zwykle w jednym z wielu j

ęzyków programowania.

Za Wirthem mo

żemy podać definicję programu:

Program = algorytm + struktury danych


Program jest wi

ęc strukturą statyczną zapisaną na jakimś nośniku.

Natomiast proces jest wykonuj

ącym się programem.

Proces - wykonuj

ący się program

Proces jest wi

ęc aktywną strukturą dynamiczną istniejącą tylko w

środowisku działającego komputera.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 2

1.3 Podstawowe definicje wspó

łbieżności

Procesy sekwencyjne (ang. Sequential processes)


Procesy s

ą sekwencyjne jeżeli następny proces ze zbioru procesów

rozpoczyna si

ę po zakończeniu procesu poprzedniego.

P1

P2

Rys. 1 Procesy P1 i P2 wykonywane s

ą sekwencyjnie

Procesy wspó

łbieżne (ang. Concurrent processes)

Dwa procesy s

ą współbieżne jeżeli jeden z nich rozpoczyna się przed

zako

ńczeniem drugiego.

P1

P2

Rys. 2 Procesy P1 i P2 wykonywane s

ą współbieżnie

Procesy równoleg

łe (ang.Paralell processes)

Dwa procesy s

ą równoległe jeżeli jeden z nich rozpoczyna się przed

zako

ńczeniem drugiego i wykonywane są jednocześnie na oddzielnych

procesorach.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 3

P1

P2

Procesor 1

Procesor 2

Rys. 3 Procesy P1 i P2 wykonywane s

ą równolegle.

Rodzaje wspó

łbieżności

Wspó

łbieżność konkurencyjna – procesy nie współpracują ze sobą.

Ich oddzia

ływanie polega tylko na konkurowaniu o dostęp do zasobów

których potrzebuj

ą.

Wspó

łbieżność kooperacyjna – procesy współpracują ze sobą

dzia

łając w ramach aplikacji jednej współbieżnej. Komunikują i

synchronizuj

ą się ze sobą w celu wykonania pewnego zadania.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 4

1.4 Podstawowe architektury systemów komputerowych

Aby proces móg

ł się wykonywać potrzebne są co najmniej następujące

zasoby:

•

procesor

•

pami

ęć operacyjna

•

urz

ądzenia wejścia / wyjścia

Aby procesy mog

ły być wykonywane niezbędne jest ku temu

odpowiednie

środowisko. Podstawowe architektury używanych obecnie

systemów komputerowych mo

żna podzielić:

1. Komputery z jednym procesorem
2. Komputery równoleg

łe

3. Systemy rozproszone

Komputery
równolegle

Wieloprocesory

(Pami

ęć

wspólna)

Multikomputery

(Pami

ęć lokana)

Komputery

z jednym

procesorem

Komputery

Systemy

rozproszone

Systemy jednoprocesorowe
Wi

ększość tradycyjnych komputerów posiada właśnie taką architekturę.

System sk

łada się z procesora, pamięci i różnych urządzeń wejścia /

wyj

ścia (dysków, napędów dyskietek, kart sieciowych, portów

szeregowych i równoleg

łych itd.). Urządzenia wejścia / wyjścia są

pod

łączone do szyny komputera za pomocą kontrolerów tych urządzeń.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 5

Procesor

Pami

ęć

Kontroler

we/wy

2

Magistrala

Urz

ądzenia we /wy

Kontroler

we/wy

1

Kontroler

we/wy

N

Sie

ć

Rys. 4 Struktura systemu jednoprocesorowego

Komputery równoleg

łe (Tanneubauma) dzielą się na dwie klasy. Podział

ten bierze pod uwag

ę komunikację pomiędzy procesorami. Może ona

by

ć przez:

•

wspóln

ą pamięć

•

system wej

ścia wyjścia

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 6

Wieloprocesory (Multiprocessors), maszyny SMP (ang. Symetric
Multiprocessors)

Jedna przestrze

ń adresowa dzielona pomiędzy wiele

procesorów.

RAM

SIEC PRZE

ŁACZAJACA

CPU 1

CPU 2

CPU N

Schemat multiprocesora

Programowanie multiprocesorów SMP (Shared Memory Processors)

Programowanie multiprocesorów musi uwzgl

ędniać ich architekturę a w

szczególno

ści charakterystyką dostępu do pamięci:

Wszystkie procesory maj

ą dostęp do tego samego obszaru pamięci.

Narz

ędzia programowania:

Model w

ątków operujących na wspólnym obszarze pamięci. Wątki

komunikuj

ą się przez wspólną pamięć a wzajemne wykluczanie

zapewnione jest przez monitory, muteksy czy semafory.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 7

Multikomputery (ang. Multicomputers)
Ka

żdy z procesorów ma swą własną przestrzeń adresowa

SIEC PRZE

ŁACZAJACA

CPU 1

CPU 2

CPU N

RAM 1

RAM 2

RAM N

I/O 1

I/O 2

I/O N

Schemat Multikomputera

Programowanie multikomputerów
W

łasności architektury multikomputerów które muszą być uwzględnione

przy

programowaniu.

1. Ka

żdy z procesorów ma dostęp tylko do swej lokalnej pamięci.

2. Procesory komunikuj

ą się ze sobą poprzez system wejścia /

wyj

ścia a dalej poprzez sieć połączeń.

Do programowania multikomputerów wykorzystywany jest model
procesów komunikuj

ących się poprzez wymianę komunikatów (model

komunikuj

ących się procesów).

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 8

Systemy rozproszone
System rozproszony sk

łada się z wielu niezależnych komputerów

po

łączonych za pomocą sieci.

Pracuj

ące na nich aplikacje komunikują się poprzez sieć.

RAM

Procesor

System

WE/WY

RAM

Procesor

System

WE/WY

RAM

Procesor

System

WE/WY

Sie

ć

Rys. 5 Struktura systemu rozproszonego

Do programowania systemów rozproszonych wykorzystywany jest
model procesów komunikuj

ących się poprzez wymianę komunikatów

(model komunikuj

ących się procesów).

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 9

1.5 Sprz

ętowe podstawy współbieżności

Niezb

ędnym minimum sprzętowym potrzebnym do implementacji takiego

systemu jest:

- System przerwa

ń

- Uk

ład zegarowy generujący impulsy które są zamieniane w

przerwania.

Procesor

Pami

ęć

Kontroler

przerwa

ń

Zegar

Kontroler

we/wy

M

Kontroler

we/wy

1

IRQ 1

IRQ 2

IRQ N

INT

Magistrala

Urz

ądzenia we /wy

Rys. 6 Uproszczony schemat komputera mog

ącego wykonywać

wspó

łbieżnie wiele procesów.

Zdarzenia w systemie komputerowym:

•

Uk

ład zegarowy cyklicznie generuje żądania przerwań IRQ0.

•

Kontrolery urz

ądzeń wejścia / wyjścia generują żądania IRQ1 -

IRQN gdy wyst

ąpi w nich pewne zdarzenie.

•

Żądania przerwań IRQ0 – IRQN doprowadzane są do kontrolera

przerwa

ń.

•

Kontroler wysy

ła do procesora przerwanie INT.

Procesor

Kontroler IO

Programowanie

ukladu IO

Obliczenia

transfer

Obliczenia

przerwanie

Przebieg operacji wej

ścia wyjścia wykonywanej przez kontroler

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 10

P1

Procesor

Kontroler IO

P1

P1

P1

T1

Proces P1 wykonywany w trybie wy

łącznym

Procesor

Kontroler IO

P2

P2

P2

P2

T2

Proces P2 wykonywany w trybie wy

łącznym

P1

Procesor

Kontroler IO

P1

P1

P1

P2

P2

P2

P2

T3

Procesy P1 i P2 wykonywane w trybie wieloprogramowym T3 < T1 + T2

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 11

1.6 Prze

łączanie procesów, wieloprogramowość

Wspó

łczesne komputery są na tyle wydajne że bez trudności mogą

wykonywa

ć wiele procesów które współdzielą czas procesora.

Procesy zgodnie z kolejno

ścią wyznaczoną przez procedurę szeregującą

(ang. scheduler) wykonywane s

ą kolejno przez zadany kwant czasu

(ang. time slice).

P1

P2

P3

Czas

Rys. 7 Procesy P1, P2, P3 wykonuj

ące się w trybie podziału czasu (ang.

time scharing)

Podstawowym mechanizmem umo

żliwiającym taki tryb pracy są

przerwania.

ISR

Procedura

obs

ługi

przerwania

Przerwanie

Powrót z

procedury

obs

ługi przerwania

proces P

proces P

Czas

Zachowanie

rejestrów

Odtwo-

rzenienie
rejestrów

Obs

ługa zdarzenia poprzez procedurę obsługi przerwania

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 12

Obs

ługa przerwania - chwilowe wstrzymanie aktualnie wykonywanego

procesu i wykonanie procedury przypisanej zdarzeniu powoduj

ącemu

przerwanie po zako

ńczeniu której następuje powrót do przerwanego

procesu.


Pojedynczy prze

łączenie składa się z trzech faz:

1. Zachowania kontekstu procesu dotychczas wykonywanego.
2. Podj

ęcie decyzji który z procesów wznowić.

3. Przywrócenie kontekstu nowego procesu.



Kontekst procesu – wszystkie informacje potrzebne do wznowienia
zawieszonego wcze

śniej procesu.

P1

P2

Czas

wykonywanie

P1

zachowanie

kontekstu P1

przywrócenie

kontekstu P2

wykonywanie

P2

zachowanie

kontekstu P2

przywrócenie

kontekstu P1

P1

Zachowanie kontekstu, wykonywanie i przywrócenie kontekstu
procesu

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 13

Prze

łączenia procesów mają miejsce w następujących sytuacjach:

•

Wyst

ąpiło przerwanie zegarowe i system stwierdził że

wykonywany proces wyczerpa

ł już swój kwant czasu.

•

Wyst

ąpiło przerwanie zewnętrzne np. od kontrolera wejścia /

wyj

ścia pewnego urządzenia sygnalizujące zakończenie się

zleconej wcze

śniej operacji.

•

Proces bie

żący wykonał pewną niedozwoloną operację polegającą

na naruszeniu systemu ochrony zasobów procesora Zdarzenie
takie powoduje przerwanie wewn

ętrzne procesora .

•

Wykonywany proces wykona

ł wywołanie systemowe zmieniające

status gotowo

ści przynajmniej jednego procesu.

Prze

łączenia procesów występują w nie dających się przewidzieć

momentach czasu. St

ąd nie można czynić założeń że pewien ciąg

instrukcji danego procesu nie zostanie przerwany.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 14

1.7 Przeplot i operacje atomowe

W systemach z jednym procesorem procesy wspó

łbieżne muszą się

wykonywa

ć z wykorzystaniem podziału czasu procesora (przeplot).

Program jest zazwyczaj pisany w j

ęzyku wysokiego poziomu.

Wykonywane s

ą natomiast instrukcje kodu maszynowego będące

wynikiem kompilacji programu

źródłowego przez kompilator.

Operacja atomowa
Operacj

ą atomową nazywamy taką operację która wykonywana jest

przez procesor niepodzielnie. Znaczy to

że o ile się rozpocznie, musi być

w trybie wy

łącznym wykonana i zakończona.

Pojedyncza instrukcja kodu maszynowego jest operacj

ą atomową.

Trudno jest stwierdzi

ć jakie operacje zapisane w języku wyższego

poziomu b

ędą operacjami atomowymi.

Wyodr

ębnienie instrukcji atomowych jest istotne gdy dwa lub więcej

procesy korzystaj

ą ze wspólnego obszaru pamięci.

Przyk

ład 1 - hazard

Zmienna wspólna

X = 0

Proces 1

Proces 2

X++

X++

Dwa procesy inkrementuj

ą wspólna zmienną

Instrukcja ta mo

że być przetłumaczona przez kompilator co najmniej na

dwa sposoby:

Sposób 1

Sposób 2

INC X

MOV A,X

ADD A, 1

MOV X, A

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 15

Proces Instrukcja

Warto

ść X

0

P1

INC X

1

P2

INC X

2

Przypadek 1

Proces Instrukcja

Warto

ść X

0

P1

MOV A, X

0

P1

ADD A,1

0

P2

MOV A, X

0

P2

ADD A,1

0

P1

MOV X, A

1

P2

MOV X, A

1

Przypadek 2


Przyk

ład 2 - wyścigi

Aplikacja sk

łada się z dwu procesów P1 i P2 mających dostęp do

wspólnej zmiennej i.

Proces P1

Proces P2

i = 0;

i = 0;

while ( i < 10) {

while ( i > - 10) {

i = i +1;

i = i - 1;

}

}

printf(„P1 – wygra

ł”); printf(„P2 – wygrał”);

W powy

ższym przykładzie instrukcje atomowe kodu procesów P1 i P2 są

przeplatane.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 16

A1 A2 A3 A4

...

An

Instrukcje procesu P1

B1 B2 B3 B4

...

Bn

Instrukcje procesu P2

A1 A2 B1 B2 B3 A3 A4 A5

...

An

B4

Przeplot instrukcji procesu P1 i P2

Rys. 8 Instrukcje procesów P1 i P2 wykonywane w trybie przeplotu

- Nie mo

żemy poczynić żadnych założeń dotyczących momentów

prze

łączenia procesów P1 i P2

- Nie da si

ę określić wyniku działania powyższych procesów.

Wynik dzia

łania aplikacji współbieżnej nie może być uzależniony od

sposobu prze

łączania procesów. Musi być prawidłowy dla wszystkich

mo

żliwych przeplotów.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 17

1.8 Poprawno

ść aplikacji współbieżnych

Kryterium poprawno

ści aplikacji sekwencyjnej

Aplikacja sekwencyjna jest poprawna je

żeli:

1. Zatrzymuje si

ę

2. Je

żeli się zatrzyma to da poprawne wyniki

Na ogó

ł aplikacje współbieżne nie działają w taki sposób że z danych

wej

ściowych wyliczają wynik i zatrzymują się. Typowe aplikacje

wspó

łbieżne to:

- systemy operacyjne,
- aplikacje steruj

ące obiektami,

- serwery baz danych
- serwery WWW.

Aplikacje te nie ko

ńczą się, a nawet jeżeli, to nie jest ich zadaniem

przedstawienie jakiego

ś końcowego wyniku. Dla tego typu aplikacji

wa

żniejsze są własności dynamiczne to znaczy zachowanie się aplikacji

w czasie.
Wa

żne jest aby system operacyjny prawidłowo sterował komputerem i

nie zawiesza

ł się, program sterujący utrzymywał obiekt w pożądanym

stanie a serwer bazy danych odpowiada

ł na zlecenia prawidłowo i w

rozs

ądnym czasie.

Dla okre

ślenia prawidłowości aplikacji współbieżnych używa się pojęć:

•

Bezpiecze

ństwa,

•

Żywotności

•

Uczciwo

ści.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 18

Bezpiecze

ństwo

Aplikacja jest bezpieczna je

żeli utrzymuje system w pożądanym stanie.

Aplikacja nie jest bezpieczna je

żeli:

•

Da nieprawid

łowe wyniki – np. nie jest zachowany warunek

wzajemnego wykluczania

•

Nie b

ędzie wykonywał pożądanych działań - ulegnie blokadzie

Z1 Z1 Z3

...

Z2

Z2

Kolejka zleceń

Serwer

K1

K2

KN

Klienci

O1

Odpowiedź

Rys. 9 Model przetwarzania typu klient - serwer

W odniesieniu do modelu klient – serwer bezpiecze

ństwo oznacza że

klienci s

ą obsługiwani w zadowalający sposób.

1. Serwer nie zaprzesta

ł obsługi zleceń.

2. Na zlecenia odpowiada

ł w prawidłowy sposób.

Blokada
Ka

żdy z zablokowanych procesów oczekuje na zdarzenie które może

by

ć wygenerowane tylko przez któryś z zablokowanych procesów.

Blokada zwana te

ż zakleszczeniem jest typowym zagrożeniem aplikacji

wspó

łbieżnych.

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 19

Zag

łodzenie

Zag

łodzenie występuje gdy procesowi cały czas odmawia się dostępu do

zasobów których ten potrzebuje by wykona

ć zlecone mu zadanie.

Wzajemne wykluczanie
Wzajemne wykluczanie musi by

ć zapewnione gdy kilka procesów ma

dost

ęp do wspólnego obszaru pamięci i przynajmniej jeden z nich

modyfikuje ten obszar.


Dla aplikacji wspó

łbieżnych nie formułuje się warunku zakończenia.

Odpowiednikiem jest

żywotność.

Żywotność
Aplikacja jest

żywotna jeżeli każde pożądane zdarzenie w końcu zajdzie.

W modelu klient – serwer

żywotność oznacza że każdy klient zostanie w

ko

ńcu obsłużony.

Uczciwo

ść

Aplikacja jest uczciwa je

żeli żądające obsługi procesy są traktowane

jednakowo lub zgodnie ze swoimi priorytetami.


W modelu klient – serwer uczciwo

ść oznacza że każdy klient zostanie

obs

łużony zgodnie z kolejnością zgłoszeń lub priorytetem.

Wyró

żnia się następujące rodzaje uczciwości:

1. Uczciwo

ść słaba – jeżeli proces nieprzerwanie zgłasza żądanie to

kiedy

ś będzie ono obsłużone.

2. Uczciwo

ść mocna – jeśli proces zgłasza żądanie nieskończenie wiele

razy to w ko

ńcu zostanie ono obsłużone.

3. Uczciwo

ść liniowa – jeśli proces zgłasza żądanie będzie ono

obs

łużone zanim dowolny inny proces będzie obsłużony więcej niż

raz.

4. Uczciwo

ść typu FIFO – żądania procesów są obsługiwane zgodnie z

kolejno

ścią ich zgłaszania. (FIFO – ang. First-In First-Out)

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 20

sprawdzanie

sprawdzanie

Uczciwo

ść mocna – proces zgłasza żądanie nieskończoną ilość

sprawdzanie

sprawdzanie

Uczciwo

ść słaba – proces musi zgłaszać żądanie nieprzerwanie

PDF created with pdfFactory trial version

www.pdffactory.com

J. U

łasiewicz Programowanie aplikacji współbieżnych 21

1.9 Skutki stosowania wspó

łbieżności

Korzy

ści wynikające z zastosowania współbieżności:

1. Polepszenie wykorzystania zasobów. Gdy jaki

ś proces czeka na

niedost

ępny w danej chwili zasób, procesor może wykonywać inny

proces.

2. Podzia

ł zadania na procesy umożliwia wykonywanie ich na

oddzielnych maszynach. Prowadzi to do zrównoleglenia
przetwarzania.

3. Podzia

ł dużego zadanie na wiele mniejszych komunikujących się

procesów prowadzi do dekompozycji problemu. Przez co u

łatwia ich

implementacj

ę, uruchamianie i testowanie przez wielu niezależnych

programistów.

Trudno

ści powstające przy implementacji aplikacji współbieżnych:

- problem sekcji krytycznej
- problem synchronizacji procesów
- problem zakleszczenia

Procesy tworz

ące aplikację nie działają w izolacji. Muszą jakoś ze sobą

wspó

łpracować co prowadzi do:

- Konieczno

ści wzajemnej wymiany informacji - komunikacja

mi

ędzyprocesowa.

- Zapewnienia okre

ślonej kolejności wykonania pewnych akcji -

problem synchronizacji.

Przedmiot programowania wspó

łbieżnego

Metodologia tworzenia aplikacji sk

ładających się z wielu komunikujących

si

ę i dzielących zasoby procesów współbieżnych.

PDF created with pdfFactory trial version

www.pdffactory.com