ALGORITMOS DE PLANIFICACION DE PROCESOS

Planificación Monoprocesador

La clave para la multiprogramación es la planificación. El propósito de la planificación es asignarle procesos al procesador para ser ejecutados, de manera tal que se cumplan los objetivos del sistema, mientras los otros procesos esperan algún evento

La planificación del procesador se clasifica según la escala relativa de tiempo en que es realizada.

Tipos de Planificación del Procesador

1. Corto Plazo


2. Medio Plazo


3. Largo Plazo
   

Largo Plazo

Determina qué nuevos programas son aceptados para ser procesados por el sistema, o sea determina el grado de multiprogramación. Una vez admitidos, se convierten en procesos que son agregados a la cola de Planificación a Corto Plazo. En algunos sistemas, son agregados a la cola de Planificación a Mediano Plazo, ya que los procesos creados recientemente comienzan en una condición de suspendidos. Relativamente, se ejecuta en forma poco frecuente.

•Determina que programas son admitidos al sistema para su procesamiento.

•Controla el grado de multiprogramación.

•Mucho procesos, cada proceso es ejecutado en pequeños porcentajes de tiempo.

Medio Plazo

Determina el intercambio con la memoria virtual. Generalmente, la decisión de activar procesos está basada en la necesidad de manejar el grado de multiprogramación. Se ejecuta un poco más frecuente que la planificación a largo plazo.

•Parte de la función de intercambio (swaping).

•Basado en la necesidad de administrar el grado de multi-programación.

Corto Plazo

Determina cuál es el próximo proceso a ejecutar. Es invocada cada vez que ocurre un evento que pueda causar una suspensión (interrupciones del reloj, interrupciones de entrada / salida, llamados al sistema operativo, señales) o que pueda asegurarle una mayor prioridad a un proceso actualmente ejecutando a favor de otro. También conocida como despachador, es la que se ejecuta más frecuente.

•Conocido como el despachador.

•Se ejecuta muy frecuentemente.

•Se invoca cuando ocurre alguno de los siguientes eventos:

–Interrupción de reloj

–Interrupción de E/S

–Llamadas al SO

–Señales

Criterios de planificación a corto plazo orientado al usuario

• Tiempo de respuesta (TS) Inicio = Primera respuesta


• Tiempo de retorno (TR) Inicio = Fin


• Tiempo ponderado retorno (TPR = TR/TC)

• Plazos => Maximizar el numero de plazos cumplidos


• Previsibilidad => El mismo trabajo, en tiempos parecidos

Para comparar los planificadores su esa el tiempo de cada promedio.

Criterios de planificación a corto plazo orientado al sistema

• Efectividad = Numero de procesos terminados.


• Eficiencia = Porcentaje utilizado por el procesador.


• Prioridad = Si es que se usa favoreces a la mayor prioridad.


• Equilibrio = Mantener ocupados a los recursos, evitar la sobrecarga y la subcarga.

Políticas de Planificación

Hay dos aspectos importantes a contemplar en las diferentes políticas de planificación: la función de selección y el modo de decisión. La función de selección determina qué proceso, entre los procesos listos, es seleccionado para ejecutarse a continuación; puede estar basada en prioridad, en los requerimientos de los recursos, o en las características de ejecución del proceso.

El modo de decisión especifica los instantes en el tiempo en los cuales la función de selección es aplicada; y puede ser Sin Preferencia o Con Preferencia. Si es Sin Preferencia, un proceso que esté en el estado de Ejecutando, continuará haciéndolo hasta que se termine o que se bloquee esperando por una E/S o para responder un servicio del sistema operativo. En cambio, si es Con Preferencia, el proceso que se está ejecutando actualmente puede ser interrumpido y movido al estado de Listo por el sistema operativo.

1. Primero en llegar, primero en ser servido


2. Turno rotatorio (round robin) q=1


3. Turno rotatorio (round eobin) q=4


4. Primero el proceso mas corto


5. Menor tiempo restante


6. Mayor tasa de espera


7. Realimentacion (Feedback) q=1


8. Realimentacion (Feedback) q=2n

Planificación Primero en Entrar-Primero en Salir (FIFO, First In First Out)

También conocida como FIFO (primero en entrar, primero en salir) o esquema de cola rígido, es la política más simple. A medida que cada proceso se torna a la condición de Listo, se une a la cola de los listos, y cuando cesa el proceso que está Ejecutando actualmente, es seleccionado para correr el proceso que ha estado en la cola el mayor tiempo.

• Todos los proceso hacen la cola de listos.


• Cuando el proceso actual deja de correr, el siguiente proceso en la cola de listos es seleccionado.


• Un pequeño grupo de procesos puede esperar largos periodos de tiempo antes de ser ejecutados.


• Favorece los proceso con carga del procesador en lugar los que tienen carga de E/S.

Cuando se tiene que elegir a qué proceso asignar la CPU se escoge al que llevara más tiempo listo. El proceso se mantiene en la CPU hasta que se bloquea voluntariamente.

La ventaja de este algoritmo es su fácil implementación, sin embargo, no es válido para entornos interactivos ya que un proceso de mucho cálculo de CPU hace aumentar el tiempo de espera de los demás procesos . Para implementar el algoritmo (ver figura 2) sólo se necesita mantener una cola con los procesos listos ordenada por tiempo de llegada. Cuando un proceso pasa de bloqueado a listo se sitúa el último de la cola.

Ejemplo

• En a) el proceso P7 ocupa la CPU, los procesos P2, P4 y P8 se mantienen en la lista de preparados.

• En b) P7 se bloquea (ya sea al realizar una E/S, una operación WAIT sobre un semáforo a cero u otra causa) y P2 pasa a ocupar la CPU.

