Sistemi Distribuiti - Home: Dipartimento di Scienze ...sd/pdf/SD2.pdf · 2 S. Balsamo - 2008-...

1

Sistemi Distribuiti

Esempi di applicazioni • comunicazione di dati

fra terminali di un sistema di elaborazione - fra sistemi di elaborazionesistemi distribuiti o centralizzaties. packed-switched networks (Arpanet, Datapac, Transpac, Telnet)comunicazione con vincoli (magazzini, carte di credito)

• condivisione di risorsees.: office automationidentificazione - protezione - gestione della intercomunicazione

• controllo di processimicroprocessori per controllo e monitor

• basi di dati distribuitepartizionamento o replicazione - località - integritàcontrollo degli accessi -affidabilità - sicurezza

SD2.2S. Balsamo - 2008 - Università Ca’ Foscari di Venezia

Organizzazione hw

Obbiettivo di progetto: migliorare le prestazioni del sistema mantenendocontenuti i costi

Sistema centralizzato: aumentare la velocità (ciclo) della CPU- limite fisico: velocità della luce- segnale elettrico può percorrere 30 cm/ns nel vuoto 20 cm/ns su rame => dato il ciclo di CPU se un elaboratore esegue 1 istruzione in 1 ns, la massima distanza che un segnale può coprire da CPU

a memoria è 20cm

Sistema distribuito: diverso modello di esecuzionediversi modelli


Sistemi distribuiti - architetture

varie classificazioni classificazione di Flynn (1972)

Flusso di istruzioni singolo multiplo

Flusso dei dati

singolo SISD MISD

SIMD array processor stesso calcolo su molti dati

MIMD sistemi distribuiti

multiplo SIMD MIMD


SISD

Modello von Neuman- singolo flusso di istruzioni (programma) eseguito da una CPU

e con una memoria contenente i dati- FETCH, DECODE, EXECUTE ogni singola istruzione nella sequenza

Strategie di accelerazione del ciclo - parallelismo (limitato) : uso di molte ALU specializzate che eseguono

ogni singola operazione ad alta velocità (es. +, x,…)- pipelining : DECODE di istruzione y contemporaneo a FETCH di

istruzione y+1, EXEC di y…- uso di gerarchie di memoria (livelli di cache)- uso di hw specializzato


SIMD

Array processor- matrice di elementi processore/memoria- singola unità di controllo che esegue il broadcast di una singola istruzione a tutti i processori- ogni processore esegue l’istruzione sui dati disponibili in memoria locale (esegue operazioni su matrici)

Esecuzione in parallelo su un insieme di dati

Architettura vettorialeanziché una singola ALU che opera su una singola variabile per ogni input, si ha un vettore di ALU che opera su un vettore di valori di input eproduce un vettore di output (esegue operazioni su vettori)

NOTA: in entrambi i casi utilizza un singolo PC (program counter)


MIMD

Nota- in alcune configurazioni le CPU possono condividere dati collocati in memoria comune accessibile via bus di sistema (multiprocessor)- gli accessi concorrenti alla memoria comune possono creare conflitti nell’accesso al bus => uso di memoria locale privata (cache) per ogni CPU, contenente codice e dati da non condividere, minimizzando gli accessi alla memoria comune

CPU distinte eseguono differenti programmi (multiple instruction stream) suflussi di dati distinti (multiple data stream)

CPU dotate di proprio Program Counter, memoria, dati, programmi,…cooperano per svolgere e fornire un servizio comune=> macchina MIMD = sistema distribuito

Esempio: sistema di prenotazione aerea: richieste multiple di prenotazione(multiple data stream) che possono essere servite concorrentemente(multiple instruction stream) da un insieme di CPU che condividonola pianta dell’aereo e ne tengono aggiornato lo stato.

2


Sistemi distribuiti - architetture

Multiprocessore memoria condivisa

accoppiamento strettoritardo di trasmissione brevevelocità di trasmissione alta

Multicalcolatore memoria locale privata

accoppiamento lascomaggiore ritardo di trasmissioneminore velocità di trasmissione

insieme di U.E. interconnesse da unarete di interconnessione

U.E. elaborazione, memorizzazione

Rete di comunicazione �

Architettura: a bus -a commutazioneSD2.8S. Balsamo - 2008 - Università Ca’ Foscari di Venezia

Multiprocessori a bus

Bus dati, indirizzo, controllo32 o 64 linee indirizzi, 32 o 64 linee dati, almeno 32 linee controllo parallele

banda 300 Mbpslimite tipico per le prestazioni:4/5 CPU

Lettura da memoria:CPU scrive l’indirizzo di parola richiesta sul bus indirizziconferma il comando di lettura via CNTRLmemoria scrive il dato su linee dati

BUS

CPU CPU MEMORIA…


Multiprocessori a bus: coerenza della memoria

