Fundamental Concepts of Dependability

Algirdas Aviž ienis Jean-Claude Laprie Brian Randell

UCLA, Los Angeles, CA, USA LAAS-CNRS Dept. of Computing Science
and Vytautas Magnus U. Toulouse U. of Newcastle upon Tyne
Kaunas, Lithuania France U.K.
aviz@cs.ucla.edu laprie@laas.fr Brian.Randell@newcastle.ac.uk

1. Origins and Integration of the Concepts Critical Applications was held in 1989. This and the six
working conferences that followed fostered the interaction
The concept of dependable computing first appears in
of the dependability and security communities, and
the 1830’s in the context of Babbage’s Calculating Engine
advanced the integration of security (confidentiality,
[1,2]. The first generation of electronic computers (late
integrity and availability) into the framework of
1940’s to mid-50’s) used rather unreliable components,
dependable computing [22]. A summary of [22] is
therefore practical techniques were employed to improve
presented next.
their reliability, such as error control codes, duplexing
with comparison, triplication with voting, diagnostics to
locate failed components, etc. [3-5]. 2. The Principal Concepts: a Summary
At the same time J. von Neumann [6], E. F. Moore A systematic exposition of the concepts of
and C. E. Shannon [7] and their successors developed dependability consists of three parts: the threats to, the
theories of using redundancy to build reliable logic attributes of, and the means by which dependability is
structures from less reliable components, whose faults attained, as shown in Figure 1.
were masked by the presence of multiple redundant AVAILABILITY
components. The theories of masking redundancy were RELIABILITY
unified by W. H. Pierce as the concept of failure tolerance SAFETY
ATTRIBUTES
in 1965 [8]. In 1967, A. Avizienis integrated masking CONFIDENTIALITY
with the practical techniques of error detection, fault INTEGRITY
diagnosis, and recovery into the concept of fault-tolerant MAINTAINABILITY
systems [9]. In the reliability modeling field, the major FAULT PREVENTION
event was the introduction of the coverage concept by FAULT TOLERANCE
Bouricius, Carter and Schneider [10]. Seminal work on DEPENDABILITY MEANS
FAULT REMOVAL
software fault tolerance was initiated by B. Randell FAULT FORECASTING
[11,12], later it was complemented by N-version
FAULTS
programming [13]. THREATS ERRORS
The formation of the IEEE-CS TC on Fault-Tolerant FAILURES
Computing in 1970 and of IFIP WG 10.4 Dependable
Figure 1 - The dependability tree
Computing and Fault Tolerance in 1980 accelerated the
emergence of a consistent set of concepts and Computing systems are characterized by four
terminology. Seven position papers were presented in fundamental properties: functionality, performance, cost,
1982 at FTCS-12 [14], and J.-C. Laprie formulated a and dependability. Dependability of a computing system
synthesis in 1985 [15]. Further work by members of IFIP is the ability to deliver service that can justifiably be
WG 10.4, led by J.-C. Laprie, resulted in the 1992 book trusted. The service delivered by a system is its behavior
Dependability: Basic Concepts and Terminology [16], in as it is perceived by its user(s); a user is another system
which the English text was also translated into French, (physical, human) that interacts with the former at the
German, Italian, and Japanese. service interface. The function of a system is what the
system is intended for, and is described by the system
In [16], intentional faults (malicious logic, intrusions)
specification.
were listed along with accidental faults (physical, design,
or interaction faults). Exploratory research on the 2.1. The Threats: Faults, Errors, and Failures
integration of fault tolerance and the defenses against the
Correct service is delivered when the service
intentional faults, i.e., security threats, was started at the
implements the system function. A system failure is an
RAND Corporation [17], University of Newcastle [18],
event that occurs when the delivered service deviates from
LAAS [19], and UCLA [20,21] in the mid-80’s. The 1st correct service. A system may fail either because it does
IFIP Working Conference on Dependable Computing for not comply with the specification, or because the
specification did not adequately describe its function. A
The alphabetic ordering of authors’ names does not imply failure is a transition from correct service to incorrect
any seniority of authorship
service, i.e., to not implementing the system function. A
transition from incorrect service to correct service is PHENOMENOLOGICAL
NATURAL FAULTS

CAUSE
service restoration. The time interval during which HUMAN-MADE FAULTS

incorrect service is delivered is a service outage. An error ACCIDENTAL FAULTS

is that part of the system state that may cause a INTENT DELIBERATE, NON-MALICIOUS FAULTS
subsequent failure: a failure occurs when an error reaches DELIBERATELY MALICIOUS FAULTS
the service interface and alters the service. A fault is the
DEVELOPMENTAL FAULTS
adjudged or hypothesized cause of an error. A fault is PHASE OF CREATION
PRODUCTION FAULTS
active when it produces an error, otherwise it is dormant. OR OCCURENCE
OPERATIONAL FAULTS
A system does not always fail in the same way. The FAULTS
ways a system can fail are its failure modes. As shown in DOMAIN
PHYSICAL FAULTS

Figure 2, the modes characterize incorrect service INFORMATION FAULTS

according to three viewpoints: a) the failure domain, b) INTERNAL FAULTS

the perception of a failure by system users, and c) the SYSTEM BOUNDARIES
EXTERNAL FAULTS
consequences of failures on the environment.
PERMANENT FAULTS
PERSISTENCE
VALUE FAILURES TRANSIENT FAULTS
DOMAIN
TIMING FAILURES Figure 3 - Elementary fault classes

PERCEPTION BY
CONSISTENT FAILURES
2.2. The Attributes of Dependability
FAILURES
SEVERAL USERS INCONSISTENT FAILURES
Dependability is an integrative concept that
MINOR FAILURES encompasses the following attributes: availability:
CONSEQUENCES •
•
•
readiness for correct service; reliability: continuity of
ON ENVIRONMENT
CATASTROPHIC FAILURES correct service; safety: absence of catastrophic
Figure 2 - The failure modes consequences on the user(s) and the environment;
confidentiality: absence of unauthorized disclosure of
A system consists of a set of interacting components,
information; integrity: absence of improper system state
therefore the system state is the set of its component
alterations; maintainability; ability to undergo repairs
states. A fault originally causes an error within the state of
and modifications.
one (or more) components, but system failure will not
occur as long as the error does not reach the service Security is the concurrent existence of a) availability
interface of the system. A convenient classification of for authorized users only, b) confidentiality, and c)
errors is to describe them in terms of the component integrity with ‘improper’ meaning ‘unauthorized’.
failures that they cause, using the terminology of Figure The above attributes may be emphasized to a greater or
2: value vs. timing errors; consistent vs. inconsistent lesser extent depending on the application: availability is
(‘Byzantine’) errors when the output goes to two or more always required, although to a varying degree, whereas
components; errors of different severities: minor vs. reliability, safety, confidentiality may or may not be
ordinary vs. catastrophic errors. An error is detected if its required. The extent to which a system possesses the
presence in the system is indicated by an error message attributes of dependability should be interpreted in a
or error signal that originates within the system. Errors relative, probabilistic, sense, and not in an absolute,
that are present but not detected are latent errors. deterministic sense: due to the unavoidable presence or
Faults and their sources are very diverse. Their occurrence of faults, systems are never totally available,
classification according to six major criteria is presented reliable, safe, or secure.
in Figure 3. Of special interest for this Workshop are Integrity is a prerequisite for availability, reliability
faults that result from attacks on a system. They are and safety, but may not be so for confidentiality (for
classified as deliberately malicious (d.m.) faults and instance attacks via covert channels or passive listening
include malicious logic [23] (Trojan horses, logic bombs, can lead to a loss of confidentiality, without impairing
trapdoors are d.m. design faults, while viruses and worms integrity). The definition given for integrity – absence of
are d.m. operational faults), intrusions (d.m. external improper system state alterations – extends the usual
operational faults) and physical attacks on a system (d.m. definition as follows: (a) when a system implements an
physical operational faults). Figure 4 shows the combined authorization policy, ’improper’ encompasses
fault classes for which defenses need to be devised. ‘unauthorized’; (b) ‘improper alterations’ encompass
Fault pathology, i.e., the relationship between faults, actions resulting in preventing (correct) upgrades of
errors, and failures is summarized by Figure 5, which information; (c) ‘system state’ encompasses hardware
gives the fundamental chain of threats to dependability. modifications or damages. The definition given for
The arrows in this chain express a causality relationship maintainability goes beyond corrective and preventive
between faults, errors and failures. They should be maintenance, and encompasses two other forms of
interpreted generically: by propagation, several errors can maintenance: adaptive and perfective maintenance.
be generated before a failure occurs.

2
 DESIGN PHYSICAL INTERACTION
FAULTS FAULTS FAULTS

NATURAL FAULTS ● ● ● ● ●

HUMAN-MADE FAULTS ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

ACCIDENTAL FAULTS ● ● ● ● ● ● ● ● ● ● ●

DELIBERATE, NON- ● ● ● ● ● ●
MALICIOUS FAULTS

DELIBERATELY ● ● ● ● ● ●
MALICIOUS FAULTS

DEVELOPMENTAL FAULTS ● ● ● ● ● ●

PRODUCTION FAULTS ● ● ● ● ●

OPERATIONAL FAULTS ● ● ● ● ● ● ● ● ● ● ● ●

PHYSICAL FAULTS ● ● ● ● ● ● ● ● ● ● ● ● ● ●

INFORMATION FAULTS ● ● ● ● ● ● ● ● ●

INTERNAL FAULTS ● ● ● ● ● ● ● ● ● ● ● ● ●

EXTERNAL FAULTS ● ● ● ● ● ● ● ● ● ●

PERMANENT FAULTS ● ● ● ● ● ● ● ● ● ● ● ● ● ● ● ●

TRANSIENT FAULTS ● ● ● ● ● ● ●

Figure 4 - Combined fault classes

… activation propagation causation …

fault error failure fault

Figure 5 - The fundamental chain of threats to dependability

The variations in the emphasis on the different

Security has not been introduced as a single attribute attributes of dependability directly affect the appropriate
of dependability. This is in agreement with the usual balance of the techniques (fault prevention, tolerance,
definitions of security, which view it as a composite removal and forecasting) to be employed in order to make
notion, namely [24] "the combination of (1) the resulting system dependable. This problem is all the
confidentiality (the prevention of the unauthorized more difficult as some of the attributes conflict (e.g.
disclosure of information), (2) integrity (the prevention of availability and safety, availability and security),
the unauthorized amendment or deletion of information), necessitating design trade-offs.
and (3) availability (the prevention of the unauthorized
2.3. The Means to Attain Dependability
withholding of information)". A single definition for
security could be: the absence of unauthorized access to, The development of a dependable computing system
or handling of, system state. calls for the combined utilization of a set of four
In their definitions, availability and reliability techniques: fault prevention: how to prevent the
emphasize the avoidance of failures, while safety and occurrence or introduction of faults; fault tolerance: how
security emphasize the avoidance of a specific class of to deliver correct service in the presence of faults; fault
failures (catastrophic failures, unauthorized access or removal: how to reduce the number or severity of faults;
handling of information, respectively). Reliability and fault forecasting: how to estimate the present number,
availability are thus closer to each other than they are to the future incidence, and the likely consequences of faults.
safety on one hand, and to security on the other; 2.3.1. Fault Prevention
reliability and availability can be grouped together, and Fault prevention is attained by quality control
collectively defined as the avoidance or minimization of techniques employed during the design and manufacturing
service outages. of hardware and software. They include structured
programming, information hiding, modularization, etc.,

3
for software, and rigorous design rules for hardware. classes of faults that can actually be tolerated depend on
Operational physical faults are prevented by shielding, the fault assumption in the design process. A widely-used
radiation hardening, etc., while interaction faults are method of fault tolerance is to perform multiple
prevented by training, rigorous procedures for computations in multiple channels, either sequentially or
maintenance, "foolproof" packages. Malicious faults are concurrently. When tolerance of operational physical faults
prevented by firewalls and similar defenses. is required, the channels may be of identical design, based
on the assumption that hardware components fail
2.3.2. Fault Tolerance independently. Such an approach has proven to be
Fault tolerance is intended to preserve the delivery of adequate for elusive design faults, via rollback, however it
correct service in the presence of active faults. It is is not suitable for the tolerance of solid design faults,
generally implemented by error detection and subsequent which necessitates that the channels implement the same
system recovery. function via separate designs and implementations, i.e.,
Error detection originates an error signal or message through design diversity.
within the system. An error that is present but not Fault tolerance is a recursive concept: it is essential
detected is a latent error. There exist two classes of error that the mechanisms that implement fault tolerance should
detection techniques: (a) concurrent error detection, be protected against the faults that might affect them.
which takes place during service delivery; and (b) Examples are voter replication, self-checking checkers,
preemptive error detection, which takes place while ‘stable’ memory for recovery programs and data, etc.
service delivery is suspended; it checks the system for Systematic introduction of fault tolerance is facilitated by
latent errors and dormant faults. the addition of support systems specialized for fault
Recovery transforms a system state that contains one tolerance such as software monitors, service processors,
or more errors and (possibly) faults into a state without dedicated communication links.
detected errors and faults that can be activated again. Fault tolerance is not restricted to accidental faults.
Recovery consists of error handling and fault handling. Some mechanisms of error detection are directed towards
Error handling eliminates errors from the system state. both malicious and accidental faults (e.g. memory access
It may take two forms: (a) rollback, where the state protection techniques) and schemes have been proposed
transformation consists of returning the system back to a for the tolerance of both intrusions and physical faults, via
saved state that existed prior to error detection; that saved information fragmentation and dispersal, as well as for
state is a checkpoint, (b) rollforward, where the state tolerance of malicious logic, and more specifically of
without detected errors is a new state. viruses, either via control flow checking, or via design
Fault handling prevents located faults from being diversity.
activated again. Fault handling involves four steps: (a)
fault diagnosis that identifies and records the cause(s) of 2.3.3. Fault Removal
error(s), in terms of both location and type, (b) fault Fault removal is performed both during the
isolation that performs physical or logical exclusion of development phase, and during the operational life of a
the faulty components from further participation in service system. Fault removal during the development phase of a
delivery, i.e., it makes the fault dormant, (c) system system life-cycle consists of three steps: verification,
reconfiguration that either switches in spare components diagnosis, correction. Verification is the process of
or reassigns tasks among non-failed components, (d) checking whether the system adheres to given properties,
system reinitialization that checks, updates and records termed the verification conditions. If it does not, the other
the new configuration and updates system tables and two steps follow: diagnosing the fault(s) that prevented
records. Usually, fault handling is followed by corrective the verification conditions from being fulfilled, and then
maintenance that removes faults isolated by fault performing the necessary corrections.
handling. The factor that distinguishes fault tolerance Checking the specification is usually referred to as
from maintenance is that maintenance requires the validation. Uncovered specification faults can happen at
participation of an external agent. any stage of the development, either during the
The use of sufficient redundancy may allow recovery specification phase itself, or during subsequent phases
without explicit error detection. This form of recovery is when evidence is found that the system will not
called fault masking. implement its function, or that the implementation cannot
Preemptive error detection and handling (often called be achieved in a cost effective way.
BIST: built-in self-test), possibly followed by fault Verification techniques can be classified according to
handling is performed at system power up. It also comes whether or not they involve exercising the system.
into play during operation, under various forms such as Verifying a system without actual execution is static
spare checking, memory scrubbing, audit programs, or the verification. Verification a system through exercising it
so-called software rejuvenation, aimed at removing the constitutes dynamic verification; the inputs supplied to
effects of software aging before they lead to failure. the system can be either symbolic in the case of symbolic
The choice of error detection, error handling and fault execution, or actual in the case of verification testing,
handling techniques, and of their implementation, is usually simply termed testing. An important aspect is the
directly related to the underlying fault assumption. The verification of fault tolerance mechanisms, especially a)
formal static verification, and b) testing that necessitates

4
faults or errors to be part of the test patterns, that is availability: a measure of the delivery of correct service
usually referred to as fault injection. Verifying that the with respect to the alternation of correct and incorrect
system cannot do more than what is specified is especially service; (3) maintainability: a measure of the time to
important with respect to what the system should not do, service restoration since the last failure occurrence, or
thus with respect to safety and security. Designing a equivalently, measure of the continuous delivery of
system in order to facilitate its verification is termed incorrect service; (4) safety is an extension of reliability.
design for verifiability. This approach is well-developed When the state of correct service and the states of incorrect
for hardware with respect to physical faults, where the service due to non-catastrophic failure are grouped into a
corresponding techniques are termed design for testability. safe state (in the sense of being free from catastrophic
Fault removal during the operational life of a system damage, not from danger), safety is a measure of
is corrective or preventive maintenance. Corrective continuous safeness, or equivalently, of the time to
maintenance is aimed to remove faults that have catastrophic failure. Safety is thus reliability with respect
produced one or more errors and have been reported, while to catastrophic failures.
preventive maintenance is aimed to uncover and remove Generally, a system delivers several services, and there
faults before they might cause errors during normal often are two or more modes of service quality, e.g.
operation. The latter faults include a) physical faults that ranging from full capacity to emergency service. These
have occurred since the last preventive maintenance modes distinguish less and less complete service
actions, and b) design faults that have led to errors in deliveries. Performance-related measures of dependability
other similar systems. Corrective maintenance for design are usually subsumed into the notion of performability.
faults is usually performed in stages: the fault may be first The two main approaches to probabilistic fault-
isolated (e.g., by a workaround or a patch) before the forecasting, aimed to derive probabilistic estimates of
actual removal is completed. These forms of maintenance dependability measures, are modeling and (evaluation)
apply to non-fault-tolerant systems as well as fault- testing. These approaches are complementary, since
tolerant systems, that can be maintainable on-line modeling needs data on the basic processes modeled
(without interrupting service delivery) or off-line (during (failure process, maintenance process, system activation
service outage). process, etc.), that may be obtained either by testing, or
2.3.4. Fault Forecasting by the processing of failure data.
Fault forecasting is conducted by performing an When evaluating fault-tolerant systems, the coverage
evaluation of the system behavior with respect to fault provided by error and fault handling mechanisms has a
occurrence or activation. Evaluation has two aspects: (1) drastic influence on dependability measures. The
qualitative, or ordinal, evaluation, that aims to evaluation of coverage can be performed either through
identify, classify, rank the failure modes, or the event modeling or through testing, i.e. fault injection.
combinations (component failures or environmental
conditions) that would lead to system failures; (2) 3. Relating Survivability and Dependability
quantitative, or probabilistic, evaluation, that aims to The dependability concepts outlined above are the
evaluate in terms of probabilities the extent to which results of nearly twenty years of activity. Survivability
some of the attributes of dependability are satisfied; those can be traced back to the late sixties - early seventies in
attributes are then viewed as measures of dependability. the military standards, where it was defined as a system
The methods for qualitative and quantitative evaluation capacity to resist a hostile environment so that it can
are either specific (e.g., failure mode and effect analysis fulfill its mission (see, e.g., MIL-STD-721 or DOD-D-
for qualitative evaluation, or Markov chains and stochastic 5000.3).
Petri nets for quantitative evaluation), or they can be used Dependability has evolved from reliability/availability
to perform both forms of evaluation (e.g., reliability block concerns, along with the technological developments of
diagrams, fault-trees). the computing and communications field, in order to
The evolution of dependability over a system's life- respond adequately to the challenges posed by
cycle is characterized by the notions of stability, growth, increasingly networked applications, and by the increase
decrease that can be stated for the various attributes of in the necessary reliance we have to place on ubiquitous
dependability. These notions are illustrated by failure computing. Survivability, as it is understood in the
intensity, i.e., the number of failures per unit of time. It workshop (according to the call for participation: “ability
is a measure of the frequency of system failures, as of a system to continue to fulfill its mission in the
noticed by its user(s). Failure intensity typically first presence of attacks, failures, or accidents”) has evolved
decreases (reliability growth), then stabilizes (stable [25] from pure security concerns; it has gained much
reliability) after a certain period of operation, then prominence with the increase of frequency and severity of
increases (reliability decrease), and the cycle resumes. attacks by intelligent adversaries on mission-critical
The alternation of correct-incorrect service delivery is networked information systems.
quantified to define reliability, availability and From the perspective of the dependability framework,
maintainability as measures of dependability: (1) survivability is dependability in the presence of active
reliability: a measure of the continuous delivery of correct faults, having in mind all the classes of faults discussed
service — or, equivalently, of the time to failure; (2) in section 2.1. However, dependability and survivability

5
are actually very close to each other, especially when [9] A. Avizienis. Design of fault-tolerant computers. In
looking at the primitives for implementing survivability, Proc. 1967 Fall Joint Computer Conf., AFIPS Conf.
i.e., the “3 R’s”: Resistance, Recognition, and Recovery Proc. Vol. 31, pages 733-743, 1967.
[25]. Resistance, i.e., the ability to repel attacks, relates, [10] W.G.Bouricius, W.C. Carter, and P.R. Schneider.
in dependability terms, to fault prevention. Recognition, Reliability modeling techniques for self-repairing
th
i.e., the ability to recognize attacks and the extent of computer systems. In Proceedings of 24 National
damage, together with Recovery, i.e., the ability to restore Conference of ACM, pages 295-309,1969.
essential services during attack, and to recover full service [11] B. Randell. Operating systems: The problems of
after attack, have much in common with fault tolerance. performance and reliability. In Proc. IFIP Congress, Vol
Clearly dependability and survivability both go beyond 1, pages 281-290. North-Holland, 1971
the traditional approaches, based on fault avoidance, and [12] B. Randell. System structure for software fault
have recognized the necessity of fault tolerance. tolerance. IEEE Transctions on Software Engineering,
Dependability and survivability, via independent SE-1:1220-232, 1975.
evolutions, have actually converged and are much in [13] A. Avizienis and L. Chen. On the implementation of N-
agreement. version programming for software fault tolerance
It is evident that the coordinated best efforts of during execution. In Proc. IEEE COMPSAC 77, pages
dependability and survivability researchers and 149-155, November 1977.
practitioners will be needed to devise defenses against the [14] Special session. Fundamental concepts of fault
many threats to mission-critical systems. tolerance. In Digest of FTCS-12, pages 3-38, June 1982.
[15] J.C. Laprie. Dependable computing and fault tolerance:
Acknowledgment concepts and terminology. In Digest of FTCS-15, pages
2-11, June 1985.
We thank all colleagues who contributed to the 1992
book [16] and added their advice on desirable [16] J.C. Laprie, editor. Dependability: Basic Concepts and
Terminology. Springer-Verlag, 1992.
improvements and extensions during the writing of the
current document [22]. Many thanks to Dr. Yutao He, to [17] R. Turn and J. Habibi. On the interactions of security
th
Jackie Furgal and Christine Fourcade, who contributed to and fault tolerance. In Proc. 9 National Computer
the preparation of this text while the authors were Security Conf., pages 138-142, September 1986.
scattered around the globe. [18] J.E. Dobson and B. Randell. Building reliable secure
computing systems out of unreliable insecure
compnents. In Proc. of the 1986 IEEE Symp. Security
References and Privacy, pages 187-193, April 1986.
[1] D. Lardner, Babbage's calculating engine. Edinburgh [19] J.M. Fray, Y. Deswarte, D. Powell. Intrusion tolerance
Review, July 1834. Reprinted in P. Morrison and E. using fine-grain fragmentation-scattering. In Proc.
Morrison, editors, Charles Babbage and His 1986 IEEE Symp. on Security and Privacy, Oakland,
Calculating Engines. Dover, 1961. Apris 1986, pages 194-201.
[2] C. Babbage. On the mathematical powers of the [20] M.K. Joseph. Towards the elimination of the effects of
calculating engine (December 1837). Unpublished malicious logic: Fault tolerance approaches. In Proc.
Manuscript. Buxton MS7, Museum of the History of th
10 National Computer Security Conf., pages 238-244,
Science. In B. Randell, editor, The Origins of Digital
September 1987.
Computers: Selected papers, pages 17-52. Springer,
1974. [21] M.K. Joseph and A. Avizienis. A fault tolerance
approach to computer viruses. In Proc. of the 1988 IEEE
[3] Proceedings of the Joint AIEE-IRE Computer
Symposium on Security and Privacy, pages 52-58, April
Conference, December 1951.
1988.
[4] Information processing systems - reliability and
[22] A. Avizienis, J.-C. Laprie, and B. Randell. Dependability
requirements. In Proccedings of Eastern Joint
of computer systems: Fundamental concepts,
Computer Conference, December 1953.
terminology, and examples. Technical report, LAAS-
[5] Session 14: Symposium: Diagnostic programs and CNRS, October 2000.
marginal checking for large scale digital computers. In
[23] C.E. Landwehr et al. A taxonomy of computer program
Convention Record of the IRE 1953 National
security flaws. ACM Computing Surveys, 26(3):211-
Convention, part 7, pages 48-71, March 1953.
254, September 1994.
[6] J. von Neumann. Probabilistic logics and the synthesis
[24] Commission Of The European Communities.
of reliable organisms from unreliable components. In C.
Information Technology Security Evaluation Criteria.
E. Shannon and J. McCarthy, editors, Annals of Math
1991.
Studies, numbers 34, pages 43-98. Princeton Univ.
Press, 1956. [25] H.F. Lipson. Survivability — A new security paradigm
for protecting highly distributed mission-critical
[7] E.F. Moore and C.E. Shannon. Reliable circuits using
systems. Collection of transparencies, 38th meeting of
less reliable relays. J. Franklin Institute, 262:191-208
IFIP WG 10.4, Kerhonson, New York, June 28-July 2,
and 281-297, Sept/Oc. 1956.
2000, pp. 63-89. Available from LAAS-CNRS.
[8] W.H. Pierce. Failure-Tolerant Computer Design.
Academic Press, 1965.

6
 Defectele şi Erorile

Un circuit sumator se dovedeşte că are una din liniile sale de ieşire blocată permanent la valoarea
1, independent de valorile operanzilor săi.
Această situaţie descrie doar un defect fizic, nu o eroare (încă).
Defectul acesta va cauza o eroare atunci când sumatorul este utilizat iar rezultatul corect, pe linia
de ieşire defectă, este zero (nicidecum 1).
Timpul scurs între momentul apariţiei defectului fizic (este foarte greu de stabilit acest moment,
oricum) şi momentul producerii erorii poartă numele de latenţa erorii.
În literatură se apreciază că va fi mai dificil de detectat defectul fizic atunci când latenţa erorii este
mai lungă. O lungă latenţă a defectului sugerează că sunt mai puţine cazuri care fac vizibil
defectul fizic.
O latenţă lungă poate fi independentă de arhitectura şi stilul de proiectare al maşinii propriu-zise
(hardware-ul), chiar dacă sunt incluse în proiectarea acesteia criterii de largi de testabilitate fie şi
pe durata normală de operare (distincte de cele prevăzute să fie utilizate în regim de test – cum ar
fi tehnicile scan design etc.).
Un exemplu simplu ar putea fi o aplicaţie software care sumează de fiecare dată câteva numere
întregi având lungime mică (întregi scurţi) şi toate pozitive. O eroare în bitul de semn care
blochează acest bit în valoarea „0” poate fi extrem de dificil de detectat atâta vreme cât se va rula
această aplicaţie (casa de marcat a unei prăvălii de cartier, spre exemplu).
Sistemele de calcul care rulează aplicaţii de al căror rezultate depind acţiuni al căror risc poate fi
extrem de grav sunt periodic supuse unor testări cu largă acoperire a unui spectru de defecte
dinainte stabilite. Astfel de sisteme de calcul pot fi din domeniul aparaturii medicale, aplicaţiilor
spaţiale, supravegherii reactoarelor nucleare etc.
Aceste testări pot fi efectuate distinct de aplicaţiile curente (sesiuni dedicate) dar pot fi şi rulate
concurent (în paralel cu sarcinile nominale prin facilităţi dedicate de felul celor grupate sub
sintagma Built-In Self Testing – BIST).
Dispozitive dedicate stabilesc oportunitatea derulării desfăşurării unor sesiuni de teste, dinainte
stocate, având durate suficient de scurte ca să nu fie perturbate activităţile nominale. Odată
testele aplicate, rezultatele respective sunt comparate cu valorile corecte ale respectivelor teste.
Aceste rezultate, ale testelor aplicate, pot fi comparate direct cu rezultatele etalon. Dar, durata
comparaţiei poate fi un element limitativ al sesiuni de teste – timpul este adeseori un factor critic în
astfel de cazuri.
O comparaţie dintre semnătura rezultatelor determinate în sesiune de test şi semnătura
corespunzătoare funcţionării corecte, este în cele mai multe dintre cazuri preferată. Semnăturile,
șiruri de valori binare, au lungimi semnificativ mai scurte decât rezultatele propriu-zise (vectorii
binari) respective iar timpul de determinare al semnăturii este foarte puţin important deoarece
calculul semnăturii se derulează, practic, simultan cu producerea vectorilor rezultatelor.
 Defecte şi Erori în Software

Se consideră o rutină care calculează funcţia cos(x), spre exemplu.

Dar, eventual din cauza unei erori de programare rutina calculează modulul funcţiei respective,
adică calculează |cos(x)|.
Acest defect, această greşeală de programare, va cauza o eroare numai dacă respectiva rutina va
fi utilizată iar rezultatul corect este negativ.
Latenţa acestei erori va fi determinată dependent de datele pentru care se calculează această
rutină.
Defecte, Erori şi Consecinţe

Atât defectele cât şi erorile se pot răspândi prin sistemele digitale.

Dacă un circuit scurtcircuitează la masă linia de alimentare, atunci este foarte posibil ca acest
defect să provoace ca şi alte circuite din vecinătate să fie defecte.
Erorile se pot propaga prin sistem, în anumite condiţii, deoarece linia de ieşire a unui circuit este
conectată la liniile de intrare ale altor circuite.

Limitarea răspândirii erorilor

Proiectanţii introduc zone de conţinere în cadrul sistemelor şi / sau structurilor digitale.

Aceste zone induc bariere care diminuează mult șansele de propagare ale unei erori dintr-o zonă,
în care aceasta a luat naştere, în altă zonă conexă.
O zonă de conţinere, spre exemplu, poate fi creată prin crearea unor unităţi de alimentare
electrică separate, proprii pentru fiecare zonă de conţinere în parte.
Astfel, tensiunea electrică maximă a unei zone este independentă de tensiunea electrică maximă
a unei alte zone conexe.
Această abordare introduce, în fapt, o izolare electrică a unei zone în raport cu altă zonă.

Clasificarea defectelor hardware după durata

manifestării

Astfel, defectele hardware pot fi clasificate după durata manifestării:

permanente,
tranzitorii, sau
intermitente.
 Defectele benigne şi defectele maligne

Un defect care cauzează mal-funcţionarea unei singure unităţi de calcul, este numit un defect
benign. Defectele benigne sunt printre cele mai simplu de abordat.
Mult mai dificile sunt defectele care produce rezultate, aparent rezonabile, dar incorecte în fapt, ori
care trimit rezultate distincte unor receptori diferiţi.
Un senzor de altitudine care, spre exemplu, determină 8000 de metri spre aparatele din bordul
avionului dar trimite o determinare de 700 de metri spre instalaţia de aer. Acest defect poate fi
deosebit de delicat.
Astfel de defecte mai sunt numite şi defecte maligne ori Bizantine.
Care este categoria de utilizatori interesaţi de capacitatea unui sistem să fie tolerant la defecte?
- utilizatorii de sistem, indiferent de natura aplicaţiei.
Care sunt entitățile economico-sociale implicate?
(i) Universităţile: Cercetare, Dezvoltare şi aplicaţii,
(ii) Industria: Cercetare, Dezvoltare şi Aplicaţii.
 Consideraţii practice

Un sistem există într-un mediu (cum ar fi un robot submarin trimis să exploreze adâncurile
oceanelor, spre exemplu) şi are atât operatori cât şi utilizatori (posibil ca aceste două categorii sa
coincidă, uneori).
Un autovehicul, alt exemplu, este un sistem compus din câteva sute de componente, multe dintre
acestea fiind similare unor subsisteme de calcul rulând un software specific. Operatorul este
integrat acestui sistem.
Sistemul oferă un răspuns, un feedback, atât operatorului cât şi utilizatorului.
Operatorii sunt, tradiţional, reprezentaţi în interiorul sistemului întrucât procedurile acestora sunt,
uzual, parte componentă prin proiectarea sistemului.
Sistemele sunt dezvoltate să realizeze un set de operaţii are satisfac anumite cerinţe, stabilite prin
proiect.
Cerinţele pot adresa performanţele de viteză de calcul, suportul software (rutine cu caracter
tehnic, matematic etc.) şi multe altele.
O cerinţă importantă poate fi dependabilitatea ridicată a anumitor sisteme.
Dependabilitatea sistemelor poate fi obţinută prin toleranţa la defecte.
 Definiţia Dependabilității
