Unidade F - Gerenciamento do processador

Escalonador

Escalonador de curto prazo,também chamado scheduler, é a parte do sistema operacional que organiza e determina o funcionamento da fila de prontos e o tempo que cada processo terá de execução no processador.

O escalonador é avaliado em dois aspectos principais, que são;

• Quanto a produção (throughput¹)
• o escalonador precisa manter o processador ocupado por mais tempo e produzir mais em menos tempo;
• basicamente, queremos que o processador seja bem utilizado e não fique ocioso.
• Quanto ao tempo de resposta (turnaround time)
• baixo tempo médio de espera na fila do processador;
• basicamente, queremos que um processo não fique muito tempo esperando na fila.

Conforme o tipo de escalonador aplicado no sistema operacional, teremos um impacto diferente nos diferentes tipos de processos.

Tipos de processos

• I/O Bound – são processos caracterizados por fazer mais uso de requisições de I/O. Estes processos não “gastam” processador porque trabalham mais com entrada e saída. Exemplos:
• editores de texto: basicamente controlam teclado, mouse, discos, etc;
• browsers: basicamente utilizam rede;
• CPU Bound – são processos caracterizados por fazer mais uso de CPU. Estes processos precisam de CPU para trabalhar, fazendo pouca I/O. Exemplos:
• programas de criptografia: basicamente fazem muitos cálculos matemáticos para aplicar nos dados a serem criptografados/descriptografados.
• programas de cálculos científicos: cálculos matemáticos.

Algoritmos escalonadores

Estes algoritmos escalonadores são clássicos, ou seja, nem sempre são ou foram utilizados comercialmente.

Algoritmo FIFO (first-in/first-out)
Este algoritmo implementa uma fila simples, onde o primeiro processo que chega na fila é executado até seu encerramento (processo não sai do processador até terminar seu processamento).

• Vantagens:
• Favorece processos do tipo CPU Bound porque estes “pegam” a CPU e não soltam mais;
• Desvantagens:
• Causa um aumento no tempo de espera da fila;
• Analogia com o banco:
• Este escalonador equivale a uma fila de banco, com apenas UM caixa, onde a ordem de atendimento é definida pela chegada na fila. A insatisfação dos clientes está em:
• Não há atendimento prioritário;

Se algum cliente tiver muitos papéis para serem processados, o tempo de todos na fila irá aumentar.

Algoritmo SJF (Shortest Job First)
Trabalhos mais curtos primeiro - este algoritmo implementa uma fila ordenada pelo menor tempo de execução, ou seja, quanto menor o tempo de execução mais na frente da fila o processo está.

• Vantagens:
• Favorece processos I/O Bound, porque são rápidos na ocupação do processador;
• Processos rápidos ficam pouco tempo na fila de espera – diminui o tempo médio de espera.
• Problemas:
• Postergação indefinida – processos considerados lentos ficarão esperando na fila por tempo indeterminado;
• Impossibilidade de implementação – é impossível prever o tempo de execução de um processo.
• Analogia com o banco:
• Este escalonador equivale a uma fila de banco, com apenas UM caixa, onde a ordem de atendimento é definida pela quantidade de papéis a serem processados – se for rápido passa na frente. A insatisfação dos clientes está em:
• Não há atendimento prioritário;
• Se algum cliente tiver muitos papéis para serem processados, irá ficar na fila aguardando até que todos os “rapidinhos” sejam atendidos;

Muitos clientes afirmam que seu atendimento é “rapidinho”, mas na verdade tem muitos papeis para processamento – causando indignação na fila.

Algoritmo por prioridade
Trabalhos marcados com prioridade primeiro – este algoritmo implementa uma fila ordenada pela prioridade, ou seja, todo processo deve ter uma marca de prioridade². Esta prioridade irá definir a posição a ser ocupada na fila.

• Vantagens:
• Favorece processos com prioridade – independentemente de tipo;
• Desvantagens:
• Postergação indefinida de processos com baixa prioridade;
• Analogia com o banco:
• Este escalonador equivale a uma fila de banco, com apenas UM caixa, onde a ordem de atendimento é definida pela prioridade do cliente, que se tiver prioridade alta passa na frente. A insatisfação dos clientes está em:

Clientes com alta prioridade são sempre atendidos primeiro – deixando os de baixa prioridade por longos períodos na fila;

Algoritmo por prioridade com aging
Para eliminar a desvantagem de postergação indefinida do algoritmo escalonador por prioridade, podemos implementar um mecanismo de aumento de prioridade conforme o tempo de espera na fila. Isto é conhecido por aging³ - e no caso, a cada “rodada” de execuções, a prioridade do processo que está na fila aumenta, até que o mesmo será atendido.

Algoritmo por prioridade preemptivo e não-preemptivo

• Prioridade preemptivo – neste algoritmo escalonador, sempre que um processo de maior prioridade (do que o que está sendo executado) chegar na fila de prontos, o algoritmo retira o processo em execução e entrega o processador ao recém-chegado de maior prioridade.

Prioridade não-premptivo – neste algoritmo escalonador, quando um processo de maior prioridade (do que esta sendo executado) chegar na fila de prontos, o algoritmo não interfere na execução. Espera que a execução acabe para entregar o processador ao recém-chegado de maior prioridade.

Algoritmo Round Robin (fatia de tempo)
Este algoritmo escalonador é o mais comum entre os sistemas operacionais convencionais e que viabiliza a multiprogramação efetivamente – o algoritmo trabalha com fatia de tempo. Cada processo na fila tem um tempo de execução (já definido como quantum); a cada quantum, o processador troca de processo em execução (pelo mecanismo de chaveamento de contexto).

Este algoritmo ainda pode ser implementado, de forma associada, ao algoritmo por prioridade (que poderá ser preemptivo ou não-preemptivo). Garantindo um mecanismo de escalonamento de fatia de tempo com prioridade.

Múltiplas filas

Sistemas operacionais atuais trabalham com o conceito de múltiplas filas, em que o processador de duas ou mais filas de espera para execução, cada qual com um algoritmo escalonador específico. Podemos, por exemplo, termos um sistema com duas filas de espera, sendo:

Fila de processos do tipo foreground
Processos com interação direta do usuário, normalmente executados na presença do usuário e com necessidade de baixo tempo de resposta. Editores de texto e planilhas são típicos exemplos de processos deste tipo.

Esta fila poderia trabalhar com um algoritmo escalonador round-robin com prioridade preemptiva. Certamente os usuários de um sistema deste tipo teriam uma boa relação entre produção e de tempo de resposta do sistema computacional.
Fila de processos do tipo background

Processos sem interação de usuário, normalmente executados sem a presença do usuário ou disparados em batch. Podem, por exemplo ser executados durante a madrugada (quando normalmente ninguém mais está usando o sistema). Processos para cálculo de folha de pagamento ou processos de computação científica podem ser exemplos deste tipo de fila. Tipicamente, processos que consomem muita CPU.

Esta fila poderia trabalhar com um algoritmo escalonador do tipo fila (FIFO) e os processos seriam executados do início ao fim sem problemas (até porque não tem usuário requisitando a máquina).