JPS6358558A - ガ−ベジコレクシヨン処理方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

【発明の詳細な説明】 〔概要〕 アドレスを動的に割りつけたセルをアクセス可能な態様
で格納する主記憶装置と、セルに関する情報を独立にア
クセス可能な態様で格納するビット操作用メモリと、該
当するセルに関する情報をアクセス制御するビット操作
制御回路とを設け、主記憶装置中の旧記憶領域から新記
憶領域に有為なセルをコピーしてガーベジコレクション
を行う際に、ビット操作用メモリ中に複数のセルから参
照される参照関係情報および旧記憶領域から新記憶領域
にコピーした旨を表すコピー情報を各セルに対応づけて
夫々格納し、参照関係情報が格納されていない旧記憶領
域中のセルに対して新記憶領域中の該当するセルに対す
るポイント情報の格納を省略してガーベジコレクション
を行うことにより、ガーベジコレクションを高速に行う
ようにしている。

〔産業上の利用分野〕

本発明は、複数のセルから参照される参照関係情報を夫
々のセルに格納し、当該参照関係情報が格納されていな
いセルに対してコピーした新記憶領域をポイントするコ
ピー先のアドレスの格納を省略してガーベジコレクショ
ン動作を高速に行うガーベジコレクション処理方式に関
するものである。

〔従来の技術〕

リスト処理プログラムを実行する場合、プログラムから
新しいセルが要求されると、未使用の記憶領域を動的に
セル領域に割りつけている。また、セルに対する参照関
係が動的に変更されるため、既にプログラムが使用した
記憶領域内に不要となったセル領域が大量に存在するこ
とが多い。このため、不要となった記憶領域を回収する
ための操作（ガーベジコレクション）が必要となる。こ
のガーベジコレクションのための処理時間がどれだけか
かるかということがシステム性能に大きくかかわって（
る。

従来、効率の良いガーベジコレクージョンの１つとして
、コピー法ガーベジコレクションがある。

これは、第５図に示すように記憶領域を上空間と新空間
とに分割し、上空間はプログラムが使用するものであり
、新空間はプログラムが使用している上空間内のセル（
アクティブセル）をコピーして圧縮して使用可能な領域
を１個所にまとめた態様に作り出すためのものである。

第６図および第７図は、コピー法ガーベジコレクション
方式の動作説明図を示す。以下説明する。

第６図において、図中０は、コピービットがＯＮである
か否かを判別する状態を示す、これは、第７図図中［相
］を用いて示すように、上空間内のセル中のコピービッ
トがＯＮであるか否かをチェックすることを意味してい
る。ＹＥＳの場合（ＯＮの場合）には、既に上空間から
新空間にコピーされているので、図中［相］でポインタ
の書き替えを行って当該セルに対する処理を終了する。

ＮＯの場合には、図中＠以下の処理を行う。

図中０は、コピーを行う状態を示す。これは、第７図図
中０を用いて示すように、上空間内のセルに格納されて
いる内容を新空間内のセルにコピーすることを意味して
いる。

図中０は、フォワーディング・ポインタ（ｆｏｒｗａｒ
ｄｉｎｇ−ｐｏｉｎｔｅｒ）をセットする状態を示す、
これは、第７図図中０を用いて示すように、上空間内の
セル中に、新空間内に新たに生成したセルをポイントす
るアドレス情報を格納することを意味してい°る。これ
により、複数の他のセルから当該セルが参照されている
場合に、２番目以降の参照セルのポインタを、コピーさ
れた新空間のセルに対するものに書き換えを行うことが
可能となる。

図中［株］は、ポインタの書き換えを行う状態を示す。

これは、第７図図中［相］に示すように、当該セルに対
するポイント先を上空間のセルから新空間のセルに書き
換えることを意味している。

図中■は、コピービットをＯＮにする状態を示す。これ
は、第７図図中０に示すように上空間内のコピーをした
セルのコピービットをＯＮにすることを意味している。

以上のようにして、上空間内のアクティブセルが新空間
内に順次詰めた態様でコピーされ、結果として上空間内
の不用のセル領域が回収されることとなる。

〔発明が解決しようとする問題点〕

従来のコピー法ガーベジコレクション方式は、既述した
ように、上空間内のコピーしようとする該当セルが複数
の他のセル、から参照される場合を考えて、複数のセル
から参照されているか否かに関係なく全てのセルに対し
てコピー情報およびこのセルがコピーされたコピー先の
アドレス（参照関係情報）を旧空間内の当該セル中に格
納しておく必要がある。このため、実際には複数の他の
セルから参照されていないセルに対しても、参照関係情
報を夫々格納しなければならず、ガーベジコレクション
に要する時間が多く必要となってしまうという問題点が
あった。

