Escalonabilidade em tarefas
Dependentes: Compartilhamento de
Recursos
André Luis Meneses Silva
Agenda
• Deadline Arbitrário
• Protocolo Herança de Prioridade
• Protocolo Prioridade Teto
Deadline Arbitrário
• Em modelos de deadline arbitrário, podemos
ter (D > P).
• Tarefas com estas características sofrem
interferência interna.
• Logo, para cálculo do tempo de resposta,
também temos de levar em consideração a
interferência da própria tarefa sobre si
mesmo.
Deadline Arbitrário
• Antes nós tínhamos:
• E agora temos:
Deadline Arbitrário
• Antes nós tínhamos:
• E agora temos:
Onde,
q+1
representam
as
ativações de Ti que
podem se sobrepor.
Deadline Arbitrário
• Tempo de Resposta (q = 0, 1, 2, ...)
• Para calcular o número de auto-interferências.
Deadline Arbitrário
• Na presença de Jitter, basta adicionarmos o
Jitter em nossos cálculos.
Deadline Arbitrário
• Exemplo
Modelar no
Cheddar.
Usar algoritmo
Highest Priority
First.
Tar. Periódicas
Jitter
Período
T. de Computação
Deadline
Prioridade
Tarefa A
Tarefa B
Tarefa C
1
3
-
40
80
20
10
10
5
40
25
40
1
2
3
Deadline Arbitrário
25 <= (0 + 1) . 20
25 <= 20 (Falso, então continuamos).
Deadline Arbitrário
25 <= (1 + 1) . 20
30 <= 40 (Verdadeiro), achamos a
interferência.
Para o Cálculo de R, fazemos
R3(0) = W3(0) – 0 = 25
Tarefas Dependentes
• Podemos ter dois casos
– Compartilhamento de Recursos.
– Dependência entre Tarefas.
Compartilhamento de Recursos
• Imaginem o seguinte cenário:
Pedido de entrada em SC
Executando em SC
Compartilhamento de Recursos
• Este comportamento é denominado de
inversão de prioridade.
– Tarefas menos prioritárias bloqueiam mais
prioritárias por estar utilizando um recurso
compartilhado.
– Problemas?
Compartilhamento de Recursos
• Este comportamento é denominado de
inversão de prioridade.
– Tarefas menos prioritárias bloqueiam mais
prioritárias por estar utilizando um recurso
compartilhado.
– Problemas?
• Tarefas mais prioritárias podem ficar um longo período
de tempo bloqueadas.
– Tarefas intermediárias vão provocar sucessivas preempções
na tarefa em sessão crítica.
• Como resolver isso?
Compartilhamento de Recursos
• Algoritmos mais comuns:
– Protocolo Herança de Prioridade
– Protocolo de Prioridade Teto
Protocolo Herança de Prioridade (PHP)
• Tarefas possuem duas prioridades:
– Tarefas possuem prioridade nominal ou estática
(RM, DM, etc).
– Tarefas possuem prioridade dinâmica ou ativa.
• Derivadas das ações de bloqueio que ocorrem no
sistema.
Protocolo Herança de Prioridade (PHP)
• Funcionamento: Tarefas são escalonadas pela
sua prioridade estática enquanto não existir
recurso bloqueado.
• Quando existe recurso bloqueado, a tarefa em
sessão crítica herda prioridade das tarefas
mais prioritárias.
Protocolo Herança de Prioridade (PHP)
Pedido de entrada em SC
Entrada em SC
Herda Prioridade P1
Fim de Execução da Sessão
Crítica
Executando em SC
Protocolo Herança de Prioridade (PHP)
• Sob o PHP um tarefa pode sofrer três tipos de
bloqueios
– Bloqueio direto
• (T1 > T2) compartilham recursos.
• T2 bloqueia T1.
– Bloqueio por herança
• (T1 > T2 >T3) compartilham recursos.
• T3 bloqueia T1 e conseqüentemente T3 bloqueia T2.
– Bloqueio transitivo
• T1 bloqueia T2. T2 bloqueia T3. T1 bloqueia T3.
Identifique os Bloqueios
Bloqueio Direto
Bloqueio Herança
Bloqueio Herança
Identifique os Bloqueios
Bloqueio Transitivo Bloqueio Transitivo
Bloqueio Direto
Protocolo Herança de Prioridade (PHP)
• Teste de Escalonabilidade.
– Similar aos anteriores, mas leva em consideração
o bloqueio máximo (Bi) de cada tarefa.
– Bi = maior sessão crítica que bloqueia Ti.
Protocolo Herança de Prioridade (PHP)
• Modelar no Cheddar
Tar. Periódicas
Período
T. de Computação
Bi
Prioridade RM
Tarefa A
Tarefa B
18
20
6
4
2
4
1
2
Tarefa C
50
10
0
3
Usar algoritmo Rate Monotonic.
Bi = Blocking Time
Protocolo Herança de Prioridade (PHP)
Tar. Periódicas
Período
T. de Computação
Bi
Prioridade RM
Tarefa A
Tarefa B
Tarefa C
18
20
50
6
4
10
2
4
0
1
2
3
Protocolo Herança de Prioridade (PHP)
• Ou ainda poderíamos utilizar:
Atividade para Casa
• Calcular a utilização para cada uma das
tarefas.
• Compare os resultados com os obtidos pelo
cheddar.
Protocolo Herança de Prioridade (PHP)
• Qual o problema do PHP?
– PHP é sujeito a deadlock.
– Alguém consegue dar um exemplo?
Protocolo Herança de Prioridade (PHP)
Sofre Preempção
Entra em SC2
Pede para entra
em SC1
Deadlock
Inicia a Execução
Volta a executar
Pede para entrar
em SC2
Entra em SC1
Como resolver isso?
Idéias?
Protocolo de Prioridade Teto
• Limita o número de bloqueios ou inversões de
prioridade para evitar deadlocks.
• Dirigido para escalonamento de prioridade
fixa.
• Similar ao PHP, porém corrige suas falhas.
– Também trabalha com herança de prioridades.
Protocolo de Prioridade Teto
• Funcionamento:
– Cada recurso possui uma prioridade teto (prioridade
igual a da tarefa mais prioritária que pode alocar o
recurso).
– Se nenhum recurso compartilhado está bloqueado,
quem requisita é atendido.
– Se alguma tarefa bloqueia outra mais prioritária, a
menos prioritária herda sua prioridade.
– No caso de haver recurso em uso:
• A tarefa que solicita só consegue acesso ao recurso solicitado
se sua prioridade for maior que a prioridade teto de todos os
recursos em uso alocados por outras tarefas.
Protocolo de Prioridade Teto
Seja P1 > P2 > P3
Legenda para os recursos
RC1 (Prioridade Teto = P1)
RC2 (Prioridade Teto = P1)
RC3 (Prioridade Teto = P2)
Tempo de término
P1
P2
P3
P2
P3
Teste de Escalonabilidade no PCP.
• Mesmas fórmulas do PHP
• Só muda o conceito de bloqueio máximo (Bi).
– Duração da maior sessão crítica que pode
bloquear pelo algoritmo de Teto.
Teste de Escalonabilidade no PCP
P1
P2
P3
P2
P3
Modelar no Cheddar
Tar. Periódicas
Período
T. de Computação
Bi
Prioridade RM
Compartilhamento
Tarefa A
Tarefa B
Tarefa C
15
20
25
10
8
6
2
1
0
1
2
3
S1, S2
S1, S3
S2, S3
Tar. Periódicas
Recurso /Intervalo
Recurso /Intervalo
Tarefa A
Tarefa B
S1 (1-2)
S1(2-3)
S2(3-4)
S3(1-2)
Tarefa C
S2(3-7)
S3(2-8)
Atividades para Casa
• Modelar no Cheddar esta escala
P1
P2
P3
P2
P3
Referências
• Farines
– Seções 2.5.3 a 2.6