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 » 22.Esercitazione - La Memoria Stabile


Sommario

  • Definizione di memoria stabile
  • Operazioni sulla memoria stabile
  • Tipologie di guasti e meccanismi di detection
  • Eliminazione dei guasti transitori
  • Eliminazione dei guasti permamenti

Memoria stabile

Si definisce stabile una memoria non soggetta a malfunzionamenti, tale che le informazioni in essa residenti non vengano perdute e non siano alterate in seguito alla caduta dell’elaboratore.

Si tratta di un’astrazione: nessuna memoria reale permamente possiede le proprietà della memoria stabile.
Tuttavia, utilizzando opportune tecniche di ridondanza, è possibile realizzare memorie che approssimano tale astrazione al livello desiderato:

  • Codici di ridondanza ciclici per i singoli dati scritti
  • Duplicazione su più dispositivi di memorizzazione

Operazioni sulla memoria stabile

Sulla memoria stabile sono definite le operazioni di lettura e scrittura: stable_read e stable_write

 

Affinchè la memoria stabile possa godere di queste caratteristiche tali operazioni devono essere atomiche, nel senso che terminano con successo, oppure lasciano lo stato della memoria inalterato, come se non fossero mai state eseguite.

Guasti e tecniche di rilevazione

Guasti temporanei

In lettura
Sono rilevati con l’utilizzo di codici di ridondanza ciclici (CRC).
Possono essere eliminati rileggendo le informazioni desiderate. Data la natura temporanea del guasto, le informazioni corrette possono sempre essere ottenute con numero finito di letture.

 

In scrittura
Sono rilevati rileggendo le informazioni appena scritte e confrontandole con quelle originali.
Possono essere eliminati riscrivendo le informazioni. Data la natura temporanea del guasto, le informazioni corrette possono sempre essere memorizzate con un numero finito di scritture.

Guasti e tecniche di rilevazione

Guasti permanenti

Sono dovuti a malfunzionamenti hardware. Possono essere dovuti a:

  • Caduta dell’elaboratore durante una scrittura
  • Alterazione di informazioni a causa di disturbi esterni o malfunzionamenti dell’hardware

Possono essere rilevati esclusivamente in fase di lettura.
Se il controllo del codice di ridondanza fallisce ripetutamente, allora il guasto non è di natura transitoria (si fissa un threshold di letture MAX_TRIALS).

Eliminazione dei guasti transitori

Disco reale: Rappresentato come un tipo di dato astratto costituito da un vettore di pagine (ognuna costituita da un array di byte), che supporta due operazioni: read e write. In particolare l’operazione read può terminare correttamente, o, in caso di errore, sollevare l’eccezione read_error.

Mostra codice

Disco permanente: Rappresentato da un tipo di dato astratto derivato dal disco reale, specializzato in maniera tale da realizzare una memoria priva di qualunque malfunzionamento temporaneo, ridefinendo opportunamente le operazioni read e write in maniera tale da renderle permamenti.

Mostra codice

Letture e scritture permanenti

Lettura permanente (priva di errori temporanei)
L’operazione di lettura viene ripetuta al più MAX_TRIALS volte, fin quando il controllo di ridondanza ciclico non è soddisfatto.

Mostra codice

Dove

buffer=super.read(p);

indica il controllo del codice di ridondanza viene effettuato nel metodo read della classe Disk.

return buffer;
indica lettura riuscita.

if (i==MAX_TRIALS-1)
indica lettura non riuscita. Se è stata superata la soglia massima di tentativi viene sollevata un’eccezione che indica una condizione di errore permanente.

Letture e scritture permanenti

Scrittura permanente (priva di errori temporanei)

I dati sono riletti dopo la scrittura, che risulta corretta solo se i dati riletti coincidono a quelli scritti.

Mostra codice

Dove

if (dataCompare(data,tmpBuffer)

indica Verifica della correttezza della scrittura.

correct=true;

indica scrittura riuscita.

throw PermanentError;
indica scrittura fallita a causa di un errore permanente.

Eliminazione dei guasti permanenti

Si fa ricorso all’astrazione di memoria stabile, costituita da un array di dischi permamenti. Una pagina stabile è costituita da un n-pla di pagine, una per ogni disco permanente.

Si ipotizza che le diverse copie che individuano una pagina non vengano alterate tutte dallo stesso malfunzionamento, che esista sempre almeno una pagina memorizzata correttamente e che non si verifichino malfunzionamenti tali da far fallire il controllo del CRC.

NB: Se il nodo cade esattamente tra due scritture, tutte le copie avranno dati integri, ma differenti tra loro. Si assume come valore corretto il dato del primo disco corretto dal punto di vista del CRC.

La memoria stabile può essere rappresentata da un tipo astratto monitor, al fine di garantire l’atomicità delle operazioni. Il monitor assicura la serializzabilità delle operazioni atomiche.

Sulla memoria stabile sono definite le operazioni:

  • stableRead: Lettura stabile
  • stableWrite: Scrittura stabile
  • reset: Inizializzazione di una pagina stabile con il valore corretto

Eliminazione dei guasti permanenti

Mostra codice

Dove

buffer=disks[count].read(p);

indica Lettura da disco permanente.

count++;

indica Lettura fallita. Si passa al prossimo disco permanente.

//Gestione evento non possibile nel modello

indica che si è ipotizzato che almeno un disco conservi una copia esatta dei dati.

Eliminazione dei guasti permanenti

//scrittura stabile – input: pagina,dati
public void stableWrite(long p,byte data[]) {
for (int i=0;i

disks[i].write(data);
}
Scrittura su disco permanente. In caso di caduta dell’elaboratore durante una write, viene alterata una sola copia della pagina, ma rimangono valide le altre.
In caso di caduta del nodo tra due scritture, i dati di tutte le pagine risulteranno integri, ma potranno essere differenti. Si usa il reset() per ristabilire l’invariante del TDA memoria stabile.

Eliminazione dei guasti permanenti

//reinizializzazione di tutte le copie di una pagina al valore corretto
public void reset(long p) {
byte buff[][]=new byte[NDISKS][BLOCK_SIZE];
for (int i=0;i<NDISKS;i++)
buff[i]=verifyRead(p,i);
for (int k=0;k<NDISKS-1;k++)
     if (!dataCompare(buff[k],buff[k+1]))
disks[k+1].write(p,buff[k]);
 }
Confronta i dati scritti sull’i-esimo disco con i dati scritti sugli altri dischi ed in caso di discrepanze o valori alterati apporta le opportune correzioni.

Eliminazione dei guasti permanenti

Mostra codice

Dove

return tmpBuffer;

indica che il dato scritto nell’i-esimo disco è corretto.

 

tmpBuffer=disks[j].read(p);
disks[i].write(p,tmpBuffer);
return tmpBuffer;

} catch (permanentError ex) {
//passa al prossimo disco
}

Indica che il dato scritto nell’i-esimo disco non è corretto. Si individua un disco j contenente il dato corretto e lo si scrive nel disco i-simo.

I materiali di supporto della lezione

Ancilotti, Boari: Principi di programmazione Concorrente

  • 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