Ahorro Energético en la Planificación de Sistemas en Tiempo Real

AHORRO ENERGÉTICO EN LA PLANIFICACIÓN DE SISTEMAS EN TIEMPO REAL ARQUITECTURA I TECNOLOGIA DE COMPUTADORS UNIVERSITAT POLITÈCNICA DE CATALUNYA DOCTORANDO: M. ÀNGELS MONCUSÍ CO-DIRECTORES: ALEJANDRO ARENAS JESÚS LABARTA AGRADECIMIENTOS Aquesta tesis, la dedico a tota la meva família especialment a la meva mare i sogra que han tingut cura dels nens ( Carla i Dídac) per a què jo tingués temps de treballar, al meu marit, que tot i estar sempre treballant ha tingut sempre temps per animar-me, també la vull dedicar al meu cunyat Joaquim, que no ha pogut veure-la finalitzada però segur que n’hagués fet broma. Vull agrair al Jesús Labarta i a l’Alex Arenas que van acceptar dirigir-me la tesis, així com la paciència, consells i les moltíssimes revisions del document que m’han fet. També vull agrair al meu company de fatigues Josep M. Banús, la companyia en els viatges a Barcelona, i l’ajuda que m’ha ofert en la cerca de informació, la generació dels jocs de proves sintètics, les discussions que hem fet i els consells que m’ha donat. - 5 de 209 - ÍNDICE Capítulo 1 .............................................17 Ahorro Energético en Sistemas de Tiempo Real ....................................................... 17 1.1 Introducción ............................................................................................... 19 1.2 Sistemas de Tiempo Real........................................................................... 21 1.3 Reducción del consumo energético............................................................ 31 1.4 Planificación con ahorro energético........................................................... 36 1.5 Objetivos de la tesis ................................................................................... 40 Capítulo 2 .............................................43 Planificación con Ahorro Energético en Sistemas de Tiempo Real .......................... 43 2.1 Introducción. .............................................................................................. 45 2.1.1 Low Power Fixed Priority Algorithm Scheduling..................................... 48 2.1.2 Dual Priority Scheduling Algorithm.......................................................... 51 2.2 Metodología y desarrollo. .......................................................................... 52 2.2.1 Power Low Modified Dual Priority Scheduling. ....................................... 53 2.2.2 Ejemplo de funcionamiento del PLMDP................................................... 56 2.2.3 Consideraciones generales sobre la velocidad del procesador................... 62 2.2.4 Enhanced Power Low Dual Priority Scheduling ....................................... 67 2.2.5 Ejemplo de funcionamiento algoritmo EPLDP.......................................... 73 2.2.6 Estimación dinámica de la utilización del procesador............................... 75 2.3 Comparativa entre los algoritmos descritos............................................... 77 6 de 209 - 2.3.1 Conjunto individual de tareas simple......................................................... 78 2.3.2 Conjuntos de tareas sintéticos. ................................................................... 85 2.4 Conclusiones ..............................................................................................97 Capítulo 3 .............................................99 Recursos Compartidos................................................................................................ 99 3.1 Introducción .............................................................................................101 3.2 Metodología y desarrollo. ........................................................................ 104 3.2.1 Ejemplo de funcionamiento ..................................................................... 106 3.2.2 Planificabilidad del sistema...................................................................... 108 3.2.3 Aplicación del protocolo a los algoritmos de planificación..................... 111 3.2.4 Cálculo de la velocidad de ejecución del procesador............................... 112 3.3 Comparativa entre los algoritmos. ...........................................................113 3.3.1 Caso real: Caso de control automático..................................................... 114 3.4 Conclusiones ............................................................................................119 Capítulo 4 ...........................................121 Plazos Globales y Precedencias entre Tareas........................................................... 121 4.1 Introducción .............................................................................................123 4.2 Metodología y desarrollo: Análisis del plazo global................................ 127 4.2.1 Adecuación de los algoritmos de planificación........................................ 130 4.3 Conclusiones ............................................................................................143 Capítulo 5 ...........................................145 Dualidad entre Ahorro de Energía y Tiempo de Finalización .................................145 5.1 Introducción .............................................................................................147 - 7 de 209 - 5.2 Planificación de las tareas aperiódicas..................................................... 148 5.3 Tareas aperiódicas y ahorro energético.................................................... 153 5.4 Conclusiones............................................................................................ 161 Conclusiones y Trabajo Futuro .......163 Anexos ................................................169 Anexo 1 Low Power Fixed Priority Algorithm Scheduling................................. 171 Anexo 2 Dual Priority Algorithm......................................................................... 179 Anexo 3 Low Power EDF .................................................................................... 185 Glosario...............................................193 Referencias Bibliográficas ................199 - 9 de 209 - ÍNDICE DE FIGURAS Figura 1: Dos ejemplos de sistemas de control en tiempo real, el de la izquierda de aviónica, y el de la derecha un control digital........................................... 22 Figura 2: Modelo de sistema de tiempo real.............................................................. 23 Figura 3: Características de la tarea τi........................................................................ 24 Figura 4: Clasificación de los planificadores clásicos de tiempo real. ...................... 27 Figura 5: Relación entre los componentes software y hardware relevantes a APM [29]. ........................................................................................................... 31 Figura 6: Relación entre los componentes software y hardware relevantes al ACPI. [28] ............................................................................................................ 32 Figura 7: Clasificación de los planificadores de bajo consumo en sistemas Tiempo Real............................................................................................................ 37 Figura 8: Pseudocódigo del algoritmo de planificación Power Low Modified Dual- Priority (PLMDP). .................................................................................... 56 Figura 9: Diagrama de planificación de procesos usando el algoritmo PLMDP cuando las tareas consumen el 100% del WCET. ..................................... 57 Figura 10: Diagrama de planificación de procesos usando el algoritmo FPS cuando todas las tareas consumen el 50 % de su WCET....................................... 59 Figura 11: Diagrama de planificación de procesos usando el algoritmo LPFPS cuando todas las tareas consumen el 50 % de su WCET. ......................... 59 Figura 12: Diagrama de procesos del algoritmo de ahorro energético PLMDP, cuando las tareas consumen el 50% WCET.............................................. 60 16 de 209 - Figura 73: Gráfica de consumo energético normalizado de los distintos planificadores con un consumo del 90% del WCET en las tareas periódicas con periodos armónicos y una utilización aperiódica del 10% con un tiempo de cálculo de las tareas aperiódicas de 1. .................................... 160 Figura 74: Gráfica de tiempo de finalización normalizado de los distintos planificadores con un consumo del 90% del WCET en las tareas periódicas con periodos armónicos y una utilización aperiódica del 10% con un tiempo de cálculo de las tareas aperiódicas de 1. .................................... 160 Figura 75: Esquema de las estructuras de datos necesarios para implementar el Low Power Fixed Priority Algorithm Scheduling (LPFPS)............................ 172 Figura 76: Pseudocódigo para el cálculo de la velocidad del procesador con el algoritmo de Low Power Fixed Priority Scheduling (LPFPS)................ 174 Figura 77: Diagrama de planificación de procesos usando el algoritmo FPS consumiendo el 100% del WCET............................................................ 175 Figura 78: Diagrama de planificación de procesos usando el algoritmo LPFPS..... 176 Figura 79: Esquema de las estructuras de datos necesarios para implementar el Dual Priority Scheduling Algorithm................................................................ 180 Figura 80: Pseudocódigo del planificador Dual Priority de [23]. ............................ 182 Figura 81: Diagrama de planificación de procesos usando el algoritmo DPS......... 183 Figura 82: Pseudocódigo para el cálculo de la velocidad del procesador con el algoritmo de Low Power Earliest Deadline First Scheduling (LPEDF). 188 Figura 83: Diagrama de planificación de procesos usando el algoritmo EDF......... 190 Figura 84: Diagrama de planificación de procesos usando el algoritmo LPEDF.... 190 Capítulo 1 AHORRO ENERGÉTICO EN SISTEMAS DE TIEMPO REAL El objetivo de este capítulo es dar una visión general de los sistemas informáticos de tiempo real y del problema del consumo energético en los mismos, realizando un énfasis especial en la problemática propia de la planificación con ahorro energético de las tareas de tiempo real. Ahorro Energético en Sistemas de Tiempo Real - 19 de 209 - 1.1 Introducción En la actualidad el uso de los procesadores se ha extendido considerablemente y se hallan en todos los campos, desde aparatos electrodomésticos, periféricos y controladores hasta llegar a los grandes equipos computacionales que requieren del uso de aplicaciones informáticas de gran complejidad. Los procesadores están evolucionando continuamente, ofreciendo configuraciones hardware más pequeñas, rápidas, fiables, y baratas, permitiendo con ello generalizar su uso. Ejemplos obvios de esta evolución se dan en el uso cada vez mayor de los teléfonos móviles, los PDA’s, las video-consolas, los ordenadores portátiles, y los no tan obvios como los procesadores empotrados que se encuentran en la mayoría de electrodomésticos modernos. A este tipo de aplicaciones se las denomina genéricamente aplicaciones de tiempo real o empotradas [14]. Siguiendo esta evolución de los procesadores, las aplicaciones que ejecutan los sistemas de tiempo real pueden ser mas complejas y precisas puesto que se dispone de una mayor velocidad de proceso. El desarrollo de estos procesadores más complejos y potentes, precisarían, a su vez, de un consumo energético mayor, provocando una mayor generación de calor y de mecanismos para su disipación. Esta disipación se hace más difícil conforme la densidad de los transistores en los chips y la de estos en los procesadores va incrementándose, lo que provoca problemas de durabilidad de los sistemas. Además, este mayor consumo energético es un gran inconveniente para aquellos sistemas que precisen del uso de baterías (sistemas móviles), y en menor medida para todos los sistemas en general. Existen sistemas que pueden estar localizados en entornos donde el ahorro energético es esencial para asegurar la operabilidad y duración del sistema, por ejemplo en aplicaciones espaciales, donde un menor consumo se traduce en menores paneles solares y menores baterías, por tanto en menor peso y dimensión. En la nota de prensa de la corporación de IBM1 en el año 2001 hace referencia al problema del consumo energético en los siguientes términos: 1 http://www-5.ibm.com/es/press/notas/2001/octubre/lowpower.html Capítulo 1 - 20 de 209 - “Durante años, IBM ha ido reduciendo su propio gasto en el consumo de energía mediante avances en tecnologías de la información y otras acciones para el ahorro de energía. En el año 2000, estas acciones de IBM a nivel mundial tuvieron como resultado un recorte en el consumo de electricidad de 271 millones de kilovatios / hora -lo que equivale al suministro anual de 45.000 hogares-, y una reducción en el consumo de combustible equivalente a 5.300.000 litros de gasolina. Como resultado, IBM evitó la emisión de aproximadamente 157.500 toneladas de dioxinas procedentes del carbón y ahorró unos 15,2 millones de dólares. Durante los últimos 10 años (1991 - 2000) IBM ha ahorrado aproximadamente 527 millones de dólares en el consumo de electricidad y ha evitado la emisión de 5,6 millones de toneladas de CO2”. A nivel hardware, investigadores de distintas universidades [12],[19],[67],[85], y grandes compañías de desarrollo de procesadores han realizado una fuerte inversión en el desarrollo de procesadores de bajo consumo energético, por ejemplo: En marzo del 2003 en una nota de prensa de Intel2 se dice que: El procesador PXA255 de Intel, basado en la microarquitectura Xscale, disponible en las velocidades de 100, 200 y 400 MHz, aporta dos mejoras ya al precedente PXA250: mayor rendimiento general y menor consumo energético. Ha doblado la velocidad del bus interno, mejorando así el rendimiento de las aplicaciones del dispositivo y ha reducido el tensión de alimentación del procesador a 1,3 voltios a 400 MHz. Esta reducción se traduce en un 30 por ciento de ahorro energético, cuando se encuentra en funcionamiento, y a hasta un 60 por ciento, cuando está inactivo. en diciembre del 2004 en una nota de prensa de AMD3 se dice que: AMD e IBM anunciaron hoy que han desarrollado una nueva y excepcional tecnología de transistores de silicio tensado con el objetivo de mejorar el rendimiento de los procesadores y el ahorro de energía. El innovador proceso da como resultado un aumento de la velocidad del transistor de hasta un 24%, 2 http://www.intel.com/pressroom 3 http://www.amd.com/es-es/Corporate/VirtualPressRoom Ahorro Energético en Sistemas de Tiempo Real - 21 de 209 - a los mismos niveles de energía, comparado con transistores similares fabricados sin esta tecnología. Estos transistores más rápidos y que utilizan la energía de forma más eficaz son la base de unos procesadores de mayor rendimiento y menor consumo energético. Al disminuir el tamaño de los transistores éstos funcionan más rápido, pero también se corre el riesgo de que aumente el nivel de calor y el consumo de energía debido a fugas eléctricas o a una conmutación ineficaz. El silicio tensado desarrollado conjuntamente por AMD e IBM ayuda a superar estas dificultades. Además, este proceso convierte a AMD e IBM en las primeras empresas en introducir el silicio tensado que funciona con tecnología de silicio sobre aislante (SOI), lo que resulta en una mejora del rendimiento y un mayor ahorro de energía. A nivel software, también se han invertido grandes esfuerzos en la minimización energética global (hardware y software) [18], [20], a nivel de la BIOS [24], del sistema operativo [39] y de la compilación de las aplicaciones [62]. Se extenderán estos puntos en apartados posteriores. La presente tesis, se centrará únicamente a nivel de sistema operativo, más concretamente en la planificación de tareas de tiempo real. En el siguiente punto se efectuará una breve descripción de las características fundamentales de la especificación de los sistemas de tiempo real, de la problemática de la reducción energética en la tecnología CMOS y de los algoritmos para la planificación de tareas de tiempo real con ahorro energético existentes. Para finalizar este capítulo se especificaran los objetivos concretos que se han planteado. 1.2 Sistemas de Tiempo Real La característica fundamental de los sistemas de tiempo real es que su correcto funcionamiento no depende únicamente del resultado lógico de la computación sino también del tiempo en el que se producen los resultados. A veces, es más conveniente tener un resultado impreciso en un cierto instante a tenerlo con gran precisión pero demasiado tarde. Por tanto, el parámetro de rendimiento más importante para estos sistemas es el cumplimiento de las restricciones temporales Capítulo 1 - 22 de 209 - impuestas por la aplicación en tiempo de diseño. Otra característica importante de estos sistemas es que las aplicaciones deben interactuar con su entorno a través de sensores y actuadores. Deben ser, por tanto, buenos receptores de eventos externos proporcionándoles una buena calidad de servicio o tiempo de finalización adecuado. Los sistemas de tiempo real, según el tipo de restricción temporal que poseen, pueden clasificarse en: • Sistemas de tiempo real estricto (Hard real time) • Sistemas de tiempo real firme (Firm real time) • Sistemas de tiempo real no estricto (Soft real time) Los sistemas de tiempo real estricto son aquellos en los que es absolutamente imperativo el cumplimiento de todos los plazos temporales, debido a que su incumplimiento puede dar lugar a una catástrofe, en vidas humanas o económicas. Básicamente, estos sistemas se hallan en aplicaciones de control industrial, aplicaciones aeronáuticas, etc. En los sistemas de tiempo real no estrictos, el tiempo de finalización es importante, pero el sistema seguirá funcionando aunque los plazos no se cumplan, simplemente habrá una degradación de la calidad de servicio, un ejemplo de estos sistemas son los sistemas multimedia en general. En la Figura 1 se pueden observar dos ejemplos de sistemas de tiempo real. Los sistemas de tiempo real mixto o firme, son aquellos en los que si se pierde algún plazo de vez en cuando, hay una degradación del servicio que puede compensarse usando mecanismos de control de calidad, por ejemplo, en las aplicaciones de control industriales, como seria el caso de las cadenas de producción, el control de una cinta transportadora, etc. Figura 1: Dos ejemplos de sistemas de control en tiempo real, el de la izquierda de aviónica, y el de la derecha un control digital. Ahorro Energético en Sistemas de Tiempo Real - 23 de 209 - Las aplicaciones desarrolladas para los sistemas de tiempo real estricto se basan en una serie de sensores que reciben información del mundo exterior y unos actuadores que permitirán ejecutar acciones de control sobre el sistema. Las aplicaciones de este tipo, necesitan tener una habilidad especial para coordinar un gran número de actividades en paralelo, pero de complejidad baja. Cada una de estas actividades esta implementada en forma de tarea, que la mayoría de veces serán de ejecución cíclica o periódica, por ejemplo la evaluación del estado de un sensor cada cierto tiempo. Sin embargo, existen algunas tareas que no pueden ser periódicas por su propia naturaleza sino que deberán ser aperiódicas, tareas que se ejecutan como respuesta a un evento externo a la aplicación por ejemplo alarmas y/o peticiones de un operador de consola, o como respuesta a un evento interno a la propia aplicación (acciones asíncronas requeridas por el propio programa). En general, las tareas implementadas para estas aplicaciones pueden tener plazos temporales estrictos (hard deadlines) o no estrictos (soft deadlines). A las tareas aperiódicas con plazos temporales se las llama tareas esporádicas, siendo las tareas aperiódicas aquellas que no los tienen. Normalmente, las aplicaciones de tiempo real tendrán una mezcla de todo tipo de tareas. A menudo las tareas esporádicas son tratadas como tareas periódicas en el que el periodo viene fijado por el tiempo mínimo entre llegadas de estas tareas, de manera que estas tareas serán siempre aceptadas. A continuación en la Figura 2 se muestra el modelo de sistema explicado. periódicas rechazo T. esporadicas T. aperiódicas T. periódicas test aceptación Procesador esporádicas y aperiodicas Planificador Figura 2: Modelo de sistema de tiempo real. Últimamente, debido a los avances tecnológicos que se han producido en la electrónica en general y en la informática en particular, se ha aumentado la complejidad de estos los sistemas de tiempo real aumentado también la complejidad de las tareas. El diseño de este tipo de aplicaciones es más complejo si en lugar de Capítulo 1 - 24 de 209 - usar un único procesador se usan varios procesadores formando una aplicación distribuida, ya que presentan nuevos requerimientos físicos tales como canales de interconexión entre los procesadores, secuencialidad entre tareas de distintos procesadores, restricciones temporales globales (desde el momento en que se produce el evento en un procesador hasta la ejecución de la última tareas de una cadena de tareas que pueden hallarse en distintos procesadores), recursos globales compartidos entre los diversos procesadores, etc. Realizando una simplificación importante, se puede decir que las tareas que ejecutan los sistemas de tiempo real tienen como características más importantes: • Periodo de activación (T) • Plazo temporal (D) • Peor tiempo de ejecución (WCET) El periodo de activación de una tarea es la separación temporal entre dos activaciones sucesivas de la tarea, el plazo temporal es el tiempo que tiene la tarea para emitir una respuesta una vez activada y el peor tiempo de ejecución es el máximo tiempo que tardará la tarea en realizar sus cálculos. Gráficamente, pueden verse representados estos tiempos en la Figura 3. Activación τ i WCET i D i T i Activación τ i Tiempo Figura 3: Características de la tarea τi Dadas las anteriores características se deduce que 0 ≤ WCET ≤ D. El porcentaje de utilización del procesador de una tarea determinada τi viene especificado por WCETi/Ti, por tanto la suma del porcentaje de utilización de todas las tareas que se ejecutaran en un procesador determinado debe cumplir: 1 1 ≤= ∑ = n i i i T WCET U (ec. 1) Ahorro Energético en Sistemas de Tiempo Real - 25 de 209 - El periodo y el plazo temporal de las tareas viene impuesto por las características del sistema físico que se quiera controlar y se determina en tiempo de diseño de la aplicación de tiempo real, sin embargo, el cálculo del peor tiempo de finalización es más complejo. En el artículo de P. Puschner y A. Burns [71] se encuentran las referencias básicas de cómo se puede realizar este cálculo. El WCET se calcula en el peor de los casos, por tanto, es una cota superior del tiempo máximo de ejecución de una determinada tarea. Esta cota temporal es dependiente de la arquitectura de la máquina donde se ejecuta, y no debe tener en cuenta las posibles interferencias entre las distintas tareas del sistema, tales como apropiaciones del procesador por una tarea de mayor prioridad, tiempos de bloqueo en el acceso a un recurso compartido, y demás tiempos que dependen del tipo de planificador que se use. A modo de resumen, el cálculo del WCET tiene que permitir: • Proporcionar una cota superior segura para el tiempo que tardará en ejecutarse una tarea, el WCET se usará para validar la planificabilidad del sistema de tiempo real. • Ajustarse al tiempo real de ejecución de la tarea, un tiempo muy pesimista dará lugar a una baja utilización real del procesador. Los principales problemas que se pueden encontrar en el momento de realizar el cálculo del WCET son los siguientes: • Caracterización de la secuencia de ejecución de la tarea, análisis de la semántica del código de las aplicaciones, por ejemplo, en cualquier sentencia de control, siempre se tiene que evaluar el camino más largo [2] de ejecución. • Cambio de la representación del código en lenguaje fuente a la representación en código máquina. Los compiladores, especialmente los que optimizan código, pueden modificar considerablemente el resultado temporal de ejecución a la vez que hacen difícil analizar los posibles caminos de ejecución hallados anteriormente. • Análisis temporal a nivel de arquitectura hardware. Este análisis debe tener en cuenta todos los tiempos de ejecución de cada posible secuencia de ejecución de código, para después calcular la cota superior. En los procesadores actuales, el tiempo de ejecución no depende exclusivamente de las instrucciones que ejecuta sino que también depende del estado del Capítulo 1 - 32 de 209 - Figura 6: Relación entre los componentes software y hardware relevantes al ACPI. [28] Estos estándares de la BIOS utilizan a nivel inferior los mecanismos de ahorro energético que proporcionan las arquitecturas de los procesadores actuales [3] [31] [69] [84] que son: • DVS (Dynamic Voltage Scaling)[67]-[70]. Esta técnica, permite la reducción de la energía consumida por el procesador, a base de reducir el voltaje suministrado al procesador y al mismo tiempo, reduciendo proporcionalmente la velocidad de ejecución de las tareas. • Diversos estados de alimentación energética[30]: o Preparado o activo: el equipo o el dispositivo está totalmente encendido y listo para su uso. o Inactividad: La inactividad es un estado intermedio dependiente del sistema que intenta ahorrar energía. Se entra en estado de inactividad cuando la Unidad central de proceso (CPU) está inactiva y se sabe que no Ahorro Energético en Sistemas de Tiempo Real - 33 de 209 - se ha producido ninguna actividad del dispositivo durante un período de tiempo especificado. El equipo no volverá al estado Activo hasta que se produzca una interrupción de hardware o se tenga acceso a cualquier dispositivo controlado. En el estado de inactividad se conservan todos los datos y parámetros operativos. o Suspendido: El estado Suspendido de un equipo se define como el mínimo nivel de consumo de energía posible que conserva los datos y parámetros operativos. Cuando el equipo se encuentra en estado Suspendido, no se realiza ninguna operación hasta que se reanude la actividad normal. La reanudación de la actividad no se produce hasta que se produce un suceso externo, como presionar un botón, la alarma de un temporizador, etc. o Hibernación: La hibernación guarda todo el estado del equipo y apaga la alimentación. Se trata del estado mínimo de suspensión de energía disponible y es seguro frente a cortes de alimentación eléctrica. Cuando reanuda la actividad desde un estado de suspensión hibernado, la BIOS realiza las pruebas POST normales y después lee el archivo de hibernación que se creó para guardar el estado del equipo. El equipo vuelve al último estado que tenía antes de que entrara en modo de hibernación. El modo de hibernación reduce el tiempo necesario para el inicio. o Apagado: Cuando se encuentra en el estado Apagado, el equipo o el dispositivo no recibe alimentación eléctrica y está inactivo. En el estado Apagado puede que los datos y los parámetros operativos no se conserven. La reducción de la energía que utiliza la BIOS y los sistema operativos vendrá dada por la detección de la inactividad del procesador así como de los diversos periféricos, sin embargo, las aplicaciones de control y algunas aplicaciones multimedia deben ejecutarse de manera continua, por ejemplo la compresión-descompresión de video o voz, y esta técnica por si sola no resulta útil. Por otra parte, estas aplicaciones no requieren un tiempo de finalización muy pequeño, sino que para obtener una buena calidad de servicio es suficiente con obtener el resultado antes de un determinado instante de tiempo, especificado durante el diseño de la aplicación. Para estas Capítulo 1 - 34 de 209 - aplicaciones resulta adecuado el uso del la técnica de DVS que consiste en reducir la tensión suministrada junto con la velocidad del procesador, siempre que la aplicación no requiera obtener el máximo rendimiento de este. En los procesadores basados en la tecnología CMOS, la potencia consumida (Pcmos) depende de tres fuentes principales[19], tal como indica la siguiente formula: ddleakageddscclkddLtcmos VIVIfVCpP ++= )( 2 (ec. 8) El primer término es la componente dinámica del consumo de potencia, donde CL es la capacitancia del procesador, fclk es la frecuencia del reloj, pt es la probabilidad de que se produzca una transición (factor de actividad), Vdd es el voltaje suministrado al procesador. El segundo termino es la potencia disipada en el transito desde la fuente al procesador. Finalmente el tercero es la corriente de fuga (leakage current) que viene determinada por consideraciones tecnológicas. La componente principal de disipación de potencia en un procesador, bien diseñado, es la componente dinámica, y es la que los diseñadores de circuitos de bajo consumo intentan minimizar, es decir, intentan disminuir el primer factor de la ecuación (ec. 8) manteniendo la funcionalidad del procesador en el sistema. En el articulo de Borkar S. [11] se especifican los retos actuales en el diseño de baja potencia, que básicamente consisten en reducir la potencia activa (utilizando técnicas de DVS o de reducción de la actividad del procesador) y la corriente de fuga. Consideraciones generales sobre la latencia de los circuito CMOS implican una relación lineal entre el voltaje suministrado y la velocidad [77]. Por lo tanto, utilizando la técnica DVS, se puede reducir la energía consumida para ejecutar un determinado conjunto de tareas reduciendo la velocidad del procesador mediante el voltaje y consiguiendo así un decremento cuadrático en la potencia disipada. Esto implica que un pequeño decremento en la velocidad del procesador, tiene como consecuencia un importante ahorro energético. Sin embargo, al ejecutar a menor velocidad, las aplicaciones tardan más tiempo en finalizar. Teniendo en cuenta que en los sistemas con restricciones temporales, el correcto funcionamiento de la aplicación depende en gran medida del tiempo en el que se producen los resultados, se debe ser muy cuidadoso en el uso de esta técnica, utilizándola únicamente cuando el sistema no requiere la máxima capacidad del procesador. Ahorro Energético en Sistemas de Tiempo Real - 35 de 209 - A diferencia de los sistemas informáticos en general en los que las aplicaciones empiezan a ejecutarse y acaban, los sistemas informáticos de tiempo real, sistemas de control, tienen un funcionando periódico continuo, no acaba nunca. Si una aplicación informática se ejecuta a mayor velocidad termina antes que si se ejecuta a velocidad reducida. El consumo de energía es mayor a mayor velocidad de ejecución de las tareas, pero puede darse el caso que si la aplicación finaliza más rápidamente consuma menor cantidad de energía. Sin embargo, en las aplicaciones informáticas de tiempo real, al estar formadas por tareas periódicas, no finalizan, sino que al finalizar una instancia, deben esperar la siguiente instanciación de la tarea para continuar la ejecución, con lo que resultará energéticamente favorable ejecutar estas aplicaciones a la velocidad mínima que garantice los plazos temporales y minimice el tiempo libre de procesador. Procesadores recientes para sistemas empotrados reducen la corriente de fuga a nivel hardware [5],[17],[31],[63] usando distintos niveles en alimentación energética: standby: congelado (freeze), hibernación (hibernation) y cryo mode; y usando técnicas clock gating[46] que consisten en deshabilitar el reloj de los circuitos que no se están usando, evitando de este modo la disipación de energía debida a la carga y descarga de los circuitos no usados. Sin embargo, estas técnicas necesitan conocer que circuitos deben suspender y durante cuanto tiempo, una suspensión y activación frecuente generan una sobrecarga que puede derivar en una disipación de potencia mayor que la que se hubiera tenido sin usar la técnica. A nivel de planificación de tareas de tiempo real, también existen estudios recientes que reducen la corriente de fuga del procesador, la idea básica de estas técnicas es poner al procesador en standby el máximo tiempo posible, ejecutando las tareas de manera que se agrupe al máximo los intervalos en que el procesador queda libre para poder “dormirlo” el máximo tiempo posible disminuyendo el número de transiciones de potencia. Y.H. Lee [41] aplica la técnica de unión de los intervalos libres del procesador a los algoritmos de expulsivos de prioridades fijas y de prioridades dinámicas básicos ejecutándose las tareas a máxima velocidad y deteniendo el procesador cuando no existen tareas activas, en S. Irani [32] y R. Jejurikar [35] se combinan las dos técnicas: DVS y la unión de los intervalos libres de procesador. Capítulo 1 - 36 de 209 - 1.4 Planificación con ahorro energético La planificación de sistemas de tiempo real con ahorro energético se basa en la utilización de técnicas DVS, y más recientemente en algoritmos que unen los intervalos libres del procesador para reducir la corriente de fuga. Los algoritmos que utilizan las técnicas DVS, pueden calcular la velocidad del procesador estáticamente (off-line) o dinámicamente (on-line) (Figura 7). En el caso del cálculo estático, se calculan las velocidades óptimas a las que debe ir el procesador en cada momento para conseguir el mayor ahorro energético posible teniendo en cuenta el consumo de todo el WCET de las tareas y garantizando el cumplimiento de todos los plazos. Posteriormente, en tiempo de ejecución el planificador únicamente debe seguir los pasos marcados ejecutando cada tarea a la velocidad indicada. Los planificadores que usan el cálculo de velocidad del procesador estático, pueden ser planificadores estáticos, a los que se ha calculado el plan de ejecución de las tareas, o planificadores dinámicos, que se basan en la prueba de planificabilidad de los algoritmos de prioridades fijas (RMA, DMA) [36] o en la de prioridades dinámicas (EDF) [68]. En el caso de planificación con prioridades dinámicas se puede ahorrar más energía que con prioridades fijas debido a que el factor de utilización del procesador que garantizan las pruebas de planificabilidad es mayor. Durante la ejecución de la aplicación de tiempo real, lo habitual es que no se llegue a consumir la totalidad del WCET de la tarea, generándose en este caso “slack dinámico”, tiempo libre del procesador que se podría aprovechar para reducir la velocidad de ejecución de alguna tarea. Los planificadores que calculan la velocidad de manera estática, no permiten aprovechar el slack dinámico, ni permite fácilmente la ampliación del conjunto de tareas, como por ejemplo disponer de tareas aperiódicas. Sin embargo, existen planificadores mixtos, en los que el cálculo de la velocidad de proceso se realiza de manera estática, y durante la ejecución se puede reducir la velocidad para permitir aprovechar el slack dinámico producido por las tareas recientemente ejecutadas. Sin embargo, puede darse el caso que la tarea que ha generado el slack dinámico sea la última tarea que estaba lista para ser ejecutada. En este caso, el tiempo que ha dejado libre no podrá ser aprovechado por ninguna otra tarea, puesto que se deberá esperar que haya tareas en el sistema listas para ser ejecutadas. Ahorro Energético en Sistemas de Tiempo Real - 37 de 209 - Planificación dinámica con ahorro energético Cálculo velocidad dinámicoCálculo velocidad estático Look-ahead -EDF Static voltage RMA Low Power Fixed Priority Algorithm Scheduling Predictive FPS Stochastic voltage Static voltage EDF Cycle-conserving RMA/EDF Figura 7: Clasificación de los planificadores de bajo consumo en sistemas Tiempo Real Si el algoritmo de planificación tiene en cuenta el slack dinámico, otorgará cierta flexibilidad a este, permitiendo un mayor ahorro energético, en este caso el planificador reducirá “en tiempo de ejecución” la velocidad con la que ejecuta la tarea. Esta es la idea de la implementación del “cycle conserving RMA o EDF” [68]. Debe tenerse en cuenta que el slack dinámico no puede ser utilizado por cualquier tarea del sistema, sino que, ésta, debe cumplir unos determinados requisitos. El slack generado por una tarea de una determinada prioridad, únicamente puede ser aprovechado por las tareas de igual o menor prioridad, nunca por una tarea de mayor prioridad. Esto implica que el algoritmo deberá disponer de tantos contadores como posibles niveles de prioridad existan en el sistema. Cuando se ejecuta una tarea de una determinada prioridad, la reducción de la velocidad que se realizará será la calculada estáticamente más la que permite el slack dinámico de las tareas con una prioridad superior a la suya, siempre teniendo en cuenta que la reducción no provoque una perdida del plazo de la tarea que se ejecuta. El planificador presentado por F. Gruian en [26] el “stochastic voltage scheduler” se basa en dividir la ejecución de las tareas en diversas fases, de manera que cada fase se ejecutará a distinta velocidad del procesador. Esta velocidad se calcula de manera estática siguiendo una distribución de probabilidades de la duración de la ejecución Capítulo 1 - 38 de 209 - de las diferentes instancias de la tarea. Las velocidades del procesador escogidas serán menores conforme haya una mayor probabilidad de ejecución y mayores conforme esta probabilidad sea menor, de manera que en caso que la instancia actual no consuma todo el WCET, la parte no consumida sea la que habría ido a mayor velocidad, y por tanto será menor el tiempo que deje libre. En este planificador tiene en cuenta el slack dinámico que se produce, usándolo para reducir la velocidad de la siguiente tarea de menor prioridad que se ejecutará. Y por último, en el esquema del cálculo de velocidad totalmente dinámico la decisión sobre que tarea se ejecuta y a que velocidad de procesador, se calcula en tiempo de ejecución del sistema, consiguiendo con ello una mayor flexibilidad en la planificación de las tareas, y pudiendo en este caso añadir nuevas tareas al sistema. En este caso se deberá guardar información extra para ayudar al planificador a decidir en cada momento que tarea ejecuta y a que velocidad puede ejecutarla. Cuanta más información se guarde mayor podrá ser el refinamiento de la velocidad a la que se ejecute la tarea consiguiendo un mayor ahorro energético, sin embargo se tendrá un mayor consumo de energía debido al incremento de memoria necesaria y al algoritmo de planificación, que será más costoso en los cálculos. En el articulo de P. Pillai [68] se desarrolla, también, un algoritmo de ahorro energético en el que el cálculo de la velocidad es totalmente dinámico, el “Lookahead EDF”. Este algoritmo se basa en determinar la necesidad de cálculo futuro y retardar la ejecución de las tareas al máximo. De manera que ejecuta a la mínima velocidad posible que permite ejecutar la mínima parte de tarea necesaria para asegurar el cumplimiento de todos los plazos temporales futuros. Esto requerirá que la ejecución del trabajo retardado se ejecutará a mayor velocidad consumiendo mayor energía, pero si la aplicación no consume todo el WCET, la parte que dejará de ejecutarse es la que debería ejecutar a mayor velocidad. El resultado final es un mayor ahorro energético global, no dejando tiempo libre al procesador. Una conclusión que se puede extraer de este último articulo es que los planificadores de prioridades fijas no pueden obtener un ahorro energético tan agresivo como con los planificadores de prioridades dinámicas. A este tipo de planificadores que calculan la velocidad de manera totalmente dinámica, también, pertenece el “Low Power Fixed Priority Algorithm Scheduling” Ahorro Energético en Sistemas de Tiempo Real - 39 de 209 - desarrollado por Y. Shin y K. Choi en [77], este algoritmo es expulsivo con prioridades fijas, de manera que el planificador escoge siempre para ejecutar la tarea de mayor prioridad, reduciendo la velocidad del procesador únicamente cuando la tarea que va a ejecutarse es la única disponible para ser ejecutada. En el caso que esta tarea no consumiera todo el WCET, el procesador se quedaría libre, hasta la llegada de una nueva instancia al sistema. Este algoritmo es uno de los algoritmos base que se ha escogido para implementar nuestro algoritmo de planificación. Una posible implementación de este algoritmo se halla en el Anexo 1. El algoritmo “predictive FPS” de P. Kumar [40], se basa en predecir el tiempo que consumirá la instancia que se va a ejecutar. De manera que se dice que la tarea consumirá la media aritmética de lo que han consumido las instancias ya ejecutadas de esa tarea. La reducción de velocidad del procesador se efectuará, al igual que en el algoritmo anterior, únicamente cuando la tarea es la única tarea del sistema lista para ser ejecutada. Se debe tener en cuenta que aunque con este algoritmo se logre un menor consumo energético que con el anterior algoritmo puede haber una perdida de las restricciones temporales de algunas tareas debido a que alguna instancia consuma más tiempo del anunciado por el WCET, lo que es inaceptable si el sistema es de tiempo real estricto. Al igual que en los sistemas de tiempo real convencionales, estos planificadores se pueden ampliar para que tengan en cuenta los recursos compartidos y la secuenciación temporal entre tareas. Capítulo 1 - 40 de 209 - 1.5 Objetivos de la tesis El objetivo principal de esta tesis es el estudio de la planificación de las tareas de aplicaciones de tiempo real estricto que se ejecutaran en una arquitectura multiprocesador distribuida realizando especial énfasis en el coste energético de la aplicación. El conjunto de tareas que se estudiarán utilizan recursos compartidos y poseen dependencias temporales entre tareas ubicadas en el mismo o distinto procesador. Para conseguir este objetivo, se han fijado distintas metas intermedias, empezando con un conjunto de tareas sencillo y añadiéndole complejidad con cada meta cumplida.  La primera meta es la planificación de tareas que permita obtener el máximo ahorro energético posible en un procesador. Estas tareas serán de tiempo real estricto independientes, es decir, tareas que no usan recursos comunes, ni poseen dependencias temporales entre ellas. El capítulo 2 esta dedicado al desarrollo de esta meta.[56], [57],[59],[61]  La segunda meta que se ha fijado es la de añadir recursos compartidos entre las tareas de tiempo real. Con el fin de alcanzar esta meta, se ha modificado convenientemente el algoritmo de planificación obtenido anteriormente y se realiza un estudio de como afecta dicha modificación a nivel de consumo energético. Se observará que en este caso no es posible llegar a obtener el mismo ahorro energético que se obtenía anteriormente. Esta meta es la que se ha desarrollado en el tercer capítulo del presente documento. [58]  Y por último, la tercera y última meta será la de añadir dependencias temporales entre las tareas, de manera que una tarea no puede empezar su ejecución hasta que termina la ejecución de la tarea que la precede. En este caso, se tienen plazos temporales globales que van desde que se inicia la primera tarea de la cadena de precedencias hasta que finaliza la última. Para resolver este problema, se modificara el algoritmo de planificación obtenido en los puntos anteriores y se implementará un algoritmo de prioridades dinámicas basado en el EDF que puede adaptarse mejor a la carga del sistema Ahorro Energético en Sistemas de Tiempo Real - 41 de 209 - para comparar el rendimiento obtenido por el primer algoritmo respecto a la planificación dinámica con prioridades dinámicas. [60] Tal como se ha comentado, los capítulos restantes están ordenados en función de las distintas metas planteadas. En todos los capítulos se empieza definiendo el conjunto de tareas que se quiere planificar, se presentan las soluciones de planificación que se han propuesto en la literatura y se plantea nuestra propuesta. A continuación se presenta una posible implementación de esta propuesta, y se evalúa su rendimiento. Finalizando el capítulo con las conclusiones particulares de éste. Se ha añadido un capítulo en el que se realiza una reflexión sobre el dilema entre el ahorro energético y el tiempo de finalización a las tareas aperiódicas. En el último capítulo del documento, se extraen unas conclusiones generales del trabajo realizado y se comentan posibles líneas de investigación futuras. En los anexos, se incluye una posible implementación realizada de los algoritmos de otros autores que se han usado a nivel de comparativa con nuestros algoritmos. Capítulo 2 - 48 de 209 - 2.1.1 Low Power Fixed Priority Algorithm Scheduling El algoritmo Low Power Fixed Priority Algorithm Scheduling (LPFPS) [77] es un planificador de tiempo real con ahorro energético del conjunto de planificadores enlínea con asignación de prioridades estáticas y cálculo dinámico de la velocidad de procesador. Este planificador es eficiente desde el punto de vista de uso de procesador, de memoria, siendo además su implementación muy simple. La reducción energética se basa en aplicar las técnicas del DVS reduciendo la velocidad de ejecución del procesador siempre que haya una única tarea lista para ser ejecutada o bien detener el procesador cuando no hay tareas listas para su ejecución. Los detalles de una posible implementación se hayan en el Anexo 1. Los resultados obtenidos comparando el funcionamiento de LPFPS con el funcionamiento de “Fixed Priority Scheduling” FPS4, llevan a la conclusión de que la reducción energética que se obtiene con el LPFPS, no depende de la utilización del procesador, sino de la relación entre los periodos de las tareas y de la distribución de la carga del procesador entre las tareas, de manera que se obtiene una mayor reducción cuando el procesador esta ocupado por pocas tareas de periodos grandes en comparación con el WCET. Las ventajas que presenta el algoritmo LPFPS son: • Implementación sencilla y eficiente en el uso de procesador y de memoria. • Permite predecir la planificabilidad del conjunto de tareas de manera estática antes de iniciar la ejecución del sistema de tiempo real al igual que FPS, garantizando el cumplimiento de todos los plazos temporales de las tareas durante la ejecución del sistema. • Es un algoritmo estable frente a situaciones de sobrecarga del sistema, es decir, en el caso extremo que alguna tarea consuma más tiempo que el WCET calculado, se puede asegurar que en el caso que no se puedan ejecutar todas las tareas cumpliendo sus plazos temporales, la tarea o tareas que perderán el plazo serás las que tengan una menor prioridad, nunca perderá el plazo una tarea de prioridad mayor a la que ha provocado la sobrecarga del procesador. 4 Rate Monotonic es una de las asignaciones de prioridades más comunes para un FPS en el que las prioridades de las tareas vienen establecidas por su periodo. A menor periodo, mayor prioridad. Planificación con Ahorro Energético en Sistemas de Tiempo Real - 49 de 209 - • Aprovechamiento implícito del slack dinámico, si una tarea finaliza sin haber consumido todo su WCET permite que la siguiente tarea empiece antes, con lo que también acabará antes y dejará al final, un intervalo mayor en el que si existe una única tarea activa en el sistema, se podrá reducir la velocidad del procesador durante más tiempo. Si los periodos del conjunto de tareas son armónicos, solo habrá una tarea que se ejecutará a velocidad reducida (habrá instantes en los que todas las tareas se activarán a la vez), pero el algoritmo agrupará todo el espacio libre del procesador, con lo que en este caso se reducirá la corriente de fuga. Si los periodos no son armónicos, los intervalos en los que el procesador puede aprovechar para reducir velocidad serán pequeños y esparcidos por todo el hiperperiodo. No obstante, en este caso, habrá más tareas que se ejecuten reduciendo su velocidad de proceso. El inconveniente principal del algoritmo LPFPS es que: • El cálculo de velocidad del procesador se realiza suponiendo que la última tarea consumirá todo el WCET, sin embargo esta suposición no siempre será cierta. Y en ese caso, no existirá ninguna otra tarea que pueda ejecutarse a velocidad reducida, dejando así libre al procesador, hasta que se active una nueva tarea. Para intentar reducir el impacto de este inconveniente, aparecen algunos algoritmos de planificación que basados en heurísticas que intentan predecir el porcentaje de WCET que usará una tarea basándose en su ejecución histórica. A continuación se detallan unos ejemplo de este tipo de heurísticas. La primera heurística consiste en guardar la historia de las diversas activaciones de las tareas, es decir, supone que si una tarea anteriormente ha consumido el 50% de su WCET, es muy probable que la siguiente activación de esa tarea, también consuma el 50% de su WCET. P. Kumar y M. Srivastava en [40] implementan esta tipo de heurística sobre el algoritmo de LPFPS. En el citado articulo el cálculo de la velocidad del procesador está basada en la media del tiempo de ejecución de las activaciones precedentes, no en el WCET. Este hecho implica que si la tarea consume más tiempo, con este algoritmo se pueda perder el plazo temporal, puesto que se habrá calculado una velocidad menor de procesador de la que hubiera sido necesaria para ejecutarse dentro de sus límites. La sobrecarga necesaria para la Capítulo 2 - 50 de 209 - implementación del algoritmo, consiste únicamente en mantener en memoria una variable extra por tarea que contenga la media de ejecución de las diversas activaciones de esa tarea, y el cálculo de esta media cuando la instancia en curso de la tarea ha finalizado. El articulo concluye que aunque se consigue una considerable mejora en el ahorro energético, existen algunas tareas que pierden su plazo temporal, siendo pues inaceptable en sistemas de tiempo real estricto. Estos problemas podrían minimizarse utilizando técnicas de inteligencia artificial, aunque estas serian más costosas de implementar. En nuestro caso, esta heurística no nos interesa, puesto que estamos en un entorno de tiempo real estricto, pero si que podría resultar interesante su aplicación en un entorno multimedia o en un entorno donde sea suficiente asegurar el cumplimiento del plazo temporal de un cierto porcentaje de tareas, pudiéndose perder un porcentaje de plazos temporales cada cierto intervalo (firm real time). La segunda heurística, es la que aplica F. Gruian en [26] y se divide en dos fases, una estática y otra dinámica. En la fase estática, antes de empezar la ejecución del sistema se calcula en cuanto puede incrementarse el tiempo necesario para ejecutar el WCET de las tareas sin perder ningún plazo temporal (a que velocidad mínima pueden ejecutarse las tareas sin perder ningún plazo temporal) . Después, se divide el tiempo disponible para ejecutar cada tarea en intervalos, de manera que el primer intervalo se ejecutará a una velocidad menor, y se irá aumentando gradualmente la velocidad conforme la tarea vaya avanzando en su ejecución, así, en el caso más realista de que la tarea no consuma todo el WCET, la parte no ejecutada será la que el procesador debería haber ejecutado a mayor velocidad y por tanto la energía final consumida será menor. Dinámicamente, cuando el sistema ya está ejecutándose, se usará el slack dinámico que vayan produciendo las tareas que finalizan sin llegar a consumir la totalidad del WCET, para ejecutar tareas con una prioridad menor a la que ha generado el slack, con una reducción mayor de la velocidad del procesador que la indicada por el análisis estático. Con esta heurística, se obtiene una mayor reducción energética que usado el LPFPS sin comprometer ningún plazo temporal, pero la implementación del planificador requiere de tantos contadores como niveles de prioridad para poder contabilizar el slack generado en cada uno de los distintos niveles de prioridad. A si Planificación con Ahorro Energético en Sistemas de Tiempo Real - 51 de 209 - mismo, en el momento de ejecutar la tarea el planificador debe recorrer todos los contadores de prioridad superior que puedan aportar slack a la tarea activa. Este algoritmo también presenta el problema de que no permite una ampliación del conjunto de tareas de una manera fácil, por ejemplo añadir tareas aperiódicas al sistema. En este caso, en el momento de la llegada de la tarea aperiódica se debe rehacer el análisis de planificabilidad para calcular la nueva velocidad de ejecución que asegure la planificabilidad. 2.1.2 Dual Priority Scheduling Algorithm. El algoritmo de prioridad dual “Dual Priority Scheduling Algorithm”(DPS) (Prioridad Dual) propuesto originalmente por A. Burns y A.J. Wellings [13] para conseguir maximizar la planificación de tareas periódicas, y modificado posteriormente por R. Davis y A.J. Wellings [23] para mejorar el tiempo de finalización para las tareas aperiódicas. Este es el algoritmo que se usará como base para la implementación de nuestro planificador de ahorro energético que elige que tarea debe ejecutar. La idea del algoritmo de prioridad dual consiste, tal como ya se ha indicado anteriormente, en retardar las tareas periódicas sin llegar a comprometer los plazos temporales, dando al mismo tiempo un buen servicio a las tareas aperiódicas que lleguen al sistema. Para eso, las tareas periódicas poseen dos niveles distintos de prioridades, en el nivel de prioridad superior “Upper Run Queue” (URQ), únicamente podrán recibir interferencias de tareas periódicas de mayor prioridad, y en el nivel de prioridad inferior “Lower Run Queue” (LRQ) podrán recibir interferencias de las tareas aperiódicas y de las tareas periódicas de mayor prioridad. Las tareas aperiódicas se hayan en un nivel intermedio (MRQ), ordenadas mediante un algoritmo FIFO (First In First Out), es decir el primero en entrar es el primer en salir. Los detalles de una posible implementación se hayan en el Anexo 2. En resumen, el funcionamiento de este algoritmo de planificación permite que las tareas periódicas retrasen su ejecución el máximo tiempo posible (teniendo en consideración la máxima interferencia que pueden tener), siempre que exista alguna tarea aperiódica en el sistema. Capítulo 2 - 52 de 209 - La dificultad principal de este algoritmo radica en el cálculo del tiempo máximo de finalización (WCRT), calculado suponiendo la máxima interferencia de las tareas de mayor prioridad, por tanto será una cota superior. En el instante crítico, la tarea tendrá esta interferencia máxima, pero normalmente, la interferencia será siempre menor. Si se mejorará esta cota, acercándola más a la interferencia real, los resultados que se obtendrían a nivel de tiempo de finalización para las tareas aperiódicas mejorarían. Este mejora la ha desarrollado G. Bernat en [10] aplicada, entre otras, a mejorar el tiempo de finalización de las tareas aperiódicas. 2.2 Metodología y desarrollo. En este punto se expondrá la idea básica de la implementación de nuestro algoritmo de ahorro energético. El algoritmo “Low Power Fixed Priority Scheduling” (LPFPS) propuesto por Y. Shin y K. Choi [77] tiene características similares de reducción de velocidad a las que deseamos. Este algoritmo, utiliza un esquema de planificación con prioridades fijas pero posee un factor limitante de la reducción energética, para garantizar el cumplimiento de los plazos temporales de todas las tareas sólo se puede reducir la velocidad del procesador cuando existe una única tarea en la cola de tareas listas para ser ejecutadas. El algoritmo “Dual Priority Scheduling” (DPS) propuesto R. Davis y A.J. Wellings [23], está pensado para ofrecer un tiempo de finalización corto para las tareas aperiódicas sin complicar el algoritmo de planificación en exceso. En el algoritmo, las tareas disponen de prioridad dual, y en su implementación se dispone de dos niveles de prioridades distintos. Combinando ambos algoritmos, y teniendo en cuenta que las tareas del nivel de prioridad menor no corren ningún riesgo de perdida de plazos temporales, se podrá reducir la velocidad del procesador siempre que exista una única tarea en el nivel superior de prioridades, pudiendo haber, varias tareas listas para su ejecución en el nivel inferior. Para nuestro algoritmo, se usara la parte del algoritmo LPFPS que realiza el cálculo de la velocidad del procesador, y la parte de elección de tareas que utiliza el algoritmo DPS que permite retardar al máximo las tareas periódicas siempre que sea posible finalizando su ejecución lo más tarde posible sin complicar el algoritmo de planificación de las tareas. Por lo tanto el “Power Low Modified Dual Priority Scheduling” (PLMDP) consiste en ralentizar la ejecución de las tareas para permitir Planificación con Ahorro Energético en Sistemas de Tiempo Real - 53 de 209 - obtener ahorro energético aplicando las técnicas del DVS en un entorno en el que las tareas disponen de prioridad dual. En el apartado 2.2.1 se desarrolla y analiza en detalle la modificación que se propone del algoritmo DPS propuesto R. Davis y A.J. Wellings [23] para poder obtener ahorro energético, se utilizará el posible retardo en la ejecución de las tareas periódicas para ejecutarlas a la mínima velocidad posible, prolongando su ejecución al máximo sin perder ningún plazo temporal. Esta ralentización de tareas se enmarca directamente en el proceso de DVS, permitiendo así, el ahorro energético. El intervalo de tiempo del que se dispone para ejecutar a velocidad reducida viene determinado por el tiempo de promoción de las tareas periódicas. O sea, siempre que no haya tareas en la URQ o en la MRQ se podrá reducir la velocidad del procesador. En caso de que tampoco existen tareas en la LRQ entonces se podrá “desconectar” el procesador. 2.2.1 Power Low Modified Dual Priority Scheduling. En esta sección se veran las modificaciones propuestas al algoritmo de prioridad dual para obtener ahorro energético aplicando las técnicas del DVS, siempre que sea posible sin comprometer los plazos temporales de las tareas del sistema. En el caso de que existan tareas aperiódicas se les intentará ofrecer una buena calidad de servicio. Para obtener ahorro energético usando el algoritmo DPS, es necesario que cuando el planificador halla seleccionado la tarea activa, calcule la velocidad de procesador a la que debe ejecutar la tarea para respetar todos los plazos temporales. Recordemos que el planificador DPS dispone de tres niveles de prioridades URQ, MRQ y LRQ, y que la tarea activa será la primera del nivel de mayor prioridad. Con el fin de restringir las expulsiones (aumentando la sobrecarga del sistema) de tareas que se producen debido a las promociones de estas a las colas de un nivel superior, y con la finalidad de ganar eficiencia con el algoritmo de planificación, la cola LRQ se ordenará por tiempo de promoción en lugar de por prioridades como estaba en el algoritmo original. El algoritmo “Power Low Modified Dual Priority Scheduling Algorithm” (PLMDP) es una combinación de los algoritmos de planificación explicados en los Capítulo 2 - 54 de 209 - subapartados anteriores: por una parte se usa los mismos criterios de planificación que el algoritmo del DPS [23] para escoger la tarea que se va a ejecutar, y por otra parte usa la fórmula del cálculo de la velocidad del procesador del LPFPS [77] para determinar la velocidad de proceso de la tarea activa. Se puede observar que con el algoritmo DPS en caso extremo que siempre haya tareas aperiódicas en la MRQ, las tareas periódicas se ejecutan siempre a partir de su tiempo de promoción, se retrasa, por tanto, la ejecución de las tareas periódicas hasta el momento de su promoción quedando garantizado el cumplimiento de todos los plazos. Este fenómeno es equivalente a reducir la velocidad de proceso de las tareas periódicas hasta la llegada de la promoción. A partir de la promoción de las tareas se aplicará el algoritmo LPFPS a la cola URQ, por lo que se podrá reducir la velocidad de proceso aunque existan varias tareas activas en la LRQ. Si existen tareas aperiódicas para ser ejecutadas, en la MRQ, se ejecutaran a máxima velocidad. Las estructuras de datos necesarias para implementar el PLMDP son las mismas que se necesitan para implementar el DPS, un esquema de las cuales se haya en la Figura 79 del Anexo 2. En la Figura 8 se muestra el pseudocódigo del algoritmo PLMDP. Este algoritmo, tiene en cuenta los siguientes casos: • Si existen tareas en la URQ, la tarea activa es la primera de la cola URQ (τi): • Si existen otras tareas en la cola URQ o en la MRQ se debe ejecutar τi a máxima velocidad. • Si es la única tarea de la cola URQ y no hay tareas en la MRQ entonces o Se puede ralentizar la ejecución de la tarea τi hasta la llegada de otra tarea τk vía promoción de la LRQ, hasta completar la ejecución de τi o hasta la llegada del plazo temporal de τi. o La velocidad de ejecución se calcula mediante la siguiente fórmula: Velocidad = trabajo / tiempo disponible (ec. 9) o Si se denota Tpk como el tiempo de promoción de cualquier tarea τk (τk≠τi) más próximo al instante actual (tc), Tdi el plazo temporal de τi, Ri el remanente de la ejecución de τi, entonces la formula de la velocidad quedaría: Planificación con Ahorro Energético en Sistemas de Tiempo Real - 55 de 209 - ( ) tcTdTp RtcTp Velocidad ik ik − − =),(min ,min (ec. 10) • Si existen tareas en la MRQ y no en la URQ se activa la primera de la cola MRQ (tarea aperiódica). o La tarea activa se ejecuta a máxima velocidad hasta que promocione una tarea τk desde la LRQ o hasta completar la ejecución de la tarea aperiódica. • Si existen tareas en la LRQ pero no en la URQ ni en la MRQ se activa la primera de la cola LRQ (τi): o Si el tiempo de promoción Tpk es inferior al tiempo de promoción de la tarea activa Tpi entonces el tiempo disponible para hacer parte del trabajo es el intervalo comprendido desde instante actual tc y el instante en que llega la tarea k (Tak), es decir Tak - tc. Esto es debido a que la LRQ está ordenada siguiendo los instantes de promoción. Por tanto, si llega al sistema una tarea con menor tiempo de promoción que la tarea activa, se producirá una expulsión. Y dado que no se sabe si se tendrá oportunidad de volver a reducir la velocidad de ejecución, la mejor alternativa consiste en que esta reducción sea lo más drástica posible, por lo tanto se ejecutará a la mínima velocidad que sea eficiente [52]. o Si por el contrario, el tiempo de promoción Tpk es superior al tiempo de promoción de la tarea activa Tpi, se puede ralentizar la ejecución de τi como si se tratase la última tarea en la URQ, por lo tanto el cálculo de la velocidad es: ( ) tcTdTp RTpTp Velocidad ik iik − − =),(min ,min (ec. 11) • Por último, si no existen tareas ni en la URQ, ni el la LRQ, “se desconectará” el procesador y se programará un temporizador para activar al procesador cuando se active una nueva instancia de alguna tarea. Capítulo 2 - 56 de 209 - L1 si no vacia(URQ) entonces L2 Tarea activa = URQ.head; L3 si URQ.head.next = NIL y empty(MRQ) entonces L4 ( ) tcTdTp RtcTp Velocidad ik ik − − =),(min ,min ; L5 sino L6 Velocidad = Maxima velocidad; L7 finsi L8 sino L9 si no vacio(MRQ) entonces L10 Tarea activa = MRQ.head; Velocidad = Maxima velocidad L11 sino L12 si no vacia(LRQ) entonces L13 Tarea activa = LRQ.head; L14 si Tpk < Tpi entonces L15 Velocidad = Mínima velocidad; L16 sino L17 ( ) tcTdTp RTpTp Velocidad ik iik − − =),(min ,min ; L18 finsi L19 sino L20 progr. temporizador a (next Tai - wake up delay); L21 Ponerse en modo power-down; L22 finsi L23 finsi L24 finsi L25 ejecutar la tarea activa a la velocidad calculada; Figura 8: Pseudocódigo del algoritmo de planificación Power Low Modified Dual-Priority (PLMDP). 2.2.2 Ejemplo de funcionamiento del PLMDP. A continuación se muestra un ejemplo de comportamiento del PLMDP usando el conjunto de tareas que se detalla en la Tabla 1. En el ejemplo, se describe como será el comportamiento de las tareas a nivel de planificación y a nivel energético (ver Figura 9) suponiendo que las tareas consumen el 100% de su WCET, aunque en la ejecución normal únicamente consumirán un porcentaje de este tiempo. En este primer ejemplo, para simplificar el comportamiento del algoritmo se supone que no llega ninguna tarea aperiódica al sistema. Planificación con Ahorro Energético en Sistemas de Tiempo Real - 57 de 209 - Task T D WCET WCRT D-WCRT P t1 50 50 10 10 40 1 t2 80 80 20 30 50 2 t3 100 100 40 80 20 3 Tabla 1: “Benchmark” propuesto por Y. Shin y K. Choi [77] para la evaluación del ahorro energético. La notación correspondiente es: T = periodo, D = plazo temporal, WCET = peor tiempo de cálculo, WCRT = peor tiempo de finalización, P = prioridad, a menor número mayor prioridad. τ 1 τ 2 τ 3 activación tarea Promoción 380 390340 350 360 370300 310 320 330260 270 280 290220 230 240 250 400200 210 velocidad 1 0.5 0 200 160 170 180 190 120 130 140 150 80 90 100 110 40 50 60 70 20 30 0 10 velocidad 1 0.5 0 Figura 9: Diagrama de planificación de procesos usando el algoritmo PLMDP cuando las tareas consumen el 100% del WCET. En la Figura 9 se representa el resultado de la planificación PLMDP suponiendo que todas las tareas consumen el 100% de su peor tiempo de cálculo y que no existen tareas aperiódicas. Esta situación permite explicar claramente el funcionamiento básico del algoritmo. En el instante tc=0, se activan las tres tareas τ1, τ2 y τ3 que se encolaran en la LRQ (cola de tareas listas para ejecutar de menor prioridad) ordenadas según su tiempo de promoción. En este caso τ3 es la que está en primer lugar, le sigue τ1 y finalmente τ2. En tc=0 empieza la ejecución de la tarea τ3. En este instante no hay tareas en la URQ (cola de tareas listas para la ejecución de mayor prioridad) por lo tanto se puede reducir la velocidad del procesador. Se aplica la fórmula (9), la primera promoción es la de τ3 que se producirá en t=20 pero esta es la promoción de la tarea activa Tpi=Tp3=20, por tanto se debe mirar cuando se producirá el siguiente instante de promoción que será el de τ1 en t=40, por tanto, Tpk=Tp1=40, el tiempo actual (tc) es igual a 0, y el remanente (R3)=40, el mínimo entre Tpk-Tpi y Ri será de 20 unidades temporales. Se ejecutan 20 unidades de la tarea τ3. En el denominador de la ecuación hay Tpk=40 y Tdi=100, por tanto el mínimo es 40. Si se resta tc=0 son 40, por lo que la tarea puede ejecutarse durante un tiempo de 40 unidades sin recibir interferencias Capítulo 2 - 64 de 209 - Si la tarea reduce la velocidad de ejecución al máximo, obliga a las tareas restantes a ejecutarse a máxima velocidad, resultando con ello un mayor gasto energético. Imaginemos, ahora, el caso límite en el que se tiene un conjunto de tareas formado por una única tarea con una utilización total del 60 %, WCET=60, T=D=100, esto implica que se dispone de un 40% de tiempo libre. Este tiempo libre, que queda después de ejecutar la tarea puede usarse para reducir la velocidad del procesador ahorrando de esta manera energía. Si se calcula la velocidad óptima de ejecución de esta tarea será de 60/100, es decir, si la tarea se ejecutase al 60% de la velocidad máxima se ocuparía todo el tiempo libre disponible, y la energía consumida por el sistema sería mínima y aplicando la formula E = tv3 seria 100*0.216=21.6 en lugar de 60*1=60 que se tendría ejecutando a máxima velocidad, v=1. Si se ejecutara a menor velocidad, supongamos al 0,5 la energía necesaria sería 120*0.125=15, se consumiría menor energía, pero la tarea finalizaría en t=120, siendo su plazo temporal de 100, por tanto se perdería el plazo temporal. Se podría ejecutar a mayor velocidad, por ejemplo a 0,7 en este caso la tarea finalizaría en t=86, cumpliendo el plazo, pero ahora la energía consumida sería de 29.5, por tanto mayor que la energía ejecutando a 0.6. Imaginemos que se ejecuta la mitad de la tarea a 0.75% de velocidad usando 40 unidades de tiempo para realizar 30 de cálculo y el resto 30 unidades de cálculo en 60 unidades de tiempo resultando una velocidad de 0.5, i se finalizará, por tanto, en t=100 cumpliendo el plazo temporal, y se habrán consumido 0.422*40+0.125*60=24.38 unidades de energía, siendo este caso superior a la energía consumida a velocidad constante del 60%. Recapitulando, se puede observar que, ejecutando a velocidades inferiores al 60%, se necesita más tiempo para ejecutar las mismas unidades de tiempo, por tanto, al final de la ejecución de la tarea si se quiere cumplir el plazo temporal, se necesita ejecutar a mayor velocidad, siendo el 100% la velocidad máxima posible. Ejecutando a velocidades superiores se finaliza con antelación al plazo temporal, pero se consume mayor energía. Esto implica que la velocidad mínima en este caso es el 60% que concuerda con la utilización que realiza la tarea del procesador. Utilizando un planificador basado en EDF donde un conjunto de tareas es planificable si y solo si la utilización del procesador es menor o igual a 1. H. Aydin, R. Melhem, D. Mosse y P. Mejia-Alvarez proponen en [7] una reducción de la Planificación con Ahorro Energético en Sistemas de Tiempo Real - 65 de 209 - velocidad en función de la utilización del procesador, de manera que la utilización final del procesador sea igual a 1. Generalizando este caso a cualquier conjunto de tareas, se puede observar que la utilización del procesador condicionará la velocidad de ejecución mínima del conjunto de tareas. Sin embargo, con asignación estática de prioridades, se debe recordar que no es suficiente con tener una utilización del procesador menor que el 100% para garantizar la planificabilidad del sistema. Un parámetro que indica mejor el grado de planificabilidad de un conjunto de tareas es el “Breakdown utilization” (BU)[37], que se calcula de la siguiente forma: Cada WCETi del conjunto de tareas es multiplicado por un factor de escala, mientras que los periodos y plazos temporales no se modifican. Todo el conjunto se escala hasta el instante en que si hubiera un incremento adicional se perdería algún plazo temporal. El Breakdown utilization es la utilización del procesador en este punto. BU= Σ i (( α WCETi)/Ti) (ec. 12) donde α es el factor de escala y el sumatorio es para todas las tareas del sistema. Se puede observar, que el factor d’escala es equivalente a la reducción de velocidad por este factor a todas las tareas del conjunto, por tanto, ejecutando todas las tareas con una reducción de α el conjunto es planificable y la energía utilizada es la mínima (Sin tener en consideración el slack dinámico generado por las tareas). Para comprobar este punto se ha utilizado un algoritmo FPS (Fixed Priority Scheduling) con asignación de prioridades estáticas según “Rate Monotonic” (a menor periodo, mayor prioridad) en el que se ha ido reduciendo gradualmente la velocidad del procesador hasta que alguna tarea del conjunto de tareas pierda algún plazo temporal, representando en la gráfica la velocidad inmediatamente superior. En el experimento se han variado los siguientes parámetros de caracterización del conjunto de tareas: armonicidad de los periodos de las tareas, utilización máxima individual de una tarea del conjunto (Umax), utilización total del procesador (U) y por último el “breakdown utilization” (BU) [37] que es la medida que indica el grado de planificabilidad de un conjunto de tareas. Los resultados se hallan en la Figura 13 y en la Figura 14. Cada punto en las gráficas es la media aritmética del consumo energético normalizado de 100 conjuntos de tareas aleatorios. La recta se corresponde a los resultados exactos que se obtienen de dividir la utilización total del Capítulo 2 - 66 de 209 - procesador entre el BU (U/BU). En sistemas con un gran número de tareas con periodos no armónicos es muy difícil encontrar conjuntos de tareas con un BU del 100%, por lo que en la Figura 14 el simulador no fue capaz de hallar un número razonable de conjuntos que permitan realizar una media aritmética estadísticamente significativa. 0,6 0,65 0,7 0,75 0,8 0,85 0,9 0,95 1 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 Breakdown utilization velocidad mínima 60% 65% 70% 75% 80% 85% 90% 95% Figura 13: Velocidad mínima necesaria para planificar un conjunto de tareas cuando se varia la utilización del procesador y el breakdown utilization de los conjuntos de tareas. El Umax está fijado al 20%, los periodos son armónicos, y el conjunto de tareas está compuesto por 8 tareas independientes. En la Figura 13, se puede observar que la reducción de velocidad factible es la resultante de aplicar la formula U/BU (líneas azules), si la reducción es menor que la máxima reducción posible, la energía consumida será mayor, mientras que si la reducción de velocidad es mayor, se consumiría menor energía, pero se podría perder el plazo temporal de alguna de las tareas del conjunto. En las Figura 13 y Figura 14 se observa que la variación del número de tareas del conjunto no afecta significativamente al comportamiento de la reducción energética, aunque si afecta al hecho de encontrar conjuntos planificables con un BU determinado. Si los periodos no son armónicos, cuantas más tareas tenga el conjunto, menor será el BU obtenido. Planificación con Ahorro Energético en Sistemas de Tiempo Real - 67 de 209 - 0,6 0,65 0,7 0,75 0,8 0,85 0,9 0,95 1 100 99 98 97 96 95 94 93 92 91 90 89 88 87 86 Breakdown utilization velocidad mínima 60% 65% 70% 75% 80% 85% 90% 95% Figura 14: Velocidad mínima necesaria para planificar un conjunto de tareas cuando se varia la utilización del procesador y el breakdown utilization de los conjuntos de tareas. El Umax está fijado al 20%, los periodos no son armónicos, y el conjunto de tareas está compuesto por 16 tareas. A pesar de los resultados mostrados, se debe tener en cuenta que este algoritmo no es apropiado para sistemas de tiempo real, puesto que esta reducción energética obtenida a base de reducir la velocidad de ejecución por igual a todas las tareas del conjunto no permite sacar provecho del hecho que las tareas finalicen sin llegar a consumir todo el WCET. De igual manera, este planificador no podrá tratar tareas aperiódicas puesto que como tareas menos prioritarias no se ejecutarían nunca, ya que la reducción de velocidad propuesta provoca que el procesador este ocupado durante todo el hiperperiodo planificable. Recordemos, que el FPS al tener prioridades estáticas no garantiza la planificabilidad al 100% de utilización del procesador. 2.2.4 Enhanced Power Low Dual Priority Scheduling En este punto se propone una mejora al planificador PLMDP aplicando los resultados obtenidos en el apartado anterior. De manera que no haya una tarea que reduzca en exceso su velocidad de ejecución provocando que el resto de tareas deban ejecutarse a máxima velocidad. Inicialmente, se calculará el BU y la U del conjunto de tareas. Estos dos datos son estáticos (no se modifican durante la ejecución del sistema) y por lo tanto, pueden calcularse con anterioridad a la ejecución del conjunto de tareas. Cuando el sistema está en funcionamiento, la utilización real del Capítulo 2 - 68 de 209 - sistema, va variando en función del comportamiento de las tareas que se ejecutan. Inicialmente se debe suponer que las tareas consumirán el 100% de su WCET, y por tanto la mínima velocidad a la que se ejecutaran las tareas será la utilización calculada inicialmente del conjunto de tareas, dividido por su BU (U/BU). A medida que las tareas se vayan ejecutando, se pueden producir varios casos: • La tarea se ha ejecutado a mayor velocidad que la calculada según la fórmula U/BU, con el fin de cumplir los plazos temporales. • La tarea ha finalizado sin llegar a consumir todo su WCET. • La tarea se ha ejecutado a menor velocidad que la calculada por U/BU con el fin de minimizar el tiempo libre de procesador. En los dos primeros casos, la tarea finalizará sin llegar a utilizar todo el tiempo que tenia disponible para su ejecución, por tanto velocidad de ejecución calculada para el resto de las tareas será menor que la que seria si se hubiera ocupado todo el tiempo disponible, es decir, la ejecución de la tarea recién finalizada ha proporcionado tiempo extra para la ejecución del resto de tareas. En el tercer caso, la tarea se ha ejecutado a menor velocidad que la previamente calculada, por tanto la tarea ha utilizado un tiempo mayor que el previsto inicialmente, sin embargo de no haberse utilizado, este tiempo se habría perdido debido a la ausencia de tareas listas para su ejecución. Esto implica que puede darse el caso que las siguientes tareas que se ejecutaran deberán hacerlo a una velocidad mayor. Resumiendo, la mejora que se propone, con el algoritmo EPLDP, consiste en conseguir que el algoritmo de planificación reparta el tiempo disponible para reducir la velocidad del ejecución de las tareas entre las máximas tareas posibles, es decir, se intentará que las tareas no deban ejecutarse a nunca a velocidad máxima. Antes de empezar la ejecución del sistema, de manera estática se calcularán: • BU, que depende únicamente de las características físicas de las tareas (periodo y WCET). • Up (La utilización pendiente de ser ejecutada) suponiendo que las tareas se ejecutarán a máxima velocidad y consumirán todo el WCET. Los cambios que se deben realizar en el tratamiento de los eventos son los siguientes: Planificación con Ahorro Energético en Sistemas de Tiempo Real - 69 de 209 - • Al inicio de un hiperperiodo, inicializar la variable Wrem con el trabajo que se deberá ejecutar en ese hiperperiodo. • Cuando se produce una expulsión de la tarea (se activa una tarea de mayor prioridad) la variable Wrem debe reducirse según el trabajo recién realizado • Cuando se produce la finalización la variable Wrem debe reducirse según el trabajo recién realizado más el tiempo que le ha sobrado. • El planificador calcula la velocidad de ejecución de la tarea de manera individual antes de iniciar su ejecución, siendo esta igual al valor máximo entre la velocidad calculada por el PLMDP y el cociente entre la utilización remanente (Urem) y el BU. La Urem se calcula de la siguiente forma: tcdohiperperio W Urem rem − = (ec. 13) En la Figura 15 se presenta el pseudo-código del algoritmo EPLDP. Nótese, que la energía obtenida será la mínima posible cuanto más cerca se este de conseguir la velocidad media deseada, mientras que el algoritmo se alejará de esta optimalidad cuando más se alejen las tareas de la media deseada. El hecho de que las tareas no consuman todo el WCET propuesto, también provocará que la energía consumida se aleje del mínimo posible, debido a que el cálculo de la utilización pendiente (Up) se alejará de la real. Pero, el planificador en ningún caso puede suponer una ejecución de las tareas por debajo del WCET, ya que de otro modo podría comprometer los plazos. Capítulo 2 - 70 de 209 - L1 si no vacia(URQ) entonces L2 Active Task = URQ.head; L3 si URQ.head.next = NIL y empty(ARQ) entonces L4 ( )         − − =BU U , tc)Td,Tp(min remaining,tcTpmin maxvelocidad rem ik ik L5 sino L6 velocidad = MAX_FREQ; L7 finsi L8 sino L9 si no vacia(ARQ) entonces L10 Active task = ARQ.head; velocidad = MAX_FREQ; L11 sino L12 si no empty(LRQ) entonces L13 Active task = LRQ.head; L14 si Tpk < Tpi entonces L15       =BU U velocidad rem L16 sino L17 ( )         − − =BU U , tc)Td,Tp(min remaining,TpTpmin maxvelocidad rem ik iik L18 finsi L19 sino L20 progr. temporizador a (next Tai - wake up delay); L21 Ponerse en modo power-down; L22 finsi L23 finsi L24 finsi L25 Ejecutar la tarea activa a la velocidad calculada; Figura 15: Pseudocódigo del Enhanced Power Low Dual-Priority (EPLDP) Scheduling. A continuación se establecerá en que casos funciona mejor el PLMDP que el EPLDP. El algoritmo EPLDP funciona siempre bien cuando se consume el 100% del WCET debido a que en este caso la velocidad estimada es la exacta. Pero conforme el consumo real del WCET se aleja del 100% la velocidad calculada también difiere más, llegando a la máxima divergencia cuando el consumo real del WCET es mínimo. En cambio, el algoritmo PLMDP, reduce siempre que puede al máximo su velocidad, de esta manera se adapta perfectamente al hecho que el porcentaje de WCET usado sea mínimo. Planificación con Ahorro Energético en Sistemas de Tiempo Real - 71 de 209 - Las gráficas (Figura 16 a Figura 18) muestran el porcentaje de WCET mínimo que deben consumir las tareas para que el planificador EPLDP mejore el ahorro energético obtenido por el planificador PLMDP. Se han realizado distintos experimentos variando: • Número de tareas: de 8 y 16 tareas. • Armonicidad de los periodos: armónicas y no armónicas • Utilización máxima de las tareas del conjunto (Umax): entre 10 y 40% • Utilizaciones máximas del procesador(U): entre el 60% y el 95%. En las gráficas se ha representado la media de 100 conjuntos para cada porcentaje de utilización del procesador representando en el eje de las X, y el % de WCET consumido en el que cambia el planificador mejor en el eje de las Y. 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 60% 65% 70% 75% 80% 85% 90% 95% %Utilización del procesador %WCET consumido 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 60% 65% 70% 75% 80% 85% 90% 95% %Utilización del procesador %WCET consumido Figura 16: Representación de la curva de transición entre el algoritmo EPLDP y el PLMDP en conjuntos de 8 tareas con una carga máxima de las tareas del 20%. En a) las tareas tienen los periodos armónicos y en b) son no armónicos. 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 60% 65% 70% 75% 80% 85% 90% 95% %Utilización del procesador %WCET consumido 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 60% 65% 70% 75% 80% 85% 90% 95% %Utilización del procesador %WCET consumido Figura 17: Representación de la curva de transición entre el algoritmo EPLDP y el PLMDP en conjuntos de 8 tareas con una carga máxima de las tareas del 40%. En a) las tareas tienen los periodos armónicos y en b) son no armónicos. b) a) EPLDP EPLDP PLMDP PLMDP b) a) EPLDP EPLDP PLMDP PLMDP Capítulo 2 - 72 de 209 - 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 60% 65% 70% 75% 80% 85% 90% 95% %Utilización del procesador %WCET consumido 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% 60% 65% 70% 75% 80% 85% 90% 95% %Utilización del procesador %WCET consumido Figura 18: Representación de la curva de transición entre el algoritmo EPLDP y el PLMDP en conjuntos de 16 tareas con una carga máxima de las tareas del 20%. En a) las tareas tienen los periodos armónicos y en b) son no armónicos. De todos los experimentos realizados se han escogido las anteriores por ser los más representativos. Si se comparan las gráficas con periodos armónicos se observa: que el planificador EPLDP tiene un mayor ahorro energético que el PLMDP con consumos menores de porcentajes de WCET, esto es debido principalmente a que con los periodos armónicos es más probable que coincidan diversas tareas en las distintas colas que con periodos no armónicos, y en este caso el PLMDP asigna el tiempo libre a una única tarea, ejecutando esa tarea a una velocidad muy reducida, pero la mayoría de tareas se ejecutan a velocidad máxima, mientras que el EPLDP reparte la velocidad de las tareas de manera más equitativa. En el caso de tareas no armónicas, el planificador PLMDP puede distribuir mejor, que con tareas armónicas, la reducción entre las distintas tareas dado que la activación de las tareas ocurre en distintos instantes, y así conseguir mejor ahorro energético con porcentajes consumidos de WCET mayores. Si se considera ahora la carga máxima teórica del procesador, se observa un comportamiento creciente, lo que implica que con cargas de utilización alta, el algoritmo PLMDP se adapta mejor a los distintos porcentajes de WCET que con utilizaciones menores de procesador. Si se dispone de mayor número de tareas para igual carga de procesador, se observa que la transición entre PLMDP y EPLDP de porcentaje de WCET consumido es menor que con menos tareas. Esto es debido a que dado que el rango de periodos es el mismo, la mayoría de tareas tendrán una carga menor, por tanto se adapta mejor el EPLDP ya que al existir mayor numero de tareas, la probabilidad de coincidencia en una cola es mayor. a) b) EPLDP EPLDP PLMDP PLMDP Planificación con Ahorro Energético en Sistemas de Tiempo Real - 73 de 209 - Resumiendo, si las tareas de la aplicación tienen el cálculo del WCET bien estimado, asegurando que un consumo medio del WCET superior al 50% en utilizaciones del procesador por debajo del 85% con periodos no armónicos y por debajo del 95% en el caso de periodos armónicos, se puede asegurar que el ahorro energético conseguido con el EPLDP será siempre mejor que el que se consigue con el PLMDP. 2.2.5 Ejemplo de funcionamiento algoritmo EPLDP. Al igual que para el algoritmo anterior, a continuación se muestra un ejemplo del comportamiento del planificador EPLDP (Enhanced Power Low Dual Priority) ejecutando el conjunto de tareas que se detalla en la Tabla 1. En la Figura 19 se muestra el comportamiento de las tareas a nivel de planificación y a nivel energético suponiendo que las tareas consumen siempre el 100% de su WCET. Y en la Figura 20 se muestra el comportamiento suponiendo que las tareas consumen únicamente el 50% de su WCET. Al igual que para los planificadores anteriores, para simplificar la problemática, se supone que no llegan tareas aperiódicas al sistema. Esta situación permite explicar claramente el funcionamiento básico del algoritmo. Como característica principal en la Figura 19, se puede observar que no existe tiempo de procesador libre, y que hay menores intervalos de ejecución de las tareas a máxima velocidad que con el algoritmo PLMDP. Otra característica que se puede observar es que la velocidad de ejecución de las tareas es más uniforme, es decir, no existen variaciones muy grandes en la velocidad de ejecución del procesador. τ 1 τ 2 τ 3 activación tarea Promoción 380 390 400340 350 360 370300 310 320 330260 270 280 290 200 velocidad 1 0.5 200 210 220 230 240 250 160 170 180 190 120 130 140 150 80 90 100 110 40 50 60 70 0 10 20 30 0 velocidad 1 0.5 0 Figura 19: Diagrama de planificación de procesos usando el algoritmo EPLDP cuando se consume el 100% del WCET. Capítulo 2 - 80 de 209 - Tarea T D WCET T1 100 100 5,1 T2 20000 20000 300 T3 2500 2500 200 T4 2500 2500 500 T5 4000 4000 100 T6 5000 5000 300 T7 5000 5000 500 T8 5900 5900 800 T9 8000 8000 900 T10 8000 8000 200 T11 10000 10000 500 T12 20000 20000 300 T13 20000 200000 100 T14 20000 20000 100 T15 20000 20000 300 T16 100000 100000 100 T17 100000 100000 100 Tabla 3:Conjunto de tareas de aviónica [50] En la Figura 26 se muestra el consumo energético normalizado de los diferentes algoritmos. Observemos que, debido a que el sistema tiene una utilización muy alta, la posibilidad de reducir la velocidad del procesador es pequeña, con lo que apenas hay ahorro energético cuando el consumo de las tareas es el 100% del WCET. Conforme el porcentaje de WCET consumido disminuye, podría mejorar el ahorro, sin embargo, dado que los algoritmos de planificación LPFPS y LPEDF se basan en reducir la velocidad de la última tarea activa y ésta representa un porcentaje muy pequeño en la utilización total, el ahorro que se obtiene es muy pequeño. En el caso del LPEDF, lo que no consume una tarea lo aporta directamente a la reducción de velocidad y por tanto energética de la siguiente, con lo que independientemente de la utilización individual de cada tarea se consiguen resultados de ahorro energético muy buenos. Con el planificador PLMDP, ocurre algo similar a los dos primeros, solo se reducirá la velocidad del procesador cuando en la cola de mayor prioridad haya un sola tarea, si dos tareas tienen el mismo comportamiento de promociones y además la tarea de mayor periodo / plazo temporal es la que aporta la mínima utilización individual. Planificación con Ahorro Energético en Sistemas de Tiempo Real - 81 de 209 - 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% % WCET consumido consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m Figura 26: Consumo energético normalizado para el conjunto de tareas de aviónica [50] según el porcentaje de WCET consumido por las tareas. En el ejemplo de aviónica, el promedio de consumo energético normalizado según el consumo con una ejecución de las tareas a máxima velocidad para cada uno de los algoritmos de planificación es: del 97% para el LPFPS, del 64% para el LPEDF, del 77% para el PLMDP y por último del 79% para el EPLDP, siendo 35% para el EPLDP-m. Caso de navegación Las características del conjunto de tareas para el caso de navegación se muestran a continuación en la Tabla 4. En este el conjunto de tareas tiene definidas 6 tareas con una utilización del procesador del 74 %. La variación entre el periodo mínimo y el máximo es de 2000, y la carga individual máxima de las tareas es de 47%, y la carga individual mínima es de 16%. La característica principal de este conjunto es que hay dos tareas (T4,T5) con el mismo periodo, y utilización individual muy pequeña. Otra característica importante es que la tarea que fija la carga máxima individual del conjunto de tareas es la que posee un periodo y un plazo temporal menor. Tarea T D WCET T1 250 250 118 T2 4000 4000 428 T3 62500 62500 1028 T4 100000 100000 2028 T5 100000 100000 10028 T6 125000 125000 2500 Tabla 4: Conjunto de tareas de navegación (INS) [15] Capítulo 2 - 82 de 209 - 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% % WCET consumido consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m Figura 27: Consumo energético normalizado para el conjunto de tareas de navegación (INS) [15] según el porcentaje de WCET consumido por las tareas. En el ejemplo de navegación, el promedio de consumo energético normalizado según el consumo con una ejecución de las tareas a máxima velocidad para cada uno de los algoritmos de planificación es: del 63% para el LPFPS, del 54% para el LPEDF, del 56% para el PLMDP y por último del 41% para el EPLDP, siendo 27% para el EPLDP-m. Caso de control automático (CNC). Las características del conjunto de tareas para el caso de control automático [38] se muestran a continuación en la Tabla 5. En este el conjunto de tareas tiene definidas 8 tareas con una utilización del procesador muy baja, del 48 %. La variación entre el periodo mínimo y el máximo es de 0.25, y la carga individual máxima de las tareas es de 15%, y la carga individual mínima es de 1,5%. La característica principal de este conjunto es que hay una tarea con el mínimo periodo y el plazo temporal mayor, siendo esta la tarea que aporta la utilización individual mínima. Tarea T D WCET T1 2400 2400 35 T2 2400 24000 40 T3 4800 4800 180 T4 4800 4800 720 T5 2400 2400 165 T6 2400 2400 165 T7 9600 9600 570 T8 7800 7800 570 Tabla 5: Conjunto de tareas de control automático (CNC) [38] Planificación con Ahorro Energético en Sistemas de Tiempo Real - 83 de 209 - En la Figura 28 se ve que en este caso, los planificadores LPFPS y el LPEDF aportan un bajo rendimiento debido a la tarea τ2 que está la mayor parte del tiempo activa, no permitiendo la reducción de velocidad a las demás tareas. En el caso del PLMDP, esta tarea no molesta tanto debido a que se halla en la cola de menor prioridad, y cuando promociona finaliza rápidamente debido a que su carga individual es la mínima posible. En el caso del planificador LPEDF se obtiene ahorro energético debido a que al tener una utilización baja, se consigue la reducción de la velocidad de ejecución de las tareas. 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 1,1 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% % WCET consumido consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 1,1 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% % WCET consumido consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m Figura 28: En a) Consumo energético normalizado para el conjunto de tareas de control automático [38] según el porcentaje de WCET consumido por las tareas. En b) todas las tareas tienen el plazo igual al periodo. a) b) Capítulo 2 - 84 de 209 - En este caso el LPFPS tiene un promedio de consumo del 91% si los periodos son distintos a los plazos y del 66% en caso de igualdad. Para el resto de planificadores no existe una diferenciación de promedios importante, siendo de 43% y 45% para el planificador LPEDF, de 30% y 31% para el PLMDP, de 22% en los dos casos para el EPLDP y finalmente de 9% y 10% para el EPLDP-m. Comentarios generales de los casos analizados anteriormente. Los resultados del consumo energético normalizado para cada una de las aplicaciones está mostrado desde la Figura 25 a la Figura 28. El resumen de las principales características de las aplicaciones se hayan en la Tabla 6, y la media normalizada consumida por los distintos planificadores se halla en la Tabla 7. armonicidad N tareas U Umax Umin Tmin/Tmax Ejemplo poco 3 85% 40% 20% 0.5 Aviónica Tareas con T iguales 17 90% 20% 10% 0.001 INS Tareas con T múltiples 6 74% 47% 16% 0.002 CNC totalmente 8 48% 15% 1,5% 0.25 Tabla 6: Características principales de las aplicaciones individuales. Ejemplo Tabla 1 Aviónica INS CNC CNC con D=T LPFPS 0,85 0,97 0,63 0,91 0,66 LPEDF 0,65 0,64 0,54 0,43 0,45 PLMDP 0,45 0,77 0,56 0,30 0,31 EPLDP 0,53 0,79 0,41 0,22 0,22 EPLDP-m 0,41 0,35 0,27 0,09 0,10 Tabla 7: Resumen de la media de los conjuntos de pruebas individuales normalizado de las tareas consumiendo entre el 10% y el 100% del WCET con los distintos algoritmos estudiados. • LPFPS: es el planificador con un rendimiento energético más desfavorable. Siendo este rendimiento peor en el caso de conjuntos de tareas con periodos armónicos debido a que hay varias tareas que se activan simultáneamente, y solo se podrá disminuir la velocidad de ejecución de la última tarea de la cola de ejecución. El planificador es muy sensible a la asignación de prioridades, de manera que si una tarea con poca prioridad se halla en el sistema, provoca Planificación con Ahorro Energético en Sistemas de Tiempo Real - 85 de 209 - que el resto de tareas no puedan disminuir la velocidad de ejecución, utilizando al final mayor porcentaje de energía. • LPEDF: obtiene mejor rendimiento cuanto más armónicos son los periodos de las tareas, debido a la existencia de un servidor de disminución de la velocidad cuya capacidad se recarga con el periodo de la tarea más frecuente. Si este periodo es muy pequeño puede ser que no se utilice totalmente el tiempo, mientras que si es muy grande, las tareas se ejecutan primero muy despacio, para ejecutarse después a máxima velocidad. • PLMDP: el rendimiento del algoritmo va en función del tamaño de las tareas, si estas son pequeñas se obtiene un mejor rendimiento que si las tareas son grandes. Además, si el procesador tiene una utilización baja, la disminución de la velocidad de proceso se realiza al principio del hiperperiodo, y esto permite que si la tarea finaliza sin consumir la totalidad del WCET este tiempo pueda ser aprovechado por las siguientes tareas. • EPLDP: Al estar basado en el algoritmo anterior, obtiene mejor rendimiento cuando el PLMDP lo obtiene, sin embargo, si el procesador tiene una utilización baja, la disminución de la velocidad de proceso puede ser más uniforme, quedando esta más repartida entre todas las distintas tareas mejorando así el resultado obtenido por el algoritmo. • EPLDP-m: Consigue mejores resultados que el anterior, debido a que se basa en la ejecución histórica para calcular la tasa de sobredimensionado del WCET. Provocando el reparto del tiempo no consumido entre todas las tareas del sistema, consiguiendo que estas no se ejecuten a máxima velocidad. Este algoritmo consigue aprovechar prácticamente la totalidad de tiempo libre del procesador. 2.3.2 Conjuntos de tareas sintéticos. Para los siguientes experimentos se han generado 100 conjuntos de tareas sintéticas para poder observar la influencia de las distintas caracterizaciones de las tareas en el ahorro energético según el algoritmo empleado. La generación y ejecución de las tareas se ha realizado como sigue: Capítulo 2 - 86 de 209 - • Durante la simulación de la ejecución se ha variado del 10% al 100% el porcentaje de WCET consumido por las tareas, en incrementos del 10%. • Se simula durante un hiperperiodo y los valores de energía obtenidos los normalizamos conjunto a conjunto, debido a que los hiperperiodos obtenidos por el conjunto de tareas pueden ser distintos (depende de los periodos de las tareas que forman parte del conjunto) y por tanto la energía consumida por los distintos conjuntos no seria comparable, aun usando el mismo planificador. En las gráficas se muestra la media aritmética normalizada del consumo de los cien conjuntos generados aleatoriamente con características similares. Variación del número de tareas y armonicidad de los periodos. Se han realizado experimentos variando la armonicidad de los periodos y el número de tareas del conjunto. Los periodos varían entre 1000 y 70000 unidades de tiempo, para los conjuntos de tareas con periodos no armónicos y entre 1024 y 65536 para los conjuntos de tareas con periodos armónicos. Las figuras siguientes muestran el consumo energético normalizado cuando la utilización del procesador es del 75%, la carga máxima individual de las tareas del 20% y se ha variado el número de tareas entre 8 y 16 tareas. Únicamente se han tenido en cuenta conjuntos planificables de tareas, es decir, los conjuntos que cumplen que ∀τi WCRTi ≤ Di. La Figura 29 para muestra conjuntos de tareas con periodos armónicos y la Figura 30 muestra conjuntos de tareas con periodos no armónicos. Planificación con Ahorro Energético en Sistemas de Tiempo Real - 87 de 209 - 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% % WCET consumido consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% % WCET consumido consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m Figura 29: 100 Conjuntos de 8 tareas con una carga máxima de las tareas del 20% y una utilización máxima del procesador del 75%. En a) los periodos de las tareas son armónicos y en b) los periodos son no armónicos. a) b) Capítulo 2 - 88 de 209 - 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% % WCET consumido consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% % WCET consumido consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m Figura 30: 100 Conjuntos de 16 tareas con una carga máxima de las tareas del 20% y una utilización máxima del procesador del 75%. En a) los periodos de las tareas son armónicos y en b) los periodos son no armónicos. En las cuatro figuras anteriores se puede observar que el algoritmo EPLDP-m es el que funciona mejor. La variación en el número de tareas no presenta diferencias estadísticamente significativas. (Tabla 8) a) b) Planificación con Ahorro Energético en Sistemas de Tiempo Real - 89 de 209 - LPFPS LPEDF PLMDP EPLDP EPLDP-m Conjunto armónico 8 tareas 87% 51% 61% 39% 28% Conjunto no armónico 8 tareas 85% 63% 62% 49% 25% Conjunto armónico 16 tareas 90% 50% 62% 38% 27% Conjunto no armónico 16 tareas 87% 61% 61% 53% 23% Tabla 8: Consumo medio normalizado de los planificadores de referencia según la armonicidad de los periodos y el número de tareas. La utilización del procesador máxima elegida es del 75%, y la carga máxima de las tareas del conjunto es del 20% De las figuras anteriores también se puede observar que el EPLDP y el LPFPS, son los planificadores que poseen un consumo energético normalizado más estable frente al consumo del WCET, es decir, el consumo energético obtenido no depende significativamente del porcentaje de WCET consumido. Este hecho es debido a que la velocidad de ejecución de las tareas que se asigna intenta ocupar todo el tiempo libre disponible con los datos disponibles inicialmente, pero si las tareas no consumen todo el WCET, este no puede ser aprovechado por ninguna tarea dejando libre el procesador. El planificador ejecuta las tareas a una velocidad superior a la necesaria, creando, con ello, espacios de procesador libres, y consumiendo mayor cantidad de energía que la que usan otros planificadores que se adaptan más fácilmente a los cambios de consumo del WCET. Si se utiliza una media móvil para calcular el sobredimensionado del WCET, conforme evoluciona el sistema se llega a disponer de un sobredimensionado muy aproximado al real, con lo que la velocidad de ejecución de las tareas es la más adecuada para ocupar todo el espacio de procesador disponible. El algoritmo EPLDP está preparado para que en caso de un consumo superior no haya perdidas de plazos, interviniendo el planificador DP de base. Pero, en caso de un consumo inferior, la media móvil va a continuar posicionándose en la velocidad necesaria. Variación de la carga del sistema entre el 60% y el 95%. La máxima utilización de las tareas del conjunto está fijada al 20%, los periodos varían entre 1000 y 70000 unidades de tiempo, para los conjuntos de tareas con periodos no armónicos y entre 1024 y 65536 para los conjuntos de tareas con Capítulo 2 - 96 de 209 - 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 1,0E-04 1,0E-03 1,0E-02 1,0E-01 1,0E+00 Tmin/Tmax consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 1,0E-05 1,0E-04 1,0E-03 1,0E-02 1,0E-01 1,0E+00 Tmin/Tmax consumo energético normalizado LPFPS LPEDF PLMDP EPLDP EPLDP-m Figura 39: Variación del ratio entre Tmin/Tmax fijando la utilización del procesador al 75% y WCET consumido al 90%. La utilización máxima de las tareas está fijada al 20%. En a) los periodos de las tareas son armónicos y en b) son no armónicos Con estas últimas figuras, se puede concluir que las diferencias de consumos energéticos entre los distintos algoritmos de planificación es mas evidente cuanto mayor es el ratio entre los periodos. %WCET consumido LPFPS LPEDF PLMDP EPLDP EPLDP-m 20% 80% 29% 33% 31% 6% 50% 83% 41% 53% 34% 20% 90% 90% 71% 79% 52% 51% Tabla 13: Consumos medios normalizados variando la utilización máxima teórica del procesador, en conjuntos de tareas con periodos armónicos a) b) Planificación con Ahorro Energético en Sistemas de Tiempo Real - 97 de 209 - %WCET consumido LPFPS LPEDF PLMDP EPLDP EPLDP-m 20% 0,78 0,57 0,36 0,40 0,04 50% 0,82 0,60 0,58 0,44 0,18 90% 0,88 0,74 0,81 0,53 0,50 Tabla 14: Consumos medios normalizados variando la utilización máxima teórica del procesador, en conjuntos de tareas con periodos no armónicos Con las medias entre los distintos planificadores, se puede observar que el planificador EPLDP-m es el que posee un mejor ahorro energético, seguido del EPLDP. Existe una gran diferencia a nivel de consumo energético para el planificador LPEDF según las tareas tengan un periodo armónico o no. Y las diferencias no son tan evidentes para el resto de los planificadores. 2.4 Conclusiones En este capítulo se han desarrollado algoritmos de planificación para sistemas de tiempo real estricto que aportan un ahorro energético superior a los algoritmos simples de prioridades estáticas o dinámicas. La implementación de los algoritmos de planificación aportan una mínima sobrecarga respecto a un algoritmo simple de prioridades estáticas. En el cálculo de la energía consumida no se ha tenido en cuenta las sobrecargas debidas al algoritmo de planificación, ni a la sobrecarga y tiempo que representa el cambio de la velocidad del procesador. Sin embargo, si que se ha tenido en cuenta que la velocidad del procesador no es lineal sino discreta, usando en este caso la velocidad mayor más próxima. Para el análisis del algoritmo se han realizado varios casos de pruebas, tanto reales como sintéticos, con el objetivo de poder hallar un patrón entre los parámetros de las tareas del ahorro energético que se obtiene. Se han comparado nuestros algoritmos EPLDP-m, EPLDP y PLMDP con el LPEDF y el LPFPS. Todos los consumos han sido normalizados respecto a la ejecución a máxima velocidad del procesador. En los conjuntos de tareas escogidos se ha ido variando: la utilización máxima del procesador, el número de tareas del sistema, la armonicidad en los periodos de las tareas, la utilización máxima de las tareas del conjunto, el rango entre el periodo Capítulo 2 - 98 de 209 - máximo y el mínimo. También se ha variado el porcentaje de WCET consumido entre el 10% y el 100% de consumo. Se ha comprobado que nuestros planificadores se comportan bien en cualquier situación, no siendo especialmente sensibles a la armonicidad de los periodos. El planificador EPLDP no se adapta con suficiente rapidez a bajos consumos de WCET, pero el planificador EPLDP-m soluciona este problema. El EPLDP-m calcula de manera dinámica el grado de consumo medio de las tareas, adecuándose al consumo real de las tareas y consiguiendo consumos energéticos mínimos en cualquier situación. Además, de las anteriores características, debido a la propia naturaleza del algoritmo base escogido, se puede asegurar que nuestros algoritmos se adaptaran bien a la llegada de tareas aperiódicas y debido a que posee prioridades estáticas, será estable en caso de sobrecarga de alguna de sus tareas, de manera que en caso de que en alguna tarea se produzca un sobrecarga del procesador las posibles tareas que pueden perder el plazo son las de prioridad igual o inferior a la que ha producido el sobrecarga. Capítulo 3 RECURSOS COMPARTIDOS. El objetivo de este capítulo es la planificación con ahorro energético de un sistema de tiempo real estricto en el que diversas tareas del sistema comparten recursos software (estructuras compartidas) o recursos hardware (dispositivos compartidos), ambos en forma de secciones críticas. Para ello se ha introducido un protocolo que minimice los problemas de la inversión de prioridades que puede presentarse en el acceso con exclusión mutua a los recursos. Recursos Compartidos. - 101 de 209 - 3.1 Introducción Los sistemas de tiempo real están formados por múltiples tareas que se ejecutan de manera concurrente, o en paralelo en el caso de las arquitecturas con múltiples procesadores. Si estas tareas no son independientes sino que interaccionan entre si la planificación resulta mucho más compleja. Cuando las tareas cooperan entre si, es imprescindible la sincronización entre ellas, ya sea mediante sincronismo en el uso de variables compartidas, dispositivos o zonas de exclusión mutua entre las distintas tareas, ya sea mediante la precedencia temporal, una tarea debe finalizar antes del inicio de la siguiente. Sin embargo, en la mayoría de estudios de planificación, se ignoran estas especificaciones de sincronismo entre las tareas. El algoritmo de planificación debe asegurar la consistencia de los recursos compartidos, por lo tanto, se debe garantizar la exclusión mutua entre las tareas que compiten por el uso de estos recursos (el código que debe ejecutase en exclusión mutua se denomina sección crítica). El modelo de tareas que se usará es el siguiente: Tareas periódicas independientes sin acceso a los recursos compartidos, tareas periódicas que acceden a los recursos compartidos en algún instante de su ejecución. El tiempo máximo de acceso al recurso compartido es conocido y se halla incluido en el WCET de la tarea periódica. Cuando se utilizan algoritmos de planificación que utilizan distintas prioridades para las tareas junto con el acceso a recursos compartidos, se puede presentar el problema de la inversión de prioridades que tiene lugar cuando una tarea de una cierta prioridad esta forzada a posponer su ejecución por otra tarea de prioridad menor con el fin de preservar la exclusión mutua. (Se dice que la tarea de menor prioridad bloquea a la tarea de mayor prioridad.) Además, la determinación del tiempo de bloqueo (tiempo en que la tarea de mayor prioridad esta pendiente de la finalización de la tarea de menor prioridad) en el peor caso no está acotado puesto que otras tareas de prioridad intermedia pueden, a su vez, retardar la ejecución de la tarea de prioridad inferior que posee el recurso. Este tiempo de bloqueo no acotado, afecta seriamente la predecibilidad del sistema de tiempo real [14]. Un mecanismo de coordinación en el acceso a los recursos compartidos en la planificación con sistema de prioridades estáticas, consiste en el uso de protocolos de Capítulo 3 - 102 de 209 - cambio de prioridad inducido por el acceso al recurso compartido. Por ejemplo, los protocolos definidos por de Sha, Rajkumar y Lehoczky en [76] que son el protocolo de herencia de prioridad (Priority Inheritance Protocol), el protocolo de techo de prioridad original (Priority Ceiling Protocol) y el protocolo de techo de prioridad inmediato (Immediate Ceiling Priority Inheritance Protocol). En los tres protocolos se produce un cambio en la prioridad de la tarea que accede o posee el recurso, pero con propiedades diversas al producirse el cambio debido a distintos motivos: • En el protocolo de herencia de prioridad, el cambio de prioridad se produce en el instante en que una tarea solicita un recurso ocupado por otra tarea de menor prioridad, la tarea que posee el recurso hereda la prioridad de la tarea que lo solicita. Al abandonar el recurso la tarea recupera la prioridad que tenia inicialmente. Este protocolo acota el tiempo de bloqueo, siendo este la el mínimo entre: la suma de tiempo que todas las tareas de menor prioridad ocupan el recurso y la suma del acceso a todos los recursos compartidos del sistema. Un problema de este protocolo es que si una tarea utiliza diferentes recursos, puede estar bloqueada en todos ellos. Este fenómeno se conoce como bloqueo en cadena y ocasiona un tiempo de bloqueo excesivo no acotado. Una tarea puede verse obligada a modificar su prioridad varias veces durante la ocupación de un recurso. Este protocolo no evita el interbloqueo entre las tareas. (Un interbloqueo se produce por ejemplo en la siguiente situación: una tarea posee un recurso x y esta bloqueada esperando la liberación de un recurso y. La tarea que posee el recurso y también esta bloqueada esperando el recurso x. Ambas tareas se encuentran en un interbloqueo, no pudiendo progresar ninguna de las dos.) • En el protocolo de techo de prioridad original, al igual que en el anterior, el cambio de prioridad se produce en el instante en que una tarea solicita un recurso ocupado por otra tarea de menor prioridad. En este caso la prioridad que obtendrá será la máxima prioridad de todas las tareas que puedan acceder al recurso (techo de prioridad). El techo de prioridad de un recurso puede calcularse de manera estática (antes de iniciar la ejecución de la aplicación). Una tarea solo puede bloquear un recurso si su prioridad es estrictamente mayor que el techo de prioridad de todos los recursos que en ese momento estén ocupados. Al abandonar el recurso recupera la prioridad inicial. Este Recursos Compartidos. - 103 de 209 - protocolo acota el tiempo de bloqueo, siendo este el máximo tiempo que pueden ocupar el recurso las tareas de menor prioridad. Este protocolo impide los bloqueos en cadena y el interbloqueo. Un problema de este protocolo es que puede bloquear tareas sin necesidad, debido a la ocupación de un recurso con un techo de prioridad mayor que la tarea no necesitará. La implementación de este protocolo es compleja, debido a que se necesita un control estricto de los recursos que están ocupados en cada instante. • En el protocolo de techo de prioridad inmediato, el cambio de prioridad se produce en el instante en que la tarea bloquea el recurso. En este caso la prioridad que obtendrá será el techo de prioridad del recurso al que accede. Este protocolo tiene las mismas ventajas que el anterior, pero su implementación es más sencilla, incluyéndose en el estándar POSIX 1000.1c (Pthreads) bajo el nombre de Priority Protected Protocol. Un refinamiento de los protocolos anteriores de cambio de prioridad es el protocolo de Stack-based diseñado por Baker en [9] que permite la planificación con prioridades dinámicas y estáticas. En el momento de diseñar nuestro algoritmo no existían (según nuestro conocimiento) otros algoritmos de planificación con ahorro energético que permitieran el uso de recursos compartidos. En las mismas fechas, R. Jejurikar y R. Gupta en [33] y [34] publicaron una serie de algoritmos basado en EDF y en RMS respectivamente. Sin embargo ambos algoritmos el computo de la velocidad del procesador se realiza de manera estática, sin poder aprovechar el WCET no consumido por la tarea. En sus artículos presentan cuatro posibilidades: • Calcular la velocidad de ejecución considerando que las secciones críticas se ejecutaran a máxima velocidad, con lo que se reduce el tiempo de bloqueo de las tareas de mayor prioridad. • Calcular la velocidad de ejecución constante durante toda la ejecución de la tarea, incrementando con ello el tiempo de bloqueo de las tareas de mayor prioridad. • Incrementar el WCET de las tareas candidatas a ser bloqueadas, y considerar a partir de este punto que las tareas son independientes. Capítulo 3 - 104 de 209 - • Añadir una nueva tarea de máxima prioridad con WCET igual al máximo tiempo de bloqueo que se pueda producir con periodo el máximo del periodo de las tareas del sistema. A partir de este punto se consideraran las tareas como independientes. Estas cuatro aproximaciones las comparan con el planificador FPS de Shin y Choi, y se demuestra que existe un ahorro de energía promedio del 25-30%. Donde los algoritmos son de complejidad polinómica. En todas sus aproximaciones se considera una variación continua de la velocidad del procesador. La consecución del objetivo del presente capítulo vendrá dado por la inmersión del protocolo de techo de prioridades inmediato en los algoritmos para ahorro energético de prioridades estáticas propuestos anteriormente, con lo que se permitirá que el conjunto de tareas utilice recursos compartidos. Para finalizar el capítulo se realizará la evaluación de los resultados obtenidos en los diversos algoritmos. 3.2 Metodología y desarrollo. En este punto se expondrán las ideas básicas de la modificación que se realizará de los algoritmos desarrollados en los capítulos anteriores, con el fin de permitir la sincronización de los procesos. La idea principal de la modificación es la inmersión de protocolos de cambio de prioridad en los algoritmos que se utilizan. El algoritmo de planificación que se usará es una modificación del algoritmo Power Low Modified Dual Priority Scheduling desarrollado en el capítulo 2 de la presente tesis. Este algoritmo, tal como se ha comentado anteriormente, se basa por una parte en el algoritmo de prioridad dual, propuesto originalmente por Burns y Wellings [13] y modificado por Davis y Wellings [23], y por otra en el algoritmo de ahorro energético Fixed Priority Scheduling Algorithm propuesto por Shin y Choi [77]. Nosotros proponemos una modificación de estos algoritmos de planificación con ahorro energético para imbuir el protocolo de techo de prioridades inmediato que Sha, Rajkumar y Lehoczky en [76] proponen como solución al problema de inversión de prioridades. Recursos Compartidos. - 105 de 209 - Las modificaciones que deben realizarse en el algoritmo Power Low Modified Dual Priority Scheduling son las siguientes: • Aumento del WCRT (Worst Case Response Time) de la tarea i (τi) debido a los bloqueos que pueden producir las tareas de menor prioridad que usan los recursos compartidos a los que quiere acceder la tarea τi. El WCRT se calcula según la siguiente formula recursiva : j ihpj j n i ii n iC T WCRT CBWCRT * )( 1∑ ∈ +         ++= (ec. 14) donde Bi es el tiempo máximo de bloqueo que se determinará mediante el siguiente algoritmo: ( ) ( )( ) kCiknutilizacióB K k i∗= = , max 1 (ec. 15) donde utilización(k,i) es la fracción de tiempo de computo de la tarea τk en su interferencia con la tarea τi en el acceso a algún recurso compartido. • Como consecuencia del punto anterior, el tiempo de promoción (Tp) disminuye, dado que éste se calcula como Tp=(D-WCRT) Este hecho repercutirá de forma negativa en el ahorro energético, dado que las tareas promocionarán más rápido a la URQ, siendo en el peor de los casos (tiempo de promoción igual al plazo temporal) un esquema equivalente al algoritmo LPFPS, en el que la única posibilidad de reducir la velocidad del procesador está ligada a la existencia de una única tarea en la cola de preparados. • Cambio de la prioridad de las tareas durante el tiempo de acceso a los recursos compartidos, incrementando momentáneamente la prioridad la tarea al techo del recurso. En el algoritmo PLMDP las tareas disponen de dos niveles de prioridades según se hallen en la URQ o en la LRQ. Recordemos que las tareas de la URQ son aquellas en las que las tareas no permiten ningún retraso causado por tareas no previstas. En nuestro caso, el techo de prioridad de los recursos será igual a la prioridad de la tarea de mayor prioridad en la URQ que utilice el recurso. Para poder evaluar la eficiencia de nuestro algoritmo y al no disponer de ningún algoritmo de planificación on-line con prioridades dinámicas, ahorro energético y acceso a recursos compartidos, se ha modificado el algoritmo propuesto por Shin y Capítulo 3 - 112 de 209 - siguiente tarea para ser ejecutada seleccionando la primera disponible desde el nivel de prioridad mayor al nivel de prioridad menor (URQ, MRQ, LRQ). Cuando el planificador ha decidido que tarea ejecutará, antes de empezar la ejecución de ésta, deberá calcular la velocidad del procesador a la que ejecutará la tarea, teniendo en cuenta el tiempo máximo de ejecución posible de las tareas según se vio en el punto 2.2.4. El cálculo de la velocidad se halla explicado en capítulo anterior. 3.2.4 Cálculo de la velocidad de ejecución del procesador. La principal diferencia entre los algoritmos PLMDP y EPLDP, tal como se vio en el Capítulo 2, se basa en el establecimiento de una cota en la máxima reducción de la velocidad. Esta cota será variable en función del comportamiento del sistema, intentando monitorizar la utilización total del procesador. En este punto se va a realizar una reflexión sobre este cálculo de velocidad. Se ha visto que la inmersión del protocolo de techo de prioridad inmediato en el algoritmo de planificación provoca un aumento del WCRT de las tareas provocado a su vez por el tiempo de bloqueo que producen las tareas de menor prioridad que usan los recursos compartidos, que conlleva una disminución del tiempo de promoción. Esto implica que las tareas promocionaran antes y por lo tanto habrá menores oportunidades para reducir la velocidad del procesador. El tiempo de bloqueo está calculado suponiendo que la tarea se ejecuta a máxima velocidad. En nuestros planificadores, la reducción de velocidad es independiente del uso de los recursos, esto implica que una tarea puede reducir la velocidad de ejecución aunque tenga asignado un recurso, por lo tanto, se debe asegurar que la reducción de la velocidad cuando la tarea usa un recurso no pueda provocar la perdida de ningún plazo temporal. El problema puede darse cuando el tiempo de bloqueo real sea mayor que el tiempo de bloqueo calculado. El tiempo de bloqueo real de la tarea de mayor prioridad es el tiempo que pasa desde que se activa, sin poder ejecutarse debido a la ejecución de una tarea de menor prioridad con un recurso, hasta que empieza la ejecución de esta. A continuación se realizará un análisis de los posibles casos: Imaginemos que en el sistema hay dos tareas: τ1 y τ2. τ2 en ejecución, τ1 mayor prioridad que τ2, esto implica que τ2 esta bloqueando el recurso. Recursos Compartidos. - 113 de 209 - o τ1 en LRQ. La tarea puede retrasarse sin causar ningún problema, tal como demuestra el planificador Dual Priority. Sin embargo debido al protocolo de techo de prioridad inmediata la tarea τ2 se esta ejecutando a la prioridad del techo del recurso (URQ) y por tanto momentáneamente tiene mayor prioridad que τ1. τ1 puede retardarse sin problemas hasta su instante de promoción. o τ1 promociona a URQ. En URQ hay como mínimo τ1 y τ2 se esta ejecutando, por tanto no se puede reducir la velocidad del procesador, ejecutándose τ2 a máxima velocidad, por lo que el tiempo de bloqueo real será igual o menor que el calculado. 3.3 Comparativa entre los algoritmos. A continuación, se evaluaran únicamente los algoritmos PLMDP y el LPFPS contra ejecutar siempre a máxima velocidad, con el fin de observar las distintas características energéticas de cada uno. En este punto no se compararan nuestros algoritmos con ningún planificador con asignación de prioridades dinámicas tipo EDF, debido a que el protocolo que se usa en el acceso a los recursos compartidos es específico para planificadores con prioridades estáticas. Ni se comparará con el EPLDP, que consiste en limitar la reducción de velocidad del procesador, adecuándose a la carga del sistema pendiente de realizarse. Cada experimento constará de un conjunto de tareas independientes que pueden o no acceder a recursos compartidos. Cada tarea está caracterizada por un periodo (T), un plazo temporal (D) y un peor tiempo de cálculo (WCET) y una prioridad relativa a las otras tareas del conjunto (P). Las tareas con acceso a recursos compartidos están especificadas por el instante de acceso al recurso, y el WCET que consumirán dentro del recurso. En los experimentos que se han realizado se ha variado el porcentaje de WCET consumido por las distintas tareas y subtareas, para comprobar si el algoritmo de planificación se adapta a esta característica dinámica en el comportamiento real de las tareas. La variación que se ha tenido en cuenta va desde el 10% hasta el 100% del WCET. La duración de cada experimentos normalmente será de un hiperperiodo (mínimo común múltiplo de los periodos de las tareas que forman un conjunto de pruebas) en el caso que el comportamiento del consumo del WCET sea siempre el Capítulo 3 - 114 de 209 - mismo para todas las activaciones de las tareas, y sobre 100 hiperperiodos en el caso de que la variación del porcentaje de WCET consumido sea variable, de media el porcentaje de WCET representado en la gráfica. Todos los resultados se muestran normalizadas respecto a uno de los algoritmos de planificación, normalmente será el que se ejecute a la máxima velocidad del procesador, que será el que tendrá un mayor consumo energético, por lo tanto, se representarán valores relativos entre 0 y 1, para evitar así las posibles diferencias entre los distintos conjuntos de prueba. En los casos conocidos no existe constancia ni del momento ni de la duración en el acceso a los recursos compartidos, por este motivo, se analizará únicamente el caso de control automático (CNC) [38] como caso real, dado que para los otros casos, aviónica [50] y navegación [15], no se ha encontrado un caso general planificable en el acceso a los recursos por parte de las tareas. 3.3.1 Caso real: Caso de control automático. Las características del conjunto de tareas para el caso de CNC [38] se muestran en la Tabla 5. En la Figura 44 se muestra el diagrama de acceso a los recursos compartidos por parte de las tareas del sistema. En esta figura, los óvalos representan las tareas periódicas y los cuadrados los recursos compartidos. Las direcciones de las flechas significan el uso que se hace del recurso, si se consulta o si se modifica. Al no estar especificado el cuando se accede al recurso, ni el tiempo de acceso a este. Se define, como es habitual, la sección crítica (cs) el intervalo de tiempo en que la tarea bloquea el recurso y la sección no crítica (ncs) el intervalo de tiempo en que la tarea no utiliza el recurso. En este caso, según las tareas bloqueen o liberen los recursos se pueden observar los siguientes casos: • cs-ncs. Bloqueo del recurso al inicio de la tarea y después se libera continuándose la ejecución de esta. • ncs-cs. Primero no se bloquea el recurso, se accede a él al cabo de un intervalo de tiempo, liberándose al final de la ejecución de la tarea. • cs-ncs-cs. Bloqueo inicial del recurso, liberación del recurso, finalizando la tarea con otro bloqueo del recurso. Recursos Compartidos. - 115 de 209 - Con estas tres posibilidades, se han caracterizado todos los casos posibles en los que la tarea puede acceder a un recurso compartido. En las simulaciones se ha variado el tiempo en el que una tarea esta ejecutando una sección crítica, es decir, está usando un recurso con exclusividad. Este tiempo se ha variado des de el 0% (no usa el recurso) al 100% del WCET (usa el recurso durante toda la ejecución) para tratar todos los casos posibles. T1 T2 T3 T4 T5 T6 T8 T7 R1 R2 R5 R6 R1,R2 R7,R8 R9 R11 R10 R1,R2, R3,R4 R3 R4 PLANT Figura 44: Diagrama del acceso a los recursos compartidos por parte de las tareas en el caso de control automático [38]. En las gráficas siguientes, se han representado los resultados en términos del promedio de energía consumida por el procesador. Todas las simulaciones cubren un hiperperiodo, y las tareas consumen siempre el mismo porcentaje de WCET. Tal como se ha visto en el Capítulo 2, es el mismo resultado que se obtendría si la simulación se hubiera realizado con las tareas consumiendo un WCET variable de promedio el indicado, y haciendo durar la simulación varios hiperperiodos. De la Figura 45 a la Figura 47, se muestra el comportamiento de los dos algoritmos cuando se varia el tiempo de ejecución en la sección crítica desde el 0% al 100%. En la Figura 45, las tareas consumen el 100% de todo el WCET, en la Figura 46 las Capítulo 3 - 116 de 209 - tareas consumen el 60% del WCET y en la Figura 47 las tareas solamente consumen el 20% del WCET. La mejora obtenida por nuestro algoritmo varia del 15% si todas las tareas consumen el 100% del WCET al 48% si las tareas consumen el 60% del WCET y el 75% si las tareas consumen únicamente el 20% del WCET. 0 0,2 0,4 0,6 0,8 1 % recursos compartidos Consumo energético LPFPS PLMDP 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% Figura 45: Consumo energético normalizado variando el tiempo ejecutado en sección crítica si la tareas consumen el 100% del WCET. 0 0,2 0,4 0,6 0,8 1 % recursos compartidos Consumo energético LPFPS PLMDP 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% Figura 46: Consumo energético normalizado variando el tiempo ejecutado en sección crítica si la tareas consumen el 60% del WCET. 0 0,2 0,4 0,6 0,8 1 % recursos compartidos Consumo energético LPFPS PLMDP 0% 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% Figura 47: Consumo energético normalizado variando el tiempo ejecutado en sección crítica si la tareas consumen el 20% del WCET. Recursos Compartidos. - 117 de 209 - En las figuras anteriores se puede observar un descenso significativo de la energía consumida cuando la ejecución de la tarea en la sección crítica es del 100%. A continuación se muestra un análisis individual de está situación particular ( Figura 48, Figura 49 ). Supongamos que se dispone de tres tareas τ1, τ2 y τ3. La prioridad de las tareas es de 3,2 y 1 respectivamente (a menor número mayor prioridad). τ1 y τ2 acceden al mismo recurso R1, por lo tanto, el techo de prioridad es la prioridad de τ2. El instante de promoción de la tarea τ1 es menor que le instante de promoción de la tarea τ2, y es menor que el instante de promoción de la tarea τ3. En la cola LRQ el orden de las tareas es τ1, τ2 y τ3. A R τ 2 URQ τ 2 1 τ 1 2 TP τ 2 τ 2 , τ 3 τ 1 3 τ 1 τ 1 1 LRQ A R τ 2 2 τ 2 3 TP τ 3 TP τ 1 τ 3 TIME τ 1 1 F F Figura 48: Las tareas no consumen todo el WCET en la sección crítica. A τ 2 URQ τ 1 3 τ 1 2 TP τ 2 τ 2 , τ 3 τ 2 3 τ 1 τ 1 1 LRQ R,F,A τ 2 1 τ 2 2 TP τ 3 TP τ 1 τ 3 TIME τ 1 1 R,F Figura 49: Las tareas consumen el WCET en la sección crítica. En la Figura 48, inicialmente la tarea τ1 se está ejecutando en la LRQ, en el instante de promoción TPτ1, la tarea τ1 promociona, y continua su ejecución. En el instante de promoción TPτ2, la tarea τ2 promociona a la URQ. Como τ1 se halla en sección crítica, su prioridad es la del techo del recurso, por lo tanto τ2 no puede expulsarla del procesador, continuando la ejecución de τ1 hasta de τ1 abandone la sección Capítulo 3 - 118 de 209 - crítica y recupere su prioridad base. Cuando τ1 libera el recurso, τ2 expulsa a τ1, que se encola en la URQ. En este momento existen dos tareas en la URQ, por la que no se puede reducir la velocidad de ejecución. Cuando finaliza τ2, τ1 puede ejecutarse a velocidad reducida, ahorrando energía, pero el tiempo de ejecución que le queda es pequeño, reduce mucho la velocidad, pero ha obligado al procesador a ejecutar τ2 a máxima velocidad. En la Figura 49, la tarea τ1 finaliza al liberar el recurso, por lo tanto τ2 esta sola en la URQ y puede por tanto reducir la velocidad de ejecución durante toda su ejecución. Finalmente, en la Figura 50 se representa el porcentaje de ahorro energético en las tres posibles combinaciones analizadas cuando el WCET consumido total varia des del 10% al 100%. Cada punto del gráfico representa la suma de la energía consumida variando el porcentaje de WCET consumido en la sección crítica desde el 0% al 100%. Se puede observar que en el caso cs-ncs-cs, en que el bloqueo causado por la sección crítica es la mitad del bloqueo causado por cs-ncs y por ncs-cs, y ocurre dos veces durante la ejecución de una instancia de la tarea, el algoritmo PLMDPR mejora al algoritmo LPFPSE entre el 23% y el 62%. En el caso de cs-ncs la mejora obtenida varia entre el 21% y el 90%. Una razón posible del distinto comportamiento entre los casos es que en el cs-ncs-cs, la tarea que abandona la sección crítica aun no ha finalizado, obligando a cualquier otra tarea de mayor prioridad que se ejecute a ejecutarse a máxima velocidad. Si existe una única sección crítica, los resultados son equivalentes, ya sea ejecutando primero la sección crítica o primero la no sección crítica finalizando la tarea con la ejecución en sección crítica. 0,0 0,1 0,2 0,3 0,4 0,5 0,6 0,7 0,8 0,9 1,0 10% 20% 30% 40% 50% 60% 70% 80% 90% 100% % of WCET exhausted PLMDPR / LPFPSR cs-ncs-cs cs-ncs ncs-cs Figura 50: Ratio PLMDPR/LPFPSR de energía consumida en función del tiempo ejecutado en sección crítica para distintas ubicaciones de ésta. Recursos Compartidos. - 119 de 209 - 3.4 Conclusiones Se ha presentado una extensión del planificador Power Low Modified Dual Priority que permite a los sistemas de tiempo real usar recursos compartidos sin comprometer el cumplimiento de los plazos temporales consiguiendo un menor consumo energético. Se ha demostrado que esta aproximación continua mejorando al ahorro energético obtenido en media por el LPFPR. En el caso del conjunto de tareas del CNC, el rango de mejoría va desde el 16% al 98% dependiendo del uso de los recursos compartidos que realicen las tareas y el porcentaje de consumo del WCET que se produzca. El algoritmo presentado no incrementa la complejidad del LPFPR con lo que puede ser implementado fácilmente en la gran mayoría de núcleos de sistemas operativos, como demuestra por una parte que el protocolo techo de prioridad inmediato sea considerado estándar POSIX, y por otra que el cálculo de la velocidad requiere únicamente conocer el instante de llegada de las tareas, el instante de promoción y el plazo temporal de las tareas, requerimientos necesarios para la implementación del algoritmo de Dual Priority [86]. Capítulo 4 PLAZOS GLOBALES Y PRECEDENCIAS ENTRE TAREAS En este capítulo se planificará un sistema de tiempo real estricto en el que existan restricciones temporales globales que afecten a una secuencia de tareas, que han de ejecutarse en el mismo o en distintos procesadores siguiendo una ordenación temporal. La planificación de la secuencia de tareas deberá garantizar todas las restricciones temporales de estas, que pueden ser individuales a las tareas o globales al conjunto, con el mínimo coste energético posible. Capítulo 3 128 de 209 - plazo que se haya establecido reducir velocidad de ejecución, obteniendo reducción energética. Sin embargo, si dos tareas consecutivas en la cadena de precedencias se hallan en procesadores distintos, se debe tener en cuenta que el procesador puede estar libre a la espera de las activaciones de las tareas sucesoras. Cada procesador se puede analizar individualmente, ya que las precedencias se aseguran en el momento de repartir el plazo global, fijando un desplazamiento inicial de las tareas sucesoras igual al plazo temporal de su tarea predecesora. El periodo de activación de todas las tareas será igual al periodo de la cadena. b) No repartiendo la totalidad del plazo global entre todas las tareas de la cadena. Si no se fija un plazo local a las tareas, se permitirá que estas usen el necesario según la carga existente en el sistema a cada momento, otorgando flexibilidad al sistema. La primera tarea de la cadena (τ1) se activará en el periodo la cadena mientras que las tareas sucesoras no tienen instante de activación sino que se activan con la finalización de sus tareas predecesoras. Esto implica que la tarea predecesora no puede ejecutarse a velocidad reducida, puesto que no tiene previsto un instante de finalización máximo distinto del plazo temporal global, instante en el que deben haber finalizado todas las tareas que forman parte de la cadena de precedencias. Esta política es la más flexible, sin embargo a nivel energético dará poco ahorro puesto que únicamente se podrá reducir la velocidad de ejecución de la última tarea de la cadena de precedencias y de las tareas independientes. Usando esta política, es muy difícil la asignación automática de prioridades a las tareas, puesto que como que el plazo global acostumbra a ser grande, las tareas de la cadena de precedencia tendrán poca prioridad. c) Repartiendo una parte del plazo global entre todas las tareas de la cadena. A cada tarea se le asigna el mínimo plazo que asegure la planificabilidad del sistema, y se usa el resto del plazo según las necesidades instantáneas de este. Este caso es parecido al del punto a), pero con el plazo temporal de las tareas variable. Plazos Globales y Precedencias entre Tareas - 129 de 209 - Si se usa un algoritmo de planificación con prioridades estáticas, el hecho de disponer de un plazo mayor puede modificar la prioridad de la tarea según la asignación de prioridades que se utilice. Sin embargo, al ser las prioridades estáticas cuando se ha decidido el orden, las tareas se ejecutaran siempre en este orden fijado. Disponer de un plazo mayor al previsto, solo será útil en el momento en que la tarea pueda reducir la velocidad de ejecución ahorrando energía. Esta división es la que se realiza en el artículo [55]. El hecho de disponer de prioridades estáticas permite que, antes de iniciar el sistema, se pueda asegurar su planificabilidad ejecutándose a máxima velocidad. Si el planificador es de prioridades dinámicas, el orden de ejecución de las tareas será variable dependiendo de la asignación del plazo que se realice. Al reducir la velocidad de ejecución de las tareas debe tenerse en cuenta que la utilización del procesador no supere el 100%, de lo contrario se tendría un sistema que no seria planificable. Para asegurar que esto no ocurre, se utilizará un planificador con servidor de tiempo disponible. Este tiempo se usará para ralentizar la ejecución de las tareas [87], ahorrando energía. Analizadas las distintas alternativas, la solución que se propone en esta tesis, consiste en no distribuir la totalidad del plazo temporal global, permitiendo una cierta flexibilidad en la ejecución de las tareas. Para realizar la planificación del sistema distribuido, se dispondrá de un planificador local en cada procesador. Las activaciones de la primera tarea de cada cadena de precedencias serán periódicas con un periodo igual al de la cadena, mientras que las activaciones de las tareas sucesoras, serán dependientes de la finalización de la tarea que la precede en la cadena. Cuando una tarea finalice su ejecución, generará un mensaje que activará su tarea sucesora. Cuando en el conjunto de tareas existen precedencias se pueden dar varias opciones: • La última tarea lista para ser ejecutada no dispone de tarea sucesora. En este caso, se puede reducir la velocidad de ejecución para finalizar antes de la activación de la siguiente tarea o antes del cumplimiento del plazo temporal. • La última tarea dispone de tarea sucesora. En este caso, existen dos opciones, todas la tarea sucesora se ejecute en el propio procesador o en otro procesador distinto. Capítulo 3 130 de 209 - o Mismo procesador: en este caso, se podría llegar a reducir la velocidad de ejecución de ambas tareas hasta el cumplimiento de su plazo o hasta la activación de otra tarea. O bien se podría ejecutar la tarea predecesora a máxima velocidad y dejar la posible reducción de velocidad para la tarea sucesora. o Distinto procesador: en este caso, la reducción de la tarea en curso (finalización posterior), puede provocar que el procesador en el que se ejecute alguna tarea sucesora quede libre a la espera de l’activación de esta. Esto implica, que la interferencia que produce esta tarea sobre las otras tareas del sistema seria mayor que si la tarea se hubiera activado a la finalización de la tarea predecesora ejecutada a máxima velocidad. Aunque como se ha visto en el capítulo 2, la mejor opción seria ejecutar ambas tareas a velocidad reducida, el algoritmo implementado reduce únicamente la velocidad de la última tarea de la cadena, reduciendo de este modo la complejidad de la solución y unificando los casos en que la tarea sucesora pertenezca al mismo o distinto procesador. 4.2.1 Adecuación de los algoritmos de planificación. A continuación se verá un ejemplo para comprobar como seria la planificación con los distintos algoritmos estudiados en los capítulos anteriores para tratar el problema de las precedencias y de los plazos globales. Supongamos que se dispone de los siguientes conjuntos ejemplos: • Tabla 16: En el conjunto de tareas existe un único plazo temporal global. • Tabla 17: En el conjunto de tareas existen dos plazos temporales globales. • Observemos que en el sistema de la Tabla 16 el plazo temporal global no es planificable directamente, puesto que si se suma el tiempo de finalización de la tarea t13 con el de la tarea τ23 se obtienen 43 unidades de tiempo, que es superior al plazo temporal disponible (36 unidades). Sin embargo, esta situación es demasiado pesimista, ya que la tarea τ23 únicamente debe esperar a que finalice la tarea τ13. Esta tarea no siempre finalizará usando su tiempo peor de finalización, y aunque ésta lo haga, la tarea τ23 puede que no reciba Plazos Globales y Precedencias entre Tareas - 131 de 209 - toda la interferencia posible de las tareas de mayor prioridad, finalizando siempre antes que el peor tiempo de finalización. Procesador Tarea Periodo Plazo Temporal WCET WCRT independiente τ11 10 10 4 4 τ12 18 18 4 8 Procesador 1 τ13 36 36 8 28 τ21 10 10 4 4 τ22 18 18 4 8 Procesador 2 τ23 36 36 3 15 Cadena de Precedencias Tareas Periodo Plazo temporal Tiempo envío del mensaje WCRT de la cadena de precedencias τ13 Dee1 τ23 36 36 1 36 Tabla 16: “Benchmark” con una cadena de precedencias para la evaluación del ahorro energético con precedencias entre las tareas. WCET=peor tiempo de ejecución, WCRT=peor tiempo de finalización suponiendo procesadores independientes. Para realizar el cálculo exacto del peor tiempo de finalización de las cadenas de precedencia debe calcularse el tiempo de finalización de cada una de las instancias de esas tareas en todo el hiperperiodo. Este cálculo puede hacerse off-line, para asegurar que el conjunto de tareas que se propone es planificable. Estudiando el peor tiempo de finalización obtenido por las distintas instancias de la cadena de precedencias en un hiperperiodo, se obtiene que el peor tiempo de finalización es de 36 unidades de tiempo, lo que implica que el sistema es planificable. El resultado del peor tiempo de finalización podría guardarse en un vector del planificador para realizar una previsión fiable del tiempo de llegada de los mensajes de las tareas predecesoras, sin embargo, si el hiperperiodo es muy grande (acostumbra a ocurrir en tareas no armónicas), el uso de memoria seria grande, cosa que se quiere evitar. En nuestros algoritmos se realizará una previsión muy optimista del tiempo de finalización de las tareas de la cadena de precedencias, previendo que tendrán una única interferencia de las tareas de mayor prioridad. Este hecho provocará que si la tarea tiene una interferencia mayor de la prevista, no se pueda reducir la velocidad de ejecución de tareas que serian factibles de ser reducidas, gastando mayor cantidad de energía y dejando libre al procesador. En la Figura 52 se puede observar la ejecución de las tareas del ejemplo (Tabla 16) suponiendo una planificación de prioridades fijas con asignación Rate Monotonic a velocidad máxima. En esta ejecución se observa que la primera instancia de la tarea τ13 se ejecuta con una interferencia máxima (instante crítico) finalizando en t=28. La Capítulo 3 132 de 209 - instancia de la tarea τ23 que la sucede no tiene la máxima interferencia finalizando en el instante 36, cumpliendo así el plazo temporal global. La tarea τ23 tiene su instante crítico en la tercera instancia con un tiempo de finalización de 14 unidades de tiempo, ya que a su llegada, una tarea de mayor prioridad ha ejecutado una unidad de cálculo. Pero en este caso su instancia precedente ha finalizado en 20 unidades de tiempo, no ha hallado la interferencia máxima. La tercera instancia, ha finalizado en 35 unidades de tiempo. El instante crítico de las tareas que forman parte de una cadena de precedencias, normalmente, no coincidirán, por lo que es demasiado pesimista considerar que se da esta circunstancia. En el caso concreto del ejemplo, se observa que no hay perdidas de plazo, y por lo tanto, el sistema es planificable, tal y como se había supuesto inicialmente. Con esta planificación existen 28 unidades libres en el primer procesador, y 53 en el segundo. 180 160 165 170 175 140 145 150 155 120 125 130 135 100 105 110 115 80 85 90 95 60 65 70 75 40 45 50 55 20 25 30 35 175 180 velocidad 1 0.5 0 0 5 10 15 155 160 165 170 135 140 145 150 115 120 125 130 95 100 105 110 75 80 85 90 55 60 65 70 35 40 45 50 15 20 25 30 Inicio de tarea t13 t23 velocidad 1 0.5 0 0 5 10 t11 t21 t12 t22 Llegada previsión Figura 52: Ejecución a máxima velocidad de los procesos de la Tabla 16 en un sistema distribuido con un único plazo temporal global usando offset dinámico. En el siguiente ejemplo (Tabla 17), se ha añadido otro plazo global en las tareas del conjunto anterior, de manera que existirán, en el sistema, dos cadenas de precedencia o plazos globales. Procesador Tarea Periodo Plazo Temporal WCET WCRT independiente τ 11 10 10 4 4 τ 12 18 18 4 8 Procesador 1 τ 13 36 36 8 28 τ 21 10 10 4 4 τ 22 18 18 4 8 Procesador 2 τ 23 36 36 3 15 Cadena de Precedencias Tareas Periodo Plazo temporal Tiempo envío del mensaje WCRT de la cadena de precedencias τ12 Dee2 τ22 18 18 1 18 τ13 Dee1 τ23 36 36 1 36 Tabla 17: Conjunto de tareas con dos cadenas de precedencias para la evaluación del ahorro energético. Plazos Globales y Precedencias entre Tareas - 133 de 209 - En este sistema se puede observar, que la suma de los peores tiempos de finalización de las tareas del Dee2 es 16, por lo tanto el sistema sería planificable repartiendo de manera estática el plazo global a cada una de las tareas de la cadena de precedencias. En el caso de distribución estática, la tarea τ22 tiene un desplazamiento inicial en su ejecución igual al plazo de la tarea τ12 no pudiendo empezar hasta el instante 8 si la repartición es estática o hasta el instante 9 en caso de activación por mensaje. Finalizando esta tarea en el instante 16 o 17, respectivamente, siendo por tanto planificable. Sin embargo, la cadena Dee1 tiene el mismo problema que en el ejemplo de la Tabla 16, no siendo planificable si se supone una repartición estática. En la Figura 53 se presenta la ejecución del sistema de la Tabla 17 en el caso de activación de la tarea sucesora mediante mensaje. En el segundo procesador, se puede observar que en el instante 4, las tarea τ21 ha finalizado, pero la tarea τ22 no se haya activa, dejando, por tanto, libre el procesador. La interferencia que tiene la primera instancia de la tarea τ13 provoca que esta finalice, en t=28 (ha hallado su máxima interferencia). En este ejemplo, a diferencia del anterior, la segunda instancia de la tarea τ22 no ha finalizado su ejecución, aumentando así, el tiempo de finalización de la primera instancia de la tarea τ23, provocando una perdida de plazo temporal. En este caso, el sistema con la asignación de prioridades Rate Monotonic, no es planificable. t11 t21 t12 t22 Inicio de tarea t13 t23 Plazo perdido velocidad 1 0.5 0 0 5 10 15 20 25 30 35 velocidad 1 0.5 0 35 0 5 10 15 20 25 30 Llegada previsión Figura 53: Ejecución a máxima velocidad de los procesos de la Tabla 17 en un sistema distribuido con un único plazo temporal global usando offset dinámico. A continuación se estudiarán estos dos ejemplos aplicados a los algoritmos propuestos en el capítulo anterior, teniendo en cuenta que las únicas tareas que reducirán la velocidad del procesador serán las que no tengan tareas sucesoras, y que se estimará la llegada de las tareas sucesoras (previsión llegada), de manera que a partir de su llegada estimada ya no será posible disminuir la velocidad del procesador Capítulo 3 134 de 209 - aunque la tarea sea la única del sistema. A si mismo, las tareas sucesoras se activarán por mensaje al finalizar su tarea precedente. Low Power Fixed Priority Scheduling Algorithm. Este algoritmo, como se ha visto en el Capítulo 2, se basa en ahorrar energía reduciendo la velocidad de ejecución de la última tarea existente en la cola de preparados. Las modificaciones realizadas en este planificador son las siguientes:  No reducción de la velocidad del procesador si la última tarea activa tiene una tarea sucesora.  Tener en cuenta la previsión de la llegada de una tarea sucesora. No pudiéndose reducir la velocidad aunque exista, únicamente, una tarea activa, cuando se prevea la activación de una tarea sucesora. La reducción de la velocidad de proceso, podría derivar en una perdida del plazo, ya que se producirá una activación de una tarea cuya llegada no estaba contemplada en el momento del cálculo de la velocidad del procesador.  Envío de un mensaje de activación de las tareas sucesoras. A continuación se analizará el resultado de la planificación LPFPS en los dos ejemplos analizados en el apartado anterior. t13 t23 5 velocidad t11 t21 t12 t22 Inicio de tarea 1 0.5 0 0 40 45 10 15 20 25 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125 130 135 140 145 150 155 160 165 170 175 180 velocidad 1 0.5 0 0 5 10 40 45 50 15 20 25 30 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125 130 135 140 145 150 175 180 155 160 165 170 Llegada previsión 35 30 35 Figura 54: Ejecución usando la planificación LPFPS de los procesos de la Tabla 16 en un sistema distribuido con un único plazo temporal global usando offset dinámico. En la Figura 54 se ha realizado el diagrama de ejecución del conjunto de tareas de la Tabla 16. En este caso se puede observar que el sistema es planificable, ya que se cumplen todos los plazos. El consumo energético obtenido frente a la planificación a máxima velocidad es del 90%. Dejando 42 unidades de tiempo libres. Plazos Globales y Precedencias entre Tareas - 135 de 209 - A continuación, se remarcan los instantes en los que se aplica la modificación del algoritmo de planificación y la consecuencias que ello comporta: • t=5. En el segundo procesador, la tarea τ22 empieza su ejecución, es este instante el algoritmo de planificación calcula la velocidad de ejecución de esa tarea. Es la única tarea activa en el sistema, por lo que se puede alargar su ejecución reduciendo la velocidad del procesador. La siguiente tarea que se activará lo hará en el instante 10, pero se tiene prevista la llegada de la tarea τ23 en el instante 9, por lo que solo se tiene disponibilidad temporal hasta el instante 9, mínimo entre la llegada de una tarea y la previsión de llegada. Este hecho comporta que el procesador quede una unidad de tiempo libre. • t=26. En el primer procesador, la tarea τ13 reanuda su ejecución. En el momento de calcular la velocidad de ejecución, se ve que aun siendo la única tarea activa en el momento, tiene una tarea sucesora, por lo tanto, se ejecutará a velocidad de procesador máxima. Este hecho comportará que al procesador le queden dos unidades de tiempo libre, hasta la activación de la tarea τ11. • t=28. En el primer procesador finaliza la ejecución la tarea τ13 que dispone de tarea sucesora, enviando un mensaje que provocará la activación en t=29 de la tarea τ23 en el segundo procesador. En la Figura 55 se ha realizado el diagrama de ejecución del conjunto de tareas de la Tabla 17. En este caso se puede observar que el sistema no es planificable, ya que no se cumple el plazo global de la cadena de precedencias Dee1. 10 15 20 15 20 25 30 35 40 30 35 40 25 0 5 0 0.5 0 5 1 0.5 0 1 velocidad velocidad t11 t12 t13 t21 t22 t23 10 Llegada previsión Plazo perdido Inicio de tarea Figura 55: Ejecución usando la planificación LPFPS de los procesos de la Tabla 17 en un sistema distribuido con un único plazo temporal global usando offset dinámico. A continuación, se remarcan los instantes en los que se aplica la modificación del algoritmo de planificación y la consecuencias que ello comporta: Capítulo 3 136 de 209 - • t=0. En el segundo procesador, la tarea τ21 empieza su ejecución, es este instante el algoritmo de planificación calcula la velocidad de ejecución de esa tarea. Es la única tarea activa en el sistema, por lo que se puede alargar su ejecución reduciendo la velocidad del procesador. Su plazo temporal es en el instante 10, pero se tiene prevista la llegada de la tarea τ22 en el instante 5, por lo que solo se tiene disponibilidad temporal asegurada hasta el instante 5, mínimo entre el plazo temporal y la previsión de llegada de un mensaje activador de una tarea sucesora. El planificador alargará la ejecución de la tarea hasta el instante 5. Este hecho comportará que el procesador quede nueve unidades de tiempo libre. • t=8. En el primer procesador, la tarea τ12 finaliza su ejecución, enviando un mensaje que llegará en el instante t=9 al segundo procesador, activando la tarea τ13. Que se ejecutará una unidad hasta la activación de la tarea τ12. En el momento de calcular la velocidad de ejecución, se ve que aun siendo la única tarea activa en el momento, no se puede ejecutar a velocidad reducida debido a que se espera la llegada de la tarea τ23. tiene una tarea sucesora, por lo tanto, se ejecuta a velocidad de procesador máxima. • t=10. La activación de la tarea τ23 se apropia del procesador, por ser una tarea de mayor prioridad. • t=28. Finaliza la ejecución de la tarea τ13 enviando un mensaje que activará la tarea τ23 que al ser la tarea de menor prioridad, debe esperar la finalización de las tareas de mayor prioridad en t=35, empieza la ejecución, pero en t=36 le llega el plazo temporal si haber finalizado la ejecución. Low Power Earliest Deadline First Scheduling Algorithm. Este algoritmo, como se ha visto en el Capítulo 2, consiste en ahorrar energía utilizando el slack estático hasta conseguir una utilización del procesador del 100%, pudiendo reducir la velocidad de ejecución de cualquier tarea. Las modificaciones realizadas en este planificador son las siguientes:  No reducción de la velocidad del procesador si la tarea que se ejecuta tiene una tarea sucesora. Plazos Globales y Precedencias entre Tareas - 137 de 209 -  Servidor con periodo igual al de la tarea más frecuente y tiempo de cálculo el máximo posible que mantenga la utilización del procesador por debajo del 100%. Al calcular la capacidad del servidor, ya se ha tenido en cuenta la utilización que usaran las tareas pertenecientes a las cadenas de precedencias.  Las tareas pertenecientes a una cadena de precedencias tendrán la siguiente asignación de plazo: Deekimess succj jki CCDeeD i Γ∈−−= ∑ ∈∀ τ (ec. 17) donde Di es el plazo temporal de la tarea τi, Deek es el plazo global de la cadena de precedencias k y Cmess es el tiempo de circulación de los mensajes. Esta asignación implica que las tareas del inicio de la cadena dispondrán de un mayor plazo, por tanto menor prioridad. Mientras que las tareas del final el plazo si las iniciales lo han usado será menor, teniendo por lo tanto mayor prioridad.  Envío de un mensaje de activación de las tareas sucesoras. A continuación, se analizará el resultado de la planificación LPEDF usando los dos ejemplos analizados anteriormente. 20 25 30 t11 t21 t12 t22 Inicio de tarea t13 t23 velocidad 1 0.5 00 5 10 15 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125 130 135 140 145 150 155 160 165 170 175 180 velocidad 1 0.5 00 5 10 15 20 25 30 35 40 45 50 55 60 65 70 75 80 85 90 95 100 105 110 115 120 125 130 135 140 145 150 155 180160 165 170 175 Figura 56: Ejecución usando la planificación LPEDF de los procesos de la Tabla 16 en un sistema distribuido con un único plazo temporal global usando offset dinámico. En la Figura 56 se ha realizado el diagrama de ejecución del conjunto de tareas de la Tabla 16. En este caso se puede observar que el sistema es planificable. El consumo energético obtenido frente a la planificación a máxima velocidad es del 87%. Dejando 27 unidades de tiempo libres. Capítulo 3 144 de 209 - igual al plazo temporal de la tarea precedente. Sin embargo este método disminuye la planificabilidad del conjunto. Nosotros hemos propuesto no repartir la totalidad del plazo global, sino que dejar cierta flexibilidad al sistema para usarlo en las tareas que realmente lo necesitan. Pero dado que los algoritmos están enfocados al ahorro energético utilizando las técnicas de DVS, se ha hecho necesaria la previsión de un tiempo de llegada de las tareas sucesoras, ya que de otra manera, las tareas que se ejecutaban no contaban con un límite temporal de ejecución, pudiendo resultar en la perdida de algún plazo. Se ha propuesto una predicción conservativa del tiempo de llegada de las tareas que garantiza el cumplimiento de los plazos ahorrando energía. Los resultados muestran que los algoritmos propuestos sin la repartición estática de los plazos, son capaces de planificar un mayor conjunto de sistemas que los que utilizan una repartición estática. Así mismo se ha observado que los planificadores basados en el Dual Priority son capaces de planificar conjuntos que no lo son utilizando los planificadores LPFPS o LPEDF. En los ejemplos que se han desarrollado, se puede observar: • Cuando el conjunto es planificable con todos los algoritmos estudiados, el algoritmo que aporta un mayor ahorro energético es el EPLDP con un 32%, seguido del PLMDP con un 21%, el LPEDF con un 13% y finalmente el LPFPS con un 10% de ahorro energético. • Existen conjuntos que únicamente son planificables con nuestros algoritmos (PLMDP, EPLDP). Con los otros algoritmos estudiados existe una perdida de un plazo temporal. • En los capítulos anteriores con sistemas monoprocesadores se ha observado que el algoritmo que aporta mayor ahorro energético es el EPLDP, con lo que estos resultados se podrían extrapolar al caso de sistemas distribuidos, como se ha observado con el conjunto evaluado. Capítulo 5 DUALIDAD ENTRE AHORRO DE ENERGÍA Y TIEMPO DE FINALIZACIÓN El objetivo de este capítulo es analizar la planificación de las tareas aperiódicas, siendo el parámetro de rendimiento usual del planificador, el tiempo de finalización medio que proporciona a estas. Se debe tener en cuenta que la idea de las técnicas del DVS de ralentizar la velocidad de ejecución de las tareas se contrapone con la idea de obtener una mayor productividad del procesador objetivo perseguido hasta la actualidad y que ha provocado parte de los grandes avances tecnológicos actuales. Dualidad entre Ahorro de Energía y Tiempo de Finalización - 147 de 209 - 5.1 Introducción Tal como se ha expuesto en el Capítulo 1, los sistemas de tiempo real usualmente están formados por tareas periódicas, tareas asociadas a eventos que tienen un comportamiento cíclico, la lectura de un sensor cada cierto intervalo de tiempo, recepción de los datos de un radar,... Sin embargo también existen componentes no periódicas, eventos externos que se activan en instantes aleatorios, como podrían ser las ordenes de un operador, las alarmas que se producen en un sistema de control,... En estos sistemas mixtos, el planificador tiene que ser capaz de integrar las tareas periódicas con las tareas aperiódicas, ofreciendo a estas últimas el menor tiempo de finalización posible. En la Figura 62 se puede observar el esquema de ejecución de las tareas periódicas y aperiódicas. Expropiación Inicialización Activación T.Periódica T.Aperiódica T. Aperiódica Finalización Ready Ejecución Tareas Suspendida Planificación Finalización T.Periódica Figura 62: Esquema de ejecución de las tareas periódicas y aperiódicas En los sistemas reales existen diversos tipos de tareas aperiódicas: • Las tareas esporádicas, aquellas tareas que tienen un plazo temporal estricto y tienen normalmente un intervalo mínimo entre las activaciones. Para este tipo de tareas, lo primordial es el cumplimiento del plazo temporal en lugar del tiempo de finalización. Estas tareas esporádicas deben garantizarse siempre y una práctica común es analizar la planificación de estas tareas como si fueran periódicas con periodo igual al mínimo intervalo de tiempo entre las activaciones. Capítulo 5 148 de 209 - • Las tareas firm aperiódicas, son tareas que también tienen un plazo temporal, pero estas tareas pueden rechazarse. Si la tarea se acepta, esta debe finalizar con anterioridad al plazo temporal. Si se rechaza, disminuye la calidad de servicio del sistema. • Las tareas aperiódicas, estas tareas se aceptan siempre y no disponen de plazo temporal estricto, como máximo pueden tenerlo flexible. Para este tipo de tareas, lo importante es el tiempo finalización medio. En este capítulo se analizaran únicamente las tareas aperiódicas sin plazo temporal, sin entrar en el tratamiento de los demás tipos. Para ello, se comentaran qué planificadores específicos para el tratamiento de las tareas aperiódicas existen, analizando los tres mejores de ellos (uno de prioridad estática, uno de prioridades dinámicas y uno mixto). A continuación se realizará el estudio de la planificación de las tareas aperiódicas en los planificadores utilizados en la presente tesis. Para finalizar con la unión de la planificación de las tareas aperiódicas junto al ahorro energético y se finalizará el capítulo con las conclusiones obtenidas. 5.2 Planificación de las tareas aperiódicas En la planificación estática, la manera más simple de planificar las tareas aperiódicas sin interferir en la planificación de las tareas periódicas es asignándoles una prioridad inferior a estas y igual a todas ellas, utilizando un esquema FIFO entre todas las tareas aperiódicas, de manera que la carga aperiódica únicamente se ejecutaran cuando no exista carga periódica. Este esquema de planificación se denomina background, y el tiempo de finalización que obtienen las tareas aperiódicas es demasiado grande, de manera que este tiempo de finalización se podría considerar como una cota superior, cualquier esquema de planificación que se use, tiene que mejorar el tiempo de finalización de este tipo de tareas. Una mejora de estos métodos consiste en el uso de los servidores [42]. Estos servidores son tareas periódicas artificiales que disponen de una capacidad de cálculo y que cuando les toca ejecutarse, ejecutan la carga aperiódica en su lugar, de manera que se puede asegurar que no interferirán con la ejecución de las tareas periódicas, pero ofrecerán un mejor tiempo de finalización a las tareas aperiódicas. Cuando se ejecuta carga aperiódica la Dualidad entre Ahorro de Energía y Tiempo de Finalización - 149 de 209 - capacidad se va utilizando. Esta capacidad se rellenará al máximo al inicio de cada periodo de la tarea servidora. Existen varias clases de servidores según el relleno y uso de la capacidad, el primero que apareció y el mas sencillo es el “polling server” (PS). Es una tarea periódica con un tiempo de cálculo, un periodo y con la mayor prioridad del sistema. Al ejecutarse mira en la cola de aperiódicas si existe trabajo aperiódico, si existe, se ejecuta durante el tiempo de cálculo asignado al servidor, si no existe el servidor se suspende hasta el siguiente periodo, perdiendo la capacidad no utilizada. El problema de este servidor, es que si la tarea aperiódica llega inmediatamente después de la activación del servidor, esta debe esperarse a la siguiente activación, aunque la capacidad del servidor no halla sido utilizada. Los servidores que conservan la capacidad no utilizada son los llamados servidores que preservan la capacidad (bandwidthperserving servers), entre ellos se hallan los Deferrable servers, los Sporadic server, los Constant utilization servers, los Total bandwidth servers, losWeighted fair queuing servers, etc. El “Deferrable Server” (DS) (Servidor diferido) [42] es el más simple de implementar de todos los servidores que preservan la capacidad, en el se define un periodo y una capacidad. Estos valores son los máximos posibles que continúan ofreciendo planificabilidad a las tareas periódicas. El funcionamiento de este servidor es el siguiente: En tiempo de ejecución cuando llega una tarea aperiódica si existe capacidad disponible, empieza a ejecutarse inmediatamente y continua hasta que finaliza o se agota la capacidad del servidor. La capacidad del servidor se decrementa conforme se ejecutan las tareas aperiódicas. Si se agota la capacidad del servidor, se suspende la tarea aperiódica o se envía en background. Cada periodo de tiempo se rellena la capacidad del servidor. Si en el instante de activación del servidor no existen tareas aperiódicas, la capacidad del servidor no se pierde si no que se mantiene durante todo el periodo del servidor. El “Sporadic Server” (SS) (Servidor esporádico) [42] se diferencia del anterior en el relleno de la capacidad. Si un proceso en el instante t utiliza una capacidad C, el servidor rellenará esta capacidad C después de T unidades de tiempo. En general, el SS proporciona una capacidad mayor que el DS, pero tiene una implementación más costosa. Capítulo 5 150 de 209 - Hay otros métodos que no utilizan servidores para planificar tareas aperiódicas, estos serian el “Slack Stealing” [44], [22] que Tia et al. demostró que no era óptimo [82] y el “Dual Priority” (Anexo 2) entre otros. Todos estos algoritmos están basados en la idea de robar todo el tiempo posible a las tareas periódicas, sin causarles ninguna perdida de plazos temporales retardando la ejecución de las tareas periódicas al máximo para obtener un buen tiempo de finalización a las tareas aperiódicas [21]. Lo que varía de un algoritmo a otro es la forma de calcular el retardo de las tareas periódicas. El “Slack Stealing” (Extractor de holgura) aprovecha el slack (tiempo disponible entre la finalización de una tarea y el plazo temporal) moviéndolo antes de la ejecución de la tarea periódica. Este algoritmo requiere tener computado de manera exacta todos los intervalos libres que dejan las tareas periódicas a lo largo del hiperperiodo, de manera que la planificación requiere del uso de tablas muy grandes (longitud del hiperperiodo) o calcular los intervalos libres en tiempo de ejecución (sobrecarga del procesador). El planificador “Dual Priority” (Prioridad dual) (Anexo 2), obtiene tiempos de finalización parecidos al “Slack Stealing”, sin tener la sobrecarga de memoria ni de cálculo [54]. En este caso, las tareas aperiódicas se ejecutan en un nivel de prioridad intermedio, de manera que ante la presencia de tareas aperiódicas únicamente se ejecutaran aquellas tareas periódicas que han promocionado, es decir, aquellas tareas que no pueden retardarse mas. En [54] se realiza una modificación del Dual Priority para mejorar el tiempo de finalización de las aperiódicas. La modificación consiste en tener en cuenta el tiempo que las tareas periódicas se han ejecutado antes de ser promocionadas. Este tiempo ejecutado en el nivel inferior de prioridad puede ser usado por las tareas aperiódicas hasta la llegada del plazo de la tarea. Spuri and Buttazzo en [79] presenta unos algoritmos óptimos para prioridades dinámicas usando el planificador EDF de base. Presenta el “Earliest Deadline Last” (EDL) y el “Improve Priority Exchange” (IPE) que es una aproximación de éste último. Este algoritmo asigna las prioridades usando EDL y calcula el tiempo que queda libre el procesador, el instante en que se produce este hueco y la longitud del mismo y lo almacena en un vector. Si en el instante que hay hueco no existe ninguna aperiódica, se ejecuta una tarea periódica de menor prioridad, intercambiando su Dualidad entre Ahorro de Energía y Tiempo de Finalización - 151 de 209 - prioridad con la del servidor, de esta manera, el hueco no se pierde y queda disponible para la llegada de tareas aperiódicas. A continuación se compararan el Background, el Dual Priority, el Slack Stealing, y el Improve Priority Exchange, a nivel de tiempo de finalización que se obtiene de las tareas aperiódicas en los distintos casos. El hecho que únicamente se compare con estos algoritmos es debido a que estos son los considerados mejores con asignación de prioridades estática (SS), el mejor con asignación de prioridades dinámicas (IPE) y el Dual Priority que es nuestro algoritmo base. En las simulaciones se han generado conjuntos de tareas con una utilización periódica y aperiódica escogidas aleatoriamente de la siguiente manera: o Número de tareas periódicas entre 4 y 10. o Periodos entre 5 y 500. o Tiempo de cálculo escogidos aleatoriamente para que las tareas sean planificables. o La llegada de las tareas aperiódicas sigue una distribución de Poisson y su requerimiento de cálculo varia entre 1 y 500. o Finalmente, se ha variado la utilización del procesador del 70% al 95 %, descartando los conjuntos con una diferencia de utilización mayor al 1% de la utilización demandada. La manera de variar la utilización del procesador dependerá del experimento realizado. Todas las simulaciones se han realizado hasta la finalización de 100.000 tareas aperiódicas. Cada conjunto se ha simulado varias veces hasta obtener un tiempo de finalización medio con un intervalo de confianza del 95%. En la Figura 63, se ha simulado 100 conjuntos de tareas aleatorias variando la utilización periódica entre un 60 y un 80%. En todos ellos se ha fijado una utilización aperiódica del 20%. Los puntos representados en el gráfico es la media aritmética del tiempo medio de finalización de las tareas aperiódicas dividido por el tiempo de ejecución de las tareas aperiódicas en cada conjunto. Capítulo 5 152 de 209 - 20% Utilización Aperiódica 0 2 4 6 8 10 12 14 16 18 20 22 24 26 28 60% 70% 75% 80% Porcentaje de utilización periódica Tiempo de respuesta medio BKG DPA SSA IPE Figura 63: Tiempo de finalización medio variando la utilización periódica del procesador. En la Figura 63, se puede observar que conforme la carga periódica aumenta, el Dual priority (DPA) y el Improve Priority Exchange (IPE) obtienen mejores resultados medios que el Slack Stealing (SSA). Esto es debido a que las prioridades dinámicas de las tareas permiten una mayor flexibilidad para permitir la ejecución de las tareas aperiódicas. En la siguiente simulación se ha variado el tiempo de ejecución de las tareas aperiódicas fijándolas a 1. La utilización aperiódica de cada conjunto se ha variado entre un 20 y un 33%. La utilización periódica se ha fijado a un 60%. 60% Utilización Periódica 0 2 4 6 8 10 12 14 16 18 20 22 24 26 20% 25% 33% Porcentaje de utilización aperiódica Tiempo de respuesta medio BKG DPA SSA IPE Figura 64: Tiempo de finalización medio variando la utilización aperiódica del procesador. Dualidad entre Ahorro de Energía y Tiempo de Finalización - 153 de 209 - En la Figura 64 se puede observar que con utilizaciones periódicas bajas del procesador el Improve Priority Exchange (IPE) y el Dual Priority (DPA) tienen el mismo comportamiento a nivel de tiempo de finalización de la tareas aperiódicas, mientras que el Slack Stealing (SS) mejora un poco. Observando los resultados obtenidos anteriormente, se puede concluir que el planificador más adecuado para el tratamiento de las tareas aperiódicas y ahorro energético es el Dual Priority dado que los tiempos de finalización que obtienen las tareas aperiódicas son aceptables siendo además el planificador con una menor sobrecarga de implementación y de utilización de memoria. En el siguiente punto se realizará el estudio combinado de ahorro energético combinado con el tratamiento de las tareas aperiódicas. 5.3 Tareas aperiódicas y ahorro energético Si se observa el comportamiento de las tareas periódicas cuando se usan los algoritmos de planificación orientados al tratamiento de las tareas aperiódicas, y se comparará con el comportamiento de este mismo tipo de tareas usando los algoritmos de planificación con ahorro energético que usan las técnicas del DVS, se observa lo siguiente:  La planificación de tareas background es equivalente a la planificación con ahorro energético LPFPS, se reduce la velocidad del procesador cuando existe una única tarea lista para ser ejecutada. En el caso de la planificación background, las tareas aperiódicas se ejecutaran únicamente cuando no hay ninguna tarea periódica lista para ser ejecutada. Si se traduce a la planificación con ahorro energético, la última tarea periódica reducirá la velocidad del procesador, que sería el momento en que se ejecutarían las tareas aperiódicas activas en el sistema.  La planificación de tareas aperiódicas que se obtiene usando el algoritmo del Dual Priority el tiempo de finalización de las tareas es mejor que el que se obtiene con el algoritmo background. Las tareas aperiódicas se ejecutaran cuando no existan tareas periódicas en la cola de mayor prioridad, momento en el que el PLMDP reduce la velocidad de ejecución de las tareas del