Determinare se un oggetto in un sistema distribuito è “garbage”
Occorre determinare il numero totale di reference ad un oggetto esistenti nel sistema.
Bisogna prestare attenzione allo stato dei canali, che potrebbero contenere delle reference in trasmissione.
Si suppone che lo scambio di messaggi nel sistema sia affidabile, cioè i messaggi sono consegnati:
Stati tipicamente attraversati da un oggetto nell’intervallo tra la sua allocazione e la restituzione delle risorse allocate al sistema
Si occupano della deallocazione degli oggetti inaccessibili.
Un oggetto si dice inaccessibile se non esiste alcuna reference all’oggetto stesso.
Semplificano la programmazione e riducono notevolmente il rischio di memory leak (con un overhead più o meno trascurabile).
Algoritmi di Garbage Collection:
Più complessa della Garbage Collection in sistemi centralizzati: bisogna tener traccia in maniera consistente delle variazioni nelle references, anche in caso di failures nei processi o nei canali di comunicazione.
Un Garbage Collector Distribuito (DGC) dovrebbe essere in grado di gestire la deallocazione di tutti i tipi di strutture dati, garantendo comunque efficienza, scalabilità, tolleranza ai guasti.
Le tecniche di DGC esistenti risolvono solo in parte questi problemi: ad esempio il tracing richiede costosi meccanismi per l’individuazione delle references inaccessibili, mentre il reference counting soffre la perdita dei messaggi.
Ogni processo ha un contatore delle reference ad ogni oggetto nel sistema distribuito.
Ricostruendo lo stato globale:
così da distinguere gli oggetti inaccessibili dagli oggetti in uso.
Per determinare lo stato globale del sistema è possibile utilizzare l’algoritmo Snapshot di Chandy-Lamport.
Per ogni processo può esistere al più un oggetto remotamente invocabile.
I processi non sono soggetti a failures.
Lo scambio di messaggi nel sistema è affidabile, cioè i messaggi sono consegnati:
Un oggetto per ogni processo
Processi completamente connessi [n*(n-1) canali]
Stato locale di ogni processo: {RL,R1,R2,R3}
Messaggi:
Il processo Pi avvia lo snapshot distribuito
Stato locale non ancora registrato
Il processo Pj riceve un MARKER da Pi
Stato locale registrato
Il processo Pj riceve un MARKER da Pk
Il processo Pi riceve un messaggio PSTATE da Pj
Dallo stato globale, per ogni oggetto Oj si ricava:
Il numero di reference esistenti
refs(Oj);
Il numero di reference granted
grantedRefs(Oj)
(messaggi NEWREF(Pj) registrati sui canali);
Il numero di reference asked
askedRefs(Oj)
(messaggi ASKREF a Pj o DUPREF(Pj) registrati sui canali).
(refs(Oj) + grantedRefs(Oj) + askedRefs(Oj) )=0 → Oj è “garbage”
Scarica il codice DAJ.
1. Caratterizzazione dei sistemi distribuiti
2. Modelli di sistemi distribuiti
3. Tempo e sincronizzazione nei Sistemi Distribuiti
4. Stato globale nei Sistemi Distribuiti
5. Problemi di consenso nei sistemi distribuiti
7. Algoritmi di mutua esclusione nei sistemi distribuiti
8. Algoritmi di elezione nei sistemi distribuiti
10. Il Network File System di SUN Microsystems
11. AFS (Andrew File System) e GFS (Google File System)
12. Transazioni e controllo di concorrenza
13. Transazioni
15. Affidabilità (dependability) dei sistemi software distribuiti
16. Affidabilità dei sistemi software distribuiti
17. Software Faults
18. Classificazione e analisi dei difetti software