SJF

De Manuais Informática - IES San Clemente.
Ir a la navegación Ir a la búsqueda

SJF (Shortest Job First)

Este algoritmo chamado SJF (Shortest Job First) ten en conta a quenda de chegada sendo non expropiativo, así determina que o proceso a entrar na CPU de todos os posibles será aquel que teña menos duración de execución na mesma, isto é, entrará o proceso con menor ciclos de CPU a executar.

Imos ver un exemplo para explicar como traballa o algoritmo SJF:

  • Supoñemos a situación seguinte:
  • Tempo de chegada: P1-->0, P2-->5, P3-->4, P4-->2
  • Cola: P1, P4, P3, P2
  • Duración Proceso: P1-->4 ciclos de CPU, P2-->7 ciclos de CPU, P3-->4 ciclos de CPU. P4-->1 ciclo de CPU.

sendo,

te|Pi O tempo de espera do Proceso Pi
tr|Pi O tempo de retorno do Proceso Pi

Imos calcular o tempo medio de espera para este algoritmo, así como o Diagrama de Gantt correspondente,

SJF CPU.png

Como podemos ver na imaxe o primeiro en entrar na CPU é o proceso P1 pois na orde de chegada é o primeiro da cola de procesos. O algoritmo SJF determina que ao entrar un proceso esté ocupará a CPU ata que o mesmo remate, xa que o algoritmo é non expropiativo, así:
  1. Ciclo de CPU 1-Tempo de Chegada 0: Entra o proceso P1 na CPU e acapara os ciclos da mesma ata o remate da súa execución, co cal acapara a CPU 4 ciclos da mesma.
  2. Ciclo de CPU 3-Tempo de Chegada 2: Entra o proceso P4, mais como o algoritmo SJF é non expropiativo segue executándose o proceso P1 ata que remate a súa execución.
  3. Ciclo de CPU 5-Tempo de Chegada 4: A continuación entra o proceso P4, xa que o algoritmo SJF determina que o proceso a entrar na CPU sexa aquel que ocupe menos ciclos da mesma. Así o proceso P4 soamente ocuparía a CPU 1 ciclo a diferenza do P3 que ocuparía a CPU 4 ciclos da mesma. Entón entra P4 que acapararía 1 ciclo de CPU.
  4. Ciclo de CPU 6-Tempo de Chegada 5: Nesta situación temos 2 procesos en cola, o proceso P3 e o proceso P2, co cal o algoritmo SJF determina que o seguinte en entrar en cola é o que menos duración ocupe na CPU, entón entrará P3 ata que remate.
  5. Ciclo de CPU 10-Tempo de Chegada 9: Entra P2 ata que remate.

--ricardofc 24 nov 2008