El tiempo de ejecución en el peor de los casos ( WCET ) de una tarea computacional es el tiempo máximo que podría tardar la tarea 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 temporal 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 las entradas en un tiempo específico. Un componente que compone 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 utilizarlo con otras técnicas, como el análisis de capacidad de programación, para garantizar que el sistema responda con la suficiente rapidez.
Si bien la WCET es potencialmente aplicable a muchos sistemas en tiempo real, en la práctica, la garantía de la WCET se utiliza principalmente en sistemas en tiempo real relacionados con la alta confiabilidad o seguridad. Por ejemplo, en el software a bordo se requiere cierta atención al software según la sección 6.3.4 de la DO178C . El uso creciente de software en sistemas automotrices también está impulsando la necesidad de utilizar el análisis WCET del software.
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 no se violen los presupuestos de tiempo preasignados en un sistema programado por particiones como ARINC 653 .
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 la ruta más larga; el conteo de instrucciones solo es aplicable 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 al rendimiento del hardware o los errores. A menudo se utiliza un margen del 20%, aunque hay 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 contar con herramientas de apoyo. 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 cuán amplio debe ser el margen de error y cuán bien probado está el sistema de software. Los argumentos de seguridad del sistema basados en un punto de referencia alcanzado durante la prueba 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 de seguridad sea que se analicen utilizando enfoques tanto estáticos como basados en mediciones. [ cita requerida ]
El problema de encontrar WCET mediante análisis es equivalente al problema de detención y, por lo tanto, no es solucionable en general. Afortunadamente, para el tipo de sistemas para los que los ingenieros suelen querer encontrar WCET, el software suele estar bien estructurado, siempre terminará y es analizable.
La mayoría de los métodos para hallar el WCET implican aproximaciones (normalmente un redondeo hacia arriba cuando hay incertidumbres) y, por lo tanto, en la práctica, el WCET exacto suele considerarse imposible de obtener. En cambio, diferentes técnicas para hallar el WCET producen estimaciones del WCET. [1] Esas estimaciones suelen ser pesimistas, lo que significa que se sabe que el WCET estimado es mayor que el WCET real (que es normalmente lo que se desea). Gran parte del trabajo sobre el análisis del WCET se centra en reducir el pesimismo en el análisis para que el valor estimado sea lo suficientemente bajo como para que sea valioso para el diseñador del sistema.
El análisis WCET generalmente se refiere al tiempo de ejecución de un único subproceso, tarea o proceso. Sin embargo, en el hardware moderno, especialmente en el de múltiples núcleos, 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 métodos automatizados para calcular el WCET además de las técnicas manuales mencionadas anteriormente. Entre ellos se incluyen:
Una herramienta estática de WCET intenta estimar el 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 fines de la década de 1980, aunque en un entorno industrial, los enfoques 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 trabajando en un fragmento de código fuente o en un ejecutable binario desensamblado . También funcionan a un 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 estático de WCET 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 saltos y secuencias de instrucciones , por ejemplo. Es posible, pero cada vez más difícil, determinar límites estrictos de WCET si se tienen en cuenta estas características arquitectónicas modernas en el modelo de temporización utilizado por el análisis.
Por lo tanto, las autoridades de certificación, como la Agencia Europea de Seguridad Aérea , confían en conjuntos de herramientas de validación de modelos. [ cita requerida ]
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 lo cual conduce a casos en los que el modelo predice un comportamiento diferente al observado en el hardware real. Por lo general, 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 multinúcleo.
Hay una serie de herramientas comerciales y académicas que implementan diversas formas de análisis estático.
Los enfoques basados en mediciones e híbridos generalmente intentan 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 grande. La razón es que es difícil probar la ruta más larga en un 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 caso solo necesita verse una vez durante la prueba para que el análisis pueda combinarlo con otros eventos del peor caso 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 (añadiendo marcadores al software) o con soporte de hardware como depuradores y módulos de rastreo de hardware de CPU. Estos marcadores dan como resultado un rastro de ejecución, que incluye tanto el camino recorrido a través del programa como el tiempo en el que se ejecutaron los diferentes puntos. Luego, el rastro 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 se hayan 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 verse afectado por 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 la observación de los efectos del peor caso durante las pruebas (aunque no necesariamente al mismo tiempo). Puede resultar difícil determinar si los efectos del peor caso se han probado necesariamente.
Hay 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 (University of York y Rapita Systems Ltd), Italia (Bolonia), España (Cantabria, Valencia) y Suiza (Zúrich). Recientemente, el tema del análisis de tiempos a nivel de código ha encontrado 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 Integrados. El objetivo del desafío era inspeccionar y comparar diferentes enfoques para analizar el tiempo de ejecución en el peor de los casos. Participaron todas las herramientas y prototipos disponibles capaces de determinar límites superiores seguros para el WCET de las tareas. Los resultados finales [2] se presentaron en noviembre de 2006 en el Simposio Internacional ISoLA 2006 en Paphos , Chipre.
En 2008 tuvo lugar un segundo Desafío. [3]
{{cite web}}: CS1 maint: copia archivada como título ( enlace )