JPH03194630A - ガーベジコレクション処理方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔概　要〕 計算機の言語処理系が自動処理するメモリ管理における
ガーベジコレクションに関し、処理が速く、結果のプロ
グラムの実行効率も良いガーベジコレクション処理方式
を目的とし、メモリと、アクセス部と、メモリ管理部を
有し、該アクセス部は、所定の要求により該メモリの所
定の記憶領域にオブジェクトを生成し、及び該オブジェ
クトを無効化し、各該オブジェクトはポインタで指示さ
れたリスト構造のデータ要素であり、該メモリ管理部は
、所定のガーベジコレクション処理の場合に、該記憶領
域上の有効な該オブジェクトのみについて、該リスト構
造の上位レベルから順次下位レベルへ、該レベルごとに
属するすべての該オブジェクトを順次所定の記憶領域へ
移動し、該移動したオブジェクトから該ポインタで指示
する下位の該オブジェクトがある場合には、該下位の１
オブジェクトのみを該移動したオブジェクトに続けて移
動するように構成する。

〔産業上の利用分野〕

本発明は、計算機における、言語処理系がメモリ管理を
自動処理するシステムのガーベジコレクシジン処理方式
に関する。

［従来の技術〕 計算機のプログラミング言語として公知の、例えばＬＩ
ＳＰ言語等で記述されたプログラムを実行するための言
語処理系では公知のように、プログラム及びデータ等の
オブジェクトを、メモリ内に切り出したヒープ等と呼ば
れる作業空間に生成して処理する。なお、オブジェクト
は例えば所定のルートからポインタで連結して木構造を
なすように生成した、リスト構造をなす。

その場合にオブジェクトは、プログラムの実行中に生滅
するので、放置すると空き領域が無くなり、又広範囲に
分散する有効なオブジェクトへのアクセスは、ページン
グを頻発させて実行効率を低下させるようになる。そこ
で、適当な時に公知のガーベジコレクション処理を行っ
て、そのとき残っている有効な各オブジェクトを、なる
べ（小領域にまとまるように移動し、又空き領域を作り
出すことが必要になる。

第４図（ａ）はオブジェクトのリスト構造の一部をなす
２レベルの部分の例を示し、図中に丸付き数字で区別し
た各長方形で各オブジェクト、各矢印でポインタの指示
を説明的に示すものである。

ガーベジコレクションの一方法である第１の方法（公知
のｂｒｅａｄｔｈ−ｆｉｒｓｔ法、以下においてＢＦ法
とする）では、リスト構造の各レベルごとに上位レベル
から順次下位レベルへ、各レベルごとに属するすべての
オブジェクトを順次所定の記憶領域へ移動する方法であ
るので、第４図（ａ）の例の場合■、■、−・■を先ず
処理した後、次のレベルに下りて■、■、■−−−−−
のように処理してオブジェクトを移動し、移動先の記憶
領域には第４図（ｂ）に示す様にオブジェクトが詰めら
れる。

又、第２の方法（公知のｄｅｐｔｈ−ｆｉｒｓｔ法、以
下にＤＦ法とする）では、リスト構造の上位レベルから
始めて、移動したオブジェクトから順次下位レベルの方
向へポインタでつながるオブジェクトを優先して所定の
記憶領域へ移動する方法であって、第４図（ａ）の例の
場合■を移動すると、次は例えば■に下り、更に下位が
あれば下方へたどり、末端に達するとルベルずつ戻って
、別のポインタがあればそのポインタの先を下方へたど
る、というように深さ方向を優先して処理するので、図
の場合■で終われば次は■に戻って■に下り、■につな
がるものをすべて処理した後■に移るというように進み
、その結果移動先の記憶領域には第４図（Ｃ）に示す様
にオブジェクトが詰められる。

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

以上の説明と、第４図０））及び（Ｃ）に゛示す処理結
果の例からも容易に推測できるように、前記ＢＦ法は、
ガーベジコレクションの処理は比較的簡単で高速に処理
できるが、第４図ら）に示す様に処理結果ではポインタ
でつながるオブジェクトが離れた位置に置かれる結果に
なり、いわゆる局所性が悪くなって、このプログラムを
実行する場合にべ−ジングを増加させて実行効率を悪化
する。