Condivisione della memoriaProblema: coerenza

al tempo t la CPU A scrive il valore ‘x’ all’indirizzo di memoria yal tempo t’>t la CPU B legge il valore ‘x’ dall’indirizzo di memoria y

Coerenza costosa da implementare => sovraccarico del bus

Soluzione basata sulla memoria cachemantenere parole accedute più recentemente

hit rate: probabilità di successo, se la parola cercata è nella m. cache (es.:90%)

BUS

CPU

Cache

CPU

Cache

MEMORIA…


Multiprocessori a bus

coerenza: possibile soluzione scrittura attraverso la cache, ogni scrittura nella m.c. èriportara in memoria (write-through cache)tutte le CPU controllano eventuali scritture e nel caso eliminano o aggiornano laparola (snoopy cache)

meccanismo trasparente all'utente - limite tipico per le prestazioni:32/64 CPU

BUS

CPU

Cache

CPU

Cache

MEMORIA…


Multiprocessori a commutazione

Memoria multimodulareConnessione a crossbarCrosspoint interruttore (switch)

Svantaggio:coston memorie ed n CPU richiedono n2 switches (es. n=64, 4096 switch)

Altre architetture

CPU

MEMORIA

commutatore di crosspoint


Multiprocessori a commutazione: Omega network

n memorie ed n CPU richiedono (n/2 log n) switches

CPU MEMORIA

Vantaggio: accesso diretto di ogni CPU ad ogni moduloSvantaggio: maggior ritardo di comunicazione: log n stati di switching

ogni stadio ha n/2 switchEsempio: n=1024, 10 stadi di switch per trasmettere da CPU a memoria e 10 stadi perla trasmissione inversa; se la CPU è una RISC con tempo di esecuzione di 10 ns i 20 switchdevono essere attraversati da meno di 10 ns=> ogni switch 10ns/2=0.5 ns= 500 picosec=> occorrono 1024x10=5120 CS da 500 picosec =>costo elevato

3



Esempio: n=8, 3=log 8 livelli di switch per trasmettere da CPU a memoria

CPU Memoria



Esempio: n=16, 4 livelli di switch per trasmettere da CPU a memoria

CPU Memoria


Multiprocessori a commutazione: NUMA

NUMA Not Uniform Memory Access

Ogni CPU ha una memoria locale:- accesso veloce alla memoria locale- più efficienti- problemi di allocazione ottima di dati e programmi

Multiprocessor

Snoopy cache Limitati dalla capacità del bus (max 64 CPU)Crossbar switch CostosoOmega Network CostosoNUMA Complessità degli algoritmi di allocazione di+

programmi e dati


Multicalcolatore a bus

Senza memoria condivisaTraffico limitato

EspandibilitàProtocolli di rete

Rete

CPU CPU…

Workstation Workstation

ML Memoria locale

ML ML

File Server

Printer


Multicalcolatore a commutazione

Es. Ipercubo:cubo ad n dimensioniOgni U.E. è un vertice, gli spigoli sono connessioniOgni U.E. ha n connessioniCrescita logaritmica delle connessioni

Diverse topologieEs. Griglia (struttura bidimensionale)

Trasmissione anche in più passiLimite logaritmico al numero di passi con √n



Es. Ipercubo:cubo ad 4 dimensioniOgni CPU ha 4 link

Ipercubo commerciale

4



Es. Ipercubo:cubo ad 6dimensioni

Ogni CPU ha 6 link


Multiprocessori e multicalcolatori a commutazione: altre soluzioni

Sistemi a parallelismo massicciosupercomputer con migliaia di CPUbassa latenza e alta bandabuona affidabilità

Sistemi a cluster di workstations (COW)U.E. connesse con componenti disponibili (‘off the shelf’)nessun accorgimento specifico per ottimizzare prestazioni e affidabilità


Sistemi distribuiti - Architetture software

Sistemi Operativi (OS)OS per un sistema uniprocessoreOS per un sistema multiprocessore: MOSOS per un sistema distribuito: DOSOS per la gestione della rete in un sistema distribuito: NOS

SO per un sistema di elaborazione uniprocessoregestione delle risorsecondivisione delle risorseinsieme di utenti (processi)

sistema con memoria condivisa globalesingola coda di processi pronti ed eseguibilipossibile attesa attivastato o modo di operazione nucleo vs utentemodello di macchina virtuale

modelli di OS microkernel monolitico



modelli di OS microkernel



Accoppiamento lasco (loosely-coupled DOS)macchine, utenti, programmi indipendenti fra lorocondividono uso di risorse costoseogni U.E. è identificabile ed è in grado di operare indipendentemente daglialtri (e.g, un guasto di rete non blocca l’operatività della singola U.E.)

Accoppiamento stretto (tightly-coupled DOS)macchine indipendenti coordinate da un controllore

