Bacon 03 Controlling

Slide1: 

David F. Bacon Perry Cheng V.T. Rajan IBM T.J. Watson Research Center Controlling Fragmentation and Space Consumption in the Metronome

Problem Domain: 

Problem Domain Hard real-time garbage collection Implemented for Java Uniprocessor Multiprocessors rare in real-time systems Complication: collector must be finely interleaved Simplification: memory model easier to program No truly concurrent operations Sequentially consistent

Metronome Project Goals: 

Metronome Project Goals Make GC feasible for hard real-time systems Provide simple application interface Develop technology that is efficient: Throughput, Space comparable to stop-the-world BREAK THE MILLISECOND BARRIER While providing even CPU utilization

Outline: 

Outline Overview of the Metronome Empirical Results What is Fragmentation? Static and dynamic measures How do we control space consumption? Conclusions

The Metronome Collector: 

The Metronome Collector

Real-time GC Approaches: 

Real-time GC Approaches Mark-sweep (non-copying) Fragmentation avoidance, coalescing Subject to space explosion Semi-space Copying Concurrently copies between spaces Cost of copying, consistency, 2x space The Metronome Mark-sweep, selective defragmentation Best of both, adaptively adjusts

Components of the Metronome: 

Components of the Metronome Incremental mark-sweep collector Mark phase fixes stale pointers Selective incremental defragmentation Moves < 2% of traced objects Time-based scheduling Segregated free list allocator Geometric size progression limits internal fragmentation Old New

Support Technologies: 

Support Technologies Read barrier: to-space invariant [Brooks] New techniques with only 4% overhead Write barrier: snapshot-at-the-beginning [Yuasa] Arraylets: bound fragmentation, large object ops Old New

Empirical Results: 

Empirical Results

Pause time distribution: javac: 

Pause time distribution: javac 12 ms 12 ms Time-based Scheduling Work-based Scheduling

Utilization vs. Time: javac: 

Utilization vs. Time: javac Time (s) Time (s) 0.4 0.2 0.0 0.6 0.8 1.0 Utilization (%) 0.4 0.2 0.0 0.6 0.8 1.0 Time-based Scheduling Work-based Scheduling 0.45

Space Usage: javac: 

Space Usage: javac

Parameterization: 

Parameterization Mutator a*(ΔGC) m Collector R Tuner Δt s u Allocation Rate Maximum Live Memory Collection Rate Real Time Interval Maximum Used Memory CPU Utilization

Is it real-time? Yes: 

Is it real-time? Yes Maximum pause time < 4 ms [currently] MMU > 50% ±2% Memory requirement < 2 X max live

Static Fragmentation: 

Static Fragmentation

Segregated Free List Allocator: 

Segregated Free List Allocator Heap divided into fixed-size pages Each page divided into fixed-size blocks Objects allocated in smallest block that fits 24 16 12

Fragmentation on a Page: 

Fragmentation on a Page Internal: wasted space at end of object Page-internal: wasted space at end of page External: blocks needed for other size external internal page-internal

Fragmentation: ρ=1/8 vs. ρ=1/2: 

Fragmentation: ρ=1/8 vs. ρ=1/2

Dynamic Fragmentation: 

Dynamic Fragmentation

Locality of Size: λ: 

Locality of Size: λ Measures reuse Normalized: 0≤λ≤1 Segregated by size Bytes Allocated Freed Allocated Freed Allocated Freed Perfect Reuse λ = Σi min ( fi / f, ai / a) Freed Reused Allocated Reused

λ in Real-time GC Context: 

λ in Real-time GC Context Mark-sweep (non-copying) Semi-space Copying The Metronome Assumes λ=1 Assumes λ=0 Adapts as λ varies

λ in Practice: 

λ in Practice

Controlling Space Consumption: 

Controlling Space Consumption

Triggering Collection: 

Triggering Collection MS 1 MS 2 MS 3 DF 1 DF 2 TIME PAGES Free Defrag

Factors in Space Consumption: 

Factors in Space Consumption MS 1 MS 2 MS 3 DF 1 DF 2 R λ

Reducing Space Consumption: 

Reducing Space Consumption Collection Rate R Higher rate: less memory reserve needed Speed up collector Specify rate more precisely (bound worst-case) Locality of Size λ Higher locality: less free page reserve needed Specify page requirement more precisely

Conclusions: 

Conclusions

Conclusions: 

Conclusions Contributions Time-based scheduling (Tunable) Mostly non-copying collection (λ varies) Efficient software read barrier Precise definition of fragmentation Precise specification of collection triggers The Metronome provides true real-time GC First collector to do so without major sacrifice Short pauses (4 ms) High MMU during collection (50%) Low memory consumption (2x max live)