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:
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 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 permanenti
Sono dovuti a malfunzionamenti hardware. Possono essere dovuti a:
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).
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 codiceDisco 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 codiceLettura 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.
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.
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 codiceDove
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.
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:
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.
//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.
//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.
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.
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
Ancilotti, Boari: Principi di programmazione Concorrente