• En c) ocurre un evento (finalización de la operación de E/S, operación SIGNAL, ...) que desbloquea a P7, esto lo vuelve listo, pasando al final de la cola de procesos listos.

ENLACE A LA SIMULACIÓN FIFO

Planficación por Turno Rotatorio (Round Robin)

Es una manera directa de reducir la penalidad que sufren los trabajos cortos por parte de la política FCFS, a través del uso de preferencia basada en un reloj. Una interrupción de reloj es generada periódicamente. Cuando esta ocurre, el proceso que está corriendo actualmente es ubicado en la cola de los listos, y el próximo trabajo listo es seleccionado en base a la política FCFS. Esta técnica también es conocida como corte por tiempo, ya que cada proceso tiene asignado un tiempo de corte.

• Prevención del uso basada en un reloj.


• Cada quantum de tiempo un proceso usa la CPU.


• Las interrupciones de reloj se generan en intervalos fijos.


• Cuando ocurre una interrupción, el proceso en ejecución es colocado en la cola de listos y el siguiente proceso es seleccionado.

Este es uno de los algoritmos más antiguos, sencillos y equitativos en el reparto de la CPU entre los procesos, muy válido para entornos de tiempo compartido. Cada proceso tiene asignado un intervalo de tiempo de ejecución, llamado cuantum o cuanto. Si el proceso agota su cuantum de tiempo, se elige a otro proceso para ocupar la CPU. Si el proceso se bloquea o termina antes de agotar su cuantum también se alterna el uso de la CPU. El round robin es muy fácil de implementar. Todo lo que necesita el planificador es mantener una lista de los procesos listos.

Ejemplo

• En a) el proceso P7 ocupa la CPU.


• En b) P7 se bloquea pasando P2 a ocupar la CPU.


• En c) P2 agota su cuantum con lo que pasa al final de la lista y P4 ocupa la CPU. La figura 4 representa un ejemplo más largo de la ocupación de la CPU utilizando el algoritmo round robin.
  

ENLACE A LA SIMULACIÓN COLAS RR

Planificación por Prioridad al más corto (SJF, Short Job First)

Al igual que en el algoritmo FIFO las ráfagas se ejecutan sin interrupción, por tanto, sólo es útil para entornos batch. Su característica es que cuando se activa el planificador, éste elige la ráfaga de menor duración. Es decir, introduce una noción de prioridad entre ráfagas. Hay que recordar que en los entornos batch se pueden hacer estimaciones del tiempo de ejecución de los procesos.

La ventaja que presenta este algoritmo sobre el algoritmo FIFO es que minimiza el tiempo de finalización promedio, como puede verse en el siguiente ejemplo:

Ejemplo:

Supongamos que en un momento dado existen tres ráfagas listos R1, R2 y R3, sus tiempos de ejecución respectivos son 24, 3 y 3 ms. El proceso al que pertenece la ráfaga R1 es la que lleva más tiempo ejecutable, seguido del proceso al que pertenece R2 y del de R3. Veamos el tiempo medio de finalización (F) de las ráfagas aplicando FIFO y SJF:

FIFO F = (24 + 27 + 30) / 3 = 27 ms.

SJF F = (3 + 6 + 30) / 3 = 13 ms.

Se puede demostrar que este algoritmo es el óptimo. Para ello, consideremos el caso de cuatro ráfagas, con tiempos de ejecución de a, b, c y d. La primera ráfaga termina en el tiempo a, la segunda termina en el tiempo a+b, etc. El tiempo promedio de finalización es (4a+3b+2c+d)/4. Es evidente que a contribuye más al promedio que los demás tiempos, por lo que debe ser la ráfaga más corta, b la siguiente, y así sucesivamente. El mismo razonamiento se aplica a un número arbitrario de ráfagas.

ENLACE A LA SIMULACIÓN SJF

Planificación por Prioridad al Tiempo Restante más Corto (SRTF, Short Remaining Time First).

En este caso, el planificador siempre elige el proceso que tiene el tiempo restante de procesamiento esperado más corto. Cuando un proceso nuevo se une a la cola de Listos, este tiene un tiempo restante más corto que el actual proceso en ejecución. Por consiguiente el planificador puede preferenciar siempre que un nuevo proceso se vuelva listo. Como con la SPN, el planificador debe tener una estimación del tiempo de procesamiento para ejecutar la función de selección, y hay un riesgo de inanición de los procesos largos.

• Versión preventiva de la política el siguiente proceso más corto.


• Puede estimarse el tiempo de procesamiento.

HHRN(Mayor Relación de Respuesta)

Brinch Hansen desarrolló la estrategia de prioridad a la tasa de respueta más alta (HRN, highest-response-ratio-next) que corrige algunas deficiencias de SJF, particularmente el retraso excesivo de trabajos largos y el favoritismo excesivo para los trabajos cortos. HRN es un disciplina de planificación no apropiativa en la cual la prioridad de cada proceso no sólo se calcula en función del tiempo de servicio, sino también del tiempo que ha esperado para ser atendido. Cuando un trabajo obtiene el procesador, se ejecuta hasta terminar. Las prioridades dinámicas en HRN se calculan de acuerdo con la siguiente expresión:

prioridad = (tiempo de espera + tiempo de servicio) / tiempo de servicio

Como el tiempo de servicio aparece en el denominador, los procesos cortos tendrán preferencia. Pero como el tiempo de espera aparece en el numerador, los procesos largos que han esperado también tendrán un trato favorable. Obsérvese que la suma tiempo de espera + tiempo de servicio es el tiempo de respuesta del sistema para el proceso si éste se inicia de inmediato.