(57)【特許請求の範囲】
【請求項１】
計算機が有する物理乱数発生器が出力する乱数を複数のユーザプロセスが同時に利用することを可能にする物理乱数発生器の制御方法であって、前記計算機は、
前記物理乱数発生器の出力を格納する複数の乱数バッファと、前記乱数バッファに確保されている乱数の使用状況を記録するバッファ使用状況と、前記乱数バッファにアクセスしているプロセス数を記録するアクセスカウンタと、プロセス間の排他を取るためのプロセス間ロックと、前記乱数バッファの内容を更新するよう前記物理乱数発生器に要求し、更新完了後にその乱数バッファに対応するバッファ使用状況に未使用を記録する動作を行うドライバプロセスからなり、ユーザプロセスが前記乱数バッファにアクセスする際は、その乱数バッファに対応するアクセスカウンタの値を＋１し、乱数取得完了時にアクセスカウンタの値を−１すると共に、対応するバッファ使用状況に使用済を記録する制御方法であって、
前記ユーザプロセスは、プロセス間排他が必要と設定された場合、前記プロセス間ロックを獲得できたときは乱数バッファにアクセスし、プロセス間ロックを獲得できなければ、プロセス間ロックを獲得するまで待機する排他処理を行い、プロセス間排他が不要と設定されていた場合、前記排他処理を行うことなく、乱数バッファにアクセスすることを特徴とする制御方法。
【請求項２】
前記ドライバプロセスは前記バッファ使用状況と前記アクセスカウンタの内容を参照し、
対応するバッファ使用状況が使用済かつ対応するアクセスカウンタの値が０である場合のみ乱数バッファの内容を更新するように前記物理乱数発生器に要求し、
更新後は対応するバッファ使用状況を未使用に設定することを特徴とする請求項１記載の制御方法。
【請求項３】
前記ユーザプロセスは、プロセス間排他が必要と設定された場合、乱数取得完了後にロックを開放することを特徴とする請求項１または２記載の制御方法。
【請求項４】
前記ユーザプロセスが複数のスレッドを有する場合、各スレッドが独立して前記乱数バッファにアクセスすることを許し、前記スレッドが前記乱数バッファにアクセスする際は、その乱数バッファに対応するアクセスカウンタの値を＋１し、アクセス完了時にアクセスカウンタの値を−１すると共に、対応するバッファ使用状況に使用済を記録することを特徴とする請求項１から３のいずれか１項に記載の制御方法。
【請求項５】
前記ユーザプロセスはスレッド間ロックを有し、前記スレッドは、スレッド間排他が必要と設定された場合、そのスレッドの親プロセスが有するスレッド間ロックを獲得できたときは乱数バッファにアクセスして、乱数取得完了後にロックを開放し、そのスレッド間ロックを獲得できなければ、そのスレッド間ロックを解放するまで待機することを特徴とする請求項１から４のいずれか１項に記載の制御方法。
【請求項６】
前記乱数バッファは、複数のＣＰＵおよびメモリインターコネクトを有する計算機において、各メモリインターコネクト配下のメモリ上に、自身と同一の内容を格納するコピーバッファを有し、前記ドライバプロセスは、前記乱数バッファの内容が更新された時、その乱数バッファに対応するコピーバッファ全てにその乱数バッファの内容をコピーすることを特徴とする請求項１から５のいずれか１項に記載の制御方法。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、物理乱数発生器の制御方法に関するものである。
【背景技術】
【０００２】
計算機上で、乱数は自然科学などのシミュレーション、暗号の鍵生成など、多くの場面に用いられる。計算機上で用いる乱数は、０と１からなる２進乱数である。この２進乱数としては、ソフトウェアで何らかのアルゴリズムに従い計算される擬似乱数が用いられることが多い。しかし、このようにして得られる擬似乱数には、何らかの周期性や規則性がある。
【０００３】
２進乱数の乱数性は、０と１の出現比率が等しいこと（等確率性）、過去の出力によらず、次に出現するパターンが０か１か予測できないこと（無規則性）の２つで評価される。前述の擬似乱数は、等確率性は満たしているが、特定のアルゴリズムを用いているので周期性や規則性があるため、次のパターンをある程度予測できてしまう。すなわち、無規則性を満たしていない。
【０００４】
これら擬似乱数の周期性や規則性が結果に影響してはならない用途のため、自然界の、規則性の無い現象を元に乱数を生成する物理乱数発生器がある。元にする自然現象としては、特許２９８０５７６号のような、抵抗の熱雑音や半導体の熱雑音などが用いられる。物理乱数発生器が出力する物理乱数は、前述の通り、規則性の無い自然現象を基に生成されるので、次の出現パターンを予測することはできない。すなわち無規則性を満たしている。等確率性については、自然現象から２進乱数への変換を行う回路の特性により、ごくわずかな偏りが出現する可能性がある。しかし、例えば特許３６８００９１号のような手段により、この偏りを打ち消すことが可能である。従って、物理乱数は等確率性、無規則性の両方を満たしている乱数である。
【０００５】
一つの擬似乱数列を分割し、複数のプロセスで使用する場合を考える。分割の方法によっては、分割後の擬似乱数列の周期は、元の擬似乱数列の周期よりも短くなる。逆に、同種の擬似乱数をまとめて一つの乱数列にすることも、似た出力が繰り返し出現する危険性がある。一方、物理乱数では、順序を入れ替える、乱数列の一部を抜き取る、複数の生成源から出力された物理乱数をまとめて１つにするなど、乱数列の内容に依存しない操作を行っても、等確率性、無規則性は変化しない。すなわち、乱数の質は変わらない。よって、計算機に搭載される物理乱数発生器が１つであっても、その出力を分割して渡せば、複数のプロセスが同時に物理乱数を使用できる。逆に、複数の物理乱数発生器を搭載した場合、それらの出力する物理乱数を適当に結合して一つのプロセスに渡すことで、プロセスが利用できる乱数生成速度を搭載台数に比例して向上させることも可能である。
【先行技術文献】
【特許文献】
【０００６】
【特許文献１】特許２９８０５７６号公報
【特許文献２】特許３６８００９１号公報
【発明の概要】
【発明が解決しようとする課題】
【０００７】
前述のように、計算機に搭載されている物理乱数発生器が1つでもあれば、その出力を分割して、任意の数のプロセスが同時に物理乱数を使用できる。
【０００８】
しかし、このように物理乱数発生器の出力を分割し、各プロセスに供給するという方法では、同時に実行するプロセスの数が増加するに従って、ひとつのプロセスが利用できる物理乱数の生成速度は小さくなってしまう。物理乱数発生器の乱数生成速度が、プロセスのメモリアクセス速度以下の場合、各プロセスの動作速度が物理乱数発生器の性能に左右されることになる。計算機の性能向上により、１台の計算機を同時に使用できるユーザーの数も増加するため、物理乱数発生器の乱数生成速度の重要性はますます高まっている。
【０００９】
本発明の目的は、同時に続行するプロセスの数が増加した場合でも、個々のプロセスが単位時間当たりに取得できる物理乱数の量を維持することにある。
【課題を解決するための手段】
【００１０】
物理乱数発生器を搭載した計算機内のメモリ上に、物理乱数発生器のドライバプロセスが管理する共有メモリを確保し、この領域に物理乱数発生器から出力された物理乱数を一度書き込む。その後、複数のプロセスが同時に物理乱数を要求した場合、それらのプロセス間に関係があるか調べ、無関係なプロセス間には同一乱数データへのアクセスを許す。複数のプロセスが同時に乱数を利用する場合でも、個々のプロセスは物理乱数発生器の生成速度と同等の速度で乱数を得ることができる。
【００１１】
一方、プロセス間に関連性がある場合、それらが同一の乱数データにアクセスできてしまうのは問題がある。このため、関連性があるプロセス間では、それぞれ異なる手法で生成された、異なる乱数データにしかアクセスできないように制御を行う。異なる乱数とプロセスとの関係は、物理乱数を使用するユーザーが自由に設定できるものとする。
【００１２】
また、同一乱数データへのアクセスを許すことにより、メモリアクセスがメモリ上の特定位置に集中する。従って、乱数を取得するプロセス数が増加すると、メモリスループットの制約により、個々のプロセスの乱数取得速度が低下する。この速度低下を緩和するため、共有メモリを複数確保し、複数の共有メモリに同一の乱数データをコピーして、各プロセスのメモリアクセスを分散させる。特に、複数のＣＰＵを搭載し、搭載するＣＰＵのそれぞれがメモリインターコネクトを持つ構成の計算機に本発明を適用すれば、それら複数のメモリインターコネクトを利用することができるので、メモリスループットによる各プロセスの乱数取得速度低下を抑制できる。
【発明の効果】
【００１３】
本発明における物理乱数発生器の制御方法によれば、物理乱数を同時に使用するプロセスの数が増加した場合でも、個々のプロセスが単位時間当たりに取得できる物理乱数の量を維持することが可能である。
【図面の簡単な説明】
【００１４】
【図１】本発明の形態の一つである物理乱数発生器の実施例を示すブロック図である。
【図２】図１の形態においてプロセスが乱数を取得する手順を示すフローチャートである。
【図３】図１の形態においてプロセスが乱数格納領域にアクセスして乱数を取得する手順を示すフローチャートである。
【図４】図1の形態において複数のプロセスが同一乱数を取得する際の動作を示すシーケンス図である。
【図５】図１の形態におけるドライバプロセスの動作を示すフローチャートである。
【図６】図１の形態においてプロセスが使用した乱数をドライバプロセスが更新する際の動作を示すシーケンス図である。
【図７】図１の形態の効果を示す図である。
【図８】本発明の他の形態の物理乱数発生器の実施例を示すブロック図である。
【図９】図７の形態においてスレッドが乱数格納領域にアクセスして乱数を取得する手順を示すフローチャートである。
【図１０】本発明の他の形態の物理乱数発生器の実施例を示すブロック図である。
【図１１】図１０の形態におけるデータの流れを表すブロック図である。
【図１２】図１０の形態におけるドライバプロセスの動作を示すフローチャートである。
【発明を実施するための形態】
【実施例１】
【００１５】
以下で本発明を実施するための形態を、図面を参照しながら解説する。
図１に、本発明の一形態の実施例を示す。図１は、計算機に搭載された物理乱数発生器１１、乱数及びその生成を制御するための情報を格納するメモリ１２、及び乱数の生成を制御する処理手段（装置又はプログラム）であるドライバプロセス１３を示す。
【００１６】
物理乱数発生器１１は、実際に自然現象から物理乱数を生成する乱数源である。物理乱数発生器１１は、ドライバプロセス１３から乱数転送命令１９３を受け取ると、メモリ上の指定されたアドレスに、指定された長さの乱数データ１９２を書き込む能力を有する。また、乱数転送命令により指示された書き込みの完了後、書き込み完了報告１９４を命令の送信元であるドライバプロセス１３に返す。図１では、物理乱数発生器１１は計算機に１つのみ存在しているが、これを複数搭載することも可能である。複数搭載した場合でも、それらの出力を結合して渡すことが可能なので、1つの高速な物理乱数発生器が搭載されているとみなすことが可能である。
【００１７】
乱数格納領域１７は、複数の乱数バッファ１〜Ｎ（１７０１〜１７０３）からなる。プロセスが乱数を取得したり、物理乱数発生器が乱数を更新したりする場合、この乱数バッファを一つの単位として処理する。乱数格納領域１７を複数の乱数バッファに分けることで、物理乱数発生器１１がいずれかの乱数バッファを更新中でも、プロセスが別の乱数バッファから並行して乱数を取得することが可能になる。
【００１８】
管理情報領域１８は、メモリ上に格納されている乱数の使用状況とアクセス状況を保持するための領域である。管理情報領域１８は、プロセス間ロック１８１と、アクセスカウンタ１〜Ｎ（１８２１〜１８２３）と、乱数が使用済かどうかを記録するバッファ使用状況１〜Ｎ（１８３１〜１８３３）からなる。本実施例において、プロセス間ロック１８１は、複数のプロセスが同時に乱数を取得しようとする際に、設定に応じてプロセス間の排他処理を行うために用いる。アクセスカウンタ１〜Ｎ（１８２１〜１８２３）の値は、それぞれが一つの乱数バッファ１〜Ｎ（１７０１〜１７０３）にアクセスしているプロセス数を表す（即ち、プロセスが乱数を取得するとアクセスカウンタには１が加算される）。アクセスカウンタは、更新のタイミングを図るために用いる。本実施例では、１つの乱数バッファに複数プロセスが同時にアクセスするため、一つのプロセスが乱数取得を完了し、使用済を設定し（即ち、アクセスカウンタを１減らす）ても、別のプロセスはまだ同じ乱数バッファから乱数を取得中の可能性がある。従って、乱数の更新が可能かどうかを判断するため、乱数取得中のプロセスが存在しないということを確認する手法が必要である。アクセスカウンタの値が０のときはどのプロセスも乱数バッファにアクセスしていないので更新可能、１以上ならアクセス中のプロセスがいるので更新不可能、といった判断が可能になる。
【００１９】
バッファ使用状況１〜Ｎ（１８３１〜１８３３）は、それぞれ一つの乱数バッファ１〜Ｎ（１７０１〜１７０３）の内容が使用済か未使用かを表すために用いる。使用済とされている乱数バッファは、過去にいずれかのプロセスが乱数の取得を完了したことを表す。
【００２０】
プロセスあるいはドライバプロセスが管理情報領域１８にアクセスする場合、同時に一つのプロセス、もしくはドライバプロセスしかアクセスできないように排他処理を行う必要がある。
【００２１】
ドライバプロセス１３は、計算機の起動と同時に開始され、計算機の稼働中は常時動作し続ける。ドライバプロセス１３は、開始時に乱数格納領域１７と、管理情報領域１８をメモリ上に確保する。また、起動中は管理情報領域１８から管理情報１９１を読み書きして、乱数バッファの管理を行う。また、アクセスカウンタが０となって使用済の乱数バッファがあれば、その内容を更新するように、物理乱数発生器１１に乱数転送命令１９３を発行する。
【００２２】
プロセス１〜Ｍ（１４１〜１４３）は、物理乱数を使用するユーザプロセスである。プロセス１〜Ｍ（１４１〜１４３）は、管理情報領域１８にアクセスして、管理情報の確認や更新を行い（１９１１〜１９１３）、乱数格納領域１７から乱数データを取得する（１９２１〜１９２３）。プロセス１〜Ｍ（１４１〜１４３）には、プロセス間の排他が必要かどうかを表す排他条件１〜Ｍ（１５１〜１５３）と、乱数格納領域１７にアクセスするためのアクセスポインタ１〜Ｍ（１６１〜１６３）が必要である。この実施例では、排他条件はプロセス間排他必要、排他不要の２つの値を取る。排他必要、とされたプロセスは、同じく排他必要とされた別のプロセスと同じ乱数を取得しない。排他不要、とされたプロセスは、他のいかなるプロセスとも同じ乱数を取得できる。従って、二つのプロセスがそれぞれ排他不要と設定されている場合、それらのプロセス間で排他は行われない。排他不要とされたプロセスが多いほど、全プロセスの合計乱数取得速度が上がる。排他条件はユーザーが任意に設定できる。
【００２３】
図1の実施例において、プロセスが乱数を取得する場合のフローチャートを図２に示す。まず、ステップ２１で初期化を行う。ステップ２１では、アクセスポインタに、乱数格納領域１７の先頭乱数バッファ１（１７０１）のアドレスを設定する。また、自身の排他条件を設定する。乱数格納領域１７のアドレスは、ドライバプロセス１３がファイルに書き出したキーファイルを介して獲得する、あるいは、オペレーティングシステムへのシステムコールを介して獲得する方法などがある。設定を終えたらステップ２２へ進む。
【００２４】
ステップ２２では、プロセス間排他が必要に設定されているかどうかを確認する。ステップ２１で排他条件をプロセス間排他必要と設定されていれば、ステップ２３に進む。排他不要と設定されていれば、ステップ２５に進む。ステップ２３では、プロセス間ロック１８１がかかっているかどうか確認する。ロックがかかっている場合は、別の排他対象になっているプロセスがロックを獲得して乱数取得中である。よって、そのプロセスがプロセス間ロック１８１を開放するまで繰り返しステップ２３を実行する。ロックがかかっていなければ、ステップ２４でプロセス間ロック１８１を獲得してステップ２５に進む。ステップ２５では、乱数格納領域１７から乱数を取得する。乱数取得時の詳細な動作は図３で説明する。乱数を必要量取得したらステップ２６に進む。
【００２５】
ステップ２６では、プロセス間排他が必要に設定されているか確認する。必要と設定されている場合はステップ２７に進み、ステップ２４で確保したプロセス間ロック１８１を開放する。不要に設定されている場合はプロセス間ロック１８１を獲得していないので、何もする必要はない。
【００２６】
図３に、ステップ２５で乱数格納領域１７にアクセスし、乱数を乱数バッファから取得する際のフローチャートを示す。最初に乱数格納領域１７にアクセスした場合、ステップ３１で、現在アクセスしようとしている乱数バッファが使用済かどうかを確認するため、対応するバッファ使用状況を確認する。例えば、乱数バッファ１（１７０１）が使用済かどうかを確認するにはバッファ使用状況１（１８３１）を確認する。バッファ使用状況に使用済と記録されていれば、ステップ３７に進む。未使用と記録されていればステップ３２に進む。
【００２７】
ステップ３２では乱数バッファに対応するアクセスカウンタの値に１を加える。例えば、乱数バッファ１（１７０１）にアクセスしようとしている場合はアクセスカウンタ１（１８２１）の値に１を加える。完了したらステップ３３に進む。ステップ３３では、アクセスポインタの指している乱数バッファから乱数を取得する。プロセスに必要な量の乱数を取得した、あるいは、乱数バッファ内の乱数を全て取得したらステップ３４に進む。ステップ３４では、対応するアクセスカウンタの値から１を引き、ステップ３５に進む。ステップ３５では、対応するバッファ使用状況を使用済に設定し、ステップ３６に進む。
【００２８】
ステップ３６では、必要な量の乱数を取得したか確認する。必要量を取得した場合は呼び出し元に戻る。まだ必要量に達しておらず、別の乱数バッファからさらに乱数を取得する必要がある場合はステップ３７に進む。ステップ３７では、アクセスポインタを次に乱数取得を試みる乱数バッファに移動する。例えば、乱数バッファ１（１７０１）から乱数を取得していたなら、アクセスポインタを乱数バッファ２（１７０２）に移動する。最後尾の乱数バッファＮ（１７０３）から乱数を取得していたなら、アクセスポインタを先頭の乱数バッファ１（１７０１）に移動する。移動後、再度ステップ３１からの処理を繰り返す。
【００２９】
図1の実施例において、２つのプロセスが同時に同じ乱数を取得する場合のシーケンス図を図４に示す。この図では、乱数バッファ４５から２つのプロセス１（４１）と２（４２）が同時に乱数を取得する。乱数バッファ４５には、アクセスカウンタ４３とバッファ使用状況４４が対応している。プロセス１（４１）と２（４２）は、共に排他条件が排他不要に設定されているものとする。区間４１０、４２０、４５０はそれぞれプロセス１（４１）、２（４２）および乱数バッファ４５の活性区間を表す。４３０、４４０はアクセスカウンタ４３、バッファ使用状況４４の各時点におけるそれぞれの内容を表す。
【００３０】
まず、プロセス１（４１）がステップ４１１でバッファ使用状況４４を確認する。ステップ４１１を実行した時点でのバッファ使用状況４４は未使用に設定されているので、プロセス１（４１）は乱数バッファ４５から乱数取得を開始してよいと判断する。プロセス１（４１）は、ステップ４１２でアクセスカウンタの値に１を加える。その後、ステップ４１３で乱数バッファ４５にアクセスして乱数取得を開始する。
【００３１】
一方、プロセス２（４２）もほぼ同時に乱数バッファから乱数取得を試みる。プロセス２（４２）は、ステップ４２１でバッファ使用状況４４を確認する。ステップ４２１の時点でも、バッファ使用状況４４はまだ未使用に設定されている。よって、プロセス２（４２）も乱数バッファ４５から乱数取得を開始してよいと判断する。プロセス２（４２）はプロセス１（４１）と同様に、ステップ４２２でアクセスカウンタの値に１を加えて２に更新し、ステップ４２３で乱数バッファ４５から乱数取得を開始する。同一の乱数バッファ４５に同時にアクセスするので、プロセス２（４２）は、プロセス１（４１）が取得したものと同じ乱数を取得する。
【００３２】
その後、プロセス１（４１）はステップ４１４で乱数バッファ４５からの乱数取得を完了し、ステップ４１５でアクセスカウンタ４３から1を引く。アクセスカウンタ４３の値は２になっているので、プロセス１（４１）は、１をアクセスカウンタ４３に記録する。さらにステップ４１６で、乱数バッファ４５の乱数が使用済であることをバッファ使用状況４４に記録し、乱数取得を終了する。このとき使用済を記録すると、乱数バッファ４５から乱数取得を開始することは禁止されるが、すでに乱数取得中のプロセス２（４２）には影響は無い。
【００３３】
プロセス２（４２）はステップ４２４で乱数取得を完了し、ステップ４２５でアクセスカウンタ４３から１を引いてアクセスカウンタの値を０にする。さらに、ステップ４２６でバッファ使用状況４４に使用済を記録する。ステップ４２６の時点では、バッファ使用状況４４がすでに使用済になっているため、バッファ使用状況４４の値は変化しない。
【００３４】
図４からわかるように、ステップ４１２からステップ４１５までの間はバッファ使用状況４４が未使用になっているため、別プロセスも乱数バッファ４５から乱数取得を開始できる（ステップ４１１から４１２までの間、ステップ４１５から４１６の間など、他プロセスが管理情報領域１８にアクセスしている場合は、排他処理により管理情報領域１８にアクセスできず、乱数取得も開始できない）。このように、バッファ使用状況を使用済にするタイミングを乱数取得完了後にすれば、複数のプロセスによる、一つの乱数バッファへの同時アクセスが発生し、それらが同一の乱数を取得する。
【００３５】
なお、通常プロセスがメモリにアクセスする速度は、物理乱数発生器１１の乱数生成速度より高速である。この場合、乱数格納領域１７の乱数が全て使用済になった後、複数のプロセスが図３のステップ３１と３７を繰り返し行う更新待ち状態になる。この状態では、ドライバプロセス１３が使用済になっている乱数バッファの更新を行い、乱数使用状況を未使用に設定した直後に、更新を待っていたプロセスがほぼ同時にその乱数バッファにアクセスを試みる。従って、図４のような１つの乱数バッファへの同時アクセスは頻繁に発生する。
【００３６】
図５は、図１の実施例における、ドライバプロセス１３の起動後からの動作フローである。ドライバプロセス１３は、起動後、ステップ５１で初期化を行う。この初期化では、メモリ上に乱数格納領域１７、管理情報領域１８を確保し、確保した乱数格納領域１７の全領域に乱数を転送するよう、物理乱数発生器１１に要求する。転送完了後、アクセスカウンタ１〜Ｎ（１８２１〜１８２３）を全て０に設定し、バッファ使用状況１〜Ｎ（１８３１〜１８３３）を全て未使用に設定する。その後、プロセスが乱数格納領域１７、管理情報領域１８を見つけられるように、オペレーティングシステムへ通知、あるいは、キーファイルの設定などを行う。最後に、先頭の乱数バッファ１（１７０１）を次のステップ５２で最初に確認する対象に選び、ステップ５２に進む。
【００３７】
ステップ５２では、確認対象の乱数バッファに対応するバッファ使用状況を見て、使用済が設定されているかを確認する。確認の結果、バッファ使用状況が使用済に設定されていた場合はステップ５３に進む。未使用であればステップ５７に進む。ステップ５３では、確認対象の乱数バッファに対応するアクセスカウンタが０かどうかを確認する。アクセスカウンタの値が０であれば、その乱数バッファから乱数取得中のプロセスが存在しないので、更新可能としてステップ５４に進む。それ以外の値であれば、乱数取得中のプロセスが存在しているため、アクセスカウンタの値が０になるまでステップ５３を繰り返し、プロセスの乱数取得完了を待つ。
【００３８】
ステップ５４では、物理乱数発生器１１に乱数バッファへの乱数転送を要求する。要求の送信後ステップ５５に進み、物理乱数発生器１１から乱数転送完了が報告されるまで待機する。乱数転送完了が報告されたらステップ５６に進む。ステップ５６では、更新された乱数バッファに対応するバッファ使用状況を未使用に設定し、ステップ５７に進む。ステップ５７では、次に確認する乱数バッファに移動する。例えば、先頭の乱数バッファ１（１７０１）を確認していたのであれば、乱数バッファ２（１７０２）を次の確認対象とする。最後尾の乱数バッファＮ（１７０３）を確認していたのであれば、先頭の乱数バッファ１（１７０１）を次の確認対象とする。移動完了したら、再度ステップ５２に進む。
【００３９】
ドライバプロセス１３は乱数を利用するプロセスの動作状況に関係なく、常時動作し続ける。また、ドライバプロセス１３は管理情報領域１８のみを参照して乱数を更新するか否か判断する。乱数を利用する側のプロセスとは、管理情報領域１８にアクセスする際の排他制御を除き、非同期に動作する。
【００４０】
図６はドライバプロセス６１（図１の１３と同じ）の動作を表すシーケンス図である。この図では、図４でプロセス１（４１）と２（４２）に乱数を取得され、使用済となった乱数バッファ４５をドライバプロセス６１が更新する場合の動作を示す。この図６の開始時点では、２つのプロセス１（４１）と２（４２）が乱数バッファ４５から乱数を取得中であるとする。区間６１０、６２０は活性区間を表す。
【００４１】
ドライバプロセス６１は、ステップ６１１、６１２のように、バッファ使用状況４４が使用済になっていないかを定期的に確認する。ステップ６１１の時点では、バッファ使用状況４４は未使用に設定されている。従って、ドライバプロセス６１は何も行わない。その後、プロセス１（４１）が乱数バッファ４５から乱数の取得を完了し、ステップ４１５でアクセスカウンタ４３の値を１に、ステップ４１６でバッファ使用状況４４を使用済に更新する。
【００４２】
次にドライバプロセス６１がステップ６１２でバッファ使用状況４４を確認したときには、使用済が設定されている。この場合は、乱数バッファ４５の内容を更新する必要があるので、ステップ６１３でアクセスカウンタ４３を確認し、乱数バッファ４５から乱数取得中のプロセスが残っているか確認する。この時点ではプロセス２（４２）が乱数取得中なので、アクセスカウンタの値は１になっている。ドライバプロセス６１はアクセスカウンタ６１の値が０になるまで確認を繰り返す。ステップ６１４で確認した時点では、プロセス２（４２）が乱数取得を完了し、ステップ４２５でアクセスカウンタを０に更新済である。よって、ドライバプロセス６１は乱数バッファ４５を更新可能な状態であることを確認できたので、ステップ６１５で物理乱数発生器６２に乱数バッファ４５の更新を要求する。
【００４３】
物理乱数発生器６２は、ドライバプロセス６１からの乱数更新要求を受け取ると、ステップ６２１で、指定された乱数バッファ４５に乱数を転送して乱数を更新する。その後、ステップ６２２で転送を完了したら、ステップ６２３で更新完了をドライバプロセス６１に通知する。一方、ドライバプロセス６１はステップ６１５の完了後、物理乱数発生器６２からの完了報告を待つ。完了報告を受け取った時点で、乱数バッファ４５の内容は更新済なので、ドライバプロセス６１はステップ６１６でバッファ使用状況６２を未使用に設定し、プロセスが再び乱数バッファ４５から乱数を取得できるようにする。
【００４４】
図７に、本実施例における効果を示す。この図では、物理乱数発生器１１の乱数生成速度は１００ＭＢ／ｓとする。図７（ａ）のように、乱数を使用する２つのプロセス１（１４４），２（１４５）が各自で物理乱数発生器１１に乱数要求１９３１、１９３２を行い、乱数を取得する従来の構成では、それぞれのプロセスが乱数データ１９２４，１９２５を取得する速度は、最大で物理乱数発生器１１の能力の半分となる。プロセス数が増加すれば、速度はさらに低下する。
【００４５】
一方、本実施例では、図７（ｂ）のように、物理乱数発生器１１が乱数格納領域１７に転送した乱数を、プロセス１（１４１），２（１４２）が取得する。二つのプロセスは、同一の乱数を取得するので、それぞれのプロセスが乱数データ１９２１，１９２２を取得する速度は最大で物理乱数発生器１１の乱数生成速度と同等である。プロセス数がさらに増加しても、メモリアクセスのスループットに影響されない限り、乱数取得速度は低下しない。
【実施例２】
【００４６】
次に、図１の形態を変形した別の形態を示す。この形態では、プロセスが一つまたは複数のスレッド（Threads, 処理単位）を生成し、生成された各スレッドが独自に乱数を取得することを可能にする。
【００４７】
図８は、この別の形態における実施例を示す図である。この構成では、一つのプロセス１（７１１）が複数のスレッド１１〜１Ｍ（７２１１〜７２１２）を生成する。プロセス２（７１２）のように、生成するスレッドが１つだけでも良い。排他条件１１〜１Ｍ、２１（１５１〜１５３）、アクセスポインタ１１〜１Ｍ、２１（１６１〜１６３）はプロセスごとではなく、スレッドごとに保持される。また、各プロセスはプロセス内ロック７３１〜７３２を一つ持つ。このプロセス内ロックにより、一つのプロセス内のスレッド間で排他を取ることを可能とする。プロセス２（７１２）はスレッドが一つだけのため、プロセス内での排他が不要であるが、後にスレッドを生成する可能性があるため、プロセス内ロックを持つ。
【００４８】
この実施例では、排他条件１１〜１Ｍ、２１（１５１〜１５３）はプロセス間排他、プロセス内排他それぞれについて必要か不要かを保持する。プロセス間排他は、同じくプロセス間排他必要と設定された、自プロセス内のスレッド間、プロセス間の両方で同じ乱数を取得してはならないことを表す。プロセス内排他は、同じくプロセス内排他必要と設定された、自プロセス内のスレッド間では同じ乱数を取得してはならないが、異なるプロセス間では同じ乱数を取得できることを表す。
【００４９】
例として、スレッド１１（７２１１）とスレッド１Ｍ（７２１２）がプロセス内排他必要、プロセス間排他不要で、スレッド２１（７２２１）がプロセス内排他必要、プロセス間排他必要と設定されている場合を示す。スレッド１１（７２１１）と１Ｍ（７２１２）は、同一プロセス内にありプロセス内排他必要なので、お互いに同じ乱数を取得してはならない。また、スレッド２１（７２２１）と１１（７２１１）、１Ｍ（７２１２）の場合、プロセスが異なるのでプロセス内排他の設定は無視される。また、スレッド２１（７２２１）はプロセス間排他必要と設定されているが、スレッド１１（７２１１）はプロセス間排他不要とされているので、排他の必要はない。すなわち、同じ乱数を取得してよい。
【００５０】
この実施例において、アクセスカウンタ１〜Ｎ（１８２１〜１８２３）は、乱数バッファ１〜Ｎ（１７０１〜１７０３）にアクセスしているプロセス数ではなく、スレッド数を表す。例えば、乱数バッファ１（１７０１）にスレッド１１（７２１１）と１Ｍ（７２１２）がアクセスしている時、アクセスしているプロセスはプロセス１（７１１）のみであるが、アクセスカウンタ１（１８２１）の値はアクセスしているスレッド数である２である。同様に、プロセス間ロック１８１もスレッド単位での排他に用いる。例えば、スレッド１１（７２１１）とスレッド１Ｍ（７２１２）が共にプロセス間排他必要と設定されていれば、スレッド１１（７２１１）がプロセス間ロック１８１を獲得している間、スレッド１Ｍ（７２１２）は乱数格納領域１７にアクセスできない。
【００５１】
図９は、図８の構成において、スレッドが乱数を取得する際のフローを表す。まず、ステップ８１で初期化を行う。初期化をスレッド単位で行う以外は、ステップ２１と同じである。次に、ステップ８２でプロセス内の排他が必要かどうかを確認するため、排他情報がプロセス内排他に設定されているかどうかを確認する。プロセス内排他必要に設定されている場合はステップ８３に進む。それ以外の場合はステップ２２に進み、図２と同様にステップ２２〜２７で乱数を取得し、ステップ８５に進む。ステップ８３では、自プロセスのプロセス内ロックが他のスレッドに獲得されているかどうか確認する。ロックがかかっている場合は、自プロセス内の排他対象スレッドが乱数取得中なので、そのスレッドがプロセス内ロックを開放するまで繰り返しステップ８３を実行する。ロックがかかっていなければ、ステップ８４に進んでプロセス内ロックを獲得した後、ステップ２２〜２７で乱数を取得し、ステップ８５に進む。ステップ８５では、プロセス内排他が必要か調べ、必要だった場合はステップ８６でプロセス内ロックを開放して終了する。不要であれば、そのまま終了する。
【実施例３】
【００５２】
次に、図１の構成と異なる別の実施例について説明する。この変形例では、乱数格納領域１７のミラーリングを行うことにより、プロセスが乱数を取得する際のメモリアクセスを分散させることが可能となる。
【００５３】
図１０に、この変形例における実施例を、前提となる計算機の構成と共に表す。まず、前提となる計算機の構成について説明する。この構成では、一台の計算機に複数のＣＰＵ１〜Ｎ（９１１〜９１３）が搭載されている。ＣＰＵ１（９１１）はメモリインターコネクト９２１および外部インターフェース９４を有する。ＣＰＵ２〜Ｎ（９１２〜９１３）はそれぞれメモリインターコネクト９２２〜９２３を有する。また、ＣＰＵ１〜Ｎ（９１１〜９１３）は、お互いにＣＰＵ間インターコネクト９３で接続されており、これを通じてＣＰＵ同士での通信が可能である。メモリインターコネクト９２１〜９２３には、それぞれメモリ１２１〜１２３が接続されている。
【００５４】
ＣＰＵ１〜Ｎ（９１１〜９１３）がそれぞれメモリ１〜Ｎ（１２１〜１２３）と通信する場合、このメモリインターコネクト９２１〜９２３を介して通信を行う。ＣＰＵ１〜Ｎ（９１１〜９１３）が直接接続されていないメモリと通信を行う場合、ＣＰＵ間インターコネクト９３を経由して通信を行う。物理乱数発生器１１は外部インターフェース９４を通じて計算機と接続されている。メモリ１２１には乱数格納領域１７と管理情報領域１８が確保される。それ以外のメモリ２〜Ｎ（１２２〜１２３）には、それぞれ乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）が確保される。
【００５５】
メモリ１２１に乱数格納領域１７と管理情報領域１８を確保する理由は、物理乱数発生器１１からＣＰＵ間インターコネクト９３を経由することなくアクセスが可能なためである。同様の理由により、ドライバプロセス９５もＣＰＵ９１１上で動作するようにする。乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）は、乱数格納領域１７と同一の内容を保持する。
【００５６】
また、乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）は乱数格納領域１７と同様、複数のミラーバッファに分けられている。ミラーバッファは乱数格納領域１７の乱数バッファに1対１で対応し、乱数バッファと対応するミラーバッファの内容は、内容更新中のときを除き、同一である。例えば、乱数バッファ１７０１と、ミラーバッファ１７１１〜１７２１の内容は全て同一である。この実施例において、管理情報領域１８は、乱数格納領域１７に加え、すべての乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）の使用状況、アクセス状況も表す。即ち、アクセスカウンタ１８２１は乱数バッファ１７０１とミラーバッファ１７１１〜１７２１にアクセスしているプロセス数の合計を表す。例えば、２つのプロセスがそれぞれミラーバッファ１７１１と１７２１にアクセスしているとき、アクセスカウンタ１８２１の値は２である。同様に、バッファ使用状況は乱数バッファとそのミラーバッファの使用状況を表す。例えば、あるプロセスがミラーバッファ１７１１から乱数を取得した場合、取得完了後にバッファ使用状況１８３１が使用済に設定される。この後は、プロセスはミラーバッファ１７１１だけでなく、乱数バッファ１７０１、ミラーバッファ１７２１のいずれからも乱数取得を開始してはならない。
【００５７】
図１１は、図１０にデータの流れを追記した図である。本実施例において、プロセス１１〜Ｎ１（９６１〜９６３）は、乱数格納領域１７の代わりに乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）にアクセスしても乱数の取得が可能である。各プロセスは、もっとも高速にアクセスできる乱数格納領域、または乱数格納領域ミラーにアクセスして乱数を取得するものとする。例として、プロセス９６１が乱数を取得する場合を考える。
【００５８】
プロセス９６１はＣＰＵ１（９１１）上で動作している。ＣＰＵ１（９１１）からもっとも高速にアクセスできるメモリは、メモリインターコネクト９２１を介して直結しているメモリ１（１２１）である。従って、プロセス１１（９６１）が乱数を取得する場合は、メモリ１（１２１）に確保されている乱数格納領域１７にアクセスして乱数データ１９２１を取得する。同様に、プロセス２１〜Ｎ１（９６２〜９６３）が乱数を取得する場合は、それぞれ乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）にアクセスして、乱数データ１９２２〜１９２３を取得する。プロセスがどのＣＰＵ上で動作しているかは、ＣＰＵ番号をシステムコールで要求する、ユーザーがプロセスを特定のＣＰＵに割り当てる、などの方法で判断できる。
【００５９】
本実施例のようなミラーバッファを確保せず、メモリアクセスを分散させない場合には、乱数を取得したいプロセスが全てメモリ１（１２１）にアクセスすることになる。この場合、全プロセスの乱数取得速度合計は、メモリ１（１２１）またはメモリインターコネクト９２１のスループットにより制限されるため、多くのプロセスが乱数を取得しようとする場合には、個々のプロセスの乱数取得速度が低下してしまう。本実施例では、各プロセスが、自身の動作しているＣＰＵに応じて、異なるメモリインターコネクト経由で乱数を取得することができるので、乱数取得時のメモリアクセスを分散することができる。従って、各プロセスが上記のような制限を受けることなく、同一の乱数を取得することが可能である。
【００６０】
使用済となった乱数バッファ、ミラーバッファの更新は、物理乱数発生器１１が乱数格納領域１７を更新した後、ドライバプロセス９５が更新された乱数格納領域１７の乱数データ１９５をそれぞれの乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）にコピーすることで行う。
【００６１】
なお、図１０、図１１では、すべてのメモリ１〜Ｎ（１２１〜１２３）に乱数格納領域ミラーを確保しているが、必ずしも全てのメモリ上に確保する必要はない。例えば、ＣＰＵ数が１６で、同時に動作するプロセス数が高々３，４ならば、乱数格納領域ミラーの数を減らし、バッファ更新時のコピー回数を抑えるほうが良い。
【００６２】
図１２は、この実施例におけるドライバプロセス９５の動作を示すフローチャートである。ドライバプロセス９５はステップ１０１で初期化を行う。この例では、ドライバプロセス９５は、計算機のメモリ１〜Ｎ（１２１〜１２３）上に管理情報領域１８および乱数格納領域１７、乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）を確保し、確保した乱数格納領域１７に乱数を転送するよう、物理乱数発生器１１に要求する。転送が完了したら、乱数格納領域１７の乱数データを、全ての乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）にコピーする。コピーが完了したら、アクセスカウンタ１〜Ｎ（１８２１〜１８２３）を全て０に設定し、バッファ使用状況１〜Ｎ（１８３１〜１８３３）を未使用に設定する。
【００６３】
これら初期設定が完了したら、プロセスが乱数格納領域１７、あるいは乱数格納領域ミラー１〜Ｎ−１（１７１〜１７２）を見つけられるように、オペレーティングシステムへ通知、あるいは、キーファイルの設定などを行う。初期化の後は、ステップ５２、５７で使用済とされた乱数バッファを見つける。見つかった場合、ステップ５３〜５５を順に実行し、乱数バッファが更新されるまで待つ。
【００６４】
更新完了後、ステップ１０２で、先程更新された乱数バッファの内容を読み取り、その乱数バッファに対応する、全てのミラーバッファに乱数バッファの内容をコピーする。コピーが完了したら、ステップ５６で乱数バッファを未使用に設定し、ステップ５７に進んで、次の乱数バッファに対し同様の処理を繰り返す。
【符号の説明】
【００６５】
１１    物理乱数発生器
１２、１２１〜１２３    メモリ
１３、９５    ドライバプロセス
１４１〜１４５、７１１〜７１２、９６１〜９６３    プロセス
１５１〜１５３    排他条件
１６１〜１６３    アクセスポインタ
１７    乱数格納領域
１７１〜１７２    乱数格納領域ミラー
１７０１〜１７０３    乱数バッファ
１７１１〜１７２１    ミラーバッファ
１８    管理情報領域
１８１    プロセス間ロック
１８２１〜１８２３    アクセスカウンタ
１８３１〜１８３３    バッファ使用状況
１９１１〜１９１３、１９１    管理情報
１９２１〜１９２５、１９２、１９５    乱数データ
１９３、１９３１，１９３２    乱数転送命令
１９４    完了報告
７２１１〜７２１２、７２２１    スレッド
７３１〜７３２    プロセス内ロック
９１１〜９１３    ＣＰＵ
９２１〜９２３    メモリインターコネクト
９３    ＣＰＵ間インターコネクト
９４    外部インターフェース。
【図１】
0005476277.tif 000002
【図２】
0005476277.tif 000003
【図３】
0005476277.tif 000004
【図４】
0005476277.tif 000005
【図５】
0005476277.tif 000006
【図６】
0005476277.tif 000007
【図７】
0005476277.tif 000008
【図８】
0005476277.tif 000009
【図９】
0005476277.tif 000010
【図１０】
0005476277.tif 000011
【図１１】
0005476277.tif 000012
【図１２】
0005476277.tif 000013