22

Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

  • Upload
    vokiet

  • View
    221

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Algoritmos de Escalonamento III

Eduardo Ferreira dos Santos

Ciência da Computação

Centro Universitário de Brasília � UniCEUB

Abril, 2017

1 / 22

Page 2: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Sumário

1 Escalonamento Deadline Monotônico

2 Classi�cação

2 / 22

Page 3: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Escalonamento Deadline Monotônico

1 Escalonamento Deadline Monotônico

2 Classi�cação

3 / 22

Page 4: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Escalonamento Deadline Monotônico

Conceitos

Extensão do algoritmo Rate Monotonic;

O deadline relativo igual ao período da tarefa pode ser bastanterestritivo.

4 / 22

Page 5: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Escalonamento Deadline Monotônico

Premissas

1 Tarefas periódicas e independentes;

2 O tempo de computação de cada tarefa Ci é conhecido e constante(Worst Computation Time);

3 O tempo de chaveamento entre as tarefas é considerado nulo;

4 Deadline relativo menor ou igual ao perído da tarefa: Di ≤ Pi

5 / 22

Page 6: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Escalonamento Deadline Monotônico

Atribuição de prioridades no DM

Ordenação baseada nos deadlines relativos das tarefas:

Atribuição na ordem inversa do deadline relativo;Deadlines menores possuem menor prioridade.

Prioridades �xas;

Escalonamento estático e online;

Também é um algoritmo ótimo na sua classe de problemas.

6 / 22

Page 7: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Escalonamento Deadline Monotônico

Exemplo

Figura 1.1: Exemplo de escalonamento DM [FARINES and MELO, 2000]

7 / 22

Page 8: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

1 Escalonamento Deadline Monotônico

2 Classi�cação

8 / 22

Page 9: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

De�nições [Chagas, 2016]

Escalonamento Ordenar tarefas na �la de pronto;

Escala Ordem de ocupação do processador pelas tarefas disponíveisna �la de pronto;

Escalonador Programa responsável pela gestão do processador em tempode execução.

9 / 22

Page 10: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Estados dos processos

Figura 2.1: Estados dos processos [Chagas, 2016]

10 / 22

Page 11: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Escalonamento

Figura 2.2: Descrição do modelo de escalonamento [Chagas, 2016]

11 / 22

Page 12: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

De�nição

Escalonar: Ordenar as tarefas na �la de pronto.

Os algoritmos de escalonamento podem ser[FARINES and MELO, 2000]:

Preemptivos Tarefas podem ser interrompidas em tempo de execução;

Não preemptivos Tarefas não podem ser interrompidas por outras maisprioritárias;

Estáticos Escalonamento calculado com base em parâmetros �xosatribuídos às tarefas;

Dinâmicos Baseados em parâmetros que mudam em tempo de execução.

12 / 22

Page 13: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

De�nição

Escalonar: Ordenar as tarefas na �la de pronto.

Os algoritmos de escalonamento podem ser[FARINES and MELO, 2000]:

Preemptivos Tarefas podem ser interrompidas em tempo de execução;

Não preemptivos Tarefas não podem ser interrompidas por outras maisprioritárias;

Estáticos Escalonamento calculado com base em parâmetros �xosatribuídos às tarefas;

Dinâmicos Baseados em parâmetros que mudam em tempo de execução.

13 / 22

Page 14: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Classi�cação

Em relação aos parâmetros enviados para as tarefas, os algoritmospodem ser:

on-line A escala é produzida em tempo de execução;o�-line A escala é produzida em tempo de projeto.

Os problemas de escalonamento de tempo real podem ser reduzidos auma solução polinomial (NP-Completos)

14 / 22

Page 15: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Carga computacional [Chagas, 2016]

De�nição: Somatório dos tempos de computação na �la de pronto.

Carga Estática (Limitada)

Todas as tarefas são bem conhecidas em tempo deprojeto;Modeladas através de tarefas periódicas e esporádicas .

Carga Dinâmica (Ilimitada)

Características de chegada da tarefa não pode serantecipada;Modeladas através de tarefas aperiódicas.

15 / 22

Page 16: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Abordagens

Figura 2.3: Abordagens de escalonamento em tempo real[FARINES and MELO, 2000]

16 / 22

Page 17: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Abordagens de escalonamento [Chagas, 2016]

Garantia em tempo de projeto I

Carga computacional dinâmica;Teste de escalonabilidade em tempo de projeto.

Garantia em tempo de execução II

Carga computacional dinâmica;Sistemas críticos que operam em ambientes nãodeterminísticos.

Abordagens de melhor esforço III

Teste de escalonabilidade em tempo de execução;Não existe previsão de pior caso e não consegue preverrecursos para todas as situações de carga.

17 / 22

Page 18: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Escalonamento estático [Chagas, 2016]

Escalonamento estático ou executivo cíclico;

A escala é de�nida durante a fase do projeto (escalonamento o�ine);

Tempo de processador atribuído a cada tarefa;

Garantia de escalonabilidade fornecida pela inspeção da lista deescalonamento (deadline da tarefa).

18 / 22

Page 19: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Dirigido a prioridades

Dirigidos de acordo com suas prioridades em tempo de execução;

Prioridades �xas: RM ou DM;

Prioridades dinâmicas;

Preemptivos ou não preemptivos.

19 / 22

Page 20: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Teste de escalonabilidade

Figura 2.4: Teste de escalabilidade real [FARINES and MELO, 2000]

20 / 22

Page 21: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

Chagas, F. (2016).Notas de aula do Prof. Fernando Chagas.

FARINES, J. M. and MELO, R. (2000).Sistemas de Tempo Real, volume 1.IME-USP.

21 / 22

Page 22: Algoritmos de Escalonamento III - eduardosan.com · Algoritmos de Escalonamento III Eduardo Ferreira dos Santos Ciência da Computação Centro Universitário de Brasília UniCEUB

Classi�cação

OBRIGADO!!!

PERGUNTAS???

22 / 22