(57)【要約】【課題】不可分操作命令やメモリバリア命令を用いずに効率的な排他制御を実現する。【解決手段】本発明に係るシステムは、第１のタスクによる排他権の獲得又は試行を示す第１情報を記憶するための第１記憶領域と、第２のタスクによる排他権の獲得又は試行を示す第２情報を記憶するための第２記憶領域とを有する記憶装置と、第１のタスクの要求に応じ、第１情報を第１記憶領域に書き込む命令を発行した後に第２記憶領域を読み出して、第２情報が読み出されなければ排他権の獲得成功を返答する第１獲得部と、第２のタスクの要求に応じ、第２情報を第２記憶領域に書き込み第１のタスクから参照可能とした後に、第１タスクにより第１記憶領域へ書き込まれた内容を第２タスクから参照可能とする書込反映処理を行い、書込反映処理の完了後に第１記憶領域を読み出し、第１記憶領域から第１情報が読み出されなければ排他権の獲得成功を返答する第２獲得部とを備える。【選択図】図５
2008112400.tif 000002
【特許請求の範囲】
【請求項１】
複数のタスクの間の排他制御を行うシステムであって、
第１のタスクによる排他権の獲得又は獲得の試行を示す第１情報を記憶するための第１記憶領域と、第２のタスクによる前記排他権の獲得又は獲得の試行を示す第２情報を記憶するための第２記憶領域とを有し、第１のタスクにより書き込み命令が発行されてから第２のタスクにより当該書き込みの内容が参照可能となるまで時間差が生じ得る記憶装置と、
第１のタスクによる排他権の獲得の要求に応じ、前記第１情報を前記第１記憶領域に書き込む命令を発行した後に前記第２記憶領域を読み出して、前記第２情報が読み出されなかったことを条件に前記排他権の獲得が成功したことを返答し、前記第２情報が読み出されたことを条件に、前記第１記憶領域から前記第１情報を消去して前記排他権の獲得が失敗したことを返答する第１獲得部と、
第１のタスクによる排他権の解放の要求に応じ、前記第１情報を前記第１記憶領域から消去する第１解放部と、
第２のタスクによる排他権の獲得の要求に応じ、前記第２情報を前記第２記憶領域に書き込んで前記第１のタスクから参照可能とした後に、第１タスクにより前記第１記憶領域へ書き込まれた内容を第２タスクから参照可能とする書込反映処理を行い、当該書込反映処理の完了後に前記第１記憶領域を読み出し、前記第１記憶領域から前記第１情報が読み出されなかったことを条件に前記排他権の獲得が成功したことを返答し、前記第１情報が読み出されたことを条件に、前記第２記憶領域から前記第２情報を消去して前記排他権の獲得が失敗したことを返答する第２獲得部と、
第２のタスクによる排他権の解放の要求に応じ、前記第２情報を前記第２記憶領域から消去する第２解放部と
を備えるシステム。
【請求項２】
第１のタスクが第２のタスクからシグナルを受信したことに応じ、第１記憶領域へ書き込まれた内容を第２のタスクから参照可能とするバリア命令を第１のタスクによる処理として実行させるシグナルハンドラ部をさらに備え、
前記第２獲得部は、前記書込反映処理として、前記シグナルを前記第２のタスクから前記第１のタスクに送信させる
請求項１に記載のシステム。
【請求項３】
前記第２獲得部は、前記書込反映処理として、前記第１のタスクの動作を一時停止して前記第１のタスクを動作させていたＣＰＵを他のタスクのために解放し、一時停止した当該第１のタスクの動作を再開させて前記第１のタスクをＣＰＵによって動作させる
請求項１に記載のシステム。
【請求項４】
前記第２獲得部は、前記書込反映処理として、前記第１獲得部により前記第１情報を書き込む命令が発行された後に前記第１情報が第２のタスクにより参照可能となるまでに要する時間を待機する処理を行う
請求項１に記載のシステム。
【請求項５】
複数の第２のタスクを動作させており、
前記第２記憶領域は、前記第２情報として、前記排他権の獲得又は獲得の試行が何れの第２のタスクによって行われたかを示す情報を記憶し、
前記第２獲得部は、ある第２のタスクによる排他権の獲得の要求に応じ、
前記第２記憶領域に前記第２情報が記憶されていなければ当該第２のタスクを識別する第２情報を前記第２記憶領域に書き込む不可分操作命令を実行し、
前記不可分操作命令による第２情報の書込みが成功したことを条件に、前記書込反映処理を行い、当該書込反映処理の完了後に前記第１記憶領域を読み出し、
前記第１記憶領域から前記第１情報が読み出されなかったことを条件に前記排他権の獲得が成功したことを返答し、前記第１情報が読み出されたことを条件に、前記第２記憶領域から前記第２情報を消去して前記排他権の獲得が失敗したことを返答し、
前記不可分操作命令による第２情報の書込みが失敗したことを条件に、前記排他権の獲得が失敗したことを返答する
請求項１に記載のシステム。
【請求項６】
複数の第１のタスクを動作させており、
前記記憶装置は、複数の第１のタスクのそれぞれに対応する複数の第１記憶領域のそれぞれと、前記複数の第１記憶領域のそれぞれに対応する複数の第２記憶領域のそれぞれとを有し、
前記書込反映処理は、書き込みを反映させる第１のタスクを指定して、書き込みを反映させる要求を送信してから、書き込みの反映まで待機する処理であり、
前記第２獲得部は、第２のタスクによる排他権の獲得の要求に応じ、
第２情報を前記複数の第２記憶領域のそれぞれに書き込んでそれぞれの第１のタスクから参照可能とした後に、前記複数の第１のタスクのそれぞれを指定した複数の前記書込反映処理の要求を順次送信してから、何れの第１のタスクにおいても書き込みが反映されるまで待機し、
全ての前記書込反映処理の完了後にそれぞれの前記第１記憶領域を読み出し、何れの前記第１記憶領域からも前記第１情報が読み出されなかったことを条件に、全ての前記排他権の獲得が成功したことを返答し、
何れかの前記第１記憶領域から前記第１情報が読み出されたことを条件に、当該第１記憶領域に対応する前記第２記憶領域から前記第２情報を消去して前記排他権の獲得が失敗したことを返答する
請求項１に記載のシステム。
【請求項７】
第２のタスクは、第１のタスクにより既に参照されなくなったメモリ上の記憶領域を検出して、以降の処理において利用可能とするために解放するガーベージコレクション（ＧＣ）を行い、
第１のタスクは、処理中に第２のタスクによるガーベージコレクションを行わせることができない予め定められた処理の実行に先立って、前記排他権の獲得を前記第１獲得部に要求し、前記排他権の獲得を条件に前記予め定められた処理を行い、前記予め定められた処理の実行後に前記排他権の解放を前記第１解放部に要求し、
第２のタスクは、ガーベージコレクションを行う前に前記排他権の獲得を前記第２獲得部に要求し、前記排他権の獲得を条件に前記ガーベージコレクションを行い、ガーベージコレクションを行った後に前記排他権の解放を前記第２獲得部に要求する
請求項１に記載のシステム。
【請求項８】
複数のタスクの間の排他制御を行うシステムとして、情報処理装置を機能させるプログラムであって、
前記情報処理装置を、
第１のタスクによる排他権の獲得又は獲得の試行を示す第１情報を記憶するための第１記憶領域と、第２のタスクによる前記排他権の獲得又は獲得の試行を示す第２情報を記憶するための第２記憶領域とを有し、第１のタスクにより書き込み命令が発行されてから第２のタスクにより当該書き込みの内容が参照可能となるまで時間差が生じ得る記憶装置と、
第１のタスクによる排他権の獲得の要求に応じ、前記第１情報を前記第１記憶領域に書き込む命令を発行した後に前記第２記憶領域を読み出して、前記第２情報が読み出されなかったことを条件に前記排他権の獲得が成功したことを返答し、前記第２情報が読み出されたことを条件に、前記第１記憶領域から前記第１情報を消去して前記排他権の獲得が失敗したことを返答する第１獲得部と、
第１のタスクによる排他権の解放の要求に応じ、前記第１情報を前記第１記憶領域から消去する第１解放部と、
第２のタスクによる排他権の獲得の要求に応じ、前記第２情報を前記第２記憶領域に書き込んで前記第１のタスクから参照可能とした後に、第１タスクにより前記第１記憶領域へ書き込まれた内容を第２タスクから参照可能とする書込反映処理を行い、当該書込反映処理の完了後に前記第１記憶領域を読み出し、前記第１記憶領域から前記第１情報が読み出されなかったことを条件に前記排他権の獲得が成功したことを返答し、前記第１情報が読み出されたことを条件に、前記第２記憶領域から前記第２情報を消去して前記排他権の獲得が失敗したことを返答する第２獲得部と、
第２のタスクによる排他権の解放の要求に応じ、前記第２情報を前記第２記憶領域から消去する第２解放部と
して機能させるプログラム。
【請求項９】
複数のタスクの間の排他制御を情報処理装置によって行う方法であって、
前記情報処理装置は、第１のタスクによる排他権の獲得又は獲得の試行を示す第１情報を記憶するための第１記憶領域と、第２のタスクによる前記排他権の獲得又は獲得の試行を示す第２情報を記憶するための第２記憶領域とを有し、第１のタスクにより書き込み命令が発行されてから第２のタスクにより当該書き込みの内容が参照可能となるまで時間差が生じ得る記憶装置を有し、
第１のタスクによる排他権の獲得の要求に応じ、前記第１情報を前記第１記憶領域に書き込む命令を発行した後に前記第２記憶領域を読み出して、前記第２情報が読み出されなかったことを条件に前記排他権の獲得が成功したことを返答し、前記第２情報が読み出されたことを条件に、前記第１記憶領域から前記第１情報を消去して前記排他権の獲得が失敗したことを返答し、
第１のタスクによる排他権の解放の要求に応じ、前記第１情報を前記第１記憶領域から消去し、
第２のタスクによる排他権の獲得の要求に応じ、前記第２情報を前記第２記憶領域に書き込んで前記第１のタスクから参照可能とした後に、第１タスクにより前記第１記憶領域へ書き込まれた内容を第２タスクから参照可能とする書込反映処理を行い、当該書込反映処理の完了後に前記第１記憶領域を読み出し、前記第１記憶領域から前記第１情報が読み出されなかったことを条件に前記排他権の獲得が成功したことを返答し、前記第１情報が読み出されたことを条件に、前記第２記憶領域から前記第２情報を消去して前記排他権の獲得が失敗したことを返答し、
第２のタスクによる排他権の解放の要求に応じ、前記第２情報を前記第２記憶領域から消去する、方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、排他制御を効率化する技術に関する。特に、本発明は、複数のタスクによる競合する動作を調停するための排他制御を効率化する技術に関する。
【背景技術】
【０００２】
近年のオペレーティングシステム（以下、ＯＳと略す）またはミドルウェアは、複数のスレッドを非同期かつ並列に動作させることができる。複数のスレッドは、コンピュータ内の共有リソース、例えば、メモリ上の所定の領域や入出力デバイスに対しアクセスする場合がある。また、プログラムによっては、複数のスレッドにより同時に実行してはならない命令列（クリティカルセクション）を有する場合がある。これらの場合には、競合するスレッドの動作を調停するために排他制御が必要となる。
【０００３】
排他制御に関する技術として以下の非特許文献１および２を挙げる。
【非特許文献１】E. W. Dijkstra. Solution of a Problem in Concurrent Programming and Control. CACM, 8(9), p.569, 1965.
【非特許文献２】T. Onodera, K. Kawachiya, and A. Koseki. Lock Reservation for Java Reconsidered. Proc. ECOOP '04, pp.560-584, 2004.
【発明の開示】
【発明が解決しようとする課題】
【０００４】
従来、効率的な排他制御を実現するために、ｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐなどの不可分操作命令が用いられている。不可分操作命令はユーザーモードで実行でき、排他制御のためにＯＳに処理を戻す必要が無く効率的である。しかしながら、不可分操作命令は他の命令（例えば演算命令、メモリからの読出命令など）よりも実行に時間がかかるため、不可分操作命令を用いた場合であっても排他制御の所要時間が問題となる場合がある。
【０００５】
これに対し、１つの排他権についてその排他権の獲得状態を示す記憶領域をスレッド毎に設けることで、不可分操作命令を不要とし、排他制御の所要時間を短縮した技術が提案されている（非特許文献１および２を参照。）。これらの技術をＷｅａｋｌｙ−ｏｒｄｅｒｅｄメモリモデルを採用したコンピュータに適用する場合には、不可分操作命令に代えてメモリバリア命令が必要となる。メモリバリア命令とは、プロセッサによるメモリへの書込みを、他のプロセッサから参照可能とする命令をいう。メモリバリア命令によれば、書込み時点からその内容を参照可能となるまでに時間差が生じ得る場合であっても、プロセッサによる書込みの内容を強制的に他のプロセッサにより参照可能とさせることができる。
しかしながら、メモリバリア命令もまた、他の命令よりは実行に時間がかかる。このため、これらの技術を採用した場合であってもなお、排他制御の所要時間が問題となる場合がある。
【０００６】
そこで本発明は、上記の課題を解決することのできるシステム、プログラムおよび方法を提供することを目的とする。この目的は特許請求の範囲における独立項に記載の特徴の組み合わせにより達成される。また従属項は本発明の更なる有利な具体例を規定する。
【課題を解決するための手段】
【０００７】
上記課題を解決するために、本発明の一側面においては、複数のタスクの間の排他制御を行うシステムであって、第１のタスクによる排他権の獲得又は獲得の試行を示す第１情報を記憶するための第１記憶領域と、第２のタスクによる排他権の獲得又は獲得の試行を示す第２情報を記憶するための第２記憶領域とを有し、第１のタスクにより書き込み命令が発行されてから第２のタスクにより当該書き込みの内容が参照可能となるまで時間差が生じ得る記憶装置と、第１のタスクによる排他権の獲得の要求に応じ、第１情報を第１記憶領域に書き込む命令を発行した後に第２記憶領域を読み出して、第２情報が読み出されなかったことを条件に排他権の獲得が成功したことを返答し、第２情報が読み出されたことを条件に、第１記憶領域から第１情報を消去して排他権の獲得が失敗したことを返答する第１獲得部と、第１のタスクによる排他権の解放の要求に応じ、第１情報を第１記憶領域から消去する第１解放部と、第２のタスクによる排他権の獲得の要求に応じ、第２情報を第２記憶領域に書き込んで第１のタスクから参照可能とした後に、第１タスクにより第１記憶領域へ書き込まれた内容を第２タスクから参照可能とする書込反映処理を行い、当該書込反映処理の完了後に第１記憶領域を読み出し、第１記憶領域から第１情報が読み出されなかったことを条件に排他権の獲得が成功したことを返答し、第１情報が読み出されたことを条件に、第２記憶領域から第２情報を消去して排他権の獲得が失敗したことを返答する第２獲得部と、第２のタスクによる排他権の解放の要求に応じ、第２情報を第２記憶領域から消去する第２解放部とを備えるシステム。
なお、上記の発明の概要は、本発明の必要な特徴の全てを列挙したものではなく、これらの特徴群のサブコンビネーションもまた、発明となりうる。
【発明を実施するための最良の形態】
【０００８】
以下、発明を実施するための最良の形態（以下、実施形態と称す）を通じて本発明を説明するが、以下の実施形態は特許請求の範囲にかかる発明を限定するものではなく、また実施形態の中で説明されている特徴の組み合わせの全てが発明の解決手段に必須であるとは限らない。
【０００９】
図１は、排他制御の第１実装例を示す。この第１実装例では、不可分操作命令としてｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐ命令を用いている。図１の１行目に、排他権の獲得状態を示す変数ｆｌａｇの定義を示す。変数ｆｌａｇの値が０の場合は排他権が獲得されておらず、変数ｆｌａｇの値が０以外の場合は排他権が獲得されていることを示す。なお、この変数の記憶領域は、複数のスレッドから参照可能な共有メモリ上に設けられる。以降の説明においても、排他権の獲得またはその試行を示す情報を格納するための変数を例示するが、これらの変数の記憶領域は、複数のスレッドから参照可能な共有メモリ上に設けられるものとする。
【００１０】
３行目から６行目に、排他権の獲得を試行するための関数を示し、８行目に、排他権を解放するための関数を示す。４行目に示すｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐが不可分操作命令である。この命令は、変数ｆｌａｇの値を読み出して定数値０と比較して、一致する場合には、スレッドの識別番号を変数ｆｌａｇに代入する。この不可分操作命令は読み出し、比較および書込みという３つの処理を不可分に行う。即ち、あるプロセッサがこれら３つの処理を行っている間は、他のプロセッサがこの変数に関し書込み処理を行うことができない。このため、読み出しから書込みまでの間に、他のプロセッサによりメモリの内容が書き換えられることは無い。したがって、読み出した値が定数値０であれば排他権の獲得成功として関数をリターンし（４行目の末尾）、定数値０でなければ排他権の獲得失敗として関数をリターンする（５行目）。
なお、ｃｏｍｐａｒｅ＿ａｎｄ＿ｓｗａｐという関数は、第１引数として与えられた変数につき、その読み出し結果が第２引数として与えられた定数０と等しければ、第３引数の値をその変数に代入したうえで、排他権獲得の成功を示す定数値ＳＵＣＣＥＳＳを返り値として返す関数である。
【００１１】
しかしながら、不可分操作命令は、ＣＰＵで実行される他の命令（例えば単なる読出命令または書込命令）よりも実行に時間がかかるため、不可分操作命令を用いた場合であっても排他制御の所要時間が問題となる場合がある。これに対し、不可分操作命令に代えてメモリバリア命令を用いることで、排他制御の所要時間をさらに短縮することもできる。
【００１２】
図２は、排他制御の第２実装例を示す。この第２実装例では、不可分操作命令に代えてメモリバリア命令を用いている。図２の１行目に、排他権の獲得状態を示す変数ｆｌａｇｓの定義を示す。配列変数ｆｌａｇｓは第１要素および第２要素を有する。第１要素が０の場合はスレッドＡにより排他権が獲得されていないことを示し、１の場合はスレッドＡにより排他権の獲得またはその試行が行われていることを示す。第２要素が０の場合はスレッドＢにより排他権が獲得されていないことを示し、１の場合はスレッドＢにより排他権の獲得またはその試行が行われていることを示す。
【００１３】
３行目から９行目に、スレッドＡのために排他権の獲得を試行する関数を示す。この関数はスレッドＡから呼び出されて処理を開始し、４行目においてまず第１要素に１を代入する。この代入処理は、ＣＰＵに対しメモリに対する書込命令を発行する処理に相当する。Ｗｅａｋｌｙ−ｏｒｄｅｒｅｄメモリモデルを採用したコンピュータにおいては、書込命令が発行されても直ちにその内容がスレッドＢから参照可能となるとは限らない。次に、５行目においてメモリバリア命令が実行される。このメモリバリア命令は、４行目における書込みの内容をスレッドＢから参照可能とする役割を果たす。さらに、このメモリバリア命令の実行以降に発行されるメモリからの読出命令が、このメモリバリア命令による処理完了前に実行されないことを保証する役割も果たす。
【００１４】
６行目の命令は、第２要素を読み出して定数値０と比較し、一致した場合にはスレッドＡに獲得成功を示す定数値「ＳＵＣＣＥＳＳ」をリターンする命令である。７行目および８行目の命令は、獲得失敗の場合に実行され、第１要素に定数値０を代入して、獲得失敗を示す定数値「ＦＡＩＬＥＤ」をリターンする命令である。
また、１１行目に、スレッドＡのために排他権を解放する関数を示す。この関数は、スレッドＡから呼び出されて処理を開始し、第１要素に０を代入して処理を終了する関数である。
【００１５】
１３行目から１９行目に、スレッドＢのために排他権の獲得を試行する関数を示し、２１行目に、スレッドＢのために排他権を解放する関数を示す。スレッドＢについての処理は、スレッドＡについての処理と同様である。即ち、配列変数の第１要素を第２要素と、配列変数の第２要素を第１要素と、スレッドＡをスレッドＢと、スレッドＢをスレッドＡとそれぞれ読み替えることによって説明される。
【００１６】
このように、この第２実装例においては、スレッドＡは配列変数の第１要素に対応付けられ、スレッドＢは配列変数の第２要素に対応付けられ、それぞれのスレッドが対応する要素にのみ書込みを行う。このため、配列変数の要素（即ちメモリ上の記憶領域）に対するアクセス競合が発生しないので、不可分操作命令を不要とすることができる。
【００１７】
図３は、排他制御の第３実装例を示す。この実装例では、記憶領域としては第２実装例と同じ２要素の配列変数のみを用いて、３以上のスレッドによるアクセス競合を調停することができる。但し、不可分操作命令が不要であるのは、１つのスレッド（ここではスレッドＡ）についての排他権の獲得処理のみであり、他のそれぞれのスレッドについての排他権の獲得処理には不可分操作命令が必要となる。即ち、この実装例は、スレッドＡにより高頻度で排他権の獲得が試行される場合に有効である。
【００１８】
具体的には、図３の１行目に、排他権の獲得状態を示す変数ｆｌａｇｓの定義を示す。配列変数ｆｌａｇｓは第１要素および第２要素を有する。第１要素が０の場合はスレッドＡにより排他権が獲得されていないことを示し、１の場合はスレッドＡにより排他権の獲得またはその試行が行われていることを示す。第２要素が０の場合はスレッドＡ以外の何れのスレッドによっても排他権が獲得されていないことを示し、０以外の値の場合にはその値により識別されるスレッドにより排他権の獲得またはその試行が行われていることを示す。
【００１９】
３行目から９行目に、スレッドＡのために排他権の獲得を試行する関数を示し、１１行目に、スレッドＡのために排他権を解放する関数を示す。これらの関数は、図２を参照して説明したスレッドＡのための処理と同一であるから説明を省略する。また、１３行目から１９行目に、スレッドＡを除くその他のスレッドのために排他権の獲得を試行する関数を示す。この関数は、当該その他のスレッドから呼び出されて処理を開始し、１４行目に示すように不可分操作命令を実行する。この不可分操作命令は、配列変数の第２要素をメモリから読み出して定数値０と比較し、一致すれば当該他のスレッドの識別情報を第２要素に代入したうえで、代入に成功した旨を示す定数値「ＳＵＣＣＥＳＳ」を返り値として出力する。スレッドの識別情報は、例えば、ＯＳに対しシステムコールを発行することで取得できるので、プログラムコードはこの図３に示すものを各スレッドで共有できる。
なお、この関数でバリア命令が明示的に用いられていないのは、不可分操作命令が同等の機能を含んでいるからである。
【００２０】
第２要素への代入が成功した時点では、スレッドＡを除く他の複数のスレッドの間でアクセス競合が調停された状態にあるが、スレッドＡとはアクセスが競合している可能性がある。したがって、１５行目に示すように、配列変数の第１要素をメモリから読み出して、定数値０と比較する。一致した場合には、排他権の獲得成功を示す定数値「ＳＵＣＣＥＳＳ」をリターンする。一致しない場合には１６行目が実行され、配列変数の第２要素に０が代入される。この場合を含め、排他権の獲得に失敗した場合には、１８行目に示すように、その旨を示す定数値「ＦＡＩＬＥＤ」がリターンされる。
２１行目に、スレッドＡを除く他のスレッドのために排他権を解放する関数を示す。この関数は、配列変数の第２要素に単に０を代入する。
【００２１】
以上、図１、図２および図３を参照して説明したように、排他制御は不可分操作命令により実現することもできるが、不可分操作命令は他の命令よりも実行に時間がかかるため、メモリバリア命令を用いるか、不可分操作命令およびメモリバリア命令を併用することが望ましい。しかしながら、メモリバリア命令もまた、他の通常の命令（メモリからの読出、メモリへの書込みなど）よりは実行に時間がかかる。このため、頻繁に排他制御を行う場合には実行の所要時間が問題となる場合がある。
【００２２】
メモリバリア命令の実行時間が問題になるのであれば、排他権獲得を頻繁に試行する一方のスレッド（ここではスレッドＡとする）においては、メモリバリア命令を実行させなければよいとも考えられる。しかしながら、これをＷｅａｋｌｙ−ｏｒｄｅｒｅｄメモリモデルを採用したコンピュータにおいて実現しようとすると問題の生じる場合がある。図４にその例を示す。
図４は、第２実装例においてメモリバリア命令を実行しないと問題の生じる例を示す。図４の例は、第２実装例の処理過程を示している。時間１から時間５までの期間に、スレッドＡにより排他権が獲得される。即ち、スレッドＡの要求に応じ、配列変数の第１要素に１が代入され、配列変数の第２要素は定数値０と比較され、一致しているので獲得の成功が返答されている。但し、メモリバリア命令は実行されない。この時点で、スレッドＡから参照可能な配列変数の要素は｛１，０｝である。一方、スレッドＢから参照可能な配列変数の要素は｛０，０｝のままである。
【００２３】
次に、時間６から時間１０までの期間に、スレッドＢは排他権の獲得を試みる。即ち、スレッドＢの要求に応じ、配列変数の第２要素に１が代入され、メモリバリア命令が実行される。これにより、配列変数の第２要素に代入された定数値１は、スレッドＡから参照可能となる。次に、時間９において、配列変数の第１要素は定数値０と比較される。この第１要素はスレッドＡにより１とされたはずであるが、書込内容の反映が遅延されているのでスレッドＢからは読み出せない。このため、配列変数の第１要素は定数値０と一致して、スレッドＢによる排他権の獲得は成功してしまう。この結果、スレッドＡおよびＢの双方が同一の排他権を獲得した状態となり、動作の調停は失敗している。
【００２４】
これに対し、本実施形態に係る情報システム１０は、スレッドＢが排他権の獲得を試行する場合に、スレッドＡによるメモリに対する書込みの内容を、その内容が参照可能となるタイミングが遅延している場合であっても、強制的にスレッドＢにより参照可能とする。これにより、動作の調停を失敗させないようにしつつも、スレッドＡのためにはメモリバリア命令の実行を不要とすることができる。以下、この形態について具体的に説明する。
【００２５】
図５は、本実施形態に係る情報システム１０の全体構成を示す。情報システム１０は、第１獲得部１００と、第１解放部１１０と、第２獲得部１２０と、第２解放部１３０と、記憶装置１６０と、シグナルハンドラ部１７０とを備える。また、情報システム１０は、第１のタスク１４０および第２のタスク１５０を動作させている。まず、ハードウェア資源との関連を説明する。後述のＲＡＭ１０２０に記憶されたプログラムは、後述のＣＰＵ１０００−１〜２を、第１獲得部１００、第１解放部１１０、第２獲得部１２０、第２解放部１３０およびシグナルハンドラ部１７０として動作させる。このプログラムはライブラリプログラムであり、ユーザプログラムと結合され、ユーザプログラム内の関数呼出やメソッド呼び出しに応じて動作するものであってよい。
【００２６】
また、第１のタスク１４０および第２のタスク１５０のそれぞれは、たとえば、オペレーティングシステムやミドルウェア（例えばＪａｖａ仮想機械）により管理されたスレッドである。即ちその実体は、プログラムの実行位置、レジスタの内容およびスタックの内容などの実行コンテキストであり、ＣＰＵ１０００−１〜２がその実行コンテキストを参照してプログラムを実行することにより、第１のタスク１４０および第２のタスク１５０として動作する。これに代えて、第１のタスク１４０および第２のタスク１５０のそれぞれはプロセスであり、互いに独立したアドレス空間を有する実行コンテキストにより実現されてもよい。記憶装置１６０は、後述のＲＡＭ１０２０またはハードディスクドライブ１０４０などにより実現される。
【００２７】
記憶装置１６０は、メモリコントローラなどの制御によって、Ｗｅａｋｌｙ−ｏｒｄｅｒｅｄメモリモデルに従った動作をする。たとえば、記憶装置１６０は、ＣＰＵ１０００−１が実行する第１のタスク１４０により書込み命令が発行されてからＣＰＵ１０００−２が実行する第２のタスク１５０により当該書き込みの内容が参照可能となるまで時間差が生じ得る。また、記憶装置１６０は、第１記憶領域１６２および第２記憶領域１６５を有する。第１記憶領域１６２は、第１のタスク１４０による排他権の獲得又は獲得の試行を示す第１情報を記憶するための領域である。この領域に記憶する定数値１は第１情報であり、定数値０は第１情報が記憶されていない状態を示している。第２記憶領域１６５は、第２のタスク１５０によるその排他権の獲得又は獲得の試行を示す第２情報を記憶するための領域である。この領域に記憶する定数値１は第２情報であり、定数値０は第２情報が記憶されていない状態を示している。
【００２８】
第１獲得部１００は、第１のタスク１４０による排他権の獲得の要求に応じ、第１記憶領域１６２および第２記憶領域１６５にアクセスして排他権の獲得を試みる。このとき、第１獲得部１００は、メモリバリア命令を発行しないので、処理は極めて短時間で終了する。第１獲得部１００は、排他権の獲得に成功した場合には獲得に成功したことを第１のタスク１４０に対し返答し、排他権の獲得に失敗した場合には獲得に失敗したことを第１のタスク１４０に対し返答する。第１解放部１１０は、第１のタスク１４０による排他権の解放の要求に応じ、第１記憶領域１６２から第１情報を消去して排他権を解放する。
【００２９】
第２獲得部１２０は、第２のタスク１５０による排他権の獲得の要求に応じ、第１記憶領域１６２および第２記憶領域１６５にアクセスして排他権の獲得を試みる。このとき、第２獲得部１２０は、第１のタスク１４０により第１記憶領域１６２へ書き込まれた内容を第２のタスク１５０から参照可能とする書込反映処理を行う。書込反映処理は、第２獲得部１２０の働きかけにより第２のタスク１５０から第１のタスク１４０に対しシグナルを送信させることにより実現されてもよい。具体的な実現方法については図１３から図１５を参照して後に説明する。シグナルを受けると、シグナルハンドラ部１７０は、第１のタスク１４０による処理の一部として、第１のタスク１４０による書込みの内容を第２のタスク１５０から参照可能とする処理を実行する。第２獲得部１２０は、排他権の獲得に成功した場合には獲得に成功したことを第２のタスク１５０に対し返答し、排他権の獲得に失敗した場合には獲得に失敗したことを第２のタスク１５０に対し返答する。第２解放部１３０は、第２のタスク１５０による排他権の解放の要求に応じ、第２記憶領域１６５から第１情報を消去して排他権を解放する。
【００３０】
図６は、第１獲得部１００が排他権の獲得を試行する処理のフローチャートである。第１獲得部１００は、第１のタスク１４０による排他権の獲得の要求に応じて動作を開始する。この要求とは、例えば、第１のタスク１４０を実現するプログラムからの関数呼び出しまたはメソッド呼び出しである。そして、まず、第１獲得部１００は、第１情報を第１記憶領域１６２に書き込む命令である書込命令を発行する（Ｓ６００）。書込命令を発行した後に、第１獲得部１００は、メモリバリア命令を実行することなく第２記憶領域１６５を読み出す（Ｓ６１０）。第２情報が読み出されなかったことを条件に（Ｓ６２０：ＮＯ）、第１獲得部１００は、排他権の獲得が成功したことを返答する（Ｓ６３０）。返答とは、例えば、関数呼び出し又はメソッド呼び出しからの戻り値に、排他権の獲得が成功したことを示す数値情報を含める処理である。第２情報が読み出されたことを条件に（Ｓ６２０：ＹＥＳ）、第１獲得部１００は、第１記憶領域１６２から第１情報を消去して（Ｓ６４０）、排他権の獲得が失敗したことを返答する（Ｓ６５０）。消去とは、例えば、第１記憶領域１６２に定数値０を書き込むことである。
【００３１】
図７は、第２獲得部１２０が排他権の獲得を試行する処理のフローチャートである。第２獲得部１２０は、第２のタスク１５０による排他権の獲得の要求に応じて動作を開始する。そして、まず、第２獲得部１２０は、第２情報を第２記憶領域１６５に書き込む書込命令を発行する（Ｓ７００）。そして、第２獲得部１２０は、その書き込んだ内容を第１のタスク１４０から参照可能とする処理であるストアフラッシュ処理を行う（Ｓ７１０）。その後に、第２獲得部１２０は、第１のタスク１４０により第１記憶領域１６２へ書き込まれた内容を第２のタスク１５０から参照可能とする書込反映処理を行う（Ｓ７２０）。次に、第２獲得部１２０は、当該書込反映処理の実行よりも後に発行される命令が、当該書込反映処理よりも先行して投機的に実行されないようにするロードバリア処理を行う（Ｓ７３０）。
【００３２】
ロードバリア処理の後に、即ち、書込反映処理の完了後であることが保証された状態において、第２獲得部１２０は、第１記憶領域１６２を読み出す（Ｓ７４０）。第２獲得部１２０は、第１記憶領域１６２から第１情報が読み出されなかったことを条件に（Ｓ７５０：ＮＯ）、排他権の獲得が成功したことを第２のタスク１５０に返答する（Ｓ７６０）。一方、第１記憶領域１６２から第１情報が読み出されたことを条件に（Ｓ７５０：ＹＥＳ）、第２獲得部１２０は、第２記憶領域１６５から第２情報を消去して（Ｓ７７０）、排他権の獲得が失敗したことを返答する（Ｓ７８０）。消去とは、例えば、第２記憶領域１６５に定数値０を書き込むことである。
【００３３】
図８は、本実施形態に係る排他制御の実装例を示す。図８に示すプログラムの行番号左側には、図２に示すプログラムと比較して相違する行に傍線を付して示す。１行目に示す配列変数ｆｌａｇｓは、記憶装置１６０内の第１記憶領域１６２および第２記憶領域１６５を示す。この配列変数の第１要素は第１記憶領域１６２に記憶され、第２要素は第２記憶領域１６５に記憶される。３行目から９行目に、第１のタスク１４０の一例であるスレッドＡのために排他権の獲得を試行する関数を示す。この関数はＣＰＵ１０００−１を第１獲得部１００として機能させる。ただし、この関数は、図２に示す関数と比較して、５行目にメモリバリア命令を有していない点で異なっている。また、この関数の動作は、メモリバリア命令を実行しない点を除き、図２に示す関数と同一であるから説明を省略する。
【００３４】
１３行目から２１行目に、第２のタスク１５０の一例であるスレッドＢのために排他権の獲得を試行する関数を示す。この関数は１５行目から１７行目において、ストアフラッシュ処理、書込反映処理およびロードバリア処理を行う点で、図２に示す関数とは異なる。即ち、ストアフラッシュ処理によって、配列変数ｆｌａｇｓの第２要素に対する代入結果がスレッドＡから参照可能となる。また、書込反映処理によって、スレッドＡが配列変数ｆｌａｇｓの第１要素に代入した結果がスレッドＢから参照可能となる。また、ロードバリア処理によって、書込反映処理の完了後にその後の処理（たとえば配列変数ｆｌａｇｓの第１要素からデータを読み出す処理）が行われることが保証される。
【００３５】
ここで、このプログラムを実行するコンピュータの種類によっては、ストアフラッシュ処理またはロードバリア処理をそれぞれ独立した命令として実行できず、ストアフラッシュ処理およびロードバリア処理の双方をまとめて処理するメモリバリア命令のみを実行することができる場合がある。このような場合には、第２獲得部１２０は、ストアフラッシュ処理に代えて、メモリバリア命令を実行し、ロードバリア処理に代えて、再度メモリバリア命令を実行すればよい。
なお、１１行目および２３行目に示す、排他権を解放するための関数は、図２に示した関数と同一であるから説明を省略する。
【００３６】
図９は、本実施形態に係る排他制御をＷｅａｋｌｙ−ｏｒｄｅｒｅｄメモリモデルに適用した例を示す。時間１から時間５までの期間の処理は図４に示した処理と同一である。時間５の経過時点において、スレッドＡから参照可能な配列変数の要素は｛１，０｝である。一方、スレッドＢから参照可能な配列変数の要素は｛０，０｝のままである。時間６から時間１０までの期間に、スレッドＢは排他権の獲得を試みる。即ち、スレッドＢの要求に応じ、第２獲得部１２０は、第２記憶領域１６５に第２情報を書込む。次の時間８において、第２獲得部１２０はストアフラッシュ処理を行う。これにより、第１記憶領域１６２に書き込んだ第２情報は第１のタスク１４０から参照可能となる。
【００３７】
次の時間９において、第２獲得部１２０は書込反映処理を行う。これにより、第１のタスク１４０によって記憶装置１６０に書き込まれた第１情報は第２のタスク１５０から参照可能となる。次の時間１０において、第２獲得部１２０はロードバリア処理を行う。これにより、次の読出処理が書込反映処理よりも先行して投機的に実行されることを防ぐことができる。次の時間１１において、第２獲得部１２０は、記憶装置１６０を読み出して定数０と比較する。第１情報が読み出されて定数０とは一致しないから、スレッドＢによる排他権の獲得は失敗する。この結果、スレッドＡにより排他権が獲得されている間はスレッドＢによって排他権を獲得することはできず。競合する２つのスレッド間で適切な調停が行えていることとなる。
【００３８】
以上、図５から図９を参照して説明したように、本実施形態に係る情報システム１０によれば、２つのスレッド間で競合する動作を調停する場合に、一方のスレッドに関しては不可分操作命令もメモリバリア命令も一切不要とすることができる。これにより、一方のスレッドによってのみ高頻度で排他権が獲得される場合など、スレッド間で処理の内容に偏りがある場合には、排他制御に要する時間を全体として削減して、処理を効率化できる。
【００３９】
次に、上記実施形態に示した排他制御を、３以上のスレッド間で実現する構成例を第１変形例として示す。
図１０は、本実施形態の第１変形例に係る情報システム１０の全体構成を示す。情報システム１０は、１つの第１のタスク１４０と、複数の第２のタスク１５０（第２のタスク１５０−１〜Ｎ）とを動作させる。その他の構成については、図５に示す情報システム１０と略同一であるから説明を省略する。但し、第２記憶領域１６５については、第２情報として１を記憶するのではなく、排他権の獲得又は獲得の試行が何れの第２のタスク１５０によって行われたかを示す情報を記憶する。獲得又は試行が行われていない場合には０が記憶される。
【００４０】
図１１は、本実施形態の第１変形例に係る第２獲得部１２０が排他権の獲得を試行する処理のフローチャートである。なお、第１変形例において第１獲得部１００が排他権の獲得を試行する処理については、図６を参照して説明した処理と同一であるから説明を省略する。まず、第２獲得部１２０は、第２のタスク１５０−１〜Ｎのうちのある第２のタスク（単に第２のタスク１５０と表記する）による排他権の獲得の要求に応じ、第２記憶領域１６５に第２情報が記憶されていなければその第２のタスク１５０を識別する第２情報を第２記憶領域１６５に書き込む不可分操作命令を実行する（Ｓ１１００）。
【００４１】
不可分操作命令による第２情報の書込みが成功したことを条件に（Ｓ１１１０：ＹＥＳ）、第２獲得部１２０は書込反映処理を行う（Ｓ１１２０）。そして、第２獲得部１２０は、書込反映処理以降に発行される読出命令が、書込反映処理の完了に先行して投機的に実行されないようにするための命令である、ロードバリア命令を実行する（Ｓ１１３０）。そして、第２獲得部１２０は、当該書込反映処理の完了したことが保証された状態で、第１記憶領域１６２を読み出す（Ｓ１１４０）。
なお、書込みが他のタスクに参照可能となることを保証するストアフラッシュ処理は、不可分操作命令の中で暗黙に行われるため、図１１には明示的に現れない。
【００４２】
第２獲得部１２０は、第１記憶領域１６２から第１情報が読み出されなかったことを条件に（Ｓ１１６０：ＮＯ）、排他権の獲得が成功したことを第２のタスク１５０に対し返答する（Ｓ１１６０）。第２獲得部１２０は、第１情報が読み出されたことを条件に（Ｓ１１６０：ＹＥＳ）、第２記憶領域１６５から第２情報を消去して（Ｓ１１７０）、排他権の獲得が失敗したことを返答する（Ｓ１１８０）。不可分操作命令の実行が失敗した場合にも（Ｓ１１１０：ＮＯ）、排他権の獲得が失敗したことが返答される（Ｓ１１７０）。
【００４３】
図１２は、本実施形態の第１変形例に係る排他制御の実装例を示す。１行目に、２要素からなる配列変数ｆｌａｇｓを示す。第１要素の記憶領域は第１記憶領域１６２であり、第２要素の記憶領域は第２記憶領域１６５である。３行目から１１行目に、スレッドＡのために排他権の獲得および解放を行う関数を示す。この関数は図８に示すスレッドＡのための関数と同一であるから説明を省略する。
【００４４】
１３行目から２１行目に、スレッドＡを除く他のスレッドのために排他権の獲得を試行する関数を示す。１４行目の不可分操作命令は、第２記憶領域１６５に第２情報が記憶されていなければその第２のタスク１５０を識別する第２情報を第２記憶領域１６５に書き込む処理を行う。そして、１５行目のロードバリア命令は、書込反映処理以降に発行される読出命令が、書込反映処理の完了に先行して投機的に実行されないようにするための処理を行う。これらの処理の存在により、スレッドＡにおいてメモリバリア命令が実行されなくても書込みの結果が他のスレッドから参照可能となる。
【００４５】
以上、第１変形例によれば、３以上のスレッドの動作を調停する場合であっても、最も頻繁に排他権を獲得するスレッドＡに関してはメモリバリア命令を不要とすることで、全体として処理を効率化することができる。
【００４６】
次に、図１３から図１５を参照して、書込反映処理の実現方法について述べる。既に述べてきたように、書込反映処理は、その処理を実行するスレッドとは異なる他のスレッドに働きかけて、当該他のスレッドにより記憶領域に書き込まれた内容をその他のスレッドから参照可能とする処理をいう。書込反映処理は、比較的低い頻度で実行されることが予想されるため、実行にある程度の時間を要しても構わない。もちろん、実行に要する時間は短い方が好ましいが、アーキティクチャの特性やアプリケーションプログラムの特性によって、以下に説明する何れの方法を採用しても構わない。
【００４７】
図１３は、書込反映処理の第１例を示す。第１例は、第２のタスク１５０から第１のタスク１４０に対しシグナルを送信して、シグナルを受けた第１のタスク１４０においてメモリバリア命令を実行させることを内容とする。具体的には、１行目から５行目に、第２獲得部１２０が書込反映処理としてシグナルを第２のタスク１５０から第１のタスク１４０に送信させる関数の実装例を示す。２行目において、シグナルを受けた第１のタスク１４０による処理完了を示すフラグをリセットする。３行目において、シグナルの宛先となるスレッドの番号ｔｈｒｅａｄ＿ｉｄを指定して、シグナルＳＩＧｘｘｘが送信される。そして、４行目において、シグナルを受けた第１のタスク１４０においてメモリバリア命令の実行が完了するまで待機する。待機している間に他の処理を行っても構わない。メモリバリア命令の実行完了は、完了フラグを定期的に読み出すことによって行われてよい。
【００４８】
７行目から１０行目に、シグナルハンドラ部１７０を実現するシグナルハンドラ関数を示す。シグナルハンドラ部１７０は、第１のタスク１４０が第２のタスク１５０からシグナルを受信したことに応じ、記憶装置１６０へ書き込まれた内容を第２のタスク１５０から参照可能とするバリア命令を、第１のタスク１４０による処理として実行させる。この処理は８行目の命令により実現される。そして、シグナルハンドラ部１７０は、処理完了を示すフラグをセットして処理を完了し、第１のタスク１４０に処理を戻して、第１のタスク１４０においてシグナル受信前に実行されていた処理を再開する。
以上、第１例によれば、タスク間のシグナル送受信の機能を利用して、他のタスクから書き込みの反映を働きかけることができる。
【００４９】
図１４は、書込反映処理の第２例を示す。第２例は、タスクを一時停止（サスペンド）させて直ぐに復帰（レジューム）させることにより、そのタスクにおける書込みの内容を反映させることを内容とする。具体的には、第２獲得部１２０は、書込みを反映させたいタスクのＩＤを指定した関数呼出を受けると（１行目）、そのＩＤのタスクを一時停止してそのタスクを動作させていたＣＰＵを他のタスクのために解放するシステムコールをＯＳに対し発行する（２行目）。この場合にはコンテキストスイッチに備えて書き込みの内容は他のタスクから参照可能となる。
【００５０】
その後ただちに、第２獲得部１２０は、一時停止したそのタスクの動作を再開させてそのタスクをＣＰＵによって動作させる（３行目）。これによりこのタスクの動作は再開され、再開後においては一時停止までの書き込みの内容は他のタスクから参照可能となっている。
以上、第２例によれば、オペレーティングシステムに備わるスレッド停止・再開の機能を利用して、他のタスクから書込み内容を強制的に反映させることができる。
【００５１】
図１５は、書込反映処理の第３例を示す。第３例は、書込み内容を反映させるために他のタスクに働きかけることはせず、当該他のタスクにより自発的に書込み内容が反映されるまで、一定時間待機するということを内容とする。具体的には、第２獲得部１２０は、書込反映処理の要求を受けると（１行目）、一定期間待機してから（２行目）処理を終了する。より詳細には、第２獲得部１２０は、第１獲得部１００により第１情報を書き込む命令が発行された後にその第１情報が第２のタスク１５０により参照可能となるまでに要する時間を充分に超える時間待機することが好ましい。このような時間の上限値が、メモリコントローラ等の仕様によって予め定められている場合には、第２獲得部１２０は、その仕様によって定まる時間を待機すればよい。これにより、第１獲得部１００による第１情報の書込みと第２獲得部１２０によるその読出の順序を保証することができる。
【００５２】
さらに、情報システム１０を実現するコンピュータのアーキティクチャによっては、第１獲得部１００により第２記憶領域１６５を読み出すために発行する読出命令が、その前に発行される命令より先行して投機的に実行される場合がある。このような場合には、第２獲得部１２０は、上記の時間に加えて、読出命令が本来実行されるべき時点と最も先行して実行される場合の実行時点との差分値を加えることが望ましい。これにより、第１のタスク１４０が第２記憶領域１６５を参照したうえで第１記憶領域１６２に対し書込みを発行した場合に、その内容を第２のタスク１５０において適切に読み出すことができる。
なお、第２のタスクはこの待機時間の間に、当該排他制御に関わらない他の処理を行ってもよい。
【００５３】
図１６は、本実施形態の第２変形例に係る情報システム１０の全体構成を示す。本変形例に係る情報システム１０は、図５を参照して説明した実施形態と比較して、複数の第１のタスクを動作させている点が異なる。これらのタスクを第１のタスク１４０−１〜Ｎとする。第１のタスク１４０−１〜Ｎのそれぞれは、ＯＳやミドルウェアなどによって管理されたスレッドであり、互いに独立してプログラムの処理を進める。プログラムの実行中には、記憶装置１６０内に記憶領域が確保され、演算処理結果の格納などのために用いられる場合がある。
【００５４】
Ｊａｖａ（登録商標）言語などの言語処理系において、プログラムの実行中に確保された記憶領域は、そのプログラム中でそれを明示的に解放する命令が実行されなくとも、ガーベージコレクタと呼ばれるソフトウェアにより自動的に解放される。そのガーベージコレクタを実現するのが第２のタスク１５０である。即ち、第２のタスク１５０は、第１のタスク１４０−１〜Ｎにより既に参照されなくなったメモリ上の記憶領域を検出して、以降の処理において再利用可能とするために解放するガーベージコレクション（ＧＣ）を行う。ここで、記憶領域を確保して使用するタスク（たとえば第１のタスク１４０−１）と、その記憶領域の解放を試みるタスク（たとえば第２のタスク１５０）とが異なる場合には、排他制御が必要となる。本第２変形例は、このような排他制御を実現することを目的とする。
【００５５】
情報システム１０は、図５に示す情報システム１０と同様に、記憶装置１６０を有する。しかしながら、本変形例における記憶装置１６０は、図５に示す記憶装置１６０とは異なり、複数の第１のタスク１４０のそれぞれに対応する複数の第１記憶領域１６２のそれぞれと、複数の第１のタスク１４０のそれぞれに対応する複数の第２記憶領域１６５のそれぞれとを有する。それぞれ、第１記憶領域１６２−１〜Ｎおよび第２記憶領域１６５−１〜Ｎとする。その他の構成については図５に示す構成と略同一であるから説明を省略する。
【００５６】
この変形例において、ある第１のタスク１４０（たとえば第１のタスク１４０−１とする）は、ＧＣを実行することができないクリティカルセクションの実行に先立って、排他権の獲得を第１獲得部１００に要求する。ここでいうクリティカルセクションとは、処理中に第２のタスク１５０によるガーベージコレクションを行わせることができない予め定められた処理を行うプログラム中の領域をいう。そして、第１のタスク１４０−１は、排他権の獲得を条件にその予め定められた処理を行い、その予め定められた処理の実行後に排他権の解放を第１獲得部１００に要求する。このような排他権は、実行するプログラムの性質によっては極めて頻繁に獲得される場合が多い。なおかつ、その獲得は多くの場合には成功しており、獲得に要する時間が無駄になっている。
【００５７】
第１獲得部１００は、第１のタスク１４０−１から排他権の獲得の要求を受けると、第１情報をその第１のタスク１４０−１に対応する第１記憶領域１６２−１に書き込む命令を実行した後に、その第１のタスク１４０−１に対応する第２記憶領域１６５−１を読み出す。そして、第１獲得部１００は、第２情報が読み出されなかったことを条件に排他権の獲得が成功したことを返答する。第２情報が読み出されたことを条件に、第１獲得部１００は、第１記憶領域１６２−１から第１情報を消去して排他権の獲得が失敗したことを第１のタスク１４０−１に返答する。第１解放部１１０は、第１のタスク１４０−１による排他権の解放の要求に応じ、第１情報を対応する第１記憶領域１６２−１から消去する。
【００５８】
一方、第２のタスク１５０は、ガーベージコレクションを行う前に排他権の獲得を第２獲得部１２０に要求する。そして、第２のタスク１５０は、全ての排他権の獲得を条件にガーベージコレクションを行い、ガーベージコレクションを行った後に排他権の解放を第２獲得部１２０に要求する。ガーベージコレクションの頻度は、第１のタスク１４０が排他権の獲得を試行する頻度と比較して小さい。このため、この獲得にはある程度の処理時間を要しても構わない。
【００５９】
第２獲得部１２０は、第２のタスク１５０から、第１のタスク１４０−１〜Ｎの全てについて排他権の獲得をするべく要求を受ける。すると、第２獲得部１２０は、第２情報を第２記憶領域１６５−１〜Ｎのそれぞれに書き込んでそれぞれの第１のタスク１４０から参照可能とする。この参照可能とする処理は、前述のように、たとえばストアフラッシュ命令によって実現されてよい。その後に、第２獲得部１２０は、第１のタスク１４０−１〜Ｎのそれぞれを指定した複数の書込反映処理の要求を順次送信する。ここでいう書込反映処理とは、書き込みを反映させる第１のタスク１４０を指定して、書込みを反映させる要求を送信してから、書き込みの反映まで待機する処理である。書込みを反映させる要求とは、たとえばシグナルの送信であり、書き込みの反映まで待機する処理とは、たとえば、書込みが反映された旨の通知を第１のタスク１４０から受ける処理である。
【００６０】
そして、第２獲得部１２０は、何れの第１のタスク１４０においても書込みが反映させるまで待機する。そして、全ての書込反映処理の完了後にそれぞれの第１記憶領域１６２を読み出し、何れの第１記憶領域１６２からも第１情報が読み出されなかったことを条件に、第１のタスク１４０−１〜Ｎについての全ての排他権が成功したことを第２のタスク１５０に返答する。一方、何れかの第１記憶領域１６２から第１情報が読み出されたことを条件に、第２獲得部１２０は、その第１記憶領域１６２に対応する第２記憶領域１６５から第２情報を消去して排他権の獲得が失敗したことを第２のタスク１５０に返答する。第２解放部１３０の動作は図５に示したものと略同一である。第２解放部１３０は、たとえば、第２のタスク１５０から、全ての排他権を解放する旨の要求を受けると、第２記憶領域１６５−１〜Ｎのそれぞれから第２情報を消去する。これにより、第１のタスク１４０−１〜Ｎの動作が再開可能となる。
【００６１】
図１７は、本実施形態の第２変形例に係る第２獲得部１２０が排他権の獲得を試行する処理のフローチャートである。なお、第１獲得部１００の動作は図５を参照して説明したものと同一であるから説明を省略し、第２獲得部の動作のみ説明する。第２獲得部１２０は、第２のタスク１５０から、第１のタスク１４０−１〜Ｎの全てについて排他権の獲得をするべく要求を受けると、第２情報を第２記憶領域１６５−１〜Ｎのそれぞれに書き込んで（Ｓ１７００）それぞれの第１のタスク１４０から参照可能とする（Ｓ１７１０）。その後に、第２獲得部１２０は、第１のタスク１４０−１〜Ｎのそれぞれを指定した複数の書込反映処理の要求を順次送信する（Ｓ１７２０）。
【００６２】
そして、第２獲得部１２０は、何れの第１のタスク１４０においても書込みが反映させるまで待機する（Ｓ１７３０）。そして、全ての書込反映処理の完了後に（Ｓ１７３０：ＹＥＳ、Ｓ１７４０）、第１記憶領域１６２−１〜Ｎを順次読み出し（Ｓ１７５０）、何れの第１記憶領域１６２からも第１情報が読み出されなかったことを条件に（Ｓ１７５５：ＮＯ）、第１のタスク１４０−１〜Ｎについての全ての排他権が成功したことを第２のタスク１５０に返答する（Ｓ１７６０）。一方、何れかの第１記憶領域１６２から第１情報が読み出されたことを条件に（Ｓ１７５５：ＹＥＳ）、第２獲得部１２０は、その第１記憶領域１６２に対応する第２記憶領域１６５から第２情報を消去して（Ｓ１７７０）排他権の獲得が失敗したことを第２のタスク１５０に返答する（Ｓ１７８０）。
第２のタスクはこの後、獲得に失敗した排他権について再度同様の獲得を試みる。全ての排他権を獲得した後に、ＧＣ処理を開始する。
【００６３】
以上、第２変形例として示したように、通常のプログラムを実行する第１タスクと、ガーベージコレクションを必要に応じて時々行う第２タスクとが競合する場合には、第１タスクにより排他権が高頻度で獲得され、第２タスクによりその排他権は稀にしか獲得されない。このように排他権の獲得頻度に偏りがある場合には、本実施形態に示す排他制御の方式は特に有効である。すなわち、システム全体として排他権の獲得またはその試行に要する時間を削減することができる。さらには、一斉に複数の排他権を獲得したい場合には、それぞれの排他権獲得のために必要なそれぞれの書込反映処理を並行して行うことで、排他権獲得に要する時間を節約することができる。
【００６４】
図１８は、本実施形態又はその変形例に係る情報システム１０として機能する情報処理装置５００のハードウェア構成の一例を示す。情報処理装置５００は、ホストコントローラ１０８２により相互に接続されるＣＰＵ１０００−１、ＣＰＵ１０００−２、ＲＡＭ１０２０、及びグラフィックコントローラ１０７５を有するＣＰＵ周辺部と、入出力コントローラ１０８４によりホストコントローラ１０８２に接続される通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を有する入出力部と、入出力コントローラ１０８４に接続されるＲＯＭ１０１０、フレキシブルディスクドライブ１０５０、及び入出力チップ１０７０を有するレガシー入出力部とを備える。
【００６５】
ホストコントローラ１０８２は、ＲＡＭ１０２０と、高い転送レートでＲＡＭ１０２０をアクセスするＣＰＵ１０００−１〜２及びグラフィックコントローラ１０７５とを接続する。ＣＰＵ１０００−１〜２は、ＲＯＭ１０１０及びＲＡＭ１０２０に格納されたプログラムに基づいて動作し、各部の制御を行う。グラフィックコントローラ１０７５は、ＣＰＵ１０００−１〜２等がＲＡＭ１０２０内に設けたフレームバッファ上に生成する画像データを取得し、表示装置１０８０上に表示させる。これに代えて、グラフィックコントローラ１０７５は、ＣＰＵ１０００−１〜２等が生成する画像データを格納するフレームバッファを、内部に含んでもよい。
【００６６】
入出力コントローラ１０８４は、ホストコントローラ１０８２と、比較的高速な入出力装置である通信インターフェイス１０３０、ハードディスクドライブ１０４０、及びＣＤ−ＲＯＭドライブ１０６０を接続する。通信インターフェイス１０３０は、ネットワークを介して外部の装置と通信する。ハードディスクドライブ１０４０は、情報処理装置５００が使用するプログラム及びデータを格納する。ＣＤ−ＲＯＭドライブ１０６０は、ＣＤ−ＲＯＭ１０９５からプログラム又はデータを読み取り、ＲＡＭ１０２０又はハードディスクドライブ１０４０に提供する。
【００６７】
また、入出力コントローラ１０８４には、ＲＯＭ１０１０と、フレキシブルディスクドライブ１０５０や入出力チップ１０７０等の比較的低速な入出力装置とが接続される。ＲＯＭ１０１０は、情報処理装置５００の起動時にＣＰＵ１０００−１〜２が実行するブートプログラムや、情報処理装置５００のハードウェアに依存するプログラム等を格納する。フレキシブルディスクドライブ１０５０は、フレキシブルディスク１０９０からプログラム又はデータを読み取り、入出力チップ１０７０を介してＲＡＭ１０２０またはハードディスクドライブ１０４０に提供する。入出力チップ１０７０は、フレキシブルディスク１０９０や、例えばパラレルポート、シリアルポート、キーボードポート、マウスポート等を介して各種の入出力装置を接続する。
【００６８】
情報処理装置５００に提供されるプログラムは、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５、又はＩＣカード等の記録媒体に格納されて利用者によって提供される。プログラムは、入出力チップ１０７０及び/又は入出力コントローラ１０８４を介して、記録媒体から読み出され情報処理装置５００にインストールされて実行される。プログラムが情報処理装置５００等に働きかけて行わせる動作は、図１から図１７を参照して説明した実施形態または変形例における情報システム１０の動作と同一であるから、説明を省略する。
【００６９】
以上に示したプログラムは、外部の記憶媒体に格納されてもよい。記憶媒体としては、フレキシブルディスク１０９０、ＣＤ−ＲＯＭ１０９５の他に、ＤＶＤやＰＤ等の光学記録媒体、ＭＤ等の光磁気記録媒体、テープ媒体、ＩＣカード等の半導体メモリ等を用いることができる。また、専用通信ネットワークやインターネットに接続されたサーバシステムに設けたハードディスク又はＲＡＭ等の記憶装置を記録媒体として使用し、ネットワークを介してプログラムを情報処理装置５００に提供してもよい。
【００７０】
以上、本実施形態またはその変形例によれば、競合する２つのタスクの間の排他制御において、一方のタスクにおいて排他制御のために他方のタスクによるメモリ書込みを強制的に反映させることにより、当該他方のタスクにおいて排他制御に要する時間を大幅に短縮することができる。これにより、当該他方のタスクのみが頻繁に排他権を獲得する場合など、実用的にはかなりの場面で想定される状況において、排他権の獲得に要する全体の時間を削減することができる。さらに、書込みを強制的に反映させる処理は、現在または将来想定されるさまざまなコンピュータの構造に応じて、適切な技術を選択して利用させることができる。
【００７１】
以上、本発明を実施の形態を用いて説明したが、本発明の技術的範囲は上記実施の形態に記載の範囲には限定されない。上記実施の形態に、多様な変更または改良を加えることが可能であることが当業者に明らかである。その様な変更または改良を加えた形態も本発明の技術的範囲に含まれ得ることが、特許請求の範囲の記載から明らかである。
【図面の簡単な説明】
【００７２】
【図１】図１は、排他制御の第１実装例を示す。
【図２】図２は、排他制御の第２実装例を示す。
【図３】図３は、排他制御の第３実装例を示す。
【図４】図４は、第２実装例においてメモリバリア命令を実行しないと問題の生じる例を示す。
【図５】図５は、本実施形態に係る情報システム１０の全体構成を示す。
【図６】図６は、第１獲得部１００が排他権の獲得を試行する処理のフローチャートである。
【図７】図７は、第２獲得部１２０が排他権の獲得を試行する処理のフローチャートである。
【図８】図８は、本実施形態に係る排他制御の実装例を示す。
【図９】図９は、本実施形態に係る排他制御をＷｅａｋｌｙ−ｏｒｄｅｒｅｄメモリモデルに適用した例を示す。
【図１０】図１０は、本実施形態の第１変形例に係る情報システム１０の全体構成を示す。
【図１１】図１１は、本実施形態の第１変形例に係る第２獲得部１２０が排他権の獲得を試行する処理のフローチャートである。
【図１２】図１２は、本実施形態の第１変形例に係る排他制御の実装例を示す。
【図１３】図１３は、書込反映処理の第１例を示す。
【図１４】図１４は、書込反映処理の第２例を示す。
【図１５】図１５は、書込反映処理の第３例を示す。
【図１６】図１６は、本実施形態の第２変形例に係る情報システム１０の全体構成を示す。
【図１７】図１７は、本実施形態の第２変形例に係る第２獲得部１２０が排他権の獲得を試行する処理のフローチャートである。
【図１８】図１８は、本実施形態又はその変形例に係る情報システム１０として機能する情報処理装置５００のハードウェア構成の一例を示す。
【符号の説明】
【００７３】
１０  情報システム
１００  第１獲得部
１１０  第１解放部
１２０  第２獲得部
１３０  第２解放部
１４０  第１のタスク
１５０  第２のタスク
１６０  記憶装置
１６２  第１記憶領域
１６５  第２記憶領域
１７０  シグナルハンドラ部
５００  情報処理装置
【図１】
2008112400.tif 000003
【図２】
2008112400.tif 000004
【図３】
2008112400.tif 000005
【図４】
2008112400.tif 000006
【図５】
2008112400.tif 000007
【図６】
2008112400.tif 000008
【図７】
2008112400.tif 000009
【図８】
2008112400.tif 000010
【図９】
2008112400.tif 000011
【図１０】
2008112400.tif 000012
【図１１】
2008112400.tif 000013
【図１２】
2008112400.tif 000014
【図１３】
2008112400.tif 000015
【図１４】
2008112400.tif 000016
【図１５】
2008112400.tif 000017
【図１６】
2008112400.tif 000018
【図１７】
2008112400.tif 000019
【図１８】
2008112400.tif 000020