Kernel de Tiempo Real para Control de Procesos

Oscar Miranda Gomez, Pedro Meja AlvarezCINVESTAV-IPN, Seccion de Computacion

Av. IPN No. 2508, Mexico, D. F. 07300.omiranda@computacion.cs.cinvestav.mx, pmejia@delta.cs.cinvestav.mx

ResumenEn este artculo se describe la estructura de un Kernel de

Tiempo Real desarrollado en la Seccion de Computacion delCINVESTAV-IPN. Las ventajas de este sistema operativo detiempo real son principalmente su tamano, su modularidad,su facilidad de poder comunicarse con otros Kernels detiempo real ejecutandose en otras computadoras y su interfazcon un sistema grafico de simulacion de tareas de tiemporeal.

El Kernel de Tiempo Real es pequeno (de tamano 20.5Kb)y ademas realiza funciones que todo sistema en tiempo re-al requiere, como son: a) manejo de interrupciones externas,b) ejecucion de tareas concurrentes, c) comunicacion y sin-cronizacion entre procesos mediante las primitivas de accesoa buzones y semaforos, d) planificacion de tareas periodicasy aperiodicas, mediante las polticas de planificacion RateMonotonic y Earliest Deadline First (EDF) [6], y e) manejode tiempos.Palabras ClaveSistemas en Tiempo Real, Kernel, Rate Monotonic, EDF,Planificacion de tareas.

1. IntroduccionEn la actualidad el avance de la tecnologa ha permi-

tido una miniaturizacion en los dispositivos electronicosy un incremento en la capacidad de procesamientode estos dispositivos. Estos dispositivos se encuentranen general empotrados (embebidos) dentro de aplica-ciones tales como telefonos celulares, PALMs, com-putadoras industriales, robots, satelites, automoviles ytambien en distintos aparatos electro-domesticos. Lamayora de estos dispositivos contienen un procesadory un pequeno sistema operativo empotrado el cual escapaz de controlar todo el hardware de manera efi-ciente. Debido a la naturaleza de estos dispositivos em-bebidos, en ocasiones se les demanda no solo un cor-recto y eficiente funcionamiento sino tambien un estric-to cumplimiento de requerimientos temporales. A estossistemas se les conoce como sistemas de tiempo realembebidos.

En un sistema de tiempo real el principal compo-nente lo constituye el sistema operativo o Kernel. Unsistema operativo de tiempo real se ejecuta por lo ge-neral sobre un plataforma embebida (que puede ser

un microcontrolador, un DSP o cualquier procesadorconvencional). Este sistema operativo debe ser ca-paz de controlar todos los recursos de hardware de laplataforma que se encuentra y tambien de administrartodos los tiempos de ejecucion de las tareas de tiem-po real. Normalmente este sistema operativo no mane-ja discos, memoria cache, DMA o complejos sistemasde redes de comunicaciones, debido a que su ejecu-cion debe ser predecible (debe ser posible estimar conexactitud sus tiempos de ejecucion).

Las tareas de tiempo real son procedimientos se-cuenciales que se ejecutan en forma concurrente conotras tareas del sistema. A una tarea de tiempo reali se le asocia, un tiempo de arribo ai, un perodo deejecucion, Ti y un plazo de respuesta Di [1]. Estas ta-reas se clasifican en periodicas y aperiodicas. Las ta-reas periodicas se ejecutan a intervalos regulares (lla-mados perodos), mientras que las tareas aperiodicasno tienen un tiempo de arribo conocido, se ejecutanpor un solo perodo de ejecucion, y cuando arribandeben de cumplir con sus plazos de respuesta. Unatarea de tiempo real que controla procesos crticos (enlos cuales no se permite la perdida de su plazo de res-puesta) se le conoce como tarea crtica. A las tareasacrticas se les exige terminar lo mas pronto posiblesu ejecucion, pero como no es crtico pueden llegar aperder algunos de sus plazos de respuesta.

Actualmente el Kernel se ejecuta sobre MS-DOS,sin embargo, ha sido disenado como software inde-pendiente (portable) del sistema operativo, con el finde que pueda cargarse en cualquier plataforma quecontenga procesadores INTEL o compatibles. Se tienecontemplado que el Kernel sea totalmente independi-ente, siendo este el que se encargue de controlar to-do el hardware y procesos que se encuentren en lamaquina, o en su caso, en el sistema empotrado endonde se implemente.

2. Trabajo RelacionadoExisten en la actualidad un gran numero de sistemas

operativos de tiempo real industriales y experimentales[8, 3].

Entre los sistemas operativos comerciales mas uti-

