(57)【要約】コンピューティングシステムのパフォーマンスを改善するための、詳細にはプラットフォームによらないプログラムを走らせているメモリ容量の小さいシステムのためのコードキャッシュ管理の効率を改善するための構成が提供される。そのようなシステムのコードキャッシュはランタイムの間継続的に監視される。条件がコードキャッシュ管理の実行を認める場合には、優先度に基づくコードキャッシュ管理が選択的コードガーベジコレクションに基づいて実行される。選択的コードガーベジコレクションは、コードキャッシュ中の寿命を終えたメソッドに対して、該寿命を終えたメソッドが再度使用される確率に基づいて選択的に行われる。【特許請求の範囲】
【請求項１】
第一のコードを受け取り、
前記第一のコードを第二のコードにコンパイルし、
該第二のコードのために十分なメモリスペースがコードキャッシュ中に存在することを保証するよう優先度に基づくコードキャッシュ管理（CCM：code  cache  management）を実行することを含む、
プラットフォームによらないプログラムを実行するシステムのパフォーマンスを改善する方法。
【請求項２】
前記第一のコードがプラットフォームによらないコードを有することを特徴とする、請求項１記載の方法。
【請求項３】
前記第二のコードが基礎にある当該システムの計算アーキテクチャにネイティブな低レベルの計算命令にコンパイルされた第一のコードであることを特徴とする、請求項１記載の方法。
【請求項４】
前記優先度に基づくＣＣＭの実行が、コードキャッシュ中のメモリスペースをより効率的に利用するために各メソッドの優先度に基づいてコードキャッシュの管理を行い、前記第二のコードがコードキャッシュにない場合には該第二のコードをコードキャッシュに転送する、ことを含むことを特徴とする、請求項１記載の方法。
【請求項５】
前記第二のコードを実行することをさらに含むことを特徴とする、請求項１記載の方法。
【請求項６】
優先度に基づくコードキャッシュ管理（ＣＣＭ）をトリガーする条件が満たされているかどうかを動的に判断し、
コードキャッシュ中の各メソッドの優先度に基づいて選択的コードガーベジコレクション（CGC：code  garbage  collection）を実行する、
ことを含むことを特徴とする、コードキャッシュを管理する方法。
【請求項７】
前記優先度に基づくＣＣＭをトリガーする条件が：コードキャッシュのフリースペースの大きさがある閾値未満になること、コードキャッシュ中のメソッドの数がある閾値を越えること、はいってくるコンパイル済みコードの大きさがコードキャッシュのフリースペースの大きさよりも大きいこと、のうちの少なくとも一つを含むことを特徴とする、請求項６記載の方法。
【請求項８】
メソッドの前記優先度が、該メソッドについての生存メソッドカウンタ（SMC：surviving  method  counter）の値を含むことを特徴とする、請求項６記載の方法。
【請求項９】
メソッドが最初にコンパイルされたときに該メソッドのＳＭＣ値を初期化し、ランタイム中に該ＳＭＣ値を更新することを含むことを特徴とする、請求項８記載の方法。
【請求項１０】
前記ＳＭＣ値の更新が、当該メソッドが前記優先度に基づくＣＣＭの間存命である、当該メソッドが前記優先度に基づくＣＣＭの間存命でない、当該メソッドがランタイム中に再コンパイルされている、のうちの少なくとも一つの条件が満たされている場合に前記ＳＭＣ値を修正することであることを特徴とする、請求項９記載の方法。
【請求項１１】
前記ＳＭＣ値が所定の範囲外に出ないことを保証するよう、前記ＳＭＣ値を制限することをさらに含むことを特徴とする、請求項１０記載の方法。
【請求項１２】
選択的ＣＧＣの実行が、寿命を終えているメソッドについて、該寿命を終えているメソッドのＳＭＣ値に基づいてＣＧＣを行うことであることを特徴とする、請求項６記載の方法。
【請求項１３】
ＣＧＣを行うことが、スタック情報に基づいて寿命を終えているメソッドから存命メソッドを分別し、ガーベジと同定された寿命を終えているメソッドによって占められているメモリスペースを再生することを含むことを特徴とする、請求項１２記載の方法。
【請求項１４】
第一のコードを受け取る仮想マシンと、
前記第一のコードを第二のコードにコンパイルするジャストインタイムコンパイラと、
コードキャッシュを効率的に管理し、前記第二のコードがキャッシュコード中になければ該第二のコードをコードキャッシュ中に転送するための、優先度に基づくコードキャッシュ管理（ＣＣＭ）機構と、
前記優先度に基づくＣＣＭ機構によって提供される優先度情報に基づいてコードキャッシュ中の寿命を終えたコードを選択的にリサイクルするコードガーベジコレクターとを有することを特徴とするシステム。
【請求項１５】
前記仮想マシンが前記第二のコードを実行する実行機構を有することを特徴とする、請求項１４記載のシステム。
【請求項１６】
前記コードガーベジコレクターが：
スタック情報に基づいてコードキャッシュ中で寿命を終えているメソッドから存命メソッドを分別するルートセットスキャン機構と、
ガーベジと同定された寿命を終えているメソッドによって占められているコードキャッシュ中のメモリスペースを再生するガーベジ再生機構とを有することを特徴とする、請求項１４記載のシステム。
【請求項１７】
メソッドがランタイム中に再度使用される確率の尺度となる生存メソッドカウンタ（ＳＭＣ）をメソッドごとにそれぞれ対応して複数有し、
ＳＭＣ値を更新するＳＭＣ更新機構をメソッドごとにそれぞれ対応して複数有し、
優先度に基づくＣＣＭをトリガーする条件が満たされているかどうかをランタイムに監視し、前記複数のＳＭＣの値に基づいて寿命を終えているメソッドのうちのどれをリサイクルするかを決定する、生存メソッド決定機構を有することを特徴とする、
優先度に基づくコードキャッシュ管理（ＣＣＭ）を実行するシステム。
【請求項１８】
メソッドごとの前記ＳＭＣ更新機構が、メソッドを同定し、該メソッドについてのＳＭＣを設定し、該メソッドの該ＳＭＣを初期化する初期化部を有することを特徴とする、請求項１７記載のシステム。
【請求項１９】
プラットフォームによらないプログラムを走らせるシステムのパフォーマンスを：
第一のコードを受け取り、
前記第一のコードを第二のコードにコンパイルし、
該第二のコードのために十分なメモリスペースがコードキャッシュ中に存在することを保証するよう優先度に基づくコードキャッシュ管理（ＣＣＭ）を実行すること、
によって改善することを、プロセッサによってアクセスされたときに提供する内容が記録された機械アクセス可能媒体、
を有することを特徴とする物品。
【請求項２０】
前記第一のコードがプラットフォームによらないコードを有することを特徴とする、請求項１９記載の物品。
【請求項２１】
前記第二のコードが基礎にある当該システムの計算アーキテクチャにネイティブな低レベルの計算命令にコンパイルされた第一のコードであることを特徴とする、請求項１９記載の物品。
【請求項２２】
優先度に基づくＣＣＭの実行のための内容が、コードキャッシュ中のメモリスペースをより効率的に利用するために各メソッドの優先度に基づいてコードキャッシュの管理を行い、前記第二のコードがコードキャッシュにない場合には該第二のコードをコードキャッシュに転送するための内容を含むことを特徴とする、請求項１９記載の物品。
【請求項２３】
前記第二のコードを実行するための内容をさらに含むことを特徴とする、請求項１９記載の物品。
【請求項２４】
優先度に基づくコードキャッシュ管理（ＣＣＭ）をトリガーする条件が満たされているかどうかを動的に判断し、
コードキャッシュ中の各メソッドの優先度に基づいて選択的コードガーベジコレクション（ＣＧＣ）を実行すること、
によってコードキャッシュを管理することを、プロセッサによってアクセスされたときに提供する内容が記録された機械アクセス可能媒体、
を有することを特徴とする物品。
【請求項２５】
前記優先度に基づくＣＣＭをトリガーする条件が：コードキャッシュのフリースペースの大きさがある閾値未満になること、コードキャッシュ中のメソッドの数がある閾値を越えること、はいってくるコンパイル済みコードの大きさがコードキャッシュのフリースペースの大きさよりも大きいこと、のうちの少なくとも一つを含むことを特徴とする、請求項２４記載の物品。
【請求項２６】
メソッドの前記優先度が、該メソッドについての生存メソッドカウンタ（ＳＭＣ）の値を含むことを特徴とする、請求項２４記載の物品。
【請求項２７】
メソッドが最初にコンパイルされたときに該メソッドのＳＭＣ値を初期化し、ランタイム中に該ＳＭＣ値を更新するための内容を含むことを特徴とする、請求項２６記載の物品。
【請求項２８】
前記ＳＭＣ値の更新のための内容が、当該メソッドが前記優先度に基づくＣＣＭの間存命である、当該メソッドが前記優先度に基づくＣＣＭの間存命でない、当該メソッドがランタイム中に再コンパイルされている、のうちの少なくとも一つの条件が満たされている場合に前記ＳＭＣ値を修正するための内容であることを特徴とする、請求項２７記載の物品。
【請求項２９】
前記ＳＭＣ値が所定の範囲外に出ないことを保証するよう、前記ＳＭＣ値を制限するための内容をさらに含むことを特徴とする、請求項２８記載の物品。
【請求項３０】
選択的ＣＧＣの実行のための内容が、寿命を終えているメソッドについて、該寿命を終えているメソッドのＳＭＣ値に基づいてＣＧＣを行うための内容であることを特徴とする、請求項２４記載の物品。
【請求項３１】
ＣＧＣを行うための内容が、スタック情報に基づいて寿命を終えているメソッドから存命メソッドを分別し、ガーベジと同定された寿命を終えているメソッドによって占められているメモリスペースを再生するための内容を含むことを特徴とする、請求項３０記載の物品。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般にはキャッシュおよびメモリ管理に関するもので、より詳細にはメモリ容量の小さいデバイスのためのコードキャッシュ管理に関するものである。
【背景技術】
【０００２】
Ｊａｖａ（登録商標）やＣ＃のようなプラットフォームによらないプログラミング言語は市場でかなりの存在感を得るに至っている。特にネットワークベースのアプリケーションの場合がそうである。典型的には、これらの言語で書かれたプログラムはまず、バイトコードと呼ばれるプラットフォームを問わない配布形式のコードにコンパイルされる。バイトコードは直接にはどのようなプラットフォームでも実行できない。特定のプラットフォームによって理解できる命令に解釈されなければならないのである。Ｊａｖａ（登録商標）プログラムの場合、バイトコードをプラットフォームによって理解される命令に解釈するのがＪａｖａ（登録商標）仮想マシン（JVM：Java（登録商標）  Virtual  Machine）である（Ｃ＃プログラムの場合、仮想マシンは共通言語インフラストラクチャー［CLI：Common  Language  Infrastructure］である）。しかし、ＪＶＭによる解釈は、ランタイムのオーバーヘッドが大きい処理が必要とされるため、通例バイトコードの実行にとって許容できないほどのパフォーマンス上の負担を課すことになる。このＪＶＭのパフォーマンスを改善するためにジャストインタイム（JIT：Just-In-Time）コンパイラというものが設計されている。これは所与のメソッドのバイトコードを、そのメソッドが最初に呼び出される前にプラットフォームのネイティブコードにコンパイルしておくものである。メソッドのネイティブコードがメモリに保存され、その後そのメソッドの呼び出しはすべて、低速のＪＶＭの解釈にかけるのではなく、より高速なこのネイティブコードによって処理される。
【０００３】
メモリ容量の小さな機器、特にモバイル機器については、ＪＩＴコンパイラによって生成されるネイティブコードはメモリに納まるには大きすぎる場合がある。その結果、そのような機器のメーカーの多くはＪＩＴコンパイラを使わないことを選び、そのためＪＩＴコンパイラのもたらすパフォーマンス上の利点を失ってしまう。メモリ容量の小さな機器についてＪＩＴコンパイラを使うには、他のネイティブコードによって占有されていたメモリスペースを効率的に再利用するメモリ管理機構を採用することが必要である。そのようなメモリ管理機構は、ネイティブコードが保存されるコードキャッシュに適用される場合、通例コードキャッシュ管理（CCM：Code  Cache  Management）機構と称される。
【０００４】
ＣＣＭの問題は典型的には動的最適化問題の一部として議論され、たとえばK.Hazelwood  and  M.D.SmithがProceedings  of  the  Sixth  Annual  Workshop  on  Interaction  between  Compilers  and  Computer  Architectures  （INTERACT’02）中の“Code  Cache  Management  Schemes  for  Dynamic  Optimizers”において議論している。ＣＣＭ方式の一つは、フル・キャッシュ・フラッシュ（FCF：Full  Cache  Flush）である。この方式では、新しくはいってくるコードはキャッシュの最低位アドレスからより高位のアドレスに向かって埋めていく。キャッシュがいっぱいになると、キャッシュ内の全コードがフラッシュされ、また最低位から埋めていくプロセスが始まる。もう一つのＣＣＭ方式としては、最後のアクセスが古いものからのフラッシュ（LRAF：Least-Recently  Accessed  Flush）があり、これはキャッシュがいっぱいになったときに最近アクセスされなかったコードをフラッシュする。最後のアクセスが最も古いコードによって解放されるスペースが新しくはいってくるコードを入れるのに十分でない場合には、隣接するコードもフラッシュされて新しいコードのために十分な連続スペースが確保できるようにされる。もう一つのＣＣＭ方式はアクセス頻度の低いものからのフラッシュ（LFAF：Least-Frequently  Accessed  Flush）と呼ばれるものである。ＬＦＡＦの考えは本質的にはＬＲＡＦと同じであり、ただ最初にフラッシュされる候補がアクセス頻度が最も低いものであるというだけである。さらにもう一つのＣＣＭ方式は作成が古いものからのフラッシュ（LRCF：Least-Recently  Created  Flush）で、この場合、コードキャッシュ中のコードはそこにはいってきたのと同じ順番で置き換えられていく。さらにもう一つのＣＣＭ方式は最大要素のフラッシュ（LEF：Largest  Element  Flush）で、これは大きさが最も大きいコードを最初にフラッシュする（新コードにもっと連続するスペースが必要であれば隣接するコードも）ことでフラッシュの回数が最小になるようにしている。さらにもう一つのＣＣＭ方式は大きさが近いもののフラッシュ（BFEF：Best-Fit  Element  Flush）であり、これは新しいコードがちょうど納まる大きさのコード（正確に同じ大きさのものがなければ、新しいコードのサイズよりも大きいうちで最小のコード）をまずフラッシュする。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
こうしたＣＣＭ方式を、プラットフォームによらないプログラム（たとえばＪａｖａ（登録商標）様のプログラム）をＪＩＴコンパイラを用いて走らせている小メモリシステムに適用すると、コードを再コンパイルする率が高くなる可能性がある。これは、あとからくるコードが、先にコンパイルされたのにＣＣＭの結果すでにフラッシュされてしまっているコードを呼び出すかもしれないからである。Ｊａｖａ（登録商標）様プログラムをＪＩＴコンパイラを用いて走らせている小メモリシステムのためのＣＣＭ方式の一つの目標は、再コンパイル率を著しく増加させることなくメモリ使用の効率を改善することである。もう一つの目標は、ＣＣＭ方式によってもたらされるオーバーヘッドを減らすことである。オーバーヘッドが大きいと処理スピードが遅くなり、ＣＣＭ方式によってもたらされうるパフォーマンス向上を損なう可能性があるからである。しかしながら、上述したような現在利用可能なＣＣＭ方式は、特にＪａｖａ（登録商標）様プログラムを走らせている小メモリシステムにとって、再コンパイル率の上昇もしくはオーバーヘッドの増加またはその両方につながる可能性がある。したがって、Ｊａｖａ（登録商標）様プログラムを走らせている小メモリシステムのパフォーマンスを改善するためには、あまりオーバーヘッドを追加することなく再コンパイル率を低下させることのできる、より効率的なＣＣＭ方式が必要とされているのである。
【０００６】
本発明の特徴および利点は以下の本発明の詳細な記述から明らかとなるであろう。
【課題を解決するための手段】
【０００７】
本発明の実施形態は、コンピューティングシステムにおいて、特にプラットフォームによらないプログラムをＪＩＴコンパイラを用いて走らせている小メモリコンピューティングシステムのために、コードキャッシュを効率的に管理する方法および装置である。本発明は、そのようなコンピューティングシステムのパフォーマンスを向上させるのに用いうるものであり、そのために、著しく再コンパイル率を増加させたりあまり大きなオーバーヘッドを招来したりすることなく、コードキャッシュ中に新しいコードのための十分なスペースが存在することを保証する。寿命を終えた（ｄｅａｄ）メソッドによってコードキャッシュ中に占められているスペースを選択的にリサイクルするため、選択的コードガーベジコレクション（CGC：Code  Garbage  Collection）に基づいた優先度に基づくＣＣＭを用いることができる。ＣＧＣをくぐり抜けたメソッドは生存（ｓｕｒｖｉｖｉｎｇ）メソッドと呼ばれる。選択的ＣＧＣを実行する場合、寿命を終えたメソッド全部がガーベジ＝ゴミと考えられるわけではない。寿命を終えたメソッドでもプログラムによって後で再度使用される可能性が高いものはコードキャッシュ中に保持され、ＣＧＣ機構によって収集の対象とはされない。あるメソッドが将来プログラムによって再度使用される確率は、生存メソッドカウンタ（SMC：surviving  method  counter）というものの値を尺度とすることができる。コードキャッシュの条件が選択的ＣＧＣを認める場合には常に、寿命を終えたメソッドがすべてＳＭＣの値に従って待ち行列に配列される。ここで、再度使用される確率が最低に対応するＳＭＣ値のメソッドが待ち行列の底にくる。ＣＧＣは待ち行列の底にある寿命を終えたメソッドから始めて、コードキャッシュ中のフリースペースの要請が満たされるまでガーベジコレクションを行う。
【０００８】
選択的ＣＧＣに基づいた優先度に基づくＣＣＭ機構というこの手法は、コードキャッシュ使用の効率を改善できる。この機構はメソッドの再コンパイル率を減らせるばかりでなく、ランタイムにおいてほとんどオーバーヘッドも生じない。特に、この機構によって、Ｊａｖａ（登録商標）様プログラムを走らせている小メモリシステムは、パフォーマンスを改善するためにＪＩＴコンパイラを使うことができるようになる。
【０００９】
本明細書において本発明の「一つの実施形態」「ある実施形態」といった表現は、その実施形態に関連して記述されている特定の機能、構造、特徴が本発明の少なくとも一つの実施形態に含まれているということを意味している。よって、本明細書の随所に現れる「ある実施形態において」という語句は、必ずしもみなが同じ実施形態のことを言っているとは限らない。
【発明を実施するための最良の形態】
【００１０】
図１は、本発明のある実施形態に基づく、Ｊａｖａ（登録商標）プログラムのための、優先度に基づくコードキャッシュ管理機構を使ったシステム例の、高いレベルでの枠組みを示す図である。コアＪＶＭ１１０はプラットフォームによらないＪａｖａ（登録商標）バイトコードを受け取り、そのバイトコードを基礎になるプロセッサによって理解できる命令に解釈するか、そのバイトコードをＪＩＴコンパイラ１２０を使うことによってコードキャッシュ中に保存されているネイディブコードにコンパイルする。コアＪＶＭは、前記ネイティブコードや前記解釈されたバイトコードを実行する実行機構を有している。通常は、ＪＩＴコンパイルされてコードキャッシュに保存されているネイティブコードを通じてＪａｖａ（登録商標）コードを実行するのは、同じＪａｖａ（登録商標）コードをＪＶＭで解釈される命令を通じて実行するよりもずっと高速である。だからたいていのＪＶＭがＪＩＴコンパイラを使うのである。ところが、ネイティブコードはコードキャッシュ中でメモリスペースを占有する。大きなコードキャッシュを持つ多くのシステムでは、ネイティブコードをコードキャッシュに保存しておくことは問題ではない。しかしながら、コードキャッシュが小さいシステムにとっては、コードキャッシュのスペースは貴重である。そのような小さなコードキャッシュは効率的に使うことが望ましい。
【００１１】
コードキャッシュ内の寿命を終えたメソッドによって占有されているスペースをリサイクルするのに、コードガーベジコレクター１４０を使うことができる。しかし、コードガーベジコレクターが、メソッドが寿命が終えたとわかるそばからそれらのメソッドのスペースをリサイクルしていくのでは、一部のメソッドの再コンパイル率が高くなることがありうる。寿命を終えたメソッドの一部はあとでまた必要とされるかもしれないからである。ＪＩＴコンパイルされたネイティブコードがＪａｖａ（登録商標）プログラムの実行スピードを改善できる理由の一つは、メソッドのネイティブコードが一度コンパイルされれば再利用できるということであった。もしもＣＧＣ技術を使うことによって再コンパイル率が高くなってしまうとしたら、ＪＩＴコンパイラを使う利点の一つが失われかねない。したがって、コードガーベジコレクターを使ってコードキャッシュ中の寿命を終えたメソッドによって占有されているスペースをすぐ再生するというだけでは、コードキャッシュ使用の効率改善には十分でない。本発明の目標の一つは、コードキャッシュ中の寿命を終えたメソッドによって占有されているスペースを再生するのみならず、全体的な再コンパイル率を減らすことである。
【００１２】
コードキャッシュの使用の効率を改善しつつ、メソッドの全体的な再コンパイル率を減らすために、優先度に基づくＣＣＭ機構１３０を用いることができる。優先度に基づくＣＣＭ機構は、寿命を終えたメソッドのうちのどれが他と比較してゴミとして収集の対象とする優先度が高いかを、寿命を終えたメソッドのそれぞれが将来再度使用される確率に基づいて決定する。寿命を終えたメソッドのうち、再使用確率の高いものは、ＣＧＣをくぐり抜ける確率が高い。メソッドの再使用確率は、そのメソッドのＳＭＣの値によって測ることができる。メソッドのＳＭＣの値がメソッドの再使用確率にどのように結び付けられるかは、設計上の選択の余地がある。一つの実施形態では、メソッドのＳＭＣの高い値がメソッドの再使用確率が高いものに相当することもある。別の実施形態では、メソッドのＳＭＣの低い値がメソッドの再使用確率の高いものに相当することもある。メソッドのＳＭＣの値は、優先度に基づくＣＣＭセッションのたびに更新されうる。メソッドのＳＭＣの値はまた、そのメソッドが再コンパイルされるたびに更新されうる。ある実施形態では、寿命を終えたメソッドのＳＭＣの値に基づいて、寿命を終えたメソッドが待ち行列に配列され、寿命を終えたメソッドの中でも再使用確率が最低のものが待ち行列の底にくるようにすることができる。コードガーベジコレクター１４０は寿命を終えたメソッドのリサイクルを、底から始めて上に進めていき、コードキャッシュスペースの要請が満たされるまで続ける。
【００１３】
図２は、本発明のある実施形態に基づく、プラットフォームによらないプログラムを走らせているシステムにおいて優先度に基づくコードキャッシュ管理を実行するプロセスの代表例としての流れ図である。ブロック２１０では、プラットフォームによらないバイトコード（Ｊａｖａ（登録商標）プログラムの場合、通例.classファイルに含まれる）をＪＶＭが受け取り、ＪＩＴコンパイラに渡すことができる。ブロック２２０では、ＪＩＴコンパイラがそのバイトコードをネイティブコードにコンパイルする。そのネイティブコードは最初はバッファ中に保存されており、コードキャッシュに転送されるのを待つこともある。ブロック２３０では、優先度に基づくＣＣＭ機構によって優先度に基づくＣＣＭが実行され、それによりコードキャッシュは各メソッドの優先度に基づいて効率的に管理され、コードキャッシュ中のスペースがより効率的に利用される。ブロック２３０ではまた、ＪＩＴコンパイラによって生成された前記ネイティブコードが、優先度に基づくＣＣＭ機構によって前記バッファから当該コードキャッシュに転送されることもできる。ブロック２２０と２３０の順番は、本発明の別の実施形態では入れ替えることもできる。たとえば、受け取ったバイトコードが非常に巨大で、その対応するネイティブコードも前記バッファに納まるには大きすぎるかもしれないような場合、ネイティブコードは直接コードキャッシュに入れなければならないこともありうる。このような状況では、コンパイルしたネイティブコードのためにコードキャッシュに十分なスペースがあるように、優先度に基づくＣＣＭはバイトコードをネイティブコードにコンパイルするのに先立って実行されうる。
【００１４】
図３は、本発明のある実施形態に基づく、優先度に基づくコードキャッシュ管理機構およびコードガーベジコレクターの高いレベルでの機能ブロック図である。コードガーベジコレクター１４０は少なくとも二つの構成要素からなっている。ルートセットスキャン機構３１０およびガーベジ再生機構３２０である。これら二つの構成要素は、機能的に、また時間的にからみあっており、再生技術がルートセットスキャン機構によって実行されるガーベジ検出技術に依存することもある。
【００１５】
ルートセットスキャン機構は寿命を終えた（ｄｅａｄ）メソッドから存命（ｌｉｖｅ）メソッドを分別する。コードガーベジコレクターが呼び出された時点では、アクティブなメソッドが存命だと考えられる。メソッドがアクティブかどうかはスタック情報に基づいて決定しうる。スタックに情報（戻りポインタ、変数など）が残っているのは存命メソッドだけだからである。これらのアクティブなメソッドが基本的なルートセットをなす。存命メソッドの最終的なセットを決定するには二つの方法がある。その二つの方法からは、存命メソッドとして二つの異なる最終的なセットが得られる。大セットと小セットである。存命メソッドの大セットは、ルートセット中のメソッドから到達可能な全メソッド、すなわち、ルートセットからのポインタのあらゆる有向パス上にある全メソッドを含む。存命メソッドの小セットは基本的ルートセットに含まれるメソッドのみを含む。定義により、大セットは小セットよりも多くのメソッドを含む場合がある。
【００１６】
大セットに関する一つの潜在的な問題は、ルートセットから到達可能なメソッドは多数に上る可能性があり、結果として得られる存命メソッドの数が大きすぎるかもしれないということである。その結果、ＣＧＣはコードキャッシュ中で必要なだけのスペースを解放できないこともありうる。この問題は、メモリの大きなシステムよりも小メモリシステムについてより頻繁に起こりうる。最悪の場合には、コードキャッシュが大セットによって定義される存命メソッドでいっぱいで再生できるスペースがなく、ＣＧＣが役に立たないこともありうる。小メモリシステムについては、存命メソッドの小セットを使うほうが望ましいと思われる。小セットに関する不都合な点の一つは、ルートセット中のメソッドによってポイントされているメソッドが寿命を終えていると見なされ、ＣＧＣの過程でリサイクルされてしまう可能性があるため、当初は再コンパイル率が高いことがありうるということである。優先度に基づくＣＣＭは最終的にはこの不都合を克服することになる。当初あるメソッドが不適切にリサイクルされてしまったら、このメソッドのＳＭＣの値が変わり（増加または減少する）、このメソッドの再使用確率が上昇することになる。換言すれば、そのメソッドは次回からはリサイクルされる確率が小さくなるのである。したがって、小メモリシステムについては、存命メソッドの小セットの定義のほうが存命メソッドの大セットの定義よりもうまく機能すると思われる。
【００１７】
ガーベジ再生機構３２０は、ルートセットスキャン機構によって与えられる存命メソッドの最終的なセットに基づいて、寿命を終えたメソッドによって占有されているスペースを再生する。典型的には、寿命を終えたメソッドは固まっては位置しておらず、コードキャッシュ中で連続的な領域を占めていはしない。コードキャッシュ中のさまざまな領域に分散している可能性がある。再生によってコードキャッシュのフラグメンテーションが生じる可能性があり、そのため再生したスペースはあまり役に立たないこともありうる。再生技術にはさまざまなものがあるが、一般に二つの範疇に分けられる。移動を伴う再生と移動を伴わない再生である。移動を伴う再生技術は寿命を終えたメソッドによって占有されていたスペースを再生するのみならず、存命メソッドを図６に示すようにコードキャッシュ中で連続的な領域に移動させる。生存メソッド６１５、６３０、６４５、６５０がコードキャッシュの一端のメソッド６０５に連続する領域に移動されることによって、移動後はフリースペースも連続領域となる。これに対して、移動を伴わない再生技術は寿命を終えたメソッドによって占有されていたスペースを再生するだけであって、存命メソッドをコードキャッシュ中の連続領域に移動させることはしない。移動を伴わない再生技術はコードキャッシュにフラグメンテーションを生じる可能性が高い。コードキャッシュにフラグメンテーションがあると、コードキャッシュ中の利用可能スペースは全フリースペースよりも実際には小さくなることもありうる。小さな断片領域には新しいコードを納められないこともありうるからである。たとえば、図６の再生されたスペース６１０は、存命メソッドの移動が行われない場合、スペース６１０のサイズより大きなサイズの新しいコードには再利用できないかもしれないのである。
【００１８】
しかしながら、コードキャッシュ中で存命メソッドを新しい領域に移動させることは、そのメソッドに位置依存性があった場合問題を起こす可能性がある。そのような問題を解決する一つの方法は、ＪＩＴコンパイラが位置独立コード（PIC：position  independent  code）を生成することを要求することである。ＰＩＣの生成は、間接呼び出しを使って行うことができる。図７は、移動を伴うガーベジ再生技術に対して直接呼出しと間接呼び出しがどのように関わってくるかの違いを対比させたものである。直接呼出しでは、移動された存命メソッド（たとえばＦ９）を呼び出す各命令（たとえば命令７１０、７２０、７３０）はそのメソッドの新しい位置（たとえば７６０）を知っていなければならない。しかし、間接呼び出しでは、移動されたメソッド（たとえばＦ９）を呼び出す各命令（たとえば命令７１０、７２０、７３０）はそのメソッドの新しい位置（たとえば７６０）を知っている必要はない。７１０のような呼出し命令はその代わりにＦ９のような呼び出されるメソッドへのポインタを知っている必要があるだけである。メソッドが移動された場合にそのメソッドの新しい位置（たとえば７６０）を知っていなければならないのは、そのメソッドへのポインタ（たとえば７４０）なのである。間接呼び出しを使うのはＰＩＣ生成の一つの方法であって、ＰＩＣを生成するにはほかにも方法がありうる。ＰＩＣを生成するのが何らかの事情で不可能だったとしても、再配置テーブルを使ってそのメソッドにパッチし、そのメソッドの新しい位置を反映するようにすることができる。
【００１９】
移動を伴うガーベジ再生技術を使うことによって、移動を伴わないガーベジ再生技術の場合よりも、ＣＧＣ後のコードキャッシュはより利用しやすいものとなりうる。移動を伴うガーベジ再生技術は同時にランタイムのオーバーヘッドも増大させることがある。本発明は、ガーベジ再生技術については移動を伴うものでも移動を伴わないものでも機能する。
【００２０】
図３に示したように、優先度に基づくＣＣＭ機構１３０は三つの構成要素を含みうる。ＳＭＣ更新機構３３０、ＳＭＣ３４０、生存メソッド決定機構３５０である。ＳＭＣ３４０は、メソッドがランタイム中に再度使用される最新の確率を保持するものである。ＳＭＣ更新機構３３０はＳＭＣの値を更新する。生存メソッド決定機構３５０は、ルートセットスキャン機構、ＳＭＣ３４０によって与えられる寿命を終えたメソッドのＳＭＣ値、その他の要因によって与えられる情報に基づいて、寿命を終えたメソッドのうちのどれを再生してよいかを決定する。その他の要因としては、ＣＧＣをトリガーするトリガー条件を満たすかどうか、ＣＧＣをストップさせるストップ条件を満たすかどうか、といったものがある。このトリガー条件とストップ条件はある閾値でよく、その値はコードキャッシュのフリースペースの大きさまたはコードキャッシュ中の生存メソッドの数に基づいていてもよい。たとえば、ＣＧＣは、コードキャッシュのフリースペースの大きさがある下限閾値を割ったら（すなわち、トリガー条件が満たされたら）常にトリガーされ、コードキャッシュのフリースペースの大きさがある上限閾値を超えたら（すなわち、ストップ条件を満たしたら）常にストップするとしてもよい。同様に、ＣＧＣは、コードキャッシュ内の生存メソッドの数がある上限閾値を超えたら（すなわち、トリガー条件を満たしたら）常にトリガーされ、コードキャッシュ内の生存メソッドの数がある下限閾値を割ったら（すなわち、ストップ条件を満たしたら）常にストップするとしてもよい。ＣＧＣのあとでは、生存メソッドのセットには、存命メソッドおよび寿命を終えてまだ再生されていないメソッドの両方が含まれる。
【００２１】
ＳＭＣ更新機構３３０はメソッドのＳＭＣの値を、ＪＩＴコンパイラ１２０および生存メソッド決定機構３５０によって与えられる情報に基づいて更新する。ＪＩＴコンパイラ１２０によって与えられる情報は、メソッドが初めてコンパイルされたのか、先にリサイクルされたメソッドが再びコンパイルされたのかといったものを含む。ある実施形態では、メソッドが再コンパイルされると、そのメソッドのＳＭＣの値がある数だけ増加するようにできる。生存メソッド決定機構３５０によって与えられる情報は、メソッドが優先度に基づくＣＣＭの間存命かどうかといったものを含む。ある実施形態では、メソッドが優先度に基づくＣＣＭの間存命であれば、そのメソッドのＳＭＣの値がある数だけ増加し、そうでなければそのメソッドのＳＭＣの値がある数だけ減少するようにできる。ＳＭＣ値は、寿命を終えたメソッドの間での相対的な再使用確率を決定するのを助ける。ここで、同じ結果を実現するのに、増加と減少操作を逆にしてもよい。たとえば、そのメソッドが再コンパイルであった場合にそのメソッドのＳＭＣの値をある数だけ減少させるなどである。異なるイベントに対する実際の値の変化量は同じでもいいし、異なっていてもよい。ある実施形態では、メソッドのＳＭＣの値は、メソッドが再コンパイルであったときには常に２増加するようにすることもできるし、そのメソッドが優先度に基づくＣＣＭの間存命であれば常に１減少するようにもできる。増減量は、すべてのＳＭＣの値が所定の範囲に収まるよう制限を設けてもよい。
【００２２】
図４は、本発明のある実施形態に基づく、ＳＭＣの値を更新するプロセスの代表例としての流れ図である。ブロック４１０では、ＳＭＣ更新機構の初期化部によってメソッドが同定される。ブロック４２０では、同定されたメソッドについてのＳＭＣは、初期化部によって初期値（たとえば０）が設定される。ブロック４３０では、そのメソッドが先にリサイクルされて再コンパイルしているのかどうかの判断がなされる。そのメソッドが再コンパイルであれば、ブロック４４０で、そのメソッドのＳＭＣの値はある第一の数だけ増加する。そうでなければ、ブロック４５０で、そのメソッドがＣＧＣの間存命かどうかについてさらなる判断がなされる。そのメソッドが優先度に基づくＣＣＭの間存命であれば、そのメソッドのＳＭＣの値はある第二の数だけ増加する。そうでなければ、そのメソッドのＳＭＣはある第三の数だけ減少する。第一、第二、第三の数は同じでもいいし、違っていてもよい。ある実施形態では、第一の数は５、第二の数は１、第三の数は１でよい。さらに、ブロック４３０と４５０の順番は逆にしたり、両ブロックを同時進行させることもできる。ブロック４８０ではそのメソッドのＳＭＣの値は更新されることができる。またさらに、所定の限界値と比較して新しい値がある所定の範囲内に収まることを保証するようにもできる。ＳＭＣ値の更新は継続的なプロセスでもよい。その場合、ブロック４８０ののち、ブロック４３０、４５０で規定された条件のいずれかが満たされたかどうかについて継続的なチェックが必要となる。すべてのブロックにおける処理はＳＭＣの更新機構によって実行される。
【００２３】
図５は、本発明のある実施形態に基づく、優先度に基づくＣＣＭが生存メソッドカウンタの値に基づいて選択的ガーベジコレクションを通じて行われるプロセスの代表例としての流れ図である。ブロック５１０でＪＶＭがプログラムの実行を開始する。ブロック５２０では、優先度に基づくＣＣＭのトリガー条件が満たされたかどうかの判断が生存メソッド決定機構３５０によってなされる。もしトリガー条件が満たされていたら、生存メソッド決定機構がガーベジ再生機構３２０に、ブロック５３０の選択的ＣＧＣを行うよう指示する。ブロック５５０では、優先度に基づくＣＣＭのストップ条件が満たされたかどうかの判断が生存メソッド決定機構によってなされる。もしストップ条件が満たされていれば、選択的ＣＧＣはストップし、ＪＶＭはブロック５６０でプログラムの実行を続ける。そうでなければ、ブロック５３０でさらなる選択的ＣＧＣが行われる。ある実施形態では、ブロック５３０と５５０は組み合わせることもできる。生存メソッド決定機構は継続的に優先度に基づくＣＣＭのトリガー条件が満たされているかどうかを監視する必要がある。
【００２４】
本発明の実施例について図１〜７のブロック図および流れ図を参照しつつ記述しているが、通常の技量をもった当業者であれば、本発明を実施するために代わりに使いうる方法はほかにも数多くあることはすぐ理解できることであろう。たとえば、流れ図におけるブロックの実行順序は変えうるし、記載されているブロック図や流れ図のブロックの一部は変更したり消去したり組み合わせたりしうる。
【００２５】
本発明の恩恵を示すために、本発明を記述するのにＪａｖａ（登録商標）プログラミング言語、ＪＶＭ、ネイティブコードのためのコードキャッシュを用いている。実は、本発明はＪａｖａ（登録商標）プログラミング言語、ＪＶＭ、あるいはネイティブコードのためのコードキャッシュに限定されるよう意図されたものではない。本発明は、他のプラットフォームによらないプログラミング言語、他のシステム、他のキャッシュシステムについても、キャッシュ管理の効率を改善し、それによりシステム全体のパフォーマンスを改善するために用いることができる。
【００２６】
以上において、本発明のさまざまな側面が記述されてきた。本発明を深く理解できるよう、説明のために特定の数、システム、構成を述べもした。しかし、本開示を受ける当業者には、本発明が特定の細部に関わりなく実施できることは明らかである。逆に、よく知られた機能、構成要素、モジュールについては、本発明をぼかすのを避けるため、省略したり、単純化したり、組み合わせたり、分割したりもした。
【００２７】
本発明の実施形態は、いかなるコンピューティングプラットフォーム（ハードウェアおよびオペレーティング・システムを含む）上で実装してもよい。
【００２８】
本発明の実施形態がソフトウェアによって実装される場合、そのソフトウェアは、記憶媒体または記憶装置（たとえば、ハードディスクドライブ、フロッピー（登録商標）ディスクドライブ、読み出し専用メモリ（ＲＯＭ）、ＣＤ−ＲＯＭ装置、フラッシュメモリ装置、デジタル多用途ディスク（ＤＶＤ）、その他の記憶装置）上に保存されているものでもよい。そのようなソフトウェアは汎用または特殊目的のプログラム可能な処理システムによって読み込み可能で、該処理システムによって前記記憶媒体または記憶装置が読まれたときに、該処理システムを動作させ、ここに記載された諸手続きを実行させるよう構成する。本発明の実施形態はまた、処理システムと一緒に使うよう構成された機械可読記憶媒体として実装されるものとも考えられる。そのように構成された該記憶媒体は、処理システムを、ここに記載された機能を実行するための個別的で所定の仕方で動作させる。
【００２９】
本発明は解説のための実施形態を参照しつつ説明されてきたが、その説明は限定的な意味で解釈されることを意図したものではない。解説のための実施形態のさまざまな修正、また本発明のその他の実施形態は、本発明が関係する当業者には明らかであり、本発明の精神と範囲内にあると考えられるものである。
【図面の簡単な説明】
【００３０】
【図１】本発明のある実施形態に基づく、Ｊａｖａ（登録商標）プログラムのための、優先度に基づくコードキャッシュ管理機構を使ったシステム例の、高いレベルでの枠組みを示す図である。
【図２】本発明のある実施形態に基づく、プラットフォームによらないプログラムを走らせているシステムにおいて優先度に基づくコードキャッシュ管理を実行するプロセスの代表例としての流れ図である。
【図３】本発明のある実施形態に基づく、優先度に基づくコードキャッシュ管理機構およびコードガーベジコレクターの高いレベルでの機能ブロック図である。
【図４】本発明のある実施形態に基づく、生存メソッドカウンタを更新するプロセスの代表例としての流れ図である。
【図５】本発明のある実施形態に基づく、優先度に基づくコードキャッシュ管理が生存メソッドカウンタの値に基づいて選択的ガーベジコレクションを通じて行われるプロセスの代表例としての流れ図である。
【図６】本発明のある実施形態に基づく、優先度に基づくコードキャッシュ管理を行う一つの方法としての、生存コードを一箇所にまとめる過程の概略的な図解である。
【図７】本発明のある実施形態に基づく、優先度に基づくコードキャッシュ管理を行う一つの方法としての、生存コードを一箇所にまとめる過程に対して，直接呼出しと間接呼び出しがどのように関わってくるかの違いを対比させた概略的な図解である。
【符号の説明】
【００３１】
１１０  コアＪａｖａ（登録商標）仮想マシン
１２０  ＪＩＴコンパイラ
１３０  優先度に基づくコードキャッシュ管理機構
１４０  コードガーベジコレクター
２１０  バイトコード受け取り
２２０  バイトコードをネイティブコードにコンパイル
２３０  優先度に基づくＣＣＭを実行
２４０  ネイティブコードを実行
３１０  ルートセットスキャン機構
３２０  ガーベジ再生機構
３３０  生存メソッドカウンタ更新機構
３４０  生存メソッドカウンタ
３５０  生存メソッド決定機構
４１０  メソッドを同定
４２０  生存メソッドカウンタ（ＳＭＣ）を初期化
４３０  メソッドは再コンパイルか？
４４０  ＳＭＣ値をある第一の数だけ増加
４５０  メソッドはＣＣＭ中存命か？
４６０  ＳＭＣ値をある第二の数だけ増加
４７０  ＳＭＣ値をある第三の数だけ減少
４８０  ＳＭＣ値を更新
５１０  プログラムの実行開始
５２０  優先度に基づくＣＣＭのトリガー条件は満たされたか？
５３０  選択的コードガーベジコレクションを実行
５４０  寿命を終えたメソッドのＳＭＣ値
５５０  優先度に基づくＣＣＭのストップ条件は満たされたか？
５６０  プログラム実行の継続
【図１】
2006521597.tif 000002
【図２】
2006521597.tif 000003
【図３】
2006521597.tif 000004
【図４】
2006521597.tif 000005
【図５】
2006521597.tif 000006
【図６】
2006521597.tif 000007
【図７】
2006521597.tif 000008