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

Abstract

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

Description

【発明の詳細な説明】 （概要］ メモリ空間を２つに分割して、一方の分割空間に展開さ
れる使用中のデータ展開域のデータを、他方の分割空間
に連続的に並べて複写していくことで、不使用のデータ
展開域の再利用を実行するガーベジコし・クション処理
方式に関し、データ処理の実時間処理を損なうことなく
、データ展開域の再利用処理を実行できるようにするこ
とを目的とし、 メモリ空間の再利用を実行する再利用部は、他方の分割
空間に複写するときに、すべての複写が終ｒするまでの
間、複写元のデータ展開域にも同一データを残すように
構成する−とともに、複写元と複写先との間にポインタ
を設定し、かつ、メモリ空間を管理する管理部は、デー
タを書き換えるときには、そのデータを展開するデータ
展開域の持つポインタの指すデータ展開域についても書
き換えていくとともに、２つのデータ展開域の一致性の
検査処理を行うときには、そのデータ展開域の持つポイ
ンタの指すデータ展開域を考慮して検査処理を実行して
いくように構成する。

〔産業上の利用分野〕

本発明は、メモリ空間を２つに分割して、一方の分割空
間に展開される使用中のデータ展開域のデータを、他方
の分割空間に連続的に並べて複写してい（ことで、不使
用のデータ展開域の再利用を実行するガーベジコレクシ
ジン処理方式に関し、特に、データ処理の実時間処理を
損なうことなく、このデータ展開域の再利用処理を実行
できるようにするガーベジコレクシジン処理方式に関す
るものである。

Ｌ、　ｌ　Ｓ　Ｐ言語等のようなデータ領域を実行時に
獲得し、て管理していくようなタイプの言語では、２メ
モリ空間上に残されでいく不要となったメモリ領域を自
動的に回収して再利用に供するガーベジコレクションを
実行していくことになる。このガー＼、２゛コレクシッ
ンは、本来のデータ処理の実行が妨げられることなく実
行されるように構成していく必要がある。

［従来の技術］ ガーベジコレクションには、大きく分けて、フリ−リス
ト力弐とコピ一方式とがある。

このフリーリスト方式のガーベジコレクションは、飛び
飛びになっている再利用１１Ｊ能な空き領域を順にポイ
ンタでつないで、フリーリストにして管理していく方法
である。すなわち、第３図に示すように、使用ポインタ
を順に辿ることで使用中のメモリ領域を特定して使用中
である旨の記録を付け、続いて、この使用中の記録の付
かない不要なメモリ領域を選び出して、これらの不要な
メモリ領域を空きポインタでつなぐことでフリーリスト
を作成する。そして、新たにメモリ領域が必要になると
きには、このフリーリストから割り付けを行うように構
成するのである。

このフリーリスト方式のガーベジコレクションでは、使
用ポインタを辿る処理もフリーリストを作成する処理も
、通常のデータ処理の合間に少しずつ行うことができる
。そして、メモリ領域の移動処理をｉテわないので、ガ
ーベジコレクノツンの途中であってもデータを参照でき
ることになる。

但し、データの書き換えの場合には、既に走査済みのメ
モリ領域から未走査のメモリ領域を指すポインタを作ら
ないようにするために、スタック−・登録する等の処理
が必要になるが、参照処理に比べて書き換え処理の出現
頻度は低いことから、この処理も大きな負担とはならな
い、これから、このフリーリスト方式のガーベジコレク
ションに従うと、５データ処理の実時間処理を損なうこ
となくガーベジコレクションを実行できるという利点が
あるとともに、オーバヘッドも小さいという利点がある
、更に、これに加えて、汎用機上で効率良く実行できる
という利点もある。

しかしながら、フリーリスト方式のガーベジコレクショ
ンでは、メモリ領域の移動を行わないので、使用可能と
なるメモリ領域が細分化されてフリーリストにつなげら
れＬしまうために、大きなメモリ領域の獲得要求に対し
て対応できないという問題点がある。