lizados estan LinxOs, VxWorks, QNX, RT-Linux, yTimeSys Linux. Estos sistemas operativos incluyen unaamplia gama de servicios tales como manejo de proce-sos, manejo de memoria, manejo de tiempos, manejode dispositivos e interfaces con distintas plataformasde hardware [10]. Por lo general estos sistemas ope-rativos son de gran tamano, y estan disenados paracubrir una amplia gama de aplicaciones de sistemasembebidos.

Por otro lado, existen los sistemas operativos experi-mentales de los cuales los mas conocidos en la actua-lidad son: EMERALDS de la Universidad de Michigan[11], S.H.A.R.K de la Escuela Superior Santa Ana dePisa Italia, MACH de la Universidad Carnegie Mellon,MARRUTTI de la Universidad de Maryland, SPRINGde la Universidad de Massachusetts en Amherts yMARS de la Universidad Tecnica de Viena. Todos es-tos sistemas operativos incluyen distintos metodos deplanificacion, son de tamano medio a pequeno, in-cluyen interfaces graficas y son bastante flexibles ensu diseno. En varios de estos sistemas operativos seincluyen tecnicas desarrolladas por dichas Universi-dades, tales son los casos de MARS con su tecnica deplanificacion basada en eventos de tiempos, o SPRINGque se basa en la tecnica de planificacion del mejor es-fuerzo (best effort scheduling).

3. Estructura del KernelEl Kernel desarrollado es de tamano pequeno, de

20.5KBytes, pero este tamano puede variar dependien-do de los servicios, libreras y controladores que se lepudieran anadir.

El Kernel esta compuesto de los siguientes compo-nentes:

Manejador de Procesos.

Manejador de Buzones para comunicacionsncrona y asncrona.

Manejador de Tareas Periodicas y Aperiodicas.

Manejador de Tiempos.

Manejador de Interrupciones externas.

Manejador de Semaforos para sincronizacion en-tre procesos.

Manejador de Comunicaciones externas.

Mecanismos de Planificacion Rate Monotonic,EDF y FIFO Round Robin.

Interface para Depuracion y Monitorizacion.

Figura 1: Bloque de control de procesos (Process BlockControl)

3.1. Manejador de ProcesosEl manejador de procesos (tareas) es uno de los

servicios basicos con los que cuenta el Kernel y ofrecevarias funciones de soporte tales como la creaciony eliminacion de procesos, la planificacion de tareas(EDF, Rate Monotonic, FIFO Round Robin) y el cambiode contexto, [2].

Un proceso es un conjunto de codigo secuencialidentificado con un nombre y una prioridad, el cualse ejecuta concurrentemente con otros procesos [4].Cada proceso tiene asociada una estructura llamadaPCB (Process Control Block) la cual contiene la infor-macion necesaria para el control del proceso.

La estructura del PCB en el Kernel esta representa-da en la Figura 1, en la cual se puede apreciar que lainformacion esta ordenada de la siguiente manera:

1) Informacion del proceso.- Aqu se encuentra al-macenado el identificador del proceso, el estadoen que se encuentra durante la ejecucion del Ker-nel (listo, suspendido, etc.) y la direccion de la pilaque le corresponde al proceso. La pila almacenael contenido de sus registros (cs, ip, bp, di, si, ds,es, dx, cx, bx, ax y flags) as como las direccionesde las instrucciones que ejecuta el proceso. Losregistros incluidos en el stack son indispensablespara que el Kernel pueda llevar a cabo el cambiode contexto.

2) Informacion para el planificador.- Aqu se en-cuentran los datos necesarios para que el procesopueda ser planificado. Contiene informacion comola prioridad, el tiempo de computo, el plazo,el tiempo de activacion y el tiempo de ejecu-cion. Estos datos son necesarios para que laspolticas de planificacion puedan calcular cuandole corresponde ejecutarse a cada proceso.

3) Informacion de memoria utilizada en buzones.-Solo contiene un apuntador a una direccion dememoria reservada para almacenar un mensaje

del buzon en caso de que el proceso sea intro-ducido a la cola de procesos bloqueados porbuzon (cpbb).

El Kernel inicialmente esta configurado para trabajarcon un maximo de 32 procesos, sin embargo elusuario en base a sus necesidades, puede aumentarel numero de los procesos a controlar por el Kernel.Los procesos reciben una prioridad de ejecucion quedepende de la poltica de planificacion en la que seejecuten. La prioridad de una tarea es estatica si estase ejecuta bajo la poltica Rate Monotonic o Fifo RoundRobin, y es dinamica cuando se ejecuta con la polticaEDF. Existen dos procesos importantes en el Kernelllamados: primero y ultimo los cuales son activados aliniciar el Kernel. El proceso primero es el encargadode activar a los demas procesos que se van a ejecutaren el sistema y el proceso ultimo es un proceso que seejecuta cuando ningun otro proceso se encuentra listopara ser ejecutado.