oferită de Standardul IEC IEV 191-02-03:

“Dependabilitatea (este) un termen colectiv utilizat să descrie disponibilitatea performanţei precum

şi a factorilor ce-o influenţează:
fiabilitatea performanţei,
mentenabilitatea performanţei şi
mentenanţa suportului performanţei“

Această definiţie a fost stabilită de Comisia Tehnică 56 (care are ca sarcină Dependabilitatea) a
Comisiei Internaţionale de Electrotehnică (IEC).
Acest comitet dezvoltă şi întreţine, în continuare, Standardele Internaţionale focalizate asupra
dependabilităţii.
 Concepte fundamentale

Atributele cheie, esenţiale, ale sistemelor tolerante la defecte:

(i) Defect - Eroare – Mal-funcţionare
(ii) Performanţă - Disponibilitate - Fiabilitate

Un alt concept, mai recent introdus, este:

Capacitatea de supravieţuire (supravieţuibilitatea) a unui sistem.
Acest concept se referă la cuantificarea supravieţuirii sistemelor în urma producerii unor
evenimente catastrofale.
Includerea acestor atribute cheie încă din faza de proiectare este foarte probabil să conducă la
costuri mult mai mici ale acestor sisteme.
Toate fazele existenţei unui obiect digital pot contribui la atributele esenţiale ale sistemelor
tolerante în raport cu defectele.
Proiectarea, spre exemplu, poate constitui una dintre fazele cele mai prolifice ale defectelor de
funcţionare începând cu cele mai simple de tratat şi încheind cu cele mai dificile care pot
compromite produsul proiectat.
Tot din proiectarea unui produs se definesc compatibilităţile acestuia cu eventuale aduceri la zi
cauzate de schimbări tehnologice, ori cauzate de extinderi ale funcţionalităţii etc.
Mediul de funcţionare al unui produs ca şi regimul său de exploatare (continuu, pentru lungi durate
de tip ori cu întreruperi dese de funcţionare) pot impune soluţii de proiectare dar şi de întreţinere -
mentenanţă pro-activă specifice.
Un modul digital intenţionat să joace un rol cheie într-o aplicaţie cu cerințe severe de toleranţă la
defecte poate fi proiectat cu tehnici avansate de testare autonomă (built-in self test abreviat BIST)
ori chiar cu auto – diagnosticare şi auto-reconfigurare, eventual, pentru un nivel superior de
robusteţe la defectare.
Tehnicile cu auto-reconfigurare pot face ca anumite sisteme digitale să posede un comportament
deosebit de performant compatibil cu cerinţele celor mai stricte norme de funcţionare înalt-
tolerante la defectare.
În acest sens se pot cita situaţii concrete, cum ar fi:
• aplicaţiile nucleare,
• misiunile spaţiale cu echipaj uman la bord
• aplicaţiile medicale cu risc ridicat pentru viaţa pacienţilor aşa cum sunt serviciile de terapie
intensivă, ori tratamentele medicale prin iradiere controlată etc.
 Considerente istorice
asupra conceptului sistemelor tolerante la defecte

Sistemele tolerante nu reprezintă un concept nou, al ultimelor decenii.

Tehnologiile timpurii, în care s-au realizat primele calculatoare, nu excelau prin fiabilitate iar printre
abordările prin care se soluţiona situaţia dificilă a unor rezultate de încredere s-a numărat şi
toleranţa la defecte.
Primele calculatoare, construite cu tuburi electronice (dispozitive termo-electronice) consumau
puteri incredibile (de ordinul KW) comparativ cu sistemele actuale, ocupau volume importante
(cum ar fi etaje ale unor clădiri) şi aveau fiabilitate scăzută (existau echipe de tehnicieni care
patrulau în permanenţă prin clădirea sistemului de calcul şi schimbau tuburile defecte pentru
întreţinerea echipamentelor de calcul).
Primele abordări ale acestui concept datează din 1956, când J. von Neumann publică lucrarea:
„Probabilistic Logic and Synthesis of Reliable Organism from Unreliable Components”,
apărută la Princeton University Press.
Dezvoltarea programelor spaţiale a adus motivaţii suplimentare:
Întâi s-au dezvoltat tehnicile de toleranţă hardware,

Ulterior s-au dezvoltat şi conceptele de toleranţă software,

Reunirea celor două dezvoltări, menţionate anterior, a consolidat definitiv domeniul.

 Noi atribute ale produselor digitale în contextul modern al tehnologiilor integrate

o Densitatea crescută a dispozitivelor active, tranzistoare bipolare ori MOS complementare, a

făcut să crească probabilitatea apariţiei defectelor.

o Apariţia tehnologiilor sub-micronice şi presiunea financiară a piețelor au condus, adeseori, la o

verificare incompletă a corectitudinii proiectărilor dar şi produselor digitale în sine.

o Utilizarea tehnologiilor nanometrice a impus micşorarea puterii disipate prin creşterea

vertiginoasă a densităţii circuitelor integrate. Una dintre căile cele mai eficiente a fost micşorea
tensiunii de alimentare la tensiuni subunitare (mai mici decât un volt). Pentru aceasta au fost
necesare modificări ale tensiunii nominale de deschidere ale tranzistoarelor (în mod normal
tensiunile de deschidere pentru tranzistoarele MOS complementare sunt mai mari decât un volt).
Această modificare a tensiunii de deschidere a adus cu sine o creştere a curenţilor de pierderi
antrenând o altă sursă de putere disipată care până la tehnologiile nanometrice juca un rol cu mult
mai puţin important.
o Implementarea unor numeroase funcţionalităţi la nivelul circuitelor integrate, plăcilor ori
sistemelor au făcut să crească probabilitățile de mal-funcţionare severă a sistemelor.

o Cerinţele pieţii s-au concentrat asupra introducerii a unor sisteme hardware şi software cu
costuri mici, accesibile şi în acelaşi timp performante.
 Aspectele cruciale în dezvoltarea sistemelor tolerante la defecte

În dezvoltarea sistemelor tolerante la defecte cele mai importante etape sunt:

Proiectarea,
Analiza şi validarea proiectării,
Implementarea - Verificarea,
Testarea - Validarea şi
Evaluarea sistemului.

Pentru o mai clară expunere a diversităţii sistemelor tolerante la defecte dar şi a subansamblelor
acestora pentru care se consideră măsuri specifice de toleranţă a defectelor se vor cita câteva
exemple tipice:

Exemple I

În cazul sistemelor de uz general vor fi considerate două mari categorii:

(1) Cazul sistemelor PC:

Pentru sistemele PC sunt considerate în primul rând memoriile RAM având verificarea parităţii şi
posibil ECC (şi considerarea unei re-executări a operaţiei atunci când s-a detectat o mal-
funcţionare la nivelul acesta);
(2) Cazul staţiilor de lucru şi – sau Serverelor:

Cea de-a doua categorie a sistemelor de uz general este dedicată calculatoarelor pe care se
rulează aplicaţii profesionale. Pentru acestea sunt de maxim interes aceste capitole de
funcţionare:
Detectarea erorilor (hardware),
Ocazional acţiuni de corectare a erorilor (software),
Sistemele ECC (hardware),
Întreținerea unui log al erorilor (software).

Exemple II
Sistemele cu fiabilitate ridicată, sunt sistemele care cuprind aparatură digitală pentru
următoarele aplicaţii:
o Sistemele telefonice,
o Sistemele bancare, terminalele de tip bancomat (ATM),
o Sistemele burselor de valori,
o Educaţia asistată de calculatoare: examinări, note, proiecte etc.,
o Sistemele incluse în jocurile cu câştiguri imediate, ş.a.m.d.
Exemple III

Sistemele cu funcţionare critică şi sub-sistemele esențiale, deasemenea critice, pentru viaţa

unor persoane:

sistemele aflate în misiune, trimise în spaţiu, cu sau fără oameni la bord,

sistemele de asistenţă şi control ale aeronavelor,
sistemele de control ale reactoarelor nucleare,
sistemele de asistare a vieţii unor persoane aflate în stare critică (terapie intensivă, operaţii pe
cord deschis etc.).

Exemple IV

Sistemele cu fiabilitate ridicată dar şi cu funcţionare critică:

Sistemele care controlează semafoarele rutiere, feroviare, aeriene, balizele aeriene ale unor
clădiri etc.
Sistemele care controlează funcţionarea automobilelor (ABS sistemul de control automat al
frânării, dispozitivul de injecţie al carburanţilor, controlul aprinderii etc.).
Sistemele de asistenţă telefonică de urgenţă (accidente, cataclisme, incendii, etc.).
 Redundanţa

Toate sistemele tolerante la defecte introduc şi gestionează redundanţe.

Redundanţa este proprietatea unui sistem de a poseda mai multe resurse decât minimum necesar
pentru îndeplinirea sarcinilor ce-i revin respectivului sistem.
Pe măsură ce mal-funcţionările au loc se exploatează redundanţa şi se maschează în acest mod
mal-funcţionările şi se menţine, în ansamblu, nivelul dorit de funcţionalitate.

Formele de implementare ale redundanţei

Sunt patru forme de implementare ale redundanţei:

Hardware,
Software,
Informaţională şi
Temporală.

Defectele hardware sunt abordate prin redundanţă, de regulă, utilizând atât hardware, informaţie,
cât şi timp.
Redundanţa hardware statică

Redundanţa hardware statică se realizează prin includerea suplimentară, în sistem, a unor

module hardware. Aceasta face să se detecteze ori să se depăşească efectele unei componente
defecte.
Se pot utiliza două, ori trei procesoare - în locul unui singur procesor, spre exemplu.
Aceste procesoare realizează aceeaşi funcționalitate. Utilizând două procesoare se poate detecta
defectarea unui singur procesor.
Printr-o configuraţie cu trei procesoare care execută toate acelaşi program se poate evita
utilizarea rezultatului eronat al unuia dintre procesoare. Acesta este un exemplu de redundanţă
hardware statică. Scopul acesteia este mascarea imediată a defectului.

Redundanţa hardware dinamică

O formă diferită de redundanţă hardware este redundanţa dinamică.

În acest caz componentele aflate în rezervă, neutilizate, sunt activate ca urmare a detecţiei
defectării unei componente curent active.
Se utilizează, adeseori, o combinaţie de tehnici statice şi dinamice pentru realizarea redundanţei
hardware hibride.
Redundanţa hardware complexă

Redundanţa hardware poate să cuprindă formule care pot porni de la o simplă duplicare de unităţi
şi până la structuri elaborate care comută unităţi aflate în rezervă cu altele active dovedite defecte
etc.
Astfel de formule complexe de redundanţă hardware, implică costuri mari care sunt justificate doar
pentru sistemele critice.

Redundanţa informaţională

Cea mai cunoscută formă de redundanţă informaţională sunt codurile detectoare şi corectoare de
defecte.
Sunt utilizaţi biţi suplimentari, numiţi biţi de verificare, care sunt adăugaţi suplimentar biţilor
informaţiei iniţiale astfel încât o eroare în biţii de date poate fi detectată ori chiar corectată.
Astfel de coduri sunt mult utilizate în unităţile de memorie actuale, pentru protecţia împotriva
erorilor.
Este de reţinut că aceste coduri, ca oricare altă formă de redundanţă, necesită circuite
suplimentare pentru procesarea informaţiei suplimentare (biţii suplimentari etc.).
 Măsuri ale Toleranţei la Defecte

Deoarece toleranţa la defecte este capabilă să producă maşini de calcul cu un grad ridicat de
dependabilitate, sunt importante măsurile proprii prin care să se calibreze dependabilitatea.
Măsura, în general, este o abstracţie matematică care exprimă anumiţi factori relevanţi de
performanţă ai obiectului măsurat. Adesea măsurile sunt exprimate prin funcţii analitice. Se poate
aprecia că o funcţie analitică este o funcţie măsură dacă este definită prin valori pozitive. O
măsură, prin natura sa abstractă, cuprinde un subset al proprietăţilor obiectului căruia i se aplică.
Punctul critic în definirea şi utilizarea măsurilor este definirea acestora astfel încât acestea să
cuprindă un subset cât mai larg al proprietăţilor micşorând numărul de măsuri asociate
respectivului obiect.

Măsurile Tradiţionale – Fiabilitatea

Două dintre aceste măsuri sunt fiabilitatea şi disponibilitatea.

Fiabilitatea, notată tradiţional prin R(t), este probabilitatea (ca o funcţie de timp) ca sistemul să fie
funcţional continuu în intervalul de timp [0, t].
Fiabilitatea este potrivită aplicaţiilor în care un defect la un moment dat poate fie extrem de
costisitor.
Un bun exemplu în acest sens sunt procesoarele care controlează aparate de zbor, pentru care
un anumit defect poate să conducă la o catastrofă.
Timpul mediu până la o defectare

Strâns legate de fiabilitate sunt utilizate două măsuri.

Una este măsura numită Timpul Mediu Înaintea unei Defectări (Mean Time to Failure, abreviat
MTTF) iar cealaltă este Timpul Mediu Dintre Defectări (Mean Time Between Failures, în original
abreviat MTBF).
Prima măsură este timpul mediu dintre două defectări ale sistemului, iar a doua este timpul mediu
dintre două defectări.
Diferenţa dintre acestea se datorează timpului de reparaţie care urmează după prima defectare.
Introducând timpul mediu până la reparaţie (Mean Time To Repair, în original, abreviat MTTR),
rezultă această relaţie simplă, între aceste măsuri:

MTBF = MTTF + MTTR

Disponibilitatea

Această măsură, notată tradiţional prin A(t), este media fracţiunii de timp cât sistemul este
funcţional.
Ca măsură, este potrivită pentru aplicaţiile în care performanţa continuă nu este vitală dar, în
cazul în care totuşi sistemul este nefuncţional un timp semnificativ costurile sunt mari.
Un sistem de rezervări pentru bilete la zborurile de linie, spre exemplu, trebuie să fie intens
disponibil deoarece un timp mai lung de nefuncţionare poate îndepărta clienţii şi produce scăderi
ale încasărilor.
Un timp ocazional, foarte scurt de oprire este, pe de-altă parte, tolerabil pentru un sistem de
rezervări de bilete la zborurile de linie.
Disponibilitatea pentru un timp mai lung notată prin A se defineşte ca fiind limita către care tinde
A(t) atunci când t tinde la infinit:

Disponibilitatea A poate fi interpretată ca fiind probabilitatea ca sistemul să fie funcţional la un

moment aleatoriu de timp şi să fie semnificativă numai pentru sisteme care cuprind şi repararea
componentelor defecte.
Disponibilitatea pentru un timp suficient de lung poate fi determinată din măsurile MTTF şi MTBF
astfel:

A = MTTF / MTBF
Sisteme distribuite – Teorie
10. Toleranta la defecte

Decembrie 18, 2009

1
Defecte

„ Un sistem are un defect daca nu satisface

specificatiile sale
„ Gravitate:
‰ Un sistem distribuit de emitere de ordine pentru un
supermarket – un defect poate rezulta in lipsa la un
moment dat a conserve de fasole
‰ Intr-un sistem distribuit de control a traficului aerian, un
defect poate fi catastrofic
„ Tipuri:
‰ Defecte de componente
‰ Defecte ale sistemelor distribuite

2
Defectele componentelor
„ Se pot defecta datorita unor erori in procesor, memorie, dispozitiv,
cablu, sau software.
„ Un defect este o functionare proasta, posibil cauzata de
‰ Erori de proiectare,

‰ Eroare de manufacturare,

‰ Eroare de programare,

‰ Stricaciune fizica,

‰ Deteriorare in timp,

‰ Conditii proaste de mediu (a nins pe calculator),

‰ Intrari neasteptate,

‰ Eroare de operare,

‰ Rozatoarele au manca o parte,

‰ etc.

„ Nu toate defectele duc (imediat) la defecte de sistem, dar unele da.

3
Defectele componentelor - clasificare
„ Defecte tranzitorii apar o data si dispar
‰ Daca operatia este repetata defectul dispare

‰ O pasare care trece prin dreptul unui transmitator poate cauza o

pierdere de biti in anumite retele
‰ Daca timpul de transmitere expira si se reincearca, probabil va fi
functiona a doua oara.
„ Intr-un defect intermitent, apare neasteptat, dispare, reapare etc.
‰ Un contact care este pierdut va cauza adeasea un defect intermitent.

‰ Defectele intermitente cauzeaze probleme grave pentru ca sunt greu

de diagnosticat.
‰ Tipic, cand apare doctorul, sistemul lucreaza perfect.

„ Un defect permanent este unul care continua sa existe pana cand

componenta este reparata.
‰ Chip ars, bug de software, crash de hard disk.

4
Scopul proiectarii sistemelor tolerante la defecte

„ Asigurarea faptului ca intregul continua sa

functioneze corect, chiar si in prezenta
defectelor
„ Aborarea clasica: analiza statistica a
defectelor componentelor electrice
„ Pe scurt:
‰ Daca o componenta are probabilitatea p de
functionare proasta intr-o secunda, timpul mediu
de defectare este = l/p
‰ De exemplu, daca probabilitatea de defectare
este 10-6 per secund, timpul mediu de defectare 5

t 106 1 1 6 il
 Defecte ale sistemului
„ SD critice: sist trebuie sa supravietuiasca defectelor
componentelor (in particular, procesoarelor!), decat sa fie
faca acest lucru improbabil.
„ Defectele procesoarelor sau caderile pot fi intelese fie ca
defecte de procesor sau buguri software.
„ Combinatii de defect de procesor cu defecte de linii de
comunicare pot fi considerate,
‰ Deoarece protocoalele standard pot ajuta recuperarea din erori
de linii in modalitati predictibile,
vom examina numai defecte de procesor!

6
 Tipuri de defecte de of procesor
„ Defecte silentioase:
‰ Un procesor se opreste si nu raspunde la intrari succesive sau nu
produce alte iesiri, exceptand posibil ca nu nu mai produce.
‰ Numite de asemenea defecte-stop.

„ Defecte bizantine:
‰ Procesorul care produce defect va continua sa ruleze, transmitand
raspunsuri gresite la intrebari, posibil lucrand impreuna malitios cu alte
procesoare cu defect dand impresia ca lucreaza corect cand nu este
cazul
‰ Bugurile software nedectare adesea produc defecte bizantine.

‰ Tratarea defectelor bizantine este mult mai dificila decat cazul

defectelor silentioase.
‰ Termenul “bizantin" se refera la imperiul bizantin din perioada 330-
1453 din Balcani in care conspiratiile, intrigile si necredinta erau
comune in cercurile de conducere

7
 Sisteme “sincrone” vs. “asincrone”
„ Presupunere:
‰ Un sistem in care daca un procesor trimite un mesaj la altul, se garanteaza
faptul ca se primeste un raspuns in timpul T cunoscut in avans.
‰ Defectul de a obtine un raspuns pentru a obtine un raspuns inseamna ca
sistemul receptor a esuat.
‰ Timpul T include timp suficient pentru a trata pierderea mesajelor
(transmitandu-le de n ori).
„ Un sistem …
‰ … care are proprietatea ca intotdeauna sa existe un raspuns la un mesaj
intr-o margine cunoscuta daca este functional se spune ca este sicron.
‰ … neavand aceasta proprietate se spune ca este asincron.

„ Aceasta terminolgie intra in conflict cu utilizarea traditionala a lor; este utilizat in

masura mare in tolerarea defectelor.
„ Sistemele asincrone sunt mai complicat de tratat dect cele sincrone
‰ Daca un procesor poate trimite un mesaj si cunoastre absenta raspunsului
in T secunde inseamna ca recipientul s-a defectat -> poate lua o actiune
corectiva
‰ Nu exista o limita superioara pentru cat este necesar rapsunsului sa fie
receptionat -> determinarea daca a existat un defect va fi o problema.

8
 Utilizarea redundantei ca abordare generala
1. Redundanta informatiei
‰ Biti suplimentari sunt adaugati pentru a permite recuperarea
bitilor pierduri
‰ E.g. un cod Hamming poate fi adaugat pentru transmiterea
datelor pentru a permite recuperarea din zgomotele de pe linia
de transmitere
2. Redundanta in timp,
‰ Este efectuata o actiune, si apoi, daca este necesar, este
efectuata din nou.
‰ Exemple: utilizarea tranzactiilor atomice – daca tranzactia este
abortata, poate fi re-efectuata fara a produce probleme.
‰ Util in mod special cand defectele sunt tranzitorii sau
intermitente.
3. Redundanta fizica
9
Redundanta fizica
„ Echipament suplimentar este adaugat pentru a face posibil ca
intregul sistem sa tolereze pierderea sau functionarea proasta a
anumitor componente.
„ Exemplu: procesoare suplimentare pot fi adaugate la sistem
astfel incat numai o parte din ele se defecteaza, sistemul poate
inca functiona corect.
„ Doua modalitati de organizare acestor procesoare extra:
‰ Replicare activa
‰ Backup primar.
„ Exemplu: cazul unui server.
‰ Cand este utilizata replicarea activa, toate procesoarele
sunt utilizate tot timpul ca servere (in paralel) pentru a
aascunde complet defectele
‰ Schema de backup primar utilizeaza doar un procesor,
inlocuindu-l cu cel de backup cand se defecteaza.

10
Tolerarea defectelor utilizand replicarea activa
„ Utilizata in
‰ biologie (mamiferele au doi ochi, dou urechi, doi
plamani, etc.),
‰ avion (Boing 747 are patru motoare dar poate
zbura cu trei), and
‰ sport (referinte multiple in cazul pierderii unui
eveniment).
„ Anumiti autori se refera la replicarea activa
ca fiind abordarea starii masinii
„ Utilizata pentru tolerarea defectelor in circuite
electrice
‰ Circuitul in (a): 11
„ Semnalul trece prin dispozitivele A, B si C, in secventa.
 Redundanta modulara tripla

„ Presupunem ca elementul A2 se defecteaza:

‰ Fiecare dintre votati, V1, V2 si V3 primesc dou intrari bune (identice) si una
gresita, si fiecare dintre ele scot valoarea corecta in etapa a doua.
‰ In esenta, efectul defectului lui A2 este complet mascat, a.i. intrarile la B1, B2 si
B3 sunt exact la fel ca si cand n-ar fi existat defect.
„ Sa consideram in plus ca si B3 si C1, produc defect, in plus fata de A2.
‰ Aceste efecte sunt de asemenea mascate, a.i. cele trei iesiri finale sunt corecte.
„ La prima vedere nu este evident de ce sunt necesari trei votanti la fiecare
etapa.
‰ De fapt, un singur votant pote detecta si pasa informatia majoritara.
„ Totusi, un votant este de asemenea o componenta care poate esua.
‰ Pp., de exemplu, ca V1 functioneaza prost.
„ Intrarea B1 va fi gresita, insa B2 & B3 vor produce aceeasi iesire si V4, V5 & V6 vor produce
toate rezultatul corect in etapa 3.
‰ Un defect in V1 nu este diferit de un defect in B1 care produce o iesire gresita,
dar in ambele caz nu este votat mai tarziu.
„ TMR poate fi aplicat recursiv,
„ De exemplu, pentru a face un cip de incredere prin utilizarea TMR in acesta

12
Cata replicare este necesara?
„ Raspunsul depinde de cantitatea de tolerare a erorii care este dorita
„ Un sistem se spune ca este k-tolerand la defecte daca poate supravietui
defectelor in k componente si inca sa corespunda specificatiilor
„ Daca componentele, fie procesoarele, esueaza silentios,
‰ Atunci este suficicinet sa exista k + 1 procesoare pentru a oferi k-
toleranta la defecte.
„ Daca k dintre ele se opresc, atunci raspunsul de la cel ramas poate fi.
„ Daca procesoarele au defecte bizantine, continuand sa ruleze si cand sunt
defecte si trimit reapsunsuir eronate sau aleatore,
‰ Un minim de 2k + 1 procesare sunt necesare pentru a atinge k-
toleranta la defecte.
„ In cel mai rau caz, k procesoare defecte pot genera accidental (sau chiar
intentionat) acelasi raspuns.
„ Totusi, cele k + 1 ramase vor produce acelalasi rapsuns, a.i. clientul sau
votantul se poate increde in majoritate.

13
Tolerarea defectelor utilizand backup primar
„ Ideea esentiala a metodei de backup primara este aceea ca exista un
singur server care este primar si realizeaza ceea ce se cere
„ Daca acest primar es defecteaza, backupul preia sarcinile.
„ Ideall, acesta schimbare trebuie sa se faca intr-o modalitate cat mai clara si
vzibila numai sistemelui de operare al clientului, nu programelor aplicatii.
„ Aceasta schema este des utilizata in lumea reala:
‰ Exemple: guvernare (Vice-presedinte), aviatie (co-pilot), automobil (roata de
rezerva), generatoare de rezerva in camerele de operatii din spitale.
„ Toleranta da defecte bazate pe primar-backup are doua avantaje majore
fata de replicarea activa:
‰ Este mai simpla in timpul operatiilor normale pentru ca mesajele merg inspre un
server (primarul) si nu catre intregul grup.
‰ In practica este necesar un numar mic de masini, deoarece la un moment dat
este necesar un primar si un secundar
„ Dezavantaj
‰ Lucreaza slab in prezenta defectelor bizantine in care primarul declara in mod
eronat ca lucreaza bine.
‰ Recuperea dintr-o defectare a primarului poate fi complex si consumatoare de
timp.

14
 Un protocol simplu primar-backup pt. o operatie de scriere

„ Un client expediaza un mesaj catre primar, care realizeaza sarcina si apoi

expediaza un mesaj de actualizare catre backup.
„ Cand backupul primeste mesajul, efectueaz sarcina si expediaza un mesaj de
confirmare catre primar.
„ Cand vine confirmarea, primarul expediaza mesaj de raspuns la client.
„ Efectul caderii primarului in diferite momente ale RPC?
‰ Daca primarul cedeaza inainte sa efectueze sarcina (pas 2), nu se strica nimic.
„ Clientul va intra in time out si va reincerca.
„ Daca incearca destul, si eventual va reusi sa se efectueze sarcina o singura data.
‰ Daca primarul cedeaza dupa ce efectueaza sarcina dar dupa expedierea
actualizarea, cand backupul preia si cerintele vin din nou,
„ Lucrul va fi realizat de doua ori – daca acesta are efecte secundare, poate fi o problema.
‰ Daca primarul cedeaza dupa pasul 4 dar inainte de pasul 6,
„ Lucrul se poate termina efectuandu-se de trei ori, odat la primar, odata la backup ca rezultta
al pasului 3, si odata ce backupul devine primar.
‰ Daca cerinntele poarta identificatori -> posibil sa fie asigurat ca sarcina este realizata
numai de doua ori
„ Asigurarea ca este realizat numai o singura data este imposibil.

15
Cand sa se treaca de la primar la backup?

„ Backupul poate sa trimita mesaje: “Esti viu?" periodic catre

primar.
„ Daca primarul nu raspunde intr-un anumit timp, backupul poate
prelua.
„ Daca primarul nu s-a defectat, dar e mai incet,
‰ Intr-un sistem asincron nu exista nici o modalitate de a distinge
intre un primar incet si unul care s-a defectat.
‰ Solutia cea mai buna este un mecanism hardware in care
backupul poate opri sau reboota primarul.
‰ Toate schemele primar-backup necesita un acord, care este greu
de atins, pe cand replicarea activa nu cere intotdeauna un
protocol pentru acord (ex. TMR).
‰ O alta solutie este utilizarea un disk cu port dual intre primar si
secundar.
„ Cand primarul obtine o cerere, scrierea cererea pe disk inainte de a
efectua sarcina si de asemenea scrie rezultatele pe disk.

16
Acord in sistemele cu defecte
„ In numeroase SDuri exista o necesitate de a ajunge la un acord
asupra unui lucru
‰ Exemple sunt: alegerea unui coordonator, decizia de a
efectua o tranzactie sau nu, impartirea sarcinilor intre
lucratori, sincronizare, etc.
„ Scopul algoritmilor de acord distribuit: pentru a face ca toate
procesoarele defectuoase sa ajunga la consens in anumite teme,
dupa un numar finit de pasi.
„ Cazuri diferite sunt posibile depinzand de parametrii sistemului,
incluzand:
1. Sunt mesajele livrate cu incredere tot timpul?
2. Pot procesele sa cedeze, si in acest caz, se defecteaza silentios
sau bizantin?
3. Este sistemul sincron sau asincron?

17
 Cazul simplu
„ Procesoare perfecte + Liniile de comunicare pot pierde mesaje
„ O problema faimoasa, cunoscuta ca problema celor doua armate,
‰ Ilustreaza dificultatea de a pune doua procesoare perfecte de acord
asupra unui singur bit de informatie

‰ Armata rosie, cu 5000 de ostasi, este campata intr-o vale.

‰ Doua armate albastre, fiecare cu 3000 de ostasi, sunt campate in jurul
dealurilor inconjuratoare care domina valea.
‰ Daca cele doua armate albastre pot sa-si coordoneze atacul aupra
armatei rosii, vor fi victorioase.
‰ Totusi, daca ataca singure, vor fi macelarite.
‰ Scopul armatelor albastre este de a ajunge la un acord privind atacul.
‰ Problema este aceea ca pot comunica numai pe un canal nesigur:
expediind un mesager care este susceptibil de a fi capturat de armata
rosie.

18
 Examplu pt.problema celor doua armate
„ Comandantul armatei albastre 1, Gen.
Alexandru, trimite un mesaj la comandantul
armatei albastre 2, Gen.Bonaparte: “Intentionez
sa atac – hai sa atacam in zori de zi."
„ Mesagerul trece si Bonaparte il trimite inapoi cu
o nota spunand: “Idee splendida, Alex. Ne
vedem maine in zori."
„ Mesagerul ajunge cun bine la baza sa, livreaza
mesajul si Alexander spune trupelor sale sa se
pregateasca pentru batalie in zori.
„ Totusi, mai tarziu in acea zi, Alexandru isi da
19
seama ca Bonaparte nu stie ca mesagerul a
 Analiza exemplului celor doua armate
„ Pp. ca exista un anumit protocol care se termina intr-un numar finit de pasi.
„ Inlatura orice pas extra de la sfarsit si se poate obtine un prtocol care
functioneaza.
„ Un anumit mesaj este in acest caz ultimul si este esential pentru acord
(deoarece este protocolul minim).
„ Daca mesajul nu ajunge din cauza unui defect, razboiul inceteaza.
„ Expeditorul ultimului mesaj nu cunoaste daca ultimul mesaj a ajuns.
„ Daca nu stie, protocolul nu este complet si celalalt general nu va ataca.
„ Astfel expeditorul ultimului mesaj nu poate cunoaste ca razboiul este
planificat sau nu, sii deci nu poate implica trupele sale.
„ Deoarece receptorul ultimului mesaj cunoaste ca expeditorul nu poat fi sigur,
nu va risca a posibila moarte, si nu exista un acord.

!!!! Chiar cu procesoare ne-defectuoase (generali), acordul intre chiar si numai

doua procese nu este posibila in cazul unei comunicare care nu este de
incredere. !!!

20
 Caz secund
„ Comunicarea este perfecta, dar procesoarele nu-s.
„ Problema clasica si in acest caz apare dintr-o perspectiva militara si
este numita problema generalilor bizantini.
‰ Armata rosie este si in acest caz campata in vale, dar exista n
generali albastrii care conduc armate aflate pe dealurile apropriate.
‰ Comunicarea este realizata prin telefon si este perfecta,

‰ Dar m generali sunt tradatori (defectuosi) si incearca activ sa previna

generalii loiali sa ajunga la un acord prin furnizarea de informatii
contradictorii si incorecte (modeleaza proc.care functioneaza prost)
‰ Intrebare: pot generalii loiali sa ajunga la un acord?

‰ Fiecare general stie numarul de ostasi pe care-l are.

‰ Scopul problemei: pentru generali sa schimbe numarul de ostasi, a.i.

la sfarsitul algoritmului, fiecare general are un vector de lungime n
corespunzand tuturor trupelor albastre.
‰ Daca generalul i est loial, atunci elementul i este valoare corecta a
trupei sale; altfel, este nedefinit.

21
 Algoritmul recursiv a lui Lamport (1982)
