Starvation-free heap size for replication-based incremental compacting garbage collection
Pages 43 - 52
Abstract
We present a method to estimate the amount of the heap required to execute application programs on runtime systems with our replication-based incremental compacting garbage collector. Our method provides a strategy for adjusting the timing to trigger garbage collection and choosing a heap region to be evacuated during partial compaction, which moves all objects in one part of the heap to the rest of the heap. The method is also used to determing the minimum heap size that guarantees free memory never exhausts during incremental garbage collection. Furthermore, we ensure that allocation never fails due to fragmentation with the strategy. The strategy is to reserve a contiguous free area and to prohibit the allocator from allocating in that area until garbage collection is triggered. When it becomes necessary to use the reserved free area to satisfy an allocation request, we trigger garbage collection. We show that, with this strategy, an application never fails to allocate objects with a larger heap than R + 2 √(2Ra) + 3a plus space overhead caused by the heap layout, where R is the maximum amount of live objects and a is the upper bound of the possible amount of allocation during a single collection cycle.
References
[1]
]]B. Alpern et al. The jalapeño virtual machine. IBM System Journal, 39(1):211--238, 2000.
[2]
]]D. F. Bacon, P. Cheng, and V. Rajan. A real-time garbage collector with low overhead and consistent utilization. In Proceedings of the 30th ACM SIGPLAN-SIGACT symposium on principles of programming languages (POPL '03), pages 285--298, 2003.
[3]
]]D. F. Bacon, P. Cheng, and V. Rajan. Controlling fragmentation and space consumption in the metronome, a real-time garbage collector for Java. In Proceedings of the 2003 ACM SIGPLAN conference on Language, compiler, and tool for embedded systems (LCTES '03), pages 81--92, 2003.
[4]
]]H. G. Baker. The treadmill: real-time garbage collection without motion sickness. ACM SIGPLAN Notice, 27(3):60--70, 1992.
[5]
]]H. G. Baker, Jr. List processing in real time on serial computer. Communications of the ACM, 21(4):280--294, 1978.
[6]
]]O. Ben-Yitzhak, I. Goft, E. K. Kolodner, K. Kuiper, and V. Leikehman. An algorithm for parallel incremental compaction. In Proceedings of the 3rd international symposium on Memory management (ISMM'02), pages 100--105, 2003.
[7]
]]G. E. Blelloch and P. Cheng. On bounding time and space for multiprocessor garbage collection. In Proceedings of the 1999 ACM SIGPLAN conference on Programming language design and implementation (PLDI '99), pages 104--117, 1999.
[8]
]]H.-J. Boehm, A. J. Demers, and S. Shenker. Mostly parallel garbage collection. In Proceedings of the 1991 ACM SIGPLAN conference on Programming language design and implementation (PLDI '91), pages 157--164, 1991.
[9]
]]R. A. Brooks. Trading data space for reduced time and code space in real-time garbage collection on stock hardware. In Proceedings of the 1984 ACM Symposium on LISP and functional programming, pages 256--262, 1984.
[10]
]]P. Cheng and G. E. Blelloch. A parallel, real-time garbage collector. In Proceedings of the 2001 ACM SIGPLAN conference on Programming language design and implementation (PLDI '01), pages 125--136, 2001.
[11]
]]D. Detlefs, C. Flood, S. Heller, and T. Printezis. Garbage-first garbage collection. In Proceedings of the 3rd international symposium on Memory management (ISMM '04), pages 37--48, 2004.
[12]
]]E. W. Dijkstra, L. Lamport, A. J. Martin, C. S. Scholten, and E. F. M. Steffens. On-the-fly garbage collection: An exercise in cooperation. communications of the ACM, 21(11):966--975, 1978.
[13]
]]T. Kalibera. Replicating real-time garbage collector for Java. In Proceedings of the 7th International Workshop on Java Technologies for Real-time and Embedded Systems (JTRES '09), pages 100--109, 2009.
[14]
]]B. Lang and F. Dupont. Incremental incrementally compacting garbage collection. In Papers of the Symposium on Interpreters and interpretive techniques, pages 253--263, 1987.
[15]
]]S. Nettles and J. O'Toole. Real-time replication garbage collection. In Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation (PLDI '93), pages 217--226, 1993.
[16]
]]F. Pizlo, L. Ziarek, P. Maj, A. L. Hosking, E. Blanton, and J. Vitek. Schism: Fragmentation-tolerant real-time garbage collection. In Proceedings of the 2010 ACM SIGPLAN conference on Programming language design and implementation (PLDI '10), pages 146--159, 2010.
[17]
]]H. Saiki, Y. Konaka, T. Komiya, M. Yasugi, and T. Yuasa. Real-time GC in JeRTy VM using the return-barrier method. In 8th IEEE International Symposium on Object-oriented Real-time distributed Computing (ISORC 2005), pages 140--148, 2005.
[18]
]]F. Siebert. Hard real-time garbage-collection in the Jamaica virtual machine. In Proceedings of the 6th International Conference on Real-Time Computing Systems and Applications (RTCSA '99), page 96, 1999.
[19]
]]G. L. Steele, Jr. Multiprocessing compactifying garbage collection. communications of the ACM, 18(9):495--508, 1975.
[20]
]]T. Ugawa, M. Yasugi, and T. Yuasa. Replication-based incremental compaction. In Proceedings of the 12th IEEE International Symposium on Object/Component/Service-oriented Real-Time Distributed Computing (ISORC '08), pages 516--524, 2008.
[21]
]]T. Ugawa, H. Iwasaki, and T. Yuasa. Improved replication-based incremental garbage collection for embedded systems. In Proceedings of the 9th international symposium on Memory management (ISMM '10), pages 73--82, 2010.
[22]
]]T. Yuasa. Real-time garbage collection on general-purpose machines. Journal of Software and Systems, 11(3):181--198, 1990.
Index Terms
- Starvation-free heap size for replication-based incremental compacting garbage collection
Recommendations
Age-based garbage collection
Modern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Improved replication-based incremental garbage collection for embedded systems
ISMM '10We have developed an incremental compacting garbage collector for embedded Java systems. The collector divides the heap into equal sized pages and uses the segregated free lists for fast allocation. Collectors that have such a heap layout have a problem ...
Age-based garbage collection
OOPSLA '99: Proceedings of the 14th ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applicationsModern generational garbage collectors look for garbage among the young objects, because they have high mortality; however, these objects include the very youngest objects, which clearly are still live. We introduce new garbage collection algorithms, ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
October 2010
82 pages
Copyright © 2010 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 19 October 2010
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
SPLASH '10
Sponsor:
SPLASH '10: Systems Programming Languages and Applications: Software for Humanity
October 19 - 21, 2010
Nevada, Reno/Tahoe, USA
Acceptance Rates
Overall Acceptance Rate 18 of 26 submissions, 69%
Upcoming Conference
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 127Total Downloads
- Downloads (Last 12 months)3
- Downloads (Last 6 weeks)0
Reflects downloads up to 19 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in