Corso diReti di Calcolatori M

Università degli Studi di BolognaFacoltà di Ingegneria

Modelli 1

Antonio Corradi

Anno accademico 2010/2011

MODELLI VARI

ASTRAZIONE …ASTRAZIONE …

Modelli 2

SISTEMI DISTRIBUITISISTEMI DISTRIBUITIAmbito non completamente risolto … o meglio Area molto utilizzata e da affrontare continuamenteMa con molte sfide da superare e problemi da risolvere. Ad esempio:• Scalabilità

Modelli 3

• Scalabilità• Predicibilità• Facilità di supporto a concorrenza e parallelismo• Latenza limitata• Superamento di failure parziali• Eterogeneità (a diversi livelli)…

• MODELLI approfonditi per l’ESECUZIONE– Modelli architetturali di supporto e fornitura serv izio

(o di provisioning)– PRAM– Efficienza e Speed -up

MODELLI e INTERPRETAZIONEMODELLI e INTERPRETAZIONE

Modelli 4

– Efficienza e Speed -up– Qualità del Servizio ossia QoS

• Esperienze di interpretazione dei modelli– Sono facili da maneggiare– Presentano la realtà (e la modellano ☺)– Aiutano nello sviluppo di progetti– I modelli sono sempre significativi e applicabili?

Spesso, pattern, modi, strategie locali sono utilimodelli e paradigmi statici/dinamicimodelli e strategie preventivi /reattivimodello di esecuzione nel sistema

monoutente/multiutente

ALCUNI MODELLI di BASEALCUNI MODELLI di BASE

Modelli 5

monoutente/multiutenteprocessore/processori

modello per esecuzione attivaprocessi/oggetti replicazione

modello delle entità per la allocazioneprocessi/oggetti decisioni statiche/dinamiche

Nei sistemi distribuiti siamo interessati allaesecuzione e operativitàCi aspettiamo che ci sia sviluppo prima della esecuzione

Ad esempio, ci sono classi sviluppate separatamente chefavoriscono ulteriori sviluppi statici, ma che poi sono daconsiderarsi un’unico contributo durante la esecuzioneAllora queste non ci interessano

ALLA BASE DEL CORSOALLA BASE DEL CORSO

Modelli 6

Allora queste non ci interessanoCi interessa tutto quello che ha impatto durante laesecuzione e che rimane significativo e vitale durantequesta, favorendo e abilitando la distribuzione (e facendocicapire in che modo )

Ad esempio, ci sono classi che poi diventeranno processi ecomponenti attivi e distribuiti per tutta la durata dellaapplicazione: sono i processi che ci interessano e cherappresentano una parte della architettura del sistema run-timeLa architettura dinamica ci interessa, e ci interessacapire come e quanto bene funziona

Nei sistemi distribuiti siamo interessati allaperformance e qualitàCi aspettiamo che ci siano risorse implicate e casiparticolarmente significativi per una architettura considerata

Ad esempio, l’uso di RMI ha un impatto molto forte sul costo esulla scalabilità del sistema complessivoMentre l’uso di socket e strumenti di più basso livello

ANCORA DI BASE …ANCORA DI BASE …

Modelli 7

Mentre l’uso di socket e strumenti di più basso livellogarantisce minore overhead e migliori caratteristiche

Durante la esecuzione ci interessano i colli di bottiglia , ossia ipunti critici e le parti che possono determinare uncomportamento del sistema poco adatto o carente

Ad esempio, usare uno strumento come una RMI (o unarichiesta remota costosa) per un messaggio scambiato in modooccasionale una tantum (e magari solo una volta) tende aintrodurre un potenziale bottleneck da considerare e dacontrollare in un progetto

La architettura va verificata a priori e a posteriori

Nei sistemi distribuiti siamo interessati a operatività ,performance , reale esecuzione distribuitaUso di modelli preventivi/reattiviComportamenti preventivi prevengono eventi o situazioni conun costo fisso sul sistema (spesso calcolabile)Comportamenti reattivi permettono di introdurre minore logica

MODELLI di ESECUZIONE …MODELLI di ESECUZIONE …

Modelli 8

Comportamenti reattivi permettono di introdurre minore logica(e limitare il costo ) in caso gli eventi non si verifichino

Uso di modelli statici/dinamiciComportamenti statici non permettono di adeguare il sistemaa fronte di variazioni (limitate)Comportamenti dinamici permettono di fare evolvere ilsistema a fronte di variazioni (limitate) ma tendono a causarecosti più elevati

Modelli statici / Modelli dinamiciIl numero degli utenti di una applicazione è predefinitoGli utenti si possono aggiungere/togliereIl numero dei processi di una applicazione è predefinitoIl numero dei processi può cambiare durante l’esecuzione

MODELLI STATICIMODELLI STATICI

Modelli 9

Il numero dei processi può cambiare durante l’esecuzioneIl numero dei nodi massimo è predefinitoI processori partecipanti possono anche aumentare moltoIl numero dei clienti di un servizio è predefinitoIl numero dei servizi (throughput) non predefinitoI servitori sono noti e predefinitiI servizi (servitori) devono cambiare in numero e tipoServitori intermedi catalogano e attivano servitori

Esecuzione di una o più applicazioniMonoutente: l'uso di un sistema in modo dedicato ètipico delle fasi prototipale

Multiutente : più utenti consentono di formare unmigliore mix di entità eseguibili sul/sui sistemi

MODELLO di ESECUZIONEMODELLO di ESECUZIONE

Modelli 10

migliore mix di entità eseguibili sul/sui sistemi

modello workstationsi utilizzano preferenzialmente le risorse locali

modello processor poolsi utilizzano le risorse in modo trasparente a secondo delloro utilizzo e disponibilità

Risorse durante la esecuzioneProcessi entità attive capaci di esecuzione di- azioni locali su un ambiente proprio e - azioni di comunicazione con altri processi attraverso

memoria condivisa e scambio di messaggiUso di dati esterni ai processi stessi (scarso confinamento)

MODELLI a MODELLI a RISORSERISORSE

Modelli 11

Uso di dati esterni ai processi stessi (scarso confinamento)

Oggetti entità introdotte per la astrazione, come capacità di- racchiudere e nascondere risorse interne (astrazione dei dati)

con visibilità esterna delle operazioni- agire su risorse interne alla richiesta di operazioni dall'esterno

Oggetti passivi astrazioni di dato su cui eseguono entità esterneOggetti attivi entità attive capaci di esecuzione e scheduling

Oggetti passiviI modelli ad oggetti PASSIVI prevedono che i processi (esterni agli oggetti stessi) possano entrare sugli oggetti e richiedere la esecuzione dei metodi- modello a scarso confinamento- scarsa protezione- interferenza tra diversi processi

Oggetti attivi

ESECUZIONE e OGGETTIESECUZIONE e OGGETTI

STATO STATO

Modelli 12

Oggetti attiviI modelli ad oggetti ATTIVI chiudono di più dal punto di vista dellaesecuzione: i processi esterni non possono entrare ma solo presentarerichieste. Chi esegue sono solo processi interni all’oggetto attivo- oggetti protetti- completa determinazione

STATO STATO

richiesta esplicita e risposta

Oggetti attiviGli Oggetti Attivi decidonoindipendentemente il comporta-mento interno e lo nascondonoconfinandolo

OGGETTI ATTIVIOGGETTI ATTIVI

CODA DELLE

ATTIVITA'

CODA DELLE

RICHIESTE

SCHEDULER

RICHIESTE DAALTRI OGGETTI

Parte Parallela

ATTIVITA'

Stato di Scheduling

GESTORE

Modelli 13

Ogni oggetto attivo racchiude alproprio interno la necessariacapacità di concorrenza e definiscela propria gestione locale dellaconcorrenza, prevenendo eventualiinterferenzeQuanti processi interni?

Parte non Parallela

v0v1v2v3

ATTIVITA'

m3m2m1m0

METODI

STATO

m4

Oggetto

GESTORE

RICHIESTE DAALTRI OGGETTI

Parte non Parallela

v0v1v2v3

m3m2m1m0

METODI

STATO

m4

Il supporto aggiunge in modo automatico tutte le funzioni di autodeterminazione- La coda delle richieste esterne- La coda delle attività interne- La realizzazione della politica

di scheduling

OGGETTI ATTIVIOGGETTI ATTIVI

