O que é o Shortest Job First Scheduling?
Shortest Job First (SJF) é um algoritmo no qual o processo com o menor tempo de execução é escolhido para a próxima execução. Este método de agendamento pode ser preemptivo ou não preemptivo. Isso reduz significativamente o tempo médio de espera para outros processos aguardando execução. A forma completa de SJF é Shortest Job First.
Existem basicamente dois tipos de métodos SJF:
- SJF Não Preemptivo
- SJF preventivo
Neste tutorial de sistema operacional, você aprenderá:
- O que é o Shortest Job First Scheduling?
- Características do escalonamento SJF
- SJF Não Preemptivo
- SJF preventivo
- Vantagens do SJF
- Desvantagens / Contras de SJF
Características do escalonamento SJF
- Ele está associado a cada trabalho como uma unidade de tempo para ser concluído.
- Este método de algoritmo é útil para o processamento do tipo em lote, em que aguardar a conclusão dos trabalhos não é crítico.
- Ele pode melhorar a taxa de transferência do processo, certificando-se de que os trabalhos mais curtos sejam executados primeiro, portanto, possivelmente, têm um tempo de retorno curto.
- Ele melhora a produção do trabalho, oferecendo trabalhos mais curtos, que devem ser executados primeiro, que geralmente 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 processar, o processo o retém até que alcance um estado de espera ou seja 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.
Etapa 1) No tempo = 1, o processo P3 chega. Mas, P4 ainda precisa de 2 unidades de execução para ser concluído. Ele continuará a execução.
Etapa 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 encerrará sua execução. O tempo de burst de P3 e P1 é comparado. O processo P1 é executado porque seu tempo de burst é menor em relação ao P3.
Etapa 4) No tempo = 4, o processo P5 chega e é adicionado à fila de espera. P1 continuará a execução.
Etapa 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 encerrará sua execução. O tempo de burst de P3, P5 e P2 é comparado. O processo P2 é executado porque seu tempo de burst é o mais baixo.
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 encerrará 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 encerrará sua execução.
Passo 10) No tempo = 23, o processo P3 encerrará sua execução.
Etapa 11) Vamos calcular o tempo médio de espera para o exemplo acima.
Wait timeP4= 0-0=0P1= 3-2=1P2= 9-5=4P5= 11-4=7P3= 15-1=14
Average Waiting Time= 0+1+4+7+14/5 = 26/5 = 5.2
SJF preventivo
Na Programação SJF preemptiva, os trabalhos são colocados na fila de espera à medida que chegam. Um processo com o tempo de burst mais curto começa a execução. Se um processo com um tempo de burst ainda mais curto chegar, o processo atual será removido ou impedido de execução e o trabalho mais curto terá 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 |
Etapa 1) No tempo = 1, o processo P3 chega. Mas, P4 tem um tempo de burst mais curto. Ele continuará a execução.
Etapa 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 encerrará sua execução. O tempo de burst de P3 e P1 é comparado. O processo P1 é executado porque seu tempo de burst é menor.
Etapa 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 é o mais baixo. O processo P1 é interrompido.
| Fila de Processo | Tempo de explosão | Tempo de chegada |
| P1 | 5 de 6 são restantes | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 4 | 4 |
Etapa 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 é mínimo. O processo P5 é interrompido.
| Fila de Processo | Tempo de explosão | Tempo de chegada |
| P1 | 5 de 6 são restantes | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 de 4 estão restantes | 4 |
Etapa 6) No tempo = 6, P2 está em execução.
Passo 7) No tempo = 7, P2 termina 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 são restantes | 2 |
| P2 | 2 | 5 |
| P3 | 8 | 1 |
| P4 | 3 | 0 |
| P5 | 3 de 4 estão restantes | 4 |
Passo 8) No tempo = 10, P5 encerrará 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.
Etapa 11) Vamos calcular o tempo médio de espera para o exemplo acima.
Wait timeP4= 0-0=0P1= (3-2) + 6 =7P2= 5-5 = 0P5= 4-4+2 =2P3= 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 no 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 os trabalhos executados em lote, onde os tempos de execução são conhecidos com antecedência.
- Para o sistema de lote de programação de longo prazo, uma estimativa de tempo de burst pode ser obtida a partir da descrição do trabalho.
- Para o agendamento de curto prazo, precisamos prever o valor do próximo tempo de burst.
- Provavelmente ideal em relação ao tempo médio de resposta.
Desvantagens / Contras de 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 prever.
- Geralmente é usado em um sistema em lote para programação de longo prazo.
- SJF não pode ser implementado para escalonamento de CPU para o curto prazo. É porque não existe um método específico para prever a duração do surto de CPU que está por vir.
- Este algoritmo pode causar tempos de resposta muito longos ou fome.
- 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 o 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 o processamento do tipo em lote, em que aguardar a conclusão dos trabalhos não é crítico.
- Existem basicamente dois tipos de métodos de SJF 1) SJF Não Preemptivo e 2) SJF Preemptivo.
- No escalonamento não preemptivo, uma vez que o ciclo da CPU é alocado para processar, o processo o retém até que alcance um estado de espera ou seja encerrado.
- Na Programação SJF preemptiva, os trabalhos são colocados na fila de espera à medida que chegam.
- Embora um processo com tempo de burst curto comece, o processo atual é removido ou impedido de execução, e o trabalho que é mais curto é executado primeiro.
- SJF é freqüentemente usado para agendamento de longo prazo.
- Reduz o tempo médio de espera no 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 prever.
- SJF não pode ser implementado para escalonamento de CPU para o curto prazo. É porque não existe um método específico para prever a duração do surto de CPU que está por vir.