JP2009508187A - クリティカルセクションをトランザクション的に実行することによるロックの回避 - Google Patents

Abstract

クリティカルセクションをトランザクション的に実行することでロックを回避するシステムは、以下のようにプログラムを修正する。（１）クリティカルセクションのトランザクション的実行中に、プログラムはまずクリティカルセクションに関連するロックが別の処理によって保持されているか否かを決定し、保持されている場合にはトランザクション的実行を打ち切る。（２）トランザクション的実行が別の処理からの干渉的データアクセスに遭遇することなく完了する場合には、プログラムはトランザクション的実行中に作成された変更をコミットし、クリティカルセクションの後のプログラムの通常の非トランザクション的実行を任意で再開する。（３）トランザクション的実行中に別の処理からの干渉的データアクセスに遭遇する場合には、プログラムはトランザクション的実行中に作成された変更を破棄し、クリティカルセクションの再実行を試みる。

Description

本発明は、コンピュータシステム内の性能を向上させるための技術に関する。より具体的には、本発明は、コードのクリティカルセクションをトランザクション的に（ｔｒａｎｓａｃｔｉｏｎａｌｌｙ）実行することによって、ロックの使用に伴うオーバーヘッドを回避するための方法および装置に関する。

コンピュータシステム設計者は、現在、チップマルチプロセッサ（ＣＭＰ）の最新世代ならびにより従来型の共有メモリマルチプロセッサ（ＳＭＰ）の中のマルチスレッディングをサポートする機構を開発している。適切なハードウェアサポートにより、マルチスレッディングは、多くのアプリケーションの性能を劇的に増加させることができる。しかしながら、マイクロプロセッサの性能が増加し続けるにつれて、スレッド（処理）間の同期化に費やす時間が、実行時間全体に大きな割合を占めるようになっている。実際、マルチスレッドのアプリケーションがさらにより多くのスレッドを使用し始めるために、この同期化のオーバーヘッドがアプリケーション性能を制限する支配的な要因となる。

プログラマーの観点から考えると、同期化は通常、ロックを使用して達成される。ロックは、一般的に、スレッドがコードのクリティカルセクションに入る前に獲得され、そのスレッドがクリティカルセクションから出た後に解除される。別のスレッドが、同一のロックによって保護されるクリティカルセクションに入ることを望む場合には、別のスレッドは同一のロックを獲得しなければならない。そのロックを獲得できない場合には、先行するスレッドがロックを入手しているため、そのスレッドは、先行スレッドがロックを解除するまで待機しなければならない（ロックは、原子動作またはセマフォなどの多数の方法で実装され得ることに留意する）。

残念ながら、ロックを獲得する処理およびロックを解除する処理は、現代のマイクロプロセッサでは多大の時間を必要とする。それらは、一般的にロードバッファおよびストアバッファをフラッシュする原子動作を伴い、その結果として、何千とまではいかなくとも何百ものプロセッササイクルを完了させる必要がある。

さらに、マルチスレッドのアプリケーションはより多くのスレッドを使用するために、より多くのロックが必要となる。例えば、多数のスレッドが共有データ構造にアクセスする必要がある場合には、全データ構造に単一のロックを使用することは、性能的な理由により実用的ではない。代わりに、データ構造の小部分をロックするために多数の細粒度ロックを使用することが好ましい。これにより、多数のスレッドがデータ構造の異なる部分で並行して操作することができる。しかしながら、データ構造の異なる部分にアクセスするために、単一のスレッドが多数のロックを獲得および解除することも必要になる。それはまた、デッドロック回避などの重要なソフトウェア工学上の懸案事項をもたらす。

一部の場合には、ロックが必要でない時にもロックが使用される。例えば、アプリケーションの多くは「スレッドセーフ」なライブラリルーチンを活用し、それはロックを使用して、マルチスレッドのアプリケーションに対して「スレッドセーフ」であることを確実にする。残念ながら、スレッドセーフなライブラリルーチンが単一スレッドのアプリケーションによってコールされる場合であっても、これらのロックを獲得および解除する際に伴うオーバーヘッドが依然として発生する。

アプリケーションは、一般的に、コードのクリティカルセクション内の相互排他を確実にするためにロックを使用する。しかしながら、多くの場合、クリティカルセクションを同時に実行可能な場合にも、スレッドは相互に干渉しない。これらの場合において、相互排他は、スレッドが実際に相互に干渉するというあり得ないケースを阻止するために使用される。したがって、これらの場合には、ロックを獲得および解除する際に伴うオーバーヘッドは、その多くが無駄になる。