CODA DELLE

ATTIVITA'

CODA DELLE

RICHIESTE

SCHEDULER

RICHIESTE DAALTRI OGGETTI

Parte Parallela

ATTIVITA'

Stato di Scheduling

GESTORE

Modelli 14

di scheduling- Le gestione della attivazione

dei processi interni- La gestione della loro

terminazione- La consegna dei risultati- La gestione degli errori

Meccanismi forniti dal supporto e Politiche lasciate all’utente

Parte non Parallela

v0v1v2v3

ATTIVITA'

m3m2m1m0

METODI

STATO

m4

Oggetto

GESTORE

OGGETTI e CLASSI OGGETTI e CLASSI -- digressionedigressioneOggetti passivi come dati e metodiI metodi sono resi visibili dalla interfaccia ed invocabili dall’esternoI dati sono tipicamente protetti e non visibili dall’esterno

I dati (attributi) sono - dati primitivi (esempio un intero di nome origine )

Modelli 15

Interfaccia

origine

vertice

StatoMetodi

metodi dati

interfaccia

- dati primitivi (esempio un intero di nome origine )- riferimenti ad altri oggetti (esempio un link tipato ad un altro oggetto)

CLASSI (digressione: non troppo)CLASSI (digressione: non troppo)

metodi

Nei sistemi con classi , sono le classi - che contengono realmente i metodi in modo unico per tutte le istanze- che specificano quali dati abbia ogni istanza e di che tipo (primitivo o meno)se i tipi non sono primitivi ma altri oggetti , la classe specifica di che classe devono essere i riferimenti

Modelli 16istanze

metodiclasse AGV

modello

posizioneportatavelocità. . . .

vaiA scaricacarica

abbassasolleva

variabili

valori valorivalorivalori

veicolo a guidaautomatica

Interfaccia

origine

vertice

StatoMetodi

Ci sono le classi a run-time?

CLASSI a RUNCLASSI a RUN--TIMETIME

metodi

Le classi sono presenti a run-time e caricate in modo dinamicoVengono caricate in un heap per ritrovare i metodi e le variabili statiche a run-time

Anche gli oggetti sono caricati in modo dinamico (heap) e fanno riferimento alla propria classe per il proprio comportamentoLe classi sono spessolegate dalla relazione di

Modelli 17

istanze

metodi

sottoclasse C

va

vb. . . .

ma mc mb

variabili

valori valorivalorivalori

. . . .

metodisuperclasse SC

v1

v2. . . .

m1 m3 m2

variabili

. . . .

legate dalla relazione di ereditarietà e si prevede che una istanza faccia riferimento a una classe e molte superclassi(si può chiamaresia m1 di SCsia ma di C)

CLASSI vs INTERFACCECLASSI vs INTERFACCENelle moderne architetture, le interfacce sono il contratto di interazione (in Java sono anche entità del programma) le classi descrivono le implementazioni specifiche (e sono uniche entità descrittive del comportamento delle istanze)Nei linguaggi OO spesso si prevede ereditarietà di entrambeEreditarietà multipla (genitori multipli) - naturale per interfacce

Modelli 18

Ereditarietà semplice (singolo genitore) - tipica per classiIn Java infatti abbiamo interfacce in grafo - e classi che possono implementarne molteplici - ma classi in catena di ereditarietà , semplificando molto il supporto per le istanze:

Un’istanza richiede il caricamento solo di una classe (di definizione) e di tutte le classi in ereditarietàOgni metodo si trova dinamicamente in modo semplice scorrendo la catena delle classi a partire dalla classe di de finizione (facilità nella produrre codice statico e nel supporto dinamico)

EREDITARIETÀ MULTIPLAEREDITARIETÀ MULTIPLANei linguaggi OO con ereditarietà multipla tra classi (C++, Vbasic, … e supporti derivati), la esplorazione dinamica è su un grafo di classi e, in questi sistemi, la ricerca del metodo da eseguire diventa più complessaAbbiamo molte classi da ricercare e in ordine prestabilito dalla ereditarietà superclassi di primo livello

Modelli 19

ValgonoOverridinge ordine inEreditarietànei sistemi concentrati

metodi

classe diattributo1. . . .

met3 met5met4

metodo2metodo1

variabili

desc.

definizione

descrizioni di variabili e di metodi

desc. desc. desc.

attributo2attributo3

attributo4

EREDITARIETÀ MULTIPLAEREDITARIETÀ MULTIPLANei linguaggi OO con ereditarietà, i metodi devono riferire gli attributi correnti della istanza (descritta dalle classi)

Ogni istanza quanti attributi e metodi ha?Il metodo metodo2 della classe corrente può riferire un attributo di una superclasse?Il metodo di una superclasse può riferire un attributo di una sottoclasse?

superclassi di primo livello

Modelli 20

Spesso uso dinotazioni per riferire metodi specificie attributi specifici

superclassi di primo livello

metodi

classe diattributo1. . . .

met3 met5met4

metodo2metodo1

variabili

desc.

definizione

descrizioni di variabili e di metodi

desc. desc. desc.

attributo2attributo3

attributo4

Ereditarietà SEMPLICE vs. MULTIPLA Ereditarietà SEMPLICE vs. MULTIPLA Nei linguaggi OO tra classi si prevede ereditarietàEreditarietà multipla (genitori multipli)Ereditarietà semplice (singolo genitore)Sia tra classi, sia tra interfacceeVantaggi? Svantaggi?

capacità espressiva,

Modelli 21

capacità espressiva, semplicità di espressionepossibilità di mapping di situazioni specificheestensibilità ad altre proprietà (AOP)semplicità di supportominore overhead

accettazione ed uso da parte degli utenti

EREDITARIETÀ MULTIPLA e DISTRIBUITOEREDITARIETÀ MULTIPLA e DISTRIBUITONei supporti con ereditarietà multipla e in architetture distribuite, molto spesso la classe (o il componente o l’interfaccia ) diventa un contenitore unico che raggruppa tutta la descrizione della entità, per ragioni di efficienza e di maggiore localitàDiventa difficile determinare in modo statico la posizione di un metodoI metodi possono

unico contenitore delle descrizioni

Modelli 22

I metodi possonoessere riferiti solotenendo conto delmappaggio per la classe specificae non in modo predefinito(un metodo ritrovatosempre attraverso la sua classe / interfaccia)

contenitore

metodi della classe corrente

desc1

descrizione compatta di entità

desc2 desc3 desc4

unicometodi della classe desc1

metodi della classe desc2

metodi della classe desc3

metodi della classe desc4

CLASSI MULTIPLE e USO dei METODICLASSI MULTIPLE e USO dei METODIAncora con ereditarietà multipla e in architetture distribuite,

In caso di compilatori , gli attributi sono risolti per la classe prima della esecuzione, e sul mapping dei nomi si potrebbe intervenire prima della esecuzione, In caso di interpreti (o di ambienti run-time) , la cosa è più complessa, per il dovere risolvere ogni entità durante la esecuzioneNon si può cambiare il codice dei metodi delle supe rclassi già

Modelli 23

Non si può cambiare il codice dei metodi delle supe rclassi già presenti (specie nelle chiamate)

Come farlo ?Uso di una tabella degli indicidei metodi divisa per classiche permette di dare un accessoveloce ai metodi stessi durantel’esecuzione senza avere calcolatoprima le posizioni delle classie dei metodi stessi

unico descrittore del componente

tabella

puntatori ai metodi classe

accesso ai metodi della entità

unicapuntatori ai metodi classe1

puntatori ai metodi classe2

puntatori ai metodi classe3

puntatori ai metodi classe4

di puntatoriclasse1+3

CLASSI MULTIPLE e USO dei METODICLASSI MULTIPLE e USO dei METODICon componenti con ereditarietà multipla e in architetture distribuite,

I metodi sono ritrovati dinamicamente in modo indiret to , in ogni caso, attraverso l’accesso ad una tabella dei metodi (e interfacce)La tabella registra tutte le classi per quel component e e per ciascuna inserisce a run-time il puntatore al metodo stessoIl ritrovare il metodo richiede due passi:- di ritrovare nel componente la classe di interesse come posizione

Modelli 24

- di ritrovare nel componente la classe di interesse come posizione- di ritrovare lo spiazzamento del metodo ricercatoL’accesso indiretto è spesso usato in sistemi dinamici

