{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T17:06:38Z","timestamp":1789059998580,"version":"build-2803163510"},"reference-count":57,"publisher":"Association for Computing Machinery (ACM)","issue":"OOPSLA","license":[{"start":{"date-parts":[[2017,10,12]],"date-time":"2017-10-12T00:00:00Z","timestamp":1507766400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["Proc. ACM Program. Lang."],"published-print":{"date-parts":[[2017,10,12]]},"abstract":"<jats:p>Modern concurrent copying garbage collection (GC), in particular, real-time GC, uses fine-grained synchronizations with a mutator, which is the application program that mutates memory, when it moves objects in its copy phase. It resolves a data race using a concurrent copying protocol, which is implemented as interactions between the collector threads and the read and write barriers that the mutator threads execute. The behavioral effects of the concurrent copying protocol rely on the memory model of the CPUs and the programming languages in which the GC is implemented. It is difficult, however, to formally investigate the behavioral properties of concurrent copying protocols against various memory models.<\/jats:p>\n                  <jats:p>To address this problem, we studied the feasibility of the bounded model checking of concurrent copying protocols with memory models. We investigated a correctness-related behavioral property of copying protocols of various concurrent copying GC algorithms, including real-time GC Stopless, Clover, Chicken, Staccato, and Schism against six memory models, total store ordering (TSO), partial store ordering (PSO), relaxed memory ordering (RMO), and their variants, in addition to sequential consistency (SC) using bounded model checking. For each combination of a protocol and memory model, we conducted model checking with a model of a mutator. In this wide range of case studies, we found faults in two GC algorithms, one of which is relevant to the memory model. We fixed these faults with the great help of counterexamples. We also modified some protocols so that they work under some memory models weaker than those for which the original protocols were designed, and checked them using model checking. We believe that bounded model checking is a feasible approach to investigate behavioral properties of concurrent copying protocols under weak memory models.<\/jats:p>","DOI":"10.1145\/3133877","type":"journal-article","created":{"date-parts":[[2017,10,13]],"date-time":"2017-10-13T11:15:45Z","timestamp":1507893345000},"page":"1-26","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":7,"title":["Model checking copy phases of concurrent copying garbage collection with various memory models"],"prefix":"10.1145","volume":"1","author":[{"given":"Tomoharu","family":"Ugawa","sequence":"first","affiliation":[{"name":"Kochi University of Technology, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Tatsuya","family":"Abe","sequence":"additional","affiliation":[{"name":"Chiba Institute of Technology, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Toshiyuki","family":"Maeda","sequence":"additional","affiliation":[{"name":"Chiba Institute of Technology, Japan"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2017,10,12]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-41540-6_8"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of 19th Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS \u201914)","author":"Abe Tatsuya","year":"2014","unstructured":"Tatsuya Abe and Toshiyuki Maeda. 2014. A General Model Checking Framework for Various Memory Consistency Models. In Proceedings of 19th Workshop on High-Level Parallel Programming Models and Supportive Environments (HIPS \u201914). IEEE, 332\u2013341."},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-47958-3_4"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.2197\/ipsjjip.25.244"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-47677-3_8"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/2.546611"},{"key":"e_1_2_2_7_1","unstructured":"Peter M\u00c3\u0133ller Alexander J. Summers. 2017. Automating Deductive Verification for Weak-Memory Programs. (2017). arXiv:1703.06368."},{"key":"e_1_2_2_8_1","unstructured":"ARM 2016. ARM Architechture Reference Manual ARMv8 for ARMv8-A architechture profile. ARM."},{"key":"e_1_2_2_9_1","volume-title":"Pauseless Garbage Collection. White paper AWP\u2013005\u2013020","unstructured":"Azul. 2008. Pauseless Garbage Collection. White paper AWP\u2013005\u2013020. Azul Systems Inc. http:\/\/www.azulsystems.com\/ products\/whitepaper\/wp_pgc.pdf"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/378795.378819"},{"key":"e_1_2_2_11_1","volume-title":"Artificial Intelligence: An MIT Perspective","author":"Baker Henry G.","unstructured":"Henry G. Baker. 1979. Optimizing Allocation and Garbage Collection of Spaces in MacLLisp. In Artificial Intelligence: An MIT Perspective, Winston and Brown (Eds.). MIT Press. http:\/\/home.pipeline.com\/~hbaker1\/OptAlloc.ps.gz"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250737"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/174675.174673"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-11957-6_15"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2837614.2837615"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2737924.2738006"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/4472.4478"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1594834.1480935"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/376656.376810"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.712"},{"key":"e_1_2_2_21_1","unstructured":"IBM. 2015. Power ISA(TM) Version 3.0."},{"key":"e_1_2_2_22_1","unstructured":"Intel. 2016. Intel\u00ae 64 and IA-32 Architectures Software Developer\u2019s Manual."},{"key":"e_1_2_2_23_1","unstructured":"ISO\/IEC 14882:2011. 2011. Programming Language C++."},{"key":"e_1_2_2_24_1","unstructured":"ISO\/IEC 9899:2011. 2011. Programming Language C."},{"key":"e_1_2_2_25_1","volume-title":"The Garbage Collection Handbook: The Art of Automatic Memory Management","author":"Jones Richard","unstructured":"Richard Jones, Antony Hosking, and Eliot Moss. 2012. The Garbage Collection Handbook: The Art of Automatic Memory Management. Chapman &amp; Hall."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1556444.1556453"},{"key":"e_1_2_2_27_1","volume-title":"Proceedings of 31st European Conference on Object-Oriented Programming (ECOOP \u201917)","author":"Kaiser Jan-Oliver","year":"2017","unstructured":"Jan-Oliver Kaiser, Hoang-Hai Dang, Derek Dreyer, Ori Lahav, and Viktor Vafeiadis. 2017. Strong Logic for Weak Memory: Reasoning About Release-Acquire Consistency in Iris. In Proceedings of 31st European Conference on Object-Oriented Programming (ECOOP \u201917) (LIPIcs). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 17:1\u201317:29."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/1133981.1134023"},{"key":"e_1_2_2_29_1","volume-title":"Proceedings of Tools and Algorithms for Construction and Analysis of Systems (TACAS \u201914)","volume":"8413","author":"Kroening Daniel","year":"2014","unstructured":"Daniel Kroening and Michael Tautschnig. 2014. CBMC - C Bounded Model Checker - (Competition Contribution). In Proceedings of Tools and Algorithms for Construction and Analysis of Systems (TACAS \u201914) (LNCS), Vol. 8413. Springer-Verlag, 389\u2013391."},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-47666-6_25"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/2754169.2754187"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-16164-3_16"},{"key":"e_1_2_2_33_1","volume-title":"Staccato: A Parallel and Concurrent Real-time Compacting Garbage Collector for Multiprocessors. IBM Research Report RC24505. IBM Research","author":"McCloskey Bill","year":"2008","unstructured":"Bill McCloskey, David F. Bacon, Perry Cheng, and David Grove. 2008. Staccato: A Parallel and Concurrent Real-time Compacting Garbage Collector for Multiprocessors. IBM Research Report RC24505. IBM Research. http:\/\/domino.watson. ibm.com\/comm\/research_people.nsf\/pages\/dgrove.rc24504.html"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/155090.155111"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0017201"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509514"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/3018743.3018749"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-14107-2_23"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1296907.1296927"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1254766.1254784"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/1375581.1375587"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806596.1806615"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-15057-9_4"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602988.2602992"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/514188.514190"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1229428.1229469"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993498.1993520"},{"key":"e_1_2_2_48_1","unstructured":"SV-COMP. 2016. Competition on Software Verification. (2016). https:\/\/sv-comp.sosy-lab.org\/ ."},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1109\/FMCAD.2016.7886679"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-03077-7_21"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-46750-4_1"},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/2660193.2660243"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602988.2602991"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/2509136.2509532"},{"key":"e_1_2_2_55_1","volume-title":"Model checking LLVM IR using LTSmin: using relaxed memory model semantics. Master\u2019s thesis","author":"van der Berg F.I.","unstructured":"F.I. van der Berg. 2013. Model checking LLVM IR using LTSmin: using relaxed memory model semantics. Master\u2019s thesis. University of Twente."},{"key":"e_1_2_2_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250734.1250787"},{"key":"e_1_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpe.837"}],"container-title":["Proceedings of the ACM on Programming Languages"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3133877","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3133877","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,9,10]],"date-time":"2026-09-10T16:10:47Z","timestamp":1789056647000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3133877"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017,10,12]]},"references-count":57,"journal-issue":{"issue":"OOPSLA","published-print":{"date-parts":[[2017,10,12]]}},"alternative-id":["10.1145\/3133877"],"URL":"https:\/\/doi.org\/10.1145\/3133877","relation":{},"ISSN":["2475-1421"],"issn-type":[{"value":"2475-1421","type":"electronic"}],"subject":[],"published":{"date-parts":[[2017,10,12]]},"assertion":[{"value":"2017-10-12","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}