Múltiplas filas

Múltiplas Filas é um tipo de algoritmo de escalonamento, no qual são usadas filas de processos. Cada fila tem um determinado nível de prioridade. Sendo um dos mais antigos agendadores de prioridade, estava presente no CTSS (Compatible Time-Sharing System - Sistema Compatível de Divisão por Tempo).

No algoritmo de Múltiplas Filas, também pode ser aplicado particularmente, em cada fila, diferentes algoritmos como por exemplo, o algoritmo Round-robin ou FCFS (First-come, first-served).

Agendamento de Processos

Fila de vários níveis o algoritmo de escalonamento é usado em cenários onde os processos podem ser classificados em grupos com base na propriedade como tipo de processo, tempo de CPU, acesso IO, tamanho da memória, etc. Uma classificação geral dos processos é processos de primeiro plano e de segundo plano. Em um algoritmo de agendamento de fila multinível, haverá um número de filas 'n', onde 'n' é o número de grupos nos quais os processos são classificados. Cada fila receberá uma prioridade e terá seu próprio algoritmo de agendamento, como Round-robin scheduling ou FIFO. Para que o processo em uma fila seja executado, todas as filas de prioridade mais altas do que deveriam estar vazias, o que significa que o processo nessas filas de alta prioridade deve ter concluído sua execução. Nesse algoritmo de agendamento, uma vez atribuído a uma fila, o processo não será movido para nenhuma outra fila.

Distribuição de Prioridades

O Sistema Operacional atende inicialmente as filas de prioridade mais alta, então apenas quando uma fila é esvaziada é que o escalonador passa para a próxima fila.

Outros métodos de escalonamento podem ser combinados com múltiplas filas, sendo aplicado por exemplo, um em cada fila:

• Escalonamento por Múltiplas Filas traz alguns benefícios, entre eles estão:
  • Aumentar a utilização da CPU: Com isto as chances da CPU ficar ociosa diminuem, aproveitando possíveis tempos de espera para a execução de outro processo.
  • Maximizar o throughput: Mais processos serão executados num determinado tempo.
  • Minimizar o turnaround: Nesse caso o tempo total dos processos na CPU será menor.
  • Minimizar o tempo de espera: O tempo de I/O dos processos será menor.
  • Minimizar o tempo de resposta: O tempo em que os processos esperam para receber a CPU pela "primeira vez" será menor.
  • Diminuir o uso de recursos: Menos recursos serão usados pelos processos, evitanto Deadlock.
  • Priorizar processos que segurem recursos chave: Processos que necessitam de certos recursos com mais frequência do que outros, terão prioridade elevada para fazê-los com mais facilidade.
  • Não degradar o sistema: Assim, mais formas de escalonamento ocorrerão fazendo com que o máximo de processos receba a CPU, aplicando-se prioridades dinâmicas e formando um ciclo que evita que eles entrem em Starvation.
  • etc.

Múltiplas Filas com Realimentação

Os processos não permanecem em uma mesma fila até o término do processamento, pois o SO faz um ajuste dinâmico (mecanismo adaptativo) para ajustar os processos em função do comportamento do sistema. Os processos não são previamente associados às filas, mas direcionados pelo sistema entre as diversas filas com base no seu comportamento.

• Parâmetros:
  • Número de filas.
  • Algoritmo de escalonamento para cada fila.
  • Método para mudar (promover ou rebaixar) o processo de fila.
  • Método para determinar em que fila um processo entra.
• Método mais complexo:
  • Um exemplo (existem outras variações).
  • Processos novos entram no fim da primeira fila.
  • Nas filas, os processos são escalonados segundo Round-robin.
  • O quantum varia de uma fila para outra (aumenta em direção às últimas, quantum 1, 2 para a segunda, etc).
  • Os processos das primeiras filas têm maior prioridade (um processo não pode ser escolhido, a menos que, as filas anteriores estejam vazias).
  • Um processo em execução é interrompido caso apareça um processo em uma das filas anteriores à sua.
  • Sempre que um processo esgotar seu quantum, ele é suspenso na fila da próxima classe de prioridade.
  • Se o processo liberar a CPU, sem preempção, sai da estrutura de filas.
  • Quando um processo volta à estrutura, é colocado em uma fila de prioridade mais alta do que estava antes de sair.

Divisão dos Processos

• Cada fila possui seu próprio algoritmo de escalonamento;
• Os Processos são previamente divididos em grupos em função do tipo de processamento realizado:
• A cada grupo é aplicado um mecanismo de escalonamento adequado.
• Por exemplo, filas distintas podem ser utilizadas para processos em background ou foreground.A fila foreground pode utilizar o escalonamento circular enquanto que background utiliza o FCFS;

Cada fila pode possuir prioridade absoluta sobre as filas de menor prioridade ou o tempo do processador pode ser compartilhado entre elas. Por exemplo, a fila foreground pode receber 80% do tempo do processador enquanto que background recebe 20%.

Problemas

Starvation: Para evitar esse problema, o Sistema Operacional pode aplicar prioridades dinâmicas. Neste caso, os processos que não tiveram acesso à CPU durante muito tempo, têm sua prioridade momentaneamente elevada. Em sistemas interativos esse mesmo mecanismo também pode ser empregado, porque o usuário deve possuir uma prioridade alta para poder trocar de programa quando desejar.

Inversão de Prioridade: Dua tarefas A e B de alta e baixa prioridades, precisam acessar um recurso R (um determinado dispositivo de E/S, uma impressora por exemplo). Considerando que A inicia após B adquirir o recurso R, a tarefa de maior prioridade A é obrigada a esperar B. Problemas surgem quando uma nova tarefa M, de média prioridade e que não utiliza R, é iniciada durante este intervalo. M é a tarefa de maior prioridade não bloqueada, portanto será escalonada antes de B que continua utilizado o recurso e A continua aguardando pelo recurso. A tarefa M irá executar, então B poderá executar - pelo menos ao ponto de liberar R - e ao final A executa. Neste cenário uma tarefa de média prioridade foi executada antes de uma de maior prioridade, demonstrando uma inversão de prioridade.