Alejandro L. Veiga

El estudio de los sistemas de tiempo real es una rama relativamente nueva de la ingeniería. Los primeros trabajos que mencionan estos términos tal cual se los utiliza en este capítulo son del la década del 80 [Stankovic, 1985, 1987]. Se trata, básicamente, de la reunión de varias técnicas preexistentes de análisis y diseño, con el propósito de organizar el desarrollo de sistemas compuestos por una combinación de hardware y software. El objetivo fundamental es que dicho desarrollo resulte en sistemas robustos y confiables, con un óptimo aprovechamiento de los recursos. Utiliza un enfoque diferente, con los mismos objetivos.

Conceptos básicos

En primera instancia se procede a presentar un conjunto de definiciones necesarias para entender el significado de la expresión sistemas de tiempo real [Laplante, 1992]:

Un sistema es una caja negra que tiene un grupo de una o más entradas y un grupo de una o más salidas.

Este sistema es determinístico si para cada estado y cada conjunto de entradas pueden ser determinados un único conjunto de salidas y el próximo estado del sistema.

El tiempo entre la presentación de un conjunto de entradas a un sistema y la aparición de todas las salidas asociadas se llama tiempo de respuesta del sistema.

Un sistema en falla es un sistema que no puede satisfacer uno o más de los requisitos presentados en la especificación del sistema.

Un sistema de tiempo real puede definirse, entonces, como un sistema que debe satisfacer restricciones explícitas en el tiempo de respuesta o arriesgarse a severas consecuencias, incluida la falla. Por lo tanto un sistema de tiempo real es un sistema que responde a un estímulo externo dentro de un tiempo especificado. Su eficiencia no solo depende de la exactitud de los resultados de cómputo, sino también del momento en que los entrega. La predictibilidad es su característica principal. A diferencia de los sistemas tradicionales, que tienden a distribuir en forma equitativa los recursos disponibles entre las diferentes tareas a ejecutar, los sistemas de tiempo real deben asegurar la distribución de recursos de tal forma que se cumplan los requerimientos de tiempo.

Los sistemas de tiempo real pueden dividirse en dos tipos diferentes, en función de su severidad en el tratamiento de los errores que puedan presentarse:

Sistemas de tiempo real blandos o Soft real-time systems: pueden tolerar un exceso en el tiempo de respuesta, con una penalización por el incumplimiento del plazo.

Sistemas de tiempo real duros o Hard real-time systems: la respuesta fuera de término no tiene valor alguno, y produce la falla del sistema.

La idea de sistema de tiempo real no debe asociarse únicamente con la velocidad de respuesta del sistema. En cambio, tiempo real implica sí necesariamente que los tiempos de respuesta estén acotados. Debe conocerse exactamente el tiempo que le tomará al sistema responder a un determinado evento. Este tiempo debe ser invariable, fundamentalmente, y además debe ser lo suficientemente rápido como para no producir una falla, por supuesto.

Si bien los primeros trabajos en sistemas de tiempo real se enfocaron a arquitecturas simples y dedicadas, los actuales sistemas de computadoras de propósitos generales y sus respectivas aplicaciones se están transformando en sistemas complejos que generalmente requieren los atributos de los sistemas de tiempo real: múltiples tareas coexisten en el sistema y cada una de ellas tiene diferentes requerimientos de tiempo; se requiere de mecanismos eficientes de comunicación entre las tareas; acceso simultáneo a dispositivos y redes; configurabilidad; adaptabilidad; etc.

El objetivo de este capítulo es presentar los aspectos a tener en cuenta en el análisis, tanto de sistemas dedicados como de sistemas de computadoras, bajo requerimientos de tiempo real.

Presentemos algunas definiciones más antes de asociar la anterior definición de sistema de tiempo real con la idea de sistemas de computadoras.

Llamaremos sistema de computadora a todo sistema que incluya un microprocesador, tanto una computadora personal, como un sistema cerrado.

Un sistema operativo es una colección especializada de programas que provee los mecanismos para interrelacionar los distintas componentes de un sistema de computadora.

Un embedded system, o sistema dedicado, es un software utilizado para controlar un hardware determinado que es parte de un sistema mayor. Generalmente se trata de sistemas cerrados en los cuales el usuario solo tiene acceso a un conjunto limitado de funciones, o a ninguna. Estos sistemas tienen un conjunto específico de tareas asignadas que no puede modificarse si no es por medio de una reprogramación total. Un ejemplo clásico de un embedded system es el software de un microcontrolador que es parte de una planta, y que está a cargo, por ejemplo, de controlar la temperatura de la misma.