Si può scalare ogni metodo in base alla posizione corrente della interfaccia nella classe corrente di riferimentoI metodi di ogni classe sono ritrovati partendo dalla classe stessa in cui sono riferiti, isolandola e considerandola in modo separato

Dobbiamo avere un modo di isolare la classe e di poterla riferire Una API potrebbe essere ClassofInterest GetClassRepresentation(Classe)

INTERFACCE MULTIPLE e COMPONENTIINTERFACCE MULTIPLE e COMPONENTITutto quello che abbiamo detto per ereditarietà multipla di classi in architetture distribuite, si può applicare al caso di componenti che implementano delle interfacce di met odi legacy predefiniticome i componenti DCOM distribuitiI metodi di ogni interfaccia sono ritrovati partendo dalla interfaccia in

Modelli 25

I metodi di ogni interfaccia sono ritrovati partendo dalla interfaccia in cui sono riferiti, isolandola e considerandola in modo separato

Abbiamo una API che isola in un componente corrente, una interfaccia di interesse HRESULT QueryInterface(const GUID Identifier;

out void ** InterfaceIsolatedPtr);

Ogni componente deve supportare la QueryInterface…che è parte di una interfaccia di ogni componenteAnzi, che è parte della interfaccia di base di ogni componente

SEMANTICA per RIFERIMENTOSEMANTICA per RIFERIMENTOGli oggetti non contengono altri oggettiIn sistemi ad oggetti, gli attributi non primitivi hanno semantica per riferimento cioè contengono solo riferimentiQuindi attraverso una variabile (con un tipo) posso riferire una altra istanzaCambiando valore della variabile posso riferire successivamente una altra istanzaGli oggetti passivi durante la esecuzione determinano un grafo di

Modelli 26

Gli oggetti passivi durante la esecuzione determinano un grafo di riferimenti tra di loro

unRettangolo

originerett1

vertice

1,1

10,11

unPunto

unPunto

RIFERIMENTI locali e REMOTI (?)RIFERIMENTI locali e REMOTI (?)In un sistema ad oggetti locale, il grafo si sviluppa nell’ambito della stessa macchina virtuale locale con variabili per riferime nto

Attraverso una variabile posso riferire una altra istanza solo locale

originerett1

vertice

1,1

unPunto

Modelli 27

In genere i sistemi più diffusi (Java) assumono che un programma o applicazione faccia solo riferimenti interni alla macchina virtuale e locali

Come si possono ritrovare entità esterne ?Si usano protocolli esterni di comunicazione introdotti per i sistemi distribuiti con agganci localiAd esempio: TCP/IP ed il suo sistema di nomi (e socket )

unRettangolo10,11

unPunto

RIFERIMENTI REMOTIRIFERIMENTI REMOTIIn un sistema ad oggetti, usiamo il supporto di un ambiente esterno per potere coordinare macchine (virtuali) diverse

Un oggetto C1 sul nodo 1 può riferire usando il supporto di Javale istanze locali di S1Se si vuole riferire una istanza remota abbiamo bisogno di un

Modelli 28

Se si vuole riferire una istanza remota abbiamo bisogno di un supporto intermediario che estenda la visibilità

In alcuni casi i riferimenti locali e remotisono resi uniformi attraverso intermediari locali(proxy ) che si incaricanodi mascherare il supporto

C1 instance

S1 instance

CLASS server S1

operations

state

Supporto di INTEGRAZIONE

S1 instance

per la DISTRIBUZIONE

RIFERIMENTI REMOTI via RMIRIFERIMENTI REMOTI via RMITra due sistemi Java possiamo usare Remote Method Invocation (RMI) che costruiscono due proxy, - uno dalla parte del cliente (stub)- uno dalla parte del servitore (skeleton)

I proxy sono spesso generati C1 instance

Modelli 29

automaticamente e facilitanoil progetto della parte utenteche ragiona indipendentementedalla distribuzione

In modo del tutto simile in altri ambienti uniformi con ampio supporto(CORBA , DCOM, ecc.)

C1 instance

N1 node

S1 instance

CLASS server S1

operations

state

S1 proxyC1 proxyN2 node

Supporto di INTEGRAZIONE

per la DISTRIBUZIONE

RIFERIMENTI REMOTI via PROXYRIFERIMENTI REMOTI via PROXYDue macchine virtuali Java usano PROXY per ottenere visibilità remote dei riferimenti per usare RMIMolte necessità di supporto e problemi:- Come si ottiene la conoscenza del servitore? (sistema di nomi)- Dove sono le classi accessorie?- Come ottenerle (durante la esecuzione)?

Modelli 30

- Come ottenerle (durante la esecuzione)?- E se ci sono inconsistenze?- E se il server non fosse attivo?- E se non mantenesse lo stato?Sui riferimenti remoti:- due riferimenti per lo stesso oggetto? - due riferimenti per lo stesso servizio?- …

C1 instance

N1 node

S1 instance

CLASS server S1

operations

state

S1 proxyC1 proxyN2 node

Supporto di INTEGRAZIONE

per la DISTRIBUZIONE

RIFERIMENTI REMOTI e MIDDLEWARERIFERIMENTI REMOTI e MIDDLEWAREUn punto centrale in tutti i middleware che aiutano l’utente a non occuparsi di dettagli è come si consente un riferimento remoto, che permetta di accedere a entità non local i in modo trasparenteBisogna sicuramente per ciascuno valutare il meccanismo di supporto

Modelli 31

meccanismo di supporto - Quanto costa l’accesso?- Quanto costa l’organizzazione

di supporto del middleware?- Come ottenere il riferimento remoto?- Sono possibili inconsistenze?- Quali compiti ha il supporto?- …

Cliente

N1 node

Server REMOTO

operations

state

Cliente locale

N2 node

Middleware comeSupporto per la DISTRIBUZIONE

Cliente locale

OGGETTI vs. COMPONENTIOGGETTI vs. COMPONENTIUn punto centrale nel distribuito è anche la difficoltà del supporto agli oggetti di un linguaggio e come si possa facilmente ottenere un modello di uso più auto-cont enuto e semplice da capire e da usare

Bisogna sicuramente limitare l’impatto dell’oggetto e la sua forte interazione con l’ambiente contenente

Modelli 32

la sua forte interazione con l’ambiente contenente Modello ad oggetti poco confinato e molto dipendent e dall’ambiente di esecuzione

Modello a componentiPer definire entità che siano più facilmente auto-contenute e tras-portabili da un ambiente ad un altroDefinizione di componente: “astrazione statica di una entità confinata con porte di collegamento verso l’esterno”

COMPONENTICOMPONENTI

Un componente- Statico in quanto indipendente dalla applicazione e con vita propria- Astratto senza visibilità della specifica struttura internamostrando solo porte di ingresso e uscita - Porte come uniche entità riconosciute per la interazione, da e per

OUT

ININ

COMPONENTE SOFTWARE

Modelli 33

- Porte come uniche entità riconosciute per la interazione, da e per l’esterno

Effetto di migliore riusabilità , con facile trasportabilità da un ambiente ad un altro (non ci sono interazioni nascoste, ma sono tutte visibili), possibilità di sostituzione di una implementazione con un’altra (aggancio dinamico) senza intervenire sull’ambiente, Verso la realizzazione di Servizi e SOA (Service Oriented Architecture o SOA)

ANCORA COMPONENTIANCORA COMPONENTI

Un componente ancora"A component is an object in a tuxedo. That is, a piece of software that is dressed to go out and interact with the world" Michael Feathers

OUT

ININ

COMPONENTE SOFTWARE

Modelli 34

Un componente è tipicamente una entità a grana più grossa di un oggetto, molto più autocontenuta e capace di operare in ambienti diversi …spesso viene a lavorare in un container , ossia un server di supporto capace di interagire con il componente e di fornirgli molte azioni necessarie con una buona divisione dei compiti

J2EE, EJB come contenitori capaci di ospitare componenti progettati per loro

SISTEMI a COMPONENTISISTEMI a COMPONENTIUn sistema a componenti si basa esclusivamente su componenti che hanno queste proprietà- Incapsulamento della implementazione- Condivisione delle risorse che devono essere assegnabili

dinamicamente- Composizione formando nuovi componenti a partire dai

componenti esistenti

Modelli 35

