循環構造に適用可能な参照カウント方式GC A GC algorithm based on Reference Counting able to collect cycles

この論文をさがす

著者

    • 前田 宗則 Maeda Munenori
    • 技術研究組合新情報処理開発機構つくば研究センタ Tsukuba Research Center, Real World Computing Partnership
    • 小中 裕喜 Konaka Hiroki
    • 技術研究組合新情報処理開発機構つくば研究センタ Tsukuba Research Center, Real World Computing Partnership
    • 石川 裕 Ishikawa Yutaka
    • 技術研究組合新情報処理開発機構つくば研究センタ Tsukuba Research Center, Real World Computing Partnership
    • 友清 孝志 Tomokiyo Takashi
    • 技術研究組合新情報処理開発機構つくば研究センタ Tsukuba Research Center, Real World Computing Partnership
    • 堀 敦史 Hori Atsushi
    • 技術研究組合新情報処理開発機構つくば研究センタ Tsukuba Research Center, Real World Computing Partnership

抄録

本稿では,循環参照カウント方式(CRC)を基礎とする新しいGCアルゴリズムCRC_<IW>を提案する.CRCは,ポインタによる循環構造も含めた任意の使用不能なメモリブロック(オブジェクト)を回収可能なGC方式であるが,対象言語がコンビネータに制限されること,循環構造を管理するアルゴリズムが逐次的であることという二点により,並列マシン上の一般の高級言語にはそのまま適用できなかった.CRC_<IW>は,各オブジェクトに順序数を与えることで任意の言語に適用可能とし,複数のプロセスによって並列に循環構造を管理するようアルゴリズムを拡張している.さらに,分散メモリを持つ並列マシンにおいてGCによる通信オーバーヘッドを低減するために,参照を3タイプに分けて管理することと各参照に重みを与えることが考察される.

In this paper, we propose a new garbage collection algorithm based on Cyclic Reference Counting, CRC, which is able to reclaim any memory block, called object, in disuse including a cyclic structure by pointers. However, CRC has difficulty in applying to high-level languages on multi-computers because: i)its target is not a general language which allows unrestricted pointer operations but only combinator, and ii)its algorithm managing cycles is sequential and not incremental. Our GC scheme, called CRC_<IW>, extends CRC in terms of above two points. A unique ordinal number for each object and a multi-processed cycle management enable CRC_<IW> to manage cycles safely in parallel independently of languages. In addition, to reduce communication overhead on a distributed environment, we investigate classifying types of reference into three and adding weight for each reference.

収録刊行物

  • 情報処理学会研究報告. 記号処理研究会報告

    情報処理学会研究報告. 記号処理研究会報告 93(81), 17-24, 1993-09-17

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

各種コード

  • NII論文ID(NAID)
    110002929388
  • NII書誌ID(NCID)
    AN10112573
  • 本文言語コード
    JPN
  • データ提供元
    NII-ELS 
ページトップへ