(57)【要約】【課題】  マネージドランタイム環境におけるロック大型化方法およびロック大型化装置に基づくスレッド同期を提供する。【解決手段】  マネージドランタイム環境におけるロック大型化方法およびロック大型化装置に基づくスレッド同期を開示する。本明細書で開示する方法は、例えば、オブジェクトに対応するロックに行われるロック動作を特定することと、該ロック動作が不平衡でない場合は該ロックの楽観的平衡同期を行うことと、該ロック動作が不平衡である場合は該ロックのロック形状を変更することとを含む。【選択図】図５
2008501199.tif 000002
【特許請求の範囲】
【請求項１】
マネージドランタイム環境においてスレッドのためにオブジェクトをロックする方法であって、
前記オブジェクトに対応するロックに対して行われるロック動作を決定することと、
前記ロック動作が不平衡でない場合に、前記ロックの楽観的平衡同期を行うことと、
前記ロック動作が不平衡である場合に、前記ロックのロック形状を変更することと
を含む方法。
【請求項２】
前記ロック動作が不平衡である場合に、前記ロックの不平衡ロック取得および前記ロックの不平衡解除のうち少なくとも１つを行うこと
をさらに含む請求項１に記載の方法。
【請求項３】
前記ロック形状は第１ロック形状および第２ロック形状のうち少なくとも１つに対応し、前記ロック形状が前記第１ロック形状に対応する場合、前記ロック形状を変更することは前記ロックを変換して前記第２ロック形状に対応するようにすることを含む
請求項１に記載の方法。
【請求項４】
前記第１ロック形状は小型ロックに対応し、前記第２ロック形状は大型ロックに対応する
請求項３に記載の方法。
【請求項５】
前記楽観的平衡同期は、当該楽観的平衡同期を行っている間に、前記ロックの前記ロック形状を指し示すようにロック形状フラグを設定することを含む
請求項１に記載の方法。
【請求項６】
前記楽観的平衡同期は、前記ロックの楽観的平衡ロック取得および前記ロックの楽観的平衡ロック解除を含み、当該楽観的平衡ロック取得および当該楽観的平衡ロック解除のうち少なくとも１つは前記ロックの前記ロック形状に基づいて行われる
請求項１に記載の方法。
【請求項７】
前記楽観的平衡ロック取得は、前記ロック形状が第１ロック形状に対応する場合、前記ロックに対応付けられたロック所有者フィールドに等しくなるように旧ロック所有者を設定することを含む
請求項６に記載の方法。
【請求項８】
前記楽観的平衡ロック解除は、前記ロック形状が第１ロック形状に対応する場合、前記ロックに対応付けられたロック所有者フィールドを旧ロック所有者に設定することを含む
請求項６に記載の方法。
【請求項９】
前記ロック形状が前記第１ロック形状に対応する場合、前記旧ロック所有者が空スレッドであれば前記ロックは解除され、前記旧ロック所有者が前記スレッドであれば当該スレッドのために前記ロックを維持する
請求項８に記載の方法。
【請求項１０】
前記楽観的平衡同期は、前記オブジェクトの前記ロックに対して行われた一連の楽観的平衡同期に対応付けられた一連のアクティブな楽観的平衡取得の状態を格納する同期マップを維持することを含む
請求項１に記載の方法。
【請求項１１】
前記ロック動作が不平衡である場合に前記ロックの不平衡取得および前記ロックの不平衡解除のうち少なくとも１つを行うことをさらに含み、当該不平衡取得および当該不平衡解除のうち少なくとも１つを行うことは、前記同期マップに格納されたアクティブな楽観的平衡取得の状態の数を特定することを含む
請求項１０に記載の方法。
【請求項１２】
前記ロックの前記ロック形状を変更することは、前記同期マップに格納された前記アクティブな楽観的平衡取得の状態の数に対応するロック再帰カウンタの値を特定することを含む
請求項１１に記載の方法。
【請求項１３】
前記同期マップは前記一連のアクティブな楽観的平衡取得の状態に対応する一連の同期マップエントリを含み、当該一連の同期マップエントリに含まれる１つの同期マップエントリは、前記ロックの旧ロック所有者および前記ロックの前記ロック形状に対応するロック形状フラグのうち少なくとも１つを含む
請求項１０に記載の方法。
【請求項１４】
前記ロックの前記ロック形状を変更することは、前記同期マップエントリの前記ロック形状フラグを変更することを含む
請求項１３に記載の方法。
【請求項１５】
前記ロックに対して行われる前記ロック動作を決定することは、当該ロック動作が、前記ロックの前記楽観的平衡同期、前記ロックの平衡同期、前記ロックの不平衡取得および前記ロックの不平衡解除のうちのいずれであるか決定することを含む
請求項１に記載の方法。
【請求項１６】
複数の機械可読命令を格納する製品であって、当該機械可読命令を実行すると機械は、
前記オブジェクトに対応するロックに対して行われるロック動作を決定し、
前記ロック動作が不平衡でない場合に、前記ロックの楽観的平衡同期を行い、
前記ロック動作が不平衡である場合に、前記ロックのロック形状を変更する
製品。
【請求項１７】
前記ロック形状は第１ロック形状および第２ロック形状のうち少なくとも１つに対応し、前記ロック形状を変更するべく、前記機械可読命令は前記機械に、前記ロック形状が前記第１ロック形状に対応する場合、前記ロックを変換させて前記第２ロック形状に対応させる
請求項１６に記載の製品。
【請求項１８】
前記機械可読命令は前記機械に、前記オブジェクトの前記ロックに対して行われた一連の楽観的平衡同期に対応付けられた一連のアクティブな楽観的平衡取得の状態に対応する一連の同期マップエントリを格納する同期マップを維持させ、当該一連の同期マップエントリに含まれる１つの同期マップエントリは、前記ロックの旧ロック所有者および前記ロックの前記ロック形状に対応するロック形状フラグのうち少なくとも１つを含む
請求項１６に記載の製品。
【請求項１９】
前記機械可読命令は前記機械に、前記ロックに対する前記ロック動作が不平衡である場合に、前記ロックの不平衡取得および前記ロックの不平衡解除のうち少なくとも１つを行わせ、当該不平衡取得および当該不平衡解除のうち少なくとも１つを行うべく、前記機械可読命令は前記機械に、前記同期マップに格納された前記アクティブな楽観的平衡取得の状態の数を決定することおよび前記同期マップの少なくとも１つの同期マップエントリの少なくとも１つのロック形状フラグを変更することのうち少なくとも１つの動作を行わせる
請求項１８に記載の製品。
【請求項２０】
マネージドランタイム環境においてスレッドのためにオブジェクトをロックする装置であって、
前記オブジェクトに対応するロックの楽観的平衡同期を行う楽観的平衡ロック同期部と、
前記ロックの不平衡ロック取得および前記ロックの不平衡ロック解除のうち少なくとも１つの発生に基づき、前記楽観的平衡同期部の状態に対して、決定および変更のうち少なくとも１つの動作を行う平衡同期状態記録部／変更部と
を備える装置。
【請求項２１】
前記楽観的平衡ロック同期部は、
前記ロック形状が第１ロック形状である場合、前記ロックの旧ロック所有者を前記ロックのロック所有者フィールドに等しくなるように設定することによって前記ロックを取得し、
前記ロック形状が前記第１ロック形状である場合、前記ロック所有者フィールドを前記旧ロック所有者に等しくなるようにリセットすることによって前記ロックを解除する
ように構成されている請求項２０に記載の装置。
【請求項２２】
前記楽観的平衡ロック同期部は、前記ロックに対して行われる楽観的平衡同期処理の実行中に、前記ロックの前記ロック形状を指し示すべくロック形状フラグを設定するように構成されている
請求項２０に記載の装置。
【請求項２３】
前記楽観的平衡ロック同期部は、前記オブジェクトの前記ロックに対して行われる一連の楽観的平衡同期に対応する一連のアクティブな楽観的平衡取得の状態を格納するための同期マップを有する
請求項２０に記載の装置。
【請求項２４】
前記同期マップは前記一連のアクティブな楽観的平衡取得の状態に対応する一連の同期マップエントリを含み、当該一連の同期マップエントリにおける１つの同期マップエントリは、前記ロックの旧ロック所有者および前記ロックの前記ロック形状に対応するロック形状フラグのうち少なくとも１つを含む
請求項２３に記載の装置。
【請求項２５】
前記平衡同期状態記録部／変更部は、前記同期マップに格納された前記アクティブな楽観的平衡取得の状態の数を決定することによって前記楽観的平衡同期部の前記状態を決定すること、および前記同期マップの少なくとも１つの同期マップエントリ内の少なくとも１つのロック形状フラグを変更することによって前記楽観的平衡同期部の前記状態を変更することのうち少なくとも１つの動作を行うように構成されている
請求項２４に記載の装置。
【請求項２６】
前記楽観的平衡同期は前記ロックの楽観的平衡取得および前記ロックの楽観的平衡解除を含み、前記楽観的平衡同期部は、前記ロックの前記ロック形状に基づき、前記楽観的平衡取得および前記楽観的平衡解除のうち少なくとも１つの動作を行うように構成されている
請求項２０に記載の装置。
【請求項２７】
前記ロックの不平衡取得を行う不平衡ロック取得部および前記ロックの不平衡解除を行う不平衡ロック解除部のうち少なくとも１つをさらに備え、当該不平衡ロック取得部および当該不平衡ロック解除部のうち少なくとも１つは前記ロックの前記ロック形状を変更するように構成されている
請求項２０に記載の装置。
【請求項２８】
マネージドランタイム環境においてスレッドのためにオブジェクトをロックするシステムであって、
プロセッサと、
メモリとを備え、
前記プロセッサは、前記オブジェクトに対応するロックに対して行われるロック動作を決定し、
前記ロック動作が不平衡でない場合に、前記ロックの楽観的平衡同期を行い、
前記ロック動作が不平衡である場合に、前記ロックのロック形状を変更するように構成され、
前記メモリは、前記ロックのロック所有者フィールド、前記ロックの旧ロック所有者および前記ロックの前記ロック形状に対応するロック形状フラグのうち少なくとも１つを格納する
システム。
【請求項２９】
前記プロセッサは同期マップを前記メモリに格納するように構成されており、当該同期マップは、前記オブジェクトの前記ロックに行われる一連の楽観的平衡同期に対応付けられた一連のアクティブな楽観的平衡取得の状態に対応する一連の同期マップエントリを含み、当該一連の同期マップエントリに含まれる１つの同期マップエントリは、前記ロックの旧ロック所有者および前記ロックの前記ロック形状に対応するロック形状フラグのうち少なくとも１つを含む
請求項２８に記載のシステム。
【請求項３０】
前記プロセッサは、前記ロックに対する前記ロック動作が不平衡である場合前記ロックの不平衡取得および前記ロックの不平衡解除のうち少なくとも１つを行うように構成されており、当該不平衡取得および当該不平衡解除のうち少なくとも１つを行うべく、前記プロセッサは、前記同期マップに格納された前記アクティブな楽観的平衡取得の状態の数を決定すること、および前記同期マップの少なくとも１つの同期マップエントリ内の少なくとも１つのロック形状フラグを変更することのうち少なくとも１つの動作を行うように構成されている
請求項２９に記載のシステム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は概してコンピュータに関し、より具体的にはマネージドランタイム環境におけるロック大型化方法およびロック大型化装置に基づいたスレッド同期に関する。
【背景技術】
【０００２】
マルチスレッドアプリケーションをサポートするソフトウェア環境（例えば、ＪＡＶＡおよびＥＣＭＡ（欧州コンピュータ製造業者協会）のＣＬＩ（共通言語基盤））は通常、１以上のスレッドが１つのオブジェクトアクセスする場合に調整を行うための同期機構を含む。当業者には明らかであるが、スレッドとは、１以上のオブジェクトを処理するべく実行される、１つの制御フローに整理された一連のプロセッサ命令を指す。またオブジェクトは、クラスのインスタンスであって、クラスとはデータおよび該データに対して実施されるメソッドを含むものである。マルチスレッドを実行する場合には、複数のスレッドが同一のオブジェクトを同時に変形してしまい、このオブジェクトがエラー状態となってしまわないように注意しなければならない。特に、スレッドは、ほかのスレッドも同時にアクセス可能なオブジェクトに対して実行されるクリティカルな部分を有することがある。この問題を解決するべく、マルチスレッドシステムでは通常、特別なステートメントを準備している。このようなステートメントにより、スレッドのクリティカルな部分の処理が、該クリティカルな部分を実行している間に上述したような共有オブジェクトに１以上のほかのスレッドがアクセスすることによって破壊されないように、保護される。
【０００３】
例えばＪＡＶＡソースコードは、オブジェクトに複数の異なるスレッドが同時にアクセスしないようにオブジェクトを保護するｓｙｎｃｈｒｏｎｉｚｅｄステートメントを含むことがある。このようなｓｙｎｃｈｒｏｎｉｚｅｄステートメントを使用することによって、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントが特定するオブジェクトの排他的ロックを取得することができる。このためスレッドは、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントが特定するオブジェクトに対して排他的ロックを取得できるまで、クリティカルな部分のコードを実行できなくなるとしてもよい。さらに、このようなロックを取得すると、ロックされたオブジェクトに対してほかのスレッドはアクセスできなくなり、クリティカルな部分のコードの実行中に行われる処理が不意に破壊されることを防ぐことができる。このようなロック処理に基づき、複数のスレッドが共有オブジェクトにアクセスする場合、クリティカルな部分のコードを同時に矛盾する形で実行しないようにするとしてもよい。ｓｙｎｃｈｒｏｎｉｚｅｄステートメントアプリケーションが用いられるのは通常、プログラムがオブジェクトおよび／またはメソッドを共有する複数のスレッドを生成する場合である。オブジェクトおよび／またはメソッドにアクセスするスレッドが１つだけである場合は、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントを用いて保護する必要はない。
【０００４】
周知のように、ＪＡＶＡソースコードはＪＡＶＡ仮想マシン（ＪＶＭ）で実行される前にまずバイトコード（つまりＪＶＭ言語）にコンパイルされるので、ＪＡＶＡソースコードに含まれるｓｙｎｃｈｒｏｎｉｚｅｄステートメントは通常ＪＶＭ命令に変換される。例えば、ｓｙｎｃｈｒｏｎｉｚｅｄステートメントは、オブジェクトに対して排他的ロックを取得する／得るべく、ｍｏｎｉｔｏｒｅｎｔｅｒ  ＪＶＭ命令に変換されるとしてもよい。ｍｏｎｉｔｏｒｅｎｔｅｒ命令に対して、オブジェクトに対する排他的ロックを解除／解放するためのｍｏｎｉｔｏｒｅｘｉｔ  ＪＶＭ命令を設定する。このため、スレッドがオブジェクトに対してｍｏｎｉｔｏｒｅｎｔｅｒ命令を実行することに成功した場合には、該スレッドはオブジェクトに対して一時的に排他的ロック所有権を取得する（つまりこのスレッドは、ほかのスレッドがクリティカルな部分のコードにアクセスできないように、オブジェクトに対してロックを取得している）。第１スレッドが一時的に排他的所有権を持つオブジェクトに対して、別のスレッド、例えば第２スレッドがｍｏｎｉｔｏｒｅｎｔｅｒ命令の実行を試みた場合、第２スレッドは第１スレッド（現在のロック所有者）がｍｏｎｉｔｏｒｅｘｉｔ命令を実行して該オブジェクトの排他的ロックを解除するまで待たなければならない（例えばスリープ状態またはスピン状態でいなければならない）。
【０００５】
オブジェクトのロック状態を表すためには通常２つの状態変数を用いる。１つ目の状態変数は現在ロックを所有するスレッドのスレッド識別子に対応するロック所有者である。このロック所有者は、どのスレッドもロックを所有していない場合には、ＮＵＬＬ値もしくはＮＵＬＬスレッドに設定されるとしてもよい。２つ目の状態変数は、（再帰的ロッキングをサポートすべく）ロック所有者がロックを取得した回数を示すロック再帰カウンタである。通常、オブジェクトのロック状態の初期化は、ロック所有者をＮＵＬＬ値に設定し（非ロック状態に対応する）、ロック再帰カウンタをゼロに設定することを指す。
【０００６】
オブジェクトのロック状態を表すためには通常ロックワードを用いる。「Ｔｈｉｎ  Ｌｏｃｋ：Ｆｅａｔｈｅｒｗｅｉｇｈｔ  Ｓｙｎｃｈｒｏｎｉｚａｔｉｏｎ  ｆｏｒ  ＪＡＶＡ（小型ロック：ＪＡＶＡ用の超軽量同期）」（ベーコン他、Ｃｏｎｆｅｒｅｎｃｅ  ｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｌａｎｇｕａｇｅｓ  Ｄｅｓｉｇｎ  ａｎｄ  Ｉｍｐｌｅｍｅｎｔａｔｉｏｎ（プログラミング言語の設計・実施に関する会議）、１９９８年、第２５８頁〜第２６８頁）において、オブジェクトのロック／同期によく利用される技術が定義されている。ベーコン他によると、小型形状および大型形状という２つの形状を持つロックワードに基いた技術が定義されている。小型ロックは、スレッド識別子およびロック再帰カウンタという状態変数だけを含むとしてもよい。また小型ロックは比較的サイズが小さいので、オブジェクトのヘッダに格納するとしてもよい。大型ロックは、小型ロックが十分でない場合（例えば、オブジェクトのロックを取得するため待機状態にあるスレッドのリストが必要であるロック競合が起こった場合）にオブジェクトのロック／同期をサポートするべく、さらに複数のデータ構造を有するとしてもよい。オブジェクトは初期化されると通常、小型ロック形状になる。ロック／同期処理では例えば、小型ロックがオブジェクトのヘッダに対して大きくなりすぎると（例えば、ロック競合が起こって待機スレッドのリストが必要な場合、小型ロックが示す最高値をロック再帰カウンタが超えた場合など）ロックを大型化する。ロック／同期処理ではほとんどの場合、大型ロックを縮小して小型ロックに戻すことはしない（つまりオブジェクトのロックが大型ロックに変換されると、残りのプログラム実行時間中は大型ロックのままとなる）。
【０００７】
先行技術に係るオブジェクトのロッキング技術の多くでは（例えば、ＪＶＭ  ｍｏｎｉｔｏｒｅｎｔｅｒ命令およびＪＶＭ  ｍｏｎｉｔｏｒｅｘｉｔ命令を実行する先行技術）、ロック解除機能（例えばｍｏｎｉｔｏｒｅｘｉｔ命令に対応する）において、ロックを解除しようとしているスレッドが本当に該ロックのロック所有者であるかどうか判断する。また、ロック解除機能は、ロック再帰カウンタを確認して、ロックを解除するか維持すべきか決定する（例えば、何度も再帰的にロックが取得されている場合はロック状態が維持される）。しかし、高級言語（例えばＪＡＶＡ）を用いて記述されバイトコードにコンパイルされた、非常によく構成されたアプリケーションの場合は、対になったロック取得動作とロック解除動作が含まれる（例えば、ＪＶＭ  ｍｏｎｉｔｏｒｅｎｔｅｒ命令およびＪＶＭ  ｍｏｎｉｔｏｒｅｘｉｔ命令の対）ので、同期特性が平衡である（つまり、ロッキング処理は、同一スレッドによって行われる平衡なロック取得とロック解除の対を含む）。平衡な同期特性を持つコードにおいて、追加で行わなければならない、ロック所有者およびロック再帰カウンタという状態変数の確認は不必要であり、そのためアプリケーションの実行効率が全体的に下がってしまうことがある。
【図面の簡単な説明】
【０００８】
【図１】本明細書で説明する方法、装置および製品の例が利用される、マネージドランタイム環境を例示するブロック図である。
【０００９】
【図２】図１に示したマネージドランタイム環境で用いられるロックマネージャを例示するブロック図である。
【００１０】
【図３Ａ】図１に示したマネージドランタイム環境で用いられる、先行技術に係るロックマネージャの例で利用する、ロックワードを例示する。
【００１１】
【図３Ｂ】図２に例示したロックマネージャで利用するロックワードを例示する。
【００１２】
【図４Ａ】図１に示したマネージドランタイム環境で用いられる先行技術に係るロックマネージャの例を実施するべく、マシンによって実行される機械可読命令の例を示すフローチャートである。
【図４Ｂ】図１に示したマネージドランタイム環境で用いられる先行技術に係るロックマネージャの例を実施するべく、マシンによって実行される機械可読命令の例を示すフローチャートである。
【００１３】
【図５】図２に示したロックマネージャの例を実施するべく、マシンによって実行される機械可読命令の例を示すフローチャートである。
【００１４】
【図６】図２に示した楽観的平衡ロック同期部の例を実施するべく、マシンによって実行される機械可読命令の例を示すフローチャートである。
【００１５】
【図７】図２に示した不平衡ロック取得部の例を実施するべく、マシンによって実行される機械可読命令の例を示すフローチャートである。
【００１６】
【図８】図２に示した不平衡ロック解除部の例を実施するべく、マシンによって実行される機械可読命令の例を示すフローチャートである。
【００１７】
【図９】図６および図７に示したプロセスで用いられる、保留中の平衡な解除の状態を変形するべく、マシンによって実行される機械可読命令の例を示すフローチャートである。
【００１８】
【図１０Ａ】図２に示すロックマネージャが行う処理の例を示す。
【図１０Ｂ】図２に示すロックマネージャが行う処理の例を示す。
【図１０Ｃ】図２に示すロックマネージャが行う処理の例を示す。
【００１９】
【図１１】図２に示したロックマネージャを実施するべく、図４から図９に示したプロセスを実行するプロセッサシステムの例を示す概略図である。
【発明を実施するための最良の形態】
【００２０】
図１は、本明細書で説明する方法、装置および製品の例が利用される利用環境１００の例を示すブロック図である。例である利用環境１００は、例えば図１１を参照して後述する、例であるプロセッサシステム１１００のようなプロセッサシステムを１以上用いて実施されるとしてもよい。図１に示す例は、ＪＡＶＡを用いた、マネージドランタイム環境（ＭＲＴＥ）に対応するが、本明細書で説明する方法、装置および製品の例は、同様のＭＲＴＥ利用環境に応用できることは当業者には明らかである。同様のＭＲＴＥ利用環境として例えば、ＣＬＩおよび対応するＣ＃言語がある。
【００２１】
利用環境１００は、図１に示すように、ＪＡＶＡ仮想マシン（ＪＶＭ）１１０として図示したＭＲＴＥを有する。例であるＪＶＭ１１０は、マシンに依存しない命令であるバイトコード１１４によって表現されるプログラムを、マシンに依存するネイティブの命令に動的に変換し、このネイティブ命令を１以上のプロセッサ１２０（例えば後述するプロセッサ１１１２）で実行する。ＪＶＭ１１０は、１以上のプロセッサ１２０に固有のオペレーティングシステム（ＯＳ）１３０を介してネイティブ命令を実行するとしてもよい。そのようなＯＳ１３０の例として、Ｍｉｃｒｏｓｏｆｔ  Ｗｉｎｄｏｗｓ  ＯＳ、ＵＮＩＸ  ＯＳやＬｉｎｕｘ  ＯＳなどがある。
【００２２】
図１に示した例によると、ＪＶＭ１１０は複数のクラスファイル１１４に格納されているバイトコード１１４を処理する。１つのクラスファイル１１４は通常、単一のＪＡＶＡクラスに対応するバイトコード１１４を格納し、バイトコード１１４はクラスを定義するインターフェース、フィールドおよびメソッドを含む。クラスファイル１１４は、例えばソフトウェア開発者によって記述されたＪＡＶＡプログラムソースコード１３８に基づき、ＪＡＶＡコンパイラ１３４によって生成されるとしてもよい。ＪＡＶＡコンパイラ１３４、対応ＪＡＶＡソースコード１３８およびクラスファイル１１４（またはバイトコード１１４）は公知技術であり、これ以上の説明は省略する。
【００２３】
クラスファイル１１４を処理するべく、ＪＶＭ１１０はクラスローダ１４２を有する。クラスローダ１４２は、１以上の所定のクラスに対応する１以上の所定のクラスファイル１１４の位置を特定し、特定されたクラスファイル１１４を、ロードされたクラスファイル１１４のローカル画像をローカルメモリ１４６に格納することによって、ＪＶＭ１１０の実行エンジン１４４にロードする。ロードされたクラスファイル１１４をメモリ１４６に格納する前に、クラスローダ１４２はバイトコード検証器１５０を呼び出し、ロードされたクラスファイル１１４の構造が正しくＪＡＶＡ言語の構成に従ったものになっているかどうか検証させるとしてもよい。このような検証を行うにしろ行わないにしろ、ＪＶＭ１１０の実行エンジン１４４は続いて、ロードされた機械に依存していないバイトコードを、例えばインタープリータ１５４および／または１以上のジャスト・イン・タイム（ＪＩＴ）コンパイラ１５８を用いて、機械に依存した命令に変換する。
【００２４】
インタープリータ１５４はバイトコード１１４を変換して、バイトコード１１４の機能をターゲットプロセッサ１２０で実現するための一連の機械位存命令を生成する。つまり、インタープリータ１５４は、プロセッサ１２０が直接ＪＡＶＡ命令セットをサポートしているかのように、バイトコード１１４をターゲットプロセッサ１２０上で実行するべく、エミュレーション層を提供する。一方ＪＩＴコンパイラ１５８は、一連のバイトコード１１４をコンパイルして、ターゲットプロセッサ１２０で実行するための一連の機械依存命令を生成する。各バイトコード１１４の機能が機械依存命令に正確には変換されないこともあるが、コンパイルの結果生成された一連の機械依存命令の機能は全体的に、元々の一連のバイトコード１１４に等しいものとなっている。このため、ＪＩＴコンパイラ１５８が生成するコードは、インタープリータ１５４が生成するコードより適切であるとしてもよい。しかし、インタープリータ１５４の方がＪＩＴコンパイラ１５８よりも実施しやすいこともある。
【００２５】
インタープリータ１５４および／または１以上のＪＩＴコンパイラ１５８が生成するプログラムコードを実行するべく、ＪＶＭ１１０の実行エンジン１４４はローカルメモリ１４６内に１以上の記憶領域を定義するとしてもよい。例えば、複数の同時スレッドの実行をサポートすべく、ＪＶＭ１１０はメモリ１４６内に、各スレッドに対して別々の仮想プログラムカウンタ（ＰＣ）レジスタおよび別々のＪＶＭスタックフレームを割り当てるとしてもよい。ＪＶＭスタックフレームは例えば、対応付けられた実行スレッドに対応するローカル変数および部分結果を格納するために用いられるとしてもよい。また、ＪＶＭ１１０はローカルメモリ１４６内に、すべてのスレッドが共有する記憶領域を定義するとしてもよい。すべてのスレッドが共有する記憶領域は例えば、プログラム実行中に生成されたオブジェクトを格納するためのヒープ、例えばあるクラス用のメソッドを実施するために用いられるデータやコードを格納するためのメソッド領域、およびあるクラスに対応付けられた定数を格納するためのランタイム定数プールを含むとしてもよい。メモリ１４６のランタイム部分を効率よく管理するべく、ＪＶＭ１１０は不要情報コレクタ１６２を有するとしてもよい。不要情報コレクタ１６２は例えば、後続のプログラムを実行するべく、オブジェクトをヒープからフリーメモリに自動的に開放する。
【００２６】
複数の同時スレッドの実行をサポートすべく、ＪＶＭ１１０の実行エンジン１４４はスレッドサポートモジュール１６６を有する。スレッドサポートモジュール１６６は、スレッドオブジェクトを生成し、該スレッドのスタートメソッドを呼び出して該スレッドを実行することによって、スレッドの生成をサポートする。さらに、スレッドサポートモジュール１６６は、優先レベルを利用することによって、スレッドの優先実行をサポートするとしてもよい。本明細書の開示内容で特に強調しておきたいのは、ＪＶＭ１１０の実行エンジン１４４がさらに、２以上のスレッドが同一の共有オブジェクトにアクセスを試みた結果発生するコンフリクトを解決すべく、ロックマネージャ１７０を有することである。
【００２７】
ＪＶＭ１１０に対応する業界標準仕様（ならびにそのほかのマネージドランタイム環境の仕様）では、複数のスレッド間でのオブジェクトの同期をサポートするための処理が定義されている。ＪＶＭ１１０は各オブジェクトについて同期ロックを行う。スレッドは、オブジェクトに対応付けられたロックの所有権を取得することによって、オブジェクトの所有権を取得するとしてもよい。同様にスレッドは、オブジェクトに対応付けられたロックの所有権を解除することによって、オブジェクトの所有権を解除するとしてもよい。ＪＡＶＡプログラミング言語において、オブジェクトおよびメソッドの同期はｓｙｎｃｈｒｏｎｉｚｅｄステートメントによって実行される。ＪＶＭ１１０の仕様では、ｍｏｎｉｔｏｒｅｎｔｅｒバイトコードおよびｍｏｎｉｔｏｒｅｘｉｔバイトコードに基づいてロック取得動作およびロック解除動作がそれぞれ定義されている。しかし、ｍｏｎｉｔｏｒｅｎｔｅｒバイトコードおよびｍｏｎｉｔｏｒｅｘｉｔバイトコードの実行については定義されていない。
【００２８】
図２は、図１に示したロックマネージャ１７０を実行するために用いられる、ロックマネージャ２００の例を示すブロック図である。ロックマネージャ２００は、ロック取得／ロック解除の大半は平衡もしくは楽観的に平衡であるという前提に基づいて、スレッドのためにオブジェクトのロックを取得および解除する。例えば、ロックマネージャ２００が一連のロック取得動作およびロック解除動作が平衡であると判定するのは、取得・解除動作が同一ネストレベルで発生し、該動作間に実行されるクリティカルな部分のコードが同期動作を含まない、もしくはロックに対する別の平衡な同期動作だけを含む場合である（例えば、スレッドはオブジェクトのロックを取得し、クリティカルな部分のプログラムコードを実行し、オブジェクトのロックを解除する）。同様に、ロックマネージャ２００が一連のロック取得動作およびロック解除動作が楽観的に平衡であると判定するのは、取得・解除動作が同一のネストレベルで発生しているものの、ロックマネージャ２００が該動作がすべて平衡であると確信を持てない場合であるとしてもよい（例えば、クリティカルな部分のコードがメソッドコールを含む場合）。高級言語（例えばＪＡＶＡ）を用いて記述されたバイトコード（例えばバイトコード１１４）にコンパイルされる、非常によく形成されたプログラムは、平衡な同期特性を示す（つまり、上述したように平衡な取得と解除の対を含む同期）。しかしまれに、ロック取得／ロック解除が平衡にならない場合がある（例えば、手動で記述したバイトコードを用いて実行されるプログラムの場合）。従って、ロックマネージャ２００は、平衡なロック処理手順および楽観的に平衡なロック処理手順に加え、オブジェクトのロックの取得および解除について、不平衡なロック取得・解除処理手順を定義するとしてもよい。
【００２９】
図２に示すように、ロックマネージャ２００はロック同期コントローラ２０４を有する。ロック同期コントローラ２０４は、実行スレッドからオブジェクト識別子の入力２０８およびスレッドコンテキストの入力２１２を受け取る。オブジェクト識別子入力２０８は、同期の対象となるオブジェクトを識別するのに用いられ、一意的なオブジェクトインスタンス識別子、該オブジェクト用のロックワードなどを含むとしてもよい。スレッドコンテキスト入力２１２は、オブジェクト識別子入力２０８によって識別されるオブジェクトをロックまたはロック解除することを求めているスレッド、該スレッドの動作状態および該オブジェクトのロックに対して行われる動作（例えば、ロック取得またはロック解除、ならびに取得および／または解除は平衡かどうか、楽観的に平衡か、または不平衡か）を特定するために用いられる。ロック同期コントローラ２０４は、オブジェクトのロックの状態を示すべく、オブジェクトロック状態の出力２１６を提供する（例えば、始めての取得、再帰的な取得、解除／解放、例外スローなど）。
【００３０】
ロック同期コントローラ２０４はさらに、オブジェクト識別子入力２０８が特定するオブジェクトのロックに対して行われるロック動作のタイプに基づいて、所定のロック動作部を呼び出す。ロック動作のタイプの例を挙げると、楽観的に平衡なロック同期（オブジェクトのロックの平衡な同期もしくは楽観的に平衡な同期に対応する）、不平衡なロック取得および不平衡なロック解除がある。ロック同期コントローラ２０４は、スレッドコンテキスト入力２１２によって提供された情報に基づき、ロック動作のタイプを判定するとしてもよい。このような情報は、バイトコード１１４を、スレッドコンテキスト入力２１２によって特定されるスレッドによって実行されている一連の機械依存命令へ変換する、例えば図１に示したインタープリータ１５４および／またはＪＩＴコンパイラ１５８によって特定されるとしてもよい。
【００３１】
オブジェクトの平衡ロック同期を行うべく（またはオブジェクトの楽観的平衡同期の場合には平衡な同期を行うことを試みるべく）、ロックマネージャ２００は、楽観的平衡ロック同期部２２０を有する。ロック同期コントローラ２０４が、（例えばオブジェクト識別子入力２０８およびスレッドコンテキスト入力２１２に基づいて）平衡な（もしくは楽観的に平衡な）同期をオブジェクトに対して行うべきであると判定した場合、楽観的平衡ロック同期部２２０は、オブジェクトに対応付けられたロックの現在の形状が楽観的に平衡な同期をサポートするかどうか判定するとしてもよい。例えば、楽観的平衡ロック同期部２２０は、オブジェクトに対応付けられたロックが小型モードである場合に限り、オブジェクトの楽観的に平衡な同期を行うように構成されているとしてもよい。楽観的平衡ロック同期部２２０は、（例えば、以前に発生したオブジェクトロックの競合、ロックに対して以前に行われた不平衡なロック動作などが原因で）ロックが大型モードである場合、公知のロック技術（例えば、上述したベーコン他が開示している技術内容）に戻るように構成されるとしてもよい。
【００３２】
例えば、ロックされる対象のオブジェクトと対応付けられているのが小型ロックである場合、楽観的平衡ロック同期部２２０はすでに該オブジェクトのロックを取得したスレッドがあるかどうか判定する。所望のオブジェクトのロックが利用できる場合（もしくは、現在ロックを要求しているスレッドがすでに所有している場合）、楽観的平衡ロック同期部２２０はロックの現在の状態を格納して、該スレッドのためにロックを取得する。ロックが利用できない場合、もしくは例えば、該オブジェクトと対応付けられているのが大型ロックの場合、楽観的平衡ロック同期部２２０は、該ロックが利用可能になった場合にこのスレッドのためにロックを取得するべく、公知のロック大型化／競合処理手順を呼び出す。どちらの場合でも、楽観的平衡ロック同期部２２０は続いて、オブジェクトのロックが既に取得済みであることを指し示すべく、ロック同期コントローラ２０４にロック状態出力２１６を更新させるとしてもよい。
【００３３】
ロックされたオブジェクトを必要としたコードの実行をスレッドが終了すると（例えばスレッドコンテキスト入力２１２が示す）、楽観的平衡ロック同期部２２０には、オブジェクトに対応付けられているのがまだ小型ロックの場合はロックを以前の状態に復元することによって、もしくは大型ロックの場合は公知の大型ロック解除処理手順を実行することによってオブジェクトのロックを解除するように伝えられるとしてもよい。オブジェクトのロックが解除されると、楽観的平衡ロック同期部２２０は、ロック同期コントローラ２０４に、適切にオブジェクトロック状態出力２１６を更新させてもよい。単一スレッドによる再帰的なロックの取得をサポートすべく、楽観的平衡ロック同期部２２０は、所定のオブジェクトの楽観的に平衡な同期すべてに対応するすべてのアクティブな楽観的に平衡なロック取得の状態を記録するための同期マップを有する。この同期マップは、ロック再帰カウンタの代わりに、スレッドがあるオブジェクトを取得した回数を記録するために用いられるとしてもよい。
【００３４】
不平衡なロック取得もしくは不平衡なロック解除を行うべく、ロックマネージャ２００は不平衡ロック取得部２２４および不平衡ロック解除部２２８を有する。ロック同期コントローラ２０４が（例えばスレッドコンテキスト入力２１２に基づいて）オブジェクトに対して不平衡ロック取得を行う必要があると判定した場合、不平衡ロック取得部２２４は、ロックが利用可能である場合（もしくは当該スレッドによってすでに所有されている場合）は該スレッドのためにオブジェクトのロックを取得、もしくはロックが利用できない場合は公知のロック競合処理手順を呼び出す。ロック同期コントローラ２０４がオブジェクトに対して不平衡ロック解除を行う必要があると判定した場合、不平衡ロック解除部２２８は、該スレッドが現在該オブジェクトのロックを所有している場合には、該オブジェクトのロックを解除／解放する。該スレッドが該オブジェクトのロックを所有していない場合には、不平衡ロック解除部２２８は、試みたロック解除は無効であった旨を示す例外をスローする。続いて、ロック取得もしくはロック解除のどちらが行われたかによって、不平衡ロック取得部２２４もしくは不平衡ロック解除部２２８の一方が、ロック同期コントローラ２０４にロック状態出力２１６を更新させて、該オブジェクトの適切なロック状態を示させるとしてもよい。また、該オブジェクトと現在対応付けられているのが小型ロックである場合、不平衡ロック取得部２２４または不平衡ロック解除部２２８が該オブジェクトのロック状態を大型化するとしてもよい。
【００３５】
不平衡ロック取得部２２４および不平衡ロック解除部２２８はどちらも、楽観的平衡ロック同期部２２０が格納する、アクティブな楽観的に平衡なロック取得の状態を示した同期マップを変更しなければならないとしてもよい。例えば、不平衡なロック取得または不平衡なロック解除のため、オブジェクトに対するロックを小型ロックから大型ロックへと大型化する必要があることもある。このようなロック大型化処理を行うために、同期マップのエントリに基づいて状態変数であるロック再帰カウンタを決定するとしてもよい。さらに、保留中の平衡な解除それぞれについて、同期マップ内にあるロック形状フラグを変更する必要があるとしてもよい。このように楽観的平衡ロック同期部２２０が維持する同期マップを更新するべく、ロックマネージャ２００は平衡同期状態記録部／変更部２３６を有する。平衡同期状態記録部／変更部２３６は、あるオブジェクトに対応するアクティブな楽観的に平衡な取得の数を特定し、あるアクティブな楽観的に平衡なロック取得に対応するロック形状を変更するように構成されるとしてもよい。平衡同期状態記録部／変更部２３６は、実行中のロック動作に基づき（つまり不平衡な取得または不平衡な解除に対応して）、不平衡ロック取得部２２４または不平衡ロック解除部２２８によって呼び出されるとしてもよい。
【００３６】
図３Ａは、先行技術に基づくロックマネージャ１７０の（図１参照）実施例で用いられるロックワードのフォーマットを例示する。逆に図３Ｂは、本発明に基づくロックマネージャ１７０の（図１参照）実施例、および／またはロックマネージャ２００で用いられるロックワードのフォーマットを例示する。図３Ａには、小型ロックおよび大型ロックをサポートする先行技術に係るロックワードのフォーマットを例示する。先行技術に係るロックワードフォーマット３００は３２ビットで、小型ロックおよび大型ロックをサポートする。ロックワードの形状（例えば、小型または大型）は１ビットのロック形状３０４で示される。例えば、値０は小型ロックを表し、値１は大型ロックを表すとしてもよい。小型ロックの場合（例えば、ロック形状３０４が０の場合）、ロックワードフォーマット３００は１５ビットのロック所有者識別子（ＩＤ）３０８および８ビットの再帰カウンタ３１２を有する。ロック形状ビット３０４とロック所有者ＩＤ３０８によって、ロック所有者フィールド３１６が形成される。残りの８ビットから成るその他フィールド３２０は例えば、オブジェクトハッシュコード、不要情報コレクタ１６２が用いるフラグなどの、オブジェクトに関連するほかの情報を格納するために用いられるとしてもよい。
【００３７】
大型ロックの場合（例えば、ロック形状３０４が１の場合）、ロックワードフォーマット３００は２３ビットのモニタＩＤ３２４を有する。モニタＩＤ３２４は例えば、オブジェクトロックに対応する大型ロックキャッシュに格納された一連のデータ構造を示す大型ロックキャッシュインデックスを格納するとしてもよい。先述したように、ベーコン他の開示内容のような先行技術に係るオブジェクトロック／同期技術によると、小型ロックが小型ロックフォーマットには大きくなりすぎた場合に小型ロックを大型化するとしてもよい。このような大型化が起こるのは例えば、ロック競合が発生しロック待機中のスレッドのリストをオブジェクトと対応付ける必要がある場合（例えば、ロック所有者ＩＤ３０８が１つでは不十分の場合）や再帰カウンタがオーバーフロー状態になった場合（例えば、８ビットの再帰カウンタフィールド３１２に収まらなくなった場合）などがある。
【００３８】
図３Ｂには、本発明の実施形態に係る、１６ビットの（図３Ａに示した先行技術に係るロックワードフォーマット３００が必要とするビット数の３分の２）小型ロックおよび大型ロックをサポートするロックワードフォーマット３５０を例示する。ロックワードの形状（例えば、小型または大型）は１ビットのロック形状３５４で示される。例えば、値０は小型ロックを表し、値１は大型ロックを表すとしてもよい。小型ロックの場合（例えば、ロック形状３５４が０の場合）、ロックワードフォーマット３５０は１５ビットのロック所有者識別子（ＩＤ）３５８を有する。ロック形状ビット３５４とロック所有者ＩＤ３５８によって、ロック所有者フィールド３６２が形成される。先行技術に係るロックワードフォーマット３００とは違い、本発明の実施形態に係るロックワードフォーマット３５０は再帰カウンタを有していない。これは、上述したように、オブジェクトに対して行われたロック取得の数は間接的に、同期マップによって記録されているためである。
【００３９】
大型ロックの場合（例えば、ロック形状３５４が１の場合）、ロックワードフォーマット３５０は１５ビットのモニタＩＤ３６６を有する。先行技術に係るロックワードフォーマット３００に含まれるモニタＩＤ３２４は、オブジェクトロックに対応する大型ロックキャッシュに格納された一連のデータ構造を示す大型ロックキャッシュインデックスを格納するとしてもよい。図２を参照しつつ上述したが、本発明の実施形態に係るロック技術（例えばロックマネージャ２００）で小型ロックを大型化するのは、不平衡なロック動作がオブジェクトのロックに対して行われた場合であってもよい。例を挙げると、不平衡なロック取得または不平衡なロック解除が行われると、小型ロックが大型ロックに変換されるとしてもよい。
【００４０】
図４Ａおよび図４Ｂに、図１に示したロックマネージャ１７０を実施するための公知の機械可読命令を表すフローチャートを示す。一方、図１に示したロックマネージャ１７０および／または図２に示したロックマネージャ２００を実施するための本発明の実施形態に係る機械可読命令を表すフローチャートは、図５から図９に示す。図５から図９の各フローチャートが表すプロセスは、プロセッサ（例えば図１１を参照して後述するコンピュータ１１００に含まれるプロセッサ１１１２）によって実行される１以上のプログラムを含む一連の機械可読命令によって実施されるとしてもよい。このようなプログラムは、有形媒体（例えば、プロセッサ１１１２に対応付けられたＣＤ−ＲＯＭ、フロッピーディスク、ハードドライブ、ＤＶＤまたはメモリ）に格納されたソフトウェアによって実施されるとしてもよい。しかし、プログラム全体および／またはその一部分が、プロセッサ１１１２以外のデバイスで代わりに実行されることも可能で、および／または公知技術に基づきファームウェアまたは専用ハードウェアによっても実施できることは当業者には明らかである。例えば、ロックマネージャ１７０および／またはロックマネージャ２００は、ソフトウェア、ハードウェア、および／またはファームウェアを自由に組み合わせて実施することができる。また、プログラムの例を図５から図９に図示したフローチャートを参照して説明するが、本明細書に開示した方法および装置を実施するにはこれ以外の方法を代わりに用いることも可能であることは当業者には明らかである。例えば、図５から図９に図示したフローチャートに基づき、ブロックの実行順を変更するとしてもよいし、および／または図示したブロックのうち幾つかを変更、省略、結合および／または複数のブロックにさらに分割するとしてもよい。
【００４１】
図２に示したロックマネージャ２００の特性および特徴、ならびに図５から図９に示したフローチャートが表すプロセスでの動作を分かりやすく説明するべく、図４Ａおよび図４Ｂに、図１のロックマネージャ１７０を実施するための先行技術に係るプロセスを示す。具体的に言うと、図４Ａは、オブジェクトのロックを取得するための、先行技術に係るプロセス４００を例示し、図４Ｂは、オブジェクトのロックを解除するための、先行技術に係るプロセス４５０を例示する。図示されていないが、制御プロセスを用いて、実行プログラムスレッドの状態に基づき、ロック取得処理手順とロック解除処理手順のどちらを呼び出すべきか判定するとしてもよい。
【００４２】
図４Ａに示すように、先行技術に係るロック取得プロセス４００は、ロックの対象であるオブジェクトに対応付けられたロックの旧ロック所有者に対応する変数／レジスタを、該ロックを表すロックワードの小型ロック所有者フィールド（例えば、図３Ａに示した小型ロック所有者フィールド３１６）の現行値と等しい値に設定することから始まる。プロセス４００は続いて、現在のスレッドのためにオブジェクトをロックしようと試みる（つまりスレッドがロックを要求する）。この動作では、まずロックの対象となっているオブジェクトのロックを既に所有しているスレッドがあるかどうか判定され、および／または該オブジェクトと大型ロックが対応付けられているかどうか判定される（つまり、小型ロック所有者フィールド３１６がＮＵＬＬ値に設定されているかどうか判定する）（ブロック４０４）。どのスレッドも所有しておらず、小型ロックが該オブジェクトと対応付けられており（つまり、小型ロック所有者フィールド３１６がＮＵＬＬ値に設定されている）（ブロック４０４）、従って該オブジェクトのロックが解除されていると判定した場合、プロセス４００は、ロック所有者ＩＤ（例えば、ロック所有者ＩＤ３０８）を該スレッドを表す値（例えば、一意的なスレッド識別子値）に設定することによって、該スレッドのためにロックを取得する（ブロック４０８）。一方、ロックを所有しているスレッドがあるか、大型ロックが該オブジェクトと対応付けられている（つまり、小型ロック所有者フィールド３１６がＮＵＬＬ値に設定されていない）と判定された（ブロック４０４）場合、プロセス４００はロック所有者ＩＤ３０８をそのままにする。第１スレッドがすでにロック所有者になるためのプロセスを実行している間に第２スレッドが同じロックの取得を試みないように、ブロック４０２、４０４、４０８は通常１回の不可分動作で行われる（例えば、インテルのＩｔａｎｉｕｍプロセッサに分類されるプロセッサで行われるｃｍｐｘｃｈｇ命令など）。不可分動作で実行することによって、スレッド（および／またはマルチプロセッサシステムのプロセッサ）は該不可分動作の実行中には共有メモリに対して排他的アクセスを得ることができる。このため、不可分動作の実行中は、該不可分動作によってアクセスされた格納場所をほかのスレッドが変更することはできない。
【００４３】
小型ロック所有者フィールド３１６がＮＵＬＬ値でない（ブロック４０４）、またはロック所有者ＩＤ３０８が現在のスレッドに設定されている（ブロック４０８）と判定された場合、プロセス４００は続いて、該オブジェクトの旧ロック所有者がＮＵＬＬ値であるかどうか（現在のスレッドがブロック４０８でロックを取得した場合と対応する）判定する（ブロック４１２）。旧ロック所有者がＮＵＬＬ値である場合（ブロック４１２）、プロセス４００は終了する。しかし旧ロック所有者がＮＵＬＬ値でないと判定された場合（ブロック４１２）、プロセス４００は旧ロック所有者が現在のスレッドかどうか（現在のスレッドが既に該オブジェクトの小型ロックを以前に取得していた場合に対応する）判定する（ブロック４１４）。旧ロック所有者が現在のスレッドである場合（ブロック４１４）、プロセス４００は現在のスレッドが該オブジェクトの小型ロックを複数回取得したことを指し示すべく、例えば該ロックに対応付けられたロック再帰カウンタを増加させるとしてもよい。プロセス４００はこれで終了する。
【００４４】
しかし旧ロック所有者が現在のスレッドではなく（ブロック４１４）、このため別のスレッドが既に該オブジェクトの小型ロックを所有している、または大型ロックが該オブジェクトと対応付けられていると判定された場合、プロセス４００は、現在のロック所有者（存在する場合）がロックを解除した後で、公知のロック大型化／競合処理手順を呼び出し、現在のスレッドに該オブジェクトの大型ロックを取得させる（ブロック４２０）。プロセス４００は例えば、現在のロック所有者（存在する場合）が該オブジェクトのロックを解除／解放するまで、現在のスレッドを実行ループでスピンさせるか現在のスレッドに実行を中止させるとしてもよい。該オブジェクトのロックが利用可能になると、プロセス４００は現在のスレッドのためにロックを大型化して取得するとしてもよい。プロセス４００はこれで終了する。
【００４５】
続いて、図４Ｂに示すように、先行技術に係るロック解除プロセス４５０は、まず該オブジェクトに対応付けられたロックの形状を判定することによって、現在のスレッドのためにオブジェクトのロック解除を試みる（つまり、スレッドが解除を要求する）ことから始まる（ブロック４５２）。該オブジェクトに大型ロックが対応付けられている場合（例えば、図３Ａに示したロック形状ビット３０４に基づいて判定する）、プロセス４５０は続いて、該オブジェクトの大型ロックを解除すべく、公知の大型ロック解除処理手順を呼び出す（ブロック４５４）。プロセス４５０はこれで終了する。しかし、小型ロックが該オブジェクトと対応付けられている場合（ブロック４５２）、プロセス４５０は続いて、該オブジェクトに対応付けられた該小型ロックのロック所有者ＩＤ（例えばロック所有者ＩＤ３０８）が現在のスレッドに対応するかどうか判定する（ブロック４５６）。ロック所有者ＩＤ３０８が現在のスレッドに一致せず、現在該ロックを所有しているのが別のスレッドである場合（ブロック４５６）、プロセス４５０は例外をスローする（ブロック４５８）。ブロック４５８において、（ロックを所有しないスレッドが該オブジェクトを解除しようと試みたので）プロセス４５０は公知の例外ハンドリング技術を用いて、試みられた解除は無効であることを指し示すための例外をスローするとしてもよい。プロセス４５０はこれで終了する。
【００４６】
しかし、ロック所有者ＩＤ３０８が現在のスレッドに一致する場合（ブロック４５６）、プロセス４５０は、該ロックに対応付けられたロック再帰カウンタ（例えば再帰カウンタ３１２）が０であるかどうか（もしくは、別の方法で、該ロックが持つ現在アクティブなロック取得が１つだけであることが示されているかどうか）判定する（ブロック４６２）。ロック再帰カウンタ３１２がゼロである場合（ブロック４６２）、プロセス４５０は、例えばロック所有者ＩＤ３０８をＮＵＬＬ値に設定することによって、該オブジェクトのロックを解除する（ブロック４６６）。しかしロック再帰カウンタ３１２がゼロでない場合（ブロック４６２）、プロセス４５０は（例えば今回のロック解除はアクティブなロック取得に対応するものであることを指し示すべく）ロック再帰カウンタ３１２を減少させる（ブロック４７０）。ブロック４６６またはブロック４７０での処理が完了すると、プロセス４５０は終了する。
【００４７】
図４Ａおよび図４Ｂに示した先行技術に係るプロセス４００および４５０を理解した上で、図５に示された、図２のロックマネージャ２００を実施するために用いられるロックマネージャプロセス５００を参照されたい。ロックマネージャプロセス５００は例えば、同期されたオブジェクトに対して実行されている１以上のスレッドのさまざまな実行段階中に呼び出されるとしてもよい。プロセス５００は例えば、オブジェクトのロックを取得または解除するべく呼び出されるとしてもよい。
【００４８】
ロックマネージャプロセス５００は、どのタイプのロック動作を現在のスレッドのためにオブジェクトのロックに対して行うのか特定することから始まる（ブロック５０４）。有効なロック動作としては例えば、楽観的に平衡なロック同期（楽観的に平衡なロック取得およびロック解除の対を含む）や不平衡なロック取得および不平衡なロック解除がある。例えば、ＪＩＴコンパイラ（例えば、図１に示したＪＩＴコンパイラ５１８）は、プログラム実行中の適切な時点においてオブジェクトのロックに対して行われるロック動作のタイプを決定するべく、制御フローグラフおよび／またはデータフロー分析を用いるとしてもよい。ＪＩＴコンパイラ１５８は続いて、ブロック５０４において適切なロック動作を特定するためにロックマネージャ２００またはロックマネージャプロセス５００が用いる、コンパイルされたコードを出力するとしてもよい。プロセス５００においてロック動作が平衡か（または少なくとも楽観的に平衡か）もしくは不平衡かどうか判定するために用いる技術はどの公知技術であってもよいので、詳細な説明は省略する。
【００４９】
ブロック５０４でロック動作を特定するとその結果に基づき、制御はブロック５０８、５１２および５１６のうちのいずれかに進む。ブロック５０８においては、ロックマネージャ２００がオブジェクトのロックに対して楽観的平衡同期処理を行う。ブロック５１２においては、ロックマネージャ２００がオブジェクトのロックに対して不平衡ロック取得処理を行う。ブロック５１６においては、ロックマネージャ２００がオブジェクトのロックに対して不平衡ロック解除処理を行う。ブロック５０８、５１２および５１６で行われる処理についてはそれぞれ、図６、図７および図８を参照しつつ後で詳述する。
【００５０】
ブロック５０８、５１２または５１６での処理が完了すると、プロセス５００は今後のスレッド実行ポイントにおいて解除を行う必要がある、保留中のロックされたオブジェクトが少なくとも１つあるかどうか判定する（ブロック５２０）。保留中のロックされたオブジェクトがあれば（ブロック５２０）、制御はブロック５０４およびそれに後続する、保留中のロックされたオブジェクトのロック（およびロックされる予定のオブジェクトのロック）を処理するためのブロックに戻る。しかし、保留中のロックされたオブジェクトがない場合（ブロック５２０）、プロセス５００はほかにロックするオブジェクトがあるかどうか判定する（ブロック５２４）。ほかにロックするオブジェクトがある場合（ブロック５２４）、制御はブロック５０４およびそれに後続する、ロック予定のオブジェクトのロックを処理するためのブロックに戻る。しかし、ほかにロックするオブジェクトがない場合（ブロック５２４）、ここでプロセス５００は終了する。ブロック５２０および／またはブロック５２４で行われる条件動作の代わりに、例えばプログラム（またはプログラムのスレッド）がまだ実行中かどうかについて直接的もしくは間接的な判定を行ってもよいことは当業者には明らかである。プロセス５００がまだ実行中である場合、制御はブロック５０４およびそれに後続するブロック５０８、５１２および５１６に戻るとしてもよい。このようなサイクルは、プロセス５００（もしくはすべてのスレッドの実行）が終了するまで繰り返されるとしてもよい。
【００５１】
図６に、図５のブロック５０８での処理を行うために用いられる、および／または図２の楽観的平衡ロック同期部２２０を実施するための、楽観的平衡ロック同期プロセス６００を例示する。楽観的平衡ロック同期プロセス６００は、大型ロックフラグをＦＡＬＳＥに初期化することから始まる（ブロック６０２）。大型ロックフラグは、ロックに対応付けられた現在のロック形状（例えば、小型または大型）を示すものである。プロセス６００は続いて、該ロックの旧ロック所有者に対応する変数／レジスタを、該オブジェクトのロックに対応付けられた小型ロック所有者フィールド（例えば、図３Ｂに示した小型ロック所有者フィールド３６２）の現在の値に等しくなるように設定する（ブロック６０４）。続いてプロセス６００は、ロックの対象であるオブジェクトのロックを既に所有しているスレッドがあるかどうか、および／または該オブジェクトと大型ロックが対応付けられているかどうか（つまり、該オブジェクトについてロック所有者が存在するかどうか、ロック所有者がＮＵＬＬ値に設定されているかどうか）判定する（ブロック６１２）。ロックを所有しているスレッドがなく、該オブジェクトと小型ロックが対応付けられており（つまり、小型ロック所有者フィールド３６２がＮＵＬＬ値である）（ブロック６１２）、このため該オブジェクトのロックが解除されている場合、プロセス６００は、該ロックの小型ロック所有者ＩＤ（例えば小型ロック所有者ＩＤ３５８）を該スレッドを表す値（例えば、一意的なスレッド識別子の値）に設定することによって、該スレッドのために該オブジェクトの小型ロックを取得する（ブロック６１６）。しかし、ロック所有者が既に存在し、および／または該オブジェクトと大型ロックが対応付けられていると判定された場合（つまり小型ロック所有者フィールド３６２がＮＵＬＬ値でない場合）（ブロック６１２）、プロセス６００は、小型ロック所有者ＩＤ３５８をそのままにする。
【００５２】
第１スレッドがすでにロック所有者になるためのプロセスを実行している間に第２スレッドがロックの取得を試みないように、ブロック６０４、６１２および６１６は通常１回の不可分動作で行われる（例えば、インテルのＩｔａｎｉｕｍプロセッサに分類されるプロセッサで行われるｃｍｐｘｃｈｇ命令など）。上述したが、不可分動作で実行することによって、スレッド（および／またはマルチプロセッサシステムのプロセッサ）は該不可分動作の実行中には共有メモリに対して排他的アクセスを得ることができる。このため、不可分動作の実行中は、該不可分動作によってアクセスされた格納場所を、ほかのスレッドが変更することはできない。例を挙げると、ブロック６０４、６１２および６１６で行われる処理は、以下の命令列に従ってインテルのＩｔａｎｉｕｍプロセッサに分類されるプロセッサによって行われるとしてもよい。
【００５３】
（式１）
ａｒ．ｃｃｖ＝ｍｏｖ  ０
ｒ１＝ｃｍｐｘｃｈ２．ａｃｑ〔ｒ３〕，ｒ２
【００５４】
この命令列において、レジスタｒ１は旧ロック所有者を表し、レジスタｒ２は現在のスレッドを表し、レジスタｒ３は現在の小型ロック所有者フィールド３６２に対応するアドレスを保持するとしてもよい。最初の命令（ａｒ．ｃｃｖ＝ｍｏｖ  ０）によって、ａｒ．ｃｃｖレジスタを０（つまりＮＵＬＬ値）に設定する。２番目の命令（ｒ１＝ｃｍｐｘｃｈｇ２．ａｃｑ〔ｒ３〕，ｒ２）は不可分動作であって、以下の動作を行うために用いられるとしてもよい。まず、（１）旧ロック所有者を、現在の小型ロック所有者フィールド３６２と等しくなるように設定（つまり、ｒ１＝〔ｒ３〕）、（２）現在の小型ロック所有者フィールド３６２がＮＵＬＬ値であるかどうか確認（つまり、〔ｒ３〕がａｒ．ｃｃｖと等しいかどうか確認）、（３）現在の小型ロック所有者フィールド３６２がＮＵＬＬ値である場合（つまり、〔ｒ３〕がａｒ．ｃｃｖと等しい場合）、小型ロック所有者ＩＤ３５８を現在のスレッドを表す値に設定（つまり、〔ｒ３〕＝ｒ２）、そして（４）現在の小型ロック所有者フィールド３６２がＮＵＬＬ値でない場合（つまり、〔ｒ３〕がａｒ．ｃｃｖと等しくない場合）、小型ロック所有者ＩＤ３５８をそのままにする（つまり、〔ｒ３〕をそのままにする）。
【００５５】
図６に戻り、小型ロック所有者フィールド３６２がＮＵＬＬ値でない（ブロック６１２）、もしくは小型ロック所有者ＩＤ３５８が現在のスレッドに設定される（ブロック６１６）と判定されると、プロセス６００は続いて、該オブジェクトの旧ロック所有者がＮＵＬＬ値かどうか（現在のスレッドがブロック６１６で小型ロックを取得した場合と対応する）判定する（ブロック６２０）。旧ロック所有者がＮＵＬＬ値である場合（ブロック６２０）、制御はブロック６２４に進む。しかし、旧ロック所有者がＮＵＬＬ値でないと判定される場合（ブロック６２０）、プロセス６００は続いて、旧ロック所有者が現在のスレッドかどうか（現在のスレッドが既に該オブジェクトの小型ロックを以前に取得していた場合と対応する）判定する（ブロック６２６）。旧ロック所有者が現在のスレッドである場合（ブロック６２６）、制御はブロック６２４に進む。しかし、旧ロック所有者が現在のスレッドでないと判定され（ブロック６２６）、従って別のスレッドが既にロックを所有しているか、大型ロックが該オブジェクトと対応付けられている場合、プロセス６００は大型ロックフラグをＴＲＵＥに設定して、大型ロックが現在該オブジェクトと対応付けられている、もしくは今後対応付けられることを指し示す（ブロック６２８）。続いてプロセス６００は公知のロック大型化／競合処理手順を呼び出して、現在のロック所有者（存在する場合）が該ロックを解除した後で、現在のスレッドに該オブジェクトの大型ロックを取得させる（ブロック６３０）。プロセス６００は、現在のロック所有者（存在する場合）が該オブジェクトのロックを解除／解放するまで、現在のスレッドを実行ループでスピンさせるか現在のスレッドに実行を中止させるとしてもよい。該オブジェクトのロックが利用可能になると、プロセス６００は現在のスレッドのために大型ロックを取得するとしてもよい。ブロック６３０のロック大型化／競合処理手順が完了した後では旧ロック所有者が存在しないので、プロセス６００はさらに、旧ロック所有者をＮＵＬＬ値にリセットするとしてもよい（ブロック６３２）。続いて制御はブロック６２４に進む。
【００５６】
ブロック６２４において、現在のスレッドは、ロックされたオブジェクトに対応するクリティカルな部分のコードを実行する。クリティカルな部分のコードの実行が完了した後、プロセス６００は大型ロックが該オブジェクトに対応付けられているかどうか（例えば、大型ロックフラグがＴＲＵＥかどうか）判定する（ブロック６３６）。小型ロックが該オブジェクトと対応付けられている場合（つまり大型ロックフラグがＦＡＬＳＥの場合）、プロセス６００は該ロックの小型ロック所有者ＩＤ３５８をリセットして旧ロック所有者とする（ブロック６４０）。小型ロック所有者ＩＤ３５８をリセットして旧ロック所有者と等しくすることによって、プロセス６００は、旧ロック所有者がＮＵＬＬ値である場合はロックを解除し、旧ロック所有者が現在のスレッドである場合は現在のスレッドのためにロックを維持する。一方、該オブジェクトに大型ロックが対応付けられている場合（つまり大型ロックフラグがＴＲＵＥの場合）、プロセス６００は公知の大型ロック解除処理手順を呼び出して、該オブジェクトの大型ロックを解除する（ブロック６４４）。ブロック６４０もしくはブロック６４４の処理が完了すると、プロセス６００は終了する。
【００５７】
再帰的な楽観的平衡ロック同期（および以下で説明する不平衡なロック取得処理および不平衡なロック解除処理）をサポートすべく、ロックマネージャ２００および／またはロックマネージャプロセス５００は１以上の同期マップを利用し、楽観的平衡ロック同期を呼び出すメソッド（例えばＪＡＶＡメソッド）のインスタンスそれぞれについて、すべてのアクティブな楽観的平衡取得処理の状態を格納／記録する。アクティブな楽観的平衡取得処理の状態を表す、同期マップエントリの例を挙げると、ロックアドレス、旧ロック所有者値、および大型ロックフラグを含む。同期マップのエントリはそれぞれ、楽観的平衡ロック同期を呼び出したメソッドのインスタンスに対応するコールフレーム内のコールスタックに格納されるとしてもよい（この結果、該メソッドに対するネストされたコールによって発生する再帰的なロック取得をサポートする）。以下でより詳細に説明するが、不平衡ロック取得処理および不平衡ロック解除処理は、コールスタックでアクティブな楽観的平衡取得処理の数を特定し必要に応じてその処理を変更するべく、同期マップを変更するとしてもよい。
【００５８】
図７に、図５のブロック５１２における処理を行うために用いられる、および／または図２の不平衡ロック取得部２２４を実施するための、不平衡ロック取得プロセス７００を例示する。不平衡ロック取得プロセス７００は、ロックの旧ロック所有者に対応する変数／レジスタを、該オブジェクトのロックに対応付けられた現在の小型ロック所有者フィールド（例えば、図３Ｂの小型ロック所有者フィールド３６２）と等しくなるように設定することから始まる（ブロック７０８）。続いてプロセス７００は、ロックの対象であるオブジェクトのロックをすでに所有しているスレッドがあるかどうか、および／または該オブジェクトに大型ロックが対応付けられているかどうか（つまり、小型ロック所有者フィールド３６２がＮＵＬＬ値に設定されているかどうか）判定する（ブロック７１２）。すでにロックを所有しているスレッドがなく、該オブジェクトに小型ロックが対応付けられており（つまり、小型ロック所有者フィールド３６２がＮＵＬＬ値に設定されている）（ブロック７１２）、従って該オブジェクトのロックが解除されている場合、プロセス７００は、該ロックの小型ロック所有者ＩＤ（例えば小型ロック所有者ＩＤ３５８）を該スレッドを表す値（例えば、一意的なスレッド識別子の値）に設定することによって、該スレッドのために該オブジェクトの小型ロックを取得する（ブロック７１６）。しかし、ロックを既に所有しているスレッドがあり、および／または該オブジェクトに大型ロックが対応付けられていると判定される場合（つまり、小型ロック所有者フィールド３６２がＮＵＬＬ値に設定されていない場合）（ブロック７１２）、プロセス７００は小型ロック所有者ＩＤ３５８をそのままとする。
【００５９】
先述したように、第１スレッドがすでにロック所有者になるためのプロセスを実行している間に第２スレッドがロックの取得を試みないように、ブロック７０８、７１２および７１６は通常１回の不可分動作で行われる（例えば、インテル(r)プロセッサに分類されるプロセッサで実行されるｃｍｐｘｃｈｇ命令など）。不可分動作で実行することによって、スレッド（および／またはマルチプロセッサシステムのプロセッサ）は該不可分動作の実行中には共有メモリに対して排他的アクセスを得ることができる。このため、不可分動作の実行中は、該不可分動作によってアクセスされた格納場所を、ほかのスレッドが変更することはできない。
【００６０】
図７に戻って、小型ロック所有者フィールド３６２がＮＵＬＬ値でない（ブロック７１２）、もしくは小型ロック所有者ＩＤ３５８が現在のスレッドに設定される（ブロック７１６）と判定されると、プロセス７００は、該オブジェクトの旧ロック所有者がＮＵＬＬ値かどうか（現在のスレッドがブロック７１６で小型ロックを取得した場合と対応する）判定する（ブロック７２０）。旧ロック所有者がＮＵＬＬ値である場合（ブロック７２０）、プロセス７００は、該オブジェクトのロックを大型化する準備として、ロック再帰カウンタを０に設定する（ブロック７２４）。ロック再帰カウンタが０に設定されると、該オブジェクトに対する初めてのロック取得が行われていることが指し示される。プロセス７００は続いて、ロック再帰カウンタの値より１大きい値に等しい、該オブジェクトのロックの再帰的ロック取得の数に基づき、公知のロック大型化処理手順を呼び出す（ブロック７２８）。この場合ロック再帰カウンタは０に設定されているので、ロック大型化処理手順は１回のロック取得に基づいて行われる。プロセス７００はここで終了する。
【００６１】
一方、旧ロック所有者がＮＵＬＬ値でないと判定された場合（ブロック７２０）、プロセス７００は続いて、旧ロック所有者が現在のスレッドかどうか（現在のスレッドが既に該オブジェクトの小型ロックを以前に取得していた場合と対応する）判定する（ブロック７３２）。旧ロック所有者が現在のスレッドである場合（ブロック７３２）、該オブジェクトのロックを大型化する準備として、プロセス７００は、ロックされる対象であるオブジェクトに対応する同期マップに格納された、アクティブな楽観的平衡取得処理の状態を固定するための処理手順を呼び出す（ブロック７３６）。このアクティブ取得固定処理手順では、同期マップを処理して、該オブジェクトに対応する再帰的な楽観的平衡ロック取得の数を決定し、対応する大型ロックフラグをＴＲＵＥに変更して大型ロックが該オブジェクトと対応付けられる（不平衡ロック取得がプロセス７００によって行われているため）ことを指し示す。ブロック７３６で行われる動作を実行するための処理手順は図９に例示するとともに、より詳細に後述する。
【００６２】
アクティブ取得固定処理が完了すると（ブロック７３６）、プロセス７００は、該オブジェクトのロックに対応するロック再帰カウンタを、アクティブ取得固定処理が特定したアクティブな楽観的平衡ロック取得の数と等しくなるように設定する（ブロック７４０）。プロセス７００は続いて、ロック再帰カウンタの値より１大きい値に等しい、オブジェクトのロックの再帰的ロック取得の数に基づき、公知のロック大型化処理手順を呼び出す（ブロック７２８）。この場合、ロック大型化処理手順は、アクティブな楽観的平衡ロック取得の数に１回の不平衡なロック取得を加えた数（ブロック７４０で特定されたロック再帰カウンタの値より１大きい値に対応する）に基づいて行われる。プロセス７００はここで終了する。
【００６３】
一方、旧ロック所有者が現在のスレッドでなく（ブロック７３２）、従って別のスレッドが既に該オブジェクトのロックを所有している、または大型ロックが既に該オブジェクトと対応付けられていると判定された場合、プロセス７００は、現在のロック所有者（存在する場合）がロックを解除した後で、公知のロック大型化／競合処理手順を呼び出し、現在のスレッドに該オブジェクトの大型ロックを取得させる（ブロック７４４）。プロセス７００は、現在のロック所有者（存在する場合）が該オブジェクトのロックを解除／解放するまで、現在のスレッドを実行ループでスピンさせるか現在のスレッドに実行を中止させるとしてもよい。該オブジェクトのロックが利用可能になると、プロセス７００は現在のスレッドのために大型ロックを取得するとしてもよい。さらに、プロセス７００は、ブロック７４４でのロック競合処理手順が完了した後では旧ロック所有者が存在しなくなるので、旧ロック所有者をリセットしてＮＵＬＬ値にするとしてもよい（ブロック７４８）。プロセス７００はこれで終了する。
【００６４】
図８に、図５のブロック５１６における処理を行うために用いられる、および／または図２の不平衡ロック解除部２２８を実施するための、不平衡ロック解除プロセス８００を例示する。不平衡ロック解除プロセス８００は、該ロックの旧ロック所有者に対応する変数／レジスタを該オブジェクトのロックに対応付けられた現在の小型ロック所有者フィールド（例えば図３Ｂに示した小型ロック所有者フィールド３６２）と等しくなるように設定することから始まる（ブロック８０４）。プロセス８００は続いて、旧ロック所有者が、オブジェクトのロックを解除しようと試みている現在のスレッドに対応するかどうか判定する（ブロック８０８）。旧ロック所有者が現在のスレッドに対応する場合（ブロック８０８）、従って現在のスレッドが該オブジェクトの小型ロックを所有している場合、該オブジェクトのロックを大型化する準備として、プロセス８００は、ロックされる対象であるオブジェクトに対応する同期マップに格納された、アクティブな楽観的平衡取得処理の状態を固定するための処理手順を呼び出す（ブロック８１２）。このアクティブ取得固定処理では、同期マップを処理して、該オブジェクトに対応する再帰的な楽観的平衡ロック取得の数を決定し、対応する大型ロックフラグをＴＲＵＥに変更して、大型ロックが該オブジェクトと対応付けられる（不平衡ロック解除がプロセス８００によって行われるため）ことを指し示す。ブロック８１２で行われる動作を実行するための処理手順は図９に例示するとともに、より詳細に後述する。
【００６５】
アクティブ取得固定処理が完了すると（ブロック８１２）、プロセス８００は、該オブジェクトのロックに対応するロック再帰カウンタを、同期マップに格納される、アクティブ取得固定処理が特定したアクティブな楽観的平衡ロック取得の数と等しくなるように設定する（ブロック８１６）。プロセス８００は続いて、ブロック８１６で決定されたロック再帰カウンタの値に等しい、オブジェクトのロックの再帰的ロック取得の数に基づき、公知のロック大型化処理手順を呼び出す（ブロック８２０）。ロック大型化処理手順が完了すると（ブロック８２０）、プロセス８００は公知の大型ロック解除処理手順を呼び出して、該オブジェクトの大型ロックを解除する（ブロック８２２）。プロセス８００はここで終了する。
【００６６】
一方、旧ロック所有者がロックを解除しようと試みている現在のスレッドに対応しない場合（ブロック８０８）、プロセス８００は続いて該オブジェクトに小型ロックが対応付けられているかどうか判定する（ブロック８２４）。プロセス８００は例えば、該オブジェクトの小型ロックに対応付けられたロック形状ビット（例えば図３Ｂに示すロック形状ビット３５４）に基づいて、この判定を行うとしてもよい。該オブジェクトに小型ロックが対応付けられており（ブロック８２４）、従って該小型ロックを所有していないスレッドがオブジェクトのロックを解除しようと試みていると判定された場合（ブロック８０８で行われた判定に基づくものである）、プロセス８００は公知の例外ハンドリング技術を用いて、現在のスレッドは所有していないロックを不適切に解除しようと試みたことを指し示すべく例外をスローする（ブロック８２８）。しかし、該オブジェクトに小型ロックが対応付けられておらず（ブロック８２４）、従って大型ロックが該オブジェクトに対応付けられている場合、プロセス８００は続いて、該オブジェクトの大型ロックを解除するべく公知の大型ロック解除処理手順を呼び出す（ブロック８２２）。ブロック８２２またはブロック８２８での処理が完了すると、プロセス８００は終了するとしてもよい。
【００６７】
同期マップ（例えば、図６の楽観的平衡ロック同期処理６００または図２の楽観的平衡ロック同期部２２０によって維持される同期マップ）に格納された、アクティブな楽観的平衡取得の状態を変更するためのプロセス９００を図９に示す。プロセス９００は、オブジェクトに対応付けられたロックを大型化するための準備として、一連のアクティブな楽観的平衡ロック取得に対応付けられたロック形状フラグを固定するために用いられるとしてもよい。プロセス９００は例えば、図７に示した不平衡ロック取得プロセス７００および／または図８に示した不平衡ロック解除プロセス８００において利用されるとしてもよい。具体的に言うと、プロセス７００および／またはプロセス８００は、図７のブロック７３６および／または図８のブロック８１２で実行される処理を実現するべく、プロセス９００を呼び出すとしてもよい。プロセス９００はまた、図２に示した平衡解除記録部／変更部２３６を実現するために用いられるとしてもよい。
【００６８】
図９に戻って、プロセス９００は、例えばオブジェクトに対応付けられたロックワードのアドレスを取得することによって、処理されているオブジェクトに対応するロックを取得することから始まる（ブロック９０４）。プロセス９００は続いて、アクティブな楽観的平衡取得の数に対応するカウンタを初期化して０とする（ブロック９０８）。この初期化が完了すると、プロセス９００は、ブロック９０４で選択したオブジェクトのロックに対応するアクティブな楽観的平衡取得が存在するかどうか決定すべく、コールスタック内の各コールフレームに対してイテレートを開始する。
【００６９】
プロセス９００は、コールスタックの次のコールフレームを取得することによって、コールスタック内の各コールフレームに対するイテレートを開始する（ブロック９１２）。プロセス９００は続いて、処理されているコールフレーム内に格納された次のロックされたオブジェクトの同期マップエントリを取得する（ブロック９１６）。プロセス９００は続いて、処理されているオブジェクトのロックに該同期マップのエントリが対応するかどうか判定する（ブロック９２０）。処理されているオブジェクトのロックに該同期マップエントリが対応する場合（ブロック９２０）、プロセス９００は、該オブジェクトのロックのアクティブな楽観的平衡取得の数に対応するカウンタを増加させる（ブロック９２４）。プロセス９００はまた、該同期マップエントリ内の大型ロックフラグをＴＲＵＥに設定して、該オブジェクトに大型ロックが対応付けられることを指し示す（ブロック９２８）。
【００７０】
ブロック９２８の処理が完了するか、処理されているオブジェクトのロックに該同期マップエントリが対応しない場合（ブロック９２０）、プロセス９００は、処理されている同期マップエントリが、処理されているコールフレーム中で最後の同期マップエントリかどうか判定する（ブロック９３２）。該同期マップエントリが最後の同期マップエントリでない場合（ブロック９３２）、制御はブロック９１６に戻る。ブロック９１６ではプロセス９００が、処理されているコールフレーム内に格納された、次のロックされたオブジェクトのための同期マップエントリを取得する。しかし、該同期マップエントリが最後の同期マップエントリである場合（ブロック９３２）、プロセス９００は、処理されているコールフレームがコールスタック内で最後のコールフレームかどうか（従って、同期マップの終わりに到達したかどうか）判定する（ブロック９３６）。該コールフレームが最後のコールフレームでない場合（ブロック９３６）、制御はブロック９１２に戻る。ブロック９１２でプロセス９００は、処理すべき次のコールフレームを取得する。しかし、処理されているコールフレームがコールスタック内で最後のコールフレームである場合（ブロック９３６）、プロセス９００は、処理されているロックされたオブジェクトに対応するアクティブな楽観的平衡取得の数を戻す（ブロック９４４）。ここでプロセス９００は終了する。
【００７１】
本明細書で説明した方法、装置および製品をより詳しく説明するべく、図１０Ａから図１０Ｃに、図２のロックマネージャ２００の動作および／または図５、図６、図７、図８および図９に示したプロセス５００、６００、７００、８００および９００での動作を例示する。図１０Ａから図１０Ｃに例示した動作は、２つのオブジェクトのロックに対して１つのスレッドが行う一連のロック取得・解除に対応する。このロック動作は、メソッド実行のためにオブジェクトをロックする必要がある、呼び出されたさまざまなメソッドＡ〜メソッドＣに基づいて行われる。図１０Ａはプログラムシーケンスを例示する。図１０Ｂは、該プログラムシーケンスにおける２点のための同期マップのエントリを例示する。図１０Ｃは、図１０Ａに示した不平衡なロックの解除が行われる前後の、各同期マップエントリに対応付けられた大型ロックフラグの状態を示す。
【００７２】
図１０Ａに例示したプログラムシーケンスは、第１オブジェクト（ｏｂｊ１）のロックの第１の楽観的平衡取得（命令Ａ１）を行うメソッドＡから始まる。図６に示したプロセス６００によると、この第１の楽観的平衡取得に対応付けられているのは、第１大型ロックフラグ（ｉｎｆｌａｔｅｄ１）および第１旧ロック所有者（ｔｈｒｅａｄＩＤ１）を含む第１同期マップエントリである。メソッドＡは続いて、同期マップキャッシュ領域に格納される、図１０Ｂに示した対応する同期マップエントリＣ１になる、メソッドＢをコールする（命令Ｃ１）。同期マップエントリＣ１は、ロックされたオブジェクトｏｂｊ１を示すスタック位置またはレジスタ、ならびに大型ロックフラグｉｎｆｌａｔｅｄ１を示すスタック位置またはレジスタを含む。
【００７３】
続いてメソッドＢは、第１オブジェクトｏｂｊ１のロックの第２の楽観的平衡取得（命令Ａ２）および第２オブジェクトｏｂｊ２のロックの第３の楽観的平衡取得（命令Ａ３）を行う。プロセス６００によると、第２の楽観的平衡取得に対応付けられているのは、第２大型ロックフラグ（ｉｎｆｌａｔｅｄ２）および第２旧ロック所有者（ｔｈｒｅａｄＩＤ２）を含む第２同期マップエントリである。同様に、第３の楽観的平衡取得に対応付けられているのは、第３大型ロックフラグ（ｉｎｆｌａｔｅｄ３）および第３旧ロック所有者（ｔｈｒｅａｄＩＤ３）を含む第３同期マップエントリである。メソッドＢは続いて、同期マップキャッシュ領域に格納される、図１０Ｂに示した対応する同期マップエントリＣ２になる、メソッドＣをコールする（命令Ｃ２）。同期マップエントリＣ２は、第１オブジェクトｏｂｊ１に対応付けられた第１データセット、ならびに第２オブジェクトｏｂｊ２に対応付けられた第２データセットを含む。第１データセットはロックされたオブジェクトｏｂｊ１を示すスタック位置またはレジスタ、ならびに大型ロックフラグｉｎｆｌａｔｅｄ２を示すスタック位置またはレジスタを含む。第２データセットはロックされたオブジェクトｏｂｊ２を示すスタック位置またはレジスタ、ならびに大型ロックフラグｉｎｆｌａｔｅｄ３を示すスタック位置またはレジスタを含む。
【００７４】
続いてメソッドＣは、第１オブジェクトｏｂｊ１のロックに対して不平衡ロック解除を行う。図８に示したプロセス８００によると、不平衡解除は、オブジェクトｏｂｊ１に対応付けられたロックを大型化するための準備として、第１オブジェクトｏｂｊ１に対応するアクティブな楽観的平衡取得を変更するアクティブ取得固定処理を呼び出す。図１０Ｃは、不平衡ロック解除（命令Ｒ３）が行われる前後の、同期マップに格納された大型ロックフラグの状態を示す。考えられるように、不平衡ロック解除が行われる前は、第１オブジェクトｏｂｊ１に対応付けられた大型ロックフラグ（ｉｎｆｌａｔｅｄ１およびｉｎｆｌａｔｅｄ２）ならびに第２オブジェクトｏｂｊ２に対応付けられた大型ロックフラグ（ｉｎｆｌａｔｅｄ３）はすべてＦＡＬＳＥである。つまり、オブジェクトｏｂｊ１およびオブジェクトｏｂｊ２の両方に対応付けられているのは小型ロックであることが示されている。不平衡ロック解除が行われた後は、第１オブジェクトｏｂｊ１に対応付けられた大型ロックフラグ（ｉｎｆｌａｔｅｄ１およびｉｎｆｌａｔｅｄ２）はＴＲＵＥに設定され、不平衡解除の結果第１オブジェクトｏｂｊ１に大型ロックが対応付けられることが指し示される。続いてプログラムは、メソッドＢが第２オブジェクトｏｂｊ２および第１オブジェクトｏｂｊ１に対して楽観的平衡解除を行い（命令Ｒ２および命令Ｒ３）、メソッドＡが楽観的平衡解除を第１オブジェクトｏｂｊ１に行うことによって終了する。
【００７５】
図１１は、本明細書で開示した装置および方法を実行することができるコンピュータまたはプロセッサシステム１１００を例示するブロック図である。コンピュータ１１００は例えば、サーバ、パソコン、携帯情報端末（ＰＤＡ）、インターネット関連機器もしくはその他の演算デバイスであるとしてもよい。
【００７６】
システム１１００はプロセッサ１１１２を備える。プロセッサ１１１２は例えば、Ｐｅｎｔｉｕｍ(r)ファミリ、Ｉｔａｎｉｕｍ(r)ファミリ、またはＸＳｃａｌｅ(r)ファミリから選ばれる１以上のインテル(r)マイクロプロセッサによって実施されるとしてもよい。また、これ以外のファミリのプロセッサを利用するとしてもよい。プロセッサ１１１２は１以上のマイクロプロセッサを有しており、図１に示した利用環境１００、図２に示したロックマネージャ２００、および／または図５、図６、図７、図８および図９に示したプロセス５００、６００、７００、８００および９００を実現するために用いられるとしてもよい。
【００７７】
プロセッサ１１１２は、バス１１１８を介して、揮発性メモリ１１１４および不揮発性メモリ１１１６を含むメインメモリと通信可能である。揮発性メモリ１１１４は、ＳＲＡＭ（Ｓｔａｔｉｃ  Ｒａｎｄｏｍ  Ａｃｃｅｓｓ  Ｍｅｍｏｒｙ）、ＳＤＲＡＭ（Ｓｙｎｃｈｒｏｎｏｕｓ  Ｄｙｎａｍｉｃ  ＲＡＭ）、ＤＲＡＭ（Ｄｙｎａｍｉｃ  ＲＡＭ）、ＲＤＲＡＭ（ＲＡＭＢＵＳ  ＤＲＡＭ）および／またはこれ以外のＲＡＭデバイスによって実現されるとしてもよい。不揮発性メモリ１１１６は、フラッシュメモリおよび／またはこれ以外の所望のメモリデバイスによって実現されるとしてもよい。メインメモリ１１１４および１１１６へのアクセスは通常、従来の方法に従ってメモリコントローラ（不図示）が制御する。
【００７８】
コンピュータ１１００はさらに、従来のインターフェース回路１１２０も備える。インターフェース回路１１２０は、どの公知のインターフェース規格によって実現されるとしてもよい。例を挙げると、イーサネットインターフェース、ＵＳＢ（ユニバーサル・シリアル・バス）および／または第３世代入出力（３ＧＩＯ）インターフェースなどがある。
【００７９】
１以上の入力デバイス１１２２がインターフェース回路１１２０に接続されている。入力デバイス１１２２によって、ユーザはデータおよびコマンドをプロセッサ１１１２に入力することができるようになる。入力デバイスは、例えばキーボード、マウス、タッチスクリーン、トラックパッド、トラックボール、ｉｓｏｐｏｉｎｔおよび／または音声認識システムによって実現するとしてもよい。
【００８０】
１以上の出力デバイス１１２４もまたインターフェース回路１１２０に接続されている。出力デバイス１１２４は例えばディスプレイデバイス（例えば液晶ディスプレイ、陰極線管（ＣＲＴ）ディスプレイ）、プリンタおよび／またはスピーカによって実現されるとしてもよい。このため、インターフェース回路１１２０は通常、グラフィクスドライバカードを有する。
【００８１】
インターフェース回路１１２０はまた、ネットワーク１１２６（例えば、イーサネット接続、デジタル加入者線（ＤＳＬ）、電話線、同軸ケーブル、携帯電話システムなど）を介した外部コンピュータとのデータのやり取りを円滑化するべく、通信デバイス（例えばモデムまたはネットワークインターフェースカード）を含む。
【００８２】
コンピュータ１１００はさらに、ソフトウェアおよびデータを格納するべく、１以上の大容量記憶デバイス１１２８を備える。この大容量記憶デバイス１１２８の例には、フロッピーディスクドライブ、ハードドライブディスク、コンパクトディスクドライブおよびＤＶＤドライブなどがある。大容量記憶デバイス１１２８および／または揮発性メモリ１１１４は、例えば図６、図７、図８および図９に示したプロセス６００、７００、８００および９００によって維持・変更される同期マップを格納するために用いられるとしてもよい。
【００８３】
本明細書に開示した方法および／または装置は、図１１に示したデバイスのようなシステムで実行する代わりに、プロセッサおよび／またはＡＳＩＣ（特定用途向け集積回路）といった構造に埋め込まれるとしてもよい。
【００８４】
上記の説明から、本明細書で開示した方法および装置は、さまざまなプログラムを実行する上で性能の最適化を図るべく、スタティックコンパイラ、マネージド・ランタイム環境のジャスト・イン・タイム（ＪＩＴ）コンパイラ、および／または直接マイクロプロセッサのハードウェアによって実行できることは当業者には明らかである。
【００８５】
本明細書では具体的な方法、装置および製品を例に挙げたが、本特許の範囲は説明した方法、装置および製品に限定されない。本特許は、本願請求項を文字通り解釈した場合および均等論に基づいて解釈した場合の範囲に含まれる方法、装置および製品をすべて網羅する。
【図１】
2008501199.tif 000003
【図２】
2008501199.tif 000004
【図３Ａ】
2008501199.tif 000005
【図３Ｂ】
2008501199.tif 000006
【図４Ａ】
2008501199.tif 000007
【図４Ｂ】
2008501199.tif 000008
【図５】
2008501199.tif 000009
【図６】
2008501199.tif 000010
【図７】
2008501199.tif 000011
【図８】
2008501199.tif 000012
【図９】
2008501199.tif 000013
【図１０Ａ】
2008501199.tif 000014
【図１０Ｂ】
2008501199.tif 000015
【図１０Ｃ】
2008501199.tif 000016
【図１１】
2008501199.tif 000017
【国際調査報告】
2008501199.tif 000018
2008501199.tif 000019
2008501199.tif 000020