- Composizione formando nuovi componenti a partire dai componenti esistenti

- Ciclo di vita come diverse possibilità di esistenza del componente

- Attività come espressione di output attraverso la interazione di componenti

- Controllo come presenza di una funzione di monitoraggio e controllo dei componenti

- Mobilità come possibilità di introdurre e rimuovere componenti in modo dinamico

DEPLOYMENT di APPLICAZIONEDEPLOYMENT di APPLICAZIONEUna applicazione viene sviluppata determinando oggetti e classinecessarie ai requisiti e, se non si lavora su una unica macchina, si decide un deployment su più macchine che comporta di - partizionare la applicazione in aggregazioni componenti e - basarsi su un supporto per i riferimenti remoti

Applicazione

Modelli 36

La applicazionesi divide in risorseche rappresentano i componentida mappare sul deployment

Applicazione

C1 C2

C3C4

C5

C6

C7

C8

C9

Possibile suddivisione in componenti

COMPONENTI della APPLICAZIONECOMPONENTI della APPLICAZIONEUna applicazione deve essere portata in un deployment su un certo numero di processori e si deve decidere come raggruppare i componenti sui processori stessiLa applicazione prevede risorsesia statiche (rappresentate nel lucido precedente) facilmente raggruppabili secondo necessità, in modo da avviare il tutto con i componenti allocati

Modelli 37

avviare il tutto con i componenti allocatisia dinamiche (non rappresentate nel lucido) che sa ranno create durante la esecuzione o potrebbero anche non essere create in alcuni runSi pensi ai processi o alle risorse che dipendono dalla esecuzione e che possono essere create solo in alcune esecuzioni, dipendentemente dallo stato e dal progresso della applicazione stessa

Allocazione …. o Deploymentle entità di una applicazione possono essere

o statiche o dinamiche (o miste )Allocazione statica : data una specifica configurazione (odeployment), le risorse sono decise prima della allocazioneAllocazione dinamica : la allocazione delle risorse è decisa

MODELLO di ALLOCAZIONEMODELLO di ALLOCAZIONE

Modelli 38

Allocazione dinamica : la allocazione delle risorse è decisadurante la esecuzione ���� sistemi dinamici

Risorse statiche (sempre decise in modo statico) Risorse dinamiche decise anche in modo statico … eIn sistemi dinamici, si creano risorse dinamiche non previste esi può pensare di riallocare risorse esistenti (migrazione):le risorse possono muoversi sulla configurazione durantela esecuzioneRisorse dinamiche decise anche in modo dinamico

- MANUALE� l’utente determina ogni singolo oggetto e lo trasferisce sui

nodi appropriati con sequenza appropriata di comandi

- APPROCCIO con FILE SCRIPT���� si devono eseguire alcuni file di script (qualche linguaggio

SUPPORTO DEPLOYMENTSUPPORTO DEPLOYMENT

Modelli 39

���� si devono eseguire alcuni file di script (qualche linguaggioshell, bash, perl, ecc.) racchiudono la sequenza dei comandiper arrivare alla configurazione che presenta dipendenzetra oggetti

- APPROCCIO basato su MODELLO o LINGUAGGI���� supporto automatico alla configurazione attraverso

linguaggi dichiarativi o modelli di funzionamento dellaconfigurazione da ottenere (ad esempio SmartFrog e Radia)

- APPROCCIO ESPLICITO (comandato dall’utente)� l’utente prevede il mappaggio per ogni risorsa potenzialmente

da creare prima della esecuzione

- APPROCCIO IMPLICITO (automatico)���� il sistema si occupa del mappaggio delle risorse della

applicazione

MODELLI di ALLOCAZIONEMODELLI di ALLOCAZIONE

Modelli 40

applicazione(anche al deployment e durante la esecuzione)

- APPROCCIO MISTO���� il sistema adotta una politica di default applicata sia

inizialmente per le risorse statiche sia dinamicamente per laallocazione delle nuove risorse e la migrazione di quelle giàesistenti

���� eventuali indicazioni dell’utente sono tenute in conto permigliorare le prestazioni

- APPROCCIO ESPLICITOCosto elevato : l’utente che prima della esecuzione deve prevedere un

mappaggio per ogni risorsa, anche che non sarà creata

- APPROCCIO IMPLICITOCosto limitato: il sistema si occupa del mappaggio solo delle parti

necessarie ���� le statiche e le dinamiche su bisogno

MODELLI di ALLOCAZIONEMODELLI di ALLOCAZIONE

Modelli 41

- APPROCCIO MISTOCosto variabile, bilanciabile e adattabile:

il sistema adotta una politica per ogni risorsa, o statica o dinamicadecisioni statiche possono essere ottimizzate prima del ru n-timedecisioni dinamiche possono essere a costo diverso, a secon dodel carico del sistemail sistema può anche usare politiche che tengono conto di indicazioniutente, se è il caso:

un oggetto deve essere coresidente con un altro, se il nodo non troppocarico oppure sul nodo N4 …

Scelta di un deployment o di un altro� Può avere un grande impatto durante la specificaesecuzione e deve essere tenuto in conto

Pensate a dei componenti che debbano comunicare ,- dobbiamo considerare strumenti di comunicazione internodose i componenti potranno essere allocati su nodi diversi

INTERESSE per il DEPLOYMENTINTERESSE per il DEPLOYMENT

Modelli 42

se i componenti potranno essere allocati su nodi diversi- dobbiamo scegliere gli strumenti di comunicazione più adattiper la allocazione che stiamo determinando (pensate adarchitetture diverse ed eterogenee di supporto)- dobbiamo anche ottimizzare gli strumenti di comunicazionequando i componenti sono presenti sulla stessa macchina ,differenziando comunicazioni internodo e intranodo (comespesso fanno i middleware esistenti)- dobbiamo verificare che il deployment sia adatto aglistrumenti di comunicazione scelti e non produca problemi(cercando colli di bottiglia e casi critici )

Vincolo di deployment in RMI� Il registry deve essere sullo stesso nodo del server e i clientidevono comunicare con lui per ritrovare il riferimento remoto� Questo rende la architettura vincolata a un nodo centrale

Possiamo fare un progetto con una diversa architettura,I riferimenti remoti possono anche essere derivati da un

CASO di RMICASO di RMI

Modelli 43

I riferimenti remoti possono anche essere derivati da unpassaggio di parametri (magari con un unico mediatore)

- possiamo prevedere una architettura in cui ai clienti i riferimenti aiserver sono passati attraverso una funzione di attivazione iniziale esenza conoscenze pregresse- eliminando il collo di bottiglia del nodo del server e del registry, chepossono introdurre dei forti limiti alla scalabilità e rappresentare unvincolo pesanteCosì possiamo introdurre nodi senza avere problemi di vincoli, incaso di crescita del sistema (estensibilità ) e di necessità diintrodurre nodi

Cliente/Servitore e richiesta operazioneIntrinsecamente distribuito su nodi diversiregole di comunicazione di alto livello :

modello asimmetrico con il cliente che conosce il servitore e interagisce in modo sincrono e bloccante (a default)

Modello C/SModello C/S

Modelli 44

(a default)Modello con forte accoppiamento:

compresenza di chi interagisceOvviamente ci interessano solo modelli che siano intrinsecamente distribuibili e distribuitie che portino a deployment realmente distribuiti

Ci sono molti punti deboli del C/S e difficoltà di usotipicamente superate da variazioni per esigenze specifiche

Molte variazioni del Cliente/ServitoreModelli pull

(faccio io il recupero del risultato con o senza attesa)Modelli push

(il server mi allunga il risultato e io lo recupero poi localmente)Modelli a delega per la attesa della risposta

MODELLI MODELLI -- OLTRE IL C/SOLTRE IL C/S

Modelli 45

Modelli a delega per la attesa della risposta (faccio aspettare un altro al posto mio e recupero il risultato da questo)

Modelli di notifica per la risposta (il delegato mi notifica che una risposta è arrivata)

Modelli ad eventi(un evento viene reso noto agli interessati consumatorie generato da produttori)

Modelli di provisioning(oltre al servitore e al cliente, una serie di intermediari interessati)

Introduzione di entità per la interazioneRispetto ad un puro meccanismo cliente servitore, si usanooggetti di Poll e Call-Back come intermediari

Oggetto Poll Oggetto Call-Back

DELEGA DELEGA -- RECUPERO RISULTATO…RECUPERO RISULTATO…

Modelli 46

Operazioni corte ed attese limitate Operazioni lunghe e ind ipendentidal chiamante

Si deve definire bene cosa sono e come sono strutturati

Modello a scambio MESSAGGIMolto flessibile e primitivoScambio di informazioni: proprietà

sincrono/asincrono (risultato o meno)simmetrico/asimmetrico (conoscenza pari o meno)indiretto/diretto (entità intermedia o meno)

SCAMBIO MESSAGGISCAMBIO MESSAGGI

Modelli 47

indiretto/diretto (entità intermedia o meno)Implementazione

bloccante/non bloccante (blocco del mittente in attesa)bufferizzato/ non (batch di messaggi)reliable/unreliable (senza o con perdita di messaggi)

Modalità a ricevente multiplomulticast (MX) e broadcast (BX)

A volte messaggi come solo informazioni elementari di sincronizzazione (e non comunicazione)

Cliente/ServitoreModello con forte accoppiamento:

compresenza di chi interagisceMeccanismo adatto per comunicazioni semplici ma poco flessibili di alto livello (ossia adatta per usi applicativi) con difficoltà in situazioni diverse, vedi multicast e broadcast

C/S vs SCAMBIO MESSAGGIC/S vs SCAMBIO MESSAGGI

Modelli 48

con difficoltà in situazioni diverse, vedi multicast e broadcast

Scambio messaggi Sender/ReceiverModello con limitato accoppiamento:

non compresenza grazie al bufferingComunicazione primitiva, flessibile, espressiva, magari difficile da maneggiaredi basso livello (ossia adatta per usi di sistema):

forme molto varie , anche con più facile supporto a forme di multicast e broadcast

Gli strumenti di comunicazione possono imporre o menodei vincoli sulle entità che devono interagire

Questi vincoli possono anche introdurre forti limiti su chi interagisce e introdurre necessità di conoscenze che a volte non sono necessarie

Accoppiamento in vari modi- spazioLe entità si devono conoscere (reciprocamente) e essere co-locate

DIS / ACCOPPIAMENTODIS / ACCOPPIAMENTO

Modelli 49

Le entità si devono conoscere (reciprocamente) e essere co-locate- tempoLe entità interagenti devono essere compresenti (presenti insieme nello stesso instante)- sincronizzazioneLe entità interagenti devono aspettarsi a vicenda e sono soggette a blocchi reciprociIl disaccoppiamento diventa un fattore per l’abilit azione di maggiore flessibilità e per arrivare a modelli che possono sfruttare la potenziale distribuzione

Disaccoppiamento tra entità interagentiGli eventi permettono ai produttori di generare eventi (publish ) e di disinteressarsi della consegnaI consumatori si sono registrati come interesse ad un evento (subscribe ) e sono avvisati della occorrenza

EVENTI e PUBLISHEVENTI e PUBLISH--SUBSCRIBESUBSCRIBE

Modelli 50produce quotazione

SISTEMA gestoredell'offerta degli eventi

produce quotazione

consuma offerta

consuma offerta

PRODUTTORE

PRODUTTORE

CONSUMATORE

CONSUMATORE

Produttori e consumatori

non devono essere presenti

insieme

Modello diverso rispetto a C/S di richieste sincron e a kernelIl Framework tende a rovesciare il controllo (per eventi di sistema)

Il processo utente non aspetta, ma registra con una propria funzioneEsempio: Windows che prevede per i processi un loop di attesa

di eventi da smistare ai richiedentiAll’arrivo di un risultato questo viene portato al processo significativo

Le risposte dal framework

FRAMEWORK: EVENTI LOCALIFRAMEWORK: EVENTI LOCALI

Classi esistenti

Da Reti LDa Reti L--AA

Modelli 51

Le risposte dal framework all’utente sono dette backcall o upcallassimilabili aeventi asincronigenerati dal supportoche le applicazionidevono gestire tramite una funzione di gestionespecificata dall’utente

Funzioni e servizi

ADTs

matematiche

GUI

LOOP gestioneeventidi sistema

internet

database

logica specifica

della applicazione

3D rendering

BACKCALL

UPCALL

I sistemi ad eventi devono essere pensati e progettatisenza vincoli di località di nessun tipo

Il modello ha la sua forza nella non località delle entitàinteragentiimplementazioni solo locali (ad esempio che prevedono ilvincolo della condivisione del codice tra produttore econsumatore) sono downsizing arbitrari e non sensati del modello

SISTEMI ad EVENTISISTEMI ad EVENTI

Modelli 52

consumatore) sono downsizing arbitrari e non sensati del modello

