1

Systemy
wieloprocesorowe

Wykład 9 i 10

2

Systemy rozproszone
silnie powiązane

W systemach wieloprocesorowych

silnie powiązanych

- procesory dzielą

pamięć i zegar. W takich systemach
komunikacja odbywa się głównie
przez pamięć dzieloną.

3

Systemy rozproszone
słabo powiązane

W

słabo powiązanych

systemach

procesory nie dzielą pamięci ani zegara.
Każdy procesor ma własną pamięć
lokalną. Procesory komunikują się ze
sobą za pomocą różnych linii
komunikacyjnych. Tego rodzaju systemy
wieloprocesorowe są zazwyczaj zwane
systemami

rozproszonymi.

4

Rozproszone
systemy procesorowe

System

rozproszony

jest zbiorem luźno

powiązanych ze sobą procesorów
połączonych siecią komunikacyjną.
Procesory nie dzielą pamięci ani
zegara, każdy procesor ma własną
lokalną pamięć.

5

Powody budowy systemów
rozproszonych



dzielenie zasobów,



przyspieszanie obliczeń,



niezawodność,



komunikacja.

6

Dzielenie zasobów

Dzielenie zasobów stanowi mechanizm

umożliwiający dzielenie plików na
zdalnych stanowiskach, przetwarzanie
informacji w rozproszonych bazach
danych, drukowanie plików na
zdalnych stanowiskach, używanie
wyspecjalizowanych urządzeń
sprzętowych.

7

Przyspieszanie obliczeń

Przyspieszanie obliczeń można

osiągnąć poprzez podzielenie
konkretnego obliczenia na pewną
liczbę obliczeń częściowych
wykonanych współbieżnie.

8

Niezawodność -

Awaria jednego stanowiska nie

powoduje przerwania pracy
pozostałych.

9

Komunikacja

Użytkownicy

uzyskują

możliwość

wymiany informacji w przypadku,
gdy stanowiska połączone są ze sobą
za pomocą sieci komunikacyjnej. Jest
to podobne do systemu komunikatów
dla pojedynczego komputera.

10

Typy systemów
operacyjnych

Systemy operacyjne dzielimy
na

sieciowe i rozproszone

11

Sieciowy S.O.

Użytkownicy rejestrują się zdalnie na odpowiednich

maszynach, o których istnieniu wiedzą.

Głównym zadaniem sieciowego S.O. jest umożliwienie

przesyłania plików z jednej maszyny do drugiej. W

środowisku sieciowym każde stanowisko utrzymuje

własny, lokalny system plików.

Użytkownik musi dokładnie wiedzieć gdzie ma szukać

pliku. Aby uzyskać dostęp do pliku musi być on

jawnie skopiowany na jego stanowisko. Stosuje się

zatem się mechanizm kopiowania plików.

12

Rozproszony S.O.

W rozproszonym S.O. użytkownicy

uzyskują dostęp do zdalnych zasobów
w taki sam sposób jak do lokalnych.
Nie muszą być świadomi wielości
maszyn.

Przemieszczanie danych i procesów z

jednego stanowiska do drugiego
odbywa się pod nadzorem S.O. w
sposób przezroczysty dla użytkownika.

13

W rozproszonym S.O.

rozpatrujemy:



przemieszczanie

danych

,



przemieszczanie

obliczeń,



przemieszczanie

procesów.

14

Przemieszczanie danych

Przemieszczanie danych polega na

przesyłaniu całego pliku, korzystaniu
z niego lokalnie a następnie
odsyłanie zmienionej kopii. Można
również przesyłać jedynie potrzebną
porcję pliku.

15

Przemieszczanie obliczeń

Przemieszczanie obliczeń

może być

realizowane na trzy sposoby:



- wywoływanie zdalnej, wcześniej przygotowanej

procedury na żądanym stanowisku,



- wysłanie komunikatu do żądanego stanowiska.