„ Exemplu pentru n = 4 si m = 1 => 4 pasi
1. Fiecare general expediaza un mesaj (de incredere) la toti generaill anuntand
nr.ostasilor sai.
„ Generalii loiali spun adevarul; tradatorii pot spune fiecarui general o minciuna diferita.
„ (a) vedem ca generalul 1 raporteaza 1K, generalul 2 raporteza 2K, generalul 3 minte pe
fiecare, dand x, y, si z, iar generalul 4 raporteaza 4K.
2. Rezultatele anunturilor din pasul 1 sunt colectate impreuna in vectorul (b)
3. Pasul 3 consta in pasarea de catre fiecare general a vectorului sau de la (b) la fiecare
alt generalother general.
„ generalul 3 minte, inventand 12 valori noi,
„ Rezultatele pasului 3 sunt aratate in (c).
4. Pasul 4: fiecare general examineaza elementul ilea pentru fiecare a din vectorii noi
primiti.
„ Daca valoare are o majoritate, valoarea este pusa in vectorul rezultat.
„ Daca nici o valoare nu are majoritatea, elemnetul corespunzator este marcat ca UNKNOWN.
„ (c): generalii 1, 2, si 4 ajung la acord asupra (1, 2, UNKNOWN, 4), rezultatul corect.
„ Tradatorul n-a fost capabil sa saboteze decizia.

22
Alt exemplu
„ pentru n = 3 si m = 1, adica, numai 2 generali loiali si 1 tradator,
„ In (c): nici un general loial nu vede o majoritate pentru elementul
1, elementul 2, sau elementul 3, a.i. toate sunt marcate
UNKNOWN.
„ Algoritmul a esuat sa produca un acord.

23
Cazul general
„ Lamport a demonstrat ca un sistem cu m procesoare defectuoase,
acordul poate fi atins numai daca 2m + 1 procesoare corect
functionale sunt prezente, dintr-un total de 3m + 1.
„ Acordul este posibil numai daca mai mult decat doua treimi din
procesoare lucreaza corect.
„ Mai rau: Fischer a demonstrat ca intr-un SD
cu procesoare asincrone + intarzieri nemarginite in transmitere,
nu este posibil un acord chiar daca numai un procesor este
defectuos (chiar daca procesorul se defecteaza silentios).
‰ Problema sistemelor asincrone este aceea ca procesoarele
arbitrar incete nu se disting de cele care sunt oprite.
„ Numeroase rezultate teoretice sunt cunoscute pentru cazuri in care
acordul este posibil si cand nu este posibil.

24
 Sisteme Tolerante la Defecte

Redundanţa Informaţională a Datelor

Erorile în datele din sistemele de calcul pot apare atunci când datele sunt transferate
de la o unitate la alta, ori chiar de la un sistem la altul, sau atunci când datele sunt
stocate în unităţile de memorie.
Tolerarea acestor erori se poate realiza prin introducerea unor redundanţe în datele
respective. Aceasta este redundanţa informaţională. Forma aceasta, cea mai
răspândită, de redundanţă este codificarea.
Codificarea adaugă, datelor, biţi de verificare care permit validarea corectitudinii
respectivelor date utilizate şi, în anumite situaţii, chiar corectarea biţilor de date
eronaţi.

1. Codificarea

Codificarea este un domeniu de cercetare binecunoscut cu o practică reputată, mai

ales, în domeniul comunicaţiilor.
Atunci când se aplică codificarea un cuvânt de informaţie cu d biţi este codificat într-
un cuvânt de cod cu c biţi. Cuvântul de cod este, întotdeauna, mai lung decât cuvântul
de informaţie, c > d. Codificarea introduce informaţie redundantă.
Aceasta înseamnă că se introduce informaţie care nu este necesară, în mod evident,
pentru procesarea informaţiei. O consecinţă a informaţiei redundante este faptul că nu
toate cele 2c combinaţii de cod sunt cuvinte valide de cod.

110 111

010 011

100 101

000 001

Figura 1. Distanţele Hamming în spaţiul cuvintelor cu 3 ranguri binare.

Din acest motiv, se poate întâmpla ca atunci când se decodifică un cuvânt de cod
având c biţi, pentru regăsirea unui cuvânt original (iniţial) cu d biţi să se dovedească
că se operează cu un cuvânt incorect. Acest fapt indică incidenţa unei erori asupra
cuvântului de cod cu c biţi. Pentru unele dintre tipurile de scheme de codificare
anumite erori fi chiar şi corectate, nu numai detectate.
Un cod este definit ca fiind mulţimea tuturor cuvintelor de cod. Parametrii cheie ai
performanţei unui cod sunt numărul de biţi eronaţi care pot fi detectaţi dar şi numărul
de erori care pot fi corectate. Efortul impus de un cod anume este evaluat atât prin
numărul suplimentar de biţi cât şi prin durata codificării şi decodificării unui cuvânt
de cod.
O metrică importantă în spaţiul cuvintelor de cod este distanţa Hamming. Distanţa
Hamming dintre două cuvinte de cod este numărul de ranguri binare prin care cele

1
 Ion Bucur

două cuvinte diferă. În figura 1 sunt prezentate cele opt cuvinte ale codului cu trei
ranguri binare. Două cuvinte, în figura 1, sunt conectate printr-o muchie dacă acestea
diferă printr-un singur rang, adică au distanţa Hamming egală cu 1. Cuvintele 101 şi
011 diferă prin două ranguri şi, din aceste motiv, au distanţa Hamming 2. Pentru a
ajunge din nodul 101 în nodul 011 sunt parcurse minimum două muchii.
Se presupune că două cuvinte de cod valide diferă doar prin rangul binar cel mai puţin
semnificativ, aşa cum sunt codurile 101 şi 100. În această situaţie o singură eroare
care afectează bitul cel mai puţin semnificativ în oricare dintre cele două cuvinte ale
codului va trece neobservată deoarece cuvântul eronat este de asemenea un cuvânt de
cod valid, aparţinând codului. Dar dacă distanţa Hamming dintre două sau mai multe
cuvinte de cod are valoarea doi sau mai mare decât doi, atunci acest fapt garantează
că o eroare afectând un singur rang din două cuvinte de cod arbitrare nu va transforma
un cuvânt de cod într-un alt cuvânt de cod.

Distanţa unui cod este distanţa Hamming minimă dintre oricare două cuvinte de cod
valide. Codul care constă din patru cuvinte de cod {001, 010, 100, 111}, marcate prin
încercuire în figura 1, are distanţa 2 şi este, astfel, capabil să detecteze orice eroare
care afectează un singur bit. Iar codul care constă din cuvintele de cod {000, 111} are
distanţa trei şi are, din acest motiv, capacitatea să detecteze orice eroare singulară ori
dublă. Dar, dacă erorile duble sunt puţin probabile să apară, atunci acest cod poate fi
utilizat să corecteze orice eroare simplă, eroare asupra unui singur rang.
Pentru detecţia a până la k ranguri eronate, în general, distanţa de cod trebuie să fie cel
puţin k + 1, iar pentru corecţia a până la k erori distanţa de cod trebuie să fie minimum
2k + 1.

O altă proprietate importantă a codurilor este separabilitatea. Un cod separabil are

câmpuri separate de date şi de verificare. Pentru astfel de coduri procedeul de
decodare este foarte simplu. Procedeul constă din separarea rangurilor de date, de
rangurile dedicate verificării. Rangurile de verificare sunt procesate separat în vederea
corectitudinii datelor.
Un cod neseparabil, pe de-altă parte , are rangurile de date şi de verificare integrate
laolaltă iar extragerea datelor din cuvintele de cod necesită o oarecare procesare care
poate aduce cu sine o întârziere.

2. Codurile de paritate

Cele mai simple coduri sunt, probabil, cele de paritate. În forma sa fundamentală un
cod de paritate cuprinde d ranguri de date şi un rang, suplimentar, care reprezintă
paritatea. Într-un cod de paritate impară (pară), rangul suplimentar este stabilit astfel
încât suma tuturor valorilor nenule din cele d + 1 ranguri să fie impară (pară).
Raportul suplimentării codului de paritate este 1/d.

Un cod de paritate are o distanţă Hamming egală cu 2 şi este garantat să detecteze

toate erorile asupra unor singure ranguri. Dacă un rang trece din zero în unu, sau
invers, paritatea globală a cuvântului de cod s-a schimbat iar eroarea este detectată.
Codurile de paritate nu pot, totuşi, să corecteze orice eroare din cuvântul respectiv.

Deoarece codurile de paritate sunt coduri separabile, este imediată proiectarea

codificării parităţii respectiv a decodificării acesteia. În figura 2 sunt arătate circuitele
de codificare şi respectiv de decodificare pentru un cuvânt de date cu 5 ranguri.

2
 Sisteme Tolerante la Defecte

Codificatorul este alcătuit dintr-un sumator modulo-2 cu cinci linii de intrare care
generează o valoare zero dacă numărul de ranguri cu valoarea 1 este par.
Decodificatorul generează paritatea din biţii de date recepţionaţi şi compară paritatea
astfel generată cu cea sosită în bitul de paritate.
Dacă acestea coincid linia de ieşire a circuitului SAU-EX (XOR) este zero indicând că
nu s-a detectat nici o eroare.
În cazul în care paritatea generată şi paritatea recepţionată nu coincid, linia de ieşire
are valoarea 1 indicând prezenţa unei erori.
Este de reţinut că erori care afectează două ranguri ale cuvântului recepţionat nu pot
fi detectate prin verificarea parităţii. Un număr impar de ranguri eronate va fi, totuşi,
detectat.
b0 =1 b0 =1
b1 b1

=1 =1
b2 b2

=1 =1
b3 b3

=1 =1
bparitate
b4 b4

=1
Eroare
bparitate

(a) Codificatorul (b) Decodificatorul

Figura 2. Circuitele de calcul pentru bitul par de paritate.

Alegerea unei parităţi pare sau impare a bitului de paritate se determină în raport cu
erorile uni-direcţionale ale tuturor rangurilor. Altfel spus, care dintre erorile:
• toate rangurile se modifică în 0, respectiv
• toate rangurile se modifică în 1,
este mai probabilă.

Dacă, spre exemplu, se alege codul de paritate pară, bitul de paritate generat pentru
toate rangurile de date zero, va fi zero. Într-un astfel de caz, o eroare de felul toate
rangurile trecute în zero va fi nedetectată deoarece cuvântul eronat este un cuvânt
valid al codificării. Prin alegerea parităţii impare a rangului de paritate, acesta va
detecta defectul care face ca toate rangurile cuvântului să fie 0.

Pe de-altă parte, dacă defectul tot cuvântul are biţii 1 este mai probabil decât defectul
atunci toate rangurile trecute în zero, trebuie să se facă astfel încât să nu fie cuvânt
valid acela care are toate rangurile 1. În acest context trebuie ales modul impar de
calcul a bitului de paritate.

Au fost propuse şi implementate mai multe varietăţi ale rangului de paritate. Una
dintre acestea este cea care atribuie câte un bit de paritate la fiecare octet (byte).
Astfel, în loc să fie determinat un bit de paritate pentru un cuvânt (de 16 biţi, 32 biţi

3
 Ion Bucur

ori chiar mai mare) se atribuie câte un bit de paritate fiecărui octet. Acest mod face să
crească raportul dintre biţii de paritate şi cei de informaţie de la 1/d la n/d, unde prin
n s-a notat numărul de octeţi din cuvântul de date considerat.
Avantajul metodei este că pot fi detectate până la m defecte atâta vreme cât acestea
apar în octeţi diferiţi. Dacă defectele toţi biţii zero şi respectiv toţi biţii unu sunt la fel
de probabile atunci se poate alege ca biţii de paritate să fie calculaţi alternativ după
paritate pară şi respectiv paritate impară.
O alternativă a acestei metode este un bit de paritate întreţesut. Astfel, dacă lungimea
d a cuvântului de date este 64 atunci aceştia se vor nota respectiv prin a63, a62, … , a0.
Se vor utiliza opt biţi de paritate astfel încât primul va fi bitul de paritate al biţilor
aleşi astfel: a63, a47, a39, a31, a23, a15 şi a7, cei mai semnificativi biţi din fiecare dintre
cei opt octeţi ai cuvântului.
Similar, ceilalţi şapte biţi de pariate vor fi atribuiţi corespunzător grupurilor de biţi
întreţesuţi.
O astfel de schemă de paritate este benefică atunci când au loc scurtcircuite între biţii
adiacenţi ai cuvântului de date protejat (utilizarea magistralelor, este un bun exemplu
în acest sens). Suplimentar biţii de paritate pot fi alternaţi (calculaţi fie pentru paritate
pară, sau fie pentru paritate impară) între grupurile de biţi respectivi cu avantajul că
erorile unidirecţionale (toţi biţii 1 sau 0) pot fi de asemenea detectate.

0 0 0 1 1 1 1
1 0 1 0 1 1 0
1 1 0 0 0 0 0
0 0 0 1 1 1 1
1 1 1 1 1 1 0
1 0 0 1 0 0 0

Figura 3. Exemplul unei parităţi de acoperire.

O altă extensie a conceptului parităţii poate opera, de asemenea, chiar şi corecţii ale
erorilor. Cea mai simplă astfel de metodă implică organizarea datelor într-o matrice
bi-dimensională aşa cum se poate vedea în figura 3. Biţii de paritate sunt cei
reprezentaţi prin caractere îngroşate. Bitul de la sfârşitul unei linii reprezintă bitul de
paritate al respectivei linii. Analog, bitul situat la baza unei coloane reprezintă bitul de
paritate al acelei coloane. Schema de paritate pară utilizată este aceeaşi atât pentru
linii cât şi pentru coloane. Un singur bit eronat, oriunde în matrice, va conduce la
identificarea unei linii şi a unei coloane eronate. Deoarece o linie şi o coloană au
intersecţie unică în matrice, bitul eronat va fi identificat şi corectat.

Tehnica prezentată anterior este un exemplu de paritate suprapusă, în care fiecare bit
este acoperit prin mai mult decât un singur bit de paritate. Această manieră se poate
generaliza printr-o metodă mai cuprinzătoare de paritate suprapusă. Scopul
generalizării este să se ofere capacitatea identificării oricărui bit singular eronat.
Se presupune că sunt în total d biţi de date în total. Scopul generalizării constă în
găsirea numărului de biţi de paritate, pe de-o parte şi care biţi ar trebui să fie acoperiţi
prin fiecare bit de paritate, pe de-altă parte.

Dacă se notează prin r (redundanţi) numărul de biţi de paritate (de verificare)

adăugaţi celor d biţi de date, atunci sunt în total, în fiecare cuvânt codat d + r biţi.
Rezultă că sunt în total d + r stări de eroare, unde în starea i bitul cu rangul i al

4
 Sisteme Tolerante la Defecte

cuvântului codat este eronat. Suplimentar mai există o stare în care nu există nici un
bit eronat, aşa că sunt d + r + 1 stări care vor fi distinse, în total.
Trebuie reţinută ideea că se abordează cazul erorilor singulare, această schemă nefiind
proiectată să detecteze toate erorile care vizează doi biţi.

Defectele vor fi detectate prin implementarea a r verificări de paritate. Astfel, pentru

fiecare bit de paritate se verifică dacă paritatea generală a respectivului bit în raport cu
biţii acoperiţi este corectă. Aceste r verificări de paritate pot să genereze până la 2r
rezultate distincte. Cu aceasta se poate concluziona că numărul minim de biţi de
verificare r satisface relaţia:
2r ≥ d + r + 1 (1)

Modul de asociere al biţilor de date la biţii de verificare care-i acoperă urmează să fie
stabilit. Se asociază fiecăruia dintre cele d + r + 1 stări unul dintre cele 2r coduri
posibile ale biţilor de paritate. Exemplul următor ilustrează procedeul.

Tabelul 1.
Un exemplu de atribuire al valorilor de paritate la stări.
Starea Erorile de paritate Sindromul
Fără erori Niciuna 000
Bitul 0 (p0) eroare p0 001
Bitul 1 (p1) eroare p1 010
Bitul 2 (p2) eroare p2 100
Bitul 3 (a0) eroare p0, p1 011
Bitul 4 (a1) eroare p0, p2 101
Bitul 5 (a2) eroare p1, p2 111
Bitul 6 (a3) eroare p0, p1, p2 011

Exemplul 1. Se presupun patru biţi de date, notaţi respectiv prin a3a2a1a0.

Din relaţia (1) se determină imediat că r = 3, numărul minim de biţi de
paritate, notaţi în cele ce urmează prin p2p1p0. Există în total 8 (4 + 3 + 1)
stări pe care le poate lua cuvântul de cod. Cuvântul de cod complet arătă
astfel:
a3a2a1a0p2p1p0.

Aşa cum se poate remarca ultimii trei biţi din cuvântul de cod, cei aflaţi în
rangurile puţin semnificative, sunt biţii de paritate, în timp ce ceilalți biţi
sunt biţii de date.

4
p0 0 2 p2
6
3 5

p1

Figura 4. Atribuirea biţilor de paritate din Tabelul 1.

5
 Ion Bucur

Tabelul 1 prezintă o posibilă atribuire a rezultatelor verificărilor de

paritate în raport cu stările, care este ilustrată, de asemenea, în figura 4.
Raţiunea existenţei unei stări „fără erori” este evidentă, ca şi atribuirea
următoarelor trei stări în care un singur bit de paritate este eronat.
Atribuirea ultimelor patru stări, corespunzătoare unor erori în biţii de date
la cele patru coduri combinate ale biţilor de paritate poate fi operată în 4!
moduri distincte. Unul dintre modurile posibile este prezentat în tabelul 1
şi în figura 4.
Dacă, spre exemplu, doi biţi de paritate p0 şi p2 sunt eronaţi (şi doar
aceştia) aceasta arată că apare o problemă cu bitul din poziţia 4, mai exact
cu bitul a1.
Un bit de paritate va acoperi toate rangurile biţilor a căror eroare este
indicată prin verificarea de paritate corespunzătoare.
Astfel, bitul de paritate p0 acoperă rangurile 0, 3 şi 4 (aşa cum se poate
urmări în figura 4). Această proprietate corespunde, matematic, expresiei:

p0 = a0 ⊕ a2 ⊕ a3.

În mod similar se pot scrie relaţiile omoloage:

p1 = a0 ⊕ a2 ⊕ a3,
p2 = a1 ⊕ a2 ⊕ a3.

Pentru biţii de date a3a2a1a0 = 1100, biţii de paritate sunt p2p1p0 = 001.
Se presupune, acum, că pentru cuvântul de cod 1100001 are loc o eroare
care afectează un singur bit şi acest cuvânt devine 1000001. Se
recalculează biţii de paritate şi se obţine codul p2p1p0 = 111. Prin calculul
diferenţei (prin aplicarea bit cu bit a operatorului SAU-EX) dintre noile
valori ale biţilor de paritate şi cele anterioare rezultă 110. Această
diferenţă, numită sindrom, arată care bit dintre biţii cuvântului de cod este
eronat. Sindromul 110 arată, aşa cum se poate remarca din tabelul 1, că
bitul a2 este eronat iar datele corecte arată astfel: a3a2a1a0 = 1100.
Acest cod se numeşte cod Hamming (7,4) corector al unei singure erori.
Sindromul (rezultat verificării parităţii) poate fi calculat direct, într-un
singur pas, din biţii a3a2a1a0p2p1p0. Modul de calcul este cel mai bine
ilustrat prin operaţii matriceale în care toate sumele sunt calculate
modulo-2. Matricea de mai jos se numeşte matricea verificării parităţii:
⎡ a3 ⎤
⎢a ⎥
⎢ 2⎥
⎡1110100 ⎤ ⎢ a1 ⎥
⎢1101010 ⎥ ⎢ a ⎥ = s s s
⎢ ⎥ ⎢ 0 ⎥ [ 2 1 0]
⎢⎣1011001 ⎥⎦ ⎢ p2 ⎥
⎢ ⎥
⎢ p1 ⎥
⎢p ⎥
⎣ 0⎦
□

6
 Sisteme Tolerante la Defecte

Dacă 2r > d + r + 1, atunci este necesar ca d + r + 1 din cele 2r să servească drept

sindromuri. În astfel de situaţii este mai bine să se evite acele combinaţii care cuprind
un număr mare de unităţi.

Codul din tabelul 1 are capacitatea să corecteze o eroare care afectează un singur bit
dar nu poate detecta o eroare care afectează doi biţi (o eroare dublă). Astfel dacă apar
două erori în cuvântul de cod 11001, cauzând cuvântul de cod eronat 1010001
(rangurile a2 şi a1 sunt afectate de aceste erori) sindromul rezultat este 011 indicând
eronat că eroarea este în bitul a0. O cale de creştere a capacităţii detecției erorilor
este suplimentarea numărului de ranguri care servesc ca ranguri de paritate atât pentru
rangurile de date cât şi pentru rangurile de verificare.
Codul rezultat este un cod Hamming (8,4) capabil să detecteze două erori şi să
corecteze o singură eroare. Generarea sindroamelor pentru acest cod este prezentată în
continuare.
⎡ a3 ⎤
⎢a ⎥
⎢ 2⎥
⎡11111111 ⎤ ⎢ a1 ⎥
⎢11100100 ⎥ ⎢ a ⎥
⎢ ⎥ ⎢ 0 ⎥ = [ s3 s2 s1s0 ]
⎢11010010 ⎥ ⎢ p3 ⎥
⎢ ⎥⎢ ⎥
⎣10110001 ⎦ ⎢ p2 ⎥
⎢p ⎥
⎢ 1⎥
⎢⎣ p0 ⎥⎦

Ca şi mai înainte ultimii trei biţi ai sindromului arată bitul eronat care poate fi
corectat, atât timp cât primul bit s3 are valoarea 1. Deoarece bitul p3 este bitul de
paritate al tuturor celorlalţi biţi ( atât biţi de paritate cât şi de date), o singură eroare
modifică paritatea globală şi ca rezultat, bitul s3 trebuie să fie egal cu 1. Dacă bitul s3
este zero şi oricare alt bit de sindrom este 1, atunci s-a detectat o eroare dublă sau mai
mare.
Dacă o eroare afectează cuvântul de cod 11001001 şi produce cuvântul eronat
10001001, sindromul calculat este 1110, arătând, ca mai înainte, că bitul a2 este
eronat.
Dar dacă, apar două erori rezultând cuvântul de cod eronat 10101001, sindromul
determinat este 0011, indicând că a avut loc o eroare ne-corectabilă.
Un număr par de erori este detectabil, în timp ce un număr impar de erori, dar mai
mare decât 1, nu este distinctibil de o eroare ce afectează un singur bit şi implică o
corecţie eronată.

În mod curent circuitele de memorii, care au suport pentru corecţia unei singure erori
şi detecţia a două erori, utilizează coduri Hamming de forma (39,7) sau (72,8).

Deoarece apariţia unor erori între două sau mai multe celule de memorie adiacente
este mai probabilă, biţii unui singur cuvânt de memorie sunt adesea plasaţi în celule de
memorie care nu sunt învecinate, reducându-se astfel probabilitatea apariţiei unei
erori duble în cadrul unui cuvânt.

7
 Ion Bucur

Un dezavantaj al codurilor Hamming considerate, capabile să detecteze două erori şi

să corecteze o singură eroare, constă în faptul că acestea pot avea viteză mică de
utilizare. Calculul biţilor adiţionali de verificare, care sunt paritatea altor biţi de
verificare şi biţi de date, pot introduce penalizări considerabile prin procesele de
codificare şi decodificarea induse.
O cale de evitare a acestor penalizări dar păstrând capacitatea detecţiei erorilor duble
constă în atribuirea, atât pentru biţii de date cât pentru şi de verificare, a unor
sindroame alcătuite dintr-un număr impar de unităţi. De remarcat faptul că pentru
codul Hamming iniţial, corector de o singură eroare, sindroamele biţilor de verificare
cuprind câte o singură unitate.

2. Sumele de verificare

Sumele de verificare, sau sumele de control, sunt utilizate în primul rând pentru
detectarea erorilor în transmisiile de date prin canalele de comunicaţie. Ideea
fundamentală este sumarea informaţiei din blocul care urmează să fie transmis şi
transmiterea acestei sume împreună cu blocul de date. Receptorul transmisiei
calculează suma datelor receptate şi compară suma determinată, cu suma transmisă.
Dacă în urma comparaţiei celor două sume acestea nu coincid, atunci se poate afirma
că s-a determinat o eroare de transmisie.

0000 0000 0000

0101 0101 0101
1111 1111 1111 00000101
0010 0010 0010 11110010
0110 00010110 0111 11110111
(a) (b) (c) (d)

Figura 5. Varietăţi de calcul ale sumelor de verificare

(cu litere îngroşate sunt prezentate sumele de verificare rezultate).
(a) Simplă precizie. (b) Dublă precizie. (c) Reziduu. (d) Honeywell.

Există câteva varietăţi de sume de verificare. Se notează prin d numărul de cuvinte de

date transmise. În versiunea simplă-precizie, suma de verificare este calculată prin
însumare modulo-2d. În versiunea dublă-precizie, suma de verificare este calculată
prin însumare modulo-22d.
Figura 5 prezintă un exemplu pentru fiecare varietate de calcul al sumei de verificare.
Suma de verificare în simplă-precizie descoperă mai puţine erori decât suma de
verificare calculată în versiunea dublă-precizie, deoarece determină doar ultimii d biţi
din dreapta (rangurile cele mai puţin semnificative). Procedeul care determină suma
de control Reziduu ia în consideraţie transportul din rangul cel mai semnificativ pe
care-l întoarce şi-l adună la rangul cel mai puţin semnificativ.
În calculul sumei de verificare Honeywell se concatenează cuvintele în perechi
succesive şi apoi se determină suma de control în dublă-precizie (modulo-22d). Acest
mod de determinare al sumelor de control ţine seama de erorile care pot apărea în
aceleaşi ranguri binare.
Se consideră, spre exemplu, cazul înfăţişat în figura 6. Se remarcă faptul că linia care
transmite rangul a3 al fiecărui cuvânt este blocată la valoarea logică 0. Din cauza
acestui defect al liniei de transmisie, receptorul va stabili că suma de control trimisă şi

8
 Sisteme Tolerante la Defecte

cea determinată în urma transmisiei se potrivesc în cazul sumei de verificare

determinate în simplă-precizie.

Linie blocată la 0
a3

a2
Transmiţător Receptor
a1

a0

(a)

1000 0000
1011 0011 10001011 00000011
0000 0000 00001100 00000100
1100 0100
1111 0111 10010111 00010111
Transmis Recepţionat Transmis Recepţionat

(b) (c)

Figura 6. Comparaţie între sumele de control în simplă-

precizie şi Honeywell.
(cu litere îngroşate sunt prezentate sumele de verificare
corespunzătoare).
(a) Circuitul. (b) Simplă precizie. (c) Honeywell.

Pe de-altă parte suma de verificare Honeywell atunci când este calculată în raport cu
datele recepţionate va fi diferită în comparaţie cu suma recepţionată. Aceasta va face
să se producă semnalul de eroare. Toate sumele de verificare permit detecţia erorii dar
nu pot determina localizarea erorii. Din acest motiv întregul bloc de date trebuie
retransmis, dacă s-a detectat o eroare în blocul de date recpţionat.

3. Codurile M-din-N

Un cod M-din-N (M < N) este un excelent exemplu pentru categoria de coduri

detectoare de erori unidirecţionale. Erorile unidirecţionale sunt de aşa natură încât toţi
biţii îşi schimbă starea în acelaşi sens, fie din 1 în 0, fie din 0 în 1, dar niciodată în
ambele sensuri.

Într-un cod M-din-N fiecare cuvânt constând din N biţi are exact M biţi poziţionaţi în
valoarea 1, rezultând existenţa a CNM cuvinte de cod distincte.
Orice modificare a unui singur bit va conduce la modificarea numărului de unităţi din
cuvânt ajungându-se fie la M + 1 ori la M - 1 biţi poziţionaţi în 1. Erorile
unidirecţionale multiple pot fi şi acestea detectate, eventual.
Un exemplu foarte simplu şi clar de cod M-din-N este codul 2-din-5 care constă din 10
cuvinte de cod şi poate servi pentru codificarea cifrelor zecimale. Un exemplu de cod
2-din-5 este prezentat în tabelul 2.
Există 10! moduri diferite de atribuire a celor 10 cuvinte de cod cifrelor zecimale.
Atribuirea arătată în tabelul 2 corespunde ordinii naturale binare. Avantajul
fundamental al codurilor M-din-N rezidă în simplitatea conceptuală a acestora. Dar, pe

9
 Ion Bucur

de-altă parte, codificarea şi decodificarea acestora este devine relativ mai complexă, în
general, deoarece aceste coduri nu sunt separabile, aşa cum se-ntâmplă în cazurile
codurilor de paritate şi celor cu sume de verificare.
Tabelul 2
Codul 2-din-5 pentru cifrele zecimale
Cifra Cuvântul de cod
0 00011
1 00101
2 00110
3 01001
4 01010
5 01100
6 10001
7 10010
8 10100
9 11000

Se pot, la rigoare, genera coduri M-din-N separabile. Dacă sunt considerate, spre
exemplu, codurile M-din-2M atunci se adaugă M biţi de verificare la deja existenţii M
biţi utilizaţi pentru codificare astfel încât cuvântul de cod cu lungimea 2M biţi să
conţină exact M unităţi. Astfel de coduri sunt uşor de codificat şi decodificat dat au o
supra-lungime mare (100% sau mai mult) comparativ cu omoloagele lor neseparabile.
Astfel, pentru codificarea celor zece cifre zecimale ajungem să se genereze un cod 4-
din-8 având un nivel de redundanţă superior celui exemplificat în tabelul 2, codul 2-
din-5.

4. Codurile ciclice

În codurile ciclice codificarea datelor constă în multiplicarea, modulo-2, a cuvântului

de date printr-un factor constant iar produsul calculat reprezintă cuvântul codificat.
Decodificarea se face prin divizarea cu aceeaşi constantă. Dacă restul este nenul,
aceasta arată apariţia unei erori. Codurile se numesc ciclice deoarece pentru orice
cuvânt de cod an-1, an-2, …, a0, deplasarea circulară, ciclică, a acestuia a0, an-1, an-2, …,
a1, este de asemenea un cuvânt de cod. Codul cu 5 biţi constând din secvenţele binare:
{00000, 00011, 00110, 011000, 11000, 10001, 00101, 01010, 10100, 01001, 10010,
01111, 11110, 11101, 11011, 10111}, este un cod ciclic. Codurile ciclice au fost ţinta
unui efort susţinut de cercetare şi sunt larg utilizate în memorarea datelor dar şi în
comunicaţii. Teoria codurilor ciclice se bazează pe elemente de algebra discreta.
Astfel, se presupune că sunt utilizaţi k biţi pentru datele care se doresc codificate.
Cuvântul codificat având lungimea de n biţi se obţine multiplicând cei k biţi de date
printr-un factor care are n-k+1 biţi lungime.
În teoria codificării ciclice multiplicatorul este reprezentat printr-un polinom, numit
polinom generator. Unităţile şi zerourile din acest polinom sunt considerate ca fiind
coeficienţii unui polinom de gradul n-k. Astfel, dacă multiplicatorul cu 5 ranguri
binare este de forma 11001, atunci generatorul polinomial este:

G(X) = 1⋅X4 + 1⋅X3 + 0⋅X2 + 0⋅X1 + 1⋅X0 = X4 + X3 + 1.

Un cod ciclic utilizând un generator polinomial de gradul n-k şi în total n biţi

codificaţi se numeşte un cod ciclic (n, k).

10
 Sisteme Tolerante la Defecte

Aceste coduri sunt mult utilizate în aplicaţii cum sunt comunicaţiile fără fir, în care
canalele sunt adesea afectate de zgomot şi supuse unor rafale de interferenţe care se
soldează cu producerea de erori binare adiacente.
Pentru ca un polinom de gradul n-k să fie utilizat ca polinom generator al unui cod
ciclic (n, k) acesta trebuie să fie un factor al polinomului Xn – 1.
Polinomul X4 + X3 + 1, spre exemplu, este un factor al polinomului X15 – 1, putând
servi ca polinom generator pentru un cod ciclic (15,11).
Un alt factor al polinomului X15 – 1 este polinomul X4 + X + 1, care poate genera un
alt cod ciclic (15,11). Polinomul X15 – 1 are, în fapt, cinci factori primi:

X15 – 1 = (X + 1)( X2 + X + 1)( X4 + X + 1)(X4 + X3 + 1)( X4 + X3 + X2 + X +1).