これに対して、コピ一方式のガーベジコレクションは、
メモリ空間を２つに分割して、一方のメモリ分割空間の
使用状況が所定状態に達するときに、使用中のメモリ領
域のデータを他方のメモリ分割空間に連続的に並べて複
写していくことで、不使用のメモリ領域の再利用を図っ
ていく方法である。すなわち、第４図に示すように、使
用ポインタを順に辿ることで使用中のメモリ領域を順次
選択して、他方のメモリ分割空間に連続的に並べて複写
していく、このとき、複写元のメモリ領域に複写された
ものである旨の記録（複写マークの記録）を付けるとと
もに、複写先へのポインタを設定していく、続いて、す
べて−の複写処理が完了したら、複写元となったメモリ
分割空間へのポインタを切断していく、そして、新たに
メモリ領域が必要になるときには、この整理された使用
中のメモリ領域に続く連続の空きのメモリ領域から割り
付けを行うように構成するのである。

このコピ一方式のガーベジコレクションでは、フリーリ
スト方式と異なって、使用可能となるメモリ領域がまと
められていることから、大きなメモリ領域の獲得要求に
対応できるという利点がでてくることになる。そして、
ポインタ順に複写されているので、線型性も向上してい
る。また、汎用機上で効率良く実行できるという利点も
残されている。

しかしながら、ガーベジコレクションの途中では、ガー
ベジコレクシ式ン専用のポインタが張られることになる
ことから、通常のデータ処理を実行することができない
という問題点がある。すなわち、ガーベジコレクション
を実行するときには、本来のデータ処理を中断しなけれ
ば會−ならず、実時間処理の要求されるデータ処理装置
には実装できないという問題点があったのである。

このようなコピ一方式のガーベジコレクションの持つ欠
点を解消するために、通常のデータ処理の実行時にポイ
ンタを辿っていくときに、ガーベジコレクション途中に
記録される複写マークがあることを検出すると、その複
写マークの付けられたメモリ領域の持つポインタについ
ても辿るようにする従来技術もある。このようにすると
、コピ一方式のガーベジコレクションを少しずつ行うこ
とが可能になり、通常のデータ処理の中断を短時間にし
て、ガーベジコレクションを実行できることになる。

〔発明が解決しようとするｔｌｆｆ） しかしながら、ガーベジコレクション途中に記録される
複写マークも考慮してポインタを辿っていく方法を採る
と、ポインタを参照する度毎に、ガーベジコレクション
処理により記録される複写マークが記録されているか否
かの検査処理を実行して、その検査結果に従って、更に
ポインタを辿る処理を実行しなくてはならないことにな
る。これから、本来のデータ処理の性能を大きく劣化さ
せることで実時間処理を損なうことになるという問題点
が残されているのである。

これに対処するために、ハードディスク制御装置等で実
装されている透明ポインタのハードウェア機構を備えて
いくことが考えられる。この透明ポインタのハードウェ
ア機構を備えれば、有効アドレスの決定において、複写
元のメモリ領域を参照すると、自動的に複写先のメモリ
領域に切り換えられるようになることから、ポインタを
２回辿ることによる性能劣化を防ぐことができるのであ
る。しかしながら、このような透明ポインタを実装する
ためには、特別なハードウェア機構を備えていかなくて
はならないことから、汎用機には実装できないという新
たな問題点がでてくることになる。

本発明はかかる事情に鑑みてなされたものであって、メ
モリ空間を２つに分割して、一方の分割空間に展開され
る使用中のデータ展開域のデータを他方の分割空間に連
続的に並べて複写していくことで、不使用のデータ展開
域の再利用を実行するコピ一方式のガーベジコレクシジ
ン処理方式にあって、データ処理の実時間処理を損なう
ことなく、ガーベジコレクシジン処理を実行できるよう
にする新たなガーベジコレクション処理方式の提供を目
的とするものである。

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

第１図は本発明の原理構成図である。

図中、１は本発明を具備するデータ処理装置である。こ
のデータ処理装置１は、メモリ領域１０、プログラム展
開部１１、命令実行部１２、領域管理部１３及び領域再
利用部１４を備える。

このメモリ領域１０は、処理対象データを記憶するデー
タ展開域１５を展開し、プログラム展開部１１ば、所定
のデータ処理ｌｌ能を発揮するアプリケージぢンプログ
ラムを展開し、命令実行部１２は、プログラム展開部１
１の展開するプログラム記述を解読して実行し、領域管
理部１３は、メモリ領域１０の管理処理を実行し、ｇ域
再利用部１４は、例えば、メモリ領域１０の使用状況が
規定状態に達するときに、メモリ領域ｌＯの再利用を回
るべくコピ一方式のガーベジコレクシジン処理を実行す
る。