Realizzare un sistema ad eventi non tenendoconto del potenziale disaccoppiamento, …vuole dire usare male il modello, una delle cose peggiori che possiamo fare usando una tecnologia

Se si vincolano gli eventi alla co-residenza e alla compresenza delle entità interagenti, stiamo determinando dei deployment che contrastano con il modello di base che stiamo usando

I sistemi ad eventi sono pensati per grandisistemi e alcuni indicatori sono fondamentali

Costo nella distribuzione degli eventi (da limitare)Performance (da ottimizzare)Scalabilità (alta)Tempi di Latenza (da limitare)

SISTEMI ad EVENTI: INDICATORISISTEMI ad EVENTI: INDICATORI

Modelli 53

Tempi di Latenza (da limitare)Pervasività del servizio (alta)Sviluppo ed esecuzione indipendente (elevata)Tolleranza ai guasti (massima)

Si devono quindi pensare a sistemi ad eventi realizzabili in cui gli indicatori , per tutte le possibili realizzazioni distribuite, presentino indicatori accettabili , magari ‘costanti’ … beh almeno prevedibili

Eventi primitiviGli eventi sono spesso considerati segnali on/off senza contenuto informativoeventi di interrupt o segnali associati ad una funzione di gestioneEventi con contenutoAlcuni eventi hanno un contenuto e si possono pensare anche afiltri di interesse e a ragionare sul contenuto

EVOLUZIONE dei SISTEMI ad EVENTIEVOLUZIONE dei SISTEMI ad EVENTI

Modelli 54

filtri di interesse e a ragionare sul contenutoRSS con registrazione su temi specifici o multicast differenziato su gruppi di destinatari diversi con registrazioni differenziateEventi con qualitàAlcuni eventi hanno requisiti da specificare in modo differenziato per i diversi utilizzatori e si possono pensare anche supporti differenziati (persistenza, tempo di mantenimento, reliability, …)Eventi persistenti : gli utenti non perdono eventi anche se off-line e ricevono tutti gli eventi non ricevutiPriorità degli eventi , Spazio e numero di eventi in coda, …

Sistemi PUB-SUB identificati come sistemi evoluti basati sumodelli ad eventi e scambi di messaggi per sfruttarne laflessibilità ed il disaccoppiamento di interazioneaumentando scalabilità e distribuibilità

Il modello PUB-SUB ha anche ulteriori flessibilità …Filtraggio dei messaggi sulla base di

SISTEMI PUBLISHSISTEMI PUBLISH--SUBSCRIBESUBSCRIBE

Modelli 55

Filtraggio dei messaggi sulla base ditopic-based : sulla base del soggetto di interesse (si pensi a uninteresse specificato tra diversi canali possibili, RSS specifico)content-based : sul soggetto del contenuto del messaggio (si pensia una parola chiave o una relazione di interesse)type-based : sul tipo di messaggio (si pensi distinguere tipi diversi epotere selezionare a priori)Qualità di Servizio (QoS) sui messaggiPersistenza, Priorità, Garanzia di mantenimento e durata, …

MODELLO a TUPLE per la INTERAZIONEmodello generale per comunicazione e sincronizzazioneprogettato come astrazione della memoria condivisa + comunicazioneUno spazio di tuple è un insieme strutturato di relazioni , intese comecontenitori di attributi e valori per PUB-SUBSu uno spazio di tuple si possono depositare / estrarre informazioni di

MODELLI DISACCOPPIATI MODELLI DISACCOPPIATI -- TUPLETUPLE

Modelli 56

Su uno spazio di tuple si possono depositare / estrarre informazioni dialto livello senza causare interferenze

Una possibile relazione: messaggio (dachi , achi , corpo )Lo spazio serve da contenitore per valori di tuple in accordo al pattern specificato(ai tipi degli attributi, qui stringhe ASCII)

