(57)【要約】  トランザクショナルメモリシステムにおいて入れ子の子の不正に失敗させられる親トランザクションを検出するために様々な技術および技法を開示する。入れ子トランザクションがロールバックするとき、所与の入れ子トランザクションのロールバックのために書き込みロックが解放される毎にリリースカウントを追跡する。例えば、書き込み停止補償マップを使用して、各入れ子トランザクションに対するリリースカウントを追跡する。入れ子トランザクションが書き込みロックを解放する回数を、その個々の書き込み停止補償マップに記録する。親トランザクションの検証中に、リリースカウントを使用して、失敗した楽観的読み取りが実際には有効であるかどうかを判断する。入れ子トランザクションの集約リリースカウントがバージョン番号の差と正確に相当する場合、楽観的読み取りは有効となる。
2010532052.tif 000002
【特許請求の範囲】
【請求項１】
トランザクショナルメモリシステムにおいて入れ子の子の親トランザクションを不正に失敗させることを回避するための方法であって、
入れ子トランザクションがロールバックするとき、書き込みロックが解放される毎にリリースカウントを追跡するステップ（２０６）と、
親トランザクションの検証中に、前記リリースカウントを使用して、検証を失敗した楽観的読み取りが実際には有効であるかどうかを決定するステップ（２１６）と
を含むことを特徴とする方法。
【請求項２】
バージョン番号の差が前記リリースカウントに正確に一致している場合、失敗した前記検証は、実際には有効であることを特徴とする請求項１に記載の方法。
【請求項３】
前記リリースカウントは、書き込み停止補償マップ内で追跡される（２７４）ことを特徴とする請求項１に記載の方法。
【請求項４】
前記書き込み停止補償マップ、入れ子トランザクションの各々に対して作成される（２７２）ことを特徴とする請求項３に記載の方法。
【請求項５】
前記書き込み停止補償マップは、入れ子トランザクションの各入れ子トランザクションに対して、該各入れ子トランザクションが最初にロールバックして書き込みロックを解放するときに作成される（２７２）ことを特徴とする請求項４に記載の方法。
【請求項６】
前記入れ子トランザクションの各々に対する前記書き込み停止補償マップは、集約書き込み停止補償マップに集約される（３１２）ことを特徴とする請求項４に記載の方法。
【請求項７】
前記集約書き込み停止補償マップは、前記親トランザクションのトランザクションログを処理する間に、失敗した前記楽観的読み取りが実際には有効であるかどうかを判断するために使用される（３１２）ことを特徴とする請求項６に記載の方法。
【請求項８】
前記親の前記トランザクションログは、逆の順序で処理される（３１２）ことを特徴とする請求項７に記載の方法。
【請求項９】
請求項１に記載の各ステップをコンピュータに実行させるためのコンピュータ実行可能な命令を記録したコンピュータ読み取り可能な媒体（２００）。
【請求項１０】
入れ子トランザクションの書き込み停止補償マップを作成するステップ（２０６）と、
前記入れ子トランザクションが書き込みロックを解放する回数を、前記書き込み停止補償マップに記録するステップ（２０８）と、
親トランザクションの検証中に、前記書き込み停止補償マップを使用して、失敗した楽観的読み取りが実際には有効であるかどうかを判断するステップ（２１６）と
を含むステップをコンピュータに実行させるためのコンピュータ実行可能な命令を記録したことを特徴とするコンピュータ読み取り可能な媒体。
【請求項１１】
前記書き込み停止補償マップは、前記入れ子トランザクションが最初にロールバックして書き込みロックを解放するときに作成される（２７２）ことを特徴とする請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１２】
前記失敗した楽観的読み取りは、バージョン番号の差が前記入れ子トランザクションが前記書き込みロックを解放した回数に一致する場合、実際には有効であることを特徴とする請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１３】
前記書き込み停止補償マップは、前記親トランザクションのトランザクションログに保持される（２７６）ことを特徴とする請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１４】
前記書き込み停止補償マップは、前記親トランザクションによって行われた全ての楽観的読み取りの後に、前記入れ子トランザクションの開始時に順序付けされることを特徴とする請求項１３に記載のコンピュータ読み取り可能な媒体。
【請求項１５】
前記書き込み停止補償マップは、親トランザクションのロールバック中に、他の入れ子の子について作成された他の書き込み停止補償マップとともに集約されて、集約された書き込み停止補償マップを形成する（２９４）ことを特徴とする請求項１０に記載のコンピュータ読み取り可能な媒体。
【請求項１６】
前記集約された書き込み停止補償マップは、前記親トランザクションのトランザクションログ内に配置される（２９４）ことを特徴とする請求項１５に記載のコンピュータ読み取り可能な媒体。
【請求項１７】
前記集約された書き込み停止補償マップは、前記親トランザクションの前記トランザクションログを逆の順序で処理するときに（３１２）前記親トランザクションの前記トランザクションログ内に配置されることを特徴とする請求項１６に記載のコンピュータ読み取り可能な媒体。
【請求項１８】
トランザクションの検証において書き込み停止補償マップを使用して入れ子トランザクションの親を不正に失敗させることを回避するための方法であって、
親のログの処理中に、入れ子の子トランザクション内で見つかった全ての書き込み停止補償マップを、集約された書き込み停止補償マップに集約するステップ（３１２）と、
楽観的読み取りがバージョン番号の不一致のために有効でないとき、前記集約された書き込み停止補償マップを参照して、前記入れ子の子トランザクションの書き込みロックリリースカウントを取り出すステップ（３１６）と、
バージョン番号の差が前記入れ子の子トランザクションの前記書き込みロックリリースカウントに一致するとき、前記楽観的読み取りは有効であるとするステップ（３２２）と
を含むことを特徴とする方法。
【請求項１９】
前記バージョン番号の差が前記入れ子の子トランザクションの前記書き込みロックリリースカウントに一致しないとき、前記楽観的読み取りは無効であるとする（３２４）ことを特徴とする請求項１８に記載の方法。
【請求項２０】
請求項１８に記載の各ステップをコンピュータに実行させるためのコンピュータ実行可能な命令を記録したことを特徴とするコンピュータ読み取り可能な媒体（２００）。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、入れ子トランザクションの親を不正に失敗させることを対処することに関する。
【背景技術】
【０００２】
ソフトウェアトランザクショナルメモリ（ＳＴＭ：Software transactional memory）は、並行処理コンピューティングにおいて共有メモリへのアクセスを制御するためのデータベーストランザクションに対する並行処理制御機構に類似している。トランザクショナルメモリのコンテキストにおいて、トランザクションとは、共有メモリに対する一連の読み取りおよび書き込みを実行するコードの一部である。ＳＴＭは、トランザクショナルロック機構（transactional locking mechanism）の代替として使用される。ＳＴＭは、並列プログラムをより簡単に書くことを可能にする。トランザクションは、あらかも分離して（isolation）実行していたかのように実行すべきコードのシーケンスを指定する。分離しているというこの錯覚は、オブジェクトを細粒度でロックすることによって、およびトランザクションが他の何らかのトランザクションと競合していることわかったときは該トランザクションをロールバックするという副作用を可能にするモードで実行することによって達成される。データアクセスのために生成されたコードが、これらのロック機構およびロールバック機構へのサポートを含むように変更された場合、該データアクセスが「トランザクト（transact）された」という。
【０００３】
多くのＳＴＭシステムは、入れ子トランザクション（nested transaction）をサポートするため、トランザクションを使用して作成された異なるコンポーネントの効率的な構成を可能にする。入れ子トランザクションは、その結果（effect）が、該入れ子トランザクションが含まれているトランザクション、すなわち親トランザクションのような同じ分離境界（isolation boundary）の一部である場合、クローズであると見なされる。クローズされた入れ子トランザクションがコミットすると、その結果はシステムの他の部分に対して可視とはならない。代わりに、その結果は、まだ進行中の親トランザクションの一部となり、親トランザクションが最終的にコミットしたときにのみシステムの他の部分に対して可視となる。入れ子トランザクションがロールバックすると、その一時的な結果は取り消され、親トランザクションの状態が、該入れ子トランザクションが開始したポイントにリストアされる。
【発明の概要】
【発明が解決しようとする課題】
【０００４】
インプレース（in-place）書き込みおよび楽観的（optimistic）読み取りを使用するＳＴＭシステムは、メモリのロック可能領域の各々に関連付けられたバージョン番号を使用して、共有データに対していつ変更が行われたかを示す。読み取りトランザクションは楽観的に、メモリのバージョン番号（オブジェクト、キャッシュラインなど）を記録するが、他方、データはロックしない。このトランザクションは、該トランザクションの期間（life）にわたってバージョン番号が変化していないときにコミットすることができる。書き込みトランザクションは、コミットまたはロールバックのいずれかのために、その書き込みロックを解放するときにバージョン番号をインクリメントする。書き込みトランザクションがデータをインプレースで一時的に更新したので、バージョン番号は、ロールバック中にクリメントされなければならない。これらの更新は、読み取りトランザクションに対して可視であり、該読み取りトランザクションに、不整合データを読み取る可能性があるためコミットすることができないことを通知しなければならない。
【０００５】
親によってまだ書き込まれていないデータを書き込む入れ子トランザクションは、ロールバックの際に、非入れ子（トップレベル）のトランザクションと同じようにバーション番号をインクリメントしなければならない。しかしながら、初めて、親トランザクションが楽観的に変数Ｘを読み取り、入れ子の子トランザクションが変数Ｘに対して書き込む場合を検討されたい。親は、そのログにＸのバーション番号、例えば、バージョンＶ１を記録するであろう。子トランザクションは、Ｘに対する書き込みロックを開始して該書き込みロックを獲得するであろう。次いで、子トランザクションがコミットする場合は問題ない。すなわち、書き込みロックが解放されて親に渡され、そして該親は、矛盾を生じさせないままコミットすることができる。しかしながら、上記入れ子トランザクションが何らかの理由でロールバックする場合、該入れ子トランザクションは、書き込みロックを解放して、Ｘのバージョン番号をＶ２にインクリメントしなければならない。親は、コミット時に矛盾を生じるように見えるであろう。ＸのバージョンはＶ２であるが、実際には、親は、Ｖ１のＸを読み取り、どれがバージョン番号をＶ２に変更したかについての記録を有さない。親が別のトランザクションと競合しているように見えるが、実際は、バージョン番号の増加を引き起こした入れ子の子トランザクションあるので、これは実際には競合ではない。親は、その子のロールバック操作によって失敗させられたのである。この問題は、ＳＴＭシステムにおける親トランザクションの疑似再実行（spurious re-executions）を引き起こす。
【課題を解決するための手段】
【０００６】
トランザクショナルメモリシステムにおいて、入れ子の子トランザクションによって不正に失敗させられる親トランザクションを検出するための様々な技術および技法を開示する。入れ子トランザクションをロールバックすると、所与の入れ子トランザクションに対する書き込みロックが解放される毎にリリースカウントが追跡される。例えば、書き込み補償停止マップを使用して、ロールバックする各入れ子トランザクションに対して解放される各ロックについて、リリースカウントを追跡する。入れ子トランザクションが書き込みロックを解放する回数を、その各々の書き込み停止補償マップに記録する。該リリースカウントを親トランザクションの検証（validation）中に使用して、一見して無効な（invalid）楽観的読み取りが実際に有効（valid）であるかどうかを判断することができる。
【０００７】
一実装では、親トランザクションの処理中に、入れ子の子トランザクションについて見つかった全ての書き込み停止補償マップを、親の集約書き込み停止補償マップに集約する。バージョン番号の不一致のために楽観的読み取りが有効とされない場合、次いで、集約書き込み停止補償マップを参照して、入れ子の子トランザクションに対する特定の変数（variable）の書き込みロックリリースカウントを取り出す。バージョン番号の差が、上記入れ子の子トランザクションの書き込みロックリリースカウントと正確に一致する場合、上記楽観的読み取りは有効である。
【０００８】
この課題を解決するための手段は、下記の発明を実施するための形態でさらに説明される概念の選択を簡略化した形で紹介するために提供されたものである。この課題を解決するための手段は、特許請求される主題の重要な機能または主要な機能を特定するようには意図されておらず、特許請求される主題の範囲を決定する際の助けとして使用されるようにも意図されていない。
【図面の簡単な説明】
【０００９】
【図１】一実装にかかるコンピュータシステムの概略図である。
【図２】図１のコンピュータシステムにおいて動作する、一実装にかかるトランザクショナルメモリアプリケーションの概略図である。
【図３】図１のシステムの一実装にかかる高レベルの処理フローを示す図である。
【図４】図１のシステムの一実装にかかる、書き込み停止補償マップを作成し、維持することに関する段階を示す処理フロー図である。
【図５】図１のシステムの一実装にかかる、トランザクションのロールバック中に書き込み停止補償マップを集約することに関する段階を示す処理フロー図である。
【図６】図１のシステムの一実装にかかる、トランザクションの検証中に、書き込み停止補償マップを使用して、入れ子トランザクションの親を不正に失敗させることを回避することに関する段階を示す処理フロー図である。
【発明を実施するための形態】
【００１０】
本明細書の技術および技法を、一般的なコンテキストでトランザクショナルメモリシステムとして説明するが、本システムは、これらに加えて他の目的も果たす。一実装では、本明細書で説明される技法の１つまたは複数を、ＭＩＣＲＯＳＯＦＴ（登録商標）．ＮＥＴ  Ｆｒａｍｅｗｏｒｋなどのフレームワークプログラム内の機能として、あるいは開発者にソフトウェアアプリケーションを開発するためのプラットフォームを提供する任意の他のタイプのプログラムまたはサービスからの機能として実装することができる。別の実装では、本明細書で説明される技法の１つまたは複数を、並列処理環境において実行するアプリケーションの開発を扱う他のアプリケーションを有する機能として実装することができる。
【００１１】
一実装では、入れ子の子トランザクションの親トランザクションを不正に失敗させることを検出し、回避することを可能にするトランザクショナルメモリシステムを提供する。本明細書で使用されるとき、「失敗させられる（doomed）」という用語は、他のトランザクションによって後から書き込まれた１つまたは複数の変数に対して、１または複数の楽観的読み取りを実行したために、後にロールバックされることとなるトランザクションを含むことが意図されている。このようなトランザクションがコミットしようとすると、失敗した楽観的読み取り（failed optimistic read）によって、当該トランザクションはロールバックして再実行することとなる。本明細書で使用されるとき「不正に失敗させられる（falsely doomed）」という用語は、失敗した楽観的読み取りが原因で失敗させられるように見えるが、当該楽観的読み取りが入れ子トランザクションによって実行された動作によるものであって実際には有効であったために、実際には失敗させられていない任意のトランザクションを含むように意図されている。本明細書で使用されるとき「入れ子トランザクション（nested transaction）」という用語は、そのトランザクションの結果が別のトランザクションの分離境界内に含まれるトランザクションを含むように意図されている。入れ子トランザクションを含んでいるトランザクションを、当該入れ子トランザクションの「親（parent）」と呼び、当該入れ子トランザクションを、典型的には「子（child）」と呼ぶ。各入れ子の子が書き込みロックを解放する回数は、ロック毎のリリースカウント（per-lock release count）で追跡される。一実装では、これらのカウントは、書き込み停止補償マップで追跡される。本明細書で使用されるとき「書き込み停止補償マップ（write abort compensation map）」という用語は、入れ子の子がロックを解放するたびに、ロック毎のリリースカウントを記憶するデータ構造を含むように意図されている。複数の書き込み停止補償マップを、トランザクションの検証中またはロールバック中に、集約マップに集約することができる。
【００１２】
親トランザクションを検証するとき、楽観的読み取りが検証に失敗（fail）した場合、次いで、現在の集約書き込み停止補償マップを参照して、トランザクショナルメモリワードにおけるバージョン番号の差が、そのオブジェクトまたはメモリ領域に対する入れ子の子トランザクションの集約リリースカウントに正確に一致しているかどうか確認する。正確に一致している場合、楽観的読み取りは有効であり、上記親は、不正に失敗させられるべきではない。本明細書で使用されるとき、トランザクショナルメモリワード（transactional memory word）という用語は、ロック状態およびバージョン番号など所与のトランザクションに関する様々な情報を追跡する、各トランザクションに対して提供されるデータ構造を含むように意図されている。例えば、ＴＭＷは、バージョン番号、およびリーダのリスト／カウントおよび／またはインジケータを含むことができる。別の実装では、リーダのリスト／カウントおよび／またはインジケータは、所与の時点で特定の値にアクセスしている（例えば、悲観的な）特定のリーダのリストを含むことができる。さらに別の実装では、リーダのリスト／カウントおよび／またはインジケータは、単に、所与の時点で特定の値にアクセスしている１つまたは複数のリーダが存在していることを示す、フラグまたは他のインジケータである。これらは例示にすぎず、本明細書におけるＴＭＷという用語の使用は、トランザクションの状態を追跡するための様々な機構を網羅するように意図されている。
【００１３】
図１に示されるように、本システムの１つまたは複数の部分を実装するために使用する例示的なコンピュータシステムには、コンピューティングデバイス１００などのコンピューティングデバイスが含まれる。最も基本的な構成では、コンピューティングデバイス１００は、典型的に、少なくとも１つの処理ユニット１０２およびメモリ１０４を含む。コンピューティングデバイスの正確な構成およびタイプに応じて、メモリ１０４は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭ、フラッシュメモリなど）、またはこれら２つの何らかの組み合わせとすることができる。この最も基本的な構成は、図１では破線１０６によって図示されている。
【００１４】
さらに、デバイス１００は、追加の機能／機能性を有することもできる。例えば、デバイス１００は、これらには限られないが磁気または光ディスクまたはテープを含め、追加のストレージ（取り外し可能および／または取り外し不可能）を含むこともできる。このような追加のストレージは、図１では、取り外し可能ストレージ１０８および取り外し不可能ストレージ１１０によって図示されている。コンピュータ記憶媒体には、コンピュータ読取可能命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実装される、揮発性および不揮発性、取り外し可能および取り外し不可能な媒体が含まれる。メモリ１０４、取り外し可能ストレージ１０８、および取り外し不可能ストレージ１１０は、全てコンピュータ記憶媒体の例である。コンピュータ記憶媒体には、ＲＡＭ、ＲＯＭ，ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくは他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージもしくは他の磁気ストレージデバイス、または所望の情報を記憶するのに使用可能であってデバイス１００によってアクセス可能な任意の他の媒体が含まれるが、これらには限定されない。このようなコンピュータ記憶媒体は全て、デバイス１００の一部とすることができる。
【００１５】
コンピューティングデバイス１００は、該コンピューティングデバイス１００が他のコンピュータ／アプリケーション１１５と通信することを可能にする、１つまたは複数の通信接続１１４を含む。デバイス１００は、キーボード、マウス、ペン、音声入力装置、タッチ入力装置などの入力装置１１２も有する。ディスプレイ、スピーカ、プリンタなどの出力装置１１２も含まれる。これらの装置は当技術分野で周知であるので、ここでは詳細に議論する必要はない。一実装では、コンピューティングデバイス１００は、トランザクショナルメモリアプリケーション（transactional memory application）２００を含む。トランザクショナルメモリアプリケーション２００については、図２でより詳細に説明する。
【００１６】
引き続き図１を参照しつつ図２に移ると、コンピューティングデバイス１００において動作するトランザクショナルメモリアプリケーション２００が図示されている。トランザクショナルメモリアプリケーション２００は、コンピューティングデバイス１００に存在するアプリケーションプログラムの１つである。しかしながら、代替または追加としてトランザクショナルメモリアプリケーション２００を、１つまたは複数のコンピュータにおけるコンピュータ実行可能命令として、および／または図１に示されているものと異なる変形形態のコンピュータ実行可能命令として具現化することもできる。代替または追加として、トランザクショナルアプリケーションメモリ２００の１つまたは複数の部分を、システムメモリ１０４の一部分とすること、他のコンピュータおよび／またはアプリケーション１１５上のものにすること、あるいはコンピュータソフトウェアの分野で起こり得るような上記他の変形形態とすることができる。
【００１７】
トランザクショナルメモリアプリケーション２００には、本明細書で説明される技法の一部または全てを実行することに関与するプログラムロジック２０４が含まれる。プログラムロジック２０４は、（以下で図４に関連して説明されるように）入れ子トランザクションが最初にロールバックして書き込みロックを解放するときに、書き込み停止補償マップ（ＷＡＣＭ：write abort compensation map）を作成するためのロジック２０６、（以下で図４に関連して説明されるように）所与のトランザクショナルメモリワードにおいて入れ子トランザクションが書き込みロックを解放した回数を、ＷＡＣＭ内の各エントリに記録するためのロジック２０８、（以下で図４に関連して説明されるように）親のトランザクションログ内にＷＡＣＭを保持するためのロジック２１０、（以下で図４に関連して説明されるように）特定の入れ子トランザクションが再実行して再びロールバックする場合に、同じＷＡＣＭを使用して更新するためのロジック２１２、（以下で図５に関連して説明されるように）適切であるとしてＷＡＣＭを集約するためのロジック２１４、（以下で図６に関連して説明されるように）トランザクションの検証中に、失敗した楽観的読み取りが実際には有効であるか、または無効であるかを判断するためにＷＡＣＭを使用するためのロジック２１６、およびアプリケーションを動作させるための他のロジック２２０
を含む。
【００１８】
引き続き図１〜２を参照しながら図３〜６に移ると、トランザクショナルメモリアプリケーション２００の１つまたは複数の実装形態を実装するための諸段階が、より詳細に説明されている。一部の実装において図３〜６の処理は、少なくとも部分的にコンピューティングデバイス１００のオペレーティングロジックで実装される。図３は、トランザクショナルメモリアプリケーション２００に関する高レベルの処理フロー図である。処理は開始ポイント２４０で始まる。入れ子トランザクションのロールバック中に解放された任意の書き込みロックが、親トランザクションを失敗させる可能性を有する（段階２４２）。トランザクションがロールバックすると、バージョン番号が増加される毎に該バージョン番号が記憶される（段階２４４）。本システムは、ロールバックする各入れ子トランザクションについて、この情報をトラックする（段階２４８）。トランザクションの検証の間に、本システムはこの情報を使用して、検証を失敗した特定の楽観的読み取りが、差が入れ子の子の再実行するによるものであったために実際には有効であるかどうかを判断する（段階２４８）。これらの段階について、図４〜６でより詳細に説明する。処理は終了ポイント２５０で終了する。
【００１９】
図４は、書き込み停止補償マップを作成および維持することに関連する諸段階の一実装を図示している。処理は、開始ポイント２７０で始まり、入れ子トランザクションが初めてロールバックして書き込みロックを解放すると、一意のロック識別子（lock identifier）によってキー付けされた書き込み停止補償マップ（ＷＡＣＭ）を作成する（段階２７２）。ＷＡＣＭ内の各エントリは、入れ子トランザクションが、所与のトランザクショナルメモリワードにおいて書き込みロックを解放した回数を記録する（段階２７４）。
【００２０】
ＷＡＣＭは、親トランザクションのログ内に保持され、該親によって全ての楽観的読み取りが行われた後、入れ子トランザクションの開始時に順序付けされる（段階２７６）。特定の入れ子トランザクションが再実行して再びロールバックする場合、システムは、同じＷＡＣＭを使用し、任意の新しい書き込みロックの解放を用いて該ＷＡＣＭを更新する（段階２７８）。入れ子トランザクションが、前の実行で獲得したロックを再び獲得する場合、トランザクショナルメモリワードのカウントは、ＷＡＣＭにおいてインクリメントされる（段階２８０）。処理は、終了ポイント２８２で終了する。
【００２１】
図５は、トランザクションのロールバック中にＷＡＣＭを集約することに関連する諸段階の一実装を図示している。処理は、開始ポイント２９０で始まり、多くの入れ子の子の親でもあった入れ子トランザクションが、そのログ全体に分散された複数のＷＡＣＭを有する可能性がある（段階２９２）。トランザクションのロールバック中に複数のＷＡＣＭが発見される場合、次いで、入れ子の子に起因する全てのＷＡＣＭが単一のＷＡＣＭに集約され、親のログ内に配置される（段階２９４）。処理は終了ポイント２９６で終了する。
【００２２】
図６は、トランザクションの検証中にＷＡＣＭを使用して入れ子の親を不正に失敗させることを回避することに関連する諸段階の一実装を図示している。処理は、開始ポイント３１０で始まり、親のログを逆に処理しつつ、検証プロセスの間に、楽観的読み取りエントリが処理されていると見なされる任意のＷＡＣＭを、一時ＷＡＣＭに集約する（段階３１２）。楽観的読み取りが、バージョン番号の不一致が原因で検証に失敗した場合（決定ポイント３１４）、次いで、ＴＭＷアドレスをキーとして使用して、一時ＷＡＣＭを参照する（段階３１６）。そのＴＭＷアドレスにおいて一致するエントリが存在する場合（決定ポイント３１８）、次いでシステムは、そのエントリに関連付けられたカウントが、バージョン番号の差と正確に一致しているかどうかを計算する（決定ポイント３２０）。カウントがバージョン番号の差と正確に一致している場合（決定ポイント３２０）、楽観的読み取りは有効であり、この差は単に、入れ子の子を再実行したことよるものであった（段階３２２）。そうでない場合は、楽観的読み取りは無効であり、これは、他のトランザクションのコミット／ロールバックによるものである（段階３２４）。これらの段階は、全ての親のログについて繰り返される。処理は、終了ポイント３２８で終了する。
【００２３】
本主題を、構造的機能および／または方法論的アクトに特有の言語で説明してきたが、添付の特許請求の範囲によって定義される本発明の対象は、必ずしも上述した特定の機能またはアクトに限定されないことを理解されたい。むしろ、上述の特定の機能およびアクトは、特許請求の範囲を実装するための例示の形式として開示されている。本明細書内および／または特許請求の範囲によって説明されるような実装に関する精神に含まれる全ての均等物、変形形態、および修正形態も保護されることが望まれる。
【００２４】
例えば、コンピュータソフトウェアの技術分野の当業者には、本明細書で議論された例示を、例示として描写されたものより少ないまたは追加のオプションまたは機能を含むように１つまたは複数のコンピュータにおいて異なるように編成することが可能であることが理解されよう。
【図１】
2010532052.tif 000003
【図２】
2010532052.tif 000004
【図３】
2010532052.tif 000005
【図４】
2010532052.tif 000006
【図５】
2010532052.tif 000007
【図６】
2010532052.tif 000008
【国際調査報告】
2010532052.tif 000009
2010532052.tif 000010