Esami Sistemi Distribuiti 2002-2011

UNIVERSITA' CA' FOSCARI DI VENEZIA
CORSO DI LAUREA IN INFORMATICA
A.A. 2004/2005
Sistemi Distribuiti
Compito – 25/1/2005
1. Definire i tipi di sincronizzazione fra orologi in sistemi distribuiti.
Illustrare in dettaglio un algoritmo e discuterne vantaggi e limiti.
Dare un esempio.
2. Illustrare il paradigma publish-subrcribe. Discutere i vari tipi di notifica e illustrare con
un esempio.
3. Descrivere l’algoritmo di bully per l’elezione in sistemi distributiti in forma algoritmica.
Discuterne le condizioni, la complessità computazionale e i vantaggi e limiti.
Illustrare con un esempio.
4. Cosa sono i lock gerarchici e per che motivi si utilizzano? Definire e illustrare con un
esempio.
5. Illustrare l’architettura del file system AFS. Discutere i problemi di consistenza della
cache. Confrontare con gli altri tipi di file system.
UNIVERSITA' CA' FOSCARI DI VENEZIA
CORSO DI LAUREA IN INFORMATICA
A.A. 2004/2005
Sistemi Distribuiti
Compito – 11/1/2005
1. Definire i diversi tipi di trasparenza nei sistemi disrtibuiti e illustrare in dettaglio un
esempio per ogni tipo.
2. Descrivere uno schema di comunicazione IPC in sistemi distribuiti che utilizza la
ritrasmissione di messaggi basata IP muticast per risolvere il problema dei messaggi
persi. Si ipotizzi che vi possano essere mittenti multipli, che soltanto una piccola
percentuale di messaggi venga persa e che, contrariamente al protocollo request-reply, i
mittenti possano inviare i messaggi senza necessariamente vincoli di tempo. Assumere
inoltre che i messaggi che non sono persi arrivino nell’ordine di invio. Descrivere lo
schema e discuterne le caratteristiche
3. Un file server usa la tecnica del caching con una hit rate dell’80%. Il costo delle
operazioni su file nel servente è di 5 ms di tempo di CPU quando il servente trova il
blocco di dati nella cache, mentre, in caso contrario, è di 15 ms di tempo di I/O.
Introducendo e spiegando appropriate assunzioni, date una valutazione del throughput nei
tre casi seguenti:
I. Singolo thread.
II. Due thread, su un solo processore.
III. Due thread, su due processori.
Descrivere in dettaglio la risposta.
4. Descrivere l’algoritmo di votazione in sistemi distribuiti dandone la descrizione
algoritmica e discutendone vangaggi e limiti.
5. Descrivere un sistema di replicazione gestito secondo il modello gossip. Illustrarne le
funzioni e descrivere il gestore di replicazioni.
UNIVERSITA' CA' FOSCARI DI VENEZIA
CORSO DI LAUREA IN INFORMATICA
A.A. 2003/2004
Sistemi Distribuiti
Compito – 15/6/2004
1. Considerare la comunicazione in un modello client-server in sistemi distribuiti.
Per quale motivo non si può dare in generale un limite superiore al tempo di
risposta di un server? Cosa occorrerebbe fare per rendere questo tempo limitato?
Proporre una soluzione e discuterne la fattibilità e convenienza.
2. Descrivere e discutere il modello di comunicazione basato su notifica di eventi in
sistemi distribuiti.
Spiegare poi se e come un osservatore (observer) che ha funzioni di inoltro
(forwarding) permette di migliorare la qualità del servizio in termini di
prestazioni e affidabilità.
3. Suggerire uno schema di bilanciamento del carico in un sistema distribuito
discutendo:
a. L’obbiettivo dell’utente e/o del sistema.
b. Le categorie a cui il metodo può essere applicato.
c. Come misurare il carico e con quale precisione.
d. Come monitorare il carico e scegliere un nuovo processo.
4. Descrivere e discutere l’algoritmo del servente centrale per la mutua esclusione
in sistemi distribuiti.
a. Adattare poi tale algoritmo per gestire la caduta di un qualsiasi cliente (in
qualsiasi stato) assumendo che il servente operi correttamente e che vi sia
un rilevatore affidabile di guasti. Discutere se il sistema risultante è
affidabile.
b. Cosa accade se se un cliente che possiede il token è sospettato
erroneamente di essere guasto?
5. Descrivere brevemente e definire un sistema di transazioni distribuite. Assumere
poi che il coordinatore di una transazione cada dopo aver registrato un elemento
della intention list, ma prima di aver registrato la lista dei partecipanti o inviato
la CanCommit? Descrivere come i partecipanti possono risolvere la situazione.
Cosa dovrà fare il coordinatore quando viene ripristinato? Conviene registrare la
lista dei partecipanti prima della intention list?
UNIVERSITA' CA' FOSCARI DI VENEZIA
CORSO DI LAUREA IN INFORMATICA
A.A. 2002/2003
Sistemi Distribuiti
Compito – 16/9/2003
1. Descrivere in dettaglio il meccanismo di comunicazione nel modello cliente
servente e le tecniche di indirizzamento, indicando le componenti architetturali e
la successione di azioni. Mostrare inoltre un esempio.
2. Illustrare i diversi tipi di architettura per threading del server in sistemi
distribuiti. Mostrare degli esempi.
3. Definire i tipi di sincronizzazione fra orologi in sistemi distribuiti. Dare un
esempio di algoritmo di sincronizzazione di orologi.
4. Descrivere l’algoritmo di ordinamento circolare per l’elezione in sistemi
distributi in forma algoritmica. Discuterne le condizioni, la complessità
computazionale e i vantaggi e limiti.
5. Illustrare il metodo di controllo della concorrenza di transazioni basato su
timestamp. Discuterne vantaggi e limiti. Mostrare un esempio.
UNIVERSITA' CA' FOSCARI DI VENEZIA
CORSO DI LAUREA IN INFORMATICA
A.A. 2002/2003
SISTEMI DISTRIBUITI
Compito – 2/7/2003
_______________________________________________________________
1. Descrivere il meccanismo di esecuzione di una chiamata di procedura remota, fra oggetti
distribuiti illustrando la struttura architetturale. Discutere i tipi di passaggio dei parametri.
Mostrare un esempio.
2. Cosa si intende per lightweight remote procedure call? Descrivere in dettaglio e illustrare
con un esempio.
3. Definire l’equivalenza seriale di transazioni. Illustrare un esempio di transazioni
serialmente equivalenti ed un esempio di transazioni non serialmente equivalenti.
4. Cosa si intende per algoritmo di snapshot in sistemi distribuiti? Discutere e illustrare con
un esempio.
5. Descrivere l’algoritmo di bully per l’elezione in sistemi distribuiti in forma algoritmica.
Discuterne le condizioni, a complessità computazionale e i vantaggi e limiti.
_______________________________________________________________
UNIVERSITA' CA' FOSCARI DI VENEZIA
CORSO DI LAUREA IN INFORMATICA
A.A. 2002/2003
SISTEMI DISTRIBUITI
Compito – 18/6/2003
_______________________________________________________________
1. Descrivere i tipi di primitive di comunicazione in sistemi distribuiti e per ogni tipo indicarne
vantaggi e svantaggi.
2. Illustrare il paradigma publish-subrcribe. Discutere i vari tipi di notifica e illustrare con un
esempio.
3. a) Quali sono le condizioni e proprietà delle transazioni?
b) Cosa sono i problemi di lost update e di inconsistent retrival per le transazioni? Illustrare i
due tipi di problemi con un esempio e discuterne come risolverli.
4. a) Quali sono le caratteristiche dello scheduling di processi in sistemi distribuiti? Discutere le
alternative di progetto e i relativi vantaggi e svantaggi.
b) Descrivere un algoritmo di scheduling in sistemi distribuiti illustrandone le caratteristiche,
vantaggi e limiti.
5. Descrivere l‚algoritmo di Maekawa per la mutua esclusione in forma algoritmica. Discuterne la
complessità computazionale e i vantaggi e limiti.
_______________________________________________________________
UNIVERSITA' CA' FOSCARI DI VENEZIA
CORSO DI LAUREA IN INFORMATICA
A.A. 2002/2003
SISTEMI DISTRIBUITI
Compito - 4/2/2003
_______________________________________________________________
1. Illustrare il modello architetturale per la gestione di dati replicati di tipo gossip, descrivendo le componenti
del sistema e le loro interazioni.
Mostrare poi in particolare la struttura del Replica Manager e i principali elementi di stato, descrivendone il
flusso dell'informazione nella realizzazione del servizio.
2. Quali sono le condizioni richieste per la mutua esclusione distribuita di un insieme di risorse?
Descrive l'algoritmo distribuito di Ricart-Agrawala e darne la forma algoritmica. Discuterne la complessità
computazionale, i pregi e limiti.
3. Classificare gli algoritmi di allocazione di processi in sistemi distribuiti, esemplificando ogni categoria.
Descrivere poi in dettaglio un algoritmo di allocazione
4. Definire un Network Operating System, un Distributed Operating System e un Multiprocessor Operating
System. Discuterne i relativi vantaggi e limiti e i campi di applicazione.
_______________________________________________________________
SISTEMI DISTRIBUITI
A.A. 2001/2002 - Compito - 18/9/2002
_____________________________________________________________________
1. Discutere i problemi aperti nella progettazione dei sistemi distribuiti.
Per due specifici aspetti dare degli esempi di problemi di progettazione con riferimento a sistemi
wireless.
2. Definire un modello orientato ad oggetti; definire riferimenti, interfacce e metodi . Definire e descrivere i
diversi tipi di semantica di invocazione di una RPC.
3. Discutere il problema della mutua esclusione in ambito distribuito ed in particolare:
- elencare le proprietà richieste
- indicare quali sono gli algoritmi adottati e le loro caratteristiche
- discutere il confronto dei diversi algoritmi considerando vari fattori quali complessità, tolleranza ai guasti
e ritardo.
4. Presentare l'algoritmo di Cristian, spiegarne obbiettivi, illustrarne il funzionamento e discuterne i limiti e
vantaggi.
5. Cosa caratterizza il file system CODA rispetto ad altri tipi di file system quali AFS e NFS? Discuterne i
vantaggi e limiti.
_____________________________________________________________________
SISTEMI DISTRIBUITI
A.A. 2001/2002 - Compito - 25/6/2002
_____________________________________________________________________
1. (a) Descrivere il protocollo two-phase commit in un sistema distribuito, indicando per quali scopi si
applica.
(b) Discuterne vantaggi e limiti. Definirne la complessità.
(c) Discutere l'applicazione nel caso di annidamento.
2. (a) Quali sono i possibili eventi di guasto durante una RPC?
(b) Come possono essere gestiti i diversi tipi di guasto anche in relazione alla semantica della RPC?
3. (a) Descrivere un modello architetturale per la gestione dei dati replicati.
(b) In accordo al modello scelto schematizzare i passi di gestione di una richiesta su un sistema di
replicazione
(c) Indicare le differenze fra il modello scelto e altri modelli architetturali e illustrare vantaggi e limiti di
ognuno.
4. Descrivere il funzionamento del Logical Clock, spiegando brevemente in che modo viene utilizzato per
risolvere il problema dovuto all'assenza di un orologio globale in un sistema distribuito asincrono.
5. (a) Descrivere in dettaglio quali passi devono essere seguiti per la creazione di un processo,
considerando le diverse possibilità di progetto per multi-thread.
(b) Descrivere la tecnica del copy-on-write e discuterne motivazioni, vantaggi e limiti.
_____________________________________________________________________
SISTEMI DISTRIBUITI
A.A. 2001/2002 - Compito - 4/6/2002
_____________________________________________________________________
1. (a) Descrivere un algoritmo di elezione in un sistema distribuito.
(b) Illustrarne i vantaggi e gli svantaggi. Definire la complessità dell'algoritmo.
(c) Dare un esempio di applicazione.
2. (a) In cosa consiste un servizio di notifica?
(b) Definire uno progetto per un servizio di notifica che utilizzi una mailbox per gestire le richieste di un
insieme di subscriber che possono specificare quando richiedono la consegna delle notifiche.
(c)Spiegare come progettare l'utilizzo di tale sistema da parte di subscriber che possono essere non
sempre attivi. Spiegare inoltre come gestire i crash dei subscriber.
3. Confrontare le architetture worker-pool multi threading e thread-per-request illustrandone i relativi
vantaggi e svantaggi.
4. Si consideri la computazione distribuita illustrata nel seguente diagramma spazio-temporale
P1
P2
P3
Si assegni a ciascun evento un valore del Logical Clock corrispondente.
5. I File System distribuiti possono essere classificati in quattro differenti livelli:
1. File System per sistemi Monoutente, Monoprogrammati
2. File System per sistemi Monoutente, Multiprogrammati
3. File System per sistemi Multiutente, Multiprogrammati
4. File System per sistemi distribuiti
Per ciascun livello dire quali sono i servizi principali che un File System deve fornire.
_____________________________________________________________________