Anomalias de Anomalias de EscalonamentoEscalonamento

Hélder Cabrita 27470Hélder Cabrita 27470

Daniel Castanheira 27520Daniel Castanheira 27520

Departamento de Electrónica, Telecomunicações e Departamento de Electrónica, Telecomunicações e InformáticaInformática

Universidade de AveiroUniversidade de Aveiro

Sistemas de Tempo-RealSistemas de Tempo-Real

Segunda-feira, 23 de Outubro de 2006Segunda-feira, 23 de Outubro de 2006

MotivaçãoMotivação

Escalonamento de tarefasEscalonamento de tarefas Tipos de EscalonamentoTipos de Escalonamento Utilização de multi-Utilização de multi-

processamentoprocessamento– Possibilidade de várias tarefas Possibilidade de várias tarefas

atendidas ao mesmo tempo.atendidas ao mesmo tempo.– Problemas associados.Problemas associados.

Tipos de Tipos de EscalonamentoEscalonamento 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 Anomalias de escalonamentoescalonamento Uma alteração aparentemente

positiva no sistema (redução da carga ou aumento dos recursos) pode causar uma perda performance.

Anomalias de Anomalias de escalonamentoescalonamento Adição de processadoresAdição de processadores Reduzir a precedência entre Reduzir a precedência entre

tarefastarefas Redução do tempo de execução Redução do tempo de execução

de tarefasde tarefas

– Podem aumentar o tempo de Podem aumentar o tempo de execução!!!execução!!!

ExemplosExemplos

Representação da precedência entre tarefas Jx:

123

487

6

95

P1P2P3

0 2 4 6 8 10 12 14

Escalonamento óptimo das tarefas Jx em 3 processadores:

J1 (3) J9 (9)

Legenda:

J9 só pode ser executada depois de J1.

J1 (3) – a tarefa J1 tem um tempo de execução de 3 unidades de tempo.

Unidades de tempo

J1 (3)

J2 (2)

J3 (2)

J4 (2)

J9 (9)

J8 (4)

J7 (4)

J6 (4)

J5 (4)

Adicionando 1 Adicionando 1 processadorprocessador

1234

8

76

95P1P2P3

0 2 4 6 8 10 12 14

P4Unidades de tempo

O tempo de processamento O tempo de processamento aumentou!!!aumentou!!!– Com 3 processadores: 12 UTCom 3 processadores: 12 UT– Com 4 processadores: 15 UTCom 4 processadores: 15 UT

Escalonamento óptimo das tarefas Jx em 4 processadores:

Reduzir a precedência Reduzir a precedência entre tarefasentre tarefas

J1 (3)

J2 (2)

J3 (2)

J4 (2)

J9 (9)

J8 (4)

J7 (4)

J6 (4)

J5 (4)

Representação da precedência entre tarefas Jx:

Escalonamento óptimo das tarefas Jx em 3 processadores:

Legenda:

J9 só pode ser executada depois de J1.

J1 (3) – a tarefa J1 tem um tempo de execução de 3 unidades de tempo.

Unidades de tempo

O tempo de processamento O tempo de processamento aumentou!!!aumentou!!!– Com 4 precedências: 12 UTCom 4 precedências: 12 UT– Com 2 precedências: 16 UTCom 2 precedências: 16 UT

123

48

7 6

95

P1P2P3

0 2 4 6 8 10 12 14

O tempo de processamento O tempo de processamento aumentou!!!aumentou!!!

Redução do tempo de Redução do tempo de execução de tarefas em 1 execução de tarefas em 1 UTUT

123

48

76 95P1

P2P3

0 2 4 6 8 10 12 14 Unidades de tempo

Escalonamento óptimo das tarefas Jx em 3 processadores:

Anomalia num Anomalia num monoprocessadormonoprocessador

ConclusãoConclusão

Se um conjunto de tarefas é escalonado Se um conjunto de tarefas é escalonado optimamente numa unidade de multi-optimamente numa unidade de multi-processamento, com determinadas prioridades processamento, com determinadas prioridades atribuídas, tempos de execução fixos e limites atribuídas, tempos de execução fixos e limites de precedência, uma alteração aparentemente de precedência, uma alteração aparentemente positiva do sistema pode causar uma redução positiva do sistema pode causar uma redução da performance do mesmo.da performance do mesmo.

Atribuição de prioridades não é uma boa Atribuição de prioridades não é uma boa solução! Esta confunde dois conceitos:solução! Esta confunde dois conceitos:– Quão importante é algo?Quão importante é algo?– A quem deverá ser atribuído “o processador” a A quem deverá ser atribuído “o processador” a

seguir?seguir?

BibliografiaBibliografia

http://www.cs.hmc.edu/~keller/courseshttp://www.cs.hmc.edu/~keller/courses/cs156/s98/slides/399.html/cs156/s98/slides/399.html

http://www.soe.ucsc.edu/classes/cmpehttp://www.soe.ucsc.edu/classes/cmpe117/Winter05/cmpe117-luca/lecture_a117/Winter05/cmpe117-luca/lecture_aperiodic_scheduling.pdfperiodic_scheduling.pdf

http://www.cs.chalmers.se/~phs/Teachhttp://www.cs.chalmers.se/~phs/Teaching/Realtime.ppting/Realtime.ppt

http://www.ce.chalmers.se/edu/year/2http://www.ce.chalmers.se/edu/year/2005/course/EDA420/Documents/Slides/005/course/EDA420/Documents/Slides/Slides_7_4up.pdfSlides_7_4up.pdf