Tuple per lo spazio messaggio: {Antonio , Giovanni , msg1 }{Giovanni , Antonio , msg1 } {Antonio , Giovanni , msg2 } …Non ci sono limiti alle tuple che si possono depositare e che possono rimanerenello spazio delle tuple senza limiti di tempo o di memoria

Operazioni di In e Out sullo spazioSu spazi di tuple sono sempre possibili operazioni di scrittura elettura concorrenti corrette con accesso in base al contenuto degliattributiIn estrazione di una tupla dallo spazio e Out inserimento di una tupla

La Out emette la tupla sullo spazio a disposizione di richieste e lìrimane fino ad un consumo corrispondente (una sola In)La In estrae una tupla dallo spazio adatta alle esigenze, se esiste

TUPLE TUPLE -- Linda (Gelernter)Linda (Gelernter)

Modelli 57

La In estrae una tupla dallo spazio adatta alle esigenze, se esisteSe non esiste, aspetta fino a che non se ne riceve unaIl match avviene in base al pattern sui valori degli attributi

In caso di match con più tuple, una sola viene estratta nondeterministicamente

Out : messaggio (P, Q, testo1)In: messaggio (?dachi, Q, ?corpo)La In aspetta una tupla in cui il secondo attributo presenti la stringa Q eproduce valori per dachi (=P) e corpo (=testo1)

Spazi di tuplePortano ad una comunicazione disaccoppiata e poco sincronaIn tempo

Un processo potrebbe lasciare tuple in un sistema distribuito e solo molto dopoi relativi consumatori potrebbero arrivare a prelevare le tuple stesse

In conoscenza reciproca (spazio e sincronizzazione)

DISACCOPPIAMENTO TUPLE DISACCOPPIAMENTO TUPLE

Modelli 58

i consumatori non devono conoscere in alcun modo i processi produttori e nonpossono interferire (una operazione estrae una tuple, eventuali altre aspettano)

In qualità - QoSGli spazi delle tuple sono persistenti e tendono a mantenere le tupledepositate senza limiti di memoria (come requisiti) senza introdurreinterferenza tra processi

Spazi di tuple sono messi a disposizione per favorirecomunicazioni ben fatte di alto livello

Javaspaces, …

PROXYIn una comunicazione si possono interporre intermediari sia dalla parte del richiedente sia dalla parte del fornitore del servizio PROXY

INTERMEDIARI e PROXYINTERMEDIARI e PROXYRichieste

Cliente Servitore

Operazioni

Proxy C Proxy S

Modelli 59

PROXYdel cliente o del servitore

proxyC/S stub e skeleton

interceptor per aggiungere funzionalità

broker simile al container

Richieste

Cliente Servitore

Operazioni

Proxy C Proxy S

broker o gestore del link

per il binding dinamico tra le entità

CONTENIMENTOSpesso molte funzionalità possono essere non controllate direttamentema lasciate come responsabilità ad una entità delegata supervisore(contenitore ) che se ne occupa• spesso introducendo politiche di default• evitando che si verifichino errori• controllando eventuali eventi

MODELLI A CONTENIMENTOMODELLI A CONTENIMENTO

Modelli 60

• controllando eventuali eventi

I contenitori (entità dette anche CONTAINER, ENGINE,MIDDLEWARE , …) possono occuparsi di azioni automatiche da cui vienesgravato l’utilizzatore che deve specificare solo la parte contenutatipicamente

di alto livello,non ripetitiva,fortemente dipendente dalla logica applicativa

CONTAINERUn servizio utente potrebbe essere integrato in un ambiente (middleware ) che si occupa in modo autonomo di molti aspetti diversi

MODELLI A CONTENIMENTOMODELLI A CONTENIMENTOCONTAINER

Richieste

Cliente 1

Cliente 2

OPERAZIONI VARIE

Modelli 61

Vedi CORBA tutti aspetti C/S Engine per framework a GUIContainer per servletSupporto per componenti

Container possono ospitare componenti più trasportabili e mobili

Cliente 2

Cliente iCliente i

Cliente i

OPERAZIONE SEMPLIFICATA

Il container può fornire “automaticamente” moltedelle funzioni per supportare il servizio dell’utente- Supporto al ciclo di vita

Attivazione del servitore / deattivazione /Mantenimento dello stato

DELEGA al CONTAINERDELEGA al CONTAINER

Modelli 62

Mantenimento dello statoPersistenza e recupero delle informazioni (interfaccia DB )

- Supporto al sistema dei nomiDiscovery del servitore / servizio /Federazione con altri container

- Supporto alla qualità del servizioTolleranza ai guasti, selezione tra possibili deploymentControllo della QoS richiesta e ottenuta

…

Un container potrebbe essere anche capace di facilitare sia l’esecuzione di componenti diversi, come

servlet , JSP, bean di varia architettura e tipo

J2EE J2EE –– Java 2 Enterprise EditionJava 2 Enterprise Edition

Modelli 63

TRASPARENZA (vs. VISIBILITÀ )Accesso omogeneità accesso alle risorse locali e remoteAllocazione uso indipendente dalla località o meno delle risorseNome indipendenza del nome dal nodo di residenzaEsecuzione non distinguibilità dell’uso di risorse locali e remotePerformance non degrado nell'uso dei servizi locali o remotiFault capacità di fornire servizi anche in caso di guasti

TRASPARENZATRASPARENZA

Modelli 64

Fault capacità di fornire servizi anche in caso di guastiReplicazione capacità di usare risorse molteplici per un

servizio unificato con migliore QoS

La trasparenza è sempre un requisito da ottenere?ad ogni costo , per ogni livello di sistema , per ogni applicazione estrumento

(??) Location-awareness per la generazione di servizi chedipendono dalla visibilità della allocazione corrente

Telecommunications Information Networking Architect ure

TINA-C - Consortium definisce modelli di servizio e disponib ilità

Si considerano utenti di un servizio (ad es. comunicazione con altri utenti)Questo è reso possibile da una serie di altri agenti in gioco: molteplicità di servizi e da una collaborazione di provider e facilitatori degli stessi.Si considerano tutti i provider di rete e di servizio

TINATINA--Consortium Consortium –– oltre il C/Soltre il C/S

Modelli 65

Si considerano tutti i provider di rete e di servizio

Accordo e negoziazione tra parti per il servizio

coinvolgendo risorse di comunicazione e tenendo conto della necessità di fare la gestione delle risorse durante il servizio

Le entità in gioco decidono un livello di QoS da ma ntenere come prerequisito per il servizioSe il servizio viene completamente erogato con la QoS negoziata

TINATINA--C C –– PROVISIONING e QoSPROVISIONING e QoS

Modelli 66

Se il servizio viene completamente erogato con la QoS negoziata viene considerato significativo, avvenuto con successo, e da pagare

Una macchina ad accesso random (RandomAccess Machine) è costituita da:

- un programma inalterabile composto di istruzioni in sequenza

- una memoria composta di una sequenza di parole,

Modello astratto (concentrato) Modello astratto (concentrato) –– RAMRAM

Modelli 67

- una memoria composta di una sequenza di parole, ciascuna capace di contenere un intero

- un solo accumulatore capace di operare- un nastro di input (read-only)- un nastro di output (write-only)

Durante un passo la RAM esegue una istruzione delprogramma in sequenza , a parte i salti

Istruzioni ad esempio: read, write, load, store, add, sub,mul, div, jump (acc), ..., haltModi di indirizzamento: immediato, diretto, indiretto

Modello RAMModello RAM

Modelli 68

Modi di indirizzamento: immediato, diretto, indiretto

La RAM è una macchina special-purpose per larisoluzione di un problema specificolimiti:- non c'è limite alla memoria di programma- le istruzioni richiedono tutte lo stesso tempo

Una macchina parallela ad accesso random (ParallelRandom Access Machine) è costituita da una collezione diRAMUna PRAM di dimensione P è composta da:

- P programmi inalterabili ciascuno fatto di istruzioni in sequenza- una sola memoria composta di una sequenza di parole capaci di

Modello PRAMModello PRAM

Modelli 69

- una sola memoria composta di una sequenza di parole capaci dicontenere un intero

- P accumulatori capace di operare- un nastro di input ed uno di output