Un sistema operativo de propósitos generales difiere de un embedded system en que no tiene asignado un único conjunto de tareas a realizar. Puede ser reprogramado completamente por el usuario. Tal es el caso de una PC con sistema operativo UNIX, con un programa ejecutándose. Este sistema operativo permite ejecutar tareas tan disímiles como un procesador de texto o un control de temperatura.

Debe aclararse que en lo que sigue se hace referencia a sistemas de computadora con un único microprocesador, dejándose las estructuras multiprocesador para un análisis posterior.

Sistemas multitarea

Las aplicaciones de tiempo real deben interaccionar, generalmente, con dispositivos externos tales como sensores y actuadores, además del correspondiente monitor, teclado y disco rígido. Estas interacciones con dispositivos externos tienen la particularidad de que están sucediendo todas simultáneamente. La misión de la aplicación es proveer una respuesta adecuada, a través de sus salidas, a cada una de las entradas, todas al mismo tiempo.

¿Cómo debe entonces estructurarse la aplicación para cumplir con dichos requerimientos? Existen unas pocas alternativas encabezadas por dos estructuras básicas: el gran loop o la estructura multitareas.

La primera opción maneja todos los eventos secuencialmente, en un orden predeterminado, dentro de una tarea única que se repite cíclicamente. Es la forma más simple de estructurar una aplicación, pero puede complicarse su diseño cuando el número de eventos a manejar es muy elevado. En este caso, el programa de aplicación debe encargarse de recorrer las múltiples tareas. Esto resulta en programas complicados y difíciles de mantener.

La segunda opción tiene, en cambio, al sistema operativo como protagonista. éste se encarga de emular un entorno de ejecución para diferentes tareas que se ejecutan independientemente una de la otra. Cada tarea dispone de un cierto tiempo de acceso a los recursos, administrado por el sistema operativo. En este tipo de sistemas, el programador escribe las tareas a realizar en programas diferentes, más simples. El sistema operativo es el encargado de hacer que todos estos programas se ejecuten en un único microprocesador. En este tipo de sistemas debe procederse cautelosamente al asignarse el número de tareas, ya que la emulación a cargo del sistema operativo significa una sobrecarga para el sistema de computadora.

En el campo del tiempo real, tanto los sistemas operativos de propósitos generales como los embedded systems, deben proveer la capacidad de realizar múltiples tareas simultáneamente, sin que esto signifique una complicación excesiva para el programador. Este tipo de sistemas operativos se denomina, en forma general, sistemas operativos multitarea.

Analizando el problema de ejecutar varias tareas simultáneamente con un poco más de profundidad, puede verse que un sistema operativo multitarea debe proveer al menos tres funciones específicas, relativas a la administración de dichas tareas (además del manejo de memoria y control de dispositivos de hardware, responsabilidad irrenunciable de todos los sistemas operativos, multitarea o no):

Scheduler de tareas: es una tarea adicional, de mayor jerarquía que las demás, que se encarga de determinar en qué orden se ejecutará el resto de las tareas presentes en el sistema.

Dispatcher de tareas: toma los recaudos necesarios para comenzar una tarea. Esto significa preservar el estado de los recursos que la tarea anterior estuviera utilizando en el momento de comenzar una nueva.

Comunicación: El sistema operativo debe proveer algún mecanismo de comunicación y sincronización entre los diferentes procesos que se están ejecutando simultáneamente.

El kernel o núcleo del sistema operativo es la porción más pequeña de sistema operativo que provee esas tres funciones.

Cada una de estas tres funciones del kernel multitarea está asociada a un problema diferente. Y dichos problemas tienen diferentes soluciones. Por ejemplo, si se dispone de tres procesos listos para ser ejecutados, ¿en qué orden deben ser ejecutados? ¿Cómo se reparte el tiempo de CPU entre los tres? ¿Se ejecuta primero el más urgente? Si se elige esta última opción ¿cuál es el más urgente? La toma de este tipo de decisiones está a cargo del scheduler del sistema operativo y son muy diversas las estrategias que pueden utilizarse. Más adelante se describen las más importantes.

Pero ese no es el único problema que debe afrontarse al diseñar un sistema operativo multitarea. Si la misma CPU es utilizada por varios programas de usuario diferentes, y suponiendo que dichos programas se ejecutan en el orden indicado por el scheduler, al interrumpirse uno de los programas para ejecutar otro el kernel debe encargarse de guardar toda la información necesaria, tal que el programa desplazado pueda ser retomado luego. Esta es la misión del dispatcher. Generalmente éstos se implementan utilizando para cada tarea en ejecución una estructura de datos llamada TCB (Task Control Block). Esta estructura contiene todos los datos asociados a una tarea, que son de relevancia para el sistema operativo, como por ejemplo un número de identificación, el estado de los registros del microprocesador en el momento de ser desplazada, un puntero a la última operación ejecutada del programa, etc.

