ESCALONAMENTO EM SISTEMAS DE TEMPO REAL
como deve ser o escalonamento de diversAs tarefas envolvidas em um sistema de tempo real?
Através do escalonamento de tarefas, se planeja e organiza formas para as tarefas atenderem seus deadlines, requisito básico para esse tipo de processamento.

Objetivo do escalonamento:
execução das tarefas críticas ("hard"), em primeiro lugar.
para as tarefas não críticas, tanto quanto for possível, tenta-se ter seus tempos de resposta minimizados.

lembrando:
As tarefas temporalmente críticas podem ser divididas em periódicas e não periódicas. 
Uma tarefa não periódica tem associado um deadline para iniciar ou terminar (ou ambos).

para Uma tarefa periódica, a restrição adicional consiste em cada instância executar uma única vez dentro do respectivo período.

A definição da seqüência de execução das tarefas (escalonamento) pode ser realizada estática ou dinamicamente.

O escalonamento estático é decidido em tempo de compilação, pois todas as tarefas envolvidas são conhecidas, bem como seus deadlines e periodicidades.
O escalonamento dinâmico é decidido em tempo de execução, pois não se conhece de antemão quais são as características das tarefas ou sua quantidade, que mudam no tempo. 

Um algoritmo de escalonamento é estático se as prioridades para as tarefas são atribuídas uma única vez, antes da execução das tarefas e não são mais alteradas durante a execução.
Um algoritmo de escalonamento é dinâmico se as prioridades das tarefas são determinadas em tempo de execução, podendo ser alteradas de acordo com a evolução do sistema.

Na prática, a maior parte dos sistemas de tempo real envolve um número de tarefas que pode ser escalonado estaticamente, bem como outro número de tarefas que exige escalonamento dinâmico.

Função de um Escalonador
Determinar para um dado conjunto de tarefas:
•	se a ordem de execução das tarefas existe.
•	se existir, então definir qual é essa ordem, de tal maneira que as restrições de tempo, distribuição, precedência, comunicação e recursos das tarefas sejam satisfeitas.
Objetivos:
•	Garantir que tarefas com rígidas restrições de tempo satisfaçam seus deadlines.
•	Obter um alto grau de utilização de recursos para tarefas com deadlines. 
•	Fornecer bons tempos médios de resposta para tarefas que não possuem deadlines.
•	Garantir a estabilidade em momentos de sobrecarga transitória do sistema.
Uma solução ótima é bastante difícil e às vezes computacionalmente intratável (NP difícil). Heurísticas são necessárias para:
•	Ou provar que o escalonamento não é possível,
•	Ou achar uma seqüência de escalonamento, desde que seja fácil fazê-lo,

Fator de Utilização
A taxa de garantia é o número total de tarefas garantidas dividido pelo número de tarefas que chegam.
O fator de utilização para uma tarefa i é definido por:

µ = E(i) / T(i)

E é o tempo de execução, T a periodicidade e i indica qual é a tarefa
µ corresponde à fração de tempo de processador gasto na execução da tarefa.

Condição necessária para que um conjunto de tarefas dinâmicas possa ser escalonado:
o fator de utilização do conjunto não seja maior que o número de processadores disponíveis.

Earliest-Deadline-First (EDF)
EDF é um algoritmo dinâmico e centralizado (monoprocessado) que:
•	Trata de tarefas periódicas.
•	Usa preempção sobre tarefas.
•	As tarefas não apresentam restrições de precedência ou de comunicação, e também não necessitam de recursos específicos para executar, ou seja, são independentes entre si.
•	O deadline D de cada tarefa é igual ao fim de seu período T, considerando o momento de início A.
•	O tempo de execução E máximo requerido é constante e é conhecido a priori.
•	O tempo necessário para troca de contextos pode ser ignorado.
•	P corresponde ao momento em que a tarefa está pronta para iniciar sua execução.

Prioridades são associadas às tarefas de acordo com seus deadlines. Deadline mais próximo, prioridade mais alta. Os períodos das tarefas podem mudar a qualquer momento, ou seja, as prioridades podem mudar.
O fator de utilização do conjunto de tarefas µ:
µ = somatória (E(i) / T(i)) ≤ 1, 
i correspondendo a cada tarefa do conjunto a ser escalonado. (Porque o resultado é ≤ 1?)

Exemplo de um Escalonamento EDF
Supondo duas tarefas A e B

	E	T	D	
A	10	20	20	
B	25	50	50	

E - Tempo de Execução
T - Período
D – Deadline

(Verificar o fator de utilização)

Em t = 0, as tarefas A e B iniciam o seu primeiro período. Como a tarefa A tem deadline corrente mais próximo (D = 20), A é escalonada e executada até t = 10, quando é completada.

Em t=10, sendo B a única tarefa pronta, esta é escalonada e executada até t = 20, quando começa o novo período de A, ou seja., aparece nova instância de A. Como há preempção e o deadline da nova A (D = 40) é mais próximo que o da tarefa B corrente (D = 50), B perde a CPU para A.

A partir de t = 20, a instância de A é executada até t = 30, sendo completada. De t = 30 a t = 40, B volta a ser executada, quando chega a próxima instância de A. Mas, B por ter deadline mais próximo (D = 50) continua em execução até t = 45, quando é completada.

Em t = 45, a nova instância de A volta a ser escolanada e permanece em execução até t = 55, mesmo quando nova instância de B aparece em t = 50.

Tente explicar o porque da tarefa B ser executada apenas até t = 60 e complete o escalonamento até t = 100.

o que ocorre a partir de t = 100, o mínimo múltiplo comum dos períodos de A e B?

 Exercícios
1.	Você considera que os algoritmos de escalonamento vistos na disciplina de Sistemas Operacionais são aplicáveis ao problema de escalonamento de tarefas em sistemas de tempo real? Justifique.
2.	Considerando as diferentes restrições que podem se aplicar às tarefas de um sistema de tempo real (deadlines, periodicidade e tempo máximo de execução de uma tarefa, além de precedência, comunicação, recursos e preempção), qual seria o grau de complexidade de um algoritmo de escalonamento para esse tipo de processamento (lembrar de análise de algoritmos)?
3.	Considerando o algoritmo EDF, discutido como solução para o escalonamento do braço do disco dentro de um driver, a idéia de atender o deadline mais próximo poderia ser usada para escalonar tarefas em um sistema de tempo real? 
4.	Dê um exemplo de sistema de tempo real que possa ter suas tarefas escalonadas com um algoritmo EDF o qual permita a preempção de tarefas em execução com a chegada de uma tarefa com deadline mais prioritário.
5.	Como é possível saber se determinado conjunto de tarefas dinâmicas é escalonável?
6.	Porque se usam heurísticas nos algoritmos de escalonamento para tempo real?