Interrupciones

Sistemas Operativos

Procesos

Algoritmos de Planificación


Ing. Alfredo Jiménez Barragán
Departamento de Ciencias Computacionales
Universidad de Guadalajara

Octubre de 2004
Corrección 1.2


Algoritmos de Planificación

La planificación de la CPU tiene que ver con el problema de decidir a cuál de los procesos en la cola de listos se le asignará la CPU.

Planificación delprimero en llegar, primero en ser atendido

 El algoritmo más sencillo
 También es llamado FCFS (“first come, first server”).
 La CPU se asigna al primer proceso que la solicite.

Se maneja por medio de una cola de tipo FIFO, cuando un proceso entra a la fila de los listos, su PCB se enlaza al final de la cola.

Cuando el CPU esta libre, se asigna al proceso que se encuentra a lacabeza de la fila; el proceso que esta en ejecución se remueve entonces de dicha cola.

 El código es fácil de escribir y entender.
 Sin embargo, el tiempo de espera promedio con esta política es bastante largo.

Considere el siguiente conjunto de procesos que llegan en el instante 0, con el tiempo de ráfaga de la CPU en milisegundos:

Proceso Tiempo de Ráfaga
P1 24
P2 3
P3 3

Sí losprocesos llegan en el orden de P1, P2 y P3 y se atienden bajo la orden FCFS, obtenemos el resultando mostrado en la siguiente gráfica de Gantt:

P1 P2 P3
0 24 27 30

El tiempo de espera es de 0 milisegundos para el proceso P1, 24 milisegundos para el proceso P2, y 27 milisegundos para el proceso P3. Se esta forma, el tiempo de espera promedio es (0 +24 + 27)/3 = 17 milisegundos.

Sin embargo, si los procesos llegan en el orden de P2, P3 y P1, los resultados serán como se muestra a continuación:

P2 P3 P1
0 3 6 30

El tiempo de espera promedio es ahora (6 + 0 + 3)/3 = 3 milisegundos

 Es una reducción significativa
 Variadependiendo el orden de llegada de las tareas
 Es NO APROPIATIVO
 Es conflictivo para algunos sistemas de tiempo compartido

Planificación de primero el trabajo + corto

 Se le llama SJF (Shortest – Job – First)
 Este algoritmo asocia a cada proceso la longitud de su siguiente ráfaga de CPU.
 Cuando la CPU esta disponible, se le asigna al proceso que tiene la siguiente ráfaga + pequeñade CPU. Si 2 procesos tienen la misma longitud, se emplea FIFO para tomar la decisión.
 Ojo: No es tanto por longitud.

Considere el siguiente conjunto de procesos con el tiempo de ráfaga de la CPU dado en milisegundos:

Proceso Tiempo de Ráfaga
P1 6
P2 8
P3 7
P4 3

Empleando la planificación SJF, planificaríamos estos procesos de acuerdo con la siguiente gráfica:

P4 P1 P3 P20 3 9 16 24

El tiempo de espera promedio es (3 + 16 + 9 + 0)/4 = 7 milisegundos.

Si utilizáramos FIFO ese tiempo sería de 10.25 milisegundos.

 SJF es óptimo, ya que da el mínimo tiempo de espera promedio para un conjunto dado de procesos.
 Ladificultad real es conocer la longitud de la siguiente solicitud de la CPU.
 Se emplea muy frecuentemente en la planificación a largo plazo. Allí se presenta el tiempo de procesamiento que especifica el usuario.
 No se puede implementar a corto plazo, pues no hay forma de conocer la longitud de la sig. ráfaga.

A corto plazo, no es posible saber ese valor, pero se puede predecircalculando un aproximado.

Este algoritmo puede ser APROPIATIVO y NO APROPIATIVO. La elección surge cuando llega un nuevo proceso a la cola de listos mientras un proceso previo se está ejecutando. El nuevo proceso puede tener una ráfaga siguiente de CPU más corta que lo que resta del proceso que en la actualidad se esta ejecutando.

Un SJF APROPIATIVO suspenderá al proceso que actualmente está en...