Oricare dintre factorii acestuia ori produse de doi ori mai mulţi factori ai acestuia pot
servi ca polinom generator ai unui cod ciclic.
Produsul primilor doi factori (X + 1)( X2 + X + 1) = X3 + 1, spre exemplu, poate
genera un cod ciclic (15,12). Adunarea şi scăderea în aritmetica modulo-2 coincid,
astfel are loc egalitatea:
X15 – 1 = X15 + 1.

Codul ciclic (5,4), cu 5 biţi {00000, 00011, 00110, 011000, 11000, 10001, 00101,
01010, 10100, 01001, 10010, 01111, 11110, 11101, 11011, 10111}, menţionat
anterior, are ca generator polinomul X + 1, satisfăcând relaţia:

X5 – 1 = (X + 1)( X4 + X3 + X2 + X + 1).

Se poate verifica simplu faptul că X + 1 este polinomul generator al codului ciclic

(15,12) prin multiplicarea tuturor cuvintelor de cod cu patru biţi, începând cu 0000 şi
încheind cu 1111 prin acest polinom X + 1, ori 11 reprezentat în binar. Astfel,
cuvântul de date 0110 se reprezintă algebric prin polinomul X2 + X, iar acesta
multiplicat prin polinomul generator X + 1 rezultă: X3 + X2 + X2 + X = X3 + X
reprezentând cuvântul de cod cu 5 biţi 01010.
Multiplicarea prin polinomul generator poate fi realizată şi binar aritmetic, nu numai
prin calcul algebric modulo-2 aşa cum se poate remarca din figura 7:

1110 ×
11
1110
1110
10010

Figura 7. Codificarea cuvântului de date 1110

prin multiplicarea cu constanta de generare 11.

De reţinut faptul că un cod ciclic nu este un cod separabil, astfel biţii de date şi biţii de
verificare pentru exemplul din figura 7, nu sunt separabili în cuvântul de cod 10010.
Una dintre raţiunile cele mai importante ale utilizării largi ale codurilor ciclice constă
în faptul că multiplicarea şi divizarea prin polinomul generator se pot implementa în
hardware prin registre de deplasare şi porţi SAU-EX. O astfel de implementare permite
atât o codificare rapidă cât şi o decodificare foarte eficientă.

11
 Ion Bucur

Pentru exemplificare se va considera polinomul generator X4 + X3 + 1, corespunzător

multiplicatorului 11001. În acest sens se va considera circuitul prezentat în figura 8
unde sunt utilizate patru bistabile D astfel conectate, încât să formeze un registru
deplasare cu reacţie liniară (porţile SAU-EX).

O4 O3 O2 O1
=1 Date
D Q D Q D Q D Q =1 Codificate

Clk Clk Clk Clk

Date
Ceas

Figura 8. Circuitul de codificare al codului ciclic

(15,11) cu polinomul generator X4 + X3 + 1.

Este destul simplu de constatat faptul că în figura 8 circuitul multiplică serial datele
prin polinomul generator X4 + X3 + 1.

10001100101 ×
11001
10001100101
00000000000
00000000000
10001100101
10001100101
110000100011101
Figura 9. Exemplul unei multiplicări
modulo-2 în cadrul codificării unui cuvânt
de date cu 11 biţi prin polinomul
generator X4 + X3 + 1.

Coloana marcată în figura 9 arată modul în care se produce cel de-al cincilea bit al
produsului prin însumarea modulo-2 a fiecărui bit corespunzător din cuvântului de
date 10001100101. Cuvântul de date care urmează să fie codificat ciclic este introdus
serial în dispozitivul de codificare, începând cu rangul cel mai puţin semnificativ.
110000100011101 : 11001 = 10001100101
11001
10100
11001
11010
11001
11111
11001
11001
11001
00000

Figura 10. Decodificarea cuvântului de date recepţionat

prin divizarea în raport cu polinomul generator X4 + X3 + 1.

12
 Sisteme Tolerante la Defecte

Procesul de decodificare se realizează prin divizarea cuvântului de date codificat în

raport cu polinomul generator. O ilustrare imediată a procesului de divizare prin
polinomul X4 + X3 + 1 (respectiv 11001) este prezentată în figura 10. În cazul în care
mesajul a fost recepţionat fără erori restul împărţirii este nul, aşa cum era de aşteptat.
În cazul în care mesajul a fost modificat prezentând o eroare şi se recepţionează
mesajul 110000100111101 (eroarea este marcată prin îngroşare) divizarea prin
polinomul generator va produce un rest nenul, aşa cum se poate vedea din figura 11.

110000100111101 : 11001 = 10001100101

11001
10100
11001
11011
11001
10111
11001
11100
11001
001011

Figura 11. Decodificarea cuvântului de date recepţionat

conţinând o singură eroare şi restul nenul obţinut prin
divizarea în raport cu polinomul generator X4 + X3 + 1.

Se poate arăta că orice eroare care afectează un singur bit din cuvântul de date
codificat ciclic este întotdeauna descoperită. O eroare care afectează un singur bit
poate fi reprezentată prin polinomul Xi iar cuvântul de date codificat ciclic poate fi
reprezentat, în acest caz, astfel: D(X)G(X) + Xi, unde s-a notat prin D(X) cuvântul
iniţial de date şi prin G(X) polinomul generator al codului ciclic. dacă polinomul
generator al codului ciclic G(X) are cel puţin doi termeni atunci acesta nu va diviza
exact expresia D(X)G(X) + Xi şi în consecinţă se va genera un rest nenul. Aşa cum a
fost ales codul ciclic în aceste exemple se poate arăta că acesta are o distanţă
Hamming egală cu trei. Aceasta revine la a spune că acest cod ciclic poate detecta
orice pereche de biţi eronați independent de localizarea acestora în mesaj. Situaţia se
schimbă în cazul apariţiei a trei erori simultan prezente în mesajul recepţionat
codificat ciclic.
110000111010101 : 11001 = 10001101101
11001
10111
11001
11100
11001
10110
11001
11111
11001
11001
11001
00000
Figura 12. Decodificarea cuvântului de date recepţionat
conţinând trei erori neadiacente, reprezentate prin
caractere îngroşate.

13
 Ion Bucur

În figura 12 este înfăţişată situaţia în care cele trei erori nu sunt adiacente, dovedindu-
se că nu poate fi detectată prezenţa acestora (restul divizării mesajul eronat
recepţionat, prin polinomul generator este nul).
110000011011101 : 11001 = 10001110011
11001
10011
11001
10100
11001
11011
11001
10110
11001
11111
11001
00110
Figura 13. Decodificarea cuvântului de date recepţionat
conţinând trei erori adiacente, reprezentate prin caractere
îngroşate.

Dar, dacă cele trei valori binare sunt adiacente, atunci codul ciclic considerat le
detectează, aşa cum se poate vedea din exemplul prezentat în figura 13, restul ne-nul
arătând acest fapt.

O4 O3 O2 O1
=1 Date
D Q D Q D Q D Q =1
Decodificate

Clk Clk Clk Clk

Date Codificate

Ceas

Figura 14. Circuitul decodificator al codului ciclic

(15,11) cu polinomul generator X4 + X3 + 1.

Pentru determinarea unui circuit logic care sa efectueze decodificarea unui mesaj
transmis fără existe erori se va considera un exemplu practic. Se notează prin E(X) un
mesaj D(X) codificat ciclic prin schema logică din figura 8, în care se utilizează
polinomul generator G(X) = X4 + X3 + 1.
Dacă mesajul E(X) este recepţionat fără erori, adică restul împărțirii este nul, atunci
putem scrie că:
E(X) = D(X)⋅G(X).
Deoarece, în acest caz, polinomul generator G(X) = X4 + X3 + 1, se poate rescrie
relaţia anterioară astfel:
E(X) = D(X)⋅( X4 + X3 + 1),
sau încă:
D(X) = E(X) – D(X)( X4 + X3),
dar deoarece în cazul sumelor modulo-2 diferenţa este tot suma rezultă:
D(X) = E(X) + D(X)( X4 + X3).

14
 Sisteme Tolerante la Defecte

Circuitul corespunzător decodificatorului este înfăţişat în figura 14.

În multe aplicaţii de transmisia datelor este necesar să se asigure că orice rafală de

erori, cu lungimea 16 sau mai mică, este detectată. În acest scop sunt utilizate coduri
ciclice de tipul, (16 + k, k). Generarea polinoamelor de gradul 16 se va alege în aşa fel
încât numărul maxim de biţi de date este suficient de mare astfel încât să permită
utilizarea aceluiaşi cod (şi respectiv aceleaşi circuite de codificare şi decodificare)
independent de lungimea blocurilor de date codificate, în genere. Acestea sunt
polinoamele CRC-16 (CRC fiind abrevierea denumirii Cyclic Redundancy Check),

G(X) = (X + 1)(X15 + X + 1) = X16 + X15 + X2 + 1,

Iar polinomul CRC-CCITT este:

G(X) = (X + 1)(X15 + X14 + X13 + X12 + X4 + X3 + X2 + X + 1) = X16 + X12 + X5 + 1,

În ambele cazuri polinoamele de grad 16 divid polinomul Xn – 1 pentru n = 215 -1, dar
nu pentru orice valoare mai mică a parametrului n. Astfel, acest cod poate fi utilizat
pentru blocuri de date a căror mărime ajunge până la 215 – 1 = 32 767 biţi. În acest
sens, este util de remarcat faptul că blocurile mai scurte de date, decât 32 767 biţi, pot
fi tamponate cu un număr suficient de 0-uri la început, acestea fiind ignorate în
operaţiile de codificare şi decodificare.
O altă remarcă utilă priveşte numărul mic de coeficienţi nenuli anume doar patru.
Aceasta simplifică mult proiectarea circuitelor pentru codificare şi pentru
decodificare.

În transferurile de date prin Internet se utilizează mult codul CRC-32:

G(X) = X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1

Acest cod permite detectarea unor rafale de erori care pot conduce până la 32 de biţi
pentru blocuri de date având mărimea mai mică sau egală cu n = 232 – 1, biţi.

În cazul transmisiilor de date prin blocuri lungi, este mult mai eficient să se utilizeze o
codificare separabilă. Aceasta pentru că în această manieră se permite utilizarea
imediată a datelor primite fără să fie necesar să se aştepte primirea şi decodificarea
tuturor biţilor din cuvântul de cod. Un cod ciclic separabil va permite detecţia erorilor
independent de procesarea datelor propriuzise.
Există, din fericire, o cale simplă de generare a unui cod ciclic (n, k) separabil. Astfel,
în loc să se codifice un cuvânt de date de forma:

D(X) = dk-1Xk-1 + dk-2Xk-2 + … + d0,

prin multiplicarea acestuia cu polinomul sau generator G(X) de grad n-k, se adaugă
întâi (n-k) zerouri la polinomul D(X), obţinându-se polinomul:

D*(X) = dk-1Xn-1 + dk-2Xn-2 + … + d0 Xn-k .

Ulterior se divide D*(X) prin G(X) rezultând:

15
 Ion Bucur

D*(X) = Q(X)G(X) + R(X),

Unde R(X) este un polinom de grad mai mic decât n-k.

În sfârşit se formează cuvântul cod:

C(X) = D*(X) – R(X),

care va fi transmis. Acest cuvânt de cod cu n biţi va avea drept factor polinomul G(X)
şi pe cale de consecinţă dacă după divizarea acestuia se va obţine un rest nul, rezultă
că nu s-au înregistrat erori. În această codificare, D*(X) şi R(X) nu au nici un termen
în comun şi, astfel, primii k biţi din C(X) = D*(X) – R(X) = D*(X) + R(X) sunt biţii
iniţiali, originali, iar restul de n-k sunt biţi de verificare, făcând astfel codificarea
separabilă.

4. Codurile aritmetice

Codurile de erori aritmetice sunt acele coduri care sunt păstrate în cadrul unei anumite
mulţimi de operaţii aritmetice. Această proprietate permite detectarea erorilor care pot
avea loc pe durata execuţiei unei operaţii aritmetice din mulţimea de operaţii
aritmetice respective.

Se spune că un cod este păstrat în raport cu o operaţie aritmetică * dacă pentru orice
doi operanzi X şi Y, şi pentru entităţile codificate corespunzător X’ şi Y’, există o altă
operaţie aritmetică # pentru operanzii codificaţi astfel încât să fie satisfăcută relaţia:

X’ # Y’ = (X * Y)’. (4.1)

Această relaţie poate fi interpretată astfel:

Rezultatul operaţiei aritmetice # va produce acelaşi rezultat ca şi prin codificarea
rezultatului operaţiei * aplicată operanzilor X şi Y.

Codurile aritmetice se aşteaptă, de regulă, să detecteze toate defectele care afectează

un singur bit. Este de remarcat faptul că, totuşi, o eroare a unui singur bit dintr-un
operand sau dintr-un rezultat intermediar poate, adesea, să cauzeze o eroare a mai
multor biţi. La sumarea a doi operanzi binari un defect în rangului i al sumatorului
poate cauza erori, eventual, în toate rangurile n – i de ordin superior ale sumatorului.

Există două clase de coduri aritmetice:

• Codurile aritmetice separabile, şi
• Codurile aritmetice neseparabile.

Cele mai simple coduri neseparabile sunt codurile AN, obţinute prin multiplicarea
operanzilor printr-o constantă A.
Cu alte cuvinte, X’ din relaţia (4.1) se obţine prin A⋅X, iar operaţiile * şi # sunt
identice pentru adunarea şi înmulţire. Astfel, dacă A = 3, atunci se multiplică cu 3
fiecare operand cu 3 şi se verifică rezultatul unei adunări ori scăderi pentru a vedea
dacă acesta este un multiplu de 3 ori nu. Toate erorile de magnitudine care sunt
multipli a constantei A sunt nedetectabile. Prin urmare nu vor nu se vor alege valori
ale constantei A care sunt puteri ale lui 2 (baza numerelor din sistemele de calcul). O
valoare impară a constantei A va detecta toate defectele care afectează un singur digit,

16
 Sisteme Tolerante la Defecte

deoarece o astfel de eroare are magnitudinea 2i. Prin alegerea valorii A = 3, se ajunge
la cel mai convenabil cod AN care poate încă detecta toate erorile singulare.
Numărul 01102 = 610, este reprezentat în cod AN, cu A = 3, prin 0100102 = 1810. Un
defect al bitului cu rangul trei, spre exemplu, poate conduce la valoarea eronată
0110102 = 2610. Această eroare va fi simplu de detectat deoarece valoarea 26 nu este
un multiplu al lui 3.

Cele mai simple coduri aritmetice separabile sunt codul rest şi codul invers al restului,
care se mai numesc şi coduri reziduale. Pentru fiecare dintre aceste coduri se ataşează
un simbol de verificare, notat prin C(X), fiecărui operand X. pentru fiecare cod rest,
C(X) = X mod A = |X|A, unde A se numeşte modulul de verificare. În cazul codului
invers al restului, simbolul de verificare se calculează astfel:

C(X) = A – (X mod A).

Relaţia (4.1) se rescrie, în acest caz, astfel:

C(X) # C(Y) = C(X * Y).

Egalitatea anterioară se păstrează pentru sume şi produse deoarece se aplică

următoarele relaţii:

| X + Y |A = ||X|A + |Y|A|A,
| X ⋅ Y |A = ||X|A ⋅ |Y|A|A.
Exemplul 4.1
Considerând un exemplu simplu în care A = 3, X = 7, iar Y = 5, rezultă:
Resturile sunt |X|A = 1 şi |Y|A = 2.
În urma sumării celor doi operanzi se obţine:
|7 + 5|3 = ||7|3 + |5|3|3 = |1+2|3 = 0.
Multiplicând cei doi operanzi, se obţine:
|7 ⋅ 5|3 = 2 = ||7|3 ⋅ |5|3| = |1⋅2|3 = 2.
◊

Pentru împărţire se dovedește că ecuaţia X – S = Q ⋅ D, este satisfăcută, unde s-au

utilizat notaţiile: X este deîmpărţitul, D este împărţitorul, Q este câtul, iar S este restul.
Din acest motiv verificarea corespunzătoare restului arată astfel:
||X|A - |S|A|A = ||Q|A ⋅ |D|A|A

Exemplul 4.2
Considerând acelaşi exemplu simplu în care A = 3, X = 7, iar Y = 5, rezultă
Q = 1 iar S =2. Verificarea corespunzătoare a resturilor este:
||7|3 - |2|3|3 = ||5|3 ⋅ |1|3|3 = 2.
Scăderea din membrul stâng al expresiei precedente este efectuată prin
adunarea complementului modulo-3, adică: |1 + |3-2|3|3 = |1 + 1|3 = 2.
◊

Un cod rest având modulul de verificare A are aceeaşi magnitudine a erorii

nedetectabile ca şi codul corespunzător AN. Dacă A = 3, spre exemplu, vor fi
nedetectate doar erorile care vor modifica rezultatul printr-un multiplu faţă de trei.
Rezultă că toate erorile care constau din modificarea unui singur bit sunt întotdeauna

17
 Ion Bucur

detectabile. Mai mult, algoritmii de verificare corespunzători codului AN şi codului

rest sunt aceeaşi: în amândouă cazurile trebuie determinat restul modulo-A al
rezultatului. Chiar şi creşterea lungimii cuvântului, |log2A| este aceeaşi în ambele
cazuri.
Cea mai importantă deosebire apare din proprietatea de separabilitate. Unitatea
aritmetică a simbolului de verificare C(X) este complet separată de unitatea principală
de operare pentru entitatea X, în timp ce, în cazul codului AN, există o singură unitate
de calcul (de complexitate mai mare).
Un sumator cu cod rest este prezentat în figura 15. Blocul de detecţie al erorii
calculează restul modulo-A al sumei |X + Y|A iar acesta este comparat cu rezultatul
determinat de sumatorul modulo-A, |X|A + |Y|A . Dacă acestea sunt diferite, atunci este
determinată o eroare.

X
Sumator
X+Y

|X|A Detecţia Eroare

Erorii
Sumator
modulo-A
|Y|A
||X|A + |Y|A|A

Figura 15. Sumator cu verificarea separată a restului.

Codurile AN şi cu rest având A = 3 sunt cele mai simple exemple de clase de coduri
aritmetice (atât separabile cât şi neseparabile). Care utilizează valoarea parametrului A
de forma A = 2n − 1, n fiind un număr natural.
Această alegere simplifică mult calculul restului atunci când sunt operate împărţiri
prin A (necesare prin algoritmul de verificare) şi pentru acest motiv astfel de coduri
sunt numite coduri aritmetice cu costuri reduse. Calculul restului atunci când are loc
o împărţire prin A = 2n − 1 este simplu, deoarece ecuaţia:

| zi r i |r −1 =| zi |r −1 , r = 2n

permite utilizarea sumării modulo - (2n − 1) a grupurilor de n biţi, care alcătuiesc

numărul (fiecare grup are valoarea 0 ≤ zi ≤ 2n − 1).

Exemplul 4.3
Calculul restului atunci când numărul binar X = 11110101011 este împărţit
prin A = 7 = 23 − 1, se face astfel:
- se partiţionează X în grupuri de câte 3 biţi, începând cu ultimul bit
semnificativ. Aceasta conduce în cazul de faţă la următoarea grupare:
X = (z3, z2, z1, z0) = (11, 110, 101, 011).
- sumează aceste grupuri modulo-7, adică se sumează iar dacă apare
transportul din rangul superior acesta este re-întors la rangul inferior,

18
 Sisteme Tolerante la Defecte

deoarece acest transport are ponderea 8, iar |8|7 = 1. Calculul concret este
prezentat mai jos:
11 z3
+ 110 z2
1 001
+ 1 transportul se sumează la rangul cel mai puţin semnificativ.
010
+ 101 z1
111
+ 011 z0
1 010
1 transportul se sumează la rangul cel mai puţin semnificativ.
+ 011

În adevăr, restul modulo-7 al numărului binar X = 11110101011, este 3

acesta fiind restul modulo-7 al numărului 196310.
◊

Atât codurile separabile cât şi codurile ne-separabile se păstrează atunci când sunt
realizate operaţii aritmetice asupra unor operanzi fără semn. Dacă se doreşte şi
includerea operanzilor cu semn, atunci este necesar să fie codul complementabil în
raport cu R, unde R este fie 2n, sau 2n − 1 (n fiind numărul de biţi al operandului
codificat). În funcţie de alegerea valorii parametrului R se va determina dacă se va
opera într-o aritmetică cu complement faţă de doi (R = 2n) sau într-o aritmetică cu
complement faţă de unu (R = 2n − 1).
Pentru codurile AN , expresia R – AX trebuie să fie divizibilă prin A, iar aceasta
impune ca A să fie un factor întreg al R. Dar dacă este necesar ca parametrul A să fie
impar atunci aceasta exclude alegerea R = 2n, rămânând doar utilizarea
complementului faţă de 1.

Exemplul 4.4
Se consideră n = 4, atunci R are valoarea 2n – 1 = 15, pentru complementul
faţă de unu şi este divizibil prin A pentru codul AN cu codul A = 3.
Numărul X = 0110 este reprezentat prin 3X = 010010, iar complementul
acestuia (faţă de unu) este 101101 (echivalent zecimal 45), fiind divizibil
prin 3.
Dacă n = 5, atunci complementul faţă de unu R este 31 şi acesta nu este
divizibil prin A. Numărul X = 00110 este reprezentat prin 3X = 0010010,
iar complementul faţă de unu al acestuia este 1101101 (10910), nefiind
divizibil prin 3.
◊

Pentru codul cu rest (rezidual), cu valoarea modului de verificare A, trebuie

satisfăcută ecuaţia A - |X|A = |R – A|A. Acesta fapt conduce la concluzia că R trebuie să
fie întreg multiplu al lui A, implicând încă odată utilizarea complementului faţă de
unu. Se poate totuși modifica procedeul astfel încât să se utilizeze complementul faţă
de doi (cu R = 2n):

|2n – X |A = |2n – 1 – X +1 |A = |2n – 1 – X |A + |1|A.

Din acest motiv este necesară adăugarea unui termen corector |1|A la codul rezidual
atunci când se calculează complementul faţă de doi. De reţinut că parametrul A
trebuie să fie în continuare un factor al expresiei 2n – 1.

19
 Ion Bucur

Exemplul 4.5
Pentru codul rezidual cu A = 7, iar n = 6, R = 26 = 64 complementul faţă de
R − 1 = 63, este divizibil prin 7. Numărul 0010102 = 1010 are reziduul 3
modulo – 7. Complementul faţă de doi al numărului 0010102 este 110110.
Complementul lui |3|7 este |4|7, iar prin adunarea termenului de corecţie |1|7
se obţine 5, ceea ce este reziduul corect modulo-7 al numărului binar
110110 (echivalentul zecimal fiind 54).
◊

O corecţie similară este necesară atunci când sunt sumaţi operanzi reprezentând
complemente faţă de doi şi se generează un transport din rangul cel mai semnificativ
(cu ponderea 2n) în sumator. Un astfel de transport este neglijat în regulile de calcul
aritmetice ale complementului faţă de doi.

Exemplul 4.6
Se însumează numărul X = 110110 (în complement faţă de doi) cu numărul
Y = 001101. Se generează un transport din rangul cel mai semnificativ,
care este ignorat.
Din acest motiv trebuie scăzut termenul de corecţie |26|7 = |1|7 din reziduul
de verificare cu modulul A = 7, obţinând 3 ceea ce este evident reziduul
modulo-7 corect al rezultatului 000011.
110110 = X 101 = |X|7
+ 001101 = Y + 110 = |Y|7
1 000011 1 011
1 transportul din rangul maxim
100
- 1 termenul de corecţie
011

Modificările introduse anterior conduc la o interdependenţă a aritmeticii unităţii de

calcul cu unitatea de verificare care operează cu reziduurile. Astfel de interdependenţe
pot cauza situaţii în care o eroare din unitatea de calcul aritmetic se propagă în
unitatea de verificare iar prezența erorii este mascată. S-a demonstrat, totuşi că
apariţia unei singure erori a fost întotdeauna detectabilă.

Corectarea unei erori poate fi realizată prin utilizarea a două sau mai multe reziduuri
de verificare. Cel mai simplu caz este codul bi-rezidual. Acesta constă din două
reziduuri de verificare A1 şi A2.
Dacă n este numărul de biţi din operanzi, se aleg două constante naturale a şi b astfel
încât n este cel mai multiplu comun al celor două constante naturale a şi b.
Dacă A1 = 2a – 1, iar A2 = 2b – 1, sunt două reziduuri de verificare, atunci poate fi
corectată orice eroare a unui singur bit.

20
 Sisteme Tolerante la Defecte

ABORDAREA CONCURENTĂ A DEFECTELOR

Toate structurile resiliente descrise prin modul de interconectare al acestora pot fi

aplicate unei palete foarte largi de module, începând cu cele mai simple module logice
combinaţionale şi până la cele mai complexe microprocesoare ori chiar plăci complete
cu microprocesoare. Duplicarea completă a unor microprocesoare, care nu sunt
proiectate să fie utilizate în aplicaţii critice, poate impune un efort complex, posibil
prohibitiv de costisitor care, adesea, se dovedeşte nejustificat.

Pentru astfel de situaţii s-au dezvoltat modalităţi mai simple necesitând dotări
suplimentare mai puţin costisitoare. Aceste tehnici se bazează pe ipoteza că un astfel
procesor execută aplicaţii curente iar în cazul apariţiei unei erori aplicaţia, ori o parte
din aceasta, poate fi reluată şi re-executată dacă sunt îndeplinite două condiţii
esenţiale:

(1) eroarea este detectată iar cauza erorii este un defect de scurtă durată,
tranzitoriu,
(2) atunci când se reia execuţia aplicaţiei este foarte probabilă dispariţia erorii.

Simularea defectelor, experimente de injectare a defectelor şi analiza log-urilor de

erori ale sistemelor operaţionale au arătat că erorile, în mare lor majoritate, sunt
provocate de defecte tranzitorii.
Tabelul 1.
Efectele iradierii cu ioni grei [KGT89]
Benchmark Control flux Control Date Altele
permanent temporar latent
Quicksort 62% 8% 16% 8% 4% 2%

Defectele tranzitorii din microprocesoare afectează mai cu seamă controlul fluxului de

date şi instrucţiuni. Din aceste raţiuni, operarea tolerantă a defectelor în sistemele
digitale impune tehnici de abordare concurente ale erorilor.

Clasificarea erorilor din sistemele cu microprocesoare

Investigarea tipurilor de erori ca şi a efectelor acestora în sistemele cu

microprocesoare constituie un curent constant de cercetare. Pe măsură ce creşte
complexitatea şi viteza dispozitivelor digitale se dovedeşte necesară considerarea a
noi defecte şi tipuri de erori. În marea majoritate a cazurilor, complexitatea
dispozitivelor sau incompleta cunoaştere a structurii interne ori chiar a operării
constituie obstacole în constituirea modelelor defectelor la nivel coborât (nivelul
porţilor ori nivelul transferului la nivel de registre).

Tabelul 2.
Efectele injectării defectelor hardware asupra magistralei sistemului
Execuţie Adresa Adresă Adresă Cod Adresă Memorie
invalidă codului memorie citire operaţie scriere inexistentă
program operaţiei invalidă invalidă inexistent invalidă
[STDM82] 63% 59% 56% 44% 37% 19% 8%
[MQS90] 45% 72% 1% 9%

Astfel, este dificil de stabilit o estimare analitică a consecinţelor defectelor de nivel

inferior asupra comportamentului sistemelor, nivel superior. Toate consideraţii sunt

1
 Ion I. Bucur, note de curs

aplicabile, cu precădere, defectelor tranzitorii deoarece această clasă de defecte nu a

dobândit o deplină caracterizare.
Atunci când se cunoaşte structura dispozitivului investigat se poate apela la tehnici
bazate pe simulare. Această abordare s-a dovedit deosebit fructuoasă atunci când s-a
aplicat în faza de proiectare a dispozitivelor digitale. În faza prototipului
dispozitivului respectiv cele mai frecvente evaluări au la bază tehnici de injectare a
defectelor. O altă sursă de analize sunt fişierele de erori, log-urile de sistem, din faza
operaţională a dispozitivelor digitale.

Tabelul 3.
Efectele simulării injectării defectelor în procesoarele RISC [ORG92].
Erori Erori Alte Erori Erori Erori
controlul Date erori magistrale adresare de bază
fluxului
Efecte 33% 60% 7% 28% 8% 37%

Câteva din rezultatele cunoscute ale cercetărilor asupra erorilor din microprocesoare
sunt prezentate în tabelele 1, 2 şi 3. Sunt considerate erorile relativ uşor de detectat
din microprocesoare.
Tehnicile întrebuinţate sunt, între altele, simularea [ORG92], injectarea defectelor
prin iradiere cu ioni grei [KGT89], disturbaţiile de putere şi modificarea semnalelor
de pe magistralele sistemelor [MKS90], [STDM82].

Cel mai important rezultat al acestor studii este faptul că defectele tranzitorii şi
intermitente constituie principala cauză a defectării sistemelor digitale. Se estimează
că aceste categorii de defecte apar cu o frecvenţă de 10 până la de 30 de ori mai mare
decât defectele permanente. Aceasta conduce la concluzia că 90% din defectele
calculatoarelor sunt tranzitorii şi intermitente [SL81].

Defectele tranzitorii pot fi cauzate în primul rând de zgomotul sursei de alimentare

(variaţii ale frecvenţei de comutaţie), interferenţe electro-magnetice (reţele de
comunicaţii fără fir şi altele), ionizări ale razelor cosmice ori particule alfa din
materialele utilizate pentru încapsularea circuitelor.

Într-o mai mică măsură, defectele intermitente, pot fi cauzate de erori ale proiectării.
Printre acestea sunt menţionate câteva deficienţe tipice, cum ar fi:
• Depăşirea numărului liniilor de intrare în anumite porţi,
• Circuitele funcţionând cu semnale marginale,
• Oscilaţiile circuitelor cu stări (oscilaţii între stările active şi cele inactive) etc.

O concluzie esenţială a acestor studii a fost determinarea celor mai eficiente

mecanisme de detecţie a erorilor.
Printre acestea, în afară de verificarea datelor, sunt:
o verificarea fluxului de comenzi (controlul),
o verificarea modului de adresare al memoriei şi
o verificarea codurilor instrucţiunilor.

Este de reţinut că, verificarea codurilor instrucţiunilor este eficientă, mai cu seamă, în
cazul în care nu sunt utilizate toate codurile posibile pentru codificarea instrucţiunilor
procesorului.

2
 Sisteme Tolerante la Defecte

Tehnici de detecţie concurentă a erorilor

Aşa cum s-a dovedit pe cale experimentală, cea mai mare parte a defectelor sunt
defecte tranzitorii. Acest tip de defecte sunt dificil de evitat prin proiectare şi prin
testare pe durata procesului de manufacturare.
Testele clasice planificate sistematic, în afara rulajului normal al unui microprocesor,
sunt consumatoare importante de timp şi nu sunt capabile să detecteze defectele
tranzitorii. Sunt de preferat tehnici concurente on-line de detecţie a erorilor [KK07].

Se dovedeşte că unica abordare pentru creşterea dependabilităţii microprocesoarelor

sunt tehnicile de toleranţă a defectelor. Deoarece dependabilitatea unui sistem este
deosebit de sensibilă faţă de defectele nedetectate ori impropriu tratate [Sos94]
aplicarea tehnicilor de detecţie eficientă a erorilor este de extrem interes.

Întrucât defectele tranzitorii nu produc defecte permanente în sisteme, şansele de

recuperare sunt importante, cu atât mai mult atunci când acoperirea erorilor este mare
iar latenţa este mică (evitându-se răspândirea efectelor erorilor şi compromiterea
recuperării datelor).

Din punctul de vedere al nivelului la care se face verificarea, detectoarele concurente

de erori pot fi clasificate în trei mari clase:
• Circuitul
• Sistemul
• Aplicaţia

Cea mai simplă tehnică de acest tip mandatează executarea oricărui program de două
ori urmând ca utilizarea rezultatelor să fie condiţionată de congruenţa acestora.
Această abordare este, adesea, numită redundanţa temporală şi are drept urmare
directă reducerea cu 50% a performanţei sistemului de calcul. Tehnica aceasta nu
impune detectarea erorii.
Memoria
Magistrala
de date

Magistrala
de adrese
Procesorul Procesorul de
principal monitorizare

Figura 1. Detecţia erorilor prin utilizarea unui procesor

de monitorizare.