したがって、クリティカルセクションにアクセスするときのロック操作に伴うオーバーヘッドを軽減する方法および装置が必要とされている。

本発明の一実施形態は、トランザクション的にクリティカルセクションを実行することによってロックを回避するシステムを提供する。操作中、システムは、ロックによって保護される一つ以上のクリティカルセクションを含むプログラムを受信する。次いで、システムは、クリティカルセクションと関連するロックを獲得することなく、ロックによって保護されるクリティカルセクションがトランザクション的に実行されるように、プログラムを修正する。

より具体的には、プログラムは以下のように修正される。すなわち、（１）クリティカルセクションのトランザクション的実行中に、プログラムはまず、クリティカルセクションと関連するロックが別の処理によって保持されているか否かを決定し、保持されている場合には、トランザクション的実行を打ち切る。（２）クリティカルセクションのトランザクション的実行が、別の処理からの干渉的データアクセスに遭遇することなく完了する場合には、プログラムはトランザクション的実行中に作成された変更をコミットし、クリティカルセクションの後のプログラムの通常の非トランザクション的実行を（任意で）再開する（システムは、多数の小さいトランザクションを大きいトランザクションに統合することも可能であり、その場合には、システムは、小さいトランザクションに関連するクリティカルセクションの後の、非トランザクション的実行を即時再開しなくてもよいことに、留意する）。（３）クリティカルセクションのトランザクション的実行中に、別の処理からの干渉的データアクセスに遭遇する場合には、プログラムはトランザクション的実行中に作成された変更を破棄し、クリティカルセクションの再実行をゼロ以上の回数試みる。

トランザクション中にロック状態を確認するステップ（上記ステップ（１））によって、クリティカルセクションを非トランザクション的に実行する前に、ロックを実際に獲得するその他の処理と共に、トランザクションの正常な機能が可能となることに留意する。これは、場合により性能が低下する恐れのある全体的な適用ではなく、有用と考えられる場合に技術を選択的に適用可能とすることから有利である。

また、コード修正処理は手動で実行され得ることに留意する。例えば、プログラマーは、頻繁に使用されるクリティカルセクションを特定し得、対応するロック獲得およびロック解除のコールを、ロックを獲得しないでクリティカルセクションがトランザクション的に実行されるようにする特別なコールと手動で置き換え得る。

本実施形態の変形例において、プログラムを修正するステップは、プログラムを修正するためにコンパイラを使用するステップ、プログラムを修正するためにバイナリ修正ツールを使用するステップ、またはプログラムによってアクセスされるライブラリを置き換えるステップ、を含み得る。

本実施形態の変形例において、クリティカルセクションのトランザクション的実行中に、他の処理からのデータアクセスを進めることが許容される。

本実施形態の変形例において、クリティカルセクションを再実行するように試みるステップは、クリティカルセクションをトランザクション的に再実行するように試みるステップを含む。

本実施形態の変形例において、トランザクション的実行の一つ以上の試みの後にクリティカルセクションが成功裡に完了しない場合には、プログラムがクリティカルセクションと関連するロックを獲得し、クリティカルセクションを非トランザクション的に実行し、クリティカルセクションに関連するロックを解除するように、プログラムは修正される。

本実施形態の変形例において、干渉的データアクセスは、トランザクション的実行中にロードされた場所への別の処理によるストア、トランザクション的実行中にストアされた場所への別の処理によるロード、またはトランザクション的実行中にストアされた場所への別の処理によるストア、を含み得る。

本実施形態の変形例において、クリティカルセクションのトランザクション的実行を開始するステップは、レジスタ値およびその他の状態情報をチェックポイントするためのチェックポインティング操作を実行するステップを含む。

以下の説明は、任意の当業者が本発明を作製および使用可能なように提示され、特定の用途およびその要件に照らして提供される。開示される実施形態へのさまざまな修正が当業者には容易に明白であり、本明細書に規定される一般的原理は、本発明の精神および範囲を逸脱することなくその他の実施形態および用途に適用され得る。したがって、本発明は、示される実施形態に限定されることを意図せず、本明細書で開示される原理および特徴と一致する最広義の範囲が与えられるべきである。

本詳細説明に記載されるデータ構造およびコードは、一般的に、コンピュータ読み取り可能な記憶媒体に保存され、それは、コンピュータシステムが使用するコードおよび／またはデータを保存可能な、任意のデバイスまたは媒体であり得る。これは、ディスクドライブ、磁気テープ、ＣＤ（コンパクトディスク）、およびＤＶＤ（デジタル多用途ディスクまたはデジタルビデオディスク）などの磁気および光学式記憶デバイス、ならびに伝送媒体において具現化されるコンピュータ命令信号（信号が変調される搬送波の有無に関わらず）を含むが、それだけに限定されない。例えば、伝送媒体はインターネットなどの通信ネットワークを含み得る。

