Hugo Albuquerque, João Vitor, Maria Cireno, Thiago Lima {hra, jvob, mcrs, tavl}@cin.ufpe.br
Preview:
Citation preview
- Slide 1
- 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.
- Slide 25
- SMR
- Slide 26
- Tcnicas Auxiliares Mid-value Selection Flux Summing
- Slide 27
- 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.
- Slide 58
- Obrigado!