Dar, dacă este implementabil un mecanism care să detecteze erorile ce pot să apară pe
durata execuţiei unei instrucţiuni, atunci instrucţiunea respectivă trebuie re-executată,
preferabil după un anumit timp care să permită dispariţia defectului tranzitoriu.
O astfel de abordare care vizează doar re-execuţia unei singure instrucţiuni, la un
anumit moment, are un impact mult mai mic asupra performanţei, comparativ cu re-
execuţia în întregime a programului.
Au fost dezvoltate şi alte tehnici, care implică costuri mici, pentru tratarea concurentă
a erorilor.

3
 Ion I. Bucur, note de curs

În acest sens s-a introdus un procesor simplu destinat să monitorizeze fluxul de date şi
comenzi la nivelul procesorului principal. Un astfel de procesor de monitorizare mai
este numit şi procesor de veghe (watchdog).

Procesorul de monitorizare

Un astfel de procesor realizează concurent, la nivelul sistemului, detecţia erorilor prin

monitorizarea magistralelor sistemului care conectează procesorul şi memoria (aşa
cum se poate vedea în figura 1). Această monitorizare se focalizează, în primul rând,
asupra verificării controlului fluxului de date. Se verifică, astfel, faptul că procesorul
principal execută blocuri corecte de cod, în ordinea corespunzătoare.

Monitorizarea poate detecta erori hardware dar şi erori software care să aibă drept
urmare fie execuţia unor instrucţiuni eronate, fie a unor căi necorespunzătoare prin
aplicaţii.

V1

V2

V3 V4

V5

(a)

acceptă semnătura(V1); acceptă şi verifică semnătura (V1);

fie fie
acceptă semnătura (V2); acceptă şi verifică semnătura (V2);
fie fie
acceptă semnătura (V3); acceptă şi verifică semnătura (V3);
ori ori
acceptă semnătura (V4); acceptă şi verifică semnătura (V4);
acceptă semnătura (V5); acceptă şi verifică semnătura (V5);
ori ori
acceptă semnătura (V5); acceptă şi verifică semnătura (V5);

(b) (c)

Figura 2.
(a) Graful fluxului de control.
(b) Verificarea fluxului de control.
(c) Verificarea nodurilor şi a fluxului de control.

4
 Sisteme Tolerante la Defecte

Pentru realizarea monitorizării fluxului de control, este necesar ca procesorul să

primească informaţia care trebuie verificată. Această informaţie facilitează verificarea
în timp real a corectitudinii execuţiei programelor prin procesorul principal.

Informaţia care este furnizată procesorului de monitorizare (Figura 2.(a)), este dedusă
din Graful Fluxului de Control, denumire abreviată GFC. Acest graf reprezintă fluxul
de control ce trebuie să fie executat de procesorul principal.
Un nod din acest graf reprezintă un bloc compact de instrucţiuni, fără ramificaţii, din
secvenţa de calcul. Într-un astfel de bloc nu există instrucţiuni de salt spre instrucţiuni
din bloc ori spre alte instrucţiuni din afara blocului şi nici nu există alte salturi din
program care să ajungă la o instrucţiune din blocul considerat.

O ramificaţie reprezintă un flux de control permis, corespunzând adesea unei

instrucţiuni de salt. Etichetele din graf, numite semnături, sunt atribuite nodurilor din
GFC şi sunt stocate în procesorul de monitorizare împreună cu GFC.

Pe durata execuției aplicaţiei, semnăturile nodurilor curent aflate în execuţie sunt

trimise procesorului de monitorizare de la procesorul principal. În această manieră,
procesorul de monitorizare poate verifica validitatea căii curente din GFC
corespunzător.

Programul executat de monitorul de monitorizare pentru GFC din figura 2.(a) este cel
din figura 2.(b). Acest program de verificare va detecta orice cale invalidă din
execuţia programului, aşa cum ar fi calea {V1, V3}, spre exemplu. Dar, orice eroare
dintr-un nod (din secvenţa corespunzătoare nodului) nu va putea fi identificată, prin
acest sistem de monitorizare.

În vederea creşterii rezoluţiei procesorului de monitorizare ca să se poată detecta şi

erorile instrucţiunilor individuale se pot utiliza semnături calculate în locul
semnăturilor atribuite. Semnătura unui nod dat poate fi determinată prin sumarea
(modulo 2) a tuturor instrucţiunilor din nod prin orice altă sumă de control, ori cod
similar.

Ca şi în cazul precedent, semnăturile sunt stocate în procesorul de monitorizare şi

sunt, apoi comparate cu semnăturile determinate pe durata execuţiei programului de
procesorul de monitorizare. Programul care va fi executat de procesorul de
monitorizare pentru GFC din figura 2.(a) cu semnăturile calculate va fi cel din figura
2.(c).

Funcţionalitatea procesorului de monitorizare poate fi, în principiu, extinsă să acopere

o largă mulţime de erori ale datelor prin includerea unor aserţiuni în programul
executat de procesorul de monitorizare.
Aserţiunile sunt teste de rezonabilitate care verifică relaţiile predeterminate dintre
variabilele din program şi sunt, în acest sens, o generalizare a testelor de acceptanţă.

Aceste aserţiuni le introduce programatorul în program şi sunt mai degrabă o parte a

software-ului de aplicaţie.
O aserţiune, ca o entitate care serveşte pentru verificarea corectitudinii execuţiei unui
program, este o relaţie invariantă între variabilele programului. Aserţiunea este

5
 Ion I. Bucur, note de curs

inserată, de programator, în diverse puncte din program semnificând intenţia acestuia

de a-i asocia valoarea de adevăr în raport cu variabilele asociate respectivei aserţiuni.
Aserţiunile pot fi definite în baza specificaţiilor ori în raport cu anumite proprietăţi ale
algoritmului.
Utilizarea aserţiunilor pentru detectarea defectelor din hardware ori din software a fost
propusă în [And79] şi în [MMA84], spre exemplu.
Eficienţa utilizării aserţiunilor a fost dovedită prin măsurători [AB81]. Anumite
proiecte propuse să utilizeze aserţiunile sunt sofisticate şi au un grad înalt de
complexitate, deoarece s-a intenţionat nu doar detectarea erorilor dar şi recuperarea
ultimei stări verificate [LS84].

Creşterea performanţei prin verificarea aserţiunilor pe procesorul de monitorizare

poate fi întrucâtva diminuată din cauza transferurilor valorilor relevante pentru
aplicaţie de la procesorul principal spre procesorul de monitorizare. Aceste transferuri
pot fi, uneori foarte frecvente.
Mai mult, procesorul de monitorizare, prin introducerea aserţiunilor, devine mai
complicat deoarece acesta trebuie să aibă capacitatea să execute instrucţiuni aritmetice
şi logice, care până în acest punct nu erau necesare.

Există şi soluţii ingenioase care reuşesc să ţină la un nivel rezonabil efortul de calcul
al procesorului de monitorizare în cazul aserţiunilor. Codul aserţiunilor este depus în
memoria locală a procesorului de monitorizare ca o bibliotecă de funcţii. Dacă
procesorul de monitorizare verifică aplicaţiile în care fluxul de date este cunoscut şi
invariant atunci, procesorul de monitorizare poate să capteze datele necesare prin
supravegherea magistralei de date a procesorului verificat. Astfel de metode au fost
propuse pentru comutarea telefoanelor şi pentru sistemele de control a zborurilor.

În sistemele de uz general transferul datelor poate fi organizat printr-o memorie

partajată ori printr-o coadă de mesaje. Prima abordare necesită tehnici de sincronizare
mai complicate. Înaintea execuţiei programului acesta este modificat. Expresia
aserţiunii este înlocuită printr-o singură instrucţiune care transferă valorile
argumentelor aserţiunii şi identificatorul funcţiei de verificare (funcţia aserţiunii)
procesorului de monitorizare.

Codul aserţiunii este descărcat într-o memorie locală a procesorului de monitorizare.

Pe durata execuţiei programului, procesorul de monitorizare recepţionează datele şi
execută funcţia cerută. Dacă instrucţiunea logică reprezentată prin funcţia aserţiunii
este falsă atunci se semnalează o eroare.

Este posibilă evitarea utilizării aserţiunilor prin aplicarea unor tehnici superioare de
detecţie a erorilor (cum ar fi codurile evoluate de paritate etc.) implementate la nivelul
procesorului de monitorizare.

Prin introducerea procesorului de monitorizare s-a introdus un bloc de circuite de

verificare care este independent de circuitele verificate – sunt evitate astfel, erorile
comune ori corelate dintre cele două blocuri. Aceasta este o trăsătură esenţială a
utilizării procesorului de monitorizare.

6
 Sisteme Tolerante la Defecte

O protecţie similară poate fi introdusă în structurile duplex prin utilizarea diversităţii

tehnologice – utilizarea unor procesoare manufacturate distinct, provenind de la
producători diferiţi.

Separarea, diferenţierea, dintre procesorul de monitorizare şi procesorul principal

devine tot mai dificil de realizat în tendinţa actuală a microprocesoarelor de nivel
înalt, în care simpla monitorizare a magistralei procesor - memorie este insuficientă ca
să se determine care instrucţiuni vor fi eventual executate şi care au fost pregătite
speculativ şi vor fi pierdute, avortate.
Suportul procesării simultane a mai multor fire creşte complexitatea proiectării
procesorului de monitorizare.

Procesarea multi-fir pentru toleranţa defectelor

Procesoarele actuale de vârf realizează performanţe superioare atât prin exploatarea

procesării în bandă de asamblare cât şi prin paralelism. Tehnologiile nanometrice de
realizarea a circuitelor digitale facilitează mult paralelismul prin existenţa unor unităţi
funcţionale multiple ceea ce face posibilă execuţia suprapusă a cât mai multor
instrucţiuni este posibil.

Din cauza datelor şi a dependenţelor de control, cea mai mare parte a aplicaţiilor au
limite severe asupra paralelismului care poate fi iniţiat în fiecare fir de execuţie. Studii
efectuate asupra unor colecţii de programe etalon (benchmark-uri) au arătat că în
medie se pot suprapune doar aproximativ 1,5 instrucţiuni.

Prin prisma acestui rezultat, cea mai mare a timpului, marea majoritate a unităţilor
funcţionale vor rămâne în aşteptare, fiind ne-utilizate.
Un salt calitativ important prin comparaţie cu paralelismul este introducerea
simultaneităţii procesării multi-fir.

Elementul cheie al procesării multi-fir constă în execuţia în acelaşi timp, pe durata

aceluiași impuls de ceas, a unor instrucţiuni aparţinând mai multor fire.
Arhitectura microprocesorului trebuie dezvoltată corespunzător pentru ca să poată
asigura suportul corespunzător. Un registru numărător program este necesar pentru
fiecare dintre firele executate simultan în sistem.

Dacă setul instrucţiunilor specifică o arhitectură cu un set de k-registre fizice, atunci

execuţia simultană a n fire va cere cel puţin nk registre fizice (câte un set de registre
fizice pentru fiecare fir de execuţie). Arhitecturile avansate au şi registre care nu sunt
vizibile extern prin setul de instrucţiuni. Spre deosebire de registrele arhitecturale,
registrele interne sunt partajate de toate firele de execuţie simultane care partajează de
asemenea şi existenţa unei cozi comune.

Este necesar să se implementeze o politică corespunzătoare pentru pregătirea şi

pentru lansarea instrucţiunilor ca şi pentru atribuirea registrelor interne şi ale altor
resurse, astfel încât nici un fir să nu fie defavorizat.

Diferenţa dintre rularea unei aplicaţii pe un multiprocesor cu n procesoare şi pe un

microprocesor care rulează n fire constă din modul în care sunt atribuite resursele.

7
 Ion I. Bucur, note de curs

În cazul multiprocesoarelor, tradiţionale, fiecare procesor rulează un fir independent

iar acel fir va avea acces doar la unităţile funcţionale şi la registrele pe care le va
redenumi, asociate respectivului procesor.

În cazul sistemelor multi-fir există un set de fire care au acces la o mulţime de unităţi
funcţionale şi care redenumesc registre. Utilizarea acestor entităţi va depinde de
disponibilul paralelism din cadrul unui fir la un anumit moment. Aceasta situaţie se
poate schimba în timp, deoarece cerinţele de resurse din cadrul unui fir şi nivelul de
paralelism inerent se modifică în fiecare fir, simultan, de execuţie.

Utilizarea proceselor de execuţie multi-fir în scopul detecţiei defectelor deschide

oportunităţi de implementare a unor facilităţi de toleranţă la defecte.
Sfera de
replicare

Copia
primară
Compararea
ieşirilor
Copia
secundară

Figura 3. Sfera de replicare a celor

două fire de execuţie

În acest scop, pentru fiecare aplicaţie se deschid două fire independente de execuţie.
Aceste fire execută acelaşi cod şi se are în vedere să primească aceleaşi intrări.

Dacă operarea decurge corect atunci aceste fire produc aceleaşi ieşiri. O divergenţă a
ieşirilor denotă un defect şi se impun măsurile de recuperare corespunzătoare.
Ideea de bază este furnizarea aceluiaşi nivel de protecţie, împotriva defectelor
tranzitorii, ce poate fi oferit într-o abordare tradiţională care ar rula, în mod
independent, două copii ale aceleiaşi aplicaţii.

Pentru micşorarea penalizării cauzate prin re-execuţie, a doua execuţie a aplicaţiei

urmează întotdeauna prima execuţie. Cele două execuţii se vor numi copia primară şi
respectiv copia secundară a aplicaţiei. Avantajul acestei abordări constă în faptul că se
poate transmite informaţie de la copia primară, spre copia secundară pentru creşterea
vitezei de rulare a secundarei dar şi pentru micşorarea consumului de resurse al
acesteia.

Pentru cele două fire de execuţie independente dar identice, ca aplicaţie, se vor aloca
două seturi distincte de componente hardware.
Se vor aloca două seturi distincte de registre arhitecturale, astfel încât un defect dintr-
un registru utilizat într-un fir de execuţie nu avea nici un impact asupra execuţiei
celuilalt fir.

8
 Sisteme Tolerante la Defecte

Aceste considerente conduc la introducerea unei sfere de replicare. Unităţile replicate

pentru cele două fire de execuţie se spune că aparţin acestei sfere, iar cele care nu sunt
replicate sunt exterioare acestei sfere (Figura 3).

Fluxul de date traversează suprafaţa acestei sfere de replicare. Entităţile replicate sunt
stabilite în funcţie de costuri şi de suprasarcina pe care acestea le implică dar şi în
raport cu eficienţa implicată.
Toate elementele ce nu sunt cuprinse în sfera de replicare dar ar putea fi ţinta unor
potenţiale erori tranzitorii pot fi protejate prin alte mijloace, cum ar fi codurile
redundante auto-detectoare (auto-corectoare) etc.

Bibliografie

[AB81] D.M. Andrews and J.P. Benson. An automated program testing

methodology and its implementation. In Proc. 5th Int. Conf. Software
Eng., paginile 254-261, 1981.
[And79] D.M. Andrews. Using executable assertions for testing and fault
tolerance. In Proc. 9th Int. Symposium on Fault Tolerant Computing,
paginile 102-105, 1979.
[KGT89] J. Karlsson, U. Gunneflo, and J. Torin. The effect of heavy-ion induced
single event upsets in the mc6890e microprocessor. In Fault Tolerant
Computing Systems, volume 214 of Informatik Fachberichte, paginile
296-307. Springer Verlag, Berlin, 1989.
[KK07] I. Koren, and C.M. Krishna. Fault-tolerant Systems, Elsevier Morgan
Kaufmann, 2007.
[LS84] Y.H. Lee and K.G. Shin. Design and evaluation of a fault tolerant
multiprocessor using hardware recovery blocks. IEEE Trans. on Comp.,
33:113-124, February 1984.
[MEM85] A. Mahmood, A. Ersoz, and E.J. McCluskey. Concurrent system-level
error detection using a watchdog processor. In Proc. 15th Int.
Symposium on Fault Tolerant Computing, paginile 145-152, 1985.
[MM88] A. Mahmood, and E. J. McCluskey. Concurrent error detection using
watchdog processors – a survey. IEEE Trans. On Comp., 37(2):160-174,
1988.
[MMA84] A. Mahmood, E. J. McCluskey, and D.M. Andrews. Writing executable
assertions to test flight software. In Conf. rec. 18th Annual Asilomar
Conf. Circuits and System Conf., paginile 262-266, 1984.
[MQS90] H. Madeira, G. Quadros, and J.G. Silva. Experimental evaluation of a set
of simple error detection mechanism. Microprocessing and
Microprogramming, 30:315-520, 1990.
[SL81] D. P. Siewiorek and L. K. Lai. Testing of digital systems. Proceedings
of the IEEE, 69:1321-1333, October 1981.
[Sos94] J. Sosnowski. Transient fault tolerance in digital systems. IEEE Micro,
paginile 24-35, February 1994.
[STDM82] M.E. Schmid, R.L. Trapp, A.E. Davidoff, and G.M. Mason. Upset
exposure by means of abstraction verification. In proc. 12th Int.
Symposium on Fault Tolerant Computing, paginile 237-244, 1982.

9
 Sisteme Tolerante la Defecte

TOLERANŢA DEFECTELOR HARDWARE

Toleranţa defectelor hardware este abordarea cea mai evoluată în contextual general al
tehnicilor de calcul tolerante la defecte.
S-au dezvoltat şi se utilizează multe tehnici de toleranţă a defectelor vizând aplicaţii
care cuprind soluţii din domeniul telefoniei şi până în aplicaţii ale misiunilor spaţiale.
Iniţial aceste tehnici aveau drept obstacol esenţial costurile asociate hardware-ului
redundant. În timp costurile hardware-ului, în general, au scăzut şi nu mai constituie
un impediment financiar utilizarea structurilor digitale în tehnicile de toleranţă a
defectelor.
Mai mult, datorită costurilor convenabile actuale, se aşteaptă o creştere a utilizării
volumului hardware-ului în proiectarea arhitecturilor hardware tolerante la defecte.

Alte considerente intervin în limitarea utilizării actuale extensive a hardware-ului.

Printre acestea un rol important îl joacă puterea disipată în structurile digitale utilizate,
în general.
Viteza de
defectare

Faza
copilăriei
Faza
finală

Durata
(ani)

Figura 1. Curba caracteristică a vitezei de defectare pentru

structurile digitale

Viteza de apariţie a defectelor hardware

Viteza de defectare a componentelor hardware este unicul şi cel mai important

parametru utilizat în analiza fiabilităţii sistemelor hardware. Această viteză se referă
la numărul de defecte în unitatea de timp ce urmează să afecteze o componentă, iniţial
funcţionând corect, pe durata utilizării viitoare a acesteia într-un anumit sistem. Viteza
de defectare este influenţată de vârsta respectivei componente dar şi de şocurile de
tensiune ori ale altor parametri de funcţionare cum ar fi temperatura dar chiar şi
tehnologia de manufacturare poate avea o contribuţie importantă în acest sens.

Pentru o structură digitală, o unitate de calcul, dependenţa faţă de durata de utilizare

are, de regulă, alura unei căzi de baie, aşa cum se poate vedea în figura 1. Atunci când
componentele structurii digitale sunt începutul la funcţionării acestora, viteza de
defectare este pronunţată. Acest fapt se datorează întâmplării care face ca anumite

1
 Ion I. Bucur, note de curs

componente să treacă prin controlul de calitate al manufacturării şi chiar să fie

utilizate. Pe măsură ce trece timpul aceste componente sunt îndepărtate, viteza de
defectare scade, iar circuitele parcurg grosul duratei lor de funcţionare cu o viteză
relativ constantă de defectare. Pe durat utilizării lor aceste componente îmbătrânesc
lent, în timp, efectele uzurii încep să se facă simţite iar viteza de defectare începe să
crească din nou.

Impactul celorlalţi factori asupra unei componente este exprimat printr-o formulă
empirică care determină viteza de defectare a respectivei componente:

λ = π Lπ Q (C1π T π V + C2π E ) (1)

În relaţia (1) notaţiile au următoarele semnificaţii:

λ este viteza de defectare a componentei.
π L acesta cuantifică maturitatea tehnologiei de fabricaţie a componentei.
π Q reprezintă factorul de calitate, reprezentând controlul de calitate al procesului de
manufacturare (cu valori cuprinse între 0,25 şi 20,00).
π T simbolizează factorul de temperatură, cu valori cuprinse între 0,1 şi 1000. Acesta
este proporţional cu e − Ea / kT , unde s-a notat prin Ea energia de activare (în electron-
volţi) asociată tehnologiei, k este constanta lui Boltzmann (0,8625·10-4eV/K) iar prin
T s-a notat temperatura (măsurată în grade Kelvin).
π V reprezintă factorul de stres în tensiune pentru circuitele CMOS. Acest factor are
valori cuprinse în intervalul [1, 10], depinzând de tensiunea de alimentare şi de
temperatură. Nu se aplică altor tehnologii (pentru alte tehnologii are valoarea 1).
π E este factorul de şoc al mediului şi are valori foarte mici (aproximativ 0,4) atunci
când componenta este plasată într-un mediu cu aer condiţionat, similar celui unui
birou, dar poate lua valori mari (13,0) atunci când mediul este mai aspru.
C1 , C2 sunt factori de complexitate; sunt determinaţi funcţie de numărul de porţi dintr-
un circuit şi de numărul de pini ai capsulei.

Dispozitivele aflate, spre exemplu, la bordul autovehiculelor, ori în medii industriale

se pot defecta mai des decât alte dispozitive, similare, dar situate în aparate care
funcţionează în medii cu temperatură controlată (birouri cu aer condiţionat, bunăoară).

Viteza de defectare, fiabilitatea şi timpul mediu până la defectare

Se consideră o singură componentă, dintr-un sistem complex, care este funcţională de

la momentul t = 0 şi până când se defectează. Toate defectările, care pot să apară, se
presupune că sunt iremediabile şi au un caracter permanent.

Se notează, tradiţional, prin T durata de viaţă a componentei şi prin f(t) şi F(t) funcţia
de densitate a probabilităţii a duratei de viaţă şi, respectiv, funcţia de distribuţie
cumulativă a duratei de viaţă T. Aceste funcţii sunt definite doar pentru t ≥ 0, deoarece
timpul de viaţă nu poate fi negativ şi sunt exprimate analitic astfel:
t
dF (t )
f (t ) = , F (t ) = ∫ f (τ )dτ (2)
dt 0

2
 Sisteme Tolerante la Defecte

Funcţia f(t) reprezintă, dar nu este egală cu, probabilitatea de defectare la momentul t.
Astfel, pentru un interval de timp suficient de mic Δt, f(t)· Δt ≈ Prob{t ≤ T ≤ t + Δt}.
Deoarece f(t) este o funcţie densitate, aceasta trebuie să îndeplinească condiţiile:
∞
f(t) ≥ 0, pentru t ≥ 0 şi ∫ f (t )dt = 1.
0

Funcţia F(t) reprezintă probabilitatea defectării componentei la momentul t ori

înaintea acestui moment t.

F(t) = Prob{T ≤ t}

Fiabilitatea unei componente, notate prin R(t), este probabilitatea ca respectiva

componentă să supravieţuiască cel puţin până în momentul t este calculată prin
expresia:
R(t) = Prob{T > t} = 1 - F(t) (3)

Funcţia f(t) este asociată probabilităţii defectării unei noi componente la momentul t,
în viitor.
O noţiune cu mai multă semnificaţie este probabilitatea ca o componentă cu vârsta
curentă t să se defecteze într-un moment ulterior după un timp, suficient de scurt, cu
durata dt.
Aceasta este o probabilitate condiţionată, deoarece se cunoaşte faptul că respectiva
componentă a supravieţuit cel puţin până în momentul t.
Această probabilitate condiţionată este reprezentată de viteza defectării (numită de
asemenea şi viteza hazardului) unei componente la momentul t, notată prin λ(t), care
este determinată astfel:
f (t )
λ (t ) = (4)
1 − F (t )
dR(t )
Deoarece = − f (t ) , relaţia (4) devine:
dt
1 dR(t )
λ (t ) = − ⋅ (5)
R(t ) dt

Anumite tipuri de componente nu suferă vreo îmbătrânire, dar au o defectare care este
constantă în timp, λ(t) = λ. Pentru astfel de situaţii,
dR(t )
= −λ R(t )
dt
Iar soluţia acestei ecuaţii diferenţiale ( cu condiţia R(0) = 1) este:

R(t) = e-λt (6)

În consecinţă, o viteză de defectare constantă implică faptul că durata vieţii T a unei

componente are o distribuţie exponenţială, cu un parametru care este chiar viteza
constantă a defectării λ:

f(t) = λe-λt F(t) = 1 - e-λt R (t) = e-λt pentru t ≥ 0

3
 Ion I. Bucur, note de curs

În cazul unei componente ireparabile, timpul MTTF este egal cu media timpului de
viaţă (media variabilei T este notată, tradiţional, prin E[T]):
∞
MTTF = E[T ] = ∫ tf (t )dt (7)
0

dR(t )
Substituind = − f (t ) rezultă:
dt
∞ ∞ ∞
dR(t )
MTTF = − ∫ t dt = −tR (t ) |0 + ∫ R(t )dt = ∫ R(t )dt
∞
(8)
0
dt 0 0

(termenul –tR(t) este nul atunci când t = 0 dar şi atunci când t = ∞, deoarece R(∞)=0).

În cazul în care viteza defectării este constantă, pentru care R(t) = e-λt, rezultă că
∞
1
MTTF = ∫ e − λt dt =
0
λ
Se consideră, în cele mai multe situaţii, o viteză constantă a defectării. Acest fapt este
datorat, în primul rând, simplității calculelor.
Dar există cazuri în care această presupunere simplificatoare este inoportună. Zonele
copilăriei şi uzurii din figura 1 sunt două exemple, în acest sens.
Pentru aceste zone se utilizează distribuţia Weibull. Această distribuţie are doi
parametrii, λ şi β, şi are următoarea funcţie a densităţii timpului de viaţă T a unei
componente:
β
f (t ) = λβ t β −1e − λt (9)

Corespunzător viteza de defectare este:

λ (t ) = λβ t β −1 (10)

Această viteză de defectare este o funcţie crescătoare pentru β > 1, este constantă
pentru β = 1 şi este o funcţie descrescătoare pentru β < 1. Aceste proprietăţi fac
distribuţia aceasta foarte flexibilă şi în mod deosebit corespunzătoare pentru fazele
copilăriei şi uzurii componentelor. Fiabilitatea unei componente cu distribuţie Weibull
este:
β
R (t ) = e − λt (11)

Iar timpul MTTF al unei componente este:

Γ( β −1 )
MTTF = (12)
βλ β −1
∞
Unde Γ( x) = ∫ y x −1e− y dy este funcţia Gamma. Această funcţie este generalizarea
0

funcţiei factorial pentru numere reale şi are următoarele proprietăţi:

(i) Γ( x) = Γ( x − 1) pentru valori x > 1;

(ii) Γ(0) = Γ(1) = 1;
(iii) Γ(n) = (n − 1)! , pentru n natural, n > 0.

4
 Sisteme Tolerante la Defecte

Este de remarcat faptul că distribuţia Weibull include ca un caz particular (pentru β =

1) distribuţia exponenţială cu viteză constantă a defectării.

Structurile canonice şi resiliente

Se vor considera câteva dintre structurile canonice, cu ajutorul cărora se pot construi
alte structuri mai complexe.
Pentru început se vor aborda structurile de bază, structurile serie şi paralele.

Sistemele serie şi paralele

Cele mai cunoscute structuri sunt structurile serie şi paralele de sisteme, aşa cum se
pot vedea în figura 2. Un sistem serie se defineşte ca fiind un set de N de module
conectate împreună astfel încât defectarea unui modul face ca întreg sistemul să cadă.
Este de reţinut că diagrama din figura 2a este o diagramă de fiabilitate şi nu constituie
întotdeauna şi o diagramă de funcţionare electrică.

(a) Sisteme Serie.

(b) Sisteme paralele.

Figura 2. Sisteme serie şi paralele.

Cele patru module din diagrama 2a pot reprezenta, spre exemplu, unitatea de
decodificare a instrucţiunii, unitatea de execuţie, memoria imediată (cache) şi
memoria imediată de instrucţiuni a procesorului. Aceste patru unităţi trebuie să
funcţioneze fără erori pentru ca microprocesorul să funcţioneze corect. Se poate
remarca diferenţa dintre diagrama de fiabilitate şi diagrama electrică.

Presupunând că modulele din figura 2a se defectează independent unul de celălalt,

fiabilitatea întregului sistem serie este produsul fiabilităţii modulelor acestuia. Se
notează prin Ri(t) fiabilitatea modulului i şi prin Rs(t) fiabilitatea întregului sistem:

N
Rs (t ) = ∏ Ri (t ) (13)
i =1

Presupunând că modulul i are o viteză constantă de defectare λi, atunci în

conformitate cu relaţia (6), Ri (t ) = e− λit , iar relaţia (13) se rescrie astfel:

5
 Ion I. Bucur, note de curs

RS (t ) = e− λS t (14)

N
În relaţia (14) s-a notat prin λS = ∑ λi . Din (14) se poate vedea că sistemele serie au
i =1

o viteză de defectare (cădere) constantă egală cu λS (suma vitezelor individuale de

1
cădere) iar MTTF pentru sistemele serie este MTTFS = .
λS

Un sistem paralel se defineşte ca fiind un set de N module conectate laolaltă astfel

încât sistemul se defectează atunci când toate modulele acestuia se defectează.
Această proprietate conduce la următoarea expresie a fiabilităţii unui sistem paralel,
notată prin Rp(t):
N
R p = 1 − ∏ (1 − Ri (t )) (15)
i =1

Presupunând că modul i are viteza de defectare λi, atunci

N
R p = 1 − ∏ (1 − e − λit ) (16)
i =1

Fiabilitatea unui sistem paralel care constă din trei module având vitezele constante de
defectare λ1, λ2 şi λ3, spre exemplu, este exprimată prin relaţia:

R p (t ) = e − λ1t + e − λ2t + e − λ3t − e − ( λ1 + λ2 )t − e − ( λ2 + λ3 ) t − e − ( λ3 + λ1 )t + e − ( λ1 + λ2 + λ3 )t

Se poate remarca, în cazul sistemelor paralele, că sistemul nu are o viteză constantă de

defectare, de cădere. Viteza de cădere a unui sistem paralel descreşte odată cu fiecare
defectare a unui modul.
Se poate arăta că timpul MTTF al unui sistem paralel, în cazul în care toate modulele
au aceeaşi viteză de defectare λ, are expresia:
N
1
MTTFp = ∑ .
k =1 k λ

A C E F

Figura 3. Sistem cu altă structură decât

paralelă ori serie.

Sisteme cu alte structuri decât paralele ori serie

Există sisteme a căror diagrame de fiabilitate nu sunt conforme cu structurile paralele
ori serie.
Un astfel de sistem este descris în figura 3. Fiabilitatea acestui sistem se nu se poate
calcula prin formulele descrise pentru sistemele cu structură paralelă ori serie. Se

6
 Sisteme Tolerante la Defecte

poate remarca existenţa mai multor căi în sistemul acesta. Calea B, E şi F arată că
sistemul poate opera corect dacă modulele B, E şi F funcţionează corect.
O cale este corectă, validă, într-o astfel de diagramă doar dacă toate modulele sunt
parcurse de la stânga spre dreapta. Din acest punct de vedere privind calea B,C,D,F se
stabileşte că această cale nu este o cale validă. Nu sunt admise transformări ale
grafului dacă acestea nu este respectată această regulă.
Pentru simplitatea scrierii, în cele ce urmează, dependenţa fiabilităţii în raport cu
timpul va fi omisă, aceasta subînţelegându-se.

Utilizând formula clasică de probabilitate faţă de evenimentele condiţionate se va

deduce formula fiabilităţii sistemului din figura 3 prin dezvoltarea acesteia în raport
cu un modul oarecare i al acestui sistem:

Rsistem = Ri·Prob{Sistemul funcţionează | i este funcţional } +

(1 - Ri)·Prob{Sistemul funcţionează | i este defect } (17)

În formula (17) s-a notat prin = Ri fiabilitatea modulului i (A, B, C, D, E, F).

Utilizând formula (17) diagrama iniţială se poate descompune în două diagrame de

fiabilitate ale sistemului iniţial din figura 3.
Prima corespunde situaţiei în care modulul i este funcţional, iar în a doua modulul
este defect.
Alegerea modului i trebuie făcută astfel încât cele două diagrame nou introduse să
aibă structuri cât mai apropiate de tipurile serie şi - ori paralel.
Pentru aceste structuri nou introduse se vor putea utiliza formulele deja stabilite
pentru structurile serie şi paralele (13) şi (15).

