Editing Tracing garbage collection (section)

== Real-time garbage collection ==

While garbage collection is generally nondeterministic, it is possible to use it in hard [[real-time computing|real-time]] systems. A real-time garbage collector should guarantee that even in the worst case it will dedicate a certain number of computational resources to mutator threads. Constraints imposed on a real-time garbage collector are usually either work based or time based. A time based constraint would look like: within each time window of duration <math>T</math>, mutator threads should be allowed to run at least for <math>T_m</math> time. For work based analysis, MMU (minimal mutator utilization)<ref>{{cite journal |first1=Perry |last1=Cheng |first2=Guy E. |last2=Blelloch |date=2001-06-22  |df=mdy |title=A Parallel, Real-Time Garbage Collector |journal=ACM SIGPLAN Notices |volume=36 |issue=5 |pages=125–136 |doi=10.1145/381694.378823 |url=http://www.aladdin.cs.cmu.edu/papers/pdfs/y2001/rtg.pdf}}</ref> is usually used as a real-time constraint for the garbage collection algorithm.

One of the first implementations of [[hard real-time]] garbage collection for the [[JVM]] was based on the [[Metronome algorithm]],<ref>{{cite conference |last1=Bacon |first1=David F. |last2=Cheng |first2=Perry |last3=Rajan |first3=V. T. |date=November 2003 |title=The Metronome: A Simpler Approach to Garbage Collection in Real-Time Systems |editor-last1=Corsaro |editor-first1=Angelo |editor-last2=Cytron |editor-first2=Ron |editor-last3=Santoro |editor-first3=Corrado |book-title=Workshop on Java Technologies for Real-Time and Embedded Systems |department=JTRES'03 |conference=OTM 2003 Workshops |work=On The Move to Meaningful Internet Systems 2003 |series=[[Lecture Notes in Computer Science|LNCS]] |volume=2889 |pages=466–478 |citeseerx=10.1.1.3.8544 |doi=10.1007/978-3-540-39962-9_52 |isbn=3-540-20494-6 |issn=0302-9743 |s2cid=14565934 |url=http://www.research.ibm.com/people/d/dfb/papers/Bacon03Metronome.pdf |archive-url=https://web.archive.org/web/20061026215158/http://www.research.ibm.com/people/d/dfb/papers/Bacon03Metronome.pdf |archive-date=2006-10-26}}</ref> whose commercial implementation is available as part of the [[IBM WebSphere Real Time]].<ref>{{cite web |last1=Biron |first1=Benjamin |last2=Sciampacone |first2=Ryan |date=2007-05-02 |df=mdy |title=Real-time Java, Part 4: Real-time garbage collection |work=IBM DeveloperWorks |url=http://www.ibm.com/developerworks/java/library/j-rtj4/index.html |archive-url=https://web.archive.org/web/20201109040826/http://www.ibm.com/developerworks/java/library/j-rtj4/index.html |archive-date=2020-11-09}}</ref> Another hard real-time garbage collection algorithm is Staccato, available in the [[IBM]]'s [[IBM J9|J9 JVM]], which also provides scalability to large multiprocessor architectures, while bringing various advantages over Metronome and other algorithms which, on the contrary, require specialized hardware.<ref>{{cite tech report |last1=McCloskey |first1=Bill |last2=Bacon |first2=David F. |last3=Cheng |first3=Perry |last4=Grove |first4=David |date=2008-02-22 |df=mdy |title=Staccato: A Parallel and Concurrent Real-time Compacting Garbage Collector for Multiprocessors |institution=IBM Research Division |number=RC24504 |url=https://dominoweb.draco.res.ibm.com/reports/rc24504.pdf |access-date=2022-04-25}}</ref>

One major challenge for real-time garbage collection on modern multi-core architectures is in designing a non-blocking concurrent garbage collection, not letting the concurrent threads block each other and create unpredictable pauses. A study of algorithms that allow non-blocking real-time concurrent garbage collection appears in a paper by Pizlo et al. in Microsoft Research.<ref>{{cite conference |last1=Pizlo |first1=Phil |author2-link=Erez Petrank |last2=Petrank |first2=Erez |last3=Steensgaard |first3=Bjarne |date=June 2008 |title=Proceedings of the 29th ACM SIGPLAN Conference on Programming Language Design and Implementation | conference=PLDI 2008 Conferenece |  pages=33–44 |citeseerx=10.1.1.3.8544 |doi=10.1145/1375581.1375587 |isbn= 9781595938602 | url=http://www.cs.technion.ac.il/~erez/Papers/real-time-pldi.pdf }}</ref>