S.O. tworzy nowy proces, który po zakończeniu

działania wysyła wyniki do pierwotnego procesu

również za pomocą komunikatu,



- obydwie powyższe metody jednocześnie.

16

Przemieszczanie
procesów

Przemieszczanie procesów

- wykonywanie procesu

na innym stanowisku niż go zainicjowano.

Stosowane by zmniejszyć obciążenie danego

stanowiska lub wykonać proces na lepszym sprzęcie

czy odpowiednim oprogramowaniu.

Przemieszczanie może być ukrywane przez system

przed użytkownikiem lub użytkownik może jawnie

określić, jak proces może być przemieszczany.

Procesy można rozmieszczać w sieci w celu

wyrównania obciążenia pracą poszczególnych

stanowisk.

Jeśli pojedynczy proces da się podzielić na pewną

liczbę podprocesów, to mogą one być wykonywane

współbieżnie na różnych stanowiskach, dzięki czemu

łączny czas wykonania całego procesu jest krótszy.

17

W środowisku S.O. rozproszonego należy

rozpatrywać następujące zagadnienia:



koordynacja
(synchronizacja+komunikacja),



wzajemne wyłączanie w środowisku
rozproszonym,



awarie, odporność systemu na
zakłócenia,



czynniki wpływające na niezawodność
systemu,



rozproszone systemy plików.

18

Koordynacja rozproszona

W systemie rozproszonym nie ma

wspólnej pamięci ani wspólnego
zegara, toteż niekiedy trudno jest
stwierdzić, które z dwu zdarzeń
wystąpiło najpierw. A jest to bardzo
ważne ponieważ np. użycie zasobu nie
może nastąpić wcześniej niż po
uzyskaniu zgody na jego przydzielenie.

19

Porządkowanie zdarzeń



W systemie scentralizowanym jest zawsze możliwe

określenie kolejności, w której wystąpiły dwa

zdarzenia, ponieważ jest w nim jedna wspólna

pamięć i zegar. W wielu zastosowaniach możliwość

określenia porządku jest niezmiernie ważna np.

przy przydziale zasobów określa się, że zasób może

zostać użyty tylko po uzyskaniu zgody na jego

przydzielenie - jednak w systemie rozproszonym

nie ma wspólnej pamięci ani wspólnego zegara.



Niekiedy jest więc niemożliwe stwierdzenie, które z

dwu zdarzeń wystąpiło wpierw.



Relacja uprzedniości zdarzeń określa tylko

częściowy porządek zdarzeń w systemach

rozproszonych.

20

Poniżej zostanie przedstawiony

algorytm rozproszony, który
rozszerza relację uprzedniości
zdarzeń na całkowite
uporządkowanie wszystkich zdarzeń
w systemie.

21

Relacja uprzedniości
zdarzeń

Ponieważ rozważamy tylko procesy

sekwencyjne, wszystkie zdarzenia
(również komunikaty) są całkowicie
uporządkowane. Możemy zdefiniować
relację uprzedniości zdarzeń,
oznaczaną przez , na zbiorze

zdarzeń, w sposób następujący:

22

Relacja uprzedniości
zdarzeń



1. Jeśli A i B są zdarzeniami w tym
samym procesie i A zostało wykonane
przed B, to AB.



2. Jeśli A jest zdarzeniem wysłania
komunikatu przez pewien proces i B jest
zdarzeniem odebrania tego komunikatu
przez inny proces, to A B.



3. Jeśli A  B i B  C, to A  C.

23

Relacja uprzedniości
zdarzeń

Jeśli dwa zdarzenia, A i B nie są związane

relacją , to mówimy, że takie dwa zdarzenia

wystąpiły współbieżnie, żadne z nich nie

może przyczynowo oddziaływać na drugie,

jeśli jednak A  B, to jest możliwe, że

zdarzenie A wpłynie przyczynowo na

zdarzenie B. Uprzedniość zdarzeń może być

