Diferenças

Aqui você vê as diferenças entre duas revisões dessa página.

Link para esta página de comparações

Próxima revisão		 Revisão anterior
so:algoritmos_de_escalonamento [2010/02/08 12:04] – created mazieroso:algoritmos_de_escalonamento [2011/05/25 08:11] (atual) – maziero
Linha 1: Linha 1:
 +====== Algoritmos de escalonamento ======
 +
 +O objetivo deste projeto é escrever um programa para simular o escalonamento de um conjunto de tarefas usando os algoritmos de escalonamento de processador mais conhecidos. O programa deverá suportar os seguintes algoritmos:
 +
 +  * FCFS (//First Come, First Served//)
 +  * //Shortest Job First//
 +  * <del>//Shortest Remaining Time First//</del>
 +  * Por prioridade, sem preempção
 +  * Por prioridade, com preempção por prioridade
 +  * //Round-Robin// com //quantum// = 2s, sem prioridade
 +  * <del>//Round-Robin// com //quantum// = 5s, sem prioridade</del>
 +  * Round-robin com prioridade e envelhecimento (t<sub>q</sub>=2, α=1)
 +
 +No caso dos escalonamentos //round-robin//, o envelhecimento deve ocorrer a cada quantum e não há preempção por prioridade.
 +
 +O programa deverá ler os dados dos processos da entrada padrão (//stdin//). Cada linha da entrada corresponde a um processo, com os seguintes dados fornecidos como inteiros separados por um ou mais espaços em branco:
 +
 +  * data de criação
 +  * duração em segundos
 +  * prioridade estática (escala de prioridades positiva)
 +
 +Um exemplo de entrada para o simulador poderia ser:
 +
 +<code tasks1.dat>
 +0 5 2
 +0 2 3
 +1 4 1
 +3 3 4
 +</code>
 +
 +Nesse exemplo de entrada, o processo P1 tem data de criação 0, sua execução dura 5 segundos e sua prioridade é 2. Esse formato de entrada deverá ser respeitado, pois o professor pode testar seu simulador com outros dados de entrada. Observe que essa listagem não precisa necessariamente estar ordenada por data de criação de cada processo.
 +
 +Para cada algoritmo, o simulador deverá produzir as seguintes informações em sua saída padrão (//stdout//):
 +
 +  * tempo médio de vida
 +  * tempo médio de espera
 +  * número de trocas de contexto
 +  * diagrama de tempo da execução
 +
 +Para simplificar, o diagrama de tempo de cada execução pode ser gerado na vertical, de cima para baixo (uma linha por segundo), conforme mostra o exemplo a seguir:
 +
 +<code>
 +tempo   P1  P2  P3  P4
 + 0- 1   ##  --
 + 1- 2   ##  --  --
 + 2- 3   --  ##  --
 + 3- 4   --  ##  --  --
 + 4- 5   --      ##  --
 + 5- 6   --      ##  --
 + 6- 7   ##      --  --
 + 7- 8   ##      --  --
 + 8- 9   --      --  ## 
 + 9-10   --      --  ##
 +10-11   --      ##  --
 +11-12   --      ##  --
 +12-13   ##          --
 +13-14               ##
 +</code>
 +
 +**Deve ser entregue ao professor o código-fonte em C do simulador, devidamente comentado**.
 +
 +Sugestão de implementação (pseudo-código que deve ser ajustado para cada política):
 +
 +<code>
 +início
 +  lê dados das tarefas da entrada padrão
 +  imprime cabeçalho do diagrama
 +  
 +  t = 0
 +  enquanto t < tmax
 +
 +    se há uma tarefa rodando
 +      se a tarefa rodando chegou ao fim da execução
 +        migra a tarefa para o estado terminado 
 +        libera o processador
 +      senão
 +        se a tarefa rodando chegou ao fim de seu quantum
 +        migra a tarefa para a fila de prontos
 +        libera o processador
 +      fim se
 +    fim se
 +
 +    para cada tarefa i
 +      se a tarefa i inicia agora (em t)
 +        coloca a tarefa na fila de prontos
 +      fim se
 +    fim para
 +
 +    se o processador estiver livre
 +      se houver tarefa na fila de prontas
 +        escolhe uma tarefa da fila de prontas
 +        migra essa tarefa para o estado "rodando"
 +      fim se
 +    fim se
 +
 +    imprime linha do diagrama com o estado de cada tarefa
 +
 +    incrementa o tempo (t++)
 +    incrementa contadores da tarefa corrente (tempo de vida e de quantum)
 +
 +  fim enquanto
 +
 +  calcula e imprime tempos médios
 +fim
 +</code>
 +
 +Sugere-se definir para cada tarefa:
 +  * identificador
 +  * datas de inicio e de conclusão
 +  * duração (tempo necessário no processador)
 +  * prioridades estática e dinâmica
 +  * estado atual (nova, pronta, rodando, terminada, ...)
 +  * tempo já executado (total e no quantum atual)
 +  * ... (outros campos podem ser necessários para algumas políticas)