(57)【要約】  ソフトウェアトランザクショナルメモリシステムにおいてバッファリングされた書込みおよび強制的直列化順序をサポートする様々な技術および技法を開示する。オブジェクトのシャドウコピーへの書込みを行い、コミット中に個々のトランザクションの妥当性を確認した後でコンテンツをオブジェクトに書き戻す、バッファリングされた書込みプロセスを提供する。特定のトランザクションの書込みロックが最初に取得されると、特定のオブジェクトのシャドウコピーが作成される。シャドウコピーへの書込みと該シャドウコピーからの読込みが行われる。コミット中に特定のトランザクションの妥当性を確認した後、コンテンツは、シャドウコピーから特定のオブジェクトに書き込まれる。トランザクションがコミットされる順序がトランザクションの抽象的直列化順序に一致することを保証する、トランザクション順序付けプロセスを提供する。トランザクションは、該トランザクションのチケット番号が、コミットするべき次のトランザクションをトラッキングするグローバル番号に一致するまで、コミットを許可されない。
2010524133.tif 000002
【特許請求の範囲】
【請求項１】
複数のトランザクションを管理するように動作可能なソフトウェアトランザクショナルメモリシステムを提供するステップと、
オブジェクトのシャドウコピーへの書込みと該シャドウコピーからの読込みを行い、コミット中に前記複数のトランザクションの個々のトランザクションの妥当性を確認した後にコンテンツを前記オブジェクトに書き戻す、バッファリングされた書込みプロセスを提供するステップと、
前記複数のトランザクションがコミットされる順序が前記複数のトランザクションの抽象的直列化順序に一致することを保証する、トランザクション順序付けプロセスを提供するステップと
を含むステップをコンピュータに実行させるためのコンピュータ実行可能命令を有することを特徴とするコンピュータ読取可能媒体。
【請求項２】
前記バッファリングされた書込みプロセスは、書込みロックが最初に取得されたときに前記オブジェクトのうちの特定の１つの特定のシャドウコピーを作成するように動作可能であることを特徴とする請求項１に記載のコンピュータ読取可能媒体。
【請求項３】
前記バッファリングされた書込みプロセスは、前記特定のシャドウコピーがすでに存在する場合は、前記オブジェクトのうちの前記特定の１つの前記特定のシャドウコピーにアクセスするように動作可能であることを特徴とする請求項２に記載のコンピュータ読取可能媒体。
【請求項４】
前記トランザクション順序付けプロセスは、グローバルデータ構造を使用して、前記トランザクションがコミットされている前記順序が前記抽象的直列化順序に一致することを保証するように動作可能であることを特徴とする請求項１に記載のコンピュータ読取可能媒体。
【請求項５】
前記グローバルデータ構造は、入力コミットカウンタと終了コミットカウンタとを含み、前記入力コミットカウンタは、コミット処理に入ったトランザクションの第１の数を表し、前記終了コミットカウンタは、コミット処理を終了しトランザクションの第２の数を表すことを特徴とする請求項４に記載のコンピュータ読取可能媒体。
【請求項６】
前記個々のトランザクションがコミット処理に入ると、前記個々のトランザクションは、前記入力コミットカウンタをアトミックに読み込み、インクリメントし、前記入力コミットカウンタから読み込まれた値を前記個々のトランザクションのチケット番号として割り当てることを特徴とする請求項５に記載のコンピュータ読取可能媒体。
【請求項７】
前記個々のトランザクションは、該個々のトランザクションがコミット処理の後に続行することを許可される前、前記終了コミットカウンタが該個々のトランザクションの前記チケット番号に一致するまで待機することを特徴とする請求項６に記載のコンピュータ読取可能媒体。
【請求項８】
前記バッファリングされた書込みプロセス、および前記トランザクション順序付けプロセスの使用は、私有化関連問題が回避されることを保証することを特徴とする請求項１に記載のコンピュータ読取可能媒体。
【請求項９】
ソフトウェアトランザクショナルメモリシステムにおいてバッファリングされた書込みを提供するための方法であって、
複数のトランザクションを管理するように動作可能なソフトウェアトランザクショナルメモリシステムを提供するステップと、
特定のトランザクションについて書込みロックを最初に取得したときに、特定のオブジェクトのシャドウコピーを作成するステップと、
前記シャドウコピーへの書込みと前記シャドウコピーからの読込みを行うステップと、
コミット中に前記特定のトランザクションの妥当性を確認した後に、コンテンツを前記シャドウコピーから前記特定のオブジェクトに書き込むステップと
を含むことを特徴とする方法。
【請求項１０】
前記特定のオブジェクトは、オブジェクトヘッダ内に、ロックタイプおよびバージョンをトラッキングするように動作可能なトランザクショナルメモリワードを有することを特徴とする請求項９に記載の方法。
【請求項１１】
前記トランザクショナルメモリワードは、前記シャドウコピーへのポインタを表すことを特徴とする請求項１０に記載の方法。
【請求項１２】
前記特定のトランザクションは、前記特定のトランザクションが直列化されたのと同じ順序でコミット処理を終了することを許可されることを特徴とする請求項９に記載の方法。
【請求項１３】
前記特定のトランザクションは、前記特定のトランザクションのチケット番号が、コミットを許可されるべき次のトランザクションを識別するグローバルカウンタに一致するまで、コミット処理を終了しないことを特徴とする請求項１２に記載の方法。
【請求項１４】
請求項９に記載のステップをコンピュータに実行させるためのコンピュータ実行可能命令を有することを特徴とするコンピュータ読取可能媒体。
【請求項１５】
ソフトウェアトランザクショナルメモリシステムにおいてトランザクションが直列化順序でコミットされることを保証するための方法であって、
複数のトランザクションを管理するように動作可能なソフトウェアトランザクショナルメモリシステムを提供するステップと、
コミット処理に入ったトランザクションの第１の数を表す入力コミットカウンタを提供するステップと、
コミット処理を終了しトランザクションの第２の数を表す終了コミットカウンタを提供するステップと、
前記複数のトランザクションのうちの特定のトランザクションがコミット処理に入ったときに、前記入力コミットカウンタをアトミックに読み込み、インクリメントし、前記入力コミットカウンタから読み込まれた値を前記特定のトランザクションのチケット番号として割り当てるステップと、
前記終了コミットカウンタが前記特定のトランザクションの前記チケット番号に一致するときに、前記特定のトランザクションをコミットするステップと
を含むことを特徴とする方法。
【請求項１６】
バッファリングされた書込みプロセスは、前記特定のトランザクションがコミットするまでオブジェクトのシャドウコピーへの書込みと該シャドウコピーからの読込みを行うために使用されることを特徴とする請求項１５に記載の方法。
【請求項１７】
特定のオブジェクトのシャドウコピーは、書込みロックが最初に取得されたときに作成されることを特徴とする請求項１６に記載の方法。
【請求項１８】
書込みは、前記特定のオブジェクトの前記シャドウコピーに行われ、読込みは、前記特定のオブジェクトの前記シャドウコピーから行われることを特徴とする請求項１７に記載の方法。
【請求項１９】
コンテンツは、前記特定のトランザクションがコミット中に妥当性を確認された後、前記シャドウコピーから前記特定のオブジェクトに書き込まれることを特徴とする請求項１８に記載の方法。
【請求項２０】
請求項１５に記載のステップをコンピュータに実行させるためのコンピュータ実行可能命令を有することを特徴とするコンピュータ読取可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、バッファリングされた書込み（buffered writes）および強制的直列化順序（enforced serialization order）を使用するトランザクショナルメモリに関する。
【背景技術】
【０００２】
コンピュータの処理ユニットは、命令のプログラムテキストからの命令ストリームを実行する。各命令は、その後続の命令、すなわち、それに続く命令、あるいは分岐またはコールの場合は他の何らかの命令のいずれかを指定する。したがって、プロセッサは、一度に１つの命令を実行する（いわゆるパイプライン化された（pipelined）「アウトオブオーダ（out-of-order）」のプロセッサは、該プロセッサの実装においてはこれに反しているが、これらのセマンティクスは保っている）。プログラムは、通常、区別化された開始命令（distinguished start instruction）を有するプログラムテキストにコンパイルされる。例えば、Ｃプログラムでは、「メイン」メソッドの第１の命令は、区別化された開始命令である。この後に実行される命令のシーケンスを決定する「プロセッサコンテキスト（processor context）」は、しばしば「コントロールスレッド」、または単に「スレッド」と呼ばれる。プログラムは、各プロセスが「仮想」マシンの全てのメモリに対する唯一のアクセスを有するかのように振る舞うことを可能にする、仮想アドレス空間を提供するオペレーティングシステムプロセスにおいて実行する。オペレーティングシステムプロセスは、仮想アドレス空間に加えて、ファイル記述子や１つまたは複数のスレッドなどの、様々なプロセスごとのオペレーティングリソースを提供する。従来のプログラムは、シングルスレッド（single-threaded）である。すなわち、従来のプログラムは、単一のコントロールスレッドしか有しないプロセスで実行する。
【０００３】
共有メモリマルチプロセッサ（shared-memory multiprocessor）は、同じメモリへのアクセスを共有するいくつかのプロセッサを有しており、あるプロセッサによる書込みが、別のプロセッサによるその後の読込みによって観察されることがある。そのようなマシンは、別々のプロセッサ上でいくつかの異なるプログラムをプロセスごとに実行することによって使用されること可能である。このモードでは、プロセスがそれぞれ別個のアドレス空間を有するので、実際には、共有メモリは使用されない。しかし、別のモードでは、プログラムは、それが実行するプロセスにおいていくつかのコントロールのスレッドを作成することができ、これらのスレッドは、複数のプロセッサ上で同時に実行し、共有メモリを介して通信することができる。（そのようなマルチスレッド、すなわち並列（concurrent）プログラムは、ユニプロセッサ上で実行することもでき、一般に、プログラムは、存在する利用可能なプロセッサより多くのスレッドを作成することができる。オペレーティングシステムのジョブの１つは、利用可能なプロセッサ上で動作可能なスレッドの実行をスケジューリングすることである。したがって、動作中のスレッドを任意の命令において中断して、別のスレッドが再開することを可能にする。）
【０００４】
スレッドによってこのように同時にインターリーブされる命令の実行は、並列プログラミングを非常に困難にする。例として、赤色のカードが全て第１の山に、黒色のカードが全て第２の山になるように分けられている１組のカードを想像されたい。各カードが１つの命令を表し、各山が１つのスレッドを表す。ブリッジのシャフリング技法を使用してこれらの山を混ぜ合わせる。赤色のカードの互いに対する順序は変更されず、黒色のカードの互いに対する順序も変更されないが、カードは交互に配置（インターリーブ）された。これは、まさに、スレッドが並行に実行するときに発生することである。それぞれが可能な実行を表す非常に多くの可能なインタリービング（interleavings）があることも明らかなはずである。プログラムは、そのような可能な実行の全てについて正確に機能する必要がある。
【０００５】
スレッドが並列コンピューティング環境で実行するとき、各スレッドが共有メモリなどのシステムリソースとどのように対話するかを管理するための機構が必要とされる。ソフトウェアトランザクショナルメモリ（ＳＴＭ：software transactional memory）は、並列コンピューティング内の共有メモリへのアクセスを制御するためのデータベーストランザクションと類似の並列処理制御機構（concurrency control mechanism）である。トランザクショナルメモリのコンテキストにおけるトランザクションは、共有メモリへの一連の読込みと書込みを実行し、しかもアトミックにトランザクション全体がシステム内で実行している唯一のコントロールスレッドであるかのように実行する、コードの一部分である。トランザクションＴｘ１が、トランザクションＴｘ２によるいずれかの書込みを観察した場合、トランザクションＴｘ１は、次いでＴｘ２による全ての書込みを観察する。トランザクショナルメモリのコンテキストにおけるデータの位置は、単一のオブジェクト、（Ｃ＋＋などにおける）キャッシュライン、ページ、単一のワードなどの、アクセスされている共有メモリの特定のセグメントである。トランザクショナルメモリシステムにおける、あるタイプの並列処理制御ロックモードは、楽観的並列処理制御（optimistic concurrency control）、または楽観的ロッキング（optimistic locking）である。
【０００６】
楽観的並列処理制御では、システムは、衝突（conflict）が後に検出されることがあるというリスクがあっても進行することを試みる。トランザクショナルメモリシステムは、しばしば、衝突しているトランザクションの１つをロールバックして、それを再実行することによって、そのような衝突の自動的な解決を行う。楽観的オペレーション（optimistic operations）は、読込みだけであり共有位置への書込みは伴わないので（すなわち、ロックを取る）ので、悲観的オペレーション（pessimistic operations）と比べると比較的コストはかからない。その名前が暗示するように、楽観的オペレーションに対する期待は衝突がほとんどないことである。これが間違いであると分かった場合は、作業がすでに無駄であり、システムはその作業をやめて衝突の解決を試みる必要がある。
【発明の概要】
【発明が解決しようとする課題】
【０００７】
楽観的並列処理制御が明示的に対処していない１つの深刻な問題は、私有化（privatization）シナリオにおいて発生し得る。私有化関連の問題は、プログラムが、並列スレッドに同じ共有メモリロケーションにアクセスするトランザクションを実行させ、これらのトランザクションのうちの１つが、ある共有メモリ位置を私有化するときに発生することがある。私有化は、あるトランザクションが、共有メモリロケーションが該トランザクションに対してのみアクセス可能にされるオペレーションを実行するときに発生する。例えば、あるオブジェクトＯへの唯一のリファレンスが、あるグローバルにアクセス可能なキューＱに格納されており、スレッドＴ１によって実行されているトランザクションＴｘ１が、ＱからＯへのリファレンスを除去するオペレーションを行い、これをローカル変数Ｔ１に格納した場合、Ｔｘ１が、ＯをＴ１に私有化することになる。
【０００８】
ＳＴＭの一部の実施形態では、私有化は、予期しない結果を発生させる可能性がある。一部のＳＴＭ実施形態は、楽観的読込みを「インプレース（ｉｎ−ｐｌａｃｅ）」書込みと結合することによって高い性能を達成しようと試みてきたが、この場合、トランザクショナル書込みは、メモリロケーションに対して直接行われる。これらの技法を使用して、私有化を行うプログラムを実装するときは、以下のシナリオがあり得る。あるグローバルロケーションＧが、共有データ構造への一意のポインタを含む。２つのスレッドが、このデータ構造に並列にアクセスしようと試みるトランザクションを実行する。スレッドＴ１は、Ｇを読み込むトランザクションＴｘ１を実行し、ポインタ読込みが非ヌルの場合、スレッドＴ１は、該ポインタが参照するデータ構造内の整数をインクリメントすることを試みる。スレッドＴ２は、Ｇをスレッドローカル変数にコピーしてＧをヌルにセットするトランザクションＴｘ２を実行する。次いで、スレッドＴ２は、Ｇをヌルにセットしたことによってデータ構造を成功裏に「私有化」したと信じて、スレッドローカルポインタ変数を介して該データ構造にアクセスする。しかし、楽観的読込みおよびインプレース書込みでは、ある実行で、Ｔｘ１が最初にＧを読み込み、非ヌル値を観察することがある。このとき、Ｔｘ２は、その全体を実行する。Ｔｘ２は、Ｔｘ１が読み込んだロケーションＧ、を書き込むことで、Ｔｘ１を途中停止するように「決定づける（dooming）」が、これは、Ｔｘ１がコミットを試みるまで発見されない。したがって、Ｔｘ１は実行を継続して、データ構造内のフィールドをインクリメントする。このインクリメントは、Ｔｘ１がコミットできなかったときは取り消されることになるが、非トランザクショナルコードはスレッドＴ２でＴｘ２の後に実行するという観点から、この書込み、および「取消し」オペレーションを行う書込みは両方とも「不可解な（inexplicable）」ことであり、これらは理由なく発生して、プログラムを不正確に実行させる可能性がある。
【０００９】
別の種類の私有化関連の問題は、「直列化の異常（serialization anomalies）」を有することである。前述したように、トランザクションは、並列トランザクションがある一連の順序で実行するという錯覚をプログラマに提供することによって、並列プログラミングを容易にする。具体的には、トランザクションＴｘ２による読込みが、トランザクションＴｘ１による書込みを観察した場合は、Ｔｘ２は、Ｔｘ１の後に直列化されなければならない。直列化の異常は、トランザクションがそれらの直列的な順序とは異なる順序で完了したときに発生する。プログラムが私有化のイディオムを利用するとき、このことにより、スレッド内でトランザクションの１つが完了した後に実行している非トランザクションコードが、「不可解な」書込みを観察する可能性がある。
【課題を解決するための手段】
【００１０】
ソフトウェアトランザクショナルメモリシステムにおいて、バッファリングされた書込みと強制的直列化順序をサポートする様々な技術および技法を開示する。トランザクションを管理するように動作可能なソフトウェアトランザクショナルメモリシステムを提供する。オブジェクトのシャドウコピーへの書込みおよび該シャドウコピーからの読込みを行い、コミット中に個々のトランザクションの妥当性を確認した後にコンテンツをオブジェクトに書き戻す、バッファリングされた書込みプロセスを提供する。最初に特定のトランザクションについて書込みロックが取得されると、特定のオブジェクトからシャドウコピーが作成される。シャドウコピーへの書込みが行われる。コミット中に特定のトランザクションの妥当性を確認した後、コンテンツがシャドウコピーから特定のオブジェクトに書き込まれる。
【００１１】
トランザクションがコミットされる順序がトランザクションの抽象的直列化順序（abstract serialization order）に一致することを保証する、トランザクション順序付けプロセスを提供する。コミット処理に入った第１の数のトランザクションを表す、入力コミットカウンタ（entered commit counter）を提供する。コミット処理を終了した第２の数のトランザクションを表す、終了コミットカウンタ（exited commit counter）が提供される。特定のトランザクションがコミット処理に入ると、システムは、入力コミットカウンタをアトミックに読み込み、インクリメントして、入力コミットカウンタから読み込まれた値を特定のトランザクションのチケット番号として割り当てる。終了コミットカウンタが特定のトランザクションのチケット番号に一致するとき、特定のトランザクションはコミット処理を終了する。
【００１２】
この課題を解決するための手段は、以下の発明を実施するための形態においてさらに詳細に説明される概念の選択を簡略化した形で紹介するために提供したものである。この課題を解決するための手段は、特許請求される対象について重要な特徴または本質的な特徴を特定することは意図されておらず、特許請求される対象の範囲を決定する際の補助として使用されることも意図されていない。
【図面の簡単な説明】
【００１３】
【図１】一実施形態のコンピュータシステムを示す概略図である。
【図２】図１のコンピュータシステム上で動作する一実施形態のソフトウェアトランザクショナルメモリ・アプリケーションを示す概略図である。
【図３】図１のシステムの一実施形態に関する高度なプロセスのフロー図である。
【図４】ソフトウェアトランザクショナルメモリシステムにおいてバッファリングされた書込みを使用するのに必要とされる高度な段階を示す、図１のシステムの一実施形態のためのプロセスのフロー図である。
【図５】ソフトウェアトランザクショナルメモリシステムでバッファリングされた書込みを使用するのに必要とされるより詳細な段階を示す、図１のシステムの一実施形態のためのプロセスのフロー図である。
【図６】トランザクショナルメモリワード内のバッファリングされた書込み情報をトラッキングするのに必要とされる段階を示す、図１のシステムの一実施形態のためのプロセスのフロー図である。
【図７】共有メモリ内のオブジェクトのシャドウコピーおよびオブジェクトへのリファレンスを保持するトランザクショナルメモリワードを示す論理図である。
【図８】トランザクションが抽象的直列化順序と同じ順序でコミットすることを保証するのに必要とされる高度な段階を示す、図１のシステムの一実施形態のためのプロセスのフロー図である。
【図９】トランザクションが抽象的直列化順序と同じ順序でコミットすることを保証するのに必要とされるより詳細な段階を示す、図１のシステムの一実施形態のためのプロセスのフロー図である。
【発明を実施するための形態】
【００１４】
本発明の原理の理解を促進する目的で、図面に図示されている実施形態を参照し、同様に説明するために特定の文言を使用する。しかしながら、このことによって、その範囲を限定することは意図されていないことは理解されよう。説明される実施形態の全ての代替形態およびさらなる変更形態、ならびに本明細書に記載される原理の他のいかなる利用形態も、当業者であれば通常は考え付くであろう。
【００１５】
本システムは、一般的なコンテキストではソフトウェアトランザクショナルメモリシステムとして説明されるが、本システムは、これらに加えて他の目的でも機能する。一実施形態では、本明細書に記載される技法の１つまたは複数を、ＭＩＣＲＯＳＯＦＴ（登録商標）．ＮＥＴフレームワークなどのフレームワークプログラムにおける機能として、あるいは、開発者がソフトウェアアプリケーションを開発するためのプラットフォームを提供する任意の他のタイプのプログラムまたはサービスからの機能として実装することができる。別の実施形態では、本明細書に記載の技法の１つまたは複数は、並列環境で実行するアプリケーションの開発に取り組む他のアプリケーションの機能として実装される。
【００１６】
一実施形態では、バッファリングされた書込みプロセスを使用して、オブジェクトのシャドウコピーへの書込みと、コミット中に個々のトランザクションの妥当性を確認した後に、コンテンツのオブジェクトへの書き戻しとを行う、ソフトウェアトランザクショナルメモリシステムを提供する。別の実施形態では、トランザクションがコミットされる順序がトランザクションの抽象的直列化順序に一致することを保証するトランザクション順序付けプロセスを提供する。トランザクションは、プログラマにトランザクションが順次それぞれ別々に実行するという錯覚を与えることにより、並列プログラミングを簡単にする。抽象的直列化順序とは、単に、トランザクションが実行するために現われる順序である。この順序は、トランザクションによって行われる読込みと書込みによって決定される。Ｔｘ１およびＴｘ２が、両方ともコミットするトランザクションであり、Ｔｘ２による読込みがＴｘ１によって書き込まれた値を観察した場合は、Ｔｘ１は、抽象的直列化順序でＴｘ２に先行しなければならない。それぞれが、他方が書き込んだ値を読み込んだ場合、それらを直列化することはできないため、両方ともコミットすることができず、したがって、少なくとも１つが途中停止しなければならない。両方がコミットしたとき、それぞれが他方に先行しなければならない場合は、１つが途中停止しなければならない。バッファリングされた書込みプロセスおよび／またはトランザクション順序付けプロセスを使用することにより、私有化関連の問題のうちの少なくとも一部は回避される。
【００１７】
図１に示されているように、システムの１つまたは複数の部分を実装するために使用する例示的なコンピュータシステムは、コンピューティング装置１００などのコンピューティング装置を含む。その最も基本的な構成では、コンピューティング装置１００は、典型的に、少なくとも１つの処理ユニット１０２およびメモリ１０４を含む。コンピューティング装置の正確な構成およびタイプに応じて、メモリ１０４は、揮発性（ＲＡＭなど）、不揮発性（ＲＯＭ、フラッシュメモリなど）、またはこの２つの何らかの組合せとすることができる。この最も基本的な構成は、図１では破線１０６で図示されている。
【００１８】
さらに、装置１００は、追加の特徴／機能を有することもできる。例えば、装置１００は、これらには限られないが、磁気または光ディスクまたはテープを含め、追加のストレージ（取外し可能および／または取外し不可能）を含むこともできる。このような追加のストレージは、図１では、取外し可能なストレージ１０８および取外し不可能なストレージ１１０で図示されている。コンピュータ記憶媒体は、コンピュータ読取可能な命令、データ構造、プログラムモジュールまたは他のデータなどの情報の記憶のために任意の方法または技術で実装される、揮発性および不揮発性媒体、取外し可能な媒体および取外し不可能な媒体を含む。メモリ１０４、取外し可能なストレージ１０８、および取外し不可能なストレージ１１０は全て、コンピュータ記憶媒体の例である。コンピュータ記憶媒体は、ＲＡＭ、ＲＯＭ、ＥＥＰＲＯＭ、フラッシュメモリもしくは他のメモリ技術、ＣＤ−ＲＯＭ、デジタル多用途ディスク（ＤＶＤ）もしくは他の光ストレージ、磁気カセット、磁気テープ、磁気ディスクストレージもしくは他の磁気ストレージ装置、または所望の情報を記憶するために使用可能であって、装置１００がアクセス可能な他の任意の媒体も含むが、これらには限定されない。このようないかなるコンピュータ記憶媒体も、装置１００の一部とすることができる。
【００１９】
コンピューティング装置１００は、コンピューティング装置１００が他のコンピュータ／アプリケーション１１５と通信することができるようにする、１つまたは複数の通信接続１１４を含む。装置１００は、キーボード、マウス、ペン、音声入力装置、タッチ入力装置などの入力装置１１２を有することもできる。また、ディスプレイ、スピーカ、プリンタなどの出力装置１１１を含むこともできる。これらの装置は、当技術分野ではよく知られているので、ここで詳細に議論する必要はない。一実施形態では、コンピューティング装置１００は、ソフトウェアトランザクショナルメモリ・アプリケーション（software transactional memory application）２００を含む。ソフトウェアトランザクショナルメモリ・アプリケーション２００について、図２でさらに詳細に説明する。
【００２０】
ここで、図１を参照しながら図２を参照すると、コンピューティング装置１００上で動作するソフトウェアトランザクショナルメモリ・アプリケーション２００が図示されている。ソフトウェアトランザクショナルメモリ・アプリケーション２００は、コンピューティング装置１００上に存在するアプリケーションプログラムの１つである。しかし、ソフトウェアトランザクショナルメモリ・アプリケーション２００は、代替または追加的に、１つまたは複数のコンピュータ上で、および／または図１に示されているものとは異なる変形形態において、コンピュータ実行可能命令として具現化され得ることが理解されよう。代替または追加として、ソフトウェアトランザクショナルメモリ・アプリケーション２００の１つまたは複数の部分は、他のコンピュータおよび／またはアプリケーション１１５におけるシステムメモリ１０４の一部分、あるいはコンピュータソフトウェアの技術分野において考えうる他の変形形態におけるシステムメモリ１０４の一部分とすることができる。
【００２１】
ソフトウェアトランザクショナルメモリ・アプリケーション２００は、本明細書で説明される技法の一部または全てを実施する役割を担うプログラムロジック２０４を含む。プログラムロジック２０４は、次のロジックを含む。すなわち、複数のトランザクションを管理するように動作可能なソフトウェアトランザクショナルメモリ・システムを提供するためのロジック２０６と、オブジェクトのシャドウコピーへの書込みと該シャドウコピーへの読込みを行い、コミット中に複数のトランザクションの個々のトランザクションの妥当性を確認した後でコンテンツをオブジェクトに書き戻す、バッファリングされた書込みプロセスを提供するためのロジック２０８と、複数のトランザクションがコミットされる順序が複数のトランザクションの抽象的直列化順序と一致することを保証する、トランザクション順序付けプロセスを提供するためのロジック２１０と、書込みロックが最初に取得されたとき、バッファリングされた書込みプロセスが、オブジェクトのうちの特定の１つのオブジェクトの特定のシャドウコピーを作成することと、シャドウコピーがすでに存在する場合はそのシャドウコピーにアクセスすることとを可能にするためのロジック２１２と、トランザクション順序付けプロセスが、グローバルデータ構造を使用してコミットの順序（例えば、入力コミットカウンタと終了コミットカウンタ）を保証することを可能にするためのロジック２１４と、トランザクション順序付けプロセスが、個々のトランザクションがコミット処理に入ると入力コミットカウンタをアトミックに読み込み、インクリメントし、入力コミットカウンタから読み込んだ値を、個々のトランザクションのチケット番号として割り当てることを可能にするためのロジック２１６と、トランザクション順序付けプロセスが、個々のトランザクションがコミット処理後の続行を許可される前は、終了コミットカウンタが個々のトランザクションのチケット番号に一致するまで、該個々のトランザクションを待機させることを可能にするためのロジック２１８と、バッファリングされた書込みプロセスおよび／またはトランザクション順序付けプロセスを使用することによって私有化関連問題を回避するためのロジック２２０と、アプリケーションを動作するための他のロジック２２２とを含む。一実施形態では、プログラムロジック２０４は、プログラムロジック２０４内のプロシージャに対するシングルコールを使用することなど、別のプログラムからプログラム的に呼び出されるように動作することができる。
【００２２】
次に、図１〜２を参照し続けながら図３〜９を参照すると、ソフトウェアトランザクショナルメモリ・アプリケーション２００の１つまたは複数の実施形態を実装するための複数の段階がさらに詳細に説明されている。図３は、ソフトウェアトランザクショナルメモリ・アプリケーション２００に関する高度なプロセスのフロー図である。一形態において、図３のプロセスは、コンピューティング装置１００のオペレーティングロジックで少なくとも部分的に実装される。本プロセスは、開始点２４０で始まり、複数のトランザクションを管理するように動作可能なソフトウェアトランザクショナルメモリシステムを提供する（段階２４２）。オブジェクトのシャドウコピーへの書込みを行い、複数のトランザクションの個々のトランザクションの妥当性を確認した後でコンテンツをオブジェクトに書き戻す、バッファリングされた書込みプロセスが提供される（段階２４４）。複数のトランザクションがコミットされる順序が複数のトランザクションの抽象的直列化順序に一致することを保証する、トランザクション順序付けプロセスが提供される（段階２４６）。バッファリングされた書込みプロセスおよび／またはトランザクション順序付けプロセスを提供することにより、一部の私有化関連問題を回避することができる（段階２４８）。本プロセスは、終了点２５０で終了する。
【００２３】
図４は、バッファリングされた書込みをソフトウェアトランザクショナルメモリシステムで使用するのに必要とされる高度な段階の一実施形態を図示している。一形態では、図４のプロセスは、コンピューティング装置１００のオペレーティングロジックで少なくとも部分的に実装される。本プロセスは、開始点２６０で始まり、複数のトランザクションを管理するように動作可能なソフトウェアトランザクショナルメモリシステムを提供する（段階２６２）。特定のトランザクションについて書込みロックが最初に取得されると、特定のオブジェクトのシャドウコピーが作成される（段階２６４）。シャドウコピーへの書込みと該シャドウコピーからの読込みが行われる（段階２６６）。下記は、シャドウコピーを使用する一実施形態において、どのように読込みが行われるかについての説明であるが、他の読込みおよび書込みのバリエーションを使用することもできよう。読込みが、書込みロックされていない（non-write-locked）オブジェクトから行われる場合は、読込みは該オブジェクトから直接行われる。オブジェクトが書込みロックされている場合は、（例えば、トランザクショナルメモリワード内の）該ロックは、何らかのトランザクションのログ内のシャドウコピーをポイントする。該シャドウコピーが何らかの他のトランザクションのログ内にある場合は、衝突が起こるため、何らかの競合管理アクション（contention management action）を取る必要がある。該ログが現在のトランザクションのログの場合は、読込みは、現在のトランザクションがポイントしているシャドウコピーから行われる。コミット中に特定のトランザクションの妥当性を確認した後、コンテンツが、シャドウコピーから特定のオブジェクトに書き込まれる（段階２６８）。本プロセスは、終了点２７０で終了する。
【００２４】
図５は、バッファリングされた書込みをソフトウェアトランザクショナルメモリシステムで使用するのに必要とされるより詳細な段階の一実施形態を図示している。一形態では、図５のプロセスは、コンピューティング装置１００のオペレーティングロジックで少なくとも部分的に実装される。本プロセスは、開始点２８０で始まり、トランザクションを実行しているスレッドが、値ＶをオブジェクトＯ内のあるロケーションに書き込むことを試みる（段階２８１）。したがって、トランザクションは、オブジェクトＯの書込みロックを取ることを望む（段階２８２）。オブジェクトが書込みロックされていない場合は（判断点２８４）、書込みロックが取得され、トランザクションは、シャドウコピーを作成し、該シャドウコピーへのリファレンスを保持する（段階２８７）。オブジェクトが書込みロックされている場合（判断点２８４）、書込みロックが現在のトランザクションによって保持されているときは（判断点２８５）、該トランザクションは、それへのリファレンスを保持する（段階２８８）。これらのイベントのいずれにおいても、トランザクションは、値ＶをＯのシャドウコピーに書き込む（段階２９０）。しかし、オブジェクトが書込みロックされている場合（判断点２８４）、書込みロックが現在のトランザクションによって保持されておらず、代わりに別のトランザクションによって保持されているとき（判断点２８４）、競合管理アクションが取られる（段階２８６）。本プロセスは、終了点２９２で終了する。
【００２５】
図６は、トランザクショナルメモリワード内のバッファリングされた書込み情報をトラッキングするのに必要とされる段階の一実施形態を図示している。一形態では、図６のプロセスは、コンピューティング装置１００のオペレーティングロジックで少なくとも部分的に実装される。本プロセスは、開始点３１０で始まり、トランザクショナルメモリワードを特定のオブジェクトのオブジェクトヘッダ内に提供する（段階３１２）。図７でより詳細に説明されるように、ロックタイプおよびバージョンがトランザクショナルメモリワードを使用してトラッキングされる（段階３１４）。書込みロックされている状態では、トランザクショナルメモリワードは、シャドウコピーを含んでいる書込みログエントリへのポインタと、オブジェクトのベースアドレスへのポインタとを保持する（段階３１６）。シャドウコピーへの書込みと該シャドウコピーからの読込みが行われ、トランザクションの妥当性を確認した後、コミット処理においてシャドウコピーの値がオブジェクトに書き戻される（段階３１８）。本プロセスは、終了点３２０で終了する。
【００２６】
図７は、オブジェクトがトランザクションログ４０６を所有しているトランザクションによって書込みロックされていることを示す書込みログエントリ４０８へのリファレンスを保持している、トランザクショナルメモリワード（transactional memory word）４０４を図示している論理図である。書込みログエントリは、固定サイズのヘッダ４１０で始まり、該ヘッダ４１０は、書込みロックされる前のオブジェクトのＴＭＷの値である元のＴＭＷ４１２、およびオブジェクトベース４１４、書込みロックされたオブジェクトへ戻るポインタを含む。該ヘッダの後には、オブジェクトヘッダ４０２に続くオブジェクト４００のコンテンツで初期化されるシャドウコピー４１６が続く。トランザクションは、このシャドウコピーとの間で書込みと読込みを行い、トランザクションがコミットしたときにその更新されたコンテンツをオブジェクト４００に書き戻す。別の実施形態では、トランザクショナルメモリワードがシャドウコピーへの直接のポインタを含むことがあり、この場合、書込みログエントリの開始へのポインタを、一定であるヘッダのサイズを引くことによって回復することができる。トランザクショナルメモリワード４０４は、オブジェクト４００のオブジェクトヘッダ４０２にある。
【００２７】
オブジェクトが書込みロックされていないとき、トランザクショナルメモリワードは、バージョン番号、ならびにリーダ（readers）（例えば、悲観的リーダ）のリスト／カウントおよび／またはインジケータを含む。オブジェクトが書込みロックされているとき、トランザクショナルメモリワードの書込みロックエントリは、オブジェクトが書込みロックされる前に読み込んだＴＭＷ値を保持する。一実施形態では、リーダのリスト／カウントおよび／またはインジケータは、所与の時点で特定の値にアクセスしているリーダ（例えば、悲観的）の数のカウントを含む。別の実施形態では、リーダのリスト／カウントおよび／またはインジケータは、所与の時点で特定の値にアクセスしている特定のリーダ（例えば、悲観的）のリストを含む。さらに別の実施形態では、リーダのリスト／カウントおよび／またはインジケータは、単に、所与の時点で特定の値にアクセスしている１つまたは複数のリーダ（例えば、悲観的）が存在することを示すためのフラグまたは他のインジケータである。他のトランザクショナルメモリワードの属性および／またはそれらの組合せを代替または追加的に他の実施形態で使用して、並列処理制御の決定をするトランザクショナルメモリシステムによって使用するためにバージョン番号、書込みロックなどを示すことができることが認識されよう。
【００２８】
図８は、トランザクションが抽象的直列化順序と同じ順序でコミットすることを保証するのに必要とされる高度な段階の一実施形態を図示している。一形態では、図８のプロセスは、コンピューティング装置１００のオペレーティングロジックで少なくとも部分的に実装される。本プロセスは、開始点４２０で始まり、複数のトランザクションを管理するように動作可能なソフトウェアトランザクショナルメモリシステムを提供する（段階４２２）。コミット処理に入ったトランザクションの数を表す入力コミットカウンタが提供される（段階４２４）。コミット処理を終了したトランザクションの数を表す終了コミットカウンタが提供される（段階４２６）。特定のトランザクションは、コミット処理に入ると、入力コミットカウンタをアトミックに読み込み、インクリメントし、入力コミットカウンタから読み込まれた値を特定のトランザクションのチケット番号として割り当てる（段階４２８）。終了コミットカウンタが特定のトランザクションのチケット番号に一致するとき、特定のトランザクションはコミット処理を終了することを許可される（段階４３０）。本プロセスは終了点４３２で終了する。
【００２９】
図９は、トランザクションが抽象的直列化順序と同じ順序でコミットすることを保証するのに必要とされるより詳細な段階の一実施形態を図示している。一形態では、図９のプロセスは、コンピューティング装置１００のオペレーティングロジックで少なくとも部分的に実装される。本プロセスは、開始点４５０で始まり、トランザクションを開始する（段階４５２）。トランザクションは、読込みおよび書込みを行い、制御フローを実行する（段階４５３）。特定のトランザクションが読込みのみ（read-only）の場合は（判断点４５４）、読込みのみのトランザクションは、抽象的直列化順序と同じ順序でコミットを終了することに制限されず（段階４５６）、コミットすることができるかどうか確かめるために読込みの妥当性確認を続けることができる（段階４７１）。このとき、本プロセスは終了点４７２で終了する。
【００３０】
トランザクションが読込みのみでない場合（判断点４５４）、トランザクションは、抽象的直列化順序と同じ順序でコミットを終了するように制限されなければならない（段階４５８）。トランザクションは、グローバルな入力コミットカウンタをアトミックに読み込み、インクリメントして、入力コミットカウンタから読み込まれた値を特定のトランザクションのチケット番号として割り当てる（段階４６０）。トランザクションは、コミット処理を行う（段階４６４）。一実施形態では、コミット処理中に次のステップが実行される。すなわち、（１）楽観的読込みの妥当性を確認し、ロケーション読込みがまだ書込みロックされていないことと、ＴＭＷが初めに読み込まれたときと同じバージョン番号をそれらが保持することとを保証するステップと、（２）シャドウコピーを書き戻すステップである。トランザクションは、グローバルな終了コミットカウンタがローカルチケット番号に一致するときのみコミット処理を終了して、トランザクションは、終了コミットカウンタをインクリメントする（段階４６８）。トランザクションがコミット処理を終了した後に、書込みロックおよび悲観的読込みロックが外される（段階４７０）。本プロセスは、終了点４７２で終了する。
【００３１】
本主題を、構造的特徴および／または方法論的アクトに特有の言語で説明してきたが、添付の特許請求の範囲によって定義される本主題は、必ずしも上述の特有の特徴またはアクトに限定されないことを理解されたい。むしろ、上述の特有の特徴および行為は、特許請求の範囲を実装する例示的な形態として開示されている。本明細書で説明された実施形態および／または添付の特許請求の範囲の精神に含まれる均等な形態、変更形態、および修正形態は全て保護されることが望ましい。
【００３２】
例えば、コンピュータソフトウェア技術分野の当業者には、本明細書で議論された実施例で説明されたようなクライアントおよび／またはサーバ構成、ユーザインターフェーススクリーンコンテンツ、および／またはデータレイアウトを、１つまたは複数のコンピュータにおいて異なるように構成し、実施例で描写されたものより少ないまたは追加のオプションまたは特徴を含むこともできることが理解されよう。
【図１】
2010524133.tif 000003
【図２】
2010524133.tif 000004
【図３】
2010524133.tif 000005
【図４】
2010524133.tif 000006
【図５】
2010524133.tif 000007
【図６】
2010524133.tif 000008
【図７】
2010524133.tif 000009
【図８】
2010524133.tif 000010
【図９】
2010524133.tif 000011
【国際調査報告】
2010524133.tif 000012
2010524133.tif 000013