Hugo Albuquerque, Joo Vitor, Maria Cireno, Thiago Lima {hra,
jvob, mcrs, tavl}@cin.ufpe.br
Slide 2
Agenda Motivao Introduo Conceitos Tolerncia a falhas Redundncia
Deteco e correo de erros Aplicaes
Slide 3
Motivao Necessidade crescente de sistemas mais confiveis
Controle de vo, Sistemas bancrios, etc. Interrupo de servio pode
ter consequncias catastrficas para alguns servios Tolerncia a
falhas visa evitar ao mximo essas interrupes do sistema.
Slide 4
Introduo O que um Sistema Tolerante a Falhas? Sistema que
continua provendo corretamente os seus servios mesmo na presena de
falhas de hardware ou de software. Defeitos no so visveis para o
usurio, pois o sistema detecta e mascara (ou se recupera) defeitos
antes que eles alcancem os limites do sistema (ponto de fuga da
especificao). O que Tolerncia a Falhas? um atributo que habilita o
sistema para ser tolerante a falhas. o conjunto de tcnicas
utilizadas para detectar, mascarar e tolerar falhas no
sistema.
Slide 5
Conceitos Servio e Tarefa Falha Erro Defeito
Dependabilidade
Slide 6
Servio e Tarefa Servios so funcionalidades oferecidas ao
usurio. Em STR, possuem limitao temporal. Servios so fornecidos
atravs de tasks(tarefas) Tarefas so trechos de cdigo ou subrotinas
para fornecer uma funcionalidade especfica. Podem ser classificadas
quanto sua prioridade ou ocorrncia
Slide 7
Tarefas (Classificao) Quanto a sua ocorrncia: Aperidicas: podem
ser disparadas a qualquer momento. Espordicas: podem ocorrer a
qualquer momento, porm o tempo mnimo entre as ativaes conhecido.
Peridicas: intervalo entre disparos conhecido e fixo. Quanto a sua
prioridade: No-Crticas: atrasos e falhas so tolerveis.
Semi-Crticas: atrasos so tolerveis, mas falhas no. Crticas: falhas
ou atrasos no so tolerveis.
Slide 8
Falha Falha: problema ou imperfeio no nvel fsico Curto
circuito, falhas algortmicas, etc. Podem ser classificadas em:
Transitrias: ficam ativas por um certo perodo de tempo.
Intermitentes: faltas transitrias ativas periodicamente.
Permanentes: aps ocorrer, permanecem ativas at correo.
Slide 9
Erro Erro: desvio na exatido ou preciso da computao Ocorrem no
nvel computacional. Associados a valores incorretos do estado do
sistema. Causados por falhas.
Slide 10
Defeito Defeito: sistema no corresponde ao esperado Desvio da
especificao Sistema no age de acordo com especificao ou Especificao
no descreve adequadamente o sistema Quando servios no so fornecidos
da forma ou prazo esperados pelo usurio Podem gerar consequncias
catastrficas
Slide 11
Dependabilidade Uma propriedade de um sistema computacional,
tal como usabilidade, desempenho e custo. Dependabilidade diz
respeito a habilidade de entregar um servio comprovadamente
confivel, ou seja, habilidade do sistema para evitar defeitos
inaceitveis para seus usurios.
Slide 12
Atributos da dependabilidade Disponibilidade diz respeito a
mdia de tempo disponvel para acesso Confiabilidade diz respeito a
continuidade da entrega de servio correto Integridade impedimento
de alteraes de estado imprprias Segurana (safety) diz respeito a
garantias de no haver defeitos catastrficos ao usurio ou
ambiente
Slide 13
Atributos da dependabilidade Confidencialidade impedimento de
acesso indevido Mantenabilidade habilidade para reparo e modificaes
eficientes Segurana (security) proteo contra acessos, ou controle,
no autorizados ao estado do sistema Testabilidade facilidade para
testar o sistema (ponto de teste, testes automatizados)
Slide 14
Como obter dependabilidade Preveno de Falhas: Visa prevenir a
ocorrncia ou introduo de falhas Remoo de Falhas: Visa reduzir o
nmero ou a severidade das falhas Previso de Falhas: Visa estimar o
nmero presente, a incidncia futura e as conseqncias das falhas
Tolerncia a Falhas: visa entregar o servio correto mesmo na presena
de falhas
Slide 15
Tolerncia a falhas Redundncia Requisito bsico Hardware/software
tolerante a falhas Implementada por mascaramento ou deteco de
erros, seguidos de recuperao do sistema. Recuperao consiste no
re-estabelecimento do estado correto do sistema
Slide 16
Tipos de Redundncia Hardware NMR, TMR, SMR, etc. Software
N-Version, N-Self-Checking Programming, etc. Informao Cdigos de
deteco/correo de erros, RAID, etc. Tempo Re-execuo de cdigo em
momentos distintos, etc.
Slide 17
Slide 18
Tcnicas de tolerncia a falhas NMR / TMR / 2MR SMR Mid-value
Selection Flux Summing Standby Sparing N Version Blocos de
recuperao
Slide 19
NMR N Modular Redundancy N mdulos paralelos Suporta at n-1/2
falhas. Sistema fail-silent Com ou sem Sistema de Votao Sistema de
votao um ponto crtico de falhas.
Slide 20
NMR
Slide 21
TMR Triple Modular Redundancy NMR de ordem 3
Slide 22
2MR 2 Modular Redundancy NMR de ordem 2 Duplicao com Comparao
Apenas detecta falhas Efetivo para Sistemas fail-silent
Slide 23
2MR
Slide 24
SMR Siftout Modular Redundancy Tolerante N-2 falhas. Mais
simples que NMR Mais eficiente e confivel do que sistemas NMR com
circuito de votao.
Mid-value Selection Efetivo para sistemas com sadas
no-booleanas Sistemas de sensores selecionada a mediana dos valores
de sada dos mdulos do sistema Pode ser definida uma faixa de
valores vlidos
Slide 28
Flux Summing A sada do sistema reusada como entrada. Uso
efetivo para correo dos mdulos. Facilita a identificao e correo de
mdulos defeituosos. Segue diagrama:
Slide 29
Flux Summing (figura)
Slide 30
Standby Sparing (a.k.a.: standby replacement) Um ou mais mdulos
em standby Apenas um mdulo operacional Em caso de falha, descarte
do mdulo operacional e substituio por mdulo em standby Hot Standby
Cold Standby
Slide 31
Hot standby Tcnica em que o mdulo principal e os secundrios
executam simultaneamente. Apenas as sadas do mdulo principal so
consideradas. Dados so espelhados do mdulo principal para os mdulos
secundrios. Dados so idnticos em todos os mdulos. Rpida recuperao
em caso de falha.
Slide 32
Cold standby Tcnica em que mdulos secundrios s so ativados em
caso de falha no mdulo principal. Espelhamentos podem ser
executados esporadicamente do mdulo principal para os mdulos
secundrios. Baixo consumo de energia.
Slide 33
Hot standby X Cold standby CaractersticaHot StandbyCold Standby
Gasto de energiaAltoBaixo Tempo de RecuperaoBaixoAlto Desgaste dos
mdulosAtoBaixo
Slide 34
N Version (Replicao de software) N equipes isoladas entre si
Apenas 1 especificao de projeto Cdigos gerados tendem a ser
diferentes entre si Tendem a no compartilhar dos mesmos erros
Probabilidade de falha de programao inversamente proporcional a
N.
Slide 35
N Version Similar ao NMR, de hardware. O cdigo gerado por cada
equipe executa em paralelo nos mdulos do sistema So submetidos a
comparao de resultados para detectar erros de programao Eficaz
apenas para deteco de erros lgicos Subentende-se que o hardware no
possui erros de projeto e fabricao.
Slide 36
N self-checking version Extenso ao N Version N equipes isoladas
entre si Apenas 1 especificao de projeto Equipes devem projetar
tambm um mdulo de verificao de corretude lgica para seus prprios
mdulos Mdulos em que sua sada no passar no prprio teste no
considerada vlida pelo sistema de votao.
Slide 37
N self-checking version
Slide 38
Blocos de Recuperao Extenso ao N version N verses de software,
apenas 1 executando no sistema Em caso de falha na verso
operacional, o sistema passa a executar uma das verses em standby
Falha detectada atravs de teste de corretude, a qual so submetidas
as sadas dos mdulos antes de se tornarem sada do sistema. Falha no
sistema caso nenhuma das verses passe na verificao de
corretude.
Slide 39
Slide 40
Verificao de capacidade Visa detectar falhas antes da ocorrncia
do erro Verificar a capacidade do sistema antes de executar uma
tarefa Verificar o funcionamento dos componentes Memria Comunicao
Executado no tempo livre do processador Geralmente gerenciada por
software (sistema operacional)
Slide 41
Verificao de consistncia Verificar determinados pontos da
computao procura de inconsistncias Por exemplo, checar se o valor
de uma varivel est dentro de um intervalo pr-determinado
Slide 42
Deteco de erros Execuo de testes para verificar ocorrncia de
erros Teste ideal Baseado apenas na especificao do sistema (caixa
preta) Completo e correto Independente do sistema em relao
suscetibilidade de erros
Slide 43
Testes de deteco de erros Testes de replicao Testes de
temporizao (timing) Tempo de resposta Testes estruturais e
semnticos Codificao Testes de coerncia Assertions Testes de
diagnstico Output calculado vs. Output previsto
Slide 44
Tcnicas de deteco de erros Duplicao Improbabilidade da alterao
ocorrer no mesmo local nos dois conjuntos simultaneamente Paridade
simples, vertical ou TRC (Transverse Redundancy Check) 1 bit a cada
caractere (byte) Paridade par ou mpar (n de 1s) Identificar nmero
mpar de bits trocados Taxa de utilizao de bits: R = 8/(8+1) = 88,8%
CaractereASCIIBinrioParidade parParidade mpar A41100000101
B42100001001 C43100001110
Slide 45
Tcnicas de deteco de erros Paridade horizontal ou LRC
(Longitudinal Redundancy Check) Caractere de paridade para blocos
de caracteres Detecta mais de 1 erro em cada caractere, porm apenas
1 erro por ordem de bit Taxa de utilizao: R = n/(n + 1), n n de
caracteres no bloco Caractere12345678910Paridade (LRC) bit
011010110100 bit 101010110101 bit 210010010010 bit 310011000010 bit
410111100010 bit 510100100111 bit 600001110111 bit
700010010110
Slide 46
Tcnicas de deteco de erros CRC (Cyclic Redundancy Check)
Transmisso: Cada bit da mensagem representa um coeficiente de um
polinmio M(X) Define-se um polinmio gerador G(X) de grau r
Desloca-se a mensagem M(X) de r bits para a esquerda Divide-se M(X)
por G(X), atravs de um XOR ( ) Soma-se o resto da diviso mensagem
deslocada, formando a mensagem composta T(X) Recepo: T(X) dividido
por G(X) Se o resto no for nulo, existe um erro na transmisso
Slide 47
Tcnicas de deteco de erros CRC (Cyclic Redundancy Check) Ex:
Mensagem: M(X) = 110011 (X 5 + X 4 + X + 1) Polinmio: G(X) = 11001
(X 4 + X 3 + 1) T(X) = 1100111001 Como o resto final foi nulo, no
foram detectados erros M(X) 1100110000 11001 G(X) 11001 100001
Quociente 0 10000 11001 Resto = CRC 1001 T(X) 1100111001 11001 G(X)
11001 100001 Quociente 0 11001 11001 Resto = CRC 0000
Slide 48
Tcnicas de deteco de erros Checksum Simples soma dos caracteres
transmitidos Realiza-se a operao mdulo sobre o resultado para
garantir o limite de tamanho no checksum Quando recebida a
mensagem, calcula-se o checksum novamente e compara-se com o
checksum recebido Ex: 1A H 75 H F8 H 9C H soma = 223 H mod (256 10
) = 23 H
Slide 49
Confinamento e Avaliao de Danos Caso necessrio, deve-se
confinar o erro, a fim de que o mesmo no se propague a outras
partes do sistema Erros propagam-se atravs da comunicao de
componentes Avaliao atravs do fluxo da informao a partir do
componente defeituoso
Slide 50
Recuperao de erros Para trs ou por retorno (Backward Recovery)
Checkpoints em pontos estveis Independe da natureza da falha
(exceto hardware) Overhead (checkpoints e rollback) Para frente ou
por avano (Forward Recovery) Medidas corretivas No h overhead
Depende de avaliao e suposies precisas
Slide 51
Tratamento de falhas Localizao da falha Reparo do sistema
Correo Reconfigurao Troca de componente
Slide 52
Tcnicas de correo de erros Paridade combinada Paridade vertical
+ horizontal Permite a localizao do erro
Caractere12345678910Paridade (LRC) bit 011010110100 bit
101010110101 bit 210010010010 bit 310011000010 bit 410111100010 bit
510100100111 bit 600001110111 bit 700010010110 Paridade
(VRC)1000111010 Caractere12345678910Paridade (LRC) bit 011010110100
bit 101010110101 bit 210010010010 bit 310011000010 bit 410111000011
bit 510100100111 bit 600001110111 bit 700010010110 Paridade
(VRC)1000101010
Slide 53
Tcnicas de correo de erros Cdigo de Hamming (c, d) Adio de bits
de redundncia a bloco de dados Deteco de 2 bits de erros ou correo
de 1 bit Bits de Hamming em potncias de 2 (1, 2, 4, 8,...)
Quantidade de bits de Hamming d + p 2 p 1
Slide 54
Tcnicas de correo de erros Cdigo de Hamming (c, d) Codificao
Para cada bit de dado ativo (1) escreve-se sua posio em binrio
Realiza-se o XOR entre as posies, 2 a 2 O resultado identifica os
bits de Hamming em ordem inversa Decodificao Realiza-se o XOR das
posies em binrio dos bits ativos de todo o bloco recebido
(incluindo os bits de Hamming) Se o resultado for nulo, no houve
erros Caso contrrio, o resultado identifica em formato binrio a
posio do erro
Slide 55
Tcnicas de correo de erros Cdigo de Hamming (c, d) Ex: Mensagem
10011001 Codificao p 1 p 2 1p 4 001p 8 1001 Hamming 0011 0111 1001
1100 = 0001 (3) (7) (9) (12) Resultado 101000101001
Slide 56
Tcnicas de correo de erros Cdigo de Hamming (c, d) Ex: Dado
1101 Codificao p 1 p 2 1p 4 101 Resultado 1010101 Situao de erro AC
B 1 1 1 0 10 0 AC B 1 0 1 0 10 0 0 1 0
Slide 57
Aplicaes Longa vida Satlites, sondas espaciais, marca-passo,
etc. Computao crtica ABS, airbag, alarmes de incndio, controles de
usinas nucleares, equipamentos de radioterapia, sistemas de suporte
vida (ventiladores, bypass, etc) Alta disponibilidade Internet,
ATMs, etc.
