Algoritmos para Escalonamento
de Tempo Real – (RM, EDF, DM)
André Luis Meneses Silva
[email protected]
strufs.wordpress.com
Agenda
•
•
•
•
•
Introdução
Escalonamento de Tarefas Periódicas
Escalonamento de Taxa Monotônica
Earliest Deadline First
Escalonamento de Deadline Monotônico
Introdução
• O que vamos ver em escalonamento de STR?
– Escalonamento de Tarefas Periódicas
– Tarefas Dependentes: Compartilhamento de
Recursos
– Tarefas Dependentes: Relações de Precedência
– Escalonamento de Tarefas Aperiódicas
Escalonamento de Tarefas Periódicas
• Devido a sua previsibilidade,
periódicas em geral:
tarefas
– Permite que se obtenha garantias em tempo de
projeto.
– Utilizadas para modelagem de sistemas de
controle de processos e aplicações multimídia.
Escalonamento de Tarefas Periódicas
• Os algoritmos de escalonamento que serão
vistos são:
– Dirigidos a prioridades
– Prioridades são atribuídas de acordo com as
restrições temporais das tarefas.
– Veremos 3 algoritmos:
• Escalonamento de Taxa Monotônica (Rate Monotonic)
• Earliest Deadline First (EDF)
• Escalonamento Deadline Monotônico (DM)
Escalonamento de Taxa Motônica
• Desenvolvido por Liu & Layland.
• Produz escalas em tempo de execução através
de escalonadores preemptivos dirigidos a
prioridades.
– On-line ou offline?
• É um esquema de prioridade fixa, ou seja,
tarefas sempre possuem a mesma prioridade.
– Estático ou dinâmico?
Escalonamento de Taxa Monotônica
• O algoritmo RM trabalha sobre um modelo de
tarefas bastante simples, que obedece às
seguintes premissas:
– As tarefas são periódicas e independentes.
– O “deadline” de cada tarefa coincide com o seu
período (Di = Pi)
– O tempo de computação (Ci) de cada tarefa é
conhecido e constante (Worst Case Computation
Time)
– O tempo de chaveamento entre tarefas é assumido
nulo.
Escalonamento de Taxa Monotônica
• Idéia: Dar maior prioridade às tarefas de
menor período.
Escalonamento de Taxa Monotônica
• Idéia: Dar maior prioridade às tarefas de
menor período.
Tarefas
Periódicas
Período
Tempo de
Computação
Prioridade
RM
Utilização
Tarefa A
100
20
1
0,2
Tarefa B
150
40
2
0,267
Tarefa C
350
100
3
0,286
Escalonamento de Taxa Monotônica
Tarefas
Periódicas
Período
Tempo de
Computação
Prioridade RM
Utilização
Tarefa A
100
20
1
0,2
Tarefa B
150
40
2
0,267
Tarefa C
350
100
3
0,286
Vamos reproduzir no Cheddar
• 1. Inserindo um processador
– Edit >> Add >> Add a processor
•
•
•
•
•
Processor Name : Processor_1
Scheduler: Rate Monotonic
Option: Preemptive
Add
Cliquem em Advanced para confirmar se realmente foi
adicionado.
Vamos reproduzir no Cheddar
• 2. Inserindo um espaço de endereçamento
– Edit >> Add >> Add an Address Space
•
•
•
•
Address Space Name : mem_1
Processor: Processor_1
Add
Cliquem em Advanced para confirmar se realmente foi
adicionado.
Vamos reproduzir no Cheddar
• 3. Inserindo Tarefas (inserir 3 tarefas)
– Edit >> Add >> Add a Task
•
•
•
•
•
Name : task_1, task_2, task_3
Task Type: Periodic
Address Space: mem_1
Processor: Processor_1
Inserir Capacity, Deadline e Period de acordo com a
tabela do próximo slide.
• Cliquem em Advanced para confirmar se realmente foi
adicionado.
Vamos reproduzir no Cheddar
• Tarefas
Tarefas
Periódicas
Período
Tempo de
Computação
Prioridade
RM
Utilização
Tarefa A
10
2
1
0,2
Tarefa B
15
4
2
0,267
Tarefa C
35
10
3
0,286
Vamos reproduzir no Cheddar
• Simulando
• Clique no botão Scheduling Simulation
• Clique em ok.
Escalonamento de Taxa Monotônica
• Que trabalhão 
• Para todo projeto de tempo real devemos
construir esta escala?
– Com certeza 
• Existe alguma fórmula que nos dê alguma
perspectiva antes de construirmos a escala?
• Sim? Qual?
Escalonamento de Taxa Monotônica
• A análise de escalonabilidade pode ser feita
através do teste abaixo que define uma
condição suficiente.
Escalonamento de Taxa Monotônica
• Aplicando a fórmula no exemplo utilizado no
cheddar, temos:
No Cheddar
• Cliquem no botão Scheduling feasibility.
Escalonamento de Taxa Monotônica
• Quando as tarefas menos prioritárias possuem
períodos múltiplos em relação a mais
prioritária, temos:
• Condição necessária e suficiente
Escalonamento de Taxa Monotônica
• Aplicando a primeira fórmula, temos:
Tarefas Periódicas
Período
Tempo de
Computação
Prioridade RM
Utilização
Tarefa A
4
1
1
0,25
Tarefa B
8
3
2
0,375
Tarefa C
16
5
3
0,25
No entanto, é
escalonável.
Escalonamento de Taxa Monotônica
• Muito utilizado devido a sua simplicidade de
implementação.
• É um algoritmo ótimo para a classe de
problemas que se propõe
– Tarefas periódicas.
– P = D.
– Prioridade Fixa.
Outro exemplo
• Digamos que modelamos um sistema com as
seguintes tarefas. O que acontece no RM?
Tarefas
Periódicas
Período
Tempo de
Computação
Prioridade
RM
Utilização
Tarefa A
20
10
1
0,5
Tarefa B
50
25
2
0,5
Outro exemplo
Tarefas
Periódicas
Período
Tempo de
Computação
Utilização
Tarefa A
20
10
0,5
Tarefa B
50
25
0,5
O que fazer?
Earliest Deadline First (EDF)
• Desenvolvido por Liu & Leiland
• Produz escalas em tempo de execução através
de escalonadores preemptivos dirigidos a
prioridades.
• É um esquema de prioridade dinâmica.
– On-line e Dinâmico.
Earliest Deadline First (EDF)
• O algoritmo EDF trabalha sobre um modelo de
tarefas bastante simples, que obedece as
seguintes premissas:
– As tarefas são periódicas e independentes.
– O “deadline” de cada tarefa coincide com o seu
período (Di = Pi)
– O tempo de computação (Ci) de cada tarefa é
conhecido e constante (Worst Case Computation
Time)
– O tempo de chaveamento entre tarefas é assumido
nulo.
Earliest Deadline First (EDF)
• Idéia: Atribuição dinâmica de prioridades de
acordo com os deadlines de cada tarefa.
Earliest Deadline First (EDF)
• Idéia: Atribuição dinâmica de prioridades de
acordo com os deadlines de cada tarefa.
Tarefas
Periódicas
Período
Tempo de
Computação
Utilização
Tarefa A
20
10
0,5
Tarefa B
50
25
0,5
Earliest Deadline First (EDF)
• Idéia: Atribuição dinâmica de prioridades de
acordo com os deadlines de cada tarefa.
Tarefas
Periódicas
Período
Tempo de
Computação
Utilização
Tarefa A
20
10
0,5
Tarefa B
50
25
0,5
Earliest Deadline First (EDF)
• A análise de escalonabilidade pode ser feita
através do teste abaixo que define uma
condição suficiente e necessária.
Escalonamento EDF
• Embora consiga trabalhar com um conjunto
maior de casos, EDF possui implementação
complexa.
• É um algoritmo ótimo para a classe de
problemas que se propõe
– Tarefas periódicas.
– P = D.
– Prioridade Dinâmica.
Escalonamento Deadline Monotônico
• Desenvolvido por Leung & Whitehead
• Estende o modelo de tarefas do Taxa
Monotônico.
• Escala em tempo de execução (on-line).
• Prioridades Fixas (estático).
Escalonamento Deadline Monotônico
• Premissas:
– As tarefas são periódicas e independentes.
– O “deadline” de cada tarefa pode não coincidir
com o seu período (
)
– O tempo de computação (Ci) de cada tarefa é
conhecido e constante (Worst Case Computation
Time)
– O tempo de chaveamento entre tarefas é
assumido nulo.
Escalonamento Deadline Monotônico
• Idéia: Atribuição estática de prioridades
baseada nos deadlines relativos das tarefas
(Di).
Tarefas
Periódicas
Período
Tempo de
Computação
Deadline
Prioridade RM
Tarefa A
2
10
6
1
Tarefa B
2
10
8
2
Tarefa C
8
20
16
3
Escalonamento Deadline Monotônico
Tarefas
Periódicas
Período
Tempo de
Computação
Deadline
Prioridade RM
Tarefa A
2
10
6
1
Tarefa B
2
10
8
2
Tarefa C
8
20
16
3
Exercícios
• Considere cada tarefa P como sendo a tripla
P(tempo de computação, período, deadline).
• 1. Sejam P1(5, 10, 10) e P2(20, 40, 40)
– Calcule a utilização (U)
– Mostre um escalonamento praticável usando EDF.
– Demonstre que um escalonamento praticável
baseado em prioridades fixas existe ou prove que
não pode existir.
Exercícios
• 2. Sejam P1 = (3, 9, 6), P2 = (4, 18, 12) e P3 =
(4, 12, 10).
– Qual a utilização do processador U
– Mostre que um escalonamento RM existe ou não.
– Mostre que um escalonamento EDF existe ou não.
– Mostre que um escalonamento DM existe ou não.
Referências
• Farines
– Seção 2.4
• Sistemas de Tempo Real. Alan C. Shaw
(Capítulo 6).
• System Design and Analysis. Philip A. Laplace
(Capítulo 3, seções 3.2.4 e 3.2.5).