Sistemi affidabili e/o altamente disponibili

Sistemi affidabili e/o altamente disponibili

1. Introduzione

2. Attributi della dependability

3. Applicazioni con requisiti di dependability 4. Descrizione degli impedimenti

5. Strumenti per la dependability (la tolleranza dei guasti)

(parte dei lucidi sono stati gentilmente concessi da Laprie e Kanoun – CNRS Toulose, Francia)

FAILURES IMPAIRMENTS

FAULTS ERRORS AVAILABILITY

ATTRIBUTES SAFETY

CONFIDENTIALITY INTEGRITY

MAINTAINABILITY RELIABILITY

Property of a computer system such that reliance can justifiably be

placed on the service it delivers

DEPENDABILITY MEANS

FAULT PREVENTION

FAULT REMOVAL FAULT FORECASTING

FAULT TOLERANCE: providing a service implementing the system function in spite of faults

Introduzione

Error: Reference source not found

Attributi della dependability

Affidabilità

L'affidabilità è una funzione del tempo R(t) definita come la probabilità che il sistema non mostri malfunzionamenti in un

intervallo temporale a condizione che nessun malfunzionamento esisteva all'inizio dell'intervallo.

Disponibilità

La disponibilità è una funzione del tempo A(t) definita come la probabilità che il sistema non mostri malfunzionamenti nell'istante in cui gli è richiesto di operare.

Si differenzia dall'affidabilità poiché quest'ultima è una misura di corretto funzionamento in un intervallo, mentre la disponibilità è una misura di corretto funzionamento ad un dato istante temporale.

Un sistema può essere altamente disponibile nonostante esso mostri frequenti, ma molto brevi, periodi di malfunzionamento.

Sicurezza

La sicurezza è la probabilità S(t) che il sistema non mostri malfunzionamenti nell'istante in cui gli è richiesto di operare, oppure che, anche se esso mostra un malfunzionamento, questo non comprometta la sicurezza di persone o impianti relazionati al sistema stesso.

E’ una misura sia della capacità del sistema di funzionare correttamente che della capacità di non provvedere correttamente alle sue funzionalità ma senza generare conseguenze rilevanti.

E' da notare che la sicurezza differisce dall'affidabilità e dalla disponibilità, poiché queste ultime sono misure relative al corretto funzionamento e non includono effetti derivanti da malfunzionamenti^.

Performability

La performability è una funzione del tempo P(L,t) definita come la probabilità che il valore della quantità di “servizi” forniti dal sistema fino all’istante t sia almeno pari ad L.

E’ una misura della capacità del sistema di fornire una determinata quantità di lavoro in un intervallo di tempo, anche in presenza di guasti.

Mantenibilità

La mantenibilità è la probabilità M(t) che il sistema malfunzionante possa essere riportato al suo corretto funzionamento entro il periodo t.

E’ una misura della facilità con la quale un sistema può essere riparato una volta manifestatosi il malfunzionamento.

Essa è strettamente correlata con la disponibilità poiché tanto più è breve l'intervallo di ripristino del corretto funzionamento, tanto più elevata sarà la probabilità di trovare il sistema funzionante ad un dato istante temporale. Per il valore estremo M(0) = 1.0, il sistema in oggetto sarà sempre disponibile.

Collaudabilità

La collaudabilità è semplicemente una misura di quanto un sistema rende facile ad un operatore verificare alcuni suoi attributi.

E' chiaramente legata alla mantenibilità poiché più facilmente è possibile collaudare un sistema malfunzionante per individuare il componente guasto, più breve sarà l'eventuale intervallo di ripristino del corretto funzionamento.

Applicazioni con requisiti di dependability

Applicazioni di lunga durata

 Applicazioni che devono rimanere attive per intervalli temporali molto lunghi

 Esempi: sistemi di elaborazione per il controllo di sistemi satellitari.

 Requisiti: rimanere operanti senza manifestare malfunzionamenti per periodi di decine di anni con probabilità pari, o addirittura superiore, a 0.95.

Applicazioni critiche

 Applicazioni in cui malfunzionamenti possono avere delle conseguenze gravi sulla sicurezza di persone, dell'ambiente o di impianti.

 Esempi: controllo del volo di aeroplani, applicazioni militari, di processi industriali (p.e. chimici)

 Requisiti: rimanere operanti senza manifestare malfunzionamenti per periodi di ore o giorni con probabilità vicino all’uno.

Applicazioni poco mantenibili

 Applicazioni in cui le operazioni di manutenzione sono estremamente costose o difficili da apportare.

 Esempi: sistemi di elaborazione in sistemi remoti geograficamente, sistemi di elaborazione e controllo su navicelle spaziali.

 Requisiti: riuscire a rinviare il più possibile la manutenzione garantendo comunque che il sistema funzioni correttamente fino all'istante dell'intervento (se possibile). Durante tale periodo il sistema deve essere in grado di poter gestire il verificarsi di guasti in maniera autonoma.