（コンピュータシステム）
図１は、本発明の実施形態に従ったコンピュータシステム１００を示す。コンピュータシステム１００は、通常、任意の種類のコンピュータシステムをも含み得、マイクロプロセッサベースのコンピュータシステム、メインフレームコンピュータ、デジタルシグナルプロセッサ、携帯型コンピュータデバイス、個人用整理手帳、デバイスコントローラ、および電気製品の計算エンジンを含むが、それだけに限定されない。図１に示されるように、コンピュータシステム１００は、プロセッサ１０１およびメインメモリ（図示せず）に接続されるレベル２（Ｌ２）キャッシュ１２０を含む。プロセッサ１０２は、構造がプロセッサ１０１と同様であるために、プロセッサ１０１のみが以下に説明される。

プロセッサ１０１は、二つのレジスタファイル１０３および１０４を有し、そのうちの一つは、「アクティブレジスタファイル」であり、他方は、バックアップ「シャドウレジスタファイル」である。本発明の一実施形態において、プロセッサ１０１は、レジスタファイル１０３からレジスタファイル１０４への全ての値を即時にコピーするフラッシュコピー操作を提供する。これは、急速なレジスタのチェックポインティング操作を助長し、トランザクション的実行をサポートする。

また、プロセッサ１０１は、加算器１０７および乗算器１０８などのような、一つ以上の機能ユニットをも含む。これらの機能ユニットは、レジスタファイル１０３または１０４から取り出されるオペランドを伴うコンピュータ操作を実行する際に使用される。従来のプロセッサのように、ロードおよびストア操作は、ロードバッファ１１１およびストアバッファ１１２を通過する。

さらに、プロセッサ１０１は、レベル１（Ｌｌ）データキャッシュ１１５を含み、プロセッサ１０１によって使用される可能性の高いデータ項目を保存する。Ｌｌデータキャッシュ１１５におけるラインは、トランザクション的実行中にラインからデータ値がロードされたことを示す、ロードマーキングビット１１６を含むことに留意する。このロードマーキングビット１１６は、図３〜図８を参照して以下に説明されるように、トランザクション的実行中に任意の干渉メモリ参照が発生するか否かを決定するために使用される。また、プロセッサ１０１は、Ｌｌ命令キャッシュ（図示せず）をも含む。

ロードマーキングは、必ずしもＬｌデータキャッシュ１１５で発生する必要がないことに留意する。通常、ロードマーキングは、Ｌ２キャッシュ１２０などの任意のレベルのキャッシュでも、または独立した構造においてさえも発生可能である。しかしながら、性能上の理由により、ロードマーキングはプロセッサにできるだけ近いキャッシュレベルで発生する可能性が高く、それは、この場合にはＬｌデータキャッシュ１１５である。そうでない場合には、ロードは、Ｌｌヒット上であってもＬ２キャッシュ１２０に向かわなくてはならない。

Ｌ２キャッシュ１２０は、プロセッサ１０１において、Ｌｌデータキャッシュ１１５（および対応するＬｌ命令キャッシュ）と連携して動作し、プロセッサ１０２において、Ｌｌデータキャッシュ１１７（および対応するＬｌ命令キャッシュ）と連携して動作する。Ｌ２キャッシュ１２０は、発明者Ｓｈａｉｌｅｎｄｅｒ ＣｈａｕｄｈｒｙおよびＭａｒｃ Ｔｒｅｍｂｌａｙ（公開番号ＵＳ−２００２−０１９９０６６−Ａ１）によって２００２年６月２６日に出願された、名称が「Ｍｅｔｈｏｄ ａｎｄ Ａｐｐａｒａｔｕｓ ｆｏｒ Ｆａｃｉｌｉｔａｔｉｎｇ Ｓｐｅｃｕｌａｔｉｖｅ Ｌｏａｄｓ ｉｎ ａ Ｍｕｌｔｉｐｒｏｃｅｓｓｏｒ Ｓｙｓｔｅｍ」である米国特許出願第１０／１８６，１１８号に記載される逆ディレクトリ構造などの、コヒーレンス機構１２２と関連していることに留意する。このコヒーレンス機構１２２は、キャッシュライン毎に「コピーバック情報」１２１を保持する。このコピーバック情報１２１は、キャッシュラインを別のプロセッサに送信しなければならない場合に、Ｌ２キャッシュ１２０から要求するプロセッサへのキャッシュラインの送信を助長する。