命令実行部１２は、領域管理部１３に対して、データ展
開域１５の参照処理や、データ展開域１５の作成処理や
、データ展開域１５の書き換え処理や、２つのデータ展
開域１５の内容比較の検査処理や、２つのデータ展開域
１５の一致性の検査処理を要求する。

領域管理部１３は、命令実行部１２から要求される処理
を実行して、その結果値を命令実行部１２に応答する。

領域再利用部１４は、メモリ領域１０を２つに分割して
、一方のメモリ領域１０に展開される使用中のデータ展
開域１５のデータを、他方のメモリ領域１０に連続的に
並べて複写していくことで、不使用のデータ展開域１５
の再利用を実行する。

この処理の実行にあたって、領域再利用部１４は、他方
のメモリ領域１０へのすべての複写処理が終了するまで
の間、複写元のデータ展開域１５にも同一データを残す
ように処理するとともに、複写元のデータ展開域１５と
複写先のデータ展開域１５との間にポインタ１６を設定
する。このポインタ１６は、好ましくは、主従の関係を
持たないで相互に相手方のデータ展開域１５を指す相互
ポインタでもって構成されることになる。

このように、領域再利用部１４は、他方のメモリ領域１
０へのすべての複写処理が終了するまでの間、複写元の
データ展開域１５にも同一データを残すように処理する
ことから、領域管理部１３は、領域再利用部１４の処理
途中であっても自処理を実行できるようになり、これが
ために、領域再利用部１４は、命令実行部１２の処理と
並行して少しずつメモリ領域の再編成処理を実行できる
ようになる。

Ｃ作用〕 本発明では、従来のコピ一方式のガーー、ジコレクショ
ン処理と異なって、７領域再利用部１４は、ガーベジコ
レクンランの処理中、複写元のデータ展開域１５にも同
一データを残すように構成する。

このように構成されるものであることから、領域管理部
１３は、命令実行部１２から発行されるデータ展開域１
５の参照処理要求や、２つのブタ展開域１５の内容比較
の検査処理要求を受は取るときに、その処理要求先のデ
ータ展開域１５が、ガーベジコレクン５ン途中に従って
もう一方の分割されるメモリ領域１０に複写されるもの
であっても、ポインタを辿ることな（直ちにそのデータ
を得ることができるので、発行される処理要求に対して
直ちに結果値を命令実行部１２に返すことができるよう
になる。

一方、領域管理部１３は、命令実行部１２から発行され
るデータ展開域１５の書き換え処理要求を受は取るとき
には、複写元のデータ展開域１５と複写先のデータ展開
域１５とが同一データを管理する構成を採っていること
に整合させて、書き換え要求のあるデータ展開域１５が
ポインタ１６を持っているときには、そのポインタ１６
の指すデータ展開域１５についても同一データに書き換
えていくように処理する。

また、領域管理部１３は、命令実行部１２から発行され
る２つのデータ展開域１５の一致性の検査処理要求を受
は取るときには、複写元のデータ展開域１５と複写先の
データ展開域１５とが同一データを管理する構成を採っ
ていることに対応させて、先ず最初に、検査要求のある
２つのデータ展開域１５が同一のデータ展開域１５であ
るか否かを判断し、この判断処理により、同一のデータ
展開域１５でないと判断するときには、次に、ポインタ
１６の指すデータ展開域１５も青酸して、検査要求のあ
る２つのデータ展開域１５が同一のデータ展開域１５で
あるか否かを判断していく。

例えば、ポインタ１６が、２つのデータ展開域１５を複
写先＊Ｓと複写元領域という主従関係を持つもので管理
する構成を採る場合には、検査対象のデータ展開［１５
が複写元領域の場合には、その複写先領域を求めて、こ
の複写先領域のデータ展開域１５同士が同一のデータ展
開域１５となるものであるか否かにより、検査要求のあ
る２つのデータ展開域１５が同一のデータ展開域１５で
あるか否かを判断していくことになる。このとき、ポイ
ンタ１６を主従関係のない相互ポインタで構成すれば、
検査要求のある２つのデータ展開域１５のいずれか一方
についてのみ相互ポインタの指すデータ展開域１５を特
定して、この特定してデータ展開域１５と、検査要求の
ある残りのデータ展開域１５との同一性の検査処理を実
行することで一致性の検査処理を実行できるので、複写
先領域への正規化処理に基づくオーバヘッドをなくすこ
とができる。