Por último, otro problema que debe resolverse en un sistema operativo multitarea, es la sincronización y concurrencia. ¿Qué sucedería si dos programas de usuario que se ejecutan compartiendo la CPU a intervalos de tiempo, decidieran acceder a un recurso único de hardware simultáneamente, como por ejemplo una impresora? Para ello, un sistema operativo de este tipo debe proveer los mecanismos necesarios para administrar los recursos compartidos de una forma ordenada. Este tipo de mecanismos es utilizado también para sincronizar tareas entre sí, y se describen con profundidad mas adelante.

Como puede verse, la complejidad de un sistema operativo multitarea es bastante grande. El kernel debe encargarse de las tareas mencionadas, además de la administración de memoria y los manejadores de dispositivos (drivers). Por lo tanto, la utilización de un sistema tan complejo lleva apareada una sobrecarga del sistema, ya que una buena parte de la CPU debe utilizarse para la toma de decisiones y administración de las múltiples tareas. Pero esto no es una desventaja. Si se utiliza un sistema operativo que no provee estos mecanismos, solo podrá realizarse una tarea con una CPU. Y si en cambio se desean ejecutar varias tareas con éste, el programador de una aplicación se verá en la obligación de implementar por sí mismo los mecanismos de scheduling, dispatching y comunicación, cada vez que escriba una aplicación.

Por lo tanto, si bien los sistemas operativos multitarea son un poco más complicados de utilizar, esto se debe a la gran cantidad de herramientas que presentan al programador. Y en el momento de desarrollar una aplicación elaborada, resultan en definitiva más simples de operar.

A continuación se profundizará en las técnicas scheduling por ser uno de los puntos clave de los sistemas de tiempo real. Luego se mencionan los mecanismos de comunicación más comúnmente utilizados en los sistemas operativos standard. Posteriormente se presentan otros aspectos de importancia a tener en cuenta al analizar las propiedades de un sistema operativo de tiempo real, como relojes y entrada/salida en tiempo real. Para finalizar se presenta un resumen de las técnicas utilizadas actualmente para la asignación de prioridades entre las tareas.

Técnicas de scheduling

Los kernel de tiempo real utilizan diferentes estrategias en lo que se refiere a la implementación del scheduler de las tareas que deben realizarse simultáneamente. Estas estrategias varían según la aplicación que se le dé al sistema, la cual puede variar considerablemente en su concepción. Se analizan a continuación las diferentes estrategias que pueden emplearse en el diseño de un kernel de tiempo real.

i. Sistemas cíclicos o Polled loop systems

En este tipo de sistemas, una única instrucción de test repetitiva es utilizada para testear un flag que indica que un evento asociado ha ocurrido.

Este método reduce la complejidad de utilizar múltiples tareas, pero puede complicarse si se trata de manejar un gran número de interacciones simultáneas. El mantenimiento de estos sistemas suele ser complicado, ya que se debe ser muy cauteloso al realizar una modificación.

Existe solo una tarea: la que verifica los flags y si alguno está activo, ejecuta una tarea asociada. Cuando esta tarea finaliza, se retoma la verificación de los flags. Por lo tanto no es necesario un scheduling ni comunicación entre tareas. Simplemente verifica secuencialmente una serie de flags, y si están activados ejecuta las tareas asociadas.

El tiempo de respuesta del kernel a un determinado evento es simple de calcular: debe suponerse el peor caso: cuando se activa un flag, están activos todos los demás y la verificación está haciéndose en el flag inmediato posterior en la secuencia. El tiempo de respuesta ante la presencia del flag correspondiente no es constante.

En realidad esta implementación no es multitarea. Ejecuta sólo una tarea a la vez y para realizar la próxima debe esperar que termine la actual. Esto puede ser una buena solución en sistemas rápidos que realicen tareas simples (sistemas sobredimensionados). En general, pueden obtenerse mejores tiempos de respuesta con las implementaciones que se describen a continuación, en las cuales surge la idea de múltiples tareas ejecutándose simultáneamente.

Debe aclararse nuevamente que estamos hablando acerca de sistemas de computadora que incluyen sólo un microprocesador. Esto quiere decir que sólo una instrucción de código de máquina puede ejecutarse simultáneamente. Al referirnos a múltiples tareas simultáneas, nos referimos a tareas que son interrumpidas para realizar otras tareas, y que luego son retomadas.

ii. Sistema multitarea cooperativo