Applicazioni disponibili

 Applicazioni per le quali gli utenti richiedenti il servizio si aspettano con alta probabilità che il servizio venga realmente fornito all'atto della richiesta.

 Esempi: sistemi di gestione di transazioni bancarie, sistemi per la gestione di servizi anagrafici.

 Requisiti: rendere indisponibili i propri servizi con bassissima probabilità.

adjudged or hypothesized cause of error(s)

IMPAIRMENTS TO DEPENDABILITY

delivered service deviates from

fulfilling the system function FAILURE

part of system state liable

to lead to failure ERROR

FAULT

FAULT

ACTIVATION (INTERNAL) OR OCCURRENCE (EXTERNAL)

ERROR

PROPAGATION

FAILURE

ERROR : FAULT MANIFESTATION IN SYSTEM

FAILURE : ERROR MANIFESTATION UPON SERVICE

Descrizione degli impedimenti

FAULT

PROGRAMMER’S ERROR

IMPAIRED INSTRUCTION(S) OR DATA

ERROR

FAILURE PROPAGATION

WHEN DELIVERED SERVICE DEVIATES (VALUE, DELIVERY INSTANT) FROM FUNCTION FULFILLING

ACTIVATION

FAULTY COMPONENT AND INPUTS

FAULT

SHORT-CIRCUIT IN INTEGRATED CIRCUIT

STUCK-AT CONNECTION, FUNCTION MODIFICATION FAILURE

ERROR

FAILURE PROPAGATION

WHEN DELIVERED SERVICE DEVIATES (VALUE, DELIVERY INSTANT) FROM FUNCTION FULFILLING

ACTIVATION

FAULTY COMPONENT AND INPUTS

OPERATOR ERROR

IMPROPER HUMAN-MACHINE INTERACTION

FAULT

ERROR

WHEN DELIVERED SERVICE DEVIATES (VALUE, DELIVERY INSTANT) FROM FUNCTION FULFILLING

FAILURE PROPAGATION

Error: Reference source not found

Error: Reference source not found

Physical faults

Human-made faults Phenomenological

cause

Accidental faults

Non-malicious intentional faults Malicious faults

Nature

FAULTS Development faults

Operational faults Phase of creation

or occurrence

Internal faults External faults System boundaries

Permanent faults Temporary faults Persistence

SYSTEM BOUNDARIES

internal faults: those parts of the system state which, when invoked by the computation activity, will produce an error

external faults: result from system interference or interaction with its physical (electromagnetic perturbations, radiation, temperature, vibration, etc.) or human environment

TEMPORAL PERSISTENCE

permanent faults: presence is not related to pointwise conditions

temporary faults: present for a limited amount of time internal (computation activity)

external (environment) PHENOMENOLOGICAL CAUSES

physical faults: due to adverse physical phenomena human-made faults: result from human imperfections

NATURE

accidental faults: appear or are created fortuitously

intentional faults: created deliberately, with or without a malicious intention

PHASE OF CREATION WITH RESPECT TO THE SYSTEM'S LIFE

operational faults: appear during the system's exploitation development faults: result from imperfections

during the development of the system (from requirement

specification to implementation) or during subsequent modifications the establishment of the procedures for operating or main taining the system

human-made fault classes

aimed at preserving acceptable performances, at facilitating the system utilization

Intentional, non-malicious, faults

induced by financial considerations

interaction faults: may result from the action of an operator aimed at overcoming an unforeseen situation

deliberately violating an operating procedure without having developed the consciousness of the possibly damaging consequences

realized often they were faults only after an unacceptable system behavior, thus a failure, has occurred

design faults: result generally from tradeoffs

Malicious faults: specific labels design faults: malicious logics

development faults: Trojan horses, logic or timing bombs, trapdoors operational faults: viruses, worms

interaction faults: intrusions

 Human-made interaction faults

result from operators errors

errors: negative side of human activities

positive side: adaptability  aptitude to address unforecasted situations

Consciousness that most interaction faults have their source in the system design

Growing relative importance

Causes of accidents in commercial flights in the USA Accidents per million take-offs

1970-78 1979-86

Technical defects 1,49 (45%) 0,43 (33%)

Weather conditions 0,82 (25%) 0,33 (26%)

Human errors 1,03 (30%) 0,53 (41%)

Total 3,34 1,29

Error: Reference source not found

Error: Reference source not found

System,Technology MTBE for MTFF for MTBE/MTFF all fault classes permanent faults

(h) (h)

PDP-10, ECL 44 800-1600 0,03 - 0,06

CM* LSI-11, NMOS 128 4200 0,03

C.vmp TMR LSI-11, NMOS 97 - 328 4900 0,02 - 0,07

