Università degli Studi di Firenze

 

Corsi di Laurea in Ingegneria Elettronica,

Informatica e delle Telecomunicazioni

 

 

Corso di Informatica Industriale

 

 

Appunti del docente

 

 

Anno Accademico 2001/2002

 

 

 

 

Introduzione alle problematiche degli errori nel calcolo e bibliografia del corso.

 

 

Prof.  A. Fantechi

 


Introduzione alle problematiche degli errori nel calcolo

 

Il corso di Informatica Industriale si rivolge per la gran parte del suo svolgimento al trattamento delle situazioni di guasto di un sistema computerizzato, situazioni che possono essere state sperimentate nella pratica quotidiana di utilizzo di un Personal Computer, ma che in generale hanno prodotto danni molto limitati.

I computer, già da una ventina di anni almeno, stanno via via rimpiazzando l’uomo in molte funzioni , alcune delle quali rivestono enorme importanza dal punto di vista della sicurezza fisica, o dal punto di vista della sicurezza economica. In questi casi i danni provocati da una situazione di guasto di un sistema computerizzato possono essere notevoli, sia in termini economici che di vite umane.

Questo indica quale possa essere l’importanza da un punto di vista industriale di un corretto approccio al trattamento (inclusa anche la prevenzione) di situazioni di guasti. D’altra parte, al neofita informatico che ha appena imparato quali siano le principali caratteristiche e funzioni dell’hardware e del software di un computer, può risultare abbastanza misterioso come si possano trattare in modo soddisfacentemente sicuro delle situazioni in cui un computer è apparentemente non più in grado di eseguire le elaborazioni come dovrebbe.

Per questo questa introduzione vuole dare una prima occhiata ai concetti base che si usano in questo settore, che verranno poi approfonditi in seguito, partendo dal semplice concetto di errore in un procedimento di calcolo.

 

 

Tecniche di rilevazione dell'errore (error detection)

 

Consideriamo quali sono i metodi classici per la rilevazione degli errori nei comuni procedimenti di calcolo aritmetici:

- verifica con rifacimento dell'operazione -  L'operazione viene eseguita due volte;  se i risultati concordano, si conclude che non c'è stato errore, altrimenti se i risultati sono discordi,  si deduce che una delle due esecuzioni dell’operazione è stata errata

·        vantaggi:  rileva tutti gli errori (singoli)

·        svantaggi:  duplicazione dello sforzo

 

- prova del nove:


dati x1, x2, x1+x2,  verifico che x1 mod 9  +  x2 mod 9 = (x1+x2) mod 9

 


