Embed Size (px)
Citation preview
INPE-15723-TDI/1474
ANALISE DE UMA EXTENSAO DO AGENDADOR A
TAXAS MONOTONICAS NA PRESENCA DE TAREFAS
ESPORADICAS OU INCERTAS APLICADA A UM
COMPUTADOR DE CONTROLE DE MISSAO
Paulo Augusto Vieira
Dissertacao de Mestrado do Curso de Pos-Graduacao em Engenharia e Tecnologia
Espaciais/Mecancia Espacial e Controle, orientada pelos Drs. Marcelo Lopes de
Oliveira e Souza e Atair Rios Neto, aprovada em 8 de abril de 2009.
Registro do documento original:
<http://urlib.net/sid.inpe.br/mtc-m18@80/2009/01.20.17.45>
INPE
Sao Jose dos Campos
2009
Livros Grátis
http://www.livrosgratis.com.br
Milhares de livros grátis para download.
PUBLICADO POR:
Instituto Nacional de Pesquisas Espaciais - INPE
Gabinete do Diretor (GB)
Servico de Informacao e Documentacao (SID)
Caixa Postal 515 - CEP 12.245-970
Sao Jose dos Campos - SP - Brasil
Tel.:(012) 3945-6911/6923
Fax: (012) 3945-6919
E-mail: [email protected]
CONSELHO DE EDITORACAO:
Presidente:
Dr. Gerald Jean Francis Banon - Coordenacao Observacao da Terra (OBT)
Membros:
Dra Maria do Carmo de Andrade Nono - Conselho de Pos-Graduacao
Dr. Haroldo Fraga de Campos Velho - Centro de Tecnologias Especiais (CTE)
Dra Inez Staciarini Batista - Coordenacao Ciencias Espaciais e Atmosfericas (CEA)
Marciana Leite Ribeiro - Servico de Informacao e Documentacao (SID)
Dr. Ralf Gielow - Centro de Previsao de Tempo e Estudos Climaticos (CPT)
Dr. Wilson Yamaguti - Coordenacao Engenharia e Tecnologia Espacial (ETE)
BIBLIOTECA DIGITAL:
Dr. Gerald Jean Francis Banon - Coordenacao de Observacao da Terra (OBT)
Marciana Leite Ribeiro - Servico de Informacao e Documentacao (SID)
Jefferson Andrade Ancelmo - Servico de Informacao e Documentacao (SID)
Simone A. Del-Ducca Barbedo - Servico de Informacao e Documentacao (SID)
REVISAO E NORMALIZACAO DOCUMENTARIA:
Marciana Leite Ribeiro - Servico de Informacao e Documentacao (SID)
Marilucia Santos Melo Cid - Servico de Informacao e Documentacao (SID)
Yolanda Ribeiro da Silva Souza - Servico de Informacao e Documentacao (SID)
EDITORACAO ELETRONICA:
Viveca Sant´Ana Lemos - Servico de Informacao e Documentacao (SID)
INPE-15723-TDI/1474
ANALISE DE UMA EXTENSAO DO AGENDADOR A
TAXAS MONOTONICAS NA PRESENCA DE TAREFAS
ESPORADICAS OU INCERTAS APLICADA A UM
COMPUTADOR DE CONTROLE DE MISSAO
Paulo Augusto Vieira
Dissertacao de Mestrado do Curso de Pos-Graduacao em Engenharia e Tecnologia
Espaciais/Mecancia Espacial e Controle, orientada pelos Drs. Marcelo Lopes de
Oliveira e Souza e Atair Rios Neto, aprovada em 8 de abril de 2009.
Registro do documento original:
<http://urlib.net/sid.inpe.br/mtc-m18@80/2009/01.20.17.45>
INPE
Sao Jose dos Campos
2009
Dados Internacionais de Catalogacao na Publicacao (CIP)
Vieira, Paulo Augusto.
V673a Analise de uma extensao do agendador a taxas monotonicas napresenca de tarefas esporadicas ou incertas aplicada a um compu-tador de controle de missao / Paulo Augusto Vieira. – Sao Josedos Campos : INPE, 2009.
180p. ; (INPE-15723-TDI/1474)
Dissertacao (Mecanica Espacial e Controle) – Instituto Nacio-nal de Pesquisas Espaciais, Sao Jose dos Campos, 2009.
Orientadores : Drs. Marcelo Lopes de Oliveira e Souza e AtairRios Neto.
1. Agendamento em tempo real. 2. Escalonamento em temporeal. 3. Sistemas em tempo real 4. Tarefas esporadicas. 5. Agen-damento a taxas monotonicas. I.Tıtulo.
CDU 629.7.06:004.451.7.031.43
Copyright c© 2009 do MCT/INPE. Nenhuma parte desta publicacao pode ser reproduzida, arma-zenada em um sistema de recuperacao, ou transmitida sob qualquer forma ou por qualquer meio,eletronico, mecanico, fotografico, microfılmico, reprografico ou outros, sem a permissao escrita daEditora, com excecao de qualquer material fornecido especificamente no proposito de ser entradoe executado num sistema computacional, para o uso exclusivo do leitor da obra.
Copyright c© 2009 by MCT/INPE. No part of this publication may be reproduced, stored in aretrieval system, or transmitted in any form or by any means, eletronic, mechanical, photocopying,microfilming, recording or otherwise, without written permission from the Publisher, with theexception of any material supplied specifically for the purpose of being entered and executed on acomputer system, for exclusive use of the reader of the work.
“Os sete pecados capitais responsáveis pelas injustiças sociais são: riqueza
sem trabalho; prazeres sem escrúpulos; conhecimento sem sabedoria;
comércio sem moral; política sem idealismo; religião sem sacrifício e ciência
sem humanismo”.
Mahatma Gandhi
A meus avôs e avós
In memoriam
AGRADECIMENTOS
Aos Professores Drs. Atair Rios Neto e Marcelo Lopes de Oliveira e Souza pela oportunidade e privilégio concedidos ao me permitirem tê-los como mentores no transcorrer da jornada que culminou com este trabalho. Aos meus colegas de pós-graduação com os quais compartilhei momentos de sofrimento e de conquistas ao longo do curso. Ao Engenheiro Antônio Magno Lima Espeschit pelo trabalho abnegado de revisão. À Maria Cecília de Almeida Chaves pelo incentivo e compreensão. A meus pais, Emil Fernandes Vieira e Enriqueta Ambrósio Vieira, por todo o tempo e esforços investidos na minha criação. Às minhas sobrinhas Ana Clara Vieira da Fonseca e Ana Beatriz Vieira da Fonseca pelos momentos de distração, diversão e bagunça.
RESUMO
Este trabalho analisa uma extensão do Agendador / Escalonador a Taxas Monotônicas (Rate Monotonic Scheduler – RMS) na presença de tarefas esporádicas ou incertas e de seus efeitos sobre um Sistema de Controle em Tempo Real Rígido. Visto que os requisitos temporais dos Sistemas são mapeados em prazos limites de tarefas, é estudada a literatura computacional, espacial e aeronáutica afim, levantando-se as bases teóricas fundamentais pertinentes ao assunto em questão, a partir das quais se identificam os algoritmos de atendimento aperiódico: Serviço em Segundo Plano, Servidor de Varredura e Servidor Esporádico, aplicados no contexto de agendamento RMS, como sendo alguns dos métodos que permitem a garantia de atendimento dos prazos limites das tarefas periódicas. São analisados quais métodos e sob quais condições estes métodos fornecem garantias de atendimento aos prazos limites aperiódicos. Para isso, estes algoritmos são implementados, simulados e analisados mediante o uso do simulador HRTSim, uma ferramenta computacional desenvolvida com o propósito de simular o agendamento e a execução de tarefas periódicas e aperiódicas no âmbito de um Sistemas em Tempo Real Rígido. Um estudo de caso envolvendo o problema do agendamento de um conjunto de tarefas de um Computador de Missão (Mission Control Computer – MCC), integrante da aviônica de uma aeronave de combate típica, cujas especificações e resultado de agendamento são conhecidos, é utilizado tanto como referência para validação da ferramenta quanto fonte de resultados para a comparação quando sujeito aos diversos algoritmos de agendamento aperiódico abordados. Como resultados são levantados alguns dos cenários de aplicação de cada método em função da criticalidade dos prazos e dos tempos de resposta esperados das tarefas aperiódicas bem como da complexidade de implementação. É observado também que um melhor aproveitamento da capacidade de processamento da CPU pode ser obtido, mediante uso da atribuição de prioridades de acordo com a política RMS, porém, com Teste de Agendabilidade baseado nos tempos de resposta ao invés do teste RMS original baseado em utilização, quando do uso do algoritmo Servidor Esporádico para atendimento a tarefa esporádica.
ANALYSIS OF AN EXTENDED RATE MONOTONIC SCHEDULER WITH SPORADIC OR UNCERTAIN TASKS AND ITS INFLUENCE ON A CONTROL
SYSTEM
ABSTRACT
This work proposes the analysis of an extended Rate Monotonic Scheduler – RMS with sporadic or uncertain tasks and its influence on a Hard Real Time Control System. Given that Systems time requirements are mapped into tasks deadlines, related computing and aerospace bibliography are reviewed, providing fundamental theoretical basis related to the subject, from which aperiodic servicing algorithms Background Servicing, Polling Server and Sporadic Server are identified as methods capable of guaranteeing periodic tasks deadlines when applied under RMS scheduling context. An analysis is undertaken to verify what methods and under which conditions these methods also provide aperiodic deadlines guarantees. To achieve this goal, the algorithms are implemented, simulated and analyzed by means of the HRTSim, a computer tool develop to simulate the scheduling and dispatching of periodic and aperiodic tasks under Hard Real Time constraints. A case study related to the tasks scheduling problem for a Mission Control Computer – MCC of a typical fighter aircraft avionics with known specifications and scheduling results, is used either as reference for the validation of the tool as source of data for comparison when submitted to the various aperiodic scheduling algorithms considered. As results, a number of application scenarios for the methods are found, as a function of deadlines criticality and expected response times of aperiodic tasks and the implementation complexity. It’s observed that a better CPU processing capacity utilization is achieved while applying the RMS priority attribution scheme in conjunction with the response time based schedulability test, instead of the original RMS utilization based test, when using Sporadic Server algorithm for sporadic task servicing.
SUMÁRIO
Pág.
LISTA DE FIGURAS LISTA DE TABELAS LISTA DE SIGLAS E ABREVIATURAS LISTA DE SÍMBOLOS
1 INTRODUÇÃO 27
1.1 Objetivo 29
1.2 Organização 30
2 REVISÃO DA LITERATURA E CONCEITOS BÁSICOS 33
2.1 Trabalhos Relacionados 33
2.2 Controle Digital e Sistemas em Tempo Real 36
2.3 Sistemas em Tempo Real 39
2.4 Programas Aplicativos e Tarefas 42
2.4.1 Tarefa Periódica 43
2.4.2 Tarefa Aperiódica 43
2.4.3 Tarefa Esporádica 44
2.5 Caracterização de uma Tarefa 45
2.5.1 Execução Preemptiva e Não Preemptiva 47
2.5.2 Despachador (Dispatcher) 48
2.5.3 Agendador (Scheduler) ou Escalonador 49
2.6 Agendador a Taxas Monotônicas (Rate Monotonic Scheduler – RMS)51
2.7 Teste de Exeqüibilidade (Feasibility) ou Agendabilidade 56
2.8 Análise de Tempos de Resposta (Response Time Analysis – RTA) 58
2.9 Agendamento de Tarefas Aperiódicas / Esporádicas 60
2.9.1 Serviço em Segundo Plano (Background Servicing – BS) 62
2.9.2 Servidor Periódico (Periodic Server) 65
2.9.3 Servidor de Varredura (Polling Server – PS) 67
2.9.4 Servidor Adiável (Deferrable Server – DS) 73
2.9.5 Servidor de Troca de Prioridades (Priority Exchange – PE) 77
2.9.6 Servidor Esporádico (Sporadic Server – SS) 83
3 DESENVOLVIMENTO 91
3.1 HRTSim – Simulador em Tempo Real Rígido 91
3.1.1 Introdução 91
3.2 Estudo de Caso: Computador de Missão 93
3.3 Verificação do HRTSim Contra o Estudo de Caso do MCC 95
3.4 Algoritmo com Serviço em Segundo Plano Aplicado ao MCC 98
3.5 Algoritmo Servidor de Varredura Aplicado ao MCC 98
3.6 Algoritmo Servidor Esporádico Aplicado ao Estudo de Caso do MCC 99
4 SIMULAÇÕES E RESULTADOS 101
4.1 MCC Com Especificações Originais – Todas as Tarefas Periódicas,
Conjunto Não Agendável 101
4.2 MCC Com Especificações Modificadas – Todas as Tarefas Periódicas,
Conjunto Agendável 106
4.3 MCC Com Especificações Modificadas – Serviço em Segundo Plano,
Conjunto Periódico Agendável, Sem Garantias Aperiódicas 110
4.4 MCC Com Especificações Modificadas – Servidor de Varredura,
Conjunto Periódico Agendável, Sem Garantias Aperiódicas 113
4.5 MCC Com Especificações Modificadas – Servidor de Varredura,
Conjunto Agendável 118
4.6 MCC Com Especificações Modificadas – Servidor Esporádico,
Conjunto Agendável 122
5 ANÁLISE E CONCLUSÕES 127
6 DIREÇÕES PARA ESTUDOS FUTUROS 133
REFERÊNCIAS BIBLIOGRÁFICAS 137
APÊNDICE A – COMPLEMENTO TEÓRICO 141
A.1 Sistemas em Tempo Real – Classificação, Detalhes e Exemplos 141
A.2 Sistemas em Tempo Real – Marcos Históricos 153
A.3 Agendador Cíclico Executivo (Cyclic Executive Scheduler – CES) 155
A.4 Agendador RMS – Exemplos 159
APÊNDICE B – DIAGRAMAS DE CLASSES DO HRTSim 165
B.1 Diagrama de Classes Geral 165
B.2 Diagrama de Classes da Tarefa 166
B.3 Diagrama de Classes do Agendador 167
B.4 Diagrama de Classes do Despachador 168
B.5 Diagrama de Classes de Elementos Variados 169
APÊNDICE C – Manual de Instalação e de Operação do HRTSim 171
ÌNDICE POR ASSUNTO 178
LISTA DE FIGURAS
2.1 – Diagrama de blocos de um Sistema de Controle digital clássico. ........... 38
2.2 – Sistema computadorizado tradicional. ..................................................... 39
2.3 – Classificação das tarefas quanto à periodicidade. .................................. 44
2.4 – Caracterização temporal de uma tarefa. ................................................. 47
2.5 – Serviço em Segundo Plano. .................................................................... 63
2.6 – Linha de Tempo com Serviço em Segundo Plano. ................................. 64
2.7 – Servidor Periódico. .................................................................................. 66
2.8 – Linha de Tempo com Servidor de Varredura. .......................................... 70
2.9 – Linha de Tempo com Servidor Adiável. ................................................... 77
2.10 – Linha de Tempo com Servidor de Troca de Prioridades. ...................... 81
2.11 – Linha de Tempo com Servidor Esporádico. ........................................... 88
4.1 – Linha de Tempo do MCC com todas as tarefas periódicas, não agendável. ................................................................................. 104
4.2 – Linha de Tempo de referência do MCC (Rate–monotonic scheduling of the generic avionics mission system tasks). .............................. 105
4.3 – Linha de Tempo do MCC com todas as tarefas periódicas, agendável. 109
4.4 – Linha de Tempo do MCC com conjunto periódico agendável, Serviço em Segundo Plano, sem garantias aperiódicas. ............................. 112
4.5 – Linha de Tempo do MCC com conjunto periódico agendável, Servidor de Varredura, sem garantias aperiódicas....................................... 116
4.6 – Capacidade dos Servidores do MCC com conjunto periódico agendável, Servidor de Varredura, sem garantias aperiódicas. .................. 117
4.7 – Linha de Tempo MCC com conjunto de tarefas agendável, Servidor de Varredura. ................................................................................. 120
4.8 – Capacidade dos Servidores do MCC com conjunto de tarefas agendável, Servidor de Varredura. .............................................................. 121
4.9 – Linha de Tempo do MCC com conjunto de tarefas agendável, Servidor Esporádico. ............................................................................... 124
4.10 – Capacidade dos Servidores do MCC com conjunto de tarefas agendável, Servidor Esporádico. ................................................................. 125
A.1 – Componentes de um Sistema em Tempo Real. ................................... 141
A.2 – Função tempo–utilidade de uma tarefa com prazo flexível. .................. 146
A.3 – Função tempo–utilidade de uma tarefa com prazo firme. ..................... 147
A.4 – Função tempo–utilidade de uma tarefa com prazo rígido com dano progressivo. ............................................................................... 149
A.5 – Função tempo–utilidade de uma tarefa com prazo rígido com dano
instantâneo e catastrófico (utilidade tendendo a – ). ............... 150
A.6 – Composição do Sistema Operacional. .................................................. 151
A.7 – Agendador e depachante em Tempo Real. .......................................... 152
A.8 – Linha de tempo do Agendador Cíclico Executivo. ................................. 157
A.9 – Linha de Tempo com conjunto de tarefas RMS 1. ................................ 160
A.10 – Linha de Tempo com conjunto de tarefas RMS 2. .............................. 162
A.11 – Linha de Tempo com conjunto de tarefas RMS 3. .............................. 164
C.1 – Elemento da Linha de Tempo. .............................................................. 171
C.2 – Estados de uma tarefa. ......................................................................... 173
C.3 – Legenda dos gráficos de Linha de Tempo do HRTSim. ....................... 176
LISTA DE TABELAS
2.1 – Limites de utilização do processador....................................................... 57
2.2 – Exemplo de conjunto de tarefas com Serviço em Segundo Plano. ......... 63
2.3 – Exemplo de conjunto de tarefas com Servidor de Varredura. ................. 69
2.4 – Exemplo de conjunto de tarefas com Servidor Adiável. .......................... 76
2.5 – Exemplo de conjunto de tarefas com Servidor Esporádico. .................... 87
3.1 – Exemplo de um conjunto de tarefas típicas de um MCC. ........................ 94
3.2 – Conjunto de tarefas MCC com especificações modificadas. ................... 97
3.3 – Instantes dos eventos. ............................................................................. 98
3.4 – Instantes dos eventos: Servidor de Varredura (agendável). .................... 99
A.1 – Exemplo de conjunto de tarefas: CES. ................................................. 156
A.2 – Exemplo de conjunto de tarefas: RMS 1. .............................................. 159
A.3 – Exemplo de conjunto de tarefas: RMS 2. .............................................. 162
A.4 – Exemplo de conjunto de tarefas: RMS 3. .............................................. 163
LISTA DE SIGLAS E ABREVIATURAS
ABS Antilock Breaking System
AUTO Automatic Delivery Mode
BIT Built–In–Test
BS Background Servicing
CCIP Continuously–Computed Impact Point
CES Cyclic Executive Scheduler
COTS Commercial–Off–The–Shelf
CPU Central Processing Unit
DEC Digital Equipment Corporation
DM Deadline Monotonic
DMS Deadline Monotonic Scheduling
DS Deferrable Server
DVD Digital Video Disk / Digital Versatile Disc
EDF Earliest Deadline First
Embraer Empresa Brasileira de Aeronáutica
ESA European Space Agency
EV Extreme Value
FCFS First Come First Served
FDP Função Densidade de Probabilidade
FORTRAN FORmula TRANslationg
HP Hewlett Packard
HOTAS Hands–On Throttle And Stick
HUD Head–Up Display
IBM International Business Machines
IEEE Institute of Electrical and Electronics Engineers
INPE Instituto Nacional de Pesquisas Espaciais
Intel Integrated Electronics
I/O Input / Output
LUB Least Upper Bound
MCC Mission Control Computer
MIT Massachusetts Institute of Technology
MPD Multi–Purpose Display
MPEG Moving Pictures Experts Group
MROS Memory Resident Operating System
NASA National Aeronautics and Space Administration
OS Operating System
PE Priority Exchange Server
PS Polling Server
POSIX Portable Operating System Interface
RM Rate Monotonic
RMA Rate Monotonic Analysis / Rate Monotonic Assignment
RMS Rate Monotonic Scheduler / Rate Monotonic Scheduling
RMX Real Time Multitasking Executive
RSX Real Time System Executive
RTA Response Time Analysis
RTOS Real Time Operational System
RTS Real Time System
RWR Radar Warning Receiver
SABRE Semi Automated Business Research Environment
SAGE Semi Automatic Ground Environment
SEI Software Engineering Institute
SS Sporadic Server
STR Sistema em Tempo Real
TS Timeline Scheduling, Timeline Scheduler
VRTX Versatile Real Time Executive
LISTA DE SÍMBOLOS
aa Instante de chegada (arrival time) ou liberação (release time) da
tarefa aperiódica
ai Instante de chegada ou liberação da tarefa i
p1, . . ., pk Pólos de malha aberta
Ca Tempo de computação da tarefa aperiódica
Ci Tempo de computação da tarefa i
Cs Tempo de computação do servidor, capacidade do servidor
Da Prazo limite relativo (deadline) da tarefa aperiódica
da Prazo limite absoluto da tarefa aperiódica
Di Prazo limite relativo da tarefa i
di Prazo limite absoluto da tarefa i
hp(i) Conjunto de tarefas com prioridade superior à tarefa i
i Índice das tarefas periódicas
j Índice dos servidores periódicos
M Quantidade de servidores periódicos no sistema
MIT Tempo mínimo entre liberações (Minimum Interarrival Time)
N Quantidade de tarefas periódicas no sistema
Pi Prioridade da tarefa i
Ps Prioridade corrente de execução do sistema
R Taxa de dados
Ri Tempo de resposta de pior caso da tarefa i
RTS Tempo de restauração ou preenchimento (Replenishment Time) da
tarefa servidora
Ti Período da tarefa i
TS Período do servidor
tei Instante de ocorrência de evento relativo à tarefa i
U Utilização, fator de utilização ou carga total do processador
ULUB(N) Limite superior de utilização para N tarefas
Ui Utilização, fator de utilização ou carga da tarefa i
Up Utilização, fator de utilização ou carga das tarefas periódicas
Us Utilização, tamanho, fator de utilização ou carga do servidor
WCET Tempo de execução de pior caso (Worst Case Execution Time)
λ(A) Autovalores da matriz de sistema A
τi i–ésima tarefa
τs tarefa servidora
27
1 INTRODUÇÃO
Sistemas em Tempo Real estão presentes em diversas áreas técnicas
destacando–se, entre outras, a aeroespacial. Incluem aspectos de Engenharia
de Controle e Ciência da Computação (ÅRZÉN et al., 1999), apresentando
grandes desafios uma vez que é extremamente complexo lidar com as
restrições temporais impostas pela natureza dessa classe de sistemas. Tais
restrições resultam em diversos compromissos entre fatores como custo,
desempenho, segurança e outros, limitados sempre pelo estado da arte da
tecnologia e do conhecimento correntes.
Atualmente, quase todos os controladores são construídos de forma digital
mediante o uso de computadores, em que uma implementação efetiva em
termos de alto desempenho com o menor custo requer alto nível de
conhecimento tanto de Teoria de Controle como de Sistemas em Tempo Real.
O problema dos Sistemas em Tempo Real é o da adequada alocação de
recursos, principalmente capacidade de processamento, de forma que as
restrições temporais sejam cumpridas eficaz e eficientemente. O componente
responsável por esta função é o escalonador ou agendador (scheduler), que
possui como objetivo básico seqüenciar as tarefas de acordo com um algoritmo
de agendamento que equacione o problema.
O universo da computação em Tempo Real demanda cada vez mais
flexibilidade à medida que avança para aplicações mais realistas, se
distanciando dos métodos de agendamento mais restritivos como o Agendador
a Executivo Cíclico (Cyclic Executive Scheduler – CES) (BURNS e WELLINGS,
1996) e o Agendador a Taxas Monotônicas (Rate Monotonic Scheduler – RMS)
tradicional (LIU e LAYLAND, 1973).
Basicamente um Sistema de Processamento em Tempo Real Rígido é uma
solução computacional para um problema, seja este de controle, monitoração
28
ou gerenciamento, na qual o programa (software) que desempenha as ações
necessárias é tradicionalmente dividido em um conjunto de tarefas periódicas,
cada qual incumbida de uma ou mais atividades, que constituem unidades de
execução individual, com requisitos temporais críticos próprios, executadas em
computador (hardware) uni ou multiprocessado, geralmente dedicado ao fim.
Os métodos de agendamento mais tradicionais e utilizados em aplicações
críticas (CES e RMS), que determinam o seqüenciamento da execução das
tarefas de maneira a garantir o atendimento dos requisitos temporais
(principalmente cumprimento dos prazos limites), foram idealizados levando–se
em conta a periodicidade de todas as tarefas. Originalmente não foi
contemplada a situação na qual uma ou mais tarefas pudessem ser
aperiódicas, o que torna difícil ou mesmo impraticável a incorporação destas
aos modelos originais existentes, principalmente em se tratando das tarefas
aperiódicas com prazos rígidos (esporádicas), haja vista o alto grau de
determinismo imposto pelo modelo do CES (APÊNDICE A.3) e as restrições
devido às hipóteses que servem de base às garantias analíticas do RMS,
ambos antagônicos com a natureza não determinística das tarefas aperiódicas.
Entretanto, devido tanto ao aumento da capacidade de processamento dos
computadores atuais, como à crescente complexidade dos sistemas e o
conseqüente aumento na quantidade de atividades sob responsabilidade
desses, surge a necessidade de atendimento a eventos assíncronos para
suportar as tarefas aperiódicas com prazos flexíveis e ou rígidos.
Do ponto de vista de controle digital de processos, tanto as medidas como os
sinais de controle são discretizados, mediante amostragens periódicas com
taxas constantes, que são processados por tarefas periódicas, geralmente com
prazos rígidos. Taxas e prazos estes, sem prejuízo de demais parâmetros,
determinados basicamente pelos requisitos de desempenho do controle,
oriundos da análise do modelo do processo, e que devem ser obrigatoriamente
cumpridos.
29
1.1 Objetivo
O objetivo do trabalho é o de apresentar, analisar e testar, por meio de
simulações, técnicas viáveis e aplicáveis que permitam a execução mista de
tarefas, isto é, a execução concomitante de tarefas periódicas e esporádicas
(ambas com prazos limites rígidos) por um computador uniprocessado
mediante o Agendamento a Taxas Monotônicas.
Para viabilizar tal objetivo, foi desenvolvido um programa Simulador de Tempo
Real Rígido (HRTSim) para prover os meios de estudo e análise necessários,
dada a escassez, no mercado, de ferramentas adequadas para este propósito
específico.
O trabalho busca com estas técnicas a flexibilização de algumas das restrições
intrínsecas impostas pelo método RMS tradicional (LIU e LAYLAND, 1973), por
meio de uma abordagem menos determinística que as tradicionais, que permite
a inclusão de algoritmos específicos ao tratamento de tarefas aperiódicas
(SPRUNT et al., 1989). Portanto o problema consiste em agendar e despachar
tal conjunto misto de tarefas de forma que todas as tarefas periódicas e
esporádicas cumpram seus prazos limites, ao mesmo tempo em que as tarefas
esporádicas apresentem o menor tempo de resposta possível. Em se tratando
de controle digital de processo, dado que as principais atividades de controle
(medida, cálculo e atuação) são desempenhadas por tarefas periódicas,
resolvendo–se tal problema garante–se a desejada não influência das tarefas
esporádicas no desempenho da malha de controle. No caso de sistemas
supervisores e gerenciadores (e.g. computadores de missão, navegação, de
bordo, etc.) garantem–se os requisitos temporais originados das especificações
do veículo seja nas ações recorrentes (periódicas) como monitoração,
apresentação de informações, cálculos, etc., seja na resposta a eventos
incertos (assíncronos ou aperiódicos) como falhas, alarmes, comandos
manuais, mudanças de modo de operação, etc.
30
1.2 Organização
Uma vez expostos os objetivos na parte introdutória (Capítulo 1), alguns dos
trabalhos relevantes na área são comentados no Capítulo 2, servindo de
subsídio ao presente estudo além de fonte para substanciar a conceituação
básica necessária à construção do alicerce teórico e ao norteamento dos
passos seguintes. Desta forma é delineado o contexto básico no qual a
computação em Tempo Real e a teoria de Controle Digital de Sistemas formam
uma amálgama que advém das necessidades técnicas impostas pelos
problemas encontrados em diversas áreas do conhecimento (no presente caso
especificamente a área aeroespacial) que fazem uso de computadores para
gerenciamento, supervisão ou controle de processo, principalmente em
aplicações críticas na qual uma falha ou operação fora das especificações
estabelecidas pelos requisitos de projeto resultam em prejuízo material,
ambiental ou mesmo humano. É então demonstrado que os requisitos
temporais, em termos de taxas de amostragem e atrasos relativos ao Sistema
de Controle, implicam em requisitos de Tempo Real do sistema computacional
e a conseqüente abordagem multidisciplinar. Uma vez conceituada a
Computação em Tempo Real, seus elementos, suas definições fundamentais e
sua estrutura na, qual o processamento é dividido em unidades de
processamento denominadas tarefas, é apresentada a teoria que trata do
problema fundamental da Computação em Tempo Real: a alocação de
recursos ao processamento das tarefas, que se traduz nas técnicas de
agendamento, mais especificamente a já consagrada teoria de Agendamento a
Taxas Monotônicas (RMS) que tanto estabelece a ordem como a confirmação
da possibilidade do seqüenciamento das tarefas periódicas previstas a priori
por meio de um Teste de Agendabilidade. A possibilidade de execução de
todas as tarefas do conjunto atendendo aos seus requisitos temporais (prazos
limites) é determinada, dentro desta teoria, por uma condição suficiente porém
não necessária, baseada na utilização do processador resultando, em geral,
em baixo aproveitamento de recursos de computação. Desta forma é
31
apresentado outro teste, baseado nos tempos de resposta, que se traduz em
uma condição suficiente e necessária, permitindo máximo aproveitamento do
processador. Como esta teoria é, na sua origem, limitada a tarefas periódicas,
são apresentados alguns dos métodos que fazem uso do Agendamento a
Taxas Monotônicas no trato misto de tarefas, onde tarefas aperiódicas,
geralmente em resposta a eventos assíncronos, executam em meio às
periódicas, dentre os quais, Serviço em Segundo Plano, Servidor de Varredura,
Servidor Adiável, Servidor de Troca de Prioridades e Servidor Esporádico. São
analisadas as características e condições de aplicação dessas técnicas por
meios analíticos e o funcionamento por meio de exemplos. Detalhes mais
aprofundados sobre alguns dos conceitos teóricos podem sem encontrados no
APÊNDICE A (classificação, componentes e exemplos de Sistemas em Tempo
Real, agendador CES e exemplos de agendamento RMS). No Capítulo 3,
encontra–se o desenvolvimento do trabalho, durante o qual foi identificada a
necessidade de uma ferramenta adequada de simulação do ambiente de
execução de um típico Sistema em Tempo Real que permitisse tanto a prova
dos conceitos relativos ao tema deste estudo, bem como a observação do
funcionamento dos diversos algoritmos e o levantamento de dados para efeito
de avaliação de desempenho e análise de resultados. Neste capítulo é feita
uma introdução à ferramenta de software HRTSim, cujo detalhamento, teoria
de operação, características de projeto e implementação encontram–se no
APÊNDICE C . Os modelos, na forma de diagramas de objetos, encontram–se
descritos no APÊNDICE B . Um estudo de caso baseado nas especificações
realistas de um Computador de Missão hipotético de uma aeronave de
combate típica é utilizado tanto na validação do HRTSim como base para as
simulações dos diversos modelos de agendamento misto, ou seja, envolvendo
tarefas periódicas juntamente com tarefas aperiódicas ou esporádicas,
conforme o caso. No Capítulo 4 encontram–se os resultados das simulações,
representados tanto pelas análises textuais como pelas saídas gráficas do
HRTSim, que ilustram tanto as linhas de tempo como as capacidades dos
servidores periódicos quando for o caso. O Capítulo 5 contém observações,
32
comentários e as conclusões do trabalho, complementado por sugestões de
estudos futuros no Capítulo 6.
33
2 REVISÃO DA LITERATURA E CONCEITOS BÁSICOS
2.1 Trabalhos Relacionados
O trabalho de Liu e Layland (1973) é considerado o precursor da teoria de
agendamento preemptivo em Tempo Real baseado em prioridades e o de
maior influência nos trabalhos posteriores a respeito do assunto. Os autores
apresentam a análise e formalização matemática de dois critérios de
agendamento e de um teste de exeqüibilidade (agendabilidade) para um
conjunto de tarefas periódicas independentes com tempo de computação
conhecidos cujos prazos limites são iguais aos respectivos períodos. Tal
análise leva em conta uma série de fatores, incluindo as restrições impostas
pelo modelo computacional adotado. O primeiro critério de agendamento atribui
prioridades estáticas às tarefas de acordo com os respectivos períodos (quanto
menor o período maior a prioridade), denominado Agendamento a Taxas
Monotônicas (Rate Monotonic Scheduling – RMS). Também é apresentado um
critério de atribuição dinâmica de prioridades no qual as prioridades são
atribuídas de acordo com a proximidade dos vencimentos dos prazos limites
atuais e que permite a utilização total da capacidade de processamento. Tal
critério é denominado Próximo Prazo Primeiro (Earliest Deadline First – EDF).
Burns e Wellings (1997) abordam uma vasta gama de assuntos relativos aos
Sistemas em Tempo Real e linguagens de programação voltadas ao tema,
desde os conceitos básicos e definições até os recursos de suporte à
programação disponíveis em algumas linguagens de desenvolvimento de
programas para sistemas em Tempo Real, como Ada e Occam2. Um dos
capítulos aborda a questão do agendamento mediante a introdução ao
Agendador a Executivo Cíclico (Cyclic Executive Scheduler – CES). Além do
desenvolvimento do esquema de Atribuição de Prioridades a Taxas
Monotônicas e do respectivo Teste de Agendabilidade suficiente, porém não
necessário, baseado na utilização do processador, Liu & Layland (1973)
34
apresentam um Teste de Agendabilidade suficiente e necessário baseado na
Análise de Tempo de Resposta (Response Time Analysis – RTA) das tarefas,
que garante a exeqüibilidade mesmo mediante a utilização do processador
acima do limite estabelecido pelo teste RMS. Algumas das premissas originais
do RMS são flexibilizadas e alternativas são propostas no trato de questões
não abordadas na teoria RMS original como: prazos limites inferiores aos
períodos, bloqueio de recursos compartilhados (blocking), atraso de liberação
de tarefas (release jitter), etc.
Farines et al. (2000), em livro texto nacional, trata dos principais aspectos
relacionados aos Sistemas em Tempo Real por meio de duas abordagens
distintas, uma dita assíncrona, que leva em conta as características do
hardware e do software básico (e.g. Sistema Operacional, kernel, linguagem,
etc.) e sua influência temporal no projeto, sendo, portanto, mais adequada à
implementação do sistema e outra abordagem dita síncrona, em um nível mais
alto, que abstrai características do hardware e do software básico, deixando de
tratar tempo de forma explícita. Esta segunda abordagem é adequada à
modelagem de alto nível (especificação, análise e validação do sistema).
Sprunt et al. (1989) e Sprunt (1990) propõem o algoritmo do Servidor
Esporádico (Sporadic Server – SS) para o agendamento de tarefas aperiódicas
e esporádicas em um contexto misto (tarefas periódicas com prazos rígidos,
simultaneamente com tarefas aperiódicas ou esporádicas), com execução
preemptiva de tarefas agendadas por meio de algoritmos de atribuição estática
de prioridades. Este trabalho mostra que o SS permite o agendamento de
tarefas aperiódicas (prazos flexíveis) com bons tempos de resposta e relativa
baixa complexidade de implementação utilizando a atribuição a Taxas
Monotônicas (Rate Monotonic – RM) de prioridades, além de permitir o
agendamento de tarefas esporádicas (prazos rígidos), utilizando a atribuição
RM, no caso de tarefas com prazos limites superiores ou iguais ao intervalo de
tempo mínimo entre liberações, ou a atribuição a Prazos Monotônicos
(Deadline Monotonic – DM), no caso de tarefas com prazos limites inferiores.
35
São feitas as análises de desempenho e de agendabilidade do algoritmo
proposto além da comparação com alguns dos demais algoritmos conhecidos
utilizados para o mesmo fim.
Stankovic (1988) apresenta uma definição para Sistemas em Tempo Real que
é a mais adotada pelos profissionais da área, além de analisar os principais
falsos juízos sobre a computação em Tempo Real, por meio de um processo
de ponto e contraponto, no qual os conceitos erroneamente interpretados são
apresentados e são a seguir desmistificados, conceitos estes na sua maioria
oriundos da computação tradicional e incautamente utilizados no contexto da
computação em Tempo Real. São também discutidas questões técnicas
fundamentais, como: especificação, verificação, teoria de agendamento,
sistemas operacionais, linguagens de programação e metodologia de projeto.
Årzén et al. (1999) e Cervin (2000, 2003) introduzem uma abordagem integrada
no desenvolvimento de Sistemas de Controle, na qual tanto os aspectos
relativos à Teoria de Controle como os aspectos relativos à Ciência da
Computação não são tratados separadamente, mas sim em conjunto, de
maneira que se obtenha o melhor desempenho de controle possível com o
mínimo de recursos computacionais. Em outras palavras, os autores definem,
informalmente, o problema de codesign de controle e agendamento:
Dado um conjunto de processos a serem controlados e um
computador com recursos computacioanais limitados, projetar um
conjunto de controladores e agendá–los como tarefas em Tempo
Real de forma que o desemplenho conjunto seja otimizado (CERVIN,
2003, pp. 12–13).
A partir deste tema são apresentados estudos do estado da arte na área de
controle integrado com agendamento, nos quais são abordadas questões como
malhas de controle periódicas, dos pontos de vista de controle e de
computação, agendamento flexível e adaptativo, agendamento de subtarefas,
ferramentas de simulação, e outras.
36
2.2 Controle Digital e Sistemas em Tempo Real
Desde seu nascimento em 1932 com a publicação do trabalho Regeneration
Theory (NYQUIST, 1932), a Teoria de Controle Realimentado Moderno criou,
entre as décadas de 1930 e 1950, sólidas bases teóricas que puderam ser
aplicadas, com o auxílio dos trabalhos de Bode, Nichols e Evans, a
praticamente qualquer sistema realimentado. Porém a partir da década de
1950 ocorreu um crescente interesse no uso dos computadores digitais como
instrumentação dos Sistemas de Controle realimentados, passando dos
modelos de tempo e estados contínuos para os modelos de tempo e estados
discretizados. Conseqüentemente, novas questões vitais passaram a ter que
ser levadas em consideração no estudo e projeto dos sistemas: taxas de
amostragem (DELCHAMPS, 1990), quantização dos sinais (efeitos do
comprimento limitado das palavras digitais) e compensação devido aos atrasos
(fase) impostos pelos dispositivos digitais.
Ao contrário dos sistemas de computação, ou mesmo de comunicação, onde a
precisão e exatidão das informações (dados e sinais) geralmente são os
fatores de maior interesse, nos Sistemas de Controle as características
temporais, notoriamente os atrasos, geralmente são os fatores mais críticos,
mesmo porque os Sistemas de Controle realimentados tendem a ser bastante
robustos com relação às imprecisões nos valores das informações. O mesmo
não se pode dizer com relação ao atraso (latência) na malha de controle, que
pode inclusive levar todo o sistema a uma condição de instabilidade. Outra
característica temporal de grande influência na estabilidade de um Sistema de
Controle realimentado é a taxa de amostragem das medidas e atuações, pois
se um sistema é instável em malha aberta, então existe uma mínima taxa de
amostragem na qual a informação de realimentação deve ser processada e
utilizada no controle em malha fechada de maneira a estabilizar o sistema. Isso
se deve ao teorema da taxa de dados (data–rate theorem) que estabelece que:
37
para qualquer sistema linear invariante no tempo com pólos de malha
aberta p1, . . ., pk no semiplano direito, uma lei de controle pode ser
estabelecida de maneira a produzir resposta limitada se e somente se
a taxa de informação R ao longo da malha fechada de controle
satisfaz a desigualdade:
(2.1)
Portanto, quanto maior a magnitude dos pólos instáveis, maior a taxa
de amostragem requerida ao longo da malha realimentada. Esse
resultado intuitivamente atrativo [...] quantifica uma relação
fundamental entre sistemas fisicamente instáveis e a taxa na qual a
informação necessita ser processada a fim de estavelmente controlá-
los. É também notável que o teorema envolva apenas a taxa na qual
a informação deva ser processada e comunicada ao longo na malha
de controle (BAILLILEUL e ANTSAKLIS, 2007).
Na Desigualdade 2.1 acima, R corresponde à taxa de informação em bits por
unidade de tempo discretizado e corresponde à parte real do pólo de
malha aberta pi no semiplano direito. Na realidade é uma particularização do
teorema mais geral (TATIKONDA e MITTER, 2004):
(2.2)
onde representa os autovalores da matriz de sistema .
Ou seja, existe um valor mínimo da taxa de amostragem abaixo do qual não há
como garantir a estabilidade de um Sistema de Controle retroalimentado
(DELCHAMPS, 1990, BAILLIEUL et al., 1980).
Entretanto, a Ciência da Computação não costuma ver o tempo como uma
questão central, uma vez que a grande maioria dos sistemas computacionais
convencionais normalmente interage com outros sistemas computacionais ou
38
com operadores humanos e não diretamente com o mundo físico. Apenas
recentemente, áreas como a de Sistemas em Tempo Real começaram a
estudar as questões relativas às restrições temporais que dão origens a
requisitos rígidos de tempo, que estabelecem limites de tempo específicos
dentro dos quais os sistemas computacionais têm que reagir, o que é essencial
aos sistemas que lidam diretamente com o mundo físico (BAILLILEUL e
ANTSAKLIS, 2007).
Com a existência de um computador na malha de controle (Figura 2.1), a
conexão entre a Ciência da Computação e a Teoria de Controle se faz ainda
mais clara e cristalina, na medida que a latência (atraso) é limitada pelo tempo
de resposta das atividades (tarefas) executadas, que por sua vez são limitadas
por seus respectivos prazos limites (deadlines) (CERVIN, 2000) prazos estes
que se configuram na principal restrição temporal a ser considerada nos
estudos dos Sistemas em Tempo Real, cunhando a principal característica
determinante no projeto e operação de tal classe de sistemas: a previsibilidade
(predictability).
O termo Tempo Real aplicado à computação deriva do seu uso nos primórdios
da Simulação para definir uma simulação que transcorre na mesma cadência
temporal do processo real sendo simulado. Curiosamente, embora
VARIÁVEL CONTROLADA
DIGITAL ANALÓGICO
MEDIDA
PLANTA + ATUADOR + AMBIENTE
CONTROLADOR (COMPUTADOR)
SENSOR / TRANSDUTOR
+ –
ERRO
A/D
D/A
CONTROLE
REFER.
Figura 2.1 – Diagrama de blocos de um Sistema de Controle digital clássico.
39
corretamente definido na sua origem, com o passar do tempo passou a ser
erroneamente utilizado como sendo sinônimo de computação de alto
desempenho ou em alta velocidade. A conceituação correta do termo Tempo
Real foi recentemente restabelecida após a publicação de alguns trabalhos
(STANKOVIC, 1988) e a aceitação por parte da comunidade científica de um
consenso a respeito de qual seria a definição mais adequada.
Ao longo da história, vários fatos são considerados como marcos importantes
para o surgimento e o desenvolvimento dos Sistemas em Tempo Real
(LAPLANTE, 2004). Alguns destes se encontram listados no APÊNDICE A.1.
2.3 Sistemas em Tempo Real
Os computadores surgiram e se difundiram como máquinas dedicadas ao
processamento de informação. Ou seja, o computador (ou sistema
computadorizado1), em sua forma mais geral e tradicional, pode ser visto como
sendo um dispositivo que recebe um conjunto de dados de entrada, armazena–
os, modifica–os segundo as regras definidas por programa e fornece um
conjunto de dados de saída, resultante do processamento (Figura 2.2).
1 No contexto deste trabalho, os termos: sistema computadorizado, sistema informatizado,
sistema de processamento de dados são utilizados indistintamente como sinônimos.
COMPUTADOR DADOS DE ENTRADA
DADOS DE SAÍDA
Figura 2.2 – Sistema computadorizado tradicional.
40
Controle de estoques, folha de pagamento, contabilização de censo e dados
estatísticos, elaboração de tabelas de tiro, planilhas contábeis, cadastro de
clientes e contribuintes, verificação das declarações de imposto de renda,
compilação e inúmeras outras aplicações enquadram–se perfeitamente nesta
definição na qual fica evidenciado que o sistema computadorizado enfoca
preponderantemente os dados de entrada e de saída. A matéria, o interesse e
os fins do computador são as informações. Tais sistemas são chamados de
sistemas transformacionais, pois calculam valores de saída a partir de valores
de entrada e então terminam seus processamentos (FARINES et al., 2000).
No início, praticamente a totalidade dos sistemas informatizados se
enquadrava neste paradigma, e ainda hoje a maioria pertence a esta classe de
sistemas voltados primariamente ao processamento de informação.
Porém, devido às potencialidades inerentes ao conceito do computador,
aliadas ao forte avanço tecnológico que vem constantemente não só
aumentando drasticamente as funcionalidades, capacidades de processamento
e armazenamento, mas também reduzindo tamanho, consumo de energia e
dimensões físicas, não tardou muito a aparecer uma nova classe de sistemas
computadorizados focados não nos dados, mas sim no ambiente no qual
vivemos, cada vez mais controlado por máquinas automáticas. Ou seja, os
sistemas pertencentes a esta classe agora têm uma forte interação com o
mundo exterior. A informação deixa de ter o papel de fim e passa a ser o meio
a partir do qual o computador “sente” e “reage” ao ambiente físico,
respondendo à sua dinâmica característica. São chamados de sistemas
reativos, pois reagem enviando respostas continuamente a estímulos de
entrada vindos de seus ambientes (FARINES et al., 2000).
Surgem as duas principais funções do sistema computadorizado desta classe:
monitoração e controle, contrapondo–se às funções de armazenamento e
processamento, foco dos sistemas tradicionais de computação.
41
A partir do momento que o sistema computadorizado tem um forte acoplamento
com o ambiente físico, as leis naturais e as conseqüentes limitações físicas
impostas por essas passam a fazer parte integrante do sistema cujo projeto,
construção e operação hão de ser norteadas, entre outras, por tais restrições.
É de se esperar que, sendo o tempo uma das senão a mais importante
característica da natureza, uma vez que tudo que nesta ocorre é em função
deste, o tempo é o fator que mais fortemente impacta os sistemas
informatizados desta segunda categoria.
Em outros termos: a cadência das operações a serem executadas pelo
computador (seja na monitoração, processamento ou controle) para cumprir
seus objetivos de forma correta é ditada pelo ambiente ou pelos entes externos
que interagem com o computador.
Além disso, quanto mais a sociedade delega o controle de funções vitais aos
computadores, mais imperativa se torna a necessidade de que tais
computadores não falhem (BURNS e WELLINGS, 1996). Como resultado desta
atribuição de responsabilidades às máquinas, o desenvolvimento e a operação
de tais sistemas são norteados pelas conseqüências sociais em caso de falhas
tanto de projeto como de operação dos mesmos.
Tais sistemas são denominados Sistemas em Tempo Real ou Sistemas de
Tempo Real (Real–Time Systems – RTS), caracterizados por várias
particularidades que os distinguem dos sistemas computacionais tradicionais
mas fundamentalmente por:
Requisitos temporais determinísticos ou probabilísticos explícitos (SHA
et al., 2004).
Requisitos de confiabilidade (BURNS e WELLINGS, 1996).
Existem inúmeras definições formais para RTS dependendo do contexto,
escola filosófica ou mesmo preferência pessoal do autor, porém podemos
42
seguramente adotar sem maiores discussões, Sistema em Tempo Real como
sendo aquele no qual a correta operação (correctness) depende não só do
resultado lógico da computação, mas também do instante de tempo no qual o
resultado é produzido (STANKOVIC, 1988).
A classificação, detalhes e exemplos a respeito dos Sistemas em Tempo Real
encontram-se no APÊNDICE A.1.
2.4 Programas Aplicativos e Tarefas
Em um processador, um programa aplicativo consiste, geralmente, em um
conjunto de tarefas (tasks)2, que formam as unidades lógicas de computação.
Tarefa (task) consiste em uma unidade de trabalho agendada (scheduled) e
executada pelo sistema, sendo responsável por uma determinada
funcionalidade caracterizada por restrições temporais, comportamento
funcional, requisitos em termos de recursos e parâmetros de relação /
dependência com outras tarefas. Consiste em um conjunto fixo de linhas de
código (programa) a ser executado repetidamente, em geral com diferentes
valores de dados de entrada.
Um programa aplicativo de navegação, por exemplo, pode ser constituído por
uma tarefa responsável por adquirir coordenadas de um receptor GPS, outra
por adquirir dados de um sistema inercial, outra para estimar a posição do
veículo a partir dos dados adquiridos e uma quarta para tratar de uma eventual
falha na alimentação dos equipamentos.
2 Os termos tarefa (task), e trabalho (job) são utilizados de forma indistinta, enquanto que
processo (process) consiste em uma tarefa em execução. Alguns autores (LIU, 2000) consideram uma tarefa como sendo composta por um conjunto de trabalhos sendo o trabalho a unidade de execução, outros consideram o trabalho como sendo uma instância da tarefa (o mesmo que processo).
43
As tarefas podem ser classificas quanto à periodicidade (taxa de ocorrência)
como:
Periódicas.
Aperiódicas.
Esporádicas.
2.4.1 Tarefa Periódica
Tarefa cíclica (recorrente) que executa a intervalos de tempo regulares, cujo
instante de liberação (release time) de cada ciclo é determinado pelo tempo
relógio. Por definição, possui prazo limite rígido.
O modelo de tarefas periódicas é um modelo de carga de trabalho
determinístico (LIU e LAYLAND, 1973) bem conhecido. Muitos algoritmos de
agendamento baseados neste modelo possuem o comportamento bem
compreendido e apresentam bom desempenho. Caracteriza de maneira
precisa muitas das aplicações em Tempo Real Rígido como controle digital e
monitoração em Tempo Real (LIU, 2000).
2.4.2 Tarefa Aperiódica
Tarefa que executa a intervalos irregulares (aleatórios), ou seja, a qualquer
instante, resultando em uma freqüência de execução sem qualquer limite
(unbounded), cujo início é geralmente dado por um evento assíncrono externo.
Por definição possui prazo limite flexível ou não possui prazo limite algum3
(LIU, 2000).
3 Dependendo do contexto, o termo tarefa aperiódica pode apresentar sentido mais amplo significando tarefa não periódica, ou seja, aquela que não possui intervalo regular de repetição, sem qualquer distinção quanto ao prazo (neste caso a tarefa esporádica constitui uma subclasse de tarefa aperiódica)
44
2.4.3 Tarefa Esporádica
A tarefa que executa a intervalos irregulares, geralmente em resposta a
eventos assíncronos externos, caracterizada por prazo limite rígido e instantes
de liberação aleatórios porém distanciados entre si por um intervalo mínimo
conhecido, é dita esporádica (LIU, 2000, BURNS e WELLINGS, 1996).
A imposição deste intervalo de tempo mínimo entre liberações (Minimum
Interarrival Time – MIT) garante limite ao tempo de computação demandado
para o atendimento das diversas liberações da tarefa esporádica. A não fixação
deste limite implica que, em um instante ou intervalo de tempo, é possível a
ocorrência de um número de liberações de uma determinada tarefa variando de
0 a infinito, resultando em demanda ilimitada (unbounded) por recursos de
processamento. Fica clara, neste caso, a impossibilidade de qualquer garantia
de atendimento aos prazos limites (deadlines).
Periódica
Esporádica
Aperiódica
T T T T
≥T
≥0
≥T
C
Tempo
Tempo
Tempo
Figura 2.3 – Classificação das tarefas quanto à periodicidade.
45
2.5 Caracterização de uma Tarefa
Em geral as tarefas são caracterizadas por meio de seus parâmetros temporais
além das demais propriedades como periodicidade e prioridade. Os parâmetros
a serem considerados quando da modelagem e representação das tarefas
dependem basicamente da complexidade do sistema e da análise, além do
grau de fidelidade no qual se desejará modelar tanto tarefas como o problema
em si:
Prioridade (priority): (Pi) é um valor numérico que confere à tarefa uma ordem
de precedência de processamento.
Instante de liberação (release time): (ai) ou instante de chegada (arrival time)
é o instante de tempo no qual a tarefa se encontra disponível para execução
que, idealmente, no caso das tarefas periódicas coincide com o início do
período a menos que ocorra variação na liberação (release jitter). Uma tarefa
pode ser agendada e executada a qualquer momento no seu instante de
liberação, ou após este, assim que as condições de dependências de dados e
controle sejam satisfeitas (LIU, 2000).
Instante de início (start time): (Si ou si) instante de tempo no qual a tarefa
efetivamente inicia sua execução.
Variação de liberação (release jitter): (Ji) máxima variação no instante de
liberação.
Instante de finalização (completion time ou finish time): (Fi ou fi) instante de
tempo no qual se completa a execução da tarefa.
Prazo Limite (deadline): (Di ou di) ou simplesmente prazo é o instante de
tempo até o qual a execução da tarefa deve necessariamente ser completada
(LIU, 2000).
46
Tempo de resposta (response time): (Ri) intervalo de tempo transcorrido
entre o instante de liberação e o instante de finalização (término) da execução
da tarefa.
Tardeza (lateness): (Li = Fi – Di) atraso entre o instante de finalização da tarefa
com relação ao prazo limite. Li < 0 se a tarefa termina antes do prazo limite.
Tempo de computação (computation time): (Ci) ou tempo de execução
corresponde à quantidade de tempo necessária para que uma tarefa execute
por completo, normalmente expressa pelo tempo de pior caso (Worst Case
Execution Time – WCET).
Folga (laxity ou slack time): (Xi = di – ai – Ci) máximo tempo que uma tarefa
pode ser atrasada na primeira ativação a fim de completar seu processamento
sem perder seu prazo limite.
Utilização (utilization): ou fator de utilização ou carga de trabalho (load)
corresponde à fração da capacidade total de processamento utilizada. A
utilização de uma tarefa (Ui) corresponde à razão entre o tempo de computação
e o período da tarefa. A utilização do processador ou utilização total (U)
corresponde ao somatório da utilização de todas as tarefas.
(2.3)
(2.4)
Alguns parâmetros temporais das tarefas podem ser absolutos, medidos a
partir de um instante de tempo t = t1 que pode ser um instante qualquer ou o
instante de início da execução do sistema (geralmente t = 0). Neste caso são
47
representados por letras minúsculas (e.g. di, si, fi, etc.). Podem também ser
relativos, situação na qual são referenciados ao início de um período da tarefa
em questão, sendo representados por letras maiúsculas (e.g. Di, Si, Fi, etc).
Alguns dos parâmetros estão representados no diagrama da Figura 2.4.
2.5.1 Execução Preemptiva e Não Preemptiva
A forma de execução das tarefas em um RTS tem grande importância na
definição dos algoritmos de agendamento e despachamento, que pode se dar
de duas maneiras:
Execução não preemptiva: neste caso, uma tarefa em execução
(processo) continua a executar até que finalize, se auto–suspenda
enquanto aguarda operação de I/O ou quando requerer algum serviço
do RTOS.
ai
Ti Ti
Di Di
di fi si
Fi
Si Si
Ji
Fi
Ci
Li Li
Tempo
Figura 2.4 – Caracterização temporal de uma tarefa.
48
Execução preemptiva: a tarefa correntemente em execução pode ser
interrompida pelo despachador, dando lugar à execução de outra tarefa.
O instante e o motivo da preempção são determinados pela política de
agendamento e algoritmo de despachamento empregados. Em geral, os
RTSs preemptivos adotam uma política de agendamento e execução
preemptiva baseada em prioridades (preemptive priority–based
scheduling) na qual uma tarefa com uma determinada prioridade é
permitida executar enquanto as demais tarefas, aguardando para serem
executadas, possuírem menor prioridade. Assim que uma tarefa de
maior prioridade se apresenta para execução, a tarefa de prioridade
inferior correntemente em execução é imediatamente interrompida
dando lugar à nova tarefa prioritária, que assim permanece até que
finalize ou sofra preempção por conta de outra tarefa de maior
prioridade.
Esquemas não preemptivos possuem um overhead menor (tempo de
processador consumido no gerenciamento do sistema e não no processamento
das aplicações), porém os esquemas preemptivos, em geral, permitem que
tarefas com maior prioridade sejam mais reativas (menor tempo de resposta) e,
portanto, são preferidos (BURNS e WELLINGS, 1996).
2.5.2 Despachador (Dispatcher)
Controla a alocação da CPU decidindo qual será a próxima tarefa executada
mediante um sinal de relógio (clock interrupt), um evento (I/O interrupt) ou uma
chamada do RTOS. Também é conhecido como agendador de curto prazo
(short–term scheduler) levando essa designação devido ao fato de tender a ser
invocado com mais freqüência que o agendador (agendador de longo prazo ou
long–term scheduler) – a cada evento que possa levar à execução de uma
nova tarefa, à suspensão da tarefa corrente ou que possa fornecer uma
oportunidade de preempção da tarefa corrente a favor de outra (no caso de
49
despachador preemptivo). O despachador efetivamente controla a execução
das tarefas, tomando as medidas necessárias ao atendimento do
seqüenciamento determinado pelo agendador:
Criação e execução de tarefas.
Atribuição e mudança de estado das tarefas.
Preempção.
Compartilhamento da CPU.
Chaveamento de contexto (context switching).
2.5.3 Agendador (Scheduler) ou Escalonador
Também conhecido como agendador de longo prazo (long–term scheduler),
agendador de admissão (admission scheduler) ou agendador de alto nível
(high–level scheduler), é um dos ou o principal elemento de um Sistema em
Tempo Real responsável pelo agendamento, isto é, pelo seqüenciamento ou
determinação do ordenamento da execução do conjunto de tarefas.
Agendamento (scheduling) ou escalonamento é uma das mais importantes
ferramentas de gerenciamento de Sistemas em Tempo Real e, de forma ampla,
constitui–se no processo de alocação de recursos (e.g. CPU) às tarefas ao
longo do tempo, sob um conjunto de restrições temporais, para atingir um
determinado objetivo. No caso dos Sistemas em Tempo Real Rígido o objetivo
primário é o de garantir que todos os prazos limites sejam rigorosamente
cumpridos, enquanto que no caso dos Sistemas em Tempo Real Flexível
procura–se otimizar o desempenho médio de forma que a quantidade de
prazos limites não cumpridos seja a menor possível.
A teoria de agendamento (scheduling) originou–se dos estudos na área de
Pesquisa de Operações (Operations Research) que trata tipicamente de
50
questões do tipo Job Shop Problem, Flow Shop Problem, Open Shop Problem,
etc. onde o agendamento envolve atividades, ordens ou projetos e os recursos
podem ser máquinas, unidades fabris, unidades de processo, pessoas, etc.
(ÅRZÉN et al., 1999).
No contexto da Ciência da Computação, a teoria de agendamento se preocupa
com o agendamento de tarefas em um ambiente uni ou multiprocessado e o
agendamento de largura de banda de comunicação em sistemas distribuídos
(ÅRZÉN et al., 1999).
Neste trabalho, trata–se o agendamento como sendo a habilidade de organizar
a execução, por um único processador, de tarefas concorrentes de maneira
que todos os prazos limites sejam cumpridos.
As tarefas são ditas concorrentes pelo fato de os recursos oferecidos pelo
computador (uniprocessado no contexto do presente trabalho) serem limitados,
notoriamente a capacidade de processamento, fazendo com que o sistema
tenha que fornecer mecanismos de compartilhamento de tais recursos entre
todas as tarefas demandantes.
Um sistema não pode ser enquadrado como de Tempo Real rígido ou de
segurança crítica a menos que se possa verificar o atendimento de seus
requisitos, provando que as restrições temporais são atendidas e validando os
resultados obtidos de forma garantida. Isso implica que a técnica utilizada deve
ser previsível, no sentido de que uma abordagem previsível, do ponto de vista
de agendamento, é aquela que permite a demonstração analítica do
atendimento das restrições temporais. Já o determinismo nas questões de
agendamento pode ser definido como sendo o grau de conhecimento a priori
(antes da execução) das características das tarefas e das condições de
execução destas.
Em geral, o agendador possui duas funções básicas:
51
Um algoritmo de agendamento responsável por ordenar o uso dos
recursos do sistema (em particular capacidade de processamento).
Um Teste de Agendabilidade, isto é, um método analítico responsável
por prever o comportamento do sistema na situação de pior caso (e.g.
todos os processos sendo liberados no mesmo instante de tempo)
quando o algoritmo é aplicado. O teste permite avaliar se o algoritmo de
agendamento aplicado ao conjunto de tarefas em questão resulta no
cumprimento de todos os prazos limites durante a execução.
Existem vários algoritmos agendadores, porém a mais famosa análise a
respeito deste problema foi feita por Liu e Layland (1973) em um trabalho no
qual dois algoritmos, o Rate Monotonic e o Earliest Deadline First são
apresentados. O primeiro constitui no agendamento baseado na atribuição
estática de prioridades às tarefas (prioridades são atribuídas a priori durante
fase de projeto e mantêm–se fixas durante a execução do sistema) tomando
como critério de atribuição os períodos enquanto o segundo algoritmo baseia–
se na atribuição dinâmica de prioridades (atribuídas a priori porém são
alteradas ao longo da execução) tendo como critério os prazos limites relativos
correntes das tarefas.
2.6 Agendador a Taxas Monotônicas (Rate Monotonic Scheduler – RMS)
O RMS é constituído por um algoritmo simples de agendamento que define um
método de atribuição de prioridades e um teste de exeqüibilidade suficiente
porém não necessário.
A atribuição de prioridades a Taxas Monotônicas (Rate Monotonic – RM)
consiste em um esquema simples de atribuição ótima de prioridades no qual
cada tarefa recebe uma prioridade única de acordo com sua taxa ou freqüência
de execução de forma que quanto maior a taxa (i.e. mais curto o período) maior
52
a prioridade. Portanto o termo Taxas Monotônicas advém da atribuição
crescente de prioridades em função da freqüência de ocorrência.
O algoritmo RMS se aplica aos sistemas caracterizados por:
Sistema uniprocessado.
Execução preemptiva das tarefas.
Atribuição estática de prioridades.
Prioridade é um valor numérico que se confere à tarefa, indicando uma ordem
de precedência de processamento. No contexto do RMS, a prioridade não tem
qualquer relação com a importância subjetiva dada à tarefa. São representadas
por números inteiros sendo que, por convenção, quanto maior o valor, maior a
prioridade.
No geral, existem dois modelos possíveis de atribuição de prioridades:
Atribuição estática de prioridades: as prioridades são fixadas a priori, antes do
início do processamento, não sendo modificadas durante execução. É o
modelo utilizado no RMS
Atribuição dinâmica de prioridades: as prioridades podem ser modificadas
durante a execução.
A execução preemptiva garante a política de execução de tarefas na qual uma
tarefa em execução pode ser temporariamente interrompida (suspensa e
retomada) por outra tarefa que passa a executar em seu lugar.
No esquema de execução baseado em prioridades, assim que uma tarefa de
maior prioridade é liberada qualquer tarefa de prioridade inferior ativa dá lugar
a essa. Tarefas de menor prioridade nunca interrompem uma de maior
prioridade. Em um esquema não preemptivo, a tarefa liberada tem que
aguardar o término da outra mesmo que esta última tenha menor prioridade.
53
O esquema de atribuição de prioridades RM é considerado ótimo no sentido de
que se um determinado conjunto de tarefas pode ser agendado utilizando
qualquer outro método estático de atribuição de prioridade (agendamento
preemptivo) então este conjunto também pode ser agendado pelo RMS (LIU e
LAYLAND, 1973).
Em outras palavras, se o RMS não puder agendar um determinado conjunto de
tarefas, então nenhum outro agendador preemptivo baseado em atribuição
estática de prioridades o conseguirá.
A maturidade do RMS pode ser constatada pelo seu histórico de aplicação:
Em 1989 a IBM aplicou o RMS a um sistema de treinamento de SONAR,
permitindo que fossem descobertos e corrigidos problemas de
desempenho (LUCAS e PAGE, 1992).
Desde 1990, o RMS foi recomendado pela IBM Federal Sector Division
(atualmente Lockheed Martin) para seus projetos em Tempo Real.
O RMS foi aplicado com sucesso a um SONAR ativo e passivo de um
sistema de submarinos da Marinha Americana.
O RMS foi escolhido pela ESA – European Space Agency como base
teórica para seu projeto de RTOS.
A aplicabilidade do RMS a sistemas aviônicos típicos foi demonstrada
por Locke et al. (1991).
O RMS foi adotado em 1990 pela NASA para o desenvolvimento do
software em Tempo Real do subsistema de gerenciamento de dados da
Estação Espacial Internacional.
A empresa Magnavox Electronics Systems incorporou o RMS no
desenvolvimento de software em Tempo Real (IGNACE et al., 1994).
54
Os princípios do RMS influenciaram o projeto e desenvolvimento dos
seguintes padrões:
o IEEE FutureBus+(SHA et al., 1991).
o POSIX.
o Ada 95.
O RMS é considerado como sendo a evolução natural do CES4 (BATE, 1998),
contornando suas principais desvantagens (uso ineficiente de recursos,
dificuldade de manutenção e de acomodação de novos requisitos, dificuldade
de incorporação de tarefas esporádicas, etc.).
Uma diferença fundamental entre o CES e o RMS é que enquanto CES é
altamente determinístico, com um ordenamento de execução de tarefas fixo, o
RMS é apenas previsível (predictable) uma vez que, embora a carga de
trabalho seja determinística, o ordenamento de tarefas é dinâmico5 (BATE,
1998).
Um determinado conjunto de tarefas (task set) é chamado agendável ou
exeqüível (feasible) se puder ser agendado pelo algoritmo adotado, ou seja,
durante o processamento nenhum prazo limite será perdido. Caso contrário,
ocorrerá a chamada sobrecarga (overload) do processador (o conjunto de
tarefas não é exeqüível/agendável). A exeqüibilidade é avaliada mediante o
Teste de Agendabilidade.
Uma vez que o desempenho de uma dada tarefa de um sistema em Tempo
Real é muito complexo de se modelar de maneira factível, e dependente de um
grande número de diferentes variáveis, é importante construir uma noção
abstrata do que se entende por “computação” da tarefa. Supondo que a tarefa
4 Vide Apêndice A.3.
5 Os instantes de liberação das tarefas não são conhecidos a priori, conseqüentemente tanto a
ordenação como o intercalamento da execução são definidas durante a execução, de maneira não determinística.
55
possa ser reduzida a uma entidade claramente definida com tempo de
computação, instantes de invocação (i.e. período) e prazo limite (deadline)
conhecidos e, se o ambiente no qual ocorre a execução também é
similarmente bem definido (por exemplo, supondo que a quantidade de tempo
disponível para a execução ocorrer é adequado), então afirmações conclusivas
podem ser feitas a respeito do sistema. O problema de agendamento (que é o
de provar que todas as tarefas atendem aos seus prazos limites) se torna
simples o suficiente para ser provado.
Algumas premissas simplificadoras são aplicadas (LIU e LAYLAND, 1973) para
permitir a modelagem e análise do RMS:
Quantidade fixa e conhecida de tarefas periódicas.
Períodos fixos e conhecidos.
Tempos de computação (WCET) fixos e conhecidos
Tarefas independentes.
Prazos limites iguais aos períodos.
Overhead do sistema é desprezado
Dado que o tempo de computação de uma tarefa pode variar de ciclo para
ciclo, o valor adotado tradicionalmente é o correspondente ao pior caso (Worst
Case Execution Time – WCET). Isto pode resultar em um grande desperdício de
capacidade de processamento devido ao pessimismo quanto ao tempo de
processamento esperado de uma tarefa; porém garante que não haverá uma
eventual sobrecarga do processador.
56
2.7 Teste de Exeqüibilidade (Feasibility) ou Agendabilidade
O teste de exeqüibilidade ou agendabilidade é utilizado para garantir que a
execução de um determinado conjunto de tarefas pode satisfazer os prazos
limites especificados quando agendado de acordo com um algoritmo de
agendamento específico (CHENG, 2002).
Como visto, a sobrecarga do processador ocorre sempre que a demanda por
recursos computacionais aumenta de maneira que um ou mais prazos limites
de um conjunto de tarefas não sejam cumpridos.
O método de agendamento RMS de tarefas que executam preemptivamente
com períodos de execução (Ti) e tempo de computação (Ci) fixos e conhecidos
em fase de projeto, garante que nunca ocorrerá sobrecarga do processador
desde que a utilização do mesmo não ultrapasse o limite definido pelo Teste de
Agendabilidade de acordo com (LIU e LAYLAND, 1973). Nele, para um
agendador preemptivo com atribuição estática de prioridades baseada nos
períodos das tarefas (Rate Monotonic Priority Assignment), a utilização do
processador (U) deve ser inferior ou igual ao limite dado por:
(2.5)
Ou seja, existe um limite superior para a utilização do processador (ULUB –
Least Upper Bound Utilization), em função da quantidade de tarefas (N), abaixo
do qual a exeqüibilidade do conjunto de tarefas é garantida:
(2.6)
Desta maneira garante–se que o algoritmo de agendamento seja exeqüível; ou
seja, que nenhum prazo limite será comprometido, lembrando–se que esta é
uma condição suficiente, porém não necessária.
57
Como a utilização do processador é dada por:
(2.7)
obtém–se:
(2.8)
Aplicando–se a Equação 2.6 com diversos valores de (N) obtém–se os valores
limites de utilização que estão na Tabela 2.1:
Tabela 2.1 – Limites de utilização do processador.
N U (N)[%]
1 100.0
2 82.8
3 78.0
4 75.7
5 74.3
10 71.8
100 69.5
69.3
Para valores grandes de N, o limite de utilização tende assintoticamente a
69.3% (ln 2).
Exemplos mais detalhados ilustrando o agendamento RMS se encontram no
APÊNDICE A.4.
58
2.8 Análise de Tempos de Resposta (Response Time Analysis – RTA)
O Teste de Agendabilidade baseado na utilização do processador, visto
anteriormente, é bastante reconhecido e citado, sendo largamente utilizado
devido à sua simplicidade conceitual e baixa complexidade de implementação.
Porém, apresenta alguns limitantes (SHA et al., 2004):
O resultado do teste é uma condição suficiente, porém não necessária,
na qual o conjunto é certamente agendável para utilização inferior ao
limite de utilização (inferior a 1.0 para n > 1). Para valores acima do limite
de utilização até a máxima utilização do processador (U = 1) o teste vai
rejeitar um conjunto possivelmente agendável. Esta incerteza inerente
implica uma teoria pessimista com relação ao aproveitamento da
capacidade do processador.
O teste supõe a restrição de que o prazo limite seja igual ao período
para cada tarefa (Di = Ti).
A atribuição de prioridades deve ser feita de acordo com o esquema RM
obrigatoriamente. O teste deixa de ser suficiente para qualquer outra
política de atribuição.
A partir do estudo feito por Harter (1984, 1987) do problema mais geral da
determinação do pior caso do tempo de resposta de uma tarefa, isto é, do
maior intervalo de tempo entre o instante de liberação e o subseqüente instante
de finalização da tarefa, chegou–se a outro Teste de Agendabilidade. Este não
é mais baseado na utilização de processador, mas sim no tempo de resposta,
mediante a comparação deste com o respectivo prazo limite para cada uma
das tarefas do conjunto a agendar. Estudos equivalentes foram feitos
independentemente por Joseph & Pandya (1986) e Audsley et al. (1993)
resultando em um algoritmo que computa o tempo de resposta de pior caso (Ri)
de uma tarefa ( i) por meio da Equação 2.9:
59
(2.9)
Observa–se que a Equação 2.9 possui a variável Ri a determinar em ambos os
lados da igualdade além da função teto (ceiling), que fornece o menor inteiro
maior que o número racional calculado. Isto torna difícil sua solução. Na
verdade esta é uma equação de ponto fixo (BURNS e WELLINGS, 1996) que,
em geral, pode apresentar várias soluções. A forma mais simples de resolvê–la
é por meio da solução de menor ponto fixo, que resulta na seguinte fórmula de
recorrência (AUDSLEY et al., 1993):
(2.10)
Na Equação 2.10, é uma mera entidade matemática utilizada para resolver
o problema de ponto fixo e hp(i) corresponde ao subconjunto de tarefas cujas
prioridades são superiores à tarefa i. O conjunto de valores
é monotonicamente não decrescente e a solução é
encontrada quando . Se a equação não possuir solução, então o
valor de wi continuará subindo indefinidamente. Uma vez este se tornando
maior que o prazo limite (Di), pode–se supor que a tarefa não o cumprirá.
Este Teste de Agendabilidade baseado no cálculo do tempo de resposta de
cada tarefa do conjunto a agendar, embora seja de maior complexidade que o
teste baseado em utilização, apresenta como vantagens:
Ser uma condição suficiente e necessária: se o conjunto de tarefas
passar no teste, então estas cumprirão os prazos limites. Por outro lado,
se falhar, então certamente pelo menos uma das tarefas perderá seu
prazo limite (BURNS e WELLINGS, 1996).
60
Permitir o caso mais geral no qual os prazos limites são menores que os
períodos das tarefas (SHA et al., 2004).
Não ser restrito à política de agendamento RM, podendo ser utilizado
inclusive quando da atribuição (estática) arbitrária de prioridades
(AUDSLEY et al., 1993).
Voltando ao exemplo do conjunto de tarefas dado pela Tabela A.4 na qual o
teste suficiente porém não necessário baseado em utilização do processador
falha (U = 1.0, maior que o limite de 0.78 para três tarefas), obtém–se como
tempos de resposta, R1 = 80, R2 = 15 e R3 = 5, não superiores aos respectivos
prazos limites de D1 = 80, D2 = 40 e D3 = 20 confirmando a agendabilidade do
conjunto de maneira suficiente e necessária.
2.9 Agendamento de Tarefas Aperiódicas / Esporádicas
Embora a maioria das tarefas em um Sistema em Tempo Real seja periódica
(aquisição e controle), algumas tarefas precisam ser executas em resposta a
um evento externo, normalmente sinalizado por meio de uma interrupção que
ocorre a intervalos de tempo irregulares (BUTTAZZO, 2002). Tais eventos
assíncronos ocorrem com certa imprevisibilidade e, mais do que isso,
geralmente requerem baixo tempo de resposta por parte das tarefas
responsáveis pelo atendimento. Exemplos incluem: resposta ao acionamento
manual de chaves e botões (push–buttons) como disparo de armas, tratamento
de alarmes (falha de equipamentos, detecção de fumaça ou incêndio, desvio
de rota ou atitude, drift de sensores, parâmetros fora de faixa normal de
operação, etc.), segurança em maquinaria industrial (detectada presença de
operador próximo à máquina em funcionamento) entre outros.
Para que o sistema atenda de maneira satisfatória tanto ao processamento das
tarefas periódicas como ao processamento das tarefas aperiódicas é
necessário conciliar as distintas necessidades de cada classe de tarefas. Isto
61
deve ser feito de forma que se possa atender aos eventos por meio de tarefas
aperiódicas com o menor tempo de resposta possível, ou esporádicas com
garantia de execução dentro dos prazos limites. E isso sem prejudicar o
atendimento dos prazos limites rígidos das tarefas periódicas.
Como visto anteriormente, o Agendador a Taxas Monotônicas tradicional
garante a exeqüibilidade de um conjunto de tarefas restrito ao conjunto de
restrições pré–estabelecidas pelo algoritmo RMS, dentre estas a da
periodicidade das tarefas. Porém existem diversas técnicas que permitem a
incorporação de uma ou mais tarefas aperiódicas ao conjunto agendado pelo
RMS sendo que, neste caso, uma premissa fundamental é de que a inclusão
de tarefas aperiódicas não afete a exeqüibilidade do conjunto de tarefas
periódicas agendadas pelo RMS.
Vale ressaltar que, no caso das tarefas aperiódicas (prazos limites flexíveis), o
objetivo do agendamento é o de minimizar o tempo de resposta, já que não é
possível garantir o atendimento dos prazos limites a priori (antes da execução).
Já para as tarefas esporádicas (prazos limites rígidos), o objetivo do
agendamento é o de garantir que os prazos limites sejam atendidos a priori.
Em qualquer dos casos, tal objetivo não deve arriscar os prazos limites rígidos
das tarefas periódicas agendadas pelo RMS ou por qualquer outro método de
agendamento.
Na literatura são consideradas basicamente duas abordagens no sentido de se
acomodar uma ou mais tarefas aperiódicas ao agendamento de tarefas
periódicas:
Serviço em Segundo Plano.
Servidor Periódico.
62
Na primeira aproveitam–se as sobras da capacidade do processador para
execução das tarefas aperiódicas; e na segunda reserva–se uma parcela da
capacidade de processamento por meio de uma tarefa periódica dedicada.
2.9.1 Serviço em Segundo Plano (Background Servicing – BS)
A forma mais simples de suportar tarefas aperiódicas em um ambiente RMS
consiste em executá–las em segundo plano, ou seja, com a menor prioridade,
utilizando–se dos ciclos de CPU excedentes (não utilizados pelo conjunto de
tarefas periódicas que fazem parte do agendamento RM). Claramente o tempo
de resposta tende a ser bastante alto, uma vez que as tarefas aperiódicas só
poderão ser atendidas após o término de execução de todas as demais tarefas
prioritárias (i.e. tarefas periódicas). Por outro lado, isto sempre produz um
agendamento correto das tarefas periódicas, que não é afetado pelo uso da
capacidade de processamento excedente. Fica claro também que só é possível
acomodar as tarefas aperiódicas se existir o excedente de CPU (Up < 1).
Neste modelo, as tarefas periódicas são agendadas normalmente pelo RMS,
enquanto que os eventos aperiódicos são enfileirados e atendidos de acordo
com uma determinada política (geralmente o atendimento na ordem de
chegada conhecido como First Come First Served – FCFS) sempre que houver
ciclos de CPU disponíveis (processador ocioso) (Figura 2.5).
63
A Figura 2.6 ilustra a operação do Serviço em Segundo Plano para o conjunto
de tarefas dado na Tabela 2.2.
Tabela 2.2 – Exemplo de conjunto de tarefas com Serviço em Segundo Plano.
Tarefa
(i) T. Comput.
(Ci) Período
(Ti) Prioridade
(Pi) Utiliz.
(Ui)
1 4 10 2 0.4
2 8 20 1 0.4
0.8
As tarefas periódicas τ1 e τ2 são agendadas segundo a Atribuição de
Prioridades a Taxas Monotônicas e o Teste de Agendabilidade confirma o
conjunto como exeqüível com utilização U = 0.8, inferior ao limite ULUB(2) = 0.828
(Tabela 2.1). No instante crítico (t = 0) τ1 e τ2 se encontram prontas para
executar e nos instantes de tempo te3 = 5 e te3 = 12 ocorrem dois eventos
aperiódicos requisitando a execução da tarefa aperiódica τ3 caracterizada por
CPU
Fila Não Priorizada
RMS
FCFS
Tarefas Periódicas
Fila Priorizada
Tarefas Aperiódicas
Tempo Relógio
Eventos
Figura 2.5 – Serviço em Segundo Plano.
64
tempo de computação C1 = 1 unidade de tempo. Esses eventos só poderão ser
atendidos a partir do instante t = 16 já que o processador se encontra
constantemente comprometido na execução das tarefas τ1 e τ2 até esse
instante, vindo a ser requisitado novamente em t = 20 para execução das
tarefas periódicas.
Durante este intervalo de 2 unidades de tempo a partir do instante t = 16 o
sistema executa a tarefa τ3 duas vezes, uma em resposta a cada um dos
eventos ocorridos. O tempo de resposta para o primeiro evento é:
(2.11)
0 2 4 6 8
Tempo
10 12 14 16 18 20
Execução
Tarefa 1
1 2
1 2
1 2
Tarefa 2
Tarefa 3
Serviço em Segundo Plano
Figura 2.6 – Linha de Tempo com Serviço em Segundo Plano.
65
(2.12)
Já para o segundo evento:
(2.13)
(2.14)
Os tempos de resposta para os dois eventos são R3 = 12 e R3 = 6 unidades de
tempo respectivamente, embora o tempo gasto para execução seja de apenas
1 unidade de tempo cada.
Quanto maior a carga imposta pelas tarefas periódicas, menor será a utilização
do processador deixada para o Serviço em Segundo Plano, implicando menor
freqüência de oportunidades de atendimento aos eventos e dilatando o tempo
de resposta.
Como o método de agendamento de tarefas aperiódicas por meio de Serviço
em Segundo Plano simplesmente faz uso da capacidade ociosa da CPU sem
fornecer quaisquer garantias intrínsecas formais em termos de atendimento de
requisitos temporais, não se podem fazer quaisquer previsões a priori em
termos de desempenho, atendimento de prazo limite ou mesmo de
atendimento ao evento, fazendo deste um método aceitável apenas para o
agendamento de tarefas aperiódicas não críticas, tolerantes a altos Tempos de
Resposta. O Serviço em Segundo Plano não é adequado ao agendamento de
tarefas esporádicas (com prazos limites rígidos ou firmes).
2.9.2 Servidor Periódico (Periodic Server)
Esta abordagem consiste em reservar capacidade de processamento
artificialmente por meio de uma tarefa periódica dedicada a atender (prestar
serviço) a um ou mais eventos aperiódicos, levando por esse motivo a
66
denominação de Servidor Periódico (Periodic Server). Em geral, para cada
evento esporádico (atendido por tarefa aperiódica com prazo rígido) é
destinado um servidor distinto. No caso de eventos aperiódicos (atendidos por
tarefas com prazos flexíveis) é comum uma única tarefa servidora atender a
mais de um evento (Figura 2.7).
Assim como qualquer outra tarefa periódica, o servidor é definido por seu
período de execução (TS) e seu tempo de computação (Cs) denominado
capacidade do servidor (execution budget ou simplesmente budget). A relação
entre a capacidade e o período do servidor (Equação 2.15) é chamada
tamanho do servidor (server size).
(2.15)
O processo de atribuir um valor a Cs é denominado restauração ou
preenchimento (replenishment) e ocorre no instante de tempo denominado
CPU
Fila Não Priorizada
RMS Tarefas Periódicas
Fila Priorizada
Tarefa Aperiódica
Tempo Relógio
Eventos
Figura 2.7 – Servidor Periódico.
67
instante de preenchimento (replenishment time - RTs). Diz–se que a capacidade
do servidor foi exaurida (exhausted) quando seu valor chega a zero.
Dentre as várias formas de implementação do Servidor Periódico podem–se
destacar:
Servidor de Varredura (Polling Server – PS).
Servidor Adiável (Deferrable Server – DS).
Servidor de Troca de Prioridades (Priority Exchange – PE).
Servidor Esporádico (Sporadic Server – SS).
2.9.3 Servidor de Varredura (Polling Server – PS)
Ou Servidor Periódico de Varredura (Polling Periodic) consiste em uma tarefa
periódica, que executa a intervalos regulares (TS), dedicada à verificação da
ocorrência de um determinado evento e ao seu atendimento por meio da
execução do código adequado a este fim durante um intervalo de tempo
limitado por sua capacidade pré–estabelecida (Cs). Não ocorrendo o evento, o
servidor se auto–suspende e tem que aguardar até o próximo instante de
varredura (i.e. TS). Além disso, a capacidade de processamento originalmente
alocada para o serviço no período corrente não é preservada para execução
aperiódica (a capacidade do servidor é zerada), sendo perdida durante este
período. O intervalo de tempo que seria utilizado pelo servidor é aproveitado
pelas tarefas periódicas (SPRUNT et al., 1989) que podem antecipar suas
execuções. O uso de servidor tem como propósito o de reservar recursos de
processador para execução de tarefas aperiódicas em meio ao quadro de
execução periódico.
O servidor é agendado por meio do mesmo algoritmo utilizado para as tarefas
periódicas ordinárias. No caso em que o servidor é dimensionado para atender
68
a mais de um evento aperiódico dentro de um único ciclo de varredura, a
ordenação do processamento destes eventos não depende do algoritmo de
agendamento utilizado para as tarefas periódicas, podendo ser feita na base da
ordem de chegada (FCFS), tempo de computação, prazo limite, ou qualquer
outro parâmetro. No caso de tarefas esporádicas, cada ciclo de varredura
atende a um único evento. A prioridade da tarefa servidora (i.e. o período no
caso do RMS) pode ser escolhida de acordo com os requisitos de tempo de
resposta esperados para as tarefas periódicas.
Embora o tempo de resposta médio para as tarefas aperiódicas servidas pelo
PS tenda a ser bem inferior aos obtidos mediante o uso do BS, deve–se notar
que, se um evento aperiódico ocorrer imediatamente logo após a suspensão do
servidor, ele tem que aguardar, no mínimo, até o início do próximo período de
varredura quando a capacidade do servidor é restabelecida ao seu valor
integral, resultando em aumento significativo do tempo de resposta e
aproveitamento ineficiente da capacidade de CPU já que a capacidade não
utilizada não é preservada no período. Portanto, em determinadas situações, o
PS pode inclusive apresentar tempo de resposta superior ao BS embora tenda
a apresentar tempo de resposta médio melhor.
Na Tabela 2.3 encontra–se um conjunto de tarefas sendo as duas primeiras
periódicas, e a terceira o Servidor de Varredura. A análise dos tempos de
resposta (R1 = 5, R2 = 20 e RS = 1) confirma que o conjunto é agendável pelo
RMS, embora a utilização seja superior ao limite para três tarefas
(ULUB(3) = 0.78). Isto significa que nenhuma tarefa periódica perderá o prazo
limite (note–se que o servidor é tratado como qualquer outra tarefa periódica de
maneira indistinta para efeito de agendabilidade periódica), porém não é
garantia suficiente para que a tarefa aperiódica, a ser atendida pelo servidor na
ocorrência do respectivo evento, tenha seu prazo limite cumprido
necessariamente.
69
Tabela 2.3 – Exemplo de conjunto de tarefas com Servidor de Varredura.
Tarefa
(i) T. Comput.
(Ci) Período
(Ti) Prioridade
(Pi) Utiliz.
(Ui)
1 4 10 2 0.4
2 8 20 1 0.4
S 1 5 3 0.2
1.0
Supondo a ocorrência dos eventos aperiódicos em te3 = 5 e te3 = 12 e o tempo
de computação da tarefa aperiódica igual à capacidade do servidor (C1 = CS = 1),
a execução do conjunto resulta na Linha de Tempo da Figura 2.8 na qual se
podem observar os tempos de resposta para o primeiro evento:
(2.16)
E para o segundo evento:
(2.17)
O mesmo conjunto de tarefas e eventos agendados pelo BS resultou em
tempos de resposta bem superiores (R3 = 12 e R3 = 6) se comparados ao
desempenho obtido com o PS (R3 = 1 e R3 = 4), principalmente para o primeiro
evento. A execução pode ser observada na Figura 2.8.
70
Dado um conjunto formado por N tarefas periódicas mais um Servidor de
Varredura caracterizado por TS e CS, suas utilizações estão nas Equações 2.18,
2.19:
(2.18)
(2.19)
Figura 2.8 – Linha de Tempo com Servidor de Varredura.
0 2 4 6 8
Tempo
10 12 14 16 18 20
Execução
Tarefa 1
1 2
1
2
Tarefa 2
Tarefa S
2
1
Capacid. Servidor
1.0
Servidor de Varredura: Tempo de Computação=1, Período=5
71
A agendabilidade do conjunto periódico é garantida pelo RMS se valem as
Equações 2.20 e 2.21:
(2.20)
(2.21)
Em geral, no caso da existência de mais de um servidor usa-se a Equação 2.22
(2.22)
que também pode ser escrita forma da Equação 2.23:
(2.23)
Dada uma tarefa esporádica a caracterizada por tempo de computação (Ca) e
prazo limite (Da), a pior situação ocorre quando o evento perde a tarefa
servidora e tem que aguardar a próxima instância (próximo período do
servidor). Supondo–se Ca CS, a tarefa esporádica completa sua execução em,
no máximo, 2 períodos do servidor (TS), um aguardando e outro processando.
Isto significa que o prazo limite pode ser garantido se valer a Equação 2.24:
(2.24)
Para o caso de tempo de computação arbitrário (Ca > CS) tem–se a Equação
2.25:
72
(2.25)
Portanto, embora seja possível garantir o prazo limite da tarefa nessas
condições (tarefa esporádica), claramente o tempo de resposta não é bom.
Vale ressaltar que o MIT não pode ser inferior ao prazo limite (Da).
Enquanto o teste resultante da aplicação da Equação 2.23 garante a
agendabilidade do conjunto de tarefas periódicas (considerando a tarefa
servidora ou as tarefas servidoras como sendo tarefas periódicas ordinárias e,
portanto, incluídas na análise) a Equação 2.24 ou 2.25, conforme o caso, é
utilizada para testar a agendabilidade da tarefa esporádica (garantia
aperiódica) atendida pelo servidor.
Este Teste de Agendabilidade da tarefa esporádica corresponde a uma
condição suficiente e não necessária porque não leva em consideração quando
ocorre a execução dentro do período do servidor. Porém um teste suficiente e
necessário (Equação 2.26) pode ser determinado no caso em que a prioridade
do servidor é a maior, ou seja, seu período é o mais curto (BUTTAZZO, 1997).
Neste, e somente neste caso, a execução sempre se dá no início do período,
tornando possível a determinação precisa do instante de finalização da tarefa
aperiódica (ou esporádica) possibilitando prever a situação no qual o prazo
limite pode ser cumprido, conforme a Equação 2.26:
(2.26)
onde:
(2.27)
Note–se que na desigualdade 2.26 aparecem o prazo limite absoluto (da) e o
tempo de liberação absoluto da tarefa aperiódica (aa). Esses parâmetros não
73
podem ser determinados a priori, de maneira que este teste só pode ser
aplicado durante a operação do sistema e imediatamente antes da execução
da respectiva tarefa. Sendo assim, neste caso, não é possível dar garantia
suficiente e necessária ao atendimento do prazo limite de uma tarefa
esporádica (aperiódica com prazo limite rígido). Entretanto, este teste pode ser
utilizado como teste de admissão de tarefas aperiódicas com prazos firmes,
situação na qual o início da iminente execução da tarefa (liberação) só é
permitido se houver a garantia de cumprimento do prazo limite.
2.9.4 Servidor Adiável (Deferrable Server – DS)
Assim como o Servidor de Varredura, o Servidor Adiável (LEHOCZKY et al.,
1987) consiste em uma tarefa periódica, normalmente com alta prioridade,
destinada a prover atendimento a eventos aperiódicos. Porém, ao contrário do
PS, o DS preserva sua capacidade (budget) ao longo do período caso não
existam eventos pendentes no instante de liberação do servidor. Desta forma,
um evento aperiódico pode ser atendido no mesmo nível de prioridade da
tarefa servidora, a qualquer momento enquanto não houver a exaustão da
capacidade do servidor (CS). No início de cada período do servidor (TS) a
capacidade é restaurada ao seu valor máximo. Devido à habilidade de prover
atendimento imediato ou quase imediato à tarefa aperiódica, o tempo de
resposta médio é sensivelmente melhorado com relação às técnicas
anteriormente apresentadas. Algoritmos deste tipo são denominados
algoritmos preservadores de banda (bandwidth preserving algorithms) devido
ao mecanismo de preservação de recursos de processamento (i.e. banda)
alocados para atendimento aperiódico caso estes, uma vez disponíveis, não
sejam imediatamente necessários (SPRUNT et al., 1989).
Não há um valor de utilização conhecido que garanta a agendabilidade do
conjunto de tarefas periódicas com prioridades fixas no qual o DS é agendado
a uma prioridade arbitrária. A única exceção é o caso especial no qual o
74
período do servidor (TS) é menor que os períodos de todas as tarefas
periódicas e o sistema é agendado pelo RMS (LIU, 2000), ou seja, o DS
executa com a prioridade mais alta. Um sistema com N tarefas6 periódicas
independentes “preemptáveis”, cujos períodos satisfazem ao conjunto de
desigualdades 2.28 e cujos prazos limites são iguais aos respectivos períodos
é agendável pelo RMS com um Servidor Adiável se sua utilização total é menor
ou igual ao valor dado pela Equação 2.29 (LEHOCZKY et al., 1987,
STROSNIDER et al., 1995).
(2.28)
(2.29)
Para uma quantidade muito grande de tarefas (N→ ) a Equação 2.29 se reduz
a:
(2.30)
Como o conjunto de tarefas periódicas é agendável se:
(2.31)
chega–se a:
(2.32)
6 N contabiliza apenas as tarefas periódicas comuns, excluindo o(s) servidor(es).
75
A garantia do prazo limite da tarefa (esporádica) se dá quando:
(2.33)
no qual:
(2.34)
onde:
(2.35)
Na Tabela 2.4 encontra–se um exemplo de conjunto de tarefas a ser agendado
mediante o uso do DS, constituído de duas tarefas periódicas mais a tarefa
servidora com 0.8 unidades de tempo de computação (CS) e período (TS) igual a
5 unidades de tempo, conferindo a esta a maior prioridade segundo o RMS.
São previstos dois eventos aperiódicos: um no instante t = 5 e outro em t = 12
com tempos de computação C = 0.8 e C = 0.4 unidade de tempo
respectivamente. O sistema inicia em t = 0 com a capacidade máxima (CS = 0.8
correspondente ao WCET) que é completamente consumida para o
processamento completo da tarefa esporádica relativa ao primeiro evento
(t = 5), cujo atendimento se dá instantaneamente uma vez que, além da alta
prioridade, o servidor dispõe de capacidade disponível para tal, que foi
preservada ao longo do tempo (ao contrário do que ocorreria com o PS).
76
Tabela 2.4 – Exemplo de conjunto de tarefas com Servidor Adiável.
Tarefa
(i) T. Comput.
(Ci) Período
(Ti) Prioridade
(Pi) Utiliz.
(Ui)
1 4 10 2 0.40
2 8 20 1 0.40
S 0.8 5 3 0.16
0.96
O comportamento do sistema pode ser observado na Figura 2.9. A capacidade
completamente exaurida no instante t = 6 é novamente restaurada ao seu valor
máximo depois de transcorrido o intervalo de tempo referente ao período do
servidor a partir da ultima restauração (ou seja, ocorre em t = 5, t = 10, t = 15,...).
Note–se que o processamento do evento que ocorre em t = 12 leva menos
tempo para finalizar neste caso específico, consumindo apenas 0.4 unidades
de tempo e não chega a exaurir toda a capacidade do servidor, dimensionado
para o WCET.
77
2.9.5 Servidor de Troca de Prioridades (Priority Exchange – PE)
Assim como os algoritmos OS e o DS, o algoritmo do Servidor de Troca de
Prioridades (LEHOCZKY et al., 1987) utiliza um servidor periódico
(normalmente com alta prioridade) para atender aos eventos aperiódicos.
Entretanto, este difere dos demais métodos na maneira na qual a capacidade é
preservada. Ao contrário do DS, o PE preserva sua capacidade em alta
prioridade trocando–a por tempo de computação de uma tarefa periódica de
0 2 4 6 8
Tempo
10 12 14 16 18 20
Execução
Tarefa 1
1 2
1
2
Tarefa 2
Tarefa S
2
1
Capacid. Servidor
1.0
Servidor Adiável: Tempo de Computação=0.8, Período=5
Figura 2.9 – Linha de Tempo com Servidor Adiável.
78
menor prioridade quando se encontra ocioso (não há evento aperiódico
pendente).
No início de cada período do servidor, a capacidade é restaurada ao seu valor
máximo. Se a prioridade corrente do sistema corresponde à prioridade do
servidor (isto é, a capacidade de processamento disponível é para o
atendimento da tarefa aperiódica) e há um evento pendente, então a tarefa
aperiódica é executada. Caso contrário, a tarefa periódica pendente (próxima
na ordem de prioridades) é executada com uma troca de prioridades. Isso
significa que a tarefa periódica executa com a prioridade mais alta, que
pertencia ao servidor. Esta, por sua vez, tem o respectivo tempo de
computação disponível não utilizado acumulado no nível de prioridade da tarefa
periódica em questão. Em outras palavras, ocorre uma troca entre a
capacidade de computação aperiódica de prioridade mais alta do servidor com
o tempo de computação utilizado pela tarefa periódica de menor prioridade.
Desta forma, a tarefa periódica dá prosseguimento ao seu processamento
normalmente e a capacidade de processamento aperiódico não é perdida, mas
sim preservada, embora em um nível de prioridade mais baixo. As trocas de
prioridade continuam até que o tempo de computação aperiódico de alta
prioridade seja exaurido ou até o instante em que ocorra um novo evento
aperiódico. A exaustão da capacidade de computação aperiódica se dá, seja
por conta de seu uso na execução da tarefa aperiódica, seja pela degradação
da prioridade ao nível de execução em segundo plano (background). Esta
degradação completa da prioridade se dá apenas quando nenhum novo evento
aperiódico ocorre cedo o suficiente para fazer uso da capacidade aperiódica. A
todo o momento o algoritmo PE faz uso do tempo de execução disponível de
maior prioridade para atender tanto as tarefas periódicas como as aperiódicas.
Além disso, como o objetivo do algoritmo é o de fornecer o menor tempo de
resposta médio ao atendimento aperiódico, qualquer empate de prioridade é
resolvido a favor da tarefa aperiódica.
79
O limite de agendabilidade do PE, dado pela Equação 2.36, é obtido com a
mesma técnica utilizada no caso do DS supondo, da mesma forma, que a
prioridade do servidor é a mais alta do sistema de acordo com as condições
estabelecidas no conjunto de desigualdades 2.28.
(2.36)
Para uma quantidade muito grande de tarefas (N→ ) a Equação 2.36 reduz–se
à Equação 2.37:
(2.37)
Como o conjunto de tarefas periódicas é agendável se:
(2.38)
chega–se a:
(2.39)
Comparando–se as Equações 2.32 e 2.39 que definem os limites de utilização
do processador para uma quantidade muito grande de tarefas (N→ ) dos
algoritmos DS e PE respectivamente, fica claro que, para um determinado
tamanho de servidor US (0 < US < 1), o limite de agendabilidade do conjunto de
tarefas periódicas (UP) do algoritmo DS é menor que o do PE (SPRUNT et al.,
1989).
A Figura 2.10 ilustra o resultado da aplicação do algoritmo PE sobre o mesmo
conjunto de tarefas (Tabela 2.4) utilizado no exemplo referente ao DS com
80
capacidade do servidor CS = 1 e período TS = 5 unidades de tempo, eventos
ocorrendo em t = 5 e t = 12 e tempos de computação iguais a 1 e 0.5 unidades
de tempo respectivamente.
81
0 2 4 6 8
Tempo
10 12 14 16 18 20
Execução
Tarefa 1
1 2
1
2
Tarefa 2
Tarefa S
1
Capacid. Servidor Prior. 1
1.0
Servidor de Troca de Prioridades: Tempo de Computação=1, Período=5
1.0
2.0
3.0
Capacid. Servidor Prior. 2
Capacid. Servidor Prior. 3
1.0
2
Figura 2.10 – Linha de Tempo com Servidor de Troca de Prioridades.
82
Como o algoritmo PE necessita lidar com a capacidade do servidor ao longo de
todos os possíveis níveis de prioridade do sistema, é necessária uma curva de
capacidade para cada um dos níveis, no caso 3, sendo que este servidor
executa com a maior prioridade. No início de execução e a cada período do
servidor, a sua capacidade relativa ao nível da prioridade nominal é restaurada
ao valor máximo (CS = 1). Como não há evento aperiódico pendente no instante
t = 0 ocorre uma troca de prioridade entre o servidor e a tarefa no próximo nível
de prioridades a executar (a capacidade do servidor é rebaixada da prioridade
PS = 3 para a prioridade P1 = 2, da tarefa 1, enquanto esta última executa). No
instante t = 4, ao término da execução da tarefa 1, ocorre uma nova troca,
agora entre a já rebaixada prioridade do servidor com a da tarefa 2 no próximo
nível (P2 = 1). Desta maneira 2 dá início a sua execução e a capacidade do
servidor é preservada com prioridade igual a 1 até o instante t = 5 (t = 0 + TS)
quando a capacidade do servidor no nível de prioridade original é restaurada.
Neste instante ocorre um evento, fazendo com que a tarefa aperiódica S seja
executada, causando a preempção da tarefa 2. A execução do servidor (S)
consome a capacidade de mais alta prioridade (no caso 3). Note–se que não
ocorre troca alguma neste caso e que, embora a capacidade de alta prioridade
seja totalmente consumida durante a execução completa da tarefa aperiódica,
ainda resta capacidade preservada no nível de prioridade 1. A tarefa 2 retoma
sua execução até t = 10 (t = 5 + TS) quando ocorre uma nova preempção, agora
devido à segunda liberação de 1 (P1 = 2), além da restauração no nível 3 da
capacidade do servidor com a subseqüente troca de prioridade devido à
inexistência de eventos pendentes. Em t = 12 ocorre um evento, a tarefa
aperiódica é executada com prioridade 2 (causando a preempção de 1, uma
vez que, ocorrendo o empate de prioridades, este é sempre vencido pela tarefa
aperiódica) consumindo 0.5 unidades de tempo de capacidade do servidor
neste nível até o instante t = 12.5 quando 1 retoma sua execução e finaliza em
t = 14.5 quando é a vez de 2 retomar a execução e o restante da capacidade
do servidor é agora trocada para o nível de prioridade 1. Em t = 15 ocorre a
83
restauração e novamente há uma troca de prioridade, agora entre com o nível
da tarefa 2 (P2 = 1). Em t = 17.5 observa–se o total acumulado de 2.5 unidades
de tempo de capacidade do servidor nesta prioridade, instante de tempo a
partir do qual inicia–se o descarte da capacidade (degradação da prioridade ao
nível de segundo plano) uma vez que não há tarefas periódicas ou aperiódicas
pendentes. A degradação total se dá em t = 20.
2.9.6 Servidor Esporádico (Sporadic Server – SS)
O Servidor Esporádico foi desenvolvido como um algoritmo geral para
agendamento tanto de tarefas aperiódicas como de tarefas esporádicas
(SPRUNT et al., 1989) objetivando contornar as principais limitações do DS
(tamanho reduzido do servidor) e do PE (grande complexidade) e ao mesmo
tempo fornecer “responsividade” comparável a estes. Como resultado, o
algoritmo do SS possui o mesmo tamanho de servidor do PE mediante um
pequeno aumento de complexidade com relação ao DS. Assim como ambos os
métodos, o SS é um algoritmo preservador de banda, diferindo basicamente na
forma em que a capacidade do servidor é restaurada. Basicamente, enquanto
os algoritmos DS e PE periodicamente restauram a capacidade do servidor
com seu valor pleno (sempre o início de cada período do servidor), o SS
restaura apenas o valor efetivamente consumido pela tarefa aperiódica
(logicamente só ocorre a restauração se a capacidade foi parcial ou totalmente
utilizada). Além disso, o instante de restauração (RTS) se dá no momento
correspondente ao período do servidor (TS) somado ao instante de tempo do
início do consumo da capacidade (CS) (início da execução da tarefa aperiódica
de atendimento ao evento).
As regras de consumo e restauração de capacidade do algoritmo garantem que
cada Servidor Esporádico com período TSi e capacidade CSi nunca demande
mais tempo de processador que a tarefa periódica caracterizada por TSi e CSi
em qualquer intervalo de tempo. Como conseqüência, pode–se tratar o SS
84
exatamente como a respectiva tarefa periódica quando da verificação da
agendabilidade do sistema (LIU, 2000).
As premissas a seguir são adotadas para efeito de análise do algoritmo SS
aplicado a tarefas esporádicas de forma que os prazos limites sejam atendidos:
Agendamento com prioridades fixas de acordo com a política RMS e
suas respectivas premissas:
o Todas as tarefas são periódicas sem interação entre si.
o Prazos limites correspondem sempre ao final do período.
o Sem interrupção.
o Tarefas não se auto-suspendem.
o Todas as tarefas rodam em um único processador.
o Não há consumo de CPU por chaveamento de contexto
(overhead nulo).
Prazo limite da tarefa periódica igual ao período do servidor.
MIT maior ou igual ao período do servidor.
Tarefa aperiódica sempre tem precedência com relação à tarefa
periódica caso ambas possuam a mesma prioridade.
Cada servidor periódico é responsável pelo atendimento de uma única
tarefa aperiódica.
O servidor possui capacidade suficiente para atender às necessidades
em termos de tempo de computação da tarefa esporádica a cada
ativação.
85
O método de restauração da capacidade do Servidor Esporádico segue as
seguintes regras básicas:
Caso o servidor tenha sua capacidade (tempo de computação) parcial
ou completamente consumida em um dos seus períodos de execução,
então sua restauração ocorrerá apenas no instante ou tempo de
restauração (RTS).
O instante ou tempo de restauração (RTS) é determinado adicionando–se
o valor do período do servidor (TS) ao instante de tempo do início do
consumo da capacidade (i.e. o instante de início da execução da tarefa
esporádica dando atendimento a um evento aperiódico).
A quantidade ou valor da capacidade a restaurar no instante RTS
corresponde ao valor da capacidade consumida durante a execução da
tarefa esporádica até o momento.
É provado que, do ponto de vista de agendabilidade, o Servidor Esporádico
pode ser tratado como uma tarefa periódica comum com mesmo período e
tempo de computação (SPRUNT et al., 1989). Tal prova é necessária uma vez
que o SS viola uma das premissas básicas que regem a execução de tarefas
periódicas de acordo com o RMS (LIU e LAYLAND, 1973). Dado um conjunto
de tarefas periódicas agendáveis pelo algoritmo RMS, essa premissa requer
que se execute obrigatoriamente a tarefa periódica de mais alta prioridade e
que se encontre pronta para ser executada (liberada). Se a referida tarefa adiar
sua execução quando, por outro lado, poderia executar imediatamente, então
há a possibilidade de que uma tarefa de menor prioridade perca o seu prazo
limite, mesmo sendo o conjunto agendável a princípio. A preservação da
capacidade de computação do Servidor Esporádico (assim como do Servidor
Adiável) quando não há evento pendente é equivalente ao processo de adiar a
execução de uma tarefa periódica de alta prioridade, fazendo com que o SS
não atenda à premissa supracitada. Entretanto, o método de restauração do
86
SS compensa qualquer eventual adiamento de execução pelo fato da
restauração da capacidade consumida também ser adiada, o que não ocorre
com o DS que efetua a restauração plena independentemente do instante de
tempo em que ocorre o consumo.
O limite superior de utilização do processador que garante a agendabilidade do
conjunto corresponde ao mesmo do algoritmo PE, dado por:
(2.40)
De forma semelhante aos demais servidores, obtém–se o valor da máxima
utilização periódica para uma quantidade muito grande de tarefas (N→ ):
(2.41)
Vale ressaltar que a Equação 2.40 é equivalente ao teste RMS (LIU e
LAYLAND, 1973) considerando–se a tarefa servidora indistintamente como
uma tarefa periódica ordinária (neste caso N contabiliza a tarefa servidora).
No caso do DS e do PE, a análise da garantia de agendabilidade do conjunto
periódico bem como do cumprimento do prazo limite da tarefa aperiódica
(esporádica) são possíveis apenas sob certas condições restritivas adicionais
dadas em 2.28, o que não ocorre no caso do SS, cujos prazos limites são
garantidos unicamente sob as condições dadas pela teoria RMS.
A Tabela 2.5 contém um conjunto formado por 2 tarefas periódicas e uma
esporádica, conjunto este a ser agendado por meio do algoritmo SS.
87
Tabela 2.5 – Exemplo de conjunto de tarefas com Servidor Esporádico.
Tarefa
(i) T. Comput.
(Ci) Período
(Ti) Prioridade
(Pi) Utiliz.
(Ui)
1 25 80 1 0.31
S 8 30 2 0.27
2 4 20 3 0.20
0.78
Note–se que este é o mesmo conjunto de tarefas utilizado no exemplo do RMS
(Tabela A.3) porém com a tarefa periódica 2 substituída por uma tarefa
esporádica com mesmo tempo de computação e período (do servidor). O
conjunto é agendável pelo RMS (U 0.78).
A execução do respectivo sistema é representada na Linha de Tempo da
Figura 2.11. No instante t = 0 a capacidade do servidor é restaurada ao seu
valor máximo e assim permanece até o instante t = 5 quando ocorre o primeiro
evento esporádico. Como a prioridade do SS é maior que a da tarefa 1 em
execução neste instante, o evento é imediatamente atendido mediante a
preempção de 1 e a execução da tarefa esporádica relacionada. Neste mesmo
instante de tempo é determinado o valor do instante de restauração da
capacidade do servidor (RTS = 35), igual ao instante de início de execução da
tarefa esporádica somado ao período do servidor (TS = 30).
88
A computação completa da tarefa esporádica (C2 = 8) se dá em t = 13 quando
toda a capacidade do servidor é exaurida, vindo esta a ser restaurada em
RTS = 35, instante no qual um segundo evento é parcialmente atendido
(computadas 5 unidades de tempo) até o instante t = 40 quando o servidor é
“preemptado” pela tarefa prioritária 1. Em t = 35 o valor de RTS é ajustado para
65, instante de tempo no qual ocorrerá a próxima restauração. A tarefa
esporádica termina em t = 47, após retomar a execução. Em t = 65 ocorre nova
restauração trazendo novamente o servidor à sua máxima capacidade, assim
permanecendo uma vez que não ocorre outro evento no intervalo de tempo
analisado.
Tempo
Execução
Tarefa 1
Tarefa S
Tarefa 2
Capacid. Servidor
8.0
Servidor Esporádico: Tempo de Computação=1, Período=5
1
2 1
0 10 20 30 40 50 60 70 80 90 100
Figura 2.11 – Linha de Tempo com Servidor Esporádico.
89
O Servidor Esporádico também pode ser utilizado nos casos em que o prazo
limite da tarefa esporádica é inferior ao MIT e, conseqüentemente, inferior ao
período do servidor. Porém um esquema diferente de atribuição de prioridades
bem como outra análise e Teste de Agendabilidade diferentes do RMS são
necessários para tal (ressaltando que no RMS parte–se do pressuposto que o
prazo limite é igual ao período). Neste caso, a prioridade do servidor deve ser
atribuída de acordo com Agendamento a Prazos Monotônicos (Deadline
Monotonic Scheduling – DMS).
91
3 DESENVOLVIMENTO
3.1 HRTSim – Simulador em Tempo Real Rígido
3.1.1 Introdução
O Simulador em Tempo Real Rígido (Hard Real Time Simulator – HRTSim) é
uma ferramenta de software projetada e desenvolvida pelo autor com uma
metodologia orientada a objetos com a finalidade de dar suporte a este
trabalho, permitindo o estudo do agendamento e execução (despachamento)
de um conjunto de tarefas periódicas com prazos rígidos na presença de uma
tarefa aperiódica ou esporádica por meio de diferentes políticas de
agendamento / despachamento. Sua necessidade adveio da constatação da
indisponibilidade de uma ferramenta comercial ou acadêmica com a
flexibilidade e recursos adequados para tal fim. Por meio desta ferramenta é
possível simular a execução de um Sistema em Tempo Real e observar
graficamente seu comportamento ao longo de um intervalo de tempo pré–
definido, além de fornecer análises a priori (testes de agendabilidade) e a
posteriori da execução (análises dos prazos e estatísticas).
Alguns dos principais recursos implementados:
Atribuição manual de prioridades.
Atribuição de prioridades RMS.
Teste de Agendabilidade RMS.
Teste de Agendabilidade por meio de análise de tempos de resposta.
Despachamento com execução preemptiva baseada em prioridades.
Suporte para agendamento e despachamento misto com algoritmos:
92
o Serviço em Segundo Plano.
o Servidor de Varredura.
o Servidor Esporádico.
Instantes de ocorrência dos eventos aperiódicos gerados de maneira
aleatória ou definidos manualmente pelo usuário.
Visualização gráfica da execução das tarefas:
o Gráficos de Linha de Tempo.
o Curvas de capacidade dos servidores periódicos.
Relatório de execução contendo:
o Análise a priori (agendabilidade).
o Andamento da simulação.
o Análise a posteriori (resultados e estatísticas).
Projetos podem ser salvos e recuperados de arquivos em disco
O núcleo do simulador é formado por uma série de objetos que modelam os
principais elementos constituintes de um RTS:
Tarefas.
Agendador.
Despachador.
Eventos.
Estes e demais objetos, codificados na linguagem C#, encontram–se
representados nos diagramas de classes constantes no APÊNDICE B .
93
A metodologia orientada a objetos permite que os modelos sejam mais
facilmente reutilizados em outros programas; e sejam, principalmente,
extensíveis, permitindo uma relativa facilidade de incorporação de novos
elementos e de refinamento dos modelos e algoritmos existentes. Maiores
detalhes e a teoria de operação da ferramenta se encontram no APÊNDICE C .
3.2 Estudo de Caso: Computador de Missão
Modernamente, todos os veículos aeroespaciais são comandados e
controlados por computadores interligados por sistemas de comunicação. Um
exemplo importante para este estudo é a aviônica de uma aeronave de
combate típica, constituída por um conjunto de equipamentos e computadores
especializados e interconectados entre si, geralmente por mais de um
barramento de comunicação por questão de redundância. Estes dispositivos
são controlados pelo Computador de Missão (Mission Control Computer –
MCC) que normalmente também acumula a função de controlador dos
barramentos. Dentre as funções normalmente desempenhadas pelo MCC
pode–se elencar: navegação, controle de sensores, mira de armamentos,
lançamento de bombas, gerenciamento de telas (displays) e controles, etc.
Demais funções como processamento de sinais de radar, navegação inercial e
por satélites, aviso de ameaças, gerenciamento de armas e cargas externas,
controle de vôo, dados anemométricos e outros ficam a cargo dos demais
computadores aviônicos especializados que interagem com o MCC. Para efeito
de análise e simulação utilizar–se–á o exemplo realístico de um MCC
uniprocessado, que é parte de um sistema aviônico hipotético cujas
especificações são compatíveis com as demandas das atuais aeronaves de
combate (LOCKE et al., 1990), no qual o conjunto de 15 tarefas apresentado
na Tabela 3.1 executa preemptivamente.
94
Tabela 3.1 – Exemplo de um conjunto de tarefas típicas de um MCC.
Tarefa
Tipo Comput. (Ci)[ms]
Período (Ti)[ms]
Prior. (Pi)
Utiliz. (Ui)
1 – Weapon Release Per. 1 10 15 0.100
2 – Radar Tracking Per. 2 40 14 0.050
3 – Target Tracking Per. 4 40 13 0.100
4 – Target Sweetening Esp. 2 40 12 0.050
5 – HOTAS Bomb Button Esp. 1 40 11 0.025
6 – Aircraft Flight Data Per. 8 50 10 0.160
7 – HUD Display Per. 6 50 9 0.120
8 – MPD Tactical Display Per. 8 50 8 0.160
9 – Steering Per. 6 80 7 0.075
10 – Weapon Trajectory Per. 7 100 6 0.070
11 – Threat Response Display Esp. 3 100 5 0.030
12 – AUTO/CCIP Toggle Esp. 1 200 4 0.005
13 – Poll RWR Per. 2 200 3 0.010
14 – Reinitiate Trajectory Esp. 6 400 2 0.015
15 – Periodic BIT Per. 5 1000 1 0.005
0.975
Fonte: Adaptado de Dodd (2006), Locke et al. (1990).
O conjunto é formado por tarefas periódicas e esporádicas (destacadas em
negrito na Tabela 3.1), com parâmetros temporais especificados em
milissegundos. São seus pressupostos:
Tarefas executam em um único processador (MCC uniprocessado).
Tarefas independentes (não há sincronização entre tarefas ou bloqueio
de recursos).
95
Prazos rígidos.
Execução preemptiva.
Prazos limites iguais aos períodos e iguais ao MIT.
Atribuição de prioridades RMS.
3.3 Verificação do HRTSim Contra o Estudo de Caso do MCC
Para efeito de verificação do funcionamento geral do programa, principalmente
no que se relaciona com os algoritmos de atribuição de prioridades e Teste de
Agendabilidade RMS, análise de tempo de resposta, despachamento e
execução das tarefas, foi tomado o estudo de caso do Computador de Missão
como referência. O conjunto de tarefas com sua especificação original (Tabela
3.1), considerando–se todas as tarefas periódicas, agendado e executado pelo
HRTSim com política RMS, gerou resultados que foram comparados com
aqueles obtidos por Dodd (2006).
O conjunto especificado possui utilização do processador igual a:
(3.1)
Enquanto o limite superior de utilização do processador para N = 15 tarefas, de
acordo com a teoria RMS, corresponde a:
(3.2)
96
Fica evidente que o conjunto não passa no teste RMS de agendabilidade uma
vez que a utilização do processador (U = 0.975) é superior ao limite de
agendabilidade (ULUB(15) = 0.709).
A análise de tempo de resposta7 (2.8) obtida por Dodd (2006) fornece os
seguintes valores8:
(R1 = 1) (D1 = 10) (R2 = 3) (D2 = 40)
(R3 = 7) (D3 = 40) (R4 = 9) (D4 = 40)
(R5 = 10) (D5 = 40) (R6 = 19) (D6 = 50)
(R7 = 26) (D7 = 50) (R8 = 35) (D8 = 50)
(R9 = 76) (D9 = 80) (R10 = 100) (D10 = 100)
(R11 = 146) > (D11 = 100)
Confirma–se então, agora mediante a condição necessária e suficiente, que o
conjunto não é agendável, pois a décima primeira tarefa (destacada em
negrito) apresenta tempo de resposta (R11 = 146) superior ao seu prazo limite
(D11 = 100).
Este conjunto de tarefas foi simulado no HRTSim e os resultados da simulação
encontram–se no item 4.1, incluindo o gráfico de Linha de Tempo gerado pelo
programa que ilustra o comportamento de execução das tarefas
As especificações originais do conjunto de tarefas foram modificadas (Tabela
3.2) de forma a torná–lo agendável (o tempo de computação C6 da tarefa τ6 –
Aircraft Flight Data foi reduzido de 8 ms para 6 ms). Note–se a ligeira redução
na utilização do processador que passa de U = 0.975 para U = 0.935, o que ainda
não garante agendabilidade RMS (ULUB(15) = 0.709). No entanto, a análise de
tempo de resposta comprova, com as novas especificações, a condição de
7 Dodd (2006) apresenta apenas os valores dos tempos de resposta das primeiras onze
tarefas. 8 Locke et al. (1990).originalmente considera alguns prazos (Tarefas τ1 e τ15) inferiores aos
respectivos períodos para a análise. No presente trabalho, foram considerados os prazos iguais aos períodos das tarefas, rigorosamente de acordo com a teoria RMS.
97
agendabilidade, como pode ser observado nos resultados da nova simulação
(item 4.2).
Tabela 3.2 – Conjunto de tarefas MCC com especificações modificadas.
Tarefa
Tipo Comput. (Ci)[ms]
Período (Ti)[ms]
Prior. (Pi)
Utiliz. (Ui)
1 – Weapon Release Per. 1 10 15 0.100
2 – Radar Tracking Per. 2 40 14 0.050
3 – Target Tracking Per. 4 40 13 0.100
4 – Target Sweetening Esp. 2 40 12 0.050
5 – HOTAS Bomb Button Esp. 1 40 11 0.025
6 – Aircraft Flight Data Per. 6 50 10 0.120
7 – HUD Display Per. 6 50 9 0.120
8 – MPD Tactical Display Per. 8 50 8 0.160
9 – Steering Per. 6 80 7 0.075
10 – Weapon Trajectory Per. 7 100 6 0.070
11 – Threat Response Display Esp. 3 100 5 0.030
12 – AUTO/CCIP Toggle Esp. 1 200 4 0.005
13 – Poll RWR Per. 2 200 3 0.010
14 – Reinitiate Trajectory Esp. 6 400 2 0.015
15 – Periodic BIT Per. 5 1000 1 0.005
0.935
Fonte: Adaptado de Dodd (2006), Locke et al. (1990).
A comparação entre os resultados obtidos nas simulações e o exemplo de
referência (com os respectivos embasamentos e cálculos teóricos) serve como
critério de avaliação da operação do aplicativo no que se refere ao
agendamento RMS, algoritmo de análise de tempo de resposta e
despachamento de tarefas periódicas.
98
Todas as demais simulações seguem utilizando o conjunto de tarefas
modificado, com a agendabilidade das tarefas periódicas garantidas.
3.4 Algoritmo com Serviço em Segundo Plano Aplicado ao MCC
O conjunto de tarefas modificado do MCC, sujeito ao agendamento RMS, com
suporte a tarefas aperiódicas pelo método do Serviço em Segundo Plano, cujos
instantes de ocorrência dos eventos estão definidos na Tabela 3.3 foi
executado no simulador fornecendo os resultados apresentados no item 4.3.
Tabela 3.3 – Instantes dos eventos.
Tarefa
Instante dos Eventos (ms)
4 – Target Sweetening 1, 45, 100, 180, 250, 300, 500, 750, 800, 950
5 – HOTAS Bomb Button 1, 50, 110, 150, 200, 350, 400, 700, 780, 820, 900, 950
11 – Threat Response Display 5, 105, 230, 350, 500, 680, 800, 980
12 – AUTO/CCIP Toggle 5, 210, 450, 810
14 – Reinitiate Trajectory 10, 450, 935
Note–se que todos os eventos respeitam o intervalo de tempo entre liberações
(MIT) e que o BS não fornece garantias de atendimento dos prazos limites
aperiódicos.
3.5 Algoritmo Servidor de Varredura Aplicado ao MCC
Utilizando os mesmos eventos (Tabela 3.3) o sistema foi simulado porém com
suporte aperiódico fornecido pelo algoritmo Servidor de Varredura. Nestas
99
condições também não há garantias dos prazos limites aperiódicos pois,
embora as tarefas periódicas (incluindo as servidoras) sejam agendáveis, a
condição estabelecida pela Equação 2.24 não é satisfeita para nenhuma das
tarefas aperiódicas. Os resultados encontram–se no item 4.4.
Visando garantir a agendabilidade das tarefas esporádicas foram definidos
outros instantes de ocorrência dos eventos (Tabela 3.2), desta vez atendendo à
condição de garantia dos prazos limites aperiódicos para o PS (Equação 2.24).
Tabela 3.4 – Instantes dos eventos: Servidor de Varredura (agendável).
Tarefa
Instante dos Eventos (ms)
4 – Target Sweetening 1, 100, 180, 300, 500, 750, 950
5 – HOTAS Bomb Button 1, 110, 200, 350, 700, 780, 900
11 – Threat Response Display 5, 230, 500, 800
12 – AUTO/CCIP Toggle 5, 450
14 – Reinitiate Trajectory 10, 935
Os resultados da simulação sob tais condições encontram–se no item 4.5.
3.6 Algoritmo Servidor Esporádico Aplicado ao Estudo de Caso do MCC
Para os instantes de ocorrência de eventos fornecidos na Tabela 3.3 o conjunto
de tarefas modificado do MCC, sujeito ao agendamento RMS com suporte a
tarefas aperiódicas pelo método do Servidor Esporádico, foi executado no
simulador fornecendo os resultados apresentados no item 4.6. Nestas
condições o sistema é agendável com garantias tanto dos prazos limites
periódicos como aperiódicos.
101
4 SIMULAÇÕES E RESULTADOS
Todas as simulações foram feitas com o HRTSim utilizando o conjunto de
tarefas do estudo de caso do Computador de Missão (MCC) agendado
mediante a política RMS de atribuição de prioridades. Iniciando–se a execução
no instante crítico das tarefas periódicas em t = 0, o intervalo de tempo total de
simulação de 0 a 999 unidades de tempo (milissegundos) corresponde a uma
Linha de Tempo de 1000 pontos, suficiente para cobrir no mínimo um período
completo da tarefa com maior período (menos prioritária). Os gráficos de Linha
de Tempo e de capacidade dos servidores periódicos cobrem o intervalo de
tempo de 0 a 400 ms de forma a não ficarem demasiadamente densos
(visualmente carregados).
4.1 MCC Com Especificações Originais – Todas as Tarefas Periódicas, Conjunto Não Agendável
Validação do agendamento RMS do HRTSim utilizando como referência o
conjunto de tarefas do MCC fornecido na Tabela 3.1 com as especificações
originais (DODD, 2006) considerando–se todas as tarefas periódicas e prazos
limites iguais aos períodos. Nessas condições o conjunto de tarefas não é
agendável (RMS e RTA).
Segue a listagem com o resultado da simulação:
***** Round 1 (11/17/2008 10:26:59 AM) ********************************************* Project file: project.rts Description: MCC original specification, RMS, non feasible, all periodics Program Version 1.0.3243.18509 -Priority assignment is RMS. -Processor utilization for the task set: 0.975 -RMS utilization bound (Liu & Layland, 1973): 0.7094119 -Periodic task set is *** NOT FEASIBLE *** (sufficient, not necessary utilization based test). -Response time analysis for periodic tasks (Hart, 1984, Joseph & Pandya, 1986) for Task(T,D,C,P): T1(10,10,1,15) - Weapon Release: (R=1) <= (D=10) : Ok. T2(40,40,2,14) - Radar Tracking: (R=3) <= (D=40) : Ok. T3(40,40,4,13) - Target Tracking: (R=7) <= (D=40) : Ok. T4(40,40,2,12) - Target Sweetening: (R=9) <= (D=40) : Ok.
102
T5(40,40,1,11) - HOTAS Bomb Button: (R=10) <= (D=40) : Ok. T6(50,50,8,10) - Aircraft Flight Data: (R=19) <= (D=50) : Ok. T7(50,50,6,9) - HUD Display: (R=26) <= (D=50) : Ok. T8(50,50,8,8) - MPD Tactical Display: (R=35) <= (D=50) : Ok. T9(80,80,6,7) - Steering: (R=76) <= (D=80) : Ok. T10(100,100,7,6) - Weapon Trajectory: (R=100) <= (D=100) : Ok. T11(100,100,3,5) - Threat Response Display: (R=146) > (D=100) : *** DEADLINE WILL BE MISSED ***. T12(200,200,1,4) - AUTO/CCIP Toggle: (R=150) <= (D=200) : Ok. T13(200,200,2,3) - Poll RWR: (R=194) <= (D=200) : Ok. T14(400,400,6,2) - Reinitiate Trajectory: (R=200) <= (D=400) : Ok. T15(1000,1000,5,1) - Periodic BIT: (R=393) <= (D=1000) : Ok. -Periodic task set is *** NOT FEASIBLE *** (sufficient and necessary response time based test). STARTING SIMULATION... -Time interval: 0 - 999. -Simulation started at critical instant. t=100ms: Task T11 - Deadline missed t=500ms: Task T11 - Deadline missed t=900ms: Task T11 - Deadline missed Total idle time: 28 SIMULATION FINISHED. SIMULATION ANALYSIS AND STATISTICS: T1 - Weapon Release - Releases: 100, Response time: 1 max, 1 mov ave - Deadlines missed: none. T2 - Radar Tracking - Releases: 25, Response time: 3 max, 3 mov ave - Deadlines missed: none. T3 - Target Tracking - Releases: 25, Response time: 7 max, 7 mov ave - Deadlines missed: none. T4 - Target Sweetening - Releases: 25, Response time: 9 max, 9 mov ave - Deadlines missed: none. T5 - HOTAS Bomb Button - Releases: 25, Response time: 10 max, 10 mov ave - Deadlines missed: none. T6 - Aircraft Flight Data - Releases: 20, Response time: 19 max, 10 mov ave - Deadlines missed: none. T7 - HUD Display - Releases: 20, Response time: 26 max, 22 mov ave - Deadlines missed: none. T8 - MPD Tactical Display - Releases: 20, Response time: 35 max, 34 mov ave - Deadlines missed: none. T9 - Steering - Releases: 13, Response time: 76 max, 34 mov ave - Deadlines missed: none. T10 - Weapon Trajectory - Releases: 10, Response time: 100 max, 63 mov ave - Deadlines missed: none. T11 - Threat Response Display - Releases: 7, Response time: 146 max, 122 mov ave - Deadlines missed: 100 500 900 . T12 - AUTO/CCIP Toggle - Releases: 5, Response time: 147 max, 128 mov ave - Deadlines missed: none. T13 - Poll RWR - Releases: 5, Response time: 149 max, 130 mov ave - Deadlines missed: none. T14 - Reinitiate Trajectory - Releases: 3, Response time: 197 max, 173 mov ave - Deadlines missed: none. T15 - Periodic BIT - Releases: 1, Response time: 389 max, 195 mov ave - Deadlines missed: none.
103
Utilização do processador pelo conjunto de tarefas e o valor do limite de
utilização agendável calculados pelo HRTSim:
(4.1)
(4.2)
Análise de tempo de resposta do conjunto de tarefas determinado pelo
HRTSim:
(R1 = 1) (D1 = 10) (R2 = 3) (D2 = 40)
(R3 = 7) (D3 = 40) (R4 = 9) (D4 = 40)
(R5 = 10) (D5 = 40) (R6 = 19) (D6 = 50)
(R7 = 26) (D7 = 50) (R8 = 35) (D8 = 50)
(R9 = 76) (D9 = 80) (R10 = 100) (D10 = 100)
(R11 = 146) > (D11 = 100) (R12 = 150) (D12 = 200)
(R13 = 194) (D13 = 200) (R14 = 200) (D14 = 400)
(R15 = 393) (D15 = 1000)
A simulação deste conjunto de tarefas no HRTSim fornece os mesmos
resultados observados no estudo de caso original (DODD, 2006), tanto na
análise RMS como na RTA.
O gráfico de Linha de Tempo gerado pelo programa (Figura 4.1) corresponde
ao obtido no trabalho de origem9 (Figura 4.2). No primeiro fica claro o
descumprimento do prazo limite (em t = 100 ms) da tarefa esporádica τ11 –
Threat Response Display, conforme previsto pela análise de tempo de resposta
na qual foi determinado o tempo de resposta R11 = 146 ms, também observado
no gráfico.
9 Dodd (2006) ordena as tarefas no gráfico de Linha de Tempo em seqüência invertida
104
Figura 4.1 – Linha de Tempo do MCC com todas as tarefas periódicas, não agendável.
105
Figura 4.2 – Linha de Tempo de referência do MCC (Rate–monotonic scheduling of the generic avionics mission system tasks). Fonte: Dodd (2006).
106
São constatados outros dois descumprimentos de prazo limite (t = 500 ms e
t = 900 ms) além do primeiro ocorrido em t = 100 ms durante os 1000 ms de
simulação (não ilustrados do gráfico que cobre apenas os primeiros 400 ms).
4.2 MCC Com Especificações Modificadas – Todas as Tarefas Periódicas, Conjunto Agendável
Validação do agendamento RMS do HRTSim utilizando como referência o
conjunto de tarefas do MCC fornecido na Tabela 3.2, na qual as especificações
originais foram modificadas (tempo de computação da tarefa τ6 – Aircraft Flight
Data – reduzido de 8 ms para 6 ms).
Segue a listagem com o resultado da simulação:
***** Round 2 (11/17/2008 10:28:20 AM) ********************************************* Project file: MCC2_AllPeriodicsCheck_Feasible.rts Description: MCC modified specification, RMS, feasible, all periodics Program Version 1.0.3243.18509 -Priority assignment is RMS. -Processor utilization for the task set: 0.9349999 -RMS utilization bound (Liu & Layland, 1973): 0.7094119 -Periodic task set is *** NOT FEASIBLE *** (sufficient, not necessary utilization based test). -Response time analysis for periodic tasks (Hart, 1984, Joseph & Pandya, 1986) for Task(T,D,C,P): T1(10,10,1,15) - Weapon Release: (R=1) <= (D=10) : Ok. T2(40,40,2,14) - Radar Tracking: (R=3) <= (D=40) : Ok. T3(40,40,4,13) - Target Tracking: (R=7) <= (D=40) : Ok. T4(40,40,2,12) - Target Sweetening: (R=9) <= (D=40) : Ok. T5(40,40,1,11) - HOTAS Bomb Button: (R=10) <= (D=40) : Ok. T6(50,50,6,10) - Aircraft Flight Data: (R=17) <= (D=50) : Ok. T7(50,50,6,9) - HUD Display: (R=24) <= (D=50) : Ok. T8(50,50,8,8) - MPD Tactical Display: (R=33) <= (D=50) : Ok. T9(80,80,6,7) - Steering: (R=39) <= (D=80) : Ok. T10(100,100,7,6) - Weapon Trajectory: (R=79) <= (D=100) : Ok. T11(100,100,3,5) - Threat Response Display: (R=99) <= (D=100) : Ok. T12(200,200,1,4) - AUTO/CCIP Toggle: (R=100) <= (D=200) : Ok. T13(200,200,2,3) - Poll RWR: (R=146) <= (D=200) : Ok. T14(400,400,6,2) - Reinitiate Trajectory: (R=192) <= (D=400) : Ok. T15(1000,1000,5,1) - Periodic BIT: (R=197) <= (D=1000) : Ok. -Periodic task set is feasible (sufficient and necessary response time based test). STARTING SIMULATION... -Time interval: 0 - 999. -Simulation started at critical instant. Total idle time: 59 SIMULATION FINISHED.
107
SIMULATION ANALYSIS AND STATISTICS: T1 - Weapon Release - Releases: 100, Response time: 1 max, 1 mov ave - Deadlines missed: none. T2 - Radar Tracking - Releases: 25, Response time: 3 max, 3 mov ave - Deadlines missed: none. T3 - Target Tracking - Releases: 25, Response time: 7 max, 7 mov ave - Deadlines missed: none. T4 - Target Sweetening - Releases: 25, Response time: 9 max, 9 mov ave - Deadlines missed: none. T5 - HOTAS Bomb Button - Releases: 25, Response time: 10 max, 10 mov ave - Deadlines missed: none. T6 - Aircraft Flight Data - Releases: 20, Response time: 17 max, 8 mov ave - Deadlines missed: none. T7 - HUD Display - Releases: 20, Response time: 24 max, 20 mov ave - Deadlines missed: none. T8 - MPD Tactical Display - Releases: 20, Response time: 33 max, 32 mov ave - Deadlines missed: none. T9 - Steering - Releases: 13, Response time: 39 max, 27 mov ave - Deadlines missed: none. T10 - Weapon Trajectory - Releases: 10, Response time: 79 max, 52 mov ave - Deadlines missed: none. T11 - Threat Response Display - Releases: 10, Response time: 99 max, 63 mov ave - Deadlines missed: none. T12 - AUTO/CCIP Toggle - Releases: 5, Response time: 100 max, 95 mov ave - Deadlines missed: none. T13 - Poll RWR - Releases: 5, Response time: 146 max, 126 mov ave - Deadlines missed: none. T14 - Reinitiate Trajectory - Releases: 3, Response time: 192 max, 168 mov ave - Deadlines missed: none. T15 - Periodic BIT - Releases: 1, Response time: 197 max, 99 mov ave - Deadlines missed: none.
Utilização do processador pelo conjunto de tarefas e o valor do limite de
utilização agendável calculados pelo programa:
(4.1)
(4.2)
Análise de tempo de resposta do conjunto de tarefas (análise a priori feita pelo
HRTSim):
108
(R1 = 1) (D1 = 10) (R2 = 3) (D2 = 40)
(R3 = 7) (D3 = 40) (R4 = 9) (D4 = 40)
(R5 = 10) (D5 = 40) (R6 = 17) (D6 = 50)
(R7 = 24) (D7 = 50) (R8 = 33) (D8 = 50)
(R9 = 39) (D9 = 80) (R10 = 79) (D10 = 100)
(R11 = 99) (D11 = 100) (R12 = 100) (D12 = 200)
(R13 = 146) (D13 = 200) (R14 = 192) (D14 = 400)
(R15 = 197) (D15 = 1000)
Apesar de o conjunto continuar não agendável pelo teste RMS, agora a análise
de tempo de resposta garante condição necessária e suficiente para o
agendamento do conjunto, o que é confirmado pela simulação do
despachamento e pela análise a posteriori, situação observada no gráfico de
Linha de Tempo correspondente (Figura 4.3). Com a redução da carga sobre o
processador, nenhum prazo limite foi comprometido durante toda a simulação
que engloba um intervalo de tempo igual ao maior período a partir do instante
crítico, confirmando a agendabilidade do sistema na configuração corrente.
109
Figura 4.3 – Linha de Tempo do MCC com todas as tarefas periódicas, agendável.
110
4.3 MCC Com Especificações Modificadas – Serviço em Segundo Plano, Conjunto Periódico Agendável, Sem Garantias Aperiódicas
A simulação do conjunto de Tarefas do MCC modificado (Tabela 3.2) com
garantia de agendamento periódico e instantes dos eventos respeitando o MIT
(Tabela 3.3) resultou em perdas significativas de prazos limites das tarefas
aperiódicas (sem nenhuma perda periódica) como esperado, uma vez que o
algoritmo de Serviço em Segundo Plano não fornece condições intrínsecas de
garanti–los em quaisquer circunstâncias.
Segue a listagem com o resultado da simulação:
***** Round 1 (11/18/2008 7:16:58 AM) ********************************************* Project file: MCC3_BS_PeriodicsFeasible.rts Description: CMM modified specification, RMS, periodics feasible, Background Servicing, no aperiodics guarantee Program Version 1.0.3244.13093 -Priority assignment is RMS. -Using Background Servicing for aperiodic tasks (no aperiodic deadlines guarantee). -Aperiodic tasks will not be considered in schedulability tests and response time analysis. -Processor utilization for the task set: 0.81 -RMS utilization bound (Liu & Layland, 1973): 0.7177346 -Periodic task set is *** NOT FEASIBLE *** (sufficient, not necessary utilization based test). -Response time analysis for periodic tasks (Hart, 1984, Joseph & Pandya, 1986) for Task(T,D,C,P): T1(10,10,1,10) - Weapon Release: (R=1) <= (D=10) : Ok. T2(40,40,2,9) - Radar Tracking: (R=3) <= (D=40) : Ok. T3(40,40,4,8) - Target Tracking: (R=7) <= (D=40) : Ok. T4(40,40,2,0) - Target Sweetening: (R=0) : Task not included in the analysis. T5(40,40,1,0) - HOTAS Bomb Button: (R=0) : Task not included in the analysis. T6(50,50,6,7) - Aircraft Flight Data: (R=14) <= (D=50) : Ok. T7(50,50,6,6) - HUD Display: (R=20) <= (D=50) : Ok. T8(50,50,8,5) - MPD Tactical Display: (R=29) <= (D=50) : Ok. T9(80,80,6,4) - Steering: (R=36) <= (D=80) : Ok. T10(100,100,7,3) - Weapon Trajectory: (R=50) <= (D=100) : Ok. T11(100,100,3,0) - Threat Response Display: (R=0) : Task not included in the analysis. T12(200,200,1,0) - AUTO/CCIP Toggle: (R=0) : Task not included in the analysis. T13(200,200,2,2) - Poll RWR: (R=75) <= (D=200) : Ok. T14(400,400,6,0) - Reinitiate Trajectory: (R=0) : Task not included in the analysis. T15(1000,1000,5,1) - Periodic BIT: (R=80) <= (D=1000) : Ok. -Periodic task set is feasible (sufficient and necessary response time based test). -Aperiodic task set *** HAS NO GUARANTEE *** (sufficient, not necessary utilization based test). -Aperiodic task set deadlines are guaranteed (sufficient and necessary response time based test). STARTING SIMULATION... -Time interval: 0 - 999. -Simulation started at critical instant.
111
t=41ms: Task T4 - Deadline missed t=41ms: Task T5 - Deadline missed t=85ms: Task T4 - Deadline missed t=90ms: Task T5 - Deadline missed t=105ms: Task T11 - Deadline missed t=140ms: Task T4 - Deadline missed t=240ms: Task T5 - Deadline missed t=340ms: Task T4 - Deadline missed t=440ms: Task T5 - Deadline missed t=540ms: Task T4 - Deadline missed t=740ms: Task T5 - Deadline missed t=840ms: Task T4 - Deadline missed t=860ms: Task T5 - Deadline missed t=940ms: Task T5 - Deadline missed t=990ms: Task T4 - Deadline missed Total idle time: 109 SIMULATION FINISHED. SIMULATION ANALYSIS AND STATISTICS: T1 - Weapon Release - Releases: 100, Response time: 1 max, 1 mov ave - Deadlines missed: none. T2 - Radar Tracking - Releases: 25, Response time: 3 max, 3 mov ave - Deadlines missed: none. T3 - Target Tracking - Releases: 25, Response time: 7 max, 7 mov ave - Deadlines missed: none. T4 - Target Sweetening - Releases: 10, Response time: 149 max, 56 mov ave - Deadlines missed: 41 85 140 340 540 840 990 . T5 - HOTAS Bomb Button - Releases: 12, Response time: 145 max, 43 mov ave - Deadlines missed: 41 90 240 440 740 860 940 . T6 - Aircraft Flight Data - Releases: 20, Response time: 14 max, 8 mov ave - Deadlines missed: none. T7 - HUD Display - Releases: 20, Response time: 20 max, 18 mov ave - Deadlines missed: none. T8 - MPD Tactical Display - Releases: 20, Response time: 29 max, 29 mov ave - Deadlines missed: none. T9 - Steering - Releases: 13, Response time: 36 max, 24 mov ave - Deadlines missed: none. T10 - Weapon Trajectory - Releases: 10, Response time: 50 max, 42 mov ave - Deadlines missed: none. T11 - Threat Response Display - Releases: 8, Response time: 137 max, 31 mov ave - Deadlines missed: 105 . T12 - AUTO/CCIP Toggle - Releases: 4, Response time: 133 max, 57 mov ave - Deadlines missed: none. T13 - Poll RWR - Releases: 5, Response time: 75 max, 62 mov ave - Deadlines missed: none. T14 - Reinitiate Trajectory - Releases: 3, Response time: 90 max, 27 mov ave - Deadlines missed: none. T15 - Periodic BIT - Releases: 1, Response time: 80 max, 40 mov ave - Deadlines missed: none.
A Linha de Tempo evidencia as diversas perdas dos prazos limites aperiódicos.
112
Figura 4.4 – Linha de Tempo do MCC com conjunto periódico agendável, Serviço em Segundo Plano, sem garantias aperiódicas.
113
Os poucos prazos limites aperiódicos cumpridos resultaram em grandes
tempos de resposta haja vista a relativa alta utilização do processador por parte
das tarefas periódicas (UP = 0.81), relegando poucas oportunidades de
execução às tarefas aperiódicas (não prioritárias). Por outro lado, observa–se
uma melhora no tempo de resposta de algumas das tarefas periódicas,
principalmente as de menor prioridade, se comparado com o resultado do
agendamento considerando–se todas as tarefas como sendo periódicas (4.2).
Isso decorre do fato de existir mais tempo de processamento disponível ao
atendimento periódico (no BS não há reserva de tempo de processamento para
as tarefas aperiódicas, ficando toda a capacidade disponível às tarefas
periódicas e apenas a sobra desta é utilizada ao processamento não
periódico). Note–se que as tarefas aperiódicas não entram no cômputo da
utilização do processador para efeito dos testes de agendabilidade.
4.4 MCC Com Especificações Modificadas – Servidor de Varredura, Conjunto Periódico Agendável, Sem Garantias Aperiódicas
O conjunto de tarefas do MCC modificado (Tabela 3.2) com instantes dos
eventos da Tabela 3.3 e tarefas aperiódicas agendadas por meio do Servidor
de Varredura apresenta os resultados dados pela listagem a seguir:
***** Round 2 (11/18/2008 7:26:19 AM) ********************************************* Project file: MCC4_PS_PeriodicsFeasible.rts Description: CMM modified specification, RMS, periodics feasible, Poling Server, no aperio dics guarantee Program Version 1.0.3244.13171 -Priority assignment is RMS. -Using Polling Server for aperiodic tasks (aperiodic deadlines guaranteed only when Di>2*Ti). -Processor utilization for the task set: 0.9349999 -RMS utilization bound (Liu & Layland, 1973): 0.7094119 -Periodic task set is *** NOT FEASIBLE *** (sufficient, not necessary utilization based test). -Response time analysis for periodic tasks (Hart, 1984, Joseph & Pandya, 1986) for Task(T,D,C,P): T1(10,10,1,15) - Weapon Release: (R=1) <= (D=10) : Ok. T2(40,40,2,12) - Radar Tracking: (R=6) <= (D=40) : Ok. T3(40,40,4,11) - Target Tracking: (R=10) <= (D=40) : Ok. T4(40,40,2,14) - Target Sweetening: (R=3) <= (D=40) : Ok. T5(40,40,1,13) - HOTAS Bomb Button: (R=4) <= (D=40) : Ok. T6(50,50,6,10) - Aircraft Flight Data: (R=17) <= (D=50) : Ok. T7(50,50,6,9) - HUD Display: (R=24) <= (D=50) : Ok.
114
T8(50,50,8,8) - MPD Tactical Display: (R=33) <= (D=50) : Ok. T9(80,80,6,7) - Steering: (R=39) <= (D=80) : Ok. T10(100,100,7,5) - Weapon Trajectory: (R=99) <= (D=100) : Ok. T11(100,100,3,6) - Threat Response Display: (R=75) <= (D=100) : Ok. T12(200,200,1,4) - AUTO/CCIP Toggle: (R=100) <= (D=200) : Ok. T13(200,200,2,3) - Poll RWR: (R=146) <= (D=200) : Ok. T14(400,400,6,2) - Reinitiate Trajectory: (R=192) <= (D=400) : Ok. T15(1000,1000,5,1) - Periodic BIT: (R=197) <= (D=1000) : Ok. -Periodic task set is feasible (sufficient and necessary response time based test). T4 - Aperiodic task has no guarantee under RMS (D=40) < 2*(T=40) T5 - Aperiodic task has no guarantee under RMS (D=40) < 2*(T=40) T11 - Aperiodic task has no guarantee under RMS (D=100) < 2*(T=100) T12 - Aperiodic task has no guarantee under RMS (D=200) < 2*(T=200) T14 - Aperiodic task has no guarantee under RMS (D=400) < 2*(T=400) -Aperiodic task set *** HAS NO GUARANTEE *** (sufficient, not necessary utilization based test). -Aperiodic task set *** HAS NO GUARANTEE *** (sufficient and necessary response time based test). STARTING SIMULATION... -Time interval: 0 - 999. -Simulation started at critical instant. t=41ms: Task T4 - Deadline missed t=41ms: Task T5 - Deadline missed t=105ms: Task T11 - Deadline missed t=205ms: Task T11 - Deadline missed t=205ms: Task T12 - Deadline missed t=330ms: Task T11 - Deadline missed t=410ms: Task T12 - Deadline missed t=410ms: Task T14 - Deadline missed t=850ms: Task T14 - Deadline missed Total idle time: 119 SIMULATION FINISHED. SIMULATION ANALYSIS AND STATISTICS: T1 - Weapon Release - Releases: 100, Response time: 1 max, 1 mov ave - Deadlines missed: none. T2 - Radar Tracking - Releases: 25, Response time: 6 max, 5 mov ave - Deadlines missed: none. T3 - Target Tracking - Releases: 25, Response time: 10 max, 9 mov ave - Deadlines missed: none. T4 - Target Sweetening - Releases: 10, Response time: 42 max, 12 mov ave - Deadlines missed: 41 . T5 - HOTAS Bomb Button - Releases: 12, Response time: 43 max, 18 mov ave - Deadlines missed: 41 . T6 - Aircraft Flight Data - Releases: 20, Response time: 17 max, 8 mov ave - Deadlines missed: none. T7 - HUD Display - Releases: 20, Response time: 24 max, 20 mov ave - Deadlines missed: none. T8 - MPD Tactical Display - Releases: 20, Response time: 33 max, 31 mov ave - Deadlines missed: none. T9 - Steering - Releases: 13, Response time: 39 max, 26 mov ave - Deadlines missed: none. T10 - Weapon Trajectory - Releases: 10, Response time: 80 max, 51 mov ave - Deadlines missed: none. T11 - Threat Response Display - Releases: 7, Response time: 131 max, 57 mov ave
115
- Deadlines missed: 105 205 330 . T12 - AUTO/CCIP Toggle - Releases: 3, Response time: 275 max, 196 mov ave - Deadlines missed: 205 410 . T13 - Poll RWR - Releases: 5, Response time: 96 max, 77 mov ave - Deadlines missed: none. T14 - Reinitiate Trajectory - Releases: 2, Response time: 490 max, 368 mov ave - Deadlines missed: 410 850 . T15 - Periodic BIT - Releases: 1, Response time: 100 max, 50 mov ave - Deadlines missed: none.
Embora estes resultados confirmem a agendabilidade periódica, a falta de
garantia aperiódica fica evidenciada nas diversas perdas de prazo limite,
perdas estas previstas uma vez que a condição estabelecida pela Equação
2.24, relativa à garantia dos prazos limites das tarefas aperiódicas para este
algoritmo, não é respeitada (prazo limite deve ser superior ao dobro do valor do
período do respectivo servidor). Enquanto a Figura 4.5 mostra a Linha de
Tempo para o agendamento, na qual se observam as perdas dos prazos limites
das tarefas aperiódicas, a Figura 4.6 representa a capacidade dos servidores
periódicos. Note–se que no instante inicial (t = 0), correspondente ao instante
crítico quanto todas as tarefas (incluindo servidores periódicos) são liberadas,
ocorre a restauração (ou preenchimento) de cada servidor com a máxima
capacidade (representada por uma linha vertical estreita em t = 0) que logo a
seguir são zeradas uma vez que, de acordo com a política do PS, não há
eventos pendentes. Estes ocorrendo após o referido instante, como
efetivamente ocorre na simulação, ficam pendentes até o próximo período
quando podem então ser atendidos mediante a restauração dos respectivos
servidores.
116
Figura 4.5 – Linha de Tempo do MCC com conjunto periódico agendável, Servidor de Varredura, sem garantias aperiódicas.
117
Figura 4.6 – Capacidade dos Servidores do MCC com conjunto periódico agendável, Servidor de Varredura, sem garantias aperiódicas.
118
4.5 MCC Com Especificações Modificadas – Servidor de Varredura, Conjunto Agendável
Utilizando um conjunto de eventos modificado (Tabela 3.4) criado a partir da
remoção de alguns eventos do conjunto original (Tabela 3.3) de forma que a
condição de agendabilidade aperiódica (Equação 2.24) seja atendida, o mesmo
conjunto de tarefas foi executado.
Segue a listagem com o resultado da simulação:
***** Round 5 (11/18/2008 7:56:50 AM) ********************************************* Project file: MCC5_PS_Feasible.rts Description: CMM modified specification, RMS, feasible, Polling Server Program Version 1.0.3244.13171 -Priority assignment is RMS. -Using Polling Server for aperiodic tasks (aperiodic deadlines guaranteed only when Di>2*Ti). -Processor utilization for the task set: 0.9349999 -RMS utilization bound (Liu & Layland, 1973): 0.7094119 -Periodic task set is *** NOT FEASIBLE *** (sufficient, not necessary utilization based test). -Response time analysis for periodic tasks (Hart, 1984, Joseph & Pandya, 1986) for Task(T,D,C,P): T1(10,10,1,15) - Weapon Release: (R=1) <= (D=10) : Ok. T2(40,40,2,12) - Radar Tracking: (R=6) <= (D=40) : Ok. T3(40,40,4,11) - Target Tracking: (R=10) <= (D=40) : Ok. T4(40,80,2,14) - Target Sweetening: (R=3) <= (D=80) : Ok. T5(40,80,1,13) - HOTAS Bomb Button: (R=4) <= (D=80) : Ok. T6(50,50,6,10) - Aircraft Flight Data: (R=17) <= (D=50) : Ok. T7(50,50,6,9) - HUD Display: (R=24) <= (D=50) : Ok. T8(50,50,8,8) - MPD Tactical Display: (R=33) <= (D=50) : Ok. T9(80,80,6,7) - Steering: (R=39) <= (D=80) : Ok. T10(100,100,7,5) - Weapon Trajectory: (R=99) <= (D=100) : Ok. T11(100,200,3,6) - Threat Response Display: (R=75) <= (D=200) : Ok. T12(200,400,1,4) - AUTO/CCIP Toggle: (R=100) <= (D=400) : Ok. T13(200,200,2,3) - Poll RWR: (R=146) <= (D=200) : Ok. T14(400,800,6,2) - Reinitiate Trajectory: (R=192) <= (D=800) : Ok. T15(1000,1000,5,1) - Periodic BIT: (R=197) <= (D=1000) : Ok. -Periodic task set is feasible (sufficient and necessary response time based test). -Aperiodic task set *** HAS NO GUARANTEE *** (sufficient, not necessary utilization based test). -Aperiodic task set deadlines are guaranteed (sufficient and necessary response time based test). STARTING SIMULATION... -Time interval: 0 - 999. -Simulation started at critical instant. Total idle time: 146 SIMULATION FINISHED. SIMULATION ANALYSIS AND STATISTICS: T1 - Weapon Release - Releases: 100, Response time: 1 max, 1 mov ave - Deadlines missed: none. T2 - Radar Tracking - Releases: 25, Response time: 6 max, 5 mov ave
119
- Deadlines missed: none. T3 - Target Tracking - Releases: 25, Response time: 10 max, 9 mov ave - Deadlines missed: none. T4 - Target Sweetening - Releases: 7, Response time: 42 max, 16 mov ave - Deadlines missed: none. T5 - HOTAS Bomb Button - Releases: 7, Response time: 43 max, 21 mov ave - Deadlines missed: none. T6 - Aircraft Flight Data - Releases: 20, Response time: 17 max, 8 mov ave - Deadlines missed: none. T7 - HUD Display - Releases: 20, Response time: 24 max, 20 mov ave - Deadlines missed: none. T8 - MPD Tactical Display - Releases: 20, Response time: 33 max, 31 mov ave - Deadlines missed: none. T9 - Steering - Releases: 13, Response time: 37 max, 26 mov ave - Deadlines missed: none. T10 - Weapon Trajectory - Releases: 10, Response time: 77 max, 50 mov ave - Deadlines missed: none. T11 - Threat Response Display - Releases: 4, Response time: 131 max, 51 mov ave - Deadlines missed: none. T12 - AUTO/CCIP Toggle - Releases: 2, Response time: 272 max, 162 mov ave - Deadlines missed: none. T13 - Poll RWR - Releases: 5, Response time: 79 max, 67 mov ave - Deadlines missed: none. T14 - Reinitiate Trajectory - Releases: 1, Response time: 485 max, 243 mov ave - Deadlines missed: none. T15 - Periodic BIT - Releases: 1, Response time: 97 max, 49 mov ave - Deadlines missed: none.
Como esperado, o conjunto todo é agendável nestas condições, com o
atendimento de todos os prazos limites tanto das tarefas periódicas como das
esporádicas, como observado no resultado da simulação e no gráfico de Linha
de Tempo respectivo Figura 4.7. O perfil de consumo das capacidades dos
servidores periódicos é observado na Figura 4.8. Atente–se ao fato de que a
duplicação do prazo limite (e conseqüentemente do MIT) das tarefas
esporádicas com relação ao caso anterior a fim de atender à condição de
agendabilidade aperiódica implica a menor quantidade (metade) de eventos e
de execuções das respectivas tarefas esporádicas resultando em uma menor
ocupação efetiva da CPU – fato observável mediante a comparação do tempo
ocioso da CPU no intervalo de tempo simulado (total idle time) em ambas as
simulações: 146 ms da simulação atual contra 119 ms da anterior.
120
Figura 4.7 – Linha de Tempo MCC com conjunto de tarefas agendável, Servidor de Varredura.
121
Figura 4.8 – Capacidade dos Servidores do MCC com conjunto de tarefas agendável, Servidor de Varredura.
122
4.6 MCC Com Especificações Modificadas – Servidor Esporádico, Conjunto Agendável
O conjunto de tarefas do MCC modificado (Tabela 3.2) com instantes dos
eventos da Tabela 3.3 (conjunto original respeitando o MIT) e tarefas
aperiódicas agendadas por meio do Servidor Esporádico (condições garantem
prazos limites periódicos e aperiódicos) apresenta os resultados mostrados na
listagem seguir:
***** Round 6 (11/18/2008 8:05:36 AM) ********************************************* Project file: MCC6_SS_Feasible.rts Description: CMM modified specification, RMS, feasible, Sporadic Server Program Version 1.0.3244.13171 -Priority assignment is RMS. -Using Sporadic Server for aperiodic tasks (aperiodic deadlines guaranteed under RMS with Ti=Di). -Processor utilization for the task set: 0.9349999 -RMS utilization bound (Liu & Layland, 1973): 0.7094119 -Periodic task set is *** NOT FEASIBLE *** (sufficient, not necessary utilization based test). -Response time analysis for periodic tasks (Hart, 1984, Joseph & Pandya, 1986) for Task(T,D,C,P): T1(10,10,1,15) - Weapon Release: (R=1) <= (D=10) : Ok. T2(40,40,2,12) - Radar Tracking: (R=6) <= (D=40) : Ok. T3(40,40,4,11) - Target Tracking: (R=10) <= (D=40) : Ok. T4(40,40,2,14) - Target Sweetening: (R=3) <= (D=40) : Ok. T5(40,40,1,13) - HOTAS Bomb Button: (R=4) <= (D=40) : Ok. T6(50,50,6,10) - Aircraft Flight Data: (R=17) <= (D=50) : Ok. T7(50,50,6,9) - HUD Display: (R=24) <= (D=50) : Ok. T8(50,50,8,8) - MPD Tactical Display: (R=33) <= (D=50) : Ok. T9(80,80,6,7) - Steering: (R=39) <= (D=80) : Ok. T10(100,100,7,5) - Weapon Trajectory: (R=99) <= (D=100) : Ok. T11(100,100,3,6) - Threat Response Display: (R=75) <= (D=100) : Ok. T12(200,200,1,4) - AUTO/CCIP Toggle: (R=100) <= (D=200) : Ok. T13(200,200,2,3) - Poll RWR: (R=146) <= (D=200) : Ok. T14(400,400,6,2) - Reinitiate Trajectory: (R=192) <= (D=400) : Ok. T15(1000,1000,5,1) - Periodic BIT: (R=197) <= (D=1000) : Ok. -Periodic task set is feasible (sufficient and necessary response time based test). -Aperiodic task set *** HAS NO GUARANTEE *** (sufficient, not necessary utilization based test). -Aperiodic task set deadlines are guaranteed (sufficient and necessary response time based test). STARTING SIMULATION... -Time interval: 0 - 999. -Simulation started at critical instant. Total idle time: 109 SIMULATION FINISHED. SIMULATION ANALYSIS AND STATISTICS: T1 - Weapon Release - Releases: 100, Response time: 1 max, 1 mov ave - Deadlines missed: none.
123
T2 - Radar Tracking - Releases: 25, Response time: 6 max, 4 mov ave - Deadlines missed: none. T3 - Target Tracking - Releases: 25, Response time: 10 max, 8 mov ave - Deadlines missed: none. T4 - Target Sweetening - Releases: 10, Response time: 3 max, 3 mov ave - Deadlines missed: none. T5 - HOTAS Bomb Button - Releases: 12, Response time: 4 max, 3 mov ave - Deadlines missed: none. T6 - Aircraft Flight Data - Releases: 20, Response time: 17 max, 10 mov ave - Deadlines missed: none. T7 - HUD Display - Releases: 20, Response time: 24 max, 21 mov ave - Deadlines missed: none. T8 - MPD Tactical Display - Releases: 20, Response time: 33 max, 31 mov ave - Deadlines missed: none. T9 - Steering - Releases: 13, Response time: 39 max, 26 mov ave - Deadlines missed: none. T10 - Weapon Trajectory - Releases: 10, Response time: 96 max, 51 mov ave - Deadlines missed: none. T11 - Threat Response Display - Releases: 8, Response time: 70 max, 24 mov ave - Deadlines missed: none. T12 - AUTO/CCIP Toggle - Releases: 4, Response time: 92 max, 56 mov ave - Deadlines missed: none. T13 - Poll RWR - Releases: 5, Response time: 99 max, 77 mov ave - Deadlines missed: none. T14 - Reinitiate Trajectory - Releases: 3, Response time: 139 max, 35 mov ave - Deadlines missed: none. T15 - Periodic BIT - Releases: 1, Response time: 194 max, 97 mov ave - Deadlines missed: none.
As condições de agendabilidade para o SS são confirmadas pelo resultado
apresentado: nenhum prazo limite, seja periódico ou aperiódico perdido. Pode–
se observar tanto do resultado da simulação como no gráfico de Linha de
Tempo (Figura 4.9) o bom tempo de resposta das tarefas esporádicas,
principalmente daquelas com as maiores prioridades, comparando, por
exemplo, com os tempos de resposta das respectivas tarefas executadas pelo
Servidor de Varredura (com garantias aperiódicas) mesmo com cerca de
metade de eventos a serem atendidos (4.5) no mesmo intervalo de tempo. Isso
com um melhor aproveitamento da capacidade de processamento, constatado
pela maior ocupação da CPU; o tempo ocioso no intervalo de tempo simulado
(total idle time) em ambas as simulações foi de 109 ms da simulação atual
contra 146 ms da anterior.
124
Figura 4.9 – Linha de Tempo do MCC com conjunto de tarefas agendável, Servidor Esporádico.
125
Figura 4.10 – Capacidade dos Servidores do MCC com conjunto de tarefas agendável, Servidor Esporádico.
126
Nas curvas de capacidade dos servidores (Figura 4.10) fica evidenciada, de
forma qualitativa, a razão do melhor desempenho no atendimento dos eventos:
a preservação da capacidade dos servidores ao longo do tempo, observável
pelas grandes áreas acinzentadas, ao contrário do que ocorre, por exemplo, no
servidor de varredura (Figura 4.8) onde ficam visíveis os curtos intervalos de
tempo no qual há capacidade de processamento dos servidores periódicos
(poucas áreas acinzentadas).
127
5 ANÁLISE E CONCLUSÕES
Partindo–se das premissas deste trabalho: 1) que uma determinada malha de
controle constitui, como um todo, um Sistema em Tempo Real Rígido; 2) o
agendamento de tarefas é feito de acordo com a teoria RMS; 3) as
especificações de projeto são corretas em termos de taxas de amostragem e
latências dos sinais de monitoração e atuação de forma que o Sistema opere
com o desempenho esperado, ou seja, de acordo com os diversos requisitos
incluindo estabilidade e segurança (“criticalidade”); conclui-se que qualquer um
dos três métodos de agendamento de tarefas aperiódicas / esporádicas
abordados (Serviço em Segundo Plano, Servidor de Varredura e Servidor
Esporádico) pode ser utilizado com a garantia de nenhum prazo limite periódico
será prejudicado. Ou seja, estando as funções básicas de controle do Sistema
(monitoração, atuação, cálculo, supervisão, diagnóstico, etc.) a cargo
exclusivamente de tarefas periódicas (que por definição possuem prazos
limites rígidos), seja qual for o algoritmo escolhido (dentre os elencados no
parágrafo anterior) para o agendamento das tarefas aperiódicas, não haverá
interferência no desempenho projetado do controle.
A escolha do método mais adequado fica restrita ao compromisso entre
requisitos (critérios) de desempenho esperados na execução das tarefas
esporádicas e na complexidade ou mesmo na possibilidade de implementação
do suporte ao método em questão no hardware (processador) e software
(Sistema Operacional) disponíveis. Isto se traduz em vários cenários possíveis,
dentre os quais:
Cenário 1 – Tarefas aperiódicas (prazos limites flexíveis – tempo de resposta
indefinido): Situação na qual as tarefas aperiódicas são responsáveis por
tarefas não críticas e o Serviço em Segundo Plano pode ser suficiente, com a
grande vantagem de ser o mais simples e facilmente adaptável aos sistemas
existentes (uma forma de implementação consiste em simplesmente atribuir a
menor prioridade possível a todas as tarefas aperiódicas).
128
Cenário 2 – Tarefas esporádicas (prazos limites rígidos) com tempos de
resposta médios longos: Nos casos em que uma ou mais tarefas são
esporádicas, porém os prazos limites são grandes (o dobro do intervalo de
tempo mínimo entre liberações do evento) e altos tempos de resposta são
tolerados, o Servidor de Varredura pode ser utilizado com relativa baixa
complexidade de implementação.
Cenário 3 – Tarefas esporádicas (prazos limites rígidos) com melhores tempos
de resposta médios (prazos limites iguais ao intervalo de tempo mínimo entre
liberações do evento): Este cenário é o mais provável de se encontrar,
principalmente em se tratando dos sistemas mais críticos e complexos pois, em
geral, o atendimento aos eventos esporádicos requer curto tempo de resposta
e muitas vezes são críticos quanto aos prazos limites. Neste caso o Servidor
Esporádico se apresenta como uma solução mais adequada, pois demonstra
um bom compromisso entre desempenho e complexidade de implementação.
Isto se alia ao fato de oferecer garantias de prazos limites periódicos e
aperiódicos independentemente de condições e restrições adicionais, além
daquelas estabelecidas pela teoria RMS e pelas premissas do algoritmo do
Servidor Esporádico.
Como o Servidor Esporádico (onde a tarefa servidora equipara–se a uma tarefa
periódica equivalente) opera sob as premissas originais do RMS, os mesmos
testes de agendabilidade utilizados no contexto RMS puramente periódico são
válidos no caso misto (SPRUNT, 1990). Desta forma, pode–se optar, quando
do uso do SS, pelo Teste de Agendabilidade RMS tradicional mais conservador
(baseado na utilização do processador) ou pelo teste baseado na análise dos
tempos de resposta que, embora sendo mais complexo, permite, em geral,
maior utilização do processador por ser condição suficiente e necessária de
agendabilidade ressaltando que, no primeiro caso, por ser conservador, o teste
tende a ser mais robusto.
129
Embora tenha demandado uma grande quantidade de recursos em termos de
esforço e tempo em seu desenvolvimento, o Simulador em Tempo Real Rígido
HRTSim foi de grande valia para o progresso deste estudo por suportar os
algoritmos de agendamento estudados e fornecer dados práticos realistas e de
acordo com a teoria de suporte. Adicionalmente isso fez com que o trabalho
fosse desenvolvido tanto no sentido da análise (a proposta original deste) como
no sentido da síntese, simultaneamente. Ambos os processos, a partir de certo
ponto, transcorreram par e passo na medida em que as teorias estudadas e
desenvolvidas eram aos poucos materializadas na prática mediante sua
incorporação nos modelos do simulador. O protótipo de produto era então
testado contra a teoria e a seguir refinado em um novo ciclo semelhante
envolvendo este processo de estudo e desenvolvimento parelhos. Desta forma,
foi possível perceber o quão sensíveis são o funcionamento e o desempenho
de um Sistema em Tempo Real em função de sua implementação, reforçando
a percepção de que, ao contrário do que ocorre na Computação em Tempo
Virtual, a Computação em Tempo Real demanda conhecimento intrínseco e
profundo da plataforma de execução tanto em nível de hardware como de
software. Detalhes aparentemente simples como, por exemplo, a forma com
que um despachador trata duas tarefas com a mesma prioridade ou qual a
postura a tomar quando uma determinada tarefa descumpre seu prazo limite
podem ter um impacto devastador sobre um sistema crítico. Enquanto a versão
corrente constitui, em princípio, uma ferramenta acadêmica, certamente ela
serve de base para um aplicativo comercial de engenharia para auxílio ao
estudo, desenvolvimento, testes e validação de Sistemas em Tempo Real
Rígido envolvendo agendamento e execução preemptiva de tarefas periódicas
e esporádicas. Basta para isto: a incorporação de funcionalidades julgadas
necessárias, a remoção daquelas dispensáveis, e o retrabalho delas dentro das
práticas de Engenharia de Software demandadas ao desenvolvimento de um
aplicativo de produção.
130
A maior contribuição do trabalho de Liu e Layland (1973) e o motivo para que
este seja um dos marcos no estudo dos Sistemas em Tempo Real foi a quebra
do paradigma, até então determinante e fundamental, de que a principal
característica que permitia um sistema operar em Tempo Real Rígido era o
determinismo, ou seja aquela situação na qual as teorias e a operação dos
sistemas em Tempo Real Rígido só se faziam possíveis mediante o completo e
absoluto conhecimento a priori de todas as características temporais do
sistema. A partir de então ficou demonstrado na teoria e provado pela prática
aplicada ao longo dos vários anos até os dias de hoje, que basta o sistema ser
previsível para que opere dentro das condições de um Sistema em Tempo Real
Rígido, no sentido de que previsibilidade, neste contexto, ao contrário de
determinismo, significa o completo e absoluto conhecimento a priori do
desempenho do sistema ao contrário da completa caracterização temporal do
seu comportamento. Basta observar que o teste de exeqüibilidade RMS se
baseia na utilização do processador, um parâmetro de desempenho no
agendamento preemptivo (seqüenciamento de tarefas não determinístico, pois
permite infinitas combinações de intercalamento de tarefas já que não há
nenhum critério implícito ou explícito de sincronismo entre os instantes de
liberação delas neste modelo). Esta troca de paradigma teve como
conseqüência uma grande mudança nas abordagens teóricas e
implementações práticas posteriores abrindo um grande horizonte em termos
de situações, métodos, teorias, modelos e arquiteturas antes inviáveis, agora
passíveis de serem aplicadas aos Sistemas em Tempo Real resultando num
grande número de trabalhos posteriores explorando a maior flexibilidade nesta
abordagem (ATLAS e BESTRAVOS, 1998, AUDSLEY, 1990, TRIVELATO e
SOUZA, 2003), inclusive o assunto tratado no presente estudo.
Enquanto o setor aeroespacial faz uso pesado não só da teoria, mas também
da prática dos Sistemas em Tempo Real já há um bom tempo, a área
acadêmica e mesmo de pesquisa, de certa forma, ainda carece do estudo
formal deste ramo do conhecimento. Veículos e sistemas aéreos e espaciais,
131
bem como outros, por suas características intrínsecas em termos de interação
com o ambiente e complexidade tanto dos problemas enfrentados bem como
das soluções idealizadas e realizadas são responsáveis por um campo fértil
permeado por necessidades e aplicações que remetem, obrigatoriamente, ao
uso de tal classe de sistemas. O interesse do setor acadêmico nos Sistemas
em Tempo Real, seja na abordagem computacional como na abordagem de
Controle e de Sistemas, tem se mostrado tímido apesar de sua grande
importância para a indústria e demais instituições geradoras ou usuárias de alta
tecnologia. Esta dicotomia se deve basicamente à relativa juventude do
assunto e à abordagem ad hoc na qual a maioria dos estudos e soluções dos
problemas de Tempo Real, até datas mais recentes, tem nascido e se
desenvolvido: de maneira puntual e isolada nas pranchetas e laboratórios das
diversas instituições no afã de resolver seus problemas do dia a dia, enquanto
uma pequena porção tem se originado de forma sistemática na academia.
Como conseqüência, a bibliografia, os trabalhos representativos, as teorias,
conceitos básicos definições e até mesmo o jargão tendem a ser dispersos,
carecendo de padrões formais, muitas vezes chegando a serem controversos
ou mesmo anacrônicos. Porém, com a conseqüente maturidade que aos
poucos o assunto vem galgando, já se pode observar um horizonte evolutivo
principalmente nos países que abrigam berços científicos e tecnológicos.
Ambos os motivos serviram de inspiração e nortearam o desenvolvimento do
presente trabalho no esforço de acompanhar e quem sabe contribuir, dando um
passo por vez, com esta evolução no estudo e na aplicação dos Sistemas em
Tempo Real na indústria, nos centros de pesquisa e nas instituições de ensino.
A bibliografia analisada, apesar de corresponder a uma fração dos trabalhos
sobre o assunto, fornece bases razoavelmente sólidas e aponta para outros
documentos essenciais constituindo um conjunto conciso com abrangência
razoável para servir de subsídio desde o aprendizado e estudos iniciais a
respeito dos Sistemas em Tempo Real até a implementação de soluções de
engenharia aos problemas do dia–a–dia no que se refere a esta classe de
sistemas. Tanto que tal bibliografia se traduziu nos primeiros capítulos deste
132
estudo abrangendo desde a conceituação fundamental até os modelos e
algoritmos necessários ao estudo proposto.
133
6 DIREÇÕES PARA ESTUDOS FUTUROS
Este trabalho, assim como qualquer outro do gênero, se mostra como uma
tentativa de abordar, analisar e aplicar apenas uma minúscula parcela do
conhecimento que permeia o assunto levantado pelo objetivo proposto. Longe
de fechar questões ou de estabelecer utópicas soluções definitivas, talvez
ainda apresente como pontos relevantes, além dos resultados e conclusões
específicas surgidas ao longo de seu desenvolvimento, todo um horizonte de
novas questões a serem resolvidas, quem sabe velhas questões a serem
revisitadas, um sem número de dúvidas até então ocultas pelo nosso efêmero
estado de certeza para serem dirimidas e para darem vida a novas dúvidas
pelo bem de nossa necessidade evolutiva. Alguns dos muitos pontos deixados
em aberto e algumas das inúmeras ramificações brotadas são a seguir
elencados como sugestões para prosseguimento do estudo corrente ou
possíveis novos pontos de partida.
Ao simulador HRTSim podem ser incluídas novas funcionalidades como:
Outras políticas de atribuição de prioridades como por exemplo o
Agendamento a Prazos Monotônicos (Deadline Monotonic).
Suporte aos modelos do Servidor Adiável e do Servidor de Troca de
Prioridades.
Levantamento de estatísticas comparativas de desempenho entre os
diversos modelos de atendimento aperiódico em função dos parâmetros
temporais e da configuração do conjunto de tarefas (e.g. tempos médios
e máximos de resposta em função da quantidade de tarefas, tempos
médios e máximos de resposta em função da utilização do processador,
etc.).
Implementação do Servidor Esporádico para tarefas com prazos limites
aperiódicos inferiores ao período do servidor utilizando a atribuição de
134
prioridades a Prazos Monotônicos para as tarefas aperiódicas /
esporádicas.
Refinamento do modelo do despachador de tarefas de forma a simular
situações mais realistas considerando overhead de processamento
(chaveamento de contexto), atrasos de liberação das tarefas (release
jitter), etc.
Cabe também a inclusão de modelos de agendadores e despachadores
dedicados à execução em regime de Tempo Real Flexível, situação na qual
seriam abertas diversas outras possibilidades de estudo e de arquitetura de
implementação como, por exemplo, o atendimento de mais de uma tarefa
aperiódica por um único servidor.
O acréscimo de métodos para contingenciamento de situações de exceção,
como sobrecarga do processador, por meio de políticas de execução de tarefas
em modo degradado (fine–coarse), salto de período (period skipping), salto de
tarefas (task / job skipping), mudanças de modo (mode changes), etc. permitiria
simular sistemas tolerantes a falha (ÅRZÉN et al., 1999, CERVIN, 2000).
O HRTSim simula um intervalo de tempo definido delimitado pelos instantes de
tempo inicial e final. Uma vez transcorrido este intervalo, poder–se–ia salvar o
último estado de execução e reiniciar a simulação tomando o instante final
como novo ponto de partida. Assim seria possível simular a execução ad
æternum do sistema, situação que permitiria o levantamento de estatísticas de
desempenho a longo prazo e, principalmente, a verificação e a validação de
modelos de agendamento, algoritmos de despachamento e configurações de
conjuntos de tarefas em regime de execução continuada.
Um trabalho envolvendo o levantamento, estudo e avaliação das ferramentas
de simulação em tempo real existentes, sejam comerciais ou acadêmicas, seria
de grande importância uma vez que tais informações, quando encontradas, são
dispersas e normalmente enfocam agendamento periódico. Informações sobre
135
o suporte ao agendamento aperiódico, quando existentes, geralmente se
limitam aos aspectos mais superficiais.
Embora este trabalho tenha tratado de dois paradigmas de suporte aperiódico
(serviço em segundo plano e servidores periódicos), existem outras
abordagens como o método da tomada de folga (slack stealing) além dos
métodos de agendamento baseados em atribuição dinâmica de prioridade e
outros temas ligados ao assunto que são dignos de estudo (AUDSLEY e
BURNS, 1990, LIU, 2000, BUTTAZZO, 2005, BUTTAZZO, 1997, DAVIS et al.,
1993).
A linha de estudos envolvendo agendamento não determinístico abre as
possibilidades para se lidar com os casos envolvendo tempos de computação
variáveis, imprecisos ou mesmo estimados por meio da modelagem por
funções de densidade de probabilidade específicas (BURNS e EDGAR, 2000)
e de carregamento dinâmico do processador no qual não se pode determinar a
priori a quantidade de tarefas a executar. A teoria do RMS Estatístico (ATLAS e
BESTRAVOS, 1998), por exemplo, aborda estas e outras questões.
137
REFERÊNCIAS BIBLIOGRÁFICAS
ÅRZÉN, K.; BERNHARDSSON, B.; EKER, J.; CERVIN, A.; PERSSON, P.; NILSSON, K.; SHA, L. Integrated control and scheduling. Lund, Sweden: Lund Institute of Technology, Aug. 1999. Technical Report. ISSN:02805316.
ATLAS, A. K.; BESTRAVOS, A. Statistical rate monotonic scheduling. Boston, MA, USA: Boston University, IEEE Computer Society Press, 1998. p. 123–132. Technical Report.
AUDSLEY, N. C. ; BURNS, A. Real–time system scheduling. York, England: University of York, 1990. Technical Report. YCS 134.
AUDSLEY, N. C.; BURNS, A.; RICHARDSON, M.; TINDELL, K.; WELLINGS, A. J. Applying new scheduling theory to static priority pre–emptive scheduling. Software Engineering Journal, v. 8, n. 5, p. 284–292, Sep. 1993.
AUDSLEY, N. C. Deadline monotonic scheduling. York, England: University of York, 1990. Internal Paper. YCS–90–146.
BAILLIEUL, J.; BROCKETT, R. W.; WASHBURN, R. B. Chaotic motion in nonlinear feedback systems. IEEE Trans. Circuits Syst., v. CAS–27, p. 990–997, 1980.
BAILLILEUL, J.; ANTSAKLIS, P. J. Control and communication challenges in networked real time systems. Proceedings of IEEE, v. 95, n. 1, p. 9–28, Jan. 2007.
BATE, I. J. Scheduling and timing analysis for safety critical systems. 1999. (YCST–99–04). PhD Thesis – University of York, York, England, Nov. 1998.
BURNS, A.; EDGAR, S. Predicting computation time for advanced processor architectures. In: EUROMICRO CONFERENCE ON REAL–TIME SYSTEMS, 12., 19–21 Jun. 2000, Stockholm, Sweden. Proceedings... Sweden: IEEE Computer Society, 2000. p. 89–96. ISBN:0769507344.
BURNS, ALAN. Scheduling hard real–time systems: a review. Software Engineering Journal, v. 6, n. 3, p. 116–128, May 1991.
BURNS, A.; WELLINGS, A. Real–time systems and programming languages. 2 ed. England: Addison Wesley, 1996. 611 p. ISBN:020140365X.
BUTTAZZO, G. Hard real–time computing systems: predictable scheduling algorithms and applications. 1 ed. Norwell, MA, USA: Kluwer Academic Publishers, 1997. 379 p. ISBN:0792399943.
BUTTAZZO, G. Rate monotonic vs. EDF: judgment day. Real–Time Systems, v. 29, n. 1, p. 5–26, Jan. 2005.
138
BUTTAZZO, G. Real–time operating systems: problems and novel solutions. In: INT. SYMPOSIUM ON FORMAL TECHNIQUES IN REAL–TIME AND FAULT–TOLERANT SYSTEMS (FTRTFT 2002), 7., Sep. 2002, Oldenburg, Germany Proceedings... Germany: Springer–Verlag, 2002. v. 2469. p. 37–51.
CERVIN, A. Integrated control and real–time scheduling. 2003. (ISRN:LUTFD2/TFRT–1065–SE). PhD Thesis – Lund Institute of Technology, Lund, Sweden, 2003. ISSN:02805316.
CERVIN, A. Towards the integration of control and real–time scheduling design. 2000. 152 p. (ISRN:LUTFD2/TFRT–3226–SE). Licentiate Thesis – Lund Institute of Technology, Lund, Sweden, 2000. ISSN:02805316.
CHENG, A. M. K. Real–time systems: scheduling, analysis, and verification. 1 ed. Hoboken, New Jersey, USA: John Wiley & Sons, Inc., 2002. ISBN:0471184063.
DAVIS, R. I.; TINDELL, K. W.; BURNS, A. Scheduling slack time in fixed priority pre–emptive systems. In: PROCEEDINGS OF REAL–TIME SYSTEMS SYMPOSIUM (RTSS1993), Dec. 1993, Raleigh Durham, NC, USA. Proceedings... USA: IEEE Computer Society Press, 1993. p. 222–231. ISBN:081864480X.
DELCHAMPS, D. F. Stabilizing a linear system with quantized state feedback. IEEE Transactions On Automatic Control. v. 35. p. 916–924, 1990.
DODD, R. B. An analysis of task–scheduling for a generic avionics mission computer. Victoria, Australia: Department of Defense, 2006. 37 p. Technical Report. DSTO–TN–0691.
FARINES, J. M.; FRAGA, J. S.; OLIVEIRA, R. S. Sistemas de tempo real. São Paulo, Brasil: IME–USP, 2000. 201 p.
HARTER, P. K. Response times in level structured systems. Boulder, CO, USA: University of Colorado,1984. Technical Report. CU–CS–269–94.
HARTER, P. K. Response times in level structured systems. ACM Transactions on Computer Systems, v. 5, n. 3, p. 232–248, Aug. 1987. ISSN:07342071.
IGNACE, S. J.; SEDLMEYER, ROBERT L.; THUENTE, DAVID J. Integrating rate monotonic analysis into real–time software development. In: IFIP TC8 WORKING CONFERENCE ON DIFFUSION, TRANSFER AND IMPLEMENTATION OF INFORMATION TECHNOLOGY, 11–13 Oct. 1993, Pittsburgh, PA, USA. Proceedings... New York, NY, USA: Elsevier Science Inc., 1994. v. A–45, p. 257–274. ISBN:0444818561.
JOSEPH, M.; PANDYA, P. Finding response times in a real–time system. The Computer Journal, v. 29, n. 5, p. 390–395, 1986.
LAPLANTE, P. A. Real–time systems design and analysis: an engineer’s handbook. 3 ed. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2004. ISBN:0471228559.
139
LEHOCZKY, J. P.; SHA, L.; DING, Y. The rate monotonic scheduling algorithm: exact characterization and average case behavior. In: IEEE REAL–TIME SYSTEMS SYMPOSIUM, 10., 5–7 Dec. 1989, Santa Monica, CA, USA. Proceedings... USA: IEEE Computer Society Press, 1989. p. 166–171. ISBN:0818620048.
LEHOCZKY, J. P.; SHA, L. ; STROSNIDER, J. K. Enhanced aperiodic responsiveness in hard real time environments. In: IEEE REAL TIME SYSTEMS SYMPOSIUM, 8., 1987, Los Alamitos, CA, USA. Proceedings... USA: IEEE Computer Society Press, 1987. p. 261–270.
LIU, C. L.; LAYLAND, J. W. Scheduling algorithms for multiprogramming in a hard real–time environment. Journal of the Association for Computing Machinery (JACM), v. 20, n. 1, p. 46–61, Jan. 1973.
LIU, J. W. S. Real time systems. 1 ed. Upper Saddle River, NJ, USA: Prentice Hall, Pearson Education, 2000. 624 p. ISBN:978–0130996510.
LI, Q.; YAO, C. Real–time concepts for embedded systems. 1 ed. USA: CMP Books, 2003. 294 p. ISBN:1578201241.
LOCKE, C. D.; VOGEL, D. R.; LUCAS, L. ; GOODENOUGH, J. B. Generic avionics software specification. Pittsburgh, PA, USA: Carnegie Mellon University, 1990. Technical Report. CMU/SEI–90–TR–8–ESD–TR–90–209.
LOCKE, C. D.; VOGEL, D. R.; MESLER, T. J. Building a predictable avionics platform in Ada: a case study. In: REAL–TIME SYSTEMS SYMPOSIUM, 20., 4–6 Dec 1991, San Antonio, TX, USA. Proceedings..., USA: IEEE Computer Society Press, 1991. p. 181–189.
LUCAS, L.; PAGE, B. Tutorial on rate monotonic analysis. In: ANNUAL WASHINGTON ADA SYMPOSIUM, 9., 13–16 Jul 1992, McLean, VA, USA. Proceedings... New York, NY, USA: Association for Computing Machinery, 1992.
MARTIN, J. Design of real–time computer systems. 1 ed. Upper Saddle River, NJ, USA: Prentice Hall, Englewood Cliffs, 1967. ISBN:0132014009.
MERCER, C. W. An introduction to real–time operating systems: scheduling theory (Draft). Nov. 1992. Disponível em: <http://www.control.auc.dk/~henrik/undervisning/sandtid/litt/sur1.review.pdf>. Acesso em 10 fev. 2009.
NYQUIST, H. Regeneration theory. Bell Syst. Technical Journal, v. 11, p. 126–147, 1932.
RAMAMRITHAM, K ; STANKOVIC, J. A. Scheduling algorithms and operating systems support for real–time systems. Proceedings of the IEEE, v. 82, n. 1, p. 55–67, Jan. 1994.
140
SHA, L.; ABDELZAHER, T.; ÅRZÉN, K.; CERVIN, A.; BAKER, T.; BURNS, A.; BUTTAZZO, G.; CACCAMO, M.; LEHOCZKY, J.; MOK, A. K. Real time scheduling theory: a historical perspective. Real–Time Systems, v. 28, n. 2–3, p. 101–155, Nov.–Dec. 2004.
SHA, L.; RAJKUMAR, R.; LEHOCZKY, J. P. Real–time computing with IEEE futurebus+. IEEE Micro, v. 11, n. 3, p. 30–38, May 1991.
SILBERSCHATZ, A.; GALVIN, P. B.; GAGNE, G. Operating system concepts. 7 ed. Hoboken, NJ, USA: John Wiley & Sons, Inc., 2005. 944 p. ISBN:0471694665.
SPRUNT, B. Aperiodic task scheduling for real–time systems. 1990. PhD Dissertation – Carnegie Mellon University, Pittsburgh, PA, USA, 1990.
SPRUNT, B.; SHA, L.; LEHOCZKY, J. Aperiodic task scheduling for hard–real–time systems. The Journal of Real–Time Systems, v. 1, n. 1, p. 27–60, Jun. 1989.
STALLINGS, W. Operating systems: internals and design principles. 5 ed. Upper Saddle River, NJ, USA: Prentice Hall, 2005. 832 p. ISBN:9780131479548.
STANKOVIC, J. A. Misconceptions about real–time computing: a serious problem for next generation systems. Computer, v. 21, n. 10, p. 10–19, Oct. 1988.
STANKOVIC, J. A.; RAMAMRITHAM, K. What is predictability for real–time systems. Real–Time Systems, v. 2, n. 4, p. 247–254, Nov. 1990. Editorial.
STANKOVIC, J. A. Real time computing. Byte, p. 155–160, Aug. 1992. Invited Paper.
STROSNIDER, J. K.; LEHOCZKY, J. P.; SHA, L. The deferrable server algorithm for enhanced aperiodic responsiveness in hard real–time environments. IEEE Transactions on Computers, v. 44, n. 1, p. 73–91, Jan. 1995.
TANENBAUM, A. S. Modern operating systems. 2 ed. Upper Saddle River, NJ , USA: Prentice Hall, 2001. 976 p. ISBN:0130313580.
TATIKONDA, S.; MITTER, S. Control under communication constraints. IEEE Transactions on Automatic Control, v. 49, n. 7, p. 1056–1068, Jul. 2004.
TRIVELATO, G. C.; SOUZA, M. L. O. Improving the rate monotonic and the
first deadline first schedulers for real time simulation and control of
aerospace vehicles. São José dos Campos: INPE, 2003. 10 p. (INPE–9880–
PRE/5455).
141
APÊNDICE A – COMPLEMENTO TEÓRICO
A.1 Sistemas em Tempo Real – Classificação, Detalhes e Exemplos
Tipicamente um Sistema em Tempo Real consiste de um sistema controlador e
de um sistema controlado, este último podendo ser visto como o ambiente com
o qual o sistema computadorizado interage (STANKOVIC, 1992). Ambos se
relacionam por meio de ações e sinais de controle e monitoração (Figura A.1).
Além disso, o tempo do sistema computadorizado controlador (tempo interno)
tem que transcorrer com a mesma escala de tempo utilizada pelo ambiente
controlado (tempo externo). Fica claro que, ao contrário da falsa crença que
Tempo Real implica em um sistema rápido, o que caracteriza os Sistemas em
Tempo Real é a previsibilidade (predictability) no sentido de que um sistema é
dito previsível se for possível mostrar, demonstrar ou provar que os requisitos
são cumpridos estando o sistema sujeito às premissas feitas (STANKOVIC e
RAMAMRITHAM, 1990).
SISTEMA EM TEMPO REAL
COMPUTADOR (SISTEMA CONTROLADOR)
AMBIENTE (SISTEMA CONTROLADO)
CO
NT
RO
LE
MO
NIT
OR
AÇ
ÃO
Figura A.1 – Componentes de um Sistema em Tempo Real.
142
A grande maioria dos Sistemas de Controle automático computadorizado são
Sistemas em Tempo Real, uma vez que tanto os modelos dos elementos como
as leis de controle do sistema, representam e lidam com a dinâmica
característica da planta (ambiente) a ser controlada. Como o computador faz
parte da malha de controle (Figura 2.1), é imperativo que as características
temporais das suas ações de aquisição de medidas, processamento e atuação
se façam em consonância com as constantes de tempo que regem a dinâmica
do sistema como um todo.
Exemplos de Sistemas em Tempo Real
Dispositivos de comunicação e utensílios em geral:
o Roteadores, switches, modems.
o Reprodutores de DVD.
o Decodificadores de TV digital.
o Telefonia celular, Voice Over IP – VOIP, Smart phones.
o Impressoras.
Equipamentos interativos e aplicações sob demanda:
o Consoles de jogos.
o Vídeo–conferência.
o Realidade virtual.
Sistemas de transporte e controle veicular:
o Controle de propulsão e navegação.
143
o Sistemas de Freio Antitravamento Automotivo (Antilock Breaking System – ABS), controle de air–bag, gerenciamento de motor.
o Sistemas automotivos em geral.
o Chaveamento de trilhos de ferrovias.
o Controle de movimentos em geral.
Controle de processo e manufatura:
o Geração de energia elétrica.
o Refinarias de petróleo.
o Controle de processos químicos em geral.
o Fabricação de semicondutores.
o Linhas de montagem automatizadas.
o Empacotamento e engarrafamento.
Sistemas de defesa e aeroespaciais:
o Sistemas de navegação.
o Posicionamento global.
o Controle e comando.
o Sistemas de armas.
o Aviônicos, controle de turbinas, controle aerodinâmico.
o Controle de tráfego aéreo.
o Estação espacial, ônibus espacial.
o Navegação e controle de foguetes e mísseis.
o Navegação e controle de satélites.
Medicina e saúde:
o Monitor de sinais vitais de unidade de terapia intensiva.
144
o Marca–passos.
o Próteses e órgãos artificiais.
Outras:
o Robótica.
o Monitoramento ambiental.
Classificação dos Sistemas em Tempo Real
Uma característica inerente da maioria dos RTS é o fato de que as
especificações de requisitos incluem informação de tempo, geralmente na
forma de prazos limites (BURNS, 1991) ao final dos quais a execução de todas
as tarefas correspondentes deve estar completamente finalizada.
Devido ao grande espectro de complexidade das aplicações dos RTSs, as
conseqüências da perda de um prazo limite variam de irrelevantes (e.g. vídeo
sob demanda) até catastróficas (e.g controle de tráfego aéreo), dependendo do
sistema. Claramente, tanto a abordagem a ser adotada como os requisitos a
serem cumpridos variam sobremaneira de um sistema para outro, o que torna
necessário o agrupamento dos RTSs em categorias.
Assim, os RTSs são classificados de acordo com a “criticalidade” dos prazos
limites das tarefas, em outras palavras, de acordo com as conseqüências, para
o ambiente, quando da perda de um ou mais prazos limites:
Sistemas em Tempo Real Flexível.
Sistemas em Tempo Real Firme.
Sistemas em Tempo Real Rígido.
Sistemas em Tempo Real Real.
145
Os sistemas computacionais que não possuem prazos limites especificados
porém procuram manter “tempos de resposta adequados” são chamados de
Sistemas Interativos (online). Note–se que, neste caso, inexistem requisitos
formais de tempo, mas sim um desempenho esperado subjetivo. Aqueles
sistemas onde não há consideração alguma acerca do tempo de resposta são
chamados Sistemas de Processamento em Lote (batch).
Durante o projeto de um sistema em Tempo Real, os requisitos temporais são
mapeados em prazos limites e a questão de atender a todos os prazos limites
constitui no problema de agendamento (scheduling) e a entidade responsável
por resolver este problema é o agendador (scheduler).
Utilidade de um Evento
Utilidade ou valor de um determinado evento é fracamente definido como
sendo a contribuição do evento no cumprimento dos objetivos do sistema
(BURNS, 1991). A utilidade de uma tarefa no contexto de um Sistema em
Tempo Real constitui em uma valoração subjetiva atribuída como
conseqüência da execução desta sob uma determinada situação temporal,
podendo tanto ser positiva, nula ou negativa. Valor nulo de utilidade significa
que não houve qualquer contribuição da execução, ou seja, a execução da
tarefa nessas condições tem o mesmo efeito da não execução da mesma.
Valores negativos de utilidade implicam em prejuízo ou dano ao sistema, ou
seja, a execução da tarefa nessas condições é pior que a não execução da
mesma.
O mapeamento do intervalo de tempo empregado por uma tarefa contra sua
utilidade chama–se função tempo–utilidade ou função tempo–valor e permite
que se tenha noção das conseqüências resultantes da execução desta em
função das restrições temporais impostas. Tal mapeamento auxilia na
classificação do RTS, como a seguir.
146
Sistemas em Tempo Real Flexível
Sistema de Tempo Real Flexível (Soft Real–Time System) é aquele onde os
prazos limites são importantes, mas o sistema ainda funcionará corretamente
se prazos limites forem ocasionalmente descumpridos (BURNS e WELLINGS,
1996).
Nos Sistemas em Tempo Real Flexível a utilidade do sistema diminui (o valor
associado à tarefa cujo prazo limite não foi cumprido degrada) à medida que a
conclusão do processamento se afasta do prazo limite (e.g. descompressor de
vídeo MPEG de um DVD, sistema de aquisição de dados, etc.). Uma curva de
utilidade típica representativa de um Sistema em Tempo Real Flexível pode ser
vista na Figura A.2. A conclusão da execução da tarefa no intervalo de tempo
definido entre o instante de referência inicial até o prazo limite (deadline)
agrega de forma integral a utilidade referente à tarefa em questão aos objetivos
do sistema. À medida que o instante de conclusão ultrapassa o prazo limite, o
valor diminui, podendo reduzir–se a zero. Apesar de representar uma operação
degradada, este caso não representa uma falha grave; o sistema é tolerante à
perda ocasional do prazo limite e seu funcionamento é considerado correto.
Utilid
ad
e
Tempo Prazo Início
Figura A.2 – Função tempo–utilidade de uma tarefa com prazo flexível.
147
Sistemas em Tempo Real Firme
Sistema em Tempo Real Firme (Firm Real–Time System) é o Sistema em
Tempo Real Flexível no qual não há benefício algum quando da entrega tardia
do serviço (BURNS e WELLINGS, 1996).
Um ou mais prazos limites para uma determinada tarefa podem ser
ocasionalmente perdidos, porém a execução tardia é sem utilidade, ou seja não
agrega ao sistema o valor associado à tarefa (e.g. sistema de validação de
cartão de crédito).
Utilid
ad
e
Tempo Prazo Início
Figura A.3 – Função tempo–utilidade de uma tarefa com prazo firme.
148
Sistemas em Tempo Real Rígido
Sistema em Tempo Real Rígido (Hard Real–Time System) é aquele onde é
absolutamente imperativo que as respostas ocorram dentro de prazos limites
especificados (BURNS e WELLINGS, 1996).
São também chamados de Sistemas Críticos de Tempo Real ou Sistema de
Segurança Crítica (Safety–Critical Systems) uma vez que a perda de um único
prazo limite basta para implicar em conseqüências danosas ou mesmo
catastróficas. O sistema falha se perder um prazo limite, resultando em dano
material ou mesmo humano (e.g. controlador de um reator nuclear, piloto
automático, controlador de atitude, etc.).
Informalmente, um Sistema em Tempo Real Rígido pode ser definido como
aquele no qual o dano resultante da perda de um prazo limite é maior que
qualquer possível utilidade que pode ser obtida por uma computação correta e
em tempo (BURNS, 1991).
O dano decorrente do não cumprimento dos requisitos temporais pode ser
progressivo, de forma que a gravidade aumenta com o passar do tempo após a
perda de um prazo limite (Figura A.4).
149
O dano também pode ser instantâneo, ou seja, a perda de um prazo limite
implica na falha ou mesmo destruição imediata do sistema (Figura A.5).
Utilid
ad
e
Tempo
Prazo Início
Dan
o
Figura A.4 – Função tempo–utilidade de uma tarefa com prazo rígido com dano progressivo.
150
Sistemas em Tempo Real Real
Sistema em Tempo Real Real (Real Real–Time System) é o Sistema em
Tempo Real Rígido no qual os tempos de resposta são muito pequenos (e.g.
sistema de guiagem de mísseis).
Sistema Operacional em Tempo Real
O Sistema Operacional em Tempo Real (Real Time Operating System – RTOS)
consiste em um conjunto de algoritmos (programas aplicativos do sistema) que
gerencia os recursos de hardware do computador (i.e. processador, memória,
discos, periféricos, etc.) criando uma abstração dos componentes físicos do
mesmo mediante a qual tais recursos são disponibilizados aos programas
Utilid
ad
e
Tempo
Prazo Início
Dan
o
Figura A.5 – Função tempo–utilidade de uma tarefa com prazo rígido com dano
instantâneo e catastrófico (utilidade tendendo a – ).
151
aplicativos e aos usuários (SILBERSCHATZ et al., 2005, STALLINGS, 2005,
TANENBAUM, 2001). Os objetivos de um RTOS são o de satisfazer os
requisitos de comportamento em Tempo Real e de fornecer um ambiente
multitarefa robusto e flexível (LAPLANTE, 2004).
O RTOS facilita a criação de Sistemas em Tempo Real, porém não garante por
si só que os resultados finais sejam em Tempo Real, o que requer projeto e
desenvolvimento correto dos aplicativos.
O RTOS é constituído por diversas camadas de abstração, cada uma das quais
lhe acrescenta conjuntos de funcionalidades típicas (Figura A.6).
O núcleo (kernel) em Tempo Real, como o próprio nome diz, constitui na parte
lógica essencial do RTOS mais próxima da parte física. É a porção que
interage mais diretamente com o hardware orquestrando a operação inteira do
HARDWARE
NÚCLEO – Agendamento – Despachamento – Sincronização – Comunicação
EXECUTIVO – Arquivos – Disco
SISTEMA OPERACIONAL – Interação com o usuário – Criação de programas – Execução de programas
Figura A.6 – Composição do Sistema Operacional.
152
computador, provendo funções específicas com relação às tarefas, dentre
outras:
Agendamento.
Despachamento.
Sincronização e comunicação entre processos.
O agendamento, a cargo do agendador (scheduler) ou escalonador, consiste
em determinar a ordem de execução de tarefas em um ambiente multitarefa de
acordo com uma política ou algoritmo de agendamento específico, enquanto
que o despachamento, a cargo do despachador (dispatcher), consiste nas
atividades relativas ao controle efetivo das tarefas (i.e. execução). A relação
entre ambos é ilustrada na Figura A.7. Os recursos de sincronização e
comunicação garantem a cooperação entre as tarefas bem como o controle de
recursos compartilhados.
Basicamente, o núcleo é a parte que mais diferencia um RTOS de um Sistema
Operacional regular, principalmente devido aos algoritmos de agendamento e
despachamento especializados.
AGENDADOR (POLÍTICA)
DESPACHADOR (CONTROLE) TAREFAS
CPU
CARACTERÍSTICAS
SEQÜÊNCIA
PROCESSO
Figura A.7 – Agendador e depachante em Tempo Real.
153
O executivo em Tempo Real acrescenta funcionalidades básicas relativas a
arquivos, acesso a disco e outros dispositivos de entrada e saída (Input/Output
– I/O).
O RTOS como um todo (camada mais externa) fornece uma interface
generalizada com o usuário, segurança (controle de acesso) e um sistema de
gerenciamento de arquivos de alto nível. Nem todo Sistema em Tempo Real
possui um RTOS; alguns sistemas com hardware relativamente simples,
dedicados ou com pequena quantidade de software aplicativo podem não
requerer um Sistema Operacional (LI e YAO, 2003). Neste caso, pode ser
suficiente um executivo em Tempo Real, um núcleo em Tempo Real ou mesmo
um subconjunto de funcionalidades de um núcleo em Tempo Real para atender
as necessidades de projeto.
Tanto as definições das camadas de abstração do RTOS bem como as
funcionalidades relativas a cada uma apresentadas são típicas e variam de
acordo com o autor e com a implementação específica do RTOS.
A.2 Sistemas em Tempo Real – Marcos Históricos
1940s e 1950s: Surgimento dos primeiros estudos e aplicações na área
de Pesquisa de Operações (Operations Research), fato que mais veio a
influenciar os estudos teóricos de Sistemas em Tempo Real.
1947: Desenvolvimento do simulador de vôo Whirlwind, pela IBM/MIT,
para a Marinha norte–americana, contando com memória de núcleo de
ferrite, uma linguagem compilada de alto nível que precedeu ao
FORTRAN e tempos de resposta compatíveis com a realidade.
1950: Aparecimento das primeiras pesquisas sobre Controle Digital na
literatura como conseqüência do aparecimento dos primeiros
computadores.
154
1957: Desenvolvimento do sistema de defesa aérea Semi Automatic
Ground Environment – SAGE, pela IBM, para a Força Aérea americana,
projetado especificamente para obter respostas em Tempo Real, uma
vez que este coordenava o fluxo de mensagens entre as estações de
radares de solo e as bases dos aviões interceptadores, reduzindo
drasticamente o tempo necessário para um ataque direto a um avião
bombardeiro inimigo. Considerado um dos primeiros sistemas online da
história.
1958: A Univac lança o computador Scientific 1103 com suporte a
interrupções assíncronas.
1959: American Airlines e IBM desenvolvem o sistema de reserva de
passagens automatizado (Semi Automated Business Research
Environment – SABRE), processo que até então era completamente
manual.
1962: Lançamento do Basic Executive da IBM, considerado o primeiro
Executivo em Tempo Real hospedado em computadores tipo mainframe.
1967: J. Martin publica um dos primeiros e certamente um dos mais
influentes livros (MARTIN, 1967) sobre Sistemas em Tempo Real.
1970: A Digital Equipment Corporation – DEC e a Hewlet Packard – HP
lançam os primeiros Sistemas Operacionais em Tempo Real para
minicomputadores, respectivamente: Real Time System Executive –
RSX–11 para computadores PDP–11 e Real Time Executive – RTE para
os sistemas da série HP–1000.
1970s: As pesquisas em Controle Digital ganham impulso devido ao
aparecimento dos microprocessadores baratos e confiáveis.
1973: Liu e Layland publicam seu trabalho (LIU e LAYLAND, 1973)
sobre a teoria do RMS que vem sendo significantemente refinada por
155
mais de 30 anos, tornando–se uma teoria mais prática para uso no
desenvolvimento de sistemas.
1980s: Aparecimento dos primeiros Sistemas Operacionais em Tempo
Real (Real Time Operating Systems – RTOS) hospedados em
computadores baseados em microprocessadores: Intel RMX–80,
Motorola MROS 68K, VRTX e outros.
1983: O Departamento de Defesa norte americano desenvolve a
linguagem Ada 83, voltada para sistemas de missão crítica.
1988: John Stankovic publica um importante trabalho (STANKOVIC,
1988) conceituando e caracterizando os RTSs com foco em aspectos
mal interpretados sobre a área.
1980s e 1990s: Grande proliferação de trabalhos teóricos voltados à
melhora em termos de previsibilidade e confiabilidade dos RTSs, além
de questões envolvendo sistemas multiprocessados.
1995: Surge a linguagem Ada 95, um refinamento de sua predecessora
Ada 83.
2000s: Proliferação de trabalhos relativos à comunicação em Tempo
Real e processamento distribuído.
A.3 Agendador Cíclico Executivo (Cyclic Executive Scheduler – CES)
Também conhecido como Agendador em Linha de Tempo (Timeline Scheduler
– TS) o CES fornece um agendamento altamente previsível de tarefas
mediante a criação de um esquema, pré–definido em tempo de projeto, de
intercalação e seqüenciamento determinísticos das tarefas que são atribuídas a
156
intervalos de tempo específicos. É uma das abordagens mais utilizadas no trato
de tarefas periódicas em sistemas militares e de controle de tráfego aéreo.
A abordagem Cíclica Executiva consiste em dividir o eixo temporal em
intervalos (timeslices) de igual duração dentro dos quais uma ou mais tarefas
são periodicamente alocadas para execução, sendo o valor deste intervalo
denominado ciclo menor (minor cycle) ou quadro menor (minor frame)
correspondente ao máximo divisor comum dos períodos do conjunto de tarefas.
O ciclo maior (major cycle) ou hiperperíodo (hyper–period) é o tempo mínimo
necessário para executar todas as tarefas garantindo o cumprimento de todos
os prazos limites e corresponde ao mínimo múltiplo comum dos períodos das
tarefas (BUTTAZZO 2002, LAPLANTE 2004). Como não há preempção (uma
vez iniciada, uma tarefa não é interrompida até seu término), o ciclo menor
deve ser longo o suficiente de forma que todas as tarefas referentes ao Ciclo
possam iniciar e completar o processamento.
A Tabela A.1 mostra um conjunto de tarefas a ser agendado pelo CES.
Tabela A.1 – Exemplo de conjunto de tarefas: CES.
Tarefa
(i) T. Comput.
(Ci)
Período
(Ti)
1 10 25
2 8 25
3 5 50
4 4 50
5 2 100
A Figura A.8 mostra uma possível Linha de Tempo para o conjunto de tarefas
dado agendado pelo CES.
157
Para garantir a priori que o agendamento é exeqüível em um determinado
processador, é suficiente conhecer o Worst Case Execution Time – WCET
de cada tarefa e verificar se a soma da execução dentro de cada intervalo é
menor ou igual ao ciclo menor.
As principais vantagens do CES:
Alto grau de determinismo e conseqüentemente de previsibilidade
facilitando a verificação (seqüência de execução fixa).
Eficiência de agendamento e gerenciamento das tarefas (todas as
decisões quanto ao agendamento e à execução são tomadas à priori,
durante fase de projeto, minimizando perdas de tempo devido ao
chaveamento de contexto durante execução).
Facilidade de compreensão e implementação do algoritmo (basicamente
resume–se em seguir uma tabela de despachamento de tarefas).
100 0 10 20 30 40
Tempo
50 60 70 80 90
Execução
Tarefa 1 Tarefa 2 Tarefa 3
Tarefa 4 Tarefa 5
Ciclo Menor
Ciclo Maior
Interrupção
Figura A.8 – Linha de tempo do Agendador Cíclico Executivo.
158
Principais problemas do CES
Dificuldade de manutenção (decisões de agendamento fortemente
acopladas com o código das tarefas).
Demanda total conhecimento dos requisitos durante a fase de projeto.
Dificuldade ou impossibilidade de incorporação de novos requisitos após
projeto.
Dificuldade em incorporar tarefas não periódicas
Dificuldade em se acomodar as diferentes tarefas na estrutura de ciclo
maior e ciclo menor, principalmente para um grande número de tarefas
(necessidade de períodos múltiplos). A construção do Cíclico Executivo
é um problema NP–árduo, o que torna a análise inviável para um
número grande de tarefas (BURNS e WELLINGS, 1996).
Baixo aproveitamento de recursos (capacidade de processamento não
aproveitada nos intervalos de tempo entre o término da última tarefa de
cada ciclo menor e o início do próximo Ciclo).
Observando a indústria de equipamentos aviônicos, percebe–se que uma
grande parte dos sistemas em Tempo Real Rígidos, ou seja, críticos com
relação à segurança (safety critical), empregam o tradicional CES e o motivo
para isso, além da tradição em si, advém de seu alto grau de determinismo, o
que facilita o processo de verificação e a certificação destes equipamentos.
Porém esse mesmo determinismo constitui na maior causa das desvantagens
deste agendador.
159
A.4 Agendador RMS – Exemplos
Um exemplo do algoritmo de agendamento RMS é mostrado abaixo por meio
de um gráfico de Linha de Tempo (timeline) para o seguinte conjunto de três
tarefas:
Tabela A.2 – Exemplo de conjunto de tarefas: RMS 1.
Tarefa
(i) T. Comput.
(Ci)
Período
(Ti)
Prioridade
(Pi)
Utiliz.
(Ui)
1 12 50 1 0.24
2 10 40 2 0.25
3 10 30 3 0.33
0.82
Note–se que a utilização do processador é de 0.82 (82%), valor este acima do
limite de ULUB = 0.78, de forma que o Teste de Agendabilidade indica que este
conjunto de tarefas não é exeqüível.
O gráfico de Linha de Tempo, além de mostrar o comportamento de cada
tarefa ao longo do tempo (intercalação de execução), também permite testar a
agendabilidade do conjunto de tarefas de forma qualitativa pela observação do
instante de liberação e do instante de finalização de cada tarefa, contabilizando
assim, pela diferença entre os dois valores, o tempo de resposta obtido para
cada tarefa. A comparação deste valor com o respectivo prazo limite permite
verificar se ocorre algum estouro de prazo limite. No caso específico do
agendamento RMS, no qual o prazo limite corresponde ao período, basta
verificar se todas as tarefas finalizam antes no início do próximo período de
execução. A questão é: por quanto tempo deve–se observar a Linha de Tempo
para se concluir que não haverá estouro de algum prazo limite? Para um
160
conjunto de tarefas cujos instantes de liberação são todos coincidentes, pode
ser demonstrado que uma Linha de Tempo cujo comprimento corresponde ao
maior período dentre as tarefas é o suficiente (LIU e LAYLAND, 1973). A este
instante de tempo dá–se a denominação de instante crítico pois corresponde
ao instante de tempo de requisição de uma tarefa que resultará no maior tempo
de resposta possível (é a situação que impõe a maior carga possível ao
processador).
0 10 20 30 40
Tempo
50 60 70 80 90 100
Execução
Tarefa 1
Tarefa 2
Tarefa 3
Tarefa 1 ativa
Tarefa 2 ativa
Tarefa 3 ativa
Preempção
Instante de liberação
Instante de finalização – prazo cumprido
Instante de finalização – prazo não cumprido
Figura A.9 – Linha de Tempo com conjunto de tarefas RMS 1.
161
No exemplo acima, assume–se a pior situação para o sistema, que é aquela na
qual todas as tarefas são liberadas no mesmo instante (t = 0 no caso). A tarefa
τ3, de menor período (30 unidades de tempo) possui a maior prioridade e, por
essa razão, executa até completar seu trabalho consumindo as 10 unidades de
tempo previstas como tempo de computação. A partir desse instante, a tarefa
seguinte na ordem de prioridade τ2 executa por 10 unidades de tempo quando
a tarefa τ1, menos prioritária é permitida executar. Note–se agora que antes
mesmo que esta última termine a execução (tempo de computação de 12
unidades de tempo), chega o momento de execução (30 unidades de tempo
após o início da primeira execução) da tarefa prioritária T3. A tarefa τ1 é
suspensa imediatamente e T3 executa até o final quanto chega o momento de
execução de τ2. Ocorre que ao término de τ2, quando a tarefa τ1 é permitida
executar e completar as duas unidades de tempo faltantes, já transcorreram 50
unidades de tempo correspondentes ao período de τ1 e a continuidade do
processamento dessa instância da tarefa τ1 não pode ocorrer. O
processamento inacabado é definitivamente abortado já que agora essa tarefa
deve dar início a uma nova execução. Confirma–se, portanto, como previsto, a
sobrecarga do processador e, portanto, este conjunto de tarefas não é
exeqüível.
O próximo exemplo do algoritmo de agendamento RM corresponde ao conjunto
de tarefas relacionado abaixo:
162
Tabela A.3 – Exemplo de conjunto de tarefas: RMS 2.
Tarefa
(i) T. Comput.
(Ci) Período
(Ti) Prioridade
(Pi) Utiliz.
(Ui)
1 25 80 1 0.31
2 8 30 2 0.27
3 4 20 3 0.20
0.78
Este conjunto é agendável pelo RMS, uma vez que a utilização do processador
corresponde ao máximo permitido para três tarefas (ULUB(3) = 0.78). Na Figura
A.10 observa–se o resultado do agendamento desde conjunto, confirmando o
cumprimento de todos os prazos limites a partir do instante crítico.
Tempo
Tarefa 3
0 10 20 30 40 50 60 70 80 90 100
Execução
Tarefa 1
Tarefa 2
Figura A.10 – Linha de Tempo com conjunto de tarefas RMS 2.
163
Um terceiro exemplo do algoritmo de agendamento RM é mostrado para o
conjunto de tarefas dado a seguir:
Tabela A.4 – Exemplo de conjunto de tarefas: RMS 3.
Tarefa
(i) T. Comput.
(Ci) Período
(Ti) Prioridade
(Pi) Utiliz.
(Ui)
1 40 80 1 0.50
2 10 40 2 0.25
3 5 20 3 0.25
1.00
Perceber que novamente o conjunto de tarefas não é exeqüível, uma vez que a
utilização do processador neste caso é 1.00 (100%), bem acima do limite de
0.78, portanto o Teste de Agendabilidade falha novamente.
164
No entanto, apesar da falha no teste, tal conjunto pôde ser agendado sem que
houvesse a sobrecarga, confirmando o fato do Teste de Agendabilidade ser
condição suficiente, porém não necessária.
0 10 20 30 40
Tempo
50 60 70 80 90 100
Execução
Tarefa 1
Tarefa 2
Tarefa 3
Figura A.11 – Linha de Tempo com conjunto de tarefas RMS 3.
165
APÊNDICE B – DIAGRAMAS DE CLASSES DO HRTSim
Os diagramas de classes representam graficamente os modelos objeto–
orientados dos elementos que compõem o núcleo da ferramenta HRTSim
incluindo: classes, enumerações, estruturas e demais abstrações de dados.
B.1 Diagrama de Classes Geral
166
B.2 Diagrama de Classes da Tarefa
167
B.3 Diagrama de Classes do Agendador
168
B.4 Diagrama de Classes do Despachador
169
B.5 Diagrama de Classes de Elementos Variados
171
APÊNDICE C – Manual de Instalação e de Operação do HRTSim
Para instalação e execução do HRTSim são necessários:
Microcomputador ou notebook compatível com IBM–PC.
Windows XP.
Microsoft DotNet Framework 2.0.
A simulação do SRT consiste em uma matriz de simulação que forma uma
Linha de Tempo (timeline) na qual cada elemento é uma estrutura de dados
TimeLineElement (Figura C.1 – Elemento da Linha de Tempo.Figura C.1) que
armazena o estado de execução de cada tarefa (linhas da matriz) num
determinado instante de tempo discreto (colunas da matriz).
Figura C.1 – Elemento da Linha de Tempo.
A quantidade de linhas da matriz corresponde ao número de tarefas do
conjunto agendado. A quantidade de colunas da matriz é determinada pela
duração da simulação, ou seja, da quantidade total de unidades de tempo. O
início da simulação se dá no instante 0 (primeiro elemento), avança passo a
passo, cada qual correspondente a uma unidade discreta de tempo, e termina
quando o número total de unidades de tempo final é alcançado.
172
As estruturas de dados (elementos da matriz) são preenchidas durante a
execução de uma máquina de estados finitos formada basicamente pelo
algoritmo de execução do despachador sobre os modelos das tarefas, de
acordo com a regra de seqüenciamento ditada pelo agendador.
As tarefas são modeladas (APÊNDICE B.2) basicamente por suas
características temporais:
Tipo (periódica ou aperiódica).
Período.
Prazo limite.
Tempo de computação (WCET).
Por seus parâmetros em tempo de execução:
Prioridade.
Tempo computado.
Estado.
Instante de liberação.
E por demais atributos como descrição, identificador e outros.
O ciclo de vida de cada tarefa segue uma seqüência de estados e as
correspondentes transições, controlados pelo despachador de acordo com a
Figura C.2.
173
Non–Existing: reflete a situação inicial antes da inicialização da tarefa
(processo de alocação e preenchimento das estruturas de dados que
representam a tarefa), portanto é um estado conceitual, que na verdade não
tem como ser atribuído a uma tarefa uma vez que, nesta situação, esta não
existe.
Dormant: estado da tarefa logo após sua criação, significando que a tarefa
está inicializada e pronta para ser criada.
Ready: tarefa pronta e colocada na fila de execução. Equivale a uma tarefa
recém inicializada e liberada (released); ou a uma tarefa “preemptada”.
Running: tarefa carregada na memória sendo executada pelo processador.
Figura C.2 – Estados de uma tarefa.
Terminated
Dormant Ready
Running
Suspended
Create
Run
Suspend
Resume
Interrupt
Terminate
Initialize
Non–Existing
Initialize
174
Suspended: estado de suspensão no qual a tarefa pára a execução devido a
algum bloqueio de recursos (e.g. compartilhamento de dados, espera de
dispositivo de I/O, etc.).
Terminated: tarefa autofinalizada ou abortada pelo despachador.
A liberação das tarefas periódicas se dá pelo tempo de relógio de acordo com
os respectivos períodos. Já no caso das tarefas aperiódicas, existe um objeto
AsyncEvents (APÊNDICE B.1) que simula o disparo de eventos aperiódicos
cujos instantes podem ser aleatórios (porém respeitando o MIT) ou pré
definidos pelo usuário (deve–se atentar que o MIT não é assegurado pelo
sistema, de forma que o usuário pode, neste caso, intencionalmente ou não
violá–lo, tornando o conjunto de tarefas não–exeqüível).
O algoritmo de execução do despachador implementado no objeto Dispatcher
(APÊNDICE B.4) simula a execução preemptiva das tarefas periódicas
seqüenciando–as de acordo com suas prioridades, previamente atribuídas pelo
objeto agendador, no caso o RateMonotonicScheduler (APÊNDICE B.3) que,
além de atribuir prioridades, aplica os testes de agendabilidade ao conjunto de
tarefas (baseado em utilização do processador e análise dos tempos de
resposta). Além disso o despachador atende aos eventos assíncronos, controla
o processo de restauração e consumo das capacidades dos servidores
periódicos e executa as tarefas aperiódicas de acordo com o método escolhido
dentre os implementados (BS, PS ou SS).
O HTRSim possui as seguintes características:
A escala de tempo é adimensional, portanto tanto o transcorrer deste,
bem como os parâmetros temporais das tarefas, são mensurados em
termos de quantidades de uma unidade de tempo genérica.
O instante inicial de simulação (t = 0) corresponde ao instante crítico
(todas as tarefas periódicas liberadas simultaneamente).
175
Apenas uma única instância de cada tarefa pode estar ativa num
determinado instante.
Tarefas executam até o final consumindo o tempo de computação
previsto independentemente do prazo limite cumprido ou não, ou seja, a
perda de prazo limite não implica no aborto da tarefa.
Tarefas mais prioritárias são as que possuem como prioridade valores
mais altos.
O agendador atribui prioridades a partir do valor 1 (menor prioridade de
tempo real).
Prioridade 0 corresponde ao processamento em segundo plano
(background).
Um servidor periódico é responsável pelo atendimento de um único
evento de uma tarefa aperiódica.
O período de uma tarefa aperiódica corresponde, na verdade, ao
período do respectivo servidor periódico.
A análise a priori determina a agendabilidade do conjunto de tarefas por meio
do teste baseado em utilização do processador (LIU e LAYLAND, 1973) e pela
análise dos tempos de resposta das tarefas (HARTER, 1984, JOSEPH e
PANDYA, 1986). A análise a posteriori é baseada no histórico da Linha de
Tempo e nos parâmetros de execução das tarefas e relata as eventuais perdas
de prazos limites, além de contabilizar os valores máximos e médios (média
móvel) dos tempos de resposta obtidos durante a simulação. A média móvel é
arredondada para o menor valor inteiro superior.
Após a execução, a ferramenta permite a visualização gráfica da simulação por
meio de gráficos de Linha de Tempo que ilustram o comportamento (estado de
execução) de cada tarefa ao longo do tempo (BURNS e WELLINGS, 1996).
176
Nos gráficos pode–se obter informações sobre os instantes de liberação e
finalização das tarefas, eventuais perdas de prazos limites, instantes de
ocorrência dos eventos aperiódicos e preempção. Além dos gráficos de Linha
de Tempo, nos casos em que exista uma ou mais tarefas aperiódicas atendidas
por servidores periódicos, também são traçadas curvas de capacidade dos
servidores, a partir das quais é possível observar a demanda de
processamento por parte das tarefas aperiódicas ao longo do tempo. A Figura
C.3 apresenta a legenda com os principais elementos gráficos do HRTSim.
Tanto o conjunto de tarefas, as configurações de agendamento e
despachamento como a simulação em si fazem parte de um projeto que pode
ser salvo e posteriormente carregado de um arquivo em disco.
O aplicativo permite o agendamento e o despachamento misto de tarefas
periódicas e de tarefas não periódicas, estas últimas mediante uma das três
possíveis políticas suportadas:
Tarefa em execução
Tarefa “preemptada”
Instante de liberação da tarefa
Instante de finalização da tarefa
Prazo perdido da tarefa
Instante do evento aperiódico
Figura C.3 – Legenda dos gráficos de Linha de Tempo do HRTSim.
177
Agendamento em Segundo Plano (BS).
Servidor de Varredura (PS).
Servidor Esporádico (SS).
Pelo fato de os algoritmos Servidor Adiável e Servidor de Troca de Prioridades
apresentarem restrições ao agendamento de tarefas esporádicas e não
apresentarem vantagens sobre o Servidor Esporádico, estes não foram
implementados na versão corrente da ferramenta, não sendo, portanto, alvos
de simulação a análise.
Os modelos e algoritmos do HRTSim foram idealizados e projetados visando a
simulação de Sistemas em Tempo Real Rígido e, embora o Agendamento em
Segundo Plano não forneça garantia de atendimento dos prazos limites das
tarefas aperiódicas com prazos rígidos (esporádicas), a decisão de suportá–lo
vem do fato de este ser o algoritmo básico mais simples de atendimento
aperiódico, servindo, portanto, como referência ou base de comparação com os
demais. Vale ressaltar que esta política não afeta os prazos limites periódicos,
ou seja, as tarefas periódicas são executadas em regime de tempo real rígido,
sem sofrer influência da falta de garantias aperiódicas. O despachamento em
segundo plano se faz mediante a atribuição da menor prioridade do sistema
(P = 0) a todas as tarefas aperiódicas. Desta maneira, estas serão executadas
durante os intervalos de tempo nos quais não há nenhuma tarefa periódica
ativa. As tarefas aperiódicas são excluídas do Teste de Agendabilidade RMS e
da análise do tempo de resposta.
No caso do Servidor de Varredura, é criada uma tarefa servidora periódica para
cada tarefa esporádica existente no conjunto de tarefas. A cada um desses
servidores é atribuída uma capacidade cujo valor nominal corresponde ao
tempo de computação de pior caso (WCET) da respectiva tarefa periódica;
portanto, a cada servidor é atribuída capacidade suficiente e necessária ao
processamento integral de um único evento aperiódico por período de
178
execução da tarefa servidora, atribuição esta que ocorre a cada instante de
liberação da tarefa servidora. Nestes instantes de tempo ocorre a verificação
da fila de eventos. Caso esteja vazia, a capacidade é zerada; do contrário, a
tarefa é executada e a capacidade é consumida à medida que a execução
prossegue. Tanto o teste RMS quanto o RTA levam em conta tanto as tarefas
periódicas ordinárias como as tarefas servidoras afim de determinar a
agendabilidade periódica. Porém, isto por si só não garante os prazos limites
aperiódicos, que demandam também uma verificação específica, feita pela
ferramenta de acordo com o teste definido pela Equação 2.24.
Processo semelhante é feito no caso do Servidor Esporádico: é criada uma
tarefa servidora periódica e um objeto gerenciador de capacidade para cada
tarefa esporádica cujo valor máximo (restauração plena) inicial corresponde ao
WCET da respectiva tarefa esporádica. Além do valor da capacidade, também é
registrado em uma fila o instante de tempo em que deve ocorrer a próxima
restauração (RTs), lembrando que este corresponde ao instante no qual se dá o
início de execução da tarefa acrescido do período do servidor. A cada passo de
execução (tique de tempo) o tempo atual é comparado com o RTs e quando
ocorre a igualdade, a capacidade é restaurada. O valor restaurado corresponde
apenas à capacidade consumida até o instante corrente, distintamente do PS
no qual a capacidade é sempre restaurada no seu valor máximo (além do
instante de restauração periódico, havendo ou não consumo).
ÌNDICE POR ASSUNTO
ABSTRACT, 13 Agendabilidade, 54 Agendador, 49
Agendador de longo prazo, 49 Cíclico Executivo, 155 Funções Básicas, 50 Pesquisa de Operações, 49 Teste de Agendabilidade, 51
Agendador a Taxas Monotônicas, 51 Aplicações, 53
179
Exeqüibilidade, 56 Premissas, 55
Agendamento de Tarefas Linha de Tempo, 159
Agendamento de Tarefas Aperiódicas, 60 Abordagens, 61 Tarefas Esporádicas, 61
Análise de Tempos de Resposta, 58 ANÁLISE E CONCLUSÕES, 127 Atribuição de prioridades, 52
Cíclico Executivo Ciclo Maior, 156 Ciclo Menor, 156 Hiperperíodo, 156 Quadro Menor, 156
Computador de Missão, 93 Controle
Teorema da Taxa de Dados, 36 Teoria de Controle, 36
Controle Digital, 36
DESENVOLVIMENTO, 91 Despachador, 48
Agendador de curto prazo, 48
Diagramas de Classes, 165
Exeqüibilidade, 54
INTRODUÇÃO, 27
LISTA DE FIGURAS, 17 LISTA DE SIGLAS E ABREVIATURAS, 21 LISTA DE SÍMBOLOS, 25 LISTA DE TABELAS, 19
Objetivo, 29 Organização, 30
Prioridades, 52 Atribuição Dinâmica, 52
Prioridades Atribuição Estática, 52
Programas Aplicativos e Tarefas, 42
REFERÊNCIAS BIBLIOGRÁFICAS, 137
Serviço em Segundo Plano, 62 Servidor de Varredura, 67 Servidor Periódico, 65
180
SIMULAÇÕES E RESULTADOS, 101 Sistema de Segurança Crítica, 148 Sistema Operacional em Tempo Real, 150
Estrutura, 151 Executivo em Tempo Real, 153 Núcleo, 151
Sistemas Críticos de Tempo Real, 148 Sistemas em Tempo Real
Sistemas em Tempo Real Firme, 147 Sistemas em Tempo Real Real, 150 Sistemas em Tempo Real Rígido, 148
Sistemas em Tempo Real Características, 41 Classificação, 144 Conceitos Básicos, 39 Definição, 41 História, 39 Introdução, 27 Processamento em Lote, 145 Sistemas em Tempo Real Flexível, 146 Sistemas Interativos, 145
Sistemas Em Tempo Real Origem do Termo Tempo Real, 38
Sobrecarga, 54
Tarefas Caracterização, 45 Classificação, 43 Concorrência, 50 Definição, 42 Estados, 172 Execução Não Preemptiva, 47 Execução Preemptiva, 48 Instante Crítico, 160 Minimum Interarrival Time, 44 Tarefa Aperiódica, 43 Tarefa Esporádica, 44 Tarefa Periódica, 43 Utilidade, 145
Utilidade de um Evento, 145
PUBLICAÇÕES TÉCNICO-CIENTÍFICAS EDITADAS PELO INPE
Teses e Dissertações (TDI)
Manuais Técnicos (MAN)
Teses e Dissertações apresentadas nos Cursos de Pós-Graduação do INPE.
São publicações de caráter técnico que incluem normas, procedimentos, instruções e orientações.
Notas Técnico-Científicas (NTC)
Relatórios de Pesquisa (RPQ)
Incluem resultados preliminares de pesquisa, descrição de equipamentos, descrição e ou documentação de programa de computador, descrição de sistemas e experimentos, apresenta- ção de testes, dados, atlas, e docu- mentação de projetos de engenharia.
Reportam resultados ou progressos de pesquisas tanto de natureza técnica quanto científica, cujo nível seja compatível com o de uma publicação em periódico nacional ou internacional.
Propostas e Relatórios de Projetos (PRP)
Publicações Didáticas (PUD)
São propostas de projetos técnico-científicos e relatórios de acompanha-mento de projetos, atividades e convê- nios.
Incluem apostilas, notas de aula e manuais didáticos.
Publicações Seriadas
Programas de Computador (PDC)
São os seriados técnico-científicos: boletins, periódicos, anuários e anais de eventos (simpósios e congressos). Constam destas publicações o Internacional Standard Serial Number (ISSN), que é um código único e definitivo para identificação de títulos de seriados.
São a seqüência de instruções ou códigos, expressos em uma linguagem de programação compilada ou inter- pretada, a ser executada por um computador para alcançar um determi- nado objetivo. São aceitos tanto programas fonte quanto executáveis.
Pré-publicações (PRE)
Todos os artigos publicados em periódicos, anais e como capítulos de livros.
Livros Grátis( http://www.livrosgratis.com.br )
Milhares de Livros para Download: Baixar livros de AdministraçãoBaixar livros de AgronomiaBaixar livros de ArquiteturaBaixar livros de ArtesBaixar livros de AstronomiaBaixar livros de Biologia GeralBaixar livros de Ciência da ComputaçãoBaixar livros de Ciência da InformaçãoBaixar livros de Ciência PolíticaBaixar livros de Ciências da SaúdeBaixar livros de ComunicaçãoBaixar livros do Conselho Nacional de Educação - CNEBaixar livros de Defesa civilBaixar livros de DireitoBaixar livros de Direitos humanosBaixar livros de EconomiaBaixar livros de Economia DomésticaBaixar livros de EducaçãoBaixar livros de Educação - TrânsitoBaixar livros de Educação FísicaBaixar livros de Engenharia AeroespacialBaixar livros de FarmáciaBaixar livros de FilosofiaBaixar livros de FísicaBaixar livros de GeociênciasBaixar livros de GeografiaBaixar livros de HistóriaBaixar livros de Línguas
Baixar livros de LiteraturaBaixar livros de Literatura de CordelBaixar livros de Literatura InfantilBaixar livros de MatemáticaBaixar livros de MedicinaBaixar livros de Medicina VeterináriaBaixar livros de Meio AmbienteBaixar livros de MeteorologiaBaixar Monografias e TCCBaixar livros MultidisciplinarBaixar livros de MúsicaBaixar livros de PsicologiaBaixar livros de QuímicaBaixar livros de Saúde ColetivaBaixar livros de Serviço SocialBaixar livros de SociologiaBaixar livros de TeologiaBaixar livros de TrabalhoBaixar livros de Turismo
