Tiempo de ejecución en el peor de los casos: Worst-case execution time

El tiempo de ejecución en el peor de los casos ( WCET ) de una tarea computacional es el tiempo máximo que la tarea podría tardar en ejecutarse en una plataforma de hardware específica .

Para que se utiliza

El tiempo de ejecución en el peor de los casos se usa normalmente en sistemas confiables en tiempo real , donde comprender el comportamiento del software en el peor de los casos es importante para la confiabilidad o el comportamiento funcional correcto.

Por ejemplo, un sistema informático que controla el comportamiento de un motor en un vehículo puede necesitar responder a las entradas dentro de un período de tiempo específico. Un componente que constituye el tiempo de respuesta es el tiempo empleado en ejecutar el software; por lo tanto, si se puede determinar el tiempo de ejecución del software en el peor de los casos, el diseñador del sistema puede usarlo con otras técnicas, como el análisis de la capacidad de programación, para garantizar que el sistema responda. suficientemente rapido.

Si bien WCET es potencialmente aplicable a muchos sistemas en tiempo real, en la práctica, una garantía de WCET se usa principalmente en sistemas en tiempo real que están relacionados con alta confiabilidad o seguridad. Por ejemplo, en el software aéreo se requiere cierta atención al software en la sección 6.3.4 de DO178B . El uso cada vez mayor de software en sistemas automotrices también está impulsando la necesidad de utilizar el análisis WCET de software.

En el diseño de algunos sistemas, WCET se utiliza a menudo como una entrada para el análisis de planificación , aunque un uso mucho más común de WCET en sistemas críticos es asegurar que los presupuestos de tiempo preasignados en un sistema programado por partición como ARINC 653 son no violado.

Cálculo

Desde los primeros días de la informática integrada, los desarrolladores de software integrado han utilizado:

  • Mediciones de código de extremo a extremo, por ejemplo, realizadas estableciendo un pin de E / S en el dispositivo en alto al comienzo de la tarea y en bajo al final de la tarea y usando un analizador lógico para medir el pulso más largo. ancho, o midiendo dentro del software mismo usando el reloj del procesador o el recuento de instrucciones.
  • técnicas manuales de análisis estático, como contar las instrucciones del ensamblador para cada función, bucle, etc. y luego combinarlas.

Ambas técnicas tienen limitaciones. Las mediciones de un extremo a otro suponen una gran carga para las pruebas de software para lograr el camino más largo; Las instrucciones de conteo solo se aplican a software y hardware simples. En ambos casos, a menudo se utiliza un margen de error para tener en cuenta el código no probado, las aproximaciones de rendimiento del hardware o los errores. A menudo se utiliza un margen del 20%, aunque se utiliza muy poca justificación para esta cifra, salvo por la confianza histórica ("funcionó la última vez").

A medida que el software y el hardware han aumentado en complejidad, han impulsado la necesidad de soporte de herramientas. La complejidad se está convirtiendo cada vez más en un problema tanto en el análisis estático como en las mediciones. Es difícil juzgar qué tan amplio debe ser el margen de error y qué tan bien probado está el sistema de software. Los argumentos de seguridad del sistema basados ​​en un alto nivel alcanzado durante las pruebas se utilizan ampliamente, pero se vuelven más difíciles de justificar a medida que el software y el hardware se vuelven menos predecibles.

En el futuro, es probable que un requisito para los sistemas críticos para la seguridad sea que se analicen utilizando enfoques tanto estáticos como basados ​​en mediciones.

Consideraciones

El problema de encontrar WCET por análisis es equivalente al problema de la detención y, por lo tanto, no se puede resolver en general. Afortunadamente, para el tipo de sistemas para los que los ingenieros suelen buscar WCET, el software suele estar bien estructurado, siempre terminará y se puede analizar.

