JP4550892B2 - マネージドランタイム環境におけるスレッド同期方法および装置 - Google Patents

Description

本開示内容は、概して、コンピュータに関する。本開示内容は、特に、マネージドランタイム環境におけるスレッド同期方法および装置に関する。

例えば、ＪＡＶＡおよびヨーロッパ電子計算機工業会（ＥＣＭＡ）共通言語基盤（ＣＬＩ）のような、マルチスレッドアプリケーションをサポートするソフトウェア環境は、概して、１つ以上のスレッドがオブジェクトにアクセスした場合に調整するための同期機構を含む。通常の技術を有する当業者が理解するように、スレッドは、１つ以上のオブジェクトを処理するために単一の実行制御フローに組織された一連のプロセッサ命令群を指す。オブジェクトは、クラスのインスタンスである。クラスは、データおよびそのようなデータを操作するメソッドの集合である。複数のスレッドが実行される場合、複数のスレッドは、オブジェクトをエラー状態にする形で同一オブジェクトを同時に変更しないように、制御される必要がある。特に、スレッドは、他のスレッドによって同時にアクセスされうるオブジェクトを操作する、クリティカルセクションを有することができる。このため、クリティカルセクションの実行中に１つ以上の他のスレッドがそのような共有オブジェクトにアクセスすることによってクリティカルセクションの処理がエラーになることを防ぐために、マルチスレッドシステムは、概して、専用のステートメントを提供する。

例えば、ＪＡＶＡソースコードは、オブジェクトが他のスレッドによって同時にアクセスされることを防ぐために、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントを含んでもよい。ｓｙｎｃｈｒｏｎｉｚｅｄステートメントの適用は、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントによって指定されたオブジェクトの排他ロックの取得を可能にする。そのため、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントによって指定された特定のオブジェクトの排他ロックが取得されるまで、スレッドは、コードのクリティカルセクションを実行しないように制御されうる。更に、そのようなロックが取得されると、他のスレッドがロックされたオブジェクトにアクセスできないため、コードのクリティカルセクションの実行中における処理は、偶発的なエラーから守られる。そのようなロック手続は、複数のスレッドがコードのクリティカルセクション実行の干渉を生じうる形で同時に共有オブジェクトにアクセスできないことを保証するために、使用されうる。当然のことながら、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントの適用は、概して、特定のプログラムがオブジェクトおよび／またはメソッドを共有する複数のスレッドを生成する場合に使用される。１つのスレッドのみが特定のオブジェクトおよび／またはメソッドにアクセスする場合、オブジェクトおよび／またはメソッドがｓｙｎｃｈｒｏｎｉｚｅｄステートメントで保護される必要はない。

当技術分野で周知のように、ＪＡＶＡソースコードは、ＪＶＭによって実行される前にまず、バイトコード（即ち、ＪＶＭ言語）に変換されるため、ＪＡＶＡソースコード内のｓｙｎｃｈｒｏｎｉｚｅｄステートメントは、概して、ＪＡＶＡ仮想マシン（ＪＶＭ）命令群に変換される。例えば、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントは、オブジェクトの排他ロックを獲得／取得するために、ｍｏｎｉｔｏｒｅｎｔｅｒ ＪＶＭ命令に変換されうる。ｍｏｎｉｔｏｒｅｎｔｅｒ命令を補完するものとして、オブジェクトの排他ロックをアンロック／解放するために、ｍｏｎｉｔｏｒｅｘｉｔ ＪＶＭ命令が、提供される。これにより、スレッドがオブジェクトに対するｍｏｎｉｔｏｒｅｎｔｅｒ命令の実行に成功した場合、スレッドは、オブジェクトの一時的な排他ロック所有権を取得する（即ち、スレッドは、他のスレッドがコードのクリティカルセクションにアクセスすることを防ぐために、オブジェクトのロックを取得した）。第１のスレッドがオブジェクトの一時的な排他所有権を有する間に、他のスレッドまたは第２のスレッドが同一のオブジェクトに対してｍｏｎｉｔｏｒｅｎｔｅｒ命令の実行を試みた場合、第２のスレッドは、第１のスレッド（即ち、現在のロックオーナー）がオブジェクトの排他ロックを解放するためにｍｏｎｉｔｏｒｅｘｉｔ命令を実行するまで、待機（例：スリープまたはスピン）する必要がある。

オブジェクトのロック状態を示すために、概して、２つの状態変数が使用される。第１の状態変数は、現在ロックを所有するスレッドのスレッド識別子に対応する、ロックオーナーである。ロックがいかなるスレッドによっても所有されていない場合、ロックオーナーは、ＮＵＬＬ値またはＮＵＬＬスレッドに設定されうる。第２の状態変数は、ロックオーナーがロックを取得した回数を示すために使用されうる、ロック再帰カウンタである（再帰ロックをサポートするため）。概して、オブジェクトのロック状態は、ＮＵＬＬ値（アンロック状態に相当）に等しいロックオーナーと、０に等しいロック再帰カウンタとを有するように初期化される。

多くの従来技術のオブジェクトロック技術（例：ＪＶＭｍｏｎｉｔｏｒｅｎｔｅｒおよびｍｏｎｉｔｏｒｅｘｉｔ命令群の従来技術における実装）では、ロック解放関数（例：ｍｏｎｉｔｏｒｅｘｉｔ命令に相当）は、ロックの解放を試みるスレッドが実際にロックのロックオーナーであるかどうかを決定する。更に、ロック解放関数は、ロックがアンロックされるべきか、または、維持（例：複数の再帰ロック取得により、ロック状態に維持される）されるべきかを決定するために、ロック再帰カウンタを確認する。しかしながら、高級言語（例：ＪＡＶＡ（登録商標））を用いて書かれ、後にバイトコードにコンパイルされる、多くの良好に形成されたアプリケーションは、ロック取得および解放操作の対応するペア（例：ｍｏｎｉｔｏｒｅｎｔｅｒおよびｍｏｎｉｔｏｒｅｘｉｔＪＶＭ命令群の対応するペア）を含むため、均衡同期の性質を示す（即ち、ロックシーケンスは、同一のスレッドによって実行される、均衡なロック取得および解放のペアを含む）。均衡同期の性質を示すコードにおいては、ロックオーナーおよびロック再帰カウンタ状態変数を確認する追加の負荷は、不必要であるため、アプリケーション実行の全体的な効率を悪化させうる。
米国特許第６０５２６９５号明細書 米国特許出願公開第２００５／０１４４１７０号明細書

本願明細書で開示される方法、装置、および製品の例が使用されうる、マネージドランタイム環境例を示すブロック図である。

図１のマネージドランタイム環境において使用されうるロックマネージャの例を示すブロック図である。

図１のマネージドランタイム環境において使用されうる従来技術のロックマネージャの例を実装するために、装置によって実行されうるマシン読み取り可能な命令群の例を示す第１のフロー図である。 図１のマネージドランタイム環境において使用されうる従来技術のロックマネージャの例を実装するために、装置によって実行されうるマシン読み取り可能な命令群の例を示す第２のフロー図である。

図２のロックマネージャ例を実装するために装置によって実行されうるマシン読み取り可能な命令群の例を示すフロー図である。

図２の均衡ロック同期部の例および楽観的均衡ロック同期部の例をそれぞれ実装するために、装置によって実行されうるマシン読み取り可能な命令群の例を示す第１のフロー図である。 図２の均衡ロック同期部の例および楽観的均衡ロック同期部の例をそれぞれ実装するために、装置によって実行されうるマシン読み取り可能な命令群の例を示す第２のフロー図である。

図２の非均衡ロック取得部の例を実装するために、装置によって実行されうるマシン読み取り可能な命令群の例を示す第１のフロー図である。 図２の非均衡ロック取得部の例を実装するために、装置によって実行されうるマシン読み取り可能な命令群の例を示す第２のフロー図である。

図２の非均衡ロック解放部の例を実装するために、装置によって実行されうるマシン読み取り可能な命令群の例を示すフロー図である。

図６Ａ、図６Ｂ、および図７のプロセスによって使用される待機中の均衡解放の状態を決定するために、装置によって実行されうるマシン読み取り可能な命令群の例を示すフロー図である。

図６Ａ、図６Ｂ、および図７のプロセスによって使用される待機中の均衡解放の状態を変更するために、装置によって実行されうるマシン読み取り可能な命令群の例を示すフロー図である。

図２のロックマネージャの動作例を示す第１の図である。 図２のロックマネージャの動作例を示す第２の図である。

図２のロックマネージャを実装するために図４から図９のプロセスを実行するプロセッサシステムの例を示す図である。

本願明細書において説明される方法、装置、および製品の例が使用されうる、例示の使用環境１００のブロック図が、図１に示される。例示の使用環境１００は、例えば、以下に説明される図１１の例示のプロセッサシステム１１００のような、１つ以上のプロセッサシステムによって、実装されうる。図１の例はＪＡＶＡベースのマネージドランタイム環境（ＭＲＴＥ）に対応するが、通常の技術を有する当業者は、本願明細書において説明される例示の方法、装置、および製品が、例えばＣＬＩおよびそれに関連するＣ＃言語のような、類似のＭＲＴＥ使用環境に対しても適用されうることを理解するであろう。

例示の使用環境１００は、図１においてＪＡＶＡ仮想マシン（ＪＶＭ）１１０として示される、ＭＲＴＥを含む。例示のＪＶＭ１１０は、マシン非依存命令群またはバイトコード１１４によって表現されるプログラムを、マシン依存またはネイティブ命令群に動的に変換し、１つ以上の（以下に説明されるプロセッサ１１１２のような）プロセッサ１２０上でネイティブ命令群を実行する。ＪＶＭ１１０は、１つ以上のプロセッサ１２０に特有の、Ｍｉｃｒｏｓｏｆｔ Ｗｉｎｄｏｗｓ ＯＳ、ＵＮＩＸ ＯＳ、Ｌｉｎｕｘ ＯＳなどのようなオペレーティングシステム（ＯＳ）を介して、ネイティブ命令群を実行しうる。

図１の例においては、ＪＶＭ１１０は、複数のクラスファイル１１４に格納されたバイトコード１１４を処理する。概して、クラスファイル１１４は、クラスを定義するインタフェース、フィールド、およびメソッドを含む、１つのＪＡＶＡクラスに対応するバイトコード１１４を格納する。クラスファイル１１４は、ＪＡＶＡコンパイラ１３４によって、例えばソフトウェア開発者によって書かれたＪＡＶＡプログラムソースコード１３８から作成される。ＪＡＶＡコンパイラ１３４、関連するＪＡＶＡソースコード１３８、および結果として生じるクラスファイル１１４（またはバイトコード１１４）は、当技術分野において周知であり、本願明細書では説明されない。