〔問題点を解決するための手段〕

本発明は、前記問題点を解決するために、アドレスを動
的に割りつけたセルをアクセス可能な態様で格納する主
記憶装置と、セルに関する情報を独立にアクセス可能な
態様で格納するビット操作用メモリと、該当するセルに
関する情報をアクセス制御するビット操作制御回路とを
設け、主記憶装置中の旧記憶領域から新記憶領域に有ろ
なセルをコピーしてガーベジコレクシシンを行う際に、
ビット操作用メモリ中に複数のセルから参照される参照
関係情報および旧記憶領域から新記憶領域にコピーした
旨を表すコピー情報を各セルに対応づけて夫々格納し、
参照関係情報が格納されていない旧記憶領域中のセルに
対して新記憶領域中の該当するセルに対するポイント情
報の格納を省略してガーベジコレクシシンを行うように
している。

第１図は本発明の原理構成図を示す。図中主記憶装置１
は、セルを格納するものであって、面突間（旧記憶領域
）および新空間（新記憶領域）を生成するものである。

ビット操作用メモリ２は、主記憶装置１に格納するセル
に対応づけて、当該セルに関するコピー情報および参照
関係情報などをアクセス可能な態様で格納するものであ
る。

ビット操作制御回路３は、ＣＰＵ４からのアドレス情報
に基づいて、所定のアドレスを生成してビット操作用メ
モリ２から該当するセルのコピー情報および参照関係情
報などをアクセスするための制御回路である。

ＣＰＵ４は、内蔵するア「ドレスレジスタ４−１あるい
はデータレジスタ４−２からアドレス情報をビット操作
制御回路３に供給したり、アドレスレジスタ４−１から
アドレス情報を主記憶装置１に供給などするものである
。

〔作用〕

第１図に示す構成を採用し、アドレスレジスタ４−１か
らのアドレス情報および所定の読み／書き信号を主記憶
装置１に供給することにより、旧空間内のアクティブセ
ルの内容が、面突間から新空間に圧縮した態様でコピー
される。

同時に、アドレスレジスタ４−１あるいはデータレジス
タ４−２からのアドレス情報の通知を受けたビット操作
制御回路３は、所定のアドレスをビット操作用メモリ２
に供給して主記憶装置１に対してアクセスしたセルに対
応したコピー情報および参照関係情報などをセル本体の
アクセスとは分離した態様で独立にアクセスする。この
際、複数のセルから参照されているセルに対してのみ、
参照関係情報ビットをオンにすると共にフォワーディン
グ・ポインタの値を格納して２番目以降の参照セルに対
するポインタの書き換えを行い得るようにしているため
、高速にガーベジコレクション処理を行うことが可能と
なる。

〔実施例〕

次に、第２図ないし第４図を用いて本発明の１実施例構
成および動作を詳細に説明する。

第２図において、主記憶装置１中には旧記憶領域（面突
間）■−１および新記憶領域（新空間）１−２が設けら
れプログラム動作環境として管理されている。この旧記
憶領域１−１および新記憶領域１−２は、Ｃ−Ｐ　Ｕ　
Ａ内のアドレスレジスタ４−１から通知されたアドレス
信号によってアクセスされ、旧記憶領域１−１中のセル
（アクティブセル）の内容が読み出され、新記憶領域１
−２中のセルに順次詰めた態様で書き込まれる（コピー
される）。

ビット操作用メモリ２は、旧記憶領域１−１および新記
憶領域１−２中に格納したセルに対応づけてこれらのセ
ルのコピー情報および参照関係情報などを分離かつ独立
にアセクスし得るＢ様で格納するものである。

ビット操作制御回路３は、３−１ないし３−３から構成
されている。制御演算部３−１は、ＣＰＵから通知され
た制御信号および演算部３−３から通知された内部制御
信号に基づいて、メモリ制御部３−２およびビット操作
用メモリ２を制御して所定のコピー情報および参照関係
情報をアクセスするものである。メモリ制御部３−２は
、ＣＰＵ４内のアドレスレジスタ４−１からのアドレス
情報あるいはデータレジスタ４−２から通知された所定
のデータに基づいてアドレス信号を生成し、ビット操作
用メモリ２から所望のセルのコピー情報および参照関係
情報をアクセスするものである。

演算部３−３は、ビット操作用メモリ２から読み出され
たコピー情報および参照関係情報などに基づいて、演算
処理を行ってＣＰＵ制御信号および内部制御信号を生成
するものである。

