[ main page ] [ back ]

2009 : Worst-Case Execution Time Analysis for Real-Time Java

Author(s)
Benedikt Huber
Abstract
Real-time systems are applications which have to meet time constraints, ensuring that periodic tasks are scheduled in time, and events are handled within a permitted delay. In order to show that the system behaves correctly, it is necessary to verify that tasks complete within a given time span. Worst Case Execution Time (WCET) analysis, the static prediction of the time needed to execute a task, therefore plays a central role for safety-critical real-time systems. In this thesis, we discuss the WCET analysis of real-time Java applications, and present a tool analyzing task executed on the Java Optimized Processor (JOP). JOP is an implementation of the Java Virtual Machine in hardware, and uses a cache fetching all instructions of a method at once, which needs to be taken into account. Two techniques for calculating a WCET bound have been implemented, the Implicit Path Enumeration Technique (IPET), translating the calculation to a maximum cost circulation problem, and a dynamic approach using the timed automata model checker uppaal. The model checking based approach is computationally more expensive, but capable of modeling timings which depend on the execution history, and therefore has the potential to yield more accurate WCET bounds than the static IPET method. JOPís variable block method cache was included in both timing models, reducing the gap between the actual and the calculated WCET. Both approaches have been integrated in the analysis tool, and we are thus able to directly compare analysis times and the quality of the calculated WCET bound. Experimental results indicate that timed automata model checking using uppaal is at least suitable for the analysis of single methods and smaller tasks, although large loop bounds lead to a significant increase of the time needed for the analysis. IPET on the other hand scales very well, but delivered slightly worse results for the cache approximation. As the model checking approach is not established yet, there seem to be plenty of opportunities for optimizations and new applications, leaving room for future research. i
Bibtex
@mastersthesis{ huber:2009,
  author =      "Benedikt Huber",
  title =       "Worst-Case Execution Time Analysis for Real-Time Java",
  address =     "Treitlstr. 3/3/182-1, 1040 Vienna, Austria",
  school =      "Technische Universit{\"a}t Wien, Institut f{\"u}r Technische Informatik",
  year =        "2009"
}
Download
Get wcet_thesis.pdf - Adobe PDF-format, (1051.9092 KB; posted at July 09 2013)


[ main page ] [ back ]