(57)【特許請求の範囲】
【請求項１】
共有メモリモデルのシステムで、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビット及び第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックの識別子を記憶することによりオブジェクトへのロックを管理する方法であって、
第１のスレッドが保持しているあるオブジェクトへのロックを第２のスレッドが獲得しようとした場合、前記あるオブジェクトの前記ロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、
前記第１の種類のロックであることを示している場合には、競合ビットを立てるステップと、
前記第１のスレッドが保持しているあるオブジェクトへのロックを解除する際に、前記ロックの種類を示すビットが前記第１の種類のロックであることを示しているか判断するステップと、
前記複数のスレッドの識別子と異なる特殊識別子を前記記憶領域に記憶するステップと、
前記記憶領域の同期命令を発行するステップと、
前記あるオブジェクトのロックを保持しているスレッドが存在しないことを前記記憶領域に記憶するステップと、
前記ロックの種類を示すビットが前記第１の種類のロックであることを示している場合には、前記競合ビットが立っているか判断するステップと、
前記競合ビットが立っていないと判断された場合には、他の処理を実施せずにロック解除処理を終了するステップと、
を含むロック管理方法。
【請求項２】
前記競合ビットが立っていると判断された場合には、オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に前記第１のスレッドが移行するステップと、
待機しているスレッドへの通知操作を前記第１のスレッドが実行するステップと、
前記所定の条件が非成立でかつ前記特殊識別子が記憶されているとき、前記あるオブジェクトのロックを保持しているスレッドが存在せずかつ、ロックの種類を示すビットが第１の種類のロックになるまで前記第２のスレッドが繁忙待機するステップと、
前記第１のスレッドが前記排他制御状態から脱出するステップと、
をさらに含む請求項１に記載のロック管理方法。
【請求項３】
前記第１の種類のロックとは、オブジェクトに対してロックを実施するスレッドの識別子を当該オブジェクトに対応して記憶することによりロック状態を管理するロック方式である、請求項１に記載のロック管理方法。
【請求項４】
前記第２の種類のロックとは、オブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である、請求項１記載のロック管理方法。
【請求項５】
共有メモリモデルのシステムで、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビット及び第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックの識別子を記憶することによりオブジェクトへのロックを管理する装置であって、
第１のスレッドが保持しているあるオブジェクトへのロックを第２のスレッドが獲得しようとした場合、前記あるオブジェクトの前記ロックの種類を示すビットが第１の種類のロックであることを示しているか判断する手段と、
前記第１の種類のロックであることを示している場合には、競合ビットを立てる手段と、
前記第１のスレッドが保持しているあるオブジェクトへのロックを解除する際に、前記ロックの種類を示すビットが前記第１の種類のロックであることを示しているか判断する手段と、
前記複数のスレッドの識別子と異なる特殊識別子を前記記憶領域に記憶する手段と、
前記記憶領域の同期命令を発行する手段と、
前記あるオブジェクトのロックを保持しているスレッドが存在しないことを前記記憶領域に記憶する手段と、
前記ロックの種類を示すビットが前記第１の種類のロックであることを示している場合には、前記競合ビットが立っているか判断する手段と、
前記競合ビットが立っていないと判断された場合には、他の処理を実施せずにロック解除処理を終了する手段と、
を含むロック管理装置。
【請求項６】
前記競合ビットが立っていると判断された場合には、オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に前記第１のスレッドが移行する手段と、
待機しているスレッドへの通知操作を前記第１のスレッドが実行する手段と、前記所定の条件が非成立でかつ前記特殊識別子が記憶されているとき、前記あるオブジェクトのロックを保持しているスレッドが存在せずかつ、ロックの種類を示すビットが第１の種類のロックになるまで前記第２のスレッドが繁忙待機する手段と、
前記第１のスレッドが前記排他制御状態から脱出する手段と、
をさらに含む請求項５に記載のロック管理装置。
【請求項７】
前記第１の種類のロックとは、オブジェクトに対してロックを実施するスレッドの識別子を当該オブジェクトに対応して記憶することによりロック状態を管理するロック方式である、請求項５に記載のロック管理装置。
【請求項８】
前記第２の種類のロックとは、オブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である、請求項５記載のロック管理装置。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
本発明は、オブジェクトのロック管理方法及び装置にかかり、特に、複数のスレッドが存在し得る状態における、オブジェクトのロック管理方法及び装置に関する。
【０００２】
【従来の技術】
複数のスレッドが動作するプログラムでオブジェクトへのアクセスを同期させるには、アクセスの前にオブジェクトをロック（ｌｏｃｋ）し、次にアクセスを行い、アクセスの後にアンロック（ｕｎｌｏｃｋ）するようにプログラムのコードは構成される。このオブジェクトのロックの実装方法としては、スピンロック及びキューロック（サスペンドロックともいう）がよく知られている。また、最近ではそれらを組み合わせたもの（以下、複合ロックという）も提案されている。以下、それぞれについて簡単に説明する。
【０００３】
（１）スピンロック
スピンロックとは、オブジェクトに対してロックを実施するスレッドの識別子を当該オブジェクトに対応して記憶することによりロック状態を管理するロック方式である。スピンロックでは、スレッドＴがオブジェクトｏｂｊのロック獲得に失敗した場合、すなわち他のスレッドＳが既にオブジェクトｏｂｊをロックしている場合、ロックに成功するまでロックを繰り返す。典型的には、ｃｏｍｐａｒｅ＃ａｎｄ＃ｓｗａｐ  のようなアトミックなマシン命令（不可分命令）を用いて、次のようにロック又はアンロックする。
【０００４】
【表１】
0003575593.tif 000002
【０００５】
上記表１から理解されるように、第２０行及び第３０行でロックを行っている。ロックが獲得できるまで、ｙｉｅｌｄ（）を行う。ここで、ｙｉｅｌｄ（）とは、現在のスレッドの実行を止め、スケジューラに制御を移すことである。通常、スケジューラは、他の実行可能なスレッドから１つを選び走らせるが、いずれまた、スケジュラは、もとのスレッドを走らせることになり、ロックの獲得に成功するまで、ｗｈｉｌｅ文の実行が繰り返される。ｙｉｅｌｄが存在していると、単にＣＰＵ資源の浪費だけでなく、実装がプラットフォームのスケジューリング方式に依存せざるを得ないため、期待どおりに動作するプログラムを書くことが困難になる。第２０行におけるｗｈｉｌｅ文の条件であるｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐは、オブジェクトｏｂｊに用意されたフィールドｏｂｊ−＞ｌｏｃｋの内容と、０とを比較して、その比較結果が真であればスレッドのＩＤ（ｔｈｒｅａｄ＿ｉｄ（））をそのフィールドに書き込むものである。よって、オブジェクトｏｂｊに用意されたフィールドに０が格納されている場合には、ロックしているスレッドが存在しないことを表している。よって、第６０行でアンロックする場合にはフィールドｏｂｊ−＞ｌｏｃｋに０を格納する。なお、このフィールドは例えば１ワードであるが、スレッド識別子を格納するのに十分なビット数であればよい。
【０００６】
（２）キューロック
キューロックとは、オブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である。キューロックにおいては、スレッドＴがオブジェクトｏｂｊのロックに失敗した場合、Ｔは自分自身をｏｂｊのキューに入れてサスペンドする。アンロックするコードには、キューが空か否かをチェックするコードが含まれ、空でなければキューから１つスレッドを取り出し、そのスレッドをリジュームする。このようなキューロックは、オペレーティング・システム（ＯＳ）のスケジューリング機構と一体になって実装され、ＯＳのＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｉｎｔｅｒｆａｃｅ）として提供されている。例えば、セマフォやＭｕｔｅｘ変数などが代表的なものである。キューロックにおいては、スペースオーバーヘッドはもはや１ワードでは済まず、十数バイトとなるのが普通である。また、ロックやアンロックの関数の内部では、キューという共有資源が操作されるため、何らかのロックが獲得され又は解放されている点にも注意する必要がある。
【０００７】
（３）複合ロック
マルチ・スレッド対応のプログラムは、マルチ・スレッドで実行されることを考慮して共有資源へのアクセスはロックにより保護するように書かれる。しかし、例えばマルチ・スレッド対応ライブラリがシングル・スレッドのプログラムから使用されるような場合もある。また、マルチ・スレッドで実行されてもロックの競合がほとんど発生しない場合もある。実際、Ｊａｖａ（Ｓｕｎ  Ｍｉｃｒｏｓｙｓｔｅｍｓ社の商標）のプログラムの実行履歴によると、多くのアプリケーションにおいて、オブジェクトへのアクセスの競合はほとんど発生していないという報告もある。
【０００８】
よって、「ロックされていないオブジェクトにロックをかけ、アクセスし、アンロックする」は高頻度に実行されるパスであると考えられる。このパスは、スピンロックでは極めて効率よく実行されるが、キューロックでは時間的にも空間的にも効率が悪い。一方、高頻度ではないとはいえ、競合が実際に発生した場合、スピンロックではＣＰＵ資源が無益に消費されてしまうが、キューロックではそのようなことはない。
【０００９】
複合ロックの基本的なアイデアは、スピンロックのような処理が簡単なロック（軽量ロックと呼ぶ）とキューロックのような処理が複雑なロック（重量ロックと呼ぶ）をうまく組み合わせて、上記の高頻度パスを高速に実行しつつ、競合時の効率も維持しようというものである。具体的に言えば、最初に軽量ロックでのロックを試み、軽量ロックで競合した場合重量ロックに遷移し、それ以降は重量ロックを使用するものである。
【００１０】
この複合ロックでは、スピンロックと場合と同様に、オブジェクトにはロック用のフィールドがあり、「スレッド識別子」又は「重量ロック識別子」の値、及び、いずれの値を格納しているかを示すブール値が格納される。
【００１１】
ロックの手順は以下のとおりである。
１）アトミックな命令（例えば、ｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐ）で軽量ロック獲得を試みる。成功すればオブジェクトへのアクセスを実行する。
失敗した場合、すでに重量ロックになっているか、又は軽量ロックのままだが他のスレッドがロックをかけているのかのいずれかであることが分かる。
２）既に重量ロックになっていれば、重量ロックを獲得する。
３）軽量ロックで競合した場合、軽量ロックを獲得した上で重量ロックへ遷移し、これを獲得する（以下の説明では、ｉｎｆｌａｔｅ関数において実行される。）
【００１２】
複合ロックには、３）における「軽量ロックの獲得」でｙｉｅｌｄするか否かで２種類の実装がある。これらを詳しく以下に説明する。なお、ロック用のフィールドは１ワードとし、さらに簡単のため「スレッド識別子」又は「重量ロック識別子」は常に０以外の偶数であるとし、ロック用のフィールドの最下位ビットが０ならば「スレッド識別子」、１ならば「重量ロック識別子」が格納される。
【００１３】
複合ロックの例１
軽量ロックの獲得において、ｙｉｅｌｄする複合ロックの場合である。ロック関数は上の手順に従って以下のように書くことができる。
【表２】
0003575593.tif 000003
【００１４】
表２に示された擬似コードは、第１０行から第１３０行までがロック関数、第１５０行から第２００行までがアンロック関数、第２２０行から第２５０行までがロック関数で用いられるｉｎｆｌａｔｅ関数を示している。ロック関数内では、第２０行で軽量ロックが試みられる。もしロックが獲得されれば、当該オブジェクトへのアクセスを実行する。そして、アンロックする場合には、第１６０行でオブジェクトのロック用フィールドにスレッド識別子が入力されているので、第１７０行においてそのフィールドに０を入力する。このように高頻度パスはスピンロックと同じで高速に実行することができる。一方、第２０行でロックを獲得できない場合には、第４０行でｗｈｉｌｅ文の条件であるロック用フィールドの最下位ビットであるＦＡＴ＿ＬＯＣＫビットとロック用フィールドをビットごとにＡＮＤした結果が０であるか、すなわちＦＡＴ＿ＬＯＣＫビットが０であるか（より詳しく言うと軽量ロックであるか）判断される。もし、この条件が満たされていれば、第６０行にて軽量ロックを獲得するまでｙｉｅｌｄする。軽量ロックを獲得した場合には、第２２０行以降のｉｎｆｌａｔｅ関数を実行する。ｉｎｆｌａｔｅ関数では、ロック用フィールドｏｂｊ−＞ｌｏｃｋに重量ロック識別子及び論理値１であるＦＡＴ＿ＬＯＣＫビット入力する（第２３０行）。そして、重量ロックを獲得する（第２４０行）。もし、第４０行で既にＦＡＴ＿ＬＯＣＫビットが１である場合には、直ぐに重量ロックを獲得する（第１１０行）。重量ロックのアンロックは第１９０行にて行われる。なお、重量ロックの獲得及び重量ロックのアンロックは、本発明とはあまり関係ないので説明を省略する。
【００１５】
この表２ではロック用フィールドの書き換えは常に軽量ロックを保持するスレッドにより実施される点に注意されたい。これは、アンロックでも同じである。ｙｉｅｌｄが発生するのは、軽量ロックでの競合時に限定されている。
【００１６】
複合ロックの例２
軽量ロックの獲得において、ｙｉｅｌｄしない複合ロックの例を示す。軽量ロックが競合した場合にはウエイト（ｗａｉｔ）する。軽量ロック解放時には、ウエイトしているスレッドに通知（ｎｏｔｉｆｙ）しなければならない。このウエイト及び通知のためには、条件変数やモニタあるいはセマフォを必要とする。以下の例ではモニタを使用して説明する。
【００１７】
【表３】
0003575593.tif 000004
0003575593.tif 000005
【００１８】
モニタとは、Ｈｏａｒｅによって考案された同期機構であり、オブジェクトへのアクセスの排他制御（ｅｎｔｅｒ及びｅｘｉｔ）と所定の条件が成立した場合のスレッドの待機操作（ｗａｉｔ）及び待機しているスレッドへの通知操作（ｎｏｔｉｆｙ  及びｎｏｔｉｆｙ＿ａｌｌ）とを可能にする機構である（Ｈｏａｒｅ，  Ｃ．Ａ．Ｒ．  Ｍｏｎｉｔｏｒｓ：  Ａｎ  ｏｐｅｒａｔｉｎｇ  ｓｙｓｔｅｍ  ｓｔｒｕｃｔｕｒｉｎｇ  ｃｏｎｃｅｐｔ．  ＣｏｍｍｕｎｉｃａｔｉｏｎＳ  ｏｆ  ＡＣＭ  １７，  １０  （Ｏｃｔ．  １９７４），  ５４９−５５７  参照）。高だか１つのスレッドがモニタにエンタ（ｅｎｔｅｒ）することが許される。スレッドＴがモニタｍにエンタしようとした時、あるスレッドＳが既にエンタしているならば、Ｔは少なくともＳがｍからイグジット（ｅｘｉｔ）するまで待たされる。このように排他制御がなされる。また、モニタｍにエンタ中のスレッドＴは、ある条件の成立を待つため、モニタｍでウエイト（ｗａｉｔ）することができる。具体的には、Ｔは陰にｍよりイグジットしサスペンドする。陰にｍよりイグジットすることにより、別のスレッドがモニタｍにエンタすることができる点に注意されたい。一方、モニタｍにエンタ中のスレッドＳは、ある条件を成立させた後に、モニタｍに通知（ｎｏｔｉｆｙ）することができる。具体的には、モニタｍでウエイト中のスレッドのうちのひとつＵを起こす（ｗａｋｅ  ｕｐ）する。それにより、Ｕはリジュームし、モニタｍに陰にエンタしようとする。ここで、Ｓがｍにエンタ中であるから、Ｕは少なくともＳがｍからイグジットするまで待たされる点に注意されたい。また、モニタｍでウエイト中のスレッドが存在しない場合には、何も起こらない。ｎｏｔｉｆｙ＿ａｌｌは、ウエイト中のスレッドを全て起こす点を除いて、ｎｏｔｉｆｙと同じである。
【００１９】
表３において、第１０行乃至第１６０行はロック関数、第１８０行乃至第２６０行はアンロック関数、第２８０行乃至３２０行はｉｎｆｌａｔｅ関数を示している。ロック関数で複合ロックの例１と異なる点は、第４０行でモニタにエンタする点、軽量ロックで競合した場合にｙｉｅｌｄせずにウエイトする点（第１１０行）、重量ロックに遷移した際（第８０行）及び重量ロックに遷移したことが確認された際（第１３０行）にはモニタからイグジットする点である。ここで、第１３０行ではモニタからイグジットし、第１４０行で重量ロックを獲得している点に注意されたい。
【００２０】
アンロック関数で複合ロックの例１と異なる点は、第２１０行乃至第２３０行においてモニタにエンタし、モニタで通知をし、モニタをイグジットする処理を実施している点である。これは、ｙｉｅｌｄをやめてモニタにおけるウエイトにしたためである。ｉｎｆｌａｔｅ関数では、ｎｏｔｉｆｙ＿ａｌｌが追加されている。これもｙｉｅｌｄをやめてモニタにおけるウエイトにしたためである。なお、第２９０行は、ａｌｌｏｃ＿ｆａｔ＿ｌｏｃｋ（）で得られる重量ロック識別子と論理値１にセットされたＦＡＴ＿ＬＯＣＫビットをＯＲ操作して、ロック用フィールドに入力する操作を示している。
【００２１】
表３を見れば、ｙｉｅｌｄは消滅しているが、アンロック時にウエイトしているスレッドがいるかもしれないので、通知（ｎｏｔｉｆｙ）という作業が入り、高頻度パスの性能が低下している。また、空間効率的には、モニタ又はモニタと同等な機能が余分に必要になっているが、重量ロックに遷移した後には不要になる。言いかえれば、モニタと重量ロックとは別に用意する必要がある。
【００２２】
【発明が解決しようとする課題】
ところで、論理的にメモリを共有する共有メモリモデルによるアーキテクチャでは、プロセッサとメモリが対称をなした対称型マルチプロセッサとよばれる共有メモリモデルによるシステム（以下、ＳＭＰシステムという）が知られている。このＳＭＰシステムでは、命令レベル並列実行やメモリシステム最適化のため、メモリ操作（ＲｅａｄおよびＷｒｉｔｅ）の順序は、用いるハードウェアによって変更される。すなわち、プログラムＪを実行するプロセッサＰ１によるメモリ操作に関して、他のプロセッサＰ２の観測順序は、プログラムＪの指定順序と同一であるとは限らない。例えば、ＩＢＭ社のＰｏｗｅｒＰＣ、ＤＥＣ社のＡｌｐｈａ、Ｓｕｎ社のＳｏｌａｒｉｓ  ＲＭＯ等の先進的なアーキテクチャでは、Ｒｅａｄ−＞Ｒｅａｄ、Ｒｅａｄ−＞Ｗｒｉｔｅ、Ｗｒｉｔｅ−＞Ｒｅａｄ、Ｗｒｉｔｅ−＞Ｗｒｉｔｅの全てにおいてプログラムの順序を保証していない。
【００２３】
しかしながら、プログラムによっては、プログラムの順序に従った観測が必要な場合もある。このため、上記アーキテクチャは、何れも、何らかのメモリ同期命令を提供している。例えば、ＰｏｗｅｒＰＣアーキテクチャは、メモリ同期命令としてＳＹＮＣ命令を有している。プログラマはこの命令を陽（直接的に）に用いることにより、ハードウェアによるメモリ操作の並べ替えを制限することができる。但し、メモリ同期命令は一般に高負荷であるので、多用することは好ましくない。
【００２４】
ＳＭＰシステムにおいてプログラムの順序に従った観測が必要となる処理の一例を、次に示す。
複合ロックの例３
【表４】
0003575593.tif 000006
0003575593.tif 000007
【００２５】
上記表のコードにおける特徴は、次の点である。なお、ここでは、高頻度パスの処理速度を低下させないために、競合ビット（ｆｌｃ＿ｂｉｔ）を新規に導入している。
【００２６】
（１）  オブジェクトヘッダ中の１つのフィールドをロック用に用いる。
（２）  軽量モードと重量モードの２つがあり、これらを区別するために形体ビット（ＦＡＴ＿ＬＯＣＫ）がある。なお、初期モードは軽量モードである。
（３）  軽量モードでは次のように動作する。軽量モードでは、ロックフィールドは、ロック状態ならばロックの保持者を、非ロック状態ならば０を格納する。スレッドＴは、ロックフィールドに自分の識別子を「原始的に」書き込むことによりロックを獲得する。スレッドＴは、ロックフィールドを「単純に（原始的ではなく）」ゼロクリアすることによりロックを解放する。
（４）  重量モードでは次のように動作する。このモードでは、ロックフィールドは、モニタ構造体への参照を格納している。重量モードでのロックの獲得解放は、モニタへの突入脱出に還元される。
（５）  軽量モードでのロック獲得時に競合が発生した場合、軽量モードから重量モードへ遷移（以下、ロックの膨張という）する。このとき、モニタ構造体が必要に応じ動的に割り当てられる。
（６）  重量モードでのロック解放時に、重量モードから軽量モードへ遷移（以下、ロックの収縮という）する場合がある。
【００２７】
上記を図７を参照して説明する。図７に示したように、あるオブジェクトをロックしているスレッドが存在しない場合（（１）の場合）には、ロック用フィールド及び競合ビット共に０が格納される。その後、あるスレッドがそのオブジェクトをロック（軽量ロック）すると、そのスレッドの識別子がロック用フィールドに格納される（（２）の場合）。もし、このスレッド識別子のスレッドがロックを解放するまでに他のスレッドがロックを試みなければ（１）に戻る。ロックを解放するまでに他のスレッドがロックを試みると、軽量ロックにおける競合が発生したので、この競合を記録するため競合ビットを立てる（（３）の場合）。その後、重量ロックに移行した際には、競合ビットはクリアされる（（４）の場合）。可能であれば、（４）は（１）に移行する。なお、ロック用フィールドの最下位に軽量ロックと重量ロックのモードを表すビット（ＦＡＴ＿ＬＯＣＫビット）設けるようにしたが、最上位に設けるようにしても良い。
【００２８】
次に、軽量モードでの動作および膨張処理について説明する。
まず、ｌｏｃｋ関数の第４行目の原始命令により、軽量モードでのロックの獲得を試みる。軽量モードでかつ無競合ならば成功する。そうでなければ重量ロックを獲得、すなわち、モニタに突入し、膨張処理に入る。このとき、すでに重量モードならばｗｈｉｌｅ文の本体は実行されない。ここで、ｏｂｔａｉｎ＿ｍｏｎｉｔｏｒ関数は、オブジェクトに対応するモニタを返す関数である。対応関係はハッシュ表等で管理される。
【００２９】
一方、ｕｎｌｏｃｋ関数では、２１行目で形体ビットがテストされ、軽量モード時は第２２行〜第２５行目を実行する。第２３行目はロック解放であるが、原始命令は使用していない。第２５行目のビットテストは、後述するが、ロックの膨張処理と関係し、無競合時は失敗し、ｉｆ文の本体は実行されない。
【００３０】
ところで、ＳＭＰシステム特有の処理が、第２２行目と第２４行目のＳＹＮＣ命令である。第２２行目のＳＹＮＣ命令は、ロック保持中に行なったメモリ操作命令をロック解放前に完了することを保証するもので、本複合ロックに限らず必要な処理である。一方、第２４行目のＳＹＮＣ命令は、第２３行目のロック解放と第２５行目のビットテストがプログラム順に完了することを強制するもので、本複合ロック独特のものである。
【００３１】
本複合ロックの膨張処理の大きな特徴は、膨張処理で繁忙待機せずにモニタ待機することである。しかも、これを軽量モードでのロック解放に、原始命令を使用することなく実現しており、少なくともユニプロセッサでは理想的なロック法となっている。
【００３２】
ここで、繁忙待機を止めてモニタ待機する際に、最大の難関は、通知保証、すなわち、「モニタ待機に入ったスレッドは必ず通知される」ことを保証することである。本複合ロックでは、ＦＬＣ（ｆｌａｔ  ｌｏｃｋ  ｃｏｎｔｅｎｔｉｏｎ）ビットと呼ばれる、ロックフィールドとは別のワードに確保された１ビットを用いて、巧妙なプロトコルを構成することで、通知保証を実現している。これについて説明する。
【００３３】
スレッドＴが、第１６行目でモニタ待機に入ったとする。これは、第１３行目の原始命令に失敗したことを意味する。この時刻をｔとする。ここで、プログラム順の完了が保証されるように第１０行〜第１３行目が書かれているとすると、時刻ｔより前にＦＬＣビットはセットされている。
【００３４】
一方、原始命令の失敗は、時刻ｔにおいて別のスレッドＳがロックを保持していること意味する。次の理由によりそれは軽量ロックである。本複合ロックは、常にモニタの保護下でモード遷移するようにコードが書かれている。スレッドＴは、第９行目の突入または第１６行目の待機からの復帰により、モニタに突入している。スレッドＴは、しかも、第１０行目で軽量モードであることを確認している。従って、第１２行目でもモードは変わらず軽量モードであることがわかる。
【００３５】
時刻ｔでスレッドＳは軽量ロックを保持しているが、特に第２４行目のＳＹＮＣ命令を実行していない。従って、時刻ｔより後にＦＬＣビットはテストされる。
【００３６】
以上のことにより、時刻ｔより前にスレッドＴはＦＬＣビットをセットし、時刻ｔより後にスレッドＳはＦＬＣビットをテストする。従って、スレッドＳは、第２５行目のテストに常に成功し、ｉｆ文の本体を実行し、スレッドＴに対しモニタ通知する。すなわち、通知保証が達成されている。
【００３７】
第２４行目のＳＹＮＣ命令がなければ、第２５行目のビットの読み出しは、第２３行目の書き込みより先に実行される可能性があり、ＦＬＣビットのテストが、原始命令の失敗時刻ｔより後だとは保証できない。したがって、第２４行目のＳＹＮＣ命令は、本複合ロックの正当性に不可欠なものである。
【００３８】
このように、本複合ロックでは、ＳＭＰシステムで実装した場合、軽量モード無競合時のロック解放において、メモリ同期命令を２つ用いる必要がある。
【００３９】
なお、重量ロックの解除では、第３３行に処理は移行する。第３４行では、ｌｏｃｋｗｏｒｄという変数にロック用フィールドの内容を格納する。そして、モニタにおける待機状態（ｗａｉｔ）にあるスレッドが他に存在しないかを判断する（第３５行）。もし、存在しない場合には、所定の条件を満たしているか判断する（第３６行）。所定の条件には、重量ロックから脱出しない方が良いような条件があればそのような条件を設定する。但し、本ステップは実行しなくてもよい。もし、所定の条件を満たしている場合には、ロック用フィールドｏｂｊ−＞ｌｏｃｋを０にする（第３７行）。すなわち、ロックを保持しているスレッドが存在しないことをロック用フィールドに格納する。そして、変数ｌｏｃｋｗｏｒｄのＦＡＴ＿ＬＯＣＫビット以外の部分に格納されたモニタ識別子のモニタからイグジットする（第３８行）。ｌｏｃｋｗｏｒｄ  ＆  ￣ＦＡＴ＿ＬＯＣＫは、ＦＡＴ＿ＬＯＣＫビットを反転させたものとｌｏｃｋｗｏｒｄとのビットごとのＡＮＤである。これにより、モニタにエンタしようとして待機していたスレッドが、モニタにエンタできるようになる。
【００４０】
次に、モニタ識別子を獲得するｏｂｔａｉｎ＿ｍｏｎｉｔｏｒ関数を説明する。この関数では、上記と同様に、ｌｏｃｋｗｏｒｄという変数にロック用フィールドの内容を格納する（第５０行）。そして、モニタの識別子を格納する変数ｍｏｎを用意し（第５１行）、ＦＡＴ＿ＬＯＣＫビットが立っているか判断する（第５２行、ｗｏｒｄ  ＆  ＦＡＴ＿ＬＯＣＫ）。もし、ＦＡＴ＿ＬＯＣＫビットが立っているようであれば、変数ｍｏｎにｌｏｃｋｗｏｒｄのＦＡＴ＿ＬＯＣＫビット以外の部分を格納する（第５３行、ｌｏｃｋｗｏｒｄ  ＆  ￣ＦＡＴ＿ＬＯＣＫ）。一方、ＦＡＴ＿ＬＯＣＫビットが立っていない場合には、関数ｌｏｏｋｕｐ＿ｍｏｎｉｔｏｒ（ｏｂｊ）を実行する（第５５行）。この関数は、オブジェクトとモニタの関係を記録したハッシュ・テーブルを有していることを前提とし、基本的にはこのテーブルをオブジェクトｏｂｊについて検索して、モニタの識別子を獲得する。もし、必要があれば、モニタを生成し、そのモニタの識別子をハッシュ・テーブルに格納した後にモニタ識別子を返す。いずれにしても、変数ｍｏｎに格納されたモニタの識別子を返す。
【００４１】
本発明の目的は、高頻度パスの処理速度を低下させない、新規な複合ロック方法を提供することである。
【００４２】
【課題を解決するための手段】
上記目的を達成するために本発明は、軽量モード無競合時のロック解放において、メモリ同期命令を必要最小限、すなわち特殊識別子による先行解放と本解放の２段解放によってメモリ同期命令を減少させている。具体的には、共有メモリモデルのシステムで、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックの種類を示すビット及び第１の種類のロックに対応してロックを獲得したスレッドの識別子又は第２の種類のロックの識別子を記憶することによりオブジェクトへのロックを管理する場合に、第１のスレッドが保持しているあるオブジェクトへのロックを第２のスレッドが獲得しようとした場合、前記あるオブジェクトの前記ロックの種類を示すビットが第１の種類のロックであることを示しているか判断するステップと、前記第１の種類のロックであることを示している場合には、競合ビットを立てるステップと、前記第１のスレッドが保持しているあるオブジェクトへのロックを解除する際に、前記ロックの種類を示すビットが前記第１の種類のロックであることを示しているか判断するステップと、前記複数のスレッドの識別子と異なる特殊識別子を前記記憶領域に記憶するステップと、前記記憶領域の同期命令を発行するステップと、前記あるオブジェクトのロックを保持しているスレッドが存在しないことを前記記憶領域に記憶するステップと、前記ロックの種類を示すビットが前記第１の種類のロックであることを示している場合には、前記競合ビットが立っているか判断するステップと、前記競合ビットが立っていないと判断された場合には、他の処理を実施せずにロック解除処理を終了するステップと、を実行する。
【００４３】
このようにして、軽量モード無競合時のロック解放では、高価なメモリ同期命令を少なくとも２つ発行することなく、本発明のように２段解放によればメモリ同期命令を１つのみに減少させることができる。
【００４４】
また、前記競合ビットが立っていると判断された場合には、オブジェクトへのアクセスの排他制御と所定の条件が成立した場合のスレッドの待機操作及び待機しているスレッドへの通知操作とを可能にする機構の排他制御状態に前記第１のスレッドが移行するステップと、待機しているスレッドへの通知操作を前記第１のスレッドが実行するステップと、前記所定の条件が非成立でかつ前記特殊識別子が記憶されているとき、前記あるオブジェクトのロックを保持しているスレッドが存在せずかつ、ロックの種類を示すビットが第１の種類のロックになるまで前記第２のスレッドが繁忙待機するステップと、前記第１のスレッドが前記排他制御状態から脱出するステップと、をさらに実行する。
【００４５】
このように、待機しているスレッドへの通知操作を実行するステップと、前記所定の条件が非成立でかつ前記特殊識別子が記憶されているとき、前記あるオブジェクトのロックを保持しているスレッドが存在せずかつ、ロックの種類を示すビットが第１の種類のロックになるまでロック処理を待機する繁忙待機を採用する。
【００４６】
なお、第１の種類のロックとは、オブジェクトに対してロックを実施するスレッドの識別子を当該オブジェクトに対応して記憶することによりロック状態を管理するロック方式である。また、第２の種類のロックとは、オブジェクトへのアクセスを実施するスレッドをキューを用いて管理するロック方式である。
【００４７】
また、共有メモリモデルのシステムで、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックを示すビットを記憶し、オブジェクトへのアクセスを実施するスレッドのキューを記憶することによりオブジェクトへのロックを管理する場合、第１のスレッドが保持しているあるオブジェクトへのロックを第２のスレッドが獲得しようとした場合、前記あるオブジェクトの前記ロックを示すビットがロックを示しているか判断するステップと、前記ロックを示しているビットが立っている場合には、前記あるオブジェクトへのアクセスを実施するスレッドのキューの個数情報を変化させて記憶するステップと、前記第２のスレッドをキューとして記憶することにより、前記あるオブジェクトへのアクセスの待機操作および通知による復帰操作する機構の制御状態に前記第２のスレッドが移行するステップと、前記第１のスレッドが保持しているあるオブジェクトへのロックを解除する際に、前記ロックを示すビットを、前記あるオブジェクトのロックを示していることを前記記憶領域に記憶するステップと、前記キューとして記憶されたスレッドが存在しているか判断するステップと、前記キューとして記憶されたスレッドが存在していることを示している場合には、待機しているスレッドへの通知操作を実行する通知状態に前記第１のスレッドが移行するステップと、前記第１のスレッドが前記通知状態から脱出するステップと、を実行する。
【００４８】
このようにすれば、一般的なスピンサスペンドロックに対して、ロックとアンロックとの各々にアトミックなマシン命令（不可分命令）を必要としない。すなわち、ロックするときにのみ、アトミックなマシン命令を用いるのみで、アンロック時にはアトミックなマシン命令を用いることのない代入等の命令でよい。
【００４９】
前記ロックを示しているビットが立っている場合には、前記あるオブジェクトへのアクセスを実施するスレッドのキューの個数情報を増加させて記憶しかつ、前記あるオブジェクトの前記ロックを示すビットがロックを示しているか判断するステップと、前記ロックを示しているビットが立っていない場合には、前記あるオブジェクトへのアクセスを実施するスレッドのキューの個数情報を減少させて記憶した後に他の処理を実施せずにロック処理を終了するステップと、をさらに実行することができる。
【００５０】
また、共有メモリモデルのシステムで、複数のスレッドが存在し得る状態において、オブジェクトに対応して設けられた記憶領域にロックを示すビットを記憶し、オブジェクトへのアクセスを実施するスレッドのキューを記憶することによりオブジェクトへのロックを管理する場合に、第１のスレッドが保持しているあるオブジェクトへのロックを第２のスレッドが獲得しようとした場合、前記あるオブジェクトの前記ロックを示すビットがロックを示しているか判断するステップと、前記ロックを示しているビットが立っている場合には、前記あるオブジェクトへのアクセスを実施するスレッドのキューの個数情報を変化させて記憶した後に、前記記憶領域の同期命令を発行するステップと、前記第２のスレッドをキューとして記憶することにより、前記あるオブジェクトへのアクセスの待機操作および通知による復帰操作する機構の制御状態に前記第２のスレッドが移行するステップと、前記第１のスレッドが保持しているあるオブジェクトへのロックを解除する際に、前記ロックを示すビットを、前記ロックを示していること及び示していないことと異なる識別子を前記記憶領域に記憶するステップと、前記記憶領域の同期命令を発行するステップと、前記あるオブジェクトのロックを示していないことを前記記憶領域に記憶するステップと、前記キューとして記憶されたスレッドが存在しているか判断するステップと、前記キューとして記憶されたスレッドが存在していることを示している場合には、待機しているスレッドへの通知操作を実行する通知状態に前記第１のスレッドが移行するステップと、前記第１のスレッドが前記通知状態から脱出するステップと、を実行する。
【００５１】
このようにすれば、一般的なスピンサスペンドロックに対して、ロックとアンロックとの各々にアトミックなマシン命令（不可分命令）を必要としない。さらに、同期命令を少なくとも、２つ用いる必要もない。すなわち、メモリをロックするときの前後で同期命令が必要であったが、本発明によれば、２段階の解除により１つの同期命令のみでよいことになる。
【００５２】
この場合、前記ロックを示しているビットが立っている場合には、前記あるオブジェクトへのアクセスを実施するスレッドのキューの個数情報を増加させて記憶しかつ、前記あるオブジェクトの前記ロックを示すビットがロックを示しているか判断するステップと、前記ロックを示しているビットが立っていない場合には、前記あるオブジェクトへのアクセスを実施するスレッドのキューの個数情報を減少させて記憶した後に他の処理を実施せずにロック処理を終了するステップと、をさらに実行することができる。
【００５３】
また、前記ロックを示しているビットが立っている場合でかつ、前記ロックを示していること及び示していないことと異なる識別子を前記記憶領域に記憶している場合、前記あるオブジェクトのロックを保持しているスレッドが存在せずかつ、ロックを示すビットがロックを示していない状態になるまで前記第２のスレッドが繁忙待機するステップと、をさらに実行することもできる。
【００５４】
以上述べた本発明の処理は、専用の装置として実施することも、また、コンピュータのプログラムとして実施することも可能である。さらに、このコンピュータのプログラムは、ＣＤ−ＲＯＭやフロッピー・ディスク、ＭＯ（Ｍａｇｎｅｔｏ−ｏｐｔｉｃ）ディスクなどの記憶媒体、又はハードディスクなどの記憶装置に記憶される。
【００５５】
【発明の実施の形態】
以下、図面を参照して本発明の実施の形態の一例を詳細に説明する。本実施の形態はＳＭＰシステムに本発明を適用したものである。
〔第１実施の形態〕
図１には本発明の処理が実施されるコンピュータの例を示す。コンピュータ１０００は、ハードウエア１００と、ＯＳ（Ｏｐｅｒａｔｉｎｇ  Ｓｙｓｔｅｍ）２００、アプリケーション・プログラム３００を含む。ハードウエア１００は、ＣＰＵ（１又は複数）１１０及びＲＡＭ１２０等のメインメモリ、及びハードウェア資源にアクセスするための入出力インタフェース（Ｉ／Ｏインタフェース）１３０を含んでいる。ＯＳ２００は、カーネル側領域２００Ａとユーザ側領域２００Ｂから構成されており、ＡＰＩ（Ａｐｐｌｉｃａｔｉｏｎ  Ｐｒｏｇｒａｍｍｉｎｇ  Ｉｎｔｅｒｆａｃｅ）２１０を含んでいる。また、ＯＳ２００は、ハードウエア１００とアプリケーション・プログラム３００との間の操作を可能にする、すなわち、アプリケーション・プログラム３００として動作する複数のスレッドを可能にする機能を有するスレッド・ライブラリ２２０を備えている。このスレッド・ライブラリ２２０はキューロックに必要な機能も提供する。また、アプリケーション・プログラム３００は、モニタ機能、本発明のロック及びアンロック機能を含む。また、データベース言語の場合には、データベース・マネイジメント・システム３３０をＯＳ２００上に設け、さらにその上でアプリケーション３４０を実行する場合もある。さらに、Ｊａｖａ言語の場合には、Ｊａｖａ  ＶＭ（Ｖｉｒｔｕａｌ  Ｍａｃｈｉｎｅ）３１０をＯＳ２００上に設け、さらにその上でアプレット又はアプリケーション３２０を実行する場合もある。アプレット又はアプリケーション３２０もマルチ・スレッドで実行され得る。Ｊａｖａ言語では、Ｊａｖａ  ＶＭ３１０に、モニタ機能、ロック及びアンロック機能が組み込まれる場合もある。また、Ｊａｖａ  ＶＭ（３１０）はＯＳ２００の一部として組み込まれる場合もある。また、コンピュータ１０００は補助記憶装置を有しない、所謂ネットワークコンピュータ等でもよい。
【００５６】
（二段解放によるメモリ同期命令の削減）
発明が解決しようとする課題の欄で説明したように、複合ロックの例３では、ＳＭＰシステムで実装した場合、軽量モード無競合時のロック解放において、高価なメモリ同期命令を２つ発行しなくてはならない。そこで、本実施の形態では、特殊識別子による先行解放と本解放の２段解放によってメモリ同期命令を１つのみに減少させている。
【００５７】
まず、どのスレッドにも割り当てられることのない識別子を１つ選び、ｕｎｌｏｃｋ関数の軽量モード時の手順を、特殊識別子による先行解放、メモリ同期命令、本解放とする。本実施の形態では、先行解放のための特殊識別子としてＳＰＥＣＩＡＬを導入する。
【００５８】
図２に示したように、あるオブジェクトをロックしているスレッドが存在しない場合（（１）の場合）には、ロック用フィールド及び競合ビット共に０が格納される。その後、あるスレッドがそのオブジェクトをロック（軽量ロック）すると、そのスレッドの識別子がロック用フィールドに格納される（（２）の場合）。もし、このスレッド識別子のスレッドがロックを解放するまでに他のスレッドがロックを試みなければ、ロック用フィールドにＳＰＥＣＩＡＬを格納し（（５）の場合）、（１）に戻る。ロックを解放するまでに他のスレッドがロックを試みると、軽量ロックにおける競合が発生したので、この競合を記録するため競合ビットを立てる（（３）の場合）。その後、重量ロックに移行した際には、競合ビットはクリアされる（（４）の場合）。可能であれば、（４）は（１）に移行する。なお、ロック用フィールドの最下位に軽量ロックと重量ロックのモードを表すビット（ＦＡＴ＿ＬＯＣＫビット）設けるようにしたが、最上位に設けるようにしても良い。
【００５９】
この特殊識別子としてＳＰＥＣＩＡＬを導入した処理を以下に示す。
【表５】
0003575593.tif 000008
0003575593.tif 000009
0003575593.tif 000010
【００６０】
上記では、ＩＢＭ  ＳｙＳｔｅｍ／３７０で定義された本来のｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐ＿３７０を用いている。この関数ｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐ（）は、次の作業を原始的に行うものである。
【表６】
0003575593.tif 000011
【００６１】
なお、競合ビットは表４ではｆｌｃ＿ｂｉｔとして示されている。上記表５は、４つの部分からなる。ロック関数の部分（第２２０行乃至第４２０行）、アンロック関数の部分（第１０行乃至第２１０行）、軽量ロックから重量ロックへの遷移であるｉｎｆｌａｔｅ関数の部分（第４４０行乃至第４８０行）、及びモニタの識別子を獲得するｏｂｔａｉｎ＿ｍｏｎｉｔｏｒ関数の部分（第５１０行乃至第５９０行）である。以下、表５の処理を詳細に説明する。なお、表５では、表４のＦＡＴ＿ＬＯＣＫビットに代えてＳＨＡＰＥビットとして示されている。
【００６２】
（１）ロック関数
第２３０行から始まったオブジェクトｏｂｊに対するロック関数の処理では、まず軽量ロックの獲得を試みる（第２５０行及び第２６０行）。この軽量ロックの獲得には、本実施の形態ではｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐのようなアトミックな命令を用いる。この命令では、第１の引き数と第２の引き数が同じ値の場合、第３の引き数を格納するものである。ここでは、オブジェクトｏｂｊのロック用フィールドであるｏｂｊ−＞ｌｏｃｋが０に等しい場合には、ｔｈｒｅａｄ＿ｉｄ（）によりスレッド識別子を獲得して、ロック用フィールドｏｂｊ−＞ｌｏｃｋに格納する。図２の（１）から（２）への遷移を実施したものである。そして、必要な処理を実施するため、リターンする（第２７０行）。もし、オブジェクトｏｂｊのロック用フィールドであるｏｂｊ−＞ｌｏｃｋが０に等しくない場合には、軽量ロックの獲得は失敗し、第３００行に移行する。
【００６３】
次に、モニタ識別子を獲得するｏｂｔａｉｎ＿ｍｏｎｉｔｏｒ（ｏｂｊ）関数の値をｍｏｎという変数に代入し（第３００行）、スレッドはそのモニタの排他制御状態に移行しようとする。すなわちモニタ（ｍｏｎｉｔｏｒ）にエンタ（ｅｎｔｅｒ）しようとする（第３１０行）。もし、排他制御状態に移行することができれば、以下の処理を実施し、もしできなかった場合には、できるまでこの段階で待つ。次に、ｗｈｉｌｅ文の条件を判断する。すなわち、ロック用フィールドｏｂｊ−＞ｌｏｃｋとＳＨＡＰＥビットのビットごとのＡＮＤを実施し、ＳＨＡＰＥビットが立っているか判断する（第３２０行）。ここでは、現在重量ロックに移行しているのか、軽量ロック中なのかを判断している。もし、ＳＨＡＰＥビットが立っていなければ（軽量ロック中）、この計算の結果は０となるから、ｗｈｉｌｅ文以下の処理を実施する。一方、ＳＨＡＰＥビットが立っている場合（重量ロック中）、ｗｈｉｌｅ文以下の処理を実施せずに、モニタにエンタした状態のままになる。このようにＳＨＡＰＥビットが立っている場合に、モニタにエンタできた場合には、重量ロックを獲得できたということを意味しており、このモニタからイグジット（ｅｘｉｔ）することなく（すなわち排他制御状態を脱出することなく）、このスレッドはオブジェクトに対する処理を実施する。
【００６４】
一方、第３２０行でＳＨＡＰＥビットが立っていないと判断された場合には、軽量ロックの競合が発生していることを意味するので、ｆｌｃ＿ｂｉｔをセットする（第３３０行、ｓｅｔ＿ｆｌｃ＿ｂｉｔ（ｏｂｊ））。これは、図２の（２）から（３）への遷移に相当する。そして、もう一度軽量ロックを獲得できるか判断する（第３４０行及び愛３５０行）。軽量ロックを獲得できる場合には軽量ロックから重量ロックへの遷移のためのｉｎｆｌａｔｅ関数の処理を実施する（第３６０行）。一方、軽量ロックが獲得できずかつｕｎｌｏｃｋ変数がＳＰＥＣＩＡＬである場合には、繁忙待機する。すなわち、本実施の形態では、繁忙待機を再導入している。これは、先行解放は観測されたが本解放は観測されていない場合であり、本解放が目前に迫っているときである。ＳＭＰシステムの場合、この時機では、繁忙待機したほうが好ましいためである。軽量ロックが獲得できずかつｕｎｌｏｃｋ変数がＳＰＥＣＩＡＬでもない場合には、モニタの待機状態（ｗａｉｔ）に移行する（第４００行）。モニタの待機状態は、モニタから脱出してサスペンドするものである。このように、軽量ロックで競合が生じると、競合ビットであるｆｌｃ＿ｂｉｔがセットされ、軽量ロックを獲得できない場合には、モニタの待機状態に移行する。この待機状態に入ると、後にｉｎｆｌａｔｅ関数の処理又はアンロックする際に通知（ｎｏｔｉｆｙ又はｎｏｔｉｆｙ＿ａｌｌ）を受けることになる。
【００６５】
（２）ｉｎｆｌａｔｅ関数
次に、ｉｎｆｌａｔｅ関数の処理を説明する。ここではまず、競合ビットがクリアされる（第４５０行、ｃｌｅａｒ＿ｆｌｃ＿ｂｉｔ）。そして、モニタの通知操作（ｍｏｎｉｔｏｒ＿ｎｏｔｉｆｙ＿ａｌｌ）を実施する（第４６０行）。ここでは、待機状態の全てのスレッドに起きる（ｗａｋｅ  ｕｐ）よう通知する。そして、ロック用フィールドＯｂｊ−＞ｌｏｃｋに、モニタの識別子を格納した変数ｍｏｎとセットされたＳＨＡＰＥビットをビットごとにＯＲした結果を格納する（第４４０行、ｍｏｎ  ｜  ＳＨＡＰＥ）。すなわち、図２の（３）から（４）の状態に遷移させたものである。これで軽量ロックから重量ロックへの遷移は完了する。なお、第３６０行の処理が終了すると、再度ｗｈｉｌｅ文の条件をチェックすることになるが、既にＳＨＡＰＥビットが立っているので、この場合にはｗｈｉｌｅ文から脱出して、モニタにエンタしたままとなる。すなわち、ｗｈｉｌｅ文の中の処理を実行しない。
【００６６】
通知を受けた全てのスレッドは第４００行において陰にモニタにエンタしようとするが、モニタにエンタする前に待機することになる。これは、通知を行ったスレッドはアンロック処理を実施するまでモニタからイグジットしていないからである。
【００６７】
（３）アンロック関数
次に、アンロック関数の処理について説明する。アンロック関数は軽量ロックのアンロックと、重量ロックのアンロックを取扱う。
【００６８】
軽量ロックのアンロック
軽量ロックのアンロックでは、まず、ロック用フィールドｏｂｊ−＞ｌｏｃｋとＳＨＡＰＥビットのビットごとのＡＮＤを計算し、その値が０であるか判断する（第２００行）。これは、ロック関数のｗｈｉｌｅ文の条件と同じであって（第３２０行）、軽量ロック中であるかどうか判断するものである。軽量ロック中である場合には、特殊識別子による先行解放を実施する（第３０行：ｏｂｊ−＞ｌｏｃｋ＝ＳＰＥＣＩＡＬ）。これは、図２の（２）から（５）への遷移に相当する。そして、メモリ同期命令（第４０行：ＭＥＭＯＲＹ＿ＢＡＲＲＩＥＲ（  ））を行った後、本解放のため、ロック・フィールドｏｂｊ−＞ｌｏｃｋに０を格納する（第５０行）。これは、図２の（５）から（１）への遷移に相当する。
【００６９】
このようにして、軽量モード無競合時のロック解放において、高価なメモリ同期命令を２つ発行することなく、２段解放によってメモリ同期命令を１つのみに減少させている。すなわち、本発明におけるメモリ同期命令がこの第４０行である。このようにして、ｕｎｌｏｃｋ関数の軽量モード時の手順を、特殊識別子による先行解放、メモリ同期命令、本解放としている。これにより、ロックを保持しているスレッドが存在しないことが記録される。そして、競合ビットが立っているか判断する（第６０行、ｔｅｓｔ＿ｆｌｃ＿ｂｉｔ）。軽量ロックで競合が生じていなくとも、第６０行のみは実施しなければならない。競合ビットが立っていない場合には、アンロック処理を終了する。
【００７０】
一方、競合ビットが立っている場合には、ロック関数の第３００行及び第３１０行と同様に、変数ｍｏｎにモニタの識別子を格納し（第７０行）、当該モニタ識別子のモニタにエンタしようとする（第８０行）。すなわち、そのスレッドはモニタの排他制御状態に入ろうとする。もしモニタにエンタできた場合には、もう一度、競合ビットが立っていることを確認し（第９０行）、もし立っていれば、モニタにおいて待機状態のスレッドの１つに起動を通知する（第１００行、ｍｏｎｉｔｏｒ＿ｎｏｔｉｆｙ（ｍｏｎ））。なお、モニタにエンタできない場合には、モニタにエンタできるまで待機する。そして通知を行ったスレッドは、モニタの排他制御状態から脱出する（第１１０行、ｍｏｎｉｔｏｒ＿ｅｘｉｔ（ｍｏｎ））。
【００７１】
第１００行で通知を受けたスレッドは、第４００行で陰にモニタにエンタする。そして第９０行に戻りその処理を実施する。通常、第１００行で通知を受けたスレッドは、通知を行ったスレッドがモニタの排他制御状態を脱出した後にモニタの排他制御状態に入り、競合ビットを立てた後に、軽量ロックを獲得し、ｉｎｆｌａｔｅ関数の処理を実施することにより重量ロックに遷移する。
【００７２】
本実施の形態では、メモリ同期命令は１つであるが、上記の複合ロックの例３と略同様の議論を展開することにより、通知保証が達成されていることがわかる。すなわち、スレッドＴがモニタ待機に入ったとする。スレッドＴが原始命令に失敗した時刻をｔとすると、時刻ｔより以前にＦＬＣビットはセットされている。ここで、時刻ｔにおけるロックフィールドの値は、ＳＰＥＣＩＡＬでもない点に注意されたい。
【００７３】
そして、別のスレッドＳが時刻ｔで軽量ロックを保持している。しかも、時刻ｔにおけるロックフィールドの値がＳＰＥＣＩＡＬでもないことから、時刻ｔでスレッドＳはＳＹＮＣ命令を実行していない。すなわち、ＦＬＣビットのテストは時刻ｔより後である。特に、本解放とＦＬＣビットのテストが逆順に実行されたとしてもそうである。
以上のことにより通知保証は達成されている。
【００７４】
なお、本実施の形態では、繁忙待機が再導入されているが、それは極めて限定的なものである。のみならず、ＳＭＰシステムにおいては、このような繁忙待機はむしろ有効ですらある。その理由は、本実施の形態において繁忙待機するのは、先行解放は観測されたが本解放は観測されていない場合である。すなわち、本解放が目前に迫っているときである。ＳＭＰシステムの場合、こうした時機では、モニタ待機しコンテキスト切替えを行うより、繁忙待機したほうが得策である。
【００７５】
〔第２実施の形態〕
本発明は、一般的なスピンサスペンド・ロック（スピンロックとキューロックとを組み合わせた複合ロック）に対して有効である。すなわち、次に示すように、一般的なスピンサスペンド・ロックで表すことができる。以下の説明では、この一般的なスピンサスペンド・ロックを、一般複合ロックという。なお、スピンサスペンド・ロックは広く応用されており、ＯＳ／２のｃｒｉｔｉｃａｌ  ｓｅｃｔｉｏｎ、ＡＩＸのｐｔｈｒｅａｄｓライブラリのｍｕｔｅｘ変数の実装においても使用されている。しかし、無競合時の性能を考えた場合、既存のアルゴリズムは、ロック獲得及び解放にそれぞれ原始命令を必要とするのに対して、本実施の形態の一般複合ロックは、ロック獲得においてのみ原始命令を必要とするものである。なお、本実施の形態は、上記の実施の形態と略同様の構成のため、同一部分には同一符号を付して詳細な説明を省略する。
【００７６】
まず、本実施の形態の処理のうちロック処理を説明する。図３に示すように、ステップ２０００において原始命令を用いた軽量ロックの獲得を試みて、次のステップ２０１０において獲得に成功したか否かを判断し、獲得に成功したときは、本ルーチンを終了する。獲得に失敗したときは、すでに他のスレッドによりロックされているため、サスペンド・モードへ移行し、次のステップ２０２０において、ｐｔｈｒｅａｄｓライブラリが提供するものと同様のセマンティクスを有するｍｕｔｅｘ変数を用いたフィールドをロックする。次のステップ２０３０では、待機スレッドの数を表すフィールドの値を増加する。すなわち、現在のスレッドを、待機しているスレッドに追加すべく表明する。次のステップ２０４０では、再度軽量ロックの獲得を試みる。獲得に成功したときは、ステップ２０６０においてフィールドの値を減少した後にｍｕｔｅｘ変数を用いたフィールドをアンロックする。一方、獲得に失敗したときは、ステップ２０８０において獲得を試みたスレッドをキューとして待機しステップ２０４０へ戻る。
【００７７】
次に、アンロック処理を説明する。図４に示すように、ステップ２１００においてロック用のフィールドを解放する状態にした後に次のステップ２１１０において待機スレッドの数を表すフィールドの値を獲得する。待機スレッドがないときはフィールドの値は「０」であるため、この場合には本ルーチンを終了する。一方、待機スレッドが存在するときは、ステップ２１２０で肯定され、ステップ２１３０においてｍｕｔｅｘ変数を用いたフィールドをロックする。次のステップ２１４０では再度待機スレッドの数を表すフィールドの値を獲得して次のステップ２１５０において再度待機スレッドが存在するか否かを判断する。このときに、待機スレッドがないときは、ステップ２１７０においてｍｕｔｅｘ変数を用いたフィールドをアンロックした後に本ルーチンを終了する。一方、待機スレッドが存在するときは、ステップ２１６０において待機しているスレッドを読み出して（通知し）、ステップ２１７０においてｍｕｔｅｘ変数を用いたフィールドをアンロックした後に本ルーチンを終了する。
【００７８】
上記の処理の流れに沿った一般複合ロックのアルゴリズムを以下に示す。
【表７】
0003575593.tif 000012
0003575593.tif 000013
【００７９】
本アルゴリズムでは、ｐｔｈｒｅａｄｓライブラリが提供するものと同じセマンティクスを有するｍｕｔｅｘ変数とｃｏｎｄｖａｒ変数を用いて、ｔｓｋ＿ｓｕｓｐｅｎｄ関数とｔｓｋ＿ｒｅｓｕｍｅ関数を記述しているが、基本的にアルゴリズムの説明のためである。一般複合ロックは、スレッドライブラリ上に作成されるものではなく、むしろカーネル空間の中でよりカスタマイズされた形で作成されるべきものである。
【００８０】
なお、ｃｏｎｄｖａｒ＿ｗａｉｔ（）関数は、条件付変数であり、第１引数を変数として待機しかつｍｕｔｅｘ変数を解除するものである。これに対応して、ｃｏｎｄｖａｒ＿ｓｉｇｎａｌ（）関数は、通知を行うものである。
【００８１】
表６において、第１０行乃至第５０行は、用いるデータの構造、第８０行乃至第１２０行はロック関数、第１４０行乃至第１８０行はアンロック関数、第２００行乃至３２０行はサスペンド関数、第３４０行乃至３９０行はレジューム関数を示している。
【００８２】
表６から理解されるように、ロック関数は、単純なスピンロックを含むこととなる。また、アンロック関数は、現在、フィールドｔｓｋ−＞ｗｃｏｕｎｔのテストを含むことを示す。これはロックを獲得しているスレッドがサスペンド・ロックに後退していた他のスレッド用のロック解除にいくらかの動作をとることを必要とするか否かを示している。しかし、第１６０行のｉｆ文の条件が成立しない限り、ｔｓｋ＿ｒｅｓｕｍｅ関数は実行されない。これは、単純なテストを行うものであって、重要な処理を行うものではない。従って、表６のアルゴリズムは、最も速くスピンロックしているアルゴリズムと比較すると単純なテストを１つ加えているだけである。
【００８３】
また、ｔｓｋ＿ｓｕｓｐｅｎｄ関数は、呼んでいるスレッドがスピン・ロックを得ようとするｗｈｉｌｅ  ｌｏｏｐを含んでいる。これはｓｐｉｎ−ｗａｉｔループでなくｓｕｓｐｅｎｄ−ｗａｉｔループである。すなわち、第２９０行で待機している何れのスレッドも休眠状態が解除されることを約束しなければならない。このために、フィールドｔｓｋ−＞ｗｃｏｕｎｔ内の現在待機しているスレッドの数の、情報を獲得し続けることになる。カウンタ（ｔｓｋ−＞ｗｃｏｕｎｔ）は、ｍｕｔｅｘの保護の下で増加そして減少する。従って、同じ保護の下にカウンタを検査することによって、どれだけのスレッドが待機しているか否かを、正しく確認することができる。
【００８４】
ところで、アンロック関数は、いかなる保護もないカウンタをチェックして、カウンタの間違った値を読み込む場合があるが本実施の形態では、先と同様の推論を展開することにより、休眠状態の解除通知は保証される。
【００８５】
（ＳＭＰシステムへの具体的適用）
ところで、一般複合ロックをＳＭＰシステムすなわち先進的ＳＭＰマシンで実装する場合、複合ロックの例３と同様の問題に遭遇する。すなわち、無競合時のロック解放に、メモリ同期命令を２つ発行しなければならない。具体的には、表６の第１５０行：「ｔｓｋ−＞ｌｏｃｋ  ＝  ＵＮＬＯＣＫＩＮＧ；」の前後である。この問題は上記実施の形態と同様の処理によって、解決できる。このＳＭＰシステムへ適用した一般複合ロックを、本実施の形態では、ＳＭＰ複合ロックと呼ぶ。
【００８６】
まず、ロック処理を説明する。図５に示すように、原始命令を用いた軽量ロックの獲得を試み（図３のステップ２０００）、獲得に成功したか否かを判断し（図３のステップ２０１０）、獲得に成功したときは、本ルーチンを終了する。獲得に失敗したときは、すでに他のスレッドによりロックされているため、サスペンド・モードへ移行し、ｐｔｈｒｅａｄｓライブラリが提供するものと同様のセマンティクスを有するｍｕｔｅｘ変数を用いたフィールドをロックする（図３のステップ２０２０）。次に、待機スレッドの数を表すフィールドの値を増加する（図３のステップ２０３０）。すなわち、現在のスレッドを、待機しているスレッドに追加すべく表明する。次に、ステップ２２００において、メモリ同期命令（ＭＥＭＯＲＹ＿ＢＡＲＲＩＥＲ（））を発行した後に、次のステップ２２１０において変数ｕｎｌｏｃｋｅｄを解放する。このメモリ同期命令は、上述したＳＹＮＣ命令と同様に、ロック保持中に行ったメモリ操作命令をロック解放前に完了することを保証する機能を有している。
【００８７】
この後に、再度軽量ロックの獲得を試みる（図３のステップ２０４０）。獲得に成功したときは、フィールドの値を減少（図３のステップ２０６０）した後にｍｕｔｅｘ変数を用いたフィールドをアンロックする（図３のステップ２０７０）。一方、獲得に失敗したときは、ステップ２２３０において変数ｕｎｌｏｃｋｅｄが充填されているか否かを判断し、肯定判断の場合にはそのままステップ２０４０へ戻り、否定判断の場合には獲得を試みたスレッドをキューとして待機（図３のステップ２０８０）しステップ２０４０へ戻る。
【００８８】
次に、アンロック処理を説明する。図６に示すように、ステップ２４００においてロック用のフィールドに先行解放を示す値を代入した後にステップ２４１０においてメモリ同期命令を発行する。次のステップ２４２０ではロックフィールドを解放し、次のステップ２４３０において待機スレッドの数を表すフィールドの値を獲得する。待機スレッドがないときはフィールドの値は「０」であるため、この場合には本ルーチンを終了する。一方、待機スレッドが存在するときは、図４のステップ２１３０以降の処理と同様に、ｍｕｔｅｘ変数を用いたフィールドをロックし、再度待機スレッドの数を表すフィールドの値を獲得して再度待機スレッドが存在するか否かを判断する。このときに、待機スレッドがないときは、ｍｕｔｅｘ変数を用いたフィールドをアンロックし、待機スレッドが存在するときは、待機しているスレッドを読み出し（通知し）た後に、ｍｕｔｅｘ変数を用いたフィールドをアンロックした後に本ルーチンを終了する。
【００８９】
上記の処理の流れに沿ったＳＭＰ複合ロックのアルゴリズムを以下に示す。ここでは、上述のＩＢＭ  ＳｙＳｔｅｍ／３７０で定義された本来のｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐ＿３７０を用いる。この関数ｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐ＿３７０を用いるとした場合、ｔｓｋ＿ｕｎｌｏｃｋ関数、ｔｓｋ＿ｓｕｓｐｅｎｄ関数は次のようになる。他の２つの関数は同じである。
【表８】
0003575593.tif 000014
【００９０】
このように、本実施の形態では、割り当てられてない識別子を１つ選び、ｕｎｌｏｃｋ関数の軽量モード時の手順を、特殊識別子による先行解放、メモリ同期命令、本解放とする。本実施の形態では、先行解放のための特殊識別子としてＵＮＬＯＣＫＩＮＧを導入している。すなわち、アンロック関数において、フィールドｔｓｋ−＞ｌｏｃｋの値をＬＯＣＫＥＤあるいはＵＮＬＯＣＫＥＤ以外のＵＮＬＯＣＫＩＮＧに一旦設定し、メモリバリヤした後に、アンロックしている。従って、特殊識別子による先行解放と本解放の２段解放で１つのみのメモリ命令での処理を可能にしている。
【００９１】
【発明の効果】
以上説明したように本発明によれば、軽量モード無競合時のロック解放において、すなわち特殊識別子による先行解放と本解放の２段解放によってメモリ同期命令を必要最小限に減少させることができる、という効果がある。
【図面の簡単な説明】
【図１】本発明の処理が実施されるコンピュータの一例を示す図である。
【図２】本発明のモードの遷移、並びに各モードにおけるロック用フィールド（ＳＨＡＰＥビットを含む）及び競合ビットの状態を説明するための図であり、（１）はロックなし、（２）は軽量ロックで競合なし、（３）は軽量ロックで競合あり、（４）は重量ロック、（５）は特殊識別子による先行解放の状態を示す。
【図３】本発明の一般複合ロックのロック処理の流れを示すフローチャートである。
【図４】本発明の一般複合ロックのアンロック処理の流れを示すフローチャートである。
【図５】本発明のＳＭＰ複合ロックのロック処理の流れを示すフローチャートである。
【図６】本発明のＳＭＰ複合ロックのアンロック処理の流れを示すフローチャートである。
【図７】複合ロックの例３のモードの遷移、並びに各モードにおけるロック用フィールド（ＦＡＴ＿ＬＯＣＫビットを含む）及び競合ビットの状態を説明するための図であり、（１）はロックなし、（２）は軽量ロックで競合なし、（３）は軽量ロックで競合あり、（４）は重量ロックの状態を示す。
【符号の説明】
１０００  コンピュータ
１００    ハードウエア
２００    ＯＳ
２００Ａ  カーネル領域
２００Ｂ  ユーザ領域
２１０    ＡＰＩ
２２０    スレッドライブラリ
３００    アプリケーション・プログラム
３１０    Ｊａｖａ  ＶＭ
３２０    Ｊａｖａ  アプレット／アプリケーション
３３０    データベースマネイジメントシステム
【図１】
0003575593.tif 000015
【図２】
0003575593.tif 000016
【図３】
0003575593.tif 000017
【図４】
0003575593.tif 000018
【図５】
0003575593.tif 000019
【図６】
0003575593.tif 000020
【図７】
0003575593.tif 000021