Resumo Sistemas de Tempo Real

Prévia do material em texto

Sistemas de Tempo Real
Definição
Possuem requisitos temporais em sua especificação. 
Não estão limitados a questão de desempenho
Sistemas de tempo real são sistemas cujo comportamento estão sujeitos às restrições temporais.
Tipos de uso
Controle
Baixo processamento
Requerem pouca memória
São sistemas altamente reativos (muito interativo)
Processamento de dados
Processamento digital de sinais
Alto processamento
Pouco interativo
Tempo e suas diferentes interpretações
Tempo na Execução: considerado como um recurso a ser gasto na execução de um programa como quaisquer outros recursos físicos ou lógicos. Tempo intervém de forma implícita.
Tempo na Programação: visto como uma grandeza a ser manipulada pelo programa como outros tipos de variáveis. Tempo intervém de forma implícita ou explícita.
Tempo Lógico: estabelece relações lógicas de precedência entre eventos, permitindo o estabelecimento de ordens causais sobre um conjunto de eventos.
Tempo Físico: tempo métrico que permite expressar quantitativamente distância entre eventos (tempo tradicional) e estabelecer ordens totais entre eles.
Tempo Denso: segue a natureza contínua do tempo físico, sendo isomorfo ao conjunto dos reais.
Tempo Discreto: simplificação do tempo físico real, sendo isomorfo ao conjunto dos inteiros positivos.
Tempo Global: noção abstrata que permite ao usuário de um sistema distribuído ter acesso a um instante de referência único em qualquer parte do sistema.
Tempo Absoluto: referência temporal é estabelecida com base em um evento global. (e.g. boot do sistema)
Tempo Local: observável localmente nos diferentes nós de um sistema distribuído
Tempo Relativo: referência temporal tomada a partir de um evento local
Conceituação Básica e Caracterização de um Sistema de Tempo Real (STR)
Um Sistema de Tempo Real (STR) é um sistema que deve reagir a estímulos oriundos de seu ambiente em prazos específicos.
O comportamento correto de um STR depende não somente de sua corretude lógica, mas também em termos do tempo para os resultados serem produzidos: resultados devem ser corretos logica e temporalmente.
Um STR é portanto um Sistema Reativo com Restrições Temporais.
A Previsibilidade nos Sistemas de Tempo Real
Previsibilidade: um sistema de tempo real é dito previsível no domínio lógico e temporal quando, independentemente de variações de hardware (i.e. desvios de relógio), da carga e de falhas, o comportamento do sistema pode ser antecipado, antes de sua execução.
Hipóteses acerca do ambiente
Hipótese de Carga: sabe-se como o ambiente se comporta e qual a carga computacional máxima gerada pelo ambiente em um intervalo mínimo de tempo
Hipótese de Falhas: descreve o tipo e frequência de falhas com as quais o sistema deve conviver
É preciso também que se conheça totalmente a infraestrutura de hardware associada e os tempos de execução de cada função/instrução a ser utilizada no sistema. Esses tempos limites são necessários nas análises e verificações do comportamento temporal do sistema de tempo real.
Fontes de incerteza (imprevisibilidade) de hardware e construções de linguagens
DMA
Memória Cache (não se sabe quando)
Hierarquia de memória
Laços e recursão não limitados
Alocação dinâmica de memória
Criação dinâmica de objetos
Construção Delay de Ada, que estipula apenas um limite mínimo na suspensão de uma tarefa, mas não o limite máximo.
Escolhas não determinísticas, Salto-nd (select)
Garbage collector
Um sistema é previsível quando podemos antecipar que todos os prazos colocados a partir das interações com seu ambiente serão atendidos.
Classificação de Sistemas de Tempo Real
Soft Real Time Systems (Sistemas Brandos de Tempo Real): Sua operação é degradada se as restrições de tempo não são obedecidas.
Requisito temporal descreve apenas comportamento desejado
Perda do deadline não tem consequências catastróficas
Existe interesse em terminar a tarefa mesmo com atraso
Exemplos: Sistemas de comunicação telefônicos, Sistema de processamento bancário
Hard Real Time Systems (Sistemas Críticos de Tempo Real): Sua operação é incorreta se as restrições de tempo não são obedecidas.
É necessário garantir requisitos temporais ainda durante o projeto
Exemplos: Sistemas de controle voo, Sinalização em ferrovias, Sistema de controle de planta nuclear, indústria petroquímica, mísseis
Paradigmas
Guaranteed response system (Sistemas de Resposta Garantida):
Existem recursos suficientes para garantir uma resposta até  mesmo no cenário de carga máxima.
Best effort system (Sistemas de Melhor Esforço):
Usa uma estratégia de alocação dinâmica de recursos, baseando-se em estudos probabilísticos de carga esperada e os cenários de falha aceitáveis. (Essa não é um paradigma bom para sistemas críticos)
Não existe garantia de que os deadlines serão cumpridos
Sempre que uma tarefa é ativada, ocorre uma análise de sua escalabilidade
Passível de sofrer sobrecarga
Capaz de fornecer análise probabilística
Algumas abordagens fornecem garantia dinâmica
Descarte de tarefas na sobrecarga
As tarefas executadas cumprem o deadline
Mais apropriado para tarefas com deadline firm (cujo resultado não tem valor após deadline)
Pode cancelar ativações individuais ou tarefas completas
Maximizar o número de tarefas executadas
Perda de deadline na sobrecarga
Em sobrecarga atrasa algumas tarefas
Possui uma função que indica o valor de cada tarefa em função de seu instante de conclusão (time-value function)
Objetivo é maximizar o valor total do sistema (somatório de todas as tarefas)
Redução de Precisão na Sobrecarga
Em sobrecarga diminui a precisão de algumas tarefas
Objetivo é fazer o possível dentro do disponível
Ignorar bits menos significativos
Trabalhar com amostras de áudio menos precisas
Alterar resolução e tamanho da imagem na tela
Simplificar animações
Usar algoritmos de controle mais simples
Interromper pesquisa em algoritmos de IA
Deadline: Tempo máximo para o término de uma tarefa
Deadline firme: 
Perda do deadline não tem consequências catastróficas
Não existe valor em terminar a tarefa após o deadline (e.g. ler o valor da temperatura)
Release Time: Tempo mínimo para início de uma tarefa
Tempo de execução: Considera o tempo de pior caso (WCET - Worst-case execution time)
Abordagens para problemas de tempo real
Assíncrona
Trata a ocorrência e percepção de eventos independentes numa ordem arbitrária e não simultânea.
Depende das ferramentas de implementação
Síncrona
Observação de eventos é cronológica, e existe uma possuem simultaneidade entre os mesmos.
Se baseia no princípio de que os cálculos e a comunicação não levam tempo. (não leva em consideração tempo de execução de instruções, etc). 
Menos dependente de implementação de hardware
Sistemas Reativos
Estímulo periódico: ocorre em intervalos de tempo conhecidos
Estímulo aperiódico/assíncrono: ocorre em intervalos de tempo imprevisíveis (Não garantem escalonabilidade)
Estímulo esporádico: não é periódico mas sabemos  o intervalo mínimo entre ocorrências
Escalonamento de Tempo Real
Escalonamento
	Ordem de Def Prioridades/Ordem de execução tarefas
	Offiline
	Online
	Estático
	Executivo Cíclico, ...
	Rate Monotonic (RM), Deadline Monotonic (DM)...
	Dinâmico
	N/A (Impossível)
	Earliest Deadline First (EDF), Windows, Linux, etc...
