著者

鈴木 貢 寺島 元章 渡邊 坦

出版者

一般社団法人情報処理学会

雑誌

情報処理学会論文誌プログラミング(PRO) (ISSN:18827802)

巻号頁・発行日

vol.42, no.11, pp.102-102, 2001-11-15

---

マークアンドスイープ法に基づく固定長セルを対象とした並列ごみ集め(GC)を提案する.従来のGCは印付けと回収が直列的に実施されるのに対し,本GCではそれらが並列に実施される.これによってGCの処理能力が増し,セルを消費する複数のプロセスに対応できる.その特徴は,印付けを行いながら回収を行う「尺取り虫印付け法」と,複数プロセスの効率の良いセルの確保を可能にする「フリーセルのクラスタ化」である.印付けは,スタックを使ったリスト辿り法を用いているので,それに要する時間は使用中セルの個数に比例する.また,本GCでは,従来の印付け回収法では必須であった回収時の印の取り外しを行わない.そして,印付けプロセスと回収プロセスが印をめぐって際どい部分に入ることがほとんどなく,両者は本質的に非同期に稼働しうる.A parallel garbage collector (GC) based on mark-and-sweep method for fixed size cells is presented. It enables parallel running of both marking process and collection process, while previous parallel GCs do not permit such parallel running. With this method, we can get enough high performance GC to support multiple processes which consume cells. The distinguished technical points of this paper are "Inchworm marking" which enables parallel running of marking and collection, and "Clustered free cells" which improves allocation time overhead for multiple mutators. We adopts list traversal method with stack for marking, and the marking process can be completed in a time proportional to the amount of in-use cells. Our GC does not reset the marks of the cells, while others does. The marking process and the collection process rarely enter into critical region for marks, and they essentially can run asynchronously.