8. Systemy

8. Systemy

z pami

z pami

ę

ę

ci

ci

ą

ą

rozproszon

rozproszon

ą

ą

Lesław Sieniawski © 2010

Przypomnienie

Przypomnienie

Pami

ęć

rozproszona

– cecha architektury komputera, gdzie

zapewniony jest sieciowy dost

ę

p do pami

ę

ci fizycznej, która

nie jest wspólna. Podzadania maj

ą

bezpo

ś

redni dost

ę

p tylko do

pami

ę

ci lokalnej, a dost

ę

p do pami

ę

ci innych maszyn (gdzie

wykonywane s

ą

inne podzadania) jest uzyskiwany poprzez

komunikacj

ę

.

CPU

RAM

CPU

RAM

Połączenia

sieciowe

Połączenia

sieciowe

CPU

RAM

CPU

RAM

System rozproszony

System rozproszony

-

-

definicje

definicje

1.

Zbiór niezale

ż

nych komputerów

, który z punktu

widzenia u

ż

ytkownika zachowuje si

ę

ł

ą

cznie jak

pojedynczy komputer

2.

Zbiór komputerów nie posiadaj

ą

cych wspólnej

pami

ę

ci ani zegara

3.

Zbiór niezale

ż

nych komputerów poł

ą

czonych

sieci

ą

komunikacyjn

ą

4.

Klasa systemów komputerowych

obejmuj

ą

ca:

–

Systemy słabo powi

ą

zane (ang.

loosely coupled;

np.

maszyny w sieci komputerowej)

–

Systemy silnie powi

ą

zane (ang.

tightly coupled

; np.

maszyny wieloprocesorowe)

Korzy

Korzy

ś

ś

ci z system

ci z system

ó

ó

w rozproszonych

w rozproszonych

Współu

ż

ytkowanie zasobów

(danych, urz

ą

dze

ń

)

Współdzielenie obci

ąż

enia zadaniami

Zwi

ę

kszenie dost

ę

pno

ś

ci

(dublowanie zasobów,

zast

ę

powanie zasobów i przenoszenie zada

ń

w razie

awarii)

Potencjalne

polepszenie wska

ź

ników ekonomicznych

wzgl

ę

dem systemu scentralizowanego

Elastyczno

ść

w zakresie zwi

ę

kszania mocy

obliczeniowej

Dobra

skalowalno

ść

systemu (łatwo

ść

dostosowywania

systemu do rosn

ą

cych obci

ąż

e

ń

)

Wady system

Wady system

ó

ó

w rozproszonych

w rozproszonych

Zło

ż

one oprogramowanie

Dla rozwi

ą

za

ń

heterogenicznych (mieszane

architektury i platformy systemowe)

konieczno

ść

standaryzacji interfejsów komunikacyjnych

(sprz

ę

t/protokoły)

Silna zale

ż

no

ść

od poprawnego działania interfejsów

komunikacyjnych

Wi

ę

ksza podatno

ść

na zagro

ż

enia bezpiecze

ń

stwa

Cechy system

Cechy system

ó

ó

w rozproszonych

w rozproszonych

Przezroczysto

ść

(ang. transparency) ze wzgl

ę

du na:

– Współu

ż

ytkowanie zasobów

(fakt korzystania z

zasobów nie jest widoczny dla innych u

ż

ytkowników)

– Poło

ż

enie

(lokalizacja zasobu sprz

ę

towego lub danych

nie musi by

ć

znana)

– Mo

ż

liwo

ść

migracji zasobów

(plików, danych,

procesów, usług, maszyn wirtualnych)

– Redundancj

ę

danych

(np. replikacj

ę

) dla zwi

ę

kszenia

wydajno

ś

ci i/lub dost

ę

pno

ś

ci

– Potencjalne awarie

(wykonanie zadania nie zale

ż

y od

sprawno

ś

ci odr

ę

bnych zasobów sprz

ę

towych)

Cechy system

Cechy system

ó

ó

w rozproszonych (2)

w rozproszonych (2)

Niejednorodno

ść

elementów składowych

(ang.

heterogeneity):

– Sprz

ę

tu komputerowego

(ró

ż

ne architektury

komputerów)

– Oprogramowania komputerów

(ró

ż

ne systemy

operacyjne, oprogramowanie narz

ę

dziowe, metody

i

ś

rodki zarz

ą

dzania zasobami)

– Zastosowanych rozwi

ą

za

ń

sieciowych

(ró

ż

ne media

transmisyjne, protokoły telekomunikacyjne, interfejsy
fizyczne/logiczne)

