(57)【要約】【課題】  ＧＣの実行回数をより少なくしてプログラムの停止時間を短縮する。【解決手段】プログラムの実行により生成されたオブジェクトを配置する記憶領域と、記憶領域内にガベージコレクションの対象となるヒープを有して、プログラムの実行を行う計算機において、ヒープに、余命の不明なオブジェクト用の余命不明領域と、余命の分っている１つ以上のオブジェクト用の余命別サブ領域を規定する。ヒープに格納されたオブジェクトの余命を計算し、余命の判明したオブジェクトをあてはまる余命別サブ領域に集めて配置し、余命別サブ領域の余命が尽きるまで余命別サブ領域のガベージコレクションを行わない。【選択図】  図２
2014182772.tif 000002
【特許請求の範囲】
【請求項１】
少なくともプログラムを記憶するメモリと、該プログラムを実行するプロセッサと、該プログラムの実行により生成されたオブジェクトを配置し、ガベージコレクションの対象となるヒープを該メモリ内に有する計算機であって、
該ヒープに、余命が不明なオブジェクトを格納する第１の領域と、余命が判明しているオブジェクトを格納する余命別の第２の領域を確保し、
該ヒープに格納されたオブジェクトの余命を計算して、余命が不明なオブジェクトを該第１の領域に配置し、該第１の領域のガベージコレクションを行い、
該余命の計算の結果、該余命の判明したオブジェクトを該第２の領域に配置し、該第１の領域のガベージコレクションの実行回数よりも少ない回数、該第２の領域のガベージコレクションを行うことを特徴とする計算機。
【請求項２】
前記第２の領域に配置されたオブジェクトの余命が尽きるまで該第２の領域のガベージコレクションを行わないことを特徴とする請求項１に記載の計算機。
【請求項３】
前記第２の領域は余命上限値および余命下限値を持ち、前記第２の領域の余命は余命上限値に等しいことを特徴とする請求項１又は２に記載の計算機。
【請求項４】
前記第２の領域として余命別に複数の余命サブ領域が用意され、
前記余命下限値以上かつ前記余命上限値未満にあてはまる余命を持つ前記オブジェクトを、該当する１の余命サブ領域に配置することを特徴とする請求項１乃至３のいずれかの項に記載の計算機。
【請求項５】
前記余命不明領域のガベージコレクション毎に、前記第２の領域内のオブジェクトの余命を１だけデクリメントし、前記第２の領域内のオブジェクトのガベージコレクション経験回数を１だけインクリメントし、前記第２の領域の前記余命上限値および前記余命下限値および余命を１だけデクリメントすることを特徴とする請求項２乃至４のいずれかの項に記載の計算機。
【請求項６】
前記第２の領域の余命が１未満になるまで前記第２の領域のガベージコレクションを行わないことを特徴とする請求項１乃至５のいずれかの項に記載の計算機。
【請求項７】
あらかじめ与えられた目標メモリ使用量をMmax、次回のガベージコレクション直前のメモリ使用量をM(n)、余命が短い順に並べた前記第２の領域S(j)が持つオブジェクト量をA(j)としたとき、A(1)＜M(n)−Mmaxである場合に、
A(1)＋・・・＋A(m)≧M(n)−Mmax
となる最小のmを見つけ、第２の領域S(m)に含まれる前記オブジェクトの余命別のオブジェクト量kを余命とした時にO(m,k)とし、
A(1)＋・・・＋A(m-1)＋O(m,k1)＋・・・＋O(m,kh)≧M(n)−Mmax
である最小のkhを見つけ、前記第２の領域S(m)を分割して前記オブジェクトの余命がk1〜khである領域S(m)’とそれ以外の領域S(m)”に分け、前記第２の領域S(1)〜S(m-1)とS(m)’を融合して前記第２の領域S(1)’とし、S(1)’とS(m)”の前記余命上下限値を調整し、メモリ使用量を目標メモリ使用量以下にすることを特徴とする請求項１乃至６のいずれかの項に記載の計算機。
【請求項８】
前記プロセッサは、前記ガベージコレクションの後に、ガベージコレクションを生き残ったオブジェクトの余命を再計算し、前記再計算した結果を、前記生き残ったオブジェクトと同種のオブジェクトの余命に反映させることを特徴とする請求項１乃至７のいずれかの項に記載の計算機。
【請求項９】
前記プロセッサは、前記ヒープを分割して超長余命オブジェクト領域を作成し、余命閾値より余命の長い超長余命オブジェクトを検出し、該超長余命オブジェクトを該超長余命オブジェクト領域に保管させることを特徴とする請求項１乃至８のいずれかの項に記載の計算機。
【請求項１０】
前記プロセッサは、前記生き残ったオブジェクトがガベージコレクションを生き残った回数を記録し、前記再計算において、前記生き残ったオブジェクトの余命に前記生き残った回数を加えた値を新たな余命とすることを特徴とする請求項１乃至９のいずれかの項に記載の計算機。
【請求項１１】
前記プロセッサは、入力装置より入力された値に基づいて、前記余命上限値、前記余命下限値、前記目標メモリ使用量、前記余命閾値を前記メモリ内に設定することを特徴とする請求項２乃至１０のいずれかの項に記載の計算機。
【請求項１２】
前記プロセッサは、寿命及び余命を以下の式によって計算して求める、請求項１乃至１１のいずれかの項に記載の計算機。（ＧＣ：ガベージコレクションの略）
平均ＧＣ間隔＝（現在時刻−プログラム開始時刻）/全ＧＣ回数
寿命＝（現在時刻−オブジェクトの生成時刻）/平均ＧＣ間隔
余命＝寿命−ＧＣ経験回数
【請求項１３】
少なくともプログラムを記憶するメモリと、該プログラムを実行するプロセッサと、該プログラムの実行により生成されたオブジェクトを配置し、ガベージコレクションの対象となるヒープを該メモリ内に有し、該ヒープに、余命が不明なオブジェクトを格納する第１の領域と、余命が判明しているオブジェクトを格納する余命別の第２の領域が確保される計算機におけるガベージコレクション制御方法であって、
該ヒープに格納されたオブジェクトの余命を計算して、余命が不明なオブジェクトを該第１の領域に配置し、該第１の領域のガベージコレクションを行い、
該余命の計算の結果、該余命の判明したオブジェクトを該第２の領域に配置し、該第１の領域のガベージコレクションの実行回数よりも少ない回数、該第２の領域のガベージコレクションを行う
ことを特徴とするガベージコレクション制御方法。
【請求項１４】
少なくともプログラムを記憶するメモリと、該プログラムを実行するプロセッサと、該プログラムの実行により生成されたオブジェクトを配置し、ガベージコレクションの対象となるヒープを該メモリ内に有し、該ヒープに、余命が不明なオブジェクトを格納する第１の領域と、余命が判明しているオブジェクトを格納する余命別の第２の領域が確保される計算機において、該プロセッサで実行可能なガベージコレクション制御用プログラムであって、
該プロセッサを、
該ヒープに格納されたオブジェクトの余命を計算して、余命が不明なオブジェクトを該第１の領域に配置し、該第１の領域のガベージコレクションを行い、
該余命の計算の結果、該余命の判明したオブジェクトを該第２の領域に配置し、該第１の領域のガベージコレクションの実行回数よりも少ない回数、該第２の領域のガベージコレクションを行う
ように動作させることを特徴とするガベージコレクション制御用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、計算機、ガベージコレクション制御方法及びプログラムに関する。
【背景技術】
【０００２】
コンピュータプログラムを開発する上で、プログラムで利用するメモリ領域の確保処理または解放処理は、不正領域の参照などプログラムの不具合を起こしやすいことが知られている。特に大規模なプログラム開発においては、プログラマが全てのメモリ領域の確保または解放処理を完全に把握することは困難になりつつある。
【０００３】
この解決手段として、プログラム中でのメモリ管理を自動化するガベージコレクタが知られている。ガベージコレクタを利用するメモリ管理機能を備えた言語処理系の１つであるＪａｖａ（登録商標）では、メモリ領域確保のための手段は用意されているが、解放はガベージコレクタが実施する。そのため、Ｊａｖａプログラムの開発者はメモリ領域の確保は明示するが、メモリ領域の解放処理を記述する必要はない。ガベージコレクタが実行するメモリ解放機能がガベージコレクション（以下、単に「ＧＣ」という）である。
【０００４】
ＧＣとは、プログラムが動的に確保したメモリ領域のうち、不要になったデータ（オブジェクト）を判別し、そのオブジェクト（単に「obj」ということがある）が占有していた領域を自動的に解放する機能である。なお、一般的なＪａｖａ仮想マシンにおけるＧＣ発動の契機は、データ配置領域の空きがなくなった際である。非特許文献１に記載されているように、一般的なＧＣの手法では、Ｊａｖａプログラムの全ての実行スレッドを停止させて、不要なオブジェクトを回収してメモリ領域を解放することが多い。
【０００５】
また、ＧＣで効率的にメモリ領域を回収する手法として、非特許文献２に記載されたＧａｒｂａｇｅ Ｆｉｒｓｔ ＧＣ手法（以下、「Ｇ１ＧＣ」という）や、特許文献１に記載されたオブジェクト寿命を利用したオブジェクト回収方法が知られている。Ｇ１ＧＣでは、プログラム実行と並行して、生存しているオブジェクトにマークをつけ（以下、「オブジェクトの生死判定」という）、マークのついていない不要オブジェクトが多いメモリ領域を選択的にＧＣすることによって、ＧＣでのメモリ領域回収率を高くしようとしている。
【０００６】
また、特許文献１に記載の、オブジェクトの寿命を用いる方法では、プログラム上のオブジェクト生成点に対して、その場所で生成したオブジェクトの寿命を求め、同じ寿命のオブジェクトを1つのメモリ領域に集めることによって、そのメモリ領域内オブジェクトが一度に不要になる量を多くし、ＧＣで効率よくメモリ領域を回収しようとしている。オブジェクトの寿命は、特許文献１に記載のように、オブジェクトの生成時の時間情報と、オブジェクトが不要になったことが検出された時点の時間情報の差分をとることで、寿命を決定できる。例えば、時間情報を、時刻÷平均ＧＣ間隔時間とすることで、寿命をＧＣ回数で表現することができる。更に、ＧＣ回数で数えたオブジェクトの余命を、オブジェクトの寿命とオブジェクトのＧＣ経験回数の差分で定義することができる。
【先行技術文献】
【特許文献】
【０００７】
【特許文献１】特開２０１２−１１８８３４号公報
【非特許文献】
【０００８】
【非特許文献１】中村成洋／相川光著、竹内郁雄監修、「ガベージコレクションのアルゴリズムと実装」、秀和システム、ｐ２３−ｐ１８４、２０１０
【非特許文献２】「Ｊａｖａ ＨｏｔＳｐｏｔ Ｇａｒｂａｇｅ Ｃｏｌｌｅｃｔｉｏｎ」、http://www.oracle.com/technetwork/java/javase/tech/g1−intro−jsp−135488.html、２０１３
【発明の概要】
【発明が解決しようとする課題】
【０００９】
長寿命なオブジェクトは複数回のＧＣを生き延び、そのうちの最後のＧＣでオブジェクトが回収されて、対応するメモリ領域が解放される。寿命が同じでもオブジェクト生成のタイミングの違いから、余命が異なるオブジェクトを同じメモリ領域に配置した場合にも、同じように複数回のＧＣを生き延びるオブジェクトが発生する。このような長寿命なオブジェクトにとって、最後のＧＣ以外のＧＣは無駄なＧＣである。この無駄なＧＣがプログラムの停止時間を長引かせる原因となり問題である。
【００１０】
そこで本発明の目的は、ＧＣの実行回数をより少なくしてプログラムの停止時間を短縮することにある。
【課題を解決するための手段】
【００１１】
本発明に係る計算機は、好ましくは、少なくともプログラムを記憶するメモリと、該プログラムを実行するプロセッサと、該プログラムの実行により生成されたオブジェクトを配置し、ガベージコレクションの対象となるヒープを該メモリ内に有する計算機であって、
該ヒープに、余命が不明なオブジェクトを格納する第１の領域と、余命が判明しているオブジェクトを格納する余命別の第２の領域を確保し、
該ヒープに格納されたオブジェクトの余命を計算して、余命が不明なオブジェクトを該第１の領域に配置し、該第１の領域のガベージコレクションを行い、
該余命の計算の結果、該余命の判明したオブジェクトを該第２の領域に配置し、該第１の領域のガベージコレクションの実行回数よりも少ない回数、該第２の領域のガベージコレクションを行うことを特徴とする計算機として構成される。
好ましい例では、前記第２の領域に配置されたオブジェクトの余命が尽きるまで該第２の領域のガベージコレクションを行わない。
【００１２】
本発明に係るガベージコレクション制御方法は、好ましくは、少なくともプログラムを記憶するメモリと、該プログラムを実行するプロセッサと、該プログラムの実行により生成されたオブジェクトを配置し、ガベージコレクションの対象となるヒープを該メモリ内に有し、該ヒープに、余命が不明なオブジェクトを格納する第１の領域と、余命が判明しているオブジェクトを格納する余命別の第２の領域が確保される計算機におけるガベージコレクション制御方法であって、
該第１の領域に配置されたオブジェクトの余命を計算して、該余命の判明したオブジェクトを該第２の領域に配置し、かつ該第１の領域のガベージコレクションを行い、
該第２の領域に配置されたオブジェクトについては、該オブジェクトの余命が尽きるまで該第２の領域のガベージコレクションを行わないことを特徴とするガベージコレクション制御方法として構成される。
【００１３】
本発明はまた、上記計算機でガベージコレクション制御方法を実施するガベージコレクション制御用プログラムとしても把握される。
【発明の効果】
【００１４】
本発明によれば、余命の判明したオブジェクトを格納する領域についてはＧＣの実行回数を少なくする、好ましくは当該領域に配置されたオブジェクトの余命が尽きるまで当該領域のガベージコレクションを行わないことにより、ＧＣの実行回数を減少させることができる。これにより、ＧＣのための停止時間が減少するので、プログラムの停止時間を短縮することが可能となる。
【図面の簡単な説明】
【００１５】
【図１】一実施形態による計算機システムの構成例を示す図である。
【図２】計算機の主メモリの機能構成例を示す図である。
【図３】領域管理テーブル２０７の構成例を示す図である。
【図４】余命管理テーブル２０８の構成例を示す図である。
【図５】Ｊａｖａ仮想マシンの処理を示すフローチャートである。
【図６】領域初期分割Ｓ５０２の処理を示すフローチャートである。
【図７】Ｊａｖａプログラム実行Ｓ５０３の処理を示すフローチャートである。
【図８】ＧＣ処理Ｓ５０５を示すフローチャートである。
【図９】領域毎処理Ｓ８０６を示すフローチャートである。
【図１０】オブジェクト余命計算Ｓ９０１の処理を示すフローチャートである。
【図１１】オブジェクト再配置Ｓ９０４の処理を示すフローチャートである。
【図１２】再配置処理Ｓ１１０３を示すフローチャートである。
【図１３】余命上下限値再計算Ｓ１２０８の処理を示すフローチャートである。
【図１４】余命別サブ領域用処理Ｓ８０９を示すフローチャートである。
【図１５】非ＧＣ領域毎処理Ｓ１４０３を示すフローチャートである。
【図１６】余命別サブ領域分割融合Ｓ１４０５の処理を示すフローチャートである。
【図１７】超長余命オブジェクト領域用処理Ｓ８０８を示すフローチャートである。
【発明を実施するための形態】
【００１６】
以下、図面を参照して、本発明の好ましい実施形態について詳細に説明する。
図１は、一実施形態による計算機システムの構成例を示す。
計算機システムは、プロセッサ１１および主メモリ１２を有する計算機１０と、ハードディスクドライブのような外部記憶装置１５と、液晶ディスプレイのような表示装置１３と、ＤＶＤ−ＲＯＭのような可搬型の記憶媒体１６を読み取る駆動装置１７と、キーボードやマウス等の入力装置１４を有して構成される。プロセッサ１１では、オブジェクト指向言語体系であるＪａｖａ規格に準拠したＪａｖａ仮想マシン１０が動作する。なお本発明は、Ｊａｖａ仮想マシン１０の構成に限定されるものではなく、オブジェクトを管理可能なプログラム言語処理系一般に適用することが可能である。
【００１７】
図２は主メモリ１２の内部機能構成の例を示す。
主メモリ１２は種々のデータやプログラムを格納する。Ｊａｖａプログラム２０６は、Ｊａｖａ仮想マシン１０上で動作するプログラムである。Ｊａｖａヒープ２０１は、Ｊａｖａプログラム２０６が利用するメモリ領域である。Ｊａｖａヒープ２０１は、余命が不明なオブジェクト（ｏｂｊと略す）を管理する余命不明領域２０２と、余命が判明している１又は複数のオブジェクトを管理する１つ以上の余命別サブ領域２０３と、非常に長い余命と判断されるオブジェクトを管理する超長余命オブジェクト用領域２０５を有して構成される。
【００１８】
余命別サブ領域２０３はオブジェクト２０４を含み、Ｊａｖａヒープ２０１の外部に領域管理テーブル２０７を有する。オブジェクト２０４はＪａｖａヒープ２０１の外部に余命管理テーブル２０８を持つ。余命不明領域２０２や超長余命オブジェクト領域２０５も余命別サブ領域と同様にオブジェクト２０４を管理する。なお、超長余命オブジェクト領域２０５は、余命別サブ領域２０３の１つとして生成してもよい。
【００１９】
主メモリ１２はまた、Ｊａｖａプログラム２０６が経験した全ＧＣ回数２０９やＧＣの平均時間間隔である平均ＧＣ間隔２１０を含む。全ＧＣ回数２０９および平均ＧＣ間隔２１０の初期値は「０」である。さらに、主メモリ１２はＪａｖａヒープ２０１が用いる最大メモリ量の目安となる目標メモリ使用量２１２を含む。主メモリ１２はさらに、非常に長い余命を持つ超長余命オブジェクトの余命の最小値となる余命閾値２１１および超長余命オブジェクト領域２０５が経験したＧＣ回数である超長余命オブジェクト領域ＧＣ経験回数２１３を含む。超長余命オブジェクト領域ＧＣ経験回数２１３の初期値は０である。
【００２０】
図３は、領域管理テーブル２０７の構成例を示す。
領域管理テーブル２０７は余命別サブ領域２０３のオブジェクトを管理するものであり、余命別サブ領域２０３の余命上限値、余命下限値、余命別サブ領域２０３の余命、前回および今回ＧＣ直前に余命別サブ領域２０３に含まれるオブジェクト２０４の総量、等の各情報を含んで構成される。
余命上限値と余命下限値は、余命別サブ領域２０３に含まれるオブジェクト２０４の余命の上限と下限を決める。余命別サブ領域２０３に含まれるオブジェクト２０４の余命は、余命下限値以上かつ余命上限値未満であると定義する。なお余命上限値および余命下限値の決め方については後述する。
【００２１】
図４は、余命管理テーブル２０８の構成例を示す。
余命管理テーブル２０８はオブジェクトの余命を管理するものであり、オブジェクト２０４の生成コンテキスト、生成時刻、寿命、余命、ＧＣ経験回数、等の各情報を含んで構成される。生成コンテキストとは、例えば、オブジェクト２０４が生成されたプログラム上の位置や、オブジェクト２０４が生成された時点の関数呼び出しの順序関係を表す関数スタックフレーム列や、それらの組み合わせ等を示す情報である。オブジェクト２０４の寿命、余命の計算方法については図１０を参照して後述する。
【００２２】
ＧＣ経験回数は、オブジェクト２０４がそれまでに経験したＧＣの回数である。このＧＣの回数には、オブジェクト２０４が余命別サブ領域２０３内にあるため実行されなかったＧＣの回数も含まれる。ＧＣ経験回数の初期値は「０」である。超長余命オブジェクト領域２０５内にあるオブジェクト２０４は、ＧＣ経験回数は使わない。
【００２３】
次に、図５のフローチャートを参照して、Ｊａｖａ仮想マシンの処理、即ちＪａｖａ仮想マシン１０がＪａｖａプログラム２０６を実行する際の処理動作について説明する。
まず、管理者による入力装置１４の操作によって、目標メモリ使用量２１２および余命閾値２１１を入力装置１４から読み込む（Ｓ５０１）。ここで、余命閾値２１１は、超長余命オブジェクトの余命の下限値を意味するので、大きな自然数（例えば１０００）であることが望ましい。次に、領域初期分割（Ｓ５０２）を実行する。ここでは、Ｊａｖａヒープ２０１を、余命不明領域２０２と、１つ以上の余命別サブ領域２０３と、超長余命オブジェクト領域２０５に分割する。なお、領域初期分割（Ｓ５０２）については図６を参照して後述する。
【００２４】
次にＪａｖａプログラム実行（Ｓ５０３）を実行する。この処理については、図７を参照して後述する。次にＪａｖａプログラム２０６の実行中にＪａｖａヒープ２０１の空き領域がなくなったかどうか判定する（Ｓ５０４）。メモリの空き領域が無くなったとは、次に確保するオブジェクト２０４のサイズが、Ｊａｖａヒープ２０１の空き領域のサイズを上回っていることを意味する。この判定の結果、空き領域が無くなった場合（Ｓ５０４：Ｙｅｓ）、ＧＣ処理（Ｓ５０５）を実行する。そしてＧＣ処理Ｓ５０５の実行が終わったら、Ｊａｖａプログラム実行Ｓ５０３に戻ってＪａｖａプログラム２０６の実行を継続する。なお、ＧＣ処理Ｓ５０５については、図８を参照して後述する。
【００２５】
一方、判定の結果、空き領域が無くなっていない場合（Ｓ５０４：Ｎｏ）、プログラムが終了したかどうか判定して（Ｓ５０６）、終了していれば（Ｓ５０６：Ｙｅｓ）実行を終了する。一方、プログラムが終了していなければ（Ｓ５０６：Ｎｏ）、Ｊａｖａプログラム実行Ｓ５０３に戻ってＪａｖａプログラム２０６の実行を継続する。
【００２６】
領域の分割は、Ｊａｖａヒープ２０１から最初に余命不明領域２０２と、余命別サブ領域２０３と、超長余命オブジェクト領域２０５を作成する領域初期分割Ｓ５０２（図６）と、実行中に分割を切り直す処理である再配置処理Ｓ１１０３（図１２）および余命別サブ領域分割融合Ｓ１４０３（図１５）の３つの処理で行われる。なおここで、領域の分割とは、Ｊａｖａヒープ２０１の領域を物理的又は論理的に分割するという意味に限らず、Ｊａｖａヒープ内に各領域２０３〜２０５を論理的に確保する或いは規定する意味で用いる。
【００２７】
図６は、領域初期分割Ｓ５０２の処理動作を示す。
まず、Ｊａｖａヒープ２０１を２つに分割し、一方を余命不明領域２０２とする（Ｓ６０１）。分割された他方を仮に残り領域Ｘ１と呼ぶことにする。次に、この残り領域Ｘ１を分割して、分割した一方を超長余命オブジェクト領域２０５とする（Ｓ６０２）。領域Ｘ１の分割された他方を仮に残り領域Ｘ２と呼ぶことにする。次に、入力装置１４から、余命上限値および余命下限値の入力があるか判断する（Ｓ６０３）。その結果、それらの入力がなければ（Ｓ６０３：Ｎｏ）、領域分割の処理を終了する。一方、入力があれば（Ｓ６０３：Ｙｅｓ）、入力装置１４から入力される余命上限値および余命下限値を読み込む（Ｓ６０４）。
【００２８】
次に、Ｊａｖａヒープの残り領域Ｘ２を分割して、一方を余命別サブ領域２０３とする。また、この余命別サブ領域２０３について領域管理テーブル２０７を作成して、先ほど入力された余命上限値と余命下限値、および余命を領域管理テーブル２０７に設定する（Ｓ６０５）。
【００２９】
ここで、入力する余命上限値および余命下限値は、重ならないように隙間なく設定することが望ましい。例えば、余命別サブ領域１番の余命上限値が「３」ならば、余命別サブ領域２番の余命下限値は「３」のごとく設定する。「３」が重なっているように見えるかもしれないが、余命別サブ領域２０３は余命下限値「以上」かつ余命上限値「未満」の余命を持つオブジェクト２０４を配置するので、複数領域で余命が重なることはない。もし、余命が重なっている場合は、重なりがないように修正するか、重なりが存在するまま余命別サブ領域２０３を生成し、オブジェクト２０４の配置時に、余命が同じオブジェクトの総量から推定される領域サイズや推定処理時間に基づいて、該当する余命範囲を持つ適切な余命別サブ領域２０３に配置する。余命別サブ領域２０３の余命は余命上限値と同一とする。次に処理Ｓ６０３に戻って更に入力があるか調べ、入力があった場合は処理Ｓ６０４及びＳ６０５を繰り返す。
【００３０】
図７は、Ｊａｖａプログラム実行Ｓ５０３の処理を示す。
まず、実行中のＪａｖａプログラム２０６がオブジェクト（ｏｂｊ）生成処理であるか判断する（Ｓ７０１）。その結果、オブジェクト生成処理でない場合は（Ｓ７０１：Ｎｏ）、そのまま通常の処理を実行して（Ｓ７０３）、Ｊａｖａプログラム実行５０を終了する。
【００３１】
一方、オブジェクト生成処理であった場合は（Ｓ７０１：Ｙｅｓ）、オブジェクト２０４を生成するとともに余命管理テーブル２０８を生成して（Ｓ７０２）、余命管理テーブル２０８に生成コンテキスト、生成時刻、余命を設定する。生成コンテキストが同じであるオブジェクトが既にＪａｖａヒープ２０１中にある場合は、そのオブジェクトの寿命を今回生成したオブジェクトの寿命として設定する。また、今回生成したオブジェクトの余命を寿命と同じ値に設定する。寿命が分らない場合は、寿命、余命ともに不明とする（Ｓ７０４）。
【００３２】
次にオブジェクト２０４の余命を判断する（Ｓ７０５）。その結果、余命が不明の場合は（Ｓ７０５：Ｙｅｓ）、余命不明領域２０２にオブジェクト２０４を配置し（Ｓ７０６）、Ｊａｖａプログラム実行Ｓ５０３を終了する。一方、生成コンテキストから余命が分っている場合は（Ｓ７０５：Ｎｏ）、処理Ｓ７０７に進む。処理Ｓ７０７では、オブジェクト２０４の余命が余命閾値２１１より小さいか調べ、その結果小さいならば（Ｓ７０７：Ｙｅｓ）、オブジェクト２０４の余命が余命下限値以上かつ余命上限値未満である余命別サブ領域２０３に配置する。一方、オブジェクト２０４の余命が余命閾値２１１より大きい場合は（Ｓ７０７：Ｎｏ）、オブジェクト２０４を超長余命オブジェクト領域２０５に配置して（Ｓ７０９）、終了する。
【００３３】
図８は、ＧＣ処理Ｓ５０５の処理を示す。
まず、全ＧＣ回数２０９を「１」だけインクリメントする（Ｓ８０１）。次に、平均ＧＣ間隔２１０を計算する（Ｓ８０２）。平均ＧＣ間隔２１０は、現在時刻とプログラム開始時刻の差分を、全ＧＣ回数２０９で割った値と定義する。次に、Ｊａｖａヒープ２０１中にある余命不明領域２０２と全ての余命別サブ領域２０３と超長余命オブジェクト領域２０５を未処理であると印をつける（Ｓ８０３）。
【００３４】
次に、未処理の領域が残っているか判断する（Ｓ８０４）。未処理領域が無ければ（Ｓ８０４：Ｎｏ）、ＧＣ処理を終了する。一方、未処理の領域が残っていれば（Ｓ８０４：Ｙｅｓ）、それが余命不明領域２０２であるか判断する（Ｓ８０５）。そして未処理の領域が余命不明領域２０２であれば（Ｓ８０７：Ｙｅｓ）、領域毎処理Ｓ８０６を実行して、その後余命不明領域２０２を処理済みと印をつけて（Ｓ８１０)、処理Ｓ８０４に戻る。なお、領域毎処理Ｓ８０６については、図９を参照して後述する。
【００３５】
上記未処理の領域が余命不明領域２０２でなければ（Ｓ８０５：Ｎｏ）、未処理の領域が余命別サブ領域２０３であるか判断する（Ｓ８０７）。その結果、余命別サブ領域２０３であれば（Ｓ８０７：Ｙｅｓ）、余命別サブ領域用処理Ｓ８０９を実行して（Ｓ８０９）、その後余命別サブ領域１００を処理済みと印をつけ（Ｓ８１０)、処理Ｓ８０４に戻る。一方、余命別サブ領域２０３でなければ（Ｓ８０７：Ｎｏ）、超長余命オブジェクト領域用処理Ｓ８０８を実行して、その後超長余命オブジェクト領域２０５を処理済みと印をつけ（Ｓ８１０）、処理Ｓ８０４に戻る。なお、超長余命オブジェクト領域用処理Ｓ８０８及び余命別サブ領域用処理Ｓ８０９については、図１７及び図１４を参照して後述する。
【００３６】
図９は、領域毎処理Ｓ８０６を示す。
まず、オブジェクト余命計算Ｓ９０１を実行して、次に領域内オブジェクト量を計算して領域管理テーブル２０７の今回ＧＣ直前の領域内オブジェクト量フィールドに登録する（Ｓ９０２）。領域内オブジェクト量は、領域が持つ全てのオブジェクトのサイズを加算すれば求まる。次にＧＣ実行して（Ｓ９０３）、最後にオブジェクト再配置を実行する（Ｓ９０４）。なお、ＧＣ実行（Ｓ９０３）は、非特許文献１で述べられているような、例えばコピーＧＣやマーク・スイープＧＣ、を用いることで実現できる。なお、オブジェクト余命計算Ｓ９０１及びオブジェクト再配置Ｓ９０４の処理については、図１０及び図１１を参照して後述する。
【００３７】
図１０は、オブジェクト余命計算Ｓ９０１の処理を示す。
最初に、処理中の領域内の全てのオブジェクトを未処理状態にする。即ち未処理である旨の印をつける（Ｓ１００１）。その後、オブジェクト毎の処理に移る。まず、処理中の領域内に未処理のオブジェクト２０４があるかを判断する（Ｓ１００２）。その結果、未処理のオブジェクト２０４がなければ（Ｓ１００２：Ｎｏ）、オブジェクト余命計算の処理を終了する。
【００３８】
一方、未処理のオブジェクト２０４があれば（Ｓ１００２：Ｙｅｓ）、オブジェクトの生死判定でそのオブジェクト２０４が直後のＧＣで不要と判定されるのであれば、そのオブジェクト２０４の寿命を計算する（Ｓ１００３）。寿命は、余命管理テーブル２０８に登録されたオブジェクト２０４の生成時刻と平均ＧＣ間隔２１０を用いて、現在時刻と生成時刻の差分を平均ＧＣ間隔２１０で割った値として定義される。ただし、寿命の定義はこれに限る訳ではなく、特定のプログラム点をプログラムが通過した時刻の差分を平均ＧＣ間隔２１０で割った値など、さまざまな例が考えられる。計算された寿命は、オブジェクト２０４の余命管理テーブル２０８に登録される。
【００３９】
次に、オブジェクト２０４と生成コンテキストが同じオブジェクトのうち、寿命が計算されていないものをＪａｖａヒープ２０１中から探して、その寿命をオブジェクト２０４の寿命と同じ値にする（Ｓ１００４）。そして、オブジェクト２０４の余命管理テーブルに登録されたＧＣ経験回数の値を「１」だけインクリメントする（Ｓ１００５）。
【００４０】
次に、寿命が登録されているオブジェクト２０４に対して、余命を計算する（Ｓ１００６）。余命は、先ほど計算した寿命と、オブジェクト２０４の余命管理テーブル２０８に登録されたＧＣ経験回数の差分と定義する。計算された余命は、オブジェクト２０４の余命管理テーブル２０８に登録される。最後に、オブジェクト２０４に処理済みの印をつけ（Ｓ１００７）、処理Ｓ１００２に戻る。
【００４１】
図１１は、オブジェクト再配置Ｓ９０４の処理を示す。
まず、処理中の領域内の全てのオブジェクトを未処理であると印をつける（Ｓ１１０１）。次に、領域内に未処理のオブジェクト２０４があるか判断する（Ｓ１１０２）。その結果、未処理のオブジェクト２０４がなければ（Ｓ１１０２：Ｎｏ）、オブジェクト再配置を終了する。一方、未処理のオブジェクト２０４があれば（Ｓ１１０２：Ｙｅｓ）、オブジェクトの再配置処理を行い（Ｓ１１０３）、オブジェクトに処理済みの印をつけて（Ｓ１１０４）、処理Ｓ１１０２に戻る。なお、オブジェクトの再配置処理Ｓ１１０３については図１２を参照して後述する。
【００４２】
図１２は、再配置処理Ｓ１１０３を示す。
この処理はＧＣ実行Ｓ９０３の直後に行われる処理であるから、本処理に至るオブジェクト２０４は、ＧＣを生き残ったオブジェクトである。すなわち、余命の推定に失敗したオブジェクトである。
【００４３】
そこで最初に、オブジェクト２０４の余命を再計算する（Ｓ１２０１)。再計算は、オブジェクト２０４の今までの余命に、オブジェクト２０４のＧＣ経験回数を加えたものを、新たな余命とする。更に、Ｊａｖａヒープ２０１中の生成コンテキストが同じオブジェクト２０４の余命にも、このＧＣ経験回数を加える。これにより、ＧＣを経験した回数が多いオブジェクト２０４ほど、より余命が長くなるという傾向を表現できる。
【００４４】
次に、オブジェクト２０４の余命が余命閾値２１１以上であるか判断する（Ｓ１２０２）。その結果、余命閾値２１１以上であれば（Ｓ１２０２：Ｙｅｓ）、処理中の領域を処理中のオブジェクト２０４を含む領域とそれを含まない領域に分割して、オブジェクトを含む領域を超長余命オブジェクト領域２０５と融合させて（Ｓ１２０３）、再配置処理を終了する。
【００４５】
一方、オブジェクト２０４の余命が余命閾値２１１以上でなければ（Ｓ１２０２：Ｎｏ）、処理中のオブジェクト２０４の余命を含む余命別サブ領域を探す（Ｓ１２０４）。ここで「余命を含む」とは、余命の値が、余命別サブ領域の余命上限値未満かつ余命下限値以上であるという意味である。次に、もし条件に合致する余命別サブ領域が見つかったかを判定する（Ｓ１２０５）。その結果、余命別サブ領域が見つかれば（Ｓ１２０５：Ｙｅｓ）、条件に合致する余命別サブ領域の中から１つを選んで、そこに処理中のオブジェクト２０４を移動させる（Ｓ１２０６）。この選び方は、任意の一つを選んでもよいし、最初に見つかったものを選んでもよいし、オブジェクト２０４の余命と最も近い余命上限値をもつ余命別サブ領域を選んでもよい。この処理Ｓ１２０６を実行した後に再配置処理を終了する。
【００４６】
上記判定Ｓ１２０５において、条件に合致する余命別サブ領域が見つからなければ（Ｓ１２０５：Ｎｏ）、処理中の領域を、オブジェクト２０４を含む領域とそれを含まない領域に分割する（Ｓ１２０７)。オブジェクト２０４を含む領域は、新しい余命別サブ領域２０３となる。最後に、オブジェクト２０４を含む新しい余命別サブ領域２０３の余命上限値および余命下限値を計算して（Ｓ１２０８）、再配置処理を終了する。なお、余命上下限値再計算Ｓ１２０８の処理については図１３を参照して後述する。
【００４７】
図１３は、余命上下限値計算Ｓ１２０８の処理を示す。
本処理の対象となる余命別サブ領域２０３は、オブジェクト２０４を１つだけ持つ領域である。この処理では、このオブジェクト２０４の余命を用いて、余命別サブ領域２０３の余命上限値をオブジェクト２０４の余命に「１」を加えたもの（Ｓ１３０１）、余命下限値をオブジェクト２０４の余命（Ｓ１３０２）、余命別サブ領域２０３の余命を余命上限値と設定する（Ｓ１３０３）。
【００４８】
ここで、余命上限値をオブジェクト２０４の余命に「１」を加えた値にするのは、余命別サブ領域２０３に含まれるオブジェクトの余命は、余命下限値以上かつ余命上限値未満と定義したからである。また、Ｊａｖａヒープ２０１中での現在のメモリ使用量と目標メモリ使用量２１２の差分が小さいときには、余命別サブ領域２０３の余命上限値をオブジェクト２０４の余命に「１」より大きな値を加えたものに設定してもよい。これは、一度に回収できるメモリ量を増やし、Ｊａｖａヒープ使用量を目標メモリ使用量２１２以下に保つための方法である。
【００４９】
図１４は、余命別サブ領域用処理Ｓ８０９を示す。
最初に、領域管理テーブル２０７にある今回ＧＣ直前の領域内オブジェクト量の値を、前回ＧＣ直前の領域内オブジェクト量フィールドに設定する（Ｓ１４０１）。次に、余命別サブ領域２０３の余命が「１」未満であるかを判断する（Ｓ１４０２）。その結果、条件を満たす場合は（Ｓ１４０２：Ｙｅｓ）、領域毎処理を実行する（Ｓ１４０４）。領域毎処理Ｓ１４０４については既に述べた。
【００５０】
一方、上記条件が満たされない場合には（Ｓ１４０２：Ｎｏ）、非ＧＣ領域毎処理を実行する（Ｓ１４０３）。領域毎処理Ｓ１４０４または非ＧＣ領域毎処理Ｓ１４０３が終了した後、余命別サブ領域分割融合Ｓ１４０５の処理を実行する。その後、余命別サブ領域用処理を終了する。なお、非ＧＣ領域毎処理Ｓ１４０３及び余命別サブ領域分割融合Ｓ１４０５の処理については、図１５及び図１６を参照して後述する。
【００５１】
図１５は、非ＧＣ領域毎処理Ｓ１４０３を示す。
本処理では、ＧＣにより回収対象外領域のオブジェクト２０４の余命が変わった場合に、オブジェクト２０４の所属する領域を適切なものに変更し、メモリ領域の使用効率を向上させる。
そのため、最初に、オブジェクト余命計算Ｓ１５０１の処理を実行し、その後にオブジェクト再配置Ｓ１５０２の処理を実行して、非ＧＣ領域毎処理Ｓ１４０３の処理を終了する。なお、オブジェクト余命計算Ｓ１５０１およびオブジェクト再配置Ｓ１５０２については既に説明した。
【００５２】
図１６は、余命別サブ領域分割融合Ｓ１４０５の処理を示す。
まず、目標メモリ使用量２１２をMmax、前回、今回、次回のＧＣ直前のメモリ使用量をそれぞれM(n−2)、M(n−1)、M(n)とする。ここで、nは「３」以上の自然数とするが、事前に実行した際のメモリ使用量データやユーザ提供のデータを利用してもよい。その際のnは任意の自然数となる。M(n−2)、M(n−1)は、領域管理テーブル２０７に登録された前回および今回ＧＣ直前の領域内オブジェクト量である。ＧＣ直前のメモリ使用量が時間に対して線形近似できる場合かつＧＣ間隔が比較的一様ならば、次回のＧＣ直前のメモリ使用量M(n)は、式（１）で表現できる。
【００５３】
M(n)＝M(n−1)＋(M(n−1)−M(n−2))    （１）
すなわち、過去２回のＧＣ直前のメモリ使用量の差分の分だけ、次回ＧＣ直前のメモリ使用量が増減すると推測可能である。次に、余命が短い順に並べた余命別サブ領域S(j)が持つオブジェクト量をA(j)とする。なおjは余命そのものではなく、余命の短い順に並べた際の順序を表すだけである。A(j)は、余命別サブ領域S(j)が持つオブジェクトの量を合計すれば求めることができる。そして、A(1)＜M(n)−Mmaxかどうか判断する（Ｓ１６０１）。これは、一番余命の短い余命別サブ領域２０３を１つＧＣするだけでＪａｖａヒープ２０１のメモリ使用量を目標メモリ使用量２１２以下に保てるかどうかという意味である。
【００５４】
処理Ｓ１６０１において条件が成立しなければ（Ｓ１６０１：Ｎｏ）、余命別サブ領域分割融合Ｓ１４０５の処理を終了する。一方、条件が成立したら（Ｓ１６０１：Ｙｅｓ）、すなわち一番余命が短い余命別サブ領域２０３を１つだけＧＣしてもＪａｖａヒープ２０１のメモリ使用量を目標メモリ使用量２１２以下に保てないのであれば、複数の余命別サブ領域２０３をＧＣしなくてはならない。そこで次に、式（２）の最小のmを見つける（Ｓ１６０２）。
【００５５】
A(1)＋・・・＋A(m)≧M(n)−Mmax    （２）
これは、次回のＧＣ直前のメモリ使用量M(n)が、目標メモリ使用量Mmaxを超えないようにするために必要な、必要最小限の領域回収量を求めるための式である。これ以上の量を回収してもよいが、ＧＣによるプログラム停止時間をできるだけ短くするために、必要最小限とした。
【００５６】
次に、余命別サブ領域S(m)に含まれるオブジェクト２０４の余命別のオブジェクト量を、kを余命とした時にO(m,k)とし、式（３）の最小のkhを見つける（Ｓ１６０３）。
【００５７】
A(1)＋・・・＋A(m−1)＋O(m,k1)＋・・・＋O(m,kh)≧M(n)−Mmax    （３）
ここで、最小のkhとしたのも上記と同じ理由である。O(m,k)は、余命別サブ領域S(m)が持つオブジェクトの量を余命k別に集計すれば求めることができる。次に、余命別サブ領域S(m)を分割して前記オブジェクトの余命がk1〜khである領域S(m)’とそれ以外の領域S(m)”に分ける（Ｓ１６０４）。そして、余命別サブ領域S(1)〜S(m−1)とS(m)’を融合して余命別サブ領域S(1)’とし（Ｓ１６０５）、S(1)’とS(m)”の余命上限値および余命下限値および領域の余命を設定する（Ｓ１６０６）。
【００５８】
余命上限値は領域中にあるオブジェクト２０４の余命最大値に「１」を加えたもの、余命下限値は領域中にあるオブジェクト２０４の余命最小値、領域の余命は余命上限値に等しいものとする。これにより、次回のＧＣでは余命別サブ領域S(1)’を回収するだけで、目標メモリ使用量２１２を超えなくなることが期待できる。また、余命別サブ領域を１つだけ回収すればよいので、ＧＣ停止時間が短くなることが期待できる。なお前述の説明では、余命別サブ領域S(1)〜S(m)に該当する領域を一つにまとめる方法を説明したが、余命別サブ領域S(m＋1)〜S(n)についても同様のアルゴリズムで領域分割・融合を実施してもよい。
【００５９】
図１７は、超長余命オブジェクト領域用処理Ｓ８０８を示す。
本処理は、超長余命オブジェクト領域を、余命閾値の回数につき１回だけＧＣすることにより、死んだ超長余命オブジェクトを回収し、メモリ使用効率を向上させる。
【００６０】
最初に、超長余命オブジェクト領域ＧＣ経験回数２１３を「１」だけインクリメントする（Ｓ１７０１）。次に、超長余命オブジェクト領域ＧＣ経験回数２１３を余命閾値２１１で割った余り（剰余）が「０」であるか判断する（Ｓ１７０２）。その結果、「０」でなければ（Ｓ１７０１：Ｎｏ）、超長余命オブジェクト領域用処理Ｓ８０８を終了する。
【００６１】
一方、「０」であれば（Ｓ１７０２：Ｙｅｓ）、オブジェクト余命計算を実行し（Ｓ１７０３）、次にＧＣ実行して（Ｓ１７０４）、超長余命オブジェクト領域用処理Ｓ８０８を終了する。なお、オブジェクト余命計算Ｓ１７０１およびＧＣ実行Ｓ９０３の処理については既に説明した。
【００６２】
以上のように、本実施例によれば、余命の近いデータ(オブジェクト)を余命別サブ領域に集め、余命が尽きるまで余命別サブ領域のガベージコレクションを行わないことで、ガベージコレクションによるプログラム停止時間を短縮することが可能となる。
【００６３】
なお、本発明は、上記実施例に限定されるものではなく、その趣旨を逸脱しない範囲で種々の変形、応用して実施し得る。
【００６４】
例えば、上記好ましい実施例においては、余命不明領域に配置されたオブジェクトについてはＧＣを行い、ヒープに格納されたオブジェクトの余命の計算の結果、余命の判明したオブジェクトをあてはまる余命別サブ領域に集めて配置し、余命別サブ領域の余命が尽きるまで余命別サブ領域のＧＣを行わないとしている。しかし代案例によれば、余命別サブ領域に集めて配置されたオブジェクトに対して実施するＧＣを最後の１回のみ実施するのでは無く、適度に複数回ＧＣを実行してもよい。少なくとも余命不明領域に配置されたオブジェクトに対するＧＣの実行回数よりも少ない回数だけ、余命別サブ領域に配置されたオブジェクトのＧＣを実行するようにすれば、少なくとも従来技術に比べてＧＣの実行回数を減らすことができ、プログラムの停止時間を短縮することが可能である。この代案例も本発明の趣旨を適用した範囲と言える。
【００６５】
また他の例について言えば、図３及び図７を参照した、領域の分割処理では、余命不明領域、超長余命オブジェクト領域、余命別サブ領域や、領域管理テーブル及び余命管理テーブルを順次に生成している。しかし、代案例においては、これらの領域やテーブルを予め作成して、Ｊａｖａヒープ２０１又は主メモリに用意しておいてもよい。
【００６６】
例えば、上記実施例では、余命別サブ領域を順次分割して生成する例を記した。代案例によれば、余命サブ領域を予め所定の複数（ｎ個）用意しておき、そのｎ個の余命管理領域の範囲内で、オブジェクトの余命iに応じて余命別サブ領域iを割り振る（ｎ−１）個の余命管理領域と、１つの超長余命オブジェクト領域を規定するようにしてもよい。
【００６７】
また、図３及び図４に示した領域管理テーブル２０７や余命管理テーブル２０８は一例であって、この構成に限定されない。また、余命の上限値/下限値の説明において「以上」や「未満」を使用しているが、これは一例であり、他の定義、例えば「超える」「以下」を用いてもよい。
【符号の説明】
【００６８】
１：計算機                        １０：Ｊａｖａ仮想マシン
１１：プロセッサ                  １２：主メモリ
２０１：Ｊａｖａヒープ            ２０２：余命不明領域
２０３：余命別サブ領域            ２０４：オブジェクト
２０５：超長余命オブジェクト領域  ２０６：Ｊａｖａプログラム
２０７：領域管理テーブル          ２０８：余命管理テーブル
２０９：全ＧＣ回数                ２１０：平均ＧＣ間隔
２１１：余命閾値                  ２１２：目標メモリ使用量
２１３：超長余命オブジェクト領域ＧＣ経験回数
【図１】
2014182772.tif 000003
【図２】
2014182772.tif 000004
【図３】
2014182772.tif 000005
【図４】
2014182772.tif 000006
【図５】
2014182772.tif 000007
【図６】
2014182772.tif 000008
【図７】
2014182772.tif 000009
【図８】
2014182772.tif 000010
【図９】
2014182772.tif 000011
【図１０】
2014182772.tif 000012
【図１１】
2014182772.tif 000013
【図１２】
2014182772.tif 000014
【図１３】
2014182772.tif 000015
【図１４】
2014182772.tif 000016
【図１５】
2014182772.tif 000017
【図１６】
2014182772.tif 000018
【図１７】
2014182772.tif 000019