Sistemi Distribuiti Corso di Laurea Magistrale in Informatica Indirizzo Reti Facoltà di Scienze...
-
Upload
bonaventura-bondi -
Category
Documents
-
view
213 -
download
0
Transcript of Sistemi Distribuiti Corso di Laurea Magistrale in Informatica Indirizzo Reti Facoltà di Scienze...
1
Sistemi Distribuiti
Corso di Laurea Magistrale in InformaticaIndirizzo RetiFacoltà di Scienze Matematiche Fisiche e Natuali
Docente: Prof. Alberto Negro
2
Obiettivi Formativi1. In questo corso tratteremo alcuni dei concetti
fondamentali alla base dei moderni sistemi distribuiti. 2. Ci occuperemo dei fondamenti: problemi, protocolli,
algoritmi e limiti insormontabili. 3. Vedremo, anche nei dettagli, le idee usate nella
costruzione dei sistemi Peer-to-Peer (P2P). 4. Infine descriveremo una piattaforma per applicazioni P2P:
JXTA.
3 e 4 sono mutuati dal corso di Sistemi P2P (3CFU).
3
4
Contenuti
•Parte A) Sistemi distribuiti: Fondamenti.▫Introduzione ai Sistemi Distribuiti
5
Contenuti
•Parte B) Sistemi P2P▫ Introduzione alle Architetture Parallele L’Ipercubo,
la Butterfly (CCC e Benes), i grafi di de Bruijn.▫ Introduzione ai sistemi P2P▫ Reti P2P non strutturate: Random Graphs, Small-
Worlds and Scale-Free Networks▫ Reti P2P strutturate▫ Reti Uniformi e Reti Randomizzate▫ Strategie di Routing ▫ Reti non Uniformi: Koorde
6
Contenuti
•Parte C) JXTA▫Introduzione a JXTA▫Architettura di JXTA▫Le componenti e i protocolli di JXTA▫Comunicazione in JXTA: Pipe, BidiPipe e Socket▫Esempi di utilizzo e Applicazioni
7
Testi1. R.Steinmetz, K. Wehrle, Peer to Peer
Systems and Applications, LNCS. 3485, Springer Verlag, 2005
2. F. Thompson Leighton, Introduction to Parallel Algorithms and Architectures: Array Trees Hypercubes.
3. Ajay D. Kshemkalyani and Mukesh Singhal. Distributed Computing: Principles, Algorithms, and Systems, Cambridge University Press, 2008. ISBN-13 978-0-521-87634-6.
4. JXTA Programmers guide.
8
Modalità di Esame
•Scritto + Orale (progetto JXTA facoltativo)
9
Introduzione ai Sistemi Distribuiti
Gennaro CordascoDipartimento di Informatica - Università degli Studi di Salerno
cordasco[@]dia.unisa.it cordasco+sd[@]gmail.comhttp://www.dia.unisa.it/~cordascoLaboratorio ISISLAB2
10
Sistema Distribuito
•Una collezione di dispositivi autonomi che comunicano attraverso una rete di interconnessione
11
Caratteristiche dei SD
•I dispositivi non hanno un clock comune•Non c’è una shared memory•I dispositivi lavorano in maniera
autonoma e sono tipicamente eterogenei•… sono separati geograficamente
I Sistemi distribuiti (SD) sono:
Incredibilmente flessibili
Incredibilmente efficienti
Difficili da mettere a punto…...
Hardware eterogeneo
AsincroniaConoscenza locale limitata
Fallimenti
12
13
Gli Algoritmi Distribuiti:
Sono difficili da progettare:Non c’è un modello accettato
Message passing vs shared memory
TimingFailure
E’ difficile dimostrarne la correttezza
Algoritmo Distribuito:
- Algoritmo per un Sistema Distribuito
14
Gli Algoritmi Distribuiti:
Usano il numero totale dei messaggi spediti comemisura di complessità
Usano anche il tempo come misura di complessità
15
• L’alternativa è un’architettura centralizzata– un singolo mainframe con terminali
stupidi• Alcuni problemi:
– se il mainframe non è disponibile, nessuna computazione è possibile– consumo di banda sulla rete per dati
(anche per i dati locali ai terminali)– costo e mantenimento alto del mainframe– terminali stupidi con capacità di calcolo
notevoli
Perchè computazione distribuita?
16
Motivazioni per il Calcolo Distribuito
• Utilizzo parallelo di risorse distribuite– CPU– Memoria
• Data Set difficilmente rilocabili vengono processati localmente• Fault-tolerance• Scalabilità• Modularità• Rapporto Prestazioni/Prezzo
– attenzione alla manutenzione
17
Le prestazioni di un Sistema Distribuito
• La capacità di un sistema distribuito può facilmente eccedere quella di un calcolatore a singolo processore:
• 5000 Pentium a 200 MIPS=1.000.000 MIPS• Una singola CPU così veloce dovrebbe
eseguire una operazione ogni 10-12 secondi• In 10-12 secondi alla velocità della luce si
coprono solo 0.3 millimetri• Una CPU in 0.3 millimetri crea problemi disurriscaldamento
Modello dei SD
18
19
Differenza con i Sistemi Paralleli
• Array processors (processori strettamente accoppiati)
• Multiprocessori (con accesso diretto alla shared memory UMA)▫ Diversi tipi di interconnessione (bus, multistage
switch, come ad esempio butterfly oppure shuffle exchange network)
• Multicomputer parallel systems (processori omogenei con una propria memoria NUMA)▫ Non c’è una memoria condivisa▫ Utilizzano una specifica rete di interconnessione
(ring, mesh, ipercubo)
20
UMA vs NUMA Models
21
Butterfly and Hypercube networks
22
Tassonomia di Flynn• SISD: Single Instruction Stream Single Data Stream
▫ Modello tradizionale• SIMD: Single Instruction Stream Multiple Data Stream
▫ Applicazioni scientifiche su dati di grande dimensione▫ vector processors, systolic arrays, Pentium/SSE, DSP chips
• MISD: Multiple Instruciton Stream Single Data Stream▫ Meno usato
• MIMD: Multiple Instruction Stream Multiple Data Stream▫ Il modello più potente, ma anche il più complesso ▫ La maggior parte dei sistemi paralleli e distribuiti
23
Terminologia• Accoppiamento (Coupling): livello di
interdipendenza fra i moduli di un SD (tightly/loosely)
• Parallelismo o SpeedUp, T(1)/T(n): misura l’accelerazione ottenuta usando n moduli invece di 1.
• Concorrenza: rapporto fra il tempo speso a fare computazione ed il tempo totale speso (include tempo di comunicazione, sincronizzazione)
• Granularità di un programma
24
Message Passing vs Shared memory•Shared Memory: La comunicazione fra i
processori si basa su una zona di memoria condivisa▫Tightly coupled multiprocessor▫Problema: gestione dei conflitti di accesso
concorrente alla memoria •Message Passing: I computer comunicano
attraverso lo scambio di messaggi asincrono▫Loosely coupled systems
25
SD Obiettivi (Sistema)
•Diverse problematiche devono essere affrontate nella realizzazione di un SD:▫Comunicazione▫Gestione dei processi▫Naming▫Synchronizzazione▫Data Storage▫Consistency and Replication
26
SD Obiettivi (Sistema)▫Fault-tolerance (nodi/link)▫Security▫Scalability▫API▫Trasparenza
27
SD Obiettivi (Algoritmi)▫Modello di esecuzione
Interleaving Partial order
▫Algoritmi distribuiti su grafi dinamici Topologia del sistema Algoritmi su grafi (permettono la
comunicazione, la sincronizzazione ecc.) Topologia dinamica Efficienza
▫Timing
28
SD Obiettivi (Algoritmi)▫Sincronizzazione
Logical time Leader Election Mutual exclusion Distributed deadlock detection and resolution Distributed termination detection Distributed garbage collection
29
SD Obiettivi (Algoritmi)• Group communication, multicast, and ordered
message delivery▫ Group: processi che condividono un contesto e/o che
collaborano▫ joins, leaves, fails▫ Invio concorrente dei messaggi: gestione della semantica
dell’ordine di arrrivo• Monitoring distributed events and predicates
▫ Predicate: condition on global system state▫ Debugging
• Progettazione dei programmi distribuiti e dei tool di verifica
• Debugging di programmi distribuiti
30
SD Obiettivi (Algoritmi)• Data replication, consistency models, and
caching▫Fast, scalable access▫coordinate replica updates▫optimize replica placement
• Reliable and fault-tolerant distributed systems▫Failure detectors:
Difficult to distinguish a "slow" process/message from a failed process/ never sent message
algorithms that "suspect" a process as having failed and converge on a determination of its up/down status
31
SD Obiettivi (Algoritmi)
•Load Balancing▫Computation migration▫Data migration▫Distributed scheduling
•Come comparare gli algoritmi▫Metriche
32
SD Applicazioni•Mobile systems•Sensor networks•Ubiquitous and pervasive computing
(domotica)•Peer to Peer computing•Publish and Subscribe content distribution•Distributed agents•Distributed data mining •Grid Computing•Security