(57)【要約】  仮想マシン、Ｊａｖａ仮想マシン、又は他の実行時環境における、仮想マシンメモリのガベージコレクション時間を改善するためのシステム及び方法。ＪＶＭ、又はその中で動作するガベージコレクタは、メモリ空間の領域について、その領域内のソフトウエア・オブジェクトのガベージコレクションの停止時間の合計を推定し、ガベージコレクションの停止時間の合計が、高い程度の確率で、目標停止時間制限未満となるように、ガベージコレクション・プロセスを制御することができる。予め選択されたコンパクション領域は、プレコンパクト化され、コンパクション時間を目標制限内に保持することができる。ガベージコレクタは又、最終マーキングに必要な時間を予測し、予測最終マーキング時間が停止時間制限内となるまで、プレクリーニングを繰り返すことができ、メモリサブシステムに入り、又は離れるときに、ガベージコレクタ作業をするためにアプリケーション・ワーカースレッドをリダイレクトすることにより、停止時間を改善することができる。【選択図】図４
2009501384.tif 000002
【特許請求の範囲】
【請求項１】
仮想マシン環境における予測可能な結果のガベージコレクションのためのシステムであって、
ソフトウエア・アプリケーションを実行するための仮想マシンと、
前記ソフトウエア・アプリケーションの一部としてのソフトウエア・オブジェクト及びポインタを記憶するに際して前記仮想マシンによる使用のためのメモリ空間と、
前記メモリ空間の領域について、前記領域内のソフトウエア・オブジェクトのガベージコレクションの前記停止時間の合計を推定し、且つ前記ガベージコレクションの停止時間の合計が目標停止時間制限未満となるように、前記ガベージコレクション・プロセスを制御するガベージコレクタと、
を含むことを特徴とするシステム。
【請求項２】
前記ガベージコレクタは、統計に基づいて、前記ガベージコレクションの停止時間の合計を推定することを特徴とする請求項１に記載のシステム。
【請求項３】
前記ガベージコレクタは、前記ガベージコレクションの停止時間の合計が、統計的確率の程度内で、目標停止時間制限未満となるように、前記ガベージコレクション・プロセスを制御することを特徴とする請求項２記載のシステム。
【請求項４】
前記メモリ空間の領域は、コンパクション領域であることを特徴とする請求項１記載のシステム。
【請求項５】
前記ガベージコレクタは、前記コンパクション領域に割り当てられた使用可能なコンパクション時間を前記目標停止時間制限の分数値に設定することを特徴とする請求項４記載のシステム。
【請求項６】
マーキングステップ中、前記コンパクション領域内のソフトウエア・オブジェクトを指すあらゆるポインタを判定し、そのように判定されたポインタが、前記指されるソフトウエア・オブジェクトのアドレス、及び前記ソフトウエア・オブジェクトを指すポインタの位置を表すキーと共に、テーブルに記憶されることを特徴とする請求項４記載のシステム。
【請求項７】
ワーカースレッド、及びワーカースレッドによりポインタが更新された回数を示す値を含むスレッドローカル変数を更に含み、
前記スレッドローカル変数は、前記ガベージコレクションの停止時間の合計を推定する際に、前記ガベージコレクタにより使用されることを特徴とする請求項６記載のシステム。
【請求項８】
前記スレッドローカル変数は、前記次のガベージコレクション中に前記ガベージコレクタにより処理されなければならないダーティーカードの数を示すことを特徴とする請求項７記載のシステム。
【請求項９】
前記ガベージコレクタは、前記ソフトウエア・オブジェクトのプレクリーニングステップを選択的に繰り返し、
前記プレクリーニングステップ中、前記ガベージコレクタは、前記ワーカースレッドによりポインタが何回更新されたかを示す、各ワーカースレッドのスレッドローカル変数を計算することを特徴とする請求項１記載のシステム。
【請求項１０】
前記停止時間の合計は、最終マーキング時間の統計的推定値に基づくものであり、
前記最終マーキング時間の推定値に応じて、前記ガベージコレクタにより、前記プレクリーニングステップが繰り返されるか否かが決定されることを特徴とする請求項９記載のシステム。
【請求項１１】
前記メモリ空間の領域における前記ソフトウエア・オブジェクトのガベージコレクションの停止時間の合計の統計的推定値は、前記ソフトウエア・アプリケーションの実行の前に前記システムにエンコードされた情報に基づくものであることを特徴とする請求項２記載のシステム。
【請求項１２】
前記メモリ空間の領域における前記ソフトウエア・オブジェクトのガベージコレクションの停止時間の合計の統計的推定値は、前記ソフトウエア・アプリケーションの実行中に前記システムにより収集された実行時間情報に基づくものであることを特徴とする請求項２記載のシステム。
【請求項１３】
コンパクションステップ中、前記コンパクションの停止時間の目標時間制限に達した場合には、前記コンパクションがアボートされることを特徴とする請求項１記載のシステム。
【請求項１４】
コンパクションステップ中、前記ソフトウエア・オブジェクトを指すポインタ位置の数が閾値を超えた場合には、前記コンパクションステップの一部として、前記ソフトウエア・オブジェクトは移動させられないことを特徴とする請求項１記載のシステム。
【請求項１５】
前記仮想マシンは、Ｊａｖａ仮想マシンであることを特徴とする請求項１記載のシステム。
【請求項１６】
仮想マシン環境における予測可能な結果のガベージコレクションのための方法であって、
ソフトウエア・アプリケーションを実行するための仮想マシンを用意するステップと、
前記ソフトウエア・アプリケーションの一部としてのソフトウエア・オブジェクト及びポインタを記憶するに際して前記仮想マシンによる使用のためのメモリ空間を用意するステップと、
ガベージコレクタを使用して、前記メモリ空間内のソフトウエア・オブジェクトのガベージコレクションを制御するステップと、
を含み、
前記ガベージコレクタは、前記メモリ空間の領域について、前記領域内のソフトウエア・オブジェクトのガベージコレクションの前記停止時間の合計を推定し、且つ前記ガベージコレクションの停止時間の合計が目標停止時間制限未満となるように、前記ガベージコレクション・プロセスを制御することを特徴とする方法。
【請求項１７】
前記ガベージコレクタは、統計に基づいて、前記ガベージコレクションの停止時間の合計を推定することを特徴とする請求項１６に記載の方法。
【請求項１８】
前記ガベージコレクタは、前記ガベージコレクションの停止時間の合計が、統計的確率の程度内で、目標停止時間制限未満となるように、前記ガベージコレクション・プロセスを制御することを特徴とする請求項１７記載の方法。
【請求項１９】
前記メモリ空間の領域は、コンパクション領域であることを特徴とする請求項１６記載の方法。
【請求項２０】
前記ガベージコレクタは、前記コンパクション領域に割り当てられた使用可能なコンパクション時間を前記目標停止時間制限の分数値に設定することを特徴とする請求項１９記載の方法。
【請求項２１】
マーキングステップ中、前記コンパクション領域内のソフトウエア・オブジェクトを指すあらゆるポインタを判定し、そのように判定されたポインタが、前記指されるソフトウエア・オブジェクトのアドレス、及び前記ソフトウエア・オブジェクトを指すポインタの位置を表すキーと共に、テーブルに記憶されることを特徴とする請求項１９記載の方法。
【請求項２２】
ワーカースレッド、及びワーカースレッドによりポインタが更新された回数を示す値を含むスレッドローカル変数を使用するステップを更に含み、
前記スレッドローカル変数は、前記ガベージコレクションの停止時間の合計を推定する際に、前記ガベージコレクタにより使用されることを特徴とする請求項２１記載の方法。
【請求項２３】
前記スレッドローカル変数は、前記次のガベージコレクション中に前記ガベージコレクタにより処理されなければならないダーティーカードの数を示すことを特徴とする請求項７記載の方法。
【請求項２４】
前記ガベージコレクタは、前記ソフトウエア・オブジェクトのプレクリーニングステップを選択的に繰り返し、
前記プレクリーニングステップ中、前記ガベージコレクタは、前記ワーカースレッドによりポインタが何回更新されたかを示す、各ワーカースレッドのスレッドローカル変数を計算することを特徴とする請求項１６記載の方法。
【請求項２５】
前記停止時間の合計は、最終マーキング時間の統計的推定値に基づくものであり、
前記最終マーキング時間の推定値に応じて、前記ガベージコレクタにより、前記プレクリーニングステップが繰り返されるか否かが決定されることを特徴とする請求項２４記載の方法。
【請求項２６】
前記メモリ空間の領域における前記ソフトウエア・オブジェクトのガベージコレクションの停止時間の合計の統計的推定値は、前記ソフトウエア・アプリケーションの実行の前に前記方法にエンコードされた情報に基づくものであることを特徴とする請求項１７記載の方法。
【請求項２７】
前記メモリ空間の領域における前記ソフトウエア・オブジェクトのガベージコレクションの停止時間の合計の統計的推定値は、前記ソフトウエア・アプリケーションの実行中に前記方法により収集された実行時間情報に基づくものであることを特徴とする請求項１７記載の方法。
【請求項２８】
コンパクションステップ中、前記コンパクションの停止時間の目標時間制限に達した場合には、前記コンパクションがアボートされることを特徴とする請求項１６記載の方法。
【請求項２９】
コンパクションステップ中、前記ソフトウエア・オブジェクトを指すポインタ位置の数が閾値を超えた場合には、前記コンパクションステップの一部として、前記ソフトウエア・オブジェクトは移動させられないことを特徴とする請求項１６記載の方法。
【請求項３０】
前記仮想マシンは、Ｊａｖａ仮想マシンであることを特徴とする請求項１６記載の方法。
【請求項３１】
ソフトウエア・アプリケーションを実行するための仮想マシンを用意するステップと、
前記ソフトウエア・アプリケーションの一部としてのソフトウエア・オブジェクト及びポインタを記憶するに際して前記仮想マシンによる使用のためのメモリ空間を用意するステップと、
前記メモリ空間の領域について、前記領域内のソフトウエア・オブジェクトのガベージコレクションの前記停止時間の合計を推定し、且つ前記ガベージコレクションの停止時間の合計が目標停止時間制限未満となるように、前記ガベージコレクション・プロセスを制御するガベージコレクタを使用して、前記メモリ空間内のソフトウエア・オブジェクトのガベージコレクションを制御するステップと、
を実行時にコンピュータに実行させる、記録媒体に記録された命令を含むコンピュータ読み取り可能な記録媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に仮想マシン環境及び他の実行時環境に関し、特に仮想マシンメモリのガベージコレクション時間を改善するためのシステム及び方法に関する。
【背景技術】
【０００２】
仮想マシンは、異なる基底(underlying)コンピュータ・アーキテクチャ間でのソフトウエア・アプリケーションの移植性を可能とする抽象的コンピュータである。通常、仮想マシン（ＶＭ）は、特定のコンピュータ・ハードウエア・プラットフォーム及び／又はオペレーティング・システム上に実装される複合ソフトウエア製品である。更に、ＶＭは、ハードウエア・プラットフォームと、任意のその上で実行するコンパイルされたソフトウエア・アプリケーションとの間の一様な抽象層を提供する。仮想マシンは、Ｊａｖａ（登録商標）を含むある技術の移植性にとって不可欠である。Ｊａｖａ（登録商標）仮想マシン（ＪＶＭ）は、Ｊａｖａ（登録商標）プログラムが、どのようなハードウエア又はオペレーティング・システムに対しても独立してＪＶＭ上で実行されることを可能とする。市販のＪＶＭの例としては、サン・マイクロシステム社のSun Java（登録商標） Virtual Machine及びＢＥＡシステム社のJRockit Virtual Machineが挙げられる。
【０００３】
Ｊａｖａ（登録商標）、Ｃ＋＋、Ｐｅｒｌ及びＬｉｓｐといった言語の仮想マシンは、ＶＭ自体の一部としてガベージコレクション機能を含む。ガベージコレクションは、ＶＭが、実行時中に未使用のコンピュータ・メモリを解放する(reclaim)ことを可能とし、ソフトウエア・アプリケーション自身内のメモリ・クリーンアップの提供及び管理の負担のほとんどから解放するので、ＶＭの重要な機能である。ガベージコレクションの基本概念は、ソフトウエア・アプリケーションから現在到達可能なデータのすべてを発見し、次いでその他のすべてのデータを捨てることである。ソフトウエア・オブジェクトのために使用されるメモリを解放するために、プログラマーは、そのオブジェクトを指すあらゆるポインタを消去しなければならないだけである。ガベージコレクション・ロジック又はルーチン（ガベージコレクタとも呼ばれる）は、その後、そのオブジェクトがもはや到達可能でないことを検知し、メモリを解放する。
【０００４】
従来、Ｊａｖａ（登録商標）環境においては、ガベージコレクション中は、ガベージコレクタは、実行中のＪＶＭを停止し、必要な作業を行う。これは、ガベージコレクタ停止時間、又は単に停止時間と呼ばれる。停止時間は、アプリケーション・コードを用意するときに、ランダムな停止を予測することが難しいので、プログラマに対して問題を引き起こす。予測不可能な停止時間を伴うＪＶＭは、通信、物理プロセス又は警告システム用のリアルタイムシステムといった、厳しい時間的要求を伴うアプリケーションに使用することができない。対話アプリケーションといった緩和された要求を伴うアプリケーションも、期待される時間枠内にユーザに応答しなければ、依然として使用することができないと思われる。
【０００５】
ガベージコレクションの停止時間を改善するために、多くの研究がなされてきた。例えば、停止中に複数のプロセッサ上で並行してガベージコレクション・スレッドを実行することによって、停止時間を短縮することができる。ガベージコレクション・プロセスは又、多く実行される若い(young)コレクション（ＹＣ）段階と、めったに実行されない古い(old)コレクション段階（ＯＣ）とに分けられる世代別ガベージコレクションとして設計することができる。更に、ガベージコレクションの一部は、実行中のソフトウエア・アプリケーションと同時に実行し、短い停止で実行中のアプリケーションにより行われる変化に適応することができる。
【０００６】
上述のように、ガベージコレクションに使用される現在の技術は、通信、警告システム及び他のリアルタイムシステムといった厳しいタイミングを要求する環境及びソフトウエア・アプリケーションにおいては、不満足なものである。望まれるのは、仮想マシン内で予測可能且つ短い停止時間を可能とするガベージコレクション技術である。
【発明の開示】
【０００７】
ここに開示されるのは、仮想マシン（ＶＭ）又は他の実行時環境における予測可能な結果の(deterministic)ガベージコレクションのための、特にＪａｖａ（登録商標）仮想マシン（ＪＶＭ）を含むシステムにおいて使用するのためのシステム及び方法である。上述のように、ガベージコレクションに使用される現在の技術は、予測不可能な停止時間を有し、通信、警告システム及び他のリアルタイムシステムといった厳しいタイミングを要求する環境及びソフトウエア・アプリケーションにおいては、不満足なものである。本発明の実施形態は、停止時間が、高い程度の確率で、目標停止時間未満となるように、メモリをガベージコレクトするシステム及び方法を提供することにより、この問題に対処するものである。１つの実施形態によれば、本発明は、仮想マシン環境における予測可能な結果のガベージコレクションのためのシステムであって、ソフトウエア・アプリケーションを実行するための仮想マシンと、ソフトウエア・アプリケーションの一部としてのソフトウエア・オブジェクト及びポインタを記憶するに際して仮想マシンによる使用のためのメモリ空間と、メモリ空間の領域について、領域内のソフトウエア・オブジェクトのガベージコレクションの停止時間の合計を推定し、且つガベージコレクションの停止時間の合計が目標停止時間制限未満となるように制御するガベージコレクタとを含むことを特徴とするシステムを提供する。別の実施形態によれば、ＪＶＭは、予め選択されたコンパクション領域を部分的にコンパクト化し、コンパクション時間を停止時間制限内に保持することができる。別の実施形態によれば、ＪＶＭは、最終マーキングに必要案時間を予測し、予測最終マーキング時間が停止時間制限内となるまで、プレクリーニングを繰り返すことができる。別の実施形態によれば、ＪＶＭは、メモリサブシステムに入り、又は離れるときに、ガベージコレクタ作業をするためにアプリケーション・ワーカースレッドをリダイレクトすることにより、停止時間を改善することができる。実施形態は又、組み合わせられ、更に短い停止時間の確率を大きくすることができる。
【発明を実施するための最良の形態】
【０００８】
本特許文書の開示の一部は、著作権の保護の主張がなされる事項を含む。本著作権者は、何人に対しても本特許文書の複製又は特許商標庁における特許包袋又は記録の開示に対して異議を唱えないが、その他の点については、すべての著作権を留保する。
【０００９】
優先権の主張：
２００５年７月１５日に出願された「仮想マシン環境における予測可能な結果のガベージコレクションのためのシステム及び方法」という名称の米国特許出願第１１／１８２，１３７［代理人整理番号ＢＥＡＳ−０１８４５ＵＳ０］
【００１０】
ここに開示されるのは、仮想マシン（ＶＭ）又は他の実行時環境における予測可能な結果のガベージコレクションのための、特にＪａｖａ（登録商標）仮想マシン（ＪＶＭ）を含むシステムにおいて使用するのためのシステム及び方法である。上述のように、ガベージコレクションに使用される現在の技術は、予測不可能な停止時間を有し、通信、警告システム及び他のリアルタイムシステムといった厳しいタイミングを要求する環境及びソフトウエア・アプリケーションにおいては、不満足なものである。本発明の実施形態は、停止時間が、高い程度の確率で、目標停止時間未満となるように、メモリをガベージコレクトするシステム及び方法を提供することにより、この問題に対処するものである。１つの実施形態によれば、本発明は、仮想マシン環境における予測可能な結果のガベージコレクションのためのシステムであって、ソフトウエア・アプリケーションを実行するための仮想マシンと、ソフトウエア・アプリケーションの一部としてのソフトウエア・オブジェクト及びポインタを記憶するに際して仮想マシンによる使用のためのメモリ空間と、メモリ空間の領域について、領域内のソフトウエア・オブジェクトのガベージコレクションの停止時間の合計を推定し、且つガベージコレクションの停止時間の合計が目標停止時間制限未満となるように制御するガベージコレクタとを含むことを特徴とするシステムを提供する。別の実施形態によれば、ＪＶＭは、予め選択されたコンパクション領域を部分的にコンパクト化し、コンパクション時間を停止時間制限内に保持することができる。別の実施形態によれば、ＪＶＭは、最終マーキングに必要案時間を予測し、予測最終マーキング時間が停止時間制限内となるまで、プレクリーニングを繰り返すことができる。別の実施形態によれば、ＪＶＭは、メモリサブシステムに入り、又は離れるときに、ガベージコレクタ作業をするためにアプリケーション・ワーカースレッドをリダイレクトすることにより、停止時間を改善することができる。実施形態は又、組み合わせられ、更に短い停止時間の確率を大きくすることができる。ここで開示された技術は、Ｊａｖａ（登録商標）ヒープが３０％を超えるライブオブジェクトを含まない場合に、場合によっては目標停止時間の９９．９９％以内の停止時間の保持を含み、断片化及びメモリ使用の増加を伴い、予測可能且つ短い停止時間を生成することが実験結果により示された。
【００１１】
図１は、従来の非世代別コンカレント・ガベージコレクタ、及び本発明の実施形態によるダーティーカード(dirty card)及びグレービット(gray bit)のデータ構造の概略図を示す。図１に示されるように、ダーティーカードアレイ１０１は、各バイトがメモリの小領域、通常は数百バイトを表すバイトアレイである。バイトが「ゼロ」１０２である場合には、その領域を表すカードはクリーン(clean)である。バイトが他の値である場合には、カードがダーティー１０３であることを意味する。実行時中、ワーカースレッド(worker thread)（ユーザのアプリケーションにより要求された実際の作業(actual work)を実行するスレッド）が領域内のＪａｖａ（登録商標）オブジェクト・ポインタを更新した場合には、領域はダーティーになる。グレービットアレイ１０４は、Ｊａｖａ（登録商標）オブジェクトのすべての可能な位置を表す。グレービットの数を限定するために、Ｊａｖａ（登録商標）オブジェクトは常に８バイト境界に合わせられる。ビットが「ゼロ」１０５である場合には、その位置にライブオブジェクトがない。ビットが「１」１０６である場合には、その位置にライブオブジェクトがある。異なるオブジェクトは、異なるメモリ量を占有する。メモリにおけるオブジェクトの正確なエクステントは、オブジェクトの種類を調べることにより見出される。
【００１２】
図２は、従来の非世代別コンカレント・ガベージコレクタによって用いられるプロセスを示すフローチャートを示す。具体的には、図２は、従来の非世代別コンカレント・ガベージコレクタがどのように６つのステップ又は段階：初期マーキング段階２０１、コンカレントマーキング段階２０２、プレクリーニング段階２０３、最終マーキング段階２０４、コンパクション(compaction)段階２０５、及びスイープ(sweep)段階２０６を含むかを示すフローチャートを示す。
【００１３】
ステップ２０１において、システムは、以下を含むガベージコレクションを実行するのに必要なデータ構造を準備する。
ヒープにおけるコンパクション領域を選択する。コンパクション領域は、速い処理を可能とするのに十分小さく、且つ断片化を抑制するのに十分大きいものとすべきである。
コンパクション・ポインタ位置セットを準備する。コンパクション・ポインタ位置セットは、選択されたコンパクション領域内のオブジェクトを指すポインタを含む、ヒープ上のすべてのポインタ位置を記憶する。コンパクション・ポインタ位置セットは、後に向きを変えられ、ポインタは、コンパクション領域内のオブジェクトの動きを反映するように更新される。
ダーティーカードアレイ１０１をクリアする。ダーティーカードアレイをクリアするためには、しばらくの時間、例えば、１ＧｂのＪａｖａ（登録商標）ヒープ、１ＧＨｚのインテル・ペンティアム（登録商標）・プロセッサのシステムで約３ｍｓかかる。クリアリング中は、ワーカースレッドは実行することができない。グレービットは、前のガベージコレクションの終了時点でクリアされている。
【００１４】
ステップ２０２において、コンカレントマーキング段階中、システムは、ルート（スレッドスタック及びグローバルデータ）からオブジェクトへのすべてのポインタを追跡し、これらのオブジェクト中のすべてのポインタについて再帰的に追跡を続ける。新たなオブジェクトが発見される度に、対応するグレービットアレイ１０４のグレービットがチェックされ、１が与えられる。既に１が与えられていた場合には、オブジェクトは既にスキャンされており、コンカレントマーキング・スレッドはそれを無視することができ、その他の場合には、オブジェクト中のポインタを再帰的に追跡する。コンカレントマーキングは、ワーカースレッドの実行中に起こるので、ワーカースレッドが、コンカレントマーキング・プロセスにより既にスキャンされたＪａｖａ（登録商標）オブジェクト中のポインタを更新することができる。これを正しい状態に戻すために、ワーカースレッドがポインタを更新する度に、そのポインタが置かれるメモリ領域のカードがダーティーであるとマーキングされる。コンカレントマーキング段階中、すべてのポインタが、選択されたコンパクション領域を指すか否かがチェックされる。ポインタが、選択されたコンパクション領域を指す場合には、ポインタ位置は、後のコンパクション中の検索のために、ポインタ位置セットに記憶される。
【００１５】
ステップ２０３において、プレクリーニング中、システムは、ルートとしてダーティーカード中のポインタのみについて、コンカレントマーキングプロセスを再開する。このプロセス中、ワーカースレッドは、更にダーティーカードを生成することができるが、ダーティーカードの数は減少するであろう。
【００１６】
ステップ２０４において、プレクリーニングの後に最終マーキング段階が実行される。この段階中、ワーカースレッドは、最終マーキングが実行されることができるように停止させられ、何らの新たなカードがダーティーであるとされることなく、最後のカードがクリーンにされる。この時点において、ガベージコレクタは、今やすべてのライブオブジェクトがＪａｖａ（登録商標）ヒープ上のどこに位置するのかを知っている。場合によっては、いくつかのオブジェクトはライブであると考えられているが、実際はそうではないという状況が起こり得る。これは、例えば、Ｊａｖａ（登録商標）オブジェクト・ポインタがゼロにされているが、ゼロにされる前に、指されたオブジェクトがスキャンされ、マーキングされた場合に起こり得る。そのようなオブジェクトは、次回のガベージコレクションの間に収集される。
【００１７】
時折、Ｊａｖａ（登録商標）ヒープ上にたくさんの空きメモリがあるが、最大の連続空きブロックが必要な割当サイズよりも小さいので、そのいずれもが使用することができない。ステップ２０５において、コンパクション段階は、これらの例におけるＪａｖａ（登録商標）ヒープの断片化を避けるために用いられる。上述のコンカレント段階中、選択されたコンパクション領域中のオブジェクトを指すすべてのポインタが記憶される。従って、ポインタ位置は既に収集されているので、コンパクション領域中のオブジェクトを移動し、移動されたオブジェクトを指すすべてのポインタを、Ｊａｖａ（登録商標）ヒープを再度スキャンすることなく更新することができる。オブジェクトはコンパクション領域の内部で移動させられて、オブジェクト間の空きメモリを除去する。ワーカースレッドは、このコンパクションが進行中、停止させられる。
【００１８】
ステップ２０６において、スイープ段階中、メモリの空き領域が集められ、空きリストにリンクされる。通常、メモリ空間の半分がスイープされ、残りがワーカースレッドにより使用される。更に、グレービットは、この段階中、同時にゼロにセットされる。
【００１９】
上述のように、従来の非世代別コンカレント・ガベージコレクタを使用した場合には、初期マーキングステップ２０１、最終マーキングステップ２０３、及びコンパクションステップ２０４を同時に行うことができないことに気付くであろう。その結果、システムが満足な動作をすべきであるのであれば、これらのステップで費やされる時間は、予測可能且つ制限されたものである必要がある。
【００２０】
予測可能な結果のガベージコレクション
本発明の実施形態は、停止時間が、高い程度の確率で、設定された目標停止時間未満になるように、仮想マシン環境におけるメモリをガベージコレクトするためのシステム及び方法を提供する。
【００２１】
図３は、ガベージコレクション及び／又はコンパクションに使用可能な時間を制御し、必要であれば、コンパクションを途中で効率的にアボートし、多くの参照を有するオブジェクトを移動させないことができるような仕方で、ヒープ内のコンパクション領域を追跡するために使用することができる、本発明の実施形態によるデータ構造の概略図を示す。図３に示されるように、Ｊａｖａ（登録商標）ヒープ３０１は、選択されたコンパクション領域３０２を含む。コンカレントマーキング段階中、選択されたコンパクション領域３０２中のオブジェクト３０３を指すポインタ３０４、３０５が検知される。１つの実施形態において、そのように検知されたポインタ（すなわち参照）は、オブジェクト（３０３）のアドレスを表すインデックス又はキー、及びこのオブジェクトを指すポインタ（３０４、３０５）の位置を表す値と共に、ハッシュテーブル、リスト又は同様のデータ構造３０６内に記憶される。そして、本システムは、以下のようにこのハッシュテーブルを使用することができる。
【００２２】
コンパクション中、停止時間の制限時間に達した場合には、コンパクションを途中で効率的にアボートすることができる。上述のように、従来の元のポインタ位置セットを使用した場合には、コンパクションがアボートされたとしても、どのポインタ位置が更新が必要かが分からないので、すべてのポインタ位置セットをスキャンする必要がある。しかしながら、本発明の実施形態によれば、ガベージコレクタは、実際に移動されたオブジェクトのみのポインタ位置を素早く見出すことができる。
【００２３】
別の使用法において、１つのオブジェクトを指すポインタ位置の数が閾値を超えた場合には、そのオブジェクトを指すポインタ位置のすべてを更新するのに長く時間がかかり過ぎるので、そのオブジェクトは移動させられない。
【００２４】
１つの実施形態によれば、コンパクション段階中、ポインタ位置のリストは、数が増加する順に、指されるアドレスについてソートされる。次いで、アドレスの値が増加する順にオブジェクトについてコンパクションが実行される（すなわち、オブジェクトは、メモリ内で下に移動させられる）ので、ソートされたポインタ位置リストによって動く１つのポインタにより、対応するポインタ位置が追跡される。
【００２５】
図４は、ガベージコレクション・プロセスを制御する予測可能な結果のガベージコレクタを含む本発明の実施形態によるシステムの例示を示す。図４に示されるように、システム４０１は、ハードウエア４０３、オペレーティング・システム４０４、及び実行時環境又は仮想マシン４０５を含むコンピュータ又は物理的なサーバ４０２を含む。仮想マシンは、例えば、サン・マイクロシステム社のSun Java（登録商標） Virtual Machine及びＢＥＡシステム社のJRockit Virtual Machineが挙げられる、Ｊａｖａ（登録商標）仮想マシン（ＪＶＭ）とすることができる。ＪＶＭは、Ｊａｖａ（登録商標）環境においてＪａｖａ（登録商標）ヒープを構成するメモリ空間４０６を含み、又はそれに対するアクセスを有する。更に、Ｊａｖａ（登録商標）ヒープは、実行されているアプリケーションのオブジェクト及びポインタ４０７を含む。本発明の実施形態によれば、予測可能な結果のガベージコレクタ４０８（又は予測可能な結果のガベージコレクション・プロセス）は、コンパクション領域４０９と呼ばれるＪａｖａ（登録商標）ヒープの一部を連続的に分析する。１つの実施形態によれば、本システムは又、各ワーカースレッドのスレッドローカル変数４１０を計算する。スレッドローカル変数は、ワーカースレッドによりポインタが何回更新されたかをカウントする。コンパクション領域についての現在情報は、ガベージコレクション・プロセス中にガベージコレクタによる使用のために、ハッシュテーブル４１１、リスト又は同様のデータ構造に記憶される。
【００２６】
図５は、上記の技術が、どのように、より短く且つより予測可能な停止時間の非世代別コンカレントガベージコレクタをもたらすかを示す、本発明の実施形態によるフローチャートを示す。本実施形態によれば、ガベージコレクション中の停止時間の合計は、設定された程度の確率内で、目標制限停止時間未満に必ずなる。図５に示されるように、初期マーキング段階中、システムは、上述のステップ２０１とほとんど同様の初期化を実行する。１つの実施形態によれば、システムは又、各ワーカースレッドのスレッドローカル変数４１０を計算する。ステップ５０２において、コンカレントマーキング段階は、上述のステップ２０２とほとんど同様に進行する。１つの実施形態によれば、システムは又、オブジェクト・ルートからのすべてのライブオブジェクトをスキャンする。これに加えて、ポインタがワーカースレッドにより更新された場合には、更新回数をカウントするワーカースレッドのスレッドローカル変数の値が１だけ増加する。
【００２７】
本発明の実施形態によれば、システムは、いくつかのプロセッサを使用して、コンカレントマーキング段階を実行することができる。コンカレントマーキング専用スレッドは別として、本実装により、ワーカースレッドは、いくつかのコンカレントマーキングをしなければならない。ワーカースレッドが、Ｊａｖａ（登録商標）ヒープ上の新たなスレッドローカル領域（ＴＬＡ）を要求する場合には、ワーカースレッドは、通常の作業に戻る前に、いくつかのコンカレントマーキングをしなければならない。
【００２８】
ステップ５０３において、プレクリーニング段階は、上述のステップ２０３とほとんど同様に進行する。これに加えて、１つの実施形態によれば、ワーカースレッド・カウンタは、ワーカースレッドの短い停止を招きつつ、値がゼロに設定される。
【００２９】
プレクリーニング段階後、プロセスは、図６に関して更に詳細が説明される、追加的な予測可能な結果のガベージコレクションステップ５１３を含む。１つの実施形態によれば、予測可能な結果のガベージコレクションステップ中、システムは、コンパクション時間を目標停止時間の分数値とし、これにより、ガベージコレクション・プロセスのこの段階が常に目標停止時間未満になるようにする。最終マーキング時間の推定値は、統計に基づく。推定最終マーキング時間に応じて、プレクリーニングを繰り返すか否かが決定される。
【００３０】
１つの実施形態によれば、ワーカースレッド・カウンタは、ワーカースレッドの実行中、加算される。この合計は、数回の更新は、１枚のカードだけをダーティーにすることができるので、ダーティーカードの総数以上となる。
【００３１】
予測可能な結果のガベージコレクションの結果、ステップ５０４において、最終マーキング停止時間に他の残りの停止時間を加えたものが目標停止時間制限未満となるぐらいにダーティーカードがほとんどない場合にのみ、最終マーキング段階が試みられる。
【００３２】
上記の予防策にもかかわらず、Ｊａｖａ（登録商標）ヒープ構造における偶発的な変化のために、別のプレクリーニングに関して、最終マーキングを遅らせることができないことが起こり得る。これは、例えば、ＪＶＭにＪＶＭヒープ空間が不足し、ＪＶＭが実行を続けるためにガベージコレクションが完了される必要がある場合に起こり得る。これが起こった場合には、停止時間は、目標停止時間制限を超えるであろう。しかしながら、上記のプロセスにより、停止時間がおそらく目標停止時間制限を超えないようにされる。
【００３３】
ステップ５０５において、コンパクションは、ハッシュテーブル又は構造３０６に記憶された情報を使用して実行される。
【００３４】
ステップ５０６において、スイープは、上述のステップ２０６とほとんど同様に実行される。
【００３５】
予測可能な結果のガベージコレクションの詳細
図６は、本発明の実施形態による予測可能な結果のガベージコレクション・プロセスのステップをより詳細に示す。具体的には、図６は、システムがプレクリーニングを何回繰り返すべきかを決定するプロセスを示す。１つの実施形態によれば、図６に記載された一連のステップは、ワーカースレッドの実行中に起こる。
【００３６】
実世界の例を考えるために、目標停止時間制限が３０ｍｓ、システムが目標停止時間の３分の１である１０ｍｓをコンパクション段階であるステップ６０１に割り当てたものとする。コンパクション段階は、システムの長期的安定性のために必要であるだけなので、ガベージコレクション・プロセスの最も柔軟性のある段階である。長期的な観点でコンパクションに十分な時間が費やされる限り、一時的にコンパクションに費やす時間を短くすることができる。本発明の実施形態は、この柔軟性を利用するものであり、コンパクション時間を目標停止時間の分数値に設定し、これにより、ガベージコレクション・プロセスのこの段階が常に目標停止時間未満になるようにする。残りの時間は、初期マーキング及び最終マーキングに割り当てられる。初期マーキングは既に行われており、その時間が差し引かれる。残りの時間（例えば、約１７ｍｓ）が、最終マーキングであるステップ６０２に使用可能である。
【００３７】
ステップ６０３において、ワーカースレッド・カウンタは、ワーカースレッドの実行中、加算される。この合計は、数回の更新は、１枚のカードだけをダーティーにすることができるので、ダーティーカードの総数以上となる。ガベージコレクタはその合計の概ねの値に関心があるだけなので、ロック(locking)は必要ない。
【００３８】
ステップ６０４において、最終マーキング時間の推定値は、統計に基づいて決定される。高い程度の確率で、Ｊａｖａ（登録商標）ヒープの任意のダーティーカードのクリーニングには、一定した量の時間を要することが実験により示された。推定最終マーキング時間に応じて、プレクリーニングを繰り返すか否かが決定される。例えば、１ＧｂのＪａｖａ（登録商標）ヒープ、１ＧＨｚのインテル・ペンティアム（登録商標）・プロセッサ、及び３０％のライブデータのシステムで、約１μｓかかる。本発明の実施形態は、ワーカースレッド・カウンタを使用し、合計をダーティーカードの推定クリーニング時間で乗ずることによって、最終マーキングにどのぐらいの時間がかかるかを推定する。ステップ６０４において、推定最終マーキング時間が、ステップ６０２において計算された時間を超えた場合には、ステップ６０５においてプレクリーニングを繰り返すと決定される。最終マーキングが、割り当てられた最終マーキング時間６０２未満であった場合には、最終マーキングを進めると決定される。
【００３９】
図７は、本発明の実施形態によって、計算された時間制限内にコンパクション時間を保持するためのプロセスをより詳細に示す。図７に示されるように、ステップ７０１において、オブジェクトが起こり得る移動のために選択される。移動されるべきオブジェクトがもはやない場合には、コンパクションは完了する（ステップ７０７も）。ステップ７０２において、システムは、ハッシュテーブル又は構造３０６を使用して、選択されたオブジェクトが移動させられた場合に、いくつの参照が更新されなければならないかを判定することができる。ステップ７０３において、参照を更新するのにかかる時間が、コンパクションに割り当てられた残り時間未満となるか否かを見るためのチェックが行われる。次いで、オブジェクトを移動することができ、或いは別のオブジェクトが選択される。ステップ７０４において、システムは、オブジェクトを、選択されたコンパクション領域内で下に移動させるか、又は選択されたコンパクション領域から出して、Ｊａｖａ（登録商標）ヒープの一番下に退避させる。コンパクション領域内にオブジェクトがほとんど見出されない場合には、オブジェクトは退避させられ、完全な空き領域が残される。その他の場合には、オブジェクトは、コンパクション領域内で移動させられる。ステップ７０５において、構造３０６を再度使用して、移動させられたオブジェクトを指す参照が更新される。ステップ７０６において、残り時間がチェックされて更にオブジェクトを移動することができる場合には、プロセスは繰り返しステップ７０１に戻る。その他の場合には、ステップ７０７において、コンパクションプロセスが完了する。
【００４０】
本発明は、本開示の教示によってプログラムされた、従来の汎用又は特別のデジタルコンピュータ又はマイクロプロセッサを用いて便宜上実装することができる。適切なソフトウエアコーディングが、本開示の教示に基づいて、当業のプログラマによって容易に用意されることができることは、ソフトウエア技術の当業者に明らかであろう。
【００４１】
いくつかの実施形態において、本発明は、本発明のあらゆるプロセスを実行するようにコンピュータをプログラムするために使用することができる命令が記録された記録媒体であるコンピュータプログラム製品を含む。記録媒体としては、これらに限られるものではないが、フロッピー（登録商標）ディスク、光学ディスク、ＤＶＤ、ＣＤ−ＲＯＭ、マイクロドライブ、及び光磁気ディスクを含むあらゆる種類のディスク、ＲＯＭ、ＲＡＭ、ＥＰＲＯＭ、ＥＥＰＲＯＭ、ＤＲＡＭ、ＶＲＡＭ、フラッシュメモリ装置、磁気カード又は光学カード、ナノシステム（分子メモリＩＣを含む）、又は命令及び／又はデータを記録するのに適したあらゆる種類の媒体若しくは装置が挙げられる。
【００４２】
以上の本発明の説明は、例示及び説明のために提供されたものである。網羅的、又は本発明を開示されたのと同じ形に限定する意図でなされたものではない。多くの修正及び変形が当業者に自明であろう。特に、上述の実施形態のシステム及び方法は、JRockit環境の文脈で説明されたが、本システム及び方法が、他の種類のアプリケーションサーバ、仮想マシン及びＪａｖａ（登録商標）仮想マシンについて用いることができることは明らかであろう。実施形態は、本発明の原理及びその実際的応用を最良に説明するために、選択され説明され、それにより、他の当業者が、様々な実施形態についての本発明、及び特定の用途について考えられる様々な修正を理解することができる。本発明の範囲は、以下の特許請求の範囲及びその均等物により定義されることが意図される。
【図面の簡単な説明】
【００４３】
【図１】従来の非世代別コンカレント・ガベージコレクタ、及び本発明の実施形態によるダーティーカード及びグレービットのデータ構造の概略図を示す。
【図２】従来の非世代別コンカレント・ガベージコレクタによって用いられるプロセスを示すフローチャートを示す。
【図３】コンパクションを途中で効率的にアボートし、多くの参照を有するオブジェクトを移動させないことができるような仕方で、ヒープ内のコンパクション領域を追跡する、本発明の実施形態によるデータ構造の概略図を示す。
【図４】予測可能な結果のガベージコレクタを含む本発明の実施形態によるシステムの例示を示す。
【図５】より短く且つより予測可能な停止時間の非世代別コンカレントガベージコレクタにより用いられるプロセスを示す本発明の実施形態によるフローチャートを示す。
【図６】プレクリーニングが何回繰り返すべきかについての決定プロセスを示す本発明の実施形態によるフローチャートを示す。
【図７】計算された時間制限内にコンパクション時間を保持するために用いられる決定プロセスを示す本発明の実施形態によるフローチャートを示す。
【図１】
2009501384.tif 000003
【図２】
2009501384.tif 000004
【図３】
2009501384.tif 000005
【図４】
2009501384.tif 000006
【図５】
2009501384.tif 000007
【図６】
2009501384.tif 000008
【図７】
2009501384.tif 000009
【手続補正書】
【提出日】平成20年3月17日(2008.3.17)
【手続補正１】
【補正対象書類名】特許請求の範囲
【補正対象項目名】全文
【補正方法】変更
【補正の内容】
【特許請求の範囲】
【請求項１】
仮想マシン環境における予測可能な結果のガベージコレクションのためのシステムであって、
ソフトウエア・アプリケーションを実行するための仮想マシンと、
前記ソフトウエア・アプリケーションの一部としてのソフトウエア・オブジェクト及びポインタを記憶するに際して前記仮想マシンによる使用のためのメモリ空間と、
前記メモリ空間の領域について、前記領域内のソフトウエア・オブジェクトのガベージコレクションの前記停止時間の合計を推定し、且つ前記ガベージコレクションの停止時間の合計が目標停止時間制限未満となるように、前記ガベージコレクション・プロセスを制御するガベージコレクタと、
を含むことを特徴とするシステム。
【請求項２】
前記ガベージコレクタは、統計に基づいて、前記ガベージコレクションの停止時間の合計を推定し、前記ガベージコレクションの停止時間の合計が、統計的確率の程度内で、目標停止時間制限未満となるように、前記ガベージコレクション・プロセスを制御することを特徴とする請求項１に記載のシステム。
【請求項３】
前記メモリ空間の領域は、コンパクション領域であり、
前記ガベージコレクタは、前記コンパクション領域に割り当てられた使用可能なコンパクション時間を前記目標停止時間制限の分数値に設定し、
マーキングステップ中、前記コンパクション領域内のソフトウエア・オブジェクトを指すあらゆるポインタを判定し、そのように判定されたポインタが、前記指されるソフトウエア・オブジェクトのアドレス、及び前記ソフトウエア・オブジェクトを指すポインタの位置を表すキーと共に、テーブルに記憶されることを特徴とする請求項１記載のシステム。
【請求項４】
ワーカースレッド、及びワーカースレッドによりポインタが更新された回数を示す値を含むスレッドローカル変数を更に含み、
前記スレッドローカル変数は、前記ガベージコレクションの停止時間の合計を推定する際に、前記ガベージコレクタにより使用され、
前記スレッドローカル変数は、前記次のガベージコレクション中に前記ガベージコレクタにより処理されなければならないダーティーカードの数を示すことを特徴とする請求項１記載のシステム。
【請求項５】
前記ガベージコレクタは、前記ソフトウエア・オブジェクトのプレクリーニングステップを選択的に繰り返し、
前記プレクリーニングステップ中、前記ガベージコレクタは、前記ワーカースレッドによりポインタが何回更新されたかを示す、各ワーカースレッドのスレッドローカル変数を計算し、
前記停止時間の合計は、最終マーキング時間の統計的推定値に基づくものであり、
前記最終マーキング時間の推定値に応じて、前記ガベージコレクタにより、前記プレクリーニングステップが繰り返されるか否かが決定されることを特徴とする請求項１記載のシステム。
【請求項６】
前記メモリ空間の領域における前記ソフトウエア・オブジェクトのガベージコレクションの停止時間の合計の統計的推定値は、前記ソフトウエア・アプリケーションの実行の前に前記システムにエンコードされた情報、又は前記ソフトウエア・アプリケーションの実行中に前記システムにより収集された実行時間情報に基づくものであることを特徴とする請求項２記載のシステム。
【請求項７】
コンパクションステップ中、前記コンパクションの停止時間の目標時間制限に達した場合には、前記コンパクションがアボートされ、又は前記ソフトウエア・オブジェクトを指すポインタ位置の数が閾値を超えた場合には、前記コンパクションステップの一部として、前記ソフトウエア・オブジェクトは移動させられないことを特徴とする請求項１記載のシステム。
【請求項８】
前記仮想マシンは、Ｊａｖａ仮想マシンであることを特徴とする請求項１記載のシステム。
【請求項９】
仮想マシン環境における予測可能な結果のガベージコレクションのための方法であって、
ソフトウエア・アプリケーションを実行するための仮想マシンを用意するステップと、
前記ソフトウエア・アプリケーションの一部としてのソフトウエア・オブジェクト及びポインタを記憶するに際して前記仮想マシンによる使用のためのメモリ空間を用意するステップと、
ガベージコレクタを使用して、前記メモリ空間内のソフトウエア・オブジェクトのガベージコレクションを制御するステップと、
を含み、
前記ガベージコレクタは、前記メモリ空間の領域について、前記領域内のソフトウエア・オブジェクトのガベージコレクションの前記停止時間の合計を推定し、且つ前記ガベージコレクションの停止時間の合計が目標停止時間制限未満となるように、前記ガベージコレクション・プロセスを制御することを特徴とする方法。
【請求項１０】
ソフトウエア・アプリケーションを実行するための仮想マシンを用意するステップと、
前記ソフトウエア・アプリケーションの一部としてのソフトウエア・オブジェクト及びポインタを記憶するに際して前記仮想マシンによる使用のためのメモリ空間を用意するステップと、
前記メモリ空間の領域について、前記領域内のソフトウエア・オブジェクトのガベージコレクションの前記停止時間の合計を推定し、且つ前記ガベージコレクションの停止時間の合計が目標停止時間制限未満となるように、前記ガベージコレクション・プロセスを制御するガベージコレクタを使用して、前記メモリ空間内のソフトウエア・オブジェクトのガベージコレクションを制御するステップと、
を実行時にコンピュータに実行させる、記録媒体に記録された命令を含むコンピュータ読み取り可能な記録媒体。
【国際調査報告】
2009501384.tif 000010