2.6 Técnica de administración del planificador

FIFO

Algoritmo de planificación de FIFO
Tal vez la disciplina mas simple de planificación sea la de primeras entradas ? primeras salidas (PEPS). Los procesos se despachan de acuerdo con su tiempo de llegada a la cola de procesos listos. Cuando un proceso tiene la CPU, se ejecuta hasta terminar. Es junto en el sentido formal, pero algo injusta en cuanto a que los trabajos largos hacen esperar a los cortos y los trabajos sin importancia hacen esperar a los importantes. FIFO ofrece variaciones relativamente pequeñas en los tiempos de respuesta y por lo tanto es mas predecible que los otros esquemas. No es útil en la planificación para los usuarios interactivos porque no puede garantizar buenos tiempos de respuesta.

El esquema FIFO rara vez se usa como esquema principal en los sistemas actuales, pero a menudo esta incorporado en otros sistemas. Por ejemplo, muchos esquemas de planificación despachan los procesos de acuerdo con la prioridad, pero los procesos con la misma prioridad se despachan de acuerdo con el esquema FIFO.
Este es un algoritmo que no usa apropiación, y que consiste en atender a los procesos por estricto orden de llegada a la lista de procesos listos. Cada proceso se ejecuta hasta que termina, o hasta que hace una llamada bloqueante (de E/S). Se trata de una política muy simple y sencilla de llevar a la practica, pero muy pobre en cuanto a su comportamiento.

Las características principales de este algoritmo son las siguientes:

• No es apropiativa.
• Es justa, aunque los procesos largos hacen esperar mucho a los cortos.
• Es una política predecible.
• El tiempo promedio de servicio es muy variable ya que esta en función del numero de procesos y la duración promedio que tenga.

EJEMPLO

Proceso		Tiempo de UCP
P1 P2 P3	24 3 3

Media del tiempo de espera:

Caso 1) ( 0 + 24 + 27 ) / 3 =17
Caso 2) ( 6 + 0 + 3 ) / 3 = 3
En este esquema se tienen tres procesos (P1, P2, P3) listos para ejecutarse, con un tiempo de ejecución de 24, 3 y 3 unidades de tiempo (para facilidad tomaremos milisegundos como unidad de tiempo) respectivamente. Los procesos se ejecutan en ese mismo orden. El primer proceso se ejecuta de inmediato y no espera nada.

El segundo proceso espera todo lo que dura en ejecutarse el primer proceso que son 24 milisegundos. Por ultimo el tercer proceso esperara la suma de lo que duran en ejecutarse los dos procesos anteriores, o sea, 27 segundos. Todo esto da como resultado un tiempo promedio de espera de 17 milisegundos. Si en cambio, el orden en que se ejecuten los procesos es como el caso 2), entonces el proceso P2 se ejecutaría de inmediato, P3 esperaría lo que tarde en ejecutarse P2 (3 milisegundos) y P1 esperaría lo que duran los dos procesos anteriores, obteniendo un tiempo promedio de espera de 3 milisegundos.

Como puede verse el tiempo promedio de espera que tengan los procesos depende por completo del orden en que llegan los procesos a ejecutarse.

SJF

Otro método de planificación de la CPU es el algoritmo de planificación con  selección del trabajo mas corto (SJF, shortest job-first). Este algoritmo asocia  con cada proceso la duración de la siguiente ráfaga de CPU del proceso.  Cuando la CPU esta disponible, se asigna al proceso que tiene la siguiente  ráfaga de CPU mas corta. Si las siguientes ráfagas de CPU de dos procesos  son iguales, se usa la planificación FCFS para romper el empate. Observe  que un termino mas apropiado para este método de planificación seria el  de algoritmo de la siguiente ráfaga de CPU mas corta, ya que la planificación  depende de la duración de la siguiente ráfaga de CPU de un proceso,  en lugar de depender de su duración 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 planificación.