1
Systemy
wieloprocesorowe
Wykład 9 i 10
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 AB.
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.