JPH02205947A - ガーベジコレクション方式 - Google Patents

Abstract

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

Description

【発明の詳細な説明】 〔産業上の利用分野〕 この発明は、情報処理装置のメモリ管理の一種であるガ
ーベジコレクション方式に関するものである。

〔従来の技術〕

数値データ以外のデータを主に取扱う知識情報処理では
、その処理の過程で主記憶中に生成されたデータが、あ
る時点以降は再度参照されることのないデータとなるこ
とが多い。このようなデータをガーベジ又はゴミと称し
、処理が進んでいくとゴミの量が多くなり主記憶の利用
率が低下する。

従って、何らかの方法でこのゴミを除く処理（ガーベジ
コレクション）が必要となる。

第１０図はゴミを含むデータが存在する主記憶の状態図
である。

図において、１はデータが書込まれた主記憶で、２は主
記憶１の各部に付けられたアドレスを示す。

主記憶１の各部は、ＧＣ（ガーベジコレクション）フラ
グ部１ａ、タグ部１ｂ、値部ＩＣの３つの部分から構成
され、各部はそれぞれプログラムで書込みと読出しが可
能である。ＧＣフラグ部１ａはガーベジコレクション処
理の為に設けられたもので、初期状態は全てｕｍが書込
まれている。タグ部１ｂは書込まれているデータの型を
示すためのものであり、この例ではデータ型には２種あ
る。

１つはｉｎｔで整数を示し、その値部ＩＣには当該整数
の値が入っている。他の１つはｖｅｃｔ２で、これは構
造体と呼ばれる一次元の配列データを示し、その値部１
ｃには当該配列データが置かれているアドレスが入って
いる。配列の長さは２語である。アドレス２は４桁で表
わされ、最上位桁２ａはエリア番号、下位３桁２ｂはエ
リア内アドレスと呼ばれる。エリア内アドレスは０から
連続して使用される。この例ではエリア番号１と５が使
用され、エリア内アドレスはともに０から４まで使用さ
れている。

第１１図は、従来多く使用されているガーベジコレクシ
ョン方式であるマーキング・アンド・スライディング・
コンパクション方式の概略フローチャートである。以下
、本フローチャートに従って処理の概要を説明する。

ステップ１００ではマーキング処理を行う、これは主記
憶１中の有効なデータを捜してそれら全ての語のＧＣフ
ラグ部１ａにｍｋを書込むものである。ｍｋが書込まれ
なかったデータは初期状態ｕｍのままであり、これが無
効となったゴミのデータである。また、マーキング処理
中、各エリア毎にこのゴミデータの総量も計数しておく
。第１０図のデータをマーキング処理した後の状態を第
１２図に示す、なお、マーキング処理の過程は本発明と
は直接関係ないので、ここでは説明を省略する。

次のステップ２００．３００ではｍｋを付けたデータだ
け、エリア内のアドレスの小さい方へ詰含むアドレスの
大きいほうから小さい方に向ってメモリを順番に読出し
、自身より小さいアドレスを指す上向きポインタ（前述
のｖｅｃｔ２で示すようなアドレス情報を値部ＩＣに持
つデータをポインタと呼ぶ）を、ゴミを除いてコンパク
ションされた後のアドレスにメンテナンスする操作を行
う。第１３図にこの部分の詳細フローチャートを示す。

第１２図のマーク済データを例にこのフローチャートで
その処理を説明する。まず、第１２図の条件に従ってス
テップ２０１及び２０３でＡＲＥＡ＝５，５Ｐ＝５００
４．ＭＰ＝３の値が代入され、ステップ２０６で５００
４番地の内容が読出される。読出したＤａｔａのＧＣフ
ラグ部がｕｍであるので（ステップ２０７）、ステップ
２１２．２１３が実行され、５Ｐ＝５００３゜ＭＰ＝２
となる。再びステップ２０６に戻り、５００３番地の内
容が読出される。そのＧＣ’フラグ部がｍｋでタグ部が
ｉｎｔであるので（ステップ２０７．２０８）、ステッ
プ２１３が実行され、５Ｐ＝５００２となる。再びステ
ップ２０６に戻り、′５００２番地の内容が読出される
。ＧＣフラグ部がｍｋでタグ部がｖｅｃｔ２．さらに値
部がｓｐより小さいので（ステップ２０７，２０８゜２
０９）ステップ２１０が実行される。ステップ２１０の
詳細は第１４図に示す、つまり、ポイント先の内容を読
出してＳＰのアドレスに書込み、ポイント先からはＳ−
Ｐの位置を指すようにする。

