Escalonamento Shortest Job Next

Escalonamento Shortest Job Next (SJN), também citado em algumas fontes de pesquisa como Shortest Job First (SJF) ou Shortest Process Next (SPN), o algoritmo seleciona o processo que tiver o menor tempo de execução que resta para executar.

Assim sendo, o processo que estiver no estado pronto e que necessitar de menor tempo de UCP, considerando um mesmo contexto, passa a possuir o estado de execução. Esta metodologia busca priorizar a uniformização do algoritmo de escalonamento Round-Robin, porém, considera o processo em estado de execução como não apropriativo.

A implementação desse paradigma de escalonamento foi utilizada com sistemas operacionais exclusivos para processamento em lote. A cada novo processo admitido pelo sistema, um tempo de execução era associado ao contexto do software.

Como não é possível determinar precisamente esse tempo de execução, uma estimativa era realizada considerando como base análises estatísticas de execuções passadas (heurística), podendo ser fornecidas pelo usuário ou incorporadas aos programas. Caso o tempo de execução informado fosse muito inferior ao tempo real, o sistema operacional poderia interromper a execução do processo.

O principal problema dessa solução é a impossibilidade de estimar o tempo de execução de processos interativos, já que a entrada de dados é uma ação imprevisível.

Em sua concepção inicial, o escalonamento SJN é um escalonamento não-preemptivo. Sua vantagem no escalonamento FCFS está na redução do tempo médio de turnaround1 dos processos, porém, no SJN é possível haver starvation2 para processos com tempo de processador muito longo, ou do tipo CPU-bound.

Neste modelo, os processos prontos ficam organizados em uma lista em ordem crescente, baseado no tempo de execução e o momento de chegada. Em suma, esse paradigma de escalonamento pode ser classificador por:

• Mão apropriativa;
• Privilegia os processos I/O-bound;
• Possui desempenho médio melhor se comparado ao paradigma FCFS;
• Possui uma desvantagem de implementação, já que necessita um algoritmo de heurística eficiente;
• É pouco previsível;
• Não é justo com processos longos.

Escalonamento Shortest Remaining Time

O algoritmo de escalonamento Shortest Remaining Time (SRT) ou Shortest Remaining First (SRF) é a variante preemptiva do escalonamento SJF. A fila de processos a serem executados pelo SRT é organizada conforme o tempo estimado de execução, ou seja, de forma semelhante ao SJN, sendo processados primeiro os menores jobs.

Na entrada de um novo processo, o algoritmo de escalonamento avalia seu tempo de execução incluindo o job em execução, caso a estimativa de seu tempo de execução seja menor que o processo corrente em execução, ocorre a substituição do processo em execução pelo processo recém chegado.

A função de seleção pode ser representada simplificadamente por:

• A cada mudança de contexto, o processo suspenso pela UCP deve ser recolocado em uma posição correspondente apenas ao seu tempo restante de execução e não mais o tempo de execução total;
• As sobrecargas impostas pela manutenção dos registros de tempos decorridos e pela troca de contexto da UCP acabam sendo justificado pelo fato de pequenos processos serem executados praticamente de imediato, minimizando o tempo médio de espera dentro de um cenário mais amplo e tornando-se útil para sistemas de tempo repartido.

Este algoritmo também se baseia nas estimativas de tempo de execução dos processos, possuindo as mesmas deficiências do algoritmo SJN, sendo necessário considerar:

• Processos com tempo de execução curtos são priorizados;
• Processos de maior duração tem seus tempos de espera variáveis em função de jobs menores que venham a ser executados primeiramente;
• Possibilidade potencial de processos grandes sendo adiados por um tempo indeterminado (starvation) devido ao excessivo favorecimento de processos de curta duração;
• Deve-se incluir um mecanismo extra para evitar que um processo, prestes a ser finalizado, sofre alguma preempção.