Anomalias de
Escalonamento
Departamento de Electrónica, Telecomunicações e Informática
Universidade de Aveiro
Sistemas de Tempo-Real
Segunda-feira, 23 de Outubro de 2006
Hélder Cabrita 27470
Daniel Castanheira 27520
Motivação



Escalonamento de tarefas
Tipos de Escalonamento
Utilização de multi-processamento
– Possibilidade de várias tarefas atendidas
ao mesmo tempo.
– Problemas associados.
Tipos de Escalonamento






Preemptive vs. non-preemptive;
Síncrono (all processes arrive at once);
Assíncrono (processes arrive one by one);
Off-line (arrival time, computation time,
deadline of all process known in advance)
ou on-line;
Independente, ou com relação de
dependência;
Aperiódico vs. periódico vs. híbrido (misto)
Anomalias de
escalonamento

Uma alteração aparentemente positiva
no sistema (redução da carga ou
aumento dos recursos) pode causar
uma perda performance.
Anomalias de
escalonamento



Adição de processadores
Reduzir a precedência entre tarefas
Redução do tempo de execução de
tarefas
– Podem aumentar o tempo de execução!!!
Exemplos
Representação da precedência entre tarefas Jx:
J1 (3)
J9 (9)
Legenda:
J8 (4)
J2 (2)
J1 (3)
J9 só pode ser executada depois de J1.
J7 (4)
J3 (2)
J1 (3) – a tarefa J1 tem um tempo de
execução de 3 unidades de tempo.
J6 (4)
J4 (2)
J5 (4)
Escalonamento óptimo das tarefas Jx em 3 processadores:
P1 1
P2 2 4
P3 3
0
2
5
6
4
6
9
7
8
8
10
12
J9 (9)
14
Unidades de tempo
Adicionando 1
processador
Escalonamento óptimo das tarefas Jx em 4 processadores:
P1 1
P2 2
P3 3
P4 4
0

5
6
7
2
4
8
9
6
8
10
12
14
Unidades de tempo
O tempo de processamento
aumentou!!!
– Com 3 processadores: 12 UT
– Com 4 processadores: 15 UT
Reduzir a precedência
entre tarefas
O tempo de processamento aumentou!!!
Representação da precedência entre tarefas Jx:

J1 (3)
J9 (9)
– Com 4 precedências:
J8 (4) 12 UT
J2 (2)
J9 só pode ser executada depois de J1.
J7 (4) 16 UT
– Com 2 precedências:
J1 (3) – a tarefa J1 tem um tempo de
J3 (2)
Legenda:
execução de 3 unidades de tempo.
J6 (4)
J4 (2)
J5 (4)
Escalonamento óptimo das tarefas Jx em 3 processadores:
8
P1 1
5
P2 2 4
7
P3 3
0
2
4
6
9
6
8
10
12
14
Unidades de tempo
Redução do tempo de
execução de tarefas em 1 UT
Escalonamento óptimo das tarefas Jx em 3 processadores:
P1 1
P2 2 4
P3 3
0

5
6
7
2
8
4
6
9
8
10
12
14
Unidades de tempo
O tempo de processamento
aumentou!!!
Anomalia num
monoprocessador
Conclusão


Se um conjunto de tarefas é escalonado
optimamente numa unidade de multiprocessamento, com determinadas prioridades
atribuídas, tempos de execução fixos e limites de
precedência, uma alteração aparentemente positiva
do sistema pode causar uma redução da
performance do mesmo.
Atribuição de prioridades não é uma boa solução!
Esta confunde dois conceitos:
– Quão importante é algo?
– A quem deverá ser atribuído “o processador” a seguir?
Bibliografia




http://www.cs.hmc.edu/~keller/courses/cs1
56/s98/slides/399.html
http://www.soe.ucsc.edu/classes/cmpe117/
Winter05/cmpe117luca/lecture_aperiodic_scheduling.pdf
http://www.cs.chalmers.se/~phs/Teaching/
Realtime.ppt
http://www.ce.chalmers.se/edu/year/2005/c
ourse/EDA420/Documents/Slides/Slides_7_4
up.pdf