クラスファイル１１４を処理することを目的として、例示のＪＶＭ１１０は、１つ以上の特定のクラスに対応する１つ以上の特定のクラスファイル１１４を見つけるため、および、例えばロードされたクラスファイル１１４のローカルイメージをローカルメモリ１４６に格納することによってそのようなクラスファイル１１４をＪＶＭ１１０の実行エンジン１４４にロードするために、クラスローダ１４２を含む。ロードされたクラスファイル１１４をメモリ１４６に格納する前に、クラスローダ１４２は、ロードされたクラスファイル１１４の構成が正常でありかつＪＡＶＡ言語の構成に準拠していることを確認するために、バイトコード確認部１５０を呼び出してもよい。いずれの場合においても、ＪＶＭ１１０の実行エンジン１４４は、その後、例えばインタープリタ１５４および／または１つ以上のＪｕｓｔ−Ｉｎ−Ｔｉｍｅ（ＪＩＴ）コンパイラ１５８を用いて、ロードされたマシン非依存バイトコードをマシン依存命令群に変換する。

インタープリタ１５４は、バイトコード１１４を、１つまたは複数のターゲットプロセッサ１２０上においてバイトコード１１４の機能を実装するマシン依存命令群のセットに変換する。換言すると、インタープリタ１５４は、１つまたは複数のプロセッサ１２０がＪＡＶＡ命令セットを直接サポートしているかのように、バイトコード１１４が１つまたは複数のターゲットプロセッサ１２０上で実行されることを可能にする、エミュレーションレイヤを提供する。一方、ＪＩＴコンパイラ１５８は、バイトコード１１４のセットを、１つまたは複数のターゲットプロセッサ１２０上で実行するために、マシン依存命令群のセットにコンパイルする。個々のバイトコード１１４の特定の機能は、マシン依存命令群に厳密にそのまま変換されない可能性があるが、結果として生じるマシン依存命令群セットの全体的な機能は、バイトコード１１４の元のセットと同等である。従って、ＪＩＴコンパイラ１５８は、インタープリタ１５４より最適なコードを生成しうる。しかしながら、インタープリタ１５４は、ＪＩＴコンパイラ１５８より実装が容易でありうる。

インタープリタ１５４および／または１つ以上のＪＩＴコンパイラ１５８によって提供されるプログラムコードを実行するために、ＪＶＭ１１０の実行エンジン１４４は、ローカルメモリ１４６内に１つ以上のストレージエリアを定義しうる。例えば、複数のスレッドの同時実行をサポートするために、ＪＶＭ１１０は、メモリ１４６内に、各スレッドに対して専用の仮想プログラムカウンタ（ｐｃ）レジスタおよび専用のＪＶＭスタックフレームを割り当てうる。ＪＶＭスタックフレームは、例えば、関連する実行スレッドに対応するローカル変数群および部分結果群を格納するために使用される。更に、ＪＶＭ１１０は、全スレッドに共通のストレージエリアをローカルエリア１４６内に定義しうる。例えば、そのようなストレージエリアは、プログラム実行中に生成されるオブジェクトを格納するためのヒープ、例えば特定のクラスのメソッドを実装するために使用されるデータおよびコードを格納するためのメソッドエリア、および、特定のクラスに関連する定数群を格納するためのランタイム定数プールを含んでもよい。メモリ１４６のランタイム部分を効率的に管理することを目的として、ＪＶＭ１１０は、例えば、ヒープからオブジェクトの割り当てを自動的に解除して次のプログラムの実行のためにメモリを解放する、ガーベッジコレクタ１６２を含んでもよい。

複数のスレッド群の同時実行をサポートするために、ＪＶＭ１１０の実行エンジン１４４は、スレッドサポートモジュール１６６を含む。スレッドサポートモジュール１６６は、スレッドオブジェクトの生成によるスレッドの生成、および、スレッドのスタートメソッドの呼び出しによるスレッドの実行をサポートする。更に、スレッドサポートモジュール１６６は、様々な優先度の使用によって優先的なスレッド群の実行をサポートしうる。本開示において特に注目する、ＪＶＭ１１０の実行エンジン１４４は、また、２つ以上のスレッドが同一の共有オブジェクトにアクセスを図った場合に起こりうる干渉を解決するために、ロックマネージャ１７０を含む。

例示のＪＶＭ１１０に対応する業界標準仕様（および他のマネージドランタイム環境の仕様）は、複数のスレッド間におけるオブジェクトの同期をサポートするために、手続を定義する。ＪＶＭ１１０は、各オブジェクトに対する同期ロックを提供する。スレッドは、オブジェクトに関連するロックの所有権を取得することによって、オブジェクトの所有権を取得しうる。同様に、スレッドは、オブジェクトに関連するロックの所有権を解放することによって、オブジェクトの所有権を解放しうる。ＪＡＶＡプログラム言語においては、オブジェクトおよびメソッドの同期は、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントによって実装される。ＪＶＭ１１０の仕様は、ｍｏｎｉｔｏｒｅｎｔｅｒおよびｍｏｎｉｔｏｒｅｘｉｔバイトコードによって、ロック取得および解放操作をそれぞれ定義する。しかしながら、ｍｏｎｉｔｏｒｅｎｔｅｒおよびｍｏｎｉｔｏｒｅｘｉｔバイトコードの実装は、定義されない。

図１の例示のロックマネージャ１７０を実装するために使用されうる例示のロックマネージャ２００のブロック図は、図２に示される。例示のロックマネージャ２００は、ロック取得およびロック解放の大部分が均衡または楽観的均衡であるという仮定に基づいて、スレッドに対してオブジェクトのロックを取得および解放する。例えば、ロックマネージャ２００は、ロックの取得および解放操作が同一のネストレベルで起こり、かつ、コードのクリティカルセクションが同期操作を含んでいない操作の間またはロックに対する他の均衡同期操作のみを含む操作の間にある場合は、ロックの取得および解放操作の組は均衡であると決定しうる（例：スレッドは、オブジェクトのロックを取得し、プログラムコードのクリティカルセクションを実行し、その後、オブジェクトのロックを解放する）。同様に、ロックマネージャ２００は、ロックの取得および解放操作の組が同一のネストレベルで起こるが全ての操作が均衡であることは確実であると確定できない場合（例：コードのクリティカルセクションがメソッド呼び出しを含む場合）、ロックの取得および解放操作の組は楽観的均衡であると決定する。高級言語（例：ＪＡＶＡ）で書かれ、後にバイトコード（例：バイトコード１１４）にコンパイルされる、良好に形成されたプログラムの多くは、均衡同期の性質を示す（即ち、上記において説明された均衡な取得および解放のペアを含む同期）。しかしながら、まれに、ロック取得または解放は、均衡ではないことがある（例：バイトコードを用いてマニュアルで書かれて実装されたプログラムの場合）。これに応じて、均衡および楽観的均衡ロック処理手続に加えて、ロックマネージャ２００は、オブジェクトのロックを取得および解放するために、それぞれ非均衡取得および解放手続を使用しうる。

図２が示すように、ロックマネージャ２００は、実行中のスレッドからオブジェクト識別子入力２０８およびスレッドコンテキスト入力２１２を受信する、ロック同期コントローラ２０４を含む。オブジェクト識別子入力２０８は、同期されるオブジェクトを識別するために使用され、ユニークなオブジェクトインスタンス識別子、オブジェクトのｌｏｃｋｗｏｒｄなどを含んでもよい。スレッドコンテキスト入力２１２は、オブジェクト識別子入力２０８によって指定されるオブジェクトをロックまたはアンロックすることを求めるスレッドの識別、スレッドの動作状態、および、オブジェクトのロックの際に実行する関連操作（例：ロックの取得またはロックの解放、および、そのロックの取得および／または解放が均衡、楽観的均衡、または非均衡であるかどうかを取得）を示すために使用される。ロック同期コントローラ２０４は、オブジェクトのロックの状態（例：最初の取得、再帰取得、解放／アンロック、例外発生、など）を示す、オブジェクトロック状態出力２１６を提供する。

更に、ロック同期コントローラ２０４は、オブジェクト識別子入力２０８によって特定されるオブジェクトのロックに対して実行されるロック操作のタイプに基づき、特定のロック操作部を呼び出す。ロック操作タイプの例は、均衡ロック同期、楽観的均衡ロック同期、非均衡ロック取得、および非均衡ロック解放を含む。ロック同期コントローラ２０４は、スレッドコンテキスト入力２１２によって提供される情報に基づき、ロック操作タイプを決定しうる。そのような情報は、例えば、バイトコード１１４から、スレッドコンテキスト入力２１２によって特定されるスレッドによって実行されるマシン依存命令のセットへの変換の一部として、図１のインタープリタ１５４および／またはＪＩＴコンパイラ１５８によって決定されうる。

オブジェクトの均衡ロック同期（即ち、均衡ロック取得とそれに続く対応する均衡ロック解放）を実行するために、例示のロックマネージャ２００は、均衡ロック同期部２１８を含む。ロック同期コントローラ２０４が、（例：オブジェクト識別子入力２０８およびスレッドコンテキスト入力２１２に基づき、）オブジェクトに対して均衡同期が実行されるべきであると決定した場合、均衡ロック同期部２１８は、スレッドがオブジェクトのロックを既に取得しているかどうかを決定する。目的とするオブジェクトのロックが使用可能である場合（または、要求側スレッドによってすでに所有されている場合）、均衡ロック同期部２１８は、ロックの現在の状態を格納し、スレッドに対してロックを取得する。ロックが使用不可能である場合、均衡ロック同期部２１８は、ロックが使用可能になった後にスレッドに対してロックを取得するために、既知のロック競合手続を呼び出す（既知のロック競合手続は、競合処理の完了後にロックの表現／フォーマットを変更しない、または、ロックを元の表現／フォーマットに戻さないという制約がある）。いずれの場合においても、均衡ロック同期部２１８は、その後、オブジェクトロックが取得されたことを示すために、ロック同期コントローラ２０４にロック状態出力２１６を更新させる。スレッドがロックされたオブジェクトを必要とするコードの実行を完了した後（例：スレッドコンテキスト入力２１２によって示される）、均衡ロック同期部２１８は、ロックを以前の状態に戻すことによってオブジェクトのロックを解放するように指示され、それに応じて、ロック同期コントローラ２０４にオブジェクトロック状態出力２１６を更新させる。

オブジェクトの楽観的均衡ロック同期を実行するために、例示のロックマネージャ２００は、楽観的均衡ロック同期部２２０を含む。楽観的均衡ロック同期部２２０は、均衡ロック同期部２１８と同じように動作する。図５Ｂを参照して以下に説明されるように、楽観的均衡ロック同期部２２０は、楽観的均衡ロック取得が実行された後に起こりうる非均衡ロック取得および／または解放から回復するために、フォールバック手段を用いる。フォールバック手段の例は、非均衡ロック操作が、楽観的均衡ロック取得の後、かつ、対応する楽観的均衡ロック解放の前（即ち、楽観的均衡ロック取得がアクティブの間）に発生したかどうかを示す、フラグまたは他のインジケータに基づく。それに応じて、そのようなフラグまたは他のインジケータは、楽観的均衡ロック同期部２２０が、対応する楽観的均衡解放操作を変更することを可能にする。単一スレッドによる再帰ロックの取得をサポートするために、楽観的均衡ロック同期部２２０は、あるオブジェクトに対する全ての待機中の楽観的均衡ロック解放の状態をトラックするために、同期マップを含む。