Cechy system

Cechy system

ó

ó

w rozproszonych (3)

w rozproszonych (3)

Poziom autonomii elementów

wzgl

ę

dem cało

ś

ci

systemu:

– NISKI – centralne zarz

ą

dzanie zasobami

– WYSOKI – lokalne zarz

ą

dzanie zasobami

Topologia poł

ą

cze

ń

elementów systemu:

– W

ę

zły

– Kraw

ę

dzie

1

3

2

4

Elementy schemat

Elementy schemat

ó

ó

w po

w po

łą

łą

cze

cze

ń

ń

1

W

ę

zeł

(

inaczej

komputer, maszyna, serwer,

stanowisko, host, itp.)

Kraw

ę

d

ź

(inaczej poł

ą

czenie, ł

ą

cze, itp.)

W

W

ę

ę

ze

ze

ł

ł

systemu rozproszonego

systemu rozproszonego

Sprzęt

System

operacyjny

Inne

oprogramowanie

W

ę

zeł

Zasoby lokalne

Inny w

ę

zeł

Sprzęt

System

operacyjny

Inne

oprogramowanie

Zasoby zdalne

Topologie system

Topologie system

ó

ó

w rozproszonych

w rozproszonych

A

B

F

C

E

D

A

B

F

C

E

D

Poł

ą

czenie pełne

Poł

ą

czenie cz

ęś

ciowe

Koszt budowy: du

ż

y

Koszt komunikacji: mały
Niezawodno

ść

: du

ż

a

(awaria w

ę

zła po

ś

redniego nie psuje sieci)

Koszt budowy:

ś

redni-du

ż

y

Koszt komunikacji: mały
Niezawodno

ść

:

ś

rednia

(awaria w

ę

zła po

ś

redniego mo

ż

e zepsu

ć

sie

ć

)

1

2

3

4

5

Poł

ą

czenie drzewiaste

Poł

ą

czenie gwia

ź

dziste

1

2

3

4

5

6

Koszt budowy: mniejszy ni

ż

sieci cz

ęś

ciowej

Koszt komunikacji: wi

ę

kszy ni

ż

dla sieci pełnej

Niezawodno

ść

: mała

(awaria w

ę

zła po

ś

redniego psuje sie

ć

)

Koszt budowy: liniowo zale

ż

ny od liczby w

ę

złów

Koszt komunikacji: mały, potencjalne w

ą

skie

gardło w w

ęź

le centralnym

Niezawodno

ść

: mała

(awaria w

ę

zła centralnego psuje sie

ć

)

Poł

ą

czenie pier

ś

cieniowe

Poł

ą

czenie magistralowe

1

2

3

4

5

6

1

2

3

4

5

Koszt budowy: liniowo zale

ż

ny od liczby w

ę

złów

Koszt komunikacji: du

ż

y

Niezawodno

ść

: mała

(awaria ka

ż

dego w

ę

zła psuje sie

ć

)

Koszt budowy: liniowo zale

ż

ny od liczby w

ę

złów

Koszt komunikacji: mały
Niezawodno

ść

: mała dla magistrali,

du

ż

a dla w

ę

złów

Kryteria oceny topologii

Kryteria oceny topologii

Koszt budowy

: koszt poł

ą

czenia w

ę

złów w

cało

ść

(jednorazowy)

Koszt komunikacji

: czas przesyłania

komunikatu pomi

ę

dzy danymi

stanowiskami

Niezawodno

ść

: wpływ awarii w

ę

zła lub

kraw

ę

dzi na komunikacj

ę

pomi

ę

dzy

pozostałymi w

ę

złami

Komunikacja

Komunikacja

Nazwy i tłumaczenie nazw

(jak procesy odnajduj

ą

si

ę

nawzajem w celu

wymiany komunikatów)

Strategie wyznaczania tras

przesyłania

komunikatów

Strategie przesyłania pakietów

(pojedynczo,

grupowo)

Strategie poł

ą

cze

ń

(jak procesy wysyłaj

ą

ci

ą

gi

komunikatów)

Strategie rozstrzygania konfliktów

o dost

ę

p do sieci

Nazwy i t

Nazwy i t

ł

ł

umaczenie nazw

umaczenie nazw

Identyfikator w

ę

zła

– Nazwa domenowa

(nazwa DNS)

www.pwsz.nysa.pl

jednoznaczna, wygodna dla człowieka

– Adres IP

213.199.201.130

jednoznaczny, wygodny dla maszyny