3.1.1. Estados de los Procesos

Cada proceso puede encontrarse en cualquiera delos siguientes estados [7], como se describe en laFigura 2:

Ejecucion.- En este estado, el proceso tiene el controldel procesador.

Listo.- En este estado, el proceso se encuentra listopara ejecutarse y espera a que se le asigne elprocesador.

Bloqueado.- En este estado, el proceso se encuentrabloqueado en algun recurso, como puede ser unsemaforo, o un un buzon.

Retrasado.- En este estado el proceso se encuentrabloqueado, esperando por un tiempo determinadoantes de regresar al estado de listo.

Eliminado.- En este estado se encuentran los proce-sos que no han sido activados o que ya han termi-nado su ejecucion.

Los procesos cambian de estado por alguna de lassiguientes razones (ver Figura 2):1. el proceso es creado.

2. se le asigna el procesador.

3. se le quita el procesador debido a: un bloqueo, elalistamiento de un proceso con mayor prioridad opor el fin de su tiempo de computo.

4. el proceso se retrasa.

5. ocurre una vez que termina su tiempo de retraso,quedando listo para ejecutarse.

Figura 2: Estados de los Procesos

6. el proceso se bloquea por un recurso o interrup-cion.

7. obtuvo el recurso que esperaba y queda listo paraejecutarse.

8. el proceso se elimina a s mismo.

3.1.2. Manejo de Colas de ProcesosDebido a que el Kernel se ejecuta sobre un solo

procesador (aunque tiene tambien la capacidad decomunicarse con otros procesadores sobre los quese ejecute el Kernel), solo un proceso puede estarejecutandose en el procesador, mientras que variosprocesos pueden encontrarse listos para ejecucion yotros mas pueden estar bloqueados por recursos.

Dependiendo del estado en que se encuentren lastareas, cada una de estas puede encontrarse enalguna de las siguientes colas:

1. Cola de procesos listos.

2. Cola de procesos bloqueados por enviar o recibirun mensaje.

3. Cola de procesos bloqueados por espera en unsemaforo.

4. Cola de procesos retrasados.

Las colas de procesos fueron disenadas con el fnde manejar eficientemente la ejecucion de las tareasde acuerdo a su estado. Las tres primeras colastienen una estructura similar con multiples nivelesde prioridades, como se muestra en la Figura 3. Laprimera tarea en la cola es aquella que cuenta conla mayor prioridad en el sistema. En nuestro Kernel,asumimos que los procesos se insertan al final de lacola respectiva dependiendo de su prioridad y su arriboa la cola.

Figura 3: Colas de Procesos

3.2. Manejador de InterrupcionesActualmente el Kernel procesa solo las solicitudes de

interrupcion del reloj y del teclado. La interrupcion 8 escapturada con el fn de manejar el reloj del Kernel. Estainterrupcion fue re-programada a 1 milisegundo con lafinalidad de aumentar la granularidad del sistema. Deesta forma, el Quantum, o el tiempo maximo asignadoa una tarea para su ejecucion, cuenta con mayorprecision. Con esta interrupcion el Kernel controla elcambio de contexto y el tiempo de bloqueo de laprimitiva retrasa. La interrupcion del teclado permite alKernel interrumpir su ejecucion, y es util en la deteccionde caracteres del teclado.

3.3. Manejo del TiempoMediante el manejador del tiempo, el Kernel puede

manejar el tiempo en que una tarea se ejecuta enforma continua. A este tiempo se le conoce comoQuantum y depende de la resolucion del timer delsistema. Como se explico anteriormente, se modifico eltimer del sistema para lograr una resolucion aproxima-da de 1 milisegundo. Por esta razon, el Quantum solopuede darse en unidades de 1 milisegundo.

Dentro del manejo del tiempo tambien se permiteque una tarea pueda dormirse durante un cierto tiempomediante la primitiva retrasa. Con esta primitiva unproceso es incluido a una cola de procesos dormidos,y despertara hasta que se consuma el tiempo quesolicita. El parametro que recibe la primitiva retrasa,permite al proceso que la ejecuta dormirse por unnumero dado de unidades de tiempo.

3.4. Sincronizacion y Comunicacion en-tre Tareas

El Kernel contiene mecanismos de sincronizaciony comunicacion entre tareas, los cuales se manejanmediante semaforos y buzones.

3.4.1. Semaforos

