Escalonamento em Sistemas de Tempo Real

Prévia do material em texto

SISTEMAS DE TEMPO REAL 
AULA 6 – ESCALONAMENTO (1) 
Prof.: Danilo Coimbra 
(danilo.dcc.ufba@gmail.com) 
(coimbra.danilo@ufba.br) 
1 
Sumário 
!  Introdução 
!  Classificação 
!  Restrições temporais 
!  Relações de Precedência e Exclusão 
!  Abordagens de Escalonamento 
de Tempo Real 
2 
Introdução 
!  Sistemas de Tempo Real 
!  Sistemas em que a noção de tempo e de concorrência são 
tratadas explicitamente 
"  Escalonamento tem importância fundamental 
!  Conceitos e técnicas de escalonamento formam a 
previsibilidade do comportamento do sistema 
3 
Introdução 
!  Previsibilidade 
!  Capacidade de afirmar algo sobre o comportamento 
futuro do sistema 
!  Antecipar se os processamentos serão executados dentro 
dos prazos especificados 
!  Determinista 
"  Todos os deadlines são respeitados 
!  Probabilista 
"  Probabilidade dos deadlines serem respeitados (estimativas) 
4 
Introdução 
!  Previsibilidade determina implicações em todos os 
níveis 
!  Linguagens 
!  Sistemas Operacionais 
!  Comunicação 
!  Arquitetura de Computador 
!  etc 
5 
Introdução 
Escalonamento 
!  Está associado com um conjunto de tarefas do sistema 
!  Determina quando serão executadas cada uma dessas 
tarefas 
!  A ordem de execução dessas tarefas 
!  Como serão alocados os recursos para essas tarefas 
!  Determina a alocação de cada uma dessas tarefas a um 
processador ou nó 
"  Sistemas multiprocessados ou distribuídos 
6 
Introdução 
Escalonamento: objetivo 
!  Sistemas convencionais 
!  Maximizar o rendimento (quantidade de tarefas por 
unidades de tempo) e/ou 
!  Minimizar o tempo de espera das tarefas 
!  Sistemas de tempo real 
!  Cumprir o deadline de cada tarefa 
!  Garantir que cada tarefa complete sua execução em um 
tempo definido 
7 
Introdução 
Elementos de um Escalonamento 
!  Escalonamento 
!  Identifica o procedimento de ordenar tarefas na fila de 
Pronto 
!  Escala de Execução (schedule) 
!  É uma ordenação ou lista que indica a ordem de ocupação 
do processador por um conjunto de tarefas disponíveis 
!  Descreve quando cada tarefa ocupa cada recurso 
!  Escalonador (scheduler) 
!  Componente do sistema reponsável pela gerência dos 
recursos, ou seja, pela gestão do precessador (em tempo 
de execução) 
8 
Classificação 
!  Classificação dos algoritmos de escalonamento 
(Kopetz, 2002) 
9 
Escalonamento de 
tempo real 
Hard 
Static Dinâmico 
Preemptivo 
Não 
Preemptivo 
Não 
Preemptivo Preemptivo 
Soft 
Classificação 
Escalonamento Dinânico vs Estático (1/2) 
!  Dinâmico (on-line) 
!  Realiza as decisões do escalonamento em tempo de 
execução 
!  Selecionando uma ou mais tarefas/threads “prontas” 
!  Escalonadores dinâmicos são flexíveis e se adaptam a um 
cenário de tarefas em evolução 
!  Consideram apenas as requisições das tarefas atuais 
!  O esforço em tempo de execução envolvido em encontrar 
um escalonamento pode ser substancial 
"  Gargalo 
 