ClassificazioneAccoppiamento lasco: S.O. di rete, interazione lascaAccoppiamento stretto: S.O. per multiprocessori e multicalcolatori



Es. SO distribuito:sw ad accoppiamento stretto su hw ad accoppiamento lascos.d. senza memoria condivisagli utenti vedono il sistema come un solo ambiente (uniprocessore virtuale)meccanismi globali per comunicazione - protezione - file system - …gestione di memoria locale

ClassificazioniAccoppiamento stretto/lascoMulticalcolatore/multiprocessoreA bus/a commutazione

Multicalcolatore sw ad accoppiamento lascoMulticalcolatore sw ad accoppiamento stretto (es su LAN con DOS)Multiprocessore sw ad accoppiamento stretto (es MPC con OS)

Es. SO a multiprocessori:sw ad accoppiamento stretto su hw ad accoppiamento strettosistema con memoria condivisa globalesingola coda di processi pronti ed eseguibilipossibile attesa attiva

5



Es. SO di rete su multicalcolatori:sw ad accoppiamento lasco su hw ad accoppiamento lascosistema operativo di rete (NOS - Network Operating System)rete di UE ognuna dotata di memoria, CPU, OS, periferichetutti i comandi sono eseguiti localmentel’esecuzione di comandi in remoto richiede la visibilità all’utente della

locazione di risorse

Esempio: rlogin ihohUE usata come terminale remoto di ihohi comandi inviati dalla UE sono eseguiti sulla macchina remotaad ogni istante una sola macchina è in esecuzionela selezione delle macchine è manuale => l’utente deve conoscere

l’esistenza e disponibilità delle macchineEsempio: rcp ihoh:file1 squit:file2

copia file1 da ihoh a squitl’utente deve sapere che file1 è nel FS di ihoh e che squit ha un FS

in cui deposita file1 con nome file2SD2.26S. Balsamo - 2008 - Università Ca’ Foscari di Venezia

NOS - sw ad accoppiamento lasco su hw ad accoppiamento lasco



Due clienti e un servente in un NOS

Esempio da A. Tanenbaum ‘Sistemi Distriibuiti”



Diversi clienti possono montare i serventi in diverse parti

Esempio da A. Tanenbaum ‘Sistemi Distriibuiti”SD2.29S. Balsamo - 2008 - Università Ca’ Foscari di Venezia


NOS V0 forme primitive di comunicazione e condivisione risorse

NOS V1 - evoluzione di NOS V

- include File Server(s) condiviso(i) che gestisce(cono) file system globale- FS accetta le richieste da ogni programma sulla UE (read, write, open,

close)- ogni richiesta è esaminata e servita e il risultato trasmesso al chiamante- FS mantiene un file system gerarchico- UE può montare arbitrariamente parte del file system globale nel proprio

fs locale- diverse viste di utenti possibili- stesso programma eseguito su diverse UE può lavorare su gerarchie diverse

- la comunicazione fra processi applicativi può avvenire tramite file condivisi



- implementazione di programmi distribuiti richiede attenzione a manipolazione eduso di nomi di risore

Es: FS mantiene file systems con path /public/work/file1UE monta o importa file1 in /home/work/file1il programma applicativo eseguito su UE contiene il nome esplicito…fd=open(“/home/work/file1”,R);…non portabile, ovvere eseguibile solo su quella UE e non sul File Server

NOS V1 gestisce comunicazioni fra UE e FS- le UE possono eseguire sotto diversi OS- NOS V1 deve garantire concordanza almeno

del FORMATO dei messaggi scambiatidelle REGOLE secondo cui devono essere scambiati (standard dei

PROTOCOLLI)- NON effettua coordinamento di attività ed esecuzione di programmi- NON maschera o nasconde l’eterogeneita dei SO

6


DOS - sw ad accoppiamento stretto su hw ad accoppiamento lasco

DOS - Distributed Operating Systemimplementa l’astrazione di un singolo sistema time-sharing (single system image, virtualprocessor) su un insieme di macchine anche eterogenee interconnesse e operanti sotto lostesso sistema operativo

Trasparenza: gli utenti (programmi) non hanno visibilità della distribuzione delle risorse

- IPC comunesupporta le interazioni fra ogni coppia di processi

- protezione globalecombinazione di schemi (es. lista di controllo, capabilities, bit di protezione)maggiore complessità

- gestione di processiidentica su ogni macchina (es. set di primitive, create, destroy, start, suspend,…)

- file systemvista identica da ogni macchina

- interfaccia di sistemaidentica su ogni macchina (stesso nucleo, più semplice coordinamentoes.: start, i nuclei cooperano per decidere dove eseguire un processo)



Ogni nucleo ha controllo sulle risorse locali

- non vi è memoria condvisa, ogni UE gestisce la memoria locale

