Upload
isis-olivares-mangueira
View
213
Download
0
Embed Size (px)
Citation preview
Extensões no teste de escalonabilidade.
André Luis Meneses Silva
Agenda
• Introdução• Extensões das fórmulas Deadline = Período• Deadline menor ou igual ao período• Presença de Atraso (jitter)
Introdução
• Os testes vistos até agora:– Impõe limites na utilização do processador– Não estabelece relações de precedência entre si
ou que os deadlines assumam valores arbitrários.– Baseam-se apenas na utilização do processador.– Os testes que veremos hoje, baseam-se na noção
de tempo de resposta.– São exatos.– Os anteriores eram...?
Introdução
• Vamos analisar os seguintes cenários:– Deadline igual ao período.– Deadline menor ou igual ao período.– Presença de atraso (Jitter).
Deadline igual ao Período
• Modelo igual ao de taxa monotônica (sem extensões).
• Teste baseado no conceito de carga cumulativa (workload).
• Também utiliza a idéia de utilização do processador.
Deadline Igual ao Período
• Carga Cumulativa– Dada uma tarefa t de prioridade i.– A carga Cumulativa consiste no cálculo do tempo
total de execução das tarefas de prioridade maior ou igual a i.
Deadline Igual ao Período
Deadline Igual ao Período
Número de ocorrências da tarefa j no período t.
Por isso teto.
Deadline Igual ao Período
Número de ocorrências da tarefa j no período t.
O tempo que o processador ficará ocupado neste intervalo.
Deadline igual ao Período
• Nossa nova fórmula de utilização do processador é:
• Qual a condição de escalonamento?– Se existir um t que satisfaça , a tarefa Ti é
escalonável.• Qual t devemos considerar?
Deadline igual ao Período• Devemos considerar valores de t que resultem
em uma menor utilização da CPU.– t deve estar no intervalo (0, Pi].– Os valores candidatos de t são obtidos a partir desta
fórmula:
– Onde consideramos os períodos de todas as tarefas j com período menor ou igual a tarefa i.
Deadline Igual ao PeríodoTarefas
PeriódicasPeríodo Tempo de
ComputaçãoUtilização
Tarefa A 20 10 0,5
Tarefa B 50 25 0,5
Deadline Igual ao Período
• Cálculo de U
Escalonável
Deadline Igual ao Período
• Cálculo de U
Não escalonável
Deadline Menor que o Período
• Teste se fundamenta no tempo de resposta.– Tempo de resposta é o tempo transcorrido entre a
chegada e o término da execução de uma instância de uma dada tarefa.
– Também é contabilizado a interferência provocada por tarefas de igual ou maior prioridade.
– As tarefas podem ser escalonadas se o seu tempo de resposta é menor ou igual ao seu deadline.
Deadline Menor que o Período
• Fórmula para cálculo do tempo de Resposta
• Onde, Ci corresponde ao tempo de computação da tarefa i.
• Ij corresponde a interferência das tarefas de maior.
Deadline Menor que Período
• Cálculo das interferências– Acho que já vi isso antes?
Deadline Menor que Período
• Cálculo das interferências– Acho que já vi isso antes?
– O que nos leva a:
Deadline Menor que Período
• Como Ri aparece em ambos os lados utilizamos um método iterativo para seu cálculo.
• Onde:– Para quando – Inicial – O método não converge quando a utilização das
tarefas for maior que 100%.
Deadline Menor que PeríodoTarefas
PeriódicasPeríodo Tempo de
ComputaçãoDeadline Prioridade RM
Tarefa A 10 2 6 1
Tarefa B 10 2 8 2
Tarefa C 20 8 16 3
Deadline Menor que PeríodoTarefas Periódicas Período Tempo de Computação Deadline Prioridade RM
Tarefa A 10 2 6 1
Tarefa B 10 2 8 2
Tarefa C 20 8 16 3
• pA>pB>pC Para Tarefa A, temos:
Deadline Menor que PeríodoTarefas Periódicas Período Tempo de Computação Deadline Prioridade RM
Tarefa A 10 2 6 1
Tarefa B 10 2 8 2
Tarefa C 20 8 16 3
• pA>pB>pC Para Tarefa B, temos:
Deadline Menor que PeríodoTarefas Periódicas Período Tempo de Computação Deadline Prioridade RM
Tarefa A 10 2 6 1
Tarefa B 10 2 8 2
Tarefa C 20 8 16 3
• pA>pB>pC Para tarefa C, temos:
Presença de Atraso
• Até o momento só trabalhamos com tarefas bem comportadas – Periódicas– Liberadas sempre no início do período de
ativação.• Nem sempre estas condições são verdadeiras.– Algumas vezes, o próprio escalonador provoca
atrasos na liberação de uma tarefa.
Presença de Atraso
• Nestes casos, temos de levar em conta o período ocupado.
• Ou seja, o atraso na liberação de cada tarefa também deve entrar em nossos cálculos.
• Nossa nova fórmula:
Presença de Atraso
• Workload (W) X Tempo de resposta (R)– O tempo de resposta é obtido pela seguinte
fórmula:
Para o Banco do Conhecimento
• Existem muitas extensões do algoritmo apresentado por Liu e Leiland (Rate Monotonic), visto na última aula.
• Para cada grupo:– Pesquisar 1 artigo • (http://www.periodicos.capes.gov.br) que apresente
uma extensão no trabalho de Liu e Leiland.– Escrever um resumo sobre este artigo e
disponibilizar no banco de conhecimento (não disponibilizar o artigo).
Referências
• Farines– Seção 2.5