Escalonadores para sistemas I/O Bound

Round Robin

  • execução de processos de maneira justa e eficiente
  • tempo compartilhado
  • preemptivo
  • dá uma fatia de tempo para cada processo
  • fila de prontos é cíclica → após o processo terminar de usar sua fatia, ele vai para o final, caso não tenha terminado de executar tudo
  • tempo de resposta rápido, já que os processos recebem CPU frequentemente
  • Overhead de comutação (troca de contexto)
  • desempenho variável → processos longos são prejudicados quando fatias de tempo (quantum) pequenos são usados
  • utilizar quantum muito grande, faz ele se tornar uma FIFO
  • quantum muito pequeno faz aumentar o overhead
Para encontrar o melhor quantum (Q) é interessante manter o equilibrio entre o 
overhead e um tempo razoavel de execução


chaveamento = 1ms

Q = 4ms
total = 4ms + 1ms = 5ms

nesse caso, 20% do tempo é perdido para o overhead com o chaveamento 
de processos



Q = 99ms
total = 99ms + 1ms = 100ms

nesse segundo caso, só 1% do tempo é perdido com a troca de contexto, 
mas há muito tempo de espera para a troca de procesos


Levando em consideração esses exemplos, escolher um quantum Q intermediario, 
como 20ms seria uma opção viavel

Baseado em prioridade

  • varias filas para cada nível de prioridade
  • processos de prioridade maior irão antes
  • pode utilizar o round-robin para gerenciar a fila
  • executa primeiro toda a fila de maior prioridade e depois vai descendo os níveis
  • pode ser tanto preemptivo como não preemptivo, dependendo do algoritmo escolhido
  • pode ajustar a prioridade dinamicamente, para evitar inanição (starvation, processos que nunca seriam executados devido a sua baixa prioridade)

Múltiplas filas

  • cada fila pode ter características distintas (processos para processamento em lote, processos interativos, processos com prioridade, etc.)
  • cada fila pode ter um algoritmo diferente para gerenciamento
  • cada fila terá uma prioridade diferente
  • pode ser preemptivo quando processos de maior prioridade entram
  • pode dar-se um tempo de execução limitado para cada fila
  • pode mover processos entre filas
  • possui overhead no gerenciamento das filas
  • pode sofrer de starvation

Loteria

  • cada processo recebe um ticket
  • a cada troca de processo um ticket é sorteado, assim o processo sorteado por ocupar a CPU
  • pode dar mais tickets para um processo para aumentar a chance dele ser sorteado(prioridade)
  • é mais justo
  • não é preemptivo
  • possui variabilidade no tempo de resposta

Fair-Share

  • leva em consideração quem é o dono do processo (user, sistema, etc.)
  • cada dono possui uma fração de tempo para usar a CPU, escalonando os processos a partir dai
  • se um user possui mais processos ele terá mais tempo

Escalonadores para sistemas de tempo real

  • hard real time → não pode atrasar (critico)
  • soft real time → alguns atrasados são tolerados
  • eventos (periódicos ou aperiódicos) causam execução de processos
  • algoritmos preemptivos
  • algoritmos usados podem ser: estáticos (define a ordem de execução antes) ou dinâmicos (avalia qual será executado em tempo de execução)

Earliest deadline first

  • preemptivo e dinâmico
  • tarefa com menor deadline tem prioridade
  • se chegar um com menor deadline ele chaveia para este com menor
  • possui overhead

Rate monotonic scheduling

  • preemptivo e estático
  • prioridade é dada pela frequência de execução
  • ótimo para sistemas periódicos e com processos independentes

Least laxity first (last stack time first)

  • escalona com base na folga (tempo restante até o deadline — tempo restante para completar a tarefa )
  • processo com menor folga vai primeiro
  • pode ter bastante overhead