Shortest Job First (SJF): Exemplo Preemptivo e Não Preemptivo

O que é o agendamento mais curto do primeiro trabalho?

Trabalho mais curto primeiro (SJF) é um algoritmo no qual o processo com menor tempo de execução é escolhido para a próxima execução. Este método de agendamento pode ser preemptivo ou não preemptivo. Reduz significativamente o tempo médio de espera de outros processos que aguardam execução. O formulário completo do SJF é Shortest Job First.

Existem basicamente dois tipos de métodos SJF:

• SJF não preemptivo
• SJF preventivo

Características do agendamento SJF

• Está associado a cada trabalho como uma unidade de tempo para ser concluído.
• Este método de algoritmo é útil para processamento em lote, onde a espera pela conclusão dos trabalhos não é crítica.
• Isso pode melhorar a produtividade do processo, garantindo que as tarefas mais curtas sejam executadas primeiro, resultando possivelmente em um tempo de resposta mais curto.
• Isso melhora a produtividade ao oferecer tarefas mais curtas, que devem ser executadas primeiro e que, em sua maioria, têm um tempo de resposta mais curto.

SJF não preemptivo

No escalonamento não preemptivo, uma vez que o ciclo da CPU é alocado a um processo, o processo o mantém até atingir um estado de espera ou ser encerrado.

Considere os cinco processos a seguir, cada um com seu próprio tempo de execução e tempo de chegada únicos.

Fila de Processo	Tempo de explosão	Tempo de chegada
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Passo 0) No instante t = 0, P4 chega e inicia a execução.

Passo 1) No instante t = 1, o processo P3 chega. Mas P4 ainda precisa de 2 unidades de execução para ser concluído. Ele continuará a execução.

Passo 2) No tempo = 2, o processo P1 chega e é adicionado à fila de espera. P4 continuará a execução.

Passo 3) No tempo = 3, o processo P4 finalizará sua execução. O tempo de burst de P3 e P1 é comparado. O processo P1 é executado porque seu tempo de burst é menor comparado ao P3.

Passo 4) No tempo = 4, o processo P5 chega e é adicionado à fila de espera. P1 continuará a execução.

Passo 5) No tempo = 5, o processo P2 chega e é adicionado à fila de espera. P1 continuará a execução.

Passo 6) No tempo = 9, o processo P1 finalizará sua execução. O tempo de burst de P3, P5 e P2 é comparado. O processo P2 é executado porque seu tempo de burst é o menor.

Passo 7) No instante t = 10, P2 está em execução e P3 e P5 estão na fila de espera.

Passo 8) No tempo = 11, o processo P2 finalizará sua execução. O tempo de burst de P3 e P5 é comparado. O processo P5 é executado porque seu tempo de burst é menor.

Passo 9) No tempo = 15, o processo P5 finalizará sua execução.

Passo 10) No tempo = 23, o processo P3 finalizará sua execução.

Passo 11) Vamos calcular o tempo médio de espera para o exemplo acima.

Wait time
P4 = 0 - 0 = 0
P1 = 3 - 2 = 1
P2 = 9 - 5 = 4
P5 = 11 - 4 = 7
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 1 + 4 + 7 + 14)/5 = 26/5 = 5.2

SJF preventivo

No escalonamento SJF preemptivo, as tarefas são colocadas na fila de prontos à medida que chegam. O processo com o menor tempo de execução inicia sua execução. Se um processo com um tempo de execução ainda menor chegar, o processo atual é removido ou preemptado da execução, e o ciclo de CPU é alocado à tarefa mais curta.

Considere os cinco processos a seguir:

Fila de Processo	Tempo de explosão	Tempo de chegada
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Passo 0) No instante t = 0, P4 chega e inicia a execução.

Fila de Processo	Tempo de explosão	Tempo de chegada
P1	6	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Passo 1) No instante t = 1, o processo P3 chega. Mas P4 tem um tempo de execução menor. Ele continuará a execução.