- eventuale uso di paging e/o swapping localmente

- se vi è multiprogrammazione ogni nucleo gestisce lo scheduling locale

=> se la gestione fosse globale occorrerebbe la nozione di stato globale delsistema distribuito, solitamente non realizzabile

Sistemi multicalcolatori omogenei vs sistemi eterogeneiSistemi omogenei: DOSSistemi eterogenei: Middleware


Middleware


Middleware

In un sistema distribuito aperto basato sul middleware i protocolli usati inogni strato middleware dovrebbero essere gli stessi middleware, come leinterfacce offerte alle applicazioni

Interfaccia

Protocollocomune

ApplicazioneApplicazione




MOS - sw ad accoppiamento stretto su hw ad accoppiamento stetto

Multiprocessor Operating System - MOS- special purpose: macchina data base- general purpose: time sharing OS (es. UNIX) su multiprocessore

Caratteristica: coda di esecuzione UNICA (globale)struttura dati mantenuta da MOS in memoria condivsa e contenente processi in stato di ‘ready’

BUS

CPU X

Processo B

cache

CPU Y

Processo A

cache

Processo C

CPU Z

cache

...

E readyD ready

C running B running A running

RUN Q: D,EMOS

Memoria

7



SchedulingEsempio:

- il processo B in CPU Y blocca- CPU Y lo sospende e cerca un nuovo processo in RUN Q- CPU Y esegue MOS allocato in memoria condivisa

- salva lo stato di B- entra nella regione critica per eseguire lo scheduler

- evita a diverse CPU di prelevare lo stesso processo- controlla la mutua esclusione della coda

- ottenuto l’accesso esclusivo a RUN Q, la CPU Y- rimuove il processo D da RUN Q- esce dalla regione critica- esegue D

Nota- nella cache inizialmente ci sono dati e istruzioni di B, per cui D è inizialmente penalizzato- allocazione dei processi: le CPU non hanno ML per cui non ha importanza chi lo esegue,ma il tempo di esecuzione è influenzato dalla presenza dei dati e programmi in cache=> conviene allocare il processo alla CPU libera che più recentemente lo ha eseguito



File System MOStradizionale con caching di blocco- accesso al File System causa MOS trap- MOS entra nella regione critica (con semafori, monitor,…)- esegue la system call escludendo le altre CPU dall’accesso ai dati

condivisiEs: write (fd,&buff,nbytes)

- lock di blocco nel file identificato da fd- scrive nbytes da buff in blocco ‘locked’- rilascia il lock

Organizzazione di MOS con CPU dedicata ad eseguire MOS e altre riservate adapplicativi

svantaggio: MOS diventa collo di bottiglia


Confronto

Organizzazione sw per n macchine

Categoria NOS DOS - Middleware MOS

Trasparenza NO SÌ - SÌ (alta) SÌ

Stesso OS NO SÌ - NO SÌCopie di OS n n 1

Comunicazione file condivisi messaggi- dip. mod. memoria condivisaProtocolli dicomunicazione SÌ SÌ - dip. modello NOcomuni

RUN Q singola NO NO SÌ Condivisione difile con non necessariamente SÌ SÌ semantica comune Scalabilità SÌ Moderata - dip. mod. NOOpeness aperto chiuso - aperto chiuso


Sistemi distribuiti - Progetto 1/2

flessibilità* kernel monolitico s.o. centralizzato + opzioni di rete e servizi remoti* microkernel comunicazione fra processi - gestione memoria

gestione processi e schedulazione a basso livelloI/O a basso livellopiù flessibile

trasparenzaimmagine di un singolo sistema, time-sharing uniprocessore* della localizzazione delle risorse: dove sono?* alla migrazione delle risorse: cambiamenti di localizzazione* alla replicazione dei file: quante copie?* alla concorrenza fra utenti: accesso a risorse condivise* al parallelismo: attività eseguibili in parallelo


Sistemi distribuiti - Progetto 2/2

prestazionimetriche: tempo di risposta, throughput, utilizzo, banda,…caratterizzazione del caricocolli bottigliaload balancingdefinizione della grana (fine o grossa) di parallelismo

affidabilitàdisponibilità (Availability): fraz. di tempo in cui il sistema è utilizzabile, funzionanteridondanza: tecnica per aumentare Aconsistenza fra copie multiplesicurezzatolleranza ai guasti (fault tolerance)

scalabilitàgrande dimensionievitare componenti, dati e algoritmi centralizzati

Sistemi Distribuiti - Home: Dipartimento di Scienze ...sd/pdf/SD2.pdf · 2 S. Balsamo - 2008-...

Documents

Transcript of Sistemi Distribuiti - Home: Dipartimento di Scienze ...sd/pdf/SD2.pdf · 2 S. Balsamo - 2008-...