La
planificación en tiempo real es uno de los campos de investigación más
activos en la informática. En este apartado, se ofrecerá una introducción a
los distintos métodos de planificación en tiempo real y se estudiarán dos
algoritmos de planificación clásicos.
En un
estudio de los algoritmos de planificación en tiempo real, se observa que los
distintos métodos de planificación dependen de sí el sistema lleva a cabo un
análisis de planificación: en caso afirmativo, si se realiza estática o dinámica:
y si el resultado del análisis genera un plan con respecto al cual se expiden
las tareas durante la ejecución. Basándose en estas consideraciones, los
autores identifican las siguientes clases de algoritmos:
Ø
Métodos
con tablas estáticas:
realizan un análisis estático de las planificaciones de expedición posibles.
El resultado del análisis es una planificación que determina, un tiempo de
ejecución, cuando debe comenzar la ejecución de una tarea.
Ø
Métodos
preferentes con prioridades estáticas: también se realiza un análisis estático, pero
no se realiza ninguna planificación. En cambio, se usa dicho análisis para
asignar prioridades a tareas, de forma que se pueda emplear un planificador
convencional preferente con prioridades.
Ø
Métodos
de planificación dinámica:
se determina la viabilidad en tiempo de ejecución (dinámicamente) en vez de
antes de empezar la ejecución (estáticamente). Se acepta una nueva tarea para
ejecutar sólo si es factible cumplir sus restricciones de tiempo. Uno de los
resultados del análisis de viabilidad es un plan o proyecto empleado para
decidir cuando se expide cada tarea.
Ø
Métodos
dinámicos del mejor resultado:
no se realiza ningún análisis de viabilidad. El sistema intenta cumplir todos
los plazos y abandona cualquier proceso ya iniciado y cuyo plazo no se haya
cumplido.
La planificación
con tablas estáticas es aplicable a tareas periódicas. La entrada del análisis
consta del tiempo periódico de llegada, el tiempo de ejecución, el plazo periódico
de finalización y la prioridad relativa de cada tarea. El planificador intenta
trazar un plan que le permite cumplir las exigencias de todas las tareas periódicas.
Este es un plan que le permite cumplir las exigencias de todas las tareas periódicas.
Este es un método predecible, pero también es inflexible, puesto que cualquier
cambio en las exigencias de una tarea. Son típicos de esta categoría los
algoritmos de planificación de primero el plazo más próximo u otras técnicas
periódicas de plazos.
La planificación
preferente con preferente con prioridades estáticas hace uso del mecanismo
de planificación referente con prioridades, habitual en la mayoría de los
sistemas muliprogamados que no son en tiempo real. En un sistema que no es real,
puede emplearse una gran variedad de factores para determinar la prioridad. Pro
ejemplo, en un sistema en tiempo compartido, la prioridad de un proceso cambia
dependiendo de sí tiene carga de procesador
o de E/S. En un sistema en tiempo real, la asignación de prioridades se
encuentra relacionada con las restricciones de tiempo asociadas a cada tarea. Un
ejemplo de ese método es el algoritmo monótono de frecuencia, que asigna
prioridades estáticas a las tareas en función de sus periodos.
La planificación
dinámica basada en un plan, después de que una tarea llega al sistema,
pero antes de comenzar a ejecutarla, se intenta crear un plan que contenga las tareas previamente planificadas, así como
la recién llegada. Si la recién llegada puede planificarse de forma que se
cumplan sus plazos y que no se pase ningún plazo de las tareas ya planificadas,
se revisa el plan para hacer sitio a la nueva tarea.
La planificación
dinámica del mejor resultado, es el método utilizado en la mayoría de los
sistemas en tiempo real comercializados en la actualidad. Cuando llega una
tarea, el sistema le asigna una prioridad en función de sus características.
Normalmente, se emplea alguna forma de planificación por plazo, como puede ser
la de primero el plazo más próximo. En general, las tareas son periódicas,
por lo que no es posible un análisis estático de planificación. Con este tipo
de planificación, no se sabe si se va a cumplir una restricción de tiempo
hasta que vence el plazo o la tarea termina. Esa es la mayor desventaja de esta
forma de planificación. Su ventaja está en la facilidad de implementación.
