Vai alla Home Page About me Courseware Federica Living Library Federica Federica Podstudio Virtual Campus 3D Le Miniguide all'orientamento Gli eBook di Federica La Corte in Rete
 
I corsi di Ingegneria
 
Il Corso Le lezioni del Corso La Cattedra
 
Materiali di approfondimento Risorse Web Il Podcast di questa lezione

Stefano Russo » 25.Esercitazione - Distributed Garbage Collection


Sommario

  • Descrizione del problema
  • Garbage Collectors
  • Garbage Collectors distribuiti
  • References remote
  • Possibile soluzione
  • Modello del sistema
  • Descrizione dell’algoritmo

Descrizione del problema

Determinare se un oggetto in un sistema distribuito è “garbage”

  • non esistono riferimenti ad esso nell’intero sistema.

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.

Assunzioni

Si suppone che lo scambio di messaggi nel sistema sia affidabile, cioè i messaggi sono consegnati:

  • certamente (prima o poi)
  • inalterati
  • una e una sola volta (nessuna duplicazione)
  • nell’ordine di spedizione (per canale –> canali FIFO)

Ciclo di vita di un oggetto

Stati tipicamente attraversati da un oggetto nell’intervallo tra la sua allocazione e la restituzione delle risorse allocate al sistema

Stati tipicamente attraversati da un oggetto nell’intervallo tra la sua allocazione e la restituzione delle risorse allocate al sistema


Garbage Collector

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:

  • Reference Counting
  • Mark and Sweep
  • Copying
  • Mark and Compact

Distributed 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.

References Remote

Creazione di una reference

Creazione di una reference


References Remote

Duplicazione di una Reference

Duplicazione di una Reference


Distributed Reference Counting

Ogni processo ha un contatore delle reference ad ogni oggetto nel sistema distribuito.

Ricostruendo lo stato globale:

  • dalle Informazioni sullo stato locale si può calcolare il numero totale di reference per ogni oggetto nel sistema distribuito
  • dallo stato dei canali tra i processi (messaggi in circolazione) è possibile dedurre:
    • il numero di reference per ogni oggetto che è stato richiesto (ASKREF o DUPREF) ma non ancora attribuito
    • il numero di reference per ogni oggetto che è stato attributo (Reference Inviata) ma non ancora registrato
  • in tal modo per ogni oggetto è possibile determinare:
    • quante reference attualmente esistono nel sistema distribuito e
    • quante reference stanno per essere create

così da distinguere gli oggetti inaccessibili dagli oggetti in uso.

Distributed Snapshot

Per determinare lo stato globale del sistema è possibile utilizzare l’algoritmo Snapshot di Chandy-Lamport.

Assunzioni

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:

  • certamente (prima o poi)
  • inalterati
  • una e una sola volta (nessuna duplicazione)
  • nell’ordine di spedizione (per canale –> canali FIFO)

Descrizione del sistema

Un oggetto per ogni processo
Processi completamente connessi [n*(n-1) canali]
Stato locale di ogni processo: {RL,R1,R2,R3}

  • RL: references all’oggetto locale
  • RX: references agli oggetti remoti

Messaggi:

  • ASKREF – Inviato dal processo Pi al processo Pj per richiedere una nuova reference all’oggetto del processo Pj
  • DUPREF(Px) – Inviato dal processo Pi al processo Pj per richiedere la duplicazione di una reference all’oggetto del processo Px
  • NEWREF(Px) – Inviato dal processo Pi al processo Pj per inviare (comunicare la creazione de) la reference all’oggetto del processo Px

Algoritmo – Avvio dello snapshot

Il processo Pi avvia lo snapshot distribuito

  • Blocca i canali in uscita
  • Registra il proprio stato locale (numero di references a Ox con x ∈ [1,4]
  • Avvia la registrazione dei messaggi sui canali in ingresso
  • Invia un marker su ogni canale in uscita
  • Sblocca i canali in uscita

Algoritmo – Ricezione di un marker

Stato locale non ancora registrato

Il processo Pj riceve un MARKER da Pi

  • Blocca i canali in uscita
  • Registra il proprio stato locale (numero di references a Ox con x ∈ [1,4]
  • Registra lo stato del canale Cij (sul quale è stato ricevuto il marker) come vuoto
  • Avvia la registrazione dei messaggi sui canali in ingresso
  • Invia un marker su ogni canale in uscita
  • Sblocca i canali in uscita

Algoritmo – Ricezione di un marker

Stato locale registrato
Il processo Pj riceve un MARKER da Pk

  • Chiude la registrazione sul canale Ckj
  • Determina lo stato del canale
  • Se lo stato di tutti i canali in ingresso è stato registrato, la parte di snapshot competente Pj è ultimata
  • La porzione di stato viene inviata al processo che ha iniziato lo snapshot (Pi)

Algoritmo – Ricezione stato

Il processo Pi riceve un messaggio PSTATE da Pj

  • Aggiorna il numero di references per ogni oggetto refsOi(Pi)=refsOi(Pi)+refsOi(Pj) con i ∈ [1,4]
  • Annota lo stato dei canali in ingresso del processo Pj : Cij, Ckj, Clj
  • Quando Pi ha ricevuto i messaggi PSTATE da tutti gli altri processi, lo stato globale del sistema distribuito è disponibile a Pi.

Algoritmo – Collection

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”


Codice

Scarica il codice DAJ.

I materiali di supporto della lezione

Codice DAJ

  • Contenuti protetti da Creative Commons
  • Feed RSS
  • Condividi su FriendFeed
  • Condividi su Facebook
  • Segnala su Twitter
  • Condividi su LinkedIn
Progetto "Campus Virtuale" dell'Università degli Studi di Napoli Federico II, realizzato con il cofinanziamento dell'Unione europea. Asse V - Società dell'informazione - Obiettivo Operativo 5.1 e-Government ed e-Inclusion