(57)【要約】  情報処理システムは、所定のlockの獲得を要求しているスレッドの状態遷移に応じて、lockの解放をspinlock方式で待っているスレッド数を示す待機スレッド数情報を更新する待機スレッド数情報更新手段と、待機スレッド数情報更新手段が更新する待機スレッド数情報と、予め定められたspinlock方式で待つスレッド数の上限値とに基づいて、lockの獲得を要求するスレッドの待機方式を決定する待機方式決定手段とを含むことを特徴とする。
2011096163.tif 000002
【特許請求の範囲】
【請求項１】
所定のlockの獲得を要求しているスレッドの状態遷移に応じて、前記lockの解放をspinlock方式で待っているスレッド数を示す待機スレッド数情報を更新する待機スレッド数情報更新手段と、
前記待機スレッド数情報更新手段が更新する前記待機スレッド数情報と、予め定められたspinlock方式で待つスレッド数の上限値とに基づいて、前記lockの獲得を要求するスレッドの待機方式を決定する待機方式決定手段とを
含むことを特徴とする情報処理システム。
【請求項２】
待機スレッド数情報更新手段は、カーネル空間からユーザ空間に配置された待機スレッド数情報にアトミックにアクセスし、前記待機スレッド数情報を更新する
請求項１記載の情報処理システム。
【請求項３】
待機スレッド数情報更新手段は、待機方式決定手段の決定結果に基づいて待機スレッド数情報を更新する
請求項１又は請求項２記載の情報処理システム。
【請求項４】
待機スレッド数情報更新手段は、lockの獲得を要求するスレッドが休眠状態に移行する場合、前記スレッドの移行前の状態に基づいて待機スレッド数を更新する
請求項１から請求項３のうちのいずれか１項に記載の情報処理システム。
【請求項５】
lockによって保護されるクリティカルセクションに関して、前記クリティカルセクションを実行しているスレッドが存在するか否かを示す情報とともに、spinlock方式で前記lockの解放を待つスレッド数およびblock方式で前記lockの解放を待つスレッドの数を示す待機スレッド数情報を含む排他制御用データを記憶する記憶手段と、
スレッドの前記lockに関する状態として、lock要求なし状態、lock獲得状態、spinlock方式でのlock解放待ち状態、又はblock方式でのlock解放待ち状態のいずれかの遷移に関して、状態遷移先を決めるアルゴリズムの入力として前記待機スレッド数情報を用いる制御手段と、
前記制御手段によるスレッドの状態遷移に応じて前記待機スレッド数情報を更新する待機スレッド数情報更新手段とを含み、
前記制御手段は、前記待機スレッド数情報更新手段が更新する待機スレッド数情報に基づいて、spinlock方式で前記lockの解放を待つスレッド数を、予め定められた上限値を超えないように制御する
ことを特徴とする情報処理システム。
【請求項６】
カーネル・プログラムからの排他制御用データの更新操作に用いられるユーザ空間アトミック・アクセス手段を含む
請求項５記載の情報処理システム。
【請求項７】
所定のlockの獲得を要求しているスレッドの状態遷移に応じて、前記lockの解放をspinlock方式で待っているスレッド数を示す待機スレッド数情報を更新し、
前記待機スレッド数情報と、予め定められたspinlock方式で待つスレッド数の上限値とに基づいて、前記lockの獲得を要求するスレッドの待機方式を決定する
ことを特徴とする排他制御方法。
【請求項８】
カーネル空間からユーザ空間に配置された待機スレッド数情報にアトミックにアクセスし、前記待機スレッド数情報を更新する
請求項７記載の排他制御方法。
【請求項９】
コンピュータに、
所定のlockの獲得を要求しているスレッドの状態遷移に応じて、前記lockの解放をspinlock方式で待っているスレッド数を示す待機スレッド数情報を更新する待機スレッド数情報更新処理と、
前記待機スレッド数情報と、予め定められたspinlock方式で待つスレッド数の上限値とに基づいて、前記lockの獲得を要求するスレッドの待機方式を決定する待機方式決定処理とを
実行させるための排他制御用プログラム。
【請求項１０】
コンピュータに、
待機スレッド数情報更新処理で、カーネル空間からユーザ空間に配置された待機スレッド数情報にアトミックにアクセスし、前記待機スレッド数情報を更新する処理を実行させる
請求項９記載の排他制御用プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、排他制御を行う情報処理システム、排他制御方法および排他制御用プログラムに関する。
【背景技術】
【０００２】
複数のスレッドを並行して実行するように構成された情報処理システムでは、スレッドによる処理の実行中の任意の時点で、他のスレッドによる他の処理の実行が割り込むことがある。これらの処理同士間に関連性がない場合には、スレッドによる処理の実行途中に他のスレッドによる他の処理が割り込んでも得られる結果に変わりはなく、問題となることはない。【０００３】
しかし、これらの処理同士間に関連性がある場合には、スレッドによる処理の実行途中に他のスレッドによる他の処理が割り込むと得られる結果が異なり、問題となることがある。【０００４】
例として、2つのスレッドが同一の変数に1を加える処理（すなわち、その変数を読み込んで1を加え、その結果を書き戻す処理）を行うことを考える。ここで問題となるのは、一方のスレッドが変数を読み込んでから1を加えた結果を書き戻すまでの間に、他方のスレッドによる処理（変数に1を加える処理）が割り込んだ場合である。【０００５】
割り込みが生じない場合には、2つのスレッドが各々変数に1を加える操作を行ない、変数の値は２増加する。各スレッドが行う処理の内容から考えると、この処理結果は正しい。【０００６】
しかしながら、前述したように一方のスレッドによる処理の実行途中に、他方のスレッドによる処理が割り込むという順で処理が進められると、最初の処理は、割り込んだ処理による変数の更新を感知することなく、当初の値に1を加えた値を変数に書き戻すことになる。したがって、2つのスレッドが変数に1を加える操作を行なったにも関わらず、変数は1増加するだけであり、正しい結果を得ることができない。【０００７】
このように、処理の途中で他処理に割り込まれると問題が発生する処理区間（上記の例では、データを読み込んでから加工した結果を書き戻すまでの区間）をクリティカルセクションと呼び、他処理に割り込まれないための制御を明示的に行うことになっている。【０００８】
プログラム実行を担うプロセッサが1個であれば、クリティカルセクションに入る時点で他処理への切り換えを禁止し、そこから出る時点で他処理への切り換えを許可することで、その期間中に他処理が割り込まないことを保証できる。プロセッサが1個の場合、あるプログラムをスレッドとして実行中に他プログラムの実行（他スレッド）が割り込むのは、最初のスレッド実行中にスレッド切り換えの契機となる何らかの事象が発生し、オペレーティング・システムがスレッド切り換えを行うためである。従って、オペレーティング・システムに対して他処理（他スレッド）への切り換えを禁止するように指示しておくことにより、スレッド切り換え禁止状態においてスレッド切り換えの契機となる何らかの事象が発生しても、その時点ではスレッド切り換えを行わず、最初のプログラムが他処理（他スレッド）への切り換えを許可した時点でスレッド切り換えを行うように制御することが可能だからである。【０００９】
一方、マルチプロセッサ・システムでは、他処理への切り換えを禁止するだけでは、正しい処理結果が得られることを保証できない。他処理への切り換えを禁止する制御は、そのプログラムを実行しているプロセッサに対しては有効であるが、他プロセッサによるプログラム実行には影響を与えないからである。【００１０】
他プロセッサによるプログラム実行がクリティカルセクションに入らないようにするための方法として一般的に行われているのは、クリティカルセクションを実行中のスレッドが存在するか否かを示すフラグ（以降、lock word）を用意する、という対処である。なお、以降の説明において、クリティカルセクションの実行権（クリティカルセクションへの侵入権）を、lockという。【００１１】
具体的には、プロセッサは、スレッドがクリティカルセクションに入る時点でlock wordを確認し、次の1)又は2)に示す処理を実行する。1) lock wordが「未使用を示す値（以降、unlockedと表記）」であれば、lock wordを「使用中を示す値（以降、lockedと表記）」に変更してクリティカルセクションの処理を実行する。また、2) lock wordがlockedであれば、lock wordがunlockedになるまで待機した後、lock wordをlockedに変更してクリティカルセクションの処理を実行する。そして、プロセッサは、クリティカルセクションの実行を終了した時点でlock wordをunlockedに戻す。以上の制御を行うことにより、他プロセッサが実行する処理と自プロセッサが実行する処理とが、クリティカルセクション上で競合するという問題が発生しない。【００１２】
クリティカルセクションには、上記に示した1スレッドのみが実行可能なものの他、実行可能なスレッド数に上限があるものがある。また、write lock（書き込み等の処理に係るlock）とread lock（読み込み等の処理に係るlock）という２種類のlockがあるread-write lockがある。実行可能なスレッド数に上限のあるlockは、1スレッドのみが実行可能なlockを、実行可能なスレッド数の上限値という観点で汎用化したものと考えられる。read-write lockについては、write lockを獲得してのクリティカルセクション処理を実行できるスレッド数が1に制限されている一方、read lockについては、同時実行可能なスレッド数の上限はなく、write lockを獲得して処理を進めているスレッドがない限りは、read lockを獲得してクリティカルセクション処理を実行できる、というものである。【００１３】
次に、lockを用いてクリティカルセクションの実行制御を行う際の一般的な待ち合わせ動作を説明する。あるスレッドがクリティカルセクションに入る時点でlock wordがlockedであり、クリティカルセクションの実行を直ちに開始することができない場合、そのスレッドは、lock wordがunlockedになるまで待機する必要がある。この方式には、次の1)及び2)に示す２種類の方式がある。1)lock wordがunlockedに変更されるまで、スレッドがプロセッサを使ってlock wordをチェックし続けるspinlock方式（以下、単にspinlock）と、2)スレッドがプロセッサの利用を中断して休眠状態（以下、sleep）に入るとともに、クリティカルセクションを実行しているスレッドに対してクリティカルセクションの実行を完了した時点で起床処理を行うように依頼するblock方式（以下、単にblock）とである。また、spinlockとblockとを組み合わせた方式、すなわち、最初はspinlockに則して待機し、時間が経つとblockに則して待機するという方式も用いられることが多い。【００１４】
Spinlockでは、スレッドに要求されている本来の処理ではないlock解放待ちという処理のためにプロセッサを使うため、プロセッサ資源の消費が増大するという点が短所となる。その反面、lockを保持しているスレッドによるlock解放操作の時点から、loopを待っているスレッドがlockを獲得してクリティカルセクションの処理を開始する時点までの時間（ハンドオーバー時間）が短い点がspinlockの長所である。Blockの長所・短所は、spinlockの裏返しである。具体的には、Blockでは、プロセッサの使用を停止するため、プロセッサ資源の消費を抑えることができるという点が長所となる。その反面、lockを保持しているスレッドによるlock解放操作の時点から、スレッドがlockを獲得してクリティカルセクションの処理を開始する時点までの時間（ハンドオーバー時間）が長い点がBlockの短所である。なお、block方式を採用する場合には、lock wordの他に、クリティカルセクションの状態を管理する変数として、待機中のスレッドが存在していることを示すフラグを加えることになる。【００１５】
何れの方法で待ち合わせを行うにしても、その間はスレッド本来の処理を実行できないため、情報処理システムが持つ能力や性能の有効活用を阻害する要因となる。特に、近年のマルチコア・プロセッサ普及に伴って一般化している多数のプロセッサを搭載した情報処理システムでは、このlock待ちが性能ボトルネックとなる状況が多くなっており、lock待ちを効率的に行うための方法が求められている。【００１６】
関連する技術として、例えば、特許文献１には、lock要求されたリソースをlockできない場合に、該当するリソースのlock時間の平均値等に基づいて、lock待ち方式を決定する方法が記載されている。また、例えば、特許文献２には、排他制御装置に対する命令数をカウントし、閾値を超えない範囲に処理を限定する方法が記載されている。【００１７】
ところで、スレッドがクリティカルセクションに入る時点で行うlock wordの値確認（読み込み）と、unlockedだった場合のlockedへの変更（書き込み）との2操作については、クリティカルセクションと同様の扱いが必要となる。このため、マルチプロセッサ向けの機能を有するプロセッサには、この操作を行うための命令が用意されている。【００１８】
例えば、インテル（登録商標）社のx86プロセッサには、cmpxchg命令（非特許文献１を参照）が用意されている。【００１９】
cmpxchg命令は、命令で予約されたレジスタ（eaxレジスタ）、レジスタ・オペランドおよびメモリ・オペランドの３オペランドを使用するものである。そして、cmpxchg命令は、1)メモリ・オペランドの値をプロセッサに読み込む、2-1)その値がeaxレジスタの値と一致する場合には、メモリにレジスタ・オペランドの値を書き込む、2-2)その値がeaxレジスタの値と一致しない場合には、その値をeaxレジスタに書き込む、という一連の操作をアトミックに行う。【００２０】
なお、ここでのアトミックとは、1)のメモリ読み込み操作と2-1)のメモリ書込み操作との間に、他のプロセッサがメモリにアクセスしないことをハードウェア動作によって保証されていることを意味する。また、このcmpxchg命令が行う操作をCompare And Swap（CAS操作）と称することが多い。【００２１】
上記CAS命令を用いてlock操作を行うには、eaxレジスタにunlocked、レジスタ・オペランドにlockedを設定するとともに、メモリ・オペランドをlock wordとしてCAS命令を実行する。lock wordがunlockedの場合には、上記2-1)の処理が実行されるので、lock wordはlockedに書き換えられ、eaxレジスタの値は変化しない。【００２２】
一方、lock wordがlockedの場合には、上記2-2)の処理が実行されるので、lock wordへの書き込みは行われず、eaxレジスタにはlockedが設定される。CAS命令を実行したスレッドは、CAS命令実行後のeaxレジスタの値を調べることで、lock操作が成功したか失敗したかを調べることができ、成否に基づいて、クリティカルセクションを実行するか、lock wordにunlockedが設定されるのを待つ状態に入るのかの判断を行うことができる。【００２３】
クリティカルセクション以外の関連技術としては、ユーザ空間とカーネル空間とに分けるメモリ管理技術（非特許文献２参照）がある。【００２４】
ユーザ空間は、アプリケーション・プログラムが動作するために必要な情報（命令、データなど）を配置するメモリ領域であり、各スレッドに対して独立した領域を有する。この空間は、通常、ページング対象となっており、メモリが逼迫してくると二次記憶装置に退避されることがある。このため、ユーザ空間に配置された情報は、実メモリ上に存在していない場合がある。【００２５】
一方、カーネル空間は、物理デバイスへのアクセスやシステムの管理を行うカーネル（OS）が動作するために必要な情報を配置するメモリ領域であり、全スレッドに共通した空間となっている。【００２６】
ユーザ空間のプログラムを実行中（ユーザ・モード）には、ユーザ空間に配置されたデータ（以下、ユーザ・データ）にアクセスできるが、カーネル空間に配置されたデータ（以下、カーネル・データ）にはアクセスできない。また、カーネル空間のプログラムを実行中（カーネル・モード）には、カーネル空間および実行中のスレッドに属するユーザ空間に配置されたデータにアクセスできるようになっている。【００２７】
この内、カーネル・モードでの実行中にユーザ・データにアクセスする際には、アクセス対象のデータが実メモリに存在しないケースが有り得るので、その状況でもシステムを正しく動作させる必要がある。そのため、カーネル機能として用意されているユーザ空間読み込み手段およびユーザ空間書き込み手段を用いて、ユーザ空間とカーネル空間との間でデータのコピーを行うようになっている。カーネルは、ユーザ・データを加工する場合には、そのデータをユーザ空間読み込み手段によりカーネル空間にコピーしてから加工を行い、その結果をユーザ空間書き込み手段によりユーザ空間に戻す、という順で処理を行う。【００２８】
カーネルからユーザ・データに対するアクセスは、ユーザ空間読み込み手段およびユーザ空間書き込み手段により行うようになっている。そのため、ユーザ空間にlock wordが配置されている場合、カーネルからlock wordに対する読み込み操作と書き込み操作をアトミックに行なう手段がないため、一般的に、lock wordに対するアトミックなアクセス、すなわちクリティカルセクションへの進入権を獲得する操作は、ユーザ空間のプログラムにおいて実施される。
【先行技術文献】
【特許文献】
【００２９】
【特許文献１】特開２００１−０８４２３５号公報
【特許文献２】特開２００２−３１２１８５号公報
【非特許文献】
【００３０】
【非特許文献１】Intel 64 and IA-32 Architectures Software Developer's Manual Volume 2A: Instruction Set Reference, A-M,[平成22年1月26日検索],インターネット〈URL:http://www.intel.com/Assets/PDF/manual/253666.pdf〉
【非特許文献２】Maurice J. Bach, THE DESIGN OF THE UNIX OPERATING SYSTEM, PRENTICE-HALL, INC., Englewood Cliffs, New Jersey 07632, 1986  なお、UNIXは登録商標である。
【発明の概要】
【発明が解決しようとする課題】
【００３１】
しかし、spinlockまたはspinlockとblockとを組合せた方式でlock解放を待つマルチプロセッサ・システムにおいては、lock競合が激しくなると、spinlockによりlock解放を待つプロセッサが多くなり、その結果、プロセッサ資源が浪費されてしまうこととなる。【００３２】
その理由は、あるスレッドがlock待ち状態に移行する場合、spinlockでlock解放を待っているスレッド数を調べる手段がないため、そのlockについてspinlockしているスレッド数が適正数を超えていた場合でも、spinlockによりlock解放を待つことになるためである。【００３３】
また、特許文献１又は特許文献２に記載された方法は、予め求められた閾値などに基づいて、lockの解放を待つ方式を選択するものであるため、lockの獲得を要求する時点の状況に応じて、効率的なlockの解放を待つ方式を選択することはできない。【００３４】
そこで、本発明は、多数のスレッドがspinlock方式でlockの解放を待つことによるプロセッサ資源の浪費を防止することができる情報処理システム、排他制御方法および排他制御用プログラムを提供することを目的とする。
【課題を解決するための手段】
【００３５】
本発明による情報処理システムは、所定のlockの獲得を要求しているスレッドの状態遷移に応じて、lockの解放をspinlock方式で待っているスレッド数を示す待機スレッド数情報を更新する待機スレッド数情報更新手段と、待機スレッド数情報更新手段が更新する待機スレッド数情報と、予め定められたspinlock方式で待つスレッド数の上限値とに基づいて、lockの獲得を要求するスレッドの待機方式を決定する待機方式決定手段とを含むことを特徴とする。【００３６】
本発明による排他制御方法は、所定のlockの獲得を要求しているスレッドの状態遷移に応じて、lockの解放をspinlock方式で待っているスレッド数を示す待機スレッド数情報を更新し、待機スレッド数情報と、予め定められたspinlock方式で待つスレッド数の上限値とに基づいて、lockの獲得を要求するスレッドの待機方式を決定することを特徴とする。【００３７】
本発明による排他制御用プログラムは、コンピュータに、所定のlockの獲得を要求しているスレッドの状態遷移に応じて、lockの解放をspinlock方式で待っているスレッド数を示す待機スレッド数情報を更新する待機スレッド数情報更新処理と、待機スレッド数情報と、予め定められたspinlock方式で待つスレッド数の上限値とに基づいて、lockの獲得を要求するスレッドの待機方式を決定する待機方式決定処理とを実行させることを特徴とする。
【発明の効果】
【００３８】
本発明によれば、多数のスレッドがspinlock方式でlockの解放を待つことによるプロセッサ資源の浪費を防止することができる
【図面の簡単な説明】
【００３９】
【図１】本発明による情報処理システムの構成例を示す説明図である。
【図２】排他制御用データ（lock word）221の一例を示す説明図である。
【図３】プログラムおよびデータのフローの一例を示す説明図である。
【図４】ユーザ空間読み込み処理手段231、ユーザ空間書き込み手段232およびユーザ空間アトミック・アクセス手段233の動作例を示す流れ図である。
【図５】スレッドの状態遷移を示す遷移図である。
【図６】lock獲得処理の動作例を示す流れ図である。
【図７】lock解放処理の動作例を示す流れ図である。
【図８】lock獲得処理におけるlock獲得操作の動作例を示す流れ図である。
【図９】lock獲得処理における休眠操作の動作例を示す流れ図である。
【図１０】lock解放処理の動作例を示す流れ図である。
【図１１】lock解放処理におけるスレッド起床処理の動作例を示す流れ図である。
【図１２】情報処理システムの機能構成例を示す機能ブロック図である。
【図１３】情報処理システムの最小の構成例を示すブロック図である。
【発明を実施するための形態】
【００４０】
次に、本発明の実施形態について図面を参照して説明する。図１は、本発明による情報処理システムの構成例を示す説明図である。図１を参照すると、本発明による情報処理システムは、複数のプロセッサ（中央処理装置）100-1〜100-nとメモリ200とを含む。なお、情報処理システムは、具体的には、プログラムに従って動作するサーバやパーソナルコンピュータ等の情報処理装置によって実現される。
【００４１】
メモリ200は、ユーザ・プログラム210、ユーザ・データ220、カーネル・プログラム230およびカーネル・データ240を記録するための領域を含む。また、カーネル・プログラム230は、ユーザ・データ220にアクセスするためのユーザ空間読み込み手段231、ユーザ空間書き込み手段232およびユーザ空間アトミック・アクセス手段233を含む。
【００４２】
ここで、ユーザ空間アトミック・アクセス手段233は、後述するように、lock word221に対して、アトミックにアクセスする機能を備えている。また、ユーザ空間読み込み手段231およびユーザ空間書き込み手段232は、一般的な技術によるものと同等の機能を備えている。具体的には、ユーザ空間読み込み手段231は、ユーザ・データ220に配置されたデータを読み込み、カーネル・データ240にコピーする機能を備えている。また、ユーザ空間書き込み手段232は、例えば、カーネル・データ240に配置されたデータをユーザ・データ220に書き込む機能を備えている。
【００４３】
なお、ユーザ・プログラム210からユーザ・データ220に対するアクセスや、カーネル・プログラム230からカーネル・データ240に対するアクセスについては、一般的な情報処理システムと同様に制限がない。すなわち、各プロセッサ100-1〜100-nは、特別に設けた手段を用いることなく、プロセッサの機械語命令による読み込み、書き込み、アトミック・アクセスを行うことができる。
【００４４】
これらの手段はそれぞれ概略つぎのように動作する。各プロセッサ100-1〜100-nは、1つ以上のスレッド（図示せず）を生成する。各スレッドは、ユーザ・プログラム210やカーネル・プログラム230から実行すべき機械語命令を読み出し、その機械語命令で規定される処理を実行する。この際、各スレッドは、必要に応じてユーザ・データ220やカーネル・データ240を使用する。以下、本実施形態では、スレッドやプログラムが処理を実行するとの表現を用いるが、具体的には、プロセッサ100がユーザ・プログラム210やカーネル・プログラム230に従って処理を実行する。
【００４５】
図２は、排他制御用データ（lock word）221の一例を示す説明図である。図２を参照すると、本実施形態におけるlock word221は、lock bit2211、spinlock thread数2213およびblock thread数2212を示す情報を含む。lock bit2211は、lock word221に対応するlockを保持してクリティカルセクションを実行中のスレッドが存在するか否かを示す。spinlock thread数2213は、spinlockによりlock解放を待つスレッドの数を示す。block thread数2212は、blockによりlock解放を待つスレッドの数を示す。また、このlock word221は、プロセッサ100が提供するCAS操作などのアトミック操作が取り扱うデータ長となっている。
【００４６】
図３は、プログラムおよびデータのフローの一例を示す説明図である。図３に示す通り、ユーザ・プログラム210は、カーネル・プログラム230の機能を使用する際には、システム・コールを行ってカーネル・モードに遷移し、以てカーネル・プログラム230による処理を実行させる。そして、カーネル・プログラム230による処理が完了すると、カーネル・プログラム230は、ユーザ・プログラム210にリターンしてユーザ・モードに復帰し、以てユーザ・プログラム210による処理を続行させる。
【００４７】
カーネル・プログラム230は、ユーザ・データ220を使用する際には、アクセスの種類に応じて、ユーザ空間読み込み手段231、ユーザ空間書き込み手段232、又はユーザ空間アトミック・アクセス手段233を用いる。
【００４８】
次に、カーネル・プログラム230が含む各手段がユーザ・データ220にアクセスする際の動作について図４を用いて説明する。図４は、ユーザ空間読み込み処理手段２３１、ユーザ空間書き込み手段232およびユーザ空間アトミック・アクセス手段233の動作例を示す流れ図である。
【００４９】
図４を参照すると、カーネル・プログラム230（ユーザ空間読み込み手段231、ユーザ空間書き込み手段232、またはユーザ空間アトミック・アクセス手段233）は、まず、アクセス対象領域がメモリ中に存在するか否かを判定する（ステップＳ１１）。
【００５０】
存在すると判定すると、カーネル・プログラム230は、指定されたアクセス処理を実行する（ステップＳ１２）。すなわち、ユーザ空間読み込み処理の場合には、カーネル・プログラム230は、ユーザ空間読み込み手段231を用いて読み込みアクセスを行う。また、ユーザ空間書き込み処理の場合には、カーネル・プログラム230は、ユーザ空間書き込み手段232を用いて書き込みアクセスを行う。ユーザ空間アトミック・アクセスの場合には、カーネル・プログラム230は、ユーザ空間アトミック・アクセス手段233を用いてアトミック・アクセスを行う。
【００５１】
その後、カーネル・プログラム230（ユーザ空間読み込み手段231、ユーザ空間書き込み手段232、またはユーザ空間アトミック・アクセス手段233）は、ユーザ空間へのアクセス処理を終了する。
【００５２】
一方、アクセス対象領域がメモリ中に存在しないと判定した場合には、カーネル・プログラム230は、ページフォルト処理を実行し、以て２次記憶装置に退避されているメモリ領域を実メモリに戻す（ステップＳ１３）。
【００５３】
次いで、カーネル・プログラム230は、ページフォルト処理が成功したか否かを判定し（ステップＳ１４）、成功したと判定した場合には、処理をステップＳ１２に移行して、指定された処理に応じたアクセスを実行し、その後、ユーザ空間のアクセス処理を終了する。また、ページフォルト処理が成功しなかったと判定した場合には、カーネル・プログラム230は、ユーザ空間のアクセス処理が失敗したものとして異常終了する。
【００５４】
次に、図５の状態遷移図と、図６および図７のフローチャートとを参照して、本実施形態における排他制御方法を適用した情報処理装置の全体の動作について説明する。
【００５５】
図５は、スレッドの状態遷移を示す遷移図である。図５を参照すると、この情報処理装置で動作しているスレッドのlockに対する状態は、lock要求なし（以下、idleと表記）状態、ロック獲得（以下、busy(locked)と表記、図において状態を示す添え字は”l”）状態、spinlockによるlock解放待ち状態、blockによるlock解放待ち状態、の４状態のいずれかである。また、複数の状態に遷移する可能性がある状態は、idle状態およびspinlock状態である。
【００５６】
Idle状態からの遷移先、すなわち、lockを獲得していないスレッドがlockの獲得要求をしたときの状態遷移先は、lock wordによって示されるlock状態に応じて、次の３種類のうちのいずれかとなる。１）lockを獲得しているスレッドが存在しない場合には、スレッドは、Idle状態からbusy（locked）状態に遷移する（遷移il）。２）別スレッドがlockを獲得しており、かつ、spinlockスレッド数が上限値未満の場合には、スレッドは、Idle状態からspinlock状態に遷移する（遷移is）。３）別スレッドがlockを獲得しており、かつ、spinlockスレッド数が上限値、または、それ以上の場合には、スレッドは、Idle状態からblock状態に遷移する（遷移ib）。
【００５７】
Spinlock状態からの遷移先は、次に示す条件に従って決まる。1）spinlock中に、lockを獲得しているスレッドがlockを解放した場合には、スレッドは、Spinlock状態からbusy(locked)状態に遷移する（遷移sl）。2）spinlockする所定期間を過ぎてもlockが解放されない場合には、スレッドは、Spinlock状態からblock状態に遷移する（遷移sb)。
【００５８】
また、スレッドは、lockを獲得しているスレッドがlockを解放したことに伴う起床処理によって、block状態から、spinlock状態に遷移する（遷移bs）。また、スレッドは、Busy(locked)状態から、獲得しているlockを解放する操作により、idle状態に遷移する（遷移li）。何れの状態遷移も、lock wordに状態を反映させる操作の終了により、遷移を完了する。
【００５９】
次に、lock獲得処理について説明する。図６は、lock獲得処理の動作例を示す流れ図である。図６を参照すると、lock獲得処理は、最初にlock獲得操作を行い（ステップＳ２１）、その結果に応じて（ステップＳ２２）、所定の動作を行い、最終的にlockを獲得して終了する。なお、lockの獲得とは、クリティカルセクションの実行権（クリティカルセクションへの侵入権）を獲得することを意味し、具体的には、スレッドがlock word221のlock bit2211をunlockedからlockedに変更することをいう。
【００６０】
すなわち、lockの獲得を要求するスレッドは、lock獲得操作（詳細については後述する）を実行すると、その結果に応じて、Idle状態から、busy（locked）状態、block状態、またはspinlock状態のいずれかの状態に遷移する。具体的には、スレッドは、図５に示す遷移図を用いて説明した上記の各条件に基づいて、状態遷移先を決定する。
【００６１】
lock獲得操作の結果、lockの獲得に成功した場合には、スレッドは、busy（locked）状態に遷移し、lock獲得処理を終了する。その後、スレッドは、クリティカルセクションを実行する。
【００６２】
また、lock獲得操作の結果、spinlock状態に遷移した場合には、スレッドは、lock獲得失敗に備えてリトライ回数（例えば、レジスタに記憶される）を0に初期化した後（ステップＳ２３）、更にlock獲得操作を行う（ステップＳ２４）。
【００６３】
この結果、lock獲得に成功した場合、またはlock獲得操作の実行結果が「blockに遷移」（詳細については後述する）の場合には、スレッドは、ステップＳ２２の判断と同様の遷移を行なう（ステップＳ２５）。
【００６４】
また、ステップＳ２４におけるlock獲得操作の結果が「spinlock状態に遷移」（詳細については後述する）の場合には、スレッドは、リトライ回数に1を加える（ステップＳ２６）。その後、スレッドは、リトライ回数がリトライ回数の限界値（例えば、後述するSPIN_LIMIT値によって予め定められる）に達したか否かを判定する（ステップＳ２７）。
【００６５】
ステップＳ２７において、限界値に達したと判定した場合には、スレッドは、spinlock状態からbusy（locked）状態に遷移する。一方、限界値に達していないと判定した場合には、スレッドは、再度spinlock状態におけるlock獲得操作（ステップＳ２４）に処理を移行し、以降の処理を繰り返すspinloop状態となる。なお、図６に示すように、本実施形態では、スレッドがspinlock状態でlock獲得操作を繰り返す状態をspinloop状態と呼ぶ。
【００６６】
ステップＳ２２又はステップＳ２５において、block状態に遷移したスレッドは、lockを獲得している他のスレッドがlockを解放する際に行なう起床操作によって起床し、block状態からspinloop状態に遷移する（ステップＳ２８）。すなわち、スレッドは、起床操作に応じて、ステップＳ２３に処理を移行する。
【００６７】
次に、lock解放処理について説明する。図７は、lock解放処理の動作例を示す流れ図である。なお、lockの解放とは、獲得中のクリティカルセクションの実行権（クリティカルセクションへの侵入権）を解放することを意味し、具体的には、スレッドがlock word221のlock bit2211をlockedからunlockedに変更することをいう。
【００６８】
図７を参照すると、busy（locked）状態にあるスレッドがlockを解放する処理では、スレッドは、まず、lock解放操作を実行する。すなわち、スレッドは、lock word内のlock bitをunlockedに変更する。その後、スレッドは、block thread数を調べ、0より大きいか否か判断する（ステップＳ３１）。
【００６９】
0より大きいと判断した場合には、スレッドは、lock word内の情報（例えば、後述するWAKEUP_LIMIT値など）からwakeup数（wakeup（起床操作）するスレッドの数）を求める（ステップＳ３２）。なお、具体的なwakeup数の求め方については後述する。
【００７０】
次いで、スレッドは、wakeup数のblock状態の他のスレッドに対して起床操作を行なった後（ステップＳ３３）、lock解放処理を終了する。なお、ステップＳ３１において、block thread数が０であると判断した場合には、スレッドは、直ちにlock解放処理を終了する。
【００７１】
本実施形態の特徴には、次の２点が挙げられる。第１の特徴は、lock獲得操作においてlock獲得できなかった場合には、lock獲得操作の結果に応じてblock状態かspinloop状態に遷移することである。そして、第２の特徴は、lock解放時にblock状態となっているスレッドが存在する場合には、lock wordの情報から起床操作の対象となるスレッドの数を決めて起床操作を行なうことである。
【００７２】
次に、具体的な例を用いて本実施形態の動作を説明する。図２に示すように、本実施形態におけるlock word221は、1bitのlock bit2211、10ビットのblock thread数2212および10ビットのspinlock thread数2213を含む。ここで、lock bit2211は、0の場合にはunlockedを、1の場合にはlockedを意味する。また、このlock word221は、CAS命令およびユーザ空間アトミック・アクセス手段によるCAS操作可能なデータ長である。
【００７３】
また、以降の説明では、変数oldおよびnewとして、lock wordと同じデータ長およびデータ構造を持つ変数を使用する。また、CAS命令およびユーザ空間アトミック・アクセス手段によるCAS操作では、eaxレジスタに変数old、レジスタ・オペランドに変数new、メモリ・オペランドにlock wordのアドレスを設定して実行する。また、本実施形態では、spinlockによりlock解放を待つスレッド数の上限値、および、lockを解放したスレッドが起床するスレッド数の上限値は予め設定されている固定値とし、夫々、SPIN_LIMIT値と、WAKEUP_LIMIT値と表記する。
【００７４】
最初に、lock獲得処理について説明する。図８は、lock獲得処理におけるlock獲得操作の動作例を示す流れ図である。図８に示すように、本実施形態におけるlock獲得操作では、以下の通りに動作する。
【００７５】
lock獲得操作では、スレッドは、oldにlock wordを代入し（ステップＳ４１）、oldのlock bitが0か否かを判定する（ステップＳ４２：lock bit検査ステップ）。
【００７６】
oldのlock bitが0であると判定した場合には、スレッドは、newにoldのlock bitを1とした値を設定し（ステップＳ４３）、CAS命令を実行する（ステップＳ４４）。
【００７７】
次いで、スレッドは、CAS命令が成功したか否かを判定する（ステップＳ４５）。CAS命令が成功したと判定した場合には、lock獲得が成功したことを意味するので、スレッドは、lock獲得操作の実行結果を「busy(locked)状態に遷移」（図６の「成功」に対応）とし、lock獲得操作を終了する。
【００７８】
また、CAS命令が失敗したと判定した場合には、CAS命令の操作としてoldにメモリから読み込んだlock word値が設定されているので、スレッドは、処理をlock bit検査ステップ（ステップＳ４２）に移行し、以降の処理を再度実行する。
【００７９】
lock bit検査ステップ（ステップＳ４２）の結果、lock bitが1である（すなわち、ロックが他のスレッドによって獲得されている）と判定した場合には、スレッドは、oldのspinlock thread数とSPIN_LIMIT値とを比較する（ステップＳ４６：spinlock thread数検査ステップ）。
【００８０】
比較の結果、spinlock thread数がSPIN_LIMIT未満の場合には、スレッドは、newにoldのspinlock thread数に1を加えた値を設定し（ステップＳ４７）、CAS命令を実行する（ステップＳ４８）。次いで、スレッドは、CAS命令が成功したか否かを判定し（ステップＳ４９）、CAS命令が成功した場合には、lock獲得操作の実行結果を「spinlock状態に遷移」とし、lock獲得操作を終了する。
【００８１】
一方、Spinlock thread数検査ステップ（ステップＳ４６）の比較の結果、spinlock thread数がSPIN_LIMIT未満ではないと判定した場合には、スレッドは、lock獲得操作の実行結果を「block状態に遷移」とし、lock獲得操作を終了する。
【００８２】
図８に示すlock獲得操作の結果が「spinlock状態に遷移」の場合には、スレッドは、idol状態からspinlock状態に遷移し、図６においてspinloop状態として示したフローに従って動作する。
【００８３】
また、lock獲得操作の結果が「block状態に遷移」の場合には、スレッドは、idol状態からblock状態に遷移し、休眠操作を実行する。
【００８４】
次に、lock獲得処理における休眠操作について説明する。なお、本実施形態における休眠操作の処理は、カーネル・プログラムとして実装され、block状態における休眠操作を実行するために用意されたシステム・コールによって起動される。また、休眠状態とは、スレッドがプロセッサ資源の利用を中断している状態をいう。
【００８５】
図９は、lock獲得処理における休眠操作の動作例を示す流れ図である。図９に示すとおり、本実施形態における休眠操作は、以下の通りに動作する。
【００８６】
まず、スレッドは、休眠操作を実行するためにシステム・コールを起動し、カーネル・モードに遷移する。次いで、スレッドは、ユーザ空間読み込み手段を用いて、ユーザ空間に配置されたlock wordを読み込み、oldに設定する（ステップＳ５１）。
【００８７】
次いで、スレッドは、oldのlock bitがunlockedであるか否かを判定し（ステップＳ５２）、unlockedであると判定した場合には休眠する必要がないので、休眠操作自体を終了する。すなわち、スレッドは、システム・コールを終了して、ユーザ・モードに復帰する。
【００８８】
ステップＳ５２において、unlockedでないと判定した場合、すなわちlock bitがlockedの場合には、スレッドは、遷移元の状態を判断し（ステップＳ５３）、遷移元の状態に応じてnewを設定する。
【００８９】
具体的には、idle状態から直接遷移した場合には、スレッドは、oldのblock thread数に1を加えた値をnewの値とする（ステップＳ５４）。また、spinloop状態から遷移した場合には、スレッドは、oldのspinloop数から1を減じ、更に、block thread数に1を加えた値をnewの値とする（ステップＳ５５）。
【００９０】
次いで、スレッドは、ユーザ空間アトミック・アクセス手段を用いてCAS操作を実行する（ステップＳ５６）。
【００９１】
次いで、スレッドは、CAS操作が成功したか否かを判定し（ステップＳ５７）、このCAS操作が失敗したと判定した場合には、処理をlock bitを調べるステップＳ５２に移行し、ステップＳ５２以降の処理を再度実行する。
【００９２】
一方、成功したと判定した場合には、スレッドは、自スレッドをblockスレッドリストに繋ぎ（ステップＳ５８）、カーネルの休眠処理を実行して（プロセッサ資源の利用を中断して）、休眠状態に移行する（ステップＳ５９）。なお、このblockスレッドリストは、一般的な技術と同様であり、wakeup操作において休眠状態のスレッドを取り出すために用いられるものである。また、この休眠状態は、lockを獲得している他のスレッドが、クリティカルセクションの実行を終了し、lock解放処理を実行した際に解除される。
【００９３】
次に、lock解放処理について説明する。図１０は、lock解放処理の動作例を示す流れ図である。図１０に示すように、本実施形態におけるlock解放処理では、スレッドは、以下の通りに動作する。
【００９４】
まず、スレッドは、oldにlock wordを代入し（ステップＳ６１）、newにoldのlock bitを0とした値を設定する（ステップＳ６２：lock bitクリア・ステップ）。
【００９５】
次いで、スレッドは、WAKEUP_LIMIT値、SPIN_LIMIT値およびoldのspinlock thread数に基づいて、wakeup数を設定する（ステップＳ６３）。具体的には、スレッドは、WAKEUP_LIMIT値と、SPIN_LIMIT+1-oldのspin thread数とを比較し、小さい方の値をwakeup数とする。
【００９６】
次いで、スレッドは、CAS命令を実行し（ステップＳ６４）、CAS命令が成功したか否かを判定する（ステップＳ６５）。
【００９７】
CAS命令が失敗したと判定した場合には、CAS命令の操作としてoldにメモリから読み込んだlock word値が設定されているので、スレッドは、処理をlock bitクリア・ステップ（ステップＳ６２）に移行し、ステップＳ６２以降の処理を再度実行する。
【００９８】
CAS命令が成功したと判定すると、スレッドは、wakeup数をチェックし（ステップＳ６６）、その値が0の場合には、そこでロック解放処理を終了する。また、wakeup数が0でない場合には、スレッドは、block状態の他のスレッドのうちの、wakeup数のスレッドに対して起床処理を実行し、lock解放処理を終了する（ステップＳ６７）。
【００９９】
次に、lock解放処理における他スレッドに対する起床処理について説明する。なお、本実施形態における起床処理は、カーネル・プログラムとして実装され、block状態のスレッドに対して起床操作を実行するために用意されたシステム・コールによって起動される。
【０１００】
図１１は、lock解放処理におけるスレッド起床処理の動作例を示す流れ図である。図１１に示すとおり、本実施形態における起床処理は、以下の通りに動作する。
【０１０１】
まず、スレッドは、起床処理を実行するためにシステム・コールを起動し、カーネル・モードに遷移する。次いで、スレッドは、blockスレッドリストに繋がれている1スレッドを取り出す。blockスレッドリストが空の場合には、スレッドは、このリストにスレッドが繋がれるまで待ってから取り出し操作を行なう（ステップＳ７１：スレッド取り出しステップ）。
【０１０２】
次いで、スレッドは、ユーザ空間読み込み手段を用いてユーザ空間に配置されたlock wordを読み込み、oldに設定する（ステップＳ７２）。
【０１０３】
その後、スレッドは、oldのblock thread数から1を減じ、更に、spinlock thread数に1を加えた値をnewの値とし（ステップＳ７３）、ユーザ空間アトミック・アクセス手段を用いてCAS操作を実行する（ステップＳ７４）。
【０１０４】
次いで、スレッドは、CAS操作が成功したか否かを判定し（ステップＳ７５）、CAS操作が失敗したと判定した場合には、old値を元にnewに値を設定するステップＳ７３に処理を移行し、以降の処理を再度実行する。
【０１０５】
成功したと判定した場合には、スレッドは、スレッド取り出しステップ（ステップＳ７１）においてblockスレッドリストから取り出したスレッドに対して、起床操作を実行する（ステップＳ７６）。その後、スレッドは、この起床操作をwakeup数で指定された回数繰り返し、起床処理を終了する。
【０１０６】
具体的には、ステップＳ７６の処理を実行すると、スレッドは、wakeup数から１を減じる（ステップＳ７７）。次いで、スレッドは、wakeup数が０であるか否かを判定し（ステップＳ７８）、０でないと判定すると、ステップＳ７３に処理を移行し、ステップＳ７３以降の処理を再度実行する。
【０１０７】
一方、０であると判定すると、スレッドは、起床処理を終了する。すなわち、スレッドは、システム・コールを終了して、ユーザ・モードに復帰する。
【０１０８】
以上のように、本実施形態では、クリティカルセクションを実行中のスレッドが存在するか否かを示すlock wordは、spinlockによりlock解放を待つスレッドの数、および、blockによりlock解放を待つスレッドの数を示す情報を含む。そして、それらの情報を、スレッドのlockに関する４つの状態、すなわち、lock要求なし、ロック獲得、spinlockによるlock解放待ち、blockによるlock解放待ち、の間の遷移を行なう際に使用すると共に、その行なった状態遷移に応じて各情報を更新する。
【０１０９】
このように、本実施形態では、アトミックなメモリアクセス機能を用いて、要求時点における競合の程度を正確にカウントし、カウントした情報に基づいて、lockの解放を待つ方式を選択する。そのため、lockの獲得を要求する時点の状況に基づいて、spinlockによりlock解放を待つスレッドの数を予め設定されている上限値以下に抑えることができる。したがって、必要数以上のスレッドがspinlockによりlock解放を待つことを回避でき、spinlock待ちによるプロセッサ資源の浪費を防止することができる。
【０１１０】
次に、本実施形態における情報処理システムの機能構成について説明する。図１２は、情報処理システムの機能構成の一例を示す機能ブロック図である。
【０１１１】
図１２に示すように、情報処理システムは、待機スレッド数情報更新手段10、lock獲得手段20、待機方式決定手段30、lock解放手段40、休眠手段50、起床手段60および排他制御用データ（lock word）221を含む。
【０１１２】
待機スレッド数情報更新手段10は、具体的には、ユーザ・プログラム210又はカーネル・プログラム230に従って動作するプロセッサ100によって実現される。待機スレッド数情報更新手段10は、所定のlockの獲得を要求しているスレッドの状態遷移に応じて、lock word221を更新する機能を備えている。また、待機スレッド数情報更新手段10は、ユーザ空間アトミック・アクセス手段を用いて、カーネル空間からユーザ空間に配置されたlock word221を更新する機能を備えている。
【０１１３】
lock獲得手段20、待機方式決定手段30およびlock解放手段40は、具体的には、ユーザ・プログラム210に従って動作するプロセッサ100によって実現される。
【０１１４】
lock獲得手段20は、所定のリソースのlockを獲得する機能を備えている。具体的には、lock獲得手段20は、lock word221のlock bit2211に基づいて、対象リソースのlockが獲得されているか否かを判定し、lock bit2211がunlockedである場合には、lockを獲得するとともに、lock bit2211をlockedに変更する。
【０１１５】
待機方式決定手段30は、lockの獲得を要求するスレッドが、他のスレッドによって獲得されているlockの解放を待つ場合の待機方式を決定する機能を備えている。具体的には、待機方式決定手段30は、lock word221のspinlock thread数2213と、予め定められたspinlock方式に則して待機するスレッド数の上限値（例えば、SPIN_LIMIT値）とに基づいて、待機方式を決定する。
【０１１６】
lock解放手段40は、獲得しているlockを解放する機能を備えている。具体的には、lock解放手段40は、lockを解放するとともに、lock word221のlock bit2211をunlockedに変更する。また、lock解放手段40は、lockを解放する際に、起床手段60に起床処理を実行させる。
【０１１７】
休眠手段50および起床手段60は、具体的には、カーネル・プログラム230に従って動作するプロセッサ100によって実現される。
【０１１８】
休眠手段50は、スレッドに対して休眠操作を実行する機能を備えている。具体的には、休眠手段50は、スレッドをblock方式に則した待機状態に移行させる。また、休眠手段50は、スレッドを休眠状態（block状態）に移行させる際に、ユーザ空間アトミック・アクセス手段233を用いて、lock word221の情報を更新する。例えば、休眠手段50は、待機スレッド数更新手段10にユーザ空間アトミック・アクセス手段233を用いてlock word221の情報を更新させる。
【０１１９】
起床手段60は、休眠状態（block状態）のスレッドに対して、起床処理を実行する機能を備えている。具体的には、起床手段60は、block方式に則した待機状態から、spinlock方式に則した待機状態にスレッドを移行させる。また、起床手段60は、起床処理を実行する際に、ユーザ空間アトミック・アクセス手段233を用いて、lock word221の情報を更新する。例えば、起床手段60は、待機スレッド数更新手段10にユーザ空間アトミック・アクセス手段233を用いてlock word221の情報を更新させる。
【０１２０】
次に、本発明による情報処理システムの最小構成について説明する。図１３は、本発明による情報処理システムの最小の構成例を示すブロック図である。図１３に示すように、情報処理システムは、最小の構成要素として、待機スレッド数情報更新手段10と、待機方式決定手段30とを含む。
【０１２１】
図１３に示す最小構成の情報処理システムでは、待機スレッド数情報更新手段10は、所定のlockの獲得を要求しているスレッドの状態遷移に応じて、lockの解放を待っているスレッド数を示す待機スレッド数情報を更新する。そして、待機方式決定手段30は、待機スレッド数情報更新手段10が更新する待機スレッド数情報に基づいて、lockの獲得を要求するスレッドの待機方式を決定する。
【０１２２】
従って、最小構成の情報処理システムによれば、lockの獲得を要求する時点の状況に応じて、効率的なlockの解放を待つ方式を選択することができ、lockの解放待ち状態におけるプロセッサ資源の浪費を防止することができる。
【０１２３】
なお、本実施形態では、以下の（１）〜（６）に示すような情報処理システムの特徴的構成が示されている。
【０１２４】
（１）情報処理システムは、所定のlockの獲得を要求しているスレッドの状態遷移に応じて、lockの解放をspinlock方式で待っているスレッド数を示す待機スレッド数情報（例えば、lock word221）を更新する待機スレッド数情報更新手段（例えば、待機スレッド数情報更新手段10によって実現される）と、待機スレッド数情報更新手段が更新する待機スレッド数情報と、予め定められたspinlock方式で待つスレッド数の上限値とに基づいて、lockの獲得を要求するスレッドの待機方式を決定する待機方式決定手段（例えば、待機方式決定手段30によって実現される）とを含むことを特徴とする。
【０１２５】
（２）情報処理システムにおいて、待機スレッド数情報更新手段は、カーネル空間からユーザ空間に配置された待機スレッド数情報にアトミックにアクセスし、待機スレッド数情報を更新する（例えば、ユーザ空間アトミック・アクセス手段233を用いて実現される）ように構成されていてもよい。
【０１２６】
（３）情報処理システムにおいて、待機方式決定手段は、待機スレッド数情報が示す所定の方式（例えば、spinlock）で待機しているスレッド数（例えば、spinlock thread数2213によって示される）と、予め定められた所定の方式で待機するスレッド数の上限値（例えば、SPIN_LIMIT値）とに基づいて、lockの獲得を要求するスレッドの待機方式を決定し、待機スレッド数情報更新手段は、待機方式決定手段の決定結果に基づいて待機スレッド数情報を更新するように構成されていてもよい。
【０１２７】
（４）情報処理システムにおいて、待機スレッド数情報更新手段は、lockの獲得を要求するスレッドが休眠状態に移行する場合（例えば、休眠手段50によって実行される）、スレッドの移行前の状態（例えば、spinlock状態又はblock状態）に基づいて待機スレッド数を更新するように構成されていてもよい。
【０１２８】
（５）情報処理システムは、lockによって保護されるクリティカルセクションに関して、クリティカルセクションを実行しているスレッドが存在するか否かを示す情報（例えば、lock bit2211）とともに、spinlock方式でlockの解放を待つスレッド数およびblock方式でlockの解放を待つスレッドの数を示す待機スレッド数情報（例えば、block thread数2212およびspinlock thread数2213）を含む排他制御用データ（例えば、lock word221によって実現される）を記憶する記憶手段（例えば、メモリ200によって実現される）と、スレッドのlockに関する状態として、lock要求なし状態（例えば、idle状態）、lock獲得状態（例えば、busy(locked)状態）、spinlock方式でのlock解放待ち状態（例えば、spinlock状態）、又はblock方式でのlock解放待ち状態（例えば、block状態）のいずれかの遷移に関して、状態遷移先を決めるアルゴリズムの入力として待機スレッド数情報を用いる制御手段（例えば、待機方式決定手段30によって実現される）と、制御手段によるスレッドの状態遷移に応じて待機スレッド数情報を更新する待機スレッド数情報更新手段（例えば、待機スレッド数情報更新手段10によって実現される）とを含み、制御手段は、待機スレッド数情報更新手段が更新する待機スレッド数情報に基づいて、spinlock方式でlockの解放を待つスレッド数を、予め定められた上限値（例えば、SPIN_LIMIT値）を超えないように制御することを特徴とする。
【０１２９】
（６）情報処理システムにおいて、カーネル・プログラム（例えば、カーネル・プログラム230）からの排他制御用データの更新操作に用いられるユーザ空間アトミック・アクセス手段（例えば、ユーザ空間アトミック・アクセス手段233によって実現される）を含むように構成されていてもよい。
【０１３０】
以上、実施形態及び実施例を参照して本願発明を説明したが、本願発明は上記実施形態および実施例に限定されるものではない。本願発明の構成や詳細には、本願発明のスコープ内で当業者が理解し得る様々な変更をすることができる。
【０１３１】
この出願は、２０１０年２月３日に出願された日本特許出願２０１０−０２１７４０を基礎とする優先権を主張し、その開示の全てをここに取り込む。
【産業上の利用可能性】
【０１３２】
本発明によれば、複数のスレッドがクリティカルセクションへの進入権を獲得する際に競合が発生することの多いユーザ・プログラムを実行する情報処理システムにおいて、プロセッサ資源の浪費を低減する用途に適用可能である。
【符号の説明】
【０１３３】
１０  待機スレッド数情報更新手段
２０  lock獲得手段
３０  待機方式決定手段
４０  lock解放手段
５０  休眠手段
６０  起床手段
１００  プロセッサ
２００  メモリ
２１０  ユーザ・プログラム
２２０  ユーザ・データ
２２１  lock word
２２１１  lock bit
２２１２  block thread数
２２１３  spinlock thread数
２３０  カーネル・プログラム
２３１  ユーザ空間読み込み手段
２３２  ユーザ空間書き込み手段
２３３  ユーザ空間アトミック・アクセス手段
２４０  カーネル・データ
【図１】
2011096163.tif 000003
【図２】
2011096163.tif 000004
【図３】
2011096163.tif 000005
【図４】
2011096163.tif 000006
【図５】
2011096163.tif 000007
【図６】
2011096163.tif 000008
【図７】
2011096163.tif 000009
【図８】
2011096163.tif 000010
【図９】
2011096163.tif 000011
【図１０】
2011096163.tif 000012
【図１１】
2011096163.tif 000013
【図１２】
2011096163.tif 000014
【図１３】
2011096163.tif 000015
【国際調査報告】
2011096163.tif 000016
2011096163.tif 000017
2011096163.tif 000018
2011096163.tif 000019