非均衡ロック取得または非均衡ロック解放を実行するために、ロックマネージャ２００は、非均衡ロック取得部２２４および非均衡ロック解放部２２８をそれぞれ含む。ロック同期コントローラ２０４が、（例：スレッドコンテキスト入力２１２に基づいて）オブジェクトに対して非均衡ロック取得が実行されるべきであると決定した場合、非均衡ロック取得部２２４は、ロックが使用可能である場合（または、スレッドによってすでに所有されている場合）、スレッドに対してオブジェクトのロックを取得する、または、ロックが使用不可能である場合、既知のロック競合手続を呼び出す（既知のロック競合手続は、競合処理が完了した後に、ロックの表現／フォーマットを変更しない、または、ロックを元の表現／フォーマットに戻さない制約がある）。ロック同期コントローラ２０４が、オブジェクトに対して非均衡解放が実行されるべきと決定した場合、ロックが現在スレッドによって所有されている場合、非均衡ロック解放部２２８は、オブジェクトのロックを解放／アンロックする。ロックがスレッドによって所有されていない場合、非均衡ロック解放部２２８は、不正なロック解放が試みられたことを示す例外を発生させる。そして、ロック取得またはロック解放が実行されたかどうかに応じて、非均衡ロック取得部２２４または非均衡ロック解放部２２８は、それぞれ、オブジェクトロックの適切な状態を示すために、ロック同期コントローラ２０４にロック状態出力２１６を更新させうる。

非均衡ロック取得部２２４および非均衡ロック解放部２２８の両方は、楽観的均衡ロック同期部２２０によって格納された、待機中の解放の同期マップを変更する必要がある場合がある。例えば、楽観的均衡ロック取得の後に実行される非均衡ロック取得は、次の楽観的均衡解放が実際にはロックを維持することを必要としうる（余分なロック取得による）。他の例においては、楽観的均衡ロック取得の後、かつ、次の楽観的均衡ロック解放の前に実行された非均衡ロック解放は、楽観的均衡ロック解放がロックを解放するのではなく、例外を発生させることを必要としうる（非均衡ロック解放によってロックが解放された後に実行される、ロックに対する余分のロック解放による）。従って、楽観的均衡ロック同期部２２０によって維持される同期マップを更新するために、例示のロックマネージャ２００は、楽観的均衡同期状態変更部２３６を含む。楽観的均衡同期状態変更部２３６は、待機中の楽観的均衡解放の状態を正常な状態（例：アンロック状態またはロック維持状態）または不正な状態（例：不正な解放／例外発生状態）に変更するように設定されうる。楽観的均衡同期状態変更部２３６は、実行されたロック操作（即ち、非均衡取得または非均衡解放）および以前の非均衡ロック操作の履歴に基づいて、それぞれ、非均衡ロック取得部２２４または非均衡ロック解放部２２８のいずれかによって呼び出されうる。例えば、非均衡ロック解放は、同期マップ内の楽観的均衡解放が変更される必要がないように、非均衡ロック取得と結び付けられる。

例示のロックマネージャ２００は、また、楽観的均衡ロック同期部２２０によって格納された同期マップを処理するために、楽観的均衡解放トラック部２３２を含む。楽観的均衡解放トラック部２３２は、例えば、同期マップ内に格納された正常な楽観的均衡解放（例：ロックのアンロック、または、再帰ロック取得の場合におけるロックの維持に対応する解放）の数を決定するように設定されうる。楽観的均衡解放トラック部２３２は、また、同期マップ内に格納された不正な楽観的均衡解放（例：例外を発生させる不正な（余分な）解放に対応する均衡解放）の存在の有無を決定しうる。楽観的均衡解放トラック部２３２は、同期マップに関するこれらの統計を提供して、非均衡ロック取得部２２４および／または非均衡ロック解放部２２８が楽観的均衡同期状態変更部２３６を正しく呼び出せるようにしている。

図１のロックマネージャ１７０を実装することを目的とした、既知のマシン読み取り可能な命令群のフロー図表現が、図３Ａおよび図３Ｂに示される。図１のロックマネージャ１７０および／または図２のロックマネージャ２００を実装することを目的とした、開示される例示のマシン読み取り可能な命令群のフロー図表現は、図４から図９に示される。図４から図９の例においては、各フロー図によって表現される処理は、図１１と関連して以下に説明される例示のコンピュータ１１００において図示されるプロセッサ１１１２のようなプロセッサによって実行される、１つ以上のプログラムを構成しうるマシン読み取り可能な命令群のセットによって実装されうる。１つ以上のプログラムは、ＣＤ−ＲＯＭ、フロッピーディスク、ハードディスクドライブ、ＤＶＤ、または、プロセッサ１１１２に関連するメモリのような有形媒体に格納されたソフトウェアに埋め込まれてもよい。しかしながら、通常の技術を有する当業者は、代替的に、プログラム全体および／またはその一部分が、プロセッサ１１１２以外のデバイスによって実行されうること、および／または、周知の方法でファームウェアまたは専用ハードウェアに組み込まれうることを理解するであろう。例えば、ロックマネージャ１７０および／またはロックマネージャ２００は、ソフトウェア、ハードウェア、および／またはファームウェアのいかなる組合せによっても実装されうる。更に、例示のプログラムは図４から図９に示されるフロー図を参照して説明されるが、通常の技術を有する当業者は、本願明細書において説明される例示の方法および装置を実装する多くの他の方法が代替的に使用されうることを理解するであろう。例えば、図４から図９に示されるフロー図を参照すると、実行ブロックの順序は変更されてもよく、および／または、説明されるいくつかのブロックは、変更、削除、統合、および／または複数のブロックに分割されてもよい。

図２に示される例示のロックマネージャ２００のプロパティおよび性質をより良く理解するため、および、下記の図４から図９のフロー図によって示される種々の処理の動作をより良く理解するために、図１のロックマネージャ１７０を実装する例示の従来技術の処理が、図３Ａから図３Ｂに示される。特に、図３Ａは、オブジェクトのロックを取得することを目的とした例示の従来技術の処理３００を示し、図３Ｂは、オブジェクトのロックを解放することを目的とした例示の従来技術の処理３５０を示す。図示されないが、制御処理は、実行中のプログラムスレッドの状態に基づきロック取得およびロック解放手続のいずれが呼び出されるべきかを決定するために、使用されうる。

図３Ａを参照すると、例示の従来技術のロック取得処理３００は、ロックされるオブジェクトに関連するロックの以前のロックオーナーに対応する変数／レジスタを、ロックの現在のロックオーナーに等しくなるように設定することによって、開始する（ブロック３０２）。そして、処理３００は、まず、ロックされるオブジェクトのロックを既に所有しているスレッドが存在するかどうか（即ち、オブジェクトのロックオーナーが存在するかどうか、または、ロックオーナーがＮＵＬＬ値に設定されているかどうか）を決定することによって、現在のスレッド（即ち、ロックを要求するスレッド）に対してオブジェクトのロックを試みる（ブロック３０４）。処理３００が、スレッドオーナーが存在しないと決定し（ブロック３０４）、それによってオブジェクトのロックはアンロックであると決定した場合、処理３００は、ロックオーナーを、スレッドを示す値（例：ユニークなスレッド識別子の値）に設定することによって、スレッドに対してロックを取得する（ブロック３０８）。しかしながら、処理３００がロックオーナーは既に存在すると判断した場合（ブロック３０４）、処理３００は、ロックオーナーを変更しない。第１のスレッドが既にロックオーナーになるための処理に入っているときに第２スレッドがロックの取得を図ることを防ぐために、ブロック３０２、３０４および３０８は、概して、単一のアトミック操作（Ｉｎｔｅｌ Ｉｔａｎｉｕｍプロセッサファミリに属するプロセッサ上のｃｍｐｘｃｈｇ命令など）を用いて実装される。アトミック操作は、アトミック操作の実行中、スレッド（および／またはマルチプロセッサシステムのプロセッサ）に、共有メモリへの排他アクセスを提供する。従って、他のスレッドは、その実行の間、アトミック操作によってアクセスされているメモリロケーションを変更できない。

ロックオーナーがＮＵＬＬでない（ブロック３０４）またはロックオーナーが現在のスレッドとして定義されている（ブロック３０８）と決定された後、処理３００は、オブジェクトの以前のロックオーナーがＮＵＬＬ値（現在のスレッドがブロック３０８においてロックを取得した場合に対応）であるかどうかを決定する（ブロック３１２）。以前のロックオーナーがＮＵＬＬ値である場合（ブロック３１２）、例示の処理３００は、終了する。しかしながら、処理３００が以前のロックオーナーはＮＵＬＬ値でないと決定した場合（ブロック３１２）、処理は、以前のロックオーナーが現在のスレッドかどうかを決定する（現在のスレッドが既にロックを取得していた場合に相当）（ブロック３１４）。以前のロックオーナーが現在のスレッドである場合（ブロック３１４）、処理３００は、例えば、現在のスレッドがオブジェクトのロックを複数回取得したことを示すために、ロックに関連するロック再帰カウンタをインクリメントしうる（ブロック３１６）。そして、処理例３００は、終了する。

しかしながら、処理３００が以前のロックオーナーは現在のスレッドでないと決定し（ブロック３１４）、従って、他のスレッドが既にロックを所有していると決定した場合、処理３００は、現在のロックオーナーがロックを解放した後に現在のスレッドがロックを取得することを可能にするために、既知のロック競合手続を呼び出す（ブロック３２０）。例えば、処理３００は、現在のロックオーナーがオブジェクトのロックを解放／アンロックするまで、現在のスレッドにループを実行させてもよい、または、実行をｈａｌｔさせてもよい。オブジェクトのロックが使用可能になった後、処理３００は、現在のスレッドに対してロックを取得する。そして、例示の処理３００は、終了する。

図３Ｂを参照すると、例示の従来技術のロック解放処理３５０は、まず現在のスレッドがオブジェクトのロックオーナーであるかどうかを決定することによって、現在のスレッド（即ち、解放を要求するスレッド）に対してオブジェクトの解放を試みることによって開始する（ブロック３５４）。現在のスレッドがロックオーナーではなく、従って、他のスレッドが現在ロックを所有している場合（ブロック３５４）、処理３５０は、例外を発生させる（ブロック３５８）。ブロック３５８において、処理３５０は、不正な解放の試みが実行されたこと（ロックを所有していないスレッドが、関連するオブジェクトのアンロックを試みたため）を示す例外を発生させるために、既知の例外処理技術を使用しうる。そして、例示の処理３５０は、終了する。

しかしながら、現在のスレッドがオブジェクトのロックオーナーである場合（ブロック３５４）、処理３５０は、ロックに関連するロック再帰カウンタ（または、類似の再帰ロックインジケータ）が０に等しいかどうか（または同様に、ロックが現在アクティブの取得を１つだけ有することを示すかどうか）を決定する（ブロック３６２）。ロック再帰カウンタが０に等しい場合（ブロック３６２）、処理３５０は、例えばロックオーナーをＮＵＬＬ値に設定することによって、オブジェクトのロックをアンロックする（ブロック３６６）。しかしながら、ロック再帰カウンタが０に等しくない場合（ブロック３６２）、処理３５０は、ロック再帰カウンタをデクリメントする（例：現在のロック解放がアクティブなロック取得に相殺されることを示すため）（ブロック３７０）。ブロック３６６またはブロック３７０における処理の完了後、例示の処理３５０は、終了する。