それに対しＤＦ法では、第４図（Ｃ）を（ｂ）の状態と
比較して明らかなように、結果のオブジェクトの局所性
が良いが、前記処理の説明のようにオブジェクトを下方
にたどった後、逆に上方にたどって戻る必要があるので
、比較的処理が複雑化して遅くなる。

本発明は、従来の処理の欠点を改良し、処理が速く、処
理結果のプログラムの実行効率も良いガーベジコレクシ
ョン処理方式を目的とする。

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

第１図は、本発明の構成を示すブロック図である。図は
ガーベジコレクション処理方式の構成であって、メモリ
１と、アクセス部２と、メモリ管理部３を有し、アクセ
ス部２は、所定の要求によりメモリ１の所定の記憶領域
４にオブジェクトを生成し、及び該オブジェクトを無効
化し、各該オブジェクトはポインタで指示されたリスト
構造のデータ要素であり、メモリ管理部３は、所定のガ
ーベジコレクション処理の場合に、記憶領域４上の有効
な該オブジェクトのみについて、該リスト構造の上位レ
ベルから順次下位レベルへ、該レベルごとに属するすべ
ての該オブジェクトを順次所定の記憶領域５へ移動し、
該移動したオブジェクトから該ポインタで指示する下位
の該オブジェクトがある場合には、該下位の１オブジェ
クトのみを該移動したオブジェクトに続けて移動する。

又、前記メモリ管理部３は、前記ガーベジコレクション
処理を行う場合に所定の条件を識別して、該所定の条件
が第１の条件の場合のみ前記の処理を実行し、該所定の
条件が第２の条件の場合には、該上位レベルから順次該
下位レベルへ、該レベルごとに属するすべての該オブジ
ェクトを順次所定の記憶領域５へ移動し、該所定の条件
が第３の条件の場合には、該上位レベルから始めて、移
動した該オブジェクトから順次下位レベルの方向へポイ
ンタでつながる該オブジェクトを優先して所定の記憶領
域５へ移動する。

〔作　用〕

この処理方式により、本発明で加えられたガーベジコレ
クションの処理方法（ＢＤ法とする）による場合には、
処理結果のオブジェクトは深さ方向にも一部まとめられ
るので、前記ＢＦ法の場合より局所性を増すが、深さ方
向はルベルのみ下がるので、前記ＤＦ法程には処理を複
雑化せず高速に処理でき、ガーベジコレクションの速度
と処理結果のオブジェクトの実行効率とを共に適当に満
足できる。又メモリ管理部に、このＢＤ法の他に、従来
のＢＦ及びＤＦ法も備えて、所定の条件で処理方法を選
択できるようにして、例えば処理頻度の多いガーベジコ
レクション（従ってオブジェクトの寿命は比較的短い）
の場合は処理速度を重視してＢＦ法を用い、処理頻度が
少ない（オブジェクトの寿命が長い）場合は処理結果の
実行効率を重視してＤＦ法を用い、それらの中間的な場
合はＢＤ法を使用するように条件を設定すれば、ガーベ
ジコレクシジンに費やす時間と結果の実行効率とを共に
適切に改善することができる。

〔実施例〕

第４図（ｄ）は、（ａ）に例示したオブジェクトを本発
明のＢＤ法によるガーベジコレクションで移動した状況
を説明する図である。

メモリ管理部３は第４図（ａ）のオブジェクトを、前記
ＢＦ法と同様に上位レベルから、同じレベルの処理を優
先して移動して、順次下位レベルへ下がるが、但し例え
ばオブジェクト■を移動したときに、■のポインタで指
示する下位オブジェクトがあれば、その内の１ポインタ
で指示する１オブジェクト、例えば■を続けて移動しく
複数のポインタがある場合には、例えば無条件に一定の
位置のポインタを選ぶように定めておく）、その後■と
同レベルの次のオブジェクト（この場合はオブジェクト
■）の処理に戻る。

