PDF de programación - Simuladores de Planificadores de Sistemas en Tiempo Real

Simuladores de Planificadores de Sistemas en Tiempo

Real 

Francisco J. Aliaga García, Isabel M. Aliaga García, 

Joaquín Olivares Bueno1, Juan C. Gámez Granados1, José M. Palomares Muñoz1

1 Dpto. de Arquitectura de Computadores, Electrónica y Tecnología Electrónica de la

Universidad de Córdoba

{i72algaf, i52algai, olivares, jcgamez, jmpalomares}@uco.es

Córdoba, España

Resumen. En este artículo se presenta un simulador desarrollado que permite
ejecutar   diferentes   planificadores   de   Tiempo   Real,   como   el   algoritmo   de
planificación cíclica, Algoritmo de la Razón Monótona (RMA) y EDF (Earliest
Deadline First) para un conjunto de procesos con unos datos dados y muestra
los resultados obtenidos. Mediante este simulador se facilita a los alumnos el
aprendizaje de los algoritmos de planificación.

Palabras Clave: Planificadores, simuladores, sistemas en tiempo real

Abstract. This paper presents a simulator that has been developed to allow the
execution   of   scheduling   algorithms   such   as   the   Cyclic   Non­preemptive
Executive,   Rate­monotonic   scheduling   (RMS)   and   Earliest   Deadline   First
(EDF) for a given set of processes with different values and the simulator
displays   the   results.   With   this   simulator,   students   are   able   to   learn   about
scheduling algorithms. 

Keywords: Schedulers, simulator, Real­Time systems, algorithms

1   Introducción

Existen   múltiples  aplicaciones   y   sistemas   que   necesitan   obtener   una   respuesta
antes   de   un   determinado   tiempo   límite   (denominado   comúnmente,  deadline).   A
dichos   sistemas   se   les   denomina   Sistemas   con   restricciones   de   Tiempo   Real   o
simplemente Sistemas en Tiempo Real. En estos sistemas se admite que el resultado
numérico no sea el óptimo, siempre que el resultado sea suficientemente aceptable y
se proporcione a tiempo. 

Enseñanza y Aprendizaje de Ingeniería de Computadores. Número 5, 2015105 En general, estos sistemas se dividen en un conjunto de tareas, cada una de ellas
encargada de dar respuesta a variaciones en el entorno o en el propio estado lógico del
sistema.   Existe   un   límite   en   el   número   de   tareas   que   se   puede   ejecutar
simultáneamente   (dicho   límite   es   igual   al   número   de   procesadores   o   núcleos   de
procesamiento existentes en el sistema). Cuando se supera dicho máximo ya no es
posible la ejecución simultánea real y por tanto, es necesario organizar de alguna
manera las tareas, para que se pueda establecer el orden de ejecución de cada una de
ellas en cada momento entre los diferentes procesadores. Las reglas que permiten
hacer dicho ordenamiento constituyen los algoritmos de planificación. 

El sistema operativo y, en particular, el planificador, es quizá el componente más
importante   de   un   Sistema   de   Tiempo   Real   [1].   Los   algoritmos   de   planificación
establecen prioridades a las tareas que permiten al sistema operativo escoger las tareas
más relevantes en cada instante. Dichas prioridades pueden ser fijas y no variar a lo
largo de la ejecución, o pueden ir variando conforme se van ejecutando las tareas.

Dada la importancia del procesamiento en tiempo real, es materia de estudio en
algunas   asignaturas.   En   particular,   se   puede   destacar   la   asignatura   Sistemas   en
Tiempo Real, perteneciente a los planes de estudios de la titulación de Ingeniería en
Informática,   Ingeniería   en   Automática   e   Ingeniería   Industrial   y   Graduado   en
Ingeniería  Informática de la Universidad de Córdoba (España).

El resto del artículo está estructurado como sigue. En el apartado 2 se hace una
breve   introducción   a   la   planificación   en   tiempo   real.   Continúa   el   apartado   3
mostrando otros planificadores que podemos encontrar en la literatura. Seguidamente,
el   apartado   4   nos   muestra   la   aplicación   desarrollada   junto   con   sus   principales
características para finalmente mostrar las conclusiones del trabajo en el apartado 5.

2   Planificación de Tiempo Real

En el momento en que hay más de dos tareas que se ejecutan en un determinado
sistema hay que plantear algún mecanismo para poder intercambiar las tareas. El
planificador es un módulo del S.O. que se encarga de controlar las tareas existentes en
el sistema y proporcionarles tiempo de CPU en un determinado instante, gestionando
el estado de ejecución en el que se encuentra y decidiendo en cada caso qué tarea
debe ejecutarse en cada momento [2].

La planificación en un sistema operativo de propósito general intenta garantizar un
uso extensivo de la CPU, equidad en la distribución de acceso al tiempo de ejecución
y bajo overhead. La planificación de un conjunto de tareas es viable si todas las tareas
comienzan su ejecución después de su instante de lanzamiento y todas terminan antes
de su deadline. La planificación de las tareas tiene dos mecanismos principales:

Enseñanza y Aprendizaje de Ingeniería de Computadores. Número 5, 2015106 