図３Ａから図３Ｂに示される例示の従来技術の処理３００および３５０によって提供される理解に基づき、図２に示される例示のロックマネージャ２００の実装に使用されうる例示のロックマネージャ処理４００が、図４に示される。例示のロックマネージャ処理４００は、例えば、同期オブジェクトを操作する１つ以上のスレッドの様々な実行ステージ中において、呼び出されうる。例えば、例示の処理４００は、オブジェクトのロックを取得または解放するために、呼び出されうる。

例示のロックマネージャ処理４００は、オブジェクトをロックする際に現在のスレッドに対してどのタイプのロック操作を実行するかを決定することによって、開始する。（ブロック４０４）。正常なロック操作は、均衡ロック同期（均衡ロック取得および解放のペアを含む）、楽観的均衡ロック同期（楽観的均衡ロック取得および解放のペアを含む）、非均衡ロック取得、および非均衡ロック解放を含んでもよい。例えば、図１のＪＩＴコンパイラ１５８のようなＪＩＴコンパイラは、プログラム実行中の適切なポイントにおいてオブジェクトのロックに対して実行するロック操作のタイプを決定するために、制御フローグラフおよび／またはデータフロー分析を使用しうる。そして、ＪＩＴコンパイラ１５８は、ブロック４０４においてロック操作の決定を適切に行うためにロックマネージャ２００またはロックマネージャ処理４００によって使用されうる、コンパイルされたコードを出力する。ロック操作が均衡、楽観的均衡、または非均衡であるかどうかを決定することを目的として既知の技術が例示の処理４００によって使用されうるため、そのような技術は、ここでは説明されない。

ブロック４０４において決定されたロック手続に基づいて、制御は、ブロック４０６、４０８、４１２、および４１６のいずれか１つに進む。ブロック４０６において、ロックマネージャ２００は、オブジェクトのロックに対して均衡同期操作を実行する。ブロック４０８において、ロックマネージャ２００は、オブジェクトのロックに対して楽観的均衡同期操作を実行する。ブロック４１２において、ロックマネージャ２００は、オブジェクトのロックに対して非均衡ロック取得操作を実行する。ブロック４１６において、ロックマネージャ２００は、オブジェクトのロックに対して非均衡ロック解放操作を実行する。ブロック４０６、４０８、４１２、および４１６において実行される処理は、それぞれ、以下に提供される図５Ａ、図５Ｂ、図６、および図７を参照して、詳細に説明される。

ブロック４０６、４０８、４１２、および４１６における処理の完了後、処理４００は、後のスレッド実行ポイントにおいて次の解放を必要とする待機中のオブジェクトが、少なくとも１つ存在するかどうかを決定する（ブロック４２０）。ロックされたオブジェクトが待機中である場合（ブロック４２０）、制御は、そのようなオブジェクトのロック（および、ロックされるべき全ての追加のオブジェクトのロック）が処理されることを可能にするために、ブロック４０４とその後続のブロックに戻る。しかしながら、待機中のロックされたオブジェクトが存在しない場合（ブロック４２０）、処理４００は、ロックすべき追加のオブジェクトが存在するかどうかを決定する（ブロック４２４）。ロックすべき追加のオブジェクトが存在する場合（ブロック４２４）、制御は、そのようなオブジェクトのロックが処理されることを可能にするために、ブロック４０４およびその後続のブロックに戻る。しかしながら、ロックすべき追加のオブジェクトが存在しない場合（ブロック４２４）、例示の処理４００は、終了する。通常の技術を有する当業者は、ブロック４２０および／または４２４において実行される条件処理が、例えば、プログラム（またはプログラムのスレッド）はまだ実行しているかどうかに関する明示的または間接的な決定によって置き換えられうることを認識するであろう。処理４００がまだ実行中である場合、制御は、ブロック４０４および後続のブロック４０６、４０８、４１２、および４１６に戻る。そのような繰り返しは、処理４００（または全スレッドの実行）が完了するまで継続してもよい。

図４のブロック４０６における処理を実行するため、および／または、図２の均衡ロック同期部２１８を実装するために使用されうる例示の均衡ロック同期処理５００は、図５Ａに示される。例示の均衡ロック同期処理５００は、ロックの以前のロックオーナーに対応する変数／レジスタを現在のロックオーナーに等しくなるように設定することによって、開始する（ブロック５０４）。そして、処理５００は、スレッドがロックされるべきオブジェクトのロックを既に所有しているかどうか（即ち、オブジェクトに対してロックオーナーが存在するかどうか、または、ロックオーナーがＮＵＬＬ値に設定されているかどうか）を決定する（ブロック５１２）。スレッドオーナーが存在せず（ブロック５１２）、従ってオブジェクトのロックはアンロックであり、かつ、ロックオーナーがＮＵＬＬ値に設定されている場合、処理５００は、ロックオーナーをスレッドを示す値（例：ユニークなスレッド識別子の値）に設定することによって、スレッドに対してオブジェクトのロックを取得する（ブロック５１６）。しかしながら、処理５００がロックオーナーは既に存在すると決定した場合（ブロック５１２）、処理５００は、ロックオーナーを変更しない。

第１のスレッドが既にロックオーナーになるための処理に入っているときに第２のスレッドがロックの取得を図ることを防ぐために、ブロック５０４、５１２、および５１６は、概して、単一のアトミック操作（Ｉｎｔｅｌ Ｉｔａｎｉｕｍプロセッサファミリに属するプロセッサ上のｃｍｐｘｃｈｇ命令など）を用いて実装される。上記のように、アトミック操作は、アトミック操作の実行中、スレッド（および／またはマルチプロセッサシステムのプロセッサ）に、共有メモリへの排他アクセスを提供する。従って、他のスレッドは、その実行中において、アトミック操作によってアクセスされているメモリロケーションを変更できない。例えば、ブロック５０４、５１２、および５１６において実行される処理は、Ｉｎｔｅｌ Ｉｔａｎｉｕｍプロセッサファミリに属するプロセッサ上において、以下の命令シーケンスに基づいて実装されうる。

ａｒ．ｃｃｖ = ｍｏｖ ０
ｒ１ ＝ ｃｍｐｘｃｈ２．ａｃｑ [ｒ３]， ｒ２

上述の命令群において、レジスタｒ１は、以前のロックオーナーを表現するために使用され、レジスタｒ２は、現在のスレッドを表現するために使用され、また、レジスタｒ３は、現在のロックオーナーに対応するアドレスを保持しうる。第１の命令（ａｒ．ｃｃｖ ＝ ｍｏｖ ０）は、ａｒ．ｃｃｖレジスタを０（即ち、ＮＵＬＬ値）に設定する。第２の命令（ｒ１ ＝ ｃｍｐｘｃｈｇ２．ａｃｑ [ｒ３]，ｒ２）は、（１）以前のロックオーナーを現在のロックオーナーに等しくなるように設定（即ち、ｒ１＝［ｒ３］）し、（２）現在のロックオーナーがＮＵＬＬ値であるかどうかを確認（即ち、［ｒ３］がａｒ．ｃｃｖに等しいかどうか）し、（３）現在のロックオーナーがＮＵＬＬ値である場合（即ち［ｒ３］がａｒ．ｃｃｖに等しい場合）、ロックオーナーを現在のスレッドを示す値に設定（即ち、［ｒ３］＝ｒ２）し、（４）現在のロックオーナーがＮＵＬＬ値でない場合（即ち［ｒ３］がａｒ．ｃｃｖと等しくない場合）、ロックオーナーを変更しない（即ち、［ｒ３］を変更しない）ために使用されうるアトミック命令である。

図５Ａに戻ると、ロックオーナーがＮＵＬＬではない（ブロック５１２）またはロックオーナーが現在のスレッドとして定義されている（ブロック５１６）と決定された後、処理５００は、オブジェクトの以前のロックオーナーがＮＵＬＬ値であるかどうかを決定する（現在のスレッドがブロック５１６においてロックを取得した場合に相当）（ブロック５２０）。以前のロックオーナーがＮＵＬＬ値である場合（ブロック５２０）、制御は、ブロック５２４に進む。しかしながら、処理５００が以前のロックオーナーはＮＵＬＬ値ではないと決定した場合（ブロック５２０）、処理は、以前のロックオーナーが現在のスレッドであるかどうかを決定する（現在のスレッドが既にロックを取得していた場合に相当）（ブロック５２６）。以前のロックオーナーが現在のスレッドである場合（ブロック５２６）、制御は、ブロック５２４に進む。しかしながら、処理５００が以前のロックオーナーは現在のスレッドではないと決定し（ブロック５２６）、従って、他のスレッドが既にロックを所有している場合、処理５００は、現在のロックオーナーがロックを解放した後に現在のスレッドがロックを取得することを可能にするため、既知のロック競合手続を呼び出す（ブロック５２８）。既知のロック競合手続は、オブジェクトロックに対して、ブロック５２８の処理の完了後にロックの表現／フォーマットが変更されないように動作すべきである。更に、処理５００は、現在のロックオーナーがオブジェクトのロックを解放／アンロックするまで、現在のスレッドにループを実行させうる、または、実行をｈａｌｔさせうる。オブジェクトのロックが使用可能になったあと、処理５００は、現在のスレッドに対してロックを取得しうる。更に、制御は、ブロック５２８のロック競合手続の完了後には以前のロックオーナーが存在しないために処理５００が以前のロックオーナーをＮＵＬＬ値にリセットする、ブロック５３２に進む。そして、制御は、ブロック５２４に進む。

ブロック５２４において、現在のスレッドは、ロックされたオブジェクトに対応するコードのクリティカルセクションを実行する。コードのクリティカルセクションの実行が完了したあと、処理５００は、ロックのロックオーナーを以前のロックオーナーにリセットする（ブロック５４０）。ロックオーナーを以前のロックオーナーに等しくなるようにリセットすることによって、処理５００は、以前のオーナーがＮＵＬＬ値の場合はロックをアンロックする、または、以前のロックオーナーが現在のスレッドである場合は現在のスレッドに対してロック維持する。そして、例示の処理５００は、終了する。

図４のブロック４０８において実行される処理を実行するため、および／または、図２の楽観的均衡ロック同期部２２０を実装するために使用されうる例示の楽観的均衡ロック同期処理５５０が、図５Ｂに示される。図５Ａおよび図５Ｂのフロー図間において著しいオーバーラップがあるため、本願明細書においては、実質的に同一の機能を有するブロックは、再度説明されない。むしろ、実質的に同一の機能を有するブロックについては、図５Ａに示される対応するブロックおよび上記の関連する説明を参照すべきである。本願内容の理解を支援するために、実質的に類似の機能を有するブロックは、図５Ａおよび図５Ｂにおいて同一の参照番号でラベルされる。

図５Ｂの例示の楽観的均衡ロック同期処理５５０は、妥当性フラグをＴＲＵＥに初期化することによって開始する（ブロック５５８）。下記において明らかになるように、この妥当性フラグは、待機中の楽観的均衡ロック解放の妥当性状態を示すために使用される。そして、制御は、処理５５０が現在のスレッドに対してロックを取得する、ブロック５０４およびその後続のブロックに進む。ブロック５０４、５１２、５１６、５２０、５２６、５２８、および５３２の詳細な説明は、図５Ａの処理例５００の詳細な説明の一部として、上記に提供された。処理５５０が現在のスレッドに対してロックを取得した後、制御は、ブロック５２４に進む。