La mayoría de los métodos para encontrar un WCET implican aproximaciones (generalmente un redondeo hacia arriba cuando hay incertidumbres) y, por lo tanto, en la práctica, el WCET exacto en sí mismo a menudo se considera inalcanzable. En cambio, diferentes técnicas para encontrar el WCET producen estimaciones para el WCET. Esas estimaciones son típicamente pesimistas, lo que significa que se sabe que el WCET estimado es más alto que el WCET real (que suele ser lo que se desea). Gran parte del trabajo en el análisis WCET se centra en reducir el pesimismo en el análisis para que el valor estimado sea lo suficientemente bajo como para ser valioso para el diseñador del sistema.

El análisis WCET generalmente se refiere al tiempo de ejecución de un solo hilo, tarea o proceso. Sin embargo, en hardware moderno, especialmente multi-core, otras tareas en el sistema afectarán el WCET de una tarea dada si comparten caché, líneas de memoria y otras características de hardware. Además, los eventos de programación de tareas, como el bloqueo o las interrupciones, deben considerarse en el análisis de WCET si pueden ocurrir en un sistema en particular. Por lo tanto, es importante considerar el contexto en el que se aplica el análisis WCET.

Enfoques automatizados

Hay muchos enfoques automatizados para calcular WCET más allá de las técnicas manuales anteriores. Éstos incluyen:

  • técnicas analíticas para mejorar los casos de prueba para aumentar la confianza en las mediciones de un extremo a otro
  • análisis estático del software (significa "estático" sin ejecutar el software).
  • enfoques combinados, a menudo denominados análisis "híbridos", que son una combinación de mediciones y análisis estructural

Técnicas de análisis estático

Una herramienta WCET estática intenta estimar WCET examinando el software de la computadora sin ejecutarlo directamente en el hardware. Las técnicas de análisis estático han dominado la investigación en el área desde finales de la década de 1980, aunque en un entorno industrial, los métodos de medición de extremo a extremo eran la práctica estándar.

Las herramientas de análisis estático funcionan a un alto nivel para determinar la estructura de la tarea de un programa , ya sea en un fragmento de código fuente o en un ejecutable binario desensamblado . También funcionan a bajo nivel, utilizando información de tiempo sobre el hardware real en el que se ejecutará la tarea, con todas sus características específicas. Al combinar esos dos tipos de análisis, la herramienta intenta dar un límite superior al tiempo requerido para ejecutar una tarea determinada en una plataforma de hardware determinada.

En el nivel bajo, el análisis WCET estático se complica por la presencia de características arquitectónicas que mejoran el rendimiento de caso promedio del procesador : cachés de instrucciones / datos , predicción de ramas y canalizaciones de instrucciones , por ejemplo. Es posible, pero cada vez más difícil, determinar límites estrechos de WCET si estas características arquitectónicas modernas se tienen en cuenta en el modelo de tiempo utilizado por el análisis.

Las autoridades de certificación como la Agencia Europea de Seguridad Aérea , por lo tanto, confían en las suites de validación de modelos.

El análisis estático ha dado buenos resultados para hardware más simple, sin embargo, una posible limitación del análisis estático es que el hardware (la CPU en particular) ha alcanzado una complejidad que es extremadamente difícil de modelar. En particular, el proceso de modelado puede introducir errores de varias fuentes: errores en el diseño del chip, falta de documentación, errores en la documentación, errores en la creación del modelo; todo ello conduce a casos en los que el modelo predice un comportamiento diferente al observado en hardware real. Normalmente, cuando no es posible predecir con precisión un comportamiento, se utiliza un resultado pesimista, lo que puede llevar a que la estimación de WCET sea mucho mayor que cualquier cosa lograda en tiempo de ejecución.

Obtener una estimación WCET estática ajustada es particularmente difícil en procesadores de múltiples núcleos.

Hay una serie de herramientas comerciales y académicas que implementan diversas formas de análisis estático.

Técnicas de medición e híbridas