この後のステップ２１３実行後のメモリの状態を第１５
図に。示す。それまでのポインタの向きが逆向きに変え
られており、１００３番地のＧＣフラグ部１ａにｒｅｖ
が付けられている。このポインタを逆転ポインタと呼ぶ
、さらに処理が進み、ｓｐが５００１．５０００，１０
０４．１００３と変化する。１００３番地まで進んだと
き、第１３図のステップ２０７で逆転ポインタｒｅｖを
検出する０次のステップ２２０の詳細は第１６図に示す
。ここでは、ポイント先の内容を読出してＳＰのアドレ
スに書込み、ＳＰ−ＭＰの計算を行って１００３番地に
令書込まれた内容がコンパクション処理の後に移動する
先を求める。つまり、ＭＰが保持するのがＳＰの位置よ
り上にあるゴミの総量であるから、その分をＳＰから差
し引くことによりコンパクション後のアドレスが求まる
ことになる。この直後のメモリの状態を第１７図に示す
、さらにｓｐが１００２．１００１゜１０００と進んで
この処理を終える。

第１１図の次のステップ３００のコンパクション・パス
２では、こんどは逆に１０００番地から順に読み出し、
ｍｋの付いたデータをエリア内アドレスＯの側に詰合せ
ていく。この時、ｍｋをｕｍにクリアする処理及びこの
例では存在しないが、下向きのポインタがあればそのメ
ンテナンスする処理もステップ２００と同様に行う。こ
の処理の後、すなわちガーベジコレクション終了後のメ
モリの状態を第１８図に示す。第１２図でｍｋが付され
たデータのみ残されて詰合されている。

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

この方式の特徴は、第１１図のステップ２００で行なわ
れている逆転ポインタによるポインタのメンテナンスで
ある。これにより特別な作業領域を取らずにデータの詰
合せが可能になるが、反面。

逆転ポインタが生成できないようなアドレス構成のメモ
リシステムではこの方式は使用できない。

例えば、第１９図に示すようなプロセス毎の多重論理空
間では逆転ポインタの生成ができない。この例では、論
理アドレス空間がプロセス間で共通に参照されるプロセ
ス共通エリア１０と、自プロセスの個別エリア内からし
か参照されないプロセス個別エリア１１．１１に分けら
れ各プロセス個別エリア１１．１１の論理アドレスはプ
ロセス毎に同じ値が使われる。なお、最終的に物理メモ
リをアクセスする際に、物理メモリアドレスとこの論理
アドレスとの対応関係を示すアドレス変換テーブルがプ
ロセス毎に異っているため、通常の使用時は問題ない。

しかし、ガーベジコレクシジンの逆転ポインタ生成時は
、プロセス共通エリア１０から各プロセス個別エリア１
１．１１を指さねばならず問題がある。すなわち、１０
０３番地に逆転ポインタを書込んだとき、そのアドレス
がプロセス１番のものか２番のものかの判別がつかない
からである。

この発明は上記のような問題点を解決するためになされ
たもので、多重論理空間にも適用できるガーベジコレク
シ９ン方式を実現することを目的とする。

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

この発明におけるガーベジコレクション方式は、プロセ
ス毎の多重論理空間において、プロセス共通エリアの大
きさに応じた作業エリアを設けて、プロセス共通エリア
における有効データのガーベジコレクション後の相対移
動量を当該有効データのアドレスに対応させて上記作業
エリア又は当該プロセス共通エリア内の無効データの領
域に書込み、プロセス個別エリアにおいてプロセス共通
エリアを指すポインタのメンテナンスを上記相対移動量
を用いて行なうようにしたものである。