このように、本発明によれば、領域再利用部１４による
ガーベジコレクシジンの途中であっても、領域管理部１
３は、命令実行部１２からの処理要求を実行できるとと
もに、最も頻繁に要求されるデータの参照処理要求に対
して、ポインタの追跡処理を実行せずに直ちにデータを
読み出せるようになることから、本来のデータ処理の性
能の劣化を最小限に止められることになるのである。

［実施例］ 以下、実施例に従って本発明の詳細な説明する。

第２図に、第１図で説明した領域再利用部１４が実行す
る本発明に係るコピ一方式のガーベジコレクシジンの一
実施例を図示する。この図において、左側の部分が、ガ
ーベジコレクシジンの処理途中のメモリ空間状態を図示
しており、右側の部分が、ガーベジコレクシジンの完了
後のメモリ空間状態を図示しである。ここで、左側の部
分では、ポインタの線が煩雑になるのを防ぐために、便
宜上、分割される２つのメモリ空間を離して図示しであ
る。

この図に示すように、本発明では、ガーベジコレクシジ
ンの実行に従って、旧空間（左側の分割メモリ空間）か
ら新空間（右側の分割メモリ空間）への複写を実行する
ときに、領域再利用部１４は、旧空間の複写元の領域に
ついても、すべての領域についての複写処理が完了する
までの間、同一データを残すように処理することを特徴
としている。

そして、領域再利用部１４は、この２つの複写元の領域
と複写先の領域とが、主従の関係を持たないで相互に相
手方の領域を指す相互ポインタ２０（図中の太線のポイ
ンタ）を持つように処理することを特徴としている。こ
の相互ポインタ２０は、ガーベジコレクシジンの処理途
中であっても複写されていない領域では使用されること
はなく、また、ガーベジコレクシジンの処理途中以外で
は使用されることはないので、そのようなときには、図
中にも示すように、自らの領域自身を指すように設定さ
れることになる。

この構成を採るものであることから、第１図で説明した
領域管理部１３は、メモリ空間を参照する必要がある場
合に、その参照先の領域がガーベジコレクシジンによる
複写中の領域であるものであっても、直ちに参照すべき
データを得ることができるようになるのである。そして
、例えば、第２図の処理途中の図において、右側の分割
メモリ空間の「Ａ」からも「Ｃ」が得られ、左側の分割
メモリ空間の「Ａ」からも「Ｃ」が得られるというよう
に、複写元の領域を指しているポインタを辿っても、複
写先の領域を指しているポインタを辿っても、本来必要
となる同一内容のデータを得ることができるようになる
のである。

一方、この構成を採ることに合わせて、領域管理部１３
は、領域の書き換えを行う場合には、複写元の領域を書
き換えるときには複写先の領域についても書き換え、複
写先の領域を書き換えるときには複写元の領域について
も書き換えるように処理することになる。また、フリー
リスト方式のガーベジコレクションと同様に、走査済み
の領域から旧字間を指すポインタを作らないようにする
ために、指す先の領域を新空間に複写してそれへのポイ
ンタを格納していくことになる。

そして、この構成を採ることに合わせて、領域管理部１
３は、領域自体の一致性の検査処理を行う場合、検査対
象のポインタ同士を比較するだけてはなくて、相互ポイ
ンタ２０も考慮して比較処理を行っていくことになる。

次に、ＬＩＳＰ言語の処理系を例にして、領域管理部１
３と領域再利用部１４の実行する処理について説明する
。

領域管理部１３は、第１図で説明した命令実行部１２か
ら新領域の獲得処理要求であるｒｃｏｎＳ」の発行を受
は取ると、 （１，１）ガーベジコレクション中の場合は、後述する
（６）で説明するガーベジコレクションの続行処理を行
う。

（１，２）ガーベジコレクション中ではないが、４現空
間に空きがない場合には、後述する（５）で説明するガ
ーベジコレクションの起動処理を行う。