·        vantaggi: veloce, facile, (in particolare,  in base 10 la operazione di modulo 9 si esegue molto facilmente:  lasciamo al lettore come esercizio la dimostrazione che data una rappresentazione posizionale in base B, l'operazione x mod (B-1)  si esegue sommando tra loro, modulo B-1, tutte le cifre della rappresentazione di x).

·        svantaggi: non rileva tutti gli errori

 

 

Nel primo caso, data una funzione f(x1, .. xn),  eseguo la verifica f(x1, .. xn) = f(x1, .. xn), ovvia tautologia, il cui fallimento rileva il malfunzionamento di una applicazione (o di entrambe le applicazioni!)  della funzione f.  Chiameremo questo meccanismo duplicazione e confronto. Questo è un primo esempio di ridondanza (nelle risorse di calcolo, in termini fisici o temporali) ai fini della rilevazione dell'errore.

Questo meccanismo lascia scoperto il caso in cui entrambe le applicazioni della funzione f falliscono producendo lo stesso valore errato (fallimento di modo comune - common mode failure).

D'altra parte la natura della funzione f  e del suo meccanismo di calcolo potrebbe portare a farci ritenere che il fallimento di modo comune sia molto raro o addirittura impossibile.

 

Nel secondo caso, data una funzione f(x1, .. xn), uso una funzione omomorfa f' definita su un dominio D' omomorfo rispetto al dominio D su cui è definita la f .

Questo significa che esiste una corrispondenza R che associa ad ogni elemento di D' un elemento di D , e che      f'(R(x1),..R(xn)) = R(f(x1, .. xn))

È appunto la verifica di questa uguaglianza che facciamo per rilevare l'errore, usufruendo del fatto che l'esecuzione di f' è normalmente più semplice e meno costosa dell'esecuzione di f.

Se questa uguaglianza risulta falsa, vuol dire che vi è stato qualche errore nell'applicazione di f, oppure nell'applicazione di f', oppure nella applicazione di R.

Se risulta vera, non possiamo garantire che non ci siano errori, perché ad esempio l'applicazione di f potrebbe ritornare un valore y' ≠  y = f(x1, .. xn), ma tale che R(y') = R (y).   Esistono perciò delle situazioni di errore non coperte dal meccanismo di rilevazione.  Conoscendo la natura della funzione e della corrispondenza R possiamo però valutare la probabilità con cui questo accade e addirittura  decidere che questa sia in realtà trascurabile.

Si noti infine che il caso precedente (duplicazione e confronto) non è altro che un caso particolare di quanto abbiamo detto ora,  in cui consideriamo f' = f, e R la relazione identità.

 

La trattazione dei meccanismi di rilevazione dell'errore può essere generalizzata in questo modo:

 

data una funzione f(x1, .. xn),  costruisco un predicato P che, dati x1,.., xn, e un valore y, ritorni vero se y è il risultato della funzione f(x1, .. xn), e che altrimenti possa ritornare ugualmente vero (casi di errore non coperti) oppure falso (casi di errori coperti).  Per essere un soddisfacente meccanismo di rilevazione dell'errore, il predicato P dovrà avere un insieme di situazioni di errore non coperte minimo, e dovrà essere valutabile con un costo (in termini di tempo o risorse di calcolo) minimo.

Vedremo nel seguito vari meccanismi di rilevazione dell'errore che si rifanno in un modo o nell'atro ai concetti sopra introdotti.  Finora abbiamo considerato solamente errori nel dominio dei valori, ma spesso si vogliono considerare anche errori nel dominio del tempo: frequente è la situazione in cui per un guasto un sistema non dà segni di vita.  Considereremo nel seguito anche meccanismi di rilevazione di questi tipi di errore.

Notare che abbiamo introdotto una serie di concetti tipici dello studio dei malfunzionamenti,  o, come diremo poi con più precisa terminologia , guasti:

1)      esiste un insieme di possibili malfunzionamenti o manifestazioni di guasti (modi di fallimento - failure modes)

2)      si possono fare assunzioni sui guasti (fault assumptions) per non considerare situazioni impossibili o estremamente improbabili

3)      ad un meccanismo di rilevazione dell'errore può essere associata un attributo di copertura rispetto ad un insieme di guasti - attributo che può essere semplicemente qualitativo, o binario rispetto ad un dato insieme di guasti, o misurato, ad esempio in termini percentuali o probabilistici ("copre il 90% dei guasti di un dato insieme" - "copre un insieme di guasti con una probabilità pari a 0,99")

 

 

Se andiamo a considerare i meccanismi basici finora considerati per la rilevazione dell’errore quando si lavori su numeri binari, si può curiosamente rilevare l’importanza che assume l’operatore di or esclusivo (XOR).

Infatti, un comparatore che segnali un errore con un valore pari a 1 quando vi sia discordanza tra due bit, è uno XOR. Un comparatore di due numeri binari è quindi una batteria di XOR le cui uscite vengono messe in OR tra loro.

Se invece volessimo eseguire in base 2 l’operazione corrispondente alla prova del 9,  vediamo che non possiamo fare una somma dei bit degli addendi di una somma modulo B-1, con B=2, perché non ha senso parlare di un sistema di numerazione modulo 1.  E quindi non possiamo definire un meccanismo di rilevazione di errori su operazioni aritmetiche quale è la prova del 9 in base 10 (in realtà possiamo definire, come vedremo, un meccanismo analogo lavorando in base 4, cioè raggruppando i bit a due a due, e quindi lavorando nel sistema di numerazione modulo 3).

Ma è ugualmente importante la somma dei bit modulo 2, che prende il nome di parità: se il numero dei bit posti ad 1 è dispari, tale somma è 1, e  0 altrimenti.  Se uno qualsiasi dei bit venisse mutato da 0 a 1 o viceversa, anche la somma dei bit modulo 2 cambia. Quindi il confronto della parità effettiva con quella attesa permette di rilevare errori nella trasmissione o nella memorizzazione di un dato.  Si noti che il calcolo della somma dei bit modulo 2 si ottiene con una concatenazione ad albero binario di XOR, e che l’ulteriore confronto è anch’esso ottenibile con uno XOR.

 