このようにして、例えば■、■、■、■・・−・・のよ
うに処理を進めて、そのレベルの最後の■及びそれにつ
ながる■を処理してルベルの処理を終わると、次はルベ
ル下がって、そのレベルに残るオブジェクトを処理する
ために、例えばオプジェツト■から処理をし、更に下位
のレベルがあれば■、■の下位の１オブジェクト、■、
■の下位の１オブジェクト・・−−−一−・のように、
処理を進め、第４図（ｄ）のようにオブジェクトを詰め
る。

この処理方法を使用してガーベジコレクションを行う場
合に、第１図のメモリ管理部３は、メモリ１を例えば第
２図に示すように固定領域、現領域及び新領域に分け、
現領域の中に新入領域と滞留領域を設けて管理する。

アクセス部２は、新しいオブジェクトをすべて新入領域
に順次生成しながらプログラムを実行し、例えば新入領
域の空きが、ある所定値より少なくなる等を契機として
、ガーベジコレクションの処理を行うためにメモリ管理
部３を起動する。

例えば第２図（ａ）は初期状態の後ガーベジコレクショ
ンを１同経た状態として、（ａ）の状態でガーベジコレ
クションを行うと、その新入領域及び滞留領域の有効な
オブジェクトを、新領域側にそれぞれ移して、（ｂ）の
ように現領域と新領域とを交換した状態にする、なお滞
留領域には、以前に新入領域にあったオブジェクトが、
後述のようにして移されているものとする。

更に実行が進み、再びガーベジコレクシジンを行うと、
再び前記のように現領域と新領域とを交換して（Ｃ）の
状態に戻る。以上のような処理を続けて、（Ｃ）の状態
のガーベジコレクションをする時、所定の回数繰り返し
ているか、又はその他所定の条件になっていると、その
場合のガーベジコレクションでは、（ｄ）のように滞留
領域のオブジェクトを固定領域へ移し、新入領域のオブ
ジェクトを新たな現領域の滞留領域に移す。

従って、固定領域には、何回かのガーベジコレクション
に耐えたので、なお以後も有効状態で生き残る可能性が
高いと見なされるオブジェクトが保持されるので、常時
のガーベジコレクションでは固定領域は処理対象とせず
、固定領域が大きくなり過ぎて十分な大きさの現領域及
び新領域を確保できなくなる等の特別の状態になったと
きのみ、例えば（Ｃ）の状態から（ｅ）〜（２）のよう
に固定領域を新しく設けて移動し、固定領域のガーベジ
コレクションを行う。

以上においてメモリ管理部３は、ガーベジコレクション
の対象領域と移動先とにより、ガーベジコレクションに
使用する処理方法を選択する（図にＢＰ、　ＤＦ、　Ｂ
Ｄで、それぞれの処理方法を示す）。

即ち、滞留領域及び新入領域について、現領域から新領
域へ移動する際（（ａ）から（ｂ）、Φ）から（Ｃ）、
及び（Ｃ）の新入領域から（ｄ）の滞留領域）は、最も
高速に処理できる前記ＢＦ法でガーベジコレクションを
実行し、滞留領域から固定領域への移動（（Ｃ）から（
ｄ））はＢＤ法でガーベジコレクションを実行してオブ
ジェクトの実行効率を改善する。又、前記のようにして
稀に発生する固定領域内のガーベジコレクションの場合
には、処理結果のオブジェクトの実行効率を重視してＤ
Ｆ法によって処理を実行する。

第３図はメモリ管理部３のガーベジコレクシジンの処理
の流れの一例を示す図であり、所定の契機で起動される
と、処理ステップ１０で固定領域の処理を要するか識別
し、固定領域を処理しない通常の場合は、処理ステップ
１１に進む。

処理ステップ１１で何回目のガーベジコレクションかを
適当なカウンタで識別して、例えば４回目になっていな
ければ、処理ステップ１２に進んでカウンタを＋１した
後、処理ステップ１３でＢＦ法のガーベジコレクシジン
により、新入領域及び滞留領域の有効オブジェクトを、
新しい新入領域及び滞留領域へそれぞれ移動し、処理ス
テップ１４で新しい現領域と新領域を設定して処理を終
わる。