zilustrowana za pomocą diagramu

czasoprzestrzennego (rysunek). Przedstawia

on czas względny dla trzech procesów

współbieżnych.

24

Uprzedniość zdarzeń

p4 q4 r1
p3 q3
p2 q2
p1 q1
p0 q0 r0

25

Uprzedniość zdarzeń

p4 q4 r1
p3 q3
p2 q2
p1 q1
p0 q0 r0

Kierunek poziomy
reprezentuje przestrzeń,
tzn. różne procesy,
kierunek pionowy - czas.

Opatrzone etykietami
pionowe linie
symbolizują procesy.

Elipsy oznaczają
zdarzenia.

Strzałki symbolizują
komunikat przesłany od
jednego procesu do
drugiego.

26

Zdarzenia A i B są równoczesne wtedy
i tylko wtedy, gdy nie istnieje żadna
ścieżka z A do B, ani z B do A.

p4 q4 r1
p3 q3
p2 q2
p1 q1
p0 q0 r0

p1  q2,

r0  q4

q3  r1

p1  q4

(ponieważ p1 

q2 i q2  q4)

27

p4 q4 r1
p3 q3
p2 q2
p1 q1
p0 q0 r0

Niektórymi
spośród zdarzeń
równoczesnych w
tym systemie są

r0 i q3
r0 i p3
q3 i p3

28

Nie jesteśmy w stanie określić, które ze

zdarzeń takich jak q0 i p2 wystąpiło
pierwsze. Nie jest to jednak istotne,
ponieważ żadne ze zdarzeń nie
oddziałuje na drugie (żadne z nich nie
może wiedzieć, czy drugie już
wystąpiło).

Ważne jest tylko, aby dla dowolnych

procesów, dla których

porządek dwu

zdarzeń równoczesnych ma znaczenie,
można było ustalić jakąś kolejność.

29

Implementacja

Ponieważ w systemie rozproszonym nie ma

wspólnego zegara, aby móc określić

kolejność zdarzeń, definiuje się relację

uprzedniości zdarzeń.

Z każdym zdarzeniem

systemowym kojarzymy znacznik czasu

(time stamp). Możemy wówczas

zdefiniować warunek ogólnego

uporządkowania: dla każdej pary zdarzeń A

i B, jeżeli A  B, to znacznik czasu A jest

mniejszy niż znacznik czasu B.

30

Jak można narzucić warunek
globalnego uporządkowania w
środowisku rozproszonym?



W każdym procesie Pi definiujemy zegar

logiczny

ZLi

:

prosty licznik

zwiększany

między wystąpieniami każdych dwu

kolejnych zdarzeń w procesie.



Jeśli zdarzenie A poprzedza zdarzenie B w

procesie Pi , to

ZLi(A) < ZLi(B)



Schemat ten zapewnia dla każdych dwu

zdarzeń w tym samym procesie

spełnienie

warunku ogólnego uporządkowania.

31

Przedstawiony schemat

nie gwarantuje

, że

warunek uporządkowania całkowitego będzie
spełniony

dla procesów

. Rozważmy dwa

komunikujące się ze sobą procesy P1 i P2.
Załóżmy, że P1 wysyła komunikat do P2
(zdarzenie A) z ZL1(A)=200, a proces P2
odbiera ten komunikat (zdarzenie B) z
ZL2(B)=195

(ponieważ procesor procesu P2 jest

wolniejszy od procesora procesu P1, więc jego zegar
logiczny tyka wolniej).

Sytuacja ta narusza więc

nasz warunek, gdyż A  B, lecz znacznik czasu

A jest większy od znacznika czasu B.

W celu usunięcia tej trudności będziemy wymagali, aby

proces przesunął swój zegar logiczny, gdy otrzyma
komunikat, którego znacznik czasu jest większy niż
bieżąca wartość jego zegara logicznego.

32



