(57)【要約】      （修正有）【課題】マルチスレッド化されたプログラムにおける競合条件の存在を有効で、かつ効率よく検出する。【解決手段】各共用メモリロケーションについて、そのロケーションを保護しているロックの集合と、そのロケーションにアクセスしている共時スレッドセグメントの集合とが維持される。これらの集合を維持するために、各スレッドは、それが現在保持しているロックの集合と、その現在のスレッドセグメントの前に順序付けられたスレッドセグメントの集合とを維持する。各スレッドは、それが第２のスレッドをフォークするときに増分される仮想クロックも維持する。スレッドセグメントは、スレッド識別子および仮想クロック値を備えるペアである。データ競合は、ある特定の共用メモリロケーションのロックセットが空であり、そのメモリロケーションに対する共時スレッドの集合のカーディナリティが１より大きいときに報告される。【選択図】図８
2005285122.tif 000002
【特許請求の範囲】
【請求項１】
複数のスレッドおよび１つまたは複数の共用メモリロケーションを有するプログラムにおける潜在的な競合条件を動的に検出するためのシステムであって、
各共用メモリロケーションに関して、（ｉ）前記ロケーションにアクセスする共時スレッドセグメントの集合を維持するための機構、および（ｉｉ）前記ロケーションに関連付けられた第１のロックの集合を維持するための機構と、
各スレッドに関して、（ｉ）前記スレッドの現在のスレッドセグメントの前に順序付けられるスレッドセグメントの集合を維持するための機構、および（ｉｉ）前記スレッドによって獲得され、解放される第２のロックの集合を維持するための機構と、
潜在的な競合条件が検出されたときに警告を報告するための機構と
を備えることを特徴とするシステム。
【請求項２】
前記共時スレッドセグメントの集合を維持するための機構は、順序付けられたペアの集合を維持するための機構を備え、前記順序付けられたペアの集合中のペアの一方のメンバはスレッド識別子であり、前記ペアの他方のメンバは前記スレッド識別子によって識別されたスレッドに関連付けられた仮想クロック値であることを特徴とする請求項１に記載のシステム。
【請求項３】
前記現在のスレッドセグメントの前に順序付けられた前記スレッドセグメントの集合を維持するための機構は、順序付けられたペアの集合を維持するための機構を備え、前記順序付けられたペアの集合中のペアの一方のメンバはスレッド識別子であり、前記ペアの他方のメンバは前記スレッド識別子によって識別されたスレッドに関連付けられた仮想クロック値であることを特徴とする請求項１に記載のシステム。
【請求項４】
複数のスレッドおよび１つまたは複数の共用メモリロケーションを有するプログラムにおける潜在的な競合条件を動的に検出するためのコンピュータ実施される方法であって、
各共用メモリロケーションに関して、
前記ロケーションに関連付けられた第１のロックの集合を維持することと、
前記ロケーションにアクセスする共時スレッドセグメントの集合を維持することと、
各スレッドに関して、
前記スレッドによって獲得され、解放される第２のロックの集合を維持することと、
前記スレッドの現在のスレッドセグメントの前に配列されたスレッドセグメントの集合を維持することと
を備えることを特徴とする方法。
【請求項５】
各スレッドに関して、前記スレッドに関連付けられた仮想クロックを維持することをさらに備えることを特徴とする請求項４に記載の方法。
【請求項６】
前記仮想クロックを維持することは、前記スレッドが作成されるときに前記仮想クロックを初期値に初期化することを備えることを特徴とする請求項５に記載の方法。
【請求項７】
前記仮想クロックを維持することは、前記スレッドが作成されるときに前記仮想クロックをゼロに初期化することを備えることを特徴とする請求項６に記載の方法。
【請求項８】
前記スレッドの現在のスレッドセグメントの前に順序付けられる前記スレッドセグメントの集合を維持することは、順序付けられたペアの集合を維持することを備え、ペアの一方のメンバはスレッド識別子であり、前記ペアの他方のメンバは仮想クロック値であることを特徴とする請求項５に記載の方法。
【請求項９】
第１のスレッドが第２のスレッドをフォークする場合、
前記第２のスレッドの現在のスレッドセグメントの前に順序付けられるスレッドセグメントの集合を、（ａ）前記第１のスレッドの現在のスレッドセグメントの前に順序付けられるスレッドセグメントの集合と（ｂ）前記第１のスレッドの現在のスレッドセグメントを含む単集合の和集合として計算することと、
前記第１のスレッドに関連付けられた前記仮想クロックを増分することと、
前記第２のスレッドに関連付けられた前記仮想クロックを初期化することと
をさらに備えることを特徴とする請求項８に記載の方法。
【請求項１０】
前記第１のスレッドに関連付けられた前記仮想クロックを増分することは、前記第１のスレッドに関連付けられた前記仮想クロックを１だけ増分することを備えることを特徴とする請求項９に記載の方法。
【請求項１１】
前記第２のスレッドに関連付けられた前記仮想クロックを初期化することは、前記第２のスレッドに関連付けられた前記仮想クロックをゼロに初期化することを備えることを特徴とする請求項９に記載の方法。
【請求項１２】
第１のスレッドがフォークされたスレッドをジョインする場合、前記第１のスレッドの現在のスレッドセグメントの前に順序付けられるスレッドセグメントの集合を、（ａ）前記第１のスレッドの現在のスレッドセグメントの前に順序付けられるスレッドセグメントの集合と、（ｂ）前記フォークされたスレッドの現在のスレッドセグメントの前に順序付けられるが、前記第１のスレッドに属さないスレッドセグメントを含む集合と、（ｃ）前記フォークされたスレッドの現在のスレッドセグメントを含む単集合の和集合として計算すること
をさらに備えることを特徴とする請求項８に記載の方法。
【請求項１３】
前記フォークされたスレッドの現在のスレッドセグメントの前に順序付けられるが、前記第１のスレッドに属さないスレッドセグメントを含む集合は、前記フォークされたスレッドの現在のスレッドセグメントの前に順序付けられるスレッドセグメントの集合中の順序付けられたペアを含む集合を、前記順序付けられたペア中の前記スレッド識別子が前記第１のスレッドを表さないように、備えることを特徴とする請求項１２に記載の方法。
【請求項１４】
スレッドが共用メモリロケーションにアクセスする場合、
前記ロケーションにアクセスする共時スレッドセグメントの集合を、（ａ）前記スレッドの現在のスレッドセグメントを含む集合、および（ｂ）前記ロケーションにアクセスし続ける共時スレッドセグメントの集合中のスレッドセグメントを含む集合の和集合を備える集合を形成することによって更新することと、
共時スレッドセグメントの前記更新された集合が多くても１つの要素を含む場合、前記ロケーションに関連付けられたロックの集合を前記スレッドに関連付けられたロックの集合に更新することと、そうでない場合、
（ｉ）前記ロケーションに関連付けられたロックの集合を、（ａ）前記ロケーションに関連付けられたロックの集合、および（ｂ）前記スレッドに関連付けられたロックの集合の積集合を備える集合に更新することと、
（ｉｉ）前記ロケーションに関連付けられたロックの集合が空である場合、潜在的な競合条件の警告を報告することと
をさらに備えることを特徴とする請求項８に記載の方法。
【請求項１５】
前記ロケーションにアクセスし続ける共時スレッドセグメントの集合中のスレッドセグメントを含む集合は、前記共時スレッドセグメントの集合の部分集合を計算することによって形成され、前記部分集合は、
ａの前に順序付けられるスレッドセグメントの集合中のあらゆるスレッドセグメントｂについて、（ｉ）ａのスレッド識別子はｂのスレッド識別子と等しくないこと、および（ｉｉ）ａの仮想クロック値はｂの仮想クロック値より大きいことの少なくとも１つが真である
ということを満たす各スレッドセグメントａを含むことを特徴とする請求項１４に記載の方法。
【請求項１６】
動的な競合検出システムであって、
コンパイルされたコードに競合検出機能へのコールを挿入する実行時システムのコンパイラと、
前記競合検出機能によって必要とされるインストルメンテーション情報を共用メモリオブジェクトに付加する前記実行時システムのメモリアロケータと
を備えたことを特徴とするシステム。
【請求項１７】
前記コンパイラは、別のコンパイラを修正したものであることを特徴とする請求項１６に記載のシステム。
【請求項１８】
前記メモリアロケータは、別のメモリアロケータを変更したものであることを特徴とする請求項１６に記載のシステム。
【請求項１９】
コンピュータ実施される動的な競合検出の方法であって、
実行時システムのコンパイラによって、コンパイルされたコードに競合検出機能へのコールを挿入することと、
前記実行時システムのメモリアロケータによって、前記競合検出機能によって必要とされるインストルメンテーション情報を共用メモリオブジェクトに付加することと
を備えることを特徴とする方法。
【請求項２０】
前記競合検出機能への前記コールを挿入することは、前記実行時システムの前記コンパイラを修正することによるものであることを特徴とする請求項１９に記載の方法。
【請求項２１】
前記競合検出機能によって必要とされる前記インストルメンテーション情報を付加することは、前記実行時システムの前記メモリアロケータを変更することによるものであることを特徴とする請求項２０に記載の方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、一般に、コンピュータシステムに関し、より詳細には、マルチスレッド化されたコンピュータプログラムにおける競合条件を検出することに関する。
【背景技術】
【０００２】
コンピュータソフトウェアの開発者にとって、実行の複数のスレッドを使用してプログラムを書くことが一般的になっている。昨今のオペレーティングシステムおよびプログラミング言語はスレッドをサポートし、多くの大規模な商用アプリケーションがマルチスレッド化されている。スレッドは、あるオペレーティングシステムプロセス内で複数の非同期計算処理を実装するのに特に有用である。例えば、イベントドリブンのアプリケーションは、マルチスレッド化を用いることが多い。
【０００３】
しかしながら、マルチスレッド化を有用なプログラミング技法にするまさにその特徴が、マルチスレッド化されたプログラムのデバッグを非常に難しいタスクにもする。複数のスレッドは、非決定的でタイミングに依存する仕方で対話することができる。通常、そのようなスレッドはデータを共用し、スレッドがどのようにスケジュールされるか、あるいはそれらの命令ストリームがどのようにインターリーブされるかにかかわらず、プログラムの正しさを確保するためにスレッドの対話の同期が必要とされる。
【０００４】
プログラマが、競合条件に関連するスレッド同期のエラーを検出することは特に難しい。マルチスレッド化されたプログラムでは、データの競合条件は、共用メモリロケーションが２つ以上の共時スレッドによってアクセスされ、それらのアクセスの少なくとも１つがライトであり、それらのアクセスの順序付けを制約する適正な同期がないときに発生する。そのような場合における実行の影響は、それらのアクセスが生起する特定の順序に依存する。競合条件は、しばしば、プログラムクラッシュや誤った結果など、予期せぬ、望ましくないプログラム挙動を生じる結果になる。このような非決定性は、まさに、従来のデバッグ技法を用いて競合条件を検出することが非常に難しい理由でもある。
【発明の開示】
【発明が解決しようとする課題】
【０００５】
競合条件の潜在的に有害な影響、およびそれらを含むプログラムをデバッグすることの難しさを考えると、競合条件の存在を検出するための自動化ツールは、マルチスレッド化されたプログラムの開発者にとって非常に重要なはずである。しかし、有効で効率のよいツールが欠如している。プログラムのある特定の実行において潜在的競合を検出しようとする試みが行われる動的競合検出に関して、２つのアプローチが広く使用されてきた。すなわち、Ｌａｍｐｏｒｔの「ハップンビフォア（ｈａｐｐｅｎｓ−ｂｅｆｏｒｅ）」順序とロックセット技法であり、これらについては以下の詳細な説明でさらに説明する。前者は、通常、Ｃ＃やＪａｖａ（登録商標）などのオブジェクト指向言語で書かれたプログラムでは特に、非常に不満足な実行時オーバーヘッドを有し、後者のアプローチは、非同期代行（ａｓｙｎｃｈｒｏｎｏｕｓ  ｄｅｌｅｇａｔｅ）を用いるプログラムで特に、許容できない数のフォールスポジティブ（ｆａｌｓｅ  ｐｏｓｉｔｉｖｅ）を生じることが多い。
【０００６】
【非特許文献１】Lamport, "Time, Clocks, and the Ordering of Events in a Distributed System," 21 Commun. ACM 558-565 (1978)
【非特許文献２】Savage et al., "Eraser: A Dynamic Data Race Detector for Multithreaded Programs," 15 ACM Trans. Comp. Sys. 391-411 (1997)
【課題を解決するための手段】
【０００７】
以下で、本発明の基本的理解を提供するために、本発明のいくつかの実施形態の簡略化した要約を示す。この要約は、本発明の包括的な概要ではない。本発明の重要なまたは決定的な要素を特定したり、本発明の範囲を画定したりすることを意図するものではない。その唯一の目的は、以下に提示するより詳細な説明への前置きとして、簡略化した形で本発明のいくつかの実施形態を提示することである。
【０００８】
本発明の一実施形態によれば、動的な競合検出のシステムが提供される。このシステムは、共用メモリロケーションにアクセスする共時スレッドセグメントの集合を維持するための機構と、稼働中のスレッドに関して、その現在のスレッドセグメントの前に順序付けられるスレッドセグメントの集合を維持するための機構と、共用メモリロケーションに関連付けられた第１のロックの集合を維持するための機構と、第２のロックの集合中のロックを獲得し、解放するスレッドに関連付けられた第２のロックの集合を維持するための機構と、検出された競合条件を報告するための機構とを含む。
【０００９】
別の実施形態によれば、動的な競合検出のための方法が提供される。この方法は、（ａ）共用メモリロケーションに関連付けられた第１のロックの集合を維持することと、（ｂ）第２のロックの集合中のロックを獲得し、解放するスレッドに関連付けられた第２のロックの集合を維持することと、（ｃ）共用メモリロケーションにアクセスする共時スレッドセグメントの集合を維持することと、（ｄ）あるスレッドに関して、そのスレッドの現在のセグメントの前に順序付けられるスレッドセグメントの集合を維持することとを含む。
【００１０】
共用メモリロケーションにアクセスする共時スレッドセグメントの集合も、あるスレッドの前に順序付けられるスレッドセグメントの集合も、順序付けられたペアの集合として表すことができ、順序付けられたペアの集合中のペアの一方のメンバはスレッド識別子であり、ペアの他方のメンバは第１のメンバのスレッドセグメントを識別する仮想クロック値である。
【００１１】
各スレッドは、そのスレッド作成時にゼロに初期化され、そのスレッドが別のスレッドをフォークするたびに１だけ増分される仮想クロックを維持する。あるスレッドが第２のスレッドをフォークするとき、第２のスレッドの前に順序付けられるスレッドセグメントの集合は、（ｉ）第１のスレッドの前に順序付けられるスレッドセグメントの集合と、（ｉｉ）第２のスレッドがフォークされる第１のスレッドのスレッドセグメントを備える単集合の和集合として計算される。一実施形態では、第１のスレッドに関連付けられた仮想クロックが１だけ増分され、フォークされたスレッドに関連付けられた仮想クロックがゼロに初期化される。スレッドが第２のスレッドに関してジョイン操作を行うとき、第１のスレッドの前に順序付けられるスレッドセグメントの集合は、（ｉ）第１のスレッドの前に順序付けられるスレッドセグメントの集合と、（ｉｉ）第２のスレッドの前に順序付けられるスレッドセグメントの集合の部分集合であって、その部分集合中の各スレッドセグメントについて、そのスレッドセグメントのスレッド識別子が第１のスレッドのスレッド識別子と等しくない部分集合と、（ｉｉｉ）第２のスレッドの現在のスレッドセグメントを含む単集合の和集合として計算される。
【００１２】
あるスレッドが共用メモリロケーションにアクセスする場合、そのロケーションにアクセスする共時スレッドセグメントの集合は、そのロケーションにもはや同時にアクセスしていないスレッドセグメントを取り除き、そのスレッドの現在のスレッドセグメントを付加することによって更新される。その新しい共時スレッドセグメントの集合が１つの要素しか含まない場合、その共用メモリロケーションに関連付けられたロックの集合は、そのスレッドに関連付けられたロックの集合に更新され、そうでない場合、共用メモリロケーションに関連付けられたロックの集合とスレッドに関連付けられたロックの集合の積集合に更新される。共時スレッドセグメントの集合が２つ以上の要素を持ち、共用メモリロケーションに関連付けられたロックの集合が空である場合、潜在的な競合条件の警告が報告される。
【００１３】
別の実施形態によれば、動的な競合検出システムおよび方法が提供される。実行時システムにおいて、共通の中間言語の形態のコードがロードされ、実行エンジンでコンパイルされるとき、競合検出機能へのコールが発せられる。メモリオブジェクトに必要とされるインストルメンテーション情報を格納するためのデータ構造が、実行時システムのメモリ割り振り機構によって、そのオブジェクトと共に割り振られる。
【００１４】
本発明のその他の特徴は、図面と共に以下の詳細な説明をから明らかになるであろう。
【発明を実施するための最良の形態】
【００１５】
以下の記述では、本発明の様々な実施形態について説明する。説明の目的で、実施形態の十分な理解を提供するために、具体的な構成および詳細を例示する。しかしながら、本発明がそれらの具体的な詳細なしでも実施し得ることが当業者には明らかであろう。さらに、記述する実施形態がわかりにくくならないように、周知の特徴は省略したり、または簡略化したりすることがある。
【００１６】
本発明の説明に進む前に、本発明の新規性および有用性を明らかにするために、上記の背景技術で言及した従来技術のハップンビフォアアプローチおよびロックセットアプローチについていくらか詳しく説明する。ハップンビフォアアプローチでは、同時実行におけるすべてのスレッドに関連付けられたすべてのイベントの部分的な順序が作成される。この順序は、参照により本明細書に組み込まれる非特許文献１に記載された関係に基づくものである。単一スレッド内では、イベントは、それらが発生する順序で順序付けられる。スレッド間では、イベントは、スレッドによって獲得され、解放されるロックまたは他の同期オブジェクトのプロパティに従って順序付けられる。１つのスレッドがロックにアクセスし、そのロックの次のアクセスが異なるスレッドによるものである場合、第１のアクセスは、そのロックのセマンティックスが、それら２つのイベントが時間的に交換されるスケジュールを妨げる場合には、第２のアクセスの「前に発生する（ｈａｐｐｅｎ  ｂｅｆｏｒｅ）」と定義される。２つのスレッドが共用メモリロケーションにアクセスし、それらのアクセスが因果的に順序付けられていない場合、競合が発生しているとみなされる。
【００１７】
ハップンビフォアアプローチの簡単な例示として、それぞれが以下のコード断片を実行する、２つの共時スレッドｔ１およびｔ２を考察する。
【００１８】
【表１】
2005285122.tif 000003
【００１９】
図１に、２つのスレッドｔ１（１０１）およびｔ２（１０３）に関連付けられたイベントの可能な順序付けを示す。ｔ１（１０１）によって実行される３つのプログラムステートメント１０５、１０７、１０９は、それらが同じスレッドで順次実行されるので、ハップンビフォアによって順序付けられる。ｔ２（１０３）によるロックｌの獲得は、ｔ１（１０１）によるロックｌの解放と共にハップンビフォアによって順序付けられる。というのは、ある特定のロックは、それがその前の保有者によって解放されるまで獲得することができないからである。最後に、ｔ２（１０３）によって実行される３つのステートメント１１１、１１３、１１５は、それらがそのスレッド内で順次実行されるため、ハップンビフォアによって順序付けられる。
【００２０】
ロックセットベースの検出は、参照により本明細書に組み込まれる非特許文献２などのいくつかの参照文献に記載されている。単純なロックセットアプローチでは、各共用ロケーションｘについて、プログラムが実行する際にｘに対するすべてのリードおよびライトを監視することにより、ｘを保護するロックの集合Ｓｘがその計算処理のために維持される。各スレッドｔについて、スレッドｔのロック獲得を監視することにより、ｔによって保持されるロックの集合Ｓｔが維持される。
【００２１】
図２Ａおよび２Ｂの流れ図に、集合ＳｔおよびＳｘが、それぞれ、ロックセットアプローチの下でどのように維持されるかを例示する。図２Ａを見ると、ステップ２０１で、Ｓｔは、初め、スレッドｔが作成されるときには空である。ステップ２０３で、スレッドｔがロックｌを獲得するかどうかが判定される。獲得する場合、ステップ２０５で、Ｓｔとｌを含む単集合の和集合（ｕｎｉｏｎ）をとることによってＳｔが更新される。同様に、ステップ２０７で、スレッドがロックｌを解放するかどうかが判定される。解放する場合、ステップ２０９で、Ｓｔとｌを含む単集合の差集合をとることによってＳｔが更新され、このようにして、スレッドｔによって保持されるロックの集合からｌが取り除かれる。次に図２Ｂを見ると、ステップ２１１で、初めにＳｘは、すべての可能なロックの集合、Ｌである。ステップ２１３で、スレッドｔがロケーションｘに関してリードまたはライト操作を行うかどうかが判定される。行う場合、ステップ２１５で、Ｓｘは、ＳｘとＳｔの積集合（ｉｎｔｅｒｓｅｃｔ）を備える集合に更新される。ステップ２１７で、Ｓｘが空であるかどうかが判定される。空である場合、ステップ２１９で、潜在的な競合条件に関する警告が報告される。
【００２２】
図３に、図１と同じ例示的な共時スレッドｔ１およびｔ２を使用して、ロックセットアプローチの操作の簡単な例を示す。スレッドｔ１およびｔ２は、以下の順序でそれぞれのステートメントを実行するものとする。
【００２３】
【表２】
2005285122.tif 000004
【００２４】
すなわち、スレッドｔ１は、スレッドｔ２がその３つのステートメントを実行する前にその３つのステートメントを実行する。また、その実行の開始時に、Ｓｔ１およびＳｔ２は空であり、ＳｘはＬであると仮定する。
【００２５】
次に図３を見ると、この流れ図には、スレッドｔ１（３０１）およびｔ２（３０３）によって実行されるステートメントのシーケンスが表されている。ブロック３０５は、初めに、Ｓｔ１が空であり、ｔ１（３０１）がロックｌを獲得した後、Ｓｔ１がｌを含む集合になることを示している。ブロック３０７で、ｔ１（３０１）がｘのライトを実行し、その後、Ｓｘもｌを含む集合になる。ブロック３０９で、ｔ１（３０１）はロックｌを解放し、Ｓｔ１は再び空集合になる。ここで、スレッドｔ１（３０１）はその実行を終了し、スレッドｔ２（３０３）が始まる。ブロック３１１は、初めにＳｔ２が空であり、ｔ２（３０３）がロックｌを獲得した後、Ｓｔ２がｌを含む集合になることを示している。ブロック３１３で、ｔ２（３０３）はロケーションｘにライトし、その後、Ｓｘは、ＳｘとＳｔ２の積集合交わりによって形成される集合になる。両集合ともｌを含む単集合であるため、Ｓｘはｌを含む集合のままである。ブロック３１５で、ｔ２（３０３）はロックｌを解放し、Ｓｔ２は再び空になる。スレッドｔ１（３０１）およびｔ２（３０３）の実行中、Ｓｘは決して空にならず、そのため、ロックセット方法はどんな競合条件も報告しない。実際、競合条件がないことは、単一のロックｌを使用して両スレッドでｘが保護されるという事実から直感的に理解される。
【００２６】
図４に、ロックセットアプローチの操作の第２の例を示す。ここでは、ｘが両スレッドで同じロックによって保護された先の例とは異なり、スレッドｔ１（４０１）およびスレッドｔ２（４０３）がそれぞれ、異なるロックｌ１およびｌ２を使用する。ブロック４０５は、初めにＳｔ１が空であり、ｔ１（４０１）がロックｌ１を獲得した後、Ｓｔ１がｌ１を含む集合になることを示している。ブロック４０７で、ｔ１（４０１）はｘのライトを実行し、その後、Ｓｘもｌ１を含む集合になる。ブロック４０９で、ｔ１（４０１）はロックｌ１を解放し、Ｓｔ１が再び空集合になる。ここで、スレッドｔ１（４０１）がその実行を終了し、スレッドｔ２（４０３）が始まる。ブロック４１１は、初めにＳｔ２が空であり、ｔ２（４０３）がロックｌ２を獲得した後、Ｓｔ２がｌ２を含む集合になることを示している。ブロック４１３で、ｔ２（４０３）はロケーションｘにライトし、その後、Ｓｘは、ＳｘとＳｔ２の積集合によって形成される集合になる。Ｓｘはｌ１を含む集合であり、Ｓｔ２はｌ２を含む集合であり、そのため、それらの積集合は空集合である。Ｓｘは空なので、実行中のこの時点において競合条件が報告される。ブロック４１５で、ｔ２（４０３）はロックｌ２を解放し、Ｓｔ２は再び空になる。
【００２７】
ロックセットアプローチを実装するツールは、一般に、ハップンビフォア関係を使用するアプローチに関連する低性能を持たないが、そのようなツールは、競合のないプログラムについて競合条件を報告する多くのフォールスポジティブを生成することが知られている。フォールスポジティブの最も一般的な類型は、スレッドがフォーク−ジョイン（待機）システムコールを行うときに生じるものを含む。一例を図５に示す。実行の開始時には１つのスレッドだけがあるものと想定する。縦線５０１はスレッドｔの実行を表す。線５０１から伸びる斜線５０３は、ｔが新しいスレッドｔ１をフォークすることを表す。縦線５０５はスレッドｔ１の実行を表す。フォークの後、同時に実行される２つのスレッド、ｔおよびｔ１がある。線５０１に向かって伸びる斜線５０７は、スレッドｔがスレッドｔ１をジョインすることを表す。すなわち、スレッドｔはｔ１が実行を完了するのを待っている。
【００２８】
フォーク５０３およびジョイン５０７は、スレッドｔ５０１およびｔ１５０５中のイベントに関する順序付けを暗黙的に課している。ブロック５０９で、スレッドｔは、ロックｌの獲得および解放と共にｘのライトを実行する。ブロック５１１で、スレッドｔ１は、同じステートメントを実行する。ｘのこれら２つのアクセスは、同じロックｌによって保護されているので、競合条件をもたらさない。ブロック５１３で、スレッドｔは、ｘのライトを実行する。この時点で、スレッドｔは、ロックを使用する必要なくｘにライトすることができ、スレッドｔ２による実行においてｘを保護するために使用された同じロックを使用する必要もない。しかし、ブロック５１３に示すように、ｘのライトの前、Ｓｘはｌを含む集合である。ｘのライトの後、Ｓｘは空になる。単一のスレッドだけが実行されており、ｘをアクセスから保護する必要がないので明らかに競合がない場合でも、Ｓｘが空なのでロックセット手順は競合を報告する。
【００２９】
本発明は、ロックセットアプローチを拡張して、フォーク−ジョインコンテキストでフォールスポジティブを報告する傾向を排除する。ロックセットアプローチのようにスレッドごと、およびロケーションごとのロックセットを記録するのに加えて、本発明はさらに２つの集合を維持する。１つの集合は、共用メモリロケーションｘにアクセスする共時スレッドセグメントの集合を備える集合Ｔｘである。競合は、該当するロックセットが空であり、Ｔｘのカーディナリティが１より大きいときに報告される。第２の新しい集合はｔの現在のスレッドセグメントの前に順序付けられたスレッドセグメントの集合を含む集合Ｂｔである。一実施形態では、ＴｘもＢｔもタプルの集合｛＜ｔ１，ｃ１＞，．．．，＜ｔｎ，ｃｎ＞｝として表される。この順序付けは、各スレッドｔについて仮想クロックＣｔの使用に依拠する。タプル＜ｔ，ｃ＞は、仮想クロック時刻ｃにおけるスレッドｔのスレッドセグメントを表す。
【００３０】
図６は、本発明の実施形態において各スレッドについて仮想クロックが維持される仕方を例示するフォークおよびジョインを表す図である。縦線６０７はスレッドｔの実行を表す。ｔの仮想クロックは初め（６０９で指示された時点において）０であるものと想定する。斜線６１１はｔがスレッドｔ１をフォークすることを表す。（６１３で指示された）スレッドｔの実行線６０７上のこの時点において、ｔの仮想クロックが１だけ増分される。縦線６１５は、フォークされたスレッドｔ１の実行を表す。スレッドｔ１の仮想クロックは（６１７で指示された時点において）０に初期化される。斜線６１９はｔによるｔ１のジョインを表す。
【００３１】
図７Ａの流れ図に、スレッドｔによる新しい共時スレッドｔ１のフォークに関連するステップを示す。ステップ７０３で、スレッドｔがスレッドｔ１をフォークするかどうかが判定される。フォークする場合、以下の操作が行われる。ステップ７０３で、スレッドｔ１の前に順序付けられたスレッドセグメントの集合、集合Ｂｔ１が、スレッドｔの対応する集合とスレッドセグメント＜ｔ，Ｃｔ＞を備える単集合の和集合として計算される。ステップ７０５で、スレッドｔの仮想クロックが１だけ増分される。ステップ７０７で、新たにフォークされたスレッドｔ１の仮想クロックが０に初期化される。図７Ｂの流れ図に、スレッドｔによるジョインに関連するステップを示す。ステップ７１１で、スレッドｔ１が実行を完了するのを待ち、スレッドｔがジョインコールを行うかどうかが判定される。ジョインコールを行う場合、ステップ７１３で、Ｂｔの新しい値が、次の３つの集合、（ｉ）Ｂｔ、（ｉｉ）現在のスレッドｔに属さない集合Ｂｔ１中のスレッドセグメントの集合、および（ｉｉｉ）ｔ１の現在のスレッドセグメントを含む単集合の和集合として計算される。
【００３２】
ロックが獲得され、解放される際の集合Ｓｔの維持に関して、図２Ａに例示し、上述したステップが本発明でも使用され、それについてここでさらに説明する必要はない。
【００３３】
図８の流れ図に、ロケーションｘのリードおよびライトがスレッドｔによって実行されるときに行われるステップを示す。ステップ８０１で、リードおよびライトの後にロケーションｘに同時にアクセスするスレッドセグメントを表す集合Ｔｘの新しい値が計算される。新しいＴｘを形成する和集合の第２の部分は、ｔの現在のスレッドセグメント＜ｔ，Ｃｔ＞を含む集合である。スレッドｔはｘをリードしたり、またはライトしたりするので、明らかにｔは、集合Ｔｘ中にあるべきスレッドの１つである。この和集合の第１の部分は、もはやそのロケーションに同時アクセスしていない任意のスレッドが除去された集合Ｔｘの古い値の部分集合を表す。ステップ８０３で、新しいＴｘのカーディナリティが１以下であるかどうかが判定される。１以下である場合、現在ｘにアクセスしているスレッドは多くても１である。Ｓｘの新しい値が、次に、ロックセットＳｔの現在の値になる（ステップ８０５）。そうでない場合、ステップ８０７で、ｘにアクセスしている複数の共時スレッドがあり、Ｓｘの新しい値は、Ｓｘの古い値とＳｔの積集合を備える集合になる。ステップ８０９で、（ａ）Ｓｘの新しい値が空であり、（ｂ）Ｔｘの新しい値のカーディナリティが１より大きいかどうかが判定される。そうである場合、ステップ８１１で、潜在的な競合条件が報告される。
【００３４】
次に図９を見ると、図５に類似しているが、競合検出が本発明のアプローチに従うフォークおよびジョインの図が示されている。実行の開始時（ブロック９０１）において、集合ＴｘおよびＢｔは空であり、Ｓｘはロックｌを含む単集合であるものと想定する。ブロック９０５はブロック９０７の前に実行されるものとする。
【００３５】
ブロック９０５の実行後、Ｓｘはｌを含む集合になり、Ｔｘはスレッドセグメント＜ｔ，１＞を含む集合になる。ブロック９０７の実行後、Ｓｘは同じままであるが、Ｔｘは、今度は、２つのスレッドセグメント＜ｔ，１＞および＜ｔ１，０＞を含む。ブロック９０９でのジョインに続いて、Ｂｔは、スレッドセグメント＜ｔ１，０＞を含む集合になる。ｔによるｘのライトの前、ブロック９１１で、Ｓｘはｌを含む集合であり、Ｔｘは依然として２つのスレッド＜ｔ，１＞および＜ｔ１，０＞を含む集合である。ライトに続いて、Ｓｘは空になり、Ｔｘはスレッドセグメント＜ｔ，１＞を含む集合になる（ｔはｘに同時アクセスする唯一のスレッドである）。Ｔｘのカーディナリティは１なので、本発明によれば、競合条件は、正しく報告されない。
【００３６】
従来技術には、本明細書に記載した本発明の実施形態に含まれる種類の競合検出機能を実装するに際して、２つの広く使用されるアプローチがある。第１のアプローチは、ソースコードまたはバイトコードレベルでメモリアクセスに対するコールを挿入するものである。第２のアプローチは、ネイティブコードにロードおよびストア命令に対するコールを挿入するものである。こうした以前のアプローチは、動的にリンクされる多数の共用ライブラリがあるときに、競合検出ツールを実行するのが冗長になり、より注目すべきは、これは、普通、高い実行時コストを伴う。本発明のいくつかの実施形態では、動的な競合検出機能が、代わりに、実行時システム内で実装される。
【００３７】
一実施形態では、競合検出機能は、マイクロソフト社の．ＮＥＴフレームワークの共通言語ランタイム（Ｃｏｍｍｏｎ  Ｌａｎｇｕａｇｅ  Ｒｕｎｔｉｍｅ）内で実装される。バイトコードをネイティブコードにコンパイルするＪＩＴ（ジャストインタイム）コンパイラは、コードが動的にロードされ、コンパイルされるときに、競合検出機能へのコールが挿入されるように変更される。共用メモリオブジェクトを割り振るための機構は、割り振りによって、競合検出機能に必要とされるインストルメンテーション情報がオブジェクトに付加されるように変更される。次いでその情報は、ランタイムのガーベッジコレクタによって自動的に管理される。
【００３８】
この実装アプローチは、以前の技術に優るいくつかの利点を有する。第１に、実行されているすべてのコードが動的に装備される。第２に、バイトコードではなくＪＩＴを変更することにより、バイトコード検証フェーズに伴ういくつかの問題が回避される。第３に、競合検出機能へのコールをＪＩＴに挿入させることにより、コンパイラによって収集された情報を用いてインストルメンテーションを最適化することが可能になる。例えばあるフィールドがリードオンリーであると宣言され、あるいは特定のスレッドに対してローカルであり他のスレッドからは見えないとコンパイラが判定する場合など、コンパイラは、インストルメンテーションが不要であると判定することができる。第４に、競合検出機能は、ガーベッジコレクタとうまく連携して、管理されたヒープ上の共用オブジェクトだけを装備し、競合検出インストルメンテーションによって引き起こされる潜在的なメモリリーク問題を防ぐ。最後に、この実装形態は、競合検出機能実装に対する標準的なアプローチに存在するあるレベルの間接化を排除するという点で性能上の優位性を提供する。
【００３９】
その他の変形形態は、本発明の趣旨の範囲内にある。このように、本発明は様々な修正形態および代替構造が可能であるが、その特定の例示的な実施形態を図面に示し、上記で詳細に説明した。しかしながら、本発明を開示した特定の形態に限定する意図はなく、それとは反対に、添付の特許請求の範囲に規定した本発明の趣旨および範囲内に入るすべての修正、代替構成、および均等物を網羅することが意図されていることを理解されたい。
【００４０】
ここに記載したすべての方法は、本明細書で特に指示しない限り、あるいは文脈と明らかに矛盾しない限り、任意の適当な順序で行うことができる。ここに提供された任意の、そしてすべての例、あるいは例示的な言葉（「など」など）は、単に、本発明の実施形態をより明確にするためのものにすぎず、特に主張しない限り、本発明の範囲を限定するものではない。本明細書中のどんな言葉も、何ら主張されていない要素を本発明の実施に不可欠なものとして示すものであると解釈されるべきではない。
【００４１】
本発明の好ましい実施形態が、本発明を実行するために発明者が知っている最良の形態を含め、ここに記載されている。それらの好ましい実施形態の変形形態は、前述の説明を読めば当業者には明らかになるであろう。発明者は、当業者がそのような変形形態を適宜用いることを予期しており、発明者は、本発明がここに具体的に記載したのと別の方法で実施されることを意図している。したがって、本発明は、適用される法律によって許容されるように、ここに添付した特許請求の範囲に記載された内容のすべての修正形態および均等物を含む。さらに、本明細書で特に指示しない限り、あるいは文脈と明らかに矛盾しない限り、前述の要素のすべての可能な変形形態における任意の組合せも本発明によって包含される。
【図面の簡単な説明】
【００４２】
【図１】従来技術による２つの共時スレッドに関連付けられたイベントのハップンビフォア順序を表す図である。
【図２Ａ】従来技術によるスレッドに関連付けられたロックセットの維持を示す流れ図である。
【図２Ｂ】従来技術による共用メモリロケーションに関連付けられたロックセットの維持を示す流れ図である。
【図３】従来技術による競合条件のない例でのロックセットアプローチの動作を示す図である。
【図４】従来技術による正しく報告された競合条件を伴う例でのロックセットアプローチの動作を示す図である。
【図５】従来技術によるロックセットアプローチの下でフォークおよびジョインを行い、フォールスポジティブをもたらすスレッドの動作を表す図である。
【図６】本発明の一実施形態によるフォークおよびジョインを行うスレッドの動作を表し、そのスレッドの仮想クロックの維持を示す図である。
【図７Ａ】本発明の一実施形態によるフォークコールに関連するステップを示す流れ図である。
【図７Ｂ】本発明の一実施形態によるジョインコールに関連するステップを示す流れ図である。
【図８】本発明の一実施形態によるメモリロケーションのリードまたはライトに関連するステップを示す流れ図である。
【図９】本発明の一実施形態によるメモリロケーションの単一スレッド化されたアクセスについて、正しく競合条件が報告されない場合のフォークおよびジョインを行うスレッドの動作を表す図である。
【符号の説明】
【００４３】
１０１  スレッドｔ１
１０３  スレッドｔ２
３０１  スレッドｔ１
３０３  スレッドｔ２
４０１  スレッドｔ１
４０３  スレッドｔ２
【図１】
2005285122.tif 000005
【図２Ａ】
2005285122.tif 000006
【図２Ｂ】
2005285122.tif 000007
【図３】
2005285122.tif 000008
【図４】
2005285122.tif 000009
【図５】
2005285122.tif 000010
【図６】
2005285122.tif 000011
【図７Ａ】
2005285122.tif 000012
【図７Ｂ】
2005285122.tif 000013
【図８】
2005285122.tif 000014
【図９】
2005285122.tif 000015
【外国語明細書】
2005285122000001.pdf