Durante un passo, la PRAM esegue P istruzioni, una perogni programma(modello MIMD o meglio MIMD sincrono)

DISTINZIONE semanticain base a come si eseguono le operazioni su una stessa cella di memoriaOperazioni di lettura/scrittura: operazioni simultanee (Concorrenti) esequenzializzate (Esclusive)Concurrent Read Exclusive Write (CREW PRAM)Exclusive Read Exclusive Write (EREW PRAM)

Modello PRAMModello PRAM

Modelli 70

Exclusive Read Exclusive Write (EREW PRAM)Concurrent Read Concurrent Write (CRCW PRAM)Exclusive Read Concurrent Write (ERCW PRAM)

lettura scritturaCREW

EREW

CRCW

ERCW

concorrente esclusiva

esclusiva esclusiva

concorrente concorrente

esclusiva concorrente

Operazioni concorrenti: quali effetti?

Operazioni sequenziali: ritardo sui programmiPrincipio di serializzazione ����

gli effetti come se una operazione fosse fatta per prima nelprimo passo , poi un'altra in successione nel successivo, poiun'altra ancora, etc., tutte in un passo di istruzione

Interferenza Operazioni ConcorrentiInterferenza Operazioni Concorrenti

Modelli 71

limiti:- le istruzioni richiedono lo stesso tempo- il tempo di operazione non dipende da P

accesso a memoria comune in un tempo che non cresce con P- il tempo di operazione di input/output trascurato

accesso ad un unico nastro non cresce con P

I/O bottleneck ���� Uso di concorrenza per gestire il sottosistema I/O

Una RAM con Message Passing (Message Passing-Random Access Machine) è una collezione di RAM,ciascuna con una memoria privata e connessione concanali punto a punto

Una MP-RAM di dimensione P è composta da:

Modello MPModello MP--RAMRAM

Modelli 72

Una MP-RAM di dimensione P è composta da:- P programmi inalterabili ciascuno fatto di istruzioni in sequenza- P memorie composte di una sequenza di parole- P accumulatori capaci di operare sulla propria memoria- un nastro di input ed uno di output- un grafo di interconnessione punto-a-punto (ad albero, a stella, ecc.)

Ogni nodo ha un certo numero di vicini ed un grado diinterconnessione

Maggiore il grado di interconnessione, maggiore il costo dellaarchitettura, minore necessità di routing intermedio

Possibilità di comunicazione bidirezionaleLe istruzioni sono accresciute con: send e receive neighborDurante un passo, la MP-RAM esegue P istruzioni, una per ogni

Modello MPModello MP--RAMRAM

Modelli 73

Durante un passo, la MP-RAM esegue P istruzioni, una per ogniprogramma

DISTINZIONE semanticacosa succede se una receive arriva prima della send sul canale punto-a-punto corrispondente?

semantica sincronachi prima arriva, aspetta l’altro (se punto a punto)

rendez-vous

Espressività PRAM >> MP-RAMGlobalità PRAM >> MP-RAMLocalità MP-RAM >> P-RAMRealizzabilità MP-RAM >> P-RAM

i modelli PRAM e MP-RAM si possono emulare

Modello PRAM e MPModello PRAM e MP--RAMRAM

Modelli 74

i modelli PRAM e MP-RAM si possono emularereciprocamente

PRAM realizza il multicast/broadcast come un insieme di spazi

coordinato per i diversi canali (canali come dato ed un flag)send e receive come istruzioni che agiscono sul flag e poi sulvalore da ricevere/inviare

MP-RAM realizza la memoria comune usando passi intermedi,routing e temporizzazione

ProblemaIl modello PRAM è troppo potente ed astratto (globale)Il modello MP-RAM è più vicino alla implementazione(locale)

Gli algoritmi sono più veloci sul modello che nei sistemireali modellati

Modello PRAM e MPModello PRAM e MP--RAMRAM

Modelli 75

Gli algoritmi sono più veloci sul modello che nei sistemireali modellati

Modelli globali o non ristrettinessun vincolo ma difficoltà nella implementazione

Modelli locali o ristrettivincolo e facilità di implementazione

COMPLESSITÀ degli algoritmi

dipendenza dalla dimensione del problema Ncomplessità in tempo CT(n) (abbreviato in T(N))complessità in spazio CS(n)

Modelli COMPUTAZIONALIModelli COMPUTAZIONALI

Modelli 76

complessità in spazio CS(n)

Pensiamo a soluzioni parallele con più processori(parallelismo di grado P )COMPLESSITÀT(1,N) soluzione sequenziale T1(N)T(P,N) soluzione parallela con P processori TP(N)

SPEED-UP Miglioramento dal sequenziale al parallelo

S(P,N) = T(1,N) / T(P,N) SP(N) = T1(N) / TP(N)

EFFICIENZA Uso delle risorse

Indicatori sinteticiIndicatori sintetici

Modelli 77

E(P,N) = Speed-up / Numero Processori

E(P,N) = SP(N) / P EP(N) = T1(N) / P TP(N)

SP(N) al massimo P ed EP(N) al massimo 1

Si parla di speed-up come miglioramento introducendouna qualche variazione: in questo caso, parallelismoreale

Stiamo ragionando su valori medi SPEED-UP ideale ed EFFICIENZA

Indicatori idealiIndicatori ideali

Speed-up

Ci interessa l’intero range di risultati,tenendo presente che possono

Modelli 78

No. processori

Speed-up

Speed-up ideale

che possono esistere casi specifici di speed-up anomalo non significativie solo casi particolari� dipendenti dall'algoritmo

legge di GroshIl migliore deployment per un programma è

una esecuzione sequenzializzata su un unico process ore

Correlazione tra N e P : possiamo considerareN indipendente da P, o dipendente da P

Fattore di caricoFattore di carico

Modelli 79

N indipendente da P, o dipendente da PFATTORE di CARICO (loading factor) L = N / Pdependent size (N funzione di P)independent size (più interessante al crescere di N)

identity size (N == P)

OBIETTIVOTrovare la migliore approssimazione per ogni algoritmo che ciinteressa esaminare

Massimo speed-up ottenibile nel passaggio dal sequenzialeal parallelo… quindi massimo vantaggio nel parallelismo

legge di Amdhallo speed-up è limitato dalla parte sequenziale

Un programma si divide in due parti:

SPEEDSPEED--UPUP

Modelli 80

Un programma si divide in due parti: una parte parallela ed una parte sequenziale

Se un programma è costituito di 100 operazioni e solo80 possono andare in parallelo e20 richiedono sequenzialità

Anche con 80 processori �lo speed-up non può arrivare oltre 5

in situazione ideale , con migliore allocazione possibileper i due indicatori , speedup fisso, efficienza varia

Considerando SPEED-UP ed EFFICIENZA

Indicatori più realiIndicatori più reali

Non possiamo superare il limite di speedup dovuto ad Amdhal

Modelli 81

Prima zona lineare poi speedup costante ed efficienza calaNo. processori

Speed-up

limite dovuto allaparte sequenziale

Amdhal

Lo speedup viene ad essere limitato,così come la efficienza

Heavily Loaded Limit T HL(N) = infP TP(N)

il valore di P tale per cui si ottiene la minore complessità delproblema (cioè T minimo)

in genere, questo avviene con N/P molto elevato , cioè seogni processore è molto carico e con carico significativo

SPEEDSPEED--UP (OTTIMO?)UP (OTTIMO?)

Modelli 82

ogni processore è molto carico e con carico significativo

TP(N) = TCompP + TCommP

TCompP = TCompPar + TCompSeq

Limite di Amdhal (legge di Amdhal) considera il rapporto trale due parti dell'algoritmo in termini di computazione eidentifica il collo di bottiglia nella parte sequenziale

Problema di dimensione N con uso di P processoriper il caso di problema di somma di N interiComplessità del sequenziale O(N)Complessità del modello parallelo identity size (N == P)

Un numero di processori pari a P e connessioni ad albero:ogni nodo foglia passa il valore somma dei due valori base;ogni nodo passa i valori dal basso come somma verso alto;

Un CASO di studio (N==P)Un CASO di studio (N==P)

Modelli 83

ogni nodo passa i valori dal basso come somma verso alto;la radice fornisce il risultato all’utente

N = 2H+1 ~= P = 2H+1-1 (N valori ~= P processori in albero)

H = O (log2 P) = O (log 2 N)

