(57)【特許請求の範囲】
【請求項１】
プログラムを実行するプロセッサと、メモリと、を備えた計算機システムにおけるメモリ管理方法であって、
前記メモリは、ガベージコレクタによって管理される第１の領域と、前記ガベージコレクタによって管理されない第２の領域と、を備えており、
前記方法は、
前記プロセッサが、前記第２の領域に関連付けされた所定のデータを基点として参照を辿ることによって、前記所定のデータの参照関係を調査する手順と、
前記所定のデータの参照関係が、前記所定のデータと同一の所属クラスのデータへの参照を含む構造である場合、前記プロセッサが、この構造を構成するデータのうちの特定のデータの前記第２の領域への移動を禁止するように判定する手順と、
前記プロセッサが、前記構造を構成するデータから前記特定のデータを除いたデータのうちの、前記第１の領域に格納されたデータを、前記第２の領域に移動させる手順と、
を含むことを特徴とするメモリ管理方法。
【請求項２】
前記判定する手順では、前記所定のデータの参照関係が、前記所定のデータから参照を辿ると、再び前記所定のデータを参照する循環構造である場合、前記プロセッサは、この循環構造を構成するデータのうちの特定のデータの前記第２の領域への移動を禁止するように判定することを特徴とする請求項１に記載のメモリ管理方法。
【請求項３】
前記特定のデータは、前記所定のデータと参照関係にあるデータのうち、ルート集合データを基点として参照を辿った数である参照の深さが、前記所定のデータの参照の深さよりも小さいデータであることを特徴とする請求項２に記載のメモリ管理方法。
【請求項４】
前記特定のデータは、前記所定のデータと参照関係にあるデータのうち、前記所定のデータを基点として参照を辿った数である距離が、所定数よりも大きいデータであることを特徴とする請求項２に記載のメモリ管理方法。
【請求項５】
前記判定する手順では、前記所定のデータの参照関係が、前記所定のデータが前記所定のデータと同一の所属クラスのデータを参照するリスト構造である場合、前記プロセッサは、このリスト構造を構成するデータのうちの、前記所定のデータと同一の所属クラスのデータ、及び、前記所定のデータと同一の所属クラスのデータから直接又は間接的に参照されるデータの、前記第２の領域への移動を禁止するように判定することを特徴とする請求項１に記載のメモリ管理方法。
【請求項６】
前記調査する手順では、前記プロセッサは、プログラムＡＰＩ、起動時オプション、又は、外部ファイルによって指示された契機で、前記所定のデータの参照関係の調査を開始することを特徴とする請求項１に記載のメモリ管理方法。
【請求項７】
プログラムを実行するプロセッサと、メモリと、を備えた計算機システムであって、
前記メモリは、ガベージコレクタによって管理される第１の領域と、ガベージコレクタによって管理されない第２の領域と、を備え、
前記プロセッサは、
前記第２の領域に関連付けされた所定のデータを基点として参照を辿ることによって、前記所定のデータの参照関係を調査し、
前記所定のデータの参照関係が、前記所定のデータと同一の所属クラスのデータへの参照を含む構造である場合、この構造を構成するデータの特定のデータの、前記第２の領域への移動を禁止するように判定し、
前記構造を構成するデータから前記特定のデータを除いたデータのうちの、前記第１の領域に格納されたデータを、前記第２の領域に移動させることを特徴とする計算機システム。
【請求項８】
プログラムを実行するプロセッサと、メモリと、を備えた計算機システムに用いられるメモリ管理プログラムであって、
ガベージコレクタによって管理されない第２の領域に関連付けされた所定のデータを基点として参照を辿ることによって、前記所定のデータの参照関係を調査する手順と、
前記所定のデータの参照関係が、前記所定のデータと同一の所属クラスのデータへの参照を含む構造である場合、この構造を構成するデータのうちの特定のデータの前記第２の領域への移動を禁止するように判定する手順と、
前記構造を構成するデータから前記特定のデータを除いたデータのうちの、前記ガベージコレクタによって管理される第１の領域に格納されたデータを、前記第２の領域に移動させる手順と、
を前記プロセッサに実行させることを特徴とするメモリ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリ管理方法に関し、特に、ガベージコレクタによって管理されるメモリ領域と管理されないメモリ領域とを併用する計算機システムにおけるメモリ管理方法に関する。
【背景技術】
【０００２】
コンピュータプログラムを開発する上で、プログラムが利用するメモリ領域の確保・解放等のメモリ管理は、プログラム開発者の手を煩わせる項目の一つである。これを解決する手段として、ガベージコレクタが利用されることが多い。
【０００３】
Ｊａｖａ（登録商標）は、ガベージコレクタを利用してメモリを管理する言語処理系の一つである。Ｊａｖａは、プログラム実行時のメモリ確保用ＡＰＩは用意されているが、メモリ解放用ＡＰＩは用意されていない言語仕様である。プログラムの実行過程で確保されたメモリ領域は、Ｊａｖａ仮想マシンに実装されたガベージコレクタによって自動的に解放される。ガベージコレクタによるメモリの解放処理（ガベージコレクション、以下、「ＧＣ（Garbage Collection）」という。)は、Ｊａｖａプログラムによって実行中の全てのスレッドを停止させて、不要なデータを回収する形態が多い。
【０００４】
ところで、Ｊａｖａ仮想マシンがＧＣを起動するのは、Ｊａｖａプログラムによって生成されたデータ(Ｊａｖａオブジェクト)を格納するＪａｖａヒープの使用量がある閾値を超える直前である。しかしながら、Ｊａｖａヒープの使用量を見積もること及びＪａｖａヒープの使用量が閾値を超えるタイミングを予見することはユーザにとって困難である。そのため、ＧＣの起動によって、プログラムが不定期に実行停止する問題がある。
【０００５】
また、Ｊａｖａ仮想マシンにおけるＧＣの実装方式として、停止時間が短時間のＧＣ（ＣｏｐｙＧＣ）と、停止時間が長時間のＧＣ（ＦｕｌｌＧＣ）と、を使い分ける世代別ガベージコレクションが多く採用されている。しかしながら、この世代別ガベージコレクションでは、次にどちらのＧＣが起動するかを予見することは困難である。そのため、予期しないＧＣの起動によって、プログラムが実行停止してシステム全体の応答が低下する問題がある。
【０００６】
これらの問題を解決することを目的として各種発明がなされてきた（特許文献１、非特許文献１、２参照）。上記各文献には、ＧＣ対象のメモリ領域（以下、「Ｊａｖａヒープ」という。）の他に、ＧＣ対象外のメモリ領域（以下、「外部ヒープ」という。）を設けた点が示されている。外部ヒープとは、プログラムによって管理可能なメモリ領域である。外部ヒープの確保、外部ヒープにおけるオブジェクトの生成及び外部ヒープの解放は、プログラマによるプログラムのソースコード中の記述に従って実行される。
【０００７】
非特許文献１には、外部ヒープに生成するデータに制限が設けた点が開示されている。この制限とは、外部ヒープにおいて、Ｊａｖａヒープ内のデータから参照されるデータの生成を制限することである。これにより、外部ヒープ内のデータにアクセスするプログラムの実行スレッド数が０となった場合に、自動的に外部ヒープをそこに格納されたデータごと解放しても、プログラムの実行結果に影響を与えないことを保証できる。つまり、外部ヒープを低オーバヘッドに且つ安全に解放することができる。仮に、Ｊａｖａヒープ内のデータが外部ヒープ内のデータを参照している状態で外部ヒープを解放すると、Ｊａｖａヒープ内のデータからの参照が不正な領域（解放されたメモリ領域）を指すことになる。そうすると、正常にプログラムの実行を継続することができなくなる。
【０００８】
しかしながら、非特許文献１に開示された技術では、ユーザが常にデータ間の参照関係に留意しながらプログラミングする必要がある点、プログラム規模の増大やプログラムに記述されない暗黙的なデータの生成により、メモリ領域上の参照関係の把握が極めて困難になる点等の問題がある。また、実際にプログラムを実行するまで、上記の制限に違反するか否かが不明である点、上記の制限に違反している場合には例外（Ｅｘｃｅｐｔｉｏｎ）が発生してプログラムが正常に実行されないことが多い点、プログラムの実行時に制限内容をチェックすることにより性能が著しく低下する点等の問題がある。
【０００９】
これらの問題を解決すべく、特許文献１及び非特許文献２には、外部ヒープに生成するデータに制限を設けずに、外部ヒープを利用可能な点が開示されている。特許文献１及び非特許文献２に開示された技術では、外部ヒープを解放する際、解放対象の外部ヒープ内のデータと、解放対象外のメモリ領域（Ｊａｖａヒープ、解放対象外の外部ヒープ）内のデータと、の参照関係を調査し、解放対象の外部ヒープ内のデータのうち、その後のプログラムの実行に必要なデータを、解放対象外のメモリ領域に移動させる。これにより、その後のプログラムの実行に支障がないことを保証した上で、解放対象の外部ヒープを解放できる。また、ユーザは、データの参照関係を気にすることなく外部ヒープ用ＡＰＩを利用してプログラミングできる。また、上記の調査は外部ヒープの解放時のみに実行されるため、プログラム実行時等に調査が実行されることによるオーバヘッドも回避することができる。
【００１０】
図１Ａは、従来の一般的なＪａｖａ用ＡＰＩの利用例を示す図である。プログラム２０１は、Ｌｉｓｔクラスのデータｌｉを生成するステップ２０２と、Ｏｂｊクラスのデータｏ１、ｏ２を生成するとともに、ステップ２０２で生成されたデータｌｉからデータｏ１、ｏ２を参照させるステップ２０６と、を含む。
【００１１】
図１Ｂは、従来の外部ヒープ用ＡＰＩの利用例を示す図である。プログラム２０３は、図１Ａのプログラム２０１を修正したものである。このプログラム２０３は、外部ヒープを生成するステップ２０４と、生成された外部ヒープに対してＬｉｓｔクラスのデータｌｉを生成するステップ２０５と、上記のステップ２０６と、生成された外部ヒープを解放（削除）するステップ２０７と、を含む。特にステップ２０４では、ＲｅｆｅｒｅｎｃｅＥｘｐｌｉｃｉｔＭｅｍｏｒｙクラスのデータｅｍを生成することによって、外部ヒープを生成する。また、ステップ２０４で生成された外部ヒープ内のデータが、他のメモリ領域内のデータから参照されている場合、ステップ２０７では、外部ヒープ内のデータを他のメモリ領域に移動させた後に、外部ヒープを解放する。
【００１２】
ところで、外部ヒープにデータを配置させる方法には、二種類の方法がある。一つは、プログラム中のある区間内で生成されるデータの全てを、外部ヒープに配置する方法（特許文献１参照）である。もう一つは、外部ヒープに関連付けされたデータ（以下、「基点データ」という。）から参照可能なデータを、外部ヒープに配置する方法（非特許文献２参照）である。図１Ｂは、後者の方法を利用するためのプログラムである。すなわち、後者の方法を利用する前提として、ステップ２０４で生成された外部ヒープに、ステップ２０５によってＬｉｓｔクラスのデータｌｉを関連付けさせている。
【００１３】
図２は、従来の外部ヒープ用ＡＰＩを利用したプログラム（図１Ｂ参照）を実行後のデータ配置を示す図である。外部ヒープ１１０は、図１Ｂのステップ２０４で生成される。この外部ヒープ１１０には、ステップ２０５で生成されたＬｉｓｔクラスのデータｌｉ３０１が基点データとして配置される。一方、図２のＪａｖａヒープ１０９には、ステップ２０６で生成されたＯｂｊクラスのデータｏ１（３０２）、ｏ２（３０３）、及び、その他のデータＦ３０５が配置される。なお、参照３０４−１、３０４−２に示すように、基点データｌｉ３０１は、データｏ１（３０２）及びデータｏ２（３０３）を参照している。また、参照３０６に示すように、データＦ３０５はデータｏ１（３０２）を参照している。
【００１４】
ここで、データｏ１（３０２）及びデータｏ２（３０３）を外部ヒープ１１０に移動させることを考える。移動させるタイミングは、ＧＣ実行時やＪａｖａヒープの使用量がある閾値を超えた場合等である。
【００１５】
図３は、従来の基点データから参照可能なデータを外部ヒープに移動させた後のデータ配置を示す図である。図３では、基点データｌｉ３０１から参照可能なデータｏ１（４０１）、ｏ２（４０２）が、外部ヒープ１１０に移動している。
【００１６】
ここで、仮に外部ヒープ１１０を解放すると、参照３０６は不正な領域（解放されたメモリ領域）を指すことになる。この場合、正常にプログラムの実行を継続できなくなる。そこで、参照３０６のような、解放対象外のＪａｖａヒープ１０９内のデータＦ３０５から解放対象の外部ヒープ１１０内のデータｏ１（４０１）への参照が存在する場合、データｏ１（４０１）をＪａｖａヒープ１０９に移動させる（図４参照）。
【００１７】
図４は、従来の解放対象の外部ヒープ内のデータを解放対象外のメモリ領域に移動させた場合のデータ配置を示す図である。図４では、データｏ１（４０１）は、データｏ１'（５０１）としてＪａｖａヒープ１０９に移動している。また、図３の参照３０６は、図４の参照５０２として更新される。
【００１８】
データｏ１（４０１）とデータｏ１'（５０１）とは同一のデータであるため、参照５０２は参照３０６と同義である。この場合、外部ヒープ１１０をデータｌｉ３０１、ｏ１（４０１）、ｏ２（４０２）ごと解放しても、その後のプログラムの実行に支障がない。
【先行技術文献】
【特許文献】
【００１９】
【特許文献１】特開２００９−０３７５４７号公報
【非特許文献】
【００２０】
【非特許文献１】F.Pizlo, J.M.Fox, D.Holmes and J.Vitek, Real-Time Java Scoped Memory: Design Patterns and Semantics, In Proceedings of the Seventh IEEE International Symposium on Object-Oriented Real-Time Distributed Computing, 2004.
【非特許文献２】小幡 元樹、西山 博泰、足立 昌彦、岡田 浩一、長瀬 卓真、中島 恵、Javaにおける明示的メモリ管理、情報処理学会論文誌、Vol.50、No.7、pp.1693-1715、July、2009年
【発明の概要】
【発明が解決しようとする課題】
【００２１】
ところで、基点データから参照可能なデータを、外部ヒープに配置する上記の方法では、基点データが参照可能なＪａｖａヒープ内の全データ群が、外部ヒープに移動する。そのため、このようなデータ群のうちの特定のデータ群のみを外部ヒープに移動させたい場合の指定が困難であった。
【００２２】
例えば、所定処理によって生成されるデータ群の参照関係上の頂点のデータを基点データとして、この基点データから参照可能なデータ群のみを一つの外部ヒープに移動させる場合を考える。この場合、基点データが特定のデータ構造上にある場合、想定外のデータ移動が発生し得る。
【００２３】
図１０は、循環構造のデータ間の参照関係を示す図である。図１０において、丸印はデータを、丸印の内側のアルファベットはデータの所属クラスを、矢印はデータ間の参照関係を示す。例えば、参照１１０７は、所属クラスＡのデータ１１０１が、所属クラスＢのデータ１１０２を参照することを示す。
【００２４】
ここで、データ１１０３−１を基点データとして、データ１１０３−１及びデータ１１０３−１から参照可能なデータ１１０４−１のみを、一つの外部ヒープに移動させるものとする。この場合、図１０に示すように、データ１１０３−１、１１０４−１、１１０１、１１０２、１１０３−１間において、参照関係が循環構造になっている。そのため、従来のデータ配置方法では、データ１１０１、１１０２も、基点データ１１０３−１から参照可能なデータとして、一つの外部ヒープに移動する。
【００２５】
図２１は、リスト構造のデータ間の参照関係を示す図である。図２１において、例えば、参照１５０４−１は、所属クラスＦのデータ１５０１−１が、同じ所属クラスＦのデータ１５０１−２を参照することを示す。
【００２６】
ここで、データ１５０１−１を基点データとして、データ１５０１−１及びこのデータ１５０１−１から参照可能なデータ１５０２−１、１５０３−１のみを、一つの外部ヒープに移動させるものとする。この場合、図２１に示すように、データ１５０１−１、１５０１−２、１５０１−３間において、参照関係が自己参照型のリスト構造になっている。そのため、従来のデータ配置方法では、データ１５０１−２、１５０１−３も、基点データ１５０１−１から参照可能なデータとして、一つの外部ヒープに移動する。
【００２７】
以上、図１０及び図２１を用いて説明してきたように、基点データが特定のデータ構造（循環構造やリスト構造）上にある場合、想定外のデータ移動が発生し得る。この結果、ユーザによる見積もりと大きさが異なる外部ヒープが生成される。そうすると、外部ヒープの解放処理においても問題が生じる。前述のように、外部ヒープの解放処理では、外部ヒープに格納されたデータのうちその後のプログラムの実行に必要なデータを他のメモリ領域に移動させる必要がある。しかしながら、基点データが特定のデータ構造上にある場合、外部ヒープには「移動すべく移動したデータ群」と「想定外に移動したデータ群」とが配置される。両者は多くの場合、データの生存期間が異なる。そして、「想定外に移動したデータ群」が配置された外部ヒープの解放時間は、「移動すべく移動したデータ群」のみが配置された他の外部ヒープの解放時間よりも長くなる。すなわち、外部ヒープによって解放時間に大きなバラつきが生じる。
【００２８】
この問題を解決する方法として、基点データとなり得る他のデータの調査、基点データが特定の構造上に置かれないようなプログラムの修正等が挙げられる。しかしながら、これらの解決方法では、外部ヒープの利便性を大きく損ねてしまう。
【００２９】
本発明は、上述した問題を考慮したものであって、基点データが特定のデータ構造（循環構造、リスト構造）上にある場合であっても、外部ヒープの利便性を損なうことなく効率的にメモリ領域を利用可能なメモリ管理方法、計算機システム及びメモリ管理プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３０】
本願において開示される発明の代表的な一例を示せば以下の通りである。すなわち、プログラムを実行するプロセッサと、メモリと、を備えた計算機システムにおけるメモリ管理方法であって、前記メモリは、ガベージコレクタによって管理される第１の領域と、前記ガベージコレクタによって管理されない第２の領域と、を備えており、前記方法は、前記プロセッサが、前記第２の領域に関連付けされた所定のデータを基点として参照を辿ることによって、前記所定のデータの参照関係を調査する手順と、前記所定のデータの参照関係が、前記所定のデータと同一の所属クラスのデータへの参照を含む構造である場合、前記プロセッサが、この構造を構成するデータのうちの特定のデータの前記第２の領域への移動を禁止するように判定する手順と、前記プロセッサが、前記構造を構成するデータから前記特定のデータを除いたデータのうちの、前記第１の領域に格納されたデータを、前記第２の領域に移動させる手順と、を含むことを特徴とする。
【発明の効果】
【００３１】
本発明によれば、基点データが特定のデータ構造（例えば循環構造、リスト構造）上にある場合に、この基点データが参照可能なデータのうちの特定のデータが第２の領域へ移動されないようにしている。そのため、外部ヒープに配置すべきでない特定のデータが外部ヒープに配置されることを防ぐことができ、外部ヒープの利便性を損なうことなく効率的にメモリを管理することができる。
【００３２】
また、ユーザの意図に沿ったデータ配置や外部ヒープの使用量の正確な見積もりを可能にする。さらに、外部ヒープ毎の解放時間のバラつきを低減することができる。
【図面の簡単な説明】
【００３３】
【図１Ａ】従来の一般的なＪａｖａ用ＡＰＩの利用例を示す図である。
【図１Ｂ】従来の外部ヒープ用ＡＰＩの利用例を示す図である。
【図２】従来の外部ヒープ用ＡＰＩを利用したプログラムを実行後のデータ配置を示す図である。
【図３】従来の基点データから参照可能なデータを外部ヒープに移動させた後のデータ配置を示す図である。
【図４】従来の解放対象の外部ヒープ内のデータを解放対象外のメモリ領域に移動させた場合のデータ配置を示す図である。
【図５】本発明の実施形態の計算機システムの構成例を示す図である。
【図６】本発明の実施形態のメモリ管理方法の概要を示すフローチャートである。
【図７Ａ】本発明の実施形態の外部ファイルによって調査契機を指定する第１の例を示す図である。
【図７Ｂ】本発明の実施形態の外部ファイルによって調査契機を指定する第２の例を示す図である。
【図８】本発明の実施形態のＪａｖａプログラムＡＰＩによって調査契機を指定する例を示す図である。
【図９】本発明の実施形態のデータ移動可否判定部及びデータ移動部の制御ロジックを示すフローチャートである。
【図１０】循環構造のデータ間の参照関係の一例を示す図である。
【図１１】本発明の実施形態の循環構造のデータの参照の深さを調査する制御ロジックを示すフローチャートである。
【図１２】本発明の実施形態の循環構造のデータの参照の深さを求めた結果を示す図である。
【図１３】本発明の実施形態のデータの参照の深さに基づく循環構造のデータの移動可否判定の制御ロジックを示すフローチャートである。
【図１４】図１３のステップ１００２の詳細処理を示すフローチャートである。
【図１５】本発明の実施形態のデータ移動の制御ロジックを示すフローチャートである。
【図１６】図１０に示す循環構造のデータに本発明の実施形態を適用した場合のデータ配置を示す図である。
【図１７】図１０に示す循環構造のデータに従来のデータ配置方法を適用した場合のデータ配置を示す図である。
【図１８】循環構造のデータ間の参照関係の他の例を示す図である。
【図１９】本発明の実施形態の循環構造のデータの距離を調査する制御ロジックを示すフローチャートである。
【図２０】本発明の実施形態のデータの距離に基づく循環構造のデータの移動可否判定の制御ロジックを示すフローチャートである。
【図２１】リスト構造のデータ間の参照関係を示す図である。
【図２２】本発明の実施形態のデータの参照の深さに基づくリスト構造のデータの移動可否判定の制御ロジックを示すフローチャートである。
【図２３】図２１に示すリスト構造のデータに本発明の実施形態を適用した場合のデータ配置を示す図である。
【図２４】図２１に示すリスト構造のデータに従来のデータ配置方法を適用した場合のデータ配置を示す図である。
【発明を実施するための形態】
【００３４】
本発明の実施形態によれば、ＧＣ対象のメモリ領域（Ｊａｖａヒープ）とＧＣ対象外のメモリ領域（外部ヒープ）とを併用する計算機システムにおいて、データ（オブジェクト）の参照関係に基づいてＪａｖａヒープから外部ヒープにデータを移動させる処理において、外部ヒープに関連付けされた基点データ（基点オブジェクト）と特定の参照関係（循環構造、リスト構造）を構成するデータのうちの特定のデータの、基点データと同一の外部ヒープへの配置を禁止する。
【００３５】
以下、本発明の実施形態について図面に基づいて説明する。なお、以下の実施形態では、本発明を、Ｊａｖａ技術を基盤とした計算機システムに適用した場合を例に説明するが、ＧＣ機能を有する他の計算機システムに対しても適用可能である。
【００３６】
（計算機システムの構成）
図５は、本発明の実施形態の計算機システム１０１の構成例を示す図である。計算機システム１０１は、プロセッサ（ＣＰＵ）１０２、メモリ１０３を備える。
【００３７】
ＣＰＵ１０２は、各処理（ここでは特にＪａｖａＶＭ１０５）を実行するプロセッサである。ＪａｖａＶＭ（Ｊａｖａ仮想マシン）１０５は、ＣＰＵ１０２によって実行され、メモリ１０３を管理する。このＪａｖａＶＭ１０５は、データ参照関係把握部１０６、データ移動可否判定部１０７、データ移動部１０８を含む。また、このＪａｖａＶＭ１０５は、Ｊａｖａヒープ１０９を自動的に解放するＧＣ機能を有する。
【００３８】
メモリ１０３は、各種データを記憶するＲＡＭ（Random Access Memory）等の記憶装置である。このメモリ１０３は、ＪａｖａＶＭ１０５によって実行されるＪａｖａプログラム１０４、ＪａｖａＶＭ１０５が実行するＧＣの対象メモリ領域であるＪａｖａヒープ１０９、ＧＣ対象外のメモリ領域である外部ヒープ１１０−１〜３（以下、総称する場合、「外部ヒープ１１０」という。）を含む。なお、Ｊａｖａプログラム１０４は、計算機システム１０１に接続された外部記憶装置（ＨＤＤ等）１１１に記録されてもよい。
【００３９】
外部ヒープ１１０は、自身に関連付けされたデータから参照可能なＪａｖａヒープ１０９内のデータを、所定の移動契機（例えばＧＣの起動時、ユーザによって指示されたタイミング）ごとに、この外部ヒープ１１０に移動させるタイプの外部ヒープである。ここでいう参照可能とは、直接又は間接的に参照していることを示す。この外部ヒープ１１０にデータを関連付ける方法には、外部ヒープ１１０にデータを直接生成する方法や、ユーザ指示によって関連があることを明示する方法等がある。また外部ヒープ１１０に関連付けるデータを動的に決定する方法の一例として、以下の方法がある。すなわち、まず、Ｊａｖａヒープ１０９に存在するデータ群のうち、スタックから直接又は間接に参照されていないデータ群を取得する。次に、取得されたデータ群の所属クラスを抽出し、抽出されたクラス毎に、クラスから生成された全てのデータのサイズと、そのデータの参照先の全てのデータのサイズと、を全て加算した総オブジェクトサイズを算出する。その後、この総オブジェクトサイズが所定の閾値を超えるクラスから生成されるデータを、外部ヒープ１１０に関連付けさせる。
【００４０】
このような外部ヒープ１１０にデータが関連付けされると、このデータから参照可能なＪａｖａヒープ１０９内のデータが、移動契機ごとにこのデータが関連付けされた外部ヒープ１１０に移動する。なお、外部ヒープ１１０に関連付けされたデータは、この外部ヒープ１１０に配置されたデータ群の参照関係上の頂点のデータ、すなわち基点データとなる。このような外部ヒープ１１０−１、１１０−２、１１０−３は、Ｊａｖａプログラム１０４のソースコード中に記述された外部ヒープ生成文（図１Ｂのステップ２０４参照）で生成された外部ヒープ生成バイトコードを実行した回数だけ生成される。
【００４１】
ＪａｖａＶＭ１０５が備えるデータ参照関係把握部１０６は、外部ヒープ１１０に関連付けされたデータである基点データの参照関係を把握する。
【００４２】
データ移動可否判定部１０７は、データ参照関係把握部１０６によって把握されたデータの参照関係に基づいて、Ｊａｖａヒープ１０９から外部ヒープ１１０へのデータの移動可否を判定する。
【００４３】
データ移動部１０８は、データ移動可否判定部１０７による判定結果に基づいて、Ｊａｖａヒープ１０９から外部ヒープ１１０にデータを移動させる。
【００４４】
なお、これらの処理部１０６〜１０８の各々は、他の処理部１０６〜１０８の結果を利用する処理である。ここで、データ移動部１０８による処理を実行する度にデータ参照関係把握部１０６及びデータ移動可否判定部１０７の処理を実行すると、調査時間が非常に大きくなることが予想される。そのため、データ参照関係把握部１０６及びデータ移動可否判定部１０７の実行契機は、例えば外部ヒープ１１０を使用する一連の処理を１回実行した直後、Ｊａｖａプログラム１０４によって利用される全てのクラスロードが終了した直後等であるとよい。これにより、データ参照関係把握部１０６及びデータ移動可否判定部１０７の処理による調査時間を短縮可能である。
【００４５】
（メモリ管理方法の概要）
図６は、本発明の実施形態のメモリ管理方法の概要を示すフローチャートである。ＪａｖａＶＭ１０５が、図６に示す制御ロジックを実行する。
【００４６】
まずＪａｖａＶＭ１０５は、データの参照関係の調査契機に到達したか否かを判定する（２４０１）。ここでいう調査契機とは、Ｊａｖａプログラム用ＡＰＩやＪａｖａＶＭ１０５の起動時オプション、外部ファイル等によって指定されたプログラム中のある処理が開始するタイミングである。調査契機については図７、８を用いて詳細に後述する。
【００４７】
調査契機に到達した場合（２４０１でＹＥＳ）、ＪａｖａＶＭ１０５は、調査対象の全てのデータの参照関係を調査する（２４０２）。
【００４８】
その後、ＪａｖａＶＭ１０５は、ステップ２４０２で取得されたデータの参照関係に基づいて、外部ヒープ１１０に関連付けされた基点データから参照可能なデータ群の中に特定の参照構造（循環構造、リスト構造等）が存在する場合、その参照構造上のデータの全て又は一部の外部ヒープ１１０への移動を不可に（禁止）する（２４０３）。なお、その後、このステップ２４０３で移動不可にされたデータは、基点データが関連付けされた外部ヒープ１１０には移動されないよう処理される。
【００４９】
（データの参照関係の調査契機）
図７Ａは、本発明の実施形態の外部ファイルによって調査契機を指定する第１の例を示す図である。図７Ｂは、本発明の実施形態の外部ファイルによって調査契機を指定する第２の例を示す図である。
【００５０】
図７Ａ及び図７Ｂには、１行目に「基点データを生成するフルメソッド名、基点データの所属クラス、調査対象の参照関係の種類、（距離）」及び２行目に「調査契機」の書式の外部ファイルを示す。
【００５１】
図７Ａにおいて、ＭｙＣｌａｓｓ．ＭｙＭｅｔｈｏｄメソッド２２０１は、基点データを生成するフルメソッド名(クラス名＋メソッド名)である。ｊａｖａ．ｕｔｉｌ．ＨａｓｈＭａｐクラス２２０２は、基点データの所属クラスである。Ｃｉｒｃｌｅ２２０３は、調査対象の参照関係の種類が循環構造であることを指定するものである。数値「３」２２０４は、外部ヒープに移動させてもよいデータの、基点データからの参照の距離である。この数値２２０４が０である場合、循環構造のデータは、外部ヒープに移動させないことになる。メソッド２２０５は、ステップ２２０１〜２２０４で指定されるデータの参照関係の調査契機を示すものである。図７Ａでは、メソッドの実行時を調査契機として指定している。なお、調査契機をプログラム中の文によって指定してもよい。図７Ｂにおいて、Ｌｉｓｔ２２０６は、調査対象の参照関係の種類がリスト構造であることを指定するものである。
【００５２】
図８は、本発明の実施形態のＪａｖａプログラムＡＰＩによって調査契機を指定する例を示す図である。図８では、図７Ａに示す内容をＪａｖａプログラムＡＰＩによって指定している。
【００５３】
図８において、Ｊａｖａプログラム２３０１は、外部ヒープを生成するステップ２３０２と、生成された外部ヒープ内に基点データ（ＭｙＣｌａｓｓのインスタンス）を生成するステップ２３０３と、調査対象の参照関係の種類を指定するステップ２３０４と、ｒｅｆｅｒｅｎｃｅＣｈｅｃｋメソッドを呼び出すことによって実際に調査を指示するステップ２３０５と、を含む。なお、ステップ２３０４の第１引数Ｃｉｒｃｌｅ、第２引数０は、それぞれ図７ＡのＣｉｒｃｌｅ２２０３、数値２２０４と同義である。
【００５４】
図７Ａ及び図７Ｂに示す外部ファイルや図８に示すＪａｖａプログラムＡＰＩに基づいて、ＪａｖａＶＭ１０５は、指定された契機で指定されたデータの参照関係を調査することができる。なお、調査箇所は、Ｊａｖａプログラムの実行に大きな影響を及ぼさない箇所が適切に指定されるとよい。これは、長い時間を要することが予想される参照関係の調査の実用性を高めるためである。
【００５５】
調査対象の参照関係としては、例えば循環構造及びリスト構造がある。
【００５６】
調査対象の参照関係が循環構造である場合、まず、全データの参照関係と参照の深さを調べる。次に、基点データからの参照関係が循環している場合に、基点データから参照可能なデータの内のどのデータを外部ヒープに移動させないかを判定する。その後、移動させないと判定されたデータの所属クラスに、外部ヒープメモリへの移動不可フラグを付与する。この移動不可フラグが付与された所属クラスのデータ群は、外部ヒープへの移動が禁止される。
【００５７】
一方、調査対象の参照関係がリスト構造である場合、まず、基点データからの参照を調べる。次に、基点データから参照可能なデータに、所属クラスが基点データと同一のデータが存在するか否かを判定する。その後、所属クラスが基点データと同一のデータが存在すると判定された場合、その所属クラスに、外部ヒープへの移動不可フラグを付与する。この移動不可フラグは、調査対象の参照関係が循環構造である場合と同義である。
【００５８】
（循環構造の場合の制御ロジック）
図９は、本発明の実施形態のデータ移動可否判定部１０７及びデータ移動部１０８の制御ロジックを示すフローチャートである。図９のステップ６０１及び６０２は、図６のステップ２４０２に対応する。ステップ６０３は、図６のステップ２４０３に対応する。
【００５９】
まず、データ参照関係把握部１０６は、全データの参照の深さを求める（６０１）。ここでは、データ参照関係把握部１０６は、処理開始時点のデータの参照関係を把握し、把握されたデータの参照関係に基づいて、全データの参照の深さを求めるとともに、全データに参照の深さを付与する。参照の深さとは、ＧＣルート集合からの距離、すなわちＧＣルート集合から参照を辿った数である。このステップ６０１の処理については図１０及び図１１を用いて具体的に後述する。
【００６０】
次に、データ参照関係把握部１０６は、ステップ６０１で求められた全データの参照の深さのうち、外部ヒープに関連付けされた基点データの参照の深さを把握する（６０２）。
【００６１】
その後、データ移動可否判定部１０７は、ステップ６０２で把握された基点データの参照の深さと、基点データから参照可能なデータの参照の深さと、を比較して、循環構造を構成するデータを検出する。また、検出されたデータについての外部ヒープへの移動の可否を判定する。さらに、移動不可と判定されたデータの所属クラスに、外部ヒープへの移動不可フラグを付与する（６０３）。このステップ６０３の処理については図１２及び図１３を用いて具体的に後述する。
【００６２】
以下、図９の各処理について詳細に説明する。なお、図９の各処理の説明に先立ち、循環構造のデータについて説明する。
【００６３】
図１０は、循環構造のデータ間の参照関係の一例を示す図である。図１０において、丸印はデータを、丸印の内側のアルファベットはデータの所属クラスを、矢印はデータ間の参照関係を示す。例えば、参照１１０７は、所属クラスＡのデータ１１０１が、所属クラスＢのデータ１１０２を参照することを示す。なお、参照１１０６の参照元はＧＣルート集合である。ＧＣルート集合とは、ＧＣによってデータの参照関係を辿る際の辿り始めのデータ（オブジェクト）である。このＧＣルート集合は、ＣＰＵ１０２内のレジスタや、Ｊａｖａプログラム１０４の実行過程で生成されるスタックフレーム内、ＪａｖａＶＭ１０５自体を構成するプログラム内等に定義される。
【００６４】
図１１は、本発明の実施形態の循環構造のデータの参照の深さを調査する制御ロジックを示すフローチャートである。図１１に示す制御ロジックは、図９のステップ６０１に対応する。
【００６５】
まず、データ参照関係把握部１０６は、全データの参照の深さを０として初期化する（７０１）。次に、データ参照関係把握部１０６は、現在の参照の深さを１にセットする（７０２）。その後、データ参照関係把握部１０６は、ＧＣルート集合から参照可能なデータに、現在の参照の深さである１をセットして、このデータをスタックにＰＵＳＨする（７０３）。なお、ここでのスタックは、一般的なＦｉｒｓｔ  Ｉｎ  Ｌａｓｔ  Ｏｕｔのデータ構造である。スタックへのデータの追加をＰＵＳＨ、スタックからのデータの取り出しをＰＯＰという。図１０に示す例では、ＧＣルート集合から参照可能なデータ１１０１に、参照の深さ１をセットして、このデータ１１０１をスタックにＰＵＳＨする。
【００６６】
その後、データ参照関係把握部１０６は、スタックが空であるか否かを判定する（７０４）。スタックが空である場合（７０４でＹＥＳ）、処理を終了する。一方、スタックが空でない場合（７０４でＮＯ）、スタックからデータを一つＰＯＰする（７０５）。図１０に示す例では、データ１１０１がＰＯＰされる。なお、以降の説明では、ステップ７０５でＰＯＰされたデータを「Ｏｂｊ」という。
【００６７】
その後、データ参照関係把握部１０６は、ステップ７０５でＰＯＰされたデータＯｂｊから参照可能なデータが存在するか否かを判定する（７０６）。図１０に示す例では、データ１１０１から参照可能なデータ１１０２が存在するので、ステップ７０７に進む。
【００６８】
ステップ７０７に進むと、データ参照関係把握部１０６は、（１）ステップ７０６で検出されたデータの参照の深さが０（初期状態）である、及び、（２）ステップ７０６で検出されたデータの参照の深さがステップ７０５でＰＯＰされたデータＯｂｊの参照の深さよりも大きい、のうちの少なくとも一方の条件を満たすか否かを判定する（７０７）。図１０に示す例では、データ１１０２の参照の深さは０（初期状態）であるため、条件（１）を満たすので、ステップ７０８に進む。
【００６９】
ステップ７０８に進むと、データ参照関係把握部１０６は、ステップ７０６で検出されたデータの参照の深さとして、ステップ７０５でＰＯＰされたデータＯｂｊの参照の深さの値に１を加算した値をセットし、ステップ７０６で検出されたデータをスタックにＰＵＳＨする（７０８）。図１０に示す例では、データ１１０２の参照の深さとして２がセットされる。その後、ステップ７０４に戻る。
【００７０】
以降、ステップ７０４からステップ７０８の処理は、スタックが空になるまで繰り返される。これにより、ＧＣルート集合から参照可能な全てのデータの各々に対して、ステップ７０８の処理は一回だけ実行される。図１０に示す例では、データ１１０２から参照可能なデータ１１０３−１、１１０３−２の参照の深さとして、３がセットされる（図１２参照）。また、データ１１０３−１、１１０３−２から参照可能なデータ１１０４−１、１１０４−２の参照の深さとして、４がセットされる（図１２参照）。なお、データ１１０４−１、１１０４−２から参照可能なデータ１１０１の参照の深さとして１がセットされており、ステップ７０５でＰＯＰされるデータ１１０４の参照の深さ４よりも小さいため（７０７でＮＯ）、前述した条件（１）（２）のいずれも満たさないので、ステップ７０４に進む。その後、スタックが空であるため（７０４でＹＥＳ）、処理を終了する。
【００７１】
図１２は、本発明の実施形態の循環構造のデータの参照の深さを求めた結果を示す図である。図１２において、深さ１３０１は、データ１１０１の参照の深さである数値１を示す。同様に、深さ１３０２、１３０３−１（２）、１３０４−１（２）は、それぞれデータ１１０２、１１０３−１（２）、１１０４−１（２）の参照の深さである数値２、３、４を示す。
【００７２】
次に、図９のステップ６０２について説明する。
【００７３】
データ参照関係把握部１０６は、基点データの参照の深さを把握する（６０２）。図１０に示す例では、囲み１１０５−１、１１０５−２内のデータをそれぞれ異なる外部ヒープに配置する場合、データ１１０３−１、１１０３−２が基点データとなる。これらデータ１１０３−１、１１０３−２の参照の深さは３である（図１３参照）。
【００７４】
次に、図９のステップ６０３について説明する。
【００７５】
図１３は、本発明の実施形態のデータの参照の深さに基づく循環構造のデータの移動可否判定の制御ロジックを示すフローチャートである。図１３に示す制御ロジックは、図９のステップ６０３に対応する。
【００７６】
まず、データ移動可否判定部１０７は、未処理の外部ヒープを一つ選択する（１００１）。図１２に示す例では、囲み１１０５−１に対応する外部ヒープが選択されるものとする。
【００７７】
次に、データ移動可否判定部１０７は、ステップ１００１で選択された外部ヒープに関連付けされた基点データから参照可能なデータのうち、参照の深さが基点データの参照の深さ以下であるデータの所属クラスに、外部ヒープへの移動を禁止する旨の移動不可フラグを付与する（１００２）。図１２に示す例では、囲み１１０５−１内の基点データ１１０３−１から参照可能なデータ１１０４−１、１１０１、１１０２のうち、基点データ１１０３−１の参照の深さ３以下の参照の深さを有するデータ１１０１（参照の深さ１）、１１０２（参照の深さ２）の所属クラスＡ、Ｂに、移動不可フラグが付与される。
【００７８】
図１４は、図１３のステップ１００２の詳細処理を示すフローチャートである。
【００７９】
まず、データ移動可否判定部１０７は、ステップ１００１で選択された外部ヒープに関連付けされた基点データを取得する（８０１）。図１２に示す例では、基点データ１１０３−１が取得される。なお、以下の説明では、ここで取得された基点データの参照の深さを「基点Ｄｅｐｔｈ」という。
【００８０】
次に、データ移動可否判定部１０７は、基点データから参照可能、且つ、基点データとの間で循環構造を構成するデータを取得する（８０２）。図１２に示す例では、基点データ１１０３−１から参照可能なデータ１１０４−１、１１０１、１１０２が取得される。なお、他の外部ヒープの基点データ１１０３−２とそのデータから参照可能なデータ１１０４−２は、取得されない。
【００８１】
ステップ８０２で取得されたデータが、ステップ８０４以降の処理が未処理のデータを含む場合には（８０３でＹＥＳ）、データ移動可否判定部１０７は、データの集合から未処理のデータを一つ選択する（８０４）。
【００８２】
その後、データ移動可否判定部１０７は、ステップ８０４で選択されたデータの参照の深さと、基点Ｄｅｐｔｈと、を比較する（８０５）。ステップ８０４で選択されたデータの参照の深さが、基点Ｄｅｐｔｈ以下である場合（８０５でＹＥＳ）、ステップ８０６に進む。
【００８３】
ステップ８０６に進むと、データ移動可否判定部１０７は、基点Ｄｅｐｔｈ以下の参照の深さを有するデータの所属クラスに、外部ヒープへの移動不可フラグを付与する（８０６）。図１２に示す例では、基点データ１１０３−１の参照の深さ３以下の参照の深さを有するデータ１１０１（参照の深さ１）、１１０２（参照の深さ２）の所属クラスＡ、Ｂに、移動不可フラグが付与される。付与された移動不可フラグは、データ移動部１０８の移動処理（図１５参照）で利用される。なお、前述のステップ８０５は、ステップ８０２で取得されたデータの全てに、このステップ８０６が適用されるのを防止するための処理である。
【００８４】
図１３に戻り、データ移動可否判定部１０７は、未処理の外部ヒープがあるか否かを判定する（１００３）。未処理の外部ヒープがある場合（１００３でＹＥＳ）、ステップ１００１に戻る。未処理の外部ヒープがない場合（１００３でＮＯ）、処理を終了する。
【００８５】
図１５は、本発明の実施形態のデータ移動の制御ロジックを示すフローチャートである。図５のデータ移動部１０８は、上記の移動不可フラグを利用して、移動すべきデータのみを外部ヒープに移動させる。
【００８６】
まず、データ移動部１０８は、移動先の外部ヒープの基点データを取得する（９０１）。図１２に示す例では、移動先の外部ヒープが囲み１１０５−１に対応する外部ヒープである場合、基点データ１１０３−１が取得される。
【００８７】
次に、データ移動部１０８は、基点データから参照可能、且つ、未処理のデータがあるか否かをチェックする（９０２）。図１２に示す例では、データ１１０４−１が存在するため（９０２でＹＥＳ）、ステップ９０３に進む。なお、所属クラスに移動不可フラグが付与されているデータ１１０１、１１０２や、他の外部ヒープ内のデータ１１０３−２、１１０４−２は、基点データ１１０３−１から参照可能なデータに含まれない。
【００８８】
ステップ９０３に進むと、データ移動部１０８は、外部ヒープへ移動可能な状態であるか否かをチェックする（９０３）。移動可能な状態とは、ＧＣ時に外部ヒープにデータを移動するのであればＪａｖａヒープ内でのＧＣの移動回数が一定値を超えた場合や、Ｊａｖａヒープの使用量が一定値を超えた場合等である。
【００８９】
ステップ９０４へ進むと、データ移動部１０８は、ステップ９０２で存在すると判定されたデータの所属クラスに、移動不可フラグが付与されているか否かをチェックする（９０４）。
【００９０】
ステップ９０３でＹＥＳ及びステップ９０４でＮＯの場合、データ移動部１０８は、外部ヒープに実際にデータを移動させる（９０６）。図１２に示す例では、データ１１０４−１が、囲み１１０５−１に対応する外部ヒープに移動する。
【００９１】
一方、ステップ９０３でＮＯ又はステップ９０４でＹＥＳの場合、データ移動部１０８は、ＧＣ時に外部ヒープにデータを移動させる場合には、Ｊａｖａヒープ内でデータを移動させる。そうでない場合には、データを移動させない（９０７）。このステップ９０７では、外部ヒープにデータを移動させなくても、少なくともプログラムが正常に実行可能な状態にする。
【００９２】
以降、ステップ９０３からステップ９０７の処理は、ステップ９０２で取得された未処理のデータの全てについて繰り返される。
【００９３】
図１６は、図１０に示す循環構造のデータに本発明を適用した場合のデータ配置を示す図である。データ１１０３−１を基点データとするデータ群は、外部ヒープ１２０１に配置される。同様に、データ１１０３−２を基点データとするデータ群は、外部ヒープ１２０１と異なる外部ヒープ１２０２に配置される。また、移動不可フラグが付与されたデータ１１０１、１１０２は、移動することなくＪａｖａヒープ１０９に配置される。
【００９４】
図１７は、図１０に示す循環構造のデータに従来のデータ配置方法を適用した場合のデータ配置を示す図である。外部ヒープ１２０１には、外部ヒープ１２０１に移動させることを想定していないデータ１１０１、１１０２が配置されている。そのため、外部ヒープの使用量の見積もりが難しい、外部ヒープ間で解放時間に大きな差が出る等の問題が発生する。言い換えると、本発明を適用して図１６に示すデータ配置とすることによって、このような問題を解決することができる。
【００９５】
（循環構造の場合の制御ロジックの変形例）
次に、循環構造の場合の制御ロジックの変形例を説明する。前述の制御ロジックでは、データの参照の深さ（ＧＣルート集合から参照を辿った数）に基づいて、外部ヒープへの移動の可否を判定した（図１３のステップ１００２参照）。ここでは、データの参照の深さの代わりに、データの距離（基点データから参照を辿った数）に基づいて、外部ヒープへの移動の可否を判定する。
【００９６】
図１８は、循環構造のデータ間の参照関係の他の例を示す図である。図１８に示す例では、囲み１９０６内の基点データ１９０３及びデータ１９０４のみが、同一の外部ヒープに配置されるべきデータである。また、距離１９０７、１９０８、１９０９、１９１０、１９１１は、それぞれデータ１９０１、１９０２、１９０３、１９０４、１９０５の基点データ１９０３からの参照上の距離の値４、５、１、２、３を示す。
【００９７】
図１９は、本発明の実施形態の循環構造のデータの距離を調査する制御ロジックを示すフローチャートである。図１９は、図１１のステップ７０１〜７０３、７０７、７０８を、それぞれステップ２００１〜２００３、２００７、２００８に置き換えたものである。以下では、図１１と同様の機能を果たす部分には同一の符号を付して重複する説明を適宜省略する。なお、図１９に示す制御ロジックは、図９のステップ６０１に対応する。
【００９８】
ステップ２００１では、データ参照関係把握部１０６は、全データの基点データからの参照上の距離、すなわち、基点データから参照を辿った数（以下、「距離」という。）を０として初期化する（２００１）。次に、データ参照関係把握部１０６は、現在の距離を１にセットする（２００２）。図１８に示す例では、基点データ１９０３に距離１がセットされる。その後、データ参照関係把握部１０６は、基点データから参照可能なデータに現在の距離１をセットして、このデータをスタックにＰＵＳＨする（２００３）。
【００９９】
ステップ２００７では、データ参照関係把握部１０６は、（１）ステップ７０６で検出されたデータの距離が０（初期状態）である、及び、（２）ステップ７０５でＰＯＰされたデータの距離よりも大きい、のうちの少なくとも一方の条件を満たすか否かを判定する（２００７）。その後ステップ２００８では、データ参照関係把握部１０６は、ステップ７０６で検出されたデータの距離として、ステップ７０５でＰＯＰされたデータＯｂｊの距離の値に１を加算した値をセットし、ステップ７０６で検出されたデータをスタックにＰＵＳＨする（２００８）。
【０１００】
以降、ステップ７０４からステップ２００８の処理は、スタックが空になるまで繰り返される。図１８に示す例では、基点データ１９０３の距離には、数値１がセットされる。また、基点データ１９０３から参照可能なデータ１９０４、１９０５、１９０１、１９０２の距離には、それぞれ数値２、３、４、５がセットされる。なお、データ１９０２から参照可能なデータ１９０３の距離は１がセットされており、ステップ７０５でＰＯＰされるデータ１９０２の距離５よりも小さいため（２００７でＮＯ）、上記の条件を満たさないので、ステップ７０４に進む。その後、スタックが空であるため（７０４でＹＥＳ）、処理を終了する。
【０１０１】
図２０は、本発明の実施形態のデータの距離に基づく循環構造のデータの移動可否判定の制御ロジックを示すフローチャートである。図２０は、図１４のステップ８０５を、ステップ２１０１に置き換えたものである。以下では、図１４と同様の機能を果たす部分には同一の符号を付して重複する説明を適宜省略する。なお、図２０に示す制御ロジックは、図１３のステップ１００２に対応する。
【０１０２】
ステップ２１０１では、データ移動可否判定部１０７は、ステップ８０４で選択されたデータの距離と、所定の閾値（例えば２）と、を比較する（２１０１）。所定の閾値とは、基点データから外部ヒープに移動可能なデータまでの距離の許容値である。ステップ８０４で選択されたデータの距離が、所定の閾値より大きい場合（２１０１でＹＥＳ）、ステップ８０６に進む。その後、データ移動可否判定部１０７は、基点データからの距離が所定の閾値より大きいデータの所属クラスに、移動不可フラグを付与する（８０６）。図１８に示す例では、基点データ１９０３からの距離が閾値２より大きいデータ１９０５、１９０１、１９０２の所属クラスＮ、Ｊ、Ｋに、移動不可フラグが付与される。なお、移動不可フラグが付与された所属クラスのデータは、外部ヒープに移動しない（図１５参照）。
【０１０３】
以上のように、本変形例によれば、データの参照の深さの代わりに、データの距離（基点データから参照を辿った数）に基づいて、外部ヒープへの移動の可否を判定することができる。
【０１０４】
（リスト構造の場合の制御ロジック）
以上、調査対象の参照関係が循環構造である場合を説明してきた。ここでは、調査対象の参照関係がリスト構造である場合について説明する。
【０１０５】
図２１は、リスト構造のデータ間の参照関係を示す図である。図２１において、丸印はデータを、丸印の内側のアルファベットはデータの所属クラスを、矢印はデータの参照関係を示す。例えば、参照１５０４−１は、所属クラスＦのデータ１５０１−１が、同一の所属クラスＦのデータ１５０１−２を参照することを示す。
【０１０６】
リスト構造とは、データ集合（図２１ではデータ１５０１−１（２、３）、１５０２−１（２、３）、１５０３−１（２、３）の単位で構成されるデータ集合）を、データ間参照（図２１ではデータ１５０１−１、１５０１−２、１５０１−３間の参照１５０４−１、１５０４−２）で参照可能な状態としたものである。同一所属クラスのデータ同士が参照関係にあることが多い。図２１に示す例では、同一所属クラスＦのデータ１５０１−１、１５０１−２、１５０１−３が参照関係にある。なお、図２１において、囲み１５０５−１内のデータ１５０１−１、１５０２−１、１５０３−１のみが、同一の外部ヒープに配置されるべきデータであるものとする。
【０１０７】
図２２は、本発明の実施形態のデータの参照の深さに基づくリスト構造のデータの移動可否判定の制御ロジックを示すフローチャートである。図２２は、図１４のステップ８０２を、ステップ１８０１に置き換えるとともに、ステップ１８０２を追加したものである。以下では、図１４と同様の機能を果たす部分には同一の符号を付して重複する説明を適宜省略する。図２２に示す制御ロジックは、図１３のステップ１００２に対応する。
【０１０８】
ステップ１８０１では、データ移動可否判定部１０７は、基点データから直接参照可能なデータを取得する（１８０１）。図２２に示す例では、基点データ１５０１−１から直接参照可能なデータ１５０２−１、１５０３−１、１５０１−２が取得される。
【０１０９】
ステップ１８０２では、データ移動可否判定部１０７は、ステップ８０４で選択されたデータと、基点データとが、同じ所属クラスであるか否かを判定する（１８０２）。両者が同じ所属クラスである場合（１８０２でＹＥＳ）、ステップ８０６に進む。図２１に示す例では、データ１５０１−２と、基点データ１５０１−１とが、同じ所属クラスＦであるため（１８０２でＹＥＳ）、クラスＦに移動不可フラグが付与される。なお、移動不可フラグが付与されたクラスＦのデータ１５０１−２等は、外部ヒープに移動しない（図１５参照）。
【０１１０】
図２３は、図２２に示すリスト構造のデータに本発明を適用した場合のデータ配置を示す図である。囲み１５０５−１内のデータ１５０１−１、１５０２−１、１５０３−１は、外部ヒープ１６０１−１に配置される。その他のデータ群は、移動することなくＪａｖａヒープ１０９に配置される。
【０１１１】
図２４は、図２２に示すリスト構造のデータに従来のデータ配置方法を適用した場合のデータ配置を示す図である。外部ヒープ１６０１−１には、外部ヒープ１６０１−１に移動させることを想定していないデータ１５０１−２（３）、１５０２−２（３）、１５０３−２（３）が配置される。そのため、外部ヒープの使用量の見積もりが難しい、外部ヒープ間で解放時間に大きな差が出る等の問題が発生する。言い換えると、本発明を適用して図２３に示すデータ配置とすることによって、このような問題を解決することができる。
【０１１２】
以上、本発明の実施の形態について説明したが、上記実施の形態は本発明の適用例の一つを示したものであり、本発明の技術的範囲を上記実施の形態の具体的構成に限定する趣旨ではない。
【符号の説明】
【０１１３】
１０１ 計算機システム
１０２ ＣＰＵ
１０３ メモリ
１０４ Ｊａｖａプログラム
１０５  ＪａｖａＶＭ（Ｊａｖａ仮想マシン）
１０６ データ参照関係把握部
１０７ データ移動可否判定部
１０８ データ移動部
１０９ Ｊａｖａヒープ
１１０ 外部ヒープ
１１１ 外部記憶装置
【図１Ａ】
0005380695.tif 000002
【図１Ｂ】
0005380695.tif 000003
【図２】
0005380695.tif 000004
【図３】
0005380695.tif 000005
【図４】
0005380695.tif 000006
【図５】
0005380695.tif 000007
【図６】
0005380695.tif 000008
【図７Ａ】
0005380695.tif 000009
【図７Ｂ】
0005380695.tif 000010
【図８】
0005380695.tif 000011
【図９】
0005380695.tif 000012
【図１０】
0005380695.tif 000013
【図１１】
0005380695.tif 000014
【図１２】
0005380695.tif 000015
【図１３】
0005380695.tif 000016
【図１４】
0005380695.tif 000017
【図１５】
0005380695.tif 000018
【図１６】
0005380695.tif 000019
【図１７】
0005380695.tif 000020
【図１８】
0005380695.tif 000021
【図１９】
0005380695.tif 000022
【図２０】
0005380695.tif 000023
【図２１】
0005380695.tif 000024
【図２２】
0005380695.tif 000025
【図２３】
0005380695.tif 000026
【図２４】
0005380695.tif 000027