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

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 os cinco processos a seguir, 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.

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.

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

Passo 1) No tempo = 1, chega o Processo P3. Porém, P4 tem um tempo de burst mais curto. 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 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

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

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

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.

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

Passo 10) No tempo =23, P3 finaliza 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/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.