Algoritmos De Planificacion

Diseño y Programación de Sistemas Operativos

Algoritmos de Planificación

Algoritmos de planificación

La planificación hace referencia a un conjunto de políticas y mecanismos incorporados al SO que gobiernan el orden en que se ejecutan los trabajos que deben ser completados por el sistema informático.


TIPOS DE PLANIFICACIÓN
Planificación a largo plazo Decisión de añadirprocesos a la reserva de procesos a ejecutar
Planificación a medio plazo Decisión de añadir procesos al conjunto de procesos que se encuentran parcial o completamente en memoria
Planificación a corto plazo Decisión sobre qué proceso disponible será ejecutado en el procesador
Planificación de E/S Decisión sobre qué solicitud de E/S pendiente será tratada por un dispositivo de E/S disponible

►FIFO (first in, first out) primero en entrar, primero en salir
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.



Problemas:
No es válido para entornos interactivos
no apropiativo y justo en el sentido formal
problemático para sistemas de tiempo compartidoVentajas:
muy simple
fácil implementación

►RR (Robin Round)
Este es uno de los algoritmos más antiguos y sencillos en el reparto de la CPU entre los procesos, muy válido para entornos de tiempo compartido
Una forma sencilla de entender el Round Robin es imaginar una secuencia para "tomar turnos".
Es muy fácil de implementar; todo lo que necesita el planificador es mantener una lista de losprocesos listos


►SRTF (shortest-remaining-time-first) la más corta de tiempo restante, en primer lugar
Asocia a cada proceso la longitud de su próxima ráfaga de CPU.
Utiliza longitudes para planificar el proceso con el menor tiempo
Esquemas:
- no preventivos: una CPU dado al proceso no puede ser anulada hasta la completa ráfaga de CPU
- preventiva: si un proceso nuevo llega con unalongitud de ráfaga de CPU menor que el tiempo restante del actual proceso de ejecución, asignación de prioridad.

► SJF (shortest-job-first) más corto puesto de trabajo, en primer lugar
Su característica principal es que cuando se activa el planificador, éste elige la ráfaga de menor duración.
Es óptimo al igual que la programación;
Da tiempo mínimo de espera promedio para un determinadoconjunto de procesos
Las ráfagas se ejecutan sin interrupción.
La ventaja que presenta este algoritmo sobre el algoritmo FIFO es que minimiza el tiempo de finalización promedio.

► (ED, Event-Driven) Planificación con expropiación basada en prioridades
Cada uno de los procesos del sistema está asignado a un nivel de prioridad y el planificador siempre elige al proceso preparado conprioridad más alta. Las prioridades pueden ser estáticas o dinámicas.
La estática no tiene variación del proceso a lo largo del ciclo de vida mientras que la dinámica si puede hacerlo.
Una problemática usual en este tipo de planificación es la posibilidad de que los procesos de prioridad más bajos queden siempre relegados en favor de los de prioridad más alta.
Cuando el sistema donde la situación noresiste el remedio habitual lo proporciona la utilización de una prioridad por envejecimiento en donde la prioridad de un proceso aumenta gradualmente en función de su tiempo de permanencia en el sistema. Los procesos más antiguos conseguirán así una prioridad tal que asegura su terminación en tiempo finito.
En un SO de tiempo real estricto, donde cada proceso debe tener garantizada su ejecuciónantes de la expiración de un plazo, se utiliza una disciplina de planificación por plazo más inmediato. Este tipo de planificación daría entrada al procesador al proceso cuyo plazo esté más próximo a cumplirse.
Otro tipo de planificación en este tipo de sistemas es la planificación por mínima laxitud, según la cual se selecciona el proceso con menor diferencia entre el tiempo que tarda en...