Diseño De Sistemas Operativos De Tiempo Real.

Transcript

´ n y de Estudios Centro de Investigacio Avanzados del IPN ´ctrica Departamento de Ingenier´ıa Ele ´ n Computacio ´n Seccio Kernel de Tiempo Real para el Control de Procesos Tesis que presenta Oscar Miranda G´omez Para obtener el grado de: Maestro en Ciencias en la Especialidad de Ingenier´ıa El´ectrica Opci´on Computaci´on Asesores de la Tesis: Dr. Pedro Mej´ıa Alvarez Dr. Alberto Soria L´opez M´exico, DF Marzo del 2004. ´Indice general ´Indice General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . iv ´Indice de Figuras . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . vii ´Indice de Tablas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . xi 1. Introducci´ on 1 1.1. Motivaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2. Trabajo Propuesto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.3. Trabajos Relacionados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3 1.4. Sistemas Operativos de Tiempo Real Comerciales . . . . . . . . . . . . . . . 4 1.4.1. VxWorks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 1.4.2. RT-Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7 1.5. Sistemas Operativos de Tiempo Real Experimentales . . . . . . . . . . . . . 10 1.5.1. EMERALDS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10 1.5.2. S.H.A.R.K. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.5.3. Spring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.6. Objetivos de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.6.1. Objetivos Generales . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20 1.6.2. Objetivos Particulares . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.7. Organizaci´on de la Tesis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2. Sistemas de Tiempo Real 23 2.1. Definici´on de Sistema de Tiempo Real . . . . . . . . . . . . . . . . . . . . . 23 2.2. Aplicaciones de los Sistemas de Tiempo Real . . . . . . . . . . . . . . . . . . 24 2.3. Elementos de un Sistema de Tiempo Real . . . . . . . . . . . . . . . . . . . 25 i ii 2.4. Caracter´ısticas de los Sistemas de Tiempo Real . . . . . . . . . . . . . . . . 27 2.5. Clasificaci´on de los Sistemas de Tiempo Real . . . . . . . . . . . . . . . . . . 28 2.5.1. Sistemas de Tiempo Real Cr´ıticos (Hard Real Time Systems) . . . . 28 2.5.2. Sistemas de Tiempo Real Acr´ıticos (Soft Real Time Systems) . . . . 28 2.6. ¿Qu´e es un Sistema Operativo de Tiempo Real? . . . . . . . . . . . . . . . . 29 2.7. Proceso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.7.1. Definici´on de Proceso . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.7.2. Definici´on de Quantum . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.7.3. Par´ametros de un Proceso de Tiempo Real . . . . . . . . . . . . . . . 30 2.7.4. Estado del Proceso . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.7.5. Transiciones entre Estados . . . . . . . . . . . . . . . . . . . . . . . . 32 2.7.6. PCB (Process Control Block) . . . . . . . . . . . . . . . . . . . . . . 33 2.8. Componentes de un Sistema Operativo de Tiempo Real . . . . . . . . . . . . 34 2.8.1. Manejador de Procesos . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.8.2. Manejador de Memoria . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.8.3. Manejador de Reloj . . . . . . . . . . . . . . . . . . . . . . . . . . . . 37 2.8.4. Mecanismos de Sincronizaci´on y Comunicaci´on . . . . . . . . . . . . . 37 2.8.5. Manejador de Entradas/Salidas . . . . . . . . . . . . . . . . . . . . . 42 3. Planificaci´ on en Sistemas de Tiempo Real 45 3.1. Tareas de Tiempo Real . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 3.1.1. Clasificaci´on de las Tareas de Tiempo Real . . . . . . . . . . . . . . . 46 3.1.2. Tipos de Restricciones de las Tareas de Tiempo Real . . . . . . . . . 48 3.2. Definici´on del Problema de Planificaci´on . . . . . . . . . . . . . . . . . . . . 50 3.3. Clasificaci´on de Pol´ıticas de Planificaci´on . . . . . . . . . . . . . . . . . . . . 50 3.4. Planificador C´ıclico . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51 3.5. Planificadores Basados en Prioridades Est´aticas . . . . . . . . . . . . . . . . 53 3.5.1. Rate Monotonic (RM) . . . . . . . . . . . . . . . . . . . . . . . . . . 54 3.5.2. Deadline Monotonic (DM) . . . . . . . . . . . . . . . . . . . . . . . . 60 3.6. Planificadores Basados en Prioridades Din´amicas . . . . . . . . . . . . . . . 61 3.6.1. Earliest Deadline First (EDF) . . . . . . . . . . . . . . . . . . . . . . 61 iii 3.6.2. Least Laxity First (LLF) . . . . . . . . . . . . . . . . . . . . . . . . . 4. Dise˜ no del Kernel de Tiempo Real 63 65 4.1. Arquitectura General . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.1.1. Estructura General de las Primitivas . . . . . . . . . . . . . . . . . . 66 4.1.2. Estructura de los Procesos o Tareas . . . . . . . . . . . . . . . . . . . 67 4.1.3. Prioridades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.1.4. Procesos o Tareas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68 4.1.5. BCP de los Procesos en el Kernel . . . . . . . . . . . . . . . . . . . . 69 4.1.6. Estados de los Procesos en el Kernel . . . . . . . . . . . . . . . . . . 71 4.1.7. Transiciones entre Estados . . . . . . . . . . . . . . . . . . . . . . . . 72 4.1.8. Primitivas y Manejadores del Kernel . . . . . . . . . . . . . . . . . . 72 4.2. Primitivas . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2.1. Primitivas de Procesos . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.2.2. Primitivas de Tiempo . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.2.3. Primitivas de Sem´aforos . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.2.4. Primitivas de Buz´on . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.3. Manejadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3.1. Manejo de Registros . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.3.2. Manejo del Procesador . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.3.3. Manejo de Colas de Procesos . . . . . . . . . . . . . . . . . . . . . . 89 4.3.4. Manejo de Planificadores . . . . . . . . . . . . . . . . . . . . . . . . . 99 4.3.5. Manejo del Reloj . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 4.3.6. Manejo de Interrupciones . . . . . . . . . . . . . . . . . . . . . . . . 105 4.3.7. Manejo de Errores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.4. Configuraci´on e Inicializaci´on del Kernel . . . . . . . . . . . . . . . . . . . . 109 4.4.1. Configuraci´on del Kernel . . . . . . . . . . . . . . . . . . . . . . . . . 109 4.4.2. Inicializaci´on del Kernel . . . . . . . . . . . . . . . . . . . . . . . . . 110 4.5. Datos T´ecnicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.5.1. Tama˜ no . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.5.2. Tiempos de ejecuci´on del Kernel . . . . . . . . . . . . . . . . . . . . . 111 iv 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de Corriente Directa 113 5.1. Introducci´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 5.1.1. Introducci´on al Control . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.2. Sistemas de Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 5.2.1. Tipos de Retroalimentaci´on . . . . . . . . . . . . . . . . . . . . . . . 117 5.2.2. Implementaci´on Digital del Proporcional Derivativo . . . . . . . . . . 120 5.3. Motores y Amplificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 5.3.1. Motores de Corriente Continua . . . . . . . . . . . . . . . . . . . . . 122 5.3.2. Amplificadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.4. Arquitectura de la Aplicaci´on . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.5. Pruebas y Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 5.5.1. Prueba 1: Control PD con Fifo Round Robin . . . . . . . . . . . . . . 124 5.5.2. Prueba 2: Control PD con Rate Monotonic . . . . . . . . . . . . . . . 127 5.5.3. Prueba 3: Control PD con Earliest DeadLine First . . . . . . . . . . . 129 5.5.4. Prueba 4: Control PD con P´erdidas de Plazo . . . . . . . . . . . . . . 130 6. Conclusiones y Trabajo Futuro 133 6.1. Conclusiones . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 6.2. Trabajo Futuro . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 134 ´Indice de Figuras 1.1. Arquitectura de VxWorks . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.2. Arquitectura de RT-Linux . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8 1.3. Arquitectura de EMERALDS . . . . . . . . . . . . . . . . . . . . . . . . . . 11 1.4. Arquitectura de SHARK . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.5. Arquitectura de Spring . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 2.1. Sistema de Tiempo Real. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24 2.2. Elementos de un Sistema de Tiempo Real. . . . . . . . . . . . . . . . . . . . 26 2.3. Par´ametros de un Proceso de Tiempo Real . . . . . . . . . . . . . . . . . . . 31 2.4. Diagrama de estado de los procesos . . . . . . . . . . . . . . . . . . . . . . . 32 2.5. Bloque de Control de Procesos (PCB) . . . . . . . . . . . . . . . . . . . . . . 33 2.6. Cambio de Contexto. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 2.7. Operaci´on WAIT. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.8. Operaci´on SIGNAL. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.9. Operaci´on WAIT en sem´aforos sin bloqueo. . . . . . . . . . . . . . . . . . . . 41 3.1. Tareas Peri´odicas y Espor´adicas. . . . . . . . . . . . . . . . . . . . . . . . . . 47 3.2. Relaci´on de precedencia para cinco tareas. . . . . . . . . . . . . . . . . . . . 49 3.3. Clasificaci´on de los algoritmos de planificaci´on para sistemas de tiempo real. 51 3.4. Planificaci´on C´ıclica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53 3.5. Conjunto de tareas que no satisface la Ecuaci´on 3.2 y por lo tanto no es planificable. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.6. Conjunto de tareas que satisface 3.2 y por tanto es planificable. . . . . . . . 57 3.7. Conjunto de tareas que no satisface 3.2. Sin embargo, es planificable. . . . . 58 v vi 3.8. Puntos de Planificaci´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.9. Planificaci´on de las tareas de la tabla 3.7 bajo EDF. . . . . . . . . . . . . . . 62 3.10. Planificaci´on de tareas bajo el algoritmo LLF. . . . . . . . . . . . . . . . . . 63 4.1. Arquitectura del Kernel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66 4.2. Bloque de Control de Procesos en el Kernel. . . . . . . . . . . . . . . . . . . 70 4.3. Estados de los Procesos en el Kernel. . . . . . . . . . . . . . . . . . . . . . . 71 4.4. Primitivas de Procesos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 4.5. Primitivas de Tiempo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 4.6. Primitivas de Sem´aforo. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.7. Utilizaci´on de los sem´aforos en el Kernel. . . . . . . . . . . . . . . . . . . . . 81 4.8. Primitivas de Buz´on. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 4.9. Procedimientos del Manejador de Registros. . . . . . . . . . . . . . . . . . . 85 4.10. Procedimiento del Manejador del Procesador. . . . . . . . . . . . . . . . . . 88 4.11. Procedimientos del Manejador de Colas de Procesos. . . . . . . . . . . . . . 90 4.12. Colas de Procesos. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 90 4.13. Ejemplos del Comportamiento de la Cola de Procesos Retrasados. . . . . . . 94 4.14. Procedimientos del Manejador del Planificador. . . . . . . . . . . . . . . . . 100 4.15. Procedimientos del Manejador del Reloj. . . . . . . . . . . . . . . . . . . . . 103 4.16. Procedimientos del Manejador de Interrupciones. . . . . . . . . . . . . . . . 105 4.17. Procedimiento del Manejador de Errores. . . . . . . . . . . . . . . . . . . . . 107 5.1. Componentes B´asicos de un Sistema de Control. . . . . . . . . . . . . . . . . 116 5.2. Elementos de un Sistema de Control en Lazo Abierto. . . . . . . . . . . . . . 116 5.3. Sistema de Control de Marcha en Reposo en Lazo Cerrado. . . . . . . . . . . 117 5.4. Motor de Corriente Continua. . . . . . . . . . . . . . . . . . . . . . . . . . . 123 5.5. Arquitectura de la Aplicaci´on. . . . . . . . . . . . . . . . . . . . . . . . . . . 125 5.6. Control PD para cuatro motores con Fifo Round Robin. . . . . . . . . . . . 126 5.7. Gr´aficas en Tiempo Real Generadas en la Prueba 1. . . . . . . . . . . . . . . 126 5.8. Control PD para cuatro motores con Rate Monotonic. . . . . . . . . . . . . . 128 5.9. Gr´aficas en Tiempo Real Generadas en la Prueba 2. . . . . . . . . . . . . . . 128 vii 5.10. Control PD para cuatro motores con Earliest Deadline First. . . . . . . . . . 129 5.11. Gr´afica del Comportamiento de los Motores en EDF. . . . . . . . . . . . . . 130 5.12. P´erdidas de Plazo Ocurridas en la Prueba 4. . . . . . . . . . . . . . . . . . . 131 viii ´Indice de Tablas 3.1. Conjunto de tareas peri´odicas . . . . . . . . . . . . . . . . . . . . . . . . . . 52 3.2. Utilizaci´on m´ınima garantizada para n tareas . . . . . . . . . . . . . . . . . 55 3.3. Conjunto de tareas, la utilizaci´on total cumple con la condici´on 3.2 . . . . . 56 3.4. Conjunto de tareas armonico, es planificable . . . . . . . . . . . . . . . . . . 57 3.5. Conjunto de Tareas que no satisface 3.2. . . . . . . . . . . . . . . . . . . . . 59 3.6. Carga en el instante t . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.7. Conjunto de tareas, cuya utilizaci´on es del 82 % . . . . . . . . . . . . . . . . 62 4.1. Estructura de las Tareas o Procesos. . . . . . . . . . . . . . . . . . . . . . . 68 4.2. C´odigo del Proceso “Primer Tarea”. . . . . . . . . . . . . . . . . . . . . . . . 69 ´ 4.3. C´odigo del Proceso “Ultima Tarea”. . . . . . . . . . . . . . . . . . . . . . . . 69 4.4. Estructura del Bloque de Control de Procesos (BCP). . . . . . . . . . . . . . 71 4.5. Primitiva Activa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.6. Primitiva Elimina Proceso. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 74 4.7. Primitiva Fin de Ciclo de la Tarea. . . . . . . . . . . . . . . . . . . . . . . . 75 4.8. Primitiva Retrasa. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 4.9. Primitiva Revisa Proceso Retrasado. . . . . . . . . . . . . . . . . . . . . . . 77 4.10. Primitiva Crea Sem´aforo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 78 4.11. Primitiva Se˜ nal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 4.12. Primitiva Espera . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80 4.13. Primitiva que revisa si la Cola de Sem´aforos est´a vac´ıa. . . . . . . . . . . . . 80 4.14. Primitiva Crea Buz´on . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 82 4.15. Primitiva Env´ıa Mensaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 ix x 4.16. Primitiva Recibir Mensaje . . . . . . . . . . . . . . . . . . . . . . . . . . . . 84 4.17. Primitiva Crea Tarea . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.18. Primitiva Inicializa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86 4.19. Primitiva Inicializa Proceso . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.20. Primitiva Carga Primer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.21. C´odigo del Cambio de Contexto. . . . . . . . . . . . . . . . . . . . . . . . . . 89 4.22. Estructura utilizada para las colas de los procesos. . . . . . . . . . . . . . . . 91 4.23. Declaraci´on de la Cola de Procesos Bloqueados por Sem´aforo (CPBS). . . . . 92 4.24. Primitiva Siguiente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.25. Primitiva Busca Mayor. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94 4.26. Primitiva Inicializa Cola. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.27. Primitiva Inserta. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 95 4.28. Primitiva Saca . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.29. Primitiva Rota . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 4.30. Primitiva Elimina . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 97 4.31. Primitiva Arregla Cola . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 4.32. Primitiva Inserta a la Cola de Retrasados . . . . . . . . . . . . . . . . . . . 98 4.33. Primitiva Saca de la Cola de Retrasa . . . . . . . . . . . . . . . . . . . . . . 99 4.34. Primitiva Inicializa Cola de Retrasa . . . . . . . . . . . . . . . . . . . . . . . 99 4.35. Planificador FIFO ROUND ROBIN . . . . . . . . . . . . . . . . . . . . . . . 100 4.36. Planificador RATE MONOTONIC . . . . . . . . . . . . . . . . . . . . . . . 101 4.37. Planificador EARLIEST DEADLINE FIRST . . . . . . . . . . . . . . . . . 102 4.38. Primitiva que revisa si es v´alido el proceso a planificar . . . . . . . . . . . . 103 4.39. Primitiva Cambia Timer . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 104 4.40. Primitiva Normaliza Timer 105 . . . . . . . . . . . . . . . . . . . . . . . . . . . 4.41. Primitiva Interrupci´on del Teclado . . . . . . . . . . . . . . . . . . . . . . . 106 4.42. Primitiva Revisa Tecla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 106 4.43. Tama˜ no del Kernel. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 4.44. Tiempos de ejecuci´on de las primitivas del Kernel. . . . . . . . . . . . . . . . 112 5.1. Conjunto de Tareas Utilizadas . . . . . . . . . . . . . . . . . . . . . . . . . . 127 xi 5.2. Conjunto de Tareas Utilizadas en la Prueba 4 . . . . . . . . . . . . . . . . . 131 xii Cap´ıtulo 1 Introducci´ on En la actualidad el avance de la tecnolog´ıa ha permitido una miniaturizaci´on en los dispositivos electr´onicos y un incremento en la capacidad de procesamiento de estos dispositivos. Estos dispositivos se encuentran en general empotrados (embebidos) dentro de aplicaciones tales como tel´efonos celulares, PALM’s, computadoras industriales, robots, sat´elites, autom´oviles y tambi´en en distintos aparatos electro-dom´esticos. La mayor´ıa de estos dispositivos contienen un procesador y un peque˜ no sistema operativo empotrado el cual es capaz de controlar todo el hardware de manera eficiente. Debido a la naturaleza de estos dispositivos embebidos, en ocasiones se les demanda no solo un correcto y eficiente funcionamiento sino tambi´en un estricto cumplimiento de requerimientos temporales. A estos sistemas se les conoce como sistemas de tiempo real embebidos. En un sistema de tiempo real, el principal componente lo constituye el sistema operativo o Kernel. Un sistema operativo de tiempo real se ejecuta por lo general sobre un plataforma embebida (que puede ser un microcontrolador, un DSP o cualquier procesador convencional). Este sistema operativo debe ser capaz de controlar todos los recursos de hardware de la plataforma en que se encuentra y tambi´en de administrar todos los tiempos de ejecuci´on de las tareas de tiempo real. Normalmente este sistema operativo no maneja discos, memoria cache, DMA o complejos sistemas de redes de comunicaciones, debido a que su ejecuci´on debe ser predecible (debe ser posible estimar con exactitud sus tiempos de ejecuci´on). 1 2 Cap´ıtulo 1. Introducci´ on 1.1. Motivaci´ on En esta tesis, la motivaci´on de construir un kernel desde su etapa inicial se debe a que se desea obtener el completo conocimiento y control del Sistema Operativo. El objetivo final es obtener un kernel lo suficientemente peque˜ no y con la capacidad de poder ser instalado en sistemas empotrados que contienen muy poca memoria, por ejemplo, aquellas plataformas que s´olo tienen capacidad de memoria de entre 16kb hasta 64kb. La mayor´ıa de los kernels que existen han sido dise˜ nados para trabajar con determinadas plataformas y por lo tanto sus primitivas de control se encuentran muy ligadas al hardware. Si se quisiera trabajar con estos kernels, entre los posibles problemas que se presentar´ıan se encuentran: 1. la necesidad de conseguir (adem´as del sistema operativo) la plataforma para la cual se encuentra dise˜ nado lo cual podr´ıa ser muy caro y en el peor de los casos poco com´ un. 2. muchos sistemas operativos de tiempo real, en especial los comerciales, no distribuyen el c´odigo fuente por lo que es casi imposible adaptarlos o portarlos a otras plataformas para las que no fueron dise˜ nados. Con el kernel que se dise˜ n´o, estos problemas se solucionan ya que se tiene toda la documentaci´on y el conocimiento sobre el kernel y por lo tanto su modificaci´on o migraci´on a otro tipo de plataformas no consumir´ıa mucho tiempo.Ser´ıa s´olo necesario para conocer a detalle la plataforma a la que se quiere portar sin tener que preocuparse por la estructura del kernel. Adem´as, esta tesis forma parte de un proyecto de investigaci´on llamado “Ambiente de Desarrollo de Sistemas en Tiempo Real Orientado a Control de Procesos”, el cual esta formado por tres proyectos de tesis, una doctoral y dos de maestr´ıa: Un Proyecto para el dise˜ no de Sistemas de Tiempo Real, basado en UML y Simulink (Tesis doctoral). Un Kernel de Tiempo Real (Tesis de maestr´ıa). Sistema Visualizador Gr´afico de Procesos en Tiempo Real (Tesis de maestr´ıa). Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.2. Trabajo Propuesto 3 El objetivo de este proyecto es crear un ambiente de dise˜ no, en donde los procesos de tiempo real se programen de forma visual, se genere autom´aticamente el c´odigo de cada tarea y este se ejecute en el kernel de Tiempo Real. 1.2. Trabajo Propuesto Se propone el dise˜ no de un kernel de tiempo real capaz de manipular y controlar procesos concurrentes utilizando distintos mecanismos de planificaci´on (existentes o experimentales). Se requiere que el kernel no sea muy grande, es decir, que cuente s´olo con las primitivas b´asicas, con el objetivo de poder portarlo a distintas plataformas sin tener que realizarle muchos cambios. Actualmente, la mayor´ıa de los Sistemas en Tiempo Real que existen (tanto experimentales como comerciales), han sido dise˜ nados para plataformas espec´ıficas. El kernel que se propone dise˜ nar estar´a en un principio pensado para ejecutarse en una m´aquina con procesador del tipo INTEL 80x86, sin embargo debido a su tama˜ no y a que no contendr´a ning´ un tipo de controladores de hardware innecesario tales como CD-ROM, Impresoras, Diskettes, etc. se podr´a f´acilmente portar a cualquier plataforma con tan s´olo modificar los archivos de configuraci´on del kernel en base al c´odigo o instrucciones que maneje la nueva plataforma o sistema empotrado. 1.3. Trabajos Relacionados Existen en la actualidad un gran n´ umero de sistemas operativos de tiempo real comerciales y experimentales. Entre los sistemas operativos comerciales que existen, analizaremos los siguientes: VxWorks [1] y RT-Linux [2]. Estos sistemas operativos incluyen una amplia gama de servicios tales como manejo de procesos, manejo de memoria, manejo de tiempos y manejo de dispositivos e interfaces con distintas plataformas de hardware. Por lo general estos sistemas operativos son de gran tama˜ no, y est´an dise˜ nados para cubrir una amplia gama de aplicaciones y servicios para sistemas embebidos. Por otro lado, existen los sistemas operativos experimentales, de los cuales los m´as conocidos en la actualidad son: EMERALDS de la Universidad de Michigan [4], S.H.A.R.K de la Escuela Superior Santa Ana de Pisa Italia Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4 Cap´ıtulo 1. Introducci´ on [5] y SPRING de la Universidad de Massachusetts en Amherts [6]. Estos sistemas operativos incluyen distintos m´etodos de planificaci´on, son de tama˜ no medio a peque˜ no (512kb - 128kb), cuentan con interfaces gr´aficas y son bastante flexibles en su dise˜ no. En varios de estos sistemas operativos se incluyen t´ecnicas desarrolladas por dichas Universidades, tales son los casos de SPRING que se basa en la t´ecnica de planificaci´ on del mejor esfuerzo (best effort scheduling) o EMERALDS que utiliza una t´ecnica de planificaci´ on llamada CSD (Combined Static/Dynamic Scheduler) que combina los algoritmos de planificaci´on Rate Monotonic y Earliest Deadline First. 1.4. 1.4.1. Sistemas Operativos de Tiempo Real Comerciales VxWorks Inicialmente VxWorks fue un ambiente de desarrollo en red para VRTX y PSOSytem. Sus creadores fundaron una empresa llamada “Wind River Systems” donde crearon su propio microkernel. El resultado obtenido fue VxWorks, el cual fue dise˜ nado para funcionar sobre arquitecturas cliente-servidor. VxWorks apareci´o oficialmente en 1987 como un microkernel orientado a objetos, r´apido, eficiente y altamente escalable. Para que Wind River trabaje en conjunto con VxWorks, se cuenta con un ambiente integrado de desarrollo de aplicaciones empotradas llamado “Tornado”. Tornado es un ambiente de dise˜ no abierto para ser ajustable y extendido por el desarrollador. Este ambiente viene con un extenso conjunto de herramientas como compiladores, depuradores, herramientas para medir el desempe˜ no de los datos en tiempo real, etc [8]. Arquitectura El coraz´on del sistema VxWorks es el Wind kernel. Este microkernel soporta un amplio rango de servicios de tiempo real como la multitarea, la planificaci´on, la sincronizaci´on, la comunicaci´on entre tareas y el manejo de memoria. Como se puede apreciar en la Figura 1.1, el sistema VxWorks cuenta en la capa m´as baja con librer´ıas y primitivas que son dependientes del hardware y en la parte alta todas aquellas que son independientes. Estas ultimas son implementadas como procesos y realizan funciones de red, de entrada y salida, de manejo Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.4. Sistemas Operativos de Tiempo Real Comerciales 5 de archivos, etc. VxWorks (en especial la versi´on 5.3.1) puede ser configurado para usarse desde un sistema empotrado peque˜ no con fuertes restricciones de memoria, hasta complejos sistemas donde m´as funciones son necesarias. Figura 1.1: Arquitectura de VxWorks Tareas o Procesos VxWorks provee un ambiente multitarea b´asico, maneja prioridades de hasta 256 niveles (donde 0 es el de mayor prioridad) y los primeros 50 niveles est´an reservados para el sistema. El n´ umero m´aximo de tareas est´a limitado por la cantidad de memoria disponible. Memoria Todo el sistema y todas las tareas comparten el mismo espacio de memoria, lo que significa que aplicaciones defectuosas o mal dise˜ nadas podr´ıan accidentalmente accesar a los recursos del sistema y comprometer la estabilidad del sistema entero. Por otro lado, la empresa WindRiver Systems provee un componente adicional llamado VxVMI que necesita ser comprado por separado. Este componente (VxVMI) permite que cada proceso tenga su propia memoria virtual privada. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 6 Cap´ıtulo 1. Introducci´ on Mecanismos de Planificaci´ on Cuenta con dos algoritmos de planificaci´on, el algoritmo de planificaci´on Round Robin y un planificador basado en prioridades, este u ´ltimo algoritmo puede funcionar en dos modalidades: 1. Con prioridad fija, en donde cada proceso tiene una prioridad asignada desde el principio y no cambia durante toda su ejecuci´on en el kernel. 2. Con prioridad variable, en donde una tarea se empieza a ejecutar con una prioridad y esta tiende a decrecer conforme el tiempo de ejecuci´on va aumentando [9]. Manejo de Interrupciones Para lograr responder lo m´as r´apido posible a interrupciones externas, las rutinas de servicio de interrupciones se ejecutan en un contexto especial (fuera de cualquier hilo de contexto), de esta manera se asegura que ninguna tarea al cambiar de contexto las involucre. Mecanismos de Comunicaci´ on entre Tareas VxWorks cuenta con eficientes mecanismos de comunicaci´on entre tareas que les permiten coordinar sus acciones dentro del sistema de tiempo real. Para un simple intercambio de datos se puede utilizar el mecanismo de memoria compartida, pero si se desea una comunicaci´on entre tareas y el CPU, es necesario utilizar las tuber´ıas (pipes) o las colas de mensajes. Este u ´ltimo mecanismo esta formado por un complejo entramado de colas donde los procesos ponen todo lo que quieren escribir o comunicar a otras tareas. Mecanismos de Sincronizaci´ on entre Tareas Los mecanismos de sincronizaci´on con los que cuenta VxWorks son: Sockets y Llamadas a Procedimientos Remotos: Utilizados para mantener una comunicaci´on en red transparente. Se˜ nales: Para el manejo de excepciones. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.4. Sistemas Operativos de Tiempo Real Comerciales 7 Sem´ aforos: Para controlar los recursos cr´ıticos del sistema. VxWorks cuenta con diferentes tipos de sem´aforos: binarios, contadores y de exclusi´on mutua con herencia de prioridad. 1.4.2. RT-Linux RT-Linux (Real Time Linux) surgi´o a partir del trabajo de Michael Barabanov y Victor Yodaiken en la Universidad de Nuevo M´exico. Actualmente contin´ uan activamente con su desarrollo desde su propia empresa (FSM Labs) desde la que ofrecen soporte t´ecnico. RT-Linux se distribuye bajo la “GNU Public License” y recientemente Victor Yodaiken ha patentado la arquitectura original en la que se basa RT-Linux [10]. RT-Linux funciona sobre quitecturas PowerPC, i386, y est´a en desarrollo la versi´on para Alpha. A partir del c´odigo de Yodaiken, se est´a desarrollando otro proyecto liderado por P. Mantegazza llamado: “Real Time Application Interface” RTAI. Las primeras versiones de RT-Linux ofrec´ıan un API (Aplication Programming Interface) muy reducido sin tener en cuenta ninguno de los est´andares de tiempo real: POSIX Real-Time extensions, PThreads, etc. A partir de la versi´on 2.0, Victor Yodaiken decide reconvertir el API original a otro que fuera “compatible” con el API de POSIX Threads. Arquitectura Es un peque˜ no kernel que coexiste con el kernel de Linux, permiti´endole a este, operar funciones de tiempo real en un ambiente predecible y de baja latencia. RT-Linux se basa en la idea de m´aquinas virtuales para poder ejecutar un sistema operativo de tiempo compartido est´andar y un gestor de tiempo real en la misma m´aquina. En si RT-Linux no es c´odigo independiente, si no que parte de su c´odigo es un parche sobre el c´odigo de Linux y otra parte son m´odulos cargables. RT-Linux se sit´ ua entre el hardware y el propio sistema operativo, creando una m´aquina virtual para que Linux pueda seguir funcionando [Figura 1.2]. RTLinux toma el control de todas las interrupciones e implementa un gestor de interrupciones por software. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 8 Cap´ıtulo 1. Introducci´ on Figura 1.2: Arquitectura de RT-Linux Tareas o Procesos Todas las tareas son definidas est´aticamente ya que no soporta asignaci´on de memoria din´amica. Los procesos de tiempo real se clasifican en hilos (threads) ligeros y pesados, cada uno con su propio espacio de memoria. El contexto de un proceso de tiempo real s´olo consiste de registros enteros, lo cual asegura un r´apido cambio de contexto. Actualmente s´olo se soportan tareas de tiempo real peri´odicas. Todas las tareas comparten el mismo espacio de memoria que el n´ ucleo, por lo que pueden acceder a todas las variables y funciones de este; aunque no es recomendable ya que se podr´ıa producir interbloqueos. Las tareas de tiempo real (RT-Tasks) no pueden hacer uso de las llamadas al sistema de Linux y se ejecutan en modo supervisor; lo que significa que pueden ejecutar cualquier instrucci´on de procesador y tienen acceso a todos los puertos de entrada y salida (E/S). Memoria Las RT-Tasks se ejecutan en el mismo espacio de memoria que el n´ ucleo de Linux. RTLinux utiliza funciones de Linux como mbuff() para compartir zonas de memoria entre los procesos de Linux y las RT-Task. Para reservar memoria, RT-Linux puede utilizar alguno de los siguientes m´etodos: Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.4. Sistemas Operativos de Tiempo Real Comerciales 9 Memoria Alta no Utilizada.- Consiste en forzar a Linux a utilizar menos memoria alta de la que hay instalada en la m´aquina. La t´ecnica consiste en indicarle a Linux que existe menos memoria de la que en realidad hay, de esta manera, la zona alta de memoria queda libre para ser utilizada por RT-Linux. BigPhysArea.- Es un parche en el n´ ucleo de Linux que reserva durante el arranque del sistema operativo, la cantidad de memoria f´ısica que se le indique. Mecanismos de Planificaci´ on Utiliza un simple planificador basado en prioridades. Este est´a implementado como una rutina que se encarga de elegir un proceso de entre varios procesos listos clasificados con prioridad “alta” y lo marca como el siguiente proceso a ejecutar. Una tarea puede abandonar voluntariamente al procesador o puede ser desalojada por otra tarea con mayor prioridad cuyo tiempo de ejecuci´on est´a por iniciar [11]. Manejo de Interrupciones En cuanto al manejo de interrupciones, RT-Linux es el que controla todo el hardware y es el u ´nico que tiene acceso directo a ´el. Linux por su parte se encuentra en ejecuci´on sobre una m´aquina virtual creada por RT-Linux y todas las interrupciones que solicite ser´an atendidas por RT-Linux. RT-Linux se encargar´a de simular por software (a trav´es de la m´aquina virtual) la interrupci´on solicitada. Con esto se puede ver que RT-Linux es capaz de definir nuevas interrupciones para la m´aquina virtual de Linux y que estas nuevas interrupciones har´an “creer” a Linux que provienen de alg´ un perif´erico en hardware, mientras que en realidad, las interrupciones habr´an sido originadas por alguna tarea de RT-Linux. Mecanismos de Comunicaci´ on entre Tareas RT-Linux maneja dos tipos de mecanismos de comunicaci´on entre tareas que son: mediante FIFOs o a trav´es de se˜ nales [12]. Se˜ nales: En UNIX las se˜ nales se utilizan como un mecanismo de “sincronizaci´on as´ıncrono”, en donde las se˜ nales hacen el papel de las interrupciones. RT-Linux hace Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 10 Cap´ıtulo 1. Introducci´ on uso extensivo de este concepto (se˜ nal/interrupci´on) y lo utiliza para comunicar RTTasks entre si, as´ı como para modificar el estado de ejecuci´on de las tareas, atender interrupciones hardware y disparar eventos en el n´ ucleo de Linux. FIFOs: Es un mecanismo de comunicaci´on basado en las “FIFO” de UNIX, pero adaptado a tiempo real. Las FIFO implementadas en RT-Linux no tienen relaci´on con las FIFO cl´asicas de UNIX. Ambas son implementaciones distintas de un mismo m´etodo de comunicaci´on. Se pueden utilizar para comunicar tanto hilos entre s´ı, como hilos con procesos Linux existan. La comunicaci´on con los FIFO es unidireccional, estos es, se comporta como un buffer circular de forma que cada operaci´on de lectura puede eliminar los datos le´ıdos. Mecanismos de Sincronizaci´ on de Procesos La sincronizaci´on es llevada a cabo mediante mecanismos tradicionales como: Mutex, Variables de Condici´on y Sem´aforos. Las Variables de Condici´on son los tipos de datos y funciones necesarias para que, junto con el Mutex, se puedan construir “monitores”. Un monitor es un conjunto de funciones que operan sobre un conjunto de datos para llevar a cabo la exclusi´on mutua. En cuanto a los sem´aforos, la funcionalidad de estos no es muy compleja ya que junto con los Mutex y las Variables de Condici´on se puede resolver cualquier tipo de problema relacionado con la sincronizaci´on. 1.5. 1.5.1. Sistemas Operativos de Tiempo Real Experimentales EMERALDS EMERALDS (Extensible Microkernel for Embedded ReAL-time, Distributed Systems) es un microkernel de tiempo real dise˜ nado para sistemas empotrados de tama˜ no medio a peque˜ no con poca memoria (32-128 Kbytes) y cuyas aplicaciones deben correr sobre procesadores lentos (12-25MHz). EMERALDS actualmente est´a dise˜ nado para trabajar en procesadores Motorola 68040 y su tama˜ no es de 13 Kbytes. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.5. Sistemas Operativos de Tiempo Real Experimentales 11 Arquitectura EMERALDS es un microkernel de tiempo real escrito en el lenguaje C++ y gracias a su dise˜ no es f´acil instalarle nuevos protocolos de comunicaci´on as´ı como nuevos manejadores de dispositivos (drivers). Como se puede ver en la figura 1.3, EMERALDS maneja procesos multihilos, planificaci´on de tiempo real, espacios de memoria protegida, paso de mensajes, sem´aforos y temporizadores; todo esto de manera eficiente y manteniendo el tama˜ no del kernel peque˜ no [13]. Figura 1.3: Arquitectura de EMERALDS Tareas o Procesos Un proceso en EMERALDS es una entidad pasiva representando una direcci´on protegida de memoria en la cual el hilo se ejecutar´a. Cada hilo tiene una prioridad especificada por el usuario . Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 12 Cap´ıtulo 1. Introducci´ on Memoria Las t´ecnicas para la asignaci´on de memoria que utiliza EMERALDS son la paginaci´on en memoria f´ısica y la capacidad de asignar memoria virtual. Muchos sistemas operativos de tiempo real (RTOS) omiten la protecci´on de memoria e hilos con la finalidad de reducir el tama˜ no e incrementar la velocidad, sin embargo en EMERALDS por el contrario se provee de la protecci´on requerida para la tabla de p´aginas (sin que esto afecte en el tama˜ no). Para evitar que creciera el tama˜ no del kernel, al implementar la protecci´on de memoria se parti´o del hecho que todas las aplicaciones en los sistemas empotrados se encuentran en memoria y que por lo tanto las regiones a proteger no necesitaban de algoritmos complejos. Mecanismos de Planificaci´ on Actualmente EMERALDS provee un algoritmo de planificaci´on basado en prioridades y tiene soporte parcial en la planificaci´on din´amica. El usuario especifica la prioridad del hilo en forma est´atica (durante el tiempo de dise˜ no) bas´andose en los algoritmos Rate Monotonic (RM) o Earliest Deadline First (EDF). EMERALDS por su parte utiliza un algoritmo de planificaci´on llamado Combined Static/Dynamic Scheduler (CSD), que es una combinaci´on de los algoritmos de planificaci´on RM y EDF. La pol´ıtica de planificaci´on de este algoritmo es la siguiente: de un 100 % de tareas en el sistema, el 50 % de tareas con prioridad alta son planificadas con EDF para evitar que pierdan sus plazos y el otro 50 % de tareas con menos prioridad, son planificadas con RM [14]. Manejo de Interrupciones EMERALDS cuenta con un controlador de dispositivos el cual se encarga de llamar al kernel y decirle que subrutina del ISR (Interrupt Service Routines) ejecutar cuando la interrupci´on ocurre. Un ISR separado puede ser anexado a cada nivel de interrupci´on, tantas veces como exista comunicaci´on entre los hilos del usuario y los controladores de dispositivos. Mecanismos de Comunicaci´ on entre Tareas Los procesos en estos sistemas tienden a intercambiar mensajes cortos y simples como la lectura de un sensor y comandos de un actuador. En EMERALDS se utiliza el tradicional Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.5. Sistemas Operativos de Tiempo Real Experimentales 13 mecanismo para el intercambio de informaci´on entre tareas que es: el paso de mensajes por medio de buzones. Mecanismos de Sincronizaci´ on de Procesos Los m´etodos utilizados para sincronizar los procesos en EMERALDS son: la exclusi´on mutua y los sem´aforos. Estos funcionan de la misma manera que en otros sistemas operativos, por ejemplo: si un hilo intenta adquirir un sem´aforo que esta siendo ocupado en ese momento, ese hilo ser´a bloqueado y se agregar´a a la cola de hilos esperando por ese sem´aforo. Cuando el hilo que ocupaba el sem´aforo lo libere, el hilo con mayor prioridad en la cola podr´ıa ser desbloqueado. 1.5.2. S.H.A.R.K. SHARK (Soft and HArd Real-time Kernel) es un kernel de investigaci´on para ayudar en la implementaci´on y prueba de nuevos algoritmos de planificaci´on, tanto para el CPU como para otros recursos. El kernel puede ser usado para validar f´acilmente las ejecuciones de los algoritmos de planificaci´on producidos en laboratorios de investigaci´on. Este m´etodo permite a los desarrolladores enfocar su atenci´on en el dise˜ no de los algoritmos, ahorr´andoles el tiempo de implementaci´on de las nuevas soluciones. Arquitectura Con el prop´osito de realizar independencia entre aplicaciones y algoritmos de planificaci´on, SHARK esta basado sobre un kernel gen´erico, el cual no implementa un algoritmo de planificaci´on en particular, sino que relega las decisiones de planificaci´on a entidades externas llamadas “m´odulos de planificaci´on”. De manera similar, el acceso a recursos compartidos es coordinado por “m´odulos de recursos” [15]. El kernel provee las primitivas sin especificar los algoritmos que residen en los m´odulos externos [ver Figura 1.4]. Actualmente SHARK tiene dos tipos b´asicos de m´odulos: 1. M´odulos que implementan algoritmos de planificaci´on peri´odicos y servicios especiales a pol´ıticas aperi´odicas llamados M´ odulos de Planificaci´ on. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 14 Cap´ıtulo 1. Introducci´ on Figura 1.4: Arquitectura de SHARK 2. M´odulos que manejan recursos compartidos (Hardware y Software) llamados M´ odulos de Recursos. Tareas o Procesos Las tareas son definidas como funciones en C est´andar. Una tarea es descrita por un identificador unico de proceso y un n´ umero secuencial. Las tareas pueden ser peri´odicas ´o aperi´odicas. Las tareas peri´odicas son activadas autom´aticamente por el kernel, mientras que las tareas aperi´odicas pueden ser activadas por una llamada explicita al sistema ´o por la ocurrencia de un evento. Las tareas pueden tener diferentes niveles de criticidad, como son: HARD(las tareas cr´ıticas en el sistema), SOFT (aquellas tareas que pueden perder algunos plazos) y NRT (para aquellas tareas que no son de tiempo real). Memoria El kernel de SHARK cuenta con un conjunto de funciones est´andar para la asignaci´on de memoria que son provistas por las librer´ıas del lenguaje C. Las m´as utilizadas son: calloc(): la cual asigna memoria para un arreglo de n elementos, realloc(): la cual cambia el tama˜ no de memoria asignado y free(): la cual libera el espacio de memoria que haya sido asignado por calloc o realloc. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.5. Sistemas Operativos de Tiempo Real Experimentales 15 El kernel tambi´en provee un asignador de memoria basado en FLUX OS kit, el cual divide la memoria en tres regiones: 1) Memoria menor a 1MB, 2) Memoria entre 1MB y 16MB, 3) Memoria por debajo de los 16MB, y por u ´ltimo 4) Memoria por encima de los 16MB [16]. Mecanismos de Planificaci´ on Como se mencion´o anteriormente, este kernel no tiene implementado un algoritmo de planificaci´on espec´ıfico ya que la planificaci´on de las tareas se realiza a trav´es de los m´odulos de planificaci´on. Actualmente algunos de estos m´odulos contienen los siguientes algoritmos de planificaci´on: Rate Monotonic, Earliest Deadline First, Round Robin y Slot Shifting. Cuando el kernel gen´erico tiene que desempe˜ nar una decisi´on de planificaci´on, los m´odulos se encargan de “preguntar” por la tarea a ejecutar. Primero se va con el m´odulo con m´as alta prioridad, si el m´odulo no tiene alguna tarea lista, entonces se le preguntar´a al m´odulo que le siga en prioridad y as´ı consecutivamente. De esta manera cada m´odulo maneja su lista privada de tareas preparadas y el kernel gen´erico planifica la primer tarea encontrada en el m´odulo con mayor prioridad. Manejo de Interrupciones Cuando una interrupci´on se presenta, se crea un c´odigo al cual se le transfieren los datos para responder a la interrupci´on. Este c´odigo puede ejecutarse en dos modos diferentes: 1. El c´odigo puede ser encapsulado por completo en una funci´on, para ser ejecutado inmediatamente con la llegada de la interrupci´on (sobre el contexto de la tarea en ejecuci´on). 2. El c´odigo puede ser encapsulado por completo en una tarea, la cual ser´a activada con la llegada de la interrupci´on y se planificar´a en base a su prioridad junto con las dem´as tareas. El primer m´etodo es apropiado cuando la interrupci´on necesita un tiempo de respuesta r´apido e inapropiado cuando el tiempo de computo no es corto,debido a que toda la planificabilidad puede ser afectada severamente; esto es porque el algoritmo no toma en cuenta el tiempo de ejecuci´on del manejador de interrupciones. El segundo m´etodo por el contrario, est´a integrado perfectamente con el mecanismo de planificaci´on del kernel, sin embargo puede causar Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 16 Cap´ıtulo 1. Introducci´ on retardos considerables en la transferencia de datos ya que espera su turno, como cualquier otra tarea, para poder ser atendida. Mecanismos de Comunicaci´ on entre Tareas El intercambio de mensajes se lleva a cabo mediante puertos de comunicaci´on. Cada puerto es u ´nico e identificable mediante un nombre simb´olico. SHARK ofrece tres tipos de puertos: STREAM: Facilita la comunicaci´on uno-a-uno y puede ser abierto tanto por la tarea receptora como por la emisora. MAILBOX (Buz´ on): Este mecanismo facilita la comunicaci´on muchos-a-uno. Fue pensado para ser usado en el modelo cliente/servidor. Este puerto de comunicaci´on s´olo puede ser abierto por la tarea receptora, la cual tiene que recibir datos desde las tareas emisoras. STICK: Facilita la comunicaci´on uno-a-muchos. Se pretende que sea usado para el intercambio de mensajes peri´odicos, para lo cual, la informaci´on m´as reciente es la m´as relevante. Este mecanismo puede ser abierto s´olo por la tarea emisora y las tareas receptoras tendr´ıan que conectarse a ´el. Los dos primeros tipos de puertos implementan comunicaci´on s´ıncrona, mientras que los puertos STICK permite implementar la comunicaci´on as´ıncrona. Los puertos STREAM usan sem´aforos para sincronizar el acceso. Los puertos STICK s´olo usan el sem´aforo de exclusi´on mutua y los puertos MAILBOX utilizan ambos tipos de sem´aforos. Mecanismos de Sincronizaci´ on de Procesos SHARK cuenta con los siguientes mecanismos de sincronizaci´on: Sem´ aforos: La interfaz de los sem´aforos en SHARK es similar a la de los sem´aforos POSIX, con la diferencia de que SHARK agrega algunas otras primitivas que permiten incrementar/decrementar el contador del sem´aforo por m´as de una unidad de tiempo con la finalidad de evitar la inversi´on de prioridad. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.5. Sistemas Operativos de Tiempo Real Experimentales 17 Mutexes: Un Mutex puede ser considerado como un sem´aforo binario inicializado en 1. De esta manera, una secci´on critica puede ser especificada usando s´olo las primitivas mutexblock() y mutexunblock(). Variables de Condici´ on: Las variables de condici´on tienen la ventaja de permitir a una tarea bloquearse a si misma en la espera de un evento. 1.5.3. Spring Spring surgi´o como un proyecto de investigaci´on en la universidad de Massachusetts en el a˜ no de 1990, pero fu´e hasta 1992 (con su segunda versi´on) cuando el kernel empez´o a tener logros significativos. Spring es un kernel de tiempo real en donde sus creadores aseguran que provee algunos de los soportes b´asicos requeridos para la siguiente generaci´on de sistemas operativos, especialmente en el conocimiento de las restricciones de tiempo. Spring surge de la necesidad de construir sistemas operativos de tiempo real predecibles y flexibles ya que la siguiente generaci´on de sistemas de tiempo real podr´ıan ser largos, complejos, distribuidos, adaptables, podr´ıan contener muchas restricciones de tiempo, operar sobre ambientes no determin´ısticos y evolucionar sobre un largo sistema de por vida. Arquitectura Spring fue desarrollado para que pudiera trabajar sobre un sistema distribuido llamado SpringNet [ver Figura 1.5]. SpringNet es f´ısicamente un sistema distribuido compuesto de una red de nodos multiprocesador en donde cada nodo ejecuta el kernel Spring. Cada nodo contiene uno o mas procesadores de aplicaci´on, un procesador de sistema y un subsistema de entrada/salida. El procesador de sistema (SP) es el encargado de administrar las funciones, particularmente las de planificaci´on de tareas. El ´o los procesadores de aplicaci´on (AP), son los encargados de ejecutar las tareas garantizadas por el planificador. Por u ´ltimo, el subsistema de entrada/salida (I/O) es dividido en partes por el kernel Spring y es el que maneja los dispositivos no-cr´ıticos y lentos de entrada/salida as´ı como a los sensores r´apidos. La arquitectura de Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 18 Cap´ıtulo 1. Introducci´ on Figura 1.5: Arquitectura de Spring Spring incorpora las ideas del nuevo paradigma propuesto por los desarrolladores del kernel, basado en la idea de la planificaci´on del “mejor esfuerzo” (Best-Efford Scheduling)[17]. Tareas o Procesos Una tarea consiste de c´odigo reentrante con datos locales y globales, una pila, un descriptor de la tarea y un bloque de control de tarea. Cada tarea adquiere recursos antes de iniciar su ejecuci´on y estos son liberados una vez que su ejecuci´on termine. Las tareas son parte de una u ´nica aplicaci´on y los tipos de tareas que pueden ocurrir en una aplicaci´on de tiempo real son conocidas de antemano, por lo tanto, pueden ser inicializadas para determinar sus caracter´ısticas. Esta informaci´on podr´ıa ser utilizada en tiempo de ejecuci´on [17]. Basados en la importancia y requerimientos de tiempo, en Spring se encuentran definidas tres tipos de tareas: tareas cr´ıticas, tareas esenciales y tareas no esenciales. Memoria Las primitivas para el manejo de memoria son utilizadas para crear recursos definidos como pilas, bloques de control de tareas, descriptores de tareas, datos locales y globales, puertos, Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.5. Sistemas Operativos de Tiempo Real Experimentales 19 discos virtuales y memoria no segmentada. Las tareas requieren de un m´aximo n´ umero de segmentos de memoria de cada tipo, pero en su correspondiente tiempo de activaci´on una tarea podr´ıa requerir menos segmentos de los que podr´ıa necesitar despu´es. Para solucionar esto, Spring asigna todos los segmentos requeridos cuando la tarea inicia su ejecuci´on y los deja residentes en memoria. Todos los procesos tienen p´aginas pre-asignadas, cargadas en tiempo de ejecuci´on y mantenidas residentes en memoria, por lo que no es necesario implementarle un m´etodo para bloquear memoria [20]. Mecanismos de Planificaci´ on En Spring el mecanismo de planificaci´on no es basado en prioridades como en la mayor´ıa de los sistemas operativos de tiempo real. El algoritmo de planificaci´on de Spring integra la planificaci´on del CPU y la de recursos para proveer garant´ıas. Este mecanismo de planificaci´on se llama “Best-Efforf” y tiene las siguientes caracter´ısticas: es din´amico, planifica tareas expulsivas y no expulsivas, con precedencia, niveles de importancia y tolerancia a fallos. En el algoritmo “Best-Efforf”, planificar un conjunto de tareas para encontrar una planificaci´on factible es un problema de b´ usqueda y se resuelve a trav´es de una b´ usqueda en un ´arbol. Un v´ertice del ´arbol es una planificaci´on parcial y una hoja o un v´ertice terminal es una planificaci´on completa. En el peor caso, encontrar una planificaci´on ´optima requerir´ıa de una b´ usqueda exhaustiva. El planificador puede ser utilizado en l´ınea y fuera de l´ınea, este algoritmo de planificaci´on ha sido implementado en software como parte del kernel Spring y en hardware en un chip VLSI [6]. Manejo de Interrupciones Las interrupciones que son generadas por los dispositivos I/O son atendidas por el sistema de entrada/salida, sin embargo, existen otras interrupciones generadas por alg´ un ambiente no deterministico y que podr´ıa afectar la predecibilidad del kernel. Para evitar esto, las tareas que se ejecutan sobre los procesadores de aplicaci´on son aisladas de cualquier interrupci´on no predecible y s´olo los procesadores de sistema junto con los subsistemas I/O pueden ser afectados por estas interrupciones. Si de manera indirecta alguna interrupci´on llegara a afectar a tareas que se ejecutan sobre los procesadores de aplicaci´on, ser´ıa responsabilidad del Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 20 Cap´ıtulo 1. Introducci´ on “algoritmo de garantia” atender la petici´on. Mecanismos de Comunicaci´ on entre Tareas La comunicaci´on entre procesos (IPC) en Spring ha sido dise˜ nada con el fin de ofrecer una comunicaci´on predecible, por lo tanto, las primitivas de comunicaci´on tienen l´ımites en el tiempo de ejecuci´on y la comunicaci´on s´ıncrona no permite que se produzcan bloqueos no predefinidos. En Spring la comunicaci´on se realiza a trav´es de puertos, los cuales son objetos de memoria protegida que contienen unidades de datos llamados mensajes. Los procesos pueden comunicarse con alg´ un otro proceso colocando mensajes en los puertos y a su vez obteniendo mensajes de los mismos. Mecanismos de Sincronizaci´ on de Procesos La predecibilidad es una de las preocupaciones que mas se tiene en cuenta en el dise˜ no de un sistema de tiempo real. Como un esfuerzo por acercarse a esta predecibilidad, Spring ha limitado cada aspecto y primitiva del kernel (incluyendo a los mecanismos de sincronizaci´on) para cumplir con las exigencias de la siguiente generaci´on de kernels multiprocesadores de tiempo real. Entre las caracter´ısticas de los mecanismos de sincronizaci´on implementados, destaca la inclusi´on de “sem´aforos s´olidos” que forman parte de los nuevos paradigmas de los sistemas de tiempo real propuestos por Spring y por lo tanto, han sido dise˜ nados para poder funcionar eficientemente sobre los sistemas de tiempo real multiprocesador. 1.6. 1.6.1. Objetivos de la Tesis Objetivos Generales En cuanto a su utilidad, el objetivo es dise˜ nar un kernel en tiempo real s´olido y capaz de interactuar con el mundo exterior para controlar los eventos que puedan ocurrir dentro de los sistemas en tiempo real. Adem´as de tener la propiedad de permitir la monitorizaci´on y el control de todos los procesos. En cuanto a lo acad´emico, se requiere que sea peque˜ no para facilitar su migraci´on en plataformas empotradas y permitir experimentar con ´el en este tipo de plataformas (PALMS, Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 1.7. Organizaci´ on de la Tesis 21 PDAS). Adem´as, debe permitir incluir nuevos mecanismos de planificaci´on con la finalidad de poder estudiar otros algoritmos que existan e incluso probar aquellos que se dise˜ nen en el CINVESTAV. 1.6.2. Objetivos Particulares Obtener el mejor tiempo de respuesta posible que pueda ofrecer el Timer de la m´aquina. (reprogramaci´on del PIT) Evitar que el kernel se extienda (en tama˜ no) con la finalidad de que permita ser transportado a plataformas empotradas las cuales suelen tener demasiadas restricciones (memorias y dispositivos de almacenamiento secundarios). Integrar este Kernel con un visualizador de procesos para fines estad´ısticos. Lograr un conocimiento profundo sobre el tema y poder documentarlo de tal forma que pudiera servir en un futuro, para el traslado del kernel en alg´ un sistema empotrado. Modularizar el kernel de tal forma que no dependa de un s´olo mecanismo de planificaci´on. Con este se logra tener un kernel que permite experimentar con otro tipo de planificadores que ya existen o incluso con algunos que se pudieran dise˜ nar en un futuro. 1.7. Organizaci´ on de la Tesis La escritura de la tesis se desarroll´o de la siguiente manera: En el Cap´ıtulo 2 se define el concepto de sistemas de tiempo real, se mencionan los elementos y caracter´ısticas de estos, as´ı como las aplicaciones y clasificaciones m´as comunes de los sistemas de tiempo real. En este cap´ıtulo tambi´en se explica que es un sistema operativo de tiempo real y se definen otros conceptos necesarios para la comprensi´on de la tesis, como el de proceso y quantum. Como los procesos o tareas son el objetivo a controlar dentro del kernel, es necesario saber bien su comportamiento y por lo tanto en este cap´ıtulo se explican los estados y transiciones que puede tener un proceso y se muestra el contenido del Bloque Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 22 Cap´ıtulo 1. Introducci´ on de Control de Procesos (BCP). Para finalizar este cap´ıtulo, se muestran y definen los componentes que todo sistema operativo en tiempo real debe contener. El Cap´ıtulo 3 est´a dedicado por completo a explicar los mecanismos de planificaci´on en los sistemas de tiempo real. Aqu´ı se clasifican y muestran las restricciones de las tareas de tiempo real, se define el problema de planificaci´on. En este cap´ıtulo adem´as, se clasifican las pol´ıticas de planificaci´on en base a sus prioridades y se da dos ejemplos por clasificaci´on. Se explica Rate Monotonic y Deadline Monotonic para planificadores basados en prioridades est´aticas y se explica Earliest Deadline First y Least Laxity First para planificadores basados en prioridades din´amicas. En el Cap´ıtulo 4 se encuentra todo lo referente al Kernel desarrollado en esta tesis, se muestra la arquitectura que se utiliz´o para desarrollar el Kernel, se presenta el BCP utilizado para las tareas del Kernel y cual es el comportamiento que van a tener dentro del mismo, se explica como configurar el Kernel para que se adapte a las necesidades del usuario y adem´as, se detalla paso a paso cada una de las primitivas y manejadores que lo integran. En este cap´ıtulo se encuentra tambi´en la estructura general que deben de tener las tareas o procesos creados por el usuario. El Cap´ıtulo 5 contiene las pruebas realizadas al kernel y se describe cual fue su comportamiento al trabajar con tareas de tiempo real no simuladas. Por u ´ltimo, el Cap´ıtulo 6 contiene las conclusiones a las que se llegaron con este trabajo de tesis y adem´as, presenta algunas extensiones o modificaciones que se le podr´ıan hacer al kernel como trabajo a futuro con la finalidad de extenderle el campo de aplicaci´on. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 2 Sistemas de Tiempo Real 2.1. Definici´ on de Sistema de Tiempo Real Un sistema de tiempo real (STR) es un sistema inform´atico que interacciona repetidamente con su entorno y responde a los est´ımulos que recibe del mismo dentro de un plazo de tiempo determinado[21]. Para que el funcionamiento del sistema sea correcto no basta con que las acciones del sistema sean correctas, si no que adem´as, tienen que ejecutarse dentro del intervalo de tiempo especificado. Los resultados deben producirse en los momentos en que a´ un tengan validez dentro del ambiente a controlar. Los sistemas de tiempo real controlan un ambiente que tiene restricciones de tiempo bien definidas (ver figura 2.1), es por ello, que se vuelven m´as complejos y por lo tanto demandan una alta confiabilidad, con resultados correctos, predecibles y a tiempo. Actualmente, los sistemas de tiempo real abarcan un amplio espectro de aplicaciones, desde los m´as simples microcontroladores (tales como un microcontrolador para el control de un autom´ovil) hasta sistemas grandes y distribuidos (como los sistemas de control de tr´afico a´ereo). Se espera que en un futuro los sistemas de tiempo real sean aun m´as complejos y se utilicen en el control de estaciones espaciales, en sistemas integrados 23 24 Cap´ıtulo 2. Sistemas de Tiempo Real Figura 2.1: Sistema de Tiempo Real. de visi´on/rob´otica/Inteligencia Artificial y en entornos peligrosos como plantas qu´ımicas, nucleares, etc. 2.2. Aplicaciones de los Sistemas de Tiempo Real En el campo de los sistemas de tiempo real se distinguen tres tipos de aplicaciones principalmente: En el control de procesos industriales: Este tipo de aplicaci´on se empez´o a llevar a cabo desde la d´ecada de los 60 y actualmente, es normal el uso de microprocesadores para este tipo de aplicaciones. El objetivo es conseguir que una determinada variable siga una evoluci´on prefijada. Esta variable puede ser: temperatura, presi´on caudal, nivel dentro de un dep´osito, velocidad o posici´on de un motor, etc. La computadora debe ser capaz de generar se˜ nales que permitan conseguir el objetivo, para esto, se parte de una variable a controlar, el valor ideal para esta variable y un algoritmo de control. En la manufacturaci´ on: El uso de las computadoras en la manufacturaci´on es esencial para reducir el costo de la producci´on y aumentar la productividad. Por lo general Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.3. Elementos de un Sistema de Tiempo Real 25 en este tipo de aplicaci´on la computadora tiene integrado el dise˜ no del producto a fabricar y se encarga de coordinar las tareas a realizar por los distintos componentes del sistema como son, las m´aquinas de construcci´on, las cintas transportadoras, etc. En la comunicaci´ on y aplicaciones militares: Este tipo de aplicaciones inicialmente surgen del campo militar, sin embargo actualmente existen un gran n´ umero de aplicaciones que tiene caracter´ısticas similares; por ejemplo la monitorizaci´on de pacientes en centros m´edicos, el control del tr´afico a´ereo y los informes bancarios remotos. Todos estos sistemas contienen un complejo juego de m´odulos de vigilancia, dispositivos que recogen informaci´on y procedimientos que permiten tomar desiciones. 2.3. Elementos de un Sistema de Tiempo Real Un sistema de tiempo real consiste principalmente de computadoras, y elementos externos con los cuales el software de la computadora debe interactuar simult´aneamente. En la figura 2.2 se muestran los elementos generales de un sistema de tiempo real donde el objetivo principal es controlar un ambiente. En dicha figura se distinguen los siguientes elementos: Ambiente: El t´ermino ambiente de la figura 2.2 se refiere al sistema controlado. Por ejemplo, un motor, un sistema de manufactura, un robot, o un avi´on, etc. El estado del ambiente (entorno f´ısico) es supervisado por los sensores y puede cambiar por los actuadores. Convertidores: Los convertidores an´alogico-digital convierten las se˜ nales generadas por el ambiente (anal´ogicas) a una serie de datos que la computadora interpreta (digitales). Reloj de Tiempo Real: El reloj de tiempo real permite al sistema contar el tiempo en que se ejecutan acciones. De la misma forma, el reloj de tiempo real permite al sistema configurar los tiempos para la planificaci´on de las tareas. Mediante el reloj de tiempo real es posible configurar interrupciones para controlar dispositivos externos, recibir y sincronizar se˜ nales de comunicaci´on, y monitorear el cumplimiento de los requerimientos temporales de las tareas del sistema. Sin el reloj de tiempo real no ser´ıa Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 26 Cap´ıtulo 2. Sistemas de Tiempo Real Figura 2.2: Elementos de un Sistema de Tiempo Real. posible configurar los tiempos de ejecuci´on de las tareas de tiempo real, y por tanto la planificaci´on del sistema, ni tampoco ser´ıa posible saber si las tareas cumplen con sus restricciones temporales. En una aplicaci´on que involucra a varias computadoras es necesario que los relojes de tiempo real se encuentren sincronizados, a fin de que todos ellos lleven la misma cuenta de tiempo. Software de Tiempo Real: El software de tiempo real esta compuesto de un sistema operativo (o kernel) y de tareas las cuales son planificadas por el kernel. La estructura del kernel esta compuesta de manejadores de tiempo, de tareas, de memoria, de dispositivos, y de todos los recursos del sistema de c´omputo. Las tareas del sistema (o procesos) son las entidades de software que permiten controlar el medio ambiente. Cada tarea es un procedimiento de software que se ejecuta de forma continua, sin embargo, la ejecuci´on concurrente de las tareas es controlada por el manejador de procesos del kernel. Existe otro software dentro del sistema, como son las librer´ıas, los drivers de dispositivos o los controladores de comunicaciones. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.4. Caracter´ısticas de los Sistemas de Tiempo Real 27 Comunicaciones: En el sistema de tiempo real pueden existir distintas computadoras que interact´ uan entre s´ı. Entre ellas existe un medio f´ısico de comunicaci´on (hardware) y un protocolo de comunicaciones (software) que les permite enlazarse, compartir informaci´on y sincronizar su ejecuci´on. Mediante la comunicaci´on es posible compartir recursos de hardware (por ejemplo, dispositivos de entrada y salida), y mejorar la eficiencia de aplicaciones mediante la distribuci´on del computo, y lograr mayor rapidez de ejecuci´on. Otras E/S (entradas y salidas): Un sistema de tiempo real tiene como entrada principalmente el comportamiento del sistema f´ısico controlado. Sin embargo, existen otras entradas y salidas principalmente aquellas con las que interact´ uan con el usuario, como son el teclado, el rat´on, y otros dispositivos de interacci´on con el usuario. 2.4. Caracter´ısticas de los Sistemas de Tiempo Real Las caracter´ısticas m´as destacables de un sistema en tiempo real son: Interacci´ on con el Entorno: Los sistemas de tiempo real interact´ uan con un entorno externo por lo que es necesario utilizar sensores que permitan realizar la toma de datos del entorno y un conjunto de actuadores que permitan modificar el estado del sistema controlado. Restricciones de Tiempo: Los sistemas de tiempo real tienen que procesar informaci´on en un plazo de tiempo finito. La obtenci´on de resultados fuera de plazo puede ocasionar graves consecuencias a´ un cuando los resultados sean correctos. Esto les diferencia de otros sistemas donde se pueden imponer restricciones de tiempo para comodidad del usuario pero su incumplimiento no es cr´ıtico. Predecible ´ o Determinista: No es f´acil dise˜ nar e implementar un sistema que garantice que la salida apropiada se generar´a en el tiempo adecuado bajo cualquier circunstancia, sin embargo los sistemas de tiempo real lo deben asegurar. Fiabilidad y Seguridad: Por la naturaleza de los sistemas de tiempo real estos requieren que la computadora interact´ ue con el mundo externo (monitorizando sensores Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 28 Cap´ıtulo 2. Sistemas de Tiempo Real y activando actuadores), por lo que el hardware y el software de las computadoras en un sistema de tiempo real deben ser fiables y seguros. 2.5. Clasificaci´ on de los Sistemas de Tiempo Real Los sistemas de tiempo real se pueden clasificar de muchas maneras (por su arquitectura, por su especificaci´on para la creaci´on del software, por los flujos de ejecuci´on de los que est´a compuesto, etc.). La clasificaci´on m´as conocida es aquella en la que distinguen a los sistemas de tiempo real en base a sus requisitos temporales y de fiabilidad. Esta clasificaci´on separa los sistemas de tiempo real en sistemas cr´ıticos y en sistemas acr´ıticos. 2.5.1. Sistemas de Tiempo Real Cr´ıticos (Hard Real Time Systems) Son sistemas en los que, por su propia naturaleza, se puede llegar a tener un fallo muy grave en el caso de que no se cumpla con alguno de sus requisitos temporales. En su dise˜ no se debe prestar especial atenci´on a la disponibilidad de los recursos y asegurar que el sistema alcanza sus plazos temporales incluso en alguna situaci´on de fallo de alguno de sus componentes f´ısicos1 . Las caracter´ısticas de los sistemas de tiempo real cr´ıticos son las siguientes: Tienen un plazo de respuesta estricto Su comportamiento temporal es determinado por el entorno El comportamiento en sobrecargas es predecible Tiene requisitos de seguridad cr´ıticos Provee tolerancia a fallos (mediante redundancia activa). El volumen de datos es reducido 2.5.2. Sistemas de Tiempo Real Acr´ıticos (Soft Real Time Systems) Son sistemas en los que es importante el cumplimiento de los requisitos temporales, pero si de alguna manera alguno de ellos no pudiera cumplirse el sistema no producir´ıa un fallo. 1 Para lograr asegurar que el sistema responda a´ un cuando llegue a tener problemas con sus componentes f´ısicos, generalmente se utiliza la redundancia de componentes. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.6. ¿Qu´ e es un Sistema Operativo de Tiempo Real? 29 Por ejemplo, en los sistemas multimedia de tiempo real las im´agenes y el sonido se deben transmitir dentro de plazos determinados, y si por alguna raz´on hubiera problemas y no se pudieran cumplir estos plazos, lo m´as que podr´ıa suceder es que una trama de sonido o de video se retrasara ´o en el peor de los casos que esta trama se tuviera que descartar, pero a pesar de los problemas, el cambio en el resultado no ser´ıa muy importante para el usuario. Las caracter´ısticas principales de los sistemas acr´ıticos son: Su plazo de respuesta es flexible Tienen un comportamiento temporal determinado por la computadora El comportamiento en sobrecargas es degradado Los requisitos de seguridad son acr´ıticos Permite la recuperaci´on en caso de fallos Manejan un volumen de datos grande 2.6. ¿Qu´ e es un Sistema Operativo de Tiempo Real? Un sistema operativo es un programa que act´ ua como un intermediario entre el usuario de una computadora y el hardware de esta. El prop´osito de un sistema operativo es proveer un ambiente en el cual, el usuario puede ejecutar un programa de manera c´omoda y eficiente. Actualmente existen muchos tipos de sistemas operativos, entre ellos resaltan los sistemas operativos multiprocesadores, los multitareas, los distribuidos, los empotrados, los paralelos y los de tiempo real, todos ellos, han sido dise˜ nados para ser eficientes en determinadas ´areas o condiciones de trabajo. Un sistema operativo de tiempo real al igual que todos los sistemas operativos, es un programa que controla el hardware de la computadora y sirve de intermediario entre la m´aquina y el usuario. Lo que hace que sea de tiempo real es la capacidad de responder a est´ımulos generados externamente dentro de un plazo determinado y finito. Todo sistema operativo de tiempo real debe ser determinista, es decir, debe garantizar que las aplicaciones que este controle se ejecuten dentro de una restricci´on de tiempo espec´ıfico. En resumen, Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 30 Cap´ıtulo 2. Sistemas de Tiempo Real se puede decir que la principal responsabilidad de un sistema operativo de tiempo real es la de producir resultados exactos y garantizar el cumplimiento de unos plazos (deadline) predefinidos. 2.7. Proceso 2.7.1. Definici´ on de Proceso Un proceso de manera informal puede ser visto como un programa en ejecuci´on, sin embargo es m´as que c´odigo de programa. Un proceso es la unidad de trabajo en la mayor´ıa de los sistemas operativos y se caracteriza por tener informaci´on como: el c´odigo del programa, el contador de programa que indica la siguiente instrucci´on a ejecutar, una pila que contiene datos temporales como las direcciones de regreso, las variables temporales de datos y los par´ametros del proceso. Adem´as, los procesos tienen una secci´on de datos en donde se almacenan todas las variables globales que este ocupe [22]. Un programa por si s´olo no es un proceso; un programa es una entidad pasiva, como puede ser el contenido de un archivo o programa almacenado en disco, mientras que un proceso es una entidad activa que controla el sistema operativo con un contador de programa que especifica la siguiente instrucci´on a ejecutar y el conjunto de recursos asociados. 2.7.2. Definici´ on de Quantum Un quantum es la unidad de tiempo que tiene asignada cada proceso para que este se ejecute en el procesador. Cuando un proceso consume su quantum, el proceso es desalojado y se le da el control al pr´oximo proceso LISTO. 2.7.3. Par´ ametros de un Proceso de Tiempo Real Como se muestra en la figura 2.3, los par´ametros asociados a un proceso de tiempo real (τi ) son: Tiempo de Activaci´ on (ai ): Es el tiempo en el cual el proceso o tarea (τi ) est´a lista para su ejecuci´on. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.7. Proceso 31 Per´ıodo de Activaci´ on (Ti ): Es el momento en que el proceso (τi ) realiza una petici´on de ejecuci´on. Tiempo de C´ omputo (Ci ): Es el tiempo de ejecuci´on del proceso (τi ). Tiempo de Inicio (si ): Tiempo en el cual el proceso (τi ) inicia su ejecuci´on. Tiempo de Finalizaci´ on (fi ): Tiempo en el cual el proceso (τi ) termina su ejecuci´on. Plazo de Respuesta (Di ): Es el tiempo permitido para que el proceso (τi ) finalice su ejecuci´on. Criticidad: Es un par´ametro relacionado a la consecuencia de la p´erdida de plazos de respuesta, o se relaciona con la importancia de los tareas dentro del conjunto de tareas. Latencia (Li ): Li = Di − fi , representa el retrazo en la terminaci´on de una tarea o proceso con respecto a su plazo de respuesta. Si Li ≤ 0 la tarea (τi ) no pierde su plazo. Prioridad (P ): Es un n´ umero que representa la importancia del proceso o la tarea dentro del sistema. Un proceso con gran importancia es ejecutado con mayor frecuencia que otro que no es tan importante con la finalidad de evitar que el proceso importante pierda su plazo. Figura 2.3: Par´ametros de un Proceso de Tiempo Real 2.7.4. Estado del Proceso Durante la ejecuci´on de un proceso, su estado cambia y por lo tanto, el estado de un proceso esta definido por la actividad que ese proceso est´e realizando. Como se muestra en la figura 2.4, cada proceso podr´ıa estar en uno de los siguientes estados: Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 32 Cap´ıtulo 2. Sistemas de Tiempo Real Nuevo: El proceso esta siendo creado. En este estado, se le asigna al proceso recursos, se reserva un espacio en memoria para cargar c´odigo, datos y stack, y se genera su “Process Control Block” (cuyo contenido se explicar´a mas adelante). Corriendo: Las instrucciones del proceso se est´an ejecutando. Esperando: El proceso est´a esperando por alg´ un evento a ocurrir. Listo: El proceso est´a esperando para ser asignado al procesador. Terminado: Pasa a este estado, solamente si el proceso ha terminado su ejecuci´on. Figura 2.4: Diagrama de estado de los procesos S´olo un proceso a la vez puede estar corriendo en un procesador en un instante determinado, a la vez que varios procesos podr´ıan estar en una cola de procesos listos esperando a que se les asigne el procesador. Los nombres de los estados son arbitrarios y var´ıan entre los sistemas operativos. Los estados que aqu´ı se presentan son mencionados en todos los sistemas operativos. 2.7.5. Transiciones entre Estados Como se muestra en la figura 2.4, los procesos pueden cambiar de estado durante su ejecuci´on, debido a alguno de los siguientes eventos: Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.7. Proceso 33 Admitido: Esta transici´on ocurre cuando el proceso es creado y est´a listo para competir por los recursos. Despachado: Ocurre cuando el planificador elige al proceso de la cola de listo y le asigna el procesador. Interrumpido: Ocurre cuando el proceso cumple con su tiempo de computo (Quantum) ´o cuando alg´ un proceso de mayor prioridad le quita el procesador. E/S ´ o Espera por evento: Ocurre cuando el proceso necesita esperar por alg´ un dispositivo de entrada/salida o por la llegada de un evento. E/S ´ o Terminaci´ on de un evento: Es cuando el dispositivo o el evento que esperaba el proceso ya ocurri´o y por lo tanto el proceso esta listo para su ejecuci´on. Fin: Ocurre cuando un proceso ha terminado de realizar todas sus tareas y por lo tanto es eliminado del sistema. 2.7.6. PCB (Process Control Block) Cada proceso es representado en el sistema operativo por un Bloque de Control de Procesos (PCB) o tambi´en conocido como Bloque de Control de Tareas. Un PCB como se muestra en la figura 2.5, contiene muchas piezas de informaci´on asociadas con un proceso espec´ıfico. Figura 2.5: Bloque de Control de Procesos (PCB) Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 34 Cap´ıtulo 2. Sistemas de Tiempo Real Esta informaci´on es la siguiente: Estado del Proceso: El estado podr´ıa ser nuevo, listo, corriendo, esperando, bloqueado, etc. Contador de Programa.- Aqu´ı se indica la direcci´on de la siguiente instrucci´on a ser ejecutada en el procesador. Registros del CPU: Los registros var´ıan en n´ umero y tipo, dependiendo de la arquitectura de la computadora. Aqu´ı se incluyen acumuladores, apuntadores a pilas, registros ´ındices y registros de prop´osito general. Informaci´ on del Planificador de CPU: Esta informaci´on incluye la prioridad del proceso, apuntadores a las colas de planificaci´on y cualquier otro par´ametro de planificaci´on. Informaci´ on para el Manejo de Memoria: Esta informaci´on podr´ıa incluir la tabla de p´aginas, de segmentos, registros l´ımites, etc. Todo depende de la memoria en el sistema utilizada por el sistema operativo. Informaci´ on Contable: Esta informaci´on contiene la cantidad de CPU y tiempo real usado, limites de tiempo, n´ umeros de procesos, etc. Informaci´ on del estado de I/O: Aqu´ı se encuentra la lista de dispositivos de entrada/salida (I/O) asignados al proceso, la lista de archivos que ha abierto, etc. 2.8. 2.8.1. Componentes de un Sistema Operativo de Tiempo Real Manejador de Procesos Un proceso es un programa en ejecuci´on el cual necesita de ciertos recursos (procesador, memoria, archivos, dispositivos E/S) para lograr su actividad. EL manejador de procesos proporciona servicios primordiales que todo sistema operativo debe proveer. Este incluye varias funciones de soporte como las de creaci´on, terminaci´on, planificaci´on y despacho de procesos, as´ı como el manejo del cambio de contexto [23]. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.8. Componentes de un Sistema Operativo de Tiempo Real 35 Creaci´ on de procesos Un proceso durante su ejecuci´on puede crear muchos procesos nuevos mediante una llamada al sistema a la rutina de creaci´on de procesos. El proceso que los cre´o es llamado proceso padre y a los nuevos procesos se les llama hijos. Cada uno de estos procesos hijos, puede a su vez crear nuevos procesos form´andose as´ı un ´arbol de procesos. Generalmente un proceso necesita de ciertos recursos (tiempo de CPU, memoria, manejo de archivos y dispositivos de E/S), por lo que cuando un proceso crea un subproceso, el subproceso podr´ıa ser capacitado para obtener sus recursos directamente desde el sistema operativo ´o ser obligado a tener un subconjunto de recursos desde el proceso padre. Terminaci´ on de un proceso Un proceso se termina cuando ´este finaliza su ejecuci´on, en este punto el proceso le pide al sistema operativo que lo borre, regresa los datos a su proceso padre y todos los recursos que el proceso ocupaba (memoria f´ısica y virtual, archivos, buffers de E/S, etc.) son devueltos al sistema operativo. Cambio de Contexto En un sistema operativo de (tipo) multiprogramaci´on, se maneja el concepto de contexto para mantener informaci´on del estado en que se encuentran cada uno de los procesos. En este contexto se encuentran incluidos los incluidos en el PCB del proceso que se est´a ejecutando. El cambio de contexto ocurre cuando un proceso es interrumpido de su ejecuci´on para que otro proceso pueda utilizar el procesador (ver figura 2.6). Esta interrupci´on puede ocurrir cuando al proceso se le termina su Quantum, o cuando un proceso de mayor prioridad demanda al procesador. Los pasos que se realizan en el cambio de contexto son los siguientes: 1. Se graba el estado de la tarea que est´a en ejecuci´on. 2. Se utiliza al planificador para conocer que tarea es la siguiente a ejecutar. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 36 Cap´ıtulo 2. Sistemas de Tiempo Real 3. Se carga el estado de la siguiente tarea para que al finalizar el cambio de contexto sea ´esta quien ahora haga uso del procesador. Figura 2.6: Cambio de Contexto. El cambio de contexto es considerado como sobrecarga ya que durante el tiempo que este se lleva a cabo, el sistema queda incapacitado para realizar alguna operaci´on u ´til. El tiempo que tarda en ejecutarse el cambio de contexto puede variar de una m´aquina a otra2 , depende de la velocidad de la memoria, el n´ umero de registros que contenga y la existencia de instrucciones especiales (tales como alguna instrucci´on que permita cargar o almacenar todos los registros de una s´ola vez)[22]. 2.8.2. Manejador de Memoria La memoria es un arreglo de words o bytes en donde cada uno cuenta con una direcci´on propia, siendo adem´as un dispositivo de acceso r´apido por el procesador o los dispositivos de entrada/salida. El procesador la utiliza para leer las instrucciones de programa que se encuentran almacenadas aqu´ı y adem´as le sirve para escribir informaci´on temporal. Los dispositivos de E/S la utilizan para leer y escribir mediante el DMA (Acceso Directo a Memoria). Las funciones que el manejador de memoria debe realizar son: 2 El tiempo que tarda en realizarse el cambio de contexto puede variar entre 1 y 1,000 microsegundos dependiendo de las caracter´ısticas de la m´ aquina. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.8. Componentes de un Sistema Operativo de Tiempo Real 37 Decidir que procesos cargar en memoria cuando est´a este disponible. Conocer que partes de la memoria est´an siendo utilizadas y por quien. Poder liberar y conceder espacio de memoria cuando se le requiera. Los mecanismos que se utilizan para administrar la memoria pueden variar (paginaci´on, segmentaci´on, reemplazo de p´aginas, etc). La elecci´on de estos mecanismos depende en gran parte del hardware para el cual se est´e dise˜ nando el sistema operativo de tiempo real. Por ejemplo, en los sistemas empotrados la memoria es escasa y todos los procesos se encuentran residentes en memoria por lo que no es necesario tener un administrador de memoria complejo. 2.8.3. Manejador de Reloj El manejador de reloj realiza diferentes acciones de acuerdo a las interrupciones que genera el reloj. Entre las funciones que controla este manejador se encuentran: Provee informaci´on para el calendario de procesos (planificadores). Mantiene actualizada la fecha y la hora del d´ıa. Maneja las alarmas. Como se puede ver, el reloj de tiempo real permite al sistema configurar los tiempos para la planificaci´on de las tareas. Adem´as, mediante el manejador de reloj es posible configurar interrupciones para controlar dispositivos externos, recibir y sincronizar se˜ nales de comunicaci´on y monitorear el cumplimiento de los requisitos temporales de las tareas del sistema. 2.8.4. Mecanismos de Sincronizaci´ on y Comunicaci´ on Es otro mecanismo b´asico que todo kernel debe proveer. La comunicaci´ on provee mecanismos para permitir que los procesos se comuniquen y se sincronicen. La sincronizaci´ on evita la inconsistencia de datos, el cual es un problema muy com´ un en los sistemas concurrentes. La manera cl´asica para resolver la sincronizaci´on es utilizando mecanismos de exclusi´on mutua o sem´aforos. La comunicaci´on re realiza a trav´es de memoria compartida o por paso de mensajes mediante buzones. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 38 Cap´ıtulo 2. Sistemas de Tiempo Real Secci´ on Cr´ıtica La secci´on cr´ıtica es una secuencia de instrucciones con un comienzo y un final claramente marcados que, por lo general, delimita la actualizaci´on de una o m´as variables compartidas. Cuando un proceso entra en una secci´on cr´ıtica, debe ejecutar todas las instrucciones incluidas en ella antes de que se pueda permitir a cualquier otro proceso entrar a la misma secci´on cr´ıtica. Exclusi´ on Mutua Se le llama exclusi´on mutua al hecho de que s´olo el proceso que ejecuta la secci´on cr´ıtica tiene permitido el acceso a la variable compartida. Cuando un proceso se encuentra en exclusi´on mutua, a los dem´as procesos se les tiene prohibida esa secci´on hasta que el proceso que esta dentro la libera, dicho de otra manera, un proceso puede excluir temporalmente a todos los dem´as de utilizar un recurso compartido con el fin de asegurar la integridad del sistema. Sem´ aforos El concepto de sem´aforo fue inventado por Dijkstra para solucionar el problema de la exclusi´on mutua. El mecanismo sem´aforo consta b´asicamente de dos operaciones primitivas, se˜ nal (signal) y espera (wait) 3 que operan sobre un tipo especial de variable sem´aforo, S. La variable sem´aforo puede tomar valores enteros y solo puede ser accedida y manipulada por medio de las operaciones se˜ nal y espera, con la excepci´on del valor en su inicializaci´on. Ambas primitivas llevan un argumento cada una (la variable sem´aforo), y se definen de la siguiente forma: Wait(S): Es una operaci´on que decrementa el valor de su argumento sem´aforo, S. La operaci´on WAIT es indivisible. Si despu´es de decrementar el sem´aforo, el valor de S es negativo, el proceso que llama a esta primitiva se bloquea (ver figura 2.7). Signal(S): Es una operaci´on que incrementa el valor de su argumento sem´aforo (S) 3 Las primitivas se˜ nal y espera originalmente fueron definidas como P y V (se˜ nal y espera en holand´es) por Dijkstra, quien fue el que invent´ o el concepto de sem´ aforo. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.8. Componentes de un Sistema Operativo de Tiempo Real 39 Figura 2.7: Operaci´on WAIT. siempre y cuando, no haya procesos bloqueados en la cola de sem´aforos, si los hay, en lugar de incrementar desbloquea al proceso. La operaci´on SIGNAL tambi´en es indivisible (ver figura 2.8). Figura 2.8: Operaci´on SIGNAL. Un sem´aforo cuya variable s´olo tiene permitido tomar los valores 0 (ocupado) y 1 (libre) se denomina sem´aforo binario. Para los sem´aforos binarios, la l´ogica de Wait(S) deber´ıa interpretarse como la espera hasta que la variable sem´aforo S sea igual a LIBRE, seguido de su modificaci´on indivisible para que se indique OCUPADO antes de devolver el control al invocador. La operaci´on de WAIT implementa por tanto la fase de negociaci´on del protocolo de exclusi´on mutua. SIGNAL pone el valor de la variable sem´aforo a LIBRE y representa por tanto la fase de liberaci´on en la secuencia de exclusi´on mutua descrita anteriormente. Tipos de Sem´ aforos Por su granularidad, los sem´aforos pueden ser: Sem´ aforos Binarios: En los sem´aforos binarios los valores que pueden tomar son cero y uno debido a que el recurso que controla, s´olo un proceso lo puede poseer. Si Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 40 Cap´ıtulo 2. Sistemas de Tiempo Real un proceso solicita un recurso controlado por un sem´aforo binario y es el primero en pedirlo, se le asigna el recurso. Por otro lado si ya estaba un proceso utilizando ese recurso, al nuevo proceso que lo solicit´o se le bloquear´ıa hasta que el recurso haya sido liberado. La definici´on en la operaci´on WAIT es la misma y en la operaci´on SIGNAL el cambio consiste en lo siguiente: Si hay procesos suspendidos, despierta uno, si no, el valor de S es igual a 1. Sem´ aforos Contadores: Los sem´aforos contadores son u ´tiles cuando hay que asignar un recurso a partir de un conjunto de recursos id´enticos. El sem´aforo tiene como valor inicial el n´ umero de recursos contenidos en el conjunto. Cada operaci´on WAIT decrementa en uno el sem´aforo, indicando que se ha retirado un recurso del conjunto y que lo esta utilizando alg´ un proceso. Cada operaci´on SIGNAL incrementa en uno el sem´aforo, lo que indica la devoluci´on de un recurso al conjunto y que el recurso puede ser asignado a otro proceso. Si se intenta una operaci´on WAIT cuando el sem´aforo tiene valor o, el proceso deber´a esperar hasta que se devuelva un recurso al banco mediante una operaci´on SIGNAL. Por otra parte, sin importar el tipo de sem´aforo que sea, los sem´aforos pueden ser con bloqueo ´o sin bloqueo. Sem´ aforos con bloqueo: Son los que normalmente se utilizan, este tipo de sem´aforos dependiendo de la condici´on en WAIT pueden llegar a bloquear un proceso hasta que el recurso por el que espera sea liberado. El mecanismo para bloquear al proceso puede ser de dos maneras, utilizando FIFOs o s´olo marc´andolos como bloqueados, en este segundo m´etodo la operaci´on SIGNAL desbloquea un proceso al azar (sin saber cual es) mientras que cuando se utiliza FIFOS, la operaci´on SIGNAL siempre desbloquea al proceso que lleva m´as tiempo en la cola. Sem´ aforos sin bloqueo: Estos sem´aforos se conocen tambi´en como sem´ aforos con espera activa y se caracterizan por su operaci´on WAIT, ya que esta es un ciclo el cual se encuentra constantemente revisando el valor de S en lugar de bloquear el proceso (ver figura 2.9). Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.8. Componentes de un Sistema Operativo de Tiempo Real 41 Figura 2.9: Operaci´on WAIT en sem´aforos sin bloqueo. Comunicaci´ on entre Procesos Para que los procesos puedan comunicarse es necesario tener una forma de referenciarse unos con otros. Para lograr esto existen mecanismos de comunicaci´on que operan a trav´es de comunicaci´on directa ´o mediante la comunicaci´on indirecta. Comunicaci´ on Directa (paso de mensajes) En la comunicaci´on directa, cada proceso que quiera comunicarse debe especificar el nombre del proceso con el que se desea comunicar de la siguiente manera: send(P,message). Esto indica que se quiere enviar un mensaje al proceso P. receive(Q,message). Esto indica que se quiere recibir un mensaje que provenga del proceso Q. Este esquema de comunicaci´on tiene una simetr´ıa en el direccionamiento, esto es, que ambos procesos tanto el que env´ıa como el que recibe conocen el nombre del otro proceso con el que se va a comunicar. Existe una variante dentro de la comunicaci´on directa en la que se tiene un direccionamiento asim´etrico, esto es, que s´olo el que env´ıa conoce el nombre del proceso destino. send(P,message). Env´ıa un mensaje al proceso P. receive(id,message). Recibe un mensaje de cualquier proceso; la variable id es utilizada para almacenar el nombre del proceso con el que se tuvo comunicaci´ on. La desventaja en ambos esquemas (sim´etricos y asim´etricos) se encuentra en el momento de cambiar el nombre de un proceso, tendr´ıa que ser necesario examinar en las definiciones Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 42 Cap´ıtulo 2. Sistemas de Tiempo Real de todos lo procesos aquellos instantes en donde se haga referencia al nombre que ten´ıa antes el proceso para poderlo cambiar por el nuevo nombre. Comunicaci´ on Indirecta (Buzones) Con la comunicaci´on indirecta, los mensajes son enviados y recibidos desde buzones (tambi´en conocidos como puertos). Un buz´on puede ser visto de manera abstracta como un objeto en el cual los procesos pueden colocar sus mensajes as´ı tambi´en como un objeto donde los procesos pueden recibir sus mensajes. Algunos m´etodos para los sistemas operativos de tiempo real ven a los buzones como la forma m´as eficiente de implementar comunicaciones entre procesos. Un ejemplo de esto es el sistema operativo de tiempo real llamado iRMX de TenAsys [7], el cual suministra un buz´on basado en memoria que permite tratar con eficacia la transferencia de datos. Este buz´on, es un lugar para enviar y recibir punteros a los datos con la finalidad de eliminar la necesidad de transferir todos los datos, ahorrando as´ı tiempo y sobrecarga. En este esquema los procesos pueden comunicarse con cualquier otro proceso a trav´es de uno o varios buzones. Como regla general, dos procesos pueden comunicarse s´olo si alguno de ellos tiene un buz´on compartido y por lo tanto, las primitivas de env´ıa y recibe quedar´ıan definidas como sigue: send(A,message). Enviar un mensaje al buz´ on A. receive(A,message). Recibe un mensaje desde el buz´ on A. De esta manera, cualquier proceso que comparta el mismo buz´on podr´a recibir el mensaje. 2.8.5. Manejador de Entradas/Salidas Existen diferentes tipos de manejadores de acuerdo a los tipos de dispositivos presentes en el sistema. Los manejadores de dispositivos son los encargados de comunicarse con los dispositivos de Entrada/Salida con la finalidad de poder realizar las operaciones que estos requieran. La comunicaci´on entre los dispositivos y el sistema operativo es llevada a cabo principalmente a trav´es de interrupciones. El sistema de entradas y salidas consiste de: Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 2.8. Componentes de un Sistema Operativo de Tiempo Real 43 Un sistema de memoria cache mediante buffers. Una interfaz general con los manejadores de los dispositivos. Los manejadores para dispositivos de Hardware espec´ıfico. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 44 Cinvestav-IPN Cap´ıtulo 2. Sistemas de Tiempo Real Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 3 Planificaci´ on en Sistemas de Tiempo Real Cuando existen actividades con restricciones temporales, como ocurre en los sistemas de tiempo real, el principal problema a resolver ser´ıa el planificar esas actividades para poder cumplir con sus restricciones temporales. Para realizar esta planificaci´on se necesitar´a de un algoritmo de planificaci´on el cual no es mas que un conjunto de reglas que determinan qu´e tarea se debe ejecutar en cada instante. Estos algoritmos deben tener en cuenta las necesidades de recursos y tiempo de las tareas de tal manera que ´estas cumplan ciertos requisitos de prestaciones. Los objetivos a alcanzar por toda pol´ıtica de planificaci´on de tiempo real son: El garantizar la correcta ejecuci´on de todas las tareas cr´ıticas. Administrar el uso de recursos compartidos. 3.1. Tareas de Tiempo Real El sistema operativo de tiempo real en relaci´on con la planificaci´on, considera a las tareas como procesos que consumen cierta cantidad de tiempo de procesador, y ciertos recursos del 45 46 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real sistema. Para el planificador, los datos que necesita cada tarea as´ı como el c´odigo que ejecuta y los resultados que producen, son totalmente irrelevantes[27]. 3.1.1. Clasificaci´ on de las Tareas de Tiempo Real En base a los par´ametros mostrados en la secci´on 2.7.3 se pueden realizar distintas clasificaciones de las tareas de tiempo real. De todas las clasificaciones que existen, la que m´as destaca es aquella en donde se clasifica en base a la necesidad del cumplimiento de su plazo por parte de las tareas. La divisi´on de las tareas queda de la siguiente manera: Tareas de tiempo real duras (hard): Estas tareas deben cumplir siempre con sus plazos de respuesta, por lo que un fallo en el cumplimiento es intolerable por sus consecuencias en el sistema controlado. Por ejemplo, en un sistema de control de un autom´ovil, el proceso encargado de inflar la bolsa de aire debe comportarse de tal manera que nunca pasen m´as de 2 milisegundos desde que se detecta una colisi´on hasta que se produce su respuesta. Si se supera ese l´ımite, la respuesta del proceso tendr´ıa un valor negativo ya que la bolsa de aire se abrir´ıa cuando ya no fuera necesaria. Tareas de tiempo real suaves (soft): Para estas tareas el no cumplir con sus plazos de respuesta, produce una disminuci´on en el rendimiento o en la calidad de respuesta, pero el funcionamiento se puede considerar todav´ıa correcto. Es decir, se acepta que en alguna de las ejecuciones de la tarea exista una tardanza, sabiendo tambi´en que a medida que aumenta el tiempo de la tardanza el resultado cada vez ser´ıa menos u ´til. Otra caracter´ıstica relacionada con los par´ametros temporales, concierne a la regularidad de la activaci´ on de las tareas. Tomando en cuenta la regularidad en la ejecuci´on de las tareas de tiempo real, estas se pueden clasificar de la siguiente manera: Peri´ odicas: Las tareas peri´odicas se ejecutan repetidamente a intervalos de tiempo regulares (fijos) llamados instancias. En cada instancia se ejecuta un Job de la tarea de tiempo real. Al inicio de cada instancia el job se encuentra listo para ejecuci´on (ver figura 3.1). Aperi´ odicas: Las tareas aperi´odicas se activan de forma irregular al producirse determinados eventos de forma imprevisible. Las tareas aperi´odicas se ejecutan solo durante Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 3.1. Tareas de Tiempo Real 47 una instancia de ejecuci´on al termino de la cual desaparecen del sistema. Las tareas aperi´odicas, no tienen restricciones criticas. Espor´ adicas: Las tareas espor´adicas son tareas aperi´odicas con restricciones temporales criticas (o duras). Si se monitorea el arribo de las tareas espor´adicas es posible determinar una separaci´on m´ınima entre activaciones consecutivas, lo cual podr´ıa permitir caracterizarlas como tareas peri´odicas (ver figura 3.1). Figura 3.1: Tareas Peri´odicas y Espor´adicas. Otras clasificaciones de las tareas de tiempo real son las siguientes: Expulsables y no expulsables: Las tareas expulsables son aquellas que durante su ejecuci´on pueden ser interrumpidas por el planificador debido a que se necesita ejecutar otra tareas de mayor prioridad. Por otro lado, las tareas no expulsables no podr´an ser interrumpidas sino hasta que estas terminen su ejecuci´on. Con restricciones de precedencia: Las tareas con restricciones de precedencia presentan un orden de ejecuci´on con respecto a otras tareas del sistema. Si la tarea τi precede a la tarea τj , significa que la tarea τi solo puede ejecutarse hasta que la tarea Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 48 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real τj termine su ejecuci´on. Este tipo de tareas suelen aparecen en sistema multiprocesadores o sistemas distribuidos, en los cuales varias tareas cooperan para proporcionar la respuesta a los eventos del sistema. 3.1.2. Tipos de Restricciones de las Tareas de Tiempo Real Restricciones de Tiempo Los sistemas de tiempo real se caracterizan principalmente por tener restricciones que afectan el tiempo de ejecuci´on de sus actividades. El plazo de respuesta (o deadline) es una restricci´on de tiempo muy com´ un en las tareas de tiempo real, la cual representa el mayor tiempo que una tarea tiene para completar su c´omputo sin causar da˜ no al sistema. Restricciones de Precedencia Las aplicaciones de tiempo real, no pueden ser ejecutadas en orden arbitrario ya que tienen que respetar alguna relaci´on de precedencia. Las relaciones de precedencia son descritas por un grafo dirigido ac´ıclico G, donde las tareas son representadas por nodos y las relaciones de precedencia se representan por medio de v´ertices. Un grafo de precedencia G origina un orden sobre el conjunto de tareas. La notaci´on τa < τb establece que la tarea τa es la antecesora de la tarea τb , lo que significa que G tiene un camino directo del nodo τa al nodo τb . La notaci´on τa → τb establece que la tarea τa es la antecesora inmediata de τb , lo que significa que G tiene un v´ertice directo de la tarea τa a la tarea τb . La figura 3.2 muestra un grafo ac´ıclico que describe las restricciones de precedencia de cinco tareas. Como puede observarse la tarea τ1 es la u ´nica que puede iniciar su ejecuci´on debido a que no tiene tareas antecesoras. Cuando τ1 ha completado su c´omputo, entonces τ2 o τ3 pueden iniciar su ejecuci´on. La tarea τ4 puede iniciar su ejecuci´on solo cuando τ2 a terminado, mientras que τ5 tendr´a que esperar hasta que τ2 y τ3 terminen su ejecuci´on. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 3.1. Tareas de Tiempo Real 49 Figura 3.2: Relaci´on de precedencia para cinco tareas. Restricciones de Recursos Un recurso es una estructura de software o de hardware que puede ser usada en forma concurrente por varios procesos. T´ıpicamente, un recurso puede ser una estructura de datos, un conjunto de variables, un ´area de memoria, un archivo, un fragmento de un programa, o un dispositivo perif´erico. Un recurso dedicado exclusivamente a un proceso particular es llamado recurso privado ´o exclusivo, mientras que un recurso que puede ser utilizado por una o m´as tareas es llamado recurso compartido. Cuando varios procesos accesan a un recurso exclusivo, su acceso debe de darse en forma ordenada y sincronizada. Esto se debe a que solo un proceso a la vez puede estar haciendo acceso de este recurso. Esta situaci´on puede motivar perdidas de plazos, si alg´ un proceso de baja prioridad hace uso de un recurso exclusivo por largos periodos de tiempo. Cuando se hace uso de recursos compartidos, varios procesos a la vez pueden accesar a dichos recursos. En el caso de los recursos compartidos sean datos (o bases de datos), un factor importante a mantener es la consistencia y la integridad en los datos. Para mantener la consistencia de datos en recursos compartidos, no debe permitirse el acceso simult´aneo por dos o m´as tareas a estos datos. En este caso deben implementarse mecanismos de exclusi´on mutua entre las tareas que compiten por este recurso. Supongamos que R es un recurso compartido exclusivo para las tareas τa y τb . Si A es una operaci´on realizada por τa sobre R, y B es la operaci´on realizada por τb sobre R, entonces A y B nunca Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 50 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real pueden ejecutarse al mismo tiempo. Un fragmento de c´odigo ejecutado bajo restricciones de exclusi´on mutua se le conoce como secci´ on cr´ıtica. Para asegurar el acceso secuencial sobre recursos compartidos, los sistemas operativos normalmente proveen mecanismos de sincronizaci´on (tales como sem´aforos) que puedan ser usados por las tareas para crear regiones cr´ıticas. 3.2. Definici´ on del Problema de Planificaci´ on Para definir el problema de planificaci´on necesitamos especificar tres conjuntos: un conjunto de n tareas Σ = {τ1 , τ2 ,...τn }, un conjunto de m procesadores P ={P1 , P2 ,...Pm } y un conjunto de recursos R={R1 , R2 , ...Rs }. Adem´as, es necesario especificar las relaciones de precedencia entre tareas y las restricciones de tiempos de cada tarea[23]. En este contexto, la planificaci´on permite asignar los procesadores del conjunto P y los recursos del conjunto R a tareas del conjunto Σ de acuerdo a un orden que permita completar las tareas bajo las restricciones impuestas. Se ha demostrado que este problema es de tipo NP-completo, lo que significa que la soluci´on es muy dif´ıcil de obtener. Para reducir la complejidad en la construcci´on de planificadores, podemos simplificar la arquitectura de la computadora, por ejemplo, restringiendo al sistema para que utilice un solo procesador, adoptar un modelo con desalojo, usar prioridades fijas, eliminar precedencias o restricciones de recursos, asumir una activaci´on simult´anea de tareas y suponer que en el sistema existen conjuntos de tareas homog´eneos (´ unicamente tareas peri´odicas o tareas aperi´odicas). 3.3. Clasificaci´ on de Pol´ıticas de Planificaci´ on En los sistemas de tiempo real existen muchas estrategias de planificaci´on de tareas, sin embargo, estas pueden ser clasificadas en dos grandes grupos: los planificadores c´ıclicos y los planificadores basados en prioridades (ver figura 3.3). Los planificadores c´ıclicos consisten en construir un plan de ejecuci´on que se repite c´ıclicamente. Este plan de ejecuci´on se divide en un ciclo principal TM , el cual a su vez se divide en ciclos secundarios con per´ıodo TS . En cada ciclo secundario se ejecutan las actividades correspondientes a cada tarea. El principal problema que presentan los ejecutivos Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 3.4. Planificador C´ıclico 51 Figura 3.3: Clasificaci´on de los algoritmos de planificaci´on para sistemas de tiempo real. c´ıclicos es la poca flexibilidad en el momento de modificar par´ametros (a˜ nadir o borrar tareas), ya que esto conlleva a la re-elaboraci´on de todo el plan. En los planificadores basados en prioridades la asignaci´on de la prioridad de una tarea puede realizarse de forma est´atica (la asignaci´ on de prioridades se realiza al principio de la ejecuci´on del sistema, y no cambia durante la ejecuci´ on.) ´o din´amica (la asignaci´ on de prioridades se realiza en forma din´amica durante la ejecuci´ on del sistema). 3.4. Planificador C´ıclico En la planificaci´on c´ıclica, todas las tareas del sistema se planifican dentro de un plan de ejecuci´on. En este plan de ejecuci´on existe un ciclo principal, y varios ciclos secundarios. La forma de calcular los ciclos principal y secundarios se describe mediante el siguiente ejemplo: Para construir el plan de ejecuci´on, se debe calcular la duraci´on del ciclo principal TM y la duraci´on de los ciclos secundarios TS . La duraci´on del ciclo principal corresponde al m´ınimo com´ un m´ ultiplo de los per´ıodos de las tareas, TM = mcm(τi ). Resultando para el ejemplo de la tabla 3.1, TM = 100. Por otro lado, para calcular el tama˜ no de los ciclos secundarios, m, se deben considerar las siguientes condiciones: Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 52 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real T area T C A 25 10 B 25 8 C 50 5 D 50 4 E 100 2 Tabla 3.1: Conjunto de tareas peri´odicas El ciclo secundario debe ser menor o igual que el plazo de ejecuci´on de cada tarea, m ≤ {Di } El ciclo secundario debe ser mayor o igual que el m´aximo de los tiempos de c´omputo de las tareas, m ≥ max{Ci }. El ciclo secundario debe ser divisor del per´ıodo de cada tarea. Es decir, m divide a Ti Se debe cumplit que: 2m − mcd(m, Ti ) ≤ Di , la cual es una condici´on necesaria y suficiente que indica el instante de activaci´on de las tareas. Aplicando las condiciones anteriores al ejemplo de la tabla 3.1 se obtiene: m ≤ {Di } =⇒ m = {1, 2, 3, ..., 25} m ≥ max{Ci } =⇒ m = {10, 11, 12, ..., 25} m divide a Ti =⇒ m = {10, 20, 25} 2m − mcd(m, Ti ) ≤ Di =⇒ m = {10, 20, 25} Con los valores obtenidos para m se puede calcular el n´ umero de ciclos secundarios del ciclo principal mediante NTS = TM /m. Para m = 10 se tiene NTS = 10, para m = 20 se tiene NTS = 5 mientras que para m = 25 se tiene NTS = 4. Como la complejidad aumenta con el n´ umero de ciclos secundarios se elige m = 25 con lo que se tiene 4 ciclos secundarios por ciclo principal. Otro dato que se puede calcular es el n´ umero de ejecuciones Nei de cada tarea τi en el ciclo principal, mediante la expresi´on Nei = TM /Ti . En el ejemplo de la tabla Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 3.5. Planificadores Basados en Prioridades Est´ aticas 53 3.1 el n´ umero de ejecuciones de cada tarea es NeA,B = 4 para τA y τB , NeC,D = 2 para τC y τD y NeE = 1 para τE . En la Figura 3.4 se presenta gr´aficamente la ejecuci´on c´ıclica para el conjunto de tareas presentado en la tabla 3.1. Figura 3.4: Planificaci´on C´ıclica. 3.5. Planificadores Basados en Prioridades Est´ aticas En esta planificaci´on, las prioridades de las tareas se asignan en forma est´atica, antes de la ejecuci´on del sistema, y no cambian durante su ejecuci´on. En la planificaci´on basada en prioridades est´aticas (off-line), se realiza un an´alisis de planificabilidad de las tareas fuera de linea. Esta planificaci´on tiene como ventajas: Producir sobre-cargas muy bajas, ya que la asignaci´on de prioridades se realiza una sola vez antes de la ejecuci´on. Las prioridades asignadas a las tareas son guardadas en una tabla la cual permite al planificador decidir el orden de ejecuci´on de las tareas. Permite verificar el comportamiento temporal de las tareas a priori (predecibilidad). Es adecuada para trabajar con tareas con plazos cr´ıticos, y el an´alisis de planificabilidad nos permite comprobar a priori si dichas tareas cumplir´an sus plazos de respuesta. En situaciones de sobrecarga del sistema, siempre es posible predecir que las tareas de menor prioridad ser´an las primeras en perder sus plazos. Sus principales desventajas son: Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 54 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real Requiere un conocimiento previo de todos los par´ametros de las tareas. Es incapaz de tratar adecuadamente las tareas aperi´odicas. Inflexible a operar bajo ambientes din´amicos en donde los par´ametros cambian constantemente. 3.5.1. Rate Monotonic (RM) En el algoritmo Rate Monotonic, la asignaci´on de las prioridades se obtiene de acuerdo a los per´ıodos de las tareas. A la tarea con menor per´ıodo, se le asigna la mayor prioridad. En este algoritmo de planificaci´on, el per´ıodo es igual al plazo. Fueron Liu y Layland [24] quienes en 1973 propusieron el algoritmo Rate Monotonic (RM), adem´as demostraron que: Teorema 3.5.1 El algoritmo RM es ´ optimo dentro de los esquemas de asignaci´ on de prioridades est´ aticas. Por ´optimo debemos entender que si se tiene una planificaci´on factible para un conjunto dado de tareas mediante un algoritmo de asignaci´on con prioridades est´aticas, entonces ese conjunto de tareas tambi´en ser´a planificable mediante el algoritmo Rate Monotonic. En el an´alisis de este algoritmo[24], los autores proporcionan un control de admisi´ on 1 de tareas para RM basado en la utilizaci´on del procesador. Este control de admisi´on, compara la utilizaci´on del conjunto de tareas con una cota l´ımite que depende del n´ umero de tareas del sistema, es decir, un conjunto de n tareas no perder´a su plazo si cumple la siguiente condici´on: U= n X Ci i=1 Ti ≤ n(21/n − 1) (3.1) Teorema 3.5.2 La condici´on suficiente para que la planificaci´ on de un conjunto de n tareas peri´ odicas sea factible mediante el algoritmo RM, es que su factor de utilizaci´ on m´ınima n(21/n − 1) cumpla la siguiente condici´on: 1 El control de admisi´ on es un mecanismo que permite al planificador decidir sobre la aceptaci´ on de las tareas en el sistema. En sistemas de tiempo real con planificaci´ on est´ atica, este mecanismo se ejecuta solo una vez, al principio de la ejecuci´ on del sistema. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 3.5. Planificadores Basados en Prioridades Est´ aticas 55 U ≤ Umin = n(21/n − 1) (3.2) La tabla 3.2 describe el comportamiento de la expresi´on 3.2 para distintos valores de n. n Umin 1 1 2 0.8284 3 0.7798 4 0.7568 5 0.7433 . . . . . . ∞ 0.6931 Tabla 3.2: Utilizaci´on m´ınima garantizada para n tareas Como se puede apreciar en la tabla 3.2, al aumentar el n´ umero de tareas la utilizaci´on m´ınima garantizada converge en: Umin = ln 2 ≈ 0,6931 (3.3) Ejemplo: Consideremos el conjunto de tareas2 τ1 (30,10), τ2 (40,10) y τ3 (50,12) mostrado en la Figura 3.5. El factor de utilizaci´on de estas tres tareas es: U= C1 C2 C3 10 10 12 494 + + = + + = ≈ 0,82 T1 T2 T3 30 40 50 600 (3.4) La utilizaci´on total de este conjunto de tareas es mayor que la utilizaci´on m´ınima garantizada para tres tareas establecida por la condici´on 3.2 (0,82 > 0,7788). Siguiendo la ejecuci´on 2 Generalmente en un modelo simple de tareas, una tarea se puede representar como un par ordenado (Ti ,Ci ), debido a que el plazo de respuesta es considerado igual al per´ıodo. Es decir, Di = Ti . Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 56 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real de las tareas, presentada en la Figura 3.5, es posible observar que la tarea τ3 del conjunto pierde su plazo de respuesta en el tiempo t=50. Esta p´erdida de plazo se debe a que en la primera instancia de ejecuci´on s´olo puede ejecutarse por 10 unidades de tiempo. Siendo que su tiempo de c´omputo es de C3 = 12, dos unidades de tiempo quedan sin ser ejecutadas. Note que la tarea τ3 posee la menor prioridad del conjunto utilizando el esquema de asignaci´on de prioridades del algoritmo RM. Figura 3.5: Conjunto de tareas que no satisface la Ecuaci´on 3.2 y por lo tanto no es planificable. En la Figura 3.5 se representa el conjunto de tareas mediante una gr´afica de Gantt. Las flechas de la gr´afica nos indican los instantes donde las tareas solicitan tiempo de procesador. Los rect´angulos sombreados muestran la cantidad de tiempo de c´omputo utilizando por la tarea. T area Ti Ci Utilizaci´ on 1 16 4 0.250 2 40 5 0.125 3 80 32 0.400 0.775 Tabla 3.3: Conjunto de tareas, la utilizaci´on total cumple con la condici´on 3.2 Por otro lado, consideremos el conjunto de tareas mostrado en la tabla 3.3. Como se puede observar, la utilizaci´on total del conjunto de tareas no excede la cota proporcionada por la condici´on 3.2, es decir, U=0.775 < 0.778 = Umin . Por lo cual se garantiza que este Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 3.5. Planificadores Basados en Prioridades Est´ aticas 57 conjunto de tareas no perder´a ning´ un plazo de respuesta. La Figura 3.6 muestra gr´aficamente el comportamiento del conjunto de tareas. Figura 3.6: Conjunto de tareas que satisface 3.2 y por tanto es planificable. Es importante observar que la tabla 3.4 describe un conjunto de tareas cuya utilizaci´on del procesador es del 100 %, es decir, no satisface la condici´on 3.2, y a´ un as´ı, el conjunto de tareas cumple con los plazos de respuesta. Es por esta raz´on, que a esta condici´on se le conoce como una condici´on suficiente, pero no necesaria. La Figura 3.7 muestra la ejecuci´on de las tareas sin que estas hayan p´erdido su plazo. T area Ti Ci Utilizaci´ on 1 20 5 0.250 2 40 10 0.250 3 80 40 0.500 1.000 Tabla 3.4: Conjunto de tareas armonico, es planificable Condici´ on de Planificabilidad Suficiente y Necesaria Lehoczky et al. [25] desarrollaron una condici´on de planificabilidad necesaria y suficiente para un conjunto de tareas que es ejecutado en un sistema uniprocesador. Esta condici´on se define en el teorema 3.5.3 Teorema 3.5.3 Sea Γ = {τ1 , τ2 ,...,τn } un conjunto de n tareas peri´ odicas, con T1 ≤ T2 ≤ T3 ≤ ... ≤ Tn . Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 58 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real Figura 3.7: Conjunto de tareas que no satisface 3.2. Sin embargo, es planificable. τi es planificable usando el algoritmo Rate Monotonic si y s´ olo si Li = min{t∈Si } Wi (t)/t ≤ 1. (3.5) El conjunto entero de tareas es planificable bajo el algoritmo Rate Monotonic si y s´ olo si L = max{1≤i≤n} Li ≤ 1. (3.6) donde: Los elementos de Si son los puntos de planificaci´on en los que la tarea i es planificada. Es decir, los instantes de tiempo en que se cumple el plazo de respuesta y los tiempos de arribo de las tareas de mayor prioridad que i. Si = {k · Tj |j = 1, ..., i; k = 1, ..., bTi /Tj c}. (3.7) Wi (t) mide la cantidad de tiempo de procesador requerido por i tareas, del instante o al instante t. Wi (t) = i X Cj · dt/Tj e. (3.8) j=1 Li (t) = Wi (t)/t. Cinvestav-IPN Secci´ on Computaci´ on (3.9) Oscar Miranda G´ omez 3.5. Planificadores Basados en Prioridades Est´ aticas 59 Esta condici´on de planificabilidad se realiza a partir del instante cr´ıtico. El instante cr´ıtico es el instante de tiempo en el cual todas las tareas presentan su m´aximo tiempo de respuesta. Este instante se presenta cuando todas las tareas comienzan a ejecutarse al mismo tiempo. La condici´on del teorema 3.5.3 es exacta. Si el conjunto de tareas no es planificable bajo esta condici´on, se debe a que ´este no es planificable (bajo ning´ un algoritmo de planificaci´on), por lo que en este caso, al menos una tarea perder´a su plazo de respuesta. Ejemplo: La tabla 3.5 muestra un conjunto de tareas peri´odicas el cual ser´a planificado con el algoritmo de planificaci´on RM, Podemos observar que el factor de utilizaci´on total es de 0.928, que es mayor que U(3). Por tanto, la condici´on 3.2 no nos permite asegurar nada sobre si se pueden garantizar los plazos de las tres tareas. Sin embargo, el factor de utilizaci´on de las dos primeras tareas (τ1 y τ2 ) es igual a 0.678 < U(2) = 0.828, por lo que podemos asegurar que τ1 y τ2 terminan siempre dentro de sus plazos de respuesta. T area Ti Ci Utilizaci´ on 1 7 3 0.428 2 12 3 0.250 3 20 5 0.250 0.928 Tabla 3.5: Conjunto de Tareas que no satisface 3.2. Se aplica la condici´on 3.7 para comprobar si el plazo de respuesta de τ3 est´a garantizado. Para ello, se examina la ejecuci´on del sistema en el intervalo de tiempo [0,20], suponiendo que t = 0 es un instante cr´ıtico. Obteni´endose los siguientes puntos de planificaci´on de τ3 : S3 = {1 ∗ 7, 2 ∗ 7, 1 ∗ 12, 1 ∗ 20} = {7, 12, 14, 20} (3.10) como se observa en la Figura 3.8, coinciden con los instantes l´ımites de τ1 , τ2 y τ3 en el intervalo [0,20]. Aplicando la condici´on 3.5 se obtiene la cantidad de tiempo de procesador requerido por las i tareas, en el instante t, la tabla 3.6 muestra este hecho. Puesto que, al menos en un caso (t = 20), se verifica la condici´on 3.5, podemos concluir que τ3 est´a garantizada y dado que esta tarea es la de menor prioridad, el conjunto de tareas Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 60 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real t W3 (t) 7 (3*1 + 3*1 + 5*1 ) = 11 12 (3*2 + 3*1 + 5*1) = 14 14 (3*2 + 3*2 + 5*1) = 17 20 (3*3 + 3*2 + 5*1) = 20 Tabla 3.6: Carga en el instante t es planificable. Figura 3.8: Puntos de Planificaci´on. 3.5.2. Deadline Monotonic (DM) En 1982 Leung y Whitehead[26] proponen un esquema de asignaci´on de prioridades fijas denominado Deadline Monotonic (DM), el cual consiste en asignar la prioridad m´as alta a las tareas que tengan plazos mas cortos. Es decir, la tarea con el plazo m´as corto se le asigna la prioridad m´as alta. En DM, el plazo puede ser menor que el periodo, sin embargo, DM es equivalente a RM cuando el per´ıodo = plazo de respuesta. Teorema 3.5.4 [26] El algoritmo DM es ´ optimo dentro de los esquemas de asignaci´ on de prioridades fijas. Esta pol´ıtica de planificaci´on es en principio id´entica al RM pero eliminando una restricci´on: las tareas pueden tener un plazo de ejecuci´on menor o igual a su per´ıodo. Las prioridades Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 3.6. Planificadores Basados en Prioridades Din´ amicas 61 se asignan de forma inversamente proporcional al plazo m´aximo de ejecuci´on. Se puede ver que el RM es un caso particular del DM en el que todas las tareas tienen un plazo de ejecuci´on igual a su per´ıodo. 3.6. Planificadores Basados en Prioridades Din´ amicas En este tipo de planificaci´on las prioridades de las tareas son asignadas durante la ejecuci´on del sistema, sin embargo todas las tareas y sus par´ametros temporales son conocidos desde el inicio de la ejecuci´on. En la planificaci´on basada en prioridades din´amicas (on-line, en l´ınea), se realiza un an´alisis de planificabilidad fuera de linea. Sus principales ventajas son: Es posible aprovechar mejor el procesador. Debido a que el planificador asigna en forma din´amica las prioridades de las tareas, el CPU puede utilizarse de forma mas eficiente que en el caso de la planificaci´on por prioridades est´aticas. y sus principales desventajas son: En una sobrecarga del sistema no es posible predecir que tareas pierden sus plazos de respuesta. Lo que es mas grave, es que en una sobrecarga, la perdida de plazos de algunas tareas puede producir un efecto en cascada de perdida de plazos de otras tareas. Se incrementa la sobrecarga causada por la planificaci´on. Esto se debe a que la planificaci´on continuamente tiene que ordenar las tareas por orden de prioridad, lo cual introduce sobrecarga al sistema. 3.6.1. Earliest Deadline First (EDF) Es uno de los algoritmos m´as conocidos para el esquema de asignaci´on din´amica es el algoritmo de planificaci´on guiado por plazos (DDSA: Deadline Driven Scheduling Algorithm), al cual posteriormente se le denomin´o como el plazo m´as pr´oximo primero (EDF: Earliest Deadline First). En el algoritmo EDF las prioridades se asignan en forma din´amica. La pol´ıtica de asignaci´on de prioridades consiste en asignar la prioridad mas alta a la tarea con plazo mas cercano. Para este algoritmo la condici´on de planificabilidad se define a continuaci´on. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 62 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real Teorema 3.6.1 La condici´on necesaria y suficiente para que un conjunto de tareas peri´ odicas tenga una planificaci´on factible mediante el algoritmo EDF es: U ≤1 (3.11) Esta condici´on de planificabilidad permite que EDF consiga un factor de utilizaci´on del 100 % para los conjuntos de tareas que planifica. Por lo que podemos decir que EDF es ´optimo globalmente, es decir, que si existe un algoritmo que propocione una planificaci´on factible con un determinado conjunto de tareas peri´odicas, entonces EDF tambi´en proporcionar´a una planificaci´on factible para dicho conjunto de tareas. Ejemplo: La tabla 3.7 muestra un conjunto de tareas, cuya utilizaci´on total es del 82 % y la Figura 3.9 muestra el comportamiento de la ejecuci´on de las tareas bajo el algoritmo de planificaci´on EDF. Como puede observarse no hay p´erdida de plazos ya que cumple con la condici´on 3.11 T area Ti Ci Utilizaci´ on 1 30 10 0.333 2 40 10 0.250 3 50 12 0.240 0.823 Tabla 3.7: Conjunto de tareas, cuya utilizaci´on es del 82 % Figura 3.9: Planificaci´on de las tareas de la tabla 3.7 bajo EDF. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 3.6. Planificadores Basados en Prioridades Din´ amicas 3.6.2. 63 Least Laxity First (LLF) El algoritmo LLF consiste en asignar las prioridades a las tareas de manera inversamente proporcional a su holgura. Es decir, le asigna la prioridad m´as alta a la tarea con la menor holgura. La holgura (laxity) de una tarea con tiempo de respuesta Di en cualquier instante de tiempo t es: holgura = Di − t − Ci (t) (3.12) donde Ci (t), es el tiempo de c´omputo pendiente por ejecutarse para que la tarea termine. Consideremos el siguiente conjunto de tareas Γ = {τ1 =(6,3), τ2 =(8,2), τ3 =(70,2)}. Para τ1 , en alg´ un instante de tiempo t antes que su tiempo de c´omputo finalice, su holgura es: 6 − t − (3 − t). Supongamos que la tarea τ1 es desalojada en el instante de tiempo t = 2 por la tarea τ3 que se ejecuta desde el tiempo 2 al 4. Durante este intervalo, la holgura de τ1 decrece de 3 a 1. (En el tiempo 4, el resto del tiempo de ejecuci´on de τ1 es 1, es decir 6-4-1=1). La Figura 3.10 muestra la planificaci´on del conjunto de tareas bajo LLF. Figura 3.10: Planificaci´on de tareas bajo el algoritmo LLF. El algoritmo LLF tambi´en puede conseguir, al igual que con EDF, un factor de utilizaci´on del 100 %. En el algoritmo EDF no es necesario conocer de los tiempos de c´omputo de las tareas, mientras que el algoritmo LLF si se necesita de dicho par´ametro temporal. Esto es una desventaja debido a que la holgura es calculada en base al tiempo m´aximo de c´omputo, Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 64 Cap´ıtulo 3. Planificaci´ on en Sistemas de Tiempo Real es decir, la determinaci´on de la holgura es inexacta ya que el algoritmo asume el peor caso para calcular la holgura. Como se puede observar, los algoritmos con manejo de prioridad din´amica tienen cierta ventaja sobre los algoritmos de prioridad fija. La ventaja radica en el hecho en que la cota l´ımite (m´axima) es del 100 % para cualquier conjunto de tareas. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 4 Dise˜ no del Kernel de Tiempo Real En la actualidad el avance de la tecnolog´ıa ha permitido que cada vez mas, los aparatos electr´onicos sean de menor tama˜ no y capaces de realizar cualquier tarea de manera aparentemente “inteligente”. La mayor´ıa de estos aparatos contiene un procesador y un peque˜ no sistema operativo empotrado el cual es capaz de controlar todo el hardware de manera eficiente, sin embargo, no es suficiente con que operan correctamente, si no que adem´as, se requiere que estos sean seguros y que respondan a eventos en un tiempo de respuesta acotado. Como proyecto de esta tesis, se desarroll´o un kernel de tiempo real. Como ya se hab´ıa mencionado antes, un Kernel es el m´odulo central de cualquier sistema operativo. Es la parte que se carga primero y permanece en la memoria principal. Normalmente, el kernel es el responsable por la administraci´on de la memoria, los procesos, las tareas y los discos. En este cap´ıtulo se describe la filosof´ıa de dise˜ no que se llevo a cabo para implementar un kernel de tiempo real para el control de procesos, as´ı como la implementaci´on de cada una de las partes que comprende al sistema, tal es el caso de las primitivas y los manejadores (en donde se menciona para cada objeto la estructura que utilizan). Tambi´en se explican las consideraciones que se deben tener para inicializarlo y algunos otros puntos generales que ayudaran a comprender mejor como fue dise˜ nado. 65 66 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real 4.1. Arquitectura General En la Figura 4.1 se presenta la arquitectura del Kernel en tiempo real. En el nivel m´as bajo se encuentran los distintos dispositivos que controla el Kernel. En el siguiente nivel est´an las distintas funciones del kernel, conocidas como primitivas. En la parte superior, se encuentran los procesos del usuario quienes interaccionan con el Kernel. El Kernel soporta una arquitectura con un s´olo procesador, en el cual los procesos se ejecutan concurrentemente. El Kernel se dise˜ n´o en el lenguaje de programaci´on C, propios de la familia de procesadores Intel 80x86. Figura 4.1: Arquitectura del Kernel. 4.1.1. Estructura General de las Primitivas Todas las primitivas en el kernel, a´ un cuando realizan funciones diferentes, tienen la siguiente estructura general1 : Nombre de la primitiva([par´ ametros]) { Deshabilitar interrupciones Validar los par´ ametros 1 Todo lo que se encuentra dentro de “[ ]” es opcional y puede o no, contenerlo la primitiva. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.1. Arquitectura General 67 Si hay error en los par´ ametros entonces Se llama al manejador de errores y excepciones; Si no hubo error Se ejecuta la funci´ on de la primitiva; [ Si alg´ un proceso se alist´ o o bloque´ o entonces Llamar al manejador del cpu ] Habilitar interrupciones } Como se muestra en el pseudoc´odigo, en cada primitiva del kernel, lo primero que se hace es deshabilitar las interrupciones, este paso es muy importante ya que todas las primitivas deben ser at´omicas debido a que las operaciones que realizan son importantes y no se deben interrumpir. El siguiente paso, es verificar los par´ametros que recibe la primitiva para detectar los posibles errores que pudieran ocurrir, si se encuentra alg´ un error, se manda a llamar al manejador de errores envi´andole como par´ametro el identificador o c´odigo de error. Si no hubo errores, se ejecuta la primitiva con la seguridad de que todo est´a en orden. Algunas primitivas como las de manejo de tiempo o buzones necesitan llamar al manejador del procesador (CPU), ya que alg´ un proceso es bloqueado o ingresado a la cola de procesos listos y es necesario que sean tomados en cuenta para la planificaci´on. Antes de salir de la primitiva, es necesario volver a habilitar las interrupciones para que los procesos puedan ser interrumpidos cuando se les termine su tiempo de ejecuci´on. 4.1.2. Estructura de los Procesos o Tareas Las tareas en el kernel se definen de la misma forma en que se crean las funciones en C est´andar. El c´odigo de una t´ıpica tarea se muestra en la Tabla 4.1, ah´ı podemos apreciar que se pueden declarar variables locales (de manera opcional) as´ı como c´odigo que s´olo se desea ejecutar una sola vez al iniciar la tarea. Todas las tareas tienen un ciclo infinito “while (1)”, este es el cuerpo de la tarea y aqu´ı va el c´odigo que deseamos que se ejecute peri´odicamente. Dentro de este ciclo infinito, de manera opcional se puede utilizar la primitiva Fin de Ciclo la cual se puede utilizar en aquellas tareas en las que se desea que el cuerpo de la tarea s´olo Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 68 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real se ejecute una vez por cada per´ıodo. 1. 2. void NombreTarea() { 3. // Variables Locales [ int a,b,c; 4. // Inicializaci´ on de variables 5. a=10; 6. ] 7. ... 8. while(1) 9. { // Cuerpo de la tarea 10. ... 11. ... 12. [Fin_de_Ciclo();] 13. 14. } } Tabla 4.1: Estructura de las Tareas o Procesos. 4.1.3. Prioridades El kernel maneja varios niveles de prioridad, el n´ umero de prioridades m´aximo se puede cambiar en el archivo de configuraci´on del kernel llamado CONFIG.H (ver secci´on 4.4.1). 2 Las prioridades son est´aticas y el usuario es quien le asigna las prioridades a las tareas, a excepci´on de la primer tarea que tiene la prioridad 0, y la u ´ltima tarea que tiene la prioridad m´as baja en el Kernel. 4.1.4. Procesos o Tareas Inicialmente el Kernel esta configurado para trabajar con un m´aximo de 32 procesos, sin embargo el usuario en base a sus necesidades, puede aumentar el n´ umero de los procesos a controlar por el Kernel. En cuanto al manejo de procesos, el Kernel trabaja con procesos est´aticos, esto es, que desde la inicializaci´on del sistema los procesos ya se encuentran definidos y no cambian durante la vida de ´este. Dentro del Kernel, existen dos procesos importantes llamados: primero y u ´ltimo los cuales son activados al iniciar el Kernel. Primer Proceso El proceso primero es la primer tarea que se ejecuta en el kernel, tiene la mayor prioridad (0 ) y es la encargada de activar a los dem´as procesos o tareas que se van a ejecutar en el 2 Por defecto ha sido inicializado con 15 niveles de prioridad en donde 0 es la m´ axima prioridad y 14 la menor. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.1. Arquitectura General 69 sistema. Este proceso antes de terminar su ejecuci´on se eliminada del sistema y no se vuelve a ejecutar jam´as en el Kernel (ver Tabla 4.2). 1. 2. void PrimerT() { register int proc; 3. //Activa todas las tareas en el kernel 4. for (proc=1;proc<=NTAREAS;proc++) 5. { activa(proc); } 6. Elimina_Proceso(); //se elimina de la cola de procesos listos el mismo 7. while(1) 8. 9. { } } Tabla 4.2: C´odigo del Proceso “Primer Tarea”. ´ Ultimo Proceso El proceso u ´ltimo es una tarea que tiene la finalidad de s´olo ejecutarse cuando el kernel no tiene otra tarea por ejecutar. La prioridad de este proceso es la m´as baja que existe dentro del kernel (MAXPRIO-1) y como se puede apreciar en la Tabla 4.3, este proceso no tiene mas que un ciclo infinito (que es el cuerpo de cualquier proceso) el cual s´olo consume tiempo de procesador mientras no hay tareas listas para ejecutarse. 1. 2. void UltimaT() { 3. while(1) 4. 5. { } } ´ Tabla 4.3: C´odigo del Proceso “Ultima Tarea”. 4.1.5. BCP de los Procesos en el Kernel Como se vi´o en la secci´on 2.7.6, cada proceso tiene asociada una estructura llamada Bloque de Control de Proceso (BCP) la cual contiene la informaci´on necesaria para el control del proceso. La estructura del BCP en el Kernel est´a representada en la Figura 4.2, en el cual se puede apreciar que la informaci´on est´a ordenada de la siguiente manera: 1) Informaci´ on del proceso: Aqu´ı se encuentra almacenado el identificador del proceso, el estado en que se encuentra durante la ejecuci´on del Kernel (listo, suspendido, etc.), la direcci´on y el segmento de c´odigo inicial del proceso (CS e IP ), el segmento y el Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 70 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real Figura 4.2: Bloque de Control de Procesos en el Kernel. puntero a los datos en la pila (SS y SP ), y la pila que le corresponde al proceso. En la pila se almacena el contenido de sus registros (cs, ip, bp, di, si, ds, es, dx, cx, bx, ax y flags) as´ı como las direcciones de las instrucciones que ejecuta el proceso. Los registros incluidos en el stack son indispensables para que el Kernel pueda llevar a cabo el cambio de contexto. 2) Informaci´ on para el planificador: Aqu´ı se encuentran los datos necesarios para que el proceso pueda ser planificado. Contiene informaci´on como la prioridad, el tiempo de c´omputo, el plazo, el tiempo de activaci´on y el tiempo de ejecuci´on. Estos datos son necesarios para que las pol´ıticas de planificaci´on puedan calcular cuando le corresponde ejecutarse a cada proceso. 3) Informaci´ on de memoria utilizada en buzones: S´olo contiene un apuntador a una direcci´on de memoria reservada para almacenar un mensaje del buz´on en caso de que el proceso sea introducido a la cola de procesos bloqueados por buz´on (cpbb). F´ısicamente, el bloque de control de procesos en el Kernel est´a representado por la estructura de la Tabla 4.4. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.1. Arquitectura General 71 1. struct BCP { 2. unsigned estado; 3. unsigned int Cs,Ip; 4. unsigned char pila[tam_pila]; 5. unsigned prioridad; 6. unsigned long tcc; // Tiempo de Computo Consumido 7. unsigned long TA; 8. unsigned long Periodo,TComputo; 9. unsigned long P; // Plazo 10. struct MENSAJE PtrMje; // Tiempo de Activaci´ on 11. }PROCESO[MaxPro]; Tabla 4.4: Estructura del Bloque de Control de Procesos (BCP). 4.1.6. Estados de los Procesos en el Kernel Dentro del Kernel, cada proceso puede encontrarse en cualquiera de los siguientes estados, tal como se describe en la Figura 4.3: Figura 4.3: Estados de los Procesos en el Kernel. Nuevo: Este estado es con el que empiezan los procesos al iniciar el Kernel, esto indica que existe el proceso pero que no ha sido activado y por lo tanto no se encuentra listo para su ejecuci´on. Listo: En este estado, el proceso se encuentra listo para ejecutarse y espera a que se le asigne el procesador. Ejecuci´ on: En este estado, el proceso tiene el control del procesador. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 72 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real Bloqueado: En este estado, el proceso se encuentra bloqueado en alg´ un recurso, como puede ser un sem´aforo, o un un buz´on. Retrasado: En este estado el proceso se encuentra bloqueado, esperando por un tiempo determinado antes de regresar al estado de listo. Eliminado: En este estado se encuentran los procesos que ya han terminado su ejecuci´on y que ya no van a volver a utilizarse dentro del Kernel. 4.1.7. Transiciones entre Estados Los procesos cambian de estado por alguna de las siguientes razones (ver Figura 4.3): 1. el proceso es creado y activado. 2. se le asigna el procesador. 3. se le quita el procesador debido a: un bloqueo, el alistamiento de un proceso con mayor prioridad o por el fin de su tiempo de c´omputo. 4. el proceso se retrasa. 5. ocurre una vez que termina su tiempo de retraso, quedando listo para ejecutarse. 6. el proceso se bloquea por un recurso o interrupci´on. 7. obtuvo el recurso que esperaba y queda listo para ejecutarse. 8. el proceso se elimina a s´ı mismo. 4.1.8. Primitivas y Manejadores del Kernel Para tener el control de todos los procesos y eventos que ocurren en el kernel, este hace uso de las primitivas y los manejadores. Como se puede apreciar en la arquitectura del kernel (ver Figura 4.1), los manejadores se encuentran estrechamente relacionados con el hardware por lo que son los u ´nicos que se pueden comunicar con ´el. En cuanto a las primitivas, estas no se pueden comunicar con el hardware, pero si con los procesos y los manejadores, esto quiere decir, que los procesos s´olo pueden utilizar las primitivas, quienes a su vez se tienen que comunicar con los manejadores para poder utilizar parte del hardware. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.2. Primitivas 4.2. 73 Primitivas 4.2.1. Primitivas de Procesos Aqu´ı se definen las primitivas para el manejo de procesos como son: la primitiva “Activa”, la primitiva “Elimina Proceso” y la primitiva “Fin de Ciclo” (Figura 4.4). La estructura de Figura 4.4: Primitivas de Procesos. las primitivas de procesos son las siguientes: Activa : NOMBRE: void activa(unsigned int num). ´ Se encarga de activar un proceso para que se ejecute en el Kernel. FUNCION: ENTRADAS: El identificador del proceso a activar (num). SALIDAS: El proceso almacenado en la cola de listos. Activa se encarga de indicar al Kernel que el proceso est´a listo para ejecutarse cambi´andole su estado en el BCP a listo e insert´andolo en la cola de procesos listos mediante la primitiva inserta del manejador de colas, la u ´nica condici´on que se pone para poder activar un proceso es, que el proceso que activa al nuevo proceso debe tener mayor prioridad (ver linea 7 de la Tabla 4.5). Elimina Proceso : NOMBRE: void Elimina_Proceso(). ´ Se encarga de eliminar al proceso que invoca esta primitiva, por lo que una FUNCION: vez eliminado, este es incapaz de volverse a ejecutar en el Kernel. ENTRADAS: El proceso en ejecuci´on (idposeedor). SALIDAS: El proceso eliminado del Kernel. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 74 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real 1. void activa(unsigned int num) 2. { //El numero del proceso debe estar dentro del rango permitido 3. if (num>=MaxPro) 4. ERROR(7); 5. else 6. { //El proceso que lo activa debe tener mayor prioridad 7. if(PROCESO[idposeedor].prioridad <= PROCESO[num].prioridad) 8. { //En el kernel el que tenga un numero menor es el que tiene 9. //mayor prioridad, Ejemplo: el de prioridad=1 es mayor que 10. //el que tenga prioridad=10. 11. PROCESO[num].estado=LISTO; 12. Inserta(cpl,PROCESO[num].prioridad,num); 13. } 14. else 15. ERROR(8); 16. } 17. } Tabla 4.5: Primitiva Activa. La primitiva Elimina Proceso le indica al Kernel que el proceso ha terminado de realizar todas sus funciones y que ya no va a ser u ´til de nuevo en el sistema, para esto, le cambia su estado a eliminado en el BCP del proceso y lo saca de la cola de procesos listos mediante la primitiva elimina del manejador de colas. La primitiva Elimina Proceso s´olo la puede llamar el proceso en ejecuci´on (IdPoseedor) y por lo tanto al finalizar la primitiva se invoca al cambio de contexto para que se le asigne el procesador a otro proceso (ver la linea 7 de la Tabla 4.6). 1. void Elimina_Proceso() 2. { {disable(); 3. // cambia el estado del proceso a ELIMINADO 4. PROCESO[idposeedor].estado= ELIMINADO; 5. Elimina(cpl,idposeedor); 6. enable(); 7. 8. CambiaContexto(); //Saca el proceso de la cola de activos // Llama al cambio de contexto } Tabla 4.6: Primitiva Elimina Proceso. Fin de Ciclo : NOMBRE: void Fin_de_Ciclo(). ´ Indica al Kernel que una tarea ya cumpli´o con su ciclo de ejecuci´on en un FUNCION: per´ıodo. ENTRADAS: Ninguna. SALIDAS: Ninguna. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.2. Primitivas 75 La primitiva Fin de Ciclo es utilizada para indicar al Kernel que la tarea ya cumpli´o con el ciclo de ejecuci´on y que no necesita ejecutarse nuevamente el c´odigo hasta su siguiente tiempo de activaci´on. 1. 2. void Fin_de_Ciclo() { 3. while (PROCESO[idposeedor].FC==VERDADERO) 4. 8. PROCESO[idposeedor].FC = VERDADERO; { // Se mantiene aqui hasta que inicie su tiempo de activaci´ on } } Tabla 4.7: Primitiva Fin de Ciclo de la Tarea. 4.2.2. Primitivas de Tiempo El Kernel permite que un proceso pueda retrasarse por un lapso de tiempo determinado, para lograrlo se hace uso de las primitivas de tiempo “Retrasa” y “Revisa ProcRetrasado” (ver Figura 4.5). Las estructuras de estas primitivas de tiempo son las siguientes: Figura 4.5: Primitivas de Tiempo. Retrasa : NOMBRE: void retrasa(unsigned long tiempo). ´ Retrasa el proceso que la llama por un tiempo determinado en milisegundos. FUNCION: Este proceso es sacado de la cola de listos y almacenado en la cola de procesos retrasados. ENTRADAS: El identificador de proceso a retrasar (idposeedor) y el tiempo (tiempo) que va a durar en la cola de retrasados. El rango de retraso es de 1 hasta 4,294,967,295 milisegundos. SALIDAS: El identificador de proceso a ejecutarse. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 76 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real La primitiva Retrasa permite que un proceso pase al estado de retrasado por un tiempo determinado, para lograrlo, el proceso es eliminado de la cola de procesos listos e insertado en la cola de procesos retrasados y su estado es cambiado a “retrasado”. Por u ´ltimo, como esta primitiva es llamada por el proceso en ejecuci´on, al terminar de ejecutarse se invoca al cambio de contexto para que otro proceso pueda hacer uso del procesador (ver Tabla 4.8). 1. 2. void retrasa(int tiempo) { disable(); 3. //Si el tiempo es menor a 1... 4. if(tiempo<1) 5. // tiempo invalido 6. ERROR(6); 7. else 8. {//saca el proceso de la cola de activos 9. //Saca el proceso de la cola de procesos listos 10. Elimina(cpl,idposeedor); 11. // y lo inserta en la cola de retrasados 12. inserta_r(idposeedor,tiempo); 13. PROCESO[idposeedor].estado=RETRASADO; 14. } 15. enable(); 16. 17. CambiaContexto(); } Tabla 4.8: Primitiva Retrasa. Revisa ProcRetrasado : NOMBRE: void Revisa_ProcRetrasado(void). ´ FUNCION: Actualiza el tiempo de retrasa y alista a todos los procesos que hayan cumplido con su tiempo de retraso. ENTRADAS: Ninguna. SALIDAS: Ninguna. La primitiva Revisa ProcRetrasado por su parte, se encarga de actualizar el tiempo de retraso que falta para activar los procesos y en caso de que alguno haya cumplido con su tiempo, este es alistado de nuevo coloc´andolo en la cola de procesos listos y cambiando su estado a “listo” (ver Tabla 4.9). Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.2. Primitivas 77 1. void Revisa_ProcRetrasado(void) 2. { unsigned val; 3. disable(); 4. if (cpr[0][1] > 0) 5. { cpr[0][1]--; 6. // Es while porque puede que varias tareas terminen su retraso al mismo tiempo. 7. while (cpr[0][1]==0 && cpr[0][0]) 8. { val=saca_r(); 9. Inserta(cpl,PROCESO[val].prioridad,val); 10. PROCESO[val].estado=LISTO; 11. }} 12. 13. enable(); } Tabla 4.9: Primitiva Revisa Proceso Retrasado. 4.2.3. Primitivas de Sem´ aforos Las cuatro primitivas utilizadas en el Kernel para manejar los sem´aforos son: “CreaSem”, “IsColSemVacia”, “Espera” y “Senial”, las cuales se pueden ver Figura 4.6. Figura 4.6: Primitivas de Sem´aforo. Iniciar Sem´ aforo: En esta primitiva se le da un valor inicial (positivo) a la variable del sem´aforo, con lo cual se crean una cola asociada al sem´aforo. En esta cola, se incluir´an los procesos bloqueados por este recurso. CreaSem : NOMBRE: void CreaSem(unsigned int idSem,unsigned int valor, char nomsem[]). ´ Crea un sem´aforo determinado, d´andole un nombre y valor inicial. FUNCION: ENTRADAS: El identificador del sem´aforo a crear (idSem), un valor inicial (valor: 0 o 1 para binarios) y el nombre del sem´aforo (nomsem). SALIDAS: El sem´aforo creado y listo para utilizarse. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 78 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real 1. 2. void CreaSem(unsigned int idSem,unsigned int valor,char nomsem[]) { disable(); 3. if(idSem >= MaxSem) 4. ERROR(9); 5. else 6. { if(valor>CuentaMaxima) 7. ERROR(10); else 8. { if( SEMAFORO[idSem].creado == VERDADERO) 9. ERROR(11); 10. else 11. { SEMAFORO[idSem].cont=valor; 12. SEMAFORO[idSem].Tam=0; 13. SEMAFORO[idSem].creado=VERDADERO; 14. CopiaCadena(SEMAFORO[idSem].nombre,nomsem); 15. 16. } 17. } 18. 19. // se nombra al sem´ aforo } enable(); } Tabla 4.10: Primitiva Crea Sem´ aforo Se˜ nal: Esta primitiva permite incrementar en una unidad, a la variable del sem´aforo. Si la variable del sem´aforo es negativa indicar´a que existe alg´ un proceso bloqueado (en la cola de este sem´aforo). Por lo tanto si al ejecutar la primitiva se˜ nal, el contador es negativo, alg´ un proceso bloqueado en la cola de este sem´aforo (el que se encuentre al principio de la cola), se pasar´a a la cola de procesos listos. En este caso, el Kernel provocar´a un cambio de contexto para verificar si el proceso desbloqueado, es de mayor prioridad que el proceso en ejecuci´on. Si al ejecutar la primitiva se˜ nal no existen procesos bloqueados (el contador es cero o positivo), se incrementa el contador del sem´aforo y el proceso continuar´a su ejecuci´on. Senial : NOMBRE: void Senial(unsigned int idSem). ´ Manda una se˜ FUNCION: nal al sem´aforo a desocupar. Si existen procesos bloqueados, se alista al de mayor prioridad. ENTRADAS: El identificador de sem´aforo a desocupar. SALIDAS: El sem´aforo libre y disponible para su uso. Espera: Esta primitiva permite decrementar en una unidad a la variable del sem´aforo. Si despu´es de decrementar esta variable, su valor es negativo, el proceso que ejecuta esta primitiva es enviado a la cola del sem´aforo y sacado de ejecuci´on. En este caso, el Kernel Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.2. Primitivas 79 1. void Senial(unsigned int idSem) 2. { unsigned int idProc; 3. unsigned int proc; 4. disable(); 5. if( idSem >= MaxSem) 6. { 7. ERROR(9); 8. } 9. else 10. { if(SEMAFORO[idSem].creado == FALSO) 11. { 12. ERROR(12); 13. } 14. else 15. { //Si la cola esta vacia... 16. if(IsColSemVacia(idSem)) 17. //Solo aumenta el contador del sem´ aforo 18. SEMAFORO[idSem].cont++; 19. else 20. //Si no, alista al de mayor prioridad 21. { //Busca al de mayor prioridad 22. idProc=BuscaMayor(SEMAFORO[idSem].cpbs); 23. //Lo saca de la cola de procesos bloqueados por sem´ aforo 24. proc=Saca(SEMAFORO[idSem].cpbs,PROCESO[idProc].prioridad); 25. // y lo inserta en la cola de procesos listos 26. Inserta(cpl,PROCESO[proc].prioridad,proc); 27. //Actualiza el conteo de los procesos bloqueados por sem´ aforo 28. SEMAFORO[idSem].Tam--; 29. //Se actualiza su estado 30. PROCESO[proc].estado = LISTO; 31. //Obliga a un cambio de contexto 32. CambiaContexto(); 33. } 34. } 35. } 36. 37. enable(); } Tabla 4.11: Primitiva Se˜ nal invocar´a a la rutina de cambio de contexto para ejecutar al siguiente proceso de la cola de listos. Por el contrario, si despu´es de ejecutar la primitiva espera, la variable del sem´aforo contiene un valor cero o positivo, el proceso continuar´a su ejecuci´on. Espera : NOMBRE: void Espera(unsigned int idSem). ´ FUNCION: Se˜ naliza el sem´aforo a ocupar, si esta vac´ıo le da el recurso, esto es, contin´ ua su ejecuci´on sin problemas, pero si estaba ocupado lo bloquea. ENTRADAS: El identificador de sem´aforo a utilizar. SALIDAS: El sem´aforo ocupado. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 80 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real 1. 2. void Espera(unsigned int idSem) { disable(); 3. if( idSem >= MaxSem) 4. ERROR(9); 5. else 6. { if(SEMAFORO[idSem].creado == FALSO) 7. ERROR(12); 8. else 9. { SEMAFORO[idSem].cont--; 10. if(SEMAFORO[idSem].cont < 0) //Si la cola no esta vac´ ıa 11. { //Bloquea el proceso que pidi´ o el sem´ aforo 12. //elimin´ andolo de la cola de procesos listos 13. Elimina(cpl,idposeedor); 14. //e insert´ andolo en la cola de procesos bloqueados por sem´ aforo 15. Inserta(SEMAFORO[idSem].cpbs,PROCESO[idposeedor].prioridad,idposeedor); 16. SEMAFORO[idSem].Tam++; //lleva el conteo de los procesos bloqueados por sem´ aforo 17. PROCESO[idposeedor].estado = BLOQUEADO; //Se actualiza su estado 18. CambiaContexto(); //Obliga a un cambio de contexto 19. }}} 20. 21. enable(); } Tabla 4.12: Primitiva Espera IsColSemVacia : NOMBRE: unsigned int IsColSemVacia(unsigned int idSem). ´ FUNCION: Se encarga de revisar si la cola de procesos bloqueados por sem´aforo est´a vac´ıa, o no. ENTRADAS: El identificador del sem´aforo a revisar. SALIDAS: FALSO si la cola tiene elementos o VERDADERO si esta vac´ıa. 1. 2. unsigned int IsColSemVacia(unsigned int idSem) { disable(); 3. if(SEMAFORO[idSem].Tam > 0) 4. return FALSO;//cola con elementos 5. else 6. return VERDADERO; //cola vacia 7. 8. enable(); } Tabla 4.13: Primitiva que revisa si la Cola de Sem´aforos est´a vac´ıa. En la Figura 4.7 se muestran 2 tareas haciendo acceso de un sem´aforo para implementar regiones cr´ıticas. El uso de estas regiones cr´ıticas permite a cada proceso accesar una variable compartida en forma exclusiva. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.2. Primitivas 81 Figura 4.7: Utilizaci´on de los sem´aforos en el Kernel. 4.2.4. Primitivas de Buz´ on Las primitivas de buz´on, como se muestran en la Figura 4.8 son: “CreaBuzon”, “RecibirMje” y “EnviarMje”. Figura 4.8: Primitivas de Buz´on. Crear Buz´ on: Esta primitiva permite crear la estructura de datos que define al buz´on y su cola de procesos asociada. CreaBuzon : NOMBRE: void CreaBuzon(unsigned int IdProceso,unsigned int IdBuzon). ´ Crea un buz´on y lo inicializa indicando que ya ha sido creado y anotando FUNCION: Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 82 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real el identificador del proceso que lo cre´o. ENTRADAS: El identificador del buz´on a crear (unsigned int IdBuzon) y el identificador del proceso que lo desea crear (IdProceso). SALIDAS: El Buz´on creado o en caso de fallo, un identificador con la descripci´on del error generado. 1. 2. void CreaBuzon(unsigned int IdProceso,unsigned int IdBuzon) { disable(); 3. if (IdBuzon >= MaxBuz) 4. ERROR(14); 5. else 6. {if (dcb[IdBuzon].Creado) 7. ERROR(15); 8. else // No hubo errores por lo tanto se crea el buz´ on 9. { dcb[IdBuzon].Creado=1; 10. dcb[IdBuzon].BuzProceso=IdProceso; 11. } 12. } 13. 14. enable(); } Tabla 4.14: Primitiva Crea Buz´ on Enviar Mensaje: Mediante esta primitiva es posible enviar un mensaje en formato ASCII al buz´on indicado (el cual previamente tuvo que haber sido creado). Si al enviar un mensaje alguna tarea se encontraba bloqueada esperando mensajes, esta tarea ser´a desbloqueada y enviada a la cola de procesos listos. Si un proceso env´ıa un mensaje al buz´on y el buz´on se encuentra lleno, provocar´a que el proceso se incluya en la cola del buz´on. Este proceso permanecer´a en esta cola hasta que otro proceso reciba mensajes y libere suficiente espacio del buz´on. EnviarMje : NOMBRE: void EnviarMje (unsigned int IdBuzon,struct MENSAJE Mensaje). ´ Env´ıa un mensaje a un buz´on determinado. FUNCION: ENTRADAS: El identificador del buz´on donde se va a almacenar el mensaje (IdBuzon) y el mensaje a enviar. SALIDAS: El mensaje almacenado en el buz´on o en caso de error, un identificador con la explicaci´on del fallo. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.2. Primitivas 1. 2. 83 void EnviarMje (unsigned int IdBuzon,struct MENSAJE Mensaje) { unsigned int Ultimo,IdProceso,Prio,Proc; 3. disable(); 4. if (IdBuzon >= MaxBuz) ERROR(14);//El idBuzon debe estar en el rango permitido 5. else 6. {if (dcb[IdBuzon].Creado==0) ERROR(16);// El buz´ on debe estar creado 7. else 8. // Si los buzones cumplen los requisitos de arriba contin´ ua... {IdProceso=Mensaje.ProCreo; //Obtiene el Id del proceso que creo el mensaje 9. Prio=PROCESO[IdProceso].prioridad; //Obtiene la prioridad del proceso 10. if (dcb[IdBuzon].UltMje==MaxMje) //Comprueba si hay espacio en la cola de buzones 11. //No hay espacio para el mensaje por lo que se env´ ıa a la cola de Bloqueados por Buz´ on. 12. {PROCESO[IdProceso].PtrMje=Mensaje; //Copia al PCB del proceso a bloquear 13. Elimina(cpl,IdProceso); // sacar proceso de la cola de procesos listos 14. Inserta(cpbb[IdBuzon],Prio,IdProceso); //y lo mete a cpbb. 15. PROCESO[IdProceso].estado=BLOQUEADO; 16. CambiaContexto(); // Llama al cambio de contexto 17. } 18. else // Hay espacio para el mensaje dentro del buz´ on. 19. { Ultimo=dcb[IdBuzon].UltMje; 20. //Obtiene la posici´ on del ´ ultimo mensaje dcb[IdBuzon].Mensajes[Ultimo]=Mensaje; //Copia la estructura del Mensaje Completo 21. dcb[IdBuzon].UltMje++; 22. }//Busca si hay procesos bloqueados por intentar recibir mensaje cuando no hab´ ıa 23. Proc=BuscaMayor(cpbb[IdBuzon]); 24. if (Proc!=0) //Si hab´ ıa bloqueados, saca al de mayor prioridad 25. { IdProceso=Saca(cpbb[IdBuzon],PROCESO[Proc].prioridad); 26. Inserta(cpl,PROCESO[IdProceso].prioridad,IdProceso); //y lo mete a cpl 27. PROCESO[Proc].estado=LISTO; 28. CambiaContexto(); // Llama al cambio de contexto 29. } 30. } 31. } 32. 33. enable(); } Tabla 4.15: Primitiva Env´ıa Mensaje Recibir Mensaje.- Esta primitiva permite recibir mensajes del buz´on indicado. Si el buz´on se encuentra vac´ıo, el proceso que invoca a esta primitiva ser´a bloqueado en la cola respectiva. Note que la cola del buz´on contendr´a solo a procesos bloqueados esperando recibir mensajes, o solo a procesos esperando enviar mensajes al buz´on. Por su implementaci´on, los dos tipos de procesos no pueden coexistir en una misma cola. RecibirMje : NOMBRE: void RecibirMje (unsigned int IdBuzon, struct MENSAJE *Mensaje). ´ Recibe un mensaje desde un buz´on determinado. FUNCION: ENTRADAS: El identificador del buz´on donde se va a recibir el mensaje (IdBuzon) y un puntero con la direcci´on donde se va a almacenar el mensaje recibido. SALIDAS: El mensaje recibido o en caso de error, un identificador con la explicaci´on Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 84 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real del fallo ocurrido. 1. 2. void RecibirMje (unsigned int IdBuzon, struct MENSAJE *Mensaje) { unsigned int Ultimo,i,Proc,IdProceso,Prio; 3. disable(); 4. if (IdBuzon >= MaxBuz) ERROR(14); //El idBuzon debe estar en el rango permitido 5. else 6. {if (dcb[IdBuzon].Creado==0) ERROR(16);// El buz´ on debe estar creado 7. else // Si los buzones cumplen los requisitos de arriba contin´ ua... 8. {Prio=PROCESO[idposeedor].prioridad; //Obtienen la prioridad del proceso 9. if (dcb[IdBuzon].UltMje==0) // Si no hay mensajes en el buz´ on... 10. { // Bloquear proceso en espera del mensaje. 11. Elimina(cpl,idposeedor); // sac´ andolo de la cola de procesos listos 12. Inserta(cpbb[IdBuzon],Prio,idposeedor); //y meti´ endolo a cpbb 13. PROCESO[idposeedor].estado=BLOQUEADO; 14. CambiaContexto(); // Llama al cambio de contexto 15. } 16. *Mensaje=dcb[IdBuzon].Mensajes[0]; // Hay mensajes, sacar el primero de la cola 17. for (i=0;i=MaxPro) ERROR(7); //se verifica que el identificador del proceso sea v´ alido 5. banderas=0x200; //Guarda el valor de las banderas para que permitan interrupciones 6. ssI = _SS; spI = _SP; // Se guardan los valores de la pila principal 9. _SS = PROCESO[id].ss = FP_SEG (&PROCESO[id].pila); 10. _SP = PROCESO[id].sp = FP_OFF (&PROCESO[id].pila+(tam_pila-2)); 11. Ics = FP_SEG(DirTarea); 12. Iip = FP_OFF(DirTarea); 13. asm { // Se obtiene la direcci´ on IP y CS del proceso push banderas // Se introducen todos los registro a la pila de cada proceso... 14. push Ics // 15. push Iip // al activarse, mete a la pila todos los registros en el Esto se hace debido a que la interrupci´ on del reloj 16. push ax // siguiente orden: AX,BX,CX,DX,ES,DS,SI,DI y BP. 17. push bx // 18. push cx // anteriores y adem´ as se ejecuta un IRET el cual saca 19. push dx // de la pila el IP, CS y FLAGS en ese orden. 20. push es 21. push ds 22. push si 23. push di 24. push bp } Al terminar la interrupci´ on se sacan los registros 26. PROCESO[id].ss = _SS; // Debido a que hubo push en la pila los registros SS y SP 27. PROCESO[id].sp = _SP; // 28. _SP = spI; _SS = ssI;// cambia la pila por la pila inicial cambiaron, por lo que es necesario guardarlos... 30. PROCESO[id].prioridad=prio; //Se asigna la prioridad 31. PROCESO[id].Periodo 32. PROCESO[id].TComputo = 33. PROCESO[id].P=P; //Siguiente Periodo o TA //CAMBIAR a TA checarlo 34. = P; TC; // El periodo // y el tiempo de computo enable(); 35. } Tabla 4.17: Primitiva Crea Tarea 1. 2. void inicializa() { register int i; 3. disable(); 4. Inicializa_Tareas(); //Inicializa el PCB de las tareas 5. InicializaCola(cpl);// Inicializa la cola de procesos listos (activos) 6. inicializa_r();//inicializa la cola de procesos retrasados 7. for (i=0;i nvapos) 5. { cpr[0][x] = cpr[0][x-1]; 6. cpr[1][x] = cpr[1][x-1]; 7. x--; 8. } 9. // Una vez recorridos los procesos, le calcula el tiempo que le corresponde 10. // al proceso que se encontraba en la posici´ on del nuevo proceso. 11. cpr[0][x] = tiemp - valor; 12. 14. cpr[1][x] = id; } Tabla 4.31: Primitiva Arregla Cola Inserta r : NOMBRE: void inserta_r(unsigned int num_p,unsigned long tiempo). ´ FUNCION: Se encarga de insertar un proceso en la cola de retrasados en la posici´on que le corresponda en base a su tiempo de retraso. ENTRADAS: El tiempo a retrasar y el identificador del proceso a insertar. SALIDAS: La cola con el proceso insertado en la posici´on correcta. 1. void inserta_r(unsigned int num_p,unsigned long tiempo) 2. { unsigned int X=1; // contador 4. unsigned long temporal=0,temporal2=0, sumatoria=0; 5. char modificado=FALSO; 7. if (cpr[0][0] == 0) // si NO hay procesos en la cola se pasa sin cambios 8. { cpr[0][1] = tiempo; cpr[1][1] = num_p; 12. } else 13. { while (X<=cpr[0][0] && modificado == 0) 14. { if (tiempo > cpr[0][X]+sumatoria) 17. { sumatoria += cpr[0][X]; X++; } 20. else 21. { modificado = VERDADERO; 22. temporal = cpr[0][X]; 23. temporal2 = cpr[1][X]; 25. cpr[0][X] = tiempo - sumatoria; 26. cpr[1][X] = num_p; 29. arregla_cola(X+1,temporal,cpr[0][X],temporal2); 30. } 31. } // Si es 0 indica que al proceso le toca al final de la cola 32. if (modificado == FALSO) 33. { cpr[0][X]=tiempo-sumatoria; cpr[1][X]=num_p; } 36. } 37. 38. cpr[0][0]++; } Tabla 4.32: Primitiva Inserta a la Cola de Retrasados Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.3. Manejadores 99 Saca r : NOMBRE: unsigned int saca_r(). ´ FUNCION: Saca al primer proceso de la cola de retrasados y recorre los elementos restantes hacia la izquierda. ENTRADAS: Ninguna. SALIDAS: El identificador del proceso que sac´o de la cola de retrasados. 1. unsigned int saca_r() 2. { unsigned int x,n_elem,valor; 3. valor = cpr[1][1]; //saca el primer valor de la cola 4. for (x=1;x<=cpr[0][0];x++) 5. { cpr[0][x] = cpr[0][x+1]; 6. cpr[1][x] = cpr[1][x+1]; 7. } 8. cpr[0][0]--; 9. 10. return valor; } Tabla 4.33: Primitiva Saca de la Cola de Retrasa Inicializa r : NOMBRE: void inicializa_r(). ´ Inicializa la cola de procesos retrasados a 0, el cual sirve para indicar que FUNCION: no hay elementos en ella. ENTRADAS: Ninguna. SALIDAS: La cola de retrasados vac´ıa y lista para su uso. 1. void inicializa_r() 2. { 3. unsigned int i; 4. for(i=0;i0) 25. { //Si es la hora de activarse y su tcc es mayor a 0, indica perdida de plazo 26. PROCESO[Mayor].tcc=0; 27. } 28. // Se calcula el siguiente Tiempo de Activaci´ on 29. if (PROCESO[Mayor].tcc == 0) 30. { PROCESO[Mayor].TA += PROCESO[Mayor].Periodo; 31. IDposAnt = Mayor; // guarda el idposeedor anterior. 32. finaliza=FALSO; 33. } 34. PROCESO[Mayor].tcc++; // aumentar el tiempo de computo consumido 35. } 36. if (finaliza==VERDADERO) 37. IDposAnt = Mayor; 38. 39. return Mayor; } Tabla 4.36: Planificador RATE MONOTONIC Planif EDF : NOMBRE: unsigned int Planif_EDF(). Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 102 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real ´ Es el planificador Earliest DeadLine First y se encarga de elegir un proceso FUNCION: para su ejecuci´on en base a un conjunto de reglas descritas en la secci´on 3.6.1. ENTRADAS: Ninguna, directamente busca el proceso en la cola de procesos listos. SALIDAS: El identificador del siguiente proceso a ejecutar. 1. void Planif_EDF() 2. { unsigned int val,i,Cambios; 3. unsigned long ARREGLO[2][NTAREAS]; //ARREGLO utilizado para ordenar las tareas 4. char finaliza=FALSO; //indica si ocurri´ o un evento 5. if (cola_retrasa[0][1] > 0)// SACA RETRASA 6. { cola_retrasa[0][1]--; 7. while (cola_retrasa[0][1]==0 && cola_retrasa[0][0]) 8. { val=saca_r(); // Es while porque puede que varias tareas terminen 9. Inserta(cpl,PROCESO[val].prioridad,val); 10. PROCESO[val].estado=LISTO; 11. //su retraso al mismo tiempo. }} 12. if (Es_Valido() && PROCESO[idposeedor].tcc == PROCESO[idposeedor].TComputo)// METE RETRASA 13. { PROCESO[idposeedor].tcc = 0; 14. finaliza=VERDADERO; 15. PROCESO[idposeedor].P += PROCESO[idposeedor].Periodo; 16. // Copia de las tareas y sus plazos a un arreglo de ayuda para el ordenamiento 17. for (i=1;i<=NTAREAS;i++) // No incluye la primera ni la ultima tarea 18. { ARREGLO[0][i-1] = i; 19. //Copia el Numero de la tarea ARREGLO[1][i-1] = PROCESO[i].P; //Copia el Plazo 20. } 21. Cambios=OrdBurMej(ARREGLO); // Se busca la tarea con plazo mas cercano 22. TRetrasa = PROCESO[idposeedor].TA-Ticks; 23. if (TRetrasa != 0) // Si es 0 Significa que termino pero que es su tiempo de Activaci´ on 24. { Elimina(cpl,idposeedor); 25. inserta_r(idposeedor,TRetrasa); 26. PROCESO[idposeedor].estado=RETRASADO; 27. } 28. if (Cambios==VERDADERO) //si hubo cambios de prioridad al ordenar 29. { for (i=0;i0) 42. PROCESO[idposeedor].tcc=0; //Si es hora de activarse y tcc es mayor a 0, indica perdida de plazo 43. if (Es_Valido() && PROCESO[idposeedor].tcc == 0) // Se calcula el siguiente Tiempo de Activaci´ on 44. { PROCESO[idposeedor].TA += PROCESO[idposeedor].Periodo; 45. IDposAnt = idposeedor; // guarda el idposeedor anterior. 46. finaliza=FALSO; 47. } 48. if (finaliza==VERDADERO) IDposAnt = idposeedor; 49. 50. if (Es_Valido) PROCESO[idposeedor].tcc++; // aumentar el tiempo de computo consumido } Tabla 4.37: Planificador EARLIEST DEADLINE FIRST Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.3. Manejadores 103 Es Valido : NOMBRE: char Es_Valido(). ´ FUNCION: Es una funci´on que comprueba si la tarea en ejecuci´on es valida para ser planificada. Esto se hace debido a que tanto la primer tarea como la ultima no tienen un Tiempo de Computo o un per´ıodo definido y que son necesarios para que los planificadores tomen la decisi´on correcta. ENTRADAS: El identificador de proceso que esta en ejecuci´on. SALIDAS: un valor de FALSO o VERDADERO dependiendo de si es o no v´alido. 1. char Es_Valido(unsigned int tarea) 2. { //Las tareas a planificar no debe ser ni la primera ni la ultima 3. if (tarea!=PrimerTarea && tarea!=UltimaTarea) 4. return VERDADERO; 5. else 6. 7. return FALSO; } Tabla 4.38: Primitiva que revisa si es v´alido el proceso a planificar 4.3.5. Manejo del Reloj Un sistema de tiempo real tiene restricciones de tiempo bien definidas, por lo que es obligatorio para todo sistema operativo de tiempo real que todos los tiempos de respuesta que ofrezcan sean lo suficientemente r´apidos, ya que las acciones de control (para este tipo de sistemas) no puede hacerse esperar. En el manejador del reloj del Kernel se encuentran los procedimientos necesarios para poder modificar el tiempo (ver Figura 4.15) y obtener una resoluci´on de 1000 interrupciones por segundo, en lugar de las 18.2 interrupciones por segundo que proporciona la m´aquina por defecto. Figura 4.15: Procedimientos del Manejador del Reloj. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 104 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real El control del tiempo e interrupciones peri´odicas dentro del Kernel se llevan a cabo mediante el temporizador 8254. Este temporizador, en cualquier PC con procesador compatible con Intel, inicialmente se encuentra alimentado con una se˜ nal de 1,193,180Hz y configurado en modo 2 con lo cual genera 18.2 ticks de reloj por segundo (una interrupci´on 08 es generada por cada tick). Esta frecuencia es muy baja para los sistemas de tiempo real, por lo que en el Kernel se re-program´o el timer cambiando su valor inicial por otro que pudiera generar interrupciones peri´odicas a 1000Hz (1,000 por segundo); esta frecuencia es similar a la que se obtiene con el reloj de tiempo real (RTC) pero con la ventaja de que el timer tiene la mayor prioridad en el vector de interrupciones y por lo tanto ninguna otra interrupci´on generada en la m´aquina lo puede detener. Procedimientos del Manejador del Reloj Cambia Timer : NOMBRE: void Cambia_Timer (int frecuencia). ´ FUNCION: Es una funci´on que permite reprogramar el timer, de tal manera que se puede acelerar o disminuir el n´ umero de interrupciones por segundo generadas por el timer. ENTRADAS: La frecuencia dada en interrupciones por segundo. SALIDAS: El timer con una frecuencia distinta a la inicial. 1. void Cambia_Timer (int frecuencia) 2. { long contador; 3. asm pushf; 4. contador = 1193181/frecuencia; //Calcula el valor del conteo para tim0 5. outportb (0x43,0x34); //Pide acceso al Tim0 6. // Programa el tim0 para contar hasta el numero deseado 7. outportb(0x40,contador%255); // Parte Baja 8. outportb(0x40,contador/255); // Parte Alta 9. 10. asm popf; } Tabla 4.39: Primitiva Cambia Timer Normaliza Timer : NOMBRE: void Normaliza_Timer(void). ´ Esta funci´on se encarga de regresar el timer a la normalidad, esto es, que FUNCION: el timer funcione como inicialmente estaba antes de ejecutarse el kernel (a 18.2 interCinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.3. Manejadores 105 rupciones por segundo). ENTRADAS: Ninguna. SALIDAS: El timer con la frecuencia original. 1. void Normaliza_Timer(void) 2. { // Pide acceso al Tim0 3. outportb (0x43,0x34); 4. // Programa el Tim0 para contar hasta contador (16 bits) 5. outportb(0x40,0); 6. 7. outportb(0x40,0); } Tabla 4.40: Primitiva Normaliza Timer 4.3.6. Manejo de Interrupciones Actualmente el manejador de interrupciones s´olo controla las solicitudes de interrupci´on del teclado, sin embargo es posible agregarle la capacidad de reconocer interrupciones generadas por el puerto paralelo, en el cual podr´ıa estar conectado cualquier tipo de interfaz dotada de sensores y actuadores. Dentro del manejador de interrupciones se deben colocar todos los procedimientos que controlen los dispositivos de las plataformas (empotradas o no) donde se implemente el Kernel. Como se ve en la Figura 4.16, los procedimientos que se tienen implementados son dos: ‘IntTeclado” y “RevisaTecla”. Figura 4.16: Procedimientos del Manejador de Interrupciones. IntTeclado : NOMBRE: void interrupt IntTeclado(). ´ FUNCION: Es una rutina de tipo interrupci´on y es la que reemplazo a la int 0x09 dedicada a controlar el teclado. Esta funci´on es llamada cada vez que se pulsa una tecla Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 106 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real y especialmente se encarga de revisar si el usuario desea salir del sistema. ENTRADAS: Ninguna, al iniciar contiene en el buffer de teclado la tecla que se puls´o. SALIDAS: Ninguna. 1. void interrupt IntTeclado() 2. { old_IntTeclado(); 3. RevisaTecla(); // Revisa que tecla se puls´ o. 4. if (SALIR==VERDADERO) //Si se pulso la tecla FIN o ESC 5. { _SS=oldss; 6. _SP=oldsp; 7. 8. } } Tabla 4.41: Primitiva Interrupci´ on del Teclado RevisaTecla : NOMBRE: void RevisaTecla(). ´ Revisa en el buffer del teclado si la tecla que se pulso es FIN o ESCAPE, FUNCION: si no son, contin´ ua con la ejecuci´on normalmente, en caso de que si las hayan pulsado, regresa las interrupciones del teclado y el reloj a su estado original y termina la ejecuci´on del kernel. ENTRADAS: Ninguna, al iniciar contiene en el buffer de teclado la tecla que se puls´o. SALIDAS: Si fue la tecla ESC o FIN, termina con la ejecuci´on del kernel. 1. void RevisaTecla() 2. { int val; 3. val=inportb(0x60); 4. if(val==0x4F OR val==1) //Tecla FIN 5. 6. setvect(0x09,old_IntTeclado); //regresa la interrupcion del teclado original 7. 8. o ESC { setvect(0x08,old_IntReloj); //regresa la interrupcion del reloj original SALIR=VERDADERO; //SALIR } Tabla 4.42: Primitiva Revisa Tecla 4.3.7. Manejo de Errores Cuando un proceso llama a una primitiva, antes de ejecutarla, el Kernel lleva a cabo una serie de validaciones para detectar posibles par´ametros err´oneos ´o eventos que no se esperaban. El Kernel tiene implementado un manejador de errores de forma que si se llega a detectar uno, el sistema manda un mensaje de error indicando que fue lo que ocurri´o y adem´as, termina la ejecuci´on del mismo debido a que es un sistema de tiempo real y los Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.3. Manejadores 107 Figura 4.17: Procedimiento del Manejador de Errores. procesos que se manejan son muy delicados por lo que no debe continuar si ocurre un error. Este manejador tiene un s´olo procedimiento encargado de manipular los errores (ver Figura 4.17) y tiene la siguiente estructura: Error : NOMBRE: void ERROR(unsigned int E);. ´ FUNCION: Se encarga de mostrar al usuario en caso de que ocurriera un error, la posible causa que lo gener´o. Debido a que un Kernel es un sistema delicado, cualquier error encontrado lleva a la finalizaci´on del sistema y por lo tanto, esta funci´on antes de finalizar intercambia las rutinas del teclado y el reloj por las que ten´ıa el sistema antes de iniciar el Kernel. ENTRADAS: Un identificador del error (E), el cual contiene el c´odigo del error que se gener´o. SALIDAS: Un mensaje con el error detectado y la terminaci´on completa del Kernel. C´ odigos de Error ERROR 1: Ocurre cuando el procedimiento “BuscaMayor” intenta conocer el proceso de mayor prioridad pero resulta que la cola de procesos listos est´a vac´ıa. ERROR 2: Este error se genera cuando se intenta insertar un proceso en cualquiera de las colas circulares tipo FIFO (la de listos, buzones o sem´aforos) y no hay espacio disponible en la cola. ERROR 3: Este error sale cuando se intenta sacar un proceso de cualquier cola tipo FIFO Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 108 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real circular y no hay elementos en ella (se encuentra vac´ıa). ERROR 4: Error que ocurre cuando se intenta eliminar un proceso de una cola tipo FIFO circular y no hay elementos en ella. ERROR 5: Este error se genera cuando el proceso que se desea eliminar no esta en la cola indicada. ERROR 6: Se genera cuando la primitiva “Retrasa” tiene un tiempo de retraso invalido. ERROR 7: Ocurre cuando la primitiva “Activa” contiene un identificador de proceso mayor a los permitidos en el Kernel. ERROR 8: Este error se genera al intentar activar un proceso con mayor prioridad que la del proceso que lo cre´o. ERROR 9: Ocurre cuando se intenta utilizar un identificador de sem´aforo mayor al n´ umero de sem´aforos permitidos. ERROR 10: Este error sale cuando se intenta dar un valor inicial diferente de 0 o 1 al sem´aforo binario. ERROR 11: Error que se genera cuando se intenta crear un sem´aforo ya creado. ERROR 12: Error que sale cuando se intenta utilizar un sem´aforo que todav´ıa no ha sido creado. ERROR 13: Este error ocurre cuando la cuenta del sem´aforo es invalida. ERROR 14: Ocurre cuando se intenta utilizar un n´ umero de buz´on mayor a los permitidos. ERROR 15: Sale este error cuando se quiere crear un buz´on que ya ha sido creado. ERROR 16: Error que se genera cuando se intenta utilizar un buz´on que todav´ıa no ha sido creado. ERROR 17: Este error sale cuando en el archivo de configuraci´on se ha escrito un planificador no valido. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.4. Configuraci´ on e Inicializaci´ on del Kernel 4.4. 109 Configuraci´ on e Inicializaci´ on del Kernel 4.4.1. Configuraci´ on del Kernel El Kernel cuenta con un archivo de configuraci´on llamado CONFIG.H, en el cual el usuario puede modificar el contenido de las variables para que el Kernel se adapte a sus necesidades. Entre las cosas que se pueden modificar se encuentran: 1. El mecanismo de planificaci´on que el Kernel utilizar´a (PLANIFICADOR). Puede ser Rate Monotonic, Earliest Deadline First y FIFO Round Robin. 2. El n´ umero de tareas hechas por el usuario (NTAREAS). La cantidad m´axima de tareas o procesos depende de esta variable ya que autom´aticamente se suman la primer y ultima tarea al valor total de procesos en el Kernel (MAXPRO=NTAREAS+2). Cada vez que se cree una nueva tarea o proceso se debe aumentar aqu´ı su valor. 3. El n´ umero m´aximo de prioridades manejadas por el Kernel (MAXPRIO). 4. El n´ umero total de sem´aforos (MAXSEM). 5. El total de buzones a utilizar en el Kernel (MAXBUZ). 6. El n´ umero total de mensajes a almacenar en el buz´on (MAXMJE). 7. La longitud m´axima para el mensaje (MAXLONGMJE). 8. El tiempo de c´omputo permitido en el mecanismo de planificaci´on FIFO Round Robin (QUANTUM). Por defecto el Kernel se encuentra configurado de la siguiente manera: Utiliza el planificador Rate Monotonic. Permite crear 10 sem´aforos. Existen 5 tareas hechas por el usuario. Maneja 15 niveles de prioridad. Soporta 15 Buzones. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 110 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real Almacena 10 mensajes por buz´on con una longitud de 15bytes cada uno. El Quantum para la planificaci´on FIFO Round Robin es de 5. 4.4.2. Inicializaci´ on del Kernel Para poder ejecutar el Kernel es necesario compilar el archivo KERNEL.C, este archivo es el principal y es el que inicializa todo el sistema. Aqu´ı se encuentran declaradas todas las librer´ıas que contienen los manejadores y las primitivas del kernel y adem´as, es aqu´ı donde se deben indicar el nombre de los archivos que contienen las tareas o proceso a ejecutar. El proceso de inicializaci´on del sistema es el siguiente: 1. Se cambia la resoluci´on del “timer” para forzar que el temporizador de la m´aquina genere interrupciones peri´odicas cada milisegundo. 2. Se ejecuta la primitiva inicializa() la cual se encarga de lo siguiente: Inicializar cada una de las tareas poniendo su estado a “NUEVO”. Inicializar las colas de procesos utilizadas en el kernel (cola de procesos listos, retrasados, de sem´aforos y de procesos bloqueados por buz´on), adem´as de crear el sem´aforo 0, el cual esta reservado para la regi´on cr´ıtica. 3. Crea los procesos primero y u ´ltimo. 4. Se crean los procesos hechos por el usuario. 5. Activa los procesos primero y u ´ltimo. 6. Por u ´ltimo manda a ejecutar la primer tarea. Una vez ejecutada la primer tarea quien se encarg´o de activar todos los procesos que se van a correr en el kernel, el control y la decisi´on de lo que se va a ejecutar en el procesador la toma el planificador y a partir de ah´ı, es este quien decide el comportamiento del kernel y la u ´nica manera de terminar con la ejecuci´on del kernel es pulsando la tecla ESC o FIN. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 4.5. Datos T´ ecnicos 4.5. 4.5.1. 111 Datos T´ ecnicos Tama˜ no Debido a que el Kernel fue dise˜ nado para su implementacion en un sistema empotrado, el Kernel contiene s´olo las funciones que son necesarias para el control de los sistemas de tiempo real en este tipo de dispositivos. Por lo tanto, el tama˜ no del Kernel es muy peque˜ no (20.5Kb). Esta caracter´ıstica hace posible que se pueda implementar en sistemas empotrados con altas restricciones de memoria. En la Tabla 4.43 se muestra a detalle el tama˜ no de cada uno de los archivos que conforman el Kernel. Nombre del archivo Tama˜ no kernel 1.05Kb config 231 bytes constant 1.55Kb libreria 1.97Kb manreg 1.49Kb mancpu 491 bytes manplan 1.99Kb mancolas 4.24Kb manreloj 376 bytes manint 304 bytes manerror 1.85Kb pribuz 2.51Kb pripro 621 bytes prisem 1.67Kb pritim 255 bytes TOTAL 20.5Kb Tabla 4.43: Tama˜ no del Kernel. 4.5.2. Tiempos de ejecuci´ on del Kernel En cualquier aplicaci´on de tiempo real es importante conocer el tiempo de ejecuci´on de las primitivas dise˜ nadas en el Kernel, debido a la predecibilidad con que debe contar el sistema. En la Tabla 4.44 se indica que el cambio de contexto tarda en promedio 32.44 microsegundos. Debido a que la granularidad del Kernel es de 1 milisegundo (1,000 interrupciones por segundo), el tiempo que le resta al proceso para ejecutarse (despu´es de la ejecuci´on de la rutina de cambio de contexto) ser´ıa de aproximadamente 967.55 microsegundos. Los tiempos presentados en la Tabla 4.44 fueron obtenidos en una computadora Laptop Pentium 4 a 1.4GHz, con 240MB de RAM y 16MB de RAM en video. Con la finalidad de Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 112 Cap´ıtulo 4. Dise˜ no del Kernel de Tiempo Real obtener las mediciones m´as realistas posibles, el Kernel se ejecut´o solo bajo el ambiente de MS-DOS (fuera del ambiente de Windows). Tiempo Tiempo Tiempo Primitiva m´ınimo(µs) m´ aximo(µs) promedio(µs) Inicializaci´ on del sistema 11.43 13.23 12.34 Cambio de contexto 30.37 34.12 32.44 Activa 11.73 12.57 11.93 Elimina 11.73 14.24 12.08 Retrasa 11.23 13.23 12.23 Crea sem´ aforo 11.73 12.57 11.81 Se˜ nal 11.73 13.40 12.17 Espera 11.73 12.57 12.17 Crea buz´ on 11.73 12.57 11.83 Env´ıa Mensaje 12.57 14.24 12.80 Recibe Mensaje 13.40 15.92 14.23 Inserta a la cola 11.73 12.57 12.32 Saca de la cola 11.73 12.57 12.30 Busca el mayor 23.46 24.30 23.59 Earliest Deadline First 11.73 15.08 12.28 Rate Monotonic 11.73 13.40 12.25 Tabla 4.44: Tiempos de ejecuci´on de las primitivas del Kernel. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 5 Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de Corriente Directa 5.1. Introducci´ on Este cap´ıtulo est´a dedicado por completo a la descripci´on de una aplicaci´on desarrollada en el Centro de Servicios Experimentales del departamento de Control Autom´atico. El objetivo es experimentar con el kernel elaborado en esta tesis, y conocer el comportamiento de este ante situaciones de tiempo real verdaderas. Debido a que la aplicaci´on maneja t´erminos espec´ıficos de control autom´atico, este cap´ıtulo contiene una breve descripci´on sobre los sistemas de control, algunos conceptos b´asicos de control, los tipos de retroalimentaci´on m´as utilizados en los sistemas de control y el control proporcional derivativo. Adem´as, en este cap´ıtulo se explican a detalle las caracter´ısticas de los amplificadores y motores de corriente directa con escobillas, la arquitectura de la aplicaci´on y los resultados obtenidos. 113 Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 114 Corriente Directa 5.1.1. Introducci´ on al Control Los sistemas de control autom´atico, son sistemas din´amicos y el conocer la teor´ıa de control, proporcionar´a una base para entender su comportamiento. Estos sistemas emplean frecuentemente componentes de diferentes tipos, como son: componentes mec´anicos, el´ectricos, hidr´aulicos y neum´aticos. En a˜ nos recientes, los sistemas de control han venido adquiriendo un papel muy importante en el desarrollo y avance de la civilizaci´on y tecnolog´ıas modernas. Casi todos los aspectos de nuestras actividades cotidianas son afectados por alg´ un tipo de sistemas de control. Por ejemplo, en el campo dom´estico, los controles autom´aticos para calefacci´on y aire acondicionado que regulan la temperatura y la humedad de los hogares, para lograr una vida c´omoda. Para alcanzar una eficiencia m´axima en el consumo de energ´ıa, muchos sistemas modernos de calefacci´on y de aire acondicionado est´an computarizados, en especial en los grandes edificios y las f´abricas. 5.2. Sistemas de Control Los sistemas de control son muy comunes en todos los sectores industriales, desde el control de calidad de productos industriales, l´ıneas de ensamble autom´atico, control de m´aquinas, herramientas, tecnolog´ıa espacial, armamento, control por computadora, sistemas de transportaci´on, rob´otica y muchos otros. Incluso problemas relacionados con el control de inventarios, los sistemas de control sociales y econ´omicos, pueden resolverse con enfoques de la teor´ıa del control. Para comprender los sistemas de control autom´aticos, es necesario definir los siguientes t´erminos los sistemas de control[28]. Planta. Una planta es un equipo o quiz´as simplemente un juego de piezas de una m´aquina funcionando juntas, cuyo objetivo es realizar una operaci´on determinada. Sistema. Un sistema es una combinaci´on de componentes que act´ uan conjuntamente y cumplen determinado objetivo. Un sistema no est´a limitado a los objetos f´ısicos. El Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 5.2. Sistemas de Control 115 concepto de sistema puede ser aplicado a fen´omenos abstractos y din´amicos, como son los sistemas de tiempo real. Perturbaciones. Una perturbaci´on es una se˜ nal que tiende a afectar adversamente el valor de la salida de un sistema. Un ejemplo de perturbaciones en los sistemas de tiempo real es la variaci´on en los tiempos de ejecuci´on de las tareas con respecto a los tiempos estimados en el peor caso. Sistema de control retroalimentado. Es aquel que tiende a mantener una relaci´on preestablecida entre la salida y la entrada de referencia, comparando ambas y utilizando la diferencia como par´ametro de control. Sistema de control autom´ atico. Es un sistema de control retroalimentado en el que la entrada de referencia o la salida deseada son constantes o var´ıan lentamente en el tiempo y donde la tarea fundamental consiste en mantener la salida en el valor deseado a pesar de las perturbaciones presentes. Cualquiera que sea el tipo de sistema de control considerado, los ingredientes b´asicos del sistema pueden describirse en t´ermino de: 1. Objetivos del control. 2. Componentes del sistema de control. 3. Resultados. En la Figura 5.1(a) se ilustra la relaci´on entre estos tres ingredientes b´asicos en forma de diagrama de bloques. Estos tres ingredientes b´asicos pueden identificarse como entradas (referencias), componentes del sistema (controlador y planta) y resultados (salidas), respectivamente, como se muestra en la Figura 5.1(b). En general el objetivo del sistema de control consiste en controlar las salidas y de una manera predeterminada, la cual est´a dada por la referencia r y el controlador. A las entradas del sistema se le llama tambi´en consigna de operaci´on y a las salidas variables controladas. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 116 Corriente Directa Figura 5.1: Componentes B´asicos de un Sistema de Control. Sistemas de Control en Lazo Abierto. Es un sistema de control simple y econ´omico que no cuenta con una retroalimentaci´on de la salida en el sistema. Un ejemplo de sistemas de lazo abierto son las lavadoras el´ectricas, estas en su dise˜ no t´ıpico, el ciclo de lavado queda determinado en su totalidad por la estimaci´on y el criterio del operador humano. Los elementos del sistema de control en lazo abierto casi siempre pueden dividirse en dos partes: el controlador y el proceso controlado, tal como se puede apreciar en el diagrama de bloques de la Figura 5.2 se aplica una se˜ nal de entrada o comando r al controlador, cuya salida act´ ua como se˜ nal de control u; la se˜ nal actuante controla el proceso controlado, de tal manera que la variable controlada y se comporte de acuerdo con est´andares predeterminados. Figura 5.2: Elementos de un Sistema de Control en Lazo Abierto. Sistemas de Control en Lazo Cerrado. Se le llama sistema en lazo cerrado a los sistemas con uno o m´as lazos de retroalimentaci´on. En estos sistemas, para obtener un control m´as preciso, la se˜ nal controlada y(t) debe retroalimentarse y compararse con la entrada de referencia, tras lo cual se env´ıa a trav´es del sistema una se˜ nal de control Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 5.2. Sistemas de Control 117 proporcional a la diferencia entre la entrada y la salida, con el objetivo de corregir el error. En la Figura 5.3 se muestra el diagrama de bloques de un sistema de control de marcha en reposo en lazo cerrado. Figura 5.3: Sistema de Control de Marcha en Reposo en Lazo Cerrado. 5.2.1. Tipos de Retroalimentaci´ on La retroalimentaci´on en los sistemas es muy importante, adem´as de permitir la reducci´on de errores tambi´en tiene efectos en las caracter´ısticas de desempe˜ no del sistema tales como: estabilidad, ganancia total, sensibilidad y reducci´on de ruido. En los controles autom´aticos industriales, son muy comunes los siguientes tipos de retroalimentaci´on: P, I, PI, PD y PID los cuales son descritos a continuaci´on ya que es importante comprender las caracter´ısticas b´asicas de cada retroalimentaci´on, para poder elegir la que m´as se adecue a determinada aplicaci´on. Retroalimentaci´ on Proporcional (P) Para un control de acci´on proporcional, la relaci´on entre la salida del controlador u(t) y la se˜ nal de error e(t) es: u(t) = Kp e(t) Cinvestav-IPN Secci´ on Computaci´ on (5.1) Oscar Miranda G´ omez Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 118 Corriente Directa o en magnitudes de transformada de Laplace, U (s) = Kp E(s) (5.2) donde Kp se conoce como sensibilidad proporcional o ganancia. El control proporcional esencialmente es un amplificador con ganancia ajustable. Valores muy grandes de Kp a menudo pueden llevar a la inestabilidad. Para la mayor´ıa de los sistemas hay un l´ımite superior en la ganancia proporcional para lograr una respuesta bien amortiguada y estable. Retroalimentaci´ on Integral (I) Es un control con acci´on integral, el valor de la salida del controlador u(t) var´ıa proporcionalmente a la se˜ nal de error actuante e(t). Esto es: du(t) = Ki e(t) dt (5.3) o u(t) = Ki Z t e(t)dt (5.4) 0 donde Ki es una constante regulable. La funci´on de transferencia del control integral es: U (s) Ki = E(s) s (5.5) Si se duplica el valor de e(t), el valor de u(t) var´ıa dos veces m´as r´apido. Para un error actuante igual a cero, el valor u(t) se mantiene estacionario. La acci´on de control integral recibe a veces el nombre de control de reposici´on. Retroalimentaci´ on Proporcional e Integral (PI) La acci´on de control proporcional e integral queda definida por la siguiente ecuaci´on: Kp Z t u(t) = Kp e(t) + e(t)dt Ti 0 (5.6) o la funci´on de transferencia del control es: M (s) 1 = Kp 1 + E(s) Ti s   (5.7) donde Kp representa la sensibilidad proporcional o ganancia y Ti el tiempo integral o tiempo de restablecimiento. Tanto Kp como Ti son regulables. El tiempo integral regula la acci´on de Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 5.2. Sistemas de Control 119 control integral, una modificaci´on en Kp afecta tanto la parte integral como la proporcional de la acci´on de control. A la inversa del tiempo integral Ti se le llama velocidad de restablecimiento. Esta retroalimentaci´on tiene la virtud de poder proporcionar un valor finito de u(t) sin se˜ nal de error de entrada e(t). La motivaci´on principal para a˜ nadir la acci´on integral es el reducir o eliminar los errores en estado estable, pero esta ventaja se consigue a costa de una estabilidad reducida. Retroalimentaci´ on Proporcional Derivativo (PD) La acci´on de control proporcional y derivativo queda definida por la siguiente ecuaci´on: u(t) = Kp e(t) + Kp Td de(t) dt (5.8) y la funci´on de transferencia es: U (s) = Kp (1 + Td s) E(s) (5.9) donde Kp es la sensibilidad proporcional y T (d) es el tiempo derivativo, los dos par´ametros son regulables. La acci´on de control derivativa es conocida tambi´en como control de velocidad debido a que el valor de control es proporcional a la velocidad de variaci´on de la se˜ nal de error actuante. El tiempo derivativo Td es el intervalo de tiempo en el que la acci´on de velocidad se adelanta al efecto de acci´on proporcional. La acci´on de control derivativa tiene la ventaja de ser anticipatoria, pero tiene la desventaja de que amplifica las se˜ nales de ruido y puede producir efectos de saturaci´on en el actuador, se utiliza junto a la proporcional para aumentar la amortiguaci´on y para incrementar la estabilidad del sistema. La acci´on derivativa por s´ı misma no lleva el error a cero. Retroalimentaci´ on Proporcional Integral Derivativo (PID) Representa la combinaci´on de las acciones proporcional, integral y derivativa, y tiene las ventajas de cada una de las tres acciones de control individuales. Normalmente se le conoce por sus siglas PID. La ecuaci´on de un control con esta acci´on de control combinada est´a dada por: u(t) = Kp e(t) + Cinvestav-IPN Kp Z t de(t) e(t)dt + Kp Td Ti 0 dt Secci´ on Computaci´ on (5.10) Oscar Miranda G´ omez Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 120 Corriente Directa y la funci´on de transferencia es: U (s) 1 = Kp 1 + + Td s E(s) Ti s   (5.11) donde Kp representa la sensibilidad proporcional, Td el tiempo derivativo y Ti el tiempo integral. Esta combinaci´on es a menudo utilizada para proveer un grado aceptable de reducci´on del error simult´aneamente a una estabilidad y amortiguaci´on aceptables. Normalmente, los controladores disponibles comercialmente tienen est´a forma, y el ingeniero de control u ´nicamente tiene que ajustar o sintonizar las tres constantes de la ecuaci´on para obtener un comportamiento aceptable. 5.2.2. Implementaci´ on Digital del Proporcional Derivativo Los controladores fueron implementados usando t´ecnicas anal´ogicas. En la actualidad es una practica com´ un implementar controladores como el PD u otros mediante microprocesadores, para lo cual deben tomarse en cuenta algunas consideraciones al implementarlo en forma digital, las consideraciones m´as importantes tienen que ver con el muestreo, la discretizaci´on y la selecci´on del periodo de muestreo. Muestreo Cuando una computadora digital es utilizada para implementar una ley de control, todo el procesamiento de se˜ nales es realizada en instancias discretas en tiempo. La secuencia de operaciones es: 1. Esperar la interrupci´on del reloj. 2. Leer la entrada anal´ogica. 3. Calcular la entrada de control. 4. Escribir la salida anal´ogica. 5. Actualizar las variables del controlador. 6. Ir al paso 1. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 5.2. Sistemas de Control 121 Las acciones de control est´an basadas sobre los valores de la salida en tiempos discretos. Este proceso es llamado muestreo. El caso normal es muestrear la se˜ nal peri´odicamente con periodo T . Discretizaci´ on Para implementar una ley de control continua en el tiempo como el controlador P D sobre una computadora digital, es necesario aproximar la parte derivativa que aparece en la Ecuaci´on 5.8. El termino derivativo es simplemente reemplazado por una expresi´on diferencial de primer orden [29], por lo que la ecuaci´on discretizada para el control proporcional derivativo queda: u(t) = Kp e(t) + Kp Td (e(k) − e(k − 1)) (5.12) Selecci´ on del Periodo de Muestreo La selecci´on del periodo de muestreo T es un problema fundamental en los sistemas muestreados [30]. El periodo de muestreo seleccionado depende de las propiedades de la se˜ nal, el m´etodo de reconstrucci´on y el prop´osito del sistema. En un problema de procesamiento de se˜ nales, el prop´osito es simplemente obtener una se˜ nal digital y despu´es recuperarla desde sus muestras, por lo tanto, un criterio razonable para la selecci´on del periodo de muestreo puede ser el tama˜ no del error entre la se˜ nal original y la se˜ nal reconstruida. La fundamentaci´on principal para la selecci´on de la frecuencia de muestreo ws o el periodo de muestreo T es el teorema de muestreo de Shannon. Este teorema especifica que una frecuencia de muestreo debe ser al menos el doble de la frecuencia m´as alta de la se˜ nal. El ancho de banda de las computadoras afecta la precisi´on de los valores obtenidos debido a los convertidores A/D y D/A, los coeficientes del controlador y las operaciones aritm´eticas de la computadora. Otras consideraciones que afectan la precisi´on incluyen los compensadores, las se˜ nales de perturbaciones, las mediciones del ruido, el tiempo de retardo inherente en el sistema, etc. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 122 Corriente Directa 5.3. 5.3.1. Motores y Amplificadores Motores de Corriente Continua Todos los motores el´ectricos tienen b´asicamente los mismos componentes. Todos tienen un magneto estacionario denomidado el estator y un electroim´an denominado la armadura. El estator genera el campo magn´etico. Cuando una corriente el´ectrica se hace pasar por el embobinado de la armadura que se ha colocado en el campo magn´etico generado por el estator, esta comienza a rotar debido al torque magn´etico. De esta manera la energ´ıa el´ectrica se convierte en energ´ıa mec´anica. En general, los motores de corriente continua son similares en construcci´on a los generadores. De hecho podr´ıan describirse como generadores que funcionan al rev´es. Todas los motores DC son reversibles. Si se les suministra un voltaje a los terminales del motor el´ectrico, su armadura gira y realiza un trabajo mec´anico. Por otro lado, si se hace girar el eje del motor y su armadura con la ayuda de alg´ un dispositivo entonces el motor trabajara como un generador el´ectrico (d´ınamo) y producir´a corriente el´ectrica. Los cuatro motores utilizados en nuestro ejemplo de aplicaci´on son como el que se muestra en la Figura 5.4. Se trata de motores de corriente directa con escobillas, tienen una masa inercial balanceada (pesa de lat´on) de 1.3 kg y un codificador ´optico incremental (enconder) con una capacidad de resoluci´on de 2,500 pulsos por revoluci´on en hardware, y por software de 5,000 con la posibilidad de incrementarse hasta 10,000. Las caracter´ısticas mec´anicas son las siguientes: PAR nominal = 36.7 oz-in ´o 0.259 N-m RPM nominal = 2000 Sus caracter´ısticas el´ectricas son: Tensi´on Nominal E = 29V Corriente Nominal I = 1,6A Potencia Nominal 38,4W Corriente M´axima Imax = 8A Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 5.3. Motores y Amplificadores 123 Figura 5.4: Motor de Corriente Continua. 5.3.2. Amplificadores Los amplificadores son necesarios para mover y controlar un motor, estos, adem´as de regular su propio desempe˜ no, amplifica la potencia (corriente y voltaje) a 52 volts. Los amplificadores utilizados en esta tesis, son el modelo 422 de Copley Controls Corp., este modelo contiene una fuente de poder no regulada que opera desde +24a + 180V DC y una corriente de salida desde 10 a 20A. Estos amplificadores ofrecen muchas ventajas para el control de motores de corriente directa con escobillas. Todos los modelos toman el est´andar industrial de ±10V para se˜ nales de control como entrada, y operan en tres modos diferentes: fuerza de torsi´on o par, velocidad, y voltaje retroalimentado con compensaci´on IR. El modo par es el m´as usado en aplicaciones para motores con tarjetas de control digital que tienen un encoder que devuelve la velocidad del motor y el control de posici´on. En el modo de velocidad, teniendo un tac´ometro retroalimentado, es usado para ciclos abiertos en el control de velocidad as´ı como en ciclos de control de posici´on. Por u ´ltimo, el control de velocidad tambi´en puede ser hecho mediante el modo de voltaje retroalimentado con compensaci´on IR, sobre todo cuando se requiere un menor costo. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 124 Corriente Directa 5.4. Arquitectura de la Aplicaci´ on La aplicaci´on consiste en controlar en posici´ on, cuatro motores de corriente directa con escobillas a trav´es del Kernel mediante el control proporcional derivativo. La arquitectura de la aplicaci´on se puede ver en la Figura 5.5. El objetivo es lograr el mejor comportamiento de los motores al tratar de imitar una se˜ nal de referencia dada. Los dispositivos que se utilizaron para desarrollar la aplicaci´on son los siguientes: 1. Una computadora, la cual contiene el kernel que va a controlar la aplicaci´on. 2. Una tarjeta de adquisici´on de datos (TAD), que cuenta con varias salidas y entradas anal´ogicas y digitales que nos permitir´an conocer datos importantes sobre los motores a controlar [3]. 3. Una caja de interface de conexiones, la cual es un acondicionamiento f´ısico de los cables entre la TAD y los dem´as dispositivos. 4. Un dispositivo de aislamiento galv´ anico, que permite aislar la computadora de control de la etapa de potencia. Su funci´on es evitar alg´ un da˜ no a la tarjeta de adquisici´on de datos que por lo general son costosas. 5. Cuatro amplificadores de corriente y voltaje, que nos permitir´an mover y controlar los motores. 6. Cuatro motores de corriente directa con escobillas, y que son los que se quieren controlar. 5.5. Pruebas y Resultados Para conocer a detalle el comportamiento del kernel ante situaciones de tiempo real verdaderas, se hicieron varias pruebas, todas estas sin cambiar la arquitectura mostrada en la Figura 5.5. Los resultados de estas pruebas son los siguientes: 5.5.1. Prueba 1: Control PD con Fifo Round Robin En esta prueba se controlan los cuatro motores de corriente directa utilizando el planificador Fifo Round Robin. Por las caracter´ısticas de este planificador, las tareas se ejecutan Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 5.5. Pruebas y Resultados 125 Figura 5.5: Arquitectura de la Aplicaci´on. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 126 Corriente Directa una tras de otra en el orden que han sido preasignadas y no cambia nada durante toda su ejecuci´on. La utilizaci´on del procesador es del 100 % y no hay p´erdidas de plazo en las tareas. Dentro del Kernel se ejecutan cuatro tareas, cada tarea (de manera independiente) controla un motor, dibuja una gr´afica en pantalla del comportamiento del motor y genera una onda cuadrada como se˜ nal de referencia. Para esta prueba, cada tarea genera una se˜ nal de referencia diferente, logrando con esto que cada motor gire exactamente una vuelta perfecta en un instante de tiempo preciso. Por ejemplo: en esta prueba el motor 1 gira una vez cada segundo, el motor 2 gira cada dos segundos, el motor 3 cada tres segundos y el motor 4 gira cada cuatro segundos. Gr´aficamente, en el Kernel las tareas planificadas con Fifo Round Robin cuyo quantum es de 5 milisegundos se comportan como lo muestra la Figura 5.6; y las gr´aficas que dibujan las tareas en el monitor para esta prueba son como se muestra en la Figura 5.7. Figura 5.6: Control PD para cuatro motores con Fifo Round Robin. Figura 5.7: Gr´aficas en Tiempo Real Generadas en la Prueba 1. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 5.5. Pruebas y Resultados 5.5.2. 127 Prueba 2: Control PD con Rate Monotonic Esta prueba consiste de cinco tareas, una tarea se encarga de generar una se˜ nal de referencia intercambiando cada 2 segundos el voltaje de 0,25V a −0,25V y viceversa, las otras cuatro tareas se encargan de controlar los motores y al mismo tiempo graficar en pantalla el estado del motor sobre la se˜ nal de referencia1 . Cada tarea controla su motor mediante el sistema de control proporcional derivativo (PD), con este control es posible encontrar el voltaje que debe ser enviado al motor para lograr que su comportamiento sea similar al de la se˜ nal de referencia generada por la tarea 1 (T1). Como resultado del control, se logra que cada motor gire una vuelta exacta cada 2 segundos (intercambiando el sentido de la vuelta tal y como lo indica la se˜ nal de referencia). El mecanismo de planificaci´on utilizado para esta prueba fue Rate Monotonic, y por lo tanto las tareas tienen una prioridad, un tiempo de computo Ci y un periodo asignado Ti . La Tabla 5.1 muestra los valores (en milisegundos) asignados a cada tarea, as´ı como la utilizaci´on que tienen sobre el procesador. T area Descripci´ on Ti ms Ci ms Utilizaci´ on T1 Se˜ nal de Referencia 2000 1 0.0005 T2 Motor1 3 1 0.333 T3 Motor2 5 1 0.2 T4 Motor3 7 1 0.142 T5 Motor4 9 1 0.111 0.7865 Tabla 5.1: Conjunto de Tareas Utilizadas Como se puede ver en la Tabla 5.1, la utilizaci´on total del procesador es del 78 % y por lo tanto no cumple con la condici´on 3.2 que garantiza que el conjunto de tareas en Rate Monotonic es planificable, sin embargo, esta condici´on es suficiente pero no necesaria. En este caso, el factor de utilizaci´on de las cuatro primeras tareas (T1,T2,T3 y T4) es igual a 0.6755 y como es menor a 0.7568 tenemos garantizado bajo la condici´on 3.2 que estas tareas terminan siempre dentro de sus plazos de respuesta. Para la quinta tarea se aplica la condici´on 1 Cada tarea controla y genera la gr´ afica que le corresponde a su motor asignado. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 128 Corriente Directa suficiente y necesaria de Lehoczky (ver teorema 3.5.3). Esta condici´on nos garantiza, en caso de salir positiva, que el conjunto de tareas no perder´a sus plazos. A continuaci´on se muestran los c´alculos realizados para comprobar que la tarea 5 cumple con la condici´on de Lehoczky, y por lo tanto, todas las tareas de esta prueba son planificables sobre Rate Monotonic. W50 = C5 = 1 W51 = C5 + W52 = C5 + W53 = C5 + W50 Cj Tj P l W51 m Cj ∀j Tj P l W52 m Cj ∀j Tj ∀j W54 = C5 + P l W55 = C5 + P l P l W56 = C5 + m l P ∀j ∀j ∀j W53 Tj W54 Tj W55 Tj m m m =1+ l =1+ l =1+ l Cj = 1 + l Cj = 1 + l Cj = 1 + l 1 2000 m 5 2000 m 6 2000 m 7 2000 m 8 2000 m 9 2000 m 1+ l m 1+ l m 1+ l m 1+ l m 1+ l m 1+ l m 1 3 5 3 6 3 7 3 8 3 9 3 1+ l m 1+ l m 1+ l m 1+ l m 1+ l m 1+ l m 1 5 5 5 6 5 7 5 8 5 9 5 1+ l m 1 7 1=5 1+ l m 5 7 1=6 1+ l m 6 7 1=7 1+ l m 7 7 1=8 1+ l m 8 7 1=9 1+ l m 1=9 9 7 Como W55 = W56 = 9 y 9 ≤ T5 = 9, entonces, es planificable. La Figura 5.8 nos muestra el comportamiento de las tareas en el kernel mediante una gr´afica de Gantt y la Figura 5.9 contiene las gr´aficas en pantalla del comportamiento de los motores durante esta prueba. Figura 5.8: Control PD para cuatro motores con Rate Monotonic. Figura 5.9: Gr´aficas en Tiempo Real Generadas en la Prueba 2. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 5.5. Pruebas y Resultados 5.5.3. 129 Prueba 3: Control PD con Earliest DeadLine First Esta prueba es similar a la prueba 2, cuenta con cinco tareas que realizan las siguientes funciones: la tarea 1 (T1 ) genera un se˜ nal de referencia, esta se˜ nal es una onda cuadrada que cambia cada 2 segundos de −0,25v a 0,25v y viceversa. Las otras cuatro tareas (T2,T3,T4 y T5 ) se encargan de controlar los motores mediante el control proporcional derivativo. Cada tarea controla a un motor en espec´ıfico y adem´as manda los resultados a un archivo para su graficaci´on posterior. La tabla 5.1 muestra el conjunto de tareas y la utilizaci´on que estas tienen en el procesador. La diferencia en esta prueba con la anterior, se encuentra en el mecanismo de planificaci´on utilizado, para esta prueba se utiliz´o EDF (Earliest Deadline First). Este algoritmo tiene la ventaja de garantizarnos que no tendremos perdidas de plazos a´ un con un factor de utilizaci´on del 100 % (ver Condici´on 3.11). La utilizaci´on total para esta prueba es del 78 % y cumple satisfactoriamente esta condici´on. La gr´afica de Gantt de la Figura 5.10 nos muestra de manera visual cual es el comportamiento de las tareas en el Kernel. Figura 5.10: Control PD para cuatro motores con Earliest Deadline First. En la Figura 5.11 se muestra el comportamiento de los motores durante la ejecuci´on del Kernel, los datos graficados fueron obtenidos de un archivo llamado “resul.txt”. Este archivo es creado al iniciar el Kernel, y durante su ejecuci´on, cada tarea se encarga de almacenarle el tiempo, la se˜ nal de referencia y la posici´on del motor en que se encuentra en ese instante. Tambi´en, en la Figura 5.11 se puede apreciar que el motor 1 es el que m´as se acerca a la se˜ nal de referencia y que el motor 4 es el que m´as tiempo tarda en igualarla; esto se debe a la prioridad que se les asign´o para esta prueba. La tarea que controla al motor 1 (T2) por tener Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 130 Corriente Directa la mayor prioridad y el per´ıodo de activaci´on m´as corto (cada 3 milisegundos) es atendida por el planificador (EDF) con mayor frecuencia y por lo tanto, es la tarea que m´as tiempo tiene para igualar la posici´on del motor a la se˜ nal de referencia. La tarea que controla al motor 4 (T5) tiene la menor prioridad y el tiempo de activaci´on m´as largo de todas las tareas que controlan motores (cada 9 milisegundos), esto, en conjunto con el tiempo de respuesta que tiene el motor al aumentarle el voltaje, nos da como resultado que el comportamiento del motor 4 no sea tan preciso como el primer motor, sin embargo, es capaz de dar la vuelta requerida en el instante preciso (cada 2 segundos). Figura 5.11: Gr´afica del Comportamiento de los Motores en EDF. 5.5.4. Prueba 4: Control PD con P´ erdidas de Plazo Esta u ´ltima prueba esta compuesta de 5 tareas, y al igual que en las pruebas anteriores, la tarea 1 se encarga de generar una se˜ nal de referencia y las otras cuatro tareas de controlar los cuatro motores en tiempo real. El planificador utilizado es Rate Monotonic. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 5.5. Pruebas y Resultados 131 El objetivo de esta prueba es mostrar el comportamiento del kernel cuando existen p´erdidas de plazo en la ejecuci´on de las tareas, para esto fue necesario sobrecargar el uso del procesador de tal manera que su factor de utilizaci´on fuera mayor al 100 %. La Tabla 5.2 muestra los valores (en milisegundos) asignados a cada tarea, as´ı como la utilizaci´on que tienen sobre el procesador. T area Descripci´ on Ti ms Ci ms Utilizaci´ on T1 Se˜ nal de Referencia 2000 1 0.0005 T2 Motor1 3 1 0.333 T3 Motor2 5 3 0.6 T4 Motor3 7 1 0.142 T5 Motor4 9 1 0.111 1.1865 Tabla 5.2: Conjunto de Tareas Utilizadas en la Prueba 4 Con una utilizaci´on del 118 % del procesador se obtienen muchas p´erdidas de plazo durante la ejecuci´on de las tareas. En la Figura 5.12, la gr´afica de Gantt nos muestra los instantes en los que las tareas perdieron sus plazos, y como era de esperarse, las tareas con menor prioridad fueron las que m´as lo perdieron. Figura 5.12: P´erdidas de Plazo Ocurridas en la Prueba 4. En esta prueba las tareas las podemos clasificar en: Tareas Cr´ıticas. Las tareas T2, T3, T4 y T5 que controlan los motores. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 5. Ejemplo de Aplicaci´ on: Control Proporcional Derivativo de Motores de 132 Corriente Directa Tareas No-Cr´ıticas. La tarea T1 que cambia el valor de la se˜ nal de referencia. Cuando ocurre una p´erdida de plazo durante la ejecuci´on de una tarea, el resultado que se puede llegar a obtener depende completamente de la criticidad de la tarea que lo perdi´o. Por ejemplo: Las tareas que controlan los motores, se encargan de enviar un voltaje al motor para aumentar o reducir la velocidad de movimiento, leen del encoder2 la posici´on de giro exacta que tiene el motor en ese instante, y adem´as, calcula el siguiente voltaje a enviar en base a la f´ormula de control proporcional derivativo. Si estas tareas llegaran a perder su plazo (tal como sucede en esta prueba), el motor no obtendr´ıa el voltaje necesario y podr´ıa girar a una velocidad mayor a la que requer´ıa. Llegar´ıa el momento en el que motor girar´ıa demasiado r´apido y en cuesti´on de milisegundos la estabilidad de todo el sistema estar´ıa comprometida. En el caso de que la tarea que perdiera su plazo fuera una tarea no-cr´ıtica como la tarea T1, el problema se ver´ıa reflejado en el tiempo de giro del motor ya que no cambiar´ıa el sentido del giro cada 2 segundos como se ten´ıa previsto, sin embargo el sistema seguir´ıa funcionando. Esta prueba es importante y nos muestra claramente lo que puede llegar a suceder en caso de p´erdidas de plazo. Es necesario tener muy claro las prioridades que se asignan a las tareas y saber reconocer cuales son cr´ıticas y cuales no lo son. El analizar por completo el sistema y conocerlo a detalle, nos permitir´a asignar de manera correcta, los per´ıodos y tiempos de ejecuci´on de las tareas, adem´as de facilitarnos la decisi´on en la elecci´on del planificador de tiempo real. La ventaja de estos planificadores, sin importar cual se elija, es que permiten conocer cual va a ser el comportamiento de las tareas antes de ejecutarlas en el Kernel, permiti´endonos con esto, detectar las posibles fallas en la asignaci´on de tiempos sin tener que comprometer el funcionamiento del sistema de tiempo real. 2 El enconder est´ a f´ısicamente integrado al motor y se encarga de medir los pulsos por revoluci´ on. Cuando el motor tiene 2,500ppr significa que gir´ o una vuelta exacta Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez Cap´ıtulo 6 Conclusiones y Trabajo Futuro 6.1. Conclusiones En la actualidad, los sistemas de tiempo real se han ido integrando a la vida cotidiana cada vez m´as, las aplicaciones que los incluyen demandan una alta confiabilidad, y por lo tanto, los resultados que estos ofrecen deben ser correctos, predecibles y precisos. Como se mostr´o en esta tesis, una aplicaci´on de tiempo real est´a compuesta por un conjunto de tareas concurrentes que cooperan entre s´ı. En el kernel que se desarroll´o, las tareas son activadas a intervalos regulares y deben completar su ejecuci´on antes del t´ermino de su plazo de respuesta. A grandes rasgos, a lo largo de esta tesis se obtuvieron los siguientes resultados: 1. Se cre´o un kernel de Tiempo Real peque˜ no con capacidad de ser portado a cualquier otra plataforma port´atil o empotrada, es capaz de responder a interrupciones externas, controla y manipula tareas concurrentes y adem´as, comunica y sincroniza procesos mediante primitivas de acceso a buzones y sem´aforos. 2. Se estudiaron e implementaron los algoritmos de planificaci´on de tareas FIFO Round Robin, Rate Monotonic y Earliest Deadline First, los dos u ´ltimos creados especialmente 133 134 Cap´ıtulo 6. Conclusiones y Trabajo Futuro para sistemas de tiempo real. 3. Se obtuvo un kernel con c´odigo f´acil de entender y modificar, por lo que permite que se le puedan agregar futuros algoritmos de planificaci´on de tiempo real dise˜ nados en el Cinvestav y a su vez experimentar el funcionamiento de estos en tiempo real dejando atr´as las simulaciones. 4. Se experiment´o y prob´o el funcionamiento del kernel en el departamento de control, para esto se crearon 4 tareas, cada tarea control´o un servomotor en tiempo real y su objetivo era manipular el voltaje del motor de tal forma que su comportamiento fuera semejante al de la se˜ nal de referencia. 6.2. Trabajo Futuro El ´area de los sistemas de tiempo real es muy amplia, y ahora que contamos con un kernel de tiempo real cuyo c´odigo conocemos y podemos cambiar en base a nuestras necesidades, son muchas las extensiones o variaciones que se le podr´ıan hacer. A continuaci´on se detallan algunos de estos posibles cambios: Extensi´ on a Tareas Aperi´ odicas. El kernel que se desarroll´o al igual que todas las investigaciones actuales realizadas dentro de este, consideran u ´nicamente el caso en donde las tareas son est´aticas, los tiempos de computo de las tareas son conocidos y se ejecutan por un tiempo m´aximo pre-establecido. Entre los trabajos a futuro que podr´ıan realizarse se encuentra, extender la capacidad de Kernel para que pueda manejar tareas aperi´odicas cuyo tiempo de arribo al sistema sea en instantes aleatorios, y que adem´as los par´ametros temporales de las tareas var´ıen de forma impredecible durante su ejecuci´on sin que esto llegue a afectar en el cumplimiento de sus plazos. Extensi´ on a Restricciones de Precedencia. En el modelo utilizado para dise˜ nar el Kernel, se considera el hecho de que algunas de las tareas preceden en ejecuci´on a otras. Una posible mejora a este modelo ser´ıa, la posibilidad de manejar tareas con restricciones de precedencia ac´ıclicas, y con restricciones de precedencia de tipo AND/OR. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 6.2. Trabajo Futuro 135 Extensi´ on a Sistemas Distribuidos y a Sistemas con M´ ultiples Procesadores. El Kernel ha sido dise˜ nado para que funcione correctamente en una computadora con un s´olo procesador, sin embargo, se le puede mejorar agreg´andole primitivas que permitan la comunicaci´on entre tareas de kernels que se est´en ejecutando en distintas m´aquinas con la finalidad de poder controlar sistemas de tiempo real distribuidos. Otra mejora importante, es la de cambiar el dise˜ no del kernel de tal forma que sea capaz de ejecutar las tareas en m´aquinas con 2 o m´as procesadores. Extensi´ on a Linux. La plataforma actual del Kernel es MS-DOS debido a que este sistema operativo permite ejecutar el Kernel sin que afecte o deshabilite las interrupciones del hardware de la m´aquina (tal como lo hace Windows), y adem´as porque con muy pocas modificaciones es posible separarlo de MS-DOS dejando al kernel como sistema operativo independiente. El lenguaje que se utiliz´o es ANSII C por lo que, si en un futuro fuera necesario experimentar el comportamiento del kernel sobre plataformas Linux, es posible realizarlo con tan s´olo cambiar aquellas primitivas que utilizan interrupciones como la del cambio de contexto. Extensi´ on a PDAS. Las agendas electr´onicas PALMS, tel´efonos celulares y otros PDA’s similares son de uso com´ un actualmente y cada vez necesitan tener un mejor sistema operativo, el Kernel desde un principio se dise˜ n´o pensando en su adaptaci´on a futuro para este tipo de aparatos (su c´odigo es peque˜ no y funciona con muy poca memoria). Trabajar en Plataformas Empotradas. Gracias a las caracter´ısticas del kernel, es posible introducirlo en cualquier plataforma empotrada que cuente con un procesador con arquitectura de Intel 80x86. Actualmente se tiene pensado adquirir un plataforma de este tipo llamada LBC-9116 la cual tiene un procesador Pentium M de gran velocidad que permite controlar la frecuencia y el voltaje. Esta plataforma junto con el kernel, permitir´an probar y experimentar con algoritmos de tiempo real que se tienen y cuya caracter´ıstica principal es maximizar el ahorro de energ´ıa y minimizar el n´ umero de plazos perdidos. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez 136 Cinvestav-IPN Cap´ıtulo 6. Conclusiones y Trabajo Futuro Secci´ on Computaci´ on Oscar Miranda G´ omez Bibliograf´ıa [1] Wind River Systems, Inc. Sistemas Operativo de Tiempo Real VxWorks http://www.windriver.com [2] FSM Labs. Real-Time Linux http://www.fsmlabs.com [3] Servo To Go, Inc. Tarjeta SERVOTOGO http://www.servotogo.com/ [4] Universidad de Michigan EMERALDS (Extensible Microkernel for Embedded RealTime, Distributed Systems) http://kabru.eecs.umich.edu/rtos/emeralds.html [5] Escuela Superior Santa Ana de Pisa, Italia. SHARK (Soft and Hard Real-Timer Kernel) http://shark.sssup.it [6] Universidad de Massachusetts en Amherts Sistema Operativo de Tiempo Real Spring. http://www-ccs.cs.umass.edu/rts/spring.html [7] TenAsys Corporation iRMX86 Real-Time Operating System for Intel Architecture http://www.tenasys.com/irmx.html [8] Wind River Systems, Inc. The Next Generation of Embedded Development Tools. Document No. 825-000026-000 property of Wind River Systems, Inc. Huntsville, Alabama. July 1998. [9] Dr. Martin Timmerman and Bart Van Beneden. VxWorks/x86 5.3.1 evaluation. RealTime Magazine, issue 1999-4, pages 6-9, 1999. [10] Marcus Goncalves Is Real-Time Linux for Real?. Real-Time Magazine, issue 1999-4, 1999. 137 BIBLIOGRAF´ IA 138 [11] Victor Yodaiken and Michael Barabanov. A Real-Time Linux. In proceedings of Linux Applications Development and Development Conference (USELINUX). January, 1997. [12] Jos´e Ismael Ripoll Ripoll Tutorial de Real Time Linux Universidad Polit´ecnica de Valencia. 2001. [13] K. M. Zuberi and K. G. Shin. EMERALDS: A microKernel for embedded real-time systems. In proceedings of IEEE Real-Time Technology and Applications Symposium PP.241-249, June, 1996. [14] Khawar M. Zuberi and K. G. Shin. EMERALDS: A Small-Memory Real-Time Microkernel. In proceedings of IEEE Transactions on Software Engineering, Vol. 27, No. 10, October, 2001. [15] Paolo Gai, Luca Abeni, Massimiliano Giorgi and Giorgio Buttazzo. A New Kernel Approach for Modular Real-Time Systems Development. In proceedings of the 13th IEEE Euromicro Conference on Real-Time Systems, Delft. NL, June 2001. [16] Paolo Gai, Giorgio Buttazzo, Luigi Palopoli, Marco Caccamo and Giuseppe Lipari. S.H.A.R.K User Manual. Scuola Superiore di Studi e Perfezionamento S. Anna, ReTiS Lab, May, 2003. [17] J.A. Stankovic and K. Ramamrithan. The Spring Kernel: A New Paradigm for RealTime Systems In proceedings of IEEE Software, Vol.8 No.3, pp 62-72, May, 1991. [18] John A. Stankovic. The Spring Architecture. Dept. of Computer and Information Science, University of Massachusetts, Amherst, Mass. June 1990. [19] D. Niehaus, E. Nahum, J. Stankovic, K. Ramamritham. Architecture and OS Support for Predictable Real-Time Systems. Dept. of Computer and Information Science, University of Massachusetts, Amherst, Mass. March 1992. [20] Marie Sie-Een Teo. A Preliminary Look at Spring and POSIX.4, Spring internal document July, 1995. [21] Juan A. de la Puente Alfaro Apuntes del Doctorado en Sistemas de Tiempo Real, Universidad Polit´ecnica de Madrid Curso 2002-2003. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez BIBLIOGRAF´ IA 139 [22] Silberschatz, Galvin and Gagne. Operating Systems Concepts, Sixth Edition, Ed. John Wiley and Sons, inc. 2002. [23] Giorgio C. Buttazzo. Hard Real-Time Computing Systems, Predictable Scheduling Algorithms and Applications. First Edition, Ed. Kluwer Academic Publishers. January, 1997. [24] C.L. Liu and W. Layland. Scheduling Algorithms for Multiprogramming in Hard RealTime Environment. Journal of the Association for Computing Machinery, 2:46-61. 1973. [25] Lui Sha John Lehoczky and Ye Ding. The Rate Monotonic Scheduling Algorithm: Exact Characterization and Average Case Behavior. IEEE Real-Time Systems Symposium, pages 166-171. December 1989. [26] J. Y. T. Leung and J. Whiteheaad. On the Complexity of Fixed-Priority Scheduling of Periodic Real-Time Task. Performance Evaluation, 2(4):237-250. December 1982. [27] Jos´e Ismael Ripoll Ripoll Planificaci´on en Sistemas de Tiempo Real. Universidad Polit´ecnica de Valencia, Departamento de Inform´ atica de Sistemas y Computadores. 2000. [28] Katsuhiko Ogata Ingenier´ıa de Control Moderna. Prentice Hall, 1980. [29] Katsuhiko Ogata Ingenier´ıa de Control Moderna. Prentice Hall, 1980. ◦ [30] Karl J. A str¨ om and Bj o¨rn Wittenmark. Computer-Controlled Systems: Theory and Design (2nd ed.). Prentice Hall, Inc. 1990. Cinvestav-IPN Secci´ on Computaci´ on Oscar Miranda G´ omez