Ｌ２キャッシュ１２０における各ラインは「ストアマーキングビット」を含み、それは、トランザクション的実行中にデータ値がラインに保存されたことを示す。このストアマーキングビットは、図３〜図８を参照して以下に説明されるように、トランザクション的実行中に干渉メモリ参照が発生するか否かを決定するために使用される。ストアマーキングは、必ずしもＬ２キャッシュ１２０で発生する必要がないことに留意する。

理想的には、ストアマーキングは、キャッシュラインがコヒーレントであるプロセッサに最も近いキャッシュレベルにおいて発生する。ライトスルーＬｌデータキャッシュについては、書き込みはＬ２キャッシュ１２０に自動的に伝播する。しかしながら、Ｌｌデータキャッシュがライトバックキャッシュである場合には、ストアマーキングはＬｌデータキャッシュで実行される（キャッシュコヒーレンスプロトコルにより、同一のキャッシュラインを後に修正する任意の他のプロセッサが、Ｌ１キャッシュからキャッシュラインを取り出し、ストアマークを認識することとなることに留意する）。

（クリティカルセクションの実行）
図２Ａは、本発明の実施形態に従って、如何にクリティカルセクションが実行されるかを示す。図２Ａの左側で示されるように、クリティカルセクションを実行するスレッドは、一般的に、クリティカルセクションに入る前に、クリティカルセクションと関連するロックを獲得する。別のスレッドがロックを獲得している場合には、スレッドは、他方のスレッドがロックを解除するまで待機しなければならない。クリティカルセクションを出ると、スレッドはロックを解除する（用語の「スレッド」および「処理」は、本明細書においては互換的に使用されることに留意する）。

ロックは共有データ構造と関連付けられ得る。例えば、共有データ構造にアクセスする前に、スレッドは共有データ構造上でロックを獲得し得る。次に、スレッドは、共有データ構造にアクセスするコードのクリティカルセクションを実行し得る。スレッドが共有データ構造へのアクセスを完了すると、スレッドはロックを解除する。

対照的に、本発明においては、スレッドはロックを獲得せず、その代わりに、クリティカルセクションに入る前に、開始トランザクション的実行（ＳＴＥ）命令を実行する。他のスレッドから干渉されずにクリティカルセクションが成功裡に完了する場合には、スレッドはコミット操作を実行して、トランザクション実行中に作成された変更をコミットする。この一連の事象は、図３〜図８を参照して以下にさらに詳しく説明する。

本発明の一実施形態において、コンパイラは、ロック獲得命令をＳＴＥ命令と置き換え、また、対応するロック解除命令をコミット命令と置き換えることに留意する。置き換えられた命令の間に一対一の対応がなくてもよいことに留意する。例えば、複数の命令から成る単一のロック獲得操作は、単一のＳＴＥ命令によって置き換えられ得る。

何らかの理由により進行できない場合には、多くの場合、ロックに頼る能力を保持することを必要とすることに留意する。また、ソフトウェア工学の観点から、共通パスのみにおいてコードを変換し、非共有パスにおいてロックコードをそのままの状態にしておくことが、しばしば望まれる。これを助長するために、トランザクション的実行のためにクリティカルセクションを変換する際に、ロック獲得はＳＴＥ命令で置き換えられ得、その後に、ロック状態をトランザクション的に読み取りかつロックが保持されていないことを確認するコードが続く（図２Ｂ参照）。

上記の説明は、プロセッサの命令セットが、ＳＴＥ命令およびコミット命令を含むように拡大されたことを想定する。これらの命令は、図３〜図９を参照して以下により詳しく記載される。

（トランザクション的実行処理）
図３は、本発明の実施形態に従って、如何にトランザクション的実行が発生するかを示すフローチャートである。スレッドは、まず、コードのクリティカルセクションに入る前にＳＴＥ命令を実行する（ステップ３０２）。次に、システムは、クリティカルセクション内でコードをトランザクション的に実行するが、トランザクション的実行の結果をコミットしない（ステップ３０４）。

クリティカルセクションのトランザクション的実行の開始時に、プログラムは、クリティカルセクションと関連するロック状態をトランザクション的に読み取り、ロックが保持されていないことを確認する。ロックが保持されている場合には、システムは、トランザクション的実行を打ち切る（ステップ３０３）。クリティカルセクションのトランザクション的実行中に別の処理がロックを獲得している場合には、ロック状態のトランザクション的な読み取りがロック獲得操作によって「干渉される」ために、クリティカルセクションのトランザクション的実行は打ち切られることに留意する。