以上のように、セルを格納する主記憶装置１と、このセ
ルのコピー情報および参照関係情報などを格納するビッ
ト操作用メモリ２を分離し、かつ独立にアクセスし得る
ａ様で設けることにより、後述するように、セル中に格
納されているポインタの書き換えなどの操作と、このセ
ルのコピー情報および参照関係情報などの０Ｎ１０ＦＦ
などの書き換えをいわば並列に処理して、高速にガーベ
ジコレクション処理を行うことが可能となる。

次に、第３図および第４図を用いて第１図および第２図
に示す構成の動作を詳細に説明する。

第３図において、図中■は、コピービットがＯＮである
か否かをチェックする状態を示す、これは、第４図図中
■に示すように、面突閣内の該当セル中のコピービット
がＯＮであるか否かをチェックすることを意味している
。ＹＥＳの場合（ＯＮの場合）には、既に面突間から新
空間にコピーされているので、図中■でポインタの書き
替えを行い、次いで、図中■で参照関係とソトをＯＦＦ
にして当該セルに対する処理を終了する。Ｎｏの場合に
は、図中■以下の処理を行う。この図中■および■のル
ートを通る処理回数は、（ｍ−ｎ）回となる。ここで、
ｍはセルのポインタ総数、ｎはアクティブセルの総数を
表す。

図中■は、コピーを行う状態を示す。これは、第４図図
中■を用いて示すように、面突閣内のセルの内容を新空
間内のセルにコピーすることを意味している。この■以
下のルートを通る処理回数は、１回（アクティブセルの
総数に等しい回数）となる。

図中■は、ポインタの書き換えを行う状態を示す。これ
は、第４図図中■に示すように、新空間にコピーしたセ
ルをポイントするようにポインタの値を書き換えること
を意味している。

図中■は、参照関係情報（ＲＥＦ−ＢＩＴ）がＯＮであ
るか否かをチェックする状態を示す。これは、第４図図
中■に示すように、面突閣内のセルのＲＥＦ−ＢＩＴが
ＯＮであるか否かをチェックすることを意味している。

ＹＥＳの場合（ＲＥＦ−Ｂ　ＩＴがＯＮの場合）には、
図中■以下の処理を行う。ＮＯの場合には、当該セルが
他のセルからポイント（参照）されていないから、フォ
ヮーディング・ポインタの値を設定することなく終了す
る。これにより、ガーベジコレクションの処理を高速に
行うことが可能となる。

図中■は、フォワーディング・ポインタのセットを行う
状態を示す。これは、第４図図中■に示すように、図中
■で新空間内にコピーしたセルへのポイントアドレスを
、面突閣内の旧セルに格納することを意味している。こ
れにより、第２番目以降に当該セルを参照した参照セル
のポインタを書き換えることが可能となる。

図中■は、新空間内のＲＥＦ−Ｂ　ＩＴをＯＮにセット
する状態を示す。これは、第４図図中■に示すように、
新空間内のセルのＲＥＦ−ＢＩＴｔ−ＯＮにセットして
複数のセルから参照されている旨を表示させるものであ
る。

図中■は、面突閣内のコピービットをＯＮにセットする
状態を示す。これは、第４図図中■に示すように、面突
閣内のコピービットをＯＮにして、当該セルを既に新空
間にコミピーした旨を表示することを意味している。

以上のように、複数の他のセルから参照されている参照
セルに対してのみ、参照関係情報（フォワーディング・
ポインタ）のセットを行うことにより、不必要な参照関
係情報をセットする手数を省略してガーベジコレクショ
ンの処理を高速に行うことが可能となる。

また、主記憶装置Ｉに設けた旧記憶領域１−１から新記
憶領域１−２に対するセルのコピーと、ビット操作用メ
モリ２中にこのセルのコピー情報および参照関係情報な
どのアクセスとを分離かつ独立にアクセス可能な態様で
設けることにより、並列に処理例えば第３図図中■と■
、■と■、■と■とを並列に処理して、ガーベジコレク
ション処理を高速に行うことが可能となる。また、第３
図図中■に関しても■の処理に並列に処理することが可
能となる。

次に、本実施例の第３図および第４図に示す構成による
所要時間と、第６図および第７図に示す従来の構成によ
る所要時間とを、簡単に以下比較する。

フォワーディング・ポインタのセントのオーバーヘッド
をτｆｐ／セル、ＲＥＦビット操作の平均オーバーヘッ
ドをτｂ、／′ビットとする。面突間にｎ個のアクティ
ブセルが存在し、単参照率（セルが１個のセルのみから
参照されている率）をｋ、セルがポイントする総数をｍ
とする。