Planificación cíclica no apropiativa: Las tareas se ejecutan repetitivamente
con un determinado periodo. El sistema operativo permite ejecutar cada tarea
sin interrupción por parte de las otras tareas hasta que finalice, tras lo cual se
ejecuta otra tarea.
Planificación apropiativa: El sistema operativo asigna la CPU a una tarea
hasta que la interrumpe y le proporciona la CPU a otra tarea distinta. Se dice
que es apropiativa (o expropiativa) porque el S.O. se apropia de la CPU, que
estaba en posesión de una tarea. La asignación de una tarea a una CPU puede
realizarse por un cierto tiempo conocido apriori o hasta que suceda un bloqueo
o llamada al sistema operativo.

La asignación de prioridades a las tareas se puede realizar con planificaciones
apropiativas y con no apropiativas, aunque lo más habitual es que se realice con
planificaciones  apropiativas.  Las prioridades  pueden  asignarse  de manera  estática
(Algoritmo de la Razón Monótona, RMA) o de manera dinámica (EDF). 

2.1   Planificación cíclica no apropiativa

La planificación cíclica sin prioridad es un mecanismo de planificación sencillo de
implementar y calculable apriori. Requiere un conocimiento muy concreto de los
tiempos de ejecución de las rutinas y es muy eficiente en términos de bajo overhead
pero no maneja bien eventos esporádicos ni interrupciones. Su desventaja es que es
muy restrictivo, ya que todas las tareas deben tener tiempos de ejecución similares.

Esta   planificación   se   utiliza   principalmente   en   pequeños   sistemas   empotrados
donde se conocen completamente las tareas que requiere el sistema. Para desarrollar
un planificador basta con diseñar un bucle que vaya ejecutando una tras otra las
tareas.

Hay que definir un ciclo mayor, que coincide con el periodo de repetición de toda
la planificación (y es el mínimo común múltiplo de todos los periodos) y un ciclo
menor, que es el máximo común divisor de los periodos de todas las tareas.

2.2   RMA (Algoritmo de la Razón Monótona)

El   Algoritmo   de   la   Razón   Monótona   (RMA)   es   uno   de   los   algoritmos   de
asignación de prioridad más estudiados y es el más utilizado en la práctica. En RMA
todas las tareas son periódicas y el deadline (relativo, es decir, en cada iteración de la
tarea) de cada tarea es igual a su periodo. Las tareas de mayor prioridad pueden
interrumpir a las tareas de menor prioridad.

Este algoritmo asigna prioridades (Pi) a las tareas inversamente proporcionales a su

periodo (Ti). La prioridad de cada tarea se calcula de la siguiente forma:

Enseñanza y Aprendizaje de Ingeniería de Computadores. Número 5, 2015107 El esquema de prioridades de RMA es óptimo, en tanto que si un conjunto de
tareas es planificable mediante cualquier mecanismo de prioridades fijas, entonces lo
será mediante RMA.

Test de planificabilidad

El algoritmo de la Razón Monótona posee un mecanismo matemático que permite
determinar   si   un   conjunto   de   tareas   es   viable   utilizando   RMA.   En   1973,   Liu   y
Layland demostraron que un conjunto de tareas es planificable utilizando RMA si:

Para N procesos, se cumple que:

Donde Ci es el tiempo de ejecución en el peor caso del proceso i.
Ti es el periodo de repetición del proceso (llamado periodo de lanzamiento).
La sumatoria representa el grado de utilización total de la CPU por el conjunto de

procesos.

Este test es solo una condición suficiente y no necesaria. Si se cumple el test,
entonces   se   cumplirán   todos   los  deadline.   Si   el   test   falla,   los  deadline  podrían
cumplirse o no, por lo que se deberá hacer el gráfico de timeline para comprobar el
comportamiento de las tareas y observar si son planificables o no. 

2.3   EDF (Earliest Deadline First)

El   Algoritmo   EDF   (Earliest   Deadline   First)   es   un   algoritmo   de   asignación
dinámica   de   prioridades.   Las   prioridades   de   las   tareas   van   modificándose,
proporcionando mayor prioridad a las tareas que tienen más cercano su deadline. EDF
es un algoritmo óptimo en uniprocesadores: si un conjunto de tareas no es viable con
EDF, no existe ningún otro algoritmo de planificación que lo haga viable.

Con EDF no es necesario realizar la suposición de que las tareas son periódicas. El

resto de suposiciones realizadas para RMA se toman para EDF.

La ventaja de las prioridades dinámicas es que aumentan la flexibilidad, permiten
aumentar la prioridad de una tarea en una situación de alerta. Sin embargo, también

Enseñanza y Aprendizaje de Ingeniería de Computadores. Número 5, 2015108 tiene algunas desventajas como que el cambio dinámico de prioridades es peligroso
porque el comportamiento del sistema es mucho más complejo de predecir y, además,
existe el riesgo de bloquear algunas tareas durante demasiado tiempo. [3]

El test de planificación para EDF cuando todas las tareas son periódicas y sus
deadlines coinciden con sus periodos, es simple: Si la utilización total del co