Otro metodo de planificacion de la CPU es el algoritmo de planificacion con seleccion del trabajo mas corto (SJF, shortest job-first). Este algoritmo asocia con cada proceso la duracion de la siguiente rafaga de CPU del proceso. Cuando la CPU esta disponible, se asigna al proceso que tiene la siguiente rafaga de CPU mas corta. Si las siguientes rafagas de CPU de dos procesos son iguales, se usa la planificacion FCFS para romper el empate. Observe que un termino mas apropiado para este metodo de planificacion seria el de algoritmo de la siguiente rafaga de CPU mas corta, ya que la planificacion depende de la duracion de la siguiente rafaga de CPU de un proceso, en lugar de depender de su duracion total. Usamos el termino SJF porque casi todo el mundo y gran parte de los libros de texto emplean este termino para referirse a este tipo de planificacion.

Como ejemplo de planificacion SJF, considere el siguiente conjunto de procesos, estando especificada la duracion de la rafaga de CPU en milisegundos:

Proceso         Tiempo de rafaga
P1                             6
P2                             8
P3                             7
P4                             3

Usando la planificacion SJF, planificariamos estos procesos de acuerdo con el siguiente diagrama de Gantt:

El tiempo de espera es de 3 milisegundos para el proceso P1, de 16 milisegundos para el proceso P2, de 9 milisegundos para P3 y de 0 milisegundos para P4. Por tanto, el tiempo medio de espera es de (3 + 16 + 9 + 0)/4 = 7 milisegundos. Por comparacion, si estuvieramos usando el esquema de planificacion FCFS, el tiempo medio de espera seria de 10,25 milisegundos.

El algoritmo de planificacion SJF es probablemente optimo, en el sentido de que proporciona el tiempo medio de espera minimo para un conjunto de procesos dado. Anteponer un proceso corto a uno largo disminuye el tiempo de espera del proceso corto en mayor medida de lo que incrementa el tiempo de espera del proceso largo. Consecuentemente, el tiempo medio de espera disminuye.

La dificultad real del algoritmo SJF es conocer la duracion de la siguiente solicitud de CPU. En una planificacion a largo plazo de trabajos en un sistema de procesamiento por lotes, podemos usar como duracion el limite de tiempo del proceso que el usuario especifique en el momento de enviar el trabajo. Con este mecanismo, los usuarios estan motivados para estimar el limite de tiempo del proceso de forma precisa, dado que un valor menor puede significar una respuesta mas rapida. (Un valor demasiado bajo producira un error de limite de tiempo excedido y sera necesario reenviar el proceso.) La planificacion SJF se usa frecuentemente como mecanismo de planificacion a largo plazo.

Aunque el algoritmo SJF es optimo, no se puede implementar en el nivel de la planificacion de la CPU a corto plazo, ya que no hay forma de conocer la duracion de la siguiente rafaga de CPU. Un metodo consiste en intentar aproximar la planificacion SJF: podemos no conocer la duracion de la siguiente rafaga de CPU, pero podemos predecir su valor, por el procedimiento de confiar en que la siguiente rafaga de CPU sera similar en duracion a las anteriores. De este modo, calculando una aproximacion de la duracion de la siguiente rafaga de CPU, podemos tomar el proceso que tenga la rafaga de CPU predicha mas corta.

Generalmente, la siguiente rafaga de CPU se predice como la media exponencial de las duraciones medidas de las anteriores rafagas de CPU. Sea tn la duracion de la n-esima rafaga de CPU y sea Tn+l el valor predicho para la siguiente rafaga de CPU. Entonces, para a, 0? α ? 1, se define

tn+1 = α tn + (1 - α) tn

Esta formula define un promedio exponencial. El valor de tn contiene la informacion mas reciente; tn almacena el historial pasado. El parametro a controla el peso relativo del historial reciente y pasado de nuestra prediccion. Si α = 0, entonces tn1 = tn’, y el historial reciente no tiene ningun efecto (se supone que las condiciones actuales van a ser transitorias); si α = 1, entonces tn+1 = tn’ y solo la rafaga de CPU mas reciente importa (se supone que el historial es obsoleto y, por tanto, irrelevante). Frecuentemente, α = 1/2, en cuyo caso, el historial reciente y pasado tienen el mis peso. El valor inicial t0 puede definirse como una constante o como un promedio global para todo el sistema. La Figura 5.3 muestra un promedio exponencial con α = 1/2 y t0 = 10.

Para comprender el comportamiento del promedio exponencial, podemos desarrollar la formula para tn+l sustituyendo el valor de tn y de los terminos sucesivos, obteniendo

Tn+1 = αtn+(1-a)atn-1 +???+(1- α)j αtn-j +???+(1-(X)n+1t0

Dado que tanto a como 1-a son menores o iguales a 1, cada termino sucesivo tiene menor peso que su predecesor.

El algoritmo SJF puede ser cooperativo o apropiativo. La necesidad de elegir surge cuando un proceso llega a la cola de procesos preparados mientras que un proceso anterior esta todavia en ejecucion. La siguiente rafaga de CPU del proceso que acaba de llegar puede ser mas corta que lo que quede del proceso actualmente en ejecucion. Un algoritmo SJF apropiativo detendra el proceso actualmente en ejecucion, mientras que un algoritmo sin desalojo permitira que dicho proceso termine su rafaga de CPU. La planificacion SJF apropiativa a veces se denomina planificacion con seleccion del proceso con tiempo restante mas corto.

Como ejemplo, considere los cuatro procesos siguientes, estando especificada la duracion de la rafaga de CPU en milisegundos:

Proceso         Tiempo de llegada         Tiempo de rafaga
P1                            0                                 8
P2                            1                                 4
P3                            2                                 9
P4                            3                                 5

Si los procesos llegan a la cola de procesos preparados en los instantes que se muestran y necesitan los tiempos de rafaga indicados, entonces la planificacion SJF apropiativa es la que se muestra en el siguiente diagrama de Gantt:

El proceso Pl se inicia en el instante 0, dado que es el unico proceso que hay en la cola. El proceso P2llega en el instante 1. El tiempo que le queda al proceso P1 (7 milisegundos) es mayor que el tiempo requerido por el proceso P2 (4 milisegundos), por lo que el proceso Pl se desaloja y se planifica el proceso P2. El tiempo medio de espera en este ejemplo es de ((10 - 1) + (1- 1) + (17 - 2) + (5 - 3) )/4 = 26/4 = 6,5 milisegundos. La planificacion SJF cooperativa proporcionaria un tiempo medio de espera de 7,75 milisegundos.