Mediante los semaforos es posible sincronizar y es-tablecer regiones de exclusion mutua entre las tareasdel sistema. Un semaforo es una variable entera quese crea en el espacio de memoria del Kernel [9], ycuyo valor solo se puede manipular con tres primitivasque hacen sus operaciones de forma atomica1.

Las tres primitivas de los semaforos son:

IniciaSemaforo.- En esta primitiva se le da un valorinicial (positivo) a la variable del semaforo, con locual se crean una cola asociada al semaforo. Enesta cola, se incluiran los procesos bloqueadospor este recurso.

Senal.- Esta primitiva permite incrementar en unaunidad, a la variable del semaforo. Si la variabledel semaforo es negativa indicara que existealgun proceso bloqueado (en la cola de estesemaforo). Por lo tanto si al ejecutar la primitivasenal, el contador es negativo, algun procesobloqueado en la cola de este semaforo (el que seencuentre al principio de la cola), se pasara a lacola de procesos listos. En este caso, el Kernelprovocara un cambio de contexto para verificar siel proceso desbloqueado, es de mayor prioridadque el proceso en ejecucion. Si al ejecutar laprimitiva senal no existen procesos bloqueados(el contador es cero o positivo), se incrementa elcontador del semaforo y el proceso continuara suejecucion.

Espera.- Esta primitiva permite decrementar en unaunidad a la variable del semaforo. Si despues dedecrementar esta variable, su valor es negativo,el proceso que ejecuta esta primitiva es enviadoa la cola del semaforo y sacado de ejecucion.En este caso, el Kernel invocara a la rutina decambio de contexto para ejecutar al siguienteproceso de la cola de listos. Por el contrario, sidespues de ejecutar la primitiva espera, la variabledel semaforo contiene un valor cero o positivo, elproceso continuara su ejecucion.

En la Figura 4 se muestran 2 tareas haciendo accesode un semaforo para implementar regiones crticas. Eluso de estas regiones crticas permite a cada procesoaccesar una variable compartida en forma exclusiva.

3.4.2. Buzones

Un buzon es una area de memoria compartida capazde contener un numero limitado de mensajes. Estos

1Todas las primitivas del Kernel son de ejecucion atomica, locual implica que no podran ser interrumpidas durante su ejecucion.Las interrupciones son deshabilitadas durante la ejecucion de lasprimitivas a fin de proteger las variables y la memoria del Kernel

Figura 4: Utilizacion de los semaforos en el Kernel

mensajes son almacenados en el buzon mediante unacola circular tipo FIFO. Con los buzones es posiblecomunicar a dos o mas procesos entre si. Cada buzontiene asociada una cola de procesos. En esta colade procesos se introduciran aquellos procesos que seencuentren bloqueados por este buzon [9].

En el manejo de los buzones se utilizan tres opera-ciones basicas:

CrearBuzon.- Esta primitiva permite crear la estruc-tura de datos que define al buzon y su cola de pro-cesos asociada.

EnviarMensaje.- Mediante esta primitiva es posibleenviar un mensaje en formato ASCII al buzonindicado (el cual previamente tuvo que haber sidocreado). Si al enviar un mensaje alguna tarea seencontraba bloqueada esperando mensajes, estatarea sera desbloqueada y enviada a la cola deprocesos listos.

Si un proceso enva un mensaje al buzon yel buzon se encuentra lleno, provocara que elproceso se incluya en la cola del buzon. Esteproceso permanecera en esta cola hasta queotro proceso reciba mensajes y libere suficienteespacio del buzon.

RecibirMensaje.- Esta primitiva permite recibir men-sajes del buzon indicado. Si el buzon se encuen-tra vaco, el proceso que invoca a esta primitivasera bloqueado en la cola respectiva.

Note que la cola del buzon contendra solo a proce-sos bloqueados esperando recibir mensajes, o solo aprocesos esperando enviar mensajes al buzon. Por suimplementacion, los dos tipos de procesos no puedencoexistir en una misma cola.

3.5. Caractersticas Adicionales en elKernel

3.5.1. Tamano

Debido a que el Kernel fue disenado para suimplementacion en un sistema empotrado, el Kernelcontiene solo las funciones que son necesarias para elcontrol de los sistemas de tiempo real en este tipo dedispositivos. Por lo tanto, el tamano del Kernel es muypequeno (20.5Kb). Esta caracterstica hace posibleque se pueda implementar en sistemas empotradoscon altas restricciones de memoria. En la tabla 1se muestra a detalle el tamano de cada uno de losarchivos que conforman el Kernel.

3.5.2. Granularidad