Esta es una forma de aproximarse a la ejecución simultánea de varias tareas. Se trata de un esquema en el cual dos o más tareas son divididas en estados o fases. Las llamadas al dispatcher central se hacen después que cada fase ha concluido, o sea que una tarea entrega voluntariamente los recursos a otra cuando ha concluido una fase. Este procedimiento requiere de una programación muy cautelosa y hay veces que no es simple subdividir las tareas en fases. Este tipo de sistemas es muy sensible a la presencia de aplicaciones “maliciosas“ que acaparen los recursos del sistema, sin cooperar.

iii. Sistemas basados en interrupciones

Primero un par más de definiciones:

Un evento es un suceso que hace que el program counter cambie no secuencialmente. Se trata de un cambio del control de flujo.

Una interrupción es una señal de hardware que inicia un evento.

El trabajo basado en interrupciones es una técnica de implementación de sistemas multitarea en la cual las tareas se ejecutan simultáneamente, administradas por un control central. Cada tarea es una entidad separada e independiente, realizando un trabajo en particular, a su propia frecuencia.

En este tipo de sistemas, el programa principal no ejecuta ninguna tarea, simplemente un loop. El scheduling de las tareas es manejado por medio de interrupciones de software o de hardware, mientras que el dispatching es realizado por las rutinas de manejo de interrupción. Hay dos formas de utilizar esta técnica para administrar tareas. La primera es utilizar un timer para que cada cierto tiempo genere una interrupción que produzca un cambio de tarea. La otra forma es asociar cada evento a una interrupción externa.

La programación de las tareas es más simple que en los casos anteriores y por lo tanto más robusta. Debido a la normalización que significa tener un scheduler y un dispatcher, independientes de las tareas de usuario, los programas de aplicación resultan además muy portables. Debe mencionarse también que en este entorno es simple agregar un nuevo proceso, lo cual no repercute en problemas de sincronización. Pero los sistemas operativos multitarea son más costosos en lo que se refiere a utilización de memoria y requieren de una permanente toma de decisiones, durante el tiempo de ejecución. Son por ello más lentos.

Debe tenerse en cuenta que estamos haciendo referencia a interrumpir tareas que se están ejecutando, para realizar otra tarea y luego retomar la primera. Como ya se mencionó, para que la primer tarea pueda continuar ejecutándose, debe tenerse la precaución de preservar la información indispensable que existía antes de entregar el control a la segunda tarea (esta operación se denomina un context switch). La información preservada se denomina contexto y es almacenada en una estructura tipo stack. La mínima información indispensable que una tarea necesita para retomar su ejecución es la siguiente:

Contenido de los registros del procesador

Contenido del program counter

Contenido de los registros del coprocesador

Registros de página de memoria

Un punto importante que debe aclararse es el siguiente: si se depende del sistema operativo para realizar la administración de tareas, debe tenerse en cuenta que cada vez que se presente un evento estarán presentes las tareas asociadas al scheduling y el dispatching. Por lo tanto el tiempo de respuesta a interrupciones externas se verá desmejorado, ya que existe una sobrecarga debido al sistema operativo. Una medida utilizada para caracterizar las bondades de un sistema operativo en este aspecto es el tiempo de latencia, que se define como el tiempo que se demora entre la aparición de la interrupción y la ejecución de la primera instrucción asociada a ella.

Existen varias estrategias de scheduling que pueden utilizarse, basadas en el uso de interrupciones.

Sistemas de tiempo compartido (time slice): A cada tarea se le asigna una cantidad fija de tiempo durante la cual puede ejecutar. Se utiliza un reloj interno de la computadora para iniciar una interrupción con una tasa correspondiente a esa "rebanada" de tiempo. Cuando llega una de estas interrupciones se produce un context switch y se cambia a la tarea siguiente. Puede haber diferentes prioridades para las tareas, lo cual se maneja cambiando el ancho de la rebanada de tiempo que se le entrega a cada uno o la frecuencia con que se le entrega dicha rebanada. Nunca un proceso se queda sin tiempo de CPU. Estos sistemas garantizan una performance promedio de las tareas (sistemas probabilísticos). Tienen un muy buen desempeño como sistemas de propósitos generales, pero el tiempo que demora una tarea en completarse es muy dependiente del resto de las tareas presentes.

