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.
  • Ele pode melhorar o rendimento do processo, garantindo que trabalhos mais curtos sejam executados primeiro e, portanto, possivelmente tenham um tempo de resposta curto.
  • Melhora a produção do trabalho, oferecendo trabalhos mais curtos, que devem ser executados 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 para o processo, o processo o retém até atingir um estado de espera ou ser encerrado.

Considere o seguintewing cinco processos, cada um com seu próprio tempo de burst e tempo de chegada exclusivos.

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 tempo=0, P4 chega e inicia a execução.

SJF não preemptivo

Passo 1) No tempo = 1, chega o Processo P3. Porém, P4 ainda precisa de 2 unidades de execução para ser concluído. Ele continuará a execução.

SJF não preemptivo

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

SJF não preemptivo

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.

SJF não preemptivo

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

SJF não preemptivo

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

SJF não preemptivo

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.

SJF não preemptivo

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

SJF não preemptivo

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.

SJF não preemptivo

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

SJF não preemptivo

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

SJF não preemptivo

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 agendamento SJF preemptivo, os trabalhos são colocados na fila de espera à medida que chegam. Um processo com menor tempo de burst inicia a execução. Se um processo com um tempo de intermitência ainda mais curto chegar, o processo atual será removido ou a execução será interrompida e o trabalho mais curto receberá um ciclo de CPU alocado.

Considere o seguintewing cinco processos:

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 tempo=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

SJF preventivo

Passo 1) No tempo = 1, chega o Processo P3. Porém, P4 tem um tempo de burst mais curto. Ele continuará a execução.

SJF preventivo

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.

SJF preventivo

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.

SJF preventivo

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

SJF preventivo

Passo 5) No tempo = 5, o processo P2 chegará. O tempo de burst de P1, P2, P3 e P5 é comparado. O processo P2 é executado porque seu tempo de burst é menor. O processo P5 é 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 3 de 4 restantes 4

SJF preventivo

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

SJF preventivo

Passo 7) No tempo =7, P2 finaliza sua execução. O tempo de burst de P1, P3 e P5 é comparado. O processo P5 é executado porque seu tempo de burst é 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

SJF preventivo

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

SJF preventivo

Passo 9) No tempo =15, P1 finaliza sua execução. P3 é o único processo restante. Ele iniciará a execução.

SJF preventivo

Passo 10) No tempo =23, P3 finaliza sua execução.

SJF preventivo

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/prós de usar o método SJF:

  • SJF é freqüentemente usado para agendamento de longo prazo.
  • Reduz o tempo médio de espera pelo algoritmo FIFO (First in First Out).
  • O método SJF fornece 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 ideal em relação ao 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.
  • 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 à fome 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 mais sobrecarga no processador.

Resumo

  • SJF é um algoritmo no qual o processo com menor tempo de execução é escolhido para a próxima execução.
  • O agendamento SJF está associado a cada trabalho como uma unidade de tempo para conclusão.
  • Este método de algoritmo é útil para processamento em lote, onde a espera pela conclusão dos trabalhos não é crítica.
  • Existem basicamente dois tipos de métodos SJF 1) SJF não preemptivo e 2) SJF preemptivo.
  • No escalonamento não preemptivo, uma vez que o ciclo da CPU é alocado para o processo, o processo o retém até atingir um estado de espera ou ser encerrado.
  • No agendamento SJF preemptivo, os trabalhos são colocados na fila de espera à medida que chegam.
  • Embora um processo com tempo de intermitência curto comece, o processo atual é removido ou impedido de execução e o trabalho mais curto é executado primeiro.
  • SJF é freqüentemente usado para agendamento de longo prazo.
  • Reduz o tempo médio de espera pelo algoritmo FIFO (First in First Out).
  • No agendamento SJF, o tempo de conclusão do trabalho deve ser conhecido com antecedência, mas é difícil de prever.
  • SJF não pode ser implementado para agendamento de CPU no curto prazo. Isso ocorre porque não existe um método específico para prever a duração do próximo burst de CPU.