このトランザクション的実行中、システムは、その他のスレッドによるデータ参照を継続的に監視し、干渉的データアクセス（またはその他の種類の障害）がトランザクション的実行中に発生するか否かを決定する。発生しない場合には、システムはトランザクション的実行中に作成された全ての変更を自動的にコミットし（ステップ３０８）、次に、クリティカルセクションの後のプログラムの通常の非トランザクション的実行を任意で再開する（ステップ３１０）。

反対に、干渉的データアクセスが検知される場合には、システムはトランザクション的実行中に作成された変更を破棄し（ステップ３１２）、クリティカルセクションの再実行を試みる（ステップ３１４）。

本発明の一実施形態において、システムは、ゼロ回、一回、二回、またはそれ以上に、クリティカルセクションをトランザクション的に再実行することを試みる。これらの試みが成功しない場合には、システムは、通常の実行モードで代替のコードブロックを実行する。この代替のコードは、トランザクションの実行を付加的に試み得、かつ、クリティカルセクションに入る前にクリティカルセクションのロックを獲得しクリティカルセクションを出た後にロックを解除する、従来の技術に戻る能力を有し得る。

干渉的データアクセスは、スレッドによってロードマークされたキャッシュラインへの、別のスレッドによるストアを含み得ることに留意する。それはまた、スレッドによってストアマークされたキャッシュラインへの、別のスレッドによるロードまたはストアをも含み得る。

また、干渉的データアクセスを検知する回路網が、従来のキャッシュコヒーレンス回路網を若干修正することによって容易に実装され得ることに、留意する。この従来のキャッシュコヒーレンス回路網は、現在は、所与のキャッシュラインが別のプロセッサにアクセスされたか否かを示す信号を生成する。したがって、これらの信号が、干渉的データアクセスが発生したか否かを決定するために使用され得る。

（トランザクション的実行の開始）
図４は、本発明の実施形態に従った、開始トランザクション的実行（ＳＴＥ）操作を示すフローチャートである。本フローチャートは、図３のフローチャートのステップ３０２の中で何が発生するかを示す。システムは、レジスタファイルをチェックポイントすることによって開始する（ステップ４０２）。これは、レジスタファイル１０３からレジスタファイル１０４へのフラッシュコピー操作を実行することを含む（図１参照）。レジスタ値をチェックポイントすることに加えて、このフラッシュコピーは、実行中のスレッドに関連するさまざまな状態のレジスタをもチェックポイントし得る。通常、フラッシュコピー操作は、対応するスレッドを再開することができる状態にまでチェックポイントする。

同時に、レジスタファイルがチェックポイントされ、また、ＳＴＥ操作が、ストアバッファ１１２を「ゲート」状態にさせる（ステップ４０４）。これにより、ストアバッファにおける既存の入力が、メモリサブシステムに伝播可能となる（したがって、プロセッサのアーキテクチャ状態にコミットされる）が、しかし、トランザクション的実行中に生成される新しいストアバッファの入力がそのように伝播されることは阻止される。

次いで、システムは、キャッシュラインのロードマーキングおよびストアマーキングを含むトランザクション的実行を開始し（ステップ４０６）、必要な場合には、干渉的参照を検知するためにデータ参照を監視する。

（ロードマーキング処理）
図５は、本発明の実施形態に従ったトランザクション的実行中に、如何にロードマーキングが実行されるかを示すフローチャートである。クリティカルセクションのトランザクション的実行中に、システムはロード操作を実行する。このロード操作の実行に際して、ロード操作がロードマークする必要のあるロード操作として特定された場合には、システムは、まず、Ｌｌデータキャッシュ１１５からデータ項目のロードを試みる（ステップ５０２）。ロードによりキャッシュヒットが発生する場合には、システムは、Ｌｌデータキャッシュ１１５における対応するキャッシュラインを「ロードマーク」する（ステップ５０６）。これは、キャッシュラインに対するロードマーキングビットの設定を含む。あるいは、ロードによりキャッシュミスが発生する場合には、システムは、さらなるレベルの記憶階層からキャッシュラインを取り出し（ステップ５０８）、ステップ５０６に進んで、Ｌｌデータキャッシュ１１５におけるキャッシュラインをロードマークする。