Sistemas preemptivos basados en prioridades: Estos sistemas utilizan un esquema preemptivo en lugar de un scheduler time slice. Se habla de preempt cuando una tarea de prioridad más alta es capaz de interrumpir la ejecución de una de prioridad más baja. Cada vez que una tarea de alta prioridad desea ejecutarse, interrumpe inmediatamente a la tarea de más baja prioridad que pudiera estar ejecutándose al momento de su arribo. Si la que se está ejecutando es de prioridad mayor, la tarea se pone en espera. Este tipo de scheduling es el más adecuado para sistemas de tiempo real, fundamentalmente cuando existen tareas breves de alta importancia. En el caso de la existencia de una tarea crítica se le asigna la más alta prioridad. Para ella, el tiempo de respuesta es solamente el del context switch. Por supuesto que este tipo de sistemas presenta una sobrecarga debido a la toma de decisiones del kernel. En este tipo de sistemas es posible predecir exactamente el tiempo que le toma a una tarea completarse (sistemas determinísticos). Un tema muy importante es el estudio de las diferentes técnicas de asignación de prioridades, tema que se trata al final del capítulo.

Sistemas tipo round-robin: la estrategia es similar a los del tipo preemptivo, con la diferencia que las tareas de igual prioridad se ejecutan dentro de un esquema de tiempo compartido.

iv. Sistemas foreground/background

Se trata de una mejora a los sistemas basados en interrupciones, donde se reemplaza al programa principal que no realiza ninguna tarea por una serie de procesos llamados de background o de fondo, que no son manejados por interrupciones. Estos procesos de background pueden ser interrumpidos en cualquier momento por los procesos de foreground, manejados por interrupciones. Los procesos de background pueden utilizar un esquema de polled-loop para realizar varias tareas. Esta es una solución muy adecuada para embedded systems.

En sistemas más sofisticados puede utilizarse un esquema time slice para los procesos del background y un esquema preemptivo para los del foreground. Existen actualmente sistemas operativos de tiempo real con extensiones para manejar complicados device drivers, redes, etc. Para implementar este tipo de sistemas operativos de utiliza una estructura tipo Task Control Block como se mencionó anteriormente.

Mecanismos de coordinación entre tareas

Se introducen a continuación los posibles mecanismos previstos por diferentes sistemas operativos para proveer de comunicación y sincronización a los múltiples procesos activos. Se trata de un tema importante en cualquier sistema multitarea pues está relacionado directamente con el problema de que varias tareas compartan un mismo recurso (llamado también problema de exclusión mutua).

Existe una gran cantidad de mecanismos de coordinación en el amplio espectro de sistemas operativos disponibles. Ninguno de ellos implementa la totalidad de los mecanismos descriptos a continuación. Estos mecanismos se diferencian en la cantidad de programación necesaria para utilizarlos, en la flexibilidad del servicio que prestan, la velocidad, confiabilidad y funcionalidad. La clasificación que sigue a continuación es una recopilación de la escasa bibliografía referida al tema. Debe aclararse que la diferencia entre un mecanismo de comunicación y otro es a veces muy sutil.

Sin embargo, en general, existen cuatro categorías diferentes, cada una con características propias: variables globales y memoria compartida, mensajes y mailboxes, semáforos y mutexes, y por último señales. A continuación se presentan los aspectos fundamentales de cada una de estas categorías.

i. Variables globales y memoria compartida

Varios mecanismos pueden ser utilizados para pasar datos entre procesos en un sistema multitarea. La forma más simple y rápida es la utilización de variables globales o zonas de memoria compartida por dos o más procesos. Si bien son consideradas contrarias a un buen diseño de software, son muy utilizadas en operaciones que requieren alta velocidad. Se trata de mecanismos de muy bajo nivel.

Uno de los problemas relacionados con las variables globales es que una tarea de alta prioridad puede remover a una de prioridad más baja en el transcurso de la escritura, produciendo un dato incorrecto. Para evitar esta situación, deben protegerse con algún mecanismo adicional, como semáforos o mutexes. Por lo tanto son de implementación complicada.

Los distintos sistemas operativos implementan diferentes métodos de utilización de zonas de memoria compartida. Los kernel se encargan de presentar estas zonas con formatos similares a los archivos.

ii. Mensajes y mailboxes

La forma más general y abstracta de comunicación es el intercambio de mensajes. Un mailbox es una zona de memoria acordada por dos tareas para el intercambio de datos. Estas tareas dependen del scheduler para ser habilitados a escribir en esa zona a través de la operación write o send, o ser habilitados a leer con la operación read o receive. La diferencia entre utilizar receive o simplemente hacer un polling del mailbox hasta que el mensaje se haga presente, es que la tarea es suspendida hasta que el nuevo dato aparece. Por lo tanto no se desperdicia tiempo verificando el mailbox.

Con este mecanismo pueden intercambiarse tanto flags que protegen un recurso, datos, o bien punteros a zonas de memoria donde residen los nuevos datos. Incluso pueden utilizarse para implementar los mecanismos de sincronización descriptos en el punto siguiente.

