Parametric specification of dynamic memory utilization

Download: PDF.

“Parametric specification of dynamic memory utilization” by Diego Garbervetsky. Ph.D. dissertation, Univ. of Buenos Aires, (Buenos Aires, Argentina), Nov. 2007.

Abstract

Current trends in the embedded and real-time software industry are leading towards the use of object-oriented programming languages such as Java. From the software engineering perspective, one of the most attractive issues in object-oriented design is the encapsulation of abstractions into objects that communicate through clearly defined interfaces.

However, in order to be able to successfully adopt languages with object oriented features like Java in embedded and real-time systems, is necessary to solve at least two problems: eliminate execution unpredictability due to garbage collection and automatically analyze memory requirements.

There has been some work trying to deal with the first problem but the problem of computing memory requirements is still challenging. In this thesis we present our approach to tackle both problems by presenting solutions towards more predictable memory management and predicting memory requirements. The effort is mainly focused in the latter problem as we found it hard, less explored, strongly relevant for all kinds of embedded systems and its applicability and usefulness is beyond real-time applications.

This thesis presents a series of techniques to automatically compute dynamic memory utilization certificates. We start by computing a technique that produces parametric specifications of memory allocations without consider any memory reclaiming mechanism. Then, we approximate object lifetime using escape analysis and synthesize a scoped-based memory organization where object are organized in regions that can be collected as a whole. We propose a technique to automatically translate conventional Java code into code that safely adopts this memory management mechanism. Under this new setting we infer parametric specifications of the size of each memory regions. Finally, we predict the minimum amount of dynamic memory required to run a method (or program) in the context of scoped memory management by computing parametric specifications of the size of memory regions and by modeling the potential configurations of the regions in run time.

We develop a prototype tool that implemented the complete chain of techniques and allow us to experimentally evaluate the efficiency and accuracy of the method on several Java benchmarks. The results are very encouraging.

Download: PDF.

BibTeX entry:

@phdthesis{Garbervetsky2007,
   author = {Diego Garbervetsky},
   title = {Parametric specification of dynamic memory utilization},
   school = {Univ. of Buenos Aires},
   type = {{Ph.D.}},
   address = {Buenos Aires, Argentina},
   month = nov,
   year = {2007}
}

Back to Publications whose methodology uses invariant detection.