Como se explico anteriormente, la granularidad deltiempo en el Kernel es de 1 milisegundo. Esto permiteprogramar el Quantum de los procesos, y el tiempo dela primitiva retrasa, con esta resolucion. Actualmente,el Kernel maneja la interrupcion 8, para efectuar sucambio de contexto. Sin, embargo, el Kernel tambienes capaz de manejar otras interrupciones tales comola interrupcion 70h, que pertenece al reloj de tiemporeal de la PC.

De la misma forma, el control del tiempo e interrup-ciones periodicas dentro del Kernel se llevan a cabomediante el temporizador 8254. Este temporizador, encualquier PC con procesador compatible con Intel, ini-cialmente se encuentra alimentado con una senal de1,193,180Hz y configurado en modo 2 con lo cual ge-nera 18.2 ticks de reloj por segundo (una interrupcion08 es generada por cada tick). Esta frecuencia es muybaja para los sistemas de tiempo real, por lo que enel Kernel se re-programo el timer cambiando su va-lor inicial por otro que pudiera generar interrupcionesperiodicas a 1000Hz (1,000 por segundo); esta fre-cuencia es similar a la que se obtiene con el reloj detiempo real (RTC) pero con la ventaja de que el timertiene la mayor prioridad y ninguna otra interrupciongenerada en la maquina lo puede detener.

Nombre del archivo TamanoKernel 1.05Kbconfig 231 bytes

constant 1.55Kberrores 1.85Kblibreria 1.97Kb

mancolas 4.24Kbmancpu 491 bytesmanreg 1.49Kbplanif 1.99Kbpribuz 2.51Kbpripro 621 bytesprisem 1.67Kbpritim 255 bytes

teclado 304 bytestimer 376 bytes

TOTAL 20.5Kb

Tabla 1: Tamano del Kernel.

Tiempo Tiempo TiempoPrimitiva mnimo(s) maximo(s) promedio(s)

Inicializacion del sistema 11.43 13.23 12.34Cambio de contexto 30.37 34.12 32.44

Activa 11.73 12.57 11.93Elimina 11.73 14.24 12.08Retrasa 11.23 13.23 12.23

Crea semaforo 11.73 12.57 11.81Senal 11.73 13.40 12.17

Espera 11.73 12.57 12.17Crea buzon 11.73 12.57 11.83

Enva Mensaje 12.57 14.24 12.80Recibe Mensaje 13.40 15.92 14.23Inserta a la cola 11.73 12.57 12.32Saca de la cola 11.73 12.57 12.30Busca el mayor 23.46 24.30 23.59

Earliest Deadline First 11.73 15.08 12.28Rate Monotonic 11.73 13.40 12.25

Tabla 2: Tiempos de ejecucion de las primitivas del Kernel.

3.5.3. Tiempos de ejecucion del KernelEn cualquier aplicacion de tiempo real es importante

conocer el tiempo de ejecucion de las primitivasdisenadas en el Kernel, debido a la predecibilidadcon que debe contar el sistema. En la tabla 2 seindica que el cambio de contexto tarda en promedio32.44 microsegundos. Debido a que la granularidaddel Kernel es de 1 milisegundo (1,000 interrupcionespor segundo), el tiempo que le resta al proceso paraejecutarse (despues de la ejecucion de la rutina decambio de contexto) sera de aproximadamente 967.55microsegundos.

Los tiempos presentados en la tabla 2 fueronobtenidos en una computadora Laptop Pentium 4 a1.4GHz, con 240MB de RAM y 16MB de RAM en video.Con la finalidad de obtener las mediciones mas realis-tas posibles, el Kernel se ejecuto solo bajo el ambientede MS-DOS (fuera del ambiente de Windows).

4. Arquitectura del KernelEn la Figura 5 se presenta la arquitectura general

del Kernel en tiempo real. En el nivel mas bajo se en-cuentran los distintos dispositivos que controla el Ker-nel. En el siguiente nivel estan las distintas funcionesdel Kernel, conocidas como primitivas. En la parte su-perior, se encuentran los procesos del usuario quienesinteraccionan con el Kernel. Entre el Kernel y los pro-cesos del usuario se encuentra una interface la cualpermite desligar a ambos componentes. Esta interfacepermite, mediante interrupciones, conectar a amboscomponentes aunque estos hallan sido compilados porseparado. Esta interface permite que los procesos deaplicacion puedan estar en un lenguaje distinto al delKernel.

El Kernel soporta una arquitectura de un procesador,en el cual los procesos se ejecutan concurrentemente.El Kernel se implemento en lenguaje de programacionC y en Ensamblador, propios de la familia de proce-sadores Intel 80x86. Algunas partes del Kernel, con-sideradas como crticas, como son el cambio de con-texto, el manejo de interrupciones y el copiado de men-sajes, se codificaron en lenguaje ensamblador para op-timizar sus tiempos de ejecucion.