Los enfoques híbridos y basados ​​en mediciones generalmente intentan medir los tiempos de ejecución de segmentos de código corto en el hardware real, que luego se combinan en un análisis de nivel superior. Las herramientas tienen en cuenta la estructura del software (por ejemplo, bucles, ramas), para producir una estimación del WCET del programa más grande. La razón es que es difícil probar la ruta más larga en software complejo, pero es más fácil probar la ruta más larga en muchos componentes más pequeños. El efecto del peor de los casos solo debe verse una vez durante la prueba para que el análisis pueda combinarlo con otros eventos del peor de los casos en su análisis.

Por lo general, las pequeñas secciones de software se pueden medir automáticamente utilizando técnicas como la instrumentación (agregando marcadores al software) o con soporte de hardware como depuradores y módulos de seguimiento de hardware de CPU. Estos marcadores dan como resultado un rastro de ejecución, que incluye tanto la ruta tomada a través del programa como el momento en que se ejecutaron los diferentes puntos. Luego, se analiza la traza para determinar el tiempo máximo que cada parte del programa ha tardado en ejecutarse, cuál es el tiempo máximo de iteración observado de cada bucle y si hay partes del software que no se han probado ( cobertura de código ).

El análisis WCET basado en mediciones ha dado buenos resultados tanto para hardware simple como complejo, aunque, al igual que el análisis estático, puede sufrir un pesimismo excesivo en situaciones de múltiples núcleos, donde el impacto de un núcleo sobre otro es difícil de definir. Una limitación de la medición es que se basa en observar los efectos del peor de los casos durante la prueba (aunque no necesariamente al mismo tiempo). Puede ser difícil determinar si los efectos del peor de los casos se han probado necesariamente.

Hay una serie de herramientas comerciales y académicas que implementan diversas formas de análisis basado en mediciones.

Investigar

Los grupos de investigación más activos se encuentran en Suecia (Mälardalen, Linköping), Alemania (Saarbrücken, Dortmund, Braunschweig), Francia (Toulouse, Saclay, Rennes), Austria (Viena), Reino Unido (Universidad de York y Rapita Systems Ltd), Italia ( Bolonia), España (Cantabria, Valencia) y Suiza (Zúrich). Recientemente, el tema del análisis de tiempo a nivel de código ha recibido más atención fuera de Europa por grupos de investigación en los EE. UU. (Carolina del Norte, Florida), Canadá, Australia, Bangladesh (MBI LAB y RDS), Reino de Arabia Saudita-UQU (HISE LAB) y Singapur.

Desafío de herramientas WCET

El primer Desafío de Herramientas WCET internacional tuvo lugar durante el otoño de 2006. Fue organizado por la Universidad de Mälardalen y patrocinado por la Red de Excelencia ARTIST2 en Diseño de Sistemas Embebidos. El objetivo del Desafío era inspeccionar y comparar diferentes enfoques para analizar el tiempo de ejecución del peor de los casos. Se han participado todas las herramientas y prototipos disponibles capaces de determinar límites superiores seguros para el WCET de tareas. Los resultados finales se presentaron en noviembre de 2006 en el Simposio Internacional ISoLA 2006 en Paphos , Chipre.

Un segundo desafío tuvo lugar en 2008.

Ver también

Referencias

  1. ^ " El problema del tiempo de ejecución del peor de los casos: descripción general de los métodos y estudio de las herramientas ", Wilhelm, Reinhard, et al., ACM Transactions on Embedded Computing Systems (TECS), vol. 7, N ° 3, 2008.
  2. ^ "Copia archivada" (PDF) . Archivado desde el original (PDF) el 2011-10-01 . Consultado el 15 de agosto de 2010 .Mantenimiento de CS1: copia archivada como título ( enlace )
  3. ^ "Copia archivada" . Archivado desde el original el 16 de febrero de 2012 . Consultado el 16 de agosto de 2008 .Mantenimiento de CS1: copia archivada como título ( enlace )

Artículos y libros blancos

enlaces externos