Estructuras de Datos, Sistemas Operativos en Tiempo Real y Automatización Industrial

Estructuras de Datos: Árboles

Un árbol es una estructura no lineal en la que cada nodo puede apuntar a uno o varios nodos. Un árbol ordenado, en general, es aquel a partir del cual se puede obtener una secuencia ordenada siguiendo uno de los recorridos posibles del árbol: inorden, preorden o postorden.

Existen varios tipos de árboles ordenados, entre los que veremos los árboles binarios de búsqueda (ABB) que son árboles de orden 2 que mantienen una secuencia ordenada si se recorren en inorden.

Preorden: Siempre a la izquierda: A, B, D, E, C, F, G
Inorden/Simétrico: Siempre abajo a la izquierda: D, B, E, A, F, C, G (se da en orden ascendente en ABB)
Postorden: Primero izquierda, luego derecha, luego raíz: D, E, B, F, G, C, A

Sistemas Operativos en Tiempo Real (SOTR)

Se clasifican en:

Críticos (Hard RTS): Deben ser ultrafíables.
No críticos (Soft RTS): Para λ fallos/hora, media de tiempo entre averías MTTF=1/λ. Si MTTF>10⁹, se consideran sistemas ultrafíables.

Requisitos de los SOTR

Determinismo: Tendencia que tiene el sistema a realizar una determinada acción en un tiempo predefinido. El minimizar el tiempo de respuesta a interrupciones garantiza un mayor nivel de determinismo.
Capacidad para responder a eventos rápidamente: Distinguiendo entre sucesos síncronos y asíncronos. Necesita una rutina de interrupciones para dar una respuesta “inmediata” a los sucesos asíncronos. Requiere que el desalojo y realojamiento de procesos de la CPU se haga con rapidez.
Control del sistema por parte del usuario: De modo que los usuarios puedan conmutar entre distintos modos de ejecución. Por ejemplo, un operario que acciona un botón de emergencia de una máquina.
Gestión de prioridades: En los sistemas operativos tradicionales la prioridad es dinámica, el propio sistema operativo va incrementando o decrementando la prioridad conforme pasa el tiempo. En los SOTR la prioridad debe ser estática con prioridades determinadas, al menos para varios procesos especialmente críticos. Las interrupciones procedentes del exterior tienen una prioridad fija, que no depende de tiempos de espera o ejecución. Además, se ha de analizar si la tarea se realiza según los plazos (seguimiento preventivo y predictivo) y cómo interfiere con las demás.
Fiabilidad: En caso de fallo hardware ha de haber una solución de tipo software. Deben estar contempladas todas las respuestas que daríamos a cada uno de los posibles fallos que se pudiesen dar.
Gestión de Memoria: Ha de ser más estricta que en los sistemas operativos tradicionales. Cuanta mayor facilidad se trata de dar al usuario mayor va a ser el kernel. En los SOTR el kernel debe ser lo menor posible.
Comunicación entre tareas: Debe ser muy rápida. Suele ser explícita, la tiene que hacer el usuario.
Código Reentrante: Se refiere a la posibilidad de que dos procesos puedan emplear un mismo código de programa, sin tener que tener una copia del mismo para cada uno y sin que haya problemas de interferencias entre ellos al manejar el mismo código.
Tamaño reducido de código: Conviene que el repertorio de rutinas empleado sea lo menor posible, a costa de mayor coste de programación por parte del usuario, de modo que se minimice el número de primitivas y el kernel.
SOTR distribuidos: Se trata de minimizar los tiempos de respuesta por parte de la red: buses de campo, redes industriales, han de minimizar el tiempo desde que se recoge algo en un sensor hasta que llega a un actuador para ejecutar la orden que corresponda, pasando por el gestor de la red. Otros problemas son considerar que puede haber sobrecarga en la red y problemas de sincronización de los relojes de los distintos elementos del sistema distribuido.

Programación Concurrente

Productor-consumidor: Paradigma de procesos cooperativos, el proceso productor produce información que es consumida por un proceso consumidor. Ejemplo: un programa de impresión produce caracteres que son consumidos por el controlador de la impresora.

Concurrencia, condición de competencia, exclusión mutua, sección crítica.

Una forma de lograr la exclusión mutua podría ser inhabilitar las interrupciones. Pero cuidado, las interrupciones son fundamentales, son el corazón del software y hardware. Si son inhabilitadas durante demasiado tiempo, el sistema fallará en la respuesta a los sucesos de hardware y la conmutación entre tareas no funcionará. Cuando existe más de un procesador en el sistema no se garantiza la exclusión mutua puesto que el otro procesador no está interrumpido. Al código de usuario no se le debe permitir desactivar las interrupciones.

El desactivar las interrupciones es una solución razonable para la exclusión mutua sólo en las siguientes condiciones: para secciones de código cortas, sobre sistemas monoprocesador, para el mismo sistema operativo.

Planificación en Sistemas de Tiempo Real (STR)

La planificación (scheduling) consiste en gestionar el uso de los recursos del sistema con el fin de garantizar los requisitos temporales de las tareas. El componente del sistema que hace esto es el planificador (scheduler) – para ello utiliza un algoritmo de planificación.

Esquemas de planificación:

Dirigida por tiempo
Turno circular (FIFO)
Planificación por prioridades
Con o sin desalojo
Prioridades fijas y variables

Planificación Cíclica

De esta forma se minimizan los cambios de contexto. Es fácil diseñar un planificador para una tarea conociendo el peor caso. La ventana de tiempo tiene que ser suficientemente pequeña para que su constante de tiempo sea menor que la de la planta pero suficientemente grande para contener las tareas a ejecutar. Las tareas se van ejecutando siempre en el mismo orden. Cada ventana de tiempo se repite indefinidamente, como por ejemplo, en los autómatas programables.

Una de las ventajas de este algoritmo radica en su simplicidad (no existe un sistema operativo propiamente dicho), siendo fácilmente implementable con muy poco código y, por tanto, muy eficiente en tiempo de ejecución. Otra ventaja es la predecibilidad absoluta derivada de que los instantes de ejecución de las tareas son fijos y conocidos, lo que además permite asegurar la planificabilidad del sistema desde el momento de la construcción de la tabla.

Inconvenientes: Por otro lado, sus principales inconvenientes son su rigidez (un pequeño cambio en una tarea puede obligar a cambiar toda la tabla), ineficiencia a la hora de gestionar eventos aperiódicos. No hay posibilidad de comunicación con eventos externos, por lo que no es posible el tratamiento por interrupciones: la interrupción ha de esperar a su ventana de tiempo. No hay desalojo, por lo que si una tarea entra en un bucle infinito, no desocupará nunca la CPU.

Pirámide de la Automatización Industrial

Capa 0. Sensores y actuadores: Esta capa es la más cercana a los procesos y las máquinas, empleada para captar y traducir las señales de los sensores y aplicar mediante actuadores las señales de control a los procesos.
Capa 1. Control automático: Esta capa consiste en los sistemas de control y monitorización, que gestionan los actuadores empleando la información del proceso dada por los sensores.
Capa 2. Control supervisado: Esta capa lleva el sistema de control automático estableciendo el objetivo al controlador.
Capa 3. Control de producción: Controla la producción, reserva de recursos, tareas en maquinaria, gestión del mantenimiento, etc.
Capa 4. Control de empresa: Este nivel trata menos del aspecto técnico y está más enfocado al aspecto comercial tal como abastecimiento, demanda, flujo de caja, marketing.