(57)【要約】  トランザクショナルメモリプログラミングインターフェースにより、スレッドが、トランザクション内の１つまたは複数の共有メモリロケーションに、１つまたは複数の他の並行スレッドによるそれら同一のロケーションへのメモリアクセスを管理するために制御構造を保持しながら、直接におよび安全にアクセスすることが可能になる。スレッドによりアクセスされる各メモリロケーションは登録レコードに関連付けられ、各スレッドはそのメモリアクセスのトランザクションログを保持する。何らかの中間バッファとは対照的に、トランザクション内で、読込操作がメモリロケーションに直接実行され、書込操作がメモリロケーションに直接試みられる。スレッドは、メモリロケーションの登録レコードとスレッドのトランザクションログの間の不一致を検知し、それによりトランザクション内のメモリアクセスが信頼できずトランザクションが再試行されるべきかを判定できる。
2009506403.tif 000002
【特許請求の範囲】
【請求項１】
第１のスレッドのトランザクション内の前記第１のスレッドおよび第２のスレッドによりアクセス可能な共有メモリロケーションへのメモリアクセスを管理する方法であって、
前記共有メモリロケーションに関連付けられる登録レコードを識別するステップと、
前記登録レコードが前記第２のスレッドによる前記共有メモリロケーションへの書込メモリアクセスと競合してないことを示している場合、前記トランザクションについて前記共有メモリロケーションを確保するために、前記登録レコードをマーキングするステップと、
取消ログ内の前記共有メモリロケーションへの参照およびその内容を記録するステップと
を備えたことを特徴とする方法。
【請求項２】
前記マーキング操作に応じて、前記トランザクション内で前記共有メモリロケーションへの書込メモリアクセスを実行するステップ
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項３】
前記マーキング操作は、
前記登録レコードにトランザクション識別子を書込むステップを含み、前記トランザクション識別子は、前記第１のスレッドの前記トランザクションを識別することを特徴とする請求項１に記載の方法。
【請求項４】
前記登録レコードが第２のスレッドによりマークされる場合、前記登録レコードは、前記第２のスレッドによる前記共有メモリロケーションへの書込メモリアクセスによる競合を示していることを特徴とする請求項１に記載の方法。
【請求項５】
前記取消ログは、順序付けられた一連の共有メモリロケーションの参照および関連する内容を含み、
前記内容を前記関連する共有メモリロケーションに書込ステップをさらに備え、個々の書込アクセスは逆の順序で前記シーケンス内で実行される
ことを特徴とする請求項１に記載の方法。
【請求項６】
前記登録レコードの参照を含むトランザクションログ項目を記録するステップをさらに備え、前記トランザクションログ項目は、前記トランザクション内の複数の書込メモリアクセスのトランザクションログ項目を含むトランザクションログ内に記録されることを特徴とする請求項１に記載の方法。
【請求項７】
前記登録レコードが前記第２のスレッドによる前記共有メモリロケーションへの書込メモリアクセスによる競合を示している場合、前記競合を解決することによって前記第１のスレッドの前記トランザクション内で前記共有メモリロケーションへの書込メモリアクセスを可能にするステップ
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項８】
前記トランザクションの終了時に前記共有メモリロケーションの前記登録レコードへ新しいバージョンの値を書込むステップ
をさらに備えたことを特徴とする請求項１に記載の方法。
【請求項９】
前記登録レコードはバージョンフィールドを含み、前記マーキング操作は、
スクラッチフィールドに前記バージョンフィールドの内容を記録するステップと、
前記バージョンフィールド内にトランザクション識別子を書込むステップと
を備えたことを特徴とする請求項１に記載の方法。
【請求項１０】
請求項１に記載の方法を実装するコンピュータ処理を実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読み取り可能な媒体。
【請求項１１】
第１のスレッドのトランザクション内の前記第１のスレッドおよび第２のスレッドによりアクセス可能な共有メモリロケーションへのメモリアクセスを管理する方法であって、
前記共有メモリロケーションに関連付けられる登録レコードを識別するステップと、
前記トランザクションに関連付けられ、前記共有メモリロケーションに関連付けられる前記登録レコードへの参照を持つトランザクションログ項目を生成するステップと、
前記第１のスレッドによる前記トランザクション内の前記共有メモリロケーションへの前記読込メモリアクセスを実行するステップと、
前記トランザクションログ項目および前記参照された登録レコードが、前記第２のスレッドによる前記共有メモリロケーションへの書込メモリアクセスによる競合を示していない場合、前記実行処理に応じて、前記読込メモリアクセスの前記トランザクションをコミットするステップと
を備えたことを特徴とする方法。
【請求項１２】
前記登録レコードはバージョンフィールドを含み、
前記実行処理に先立ち、前記登録レコードの前記バージョンフィールドの内容を読み込むステップと、
前記内容が前記第１のスレッドのトランザクション識別子を表す場合、前記登録レコードに対する前記トランザクションログ項目が前記トランザクション内で既に生成されていると認識するステップと
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１３】
前記登録レコードはバージョンフィールドを含み、
前記実行処理に先立ち、前記登録レコードの前記バージョンフィールドの内容を読み込むステップと、
前記内容が前記第２のスレッドのトランザクション識別子を表す場合、前記トランザクションを異常終了させるステップと
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１４】
前記登録レコードはバージョンフィールドを含み、
前記実行処理に先立ち、前記登録レコードの前記バージョンフィールドの内容を読み込むステップと、
前記内容がバージョンの値を表す場合、前記トランザクションログ項目内の前記バージョンの値を記録するステップと
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１５】
前記トランザクションログ項目内に記録されたバージョンの値がコミット時に前記登録レコード内に記録されたバージョンの値と合致しない場合、前記第２のスレッドによる前記共有メモリロケーションへの書込メモリアクセスによる競合であると識別するステップをさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１６】
競合であると識別される場合、前記トランザクションを異常終了するステップをさらに備えたことを特徴とする請求項１５に記載の方法。
【請求項１７】
前記登録レコードはバージョンフィールドを含み、
前記登録レコードに関連付けられるスクラッチフィールドから、前記登録レコードの前記バージョンフィールド内に予め格納されたバージョンの値を読込むステップと、
前記トランザクションログ項目内に記録されたバージョンの値がコミット時に前記スクラッチフィールド内に記録された前記バージョンの値と合致しない場合、前記第２のスレッドによる前記共有メモリロケーションへの書込メモリアクセスによる競合であると識別するステップと
をさらに備えたことを特徴とする請求項１１に記載の方法。
【請求項１８】
請求項１１に記載の方法を実装するコンピュータ処理を実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読み取り可能な媒体。
【請求項１９】
第１のスレッドのトランザクション内の前記第１のスレッドおよび第２のスレッドによりアクセス可能な共有メモリロケーションへのメモリアクセスを管理する方法であって、
前記トランザクション内に前記共有メモリロケーションを登録するステップと、
前記トランザクションに関連付けられるトランザクションログ項目を含むトランザクションログおよび各共有メモリロケーションに対する登録レコードを維持するステップと、
前記共有メモリロケーションへの書込メモリアクセスの項目を含む取り消しログを維持するステップであって、前記項目の各々は、前記書込メモリアクセスの共有メモリロケーションに関連付けられるアドレスおよび前記共有メモリロケーションの前の内容を含むステップと、
前記共有メモリロケーションへメモリアクセスを直接実行するステップと、
前記第２のスレッドによる前記共有メモリロケーションへの書込メモリアクセスによる競合が検知されない場合、前記実行処理に応じて、前記メモリアクセスの前記トランザクションをコミットするステップと
を備えたことを特徴とする方法。
【請求項２０】
請求項１９に記載の方法を実装するコンピュータ処理を実行するコンピュータ実行可能命令を有することを特徴とするコンピュータ読み取り可能媒体。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般的にコンピュータメモリ操作に関し、詳細には直接更新ソフトウェアトランザクショナルメモリに関する。
【背景技術】
【０００２】
マルチスレッド処理の複数のスレッドが並行して実行される間、一般的に共通メモリロケーションを共有する。したがって、マルチスレッド化されたプログラムの２つの異なるスレッドは、そのプログラムによりアクセス可能な同一のメモリロケーションを読み込みおよび更新する可能性がある。しかし、１つのスレッドは、他のスレッドが共有メモリロケーションの値に依存する一連の操作の最中である間は、その値を修正しないことを保証することに注意をしなければならない。
【０００３】
例えば、プログラムが２つの異なるソフトウェアオブジェクトのコンテンツにアクセスしており、各オブジェクトが異なる銀行口座の預金高を表すとする。最初に、第１の口座の額が１０ドルであり、メモリアドレスＡ１に格納され、一方第２の口座の額が２００ドルであり、メモリアドレスＡ２に格納されている。銀行業務プログラムの第１のスレッドが、１００ドルをＡ２からＡ１に振り替えるようにコーディングされ、第２のスレッドが、両方の口座の預金額計を計算するようにコーディングされている。第１のスレッドは、１００ドルをＡ１の内容に加算し、Ａ１を１１０ドルに更新することにより開始し、次に１００ドルをＡ２の内容から減算することに進み、Ａ２を１００ドルに更新してよい。しかし、第２のスレッドがこれら２つの操作の間で実行する場合、第２のスレッドは、２つの口座に対して、２１０ドルという正しい合計ではなく、３１０ドルという正しくない合計を計算する恐れがある。
【０００４】
ソフトウェアトランザクショナルメモリは、スレッドが一連の共有メモリアクセスを安全に実行でき、そのスレッドがそのトランザクションを他のスレッドからの干渉なしに完了することができるプログラミング抽象（ｐｒｏｇｒａｍｍｉｎｇ  ａｂｓｔｒａｃｔｉｏｎ）を提供する。したがって、第１のスレッドの例示の加算および減算の操作を含むトランザクションは、メモリロケーションＡ１およびＡ２について「アトミック」であり、その結果第２のスレッドが２つの口座の正しい合計額を確実に計算するために、トランザクショナルメモリをソフトウェア内で使用することが可能である。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
しかし、トランザクショナルメモリをソフトウェア内で実装する既存の方法は、性能の点で問題である。例えば、ある既存の方法では、スレッドが一連のメモリロケーションにトランザクションにおいてアクセスするときに、そのスレッドは、そのトランザクションの間に読み込みおよび更新（すなわち、書き込み）を行いたいメモリロケーションおよび値の別のリストを保持し、その後トランザクションの最後に、そのスレッドは実際の共有メモリロケーションのこれらの値のすべてを更新する。トランザクションの間に、そのスレッドがそのリスト内の任意のメモリロケーションに再読み込みまたは再書き込みをしたい場合、そのスレッドは、リスト内のメモリロケーションの項目を探して、その項目にアクセスしなければならず、これはプログラムで実行すると遅くなる。したがって、ソフトウェア内でトランザクショナルメモリを実装する、このような間接的な方法は、性能が低いという問題になる。
【課題を解決するための手段】
【０００６】
本明細書で説明し請求する実装により、スレッドが、トランザクション内の１つまたは複数の共有メモリロケーションに、１つまたは複数の他の並行スレッドによるそれら同一のロケーションへのメモリアクセスを管理するために制御構造を保持しながら、直接におよび安全にアクセスすることを可能にするトランザクショナルメモリプログラミングインターフェースが提供されることにより上述の問題が解決する。スレッドによりアクセスされる各メモリロケーションは登録レコードに関連付けられ、各スレッドはそのメモリアクセスのトランザクションログを保持する。中間バッファとは対照的に、トランザクション内で、読み込み操作がメモリロケーションで直接実行され、書き込み操作がメモリロケーションに直接試みられる。スレッドがメモリロケーションの登録レコードとそのトランザクションログの間の不一致を検知する場合、スレッドは、トランザクション内のメモリアクセスが信頼できずトランザクションが再試行されるべきであると判定する。さらに、スレッドがトランザクション内のメモリロケーションに書き込みを試み、他のスレッドが他の未完了のトランザクション内のメモリロケーションを既に更新していると判定する場合、第１のスレッドは、待機してトランザクションを後で再試行、または他方のスレッドとの競合を解決することを試みることができる。加えて、スレッドは、トランザクションが異常終了する場合、スレッドがこれらの操作の取消しを可能にするために、元の値およびそのロケーションのアドレスを含むその書き込みメモリアクセスの取り消しログをトランザクションの間保持することができる。
【０００７】
実装によっては、コンピュータプログラムの製品が提供される。コンピュータプログラムの製品の実装としては、コンピュータシステムにより読み取り可能でコンピュータプログラムを符号化するコンピュータプログラムの記憶媒体がある。コンピュータプログラムの製品の他の実装としては、コンピューティングシステムにより搬送波で実現され、コンピュータプログラムを符号化するコンピュータデータ信号を提供することができる。
【０００８】
更に他の実装も本明細書で説明する。
【発明を実施するための最良の形態】
【０００９】
図１は、例示の直接更新ソフトウェアトランザクショナルメモリインターフェース１０８および１１０（例えば、アプリケーションプログラミングインターフェースまたはＡＰＩ）を介して共有メモリロケーション１０４および１０６にアクセスする２つの並行スレッド１００および１０２を示す。スレッド１００は例えば、銀行口座の振替（報告１１２となる）の計算を表し、スレッド１０２は例えば、２つの銀行口座の合計（報告１１４となる）の計算を表す。共有メモリロケーション１０４（Ａｌ）および１０６（Ａ２）は、共用メモリ領域１１６に常駐し、初期値がそれぞれ１０ドルおよび２００ドルである２つの別の口座の預金高を表す値を格納する。
【００１０】
各共有メモリロケーションは、システム内のメモリアドレスの値（例えば、配列、リスト、テーブル、ソフトウェアオブジェクト等）に関連付けることが可能である。ｅ−ｒｅｃ１１８またはｅ−ｒｅｃ１２０などの登録レコード（ｅｎｌｉｓｔｍｅｎｔ  ｒｅｃｏｒｄ）は、直接更新ソフトウェアトランザクショナルメモリアクセスのための制御構造として働き、各メモリロケーションに関連付けられる。登録レコードは、様々な方法でメモリロケーションに関連付けられることができ、ある登録レコードは各メモリロケーションに、ある登録レコードは各ソフトウェアオブジェクトに、またはある登録レコードはプロセスの仮想アドレス空間内のページなどのメモリロケーションのブロックに関連付けられることができる。一実装では、登録レコードは、バージョンフィールドおよびスクラッチフィールドの２つのフィールドを有するが、バージョンフィールドはトランザクション識別子も保持することができる。他の実装では、登録レコードが有するのは単一のバージョンフィールドだが、このバージョンフィールドはトランザクション識別子またはトランザクションログのポインタも保持することができる。他の登録レコードの構造も考えられる。
【００１１】
図示の例では、スレッド１００は、単一のトランザクション内に、メモリアドレス１０４に対応する第１の口座からメモリロケーション１０６に対応する第２の口座へ１００ドルを振り替える少なくとも２つのアトミック操作を含む。第１の操作は、メモリロケーション１０４に対応する値に１００を加算し、第２の操作はメモリロケーション１０６に対応する値から１００を減算して、それにより振替を行う。並行スレッド１０２は、トランザクション内に、両方の口座の金額を合計するアトミック操作を含む。
【００１２】
各トランザクションに対して安全なメモリアクセスを保証するために、スレッド１００および１０２は、ＡＰＩ１０８および１１０を用いて共有メモリロケーション１０４および１０６にアクセスする。スレッドは、ＡＰＩを通してメモリロケーションに直接トランザクション内の読込操作を実行し、トランザクションが完了すると、スレッドがそのトランザクションの結果を信頼できるか否かを示す信号を受信する。同様に、他のスレッドが書き込み操作を共有メモリロケーションにまだマークしていなかった場合、スレッドはＡＰＩを介して共有メモリロケーションに直接トランザクション内の書込操作を実行する。
【００１３】
各スレッドは、トランザクションログ（例えば、トランザクションログ１２２またはトランザクションログ１２４）を保持し、それによりその直接更新トランザクショナルメモリアクセスを管理する。一実装では、トランザクションログは、１つは読み込み用であり１つは更新用である２つのコンポーネントリストを有する。代替の実装では、トランザクションログの有するリストは１つであり、リスト項目は「読込」または「更新」としてパラメータ化されている。各トランザクションログは状態フィールドも含み、このフィールドはＡＣＴＩＶＥ（処理中）、ＡＢＯＲＴＥＤ（異常終了）、またはＣＯＭＭＩＴＴＥＤ（コミット終了）を示す値を保持する。個々のリスト項目は、関連したメモリアドレスの登録レコードへのポインタ（例えば、参照）を含み、バージョンの値も含んでよい。代替の実装では、リスト項目は、スクラッチフィールドも含んでよい。他のデータ構造では、取消ログと呼ばれるが、トランザクション内で更新されたメモリアドレスおよびその前の値（すなわち、メモリロケーションが更新される以前）のリストを保持する。また他の実装では、トランザクションログおよび更新ログの機能を組み合わせた単一のログが用いられ、リスト項目は「読込」、「更新」（または「書込」）、あるいは「取消」項目としてパラメータ化されている。
【００１４】
各トランザクションは、所与のトランザクションのメモリ書込アクセスを取消ために使用可能な取り消しログ（１２６および１２８）も保持する。一実装では、取り消しログは、トランザクションの各書き込みアクセスに関連する元の値およびメモリアドレスを記録する。この方法で、トランザクションが異常終了する場合、取消ログ内の項目が逆の順番で実行され、それによりトランザクションにより書込まれた共有メモリロケーションをそれ以前のトランザクションの状態に復元できる。
【００１５】
ＡＰＩ１０８および１１０に指定されたプロトコルに従うことにより、スレッド１００および１０２は、個々のトランザクション内の共有メモリロケーションへの一連のメモリアクセスを他のスレッドにより検知されない場合の衝突のリスクなしに安全に実行できる。
【００１６】
図２は、トランザクション内の一連のメモリアクセスを例示の直接更新ソフトウェアトランザクショナルメモリインターフェースを介して実行する操作２００を示す。操作２００は、１つまたは複数の共有メモリロケーションにアクセスする個々のスレッドによりＡＰＩを介して行われる一連の呼び出しを表す。例えば共有メモリロケーションは、個々の銀行口座に対するソフトウェアオブジェクトに対応してよい。各共有メモリロケーションは、対応するソフトウェアオブジェクトの作成の際にメモリアドレスおよび登録レコードに関連付けられる。
【００１７】
初期化操作２０２は、スレッドのための新しいトランザクションを初期化する。一実装では、初期化操作２０２は、例示の直接更新ソフトウェアトランザクショナルメモリインターフェース内で「ＴｒａｎｓａｃｔｉｏｎＳｔａｒｔ（）」操作により表され、新しいトランザクションのためのトランザクションログを割り当てて初期化する。トランザクションログは、スレッドによりアクセス可能なローカル（すなわち、非共有）メモリ内に保持される。初期化時に、スレッドのためのトランザクションログは空となり、その状態はＡＣＴＩＶＥ（処理中）に設定される。一実装では、初期化操作２０２は、そのトランザクションに関連付けられる新しい取消ログの割り当ても行って初期化する。
【００１８】
登録操作２０４は、読込操作または書込操作などのメモリアクセス操作について指定されたメモリロケーションを登録する。一実装では、登録操作２０４は、例示の直接更新ソフトウェアトランザクショナルメモリインターフェース内で「ＥｎｌｉｓｔＡｄｄｒＦｏｒＲｅａｄ（Ａｄｄｒ  ｒ）」操作により表され、この操作でＡｄｄｒ  ｒは指定されたメモリロケーションのアドレスを表す。他の実装では、登録操作２０４は、例示の直接更新ソフトウェアトランザクショナルメモリインターフェース内で「ＥｎｌｉｓｔＡｄｄｒＦｏｒＷｒｉｔｅ（Ａｄｄｒ  ｒ）」操作により表され、この操作でアドレス（Ａｄｄｒ）ｒは指定されたメモリロケーションのアドレスを表す。登録操作のより詳細な説明が以下で行う。
【００１９】
アクセス操作２０６は、例えば、読込操作または書込操作によって、指定されたメモリロケーションへのメモリアクセスを行う。一実装では、アクセス操作２０６は、指定されたメモリロケーションへの直接読込により表される。他の実装では、アクセス操作２０６は、例示の直接更新ソフトウェアトランザクショナルメモリインターフェース内で「ＴｒａｎｓａｃｔｉｏｎＲｅａｄ（Ａｄｄｒ  ｒ）」操作により表され、この操作でＡｄｄｒ  ｒは指定されたメモリロケーションのアドレスを表し、この操作は指定されたメモリロケーションから直接値を読込む。さらに別の実装では、アクセス操作２０６は、指定されたメモリロケーションへの直接書込により表される。この実装では、別のＵｐｄａｔｅＵｎｄｏ（Ａｄｄｒ  ｒ）も用いて（上述のように）取消ログを更新してよい。さらに別の実装では、アクセス操作２０６は、例示の直接更新ソフトウェアトランザクショナルメモリインターフェース内で「ＴｒａｎｓａｃｔｉｏｎＷｒｉｔｅ（Ａｄｄｒ  ｒ、Ｖａｌｕｅ  ｖ）」操作により表され、この操作でＡｄｄｒ  ｒは指定されたメモリロケーションのアドレスを表し、及びＶａｌｕｅ  ｖはメモリロケーションに書き込まれるべき値を表しており、この操作により、取消ログに項目が追加される。
【００２０】
決定操作２０８は、他のメモリアクセス操作がトランザクションのシーケンス内に残っているかを判定する。操作が残っており、トランザクションが次のメモリアクセス操作の指定されたメモリロケーションにまだアクセスしていなかった場合、処理は登録操作２０４に進む。別の方法として、指定されたメモリロケーションが現在のトランザクション内に既に登録されているため、処理は登録操作２０４を迂回するように処理させることもできる。
【００２１】
いずれにしても、処理は、それ以上メモリアクセス操作がトランザクションのシーケンス内に残っていないようになるまで、トランザクションのシーケンス内の各メモリアクセスを一ステップずつ実行し、残り操作がなくなるとコミット操作２１０がトランザクションのコミットを試みる。一実装では、コミット操作２１０は、例示の直接更新ソフトウェアトランザクショナルメモリインターフェース内で「ＴｒａｎｓａｃｔｉｏｎＣｏｍｍｉｔ（）」操作により表される。概して、コミット操作２１０は、トランザクション内のメモリ読込操作のすべてが他のスレッドが衝突するような更新なしにトランザクション内で完了されたかを判定する。コミット操作２１０が失敗する場合、スレッドは、トランザクションが失敗と判定し、適切な場合にはトランザクション全体を再実行する。コミット操作２１０が成功する場合、スレッドは、トランザクションが成功裡に完了しており、スレッドがトランザクションの結果（例えば、読み込んだ値および更新操作）を信頼できると判定する。完了時に、コミット操作２１０は、トランザクションの登録を「解体（ｓｔａｎｄ  ｄｏｗｎ）」し、その結果関連したメモリロケーションは他のスレッドがアクセスできるようになる。一実装では、この解体は、関連した登録レコードのそれぞれに対してトランザクションログ内の書込トランザクション項目を全部繰り返し、更新したメモリロケーションの登録レコードのバージョンフィールド内に新しいバージョン番号（例えば、バージョン番号をインクリメントする）を格納することにより実行される。
【００２２】
バージョン番号を超過する可能性がある（例えば、バージョンフィールド内の利用可能な番号のすべてが時間を超過して使用された可能性がある）。例えば、バージョンが各更新で１ずつインクリメントされ（例えば、０、１、２、３、など）、最終的に最大のバージョン番号「Ｎ」を超える場合、「再利用（ｒｏｌｌｏｖｅｒ）」またはその他の方法でバージョン番号のオーバーフローを処理する仕組みが適切である可能性がある。一実装では、時間超過して実行されたトランザクションの個数がＮを超える場合、その時点で実行中のトランザクションは異常終了することができる。または、時間を超過して実行されたトランザクションの個数がＮを超える場合、その時点で実行中のトランザクションは部分的にコミットされ、その結果無効なトランザクションは異常終了され、有効なトランザクションは処理を続けてよい。また別の実装では、妥当な処理がＮを超えることがまったくないほどの大きさにＮの大きさを設定することができる。
【００２３】
異常終了操作は、例示の直接更新ソフトウェアトランザクショナルメモリインターフェース内でＴｒａｎｓａｃｔｉｏｎＡｂｏｒｔ（）操作とすることができるが、現在のスレッドに関連付けられる現在のトランザクションを破棄し、異常終了イベントに先立ちトランザクション内で実行されたいかなる更新も巻き戻す。一実装では、現在のトランザクションログ内の状態フィールドは、ＡＢＯＲＴＥＤ（異常終了）に設定され、取り消しログ内の項目は、逆に実行され、更新されたメモリロケーションの前のトランザクションの値を復元する。異常終了したトランザクションの更新が取消されると、異常終了操作は登録を「解体」する。
【００２４】
図３は、トランザクション内のメモリロケーション上に読込操作を登録する例示の操作３００を示す。所与のメモリアドレスｒに対する登録読込操作（図２に関する説明を参照されたい）へのスレッドによる呼び出しに応じて、位置指定操作３０２が、メモリアドレスｒに関連付けられる登録レコード（すなわち、「ｅ−ｒｅｃ」）を位置指定する。一実装では、登録レコードは、メモリアドレスｒに関連付けられるデータ構造（例えば、メモリアドレスｒのソフトウェアオブジェクトの一部としてまたはそのソフトウェアオブジェクトにより参照されるもの）である。
【００２５】
バージョン操作３０４は、位置指定された登録レコードからメモリアドレスに関連付けられたバージョンの値を読込む。決定操作３０６は、読込んだバージョンの値が実際にバージョンを表すか、現在のトランザクションを示す識別子を表すか、または他のトランザクションを示す識別子を表すかを判定する。読込バージョンの値が実際のバージョンを表す場合、ログ記録操作３０８は、バージョンおよび位置指定された登録レコードへのポインタ（例えば、参照）をトランザクションログの読み込みトランザクションリスト（例えば、リンクリスト）内の項目に加える。次にスレッドは、メモリアドレスの値の直接読込みに進むことができる。
【００２６】
読込んだバージョンの値が現在のトランザクションによりメモリアドレスの登録レコードに書き込まれた識別子を表す場合、トランザクションログは現在のトランザクション内の書き込み操作により既に更新されており、スレッドは（継続操作３１０によって示されるように）単にメモリアドレスの値を直接読み込み続けることができる。読み込み続けることにより、スレッドは、登録レコードに対するトランザクションログの項目が既にトランザクションのトランザクションログ内に生成されたことを認識している。トランザクションの識別子は、任意の一意なトランザクション識別子、トランザクションログ内のスクラッチフィールドへ戻るポインタ（例えば、参照）、または何らかの他の一意の識別子であってよい。
【００２７】
読込まれたバージョンの値が他のトランザクションによりメモリアドレスの登録レコードに書込まれた識別子を表す場合、トランザクションログは他方のトランザクションの書き込み操作により既に更新されており、スレッドは解決操作３１２を呼び出し、登録を再試行する。一実装では、例示の解決操作３１２は、実際にはノーオペレーション（ｎｏ−ｏｐ）命令であり、この命令は、登録操作をスピンウェイトさせることになる。または、相互排除のロックを、スピニングを回避するために登録レコードに関連付けることができる。また他の代替の実装では、各トランザクションログは、取り消し可能なロックに関連付けられることが可能である。この実装では、後にアクセスするトランザクション（Ｔ２）の解決操作が取消可能なロックを前のトランザクション（Ｔｌ）から取得できる。取り消し可能なロックで、Ｔ２はＴｒａｎｓａｃｔｉｏｎＡｂｏｒｔ（）をＴ１の代わりに実行してＴ１の取消可能なロックを解除することができる。それ以降、Ｔ２は、メモリアドレスｒをその読込操作に対して再登録でき、Ｔ１は、例外を上げてそれによりＴ１が異常終了しており処理の適切な時点で再起動される必要があることを示すことができる復元機能に取って代わられることができる。
【００２８】
代替の実装では、ＥｎｌｉｓｔＡｄｄｒＦｏｒＲｅａｄ（）操作は読込んだバージョンの値に関する決定操作３０６を省略し、単に登録レコード内のバージョンフィールドの内容がバージョンであると仮定する。この実装では、ＴｒａｎｓａｃｔｉｏｎＣｏｍｍｉｔ（）操作は、競合がバージョン競合によるものであろうと、または他のスレッドの書き込みアクセスによる共有メモリロケーションの確保によるものであろうと、共有メモリロケーション内のいかなる競合も把握する。
【００２９】
図４は、トランザクション内のメモリロケーション上に書込操作を登録する例示の操作４００を示す。所与のメモリアドレスｒに対する登録書込操作（図２に関する説明を参照されたい）へのスレッドによる呼び出しに応じて、位置指定操作４０２が、メモリアドレスｒに関連付けられる登録レコード（すなわち、「ｅ−ｒｅｃ」）を位置指定する。一実装では、登録レコードは、メモリアドレスｒに関連付けられる（例えば、メモリアドレスのソフトウェアオブジェクトの一部としてまたはそのソフトウェアオブジェクトにより参照されるものとして）データ構造である。
【００３０】
バージョン操作４０４は、位置指定された登録レコードからメモリアドレスに関連付けられたバージョンの値を読込む。決定操作４０６は、読込んだバージョンの値が実際にバージョンを表すか、現在のトランザクションを示す識別子を表すか、または他のトランザクションを示す識別子を表すかを判定する。読込バージョンの値が実際のバージョンを表す場合、ログ記録操作４０８は、バージョンおよび位置指定された登録レコードへのポインタ（例えば、参照）をトランザクションログの書込トランザクションリスト（例えば、リンクリスト）内の項目に加える。マーキング操作４１０は、アトミックなコンペアアンドスワップ操作を用いてメモリアドレスｒの登録レコードのバージョンフィールド内に現在のトランザクションを指定するマークを設定し、それにより現在のトランザクションのためにメモリアドレスｒ（および関連したメモリロケーション、メモリロケーションの範囲、オブジェクト等）を一時的に確保する。コンペアアンドスワップ操作が成功する場合（決定操作４１２により判定されるように）、トランザクションログ内の書き込みトランザクションリストに保存されたバージョンの値が登録レコードのスクラッチフィールドに書き込まれ、次にスレッドはメモリアドレスの値の直接更新に進むことができる。一方、コンペアアンドスワップ操作が失敗する場合、バージョンおよび位置指定された登録レコードへのポインタ（例えば、参照）はトランザクションログ内の書き込みトランザクションリストから削除され、登録が位置指定操作４０２で再び試みられる。
【００３１】
一実装では、スクラッチフィールドは、登録レコードではなくトランザクション項目内に含まれてよい。この実装では、登録レコードのバージョンフィールド内のトランザクション識別子は、トランザクション項目へのポインタ（例えば、参照）である。この方法で、高速コンペアアンドスワップ操作を使用することができ、バージョンスクラッチは、トランザクション内の更新されたメモリロケーションのためだけにローカルの非共有メモリに格納される。
【００３２】
読込んだバージョンの値が現在のトランザクションによりメモリアドレスの登録レコードに書込まれた識別子を表す場合、トランザクションログは現在のトランザクション内の書込操作により既に更新されており、スレッドは（継続操作４１６によって示されるように）単にメモリアドレスの値を直接更新し続けることができる。読み込まれたバージョンの値が他のトランザクションによりメモリアドレスの登録レコードに書き込まれた識別子を表す場合、トランザクションログは他方のトランザクションの書き込み操作により既に更新されている。したがって、スレッドは解決操作４１８を呼び出して登録を再試行する。解決操作４１８に関しては、例示の解決操作が既に説明されている。
【００３３】
図５は、直接更新ソフトウェアトランザクショナルメモリインターフェース内のトランザクションをコミットする例示の操作５００を示す。ログ項目操作５０２は、ポインタ（例えば、参照）をトランザクションログの読み込みトランザクションリスト内の項目から読み込む。このポインタを使って、登録レコード操作５０４は、メモリアドレスに関連付けられる登録レコードのバージョンフィールドを読み込む。決定操作５０６は、バージョンフィールドから読み込まれた値が実際にバージョンを表すか、現在のトランザクションを示すマークを表すか、または他のトランザクションを示すマークを表すかを判定する。
【００３４】
バージョンフィールドから読み込まれた値が実際にバージョンである場合、読み込み操作５０８は、その項目からポインタ（例えば、参照）がログ項目操作５０２で読み込まれたトランザクションログ項目からバージョンを読み込む。２つのバージョンが合致する場合（決定操作５１０により判定されるように）、現在のログ項目に関連付けられるメモリアドレスはトランザクションの間他のスレッドにより更新されなかったため、スレッドは、引き続き成功裡に終了することができる。これが読込トランザクションリスト内のログ項目のすべてにあてはまる場合、現在のトランザクション内でそのメモリアドレスへのすべての読み込みは有効であり、トランザクションは有効である可能性がある。
【００３５】
決定操作５１２は、次のトランザクションログ項目が読み込みトランザクションリストに存在するかを判定する。存在する場合、処理はログ項目操作５０２に進む。その他の場合、成功操作５１４がコミット操作からの成功を信号で伝え、現在のトランザクションログの状態をＣＯＭＭＩＴＴＥＤ（コミット終了）に設定する。バージョン操作５２０が、書き込みトランザクションリスト項目に関連付けられるすべての登録レコードのバージョンの値を更新し、それによりトランザクションがそのメモリロケーションと関連して成功裡に終了したことを示す。終了操作５２２により、すべてのトランザクションログ項目をトランザクションログから削除し、トランザクションログ自体を削除する。
【００３６】
決定操作５１０により、バージョンが合致しないと判定された場合、この不一致は、メモリアドレスが現在のトランザクションの間に他のスレッドにより更新されたため、メモリロケーションへの読込が有効でないことを示す。この場合、処理は失敗操作５１８に進み、この操作はコミット操作の失敗を信号で伝える。さらに、異常終了操作は、上述のようにトランザクションを異常終了させる。
【００３７】
決定操作５０６が登録レコードのバージョンフィールドから読込んだ値が実際に現在のトランザクションを示す識別子を表していると判定する場合、読込操作５１６により、スクラッチフィールドからバージョンの値を読込む。一実装では、スクラッチフィールドは、メモリアドレスの登録レコードの一部である。別の実装では、スクラッチフィールドは、トランザクションログの項目内に格納される。次に処理は読込操作５０８および決定オペレーショ５１０に進み、スクラッチフィールドからのバージョンをトランザクションログ内のバージョンと比較する。
【００３８】
決定操作５０６により登録レコードのバージョンフィールドから読み込まれた値が実際に他のトランザクションを示す識別子を表すと判定された場合、メモリアドレスへの更新は、他の並行トランザクションの更新により排除される。したがって、失敗操作５１８はトランザクションの失敗を信号で伝える。さらに、異常終了操作は上述のようにトランザクションを異常終了させる。
【００３９】
本発明を実装する図６の例示のハードウェアおよびオペレーティング環境は、コンピュータ２０のような汎用コンピューティング装置を備え、コンピュータ２０は、処理装置２１、システムメモリ２２、およびシステムメモリを処理装置２１へ接続するなど、様々なシステム要素を動作可能なように接続するシステムバス２３を備える。コンピュータ２０のプロセッサは、単一の中央演算処理装置（ＣＰＵ）、または並列処理環境と通常呼ばれる複数の処理装置を備えるような、ただ１つの処理装置２１が存在してもよく、または１つより多い処理装置２１が存在してもよい。コンピュータ２０は、従来のコンピュータ、分散コンピュータ、または任意の他のタイプのコンピュータであってよく、本発明はそのような制限をうけることはない。
【００４０】
システムバス２３は、いくつかのタイプのバス構造のうちの任意のものでよく、これらのバス構造は、様々なバスアーキテクチャのうちの任意のものを用いるメモリバスまたはメモリコントローラ、周辺バス、スイッチファブリック、２地点間接続、およびローカルバスを含む。システムメモリは、単にメモリと呼ばれてもいいが、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）２４およびＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）２５を含む。ＢＩＯＳ（Ｂａｓｉｃ  Ｉｎｐｕｔ／Ｏｕｔｐｕｔ  Ｓｙｓｔｅｍ）２６は、起動中などにコンピュータ２０内の要素間で情報を移送することを支援する基本ルーチンを含み、ＲＯＭ２４に格納される。さらにコンピュータ２０は、ハードディスク（図示せず）から読取り、ハードディスクへ書き込むハードディスクドライブ２７、リムーバブル磁気ディスク２９から読取り、またはリムーバブル磁気ディスク２９へ書込む磁気ディスクドライブ２８、およびＣＤ  ＲＯＭまたは他の光学媒体などのリムーバブル光ディスク３１から読取り、またはリムーバブル光ディスク３１へ書込む光ディスクドライブ３０を含む。
【００４１】
ハードディスクドライブ２７、磁気ディスクドライブ２８、および光ディスクドライブ３０は、システムバス２３にそれぞれハードディスクドライブインターフェース３２、磁気ディスクドライブインターフェース３３、および光ディスクドライブインターフェース３４により接続される。ドライブおよびその関連したコンピュータ読み取り可能な媒体は、コンピュータ２０のためにコンピュータ読み取り可能な命令、データ構造、プログラムモジュールおよび他のデータの非揮発性の保存を行う。磁気カセット、フラッシュメモリカード、デジタルビデオディスク、ＲＡＭ（Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＲＯＭ（Ｒｅａｄ  Ｏｎｌｙ  Ｍｅｍｏｒｙ）などのような、コンピュータによりアクセス可能なデータを格納できる任意のタイプのコンピュータ読み取り可能な媒体は、例示のオペレーティング環境内で用いられてよいことを当業者は理解されたい。
【００４２】
オペレーティングシステム３５、１つまたは複数のアプリケーションプログラム３６、他のプログラムモジュール３７、およびプログラムデータ３８を含むいくつかのプログラムモジュールは、ハードディスク、磁気ディスク２９、光ディスク３１、ＲＯＭ２４、またはＲＡＭ２５上に格納できる。ユーザは、コマンドおよび情報をパーソナルコンピュータ２０にキーボード４０およびポインティングデバイス４２などの入力装置を介して入力できる。他の入力装置（図示せず）は、マイクロフォン、ジョイスティック、ゲームパッド、パラボラアンテナ、スキャナ等を含んでよい。これらのおよび他の入力装置は、処理装置２１に、システムバスに接続されるシリアルポートインターフェース４６を介して接続されることが多いが、パラレルポート、ゲームポート、またはユニバーサルシリアルバス（ＵＳＢ）などの他のインターフェースにより接続されてよい。モニタ４７または他のタイプのディスプレイ装置もシステムバス２３にビデオアダプタ４８などのインターフェースを介して接続される。モニタに加え、コンピュータは典型的にはスピーカおよびプリンタなどの他の周辺出力装置（図示せず）を含む。
【００４３】
コンピュータ２０は、リモートコンピュータ４９などの１つまたは複数のリモートコンピュータへの論理接続を用いてネットワーク環境で動作してよい。これらの論理接続は、コンピュータ２０に接続されるかまたはコンピュータ２０の一部である通信装置により実現され、本発明は特定のタイプの通信装置に限定されない。リモートコンピュータ４９は、他のコンピュータ、サーバ、ルータ、ネットワークＰＣ、クライアント、ピアデバイスまたは他の一般的なネットワークノードであってよく、メモリ記憶装置５０のみが図６で示されているが、典型的にはコンピュータ２０に対して上述された多くのまたはすべての要素を含む。図６に図示された論理接続は、ローカルエリアネットワーク（ＬＡＮ）５１および広域ネットワーク（ＷＡＮ）５２を含む。このようなネットワーク環境は、オフィスネットワーク、企業規模のコンピュータネットワーク、イントラネットおよびインターネットで一般的であり、これらはすべてのタイプのネットワークである。
【００４４】
ＬＡＮネットワーク環境で使われるとき、コンピュータ２０は、ローカルネットワーク５１にネットワークインターフェースまたはアダプタ５３を介して接続され、このインターフェースは１つのタイプの通信装置である。ＷＡＮネットワーク環境で使われるとき、コンピュータ２０は通常、モデム５４、ネットワークアダプタ、通信装置の類、または広域ネットワーク５２を介して通信を確立するための任意の他のタイプの通信装置を含む。モデム５４は、内蔵型または外付け型であってよいが、システムバス２３にシリアルポートインターフェース４６を介して接続される。ネットワーク環境では、パーソナルコンピュータ２０に対して図示されたプログラムモジュールまたはその部分は、リモートメモリ記憶装置に格納されてよい。図示のネットワーク接続は例示であり、コンピュータ間の通信リンクを確立する他の手段の通信装置が使用されてよいことを理解されたい。
【００４５】
例示の実装では、ＴｒａｎｓａｃｔｉｏｎＳｔａｒｔ（）モジュール、ＥｎｌｉｓｔＡｄｄｒＦｏｒＲｅａｄ（）モジュール、ＥｎｌｉｓｔＡｄｄｒＦｏｒＷｒｉｔｅ（）モジュール、ＴｒａｎｓａｃｔｉｏｎＲｅａｄ（）モジュール、ＴｒａｎｓａｃｔｉｏｎＷｒｉｔｅ（）モジュール、ＴｒａｎｓａｃｔｉｏｎＡｂｏｒｔ（）モジュール、ＴｒａｎｓａｃｔｉｏｎＣｏｍｍｉｔ（）モジュール、および他のモジュールは、オペレーティングシステム３５、アプリケーションプログラム３６、または他のプログラムモジュール３７の一部として組み込まれてよい。トランザクションログ、登録レコード、および他のデータは、プログラムデータ３８として格納されてよい。
【００４６】
本明細書で説明した技術は、１つまたは複数のシステム内の論理操作および／またはモジュールとして実装される。論理操作は、（１）１つまたは複数のコンピュータシステムで実行する一連のプロセッサ実装のステップとして、および（２）１つまたは複数のコンピュータシステム内で相互接続したマシンまたは回路モジュールとして実装されてよい。同様に、様々なコンポーネントモジュールの説明がモジュールにより実行されるかまたは行われる操作に関して行われてよい。その結果の実装されたものは選択の問題であり、説明された技術を実装する基礎となるシステムの性能要件に依存する。したがって、本明細書で説明した技術の実施形態を作り上げる論理操作は、操作、ステップ、オブジェクト、またはモジュールとして様々に参照される。さらに、他の方法で明示的にクレーム化されないかまたは特定の順序がクレーム文言により本質的に必要とされないならば、論理操作が任意の順序で実行されてよいことを理解されたい。
【００４７】
上記の明細書、例およびデータは、本発明の例示の実施形態の構造および使用の完全な説明を提供する。本発明の多くの実施形態は本発明の本質および範囲から逸脱することなく行うことができるため、本発明は特許請求の範囲に存在する。特に、説明された技術はパーソナルコンピュータと無関係に用いられてよいことを理解されたい。したがって、他の実施形態が考えられる。
【図面の簡単な説明】
【００４８】
【図１】例示の直接更新ソフトウェアトランザクショナルメモリインターフェースを介して共有メモリロケーションにアクセスする２つの並行スレッドを示す図である。
【図２】例示の直接更新ソフトウェアトランザクショナルメモリインターフェースを介してメモリアクセスを実行する操作を示す図である。
【図３】トランザクション内のメモリロケーション上の読み込み操作を登録する例示の操作を示す図である。
【図４】トランザクション内のメモリロケーション上の書き込み操作を登録する例示の操作を示す図である。
【図５】直接更新ソフトウェアトランザクショナルメモリインターフェースでトランザクションをコミットする例示の操作を示す図である。
【図６】説明された技術を実装するのに有用である可能性があるシステムを示す図である。
【図１】
2009506403.tif 000003
【図２】
2009506403.tif 000004
【図３】
2009506403.tif 000005
【図４】
2009506403.tif 000006
【図５】
2009506403.tif 000007
【図６】
2009506403.tif 000008