Non deve stupire l’importanza dell’operatore di XOR, come pure quella dei sistemi di numerazione in modulo, nel trattamento degli errori. In realtà tutta la teoria dei gruppi ciclici (insiemi finiti muniti di operazioni di somma in cui a partire da un elemento si possono generare mediante somme tutti gli altri elementi), di cui i sistemi di numerazione in modulo sono i più semplici esempi, nonchè di altre strutture algebriche che possono essere visti come loro specializzazioni, come ad esempio i campi,  è fondamentale nello studio dei più sofisticati codici di rilevazione e correzione degli errori, quali quelli usati ad esempio per al memorizzazione dei dati nei CD e DVD. Pur non entrando nei dettagli tecnici di questo interessante ramo della matematica, avremo a che fare diverse volte con tali concetti.

 

 

Tecniche di correzione dell'errore (error correction)

 

Consideriamo quali sono i metodi classici per la rilevazione degli errori nei comuni procedimenti di calcolo aritmetici:

un primo metodo è una evoluzione del metodo di duplicazione e confronto visto per la rilevazione degli errori: si esegue tre volte l’operazione: se i valori dei tre risultati non coincidono, nell’ipotesi che si sia al più fatto un solo errore, considero i due risultati uguali come quelli corretti. 

Più in generale, posso ripetere l’operazione n volte e verificare se riesco a raggiungere una maggioranza di valori uguali, che ipotizzo essere quelli corretti. Questa operazione si indica come votazione a maggioranza.

 

Un metodo alternativo è invece una evoluzione in senso diverso dei meccanismi di rilevazione dell’errore.  Supponiamo di avere un meccanismo di rilevazione dell’errore che abbia capacità di diagnosi, cioè che ci sappia indicare dove è che, nel calcolo di una operazione, si è effettuato un errore.  Possiamo allora intervenire correggendo opportunamente il risultato.

Ad esempio, supponiamo di avere un risultato di un operazione come numero di n bit. Un adeguato meccanismo di diagnosi potrebbe rilevare che il bit i-esimo è guasto. E’ allora possibile correggere l’errore semplicemente negando il bit in questione.  Se la diagnosi viene fornita sotto forma di un numero binario dove tutti i bit sono a zero e solo il bit i-esimo (corrispondente a quello guasto) è ad uno (o, più in generale, dove tutti i bit corrispondenti a bit guasti, se ve ne sono più di uno, sono posti a uno), allora basterà fare uno XOR (o somma modulo 2) bit a bit del numero con errori con il numero di diagnosi. Ancora una volta ci troviamo tra i piedi lo XOR.

 

 

 

Il fattore temporale

 

A complicare la situazione rispetto alle semplici schematizzazioni fatte in precedenza subentra il fattore temporale.

 

Un primo punto a questo riguardo è che la ridondanza nel calcolo può essere temporale invece che strutturale:  come quando si opera nella normale aritmetica, le operazioni ridondate possono essere fatte in sequenza utilizzando la stessa risorsa di calcolo; ad esempio possiamo duplicare temporalmente lo svolgimento di una operazione e confrontarne i risultati successivamente.