10 
Classificação 
Escalonamento Dinânico vs Estático (2/2) 
!  Estático 
!  Realiza as decisões de escalonamento em um tempo 
anterior ao de execução (“tempo de compilação”) 
!  Necessita de conhecimento prévio completo do conjunto de 
características das tarefas. Ex.: 
"  Tempo máximo de execução 
"  Variáveis de precedência 
"  Deadlines 
"  Variáveis de exclusão mútua 
"  etc 
11 
Classificação 
Escalonamento Preemptivo vs Não Preemptivo 
!  Preemptivo 
!  A tarefa de execução atual pode ser preemptida 
"  Interrompida, se outra tarefa mais urgente requisitar o serviço 
!  Não preemptivo 
!  A tarefa de execução atual não será interrompida até que 
ela decida desalocar os recursos (normalmente depois 
completada) 
!  É adequado em um cenário onde há muitas tarefas curtas 
sendo executadas 
12 
Classificação 
Escalonamento Centralizado vc Distribuído 
!  Centralizado 
!  Todas as decisões são centralizadas em um escalonador 
!  Requisita informação atualizada das situações de carga de 
todos os nós (sistema distribuído dinâmico) 
!  Ponto crítico de falha (comunicação) 
"  Gargalho 
!  Distribuído 
!  Possui algoritmos distribuídos cooperativos para a solução 
do problema de escalonamento 
13 
Modelo de Tarefas 
!  Tarefa 
!  Segmento de código cuja execução é sequencial 
!  Alguns fatores são impostos em tarefas em STR 
!  Restrições temporais 
!  Relações de Precedência e de Exclusão 
!  Necessário um Modelo de Tarefas para considerar 
esses fatores no problema de escalonamento 
14 
Modelo de Tarefas- Restrições Temporais 
!  Tipicamente, as tarefas de tempo real estão sujeitas a 
prazos: deadlines 
!  Classificadas em 
!  Críticas x não críticas 
"  Consequências de uma tarefa ser concluída após seu deadline 
!  Periódicas x Aperíodicas 
"  Baseada nas regularidades das ativações 
15 
Modelo de Tarefas- Restrições Temporais 
!  Tarefas Cíticas (hard) 
!  Se completada depois de seu deadline pode causar falhas 
catastróficas no sistema de tempo real e em seu ambiente 
!  Danos irreversíveis em equipamentos ou ainda, em perda 
de vidas humanas 
16 
Modelo de Tarefas- Restrições Temporais 
!  Tarefas Brandas ou não Críticas (soft) 
!  Se completadas depois de seus deadlines, no máximo 
implicam numa diminuição de desempenho do sistema 
!  Falhas são identificadas como benignas, onde a 
consequência do desvio do comportamento normal não 
representa um custo muito significativo 
17 
Modelo de Tarefas- Restrições Temporais 
!  Tarefas Periódicas 
!  Quando as ativações do processamento de uma tarefa 
ocorrem numa sequência, uma só ativação por intervalo 
regular é chamado de Período 
!  Essas ativações formam o conjunto de diferentes instâncias 
da tarefa 
!  Assim, a primeira ativação de uma tarefa periódica ocorre 
na origem dos tempos considerados na aplicação (em t=0) 
18 
Modelo de Tarefas- Restrições Temporais 
!  Tarefas Aperiódicas ou Tarefas Assíncronas 
! Quando a ativação do processamento de uma tarefa 
responde a eventos internos ou externos, sem uma 
sequência regular 
! Se essas ativações tem tais características, as tarefas 
são ditas aperiódicas 
19 
Modelo de Tarefas- Restrições Temporais 
!  Tarefas periódicas usualmente são associadas a hard 
deadlines, ou seja, são tarefas críticas 
!  Pela regularidade e pela previsibilidade 
!  Tarefas aperiódicas são associadas a tarefas 
brandas, exatamente por ter deadline softs 
!  Por falta de previsibilidade 
!  Tarefas esporádicas são aperiódicas (deadline hard) 
!  Característica central: a restrição de um intervalo mínimo 
conhecido entre duas ativações consecutivas 
20 
Modelo de Tarefas- Restrições Temporais 
Restrições temporais (tempos) no comportamento de 
uma tarefa (1/2) 
!  Tempo de computação (Computation Time) 
!  O tempo de computação de uma tarefa é o tempo necessário 
para a execução completa da tarefa 
!  Tempo de início (Start Time) 
!  Esse tempo corresponde ao instante de início do 
processamento da tarefa em uma ativação 
!  Tempo de término (Completion Time) 
!  É o instante de tempo em que se completa a execução da 
tarefa na ativação. 
21 
Modelo de Tarefas- Restrições Temporais 
Restrições temporais (tempos) no comportamento de uma 
tarefa (2/2) 
!  Tempo de chegada (Arrival Time) 
!  É o instante em que o escalonador toma conhecimento de uma 
ativação dessa tarefa 
!  Em tarefas periódicas, o tempo de chegada coincide sempre 
com o início do período da ativação. 
!  As tarefas aperiódicas apresentam o tempo de chegada 
coincidindo com o tempo da requisição do processamento 
aperiódico!  Tempo de liberação (Release Time) 
!  O tempo de liberação de uma tarefa coincide com o instante de 
sua inclusão na fila de Pronto (fila de tarefas prontas) para 
executar 
22 
Modelo de Tarefas- Restrições Temporais 
!  Dependendo do modelo assumido, o tempo de 
liberação pode ou não coincidir com o tempo de 
chegada da tarefa 
!  Tão logo uma tarefa chega, ela é liberada na fila de Pronto 
!  Contudo, o pooling do escalonador ativado por tempo 
("tick scheduler”) ou o bloqueio na recepção de uma tarefa 
de evento 
!  Pode ocasionar a não coincidência dos tempos de chegada com 
as liberações (Release Jitter) 
"  representa a máxima variação dos tempos de liberação das instâncias 
da tarefa 
23 
Modelo de Tarefas- Restrições Temporais 
24 
Modelo de Tarefas- Restrições Temporais 
25 
Descrição de Tarefa Períodica 
!  A tarefa periódica Ti pode ser descrita pela quádrupla 
(Ji , Ci , Pi , Di ) 
!  Ci representa o tempo de computação da tarefa 
!  Pi é o período da tarefa (tempo entre 2 ativações) 
!  Di é o deadline da tarefa 
!  Ji é o release jitter da tarefa (pior situação de liberação da 
tarefa) 
Modelo de Tarefas- Restrições Temporais 
26 
Descrição de Tarefa Períodica 
 
 
 
 
 
 
 
 (Ji , Ci , Pi , Di ) 
Modelo de Tarefas- Restrições Temporais 
27 
Descrição de Tarefa Períodica 
 
 
 
 
 
 
 
 (Ji , Ci , Pi , Di ) 
Modelo de Tarefas- Restrições Temporais 
28 
Descrição de Tarefa Períodica 
(Ji , Ci , Pi , Di ) 
 
 
 
 
 
 
 
 
Modelo de Tarefas- Restrições Temporais 
29 
Descrição de Tarefa Períodica 
(Ji , Ci , Pi , Di ) 
 
 
 
 
 
 
 
 
Modelo de Tarefas- Restrições Temporais 
30 
Descrição de Tarefa Períodica 
!  Nessa representação de tarefas periódicas, Ji e Di são 
grandezas relativas (intervalos), medidas a partir do início do 
período Pi 
!  O deadline absoluto e o tempo de liberação da k-ésima ativação 
da tarefa periódica Ti são determinados a partir dos períodos 
anteriores: 
 
 
 
 
 
 
 
Modelo de Tarefas- Restrições Temporais 
31 
Descrição de Tarefa Períodica 
 
 
 
 
 
 
 3a ativação (k=3) Pi= 4ms 
Di=3ms 
Ji = 1ms 
3a ativação 
Dik = (3-1)*4 + 3 = 11ms 
Ri = (3-1)*4 + 1 = 9ms 
tempo de liberação da terceira ativação da 
tarefa 
deadline absoluto 
Modelo de Tarefas- Restrições Temporais 
32 
Descrição de Tarefa Períodica 
 
 
 
 
 
 
 3a ativação (k=3) Pi= 4ms 
Di=3ms 
Ji = 1ms 
3a ativação 
Dik = (3-1)*4 + 3 = 11ms 
Ri = (3-1)*4 + 1 = 9ms 
tempo de liberação da terceira ativação da 
tarefa 
deadline absoluto 
Modelo de Tarefas- Restrições Temporais 
33 
Descrição de Tarefa Períodica 
 
 
 
 
 
 
 3a ativação (k=3) Pi= 4ms 
Di=3ms 
Ji = 1ms 
3a ativação 
Dik = (3-1)*4 + 3 = 11ms 
Ri = (3-1)*4 + 1 = 9ms 
tempo de liberação da terceira ativação da 
tarefa 
deadline absoluto 
Modelo de Tarefas- Restrições Temporais 
34 
Descrição de Tarefa Períodica 
!  Cada ativação da tarefa periódica é definida pelos seus tempos 
absolutos 
"  ai = tempos de chegada 
"  ri = tempos de liberação 
"  sti =tempos de início 
"  cti=Tempos de término 
"  di=Termpos de deadline 
 
 
 
 
 
 
Modelo de Tarefas- Restrições Temporais 
35 
Descrição de Tarefa Esporádica 
!  Descrita pela tripla (Ci, Di, mini) 
!  Ci = tempo de computação 
!  Di é o deadline relativo, medido a partir do instante da requisição 
do processamento aperiódico (chegada da tarefa esporádica) 
!  mini = mínimo intervado de tempo entre duas requisições 
consecutivas da tarefa esporádica 
!  A descrição de uma tarefa aperiódica se limite apenas às 
restrições Ci e Di 
Modelo de Tarefas- Restrições Temporais 
36 
Descrição de Tarefa Esporádica 
!  Descrita pela tripla (Ci, Di, mini) 
!  2 requisições 
!  Deadline absoluto (requisição 2) 
"  
 
Relações de Precedência e Exclusão 
37 
!  Em aplicações de tempo real, muitas vezes os 
processamentos não podem executar em ordem 
arbitrária 
!  Relação de precedência determina ordens parciais entre as 
mesmas 
!  Exemplo1: uma tarefa Tj é precedida por Ti, ou seja, 
Ti ( Ti -> Tj ). Tj somente inicia sua execução se após o término 
da execução de Ti 
!  Exemplo 2: A-> B. Tarefa A é predecessora de B. 
B é sucessora da tarefa A 
Relações de Precedência e Exclusão 
38 
!  As relações de precedência em um conjunto de tarefas 
usualmente são representadas na forma de um grafo 
acíclico orientado*, 
!  onde os nós correspondem às tarefas do conjunto e os 
arcos/flechas descrevem as relações de precedência 
existentes entre as tarefas 
!  Exemplo: ..(próximo slide) 
*É um grafo orientado, onde para qualquer vértice v, não há nenhuma ligação 
dirigida começando e acabando em v. 
Relações de Precedência e Exclusão 
39 
Relações de Precedência e Exclusão 
40 
!  Atividade 
!  Conjunto de tarefas interligadas por relações de 
precedência 
Relações de Precedência e Exclusão 
41 
!  Relações de exclusão 
!  Definido pelo compartilhamento de recursos em exclusão 
mútua 
!  Uma tarefa Ti exclui Tj quando a execução de uma seção 
crítica de Tj que manipula o recurso compartilhado não 
pode executar porque Ti já ocupa o recurso 
!  Relações de exclusão em escalonamentos dirigidos a 
prioridade podem levar a inversões de prioridades onde 
tarefas mais prioritárias são bloqueadas por tarefas menos 
prioritárias 
Relações de Precedência e Exclusão 
42 
!  Relações de exclusão mútua entre tarefas 
!  Tarefas A e B apresentam exclusão mútua quando NÃO 
podem executar simultaneamente 
!  Exemplos 
"  Estrutura de dados compartilhadas 
"  Arquivo 
"  Controlador de periférico 
Abordagens de Escalonamento 
de Tempo Real 
43 
!  STR e Escalonamento 
!  Um STR é composto por: 1) um conjunto de tarefas e o 2) 
somatório dos tempos de computação dessas tarefas na fila 
de Pronto, que determina a carga computacional (task load ) 
!  Task load está relacionada a aplicação e seus recursos 
computacionais em um determinado instante 
!  Dois tipos de carga 
!  Carga Estática 
!  Carga Dinâmica 
 
Abordagens de Escalonamento 
de Tempo Real 
44 
!  Carga Estática (ou limitada) 
!  Ocorre quando todas as restrições temporais das tarefas 
são bem conhecidas em tempo de projeto 
"  São conhecidas as suas condições de chegada (arrival times) 
!  É possível determinar os prazos que uma carga está sujeita 
!  Situações de pico (pior caso) também torna-se possível 
identificar em tempo de projeto 
 
!  Carga Dinâmica (ou ilimitada) 
!  Ocorrem em situações onde as características de chegada 
das tarefas não podem ser antecipadas 
Abordagens de Escalonamento 
de Tempo Real 
45 
!  Diferentes tipos de classificações (Ramamrithan& 
Stankovic, 1994) 
Abordagens de Escalonamento 
de Tempo Real 
46 
!  Abordagens com garantia de tempo de projeto 
!  É formado por abordagens que tem como finalidade a 
previsibilidade determinista 
!  Composta por duas premissas 
"  a carga computacional do sistema é conhecida em tempo de 
projeto (conhecida previamente-> carga estática) 
"  no sistema existe uma reserva de recursos suficientes para a 
execução das tarefas, atendendo suas restrições temporais, na 
condição de pior caso 
Abordagens de Escalonamento 
de Tempo Real 
47 
!  Abordagens com garantia de tempo de projeto 
!  Carga estática permite realizar testes de escalonabilidade 
"  Determinando se o conjunto de tarefas é escalonável 
!  Conhecimento do pior caso (situação de pico) permite que 
se possa redimensionar o sistema caso necessário!  Apropriado para aplicações deterministas ou críticas onde 
a carga é conhecida previamente 
"  Aplicações embarcadas 
"  Controle de tráfego ferroviário 
"  Controle de processos em geral 
Abordagens de Escalonamento 
de Tempo Real 
48 
!  Executivo cíclico 
!  O teste de escalonabilidade e a produção da escala, são 
realizados em tempo de projeto 
!  O escalonador em tempo de execução se resume a um 
simples despachante, ativando as tarefas ciclicamente 
!  O pior caso é distante do caso médio e nem sempre ocorre 
"  A ativação das tarefas, embora satisfaça às restrições temporais, 
implica em desperdício de recursos que são sempre reservados 
para o pior caso 
Abordagens de Escalonamento 
de Tempo Real 
49 
!  Dirigidos a prioridades 
!  Teste de escalonamento é realizado em tempo de projeto 
enquanto a escala é produzida on-line por um escalonador 
dirigido a prioridades 
!  As tarefas têm suas prioridades definidas segundo políticas 
de escalonamento 
"  Prioridades estáticas ou dinâmicas 
!  Pior caso se reflete apenas no teste de escalonabilidade 
que é executado em tempo de projeto, decidindo se o 
conjunto de tarefas é escalonável ou não 
!  Abordagem mais flexiva 
Abordagens de Escalonamento 
de Tempo Real 
50 
!  Abordagens de garantia dinâmica e melhor esforço 
!  Não tratam com uma carga computacional previsível 
!  A carga tratada por essas abordagens é dinâmica 
"  Os tempos de chegada das tarefas não são conhecidos previamente 
!  O pior caso não pode ser antecipado em tempo de projeto, 
não se consegue prever recursos para todas as situações de 
carga 
!  Não garante que todos os deadlines sejam respeitados 
!  Lidam com situações, em tempo de execução, onde os 
recursos computacionais são insuficientes (situações de 
sobrecarga) 
!  Tanto a escala como os testes de escalonabilidade são 
realizados em tempo de execução 
Abordagens de Escalonamento 
de Tempo Real 
51 
!  Garantia dinâmica 
!  Utilizam de um teste para verificar a escalonabilidade do 
conjunto formado por uma nova tarefa que chega no sistema 
e das tarefas que já existiam previamente na fila de pronto 
"  Testes de aceitação (baseados em aná lises realizadas com 
hipóteses de pior caso sobre alguns parâmetros temporais) 
!  Se o teste indica o conjunto como não escalonável, a nova 
tarefa que chegou é então descartada 
Abordagens de Escalonamento 
de Tempo Real 
52 
!  Garantia dinâmica 
!  Garante em qualquer situação a preservação das tarefas já 
previamente garantidas como escalonáveis 
!  Próprias para aplicações que possuam restrições críticas mas 
que operam em ambientes não deterministas 
"  Sistema de radar 
"  Sistemas militares 
"  Controle aéreo 
Abordagens de Escalonamento 
de Tempo Real 
53 
!  Melhor esforço 
!  São constituídas por algoritmos que tentam encontrar uma 
escala realizável em tempo de execução 
"  sem realizar testes ou ainda, realizando testes mais fracos 
!  Não existe a garantia de execuções de tarefas atendendo 
suas restrições temporais 
!  São adequadas para aplicações de tempo real brandas 
como sistemas de multimídia 
!  Tarefas são abortadas somente em condições reais de 
sobrecarga, na ocorrência de falhas temporais 
"  deadlines não podem ser atendidos 
Exercícios 
1) O que é previsibilidade? Cite e explique os dois tipos de 
previsibilidade que podem ocorrer nos sistemas de tempo real. 
2) Quais as diferenças entre as tarefas periódicas e aperiódicas? 
3) Quais as diferenças entre um escalonamento dinâmico e 
escalonamento estático? 
4) Quais as diferenças entre o escalonamento preemptivo e o não 
preemptivo? 
5) Quais as variáveis que descrevem uma tarefa periódica? 
6) Calcule o deadline absoluto de uma tarefa na sua décima 
ativação (k=10), tendo 5ms de período e 4ms de deadline relativo. 
7) Explique a abordagem de escalonamento de garantia dinâmica. 
8) Explique a diferença entre carga estática e carga dinâmica. 
54 
Referências 
!  Kopetz, Hermann. Real-time systems: design principles for 
distributed embedded applications. Springer Science & 
Business Media, 2002. 
!  Cheng, Albert MK. Real-time systems: scheduling, analysis, and 
verification. John Wiley & Sons, 2003. 
!  K. Ramamrithan, J. A. Stankovic. Scheduling Algorithms and 
Operating Systems Support for Real-Time Systems . 
Proceedings of the IEEE, Vol. 82, No 1, pp. 55-67, January 
1994. 
!  Farines, J. M., Fraga, J. D. S., & Oliveira, R. D. Sistemas de 
tempo real. Escola de Computação, 2000. 
55