Pipes y FIFOs

Se trata de mecanismos de comunicación entre procesos manejados por el kernel tal como si fueran archivos. Un pipe es un arreglo de dos descriptores de archivos, uno de escritura y otro de lectura. Se lee y se escribe en ellos de la misma forma que en archivos: con read y write. Estos descriptores de archivo son heredados por los procesos hijo, por lo tanto son la forma de comunicación entre procesos creados por nuestra aplicación. Su creación es muy simple: utilizando la llamada al sistema pipe se crean los dos descriptores de archivos y los datos se acceden de tal forma que el primer dato en entrar es el primero en salir.

Un FIFO es similar a un pipe, pero con un nombre en el sistema de archivos. Esto significa que cualquier proceso con los permisos adecuados puede acceder al pipe, sin necesidad de heredar el descriptor. Los FIFOs se abren con open, para solo lectura o solo escritura, dependiendo que extremo se desee. Pero primero deben ser creados, para lo que existe una llamada al sistema. También se denominan named pipes.

Los pipes y FIFOs tienen algunas desventajas. Pueden mencionarse, por ejemplo, que no puede darse prioridades a los mensajes, que no existe control sobre la estructura del pipe o que el tipo de datos es no estructurado.

Message queues

Los problemas presentes en los pipes, mencionados anteriormente, son en parte subsanados por la estructura de cola de mensajes o message queue. éstas tienen una estructura de mensaje más marcada y dichos mensajes pueden ser priorizados. Además se dispone de cierto control sobre la cola de mensajes. Los mensajes pueden ser enviados sin conocer el destinatario. Tiene la ventaja, frente a la memoria compartida, que pueden implementarse mensajes sobre sistemas distribuidos. Incluso existe la posibilidad de que un proceso sea notificado cuando un mensaje fue puesto en la cola, sin necesidad de que éste pregunte.

El kernel es quien implementa estas facilidades, pero debe aclararse que en distintos sistemas operativos existen diferentes implementaciones de estas colas, no todas con las mismas propiedades, funcionalidad y performance.

Algunas limitaciones se mantienen. El tipo de comunicación está limitado al formato de cola; es complicado implementar un stack. Además su eficiencia es limitada, ya que el mensaje debe ser copiado desde el emisor al sistema operativo, y del sistema operativo al receptor; estas dos operaciones de copia consumen recursos, que son mayores cuanto más grande es el mensaje.

iii. Semáforos y mutexes

En sistemas multitareas un aspecto muy importante y crítico es el de los recursos compartidos y su implementación. En la mayoría de los casos, los recursos pueden ser utilizados por una sola tarea a la vez, y la utilización del recurso no puede ser interrumpida. Estos recursos se denominan serially reusable, e incluyen los periféricos, memoria compartida y la CPU. La CPU está protegida de utilizaciones simultáneas, pero el código que interactúa con el resto de dichos recursos no lo está. Ese código se denomina región crítica. Si dos tareas entran en una región crítica simultáneamente, un error catastrófico puede ocurrir. Esta situación se denomina colisión, y los sistemas operativos proveen diferentes mecanismos para evitarlas.

Semáforos binarios

Esta metodología de protección involucra una variable especial llamada semáforo S y dos operaciones posibles sobre éste (semaphore primitives) P(S) y V(S). Un semáforo es una posición de memoria que sirve como lock para proteger una sección crítica. La operación P se utiliza para setear el semáforo y la operación V para resetearlo. La primera se llama también operación de espera y la segunda, operación de señalización. El efecto de la operación P es suspender el proceso que requiere del uso del semáforo hasta que éste esté en “0“. La operación de señalización pone el semáforo en “0“. Esta técnica evita que más de un proceso ingrese en la sección crítica. En esta categoría puede incluirse la técnica de file locking.

Semáforos contadores

Con la técnica descripta anteriormente, el semáforo sólo puede tomar los valores “0“ o “1“. Con la técnica de semáforos contadores, cada operación de señalización incrementa en uno el valor del semáforo, que puede tomar cualquier valor entero positivo. La operación de espera decrementa el valor del semáforo, o suspende la ejecución si es cero, hasta que éste se incremente.

Mutexes y variables de condición

Los mutexes son mecanismos que proveen exclusión mutua (los procesos se excluyen unos a otros) para el acceso a una zona crítica. Suele sugerirse la idea de imaginar a la sección crítica como una habitación en la que solo puede entrar un proceso. El mutex es la puerta a dicha habitación, que puede ser trabada o destrabada. El proceso que traba la puerta (el mutex) es el único que puede destrabarla. Este concepto es diferente del semáforo. Los mutex tienen asociada la idea de dueño, mientras que los semáforos no.