（ストアマーキング処理）
図６は、本発明の実施形態に従ったトランザクション的実行中に、如何にストアマーキングが実行されるかを示すフローチャートである。クリティカルセクションのトランザクション的実行中に、システムはストア操作を実行する。このストア操作がストアマークする必要のあるストア操作として特定された場合には、システムは先ず、専用の対応するキャッシュラインをプリフェッチする（ステップ６０２）。ラインが既にキャッシュに位置し、既に専用状態にある場合には、このプリフェッチ操作は何も行なわないことに留意する。

本実施例において、Ｌｌデータキャッシュ１１５はライトスルーキャッシュであり、ストア操作はＬｌデータキャッシュ１１５からＬ２キャッシュ１２０に伝播する。次に、システムは、Ｌ２データキャッシュ１１５におけるストア操作に対応するキャッシュラインのロックを試みる（ステップ６０４）。対応するラインがＬ２キャッシュ１２０にある場合（キャッシュヒット）には、システムは、Ｌ２キャッシュ１２０の中のその対応するキャッシュラインを「ストアマーク」する（ステップ６１０）。これは、キャッシュラインに対するストアマーキングビットの設定を含む。あるいは、対応するラインがＬ２キャッシュ１２０にない場合（キャッシュミス）には、システムは、さらなるレベルの記憶階層からキャッシュラインを取り出し（ステップ６０８）、次にステップ６１０に進んで、Ｌ２キャッシュ１２０におけるキャッシュラインをストアマークする。

次いで、ステップ６１０でキャッシュラインがストアマークされると、システムは、ストアバッファ１１２の入力にストアデータを入力する（ステップ６１２）。このストアデータは、後続のコミット操作が発生するまで、またはトランザクション的実行中の変更が破棄されるまで、ストアバッファ１１２に留まることに留意する。

所与のスレッドによってストアマークされるキャッシュラインは、その他のスレッドによって読み取られ得ることに留意する。これにより、所与のスレッドが失敗し、その一方で他のスレッドが継続し得ることに、留意する。

（コミット操作）
図７は、本発明の実施形態に従って、トランザクション的実行が成功裡に完了した後に、如何にコミット操作が実行されるかを示すフローチャートである。本フローチャートは、図３のフローチャートのステップ３０８の中で何が発生するかを示す。

システムは、ストアマークされたキャッシュラインを、ロックされたもののように処理することによって開始する（ステップ７０２）。これは、ストアマークされたラインを要求するその他のスレッドが、ラインがロックされなくなるまで待機してから、ラインにアクセス可能になることを意味する。これは、従来のキャッシュでラインがロックされる方法に類似している。

次いで、システムは、Ｌｌデータキャッシュ１１５からロードマークを消去する（ステップ７０４）。

次に、システムは、マークする必要があると特定されるストアのために、トランザクション的実行中に生成された、ストアバッファ１１２からの入力を記憶階層にコミットする（ステップ７０６）。各入力がコミットされると、Ｌ２キャッシュ１２０における対応するラインはロック解除される。

また、システムは、レジスタファイルの変更をもコミットする（ステップ７０８）。例えば、これは、図１に示されたシステムにおけるレジスタファイル１０３とレジスタファイル１０４との間のフラッシュコピーを機能的に実行することを含み得る。

（変更破棄）
図８は、本発明の実施形態に従って、トランザクション的実行が不成功に完了した後に、如何に変更が破棄されるかを示すフローチャートである。本フローチャートは、図３のフローチャートのステップ３１２の中で何が発生するかを示す。システムは、まず、トランザクション的実行中に作成されたレジスタファイルの変更を破棄する（ステップ８０２）。これは、トランザクション的実行中に作成されたレジスタファイルの変更を消去するか、または単に無視することを含み得る。これは、トランザクション的実行の開始前に古いレジスタ値がチェックポイントされているために、容易に達成される。また、システムは、Ｌｌデータキャッシュ１１５におけるキャッシュラインからロードマークをも消去し（ステップ８０４）、トランザクション的実行中に生成されたストアバッファの入力を、記憶階層にコミットせずにドレインする（ステップ８０６）。同時に、システムは、対応するＬ２キャッシュラインのマークを解除する。最後に、本発明の一実施形態において、システムはＳＴＥ命令によって特定される目標位置に分岐する（ステップ８０８）。本目標位置においてコードは、クリティカルセクションの再実行を任意で試みる（図１のステップ３１４を参照して上述されたように）か、または、コンテンション軽減のためのバックオフなどの、障害に応じたその他のアクションを取る。

本発明の実施形態の上述の説明は、図示および説明のためのみ提示されている。それらは、余すことなく述べることを意図せず、あるいは本発明を開示される形態に限定することを意図していない。したがって、多くの修正および変形が、当業者にとっては明白である。さらに、上記の開示は本発明を限定することを意図していない。本発明の範囲は、添付の特許請求の範囲によって定義される。