Sistemas de Prioridade Dinâmica
Earliest-Deadline-First (EDF)
Escalonamento preemptivo de prioridade dinâmica
Deadline é calculado quando a tarefa é disparada
Escalonador põe pra executar a tarefa com menor deadline
Least Slack Scheduling
Escalonamento não-preemptivo de prioridade dinâmica
Tarefa com maior sobra (Slack) tem maior prioridade
Teste de Escalonabilidade
Necessário reservar recursos para o pior caso
Difícil determinar o pior caso em soluções off-the-shelf
Gera enorme subutilização de recursos
Tipos de Escalonamento
Preemptivo
Não-Preemptivo
Estático
Quando a ordem de execução toma como base parâmetros definidos em tempo deprojeto
Hipótese de Carga estática ou limitada
Conhecemos a carga a-priori
Permite obter garantia de escalonabilidade em tempo de projeto: o sistema é determinístico
Dinâmico
Quando a ordem de execução toma como base parâmetros definidos em tempo de execução
Hipótese de Carga Dinâmica ou ilimitada
Não permite garantias em tempo de projeto
Implica na existência de tarefas aperiódicas/assíncronas
Offiline: Quando a escala é definida em tempo de projeto
Online: Quando a escala é definida em tempo de execução
Características de Escalonamento
Justica (Fairness):  todos os processos têm chances iguais de uso do processador
Eficiência: O objetivo é manter a CPU 100% ocupada
Tempo de Resposta: Tempo entre a requisição da ação e obtenção do resultado
Throughput: Número de tarefas por unidade de tempo
Modelagem das tarefas:
Periódicas: Pela previsibilidade, conjunto de tarefas de deadline hard
Aperiódicas/Assíncronas: imprevisível, normalmente têm deadlines soft, conjunto de tarefas 
Esporádicas: tarefas aperiódicas com um intervalo mínimo conhecido entre ativações, podem ter atributos de tarefas críticas. Essas tarefas são portanto associadas a deadline hard.
Tarefas Periódicas:
Deadline monotonic
Teste de Escalonabilidade
Onde
As tarefas são escalonáveis se Ri <= Di para todas as tarefas.
Tarefas Aperiódicas
Escalonamento de Tarefas Aperiódicas
Abordagem híbrida
Baseada nas sobras de processador na escala de carga periódica
Solução 1: Background Server (BS)
Este é o mais simples dos servidores
Processa tarefas aperiódicas quando não há tarefas periódicas pendentes - tempo livre do processador
Possui implementação bastante simples
Grande carga periódica resulta em um alto tempo de resposta para tarefas aperiódicas
Requer tarefas aperiódicas não críticas e baixa carga periódica
Solução 2: Polling Server (PS)
Cria-se uma tarefa periódica servidora para atender a carga aperiódica
Esta tarefa periódica tem período, prioridade e tempo de computação definidos
Em cada ativação, a tarefa servidora executa as tarefas aperiódicas pendentes durante seu tempo de computação (quantum)
Caso não haja tarefas aperiódicas para serem executas, esta tarefa servidora é suspensa até sua próxima ativação e o processamento volta para as tarefas periódicas
Se uma tarefa aperiódica é requisitada logo após a suspensão da tarefa servidora, a tarefa aperiódica deve esperar até a próxima ativação da tarefa servidora
A interferência da tarefa servidora no sistema é no pior caso igual a interferência causada por uma tarefa com o mesmo tempo de computação e período
Melhora o tempo de resposta médio de tarefas aperiódicas
Não possui serviço de resposta imediato
Solução 3: Deferrable Server (DS)
Supera as desvantagens do PS e BS
De forma similar ao PS, o algoritmo de DS cria uma tarefa periódica geralmente de alta prioridade para servidores de requisições aperiódicas
Diferentemente do PS, o DS presevar o tempo de execução das tarefas aperiódicas (conserva sua capacidade)
No início de cada período da tarefa servidora (DS), o tempo de execução é recuperado para sua capacidade completa
Tarefas Esporádicas
Garantia em tempo de projeto – Sistema de prioridade estático
Time-driven system (Executivos cíclicos)
O executivo cíclico simplesmente põe as tarefas em execução segundo o tempo e a ordem definidas em tempo de projeto.
É um escalonamento offline estático.
Tarefas são arranjadas numa lista que define a ordem e tempo de execução de cada uma.
A busca por esta ordem é, em geral, realizada por um algoritmo de busca em árvore.
São utilizadas heurísticas para limitar a busca, embora possa resultar na busca de todas as combinações possíveis (NP-completo).
Apenas tarefas periódicas podem ser escalonadas.
O ciclo completo é o Mínimo Múltiplo Comum dos períodos de todas as tarefas.
A lista é executada repetidamente, caracterizando ciclos de execução.
Event-driven systems
É feito um teste escalonabilidade em tempo de projeto, mas a escala propriamente dita é feita em tempo de execução.
A definição da escala obedece às prioridades das tarefas.
A ordem real de execução é regida por eventos (externos ou do timer) e pelas prioridades das tarefas.
Escalonamento Rate-Monotonic (RMS)
Escalonamento preemptivo de prioridade fixa.
Quanto menor o período maior a prioridade de uma tarefa.
Tarefas periódicas e independentes
Os deadlines coincidem com os períodos.
Tempo de mudança de contexto é considerado nulo.
É ótimo
É um escalonamento online estático.
Análise de escalonabilidade (Teste suficiente, mas não necessário)
Para uma Tarefa Ti, temos que: 
Pi: Período 
Mini: Intervalo Mínimo entre Requisições (tarefas esporádicas) 
Ci: Tempo de Computação 
Di: Deadline 
Ui = Utilização do Processador por uma tarefa Ti 
Ui = Ci/Pi, se Ti é periódica 
Ui = Ci/Mini, se Ti é esporádica 
U(n) = 1,0 se o conjunto de tarefas é harmônico
Um conjunto de tarefas é harmônico se os períodos de todas as tarefas são múltiplos ou submúltiplos entre si
•U(n) = 0,88 na média de tarefas randômicas
Escalonamento Earliest-Deadline First (EDF)
Escalonamento preemptivo de prioridade dinâmica.
Quanto mais próximo o deadline maior a prioridade
Tarefas periódicas e independentes
Os deadlines coincidem com os períodos (Di = Pi).
Tempo de mudança de contexto é considerado nulo.
É ótimo
Escalonamento online dinâmico.
Teste de escalonamento (suficiente e necessário)
Quando o sistema está com sobrecarga (overloaded) o conjunto de processos que perde seu deadline é altamente imprevisível: é uma função dos deadlines no momento em que ocorre a sobrecarga.
É muito difícil de implementar em hardware.
É difícil representar deadlines em poucos bytes para calcular deadlines relativos ao instante atual. Se for usada aritmética modular, as variáveis que armazenam os deadlines futuros devem acomodar um valor no mínimo do ((maior tempo esperado para o término} * 2) + “agora").
Escalonamento Deadline-Monotonic (DMS)
Semelhante ao RMS, mas os deadlines podem ser menores ou iguais aos períodos
Quanto menor o deadline da tarefa maior sua prioridade
Os deadlines são fixos e relativos aos começos dos períodos.
Escalonamento online estático.
Teste de escalonamento (exato)
Para uma Tarefa Ti, temos que:
Pi: Período
Ci: Tempo de Computação
Di: Deadline
Prii: Prioridade
Ri: Tempo de Resposta
Ii: Interferência
Calcula o tempo de resposta no pior caso e compara ao deadline
Se Ri < Di para todo Ti, o teste é válido
Para a tarefa T1, a mais prioritária: R1 = C1 
As demais sofrem interferência das que tem prioridade maior Neste caso, Ri = Ci + Ii 
Interferência é máxima a partir do Instante Crítico (Instante onde todas as tarefas são liberadas simultaneamente )
Interferência entre tarefas 
Seja Tj uma tarefa com prioridade maior que Ti 
Quantas vezes Tj pode acontecer durante a execução de Ti ? Ri/Tj 
Qual a interferência total de Tj sobre Ti ? Ri/Tj x Cj 
Qual a interferência total sobre Ti ? 
Ii = Σ Ri/Tj x Cj, onde Prij>Prii
O tempo máximo de resposta de Ti é Ri = Ci + Ii 
Ri = Ci + Σ Ri/Tj x Cj
O cálculo é feito recursivamente em iterações sucessivas, até: 
Tempo de resposta passar do deadline (falha) 
Resultado convergir, ou seja, iteração x+1 igual a iteração x 
Wix+1 = Ci + Σ Wix/Tj x Cj, onde Wi0= Ci
Atrasos na Liberação das Tarefas: Suponha uma tarefa liberada por evento externo
Eventos podem ser amostrados periodicamente
Sinalização do evento pode ter atraso variável
Release Jitter Ji: Atraso máximo na liberação da tarefa
A formula do tempo de resposta se torna:
Ri = Ji + Wi, onde Wi = Ci + ƒ° (Wi+Jj)/Tj x Cj
 
Tolerância à Falhas
Modelo dos Três universos
Físico (Falha) Informação (Erro) Usuário (Defeito) (FIU FED)
Tipos de falhas
Falhas físicas
Falhas humanas
Falhas de projeto (especificação)
Falhas de interação
Tipos de erro
Erro latente
Criado após ocorrência da falha
Erro efetivo
Ocorre quando da ativação do errolatente
Etapas na Detecção e Recuperação de Erros
Detecção de erro
Confinamento e avaliação do dano causado pela falha
Recuperação do erro
Tratamento da falha
Técnicas de Detecção de Erros
Replicação
Temporização
Coerência
Reversão (Isso na verdade é correção)
Diagnóstico
Redundância
De Hardware
Introdução componentes extras
Pode ser
Estática
Dinâmica
Híbrida
De Software
Introdução de elementos
De Informação
Duplicação de dados
Temporal
Re-execução de tarefas
Recuperação de Erros
Técnicas
Correção do erro
Troca de componente
Reconfiguração
Abordagens
Por avanço
Por retorno