Las variables de condición están asociadas a los mutexes. Imagínese la situación en que un proceso traba un mutex, entra a la sección crítica y se da cuenta de que una condición necesaria aún no ha sido satisfecha por otro proceso. Entonces debe destrabar el mutex y volver luego. Esperando por una variable de condición, el mutex se destraba y se espera la condición atómicamente, en una acción no interrumpible. Cuando el otro proceso satisface la condición necesaria, modifica la variable de condición, y despierta al primer proceso, que vuelve a trabar el mutex y ejecuta la acción pendiente, con la condición satisfecha.

Locks de lectura/escritura

Esta técnica se basa en que varios procesos pueden leer simultáneamente una zona compartida, pero si se desea escribir en dicha zona se debe esperar a que ésta esté libre de lectores. Con el mismo criterio, si hay un proceso modificando la zona compartida, los lectores que aparezcan serán bloqueados hasta que el primero termine su trabajo.

iv. Señales

Las señales son parte integral del entorno multitarea de los sistemas tipo UNIX. éstas son utilizadas con diferentes propósitos, como por ejemplo manejo de excepciones, notificación a los procesos de la ocurrencia de eventos asíncronos, eliminación de procesos en circunstancias anormales y comunicación entre procesos.

Una señal es el equivalente de software de una interrupción. Cuando un proceso recibe una señal, esto indica que algo ha sucedido que requiere su atención. Como un proceso puede enviar una señal a otro, ésta puede utilizarse como un método de comunicación. Desde este punto de vista son lentas, limitadas e interrumpen a los procesos asíncronamente, lo que requiere de un tratamiento especial por parte del receptor.

Las señales pueden ser enmascaradas, lo que les da una cierta flexibilidad en la utilización como comunicación entre procesos.

Al ser un mecanismo standard de todos los sistemas tipo UNIX, la información al respecto es abundante y no se tratará este tema con detenimiento. En el capítulo de bibliografía, en la sección de programación se presentan varios textos que se encargan del tema.

Otros aspectos de importancia en sistemas de tiempo real

Además de la estrategia de scheduling necesaria para administrar las tareas, y de la comunicación necesaria entre dichas tareas, hay otros aspectos a tener en cuenta en el momento de analizar las propiedades de tiempo real de un sistema operativo. Se presentan a continuación algunos puntos importantes respecto de la administración de memoria, relojes y entrada/salida del sistema.

Memory lock

En sistemas de tiempo real debe evitarse que las páginas de memoria (en un sistema de memoria virtual) asociadas a una tarea con restricciones estrictas de tiempo sean enviadas al disco por falta de memoria para otras tareas (este fenómeno se denomina swapping). Esto produciría un incremento indeterminado en el cambio de contexto, ya que no puede saberse a priori si las páginas fueron enviadas a disco o no. Para ello, la mayoría de los sistemas de tiempo real proveen facilidades para evitar que esto ocurra. Los sistemas más inteligentes proveen dos formas de trabar en la memoria. La primero hace un lock del proceso completo en memoria, pero en el caso de que se supere la capacidad de memoria disponible, se dispone de una segunda opción que permite hacer un lock en memoria solo de las porciones críticas del proceso.

Relojes y timers de tiempo real

Como es lógico pensar, este es un punto muy importante en sistemas de tiempo real. Es fundamental que el sistema provea una base de tiempo adecuada para la sincronización interna de los procesos presentes. Debe aclararse aquí la diferencia entre reloj y timer. El primero es simplemente un contador que provee una base de tiempo, y el segundo es un contador que llegado a cierto estado, es capaz de notificar que esto ha sucedido. Para la implementación de un timer es necesario un reloj.

Un sistema de tiempo real debe ser capaz de medir internamente el tiempo con la resolución y precisión adecuada para el caso de aplicación. Es deseable también que el sistema sea capaz de reconocer cuándo un timer ha expirado varias veces (timer overrun) y que sea también capaz de generar una señal standard ante la expiración normal de un timer.

Un aspecto importante es la capacidad del sistema de sincronizar su reloj interno con el entorno, o sea con el “tiempo real“. De la misma manera, en un sistema distribuido, es necesaria una adecuada sincronización entre los diferentes nodos. Los principales problemas que se presentan son los drifts debido a la temperatura e incluso la falla de los relojes, problemas que deben ser subsanados para evitar la falla total del sistema. Uno de los métodos utilizados es el empleo de una base de tiempo global, a la cual tienen acceso todos los nodos.

