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.
El tiempo de ejecución en el peor de los casos se utiliza 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 podría necesitar responder a entradas dentro de un período de tiempo específico. Un componente que constituye el tiempo de respuesta es el tiempo dedicado a ejecutar el software; por lo tanto, si se puede determinar el tiempo de ejecución del peor caso del software, entonces el diseñador del sistema puede usarlo con otras técnicas, como el análisis de programabilidad, para garantizar que el sistema responda. suficientemente rapido.
Si bien WCET es potencialmente aplicable a muchos sistemas en tiempo real, en la práctica la garantía de WCET se utiliza principalmente en sistemas en tiempo real relacionados con una alta confiabilidad o seguridad. Por ejemplo, en el software aerotransportado se requiere cierta atención al software en la sección 6.3.4 de DO178C . El uso cada vez mayor de software en sistemas automotrices también está impulsando la necesidad de utilizar el análisis de software WCET.
En el diseño de algunos sistemas, WCET se utiliza a menudo como entrada para el análisis de programabilidad , aunque un uso mucho más común de WCET en sistemas críticos es garantizar que los presupuestos de tiempo preasignados en un sistema de partición programada como ARINC 653 sean no violado.
Desde los primeros días de la informática integrada, los desarrolladores de software integrado han utilizado:
Ambas técnicas tienen limitaciones. Las mediciones de extremo a extremo imponen una gran carga a las pruebas de software para lograr el camino más largo; Las instrucciones de conteo solo son aplicables 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 hay muy poca justificación para esta cifra, salvo 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 como en las mediciones estáticas. 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 nivel máximo 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. [ cita necesaria ]
El problema de encontrar WCET mediante análisis es equivalente al problema de la detención y, por lo tanto, no tiene solución en general. Afortunadamente, para el tipo de sistemas para los que los ingenieros normalmente quieren encontrar WCET, el software suele estar bien estructurado, siempre terminará y es analizable.
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 a menudo se considera inalcanzable. En cambio, diferentes técnicas para encontrar el WCET producen estimaciones para el WCET. [1] Esas estimaciones suelen ser 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 subproceso, tarea o proceso. Sin embargo, en el hardware moderno, especialmente el multinúcleo, otras tareas del sistema afectarán el WCET de una tarea determinada si comparten caché, líneas de memoria y otras características del hardware. Además, los eventos de programación de tareas, como bloqueos o interrupciones, deben considerarse en el análisis 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.
Existen muchos enfoques automatizados para calcular WCET más allá de las técnicas manuales mencionadas anteriormente. Éstas incluyen:
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 alto nivel para determinar la estructura de la tarea de un programa , trabajando 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 necesario 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 promedio del procesador : cachés de instrucciones/datos , predicción de bifurcaciones y canales de instrucciones , por ejemplo. Es posible, aunque cada vez más difícil, determinar límites estrictos de WCET si estas características arquitectónicas modernas se tienen en cuenta en el modelo de temporización utilizado en el análisis.
Por lo tanto, las autoridades de certificación como la Agencia Europea de Seguridad Aérea confían en conjuntos de validación de modelos. [ cita necesaria ]
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 conduce a casos en los que el modelo predice un comportamiento diferente al observado en el 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 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 multinúcleo.
Existe una serie de herramientas comerciales y académicas que implementan diversas formas de análisis estático.
Los enfoques híbridos y basados en mediciones suelen intentar medir los tiempos de ejecución de segmentos de código cortos 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 amplio. 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 del mismo. Un efecto del peor de los casos solo necesita 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.
Normalmente, las pequeñas secciones de software se pueden medir automáticamente mediante técnicas como instrumentación (agregar 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 el camino recorrido por el programa como el momento en el que se ejecutaron los diferentes puntos. Luego, el seguimiento se analiza 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 están probadas ( 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 peores efectos durante las pruebas (aunque no necesariamente al mismo tiempo). Puede resultar difícil determinar si necesariamente se han probado los efectos del peor de los casos.
Existe una serie de herramientas comerciales y académicas que implementan diversas formas de análisis basado en mediciones.
Los grupos de investigación más activos se encuentran en EE.UU. (American Michigan University), 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 (Zurich). Recientemente, el tema del análisis de temporización a nivel de código ha recibido más atención fuera de Europa por parte de grupos de investigación en EE. UU. (Carolina del Norte, Florida), Canadá, Australia, Bangladesh (MBI LAB y RDS), Reino de Arabia Saudita-UQU (HISE LAB), Singapur e India (IIT Madras, IISc Bangalore).
El primer WCET Tool Challenge 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 en el peor de los casos. Han participado todas las herramientas y prototipos disponibles capaces de determinar límites superiores seguros para las tareas del WCET. Los resultados finales [2] se presentaron en noviembre de 2006 en el Simposio Internacional ISoLA 2006 en Paphos , Chipre.
En 2008 se llevó a cabo un segundo Desafío. [3]
{{cite web}}: Mantenimiento CS1: copia archivada como título ( enlace )