Oppure possiamo svolgere tre volte la stessa operazione e votarne a maggioranza i risultati: in questo caso possiamo normalmente effettuare due operazioni, e solo se i risultati discordano (rilevazione dell'errore), eseguire la terza operazione.  Si noti che con questo ultimo meccanismo la ridondanza temporale è normalmente pari a 2, tranne nei casi in cui si verifica un errore.

 

Si potrebbe obiettare che, se una unità di calcolo si guasta, è inutile farle ripetere il calcolo perché comunque sbaglierà anche il prossimo, introducendo quindi addirittura errori di modo comune.

Ma questo solo se si assumono solo guasti permanenti, non se si assumono guasti temporanei (transienti).  Quindi il fattore tempo rientra anche nella definizione stessa delle assunzioni di guasto

 

La ridondanza temporale è il meccanismo più naturalmente utilizzato per la correzione degli errori di comunicazione: in questo caso il meccanismo di rilevazione dell'errore è pure di natura temporale, cioè il time-out.  Se un messaggio di acknowledge ad una spedizione non è arrivato entro un certo tempo massimo, si suppone l'esistenza di un guasto e si usa la ritrasmissione (ridondanza temporale) per correggere l'errore.  In questo caso si assumono guasti temporanei; spesso si associa a questo meccanismo un meccanismo di rilevazione di guasti permanenti ancora basato sulla ridondanza temporale: dopo un certo numero di ritrasmissioni si dichiara defunto il collegamento.

Un meccanismo di time-out è anche quello che si usa, più o meno  …..,  per monitorare la corretta attività di un processore:   quando ad esempio si dice che un computer si è "piantato" in realtà si esprime il fatto che esso non presenta segni di attività per un tempo inaccettabilmente lungo. A questo proposito notiamo che:

1)      normalmente un processore non si "pianta", ma continua ad eseguire (all'infinito) un ciclo di operazioni che non danno risultati osservabili

2)      "inaccettabilmente lungo" è una locuzione soggettiva:  probabilmente al lettore è capitato di essersi imbattuto in un computer apparentemente "piantato", di cui si è inopinatamente fatto uno shutdown pochi secondi prima che il suo normale funzionamento (cioè, l'osservabilità esterna del suo normale funzionamento) riprendesse.

 

Ma finora abbiamo parlato esclusivamente di meccanismi di rivelazione e correzione di errori basati sul tempo.  In realtà il tempo può rientrare anche nella definizione di corretto servizio fornito dal sistema.  Cioè possiamo considerare un sistema guasto non solo quando fornisce un valore errato, ma anche quando lo fornisce corretto, ma troppo tardivo:  questa è una condizione tipica dei sistemi real-time, dove la tempistica rientra nella definizione stessa di corretto servizio fornito.

Cioè i guasti si manifestano non soltanto come errori nel dominio dei valori, ma anche come errori nel dominio del tempo.

 

La terminologia della Dependability

 

Le premesse fatte finora sono solo introduttive ad acluni concetti che meritano un ulteriore approfondimento. Prima di approfondire le tecniche con cui si affronta la possibilità che un sistema computerizzato possa errare a causa di qualche forma di guasto, è necessario accordarsi su quali termini utilizzaimo per indicare fenomeni e concetti:  possiamo ad esempio notare come finora si siano usati indifferentemente i termini guasto e errore, quasi fossero sinonimi. La terminologia nel settore dell’affidabilità dei sistemi computerizzati è in realtà molto varia, derivando i suoi termini da vari campi delle tecnologie hardware e software, tanto che all’interno dell’Working Group  WG 10.4 (Dependable Computing and Fault-Tolerance) dell’IFIP si è sentita la necessità di definire precisamente i vari termini usati, chiarendo le sottili differenze esistenti tra termini apparentemente simili, in un documento intitolato “Dependability: Basic Concepts and Terminology”  che introduce il concetto di Dependability, cioè la proprietà di un sistema di essere adeguato a che un essere umano, o una collettività, possa dipendere da esso, senza correre rischi inaccettabili.

 

 

 

Bibliografia del corso

 

Introduzione al corso:  questi appunti.

Dependability – concetti e terminologia:  IFIP WG10.4 - Dependability: Basic Concepts and Terminology

Tecniche di prevenzione del guasto, tecniche di rilevazione del guasto, tecniche di ridondanza, codici di rilevazione e correzione di errore, architetture di sistemi fault-tolerant commerciali:

D.P. Siewiorek, R.P. Swarz,  Reliable Computer Systems : Design and Evaluation Digital Press, 1992

D. K. Pradhan, Fault-Tolerant Computer System Design, Prentice Hall, 1996

Elementi di teoria del testing:  Alcuni lucidi su testing

Tendenze di utilizzo industriale  di strumenti di verifica formale:    Slides su B,  Appunti su model-checking e simulazione ,  Alcuni lucidi su applicazioni industriali di metodi formali

La  certificazione software  e la Normativa CENELEC:  EN50128, in 5 files: 1, 2, 3, 4, 5.

Introduzione ai processori di utilizzo industriale: