Escalonamento de Tarefas de Tempo Real

Prévia do material em texto

SISTEMAS DE TEMPO REAL 
AULA 7 – ESCALONAMENTO (2) 
Prof.: Danilo Coimbra 
(danilo.dcc.ufba@gmail.com) 
(coimbra.danilo@ufba.br) 
1 
Sumário 
!  Testes de Escalonabilidade 
!  Utilização de Tarefa 
!  Instante Crítico 
!  Escalonamento de Tarefas Periódicas 
!  Escalonamento Taxa Monotônica 
!  Escalonamento Deadline Monotônico 
2 
Testes de Escalonabilidade 
!  São testes que auxiliam no escalonamento de tarefas 
de tempo real, determinando se são tarefas 
escalonáveis ou não 
!  Se existe para esse conjunto de tarefas escalonamento 
realizável ou não 
!  Podem ser feitos offline (previamente) e online (em 
tempo de execução do sistema) 
!  Variam conforme os modelos de tarefas e políticas 
definidas em um problema de escalonamento 
3 
Testes de Escalonabilidade 
!  Normalmente, correspondem a análises de pior caso 
de certas classes de problemas 
 
!  Tipicamente, são utilizados três tipos de teste offline 
!  Testes exatos 
!  Testes suficientes 
!  Testes necessários 
4 
Testes de Escalonabilidade 
Testes Exatos 
!  São análises que não afastam conjuntos de tarefas 
que apresentam escalas realizáveis 
!  São precisos, pois identificam também conjuntos não 
escalonáveis 
!  Em muitos problemas são impraticáveis os testes 
exatos 
!  Podem ser muito complexos 
5 
Testes de Escalonabilidade 
Testes Suficientes 
!  Um teste suficiente de escalonabilidade positivo 
!  garante que o conjunto de tarefas é sempre escalonável 
!  São mais simples na execução, porém apresentam o 
custo do descarte de conjuntos de tarefas escalonáveis 
!  É um teste mais restritivo onde conjuntos de tarefas 
aceitos nesses testes certamente são escalonáveis 
!  porém entre os descartados podem existir conjuntos 
escalonáveis 
6 
Testes de Escalonabilidade 
Testes Necessários 
!  Um teste necessário de escalonabilidade negativo 
!  garante que o conjunto de tarefas é sempre não 
escalonável 
!  Correspondem também a análises simples porém não 
tão restritivas 
!  O fato de um conjunto ter passado por um teste 
necessário não implica que o mesmo seja escalonável 
!  Única garantia: mostrar que os conjuntos descartados 
de tarefas certamente são não escalonáveis 
7 
Testes de Escalonabilidade 
8 
!  Tipos de teste de Escalonabilidade 
Testes de Escalonabilidade 
9 
!  Verificação online da escalonabilidade de um sistema 
!  Teste para a aceitação/rejeição da inclusão de uma 
nova tarefa num conjunto de tarefas previamente 
escalonável 
!  Este tipo de testes deve ter complexidade menor, pois 
existe o risco de rejeição de tarefas potencialmente 
escalonáveis 
Utilização de Tarefa 
10 
!  A utilização de uma tarefa Ti serve como uma medida 
da ocupação do processador pela mesma, é dado 
por: 
!  onde Ci , Pi e Mini são respectivamente o tempo 
máximo de computação, o período e o intervalo 
mínimo entre requisições da tarefa Ti 
Utilização de Tarefa 
11 
!  A utilização de um processador (U ) dá a medida da 
ocupação do mesmo por um conjunto de tarefas 
 { T1 , T2 , T3 , ..., Tn }: 
 
 
 
!  O conceito de utilização serve de base para testes 
simples e bastante usados 
Utilização de Tarefa 
12 
!  A ideia central nesses testes é que a soma dos fatores 
de utilização (Ui ) das tarefas do conjunto não 
ultrapasse o número de processadores disponíveis 
para suas execuções: 
!  onde m é o número de processadores 
!  Testes baseados na utilização podem ser exatos, 
necessários ou suficientes, dependendo da política 
usada e do modelo de tarefas assumido 
Exemplos de Escalonamento 
13 
Exemplo: Quatro cenários/exemplos de escalonamento 
!  1. Escalonamento preemptivo, com primeiros pedidos de 
execução arbitrariamente defasados 
!  2. Escalonamento preemptivo, com simultaneidade nos 
primeiros pedidos de execução 
!  3. Escalonamento não-preemptivo, com simultaneidade 
nos primeiros pedidos de execução 
!  4. Escalonamento não-preemptivo com ativação de 
tarefa de menor prioridade imediatamente anterior à 
ativação simultânea de todas as outras tarefas 
Exemplos de Escalonamento 
14 
!  Cenário 1: -Tarefas Periódicas: τ={Ci, Ti, di}; U=90,3% -Escalonamento preemptivo por prioridades 
-Atribuição de prioridades às tarefas (?) 
-1os pedidos de execução defasados 
Exemplos de Escalonamento 
15 
!  Cenário 2: -Tarefas Periódicas: τ={Ci, Ti, di}; U=90,3% -Escalonamento preemptivo por prioridades 
-Atribuição de prioridades às tarefas (?) 
-1os pedidos de execução simultâneos 
Exemplos de Escalonamento 
16 
!  Cenário 3: -Tarefas Periódicas: τ={Ci, Ti, di}; U=90,3% -Escalonamento não-preemptivo por prioridades 
-Atribuição de prioridades às tarefas (?) 
-1os pedidos de execução simultâneos 
Exemplos de Escalonamento 
17 
!  Cenário 4: 
-Tarefas Periódicas: τ={Ci, Ti, di}; U=90,3% 
-Escalonamento não-preemptivo por prioridades 
-Atribuição de prioridades às tarefas (?) 
-1o pedido de execução de uma tarefa de menor prioridade 
imediatamente anterior à ativação simultânea de todas as outras 
tarefas 
 
Instante Crítico 
18 
!  Num sistema com escalonamento preemptivo, a 
ativação simultânea de todas as tarefas (instante 
crítico) tem como consequência: 
!  em termos de utilização, um período de carga máxima do 
processador 
!  em termos de tempo de resposta, um intervalo de tempo 
(intervalo crítico) durante o qual o tempo de resposta é 
máximo para cada uma das ativações das tarefas 
!  Num sistema com escalonamento não-preemptivo 
!  É definido como a ativação da tarefa de maior duração 
(efeito de bloqueio) imediatamente antes da ativação 
simultânea de todas as outras tarefas 
Escalonamento de Tarefas Periódicas 
19 
!  Se considerarmos aplicações de tempo real de uma 
maneira geral, as atividades envolvidas nessas 
aplicações se caracterizam basicamente pelo 
comportamento periódico de suas ações 
!  As características de tarefas periódicas determinam o 
conhecimento a priori dos tempos de chegada e, por 
consequência, da carga computacional do sistema 
!  Permitindo obter garantias em tempo de projeto sobre a 
escalonabilidade de um conjunto de tarefas periódicas 
Escalonamento de Tarefas Periódicas 
20 
!  Será abordado somente tarefas dirigida a 
prioridades 
!  Prioridades atribuídas às tarefas estudadas são 
derivadas de suas restrições temporais 
!  e não de atributos outros como a importância ou o grau 
de confiabilidade das tarefas 
!  Escalonamentos baseados em prioridades geralmente 
apresentarem melhor desempenho e flexibilidade 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
21 
!  Produz escalas em tempo de execução através de 
escalonadores preemptivos, dirigidos a prioridades 
!  É um algoritmo ótimo de escalonamento de prioridade 
fixa 
!  nenhum outro algoritmo da mesma classe pode escalonar 
um conjunto de tarefas que não seja escalonável pelo RM 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
22 
!  As premissas do RM que facilitam as análises de 
escalonabilidade, definem um modelo de tarefas 
bastante simples: 
!  a) As tarefas são periódicas e independentes (não tem 
relações de precedência) 
!  b) O deadline de cada tarefa coincide com o seu período 
(Di = Pi ) 
!  c) O tempo de computação (Ci ) de cada tarefa é 
conhecido e constante (“Worst Case Computation Time”- 
tempo máximo de execução ) 
!  d) O tempo de chaveamento entre tarefas é assumido 
como nulo 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
23 
!  Atribuição de prioridades 
!  As prioridades decrescem em função do aumento dos 
períodos, ou seja, quanto mais frequente a tarefa maior a 
sua prioridade no conjuntoPTi < PTj => Pri > Prj 
Onde PT = período da tarefa i, j e Pr = prioridade da 
tarefa i ou j 
!  Como os períodos das tarefas não mudam, o RM 
define uma atribuição estática de prioridades 
(prioridade fixa) 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
24 
Análise de Escalonabilidade do RM 
!  Baseada no cáculo de utilização 
!  Teste suficiente de escalonabilidade 
!  Feito para que n tarefas tenham suas restrições temporais 
atendidas quando escalonadas pelo RM 
 ou 
 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
25 
!  Exemplo de teste de escalabilidade 
!  Taxa de utilização do processador 
!  U= ( UTA+UTB+UTC ) = 0.2+0.267+0.286=0.753 
!  Teste suficiente (n = quantidade de tarefas = 3) 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
26 
!  Exemplo: escalanomento RM (diagrama de Gantt) (1/3) 
!  Tarefas A, B e C chegam em t=0 
!  Por ser mais frequente (maior prioridade segundo o RM), 
A assume o processador. 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
27 
!  Exemplo: escalanomento RM (diagrama de Gantt) (1/3) 
!  Em t=20, a tarefa A conclui e B toma posse do 
processador por ser a mais prioritária na fila de Pronto 
!  A tarefa C assume em t=60 e é interrompida quando 
chega a nova ativação de A em t=100 
20 40 40 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
28 
!  Exemplo: escalanomento RM (diagrama de Gantt) (1/3) 
!  A passa a se executar (preempção de C por A) 
 
 
 
 
 
 
 
!  C sofre mais interrupções de novas ativações das tarefas 
B em t=150 e A em t=200, ... 
20 40 40 20 30 (70) 40 
10(80) 
20 20 (100) 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
29 
!  Três cenários utilizando o algoritmo de RM 
!  considera conjuntos de tarefas com diferentes taxas de ativação (P) 
1)Teste de escalonabilidade é respeitado 
!  conjunto de tarefas é sempre escalonável 
2)Teste de escalonabilidade não é respeitado 
!  No entanto, após o instante crítico, a meta temporal da tarefa de 
menor prioridade é respeitada (o conjunto de tarefas é sempre 
escalonável) 
3)Teste de escalonabilidade não é respeitado, nem a meta 
temporal da tarefa de menor prioridade (após o instante 
crítico) 
!  conjunto de tarefas não é escalonável 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
30 
!  Cenário 1 (T = P) 
 
 tarefas periódicas: τ={Ci, Ti}; di=Ti ; U=77,5% 
 -data de ativação das tarefas simultânea 
 -escalonamento sempre realizável 
„ teste suficiente de escalonabilidade respeitado 
C T 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
31 
!  Cenário 2 (T = P) 
 
 tarefas periódicas: τ={Ci, Ti}; di=Ti ; U=87,5% 
 -data de ativação das tarefas simultânea 
 -escalonamento sempre realizável 
„ teste suficiente de escalonabilidade não é respeitado 
 no entanto, a meta temporal da tarefa t3 é respeitada após o 
instante crítico, logo o conjunto de tarefas é sempre escalonável 
 C T 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
32 
!  Cenário 3 (T = P) 
 
 tarefas periódicas: τ={Ci, Ti}; di=Ti ; U=96,3% 
 -data de ativação das tarefas simultânea 
 -escalonamento não é realizável 
„ teste suficiente de escalonabilidade não é respeitado 
 meta temporal da tarefa t3 não é respeitada após o 
 instante crítico 
 C T 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
