|
|
WASTE NOT,WANT NOT: ADAPTIVE GARBAGE COLLECTION IN A SHARED ENVIRONMENT
Chengliang Zhang†, Kirk Kelsey†, Xipeng Shen‡
Chen Ding†, Matthew Hertz_, and Mitsu Ogihara†
†Department of Computer Science
University of Rochester
{zhangchl,kelsey,cding,ogihara}@cs.rochester.edu
‡Department of Computer Science
The College of William and Mary
xshen@cs.wm.edu
_Department of Computer Science
Canisius College
hertzm@canisius.edu
University of Rochester Computer Science Department
Technical Report TR-2006-908
Introduction
Software developers are taking advantage of garbage collection for the many
engineering benefits it provides using either garbage-collected languages such
as Lisp, ML, Java, and C# or conservative garbage collectors such as the
Boehm-Demers-Weiser collector [6]. While a conventional program uses exactly as
much memory as it needs, the memory use of a garbage collected program can
expand beyond its need. This difference raises the possibility of resource-based
garbage collection, which is to adapt the frequency of GC in response to the
changing amount of available memory.
Memory usage depends first on the program demand. The heap must be large enough
to accommodate all reachable data. When the heap size is large enough, setting a
larger heap size in the virtual machine will lead to fewer calls to the
collector, which means lower collection time, so long as the heap size does not
exceed the available memory and cause paging. The common scheme for Java
programs is to use a fixed range by which the heap size can exceed the program’s
need. As an example Jikes RVM uses a range of 50MB to 100MB by default. This is
often a mismatch to the available resource for a number of reasons. First, the
actual memory usage depends on the garbage collector implementation (e.g. twice
the heap size for a copying collector), not counting the memory needed by the
virtual machine and the operating system. Second, knowing the exact amount of
available memory is difficult because it requires ascertaining the active memory
usage of other programs. Much memory may be occupied but not used (for example
the file cache) and can be made available. Last but not least, the heap size,
which is set before the execution, cannot respond to change of conditions in the
middle of an execution.
In this paper we address the problem of resource-based garbage collection in a
shared environment, which is increasingly common on today’s multi-processor,
multi-core, and multi-threaded machines. Garbage-collected programs, however,
lack a firm basis for high degrees of multi-programming if two problems remain
unsolved. The amount of available memory may change significantly and
dynamically because of memory sharing, making any setup vulnerable to extreme
and adverse conditions if it does not adapt to the dynamic resource. Also, the
moment a program starts to adapt, it embarks on a collision course with other
like-minded programs, no matter how much memory is available.
We first revise the classical performance model, which is demand-based, to
accommodate resource-based memory management. We introduce a new quantitative
notion called time-memory curve and use it to predict the performance of memory
sharing in this new context. An example of a resource-based garbage collection
system is program level adaptive memory management (PAMM), which uses run-time
monitoring and heap-size control for resource adaptation [24]. We develop a
scheme similar to PAMM for memory sharing. While the previous scheme used
semi-manual phase analysis, we make it fully automatic so it can be applied to
general programs. The previous scheme is designed for a static environment and
by nature is selfish. It does not consider other contenders for the monopoly on
memory. We present cooperative PAMM, which dynamically divides the available
memory among the resource contenders through a shared white-board data structure
to maximize system throughput.
The adaptive GC techniques are implemented at the program level by inserting a
run-time monitor and controller, without users’ effort. They monitor the program
demand and the memory performance (in particular the memory paging) to adapt the
memory demand with the available resource. They do not require changes to the
virtual machine or the operating system, so they can be automatically deployed
on existing systems.
More information
For more information, see the complete
whitepaper.
References
[6] H.-J. Boehm and M. Weiser. Garbage collection in an uncooperative
environment. Software: Practice and Experience,
[24] C. Zhang, K. Kelsey, X. Shen, C. Ding, M. Hertz, and M. Ogihara.
Program-level adaptive memory management. In
Proceedings of the International Symposium on Memory Management, Ottawa, Canada,
June 2006. |
DR.
CHEN DING