処理ステップ１１でカウンタが４回目を示したとき（例
えば第２図（Ｃ）から（ｄ）に移る場合）は、処理ステ
ップ１５でカウンタを０にリセットし、処理ステップ１
６でＢＤ法により、滞留領域の有効オブジェクトを固定
領域へ移動する。又、処理ステップ１７でＢＦ法のガー
ベジコレクシジンにより、新入領域の有効オブジェクト
を新しい滞留領域へ移動した後、処理ステップ１４で新
しい現領域と新領域を設定して処理を終わる。

又、処理ステップ１０で固定領域の処理を要するガーベ
ジコレクションであると識別した場合は、処理ステップ
１８．１９で処理ステップ１６．１７の場合と同様のガ
ーベジコレクションによって、新入領域及び滞留領域の
処理をした後、処理ステップ２０でＤＦ法のガーベジコ
レクションによって固定領域の有効オブジェクトを新し
い固定領域へ移動して固定領域を作り、処理ステップ１
４で新しい現領域と新領域を設定して処理を終わる。

以上ではガーベジコレクション時の移動先等の一定の条
件によって、常に自動的に処理方法を選択する例を示し
たが、例えば利用者がガーベジコレクションの処理方法
を指定して、例えばガーベジコレクションは遅くても実
行を速くするような選択ができるように、特定の処理方
法を指定する適当な指定手段を設けてもよく、又例えば
システムがメモリの使用状況等を観測して、処理方法を
動的に決定するようにしてもよい。

〔発明の効果］ 以上の説明から明らかなように本発明によれば、計算機
における、言語処理系が自動処理するメモリ管理の処理
において、ガーベジコレクションの頻度等から、ガーベ
ジコレクションに費やす時間と、処理結果のオブジェク
トの実行効率とを勘案シテ、適切なガーベジコレクショ
ンの処理方法を選択し、システムの総合的な処理効率を
改善できるという著しい工業的効果がある。

【図面の簡単な説明】

第１図は本発明の構成を示すブロック図、第２図はメモ
リの状況を説明する図、 第３図は本発明の処理の流れ図、 第４図はオブジェクトの状態を説明する図である。 図において、 １はメモリ、　　　　　　２はアクセス部、３はメモリ
管理部、　　４．５は記憶領域１０〜２０は処理ステッ
プ 本発明の構成を示すブロック図 第１図 メモリの状況を説明する図 第２図 本発明の処理の流れ図 オブジェクトの状態を説明する図 第 図

Claims (1)

1. 【特許請求の範囲】 １、メモリ（１）と、アクセス部（２）と、メモリ管理
   部（３）を有し、 該アクセス部（２）は、所定の要求により該メモリ（１
   ）の所定の記憶領域（４）にオブジェクトを生成し、及
   び該オブジェクトを無効化し、 各該オブジェクトはポインタで指示されたリスト構造の
   データ要素であり、 該メモリ管理部（３）は、所定のガーベジコレクション
   処理の場合に、該記憶領域（４）上の有効な該オブジェ
   クトのみについて、該リスト構造の上位レベルから順次
   下位レベルへ、該レベルごとに属するすべての該オブジ
   ェクトを順次所定の記憶領域（５）へ移動し、該移動し
   たオブジェクトから該ポインタで指示する下位の該オブ
   ジェクトがある場合には、該下位の１オブジェクトのみ
   を該移動したオブジェクトに続けて移動するように構成
   されていることを特徴とするガーベジコレクション処理
   方式。 ２、前記メモリ管理部（３）は、前記ガーベジコレクシ
   ョン処理を行う場合に所定の条件を識別して、該所定の
   条件が第１の条件の場合のみ請求項１記載の処理を実行
   し、 該所定の条件が第２の条件の場合には、該上位レベルか
   ら順次該下位レベルへ、該レベルごとに属するすべての
   該オブジェクトを順次所定の記憶領域へ移動し、 該所定の条件が第３の条件の場合には、該上位レベルか
   ら始めて、移動した該オブジェクトから順次下位レベル
   の方向へポインタでつながる該オブジェクトを優先して
   所定の記憶領域へ移動することを特徴とする請求項１記
   載のガーベジコレクション処理方式。