(57)【要約】  トランザクショナルメモリシステムにおける並列入れ子状トランザクションをサポートする様々な技術及び技法を開示する。複数の閉じた入れ子状トランザクションが、単一の親トランザクションについて作成され、閉じた入れ子状トランザクションは、並列入れ子状トランザクションとして並行して実行される。様々な技術を用いて、並列入れ子状トランザクションの作用は、親トランザクションがコミット処理する迄、親トランザクション外部の他のトランザクションから隠されるのを保証する。例えば、版数化書込ロックが並列入れ子状トランザクションによって用いられる。トランザクショナルメモリワードが書込ロックから版数化書込ロックに変化する時、エントリがグローバル版数化書込ロックマップに作られ、版数化書込ロックが置き換えた書込ログエントリへのポインタを記憶する。版数化書込ロックがトランザクション処理中に遭遇された時、グローバル版数化書込ロックマップが参照され、版数化書込ロックを書込ログエントリへのポインタに変換する。
2010539609.tif 000002
【特許請求の範囲】
【請求項１】
コンピュータ実行可能命令が記録されたコンピュータ読取可能媒体であって、
単一の親トランザクションについて複数の閉じた入れ子状トランザクションを作成するステップ（２０６）と、
前記複数の閉じた入れ子状トランザクションを、並列入れ子状トランザクションとして並行実行するステップ（２０８）と
をコンピュータに実行させるコンピュータ実行可能命令が記録されていることを特徴とするコンピュータ読取可能媒体。
【請求項２】
前記並列入れ子状トランザクションが一度に全て作成される（２４４）ことを特徴とする請求項１に記載のコンピュータ読取可能媒体。
【請求項３】
前記並列入れ子状トランザクションの各々の作成時に、並列入れ子状トランザクションエントリが前記単一の親トランザクションのログに作成される（２７２）ことを特徴とする請求項２に記載のコンピュータ読取可能媒体。
【請求項４】
前記並列入れ子状トランザクションエントリの各々は、前記単一の親トランザクションのログから、前記並列入れ子状トランザクションのうちの対応する１つによって、次に利用可能な並列入れ子状トランザクションインデックスに基づいた比較処理及びスワップ処理を用いて、読み出される（２７４）ことを特徴とする請求項３に記載のコンピュータ読取可能媒体。
【請求項５】
ロックエントリが所与の並列入れ子状トランザクションのログにおいてコミット処理中に遭遇される時、ロック所有権及び前記ログエントリが、前記単一の親トランザクションに移転される（４４４）ことを特徴とする請求項１に記載のコンピュータ読取可能媒体。
【請求項６】
前記並列入れ子状トランザクションは、必要に応じて作成される（２４４）ことを特徴とする請求項１に記載のコンピュータ読取可能媒体。
【請求項７】
前記並列入れ子状トランザクションの各々が作成される際に、前記単一の親トランザクションのログにおいて、対応する並列入れ子状トランザクションエントリのために領域（room）が割り当てられる（２９２）ことを特徴とする請求項６に記載のコンピュータ読取可能媒体。
【請求項８】
前記並列入れ子状トランザクションの各々がコミット処理する時、対応する並列入れ子状トランザクションエントリが、前記単一の親トランザクションのログにおいて作成される（２９４）ことを特徴とする請求項７に記載のコンピュータ読取可能媒体。
【請求項９】
前記単一の親トランザクションのログは、複数の並列入れ子状兄弟トランザクション中のアクセスのために同期化される（２９６）ことを特徴とする請求項７に記載のコンピュータ読取可能媒体。
【請求項１０】
前記並列入れ子状トランザクションの作用を、前記親トランザクションがコミット処理する迄、前記親トランザクション外部にある他のトランザクションから隠すステップ（２０８）をコンピュータに実行させるコンピュータ実行可能命令を更に含むことを特徴とする請求項１に記載のコンピュータ読取可能媒体。
【請求項１１】
所与の並列入れ子状トランザクションの作用を、前記所与の並列入れ子状トランザクションが前記親トランザクション中にコミット処理される迄、前記所与の親トランザクション外部にある他のトランザクションから隠すステップ（４４４）をコンピュータに実行させるコンピュータ実行可能命令を更に含むことを特徴とする請求項１０に記載のコンピュータ読取可能媒体。
【請求項１２】
並列入れ子状トランザクションに版数化書込ロックを用いる方法であって、
トランザクショナルメモリワードが書込ロックから版数化書込ロックに変化する時、グローバル版数化書込ロックマップにエントリを作り、前記版数化書込ロックが置き換えた書込ログエントリへのポインタを記憶するステップ（３４４）と、
前記版数化書込ロックがトランザクション処理中に遭遇される時、前記グローバル版数化書込ロックマップを参照して、前記版数化書込ロックを前記書込ログエントリへのポインタに変換するステップ（３４６）と
を含むことを特徴とする方法。
【請求項１３】
前記版数化書込ロックを用いて、並列入れ子状トランザクションが、親トランザクションによって保持されたロックを獲得及び解除できることによって、前記親トランザクションの隔離境界を破ることなく適切に同期化する（３５２）ことを特徴とする請求項１２に記載の方法。
【請求項１４】
前記トランザクショナルメモリワードに記憶される版数番号が、版数及び総数ペア内又は前記版数化書込ロック内に保持されているか否かに関わらず、常に増分される（３４８）ことを特徴とする請求項１２に記載の方法。
【請求項１５】
悲観的な読込を獲得する時、前記トランザクショナルメモリワードは、前記版数化書込ロックに切り替えられて、悲観的な読込側の総数を記憶する領域を提供するステップをさらに含み、前記版数化書込ロックが、親トランザクションが既に書込ロックしたオブジェクト上に兄弟トランザクションが悲観的な読込を実行したであろうことを示す（７９６）ことを特徴とする請求項１２に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、トランザクショナルメモリにおける並列入れ子状トランザクションに関する。
【背景技術】
【０００２】
ソフトウェアトランザクショナルメモリ（ＳＴＭ）とは、並行コンピューティングにおいて共有メモリへのアクセス制御をなすデータベーストランザクションに類似する並行制御メカニズムである。トランザクショナルメモリの分野におけるトランザクションとは、共有メモリに対する一連の読込及び書込を実行する一片のコードである。換言すれば、トランザクションは、１つ以上のオブジェクト内のデータにアクセスする。トランザクショナルメモリの分野におけるオブジェクトとは、１つのエンティティとしてロックされた１組の連結されたメモリロケーションである。また、この分野におけるオブジェクトは、静的変数又は１組のかかる変数であるかもしれないし、１組のキャッシュライン（cache line）であるかもしれない。
【０００３】
ＳＴＭは、伝統的なロック機構に代わるものとして用いられる。ＳＴＭは、並行プログラムがより単純に書かれるのを可能とする。トランザクションは、あたかも一連のコードが隔離されて実行されているかのように想定される一連のコードを示す。隔離のこの錯覚は、オブジェクトのきめの細かいロック処理によって達成されるし、トランザクションが他の何らかのトランザクションと衝突すると発見された場合に、トランザクションの副作用がロールバック処理されるのを可能とするモードで実行されることによって達成される。我々は、当該アクセスのために生成されたコードがこれらロック処理及びロールバック処理機構のサポートを含むように改変された場合に、あるデータアクセスが「トランザクションにされる（transacted）」と称する。
【０００４】
トランザクションは、入れ子状にされてもよく、開いたか又は閉じた入れ子状として分類され得る。あるスレッドがトランザクションを現在実行し、新たな不可分ブロック（atomic block）の始点に達する場合、この不可分ブロックは、現在時点で実行されている親トランザクションの閉じた入れ子状子トランザクションとして実行される。この入れ子状トランザクションは、囲んでいるトランザクション（enclosing transaction）と同一の隔離境界（isolation boundary）内で実行され、ちょうど当該囲んでいるトランザクション内でアクセスされる他のメモリの如く、入れ子状トランザクションの作用は、当該囲んでいるトランザクションがコミット処理する時に見えるようになるだけである。換言すれば、親トランザクションが有効に一時停止され、閉じた入れ子状トランザクションは、当該親トランザクションにおける処理が再開される前に、完了に向って実行することが許される。入れ子状トランザクションがロールバック処理される時、その暫定的な作用は元通りにされ、親トランザクションの状態は入れ子状トランザクションが開始された時点に回復される。
【０００５】
所与のスレッドよって実行されている「最も外側の」トランザクションは入れ子状にされていない。我々は、これをトップレベルのトランザクションと称する。このトップレベルのトランザクションは、入れ子状トランザクションがその１部分になるように不可分的に実行しなければならない。入れ子状にするのが発生するのは、例えば、ある抽象作用（abstraction）Ａ及びＢの各々が内部表現不変量（internal representation invariants）を有する場合であり、従って、それら抽象作用は、並行スレッドによる使用中にさえ維持することを欲し、これら不変量が並行アクセスよって侵害されないことを保証するために、それらのメソッドの実行において不可分ブロックを用いた場合である。ここで、あるより高レベルの抽象作用Ｃが、その実行においてインスタンスＡ及びＢを用い、これらインスタンスＡ及びＢに関係するある不変量を有すると仮定する。メソッドＣは、トランザクションを用いてこの不変量が侵害されないことを保証するであろう。もしメソッドＡ及びＢがＣのトランザクション内で使われる場合、メソッドＡ及びＢにおけるトランザクションは（この使用において）入れ子状にされる。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
現行のトランザクションナルメモリシステムは、１つのトランザクションの隔離境界内で実行される作業が、実行中の複数の並行スレッド間で分散されるのを可能とはしていない。現行のシステムにおいて、１つのトランザクションは、１つの入れ子状子トランザクションを有するだけかもしれない。かかるシステムのセマンティクス（semantics）は、トランザクション内でのかかる並列化を単純には可能とはしないし、１つ以上の入れ子状トランザクションを一度に実行する試みは、親トランザクションのログ中で順序無くして混在された入れ子状トランザクションログのエントリや他のエラーを生むであろうし、基本的な基礎をなすように細かく粒状化されたロック処理プロトコルの故障は隔離の錯覚を提供することとなる。
【課題を解決するための手段】
【０００７】
トランザクショナルメモリシステムにおける並列入れ子状トランザクション（parallel nested transaction）をサポートする様々な技術及び技法を開示する。複数の閉じた入れ子状トランザクションが単一の親トランザクションについて作成され、当該閉じた入れ子状トランザクションは、並列入れ子状トランザクションとして並行して実行される。様々な技術を用いて、並列入れ子状トランザクションの作用が、親トランザクションがコミット処理する迄、親トランザクション外側の他のトランザクションから隠されるのを保証する。
【０００８】
一実施形態では、版数化された書込ロック（versioned write lock）が並列入れ子状トランザクションと共に用いられる。トランザクショナルメモリワード（transactional memory word）が書込ロックから版数化書込ロックに変わるとき、グローバル版数化書込ロックマップ（global versioned write lock map）にエントリが作られ、当該版数化書込ロックが置き換えた書込ログエントリへのポインタを記憶する。版数化書込ロックがトランザクション処理中に遭遇（encountered）されたとき、グローバル版数化書込ロックマップが参照され、版数化書込ロックを書込ログエントリへのポインタに変換する。
【０００９】
他の実施形態では、ロールバック処理のための複製の書込ロックの解除が並列トランザクションのためにサポートされる。並列入れ子状トランザクションのロールバック処理中、書込ロックを表す第１の書込ログエントリが遭遇される。当該書込ロックが複製であると判定された場合、グローバルロックが獲得され、グローバル版数化書込ロックマップへのアクセスを同期するのに用いられる。
【００１０】
さらに他の実施形態では、楽観的な読込検証（optimistic read validation）が並列入れ子状トランザクションについてサポートされる。楽観的な読込の検証中、版数化書込ロックが兄弟（sibling）並列入れ子状トランザクションからの衝突を示す場合、並列入れ子状トランザクションがドゥーム（doom）処理されるべきか否かを決定する情報が参照される。一実施形態において、当該情報は、版数化書込ロック内及びグローバル版数化書込ロックマップ内に格納される。
【００１１】
更なる実施形態では、書込ロック獲得（write lock acquisition）が並列入れ子状トランザクションについてサポートされる。並列入れ子状トランザクションのための書込ロックを獲得する試みに応じて、トランザクショナルメモリワードが読み込まれ、書込ロックが得られる否かを判定するために分析される。トランザクショナルメモリワードが版数化書込ロックを示す場合、グローバル版数化書込ロックマップがアクセスされ、第１の書込ログエントリを指示する書込ログエントリポインタが読み出される。
【００１２】
さらに他の実施形態では、悲観的な読込（pessimistic read）が並列入れ子状トランザクションについてサポートされる。悲観的な複製化検出データ構造（duplication detection data structure）が並列入れ子状トランザクションのために作成される。並列入れ子状トランザクションにおける各悲観的な読込毎に、エントリが当該データ構造内に作られる。並列入れ子状トランザクションをコミット処理するとき、新たな悲観的な読込ロックが直近の親トランザクションに渡され、当該直近の親トランザクションの別の悲観的な複製化検出データ構造内に、兄弟トランザクション間の同期によってエントリが作られる。悲観的な複製化検出データ構造は、悲観的な読込から書込ロックへの格上げ（upgrade）にも用いられ得る。
【００１３】
さらに他の実施形態では、再試行動作（retry operation）が並列入れ子状トランザクションについてサポートされる。並列入れ子状トランザクションであるか又は並列入れ子状トランザクションの子トランザクションであるトランザクションが再試行を実行する時に、当該トランザクションの読込セット（read set）が再試行のために登録される。再試行を当該トランザクションの親である並列入れ子状トランザクションを過ぎて伝播する判定がなされた時、読込セットは、登録されたままで親の読込セットの部分をなす。
【００１４】
更なる実施形態では、書込アボート処理補償マップ（write abort compensation map）が並列入れ子状トランザクションに用いられて、不正にドゥーム処理された親トランザクションを検出及び処置する。書込アボート処理補償マップは、ロールバック処理中の並列入れ子状トランザクションについて新たな書込ロックを解除する時に作られる。並列入れ子状トランザクションがロールバック処理される時、解除された新たな書込ロック毎に、エントリが書込アボート処理補償マップ内に作られる。
【００１５】
上述した概要は、以下の発明の詳細な説明で更に説明される内容を単純化した形式で概念の抜粋を紹介するために提供される。本概要は、請求される発明の内容の鍵となる特徴又は本質的な特徴を識別することを意図せず、請求される発明の範囲を決定することを目的として用いられることも意図しない。
【図面の簡単な説明】
【００１６】
【図１】一実施形態のコンピュータシステムのブロック図である。
【図２】図１のコンピュータシステム上で動作する、一実施形態のトランザクショナルメモリアプリケーションのブロック図である。
【図３】図１のシステムの一実施形態における処理フローチャートであり、複数の並列トランザクションが単一の親トランザクションの下で入れ子状にされるのを可能とするステージを示す。
【図４】図１のシステムの一実施形態における処理フローチャートであり、並列入れ子状トランザクションの数が前もって既知である時、並列入れ子状トランザクションエントリを親ログに割り当てるステージを示す。
【図５】図１のシステムの一実施形態における処理フローチャートであり、並列入れ子状トランザクションの数が前もって既知ではない時、並列入れ子状トランザクションエントリを親ログに割り当てるステージを示す。
【図６】一実施形態におけるトランザクショナルメモリワードの構造例を示す図である。
【図７】図１のシステムの一実施形態における処理フローチャートであり、版数化書込ロックを用いて、並列入れ子状トランザクションの入れ子を保証すると共に適切に構成するステージを示す。
【図８】図１のシステムの一実施形態における処理フローチャートであり、書込ロックを獲得して入れ子状トランザクションを適切に処置するステージを示す。
【図９】図１のシステムの一実施形態における処理フローチャートであり、書込ロックを獲得して、入れ子状トランザクションを適切に処置するステージを示す。
【図１０】図１のシステムの一実施形態における処理フローチャートであり、コミット処理のために何らかの種類の書込を解除して入れ子状トランザクションを適切に処置するステージを示す。
【図１１】図１のシステムの一実施形態における処理フローチャートであり、ロールバック処理のために新たな書込ロックを解除して入れ子状トランザクションを適切に処置するステージを示す。
【図１２】図１のシステムの一実施形態における処理フローチャートであり、ロールバック処理のために複製書込ロックを解除して入れ子状トランザクションを適切に処置するのに伴われるステージを示す。
【図１３】図１のシステムの一実施形態における処理フローチャートであり、楽観的な読込ロックの獲得の実行を示す。
【図１４Ａ】図１のシステムの一実施形態における処理フローチャートであり、楽観的な読込の検証実行を示す。
【図１４Ｂ】図１のシステムの一実施形態における処理フローチャートであり、楽観的な読込の検証実行を示す。
【図１４Ｃ】図１のシステムの一実施形態における処理フローチャートであり、楽観的な読込の検証実行を示す。
【図１４Ｄ】図１のシステムの一実施形態における処理フローチャートであり、楽観的な読込の検証実行を示す。
【図１５】図１のシステムの一実施形態における処理フローチャートであり、並列入れ子状トランザクションによる悲観的な読込の正しい動作を保証するステージを示す。
【図１６】図１のシステムの一実施形態の場合における処理フローチャートであり、悲観的な読込ロックを書込ロックに格上げするステージを示す。
【図１７Ａ】図１のシステムの一実施形態における処理フローチャートであり、悲観的な読込ロックの獲得の実行を示す。
【図１７Ｂ】図１のシステムの一実施形態における処理フローチャートであり、悲観的な読込ロックの獲得の実行を示す。
【図１７Ｃ】図１のシステムの一実施形態における処理フローチャートであり、悲観的な読込ロックの獲得の実行を示す。
【図１７Ｄ】図１のシステムの一実施形態における処理フローチャートであり、悲観的な読込ロックの獲得の実行を示す。
【図１８】図１のシステムの一実施形態における処理フローチャートであり、再試行が並列入れ子状トランザクションによって正しく働くのを可能とするステージを示す。
【図１９】図１のシステムの一実施形態における処理フローチャートであり、書込アボート処理補償マップを並列入れ子状トランザクションによって用いるステージを示す。
【発明を実施するための形態】
【００１７】
本明細書における技術及び技法は、トランザクショナルメモリシステムとしての一般的な文脈において説明されるが、本システムはトランザクショナルメモリシステムに加えて他の目的に供されてもよい。一実施形態において、本明細書において説明される技術の１つ以上は、ＭＩＣＲＯＳＯＦＴ（登録商標）．ＮＥＴフレームワークの如きフレームワークプログラム内の態様として実施され得るか、又はソフトウェアアプリケーションを開発する開発者にプラットフォームを提供する他の何らかのタイプのプログラム又はサービスから実施され得る。他の実施形態において、本明細書において説明される技術の１つ以上は、並行環境において実行されるアプリケーションの開発を取扱う他のアプリケーションを備える態様においても実施される。
【００１８】
背景技術において説明したように、入れ子状トランザクションは、自身が含んでいる隔離境界か又は親のトランザクションと同一の隔離境界の部分にその作用が及ぶ場合に閉じられていると見做される。本明細書において説明される様々な技術及び技法を用いることよって、トランザクションは同時に複数の閉じた入れ子状トランザクションを有してもよい。これらは、「複数の並列入れ子状トランザクション（parallel nested transactions）」（複数のＰＮＴ）と称される。囲んでいる単一のトランザクション下の複数のＰＮＴの全ては、トランザクションの「並列子トランザクション」と称され、当該囲んでいるトランザクションは「並列親トランザクション」と称される。並列親トランザクション及びその子トランザクションは「並列入れ子」と称される。１つのＰＮＴの「兄弟トランザクション」は、（ある入れ子レベルで）同一の並列親トランザクション内に囲まれた他のＰＮＴである。一実施形態において、各ＰＮＴは、ほとんど通常の閉じた入れ子状トランザクションのように実行され、その作用は囲んでいるトランザクション内に隔離され、並列親トランザクションがコミット処理する時にのみ並列入れ子を越えてその作用が見えるようになる。しかし、各ＰＮＴは、あたかもそれがトップレベルのトランザクションであるかのように、その兄弟トランザクションから隔離されている。ＰＮＴの作用は、それ自身がコミット処理する時のみ、その兄弟トランザクションから見えるようになる。
【００１９】
図１に示されるように、本システムの１つ以上の部分の実装に用いる例示的なコンピュータシステムは、コンピュータ装置１００の如きコンピュータ装置を含む。その最も基本的な構成において、コンピュータ１００は、典型的には少なくとも１つの処理装置１０２とシステムメモリ１０４とを含む。コンピュータ装置の実際の構成及びタイプに依存して、システムメモリ１０４は（ＲＡＭの如き）揮発性媒体、（ＲＯＭ、フラッシュメモリ、その他の如き）不揮発性媒体、又はかかる２つのタイプの組み合わせであってもよい。この最も基本的な構成は破線１０６によって示されている。
【００２０】
さらに、装置１００は、また、付加的な態様／機能を有してもよい。例えば、装置１００は、また、限定するものではないが、磁気又は光学ディスク又はテープを含む（着脱可能及び／又は着脱不能な）付加的な記憶装置を含んでもよい。かかる付加的な記憶装置は、着脱可能な記憶装置１０８及び着脱不能な記憶装置１１０として図１に示されている。コンピュータ記憶媒体としては、コンピュータ読取可能命令、データ構造、プログラムモジュール又は他のデータの如き情報記憶のための何らかの方法又は技術で実現される、揮発性及び不揮発性の着脱可能及び着脱不能な媒体を含む。メモリ１０４、着脱可能記憶装置１０８及び着脱不能記憶装置１１０は、コンピュータ記憶媒体の全ての例である。コンピュータ記憶媒体は、限定されるものではないが、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ若しくはその他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）若しくは他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置若しくは他の磁気記憶装置、又は所望の情報を記憶するのに用いられると共に装置１００よってアクセスされ得る何らかの他の媒体であってもよい。かかる何らかのコンピュータ記憶媒体は、装置１００の一部であってもよい。
【００２１】
コンピュータ装置１００は、コンピュータ装置１００が他のコンピュータ／アプリケーション１１５と通信するのを可能とする１つ以上の通信接続部１１４を含む。装置１００は、また、キーボード、マウス、ペン、音声入力装置、タッチ入力装置、その他の如き入力装置１１２を含んでもよい。ディスプレイ、スピーカ、プリンタ、その他の如き出力装置１１１が含まれてもよい。これらの装置は、周知の技術であり、ここで詳細に説明しない。一実施形態において、コンピュータ１００はトランザクショナルメモリアプリケーション２００を含む。トランザクショナルメモリアプリケーション２００は、図２において更に詳細に説明する。
【００２２】
図１に続いて図２を参照すると、コンピュータ１００上で動作しているトランザクショナルメモリアプリケーション２００が示されている。トランザクショナルメモリアプリケーション２００は、コンピュータ１００上に存在するアプリケーションプログラムの１つである。しかし、トランザクショナルメモリアプリケーション２００は、１つ以上のコンピュータ及び／又は図１に示されたものとは異なるコンピュータ上で、コンピュータ実行命令として代替的に又は付加的に実施され得ることが理解されるであろう。代替的に又は付加的に、トランザクショナルメモリアプリケーション２００の１つ以上の部分は、他のコンピュータ及び／又はアプリケーション１１５において、システムメモリ１０４の部分であることが可能であり、又はコンピュータソフトウェア技術においてあり得る他のかかる変容が可能である。
【００２３】
トランザクショナルメモリアプリケーション２００はプログラム論理部２０４を含み、これは本明細書において説明される技術のある部分又は全てを実行することを担う。プログラム論理部２０４は、複数の並列のトランザクションが単一の親トランザクションの下で入れ子にされるのを可能とする論理部２０６を（図３に関して以下に説明されるように）含み、並列入れ子状トランザクションが入れ子にされ、他の閉じた入れ子状トランザクションと適切に合成されるのを（図７〜図１４に関して以下に説明されるように）可能とする論理部２０８と、並列入れ子状トランザクションが独立したログを伴って実行され、ロック所有権及びログを、親トランザクションへ低い競合で以て移転するのを（図４及び５に関して以下に説明されるように）可能とする論理部２１０と、並列入れ子状トランザクションを同一のトランザクションにおいて楽観的及び悲観的な読込のために（図１５〜図１７に関して以下に説明されるように）活性化（enabling）する論理部２１２と、並列入れ子状トランザクションをインプレース（in-place）書込又はバッファード（buffered）書込のために（図７、図１１及び図１２に関して以下に説明されるように）活性化する論理部２１４と、再試行が並列入れ子状トランザクションによって正しく働くのを（図１８に関して以下に説明されるように）可能とする論理部２１６と、書込アボート処理補償マップが並列入れ子状トランザクションによって正しく働くのを（図１９に関して以下に説明されるように）可能とする論理部２１８と、アプリケーションを動作せしめる他の論理部２２０とを含む。
【００２４】
図１〜図２に続いて図３〜図１９を参照して、トランザクショナルメモリアプリケーション２００の１つ以上の実施形態による複数のステージを更に詳細に説明する。ある実施形態において、図３〜図１９のプロセスは、コンピュータ装置１００で動作する論理部で少なくとも部分的に実行される。図３は、複数の並列トランザクションが単一の親トランザクションの下で入れ子にされるのを可能とする複数のステージからなる一実施形態を示す。このプロセスは、機能又は他の態様を提供する始点２４０で始まり、実行可能状態にある１組の並列入れ子状トランザクションを作成する（ステージ２４２）。１組の並列入れ子状トランザクションは、所与の親トランザクションについて全て一度に又は必要に応じて遅延されて作成される（ステージ２４４）。特別な論理部が用いられてトランザクション方式で並列入れ子状トランザクションを、実行、コミット処理、ロールバック処理、再実行及び再試行する（ステージ２４６）。並列入れ子状トランザクションが終了する時、当該並列入れ子状トランザクションは、それ自身及びその兄弟トランザクションの全てが完了した後に破壊されなければならない（ステージ２４８）。このプロセスは終点２５０で終わる。
【００２５】
図４及び図５は、並列入れ子状トランザクションエントリを親ログにおいて割り当てるプロセスを示す。並列入れ子状トランザクションは、図４及び５で説明される割当技術の１つによって割り当てられた後に、独立したログを伴って実行され、ロック所有権、ログ及び他のデータを親トランザクションに低い競合で以て移転することが可能である。図４に戻ると、並列入れ子状トランザクションの数が事前に既知である時、並列入れ子状トランザクションエントリを親ログにおいて割り当てる一実施形態が示されている。このプロセスは、始点２７０で開始され、並列入れ子状トランザクションの数が事前に既知であることから、何らかのＰＮＴが実行開始される前に、入れ子における各並列入れ子状トランザクション（ＰＮＴ）毎に、１つの並列入れ子状トランザクションエントリ（ＰＮＴＥ）が作成される（ステージ２７２）。ロールバック処理又はコミット処理中に必要な時、並列入れ子状トランザクションは、親トランザクションから並列入れ子状トランザクションエントリを最小同期で読み出す。一実施形態において、予め割り当られたＰＮＴＥは、親トランザクションにおいて配列状で保持される。ＰＮＴは、次に利用可能なＰＮＴＥへのポインタを、次に利用可能な並列入れ子状トランザクションインデックスに基づいた単純な比較処理及びスワップ処理によって、取得してもよい（ステージ２７４）。比較処理及びスワップ処理（ＣＡＳ）は、所与の値と所与のメモリロケーションとの間の比較を微細に実行する処理であり、それらが一致する場合、所与の新しい値がメモリロケーションに記憶される。それらが一致しない場合、何ら動作はなされない。異なる複数のＣＰＵ及びオペレーティングシステムにおいて、ＣＡＳ処理、ハードウェア及びソフトウェアを実行する多くの方法が存在する。本明細書において用いられる用語ＣＡＳは、これらの方法の全てをカバーする一般的な意味で用いられる。
【００２６】
並列入れ子状トランザクションは、親ログにおける並列入れ子状トランザクションエントリに情報を充填する（ステージ２７６）。一実施形態において、当該情報は、子トランザクションについて、子ログへのポインタと、書込アボート処理補償マップへのポインタとを含み、及び／又は適用可能ならば悲観的な読込オブジェクトテーブルを含む。書込アボート処理補償マップは、図１９で更に詳細で説明する。悲観的な読込オブジェクトテーブルは、図１５で更に詳細に説明する。このプロセスは終点２７８で終わる。
【００２７】
図５は、並列入れ子状トランザクションの数が事前に既知ではない時、並列入れ子状トランザクションエントリを親ログに割り当てる複数のステージからなる一実施形態を示す。このプロセスは、始点２９０で始まり、並列入れ子状トランザクションが作成される時、新たな並列入れ子状トランザクションエントリのために領域（room）を親ログにおいて割り当てる（ステージ２９２）。並列入れ子状トランザクションがコミット処理する時、並列入れ子状トランザクションエントリが親ログに作成される（ステージ２９４）。親ログへのアクセスは、親トランザクションの現在ログポイントを動かすように同期化され、並列入れ子状トランザクションエントリのための次に利用可能なスペースへのアクセスを獲得する（ステージ２９６）。並列入れ子状トランザクションは、親ログにおける並列入れ子状トランザクションエントリに情報を充填する（ステージ２９８）。一実施形態において、当該情報は、子トランザクションについて、子ログへのポインタと、書込アボート処理補償マップへのポインタとを含み、及び／又は適用可能ならば悲観的な読込オブジェクトテーブルを含む。書込アボート処理補償マップは、図１９で更に詳細で説明する。悲観的な読込オブジェクトテーブルは、図１５で更に詳細に説明する。このプロセスは終点３００で終わる。
【００２８】
図６は、一実施形態のトランザクショナルメモリワード（ＴＭＷ）の構造例３２０を示し、様々なロック状態に印を与えるのに用いられる様々なビット３２２を備えている。一実施形態では、ＴＭＷは各オブジェクトに関連付けられる。一実施形態では、単一のハードウェアワード表現が用いられるが、複数のＴＭＷについては、記憶されるべき情報をロック可能とする幾つかの他の表現があり得る。本明細書で説明される構造例において、ＴＭＷは、関連付けられたオブジェクトが書込ロックされるか又は解除されていることを示してもよい。ＴＭＷの１つのビットはこの区別にあてがわれる。ＴＭＷが書込ロックされていない場合、ＴＭＷは、版数番号(version number)／総数（count）ペア３２４（Ｖ／Ｃペア）と称される悲観的な読込側の版数番号及び総数を含む。この状態において、ＴＭＷの幾数のビットがオブジェクトの版数番号を記録し、オブジェクト上の悲観的な読込ロックを現在保持しているトランザクションの総数を残りのビットが表す。トランザクションがオブジェクトに書込ロックを保持する時、このロックは２つの種類からなり得る（当該ＴＭＷにおける他のビットよって区別される）。通常、書込ロックされたＴＭＷの残りのビットは、ロックしているトランザクションの書込ログにおけるエントリへのポインタ３２６を含み、この書込ログエントリ（ＷＬＥ）は、オブジェクト及びロックすることに関する他の情報を含む。例えば、ＷＬＥは、書込ロックが取得される前のオブジェクトについてのＴＭＷ値を含んでもよく、他の実施形態において、ＷＬＥは、オブジェクトの「シャドウ・コピー」を含んでもよく、その場合、オブジェクトへはコミット処理されない変形がなされる。他の状態において、書込ロックされたＴＭＷは、版数化された書込ロック（ＶＷＬ）を含む。ここで、ＴＭＷの残りのビット（ＶＷＬ（Ｖ／Ｃ）３２８と称される）は、Ｖ／Ｃペアと同様に、なお書込ロックされているオブジェクトの版数番号、及び悲観的な読込側の総数を表す。
【００２９】
如何にして版数化書込ロックが用いられるかに関する詳細な説明の前に、版数化書込ロック（複数のＶＷＬ）の必要性を例示するのを助ける例を説明する。インプレースＳＴＭシステムと、オブジェクトＯ１上に書込ロックを獲得するトップレベルのトランザクションＴｘ１とがあると仮定する。Ｏ１についてのＴＭＷがＷＬＥ１に設定され、ＷＬＥ１は、Ｏ１上のＴｘ１の書込ロックを表している、Ｔｘ１のログ内の書込ログエントリである。ここで、親トランザクションとしてのＴｘ１と共に、２つのＰＮＴ、すなわちＴｘ２及びＴｘ３が導入されると仮定する。Ｔｘ２及びＴｘ３は、並列入れ子において兄弟トランザクションであり、並行して実行される。Ｔｘ２及びＴｘ３は、Ｔｘ１よってロックされたデータにアクセスしてもよいが、それらは互いに隔離されなければならない。従って、Ｔｘ２及びＴｘ３が双方ともＯ１にアクセスしてもよい一方で、それらは並行してアクセスすることが許されてはならない。ここで、Ｏ１からの読込を望むＴｘ３を仮定する。Ｔｘ３は、Ｏ１のＴＭＷの値をＷＬＥ１として記録する楽観的な読込ログエントリをそのログ内に作成して、楽観的な読込処理を実行する。次に、Ｔｘ２がＯ１に書込を行うと仮定する。Ｔｘ２はＯ１上に書込ロックを獲得し、Ｔｘ２のログにおいて書込ログエントリであるＷＬＥ2にＯ１のＴＭＷを設定することになる。ＷＬＥ2は、ＷＬＥ１がＯ１のＴＭＷの以前の値であることを記録している。Ｔｘ２は、ここでＯ１のフィールドに書き込んでもよいし、インプレース書込によって書込みを行ってもよい。Ｔｘ３が実行を続けるにつれて、Ｔｘ２からコミット処理されていない書込を含むＯ１のフィールドをＴｘ３が読込む。Ｔｘ３は規定によってドゥーム処理され、ロールバック処理するべきことになる。しかし、Ｔｘ３がコミット処理を試みる前にもしＴｘ２が何らかの理由でロールバック処理する場合には、Ｔｘ２はＯ１上の書込ロックを解除しなければならない。これをするために、Ｔｘ２は通常Ｏ１のＴＭＷをＷＬＥ１へ戻す設定をすることになる。しかしここで、Ｔｘ３がコミット処理を試みる時、Ｔｘ３が最初にＯ１を読込んだ時にＴｘ３がした同一の値をＯ１のＴＭＷが含むことをＴｘ３が認識することになる。この状況において、Ｔｘ３は正しいと見えることになり、Ｔｘ２からコミット処理されていない書込を読込むことを認識するのにＴｘ３は失敗することになる。従って、Ｔｘ２がロールバック処理する時、Ｔｘ２はＯ１のＴＭＷをＷＬＥ１以外のある値に設定しなければならず、そして、Ｏ１はＴｘ１よってなおロックされていることを、本システムにおける他のトランザクション（兄弟ＰＮＴ又は他のトップレベルのトランザクション）が認識するのを保証する形で、Ｔｘ２はロールバック処理をしなければならない。これは次のように達成され、すなわち、Ｏ１のＴＭＷを版数化書込ロック（ＶＷＬ）に設定することと、Ｔｘ１がＯ１上に書込ロックを保持していることを示すエントリをグローバル版数化書込ロックマップ（ＶＷＬＭ）内に作ることとによって達成される。複数のＶＷＬ及びＶＷＬＭの詳細及び使用については以下に説明する。この実施形態は、ＶＷＬが必要である１つのケースを示している。しかし、Ｖ���Ｌが用いられ得る複数のシナリオが在ることが、ロック獲得及び解除のプロセスが本節の残りで詳細に説明されるにつれて、当業者によって認められるであろう。
【００３０】
図７は、版数化書込ロックを用いることによって並列入れ子状トランザクションの入れ子を保証し且つ適切に構成する複数のステージからなる一実施形態を示す。このプロセスは、始点３４０で始まり、版数番号／総数ペア、書込ログエントリ（ＷＬＥ）、又は版数化書込ロック（ＶＷＬ）のうちの１つであり得るトランザクショナルメモリワードを提供する（ステージ３４２）。トランザクショナルメモリワード（ＴＭＷ）が版数化書込ロックに変化する時、インデックスが付けられているグローバル版数化書込ロックマップ（ＶＷＬＭ）にエントリが作られ、当該エントリは、版数化書込ロックが置き換えた旧い書込ログエントリポインタを参照している（ステージ３４４）。版数化書込ロックが見出される時、グローバル版数化書込ロックマップが参照されて、版数化書込ロックを書込ログエントリポインタに変換し、通常の処理が書込ログエントリポインタに基づいて発生する（ステージ３４６）。トランザクショナルメモリワードにおける版数番号は、Ｖ／Ｃペア又は版数化書込ロックに保持されるか否かに関わらず、コミット処理又はアボート処理中に常に増分される（ステージ３４８）。版数化書込ロックがトランザクショナルメモリワードに置かれる直前に、エントリがグローバル版数化書込ロックマップに作られ、トランザクショナルメモリワードに版数化書込ロックを含む限り、当該エントリは残る（ステージ３５０）。どの時点においても、トランザクションは、グローバル版数化書込ロックマップにアクセスするのに、グローバルロックを獲得しなければならない（ステージ３５２）。このプロセスは終点３５４で終わる。
【００３１】
図８及び図９は、書込ロックを獲得している入れ子状トランザクションを適切に処置する複数のステージからなる一実施形態を示す。新たな書込ロックは、トランザクションの入れ子内で初めて獲得される書込ロックであり、複製書込ロックは、祖先トランザクションが現在書込みロックしたオブジェクト上に、入れ子状トランザクションが獲得しているかもしれない書込ロックである。このプロセスは、始点３７０で始まり、入れ子状トランザクションがトランザクショナルメモリワードを読み込む（ステージ３７２）。トランザクショナルメモリワードがＶ／Ｃペアではない場合（判定ポイント３７４）、このプロセスは図９に続き（ステージ４０４）、次節で説明される。トランザクショナルメモリワードが零より大きいＣ（悲観的な読込側の総数）を有するＶ／Ｃペアである場合（判定ポイント３７５）、図１６のプロセスが実行されて、悲観的な読込を処置して書込ロック格上げを行う。トランザクショナルメモリワードが零に等しいＣを有するＶ／Ｃペアである場合（判定ポイント３７５）、これは、トランザクショナルメモリワードが何らかのトランザクションよって読込又は書込が悲観的にはロックされていないことを示し、従って新たな書込ロックの獲得を可能としている。書込ロック獲得のためには、このシステムは、新たな書込ログエントリを形成して版数番号を記録し、書込ログエントリをトランザクションの書込ログに追加する（ステージ３７６）。比較処理及びスワップ処理が次いで実行され、トランザクショナルメモリワード値を、Ｖ／Ｃペアから書込ログエントリポインタ（例えばＷＬＥ*）に切り替える（ステージ３７８）。比較処理及びスワップ処理が成功した場合（判定ポイント３８０）、ロックは成功裏に取得される（ステージ３８２）。比較処理及びスワップ処理が成功しなかった場合（判定ポイント３８０）、衝突が存在し、ロックは成功裏には取得されない（ステージ３８４）。このプロセスは終点３８６で終わる。
【００３２】
図９を続けて参照して、ＴＭＷがＶ／Ｃペアでない場合（図８の判定ポイント３７４）且つトランザクショナルメモリワードが版数化書込ロックではない場合（判定ポイント４０４）、トランザクショナルメモリワードはＷＬＥAに対するポインタＷＬＥ*であり、このプロセスはステージ４０８に続く。トランザクショナルメモリワードが版数化書込ロックである場合（判定ポイント４０４）、グローバル版数化書込ロックマップが用いられてＷＬＥAに対して基礎をなすＷＬＥ*を読み出す（ステージ４０６）。ＷＬＥAがトランザクションの何らかの祖先トランザクションによって所有されていない場合（判定ポイント４０８）、衝突が存在し（ステージ４１０）、このプロセスは終点４２０で終わる。ＷＬＥAが祖先トランザクションによって所有されている場合（判定ポイント４０８）、新たなＷＬＥBが形成されＷＬＥAを記録し、ＷＬＥBがトランザクションの書込ログに追加される（ステージ４１２）。比較処理及びスワップ処理が次いで実行され、トランザクショナルメモリワード値をＷＬＥA*からＷＬＥB*に切り替える（ステージ４１４）。比較処理及びスワップ処理が成功した場合（判定ポイント４１６）、ロックは成功裏に取得される（ステージ４１８）。比較処理及びスワップ処理が成功しなかった場合（判定ポイント４１６）、衝突が存在し（ステージ４１０）、ロックは成功裏に取得されない。このプロセスは終点４２０で終わる。
【００３３】
図１０は、コミット処理のために何らかの種類の書込ロックを解除して入れ子状トランザクションを適切に処置する複数のステージからなる一実施形態を示す。このプロセスは、始点４４０で始まり、ＷＬＥXがコミット処理中にトランザクション書込ログにおいて遭遇される（ステージ４４２）。書込ロックの所有権及びＷＬＥXは、直近の親トランザクションに単純に移転される（ステージ４４４）。所有権を並列入れ子状トランザクションからコミット処理にある親トランザクションに移転することよって、他の兄弟トランザクションは、彼等自身のための書込ロックをこの時点で彼等が獲得できることを発見する。同様に、複製書込ロックを獲得する動作は、兄弟トランザクションが彼等自身のための書込ロックを獲得できるのを防止する。このプロセスは終点４４６で終わる。
【００３４】
図１１は、ロールバック処理のために新たな書込ロックを解除して入れ子状トランザクションを適切に処置する複数のステージからなる一実施形態を示す。このプロセスは、始点４６０で始まり、ＷＬＥXがロールバック処理中にトランザクションで書込ログにおいて遭遇される（ステージ４６２）。このシステムは、ＷＬＥXがどのタイプの書込ロックを表しているかをチェックする（ステージ４６４）。ＷＬＥXが新たな書込ロックを表していない場合（判定ポイント４６６）、図１２において一実施形態について説明されたように、複製書込ロックを解除する論理部が実行される（ステージ４７１）。ＷＬＥXが新たな書込ロックを表している場合（判定ポイント４６６）、ＷＬＥXで記憶されている以前の版数番号が読み出される（ステージ４６８）。トランザクショナルメモリワードのロケーションがＷＬＥXから読み出され、書込ロックが通常の記憶動作を用いて解除され、トランザクショナルメモリワード値をシステムのタイプ（インプレース又はバッファード）にとって適当なＶ／Ｃペアに変更する（ステージ４７０）。バッファードシステムの一実施形態では、トランザクショナルメモリワード値が元の版数番号を表す値に戻す変更がなされる。インプレースシステムの一実施形態では、トランザクショナルメモリワードの値は、元の版数番号＋１を表す値に変更される。このプロセスは終点４７２で終わる。
【００３５】
図１２は、ロールバック処理のために複製書込ロックを解除して入れ子状トランザクションを適切に処置する複数のステージからなる一実施形態を示す。一実施形態では、このプロセスは、ロールバック処理中にオブジェクトの版数番号を増分するシステム、すなわちインプレースシステムの用途にだけ用いられる。バッファードシステムの実施形態では、版数番号はロールバック処理中に増加されない。これらのシステムにおいて、新たな書込ロックを解除する（図１１）ためのプロセスは、複製書込ロックを解除するために用いられてもよい。このプロセスは、始点４９０で始まり、ＷＬＥXがロールバック処理中にトランザクション書込ログにおいて遭遇される（ステージ４９２）。システムは、どのタイプの書込ロックかをＷＬＥXが表すかチェックする（ステージ４９４）。ロックが複製書込ロックではない場合（判定ポイント４９６）、一実施形態について図１１で説明されたように、新たな書込ロックを解除する論理部が実行される（ステージ５１１）。ロックが複製書込ロックである場合、グローバル版数化書込ロックマップへのアクセスに同期するのに用いられるグローバルロックが獲得される（ステージ４９８）。元の書込ログエントリポインタＷＬＥY*とトランザクショナルメモリワードのロケーションとがＷＬＥXから読み出される（ステージ５００）。新たなグローバル版数化書込ロックマップエントリが、ＷＬＥYを参照して、オブジェクトのために形成される（ステージ５０２）。グローバル版数化書込ロックマップへのアクセスに同期するのに用いられるグローバルロックが次いで解除される（ステージ５０４）。元の版数番号かＷＬＥXから読み出され（ステージ５０６）、新しい版数化書込ロック値が元の版数番号＋１として形成される（ステージ５０８）。書込ロックは通常の記憶動作を用いて解除され、トランザクショナルメモリワード値をＷＬＥX*から新たな版数化書込ロックに変更される（ステージ５１０）。このプロセスは終点５１２で終わる。
【００３６】
図１３は、図１のシステムの一実施形態のための処理フローチャートであり、楽観的な読込ロック獲得の実行を示す。このプロセスは、始点５３０で始まり、トランザクションがオブジェクト上に楽観的な読込を実行する時、オブジェクトの現在のＴＭＷ値が読み込まれる（ステージ５３２）。楽観的な読込ログエントリが作成され（ステージ５３４）、現在のＴＭＷ値及びＴＭＷのロケーションによって占有させる（ステージ５３６）。読込ログエントリがトランザクションの読込ログに追加される（ステージ５３８）。一実施形態において、このプロセスは、トップレベルの、単純な入れ子状の、又は並列入れ子状のトランザクションの如きトランザクションの全てのタイプについて同一である。このプロセスは終点５４０で終わる。
【００３７】
図１４Ａ〜図１４Ｄは、図１のシステムの一実施形態のための処理フローチャートであり、楽観的な読込の検証の実行を示す。このプロセスは、始点５６０で始まり、トランザクションをコミット処理しようとするか或いはトランザクションが有効か否かを判定しようとする時、トランザクション読込ログにおける各楽観的な読込ログエントリを考慮する（ステージ５６２）。ＴＭＷの元の値は読込ログエントリから読み出され（ステージ５６４）、ＴＭＷの現在値が読み込まれる（ステージ５６６）。尚、各ケースにおいて、システムが書込アボート処理補償マップ（ＷＡＣＭ）を（図１９で説明されるように）用いている場合、現在の集積された（検証処理又はコミット処理中に形成される）ＷＡＣＭが、２つの版数番号に違いがあるにも関わらず、参照される。元のＴＭＷがＶ／Ｃペアである場合（判定ポイント５６８）、図１４Ｂで説明されるプロセスが実行される。元のＴＭＷがＷＬＥ*である場合（判定ポイント５７０）、図１４Ｃで説明されるプロセスが実行される。元のＴＭＷがＶ／ＣペアでもＷＬＥ*でもない場合、元のＴＭＷはＶＷＬであり（ステージ５７２）、図１４Dのプロセスが実行される。これらのシナリオの各々について更に詳細に説明する。
【００３８】
図１４Ｂは、元のＴＭＷがＶ／Ｃペアである時に（判定ポイント５６８）、一実施形態における楽観的な読込の検証中に実行される例示的なプロセスをより詳細に示す。現在のＴＭＷがＶ／Ｃペアであり（判定ポイント５９０）且つ元のＴＭＷと現在のＴＭＷとで版数番号が一致する場合（判定ポイント５９２）、トランザクションは有効である（ステージ５９４）。現在のＴＭＷがＶ／Ｃペアであり（判定ポイント５９０）且つ元のＴＭＷと現在のＴＭＷとで版数番号が一致しない場合（判定ポイント５９２）、トランザクションは無効である（ステージ５９６）。
【００３９】
現在のＴＭＷが代わりにＷＬＥ*であり（判定ポイント５９８）且つＷＬＥがトランザクションによって所有されていて且つＷＬＥにおいて記憶されている版数番号が旧いＴＭＷに一致する（判定ポイント６００）場合、トランザクションは有効である（ステージ５９４）。現在のＴＭＷがＶ／Ｃペアではなく（判定ポイント５９０）且つ現在のＴＭＷがＷＬＥ*ではない（判定ポイント５９８）場合、ＴＭＷはＶＷＬである（ステージ６０２）。同期化されたルックアップ処理が、ＶＷＬＭにおいてロックされたオブジェクトのアドレスを用いてなされる。ＶＷＬＭエントリが無い場合（判定ポイント６０４）、トランザクションは無効である（ステージ５９６）。エントリがある場合（判定ポイント６０４）、当該ＶＷＬＭエントリはＶＷＬが置き換えたＷＬＥ*を読み出すのに用いられる。ＷＬＥがトランザクションよって所有され且つＷＬＥに記憶された版数番号が旧いＴＭＷに一致する場合（判定ポイント６０６）、トランザクションは有効である（ステージ５９４）。それ以外の場合、トランザクションは無効である（ステージ５９６）。このプロセスは終点６０８で終わる。
【００４０】
図１４Ｃを参照すると、元のＴＭＷがＷＬＥ*である時に一実施形態において楽観的な読込確認中に実行される例示的なプロセスが示されている。現在のＴＭＷがＶ／Ｃペアである場合（判定ポイント６２０）、現在のトランザクションは有効ではない（ステージ６３０）。現在のＴＭＷがＶ／Ｃペアではなく（判定ポイント６２０）、その代わりにＷＬＥ*である場合（判定ポイント６２４）、システムは、元のＴＭＷと現在のＴＭＷとが一致することをチェックすると共に、ＷＬＥが現在のトランザクション又は何らかの祖先トランザクションによって所有されていることをチェックする（判定ポイント６２６）。これら判定基準が双方とも充足された場合、トランザクションは有効である（ステージ６２８）。それ以外の場合、トランザクションは無効である（ステージ６３０）。
【００４１】
現在のＴＭＷがＶ／Ｃペアではなく（判定ポイント６２０）且つＷＬＥ*ではない場合（判定ポイント６２４）、現在のＴＭＷはＶＷＬである（ステージ６３２）。元のＷＬＥからのＴＭＷが、このトランザクション又は何らかの祖先トランザクションによって所有されていて且つＷＬＥに記憶されている版数番号がＶＷＬにおける版数番号に一致する場合（判定ポイント６３４）、トランザクションは有効である（ステージ６２８）。それ以外の場合、トランザクションは有効ではない（ステージ６３０）。このプロセスは終点６３６で終わる。
【００４２】
図１４Ｄを参照すると、元のＴＭＷがＶＷＬである時に、一実施形態における楽観的な読込検証中に実行される例示的なプロセスが示されている。現在のＴＭＷがＶ／Ｃペアである場合（判定ポイント６５０）、トランザクションは衝突のために有効ではない（ステージ６６０）。現在のＴＭＷがＶ／Ｃペアではなくて（判定ポイント６５０）、その代わりにＷＬＥ*である場合（判定ポイント６５４）、システムは、ＷＬＥが現在のトランザクション又は何らかの祖先トランザクションによって所有されていることをチェックすると共にＷＬＥに記憶されている版数番号がＶＷＬにおける版数番号に一致していることをチェックする（判定ポイント６５６）。これらの判定基準が双方とも充足される場合、トランザクションは有効である（ステージ６５８）。それ以外の場合、トランザクションは有効ではない（ステージ６６０）。
【００４３】
現在のＴＭＷがＶ／Ｃペアではなく（判定ポイント６５０）且つ現在のＴＭＷがＷＬＥ*ではない場合（判定ポイント６５４）、現在のＴＭＷはＶＷＬである（ステージ６６２）。ＶＷＬＭにおいてルックアップ処理が実行されてＶＷＬをＷＬＥ*に変換する（ステージ６６４）。エントリが発見されない場合（判定ポイント６６６）、トランザクションは有効ではない（ステージ６６０）。それ以外の場合で、エントリが発見された場合（判定ポイント６６６）、システムは、元のＶＷＬと現在のＶＷＬとで版数番号が一致することをチェックすると共に、ＴＭＷについてＶＷＬＭで発見されたＷＬＥが、このトランザクション又は何らかの祖先トランザクションによって所有されていることをチェックする（判定ポイント６６８）。双方の判定基準が充足された場合、トランザクションは有効である（ステージ６５８）。それ以外の場合、トランザクションは無効である（ステージ６６０）。このプロセスは終点６７０で終わる。
【００４４】
単純な閉じた入れ子状トランザクションによる、システムにおける悲観的な読込の正しい動作は、悲観的読込オブジェクトテーブル（ＰＲＯＴ）と称される複製検知データ構造の使用を要求する。各トップレベルのトランザクションは、トランザクション開始時又は遅延して最初の悲観的な読込動作時点の何れかでＰＲＯＴを作成する。トランザクション又は何らかの子孫トランザクションがオブジェクト上に悲観的な読込ロックを獲得しようとする時、トランザクションは、ＰＲＯＴを参照して、悲観的な読込ロックが既に獲得されているか否かを判定する。オブジェクトがＰＲＯＴにある場合、オブジェクトはトランザクションの入れ子によって既に読込ロックされている。オブジェクトがＰＲＯＴに無く且つオブジェクトが他のトランザクションによって現在書込ロックされていない場合、悲観的な読込ロックがＣＡＳ処理を用いて獲得されてオブジェクトのＴＭＷに記憶されているＶ／ＣペアにおけるＣ（悲観的な読込側の総数）を増分する。ＣＡＳ処理が成功した場合、エントリがＰＲＯＴにおいて作られ、悲観的な読込のためにロックされたオブジェクトを入れ子が現在有している事実を記録する。悲観的な読込ロックが解除される時、トップレベルのコミット処理中又はロールバック処理中の何れかでＣが（再びＣＡＳによって）減分され、ＰＲＯＴエントリが除去される。次に、如何にして複数のＰＲＯＴが並列入れ子状トランザクションによって用いられるかを説明する。
【００４５】
図１５は、悲観的な読込の正しい動作を並列入れ子状トランザクションによって保証する複数のステージからなる一実施形態を示す。このプロセスは、始点６９０で始まり、並列入れ子状トランザクションは、初期化中又は遅延して並列入れ子状トランザクションによる第１の悲観的な読込ロックの獲得中に、悲観的な複製検知データ構造（先の説明のようにＰＲＯＴと称される）を作成する（ステージ６９２）。このデータ構造は、トランザクションが悲観的な読込ロックを書込ロックに格上げしようとする時にシステムよって用いられる。並列入れ子状トランザクション又は何らかの連続した子トランザクションによって作られたオブジェクトの第１の悲観的な読込のためのエントリがＰＲＯＴ中に作られる（ステージ６９４）。コミット処理に基づいて、新たな悲観的な読込ロックが直近の親トランザクションに渡され、適切な親ＰＲＯＴエントリが作られる（ステージ６９６）。複製読込ロックが解除され、並列子トランザクションがコミット処理した後に兄弟トランザクションが書込アクセスを取得するのを可能とする（ステージ６９８）。システムは、次いで、複製の悲観的な読込ロックに関連付けられたログエントリを破壊する（ステージ７００）。コミット処理の後、子トランザクションのＰＲＯＴは、トランザクションの残りによって破壊され得る（ステージ７０２）。このプロセスは終点７０４で終わる。
【００４６】
図１６は、悲観的な読込ロックを書込ロックに格上げする複数のステージからなる一実施形態を示す。このプロセスは、始点７２０で始まり、あるオブジェクトにとって望ましい書込ロックが既に悲観的な読込のために開かれていることを発見する（ステージ７２２）。子トランザクションのＰＲＯＴがクエリ処理され（ステージ７２４）、読込側の現在の総数を見て、現在のトランザクションがそれらの全ての読込を総数処理できるか否かを判定する（ステージ７２６）。その結果が悲観的な読込側の全てを総数処理できる場合、子トランザクションは、書込ロックへの格上げを通常のように試みてもよい（ステージ７２８）。総数処理できない読込側がなおある場合、子トランザクションは、全ての祖先トランザクションの複数のＰＲＯＴをクエリ処理して、子トランザクションが書込ロックに格上げしてもよいか否かを判定する（ステージ７３０）。祖先トランザクションが並列親トランザクションである場合、既にコミット処理を行った何らかの並列兄弟トランザクションのＰＲＯＴと同様に、並列親トランザクションのＰＲＯＴを考慮しなければならない。これら兄弟トランザクションのＰＲＯＴは、並列親トランザクションのログに複数のＰＮＴＥを介して保持されている。適切な同期処理が、これら兄弟トランザクションのＰＲＯＴへの競争の無い（race-free）アクセスを保証するのに要求される。この同期処理は、ＰＮＴがそのＰＲＯＴに、関連付けられたＰＮＴＥ内にＰＲＯＴを置いた後には、アクセスしないことを保証することよって達成される。祖先トランザクション及び何らかのコミット処理された並列兄弟トランザクションが、余分の悲観的な読込側を埋め合わせる場合、子トランザクションは、書込ロックに格上げしようと通常のように試みてもよい（ステージ７３２）。一実施形態において、格上げは次のように達成される。新たな書込ログエントリが形成されてＰＮＴのログに追加される。ＴＭＷの現在値は、ロールバック処理及びコミット処理中の使用のためにＷＬＥに置かれる。ＴＭＷの現在値がＶＷＬである場合、ＶＷＬＭが用いられて適切な同期化によって当該ＶＷＬを最初にＷＬＥ*に変換する。ＣＡＳ処理が用いられて書込ロックを獲得する。ＣＡＳ処理が成功した場合、格上げが働き、そうではない場合には衝突がある。このプロセスは終点７３４で終わる。
【００４７】
ここで、並列入れ子状トランザクションにおける悲観的な読込ロック獲得を実行する、図１７Ａ〜図１７Ｄに示される例示的なプロセスを説明する。プロセスは、図１７Ａで始まり、現在のＴＭＷを読み込む（ステージ７５２）。ＴＭＷがＶ／Ｃペアである場合（判定ポイント７５４）、図１７Ｂで説明されるプロセスが実行される。ＴＭＷがＷＬＥ*である場合（判定ポイント７５６）、図１７Ｃで説明されるプロセスが実行される。ＴＭＷがＶ／Ｃペアではなく（判定ポイント７５４）且つＷＬＥ*ではない場合（判定ポイント７５６）、ＴＭＷはＶＷＬであり（ステージ７５８）、図１７Ｄで説明されるプロセスが実行される。これらシナリオの各々を、以下に更に詳細に説明する。
【００４８】
図１７Ｂを参照すると、ＴＭＷがＶ／Ｃペアである場合、トランザクションのＰＲＯＴが参照されて、ＰＲＯＴがオブジェクト上の悲観的な読込ロックを既に保持しているか否かを判定する（判定ポイント７６９）。ＰＲＯＴエントリがある場合、プロセスは終点７７６で終わる。ＰＲＯＴエントリが無い場合（判定ポイント７６９）、比較処理及びスワップ処理（ＣＡＳ）が用いられて、悲観的な読込側の総数であるＣを増分する（ステージ７７０）。ＣＡＳが成功した場合（判定ポイント７７２）、ロックが獲得され、ＰＲＯＴエントリが作られる（ステージ７７４）。ＣＡＳ処理が失敗した場合（判定ポイント７７２）、図１７Ａに示されるステージ７５２の処理が再度なされる。
【００４９】
図１７Ｃに示されるように、ＴＭＷがＷＬＥ*であり且つＷＬＥが現在のトランザクション又は何らかの祖先トランザクションによって所有されている場合（判定ポイント７９０）、システムは、所有しているトランザクションが並列親トランザクションより下にあるか又はより上にあるかを判定する（判定ポイント７９２）。所有しているトランザクションが並列親トランザクションより下にある場合（判定ポイント７９２）、悲観的な読込を続行する（ステージ７９４）。所有しているトランザクションが並列親トランザクションより上にある場合（判定ポイント７９２）、システムは、ＴＭＷをＶＷＬに切り替えて兄弟トランザクションと連携する。そうするために、ＶＷＬＭエントリが作られてＷＬＥ*を適当な同期化によって記録し（ステージ７９６）、ＶＷＬが当該ＶＷＬに記憶された版数番号から形成され、Ｃ（悲観的な読込側の総数）が１に設定される。新たなＶＷＬは、ＴＭＷにＣＡＳ処理によって設定される（ステージ８００）。ＣＡＳ処理が成功した場合、ＰＲＯＴエントリが作られ、悲観的な読込ロックが獲得される（ステージ８０６）。ＣＡＳ処理が成功しなかった場合、ＶＷＬＭエントリは除去され（ステージ８０４）、次いで、図１７Ａに戻ることよってステージ７５２の処理を再度行う。このプロセスは終点８１０で終わる。
【００５０】
図１７Dに示されるように、ＴＭＷがＶＷＬである場合、ＶＷＬは、ＷＬＥ*にＶＷＬＭを介して適切な同期化処理によって変換される（ステージ８２０）。ＷＬＥがこのトランザクション又は何らかの祖先トランザクションよって所有されている場合（判定ポイント８２２）、ＣＡＳ処理が用いられてＴＭＷにおけるＶＷＬにおけるＣ（悲観的な読込側の総数）を増分する（ステージ８２４）。ＣＡＳ処理が成功した場合（判定ポイント８２６）、ＰＲＯＴエントリが作られ、ロックが獲得される。ＣＡＳが失敗した場合、図１７Aのステージ７５２の処理を再度行う。ＷＬＥがこのトランザクション又は何らかの祖先トランザクションによって所有されていない場合（判定ポイント８２２）、衝突が在る（ステージ８３０）。このプロセスは終点８３２で終わる。
【００５１】
図１８は、再試行が並列入れ子状トランザクションと正しく働く複数のステージからなる一実施形態を示す。図１８の詳細に立ち入って再試行が並列入れ子状トランザクションと正しく働くのを可能とする説明をする前に、先ず一実施形態の再試行動作に関する背景情報を提供する。再試行動作はトランザクション間の基本的通信を可能とする。トランザクションが再試行動作を実行する時、その作用はロールバック処理され、トランザクションの読込が変化する所迄、実行が停止される。変化が検出された時、トランザクションは再実行される。再試行動作は、キュー遮断のような非常に一般的なあるデータ構造について用いられ得る。例えば、トランザクションは、キューが空であるか否かについてチェックし、キューが空である場合には再試行を行い、列が空ではない場合にはエレメントを除去することができる。トランザクションはキューが不変のままである間は遮断し、キューの状態が変化する時には再実行を行うことになり、かかる態様はトランザクションが完了する別の機会を与える。
【００５２】
一実施形態において、トランザクションが再試行動作を実行する時、システムは、再実行を行うトランザクションの読込セットにおける全ての読込を待つ登録を行う。再試行するトランザクションは、読込セットにおける何らかが変化したことの通知を待つ。待ち通知は、書込ロックを解除している特定のトランザクションから始動される。トランザクションは、２つの方法のうちの１つで通知が必要か否かを知る。第１の方法において、書込ロック獲得中にトランザクショナルメモリワードが待ち側（waiter）ビットを含んでいた場合、解除中にトランザクショナルメモリワードがオブジェクト待ち側マップで調べられ、各待っているトランザクションに知らされる。第２の方法において、書込をするトランザクションは、全ての書込ロックを解除した後に、待っているトランザクションのグローバル総数が零より大きいと判る場合、書込をするトランザクションは、トランザクション待ち側マップを用いて、どのトランザクションが、少なくとも書き込まれるロケーションを待っていて知らされる必要があるかを判定する。各方法において、書込ロックは通常の記憶動作を用いて解除される。
【００５３】
他の実施形態において、漸進的な再試行動作は、まさに入れ子状トランザクションのロールバック処理及びその読込セットを待つことによって開始される。ある特定の時間又は遭遇されるある他の条件を待った後に、バックオフプロセスが実行されて、元の待ちセットのサイズを大きくして、再試行を行うトランザクションの直近の親トランザクションをロールバック処理する。バックオフプロセスは、各次の親トランザクション毎に追加的な待ちを追加して、最もトップレベルの親トランザクションのロールバック処理迄反復される。漸進的な待ちセットは、最もトップレベルの親トランザクションに関連付けられ、何らかの通知が最もトップレベルの親トランザクションの再実行をもたらす。
【００５４】
図１８に戻り、如何にして再試行が並列入れ子状トランザクションによって用いられ得るかをここで説明する。このプロセスは、始点８５０で始まり、並列入れ子状トランザクション又は何らかの連続した子孫トランザクションの再試行が実行される時、システムは、再試行のトランザクションの読込セットを通常のように登録する（ステージ８５２）。システムは、再試行を行うトランザクションの祖先トランザクションからなるあるサブセットを含むように当該再実行を拡張する前に、当該再試行を行うトランザクションがどの位長く待つべきかを決定する発見的方法（heuristics）を含む（ステージ８５４）。この方法は、並列入れ子状トランザクションについて調整され、他の並列兄弟トランザクションがアクティブである限り延長された待ち時間を可能とする。延長待ち時間を超えた場合、当該再試行動作が親トランザクションを含むように拡張される（ステージ８５６）。兄弟トランザクションの状態が更なる伝播の前に考慮される（ステージ８５８）。再試行が並列入れ子状トランザクションの親を越えて伝播するような決定がなされた時、全ての子トランザクションはドゥーム（doom）処理され、次いで、再試行する親トランザクションがロールバック処理される前に、子トランザクションは終了しなければならない（ステージ８６０）。再試行が親トランザクションを越えて伝播するような決定がなされた時、並列入れ子状トランザクションの読込セットは登録されたままであり、親トランザクションの読込セットの一部となる（ステージ８６２）。尚、親トランザクション中に既にコミット処理された何らかの並列兄弟トランザクションの読込セットは、親トランザクションの読込セットと一緒に待ちセットの一部をなす。当該決定よってアボート処理されて当該再試行を親トランザクションに迄伝播された何らかの並列兄弟トランザクションは待ちセットに寄与しない。このプロセスは終点８６４で終わる。
【００５５】
図１９は、並列入れ子状トランザクションによって書込アボート処理補償マップを用いる複数のステージからなる一実施形態を示す。図１９の詳細並びに如何にして書込アボート処理補償マップが並列入れ子状トランザクションによって用いられ得るかについて詳細に説明する前に、一実施形態の書込アボート処理補償マップに関する背景情報を提供する。
【００５６】
書込アボート処理補償マップが用いられて、インプレース書込を用いるトランザクショナルメモリシステムにおいて入れ子状子トランザクションの誤ってドゥーム処理された親トランザクションを検出する。書込アボート処理補償マップ（又は他の記憶メカニズム）は、ロールバック処理する各入れ子状トランザクション毎に解除された各ロック毎に解除総数を追跡する。入れ子状トランザクションの各々が書込ロックを解除する回数は、それら各々の書込アボート処理補償マップに各々記録される。解除総数が、親トランザクションの検証中に用いられ、明白に無効な楽観的な読込が本当は有効であるか否かを判定することができる。
【００５７】
一実施形態において、親トランザクションログを処理する間、入れ子状子トランザクションについて見られる何らかの書込アボート処理補償マップは、親トランザクションにおいて集積された書込アボート処理補償マップ中に結合される。楽観的な読込が版数番号不一致に起因して検証に失敗した場合、当該集積された書込アボート処理補償マップが参照され、入れ子状子トランザクションについて特定変数の書込ロック解除総数を読み出す。版数番号における差が、入れ子状子トランザクションについての書込ロック解除総数に実際には一致する場合、楽観的な読込は有効である。
【００５８】
図１９に戻り、如何にして書込アボート処理補償マップが並列入れ子状トランザクションによって用いられるかについて説明する。このプロセスは、始点８８０で始まり、並列入れ子状トランザクションのロールバック処理中に新たな書込ロックを解除する時、書込アボート処理補償マップ（ＷＡＣＭ）を作成する（ステージ８８２）。入れ子状トランザクションがロールバック処理する時、入れ子状トランザクションは、解除される新たな各書込ロック毎にＷＡＣＭエントリを作成する（ステージ８８４）。ログの所有権が親トランザクションにコミット処理中に移転される時、並列入れ子状トランザクションのログの前にＷＡＣＭが論理的に置かれる（ステージ８８６）。これらＰＮＴの複数のＷＡＣＭは、親トランザクションのロールバック処理中に、まるで何れかの他の入れ子状トランザクションのＷＡＣＭのように上記の如く用いられることになり、親トランザクションの楽観的な読込の正しい検証を保証することになる（ステージ８８８）。このプロセスは終点８９０で終わる。
【００５９】
本発明の内容を、構造上の態様及び／又は方法上の動作に特有の言語で説明したが、添付の特許請求の範囲で画定される本発明の内容は必ずしも上記した特定の態様又は動作に限定されるものではないことが理解されよう。むしろ、上記に説明された特定の態様及び動作は、請求項の内容を実施する形態例として開示されている。本明細書及び／又は請求項によって説明された如き実施形態の思想に含まれる全ての均等物、変更及び改変が保護されるべきである。
【００６０】
例えば、コンピュータソフトウェア分野における当業者は、本明細書で説明した実施形態が、１つ以上のコンピュータ上で異なって組織されることができ、例として示されたものより少ないか又は別の選択肢又は態様を含むことがきることを認識するであろう。
【図１】
2010539609.tif 000003
【図２】
2010539609.tif 000004
【図３】
2010539609.tif 000005
【図４】
2010539609.tif 000006
【図５】
2010539609.tif 000007
【図６】
2010539609.tif 000008
【図７】
2010539609.tif 000009
【図８】
2010539609.tif 000010
【図９】
2010539609.tif 000011
【図１０】
2010539609.tif 000012
【図１１】
2010539609.tif 000013
【図１２】
2010539609.tif 000014
【図１３】
2010539609.tif 000015
【図１４Ａ】
2010539609.tif 000016
【図１４Ｂ】
2010539609.tif 000017
【図１４Ｃ】
2010539609.tif 000018
【図１４Ｄ】
2010539609.tif 000019
【図１５】
2010539609.tif 000020
【図１６】
2010539609.tif 000021
【図１７Ａ】
2010539609.tif 000022
【図１７Ｂ】
2010539609.tif 000023
【図１７Ｃ】
2010539609.tif 000024
【図１７Ｄ】
2010539609.tif 000025
【図１８】
2010539609.tif 000026
【図１９】
2010539609.tif 000027
【国際調査報告】
2010539609.tif 000028
2010539609.tif 000029