33 
!  Vantagens do algoritmo RM 
! Simplicidade 
! Adequado para utilização em sistemas operacionais 
existentes 
! Pode ser utilizado para a atribuição de prioridades a 
níveis de interrupção 
! Se a meta temporal da tarefa de menor prioridade 
for respeitada após um instante crítico, então o 
conjunto de tarefas é sempre escalonável 
Escalonamento Taxa Monotônica 
(Rate Monotonic - RM) 
34 
!  Desvantagens do algoritmo RM 
! Modelo de tarefas muito limitado 
! Não adequado quando se têm metas temporais 
inferiores ao período 
! Não suporta exclusão mútua no acesso a recursos 
partilhados 
Deadline Monotônico (DM) 
35 
Algoritmo Taxa Monotônica 
!  Limitação do algoritmo RM: 
!  A cada tarefa é atribuída uma prioridade proporcional à 
sua cadência de ativação (P ou T: período) 
!  No entanto, a importância de uma tarefa pode ser 
independente da sua cadência de ativação (por ex.: 
leitura de temperatura) 
!  Existem outros parâmetros temporais que podem ser 
considerados 
Deadline Monotônico 
36 
!  Algoritmo de atribuição de prioridades a um conjunto 
de tarefas periódicas, independentes e com metas 
temporais menores ou iguais ao respectivo período 
!  (di ≤ Ti ) 
!  A atribuição de prioridades às tarefas é efetuada na 
ordem inversa do valor da sua meta temporal (d): 
!  menor meta temporal: maior prioridade 
!  maior meta temporal: menor prioridade 
"  situações de empate serão resolvidas arbitrariamente 
Deadline Monotônico 
37 
!  A política do DM define uma atribuição estática de 
prioridades, baseada nos deadlines relativos das 
tarefas (Di) 
!  A produção da escala é feita em tempo de execução 
por escalonador preemptivo dirigido a prioridades 
!  O esquema de prioridades fixas do DM também 
define um escalonamento estático e online 
Deadline Monotônico 
38 
!  Exemplo (diagrama de Gantt) 
A 
Deadline Monotônico 
39 
Exemplos de dois escalonamento por prioridades fixas 
(idêntico conjunto de tarefas): 
!  Prioridades atribuídas segundo o algoritmo DM 
(tarefas ordenadas por valor de meta temporal 
crescente): 
!  verifica-se que o conjunto de tarefas é sempre 
escalonavel 
!  Prioridades atribuídas segundo o algoritmo RM 
(tarefas ordenadas por periodicidade crescente): 
!  verifica-se que o conjunto de tarefas não é escalonável 
Deadline Monotônico 
40 
!  Cenário 1: conjunto de tarefas ordenado por metas 
temporais crescentes 
 
C T d deadline ativação 
Deadline Monotônico 
41 
!  Cenário 2: conjunto de tarefas ordenados por períodos crescentes (RM) 
C T d
Deadline Monotônico 
42 
!  Cenário 2: Conclusão 
!  Por simples inspeção da figura anterior, verifica-se que o 
conjunto de tarefas não é escalonável quando se utiliza o 
algoritmo RM 
!  O algoritmo RM é um algoritmo que não é ótimo quando se 
consideram conjuntos de tarefas com metas temporais 
inferiores aos períodos 
!  Para este tipo de conjunto de tarefas (d<T), a atribuição dos 
níveis de prioridade deverá ser efetuada utilizando o 
algoritmo DM (algoritmo ótimo) 
Deadline Monotônico 
43 
!  Vantagens do algoritmo DM 
!  Simples e adequado para utilização em sistemas 
operacionais existentes 
!  Pode ser utilizado para a atribuição de prioridades a 
níveis de interrupção 
!  Admite tarefas com metas temporais inferiores ao período 
!  Desvantagens do algoritmo DM 
!  Modelo de tarefas também muito limitado 
!  Não suporta exclusão mútua no acesso a recursos 
partilhados 
Exercícios 
1) Quais os testes offline que compõem os testes de escalonabilidade? 
2) Calcule a porcentagem de utilização das 3 tarefas e diga se são 
escalonáveis. 
 Tarefa (tempoComputação, deadline, Período) 
 T1 (3,5,20), T2 (3,7,15), T3(5,10,15) 
3) Explique o que é Instante Crítico. 
4) Quais as vantages e desvantagens do algoritmo de escalonamento 
Taxa Monotônica. 
5) Quais as vantages e desvantagens do algoritmo de escalonamento 
Deadline Monotônico. 
6) Se caso o sistema de Tempo Real possuir deadlines inferiores aos 
Períodos de ativação de instâncias das tarefas, qual a abordagem mais 
adequada, Taxa Monotônica ou Deadline Monotônico? Por quê? 
7) Considere as 3 tarefas do exerc.2. Elassão escalonáveis usando o 
deadline monotômico? 
44 
Referências 
!  Cheng, Albert MK. Real-time systems: scheduling, analysis, and 
verification. John Wiley & Sons, 2003. 
!  Jane W. S. W. Liu. 2000. Real-Time Systems (1st ed.). Prentice 
Hall PTR, Upper Saddle River, NJ, USA. 
!  Vasques, F. Notas de curso realizado em Agosto de 2006 na 
Universidade Federal do Rio Grande do Norte (UFRN). 
!  Farines, J. M., Fraga, J. D. S., & Oliveira, R. D. Sistemas de 
tempo real. Escola de Computação, 2000. 
45