(57)【要約】      （修正有）【課題】従来のスレッドローカルGCを改良して、フラグメンテーションを避ける技術を提供する。【解決手段】トランザクショナルメモリを実装した複数のプロセッサを含むメモリ管理装置であって、ポインタの書き込み操作の開始に応答してライトバリアを実行する際に、固有領域外にあって、固有領域内のオブジェクトを指すポインタを有するオブジェクトを書き込みログに登録して衝突検知の対象とするライトバリア処理部236と、衝突が検知されない限りにおいて、固有領域内の生きている共有オブジェクトを固有領域の外へコピーし、共有であるか否かに関わらず不要になったオブジェクトを回収するガーベッジコレクタ238とを含む。【選択図】図２
2011134202.tif 000002
【特許請求の範囲】
【請求項１】
トランザクショナルメモリを実装した複数のプロセッサを含むメモリ管理装置であって、
その一部が、動作中の各スレッドにそれぞれ対応する複数の固有領域として割り付けられるメモリと、
属性が共有である共有オブジェクトへの前記各スレッドによるポインタ書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトの属性を共有に変更し、前記ポインタの書き込み先の前記共有オブジェクトを含む各共有オブジェクトが、前記スレッドに対応する固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトの前記ポインタをトランザクショナルメモリの書き込みログに登録して衝突検知対象としかつ前記条件を満たす共有オブジェクトを前記スレッドのコピー用リストに登録するライトバリア処理部と、
前記複数の固有領域のいずれかが満杯になったことに応答して、満杯になった前記固有領域を割り付けられたスレッドに関して衝突が検知されない場合、該スレッドの前記コピー用リストに登録された各共有オブジェクトから到達可能な各オブジェクトを前記満杯になった固有領域の外へコピーし、前記コピー用リストに登録された前記各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングして前記トランザクショナルメモリの書き込みログに登録し、トランザクションをコミットし、およびその属性に関係なく不要になったオブジェクトを回収し、満杯になった前記固有領域を割り付けられたスレッドに関して衝突が検知される場合、前記固有領域についてその属性が共有でない不要になったオブジェクトを回収するガーベッジコレクタと、
を含むメモリ管理装置。
【請求項２】
前記衝突の検知に応答して、該衝突が検知された共有オブジェクトに関して、バッファリングされている前記書き込み、および登録されている前記トランザクショナルメモリの書き込みログを破棄し、前記衝突が検知された共有オブジェクトを含むコピー用リストを有するスレッドの固有領域内の共有オブジェクトのコピーを禁止する衝突ハンドラを更に含む、請求項１に記載のメモリ管理装置。
【請求項３】
前記衝突ハンドラは、前記ガーベッジコレクタによる処理の開始後かつ前記トランザクションのコミット前に衝突が検知された場合、前記ガーベッジコレクタに前記トランザクションのコミットまでの残りの処理をスキップさせ、属性が共有でない不要になったオブジェクトの回収から処理を開始させる、請求項２に記載のメモリ管理装置。
【請求項４】
前記ライトバリア処理部は、前記条件を満たす共有オブジェクトの代わりに、該条件を満たす共有オブジェクトが直接参照する前記固有領域内のオブジェクトを、トランザクショナルメモリの書き込みログに登録して衝突検知対象とし、かつ前記スレッドのコピー用リストに登録し、前記ガーベッジコレクタは、衝突が検知されない場合に、属性に関係なく不要になったオブジェクトを回収する代わりに、前記コピー用リストに登録された前記各オブジェクトを除いて、属性に関係なく不要になったオブジェクトを回収する、請求項１に記載のメモリ管理装置。
【請求項５】
トランザクショナルメモリを実装した複数のプロセッサを含むメモリ管理装置であって、
その一部が、動作中の各スレッドにそれぞれ対応する複数の固有領域として割り付けられるメモリと、
属性が共有である共有オブジェクトへの前記各スレッドによるポインタ書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトの属性を共有に変更し、前記ポインタの書き込み先の前記共有オブジェクトを含む各共有オブジェクトが、前記スレッドに対応する固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトの前記ポインタをトランザクショナルメモリの書き込みログに登録して衝突検知対象としかつ前記条件を満たす共有オブジェクトを前記スレッドのコピー用リストに登録するライトバリア処理部と、
衝突の検知に応答して、該衝突が検知された共有オブジェクトに関して、バッファリングされている書き込み、登録されている前記トランザクショナルメモリの書き込みログを破棄し、および前記コピー用リスト内の前記衝突が検知された共有オブジェクトから到達可能な各オブジェクトにマークを付ける衝突ハンドラと、
前記複数の固有領域のいずれかが満杯になったことに応答して、該固有領域を割り付けられたスレッドの前記コピー用リストに登録された各共有オブジェクトから到達可能な前記マークの付いていない各オブジェクトを前記満杯になった固有領域の外へコピーし、前記コピー用リストに登録された前記各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングして前記トランザクショナルメモリの書き込みログに登録し、トランザクションをコミットし、および前記マークの付いた前記各オブジェクトを除く不要になったオブジェクトを回収するガーベッジコレクタと、
を含むメモリ管理装置。
【請求項６】
トランザクショナルメモリを実装した複数のプロセッサと、その一部が、動作中の各スレッドにそれぞれ対応する複数の固有領域として割り付けられるメモリとを含むメモリ管理装置において実行されるメモリ管理方法であって、
ライトバリア・モジュールを呼び出すスレッドを実行するプロセッサが、属性が共有である共有オブジェクトへの前記スレッドによるポインタ書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトを、その属性を変更することにより共有オブジェクトにするステップと、
前記ライトバリア・モジュールを呼び出す前記スレッドを実行する前記プロセッサが、前記属性の変更に応答して、前記ポインタの書き込み先の前記共有オブジェクトを含む各共有オブジェクトが、前記スレッドに対応する固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトの前記ポインタをトランザクショナルメモリの書き込みログに登録して衝突検知対象としかつ前記条件を満たす共有オブジェクトを前記スレッドのコピー用リストに登録するステップと、
ガーベッジコレクタを呼び出す前記スレッドを実行する前記プロセッサが、該スレッドに割り付けられた固有領域が満杯になったことに応答して、前記スレッドに関して衝突が検知されない場合、前記スレッドの前記コピー用リストに登録された各共有オブジェクトから到達可能な各オブジェクトを前記満杯になった固有領域の外へコピーし、前記コピー用リストに登録された前記各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングして前記トランザクショナルメモリの書き込みログに登録し、トランザクションをコミットし、およびその属性に関係なく不要になったオブジェクトを回収し、前記スレッドに関して衝突が検知される場合、前記固有領域についてその属性が共有でない不要になったオブジェクトを回収するステップと、
を含むメモリ管理方法。
【請求項７】
衝突ハンドラを呼び出す前記スレッドを実行する前記プロセッサが、前記衝突の検知に応答して、該衝突が検知された共有オブジェクトに関して、バッファリングされている前記書き込み、および登録されている前記トランザクショナルメモリの書き込みログを破棄し、前記スレッドに割り付けられた固有領域内の共有オブジェクトのコピーを禁止するステップを更に含む、請求項６に記載のメモリ管理方法。
【請求項８】
前記ライトバリア・モジュールを呼び出す前記スレッドを実行する前記プロセッサが、前記条件を満たす共有オブジェクトの代わりに、該条件を満たす共有オブジェクトが直接参照する前記固有領域内のオブジェクトを、トランザクショナルメモリの書き込みログに登録して衝突検知対象とし、かつ前記スレッドのコピー用リストに登録し、前記ガーベッジコレクタを呼び出す前記スレッドを実行する前記プロセッサが、衝突が検知されない場合に、属性に関係なく不要になったオブジェクトを回収する代わりに、前記コピー用リストに登録された前記各オブジェクトを除いて、属性に関係なく不要になったオブジェクトを回収する、請求項６に記載のメモリ管理方法。
【請求項９】
トランザクショナルメモリを実装した複数のプロセッサと、その一部が、動作中の各スレッドにそれぞれ対応する複数の固有領域として割り付けられるメモリとを含むメモリ管理装置において実行されるメモリ管理プログラムであって、
前記複数のプロセッサ各々に、
該プロセッサ上で動作するスレッドによる属性が共有である共有オブジェクトへのポインタ書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトを、その属性を変更することにより共有オブジェクトにするステップ、および
前記属性の変更に応答して、前記ポインタの書き込み先の前記共有オブジェクトを含む各共有オブジェクトが、前記スレッドに対応する固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトの前記ポインタをトランザクショナルメモリの書き込みログに登録して衝突検知対象としかつ前記条件を満たす共有オブジェクトを前記スレッドのコピー用リストに登録するステップとを実行させるライトバリア・モジュール、ならびに、
前記複数のプロセッサ各々に、
該プロセッサ上で動作するスレッドに割り付けられた固有領域が満杯になったことに応答して、前記スレッドに関して衝突が検知されない場合、前記スレッドの前記コピー用リストに登録された各共有オブジェクトから到達可能な各オブジェクトを前記満杯になった固有領域の外へコピーし、前記コピー用リストに登録された前記各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングして前記トランザクショナルメモリの書き込みログに登録し、トランザクションをコミットし、およびその属性に関係なく不要になったオブジェクトを回収し、前記スレッドに関して衝突が検知される場合、前記固有領域についてその属性が共有でない不要になったオブジェクトを回収するステップを実行させるガーベッジコレクタ、
を含むメモリ管理プログラム。
【請求項１０】
前記ライトバリア・モジュールは、前記複数のプロセッサ各々に、前記条件を満たす共有オブジェクトの代わりに、該条件を満たす共有オブジェクトが直接参照する前記固有領域内のオブジェクトを、トランザクショナルメモリの書き込みログに登録して衝突検知対象とし、かつ前記スレッドのコピー用リストに登録するステップを実行させ、前記ガーベッジコレクタは、前記複数のプロセッサ各々に、衝突が検知されない場合に、属性に関係なく不要になったオブジェクトを回収する代わりに、前記コピー用リストに登録された前記各オブジェクトを除いて、属性に関係なく不要になったオブジェクトを回収させる、請求項９に記載のメモリ管理プログラム。
【請求項１１】
トランザクショナルメモリを実装した複数のプロセッサと、その一部が、動作中の各スレッドにそれぞれ対応する複数の固有領域として割り付けられるメモリとを含むメモリ管理装置において実行されるメモリ管理プログラムであって、
前記複数のプロセッサ各々に、
該プロセッサ上で動作するスレッドによる属性が共有である共有オブジェクトへのポインタ書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトを、その属性を変更することにより共有オブジェクトにするステップ、および
前記属性の変更に応答して、前記ポインタの書き込み先の前記共有オブジェクトを含む各共有オブジェクトが、前記スレッドに対応する固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトの前記ポインタをトランザクショナルメモリの書き込みログに登録して衝突検知対象としかつ前記条件を満たす共有オブジェクトを前記スレッドのコピー用リストに登録するステップとを実行させるライトバリア・モジュール、    
前記複数のプロセッサ各々に、
該プロセッサ上で動作するスレッドへの衝突検知の通知に応答して、該衝突が検知された共有オブジェクトに関して、バッファリングされている書き込み、登録されている前記トランザクショナルメモリの書き込みログを破棄し、および前記コピー用リスト内の前記衝突が検知された共有オブジェクトから到達可能な各オブジェクトにマークを付けるステップを実行させる衝突ハンドラ、および
前記複数のプロセッサ各々に、
該プロセッサ上で動作するスレッドに割り付けられた固有領域が満杯になったことに応答して、前記スレッドの前記コピー用リストに登録された各共有オブジェクトから到達可能な前記マークの付いていない各オブジェクトを前記満杯になった固有領域の外へコピーし、前記コピー用リストに登録された前記各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングして前記トランザクショナルメモリの書き込みログに登録し、トランザクションをコミットし、前記マークの付いた前記各共有オブジェクトを除く不要になったオブジェクトを回収させるガーベッジコレクタ、
を含むメモリ管理プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スレッドごと固有のメモリ領域を用意し、固有メモリ領域ごと、他のスレッドによりアクセス可能なオブジェクト以外のオブジェクトを対象として不要になったオブジェクトを回収するガーベッジコレクションの改良技術に関する。
【背景技術】
【０００２】
プログラムが実行中に割り付けたオブジェクトを安全かつ自動で回収するためにガーベッジコレクション（Garbage Collection、以下単にGCという）が広く用いられている。GCを、複数のスレッドが平行に動作し、記憶領域を共有するマルチスレッドアプリケーションにおいて行うためには、全てのアプリケーションスレッド（以下、単にスレッドという）を停止しなければならない。このことは処理の応答性の低下を意味する。従って、Webアプリケーション等の応答性が重要となるアプリケーションではGCによる停止時間の発生が問題となる。
【０００３】
上記問題を解決する従来技術として、特許文献１が存在する。特許文献１は、アプリケーションプログラムを構成するメソッドが実行開始された場合にメソッド用メモリ領域を確保し、確保したメソッド用メモリ領域とメソッドとの対応関係及び確保した各メソッド用メモリ領域同士の確保時期の先後関係を記録する確保手段と、メソッド用メモリ領域中のあるオブジェクトが当該メソッド用メモリ領域より先に確保されたメソッド用メモリ領域から参照されている場合に、当該オブジェクトを当該先に確保されたメソッド用メモリ領域に移動させる移動手段と、メソッドが実行終了した場合に当該メソッドに対応するメソッド用メモリ領域を解放する解放手段を備えるガーベッジコレクション装置を開示する。
【０００４】
上記問題を解決する他の従来技術として、特許文献２が存在する。特許文献２は、ガーベジコレクションの開始に先だって、前記プログラムが前記一方の空間に配置されるオブジェクトを参照・更新することを禁止する参照更新禁止手段と、前記ガーベジコレクションが実行され、前記プログラムが参照・更新することを禁止されたオブジェクトを参照・更新する処理を行う場合に、この処理に支障のないような例外処理を行う例外処理手段と、を備えた情報処理装置において、前記例外処理として、前記プログラムが参照・更新する、前記一方の空間では参照・更新が禁止されたオブジェクトを、前記他方の空間に複写し、また、このオブジェクトに対するポインタを前記他方の空間におけるポインタに変更する処理を行う技術を開示する。
【０００５】
上記問題を解決する更に他の従来技術として、ほとんどのオブジェクトは死ぬまでにそれを割り付けたスレッド以外からは到達不可能であるということに注目して、スレッド全ては止めずにオブジェクトの回収を行う手法（以下、スレッドローカルGCという）が存在する（非特許文献１参照）。スレッドローカルGCでは、スレッドごとにオブジェクトを割り付ける固有領域が用意され、また、各オブジェクトには、複数のスレッドから到達可能であるか否かを示す属性（以下、共有オブジェクト属性とも言う）が設定される。そして、スレッドがポインタをオブジェクトのフィールドに書き込む際に、ソフトウェアライトバリアが実行され、他のスレッドから参照される可能性のあるオブジェクト（以下、共有オブジェクトという）の属性が共有に変更される。  
【０００６】
その後いずれかの固有領域が満杯になるとGCが起動され、満杯になった固有領域に対し、属性が共有でないオブジェクトを対象として不要となったオブジェクトの回収が行われる。このようにスレッドローカルGCでは、他のスレッドから参照される可能性のある共有オブジェクトをその属性により識別して回収の対象から外すので、他のスレッドを停止する必要がない。
【０００７】
しかしスレッドローカルGCでは、共有オブジェクトは回収することができず、また、他のスレッドにより参照される可能性があることから他の領域へコピーすることもできない。このため、スレッドローカルGCでは、固有領域内でフラグメンテーションが起きる。１回のスレッドローカルGCで固有領域に残る共有オブジェクトの数は僅かであることが多いが、同じ固有領域が何回も使い回されるうちにフラグメンテーションは激しくなり、別の固有領域を割り付ける必要が出てくる。
【０００８】
上記フラグメンテーションの問題を解決する従来技術として、特許文献３が存在する。特許文献３は、プログラムに対応して生成され、平行動作する１つ以上のスレッドの各々に対応するスレッド固有領域とスレッドが共有する大域領域とをメモリに設け、スレッドの各々が固有に参照するデータをスレッド固有領域に配置し、スレッドの各々以外から参照されるデータを大域領域に配置し、スレッド固有領域に配置したデータが、スレッドの各々以外から参照される場合、その参照に先立って、参照される可能性のあるデータを大域領域に移動する技術を開示する。
【０００９】
上記フラグメンテーションの問題を解決する他の従来技術として、特許文献４が存在する。特許文献４は、アプリケーションプログラムが生成するオブジェクトを、１つのスレッドと対応付けられたスレッドローカルヒープに生成し、上記生成されたオブジェクトを参照することができるスレッドが変化することに応じて、適切なスレッドグループヒープ（所定のオブジェクトを参照可能なスレッドの集合に対応するスレッドグループヒープ）に移動させ、不要になったオブジェクトを回収する際に、上記不要になったオブジェクトを参照することができるスレッドのみを停止する技術を開示する。
【００１０】
その他、コピー式並行GCを、共有オブジェクトに対する同期オーバーヘッドを削減する手法として広く研究されているトランザクショナルメモリと組み合わせる手法を提案する従来技術も存在する（非特許文献２参照）。
【先行技術文献】
【特許文献】
【００１１】
【特許文献１】特許第３９３９９７５号公報
【特許文献２】特開２００１―１８４２５４号公報
【特許文献３】特開２００９―３７５４６号公報
【特許文献４】特開２００４―２４６７５３号公報
【非特許文献】
【００１２】
【非特許文献１】T. Domani他, “Thread-Local Heaps for Java”, In Proceedingsof theInternational Symposium on Memory Management, pp.76-87, 2002.
【非特許文献２】Phil McGachey他, “Concurrent GCleveraging transactional memory”, In Proceedings of the 13th ACM SIGPLAN Symposium on Principles andpractice of parallel programming, pp. 217-226, 2008.
【発明の概要】
【発明が解決しようとする課題】
【００１３】
しかしながら、上記従来技術にはそれぞれ次のような問題がある。即ち、メソッド呼出しごとにオブジェクト割り付け用の領域を用意する特許文献１の手法では、効率的にオブジェクトを回収できるのは、オブジェクトの寿命がメソッドの寿命より短い場合のみである。また、コピー式並行GCの一手法である特許文献２の手法は、リードバリアが発動する頻度が高く、また、from領域からto領域へオブジェクトをコピーする際にOSのページ保護機構を用いてfrom領域に対するリードバリアを実現しているため、発動した時のオーバーヘッドが大きい。
【００１４】
また、非特許文献１が開示するスレッドローカルGCでは、上述したようにフラグメンテーションの問題がある。特許文献３の手法は、このフラグメンテーションの問題解決を目的とする。しかし、特許文献３の手法では、オブジェクトは、複数のスレッドから指された時点で共有オブジェクトと見なされるため、大域GCの回数が増して全てのスレッドを止める頻度が増してしまう。また、特許文献４が開示する手法では、オブジェクトを参照する可能性のあるスレッドの集合を管理することによりGCの停止時間は短くなるが、GCのたびに全てのスレッドを止める必要がある。
【００１５】
また、トランザクショナルメモリとコピー式並行GCとの組み合わせを提案する非特許文献２は、ソフトウェアトランザクショナルメモリにおけるリード・ライドバリアと、コピー式並行GCにおけるソフトウェアリード・ライトバリアが似ている機能を持っていることから、トランザクショナルメモリとコピー式並行GCを組み合わせてもオーバーヘッドの増加が少ないことを述べるのみである。
【００１６】
この発明は、上記の問題点を解決するためになされたものであって、従来のスレッドローカルGCを改良して、フラグメンテーションを避ける技術を提供することを目的とする。
【課題を解決するための手段】
【００１７】
本願発明者は、従来のスレッドローカルGC について研究をし、保守的過ぎる共有オブジェクト属性の判定に問題があることを突き止めた。即ち、従来のスレッドローカルGCでは、他のスレッドから参照される可能性が生じた時点で、オブジェクトの属性は共有に変更される。しかし厳密には、実際にオブジェクトが読み書きされるまでオブジェクトは共有されない。従って実際に読み書きされるまで、オブジェクトの属性はスレッドローカルのままとすべきである。しかしながら、あるスレッドが割り付けたオブジェクトを他のスレッドが読書きしたことを低コストで検知する手法はこれまで存在しなかった。
【００１８】
そこで本願発明者は更に研究を進め、トランザクショナルメモリにおける衝突検知（conflict detection）とコミット前におけるトランザクション中のバッファリングの仕組みに着目し、スレッドローカルGCにおいて、トランザクショナルメモリを利用して他のスレッドからの読書きを検知し、該読書きを検知しない限りにおいて、共有オブジェクトを注目スレッドの固有のヒープ領域外にコピーしてフラグメンテーションを避けるというアイデアに想到した。
【００１９】
即ち、上記課題を解決するために、本発明の第１の態様においては、トランザクショナルメモリを実装した複数のプロセッサを含むメモリ管理装置であって、その一部が、動作中の各スレッドにそれぞれ対応する複数の固有領域として割り付けられるメモリと、属性が共有である共有オブジェクトへの前記各スレッドによるポインタ書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトの属性を共有に変更し、前記ポインタの書き込み先の前記共有オブジェクトを含む各共有オブジェクトが、前記スレッドに対応する固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトの前記ポインタをトランザクショナルメモリの書き込みログに登録して衝突検知対象としかつ前記条件を満たす共有オブジェクトを前記スレッドのコピー用リストに登録するライトバリア処理部と、前記複数の固有領域のいずれかが満杯になったことに応答して、満杯になった前記固有領域を割り付けられたスレッドに関して衝突が検知されない場合、前記スレッドの前記コピー用リストに登録された各共有オブジェクトから到達可能な各オブジェクトを前記満杯になった固有領域の外へコピーし、前記コピー用リストに登録された前記各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングして前記トランザクショナルメモリの書き込みログに登録し、トランザクションをコミットし、およびその属性に関係なく不要になったオブジェクトを回収し、満杯になった前記固有領域を割り付けられたスレッドに関して衝突が検知される場合、前記固有領域についてその属性が共有でない不要になったオブジェクトを回収するガーベッジコレクタと、を含むメモリ管理装置を提供する。
【００２０】
好ましくは、上記メモリ管理装置は更に、前記衝突の検知に応答して、該衝突が検知された共有オブジェクトに関して、バッファリングされている前記書き込み、および登録されている前記トランザクショナルメモリの書き込みログを破棄し、および、前記衝突が検知された共有オブジェクトを含むコピー用リストを有するスレッドの固有領域内の共有オブジェクトのコピーを禁止する衝突ハンドラを含む。なお、衝突ハンドラは、衝突の検知に応答して、更に、該衝突が検知された共有オブジェクトを含むコピー用リストを空にしてもよい。また、上記コピーの禁止は、上記固有領域ごとに禁止フラグを設け、これをセットすることにより行ってもよい。
【００２１】
より好ましくは、前記衝突ハンドラは、前記ガーベッジコレクタによる処理の開始後かつ前記トランザクションのコミット前に衝突が検知された場合、前記ガーベッジコレクタに前記トランザクションのコミットまでの残りの処理をスキップさせ、属性が共有でない不要になったオブジェクトのみを回収させる。
【００２２】
また好ましくは、前記ライトバリア処理部は、前記条件を満たす共有オブジェクトの代わりに、該条件を満たす共有オブジェクトが直接参照する前記固有領域内のオブジェクトを、トランザクショナルメモリの書き込みログに登録して衝突検知対象とし、かつ前記スレッドのコピー用リストに登録する。そして、前記ガーベッジコレクタは、衝突が検知されない場合に属性に関係なく不要になったオブジェクトを回収する代わりに、衝突が検知されない場合、前記コピー用リストに登録された前記各オブジェクトを除いて、属性に関係なく不要になったオブジェクトを回収する。
【００２３】
上記課題を解決するために、本発明の第２の態様においては、トランザクショナルメモリを実装した複数のプロセッサを含むメモリ管理装置であって、その一部が、動作中の各スレッドにそれぞれ対応する複数の固有領域として割り付けられるメモリと、属性が共有である共有オブジェクトへの前記各スレッドによるポインタ書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトの属性を共有に変更し、前記ポインタの書き込み先の前記共有オブジェクトを含む各共有オブジェクトが、前記スレッドに対応する固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトの前記ポインタをトランザクショナルメモリの書き込みログに登録して衝突検知対象としかつ前記条件を満たす共有オブジェクトを前記スレッドのコピー用リストに登録するライトバリア処理部と、衝突の検知に応答して、該衝突が検知された共有オブジェクトに関して、バッファリングされている書き込み、登録されている前記トランザクショナルメモリの書き込みログを破棄し、および前記コピー用リスト内の前記衝突が検知された共有オブジェクトから到達可能な各オブジェクトにマークを付ける衝突ハンドラと、前記複数の固有領域のいずれかが満杯になったことに応答して、該固有領域を割り付けられたスレッドの前記コピー用リストに登録された各共有オブジェクトから到達可能な前記マークの付いていない各オブジェクトを前記満杯になった固有領域の外へコピーし、前記コピー用リストに登録された前記各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングして前記トランザクショナルメモリの書き込みログに登録し、トランザクションをコミットし、および、前記マークの付いた前記各オブジェクトを除く不要になったオブジェクトを回収するガーベッジコレクタと、を含むメモリ管理装置を提供する。
【００２４】
以上、メモリ管理装置として本発明を説明したが、本発明は、トランザクショナルメモリを実装した複数のプロセッサと、その一部が、動作中の各スレッドにそれぞれ対応する複数の固有領域として割り付けられるメモリとを含むコンピュータ・システムにより実施される、メモリ管理方法およびメモリ管理プログラムとして把握することもできる。
【発明の効果】
【００２５】
本願発明によれば、トランザクショナルメモリの衝突検知とバッファリングの仕組みを利用して、実際に他のスレッドからアクセスがあるまでは、共有オブジェクトをスレッドローカルなオブジェクトとして扱い固有領域外へコピーするので、フラグメンテーションの問題が大きく改善され、また、全てのスレッドを停止する大域GCの頻度も少なくなり停止時間が大幅に減る。本発明のその他の効果については、各実施の形態の記載から理解される。
【図面の簡単な説明】
【００２６】
【図１】図１（ａ）は、本発明を適用可能なコンピュータ・システムの主要構成要素を示す上位レベルの構成図である。図１（ｂ）は、図１（ａ）に示すコンピュータ・システムの典型的ノードの主要ハードウェア構成要素を示す構成図である。
【図２】図２は、本発明の実施形態に係るメモリ管理装置２００の機能ブロック図である。
【図３】図３は、本発明の実施形態に係るライトバリア処理部２３６による処理の流れの一例を示すフローチャートである。
【図４】図４は、本発明の実施形態に係るガーベッジコレクタ２４０による処理の流れの一例を示すフローチャートである。
【図５】図５は、本発明の実施形態に係る衝突ハンドラ２３８による処理の流れの一例を示すフローチャートである。
【図６】図６（ａ）〜（ｅ）は各々、衝突が検知されない場合の、本発明の実施形態に係る改良されたスレッドローカルGCの動作例を示す図である。
【図７】図７（ａ）〜（ｄ）は各々、衝突が検知された場合の、本発明の実施形態に係る改良されたスレッドローカルGCの動作例を示す図である。
【図８】従来のスレッドローカルGCと本発明の実施形態に係る改良されたスレッドローカルGCの動作を、オブジェクトのカテゴリごとにまとめた表を示す。
【図９】あるGCから次のGCまでに新たに生成されるオブジェクトおける、各カテゴリのオブジェクトが占める割合示す図である。
【図１０】図１０（ａ）〜（ｃ）は各々、従来のレッドローカルGCの動作例を示す図である。
【発明を実施するための形態】
【００２７】
以下、本発明を実施するための形態を図面に基づいて詳細に説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。なお、実施の形態の説明の全体を通じて同じ要素には同じ番号を付している。
【００２８】
図１（ａ）は、本発明を適用可能なコンピュータ・システム１００の主要構成要素を示す上位レベルの構成図である。コンピュータ・システム１００は複数のノード１０２、１０４、１０６、および１０８を含む。なお、図１のシステムの例には４つのノードを示すが、ノード数は、１つでもよく４つに制限されないことを理解されたい。各ノードは、任意のノードを他の任意のノードとやりとりできるようにする、ノード間通信ネットワーク１１０によって接続される。ノード間通信ネットワーク１１０の目的は、各装置がノード境界をまたいで通信できるようにすること、具体的には、任意のノード中のプロセッサが、他の任意のノード中にあるメモリにアクセスできるようにすることである。
【００２９】
好ましい実施形態では、ノード間通信ネットワーク１１０は、ファブリックバスであってよい。これに代えてノード間通信ネットワーク１１０として、既存の、または今後開発される様々な代替手段を使用することもできることは言うまでもない。
【００３０】
図１（ｂ）は、好ましい実施形態による、コンピュータ・システム１００の典型的ノードの主要ハードウェア構成要素の一例を示す構成図である。本明細書に含まれる記述の一貫性を保つために、ノードを総称して参照番号１０２とするが、これはノード１０２、１０４、１０６、および１０８のいずれでもあり得ることを理解されたい。ノード１０２は、分散メイン・メモリからの命令および他のデータに基づいて基本的な機械処理機能を実施する複数の中央処理装置（CPU）１２０および１２４を含む。なお本明細書では、プロセッサという用語はCPUと同義であるとしてこれらを区別せずに使用する。各CPU１２０および１２４は、データおよび命令の一時的記憶のためにそれぞれのキャッシュ１２２および１２６を含み、あるいはそれを制御する。
【００３１】
大規模なマルチプロセッサ・コンピュータ・システムでは、通常キャッシュは、複数のレベルで複数の構造として存在する。例えばCPUは、そのCPUで実行される命令の記憶専用のレベル１キャッシュ（Ｌ１命令キャッシュ）、そのCPUによって操作される命令以外のデータの記憶専用の、物理的に別個のレベル１キャッシュ（L1データ・キャッシュ）、および命令と他のデータの両方を記憶し、L1命令キャッシュおよびL1データ・キャッシュに補給するために使用されるレベル２キャッシュ（L2キャッシュ）を含むことができる。
【００３２】
図１（ｂ）では、上記１つまたは複数のキャッシュ構造は、それぞれのプロセッサごとに単一ブロック１２２および１２６として単純化した形で表されているが、他の多くの変形形態が可能であることを理解されたい。また本発明を適用可能なコンピュータ・システム１００のノード１０２に含まれるCPU１２０、１２４、およびキャッシュ１２２、１２６は、トランザクショナルメモリをハードウェア実装する。
【００３３】
トランザクショナルメモリは、共有オブジェクトに対する同期オーバヘッドを削減する手法として広く研究されており、商用CPUではハードウェア実装トランザクショナルメモリが提供されつつある。トランザクショナルメモリを用いる場合、まずプログラムにおいてトランザクションの範囲を指定する。そしてスレッドは、指定されたトランザクションを実行する際、共有オブジェクトへの読み込みと書き込みのログをそれぞれとる。これにより、トランザクション実行中に他のスレッドが同じ共有オブジェクトを読み書きし、かついずれかのスレッドの操作が書き込みであると、衝突が検知され、トランザクションの失敗がスレッドに通知される。また、トランザクション中の書き込みはバッファリングされ、コミットまで他のスレッドからは見えない。
【００３４】
ハードウェア実装のトランザクショナルメモリでは、CPUキャッシュとコヒーレンスプロトコルが利用され、低コストでキャッシュライン単位の衝突検知と書き込みバッファリングが可能となる。但し、ハードウェア実装のトランザクショナルメモリでは、トランザクションの範囲内で読み書きできるデータの総量はCPUキャッシュサイズにより制限される。このため従来のトランザクショナルメモリの利用のほとんどが、共有オブジェクトへの読み書きを行う比較的短いトランザクション同士の並列性をあげるためであった。本願発明では、上記トランザクショナルメモリにおける衝突検知とバッファリングの仕組みを、スレッドローカルGCにおける他のスレッドによる共有オブジェクトへのアクセス検知に利用し、それによって、注目スレッド固有のヒープ領域外への共有オブジェクトのコピーを可能とする。なお、トランザクショナルメモリのハードウェア実装方法は公知の技術であり、またそれ自体は本発明の要旨ではないのでこれ以上の説明は省略する。
【００３５】
コンピュータ・システム１００は、分散メイン・メモリを利用し、ノード１０２ごとに別個のローカル・メモリ１２８を含む。コンピュータ・システム１００内のアドレス指定可能なメイン・メモリの合計は、各ノード中のアドレス指定可能なローカル・メモリ１２８の総和である。コンピュータ・システム１００全体のすべてのＣＰＵは、同じアドレス指定可能な分散メイン・メモリを共用する。したがって、分散メイン・メモリの実アドレス空間は、コンピュータ・システム１００全体で一定であり、ローカル・メモリ１２８中の任意のメモリ位置は、すべてのプロセッサおよびすべてのノードにとって同じ、一意の実アドレスを持つ。  
【００３６】
ノード間インターフェイス・ユニット１３０は、ノード１０２をノード間通信ネットワーク１１０に接続し、それによってノード１０２がコンピュータ・システム１００内の他のノードとやりとりできるようにする。ノード間インターフェイス・ユニット１３０は、ノード間で渡されるデータの一時記憶のためのキャッシュまたはバッファを含んでよい。
【００３７】
入出力インターフェイス・ユニット１３２は、１以上の入出力バスを介した１以上の入出力装置（図（ｂ）では記憶装置１３４）への通信を提供する。入出力バスは、直接アクセス記憶装置（ＤＡＳＤ）、テープ装置、ワークステーション、印刷装置、および専用の通信線またはネットワークを介した遠隔装置または他のコンピュータ・システムとの通信のための遠隔通信アダプタなど、従来の入出力装置との
通信に適したどんなタイプのものでもよい。例えば、入出力バスは、業界標準のＰＣＩバスとすることもできる。なお、すべてのノード１０２が入出力インターフェイス・ユニット１３２や接続された入出力装置を含む必要はないことを理解されたい。
【００３８】
内部ノード・バス１３６は、ノード１０２の各種構成要素間の通信を提供する。具体的には、内部ノード・バス１３６は、ＣＰＵ１２０および１２４によって発せられたメモリ・アクセスに応答して、ローカル・メモリ１２８とそれぞれのＣＰＵ１２０および１２４のキャッシュ１２２および１２６との間でデータを転送する。ローカル・メモリ１２８でのロジックを監視して、ノード間インターフェイス・ユニット１３０、または内部ノード・バス１３６自体、あるいはその両方は、メモリ・アクセスで要求された個々の実アドレスが、ノード１０２のローカル・メモリ１２８に含まれているか、それとも別の（遠隔）ノードのローカル・メモリに含まれているか判定し、場合に応じて、そのメモリ・アクセスを、ローカル・メモリ１２８、または遠隔ノードとの通信のためのノード間インターフェイス・ユニット１３０に送る。
【００３９】
図１（ａ）には４つのノードを備えるコンピュータ・システム１００が示されており、図１（ｂ） には２つのＣＰＵ および他の各種装置を備える典型的ノードが示されているが、図１（ａ）および図１（ｂ）は、コンピュータ・システムの１つの可能な構成の一例を示すためのものにすぎず、そうした構成での可能な装置の数およびタイプは異なることがあることを理解されたい。さらに、すべてのノードが同一であることも、すべてのノードが同数のＣＰＵまたは同量のアドレス指定可能なローカル・メモリを備えることも必要とされないことも理解されたい。
【００４０】
図２は、本発明の実施形態によるメモリ管理装置２００の機能ブロック図である。本発明に係るメモリ管理装置２００は、図１を参照して説明したコンピュータ・システムとしてのハードウェア２０５を用いて実現される。なお図２には、Java(登録商標）実行時環境としてのメモリ管理装置２００を示し、以下ではJava実行時環境を例に説明するが、本発明は、Common Language Runtime(CLR）等、プラットフォーム間の違いを吸収し、クラス・ライブラリやGC等のサービスを提供する他の共通実行時環境について適用可能なことを理解されたい。  
【００４１】
Java言語は、Sun Microsystems社によって作成された言語である。Javaソフトウェア・ツールおよびJava開発者ツールに関する情報は、オンラインＵＲＬ http://www.sun.com/javaで入手できる。Javaの使用とJavaアプリケーションおよびJavaアプレットの作成は、当技術分野において公知であるため本明細書では詳細な説明を省略する。ソフトウェア開発者によって書かれたJavaソース・コードは、特定のプラットフォーム用に設計されたフォーマットにコンパイルされるのではなく、実行時環境を有するすべてのシステムで実行できるバイト・コードという中間形式にコンパイルされる。Javaバイト・コードは後述するクラスファイル２０２として、入出力インターフェイス・ユニット１３２を介して、ローカル・ハード・ディスク（図１（ｂ）の記憶装置１３４を参照）や他のコンピュータ・システムからJava仮想マシン２２０へ移される。
【００４２】
Java仮想マシン２２０は、JavaアプリケーションまたはJavaアプレットの場合にはウェブ・ブラウザが、オペレーティング・システム２１０とその下層のハードウェア２０５に無関係に全てのシステムで走行できるようにするプラットフォームである。Java仮想マシン２２０は、マシンに依存しない命令であるJavaバイト・コードによって表現されるプログラムを受け取って、これをマシンに依存するネイティブの命令に変換する。そしてJava仮想マシン２２０は、変換したネイティブの命令を、図１（ｂ）を参照して上述したいずれかのノード内のプロセッサで直接またはオペレーティング・システム２１０を介して実行する。そのようなオペレーティング・システム２１０としては、例えばAIX(登録商標）オペレーティング・システムやLinux(商標）等のオペレーティング・システムがある。
【００４３】
Javaのソース・コードから生成されたJavaバイト・コードは、１つまたは複数のクラスに編成される。このクラスは、仮想マシン２２０ によるコンピュータ・プログラムの実行中に割り振られ、使用されるオブジェクトのテンプレートを表す。クラスは、実行可能バイト・コードとそのような実行可能バイト・コードが頼るデータの両方を含むクラスファイル２０２に編成され、該クラスファイル２０２はオブジェクトに関する他の情報を含んでもよい。このようなクラスファイル２０２は、Javaソース・コードに基づきJavaコンパイラによって生成される。Javaソース・コード、Javaコンパイラ、およびクラスファイルは当技術分野において公知であるため本明細書では詳細な説明を省略する。
【００４４】
クラスローダ２２２は、クラスファイル２０２内のJavaバイト・コードによって指定される所与の動作のために、クラス・ライブラリ２２４から１以上のJavaクラス・ライブラリを取り出す。そして、クラスローダ２２２は、クラスファイル２０２と取り出した１以上のJavaクラス・ライブラリを、実行エンジン２３０のメモリ２３４へ格納することにより動的にロードする。なおクラスローダ２２２は、メモリ２３４へ格納する前に、当技術分野で既知の方法によりクラス検証を実行して、Javaセキュリティに合致することを検証してもよい。
【００４５】
インタープリタ２３２は、クラスローダ２２２によるクラスファイル２０２のロードに応答して、各クラスファイル２０２に含まれるJavaバイト・コードを１つ１つ解釈しそれぞれに対応する動作を行う。これにより、１以上のスレッドがノード１０２内のプロセッサにより実行されることになる。
【００４６】
なお、インタープリタ２３２によるJava バイト・コードの解釈と実行は、当技術分野で公知の動作であるため本明細書では詳細な説明を省略する。また実行エンジン２３０は、インタープリタ２３２に加えて、ジャストインタイム（JIT)・コンパイラ（図示しない）を含むとしてもよい。JITコンパイラは、実行前に一連のJavaバイト・コードをまとめて変換することで実行時のオーバヘッドをなくし、実行速度を向上させる。JITコンパイラもまた、当技術分野で公知の動作であるため本明細書では詳細な説明を省略する。
【００４７】
メモリ２３４は、インタープリタ２３２によるJavaバイト・コードの実行のため、スタックとヒープに大別される定義された複数の記憶領域を含む。スタックは、マルチ・スレッドをサポートするために、スレッドが起動するたびにスレッドごと割り付けられる記憶領域である。メモリ２３４はまた、プログラムカウンタ（PC)レジスタも含む。
【００４８】
一般に、Java仮想マシン２２０のスタックは、後入れ先出し(LIFO:Last-In-First-Out) のデータ構造を実装する。スタック上のデータの単位はフレームと呼ばれ、スレッドが実行するメソッドのローカル変数の配列や、処理対象のデータを保持するスタック (Operand Stack)、当該メソッドのクラスの実行時コンスタント・プールへの参照を保持する。スレッドによりメソッドが起動されると、スタック上にフレームが積み上げられ、呼び出されたメソッドがアクティブになる。メソッドの処理が終了すると、対応するフレームは削除され、呼び出し元のメソッドが再びアクティブになる。  
【００４９】
ヒープは、仮想マシン２２０の起動時に割り付けられる、全てのスレッドから共有される記憶領域である。ヒープは、オブジェクトのインスタンスのような GC 対象となる動的なデータを格納する領域と、クラス構造などの静的なデータを格納するメソッド・エリア (Method Area)と呼ばれる領域とを含む。本願発明ではヒープ内のGC 対象となる記憶領域は複数のサブ領域を含み、各サブ領域は該サブ領域をローカル・メモリ１２８の少なくとも一部とするノード１０２に割り付けられる。そして各サブ領域は、該サブ領域を割り付けられたノード１０２内のCPU上で動作中の各スレッドにそれぞれ対応する複数の固有領域を含む。各スレッドは、それ自身の固有領域からオブジェクトを割り付ける。サブ領域および固有領域の位置、サイズ、および数は、オペレーティング・システム２１０やJava仮想マシン２２０に依存し、１つのノード１０２に複数のサブ領域が割り付けられる場合もある。
【００５０】
なお、本実施例では従来のスレッドローカルGCと同様に、各オブジェクトにつき１ビットを用意してスレッドローカル属性を表すようにする。一例として属性は、オブジェクトのヘッダの使用されていない領域を用いてよい。複数のスレッドから到達可能であると予め分かっているオブジェクトは、属性ビットを「共有」にセットして、当初より共有オブジェクトとして固有領域に割り付ける。それ以外のオブジェクトは、属性ビットを「スレッドローカル」にセットして、他のスレッドからアクセスされないローカルなオブジェクトとして固有領域に割り付ける。複数のスレッドから到達可能であると予め分かっているオブジェクトとしては、例えばJava言語の場合、クラスオブジェクトや、java.lang.Threadクラスおよびそのサブクラスのインスタンスがある。
【００５１】
ライトバリア処理部２３６は、属性が共有である共有オブジェクトへの各スレッド（以下、呼び出し元スレッドという）によるポインタの書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトの属性を共有に変更する。その際ライトバリア処理部２３６は、ポインタの書き込み先の共有オブジェクトを含む各共有オブジェクトが、呼び出し元スレッドに対応する固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトのポインタをトランザクショナルメモリの書き込みログに登録して衝突検知対象とし、かつ上記条件を満たす共有オブジェクトを呼び出し元スレッドのコピー用リストに登録する。なお、上記条件に、呼び出し元のスレッドに割り付けられた固有領域内の共有オブジェクトのコピーが可能であることを追加してもよい。
【００５２】
ここでコピー用リストはスレッドごとに用意され、該スレッドに割り付けられた固有領域に対して実施されるGCにおいて利用される。具体的には、コピー用リストに登録されたオブジェクトを手掛かりとして、GCが実施される固有領域の外へコピーするコピー対象となる上記固有領域内の共有オブジェクトが見つけられる。また、ライトバリア処理部２３６は、上記条件を満たす共有オブジェクトのポインタをトランザクショナルメモリの書き込みログに登録するが、この際バッファリングは行わない。この理由は、書き込み内容は他のスレッドに見えなければならないからである。
【００５３】
ガーベッジコレクタ２３８は、複数の固有領域のいずれかが満杯になったことに応答して、該固有領域を割り付けられたスレッド（以下、注目スレッドという）に関して衝突が検知されたか否かを判定し、満杯になった固有領域に対し判定結果に応じたGCを行う。衝突検知の判定は、一例として、後述する衝突ハンドラ２４０により設定される禁止フラグに基づいて行ってよい。
【００５４】
衝突が検知されない場合、ガーベッジコレクタ２３８は、注目スレッドのコピー用リストに登録された各共有オブジェクトから到達可能な各オブジェクトを、注目スレッドに割り付けられた固有領域内の現在の位置から固有領域外へコピーする。またコピー後のオブジェクトを指すように、コピーしたオブジェクト間のポイントを張りなおす。なお、上記オブジェクトのコピーとポインタの張りなおしは通常の書き込みにより行い、バッファリングも書き込みログへの登録も行わないことに留意されたい。
【００５５】
ガーベッジコレクタ２３８はまた、注目スレッドのコピー用リストに登録された各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングし、かつ、トランザクショナルメモリの書き込みログに登録して、その後トランザクションをコミットする。なおトランザクションのコミット前に、注目スレッドのコピー用リストを空にしてもよい。
【００５６】
そしてガーベッジコレクタ２３８は、その属性に関係なく不要になったオブジェクトを回収する。このように属性に関わらず回収できるのは、共有オブジェクトを既に固有領域外へコピーしており、また、コピーされずに残っている共有オブジェクトは、いずれのスレッドからも到達されないオブジェクトであるからである。なお、オブジェクトの回収方法は、例えばマーク＆ スイープ法、参照カウント法、複写法など既存のGCのいずれの方法でもよい。マーク＆ スイープ法を使用する場合、ガーベッジコレクタ２４０は、注目スレッドのレジスタおよびスタックからそれぞれ到達可能なオブジェクトをマークし、マークが付いてないオブジェクトを回収する。回収が終わると、ガーベッジコレクタ２３８は新しいトランザクションを開始する。
【００５７】
一方、衝突が検知された場合、ガーベッジコレクタ２３８は、従来のスレッドローカルGCと同様に、注目スレッドに割り付けられた固有領域について、その属性が共有でない不要になったオブジェクトを回収する。即ち、ガーベッジコレクタ２３８は、共有オブジェクトを除いたスレッドローカルオブジェクトの集合を対象として不要になったオブジェクトを回収する。なお、ここでもオブジェクトの回収は既存のGCのいずれの方法で行ってもよい。
【００５８】
衝突ハンドラ２４０は、衝突の検知に応答して、該衝突が検知された共有オブジェクトに関して、バッファリングされている書き込み、および登録されているトランザクショナルメモリの書き込みログを破棄する。衝突ハンドラ２４０はまた、衝突が検知された共有オブジェクトを含むコピー用リストを空にしてもよい。そして衝突ハンドラ２４０は、衝突が検知された共有オブジェクトを含むコピー用リストを有するスレッド、即ち衝突検知の通知を受けたログ登録側のスレッドに割り付けられた固有領域内の共有オブジェクトのコピーを禁止する。この禁止は、例えば固有領域ごとに１ビットの禁止フラグを用意し、この禁止フラグをセットすることより行ってよい。なお衝突の検知それ自体は、上述したようにCPUキャッシュとコヒーレンシプロトコルを利用してハードウェアによりなされ、衝突ハンドラ２４０は、衝突検知の通知を受けたログ登録側のスレッドから呼び出されてその処理を開始する。
【００５９】
衝突ハンドラ２４０は、ガーベッジコレクタ２３８による衝突が検知されない場合の処理開始後かつそのトランザクションのコミット前に衝突が検知された場合、ガーベッジコレクタ２３８に、トランザクションのコミットまでの残りの処理をスキップさせ、属性が共有でない不要になったオブジェクトの回収処理を開始させる。一方ガーベッジコレクタ２３８が処理を開始する前に衝突が検知された場合、衝突ハンドラ２４０は、衝突検知直前の処理、即ち、衝突検知により割り込まれた地点へ戻り制御を返す。
【００６０】
なお、上述したライトバリア処理部２３６、ガーベッジコレクタ２３８、および衝突ハンドラ２４０は、各々独立したスレッドにより実行されるとは限らないことに留意されたい。即ち、ライトバリア処理部２３６は、対応するライトバリア・モジュールを、アプリケーション・スレッドが呼び出して実行することにより実現されてよい。また、ガーベッジコレクタ２３８は、既存のガーベッジコレクタの一部の機能として実装されてよく、また対応するGCモジュールを、アプリケーション・スレッドが呼び出して実行することにより実現されてよい。衝突ハンドラ２４０もまた、ガーベッジコレクタ２３８やアプリケーション・スレッドにより呼び出されて実行されてよい。なお、以下では、本願発明による改良されたスレッドローカルGCを、コピー式スレッドローカルGCとも呼ぶものとする。
【００６１】
また、本願発明ではトランザクショナルメモリを使用するが、上述したようにトランザクションは、ガーベッジコレクタ２３８により不要オブジェクトが回収された後開始され、また、ガーベッジコレクタ２３８によりトランザクションがコミットされることにより終了する。従って、上記ライトバリア処理部２３６、およびガーベッジコレクタ２３８の各処理において行われるメモリ書き込みは、いずれもトランザクション中のメモリ書き込みである。しかし本願発明では以下に説明する３種類のメモリ書き込みを用意し、ライトバリア処理部２３６、およびガーベッジコレクタ２３８の各処理においてそれぞれ目的に応じたメモリ書き込みができるようにする。
【００６２】
本願発明において用意する３種類の書込みとは、（１ ）バッファリングも書き込みログへの登録も行わない通常の書き込み、（２）バッファリングしないが書き込みログへの登録は行う書き込み、（３）バッファリングも書き込みログへの登録も行う書き込みである。（１）の通常の書き込みを可能とするためには、通常のメモリ読み書き命令をトランザクション中で実行する機能が必要である。この機能は一般に、トランザクションを一時的に中断するsuspend/resume命令か、またはトランザクション用の特別なメモリ読み書き命令（以下、単に通常の書き込み命令という）のどちらかを用意することにより提供されることが多く、以下に説明する実施例では、後者を採用するものとする。
【００６３】
（２）の書き込みログへの登録のみ行う書き込みを可能とするには、以下の２つの方法（Ｌ１、Ｌ２）がある。Ｌ１の方法では、CPUキャッシュラインごとに状態を１つ追加し、「書き込みログに登録されているがバッファリングはされていない」という状態を表わすことができるようにする。また、CPUキャッシュラインをこの状態にするための「ロギング用書き込み命令」を用意する。なお、以下に説明する実施例ではこのＬ１の方法を採用するものとする。
【００６４】
CPUキャッシュラインに状態を追加したくない場合はＬ２の方法を利用する。Ｌ２の方法では、ライトスルーするトランザクション用書込み命令を用意する。この命令ではCPUキャッシュライン中の値と同時にメモリ中の値も書き換える。この手法の問題点は、バッファリングされている書き込みデータと同じキャッシュラインに同じスレッドが通常の書き込みを行った場合、多くのハードウェア・トランザクショナルメモリの実装では衝突と扱われてしまう点である。従って、衝突ハンドラの中でライトスルーするトランザクション用書き込み命令で同じ値をもう一度書き込む必要がある。なお（３）のトランザクション用書き込みを行う「トランザクション用書き込み命令」は、一般的なトランザクション中のメモリ書き込み命令として既知であるため、詳細な説明は省略する。
【００６５】
また上述した衝突ハンドラ２４０の処理に関して、本願発明は次の挙げる機能を必要とする。（Ａ）eagerな衝突検知機能。本願発明では、ログされた書き込みデータを他のスレッドが読書きした時点でスレッドに通知する必要がある。なお、既存のハードウェア・トランザクショナルメモリの実装では、実装の容易さからeagerに衝突を検知することが多い。（Ｂ）書き込みログで衝突を検知した場合にログを登録した側のスレッドに衝突検知を通知する機能。Strong atomicityを実装する場合は、通常のメモリ読み書き命令を発行した側のスレッドではなくログを登録した側のスレッドに通知するほうが容易である。
【００６６】
（Ｃ）衝突が通知されてもトランザクションがアボートされない機能。ハードウェア・トランザクショナルメモリの実装では、衝突が通知されると自動的にトランザクションの開始位置まで実行が巻き戻る実装と、前もって登録しておいたハンドラにジャンプしてその中でソフトウェアがアボート命令を発行する実装がある。本願発明では、後者の実装を採用する。
【００６７】
（Ｄ）書き込みログやバッファリングされた書込みがCPUキャッシュから追い出されたことが通知されてもトランザクションがアボートされない機能。ハードウェア・トランザクショナルメモリでは有限な大きさのCPUキャッシュの中にログとバッファを持つことが多い。ログやバッファがCPUキャッシュから追い出されてしまった場合は、それらを登録したスレッドに通知がなされる。本願発明では、このような通知を受けてもスレッドがトランザクションを自動的にアボートしないように実装を行う。
【００６８】
（Ｅ）書き込みログとバッファリングされた書き込みを破棄しても、トランザクションの開始位置まで戻ることはしないアボート命令。このようなアボート命令が用意されていない場合は追加する。なお、上述した（A)から（E)の各機能は、現在実装されているハードウェア・トランザクショナルメモリに備わっている機能または、簡単な変更で追加可能な機能であり公知の技術であるため、細かな実装方法の説明は省略する。
【００６９】
次に図３から図５を参照して、本発明の実施の形態に係るライトバリア処理部２３６、ガーベッジコレクション２３８、および衝突ハンドラ２４０の各処理の流れを説明する。図３は、本発明の実施の形態に係るライトバリア処理部２３６による処理の流れを示すフローチャートである。図３に示すライトバリア処理は、ポインタを書き込もうとするスレッドがライトバリア処理部２３６を呼び出すことにより開始され、ライトバリア処理部２３６は、呼び出し元スレッドによってポインタを書き込まれる書き込み先のオブジェクトの属性が「共有」であるか否かを判定する（ステップ３０５）。属性が「共有」でない場合（ステップ３０５：NO)、処理はステップ３９０へ進み、ライトバリア処理部２３６は、通常のメモリ書き込み命令で、書き込もうとしていたポインタを書き込み先のオブジェクトのポインタフィールドに書き込み、処理は終了する。
【００７０】
一方、ステップ３０５において属性が「共有」であった場合、ライトバリア処理部２３６は、ポインタが指す先のオブジェクトを現在のオブジェクトとする（ステップ３１０）。続いてライトバリア処理部２３６は、現在のオブジェクトの属性ビットが「スレッドローカル」であるか否かを判定する（ステップ３１５）。属性が「スレッドローカル」である場合（ステップ３１５：YES）、ライトバリア処理部２３６は、現在のオブジェクトの属性ビットを「共有」に書き換える（ステップ３２０）。またライトバリア処理部２３６は、現在のオブジェクトのポインタフィールドの集合をPに登録し（ステップ３２５）、この集合Pにポインタフィールドが入っているか否かを判定する（ステップ３３０）。
【００７１】
集合Pにポインタフィールドが入っている場合（ステップ３３０：YES)、ライトバリア処理部２３６は、集合Pからポインタフィールドを１つ取り出して、該フィールドのアドレスを取得する（ステップ３３５）。続いてライトバリア処理部２３６は、取り出したポインタフィールドが指す先のオブジェクトを求め、これを子供オブジェクトとして集合S（例えばキュー）に登録する（ステップ３４０、３４５）。
【００７２】
続いてライトバリア処理部２３６は、呼び出し元スレッドに割り付けられた固有領域（スレッドローカルヒープともいう）について、該固有領域内の共有オブジェクトのコピーが可能であるか、また、現在のオブジェクトが上記固有領域の外にあり、直前に集合Sに登録した子供オブジェクトが上記固有領域内にあるか否かを判定する（ステップ３５０）。なお、ある固有領域内の共有オブジェクトのコピーが可能であるか否かの判定は、上述したように、衝突ハンドラ２４０によって設定される固有領域ごとの禁止フラグに基づいて行ってよい。また、あるオブジェクトが呼び出し元スレッドに割り付けられた固有領域内にあるかまたは外にあるかの判定は、オブジェクトを指すポインタの値に基づいて行ってよい。  
【００７３】
呼び出し元スレッドのスレッドローカルヒープ内の共有オブジェクトのコピーが可能であり、また、現在のオブジェクトは上記ローカルーヒープ外に、かつ直前に集合Sに登録した子供オブジェクトはスレッドローカルヒープ内にある場合（ステップ３５０：YES）、ライトバリア処理部２３６は、現在のオブジェクトを呼び出し元スレッドのコピー用リストに登録し、ステップ３３５において取得したアドレスに対して、直前に集合Sに登録した子供オブジェクトへのポインタを、ロギング用書き込み命令を使って書き込む。（ステップ３５５、３６０）。一方、ステップ３５０でＮＯの場合、またはステップ３６０から、処理は再びステップ３３０へ戻り一連の処理を繰り返す。
【００７４】
一方、ステップ３１５において現在のオブジェクトの属性が「スレッドローカル」でない場合、あるいはステップ３３０において集合Pにポインタフィールドが入っていない場合、処理はステップ３６５へ進み、ライトバリア処理部２３６は、集合Sが空であるか否かを判定する。集合Sが空でない場合（ステップ３６５：NO）、処理はステップ３７０へ進み、ライトバリア処理部２３６は、集合Sからオブジェクトを１つ取り出して、これを現在のオブジェクトとする。そして処理は再びステップ３１５へ戻り、現在のオブジェクトに対し上述した一連の処理を繰り返す。  
【００７５】
一方、ステップ３６５においてYESの場合、即ち、集合Sが空である場合、処理はステップ３７５へ進み、ライトバリア処理部２３６は、呼び出し元スレッドに割り付けられたスレッドローカルヒープについて、該スレッドローカルヒープ内の共有オブジェクトのコピーが可能であるか、また、書き込み先オブジェクトが上記スレッドローカルヒープの外にあり、呼び出し元スレッドが書き込むポインタの指す先のオブジェクトが上記スレッドローカルヒープ内にあるか否かを判定する。なお各判定の方法は上述した通りである。
【００７６】
呼び出し元スレッドのローカルヒープ内の共有オブジェクトのコピーが可能であり、また、書き込み先オブジェクトは上記ローカルーヒープ外に、かつ呼び出し元スレッドが書き込むポインタの指す先のオブジェクトはローカルヒープ内にある場合（ステップ３７５：YES）、ライトバリア処理部２３６は、書き込み先オブジェクトを呼び出し元スレッドのコピー用リストに登録し、呼び出し元スレッドが書き込もうとしていたポインタを、ロギング用書き込み命令を使って書き込む。（ステップ３８０、３８５）。そして処理は終了する。一方ステップ３７５においてＮＯの場合、処理はステップ３９０へ進み、ライトバリア処理部２３６は、通常のメモリ書き込み命令で、書き込もうとしていたポインタを書き込み先のオブジェクトのポインタフィールドに書き込み、処理は終了する。
【００７７】
図４は、本発明の実施の形態に係るガーベッジコレクタ２３８による処理の流れを示すフローチャートである。なお、図４に示すフローチャートでは、オブジェクトを回収するためにマーク＆ スイープ法を用いているが、上述したように不要オブジェクトの回収法方はこれに制限されないことを理解されたい。図４に示す処理は、複数の固有領域のいずれかが満杯になったことに応答して、満杯になった固有領域を割り付けられたスレッドがガーベッジコレクタ２３８を呼び出すことにより開始され、ガーベッジコレクタ２３８は、満杯になった固有領域（スレッドローカルヒープともいう）内の共有オブジェクトのコピーが可能であるか否かを判定する（ステップ４０５）。この判定は、ガーベッジコレクタ２３８を呼び出したスレッドに関して衝突が検知された否かを調べるためのものであり、上述したように、衝突ハンドラ２４０によって設定される固有領域ごとの禁止フラグに基づいて行ってよい。
【００７８】
共有オブジェクトのコピーが可能である場合（ステップ４０５：YES）、ガーベッジコレクタ２３８は、上記スレッドのコピー用リストに登録された共有オブジェクトから到達可能であり、かつ満杯になったスレッドローカルヒープ内にあるオブジェクトを、そのスレッドローカルヒープ外へコピーし、また、コピーしたオブジェクト間のポインタを張りなおす（ステップ４１０、４１５）。
【００７９】
ここでコピーとポインタの張りなおしには、既存のコピー式GCを使ってよく、また、通常の書き込み命令を用いる。但し、ポインタを張りなおすアルゴリズムの中には、元のオブジェクトにforwardポインタを埋め込むものもあり、元のオブジェクトを破壊するこのような書き込みにはトランザクション用書き込み命令を用いる。
【００８０】
続いてガーベッジコレクタ２３８は、上記コピー用リストに登録されている各共有オブジェクト中のポインタフィールドを、トランザクション用書き込み命令を使用して、コピー先のオブジェクトを指すように書き換える（ステップ４２０）。全ての登録共有オブジェクトについて上記処理が終わると、ガーベッジコレクタ２３８は、上記コピー用リストを空にして（ステップ４２５）、トランザクションをコミットする（ステップ４３０）。トランザクションをコミットすることで、それまでのトランザクション用書き込みの結果が他のスレッドに原子的に見えるようになる。
【００８１】
ステップ４０５において、共有オブジェクトのコピーが可能でない場合、またはステップ４３０から、処理はステップ４３５へ進み、ガーベッジコレクタ２３８は、上記スレッドのレジスタとスタックから到達可能なオブジェクトをマークするとともに、該オブジェクトについて、コピーされた共有オブジェクトへのポインタを、通常の書き込み命令を用いて張りなおす。
【００８２】
続いてガーベッジコレクタ２３８は、再び、満杯になったスレッドローカルヒープ内の共有オブジェクトのコピーが可能であるか否かを判定する（ステップ４４０）。共有オブジェクトのコピーが可能である場合（ステップ４４０：YES）、即ち上記スレッドローカルヒープを割り付けられたスレッドに関して衝突が検知されていない場合、ガーベッジコレクタ２３８は、属性に関わらずマークが付いていないオブジェクトを回収する（ステップ４５０）。そしてガーベッジコレクタ２３８は、最後にトランザクションを開始して（ステップ４５５）、処理を終了する。
【００８３】
一方、共有オブジェクトのコピーが可能でない場合（ステップ４４０：NO）、即ち上記スレッドローカルヒープを割り付けられたスレッドに関して衝突が検知された場合、ガーベッジコレクタ２３８は、マークが付いていない、属性がスレッドローカルであるオブジェクトを回収する（ステップ４６０）。そして処理は終了する。なお、ステップ４０５の処理開始後であって、かつステップ４３０のトランザクションのコミット前において衝突が検知された場合、ガーベッジコレクタ２３８の処理に割り込んで衝突ハンドラ２４０の処理が開始される。その後衝突ハンドラ２４０の処理が終わると、ガーベッジコレクタ２３８の処理はステップ４３５から開始し、割り込まれた地点からステップ４３０のトランザクションのコミットまでの処理はスキップされることに注意されたい。
【００８４】
図５は、本発明の実施の形態に係る衝突ハンドラ２４０による処理の流れを示すフローチャートである。図５に示す処理は、トランザクショナルメモリの書き込みログで衝突が検知され、衝突検知の通知がなされたログ登録側のスレッドが衝突ハンドラ２４０を呼び出すことにより開始され、衝突ハンドラ２４０は、アボート命令を発行して、バッファリングされた書き込みと書き込みログを破棄する（ステップ５０５）。なお、上述したように本願発明において使用するアボート命令は、バッファリングされた書き込みと書き込みログを破棄しても、トランザクションの開始位置まで実行を巻き戻すことはしないことに留意されたい。
【００８５】
続いて衝突ハンドラ２４０は、ログ登録側のスレッドのコピー用リストを空にし（ステップ５１０）、また、ログ登録側のスレッドの固有領域、即ちスレッドローカルヒープ内の共有オブジェクトのコピーを不可能とする（ステップ５１５）。上述したように、コピーを不可能とする処理は、例えばログ登録側のスレッドのスレッドローカルヒープに対応する禁止フラグを設定することにより行ってよい。
【００８６】
最後に衝突ハンドラ２４０は、現在ガーベッジコレクタ２３８によるGCが実行中であるか否かを判定し（ステップ５２０）、実行中である場合（ステップ５２０：YES）、ガーベッジコレクタ２３８に、衝突検知で割り込まれた地点からトランザクションのコミットまでの処理をスキップさせ、図４に示すフローチャートのステップ４３５の地点から処理を開始させる（ステップ５２５）。一方、実行中でない場合（ステップ５２０：NO)、衝突ハンドラ２４０は、衝突検知で割り込まれた地点へ戻り、制御を返す（ステップ５３０）。そして処理は終了する。
【００８７】
このように、ガーベッジコレクタ２３８によるGCの実行中に衝突ハンドラ２４０が呼び出されると、トランザクションはコミットされることなく終了するので、共有オブジェクトがコピーされたとしても他のスレッドはその結果を見ることはできない。このため、共有オブジェクトのコピー先の領域は無駄になるが、１回のコピー式スレッドローカルGCにおいてコピーされる共有オブジェクトの数は少ないと考えられるので問題はない。
【００８８】
次に図６および図７を参照して、本発明の実施形態に係るコピー式スレッドローカルGCの動作を、具体例を用いて説明する。その前にまず、本願発明による改良がより明らかになるように、図１０を参照して従来のスレッドローカルGCの動作を説明する。図１０（ａ）は、スレッドＸに割り付けた固有領域１０２２を含むメモリの初期状態を示す。図１０（ａ）において、スタック１０２０はスレッドＸの、スタック１０２６はスレッドＹのそれぞれスタックであり、領域１０２８は複数のスレッドにより共有される領域である。また図中の矢印は、オブジェクト間の参照関係を示すポインタである。
【００８９】
図１０（ａ）に示すように、初期状態では、スレッドＸの固有領域１０２２にはオブジェクトＢからオブジェクトＥが割り付けられており、共有領域１０２８にはオブジェクトＡが配置されている。また、各オブジェクトのヘッダ部分の数字はその属性を示すビット値を示しており、初期状態では、オブジェクトＡのみが値1を有し共有オブジェクトとなっている。更に、オブジェクトＤとオブジェクトＥはどのスレッドからも到達不可能となっており、従ってこれらは不要となったオブジェクトである。
【００９０】
図１０（ａ）に示す初期状態において、スレッドＸがオブジェクトＡからオブジェクトＢへのポインタをオブジェクトＡに書き込もうとすると、従来のライトバリアが実行される。ライトバリアの実行により、オブジェクトＡからオブジェクトＢへのポインタを出発点としてオブジェクトが辿られ、オブジェクトＢ、オブジェクトＣの属性ビットがそれぞれ共有であることを示す「１」に変更される。図１０（ｂ）は、従来のライトバリア実行後のメモリの状態を示す。
【００９１】
続いて、図１０（ｂ）に示す状態において、スレッドＸがオブジェクトＢに対し、オブジェクトＢからオブジェクトＣへのポインタを消したとする。するとスレッドＸの固有領域１０２２は図１０（ｃ）に示す状態へと遷移する。その後スレッドＸの固有領域１０２２が満杯となると、固有領域１０２２に対して従来のスレッドローカルGCが実施される。図１０（ｄ）は、従来のスレッドローカルGC実施後のメモリの状態を示す。
【００９２】
従来のスレッドローカルGCでは、共有でない不要となったオブジェクトが回収されるので、図１０（ｄ）に示すように、たとえ不要となったものであっても、属性が共有であるオブジェクトＣは回収されず固有領域１０２２に残る。また不要でない共有オブジェクトであるオブジェクトＢは、他のスレッドから参照される可能性があるため、固有領域１０２２の外へコピーすることはできない。そのため共有オブジェクトＢもまた固有領域１０２２にそのまま残る。
【００９３】
このように従来のスレッドローカルGCでは、固有領域内に共有オブジェクトが残され、GCの回数を重ねるうちにこの回収されない共有オブジェクトの数が増え、フラグメンテーションが激しくなっていた。固有領域に残されたままの共有オブジェクト（図１０（ｄ）の例では、オブジェクトＢとオブジェクトＣ）は、次の大域GCで全てのスレッドを停止してGCを実施することにより初めて固有領域外へコピーされ、あるいは回収される。従って、従来のスレッドローカルGCには、フラグメンテーションの問題だけではなく、それによって大域GCの回数が増すと全てのスレッドを止める頻度が増し停止時間が長くなるという問題もあった。
【００９４】
図６は、衝突が検知されない場合における、本発明の実施形態に係るコピー式スレッドローカルGCの動作例を示す図である。図６（ａ）は、図１０（ａ）に一部対応しており、スレッドＸに割り付けた固有領域６２２を含むメモリと、スレッドＸを実行中のＣＰＵ０が有するキャッシュ６０３を含むキャッシュの初期状態を示す。なお、ＣＰＵ１はスレッドＹを実行中のＣＰＵであり、同様にキャッシュ６１１を有している。
【００９５】
図６（ａ）において、キャッシュ６０３内に入っているキャッシュライン６０４の先頭の１ビット６０６は値１のとき、キャッシュライン６０４内のデータがログされている書込みであることを示すものである。一方、１ビット６０６の隣の１ビット６０８の値１は、キャッシュライン６０４内のデータがバッファリングされている書込みであることを示すものである。キャッシュ６１１内のキャッシュライン６１２のビット６１４、６１６も同様である。
【００９６】
ハードウェア・トランザクショナルメモリの多くの実装では、このように、各キャッシュラインにビットが追加され、バッファリングされた書き込みやログされた書込みであることを表す。バッファリングされた書き込みデータは他のスレッドからは見えない。ログされた書き込みは衝突検知の対象となる。そしてトランザクションがコミットされるとどちらのビットも０になる。
【００９７】
図６（ａ）において、残りの他の部分は基本的に図１０（ａ）と同じであるため、繰り返しを避けるためここでは説明を省略する。但し、コピー式スレッドローカルGCでは、固有領域ごとに１ビットの禁止フラグ６２４を用意し、これによって該固有領域内の共有オブジェクトのコピーの可能・不可能を示すようにしている。
【００９８】
図６（ａ）に示す初期状態において、スレッドＸがオブジェクトＡからオブジェクトＢへのポインタをオブジェクトＡに書き込もうとすると、本発明の実施形態に係るライトバリアが実行される。図６（ｂ）は、ライトバリア実行後のメモリとキャッシュの状態を示す。
【００９９】
本発明の実施形態に係るライトバリアの実行では、オブジェクトＡからオブジェクトＢへのポインタを出発点としてオブジェクトが辿られ、オブジェクトＢ、オブジェクトＣの属性ビットがそれぞれ、共有であることを示す「１」に変更される。またこのとき、所定の条件が満たされるか否か、即ち、禁止ビット６２４を参照してスレッドＸの固有領域６２２内の共有オブジェクトのコピーが可能であるか否か、また、ポインタを書き込もうとする書き込み先のオブジェクトＡがスレッドＸの固有領域６２２の外にあり、書き込もうとするポインタが指す先のオブジェクトＢがスレッドＸの固有領域６２２内にあるか否かが判定される。
【０１００】
図６（ａ）に示す初期状態は上記所定の条件を満たすため、ロギング用の書き込み命令でオブジェクトＡからオブジェクトＢへのポインタが書き込まれ、図６（ｂ）に示すように、オブジェクトＡを含むキャッシュラインがスレッドＸを実行中のＣＰＵ０のキャッシュ６０３に入り、ログされている書込みであることを示すビット６０６が１に設定される。また、図示はしないが、このときオブジェクトＡは、スレッドＸのコピー用リストにも登録される。
【０１０１】
続いて、図６（ｂ）に示す状態において、スレッドＸがオブジェクトＢに対し、オブジェクトＢからオブジェクトＣへのポインタを消し、その後スレッドＸの固有領域６２２が満杯になってガーベッジコレクタ２３６によるGCが実施されたとする。図６（ｃ）は、コピー式スレッドローカルGCにおいて行われるコピー処理の後のメモリとキャッシュの状態を示す。
【０１０２】
ガーベッジコレクタ２３６によるGCではまず、禁止ビット６２４を参照してスレッドＸの固有領域６２２内の共有オブジェクトのコピーが可能であることが確認され、図６（ｃ）に示すように、スレッドＸのコピー用リストに登録されているオブジェクトＡから到達可能であり、固有領域６２２内にあるオブジェクトＢが、固有領域６２２の外の領域６２８へコピーされる。なおコピー式スレッドローカルGCが行われる前にオブジェクトBについてポインタが消されることから、図６（ｃ）では、オブジェクトＢからオブジェクトＣへのポインタが消されている。
【０１０３】
コピー処理が終わると、次にスレッドＸのコピー用リストに登録されているオブジェクトＡについて、トランザクション用書き込み命令を使ってオブジェクトＡのポインタフィールドがコピー先のオブジェクトＢを指すように書き換えられる。図６（ｄ）は、ポインタ張りかえ処理後のメモリとキャッシュの状態を示す。図６（ｄ）をみると、ビット６０６、６０８がいずれも値１にセットされて、それぞれ、キャッシュライン６０４に登録されたデータがログされていること、またバッファリングされていることを示している。
【０１０４】
続いて、図６（ｄ）に示す状態においてトランザクションがコミットされ、その後、スレッドＸのレジスタやスタック６２０から辿られるオブジェクトについて、コピーされた共有オブジェクトへのポインタが通常の書き込み命令を用いて張りなおされる。また、スレッドＸの固有領域６２２に対して、属性にかかわらず不要になったオブジェクトの回収が行われ、その後ガーベッジコレクタ２３６によるGCが終了する。図６（ｅ）は、コピー式スレッドローカルGC終了後のメモリとキャッシュの状態を示す。
【０１０５】
図６（ｅ）をみると、トランザクションがコミットされたことにより、ビット６０６とビット６０８の値が０にリセットされている。バッファリングされていたオブジェクトＡからコピー先のオブジェクトＢへのポインタも、トランザクションがコミットされたことより、他のスレッドからも見えるように共有領域６２８に書き込まれている。また、スタック６２０のポインタも、コピー先のオブジェクトＢを指すように変更されている。そして、スレッドＸの固有領域６２２内の不要になったオブジェクトは、その属性に関係なく全て回収されている。
【０１０６】
このように本願発明のコピー式スレッドローカルGCによれば、トランザクショナルメモリの衝突検知とバッファリングの仕組みを利用して、実際に他のスレッドからアクセスがあるまでは、共有オブジェクトをスレッドローカルなオブジェクトとして扱い固有領域外へコピーするので、フラグメンテーションの問題が大きく改善され、また、全てのスレッドを停止する大域GCの頻度も少なくなり停止時間も大幅に減る。
【０１０７】
図７は、衝突が検知される場合における、本発明の実施形態に係るコピー式スレッドローカルGCの動作例を示す図である。衝突が検知されるまでの動作は図６に示す動作例と同じであるため、初期状態を示す図６（ａ）に対応する図７（ａ）と、ライトバリア実行後の状態を示す図６（ｂ）に対応する図７（ｂ）の説明はここでは省略する。
【０１０８】
図７（ｂ）に示す状態において、オブジェクトＢについてオブジェクトＢからオブジェクトＣへのポインタが消され、また、スレッドＹがオブジェクトＡを読み込み、衝突が検知されたとする。図７（ｃ）は、衝突検知後の、スレッドＸに割り付けた固有領域６２２を含むメモリと、スレッドＸを実行中のＣＰＵ０が有するキャッシュ６０３と、スレッドＹを実行中のＣＰＵ１が有するキャッシュ６１１を含むキャッシュの状態を示す。
【０１０９】
図７（ｃ）をみると分かるように、スレッドＹがオブジェクトＡを読み込んだことから、オブジェクトＡを含むキャッシュラインが、スレッドＹを実行中のＣＰＵ１のキャッシュ６１１に入っている。またこの読み込みにより衝突が検知されたため、トランザクションがアボートされ、その結果キャッシュライン６０４のビット６０６が０にリセットされている。更に衝突が検知されたことから、スレッドＸの固有領域６２２に対応する禁止フラグ６２４が「コピー不可能」を表す０に設定されている。
【０１１０】
その後図７（ｃ）に示す状態において、スレッドＸの固有領域６２２が満杯になり、本願発明の実施形態に係るコピー式スレッドローカルGCが実施されたとする。図７（ｄ）は、コピー式スレッドローカルGC終了後のメモリとキャッシュの状態を示す。図７（ｄ）をみると分かるように、コピー式スレッドローカルGCは、衝突が検知されたことから従来のスレッドローカルGCと同様に共有でない不要となったオブジェクトを回収しており、その結果、固有領域６２２には、共有オブジェクトＢ、Ｃが残されたままとなっている。
【０１１１】
このように、図７に示す例では、ガーベッジコレクタ２３６によるGCが実施される前にスレッドＹがオブジェクトＡを読み込んでしまい衝突が検知されるので、スレッドＸの固有領域６２２の外へオブジェクトＢをコピーすることはできない。また、一度衝突が検知されると、以降は保守的に動作する必要があるので共有オブジェクトＣは回収できない。
【０１１２】
ところで上記実施例では、実際のハードウェア・トランザクショナルメモリの実装はキャッシュライン単位で衝突が検知されることから、スレッドＹが、オブジェクトＡ内のオブジェクトＢを指すポインタフィールド以外のフィールドや、同じキャッシュライン内の別のオブジェクトを読み書きした場合であっても、共有オブジェクトが不可能となる例を説明した。しかしながら本来は、スレッドＹがオブジェクトＡ内のオブジェクトＢを指すポインタフィールドを読み込んだときに限って共有オブジェクトのコピーを不可能とするべきである。
【０１１３】
そこで本願発明の第１の他の実施例として、スレッドに割り付けられた固有領域の外の共有オブジェクトから直接指される固有領域内のオブジェクトを、書き込みログとコピー用リストに登録する方法を新たに提案する。この第１の他の実施例によれば、図２に示すライトバリア処理部２３６は、属性が共有である共有オブジェクトへの各スレッドによるポインタ書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトの属性を共有に変更し、上記ポインタの書き込み先の共有オブジェクトを含む各共有オブジェクトが、上記スレッドに割り付けられた固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトが直接参照する上記固有領域内のオブジェクトを、トランザクショナルメモリの書き込みログに登録して衝突検知対象とし、かつ上記スレッドのコピー用リストに登録するものとして理解される。
【０１１４】
第１の他の実施例に係るライトバリア処理部２３６の処理を示すフローチャートは、基本的は図４に示すものと同じであるが、図３のステップ３５５および３６０の処理において、コピー用リストと書き込みログに登録するのは、直前に集合Sに登録した子供オブジェクトである。また、図３のステップ３８０と３８５においてコピー用リストと書き込みログに登録するのは、書き込もうとするポインタが指す先のオブジェクトである。
【０１１５】
また、第１の他の実施例によれば、図２に示すガーベッジコレクタ２３８は、複数の固有領域のいずれかが満杯になったことに応答して、満杯になった固有領域を割り付けられたスレッドに関して衝突が検知されない場合、該スレッドのコピー用リストに登録された各共有オブジェクトから到達可能な各オブジェクトを満杯になった固有領域の外へコピーし、上記コピー用リストに登録された各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングし、トランザクショナルメモリの書き込みログに登録し、トランザクションをコミットし、および上記コピー用リストに登録された各共有オブジェクトを除いて、その属性に関係なく不要になったオブジェクトを回収し、満杯になった固有領域を割り当てられたスレッドに関して衝突が検知される場合、該固有領域についてその属性が共有でない不要になったオブジェクトを回収するものとして理解される。
【０１１６】
第１の他の実施例に係るガーベッジコレクタ２３８の処理を示すフローチャートは、基本的は図４に示すものと同じであるが、図４のステップ４５０の処理は、コピー用リストに登録された各共有オブジェクトを除いて、その属性に関係なく不要になったオブジェクトを回収する処理に取って代わる。なお、第１の他の実施例に係る衝突ハンドラ２４０は、図２および図５を参照して上記説明した衝突ハンドラ２４０と同じであるため、繰り返しを避けるためここでは説明を省略する。
【０１１７】
図７に示す例では、オブジェクトＢが、上記第１の他の実施例における書き込みログとコピー用リストの対象となる。この第１の他の実施例によれば、スレッドローカルヒープの外の共有オブジェクトから直接指されるオブジェクトＢは、衝突検知の有無に関わらず固有領域外へコピーできなくなる。しかし、この第１の他の実施例によれば、スレッドローカルヒープの外の共有オブジェクトから直接指されるオブジェクトＢが他のスレッドより実際にアクセスされた場合にのみ衝突が検知されることから、衝突検知の可能性は低くなり、また、衝突が検知されない限り不要となった共有オブジェクトＣは回収できる。
【０１１８】
ところで上述した２つの実施例では、あるスレッドローカルヒープで一度共有オブジェクトのコピーが不可能となると、それ以降は従来のスレッドローカルGCと同様にそのスレッドローカルヒープ内では常に共有オブジェクトのコピーは不可能として扱ってきた。しかし、衝突が検知され、コピーが不可能となった共有オブジェクトに印を付け、そのような印のついた共有オブジェクトを回収およびコピーの対象外として取り扱うことで、それ以降も、その共有オブジェクトが割り付けられたスレッドローカルヒープに対しコピー式スレッドローカルGCを適用可能となる。
【０１１９】
そこで本願発明の第２の他の実施例として、次のような、トランザクショナルメモリを実装した複数のプロセッサと、その一部が、動作中の各スレッドにそれぞれ対応する複数の固有領域として割り当てられるメモリとを含むメモリ管理装置を提案する。この第２の他の実施例によれば、図２に示すライトバリア処理部２３６は、属性が共有である共有オブジェクトへの各スレッドによるポインタ書き込み操作の開始に応答して、書き込もうとするポインタの指す先を出発点として再帰的に辿ることにより到達可能な各オブジェクトの属性を共有に変更し、ポインタの書き込み先の共有オブジェクトを含む各共有オブジェクトが、上記スレッドに対応する固有領域の外にあり、かつ該固有領域内のオブジェクトを指すポインタを有することを条件として、該条件を満たす共有オブジェクトの前記ポインタをトランザクショナルメモリの書き込みログに登録して衝突検知対象とし、かつ上記条件を満たす共有オブジェクトを前記スレッドのコピー用リストに登録するものとして理解される。このように、第２の他の実施例に係るライトバリア処理部２３６の処理を示すフローチャートは図３に示すものと同じものとなるため、繰り返しを避けるためここでは説明を省略する。
【０１２０】
また、第２の他の実施例によれば、図２に示す衝突ハンドラ２４０は、衝突の検知に応答して、該衝突が検知された共有オブジェクトに関して、バッファリングされている書き込み、登録されているトランザクショナルメモリの書き込みログを破棄し、およびコピー用リスト内の衝突が検知された共有オブジェクトから到達可能な各オブジェクトにマークを付けるものとして理解される。第２の他の実施例に係る衝突ハンドラ２４０の処理を示すフローチャートは、基本的には図５に示すものと同じであるが、図５のステップ５１５における処理は、コピー用リスト内の衝突が検知された共有オブジェクトから到達可能な各オブジェクトにマークを付ける処理に取って代わる。また、図５のステップ５２５の処理は、トランザクションの開始位置まで実行を巻き戻す処理に取って代わる。
【０１２１】
更に、第２の他の実施例によれば、図２に示すガーベッジコレクタ２３８は、複数の固有領域のいずれかが満杯になったことに応答して、該固有領域を割り付けられたスレッドのコピー用リストに登録された各共有オブジェクトから到達可能な上記マークの付いていない各オブジェクトを満杯になった固有領域の外へコピーし、コピー用リストに登録された各共有オブジェクトについて、コピーされたオブジェクトへのポインタを該オブジェクトのコピーを指すように変更するための書き込みをバッファリングしてトランザクショナルメモリの書き込みログに登録し、トランザクションをコミットし、および上記マークの付いた各オブジェクトを除く不要になったオブジェクトを回収するものとして理解される。
【０１２２】
第２の他の実施例に係るガーベッジコレクタ２３８の処理を示すフローチャートは、基本的は図４に示すものと同じであるが、図４のステップ４０５、４４０および４６０のステップはなくなる。そして、図４のステップ４１０、４５０の各処理は、衝突ハンドラ２４０によりマークを付けられた各オブジェクトを処理対象から除外してなされる。
【０１２３】
次に図８および図９を参照して、本発明の効果を従来のスレッドローカルGCとの比較により検討する。最初に図８を参照して、オブジェクトのカテゴリごと、従来のスレッドローカルGCと本発明の実施形態に係るコピー式スレッドローカルGCのオブジェクトに対する動作を説明する。そして次に、一定の期間一定条件の下生成されるオブジェクトについて、各カテゴリのオブジェクトが占める割合を示し、それによって本発明によって得られる効果が大きいことを証明する。
【０１２４】
図８に示す表は、従来のスレッドローカルGCと本発明の実施形態に係るコピー式スレッドローカルGCの動作を、オブジェクトのカテゴリごとにまとめたものである。あるスレッドローカルGCから次のローカルスレッドGCまでの間に新たに生成されるオブジェクトは、次のローカルスレッドGCの開始時点において、図８に示すように６つのカテゴリに分類される。図８においてLiveとは、スレッドのレジスタまたはスタックから到達可能であることを意味し、Deadとは、どこからも参照されなくなったことを意味する。また、Thread-local（スレッドローカル）とは、属性がスレッドローカルであることを意味し、Globalとは属性が共有であることを意味する。更にglobal and accessed frommultiple threads は属性が共有であり、かつ実際に複数のスレッドからアクセスがあったことを意味する。
【０１２５】
図８に示されるように、属性がスレッドローカルであるオブジェクトに対する動作は、オブジェクトが生きているか死んでいるかに関係なくどちらの場合も従来のスレッドローカルGCと本願発明のコピー式スレッドローカルGCとで同じであり、生きているオブジェクトはコンパクション（compaction)するか外へ追い出され、死んでいるオブジェクトは回収される。一方、属性が共有であるオブジェクトに対する動作は、従来のスレッドローカルGCと本願発明のコピー式スレッドローカルGCとで異なる。
【０１２６】
従来のスレッドローカルGCでは、オブジェクトが生きているか死んでいるかに関係なく共有オブジェクトは回収対象から除外される。このため従来のスレッドローカルGCではフラグメント化が起こる。一方、本願発明のコピー式スレッドローカルGCでは、スレッドローカルヒープ内に１つもGlobal andaccessed from multiple threadsが存在しない限り、生きている共有オブジェクトはスレッドローカルヒープ外へ追い出されるので、フラグメンテーションは起こらない。死んでいる共有オブジェクトについても同様に、スレッドローカルヒープ内に１つもglobal and accessed from multiple threadsが存在しない限り、該オブジェクトは回収されるのでフラグメンテーションは起こらない。
【０１２７】
global and accessedfrom multiple threadsに対する動作に関しては、オブジェクトが生きているか死んでいるかに関係なくどちらの場合も従来のスレッドローカルGCと本願発明のコピー式スレッドローカルGCとで同じである。但し、本願発明のコピー式スレッドローカルGCについては、衝突が検知されその結果、生きている共有オブジェクトはスレッドローカルヒープ外へ追い出すことができなくなり、また死んでいる共有オブジェクトは回収することができなくなるため、フラグメント化が起こる。
【０１２８】
図９のグラフは、SPECjbb2005を用いて、あるGCから次のGCまでの間に生成されたオブジェクトが２回目のGCの時点で図８に示した６つのカテゴリのどれに属するかを調べた結果を示す。図９において、横軸はスレッドに割り付けられるスレッドローカルヒープのサイズを示し、縦軸は各サイズにおける各カテゴリの占める割合を示す。なお、共有オブジェクトが複数のスレッドからアクセスされたことを調べることは困難であること、その一方でSPECjbb2005ではロックの衝突がlong-liveオブジェクトで僅かに起きることだけであることから、図９では、新たに生成されたオブジェクトが次のGCまでに複数のオブジェクトからアクセスされることはないと仮定し、実際には４つのカテゴリについて調べている。
【０１２９】
なお、図９では、スレッドローカルヒープのサイズを変化させて４つのカテゴリの割合を調べているが、実際にスレッドローカルヒープを実装したわけではなく、thread-local heap size per thread = (Java heap size−size of long-lived objects)/8により概算している。図９のグラフを見ると、サイズが３２MBの場合を除いて、共有オブジェクトの合計サイズがスレッドローカルヒープのサイズの５０％を越えている。このことは、従来のスレッドローカルGCでは、フラグメンテーションが非常に激しくなるだけでなく、一回のスレッドローカルGCでは半分以下しか回収できないことを意味する。一方で、死んだ共有オブジェクトは全体の５０％前後を占めており、本願発明のコピー式スレッドローカルGCによれば、このようなオブジェクトは全て回収される。また、生きている共有オブジェクトは、本願発明のコピー式スレッドローカルGCによれば、外へ追い出すことができる。
【０１３０】
図９のグラフにおいて、スレッドローカルヒープのサイズごとの共有オブジェクトの割合を見ると、サイズを小さくしても共有オブジェクトの割合は減らない。従って、本願発明のコピー式スレッドローカルGCの従来法に対する有用性は変わらない。一方で、サイズを小さくするとスレッドローカルヒープ中の共有オブジェクトが他のスレッドからアクセスされる可能性は下がると予測される。従って本願発明のコピー式スレッドローカルGCではスレッドのサイズを小さくしたほうが有利である。但し極端に小さくすると、スレッドローカルGCが頻繁おこる可能性があり、最終的にGCによる処理の時間が全体の実行時間に占める割合が高くなりスループットが落ちることが予測されるという点には注意が必要である。
【０１３１】
以上、実施形態を用いて本発明の説明をしたが、本発明の技術範囲は上記実施形態に記載の範囲には限定されない。上記の実施形態に、種々の変更または改良を加えることが可能であることが当業者に明らかである。従って、そのような変更または改良を加えた形態も当然に本発明の技術的範囲に含まれる。
【図１】
2011134202.tif 000003
【図２】
2011134202.tif 000004
【図３】
2011134202.tif 000005
【図４】
2011134202.tif 000006
【図５】
2011134202.tif 000007
【図６】
2011134202.tif 000008
【図７】
2011134202.tif 000009
【図８】
2011134202.tif 000010
【図９】
2011134202.tif 000011
【図１０】
2011134202.tif 000012