(57)【要約】【課題】情報処理システムが持つ能力や性能を、より有効に活用可能とする。【解決手段】情報処理システム１は、メモリ２をユーザ空間１０とカーネル空間２０とに分けて管理する。一のスレッドによるユーザ空間１０に配置されたユーザ・プログラム１１中のクリティカルセッションの実行が他のスレッドと競合した場合、カーネル・プログラム２１は、ユーザ空間アトミック・アクセス機能２０３を用いて、ユーザ空間１０に配置されるｌｏｃｋ ｗｏｒｄ(排他制御用データ)１００に対してアトミックにアクセスし、前記一のスレッドによる前記クリティカルセクションの実行可否を判定する。【選択図】図１
2011118756.tif 000002
【特許請求の範囲】
【請求項１】
メモリをユーザ空間とカーネル空間とに分けて管理する情報処理システムに、排他制御を行わせる排他制御プログラムであって、
前記排他制御プログラムは、前記カーネル空間で実行され、
前記排他制御は、一の実行単位による前記ユーザ空間に配置されたユーザ・プログラム中のクリティカルセッションの実行が他の実行単位と競合した場合、前記ユーザ空間に配置される前記競合を管理するためのデータに対してアトミックにアクセスし、前記一の実行単位による前記クリティカルセクションの実行可否を判定することを含む、排他制御プログラム。
【請求項２】
請求項１において、
前記排他制御は、前記一の実行単位が自身の休眠状態への移行を要求する場合に、前記競合の発生を検知することを含む、排他制御プログラム。
【請求項３】
請求項１又は２において、
前記排他制御は、前記データが前記競合の解消を示す場合、前記一の実行単位による前記クリティカルセクションの実行が可能と判定し、前記一の処理単位に、前記クリティカルセクションの実行権を与えることを含む、排他制御プログラム。
【請求項４】
メモリをユーザ空間とカーネル空間とに分けて管理する情報処理システムにおける排他制御方法であって、
一の実行単位による前記ユーザ空間に配置されたユーザ・プログラム中のクリティカルセッションの実行が他の実行単位と競合した場合、前記カーネル空間から、前記ユーザ空間に配置される前記競合を管理するためのデータに対してアトミックにアクセスし、前記一の実行単位による前記クリティカルセクションの実行可否を判定する、排他制御方法。
【請求項５】
請求項４において、
前記一の実行単位が自身の休眠状態への移行を要求する場合に、前記競合の発生を検知する、排他制御プログラム。
【請求項６】
請求項４又は５において、
前記データが前記競合の解消を示す場合、前記一の実行単位による前記クリティカルセクションの実行が可能と判定し、前記一の処理単位に、前記クリティカルセクションの実行権を与える、排他制御方法。
【請求項７】
メモリをユーザ空間とカーネル空間とに分けて管理する情報処理システムであって、
請求項１〜３のいずれか一項に記載の排他制御プログラムを前記カーネル空間で実行する、情報処理システム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、排他制御プログラム、排他制御方法、及び情報処理システムに関し、特に複数のスレッドによるクリティカルパスの実行に際しての排他制御を行う技術に関する。
【背景技術】
【０００２】
情報処理システムでは、プロセッサ等の計算機資源を効率良く利用するため、複数のプロセスやスレッドを並列に動作させることが一般的である。
【０００３】
プロセスとスレッドは、プログラムを実行する実行単位を意味するという点で同様の概念である。しかしながら、通常、プロセスは他のプロセスから独立しており、プロセス毎のメモリ空間やファイルは別個のものである。一方、スレッドは、プロセスと異なり、メモリ空間やファイルを共有する。正確には、１つのプロセスに１つ若しくは複数のスレッドが存在しているというのが正確な表現である。
【０００４】
１つのプロセスに１つのスレッドしか存在しない構成がマルチプロセス・システムであり、１つのプロセスに複数のスレッドが存在する構成がマルチスレッド・システムである。すなわち、マルチスレッド・システムにおいては、１つのプロセスに属する複数のスレッドが同一のプログラムを実行する。
【０００５】
なお、以降の説明においては、プログラムを実行する単位をスレッドと表記するが、異なるプログラムや異なるメモリ空間を意識する場合にはプロセスと表記する。
【０００６】
複数のスレッドを並列に動作させるように構成された情報処理システムでは、一のスレッドによる一の処理の実行中の任意の時点で、他のスレッドによる他の処理の実行が割り込むことがある。これらの処理同士間に関連性が無い場合は、一の処理途中に他の処理が割り込んでも得られる結果に変わりはなく、問題となることはない。
【０００７】
しかしながら、処理同士間に関連性が有る場合には、一の処理途中に他の処理が割り込むと得られる結果が異なり、問題となることがある。
【０００８】
例えば、２つのスレッドが、同一の変数に"１"を加える処理(すなわち、変数をメモリ等から読み出して"１"を加え、その結果をメモリ等に書き戻す処理)を並列に実行するとする。この例で問題となるのは、一方のスレッドが変数を読み出してから"１"を加えた結果を書き戻すまでの間に、他方のスレッドによる処理(変数に"１"を加える処理)が割り込んだ場合である。
【０００９】
割り込みが生じない場合、２つのスレッドが変数に"１"を加える操作を順に行ない、以て変数の値は"２"増加する。各スレッドが行う処理の内容を考慮すると、この処理結果は正しい。
【００１０】
一方、割り込みが生じた場合、一方のスレッドは、他方のスレッドによる変数の更新を感知すること無く、自身が読み出した値に"１"を加えた値を変数に書き戻すことになる。従って、２つのスレッドが変数に"１"を加える操作を行なったにも関わらず変数の値は"１"増加するだけであり、正しい処理結果は得られない。
【００１１】
このように処理途中で他処理に割り込まれると問題が発生する処理区間(上記の例では、変数を読み出してから加算した結果を書き戻すまでの区間)をクリティカルセクションと呼び、他処理に割り込まれないための排他制御が明示的に行われることになっている。
【００１２】
プログラム実行を担うプロセッサが１個であれば、クリティカルセクションに入る時点で他処理への切り替えを禁止し、クリティカルセクションから出る時点で他処理への切り替えを許可することで、その期間中に他処理が割り込まないことを保証できる。プロセッサが１個の場合、或るプログラムをプロセスとして実行中に他プログラムの実行(他プロセス)が割り込むのは、最初のプロセス実行中にプロセス切り替えの契機となる何らかの事象が発生し、オペレーティング・システム(ＯＳ)がプロセス切り替えを行うためである。従って、オペレーティング・システムに対して他処理(他プロセス)への切り替えを禁止するように指示しておけば、プロセス切り替え禁止状態においてプロセス切り替えの契機となる何らかの事象が発生しても、その時点ではプロセス切り替えを行わず、最初のプロセスが他プロセスへの切り替えを許可した時点でプロセス切り替えを行うように制御できる。
【００１３】
一方、マルチプロセッサ・システムでは、他プロセスへの切り替え禁止だけでは正しい処理結果を保証できない。他プロセスへの切り換え禁止は、そのプログラムを実行している(当該他プロセスを動作させている)プロセッサに対しては有効であるが、他プロセッサによるプログラム実行には影響を与えないからである。
【００１４】
他プロセッサによるプログラム実行がクリティカルセクションに入らないようにするための排他制御として一般的に行われているのは、クリティカルセクションを実行中のプロセスが存在するか否かを示すフラグ(以下、ｌｏｃｋ ｗｏｒｄ)を用いる、という対処である。なお、以降の説明おいては、クリティカルセクションの実行権(クリティカルセクションへの進入権)を、「ロック(ｌｏｃｋ)」と呼称することがある。
【００１５】
具体的には、各プロセスは、クリティカルセクションに入る時点でｌｏｃｋ ｗｏｒｄを確認し、下記(１)又は(２)に示す処理を実行する。
(１)ｌｏｃｋ ｗｏｒｄが「未使用を示す値(以下、ｕｎｌｏｃｋｅｄ)」であれば、ｌｏｃｋ ｗｏｒｄを「使用中を示す値(以下、ｌｏｃｋｅｄ)」に変更してクリティカルセクションを実行する。また、クリティカルセクションの実行を終了した時点でｌｏｃｋ ｗｏｒｄをｕｎｌｏｃｋｅｄに戻す。
(２)ｌｏｃｋ ｗｏｒｄがｌｏｃｋｅｄであれば、ｌｏｃｋ ｗｏｒｄがｕｎｌｏｃｋｅｄになるまで待機した後、上記(１)の処理を実行する。
【００１６】
以上の制御を行うことにより、他プロセッサが実行する処理と自プロセッサが実行する処理がクリティカルセクション上で競合するという問題は発生しない。
【００１７】
クリティカルセクションには、１つのスレッドのみが実行可能なものの他、実行可能なスレッド数に上限があるもの(複数のスレッドにロックを与えるもの)がある。また、クリティカルセクションには、ｗｒｉｔｅ ｌｏｃｋ(書込や更新等の処理に係るロック)とｒｅａｄ ｌｏｃｋ(読出や参照等の処理に係るロック)という２種類のロックを与えるｒｅａｄ−ｗｒｉｔｅ ｌｏｃｋが適用されることもある。ｗｒｉｔｅ ｌｏｃｋを獲得してクリティカルセクションを実行できるスレッド数は、"１"に制限されている。一方、ｒｅａｄ ｌｏｃｋを獲得可能なスレッド数には上限が無く、ｒｅａｄ ｌｏｃｋを獲得したスレッドは、ｗｒｉｔｅ ｌｏｃｋを獲得して処理を進めているスレッドが存在しない場合に限り、クリティカルセクションを実行できる。
【００１８】
次に、スレッドによるクリティカルパスの実行に際しての一般的な排他制御について詳細に説明する。
【００１９】
或るスレッドがクリティカルセクションに入る時点でｌｏｃｋ ｗｏｒｄがｌｏｃｋｅｄであり、クリティカルセクションの実行を直ちに開始することができない場合、そのスレッドはｌｏｃｋ ｗｏｒｄがｕｎｌｏｃｋｅｄになるまで待機する。
【００２０】
この方式には、下記(１)及び(２)に示す２種類の方式がある。
(１)ｌｏｃｋ ｗｏｒｄがｕｎｌｏｃｋｅｄに変更されるまで、スレッドがプロセッサ資源を利用してｌｏｃｋ ｗｏｒｄをチェックし続けるｓｐｉｎ ｌｏｏｐ方式。
(２)スレッドが、プロセッサ資源の利用を中断して休眠状態へ移行すると共に、クリティカルセクションを実行している他のスレッドに対して、クリティカルセクションの実行を完了した時点で起床処理を行うように依頼するｂｌｏｃｋ方式(例えば、特許文献１参照)。
【００２１】
また、ｓｐｉｎ ｌｏｏｐ方式とｂｌｏｃｋ方式とを組み合わせた方式(すなわち、最初はｓｐｉｎ ｌｏｏｐ方式に則して待機し、一定の時間が経過するとｂｌｏｃｋ方式に則して待機する方式)が採用されることも多い。
【００２２】
なお、ｂｌｏｃｋ方式を採用する場合には、クリティカルセクションの状態を管理する変数として、ｌｏｃｋ ｗｏｒｄに加えて、待機中のスレッドが存在するか否かを示すフラグが併用されることになる。
【００２３】
何れの方式を採用するにしても、スレッドは、ロック獲得を待機する間、本来の処理を実行できない。これは、情報処理システムが持つ能力や性能の有効活用を阻害する要因となる。特に、近年のマルチコア・プロセッサの普及に伴って一般化している多数のプロセッサを搭載した情報処理システムでは、このロック獲得待ちが性能ボトルネックとなる状況が多くなっており、ロック獲得待ちを効率的に行うための方法が求められている。
【００２４】
ところで、スレッドがクリティカルセクションに入る時点で行うｌｏｃｋ ｗｏｒｄの確認(読出)と、ｌｏｃｋ ｗｏｒｄがｕｎｌｏｃｋｅｄだった場合のｌｏｃｋｅｄへの変更(書込)の２操作には、クリティカルセクションと同様の扱いが必要となる。このため、マルチプロセッサ向けの機能を有するプロセッサには、これらの操作を行うための命令が用意されている。
【００２５】
例えば、インテルのｘ８６プロセッサには、ｃｍｐｘｃｈｇ命令が用意されている(非特許文献１参照)。
【００２６】
このｃｍｐｘｃｈｇ命令は、予約されたレジスタ(ｅａｘレジスタ)と、レジスタ・オペランドと、メモリ・オペランドの３オペランドを使用し、下記(１)、(２−１)、及び(２−２)に示す一連の操作をアトミックに行うものである。
(１)メモリからプロセッサに、メモリ・オペランドが示すアドレスに対応する値を読み出す。
(２−１)上記(１)での読出値がｅａｘレジスタの値と一致する場合、メモリにレジスタ・オペランドの値を書き込む。
(２−２)上記(１)での読出値がｅａｘレジスタの値と一致しない場合、当該読出値をｅａｘレジスタに書き込む。
【００２７】
なお、アトミックとは、上記(１)のメモリ読出操作と上記(２−１)のメモリ書込操作の間に、他のプロセッサがメモリにアクセスしないことをハードウェア動作によって保証することを意味する。また、ｃｍｐｘｃｈｇ命令のような命令は、一般にＣＡＳ(Ｃｏｍｐａｒｅ Ａｎｄ Ｓｗａｐ)命令と呼称される。本願明細書では、ＣＡＳ命令による一連の操作を「アトミック・アクセス」と表記する。
【００２８】
上記のＣＡＳ命令を用いてロック獲得を行うには、ｅａｘレジスタにｕｎｌｏｃｋｅｄ、レジスタ・オペランドにｌｏｃｋｅｄを設定すると共に、メモリ・オペランドにｌｏｃｋ ｗｏｒｄのアドレスを設定してＣＡＳ命令を実行する。ｌｏｃｋ ｗｏｒｄがｕｎｌｏｃｋｅｄである場合は、上記(２−１)が実行されるので、ｌｏｃｋ ｗｏｒｄはｌｏｃｋｅｄに書き換えられ、ｅａｘレジスタの値は変化しない。
【００２９】
一方、ｌｏｃｋ ｗｏｒｄがｌｏｃｋｅｄである場合には、上記(２−２)が実行されるので、ｌｏｃｋ ｗｏｒｄは更新されず、ｅａｘレジスタにはｌｏｃｋｅｄが設定される。ＣＡＳ命令を実行したスレッドは、ＣＡＳ命令実行後のｅａｘレジスタの値を調べることで、ロック獲得が成功したか否かを調べることができる(すなわち、クリティカルセクションを実行するか、或いは他のスレッドによりｌｏｃｋ ｗｏｒｄがｕｎｌｏｃｋｅｄに変更されるのを待機するかを判断できる)。
【００３０】
また、他の関連技術としては、メモリをユーザ空間とカーネル空間とに分けて管理するメモリ管理技術がある(例えば、非特許文献２参照)。
【００３１】
この内、ユーザ空間は、アプリケーション等のユーザ・プログラムが動作するために必要な情報(命令、データ等)を配置するメモリ領域であり、各プロセスに対して独立した領域が用意されている。このユーザ空間は、通常、ページングの対象となっており、メモリ容量が逼迫してくると二時記憶装置に退避されることがある。このため、ユーザ空間に配置された情報は、実メモリ上に存在していない場合がある。
【００３２】
一方、カーネル空間は、物理デバイスへのアクセスやシステム管理を行うカーネル(ＯＳ)が動作するために必要な情報を配置するメモリ領域であり、全プロセスに共通した空間となっている。
【００３３】
ユーザ・プログラムを実行するユーザモードでは、プロセスは、ユーザ空間に配置されるデータ(以下、ユーザ・データ)にアクセスできるが、カーネル空間に配置されるデータ(以下、カーネル・データ)へはアクセスできない。一方、カーネル空間に配置されるプログラム(以下、カーネル・プログラム)を実行するカーネルモードでは、プロセスは、カーネル空間に配置されたカーネル・データ、及び当該プロセスに属するユーザ空間に配置されたユーザ・データの両者にアクセスできる。
【００３４】
また、カーネル空間からユーザ・データにアクセスする際は、アクセス対象の情報が実メモリ上に存在しないケースが有り得るので、その状況でもシステムを正しく動作させる必要がある。このため、カーネル機能として用意されるユーザ空間読出機能及びユーザ空間書込機能を用いて、ユーザ空間とカーネル空間の間で情報のコピーを行うようになっている。カーネルは、ユーザ・データを加工する場合、ユーザ・データをユーザ空間読出機能によりカーネル空間にコピーしてから加工し、その結果をユーザ空間書込機能によりユーザ空間へ書き戻す。
【００３５】
また、上記のｌｏｃｋ ｗｏｒｄは一般にユーザ空間に配置され、ロック獲得操作はユーザ・プログラムにおいて実施される。
【先行技術文献】
【特許文献】
【００３６】
【特許文献１】特開平１０−１６１８９２号公報
【非特許文献】
【００３７】
【非特許文献１】Ｉｎｔｅｌ ６４ ａｎｄ ＩＡ-３２ Ａｒｃｈｉｔｅｃｔｕｒｅｓ Ｓｏｆｔｗａｒｅ Ｄｅｖｅｌｏｐｅｒ'ｓ Ｍａｎｕａｌ Ｖｏｌｕｍｅ ２Ａ： Ｉｎｓｔｒｕｃｔｉｏｎ Ｓｅｔ Ｒｅｆｅｒｅｎｃｅ, Ａ-Ｍ, ｈｔｔｐ：／／ｗｗｗ.ｉｎｔｅｌ.ｃｏｍ/Ａｓｓｅｔｓ/ＰＤＦ/ｍａｎｕａｌ/２５３６６６.ｐｄｆ
【非特許文献２】Ｍａｕｒｉｃｅ Ｊ. Ｂａｃｈ, ＴＨＥ ＤＥＳＩＧＮ ＯＦ ＴＨＥ ＵＮＩＸ ＯＰＥＲＡＴＩＮＧ ＳＹＳＴＥＭ, ＰＲＥＮＴＩＣＥ−ＨＡＬＬ, ＩＮＣ．, Ｅｎｇｌｅｗｏｏｄ Ｃｌｉｆｆｓ, Ｎｅｗ Ｊｅｒｓｅｙ ０７６３２, １９８６
【発明の概要】
【発明が解決しようとする課題】
【００３８】
しかしながら、上述した従来の排他制御には、情報処理システムが持つ能力や性能を十分に活用できないという課題があった。これは、スレッドがロック競合に起因して休眠処理を依頼するためにカーネル・プログラムを呼び出してから、カーネル・プログラムが休眠処理を行ってスレッドを休眠状態へ移行するまでの間にロックが解放された場合であっても、スレッドが直ちにはロックを獲得できない(休眠状態からの復帰後でなければロック獲得操作を実行できない)ためである。
【００３９】
従って、本発明の目的は、情報処理システムが持つ能力や性能をより有効に活用可能とすることにある。
【課題を解決するための手段】
【００４０】
上記の目的を達成するため、本発明の一態様に係る排他制御プログラムは、メモリをユーザ空間とカーネル空間とに分けて管理する情報処理システムに、排他制御を行わせる。この排他制御プログラムは、前記カーネル空間で実行され、前記排他制御は、一の実行単位による前記ユーザ空間に配置されたユーザ・プログラム中のクリティカルセッションの実行が他の実行単位と競合した場合、前記ユーザ空間に配置される前記競合を管理するためのデータに対してアトミックにアクセスし、前記一の実行単位による前記クリティカルセクションの実行可否を判定することを含む。
【００４１】
また、本発明の一態様に係る排他制御方法は、メモリをユーザ空間とカーネル空間とに分けて管理する情報処理システムにおける排他制御方法を提供する。この排他制御方法は、一の実行単位による前記ユーザ空間に配置されたユーザ・プログラム中のクリティカルセッションの実行が他の実行単位と競合した場合、前記カーネル空間から、前記ユーザ空間に配置される前記競合を管理するためのデータに対してアトミックにアクセスし、前記一の実行単位による前記クリティカルセクションの実行可否を判定する。
【００４２】
さらに、本発明の一態様に係る情報処理システムは、メモリをユーザ空間とカーネル空間とに分けて管理すると共に、上記の排他制御プログラムを前記カーネル空間で実行する。
【発明の効果】
【００４３】
本発明では、カーネル空間からロック獲得操作を実施する。このため、スレッドがロック競合に起因して休眠処理を要求してから休眠状態へ移行するまでの間にロックが解放された場合、スレッドは、休眠すること無く即座にロックを獲得することが可能となる。従って、スレッドは本来の処理を継続して実行でき、以て情報処理システムが持つ能力や性能をより有効に活用することが可能である。
【図面の簡単な説明】
【００４４】
【図１】本発明の実施の形態に係る情報処理システムの構成例を示したブロック図である。
【図２】本発明の実施の形態に係る排他制御プログラムの概略的な動作例を示した図である。
【図３】本発明の実施の形態に係る排他制御プログラムが有する、ユーザ空間読出機能、ユーザ空間書込機能、及びユーザ空間アトミック・アクセス機能の動作例を示したフローチャート図である。
【図４】本発明の実施の形態に係る情報処理システムの全体動作例を示したフローチャート図である。
【図５】本発明の実施の形態に係る情報処理システムに用いるｌｏｃｋ ｗｏｒｄの構成例を示した図である。
【図６】本発明の実施の形態に係る情報処理システムにおける通常ロック獲得操作の一例を示したフローチャート図である。
【図７】本発明の実施の形態に係る情報処理システムにおけるシステム・コール前処理の一例を示したフローチャート図である。
【図８】本発明の実施の形態に係る情報処理システムにおける、ユーザ空間アトミック・アクセス機能を用いたロック獲得操作の一例を示したフローチャート図である。
【図９】本発明の実施の形態に係る情報処理システムにおけるロック解放処理の一例を示したフローチャート図である。
【図１０】本発明の実施の形態に係る情報処理システムにおける休眠後処理の一例を示したフローチャート図である。
【発明を実施するための形態】
【００４５】
以下、本発明に係る排他制御プログラム及びこれを実行する情報処理システムの実施の形態を、図１〜図１０を参照して説明する。なお、各図面において、同一要素には同一の符号が付されており、説明の明確化のため、必要に応じて重複説明は省略される。
【００４６】
図１に示す本実施の形態に係る情報処理システム１は、メモリ２と、複数のプロセッサ(中央処理装置)３＿１〜３＿ｎとで構成されている。メモリ２内には、ユーザ空間１０とカーネル空間２０とが形成される。
【００４７】
ユーザ空間１０には、ユーザ・プログラム１１と、ユーザ・データ１２とが配置される。また、ユーザ・データ１２は、排他制御用のデータであるｌｏｃｋ ｗｏｒｄ １００を含む。
【００４８】
一方、カーネル空間２０には、カーネル・プログラム２１と、カーネル・データ２２とが配置される。また、カーネル・プログラム２１は、上述したユーザ空間読出機能２０１及びユーザ空間書込機能２０２に加えて、ユーザ空間アトミック・アクセス機能２０３を含む。ここで、ユーザ空間アトミック・アクセス機能２０３は、後述する如く、ｌｏｃｋ ｗｏｒｄ１００に対してアトミックにアクセスする。また、カーネル・プログラム２１は、ユーザ空間アトミック・アクセス機能２０３を用いて、カーネル空間２０からロック獲得操作を実行する。
【００４９】
また、各プロセッサ３＿１〜３＿ｎは、１つ以上のスレッド(図示せず)を生成する。各スレッドは、ユーザ・プログラム１１又はカーネル・プログラム２１から実行すべき機械語命令を読み出し、その機械語命令で規定される処理を実行する。この際、各スレッドは、必要に応じてユーザ・データ１２又はカーネル・データ２２を使用する。
【００５０】
なお、ユーザ・プログラム１１からユーザ・データ１２に対するアクセス、及びカーネル・プログラム２１からカーネル・データ２２に対するアクセスには、一般的な情報処理システムと同様に制限は無い。すなわち、各プロセッサ３＿１〜３＿ｎは、特別な機能を使用すること無く、機械語命令の実行により読出、書込、アトミック・アクセスを行うことができる。
【００５１】
ユーザ・プログラム１１及びカーネル・プログラム２１は、概略、図２に示す如く動作する。
【００５２】
図２に示すように、ユーザ・プログラム１１は、カーネル・プログラム２１の機能を使用する場合、システム・コールを行ってカーネルモードに遷移し、以てカーネル・プログラム２１による処理を実行させる。カーネル・プログラム２１による処理が完了した場合、カーネル・プログラム２１は、ユーザ・プログラム１１にリターンしてユーザモードに復帰し、以てユーザ・プログラム１１による処理を続行させる。カーネル・プログラム２１は、ユーザ・データ１２を使用する場合、アクセスの種類に応じて、ユーザ空間読出機能２０１、ユーザ空間書込機能２０２、又はユーザ空間アトミック・アクセス機能２０３を用いる。
【００５３】
これらの機能２０１〜２０３は、概略、図３に示す如く動作する。
【００５４】
図３に示すように、各機能２０１〜２０３は、まず、アクセス対象領域がメモリ２中に存在するかどうかを調べる(ステップＳ１)。この結果、アクセス対象領域がメモリ２中に存在すると判定した場合、各機能２０１〜２０３は、自機能に予め定められたアクセス処理を実行する(ステップＳ２)。すなわち、ユーザ空間読出機能２０１は、ユーザ・データ１２に対する読出アクセスを行い、ユーザ空間書込機能２０２は、ユーザ・データ１２に対する書込アクセスを行い、ユーザ空間アトミック・アクセス機能２０３は、ｌｏｃｋ ｗｏｒｄ１００に対するアトミック・アクセスを行う。
【００５５】
一方、上記のステップＳ１でアクセス対象領域がメモリ２中に存在しないと判定した場合、各機能２０１〜２０３は、ページフォルト処理を実行し、以て２次記憶装置(図示せず)に退避されているメモリ領域を実メモリに戻す(ステップＳ３)。ページフォルト処理が成功した場合(ステップＳ４)、各機能２０１〜２０３は、上記のステップＳ２に進み、所定のアクセス処理を実行する。なお、ページフォルト処理が成功しなかった場合には、各機能２０１〜２０３は、ユーザ空間へのアクセス処理に失敗したものとして異常終了する。
【００５６】
次に、本実施の形態の具体的な動作例を、図４〜図１０を参照して詳細に説明する。
【００５７】
情報処理システム１で動作するスレッドは、ユーザ・プログラム１１中のクリティカルセクションの実行に先立って、図４に示すロック獲得処理を実行する。具体的には、スレッドは、まず、ロック獲得失敗に備えて、リトライ回数３００を"０"に初期化する(ステップＳ１１)。
【００５８】
そして、スレッドは、ユーザモードでの通常のロック獲得操作を実行する(ステップＳ１２)。具体的には、スレッドは、例えば図５に示す如く構成されたｌｏｃｋ ｗｏｒｄ１００に対して、図６に示す処理を実行する。ここで、ｌｏｃｋ ｗｏｒｄ１００は、１ビットのｌｏｃｋ ｂｉｔ１０１と、１０ビットのｂｌｏｃｋｅｄ ｔｈｒｅａｄ数１０２とを含む。このｌｏｃｋ ｗｏｒｄ１００は、ＣＡＳ命令で扱うことが可能なデータ長を有する。また、ｌｏｃｋ ｂｉｔ１０１＝"０"は、ｕｎｌｏｃｋｅｄを意味し、ｌｏｃｋ ｂｉｔ１０１＝"１"は、ｌｏｃｋｅｄを意味する。さらに、ｂｌｏｃｋｅｄ ｔｈｒｅａｄ数１０２には、ロック競合により休眠状態へ移行するスレッドの数が計数される。
【００５９】
図６に示すように、スレッドは、まず、ｌｏｃｋ ｗｏｒｄ１００と同一のデータ長及びデータ構造を持つ作業用変数ｏｌｄに、ｌｏｃｋ ｗｏｒｄ１００を代入する(ステップＳ３１)。そして、スレッドは、変数ｏｌｄのｌｏｃｋ ｂｉｔが"０"であるか否かを判定する(ステップＳ３２)。
【００６０】
この結果、ｌｏｃｋ ｂｉｔ＝"０"が成立する場合、スレッドは、ｌｏｃｋ ｗｏｒｄ１００と同一のデータ長及びデータ構造を持つ作業用変数ｎｅｗに変数ｏｌｄをコピーした後(ステップＳ３３)、変数ｎｅｗのｌｏｃｋ ｂｉｔを"１"に設定する(ステップＳ３４)。
【００６１】
そして、スレッドは、ｅａｘレジスタに変数ｏｌｄ、レジスタ・オペランドに変数ｎｅｗ、メモリ・オペランドにｌｏｃｋ ｗｏｒｄ１００のアドレスを設定して、ＣＡＳ命令を実行する(ステップＳ３５)。ＣＡＳ命令が成功した場合(ステップＳ３６)、ｌｏｃｋ ｗｏｒｄ１００のｌｏｃｋ ｂｉｔ１０１に"１(ｌｏｃｋｅｄ)"が設定されるため、スレッドは、ロック獲得に成功したとして処理を終了する。ＣＡＳ命令が失敗した場合(すなわち、上記のステップＳ３２〜３４を実行する間に他のスレッドによりｌｏｃｋ ｗｏｒｄ１００が変更されていた場合)には、スレッドは、上記のステップＳ３２に戻って、ロック獲得操作を再び実行する。なお、この時、変数ｏｌｄには、最新のｌｏｃｋ ｗｏｒｄ１００が代入されることろなる。
【００６２】
一方、上記のステップＳ３２でｌｏｃｋ ｂｉｔ＝"１"が成立した場合、スレッドは、ロック獲得に失敗したとして処理を終了する。
【００６３】
図４に戻って、上記の通常ロック獲得操作に成功した場合(ステップＳ１３)、スレッドは、ロック獲得処理を終了し、クリティカルセクションを実行する。
【００６４】
一方、上記の通常ロック獲得操作に失敗した場合には、スレッドは、予め定められた閾値に達するまでリトライ回数３００をインクリメントしながら(ステップＳ１４及びＳ１５)、上記の通常ロック獲得操作を繰り返し実行する。リトライ回数３００が閾値に達した場合、スレッドは、休眠状態へ移行するためのシステム・コール(以下、休眠用システム・コールと呼称する)の起動が必要であると判断する。
【００６５】
そして、スレッドは、休眠用システム・コールの起動に先立って、図７に示す前処理を実行し(ステップＳ１６)、以てｌｏｃｋ ｗｏｒｄ１００のｂｌｏｃｋｅｄ ｔｈｒｅａｄ数１０２をインクリメントする。具体的には、スレッドは、まず、変数ｏｌｄにｌｏｃｋ ｗｏｒｄ１００を代入する(ステップＳ４１)。そして、スレッドは、変数ｎｅｗに変数ｏｌｄをコピーした後(ステップＳ４２)、変数ｎｅｗのｂｌｏｃｋｅｄ ｔｈｒｅａｄ数を"１"だけインクリメントする(ステップＳ４３)。そして、スレッドは、上記のステップＳ３５と同様にして、ＣＡＳ命令を実行する(ステップＳ４４)。ＣＡＳ命令が成功した場合(ステップＳ４５)、ｌｏｃｋ ｗｏｒｄ１００のｂｌｏｃｋｅｄ ｔｈｒｅａｄ数１０２が"１"だけインクリメントされるため、スレッドは、休眠用システム・コールを起動する(図４のステップＳ１７)。一方、ＣＡＳ命令が失敗した場合には、スレッドは、上記のステップＳ４２に戻って、ｂｌｏｃｋｅｄ ｔｈｒｅａｄ数１０２のインクリメントを再試行する。
【００６６】
図４に戻って、休眠用システム・コールを起動すると、スレッドは、カーネルモードに遷移し、ユーザ空間アトミック・アクセス機能２０３を用いたロック獲得操作を実行する(ステップＳ１８)。
【００６７】
具体的には、図８に示すように、スレッドは、まず、変数ｏｌｄにｌｏｃｋ ｗｏｒｄ１００を代入する(ステップＳ５１)。そして、スレッドは、変数ｏｌｄのｌｏｃｋ ｂｉｔが"０"であるか否かを判定する(ステップＳ５２)。
【００６８】
この結果、ｌｏｃｋ ｂｉｔ＝"０"が成立する場合、スレッドは、変数ｎｅｗに変数ｏｌｄをコピーした後(ステップＳ５３)、変数ｎｅｗのｌｏｃｋ ｂｉｔを"１"に設定し(ステップＳ５４)、変数ｎｅｗのｂｌｏｃｋｅｄ ｔｈｒｅａｄ数を"１"だけデクリメントする(ステップＳ５５)。そして、スレッドは、上記のステップＳ３５と同様にして、ＣＡＳ命令を実行する(ステップＳ５６)。ＣＡＳ命令が成功した場合(ステップＳ５７)、スレッドは、ロック獲得に成功したとして処理を終了する。ＣＡＳ命令が失敗した場合には、スレッドは、上記のステップＳ５２に戻って、ロック獲得操作を再び実行する。
【００６９】
一方、上記のステップＳ５２でｌｏｃｋ ｂｉｔ＝"１"が成立した場合、スレッドは、ロック獲得に失敗したとして処理を終了する。
【００７０】
図４に戻って、上記のユーザ空間アトミック・アクセス機能２０３を用いたロック獲得操作に成功した場合(ステップＳ１９)、スレッドは、直ちにシステム・コールを終了してユーザモードに復帰し(ステップＳ２０)、ロック獲得処理を終了する。
【００７１】
これにより、スレッドは、休眠すること無く即座にロックを獲得し、クリティカルセクションを実行することができる。このため、情報処理システム１が持つ能力や性能を有効に活用できる。
【００７２】
一方、ユーザ空間アトミック・アクセス機能２０３を用いたロック獲得操作に失敗した場合、スレッドは、休眠処理を実行して(プロセッサ資源の利用を中断して)、休眠状態に移行する(ステップＳ２１)。
【００７３】
この休眠状態は、ロックを獲得している他のスレッドが、クリティカルセクションの実行を終了し、ロックを解放する処理(以下、ロック解放処理と呼称する)を実行した際に解除される。
【００７４】
具体的には、図９に示すように、他のスレッドは、まず、変数ｏｌｄにｌｏｃｋ ｗｏｒｄ１００を代入する(ステップＳ６１)。そして、他のスレッドは、変数ｎｅｗに変数ｏｌｄをコピーした後(ステップＳ６２)、変数ｎｅｗのｌｏｃｋ ｂｉｔを"０"に設定する(ステップＳ６３)。そして、他のスレッドは、上記のステップＳ３５と同様にして、ＣＡＳ命令を実行する(ステップＳ６４)。
【００７５】
ＣＡＳ命令が成功した場合(ステップＳ６５)、他のスレッドは、変数ｏｌｄのｂｌｏｃｋｅｄ ｔｈｒｅａｄ数が"０"であるか否かを判定する。ｂｌｏｃｋｅｄ ｔｈｒｅａｄ数＝"０"が成立する場合(ステップＳ６６)、他のスレッドは、ロック解放処理を終了する。一方、ｂｌｏｃｋｅｄ ｔｈｒｅａｄ数＝"０"が成立しない場合、他のスレッドは、休眠状態に在るスレッドに対する起床処理を実行した後、ロック解放処理を終了する(ステップＳ６７)。
【００７６】
一方、ＣＡＳ命令が失敗した場合には、他のスレッドは、上記のステップＳ６２に戻って、ロック解放処理を再び実行する。
【００７７】
図４に戻って、上記のロック解放処理により休眠状態が解除されると、スレッドは、図１０に示す後処理を実行し(ステップＳ２２)、以てｌｏｃｋ ｗｏｒｄ１００のｂｌｏｃｋｅｄ ｔｈｒｅａｄ数１０２をデクリメントする。具体的には、スレッドは、まず、変数ｏｌｄにｌｏｃｋ ｗｏｒｄ１００を代入する(ステップＳ７１)。そして、スレッドは、変数ｎｅｗに変数ｏｌｄをコピーした後(ステップＳ７２)、変数ｎｅｗのｂｌｏｃｋｅｄ ｔｈｒｅａｄ数を"１"だけデクリメントする(ステップＳ７３)。そして、スレッドは、上記のステップＳ３５と同様にして、ＣＡＳ命令を実行する(ステップＳ４４)。ＣＡＳ命令が成功した場合(ステップＳ７５)、ｌｏｃｋ ｗｏｒｄ１００のｂｌｏｃｋｅｄ ｔｈｒｅａｄ数１０２が"１"だけデクリメントされるため、スレッドは、後処理を終了する。一方、ＣＡＳ命令が失敗した場合には、スレッドは、上記のステップＳ７２に戻って、ｂｌｏｃｋｅｄ ｔｈｒｅａｄ数１０２のデクリメントを再試行する。
【００７８】
この後、スレッドは、休眠用システム・コールを終了し、ユーザモードに復帰する(図４のステップＳ２３)。この時、スレッドは、上記のステップＳ２０とは異なり、上記のステップＳ１１に戻ってロック獲得処理を再び実行する。なお、スレッドは、休眠状態が解除された後、ユーザモードに復帰せずに上記のステップＳ１８に戻り、以てユーザ空間アトミック・アクセス機能２０３を用いたロック獲得操作を再び実行しても良い。
【００７９】
なお、上記の実施の形態によって本発明は限定されるものではなく、特許請求の範囲の記載に基づき、当業者によって種々の変更が可能なことは明らかである。
【産業上の利用可能性】
【００８０】
本発明は、排他制御プログラム、排他制御方法、及び情報処理システムに適用され、特に複数のスレッドによるクリティカルパスの実行に際しての排他制御を行う用途に適用される。
【符号の説明】
【００８１】
１  情報処理システム
２  メモリ
３＿１〜３＿ｎ  プロセッサ
１０  ユーザ空間
１１  ユーザ・プログラム
１２  ユーザ・データ
２０  カーネル空間
２１  カーネル・プログラム
２２  カーネル・データ
１００  ｌｏｃｋ ｗｏｒｄ(排他制御用データ)
１０１  ｌｏｃｋ ｂｉｔ
１０２  ｂｌｏｃｋｅｄ ｔｈｒｅａｄ数
２０１  ユーザ空間読出機能
２０２  ユーザ空間書込機能
２０３  ユーザ空間アトミック・アクセス機能
３００  リトライ回数
【図１】
2011118756.tif 000003
【図２】
2011118756.tif 000004
【図３】
2011118756.tif 000005
【図４】
2011118756.tif 000006
【図５】
2011118756.tif 000007
【図６】
2011118756.tif 000008
【図７】
2011118756.tif 000009
【図８】
2011118756.tif 000010
【図９】
2011118756.tif 000011
【図１０】
2011118756.tif 000012