ブロック５２４において、現在のスレッドは、オブジェクトがロックされることを必要とするコードのクリティカルセクションを実行する。コードのこのクリティカルセクションの実行完了後、制御は、処理５００がまず待機中の楽観的解放に対応する妥当性フラグが解放は正常であることを示すかどうかを決定することによって、オブジェクトのロックに対する最近の楽観的均衡ロック取得の解放を試みる、ブロック５６２に進む。妥当性フラグがＴＲＵＥであり（ブロック５６２）、従って、待機中の楽観的均衡解放がアンロックまたはロック維持に相当（再帰ロックの場合）する場合、処理５５０は、ロックのロックオーナーを以前のロックオーナーにリセットする（ブロック５４０）。しかしながら、妥当性フラグがＦＡＬＳＥであり（ブロック５６２）、従って、不正な楽観的均衡解放に対応する場合、処理５５０は、既知の例外処理技術を用いて例外を発生させうる（ブロック５６６）。そして、ブロック５４０またはブロック５６６における処理の完了後、例示の処理５５０は、終了する。

再帰楽観的均衡ロック同期（および、以下に説明される非均衡ロック取得および解放手続）をサポートするために、ロックマネージャ２００および／またはロックマネージャ処理４００は、楽観的均衡ロック同期を呼び出すメソッド（例：ＪＡＶＡメソッド）の各インスタンスに対する待機中の楽観的均衡同期操作をトラックするために、１つ以上の同期マップを使用する。例示の同期マップは、メソッド内の各楽観的均衡同期操作に対するロックアドレス、以前のロックオーナー値、および、妥当性フラッグを含んでもよい。更に、同期マップは、オブジェクトがロックされることを必要とするコードのクリティカルセクションに対応するアドレス範囲を含んでもよい。同期マップの各エントリは、楽観的均衡ロック同期を引き起こすメソッドの特定のインスタンスに対応する、コールフレーム内のコールスタックに格納されうる（それによって、ネストされた呼び出しによって生じる、同一メソッドに対する再帰ロック取得をサポートする）。以下に詳細に説明されるように、非均衡ロック取得および解放操作は、コールスタック上で待機中の楽観的均衡同期操作（および、特に、楽観的均衡解放操作）の数とタイプを決定するため、および、必要に応じてそれらの操作を変更するために、同期マップを確認する。

図４のブロック４１２における処理を実行するため、および／または、図２の非均衡ロック取得部２２４を実装するために使用されうる例示の非均衡ロック取得処理６００は、図６Ａから図６Ｂに示される。例示の非均衡ロック取得処理６００は、待機中の正常な楽観的均衡解放の数を数えるため、および、待機中の楽観的均衡解放が存在するかどうかを決定するために、例えば、図５Ｂの例示の楽観的均衡ロック同期処理５５０、または、図２の楽観的均衡ロック同期部２２０によって維持される同期マップを確認することによって、開始する（図６Aのブロック６０４）。ブロック６０４において実行される処理を実装するための例示の処理は、図８に示され、以下において詳細に説明される。

ブロック６０４における処理完了後、処理６００は、ロックの以前のロックオーナーに対応する変数／レジスタを現在のロックオーナーに等しくなるように設定する（ブロック６０８）。そして、処理６００は、スレッドがロックされるべきオブジェクトのロックを既に所有しているかどうかを決定する（即ち、オブジェクトに対してロックオーナーが存在するかどうか、または、ロックオーナーがＮＵＬＬ値に設定されているかどうか）（ブロック６１２）。スレッドオーナーが存在せず（ブロック６１２）、従って、オブジェクトのロックがアンロックであり、ロックオーナーがＮＵＬＬ値に設定されている場合、処理６００は、ロックオーナーをスレッドを示す値（ユニークなスレッド識別子の値）に設定することによって、スレッドに対してオブジェクトのロックを取得する（ブロック６１６）。しかしながら、処理６００がロックオーナーは既に存在すると決定した場合（ブロック６１２）、処理６００は、ロックオーナーを変更しない。

上記に説明されたように、第１のスレッドがロックオーナーになるための処理にすでに入っている間に第２のスレッドがロックの取得を図ることを防ぐために、ブロック６０８、６１２、および６１６は、概して、単一のアトミック操作（Ｉｎｔｅｌ Ｉｔａｎｉｕｍプロセッサファミリに属するプロセッサ上のｃｍｐｘｃｈｇ命令など）を用いて実装される。アトミック操作は、アトミック操作の実行中、スレッド（および／またはマルチプロセッサシステムのプロセッサ）に、共有メモリへの排他アクセスを提供する。従って、他のスレッドは、その実行中において、アトミック操作によってアクセスされているメモリロケーションを変更できない。

図６Ａに戻ると、ロックオーナーがＮＵＬＬではない（ブロック６１２）またはロックオーナーが現在のスレッドであると定義されている（ブロック６１６）と決定された後、処理６００は、オブジェクトの以前のロックオーナーがＮＵＬＬ値かどうかを決定する（現在のスレッドがブロック６１６においてロックを取得した場合に相当）（ブロック６２０）。以前のロックオーナーがＮＵＬＬ値である場合（ブロック６２０）、制御は、図６Ｂのブロック６２４に進む。しかしながら、処理６００が以前のロックオーナーはＮＵＬＬ値ではないと決定した場合（ブロック６２０）、処理は、以前のロックオーナーが現在のスレッドであるかどうかを決定する（現在のスレッドが既にロックを取得していた場合に相当）（ブロック６２５）。以前のロックオーナーが現在のスレッドである場合（ブロック６２５）、制御は、図６Ｂのブロック６２４に進む。しかしながら、処理６００が以前のロックオーナーは現在のスレッドではないと決定し（ブロック６２５）、従って他のスレッドが既にロックを所有している場合、処理６００は、現在のロックオーナーがロックを解放した後に現在のスレッドがロックを取得することを可能にするために、既知のロック競合手続を呼び出す（ブロック６２６）。既知のロック競合手続は、オブジェクトロックに対して、ブロック６２６の処理完了後にロックの表現／フォーマットが変更されないように動作すべきである。更に、処理６００は、現在のロックオーナーがオブジェクトのロックを解放／アンロックするまで、現在のスレッドにループを実行させうる、または、実行をｈａｌｔさせうる。オブジェクトのロックが使用可能になった後、処理６００は、現在のスレッドに対してロックを取得しうる。更に、制御は、ブロック６２６のロック競合処理完了後に以前のロックオーナーが存在しないために処理６００が以前のロックオーナーをＮＵＬＬ値にリセットする、ブロック６２７に進む。そして、制御は、図６Ｂのブロック６２４に進む。

図６Ｂのブロック６２４において、処理６００は、ロック回帰カウンタが０に等しいように設定されているかどうかを決定する。ロック再帰カウンタ（または類似のインジケータ）は、非均衡ロック解放によってオフセットされないアクティブな非均衡ロック取得の数を示すために使用されうる。ロック再帰カウンタが０に等しく（ブロック６２４）、従って、アクティブな非均衡ロック取得が存在しない場合、処理６００は、ブロック６０４において実行された処理によって、０でない数の待機中の正常な楽観的均衡解放が返されたかどうかを決定する（ブロック６２８）。待機中の正常な楽観的均衡解放の数が０ではなく（ブロック６２８）、従って、待機中の正常な楽観的均衡解放が少なくとも１つ存在する場合、処理６００は、最も外側（即ち、最も古い）の待機中の正常な楽観的均衡解放の状態をアンロック操作からロック維持操作に変更する（ブロック６３２）。この変更は、追加の非均衡ロック取得が最後の待機中の楽観的均衡ロック解放が実行された場合にアクティブなロック取得の残存を生じるため、必要とされる。従って、処理６００は、残存するアクティブロック取得に対応するために、ロックを維持する必要がある。ブロック６３２において実行される処理を実装するための例示の処理は、図９に示され、かつ、以下においてより詳細に説明される。

ロック再帰カウンタが０ではなく（ブロック６２４）、従って他の非均衡ロック取得がアクティブである場合、同期マップ内に正常な楽観的均衡解放が存在しない場合（ブロック６２８）、または、ブロック６３２における処理が完了した場合、制御は、ブロック６３６に進む。ブロック６３６において、処理６００は、ブロック６０４において実行された処理によって待機中の不正な楽観的均衡解放の存在が示されたかどうかを決定する。待機中の不正な楽観的均衡解放が存在する場合（ブロック６３６）、処理６００は、最も内側（即ち、最も新しい）待機中の不正な楽観的均衡解放の状態を、例外発生操作からロックのアンロック操作に変更する（ブロック６４０）。不正な楽観的均衡解放は、常に、全ての待機中の正常な楽観的均衡解放が実行された後に発生する。従って、この修正は、追加の非均衡ロック取得が第１の不正な楽観的均衡ロック解放とオフセットするため、必要とされる。従って、処理６００は、追加のアクティブなロック取得に対応するために、この第１の不正な楽観的均衡解放に対してロックをアンロックする必要がある。ブロック６４０において実行された処理を実装するための例示の手続は、図９に示され、かつ、以下において詳細に説明される。

しかしながら、待機中の不正な楽観的均衡解放が存在しない場合（ブロック６３６）、処理６００は、非均衡ロック取得が実行され（よってアクティブであり）かつ以前の非均衡ロック解放によってオフセットされないことを示すために、ロック再帰カウンタをインクリメントする（ブロック６４４）。（以前の非均衡解放が実行された場合は、待機中の不正な楽観的均衡解放が少なくとも１つ存在するため、制御は、ブロック６４０に進む）。ブロック６４０または６４４における処理の完了後に、図６の例示の処理は、終了する。

図４のブロック４１６における処理を実行するため、および／または、図２の非均衡ロック解放部２２８を実装するために使用されうる例示の非均衡ロック解放処理７００は、図７に示される。例示の非均衡ロック解放処理７００は、現在のスレッドが解放されるべきオブジェクトのロックオーナーであるかどうかを決定することによって開始される（ブロック７０４）。現在のスレッドがロックオーナーではない場合（ブロック７０４）、処理７００は、スレッドが所有していないロックの解放を不正に図ったことを示す例外を発生させるために、既知の例外処理技術を使用しうる（ブロック７０８）。そして、例示の処理７００は、終了する。

しかしながら、現在のスレッドがロックオーナーである場合（ブロック７０４）、少なくとも１つの楽観的均衡ロック同期または非均衡ロック取得が、オブジェクトのロックに対して実行された。従って、処理７００は、待機中の正常な楽観的均衡解放の数を数えるために、例えば、図５Ａの例示の楽観的均衡ロック同期処理５５０または図２の楽観的均衡ロック同期部２２０によって維持される、同期マップを確認する（ブロック７１２）。ブロック７１２において実行される処理を実装するための例示の手続は、図８に示され、以下において詳細に説明される。そして、処理７００は、ブロック７１２において返された待機中の正常な楽観的均衡解放の数（アクティブな楽観的均衡ロック取得の数に相当）と、ロック再帰カウンタ（例：非均衡ロック解放によってオフセットされないアクティブな非均衡ロック取得の数を示すために、図６Ａから図６Ｂの例示の非均衡ロック取得処理によって更新される）を合計し、更に、１を引くことによって、実際の再帰カウンタ（ロックに対してまだアクティブな楽観的均衡取得と非均衡取得の総数より１小さい値に相当）を決定する（ブロック７１６）。

