Embed Size (px)
Citation preview
Algoritmos para Escalonamento de Tempo Real – (RM, EDF, DM)
André Luis Meneses [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, tarefas periódicas em geral:– 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çãoPrioridade 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.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ódicasPeríodo Tempo de
ComputaçãoPrioridade
RMUtilizaçã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).
