JPH0410143A - ガーベジ・コレクション方法 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、コンピュータ等の記憶装置において使用済み
になった記憶領域を利用可能な形に整理するガーベジ・
コレクション（ｇａｒｂａｇｅ　ｃｏｌ　１ｅｃｔｏｎ
、不要情報整理）、特にそのコピー方式（複写方式）に
関するものである。

（従来の技術〉 従来、この種のガーベジ・コレクション方法には、特開
昭６２−２２１７４８号公報に記載されるようなものが
あった。

従来、Ｌｉ５ｐ言語（ｌｉｓｔ　ｐｒｏｃｅｓｓｉｎｇ
　Ｉａｎｇｕａｇｅ、リスト処理を目的とした言語）や
、ｐｒｏｌＯｇ言語（ｐｒｏｇｒａｍｍｉｎｇ　ｉｎ　
ｌｏｇｉｃ、論理式の記述法をプログラム言語化したも
の）に代表されるような、つなぎ（ポインタ）のあるデ
ータ構造を扱う記号処理装置では、中央処理装置（以下
、ＣＰＵという）によるプログラム制御等により、文章
処理や図形処理等といった多数のデータ処理を行う。そ
れ故、記憶装置におけるデータ領域を有効利用するため
に、処理の進行（ポインタの切断等）と共に、使用され
なくなったデータ領域を再使用可能にするための記憶空
間管理方法であるガーベジ・コレクション方法が使用さ
れている。

このガーベジ・コレクション方法には、コピー方式と呼
ばれる方法がある。この方式では、記憶空間を２つに分
けて一時的にはどちらか一方の空間だけをデータ領域に
使用し、ガーベジ・コレクション時において、使用中の
記憶空間から、使用されているデータのみを未使用の記
憶空間にコピーする。使用中の記憶空間における使用さ
れているデータを決めるには、プロセスのスタックやシ
ステムの静的なデータ領域から、つなぎ（ポインタ）を
たどりながう、印付け（マーキング）を行う。印付けさ
れなかったデータ領域が、不要データとなり、再使用可
能なデータ領域となる。

この種のコピー方式のガーベジ・コレクション方法では
、記憶空間を２分割して使用しているため、使用可能な
自由領域が全記憶空間の半分になって多量のデータを扱
うことができない。また、ガーベジ・コレクションの際
に、全自由領域をサーチして印付けされた使用中のデー
タ領域を複写用記憶空間に圧縮してコピーするので、は
とんど全仮想空間へのアクセスとなり、その結果、ペー
ジフォルトが多発しなり、プログラムのような固定的で
かつ部分的なデータ領域の無駄なコピー等で、処理速度
が低下するという問題があった。

そこで、この問題を解決するため、前記文献の技術では
、記憶空間を３以上の複数に分割し、記憶空間管理テー
ブルを設け、ガーベジ、コレクション時に不要データの
最も多い分割領域を対象とする方法が提案されている。

この方法では、記憶空間を２つに分けた場合よりも、使
用できる記憶空間の割合が高くなり、ガーベジ・コレク
ションを行う領域を、分割した領域単位に行うことがで
きる。

（発明が解決しようとする課題） しかしながら、前記文献の方法では、次のような課題が
あった。

前記文献のような記憶空間を３以上の複数に分割する方
法では、ガーベジ・コレクション起動時に、コピー対象
の分割領域を決定するために不要データを特定するため
の印付け（使用中のデータ領域を表示するための印付け
）がされていなければならない。ところが、印付は処理
は、使用している全ての記憶空間を処理の対象とし、デ
ータのつなぎをたどる必要がある。そのため、ガーベジ
・コレクション時において、分割した１つの領域を複写
用領域にコピーする度に、印付は処理を行うことが必要
となり、煩雑な印付は処理による処理速度の低下を招く
という問題があり、それを解決することが困難であった
。

本発明は前記従来技術が持っていた課題として、記憶空
間を３以上の複数に分割する方法において、ガーベジ・
コレクション時の煩雑な印付は処理による処理速度の低
下の点について解決したガーベジ・コレクション方法を
提供するものである。