Prin alegerea modulului C se obţin cele două diagrame din figura 4.

B E
F
A D

(a) Modulul C este

nefuncţional

A E F

(b) Modulul C este

funcţional

Figura 4. Descompunerea diagramei din

figura 3, în raport cu modulul C.

Procesul de descompunere se poate relua, se poate re-itera, până când se obţin doar
combinaţii de diagrame de tip serie ori paralel.

7
 Ion I. Bucur, note de curs

Aşa cum se poate remarca din figura 4.a aceasta este constituită doar din diagrame
serie şi paralel.

Figura 4.b, spre deosebire de figura 4.a, nu este alcătuită exclusiv din combinaţii serie
şi paralel. În acest sens trebuie remarcat faptul că modulele A şi B nu sunt în paralel,
aşa cum s-ar putea aprecia la o primă privire.

Dacă aceste module ar fi în paralel, aşa cum ar apare datorită funcţionării corecte a
modulului C, atunci ar trebui să existe în diagrama iniţială, din figura 3, o cale BCDF,
ceea nu se-ntâmplă să fie.

În figura 4.b acest fapt este marcat de sub-segmentul aflat între conexiunile modulelor
D şi B (corespunzător prezenţei funcţional sigure a modulului C).

Cu aceste remarci, se poate rescrie relaţia (17) astfel:

Rsistem = RC·Prob{Sistemul funcţionează | C este funcţional} +

(1 – RC)·RF·[1 – (1 – RA·RD)(1 – RB·RE)] (18)

Pentru calculul probabilităţii condiţionate a sistemului (în raport cu faptul că modulul

C este funcţional) diagrama din figura 4.b va fi descompusă în raport cu modulul E,
aşa cum se poate urmări în figura 5.

D F

(a) Modulul E este

nefuncţional

A F

(b) Modulul E este

funcţional

Figura 5. Descompunerea diagramei

din figura 4.b, în raport cu modulul E.

Atunci când modulul E este nefuncţional diagrama de fiabilitate arată ca în figura 5.a.
Este important de reţinut că modul C este funcţional atât în figura 5.a, cât şi în figura
5.b.

Expresia probabilităţii sistemului atunci când C funcţionează iar modul E este

nefuncţional se calculează pentru conectarea în serie a modulelor A, D şi F.

8
 Sisteme Tolerante la Defecte

Se poate remarca în această situaţie că modulul B este prezent în sistem dar nu este
conectat la modul F de ieşire, întrucât nu există o cale între modulul B şi F în
diagrama iniţială de fiabilitate a sistemului.

Expresia algebrică a probabilităţii sistemului condiţionat de faptul că modulul C este

funcţional, iar modulul E este nefuncţional arată astfel:

Prob{Sistemul funcţionează | C este funcţional şi E este nefuncţional} =

(1 - RE)RARDRF.

Iar cealaltă probabilitate arată astfel:

Prob{Sistemul funcţionează | C şi E sunt funcţionale} = RE RF[1 – (1 - RA)(1 – RB)].

După determinarea acestei expresii se poate exprima fiabilitatea sistemului ca fiind:

Rsistem = RC[RERF(RA + RB – RARB) + (1 – RE)RARDRF] +

(1 – RC)[RF(RARD + RARE - RARDRBRE)] (19).

Dacă blocurile acestei diagrame de fiabilitate au fiabilităţi identice:

RA = RB = RC = RD = RE = RF = R,

atunci fiabilitatea sistemului are expresia:

Rsistem = R3(R3 – 3R2 + R + 2) (20)

Atunci când o diagramă are o structură foarte complicată pentru aplicarea unei
proceduri similare celei parcurse anterior se pot calcula margini inferioare şi
superioare a fiabilităţii sistemului, Rsistem.

O margine superioară este determinabilă prin expresia:

Rsistem ≤ 1 − ∏ (1 − Rcaleai ) (21)

Fiabilitatea unei căi se calculează ca pentru conectarea în serie a modulelor ce

alcătuiesc acea cale.

Marginea superioară din expresia (21) presupune că toate căile sunt în paralele, pe de-
o parte, şi independenţa respectivelor căi, pe de-altă parte.

Cazurile reale pot prezenta situaţii în care două astfel de căi au un modul în comun iar
defectarea unui astfel de modul va conduce la defectarea ambelor căi.
Aceasta este raţiunea pentru care termenul din dreapta expresiei (21) constituie doar o
margine superioară şi nu o valoare exactă.

O margine inferioară poate fi calculată în baza determinării unor seturi minimale de

tăieturi ale diagramei de fiabilitate a sistemului.

9
 Ion I. Bucur, note de curs

Un set minimal de tăieturi este o listă de module cu proprietatea că prin îndepărtarea

tuturor modulelor dintr-un set (datorită defectărilor) aceasta va conduce la defectarea
sistemului, presupus iniţial perfect funcţional.

Marginea inferioară se calculează din expresia:

Rsistem ≥ ∏ (1 − Qcuti ) (23)

În relaţia (23) s-a notat prin Qcuti probabilitatea ca respectiva tăietură i să fie defectă.
Referitor la figura 3, seturile minimale de tăieturi ale diagramei de fiabilitate din
această figură sunt:
F, AB, AE, DE şi BCD.

Formula algebrică a marginii inferioare determinată prin seturile minimale de tăieturi

arată astfel:

Rsistem ≥ RF[1 – (1 – RA)( 1 – RB)][1 – (1 – RA)( 1 – RE)][1 – (1 – RD)( 1 – RE)]

×[1 – (1 – RB)( 1 – RC)( 1 – RD)] (24)

Dacă RA = RB = RC = RD = RE = RF = R, atunci:
Rsistem ≥ R5(24 – 60R + 62R2 – 33R3 + 9R4 – R5).

10
 Sistemele Tolerante la Defecte

Modelele Markov

Modelele Markov sunt utilizate în sistemele complexe, presupuse ca având viteze de

defectare constante, dar pentru care abordarea prin argumente combinatorice este
ineficientă în analiza fiabilităţii respectivelor sisteme.

Modelele Markov oferă un tratament structural pentru determinarea fiabilităţii

sistemelor care conţin procese de reparare şi facilităţi de acoperire a erorilor.

Un lanţ Markov este un tip special de proces stohastic.

Un proces stohastic X(t), în general, este un număr infinit de variabile aleatoare
indexate prin timpul t. Se consideră un proces stohastic X(t) care ia valori dintr-o
mulţime (numită spaţiul stărilor) de entităţi discrete. Se va utiliza pentru spaţiul
stărilor o submulţime a numerelor întregi {0, 1, 2, …}.

Procesul stohastic X(t) este numit Markov dacă:

Prob{ X(tn) = j | X(t0) = i0, X(t1) = i1, … , X(tn-1) = i n-1 } =

Prob{ X(tn) = j | X(tn-1) = i n-1 },
pentru fiecare t0 < t1< … < tn-1 < tn .

Dacă X(t) = i, pentru un anumit t şi i, se spune că lanţul este în starea i la momentul t.

În cele ce urmează se vor considera lanţuri Markov cu stări discrete pentru care timpul
este real şi pozitiv (0 ≤ t < ∞), iar X(t) ∈{0, 1, 2, …}.

Proprietatea Markov înseamnă că pentru determinarea traiectoriei viitoare a lanţului

(valorile viitoare X(t) ) este suficientă cunoaşterea stării prezente. Independenţa stării
viitoare a lanţului Markov de totalitatea istoriei sale anterioare este deosebit de
importantă pentru analiza proceselor stohastice.

Comportamentul probabilistic al unui lanţ Markov are o descriere simplă. Odată ce

lanţul Markov a ajuns într-o stare oarecare i, acesta va rămâne în această stare pentru
un timp care are distribuţie exponenţială cu parametrul λi. Aceasta implică o viteză
constantă λi a părăsirii stării i.

Probabilitatea ca, atunci când lanţul Markov părăseşte starea i, să ajungă în starea j
(cu i ≠j) se notează prin pij ( ∑ j ≠i pij = 1 ).
Viteza de tranziţie din starea i în starea j este:

λij = pijλi ( ∑ j ≠i λij = λi ).

Se notează, în general, prin Pi(t) probabilitatea ca procesul să fie în starea i la

momentul t, dată fiind startarea acestuia din starea i0 la momentul t = 0 .

Pentru un anumit moment de timp t şi pentru o stare dată i şi pentru un foarte scurt
interval de timp Δt, lanţul va fi în starea i la momentul t + Δt, într-unul din
următoarele cazuri:

1
 Ion I. BUCUR, note de curs

1. Lanţul a fost în starea i la momentul t şi nu a tranzitat într-o altă stare pe durata

intervalului de timp Δt. Acest eveniment are probabilitatea Pi(t)(1 - λiΔt) la
care se adaugă, posibil, termeni în Δt2.

2. Lanţul a fost în starea j la momentul t (j ≠ i) şi a tranzitat din starea j în starea

i pe durata intervalului de timp Δt. Acest eveniment are probabilitatea
Pj(t)λjiΔt la care se adaugă, posibil, termeni în Δt2.

Probabilitatea efectuării mai multor tranziţii pe durata intervalului de timp Δt este

neglijabilă (este de ordinul Δt2) dacă intervalul de timp Δt este suficient de mic.
Astfel, pentru un interval scurt de timp Δt,

Pi(t + Δt) ≈ Pi(t)(1 - λiΔt) + ∑ P (t )λ

i≠ j
j ji Δt .

Această aproximaţie devine mai precisă atunci când intervalul de timp considerat Δt
tinde spre zero, Δt → 0 şi rezultă:

dPi (t )
= −λi Pi (t ) + ∑ λij Pj (t ) ,
dt j ≠i

Deoarece ∑ j ≠i
λij = λi , relaţia anterioară se rescrie astfel:
dPi (t )
= −∑ λij Pi (t ) + ∑ λij Pj (t )
dt j ≠i j ≠i

Acest set de ecuaţii diferenţiale (pentru i = 0, 1, 2, … )poate fi soluţionat utilizând

