著者

井田 昌之 竹内 郁雄 萩谷 昌巳 安村 通晃 湯浅 太一 寺島 元章

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.27, no.1, pp.p67-77, 1986-01

著者

川又 晃 羅翔 寺島 元章

出版者

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

雑誌

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

巻号頁・発行日

vol.41, no.2, pp.105-105, 2000-03-15

---

当研究室で開発した便宜的ガーベッジコレクション(ccasional G)の並行化とその実装について述べる.便宜的GCとは,リスト処理などの純計算側が消費したヒープ中の最新の使用域のみを対象として使用中オブジェクトの圧縮(liding compactio)処理を行うものである.その効果として,GC処理時間の短縮化と,ヒープ使用の節約に伴うワーキングセットの縮小で純計算時間の短縮も図れることが停止回収型の実装から示されている.この便宜的GCの並行化は,毎回行われるGC処理の実時間(ealtim)化と定期的に行われるGCの並列(oncurren)化とからなる.前者は通常の掃除をこまめに行うことを,後者は時間のかかる大掃除を別個に行うことを意味する.GCの圧縮処理の実時間化に必要な,write?barrierと輪切り複写の機能は,そのまま並列化にも適用できる.並列化ではこれらに,排他制御が付加されるだけである.輪切り複写とは,一度に圧縮するオブジェクトを移動先にその複製が作られる範囲に限定することであり,GCの圧縮処理中での中断を可能にする.また,write?barrierはオブジェクト参照に伴う純計算側の負荷を減らす.純計算側はLispの一方旨であるPHLを用い,GC側はスレッドライブラリを利用したコルーティンという汎用的な環境下で実装を行った.数種のLispプログラムの実行結果から得られた本GCの実時間特性についても述べる.The design and implementation ofincremental occasional garbage collection are presented. The occasional garbage collectionis a new type of garbage collection(GC)based on a "mark-and-compact" or sliding compaction scheme.The GC focuses its task of scavenging on most recently generated data object to gain time, and its good performance is shown by a prototype of "stop-and‐collect" version. The incremental occasional garbage collection is made up of two features:"realtime"and"concurrency''. The former is performed usually, while the latter is periodically to gain more spaces.They need common schemes of a write barrier and a coherent copy.The write barrier is less costly in time for coordination than a read barrier, and the coherent copy makes each data object consistent upon its relocation. The concurrency needs exclusive control in addition to them, so that these two features are implemented effectively in the GC.The incrementaI GC is implemented on a multi‐processor machine with shared memory by using(POSI・ス)thread library that makes it portable. The analys of the GC on its performance is done by using our experimental data obtained from the execution of typical Lisp programs.

著者

寺島 元章

出版者

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

雑誌

情報処理 (ISSN:04478053)

巻号頁・発行日

vol.26, no.7, pp.p711-720, 1985-07-15

被引用文献数

1

著者

平岡 慶子 小寺 信治 寺島 元章

出版者

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

雑誌

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

巻号頁・発行日

vol.44, no.2, pp.36, 2003-02-15

---

使用中データオブジェクトをヒープの一端にそれらの配置順序を保存して再配置する圧縮方式(mark-and-compact )に基づいた三世代ガーベッジコレクションの実装とその評価について述べる.圧縮方式のガーベッジコレクション(GC )ではヒープ上での世代の序列が永久に変化しないため,各世代は単にヒープのアドレスで区分できる.そこで,GC はGC 対象領域と呼ぶヒープ中の1 区画を決めることで,3 つのオブジェクト世代に対して包括的かつ効率的に行うことができる.隣接したGC間で消費された領域には新しい世代のオブジェクトがあり,それをGC 対象領域とするのが新世代GC である.1 回のGC 経験回数で殿堂入りした新古世代オブジェクトはその総量が閾値を超えるとGC により古世代オブジェクトとなる.このときのGC 対象領域は新世代と新古世代のオブジェクトが存在する連続した区画となる.新世代GC と異なるのは区画が大きくなるだけである.なお,古世代はヒープが枯渇しない限りGC の対象とはならない.また,新古世代オブジェクト量を調整するための新世代領域の動的変更機能についても述べる.We describe implementations and evaluation of three-generational garbage collection based on a sliding compaction (mark-and-compact)scheme that moves data objects being in use toward an end of a heap preserving their allocated order.The GC based on the sliding compaction scheme preserves the allocated order of generations as a group of data objects,so that the generations are simply classi fied according to their addresses of the heap.Our generational GC processes three generations efficiently and collectively by choosing a continuous space being subjected to GC from the heap.The GC for a young generation (minor collection) chooses the space that has been consumed since the last GC invocation and contains newest data objects.The objects that were subjected to the process of a single GC invocation changes to an old generation.The old generation is processed by the GC if its amount exceeds a prescribed value,and then changes to the oldest generation.This GC (major collection)chooses the continuous space that contains both the young and the old generations that is larger than the space for the minor collection.The oldest generation is free from the GC provided that the heap is not full of objects.Our generational GC also adopts dynamic adjustment of the space for the minor collection in order to reduce the amount of the old generation that affects the GC performance largely.

著者

鈴木 貢 寺島 元章 渡邊 坦

出版者

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

雑誌

情報処理学会論文誌プログラミング(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.