(57)【特許請求の範囲】
【請求項１】
コンピュータプロセッサ（１１０）であって、
前記コンピュータプロセッサで現在実行されているプロセスまたはスレッドによってロックされているコンピュータリソースを識別する値のうち少なくとも一部の値を保持するための１つ或いはそれ以上のレジスタＲ１（LOCKADDR）であって、前記コンピュータプロセッサにより現在実行されており、コンピュータリソースに対してロックを保持できるプロセスまたはスレッドによってロック処理が実行される場合にのみ、前記各レジスタＲ１がロック処理動作により変更可能である、該レジスタＲ１と、
コンピュータリソースをロックするためのロック処理動作、コンピュータリソースをアンロックするためのアンロック処理動作或いはロック処理及びアンロック処理動作の両方を実行するための回路部品であって、前記回路部品がコンピュータリソースを識別する値Ｖ１を受け取るための回路部分であり、また前記レジスタＲ１が、前記コンピュータプロセッサにより現在実行されているプロセスまたはスレッドにより前記リソースがロックされていることを指示する前記値Ｖ１を保持するか否かを判定するための回路部分である、該回路部品とを備えることを特徴とするコンピュータプロセッサ。
【請求項２】
前記レジスタＲ１が、前記コンピュータプロセッサの命令実行ユニット（１３６）の一部であることを特徴とする請求項１に記載のコンピュータプロセッサ。
【請求項３】
前記レジスタＲ１により識別されるようなロックされているコンピュータリソースに関連するカウント値を表す値を保持するための１つ或いはそれ以上のレジスタＲ２（LOCKCOUNT）をさらに備え、前記各カウント値が、リソースに対して発行されたが、対応するアンロック命令が発行されなかったロック命令のカウント値であり、前記ロック処理或いはアンロック処理動作の少なくとも１つにおいて、前記回路部品が、前記レジスタＲ１が前記リソースがロックされることを指示する前記値Ｖ１を保持する場合にレジスタＲ２を変更することを特徴とする請求項１或いは２に記載のコンピュータプロセッサ。
【請求項４】
前記レジスタＲ２が、前記コンピュータプロセッサの命令実行ユニット（１３６）の一部であることを特徴とする請求項３に記載のコンピュータプロセッサ。
【請求項５】
前記各レジスタＲ２が対応する所定のレジスタＲ１と関連するカウント値を保持することを特徴とする請求項３或いは４に記載のコンピュータプロセッサ。
【請求項６】
前記各レジスタＲ１のために、前記対応するレジスタＲ１の値により識別されるリソースに対するロックを保持する実行可能なプロセスまたはスレッドを識別するためのレジスタＲ３（THREAD_ID）をさらに備え、
前記レジスタＲ１が前記値Ｖ１を保持するか否かを判定する前記回路部品が、前記コンピュータプロセッサにより現在実行されているプロセスまたはスレッドを識別する任意のレジスタＲ３のために、前記対応するレジスタＲ１が前記値Ｖ１を保持するか否かを判定する回路部品を備えることを特徴とする請求項１乃至５のいずれか一項に記載のコンピュータプロセッサ。
【請求項７】
現在実行されているプロセスまたはスレッドによりロックされるようなリソースを識別する値を格納するような１つ或いはそれ以上のロック処理レジスタＲ１を備えるコンピュータプロセッサによってコンピュータリソースをロック及びアンロックする方法であって、
前記コンピュータプロセッサによって、１つのプロセスまたはスレッドから別のプロセスまたはスレッドに切替える過程と、
前記プロセスまたはスレッドの切替えの際に、前記１つ或いはそれ以上のレジスタＲ１に、前記別のプロセスまたはスレッドによってロックされるようなリソースを識別する値をロードする過程とを有することを特徴とする方法。
【請求項８】
現在実行されているプロセスまたはスレッドによりロックされているリソースを識別する値を格納するような１つ或いはそれ以上のロック処理レジスタＲ１と、前記各レジスタＲ１に対して対応するレジスタＲ２とを備え、前記レジスタＲ２が、前記対応するレジスタＲ１により識別されるリソースに関連するような対応するアンロック命令が発行されていないロック命令のカウント値を保持するようなコンピュータプロセッサによってコンピュータリソースをロック及びアンロックする方法であって、
前記コンピュータプロセッサによって、１つのプロセスまたはスレッドから別のプロセスまたはスレッドに切替える過程と、
前記プロセスまたはスレッドの切替えの際に、前記１つ或いはそれ以上のレジスタＲ１に、前記別のプロセスまたはスレッドによってロックされるようなリソースを識別する値をロードする過程と、
前記プロセスまたはスレッドの切替えの際に、前記各レジスタＲ２に、前記対応するレジスタＲ１にロードされている値に対応するような前記別のプロセスまたはスレッドに関連しているカウント値をロードする過程とを有することを特徴とする方法。
【請求項９】
コンピュータリソースをロック及びアンロックするシステムであって、前記システムが、
コンピュータオブジェクトデータの一部であって２バイト境界に格納されているような前記一部のアドレスを識別する情報を格納するためのビットと前記オブジェクトデータの前記一部の前記アドレスを格納するためには用いられないビットとからなる大きさのコンピュータアドレスを有するフィールド（２２０Ｈ）が含まれる前記オブジェクトデータ（２２０）を格納するような記憶手段であって、前記記憶手段が、前記オブジェクトデータにアクセスするための１つ或いはそれ以上のコンピュータ命令を格納し、前記オブジェクトデータの前記一部の前記アドレスを格納するためには用いられない前記フィールドの１つ或いはそれ以上のビット（Ｌ）が、前記オブジェクトがロックされるか否かを示すための前記コンピュータ命令により用いられるような前記記憶手段と、
前記記憶手段にアクセスしかつ前記コンピュータ命令を実行するべく動作可能なコンピュータプロセッサとを有することを特徴とするシステム。
【請求項１０】
前記オブジェクトデータの前記一部が、４バイト境界に格納されるための部分であり、
また前記フィールドが、前記オブジェクトデータの前記部分の前記アドレスを格納するためには用いられない２つのビット（Ｗ、Ｌ）を有し、
さらに前記オブジェクトデータの前記一部の前記アドレスを格納するためには用いられない前記フィールドの前記１つ或いはそれ以上のビットが、前記コンピュータプロセッサで現在実行されているプロセスまたはスレッドが前記オブジェクトに対するロックを獲得することを要求するか否かを示すための前記コンピュータ命令により用いられるビット（Ｗ）を含むことを特徴とする請求項９に記載のシステム。
【発明の詳細な説明】
【０００１】
［発明の背景］
【０００２】
本発明はコンピュータリソースのロック処理に関連する。
【０００３】
コンピュータプロセス或いはスレッドのような種々のコンピュータエンティティがコンピュータリソース（例えばデータ、コード或いはハードウエアの部品）を共有する際に、コンピュータエンティティの１つが暫くの間リソースをロックし、他のコンピュータエンティティによるある種類のリソースへのアクセスを防ぐようにすることが好ましい。例えば、２つ或いはそれ以上のスレッドがコンピュータデータを共有し、１つのスレッドがデータを変更し始めているが終了していない場合に、別のスレッドがデータにアクセスするなら、他のスレッドがそのデータから不正確な情報を取得するか、並びにまたそのデータが２つのスレッドにより汚染されることもある。また１つのスレッドがクリティカルコード部分の実行を開始しているが終了していない場合に、他のスレッドが同じコード部分を実行し始めるなら、例えば、クリティカルコード部分がデータ領域、ハードウエアコントローラ或いはいくつかの他のコンピュータリソースの状態を変更していない場合に実行エラーが生じることがある。それゆえロック処理技術により、コンピュータエンティティがコンピュータリソースをロックしている。
【０００４】
コンピュータリソースをロック処理するための高速化技術を実現することが望ましい。
［概要］
【０００５】
本発明は多くの頻繁に生じる状況において、コンピュータリソースのロック処理及びアンロック処理を高速化する方法及び回路を実現する。詳細には、ある実施例では典型的には、ロックに対する競合が生じない（すなわちそのロックが別のコンピュータエンティティにより保持されていない）場合にロック処理が高速化される。また典型的には、同じコンピュータエンティティ、例えば同じスレッドが、そのスレッドがロックを解除する前にその同じロックにおいて多数のロック操作を実行する場合に、ロック処理操作は高速化される。スレッドが再帰的コードを実行する場合、そのロックが解除される前に多数のロック操作が生じるようになる。
【０００６】
いくつかの実施例では、以下のようにして上記利点が達成される。コンピュータプロセッサはいくつかのレジスタ対（LOCKADDR、LOCKCOUNT）を備える。各LOCKADDRレジスタは、コンピュータリソースに対するロックを識別する値を保持する。いくつかの実施例では、この値はロックされるオブジェクトへの参照値である。このように、いくつかの実施例ではその値はロックされるオブジェクトのアドレスである。対応するLOCKCOUNTレジスタは、LOCKADDRレジスタにより識別されたロックに関連するロック命令のカウント値を保持する。スレッドが、LOCKADDRレジスタにより識別されたロックに対するロック命令を発行する際に、コンピュータプロセッサは対応するLOCKCOUNTレジスタをインクリメントする。スレッドがアンロック命令を発行する際に、コンピュータプロセッサは対応するLOCKCOUNTレジスタをデクリメントする。
【０００７】
いくつかの実施例では、プロセッサは、Java仮想マシンのロック及びアンロック命令を実行するのに適している。Java仮想マシンは、例えばT.Lindholm,F.Yellinによる「The JavaTM Virtual Machine Specification」に記載される。Java仮想マシンでは、各オブジェクトはそのオブジェクトに関連するモニタを備える。スレッドがロック命令「monitorenter」を実行する際に、対応するモニタに関連するカウンタがインクリメントされる。スレッドがアンロック命令「monitorexit」を実行する際に、カウンタはデクリメントされる。いくつかの実施例では、そのカウンタはLOCKCOUNTレジスタを用いて実装される。
【０００８】
いくつかの実施例では、LOCKCOUNTレジスタは省略され、あるリソースに対するロックは、そのリソースに対して発行された任意のアンロック命令において解除される。
【０００９】
いくつかの実施例では、各オブジェクトはクラス構造へのポインタであるヘッダを備える。クラス構造は４バイト境界上に位置合わせされ、それゆえそのポインタの２つのＬＳＢは０であり、ヘッダに格納される必要はない。代わりにヘッダの２つのＬＳＢを用いて、（１）そのオブジェクトがロックされるか否かを示す「LOCK」ビット及び（２）そのオブジェクトに対するロックを取得するためにスレッドが待機しているか否かを示す「WANT」ビットを格納する。
【００１０】
本発明の他の特徴及び利点が以下に記載される。本発明は添付の請求の範囲により画定される。
【図面の簡単な説明】
【００１１】
第１図は、本発明によるプロセッサを備えるコンピュータシステムのブロック図である。
【００１２】
第２図は、第１図のプロセッサにおいてロック処理操作を行うために用いられるレジスタ及び第１図のシステムのメモリ内の関連するデータ構造を示すブロック図である。
【００１３】
第３図は、第１図のメモリ内のデータ構造を示すブロック図である。
【００１４】
第４図は、本発明によるプロセッサにおけるロック処理操作に用いられるレジスタを示すブロック図である。
［好適な実施例の説明］
【００１５】
第１図は、ロック処理回路を備えるコンピュータシステムのブロック図である。プロセッサ１１０はバス１３０によりメモリ１２０に接続される。プロセッサ１１０は、メモリ１２０から呼び出された命令を実行する実行ユニット１３６を備える。実行ユニット１３６は、LOCKADDR,LOCKCOUNTを付されたレジスタ１４４を備える。これらのレジスタは、以下に記載するようなオブジェクトロック処理の場台に用いられる。
【００１６】
バス１３０は、Ｉ／Ｏバス及びプロセッサ１１０のメモリインターフエースユニット１５０に接続される。プロセッサ１１０がメモリ１２０から命令を読み出す際に、インターフェースユニット１５０がその命令を命令キャッシュ１５６に書き込む。その後その命令はデコードユニット１６０によりデコードされる。デコードユニット１６０はコントロール信号を実行コントロール及びマイクロコードユニット１６６に送出する。ユニット１６６はコントロール信号を実行ユニット１３６と交換する。またデコードユニット１６０はコントロール信号をスタックキャッシュ及びスタックキャッシュコントロールユニット１７０（以下では「スタックキャッシュ」と呼ばれる）にも送出する。スタックキャッシュ１７０はコントロール及びデータ信号を実行ユニット及びデータキャッシュユニット１８０と交換する。キャッシュユニット１７０及び１８０は、インターフェース１５０及びバス１３０を介してメモリ１２０とデータを交換する。実行ユニット１３６は命令キャッシュ１５６、スタックキャッシュ１７０及びデータキャッシュ１８０をフラッシュすることができる。
【００１７】
第２図は、レジスタ１４４及びメモリ１２０内の対応するオブジェクトの１つを示す。レジスタ１４４は、LOCKADDRO／LOCKCOUNTOからLOCKADDR３／LOCKCOUNT３を付された４つのレジスタ対を備える。各LOCKADDRレジスタは、ロックされるオブジェクトのアドレスを保持する。この実施例では各アドレスは３２ビット長であるため、各LOCKADDRレジスタは３２ビット長である。しかしながらいくつかの実施例では各オブジェクトは４バイト境界上で始まる。それゆえその実施例ではオブジェクトのアドレスの２つの最下位ビットは０であり、レジスタLOCKADDRから省略される。そのような実施例では、各レジスタLOCKADDRは３０ビット長である。
【００１８】
LOCKADDRレジスタが０を含む場合、これはレジスタ対が未使用であることを意味する。
【００１９】
各レジスタ対では、LOCKCOUNTレジスタが、そのオブジェクトに対するロック命令のカウント値を保持し、そのオブジェクトのアドレスが対応するLOCKADDRレジスタに保持される。LOCKCOUNTレジスタは、対応するアンロック命令が発行されていないロック命令の数を保持する。LOCKCOUNTレジスタはそのオブジェクトに対する各ロック命令時にインクリメントされ、各アンロック命令時にデクリメントされる。そのロックは実際に、LOCKCOUNTレジスタが０までデクリメントされる場合にのみ解除される（しかしながらいくつかの実施例では、以下に記載するように、LOCKCOUNTレジスタはロックカウントの一部のみを保持する。そのロックは、全ロックカウントが０までデクリメントされる場合に解除される）。いくつかの実施例では、各LOCKCOUNTレジスタは８ビット長であり、０〜２５５の数を保持する。
【００２０】
多数のロック命令にアンロック命令が介在しないのは、再帰的コードによるものである。LOCKCOUNTレジスタが、そのオブジェクトに対するロック及びアンロック命令の正味のカウント（すなわち、そのオブジェクトに対するロック命令の数とアンロック命令の数との差）を保持するため、ソフトウエアプログラムは、各アンロック命令前に検査を行い、そのロックに対する要求が満了するまで、そのスレッドのいくつかの他の部分によりそのオブジェクトがロックされたか否かを、それゆえオブジェクトのロックが保持されるべきか否かを判定する必要性を軽減される。
【００２１】
いくつかの実施例では、レジスタ１４４は１つのスレッド或いは１つのコンピュータプロセスのみに対するロックアドレス及びカウントを保持する。プロセッサ１１０が異なるスロット或いはプロセスに切り替わる際に、レジスタ１４４は、実行されるはずの新規のスレッド或いはプロセスに対するロックデータ（ロックアドレス及びカウント）をロードされる。
【００２２】
第２図は、アドレスがLOCKADDRレジスタ（第２図のレジスタLOCKADDR３）に格納されるオブジェクトを示す。第２図では、そのオブジェクトはメモリ１２０に格納される。しかしながらオブジェクトの全部或いは一部が、データキャッシュ１８０内に格納されることもできる。この説明全体を通して、メモリ１２２にデータ或いは命令を格納することを説明する場合、他に説明がなければ、データ或いは命令はデータキャッシュ１８０、スタックキャッシュ１７０或いは命令キャッシュ１５６に格納できることは理解されたい。
【００２３】
第２図に示されるように、レジスタLOCKADDR３のアドレスは、オブジェクト構造２２０へのポインタである。オブジェクト構造２２０はヘッダ２２０Ｈで開始する。ヘッダ２２０Ｈに、他のデータ（図示せず）が後続する。ヘッダ２２０Ｈは、そのオブジェクトを記載するクラス構造２３０へのポインタを備える。クラス構造２３０は４バイト境界に位置合わせされる。その結果として、さらに全てのアドレスが、上記バイトより大きいアドレスバイトを有する各連続バイトを備えるバイトアドレスであるため、クラス構造アドレスの２つのＬＳＢは０である。これら０のＬＳＢはヘッダ２２０Ｈに格納されない。それゆえヘッダはアドレス記憶に用いられない２つのビットを有する。これらのビット（ヘッダＬＳＢＯ及び１）は、オブジエクトロック処理の場合に用いられる。ビット０は、Ｌビット或いはLOCKビットとも呼ばれ、オブジェクトがロックされる際に１に設定される。ビット１は、Ｗ或いはWANTビットとも呼ばれ、スレッドが、オブジェクト２２０に対するロックを捕捉するための待機を阻止される際に１に設定される。
【００２４】
本説明の最後（請求の範囲の前）における付録Ａ及びＢは、プロセッサ１１０の一実施例においてロック及びアンロック命令を実行する回路に対する疑似コードを含む。その回路は実行ユニット１３６並びにまた実行コントロール及びマイクロコードユニット１６６の一部である。付録Ａ及びＢの疑似コード言語はハードウエア記述言語Verilog（登録商標）に類似であり、それは例えばD.E.Thomas,J.P.Moorbyによる「The Verilog Hardware Description Language」（１９９１）に記載されており、ここで参照して本明細書の一部としている。疑似コードは容易にVerilogに変換されることができ、対応する回路は当分野で周知の方法を用いて実装されることができる。
【００２５】
付録Ａはロック命令に対する疑似コードを示す。付録Ａのステップ１−０から１−３ではそれぞれ、対応するレジスタLOCKADDR０からLOCKADDR３までの内容が、ロックされるのオブジェクトのアドレスと比較される。一致する場合、対応するレジスタLOCKCOUNTがインクリメントされ（ステップ１−０ａ、１−１ａ、１−２ａ、１−３ａ）、０と比較される（ステップ１−０ｂ、１−１ｂ、１−２ｂ、１−３ｂ）。インクリメント後にLOCKCOUNTレジスタが０になる場合、オーバーフローが発生しており、トラップLockCountOverflowIncrementTrapが生成される。あるトラップの発生により、その命令の実行が終了される。そのトラップがイネーブルされる場合には、プロセッサ１１０はそのトラップに対して規定されるトラップハンドラの実行を開始する。トラップハンドラはコンピュータプログラムである。
【００２６】
いくつかの実施例では、LockCountOverflowIncrementTrapに対するトラップハンドラは、LOCKCOUNTレジスタより大きいロックカウンタmLOCKCOUNT（第３図）を保持する。より詳細にはいくつかの実施例では、オペレーティングシステムが、メモリ１２０のテーブル３１０を用いて、ロックされたオブジェクトのトラックを保持する。個別のテーブル３１０は各スレッドに対して保持される。テーブル３１０は、あるスレッドが作成される際に、そのスレッドに対して作成され、テーブル３１０は、対応するスレッドが消失する際に、割当て解除される。
【００２７】
各テーブル３１０はいくつかのエントリ（mLOCKADDR,mLOCKCOUNT）を備える。各エントリの機能は、レジスタ値LOCKADDR／LOCKCOUNTの機能と類似である。より詳細には、mLOCKADDRは、そのスレッドによりロックされるオブジェクトのアドレスを保持する。mLOCKCOUNTは、そのオブジェクトに対してスレッドにより発行されたロック命令のカウント値を保持する。ロック命令のカウント値は、対応するアンロック命令が実行されていないロック命令数である。mLOCKADDR＝０の場合、エントリが未使用であることを意味する。
【００２８】
テーブル３１０は４つ以上のエントリを有することがある。種々のテーブル３１０は異なる数のエントリを有することがある。
【００２９】
各メモリ位置mLOCKADDRは、ある実施例では３２或いは３０ビット長である。各位置mLOCKCOUNTは８ビット長以上である。いくつかの実施例では、各位置mLOCKCOUNTは３２ビット長であり、各レジスタLOCKCOUNTは８ビット長である。
【００３０】
オペレーティングシステムが実行に対するスレッドをスケジュールする際に、オペレーティングシステムは、対応するテーブル３１０からレジスタ対LOCKADDR／LOCKCOUNTへの４つまでのエントリをロードすることがある。各エントリは１つのレジスタ対LOCKADDR／LOCKCOUNTに書き込まれる。mLOCKCOUNTがLOCKCOUNTより大きい場合、オペレーティングシステムは、LOCKCOUNT（いくつかの実施例では８ＬＳＢ）に適合する同じ数のmLOCKCOUNTのＬＳＢをLOCKCOUNTに書き込む。あるレジスタ対がテーブル３１０からのエントリを受信しない場合、オペレーティングシステムは対応するレジスタLOCKADDRを０に設定し、そのレジスタ対が未使用（「空き」）であることを示す。
【００３１】
ある実施例では、テーブル３１０は各エントリに対するビット（図示せず）を備え、そのスレッドが実行に対してスケジュールされる際にそのエントリがLOCKADDR／LOCKCOUNTレジスタ対に書き込まれるべきか否かを示す。他の実施例では各スレッドに対して、オペレーティングシステムは、そのスレッドが実行に対してスケジュールされる際にレジスタ１４４に書き込まれるべきエントリのリスト（図示せず）を保持する。いくつかの実施例では、オペレーティングシステムは各エントリに対するビット或いはエントリのリストを備え、LOCKADDR／LOCKCOUNTレジスタに書き込まれているエントリをマークする。
【００３２】
ある場合には、ロック及びアンロック命令によりトラップが生成されることはない。それゆえmLOCKCOUNTのＬＳＢは無効である、すなわちLOCKADDR／LOCKCOUNTレジスタ対により識別されるロックに対するテーブル３１０にエントリが存在しない場合がある。
【００３３】
あるスレッドＴ１が割り込まれ、他のスレッドＴ２がプロセッサ１１０上で実行に対してスケジュールされる際に、オペレーティングシステムは、スレッドＴ２のテーブル３１０からレジスタをロードする前に、全ての非空きLOCKADDR／LOCKCOUNTレジスタ対をスレッドＴ１のテーブル３１０に書き込む。mLOCKCOUNTがLOCKCOUNTより大きい場合には、オペレーティングシステムは各LOCKCOUNTレジスタを対応する位置mLOCKCOUNTのＬＳＢに書き込む。現在のスレッドのテーブル３１０がLOCKADDR／LOCKCOUNTレジスタ対により識別されるロックに対するエントリを持たない場合には、オペレーティングシステムによりエントリが作成される。
【００３４】
いくつかの実施例では、LockCountOverflowTrapに対するトラップハンドラは、ロックされるオブジェクトのアドレスを含むmLOCKADDRを有するエントリに対する現在スレッドのテーブル３１０を探索する。そのようなエントリが存在しない場合には、トラップハンドラは未使用エントリを探索し、mLOCKADDRをロックされるオブジェクトのアドレスに設定し、mLOCKCOUNTを０に設定する。いずれの場合（エントリが存在したか或いはエントリがそこで作成されたかの何れの場合）であっても、トラップハンドラは、LOCKCOUNTレジスタに格納されないmLOCKCOUNTのＭＳＢをインクリメントし、ＬＳＢを０に設定する。
【００３５】
ここで命令ユニット１３６によるロック命令の実行に説明を戻す。いくつかの実施例では、付録Ａのステップ１−０から１−３におけるレジスタLOCKADDRとロックされるオブジェクトのアドレスとの比較が、４つのレジスタに対応する４つのコンパレータにより並列に実行され、ステップ１−０ａ、１−１ａ、１−２ａ、１−３ａにおけるLOCKCOUNTのインクリメントがインクリメンタを用いて実行される。そのようなコンパレータ及びインクリメンタは当分野では周知である。
【００３６】
実行ユニット１３６は、ロックされるオブジェクトのヘッダ２２０からLOCKビット（第２図）を読み出し、LOCKビットを１に設定し、そのオブジェクトがロックされる（ステップ２ａ）ことを示す。この読出し及び設定（検査及び設定）動作は最小単位動作（atomic operation）であり、すなわち（１）プロセッサが、その動作が完了するまで割込みを行わない及び（２）マルチプロセッサ環境では、その動作が完了するまで他のプロセッサがそのLOCKビットにアクセスすることができないであろう。いくつかの実施例では、この検査及び設定動作は、ステップ１−０から１−３と並列に実行される。他の実施例では、この検査及び設定動作は、ステップ１−０から１−３の後、いずれのLOCKADDRレジスタもロックされるオブジェクトのアドレスを含まない場合にのみ実行される。
【００３７】
いずれのLOCKADDRレジスタもロックされるオブジェクトのアドレスを含まず（ステップ２）、検査及び設定動作前にLOCKビットが設定されていた場合（ステップ２ａ）、プロセッサ１１０はトラップLockBusyTrapを生成する。
【００３８】
LockBusyTrapに対するトラップハンドラが、現在のスレッドのテーブル３１０を探索し、現在のスレッドがオブジェクトに対するロックを保持するか否かを確認する。オブジェクトアドレスが、テーブル３１０のエントリの１つのmLOCKADDRに格納されるアドレスに等しい場合、対応するmLOCKCOUNTがトラップハンドラによりインクリメントされる。さらにいくつかの実施例では、トラップハンドラはそのエントリをレジスタ対LOCKADDR／LOCKCOUNT内に配置することがある。これは、スレッドにより発行される次のロック或いはアンロック命令が、そのスレッドが最も新しいロック命令を発行したオブジェクトに対するものである可能性がある場合に望ましい。トラップハンドラがエントリをレジスタ対に配置することが望ましいが、全てのレジスタ対が他のロックにより占有されている場合には、トラップハンドラはテーブル３１０に書き込むことにより、レジスタ対の１つを空ける（上記のように、mLOCKCOUNTがLOCKCOUNTより大きい場合、LOCKCOUNTレジスタはmLOCKCOUNTのＬＳＢに書き込まれる）。
【００３９】
現在のスレッドがロックを保持せず、そのオブジェクトアドレスが対応するテーブル３１０のメモリ位置mLOCKADDRと全く一致しない場合には、そのトラップハンドラはオブジェクトヘッダ（第２図）にＷＡＮＴビットを設定し、このロックを捕捉するために待機しているスレッドの待ち行列にスレッドを配置する。
【００４０】
ここで実行ユニット１３６によるロック命令の実行に説明を戻す。オブジェクトのLOCKビットが、検査及び設定動作前に設定されていなかった場合には、ステップ２ｂ−０から２ｂ−３が実行される。ステップ２ｂ−ｉ（ｉ＝０〜３）ではそれぞれ、各コンパレータがレジスタLOCKADDRiと０とを比較する。この比較は、ステップ１−０から１−３及び２の比較と並列に実行される。LOCKADDR０＝０（ステップ２ｂ−０）の場合には、レジスタ対LOCKADDR０／LOCKCOUNT０は未使用である。レジスタLOCKADDR０は、ロックされるオブジェクトのアドレスを書き込まれる（ステップ２ｂ−０ａ）。レジスタLOCKCOUNT０は１に設定される（ステップ２ｂ−０ｂ）。
【００４１】
LOCKADDR０が０ではないが、LOCKADDR１＝０の場合には、レジスタLOCKADDR１はロックされるオブジェクトのアドレスを書き込まれ、レジスタLOCKCOUNT１は１に設定される。（ステップ２ｂ−１ａ、２ｂ−１ｂ）。LOCKADDR０及びLOCKADDR１が０ではないが、LOCKADDR２＝０の場合、LOCKADDR２はロックされるオブジエクトのアドレスを書き込まれ、レジスタLOCKCOUNT２は１に設定される（ステップ２ｂ−２ａ、２ｂ−２ｂ）。LOCKADDR０、LOCKADDR１及びLOCKADDR２が０ではないが、LOCKADDR３＝０の場合、レジスタLOCKADDR３はロックされるオブジエクトのアドレスを書き込まれ、レジスタLOCKCOUNT３が１に設定される（ステップ２ｂ−３ａ，２ｂ−３ｂ）。
【００４２】
LOCKADDRレジスタのいずれも０ではない場合には、トラップNoLockAddrRegsTrapが生成される（ステップ２ｃ）。いくつかの実施例では、このトラップに対するトラップハンドラは、現在のスレッドのテーブル３１０の未使用エントリを探索するか或いは作成する。そのトラップハンドラはロックされるオブジェクトのアドレスをそのエントリの位置mLOCKADDRに書き込み、対応するmLOCKCOUNTを１に設定する。さらにトラップハンドラは、テーブルエントリをLOCKADDR／LOCKCOUNTレジスタ対に配置することもある。レジスタ対の古い内容は、そのレジスタ対が書き込まれる前に、スレッドのテーブル３１０に格納される。
【００４３】
付録Ｂはアンロック命令に対する疑似コードを示す。ステップ１−０から１−３では、LOCKADDRレジスタがアンロックされるオブジエクトのアドレスと並列に比較される。一致する場合には、現在のスレッドがロックを保持することを示しており、対応するLOCKCOUNTレジスタがデクリメンタによりデクリメントされ（ステップ１−０ａ、１−１ａ、１−２ａ、１−３ａ）、０と比較される（ステップ１−０ｂ、１−１ｂ、１−２ｂ、１−３ｂ）。デクリメント後にLOCKCOUNTレジスタが０になる場合には、トラップLockCountZeroDecrementTrapが生成される。上記のようにいくつかの実施例ではテーブル３１０の位置mLOCKCOUNTは、LOCKCOUNTレジスタより大きい。そのようないくつかの実施例では、LockCountZeroDecrementTrapに対するトラップハンドラが、あるエントリに対する対応するテーブル３１０を探索し、そのエントリのmLOCKADDRは、アンロックされるオブジェクトのアドレスを格納する。そのようなエントリが見いだされる場合、トラップハンドラは、０までデクリメントされたLOCKCOUNTに対応するmLOCKCOUNT位置をチェックする。そのmLOCKCOUNT位置が、LOCKCOUNTレジスタに書き込まれていなかったＭＳＢにおいて「１」に有する場合、そのオブジェクトはスレッドによりロック状態を保持する。mLOCKCOUNTメモリ位置では、ＭＳＢにより形成されるフィールドがデクリメントされ、ＬＳＢが１１．．．１（全て１）に設定され、LOCKCOUNTレジスタに書き込まれる。
【００４４】
mLOCKCOUNTのＭＳＢが全て０、すなわちアンロックされるオブジェクトのアドレスを保持するmLOCKADDRを有するエントリが存在しない場合には、そのトラップハンドラはロックを解除し、他のスレッドが利用できるようにする。ロックの解除処理は、以下により詳細に記載される。
【００４５】
mLOCKCOUNT位置がLOCKCOUNTレジスタより大きくない場合には、トラップハンドラは、ロックが解除されるべきか否かを判定するためにmLOCKCOUNT位置をチェックする必要はない。
【００４６】
ロックの解除処理は以下の動作を含む。トラップハンドラがオブジェクトヘッダ２２０ＨのWANTビットを検査する。WANTビットが設定されている場合、他のスレッドがこのロックにおいて阻止している。トラップハンドラがそのようなスレッドの１つを選択し、その状態を実行可能に設定し、さらにこのスレッドにロックを与える。詳細には、トラップハンドラはLOCKCOUNTレジスタに１のカウント値を書き込む。１つの対応するレジスタ対mLOCKADDR／mLOCKCOUNTが存在した場合には、そのトラップハンドラはmLOCKCOUNT位置に１を書き込む。別法ではいくつかの実施例では、トラップハンドラはLOCKADDR位置に０を書き込み、mLOCKADDR／mLOCKCOUNT対を割当て解除する。さらに、ロックを受け取るスレッドがそのロックにおいて阻止しているスレッドのみである場合には、そのトラップハンドラはWANTビットをリセットする。
【００４７】
そのロックにおいて阻止するスレッドが存在しない場合には、そのトラップハンドラは０を（ａ）対応するLOCKADDRレジスタに、及び（ｂ）存在するなら、対応するmLOCKADDR位置に書き込む。さらにトラップハンドラはヘッダ２２０ＨのLOCKビットをリセットする。またそのレジスタが利用できなかったため、現在のスレッドのテーブル３１０がLOCKADDR／LOCKCOUNTレジスタに書き込まれることができなかった非空きエントリを含む場合、トラップハンドラは、そのエントリの１つを、ロック解除動作により空き状態にされるLOCKADDR／LOCKCOUNTレジスタ対に配置する。
【００４８】
いかなるLOCKADDRレジスタもアンロックされるオブジェクトのアドレスを保持しない場合には（ステップ２）、LockReleaseTrapが生成される。その関連するトラップハンドラは、アンロックされるオブジエクトのアドレスに対する現在のスレッドのテーブル３１０のmLOCKADDR位置を探索する。一致する場合には、対応する位置mLOCKCOUNTはトラップハンドラによりデクリメントされる。mLOCKCOUNTが０になる場合ロックは解除される。ロックを解除するためにトラップハンドラは、トラップLockCountZeroDecrementTrapに対して上記の動作と類似の動作を実行する。より詳細には、WANTビットが設定される場合、トラップハンドラはそのロックにおいて阻止する別のスレッドを探索し、そのスレッドの状態を実行可能に設定する。トラップハンドラは対応する位置mLOCKCOUNTを１に設定する。いくつかの実施例では、そのトラップハンドラはmLOCKADDR／mLOCKCOUNTエントリをLOCKADDR／LOCKCOUNTレジスタ対に配置する。ロックを受け取るスレッドが、そのロックにおいて阻止されている唯一のスレッドである場合には、トラップハンドラはWANTビットをリセットする。そのロックにおいて阻止するスレッドが存在しない（WANTビットが０であった）場合には、そのトラップハンドラはmLOCKADDR位置に０を書き込み、オブジェクトヘッダ２２０ＨのLOCKビットをリセットする。
【００４９】
現在スレッドのテーブル３１０においていかなるメモリ位置mLOCKADDRもアンロックされるオブジェクトのアドレスを保持しない場合、そのトラップハンドラは例外IllegalMonitorStateExceptionを生成する。いくつかの実施例では、この例外はJAVA（登録商標）動作である。より詳細には幾つかの実施例では、プロセッサ１１０はJAVA（登録商標）仮想マシン言語命令（JAVAバイトコードとしても知られる）を実行する。JAVA仮想マシン言語は、例えばLindholm and F.Yellinによる「The JAVATM Virtual Machine Specification」（１９９７）に記載されており、ここで参照して本明細書の一部としている。
【００５０】
プロセッサ１１０は以下に示す多くの通常状態において、高速ロック処理及びアンロック処理を実現する。ロックに対する競合が存在しない場合、さらにオブジェクトロックが解除される前に、同じオブジェクトにおいてスレッドが多数のロック動作を実行する場合であるがそれに相当する。より詳細には、オブジェクトが別のスレッドによりロックされていない（すなわち競合が生じない）多くの場合において、ロック命令が発行される場合である。そのオブジェクトが、現在のロック命令を発行した同じスレッドにより既にロックされている場合、多くの場合、スレッドが同時に５つ以上のロックを保持せず、さらにそのスレッドに対する全てのロックされたオブジェクトアドレスがLOCKADDRレジスタ内に存在するため、多くの場合にそのオブジェクトのアドレスは既にLOCKADDRレジスタ内に存在する。ロックされたオブジェクトアドレスがLOCKADDRレジスタ内に全く存在しない場合でも、ロック命令により識別されるオブジェクトのアドレスがLOCKADDRレジスタ内に存在する可能性がある。そのような多くの場合において、ロック処理動作は対応するLOCKCOUNTレジスタをインクリメントする必要があり（付録Ａ、ステップ１−ｉａ、ただしｉ＝０、１、２、３）、多くの実施例においてそれは高速動作である。そのインクリメントによりオーバーフローが生じない場合には、いかなるトラップも生成されないであろう。
【００５１】
またレジスタ対LOCKADDR／LOCKCOUNTの１つが未使用である場合には、そのオブジェクトがいかなるスレッド（ロック命令を発行するスレッドを含む）によってもロックされていない際に、ロック処理は高速化される。そのような場合には、オブジェクトはステップ２ｂ−０から２ｂ−３の１つにおいてロックされる（付録Ａ）。再びいかなるトラップも生成されない。
【００５２】
同様に、アンロック命令では多くの場合に、ロックされるオブジェクトのアドレスがLOCKADDRレジスタの１つに存在するであろう。対応するLOCKCOUNTレジスタが０ではない値にデクリメントされる場合には、いかなるトラップも生成されない。
【００５３】
いくつかの実施例では、プロセッサ１１０は、Sun Microsystems（Mountain View,California）によりその仕様が作成された「picoJAVA I」タイプのマイクロプロセッサである。このマイクロプロセッサはJAVA仮想マシン命令を実行する。ロック命令は、JAVA仮想マシン命令セットの「monitorenter」命令か、或いはプロセッサ「picoJAVA I」の「enter_sync_method」命令である。「enter_sync_method」命令は「monitorenter」に類似であるが、「enter_sync_method」命令は、オブジェクト以外のメソッドへの参照値をパラメータとして取得する。「enter_sync_method」はそのメソッドに対する受信オブジェクトをロックし、そのメソッドを呼び出す。アンロック命令はJAVA仮想マシン命令セットの「monitorexit」命令か、或いは上記「enter_sync_method」命令において参照されるメソッドからのリターン命令である。
【００５４】
プロセッサ１１０のいくつかの実施例は、４つ以上或いは４つ以下のLOCKADDR／LOCKCOUNTレジスタ対を含む。
【００５５】
いくつかの実施例では、レジスタ１４４は、図４に示されるように３組のレジスタ「THREAD_ID,LOCKADDR,LOCKCOUNT」を備える。その３組のレジスタでは、レジスタTHREAD_IDが、レジスタ対LOCKADDR／LOCKCOUNTに記録されるロックを保持するスレッドを識別する。ロック或いはアンロック命令が発行される際に、実行ユニット１３６は、レジスタTHREAD_IDが現在のスレッドのＩＤを保持するそのLOCKADDR／LOCKCOUNT対のみを検査する。他の点では、ロック及びアンロック命令の実行は第２図の場台と同様である。第４図の構造は、異なるスレッドに対して同時にロックされたオブジェクトのアドレス及びロックカウントをレジスタ１４４に保持するのを容易にする。第４図の構造を用いるいくつかの実施例では、オペレーティングシステムは、異なるスレッドが実行をスケジュールされる際に、レジスタ１４４をリロードしない。オペレーティングシステムは、第３図に示されるように各スレッドに対するテーブル３１０を保持する。３組のレジスタが空状態にされる必要がある際に、対応するLOCKADDR／LOCKCOUNT値が対応するテーブル３１０に書き込まれる。テーブルエントリがレジスタ対LOCKADDR／LOCKCOUNTに配置される際に、対応するレジスタTHREAD_IDが、対応するスレッドのIDを書き込まれる。
【００５６】
第１図−第４図のプロセッサは、JAVA仮想マシンロック及びアンロック命令「monitorenter」及び「monitorexit」を効率よく実行するのに適している。JAVAのオブジェクトモニタに関連するカウンタは、レジスタLOCKCOUNTを用いて実装されることができる。
【００５７】
ある実施例ではレジスタLOCKCOUNT及び位置mLOCKCOUNTは省略される。プロセッサはLOCKCOUNTのトラックを保持せず、プロセッサがそのロックに対応するあらゆるアンロック命令においてロックを解除する。プロセッサ動作は、付録Ａ及びＢに関連して上記した動作と同様である。しかしながら付録Ａでは、ステップ１−０から１−３ｂまでが省略される。またステップ２ｂ−０ｂ、２ｂ−１ｂ、２ｂ−２ｂ及び２ｂ−３ｂ（LOCKCOUNT動作）も省略される。付録Ｂでは、ステップ１−０ａが省略され、ステップ１−０ｂでは、無条件にトラップLockCountZeroDecrementTraptが生成される。同じことがステップ１−１ａ及び１−１ｂ、１−２ａ及び１−２ｂ、１−３ａ及び１−３ｂにも当てはまる。
【００５８】
いくつかの実施例では、各LOCKCOUNTレジスタは１ビット長であり、プロセッサはそのロックに対応するあらゆるアンロック命令においてロックを解除する。
【００５９】
上記実施例は例示であって、本発明を限定するものではない。本発明は、任意の特定のプロセッサアーキテクチャ、キャッシュ或いはメモリの存在または構造、或いは任意のレジスタまたはメモリ位置におけるビット数により制限されない。本発明は、ロック或いはアンロックされるようになる任意の特定のタイプのオブジェクトに制限されない。オブジェクトは、データ、クリティカルコード部分、ハードウエア或いは上記の任意の組み合わせのようなリソースを含む任意のコンピュータリソースを表すことができる。いくつかの実施例は、ロック処理及びアンロック処理動作のためのコンピュータリソースを表す専用のオブジェクトを形成する。上記実施例では、未使用のレジスタ対LOCKADDR／LOCKCOUNTはLOCKADDRレジスタにおいて０により識別されるが、いくつかの実施例では未使用レジスタ対は、LOCKADDRレジスタにおける０ではない値、すなわちLOCKCOUNTレジスタのある値によって、または第４図の実施例の場合、THREAD_IDレジスタのある値、或いはLOCKADDR／LOCKCOUNTレジスタ対並びにまた任意の２つ或いは３つのLOCKADDR／LOCKCOUNT／THREAD_IDレジスタの値の組み合わせにより、または個別のビットにより識別される。同様のことが未使用のmLOCKADDR／mLOCKCOUNT位置の場合に当てはまる。いくつかの実施例では、トラップハンドラにより実行されるような上記の動作のいくつか或いは全てがソフトウエアではなくハードウエアにより実行される。いくつかの実施例では、ハードウエアにより実行されるように上記されたいくつかの動作がハードウエアではなくソフトウエアにより実行される。本発明はバイトアドレスであるアドレスに限定されない。他の実施例及び変形例も本発明の範囲内にあり、添付の請求項により規定される。
【数１ａ】
0004196414.tif 000002
【数１ｂ】
0004196414.tif 000003
【数１ｃ】
0004196414.tif 000004
【数２】
0004196414.tif 000005
【図１】
0004196414.tif 000006
【図２】
0004196414.tif 000007
【図３】
0004196414.tif 000008
【図４】
0004196414.tif 000009