図１は、本発明の実施形態に従ったコンピュータシステムを示す。 図２Ａは、本発明の実施形態に従って、如何にクリティカルセクションが実行されるかを示す。 図２Ｂは、本発明の実施形態に従って、如何にクリティカルセクションが実行されるかの別の例を示す。 図３は、本発明の実施形態に従った、トランザクション的実行処理を示すフローチャートである。 図４は、本発明の実施形態に従った、開始トランザクション的実行（ＳＴＥ）操作を示すフローチャートである。 図５は、本発明の実施形態に従ったトランザクション的実行中に、如何にロードマーキングが実行されるかを示すフローチャートである。 図６は、本発明の実施形態に従ったトランザクション的実行中に、如何にストアマーキングが実行されるかを示すフローチャートである。 図７は、本発明の実施形態に従った、如何にコミット操作が実行されるかを示すフローチャートである。 図８は、本発明の実施形態に従った、トランザクション的実行が不成功に完了した後に、如何に変更が破棄されるかを示すフローチャートである。

Claims (20)

1. クリティカルセクションをトランザクション的に実行することによってロックを回避するようにプログラムを修正するための方法であって、該方法は、
   ロックによって保護される一つ以上のクリティカルセクションを含むプログラムを受信するステップと、
   該クリティカルセクションと関連するロックを獲得することなく、ロックによって保護される該クリティカルセクションがトランザクション的に実行されるように、該プログラムを修正するステップと、
   を包含し、
   該プログラムは、
   クリティカルセクションのトランザクション的実行中に、該プログラムはまず、該クリティカルセクションと関連するロックが別の処理によって保持されているか否かを決定し、保持されている場合には、該トランザクション的実行を打ち切り、
   該クリティカルセクションの該トランザクション的実行が、別の処理からの干渉的データアクセスに遭遇せずに完了する場合には、該プログラムは、該トランザクション的実行中に作成された変更をコミットし、該クリティカルセクションの後の該プログラムの通常の非トランザクション的実行を任意で再開し、
   該クリティカルセクションの該トランザクション的実行中に、別の処理からの干渉的データアクセスに遭遇する場合には、該プログラムは、該トランザクション的実行中に作成された変更を破棄し、該クリティカルセクションを再実行するようにゼロ以上の回数試みる、
   ように修正される、
   方法。
2. 前記プログラムを修正するステップは、
   該プログラムを修正するためにコンパイラを使用するステップ、
   該プログラムを修正するためにバイナリ修正ツールを使用するステップ、
   または、該プログラムによってアクセスされるライブラリを置き換えるステップ、
   を含む、
   請求項１に記載の方法。
3. 前記クリティカルセクションの前記トランザクション的実行中に、他の処理からのデータアクセスを進めることが許容される、請求項１に記載の方法。
4. 前記クリティカルセクションを再実行するように試みるステップは、該クリティカルセクションをトランザクション的に再実行するように試みるステップを含む、請求項１に記載の方法。
5. トランザクション的実行の一つ以上の試みの後に、前記クリティカルセクションが成功裡に完了しない場合には、前記プログラムが、
   該クリティカルセクションと関連するロックを獲得し、
   該クリティカルセクションを非トランザクション的に実行し、
   該クリティカルセクションと関連する該ロックを解除するように、
   該プログラムは修正される、
   請求項４に記載の方法。
6. 前記干渉的データアクセスは、
   トランザクション的実行中にロードされた場所への別の処理によるストアと、
   トランザクション的実行中にストアされた場所への別の処理によるロードと、
   トランザクション的実行中にストアされた場所への別の処理によるストアと、
   を含み得る、
   請求項１に記載の方法。
7. クリティカルセクションのトランザクション的実行を開始するステップは、レジスタ値およびその他の状態情報をチェックポイントするためのチェックポインティング操作を実行するステップを含む、請求項１に記載の方法。
8. コードのクリティカルセクションをトランザクション的に実行することによってロックを回避するための方法であって、該方法は、
   該クリティカルセクションと関連するロックを獲得することなく、プログラム内のコードのクリティカルセクションをトランザクション的に実行するための処理を許容するステップを包含し、
   該クリティカルセクションをトランザクション的に実行するステップは、まず、該クリティカルセクションと関連する該ロックが別の処理に保持されているか否かを決定するステップと、保持されている場合には該トランザクション的実行を打ち切るステップと、を含み、
   該処理が、別の処理からの干渉的データアクセスに遭遇せずに該クリティカルセクションを完了する場合には、該方法は、
   該トランザクション的実行中に作成された変更をコミットするステップと、
   該クリティカルセクションの後の、該プログラムの通常の非トランザクション的実行を任意で再開するステップと、をさらに包含し、
   該クリティカルセクションのトランザクション的実行中に別の処理からの干渉的データアクセスに遭遇する場合には、該方法は、
   該トランザクション実行中に作成された変更を破棄するステップと、
   該クリティカルセクションをゼロ以上の回数再実行するように試みるステップと、をさらに包含する、
   方法。
