[Back]


Diploma and Master Theses (authored and supervised):

B. Huber:
"Worst-Case Execution Time Analysis for Real-Time Java";
Supervisor: H. Grünbacher, M. Schoeberl; Institut für Technische Informatik - E182, 2009.



English 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

Created from the Publication Database of the Vienna University of Technology.