次に、処理７００は、実際の再帰カウンタが０に等しく、従って、アクティブな楽観的均衡取得が１つだけ存在する、または、アクティブな非均衡取得が１つ存在するかどうかを決定する（ブロック７２０）。このように、実際の再帰カウンタが０に等しい場合（ブロック７２０）、処理７００は、１つのアクティブロック取得の後に非均衡解放操作を実行した結果、オブジェクトのロックをアンロックする（ブロック７２４）。しかしながら、実際の再帰カウンタが０より大きい場合（ブロック７２０）、処理７００は、ロック再帰カウンタが１に等しいかどうかを決定する（ブロック７２８）。ロック再帰カウンタが１に等しい場合、１つのアクティブな非均衡ロック取得と、少なくとも１つのアクティブな楽観的均衡ロック取得（および、対応する正常な楽観的均衡解放）が存在する。従って、ロック再帰カウンタが１に等しい場合、処理７００は、最も外側（即ち、最も古い）待機中の正常な楽観的均衡解放の状態をロック維持操作からアンロック操作に変更する（ブロック７３２）。この変更は、非均衡ロック解放が、以前に最も外側の待機中の正常な楽観的均衡解放をロック維持状態に一致するように設定させた非均衡ロック取得と相殺するため、必要とされる。従って、処理７００は、最も外側の待機中の正常な楽観的均衡解放を元のアンロック状態に戻させる必要がある。ブロック７３２において実行される処理を実装するための例示の処理は、図９に示され、以下において詳細に説明される。

しかしながら、ロック再帰カウンタが１と等しくない場合（ブロック７２８）、処理７００は、ロック再帰カウンタが０に等しいかどうかを決定する（ブロック７３６）。ロック再帰カウンタが０に等しい場合（ブロック７３６）、少なくとも２つの待機中の正常な楽観的均衡解放が存在する（ブロック７２０において実際の再帰カウンタが０より大きいと決定されたため）。従って、再帰カウンタが０に等しい場合、処理７００は、２番目に外側の（即ち、２番目に最も古い）待機中の正常な楽観的均衡解放の状態を、ロック維持操作からアンロック操作に変更する（ブロック７４０）。この変更は、非均衡ロック解放が全てのアクティブなロック取得が相殺された後にオブジェクトのロックをアンロックする余分なロック解放を生じるため、必要とされる。従って、処理７００は、全てのアクティブな取得が解放によって相殺された場合、2番目に最も外側の待機中の正常な楽観的均衡解放をアンロック状態に変更する必要がある。ブロック７４０において実行される処理を実装するための例示の手続は、図９に示され、以下において詳細に説明される。

ブロック７２４、７３２、または７４０における処理の完了後、制御は、処理７００がロック再帰カウンタは０に等しいかどうかを決定する、ブロック７４４に進む。ロック再帰カウンタが０に等しい場合（ブロック７４４）、少なくとも１つの待機中の正常な楽観的均衡解放が存在する。従って、ロック再帰カウンタが０に等しい場合、処理７００は、最も外側の（即ち、最も古い）待機中の正常な楽観的均衡解放の状態をアンロック操作から例外発生操作に変更する。この変更は、追加の非均衡ロック解放が全てのアクティブな取得が相殺された後に１つの追加の解放を生じるため、必要とされる。従って、処理７００は、全てのアクティブな取得が解放によって相殺された場合にオブジェクトのロックオーナーではないスレッドによって他の解放が実行されるため、最も外側の待機中の正常な楽観的均衡解放を例外発生状態に変更する必要がある。ブロック７４８において実行される処理を実装するための例示の手続は、図９に示され、以下において詳細に説明される。

しかしながら、ロック再帰カウンタが０より大きい場合（ブロック７４４）、処理７００は、アクティブな非均衡ロック取得のうちの１つが非均衡ロック解放によって相殺されたことを示すために、ロック再帰カウンタをデクリメントする（ブロック７５２）。ブロック７４８または７５２における処理の完了後、例示の処理７００は、終了する。

同期マップ（図５Ａの楽観的均衡ロック同期処理５５０または図２の楽観的均衡ロック同期部２２０によって維持される同期マップ）内の待機中の正常な楽観的均衡解放の数をカウントし、待機中の不正な楽観的均衡解放が存在するかどうかを決定する例示の処理８００は、図８に示される。処理例８００は、例えば、図６および図７の、例示の非均衡ロック取得処理例６００および／または非均衡ロック解放処理７００によって、それぞれ使用される。特に、例示の処理８００は、図６のブロック６０４および／または図７のブロック７１２によって実行される処理を実装するために、例示の処理６００および／または例示の処理７００によって呼び出されうる。例示の処理８００は、また、図２の楽観的均衡解放トラック部２３２を実装するために使用されうる。

図８を参照すると、例示の処理８００は、例えば、オブジェクトに関連するｌｏｃｋｗｏｒｄのアドレスを取得することによって、処理されているオブジェクトに対応するロックを取得することによって開始する（ブロック８０４）。そして、処理８００は、待機中の正常な楽観的均衡解放の数に対応するカウンタを０に初期化し、かつ、待機中の正常な楽観的均衡解放の存在に対応するフラグをＦＡＬＳＥに初期化する（ブロック８０８）。この初期化の完了後、処理８００は、ブロック８０４において選択されたオブジェクトロックに対応する楽観的均衡解放の存在を決定するために、コールスタック内の各コールフレームの繰り返しを開始する。

処理８００は、コールスタック上の次のコールフレームを取得することによって、コールスタックのコールフレームの繰り返しを開始する（ブロック８１２）。そして、処理８００は、処理されているコールフレーム内に格納された次の待機中の楽観的均衡解放を取得する（ブロック８１６）。次に、処理８００は、待機中の楽観的均衡解放が処理されているオブジェクトロックに対応するかどうかを決定する（ブロック８２０）。待機中の楽観的均衡解放が処理されているオブジェクトロックに対応しない場合（ブロック８２０）、処理８００は、処理されている待機中の楽観的均衡解放に対応する妥当性フラグがＴＲＵＥに設定されているかどうかを決定する（ブロック８２４）。妥当性フラグがＴＲＵＥである場合（ブロック８２４）、処理８００は、待機中の正常な楽観的均衡解放の数に対応するカウンタを、インクリメントする（ブロック８２８）。

ブロック８２８における処理完了後、または、楽観的均衡解放が処理されているオブジェクトロックに対応しない場合（ブロック８２０）、処理８００は、処理されている楽観的均衡解放が、処理されているコールフレーム内の最後の解放かどうかを決定する（ブロック８３２）。楽観的均衡解放が最後の解放でない場合（ブロック８３２）、制御は、処理８００がコールフレーム内の次の楽観的均衡解放を処理するために取得する、ブロック８１６に戻る。しかしながら、楽観的均衡解放が最後の解放である場合（ブロック８３２）、処理８００は、処理されているコールフレームがコールスタック内の最後のコールフレームであるかどうか（従って、同期マップの終わりに到達したかどうか）を決定する（ブロック８３６）。コールフレームが最後のコールフレームではない場合（ブロック８３６）、制御は、処理８００が処理するために次のコールフレームを取得する、ブロック８１２に戻る。

ブロック８２４において、処理されている楽観的均衡解放の妥当性フラグがＦＡＬＳＥであると決定された場合、処理８００は、コールスタックの各コールフレームを繰り返す制御フローをブレークし、ブロック８４０に進む。ブロック８４０において、処理８００は、待機中の不正な楽観的均衡解放の存在に対応するフラグをＦＡＬＳＥに設定する。そして、ブロック８４０における処理の完了後、または、処理されているコールフレームがコールスタックの最後のコールフレームである場合（ブロック８３６）、処理８００は、待機中の正常な楽観的均衡解放の数、および、待機中の不正な楽観的均衡解放の存在または不在を示すフラグを返す。そして、例示の処理８００は、終了する。

同期マップ（例：図５Ａの楽観的均衡ロック同期処理５５０または図２の楽観的均衡ロック同期部によって維持される同期マップ）内の待機中の楽観的均衡解放の状態を変更する例示の処理９００は、図９に示される。処理例９００は、例えば、図６および図７の、例示の非均衡ロック取得処理６００および／または非均衡ロック解放処理７００によってそれぞれ使用されうる。特に、例示の処理９００は、図６のブロック６３２および６３４、および図７のブロック７３２、７４０、および７４８のいずれかまたは全てによって実行される処理を実装するために、例示の処理６００および／または７００によって呼び出されうる。例示の処理９００は、また、図２の楽観的均衡同期状態変更部２３６を実装するために使用されうる。

図９を参照すると、例示の処理９００は、例えば、オブジェクトに関連するｌｏｃｋｗｏｒｄのアドレスを取得することによって、処理されているオブジェクトに対応するロックを取得することによって開始する（ブロック９０４）。処理９００は、また、処理すべき同期マップ内の待機中の楽観的均衡解放へのインデックスと、インデックスされた解放に対して実行される動作とを取得する（ブロック９０４）。オブジェクトロック、待機中の楽観的均衡解放インデックス、および目的とする動作は、例えば、例示の処理９００を呼び出した呼び出し処理によって、提供されうる。そして、制御は、処理９００がオブジェクトロックに対応するインデックスされた楽観的均衡解放に対して目的とする動作の実行を開始する、ブロック９０８に進む。

ブロック９０８において、処理９００は、目的とする動作がインデックスされた均衡解放のロック維持状態に対応するかどうかを決定する。目的とする動作がロック維持状態に対応する場合（ブロック９０８）、処理９００は、インデックスされた楽観的均衡解放の以前のロックオーナーを、現在のスレッドと等しくなるように設定する（ブロック９１２）。従って、インデックスされた楽観的均衡解放が実行されると、ロックオーナーは、現在のスレッドである以前のロックオーナーに設定され、それによってロックを維持する。処理９００は、また、インデックスされた楽観的均衡解放の妥当性フラグをＴＲＵＥに設定（ブロック９１６）する。そして、例示の処理９００は、終了する。

ブロック９０８において目的とする動作がロック維持状態に対応しない場合、処理９００は、目的とする動作がインデックスされた楽観的均衡解放のアンロック状態に対応するかどうかを決定する（ブロック９２０）。目的とする動作がアンロック状態に相当する場合（ブロック９２０）、処理９００は、インデックスされた楽観的均衡解放の以前のロックオーナーをＮＵＬＬ値と等しくなるように設定する（スレッドオーナーが無いことを示す）（ブロック９２４）。従って、インデックスされた均衡解放が実行されると、ロックオーナーはＮＵＬＬ値である以前のロックオーナーに設定され、それによってロックをアンロックする。処理９００は、また、インデックスされた楽観的均衡解放の妥当性フラグをＴＲＵＥに設定する（ブロック９２８）。そして、例示の処理９００は、終了する。