〔作用〕

この発明におけるガーベジコレクション方式では、多重
論理空間のプロセス共通エリアにおける有効データの相
対移動量が、対応する作業エリア又はプロセス共通エリ
ア内の無効データの領域に書込まれているため、この相
対移動量を用いてプロセス個別エリアからプロセス共通
エリアを指すポインタのメンテナンスが可能となる。

〔実施例〕

以下、この発明の一実施例を図について説明する。第１
図において、１０．１１．１２は主記憶で、−語は前述
したようにＧＣフラグ部１ａ、タグ部１ｂ、値部ＩＣで
構成され、各部はそれぞれプログラムで書込みと読出し
が可能である。ＧＣフラグ部１ａはガーベジコレクショ
ン処理の為に設けられたもので、初期状態は全てにｕｍ
が書込まれており、ガーベジコレクション処理の中でｍ
ｋ又はｕｍが書込まれる。タグ部１ｂは書込まれている
データの型を示すためのものであり、この例ではデータ
型には２種ある。１つはＬｎｔで整数を示し、その値部
ＩＣには当該整数の値が入っている。他の１つはｖｅｃ
ｔ２で、これは構造体と呼ばれる一次元の配列データを
示し、その値部１ｃには当該配列データが置かれている
アドレスが入っている。配列の長さは２語である。アド
レス２は４桁で表わされ、最上位桁２ａはエリア番号、
下位３桁２ｂはエリア内アドレスである。

エリア内アドレスは０から連続して使用される。

エリア番号５はプロセス個別エリア１１で、異なるプロ
セス間で同じ論理アドレスが使われる。プロセス個別エ
リア１１内にあるｖｅｃｔ２のデータは、プロセス共通
エリア１０又は自分のプロセス個別エリア１１内を指す
。エリア番号１はプロセス共通エリア１０で、各プロセ
ス個別エリア１１から指される。

エリア番号１のプロセス共通エリア１０内にあるｖｅｃ
ｔ２のデータは同一エリアｌＯ内を指し、プロセス個別
エリア１１を指すことは無い。エリア番号Ｏは、本発明
の実現の為に使用されるプロセス共通のＧＣ用作業エリ
ア１２で、ガーベジコレクションの作業領域である。こ
のエリアの大きさはプロセス共通エリア１０の１／４の
大きさ（余りがある場合はプラス１）が取られている。

第２図は本発明によるガーベジコレクションのフローチ
ャートである。第１図の例をもとに、このガーベジコレ
クションの動作を説明する。ステップ１００ではマーキ
ング処理を行う。これは主記憶中の有効なデータを捜し
てそれら全ての語のＧＣフラグ部にｍｋを書込むもので
、従来と同様である。ｍｋが書込まれなかったデータは
初期状９ｕｍのままであり、これがゴミのデータである
。

第１図のＧＣフラグ部１ａはこのマーキング処理終了後
の状態を示している。

ステップ４００は本発明による共通エリア・コンパクシ
ョン・パスｌの処理である。この処理はプロセス共通エ
リア１０をエリア内アドレスの大きい方から順番に読み
出し、ｍｋの付いた語で上向きポインタをメンテナンス
するところは第１１図に示した従来のガーベジコレクシ
ョンのステップ２００の処理と同じである０本願のステ
ップ４００では、これに加え、共通エリア内のｍｋデー
タがコンパクションの後で移動する位置を知るために、
現在位置からの相対移動量を求め、それを記録しておく
。記録は以下の方法で行う。