（１，３）現空間中に要求の領域を割り付ける。

という処理を実行していく、ガーベジコレクションは、
後述するように、領域管理部１３の処理の中断時間が規
定値に達すると中断されることになるので、（１，１）
　（１，２）の処理時点からその規定値の中断時間に達
すると、（１，３）の処理の実行に入ることになる。こ
のようにして、新領域の獲得要求毎にガーベジコレクシ
ョンが少しずつ実行されていくことになる。

領域管理部１３は、命令実行部１２から、指定されるポ
インタの指す領域の参照処理要求であるｒ（ａｒ」’ｒ
ｅｄｒ」の発行を受は取ると、（２，１）その参照要求
先の領域のｃａｒ部／　ｃ　ｄ　ｒ部を参照して、命令
実行部１２に返す。

という処理を実行する。上述したように、本発明では、
ガーベジコレクション途中の複写元の領域についてもデ
ータを残すように構成していることから、参照要求先の
領域が旧字間にあるものであっても、更にポインタを辿
ることなく直ちに所望のデータを参照できるのである。

領域管理部１３は、命令実行部１２がら、指定されるポ
インタの根元の領域の領域内容の書き換え処理要求であ
るｒｒｐｌａｃａ」　ｒｒｐｌａｃｄ」の発行を受は取
ると、 （３，１）ガーベジコレクション中でない場合は、書き
換え要求のある領域を新内容に書き換える処理を行う。

（３，２）ガーベジコレクション中の場合は、次の処理
を行う。

（３，２，１）書き換え要求のある領域が新空間の走査
済み領域であり、指定のポインタが旧空間内の領域を指
すとき、その旧字間の領域の複写処理を行って、その指
定のポインタが新空間内を指すものに変える。このとき
の複写処理は、後述する（７）の処理に従って実行され
る６ （３，２，２）書き換え要求のある領域を新内容に書き
換える。

（３゜２．３）　？１写相手のポインタを辿って、もう
一方の領域も新内容で書き換える。

という処理を実行する。

領域管理部１３は、命令実行部１２がら、指定される２
つのポインタの指す領域の一致性の検査処理要求である
’ｅＱＪの発行を受は取ると、（４，１）指定の２つの
ポインタの指す領域を比較して、同一領域を指していれ
ば真と判断して命令実行部１２に返す。

（４，２）　（４，１）の判断で、同一領域を指してい
ないと判断するときには、いずれか一方の領域の持つ相
互ポインタ２０が他方の領域を指しているか否かを比較
して、同一領域を指していれば真と判断して命令実行部
１２に返す。

（４，３）それ以外は偽と判断して、命令実行部１２に
返す。

という処理を実行する。〔作用〕の欄で説明したように
、複写元と複写先の領域とを主従関係のない相互ポイン
タ２０でもってポイントしているので、領域管理部Ｉ３
は、このＮ域自体の一致性検査処理を少ないオーバヘッ
ドでもって実行できるようになる。

領域再利用部１４は、領域管理部１３からガーベジコレ
クションの起動処理要求を受は取ると、（５，１）現空
間を旧交間とし、もう１つの空間を現空間に設定する。

（５，２）走査済み領域を無しに初期設定する。

（５，３）ルート（最も根元になる領域を指す）が指す
領域について複写処理を行う、このときの複写処理は、
後述する（７）の処理に従って実行される。

（５，４）状態を“複写中１にセントする。

（５，５）ガーベジコレクションの続行処理を行う。

このときの続行処理は、後述する（６）の処理に従って
実行される。

という処理を実行する。

領域再利用部１４は、ガーベジコレクションの超勤続行
要求を受は取ると、 （６，ＩＮＪＩ域管理部１３の処理の中断時間が許容範
囲に収まるまでの回数、以下の処理を行う。

（６，２）状態が“複写中”の場合、未走査領域を１つ
選択して次の処理を行う。

（６，２，１）その未走査開城から指す領域を複写処理
し、新領域を指すように更新する。このときの複写処理
は、後述する（７）の処理に従って実行される。

（６，２，２）その未走査領域を走査済み領域とする。

（６，２，３）未走査領域が無くなれば、状態を”後始
末中”にセットして、全領域を未走査領域とする。

