(57)【要約】【課題】メモリ内の若い世代領域に対して古い世代領域のゴミ集めを的確なタイミングで実行し、システム障害やシステムの性能低下をできる限り回避する。【解決手段】若い世代領域４２の生存中の全てのオブジェクトを古い世代領域４３へ移す若い世代のゴミ集め及び古い世代のゴミ集めを実行するゴミ集め実行部２１と、若い世代領域４２のオブジェクトの生存量ＥＳを予測する予測生存量算出部２４と、古い世代領域４３の空き容量ＯＦを計測するメモリ監視部２２と、予測された若い世代領域４２のオブジェクト生存量ＥＳと計測された古い世代領域４３の空き容量ＯＦとを比較し、空き容量ＯＦが大きければ、ゴミ集め実行部２１に若い世代領域４２のゴミ集めを実行させ、空き容量ＯＦが小さければ、ゴミ集め実行部２１に古い世代領域４３のゴミ集め実行させた後、若い世代領域４２のゴミ集めを実行させるゴミ集め制御部２３とを有する。【選択図】図１
2007213252.tif 000002
【特許請求の範囲】
【請求項１】
メモリのヒープ領域を複数の世代別の領域に分け、各世代別の領域のゴミ集めを行うゴミ集め処理プログラムにおいて、
複数の世代の領域のゴミ集めを行うゴミ集め実行ステップと、
複数の世代の領域のうちの一つの世代の領域（以下、若い世代領域とする）に対するゴミ集め実行で、該若い世代領域に存在している１以上のオブジェクトのうちから生存中のオブジェクトを該若い世代領域よりも一つ古い世代の領域（以下、古い世代領域とする）へ移すオブジェクトの量を、過去のゴミ集め実績から予測する移動量予測ステップと、
前記古い世代領域の空き容量を計測する空き容量計測ステップと、
前記移動量予測ステップで予測された前記若い世代領域のオブジェクトの移動量が、前記空き容量計測ステップで計測された前記古い世代領域の空き容量より小さければ、該若い世代領域のゴミ集めを前記ゴミ集め実行ステップで実行させ、該若い世代領域のオブジェクトの移動量が該古い世代領域の空き容量以上であれば、該古い世代領域を含む領域のゴミ集めを該ゴミ集め実行ステップで実行させるゴミ集め制御ステップと、
を前記メモリを備えているコンピュータに実行させることを特徴とするゴミ集め処理プログラム。
【請求項２】
請求項１に記載のゴミ集め処理プログラムにおいて、
前記ゴミ集め実行ステップでは、前記若い世代領域のゴミ集めの際には、該若い世代領域に存在している１以上のオブジェクトのうちから、生存中のオブジェクトを全て前記古い世代領域に移し、
前記移動量予測ステップは、
前記若い世代領域の使用量を計測する使用量計測ステップと、
ゴミ集め前のオブジェクトの領域使用量に対するゴミ集め後のオブジェクトの生存量の割合である生存率を、前記若い世代領域のゴミ集め実行毎に計測する生存率計測ステップと、
前記生存率計測ステップで計測された過去の生存率から次のゴミ集めの際の生存率を予測する生存率予測ステップと、
前記使用量計測ステップで計測された前記若い世代領域の使用量と前記生存量予測ステップで予測された前記生存率とから、該若い世代領域のオブジェクトの生存量を予測する生存量予測ステップと、を有し、
前記ゴミ集め制御ステップでは、前記生存量予測ステップで予測された前記若い世代領域のオブジェクトの生存量を、該若い世代領域のオブジェクトの移動量として、前記古い世代領域の空き容量と比較する、
ことを特徴とするゴミ集め処理プログラム。
【請求項３】
請求項１に記載のゴミ集め処理プログラムにおいて、
前記ゴミ集め実行ステップでは、前記若い世代領域のゴミ集めの際には、該若い世代領域に存在している１以上のオブジェクトのうちから、予め定められた回数のゴミ集めで生き残ったオブジェクトのみを前記古い世代領域に移し、
前記移動量予測ステップは、
前記若い世代領域の使用量を計測する使用量計測ステップと、
ゴミ集め前のオブジェクトの領域使用量に対するゴミ集め後のオブジェクトの生存量の割合である生存率を、前記若い世代領域のゴミ集め実行毎に計測する生存率計測ステップと、
前記生存率計測ステップで計測された過去の生存率から次のゴミ集めの際の生存率を予測する生存率予測ステップと、
前記若い世代領域のオブジェクトの生存量に対する、前記若い世代領域のゴミ集めで前記古い世代領域に移るオブジェクトの昇進量の割合である昇進率を、該若い世代領域のゴミ集め実行毎に計測する昇進率計側ステップと、
前記昇進率計側ステップで計測された過去の昇進率から次のゴミ集めでの昇進率を予測する昇進率予測ステップと、
前記使用量計測ステップで計測された前記若い世代領域の使用量と前記生存量予測ステップで予測された前記生存率と前記昇進率予測ステップで予測された次のゴミ集めでの昇進率とから、次のゴミ集めでの昇進量を予測する昇進量予測ステップと、を有し、
前記ゴミ集め制御ステップでは、前記昇進量予測ステップで予測された前記若い世代領域のオブジェクトの昇進量を、該若い世代領域のオブジェクトの移動量として、前記古い世代領域の空き容量と比較する、
ことを特徴とするゴミ集め処理プログラム。
【請求項４】
請求項１から３のいずれか一項に記載のゴミ集め処理プログラムにおいて、
前記若い世代領域のゴミ集め実行中に、前記空き容量計測ステップにより前記古い世代領域の空き容量が該若い世代領域のゴミ集めに十分な量でなくなったことが計測されると、前記ゴミ集め制御ステップでは、前記ゴミ集め実行ステップに対して、前記若い世代領域のゴミ集めの実行を中断又は中止させ、前記古い世代領域を含む領域のゴミ集めを実行させる、
ことを特徴とするゴミ集め処理プログラム。
【請求項５】
メモリのヒープ領域を複数の世代別の領域に分け、各世代別の領域のゴミ集めを行うゴミ集め処理方法において、
複数の世代の領域のゴミ集めを行うゴミ集め実行工程と、
複数の世代の領域のうちの一つの世代の領域（以下、若い世代領域とする）に対するゴミ集め実行で、該若い世代領域に存在している１以上のオブジェクトのうちから生存中のオブジェクトを該若い世代領域よりも一つ古い世代の領域（以下、古い世代領域とする）へ移すオブジェクトの量を、過去のゴミ集め実績から予測する移動量予測工程と、
前記古い世代領域の空き容量を計測する空き容量計測工程と、
前記移動量予測工程で予測された前記若い世代領域のオブジェクトの移動量が、前記空き容量把握工程で計測された前記古い世代領域の空き容量より小さければ、該若い世代領域のゴミ集めを前記ゴミ集め実行工程で実行させ、該若い世代領域のオブジェクトの移動量が該古い世代領域の空き容量以上であれば、該古い世代領域を含む領域のゴミ集めを該ゴミ集め実行工程で実行させるゴミ集め制御工程と、
を含むことを特徴とするゴミ集め処理方法。
【請求項６】
請求項５に記載のゴミ集め処理プログラムにおいて、
前記若い世代領域のゴミ集め実行中に、前記空き容量計測工程により前記古い世代領域の空き容量が該若い世代領域のゴミ集めに十分な量でなくなったことが計測されると、前記ゴミ集め制御工程では、前記ゴミ集め実行工程に対して、前記若い世代領域のゴミ集めの実行を中断又は中止させ、前記古い世代領域を含む領域のゴミ集めを実行させる、
ことを特徴とするゴミ集め処理方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、メモリのヒープ領域を複数の世代別の領域に分け、各世代別の領域のゴミ集めを行うゴミ集め処理プログラム及びゴミ集め処理方法に関する。
【背景技術】
【０００２】
ゴミ集め処理（Garbage Collection）は、メモリ領域内で不用なオブジェクト、より正確には、システムからアクセス不可能なオブジェクトをゴミとして回収し、メモリ領域内に空き領域を確保する処理である。なお、本出願において、オブジェクトとは、構造体、レコード型、Lispのconsセルなど、メモリ上の連続領域に割り当てられるデータ構造のことである。このゴミ集め処理は、プログラムのスコープに縛られずに、動的に利用されるメモリの領域を自動管理するために実行される。動的に利用されるメモリ領域とは、メモリ領域の生存期間がプログラムの生存期間と異なるメモリ領域である。このような動的メモリは、スタック領域とヒープ領域に割り付けられる。プログラムのスコープによってメモリ領域の生存期間が決まるメモリ領域は、通常スタック領域に割り付けられる。プログラムのスコープとは関係なく生存期間が決まるメモリ領域はヒープ領域に割り付けられる。
【０００３】
このヒープ領域は、多くの場合、複数の世代別の領域に分けられている。若い世代領域に対して古い世代領域は、オブジェクトが割り付けられてからの時間が相対的に長い領域である。作成されたオブジェクトは、まず、オブジェクトの割付処理により、最も若い世代領域に割り付けられる。割付処理では、若い世代領域に十分な空きがなくなると、ゴミ集め処理が呼び出される。ゴミ集め処理では、若い世代領域に属するオブジェクトのうち、システムからアクセス可能なオブジェクト、つまり生存中のオブジェクトが古い世代領域に移される。これを、一般的に、「殿堂入り」と呼ぶ。このゴミ集め処理の結果、若い世代領域には不要なオブジェクトのみが残り、若い世代領域に新たなオブジェクトが割り付けられるようになる。若い世代領域からゴミ集め処理で生き残ったオブジェクトが移されてくると、古い世代領域の空き領域が次第に少なくなる。このため、従来技術では、古い世代領域の空き領域が十分に確保できなると想定される条件を、ユーザが予め定め、このユーザが定めた条件を満たしたときに、古い世代領域のゴミ集め処理が実行される。
【０００４】
以上のような世代別のゴミ集めや、ゴミ集めの基本的手法に関しては、以下の非特許文献１，２等に詳細に記載されている。
【０００５】
【非特許文献１】「ゴミ集めの基礎と最近の動向」、情報処理学会会誌、Vol. 35、1994年、p.991-1032
【非特許文献２】「Garbage Collection: Algorithms for Automatic Dynamic Memory Management」、Richard Jones, Rafael Lins、1999年、John Wiley & Sons Ltd.(ISBN 0-471-94148-4)
【発明の開示】
【発明が解決しようとする課題】
【０００６】
しかしながら、従来技術では、前述したように、ユーザが定めた条件を満たしたときに、古い世代領域のゴミ集め処理が実行されるため、以下のような問題点がある。つまり、ユーザが古い世代領域のゴミ集め処理をあまり実行しない方向にこの条件を設定した場合、実際には古い世代領域の空き領域が十分に確保されていない状態になっているにも関わらず、この条件を満たさないことがあり、若い世代領域のゴミ集めを実行しようとしても、この若い世代領域のゴミ集めを実行できず、システム障害を招く虞があるという問題点がある。また、逆に、ユーザが古い世代領域のゴミ集め処理を頻繁に実行する方向にこの条件を設定した場合、実際には古い世代領域の空き領域が十分に確保されている状態になっているにも関わらず、この条件を満たしてしまい、頻繁に古い世代領域のゴミ集めが実行され、システムの性能低下を招くという問題点がある。
【０００７】
そこで、本発明は、以上のような従来技術の問題点に着目し、若い世代領域のゴミ集めに対して古い世代領域のゴミ集めを的確なタイミングで実行し、システム障害やシステムの性能低下をできる限り回避することができるゴミ集め処理プログラム及びゴミ集め処理方法を提供することを目的とする。
【課題を解決するための手段】
【０００８】
前記目的を達成するためのゴミ集め処理プログラムは、
メモリのヒープ領域を複数の世代別の領域に分け、各世代別の領域のゴミ集めを行うゴミ集め処理プログラムにおいて、
複数の世代の領域のゴミ集めを行うゴミ集め実行ステップと、
複数の世代の領域のうちの一つの世代の領域（以下、若い世代領域とする）に対するゴミ集め実行で、該若い世代領域に存在している１以上のオブジェクトのうちから生存中のオブジェクトを該若い世代領域よりも一つ古い世代の領域（以下、古い世代領域とする）へ移すオブジェクトの量を、過去のゴミ集め実績から予測する移動量予測ステップと、
前記古い世代領域の空き容量を計測する空き容量計測ステップと、
前記移動量予測ステップで予測された前記若い世代領域のオブジェクトの移動量が、前記空き容量計測ステップで計測された前記古い世代領域の空き容量より小さければ、該若い世代領域のゴミ集めを前記ゴミ集め実行ステップで実行させ、該若い世代領域のオブジェクトの移動量が該古い世代領域の空き容量以上であれば、該古い世代領域を含む領域のゴミ集めを該ゴミ集め実行ステップで実行させるゴミ集め制御ステップと、
を前記メモリを備えているコンピュータに実行させることを特徴とする。
【０００９】
ここで、前記ゴミ集め処理プログラムは、
前記若い世代領域のゴミ集め実行中に、前記空き容量計測ステップにより前記古い世代領域の空き容量が該若い世代領域のゴミ集めに十分な量でなくなったことが計測されると、前記ゴミ集め制御ステップでは、前記ゴミ集め実行ステップに対して、前記若い世代領域のゴミ集めの実行を中断又は中止させ、前記古い世代領域を含む領域のゴミ集めを実行させるものであることが好ましい。
【００１０】
また、前記目的を達成するためのゴミ集め処理方法は、
メモリのヒープ領域を複数の世代別の領域に分け、各世代別の領域のゴミ集めを行うゴミ集め処理方法において、
複数の世代の領域のゴミ集めを行うゴミ集め実行工程と、
複数の世代の領域のうちの一つの世代の領域（以下、若い世代領域とする）に対するゴミ集め実行で、該若い世代領域に存在している１以上のオブジェクトのうちから生存中のオブジェクトを該若い世代領域よりも一つ古い世代の領域（以下、古い世代領域とする）へ移すオブジェクトの量を、過去のゴミ集め実績から予測する移動量予測工程と、
前記古い世代領域の空き容量を計測する空き容量計測工程と、
前記移動量予測工程で予測された前記若い世代領域のオブジェクトの移動量が、前記空き容量把握工程で計測された前記古い世代領域の空き容量より小さければ、該若い世代領域のゴミ集めを前記ゴミ集め実行工程で実行させ、該若い世代領域のオブジェクトの移動量が該古い世代領域の空き容量以上であれば、該古い世代領域を含む領域のゴミ集めを該ゴミ集め実行工程で実行させるゴミ集め制御工程と、
を含むことを特徴とする。
【発明の効果】
【００１１】
本発明によれば、若い世代領域に格納されている１以上のオブジェクトのうちから古い世代領域へ移すオブジェクトの量を、過去のゴミ集め実績から予測し、この移動量と古い世代領域の空き容量と比較し、その結果に応じて、古い世代領域のごみ集めを実行するので、古い世代領域のゴミ集めのタイミングが比較的的確になり、システム障害の可能性を低くすると共に、システムの性能低下を抑えることができる。
【発明を実施するための最良の形態】
【００１２】
以下、本発明に係るゴミ集め処理の各種実施形態について、図面を用いて説明する。
【００１３】
［第一の実施形態］
第一の実施形態について、図１〜図１８を用いて説明する。
【００１４】
図１に示すように、本実施形態のゴミ集め処理プログラム３２を実行するコンピュータ１０は、各種処理を実行するプロセッサ１１と、プロセッサ１１が実行するプログラムが記憶されているプログラムメモリ３０と、各種データが記憶されるデータメモリ４０とを備えている。なお、図１には示していないが、このコンピュータ１０は、処理結果等を表示するディスプレイ、データや指示等を入力するための入力装置、外部記憶装置、外部の通信網を介して他のコンピュータ等と通信するための通信処理装置等も備えている。
【００１５】
この実施形態のコンピュータ１０は、Java言語（Javaは米国Sun Microsystems, Inc.及びその他の国における商標または登録商標）で記述されたプログラムを実行する。このため、コンピュータ１０は、内部に、このJava言語で記述されたプログラムを実行するために仮想マシン１２を形成する。この仮想マシン１２をコンピュータ１０内に形成するための仮想マシンプログラム３１は、プログラムメモリ３０内に格納されている。仮想マシンプログラム３１には、ゴミ集め処理（Garbage Collection）プログラム３２が含まれている。また、このプログラムメモリ３０内には、仮想マシン１２で実行する実行プログラム３３が格納されている。この実行プログラム３３は、Java言語から中間言語に変換した状態で、プログラムメモリ３３に格納されている。
【００１６】
データメモリ４０のヒープ領域４１は、若い世代領域４２と古い世代領域４３とに分けられている。
【００１７】
プロセッサ１１は、前述したように、仮想マシンプログラム３１を実行することで仮想マシン１２を形成する。この仮想マシン１２は、機能的に、実行プログラム３３を解読する命令解読部１３と、命令解読部１３で解読された命令を実行する命令実行部１４と、命令実行部１４での命令実行過程でオブジェクトを記憶する必要性が生じたときにデータメモリ４０に対する記憶割当を管理・実行する記憶割当部１５と、データメモリ４０内の不要なオブジェクトを回収するゴミ集め処理部２０とを有している。このゴミ集め処理部２０の機能は、前述のゴミ集め処理プログラム３２の実行で実現する。
【００１８】
ゴミ集め処理部２０は、データメモリ４０の若い世代領域４２及び古い世代領域４３のぞれぞれのゴミ集めを実行するゴミ集め実行部２１と、各領域４２，４３の使用量及び空き容量を計測するメモリ監視部２２と、メモリ監視部２２での計測結果等に基づいて若い世代領域４２のオブジェクト生存量ＥＳを予測する予測生存量算出部２４と、これらの各部２１，２２，２４を制御するゴミ集め制御部２３とを有している。予測生存量算出部２４は、ゴミ集め前のオブジェクトの領域使用量ＹＵに対するゴミ集め後のオブジェクトの生存量Ｓの割合である生存率ＳＲ（＝Ｓ/ＹＵ）を計測し、過去の生存率ＳＲの実績から現在の生存率ＥＳＲを予測する生存率予測部２５と、予測された若い世代領域４２の現在の生存率ＥＳＲと現在の若い世代領域４２の使用量ＹＵとから、若い世代領域４２のオブジェクトの生存量ＥＳ（＝ＹＵ・ＥＳＲ）を予測する生存量予測部２６とを有する。
【００１９】
記憶割当部１５は、命令実行部１４からオブジェクトのメモリ割当命令を受けると、若い世代領域４２に格納領域を確保し、この格納領域の先頭アドレスを命令実行部１４に返す。記憶割当部１５は、仮に、若い世代領域４２に十分な格納領域を確保できないと認識した場合、ゴミ集め処理部２０に対してゴミ集め実行命令を出力し、データメモリ４０内のゴミ集めを実行させる。ゴミ集め処理部２０は、データメモリ４０内のゴミ集めが終了すると、ゴミ集め終了の旨を記憶割当部１５に返す。すると、この記憶割当部１５は、ゴミ集め後の若い世代領域４２にオブジェクトの格納領域を確保し、この格納領域の先頭アドレスを命令実行部１４に返す。記憶割当部１５は、ゴミ集め後であっても、若い世代領域４２に十分な格納領域を確保できないと認識した場合、メモリ不足の旨をディスプレイ等に出力させる。
【００２０】
次に、ゴミ集め処理部２０の動作内容、言い換えると、ゴミ集め処理プログラム３２の実行による処理内容について、図３に示すフローチャートに従って説明する。
【００２１】
ゴミ集め処理部２０のゴミ集め制御部２３は、前述の記憶割当部１５からゴミ集め実行命令を受けると、生存率予測部２５が生存量予測部２６に、若い世代領域４２の予測生存率をＥＳＲとして渡す（Ｓ１）。この際、ゴミ集め実行命令の受信が例えば５回目以降である場合には、生存率予測部２５は、ここで予測した予測生存率をＥＳＲとして生存量予測部２６に渡し、ゴミ集め実行命令の受信が例えば５回目未満である場合には、生存率予測部２５は、予め設定された予測生存率をＥＳＲとして生存量予測部２６に渡す。
【００２２】
続いて、メモリ監視部２２が若い世代領域４２の使用量ＹＵ及び古い世代領域４３の空き量ＯＦを計測し、若い世代領域４２の使用量ＹＵを生存率予測部２５及び生存量予測部２６に渡すと共に、古い世代領域４３の空き量ＯＦをゴミ集め制御部２３に渡す（Ｓ２）。
【００２３】
生存量予測部２６は、若い世代領域４２の使用量ＹＵを受け取ると、この使用量ＹＵと先に受け取った若い世代領域４２の予測生存率ＥＳＲとから、若い世代領域４２の予測生存量ＥＳ（＝ＹＵ×ＥＳＲ）を求め、この予測生存量ＥＳをゴミ集め制御部２３に渡す（Ｓ３）。
【００２４】
ゴミ集め制御部２３は、若い世代領域４２の予測生存量ＥＳを受け取ると、先に受け取った古い世代領域４３の空き量ＯＦと若い世代領域４２の予測生存量ＥＳとの大小関係を比較し（Ｓ４）、古い世代領域４３の空き量ＯＦに対して若い世代領域４２の予測生存量ＥＳが大きければ、ゴミ集め実行部２１に古い世代領域４３のゴミ集めを実行させた後（Ｓ５）、若い世代領域４２のゴミ集めを実行させる（Ｓ６）。一方、古い世代領域４３の空き量ＯＦに対して若い世代領域４２の予測生存量ＥＳが大きくなければ、ゴミ集め実行部２１に若い世代領域４２のゴミ集めを開始させる（Ｓ７）。
【００２５】
ここで、図１６を用いて、古い世代領域４３の空き量ＯＦと若い世代領域４２の予測生存量ＥＳとの大小関係の比較理由、及びこの比較結果でゴミ集めの実行対象領域が異なる理由について説明する。
【００２６】
記憶割当部１５からゴミ集め実行命令を受けて行うゴミ集めは、基本的に若い世代領域４２に属するオブジェクトのうち、システムから到達可能なオブジェクト、つまり生存中のオブジェクトを古い世代領域４３に移し、若い世代領域４２中にシステムが必要とするオブジェクトを残さないようにすることである。このため、若い世代領域４２の使用量ＹＵと予測生存率ＥＳＲとから、予測生存量ＥＳを求め、この予測生存量ＥＳ分のオブジェクトを古い世代領域４３の空き領域に移せるか否かを把握するために、古い世代領域４３の空き量ＯＦと若い世代領域４２の予測生存量ＥＳとの大小関係を比較する。
【００２７】
古い世代領域４３の空き量ＯＦに対して若い世代領域４２の予測生存量ＥＳが大きければ、若い世代領域４２の予測生存量ＥＳ分のオブジェクトを古い世代領域４３の空き領域に移せないので、まず、古い世代領域４３のゴミ集めを実行させ（Ｓ５）、その後、若い世代領域４２のゴミ集めを実行させる（Ｓ６）。一方、古い世代領域４３の空き量ＯＦに対して若い世代領域４２の予測生存量ＥＳが大きくなければ、若い世代領域４２の予測生存量ＥＳ分のオブジェクトを古い世代領域４３の空き領域に移せるので、若い世代領域４２のゴミ集めを開始させる（Ｓ７）。
【００２８】
若い世代領域４２のゴミ集めが開始されると、若い世代領域４２から古い世代領域４３にオブジェクトが移動してくる、つまり、若い世代のオブジェクトが古い世代領域４３に殿堂入りする。このため、メモリ監視部２２は、若い世代領域４２のゴミ集め実行中、古い世代領域４３の空き量が十分に確保されているか否かを確認する（Ｓ８）。メモリ監視部２２は、古い世代領域４３の空き量が十分に確保されなくなったことを検知すると、ゴミ集め制御部２３は、ゴミ集め実行部２１に若い世代領域４２のゴミ集めを一時中断させ（Ｓ９）、古い世代領域４３のゴミ集めを実行させる（Ｓ１０）。そして、この古い世代領域４３のゴミ集めが終了すると、若い世代領域４２のゴミ集めを再開させる（Ｓ１１）。
【００２９】
若い世代領域４２のゴミ集めが終了すると（Ｓ６，Ｓ１１，Ｓ１２）、ゴミ集め実行部２１は、若い世代領域４２から古い世代領域４３へ実際に移したオブジェクトの量、つまり若い世代領域４２のオブジェクトの生存量をＳとして、生存率予測部２５に渡す（Ｓ１３）。
【００３０】
生存率予測部２５は、この生存量Ｓを受け取ると、先のステップ２でメモリ監視部２２から受け取ったゴミ集め前の若い世代領域４２の使用量ＹＵとこの生存量Ｓとから、ゴミ集め直前における若い世代領域４２のオブジェクト生存率ＳＲ（＝Ｓ／ＹＵ）を求め、これを記憶しておく（Ｓ１４）。そして、今回求めたオブジェクト生存率ＳＲと、過去４回のゴミ集めで求めたオブジェクト生存率ＳＲとを統計処理して、次回のゴミ集め直前の若い世代領域４２の生存率ＥＳＲを予測する（Ｓ１５）。この予測生存率ＥＳＲは、次回のゴミ集め処理のステップ１で用いられる。
【００３１】
過去の生存率ＳＲから予測生存率ＥＳＲを求める方法としては、過去５回分の生存率ＳＲの平均値を予測生存率とする方法や、過去５回分の生存率ＳＲのうちの最大のものを予測生存率とする方法や、過去５回分の生存率の分布を正規分布とみなし、その８０％に相当する生存率を予測生存率とする方法等、各種方法が考えられる。なお、ここでは、合計で過去５回分の生存率から予測生存率を求めているが、例えば、過去１回分、つまり直前に行ったゴミ集めで取得した生存率に重み付けをして、これを予測生存率としてもよいし、また、２回〜４回分、さらには６回分以上の生存率から予測生存率を求めるようにしてもよい。
【００３２】
また、ここでは、説明の簡単のため、データメモリ４０のヒープ領域４１を若い世代領域４２と古い世代領域４３との二つに分けたが、さらに古い世代領域を設定し、つまり、ヒープ領域４１を３以上に分けてもよい。仮に、ヒープ領域４１を３つに分け、若い順に、第一世代領域、第二世代領域、第三世代領域とした場合、ゴミ集め処理部２０は、記憶割当部１５からゴミ集め実行命令を受けると、まず、第一世代領域の予測生存量を求め（Ｓ３）、この予測生存量と第二世代領域の空き量との大小関係を比較（Ｓ４）して、この比較結果に応じて第一世代領域か第二世代領域のゴミ集め（Ｓ８orＳ５）を行う。第二世代領域のゴミ集めを行うことになった場合には、第二世代領域の予測生存量を求め（Ｓ３）、この予測生存量と第三世代領域の空き量との大小関係を比較（Ｓ４）して、この比較結果に応じて第二世代領域か第三世代領域のゴミ集め（Ｓ８orＳ５）を行うことになる。
【００３３】
次に、オブジェクトのデータ構成について、図２を用いて説明する。
【００３４】
オブジェクトは、ヘッダ５０とペイロード５５とを有する。ヘッダ５０は、オブジェクトを処理系のシステムが管理するために必要なデータを格納する部分で、基本的にユーザプログラムから直接操作することはできない。それに対して、ペイロード５５は、ユーザプログラムが処理の実行に利用するためのデータを保存し、ユーザプログラムから直接操作できる。ヘッダ５０には、ルートから当該オブジェクトに到達可能であるか否かを示すマークが格納される到達可能性フィールド５１と、当該オブジェクトがコピー処理により実体移動が済んでいるか否かのマークが格納される移動済みフィールド５２と、当該オブジェクトの移動先のアドレスが格納される移動先フィールド５３と、当該オブジェクトのサイズが格納されるサイズフィールド５４とがある。到達可能性フィールド５１にマークが格納されているオブジェクトは、前述したように、ルートから到達可能なオブジェクトであり、ゴミ集めによって古い世代領域にコピーされるオブジェクトであるから、マークフェーズの終了後に到達可能性フィールド５１にマークが付されていないオブジェクトはゴミである。到達可能性フィールド５１に付されたマークは、ゴミ集め終了後に全て消去される。
【００３５】
到達可能性フィールド５１、移動済みフィールド５２、移動先フィールド５３等がヘッダ５０のどの部分にとられるかはシステムによる。これらのフィールドは、ゴミ集め実行中以外には利用しないので、通常使用時にのみ必要となる他のフィールドと兼用することも多い。例えば、移動先フィールド５３として32bit分の領域が確保されている場合、この移動先フィールド５３の下位2bitは常に0となるので、下位2bitの部分に到達可能性フィールドや移動済みフィールドを配置し、移動先を取得するときは下位2bitを0に戻して取得し、移動先を書き込むときは下位2bitの値はそのまま残して書き込むという方法を用いることもある。
【００３６】
ペイロード５５には、ポインタフィールド５６，５７，５９とデータフィールド５８とがある。ポインタフィールド５６，５７，５９には、当該オブジェクトと参照関係にある他のオブジェクトの先頭アドレスが格納される。ゴミ集めのときは、このポインタフィールド５８に格納されているアドレスのオブジェクトをたどることになる。データフィールド５８には、整数や、動小数点数などのポインタ以外の値が格納される。
【００３７】
ここで、以下の説明の都合上、ポインタｐがオブジェクトを指示する変数のとき、「オブジェクトP」は、「ポインタｐの示すオブジェクト」である。また、Xをオブジェクトのフィールドとすると、「PのX」は「オブジェクトPのフィールドX」を意味する。ポインタフィールドXに書き込まれている値のことを「Xの値」と呼ぶ。
【００３８】
次に、若い世代領域４２のゴミ集め処理（Ｓ６，７）の処理内容について説明する。
【００３９】
ゴミ集め処理の基本的方式としては、「背景技術」の欄で示した非特許文献１，２に記載されているように、マークスイープ方式、コピー方式、マークコンパクト方式等があるが、ここでは、コピー方式を採用する。なお、若い世代領域４２のゴミ集めの方式に、コピー方式以外の方式を採用してもよいことは言うまでもない。
【００４０】
若い世代のゴミ集め処理（Ｓ６，７）では、図４のフローチャートに示すように、ゴミ集め実行部２１が、まず、初期化処理（Ｓ１００）を行う。この初期化処理では、図１７（ａ）に示すように、大域変数のscan及びfreeを古い世代の空き領域ＯＦの先頭アドレスとする。若い世代領域４２をコピー方式でゴミ集めする場合、このコピー方式において、Fromに当たるものは、図１６に示すように、若い世代領域４２の使用中領域ＹＯであり、Toに当たるものが古い世代領域４３の空き領域ＯＦである。つまり、若い世代領域のゴミ集めを実行することで、若い世代領域４２の使用中領域ＹＯ中に生存するオブジェクトをすべて古い世代領域の空き領域ＯＦへ移動する。この処理に必要な大域変数が上述のscanとfreeである。
【００４１】
ゴミ集め実行部２１は、初期化処理（Ｓ１００）が終了するとルート処理（Ｓ２００）を行う。ルートとは、オブジェクトにアクセスするときの起点となる位置（アドレス）のことである。このルート値は、ＣＰＵのレジスタ等に記憶されている。このルート処理は、ルートが示すオブジェクトを古い世代領域４３にコピー処理することである。
【００４２】
ゴミ集め実行部２１は、ルート処理（Ｓ２００）が終了すると、スキャン処理（Ｓ３００）を行う。このスキャン処理は、前述のルート処理でコピーされたオブジェクトと参照関係にあるオブジェクトを古い世代領域４３にコピー処理することである。従って、前述のルート処理とこのスキャン処理で、ルートから到達可能な全てのオブジェクト、言い換えると、全ての生存中のオブジェクトを古い世代領域４３にコピーすることになる。
【００４３】
次に、図５に示すフローチャートに従って、前述のルート処理２００の詳細処理について説明する。このルート処理では、すべてのルートが示す各オブジェクトに対しコピー処理を行い、その結果で各ルートの値を書き換える。ゴミ処理実行部２１は、まず、未だ処理を行っていないルートがあるか調べる（Ｓ２０１）。この結果、未処理のルートがあった場合、未処理のルートを一つ取り出し、その値をRとし（Ｓ２０２）、このRを引数としてコピー処理を呼び出す（Ｓ２０３）。続いて、このコピー処理の戻り値にRを書き換える。その後、再び、ステップ２０１の判断処理に戻り、未処理のルートが無かった場合、ルート処理を終了する。
【００４４】
次に、先のルート処理２００のステップ２０３で呼び出されるコピー処理（Ｓ４００）について、図６のフローチャートに従って説明する。
【００４５】
ゴミ集め実行部２１は、まず、コピー処理の引数Ｒとして受け取った値を変数Pに代入する（Ｓ４０１）。そして、このＰを先頭アドレスとするオブジェクトの移動済みフィールド５２にマークが付されているか、つまり既にコピー処理が終了して当該オブジェクトが移動してしまったかを調べる（Ｓ４０２）。
【００４６】
Ｐを先頭アドレスとするオブジェクトの移動済みフィールド５２にマークが付されている場合には、Ｐを先頭アドレスとするオブジェクトの移動先フィールド５３に格納されている値をコピー処理の戻り値として返して（Ｓ４０８）、コピー処理を終了する。
【００４７】
また、Ｐを先頭アドレスとするオブジェクトの移動済みフィールド５２にマークが付されていない場合、変数addrに、初期化処理（Ｓ１００）で設定したfreeの値を代入し（Ｓ４０３）、Ｐを先頭アドレスとするオブジェクトをfreeが指すアドレスを先頭とする領域にコピーする（Ｓ４０４）。次に、freeの値をコピーしたオブジェクトのサイズ分だけ大きくする（Ｓ４０５）。この結果、freeは古い世代領域の未使用領域の先頭アドレスを指すようになる。つまり、freeはコピー処理により移動したオブジェクトの後尾アドレスを示す変数である。続いて、コピー元のオブジェクトの移動済みフィールド５２にマークをつけると共に、このコピー元のオブジェクトの移動先フィールド５３にaddrの値を書き込む。（Ｓ４０６）。そして、addrの値をコピー処理の戻り値として返し（Ｓ４０７）、コピー処理を終了する。
【００４８】
例えば、図１７（ａ）に示すように、ヒープ領域の若い世代領域４２にオブジェクトａ，ｂ，ｃが格納され、古い世代領域４３にオブジェクトｄ，ｅ，ｆが格納されており、ルートフィールド６１，６２に「1」「4」が格納されているとする。また、各オブジェクトａ，ｂ，〜，ｆの先頭アドレス、及び古い世代領域４３の空き領域の先頭アドレスをそれぞれ、１，２，３，４，５，６，７とする。そして、若い世代領域４２のゴミ集め処理の初期化処理（Ｓ１００）で、古い世代領域４３の空き領域の先頭アドレス「7」にscan及びfreeが設定されているとする。なお、ここでは、便宜上、ポインタフィールド５６が一つしかないが、図２を用いて説明したように、複数のポインタフィールドがあってもよい。また、ここでは、以下の説明を簡単にするために、オブジェクトのサイズを全て同一にしているが、各オブジェクト毎にサイズが異なっていてもよい。
【００４９】
前述のルート処理２００のステップ２０２で、ルートフィールド６１，６２からルート「１」が抽出され、これが引数Ｒになり、この引数Ｒ（＝1）でコピー処理が呼び出された場合、コピー処理４００のステップ４０１では引数Ｒ（＝１）が変数Ｐに代入され、ステップ４０２ではこの変数Ｐ（＝１）を先頭アドレスとするオブジェクトａの移動済みフィールド５２にマークが付されているか否かが調べられる。この場合、オブジェクトａの移動済みフィールド５２にマークが付されていないので、ステップ４０３に進んで、変数addrにfreeの値（＝７）を代入され（Ｓ４０３）、図１７（ｂ）に示すように、Ｐ（＝１）を先頭アドレスとするオブジェクトａをfreeが指すアドレス「７」を先頭とする領域にコピーされる（Ｓ４０４）。次に、freeの値がコピーしたオブジェクトのサイズ分だけ大きくされる（Ｓ４０５）。そして、コピー元のオブジェクトａの移動済みフィールド５２にマークを付けられると共に、このコピー元のオブジェクトａの移動先フィールド５３にaddr（＝７）の値が書き込まれ、さらに、ルートフィールド６１のルート値「1」がオブジェクトａのコピー先のアドレスである「7」に書き換えられる（Ｓ４０６）。そして、addr（＝７）の値がコピー処理の戻り値として返されて（Ｓ４０７）、コピー処理が終了する。
【００５０】
次に、図７に示すフローチャートに従って、スキャン処理（Ｓ３００）の詳細処理について説明する。
【００５１】
このスキャン処理（Ｓ３００）では、全てのコピー先オブジェクトのポインタフィールドに格納されているポインタに対し、図６を用いて前述したコピー処理（Ｓ４００）が順に実行され、コピー処理の戻り値でポインタ値が更新される。具体的には、ゴミ集め実行部２１は、まず、scanの示すアドレスがfreeの示すアドレス値より小さいかを調べる（Ｓ３０１）。小さい場合は、scanの指すアドレスを先頭アドレスとするオブジェクト内にまだ処理の行われていないポインタフィールドが存在するかを調べる（Ｓ３０２）。未処理のポインタフィールドが見つかった場合、この未処理のポインタフィールドの値ｐを一つ取り出し（Ｓ３０３）、このｐの値を引数として、図６に示すコピー処理（Ｓ４００）を呼び出す（Ｓ３０４）。つまり、このスキャン処理（３００）でのコピー処理（S４００）では、ルート処理（Ｓ２００）で古い世代領域にコピーされたオブジェクトのポインタフィールドを調べ、このポインタフィールドに格納されたポインタ値を先頭アドレスとするオブジェクトをfreeの示すアドレスのところにコピー処理する。コピー処理が終了すると、このコピー処理の戻り値をｐの値として書き込む（Ｓ３０５）。そして、ステップ３０２の判断処理に戻る。
【００５２】
このステップ３０２で、未処理のポインタフィールドがないと判断した場合、scanの値にscanの指すオブジェクトのサイズを加えた値を、scanの示す新たなアドレスとする。つまり、scanの指すアドレスを次のオブジェクトの先頭アドレスにする（Ｓ３０６）。従って、この変数scanは、スキャン処理が終了した箇所のアドレスを示す変数と言える。この処理（Ｓ３０６）が終了すると、再び、ステップ３０１に戻り、scanの示すアドレスがfreeの示すアドレス値より小さいかを調べ、scanの示すアドレスがfreeの示すアドレス値より小さくないと判断すると、スキャン処理を終了する。
【００５３】
前述のルート処理（Ｓ２００）に続く、このスキャン処理（Ｓ３００）で、若い世代のゴミ集めが終了する。
【００５４】
ここで、具体的なスキャン処理（Ｓ３００）の例について、図１８（ｇ）（ｈ）を用いて説明する。
【００５５】
図１８（ｇ）は、後に詳細に説明するが、図３のフローチャート中で、若い世代のゴミ集めを開始し（Ｓ７）、スキャン処理過程の途中で古い世代領域の空きが無くなったために（Ｓ８）、若い世代のゴミ集めを中断し（Ｓ９）、古い世代のゴミ集め（Ｓ１０）が終了した段階のヒープ領域を示している。古い世代のゴミ集め（Ｓ１０）が終了すると、若い世代のゴミ集めが再開される（Ｓ１１）。この場合、途中で中断したスキャン処理が再開される。このスキャン処理が再開される段階で、scanの示すアドレス、freeの示すアドは、図１８（ｇ）に示すように、それぞれ、「6」「7」である。
【００５６】
このスキャン処理（Ｓ３００）では、ゴミ集め実行部２１は、まず、scanの示すアドレス（＝6）がfreeの示すアドレス（＝7）より小さいかを調べる（Ｓ３０１）。この場合、scanの方が小さいので、scanの指すアドレスを先頭アドレスとするオブジェクトａにまだ処理の行われていないポインタフィールド５６が存在するかを調べる（Ｓ３０２）。この場合、未処理のポインタフィールド５６があるので、この未処理のポインタフィールド５６の値（＝3）を取り出し（Ｓ３０３）、この値を引数として、コピー処理（Ｓ４００）を呼び出す（Ｓ３０４）。このコピー処理（Ｓ４００）では、引数（＝3）を先頭アドレスとするオブジェクトｃがfree（＝7）の位置にコピーされ（Ｓ４０４）、freeの示すアドレスが「8」に換えられ（Ｓ４０５）、移動元にあるオブジェクトｃの移動済みフィールドにマークが付けられると共に、移動先フィールドに移動先のアドレスの値（＝7）が書き込まれる（Ｓ４０６）。コピー処理（Ｓ４００）が終了すると、再び、ステップ３０２に戻り、ここでは、scanの指すアドレスを先頭アドレスとするオブジェクトａにまだ処理の行われていないポインタフィールド５６が存在しないと判断される。
【００５７】
そして、scanの値が新たな値（＝7）に更新され（Ｓ３０６）、ステップ３０１に戻り、ここで、scanの示すアドレス（＝7）がfreeの示すアドレス（＝7）より小さくないと判断され、スキャン処理が終了する。この結果、若い世代のゴミ集めが終了する。
【００５８】
次に、古い世代のゴミ集め処理（Ｓ５，１０）について、図８に示すフローチャートに従って説明する。
【００５９】
この古い世代のゴミ集めでは、「背景技術」の欄で示した非特許文献１，２に記載されているLisp2方式のアルゴリズムを用いたマークコンパクト方式を採用する。なお、古い世代のゴミ集めの方式に、マークコンパクト方式以外の方式を採用してもよいことは言うまでもない。
【００６０】
古い世代のゴミ集め処理（Ｓ５，１０）では、ゴミ集め実行部２１が、まず、マーク処理（Ｓ５００）を行う。このマーク処理では、古い世代領域に存在するオブジェクトで、ルートから到達可能な全てのオブジェクの到達可能性フィールドにマークを付ける。このとき、若い世代領域に存在するオブジェクトのポインタもルートとみなして処理を行う。
【００６１】
具体的なマーク処理の例について、図１７（ｂ）（ｃ）を用いて説明する。
【００６２】
図１７（ｂ）は、前述したように、若い世代のゴミ集めにおけるルート処理が終了した段階のヒープ領域を示している。ルート処理が終了すると、前述したように、このルート処理で移動したオブジェクトａをスキャンして、このオブジェクトａのポインタフィールドに格納されたポインタ値を先頭アドレスとするオブジェクトをfreeの示すアドレスのところにコピー処理しようとする。しかしながら、この場合、古い世代領域には空きがないため、図３に示すフローチャートにおいて、若い世代のゴミ集め中（Ｓ７）に、古い世代領域の空きがなく無くなったと判断され（Ｓ８）、この若い世代のゴミ集めが中断されて（Ｓ９）、古い世代のゴミ集めが開始される（Ｓ１０）。この古い世代のゴミ集め（Ｓ１０）のマーク処理（Ｓ５００）では、前述したように、古い世代領域に存在するオブジェクトで、ルートから到達可能な全てのオブジェクの到達可能性フィールドにマークが付けられる。この場合、ルートフィールド６１，６２には、ルート値として「7」「4」が格納されているので、「7」を先頭アドレスとする移動後のオブジェクトa、「4」を先頭アドレスとするオブジェクトｄのそれぞれの到達可能性フィールド５１にマークが付される。さらに、マークが付されたオブジェクトaのポインタフィールド５６に格納されている「3」を先頭アドレスとするオブジェクトｃ、マークが付されたオブジェクトｄのポインタフィールド５６に格納されている「6」を先頭アドレスとするオブジェクトｆのそれぞれの到達可能性フィールド５１にマークが付される。
【００６３】
再び、図８のフローチャートの説明に戻る。
【００６４】
ゴミ集め実行部２１は、マーク処理（Ｓ５００）が終了すると、古い世代領域に存在する全ての生存中のオブジェクトの移動先を決定し（S６００）、メモリ内容の修正を行う（Ｓ７００）。このメモリ内容修正処理は、各オブジェクトの移動に伴うオブジェクトのヘッダの内容を修正する処理である。ゴミ集め実行部２１は、その後、移動先決定処理（Ｓ６００）で決定した移動先に、古い世代領域に存在する生存中のオブジェクトを移動させて（Ｓ８００）、古い世代のゴミ集めを終了する。なお、ステップ８００でのオブジェクト移動処理での「移動」は、前述のコピー処理での移動のように移動元にオブジェクトが残る場合を含まない狭義の意味での移動である。
【００６５】
次に、図９に示すフローチャートに従って、移動先決定処理（Ｓ６００）について説明する。
【００６６】
この移動先決定処理（Ｓ６００）では、前述したように、古い世代領域に存在する全ての生存中のオブジェクトの移動先のアドレスが決定され、さらに、当該オブジェクトの移動先フィールドに決定した移動先のアドレスが書き込まれる。具体的に、ゴミ集め実行部２１は、まず、freeとＰを古い世代領域の先頭アドレスを指すように設定する（Ｓ６０１）。Ｐは現在移動先決定処理の対象となっているオブジェクトを指し、freeはオブジェクトを移動する場合の移動先を指す。続いて、Ｐが古い世代領域の使用中領域の後尾アドレス未満であるかを調べる（Ｓ６０２）。Ｐが古い世代領域の使用中領域の後尾アドレス未満である場合、Ｐを先頭アドレスとするオブジェクトの到達可能性フィールドにマークが付いているか否かを調べる（Ｓ６０３）。マークが付いている場合は、このオブジェクトは生存していることを意味するので、このオブジェクトの移動先フィールドにfreeの値を書き込み、freeの値にこのオブジェクトのサイズの値を加え、これを新しいfreeの値とし（Ｓ６０４）、ステップ６０５に進む。一方、ステップ６０３の判断でマークが付いていないと判断した場合には、このオブジェクトは生存していないことを意味するので、移動対象にはならず、直ちに、ステップ６０５に進む。ステップ６０５では、Ｐの値に、Ｐの値を先頭アドレスとするオブジェクトのサイズを加えて、これを新しいＰの値とする（Ｓ６０４）。次に、再び、ステップ６０２の判断処理に戻り、Ｐが古い世代領域の使用中領域の後尾アドレス以下でないと判断すると、移動先決定処理が終了する。なお、以上では説明していないが、次のフェーズ以降の処理を早くするために、到達可能性フィールドにマークが付いていないオブジェクトが連続する場合、それらをまとめて一つのオブジェクトとみなす処理を行うことも可能である。
【００６７】
具体的な移動先決定処理（Ｓ６００）の例について、図１７（ｃ）（ｄ）を用いて説明する。
【００６８】
図１７（ｃ）は、前述したように、古い世代のゴミ集めにおけるマーク処理（Ｓ５００）が終了した段階のヒープ領域を示している。このマーク処理が終了すると、移動先決定処理（Ｓ６００）が開始され、freeとＰが共に古い世代領域４３の先頭アドレス（＝4）を指すように設定される（Ｓ６０１）。Ｐが古い世代領域４３の使用中領域の後尾アドレス未満であれば（Ｓ６０２）、Ｐ（＝4）を先頭アドレスとするオブジェクトｄの到達可能性フィールド５１にマークが付いているか否かを調べる（Ｓ６０３）。この場合、オブジェクトｄの到達可能性フィールド５１にマークが付いているが、古い世代領域４３の先頭に格納されているので、移動対象とはしない。そして、freeの値にこのオブジェクトｄのサイズの値を加え、これを新しいfree（＝5）の値とし（Ｓ６０４）、Ｐの値に、Ｐの値を先頭アドレスとするオブジェクトｄのサイズを加えて、これを新しいＰ（＝5）の値とする（Ｓ６０４）。つまり、free及Ｐがそれぞれアドレス５を指すように設定する。再び、ステップ６０２に戻ってからステップ６０３に進み、ここで、Ｐ（＝5）を先頭アドレスとするオブジェクトｅの到達可能性フィールド５１にマークが付いているか否かを調べる。このオブジェクトｅの到達可能性フィールド５１にはマークが付いておらず、このオブジェクトｅが生存していないことを意味するので、移動対象にはならないで、直ちに、ステップ６０５に進む。ステップ６０５では、Ｐの値に、Ｐの値を先頭アドレスとするオブジェクトｅのサイズを加えて、これを新しいＰの値（＝6）とする。
【００６９】
その後、再び、ステップ６０２に戻ってからステップ６０３に進み、ここで、Ｐ（＝6）を先頭アドレスとするオブジェクトｆの到達可能性フィールド５１にマークが付いているか否かを調べる。このオブジェクトｆの到達可能性フィールド５１にはマークが付いているので、このオブジェクトｆの移動先フィールド５３の値をfreeの値（＝5）にした後、freeの値を6に更新する（Ｓ６０４）。そして、Ｐの値を７に更新した後（Ｓ６０５）、再び、ステップ６０２に戻ってからステップ６０３に進む。この場合も、Ｐ（＝7）を先頭アドレスとするオブジェクトａの到達可能性フィールド５１にマークが付いているか否かを調べる。このオブジェクトａの到達可能性フィールド５１にもマークが付いているので、このオブジェクトａの移動先フィールド５３の値をfreeの値（＝6）にした後、freeの値を7に更新する（Ｓ６０４）。そして、Ｐの値を8に更新した後（Ｓ６０５）、再び、ステップ６０２に戻る。このステップ６０２では、Ｐの値（＝8）が古い世代領域４３の使用中の後尾アドレス（＝8）になっているので、移動先決定処理を終了する。すなわち、ここでは、オブジェクトｆの移動先をアドレス５に決定し、オブジェクトａの移動先をアドレス６に決定する。
【００７０】
次に、図１０に示すフローチャートに従って、メモリ内容修正処理（Ｓ７００）について説明する。
【００７１】
ゴミ集め実行部２１は、メモリ内容修正処理として、まず、若い世代のメモリ内容修正処理（Ｓ７１０）を行い、その後、ルートフィールドのメモリ内容修正処理（Ｓ７４０）、古い世代のメモリ内容修正処理1（Ｓ７５０）を順に行う。
【００７２】
次に、図１１に示すフローチャートに従って、若い世代のメモリ内容修正処理（Ｓ７１０）の詳細について説明する。
【００７３】
若い世代のメモリ内容修正処理（Ｓ７１０）では、若い世代のすべてのオブジェクトに対し、移動済みフィールドにマークが付いていない場合には、オブジェクト内のポインタフィールドの値を、ポインタの指すオブジェクトの移動先フィールドの値に修正する。移動済みフィールドにマークが付いている場合は、オブジェクトの移動先フィールドをその移動先が指すオブジェクトの実体の移動先フィールドの値に更新し、オブジェクトの到達可能性フィールドにマークを付ける。若い世代のオブジェクトの到達可能性フィールドのマークは、オブジェクトの移動先フィールドが実体の移動先で既に更新されていることを表す。オブジェクトの移動済みフィールドにマークが付いているのは、若い世代領域の中断中（図３中のＳ９）だけなので、図３中のＳ１０で古い世代領域のゴミ集め処理が呼び出されたときだけである。
【００７４】
ゴミ集め実行部２１は、この若い世代のメモリ内容修正処理で（Ｓ７１０）、まず、若い世代領域の先頭アドレスをＳに代入する（Ｓ７１１）。Ｓは、現在メモリ内容修正中のオブジェクトを指すポインタである。次に、Ｓの示すアドレスが若い世代領域の使用中領域の後尾アドレス未満であるかを調べる（Ｓ７１２）。Ｓの示すアドレスが若い世代領域の使用中領域の後尾アドレス未満である場合には、Ｓの示すアドレスを先頭アドレスとするオブジェクトの移動済みフィールドにマークが付いているか否かを調べる（Ｓ７１３）。マークが付いている場合、ステップ７１４又はステップ７１８に進む。ステップ７１４からステップ７１７までの処理は、若い世代領域のゴミ集めを中断したとき（図３中のＳ９）のみに実行し、若い世代領域のゴミ集めを中断してない場合には、直ちに、ステップ７１８に進む。ステップ７１４では、Ｓの示すアドレスを先頭アドレスとするオブジェクトの移動先フィールドに格納されている値をQとする。次に、このQを引数として後述の移動先取得処理（Ｓ７３０）を呼び出し（Ｓ７１５）、移動先取得処理の戻り値をQとする、つまり移動先フィールドに戻り値Qを書き込む（Ｓ７１６）。移動先取得処理の戻り値は、Sの示すアドレスを先頭アドレスとするオブジェクトの実体の移動先である。次に、Sの示すアドレスを先頭アドレスとするオブジェクトの到達可能性フィールドにマークを付ける（Ｓ７１７）。ここでマークを付けるのは、当該オブジェクトの移動先フィールドの値が実体の移動先となったことを区別するためである。
【００７５】
到達可能性フィールドにマークを付けると（Ｓ７１７）、Sの値に、Sの示すアドレスを先頭アドレスとするオブジェクトのサイズを加え、これを新しいSの値とする（Ｓ７１８）。これは、処理するオブジェクトを次のオブジェクトに進める処理である。この処理が終わると、ステップ７１２の判断処理に戻る。このステップ７１２で、Sの示すアドレスが若い世代領域の使用中領域の後尾アドレス未満ではないと判断すると、若い世代のメモリ内容修正処理を終了する。
【００７６】
ステップ７１３で、Sの示すアドレスを先頭アドレスとするオブジェクトの移動済みフィールドにマークが付いていないと判断した場合には、このオブジェクトに未処理のポインタフィールドが存在するか否かを調べる（Ｓ７１９）。未処理のポインタフィールドが無い場合には、前述のステップ７１８に進む。また、未処理のポインタフィールドが存在する場合には、この未処理のポインタフィールドの値を取出し（Ｓ７２０）、このポインタフィールドの値ｐを引数として、後述の移動先取得処理を呼び出した後（Ｓ７２１）、この移動先取得処理の戻り値をポインタフィールドに書き込み（Ｓ７２２）、ステップ７１９に戻る。
【００７７】
次に、移動先取得処理（Ｓ７３０）について、図１２に示すフローチャートに従って説明する。
【００７８】
この移動先取得処理（Ｓ７３０）は、図１１中のステップ７１５及びステップ７２１の処理で呼び出される。移動先取得処理では、引数の指すオブジェクトをコンパクション処理で移動するなら移動先フィールドの値を返し、そうでないなら引数をそのまま返す。ただし、オブジェクトに移動済みフィールドにマークが付いている場合は、若い世代のゴミ集めにより、このオブジェクトの実体がすでに別の場所に移動されているので、このオブジェクトの移動先フィールドの値で示されているオブジェクトの移動先フィールドの値を返す。また、オブジェクトの移動済みフィールドと到達可能性フィールドの両方にマークが付いている場合は、このオブジェクトの移動先はすでに実体の移動先に書き換えられているので、その値を返す。
【００７９】
ゴミ集め実行部２１は、この移動先取得処理で（Ｓ７３０）、まず、Pに引数を代入する（Ｓ７３１）。次に、このＰを先頭アドレスとするオブジェクトの到達可能性フィールドにマークが付いているか否かを調べる（Ｓ７３２）。マークが付いている場合は、このオブジェクトの移動先フィールドの値を戻り値とし（Ｓ７３３）、処理を終了する。また、マークが付いていない場合、このオブジェクトの移動先フィールドにマークが付いているか否かを調べる（Ｓ７３４）。マークが付いていない場合、Ｐの値を戻り値とし（Ｓ７３７）、処理を終了する。つまり、この場合は、引数として与えられた値がそのまま戻り値になる。また、マークが付いている場合、このオブジェクトの移動先フィールドの値を引数として、この処理自身を呼び出し（Ｓ７３５）、呼び出した処理からの戻り値を、この移動先取得処理での戻り値とし（Ｓ７３６）、処理を終了する。
【００８０】
具体的な若い世代のメモリ内容修正処理（Ｓ７１０）及びこの処理で実行される移動先取得処理（Ｓ７３０）の例について、図１７（ｄ）、図１８（ｅ）を用いて説明する。
【００８１】
図１７（ｄ）は、前述したように、移動先決定処理（Ｓ６００）が終了した段階のヒープ領域を示している。この移動先決定処理が終了すると、若い世代のメモリ修正処理（Ｓ７１０）が開始され、若い世代領域４２の先頭アドレスをS（＝1）に代入する（Ｓ７１１）。次に、S（＝1）の示すアドレスが若い世代領域４２の使用中領域の後尾アドレス未満であるかを調べる（Ｓ７１２）。この場合、Sの示すアドレスが若い世代領域の使用中領域の後尾アドレス未満であるので、Sの示すアドレスを先頭アドレスとするオブジェクトａの移動済みフィールド５２にマークが付いているか否かを調べる（Ｓ７１３）。この場合、マークが付いているので、Sの示すアドレスを先頭アドレスとするオブジェクトａの移動先フィールドに格納されている値をQ（＝7）に代入する（Ｓ７１４）。次に、このQを引数として移動先取得処理（Ｓ７３０）を呼び出す（Ｓ７１５）。
【００８２】
呼び出された移動先取得処理（Ｓ７３０）では、まず、Pに引数Q（＝7）を代入する（Ｓ７３１）。次に、このＰ（＝7）を先頭アドレスとするオブジェクトaの到達可能性フィールド５１にマークが付いているか否かを調べる（Ｓ７３２）。この場合、マークが付いているので、このオブジェクトaの移動先フィールドの値（＝6)を戻り値とし（Ｓ７５３）、移動先取得処理を終了する。
【００８３】
ステップ７１５での移動先取得処理の呼び出し後、この移動先取得処理から戻り値（＝6)をQとする、つまり、図１８（ｅ）に示すように、戻り値（＝6)をオブジェクトａの移動先フィールド５３に書き込む（Ｓ７１６）。次に、S（＝１）のアドレスを先頭アドレスとするオブジェクトaの到達可能性フィールド５１にマークを付ける（Ｓ７１７）。そして、Sの値（＝１）に、Sのアドレスを先頭アドレスとするオブジェクトaのサイズを加え、これを新しいSの値（＝2）とし（Ｓ７１８）、つまり、メモリ内容の修正処理の対象をＳの値を先頭アドレスとするオブジェクトｂにして、ステップ７１２の判断処理に戻る。そして、ステップ７１３，７１９を経て、ステップ７１８で、Ｓの値を新しい値（＝3）に更新して、再び、ステップ７１２に戻る。
【００８４】
再び戻ったステップ７１２を経て、ステップ７１３に至ると、ここでは、S（＝3）の示すアドレスを先頭アドレスとするオブジェクトｃの移動済みフィールド５３にマークが付いていないので、ステップ７１９，７２０に進む。そして、ステップ７２０で、S（＝3）のアドレスを先頭アドレスとするオブジェクトｃのポインタフィールド５６の値ｐ（＝1）を取出し、ｐの値（＝1）を引数として、移動先取得処理（Ｓ７３０）を呼び出す（Ｓ７２１）。
【００８５】
呼び出された移動先取得処理（Ｓ７３０）では、まず、Pに引数ｐ（＝1）を代入する（Ｓ７３１）。次に、このＰ（＝1）を先頭アドレスとするオブジェクトaの到達可能性フィールド５１にマークが付いているか否かを調べる（Ｓ７３２）。この場合、マークが付いているので、このオブジェクトaの移動先フィールドの値（＝6)を戻り値とし（Ｓ７５３）、移動先取得処理を終了する。
【００８６】
ステップ７２１での移動先取得処理の呼び出し後、この移動先取得処理から戻り値（＝6)をQとする、つまり、図１８（ｅ）に示すように、戻り値（＝6)をオブジェクトｃの移動先フィールド５３に書き込む（Ｓ７１６）。次に、S（＝3）のアドレスを先頭アドレスとするオブジェクトｃの到達可能性フィールド５１にマークを付ける（Ｓ７１７）。なお、オブジェクトｃの到達可能性フィールド５１には既にマークが付いているのでマークを上書きすることになる。そして、Sの値（＝3）を新しいSの値（＝4）とし（Ｓ７１８）、再び、ステップ７１２に戻る。
【００８７】
このステップ７１２では、Ｓの値（＝４）が若い世代領域４２の使用中領域の後尾アドレスであるので、Ｓの値（＝４）が若い世代領域４２の使用中領域の後尾アドレス未満ではないと判断して、若い世代のメモリ内容修正処理を終了する。
【００８８】
次に、図１３に示すフローチャートに従って、ルートのメモリ内容修正処理（Ｓ７４０）について説明する。
【００８９】
このメモリ内容修正処理（Ｓ７４０）では、全てのルートに対し、その内容を順に修正していく。ゴミ集め実行部２１は、まず、未処理のルートが残っているかを調べる（Ｓ７４１）。残っていない場合は処理を終了する。残っていた場合は、未処理のルートを一つ取り出し、このルート値をRとする（Ｓ７４２）。次に、Rを引数として前述の移動先取得処理（Ｓ７３０）を呼び出す（Ｓ７４３）。そして、移動先取得処理からの戻り値をRに代入し、つまり、ルートフィールドに書き込んで（Ｓ７４４）、ステップ７４１に戻る。ルートのメモリ修正処理において大域変数のscanもルートとして扱う。一方、freeはルートとして扱わない。
【００９０】
次に、図１４に示すフローチャートに従って、古い世代のメモリ内容修正処理（Ｓ７５０）について説明する。
【００９１】
この古い世代のメモリ内容修正処理（Ｓ７５０）では、古い世代の各オブジェクトに対し、ポインタフィールドの値をポインタの指すオブジェクトの移動先に修正する。ゴミ集め実行部２１は、まず、古い世代領域の先頭アドレスをPに代入する（Ｓ７５１）。このPは現在、メモリ内容修正中のオブジェクトを指すポインタである。次に、Pが古い世代の使用中領域の後尾アドレス未満であるかを調べる（Ｓ７５２）。Pが古い世代の使用中領域の後尾アドレス未満でない場合、古い世代領域の全てのオブジェクトに対しメモリ内容修正が終了したことになるので、古い世代領域のメモリ内容修正処理を終了する。一方、Pが古い世代の使用中領域の後尾アドレス未満の場合、Pを先頭アドレスとするオブジェクトの到達可能性フィールドにマークが付いているかを調べる（Ｓ７５３）。マークが付いている場合は、Pの指すオブジェクトに未処理のポインタがあるかを調べる（Ｓ７５４）。未処理のポインタがある場合、Pの指すオブジェクトの未処理のポインタフィールドの値を一つ取り出しそれをQとする（Ｓ７５５）。そして、Qの値を引数として、前述の移動先取得処理（Ｓ７３０）を呼び（Ｓ７５６）、この移動先取得処理からの戻り値にQの値を更新する。つまり、Pの指すオブジェクトのポインタフィールドに戻り値を書き込み（Ｓ７５７）、ステップ７５４に戻る。ステップ７５３で、Pを先頭アドレスとするオブジェクトの到達可能性フィールドにマークが付いていないと判断した場合、及びステップ７５４で、Pの指すオブジェクトに未処理のポインタがない場合には、Pの指すオブジェクトに、このオブジェクトのサイズを加えて、この値を新しいPの値とし（Ｓ７５８）、ステップ７５２に戻る。
【００９２】
以上の若い世代のメモリ内容修正処理（Ｓ７１０）、ルートのメモリ内容修正処理（Ｓ７４０）、古い世代のメモリ内容修正処理（Ｓ７５０）で、メモリ内容修正処理（Ｓ７００）が終了する。
【００９３】
ここで、具体的なルートのメモリ内容修正処理（Ｓ７４０）及び古い世代のメモリ内容修正処理（Ｓ７５０）の例について、図１８（ｅ）及び同図（ｆ）を用いて説明する。
【００９４】
図１８（ｅ）は、前述したように、若い世代のメモリ内容修正処理（Ｓ７１０）が終了した段階のヒープ領域を示している。この若い世代のメモリ内容修正処理が終了すると、ルートのメモリ修正処理（Ｓ７４０）が開始される。このルートのメモリ内容修正処理では、未処理のルート、この場合、ルートフィールド６１の値（＝７）を取り出し、この値をＲに設定する（Ｓ７４１，７４２）。次に、このR（＝7）を引数として移動先取得処理（Ｓ７３０）を呼び出す（Ｓ７４３）。
【００９５】
呼び出された移動先取得処理（Ｓ７３０）では、まず、Pに引数ｐ（＝７）を代入する（Ｓ７３１）。次に、このＰ（＝7）を先頭アドレスとするオブジェクトaの到達可能性フィールド５１にマークが付いているか否かを調べる（Ｓ７３２）。この場合、マークが付いているので、このオブジェクトaの移動先フィールドの値（＝6)を戻り値として（Ｓ７５３）、移動先取得処理を終了する。
【００９６】
ステップ７４３での移動先取得処理の呼び出し後、この移動先取得処理から戻り値（＝6)をRとする、つまり、図１８（ｆ）に示すように、ルートフィールド６１の値を戻り値（＝6)に更新する（Ｓ７４４）。なお、このルートのメモリ内容修正処理では、scanやfreeもルートとして扱い、ルートと同様の処理を行う。このため、scanはアドレス「6」を指し、freeはアドレス「7」を指すようになる。以上で、ルートのメモリ内容修正処理が終了する。
【００９７】
続いて、古い世代のメモリ内容修正処理（Ｓ７５０）が開始される。古い世代のメモリ内容修正処理では、まず、古い世代領域の先頭アドレス（＝4）をPに代入する（Ｓ７５１）。次に、Pが古い世代の使用中領域の後尾アドレス未満であると（Ｓ７５２）、P（＝4）を先頭アドレスとするオブジェクトｄの到達可能性フィールド５１にマークが付いているかを調べる（Ｓ７５３）。この場合、マークが付いているので、更に、このオブジェクトｄに未処理のポインタがあるかを調べる（Ｓ７５４）。この場合、未処理のポインタがあるので、このオブジェクトｃの未処理のポインタフィールドの値（＝6）を取り出しそれをQとする（Ｓ７５５）。そして、Qの値を引数（＝6）として、移動先取得処理（Ｓ７３０）を呼び出す（Ｓ７５６）。
【００９８】
呼び出された移動先取得処理（Ｓ７３０）では、まず、Pに引数ｐ（＝6）を代入する（Ｓ７３１）。次に、このＰ（＝6）を先頭アドレスとするオブジェクトｆの到達可能性フィールド５１にマークが付いているか否かを調べる（Ｓ７３２）。この場合、マークが付いているので、このオブジェクトｆの移動先フィールドの値（＝5)を戻り値として（Ｓ７５３）、移動先取得処理を終了する。
【００９９】
ステップ７５６での移動先取得処理の呼び出し後、この移動先取得処理から戻り値（＝5)をＱとする、つまり、図１８（ｆ）に示すように、ポインタフィールド５６の値を戻り値（＝5)に更新し（Ｓ７５７）、ステップ７５４に戻る。その後、ステップ７５８を経て、ステップ７５２に戻る。以降、残りのオブジェクトｅ，ｆ，ａに対しても、ステップ７５２〜７５８の処理が繰り返されるが、オブジェクトｅ，ｆ，ａのポインタフィールド５６の変更は行われない。
【０１００】
次に、図１５に示すフローチャートに従って、オブジェクト移動処理（Ｓ８００）について説明する。
【０１０１】
このオブジェクト移動処理は、先の移動先決定処理（Ｓ６００）で決めた移動先のアドレスに、オブジェクトを実際に移動する処理である。
【０１０２】
ゴミ集め実行部２１は、このオブジェクト移動処理（Ｓ８００）で、まず、古い世代領域の先頭アドレスをPに代入する（Ｓ801）。このPは移動処理の対象となるオブジェクトを指す。次に、アドレスPが古い世代領域の使用中領域の後尾アドレス未満かを調べる（Ｓ８０２）。アドレスPが古い世代領域の使用中領域の後尾アドレス未満の場合、Pを先頭アドレスとするオブジェクトの到達可能性フィールドにマークがあるか、さらに、このオブジェクトの移動先フィールドに値が格納されているかを調べる（Ｓ８０３）。このオブジェクトの到達可能性フィールドにマークがあり、さらに、このオブジェクトの移動先フィールドに値が格納されている場合には、このオブジェトが移動候補であるとして、freeをこのオブジェクトの移動先フィールドの値に換えると共に、このオブジェクトの到達可能性フィールドのマークと移動先フィールドの値を消去する（Ｓ８０４）。続いて、このオブジェクトをfreeの位置に移動する（Ｓ８０５）。なお、このオブジェクト移動処理での「移動」は、前述したように、コピー処理のように移動元にオブジェクトが残る移動ではない。但し、本願において、特にことわりがない限り、「移動」とは、コピー処理のように移動元にオブジェクトが残る移動も、このオブジェクト移動処理の際の移動のように移動元にオブジェクトが残らない移動も含まれる。そして、ＰにＰのサイズを加えることで、処理対象となるオブジェクトを次のオブジェクトに進めて（Ｓ８０６）、ステップ８０２に戻る。また、ステップ８０３で、Pを先頭アドレスとするオブジェクトの到達可能性フィールにマークがない、又は、このオブジェクトの移動先フィールドに値が格納されていないと判断した場合にも、同様に、ＰにＰのサイズを加えてから（Ｓ８０６）、ステップ８０２に戻る。
【０１０３】
ステップ８０２で、アドレスPが古い世代領域の使用中領域の後尾アドレス未満ではないと判断すると、ＰにＰのサイズを加えて（Ｓ８０7）、オブジェクト移動処理を終了する。
【０１０４】
以上のマーク処理（Ｓ５００）、移動先決定処理（Ｓ６００）、メモリ内容修正処理（Ｓ７００）、オブジェクト移動処理（Ｓ８００）で、古い世代のゴミ集めが終了する。
【０１０５】
ここで、具体的なオブジェクト移動処理（Ｓ８００）の例について、図１８（ｆ）及び同図（ｇ）を用いて説明する。
【０１０６】
図１８（ｆ）は、前述したように、メモリ内容修正処理（Ｓ７００）が終了した段階のヒープ領域を示している。このメモリ内容修正処理が終了すると、オブジェクト移動処理（Ｓ８００）が開始される。ゴミ集め実行部２１は、まず、古い世代領域４３の先頭アドレスをPに代入する（Ｓ801）。次に、アドレスP（＝4）が古い世代領域４３の使用中領域の後尾アドレス未満かを調べる（Ｓ８０２）。アドレスPが古い世代領域の使用中領域の後尾アドレス未満の場合、P（＝4）を先頭アドレスとするオブジェクトｄの到達可能性フィールド５１にマークがあるか、さらに、このオブジェクトｄの移動先フィールド５３に値が格納されているかを調べる（Ｓ８０３）。このオブジェクトｄの移動先フィールド５３には値が格納されていないので、ＰにＰのサイズを加えてから（Ｓ８０６）、ステップ８０２に戻る。
【０１０７】
同様に、Ｐ（＝5）を先頭アドレスとするオブジェクトｅに対しても、ステップ８０３〜ステップ８０６を実行し、対象とするオブジェクトをオブジェクトｆに変える。このオブジェクトｆは、その到達可能性フィールド５１にマークがあり、さらに、このオブジェクトｆの移動先フィールド５３に値が格納されているので（Ｓ８０３）、このオブジェトｆが移動候補であるとして、freeをこのオブジェクトｆの移動先フィールド５３の値（＝5）に換えると共に、このオブジェクトｆの到達可能性フィールドのマークと移動先フィールドの値を消去する（Ｓ８０４）。続いて、図１８（ｇ）に示すように、このオブジェクトｆをfree（＝5）の位置に移動する（Ｓ８０５）。なお、図１８（ｇ）中のscan及びfreeは、このオブジェクト移動処理に関係するものではなく、後述するように、スキャン処理のためのものである。その後、処理対象となるオブジェクトを次のオブジェクトａに進めて（Ｓ８０６）、ステップ８０２に戻る。
【０１０８】
このオブジェクトａは、その到達可能性フィールド５１にマークがあり、さらに、このオブジェクトａの移動先フィールド５３に値が格納されているので（Ｓ８０３）、このオブジェトａも移動候補であるとして、freeをこのオブジェクトａの移動先フィールド５３の値（＝6）に換えると共に、このオブジェクトａの到達可能性フィールドのマークと移動先フィールドの値を消去する（Ｓ８０４）。続いて、このオブジェクトａをfree（＝6）の位置に移動する（Ｓ８０５）。そして、ＰにＰのサイズを加えてから（Ｓ８０６）、ステップ８０２に戻る。
【０１０９】
ステップ８０２では、アドレスP（＝7）が古い世代領域４３の使用中領域の後尾アドレス未満ではないと判断して、ＰにＰのサイズを加えて（Ｓ８０7）、オブジェクト移動処理を終了する。この結果、古い世代のゴミ集め（Ｓ１０）が終了する。
【０１１０】
この古い世代のゴミ集め（Ｓ１０）は、図３を用いて前述したように、若い世代のゴミ集めのスキャン処理過程で中断（Ｓ９）した後に行われた処理であるため、この若い世代のゴミ集め（Ｓ１０）が終了すると、中断していた若い世代のゴミ集めのスキャン処理が再開される（Ｓ１１）。このスキャン処理では、スキャン処理の具体例として、図１８（ｈ）を用いて前述したように、アドレス値「３」を先頭とするオブジェクトｃがアドレス「7」の位置にコピーされ、若い世代のゴミ集めが終了する。このように若い世代のゴミ集めが終了すると、若い世代領域４２には、実体が古い世代領域４３に移動してしまったオブジェクトａ，ｃと、システムからアクセスできない、つまり生存していないオブジェクトｂのみが残ることになる。この結果、若い世代領域４２は、不要なオブジェクトのみしか存在しなくなったので、以降、若い世代領域４２の全領域に新たなオブジェクトを格納することができるようになる。
【０１１１】
以上のように、本実施形態では、若い世代領域４２のゴミ集めの際に、この若い世代領域４２に格納されている１以上のオブジェクトのうちから古い世代領域４３へ移すオブジェクトの量、つまり若い世代の生存量ＥＳを、若い世代領域４２の過去のゴミ集め実績から予測し、この移動量と古い世代領域４３の空き容量ＯＦと比較し、その結果に応じて、古い世代領域４３のごみ集めを実行するので、古い世代領域のゴミ集めのタイミングが比較的的確になり、システム障害の可能性を低くすると共に、システムの性能低下を抑えることができる。さらに、若い世代領域４２のゴミ集め実行中に、この若い世代領域４２からのオブジェクトを格納するための空きが古い世代領域４３に無くなった場合、若い世代領域４２のゴミ集めが一時中断され、古い世代領域４３のゴミ集めが実行された後、再び、若い世代領域４２のゴミ集めが再開されるので、よりシステム障害の可能性を低くし、システム性能の低下を抑えることができる。
【０１１２】
［第二の実施形態］
第二の実施形態について、図１９〜図２３を用いて説明する。
【０１１３】
本実施形態では、第一の実施形態のように、若い世代領域のゴミ集めを生き残った全てのオブジェクトが古い世代領域に殿堂入りするのではなく、若い世代領域での１回以上のゴミ集めを生き残ったオブジェクトのみが古い世代領域に殿堂入りする。
【０１１４】
このため、本実施形態では、図１９に示すように、第一の実施形態に対してゴミ集め処理部２０ａの機能構成が異なっている。具体的には、若い世代領域から古い世代領域に移されるオブジェクトの量として、第一の実施形態では若い世代領域のオブジェクトの生存量ＥＳを予測しているが、本実施形態では若い世代領域から古い世代領域へオブジェクトの昇進量ＥＰを予測する。なお、本実施形態は、このゴミ集め処理部２０ａ以外の部分の構成及び動作は第一の実施形態と同様である。
【０１１５】
また、本実施形態では、前述したように、若い世代領域での１回以上のゴミ集めを生き残ったオブジェクトのみが殿堂入りするので、ある世代でのゴミ集めを生き残った回数を把握する必要がある。このため、図２０に示すように、オブジェクトのヘッダ５０は、第一の実施形態と同様の、到達可能性フィールド５１と移動済みフィールド５２と移動先フィールド５３とサイズフィールド５４の他に、現在存在している世代の領域でのゴミ集めを生き残った回数である年齢が格納される年齢フィールド５６ａがある。
【０１１６】
図１９に示すように、データメモリ４０のヒープ領域４１は、若い世代領域４２ａと古い世代領域４３とに分けられている。この若い世代領域４２ａは、さらに、Eden４４とfrom４５とto４６とに分けられている。
【０１１７】
ゴミ集め処理部２０ａは、図１９に示すように、データメモリ４０の若い世代領域４２a及び古い世代領域４３のぞれぞれのゴミ集めを実行するゴミ集め実行部２１ａと、各領域４２ａ，４３の使用量及び空き容量を計測するメモリ監視部２２と、若い世代領域４２aから古い世代領域４３へ殿堂入りするオブジェクト昇進量ＥＰを予測する予測昇進量算出部２７と、これらの各部２１ａ，２２，２７を制御するゴミ集め制御部２３とを有している。予測昇進量算出部２７は、ゴミ集め前のオブジェクトの領域使用量ＹＵに対するゴミ集め後に生き残ったオブジェクトの生存量ＹＳの割合である生存率ＳＲ（＝ＹＳ/ＹＵ）を計測し、過去の生存率ＳＲの実績から現在の生存率ＥＳＲを予測する生存率予測部２５と、若い世代のゴミ集め後に生き残ったオブジェクトの生存量ＹＳに対する若い世代領域４２ａから古い世代領域４３へ殿堂入りするオブジェクトの昇進量ＹＰの割合である昇進率ＰＲ（＝ＹＰ/ＹＳ）を計測し、過去の昇進率ＰＲの実績から次のゴミ集めの際の昇進率ＥＰＲを予測する昇進率予測部２８と、予測された昇進率ＥＰＲと予測された若い世代領域４２ａの現在の生存率ＥＳＲと現在の若い世代領域４２ａの使用量ＹＵとから、若い世代領域４２ａから古い世代領域４３へ殿堂入りするオブジェクトの昇進量ＥＰ（＝ＥＰＲ（ＹＵ・ＥＳＲ））を予測する昇進量予測部２９とを有する。
【０１１８】
記憶割当部１５は、命令実行部１４からオブジェクトのメモリ割当命令を受けると、若い世代領域４２ａのEden４４に格納領域を確保し、この格納領域の先頭アドレスを命令実行部１４に返す。記憶割当部１５は、仮に、若い世代領域４２ａのEden４４に十分な格納領域を確保できないと認識した場合、ゴミ集め処理部２０ａに対してゴミ集め実行命令を出力し、データメモリ４０内のゴミ集めを実行させる。
【０１１９】
次に、記憶割当部１５からゴミ集め実行命令を受けた際のゴミ集め処理部２０ａの動作内容、言い換えると、ゴミ集め処理プログラム３２の実行による処理内容について、図２１に示すフローチャートに従って説明する。
【０１２０】
ゴミ集め処理部２０ａのゴミ集め制御部２３は、前述の記憶割当部１５からゴミ集め実行命令を受けると、生存率予測部２５が若い世代領域４２ａの予測生存率をＥＳＲとして昇進量予測部２９に渡すと共に、昇進率予測部２８が若い世代領域４２ａから古い世代領域４３へ殿堂入りする予測昇進率をＥＰＲとして昇進量予測部２９に渡す（Ｓ１ａ）。この際、ゴミ集め実行命令の受信が例えば５回目以降である場合には、生存率予測部２５は、ここで予測した予測生存率をＥＳＲとして昇進量予測部２９に渡し、昇進率予測部２８は、ここで予測した予測昇進率をＥＰＲとして昇進量予測部２９に渡す。また、ゴミ集め実行命令の受信が例えば５回目未満である場合には、生存率予測部２５は、予め設定された予測生存率をＥＳＲとして生存量予測部２６に渡し、昇進率予測部２８は、予め設定された予測昇進率をＥＰＲとして昇進量予測部２９に渡す。
【０１２１】
続いて、メモリ監視部２２が若い世代領域４２ａの使用量ＹＵ及び古い世代領域４３の空き量ＯＦを計測し、若い世代領域４２ａの使用量ＹＵを生存率予測部２５及び生存量予測部２６に渡すと共に、古い世代領域４３の空き量ＯＦをゴミ集め制御部２３に渡す（Ｓ２）。ここでの使用量ＹＵとは、図２３に示すように、若い世代領域４２ａのEden４４の使用量ＹＯｅとto４６の使用量ＹＯｔとを加算したものである。なお、若い世代領域４２ａのfrom４５は、後述する理由で未使用（但し、生存していないオブジェクトは存在する）である。
【０１２２】
昇進量予測部２９は、若い世代領域４２ａの使用量ＹＵを受け取ると、この使用量ＹＵと先に受け取った若い世代領域４２の予測生存率ＥＳＲとから、若い世代領域４２ａの予測生存量（＝ＥＳＲ・ＹＵ)を求め、この予測生存量に予測昇進率ＥＰＲを掛けて、予測昇進量ＥＰ（＝ＥＰＲ（ＥＳＲ・ＹＵ））を求める。そして、この予測昇進量ＥＰをゴミ集め制御部２３に渡す（Ｓ３ａ）。
【０１２３】
ゴミ集め制御部２３は、若い世代領域４２ａの予測昇進量ＥＰを受け取ると、先に受け取った古い世代領域４３の空き量ＯＦと若い世代領域４２ａの予測昇進量ＥＰとの大小関係を比較し（Ｓ４）、古い世代領域４３の空き量ＯＦに対して若い世代領域４２ａの予測昇進量ＥＰが大きければ、ゴミ集め実行部２１ａに古い世代領域４３のゴミ集めを実行させた後（Ｓ５）、若い世代領域４２aのゴミ集めを実行させる（Ｓ６a）。一方、古い世代領域４３の空き量ＯＦに対して若い世代領域４２aの予測昇進量ＥＰが大きくなければ、ゴミ集め実行部２１ａに若い世代領域４２ａのゴミ集めを開始させる（Ｓ７ａ）。
【０１２４】
ここで、図２３を用いて、古い世代領域４３の空き量ＯＦと若い世代領域４２ａの予測昇進量ＥＰとの大小関係の比較理由、及びこの比較結果でゴミ集めの実行対象領域が異なる理由について説明する。なお、同図（ａ）は若い世代領域４２ａのゴミ集め前のヒープ領域の状態を示し、同図（ｂ）は若い世代領域４２ａのゴミ集め後のヒープ領域の状態を示す。
【０１２５】
若い世代領域４２ａのゴミ集めでは、前述したように、何回かのゴミ集めを生き残ったオブジェクトのみが古い世代領域４３に殿堂入りする。このため、若い世代領域４２ａから古い世代領域４３へ殿堂入りするであろうオブジェクトの量、つまり予測昇進量ＥＰを求め、この予測昇進量ＥＰ分のオブジェクトを古い世代領域４３の空き領域に移せるか否かを把握するために、古い世代領域４３の空き量ＯＦと若い世代領域４２ａの予測昇進量ＥＰとの大小関係を比較する。
【０１２６】
古い世代領域４３の空き量ＯＦに対して若い世代領域４２ａの予測昇進量ＥＰが大きければ、若い世代領域４２ａの予測昇進量ＥＰ分のオブジェクトを古い世代領域４３の空き領域に移せないので、まず、古い世代領域４３のゴミ集めを実行させ（Ｓ５）、その後、若い世代領域４２ａのゴミ集めを実行させる（Ｓ６ａ）。一方、古い世代領域４３の空き量ＯＦに対して若い世代領域４２ａの予測昇進量ＥＰが大きくなければ、若い世代領域４２ａの予測昇進量ＥＰ分のオブジェクトを古い世代領域４３の空き領域に移せるので、若い世代領域４２ａのゴミ集めを開始させる（Ｓ７ａ）。
【０１２７】
若い世代領域４２ａのゴミ集めが開始されると、若い世代領域４２ａから古い世代領域４３にオブジェクトが殿堂入りする。このため、メモリ監視部２２は、第一の実施形態と同様に、若い世代領域４２ａのゴミ集め実行中、古い世代領域４３の空き量が十分に確保されているか否かを確認する（Ｓ８）。メモリ監視部２２は、古い世代領域４３の空き量が十分に確保されなくなったことを検知すると、ゴミ集め制御部２３は、ゴミ集め実行部２１ａに若い世代領域４２ａのゴミ集めを一時中断させ（Ｓ９）、古い世代領域４３のゴミ集めを実行させる（Ｓ１０）。そして、この古い世代領域４３のゴミ集めが終了すると、若い世代領域４２ａのゴミ集めを再開させる（Ｓ１１ａ）。
【０１２８】
若い世代領域４２ａのゴミ集めが終了すると（Ｓ６ａ，Ｓ１１ａ，Ｓ１２）、ゴミ集め実行部２１ａは、若い世代領域４２ａから古い世代領域４３へ実際に移したオブジェクトの量、つまり若い世代領域４２ａからの昇進量をＹＰとして、生存率予測部２５及び昇進率予測部２８に渡す。さらに、若い世代領域４２ａのゴミ集めで、他の領域に実際に移した全オブジェクトの量、つまり若い世代領域４２ａのオブジェクトの生存量をＹＳとして、昇進率予測部２８に渡す（Ｓ１３ａ）。なお、若い世代領域４２ａのゴミ集めで、他の領域に実際に移した全オブジェクトの量、つまり生存量ＹＳは、図２３に示すように、若い世代領域４２ａから古い世代領域４３への実際に移したオブジェクトの量である昇進量ＹＰ（＝ＹＳｔ）に、若い世代領域４２ａ内のある領域から他の領域へ実際に移したオブジェクトの量（ＹＳｅ）を加えた量（ＹＰ（＝ＹＳｔ）＋ＹＳｅ）である。
【０１２９】
生存率予測部２５は、この生存量ＹＳを受け取ると、先のステップ２でメモリ監視部２２から受け取ったゴミ集め前の若い世代領域４２ａの使用量ＹＵとこの生存量ＹＳとから、ゴミ集め直前における若い世代領域４２ａのオブジェクト生存率ＳＲ（＝ＹＳ／ＹＵ）を求め、これを記憶しておく（Ｓ１４）。そして、今回求めたオブジェクト生存率ＳＲと、過去４回のゴミ集めで求めたオブジェクト生存率ＳＲとを統計処理して、次回のゴミ集め直前の若い世代領域４２ａの生存率ＥＳＲを予測する（Ｓ１５）。この予測生存率ＥＳＲは、次回のゴミ集め処理のステップ１ａで用いられる。
【０１３０】
また、昇進率予測部２８は、ステップ１３ａで生存量ＹＳ及び昇進量ＹＰを受け取ると、これらの値を用いて、若い世代領域４２ａの昇進率ＰＲ（＝ＹＰ/ＹＳ）を求め、これを記憶しておく（Ｓ１６）。そして、今回求めた昇進率ＰＲと、過去４回のゴミ集めで求めた昇進率ＰＲとを統計処理して、次回の若い世代領域４２ａのゴミ集めの際の昇進率ＥＰＲを予測する（Ｓ１７）。この予測昇進率ＥＰＲは、次回のゴミ集め処理のステップ１ａで用いられる。
【０１３１】
なお、過去の生存率ＳＲから予測生存率ＥＳＲを求める方法、過去の昇進率ＰＲから予測昇進率ＥＰＲを求める方法は、第一の実施形態において、例示した各種統計処理方法が考えられる。
【０１３２】
次に、若い世代のゴミ集め処理（Ｓ６ａ，Ｓ７ａ）について説明する。
【０１３３】
この実施形態でも、ゴミ集め実行部２１ａは、若い世代のゴミ集め処理で、図４に示すように、初期化処理（Ｓ１００）、ルート処理（Ｓ２００）、スキャン処理（Ｓ３００）を実行する。但し、初期化処理の内容、ルート処理及びスキャン処理でのコピー処理の内容が第一の実施形態と異なるので、以下では、これらの内容について説明する。
【０１３４】
初期化処理では、ゴミ集め実行部２１ａは、まず、第一の実施形態と同様に、大域変数のscan及びfreeを古い世代の空き領域ＯＦの先頭アドレスとする。次に、図２３に示すように、現在のfrom４５をto４６とし、現在のto４６をfrom４５とする。この結果、未使用の領域はfrom４５からto４６に変わる。そして、変数scan  ｔｏ及び変数free  ｔｏを新たなto４６の先頭アドレスとして、初期化処理を終了する。
【０１３５】
ルート処理（Ｓ２００）では、第一の実施形態と同様に、未処理のルートの値を引数としてコピー処理を呼び出し（図５、Ｓ２０３）、スキャン処理（Ｓ３００）では、未処理のポインタの値を引数としてコピー処理を呼び出す（図７、Ｓ３０４）。
【０１３６】
このコピー処理（Ｓ４００ａ）で、ゴミ集め実行部２１ａは、まず、第一の実施形態のコピー処理（図６、Ｓ４００）と同様に、ルート処理又はスキャン処理からの引数をＰに代入し（Ｓ４０１）、このＰの値を先頭アドレスとするオブジェクトが移動済みであるか否かを判断する（Ｓ４０２）。Ｐを先頭アドレスとするオブジェクトが移動済みである場合には、Ｐを先頭アドレスとするオブジェクトの移動先フィールド５３に格納されている値をコピー処理の戻り値として返して（Ｓ４０８）、コピー処理を終了する。
【０１３７】
一方、Ｐを先頭アドレスとするオブジェクトが移動済みでない場合には、このオブジェクトの年齢フィールド５６ａを参照して、このオブジェクトの年齢が予め定められた昇進年齢より大きいか否かを判断する（Ｓ４１０）。このオブジェクトの年齢が予め定められた昇進年齢より大きい場合、つまり、図２３（ａ）に示すように、ゴミ集めの初期化処理前の若い世代領域４２ａのｔｏ４６（初期化処理後のfrom４５）に格納されているオブジェクトである場合、第一の実施形態のステップ４０３〜ステップ４０５と同様の処理を行う。すなわち、変数addrに、初期化処理で設定したfreeの値を代入し（Ｓ４０３）、Ｐを先頭アドレスとするオブジェクトをfreeが指すアドレスを先頭とする領域にコピーし（Ｓ４０４）、freeの値をコピーしたオブジェクトのサイズ分だけ大きくする（Ｓ４０５）。そして、このオブジェクトの年齢フィールド５６ａの値を０にする（Ｓ４１１）。
【０１３８】
一方、ステップ４１０の判断で、このオブジェクトの年齢が予め定められた昇進年齢より大きくない場合、つまり、図２３（ａ）に示すように、ゴミ集めの初期化処理前の若い世代領域４２ａのEden４４に格納されているオブジェクトである場合、変数addrに、初期化処理で設定したfree  toの値を代入し（Ｓ４０３a）、Ｐを先頭アドレスとするオブジェクトをfree toが指すアドレスを先頭とする領域にコピーし（Ｓ４０４ａ）、free toの値をコピーしたオブジェクトのサイズ分だけ大きくする（Ｓ４０５ａ）。そして、このオブジェクトの年齢フィールド５６ａの値に１を加える（Ｓ４１１ａ）。
【０１３９】
コピー元のオブジェクトの年齢フィールド５６ａの値を変更した後（Ｓ４１１，４１１ａ）は、第一の実施形態と同様に、ステップ４０６，４７０の処理を実行してコピー処理を終了する。
【０１４０】
以上のようなコピー処理（Ｓ４００ａ）を含むルート処理及びスキャン処理が終了し、若い世代のゴミ集めが終了すると、図２３に示すように、若い世代領域４２ａのEden４４に格納されていた生存中のオブジェクトが若い世代領域４２ａのｔｏ４６にコピーされ、Eden４４は、生存していないオブジェクト又はコピー済みのオブジェクトのみになり、未使用領域として利用できるようになる。また、ゴミ集めの初期化処理前の若い世代領域４２ａのｔｏ４６（初期化処理後のfrom４５）に格納されているオブジェクトは、古い世代領域４３の未使用領域に格納され、ゴミ集めの初期化処理前のｔｏ４６、言い換えると、初期化処理後のfrom４５は、生存していないオブジェクト又はコピー済みのオブジェクトのみになり、未使用領域として利用できるようになる。
【０１４１】
ところで、この実施形態におけるスキャン処理では、図７を用いて説明した第一の実施形態のスキャン処理のステップ３０１，３０２,３０３，３０６で、各処理の「scan」を「scan  to」にし、各処理の「free」を「free to」にした処理を行う。
【０１４２】
また、若い世代のメモリ内容修正処理でも、図１１に示す第一の実施形態の若い世代のメモリ内容修正処理を二点変更した処理を行う。第一点は、最初の処理において、ステップ７１１でEden４４の先頭アドレスをSに代入する処理に変更し、ステップ７１２の判断では、SがEden４４の使用中領域の最後のアドレス未満であるかを調べる処理に変更する点である。第二点は、次に実行する処理において、ステップ７１１でTo４６の先頭アドレスをSに代入する処理に変更し、ステップ７１２の判断では、Sがto４６の使用中領域の最後のアドレス未満であるかを調べる処理に変更する点である。
【０１４３】
なお、以上の実施形態では、昇進年齢が常に一定であるとしたが、システムの実行状況によって昇進年齢を可変にすることも可能である。
【０１４４】
［第三の実施形態］
第三の実施形態について、図２４を用いて説明する。
【０１４５】
本実施形態では、第一の実施形態のように、古い世代のゴミ集めをする際には、古い世代領域のゴミ集めのみを行わず、全世代のゴミ集めをする。
【０１４６】
このため、本実施形態のゴミ集め処理では、図２４に示すように、第一の実施形態における図３に示すゴミ集め処理中の以下の二点が異なる。すなわち、第一点は、古い世代領域４３の空き量ＯＦと若い世代領域４２の予測生存量ＥＳとの大小関係を比較した後（Ｓ４）、古い世代領域４３の空き量ＯＦに対して若い世代領域４２の予測生存量ＥＳが大きければ、ゴミ集め実行部２１に直ちに全世代領域のゴミ集めを実行させる（Ｓ５ａ）点である。第二点は、ゴミ集め実行部２１に若い世代領域４２のゴミ集めを実行させている最中に（Ｓ７）、古い世代領域４３の空き量が十分に確保されなくなった場合（Ｓ８）、若い世代領域４２のゴミ集めを中止させて（Ｓ９ｂ）、ゴミ集め実行部２１に直ちに全世代領域のゴミ集めを実行させる（Ｓ１０）点である。
【０１４７】
全世代領域のゴミ集め処理は、第一の実施形態の古い世代領域４３のゴミ集めと同様に、Lisp2方式のアルゴリズムを用いたマークコンパクト方式を採用する。したがって、本実施形態における全世代領域のゴミ集め処理でも、図８に示すフローチャートに示す処理と同様に、マーク処理、移動先決定処理、メモリ内容修正処理、オブジェクト移動処理を行う。但し、本実施形態では、マーク処理及び移動先決定処理に関して、第一の実施形態と若干異なる。
【０１４８】
本実施形態のマーク処理の際には、全世代領域に存在するオブジェクトで、ルートから到達可能な全てのオブジェクの到達可能性フィールドにマークが付けられる。
【０１４９】
また、本実施形態の移動先決定処理の際には、まず、図９に示すフローチャートに従って古い世代領域のオブジェクトの移動先を決定した後、同フローチャートに従って若い世代領域のオブジェクトの移動先を決定する。この場合、図９中のフローチャートのステップ６０１で、若い世代領域の先頭アドレスの値をＰに代入し、freeに対する代入処理を行わない。さらに、ステップ６０２で、Ｐの値が若い世代領域の使用中の領域の後尾アドレス未満であるか否かを判断する。
【０１５０】
第一の実施形態の古い世代領域４３のゴミ集め処理の方法に以上のような変更を加えることで、全世代領域のゴミ集めが可能になる。
【０１５１】
以上、本実施形態では、若い世代領域のゴミ集め中に、古い世代領域の空き容量が不足した場合、若い世代領域のゴミ集めが中止されるものの、全世代領域のゴミ集めが実行されるので、基本的に第一の実施形態と同様の効果を得ることができる。
【０１５２】
ここで、本実施形態の変形例について説明する。
【０１５３】
オブジェクトとしては、図２を用いて説明した第一の実施形態のように、到達可能性フィールド５１及び移動済みフィールド５２を有するものが考えられるが、これら二つのフィールド５１，５２が一つのフィールドで形成され、この一つのフィールドが到達可能性フィールドと移動済みフィールドとを兼ねる場合も考えられる。そこで、このような場合の対応方法について、第三の実施形態の変形例として、以下で説明する。
【０１５４】
この変形例でも、第三の実施形態と同様に、若い世代領域４２のゴミ集めを実行させている最中に（Ｓ７）、古い世代領域４３の空き量が十分に確保されなくなった場合（Ｓ８）、若い世代領域４２のゴミ集めを中止させて（Ｓ９ｂ）、ゴミ集め実行部２１に直ちに全世代領域のゴミ集めを実行させる（Ｓ１０）。但し、若い世代のゴミ集め中止（Ｓ９ｂ）の後、再び、若い世代のゴミ集めを行う。この再度行う若い世代のゴミ集めでは、図６に示すコピー処理の際、ステップ４０２でＰを先頭アドレスとするオブジェクトが移動済みでない場合、Ｐを戻り値としてコピー処理を終了する。そして、この再度の若い世代のゴミ集めが終了したら、若い世代領域に存在する全てのオブジェクトについて、到達可能性フィールド兼移動済みフィールドのマーク（移動済みを示すマーク）を消去する。
【０１５５】
また、全世代領域のゴミ集めでは、第三の実施形態と同様に、マーク処理、移動先決定処理、メモリ内容修正処理、オブジェクト移動処理を行う。これらの処理のうち、マーク処理及び移動先決定処理に関しては、第三の実施形態と同様である。
【０１５６】
メモリ内容修正処理における若い世代のメモリ内容修正処理では、第一の実施形態における若い世代のメモリ内容修正処理を行わず、図１４に示す第一の実施形態の古い世代のメモリ内容修正処理の一部を変更した処理を行う。この若い世代のメモリ内容修正処理では、図１４のフローチャート中、ステップ７５１で若い世代領域の先頭アドレスをＰに代入し、ステップ７５２でＰの値が若い世代領域の使用中領域の後尾アドレス未満であるか否かを判断する。その他の処理は、図１４のフローチャートに示す処理と同様である。
【０１５７】
また、各メモリ内容修正処理で呼び出される移動先取得処理では、図１２に示すフローチャート中のステップ７３４，７３５，７３６を省略し、ステップ７３２で到達可能性フィールドにマークがないと判断した場合には、直ちに、ステップ７３７に進む処理を行う。
【０１５８】
［第四の実施形態］
第四の実施形態について、図２５を用いて説明する。
【０１５９】
本実施形態は、第一の実施形態の変形例で、第三の実施形態に対するその変形例との関係のように、第一の実施形態におけるオブジェクト中の一つのフィールドが到達可能性フィールドと移動済みフィールドとを兼ねる場合の例である。
【０１６０】
本実施形態は、古い世代領域に存在するオブジェクトでは、このオブジェクトの兼用フィールドを到達可能性フィールドとして利用し、若い世代領域に存在するオブジェクトでは、このオブジェクトの兼用フィールドを移動済みフィールドとして利用する。この区別を行うため、オブジェクトが若い世代領域と古い世代領域のどちらに属するかによって、到達可能性フィールドを検査する場合の処理に変更が加わる。さらに、メモリ内容修正処理では、第一の実施形態において、若い世代領域のオブジェクトの到達可能性フィールドにマークを付けることで移動先が更新済みであることを区別したが、本実施形態おいては、メモリ内容修正処理の完了点を示すポインタとオブジェクトのアドレスを比較することで、オブジェクトの移動先が更新済みであるかを区別する。それ以外のアルゴリズムについては第一の実施形態と同様である。そこで、以下、第一の実施形態との相違点のみについて説明する。
【０１６１】
図１１に示す若い世代のメモリ内容修正処理では、この処理で用いる変数Ｓを大域変数として確保する。この大域変数Ｓは、メモリ内容修正処理がどの場所まで終了しているかを判定するために用いる。
【０１６２】
また、各メモリ内容修正処理で呼び出される移動先取得処理では、図２５のフローチャートに示す処理を行う。
【０１６３】
ゴミ集め実行部２１は、第一の実施形態と同様に、この移動先取得処理（Ｓ７３０ｃ）で、Pへの引数代入（Ｓ７３１）、Ｐを先頭アドレスとするオブジェクトの兼用フィールドにマークが付いているか否かの調査（Ｓ７３２）を行う。マークが付いていない場合、第一の実施形態と異なり、直ちに、Ｐの値を戻り値とし（Ｓ７３７）、処理を終了する。つまり、この場合は、引数として与えられた値がそのまま戻り値になる。また、マークが付いている場合は、Ｐの値が前述の大域変数Ｓの値未満であるか、又は、Ｐの値が古い世代領域の先頭アドレス以上であるかを調べる（Ｓ７３８）。Ｐの値がＳの値より小さい場合、Ｐを先頭アドレスとするオブジェトの兼用フィールドのマークは移動済みであることを表し、このオブジェクトの移動先フィールドが指す先はコンパクションによりこのオブジェクトが移動される先を示す。この場合、移動先は、移動先フィールドの値となる。また、Ｐが古い世代領域の先頭アドレス以上のときは、Ｐを先頭アドレスとするオブジェクトが古い世代領域に属するので、このオブジェクトの移動先フィールドの値がオブジェクトの移動先となる。
【０１６４】
ステップ７３８の判断で、Ｐの値が前述の大域変数Ｓの値未満であるか、又は、Ｐの値が古い世代領域の先頭アドレス以上であると判断した場合には、このオブジェクトの移動先フィールドの値を戻り値とし（Ｓ７３３）、処理を終了する。また、Ｐの値が前述の大域変数Ｓの値未満ではなく、且つＰの値が古い世代領域の先頭アドレス以上ではないと判断した場合には、このオブジェクトの移動先フィールドの値がこのオブジェクトの実体が存在する場所を示すので、このオブジェクトの移動先フィールドの値、つまり実体が存在する場所のアドレスを引数として、この処理自身を呼び出し（Ｓ７３５）、呼び出した処理からの戻り値を、この移動先取得処理での戻り値とし（Ｓ７３６）、処理を終了する。
【０１６５】
以上の変更により、ブジェクト中の一つのフィールドが到達可能性フィールドと移動済みフィールドとを兼ねる場合でも、以上で説明した処理を除き、基本的に、第一の実施形態と同様の処理を行うことができる。
【図面の簡単な説明】
【０１６６】
【図１】本発明に係る第一の実施形態のコンピュータの機能構成を示す説明図である。
【図２】本発明に係る第一の実施形態のオブジェクトのデータ構成を示す説明図である。
【図３】本発明に係る第一の実施形態のゴミ集め処理のフローチャートである。
【図４】図３のフローチャート中の若い世代のゴミ集め処理のフローチャートである。
【図５】図４のフローチャート中のスキャン処理のフローチャートである。
【図６】本発明に係る第一の実施形態のルート処理及びスキャン処理中のコピー処理のフローチャートである。
【図７】図４のフローチャート中のルート処理のフローチャートである。
【図８】図３のフローチャート中の古い世代のゴミ集め処理のフローチャートである。
【図９】図８のフローチャート中の移動先決定処理のフローチャートである。
【図１０】図８のフローチャート中のメモリ内容修正処理のフローチャートである。
【図１１】図１０のフローチャート中の若い世代のメモリ内容修正処理のフローチャートである。
【図１２】図１１のフローチャート中の移動先取得処理のフローチャートである。
【図１３】図１０のフローチャート中のルートのメモリ内容修正処理のフローチャートである。
【図１４】図１０のフローチャート中の古い世代のメモリ内容修正処理のフローチャートである。
【図１５】図１０のフローチャート中のオブジェクト移動処理のフローチャートである。
【図１６】本発明に係る第一の実施形態で、若い世代領域と古い世代領域のいずれの領域をゴミ集めするかの判断を説明するための説明図である。
【図１７】本発明に係る第一の実施形態でのゴミ集め実行過程でのヒープ領域の変化を示す説明図（その１）である。
【図１８】本発明に係る第一の実施形態でのゴミ集め実行過程でのヒープ領域の変化を示す説明図（その２）である。
【図１９】本発明に係る第二の実施形態のコンピュータの機能構成を示す説明図である。
【図２０】本発明に係る第二の実施形態のオブジェクトのデータ構成を示す説明図である。
【図２１】本発明に係る第二の実施形態のゴミ集め処理のフローチャートである。
【図２２】本発明に係る第二の実施形態のコピー処理のフローチャートである。
【図２３】本発明に係る第二の実施形態で、若い世代領域と古い世代領域のいずれの領域をゴミ集めするかの判断を説明するための説明図である。
【図２４】本発明に係る第三の実施形態のゴミ集め処理のフローチャートである。
【図２５】本発明に係る第四の実施形態の移動先取得処理のフローチャートである。
【符号の説明】
【０１６７】
１０：コンピュータ、１１：プロセッサ、１２：仮想マシン、２０，２０a:ゴミ集め処理部、２１，２１a:ゴミ集め実行部、２２：メモリ監視部、２３：ゴミ集め制御部、２４：予測生存量算出部、２５：生存率予測部、２６：生存量予測部、２７：予測昇進量算出部、２８：昇進率予測部、２９：昇進量予測部、３０：プログラムメモリ、３１：仮想マシンプログラム、３２：ゴミ集め処理（CG）プログラム、３３：実行プログラム、４０：データメモリ、４１：ヒープ領域、４２，４２ａ：若い世代領域、４３：古い世代領域、５０：ヘッダ、５１：到達可能性フィールド、５２：移動済みフィールド、５３：移動先フィールド、５４：サイズフィールド、５６，５７，５９：ポインタフィールド、５６ａ：年齢フィールド、５８：データ
【図１】
2007213252.tif 000003
【図２】
2007213252.tif 000004
【図３】
2007213252.tif 000005
【図４】
2007213252.tif 000006
【図５】
2007213252.tif 000007
【図６】
2007213252.tif 000008
【図７】
2007213252.tif 000009
【図８】
2007213252.tif 000010
【図９】
2007213252.tif 000011
【図１０】
2007213252.tif 000012
【図１１】
2007213252.tif 000013
【図１２】
2007213252.tif 000014
【図１３】
2007213252.tif 000015
【図１４】
2007213252.tif 000016
【図１５】
2007213252.tif 000017
【図１６】
2007213252.tif 000018
【図１７】
2007213252.tif 000019
【図１８】
2007213252.tif 000020
【図１９】
2007213252.tif 000021
【図２０】
2007213252.tif 000022
【図２１】
2007213252.tif 000023
【図２２】
2007213252.tif 000024
【図２３】
2007213252.tif 000025
【図２４】
2007213252.tif 000026
【図２５】
2007213252.tif 000027