JPH10254716A - マルチスレッデッドプログラムにおけるコンカレントエラーの検出 - Google Patents
マルチスレッデッドプログラムにおけるコンカレントエラーの検出Info
- Publication number
- JPH10254716A JPH10254716A JP10058064A JP5806498A JPH10254716A JP H10254716 A JPH10254716 A JP H10254716A JP 10058064 A JP10058064 A JP 10058064A JP 5806498 A JP5806498 A JP 5806498A JP H10254716 A JPH10254716 A JP H10254716A
- Authority
- JP
- Japan
- Prior art keywords
- lock
- lockset
- thread
- concurrent
- address
- Prior art date
- Legal status (The legal status is an assumption and is not a legal conclusion. Google has not performed a legal analysis and makes no representation as to the accuracy of the status listed.)
- Pending
Links
Classifications
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/30—Monitoring
- G06F11/34—Recording or statistical evaluation of computer activity, e.g. of down time, of input/output operation ; Recording or statistical evaluation of user activity, e.g. usability assessment
- G06F11/3466—Performance evaluation by tracing or monitoring
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/36—Prevention of errors by analysis, debugging or testing of software
- G06F11/362—Debugging of software
- G06F11/3636—Debugging of software by tracing the execution of the program
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F11/00—Error detection; Error correction; Monitoring
- G06F11/36—Prevention of errors by analysis, debugging or testing of software
- G06F11/362—Debugging of software
- G06F11/3644—Debugging of software by instrumenting at runtime
-
- G—PHYSICS
- G06—COMPUTING OR CALCULATING; COUNTING
- G06F—ELECTRIC DIGITAL DATA PROCESSING
- G06F9/00—Arrangements for program control, e.g. control units
- G06F9/06—Arrangements for program control, e.g. control units using stored programs, i.e. using an internal store of processing equipment to receive or retain programs
- G06F9/46—Multiprogramming arrangements
- G06F9/52—Program synchronisation; Mutual exclusion, e.g. by means of semaphores
- G06F9/524—Deadlock detection or avoidance
Landscapes
- Engineering & Computer Science (AREA)
- Theoretical Computer Science (AREA)
- General Engineering & Computer Science (AREA)
- Physics & Mathematics (AREA)
- General Physics & Mathematics (AREA)
- Computer Hardware Design (AREA)
- Quality & Reliability (AREA)
- Software Systems (AREA)
- Debugging And Monitoring (AREA)
- Information Retrieval, Db Structures And Fs Structures Therefor (AREA)
Abstract
(57)【要約】
【課題】 プログラムスレッドをコンカレントに実行す
るに際し、コンカレントエラーを検出すること。 【解決手段】 コンピュータによって実施される方法
は、プログラムにおけるコンカレントエラーを検出す
る。複数のプログラムスレッドの機械イメージは、スレ
ッドのコンカレント状態をもたらす命令を捜し出し置き
換えるようにインストルメントされる。複数のスレッド
が実行されている間に、コンカレント状態情報はメモリ
に記録される。この記録されたコンカレント状態情報
は、分析され、一致しない動的コンカレント状態遷移
が、コンカレントエラーとして報告される。
るに際し、コンカレントエラーを検出すること。 【解決手段】 コンピュータによって実施される方法
は、プログラムにおけるコンカレントエラーを検出す
る。複数のプログラムスレッドの機械イメージは、スレ
ッドのコンカレント状態をもたらす命令を捜し出し置き
換えるようにインストルメントされる。複数のスレッド
が実行されている間に、コンカレント状態情報はメモリ
に記録される。この記録されたコンカレント状態情報
は、分析され、一致しない動的コンカレント状態遷移
が、コンカレントエラーとして報告される。
Description
【０００１】
【発明の属する技術分野】本発明は、一般的には、コン
ピュータシステムにおいてプログラムスレッドをコンカ
レントに実行することに関し、より詳細に述べるなら
ば、コンカレントエラーを検出することに関するもので
ある。
ピュータシステムにおいてプログラムスレッドをコンカ
レントに実行することに関し、より詳細に述べるなら
ば、コンカレントエラーを検出することに関するもので
ある。
【０００２】
【従来の技術】コンプレックスコンピュータシステムに
おいては、処理をスピードアップするために、多重実行
パスまたは“スレッド”が使用されうる。例えば、ユー
ザとの対話は、フォアグラウンドスレッドによって取り
扱われうるが、一方、データベース更新の如き計算集中
オペレーションは、バックグランドスレッドによって取
り扱われうる。また、性能を改善するために、パラレル
スレッドが多重プロセッサにて実行されうる。
おいては、処理をスピードアップするために、多重実行
パスまたは“スレッド”が使用されうる。例えば、ユー
ザとの対話は、フォアグラウンドスレッドによって取り
扱われうるが、一方、データベース更新の如き計算集中
オペレーションは、バックグランドスレッドによって取
り扱われうる。また、性能を改善するために、パラレル
スレッドが多重プロセッサにて実行されうる。
【０００３】コンカレントエラーを検出することが問題
である。一つの型のコンカレントエラーは、“デッドロ
ック”、すなわち、デッドロック状態である。例えば、
スレッドＡが共用リソースＸを所有し、また、リソース
Ｙを獲得することを必要とするような場合に、デッドロ
ック状態が存在する。リソースＹは、リソースＸを獲得
することを必要としている第２のスレッドＢによって所
有されている。この結果、リソースのコンフリクトが生
ずる。典型的には、デッドロック状態により、システム
の意図された機能が停止させられてしまう。
である。一つの型のコンカレントエラーは、“デッドロ
ック”、すなわち、デッドロック状態である。例えば、
スレッドＡが共用リソースＸを所有し、また、リソース
Ｙを獲得することを必要とするような場合に、デッドロ
ック状態が存在する。リソースＹは、リソースＸを獲得
することを必要としている第２のスレッドＢによって所
有されている。この結果、リソースのコンフリクトが生
ずる。典型的には、デッドロック状態により、システム
の意図された機能が停止させられてしまう。
【０００４】もう一つ別の型のコンカレンシー問題は、
競合状態である。データ状態がスレッド実行のスピード
およびオーダーに依存する場合に、競合状態が存在しう
る。例えば、あるスレッドは、他のスレッドによって書
き込まれるアドレスのデータを読み出す必要があるかも
しれない。読み出される実際のデータは、個々のスレッ
ドにより読み取りおよび書き込みのオーダーに依存す
る。このような競合状態から生ずる非決定論により、そ
のプログラムはエラーを含む結果を生じてしまう。
競合状態である。データ状態がスレッド実行のスピード
およびオーダーに依存する場合に、競合状態が存在しう
る。例えば、あるスレッドは、他のスレッドによって書
き込まれるアドレスのデータを読み出す必要があるかも
しれない。読み出される実際のデータは、個々のスレッ
ドにより読み取りおよび書き込みのオーダーに依存す
る。このような競合状態から生ずる非決定論により、そ
のプログラムはエラーを含む結果を生じてしまう。
【０００５】知られている従来の技術は、コンカレント
エラーを静的にチェックするものである。典型的には、
従来の技術は、プログラムが正しい、すなわち、“真”
であるという定理を立証している。
エラーを静的にチェックするものである。典型的には、
従来の技術は、プログラムが正しい、すなわち、“真”
であるという定理を立証している。
【０００６】厳密なロッキングオーダーまたはデータア
クセスシーケンスは、スレッドが実行されている間に、
動的に変化することがあるということが問題である。こ
のような変化は、静的チェッカーでは検出し得ない。し
たがって、コンカレントエラーを動的にチェックするこ
とが望まれている。
クセスシーケンスは、スレッドが実行されている間に、
動的に変化することがあるということが問題である。こ
のような変化は、静的チェッカーでは検出し得ない。し
たがって、コンカレントエラーを動的にチェックするこ
とが望まれている。
【０００７】
【発明の概要】本発明によれば、プログラムにおけるコ
ンカレントエラーを検出するためのコンピュータによっ
て実施される方法が提供される。多重プログラムスレッ
ドの機械語は、スレッドのコンカレント状態をもたらす
命令を捜し出して置き換えるようにインストルメントさ
れる。置換命令は、モニターのプロシージャをコールす
る。
ンカレントエラーを検出するためのコンピュータによっ
て実施される方法が提供される。多重プログラムスレッ
ドの機械語は、スレッドのコンカレント状態をもたらす
命令を捜し出して置き換えるようにインストルメントさ
れる。置換命令は、モニターのプロシージャをコールす
る。
【０００８】本発明は、上位概念において、本特許請求
の範囲の請求項１に限定されたような、プログラムにお
けるコンカレントエラーを検出するためのコンピュータ
によって実施される方法にある。
の範囲の請求項１に限定されたような、プログラムにお
けるコンカレントエラーを検出するためのコンピュータ
によって実施される方法にある。
【０００９】後述するように、モニタープロシージャ
は、多重スレッドが実行されている間、メモリにコンカ
レント状態情報を記録する。その記録されたコンカレン
ト状態情報は、分析され得て、一致しないコンカレント
状態遷移は、コンカレントエラーとして報告され得る。
は、多重スレッドが実行されている間、メモリにコンカ
レント状態情報を記録する。その記録されたコンカレン
ト状態情報は、分析され得て、一致しないコンカレント
状態遷移は、コンカレントエラーとして報告され得る。
【００１０】置換される命令は、ロックを獲得し解放す
る命令であるのが好ましい。この場合において、記録さ
れた状態情報は、ロックのロッキングオーダーである。
ロッキングオーダーにおけるサイクルは、デッドロック
状態を示している。
る命令であるのが好ましい。この場合において、記録さ
れた状態情報は、ロックのロッキングオーダーである。
ロッキングオーダーにおけるサイクルは、デッドロック
状態を示している。
【００１１】ヒープのアドレス毎に、シャドーアドレス
が、シャドーヒープに維持される。これは、メモリアロ
ケーションおよびデアロケーション命令を捜し出し置き
換えることによって行われうる。この場合において、記
録された状態情報は、データがアクセスされるオーダー
に関連付けられている。一致しないアクセスオーダー
は、データ競合状態として報告される。
が、シャドーヒープに維持される。これは、メモリアロ
ケーションおよびデアロケーション命令を捜し出し置き
換えることによって行われうる。この場合において、記
録された状態情報は、データがアクセスされるオーダー
に関連付けられている。一致しないアクセスオーダー
は、データ競合状態として報告される。
【００１２】
【発明の実施の形態】次に、添付図面に基づいて、本発
明の実施の形態について、本発明をより詳細に説明す
る。
明の実施の形態について、本発明をより詳細に説明す
る。
【００１３】図１は、多重プログラムスレッドのコンカ
レントエラーを動的に検出するのに使用されうるプロセ
ス１００を示す。プログラマーは、通常のプログラミン
グ方法を使用してソースプログラム１１０を作成する。
ソースプログラム１１０は、処理されるとき、コンピュ
ータシステム（ＣＰＵ）１９０において同時に実行され
るようになっている。コンピュータシステム１９０は、
１つのメモリおよび１つのプロセッサを含むか、関連し
て使用される複数のメモリおよびプロセッサを含む。プ
ログラム１１０は、コンパイラ１１１によってオブジェ
クトモジュール（thread obj）１２０へとコンパイルさ
れる。
レントエラーを動的に検出するのに使用されうるプロセ
ス１００を示す。プログラマーは、通常のプログラミン
グ方法を使用してソースプログラム１１０を作成する。
ソースプログラム１１０は、処理されるとき、コンピュ
ータシステム（ＣＰＵ）１９０において同時に実行され
るようになっている。コンピュータシステム１９０は、
１つのメモリおよび１つのプロセッサを含むか、関連し
て使用される複数のメモリおよびプロセッサを含む。プ
ログラム１１０は、コンパイラ１１１によってオブジェ
クトモジュール（thread obj）１２０へとコンパイルさ
れる。
【００１４】ソースプログラム１１０が実行されている
間そのソースプログラムの挙動に関して報告を行なうた
めのモニタープログラム１３０も作成される。ソースプ
ログラム１１０の実行に関してモニタープログラム１３
０が如何にして報告を行なうことができるかについての
詳細については、後述する。モニタープログラム１３０
は、コンパイラ１３１によってオブジェクトモジュール
（mon obj)１２１へとコンパイルされる。リンカー１４
０は、オブジェクトモジュール１２０−１２１を機械イ
メージ（.exe) １５０へとリンクする。機械イメージ１
５０は、“バイナリー”プログラムまたは“テキスト”
として知られている。スレッドの実行に関する報告をす
るためのイメージ１５０の統合部分は、“モニター”１
５５と称される。
間そのソースプログラムの挙動に関して報告を行なうた
めのモニタープログラム１３０も作成される。ソースプ
ログラム１１０の実行に関してモニタープログラム１３
０が如何にして報告を行なうことができるかについての
詳細については、後述する。モニタープログラム１３０
は、コンパイラ１３１によってオブジェクトモジュール
（mon obj)１２１へとコンパイルされる。リンカー１４
０は、オブジェクトモジュール１２０−１２１を機械イ
メージ（.exe) １５０へとリンクする。機械イメージ１
５０は、“バイナリー”プログラムまたは“テキスト”
として知られている。スレッドの実行に関する報告をす
るためのイメージ１５０の統合部分は、“モニター”１
５５と称される。
【００１５】ここで注意すべきことは、リンカー１４０
は、コンパイラー１１１および１３１によって作成され
たシンボルテーブル１４１にアクセスしうるということ
である。シンボルテーブル１４１を使用して、リンカー
１４０は、例えば、オブジェクトモジュールの間で共通
なプロシージャコールおよびデータレファレンスを分析
しうる。また、ここで注意すべきことは、プログラムの
コンパイリングおよびリンキングにより、プログラムの
テキスト部分１５０と共に通される定数値を記憶するデ
ータセクション（data）１５１が発生されうるというこ
とである。一つの実施例として、プログラムテキストま
たは機械イメージ１５０は、機械命令、例えば、オペラ
ンドおよびオペレータのみを含む。すべてのデータは、
データセクション１５１に別々に記憶される。
は、コンパイラー１１１および１３１によって作成され
たシンボルテーブル１４１にアクセスしうるということ
である。シンボルテーブル１４１を使用して、リンカー
１４０は、例えば、オブジェクトモジュールの間で共通
なプロシージャコールおよびデータレファレンスを分析
しうる。また、ここで注意すべきことは、プログラムの
コンパイリングおよびリンキングにより、プログラムの
テキスト部分１５０と共に通される定数値を記憶するデ
ータセクション（data）１５１が発生されうるというこ
とである。一つの実施例として、プログラムテキストま
たは機械イメージ１５０は、機械命令、例えば、オペラ
ンドおよびオペレータのみを含む。すべてのデータは、
データセクション１５１に別々に記憶される。
【００１６】機械イメージ１５０は、インストルメンタ
ー１６０によって変更され、すなわち、“パッチ”され
る。インストルメンテーションは、イメージ１５０の選
択された命令を捜し出し置き換えるプロセスである。使
用されうるインストルメンターの例は、１９９６年７月
３日にShrivastava 氏等に与えられた米国特許第５５３
９９０７号「System for Monitoring Computer System
Performance 」に開示されている。
ー１６０によって変更され、すなわち、“パッチ”され
る。インストルメンテーションは、イメージ１５０の選
択された命令を捜し出し置き換えるプロセスである。使
用されうるインストルメンターの例は、１９９６年７月
３日にShrivastava 氏等に与えられた米国特許第５５３
９９０７号「System for Monitoring Computer System
Performance 」に開示されている。
【００１７】各選択された命令は、１つまたはそれ以上
の置換命令でオーバーライトされる。例えば、置換命令
は、サブルーチンへの飛び越し命令（jsr)１７１であり
うる。jsr 命令は、モニター１５０のプロシージャ１７
３のうちの一つを“コール”（１７２）することができ
る。プロシージャ１７３は、選択された命令がまさに実
行されようとしている時の、システムのコンカレント状
態を調べ、記録し、分析するように構成されている。
の置換命令でオーバーライトされる。例えば、置換命令
は、サブルーチンへの飛び越し命令（jsr)１７１であり
うる。jsr 命令は、モニター１５０のプロシージャ１７
３のうちの一つを“コール”（１７２）することができ
る。プロシージャ１７３は、選択された命令がまさに実
行されようとしている時の、システムのコンカレント状
態を調べ、記録し、分析するように構成されている。
【００１８】別の実施例において処理をスピードアップ
するために、コール１７２は、インライン命令として実
施されうる。すなわち、インライン命令は、プロシージ
ャ１７３を実施する。したがって、以下の説明において
は、コール１７２は、呼び出されるルーチンのサブルー
チンコールまたは等価なインライン命令を意味してい
る。
するために、コール１７２は、インライン命令として実
施されうる。すなわち、インライン命令は、プロシージ
ャ１７３を実施する。したがって、以下の説明において
は、コール１７２は、呼び出されるルーチンのサブルー
チンコールまたは等価なインライン命令を意味してい
る。
【００１９】機械語１５０がインストルメントされた
後、この機械語は、システムのメモリに記憶される。こ
のために、インストルメンテーションは、“バイナリー
リライト”として知られている。
後、この機械語は、システムのメモリに記憶される。こ
のために、インストルメンテーションは、“バイナリー
リライト”として知られている。
【００２０】変形機械語１５０は、ローダー１８０によ
ってプロセッサ１９０へロードされうる。プログラムを
実行している間に、挿入された“コール”１７２は、ス
レッド実行をインタセプトする。プロシージャ１７３
は、システムについての選択されたコンカレント状態情
報１９５を記録する。記録された状態情報は、それら状
態に関してプログラムの挙動を報告１９６するために分
析されうる。
ってプロセッサ１９０へロードされうる。プログラムを
実行している間に、挿入された“コール”１７２は、ス
レッド実行をインタセプトする。プロシージャ１７３
は、システムについての選択されたコンカレント状態情
報１９５を記録する。記録された状態情報は、それら状
態に関してプログラムの挙動を報告１９６するために分
析されうる。
【００２１】例えば、一致しないオーダーにおけるロッ
キング、または、一致しないオーダーにおけるデータの
記憶は、コンカレントエラーを反映していることがあり
うる。モニタープロシージャ１７３の完了後、置換され
た命令が実行でき、プログラムスレッドの通常の実行
は、サブルーチンからの復帰命令１７４を介して再開さ
れうる。コンカレントエラーは、プログラムが実行され
ている間、または、モニタリングの完了後に報告されう
る。
キング、または、一致しないオーダーにおけるデータの
記憶は、コンカレントエラーを反映していることがあり
うる。モニタープロシージャ１７３の完了後、置換され
た命令が実行でき、プログラムスレッドの通常の実行
は、サブルーチンからの復帰命令１７４を介して再開さ
れうる。コンカレントエラーは、プログラムが実行され
ている間、または、モニタリングの完了後に報告されう
る。
【００２２】インストルメンテーション中に置き換えら
れる特定の命令１７１は、どのスレッドコンカレント状
態を分析し報告すべきかに依存している。デッドロック
状態を検出するために、ロックを獲得し解放させるのに
使用されるプロシージャをコールするすべての機械命令
がインストルメントされる。競合状態を検出するため
に、ロックを獲得し解放させるのに使用されるプロシー
ジャをコールするすべての機械命令がインストルメント
され、それに加えて、データアクセス命令、例えば、ロ
ードおよびストア、並びに、メモリアロケーションおよ
びデアロケーションコールもインストルメントされる。
れる特定の命令１７１は、どのスレッドコンカレント状
態を分析し報告すべきかに依存している。デッドロック
状態を検出するために、ロックを獲得し解放させるのに
使用されるプロシージャをコールするすべての機械命令
がインストルメントされる。競合状態を検出するため
に、ロックを獲得し解放させるのに使用されるプロシー
ジャをコールするすべての機械命令がインストルメント
され、それに加えて、データアクセス命令、例えば、ロ
ードおよびストア、並びに、メモリアロケーションおよ
びデアロケーションコールもインストルメントされる。
【００２３】図２を参照して、デッドロックコンカレン
トエラーの検出について説明する。システム１９０にお
いて、複数のスレッド（Ａ、Ｂ、Ｃ）２１１−２１３が
命令をコンカレントに実行している。スレッド２１１−
２１３は、それらのアクティビィティー、例えば、共用
リソースへのアクセスを同期するためロック（ａ、ｂ、
・・・、ｅ、ｆ）へアクセスする。
トエラーの検出について説明する。システム１９０にお
いて、複数のスレッド（Ａ、Ｂ、Ｃ）２１１−２１３が
命令をコンカレントに実行している。スレッド２１１−
２１３は、それらのアクティビィティー、例えば、共用
リソースへのアクセスを同期するためロック（ａ、ｂ、
・・・、ｅ、ｆ）へアクセスする。
【００２４】所定のアクティビィティーを同期するため
に、スレッドは、関連するロックを獲得するためにコー
ル２２１をなす。そのロックをホールドすることによ
り、そのスレッドは、他のスレッドが同じ共用リソース
を使用しないようにすることができる。そのアクティビ
ィティーが完了したときに、コール２２２がそのロック
を解放する。単一のコールが複数のロックを獲得し、ま
たは解放することもありうる。マニピュレートされる特
定のロックは、コール２２１−２２２のアーギュメント
として通されうる。もし、所望のロックが使用できない
場合、例えば、そのロックが他のスレッドによってホー
ルドされている場合には、その獲得しようとしているス
レッドは、そのロックが使用できるようになるまで、待
ち状態にホールドされうる。
に、スレッドは、関連するロックを獲得するためにコー
ル２２１をなす。そのロックをホールドすることによ
り、そのスレッドは、他のスレッドが同じ共用リソース
を使用しないようにすることができる。そのアクティビ
ィティーが完了したときに、コール２２２がそのロック
を解放する。単一のコールが複数のロックを獲得し、ま
たは解放することもありうる。マニピュレートされる特
定のロックは、コール２２１−２２２のアーギュメント
として通されうる。もし、所望のロックが使用できない
場合、例えば、そのロックが他のスレッドによってホー
ルドされている場合には、その獲得しようとしているス
レッドは、そのロックが使用できるようになるまで、待
ち状態にホールドされうる。
【００２５】デンドロック状態を検出するための本発明
の方法によれば、ロックが正しく獲得されるべきオーダ
ーが予め規定される。これは、マルチプロセスおよびマ
ルチスレッデッドプログラムにおけるロックの獲得をマ
ネージするための普通のディシプリンである。反例とし
て、スレッドＡは、ロックａをホールドし、スレッドＢ
は、ロックｂをホールドする。前に進むためには、スレ
ッドＡもロックｂを必要とし、スレッドＢは、ロックａ
を必要とする。獲得オーダーが競合するこのような場合
には、どちらのスレッドも前に進めない。これは、デッ
ドロックのクラシカルなケースである。
の方法によれば、ロックが正しく獲得されるべきオーダ
ーが予め規定される。これは、マルチプロセスおよびマ
ルチスレッデッドプログラムにおけるロックの獲得をマ
ネージするための普通のディシプリンである。反例とし
て、スレッドＡは、ロックａをホールドし、スレッドＢ
は、ロックｂをホールドする。前に進むためには、スレ
ッドＡもロックｂを必要とし、スレッドＢは、ロックａ
を必要とする。獲得オーダーが競合するこのような場合
には、どちらのスレッドも前に進めない。これは、デッ
ドロックのクラシカルなケースである。
【００２６】コンプレックス実行環境においては、処理
アクティビィティーを同期するために数千のロックが使
用されうる。一致したロッキング挙動は、ある程度まで
は、静的にモニターされうる。もし、ロックが獲得され
るオーダーが特定の実行に依存している場合には、デッ
ドロック状態を検出することは非常に難しいものとな
る。何故ならば、ことなるロッキングオーダーにおける
置換の数は、非常に大きくなるからである。
アクティビィティーを同期するために数千のロックが使
用されうる。一致したロッキング挙動は、ある程度まで
は、静的にモニターされうる。もし、ロックが獲得され
るオーダーが特定の実行に依存している場合には、デッ
ドロック状態を検出することは非常に難しいものとな
る。何故ならば、ことなるロッキングオーダーにおける
置換の数は、非常に大きくなるからである。
【００２７】したがって、図１のモニター１５５は、ス
レッドが実行されている間におけるロックが獲得され解
放されるオーダーに関連したコンカレント状態情報を記
憶するデータ構造を維持する。この状態情報は、プログ
ラムが一般的な使用のために利用できるようにされる前
に、ロッキングオーダーにおけるエラーを検出するため
に分析されうる。
レッドが実行されている間におけるロックが獲得され解
放されるオーダーに関連したコンカレント状態情報を記
憶するデータ構造を維持する。この状態情報は、プログ
ラムが一般的な使用のために利用できるようにされる前
に、ロッキングオーダーにおけるエラーを検出するため
に分析されうる。
【００２８】もし、インストルメンター１６０がマネー
ジメントプロシージャをロックするすべてのコール１７
１を捜し出しパッチする場合には、１つのロックが獲得
され、または、解放される毎に、それらスレッドの実行
フローは、図１のプロシージャ１７３の１つによってイ
ンタセプトされうる。
ジメントプロシージャをロックするすべてのコール１７
１を捜し出しパッチする場合には、１つのロックが獲得
され、または、解放される毎に、それらスレッドの実行
フローは、図１のプロシージャ１７３の１つによってイ
ンタセプトされうる。
【００２９】より詳細に述べるならば、モニターは、各
スレッドに対して１つのロックセット２３０を維持す
る。１つのロックが獲得されるときはいつでも、そのロ
ックは、そのスレッドに関連したロックセット２３０の
メンバーとなる。そのロックが解放されるとき、そのロ
ックは、そのセットから削除される。例えば、もし、ス
レッドＡがロックａ、ｂ、ｃを獲得し、後でロックｂを
解放する場合には、そのロックセットは、メンバー
｛ａ、ｃ｝を有する。
スレッドに対して１つのロックセット２３０を維持す
る。１つのロックが獲得されるときはいつでも、そのロ
ックは、そのスレッドに関連したロックセット２３０の
メンバーとなる。そのロックが解放されるとき、そのロ
ックは、そのセットから削除される。例えば、もし、ス
レッドＡがロックａ、ｂ、ｃを獲得し、後でロックｂを
解放する場合には、そのロックセットは、メンバー
｛ａ、ｃ｝を有する。
【００３０】さらにまた、モニターは、ロックログ３０
０にすべてのロック獲得を記録する。図３に示されるよ
うに、獲得されたロックは、順序付けされたペア３０１
−３１２として次のように記録される。例えば、スレッ
ドＡは、順に、ロックａ、ｂ、ｃを獲得する。ロックｂ
が獲得されるとき、そのペア（ａ、ｂ）３０１は、その
ログに記録される。これは、ロックｂがロックａの後で
獲得されたことを示している。その後、スレッドがロッ
クｃを獲得するとき、それらペア（ａ、ｃ）および
（ｂ、ｃ）もまた記録される。何故ならば、ロックａお
よびｂは、共に、ロックｃが獲得されたときでも、スレ
ッドＡのロックセットのメンバーであるからである。
０にすべてのロック獲得を記録する。図３に示されるよ
うに、獲得されたロックは、順序付けされたペア３０１
−３１２として次のように記録される。例えば、スレッ
ドＡは、順に、ロックａ、ｂ、ｃを獲得する。ロックｂ
が獲得されるとき、そのペア（ａ、ｂ）３０１は、その
ログに記録される。これは、ロックｂがロックａの後で
獲得されたことを示している。その後、スレッドがロッ
クｃを獲得するとき、それらペア（ａ、ｃ）および
（ｂ、ｃ）もまた記録される。何故ならば、ロックａお
よびｂは、共に、ロックｃが獲得されたときでも、スレ
ッドＡのロックセットのメンバーであるからである。
【００３１】そのプログラムの実行のモニタリング中に
ロッキングオーダーが変更されない場合には、そのオー
ダリング関係を利用する最適化が可能である。このよう
な最適化において、１つのスレッドによってホールドさ
れるロックのセットは、最も前に獲得されたものから、
最も最近に獲得されたものまで、時間的順序にて維持さ
れる。このような最適化でもって、新しいロックがある
スレッドによって獲得されたときには、最も最近に獲得
されたロックおよび今獲得されつつあるロックからなる
ペアがログに記憶される。
ロッキングオーダーが変更されない場合には、そのオー
ダリング関係を利用する最適化が可能である。このよう
な最適化において、１つのスレッドによってホールドさ
れるロックのセットは、最も前に獲得されたものから、
最も最近に獲得されたものまで、時間的順序にて維持さ
れる。このような最適化でもって、新しいロックがある
スレッドによって獲得されたときには、最も最近に獲得
されたロックおよび今獲得されつつあるロックからなる
ペアがログに記憶される。
【００３２】したがって、一般的な場合において、ある
スレッドがあるロックを獲得するときはいつでも、ある
ペアが、そのスレッドのロックセットの現在のメンバー
とその新しく獲得されるロックとの組合せ毎に、ロック
ログ３００に記憶される。換言するばらば、それらペア
は、ロッキングのオーダーを表している。もし、ロック
ログ３００が既に同一ペアを記録している場合には、そ
の新しいペアは、記録されない。すなわち、そのログ
は、独自のペアのみを記憶する。ことなるオーダーにて
獲得されたロックを表す２つのペア、例えば、（ａ、
ｂ）と（ｂ、ａ）とは同一ではない。
スレッドがあるロックを獲得するときはいつでも、ある
ペアが、そのスレッドのロックセットの現在のメンバー
とその新しく獲得されるロックとの組合せ毎に、ロック
ログ３００に記憶される。換言するばらば、それらペア
は、ロッキングのオーダーを表している。もし、ロック
ログ３００が既に同一ペアを記録している場合には、そ
の新しいペアは、記録されない。すなわち、そのログ
は、独自のペアのみを記憶する。ことなるオーダーにて
獲得されたロックを表す２つのペア、例えば、（ａ、
ｂ）と（ｂ、ａ）とは同一ではない。
【００３３】図３の例であるログ３００は、ロックａ、
ｃおよびｄを獲得しているスレッドＢを示している。そ
の後で、スレッドＡは、ロックａおよびｃを解放した
が、ロックｄ、ｅおよびｆを獲得した。それから、スレ
ッドＢは、ロックａ、ｃおよびｄを解放し、ロックｆお
よびｂを獲得する。最後のロック獲得は、ログ３００に
おいてペア（ｆ、ｂ）３１２として反映されている。
ｃおよびｄを獲得しているスレッドＢを示している。そ
の後で、スレッドＡは、ロックａおよびｃを解放した
が、ロックｄ、ｅおよびｆを獲得した。それから、スレ
ッドＢは、ロックａ、ｃおよびｄを解放し、ロックｆお
よびｂを獲得する。最後のロック獲得は、ログ３００に
おいてペア（ｆ、ｂ）３１２として反映されている。
【００３４】図４は、図３のロックログ３００の図式的
表示４００を示している。ここで、各ロックは、ロック
オーダリンググラフ４００におけるノード４０１−４０
３であり、ノードのペア間の方向付けエッジ４０４−４
０５は、それらロックが獲得された相対的オーダーを示
している。
表示４００を示している。ここで、各ロックは、ロック
オーダリンググラフ４００におけるノード４０１−４０
３であり、ノードのペア間の方向付けエッジ４０４−４
０５は、それらロックが獲得された相対的オーダーを示
している。
【００３５】ここで、この例のロッキングオーダーによ
れば、反対方向における２つの相互接続エッジ４０４お
よび４０５を有するノード４０２および４０３が生ずる
ことは明らかである。これは、サイクルと称される。サ
イクルは、スレッドが競合オーダーにてロックを獲得し
ていることを示している。方向付けグラフにおけるサイ
クルは、ロックログ３００のペアに関してトポロジカル
ソートを行うことによって検出されうる。
れば、反対方向における２つの相互接続エッジ４０４お
よび４０５を有するノード４０２および４０３が生ずる
ことは明らかである。これは、サイクルと称される。サ
イクルは、スレッドが競合オーダーにてロックを獲得し
ていることを示している。方向付けグラフにおけるサイ
クルは、ロックログ３００のペアに関してトポロジカル
ソートを行うことによって検出されうる。
【００３６】他のアプリケーションのためのトポロジカ
ルソートについては、D.Knuth 氏による「The of Progr
amming, VolumeＩ, Fundamental Algorithms, Addison-
Wesley, 1968, pp.258-268」に一般的に開示されてい
る。サイクルは、潜在的なデッロック状態の証拠であ
り、したがって、報告される。
ルソートについては、D.Knuth 氏による「The of Progr
amming, VolumeＩ, Fundamental Algorithms, Addison-
Wesley, 1968, pp.258-268」に一般的に開示されてい
る。サイクルは、潜在的なデッロック状態の証拠であ
り、したがって、報告される。
【００３７】ここで注意すべきことは、ロックオーダリ
ンググラフ４００にサイクルがないことは、そのプログ
ラムが絶対的にデッドロックのないことを意味するもの
でないということである。何故ならば、他のリソース同
期化機構がデッドロック状態に巻き込まれうるからであ
る。さらに、スレッドが異なるオーダーにおいてロック
を獲得するようにさせる入力データの別のセットもあり
うる。一般的に、コンカレントエラーを動的にチェック
しても、そのプログラムの特定の実行についてスレッド
が適切にロックすることを立証することができるだけで
ある。
ンググラフ４００にサイクルがないことは、そのプログ
ラムが絶対的にデッドロックのないことを意味するもの
でないということである。何故ならば、他のリソース同
期化機構がデッドロック状態に巻き込まれうるからであ
る。さらに、スレッドが異なるオーダーにおいてロック
を獲得するようにさせる入力データの別のセットもあり
うる。一般的に、コンカレントエラーを動的にチェック
しても、そのプログラムの特定の実行についてスレッド
が適切にロックすることを立証することができるだけで
ある。
【００３８】別の型のコンカレントエラーは、データ競
合状態である。競合状態は、複数のスレッドが同一アド
レスのデータにアクセスするときに起こる。例えば、２
つのスレッドの両者が変更する意図をもってデータを読
み取る。この場合において、最終データ状態は、どちら
のスレッドが最初に完了するかに依存している。
合状態である。競合状態は、複数のスレッドが同一アド
レスのデータにアクセスするときに起こる。例えば、２
つのスレッドの両者が変更する意図をもってデータを読
み取る。この場合において、最終データ状態は、どちら
のスレッドが最初に完了するかに依存している。
【００３９】大抵のオペレーティングシステムにおいて
は、スケジュラーは、任意のオーダーにおいてスレッド
を実行する自由を有しており、同期化の制約のみを受け
る。マルチプロセッサシステムにおいては、実行は、例
えば、異なるプロセッサのキャッシュミスおよびその他
のロード条件に依存した異なるスピードで行われうる。
したがって、もし、完了時間が動的に変化する場合に
は、最終データ状態も変化しうる。
は、スケジュラーは、任意のオーダーにおいてスレッド
を実行する自由を有しており、同期化の制約のみを受け
る。マルチプロセッサシステムにおいては、実行は、例
えば、異なるプロセッサのキャッシュミスおよびその他
のロード条件に依存した異なるスピードで行われうる。
したがって、もし、完了時間が動的に変化する場合に
は、最終データ状態も変化しうる。
【００４０】もし、各共用データがロックで保護される
場合には、データ競合は避けられうる。大きなプログラ
ムの複数のスレッドの間では、どのロックがどのデータ
に関連しているのかを静的に確認することは難しい。
場合には、データ競合は避けられうる。大きなプログラ
ムの複数のスレッドの間では、どのロックがどのデータ
に関連しているのかを静的に確認することは難しい。
【００４１】図５は、アドレスレベルでデータ競合状態
を検出するのに使用されうるデータ構造を示している。
ランダムアクセスメモリ（ＲＡＭ）５００は、“ヒー
プ”５１０のアドレスにデータを記憶する。ヒープ５１
０は、データを共用するために複数のプログラムスレッ
ドによってコンカレントにアクセスされうる。
を検出するのに使用されうるデータ構造を示している。
ランダムアクセスメモリ（ＲＡＭ）５００は、“ヒー
プ”５１０のアドレスにデータを記憶する。ヒープ５１
０は、データを共用するために複数のプログラムスレッ
ドによってコンカレントにアクセスされうる。
【００４２】データは、アドレス５１１の如き独自のア
ドレスに記憶される。これらアドレスは、仮想メモリア
ドレスでありうる。これは、ダイナミック物理メモリ
（ＤＲＡＭ）の総量がアドレスされうるものよりも少な
いことを意味している。１つのありうる仮想メモリシス
テムにおいては、アドレス５１１は、３２ビット値とし
て表され得て、メモリの４ギガバイトのアドレッシング
を可能とする。物理メモリとしては、そのうちの少量部
分のみしか実施され得ない。ここで理解すべきことは、
これは、多くの変化のうちの１つのみであり、例えば、
６４ビットワードしか使用され得ないということであ
る。
ドレスに記憶される。これらアドレスは、仮想メモリア
ドレスでありうる。これは、ダイナミック物理メモリ
（ＤＲＡＭ）の総量がアドレスされうるものよりも少な
いことを意味している。１つのありうる仮想メモリシス
テムにおいては、アドレス５１１は、３２ビット値とし
て表され得て、メモリの４ギガバイトのアドレッシング
を可能とする。物理メモリとしては、そのうちの少量部
分のみしか実施され得ない。ここで理解すべきことは、
これは、多くの変化のうちの１つのみであり、例えば、
６４ビットワードしか使用され得ないということであ
る。
【００４３】ヒープ５１０のアドレス毎に、シャドーヒ
ープ５２０もまた維持される。これは、アドレス５１１
とアドレス５２１との間の１対１の対応５０１があるこ
とを意味している。シャドーヒープ５２０は、アクセス
コンカレント状態情報を記憶するのに使用される。これ
は、ヒープのあるアドレスのデータがアクセスされると
きはいつでも、アルゴリズムがそのように要求する場合
には、現在のデータアクセスコンカレント情報は、シャ
ドーヒープ５２０の対応するアドレスにて更新される。
ープ５２０もまた維持される。これは、アドレス５１１
とアドレス５２１との間の１対１の対応５０１があるこ
とを意味している。シャドーヒープ５２０は、アクセス
コンカレント状態情報を記憶するのに使用される。これ
は、ヒープのあるアドレスのデータがアクセスされると
きはいつでも、アルゴリズムがそのように要求する場合
には、現在のデータアクセスコンカレント情報は、シャ
ドーヒープ５２０の対応するアドレスにて更新される。
【００４４】図１の機械語１５０は、次のように変更さ
れる。ヒープ（ロードおよびストア）のアドレスにアク
セスするすべての命令１７１は、モニター１５５のプロ
シージャ１７３へのコール１７２によって置き換えられ
る。さらに、ヒープ５１０のアドレスをアロケートおよ
びデアロケートするプロシージャへの機械語１５０によ
るコールは、手順をモニタリングするコールで置き換え
られる。この後のアクティビィティーは、シャドーヒー
プ５２０がそのヒープ５１０のアドレスを正確に反映す
るようにするために行われる。
れる。ヒープ（ロードおよびストア）のアドレスにアク
セスするすべての命令１７１は、モニター１５５のプロ
シージャ１７３へのコール１７２によって置き換えられ
る。さらに、ヒープ５１０のアドレスをアロケートおよ
びデアロケートするプロシージャへの機械語１５０によ
るコールは、手順をモニタリングするコールで置き換え
られる。この後のアクティビィティーは、シャドーヒー
プ５２０がそのヒープ５１０のアドレスを正確に反映す
るようにするために行われる。
【００４５】図６は、シャドーヒープ５２０のアドレス
の１つにおけるワード６００を示している。このワード
６００は、２つのフィールド、すなわち、アクセス状態
フィールド６１０と、ロックセット状態フィールド６２
０とを有している。後述するように、ある特定の実施に
おいては、状態フィールド６２０は、２つのサブフィー
ルド６２１−６２２を含み得る。アクセス状態フィール
ド６１０は、１から３ビット、例えば、アクセス
（Ａ）、共用（Ｓ）および読取り／書込み（Ｒ／Ｗ）６
１１、６１２および６１３を有しうる。
の１つにおけるワード６００を示している。このワード
６００は、２つのフィールド、すなわち、アクセス状態
フィールド６１０と、ロックセット状態フィールド６２
０とを有している。後述するように、ある特定の実施に
おいては、状態フィールド６２０は、２つのサブフィー
ルド６２１−６２２を含み得る。アクセス状態フィール
ド６１０は、１から３ビット、例えば、アクセス
（Ａ）、共用（Ｓ）および読取り／書込み（Ｒ／Ｗ）６
１１、６１２および６１３を有しうる。
【００４６】ワード６００のアドレスは、ヒープ５１０
の対応するアドレスがアロケートされるとき、シャドー
ヒープ５２０にアロケートされうる。ワード６００は、
すべてのビットを零へセットするように初期化されう
る。これは、ヒープアドレスの対応するワードが決して
アドレスされていないことを示している。ヒープにおけ
るワードのデアロケーション時には、そのシャドーヒー
プの対応するワードがデアロケートされ、それが以前に
記憶していたどの情報も失われる。このデアロケーショ
ンは、ライブラリデアロケーションルーチンに対するプ
ログラムにおける明示コールを通して起こりうるか、ま
たは、後述するように注釈されたガーベジコレクターの
如き自動記憶リクラメーションルーチンを通して起こり
うる。
の対応するアドレスがアロケートされるとき、シャドー
ヒープ５２０にアロケートされうる。ワード６００は、
すべてのビットを零へセットするように初期化されう
る。これは、ヒープアドレスの対応するワードが決して
アドレスされていないことを示している。ヒープにおけ
るワードのデアロケーション時には、そのシャドーヒー
プの対応するワードがデアロケートされ、それが以前に
記憶していたどの情報も失われる。このデアロケーショ
ンは、ライブラリデアロケーションルーチンに対するプ
ログラムにおける明示コールを通して起こりうるか、ま
たは、後述するように注釈されたガーベジコレクターの
如き自動記憶リクラメーションルーチンを通して起こり
うる。
【００４７】図７は、シャドーヒープ５２０を維持する
のに使用されうるプロセス７００を示している。図２の
任意のスレッド２１１がステップ７１０でまさにヒープ
５１０のアドレスのデータにアクセスしようとすると
き、ステップ７２０において、シャドーヒープ５２０の
対応するアドレスがアロケートされていたかを決定す
る。シャドーヒープアドレスがないことにより、ステッ
プ７２５においてヒープ５１０のアロケートされていな
い部分にアクセスする誤った試みが検出される。
のに使用されうるプロセス７００を示している。図２の
任意のスレッド２１１がステップ７１０でまさにヒープ
５１０のアドレスのデータにアクセスしようとすると
き、ステップ７２０において、シャドーヒープ５２０の
対応するアドレスがアロケートされていたかを決定す
る。シャドーヒープアドレスがないことにより、ステッ
プ７２５においてヒープ５１０のアロケートされていな
い部分にアクセスする誤った試みが検出される。
【００４８】もし、妥当なシャドーヒープアドレスに記
憶された値が零（ステップ７３０における以前のアクセ
スのない）である場合には、ステップ７３２において、
状態フィールド６１０のアクセスビット７１１を論理
“１”へセットし、ステップ７３５において、アクセス
しているスレッドに関連した現在のロックセットをロッ
クセットフィールド６２０へ書き込む。置換された命令
を実行した後、そのスレッドの実行を再開する。ロック
セットがどのようにしてシャドーヒープ５２０のアドレ
スに記憶されかについては、後で詳述する。後述するよ
うに実際には、ロックセット状態フィールド６２０は、
そのロックセットが記憶されるアレー素子に対するポイ
ンタを記憶する。したがって、ロックセットの“書き込
み”は、ワード６００のポインタの記憶を意味してい
る。
憶された値が零（ステップ７３０における以前のアクセ
スのない）である場合には、ステップ７３２において、
状態フィールド６１０のアクセスビット７１１を論理
“１”へセットし、ステップ７３５において、アクセス
しているスレッドに関連した現在のロックセットをロッ
クセットフィールド６２０へ書き込む。置換された命令
を実行した後、そのスレッドの実行を再開する。ロック
セットがどのようにしてシャドーヒープ５２０のアドレ
スに記憶されかについては、後で詳述する。後述するよ
うに実際には、ロックセット状態フィールド６２０は、
そのロックセットが記憶されるアレー素子に対するポイ
ンタを記憶する。したがって、ロックセットの“書き込
み”は、ワード６００のポインタの記憶を意味してい
る。
【００４９】その後、同じアドレスに対する別のアクセ
スにより、アクセスビット７１１が零でないことが検出
される。この場合において、アドレスにアクセスしてい
るスレッドのロックセットとシャドーアドレスに記憶さ
れたロックセットとのインターセクションをとり、ステ
ップ７４０において残りのロックセットをロックセット
フィールド６２０に記憶する。もし、インターセクショ
ンをとった後ロックセットフィールド６２０がステップ
７５０において空である場合、例えば、共通の未決定の
ロックがない場合には、ステップ７５５においてそのア
ドレスに対するデータ競合状態がありうるか、または、
さもなければ、戻る。アドレスをデアロケートすること
により、ワード６００は、その初期のすべてゼロ値へと
リセットさせられる。
スにより、アクセスビット７１１が零でないことが検出
される。この場合において、アドレスにアクセスしてい
るスレッドのロックセットとシャドーアドレスに記憶さ
れたロックセットとのインターセクションをとり、ステ
ップ７４０において残りのロックセットをロックセット
フィールド６２０に記憶する。もし、インターセクショ
ンをとった後ロックセットフィールド６２０がステップ
７５０において空である場合、例えば、共通の未決定の
ロックがない場合には、ステップ７５５においてそのア
ドレスに対するデータ競合状態がありうるか、または、
さもなければ、戻る。アドレスをデアロケートすること
により、ワード６００は、その初期のすべてゼロ値へと
リセットさせられる。
【００５０】この方法は、データ競合状態を誤って合図
する可能性がある。これらは、誤りアラームとして知ら
れている。誤りアラームは、単一のスレッドのみがデー
タをアクセスしている場合に起こりうる。
する可能性がある。これらは、誤りアラームとして知ら
れている。誤りアラームは、単一のスレッドのみがデー
タをアクセスしている場合に起こりうる。
【００５１】図８は、プロセス７００がどのようにして
より弁別しうるコンカレント検出を行うように修正され
うるかを示している。この変形においては、もし、アク
セスビット７１１が非零である場合に、付加的なチェッ
クが共用ビット７１２に関してなされる（ステップ７６
０）。共用ビット７１２が零である間、スレッド識別子
が、シャドーアドレスのフィールドに記憶される。
より弁別しうるコンカレント検出を行うように修正され
うるかを示している。この変形においては、もし、アク
セスビット７１１が非零である場合に、付加的なチェッ
クが共用ビット７１２に関してなされる（ステップ７６
０）。共用ビット７１２が零である間、スレッド識別子
が、シャドーアドレスのフィールドに記憶される。
【００５２】その後のアクセスにおいて、もし、共用ビ
ット７１２がなおも零である場合には、アクセスしてい
るスレッドの識別子が、シャドーアドレスに記憶された
識別子と比較される。もし、それら識別子が異なる場合
には、共用ビット７１２は、少なくとも２つのスレッド
がそのアドレスにアクセスしたことを示すために、論理
“１”にセットされる。
ット７１２がなおも零である場合には、アクセスしてい
るスレッドの識別子が、シャドーアドレスに記憶された
識別子と比較される。もし、それら識別子が異なる場合
には、共用ビット７１２は、少なくとも２つのスレッド
がそのアドレスにアクセスしたことを示すために、論理
“１”にセットされる。
【００５３】ロックセットは、共用ビット７１２が
“１”へセットされるまでは、シャドーアドレスに記憶
されない。何故ならば、そのアドレスが１つより多いス
レッドによって共用されるまでは、エラーチェックを行
う必要がないからである。スレッド識別子およびロック
セットは同時にシャドーアドレスに記憶される必要はな
いので、シャドーアドレスの同じフィールド６２０が、
異なる時間にてこれらの値を記憶するのに使用されう
る。
“１”へセットされるまでは、シャドーアドレスに記憶
されない。何故ならば、そのアドレスが１つより多いス
レッドによって共用されるまでは、エラーチェックを行
う必要がないからである。スレッド識別子およびロック
セットは同時にシャドーアドレスに記憶される必要はな
いので、シャドーアドレスの同じフィールド６２０が、
異なる時間にてこれらの値を記憶するのに使用されう
る。
【００５４】共用ビット７１２がゼロのままである限
り、そのプロセスは、ステップ７３５においてシャドー
アドレスのロックセットフィールド６２０にそのスレッ
ドのアイデンティティを単に書き込む。この場合におい
て、ロックセットは、同じスレッドがそのアドレスのデ
ータにアクセスし続ける限り、もはやインターセクトさ
れない。もし、共用ビット７１１が“１”にセットされ
る場合には、空のセット７４０および７５０についてイ
ンターセクトし、チェックする。
り、そのプロセスは、ステップ７３５においてシャドー
アドレスのロックセットフィールド６２０にそのスレッ
ドのアイデンティティを単に書き込む。この場合におい
て、ロックセットは、同じスレッドがそのアドレスのデ
ータにアクセスし続ける限り、もはやインターセクトさ
れない。もし、共用ビット７１１が“１”にセットされ
る場合には、空のセット７４０および７５０についてイ
ンターセクトし、チェックする。
【００５５】しかしながら、この方法は、あるアプリケ
ーションに対しては粗過ぎて、なおも誤りアラームを生
ずる可能性がある。例えば、多くのデータ処理システム
においては、多くのスレッドがその後にこれらのアドレ
スを読み取ることがあるとしても、多くのアドレスが１
つのスレッドによって一度初期化されるが、決して再び
書き込まれない。この場合において、ロックは、それが
最後に書き込まれたときに、そのアドレスを保護するた
めに必要とされない。したがって、前述したコンカレン
トチェッキング方法は、多くの誤りアラームを報告する
可能性がある。
ーションに対しては粗過ぎて、なおも誤りアラームを生
ずる可能性がある。例えば、多くのデータ処理システム
においては、多くのスレッドがその後にこれらのアドレ
スを読み取ることがあるとしても、多くのアドレスが１
つのスレッドによって一度初期化されるが、決して再び
書き込まれない。この場合において、ロックは、それが
最後に書き込まれたときに、そのアドレスを保護するた
めに必要とされない。したがって、前述したコンカレン
トチェッキング方法は、多くの誤りアラームを報告する
可能性がある。
【００５６】シャドーアドレスに記憶されたＲ／Ｗビッ
ト６１３は、この問題を克服するのに使用される。この
ビットは、共用ビット６１２がセットされるまでは、無
視される。共用ビット６１２がセットされるとき、Ｒ／
Ｗビット６１３は、次の書き込みアクセス時に“１”に
セットされる。もし、共用ビット６１２が書き込みアク
セスによりセットされる場合には、Ｒ／Ｗビット６１３
もまたすぐにセットされる。
ト６１３は、この問題を克服するのに使用される。この
ビットは、共用ビット６１２がセットされるまでは、無
視される。共用ビット６１２がセットされるとき、Ｒ／
Ｗビット６１３は、次の書き込みアクセス時に“１”に
セットされる。もし、共用ビット６１２が書き込みアク
セスによりセットされる場合には、Ｒ／Ｗビット６１３
もまたすぐにセットされる。
【００５７】シャドーアドレス６００に記憶されたロッ
クセット６２０に対する更新は、Ｒ／Ｗビット６１３の
状態とは関係なく、通常のように進められる。Ｒ／Ｗビ
ット６１３の作用は、ビットが零であるときに、エラー
メッセージを抑圧することである。何故ならば、少なく
とも２つのスレッドがあるアドレスのデータにアクセス
しておらず（共用ビット６１２は“１”にセットされ
る）且つそのアドレスの共用後にそれらスレッドの少な
くとも一方によってそのアドレスが書き込まれていない
（Ｒ／Ｗビットが“１”にセットされる）限り、アクセ
スエラーは起こり得ないからである。
クセット６２０に対する更新は、Ｒ／Ｗビット６１３の
状態とは関係なく、通常のように進められる。Ｒ／Ｗビ
ット６１３の作用は、ビットが零であるときに、エラー
メッセージを抑圧することである。何故ならば、少なく
とも２つのスレッドがあるアドレスのデータにアクセス
しておらず（共用ビット６１２は“１”にセットされ
る）且つそのアドレスの共用後にそれらスレッドの少な
くとも一方によってそのアドレスが書き込まれていない
（Ｒ／Ｗビットが“１”にセットされる）限り、アクセ
スエラーは起こり得ないからである。
【００５８】ある場合に使用されうる１つのプログラミ
ング取決めは、１つより多いロックで単一のアドレスに
記憶されるデータを保護する。この取決めにおいては、
スレッドは、データが変更される前に、すべてのロック
を獲得しなければならないが、１つのスレッドは、その
データを読み取るために１つのロックを必要とするだけ
である。本発明の方法は、このようなプログラミング取
決めを受け入れるように変更されうる。ある書き込みア
クセス時に、そのプロセスは、前述したように、シャド
ーアドレスを更新しうる。ある読み取りアクセス時に、
空セットに対するロックセットインターセクションおよ
びテストが前述したように行われる。しかしながら、こ
の場合において、シャドーアドレスに記憶されたロック
セットは、インターセクトされたセットで更新されな
い。
ング取決めは、１つより多いロックで単一のアドレスに
記憶されるデータを保護する。この取決めにおいては、
スレッドは、データが変更される前に、すべてのロック
を獲得しなければならないが、１つのスレッドは、その
データを読み取るために１つのロックを必要とするだけ
である。本発明の方法は、このようなプログラミング取
決めを受け入れるように変更されうる。ある書き込みア
クセス時に、そのプロセスは、前述したように、シャド
ーアドレスを更新しうる。ある読み取りアクセス時に、
空セットに対するロックセットインターセクションおよ
びテストが前述したように行われる。しかしながら、こ
の場合において、シャドーアドレスに記憶されたロック
セットは、インターセクトされたセットで更新されな
い。
【００５９】このコンカレントエラー検出法は、ロック
が２つのモード、すなわち、読み取りモードおよび書き
込みモードのうちの一方において獲得されうるような単
一ライター／多重リーダーロックを取り扱うように更に
改良されうる。もし、あるスレッドが書き込みモードに
おいてあるロックを獲得する場合には、そのスレッド
は、他のスレッドがどのような場合でもロックをホール
ドしないように保証される。もし、あるスレッドが読み
取りモードにおいてそのロックを獲得する場合には、他
のスレッドが書き込みモードにおいてロックをホールド
しないことが保証されるだけである。
が２つのモード、すなわち、読み取りモードおよび書き
込みモードのうちの一方において獲得されうるような単
一ライター／多重リーダーロックを取り扱うように更に
改良されうる。もし、あるスレッドが書き込みモードに
おいてあるロックを獲得する場合には、そのスレッド
は、他のスレッドがどのような場合でもロックをホール
ドしないように保証される。もし、あるスレッドが読み
取りモードにおいてそのロックを獲得する場合には、他
のスレッドが書き込みモードにおいてロックをホールド
しないことが保証されるだけである。
【００６０】単一ライター／多重リーダーロックによ
り、多重スレッドがあるアドレスに記憶されたデータを
コンカレントに読み取れるようにされる。これは、多重
ロックでアドレスを保護する概念に類似している。しか
しながら、実施のための考え方は、本発明のコンカレン
トエラー検出法においてロックを受け入れる仕方のよう
に、異なる。
り、多重スレッドがあるアドレスに記憶されたデータを
コンカレントに読み取れるようにされる。これは、多重
ロックでアドレスを保護する概念に類似している。しか
しながら、実施のための考え方は、本発明のコンカレン
トエラー検出法においてロックを受け入れる仕方のよう
に、異なる。
【００６１】このような説明においては、単一のロック
セットのみが１つのスレッドに関連付けられている。ロ
ックがそのスレッドによって獲得され解放されるとき
に、ロックはそのセットに加えられ、そのセットから除
かれる。単一ライター／多重リーダーロックを受け入れ
るために、２つのロックセット、すなわち、読み取りセ
ットおよび書き込みセットが各スレッドに関連付けられ
る。
セットのみが１つのスレッドに関連付けられている。ロ
ックがそのスレッドによって獲得され解放されるとき
に、ロックはそのセットに加えられ、そのセットから除
かれる。単一ライター／多重リーダーロックを受け入れ
るために、２つのロックセット、すなわち、読み取りセ
ットおよび書き込みセットが各スレッドに関連付けられ
る。
【００６２】ある書き込みロックが獲得されるとき、そ
れは、両方のセットに加えられ、そのロックは、そのロ
ックが解放されるときに、それら２つのセットから除か
れる。読み取りロックの場合には、そのロックが読み取
りセットに加えられ、読み取りセットから解放されるだ
けである。シャドーアドレスでの情報の処理は、読み取
りアクセス中に読み取りセットのみが使用され、書き込
みアクセス中に書き込みセットが使用されること以外
は、前述したものと同様である。
れは、両方のセットに加えられ、そのロックは、そのロ
ックが解放されるときに、それら２つのセットから除か
れる。読み取りロックの場合には、そのロックが読み取
りセットに加えられ、読み取りセットから解放されるだ
けである。シャドーアドレスでの情報の処理は、読み取
りアクセス中に読み取りセットのみが使用され、書き込
みアクセス中に書き込みセットが使用されること以外
は、前述したものと同様である。
【００６３】次に、ロックセットおよびロックセットに
対するポインターをオルガナイジングするための好まし
い仕方についてより詳細に説明する。図９は、複数のロ
ックセット９０１−９０７を含むアレー９００を示して
いる。このアレー９００における各エントリーは、ロッ
クの独自のセットである。実際には、異なるロックセッ
トの数は、小さく、したがって、テーブル９００は、大
抵の場合において、メインメモリに記憶されうる。テー
ブル９００のエントリーは、特定のモニタリングセッシ
ョン中において恒久的なものである。これは、それらエ
ントリーが変更されず、テーブル９００から削除されな
いことを意味している。
対するポインターをオルガナイジングするための好まし
い仕方についてより詳細に説明する。図９は、複数のロ
ックセット９０１−９０７を含むアレー９００を示して
いる。このアレー９００における各エントリーは、ロッ
クの独自のセットである。実際には、異なるロックセッ
トの数は、小さく、したがって、テーブル９００は、大
抵の場合において、メインメモリに記憶されうる。テー
ブル９００のエントリーは、特定のモニタリングセッシ
ョン中において恒久的なものである。これは、それらエ
ントリーが変更されず、テーブル９００から削除されな
いことを意味している。
【００６４】識別子として使用される小さな整数値が各
ロックセットに関連付けられる。この識別子は、アレー
９００へのインデックスである。テーブル９００におけ
るエントリーは、エントリー“０”から始まって順次、
エントリー“１”、・・・等々の如く発生されていく。
アレーへのインデックスは、そのエントリーの識別子で
ある。図６のロックセット状態フィールド６２０に実際
に記憶されるのは、これらの識別子である。
ロックセットに関連付けられる。この識別子は、アレー
９００へのインデックスである。テーブル９００におけ
るエントリーは、エントリー“０”から始まって順次、
エントリー“１”、・・・等々の如く発生されていく。
アレーへのインデックスは、そのエントリーの識別子で
ある。図６のロックセット状態フィールド６２０に実際
に記憶されるのは、これらの識別子である。
【００６５】テーブルを小さく保つために、一つのエン
トリーは、１回より多くはアレー９００に加えられな
い。したがって、補助ハッシュテーブル１１００が維持
される。一つのロックセットエントリーがアレー９００
に発生される毎に、ハッシュテーブルエントリー１１１
０も発生される。ハッシュキー値は、ハッシングファン
クションをロックセットに直接に適用することによって
導出される。ロックセット識別子（アレーインデック
ス）は、対応するハッシュテーブル値に記憶される。し
たがって、オペレーション中、ロックセットは、独自に
識別されうる。
トリーは、１回より多くはアレー９００に加えられな
い。したがって、補助ハッシュテーブル１１００が維持
される。一つのロックセットエントリーがアレー９００
に発生される毎に、ハッシュテーブルエントリー１１１
０も発生される。ハッシュキー値は、ハッシングファン
クションをロックセットに直接に適用することによって
導出される。ロックセット識別子（アレーインデック
ス）は、対応するハッシュテーブル値に記憶される。し
たがって、オペレーション中、ロックセットは、独自に
識別されうる。
【００６６】デッドロックを検出する方法の場合のよう
に、競合状態を検出するためのこれらの方法の使用によ
り発生される結果は、モニターされる特定のプログラム
実行に依存している。異なる入力データまたは事象のわ
ずかに異なるシーケンスにより、プログラムを通しての
実行パスが異なってくることがある。このために、この
方法を使用するときには、起こりうる競合状態のすべて
が検出されるというわけにはいかないことがありうる。
実際に同期化がロッキング以外のあるメカニズムにより
起きたときや、競合状態が実際に起きえないときに、潜
在的競合状態が報告されることがありうる。
に、競合状態を検出するためのこれらの方法の使用によ
り発生される結果は、モニターされる特定のプログラム
実行に依存している。異なる入力データまたは事象のわ
ずかに異なるシーケンスにより、プログラムを通しての
実行パスが異なってくることがある。このために、この
方法を使用するときには、起こりうる競合状態のすべて
が検出されるというわけにはいかないことがありうる。
実際に同期化がロッキング以外のあるメカニズムにより
起きたときや、競合状態が実際に起きえないときに、潜
在的競合状態が報告されることがありうる。
【００６７】さらに改善したものとして、チェックされ
るべきプログラムに注釈を付けることができる。プログ
ラム注釈は、プログラマーの意図を示すためにそのプロ
グラムに付される“シグナル”である。注釈は、プログ
ラムの実行に影響を与えないものである。一つの効果と
して、注釈は、コンカレントエラー検出プロセスを改良
するために実行中にチェックされうる。
るべきプログラムに注釈を付けることができる。プログ
ラム注釈は、プログラマーの意図を示すためにそのプロ
グラムに付される“シグナル”である。注釈は、プログ
ラムの実行に影響を与えないものである。一つの効果と
して、注釈は、コンカレントエラー検出プロセスを改良
するために実行中にチェックされうる。
【００６８】ソース注釈の例としては、所定のアーギュ
メントでの“ナル”プロシージャへのコールの形であり
うる。このナルプロシージャは、その名が意味するよう
に、正規の実行フローへの戻りにほかならない。ナルプ
ロシージャへのコールは、インストルメンター１６０に
よって識別されうる。これらのコールは、アーギュメン
トを解釈するモニター１５５のプロシージャ１７３への
コールによって置き換えられうる。別の仕方として、注
釈は、モニターのプロシージャへのコールの形でもあり
うる。これらのプロシージャは、シンボルテーブル１４
１にて識別されうる。
メントでの“ナル”プロシージャへのコールの形であり
うる。このナルプロシージャは、その名が意味するよう
に、正規の実行フローへの戻りにほかならない。ナルプ
ロシージャへのコールは、インストルメンター１６０に
よって識別されうる。これらのコールは、アーギュメン
トを解釈するモニター１５５のプロシージャ１７３への
コールによって置き換えられうる。別の仕方として、注
釈は、モニターのプロシージャへのコールの形でもあり
うる。これらのプロシージャは、シンボルテーブル１４
１にて識別されうる。
【００６９】例えば、ある注釈は、次のアロケーション
が読み取り命令によって共用モードにてアクセスされう
るだけのものであるメモリアドレスに対するものである
ことを示すことがありうる。別の注釈は、アロケートさ
れるメモリがそのスレッドに対して専用であることを示
すことができる。明らかなように、このような注釈は、
誤りアラームの数を減少させうるものである。
が読み取り命令によって共用モードにてアクセスされう
るだけのものであるメモリアドレスに対するものである
ことを示すことがありうる。別の注釈は、アロケートさ
れるメモリがそのスレッドに対して専用であることを示
すことができる。明らかなように、このような注釈は、
誤りアラームの数を減少させうるものである。
【００７０】デッドロック検出の場合に加えられうる注
釈の別の例として、プログラムに使用されるロッキング
オーダーが変更されていることを示す注釈がある。例え
ば、このような注釈は、ロッキングオーダーにおけるロ
ックの位置が変更され且つそれを含むすべてのペアがロ
グから除去されるべきであったことを示すことがありう
る。
釈の別の例として、プログラムに使用されるロッキング
オーダーが変更されていることを示す注釈がある。例え
ば、このような注釈は、ロッキングオーダーにおけるロ
ックの位置が変更され且つそれを含むすべてのペアがロ
グから除去されるべきであったことを示すことがありう
る。
【００７１】動的競合検出の場合において、もし、プロ
グラムが自動記憶リクラメーション（ガーベジコレクシ
ョン）を与える場合には、モニターに対するコールの形
の注釈は、記憶のあるレンジがリクラメートされてお
り、シャドーヒープからデアロケートされるべきである
ことを示すために、プログラムのソースに含まれうる。
グラムが自動記憶リクラメーション（ガーベジコレクシ
ョン）を与える場合には、モニターに対するコールの形
の注釈は、記憶のあるレンジがリクラメートされてお
り、シャドーヒープからデアロケートされるべきである
ことを示すために、プログラムのソースに含まれうる。
【００７２】本発明の特定の実施例について説明してき
たのであるが、これらの実施例の種々な変形態様が考え
られ、これら変形態様においても、前述したような効果
のすべて、またはそれら効果のうちのいくつかを達成し
うることは明らかであろう。したがって、本請求の範囲
の記載は、本発明の範囲内に入るような変形態様のすべ
てを包含しようとするものである。
たのであるが、これらの実施例の種々な変形態様が考え
られ、これら変形態様においても、前述したような効果
のすべて、またはそれら効果のうちのいくつかを達成し
うることは明らかであろう。したがって、本請求の範囲
の記載は、本発明の範囲内に入るような変形態様のすべ
てを包含しようとするものである。
【図１】プログラムにおける同期エラーを動的に検出す
るためのプロセスを示すブロック図である。
るためのプロセスを示すブロック図である。
【図２】多重スレッドおよびロックセットを示すブロッ
ク図である。
ク図である。
【図３】ロックログを示すブロック図である。
【図４】ロックオーダーリンググラフを示すブロック図
である。
である。
【図５】ヒープおよびシャドーヒープを示すブロック図
である。
である。
【図６】ロックセットを示すブロック図である。
【図７】コンカレントアクセスエラーをチェックするた
めのプロセスを示すブロック図である。
めのプロセスを示すブロック図である。
【図８】コンカレント共用アクセスエラーをチェックす
るための変形フローを示す図である。
るための変形フローを示す図である。
【図９】ロックセットアレーおよびハッシュテーブルを
示すブロック図である。
示すブロック図である。
１００ プロセス １１０ ソースプログラム １１１ コンパイラ １２０ オブジェクトモジュール １２１ オブジェクトモジュール １３０ モニタープログラム １３１ コンパイラ １４０ リンカー １４１ シンボルテーブル １５０ 機械イメージ １５１ データセクション １５５ モニター １６０ インストルメンター １７１ サブルーチンへの飛び越し命令 １７２ コール １７３ プロシージャ １７４ サブルーチンからの復帰命令 １８０ ローダー １９０ プロセッサ １９５ コンカレント状態情報
───────────────────────────────────────────────────── フロントページの続き (72)発明者 チャールズ ジー ネルソン アメリカ合衆国 カリフォルニア州 94306 パロ アルト カレッジ アベニ ュー 770 (72)発明者 ステファン サヴェージ アメリカ合衆国 ワシントン州 98052 レッドモンド ノースイースト ワンハン ドレッズ コート 17831 (72)発明者 パトリック ジー ソバルヴァーロ アメリカ合衆国 カリフォルニア州 94301 パロ アルト エマーソン スト リート 312
Claims (10)
- 【請求項１】 プログラムにおけるコンカレントエラー
を検出するためのコンピュータによって実施される方法
であって、プログラムの複数のスレッドの機械語をイン
ストルメンティングして、該スレッドのコンカレント状
態をもたらす命令を捜し出して置き換え、前記複数のス
レッドが実行されている間にメモリにコンカレント状態
情報を記録し、該記録されたコンカレント状態情報を分
析し、一致しない動的コンカレント状態遷移をコンカレ
ントエラーとして報告することを特徴とする方法。 - 【請求項２】 ロックを獲得し解放する命令を捜し出
し、該捜し出された命令を実行フローをインタセプトす
る命令と置き換え、実行されている間に前記複数のスレ
ッドがロックを獲得し解放するオーダーを記録し、前記
複数のロックがロックを獲得するオーダーにおいて一致
しないコンカレント状態遷移をサイクルとして報告し、
実行フローをインタセプトするときにモニタリングプロ
シージャをコールすることを含む請求項１記載の方法。 - 【請求項３】 各スレッドに対して、スレッドに関連し
た現在のロックセットを維持し、ロックが獲得されると
きに前記ロックセットにそのロックを加え、前記ロック
が解放されるときに前記ロックセットからそのロックを
削除し、前記ロックが獲得されるオーダーをロックログ
に記憶させ、新しいロックが獲得されるときに前記ロッ
クセットにロックセットペアを記憶させ、該ペアは、前
記ロックセットの現在のメンバーと、前記ロックセット
のメンバーでない前記新しいロックとの各独自の組み合
わせであり、各ペアに対して、前記ロックセットの現在
のメンバーが第１の位置に記録され、前記新しいロック
が第２の位置に記録されるか、または、前記ロックセッ
トの現在のメンバーが第２の位置に記録され、前記新し
いロックが第１の位置に記憶されるか、するように決定
されたオーダーにて前記ペアを記憶させることを含む請
求項１記載の方法。 - 【請求項４】 前記ロックログのペアは、順序付けされ
たロックグラフとして表されており、さらに、各ロック
のためのノードと、第１のロックを第２のロックに接続
する方向付けエッジとを備えており、該エッジの方向
は、前記第１および第２のロックが獲得されたオーダー
を示しており、第１のノードおよび第２のノードが反対
方向に向けられた第１のエッジおよび第２のエッジによ
って接続されるようなトポロジカルソートを前記ロック
グラフに対して行い、前記第１および第２のノードに関
連したロックをコンカレントロッキングエラーとして報
告することを含む請求項３記載の方法。 - 【請求項５】 ヒープの各アドレスに対して、メモリア
ロケーションおよびメモリデアロケーション命令を捜し
出し置き換えることによってシャドーヒープにおけるシ
ャドーアドレスを維持し、前記ヒープのアドレスのデー
タにアクセスする命令を捜し出し、該アクセス命令をモ
ニタリングプロシージャに対する命令で置き換え、前記
モニタリングプロシージャによって対応するシャドーア
ドレスにロックセット情報を記録し、前記アクセス命令
によるアクセスが前記記録されたロックセット情報と一
致しない場合に、一致しないコンカレント状態をデータ
競合状態として報告することを含む請求項１記載の方
法。 - 【請求項６】 前記ヒープのアロケートされたアドレス
へのアクセスを検出することを含む請求項５記載の方
法。 - 【請求項７】 現在アクセスしているスレッドの現在の
ロックセット情報を前記ヒープのアドレスにアクセスし
ている前のスレッドの記憶されたロックセット情報でイ
ンターセクトし、前記セットのインターセクションが空
である場合に、データ競合状態を報告し、現在のロック
セットと前のロックセットとが異なる場合に、現在のロ
ックセット情報と記憶されたロックセット情報とのイン
ターセクションを記憶し、前記アクセスが前記アドレス
への書き込みである場合に、前記現在のロックセットと
記憶されたロックセットとのインターセクションを書き
込むことを含む請求項６記載の方法。 - 【請求項８】 前記スレッドアクセスが共用されないと
きに、アクセスするスレッドのアイデンティティを記憶
することを含む請求項５記載の方法。 - 【請求項９】 読み取りアクセスに対して読み取りロッ
クセットを維持し、書き込みアクセスに対して書き込み
ロックセットを維持し、読み取りアクセスに対して前記
読み取りロックセットに読み取りロックを加え、書き込
みアクセスに対して前記書き込みロックセットに書き込
みロックを加えることを含む請求項１記載の方法。 - 【請求項１０】 前記ロックセットをアレーのエントリ
ーに記録し、特定のエントリーに記憶されたロックセッ
トに関連した各シャドーアドレスでのアレーのその特定
のエントリーに対するポインターを記憶させ、特定のロ
ックセットからハッシュ値を決定し、該ハッシュ値によ
って決定されるようなハッシュテーブルに前記ポインタ
ーを記憶させることを含む請求項５記載の方法。
Applications Claiming Priority (2)
| Application Number | Priority Date | Filing Date | Title |
|---|---|---|---|
| US08/815,979 US6009269A (en) | 1997-03-10 | 1997-03-10 | Detecting concurrency errors in multi-threaded programs |
| US08/815979 | 1997-03-10 |
Publications (1)
| Publication Number | Publication Date |
|---|---|
| JPH10254716A true JPH10254716A (ja) | 1998-09-25 |
Family
ID=25219348
Family Applications (1)
| Application Number | Title | Priority Date | Filing Date |
|---|---|---|---|
| JP10058064A Pending JPH10254716A (ja) | 1997-03-10 | 1998-03-10 | マルチスレッデッドプログラムにおけるコンカレントエラーの検出 |
Country Status (4)
| Country | Link |
|---|---|
| US (1) | US6009269A (ja) |
| EP (1) | EP0864975A3 (ja) |
| JP (1) | JPH10254716A (ja) |
| CA (1) | CA2231597A1 (ja) |
Cited By (4)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100421316B1 (ko) * | 2000-02-24 | 2004-03-10 | 박희동 | 동기화를 가진 공유메모리 병렬프로그램에서 실행중 2단계최초경합 탐지를 위한 사건선택 방법 |
| US6931514B2 (en) | 2000-11-29 | 2005-08-16 | Nec Corporation | Data dependency detection using history table of entry number hashed from memory address |
| JP2005285122A (ja) * | 2004-03-24 | 2005-10-13 | Microsoft Corp | マルチスレッド化されたプログラムにおける潜在的な競合を検出するための方法およびシステム |
| JP2009032197A (ja) * | 2007-07-30 | 2009-02-12 | Fujitsu Microelectronics Ltd | ソフトウェアのシミュレーション方法、ソフトウェアのシミュレーションのためのプログラム、及びソフトウェアのシミュレーション装置 |
Families Citing this family (84)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| US6654879B1 (en) * | 1997-01-30 | 2003-11-25 | Northbrook Services | Method and apparatus for analyzing code for out-of-range data involving base and seed tables/lists |
| JP3367385B2 (ja) * | 1997-06-27 | 2003-01-14 | 日本電気株式会社 | 分散トランザクション整合方法及びプログラムを記録した機械読み取り可能な記録媒体 |
| US6212653B1 (en) * | 1998-02-18 | 2001-04-03 | Telefonaktiebolaget Lm Ericsson (Publ) | Logging of events for a state driven machine |
| US6920634B1 (en) * | 1998-08-03 | 2005-07-19 | International Business Machines Corporation | Detecting and causing unsafe latent accesses to a resource in multi-threaded programs |
| US6360220B1 (en) * | 1998-08-04 | 2002-03-19 | Microsoft Corporation | Lock-free methods and systems for accessing and storing information in an indexed computer data structure having modifiable entries |
| US6321276B1 (en) | 1998-08-04 | 2001-11-20 | Microsoft Corporation | Recoverable methods and systems for processing input/output requests including virtual memory addresses |
| US6594701B1 (en) | 1998-08-04 | 2003-07-15 | Microsoft Corporation | Credit-based methods and systems for controlling data flow between a sender and a receiver with reduced copying of data |
| US6314471B1 (en) * | 1998-11-13 | 2001-11-06 | Cray Inc. | Techniques for an interrupt free operating system |
| US6862635B1 (en) | 1998-11-13 | 2005-03-01 | Cray Inc. | Synchronization techniques in a multithreaded environment |
| US6480818B1 (en) | 1998-11-13 | 2002-11-12 | Cray Inc. | Debugging techniques in a multithreaded environment |
| US6952827B1 (en) | 1998-11-13 | 2005-10-04 | Cray Inc. | User program and operating system interface in a multithreaded environment |
| US6826752B1 (en) * | 1998-12-17 | 2004-11-30 | California Institute Of Technology | Programming system and thread synchronization mechanisms for the development of selectively sequential and multithreaded computer programs |
| US6415433B1 (en) | 1998-12-23 | 2002-07-02 | Cray Inc. | Method and system for identifying locations to move portions of the computer program |
| US6430676B1 (en) | 1998-12-23 | 2002-08-06 | Cray Inc. | Method and system for calculating instruction lookahead |
| US6593940B1 (en) * | 1998-12-23 | 2003-07-15 | Intel Corporation | Method for finding errors in multithreaded applications |
| US6230313B1 (en) | 1998-12-23 | 2001-05-08 | Cray Inc. | Parallelism performance analysis based on execution trace information |
| US6665688B1 (en) | 1998-12-23 | 2003-12-16 | Cray Inc. | Method and system for automatically regenerating data on-demand |
| US6321379B1 (en) | 1998-12-23 | 2001-11-20 | Cray Inc. | Method and system for target register allocation |
| US6353829B1 (en) | 1998-12-23 | 2002-03-05 | Cray Inc. | Method and system for memory allocation in a multiprocessing environment |
| US6378124B1 (en) | 1999-02-22 | 2002-04-23 | International Business Machines Corporation | Debugger thread synchronization control points |
| US6587967B1 (en) * | 1999-02-22 | 2003-07-01 | International Business Machines Corporation | Debugger thread monitor |
| US6405326B1 (en) * | 1999-06-08 | 2002-06-11 | International Business Machines Corporation Limited | Timing related bug detector method for detecting data races |
| US6714958B1 (en) * | 1999-07-28 | 2004-03-30 | International Business Machines Corporation | Detecting and causing latent deadlocks in multi-threaded programs |
| US6915342B1 (en) * | 2000-02-04 | 2005-07-05 | Ricoh Company Limited | Method and system for maintaining the business office appliance through log files |
| US6658650B1 (en) * | 2000-02-18 | 2003-12-02 | International Business Machines Corporation | Service entry point for use in debugging multi-job computer programs |
| US6601120B1 (en) * | 2000-07-13 | 2003-07-29 | Silicon Graphics, Inc. | System, method and computer program product for implementing scalable multi-reader/single-writer locks |
| US6681345B1 (en) * | 2000-08-15 | 2004-01-20 | International Business Machines Corporation | Field protection against thread loss in a multithreaded computer processor |
| US6817009B2 (en) * | 2000-11-30 | 2004-11-09 | Hewlett-Packard Development Company, L.P. | Method and apparatus for verifying data local to a single thread |
| US7469403B2 (en) * | 2001-04-19 | 2008-12-23 | International Business Machines Corporation | Static detection of a datarace condition for multithreaded object-oriented applications |
| US7137120B2 (en) * | 2001-12-17 | 2006-11-14 | International Business Machines Corporation | Dynamic diagnostic program for determining thread wait time |
| US6807541B2 (en) * | 2002-02-28 | 2004-10-19 | International Business Machines Corporation | Weak record locks in database query read processing |
| WO2003083614A2 (en) * | 2002-03-25 | 2003-10-09 | Eternal Systems, Inc. | Transparent consistent active replication of multithreaded application programs |
| US7516446B2 (en) * | 2002-06-25 | 2009-04-07 | International Business Machines Corporation | Method and apparatus for efficient and precise datarace detection for multithreaded object-oriented programs |
| US7111287B2 (en) * | 2003-01-10 | 2006-09-19 | International Business Machines Corporation | Global processor resource assignment in an assembler |
| US7278057B2 (en) * | 2003-07-31 | 2007-10-02 | International Business Machines Corporation | Automated hang detection in Java thread dumps |
| US20050038806A1 (en) * | 2003-08-12 | 2005-02-17 | Zhiqiang Ma | Methods and apparatus for detecting data race conditions in message-based multi-threaded programs |
| EP1569121B1 (en) * | 2004-02-26 | 2007-07-11 | Research In Motion Limited | Method and system for detecting potential deadlocks in computer programs |
| US7366956B2 (en) * | 2004-06-16 | 2008-04-29 | Hewlett-Packard Development Company, L.P. | Detecting data races in multithreaded computer programs |
| US7757237B2 (en) * | 2004-06-16 | 2010-07-13 | Hewlett-Packard Development Company, L.P. | Synchronization of threads in a multithreaded computer program |
| US20050283770A1 (en) * | 2004-06-18 | 2005-12-22 | Karp Alan H | Detecting memory address bounds violations |
| US7458065B2 (en) * | 2004-09-21 | 2008-11-25 | Intel Corporation | Selection of spawning pairs for a speculative multithreaded processor |
| US7620852B2 (en) * | 2005-03-02 | 2009-11-17 | Microsoft Corporation | Systems and methods of reporting multiple threads involved in a potential data race |
| US8266600B2 (en) * | 2005-03-28 | 2012-09-11 | Nec Laboratories America, Inc. | Model checking of multi threaded software |
| US20070074210A1 (en) * | 2005-09-23 | 2007-03-29 | Microsoft Corporation | Optimal stateless search |
| EP1783604A3 (en) * | 2005-11-07 | 2007-10-03 | Slawomir Adam Janczewski | Object-oriented, parallel language, method of programming and multi-processor computer |
| US7644396B2 (en) * | 2005-11-29 | 2010-01-05 | Microsoft Corporation | Optimal program execution replay and breakpoints |
| US20070143766A1 (en) * | 2005-12-21 | 2007-06-21 | International Business Machines Corporation | Deadlock detection in a computing environment |
| US8572606B1 (en) * | 2005-12-29 | 2013-10-29 | Vmware, Inc. | System and method for avoiding synchronization bugs through virtualization |
| US7836435B2 (en) * | 2006-03-31 | 2010-11-16 | Intel Corporation | Checking for memory access collisions in a multi-processor architecture |
| US8028296B2 (en) * | 2006-03-31 | 2011-09-27 | Microsoft Corporation | Providing a wrapper around native synchronization objects |
| US20070271450A1 (en) * | 2006-05-17 | 2007-11-22 | Doshi Kshitij A | Method and system for enhanced thread synchronization and coordination |
| US8185874B2 (en) * | 2006-11-07 | 2012-05-22 | Microsoft Corporation | Automatic and systematic detection of race conditions and atomicity violations |
| US20080281887A1 (en) * | 2007-05-10 | 2008-11-13 | Nokia Corporation | Application specific garbage collection system |
| US9026993B2 (en) * | 2008-06-27 | 2015-05-05 | Microsoft Technology Licensing, Llc | Immutable types in imperitive language |
| US7941616B2 (en) * | 2008-10-21 | 2011-05-10 | Microsoft Corporation | System to reduce interference in concurrent programs |
| US9569282B2 (en) | 2009-04-24 | 2017-02-14 | Microsoft Technology Licensing, Llc | Concurrent mutation of isolated object graphs |
| CN102053861B (zh) * | 2009-10-30 | 2014-03-12 | 国际商业机器公司 | 并行程序中死锁检测的方法和系统 |
| US8566544B2 (en) * | 2009-12-29 | 2013-10-22 | Microsoft Corporation | Compiler-enforced agent access restriction |
| US8316369B2 (en) | 2009-12-29 | 2012-11-20 | Microsoft Corporation | Dataflow component scheduling using reader/writer semantics |
| US8695003B2 (en) | 2009-12-29 | 2014-04-08 | Microsoft Corporation | Method for managing data accessibility by scheduling three types of executable agents associated with pre-defined access rights within a domain |
| US8549359B2 (en) * | 2010-05-12 | 2013-10-01 | Salesforce.Com, Inc. | Method and system for identifying errors in code |
| US9069894B2 (en) * | 2010-06-18 | 2015-06-30 | Microsoft Technology Licensing, Llc | Data collisions in concurrent programs |
| US8769518B1 (en) | 2010-06-29 | 2014-07-01 | Ca, Inc. | Ensuring determinism during programmatic replay in a virtual machine |
| US8732670B1 (en) | 2010-06-29 | 2014-05-20 | Ca, Inc. | Ensuring determinism during programmatic replay in a virtual machine |
| US9395987B2 (en) * | 2010-09-23 | 2016-07-19 | Freescale Semiconductor, Inc. | Method and device for detecting a race condition |
| US8533682B2 (en) | 2010-11-05 | 2013-09-10 | Microsoft Corporation | Amplification of dynamic checks through concurrency fuzzing |
| US20120151271A1 (en) * | 2010-12-10 | 2012-06-14 | Nec Laboratories America, Inc. | Mat-reduced symbolic analysis |
| EP2795466A4 (en) * | 2011-12-21 | 2015-09-23 | Intel Corp | METHODS AND SYSTEMS FOR IDENTIFYING AND REPRODUCING SIMULTANEOUS ACCESS VIOLATIONS IN MULTIFUNCTION PROGRAMS |
| US9135139B2 (en) | 2012-06-27 | 2015-09-15 | Intel Corporation | Methods and systems to identify and reproduce concurrency violations in multi-threaded programs using expressions |
| US9098269B2 (en) * | 2013-01-04 | 2015-08-04 | Microsoft Technology Licensing, Llc | System and method to ensure resource access safety with immutable object types |
| US10078575B2 (en) * | 2013-03-13 | 2018-09-18 | Microsoft Technology Licensing, Llc | Diagnostics of state transitions |
| US9117021B2 (en) * | 2013-03-14 | 2015-08-25 | Intel Corporation | Methods and apparatus to manage concurrent predicate expressions |
| US9842009B2 (en) * | 2013-05-13 | 2017-12-12 | Nxp Usa, Inc. | Method and device for detecting a race condition and a computer program product |
| DE102015011315A1 (de) * | 2015-08-28 | 2017-03-02 | Giesecke & Devrient Gmbh | Codeverschleierung |
| US10614039B2 (en) * | 2017-04-04 | 2020-04-07 | International Business Machines Corporation | Testing of lock managers in computing environments |
| US10733083B2 (en) * | 2017-10-18 | 2020-08-04 | Salesforce.Com, Inc. | Concurrency testing |
| US10599552B2 (en) * | 2018-04-25 | 2020-03-24 | Futurewei Technologies, Inc. | Model checker for finding distributed concurrency bugs |
| CN111414337B (zh) * | 2019-01-08 | 2023-05-26 | 阿里巴巴集团控股有限公司 | 一种文件读取方法、装置、计算设备及存储介质 |
| CN111090528B (zh) * | 2019-12-25 | 2023-09-26 | 北京天融信网络安全技术有限公司 | 死锁确定方法、装置及电子设备 |
| EP3964959A1 (en) * | 2020-09-03 | 2022-03-09 | ARM Limited | Data processing |
| CN112181808B (zh) * | 2020-09-08 | 2022-06-28 | 北京邮电大学 | 一种程序并发缺陷检测方法、装置、设备以及存储介质 |
| CN116758657B (zh) * | 2023-05-06 | 2026-01-27 | 珠海格力电器股份有限公司 | 一种智能门锁的管理方法、装置、设备及存储介质 |
| CN117971137B (zh) * | 2024-04-02 | 2024-06-04 | 山东海润数聚科技有限公司 | 一种基于多线程的大规模向量数据一致性的评估方法和系统 |
| CN121187933B (zh) * | 2025-09-10 | 2026-04-17 | 成都蜀天众赢科技有限公司 | 一种软件缺陷的实时监控与根因定位方法及系统 |
Family Cites Families (11)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| JPH05134886A (ja) * | 1990-11-30 | 1993-06-01 | Fujitsu Ltd | デツドロツク検出方式 |
| US5193180A (en) * | 1991-06-21 | 1993-03-09 | Pure Software Inc. | System for modifying relocatable object code files to monitor accesses to dynamically allocated memory |
| US5469575A (en) * | 1992-10-16 | 1995-11-21 | International Business Machines Corporation | Determining a winner of a race in a data processing system |
| EP0595453B1 (en) * | 1992-10-24 | 1998-11-11 | International Computers Limited | Distributed data processing system |
| DE69422743T2 (de) * | 1993-03-30 | 2000-06-08 | Fujitsu Ltd., Kawasaki | Endlosschleife-Erkennungsgerät |
| FR2708766B1 (fr) * | 1993-08-03 | 1995-09-08 | Bull Sa | Procédé d'analyse d'interblocages dans un système d'exploitation. |
| US5539907A (en) * | 1994-03-01 | 1996-07-23 | Digital Equipment Corporation | System for monitoring computer system performance |
| JP3392236B2 (ja) * | 1994-11-04 | 2003-03-31 | 富士通株式会社 | 分散トランザクション処理システム |
| US5764976A (en) * | 1995-02-06 | 1998-06-09 | International Business Machines Corporation | Method and system of deadlock detection in a data processing system having transactions with multiple processes capable of resource locking |
| US5682537A (en) * | 1995-08-31 | 1997-10-28 | Unisys Corporation | Object lock management system with improved local lock management and global deadlock detection in a parallel data processing system |
| US5862376A (en) * | 1996-06-24 | 1999-01-19 | Sun Microsystems, Inc. | System and method for space and time efficient object locking |
-
1997
- 1997-03-10 US US08/815,979 patent/US6009269A/en not_active Expired - Lifetime
-
1998
- 1998-03-09 EP EP98104160A patent/EP0864975A3/en not_active Withdrawn
- 1998-03-09 CA CA002231597A patent/CA2231597A1/en not_active Abandoned
- 1998-03-10 JP JP10058064A patent/JPH10254716A/ja active Pending
Cited By (6)
| Publication number | Priority date | Publication date | Assignee | Title |
|---|---|---|---|---|
| KR100421316B1 (ko) * | 2000-02-24 | 2004-03-10 | 박희동 | 동기화를 가진 공유메모리 병렬프로그램에서 실행중 2단계최초경합 탐지를 위한 사건선택 방법 |
| US6931514B2 (en) | 2000-11-29 | 2005-08-16 | Nec Corporation | Data dependency detection using history table of entry number hashed from memory address |
| US7418583B2 (en) | 2000-11-29 | 2008-08-26 | Nec Corporation | Data dependency detection using history table of entry number hashed from memory address |
| JP2005285122A (ja) * | 2004-03-24 | 2005-10-13 | Microsoft Corp | マルチスレッド化されたプログラムにおける潜在的な競合を検出するための方法およびシステム |
| KR101143214B1 (ko) | 2004-03-24 | 2012-05-18 | 마이크로소프트 코포레이션 | 멀티스레드된 프로그램에서의 잠재적 레이스를 검출하기위한 방법 및 시스템 |
| JP2009032197A (ja) * | 2007-07-30 | 2009-02-12 | Fujitsu Microelectronics Ltd | ソフトウェアのシミュレーション方法、ソフトウェアのシミュレーションのためのプログラム、及びソフトウェアのシミュレーション装置 |
Also Published As
| Publication number | Publication date |
|---|---|
| EP0864975A2 (en) | 1998-09-16 |
| US6009269A (en) | 1999-12-28 |
| CA2231597A1 (en) | 1998-09-10 |
| EP0864975A3 (en) | 2007-10-03 |
Similar Documents
| Publication | Publication Date | Title |
|---|---|---|
| US6009269A (en) | Detecting concurrency errors in multi-threaded programs | |
| Pozniansky et al. | MultiRace: efficient on‐the‐fly data race detection in multithreaded C++ programs | |
| Pozniansky et al. | Efficient on-the-fly data race detection in multithreaded C++ programs | |
| KR101143214B1 (ko) | 멀티스레드된 프로그램에서의 잠재적 레이스를 검출하기위한 방법 및 시스템 | |
| Adve et al. | Detecting data races on weak memory systems | |
| Perkovic et al. | Online data-race detection via coherency guarantees | |
| Chakrabarti et al. | Atlas: Leveraging locks for non-volatile memory consistency | |
| US6854108B1 (en) | Method and apparatus for deterministic replay of java multithreaded programs on multiprocessors | |
| US6817009B2 (en) | Method and apparatus for verifying data local to a single thread | |
| US7752605B2 (en) | Precise data-race detection using locksets | |
| US20020120428A1 (en) | Topological, on-the-fly classification of objects into a global set and local sets | |
| US10241894B2 (en) | Data-scoped dynamic data race detection | |
| US20090199162A1 (en) | Method and apparatus for efficient and precise datarace detection for multithreaded object-oriented programs | |
| JP2009523271A (ja) | ソフトウェアトランザクショナルメモリ動作の最適化 | |
| Sack et al. | Accurate and efficient filtering for the intel thread checker race detector | |
| US20110029819A1 (en) | System and method for providing program tracking information | |
| US7844977B2 (en) | Identifying unnecessary synchronization objects in software applications | |
| Ceze et al. | Colorama: Architectural support for data-centric synchronization | |
| Christiaens et al. | TRaDe: Data race detection for Java | |
| Pyla et al. | Avoiding deadlock avoidance | |
| Luchangco et al. | On the uncontended complexity of consensus | |
| Jenke et al. | Mapping high-level concurrency from OpenMP and MPI to ThreadSanitizer Fibers | |
| Ronsse et al. | Non-intrusive on-the-fly data race detection using execution replay | |
| Edelson | Fault interpretation: fine-grain monitoring of page accesses | |
| Yu et al. | Facilitating Bug Detection for OpenMP Offloading Applications |
Legal Events
| Date | Code | Title | Description |
|---|---|---|---|
| A621 | Written request for application examination |
Free format text: JAPANESE INTERMEDIATE CODE: A621 Effective date: 20041119 |
|
| A977 | Report on retrieval |
Free format text: JAPANESE INTERMEDIATE CODE: A971007 Effective date: 20061117 |
|
| A131 | Notification of reasons for refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A131 Effective date: 20061127 |
|
| A601 | Written request for extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A601 Effective date: 20070227 |
|
| A602 | Written permission of extension of time |
Free format text: JAPANESE INTERMEDIATE CODE: A602 Effective date: 20070302 |
|
| A521 | Written amendment |
Free format text: JAPANESE INTERMEDIATE CODE: A523 Effective date: 20070528 |
|
| A02 | Decision of refusal |
Free format text: JAPANESE INTERMEDIATE CODE: A02 Effective date: 20071009 |