CprE 458/558: Real-Time SystemsFault Tolerant StrategiesReconfiguration ApproachThe Concept of RedundancyThe Concept of Redundancy (Cont’d)Hardware RedundancyHardware Redundancy (Cont’d)Hardware Redundancy - A TaxonomyTriple Modular Redundancy (TMR)Software Redundancy - to Detect Software FaultsN-Version Programming (NVP)N-Version Programming (Cont’d)Recovery Blocks (RB)Recovery Blocks (Cont’d)Slide 15CprE 458/558 G. Manimaran (ISU)CprE 458/558: Real-Time SystemsLecture 17Fault-tolerant design techniques2CprE 458/558 G. Manimaran (ISU)Fault Tolerant StrategiesFault tolerance in computer system is achieved through redundancy in hardware, software, information, and/or computations. Such redundancy can be implemented in static, dynamic, or hybrid configurations.Fault tolerance can be achieved by many techniques:Fault masking is any process that prevents faults in a system from introducing errors. Example: Error correcting memories and majority voting.Reconfiguration is the process of eliminating faulty component from a system and restoring the system to some operational state.3CprE 458/558 G. Manimaran (ISU)Reconfiguration ApproachFault detection is the process of recognizing that a fault has occurred. Fault detection is often required before any recovery procedure can be initiated.Fault location is the process of determining where a fault has occurred so that an appropriate recovery can be initiated.Fault containment is the process of isolating a fault and preventing the effects of that fault from propagating throughout the system.Fault recovery is the process of remaining operational or regaining operational status via reconfiguration even in the presence of faults.4CprE 458/558 G. Manimaran (ISU)The Concept of RedundancyRedundancy is simply the addition of information, resources, or time beyond what is needed for normal system operation.Hardware redundancy is the addition of extra hardware, usually for the purpose either detecting or tolerating faults.Software redundancy is the addition of extra software, beyond what is needed to perform a given function, to detect and possibly tolerate faults.Information redundancy is the addition of extra information beyond that required to implement a given function; for example, error detection codes.5CprE 458/558 G. Manimaran (ISU)The Concept of Redundancy (Cont’d)Time redundancy uses additional time to perform the functions of a system such that fault detection and often fault tolerance can be achieved. Transient faults are tolerated by this.The use of redundancy can provide additional capabilities within a system. But, redundancy can have very important impact on a system's performance, size, weight, power consumption, and reliability.6CprE 458/558 G. Manimaran (ISU)Hardware RedundancyPassive techniques use the concept of fault masking. These techniques are designed to achieve fault tolerance without requiring any action on the part of the system. Relies on voting mechanisms.Active techniques achieve fault tolerance by detecting the existence of faults and performing some action to remove the faulty hardware from the system. That is, active techniques use fault detection, fault location, and fault recovery in an attempt to achieve fault tolerance.7CprE 458/558 G. Manimaran (ISU)Hardware Redundancy (Cont’d)Hybrid techniques combine the attractive features of both the passiveand active approaches. Fault masking is used in hybrid systems to prevent erroneous results from being generated.Fault detection, location, and recovery are also used to improve fault tolerance by removing faulty hardware and replacing it with spares.8CprE 458/558 G. Manimaran (ISU)Hardware Redundancy - A TaxonomyTitle:hard-fault.figCreator:fig2dev Version 3.1 Patchlevel 2Preview:This EPS picture was not savedwith a preview included in it.Comment:This EPS picture will print to aPostScript printer, but not toother types of printers.9CprE 458/558 G. Manimaran (ISU)Triple Modular Redundancy (TMR)Title:tmr1.figCreator:fig2dev Version 3.1 Patchlevel 2Preview:This EPS picture was not savedwith a preview included in it.Comment:This EPS picture will print to aPostScript printer, but not toother types of printers.10CprE 458/558 G. Manimaran (ISU)Software Redundancy - to Detect Software FaultsThere are two popular approaches: N-Version Programming (NVP) and Recovery Blocks (RB).NVP is a forward recovery scheme - it masks faults.NVP: multiple versions of the same task is executed concurrently.NVP relies on voting.RB is a backward error recovery scheme.RB: the versions of a task are executed serially.RB relies on acceptance test.11CprE 458/558 G. Manimaran (ISU)N-Version Programming (NVP) NVP is based on the principle of design diversity, that is coding a software module by different teams of programmers, to have multiple versions.Diversity can also be introduced by employing different algorithms for obtaining the same solution or by choosing different programming languages.NVP can tolerate both hardware and software faults.Correlated faults are not tolerated by the NVP.In NVP, deciding the number of versions required to ensure acceptable levels of software reliability is an important design consideration.12CprE 458/558 G. Manimaran (ISU)N-Version Programming (Cont’d)Title:nvp.figCreator:fig2dev Version 3.1 Patchlevel 2Preview:This EPS picture was not savedwith a preview included in it.Comment:This EPS picture will print to aPostScript printer, but not toother types of printers.13CprE 458/558 G. Manimaran (ISU)Recovery Blocks (RB)RB uses multiple alternates (backups) to perform the same function; one module (task) is primary and the others are secondary.The primary task executes first. When the primary task completes execution, its outcome is checked by an acceptance test.If the output is not acceptable, a secondary task executes after undoing the effects of primary (i.e., rolling back to the state at which primary was invoked) until either an acceptable output is obtained or the alternates are exhausted.14CprE 458/558 G. Manimaran (ISU)Recovery Blocks (Cont’d)Title:rblocks.figCreator:fig2dev Version 3.1 Patchlevel 2Preview:This EPS picture was not savedwith a preview included in it.Comment:This EPS picture will print to aPostScript printer, but not toother types of printers.15CprE 458/558 G. Manimaran (ISU)Recovery Blocks (Cont’d)The acceptance tests