Telettra, TTL 80 - 170 1300 0,06 - 0,13

SUN-2, TTL-MOS 689 6552 0,11

1 Mx37 RAM, MOS 106 1450 0,07

13 stations of CMU Andrew network, 21 stations.years

Number Mean time to manifestations manifestation (h)

Permanent faults 29 6552

Intermitent faults 610 58

Transient faults 446 354

System crashes 298 689

FAULT PATHOLOGY

 active fault produces error(s)

activation of dormant fault by computation process external fault

 error is latent or detected

error propagation other errors

 failure occurs when error "passes through"

system-user interface



fault as viewed by system containing / components interacting with failed component

component failure



FAULT ERROR FAILURE

FAILURE   

…

…

NUMEROUS SYNONYMS FAULT  BUG, DEFECT

FAILURE  MALFUNCTIONING, BREAKDOWN, (SERVICE) OUTAGE LABEL ASSIGNMENT : USAGE

FAILURE RATE

ERROR DETECTION AND CORRECTION FAULT DIAGNOSIS, FAULT TOLERANCE

Strumenti per la dependability

Gli obiettivi della dependability possono essere raggiunti tramite:

 la tolleranza dei guasti (Fault Tolerance – F.T.);

 la rimozione dei guasti;

 la previsione dei guasti.

FAULT TOLERANCE

Error processing: error removal, before failure occurs

Fault treatment: avoiding fault(s) to be activated again

La tolleranza dei guasti (Fault Tolerance)

Error detection

and recovery Fault masking ERROR PROCESSING

Error recovery Error detection

Backward recovery Forward recovery Compensation Error diagnosis







 



 



systematic application even in error absence Error: Reference source not found

FAULT TREATEMENT Fault diagnosis

Fault isolation

determination of error causes

removing faulty components from subsequent execution process

system no longer able to deliver same service

Reconfiguration



Modification of system structure, such that non- failed components deliver degraded service

Error Detection

Forward recovery

Fault Treatment Temporary

physical fault or Design fault

•

Maintenance Call Permanent

physical fault

•

Service Continuation

Error Detection

Compensation

Fault Treatment Temporary

physical fault or Design fault

•

Maintenance Call Permanent

physical fault

•

Service Continuation Error Detection

Backward recovery

Fault Treatment

Maintenance Call

• ^{Temporary physical} _{fault or}

Design fault

Permanent physical

fault

•

Service Continuation

Fault Masking

Compensation

Fault Treatment Temporary

physical fault or Design fault

•

Maintenance Call Permanent

physical fault Error Detection

•

Service Continuation

Error detection and Recovery

REDUNDANCIES

NATURE SYNCHRONIZATION

Action mode

Status of redundant components

Application level (granularity)

Selective (locale) redundancy

Massive (global) redundancy Static

redundancy

Dynamic redundancy

Active (hot) redundancy

Passive (cold) redundancy Semi-active or semi-passive (warm) redundancy

Tight:

synchronous (micro-synchronous) redundancies Weak:

asynchronous (macro-synchronous) redundancies

Error detection and

recovery semi-active, or passive,

dynamic redundancy Error detection and

recovery Active dynamic redundancy

Fault masking Static redundancy

INDEPENDENCY / FAULTS

Replication redundancy

Diversification redundancy

Tipi di ridondanza

 Hardware (moduli o componenti)

 Software

 Dati

 Temporale

Ridondanza a livello hardware

 Ridondanza statica o replicazione passiva o mascheramento dei guasti.

 Ridondanza dinamica

 Ridondanza ibrida

Ridondanza statica

Permette di prevenire che guasti originino errori senza che vi sia alcun intervento esplicito da parte del sistema stesso o di un operatore esterno per quanto riguarda il rivelamento del guasto ed una eventuale riconfigurazione.

Triple Modular Redundancy (TMR)

In questo tipo di schema, vengono mascherati guasti a livello dei componenti, ma non eventuali guasti a livello del voter, per il quale non vi è alcuna ridondanza^.

Se il voter è soggetto a guasto allora il suo valore di output potrebbe essere scorretto ed originare quindi errori e poi malfunzionamenti. Per questo tipo di schema, l'affidabilità dell'intero sistema non può mai essere superiore all'affidabilità del voter. Dato un sistema, ogni singolo componente il cui guasto può dar luogo a malfunzionamento del sistema stesso viene denominato singolo punto di fallimento.

Una tecnica classica per prevenire che il voter diventi un singolo punto di fallimento è quella di replicarlo^.

Fig. Esempio di replicazione di processore, memoria e voter.

Fig. Esempio di voter implementato via software

N-modular redundancy (NMR)

Una generalizzazione dell'approccio TMR è la cosiddetta ridondanza ad N moduli (N-modular redundancy - NMR), la quale differisce da TMR nel fatto che il componente in oggetto viene replicato N volte, con N possibilmente maggiore di 3. Il vantaggio di utilizzare N > 3 moduli risiede nel fatto che più di un singolo guasto può essere tollerato.

Ad esempio, il voto di maggioranza permette ad un sistema di tipo 5MR di tollerare il guasto di un massimo di due componenti.

Ovviamente lo svantaggio sarà associato al maggiore costo dovuto al più alto numero di copie del modulo per cui si adotta la ridondanza.

Ridondanza attiva

E' da notare che in questo caso non c'è alcun tentativo di prevenzione affinché guasti non diano origine ad errori ed a malfunzionamenti, ma esistono solo azioni di rimedio per riportare il sistema al corretto funzionamento.

Quindi tale tipo di ridondanza risulterà più appropriata per tutte quelle applicazioni in cui la presenza, se pur temporanea, di errori e malfunzionamenti è accettabile.

Fig. Diagramma a stati per la ridondanza attiva.

Esempi di ridondanza attiva

Una forma particolare di ridondanza attiva è la cosiddetta riserva fredda, in cui per ogni modulo soggetto a ridondanza esiste una sua copia non attiva, che viene attivata in caso di guasto della copia originale, da cui il nome di riserva fredda. In tal caso, la riconfigurazione ha lo scopo di sostituire la copia originale con la riserva fredda. E' da notare che, durante il periodo di riconfigurazione necessario all'attivazione della riserva, la funzionalità del sistema viene interrotta. Per minimizzare la durata di questo periodo è possibile utilizzare riserve calde, che a differenza di quelle fredde, sono attive contemporaneamente al modulo per cui fungono da ridondanza. Lo svantaggio principale è che queste riserve consumano costantemente energia per rimanere attive, anche quando non forniscono reali servizi.

Figura 6.2 e 6.3 del manuale di informatica III edizione

Ridondanza ibrida

Infine, un terzo approccio classico alla ridondanza hardware, denominato ridondanza ibrida, combina le caratteristiche salienti delle due soluzioni precedenti. In particolare, in questa soluzione viene adottata sia una tecnica di mascheramento dei guasti per prevenire gli errori, sia una tecnica di diagnosi dei guasti stessi con relative azioni di riconfigurazione per isolare il componente guasto. In generale la ridondanza ibrida è implementata tramite una combinazione di ridondanza NMR in cui sono presenti anche riserve (fredde o calde). Le riserve subentreranno ad eventuali componenti guasti facenti parte dell' insieme originale di N repliche^.

 Implicit, but frequent, assumption in most fault-tolerant distributed systems

 Implies self-checking processors

 Induced simplifications:

1) Only correct value messages are sent

 minimum number of processors for consensus in presence of t faults: n t+2  2) Error detection: halting detection by interrogating and waiting

3) Resource replication for tolerating t faults ("halts"): t+1 

4) Communication network saturation by “babbling” is impossible 5) Network architecture:

Fail-silent processors Protocol hierarchy according to relation

"uses the service of"

Group membership Atomic broadcast Clock synchronisation

Common mechanism:

consensus

Fault assumption



Distributed system: set of processors (processing and/or storage elements) communicating by messages via communication network

Communication network

Processor Processor Processor Processor Processor

Ridondanza attiva nei sistemi distribuiti

Error: Reference source not found

Propagazione degli errori nei sistemi distribuiti

Peculiarità dei sistemi distribuiti: stato dell’esecuzione distribuito tra vari nodi di elaborazione. Ciò implica che in caso di rivelazione di un guasto gli errori si possono essere estesi anche nei nodi sani.

Fig. Esempio di propagazione d'errore in sistemi distribuiti.

Effetto-domino: provoca il ripristino dello stato di ciascun nodo al proprio valore iniziale, perdendo quindi tutti i risultati della computazione prodotti fino alla rivelazione dell'errore.

L'effetto-domino trae origine dal fatto che esistono delle dipendenze tra i checkpoint dei singoli nodi dovute allo scambio di informazione trasportata dai messaggi

Per evitare l’effetto domino è necessario coordinare l’inserzione dei checkpoint

Il coordinamento può essere:

predefinito, dinamico.

Il coordinamento predefinito previene la dipendenza tra i checkpoint

Caratteristiche:

 semplice da implementare,

 numero di checkpoint notevole (molti checkpoint inutili)

Il coordinamento dinamico evita la dipendenza tra i checkpoint cercando di minimizzare il numero di inserzioni.

Caratteristiche:

 implementazione un po’ complicata,

 overhead variabile.

Esempio di coordinamento predefinito

Uno dei coordinamenti predefiniti più semplice è quello in cui viene inserito un checkpoint prima dell’esecuzione di ogni primitiva di ricezione. In questo modo nel caso in cui viene annullato un messaggio per un recovery il processo destinatario viene ripristinato nello stato che aveva prima della ricezione dello stesso. In questo modo si minimizza il processamento da annullare in ogni singolo processo interessato ad un recovery e si evita la propagazione del recovery in altri processi non direttamente destinatari del processo che ha iniziato il recovery.

Esempio di coordinamento dinamico

Un algoritmo distribuito di coordinamento dinamico molto semplice è il seguente: ciascun nodo mantiene una variabile locale denominata timestamp il cui valore iniziale è zero; il valore di questa variabile viene incrementato di uno ogni volta che il nodo decide di prendere un checkpoint; tale valore viene aggiunto come informazione di controllo su ciascun messaggio spedito; quando viene ricevuto un messaggio con informazione di controllo associata ad un valore superiore al timestamp locale del nodo ricevente, allora prima di processare il messaggio viene preso un checkpoint e viene portato il valore del timestamp locale al valore dell'informazione di controllo.

Fig. - Un esempio di coordinamento tramite timestamp.

Il nodo A prende il checkpoint X e porta il suo timestamp al valore 2; questo valore viene poi aggiunto sul messaggio m.

Quando il nodo B riceve m si accorge che il suo timestamp è inferiore a 2; questo induce B a prendere il checkpoint Y prima di processare m. In questo modo non esistono dipendenze tra X ed Y, quindi questi due checkpoint possono essere usati in un recupero all'indietro senza rischio di effetto-domino.

Ridondanza a livello software

Controllo della consistenza: consiste nell'utilizzo di conoscenza a priori delle caratteristiche dell'informazione che viene gestita dall'applicazione al fine di rivelare eventuali guasti/errori/malfunzionamenti.

Esempio: è noto a priori che il valore di un determinato parametro non possa mai superare una data soglia. Se questo accade allora vi è un problema in qualche componente del sistema.

Controllo di capacità: consiste nel collaudare durante la vita operativa i singoli componenti hardware del sistema per verificarne il corretto funzionamento.