（課題を解決するための手段） 本発明は前記課題を解決するために、信号処理装置に用
いられるコピー方式のガーベジ・コレクションの対象と
なる記憶空間を３以上の複数の分割領域に分割し、その
分割領域内の少なくとも１つを複写用分割領域として使
用し、前記各分割領域の情報を記憶空間管理テーブルで
管理して、前記複写用分割領域以外の分割領域から、使
用中のデータのみを前記複写用分割領域へコピーするガ
ーベジ・コレクション方法において、次のような手段を
講じたものである。

すなわち、本発明では、ガーベジ・コレクション時に、
前記記憶空間管理テーブルにより、前記使用中のデータ
を表示する印付は処理を前記分割領域毎に管理し、前記
分割領域に対する不要データ回収処理の有効性を判定し
、その判定結果に基づき前記印付は処理を制御するよう
にしたものである。

（作用） 本発明によれば、以上のようにガーベジ・コレクション
方法を構成したので、ガーベジ、コレクション時におい
て、記憶空間管理テーブルを参照して、使用中のデータ
を表示する印付は処理を、記憶空間の分割領域毎に管理
する。そして、この分割領域に対する不要データ回収処
理の有効性を判定し、その判定結果に基づき印付は処理
を制御することにより、記憶空間の使用情況に合わせて
印付は処理を行うか否かの判断と、その制御が行われ、
それによってガーベジ・コレクション時における印付は
処理の軽減化が図れる。従って、前記課題を解決できる
のである。

（実施例） 第１図は本発明の実施例を示すガーベジ・コレクション
方法のフローチャート、第２図は第１図の方法が適用さ
れる記号処理装置におけるメモリ管理の機能ブロック図
、及び第３図は第２図中の記憶空間管理テーブル及び記
憶空間を示す図である。

先ず、第２図及び第３図を参照しつつ、記号処理装置に
おけるメモリ管理の機能ブロックについて説明する。

第２図に示すメモリ管理の機能ブロックは、ＣＰＵによ
り実行される記号処理プログラムによって制御されるメ
モリ管理部１０と、そのメモリ管理部１０によってデー
タのアクセス及びガーベジ・コレクションが制御される
記憶装置の記憶空間２０とを、備えている。

メモリ管理部１０は、記号処理プログラムに従ってメモ
リ管理部１０全体を制御する記憶空間管理部１１と、ガ
ーベジ・コレクションにおける回収処理を行う回収制御
部１２と、ガーベジ・コレクションにおける印付は処理
を行う印付は制御部１３と、記憶空間管理テーブル１４
とを、備えている。記憶空間管理部１１は、記号処理プ
ログラムによる新しいデータ領域の要求やデータの参照
及び変更命令に基づき、記憶空間２０に対してアクセス
処理を行い、その処理結果をＣＰＵに返す機能を有する
と共に、ガーベジ・コレクション起動時において回収制
御部１２及び印付は制御部１３を制御して記憶空間２０
に対して処理を行わせる機能を有している。

第３図に示すように、記憶空間２０は、例えば５つの分
割領域２０−１〜２０−５に分割され、そのうちの１つ
の分割領域が複写用に使用される例が示されている。記
憶空間管理テーブル１４は、分割された記憶空間２０の
それぞれの分割領域２０−１〜２０−５の状態を示すテ
ーブルであって、複写用の分割領域を示すフラグＣ１分
割領域が印付けされていることを示すフラグＭ、各分割
領域で使用可能なデータ量を示す自由領域サイズ、各分
割領域で印付けされたデータ領域のデータ量を示す印付
は領域サイズの情報等が記入されている。

この記憶空間管理テーブル１４の情報の変更は、記憶空
間管理部１１、回収制御部１２及び印付は制御部１３に
よって行われる構成になっている。

次に、記憶空間２０の例えばＮｏ、　５の分割領域２０
−５が複写用分割領域、Ｎｏ、　１〜Ｎｏ、　４の分割
領域２０−１〜２０−４が使用中の分割領域であるとし
て、第１図を参照しつつガーベジ・コレクション方法を
説明する。