（６，３）状態が“後始末中２の場合、未走査領域を１
つ選択して次の処理を行う。

（６，３，１）複零相手を指す相互ポインタ２０を自分
自身を指すように変える。

（６，３，２）この領域を走査済み領域とする。

（６，３，３）未走査領域が無くなった場合、ガーベジ
コレクシッン終了とする。

という処理を実行する。

領域再利用部１４は、複写処理要求を受は取ると、 （７，１） （７，２） 複写要求のある領域が新空間にある場合は、何もせず、
そのままの領域のポインタを返す。

複写要求のある領域が旧交間にあるが、既に複写相手を
持っている場合、複写相手へのポインタを返す。

（７，３）その他の場合、次の処理を行う。

（７，３，１）新空間に領域を確保し、内容を該領域か
ら複写する。このとき、旧交間の複写元の領域にも内容
をそのまま残しておく。

（７，３，２）新空間の領域は未走査領域きする。

（７，３，３）複写相手との間に相互ポインタ２０を設
定する。

（７，３，４）新領域を指すポインタを返す。

という処理を実行する。

〔発明の効果〕

以上説明したように、本発明によれば、コピー方式のガ
ーベジコレクション処理方式を実装していく場合、ガー
ベジコレクションの実行のために中断されるデータ処理
の中断時間を極めて短いものにできるようになる。これ
から、データ処理の実時間処理を損なうことなく、ガー
ベジコレクシボンを実行できるようになるのである。

【図面の簡単な説明】

第１図は本発明の原理構成図、 第２図は本発明の一實施例、 第３図はフリーリスト方式ガーベジコレクションの説明
図、 第４図はコピ一方式ガーベジコレクションの説明図であ
る。 回申、１はデータ処理装置、１０はメモリ領域、１１は
プログラム展開部、１２は命令実行部、１３は領域管理
部、１４は領域再利用部、１５はデータ展開域、１６は
ポインタ、２０は相互ポインタである。

Claims (2)

【特許請求の範囲】
1. （１）メモリ空間を管理する領域管理部（１３）と、該
   メモリ空間を再編成する領域再利用部（１４）とを備え
   、該領域再利用部（１４）が、メモリ空間を２つに分割
   して、一方の分割空間に展開される使用中のデータ展開
   域のデータを、他方の分割空間に連続的に並べて複写し
   ていくことで、不使用のデータ展開域の再利用を実行す
   るように構成されるデータ処理装置において、 上記領域再利用部（１４）は、他方の分割空間にデータ
   を複写するときに、該分割空間へのすべての複写処理が
   終了するまでの間、複写元のデータ展開域にも同一デー
   タを残すように構成するとともに、複写元のデータ展開
   域と複写先のデータ展開域との間にポインタ（１６）を
   設定するよう構成し、かつ、上記領域管理部（１３）は
   、データを書き換えるときには、該データを展開するデ
   ータ展開域の持つ上記ポインタ（１６）の指すデータ展
   開域についても同一データに従って書き換えていくとと
   もに、２つのデータ展開域の一致性の検査処理を行うと
   きには、該データ展開域の持つ上記ポインタ（１６）の
   指すデータ展開域を考慮して一致性の検査処理を実行し
   ていくように構成されてなることを、特徴とするガーベ
   ジコレクション処理方式。
2. （２）請求項（１）記載のガーベジコレクション処理方
   式において、 複写元のデータ展開域と複写先のデータ展開域との間に
   設定されるポインタ（１６）が、主従の関係を持たない
   で相互に相手方のデータ展開域を指す相互ポインタでも
   って構成され、 領域管理部（１３）は、２つのデータ展開域の一致性の
   検査処理を行うときにあって、検査要求のある２つのデ
   ータ展開域が同一のデータ展開域でないと判断するとき
   には、いずれか一方のデータ展開域の持つ上記相互ポイ
   ンタを特定して、その特定された相互ポインタの指すデ
   ータ展開域と、検査要求のある残りのデータ展開域とが
   同一のデータ展開域であるのか否かを検査していくこと
   で、検査要求のある２つのデータ展開域の一致性の判断
   処理を実行していくよう構成されてなることを、特徴と
   するガーベジコレクション処理方式。