TP(N) = O (H) = O (log 2 N) =~ 2 log 2 N

I valori fluiscono dalle foglie in su ed ogni nodo li somma ad ognipasso (solo tempo di comunicazione)

Efficienza tende a zero

L = N / P = 1

SP(N) = T1(N) / TP(N) = O(N) / O(log2N) = O(N/ log 2N)SP(N) = O(P/ log2P)

Un CASO di studio (N==P)Un CASO di studio (N==P)

Modelli 84

EP(N) = T1(N) / P TP(N) = O(1/ log2P) = O(1/ log 2N)

Maggiore il numero di processori (lo speedup aumenta)ma minore l’efficienza

I processori lavorano per una frazione sempre minoredell’intero tempo di soluzione (EP(N) cala al crescere di P)

Problema di dimensione N con uso di P processoriSe possiamo dividere il problema parallelizzandolo con uncerto fattore di caricoUna fase locale di lavoro (somme, Comp) ed una fase discambio di informazioni (Comm) per combinare i risultatiL = N/P

Un CASO di studio (indipendent size)Un CASO di studio (indipendent size)

Modelli 85

L = N/PT(P,N) = O(N/P + log2 P) = O (L + log2P) ossia TComp + TComm

SP(N) = T1(N) / TP(N) = O(N/ ((N/P) + log 2P)) =

O(P/ (1 + P/N log 2P))

EP(N) = T1(N) / P TP(N) = O(1/(1+ P/N log 2P))

N>>P Lo speed-up tende a P e la efficienza tende a 1

il caso di somma di N numeri con P processori concarico locale e comunicazione

Consideriamo unitario e uguale il costo delle somme e dellacomunicazione

TP(N) =~ N/P + 2 log2 P nodi totali P = 2H+1-1

CASO di STUDIOCASO di STUDIO

Modelli 86

TP(N) =~ N/P + 2 log2 P nodi totali P = 2 -1

SP(N) = N /(N/P + 2 log2 P) = N P /(N + 2 P log 2 P)EP(N) = N / ( N + 2 P log 2 P )

I due indicatori dipendono sia dal numero di processorisia dalla dimensione del problema

GraficamenteGraficamenteSPEED-UP

5

10

15

20

25

N=64

N=192

N=320

N=512

Modelli 87

0

1 4 8 16 32

EFFICIENZA

0

0,2

0,4

0,6

0,8

1

1,2

1 4 8 16 32

N=64

N=192

N=320

N=512

PROBLEMI- schematizziamo a meno di fattori costanti- a volte il caso peggiore può essere più significativo- trascuriamo completamente molti elementi

Trascuriamomovimento di dati I/O e

Indicatori come speedIndicatori come speed--up ed efficienzaup ed efficienza

Modelli 88

movimento di dati I/O emappaggio (deployment specifico)

Nel mondo reale ����

sono necessarie comunicazioni (non solo aregime, ma anche prima e dopo del regime)

Trasferimento iniziale dei datiStampa e gestione valori intermediRaccolta dei risultati

Complessità del modello parallelo heavily loaded limitSe L cresce TP HL (P,N) = O (L + log2 P) � OHL (L)

SP HL (N) = O(LP) / O( L + log2 P) � OHL (P)

E (N) = O(LP) / O( LP + Plog P) � O (1)

Ancora sul CASO di studioAncora sul CASO di studio

Modelli 89

EP HL(N) = O(LP) / O( LP + Plog2 P) � OHL (1)

Cioè, intuitivamente se carichiamo ogni nodo molto �

Il fattore di carico L è molto elevato

Si può raggiungere ancheuno speed-up ideale ed un’efficienza ideale

poiché abbiamo caricato bene tutti i processori e nessuno èusato poco e male

Assumiamo di avere mappato il problema nel modo migliore(configurazione e deployment )

Spesso non si possono fare allocazioni così faciliproblemi dinamici nella comunicazione dopo la allocazione

Si può considerare la funzione di Overhead Totale, o T 0

MAPPAGGIOMAPPAGGIO

Modelli 90

0

cioè tenendo in contole risorse ed il tempo speso in comunicazione

T1(N) tempo sequenziale di esecuzioneTp(N) tempo parallelo di esecuzioneT0(N) = T0 (T1, P) = P * TP (N) - T1(N) = |P * TP (N) - T1(N)|Se si lavorasse con efficienza massima, overhead nulloT0(N) = 0 => P * TP (N) = T1(N)

T0(N) >= 0 � T1(N) <= P * TP (N) ossia

P * TP (N) = T0 (N) + T1(N)T0 rappresenta il lavoro perso

TP(N) = (T0(N) + T1(N)) / P

OVERHEADOVERHEAD

Modelli 91

P 0 1

SP(N) = T1(N) / TP(N) = P * T1(N) / (T0(N) + T1(N))

EP(N) = S / P = T1(N) / (T0(N) + T1(N))

EP(N) = 1 / (T0(N)/T1(N) + 1) = 1 / (1 + T0(N)/T1(N))

Si dovrebbero fare misure precise in uno dei due sensie verificare le reali dipendenze: T0(N) da N e da P?

Nel caso della somma di N numeri con P processori

Consideriamo unitario il costo somma e comunicazioneTP(N) =~ N/P + 2 log2 P nodi totali P = 2H+1-1

T (N,P) = P T (N) - T (N) =~ P (N/P + 2 log P) – N

CASO di STUDIOCASO di STUDIO

Modelli 92

T0(N,P) = P TP (N) - T1(N) =~ P (N/P + 2 log2 P) – NT0(N,P) =~ 2 P log 2 P

L’overhead dipende in modo rilevante dal numero diprocessori impegnati

L’aumento è motivato dalla necessità di coordinarne illavoro, in fase iniziale, e per la raccolta dei risultati in fasedi completamento

Graficamente TGraficamente T oo

160

200

240

280

320

N=512

N=320

N=132

Modelli 93

0

40

80

120

160

1 4 8 16 32

N=132

N=64

Grafici sovrapposti

ISOEFFICIENZAISOEFFICIENZA

EP(N,P) = 1/ (T0(N)/T1(N) + 1 ) T1(N) è il lavoro utile

Obiettivo � mantenere l'efficienza costante

T0(N)/T1(N) = (1 – E) / E T0(N) = (1 - E) / E T1(N)

Modelli 94

T0(N,P) = ( (1 – E)/ E) T1(N,P) = K T1(N)

T0(N,P) = K T1(N) considerando il fattore K costante

La costante (?) K caratterizza il sistema

Nel caso precedente (1 nodo /1 valore) K non costanteNell’albero, K dipende da P ed N e vale (2 P log 2 P / N)

ISOEFFICIENZAISOEFFICIENZA

Funzione isoefficienzaSe teniamo costante N e variamo P, K determina se un sistema parallelo possa mantenere un'efficienza cost ante� cioè uno speed-up ideale

Se K è piccola ���� possibile alta scalabilità

Modelli 95

Se K è piccola ���� possibile alta scalabilitàSe K è elevata ���� poca scalabilitàK può non essere costante ���� sistemi non scalabili

Nell’albero, K vale 2 P log2 P / Nsistema scarsamente scalabile

I sistemi reali sono tutti scarsamenti scalabili ( sic ����)

CASO per RIFLESSIONECASO per RIFLESSIONEData una applicazione costituita da Q processicon infiniti processori a disposizionecome gestire la allocazione dei processori?

argomentate su quanti processori usareCome sono i processi?

Modelli 96

Come sono i processi?Quale è la interazione?Quanto è necessario caricare ogni singola macchina?La applicazione basata su oggetti?E le classi sono replicate?

La legge di Grosh dice che è bene usare un unico processore se la cosa è possibile e praticabile MAI!

ANCORA RIFLESSIONIANCORA RIFLESSIONI

se volessimo considerare l'esperienza dei sistemi concentrati di calcoloheavily loaded limit come buona situazione buona efficienza con processori molto carichi

Come è la vostra esperienza di utilizzatori di PC e

Modelli 97

Come è la vostra esperienza di utilizzatori di PC eworkstation?Cosa dice la legge di Grosh?Che senso ha parlare di processi leggeri e pesanti?Cosa ci guida per la efficienza?Come calcolare il fattore di carico in termini di processi per processore? Numero di processi per processori Ma quanti processi sono ragionevoli?