Probabilistic analysis of heap fragmentation
in Java-programs

M.Sc. Thesis project (Ex-jobb) proposal

March 24, 2009

Background

If a heap is occupied by a spatially scattered large number of small live objects the heap is said to be fragmented. Heap fragmentation is a result of a large number of allocations / deallocations and can cause unexpected delays when allocating memory for new objects.

The main counter-measurement is called defragmentation or compaction of the heap. Since Java hides the actual memory addresses for objects, the JVM is allowed to implement facilities to compact the heap at will. However, this obviously comes with a performance penalty.

Objective

In this project you will develop a tool to foresee heap fragmentation. That is, given some initial knowledge of the program, the tool shall predict the state of fragmentation in the long run by simulating a coarse model of the program using a stochastic memory model.

The tool would roughly work as follows:

1. The user selects a program to analyze.
2. The tool statically analyzes the program
3. (Optional step) The tool rewrites the program to log branching probabilities during execution and runs for a relatively short period of time.
4. A model is built based on the analysis and logged branching probabilities.
5. The model is simulated, or ``executed'', and statistical data is collected.
6. A report is generated, with useful information about where the worst memory fragmentation occurs.

Upon successful completion of the project, you are welcome to participate in writing and submitting a scientific paper to a suitable conference.

The project includes:

• A reading part to deepen knowledge of the Java memory model, Java garbage collection and heap fragmentation.
• A tool development part.
• Case study part; Dig up about two or three real world Java applications and analyze them with the tool.
• A writing part in which a formal report is written.

Competence:

• Profound programming skills, preferably with a background in Java.
• Essential knowledge of probability and statistics.

Further reading

http://java.dzone.com/articles/ghost-java-virtual-machine
http://www.artima.com/insidejvm/ed2/gc.html
http://en.wikipedia.org/wiki/Fragmentation_(computer)

Contact

If interested in this project, please contact

Mads Dam, mfd@kth.se, (www.csc.kth.se/~mfd), or
Andreas Lundblad, landreas@kth.se, (www.csc.kth.se/~landreas)