プロセス共通エリア１０のエリア内アドレス００から４
語づつのブロックに分け、１つのブロックが全てｍｋの
場合はブロック内のどの語も相対移動量が等しいわけで
あるから、その相対移動量を第１図のエリア番号０のＧ
Ｃ用作業エリア１２に移動量テーブルとして書込む。書
込みアドレスは元のエリア内アドレスを４で割ることに
よって求める。ブロック内にｕｍのデータが存在する場
合はそのブロック内のｍｋのデータは相対移動量が異な
る可能性があるので、ＧＣ用作業エリア１２は使用せず
、ｍｋデータのすぐ上のｕｍデータの値部１ｃに相対移
動量を書込む０以上の共通エリア・コンパクション・パ
ス１の処理を第３図のフローチャートで示す０本フロー
チャートでは、ステップ２１４で図示しない■フラグを
初期化し、これをｕｍを検出するとリセツトすることに
よってブロック内が全てｍｋかを判断している。

ステップ２４０の移動量テーブル作成ルーチンの詳細は
第４図に示す。ＧＣ用作業エリア１２のＧＣフラグ部１
ａがｍｋの場合、対応する共通エリアのブロックが全て
ｍｋで、この語の値部ＩＣには相対移動量が書込まれて
いることを示し、ｕｍの場合は対応するブロック内にｕ
ｍが存在し、この語の値部ＩＣには相対移動量が書込ま
れていない事を示す。第５図は、共通エリア・コンパク
ション・バス１が終了した後の状態を示す。相対移動量
が０００１番地、０００３番地、１０００番地、１００
２番地、１０１０番地に書込まれている。

次に再び第２図フローチャートで次のステップを説明す
る。ステップ５００は個別エリア・コンパクション・バ
ス１で、プロセス個別エリア１１をエリア内アドレスの
大きい方から順番に読み出し、同一エリア内の上向きポ
インタをメンテナンスするところは第１１図に示した従
来のガーベジコレクションのステップ２００の処理と同
じである。本願のステップ５００では、この時プロセス
共通エリア１０を向いたポインタに対して前記ステップ
４００で書込んだ相対移動量を読出してメンテナンスす
る処理が追加されている。ステップ５００の処理の詳細
を第６図に示す。第６図において、同一エリア内の上向
きポインタはステップ２１０．２２０によって従来のよ
うに逆転ポインタを生成して処理する。共通エリア向ポ
インタはステップ２１５によって判断し、ステップ２３
０により処理する。ステップ２３０の詳細は第７図に示
す。ステップ２３１でＧＣ用作業エリア１２の対応する
エントリのアドレスを求め、ステップ２３２で読出した
内容のＧＣフラグ部によりそこに移動量が書き込まれて
いるかを判断する。ｍｋならば移動量が書込まれている
ので、ステップ２３３で移動先のアドレス計算を行い、
ＳＰのアドレスに書込む。移動量がＧＣ用作業エリア１
２に無い場合は、ステップ２３４に進み、ここからエリ
ア番号１０ポイント先から上方向に一語づつ読出してｕ
ｍのデータを見付けると、その中に移動量が書いである
ので、ステップ２３７によって移動先のアドレス計算を
行い、ＳＰのアドレスに書込む。最後に、第６図のステ
ップ２１６でＧＣ用作業エリア１２のＧＣフラグ部１ａ
をｕｍにクリアする。この処理の後のメモリ状態を第８
図に示す、プロセス共通エリア１０を向いたポインタが
全てメンテナンスされている。

続いて第２図ステップ３００に戻り、コンパクション・
バス２を行う。

これは第１１図に示す従来の処理と同じである。

エリア番号１．エリア番号５の順でエリア内アドレスの
小さい方から大きい方へ向って順次メモリを続出し、ｍ
ｋの付いたデータをエリア内アドレスの小さい方へ詰合
せる。この時、ＧＣフラグ部１ａをｕｎにクリアする。

また、下向きのポインタがあれば逆転ポインタを生成し
てメンテナンスを行う、第９図にガーベジコレクション
終了後のメモリの状態を示す。

なお、上記実施例では、ＧＣフラグ部１ａ、タグ部１ｂ
、値部ＩＣが同一部内にある例を示したが、２語でこれ
らを含むような構成のメモリシステムでもよい、また、
プロセス共通エリア１０を４語単位でブロック化したが
、これは２のべき東部単位であればいくらでも良（、こ
れに対応して、ＧＣ用作業エリア１２の大きさは、プロ
セス共通エリア１０の２のべき乗置の１の大きさとなる
。