第１図において、まず、記号処理プログラムに従って記
憶空間管理部１１によりガーベジ・コレクションが起動
されると、該記憶空間管理部１１は記憶空間管理テーブ
ル１４の印付はフラグＭを調べ、印付けされている分割
領域２ｏ−１〜２゜５があるかを調べる（ステップＳＬ
＞。印付けされた分割領域がない場合は、印付は制御部
１３によって印付は処理（ステップＳ６）を行い、ステ
ップＳ７へ進む。

ステップＳ１において印付けされた分割領域がある場合
（第３図の２０−２．２Ｏ−３）　、記憶空間管理部１
１は使用中の全ての分割領域が印付けされているかを調
べる（ステップＳ２＞。使用中の全ての分割領域が印付
けされている場合には、ステップＳ７へ進む。

使用中の分割領域のうちで印付けされていない分割領域
がある場合、記憶空間管理部１１では、印付けされた分
割領域２０−２．２０−３のどれを複写用の分割領域に
コピーすることによって十分なデータ領域を回収できる
かを、分割領域の自由領域サイズｎ２．ｎ３と、印付は
領域サイズｍ２、ｍ３より計算する（ステップＳ３）。

そして記憶空間管理部１１では、ステップＳ３の計算結
果より、十分なデータ領域が回収可能であるがを判定す
る（ステップＳ４＞。この判定結果より、十分なデータ
領域が回収可能でない場合、印付は制御部１３はステッ
プＳ５において、印付けされている分割領域、例えば２
０−２の印Ｍを消し、続いてステップＳ６で印付は処理
を行った後、ステップＳ７へ進む。ステップＳ６の印付
は処理は、使用中の全分割領域２０−１〜２０−３に対
して行われ、記憶空間管理テーブル１４の印付はフラグ
と印付は領域サイズを設定する。

記憶空間管理部１１では、ステップＳ７において、記憶
空間管理テーブル１４の自由領域サイズと印付は領域サ
イズとから、印付けされている分割領域２０−２．２０
−３の内、どの分割領域を複写用分割領域２０−５にコ
ピーするのが適切であるかを計算し、さらに、続いて別
の分割領域、例えば２０−２を新たに複写用になる分割
領域２０−２にコピーするのが適切であるかを計算する
。

回収制御部１０はステップＳ８において、ステップＳ７
の計算で決定された分割領域の最初の分割領域、例えば
２０−２を複写用の分割領域２０−５にコピーする。こ
のコピー操作により、分割領域２０−５は使用中の分割
領域となって記憶空間管理テーブル１４から複写用フラ
グＣが消え、それに代えて分割領域２０−２が新たな複
写用の分割領域となって複写用フラグＣが立つ。この時
、分割領域２０−５に対応する記憶空間管理テーブル１
４中の印付はフラグは印付けされていない状態を示し、
自由領域サイズがコピーされたデータ量になる。

記憶空間管理部１１では、ステップＳ７でさらにコピー
するのが適切である分割領域、例えば２０−３があった
かを調べ（ステップＳ９）、さらにコピーする時はステ
ップＳ８を繰り返す。さらにコピーする必要のない時は
、ガーベジ・コレクションを終了する。

前記のステップＳ３．Ｓ７において、コピーによって使
用可能になる自由領域のデータ量は、分割領域のサイズ
から印付は領域サイズを引いた値である。記憶空間管理
部１１では、この計算した値を元に、記号処理プログラ
ムが要求しているデータ領域のサイズ以上で、全体の記
憶空間２０のサイズのあるパーセント（例えば、１０パ
ーセント）を越えるデータ領域を回収するために、どの
分割領域をコピーすれば良いかを求める。また、ステッ
プＳ３において、特に、回収できるデータ量が少ない時
には、印付は処理をした方が良いことを記憶空間管理部
１１に知らせ、ステップＳ４へ移る。

なお、記号処理プログラムが記憶空間管理部１１に対し
て新しいデータ領域を要求し、そのデータ領域が確保で
きる時には、ガーベジ・コレクション動作が行われない
。この時、新・しいデータ領域を確保する分割領域に対
する記憶空間管理テーブル１４中の印付はフラグＭが設
定されている場合には、印付は制御部１３によって新し
いデータ領域に印を付け、印付は領域サイズをデータ量
分増やす。