Passo 2) No tempo = 2, o processo P1 chega com tempo de burst = 6. O tempo de burst é maior que o de P4. Portanto, P4 continuará a execução.

Passo 3) No tempo = 3, o processo P4 finalizará sua execução. O tempo de burst de P3 e P1 é comparado. O processo P1 é executado porque seu tempo de burst é menor.

Passo 4) No tempo = 4, o processo P5 chegará. O tempo de burst de P3, P5 e P1 é comparado. O processo P5 é executado porque seu tempo de burst é menor. O processo P1 é interrompido.

Fila de Processo	Tempo de explosão	Tempo de chegada
P1	5 de 6 restantes	2
P2	2	5
P3	8	1
P4	3	0
P5	4	4

Passo 5) No instante t = 5, o processo P2 chegará. O tempo de execução (burst time) de P1, P2, P3 e P5 é comparado. O processo P2 é executado porque seu tempo de execução é o menor. O processo P5 é preemptado.

Fila de Processo	Tempo de explosão	Tempo de chegada
P1	5 de 6 restantes	2
P2	2	5
P3	8	1
P4	3	0
P5	3 de 4 restantes	4

Passo 6) No instante t = 6, P2 está em execução.

Passo 7) No instante t = 7, o processo P2 termina sua execução. O tempo de execução (burst time) dos processos P1, P3 e P5 é comparado. O processo P5 é executado porque seu tempo de execução é menor.

Fila de Processo	Tempo de explosão	Tempo de chegada
P1	5 de 6 restantes	2
P2	2	5
P3	8	1
P4	3	0
P5	3 de 4 restantes	4

Passo 8) No instante t = 10, o processo P5 terminará sua execução. O tempo de execução de P1 e P3 é comparado. O processo P1 é executado porque seu tempo de execução é menor.

Passo 9) No instante t = 15, P1 termina sua execução. P3 é o único processo restante. Ele iniciará sua execução.

Passo 10) No instante t = 23, P3 termina sua execução.

Passo 11) Vamos calcular o tempo médio de espera para o exemplo acima.

Wait time
P4 = 0 - 0 = 0
P1 = (3 - 2) + 6 = 7
P2 = 5 - 5 = 0
P5 = 4 - 4 + 2 = 2
P3 = 15 - 1 = 14

Average Waiting Time = (0 + 7 + 0 + 2 + 14)/5 = 23/5 = 4.6

Vantagens do SJF

Aqui estão os benefícios/vantagens de usar o método SJF:

• SJF é freqüentemente usado para agendamento de longo prazo.
• Isso reduz o tempo médio de espera em comparação com o algoritmo FIFO (First In First Out).
• O método SJF proporciona o menor tempo médio de espera para um conjunto específico de processos.
• É apropriado para trabalhos executados em lote, onde os tempos de execução são conhecidos antecipadamente.
• Para o sistema em lote de agendamento de longo prazo, uma estimativa do tempo de rajada pode ser obtida na descrição do trabalho.
• Para escalonamento de curto prazo, precisamos prever o valor do próximo tempo de rajada.
• Provavelmente é a opção ideal em termos de tempo médio de resposta.

Desvantagens/Contras do SJF

Aqui estão algumas desvantagens/contras do algoritmo SJF:

• O tempo de conclusão do trabalho deve ser conhecido com antecedência, mas é difícil de prever.
• É frequentemente usado em um sistema em lote para agendamento de longo prazo.
• O SJF não pode ser implementado para agendamento de CPU para o curto prazo. Isso ocorre porque não existe um método específico para prever a duração do próximo burst de CPU.
• Este algoritmo pode causar tempos de resposta muito longos ou inanição.
• Requer conhecimento de quanto tempo um processo ou trabalho será executado.
• Isso leva à inanição, o que não reduz o tempo médio de resposta.
• É difícil saber a duração da próxima solicitação de CPU.
• O tempo decorrido deve ser registrado, o que resulta em maior sobrecarga para o processador.

Perguntas Frequentes