Diferenças

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

--- so:algoritmos_de_escalonamento [2010/02/08 16:46] – maziero
+++ so:algoritmos_de_escalonamento [2011/05/25 11: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>
+5 2
+2 3
+4 1
+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
+- 1   ##  --
+- 2   ##  --  --
+- 3   --  ##  --
+- 4   --  ##  --  --
+- 5   --      ##  --
+- 6   --      ##  --
+- 7   ##      --  --
+- 8   ##      --  --
+- 9   --      --  ##
+-10   --      --  ##
+-11   --      ##  --
+-12   --      ##  --
+-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)