以上のように本実施例では、記憶空間２０を例えば５に
分割し、そのうちの１つを複写用分割領域に使用してそ
れに使用中のデータをコピーするようにしたので、記憶
空間２０における自由領域が広くなって、その記憶空間
２０を有効に使用することができ、さらにガーベジ・コ
レクションを行う領域が局所的に小さくなるので、ガー
ベジ。

コレクションの高速化が図れる。しかも、本実施例では
ステップＳ３．Ｓ４により、印付は処理を行う有無を、
記憶空間２０の使用情況に合わせて判断し、制御するの
で、従来のようにコピーする度に印付は処理する必要が
なくなり、ガーベジコレクションにおける印付は処理を
軽減でき、それによってガーベジ・コレクションの処理
を高速に実行することができる。

なお、本発明は図示の実施例に限定されず、種々の変形
が可能である。その変形例としては、例えば次のような
ものがある。

（ａ）　　上記実施例では、記憶空間２０を５つの分割
領域２０−１〜２０−５に分割してその内１つを複写用
にしているが、分割は３以上で複写用は１つ以上あれば
、上記実施例とほぼ同様の利点が得られる。

（ｂ）　　第１図のステップＳ３．Ｓ４におけるコピー
する分割領域の選択や印付は処理の選択の基準（前記の
１０パーセント等）は、上記実施例に限定されず、種々
の変形が可能である。

（発明の効果） 以上詳細に説明したように、本発明によれば、記憶空間
を３以上の複数の分割領域に分割し、その分割領域内の
少なくとも１つを複写用分割領域として使用し、その各
分割領域の情報を記憶空間管理テーブルで管理するので
、記憶空間における自由領域が広くなってその記憶空間
を有効に使用することができるばかりか、ガーベジ・コ
レクションを行う領域が局所的に小さくなるので、高速
化することができる。

本発明では、このようなガーベジ・コレクション方法の
技術を前提として、ガーベジ・コレクション時に、記憶
空間管理テーブルにより、印付は処理を分割領域毎に管
理し、その分割領域に対する不要データ回収処理の有効
性を判定し、その判定結果に基づき印付は処理を制御す
るようにしている。つまり、印付は処理を行う有無を、
記憶空間の使用情況に合わせて判定し、制御するように
しているので、従来のようにコピーする度に印付は処理
が必要であったものを、必要なものだけに対して印付は
処理を行うので、ガーベジ・コレクションにおける印付
は処理を軽減することができ、それによってガーベジ・
コレクション処理を高速に実行することができる。

【図面の簡単な説明】

第１図は本発明の実施例を示すガーベジ・コレクション
方法を説明するためのフローチャート、第２図は第１図
の方法が適用される記号処理装置におけるメモリ管理の
機能ブロック図、第３図は第２図中の記憶空間管理テー
ブル及び記憶空間を示す図である。 １０・・・・・・メモリ管理部、１１・・・・・・記憶
空間管理部、１２・・・・・・回収制御部、１３・・曲
印付は制御部、１４・・・・・・記憶空間管理テーブル
、２ｏ・・曲記憶空間、２０−１〜２０−５・・・・・
・分割領域。 本発明の実施例のガーベジ・コレクショ〉方法第１図 第２図

Claims (1)

1. 【特許請求の範囲】 信号処理装置に用いられるコピー方式のガーベジ・コレ
   クションの対象となる記憶空間を３以上の複数の分割領
   域に分割し、その分割領域内の少なくとも１つを複写用
   分割領域として使用し、前記各分割領域の情報を記憶空
   間管理テーブルで管理して、前記複写用分割領域以外の
   分割領域から、使用中のデータのみを前記複写用分割領
   域へコピーするガーベジ・コレクション方法において、
   ガーベジ・コレクション時に、前記記憶空間管理テーブ
   ルにより、前記使用中のデータを表示する印付け処理を
   前記分割領域毎に管理し、 前記分割領域に対する不要データ回収処理の有効性を判
   定し、その判定結果に基づき前記印付け処理を制御する
   こと、 を特徴とするガーベジ・コレクション方法。