Otro método es la implementación de un promedio entre los relojes presentes en el sistema. Para ello se utilizan algoritmos que prevén los retardos debido a la comunicación y posibles relojes maliciosos. Uno de los algoritmos más utilizados es Fault tolerant average algorithm de Ochsenreiter y Kopetz, de 1987 [Buttazzo, 1997], que se encuentra disponible como un elemento de hardware que puede incluirse en el sistema.

Entrada/salida en sistemas de tiempo real

Es fundamental que, una vez realizado el procesamiento en tiempo real, la interacción con los dispositivos externos sea también acotada en tiempo. Es importante que el sistema operativo disponga de un sistema de entrada/salida sincrónico. Por ejemplo, el sistema de archivos debe tener acotados los tiempos de respuesta, si se desea que dichos archivos sean de “tiempo real“.

Para la transmisión de datos entre el sistema de tiempo real y los diversos sensores y actuadores que pueden estar presentes en el sistema (incluso para la comunicación de datos entre distintos nodos de un sistema distribuido) existen diferentes técnicas de buses de tiempo real, que permiten disponer de sensores inteligentes. éstos no solo transmiten el dato adquirido, sino que además envían la información acerca del momento en que dicho dato fue tomado (por ejemplo Fieldbus).

Dentro de los protocolos de comunicación que disponen de la capacidad de acotar los tiempos de transmisión pueden mencionarse el protocolo PAR (Positive Acknowledge or Retransmit), Implicit Flow Control, CSMA/CD (Carrier Sense Multiple Access/Collision Detection), CAN (Control Area Network), Tokenbus (por ejemplo Profibus), Central Master, y TDMA-TTP (Time Division Multiple Access – Time Triggered Protocol).

BIBLIOGRAFIA

Bach, Maurice. The design of the UNIX operating system. Prentice Hall. 1986.

Barabanov, M. y V. Yodaiken. Introducing Real Time Linux. Linux Journal # 34. 1997.

Dibble, Peter. OS-9 Insights. Advanced Programmers Guide. Microware Systems Corp. 1988.

Dijkstra, Edsger. Cooperating sequential processes. Technical Report EWD-123, Eindhoven, Holanda. Technological University. 1965.

Epplin, J. Linux as an Embedded Operating System. Embedded Systems Programming. Octubre 1997.

Gallmeister, Bill O. POSIX.4 Programming for the real world. O'Reilly & Associates, 1995.

Hwang, K. y F. Briggs. Computer Architecture and Parallel Processing. Mc Graw Hill. 1984.

IEEE. Institute of Electrical and Electronic Engineers. Portable Operating System Interface (POSIX) - Part 1: System Application Program Interface (POSIX.1), and Amendment: Real time Extension (POSIX.4). Institute of Electrical and Electronic Engineers. 1-55937-061-0.

Laplante, Philip A. Real-Time Systems Design and Analisis. IEEE Press, 1992.

Leffler, Samuel J., Kirk McKusick, mike Karels y John Quarterman. The design and implementation of the 4.3 BSD UNIX Operating System. Addison-Wesley, 1990.

Markus, K. Linux POSIX.1b Compatibility. Linux Documentation Project. 1996.

Moses, J. Is POSIX Appropiate for Embedded Systems? Embedded Systems Programming. Julio 1995.

Oualline, Steve. Practical C. O'Reilly & Associates, Inc. 1993.

QNX Software Systems Ltd. QNX Operating System. 1996.

RTLinux Home Page. http://www.rtlinux.org. Referencias a las extensiones citadas pueden encontrarse en ftp://rtlinux.cs.nmt.edu/pub/rtlinux/v1/drivers.

Stankovic, John A. Real-Time and Embedded Systems. Departament of Computer Science, University of Massachusetts, Amherst, MA 01003. 1985.

Stankovic, John A. y Krithi Ramamritham. Tutorial Hard Real-Time Systems. IEEE Computer Society. 1987.

Stankovic, John A. Real-Time Computing. Departament of Computer Science, University of Massachusetts, Amherst, MA 01003. Abril de 1992.

Stankovic, John A. y Krithi Ramamritham. Advances in Real-Time Systems. IEEE Computer Society. 1993.

Stevens, W. Advanced Programming in the Unix Enviroment. Addison Wesley. 1992.

Tanenbaun, Andrew S. Sistemas Operativos. Diseño e implementación. Prentice Hall Inc. 1988.

Tanenbaun, Andrew S. Modern Operating Systems. Prentice Hall Inc. 1992.

Tanenbaun, Andrew S. Sistemas Operativos Distribuidos. Prentice Hall Inc. 1996.