5. Planificacion de ProcesosEn las aplicaciones de Tiempo Real, lo importante

es proporcionar un orden de ejecucion a las tareasde tiempo real, de forma tal que todas estas cumplancon sus plazos de respuesta. Para esto, es necesarioconocer con la mayor precision posible los tiemposde arribo, los tiempos de ejecucion y los tiempos derespuesta, de cada una de las tareas del sistema.As mismo es necesario conocer con precision lostiempos de los perodos de ejecucion (inter-arribo detareas) para el caso de las tareas periodicas.

Las polticas de planificacion permiten dar un ordende ejecucion a las tareas y garantizar el correctofuncionamiento temporal de las mismas.

El Kernel desarrollado utiliza tres tipos de planifi-cadores:

FIFO Round Robin.

Rate Monotonic.

Earliest Deadline First (EDF).El planificador FIFO Round Robin es el mas simple

y se dedica a atender las tareas en base a suprioridad. Las tareas en la cola de listos se encuentran

Figura 5: Arquitectura del Kernel

ordenadas de acuerdo a su prioridad, la cual esasignada por el usuario. Las tareas con la mismaprioridad son atendidas de forma FIFO Round-Robin.

La planificacion Rate Monotonic asigna prioridades alas tareas en base a sus perodos. La tareas con menorperodo (o mayor frecuencia de ejecucion) reciben lamayor prioridad. La asignacion de prioridades en lapoltica Rate Monotic es estatica, es decir, que seasigna una sola vez, al principio de la ejecucion delas tareas, y esta no cambia durante su ejecucion.La planificacion EDF asigna las prioridades de formadinamica. La prioridad se asigna de acuerdo a lacercana de las tareas (de su tiempo de arribo) conrespecto a su plazo de respuesta. La tarea conplazo de respuesta mas cercano (en un momentodeterminado) es la que recibe mayor prioridad. Estetipo de planificacion permite que las prioridades delas tareas cambien todo el tiempo, dependiendo de sucercana en ese momento con su plazo de respuesta.

6. Analisis de Planificabilidadpara Sistemas de Tiempo Real

La funcion de un algoritmo de planificacion es deter-minar un orden de ejecucion para un conjunto de ta-reas. Los algoritmos de planificacion tienen asociadosun analisis de planificabilidad que permite verificar si elconjunto de tareas es factible (si ninguna tarea pierdesus plazos de respuesta). Un sistema en tiempo real seconsidera factible si, en funcion del algoritmo de plani-ficacion elegido, es capaz de satisfacer todos los tiem-pos de respuesta de las tareas. Una forma para deter-minar que el algoritmo de planificacion elegido asegurael cumplimiento de los plazos, es realizando un analisisde planificabilidad. Un tipo de analisis consiste en uncalculo de los tiempos de respuesta del peor caso paracada una de las tareas que conforman el sistema. Silos tiempos de respuesta para el peor caso son siem-pre menores que los plazos de respuesta asociados alas mismas, quiere decir que el sistema es planificableen cualquier condicion.

Las caractersticas del modelo de las tareas

planteadas originalmente para los algoritmos de plani-ficacion Rate Monotonic y EDF [5] son las siguientes:

1. Un conjunto de tareas T esta compuesto porn tareas {1 . . . i . . . n}. Cada i esta definidade acuerdo a los parametros: Di = Plazo, Pi =Perodo y Ci = Tiempo de ejecucion (ejecutado sininterrupcion).

2. Ci Di = Pi, es decir, las tareas tienen tiemposde ejecucion menores que su plazo, y su plazo esigual a su perodo.

3. El tiempo de ejecucion de cada tarea (Ci) es cons-tante. Siempre se ejecuta a la misma velocidad.

4. Todas las tareas son periodicas.

5. No existen relaciones de precedencia entre lastareas.

6. No se permite la comunicacion ni la sincronizacionentre tareas.

7. No se considera el acceso a recursos compartidospor parte de las tareas.

8. El tiempo de ejecucion del cambio de contexto yde las primitivas es despreciable.

9. Todos los procesos se ejecutan en un solo proce-sador.

6.1. Factor de Utilizacion (U)El factor de utilizacion del procesador para un

conjunto dado de tareas representa la fraccion detiempo de procesador empleada en la ejecucion dedicho conjunto de tareas.

Para el modelo de sistema presentado, el factor deutilizacion de una tarea i se expresa como sigue:

Ui =CiTi

(1)

De la ecuacion (1) se tiene que el factor de utilizacionpara un conjunto de tareas es:

U =ni=1

CiPi

(2)

