ALGORITMOS DE PLANIFICACION

DAVID ESTEBAN RODRIGUEZ GOMEZ

SJF (Shortest Job First)

Concepto:

Disciplina no apropiativa y no recomendable en ámbitos de tiempo compartido, el proceso espera con el menor tiempo de ejecución hasta su terminando permitiendo que el siguiente se ejecute.

• Los tiempos de espera son menos predecibles que en “FIFO”.

• Favorece a los procesos cortos en detrimento de

los largos. • Tiende a reducir el número de procesos en espera

y el número de procesos que esperan detrás de procesos largos.

• Requiere un conocimiento preciso del tiempo de

ejecución de un proceso, lo que generalmente se desconoce.

• Se pueden estimar los tiempos en base a series

de valores anteriores.

Características

Funciones

• Asocia a cada proceso tiempo aproximado de la utilización del CPU

• Asigna la CPU al proceso con menor tiempo asociado

• Cuando un proceso consigue la CPU, la conserva hasta que desea liberarla

Problemáticas

Estimación del tiempo de utilización del CPU por parte de un proceso

EjemploPara el siguiente ejemplo se tienen 4 procesos (P1, P2,P3 y P4). A medida que estos se van incorporando a la cola de listos, se les calcula su próximo ciclo de CPU.Para calcular el próximo ciclo de CPU se pueden emplear: métodos estadísticos, cálculos probabilísticos, entre otros.

EjemploEn el ejemplo se toma como criterio que la cola de procesos listos está inicialmente vacía. En la figura se representa la llegada de P1 a la cola de listos con un tiempo de llegada (0,0). Luego a P1 se le calcula su CCPU (CCPU = 7) y en ese instante se comienza a ejecutar.

Estando en ejecución el proceso P1, se incorpora a la cola de listos P2, al cual se le calcula su CCPU (CCPU = 4).Pero como el CCPU de P2 es menor que el CCPU de P1, entonces P1 es desalojado y P2 toma la CPU. En este caso P1 se reincorpora a la cola de listos porque no ha terminado su ejecución, y en ese instante se le vuelve a calcular el valor del CCPU (CCPU = 6).

Ejemplo

Luego llega el proceso P3 a la cola de listos y se le calcula el CCPU (CCPU = 1). Por lo que sucede igual que el caso anterior, el CCPU de P3 es menor que el CCPU de P2, por lo que se desaloja P2 para cederle la CPU a P3. P2 es reincorporado a la cola de listos porque no ha terminado su ejecución CCPU y se le vuelve a calcular su CCPU (CCPU = 3).

Ejemplo

El proceso P4 se incorpora a la cola de listos y se le calcula su CCPU (CCPU = 4). Luego P3 termina su ejecución para cederle la CPU al próximo proceso que le corresponda según el criterio que establece el algoritmo. Para el ejemplo le corresponde el turno a P2, luego a P4 y finalmente a P1.

Ejemplo

¿Algoritmo Óptimo?

El SJF se considera como un algoritmo óptimo, porque da el mínimo tiempo de espera promedio para un conjunto de procesos, así como las estimaciones de CPU. Su dificultad radica en que materialmente es un algoritmo imposible de implementar .

SRTF (Shortest Remaining Time

First)Concepto:

Da prioridad al proceso que le resta menor tiempo de CPU para terminar, es una variante del SJF pero con expulsión, optimiza la media del tiempo de espera y rendimiento.

Características

Es la contraparte apropiativa del SJF.

Es útil en sistemas de tiempo compartido.

El proceso con el tiempo estimado de ejecución menor para finalizar es el siguiente en ser ejecutado. Un proceso en ejecución puede ser apropiado por un nuevo proceso con un tiempo estimado de ejecución menor.

Tiene mayor sobrecarga que la planificación SJF.

Debe mantener un registro del tiempo de servicio transcurrido del proceso en ejecución, lo que aumenta la sobrecarga. Los trabajos largos tienen un promedio y una varianza de los tiempos de espera aún mayor que en SJF.

La apropiación de un proceso a punto de terminar por otro de menor duración recién llegado podría significar un mayor tiempo de cambio de contexto (administración del procesador) que el tiempo de finalización del primero.

Funciones

• Los procesos llega a la cola y solicitan intervalo de CPU

• Si el intervalo es inferior al que falta al proceso en ejecución para abandonar la CPU, el nuevo proceso pasa a la CPU y el que se ejecutaba a la cola de preparados.

Problemáticas

• El intervalo es difícil de predecir

• Posibilidad de inanición: los trabajos no se ejecutaran mientras hayan trabajos cortos

Ejemplo

Si un nuevo proceso pasa a listo se activa el dispatcher para ver si es más corto que lo que queda por ejecutar del proceso en ejecución. Si es así el proceso en ejecución pasa a listo y su tiempo de estimación se decrementa con el tiempo que ha estado ejecutándose. En la figura 6.5 tenemos un ejemplo de funcionamiento del algoritmo en el que se observa cómo se penalizan las ráfagas largas (como en SJF). Un punto débil de este algoritmo se evidencia cuando una ráfaga muy corta suspende a otra un poco más larga, siendo más largo la ejecución en este orden al ser preciso un cambio adicional de proceso y la ejecución del código del planificador.

Ejemplo

Ejemplos ambas planificaciones

Para que puedan observar el ejemplo por favor ingresen a esta dirección

http://www.youtube.com/watch?v=-vxbZUi78yI

GRACIAS POR SU ATENCIÓN