Predicting Time and Memory Demands of Object-Oriented Programs

Embedded computer systems are subject to a multitude of requirements. These include real-time requirements, that is, such computers must respond to external events within limited time. Many systems, such as satellites and telephone switches, must also operate unattended for long periods of time. They must not fail due to defective software. Modern object-oriented programming languages, particularly Java, offer type safety, automatic memory management (garbage collection), dynamic loading of code, and object-oriented abstraction mechanisms. All these features, designed to increase software quality and flexibility, are highly desirable in embedded systems. Yet object-oriented languages are often avoided in such applications. One reason for this is that previous techniques for worst-case execution time (WCET) predictions are unsuitable for object-oriented languages. WCET predictions are necessary to guarantee fulfilment of real-time requirements. We present techniques for predicting the WCET of programs in object-oriented languages. We also show how to predict the amount of memory required by an object-oriented program; such information is required for safe scheduling of real-time garbage collection. The techniques are mainly automatic (assisted by manual annotations) and benefit from integration with a compiler. They are being implemented in an interactive development environment for a subset of the Java programming language. The presented techniques make object-oriented programming languages with garbage collection more predictable and thus more appropriate for hard real-time systems. The declarative implementation technique (reference attributed grammars) facilitates a clear and concise implementation suitable for our interactive environment. This interactivity allows timing problems, requiring revision of design or requirements, to be detected early