Es uno de los algoritmos de planificacion masantiguos, sencillo y usado, en este cada proceso tieneasignado un intervalo de tiempo de ejecucion llamadoQuantum. FIFO Round Robin es muy sencillo deimplementar, todo lo que necesita el planificador esconocer la cola de los procesos listos y una vez queel proceso en ejecucion consume su Quantum, se lequita el procesador y se le asigna al siguiente en lacola, colocando al proceso que salio al final de la colade procesos listos.

El analisis de planificabilidad para este algoritmoconsiste unicamente en verificar si su factor de uti-lizacion excede al 100 % (U 1).

6.2. Algoritmo Rate MonotonicEn el algoritmo Rate Monotonic, sus autores [5]

proporcionan un analisis de planificabilidad de tareasbasado en la utilizacion del procesador. Este analisis,compara la utilizacion del conjunto de tareas con unacota lmite que depende del numero de tareas delsistema. En este analisis un conjunto de n tareas noperdera su plazo si cumple con la siguiente condicion:

UTOT =ni=1

CiTi n(2 1n 1) (3)

La tabla 3 describe el comportamiento de la expre-sion (3) para distintos valores de n. Como se puedeapreciar en dicha tabla, al aumentar el numero de tare-as la utilizacion mnima garantizada converge en:

Umin = ln2 0,6931 (4)

6.3. Algoritmo FIFO Round RobinEs uno de los algoritmos de planificacion mas

antiguos, sencillo y usado, en este cada proceso tiene

n Umin

1 12 0.82843 0.77884 0.75685 0.7334. .

. .

0.6931

Tabla 3: Utilizacion mnima garantizada para n tareas.

asignado un intervalo de tiempo de ejecucion llamadoQuantum. FIFO Round Robin es muy sencillo deimplementar, todo lo que necesita el planificador esconocer la cola de los procesos listos y una vez queel proceso en ejecucion consume su Quantum, se lequita el procesador y se le asigna al siguiente en lacola, colocando al proceso que salio al final de la colade procesos listos.

El analisis de planificabilidad para este algoritmoconsiste unicamente en verificar si su factor de uti-lizacion excede al 100 % (U 1).

6.4. Algoritmo Earliest Deadline First

El algoritmo de planificacion EDF (Earliest DeadlineFirst) es otro algoritmo de planificacion para sistemasen tiempo real el cual utiliza el plazo de respuestade las tareas como la base para asignar prioridades.En esta poltica de planificacion, la tarea con plazomas cercano es quien recibe la mayor prioridad deejecucion. Bajo este algoritmo, la condicion necesariay suficiente para que un conjunto de tareas periodicastenga una planificacion viable es:

U 1 (5)

EDF consigue un factor de utilizacion del 100 % paralos conjuntos de tarea que planifica, por lo que sepuede decir que es optimo globalmente, es decir, quesi existe un algoritmo que proporcione una planifica-cion factible con un determinado conjunto de tareasperiodicas, entonces EDF tambien proporciona unaplanificacion factible para dicho conjunto de tareas.

7. Ejemplo de Aplicacion de Tare-as de Tiempo-Real

Como se aprecia en la figura 6 hemos creado unaaplicacion que consiste de 4 tareas de tiempo real.La prioridad de las tareas es la misma. La tarea 1representa un reloj en movimiento. Las tareas 2 y3 ejecutan un juego en el cual un caracter rebotasobre una ventana. Finalmente la tarea 4 consiste enun editor de caracteres que se ejecuta dentro de suventana. La poltica de planificacion utilizada fue FIFORound-Robin.

Durante la ejecucion de esta aplicacion, el Quantumutilizado fue de 5 mili-segundos. Con esta resolucion,fue posible observar que cada tarea se ejecuta como siestuviera en un procesador diferente.

Figura 6: Muestra de 4 tareas ejecutandose sobre el Kernel

8. Ambiente de Desarrollo de Sis-temas de Tiempo Real

El Kernel de tiempo real descrito en este artculo,es un componente de un ambiente de desarrollo desistemas de tiempo real mas amplio. El ambiente dedesarrollo se muestra en la Figura 7 y consiste de lossiguientes componentes:

