(57)【特許請求の範囲】
【請求項１】
ソフトウェアトランザクショナルメモリシステム中でトランザクションに順序付けを適用する、コンピュータシステムに実装される方法であって、該方法は、前記コンピュータシステムの少なくとも１つのコンピューティングデバイスによって実施され、
複数の関連するトランザクションの実行の前の任意の時点で、所定のコミット順序を、前記複数の関連するトランザクションについて指定するステップと、
前記所定のコミット順序を使用して、コミット順序番号を前記複数の関連するトランザクションのそれぞれに提供するステップと、
共有ソフトウェアトランザクショナルメモリ中で複数のトランザクションを実行するステップであって、前記複数のトランザクションのそれぞれは、前記ソフトウェアトランザクショナルメモリ中で前記複数のトランザクションの他のトランザクションに関して原子的に実行されるステップを含み、
前記複数のトランザクションを実行するステップは、
前記複数の関連するトランザクションの第１のトランザクション、および、前記複数の関連するトランザクションの第２のトランザクションを実行するステップであって、前記第１のトランザクションの前記コミット順序番号は、前記第２のトランザクションの前記コミット順序番号とは異なるステップと、
前記ソフトウェアトランザクショナルメモリシステム中での前記複数のトランザクションの前記実行を管理するステップとを含み、
前記実行を管理ステップは、
前記第１のトランザクションと前記第２のトランザクションとの間の競合を検出するステップと、
前記競合を解決するステップとを含み、
前記競合を解決するステップは、
前記第２のトランザクションの前記コミット順序番号に基いて、前記第２のトランザクションをホールド状態にするステップと、
前記第１のトランザクションの前記コミット順序番号に基いて、前記第１のトランザクションをコミットするステップと、
前記第１のトランザクションがコミットされた後に、前記第２のトランザクションをコミットするステップと
によって、前記競合を解決するステップと
を含むことを特徴とする方法。
【請求項２】
前記所定のコミット順序は、前記複数の関連するトランザクションが特定の線形順序でコミットするよう強いられる、前記複数の関連するトランザクションの所定の全体的順序付けを含むことを特徴とする請求項１に記載の方法。
【請求項３】
前記所定のコミット順序は、前記複数の関連するトランザクションをコミットするための複数の許容可能な順序付けを特定する、前記複数の関連するトランザクションの所定の部分的順序付けを含むことを特徴とする請求項１に記載の方法。
【請求項４】
前記所定のコミット順序を指定するステップの後に、コミットアービトレータによって、前記所定のコミット順序に関する１つまたは複数の順序付け値を追跡するステップであって、前記１つまたは複数の順序付け値は、前記複数の関連するトランザクションを互いにコミットする適切な順序付けを決定するために使用されるステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項５】
前記複数の関連するトランザクションのうちの特定のトランザクションがコミットする準備ができたとき、前記１つまたは複数の順序付け値を前記特定のトランザクションに提供されたコミット順序番号と比較して、前記特定のトランザクションがコミットできるかどうか判定することを特徴とする請求項４に記載の方法。
【請求項６】
前記所定のコミット順序は、動的に指定されることを特徴とする請求項１に記載の方法。
【請求項７】
前記所定のコミット順序は、静的に指定されることを特徴とする請求項１に記載の方法。
【請求項８】
前記所定のコミット順序を指定するステップの後に、コミットアービトレータによって、前記複数の関連するトランザクションのうちでコミットすることが許可されるべき次のトランザクションのコミット順序番号を表すｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドを追跡するステップをさらに含むことを特徴とする請求項１に記載の方法。
【請求項９】
前記複数の関連するトランザクションのうちの特定のトランザクションがコミットする準備ができたとき、前記特定のトランザクションのコミット順序番号が、前記コミットアービトレータによって追跡される前記ｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドと同じ値を有するかどうか判定することを特徴とする請求項８に記載の方法。
【請求項１０】
前記特定のトランザクションの前記コミット順序番号と前記ｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドとが同じ値を有する場合は、前記コミットの続行を許可することを特徴とする請求項９に記載の方法。
【請求項１１】
前記コミットが続行して成功した後、前記コミットアービトレータは前記ｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドをシーケンスにおける次の数にインクリメントすることを特徴とする請求項１０に記載の方法。
【請求項１２】
前記特定のトランザクションの前記コミット順序番号と前記ｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドとが同じ値を有さない場合は、前記特定のトランザクションが、先行トランザクションがコミットした後の、より後の時点でウェイクされるまで、前記特定のトランザクションをホールド状態にすることを特徴とする請求項９に記載の方法。
【請求項１３】
請求項１に記載の方法をコンピュータに実施させるためのコンピュータ実行可能命令を記憶していることを特徴とするコンピュータ可読媒体。
【請求項１４】
ソフトウェアトランザクショナルメモリシステム中で順序付けによるコンテンション管理を提供する、コンピュータシステムに実装される方法であって、該方法は、前記コンピュータシステムの少なくとも１つのコンピューティングデバイスによって実施され、
複数のトランザクションの実行の前の任意の時点で、所定のコミット順序を、トランザクショングループ中で前記複数のトランザクションについて指定することと、
前記トランザクショングループの第１のトランザクションおよび第２のトランザクションを実行することであって、前記第１のトランザクションおよび前記第２のトランザクションは、ソフトウェアトランザクショナルメモリ中で他のトランザクションに関して原子的に実行されることと、
前記第１のトランザクションと前記第２のトランザクションとの間で競合が発生したときにコンテンション管理プロセスを呼び出すことと、
前記トランザクショングループ中の前記複数のトランザクションについて指定された前記所定のコミット順序にしたがって、前記第１のトランザクションと前記第２のトランザクションをコミットすることと
を含むことを特徴とする方法。
【請求項１５】
前記コンテンション管理プロセスを呼び出した後に、前記所定のコミット順序を使用して、前記トランザクショングループ中でそれぞれのコミット順序番号を前記複数のトランザクションに提供することと、
前記第１のトランザクションと前記第２のトランザクションとが同じトランザクショングループに含まれるかどうかを、前記コンテンション管理プロセスによって判定することと、
前記第１のトランザクションと前記第２のトランザクションとが同じトランザクショングループに含まれると判定された場合、前記第１のトランザクションに提供された前記コミット順序番号と、前記第２のトランザクションに提供された前記コミット順序番号とを比較することと、
前記第１のトランザクションと前記第２のトランザクションのうち、どちらがより低いコミット順序番号を有するかに基いて、前記第１のトランザクションと前記第２のトランザクションのうち、特定のトランザクションが続行されるのを許可することと
をさらに含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
請求項１４に記載の方法をコンピュータに実施させるためのコンピュータ実行可能命令を記憶していることを特徴とするコンピュータ可読媒体。
【請求項１７】
コンピュータ実行可能命令を記憶しているコンピュータ可読媒体であって、前記コンピュータ実行可能命令は、ソフトウェアトランザクショナルメモリシステムを有するコンピュータを制御して、
ソフトウェアトランザクショナルメモリ中で他のトランザクションに関して原子的に実行される第１のトランザクションと第２のトランザクションの実行の前の任意の時点で、所定のコミット順序を指定することと、
前記第１のトランザクションと前記第２のトランザクションとの間に競合が発生したときにコンテンション管理プロセスを呼び出すことと、
前記指定された所定のコミット順序に基いて、前記第１のトランザクションと前記第２のトランザクションとからコミットするトランザクションを決定することと、
前記決定されたトランザクションをコミットすることと
を含む方法を、前記コンピュータに実施させることを特徴とするコンピュータ可読媒体。
【請求項１８】
前記方法は、
前記コンテンション管理プロセスを呼び出した後に、ネストされたトランザクション内でコミット順序付けを実行することをさらに含むことを特徴とする請求項１７に記載のコンピュータ可読媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、ソフトウェアトランザクショナルメモリシステム中でトランザクションに順序付けを適用することに関する。
【背景技術】
【０００２】
ソフトウェアトランザクショナルメモリ（ＳＴＭ）は、並行コンピューティングにおいて共有メモリへのアクセスを制御するための、データベーストランザクションに似た並行処理制御機構である。トランザクショナルメモリのコンテキストにおいて、トランザクションは、共有メモリに対する一連の読取りおよび書込みを実行するコードの一部分である。ＳＴＭは、従来のロック機構の代替として使用される。プログラマは、コードブロックの周囲に宣言的注釈（例えばａｔｏｍｉｃ）を配置して、必要とする安全性プロパティを示し、システムは自動的に、このブロックが他の保護されたコード領域に対して原子的に実行されることを保証する。ソフトウェアトランザクショナルメモリのプログラミングモデルは、ロックベースの優先順位逆転およびデッドロックの問題を防止する。
【０００３】
通常のＳＴＭシステムは多くの利点を有するが、それでもプログラマは、意図されないメモリアクセス順序付けを回避することに注意を払う必要がある。例えば、通常のＳＴＭ環境では、トランザクションがコミットされる順序（すなわちコミット処理）は制約されない。トランザクションは、相互に競争してコミットし、このことは、トランザクション１がトランザクション２の前にコミットするかまたは後にコミットするかということが、プログラムの動的スケジューリングの（また、しばしばプログラム特有ロジックによる）結果であることが多いことを意味する。さらに、メモリの同じ部分に書き込もうとすることなどにより２つのトランザクションが競合する場合は、これらのトランザクションのコミット順序は、多くの可能なコンテンション管理ポリシの１つに基づいて任意に決定される可能性がある。これらのシナリオの両方で、特定のコミット順序は保証されない。したがって、プログラマには、自身のプログラムがどちらの順序でも正しく動くようにするという負担がかかっている。このため、並列プログラミングは非常に難しい。
【０００４】
並列プログラミングを単純化する手法の１つは、プログラムのセマンティクスが変更されないことを保証するようにして、逐次的プログラム（sequential programs）を自動的に並列化することである。言い換えれば、逐次的なプログラムが正しく動くならば、並列化したバージョンもそのようになる。逐次的プログラムを並列化するこの概念の、２つの（別々の）変形は、それぞれセーフフューチャ（safe futures）および投機的ループ並列化（speculative loop parallelization）と呼ばれてきた。セーフフューチャでは、プログラムの逐次的バージョンは「Ａ；Ｂ」を実施する（すなわちＡを行ってからＢを行う）場合がある。プログラマは、注釈（annotation）（「フューチャ」）を追加して、プログラムセマンティクスを変更せずにＡとＢとを並列で実施することが可能であろうと自身が思っていること、つまりＡはＢが読み取るどんなメモリ位置も読み取らず、その逆も同様であると思っていることを示すことができる。しかし、システムはこれを、その有効性をチェックしなければならない「ヒント」として厳格に扱う。システムは、ＡおよびＢをトランザクションとして実行し、これらが競合する場合は、ＢがＡの前に直列化されることになればＢがコミットしないようにする。これが、先に触れた未定コミット順序の「望ましくない」一面である。
【０００５】
投機的ループ並列化は同様の考えであり、逐次的プログラム中で実施されるアクションは、ループの連続的反復である。プログラマ（または何らかの静的分析）は、ループを並列実行することが有利であろうことを示し、システムは、ループの各反復を並列トランザクションとして実行して、元のプログラム中で反復がコミットしたであろう順序でこれらのトランザクションがコミットすることを必要とする。
【発明の概要】
【発明が解決しようとする課題】
【０００６】
ソフトウェアトランザクショナルメモリシステム中でトランザクションに順序付けを適用する技術および技法を提供する。
【課題を解決するための手段】
【０００７】
ソフトウェアトランザクショナルメモリシステム中でトランザクションに順序付けを適用するための、様々な技術および技法を開示する。所定のコミット順序を複数のトランザクションに対して指定できるようにする機能が、ソフトウェアトランザクショナルメモリシステムに提供される。所定のコミット順序は、実行時に使用されて、ソフトウェアトランザクショナルメモリシステム中でトランザクションをコミットする順序を決定する助けとなる。一実施形態では、所定のコミット順序は、全体的順序付けと部分的順序付けのいずれかとすることができる。全体的順序付けの場合は、トランザクションは線形順序でコミットするよう強いられる。部分的順序付けの場合は、トランザクションは複数の許容可能なシナリオのうちの１つでコミットすることが許可される。一実施形態では、コミットアービトレータ（arbitrator）が、次にコミットすることが許可されるべきトランザクションを表すｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔ値を常に把握しており、特定のトランザクションがコミットする準備ができたとき、そのコミット順序番号がコミットアービトレータのｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔ値と一致する場合に、この特定のトランザクションはコミットすることが許可される。
【０００８】
第１のトランザクションと第２のトランザクションとの間で競合が発生した場合、コンテンション管理プロセスが呼び出される。所定のコミット順序は、コンテンション管理プロセス中で使用されて、第１のトランザクションと第２のトランザクションのどちらが競合に勝って続行を許可されるべきかを決定する助けとなる。
【０００９】
この概要は、発明を実施するための形態でさらに後述する単純化した形の概念の精選を紹介するために提供した。この概要は、特許請求する主題の鍵となる特徴または必須の特徴を識別するものとはせず、また、特許請求する主題の範囲を決定する助けとして使用されるものともしない。
【図面の簡単な説明】
【００１０】
【図１】一実施形態のコンピュータシステムの図である。
【図２】図１のコンピュータシステム上で動作する一実施形態のソフトウェアトランザクショナルメモリアプリケーションの図である。
【図３】図１のシステムの一実施形態に関する高レベルのプロセスフロー図である。
【図４】コミットアービトレータを使用して所定のコミット順序を実行することに含まれる段階を示す、図１のシステムの一実施形態のプロセスフロー図である。
【図５】コミットアービトレータを使用して複数のトランザクションの全体的順序付けを実行することに含まれる段階を示す、図１のシステムの一実施形態のプロセスフロー図である。
【図６】コミットアービトレータを使用して複数のトランザクションの部分的順序付けを実行することに含まれる段階を示す、図１のシステムの一実施形態のプロセスフロー図である。
【図７】所定のコミット順序情報を使用して競合を管理するコンテンション管理プロセスを提供することに含まれる段階を示す、図１のシステムの一実施形態のプロセスフローである。
【図８】所定のコミット順序情報を使用して、ネストされたトランザクションを伴う競合を管理するコンテンション管理プロセスを提供することに含まれる段階を示す、図１のシステムの一実施形態のプロセスフローである。
【図９】共通の先祖を有するトップレベルの先祖を含む例示的な先祖ツリーを示す論理図である。
【図１０】共通の先祖を有さないトップレベルの先祖を含む例示的な先祖ツリーを示す論理図である。
【図１１】コミットアービトレータをソフトウェアトランザクショナルメモリシステム中で使用して無駄な作業の量を削減することに含まれる段階を示す、図１のシステムの一実施形態のプロセスフロー図である。
【図１２】コンテンション管理プロセス中で先祖連鎖全体を分析して適切な競合解決を決定することに含まれる段階を示す、図１のシステムの一実施形態のプロセスフロー図である。
【発明を実施するための形態】
【００１１】
本発明の原理の理解を促進するために、次に、図面に示す実施形態を参照して、具体的な用語を使用してその実施形態について説明する。しかし、それによって範囲の限定は意図されないことを理解されたい。説明する実施形態の任意の改変およびさらなる修正、ならびに本明細書に述べる原理の任意のさらなる適用も、当業者が通常思い付くであろうものとして企図される。
【００１２】
本システムは、ソフトウェアトランザクショナルメモリシステムとしての一般的なコンテキストにおいて述べることができるが、これらに加えて他の目的にも役立つ。一実施形態では、本明細書に述べる技法の１つまたは複数は、ＭＩＣＲＯＳＯＦＴ（登録商標）．ＮＥＴ  Ｆｒａｍｅｗｏｒｋなどのフレームワークプログラム内の機能として、あるいは、開発者がソフトウェアアプリケーションを開発するためのプラットフォームを提供する他の任意のタイプのプログラムまたはサービスからの機能として実施することができる。別の実施形態では、本明細書に述べる技法の１つまたは複数は、並行環境で実行されるアプリケーションの開発を扱う他のアプリケーションによる機能として実施される。
【００１３】
所定のコミット順序を複数のトランザクションに対して指定できるようにする機能が、ソフトウェアトランザクショナルメモリシステムに備わる。所定のコミット順序が使用されて、トランザクションをコミットする順序を決定する助けとなる。一実施形態では、第１のトランザクションと第２のトランザクションとの間で競合が発生したとき、コンテンション管理プロセスが呼び出される。次いで、所定のコミット順序は、コンテンション管理プロセス中で使用されて、第１のトランザクションと第２のトランザクションのどちらが競合に勝って続行を許可されるべきかを決定する助けとなる。
【００１４】
図１に示すように、本システムの１つまたは複数の部分を実施するのに使用する例示的なコンピュータシステムは、コンピューティングデバイス１００などのコンピューティングデバイスを含む。コンピューティングデバイス１００は通常、その最も基本的な構成では、少なくとも１つの処理ユニット１０２と、メモリ１０４とを備える。コンピューティングデバイスの正確な構成およびタイプに応じて、メモリ１０４は揮発性（ＲＡＭなど）、不揮発性（ＲＯＭ、フラッシュメモリなど）、またはこの２つの組合せとすることができる。この最も基本的な構成は、図１では破線１０６で示されている。
【００１５】
加えて、デバイス１００は、追加の機構／機能を有することもできる。例えば、デバイス１００は、追加の記憶装置（取外し可能および／または取外し不可能）を備えることもでき、これらは磁気または光学のディスクまたはテープを含むが、これらに限定されない。このような追加の記憶装置は、図１では取外し可能な記憶装置１０８および取外し不可能な記憶装置１１０で示されている。コンピュータ記憶媒体は、コンピュータ可読命令、データ構造、プログラムモジュール、または他のデータなどの情報を記憶するための任意の方法または技術で実現された、揮発性と不揮発性、取外し可能と取外し不可能の媒体を含む。メモリ１０４、取外し可能な記憶装置１０８、および取外し不可能な記憶装置１１０はすべて、コンピュータ記憶媒体の例である。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリ、または他のメモリ技術、ＣＤ−ＲＯＭ、ディジタル多用途ディスク（ＤＶＤ）、または他の光学記憶装置、磁気カセット、磁気テープ、磁気ディスク記憶装置、または他の磁気記憶デバイスを含み、あるいは、所望の情報を記憶するのに使用できデバイス１００によってアクセスできる他の任意の媒体を含むが、これらに限定されない。このような任意のコンピュータ記憶媒体をデバイス１００の一部とすることができる。
【００１６】
コンピューティングデバイス１００は、コンピューティングデバイス１００が他のコンピュータ／アプリケーション１１５と通信できるようにする１つまたは複数の通信接続１１４を備える。デバイス１００はまた、キーボード、マウス、ペン、音声入力デバイス、タッチ入力デバイスなど、入力デバイス（複数可）１１２を有することもできる。また、表示装置、スピーカ、プリンタなど、出力デバイス（複数可）１１１を備えることもできる。これらのデバイスはすべて当技術分野で周知であり、ここでは詳細に論じない。一実施形態では、コンピューティングデバイス１００は、ソフトウェアトランザクショナルメモリアプリケーション２００を備える。ソフトウェアトランザクショナルメモリアプリケーション２００については、図２でさらに詳細に述べる。
【００１７】
引き続き図１を参照しながら、次に図２に目を向けると、コンピューティングデバイス１００上で動作するソフトウェアトランザクショナルメモリアプリケーション２００が示されている。ソフトウェアトランザクショナルメモリアプリケーション２００は、コンピューティングデバイス１００上にあるアプリケーションプログラムの１つである。しかし、ソフトウェアトランザクショナルメモリアプリケーション２００は、別法としてまたは追加で、１つまたは複数のコンピュータ上の、かつ／あるいは図１に示したものとは異なる変形における、コンピュータ実行可能命令として具体化されてもよいことは理解されるであろう。別法としてまたは追加で、ソフトウェアトランザクショナルメモリアプリケーション２００の１つまたは複数の部分は、他のコンピュータおよび／またはアプリケーション１１５上のシステムメモリ１０４の一部、あるいはコンピュータソフトウェアの当業者なら思い付くであろう他のそのような変形の一部とすることもできる。
【００１８】
ソフトウェアトランザクショナルメモリアプリケーション２００は、本明細書に述べる技法のいくつかまたはすべてを実施することを担うプログラムロジック２０４を含む。プログラムロジック２０４は、ソフトウェアトランザクショナルメモリ（ＳＴＭ）システムを提供するためのロジック２０６と、ＳＴＭシステム中で所定のコミット順序を複数のトランザクションに対して静的または動的に指定できるようにするコミットアービトレータを提供するためのロジック２０８と、コミットアービトレータが所定のコミット順序を実行時に使用して、ソフトウェアトランザクショナルメモリシステム中で複数のトランザクションをコミットする順序を決定する助けとするのを可能にするためのロジック２１０と、第１のトランザクションと第２のトランザクションとの間に競合が発生したときに呼び出されるコンテンション管理プロセスを提供するためのロジック２１２と、所定のコミット順序をコンテンション管理プロセス中で使用して、第１のトランザクションと第２のトランザクションのどちらが競合に勝って続行を許可されるべきかを決定する助けとする（例えば、同じトランザクショングループ中の２つのトランザクションのうち、どちらのトランザクションのコミット順序番号の方が低いかに応じて）ためのロジック２１４と、コミットアービトレータが所定のコミット順序付けを使用して１つまたは複数の順序付け値（例えば、全体的順序付けでは、複数のトランザクションのうちでコミットを許可されるべき次のトランザクションを表すｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールド）を追跡するように動作できることを可能にするためのロジックであって、１つまたは複数の順序付け値を所与のトランザクションの特定のコミット順序番号と比較して、実行すべき順序付けを仮定した場合の所与のトランザクションのコミットが適切かどうか確認するためのロジック２１６と、アプリケーションを動作させるための他のロジック２２０とを含む。一実施形態では、プログラムロジック２０４は、プログラムロジック２０４中のプロシージャへの単一呼出しを使用するなどして、別のプログラムからプログラム的に呼び出されるように動作可能である。
【００１９】
引き続き図１〜２を参照しながら、次に図３〜１０に目を向けると、ソフトウェアトランザクショナルメモリアプリケーション２００の１つまたは複数の実施形態を実現するための段階（stages）がさらに詳細に述べてある。図３は、ソフトウェアトランザクショナルメモリアプリケーション２００に関する高レベルのプロセスフロー図である。一形式では、図３のプロセスは、少なくとも部分的にはコンピューティングデバイス１００の動作ロジック中で実施される。この手順は開始点２４０で開始し、ソフトウェアトランザクショナルメモリシステムが提供される（段階２４２）。所定のコミット順序（例えば全体的順序付けまたは部分的順序付け）を複数のトランザクションに対して指定する（例えば動的または静的に割り当てる）のを可能にする機能が提供される（段階２４４）。本明細書において「所定のコミット順序」という用語は、トランザクションが実行を開始する前の任意の時点で決定される、関連するトランザクションの特定のグループがコミットされるべき具体的な順序を含むものとして意図される。本明細書においてトランザクションの「グループ」という用語は、同じコミットアービトレータによって管理される特定の１組の（例えば複数の）トランザクション、ならびにこれらのトランザクションのネストされた子を含む。
【００２０】
所定のコミット順序が実行時に使用されて、ソフトウェアトランザクショナルメモリシステム中で複数のトランザクションをコミットする順序を決定する助けとなる（段階２４６）。所定のコミット順序が使用されて、複数のトランザクションのうちの２つまたはそれ以上の間で発生する競合を解決する助けとなる（段階２４８）。プロセスは終了点２５０で終了する。
【００２１】
図４に、コミットアービトレータを使用して所定のコミット順序を実行することに含まれる段階の一実施形態を示す。一形式では、図４のプロセスは、少なくとも部分的にはコンピューティングデバイス１００の動作ロジック中で実施される。この手順は開始点２７０で開始し、１つまたは複数のコミットアービトレータがソフトウェアトランザクションメモリシステムに提供される。コミットアービトレータは、所定のコミット順序を複数のトランザクションに対して指定するのを可能にするように動作可能である（段階２７２）。本明細書において「コミットアービトレータ」という用語は、相互に順序付けるべきトランザクションの１つまたは複数のグループを管理することを担う任意のタイプのプログラム、機能、またはプロセスを含むものとして意図される。一実施形態では、いずれか所与の時点で、プログラム内でアクティブなコミットアービトレータが１つまたは複数あってもよい。例えば、必要なだけ多くのコミットアービトレータを作り出して、種々のトランザクショングループを管理することができる。コミットアービトレータは、相互に適切なトランザクションの順序付けを決定するのに使用される１つまたは複数の順序付け値を追跡および更新する（段階２７４）。全体的順序付けの場合は、ｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドを使用して、複数のトランザクションのうちで次にコミットされるべき次のトランザクションを表すことができる（段階２７４）。部分的順序付けの場合は、順序付け値を使用して、種々の可能な順序の有向グラフが追跡される。適宜、コミットアービトレータは、所定のコミット順序を使用して、複数のトランザクションのそれぞれにコミット順序番号を提供する（段階２７６）。
【００２２】
複数のトランザクションのうちの特定のトランザクションがコミットする準備ができたとき、この特定のトランザクションのコミット順序番号を１つまたは複数の順序付け値と比較してコミットが適切であることが明らかになった場合は、コミットアービトレータは、トランザクションがコミットするのを許可する（段階２７８）。全体的順序付けの場合は、このシナリオは、ｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドと、特定のトランザクションのコミット順序番号とが同じ値を有するときに生じる。このようなシナリオでは、コミットアービトレータは、トランザクションがコミットするのを許可し、次いで、コミットが成功した場合はｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドをシーケンスにおける次の数（例えば次に高い数）にインクリメントする（段階２７８）。複数のトランザクションのうちの特定のトランザクションがコミットする準備ができたとき、この特定のトランザクションのコミット順序番号を順序付け値と比較してコミットが適切でないことが明らかになった場合は、特定のトランザクションは、先行トランザクションがコミットした後の、より後の時点でウェイクされるまで、ホールドモード（hold mode）にされる（段階２８０）。全体的順序付けの場合は、ｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドと、特定のトランザクションの順序番号とが同じ値を有さないときに、このホールドモードに入る。
【００２３】
一実施形態では、システムはトランザクションを、そのすぐ前の先行トランザクションがコミットした後でウェイクすることができ、この場合はすぐにコミットを試みることができる。別法として、システムはトランザクションを、そのすぐ前の先行トランザクションがまだコミットしていない場合があっても、すぐ前ではない何らかの先行トランザクションがコミットした後でウェイクすることを選択することができる。ウェイクされた後、システムは、トランザクションが本当にコミットすることが適切かどうかチェックして確認する。適切である場合は、トランザクションはコミットされる。プロセスは終了点２８２で終了する。
【００２４】
図５に、コミットアービトレータを使用して複数のトランザクションの全体的順序付けを実行することに含まれる段階の一実施形態を示す。一形式では、図５のプロセスは、少なくとも部分的にはコンピューティングデバイス１００の動作ロジック中で実施される。この手順は開始点２９０で開始し、所定の全体的順序付け（例えば、複数のトランザクションがコミットされるべき正確な順序を指定するもの）を複数のトランザクションに対して指定するのを可能にするように動作可能な１つまたは複数のコミットアービトレータが提供される（段階２９２）。複数のトランザクションのうちの特定のトランザクションがそのコミットポイントに達したとき、コミット順序を実行するために、この特定のトランザクションのコミット順序がコミットアービトレータのｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドと比較される（段階２９６）。一実施形態では、全体的順序付けの実行が必要でないとシステムが決定した場合は（例えば競合が絶対にないなどの理由で）、全体的順序付け要件を適宜破棄することができ（段階２９４）、次いでプロセスは終了点３０２で終了する。
【００２５】
コミット順序付けが実行されることになる場合、かつ特定のトランザクションのコミット順序がコミットアービトレータのｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドと同じ値を有する場合（判定点２９６）は、特定のトランザクションはコミットされ、コミットが成功した場合、ｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドがインクリメントされ、後続トランザクションが存在すればそれがウェイクされる（段階２９８）。特定のトランザクションのコミット順序がコミットアービトレータのｎｅｘｔ−ｔｏ−ｃｏｍｍｉｔフィールドと同じ値を有さない場合（判定点２９６）は、特定のトランザクションは、先行トランザクションがコミットした後の、より後の時点でウェイクされるまで、ホールド／スリープモードにされる（段階３００）。一実施形態では、このより後の時点で、先行トランザクションとの競合が発生した場合は、先行トランザクションが前進できるように中止し、ロールバックするよう、この特定のトランザクションに要求することができる。そうではなく、そのような競合が発生しなかった場合は、特定のトランザクションは、本明細書に述べるコミット順序要件が満たされればコミットできるべきである。次いでプロセスは終了点３０２で終了する。
【００２６】
図６に、コミットアービトレータを使用して複数のトランザクションの部分的順序付けを実行することに含まれる段階の一実施形態を示す。一形式では、図６のプロセスは、少なくとも部分的にはコンピューティングデバイス１００の動作ロジック中で実施される。この手順は開始点３１０で開始し、所定の部分的順序付け（例えば、複数のトランザクションがコミットされるべき複数の許容可能な順序を例えば有向グラフの形で指定するもの）を複数のトランザクションに対して指定するのを可能にするように動作可能な１つまたは複数のコミットアービトレータが提供される（段階３１２）。複数のトランザクションのうちの特定のトランザクションがそのコミットポイントに達したとき、コミット順序を実行するために、先行トランザクションの状態（例えば１つまたは複数の順序付け値）が、コミットする特定のトランザクションに対して照会される（例えばコミットアービトレータによって追跡されて）（段階３１４）。特定のトランザクションに対するすべての先行トランザクションがコミット済みである場合は（判定点３１６）、特定のトランザクションはコミットされる（段階３１８）。コミットが成功した場合、コミットアービトレータによって追跡される１つまたは複数の値は適宜更新され、可能な後続トランザクションが存在すればそれらはすべてウェイクされる（段階３１８）。
【００２７】
特定のトランザクションに対するすべての先行トランザクションがコミットしていない場合は（判定点３１６）、特定のトランザクションは、先行トランザクションがコミットした後の、より後の時点でウェイクされるまで、ホールド／スリープモードにされる（段階３２０）。プロセスは終了点３２２で終了する。
【００２８】
図７に、所定のコミット順序情報を使用して競合を管理するコンテンション管理プロセスを提供することに含まれる段階の一実施形態を示す。一形態では、図７のプロセスは、少なくとも部分的にはコンピューティングデバイス１００の動作ロジック中で実施される。この手順は開始点３４０で開始し、１つまたは複数のトランザクショングループに対する所定のコミット順序をサポートするソフトウェアトランザクショナルメモリシステムが提供される（段階３４２）。第１のトランザクションと第２のトランザクションとの間で競合が発生したときに呼び出されるコンテンション管理プロセスが提供される（段階３４４）。所定のコミット順序が、コンテンション管理プロセス中で使用されて、第１のトランザクションと第２のトランザクションのどちらが競合に勝って続行を許可されるべきかを決定する助けとなる（段階３４６）。第１のトランザクションと第２のトランザクションとが同じトランザクショングループの一部でない場合は（判定点３４８）、この２つのトランザクション間で所定のコミット順序は実行されない（所定のコミット順序が存在しなかったため）（段階３５０）。このようなシナリオでは、２つのトランザクションが同じトランザクショングループ中にないので、順序付けファクタを使用して競合の解決を助けることはしない（段階３５０）。
【００２９】
第１のトランザクションと第２のトランザクションとが同じトランザクショングループの一部である場合は（判定点３４８）、システムは、第１のトランザクションの第１の順序番号と、第２のトランザクションの第２の順序番号とを比較する（段階３５２）。順序番号が低い方の（または別の適した優先順位付けによる）トランザクションが、続行を許可される（段階３５４）。プロセスは終了点３５６で終了する。
【００３０】
図８に、所定のコミット順序情報を使用して、ネストされたトランザクションを伴う競合を管理するコンテンション管理プロセスを提供することに含まれる段階の一実施形態を示す。一形式では、図８のプロセスは、少なくとも部分的にはコンピューティングデバイス１００の動作ロジック中で実施される。一実施形態では、各トランザクションにつき、その特定のトランザクションをコミットする前に先祖連鎖全体が考慮され、それにより、その連鎖中に順序付けがあればそれが実行される。この手順は開始点３７０で開始し、第１のトランザクションと第２のトランザクションとの間で競合が発生したときに呼び出されるコンテンション管理プロセスが提供される（段階３７２）。所定のコミット順序が、コンテンション管理プロセス中で使用されて、第１のトランザクションと第２のトランザクションのどちらが競合に勝って続行を許可されるべきかを決定する助けとなる（段階３７４）。第１と第２のトランザクションが同じトランザクショングループの一部でない場合は（判定点３７６）、この２つのトランザクション間で所定のコミット順序は実行されず（所定のコミット順序が存在しなかったため）（段階３７８）、プロセスは終了点３８８で終了する。第１と第２のトランザクションが同じトランザクショングループの一部である場合は（判定点３７６）、システムは、ネストされたトランザクションが関係するかどうかチェックして確認する（判定点３８０）。
【００３１】
ネストされたトランザクションが関係しない場合は（判定点３８０）、第１のトランザクションの順序番号（または他の順序付けインジケータ）が、第２のトランザクションの順序番号（または他の順序付けインジケータ）と比較される（段階３８４）。順序番号が低い方のトランザクション（または、他の適した順序付け基準を使用して次の順番であると決定されたトランザクション）が、続行を許可される（段階３８６）。
【００３２】
ネストされたトランザクションが関係する場合は（判定点３８０）、第１のトランザクションのトップレベルの先祖の順序番号（または他の順序付けインジケータ）が、第２のトランザクションのトップレベルの先祖の順序番号（または他の順序付けインジケータ）と比較される（段階３８２）。本明細書において「トップレベルの先祖（top level ancestor）」という用語は、共通の先祖が関係する場合の、共通の先祖の直接の子と、関係する共通の先祖がない場合の、各トランザクションのトップレベルの先祖とを含むものと意図される。共通および非共通の先祖を含むこれらのシナリオについては、図９および１０により詳細に示す。順序番号が低い方のトランザクション（例えば、より低い順序番号または他の適した基準を有した先祖に関連するトランザクション）が、続行を許可される（段階３８６）。プロセスは終了点３８８で終了する。
【００３３】
図９は、共通の先祖を有するトップレベルの先祖を含む例示的な先祖ツリーを示す論理図である。図示の例では、トランザクションＡは、ＤとＥの共通の先祖である。ＤとＥの間で発生した競合では、トランザクションＢとＣ（共通の先祖Ａの直接の子）の順序番号が分析されて、トランザクションＤとＥのどちらが続行を許可されるべきかが決定される（図８の段階３８２）。
【００３４】
図１０は、共通の先祖を有さないトップレベルの先祖を含む例示的な先祖ツリーを示す論理図である。図示の例では、トランザクションＡはトランザクションＣの先祖である。トランザクションＤはトランザクションＦの先祖である。トランザクションＣとＦの間に発生した競合では、トランザクションＡとＤ（それぞれのトップレベルの先祖）の順序番号が比較されて、トランザクションＣとＦのどちらが続行を許可されるべきかが決定される（図８の段階３８２）。
【００３５】
図１１に、コミットアービトレータをソフトウェアトランザクショナルメモリシステム中で使用して無駄な作業の量を削減することに含まれる段階の一実施形態を示す。一形式では、図１１のプロセスは、少なくとも部分的にはコンピューティングデバイス１００の動作ロジック中で実施される。この手順は開始点４００で開始し、１つまたは複数のコミットアービトレータがソフトウェアトランザクショナルメモリシステムに提供される。コミットアービトレータは、所定のコミット順序を複数のトランザクションに対して指定するのを可能にするように動作可能である（段階４０２）。コミットアービトレータは、トランザクションをスリープ／ホールドモードにして、先行トランザクションがまだ実行されているときにこのトランザクションが再実行されるのを阻止するように動作可能である（例えば、所定のコミット順序を分析して適切な順序を決定することによって）（段階４０４）。また、コミットアービトレータは、先行トランザクション（複数可）が終了すると、ホールドにされていたトランザクションをウェイクアップするようにも動作可能である（例えば、再び所定のコミット順序を分析して適切な順序を決定することによって）（段階４０６）。これらの阻止機構およびウェイク機構を提供することにより、コミットアービトレータは、後で取り消さなければならなくなる操作が実施されないようにすることによって、無駄な作業の量を削減するのを助ける（段階４０８）。プロセスは終了点４１０で終了する。
【００３６】
図１２に、コンテンション管理プロセス中で先祖連鎖全体を分析して適切な競合解決を決定することに含まれる段階の一実施形態を示す。一形式では、図１２のプロセスは、少なくとも部分的にはコンピューティングデバイス１００の動作ロジック中で実施される。この手順は開始点４３０で開始し、第１のトランザクションと第２のトランザクションとの間で競合が発生したときに呼び出されるコンテンション管理プロセスが提供される（段階４３２）。所定のコミット順序が、コンテンション管理プロセス中で使用されて、第１のトランザクションと第２のトランザクションのどちらが競合に勝って続行を許可されるべきかを決定する助けとなる（段階４３４）。所定のコミット順序の先祖連鎖全体が分析されて、適切な競合管理を決定するのを助ける（段階４３６）。例えば、２つの親および２つの子の、４つのトランザクションがある場合に、ＢはＡ内にネストされ、ＤはＣ内にネストされている。ＡはＣの前にコミットすべきであるという順序付け関係が、ＡとＣの間にあると仮定する。ＢとＤが競合する場合、コンテンション管理プロセスは、Ｂを優遇すべきである。というのは、ＡがＣの前にコミットしなければならないとすれば、Ｄを優遇するのは無益だからである（段階４３６）。プロセスは終了点４３８で終了する。
【００３７】
本明細書で説明した実施形態例では、様々な技術および技法を使用してコミットの順序付けを実行することについて述べたが、トランザクションはコミットアービトレータを全く有さない場合もあることに留意されたい。トランザクションがコミットアービトレータを全く有さない場合は、順序付けのない通常のコミットが行われることになる。
【００３８】
構造上の特徴および／または方法上の行為に特有の言葉で本主題を述べたが、添付の特許請求の範囲に定義する本主題は、前述の具体的な特徴または行為に必ずしも限定されないことを理解されたい。そうではなく、前述の具体的な特徴および行為は、特許請求の範囲を実現する例示的な形として開示する。本明細書に述べた実施形態の趣旨に含まれる、かつ／または添付の特許請求の範囲による、あらゆる均等物、変更、および修正は、保護されることが望まれる。
【００３９】
例えば、本明細書で説明した実施形態で述べたようなクライアントおよび／またはサーバ構成、ユーザインタフェーススクリーン内容、ならびに／あるいはデータレイアウトを、１つまたは複数のコンピュータ上で違った形で構成して、実施形態で示したものよりも少ないまたは追加のオプションまたは特徴を含めることができることは、コンピュータソフトウェアの当業者なら理解するであろう。
【図１】
0004698757.tif 000002
【図２】
0004698757.tif 000003
【図３】
0004698757.tif 000004
【図４】
0004698757.tif 000005
【図５】
0004698757.tif 000006
【図６】
0004698757.tif 000007
【図７】
0004698757.tif 000008
【図８】
0004698757.tif 000009
【図９】
0004698757.tif 000010
【図１０】
0004698757.tif 000011
【図１１】
0004698757.tif 000012
【図１２】
0004698757.tif 000013