Jeżeli proces Pi, otrzymuje komunikat (zdarzenie

B) ze znacznikiem czasu t i

ZLi(B)<=t

to

powinien przesunąć swój zegar tak, aby

ZLi(B)=t+1

.

W naszym przykładzie, gdy proces P2 otrzyma

komunikat od P1 powinien tak przestawić swój

zegar aby ZL2(B)=201



Aby otrzymać uporządkowanie całkowite,

powinniśmy zaobserwować, że w naszym

schemacie porządkowania według znaczników

czasowych, równość dwu znaczników czasu

zdarzeń A i B oznacza równoczesność tych

zdarzeń aby pokonać tę przeszkodę i utworzyć

uporządkowanie całkowite, można posłużyć się

liczbami identyfikującymi procesy.

33

Wzajemne wyłączanie w
środowisku rozproszonym

Zakładamy, że system składa się z n procesów, z

których każdy rezyduje w innym procesorze. Załóżmy,

że procesy są jednoznacznie ponumerowane od 1 do n,

oraz że między procesami istnieje odwzorowanie jeden

do jednego (tzn. każdy proces ma własny procesor).

Wyróżniamy następujące podejścia:



a)

podejście scentralizowane

- jeden z procesów jest

wybrany do koordynowania wejść do sekcji krytycznej;



b)

podejście w pełni rozproszone

- gdy proces chce

wejść do sekcji krytycznej - wówczas wysyła

zamówienie do wszystkich procesów w systemie. Po

otrzymaniu odpowiedzi od wszystkich - wchodzi do

sekcji krytycznej.



c)

metoda przekazywania żetonu

- żeton jest

specjalnym rodzajem komunikatu przekazywanym w

obrębie systemu. Ten proces, który ma żeton może

wejść do sekcji krytycznej.

34

Podejście zcentralizowane

W celu zapewnienia wzajemnego wykluczania jeden z

procesów w systemie zostaje wybrany do koordynowania

wejść do sekcji krytycznej.



Każdy proces, który chce spowodować wzajemne

wyłączanie wysyła komunikat z zamówieniem do

koordynatora. Kiedy proces otrzyma od koordynatora

komunikat z odpowiedzią, wtedy może wejść do swojej sekcji

krytycznej. Po wyjściu z sekcji krytycznej proces wysyła do

koordynatora komunikat zwalniający i kontynuuje działanie.



Po otrzymaniu komunikatu z zamówieniem koordynator

sprawdza czy jakiś inny proces jest w swojej sekcji

krytycznej. Jeżeli nie ma takiego procesu, to koordynator

wysyła komunikat z odpowiedzią, w przeciwnym razie

zamówienie zostaje włączone do kolejki; gdy koordynator

otrzyma komunikat o zwolnieniu, wówczas usuwa jeden z

komunikatów z zamówieniami z kolejki i wysyła komunikat z

odpowiedzią do procesu zamawiającego.



Algorytm ten gwarantuje wzajemne wyłączanie. Opisany

schemat wymaga trzech komunikatów na wejściu do sekcji

krytycznej: zamówienia, odpowiedzi i zwolnienia.

35

Podejście w pełni
rozproszone

Gdy proces Pi chce wejść do sekcji krytycznej, wówczas wytwarza nowy znacznik czasu

ZC

i wysyła komunikat zamówienie

(Pi, ZC)

do wszystkich innych procesów w

systemie, także dla siebie. Po otrzymaniu komunikatu zamawiającego, proces może

odpowiedzieć natychmiast (tj. wysłać komunikat z odpowiedzią do Pi), lub może

zwlekać z wysłaniem odpowiedzi (bo np. właśnie znajduje się w sekcji krytycznej).

Proces, który otrzyma komunikat z odpowiedzią od wszystkich innych procesów w

systemie, może wejść do swojej sekcji krytycznej powoduje ustawianie

nadchodzących zamówień w kolejce i ich odwlekanie.