Ambiente Visual para Desarrollo de Sistemasde Tiempo RealEste ambiente visual esta siendo desarrollado jun-to con el Kernel, y permitira disenar los procesosde tiempo real en forma visual utilizando UML ySimuLink. Nuestro objetivo es disenar sistemas detiempo real para aplicaciones de control de pro-cesos, en donde pueda ser que no sea necesarioprogramar ni una linea de codigo.Para lograr este objetivo estamos actualmente de-sarrollando interfaces que permitan que SimuLink(Herramienta para generar aplicaciones de controlde procesos) genere el codigo que pueda serincluido en el Kernel como una tarea del sis-tema. Ademas, dentro de este ambiente visualsera posible incluir codigo en forma visual (deforma parecida a como se realiza en VISUALC incluyendo componentes de software de tipogeneral y mediante objetos en UML.

Kernel de Tiempo Real Distribuido.El Kernel descrito en este artculo, actualmenteesta siendo extendido para un sistema distribuido.Nuestro interes es de que tareas de tiemporeal ejecutandose en en distintas computadoraspuedan comunicarse y sincronizarse.

Ambiente de Simulacion.

Otro componente de este ambiente de desarrolloes el ambiente de simulacion de tareas de tiemporeal, el cual permitira graficar la ejecucion delas tareas de tiempo real del sistema en for-ma estatica y dinamica. En el modo estatico,sera posible definir un conjunto de tareas detiempo real y graficar su comportamiento. En elmodo dinamico, el Kernel se conectara en formadinamica al ambiente de simulacion a fin depresentar en forma grafica la ejecucion del Kernel.As mismo, el Kernel podra generar un archivo detexto con su secuencia de ejecucion y el ambientede simulacion podra leer este archivo y graficar suejecucion.

Ejecucion en Plataformas Embebidas.Actualmente el Kernel de tiempo real se ejecutasobre MS-DOS, sin embargo, como trabajo futuronos hemos planteado la necesidad de portar elKernel en plataformas embebidas. Sobre estasplataformas, sera necesario anadir al Kernel unmanejador de memoria debido a que actualmenteel Kernel utiliza el cargador (loader) de MS-DOS para el asignamiento de memoria y para suejecucion. Ademas, sera necesario el desarrollode interfaces de aplicacion (API) y drivers paralos dispositivos de entrada/salida requeridos en laplataforma embebida.

9. Conclusiones y Trabajo FuturoEl Kernel descrito en este artculo es capaz de

controlar tareas de tiempo real concurrentes a unaresolucion de un milisegundo. El Kernel contiene distin-tas primitivas para manejo de procesos, comunicacion,sincronizacion y manejo de tiempo. As mismo elKernel desarrollado utiliza los mejores mecanismos de

Figura 7: Ambiente de Desarrollo de Sistemas en Tiempo Real Orientado a Control de Procesos

planificacion de procesos existentes (Rate Monotonic yEDF) para obtener la mejor eficiencia y menor perdidade plazos durante la ejecucion del mismo.

Como meta final nos proponemos obtener un am-biente de desarrollo de sistemas de tiempo real, endonde sea posible disenar este tipo de tareas en for-ma visual. Actualmente nos encontramos en las etapasfinales de desarrollo de este ambiente.

Referencias[1] A. Burns and A. Wellings. Real-Time Systems and

programming languages, Addison-Wesley, April, 1997.[2] G. Buttazzo. Hard Real-Time Computing Systems.

Predictable scheduling algorithms and applications.Kluwer Academic, 1997.

[3] P. Gai, L. Abeni, M. Giorgi, G. Buttazzo. A New KernelApproach for Modular Real-Time System Development.Proceedings of the 13th IEEE Euromicro conference onReal-Time Systems, June 2001, Delft, NL.

[4] J. W. S. Liu. Real-Time Systems. Prentice Hall, PrimeraEdicion, Junio 15, 1997.

[5] C. L. Liu and W. Layland. Scheduling algorithmsfor multiprogramming in hard real-time environment.Journal of the Association for Computing Machinery,2:46-61, 1973.

[6] P. Meja Alvarez. Sistemas operativo en tiemporeal para multiples procesos (sopco). IV CongresoLatinoamericano de Control Automatico, Noviembre,1990.

[7] P. Mejia Alvarez. Sistemas en Tiempo Real. Notas delcurso de Sistemas en Tiempo Real, 2001.

[8] K. Gosh, B. Mukherjee, K. Schwan. A Survey of Real-Time Operating Systems. Tech Report. GIT-CC-93/18.

College of Computing, Georgia Institute of Technology.Feb 1994.

[9] A. Silberschatz and P. B. Galvin. Operating SystemConcepts. Addison Wesley, 1994.

[10] R. Yerraballi. Real-Time operating systems: An ongoingreview. Proceedings of 21st IEEE Real-Time Sympo-sium, WIP sectione Systems, Orlando Florida, 2000.

[11] K. M. Zuberi and K. G. Shin. Emeralds: A microKer-nel for embedded real-time systems. In proceedings ofIEEE Real-Time Technology and Applications Sympo-sium PP.241-249, June , 1996.