Przekład nazw na adresy IP – usługa DNS

Identyfikator procesu

w danym w

ęź

le,

Wskazanie procesu

w zdalnym systemie:

<ID_w

ę

zła, lokalny_ID_procesu>

Strategie wyznaczania tras

Strategie wyznaczania tras

Ustalanie drogi

, któr

ą

zostanie przesłany komunikat do

zdalnego w

ę

zła:

– Jednoznaczne, gdy istnieje tylko jedna droga (np. topologia drzewa

lub gwiazdy)

– Wieloznaczne, gdy mo

ż

liwych dróg jest wi

ę

cej ni

ż

jedna (np.

topologia pier

ś

cienia, sie

ć

w pełni poł

ą

czona)

Tablica tras

w ka

ż

dym w

ęź

le – drogi alternatywne, koszt

poł

ą

czenia, aktualizacja tablicy

Wyznaczanie trasy

(ang. routing):

– Trwałe (trasa okre

ś

lona z góry, w zasadzie niezmienna)

– Metod

ą

obwodu wirtualnego (trasa ustalona na czas trwania jednej

sesji, np. przesłania pliku lub poł

ą

czenia terminalowego)

– Dynamiczne (tras

ę

okre

ś

la si

ę

tu

ż

przed wysłaniem komunikatu)

Strategie przesy

Strategie przesy

ł

ł

ania pakiet

ania pakiet

ó

ó

w

w

Implementacja przesyłania komunikatów

w postaci pakietów (ramek lub datagramów)

Przesyłanie pakietów

:

– bezpoł

ą

czeniowo

(bez gwarancji dostarczenia lub z

potwierdzeniem dostarczenia)

– poł

ą

czeniowo

(dla zwi

ę

kszenia niezawodno

ś

ci

wymiany pakietów)

Strategie po

Strategie po

łą

łą

cze

cze

ń

ń

Ł

ą

czenie par procesów w celu wymiany informacji

:

– Komutowanie ł

ą

czy

: ustanowienie stałego poł

ą

czenia

fizycznego na wył

ą

czno

ść

na czas trwania komunikacji

(analogia: analogowa ł

ą

czno

ść

telefoniczna)

– Komutowanie komunikatów

: dynamiczne ustanowienie ł

ą

cza

na czas przesyłania jednego komunikatu; komunikat zawiera
dane nadawcy i odbiorcy; to samo ł

ą

cze mo

ż

e słu

ż

y

ć

do

przesyłania komunikatów od ró

ż

nych nadawców

(analogia: dostarczanie poczty)

– Komutowanie pakietów

: pakiety składaj

ą

ce si

ę

na komunikat

zawieraj

ą

dane nadawcy i odbiorcy, s

ą

osobno wysyłane do

miejsca przeznaczenia, gdzie z powrotem s

ą

składane

w komunikat

Strategie rozstrzygania konflikt

Strategie rozstrzygania konflikt

ó

ó

w

w

Sie

ć

jako medium

do

przesyłania komunikatów
- zasób ograniczony

Kraw

ę

d

ź

(ł

ą

cze) –

potencjalne w

ą

skie

gardło

, je

ś

li nale

ż

y do

wielu tras przesyłania
komunikatów

1

2

3

4

5

Przykład

Łącze

4-5

stanowi element tras:

1-3-5-2, 2-4-5, 3-5-4, i in.

Strategie rozstrzygania konflikt

Strategie rozstrzygania konflikt

ó

ó

w (2)

w (2)

CSMA/CD

– wielodost

ę

p z badaniem stanu ł

ą

cza

i wykrywaniem kolizji

Przekazywanie

ż

etonu

– odebranie przez w

ę

zeł

kr

ążą

cego w sieci (o strukturze pier

ś

cienia)

specjalnego komunikatu (ang. token) uprawnia ten
w

ę

zeł do zast

ą

pienia

ż

etonu przez swoje komunikaty,

a nast

ę

pnie odtworzenie

ż

etonu

Pojemniki na komunikaty

– w sieci (o strukturze

pier

ś

cienia) kr

ążą

pojemniki puste lub zaj

ę

te przez

komunikaty stałej długo

ś

ci wyposa

ż

one w adres

nadawcy i odbiorcy; wskazany odbiorca pobiera
adresowany do niego komunikat i opró

ż

nia pojemnik

Systemy operacyjne system

Systemy operacyjne system

ó

ó

w rozproszonych

w rozproszonych

Sieciowy system operacyjny

– Instalowany na ka

ż

dym pojedynczym komputerze

– Jawnie wskazywany przez u

