(57)【特許請求の範囲】
【請求項１】
複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、前記メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータのメモリ・アクセス順序付け方法において、
メモリ・アクセスについて前後の関係で順序付けを必要とする、プログラム上で前後の記述順となっている、ストア命令及びロード命令は、そのアドレス範囲が重複部分をもつようにかつストア及びロードの必要なデータのアドレス範囲をそれぞれ含むように設定してプログラム上に配置するステップと、
これらストア命令及びロード命令の対を各ＣＰＵにおいて検出させる検出ステップと、
検出された対に係るプログラムを実行するＣＰＵに、その投機実行中止機構を、検出した対に対して作動させる作動ステップと、
を含むことを特徴とするメモリ・アクセス順序付け方法。
【請求項２】
各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
前記投機実行中止機構は、前記対の両命令に係る、前記メモリ上の、アドレス範囲が同一である場合には、前記対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとして前記ストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、前記対の両命令に係る、前記メモリ上の、アドレス範囲が部分的にのみ重複している場合には、前記対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、前記対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
前記作動ステップでは、検出された対に係るプログラムを実行するＣＰＵに、該対に対して前記投機実行中止機構のＳＦＡ機構を作動させる、
ことを特徴とする請求項１記載のメモリ・アクセス順序付け方法。
【請求項３】
前記対において、ストア命令のアドレス範囲は本来的にストアの必要なデータのみをストアするように設定されているのに対し、ロード命令のアドレス範囲は、本来的にロードの必要なデータと共にロードの不要なデータもロードするように、設定され、該ロード命令に基づいてデータのロードを実行するロード命令実行ステップと、
本来的にロードの必要なデータは、ロード命令によりロードしたデータから抽出する抽出ステップと、
を含むことを特徴とする請求項１記載のメモリ・アクセス順序付け方法。
【請求項４】
前記プログラムは第１及び第２の処理に係る第１及び第２のプログラム部分を含み、第１及び第２の処理は、ストア処理部分、及び相手の処理でストアしたかもしれないデータを前記ストア処理部分の実行後に観測する観測処理部分、及び該観測処理部分の観測結果に基づいて対応の処理へ分岐する分岐処理部分を含み、
前記対におけるストア命令及びロード命令は、第１及び第２の処理におけるストア処理部分及び観測処理部分に含まれていることを特徴とする請求項１記載のメモリ・アクセス順序付け方法。
【請求項５】
第１及び第２の処理は、それぞれオブジェクト管理方法のオブジェクトのロック解除に係る処理及びオブジェクト獲得に係る処理であることを特徴とする請求項４記載のメモリ・アクセス順序付け方法。
【請求項６】
複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、前記メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにおけるオブジェクトへのロックを管理するロック管理方法であって、
前記ロック管理方法では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
前記第１の種類のロックは、オブジェクトに対してロックを実施するスレッドの識別子を前記フィールドに記憶することによりオブジェクトに対するロックを行うものであり、前記第２の種類のロックは、前記第１の種類のロックよりも処理が複雑なロック方式のものであり、
さらに、前記ロック管理方法は、第１のスレッドが保持している或るオブジェクトへのロックを第２のスレッドが獲得するオブジェクト獲得方法と、前記第１のスレッドが前記或るオブジェクトへのロックを解除するロック解除方法とを含み、
前記オブジェクト獲得方法は、
（ａ１）前記或るオブジェクトの前記ロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、
（ａ２）前記第１の種類のロックであることを示しているときには、競合ビットを立てるステップと、
（ａ３）前記（ａ２）において競合ビットを立てた後、前記第１の種類のロックを獲得することが可能な場合には、前記競合ビットをクリアし、前記第２の種類のロックに係る識別子及び該ロックの種類を示すビットを前記フィールドに記憶し、前記第２の種類のロックを獲得するが、前記第１の種類のロックを獲得することができない場合には、待機状態に移行するステップと、
を含み、
前記ロック解除方法は、
（ｂ１）前記ロックの種類を示すビットが前記第１の種類のロックであることを示しているか判断するステップと、
（ｂ２）前記或るオブジェクトのロックを保持しているスレッドが存在しないことを前記記憶領域に記憶するステップと、
（ｂ３）前記ロックの種類を示すビットが前記第１の種類のロックであることを示しているときには、前記競合ビットが立っているか判断するステップと、
（ｂ４）前記競合ビットが立っていないと判断されたときには終了するステップと、
（ｂ５）前記（ｂ２）における記憶に対応するストア命令Ｓと前記（ｂ３）におけるビットの読み出しに対応するロード命令Ｌとについて、前記投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係るプログラムにおいて、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲を設定するステップと、
を含み、
該設定に基づいて前記（ｂ２）及び（ｂ３）のステップを実行する、
ことを特徴とするロック管理方法。
【請求項７】
各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
前記投機実行中止機構は、前記対の両命令に係る、前記メモリ上の、アドレス範囲が同一である場合には、前記対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとして前記ストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、
前記対の両命令に係る、前記メモリ上の、アドレス範囲が部分的にのみ重複している場合には、前記対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、前記対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
前記ストア命令Ｓ及び前記ロード命令Ｌに係る、メモリ上の、アドレス範囲は、ＳＦＡ機構を作動させるように、設定され、
該設定に基づいて前記（ｂ２）及び（ｂ３）のステップを実行する、
ことを特徴とする請求項６記載のロック管理方法。
【請求項８】
前記（ｂ２）における記憶に対応するストア命令Ｓは、前記或るオブジェクトのロックを保持しているスレッドが存在しないことが記憶される前記記憶領域に係るアドレス範囲Ａ１をアドレス範囲として設定され、
前記（ｂ３）におけるビットの読み出しに対応するロード命令Ｌは、該ビットに係るアドレス範囲を全部含むとともに、前記アドレス範囲Ａ１を少なくとも部分的に含むアドレス範囲Ａ２をアドレス範囲として設定され、
該設定に基づいて前記（ｂ２）及び（ｂ３）のステップを実行する、
ことを特徴とする請求項６記載のロック管理方法。
【請求項９】
前記ロック解除方法は、
（ｂ５）前記競合ビットが立っていると判断されたときには、オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の制御状態に前記第１のスレッドが移行するステップと、
（ｂ６）待機しているスレッドへの通知操作を実行するステップと、
（ｂ７）前記第１のスレッドが前記制御状態から脱出するステップと、
をさらに含むことを特徴とする請求項６記載のロック管理方法。
【請求項１０】
複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、前記メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにおけるオブジェクトへのロックを管理するロック管理方法であって、
前記ロック管理方法では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又はオブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
前記第１の種類のロックは、オブジェクトに対してロックを実施するスレッドの識別子を前記フィールドに記憶することによりオブジェクトに対するロックを行うものであり、前記第２の種類のロックは、前記第１の種類のロックよりも処理が複雑なロック方式のものであり、
（ｃ１）オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の制御状態に第１のスレッドが移行するステップと、
（ｃ２）或るオブジェクトの前記ロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、
（ｃ３）前記或るオブジェクトの前記ロックの種類を示すビットが第１の種類のロックであることを示しているとき、競合ビットをセットするステップと、
（ｃ４）前記（ｃ３）のステップの後、前記或るオブジェクトに対応して設けられた記憶領域の内容に基づいて前記第１の種類のロックを第１のスレッドが獲得できるか判断するステップと、
（ｃ５）前記第１の種類のロックを第１のスレッドが獲得できるときには、前記或るオブジェクトに対応して設けられた記憶領域に第２の種類のロックを示すビット及び前記第２の種類のロックに係る識別子を記憶するステップと、
（ｃ６）前記第１のスレッドが前記或るオブジェクトに対して必要な処理を終了した後に前記制御状態を脱出するステップと、
（ｃ７）前記（ｃ３）における競合ビットのセットに対応するストア命令Ｓと前記（ｃ４）における前記記憶領域の内容の読み出しに対応するロード命令Ｌとについて、前記投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係るプログラムにおいて、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲を設定するステップと、
を含み、
該設定に基づいて前記（ｃ３）及び（ｃ４）のステップを実行する、
ことを特徴とするロック管理方法。
【請求項１１】
各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
前記投機実行中止機構は、前記対の両命令に係る、前記メモリ上の、アドレス範囲が同一である場合には、前記対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとして前記ストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、前記対の両命令に係る、前記メモリ上の、アドレス範囲が部分的にのみ重複している場合には、前記対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、前記対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
前記ストア命令Ｓ及び前記ロード命令Ｌに係る、メモリ上の、アドレス範囲は、ＳＦＡ機構を作動させるように、設定され、
該設定に基づいて前記（ｃ３）及び（ｃ４）のステップを実行する、
ことを特徴とする請求項１０記載のロック管理方法。
【請求項１２】
前記（ｃ３）における競合ビットのセットに対応するストア命令Ｓは、競合ビットに係るアドレス範囲Ａ１をアドレス範囲として設定され、
前記（ｃ４）における前記記憶領域の内容の読み出しに対応するロード命令Ｌは、前記記憶領域のアドレス範囲を全部含むとともに、前記アドレス範囲Ａ１を少なくとも部分的に含むアドレス範囲Ａ２をアドレス範囲として設定され、該設定に基づいて前記（ｃ３）及び（ｃ４）のステップを実行する、
ことを特徴とする請求項１０記載のロック管理方法。
【請求項１３】
複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、前記メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータのメモリ・アクセス順序付け装置において、
メモリ・アクセスについて前後の関係で順序付けを必要とする、プログラム上で前後の記述順となっている、ストア命令及びロード命令は、そのアドレス範囲が重複部分をもつようにかつストア及びロードの必要なデータのアドレス範囲をそれぞれ含むように設定されて、プログラム上に配置されているプログラムと、
これらストア命令及びロード命令の対を各ＣＰＵにおいて検出させる検出手段と、
検出された対に係るプログラムを実行するＣＰＵに、その投機実行中止機構を、検出した対に対して作動させる作動手段と、
を含むことを特徴とするメモリ・アクセス順序付け装置。
【請求項１４】
各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
前記投機実行中止機構は、前記対の両命令に係る、前記メモリ上の、アドレス範囲が同一である場合には、前記対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとして前記ストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、前記対の両命令に係る、前記メモリ上の、アドレス範囲が部分的にのみ重複している場合には、前記対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、前記対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
前記作動手段では、検出された対に係るプログラムを実行するＣＰＵに、該対に対して前記投機実行中止機構のＳＦＡ機構を作動させる、
ことを特徴とする請求項１３記載のメモリ・アクセス順序付け装置。
【請求項１５】
前記対において、ストア命令のアドレス範囲は本来的にストアの必要なデータのみをストアするように設定されているのに対し、ロード命令のアドレス範囲は、本来的にロードの必要なデータと共にロードの不要なデータもロードするように、設定され、該ロード命令に基づいてデータをロードを実行するロード命令実行手段と、
本来的にロードの必要なデータは、ロード命令によりロードしたデータから抽出する抽出手段と、
を含むことを特徴とする請求項１３記載のメモリ・アクセス順序付け装置。
【請求項１６】
前記プログラムは第１及び第２の処理に係る第１及び第２のプログラム部分を含み、第１及び第２の処理は、ストア処理部分、及び相手の処理でストアしたかもしれないデータを前記ストア処理部分の実行後に観測する観測処理部分、及び該観測処理部分の観測結果に基づいて対応の処理へ分岐する分岐処理部分を含み、
前記対におけるストア命令及びロード命令は、第１及び第２の処理におけるストア処理部分及び観測処理部分に含まれていることを特徴とする請求項１３記載のメモリ・アクセス順序付け装置。
【請求項１７】
第１及び第２の処理は、それぞれオブジェクト管理装置のオブジェクトのロック解除に係る処理及びオブジェクト獲得に係る処理であることを特徴とする請求項１６記載のメモリ・アクセス順序付け装置。
【請求項１８】
複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、前記メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにより実行するロック管理装置であって、
前記ロック管理装置では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
前記第１の種類のロックは、オブジェクトに対してロックを実施するスレッドの識別子を前記フィールドに記憶することによりオブジェクトに対するロックを行うものであり、前記第２の種類のロックは、前記第１の種類のロックよりも処理が複雑なロック方式のものであり、
さらに、前記ロック管理装置は、第１のスレッドが保持している或るオブジェクトへのロックを第２のスレッドが獲得するオブジェクト獲得装置と、前記第１のスレッドが前記或るオブジェクトへのロックを解除するロック解除装置とを含み、
前記オブジェクト獲得装置は、
（ａ１）前記或るオブジェクトの前記ロックの種類を示すビットが第１の種類のロックであることを示しているか判断する手段と、
（ａ２）前記第１の種類のロックであることを示しているときには、競合ビットを立てる手段と、
（ａ３）前記（ａ２）の手段により競合ビットを立てた後、前記第１の種類のロックを獲得することが可能な場合には、前記競合ビットをクリアし、前記第２の種類のロックに係る識別子及び該ロックの種類を示すビットを前記フィールドに記憶し、前記第２の種類のロックを獲得するが、前記第１の種類のロックを獲得することができない場合には、待機状態に移行する手段と、
を含み、
前記ロック解除装置は、
（ｂ１）前記ロックの種類を示すビットが前記第１の種類のロックであることを示しているか判断する手段と、
（ｂ２）前記或るオブジェクトのロックを保持しているスレッドが存在しないことを前記記憶領域に記憶する手段と、
（ｂ３）前記ロックの種類を示すビットが前記第１の種類のロックであることを示しているときには、前記競合ビットが立っているか判断する手段と、
（ｂ４）前記競合ビットが立っていないと判断されたときには終了する手段と、
（ｂ５）前記（ｂ２）における記憶に対応するストア命令Ｓと前記（ｂ３）におけるビットの読み出しに対応するロード命令Ｌとについて、前記投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定されたプログラムと、
を含み、
該設定に基づいた処理を前記（ｂ２）及び（ｂ３）の手段が実施する、ことを特徴とするロック管理装置。
【請求項１９】
各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
前記投機実行中止機構は、前記対の両命令に係る、前記メモリ上の、アドレス範囲が同一である場合には、前記対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとして前記ストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、
前記対の両命令に係る、前記メモリ上の、アドレス範囲が部分的にのみ重複している場合には、前記対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、前記対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
前記ストア命令Ｓ及び前記ロード命令Ｌに係る、メモリ上の、アドレス範囲は、ＳＦＡ機構を作動させるように、設定され、
該設定に基づいた処理を前記（ｂ２）及び（ｂ３）の手段が実施する、ことを特徴とする請求項１８記載のロック管理装置。
【請求項２０】
前記（ｂ２）における記憶に対応するストア命令Ｓは、前記或るオブジェクトのロックを保持しているスレッドが存在しないことが記憶される前記記憶領域に係るアドレス範囲Ａ１をアドレス範囲として設定され、
前記（ｂ３）におけるビットの読み出しに対応するロード命令Ｌは、該ビットに係るアドレス範囲を全部含むとともに、前記アドレス範囲Ａ１を少なくとも部分的に含むアドレス範囲Ａ２をアドレス範囲として設定され、
該設定に基づいた処理を前記（ｂ２）及び（ｂ３）の手段が実施する、
ことを特徴とする請求項１８記載のロック管理装置。
【請求項２１】
前記ロック解除装置は、
（ｂ５）前記競合ビットが立っていると判断されたときには、オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の制御状態に前記第１のスレッドが移行する手段と、
（ｂ６）待機しているスレッドへの通知操作を実行する手段と、
（ｂ７）前記第１のスレッドが前記排他制御状態から脱出する手段と、
をさらに含むことを特徴とする請求項１８記載のロック管理装置。
【請求項２２】
複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、前記メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにより実行するロック管理装置であって、
前記ロック管理装置では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又はオブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
前記第１の種類のロックは、オブジェクトに対してロックを実施するスレッドの識別子を前記フィールドに記憶することによりオブジェクトに対するロックを行うものであり、
前記ロック管理装置は、
（ｃ１）オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の制御状態に第１のスレッドを移行させる手段と、
（ｃ２）或るオブジェクトの前記ロックの種類を示すビットが第１の種類のロックであることを示しているか判断する手段と、
（ｃ３）前記或るオブジェクトの前記ロックの種類を示すビットが第１の種類のロックであることを示しているとき、競合ビットをセットする手段と、
（ｃ４）前記（ｃ３）の手段の後、前記或るオブジェクトに対応して設けられた記憶領域の内容に基づいて前記第１の種類のロックを第１のスレッドが獲得できるか判断する手段と、
（ｃ５）前記第１の種類のロックを第１のスレッドが獲得できるときには、前記或るオブジェクトに対応して設けられた記憶領域に第２の種類のロックを示すビット及び前記第２の種類のロックに係る識別子を記憶する手段と、
（ｃ６）前記第１のスレッドを、前記或るオブジェクトに対して必要な処理を終了した後に前記制御状態から脱出させる手段と、
（ｃ７）前記（ｃ３）における競合ビットのセットに対応するストア命令Ｓと前記（ｃ４）における前記記憶領域の内容の読み出しに対応するロード命令Ｌとについて、前記投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定されたプログラムと、
を含み、
該設定に基づいた処理を前記（ｃ３）及び（ｃ４）の手段が実施する、
ことを特徴とするロック管理装置。
【請求項２３】
各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
前記投機実行中止機構は、前記対の両命令に係る、前記メモリ上の、アドレス範囲が同一である場合には、前記対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとして前記ストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、
前記対の両命令に係る、前記メモリ上の、アドレス範囲が部分的にのみ重複している場合には、前記対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、前記対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
前記ストア命令Ｓ及び前記ロード命令Ｌに係る、メモリ上の、アドレス範囲は、ＳＦＡ機構を作動させるように、設定され、該設定に基づいた処理を前記（ｃ３）及び（ｃ４）の手段が実施する、
ことを特徴とする請求項２２記載のロック管理装置。
【請求項２４】
前記（ｃ３）における競合ビットのセットに対応するストア命令Ｓは、競合ビットに係るアドレス範囲Ａ１をアドレス範囲として設定され、
前記（ｃ４）における前記記憶領域の内容の読み出しに対応するロード命令Ｌは、前記記憶領域のアドレス範囲を全部含むとともに、前記アドレス範囲Ａ１を少なくとも部分的に含むアドレス範囲Ａ２をアドレス範囲として設定され、
該設定に基づいた処理を前記（ｃ３）及び（ｃ４）の手段が実施する、
ことを特徴とする請求項２２記載のロック管理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、メモリ・アクセス順序付け及びロック管理の方法、装置、プログラム及び記録媒体に関し、特に、ＣＰＵによるロード命令の投機実行機能にもかかわらずメモリ・アクセスについてストア命令及びロード命令についての順序付けを保証するメモリ・アクセス順序付け及びロック管理の方法、装置、プログラム及び記録媒体に関する。
【０００２】
【従来の技術】
サーバー向けソフトウェアは、複数のクライアントからの要求を処理するため、マルチスレッドを使ったソフトウェアになる。一般的にそうしたスレッド並列性を持つソフトウェアは、マルチプロセッサを用いて並列処理し、多くの処理を同時に行えることができる。マルチスレッドでは、複数のスレッドが同じデータを更新することがよく起きる。このような場合には、データの一貫性を保証するため同期機構を用いる。マルチスレッドに言語レベルで対応しているJava（Sun Microsystems社の商標）では、synchronizedメソッドおよびsynchronizedブロックの２種類の同期機構をサポートしている。今日、ミドルウェアなどサーバー向けソフトウェアがJavaで書かれることが多くなっている。そのため、このJavaにおける２つの同期機構の性能は、サーバーの性能に大きな影響を与える。
【０００３】
本出願人は、オブジェクト管理システムにおける優れた同期機構のアルゴリズムとして襷（tasuki）ロックを提案した（特開２０００−７６０８６）。tasukiロックの特徴は、atomic命令が１つで済む軽量（thin）ロックのメリットを維持しつつ、thinロックが持つ弱点であるスピンウェイトを排除したことである。tasukiロックは、今考えられる限り最も優れたアルゴリズムであり、それを実装したJava仮想マシンが公知になっている。
【０００４】
ここで、オブジェクト管理システムにおけるtasukiロックについて、その他のロック方式と一緒に説明する。複数のスレッドが動作するプログラムでオブジェクトへのアクセスを同期させるためには、アクセスの前にオブジェクトをロック（lock）し、次にアクセスを行い、アクセスの後にアンロック（unlock）するようにプログラムのコードは構成される。このオブジェクトのロックの実装方法としては、スピンロック及びキューロックがよく知られている。また、それらを組み合わせたもの（以下、複合ロックという）も提案されている。
【０００５】
（１）スピンロック：
スピンロックとは、オブジェクトに対してロックを実施するスレッドの識別子を当該オブジェクトに対応して記憶することによりロック状態を管理するロック方式である。スピンロックでは、スレッドＴがオブジェクトｏのロック獲得に失敗した場合、すなわち他のスレッドＳが既にオブジェクトｏをロックしている場合、ロックに成功するまでロックを繰り返す。典型的には、compare_and_swapのようなアトミックなマシン命令を用いて、次のようにロック又はアンロックする。
【０００６】
【表１】
10 /* ロック */
20 while (compare_and_swap(&o->lock,0,thread_id())==0)
30   yield();
40 /* ｏへのアクセス */
・・・
50 /* アンロック */
60 o->lock=0;
【０００７】
表１では、第２０行及び第３０行でロックを行っている。ロックが獲得できるまでyield()を行う。ここでyield()とは、現在のスレッドの実行を止め、スケジューラに制御を移すことである。通常、スケジューラは、他の実行可能なスレッドから１つを選び走らせるが、いずれまた、スケジュラーは、もとのスレッドを走らせることになり、ロックの獲得に成功するまでwhile文の実行が繰り返される。yieldが存在していると、単にＣＰＵ資源の浪費だけでなく、実装がプラットフォームのスケジューリング方式に依存せざるを得ないため、期待どおりに動作するプログラムを書くことが困難になる。第２０行におけるwhile文の条件であるcompare_and_swapは、オブジェクトｏに用意されたフィールドo->lockの内容と、０とを比較して、その比較結果が真であればスレッドのＩＤ（thread_id()）をそのフィールドに書き込むものである。よって、オブジェクトｏに用意されたフィールドに０が格納されている場合には、ロックしているスレッドが存在しないことを表している。よって、第６０行でアンロックする場合にはo->lockに０を格納する。なお、このフィールドは例えば１ワードであるが、スレッド識別子を格納するのに十分なビット数であればよい。
【０００８】
（２）キューロック：
キューロックとは、オブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である。キューロックにおいては、スレッドＴがオブジェクトｏのロックに失敗した場合、Ｔは自分自身をｏのキューに入れてサスペンドする。アンロックするコードには、キューが空か否かをチェックするコードが含まれ、空でなければキューから１つスレッドを取り出し、そのスレッドをリジュームする。このようなキューロックは、オペレーティング・システム（ＯＳ）のスケジューリング機構と一体になって実装され、ＯＳのＡＰＩ（Application Programming Interface）として提供されている。例えば、セマフォやＭｕｔｅｘ変数などが代表的なものである。キューロックにおいては、スペースオーバーヘッドはもはや１ワードでは済まず、十数バイトとなるのが普通である。また、ロックやアンロックの関数の内部では、キューという共有資源が操作されるため、何らかのロックが獲得され又は解放されている点にも注意する必要がある。
【０００９】
（３）複合ロック：
マルチ・スレッド対応のプログラムは、マルチ・スレッドで実行されることを考慮して共有資源へのアクセスはロックにより保護するように書かれる。しかし、例えばマルチ・スレッド対応ライブラリがシングル・スレッドのプログラムから使用されるような場合もある。また、マルチ・スレッドで実行されてもロックの競合がほとんど発生しない場合もある。実際、Ｊａｖａ（Sun Microsystems社の商標）のプログラムの実行履歴によると、多くのアプリケーションにおいて、オブジェクトへのアクセスの競合はほとんど発生していないという報告もある。
【００１０】
よって、「ロックされていないオブジェクトにロックをかけ、アクセスし、アンロックする」は高頻度に実行されるパスであると考えられる。このパスは、スピンロックでは極めて効率よく実行されるが、キューロックでは時間的にも空間的にも効率が悪い。一方、高頻度ではないとはいえ、競合が実際に発生した場合、スピンロックではＣＰＵ資源が無益に消費されてしまうが、キューロックではそのようなことはない。
【００１１】
複合ロックの基本的なアイデアは、スピンロックのような処理が簡単なロック（軽量ロックと呼ぶ）とキューロックのような処理が複雑なロック（重量ロックと呼ぶ）をうまく組み合わせて、前記の高頻度パスを高速に実行しつつ、競合時の効率も維持しようというものである。具体的に言えば、最初に軽量ロックでのロックを試み、軽量ロックで競合した場合重量ロックに遷移し、それ以降は重量ロックを使用するものである。
【００１２】
この複合ロックでは、スピンロックと場合と同様に、オブジェクトにはロック用のフィールドがあり、「スレッド識別子」又は「重量ロック識別子」の値、及び、いずれの値を格納しているかを示すブール値が格納される。
【００１３】
ロックの手順は以下のとおりである。
１）アトミックな命令（例えば、compare_and_swap）で軽量ロック獲得を試みる。成功すればオブジェクトへのアクセスを実行する。失敗した場合、すでに重量ロックになっているか、又は軽量ロックのままだが他のスレッドがロックをかけているのかのいずれかであることが分かる。
２）既に重量ロックになっていれば、重量ロックを獲得する。
３）軽量ロックで競合した場合、軽量ロックを獲得した上で重量ロックへ遷移し、これを獲得する（以下の説明では、inflate関数において実行される。）
【００１４】
複合ロックには、３）における「軽量ロックの獲得」でyieldするか否かで２種類の実装がある。これらを詳しく以下に説明する。なお、ロック用のフィールドは１ワードとし、さらに簡単のため「スレッド識別子」又は「重量ロック識別子」は常に０以外の偶数であるとし、ロック用のフィールドの最下位ビットが０ならば「スレッド識別子」、１ならば「重量ロック識別子」が格納される。
【００１５】
複合ロックの例１：
軽量ロックの獲得において、yieldする複合ロックの場合である。ロック関数は上の手順に従って以下のように書くことができる。
【００１６】
【表２】
10 :void lock(o) {
20 :   if (compare_and_swap(&o->lock, 0, thread_id())
30 :     return;
40 :   while (! (o->lock & FAT_LOCK)) {
50 :     yield();
60 :     if (compare_and_swap (&o->lock, 0, thread_id())){
70 :       inflate(o);
80 :       return;
90 :     }
100:   }
110:     fat_lock(o->lock)
120:     return;
130: }
150: void unlock (o){
160:   If (o->lock==thread_id())
170:     o->lock=0;
180:   else
190:       fat_unlock(o->lock);
200: }
220: void inflate(o){
230;   o->lock= alloc_fat_lock() | FAT_LOCK;
240:   fat_lock(o->lock);
250: }
【００１７】
表２に示された擬似コードは、第１０行から第１３０行までがロック関数、第１５０行から第２００行までがアンロック関数、第２２０行から第２５０行までがロック関数で用いられるinflate関数を示している。ロック関数内では、第２０行で軽量ロックが試みられる。もしロックが獲得されれば、当該オブジェクトへのアクセスを実行する。そして、アンロックする場合には、第１６０行でオブジェクトのロック用フィールドにスレッド識別子が入力されているので、第１７０行においてそのフィールドに０を入力する。このように高頻度パスはスピンロックと同じで高速に実行することができる。一方、第２０行でロックを獲得できないときには、第４０行でｗｈｉｌｅ文の条件であるロック用フィールドの最下位ビットであるＦＡＴ＿ＬＯＣＫビットとロック用フィールドをビットごとにＡＮＤした結果が０であるか、すなわちＦＡＴ＿ＬＯＣＫビットが０であるか（より詳しく言うと軽量ロックであるか）判断される。もし、この条件が満たされていれば、第６０行にて軽量ロックを獲得するまでyieldする。軽量ロックを獲得した場合には、第２２０行以降のinflate関数を実行する。inflate関数では、ロック用フィールドo->lockに重量ロック識別子及び論理値１であるＦＡＴ＿ＬＯＣＫビット入力する（第２３０行）。そして、重量ロックを獲得する（第２４０行）。もし、第４０行で既にＦＡＴ＿ＬＯＣＫビットが１である場合には、直ぐに重量ロックを獲得する（第１１０行）。重量ロックのアンロックは第１９０行にて行われる。なお、重量ロックの獲得及び重量ロックのアンロックは、本発明とはあまり関係ないので説明を省略する。
【００１８】
この表２ではロック用フィールドの書き換えは常に軽量ロックを保持するスレッドにより実施される点に注意されたい。これは、アンロックでも同じである。yieldが発生するのは、軽量ロックでの競合時に限定されている。
【００１９】
複合ロックの例２：
軽量ロックの獲得において、yieldしない複合ロックの例を示す。軽量ロックが競合した場合にはウエイト（wait）する。軽量ロック解放時には、ウエイトしているスレッドに通知（notify）しなければならない。このウエイト及び通知のためには、条件変数やモニタあるいはセマフォを必要とする。以下の例ではモニタを使用して説明する。
【００２０】
【表３】
10 :void lock (o) {
20 :   if (compare_and_swap (&o->lock, 0, thread_id())
30 :     return; 40 : monitor_enter (o);
50 :     while (! (o->lock, & FAT_LOCK)){
60 :       if (compare_and_swap(&o->lock, 0, thread_id()){
70 :         inflate(o);
80 :         monitor_exit(o);
90 :         return;
100:       } else
110:           monitor_wait(o);
120:   }
130:   monitor_exit(o);
140:   fat_lock(o->lock);
150:   return;
160: }
180: void unlock (o) {
190:   if (o->lock == thread_id()) {
200:     o->lock=0;
210:     monitor_enter(o);
220:     monitor_notify(o);
230:     monitor_exit(o);
240:   } else
250:     fat_unlock(o->lock);
260: }
280: void inflate (o) {
290:   o->lock = alloc_fat_lock() | FAT_LOCK
300:   fat_lock(o->lock);
310:   monitor_notify_all(o);
320: }
【００２１】
モニタとは、Ｈｏａｒｅによって考案された同期機構であり、オブジェクトへのアクセスの排他制御（enter及びexit）と所定の条件が成立した場合のスレッドの待機操作（wait）及び待機しているスレッドへの通知操作（notify 及びnotify_all）とを可能にする機構である（Hoare, C.A.R. Monitors: An operatingsystem structuring concept. CommunicationS of ACM 17, 10 (Oct. 1974), 549-557 参照）。高だか１つのスレッドがモニタにエンタ（enter）することが許される。スレッドＴがモニタｍにエンタしようとした時、あるスレッドＳが既にエンタしているならば、Ｔは少なくともＳがｍからイグジット（exit）するまで待たされる。このように排他制御がなされる。また、モニタｍにエンタ中のスレッドＴは、ある条件の成立を待つため、モニタｍでウエイト（wait）することができる。具体的には、Ｔは陰にｍよりイグジットしサスペンドする。陰にｍよりイグジットすることにより、別のスレッドがモニタｍにエンタすることができる点に注意されたい。一方、モニタｍにエンタ中のスレッドＳは、ある条件を成立させた後に、モニタｍに通知（notify）することができる。具体的には、モニタｍでウエイト中のスレッドのうちのひとつＵを起こす（wake up）する。それにより、Ｕはリジュームし、モニタｍに陰にエンタしようとする。ここで、Ｓがｍにエンタ中であるから、Ｕは少なくともＳがｍからイグジットするまで待たされる点に注意されたい。また、モニタｍでウエイト中のスレッドが存在しない場合には、何も起こらない。notify_allは、ウエイト中のスレッドを全て起こす点を除いて、notifyと同じである。
【００２２】
表３において、第１０行乃至第１６０行はロック関数、第１８０行乃至第２６０行はアンロック関数、第２８０行乃至３２０行はinflate関数を示している。ロック関数で複合ロックの例１と異なる点は、第４０行でモニタにエンタする点、軽量ロックで競合した場合にyieldせずにウエイトする点（第１１０行）、重量ロックに遷移した際（第８０行）及び重量ロックに遷移したことが確認された際（第１３０行）にはモニタからイグジットする点である。ここで、第１３０行ではモニタからイグジットし、第１４０行で重量ロックを獲得している点に注意されたい。
【００２３】
アンロック関数で複合ロックの例１と異なる点は、第２１０行乃至第２３０行においてモニタにエンタし、モニタで通知をし、モニタをイグジットする処理を実施している点である。これは、yieldをやめてモニタにおけるウエイトにしたためである。inflate関数では、notify_allが追加されている。これもyieldをやめてモニタにおけるウエイトにしたためである。なお、第２９０行は、alloc_fat_lock()で得られる重量ロック識別子と論理値１にセットされたＦＡＴ＿ＬＯＣＫビットをＯＲ操作して、ロック用フィールドに入力する操作を示している。
【００２４】
表３を見れば、yieldは消滅しているが、アンロック時にウエイトしているスレッドがいるかもしれないので、通知（notify）という作業が入り、高頻度パスの性能が低下している。また、空間効率的には、モニタ又はモニタと同等な機能が余分に必要になっているが、重量ロックに遷移した後には不要になる。言いかえれば、モニタと重量ロックとは別に用意する必要がある。
【００２５】
複合ロックの例３この例では、複合ロックの例１とは異なり、重量ロックとモニタとを別に用意せず、ＦＡＴ＿ＬＯＣＫビットが重量ロックへの遷移を示しておりかつモニタに入った場合には重量ロックを獲得したとして処理をする。例えば、David F.Bacon, Ravi Konuru, Chet Murthy, and Mauricio Serrano. Thin Locks: Featherweight Synchronization for Java. Proceedings of the SIGPLAN '98 Conference on Programming Language Design and Implementation (1998), pp. 258-268を参照のこと。但し、この論文ではyieldが行われている。
【００２６】
次に開示するtasukiロックは、高頻度パスの処理速度を低下させない複合ロック方法である。また、yieldを用いずに、重量ロックとモニタとを別に用意することなく、ＦＡＴ＿ＬＯＣＫビットが重量ロックへの遷移を示しておりかつモニタに入った場合には重量ロックを獲得したとして処理できる。さらに、表３までの複合ロックでは、重量ロックから軽量ロックへの遷移は何等考慮されていないのに対し、次のtasukiロックでは、重量ロックから軽量ロックへの遷移を可能にする。
【００２７】
tasukiロックでは、高頻度パスの処理速度を低下させないための競合ビットを新たに導入する。図１に示すように、或るオブジェクトをロックしているスレッドが存在しない場合（（１）の場合）には、ロック用フィールド及び競合ビット共に０が格納される。その後、あるスレッドがそのオブジェクトをロック（軽量ロック）すると、そのスレッドの識別子がロック用フィールドに格納される（（２）の場合）。もし、このスレッド識別子のスレッドがロックを解放するまでに他のスレッドがロックを試みなければ（１）に戻る。ロックを解放するまでに他のスレッドがロックを試みると、軽量ロックにおける競合が発生したので、この競合を記録するため競合ビットを立てる（（３）の場合）。その後、重量ロックに移行した際には、競合ビットはクリアされる（（４）の場合）。可能であれば、（４）は（１）に移行する。なお、ロック用フィールドの最下位に軽量ロックと重量ロックのモードを表すビット（ＦＡＴ＿ＬＯＣＫビット）設けるようにしたが、最上位に設けるようにしても良い。
【００２８】
上のような競合ビット及びロック用フィールドを用いた本tasukiロックの処理を以下に示す。
【００２９】
【表４】
10 : void lock (Object* o){
20 :   /* 軽量ロック */
30 :   if (compare_and_swap (&o->lock, 0, thread_id()))
40 :     return;
50 :   /* 重量ロック及びモード遷移パス */
60 :   MonitorId mon=obtain_monitor(o);
70 :   monitor_enter(mon);
80 :   /* モード遷移ループ */
90 :   while (o->lock & FAT_LOCK) ==0) {
100:     set_flc_bit(o);
110:     if (compare_and_swap (&o->lock, 0, thread_id()))
120:       inflate(o, mon);
130:     else
140:       monitor_wait (mon);
150:   }
160:
170: }
180:
190: void unlock (Object* o) {
200:   /* 軽量ロックパス */
210:   if ((o->lock & FAT_LOCK) ==0)
220:     o->lock=0;
230:     if (test_flc_bit(o)) { /* 本発明のオーバーヘッド */
240:       MonitorId mon=obtain_monitor(o);
250:       monitor_enter(mon);
260:       if (test_flc_bit(o))
270:         monitor_notify(mon);
280:       monitor_exit(mon);
290:     }
300:     return;
310:   }
320:   /* 重量ロックパス */
330:   x=o->lock
340:   if (oについてモニタでウエイトしているスレッドがない)
350:     if (所定の条件が満たされた)
360:       o->lock=0; /* 重量ロックから軽量ロックへの遷移 */
370:     monitor_exit( x & ~FAT_LOCK );
380: }
390:
400:
410: void inflate (Object* o, MonitorId mon) {
420:   clear_flc_bit;
430:   monitor_notify_all (mon);
440:   o->lock= (Word) mon | FAT_LOCK;
450: }
460:
470:
480: MonitorId obtain_monitor(Object* o){
490:   Word word=o->lock;
500:   MonitorID mon;
510:   if (word & FAT_LOCK)
520:     mon = word & ~FAT_LOCK;
530:   else
540:     mon = lookup_monitor(o);
550:   return mon;
560: }
【００３０】
tasukiロックで導入された競合ビットは表４ではｆｌｃ＿ｂｉｔとして示されている。では、表４の内容を詳細に説明する。表４は大きく分けて４つの部分からなる。ロック関数の部分（第１０行乃至第１７０行）、アンロック関数の部分（第１９０行乃至第３８０行）、軽量ロックから重量ロックへの遷移であるinflate関数の部分（第４１０行乃至第４５０行）、及びモニタの識別子を取得するobtain_monitor関数の部分（第４８０行乃至第５６０行）である。
【００３１】
（１）ロック関数：
第１０行から始まったオブジェクトｏに対するロック関数の処理では、まず軽量ロックの取得を試みる（第３０行）。この軽量ロックの取得には、例えばcompare_and_swapのようなアトミックな命令を用いる。この命令では、第１の引き数と第２の引き数が同じ値の場合、第３の引き数を格納するものである。ここでは、オブジェクトｏのロック用フィールドであるo->lockが０に等しい場合には、thread_id()によりスレッド識別子を取得して、ロック用フィールドo->lockに格納する。図１の（１）から（２）への遷移を実施したのである。そして、必要な処理を実施するため、リターンする（第４０行）。もし、オブジェクトｏのロック用フィールドであるo->lockが０に等しくない場合には、軽量ロックの取得は失敗し、第６０行に移行する。ここまでの処理は表３のコードと同じである。
【００３２】
次に、モニタ識別子を取得するobtain_monitor(o)関数の値をmonという変数に代入し（第６０行）、スレッドはそのモニタの排他制御状態に移行しようとする。すなわちモニタ（monitor）にエンタ（enter）しようとする（第７０行）。もし、排他制御状態に移行することができれば、以下の処理を実施し、もしできなかった場合には、できるまでこの段階で待つ。次に、while文の条件を判断する。すなわち、ロック用フィールドo->lockとＦＡＴ＿ＬＯＣＫビットのビットごとのＡＮＤを実施し、ＦＡＴ＿ＬＯＣＫビットが立っているか判断する（第９０行）。ここでは、現在重量ロックに移行しているのか、軽量ロック中なのかを判断している。もし、ＦＡＴ＿ＬＯＣＫビットが立っていなければ（軽量ロック中）、この計算の結果は０となるから、while文以下の処理を実施する。一方、ＦＡＴ＿ＬＯＣＫビットが立っている場合（重量ロック中）、while文以下の処理を実施せずに、モニタにエンタした状態のままになる。このようにＦＡＴ＿ＬＯＣＫビットが立っている場合に、モニタにエンタできた場合には、tasukiロックでは重量ロックを取得できたということを意味しており、このモニタからイグジット（exit）することなく（すなわち排他制御状態を脱出することなく）、このスレッドはオブジェクトに対する処理を実施する。
【００３３】
では、第９０行でＦＡＴ＿ＬＯＣＫビットが立っていないと判断されたときには、軽量ロックの競合が発生していることを意味するので、ｆｌｃ＿ｂｉｔをセットする（第１００行、set_flc_bit(o)）。ここで、図１の（２）から（３）への遷移を実施したのである。そして、もう一度軽量ロックを取得できるか判断する（第１１０行）。もし、軽量ロックを取得できる場合には軽量ロックから重量ロックへの遷移のためのinflate関数の処理を実施する（第１２０行）。一方、軽量ロックが取得できないときには、モニタの待機状態（wait）に移行する（第１４０行）。モニタの待機状態は、先にモニタの説明の部分で述べたが、モニタから脱出してサスペンドするものである。このように、軽量ロックで競合が生じると、競合ビットであるｆｌｃ＿ｂｉｔがセットされ、軽量ロックを取得できないときには、モニタの待機状態に移行する。この待機状態に入ると、後にinflate関数の処理又はアンロックする際に通知（notify又はnotify_all）を受けることになる。
【００３４】
（２）inflate関数：
では、第４１０行乃至第４５０行のinflate関数の処理を説明する。ここではまず、競合ビットがクリアされる（第４２０行、clear_flc_bit）。そして、モニタの通知操作（monitor_notify_all）を実施する（第４３０行）。ここでは、待機状態の全てのスレッドに起きる（wake up）よう通知する。そして、ロック用フィールドo->lockに、モニタの識別子を格納した変数ｍｏｎとセットされたＦＡＴ＿ＬＯＣＫビットをビットごとにＯＲした結果を格納する（第４４０行、mon | FAT_LOCK）。すなわち、図１の（３）から（４）の状態に遷移させたのである。これで軽量ロックから重量ロックへの遷移は完了する。なお、第１２０行の処理が終了すると、再度while文の条件をチェックすることになるが、既にＦＡＴ＿ＬＯＣＫビットが立っているので、この場合にはwhile文から脱出して、モニタにエンタしたままとなる。すなわち、while文の中の処理を実行しない。
【００３５】
通知を受けた全てのスレッドは第１４０行において陰にモニタにエンタしようとするが、モニタにエンタする前に待機することになる。これは、通知を行ったスレッドはアンロック処理を実施するまでモニタからイグジットしていないからである。
【００３６】
（３）アンロック関数：
では、次に第１９０行乃至第３８０行のアンロック関数の処理について説明する。このアンロック関数は軽量ロックのアンロックと、重量ロックのアンロックを取扱う。重量ロックにおけるアンロックは、図１の（４）から（１）への遷移を取扱うものである。
【００３７】
（３−１）軽量ロックのアンロック：
軽量ロックのアンロックでは、まず、ロック用フィールドo->lockとＦＡＴ＿ＬＯＣＫビットのビットごとのＡＮＤを計算し、その値が０であるか判断する（第２１０行）。これは、第９０行のwhile文の条件と同じであって、軽量ロック中であるかどうか判断するものである。もし、軽量ロック中である場合には、o->lockに０を格納する（第２２０行）。これにより、ロックを保持しているスレッドが存在しないことが記録される。そして、競合ビットが立っているか判断する（第２３０行、test_flc_bit）。もし、軽量ロックで競合が生じていなくとも、第２３０行のみは実施しなければならない。よって、tasukiロックにおける高頻度パスの唯一のオーバーヘッドがこの第２３０行である。競合ビットが立っていない場合には、他の処理を実施せずにアンロック処理を終了する（第３００行）。
【００３８】
もし、競合ビットが立っている場合には、第６０行及び第７０行と同じように、変数ｍｏｎにモニタの識別子を格納し（第２４０行）、当該モニタ識別子のモニタにエンタしようとする（第２５０行）。すなわち、そのスレッドはモニタの排他制御状態に入ろうとする。もしモニタにエンタできた場合には、もう一度、競合ビットが立っていることを確認し（第２６０行）、もし立っていれば、モニタにおいて待機状態のスレッドの１つに起動を通知する（第２７０行、monitor_notify(mon)）。なお、モニタにエンタできないときには、モニタにエンタできるまで待機する。そして通知を行ったスレッドは、モニタの排他制御状態から脱出する（第２８０行、monitor_exit(mon)）。
【００３９】
第２７０行で通知を受けたスレッドは、第１４０行で陰にモニタにエンタする。そして第８０行に戻りその処理を実施する。通常、第２７０行で通知を受けたスレッドは、通知を行ったスレッドがモニタの排他制御状態を脱出した後にモニタの排他制御状態に入り、競合ビットを立てた後に、軽量ロックを取得し、inflate関数の処理を実施することにより重量ロックに遷移する。
【００４０】
（３−２）重量ロックのアンロック：
もし、第２１０行でＦＡＴ＿ＬＯＣＫビットが立っていることが分かった場合には、第３３０行に処理は移行する。第３３０行では、ロック用フィールドの内容を変数ｘに格納する。そして、モニタにおける待機状態（wait）にあるスレッドが他に存在しないかを判断する（第３４０行）。もし、存在しない場合には、所定の条件を満たしているか判断する（第３５０行）。所定の条件には、重量ロックから脱出しない方が良いような条件があればそのような条件を設定する。但し、本ステップは実行しなくてもよい。もし、所定の条件を満たしている場合には、ロック用フィールドo->lockを０にする（第３６０行）。すなわち、ロックを保持しているスレッドが存在しないことをロック用フィールドに格納する。そして、変数ｘのＦＡＴ＿ＬＯＣＫビット以外の部分に格納されたモニタ識別子のモニタからイグジットする（第３７０行）。x & ~FAT_LOCK は、FAT_LOCKビットを反転させたものとxとのビットごとのＡＮＤである。これにより、モニタにエンタしようとして待機していたスレッドが、モニタにエンタできるようになる。
【００４１】
（４）モニタ識別子を取得するobtain_monitor関数：
この関数では、まず、wordという変数にロック用フィールドの内容を格納する（第４９０行）。そして、モニタの識別子を格納する変数ｍｏｎを用意し（第５００行）、ＦＡＴ＿ＬＯＣＫビットが立っているか判断する（第５１０行、word& FAT_LOCK）。もし、ＦＡＴ＿ＬＯＣＫビットが立っているようであれば、変数ｍｏｎにｗｏｒｄのＦＡＴ＿ＬＯＣＫビット以外の部分を格納する（第５２０行、word & ~FAT_LOCK）。一方、ＦＡＴ＿ＬＯＣＫビットが立っていない場合には、関数ｌｏｏｋｕｐ＿ｍｏｎｉｔｏｒ（ｏ）を実行する（第５３０行）。この関数は表４で説明は省略しているが、オブジェクトとモニタの関係を記録したハッシュ・テーブルを有していることを前提とし、基本的にはこのテーブルをオブジェクトｏについて検索して、モニタの識別子を取得する。もし、必要があれば、モニタを生成し、そのモニタの識別子をハッシュ・テーブルに格納した後にモニタ識別子を返す。いずれにしても、変数ｍｏｎに格納されたモニタの識別子を返す。
【００４２】
表３と表４とを比較すると、競合ビットを導入した他に、第１５０行乃至第１７０行の間に何等の処理が存在していない点、及び第３２０行乃至第３７０行の重量ロックから軽量ロックへの遷移が存在している点、が大きく異なる。競合ビットを導入したことにより第２３０行のチェックが必要になったが、競合ビットを導入しなければ、表３のような、より大きなペナルティを受ける。また、ＦＡＴ＿ＬＯＣＫビットが立っておりかつモニタの排他制御状態に移行することができた場合には重量ロックを獲得しているということにしたため、モニタの他に重量ロックの機構を用意する必要がなくなり、かつモニタの排他的状態からの脱出及び重量ロックの獲得といった処理をなくし、それにより処理を高速化することもできるようになった。また、重量ロックから軽量ロックへの遷移（図１の（４）から（１））を設けたことにより、低負荷な高頻度パス（図１の（１）と（２）の間の遷移）を実行できるような状態に戻ることができた。
【００４３】
以下に、競合ビットを表４内の第１００行でセットし、第２３０行でチェックすることで何等の問題が生じないということについて述べておく。最初に、「競合ビットは、inflate関数でのみクリアされる」ということを確認しておく。
【００４４】
そして、スレッドＴがウエイト（wait）したとする。スレッドＴが必ず通知（notify）を受けることを、次の２つの場合に分けて説明する。
（１）その後inflate関数が実行される場合。 inflate関数が実行されると、第４３０行目でnotify_allが実行される。すなわち、Ｔはnotifyを受ける。
（２）inflate関数が実行されない場合。 Tがウエイト（wait）したのは、第１１０行目における軽量ロック獲得に失敗したからである。第１１０行目の失敗の時点を考えると、この時点で別なスレッドＳが軽量ロックを保持している、すなわち、Ｓはアンロック関数の第２２０行目の実行に到達していない。また、Ｔがウエイト（wait）前にセットした競合ビットは、inflate関数が実行されない場合を考えているので、上で確認した事項により、セットされたままである。Ｓはいずれアンロック関数の第２２０行目に到達し、次の競合ビットのチェックを実行するが、このチェックは必ず成功する。すなわち、ＴはＳにより通知（notify）される。
【００４５】
また、図１における（４）から（１）の遷移を導入した。これは、１）軽量ロックを獲得するためには第３０行のcompare_and_swapを成功しなければならないが、他のスレッドが重量ロックを獲得している限り、第３０行のcompare_and_swapは成功しないので、重量ロックを他のスレッドが獲得している時には軽量ロックを獲得することは不可能であることが保証され、２）重量ロックを獲得するためには、モニタにエンタしてwhile文の条件が満たされない必要があるが、他のスレッドが軽量ロックを保持している限り、必ずwhile文の条件が満たされてしまうので、軽量ロックを他のスレッドが獲得している時にはモニタにエンタできても重量ロックを獲得することは不可能であることが保証されるので、安全な処理である。
【００４６】
tasukiロックは優れたアルゴリズムであるが、先進的なＣＰＵでは効率的な実装が不可能であった。その原因は、tasukiロックが必要とするメモリ・アクセスの順序関係にある。原因について議論する前に、このtasuki制約と言うべきメモリ・アクセス順序について簡単に説明しておく。tasukiロックはstarvation freeを実現するために、以下のメモリ・アクセス順序を必要としている。tasukiロックの解除は、スレッドID（TIDフィールド：スレッド識別フィールド）のクリア、その後、フラットロックコンテンションビット（flcビット）の参照、の順に行われる。またtasukiロックの確保失敗による待ち動作は、flcビットのセット、その後、TIDフィールドの参照、の順に行われる。これらStore-Loadのメモリ・アクセス順序が崩れると、２度と起こされないスレッドが生じる。
【００４７】
tasuki制約が特に問題となるのは、先進的なアーキテクチャのＣＰＵによるマルチプロセッサ環境である。具体的には、ＣＰＵが元のプログラムにおけるloadとstoreの順番を変えて、loadがstoreを抜いて投機的に（out-of-order）実行されるアーキテクチャである。プログラムの実行時間においてloadのレイテンシを隠すことは非常に重要であり、投機的なload実行は見かけのレイテンシ隠しに非常に貢献する。そのため、最近のほとんどすべてのＣＰＵは、このような投機的load実行機構を持つ。しかしこのようなＣＰＵでは、プログラム上、tasuki制約を満たすように書いても、実際のＣＰＵ内部ではtasuki制約が満たされない。
【００４８】
tasuki制約を満たすためには、loadがstoreを抜かないように特に明示的に順序づけ（serialize）する必要がある。現在存在する明示的順序づけのための命令は、fenceとsync（あるいはそれに属する命令）である。fence命令は、プログラム上その命令に先行するすべてのメモリ・アクセス命令をfence実行前に完了させ、プログラム上その命令に続くすべてのメモリ・アクセス命令をfence実行後に開始する。sync命令は、fence命令と似ているが、メモリ・アクセス命令に限らずすべて命令が対象である。例えばIntel Pentium 4では、fenceにはlfence, sfence, mfenceの３命令がある。syncには、lockプレフィックス付きの命令、I/O命令、ＣＰＵID命令などがある（Pentium IIあるいはPentium IIIも同様）。PowerPCにはsync命令がある。
【００４９】
tasukiロックにおけるtasuki制約について図２を参照して説明する。tasukiロックを実行するために、各オブジェクトに対応してオブジェクト・ヘッダが用意される。このオブジェクト・ヘッダは３個のワード（１ワードは３２ビットから成る。）から成り、競合ビットとしてのｆｌｃ(flat lock contention)ビットはオブジェクト・ヘッダの第１行目のワード内に配置され、ＴＩＤ（スレッドＩＤ）はオブジェクト・ヘッダの第３行目のワード内に配置される。スレッドＡには、オブジェクトを解放するためのストア命令及びロード命令のコードを順序付けて記述されている。これらストア命令及びロード命令は表４の第２２０行及び第２３０行に対応する。すなわち、ストア命令では、ＴＩＤをクリアし、ロード命令ではｆｌｃ  ｂｉｔの値をレジスタへ書き込んでいる。一方、スレッドＢには、オブジェクトをロックするためのストア命令及びロード命令のコードを順序付けて記述されている。これらストア命令及びロード命令は表４の第１００行及び第１１０行に対応する。すなわち、ストア命令では、ｆｌｃ  ｂｉｔをクリアし、ロード命令ではＴＩＤをレジスタへ書き込んでいる。各スレッドがメモリにストアした内容は他のスレッドから視覚可能（ｖｉｓｉｂｌｅ）とならなければならないので、各スレッドにおけるストア命令及びストア・バッファの順序付けは厳格に守られなければならない。ところが、先進的ＣＰＵのマルチプロセッサ環境では、ロード命令のレイテンシを隠すために、プログラム上ではロード命令がストア命令より後の順序付けにもかかわらず、ロード命令をストア命令より先に実行する投機実行が行われる。結果、例えば、スレッドＢは、ｆｌｃ  ｂｉｔをセットして、オブジェクトｏを図１の（２）から（３）へ移行させ、移行後の処理を開始したにもかかわらず、スレッドＡは、まだセットされていないオブジェクトｏのｆｌｃ  ｂｉｔを読み込んで、まだ、無競合の状態と判断して、オブジェクトｏについての無競合の状態でのアンロック処理を実行してしまい、すなわち、無競合と判断した時点でアンロック処理を終了してしまい（表４の第３００行のｒｅｔｕｒｎ）、結果、ウェイトしているスレッドへの通知（表４の第２７０行のｎｏｔｉｆｙ）が行われずじまいになってしまい、該ウェイトしているスレッドは永遠にウェイトし続けてしまう。故に、所定のストア命令及びロード命令の対はtasuki制約としてメモリ・アクセスへの順序付けを厳守しなければならない。
【００５０】
図３は各スレッドにおけるストア命令及びロード命令の順序付けを保証する措置の説明図である。図３（ａ）では、ｆｅｎｃｅ命令がストア命令とロード命令との間に挿入される。これにより、各スレッドにおいてコード順番がｆｅｎｃｅ命令より前のストア命令及びロード命令は、メモリ・アクセス順も、該ｆｅｎｃｅ命令より前となり、また、各スレッドにおいてコード順番がｆｅｎｃｅ命令より後のストア命令及びロード命令は、メモリ・アクセス順も、該ｆｅｎｃｅ命令より後となる。図３（ｂ）では、ｓｙｎｃ命令がストア命令とロード命令との間に挿入される。これにより、ロード命令及びストア命令だけでなくａｄｄ（加算）及びｓｕｂ（減算）等の他の命令を含む全部の命令について、各スレッドにおいてコード順番がｓｙｎｃ命令より前のものは実行順も前となり、また、各スレッドにおいてコード順番がｆｅｎｃｅ命令より後のものは実行順も後になる。
【００５１】
【発明が解決しようとする課題】
ｆｅｎｃｅ命令を使う場合の問題は、これら明示（explicit）的順序づけ命令を実行すると、非常に大きなオーバーヘッドが生じることである。そのため、先進的ＣＰＵにおいて必然な明示的順序づけ命令によるtasukiロックの実装は、結果的にthinロックのatomic命令が１つですむというメリットを失うことになってしまう。このように、高速なロック確保と無駄のないロック待ちという高バランスなtasukiロックアルゴリズムであるが、そのバランスを失わずには、昨今の投機的load実行機構を持つＣＰＵ上にtasuki制約を実装できなかった。
【００５２】
本発明の目的は、高速性を損なうことなく、プログラムにおけるストア命令及びロード命令の順序付けを、ＣＰＵによる投機実行機能にもかかわらず、メモリ・アクセスについての順序付けとして保証できるメモリ・アクセス順序付け及びロック管理の方法、装置、プログラム及び記録媒体を提供することである。
【００５３】
【課題を解決するための手段】
本発明では、ＣＰＵがプログラムの意味を変えないために暗に（implicit）に持つ、通常は使用を避けられる機構を積極的に使う。この技術をＳＦＡ(store forwarding avoidance)と呼ぶ。この技術はtasukiロック（表４のアルゴリズムのこと。）に限らず、以下説明する条件を満たしていればその他の分野でも、メモリ・アクセス順序を保証するために利用できる。
【００５４】
loadの投機的実行を行うＣＰＵでは、loadのレイテンシを隠すことが重要である。そうしたＣＰＵは多くの場合、storeの結果をloadでＣＰＵ内利用できるＳＦ（store fowarding）という機構を持つ。そうしたＣＰＵではstore実行の高速化のため、store結果はストア・バッファ（store buffer）と呼ばれるストア・バッファーに一旦保持され、後にメモリ階層に書き出される。同じＣＰＵ内でそのstore結果を参照するloadが実行された場合、store fowardingによってstore結果をstore bufferから直接読み出すことができる。こうしてメモリ階層から読み出すレイテンシを隠すことができる。ＳＦを行うためには、いくつかの条件がある（資源を効率的に活用するための、ハードウェア設計からくる条件で一般的と思われる）。典型的なのは、アクセスされるメモリが、同じアドレス、同じサイズであることである。例えばアドレス100番に4バイトstoreした結果は、アドレス100番から4バイトloadする命令にＳＦされる。しかしアドレス100番に4バイトstoreした結果は、アドレス100番から8バイトloadする命令にＳＦされない。store fowardingされない場合、storeした結果はストア・バッファからメモリ階層に書き出され、loadはメモリ階層から読む。つまりstore fowardingされない場合、loadは投機的実行されず、storeを追い抜かない。本発明の鍵は、この特性を積極的に利用することにある。
【００５５】
本発明のメモリ・アクセス順序付け方法を実行するコンピュータは、複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備する。各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する。コンピュータのメモリ・アクセス順序付け方法は、メモリ・アクセスについて前後の関係で順序付けを必要とする、プログラム上で前後の記述順となっている、ストア命令及びロード命令は、そのアドレス範囲が重複部分をもつようにかつストア及びロードの必要なデータのアドレス範囲をそれぞれ含むように設定されて、プログラム上に配置されており、これらストア命令及びロード命令の対を各ＣＰＵにおいて検出させる検出ステップと、検出された対に係るプログラムを実行するＣＰＵに、その投機実行中止機構を、検出した対に対して作動させる作動ステップと、を含む。
【００５６】
本発明のメモリ・アクセス順序付け方法は、後述のオブジェクト用ロック管理方法への適用に限定されない。該メモリ・アクセス順序付け方法は、プログラム記述順でそれぞれ前と後にあるストア命令及びロード命令について、ＣＰＵの投機実行機能にもかかわらず、そのプログラム上の順序付け通りにメモリ・アクセスを順序付けられる。本発明のメモリ・アクセス順序付け方法が実装されるコンピュータは、各ＣＰＵがストア・バッファ、ストア・フォワーディング（ＳＦ）及びＳＦＡ（ストア・フォワーディング・アボイダンス（ＳＦＡ）を装備するものに限定されない。各ＣＰＵがストア・バッファ、ＳＦ機構及びＳＦＡ機構を装備しないコンピュータにも、本発明のメモリ・アクセス順序付け方法は適用可能である。好ましくは、本発明のメモリ・アクセス順序付け方法は、投機実行中止機構作動のためにアドレス範囲を、本来、ロードの必要なデータに係るアドレス範囲より広げられた、前述の対の、ロード命令によりロードされたデータから、本来必要なデータを抽出するステップを、さらに、含んでいる。このような抽出ステップに対処するために、対において、ストア命令のアドレス範囲は本来的にストアの必要なデータのみをストアするように設定されているのに対し、ロード命令のアドレス範囲は、本来的にロードの必要なデータと共にロードの不要なデータもロードするように、設定されている。
【００５７】
好ましいメモリ・アクセス順序付け方法によれば、各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備する。投機実行中止機構は、対の両命令に係る、メモリ上の、アドレス範囲が同一である場合には、対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとしてストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、対の両命令に係る、メモリ上の、アドレス範囲が部分的にのみ重複している場合には、対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備する。作動ステップでは、検出された対に係るプログラムを実行するＣＰＵに、該対に対して投機実行中止機構のＳＦＡ機構を作動させる。
【００５８】
好ましいメモリ・アクセス順序付け方法は、さらに、前述の対において、ストア命令のアドレス範囲は本来的にストアの必要なデータのみをストアするように設定されているのに対し、ロード命令のアドレス範囲は、本来的にロードの必要なデータと共にロードの不要なデータもロードするように、設定され、該ロード命令に基づいてデータをロードを実行するロード命令実行ステップと、本来的にロードの必要なデータは、ロード命令によりロードしたデータから抽出する抽出ステップと、を含む。例えば、プログラムは第１及び第２の処理に係る第１及び第２のプログラム部分を含み、第１及び第２の処理は、ストア処理部分、及び相手の処理でストアしたかもしれないデータをストア処理部分の実行後に観測する観測処理部分、及び該観測処理部分の観測結果に基づいて対応の処理へ分岐する分岐処理部分を含む。対におけるストア命令及びロード命令は、第１及び第２の処理におけるストア処理部分及び観測処理部分に含まれている。好ましくは、第１及び第２の処理は、それぞれオブジェクト管理方法のオブジェクトのロック解除に係る処理及びオブジェクト獲得に係る処理である。
【００５９】
本発明のロック管理方法を実行するコンピュータは、複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備する。各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する。本発明のロック管理方法によれば、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理する。本発明のロック管理方法は、第１のスレッドが保持している或るオブジェクトへのロックを第２のスレッドが獲得するオブジェクト獲得方法と、第１のスレッドが或るオブジェクトへのロックを解除するロック解除方法とを含む。オブジェクト獲得方法は、（ａ１）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、（ａ２）第１の種類のロックであることを示しているときには、競合ビットを立てるステップと、を含む。ロック解除方法は、（ｂ１）ロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、（ｂ２）或るオブジェクトのロックを保持しているスレッドが存在しないことを記憶領域に記憶するステップと、（ｂ３）ロックの種類を示すビットが第１の種類のロックであることを示しているときには、競合ビットが立っているか判断するステップと、（ｂ４）競合ビットが立っていないと判断されたときには終了するステップと、を含む。（ｂ２）における記憶に対応するストア命令Ｓと（ｂ３）におけるビットの読み出しに対応するロード命令Ｌとについて、投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定される。そして、該設定に基づいて（ｂ２）及び（ｂ３）のステップを実行する。
【００６０】
”第２の種類のロックに係る識別子”とは、発明の実施の形態では、各オブジェクトに対応付けられているモニターの識別子である。（ａ１）及び（ａ２）は、表４の第９０行及び第１００行にそれぞれ対応する。（ｂ１）、（ｂ２）、（ｂ３）及び（ｂ４）は表４の第２１０行、第２２０行、第２３０行及び第３００行にそれぞれ対応する。
【００６１】
好ましくは、ロック解除方法は、（ｂ５）競合ビットが立っていると判断されたときには、オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に第１のスレッドが移行するステップと、（ｂ６）待機しているスレッドへの通知操作を実行するステップと、（ｂ７）第１のスレッドが排他制御状態から脱出するステップと、をさらに含む。(ｂ５)、（ｂ６）及び（ｂ７）は、表４の第２６０行、第２７０行及び第２８０行に対応する。
【００６２】
第１の種類のロックとは、例えば、オブジェクトに対してロックを実施するスレッドの識別子を当該オブジェクトに対応して記憶することによりロック状態を管理するロック方式である。また、第２の種類のロックとは、例えばオブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である。
【００６３】
本発明のロック管理方法を実行するコンピュータは、複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備する。各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する。本発明のロック管理方法によれば、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又はオブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理する。本発明のロック管理方法は、（ｃ１）オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に第１のスレッドが移行するステップと、（ｃ２）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、（ｃ３）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているとき、競合ビットをセットするステップと、（ｃ４）前述（ｃ３）のステップの後、或るオブジェクトに対応して設けられた記憶領域の内容に基づいて第１の種類のロックを第１のスレッドが獲得できるか判断するステップと、（ｃ５）第１の種類のロックを第１のスレッドが獲得できるときには、或るオブジェクトに対応して設けられた記憶領域に第２の種類のロックを示すビット及び第２の種類のロックに係る識別子を記憶するステップと、を含む。第１のスレッドは或るオブジェクトに対して必要な処理を終了した後に排他的状態を脱出する。（ｃ３）における競合ビットのセットに対応するストア命令Ｓと（ｃ４）における記憶領域の内容の読み出しに対応するロード命令Ｌとについて、投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定されている。そして、該設定に基づいて（ｃ３）及び（ｃ４）のステップを実行する。
【００６４】
（ｃ１）、（ｃ２）、（ｃ３）、（ｃ４）及び（ｃ５）は表４の第７０行、第９０行、第１００行、第１１０行及び第１２０行にそれぞれ対応する。
【００６５】
好ましくは、ロック管理方法は、（ｃ６）第１の種類のロックを第１のスレッドが獲得できないときには、機構の待機状態に移行するステップ、（ｃ７）或るオブジェクトのロックのロックの種類を示すビットが第１の種類のロックであることを示していないとき、第１のスレッドは第２の種類のロックを獲得したとして排他的状態を脱出することなく処理を実施するステップ、（ｃ８）前述の（ｃ２）において或るオブジェクトのロックの種類を示すビットが第２の種類のロックであることを示しているとき、第１のスレッドは第２の種類のロックを獲得したとして排他的状態を脱出することなく処理を実施するステップ、を含む。をさらに含む。（ｃ６）は表４の第１４０行に対応する。（ｃ８）は、（ｃ７）と同様に、第１のスレッドが、表４の第７０行においてモニターへエンターし、第９０行〜第１４０行をすり抜けることに対応する。（ｃ７）における条件内容は「〜第１の種類のロックであることを示していないとき、〜」であるのに対し、（ｃ８）における条件内容は「〜が第２の種類のロックであることを示しているとき、〜」となっている。
【００６６】
好ましくは、ロック管理方法を実行するコンピュータは、複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備する。各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する。ロック管理方法によれば、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理する。ロック管理方法は、第１のスレッドが保持している或るオブジェクトへのロックを第２のスレッドが獲得するオブジェクト獲得方法と、第１のスレッドが或るオブジェクトへのロックを解除するロック解除方法とを含む。オブジェクト獲得方法は、（ａ１）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、（ａ２）第１の種類のロックであることを示しているときには、競合ビットを立てるステップと、を含む。ロック解除方法は、（ｂ１）ロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、（ｂ２）或るオブジェクトのロックを保持しているスレッドが存在しないことを記憶領域に記憶するステップと、（ｂ３）ロックの種類を示すビットが第１の種類のロックであることを示しているときには、競合ビットが立っているか判断するステップと、（ｂ４）競合ビットが立っていないと判断されたときには、或るオブジェクトへのロックを解除する以外の他の処理を実施せずにロック解除処理を終了するステップと、を含む。（ｂ２）における記憶に対応するストア命令Ｓと（ｂ３）におけるビットの読み出しに対応するロード命令Ｌとについて、投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定される。ロック解除方法は、（ｄ１）第１のスレッドが獲得している或るオブジェクトのロックが第２の種類のロックであるか判断するステップと、（ｄ２）第１のスレッドが獲得している或るオブジェクトのロックが第２の種類のロックであるとき、オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構における待機状態のスレッドが存在しているか判断するステップと、（ｄ３）他のスレッドが存在していない場合、ロックを保持しているスレッドが存在しないことを記憶領域に記憶するステップと、をさらに含む。（ｄ１）、（ｄ２）及び（ｄ３）は、表４の第２１０行、第３４０行及び第３６０行にそれぞれ対応する。
【００６７】
好ましいロック管理方法によれば、各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備する。投機実行中止機構は、対の両命令に係る、メモリ上の、アドレス範囲が同一である場合には、対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとしてストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、対の両命令に係る、メモリ上の、アドレス範囲が部分的にのみ重複している場合には、対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備する。そして、  ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲は、ＳＦＡ機構を作動させるように、設定され、該設定に基づいて（ｂ２）及び（ｂ３）のステップ、並びに（ｃ３）及び（ｃ４）のステップを実行する。
【００６８】
本発明のメモリ・アクセス順序付け装置が実装されるコンピュータは、複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備する。各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する。コンピュータのメモリ・アクセス順序付け装置は、メモリ・アクセスについて前後の関係で順序付けを必要とする、プログラム上で前後の記述順となっている、ストア命令及びロード命令は、そのアドレス範囲が重複部分をもつようにかつストア及びロードの必要なデータのアドレス範囲をそれぞれ含むように設定されて、プログラム上に配置されており、これらストア命令及びロード命令の対を各ＣＰＵにおいて検出させる検出手段と、検出された対に係るプログラムを実行するＣＰＵに、その投機実行中止機構を、検出した対に対して作動させる作動手段と、を含む。
【００６９】
好ましくは、メモリ・アクセス順序付け装置は、複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備する。各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備する。投機実行中止機構は、対の両命令に係る、メモリ上の、アドレス範囲が同一である場合には、対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとしてストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、対の両命令に係る、メモリ上の、アドレス範囲が部分的にのみ重複している場合には、対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備する。作動手段では、検出された対に係るプログラムを実行するＣＰＵに、該対に対して投機実行中止機構のＳＦＡ機構を作動させる。
【００７０】
好ましいメモリ・アクセス順序付け装置は、対において、ストア命令のアドレス範囲は本来的にストアの必要なデータのみをストアするように設定されているのに対し、ロード命令のアドレス範囲は、本来的にロードの必要なデータと共にロードの不要なデータもロードするように、設定され、該ロード命令に基づいてデータをロードを実行するロード命令実行手段と、本来的にロードの必要なデータは、ロード命令によりロードしたデータから抽出する抽出手段と、を含む。好ましくは、プログラムは第１及び第２の処理に係る第１及び第２のプログラム部分を含み、第１及び第２の処理は、ストア処理部分、及び相手の処理でストアしたかもしれないデータをストア処理部分の実行後に観測する観測処理部分、及び該観測処理部分の観測結果に基づいて対応の処理へ分岐する分岐処理部分を含み、対におけるストア命令及びロード命令は、第１及び第２の処理におけるストア処理部分及び観測処理部分に含まれている。例えば、第１及び第２の処理は、それぞれオブジェクト管理装置のオブジェクトのロック解除に係る処理及びオブジェクト獲得に係る処理である。
【００７１】
【発明の実施の形態】
以下、発明の実施の形態について図面を参照して説明する。
図４はコンピュータの概略構成図である。コンピュータ１０は、複数のＣＰＵ及びメインメモリを含むハードウエア１２と、ＯＳ（Operating System）１４、アプリケーション・プログラム２０を含む。ＯＳ１４は、アプリケーション・プログラム２０として動作する複数のスレッドを可能にする能力を有する。また、ＯＳ１４はキューロックに必要な機能も提供する。また、アプリケーション・プログラム２０は、例えば、ロック管理を実行するものであり、モニタ機能、ロック及びアンロック機能を含む。さらに、Ｊａｖａ言語のプログラムの実行に備えて、Ｊａｖａ ＶＭ（Virtual Machine）１８をＯＳ１４上に設け、さらにその上でアプレット又はアプリケーション・プログラム２０を実行する場合もある。アプレット又はアプリケーション・プログラム２０もマルチ・スレッドで実行され得る。Ｊａｖａ言語においては、Ｊａｖａ ＶＭ１８に、モニタ機能、本発明のロック及びアンロック機能が組み込まれる。なお、Ｊａｖａ ＶＭ１８はＯＳ１４の一部として組み込まれる場合もある。また、コンピュータ１０は補助記憶装置を有しない、いわゆるネットワークコンピュータ等でもよい。
【００７２】
図５は本発明におけるストア命令及びロード命令についてのプログラム上の順序付けの説明図である。本発明では、プログラム上の特定のストア命令及びロード命令の対は、メモリ・アクセスについても、図３（ａ）及び（ｂ）のような”ｆｅｎｃｅ”や”ｓｙｎｃ”を使用することなく、プログラム上の順序付け通りに暗に（ｉｍｐｌｉｃｉｔｌｙ）順序付けられる。
【００７３】
図６はＳＦ（Ｓｔｏｒｅ  Ｆｏｗａｒｄｉｎｇ：ストア・フォワーディング）の説明図である。ＣＰＵ３２は、ストア・バッファ３４、キャッシュ・ライン３６及びレジスタ（図示せず）を備え、プログラム３０のストア命令に従ってＣＰＵ３２のレジスタからメモリ３８へストアするデータは、ストア・バッファ３４及びキャッシュ・ライン３６を経由させるようにしている。また、プログラム３０のロード命令に従ってメモリ３８からＣＰＵ３２のレジスタへロードされるデータはキャッシュ・ライン３６を経由させるようにしている。なお、複数個のＣＰＵ３２を装備するコンピュータ１０では、ストア・バッファ３４及びキャッシュ・ライン３６は各ＣＰＵ３２に装備されるのに対し、メモリ３８は全部のＣＰＵ３２に共有される。プログラム３０では、ストア命令及びロード命令がその順番で記述されている。図６の例では、ストア命令によりデータをストアするメモリ３８のアドレス範囲と、ロード命令によりデータをロードするメモリ３８のアドレス範囲とが、同一のＡであると仮定している。このような場合では、ＣＰＵ３２は、プログラム３０のロード命令の投機実行を中止するとともに、プログラム３０のロード命令に対し、キャッシュ・ライン３６又はメモリ３８からデータをロードすることなく、プログラム３０のストア命令によりストア・バッファ３４に書き込まれているデータをプログラム３０へ送る。このようなストア命令及びロード命令間のデータの流れをＳＦと言う。
【００７４】
図７はＳＦＡ（Ｓｔｏｒｅ  Ｆｏｗａｒｄｉｎｇ  Ａｖｏｉｄｅｎｃｅ：ストア・フォワーディング・アボイダンス）の説明図である。図７の例では、ストア命令によりデータをストアするメモリ３８のアドレス範囲Ａと、ロード命令によりデータをロードするメモリ３８のアドレス範囲Ａ’とが、Ａ⊂Ａ’の関係であると仮定している。なお、ＳＦＡを実現させる要件は次の（ａ）及び（ｂ）の２個である。
（ａ）ＡとＡ’とが完全一致していないこと。
（ｂ）Ａ∩Ａ’が空集合でないこと。
これら２要件が具備された場合には、ＣＰＵ３２によるロード命令の投機実行は行われず、ＳＦＡが実行される。Ａ⊂Ａ’は要件（ａ）及び（ｂ）を満たしている。ＣＰＵ３２は、ロード命令について投機実行よりＳＦ及びＳＦＡを優先する。こうして、プログラム３０のストア命令によるアドレス範囲Ａのデータは、ストア・バッファ３４からキャッシュ・ライン３６へ書き込まれる。メモリ３８のデータは、キャッシュ・ライン３６のデータに対して、ＣＰＵ３２の作動中、一時的には相違していることもあるが、一致性が保証されている。ＣＰＵ３２によるデータ読み書き高速化のために、メモリ３８の一部のデータがキャッシュ・ライン３６にコピーされ、ＣＰＵ３２は、キャッシュ・ライン３６にデータが存在している限り、キャッシュ・ライン３６に対してデータを読み書きする。キャッシュ・ライン３６及びメモリ３８は、メモリ階層に属し、その内容はどのＣＰＵからも観測可能になっている。本発明では、メモリ・アクセスについて、プログラム上のストア命令及びロード命令の順序付け通りに順序付けられることを保証するため、かつ他のＣＰＵからもストア命令のデータを観測可能（ｖｉｓｉｂｌｅ）にするため、ＳＦＡを積極的に利用する。従来のコンピュータでは、ＳＦＡは、ＳＦを実行できないときに、止むを得ず生じるものであり、ＳＦＡに利用価値はなかった。
【００７５】
図８はオブジェクト・ヘッダ４６の構造とＳＦＡとの関係についての説明図である。図８の例では、オブジェクト・ヘッダ４６は３個のワードなら成る。１ワードは４バイトであり、このオブジェクト・ヘッダ４６のサイズは１２バイトである。ｆｌｃビット４８はオブジェクト・ヘッダ４６の１番目のワード存在し、ＴＩＤ５０（スレッドＩＤ）はオブジェクト・ヘッダ４６の３番目のワードに存在する。ＴＩＤ５０は典型的には１５ビットである。スレッドＡにおけるストア命令及びロード命令は、ＣＰＵが例えばIntel IA-32の場合では、それぞれ２バイトのmov命令によるstoreと、８バイトのfild命令によるloadで実現される。この実装ではfildはFPレジスタに値を持ち、そのままflcビットだけ検査ができないため、一旦fistp命令でメモリに書き戻す。SSE命令やSSE2命令が利用できれば、レジスタ上で直接flcビットを検査でき、ロード命令を効率よく実現できる。スレッドＡ及びＢにおけるコード上の記述順では、ストア命令がロード命令より先になっている。スレッドＡにおけるストア命令は、ＴＩＤ５０を０にするものであり、表４の第２２０行に対応する。また、スレッドＡにおいて抽出される（ｅｘｔｒａｃｔ）ｆｌｃビット４８は表４の第２３０行において使用されている。他方、スレッドＢにおけるストア命令は、ｆｌｃビット４８をセットするものであり、表４の第１００行に対応する。また、スレッドＢにおいて抽出される（ｅｘｔｒａｃｔ）ＴＩＤ５０は表４の第１１０行において使用されている。なお、表４の第１００行及び第１１０行は、tasukiロックのオブジェクト獲得処理のためのプログラム記述部分に存在し、また、表４の第２２０行及び第２３０行は、tasukiロックのロック解除（アンロック）処理のためのプログラム記述部分に存在する。なお、オブジェクト・ヘッダのデータの読み書き方向は、図の上から下へ、かつ同一行内では右から左へとなっている。スレッドＡ及びＢにおけるロード命令がＳＦＡを実現するものとなるために、所定のアドレス範囲としてのＳＦＡ領域（ｓｆａ  ａｒｅａ：図８でハッチング領域）が設定される。このｓｆａ  ａｒｅａは、ｆｌｃビットアドレス範囲及びｔｉｄのアドレス範囲を含んでおり、スレッドＡ及びＢにおいて、ストア命令とその後続のロード命令との実行においてＳＦＡを起こすための前述の要件（ａ）及び（ｂ）を満たすものとして、設定されている。なお、ロード命令によるデータの最大読み込みサイズは、ＣＰＵによって異なっており、典型的なＣＰＵでは、１６バイトである。スレッドＡでは、ロード命令によりレジスタにｓｆａ  ａｒｅａの内容をロードし、次に、ｓｆａ  ａｒｅａの内容からｆｌｃを抜き出す。スレッドＢでは、ロード命令によりレジスタにｓｆａ  ａｒｅａの内容をロードし、次に、ｓｆａ  ａｒｅａの内容からｉｄを抜き出す。こうして、ＳＦＡを利用することにより、プログラム上のストア命令及びロード命令の順序付け通りにストア命令及びロード命令による実際のメモリ・アクセスを制御できる。
【００７６】
図９はオブジェクト・ヘッダの別の構造とＳＦＡとの関係についての説明図である。図９のオブジェクト・ヘッダでは、ｔｉｄとｆｌｃビットとは、共にオブジェクト・ヘッダの３番目のワードに配置される。これに伴い、ｓｆａ  ａｒｅａのアドレス範囲は、この３番目のワードのアドレス範囲（４バイト）とされる。このｓｆａ  ａｒｅａも、図８の場合のｓｆａ  ａｒｅａと同様に、スレッドＡ及びＢにおいて、ストア命令とその後続のロード命令との実行においてＳＦＡを起こすための前述の要件（ａ）及び（ｂ）を満たすものとして、設定されている。各スレッドにおけるＳＦＡの実現により、各スレッド上のストア命令及びロード命令の順序付け通りにストア命令及びロード命令による実際のメモリ・アクセスが制御される。
【００７７】
図１０はＳＦＡを実施したＣＰＵのストアデータが他のＣＰＵから観測できる状況を説明する図である。第１及び第２のプログラム３０ａ，３０ｂは図８のスレッドＡ，Ｂにおける順序付けを確保される記述部分を示している。図１０では、第１及び第２のＣＰＵ３２ａ，３２ｂの２個のＣＰＵしか図示されていないが、コンピュータ１０は３個以上のＣＰＵを装備してもよい。ＣＰＵは、第１及び第２のプログラム３０ａ，３０ｂは、同一の構成となっており、ストア・ハッファ３４ａ，３４ｂ及びキャッシュ・ライン３６ａ，３６ｂを備えている。各ＣＰＵは、外部バス５４を介してキャッシュ・ライン３６を相互に接続されている。各ＣＰＵのキャッシュはキャッシュ整合プロトコルによって一貫性が保たれる。ここで、一貫性とは、例えば第１のプログラム３０ａにおいてストア・バッファ３４ａからのデータがキャッシュ・ライン３６ａに書き込まれると、以降、他の任意のＣＰＵとしての第２のＣＰＵ３２ｂが、自己のキャッシュ・ライン３６ｂにおいて、キャッシュ・ライン３６ａに書き込まれたデータと同一のアドレス範囲にアクセスすれば、第１のＣＰＵ３２ａがキャッシュ・ライン３６ａに書き込んだデータをキャッシュ・ライン３６ｂから読み出すことができると言う意味である。すなわち、第２のＣＰＵ３２ｂが古いキャッシュ・ライン３６ｂを持っていても，プロトコルによってそのラインは無効化される。図１０において、ｆ１〜ｆ４は、第１のＣＰＵ３２ａにおけるＳＦＡの実現により、第１のプログラム３０ａのストア命令によりストアしたデータとしてのＴＩＤが第２のプログラム３０ｂのロード命令において読み出すときのデータの流れを示している。第１のプログラム３０ａのストア命令によりストアされるＴＩＤは、ストア・バッファ３４ａに書き込まれ（ｆ１）、ＳＦＡによりキャッシュ・ライン３６ａに書き込まれ（ｆ２）、次に、第２のプログラム３０ｂにおけるロード命令に従って、キャッシュ・ライン３６ｂへ書き込まれ（ｆ３）、第２のＣＰＵ３２ｂ内のキャッシュ・ライン３６ｂ及びレジスタ（図示せず）を経てレジスタからからプログラム３０ｂに通知される（ｆ４）。
【００７８】
図１１はtasukiロックのtasuki制約を満たすためにＳＦＡを実現させるロック解除処理の部分のフローチャートである。なお、Ｓ６０、Ｓ６６及びＳ６８は表４の第２２０行、第２３０行及び第２５０行に対応する。オブジェクトのロック解除処理では、現在のロック状態が軽量（ｔｈｉｎ）ロックであると判明すると（表４の第２１０行）、ストア命令を使って、ｔｉｄに０を代入する（Ｓ６０）。次に、ロード命令を使って、ｓｆａ  ａｒｅａの内容をロードする（Ｓ６２）。Ｓ６０，Ｓ６２によりＳＦＡが実現する。ｆｌｃビットはｓｆａ  ａｒｅａの内容から抽出して求める（Ｓ６４）。ｆｌｃビットが”０”か”１”かを判定し、”０”であれば、すなわち該オブジェクトの獲得について競合状態でなかったならば、ロック解除処理を終了する。また、”１”であれば、すなわち、すなわち該オブジェクトの獲得について競合状態であったならば、オブジェクトに係るモニターへ入る（Ｓ６８）。
【００７９】
Pentium 4やPower 4など、高いクロックで動作し、out-of-orderの度合いが高いＣＰＵほど順序づけ命令のオーバーヘッドは高い（この傾向を調べる実験として、Javaの典型的なsynchronizedメソッドであるRandomクラスのnextIntメソッドを繰り返し実行するマイクロベンチマークを、IBM Java JITコンパイラを使ってIntel IA-32系マルチプロセッサ環境で実行した。１つは933MHzで動作するPentium III、もう１つはその1.6倍の1.5GHzで動作するPentium 4上での結果である。JITedコードでは、synchronizedメソッドに関して、lock cmpxchg命令（ロック確保時に必要）＋lock and命令（ロック解放時に必要）が行われている。 nextIntメソッドは適度な計算量を持つ（64ビットの乗算とシフト）にも関わらず、結果には順序づけ命令の影響が大きく出た。順序づけ命令の影響で、Pentium 4がPentium IIIより2.7倍遅い、クロック費を考慮すれば4.3倍遅い結果となった。）と予想され、ＳＦＡ利用によるメモリ・アクセスの順序付けの効果は高まる。比較ベースとしてthinロックを考える。thinロックはtasukiロックの原型ともいえる存在で、tasukiロック＝thinロック＋tasuki制約である。Pentium 4上でのRandom.nextマイクロベンチマークにおいて、tasuki制約のための順序づけ命令が原因で、tasukiロックの性能はthinロックの６５%（lockプレフィックス命令の場合、新しい命令であるmfence命令を使っても71%にしかならない。）にダウンしている。そのため、tasuki制約を導入してもどれだけthinロックの性能を維持できるかがポイントである。
【００８０】
メモリ・アクセスの順序付けのためにSFAを適用すると、SSE命令による実装では、完全にthinロックの性能を回復できた。こうして、マイクロプロセッサ環境においてもシングルプロセッサ環境と同様に、tasukiロックはthinロックと同等の性能でスピンウェイトの排除を達成できた。この改善はSPECjvm98ベンチマークでも大きな意味を持つ。SPECjvm98ベンチマークは複数のプログラムの性能を見るベンチマークであるが、mtrtプログラムだけが２スレッドの並列性を持つ。したがって２プロセッサで実行すれば、単純にmtrtプログラムの性能を２倍にできる。そのため最近のSPECjvm98ベンチマークの結果報告は、２プロセッサで計測したものが多い。しかし一方で、２プロセッサで計測すれば当然、synchronizedメソッドを頻繁に呼ぶプログラムは遅くなる。SFAを適用した結果、Pentium III上でdb 12%、javac 7.3%、jack 3.2%、geometric mean 2.4%向上した。これらの結果はあくまでも現在のIBM Java上でのfild/fistpによる次善の実装であり、fistpとflcビットのテストで無駄なSFAが起きてベストの性能が出せないでいる。したがって、実施例２で示した、TIDフィールドとflcビットが同一ワードにある実装では、より大きく改善できる能力を持つことに注意してほしい。
【００８１】
まとめとして本発明の構成に関して以下の事項を開示する。
（１)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータのメモリ・アクセス順序付け方法において、
メモリ・アクセスについて前後の関係で順序付けを必要とする、プログラム上で前後の記述順となっている、ストア命令及びロード命令は、そのアドレス範囲が重複部分をもつようにかつストア及びロードの必要なデータのアドレス範囲をそれぞれ含むように設定されて、プログラム上に配置されており、これらストア命令及びロード命令の対を各ＣＰＵにおいて検出させる検出ステップと、
検出された対に係るプログラムを実行するＣＰＵに、その投機実行中止機構を、検出した対に対して作動させる作動ステップと、
を含むメモリ・アクセス順序付け方法。
【００８２】
（２)：各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
投機実行中止機構は、対の両命令に係る、メモリ上の、アドレス範囲が同一である場合には、対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとしてストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、対の両命令に係る、メモリ上の、アドレス範囲が部分的にのみ重複している場合には、対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
作動ステップでは、検出された対に係るプログラムを実行するＣＰＵに、該対に対して投機実行中止機構のＳＦＡ機構を作動させる、
（１)記載のメモリ・アクセス順序付け方法。
（３)：対において、ストア命令のアドレス範囲は本来的にストアの必要なデータのみをストアするように設定されているのに対し、ロード命令のアドレス範囲は、本来的にロードの必要なデータと共にロードの不要なデータもロードするように、設定され、該ロード命令に基づいてデータをロードを実行するロード命令実行ステップと、
本来的にロードの必要なデータは、ロード命令によりロードしたデータから抽出する抽出ステップと、
を含む（１)又は（２）記載のメモリ・アクセス順序付け方法。
（４)：プログラムは第１及び第２の処理に係る第１及び第２のプログラム部分を含み、第１及び第２の処理は、ストア処理部分、及び相手の処理でストアしたかもしれないデータをストア処理部分の実行後に観測する観測処理部分、及び該観測処理部分の観測結果に基づいて対応の処理へ分岐する分岐処理部分を含み、対におけるストア命令及びロード命令は、第１及び第２の処理におけるストア処理部分及び観測処理部分に含まれている（１)〜（３）のいずれかに記載のメモリ・アクセス順序付け方法。
（５)：第１及び第２の処理は、それぞれオブジェクト管理方法のオブジェクトのロック解除に係る処理及びオブジェクト獲得に係る処理である（４)記載のメモリ・アクセス順序付け方法。
【００８３】
（６)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにより実行するロック管理方法であって、
ロック管理方法では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
さらに、ロック管理方法は、第１のスレッドが保持している或るオブジェクトへのロックを第２のスレッドが獲得するオブジェクト獲得方法と、第１のスレッドが或るオブジェクトへのロックを解除するロック解除方法とを含み、
オブジェクト獲得方法は、
（ａ１）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、
（ａ２）第１の種類のロックであることを示しているときには、競合ビットを立てるステップと、
を含み、
ロック解除方法は、
（ｂ１）ロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、
（ｂ２）或るオブジェクトのロックを保持しているスレッドが存在しないことを記憶領域に記憶するステップと、
（ｂ３）ロックの種類を示すビットが第１の種類のロックであることを示しているときには、競合ビットが立っているか判断するステップと、
（ｂ４）競合ビットが立っていないと判断されたときには終了するステップと、を含み、
（ｂ２）における記憶に対応するストア命令Ｓと（ｂ３）におけるビットの読み出しに対応するロード命令Ｌとについて、投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定され、
該設定に基づいて（ｂ２）及び（ｂ３）のステップを実行する、
ロック管理方法。
【００８４】
（７)：各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
投機実行中止機構は、対の両命令に係る、メモリ上の、アドレス範囲が同一である場合には、対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとしてストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、対の両命令に係る、メモリ上の、アドレス範囲が部分的にのみ重複している場合には、対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲は、ＳＦＡ機構を作動させるように、設定され、
該設定に基づいて（ｂ２）及び（ｂ３）のステップを実行する、
（６)記載のロック管理方法。
（８)：（ｂ２）における記憶に対応するストア命令Ｓは、或るオブジェクトのロックを保持しているスレッドが存在しないことが記憶される記憶領域に係るアドレス範囲Ａ１をアドレス範囲として設定され、
（ｂ３）におけるビットの読み出しに対応するロード命令Ｌは、該ビットに係るアドレス範囲を全部含むとともに、アドレス範囲Ａ１を少なくとも部分的に含むアドレス範囲Ａ２をアドレス範囲として設定され、
該設定に基づいて（ｂ２）及び（ｂ３）のステップを実行する、
（６)又は（７）記載のロック管理方法。
（９)：ロック解除方法は、
（ｂ５）競合ビットが立っていると判断されたときには、オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に第１のスレッドが移行するステップと、
（ｂ６）待機しているスレッドへの通知操作を実行するステップと、
（ｂ７）第１のスレッドが排他制御状態から脱出するステップと、
をさらに含む（６)〜（８）のいずれかに記載のロック管理方法。
【００８５】
（１０)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにより実行するロック管理方法であって、
ロック管理方法では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又はオブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
（ｃ１）オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に第１のスレッドが移行するステップと、
（ｃ２）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、
（ｃ３）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているとき、競合ビットをセットするステップと、
（ｃ４）前述の（ｃ３）のステップの後、或るオブジェクトに対応して設けられた記憶領域の内容に基づいて第１の種類のロックを第１のスレッドが獲得できるか判断するステップと、
（ｃ５）第１の種類のロックを第１のスレッドが獲得できるときには、或るオブジェクトに対応して設けられた記憶領域に第２の種類のロックを示すビット及び第２の種類のロックに係る識別子を記憶するステップと、
を含み、
第１のスレッドは或るオブジェクトに対して必要な処理を終了した後に排他的状態を脱出し、
（ｃ３）における競合ビットのセットに対応するストア命令Ｓと（ｃ４）における記憶領域の内容の読み出しに対応するロード命令Ｌとについて、投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定され、
該設定に基づいて（ｃ３）及び（ｃ４）のステップを実行する、
ロック管理方法。
【００８６】
（１１)：各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
投機実行中止機構は、対の両命令に係る、メモリ上の、アドレス範囲が同一である場合には、対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとしてストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、対の両命令に係る、メモリ上の、アドレス範囲が部分的にのみ重複している場合には、対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲は、ＳＦＡ機構を作動させるように、設定され、
該設定に基づいて（ｃ３）及び（ｃ４）のステップを実行する、
（１０)記載のロック管理方法。
（１２)：（ｃ３）における競合ビットのセットに対応するストア命令Ｓは、競合ビットに係るアドレス範囲Ａ１をアドレス範囲として設定され、
（ｃ４）における記憶領域の内容の読み出しに対応するロード命令Ｌは、記憶領域のアドレス範囲を全部含むとともに、アドレス範囲Ａ１を少なくとも部分的に含むアドレス範囲Ａ２をアドレス範囲として設定され、該設定に基づいて（ｃ３）及び（ｃ４）のステップを実行する、
（１０)又は（１１）記載のロック管理方法。
【００８７】
（１３)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータのメモリ・アクセス順序付け装置において、
メモリ・アクセスについて前後の関係で順序付けを必要とする、プログラム上で前後の記述順となっている、ストア命令及びロード命令は、そのアドレス範囲が重複部分をもつようにかつストア及びロードの必要なデータのアドレス範囲をそれぞれ含むように設定されて、プログラム上に配置されており、これらストア命令及びロード命令の対を各ＣＰＵにおいて検出させる検出手段と、
検出された対に係るプログラムを実行するＣＰＵに、その投機実行中止機構を、検出した対に対して作動させる作動手段と、
を含むメモリ・アクセス順序付け装置。
【００８８】
（１４)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
投機実行中止機構は、対の両命令に係る、メモリ上の、アドレス範囲が同一である場合には、対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとしてストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、対の両命令に係る、メモリ上の、アドレス範囲が部分的にのみ重複している場合には、対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
作動手段では、検出された対に係るプログラムを実行するＣＰＵに、該対に対して投機実行中止機構のＳＦＡ機構を作動させる、
（１３)記載のメモリ・アクセス順序付け装置。
（１５)：対において、ストア命令のアドレス範囲は本来的にストアの必要なデータのみをストアするように設定されているのに対し、ロード命令のアドレス範囲は、本来的にロードの必要なデータと共にロードの不要なデータもロードするように、設定され、該ロード命令に基づいてデータをロードを実行するロード命令実行手段と、
本来的にロードの必要なデータは、ロード命令によりロードしたデータから抽出する抽出手段と、
を含む（１３)又は（１４）記載のメモリ・アクセス順序付け装置。
（１６)：プログラムは第１及び第２の処理に係る第１及び第２のプログラム部分を含み、第１及び第２の処理は、ストア処理部分、及び相手の処理でストアしたかもしれないデータをストア処理部分の実行後に観測する観測処理部分、及び該観測処理部分の観測結果に基づいて対応の処理へ分岐する分岐処理部分を含み、
対におけるストア命令及びロード命令は、第１及び第２の処理におけるストア処理部分及び観測処理部分に含まれている（１３)〜（１５）のいずれかに記載のメモリ・アクセス順序付け装置。
（１７)：第１及び第２の処理は、それぞれオブジェクト管理装置のオブジェクトのロック解除に係る処理及びオブジェクト獲得に係る処理である（１６)記載のメモリ・アクセス順序付け装置。
【００８９】
（１８)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにより実行するロック管理装置であって、
ロック管理装置では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
さらに、ロック管理装置は、第１のスレッドが保持している或るオブジェクトへのロックを第２のスレッドが獲得するオブジェクト獲得装置と、第１のスレッドが或るオブジェクトへのロックを解除するロック解除装置とを含み、
オブジェクト獲得装置は、
（ａ１）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているか判断する手段と、
（ａ２）第１の種類のロックであることを示しているときには、競合ビットを立てる手段と、
を含み、
ロック解除装置は、
（ｂ１）ロックの種類を示すビットが第１の種類のロックであることを示しているか判断する手段と、
（ｂ２）或るオブジェクトのロックを保持しているスレッドが存在しないことを記憶領域に記憶する手段と、
（ｂ３）ロックの種類を示すビットが第１の種類のロックであることを示しているときには、競合ビットが立っているか判断する手段と、
（ｂ４）競合ビットが立っていないと判断されたときには終了する手段と、
を含み、
（ｂ２）における記憶に対応するストア命令Ｓと（ｂ３）におけるビットの読み出しに対応するロード命令Ｌとについて、投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定され、
該設定に基づいた処理を（ｂ２）及び（ｂ３）の手段が実施する、
ロック管理装置。
（１９)：各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
投機実行中止機構は、対の両命令に係る、メモリ上の、アドレス範囲が同一である場合には、対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとしてストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、対の両命令に係る、メモリ上の、アドレス範囲が部分的にのみ重複している場合には、対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲は、ＳＦＡ機構を作動させるように、設定され、
該設定に基づいた処理を（ｂ２）及び（ｂ３）の手段が実施する、
（１８)記載のロック管理装置。
（２０)：（ｂ２）における記憶に対応するストア命令Ｓは、或るオブジェクトのロックを保持しているスレッドが存在しないことが記憶される記憶領域に係るアドレス範囲Ａ１をアドレス範囲として設定され、
（ｂ３）におけるビットの読み出しに対応するロード命令Ｌは、該ビットに係るアドレス範囲を全部含むとともに、アドレス範囲Ａ１を少なくとも部分的に含むアドレス範囲Ａ２をアドレス範囲として設定され、
該設定に基づいた処理を（ｂ２）及び（ｂ３）の手段が実施する、
（１８)又は（１９）記載のロック管理装置。
（２１)：ロック解除装置は、
（ｂ５）競合ビットが立っていると判断されたときには、オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に第１のスレッドが移行する手段と、
（ｂ６）待機しているスレッドへの通知操作を実行する手段と、
（ｂ７）第１のスレッドが排他制御状態から脱出する手段と、
をさらに含む（１８)〜（２０）のいずれかに記載のロック管理装置。
【００９０】
（２２)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにより実行するロック管理装置であって、
ロック管理装置では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又はオブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
（ｃ１）オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に第１のスレッドが移行する手段と、
（ｃ２）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているか判断する手段と、
（ｃ３）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているとき、競合ビットをセットする手段と、
（ｃ４）前述の（ｃ３）の手段の後、或るオブジェクトに対応して設けられた記憶領域の内容に基づいて第１の種類のロックを第１のスレッドが獲得できるか判断する手段と、
（ｃ５）第１の種類のロックを第１のスレッドが獲得できるときには、或るオブジェクトに対応して設けられた記憶領域に第２の種類のロックを示すビット及び第２の種類のロックに係る識別子を記憶する手段と、
を含み、
第１のスレッドは或るオブジェクトに対して必要な処理を終了した後に排他的状態を脱出し、
（ｃ３）における競合ビットのセットに対応するストア命令Ｓと（ｃ４）における記憶領域の内容の読み出しに対応するロード命令Ｌとについて、投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定され、
該設定に基づいた処理を（ｃ３）及び（ｃ４）の手段が実施する、
ロック管理装置。
【００９１】
（２３)：各ＣＰＵは、プログラムのストア命令に対してデータをメモリへ書き込むためのストア・バッファを装備し、
投機実行中止機構は、対の両命令に係る、メモリ上の、アドレス範囲が同一である場合には、対のロード命令の投機実行を中止するとともに、該対のストア命令に基づいてストア・バッファに書き込まれたデータＡをデータＢとしてストア・バッファからプログラムへ通知するストア・フォワーディング（ＳＦ）機構と、対の両命令に係る、メモリ上の、アドレス範囲が部分的にのみ重複している場合には、対のロード命令の投機実行を中止するとともに、ＳＦの代わりに、ストア・バッファのデータＡをメモリ階層にストアしてから、対のロード命令に基づいてメモリ階層のデータＢをプログラムへ通知するストア・フォワーディング・アボイダンス（ＳＦＡ）機構とを装備し、
ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲は、ＳＦＡ機構を作動させるように、設定され、
該設定に基づいた処理を（ｃ３）及び（ｃ４）の手段が実施する、
（２２)記載のロック管理装置。
【００９２】
（２４)：（ｃ３）における競合ビットのセットに対応するストア命令Ｓは、競合ビットに係るアドレス範囲Ａ１をアドレス範囲として設定され、
（ｃ４）における記憶領域の内容の読み出しに対応するロード命令Ｌは、記憶領域のアドレス範囲を全部含むとともに、アドレス範囲Ａ１を少なくとも部分的に含むアドレス範囲Ａ２をアドレス範囲として設定され、
該設定に基づいた処理を（ｃ３）及び（ｃ４）の手段が実施する、
（２２)又は（２３）記載のロック管理装置。
【００９３】
（２５)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータのメモリ・アクセス順序付け方法において、
メモリ・アクセスについて前後の関係で順序付けを必要とする、プログラム上で前後の記述順となっている、ストア命令及びロード命令は、そのアドレス範囲が重複部分をもつようにかつストア及びロードの必要なデータのアドレス範囲をそれぞれ含むように設定されて、プログラム上に配置されており、これらストア命令及びロード命令の対を各ＣＰＵにおいて検出させる検出ステップと、
検出された対に係るプログラムを実行するＣＰＵに、その投機実行中止機構を、検出した対に対して作動させる作動ステップと、
を含むメモリ・アクセス順序付け方法の各ステップをコンピュータに実行させるためのプログラム。
（２６)：（２５)記載のプログラムを記録した記録媒体。
【００９４】
（２７)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにより実行するロック管理方法であって、
ロック管理方法では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
さらに、ロック管理方法は、第１のスレッドが保持している或るオブジェクトへのロックを第２のスレッドが獲得するオブジェクト獲得方法と、第１のスレッドが或るオブジェクトへのロックを解除するロック解除方法とを含み、
オブジェクト獲得方法は、
（ａ１）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、
（ａ２）第１の種類のロックであることを示しているときには、競合ビットを立てるステップと、
を含み、
ロック解除方法は、
（ｂ１）ロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、
（ｂ２）或るオブジェクトのロックを保持しているスレッドが存在しないことを記憶領域に記憶するステップと、
（ｂ３）ロックの種類を示すビットが第１の種類のロックであることを示しているときには、競合ビットが立っているか判断するステップと、
（ｂ４）競合ビットが立っていないと判断されたときには終了するステップと、を含み、
（ｂ２）における記憶に対応するストア命令Ｓと（ｂ３）におけるビットの読み出しに対応するロード命令Ｌとについて、投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定され、
該設定に基づいて（ｂ２）及び（ｂ３）のステップを実行する、
ロック管理方法の各ステップをコンピュータに実行させるためのプログラム。
（２８)：（２７)記載のプログラムを記録した記録媒体。
【００９５】
（２９)：複数のＣＰＵとこれら複数のＣＰＵにより共有されるメモリとを装備し、
各ＣＰＵは、それが実行するプログラムにおいて記述順でそれぞれ前及び後ろの関係となっているストア命令及びロード命令の対について、該対の両命令に係る、メモリ上の、アドレス範囲が重複部分をもつ場合には、ロード命令の投機実行を中止するとともに、該ロード命令の実行前に、ストア命令に係るデータが他のＣＰＵから観測可能にし得る投機実行中止機構を装備する、
コンピュータにより実行するロック管理方法であって、
ロック管理方法では、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビットと第１の種類のロックに対応してロックを獲得したスレッドの識別子又はオブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である第２の種類のロックに係る識別子とを記憶するフィールドを持つことによりオブジェクトへのロックを管理し、
（ｃ１）オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に第１のスレッドが移行するステップと、
（ｃ２）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、
（ｃ３）或るオブジェクトのロックの種類を示すビットが第１の種類のロックであることを示しているとき、競合ビットをセットするステップと、
（ｃ４）前述の（ｃ３）のステップの後、或るオブジェクトに対応して設けられた記憶領域の内容に基づいて第１の種類のロックを第１のスレッドが獲得できるか判断するステップと、
（ｃ５）第１の種類のロックを第１のスレッドが獲得できるときには、或るオブジェクトに対応して設けられた記憶領域に第２の種類のロックを示すビット及び第２の種類のロックに係る識別子を記憶するステップと、
を含み、
第１のスレッドは或るオブジェクトに対して必要な処理を終了した後に排他的状態を脱出し、
（ｃ３）における競合ビットのセットに対応するストア命令Ｓと（ｃ４）における記憶領域の内容の読み出しに対応するロード命令Ｌとについて、投機実行中止機構が作動するように、ストア命令Ｓ及びロード命令Ｌに係る、メモリ上の、アドレス範囲が設定され、
該設定に基づいて（ｃ３）及び（ｃ４）のステップを実行する、
ロック管理方法の各ステップをコンピュータに実行させるためのプログラム。
（３０)：（２９)記載のプログラムを記録した記録媒体。
【００９６】
【発明の効果】
このように、高速性に問題のある明示的な命令を使用することなく、メモリ・アクセスについてのストア命令及びロード命令の順序付けを保証することができる。
【図面の簡単な説明】
【図１】本発明の処理が実施されるコンピュータの一例を示す図である。
【図２】モードの遷移、並びに各モードにおけるロック用フィールド（ＦＡＴ＿ＬＯＣＫビットを含む）及び競合ビットの状態を説明するための図である。なお、（１）はロックなし、（２）は軽量ロックで競合なし、（３）は軽量ロックで競合あり、（４）は重量ロックの状態を示す。
【図３】各スレッドにおけるストア命令及びロード命令の順序付けを保証する措置の説明図である。
【図４】コンピュータの概略構成図である。
【図５】本発明におけるストア命令及びロード命令についてのプログラム上の順序付けの説明図である。
【図６】ＳＦの説明図である。
【図７】ＳＦＡの説明図である。
【図８】オブジェクト・ヘッダの構造とＳＦＡとの関係についての説明図である。
【図９】オブジェクト・ヘッダの別の構造とＳＦＡとの関係についての説明図である。
【図１０】ＳＦＡを実施したＣＰＵのストアデータが他のＣＰＵから観測できる状況を説明する図である。
【図１１】tasukiロックのtasuki制約を満たすためにＳＦＡを実現させるロック解除処理の部分のフローチャートである。
【符号の説明】
１０    コンピュータ
１６    アプリケーション・プログラム
３０    プログラム
３２    ＣＰＵ
３４    ストア・バッファ
３６    キャッシュ・ライン
３８    メモリ
【図１】
0003798726.tif 000002
【図２】
0003798726.tif 000003
【図３】
0003798726.tif 000004
【図４】
0003798726.tif 000005
【図５】
0003798726.tif 000006
【図６】
0003798726.tif 000007
【図７】
0003798726.tif 000008
【図８】
0003798726.tif 000009
【図９】
0003798726.tif 000010
【図１０】
0003798726.tif 000011
【図１１】
0003798726.tif 000012