SJR Sistemas Operativos

Administracion de Procesos y El Procesador

2.6.2 SJR

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:

P4 P1 P3 P2

0 3 9 16 24

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

...