ż

ytkownika (system lokalny lub

zdalny)

– Udost

ę

pniaj

ą

cy pliki i inne zasoby w sposób jawny

– Mała tolerancja bł

ę

dów

Systemy operacyjne system

Systemy operacyjne system

ó

ó

w rozproszonych (2)

w rozproszonych (2)

Rozproszony system operacyjny

– Słabe wzajemne powi

ą

zanie składników sprz

ę

tu

– Silne wzajemne powi

ą

zanie oprogramowania

– Jeden system operacyjny (jeden egzemplarz, nie typ)

– Liczba komputerów, ich poło

ż

enie i lokalizacja zasobów nie

musz

ą

by

ć

znane u

ż

ytkownikom

– Jednolity dost

ę

p do zasobów lokalnych i zdalnych

– Jawna lub niejawna migracja danych, oblicze

ń

i procesów

pomi

ę

dzy komputerami

– Mała autonomia poszczególnych komputerów

– Du

ż

a odporno

ść

na bł

ę

dy

Przykłady: Amoeba, Mach, Chorus, DCE

Obliczenia w systemach rozproszonych

Obliczenia w systemach rozproszonych

Pocz

ą

tek prac

– lata 1980

(

ś

rodowiska PVM, P4, PICL;

standard przesyłania komunikatów LAM)

Ś

rodowisko PVM

(ang. Parallel Virtual Machine)

– projekt wewn

ę

trzny Oak Ridge National Laboratory (1989)

do programowania równoległego w sieci niejednorodnych
komputerów,

– University of Tennessee (1991)
– Trzecia wersja (1993)
– implementacje dla ró

ż

nych platform (m.in. Unix, MS Windows,

Mac)

– obecny rozwój mało intensywny

Obliczenia w systemach rozproszonych. MPI

Obliczenia w systemach rozproszonych. MPI

Ś

rodowisko MPI

(ang. Message Passing Interface) –

formalna specyfikacja interfejsu programowego

– Wersje MPI-1 (1994) i MPI-2 (1998)
– MPI-2 - nadzbiór MPI-1 (zgodno

ść

w gór

ę

);

– najpopularniejsze wydania: MPI-1.2 i MPI-2.1
– Pierwsza zaawansowana implementacja MPI-2 – 2002 r.
– Przeznaczone dla j

ę

zyków C/C++, Fortran, Java, i in.

– Dost

ę

pne dla komputerów równoległych i heterogenicznych

sieci maszyn o ró

ż

nych platformach systemowych

– Mechanizmy komunikacji: punkt-punkt i grupowa
– Komunikacja nie obci

ąż

a procesora operacjami kopiowania

pami

ę

ci

– Uwa

ż

ane za standard dla zastosowa

ń

praktycznych

Obliczenia w systemach rozproszonych. MPI (2)

Obliczenia w systemach rozproszonych. MPI (2)

MPI

– specyfikacja biblioteki funkcji do wymiany

komunikatów dla programowania równoległego

– MPI-1 nie obsługuje pami

ę

ci współdzielonej

– MPI-2 obsługuje rozproszon

ą

pami

ęć

współdzielon

ą

Program w MPI

– Zbiór niezale

ż

nych procesów korzystaj

ą

cych z ró

ż

nych

danych (model MIMD)

– Mo

ż

liwe wykorzystanie pami

ę

ci współdzielonej

– Sposób programowania - architektura NUMA
– Procesy - własne przestrzenie adresowe
– Procesy jedno- lub wielow

ą

tkowe

– Interfejs programistyczny – implementacja ukryta przed

programist

ą

Obliczenia w systemach rozproszonych. MPI (3)

Obliczenia w systemach rozproszonych. MPI (3)

Zalety MPI

– Wysoka efektywno

ść

w systemach wieloprocesorowych

– Bogata biblioteka funkcji (MPI-2: ponad 500 funkcji dla ANSI

C/C++ i ANSI Fortranu 90)

– Dobra dokumentacja

– Status public domain

– de facto standard

Wady MPI

– Statyczna konfiguracja jednostek przetwarzaj

ą

cych

– Statyczna struktura procesów w czasie wykonania programu

(nie dotyczy implementacji MPI-2)

– Brak wielow

ą

tkowo

ś

ci

Obliczenia w systemach rozproszonych. MPI (4)

Obliczenia w systemach rozproszonych. MPI (4)

Implementacje

:

– MPICH, MPICH2 – Argonne National Laboratory

– LAM MPI

– OpenMPI

- wg MPI-2