Po opuszczeniu sekcji krytycznej proces wysyła komunikaty z odpowiedziami na

wszystkie opóźniane zamówienia.

Rodzaj odpowiedzi procesu Pi na komunikat zamówienie

(Pj, ZC)

zależy od 3 czynników:



Jeśli proces Pi przebywa w sekcji krytycznej, to opóźnia odpowiedź do Pj.



Jeśli proces Pi nie chce wejść do sekcji krytycznej, to odpowiedź do Pj wysyła

natychmiast.



Jeśli proces Pi chce wejść do sekcji krytycznej, lecz jeszcze do niej nie wszedł, to

porównuje znacznik czasu swojego zamówienia ze znacznikiem czasu

ZC

zamówienia, które nadeszło od procesu Pj. Jeśli jego znacznik czasu jest większy od

ZC

, to natychmiast wysyła odpowiedź do Pj (Pj prosił pierwszy). W przeciwnym razie

zwleka z odpowiedzią.

Algorytm

ten wykazuje pożądane cechy.

Pozwala uzyskać wzajemne wykluczanie

. Nie grozi głodzenie, ponieważ wejście do sekcji

krytycznej jest planowane według znaczników czasu. Uporządkowanie według

znaczników czasu gwarantuje obsługę procesów w porządku „pierwszy zgłoszony -

pierwszy obsłużony".

Liczba komunikatów

potrzebnych do wejścia do sekcji krytycznej wynosi 2 * (n - 1). Jest

to

minimalna

liczba komunikatów wymaganych do wejścia do sekcji krytycznej w

warunkach niezależnego i współbieżnego działania procesów.

36

Metoda przekazywania
żetonu

Żeton jest specjalnym rodzajem

komunikatu, przekazywanym w obrębie

systemu. Ten proces, który ma żeton

może wejść do sekcji krytycznej.

Ponieważ w systemie jest tylko jeden

żeton, w danej chwili tylko jeden proces

może znaleźć się w sekcji krytycznej.

37

Zapobieganie blokadom

Zapobieganie blokadom w środowisku rozproszonym

opiera się na

1.

wprowadzaniu poprawek do sposobów zapobiegania

blokadom w środowisku jednoprocesorowym. Jest to

czekanie albo śmierć:



opiera się na technice bez wywłaszczeń,



jeśli proces Pi zamawia zasób przetrzymywany

przez Pj to jeśli jego znacznik czasowy Pi jest

mniejszy od znacznika czasowego procesu

przetrzymującego Pj to czeka w przeciwnym razie

zamawiający wypada z pamięci (umiera).

W tym schemacie starszy proces musi czekać, aż

młodszy zwolni zasoby. Im proces starszy tym

większa jest jego tendencja do czekania.

38

2

. na schematach opartych na porządkowaniu tzw.

znaczników czasowych z wywłaszczaniem

zasobów. Każdy proces otrzymuje jednoznaczny

numer priorytetu

. To pozwala

uniknąć blokad

(ale

może spowodować głodzenie procesów z niskimi

priorytetami).

Zranienie lub czekanie:



oparty na wywłaszczeniach,



jeśli Pi zamówi zasób przetrzymywany przez Pj to

Pi może czekać, gdy ma większy znacznik czasowy

(Pi-młodszy od Pj) w przeciwnym razie Pj jest

usuwany z pamięci (Pj zraniony przez Pi).

Starszy proces nigdy nie czeka na młodszy proces.

39

Odporność systemu na
uszkodzenia

Systemy rozproszone są narażone na różnego

rodzaju uszkodzenia sprzętu. Aby system mógł

działać pomimo błędów musi wykrywać

uszkodzenia i umieć się rekonfigurować. Po

usunięciu awarii, system musi zrekonfigurować

się ponownie i przywrócić normalny stan.

Zadania S.O. stąd wynikające:

1. wykrywanie awarii,
2. rekonfiguracja,
3. wychodzenie z awarii.