ブロック９２０において目的とする動作がアンロック状態に相当しない（かつ、ブロック９０８における処理に基づき、ロック維持状態に相当しない）場合、目的とする動作が例外発生状態に相当するので、処理９００は、インデックスされた楽観的均衡解放の妥当性フラグをＦＡＬＳＥに設定する（ブロック９３２）。そして、例示の処理９００は、終了する。

方法に関する理解を支援するために、図２の例示のロックマネージャの動作例、および／または、図５Ａ、図５Ｂ、図６Ａ、図６Ｂ、図７、図８、および図９それぞれの動作例５００、５５０、６００、７００、８００、および９００が、図１０Ａおよび図１０Ｂに示される。図１０Ａおよび図１０Ｂの例示の動作は、単一スレッドにより単一オブジェクトのロックに対して実行されるロック取得および解放シーケンスに相当する。ロックシーケンスは、方法を実行するためにオブジェクトがロックされることを必要とする種々の方法Ａから方法Ｆが呼び出されることによって生じる。ロックシーケンスの各段階において、図１０Ａおよび図１０Ｂは、オブジェクトロックの状態１０１０と、対応するロック操作の完了時における同期マップ１０２０の内容を示す。オブジェクトロック１０１０は、ロックオーナーとロック再帰カウンタを含む。同期マップ１０２０の各エントリは、以前のロックオーナー、妥当性フラッグ、および他の情報を含む。

図１０Ａの段階１０３０において、例示の処理は、アンロックされているオブジェクトに対して開始し（即ち、ＮＵＬＬ値に等しいロックオーナー、および、０に等しい再帰カウンタに相当）、方法Ａは、ロックに対して楽観的均衡ロック同期を実行させる。例示の処理５５０によると、オブジェクトロックは、現在のスレッドにロックオーナーを割り当てるために更新され、再帰カウンタは０のままである。同期マップは、第１の楽観的均衡解放に対応する１つのエントリを含み、ＮＵＬＬ値に等しい以前のオーナーと、ＴＲＵＥに等しい妥当性フラッグとを有する（即ち、アンロック状態に相当）。

次に、段階１０３５において、方法Ｂは、オブジェクトのロックに対して他の楽観的均衡ロック同期を実行させる（再帰ロックシナリオに相当）。例示の処理５５０によると、オブジェクトロックの状態は変更されず、この第２の楽観的均衡解放に対応する同期マップに他のエントリが追加される。この新規エントリに対するロックの以前のオーナーは、スレッドを示す値と等しくなるように設定され（ロックがすでにスレッドによって所有されているため）、かつ、妥当性フラグは、ＴＲＵＥに設定される（即ち、ロック維持状態に相当）。

次に、段階１０４０において、方法Ｃは、オブジェクトロックに対して非均衡ロック取得を実行させる。例示の処理６００によると、ロック再帰カウンタは、１の値にインクリメントされる。更に、最も外側の待機中の正常な楽観的均衡解放は、以前のロックオーナーを現在のスレッドを示す値に設置し、かつ、妥当性フラグをＴＲＵＥに設定することによって、アンロック状態からロック維持状態に変更される。

次に、段階１０４５において、方法Ｄは、オブジェクトのロックに対して他の楽観的均衡ロック同期を実行させる（再帰ロックシナリオに相当）。例示の処理５５０によると、オブジェクトロックの状態は変更されず、かつ、この第３の楽観的均衡解放に対応する同期マップに他のエントリが追加される。この新規エントリのロックの以前のオーナーは、スレッドを示す値と等しくなるように設定され（ロックが既にスレッドによって所有されているため）、かつ、妥当性フラグは、ＴＲＵＥに設定される（即ち、ロック維持状態に相当）。

次に、段階１０５０において、方法Ｅは、オブジェクトロックに対して非均衡ロック解放を実行させる。例示の処理７００によると、実際の再帰カウンタは、３の値を持つと決定される（３つの待機中の正常な楽観的均衡解放、および、１に等しい再帰カウンタに相当）。従って、最も外側の待機中の正常な楽観的均衡解放は、以前のロックオーナーをＮＵＬＬ値に設定し、かつ、妥当性フラグをＴＲＵＥに設定することによって、ロック維持状態からアンロック状態に変更される。更に、ロック再帰カウンタは、０の値にデクリメントされる。

次に、図１０Ｂの段階１０５５において、方法Ｆは、オブジェクトロックに対して他の非均衡ロック解放を実行させる。例示の処理７００によると、実際の再帰カウンタは、２の値を持つと決定される（３つの待機中の正常な楽観的均衡解放、および、０に等しい再帰カウンタに相当）。従って、次に最も外側の待機中の正常な楽観的均衡解放は、以前のロックオーナーをＮＵＬＬ値に設定し、かつ、妥当性フラグをＴＲＵＥに設定することによって、ロック維持状態からアンロック状態に変更される。更に、最も外側の待機中の正常な楽観的均衡解放は、妥当性フラグをＦＡＬＳＥに設定することによって、アンロック状態から例外発生状態に変更される。

次にブロック１０６０において、方法Ｄのクリティカルセクションの実行完了は、最も内側の３つの待機中の楽観的均衡解放を処理させる。楽観的均衡解放処理は、図１０Ｂに示されるように、現在のスレッドによって所有されているロックから開始する。そして、例示の処理５５０によると、ロック維持状態を有する最も内側の待機中の楽観的均衡解放は、処理される。

次に、ブロック１０６５において、方法Ｂのクリティカルセクションの実行完了は、最も内側の２つの待機中の楽観的均衡解放を処理させる。段階１０６０において以前の均衡解放が処理された結果、オブジェクトロックは、まだ現在のスレッドによって所有される。そして、例示の処理５５０によると、アンロック状態を有する最も内側の待機中の均衡解放が処理される。

最後に、ブロック１０７０において、方法Ａのクリティカルセクションの実行完了は、残存する待機中の楽観的均衡解放を処理させる。段階１０６５における以前の均衡解放処理の結果、オブジェクトロックは、所有されない（例：ＮＵＬＬ値に設定される）。そして、例示の処理５５０によると、例外発生状態を有する残存する待機均衡解放が処理され、それによって、例外が発生する。

図１１は、開示された装置および方法を実装可能な例示のコンピュータまたはプロセッサシステム１１００のブロック図である。コンピュータ１１００は、例えば、サーバ、パーソナルコンピュータ、パーソナルデジタルアシスタント（ＰＤＡ）、インターネットアプラインアンス、または、他のいかなるコンピューティングデバイスであってもよい。

簡単な例示のシステム１１００は、プロセッサ１１１２を含む。例えば、プロセッサ１１１２は、Ｐｅｎｔｉｕｍ（登録商標）ファミリ、Ｉｔａｎｉｕｍ（登録商標）ファミリ、またはＸＳｃａｌｅ（登録商標）ファミリを含む１つ以上のＩｎｔｅｌ（登録商標）マイクロプロセッサによって実装されうる。当然のことながら、他のファミリの他のプロセッサも、適用可能である。１つ以上のマイクロプロセッサを含むプロセッサ１１１２は、図１の例示の使用環境１００、図２の例示のロックマネージャ２００、および／または、図５Ａ、図５Ｂ、図６Ａ、図６Ｂ、図７、図８、および図９それぞれの例示の処理５００、５５０、６００、７００、８００、および９００を実装するために使用されうる。

プロセッサ１１１２は、揮発性メモリ１１１４および不揮発性メモリ１１１６を含むメインメモリとバス１１１８によって通信する。揮発性メモリ１１１４は、スタティックランダムアクセスメモリ（ＳＲＡＭ）、同期ダイナミックランダムアクセスメモリ（ＳＤＲＡＭ）、ダイナミックランダムアクセスメモリ（ＤＲＡＭ）、RAMBUSダイナミックランダムアクセスメモリ（RDRAM）、および／または他のタイプのランダムアクセスメモリデバイスによって実装されうる。不揮発性メモリ１１１６は、フラッシュメモリおよび／または他のメモリデバイスによって実装されうる。メインメモリ１１１４、１１１６へのアクセスは、概して、従来技術のメモリコントローラ（図示されない）によって制御される。

コンピュータ１１００は、また、従来のインタフェース回路１１２０を含む。インタフェース回路１１２０は、イーサネットインタフェース、ユニバーサルシリアルバス（ＵＳＢ）、および／または第３世代入力／出力（３ＧＩＯ）インタフェースのようないかなる既知のインタフェース標準によっても実装されうる。

１つまたは複数の入力デバイス１１２２は、インタフェース回路１１２０に接続される。入力デバイス１１２２は、ユーザに、プロセッサ１１１２へのデータおよびコマンドの入力を可能にする。入力デバイスは、例えば、キーボード、マウス、タッチスクリーン、トラックパッド、トラックボール、イソポイント、および／または音声認識システムによって実装されうる。

１つまたは複数の出力デバイス１１２４は、また、インタフェース回路１１２０に接続される。出力デバイス１１２４は、例えば、ディスプレイデバイス（例：液晶ディスプレイ、陰極線管（ＣＲＴ））、プリンタ、および／またはスピーカによって実装されうる。従って、インタフェース回路１１２０は、概して、グラフィックスドライバカードを含む。

インタフェース回路１１２０は、また、ネットワーク１１２６（例：イーサネット接続、デジタル加入者線（ＤＳＬ）、電話線、同軸ケーブル、携帯電話システムなど）を介して外部コンピュータとデータの交換を可能にするために、モデムまたはネットワークインタフェースカードのような通信デバイスを含む。

コンピュータ１１００は、また、ソフトウェアおよびデータを格納するための１つ以上の大容量ストレージデバイス１１２８を含む。そのような大容量ストレージデバイス１１２８の例は、フロッピーディスクドライブ、ハードディスクドライブ、コンパクトディスクドライブおよびデジタル多用途ディスク（DVD）ドライブを含む。大容量ストレージデバイス１１２８および／または揮発性メモリ１１１４は、例えば、図５Ａ、図５Ｂ、図６Ａ、図６Ｂ、および図７それぞれの処理５００、５５０、６００、および７００によって維持および変更される同期マップを格納するために使用されうる。

図１１のデバイスのようなシステムにおいて、開示された方法および／または装置を実装するための代替手段として、開示された方法および／または装置は、代わりに、プロセッサおよび／またはＡＳＩＣ（特定用途向け集積回路）のような構造に組み込まれてもよい。

上記のように、通常の技術を有する当業者は、上記に開示された方法および装置は、種々のプログラムの実行における性能の最適化を実現するために、静的コンパイラ、マネージドランタイム環境ｊｕｓｔ−ｉｎ−ｔｉｍｅ（ＪＩＴ）コンパイラ、および／またはマイクロプロセッサのハードウェア内に直接実装されうることを理解するであろう。

特定の方法、装置、および製品の例が説明されたが、本願の特許請求の範囲は、これらに限定されない。反対に、本願は、添付の請求項の範囲に明示的に含まれる、または、その均等物の範囲に含まれる、全ての方法、装置、および製品を含む。

Claims (30)

