Patent ID: 7953773

Claim:
A system for deterministic garbage collection in a virtual machine environment, comprising: a computer, including a computer readable medium and processor operating thereon; a virtual machine, executing on the computer, for executing a software application; a memory space for use by the virtual machine in storing software objects and pointers as part of the software application; a plurality of worker threads that each update pointers within the memory space at runtime; a data structure including a plurality of elements, wherein each element is associated with a different region of the memory space, and wherein when a pointer is updated in a particular region of the memory space the element associated with the particular region is modified to indicate that the particular region of the memory space requires cleaning; a plurality of worker thread counters, wherein each worker thread counter is a thread local variable associated with one of the plurality of worker threads and wherein each time one of the worker threads updates any pointer, the corresponding worker thread counter increments such that it indicates the number of times the corresponding worker thread has updated pointers; a counter sum associated with the plurality of worker threads, wherein the counter sum is calculated by summing the plurality of worker thread counters to indicate a total number of times the plurality of worker threads have updated pointers, which provides an estimate of a maximum number of regions of the memory space that require cleaning; and a garbage collector that determines a target pause time limit for garbage collection, performs an initial marking phase of garbage collection, allocates a fractional amount of the target pause time limit for a compaction phase of garbage collection; determines an estimated pause time based on the maximum number of regions of the memory space that require cleaning, as estimated by the counter sum, determines a calculated time limit for garbage collection of the software objects within a compaction area which corresponds to the target pause time limit less a time taken to perform the initial marking phase and the fractional amount of the target pause time limit, and controls the garbage collection process so that a final marking phase is performed only when the estimated pause time is less than the calculated time limit.