condiţiile Pi0 = 1 şi Pj(0) = 0 pentru j ≠ i0 (deoarece i0 este starea iniţială a lanţului
Markov.

2 1
λc
Ambele 1 funcţional
funcţionale 1 defect

λ(1-c) λ

Sistemul
este defect

Figura 1. Modelul Markov al unui sistem duplex cu un procesor activ şi unul în

rezervă.

2
 Sistemele Tolerante la Defecte

Se consideră, spre exemplu, un sistem duplex care un singur procesor active şi un

singur procesor de rezervă, în aşteptare. Procesorul de rezervă este conectat numai
atunci când s-a detectat o eroare în procesorul activ.

Fie λ viteza, fixă, de defectare a unui procesor atunci când acesta este activ şi fie c
factorul de acoperire. Modelul Markov al acestui sistem este prezentat în figura 1.
Deoarece întregii atribuiţi diferitelor stări sunt, în general, arbitrari aceştia pot fi
asociaţi unei semnificaţii pentru sistemul modelat. Starea reprezintă numărul de
procesoare funcţionale (0, 1, sau 2 procesoare funcţionale - în starea iniţială fiind două
procesoare funcţionale).
Ecuaţiile diferenţiale care descriu acest lanţ Markov sunt:

dP2 (t )
= −λ P2 (t )
dt
dP1 (t )
= λ cP2 (t ) − λ P1 (t ) (1)
dt
dP0 (t )
= λ (1 − c) P2 (t ) + λ P1 (t )
dt

Soluţionarea sistemului (1) cu condiţiile iniţiale P2(0) =1, P1(0) = P0(0) = 0, conduce
la expresiile probabilităţilor celor trei stări:

P2 (t ) = e− λt ,
P1 (t ) = cλ te− λt , (2)
P0 (t ) = 1 − P2 (t ) − P1 (t ).

Fiabilitatea sistemului duplex considerat are expresia:

Rduplex (t ) = 1 − P0 (t ),
Rduplex (t ) = P2 (t ) + P1 (t ), (3)
Rduplex (t ) = e − λt + cλ e − λt .

Un alt sistem duplex care este imediat analizabil prin modelul lanţurilor Markov este
cel care are o viteză constantă de defectare λ dar şi o viteză constantă de reparaţie μ.
Modelul Markov al acestui sistem este prezentat în figura 2.

2λ λ
2 1 0

Ambele 1 funcţional Sistemul

funcţionale 1 defect este defect

μ 2μ

Figura 2. Modelul Markov al unui sistem duplex cu reparaţie.

3
 Ion I. BUCUR, note de curs

Similar cazului anterior starea din acest lanţ Markov este reprezentată prin numărul de
procesoare funcţionale. Ecuaţiile diferenţiale care descriu acest lanţ Markov sunt
descrise prin sistemul (4):

dP2 (t )
= −2λ P2 (t ) + μ P1 (t )
dt
dP1 (t )
= 2λ P2 (t ) + 2 μ P0 (t ) − (λ + μ ) P1 (t ) (4)
dt
dP0 (t )
= λ P2 (t ) − 2μ P0 (t )
dt

Soluţia sistemului (4) cu condiţiile iniţiale P2(0) = 1, P1(0) = P0(0) = 0, arată astfel:

μ2 2λμ − ( λ + μ )t λ2
P2 (t ) = + e + e−2( λ + μ )t ,
(λ + μ ) 2 (λ + μ ) 2 (λ + μ ) 2
2λμ 2λ (λ − μ ) − ( λ + μ )t 2λ 2
P1 (t ) = + e + e−2( λ + μ )t , (5)
(λ + μ ) 2 (λ + μ ) 2 (λ + μ ) 2
P0 (t ) = 1 − P1 (t ) − P2 (t ).

Se poate remarca faptul că s-au determinat doar expresiile pentru P1(t) şi P2(t). Prin
utilizarea condiţiei de însumare a celor trei probabilităţi s-a determinat şi cea de-a
treia probabilitate (P0(t)). Prin această metodă se reduce cu o unitate numărul de
ecuaţii diferenţiale care trebuiesc rezolvate.

Este de reţinut faptul că sistemul acesta nu se defectează complet niciodată. Redevine

operaţional după ce a stat un timp în starea 0, şi după ce s-a reparat revine în
funcţiune.
Pentru sistemele cu reparare calculul disponibilităţii este mai semnificativ, mai
important, decât calculul fiabilităţii.
Disponibilitatea sau probabilitatea ca sistemul să fie operaţional la momentul t este:

A(t) = P1(t) + P2(t) (6)

Deoarece în cele mai multe din cazuri procesoarele sunt reparate atunci când s-au
defectat amândouă, disponibilitatea pe termen lung a sistemului duplex este mult mai
relevantă decât fiabilitatea aceluiaşi sistem.
Pentru calculul acesteia trebuie determinate P2(∞), P1(∞) şi P0(∞). Acestea
probabilităţi pot fi obţinute prin trecerea la limită a variabilei t în expresiile
corespunzătoare sau prin anularea tuturor derivatelor din sistemul (5) şi soluţionând
sistemul de ecuaţii rezultat.

μ2 2λμ
A = P2 (∞) + P1 (∞) = + ,
(λ + μ ) (λ + μ ) 2
2

(7)
μ (μ + λ ) λ2
A= = 1 − .
(λ + μ ) 2 (λ + μ ) 2

4
 Modelarea prin lanţuri Markov discrete

0,4

0,6 0 1 0,7

0,3

Dacă I şi S sunt populaţia iniţială a unui oraș şi respective populaţia

suburbană a acelui oraş şi dacă se determină că în fiecare an 40% din
populaţia oraşului migrează în suburban în timp ce 30% din populaţia din
suburban migrează în oraş atunci după un an populaţia urbană şi suburbană
sunt calculabile prin relaţia matricială

Matricea

este foarte importantă. În adevăr, valorile fiecărei coloane sunt pozitive şi

suma acestora este 1. Astfel de vectori sunt numiţi vectori de probabilitate .
O matrice în care toate coloanele sunt vectori de probabilitate se numesc
matrice de tranziţie sau stohastice . Andrei Markov, matematician rus, a fost
primul care a studiat aceste matrice. La începutul secolului XX acesta a
dezvoltat fundamentele teoriei Lanţurilor Markov.
Un lanţ Markov este un proces care constă dintr-un număr finit de stări şi
anumite probabilităţi cunoscute pij, unde pij este probabilitatea trecerii din
starea i în starea j. În exemplul anterior, sunt două stări: 0 şi 1.
Valoarea pij reprezintă probabilitatea trecerii din starea i în starea j, într-un
anumit interval de timp.
Lanţurile Markov pot avea două sau mai multe stări.

1
Un sistem de calcul cu trei procesoare, spre exemplu, poate avea toate
procesoarele funcţionale (starea 3) după cum poate avea doar două
procesoare funcţionale (starea 2), unul funcţional (starea 1) sau niciunul
(starea 0). Sistemul de calcul este, iniţial, complet funcţional şi are
capacitatea să recupereze, parţial sau total, funcţionalitatea.
Probabilitatea p30, spre exemplu, reprezintă probabilitatea defectării la un
moment dat a întregului sistem, constituit din cele trei procesoare.

p32
p33 3 p23
2 p22

p02
p13
p03 p12

p30
p31 p21
p20
p01
p00 0 p10
1 p11

Figura 1. Lanţul Markov asociat unui sistem tri-procesor având capacitatea unei
recuperări dinamice.

Analog, probabilitatea p02, spre exemplu, reprezintă probabilitatea reparării

simultane a două procesoare, din cele trei ale sistemului, după acelaşi
interval de timp t, atunci când sistemul tri-procesor a fost complet
nefuncţional.
Pentru fiecare stare a lanţului Markov din figura 1 se pot scrie relaţiile:

p33 + p32 + p31 + p30 = 1,

p23 + p22 + p21 + p20 = 1,
p13 + p12 + p11 + p10 = 1,
p03 + p02 + p01 + p00 = 1.

Aceste relaţii arată completitudinea sistemului de evenimente asociate

fiecărei stări, în parte, din lanţul Markov.

Probabilitatea ca sistemul să fie complet funcţional, spre exemplu, la

momentul n poate fi scrisă astfel:

P3(n) = p33P3(n-1) + p23P2(n-1) + p13P1(n-1) + p03P0(n-1). (01)

2
În (01) s-a notat, spre exemplu, prin P2(n-1) probabilitatea ca sistemul să
funcţioneze cu două unităţi din trei la momentul n-1, iar prin p23 s-a notat
probabilitatea recuperării unității nefuncţionale pe durata momentului n-1.

Similar, probabilităţile ca la momentul n sistemul să a funcţioneze cu 2, 1

sau niciuna dintre unităţile sale funcţionale sunt:

P2(n) = p32P3(n-1) + p22P2(n-1) + p12P1(n-1) + p02P0(n-1), (02)

P1(n) = p31P3(n-1) + p21P2(n-1) + p11P1(n-1) + p01P0(n-1), (03)
P0(n) = p30P3(n-1) + p20P2(n-1) + p10P1(n-1) + p00P0(n-1), (04)

Relaţiile anterioare ( (01) – (04)) se pot rescrie matricial astfel:

⎡ P3 (n) ⎤ ⎡ p33 p23 p13 p03 ⎤ ⎡ P3 (n − 1) ⎤

⎢ P (n) ⎥ ⎢ p p p p ⎥ ⎢ P (n − 1) ⎥
⎢ 2 ⎥ = ⎢ 32 22 12 02 ⎥ i ⎢ 2 ⎥ (05)
⎢ P1 (n) ⎥ ⎢ p31 p21 p11 p01 ⎥ ⎢ P1 (n − 1) ⎥
⎢ ⎥ ⎢ ⎥⎢ ⎥
⎣ P0 (n) ⎦ ⎣ p30 p20 p10 p00 ⎦ ⎣ P0 (n − 1) ⎦

Se notează în (05) vectorul coloană din stânga prin:

⎡ P3 (n) ⎤
⎢ P ( n) ⎥
Πn = ⎢ 2 ⎥ (06)
⎢ P1 (n) ⎥
⎢ ⎥
⎣ P0 (n) ⎦

Matricea pătrată a sistemului din (05) se notează, tradiţional, astfel:

⎡ p33 p23 p13 p03 ⎤

⎢p p p p ⎥
32 22 12 02 ⎥
A=⎢ (07)
⎢ p31 p21 p11 p01 ⎥
⎢ ⎥
⎣ p30 p20 p10 p00 ⎦

Atunci relaţia (05) se rescrie astfel:

Π n = AiΠ n −1 . (07)

Explicitând expresia (07) rezultă:

Π n = An i Π 0 (08)

3
Vectorul iniţial Π 0 arată astfel:
⎡1 ⎤
⎢0 ⎥
Π0 = ⎢ ⎥ . (09)
⎢0 ⎥
⎢ ⎥
⎣0 ⎦

Vectorul coloană iniţial arată astfel deoarece, la momentul zero, sistemul se

presupune că era complet funcţional.

Pentru o istorie suficient de lungă a funcţionării sistemului tri-procesor

considerat acesta intră într-o starea staţionară caracterizată printr-o anumită
distribuţie a probabilităţilor stărilor acestuia.

Π = AiΠ (10)

Această distribuţie stabileşte probabilităţile sistemului de a se găsi în cele

patru stări posibile.
Un vector coloană de probabilităţi Π care satisface (10) este alcătuit din
valori proprii ale matricei A.
Determinarea valorilor proprii ale unei matrice poate fi o sarcină laborioasă.
Dintr-un punct de vedere pragmatic vectorul coloană Π poate fi aproximat
printr-un calcul iterativ aplicând expresia (07). Calculul poate fi oprit
deîndată ce:
Π n +1 − Π n ≤ ε (11)

În (11) constanta pozitivă ε poate fi aleasă convenabil, în raport cu precizia

urmărită, în calculul probabilităţilor staţionare ale lanţului Markov respectiv.
Uzual, valori ale erorii ε de ordinul 0 < ε < 10-6 sunt satisfăcătoare în marea
majoritate a situaţiilor.

4
 TEHNICILE SOFTWARE PENTRU TOLERANTA LA DEFECTE

În continuare vor fi considerate cele mai utilizate metode de identificare a procesorului defect.
Mult utilizată pentru identificarea procesorului defect este aplicarea unor seturi de procedee care să verifice
rezultatul fiecărui procesor. Aceste seturi de procedee sunt, adesea, numite teste de acceptare.
Testul gamei de valori, este reprezentativ pentru astfel de teste.
Verificarea gamei de valori este un test simplu şi foarte potrivit în cele mai multe din cazuri.
Dacă rezultatul în discuţie este nivelul unui lichid dintr-un un container, spre exemplu, atunci este de dorit
compararea gamei valorilor posibile ale nivelului lichidului cu valorile calculate de cele două procesoare.
O valoare calculată în afara gamei respective (depăşeşte volumul real al containerului, spre exemplu) va fi, cu
siguranţă, declarată eronată.
Determinarea intervalului de valori acceptabile pentru rezultatele calculate este cu atât mai bună, cu cât
intervalul de valori este mai strâns, mai îngust. Un interval mai mic al valorilor acceptabile va creşte
probabilitatea identificării corecte a rezultatului eronat şi va micşora şansele declarării greşite a unui rezultat ca
fiind eronat.
Se defineşte sensibilitatea unui test ca fiind probabilitatea condiţionată ca testul să detecteze o eroare, dat fiind
faptul că ieşirea calculatorului este actualmente eronată.
Similar se introduce specificitatea unui test ca fiind probabilitatea condiţionată ca ieşirea calculatorului să fie
eronată, dat fiind faptul că testul de acceptare declară o eroare.
Un interval îngust al valorilor acceptate va avea o sensibilitate ridicată şi o specificitate joasă.
Aceasta înseamnă că testul este foarte probabil să nu piardă o ieşire eronată dar în acelaşi timp este posibil să
genereze multe rezultate fals-pozitive (adică, rezultate corecte pe care testul le declară eronate).
Un interval larg al gamei de valori va avea sensibilitate joasă dar, va avea specificitatea ridicată.
Gama de valori este cea mai simplă metodă dar, în nici un caz, nu este unica. Se presupune, spre exemplu, că
se doreşte să se verifice un rezultat de forma ex.
Simpla aplicare a logaritmului natural asupra rezultatului în dubiu poate, mijlocind o eventuală pierdere de
precizie, stabili adevărul (dar doar atât de cert cât va permite precizia de calcul).
 SISTEME TOLERANTE LA DEFECTE

TOLERANTA SISTEMELOR IN RAPORT CU DEFECTELE SOFTWARE

Dr.Ing.Mat. Ion Bucur

S-a scris mult despre cauzele care conduc la sensibilitatea software-ul la defecte dar şi despre
raţiunile care fac ca proiectarea şi scrierea software-ului sǎ fie intrinsec dificilǎ. Cercetarea a
dovedit cǎ existǎ atât dificultǎţi esenţiale cât şi accidentale care sunt implicate în producţia
software-ului. Dificultǎţile esenţiale ţin de natura aplicaţiilor complexe ca şi de mediul
complex de operare. Aceste dificultǎţi îşi au sorgintea şi în construcţia cu un numǎr foarte
mare de stǎri, guvernate prin legi de tranzitare complexe.

Introducerea, frecventǎ, pe durata ciclului de viaţǎ a software-ului a modificǎrilor impuse de

reglementǎri ori de situaţii noi. Astfel, sunt adǎugate software-ului noi faciltǎţi pentru a
adapta o aplicaţie software la cerințele actualizate ale contextului de utilizare.
Platformele hardware şi sistemul de operare se pot modifica ulterior perioadei în care a fost
proiectatǎ şi implementatǎ o aplicaţie software iar aceasta trebuie ajustatǎ corespunzǎtor.
Software-ul este, adesea, utilizat sǎ mascheze incompatibilitǎţile dintre componentele unui
sistem de calcul.

Considerațiile privind costurile nu pot fi ocolite atunci când sunt alternative în implementarea
unei aplicaţii complexe. De cele mai multe ori se face apel la software existent, deja
disponibil contra cost (COTS Commercial Off-The-Shelf) care nu este proiectat întotdeauna
pentru aplicații de mare fiabilitate.
Utilizarea COTS este mandatatǎ în multe programe guvernamentale ori de afaceri pentru cǎ
pot oferi economii semnificative atât în costurile iniţiale de achiziţie cât şi în costurile
ulterioare, de întreţinere. Totuşi, specificaţiile software-ului COTS sunt scrise extern,
independent, de utilizarea acestui software într-o aplicaţie aparţinând, eventual, unei agenţii
guvernamentale.
Acest fapt poate induce rezerve şi temeri deoarece schimbǎrile viitoare ale produsului
respectiv nu mai pot fi controlate.
Principalele motive invocate atunci când sunt utilizate produsele COTS vizeazǎ:
(1) reducerea globalǎ a timpului de dezvoltare,
(2) costurile de dezvoltare, deoarece componentele pot fi achiziţionate ori licenţiate, în loc
sǎ fie dezvoltate pornind de la specificaţii,
(3) costuri mai reduse de întreţinere.

Software-ul conține, aproape inevitabil, defecte. De aceea se face tot posibilul ca rata de
defectare sǎ scadǎ ori, pentru soluţionarea problemelor erorilor din software, se folosesc
tehnici de creştere a toleranţei la defecte.
Teoretic, o metodǎ foarte eficientǎ de evitarea erorilor în software este verificarea formalǎ.
Dar aceastǎ metodǎ nu este aplicabilǎ modulelor mari, complexe, dintr-o aplicaţie software.

Un pas important, în orice tentativǎ de tolerare a defectelor, este detectarea acestora. O cale
mult utilizatǎ de detectare a defectelor în software este aplicarea testelor de acceptare.
Acestea sunt utilizate în contextul aşa - numitelor wrappers (ambalaje) dar şi în blocurile de
recuperare.

Aceste teste sunt mecanisme importante în implementarea toleranţei la defecte în software.

Dacǎ un termometru aratǎ – 40o C în miezul unei zile de varǎ, spre exemplu, termometrul
respectiv este presupus cǎ funcţioneazǎ eronat. Acesta este un exemplu de test de acceptare.

1
 SISTEME TOLERANTE LA DEFECTE

Un test de acceptare este, în esenţǎ, o verificare a rezonabilitǎţii. Cele mai multe dintre testele
de acceptare, în general, sunt cuprinse într-una din categoriile urmǎtoare.

Verificarea duratei de execuţie. Acesta este un alt instrument mult folosit în toleranţa
defectelor în software. Dacǎ existǎ o apreciere cât de cât a duratei rulǎrii codului, se poate
programa o întrerupere corespunzǎtoare intervalului de timp estimat. Atunci când acel timp
estimat a fost depǎşit se poate presupune cǎ a avut loc o funcţionare necorespunzǎtoare (o
eroare produsǎ în hardware ori ceva eronat în software care a cauzat depǎşirea duratei
estimate). Verificǎrile prin durata execuţiei sunt folosite în paralel cu alte teste de acceptare.

Verificarea rezultatului. În anumite cazuri testul de acceptare este cât se poate de natural
sugerat chiar de problema în cauzǎ. Adicǎ, natura problemei este de în aşa fel, încât chiar dacǎ
problema este dificil de soluţionat, este mult mai comod de verificat corectitudinea
rezultatului deoarece este mult mai puţin probabil ca verificarea, în sine, sǎ fie incorectǎ.
În acest sens, spre exemplu, soluţionarea unui joc puzzle poate fi de duratǎ, dar verificarea
corectitudinii acesteia este trivial de simplǎ.

Exemple ale unor astfel de probleme în software sunt:

o calculul rǎdǎcinii pǎtrate (se ridicǎ la pǎtrat rezultatul şi se verificǎ obţinerea
numǎrului iniţial),
o factorizarea unor numere mari (se multiplicǎ factorii corespunzǎtori, urmǎrind
obţinerea numerelor respective, dar metoda poate fi de durată),
o soluţionarea ecuaţiilor (se introduc soluţiile în ecuaţiile iniţiale) şi
o ordonarea. De remarcat cǎ în problemele de ordonare este insuficient sǎ se verifice
corecta ordonare, pe de-o parte dar trebuie verificat şi faptul că toate numerele supuse
ordonǎrii sunt prezente în rezultatul final (şirul ordonat complet de numere).

Adeseori, din raţiuni care ţin de durata testelor, se utilizeazǎ verificǎri probabilistice. Acestea
nu garanteazǎ detectarea tuturor rezultatelor eronate chiar dacǎ verificǎrile sunt executate
perfect. Un astfel de exemplu de verificare probabilisticǎ, privind corectitudinii înmulţirii
matricelor, este descris în cele ce urmeazǎ.
Se presupune cǎ sunt înmulţite douǎ matrice A şi B, pǎtrate de dimensiune n, obţinându-se
matricea C.
Verificarea rezultatului, fǎrǎ repetarea înmulţirii matricelor, utilizeazǎ un vector aleatoriu cu n
întregi, R, şi efectueazǎ operaţiile M1 = A × (B × R) şi M2 = C × R. Dacǎ M1 ≠ M2, atunci a
avut loc o eroare.

Dar, dacǎ M1 = M2, aceasta nu dovedeşte, totuşi, cǎ rezultatul C este corect.

În acelaşi timp, este foarte puţin probabil cǎ vectorul aleatoriu R a fost astfel ales încât M1 =
M2, chiar dacǎ A × B ≠ C. Se poate obţine reducerea, în continuare, a acestei probabilitǎţi
prin alegerea unui alt vector aleatoriu R, tot cu n componente, repetând verificarea. Acest test
are complexitatea O(mn2).

Verificarea ordinului mǎrimii a rezultatului. Existǎ situaţii când nu sunt la îndemânǎ abordǎri
evidente şi convenabile pentru verificarea corectitudinii rezultatului. Pentru astfel de situaţii
sunt folosite majorǎri ori limite ale rezultatului. În acest sens, se utilizeazǎ cunoaşterea naturii
aplicaţiei pentru evaluarea unor limite acceptabile ale rezultatului. Un rezultat situat în afara
acestor limite justificǎ declararea rezultatului respectiv ca fiind eronat.
De cele mai multe ori limitele sunt fie valori prestabilite, fie sunt calculabile prin funcţii
simple care depind de variabilele în raport cu care se determinǎ rezultatul respectiv.

2
 SISTEME TOLERANTE LA DEFECTE

În cele de-al doilea caz este important ca funcţiile sǎ fie suficient de simplu implementabile
astfel încât probabilitatea de rejecţie a testului software însuşi, ca fiind defect, sǎ fie suficient
de micǎ.

Un satelit prevǎzut cu sensori de temperaturǎ, spre exemplu, efectueazǎ din spaţiu imagini
termice ale suprafeţei pǎmântului. Se pot stabili, evident, limite ale gamei de temperaturi şi se
poate considera orice abatere faţǎ de aceste limite, ca fiind o indicaţie clarǎ a unei
malfuncţionǎri. Chiar mai mult, se pot stabili corelaţii spaţiale, care sǎ repereze diferenţe
excesive dintre temperaturile unor arii adiacente şi sǎ se declare eroare dacǎ diferenţele nu
sunt explicabile prin cauze fizice (cum ar fi prezenţa unor vulcani).

Atunci când sunt stabilite limitele pentru acceptarea testelor trebuie sǎ fie consideraţi doi
parametri, sensibilitatea şi specificitatea.

Sensibilitatea este probabilitatea ca testul de acceptare sǎ sesizeze un rezultat eronat. Mai

exact, sensibilitatea este probabilitatea condiţionatǎ ca testul sǎ declare o eroare, dat fiind
faptul cǎ rezultatul este eronat.

Specificitatea, spre deosebire de sensibilitate, este probabilitatea condiţionatǎ ca atunci când

testul de acceptare detecteazǎ un rezultat eronat, aceasta este într-adevǎr o eroare şi nicidecum
un rezultat corect, care se întâmplǎ sǎ se situeze în afara limitelor testului.

Un parametru strâns legat este probabilitatea unei false alarme. Aceasta este probabilitatea
condiţionatǎ ca testul sǎ declare eronat un rezultat care, în fapt, este corect. Se poate atinge o
creştere a sensibilitǎţii prin îngustarea intervalului de acceptare. Aceasta ar conduce, în acelaşi
timp, din nefericire la micşorarea specificitǎţii şi creşterea probabilitǎţii falselor alarme.

Versiunea singularǎ la toleranţa faţǎ de defecte

Sunt considerate cǎi şi metode prin care componente individuale de software pot fi fǎcute sǎ
fie mult mai robuste. Se vor considera, pentru început încapsulǎrile. Acestea sunt interfeţe
specifice care îmbunǎtǎţesc interfeţele modulelor software existente.

Încapsulǎrile

Acestea sunt structuri software care încapsuleazǎ un program atunci când acesta este
executat. Se poate efectua încapsularea aproape la orice nivel al software-ului. Exemple
curente cuprind software de aplicaţii, middleware şi chiar nucleul sistemului de operare.
Fluxul intrǎrilor venind de la mediul extern, lumea din afarǎ, spre entitatea încapsulatǎ sunt
interceptate de încapsulare, care decide când sǎ le transmitǎ entitǎţii încapsulate sau când sǎ
semnaleze o excepţie spre sistem.
În mod absolut similar ieşirile entitǎţii încapsulate sunt de asemenea filtrate prin încapsulare.

Încapsulǎrile au devenit foarte mult uzitate atunci când s-a început utilizarea componentelor
software COTS în vederea aplicaţiilor cu înaltǎ fiabilitate. Componentele COTS sunt scrise
pentru aplicaţii de uz general, pentru care erorile sunt supǎrǎtoare, în adevǎr, dar nu sunt o
calamitate.
Înainte ca aceste componente sǎ fie folosite în aplicaţii care impuneau fiabilitate ridicatǎ,
acestea trebuiau sǎ fie incluse, cuprinse, într-un anumit mediu software care sǎ le micşoreze
rata erorilor.

3
 SISTEME TOLERANTE LA DEFECTE

Acest mediu (încapsularea) trebuia sǎ evite spre aplicaţia încapsulatǎ fluxuri de intrǎri care
sunt fie în afara gamei de valori valide, fie sunt cunoscute deja ca fiind cauzatoare de erori.
Similar, încapsularea trece fluxurile de ieşire ale entitǎţii încapsulate printr-un filtru de
acceptare înainte sǎ le trimitǎ spre sistem.

Dacǎ anumite informaţii, eventual toate ieşirile violeazǎ testul de acceptare, acest fapt trebuie
transmis sistemului care decide asupra unei acţiuni corespunzǎtoare.
O încapsulare este caracterizatǎ, specificatǎ, prin entitatea încapsulatǎ dar şi prin sistemul în
care se instaleazǎ.

Software-ul încapsulǎrii

Aplicaţia încapsulatǎ

Structura generalǎ a unei încapsulǎri

software

Tratarea depǎşirii lungimii zonelor tampon de memorie. Limbajul de programare C,

tradiţional, nu efectueazǎ întotdeauna verificarea mǎrimii masivelor, ceea ce poate cauza
neajunsuri accidentale ori rǎu intenţionate. Scrierea unui şir mare de caractere într-o zonǎ
tampon de memorie insuficientǎ ca mǎrime, produce o depǎşire; deoarece nu se efectueazǎ
nici o verificare a lungimii zonelor implicate în transfer, o regiune din memorie, situatǎ în
imediata vecinătate a zonei tampon, este suprascrisǎ. Mai mult, conţinutul zonei suprascrise
nu este controlat.

Se considerǎ, spre exemplu, funcţia strcpy() din limbajul C. Aceasta funcţie copiazǎ şiruri de
caractere dintr-o locaţie de memorie în alta. Dacǎ se executǎ apelul strcpy(str1, str2), unde
str1 desemnează o zonǎ tampon de memorie cu lungimea 5 iar str2 este adresa unui şir cu
lungimea 25, atunci depǎşirea zonei de memorie va suprascrie o regiune din memorie în afara
zonei de tampon str1.
Astfel de depǎşiri au fost exploatate în vederea producerii unor agresiuni.

O încapsulare poate verifica şi asigura cǎ astfel de depǎşiri de suprascriere nu sunt posibile,

spre exemplu, prin verificarea capacitǎţii zonei de memorie tampon în raport cu şirul
desemnat.
Violarea acestei reguli face sǎ se anuleze apelul funcţiei strcpy() iar încapsularea returneazǎ o
eroare sau ridicǎ o excepţie spre sistem.

Utilizarea unor aplicaţii software având erori cunoscute. Sunt cunoscute situaţii în care o
aplicaţie achiziţionatǎ se dovedeşte să aibă defecte. Stabilirea funcţionǎrii defectuoase poate
avea loc în urma unor verificǎri specifice sau ca urmare a unor rapoarte provenite din utilizǎri

4
 SISTEME TOLERANTE LA DEFECTE

anterioare şi care au dovedit existenţa unor anumite malfuncţionǎri, corespunzătoare unor

anumite seturi de date S, etc.
Se poate ca versiunea nouǎ, corectatǎ şi adusă la zi, urmând sǎ fie lansatǎ de producǎtor sǎ nu
fie încǎ disponibilǎ, cel puţin un timp.
În consecinţǎ, trebuie utilizatǎ cea curentǎ, aşa cum este aceasta. Pentru evitarea defectelor
cunoscute aceastǎ aplicaţie trebuie controlată. Instituirea acestui control se realizează prin
încapsulare.

Încapsularea va intercepta intrǎrile de date ale aplicaţiei şi va stabili dacǎ acestea au

intersecţie nevidǎ cu mulţimea S de seturi de date, cunoscute ca fiind cauzatoare a
malfuncţionării. În cazul în care datele de intrare ale aplicaţiei sunt din mulţimea S, acestea se
pot redirecţiona spre o aplicaţie special constituită, capabilă sǎ trateze situaţia ori, în cel mai
defavorizat caz, să poată emite o excepţie spre sistem.

Utilizarea unei aplicaţii de încapsulare care să verifice corectitudinea rezultatelor

produse. O astfel de aplicaţie de încapsulare cuprinde un test de acceptare prin care se poate
filtra orice rezultat produs de aplicaţia verificată. Dacă rezultatul produs de aplicaţia verificată
trece de testul respectiv, atunci acel rezultat este transmis mai departe. Dar, dacă rezultatul nu
satisface testul de acceptare atunci se generează o excepţie iar sistemul are de soluţionat un
caz suspect.
O alternativă la generarea unei excepții, este implementarea în aplicaţia de încapsulare a unui
modul specific de tratare a situaţiei generate în urma ne-satisfacerii testului de acceptare.
Acest modul specific poate stabili rezultatul corect şi îl poate substitui celui produs în
aplicaţia verificată.

Capacitatea încapsulării cu succes a unei aplicaţii existente depinde de anumiţi factori:

(a) Calitatea testelor de acceptare. Acest factor este intens dependent de aplicaţia
respectivă şi are un impact imediat asupra abilităţii aplicaţiei încapsulatoare să
blocheze ieşirile eronate produse de aplicaţia încapsulată.
(b) Disponibilitatea informaţiilor necesare, proprii aplicaţiei încapsulate. Adesea
componenta încapsulată este tratată ca fiind o cutie neagră şi tot ce se poate observa în
legătură cu comportamentul acesteia sunt valorile produse la ieşire, ca răspuns la
anumite valori ale intrărilor. În astfel de situaţii încapsularea va fi cumva limitată.
(c) Măsura în care aplicaţia încapsulată a fost deja testată. Testarea extensivă a acestei
aplicaţii permite identificarea regiunilor din spaţiul valorilor de intrare pentru care
aplicaţia nu funcţionează corect şi implicit diminuarea probabilității propagării în
sistem a valorilor eronate.

Se consideră, spre exemplu, verificarea corectitudinii unui modul planificator de sarcini

(scheduler). Pentru aceasta se consideră o încapsulare a planificatorului de sarcini dintr-un
sistem în timp real, tolerant la defecte.
Spre deosebire de sistemele de operare de uz general, planificatoarele sistemelor în timp real
nu utilizează o planificare de tip R-R (round-robin).

Un algoritm de planificare pentru planificatoarele de sarcini în timp real este de tip EDF
(EDF fiind abrevierea denumirii Earliest Deadline First) în care, aşa cum rezultă din
denumire, sistemul execută prioritar sarcina cu cel mai strâns, apropiat, termen de execuţie
dintre toate sarcinile care sunt gata să fie lansate în execuţie.

5
 SISTEME TOLERANTE LA DEFECTE

Un astfel de algoritm trebuie să ia în consideraţie anumite restricţii privind întreruperea

execuţiei unei sarcini înainte de terminarea execuţiei acesteia, deoarece anumite sarcini nu se
pot întrerupe pe durata unor anumite porţiuni, dinainte cunoscute, ale execuţiei acestora.

Un astfel de planificator poate fi supus unei încapsulări printr-o aplicaţie care verifică modul
corect de execuție al planificatorului:
• planificatorul alege, dintr-o mulţime existentă, mereu sarcina gata de execuţie
caracterizată prin termenul de execuţie cel apropiat.
• apariţia, la un moment dat, a unei noi sarcini executabile având termen mai scurt decât
sarcina executată curent trebuie să conducă la lansarea acesteia în execuţie doar dacă
execuţia sarcinii curente poate fi întreruptă.

Este evident că pentru soluţionarea verificării funcţionării corecte a planificatorului EDF,

aplicaţia încapsulatoare trebuie să aibă acces la anumite informaţii esenţiale:
o mulţimea sarcinilor gata de execuţie,
o termenele de execuţie ale acestora şi
o informaţia privind posibilitatea întreruperii înainte de termen a sarcinii executate
curent.

Obţinerea acestor informaţii impune, în fapt, accesul printr-o interfaţă corespunzătoare a

respectivului planificator al sarcinilor în timp real, privitor la starea sarcinilor gata de lansat în
execuţie ca şi asupra termenelor lor de execuţie, pe de-o parte, dar şi asupra momentului când
sarcina aflată curent în execuţie este interuptibilă înainte de termen.

Reîntinerirea software-ului

Sunt multe situaţii în care un utilizator se confruntă cu situaţii în care calculatorul se

blochează. Reacţia firească este adesea reîncărcarea sistemului de operare. Această operaţie
este cea mai simplă cale de reîntinerire a software-ului.
Pe măsură ce se execută un proces de calcul acesta ocupă memorie şi acaparează fişiere fără
să elibereze corespunzător aceste resurse. În paralel datele unui astfel de proces tind să fie
corupte şi să se acumuleze erori necorectate. Un astfel de proces tinde să consume, în egală
măsură, fire de execuţie şi semafoare fără să le elibereze. Dacă un asemenea proces continuă
să ruleze indefinit, va deveni defect şi va stopa execuţia. Pentru evitarea unei astfel de situaţii
se poate proceda să se stopeze, proactiv, procesul. Astfel, starea internă a acestui proces este
re-iniţializată şi se poate demara reluarea respectivului proces. Aceasta este ceea ce se
numeşte o reîntinerire a software-ului.

Nivelul reîntineririi

Se poate aplica un procedeu de reîntinerire fie la nivelul aplicaţiei, fie la nivelul procesorului
respectiv.
Reîntinerirea practicată la nivelul unei aplicaţii constă din suspendarea individuală a
respectivei aplicaţii, ştergerea stării acesteia, reiniţializarea structurilor de date ale acesteia
ş.a.m.d., după care se relansează în execuţie respectiva aplicaţie.
Reîntinerirea aplicată la nivelul procesorului constă din re-încărcarea sistemului de operare şi
afectează toate aplicaţiile care rulau pe respectivul procesor. Dacă situaţia se petrece la nivelul
unui cluster de procesoare este de dorit ca să se mărginească reîntinerirea astfel încât o atare
reîntinerire să afecteze doar o mica parte a procesoarelor la un moment dat.

6
 SISTEME TOLERANTE LA DEFECTE

Modul de aplicare al reîntineririi

Reîntinerirea software-ului se poate determina în raport cu timpul sau se poate stabili prin
predicţie. Reîntinerirea software-ului în raport cu timpul constă în acţiuni de reîntinerire la
intervale constante de timp.
Determinarea perioadei optime de inter-reîntinerire trebuie să echilibreze beneficiile în raport
cu costurile operaţiei de reîntinerire.
Se poate constitui un model matematic simplu al modului de aplicare periodică a reîntineririi
software-ului.
Se vor utiliza câteva notaţii:

N(t) – numărul mediu de erori dintr-un interval de timp t, fără efectuarea

vreunei reîntineriri.
Ce – costul fiecărei erori,
Cr – costul fiecărei operaţii de reîntinerire,
P – perioada de timp scursă între două reîntineriri succesive.

Prin sumarea costurilor datorită erorilor şi aferente operaţiilor de reîntinerire se determină

expresia costului reîntineririi aferente unei perioade de timp P, notat prin Cre (P):

Cre (P) = N(P)⋅Ce + Cr

Prin raportarea acestui cost la timpul de aplicare a unei reîntineriri, se obţine costul (în raport
cu o unitate de timp) unei operaţii de reîntinerire.
Acest cost este notat prin Crata(P) şi are expresia:

Cre ( P) N ( P)Ce + Cr
Crata ( P) = = (1)
P P

Este util de considerat diferite cazuri asupra modului cum evoluează numărul mediu de erori
între două operaţii de reîntinerire.
Întâi se poate considera că viteza de defectare a software-ului λ este constantă pe toată durata
de execuţie a software-ului.
Această ipoteză conduce la o expresie a numărului mediu de erori, acumulate după un interval
P de timp, de forma:

N(P) = λP.

Substituind această expresie pentru N(P) în (1) se obţine:

Crata ( P) = λ Ce + Cr / P .

Se poate uşor remarca faptul că se poate minimiza această expresie, dedusă, pentru Crata(P)
dacă P tinde spre infinit. Concluzia se poate formula în termenii următori:
• Atunci când viteza de defectare a software-ului este constantă în timp, este
rentabil să se evite reîntinerirea software-ului.
• Reîntinerirea software-ului este profitabilă atunci când viteza de apariţie a
erorilor creşte pe măsură ce este executat software-ul respectiv.

7
 SISTEME TOLERANTE LA DEFECTE

Următoarea ipoteză asupra vitezei de defectare a software-lui consideră că numărul mediu de

defecte care apar într-un interval de timp P este de forma:

N(P) = λP2.

Din expresia (1) cu N(P) = λP2 rezultă că:

Crata ( P) = λ PCe + Cr / P

Minimizarea expresiei astfel obţinute se va determina pentru:

dCrata ( P)
= 0,
dP
Cu condiţia:
d 2Crata ( P)
> 0.
dP 2

Prin soluţionarea condiţiilor anterior menţionate se obţine o durată optimă, notată prin P*, de
forma:

Cr
P* = .
λCe

În cel de-al treilea caz se consideră că N(P) = λPn, n >1.

Acest caz este o generalizarea a cazului precedent. Astfel, în acest caz se obţine, pentru
Crata(P), expresia:

Crata ( P) = λ P n −1Ce + Cr / P .

Printr-un calcul similar celui aplicat în cazul anterior, se stabileşte că perioada optimă de
reîntinerire are expresia:

Cr
P* = ( )1/ n
(n − 1)λCe

Pentru alegerea corespunzătoare a valorii perioadei P este necesară cunoaşterea valorilor

parametrilor Cr/Ce şi N(t).
Aceşti parametrii se pot obţine experimental prin rularea unor simulări ori alternativ, sistemul
poate fi proiectat adaptiv, având anumite valori iniţiale implicite, alese pentru început.
În timp, pe măsură ce se culeg date şi se determină statistici, care reflectă natura căderilor
software-ului, se poate ajusta corespunzător perioada de reîntinerire.

Reîntinerirea bazată pe predicţii cuprinde monitorizarea caracteristicilor sistemului (cum ar fi

volumul de memorie alocat, numărul de fişiere etc.) şi predicţiile privitor la condiţiile în care
au loc căderile sistemului. Dacă un proces, spre exemplu, este intens consumator de memorie,
cu o anumită viteză, atunci sistemul va putea estima destul de precis când va avea loc
depăşirea volumului de memorie disponibilă. Reîntinerirea software-ului, în acest caz, va avea
loc chiar înaintea momentului predeterminat al epuizării memoriei disponibile.

8
 SISTEME TOLERANTE LA DEFECTE

Software-ul care implementează reîntinerirea bazată pe predicţii trebuie să poată să aibă acces
la suficient de multe informaţii de stare ale sistemului pentru determinarea unor predicţii
fiabile. Atunci când aplicaţia care gestionează reîntinerirea software-ului face parte din
sistemul de operare, este satisfăcut accesul la informațiile vitale pentru stabilirea unor
predicţii satisfăcătore.
Dar dacă această aplicaţie rulează peste sistemul de operare, fără să aibă privilegii speciale,
atunci aceasta va fi constrânsă să utilizeze orice interfaţă este oferită de sistemul de operare
pentru ca să colecteze informaţii privitor la starea sistemului.

Sistemul de operare Linux, spre exemplu, oferă anumite facilităţi de acces la informaţiile de
sistem prin intermediul unor utilităţi cum ar fi:
vmstat – oferă informaţii despre utilizarea procesorului, memoriei şi activităţii în pagini,
întreruperi şi operaţii de I/E.
iostat – produce utilizarea procentuală a UC, la nivelurile de utilizator şi sistem, precum şi un
raport asupra utilizării fiecărui dispozitiv de I/E.
netstat – arată conexiunile în reţea, tabelele de rutare şi tabelul tuturor interfeţelor de reţea.
nfsstat – oferă statistici despre clientul NFS şi activităţile NFS.

Odată ce s-au colectat informaţiile corespunzătoare stării sistemului, se pot identifica

tendinţele şi se pot face predicţii privitor la momentul în care aceste tendinţe vor produce
erorile de sistem. Dacă se cunoaşte modul în care a fost cerută şi alocată memorie, unui
anumit proces, de-a lungul timpului, se poate determina o aproximare polinomială (eventual
utilizând metoda celor mai mici pătrate) a alocărilor de memorie dintr-o anumită fereastră,
interval, de timp scurs recent.
Cea mai simplă abordare, în acest sens, este potrivirea peste punctele de alocare a unei linii
drepte, echivalentă unui polinom de gradul întâi, de forma: f(t) = mt + c.
Aproximări mai complexe pot utiliza un polinom de grad neprecizat, de gradul n, spre
exemplu. Fereastra de timp se presupune că include ultimele k momente de timp:
t1 < t2 <… tk,
unde tk este cel mai recent moment.
Se presupun cunoscute valorilor corespunzătoare celor k momente de timp:

μ(t1), μ(t2), … μ(tk).

Unde μ(ti), 1 ≤ i ≤ k, reprezintă volumul de memorie alocată la momentul ti.

Se caută să se determine coeficienţii polinomului:

f(t) = mntn + mn-1tn-1 + … m1t + m0,

astfel încât să se minimizeze expresia:

∑ [μ (t ) − f (t )]
i =1
i i
2
.

Acest polinom poate fi utilizat pentru extrapolarea funcţiei de alocare a memoriei şi să se

poată prognoza momentul când procesul va epuiza memoria disponibilă.
În aproximarea prin cele mai mici pătrate fiecare punct observat μ(ti) are aceeaşi pondere în
determinarea funcţiei de aproximare. O variantă a acestei metode este metoda ponderată a

9
 SISTEME TOLERANTE LA DEFECTE

celor mai mici pătrate, în care se caută să se minimizeze suma ponderată a pătratelor. Pentru
problema aproximării cererilor de memorie se vor alege anumite ponderi:

w1, w2, … , wk,

urmând să se determine coeficienţii funcţiei f(t) astfel încât să se minimizeze expresia:

∑ w [μ (t ) − f (t )]
i=1
i i i
2
.

Introducerea ponderilor face posibilă introducerea unei anumite discriminări între anumite
puncte din domeniul de definiţie al funcţiei f.
Astfel, dacă w1 < w2 < … < wk, atunci datele mai recente vor influenţa procesul de potrivire
mai mult decât cele anterioare.

Abordarea problemei predicţiei prin metoda de aproximare a celor mai mici pătrate este
vulnerabilă la impactul câtorva puncte cu valori disparate (valori mult în afara celorlalte, mult
mai mari ori mult mai mici) care pot distorsiona potrivirea căutată.
Pentru astfel de situaţii sunt utilizate tehnici care să favorizeze o potrivire mai robustă, prin
reducerea impactului unor astfel de puncte cu valori disparate.

Abordările combinate sunt adeseori utilizate. Astfel, reîntinerirea software-ului poate avea
loc:
o fie la momentul planificat P,
o fie corespunzător momentului pentru care s-a făcut predicţia producerii următoarei
erori.

Este ales acel moment care îl precede pe celălalt.

(a) (b)

Figura 1. Regiuni de eşec.

(a) regiuni de eşec mici, dispersate. (b) regiunea de eşec mare, compactă.

Diversitatea datelor

Spaţiul intrărilor unui program este spaţiul ce cuprinde toate intrările posibile. Acest spaţiu
poate fi divizat în regiuni de eşec şi regiuni de non-eşec. Un program eşuează dacă şi numai
dacă intrările sale aparţin unor regiuni de eşec.
Regiunile de eşec pot fi determinate în orice formă geometrică şi mărime. Spaţiul intrărilor
poate avea, tipic, un număr mare de dimensiuni, dar poate fi vizualizat doar într-un nerealist

10
 SISTEME TOLERANTE LA DEFECTE

de simplu spaţiu bidimensional. Figura 1 prezintă două reprezentări arbitrare ale unor spaţii de
eşec. Regiunile de eşec, reprezentate în figura 1 prin suprafeţele haşurate, ocupă, în ambele
cazuri, aproximativ aceeaşi arie din spaţiul intrărilor. Dar, regiunea de eşec în figura 1 (a)
constă dintr-un număr de opt zone insulare relativ mici, în timp ce regiunea de eşec din figura
1 (b) apare reprezentată printr-o arie compactă şi relativ întinsă.
În ambele cazuri, figura 1 (a) sau (b), dacă intrările sistemului sunt din zona de eşec acesta va
eşua. Diferenţa esenţială dintre figura 1 (a) şi figura 1 (b) constă în faptul că o mică
perturbaţie a valorilor intrărilor din figura 1 (a) poate face ca valorile liniilor de intrare să
părăsească regiunea de eşec şi să treacă în regiunea de non-eşec.

Defectări de felul celor reprezentate prin figura 1 (a) sugerează o posibilă abordare a
toleranţei defectelor. Dacă se consideră că intrările sistemului sunt dintr-una din zonele de
eşec, atunci o mică perturbaţie a intrărilor sistemului este posibil să scoată intrările acestuia
din aria de eşec şi să le treacă în zona non-eşec. Această abordare generică se numeşte, în
literatură, diversitatea datelor. Modul în care se implementează aceasta depinde de
mecanismele de detecţie a erorilor.
Dacă se rulează doar o singură copie a software-ului la un moment dat şi se utilizează un test
de acceptare pentru detectarea erorilor, atunci se poate recalcula acelaşi rezultat cu intrări
perturbate şi verifica rezultatul astfel determinat.
Dacă se utilizează un sistem masiv redundant, se pot aplica seturi de intrări uşor diferite
diferitelor versiuni ale programului şi urmărit rezultatul la circuitul de votare. Perturbări ale
datelor de intrare se pot face atât implicit cât şi explicit.

11
 Toleranţa la Defecte Bazată pe Algoritmi

Lucrarea este o implementare a algoritmilor care realizează toleranţa la defecte. Sunt

ilustrate operaţiile de adunare şi înmulţire a matricelor. Tehnica constă în adăugarea
informaţiilor sume de control ambilor operanzi înaintea operaţiei matriciale.

4 7 0 11 5 1 7 13
5 7 6 18 9 1 6 16
6 4 3 13 1 2 0 3
15 18 9 42 15 14 13 32

Figura 1. Două matrice bordate cu sume de control.

Informaţiile sume de control sunt adăugate fiecărei matrice operand în parte prin
calculul şi includerea corespunzătoarelor sumelor de control pentru fiecare linie şi
fiecare coloană, aşa cum se poate vedea din figura 1. Sumele de control atât pentru
fiecare linie cât şi pentru fiecare coloană au fost scrise cursiv şi îngroşat.

4 7 0 11 5 1 7 13 9 8 7 24
5 7 6 18 9 1 6 16 14 8 12 34
6 4 3 13 + 1 2 0 3 = 7 6 3 16
15 18 9 42 15 14 13 32 30 22 22 74

Figura 2. Sumarea fără erori a două matrice bordate cu sume de control.

Deîndată ce operaţia matricială a fost realizată se pot recalcula sumele de control în

matricea rezultată şi acestea se pot compara cu sumele de control obţinute prin
operarea matricelor.

4 7 0 11 1 1 7 13 5 8 7 24
5 9 6 18 9 1 6 16 14 10 12 34
6 4 3 13 + 1 8 0 3 = 7 12 3 16
27 18 9 42 15 4 13 32 42 22 22 74

Figura 3. Sumarea cu erori a două matrice bordate cu sume de control.

În cazul în care aceste sume de control nu coincid s-a detectat o eroare. Cazul în care
matricele din figura 2 au fost afectate de erori după calculul sumelor de verificare,
înainte de însumare, este prezentat în figura 3. Erorile care au afectat cele două
matrice sunt marcate în ambele matrice prin scriere îngroşată. Sumele de verificare,
din matricea rezultat, care nu coincid cu sumele de verificare calculate direct sunt
marcate în figura 3 prin subliniere şi scriere îngroşată.

1
Metoda presupune că toate erorile au apărut după ce sumele de control iniţiale au fost
calculate pentru operanzii matriceali. Raţiunea procedeului constă în faptul că sumele
de control sunt invariabile în absenţa erorilor.

Dar dacă erorile afectează, eventual, celule din aceste matrice operand, atunci
proprietatea este alterată. În aceste situaţii, recalcularea sumelor de control pentru
matricea rezultat şi comparaţia acestora cu valorile corespunzătoare după operaţia
matriceală va releva neconcordanţa.

Matricea A Matricea B

0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0

Editeaza Matricea
Editeaza Matricea

Toleranţa la defecte bazată pe algoritmi.

Instrucţiuni de utilizare
Ajutor Iniţializare
1. Alegeţi dimensiunile matricelor.

Mărimea matricelor 3 2. Editaţi conţinutul matricelor prin acţionarea

butoanelor Editează Matricea.
Alternativ se poate popula aleator matricele
10
Valoarea maximă precizând valoarea maximă, numărul de
ranguri zecimale (fracţionare) şi acţionând
Ranguri zecimale 0 butonul Matrice aleatoare.

Matrice aleatoare 3. Acţionaţi butonul Sumele de Control

Matriceale.

Sumă Produs

Utilizarea aplicaţiei:

Sunt utilizate două matrice pătrate cu care operaţiile matriceale sumă şi produs pot fi
exemplificate. Aceste matrice sunt numite generic respectiv A şi B. Cele două matrice
se află în partea de sus a ecranului în câte un cadru separat. Aceste matrice sunt
iniţializate cu valori implicite (default) 0.

2
Cadrul de jos stânga este dedicat controlului aplicaţiei iar cadrul de jos dreapta
afişează informaţie pentru utilizator ilustrând rezultatele operaţiilor matriceale.
Aplicaţia menţine o stare internă şi numai anumite funcţii pot fi realizate în fiecare
stare. Butoanele ne-utilizate într-o stare anumită nu vor fi afişate.

Aplicaţia poate fi oricând re-iniţializată prin acţionarea butonului Iniţializare din

aplicaţie ori prin butonul de reiniţializare (refresh) al browser-ului.

Stabilirea dimensiunii matricelor

Dimensiunea matricelor se va alege dintr-o listă cu valori posibile: 2, 3, . . . , 12.

Editarea matricelor
Matricele A şi B pot fi editate doar înainte ca sumele de control să fie calculate.
Utilizatorul poate introduce manual valorile dorite în fiecare matrice prin acționarea
butonului Editeaza Matricea aflat sub fiecare matrice. Astfel, se va deschide o fereastra
suplimentară care va permite introducerea datelor în fiecare matrice.
Alternativ, matricele A şi B pot fi încărcate cu numere generate aleator introducând în
prealabil valoarea maximă admisă, Valoarea maximă (input box), şi numărul de ranguri
fracţionare Ranguri zecimale (input box) dorit după virgulă.
Prin acţionarea butonului Matrice aleatoare ambele matricele vor fi populate
corespunzător.

Calculul sumelor de control

Prin acţionarea butonului Sumele de control atât matricea A cât şi matricea B vor fi
fiecare în parte bordate printr-o linie şi o coloană cuprinzând sumele de control pe
coloane şi respectiv pe linii. După apariţia acestor sume acţionaţi butoanele Introduceţi Erori
(butoanele Editeaza Matricea sunt înlocuite prin butoanele Introduceţi Erori după acţionarea
butonului Sumele de control)

Introducerea Erorilor
După ce au fost calculate sumele de control ale celor două matrice A şi B sub fiecare
matrice apare câte un buton numit Introduceţi Erori. Prin acţionarea individuală a fiecărui
buton corespunzător unei matrice se vor deschide ferestre suplimentare care vor
permite modificarea conținutului individual al celulelor matricelor (inclusiv celulele
liniei şi coloanei corespunzătoare sumelor de verificare)

Operaţii cu matricele A şi B
În aplicaţie sunt utilizate doar suma şi produsul matricelor. Pentru aceste operaţii
există câte un buton numit Sumă şi respectiv Produs.
După acţionarea unuia dintre cele două butoane de operaţii, aplicaţia calculează
rezultatul respectiv şi verifică conţinutul liniei şi respectiv coloanei de verificare.
Matricea rezultat este afişată. Celulele din linia de verificare şi din coloana de
verificare care se dovedesc că nu corespund calculului de verificare în matricea
Rezultat sunt afişate cu culoarea roşie. Matricea rezultat se afişează separat de
matricele operand care sunt menţinute pe ecran după introducerea erorilor. Matricea
Rezultat apare în zona de ecran care conţinea iniţial instrucţiunile de utilizare.
În cazul în care nu sunt erori în matricea rezultat sub matrice se afişează, cu culoarea
albastră, mesajul: Nu sunt erori.

3
  

   

Platformă de e‐learning și curriculă e‐content 
 

 
pentru învățământul superior tehnic
 

  Sisteme Tolerante la Defecte 
 

 
15.  Sisteme M ‐ din ‐ N redundante 
 SISTEME M – DIN – N REDUNDANTE

Un sistem M – din – N redundant constă din N module care are nevoie de cel puţin M
dintre acestea ca să funcţioneze corespunzător.

Un astfel de sistem încetează să mai funcţioneze atunci când mai puţin decât M
module sunt funcţionale.

Cel mai cunoscut exemplu, din această categorie, este sistemul triplex. Un astfel de
sistem constă din trei module identice ale căror ieşiri sunt votate.

Câtă vreme există o majoritate (cel puţin 2 din 3) a modulelor care produc rezultate
corecte, sistemul va fi funcţional.

Evaluarea fiabilităţii unui sistem M – din – N

Se presupune că defectarea diferitelor module este statistic independentă şi că nu se

pot repara modulele defecte.

Prin R(t) se notează, tradiţional, fiabilitatea individuală a unui modul (semnificând

probabilitatea ca modul să fie încă operaţional la momentul t).

Fiabilitatea unui sistem M – din – N este probabilitatea ca M ori mai multe module să
fie funcţionale la momentul t.

Astfel, fiabilitatea sistemului M – din – N este exprimată prin formula:

N
RM _ din _ N (t ) = ∑ CNi R i (t )[1 − R(t )]N −i (1)
i=M

Ipoteza că defectările sunt independente este un factor cheie, un factor deosebit de

important, în realizarea fiabilităţii ridicate a sistemelor M – din – N.

Chiar şi doar într-o mică măsură prezentă o corelaţie a defectărilor, aceasta poate
diminua drastic fiabilitatea acestor sisteme.

Presupunând o probabilitate nenulă qcor a corelaţiei unui defect în sistem, considerat în

totalitatea sa, atunci expresia fiabilităţii arată astfel:

N
RMcor_ din _ N (t ) = (1 − qcor ) ∑ CNi R i (t )[1 − R(t )]N −i (2)
i=M

Într-un sistem inadecvat proiectat, factorul de defectare corelat poate domina

probabilitatea defectării globale.

1
Defectările corelate pot fi foarte dificil de estimat, în practică.

Expresia (2) a fost scrisă cu asumpția existenţei unei mal-funcţionări care să afecteze
întreg grupul celor N module din sistem.

Există, de asemenea, şi alte moduri de defectare decât cel presupus în formula (2).

Sunt 2N – N – 1 submulţimi distincte care ar conţine două sau mai multe module şi în
acest mod apare ca fiind extrem de dificil de realizat experimental ori prin alte
mijloace probabilităţile asociate acestor submulţimi, fie şi doar pentru valori moderate
ale numărului total de module.
Modul

Circuitul
Modul de Vot

Modul

Figura 1. Structura unui sistem

Triplu-Modul Redundant (TMR).

Dintre sistemele M – din – N, e foarte posibil să fie cel mai cunoscut sistemul triplex,
ca un astfel de sistem.

Diagrama sistemului triplex, ori a sistemului Triplu-Modul Redundant (TMR), este

prezentată în figura 1. În astfel de sisteme, M = 2 şi N = 3, sunt trei module şi un
circuit de vot care decide majoritatea rezultatelor.

Prin utilizarea unui singur circuit de vot, acesta devine o entitate critică. Fiabilitatea
sistemului, ţinând seama de fiabilitatea circuitului de vot (notată prin Rvot (t)), arată
astfel:
3
RTMR (t ) = Rvot (t )∑ C3i R i (t )[1 − R (t )]3−i (3)
i=2

Prin dezvoltarea binomului se obţine o exprimare mai compactă de forma:

RTMR (t ) = Rvot (t )(3R 2 (t ) − 2 R 3 (t )) (4)

Cazul general al TMR se numeşte N-Modul Redundant având N module, N fiind

impar, iar M este egal cu unu plus partea întreagă a expresiei N/2.

Pentru sisteme constituite cu module având fiabilitate ridicată, cu câte este mai mare
redundanţa cu atât se obţin sisteme mai fiabile.

Atunci când fiabilitatea modulelor are valori mai mici, avantajele redundanţei scad.

Astfel, pentru sisteme constituite cu module a căror fiabilitate este joasă, aceasta
revine la inegalitatea R(t) < 0,5 , redundanţa ajunge să constituie un dezavantaj iar un

2
sistem simplu (cu un singur modul, sistem numit adesea şi simplex) devine mai fiabil
decât orice combinaţie constituită cu modulele respective.

Acest fapt se reflectă în valoarea MTTRTMR, care poate fi determinată pentru:

Rvot(t) = 1 şi R(t) = e-λt astfel:

∞ ∞
5
MTTRTMR = ∫ (3R 2 (t ) − 2 R 3 (t )) dt = ∫ (3e−2 λt − 2e −3λt ) dt = (5)
0 0
6λ

Se poate uşor aprecia faptul că:

5 1
MTTFTMR = < = MTTFSimplex
6λ λ

În cele mai multe dintre situaţiile reale, totuşi, R(t) >> 0,5 pentru valori practice ale
variabilei t iar sistemul este fie reparat, fie înlocuit mult înainte ca R(t) < 0,5 astfel
încât configuraţia triplex să confere creşteri semnificative ale fiabilităţii.

Expresia fiabilităţii sistemului Triplu-Modul Redundant s-a dedus având, presupusă

implicit, ipoteza că orice defect al circuitului de vot va implica o ieşire eronată a
sistemului şi orice defectare a două module, din trei, este determinantă pentru mal-
funcţionarea sistemului.

Astfel de situaţii nu sunt, totuşi, întotdeauna necesare pentru declararea încetării

funcţionării sistemului.

Aceasta se poate uşor constata din următorul exemplu:

Dacă un modul are, la una dintre ieşirile sale, permanent valoarea logică 1 iar un al
doilea modul are permanent valoarea logică 0, la ieşirea omoloagă, atunci TMR va
continua, aparent, să funcţioneze corect, spre exemplu.

Similar, o situaţie comparabilă poate să se întâmple şi în circuitul de vot (majoritate).

Aceste exemple vizează, în esenţă, compensarea reciprocă a defectelor.

Paradoxal, astfel de situaţii conduc la o creştere a fiabilităţii sistemelor TMR.

Circuitele de vot

Astfel de circuite au, în principiu, N linii de intrare x1, x2 … , xN la care sunt conectate
liniile de ieşire omoloage din sistemul redundant M – din - N.

Cu valorile recepţionate pe liniile de intrare, circuitul de vot generează corespunzător

o valoare reprezentativă.

Cea mai simplă metodă este compararea bit cu bit a valorilor liniilor de intrare
omoloage şi determinarea valorii majoritare.

Această metodă presupune că fiecare din cel N module ale sistemului va genera ieşiri
similare, comparabile bit cu bit, cu ale celorlalte module.

3
Dacă modulele sunt constituite cu procesoare identice care primesc aceleaşi valori de
intrare, rulează aplicaţii identice şi sunt conduse prin impulsuri de ceas mutual
sincronizate, atunci procedeul de vot este imediat.

Dar, dacă modulele sunt construite cu procesoare diferite ori rulează aplicaţii distincte
pentru aceeaşi sarcină de calcul atunci este foarte posibil să fie valori întrucâtva
divergente, (în zona biţilor de rang inferior, spre exemplu) chiar dacă, în fapt,
reprezintă rezultate corecte.

Astfel, două rezultate u şi v sunt practic identice dacă are loc relaţia:

|u – v| < δ,

unde valoarea parametrului δ este dinainte specificată.

Este de reţinut faptul că relaţia practic identice nu este o relaţie tranzitivă.

Aceasta înseamnă că atunci când m este practic identic cu n, iar n este practic identic
cu p, nu rezultă că şi m este practic identic cu p.

Se consideră o valoare δ = 0,1 şi un set cu cinci rezultate {1,11; 1,32; 3,00; 1,10;
1,49}.

Un circuit de vot bi-valoric cu parametrul δ = 0,1 va genera, pentru acest set de

rezultate, subsetul {1,10; 1,11}.

În consideraţiile care au stat la baza construcţiilor teoretice de fiabilitate ale sistemelor

TMR s-a introdus implicit ipoteza că toate liniile de ieşire conectate la intrările
circuitului de vot sunt caracterizate printr-o probabilitatea de defectare identică.

Sunt numeroase situaţii când această ipoteză este invalidată.

Circuitele ori aplicaţiile care produc un anumit rezultat pot avea probabilităţi diferite
de defectare, din raţiuni care guvernează modul de funcţionare şi de evaluare a
fiabilităţii (tehnologiile diferite, spre exemplu).

Din aceste considerente rezultă utilizarea un circuit de vot care funcţionează ponderat
şi generează ieşiri care sunt asociate la mai mult decât jumătatea sumei ponderilor
sale de funcţionare.

4
  

   

Platformă de e‐learning și curriculă e‐content 
 

 
pentru învățământul superior tehnic
 

  Sisteme Tolerante la Defecte 
 

 
16.  Variatii ale redundantei N ‐ modulare 
 VARIAŢII ALE REDUNDANŢEI N-MODULARE

Independent de utilizarea replicării modulelor şi de introducerea circuitelor de vot la

nivelul sistemului, se poate face uz de aceeaşi metodă chiar şi la nivelul fiecărui
subsistem.

Redundanţa modulară la nivelul unităţilor

O versiune a sistemului triplu-modular redundant aplicată la nivelul fiecărei unităţi

(u1, u2, u3, şi u4) dintr-un sistem constituit cu patru unităţi este prezentată în figura 1.

În această diagramă se poate remarca faptul că scade criticitatea circuitelor de vot

(blocurile V, în figura 1) din sistemele NMR. În acest caz defectarea unui singur circuit
de vot va afecta doar o unitate singulară iar efectul său nu va depăşi următorul nivel al
unităţii.

u2 V

u2 V

u1 V u2 V u4 V

u1 V u4 V

u1 V u3 V u4 V

u3 V

u3 V

Figura 1. Triplu-Modular Redundant

implementat la nivelul subsistemelor.

Sistemul triplu-modular redundant implementat la nivelul unui sistem între procesoare

şi memorii, prezentat în figura 2 are o structură deosebit de interesantă.

Procesor V Memorie

Procesor V Memorie

Procesor V Memorie

Figura 2. Circuite de vot triplicate într-un sistem triplu-

modular redundant la nivelul procesoarelor şi memoriilor.

În acest sistem toate comunicaţiile în orice direcţie dintre procesoarele triplicate şi

memoriile triplicate trec prin circuitele de vot majoritar. Această organizare a

1
sistemului este mai fiabilă decât votul majoritar singular al unei structuri având
triplicat binomul procesor – memorie.

Redundanţa dinamică

Variantele N-modular redundante (NMR) considerate până acum utilizează volume

importante de circuite hardware în scopul mascării imediate a erorilor care pot să
apară pe durata operării sistemelor.

Cu toate acestea, în multe arii de aplicaţii, rezultatele eronate care şi-au făcut temporar
simţită prezenţa s-au dovedit a fi tolerabile în măsura în care sistemul este capabil să
detecteze independent aceste erori şi să se auto-reconfigureze prin înlocuirea unui
modul defect cu un altul care funcţionează corect, care s-a aflat în rezervă până în
momentul în care s-a decis reconfigurarea sistemului.

Diagrama generică a unui sistem redundant dinamic este arătată în figura 3. Sistemul
constă din N module inactive aflate în rezervă, un modul activ şi unitatea detecţiei
defectelor şi reconfigurării.

Modul Activ

Modul Rezervă 1
Unitatea
Detecţiei
Modul Rezervă 2 Erorilor
şi
. Reconfigurării
.
.

Modul Rezervă N

Figura 3. Redundanţa dinamică.

Unitatea detecţiei erorilor şi reconfigurării se presupune că are capacitatea identificării

oricărei valori eronate aflate la ieşirea modulului activ.

Urmare a detectării erorii această unitate deconectează modulul activ curent, dovedit
defect, şi conectează în locul acestuia un modul funcţional aflat în rezervă, dacă mai
este vreunul disponibil.

Dacă toate modulele de rezervă sunt active (sunt puse sub tensiune şi alimentate) este
posibil să aibă aceeaşi viteză de defectare ca şi unicul modul activ.

Redundanţa acestei structuri este, practic, similară cu cea a sistemului paralel iar
fiabilitatea sa are expresia:

Rdinamic = Rudr (t )(1 − [1 − R(t )]N +1 ) (1)

În (1) s-a notat prin R(t) fiabilitatea fiecărui modul iar Rudr este fiabilitatea unităţii de
detecţie şi reconfigurare.

2
Dar dacă modulele aflate în rezervă nu sunt alimentate (se economiseşte energie)
acestea pot avea o viteză de defectare neglijabilă atunci când nu sunt active.

Apariţia defectelor în modulul activ are loc cu viteza λ.

Se notează prin c factorul de acoperire, definit ca fiind probabilitatea ca modulul activ

defect să fie corect diagnosticat şi deconectat iar apoi înlocuit cu succes printr-un
modul funcţional disponibil aflat în rezervă.

Astfel, probabilitatea ca o defectare să nu fie recuperată este 1 − c . Iar viteza cu care

au loc defectările irecuperabile este ( 1 − c )λ.

Prin urmare probabilitatea ca să aibă loc o defectare irecuperabilă a modulului activ

peste o durată t este determinată prin e− (1−c ) λt .

Fiabilitatea unităţii de detecţie şi reconfigurare a fost notată prin Rudr(t), rezultând

expresia fiabilităţii redundanţei dinamice:
Rdinamic (t ) = Rudr (t )e − (1−c ) λt . (2)

3
  

   

Platformă de e‐learning și curriculă e‐content 
 

 
pentru învățământul superior tehnic
 

  Sisteme Tolerante la Defecte 
 

 
17.  Redundanta hibrida 
 REDUNDANŢA HIBRIDĂ

Un sistem NMR este capabil să mascheze atât defectări permanente cât şi defectări
intermitente dar, fiabilitatea acestuia scade sub aceea a unui singur modul pe durata
unor misiuni foarte îndelungate dacă nu are loc repararea ori înlocuirea modulelor
defecte.

Scopul unei redundanţe hibride este să depăşească acest neajuns prin introducerea
unor module de rezervă care vor fi destinate să înlocuiască modulele active deîndată
ce acestea s-au defectat.

Unitatea de
Comparaţie
Ieşiri ale
Semnale de
unităţilor
dezacord
active
Primar 1
Unitatea de V
Reconfigurare
Primar N

Rezervă 1

Rezervă K

Figura 1. Redundanţa hibridă.

În figura 1 este prezentată diagrama unui sistem hibrid constând dintr-un nucleu cu N
procesoare care constituie un sistem NMR şi un set de K procesoare de rezervă.

Ieşirile modulelor primare active sunt comparate (în Unitatea de Comparaţie) urmare
a unui semnal al circuitului de vot (V) în vederea identificării unui posibil procesor
defect (dacă există vreunul).

În cazul detectării unei astfel de situaţii Unitatea de Comparaţie generează un semnal

de dezacord care va determina Unitatea de Reconfigurare să deconecteze procesorul
primar activ defect şi să conecteze un procesor de rezervă, substituind procesorul
primar defect.

Fiabilitatea unui sistem hibrid cu un nucleu TMR şi K procesoare de rezervă are

forma:

Rhibrid (t ) = Rvot (t ) Rrec (t )(1 − mR(t )[1 − R (t )]m −1 − [1 − R(t )]m ) (1)

În formulă s-a notat prin m numărul total de procesoare, m = K + 3, iar prin Rvot(t)
fiabilitatea circuitului de vot şi comparaţie şi prin şi Rrec(t) fiabilitatea unităţii de
reconfigurare.

1
În expresia (1) se presupune că orice defect care apare fie în circuitul de vot, fie în
unitatea de comparaţie şi configurare va cauza defectarea sistemului.

Practic, nu toate defectele din aceste circuite sunt capitale şi din acest motiv, în
realitate, fiabilitatea sistemului hibrid este mai mare decât fiabilitatea evaluată prin
această formulă.

E posibilă o expresie mai precisă a fiabilităţii sistemelor hibride care se poate

determina printr-o analiză amănunţită a căilor de defectare ale circuitului de vot ca şi
ale circuitelor de comparaţie şi reconfigurare.

2
  

   

Platformă de e‐learning și curriculă e‐content 
 

 
pentru învățământul superior tehnic
 

  Sisteme Tolerante la Defecte 
 

 
18.  Redundanta modulara cu filtrare 
 REDUNDANŢA MODULARĂ CU FILTRARE

Similar structurii NMR, toate cele N module din schema redundanţei modulare cu
filtrare sunt active (figura 1) iar sistemul este operaţional atâta vreme cât există cel
puţin două module funcţionale.

Ceea ce deosebeşte această structură redundantă de structura de referinţă NMR este

introducerea unor noi blocuri.

Caracteristic sunt introduse blocurile Comparator, Detector şi Colector care

înlocuiesc circuitul de vot majoritar.

Modulul 1

Modulul 2 Colector

Modulul N

F1 F2 FN
E12

Comparator Detector

E(N-1)N

Figura 1. Structura redundanţei modulare cu filtrare.

Blocul Comparator efectuează comparaţia liniilor de ieşire ale modulelor considerate

două câte două.

Liniile de ieşire ale comparatorului Eij, câte una pentru fiecare pereche distinctă de
module, sunt asertate atunci când liniile de ieşire ale celor două module, respectiv
Modulul i şi Modulul j, nu se potrivesc.

Utilizând valorile liniilor Eij, în blocul Detector, pe interfaţa cu blocul Colector, se

generează semnalele logice F1, F2, …, FN.

Atunci când aceste linii Fi sunt asertate, corespunzător lor modulele respective sunt
detectate ca fiind defecte.

Blocul Colector produce un semnal pe linia de ieşire a sistemului corespunzător

disjuncţiei liniilor de ieşire ale modulelor corect funcţionale din structură.

1
În acest mod, liniile de ieşire ale modulelor care nu corespund celorlalte linii de ieşire
sunt filtrate şi încetează să contribuie la formarea ieşirii sistemului.

Implementarea acestei structuri este apreciată ca fiind mai simplă decât a structurii
redundanţei hibride, spre exemplu.

Un punct sensibil al acestui sistem rezidă în determinarea pragului de severitate al

procesului de filtrare.
Marea majoritate a defectărilor, în astfel de sisteme, au tendinţa să prezinte un
caracter tranzitoriu şi dispar, din raţiuni proprii, după un timp.

Prin prisma acestor raţiuni pragmatice, se preferă filtrarea definitivă a unui modul abia
atunci când a livrat ieşiri incorecte pe durata unui interval susţinut de timp.

2
  

   

Platformă de e‐learning și curriculă e‐content 
 

 
pentru învățământul superior tehnic
 

  Sisteme Tolerante la Defecte 
 

 
19.  Sistemele redundante duplex 
 SISTEMELE REDUNDANTE DUPLEX

Sistemele duplex sunt cele mai simple exemple de redundanţă modulară.

Un exemplu de sistem duplex compus din două procesoare şi un comparator este

ilustrat în figura 1.

Ambele procesoare execută aceleaşi sarcini, iar dacă blocul Comparator stabileşte că
sunt concordante ieşirile celor două procesoare se conchide că rezultatul calculat este
corect.
Este implicit aplicată ipoteza unei extrem de mici probabilităţi ca ambele procesoare
să fie defecte dar, astfel încât să producă rezultate care să concorde.

Modul
Comparator

Modul

Figura 1. Structura unui sistem duplex.

Dar dacă rezultatele sunt diferite atunci, fiind dovedită o mal-funcţionare evidentă, se
apelează o rutină de nivel înalt care decide modul de tratare al erorii.

Faptul că rezultatele calculate prin cele două procesoare diferă nu poate decide
identificarea rezultatului corect implică introducerea unor criterii şi metodele
corespunzătoare detectării procesorului defect.

Fiabilitatea sistemelor duplex utilizează factorul de acoperire. Acest factor este

probabilitatea ca un procesor defect să fie corect diagnosticat, identificat şi deconectat
din structură.

Presupunând utilizarea a două procesoare identice în sistemul duplex, fiecare având

fiabilitatea T(t), atunci fiabilitatea sistemului duplex este:

Rduplex (t ) = Rcomparator (t )( R 2 (t ) + 2cR(t )(1 − R(t ))) (1)

În relaţia (1) s-a notat prin Rcomparator(t), fiabilitatea comparatorului.

Dacă se ia în consideraţie o viteză constantă λ de defectare a fiecărui procesor şi un

comparator ideal (foarte fiabil Rcomparator(t) = 1), atunci expresia MTTF pentru
sistemul duplex arată astfel:

1 c
MTTFduplex = +
2λ λ

Diferenţa majoră dintre TMR şi sistemul duplex rezidă în faptul că pentru sistemul
duplex procesorul defect trebuie identificat.

1
  

   

Platformă de e‐learning și curriculă e‐content 
 

 
pentru învățământul superior tehnic
 

  Sisteme Tolerante la Defecte 
 

 
21.  Sistemele duplex cu rezerve duplex 
 Sistemele Duplex cu Rezerve Duplex

Au fost propuse şi descrise câteva structuri resiliente mai complicate care utilizează
sistemul duplex drept un bloc de construcţie.

Sistemele duplex cu rezerve duplex, aşa cum se poate vedea din figura 1, sunt sisteme
în care modulele sunt grupate în perechi iar fiecare pereche are un comparator care
verifică dacă cele două ieşiri sunt egale (ori suficient de apropiate).

Modul
Comparator
Modul
Comparator
Comutator
Modul
Comparator
Modul

Figura 1. Structura unui sistem duplex cu rezerve duplex.

Dacă ieşirile celor două module primare nu coincid acest fapt indică o eroare a unui
dintre cele două procesoare dar nu indică şi care anume este cel ce a produs eroarea.

Rularea testelor de diagnostic, aşa cum s-a arătat anterior, ar provoca o întrerupere a
serviciului furnizat de sistemul respectiv.

În scopul evitării întreruperii serviciului întreaga pereche este deconectată iar calcul
va fi continuat de o pereche de procesoare aflate, până atunci, în rezervă.

Cele două procesoare excluse din sistem pot fi, în acest context, testate separat şi
independent de activitatea sistemului.

Testarea are în vedere stabilirea naturii erorii - eroare tranzitorie ori eroare
permanentă, pentru procesorul în cauză.

În cazul în care eroarea s-a stabilit ca fiind de natură tranzitorie, perechea de

procesoare poate fi, eventual, declarată ca fiind o pereche funcţională şi introdusă în
rezervă.

1
  

   

Platformă de e‐learning și curriculă e‐content 
 

 
pentru învățământul superior tehnic
 

  Sisteme Tolerante la Defecte 
 

24. Retele si sisteme distribuite tolerante la defecte 
 
 RETELE SI SISTEME DISTRIBUITE TOLERANTE LA DEFECTE

Heartbeats

Heartbeats reprezintǎ o abordare comunǎ a detectǎrii mal-funcționării proceselor din

diverse noduri ale unui calcul distribuit.

Periodic, o entitate din reţea care monitorizeazǎ, trimite un anumit mesaj (numit a
heartbeat, ce se poate interpreta ca însemnând o bǎtaie de inimǎ, în traducere liberă)
unui anumit nod ori unui anumit proces monitorizat şi aşteaptǎ o anumită replică.

Dacǎ nodul monitorizat nu rǎspunde într-un interval de timp prestabilit, acesta este
declarat nefuncţional şi se iniţiazǎ un proces corespunzător de recuperare.

Durata intervalului de timp este, eventual, pre-negociată ori adaptată volumului de

trafic din reţea, dar şi stării de încărcare a nodurilor etc.

În funcţie de natura aplicaţiei monitorizate acest procedeu poate fi mai laborios.

Aplicaţiile dezvoltate multi-fir au un fir de execuţie dedicat răspunsului la heartbeat.

Pe de-altă parte, dacă unul sau mai multe dintre firele aplicaţiei monitorizate nu
progresează, sau sunt blocate, firul care răspunde monitorizării trebuie să aibă acces la
starea proceselor dedicate sarcinii respective.

Riscul este să fie considerat procesul monitorizat ca fiind blocat şi re-iniţiat ceea ce
poate constitui o situaţie eventual ciclică, posibil nedorită, chiar foarte gravă într-un
sistem în timp real etc.

Conceptul de bazǎ în redundanţa temporalǎ este repetarea calculului de douǎ ori de

mai multe ori cu compararea rezultatelor pentru a detecta apariţia unor posibile
deosebiri.

Dacǎ se detecteazǎ o deosebire, calculele pot fi re-executate pentru a stabili dacǎ

deosebirea continuă să fie prezentă ori dispare.

Aceste abordǎri sunt utile pentru detectarea erorilor datorate unor defecte tranzitorii
dar sunt mai puţin eficiente în raport cu erorile care provin din defecte permanente din
sistem.

O altǎ metodǎ de redundanţǎ temporalǎ, de data aceasta pentru tratarea defectelor

permanente, vizează modificarea manierei în care se executǎ calculele aritmetice
atunci când are loc repetarea acestora.

O soluție posibilă pune în valoare o logicǎ combinaţională auto-duală (pentru calcul

aritmetic binar).

1
Astfel, se executǎ o anumită funcție aritmetică corespunzător unui set de operanzi
într-o primă etapă şi re-executǎ aceeași funcție aritmetică cu intrǎrile complementate
la cea de-a doua execuţie.

Rezultatul celui de-al doilea calcul ar trebui sǎ fie complementul primului rezultat
obţinut. Dacǎ al doilea rezultat al calculului aritmetic nu este complementarul
primului, aceasta constituie detecţia unei erori.

Abordarea urmǎtoare utilizeazǎ o reefectuare a calculului cu operanzii deplasați spre

stânga şi este aplicabilǎ unor unităţi aritmetico-logice cu lungime suficientă a
registrelor. În prima etapă se executǎ calculul normal al operanzilor. În a doua etapă
operanzii sunt deplasați spre stânga cu k biți (multiplicaţi cu 2k), iar rezultatul astfel
obţinut va fi corectat în registrul acumulator. Adică acesta va fi deplasat spre dreapta
tot cu k biți iar rezultatul se va compara cu cel din calculul precedent.

Timerele watchdog

Timerele watchdog sunt o categorie importantă de întreruperi în orice sistem de

calcul. Atunci când se startează un anumit proces, pentru care există o evaluare
acoperitoare a timpului de execuţie, se declanşează un astfel de timer. Procesul
supravegheat, la încheierea sa trebuie sǎ blocheze declanşarea timerului înainte ca
acesta sǎ expire; altminteri procesul este considerat ca fiind defect.
Un avantaj important al acestei metode constă în faptul că nu utilizează un model
anume al defectului. Printre dezavantaje se poate cita o limitare, cumva, a acestei
metode. Astfel, daca procesul supravegheat generează o eroare, cu mult înaintea
declanşării timerului, timerul va fi resetat prin mecanisme de sistem şi vor trebui
declanşate rutine corespunzătoare care sa investigheze cauzele generării erorii.

2
  

   

Platformă de e‐learning și curriculă e‐content 
 

 
pentru învățământul superior tehnic
 

  Sisteme Tolerante la Defecte 
 

 
26.  Redundanţa temporală ‐ Checkpoint 
 REDUNDANŢA TEMPORALĂ (CHECKPOINT)

Multe dintre aplicaţiile curente pot să se deruleze pe durate lungi de timp. În acest
sens se pot cita aplicaţii mari consumatoare de timp ca fiind:

- simulările unor circuite complexe (microprocesoarele) înaintea producerii

măştilor (sunt raportate durate de ordinul săptămânilor)
- aplicaţiile de proiectare şi optimizare automată a circuitelor digitale
laborioase,
- calcul financiar-bancar previzional etc.

Orice eroare semnalată şi detectată, la un moment dat, poate declanşa reluarea unei
astfel de aplicaţii cu masive implicaţii asupra costurilor dar chiar şi asupra
oportunităţii reluării respectivei aplicaţii.

Duratele lungi de calcul fac întotdeauna ca probabilităţile de apariţie ale unor erori să
crească, indiferent de cauzele care favorizează ori produc respectivele erori.

Un model analitic al unei astfel de situaţii poate fi creionat astfel:

• Rularea completǎ a programului dureazǎ T ore. Sistemul

este afectat de defecte tranzitorii cu o medie de l erori
într-o orǎ.
• Defectul este tranzitoriu dar tot volumul de calcul până
în momentul apariţiei defectului este iremediabil
pierdut.

STUDII DE CAZ

Se presupune că sistemul este afectat de defecte tranzitorii modelabile printr-un

proces Poisson cu viteza de λ defecte într-o unitate de timp.
Se consideră că timpul de reluare a procesului de calcul al sistemului, urmare a unei
defectări aleatorii, este neglijabil.

Se notează prin E timpul mediu de execuţie al proceselor de calcul, incluzând orice

timp al unor calcule pierdute ca urmare a apariţiei erorilor tranzitorii.

Există două situaţii:

- nu are loc nici o defectare a sistemului pe durata procesului de calcul dorit,
- există cel puţin o defectare a sistemului pe durata procesului de calcul dorit.

În primul caz durata execuţiei procesului de calcul dorit este T.

Probabilitatea să nu apară nici un defect într-un interval de timp cu durata T este:
p = e − λT .

Astfel, durata medie a timpului de execuţie a procesului de calcul fără defecte este de
forma:
Tmediu = Te− λt (01)

1
Dar dacă se consideră şi apariţia unui defect tranzitoriu în intervalul de timp [0, T] la
momentul τ∈[0, T], atunci timpul mediu de execuţie are expresia:
e λT − 1
E= (02)
λ
Se poate aprecia că media timpului de execuţie este deosebit de sensibilă cu T. În
adevăr E creşte exponenţial cu T.

Penalizarea indusă de procesul de apariţie al unui defect tranzitoriu poate fi evaluată

prin expresia: E – T.

Adică, timpul suplimentar impus prin pierderea unui volum de calcule la un moment
dat datorită defectului tranzitoriu.

Prin normalizarea acestei penalizări faţă de durata nominală de execuţie se obţine

metrica adimensională a acestei penalizări:
e λT − 1
η= −1 (03)
λT

De remarcat faptul că penalizarea η depinde numai de produsul λT.

Produsul λT reprezentând că numărul mediu de defectări care va afecta procesorul pe
durata unei execuţii.

Este evident că pentru valori mici ale numărului mediu de defectări penalizarea η are
valori modeste dar deîndată ce produsul λT va lua valori mai mari, penalizarea η
atinge valori mult mai importante.

Faptul că în urma apariţiei unui defect tranzitoriu se pierde tot ceea ce s-a calculat
până în acel moment devine foarte supărător atunci când apariţia defectului tranzitoriu
are loc cât mai aproape de încheierea procesului de calcul.

O soluţie este introducerea periodică a salvării, undeva pe un mediu (eventual extern)

suficient de fiabil, a tuturor rezultatelor parţiale ale calculelor de până în acel moment.
Astfel încât, să se poată relua calculul pornind de la acestea, dacă în viitor, înaintea
unei altei salvări periodice reapare un defect tranzitoriu.

Salvarea la un moment dat a informaţiilor cheie astfel încât să se poată relua calculul
pornind de la acele informaţii, este un checkpoint.

Mediul de salvare al informaţiei trebuie să fie nu numai fiabil dar să poate găzdui,
eventual, un volum suficient de mare de informaţie cu costuri reduse. Nu sunt rare
situaţiile în care informaţia salvată periodic are volume de ordinul sutelor de mega-
octeţi.

În aceste condiţii sunt preferate discurile clasice ca mediu de salvare. Chiar şi dacă se
întrerupe sursa de alimentare a acestora, nu se pierde informaţia stocată, atâta timp cât
nu este afectat mediul de stocare (suprafaţa, în cazul discurilor clasice).

2
Sunt şi situaţii când memoria RAM, asigurată eventual şi printr-o sursă suplimentară
foarte stabilă de alimentare electrică (cum ar fi bateriile, spre exemplu), poate găzdui
astfel de checkpoint-uri.

O frecventă salvare a informaţiilor necesare şi suficiente pentru reluare procesului de

calcul poate induce o creştere a timpului de execuţie, indiferent dacă apar sau nu apar
defecte tranzitorii.

Această creştere a timpului de calcul, impusă de procesul de salvare defineşte

suprasarcina indusă de procesul de checkpoint-are.
Legat de procesul de checkpoint-are este de luat în consideraţie şi timpul de salvare al
informaţiilor. Aceste timp este numit în literatură latenţa checkpoint-ării.

În cele mai multe dintre aplicaţiile foarte simple suprasarcina şi latenţa checkpoint-
ării sunt aproape identice.

Dar, în cazul sistemelor mari care permit o suprapunere a operaţiilor de salvare cu

execuţia aplicaţiei, latenţa poate fi substanţial mai mare decât suprasarcina.
Latenţa checkpoint-ării depinde mult de volumul salvărilor.