9. 請求項８に記載の方法であって、前記プログラムを実行する前に、ロックによって保護されるクリティカルセクションがトランザクション的に実行されるように、該プログラムを修正するステップをさらに包含する、方法。
10. 前記プログラムを修正するステップは、
    該プログラムを修正するためにコンパイラを使用するステップ、
    該プログラムを修正するためにバイナリ修正ツールを使用するステップ、
    または、該プログラムによってアクセスされるライブラリを置き換えるステップ、
    を含む、
    請求項９に記載の方法。
11. 前記クリティカルセクションの前記トランザクション的実行中に、他の処理からのデータアクセスを進めることが許容される、請求項８に記載の方法。
12. 前記クリティカルセクションを再実行するように試みるステップは、該クリティカルセクションをトランザクション的に再実行するように試みるステップを含む、請求項８に記載の方法。
13. トランザクション的実行の一つ以上の試みの後に、前記クリティカルセクションが成功裡に完了しない場合には、
    該クリティカルセクションと関連するロックを獲得するステップと、
    該クリティカルセクションを非トランザクション的に実行ステップと、
    該クリティカルセクションと関連する該ロックを解除するステップと、
    をさらに包含する、
    請求項１２に記載の方法。
14. クリティカルセクションのトランザクション的実行を開始するステップは、レジスタ値およびその他の状態情報をチェックポイントするためのチェックポインティング操作を実行するステップを含む、請求項８に記載の方法。
15. 前記干渉的データアクセスは、
    トランザクション的実行中に前記処理がロードされた場所への別の処理によるストアと、
    トランザクション的実行中に該処理がストアされた場所への別の処理によるロードと、
    トランザクション的実行中に該処理がストアされた場所への別の処理によるストアと、
    を含み得る、
    請求項８に記載の方法。
16. クリティカルセクションをトランザクション的に実行することによってロックを回避するためにプログラムを修正する装置であって、該装置は、
    該クリティカルセクションと関連するロックを獲得することなく、ロックによって保護されるクリティカルセクションがトランザクション的に実行されるように、該プログラムを修正するように構成される、修正機構を備え、
    該修正機構は、該プログラムを、
    クリティカルセクションのトランザクション的実行中に、該プログラムは、まず、該クリティカルセクションと関連するロックが別の処理によって保持されているか否かを決定し、保持されている場合には、該トランザクション的実行を打ち切り、
    該クリティカルセクションの該トランザクション的実行が、別の処理からの干渉的データアクセスに遭遇せずに完了する場合には、該プログラムは、該トランザクション的実行中に作成された変更をコミットし、該クリティカルセクションの後の該プログラムの通常の非トランザクション的実行を任意で再開し、
    該クリティカルセクションのトランザクション的実行中に、別の処理からの干渉的データアクセスに遭遇する場合には、該プログラムは、該トランザクション的実行中に作成された変更を破棄し、該クリティカルセクションの再実行をゼロ以上の回数試みるように、
    修正するように構成される、
    装置。
17. 前記修正機構は、
    コンパイラ、
    バイナリ修正ツール、
    または、前記プログラムによってアクセスされるライブラリを置き変える機構、
    である、
    請求項１６に記載の装置。
18. 前記クリティカルセクションの前記トランザクション的実行中に、他の処理からのデータアクセスを進めることが許容される、請求項１６に記載の装置。
19. 前記クリティカルセクションを再実行するように試みるステップは、前記クリティカルセクションをトランザクション的に再実行するように試みるステップを含む、請求項１６に記載の装置。
20. トランザクション的実行の一つ以上の試みの後に、前記クリティカルセクションが成功裡に完了しない場合には、前記プログラムが、
    該クリティカルセクションと関連するロックを獲得し、
    該クリティカルセクションを非トランザクション的に実行し、
    該クリティカルセクションと関連する該ロックを解除するように、
    該プログラムは修正される、
    請求項１９に記載の装置。

Images