Aula 09.2 - Algoritmos de Escalonamento (RR e multinível)

Escalonador Round-Robin

• O escalonador Round-Robin permite que cada processo receba a CPU por um intervalo de tempo fixo, denominado "Quantum".

• Os Quantum geralmente variam de milissegundos a dezenas ou centenas de milissegundos.

• Quando um processo atinge seu tempo de Quantum, ele é interrompido e colocado de volta na fila de prontos.

Overhead e Interatividade

• A interrupção periódica do processo gera um custo adicional, conhecido como "overhead".

  • O overhead mais comum é relacionado à troca de contexto.

• Apesar do overhead, o algoritmo Round-Robin favorece a interatividade.

  • Se o quanta for muito grande, o algoritmo se aproxima de um FIFO, onde processos são executados em ordem, resultando em pouca interatividade.

  • Se o quanta for muito pequeno, o overhead aumenta e pode resultar em mais tempo gasto nas trocas de contexto do que na execução efetiva dos processos.

Garantias do Modelo Round-Robin

• Garante que cada processo receba acesso à CPU, assegurando que nenhum processo espere mais do que um quanta para ser executado novamente.

• O plural de quanta é "quantas".

• Assume que N é a quantidade de processos na fila, e cada processo é alternadamente atribuído à CPU, garantindo justiça no uso dos recursos computacionais disponíveis.

Exemplo Prático

• Considerando um quanta de 20 unidades de tempo:

  • Processo P1 executa por 21 unidades; após 20 unidades, passa a ter 33 unidades restantes.

  • Processo P2 gasta 17 unidades e termina antes do quanta expirar, com 37 unidades restantes.

  • Processo P3 executa por 20 unidades, utilizando o quanta até 57 unidades.

  • P4 executa de 57 a 77, com 4 unidades restantes.

  • Retorno ao P1, que executa por 20 unidades e termina, restando 13 unidades.

  • O processo continua em um ciclo entre P1, P2, P3 e P4.

Alternâncias e Trocas de Contexto

• O algoritmo Round-Robin consegue manter uma boa capacidade de resposta ao alternar entre os processos.

• A relação entre o tamanho do quanta e a quantidade de trocas de contexto:

  • Quanto maior o quanta, menor o número de trocas de contexto.

  • Para um processo que consome 10 unidades, com um quanta de 12, não haverá trocas; com um quanta de 1, haverá 9 trocas.

Algoritmos de Múltiplas Filas

• Alternativa aos algoritmos tradicionais de escalonamento.

• Permitem classificar processos com características distintas (ex: interativos vs. batch).

  • Usam diferentes algoritmos de escalonamento para cada fila, baseando-se em prioridades.

• Permitem mover processos entre filas, oferecendo flexibilidade e adaptabilidade ao sistema.

Escalonamento em Ambientes Multiprocessados

• Com a chegada de múltiplas CPUs, o escalonamento se torna mais complexo.

• Pode haver variações entre unidades de processamento homogêneas (ex: multi-core) e heterogêneas (ex: diferentes CPUs com bancos de memória distintos).

• Trocas de processos entre CPUs podem alterar significativamente o desempenho devido a diferenças de acesso à memória.

Considerações sobre Tempo Real

• Em sistemas de tempo real, há uma preocupação com a latência e o tempo de resposta a tarefas críticas.

  • Importante em aplicações como controle de sistemas, carros autônomos, aviação, etc.

• Os sistemas que não são estritamente tempo real ainda necessitam de escalonamento eficiente, como no caso de vídeos em tempo real.