本実施例によれば、フォヮーディング・ポインタのセッ
トおよびＲＥＦビット操作に要する時間Ｔ２は、下式の
ようになる。

Ｔ、＝τｒｐ（１−ｋ）　　Ｈｎ＋τｂａｒ　・ｎ＋　
２τｂ＋ａ　Ｈｎ＋（ｍ−ｎ）・τｂｓ”　τｒｐ（１
−ｋ）　　・ｎ＋　τ、（２ｎ＋ｍ）・・・・（１）ま
た、従来方式によれば、フォワーディング・ポインタの
セットに要するＴ１時間は、下式のようになる。

Ｔ、＝τ２．・ｎ　・・・・・・・・・・・・・・（２
）従って、ｎｋ／（２ｎ＋ｎ）　＞τ工／τ、が満足さ
れる場合に、本実施例のほうが効率が良くなる。

更に、本実施例は、ビット操作制御回路３を付加するこ
とにより、ビット操作が他の操作と並列に動作可能とな
り、このオーバーヘッドが見えなくなる（τ１．０とし
て）。この場合、式（１）は、下式のように簡単になる
。

Ｔ、＝　τｒ−（１−ｋ）　　・ｎ　・・・・・・・・
・・（３）これにより、従来方式の式（２）と比較する
と、τｆ、’ｎ　≧τｆ２（１−ｋ）・ｎ・・・・・・
・・（４）となり、本実施例が非常に効果的となる（通
常１≧に２０．９位）。

〔発明の効果〕

以上説明したように、本発明によれば、アドレスを動的
に割りつけたセルをアクセス可能な態様で格納する主記
憶装置と、セルに関する情報を独立にアクセス可能なり
様で格納するビット操作用メモリと、８亥当するセルに
関する情報をアクセス制御するビット操作制御回路とを
設け、主記憶装置中の旧記憶領域から新記憶領域に有為
なセルをコピーしてガーベジコレクションを行う際に、
ビット操作用メモリ中に７３ｆ数のセルから参照される
参照関係情報および旧記憶領域から新記憶領域にコピー
した旨を表すコピー情報を各セルに対応づけて夫々格納
し、参照関係情報が格納されていない旧記憶領域中のセ
ルに対して新記憶領域中の該当するセルに対するポイン
ト情報の格納を省略してガーベジコレクションを行う構
成を探用しているため、不要なフォワーディング・ポイ
ンタのセフ）を省略しかつ並列動作を行わせてガーベジ
コレクション処理を高速に行うことができる。

【図面の簡単な説明】

第１図は本発明の原理構成図、第２図は本発明の１実施
例樽成図、第３図は本発明の詳細な説明するフローチャ
ート、第４図は本発明の動作説明図、第５図はガーベジ
コレクションの概念説明図、第６図は従来方式の動作を
説明するフローチャート、第７図は従来方式の動作説明
図を示す。 図中、１は主記憶装置、２はビット操作用メモリ、３は
ビット操作制御回路、４はｃＰＵを表す。 ／Ｉ；う６明の匂力作１−ｓ’ｊ−ヨ目Ｔるフｏ−％−
Ｆ￥’＋３図 カ゛−へゾつレクシクン外刊り党を先日Ｊ［２１′ｇ１
５５　　図 １凭Ｌ１５Ｘ）〈の１力４１Ｌ名Ｚａ月するフローケヤ
ート第　６　圓

Claims (1)

1. 【特許請求の範囲】 記憶領域に動的に割りつけたセルのうち有為なものを新
   領域にコピーして不要となったセル領域を回収処理する
   ガーベジコレクション処理方式において、 アドレスを動的に割りつけたセルをアクセス可能な態様
   で格納する主記憶装置（１）と、 この主記憶装置（１）にアセクス可能な態様で格納した
   セルに対応づけて当該セルに関する情報を独立にアクセ
   ス可能な態様で格納するビット操作用メモリ（２）と、 このビット操作用メモリ（２）に対して該当するセルに
   関する情報をアクセス制御するビット操作制御回路（３
   ）とを備え、 主記憶装置（１）中の旧記憶領域から新記憶領域に有為
   なセルをコピーしてガーベジコレクションを行う際に、
   ビット操作用メモリ（２）中に複数のセルから参照され
   る参照関係情報および旧記憶領域から新記憶領域にコピ
   ーした旨を表すコピー情報を各セルに対応づけて夫々格
   納し、参照関係情報が格納されていない旧記憶領域中の
   セルに対して新記憶領域中の該当するセルに対するポイ
   ント情報の格納を省略してガーベジコレクションを行う
   よう構成したことを特徴とするガーベジコレクション処
   理方式。