1. マネージドランタイム環境においてスレッドに対してオブジェクトをロックする方法であって、
   前記オブジェクトに対応するロックに対して実行するロック操作の組を決定することと、
   第１のロック操作が非均衡でない場合、前記ロックの均衡同期および前記ロックの楽観的均衡同期のうちの少なくとも１つを有する前記第１のロック操作を実行することと、
   前記第１のロック操作が前記ロックの楽観的均衡同期であり、かつ前記楽観的均衡同期に対応するロックが解放されていない場合、第１のロック操作の次の第２のロック操作が非均衡であるとき、更に、前記楽観的均衡同期の待機中の楽観的均衡解放の状態を変更することと
   を備える方法。
2. 前記均衡同期および前記楽観的均衡同期のうちの前記少なくとも１つは、
   前記ロックを取得するために、前記ロックの以前のロックオーナーを前記ロックのロックオーナーに等しくなるように設定し、前記ロックの前記ロックオーナーがｎｕｌｌスレッドである場合、前記ロックの前記ロックオーナーを、前記スレッドを示す値に設定する、アトミック操作を実行することと、
   ロックオーナーを以前のロックオーナーに等しくなるように設定することと
   を備える請求項１に記載の方法。
3. 前記楽観的均衡同期は、待機中の前記楽観的均衡解放が正常であることを示すために、妥当性フラグを設定することを備える請求項１または２に記載の方法。
4. 前記待機中の楽観的均衡解放の状態は、妥当性フラグおよび前記ロックの以前のロックオーナーのうちの少なくとも１つによって指示され、前記楽観的均衡同期の実行は、前記待機中の楽観的均衡解放の前記状態に基づき、前記ロックを解放することを備える請求項１から３のいずれかに記載の方法。
5. 前記ロックの解放は、前記待機中の楽観的均衡解放が正常であることを前記妥当性フラグが示す場合、前記ロックのロックオーナーを前記ロックの前記以前のロックオーナーにリセットすることを備える請求項４に記載の方法。
6. 前記以前のロックオーナーがｎｕｌｌスレッドである場合に前記ロックはアンロックされ、前記以前のロックオーナーが前記スレッドである場合に前記ロックは前記スレッドに対して維持される、請求項４または５に記載の方法。
7. 前記待機中の楽観的均衡解放は不正であることを前記妥当性フラグが示す場合、前記ロックの解放は、例外を発生させることを備える請求項４から６のいずれかに記載の方法。
8. 前記楽観的均衡同期は、前記ロックに対して実行されるべき待機中の楽観的均衡解放の組をトラックするために、同期マップを維持することを備え、前記待機中の楽観的均衡開放の組は、前記ロックの楽観的均衡同期の組に対応する請求項１から７のいずれかに記載の方法。
9. 前記待機中の楽観的均衡解放の組は、正常な楽観的均衡解放の組と、不正な楽観的均衡解放の組とを備える請求項８に記載の方法。
10. 正常な楽観的均衡解放の組の中の正常な楽観的均衡解放は、ＴＲＵＥに等しい妥当性フラグ、アンロック状態、およびロック維持状態のうちの少なくも１つに対応する請求項９に記載の方法。
11. 前記不正な楽観的均衡解放の組の中の不正な楽観的均衡解放は、ＦＡＬＳＥに等しい妥当性フラグおよび例外発生状態のうちの少なくとも１つに対応する請求項９または１０に記載の方法。
12. 前記ロックに対する前記第２のロック操作が非均衡である場合、前記ロックの非均衡取得および前記ロックの非均衡解放のうちの少なくとも１つを実行することを更に備え、前記ロックの前記非均衡取得および前記ロックの非均衡解放のうちの前記少なくとも１つを実行することは、前記同期マップ内の正常な楽観的均衡解放の数を決定すること、および、前記同期マップが少なくとも１つの不正な楽観的均衡解放を含むかどうか決定することのうちの少なくとも１つを備える請求項９から１１のいずれかに記載の方法。
13. 前記待機中の楽観的均衡解放は、前記待機中の楽観的均衡解放の前記状態を、アンロック状態、ロック維持状態、および、例外発生状態のうちの少なくとも１つに対応するように変更する請求項１から１２のいずれかに記載の方法。
14. 前記アンロック状態、前記ロック維持状態、および、前記例外発生状態のうちの少なくとも１つは、前記ロックの以前のロックオーナーと妥当性フラグとによって決定される請求項１３に記載の方法。
15. 前記ロックに対して実行するロック操作の前記組を決定することは、前記組の各ロック操作が、前記ロックの前記均衡同期、前記ロックの前記楽観的均衡同期、前記ロックの非均衡取得、および、前記ロックの非均衡解放のうちの１つであるかどうかを決定することを備える請求項１から１４のいずれかに記載の方法。
16. マシン読み取り可能な命令群を格納するプログラムであって、
    マシンによって実行されることによって、前記マシンに、
    オブジェクトに対応するロックに対して実行するロック操作の組を決定させ、
    第１のロック操作が非均衡でない場合、前記ロックの均衡同期および前記ロックの楽観的均衡同期のうちの少なくとも１つを有する前記第１のロック操作を実行させ、
    前記第１のロック操作が前記ロックの楽観的均衡同期であり、かつ前記楽観的均衡同期に対応するロックが解放されていない場合、前記第１のロック操作の次の第２のロック操作が非均衡であるとき、更に、前記楽観的均衡同期の待機中の楽観的均衡解放の状態を変更させる
    プログラム。
17. 前記マシン読み取り可能な命令群は、前記マシンに、前記ロックに対して実行されるべき待機中の楽観的均衡解放の組をトラックするために同期マップを維持させ、前記待機中の楽観的均衡解放の組は、楽観的均衡同期の組に対応する請求項１６に記載のプログラム。
18. 前記マシン読み取り可能な命令群は、前記ロックに対する前記第２のロック操作が非均衡である場合、前記マシンに、前記ロックの非均衡取得および前記ロックの非均衡解放の少なくとも１つを実行させ、前記ロックの前記非均衡取得および前記ロックの前記非均衡解放の少なくとも１つを実行するために、前記マシン読み取り可能な命令群は、前記マシンに、前記同期マップ内の正常な待機中の楽観的均衡解放の数を決定すること、および、前記同期マップが少なくとも１つの不正な待機中の楽観的均衡解放を有するかどうかを決定することのうちの少なくとも１つを実行させる請求項１７に記載のプログラム。
19. 前記マシン読み取り可能な命令群は、前記ロックに対する前記第２のロック操作が非均衡である場合に前記マシンに前記ロックの非均衡取得および前記ロックの非均衡解放のうちの少なくとも１つを実行させ、前記非均衡取得および前記非均衡解放のうちの前記少なくとも１つを実行させるために、前記マシン読み取り可能な命令群は、前記マシンに、前記待機中の楽観的均衡解放の前記状態およびロック再帰カウンタのうちの少なくとも１つを変更させる請求項１７または１８に記載のプログラム。
20. マネージドランタイム環境においてスレッドに対してオブジェクトをロックする装置であって、
    前記オブジェクトに対応するロックの均衡同期を実行する均衡ロック同期部、および、前記オブジェクトに対応する前記ロックの楽観的均衡同期を実行する楽観的均衡ロック同期部のうちの少なくとも１つと、
    前記装置が前記楽観的均衡ロック同期部を備える場合、更に、前記ロックの非均衡取得および前記ロックの非均衡解放のうちの少なくとも１つの発生に基づき、前記楽観的均衡ロック同期部の状態を変更する楽観的均衡同期状態変更部と
    を備える装置。
21. 前記均衡ロック同期部および前記楽観的均衡ロック同期部のうちの少なくとも１つは、
    前記ロックの以前のロックオーナーがｎｕｌｌスレッドであることに基づき、前記ロックの以前のロックオーナーを前記ロックのロックオーナーに等しくなるように設定し、かつ、前記ロックの前記ロックオーナーを前記スレッドを示す値に設定することによって、前記ロックを取得し、
    前記ロックオーナーを前記以前のロックオーナーに等しくなるようにリセットすること、および、例外を発生させることのうちの少なくとも１つによって、前記ロックを解放するように設定される
    請求項２０に記載の装置。
22. 前記楽観的均衡ロック同期部は、前記ロックの前記楽観的均衡同期の待機中の楽観的均衡解放の状態に基づき、前記ロックのアンロック、前記ロックの維持、および、例外発生のうちの少なくとも１つに設定される請求項２０または２１に記載の装置。
23. 前記楽観的均衡ロック同期部は、前記ロックに対して実行される待機中の楽観的均衡解放の組をトラックする同期マップを備え、前記楽観的均衡解放の組は、前記ロックの楽観的均衡同期の組に対応する請求項２０から２２のいずれかに記載の装置。
24. 前記待機中の楽観的均衡解放の組は、正常な楽観的均衡解放の組と、不正な楽観的均衡解放の組とを備える請求項２３に記載の装置。
25. 前記同期マップ内の正常な楽観的均衡解放の数を決定すること、および、前記同期マップが少なくとも１つの不正な楽観的均衡解放を含んでいるかどうかを決定することのうちの少なくとも１つを実行するために、楽観的均衡解放トラッカーを更に備える請求項２４に記載の装置。
26. 前記楽観的均衡同期は、前記ロックの楽観均衡取得と、前記ロックの待機中の楽観的均衡解放とを備え、前記楽観的均衡同期状態変更部は、前記待機中の楽観的均衡解放の状態を、アンロック状態、ロック維持状態、および例外発生状態のうちの１つに変更するように設定される請求項２０から２５のいずれかに記載の装置。
27. 前記ロックの非均衡取得を実行する非均衡ロック取得部、および、前記ロックの非均衡解放を実行する非均衡ロック解放部のうちの少なくとも１つを更に備える請求項２０から２６のいずれかに記載の装置。
28. マネージドランタイム環境においてスレッドに対してオブジェクトをロックするシステムであって、
    前記オブジェクトに対応するロックに対して実行するロック操作の組を決定し、
    第１のロック操作が非均衡でない場合、前記ロックの均衡同期および前記ロックの楽観的均衡同期のうちの少なくとも１つを有する前記第１のロック操作を実行し、
    前記第１のロック操作が前記ロックの楽観的均衡同期であり、かつ前記楽観的均衡同期に対応するロックが解放されていない場合、前記第１のロック操作の次の第２のロック操作が非均衡であるとき、更に、前記楽観的均衡同期の待機中の楽観的均衡解放の状態を変更する
    ように設定されるプロセッサと、
    前記ロックのロックオーナー、前記ロックの以前のロックオーナー、および妥当性フラグのうちの少なくとも１つを格納するメモリと
    を備えるシステム。
29. 前記メモリは、前記ロックに対して実行される待機中の楽観的均衡解放の組をトラックするために、同期マップを格納するように設定され、前記待機中の楽観的均衡解放の組は、前記ロックの楽観的均衡解放の組に対応する請求項２８に記載のシステム。
30. 前記楽観的均衡解放の前記状態を変更するために、前記プロセッサは、前記ロックの前記以前のロックオーナーおよび前記妥当性フラグのうちの少なくとも１つに基づき、前記状態をアンロック状態、ロック維持状態、および例外発生状態のうちの少なくとも１つに対応するように変更するように設定される請求項２８または２９に記載のシステム。

Images