〔発明の効果〕

以上のように、この発明によれば、プロセス共通エリア
の大きさに応じた作業エリアを設けて、プロセス共通エ
リアにおける有効データのガーベジコレクシジン後の相
対移動量を当該有効データのアドレスに対応させて上記
作業エリア又は当該プロセス共通エリア内の無効データ
の領域に書き込み、プロセス個別エリアにおいてプロセ
ス共通エリアを指すポインタのメンテナンスを上記相対
移動量を用いて行なうようにしたので、プロセス個別エ
リアからプロセス共通エリアを指すポインタのメンテナ
ンス時に逆転ポインタの生成が不要となり、最小限の作
業領域で多重論理空間におけるガーベジコレクションが
可能となる効果がある。

【図面の簡単な説明】

・第１図はこの発明が適用されるメモリシステムの一例
を示す構成図、第２図はこの発明の一実施例によるガー
ベジコレクション方式を示す概略フローチャート、第３
図は第２図の共通エリア・コンパクション・バス１を示
す詳細フローチャート、第４図は第３図の移動量テーブ
ル作成ルーチンを示す詳細フローチャート、第５図は共
通エリア・コンパクション・バス１終了後のメモリ状態
を示す図、第６図は第２図の個別エリア・コンパクショ
ン・バスｌを示す詳細フローチャート、第７図は第６図
の共通エリア向ポインタメンテナンスの詳細フローチャ
ート、第８図は個別エリア・コンパクション・バス１終
了後のメモリ状態を示す図、第９図は実施例のガーベジ
コレクション終了後のメモリ状態を示す図、第１０図は
従来のガーベジコレクション方式が適用されるメモリシ
ステムの構成図、第１１図は従来のガーベジコレクショ
ン方式を示す概略フローチャート、第１２図はマーキン
グ後のメモリ状態を示す図、第１３図は第１１図のコン
パクション・バス１を示ス詳細フローチャート、第１４
図は第１３図の逆転ポインタ生成ルーチンを示す詳細フ
ローチャート、第１５図は逆転ポインタ生成後のメモリ
状態を示す図、第１６図は第１３図のポインタメンテナ
ンスルーチンを示す詳細フローチャート、第１７図はポ
インタメンテナンス後のメモリ状態を示す図、第１８図
は従来のガーベジコレクション終了後のメモリ状態を示
す図、第１９図は多重論理空間のメモリシステム例を示
す構成図である。 １０はプロセス共通エリア、１１はプロセス個別エリア
、１２はＧＣ用作業エリア、ｌａはＧＣフラグ部、１ｂ
はタグ部、ＩＣは値部、２はアドレス、２ａはエリア番
号、２ｂはエリア内アドレス。 なお、図中、同一符号は同−又は相当部分を示す。 代理人　　大岩増雄（ばか２名） 葛１１図

Claims (1)

1. 【特許請求の範囲】 メモリ中で不要となった無効データを除去し、有効デー
   タを詰合せて無効データの領域を回収する際に、有効デ
   ータを指すポインタの参照アドレスのメンテナンスを行
   なうガーベジコレクション方式において、 メモリの論理アドレス空間を複数のエリアに分割して、
   全てのプロセスから共通に参照されるプロセス共通エリ
   アと、プロセス毎に同じ論理アドレスが割付けられて自
   プロセスからのみ参照されるプロセス個別エリアとを設
   けたメモリシステムに、上記プロセス共通エリアの大き
   さに応じた作業エリアを設けて、プロセス共通エリアに
   おける有効データのガーベジコレクション後の相対移動
   量を当該有効データのアドレスに対応させて上記作業エ
   リア又は当該プロセス共通エリア内の無効データの領域
   に書込み、プロセス個別エリアにおいてプロセス共通エ
   リアを指すポインタのメンテナンスを上記相対移動量を
   用いて行なうようにしたことを特徴とするガーベジコレ
   クション方式。