Esempio: test che si effettua sulle ALU. Consiste nel fare eseguire alla ALU specifiche istruzioni (addizioni, moltiplicazioni, operazioni logiche e trasferimento) su particolari dati e si compara poi il risultato con valori noti memorizzati per esempio in una memoria a sola lettura (ROM.

Le tecniche di ridondanza software considerate utilizzano moduli aggiuntivi per effettuare il controllo di consistenza/capacità. Non permettono di scoprire e possibilmente tollerare guasti che possono coinvolgere il software stesso. A differenza dell'hardware, il software non si "rompe", ciò che invece può accadere è che si manifestino guasti originati da progetti software non corretti oppure anche da errori nel processo di codifica degli algoritmi. Quindi ogni tecnica che cerca di scoprire guasti nel software di fatto cerca di scoprire imperfezioni nel processo di progetto o di codifica.

Design diversity:

 N-self-checking programs;

 N version programming;

 Recovery blocks.

N self-checking programs – NSCP (N programmi autocontrollanti)

Ci sono N versioni distinte dello stesso software. Ciascuna di esse contenente i propri test di accettazione, i quali non sono altro che azioni di controllo sui risultati prodotti dal programma. Viene poi utilizzato un modulo che implementa una data logica di selezione per prelevare i risultati prodotti da uno dei programmi in cui tutti i test di accettazione hanno avuto esito positivo.

Supponendo, come sia ragionevole, che i possibili guasti in una delle versioni non siano correlati con quelli delle altre, e che gli errori da loro generati siano scoperti tramite i test di accettazione, allora la tecnica NSCP può tollerare fino ad un massino di N-1 guasti.

N version programming - NVP (programmazione ad N versioni )

In questa tecnica, ciascun modulo software viene progettato e codificato N volte da gruppi di progettisti/programmatori distinti.

Le N versioni vengono poi utilizzate in un classico meccanismo di voto, simile a quello associato alla ridondanza hardware di tipo NMR. L'obiettivo in questo caso è un vero e proprio mascheramento del guasto nel software. Per questo tipo di soluzione esistono due problematiche specifiche. In primo luogo, poiché è statisticamente provato che progettisti/programmatori distinti tendano spesso a fare gli stessi tipi di errori, non vi è mai buona garanzia che due versioni distinte non avranno gli stessi identici guasti. In secondo luogo, le N versioni sono comunque sviluppate a partire dalla stessa specifica, per cui l'approccio NVP non ha la capacità di affrontare il problema delle imperfezioni nella specifica.

Recovery blocks (blocchi di recupero)

Essa è concettualmente simile alla tecnica delle N riserve fredde nella ridondanza hardware. In particolare, vengono impiegate N versioni distinte di un dato programma ed un solo insieme di test di accettazione. Una delle versioni è denominata primaria, le altre N-1 sono invece delle riserve fredde. La versione primaria rimane attiva fino a quando i test di accettazione non rivelano un errore. Il tal caso essa viene sostituita da una delle versioni secondarie e così via. Assumendo che i test di accettazione abbiano capacità completa di rivelare gli errori e che questi siano indipendenti nelle N versioni, questa tecnica permette di tollerare al più N-1 guasti.

Fig.- Tolleranza dei guasti di tipo software tramite blocchi di recupero.

EXPERIMENTAL OR THEORETICAL EVALUATIONS

 ALL POSITIVE OPERATIONAL REALISATIONS

COMMERCIAL AVIONICS : MASSIVE AND GENERALISED UTILISATION RAILWAY CONTROL AND SIGNALLING : PARTIAL

UTILISATION (ITALY, SINGAPORE, SWEDEN, USA, ...)

DEPENDABILITY EVALUATION





FAULTINDEPENDENCY / SEPARATE DEVELOPMENTS ? FAULT TOLERANCE COVERAGE



Error: Reference source not found

Ridondanza a livello dei dati

La ridondanza a livello dei dati consiste nell'utilizzo di informazioni aggiuntive associate ai dati stessi al fine di poter garantire la correttezza del loro valore. L'aggiunta di questa informazione da luogo a codifiche dei dati cosiddette ridondanti, che permettono appunto o la rivelazione o addirittura la correzione di dati aventi valore corrotto a causa di un qualche guasto. Ogni codice è caratterizzato da una quantità massima di bit di informazione corrotti che esso riesce a rivelare o a correggere. Un codice in grado di rivelare/correggere al più un unico bit di informazione corrotto viene comunemente denominato codice rivelatore/correttore di singolo errore.

Qui inserire i lucidi sui codici ridondanti e sulla distanza di Hamming fatti a mano

Codici di parità per sovrapposizione

I codici di parità per sovrapposizione sono codici a rivelazione e a correzione di errore, sono in grado di individuare quale sia il bit eventualmente errato, che quindi può essere corretto tramite una semplice operazione di complementazione del suo valore.

In questi codici, i bit propri del dato in oggetto vengono suddivisi in insiemi, possibilmente non disgiunti, e viene introdotto un bit di parità per ciascun insieme. Ciascuno degli insiemi finali includenti il bit di parità viene denominato insieme di parità. L'idea di base è di associare un dato bit ad una combinazione unica di insiemi sovrapposti, così che la corruzione del suo valore ha un effetto finale univocamente identificabile dal punto di vista della parità all'interno dei vari insiemi.

Fig. - Un esempio di codice di parità per sovrapposizione.

Architetture RAID

(Redundant Array of Inexpensive Disk)

Legge di Amdhal

dove:

S è lo speed-up effettivo;

f è la frazione di lavoro non dipendente dai dispositivi di I/O;

K è lo speed-up della modalita’ veloce.

L’espressione afferma che lo speed-up effettivo di un sistema di elaborazione è limitato dall’interazione con i dispositivi di I/O.

Per esempio per un’applicazione che utilizza il 20% del suo tempo per operazioni di I/O ed ipotizzando che il sistema processore- memoria di lavoro migliori le prestazioni di 100 volte, dall’espressione si può notare che lo speed-up effettivo è minore di 5.

Caratteristiche di disco a testina mobile (costituito da un singolo disco fisico o da più dischi fisici coassiali):

 tempo di ricerca (seek-time): il tempo per posizionare la testina sulla traccia;

 latenza di rotazione (rotational latency): il tempo di attesa per permettere all'inizio del settore che si vuole leggere di passare sotto la testina;

 tempo di trasferimento (data transfer time): il tempo necessario per leggere i dati dal settore.

K f f S







) 1 (

1

Cambiando la tecnologia si possono migliorare le prestazioni, comunque essendoci degli organi elettromeccanici, questi non potranno mai andare alla velocità dei componenti elettronici.

Pertanto, si è pensato di migliorare le prestazioni utilizzando contemporaneamente più dischi. Le architetture AID (Arrays of Inexpensive Disks) sono basate su un insieme di dischi indipendenti, organizzati in modo di essere visti dall’utilizzatore come un unico disco logico di grandi dimensioni, con il vantaggio di poter accedere in parallelo ai singoli dischi. Ciò permette alte frequenze di trasferimento (Data Transfer Rates), nel caso di accesso a file di grandi dimensioni, ed elevati tassi di I/O (I/O Rates), nel caso di file di piccole dimensioni. Questo tipo d'architetture permette, tra l’altro, di distribuire in maniera efficiente il carico tra i vari dischi o pile di dischi.

Purtroppo le architetture AID hanno una bassa affidabilità (vedere Sezione "Sistemi affidabili ed in tempo reale"). Infatti, se si indica con MTTFSingolo-disco (Mean Time To Failure) il tempo medio di guasto di un singolo disco, il tempo medio di guasto di un AID è pari a:

Per esempio, se si ha array con 10 dischi, ognuno con un MTTFSingolo-disco pari a 10000 ore, l’MTTFAID è pari a solo 1000 ore, cioè si passa da un’affidabilità di circa un anno ad un’affidabilità di circa un mese.

RAID

array dell dischi di

Numero

MTTF_AID MTTF^{Singolo disco}

'

 

Nei sistemi RAID i dati di un file sono suddivisi in più frammenti (stripe). Ogni frammento sarà visto da ogni singolo disco come un’unica entità, sarà il gestore a livello superiore che ha l’onere di gestire la frammentazione e la ricostruzione del file di partenza.

Attualmente sono state proposte sei differenti tipi d'architetture, che sono sommariamente descritte di seguito. Nella descrizione si fa riferimento ad un sistema di memorizzazione con una capacità effettiva pari a quella di quattro dischi. Nella figura i dischi sono schematizzati come un cilindro pieno o come un cilindro costituito da una pila di vassoi, dove ogni vassoio rappresenta per semplicità un frammento. Le entità ombrate rappresentano risorse ridondanti.

Fig. - Architetture RAID

Livello 0: non contiene alcuna ridondanza, l’organizzazione a stripe permette un accesso in parallelo dell’informazione in più dischi contemporaneamente, permettendo così un miglioramento delle prestazioni rispetto a quelle ottenibili accedendo ad un singolo disco.

Livello 1: conosciuto anche come architettura con dischi duplicati o replicati (mirrored-disks). In quest'architettura l’informazione è duplicata, è quindi memorizzata su un numero doppio di dischi rispetto a quello del livello 0 (a parità di capacità di memorizzazione) ed ogni singola informazione è memorizzata su ogni singolo disco con un codice di rivelazione d'errore (normalmente il codice di parità). Quest'architettura è in grado di tollerare la presenza di un singolo guasto ed ogni operazione di scrittura è fatta su due dischi. In fase di lettura il guasto di un disco è identificato tramite il codice di rivelazione d'errore utilizzato localmente, quindi si potrà utilizzare l’informazione memorizzata sul disco gemello. Quest'informazione è utilizzata anche per aggiornare l’informazione del disco diagnosticato

guasto. Il guasto verrà diagnosticato come permanente se in un successivo tentativo di lettura si verifica un ulteriore errore; in questo caso è necessario riparare o sostituire il disco guasto. Il vantaggio di quest'architettura è nella semplicità di realizzazione e nel fatto che in assenza di guasti la lettura di un’informazione può essere fatta accedendo alla copia memorizzata sul disco che in quell’istante garantisce il minor tempo di accesso (per esempio perché ha una coda di richieste più piccola o perché ha la testina vicino al settore dove è memorizzata l’informazione).

Livello 2: usa il codice di Hamming, che è un codice a rivelazione e a correzione di errori, per memorizzare le informazioni. Il vantaggio di questa architettura è che il numero di dischi ridondanti non è il doppio di quelli strettamente necessari a memorizzare l’informazione ma è logaritmica al loro numero. I bit ridondanti non solo permettono di rivelare un errore ma ne permettono anche di identificare la posizione. Lo svantaggio risiede nel fatto che, per la lettura e la scrittura, è necessario accedere a tutti i dischi.

Livello 3: usa un codice “prodotto”, dato dal doppio uso del codice di parità, come il livello 1 usa localmente il codice di parità per rivelare errori, invece per ricostruire l’informazione persa usa un solo disco in cui viene memorizzato il bit di parità dei bit disposti nella stessa posizione nei dischi utili. Il valore di questo è sufficiente a ricostruire quello del bit errato. Anche in questo caso lo svantaggio risiede nel fatto che per la lettura e per la scrittura è necessario accedere a tutti i dischi.

1 1 0 0 0

0 0 1 0 1

0 1 1 0 0

0 0 1 1 0

1 0 1 1

Fig. – Esempio di codice prodotto

Livello 4: è un miglioramento del livello 3 arrangiando le strisce (stripe) in blocchi piuttosto che in bit. Con questa soluzione la lettura di un blocco necessita dell’accesso del disco dove è memorizzata l’informazione stessa, purtroppo anche in questo caso ad ogni aggiornamento corrisponde un accesso al disco di parità, che diviene così il collo di bottiglia del sistema.

Livello 5: è un miglioramento del livello 4 evitando il collo di bottiglia del disco di parità. In questo caso le informazioni ridondanti sono equamente distribuite su tutti i dischi, in modo che ad ogni singolo aggiornamento non sia coinvolto sempre lo stesso disco. Purtroppo le prestazioni in scrittura sono peggiori di quelle del livello 1, in quanto ogni singola scrittura necessita di quattro singoli accessi a disco: una lettura sul disco in cui è memorizzato la vecchia informazione del blocco, una lettura sul disco in cui è memorizzata la vecchia l’informazione ridondata (queste informazioni insieme ai nuovi dati che devono essere memorizzati servono per identificare quali bit cambiare nel blocco ridondante), un accesso in scrittura sui due dischi in questione per memorizzare il nuovo blocco e l’informazione ridondante. Notare come gli accessi in lettura, come quelli in scrittura possono essere fatti in

parallelo, così che il tempo di aggiornamento affidabile dell’informazione è pari alla somma di due singoli tempi di accesso, inoltre è da osservare che, se la scrittura segue immediatamente la lettura sullo stesso settore, il secondo accesso non necessita del tempo di ricerca (seek time).

Livello 6: utilizza codici ridondanti che permettono la correzione di due errori, invece che uno solo come nei livelli precedenti. Le prestazioni del livello 6 sono analoghe a quelle del livello 5 anche se il numero di accessi per ogni singolo aggiornamento sui singoli dischi è sei: tre per la lettura e tre per la scrittura, invece delle quattro necessarie al livello 5 (notare come, anche in questo caso, gli accessi in lettura così come quelli in scrittura possono essere fatti in parallelo). Rispetto al livello 5 necessita di un maggior numero di dischi per poter utilizzare codici con maggiore distanza di Hamming.

La scelta tra i differenti livelli è naturalmente un compromesso tra costi, prestazioni ed affidabilità. I prodotti commerciali disponibili oggi sul mercato sono di tipo 1, 5 e 6.

La ridondanza temporale

Il concetto di base della ridondanza temporale è quello di eseguire un dato calcolo in sequenza più di una volta, e comparare i risultati ottenuti in ciascuna ripetizione per verificare se esista qualche discrepanza. In caso affermativo, la discrepanza è sintomatica di un errore e l'azione classica è quella di ripetere il calcolo tramite una nuova sequenza per verificare se tale discrepanza persiste o meno.

Originariamente la ridondanza temporale è stata impiegata soprattutto per il trattamento degli errori dovuti a guasti transienti, ove, una volta rivelato l'errore, successive ripetizioni dovrebbero rivelare assenza di discrepanza dovuta al fatto che il guasto scompare autonomamente. Comunque questo tipo di ridondanza ha la capacità di far scoprire anche guasti permanenti in componenti hardware a patto che si faccia uso di una minima quantità di hardware aggiuntivo. Lo schema in figura riporta un esempio di ridondanza temporale per la scoperta di guasti permanenti.

Al tempo T0 viene effettuata una prima computazione, poi al tempo T1 viene effettuata una seconda computazione in cui i dati di ingresso vengono codificati in ingresso al sistema di calcolo e poi decodificati in uscita. I risultati delle due computazioni vengono poi comparati per rivelare eventuali discrepanze. Le funzioni di codifica/decodifica sono selezionate in modo da poter rivelare guasti nel sistema di calcolo, classiche funzioni di decodifica utilizzate sono gli operatori di complementazione e gli shift aritmetici/logici.

Fig. - Ridondanza temporale per guasti permanenti.

non fault tolerant

Availability: 97,7%

Failure sources

Server 66%

Network 10%

Client 11%

Envir & Oper 13%

Design 60%

Operations 24%

Physical 16%

non fault tolerant

[Japan, 1383 organisations, 1986;

USA, 450 companies, 1993]

Mean time to failure : 6 - 12 weeks Average outage : 1 - 4 hr

Failure sources

Hardware 50%

Software 25%

Communications -

Environment 15%

Operations -

Procedures 10%

fault tolerant

[Tandem Computers, 1990;

Bell Northern Research, 1992]

Mean time to failure:

21 ans [Tandem]

Failure sources Software 65%

Operations -

Procedures 20%

Hardware 8%

Environment 7%

Traditional systems Client-server networks

fault tolerant servers

Availability: 99%

Failure sources

Server 22%

Network 23%

Client 25%

Envir & Oper 30%

[Tandem Computers, 1994]

Statistiche dei guasti su sistemi FT e non

Dynabus

Dynabus interface CPU Memory I/O Channel

Disk Controller

Disk Controller

Disk Controller Tape Controller

VDU Controller Processor

Module

Processor Module

Processor Module

Tandem NonStop

Architettura del TANDEM

1985 1987 1989

Systems 2400 6000 9000

Processors 7000 15000 25500

Disks 16000 46000 74000

MTBF System 8 years 20 years 21 years

Tandem experimental data

Period Sep 82 - Jun 85 Jun 85 - Jun 87 Jun 87 - Jun 89

50 100 150 200 250 300 350 400 450

01985 1987 1989

Environment

Total

Maintenance

Operations

Software Hardware MTBF

(years) Error: Reference source not found

Error:

Reference source not found

Error: Reference source not found