(57)【要約】      （修正有）【課題】スレッド間において、ＣＡＳ操作を利用せずに、矛盾なく情報の受け渡しをすることが可能なスレッド間通信方法、スレッド間通信システム、及びスレッド間通信プログラムを提供する。【解決手段】各スレッドには他のスレッドの数に相当する数だけバッファが用意されており、送信スレッドＴ１が、バッファにおける格納先ポインタ変数が指す場所にレコードを格納する。また、取り出しスレッドであるスレッドＴＯが、バッファから取得先ポインタ変数が指す場所からレコードを取り出す。このように、各スレッドには他のスレッドの数に相当する数だけバッファが用意された上で、送信スレッドによるバッファへのレコードの格納と、取り出しスレッドによるバッファからのレコードの取り出しとが行われる。【選択図】図２
2015005123.tif 000002
【特許請求の範囲】
【請求項１】
レコードを格納可能なノードの場所を指すポインタ情報が格納されるポインタ変数からの当該ポインタ情報の読み込み処理と、当該ポインタ変数へのポインタ情報の書き込み処理とが、不可分に可能な環境において、複数のスレッドが互いにレコードを送受信するためのスレッド間通信システムであって、
各スレッドには、他のスレッドの数に相当する数だけリングバッファが用意されており、各リングバッファは、互いに異なる他のスレッドの一つと対応付けられ、
前記各リングバッファは、次のレコードを格納する場所を指す格納先ポインタ変数と、次のレコードを取り出す場所を指す取得先ポインタ変数とを有し、
前記各リングバッファにおける取得先ポインタ変数の指す所定の場所が初期値として決定されるとともに、前記取得先ポインタ変数の指す場所の次の場所が、前記格納先ポインタ変数が指す場所の初期値として決定され、
レコードの送信元である送信スレッドは、
他のスレッドが処理を担当する一のレコードが入力されると、当該他のスレッドのリングバッファにおける、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所ではない場合は、前記他のスレッドのリングバッファに空きがあると判断し、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所である場合は、前記他のスレッドのリングバッファに空きがないと判断するバッファ判断手段と、
前記バッファ判断手段において、当該リングバッファに空きがあると判断されると、前記格納先ポインタ変数が指す場所に前記一のレコードを格納するとともに、前記格納先ポインタ変数が指す場所を次の場所に変更する第１の変更手段と、
を備えるスレッド間通信システム。
【請求項２】
前記送信スレッドは、
前記バッファ判断手段において、前記リングバッファに空きがないと判断されると、前記リングバッファに空きができるまで所定時間待機して、前記リングバッファへの前記一のレコードの格納処理を実行する実行手段を
さらに備える請求項１に記載のスレッド間通信システム。
【請求項３】
前記リングバッファからレコードを取り出す取出スレッドは、
前記取得先ポインタ変数が指す場所の次の場所が、前記格納先ポインタ変数が指す場所ではない場合は、前記リングバッファに処理すべき前記一のレコードがあると判断し、前記取得先ポインタ変数が指す次の場所が、前記格納先ポインタ変数が指す場所である場合は前記リングバッファに処理すべき前記一のレコードはないと判断するレコード判断手段と、
前記レコード判断手段において、処理すべき前記一のレコードがあると判断されると、前記取得先ポインタ変数が指す場所の次の場所から当該処理すべき前記一のレコードを前記リングバッファから取り出してから、前記取得先ポインタ変数が指す場所を次の場所に変更する第２の変更手段と、
を備える請求項１または２に記載のスレッド間通信システム。
【請求項４】
前記各スレッドには、前記リングバッファに１対１に対応付けられている送受信リンクリストが用意されており、
前記送信スレッドは、
前記バッファ判断手段において、当該リングバッファに空きがないと判断されると、前記一のレコードを格納するためのノードを新規作成するノード作成手段と、
前記ノード作成手段において作成されたノードに、前記一のレコードを格納して、前記送受信リンクリストに追加するノード追加手段と、
を備え、
前記リングバッファからレコードを取り出す取出スレッドは、
前記リングバッファから、処理すべきレコードの取り出し処理を行うとともに、前記送受信リンクリストに、前記一のレコードを格納したノードが追加されているか否かを判断するノード判断手段と、
前記ノード判断手段において当該ノードが追加されたと判断された場合には、当該ノードから前記一のレコードを取り出すレコード取出手段と、
を備える請求項１に記載のスレッド間通信システム。
【請求項５】
前記各スレッドには、前記リングバッファと前記送受信リンクリストとの組に１対１に対応付けられている保管リンクリストが用意されており、
前記送信スレッドは、
当該送信スレッドが前記送受信リンクリストに追加するノードを用意する際、前記保管リンクリストに再利用できるノードが存在する場合には、当該保管リンクリストから当該再利用可能なノードを取り出すノード取出手段と、
を備え、
前記ノード追加手段は、前記ノード取出手段において取り出されたノードにレコードを格納して、当該ノードを前記送受信リンクリストに追加し、
前記ノード作成手段は、前記保管リンクリストに再利用できるノードが存在しない場合には、ノードを新規生成し、
前記取出スレッドは、
前記送受信リンクリストからノードを取り出して、当該ノードからレコードを取り出した後、取り出され使用済みとなったノードを前記保管リンクリストに追加する追加手段を
備える請求項４に記載のスレッド間通信システム。
【請求項６】
レコードを格納可能なノードの場所を指すポインタ情報が格納されるポインタ変数からの当該ポインタ情報の読み込み処理と、当該ポインタ変数へのポインタ情報の書き込み処理とが、不可分に可能な環境において、複数のスレッドが互いにレコードを送受信するためのスレッド間通信システムのスレッド間通信方法であって、
各スレッドには、他のスレッドの数に相当する数だけリングバッファが用意されており、各リングバッファは、互いに異なる他のスレッドの一つと対応付けられ、
前記各リングバッファは、次のレコードを格納する場所を指す格納先ポインタ変数と、次のレコードを取り出す場所を指す取得先ポインタ変数とを有し、
前記各リングバッファにおける取得先ポインタ変数の指す所定の場所が初期値として決定されるとともに、前記取得先ポインタ変数の指す場所の次の場所が、前記格納先ポインタ変数が指す場所の初期値として決定され、
レコードの送信元である送信スレッドは、
他のスレッドが処理を担当する一のレコードが入力されると、当該他のスレッドのリングバッファにおける、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所ではない場合は、前記他のスレッドのリングバッファに空きがあると判断し、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所である場合は、前記他のスレッドのリングバッファに空きがないと判断するバッファ判断ステップと、
前記バッファ判断ステップにおいて、当該リングバッファに空きがあると判断されると、前記格納先ポインタ変数が指す場所に前記一のレコードを格納するとともに、前記格納先ポインタ変数が指す場所を次の場所に変更する変更ステップと、
を備えるスレッド間通信方法。
【請求項７】
レコードを格納可能なノードの場所を指すポインタ情報が格納されるポインタ変数からの当該ポインタ情報の読み込み処理と、当該ポインタ変数へのポインタ情報の書き込み処理とが、不可分に可能な環境において、複数のスレッドが互いにレコードを送受信するためのスレッド間通信システムとしての機能をコンピュータに実現させるスレッド間通信プログラムであって、
各スレッドには、他のスレッドの数に相当する数だけリングバッファが用意されており、各リングバッファは、互いに異なる他のスレッドの一つと対応付けられ、
前記各リングバッファは、次のレコードを格納する場所を指す格納先ポインタ変数と、次のレコードを取り出す場所を指す取得先ポインタ変数とを有し、
前記各リングバッファにおける取得先ポインタ変数の指す所定の場所が初期値として決定されるとともに、前記取得先ポインタ変数の指す場所の次の場所が、前記格納先ポインタ変数が指す場所の初期値として決定され、
レコードの送信元である送信スレッドは、
他のスレッドが処理を担当する一のレコードが入力されると、当該他のスレッドのリングバッファにおける、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所ではない場合は、前記他のスレッドのリングバッファに空きがあると判断し、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所である場合は、前記他のスレッドのリングバッファに空きがないと判断するバッファ判断機能と、
前記バッファ判断機能において、当該リングバッファに空きがあると判断されると、前記格納先ポインタ変数が指す場所に前記一のレコードを格納するとともに、前記格納先ポインタ変数が指す場所を次の場所に変更する変更機能と、
を備えるスレッド間通信プログラム。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、スレッド間通信方法、スレッド間通信システム、及びスレッド間通信プログラムに関する。
【背景技術】
【０００２】
スレッド間で情報の受け渡しを行う典型的な通信方法は、スレッド間で変数を共有し、当該変数の読み書き時に排他ロック機構によるロックを取得することにより、当該変数を介して矛盾なく情報の受け渡しを行うというものである。しかしながら、この方法には、当該変数の読み書きが行われる毎にその都度ロックを取得する必要があることから、処理効率が低下するおそれがあるという問題がある。また、この方法には、場合によってはデッドロックが発生しプログラム動作が破綻してしまうおそれがあるといった問題がある。
【０００３】
この排他ロック機構において起き得る問題を解決するために、ロックフリーな方法（排他ロック機構によるロックを用いない方法）により、スレッド間で情報の受け渡しを行う技術が考えられてきた。例えば非特許文献１には、ハッシュテーブル上において管理対象データの登録情報及び参照カウンタを併せ持ちつつ、これらを一体操作することによって、高並列データ処理に特有の複雑な競合タイミングを部品内部に局所化して隠蔽する技術が記載されている。
【０００４】
非特許文献１に記載の技術では、排他ロック機構の代わりに、ＣＡＳ（Compare And Swap）操作（又はそれに準じる操作）が用いられる。ＣＡＳ操作とは、メモリの位置が指す指定値と保持値とを比較し、一致していれば指示値を更新し、一方、不一致であれば再度、比較処理を行う操作のことであり、複数のスレッドがＣＡＳ操作を行って競合した場合、ただ一つのスレッドだけがＣＡＳ操作に成功し、他のスレッドは失敗するものである。非特許文献１に記載の技術では、ＣＡＳ操作に成功したスレッドがデータ構造への読み書き処理を行い、ＣＡＳ操作に失敗した他のスレッドは成功するまで繰り返しＣＡＳ操作を試みる。このように、ＣＡＳ操作ではロックの取得が行われないため、デッドロックが発生しプログラム動作が破綻してしまうおそれがあるという問題が解決されている。
【先行技術文献】
【非特許文献】
【０００５】
【非特許文献１】新田淳、外１名、「インメモリDBへの適用に向けた実用的で安全な高並列オープンアドレスハッシュテーブル」、情報処理学会論文誌、一般社団法人情報処理学会、平成２４年９月２８日、データベース５（３）、ｐ．１２６−１４０
【発明の概要】
【発明が解決しようとする課題】
【０００６】
しかしながら、上述したように、ＣＡＳ操作を利用する方法には二つの問題が残されている。一つの問題は、ＣＡＳ操作に失敗したスレッドは、成功するまで繰り返しＣＡＳ操作を試みるため、ウェイトフリー（Wait-free：予め定められた時間又はステップ数でＣＡＳ操作が終了すること）とならず、（競合が激しい状況下では）ＣＡＳ操作が終了しないことから、プログラムの処理効率が低下してしまうという問題である。スレッド間の競合は、スレッド数が多くなるほど起こりやすい。実際に、スレッド間の競合が激しい状況においては、スレッド数が多くなるほど、単一スレッドに対して性能はむしろ低下することを示す文献も存在する。昨今は、ＣＰＵのマルチコア化が進み、今後ますます、より多くのスレッドを用いたプログラムが開発されると予想されるため、この問題は重大である。
【０００７】
もう一つの問題は、ＣＡＳ操作自体が、全ての計算機、演算端末、及び／又はプログラミング言語において利用可能とは限らないことである。すなわち、ＣＡＳ操作を利用する方法は、利用可能な環境を限定してしまうということである。
【０００８】
そこで本発明は、上述の問題点を解消する為になされたものであり、スレッド間において、ＣＡＳ操作を利用せずに、矛盾なく情報の受け渡しをすることが可能なスレッド間通信方法、スレッド間通信システム、及びスレッド間通信プログラムを提供することを目的とする。
【課題を解決するための手段】
【０００９】
上述の課題を解決するために、本発明のスレッド間通信システムは、レコードを格納可能なノードの場所を指すポインタ情報が格納されるポインタ変数からの当該ポインタ情報の読み込み処理と、当該ポインタ変数へのポインタ情報の書き込み処理とが、不可分に可能な環境において、複数のスレッドが互いにレコードを送受信するためのスレッド間通信システムであって、各スレッドには、他のスレッドの数に相当する数だけリングバッファが用意されており、各リングバッファは、互いに異なる他のスレッドの一つと対応付けられ、前記各リングバッファは、次のレコードを格納する場所を指す格納先ポインタ変数と、次のレコードを取り出す場所を指す取得先ポインタ変数とを有し、前記各リングバッファにおける取得先ポインタ変数の指す所定の場所が初期値として決定されるとともに、前記取得先ポインタ変数の指す場所の次の場所が、前記格納先ポインタ変数が指す場所の初期値として決定され、レコードの送信元である送信スレッドは、他のスレッドが処理を担当する一のレコードが入力されると、当該他のスレッドのリングバッファにおける、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所ではない場合は、前記他のスレッドのリングバッファに空きがあると判断し、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所である場合は、前記他のスレッドのリングバッファに空きがないと判断するバッファ判断手段と、前記バッファ判断手段において、当該リングバッファに空きがあると判断されると、前記格納先ポインタ変数が指す場所に前記一のレコードを格納するとともに、前記格納先ポインタ変数が指す場所を次の場所に変更する第１の変更手段と、を備えている。
【００１０】
この発明によれば、各送信スレッドにおいて、他のスレッドが処理を担当する一のレコードが入力されると、当該他のスレッドのリングバッファにおける、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所ではない場合は、他のスレッドのリングバッファに空きがあると判断して、格納先ポインタ変数が指す場所に一のレコードを格納するとともに、前納先ポインタ変数が指す場所を次の場所に変更する。これにより、各スレッドには、他のスレッドの数に相当する数だけのリングバッファが用意された上で、送信スレッドによりリングバッファへのレコードの格納を可能にする。したがって、このリングバッファからのレコードからの取り出しをしようとした場合、ＣＡＳ操作を利用せずに、矛盾なく情報の受け渡しをすることが可能になる、という効果を奏する。さらに、リングバッファのサイズを十分大きくすることで、リングバッファに空きがない状況が起きないようにすることで、実質的にウェイトフリー性を確保することができる。
【００１１】
また、本発明のスレッド間通信システムにおいて、前記送信スレッドは、前記バッファ判断手段において、前記リングバッファに空きがないと判断されると、前記リングバッファに空きができるまで所定時間待機して、前記リングバッファへの前記一のレコードの格納処理を実行する実行手段をさらに備える。
【００１２】
この発明によれば、リングバッファに空きがないと判断されると、リングバッファに空きができるまで所定時間待機して、リングバッファへの一のレコードの格納処理を実行することで、バッファへの格納処理を確実に行うことができる。
【００１３】
また、本発明のスレッド間通信システムにおいて、前記リングバッファからレコードを取り出す取出スレッドは、前記取得先ポインタ変数が指す場所の次の場所が、前記格納先ポインタ変数が指す場所ではない場合は、前記リングバッファに処理すべき前記一のレコードがあると判断し、前記取得先ポインタ変数が指す次の場所が、前記格納先ポインタ変数が指す場所である場合は前記リングバッファに処理すべき前記一のレコードはないと判断するレコード判断手段と、前記レコード判断手段において、処理すべき前記一のレコードがあると判断されると、前記取得先ポインタ変数が指す場所の次の場所から当該処理すべき前記一のレコードを前記リングバッファから取り出してから、前記取得先ポインタ変数が指す場所を次の場所に変更する第２の変更手段と、を備えている。
【００１４】
この発明によれば、取得先ポインタ変数が指す場所の次の場所が、格納先ポインタ変数が指す場所ではない場合は、リングバッファに処理すべき一のレコードがあると判断し、取得先ポインタ変数が指す次の場所が、格納先ポインタ変数が指す場所である場合はリングバッファに処理すべき一のレコードはないと判断する。そして、処理すべき一のレコードがあると判断されると、取得先ポインタ変数が指す場所の次の場所から当該処理すべき一のレコードをリングバッファから取り出してから、取得先ポインタ変数が指す場所を次の場所に変更する。これにより、送信スレッドによるリングバッファに対する格納処理と、取出スレッドによるリングバッファからの取出処理とを行う際に、ＣＡＳ操作を利用せずに、矛盾なく情報の受け渡しをすることが可能になる、という効果を奏する。
【００１５】
また、本発明のスレッド間通信システムは、前記各スレッドには、前記リングバッファに１対１に対応付けられている送受信リンクリストが用意されており、前記送信スレッドは、前記バッファ判断手段において、当該リングバッファに空きがないと判断されると、前記一のレコードを格納するためのノードを新規作成するノード作成手段と、前記ノード作成手段において作成されたノードに、前記一のレコードを格納して、前記送受信リンクリストに追加するノード追加手段と、を備え、前記リングバッファからレコードを取り出す取出スレッドは、前記リングバッファから、処理すべきレコードの取り出し処理を行うとともに、前記送受信リンクリストに、前記一のレコードを格納したノードが追加されているか否かを判断するノード判断手段と、前記ノード判断手段において当該ノードが追加されたと判断された場合には、当該ノードから前記一のレコードを取り出すレコード取出手段と、を備えている。
【００１６】
この発明によれば、当該リングバッファに空きがないと判断されると、一のレコードを格納するためのノードを新規作成し、作成されたノードに、一のレコードを格納して、送受信リンクリストに追加する。そして、レコードの取出し処理に際して、リングバッファから、処理すべきレコードの取り出し処理を行うとともに、送受信リンクリストに、一のレコードを格納したノードが追加されているか否かを判断し、当該ノードが追加されたと判断された場合には、当該ノードから一のレコードを取り出す。そして、各スレッドは、リングバッファおよび送受信リンクリストを他のスレッドの数に相当する分だけ用意されていることから、送信スレッドによるリングバッファおよび送受信リンクリストに対する格納処理と、取出スレッドによるリングバッファおよび送受信リンクリストからの取出処理とを行う際に、ＣＡＳ操作を利用せずに、矛盾なく情報の受け渡しをすることが可能になり、かつウェイトフリー性を確保することができる、という効果を奏する。
【００１７】
また、本発明のスレッド間通信システムは、前記各スレッドには、前記リングバッファと送受信リンクリストとの組に１対１に対応付けられている保管リンクリストが用意されており、前記送信スレッドは、当該送信スレッドが前記送受信リンクリストに追加するノードを用意する際、前記保管リンクリストに再利用できるノードが存在する場合には、当該保管リンクリストから当該再利用可能なノードを取り出すノード取出手段と、を備え、前記ノード追加手段は、前記ノード取出手段において取り出されたノードにレコードを格納して、当該ノードを前記送受信リンクリストに追加し、前記ノード作成手段は、前記保管リンクリストに再利用できるノードが存在しない場合には、ノードを新規生成し、前記取出スレッドは、前記送受信リンクリストからノードを取り出して、当該ノードからレコードを取り出した後、取り出され使用済みとなったノードを前記保管リンクリストに追加する追加手段を備えている。
【００１８】
この発明によれば、当該送信スレッドが送受信リンクリストに追加するノードを用意する際、保管リンクリストに再利用できるノードが存在する場合には、当該保管リンクリストから当該再利用可能なノードを取り出し、取り出されたノードにレコードを格納して、当該ノードを送受信リンクリストに追加する。一方、保管リンクリストに再利用できるノードが存在しない場合には、ノードを新規生成して、そのノードにレコードを格納して、当該ノードを送受信リンクリストに追加する。そして、取出スレッドは、取出し処理を行うに際して、送受信リンクリストからノードを取り出して、当該ノードからレコードを取り出した後、取り出され使用済みとなったノードを保管リンクリストに追加する。これにより、使用済みのノードを再利用することができるため、新たなノードの生成を抑制し、処理の効率化を図ることができる。
【００１９】
また、本発明のスレッド間通信システムは、システムの態様のほか、スレッド間通信方法およびスレッド間通信プログラムとしてとらえることができる。
【００２０】
すなわち、本発明のスレッド間通信方法は、レコードを格納可能なノードの場所を指すポインタ情報が格納されるポインタ変数からの当該ポインタ情報の読み込み処理と、当該ポインタ変数へのポインタ情報の書き込み処理とが、不可分に可能な環境において、複数のスレッドが互いにレコードを送受信するためのスレッド間通信システムのスレッド間通信方法であって、各スレッドには、他のスレッドの数に相当する数だけリングバッファが用意されており、各リングバッファは、互いに異なる他のスレッドの一つと対応付けられ、前記各リングバッファは、次のレコードを格納する場所を指す格納先ポインタ変数と、次のレコードを取り出す場所を指す取得先ポインタ変数とを有し、前記各リングバッファにおける取得先ポインタ変数の指す所定の場所が初期値として決定されるとともに、前記取得先ポインタ変数の指す場所の次の場所が、前記格納先ポインタ変数が指す場所の初期値として決定され、レコードの送信元である送信スレッドは、他のスレッドが処理を担当する一のレコードが入力されると、当該他のスレッドのリングバッファにおける、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所ではない場合は、前記他のスレッドのリングバッファに空きがあると判断し、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所である場合は、前記他のスレッドのリングバッファに空きがないと判断するバッファ判断ステップと、前記バッファ判断ステップにおいて、当該リングバッファに空きがあると判断されると、前記格納先ポインタ変数が指す場所に前記一のレコードを格納するとともに、前記格納先ポインタ変数が指す場所を次の場所に変更する変更ステップと、を備えている。
【００２１】
また、本発明のスレッド間通信プログラムは、レコードを格納可能なノードの場所を指すポインタ情報が格納されるポインタ変数からの当該ポインタ情報の読み込み処理と、当該ポインタ変数へのポインタ情報の書き込み処理とが、不可分に可能な環境において、複数のスレッドが互いにレコードを送受信するためのスレッド間通信システムとしての機能をコンピュータに実現させるスレッド間通信プログラムであって、各スレッドには、他のスレッドの数に相当する数だけリングバッファが用意されており、各リングバッファは、互いに異なる他のスレッドの一つと対応付けられ、前記各リングバッファは、次のレコードを格納する場所を指す格納先ポインタ変数と、次のレコードを取り出す場所を指す取得先ポインタ変数とを有し、前記各リングバッファにおける取得先ポインタ変数の指す所定の場所が初期値として決定されるとともに、前記取得先ポインタ変数の指す場所の次の場所が、前記格納先ポインタ変数が指す場所の初期値として決定され、レコードの送信元である送信スレッドは、他のスレッドが処理を担当する一のレコードが入力されると、当該他のスレッドのリングバッファにおける、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所ではない場合は、前記他のスレッドのリングバッファに空きがあると判断し、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所である場合は、前記他のスレッドのリングバッファに空きがないと判断するバッファ判断機能と、前記バッファ判断機能において、当該リングバッファに空きがあると判断されると、前記格納先ポインタ変数が指す場所に前記一のレコードを格納するとともに、前記格納先ポインタ変数が指す場所を次の場所に変更する変更機能と、を備えている。
【発明の効果】
【００２２】
本発明によれば、スレッド間において、ＣＡＳ操作を利用せずに、矛盾なく情報の受け渡しをすることが可能なスレッド間通信方法及びスレッド間通信システムを提供することができる。
【図面の簡単な説明】
【００２３】
【図１】本実施形態におけるスレッド間通信システム１０の主な機能構成の概略を説明するための機能ブロック図である。
【図２】スレッド間通信システム１０による、例として三つのスレッド間での通信の一例を説明するための説明図である。
【図３】入力データ中の各レコードを処理する担当スレッドを、例として三つのスレッドの中から、ｍｏｄｕｌｏにて決定した場合の一例を説明するための説明図である。
【図４】実行制御部１０１による処理の流れを説明するためのフローチャートである。
【図５】、他スレッド（例えば、スレッドＴ１）が、担当スレッド（例えば、スレッドＴ０）のバッファにレコードを格納するための処理を示すフローチャートである。
【図６】バッファＢｍ−ｎのレコードスペースとその取得先ポインタ変数および格納先ポインタ変数とを説明するための説明図である。
【図７】担当スレッドが、そのバッファに格納されているレコードの処理を示すフローチャートである。
【図８】バッファＢｍ−ｎのレコードスペースとその取得先ポインタ変数および格納先ポインタ変数とを説明するための説明図である。
【図９】図７の変形例におけるフローチャートである。
【図１０】プールからの再利用ノードの取り出しと、取り出した再利用ノードのパイプへの追加の様子の詳細を説明するための説明図である。
【図１１】再利用ノードの取り出し処理と、パイプへの追加処理を示すフローチャートである。
【図１２】パイプからのノードの取り出しと、取り出したノードのプールへの追加の様子の詳細を説明するための説明図である。
【図１３】ノードの取り出し処理と、プールへの追加処理を示すフローチャートである。
【図１４】スレッド間通信プログラムのモジュール構成を示すブロック図である。
【発明を実施するための形態】
【００２４】
以下、添付図面を参照しながら本実施形態のスレッド間通信システムおよびスレッド間通信方法について説明する。なお、図面の説明において同一要素には同一符号を付し、重複する説明を省略する。
【００２５】
（１）本実施形態におけるスレッド間通信システムの構成
まず、本実施形態におけるスレッド間通信システムの構成について、図１および図２を用いて説明する。図１は、本実施形態におけるスレッド間通信システム１０の主な機能構成の概略を説明するための機能ブロック図である。また、図２は、スレッド間通信システム１０による、例として三つのスレッド間での通信の一例を説明するための説明図である。
【００２６】
図１に示されるスレッド間通信システム１０は、複数のスレッドが互いにレコードを送受信可能なように当該複数のスレッドを制御するシステムである。スレッド間通信システム１０は、実行中のプログラム内の全てのスレッド毎に対応して存在するように、各スレッド内で生成される。スレッド間通信システム１０は、ＣＡＳ操作を利用せずに、スレッド間において矛盾なくレコード（情報）の受け渡しをすることを可能にする。レコードは、レコードスペースまたはノードに格納することが可能なデータであり、レコードスペースまたはノードの場所（アドレス）は、ポインタ情報によって指し示される。ポインタ情報は、ポインタ変数に格納することが可能な情報である。レコードスペースまたはノードは、ポインタ変数を有することが可能であり、ポインタ変数は、当該レコードスペースまたはノードの次に格納されている後続レコードスペースまたは後続ノードの場所（アドレス）を指し示す。また、スレッド間通信システム１０は、ポインタ変数からのポインタ情報の読み込み処理と、当該ポインタ変数へのポインタ情報の書き込み処理とを、不可分に行える環境に存在する。
【００２７】
なお、図２に示されるように、各スレッドには、他のスレッドの数に相当する数だけバッファが用意されている。例えば、スレッドＴ０には、他のスレッドの数（スレッドＴ１，Ｔ２の二つ）に相当する数のバッファＢ０−１，Ｂ０−２が用意されている。各バッファは、互いに異なる他のスレッドの一つと対応付けられ、当該対応付けられたスレッドから送信されたレコードを格納順を指定して格納することが可能である。例えば、図２に示されるように、バッファＢ０−１はスレッドＴ１と対応付けられ、バッファＢ０−２はスレッドＴ２と対応付けられている。そして、バッファＢ０−１は、スレッドＴ１から送信されたレコードを格納順を指定して格納することが可能であり、バッファＢ０−２は、スレッドＴ２から送信されたレコードを格納順を指定して格納することが可能である。なお、本実施形態におけるバッファとは、いわゆるリングバッファであり、ポインタ変数が指す場所が最後を超えると、最初に戻るように構成されているバッファである。本実施形態においては、このバッファには、レコードスペースがあらかじめ形成されており、このレコードスペースの数等は、実装時に静的に決定してもよいし、起動時に指定してもよい。さらに、設定ファイル等で調整できるようにしてもよい。
【００２８】
つぎに、スレッド間通信システム１０について説明する。図１に示される通り、このスレッド間通信システム１０は、実行制御部１０１（レコード判断手段）、担当スレッド判断部１０２、データ入力部１０３、データ処理部１０４、レコード転送部１０５（実行手段）、バッファ管理部１０６（バッファ判断手段、第１の変更手段、第２の変更手段、実行手段）、及び終了条件判断部１０９を備えて構成されている。また、オプションとして、パイプ管理部１０７（ノード追加手段、ノード判断手段、レコード取出手段）およびプール管理部１０８（ノード取出手段、追加手段、ノード作成手段）を備えて構成してもよい。
【００２９】
なお、バッファ管理部１０６は、他のスレッド（送信スレッド）からの操作に従って、バッファ判断手段、第１の変更手段、および第２の変更手段として機能するものであり、レコード転送部１０５およびバッファ管理部１０６は、レコードの送信元となるスレッドおよびレコードの送信先となるスレッドとが協働することにより実行手段として機能する。また、同様のパイプ管理部１０７およびプール管理部１０８も、他のスレッド（送信スレッド）からの操作に従って、ノード作成手段、ノード追加手段、およびノード取出手段として機能するものである。
【００３０】
実行制御部１０１は、各担当スレッド判断部１０２〜終了条件判断部１０９に対して、他のスレッドとの情報の受け渡しを実行するのに必要な制御を行う制御部分である。例えば、実行制御部１０１は、対応するスレッドへの入力データを、データ入力部１０３から担当スレッド判断部１０２に一定件数読み込ませる制御を行う。ここでは、入力データとは、複数のレコードの集合体であるとする。
【００３１】
また、実行制御部１０１は、当該スレッドにおいてデータ処理部１０４が処理すべきデータの取得元の制御を行う。より詳しくは、実行制御部１０１は、担当スレッド判断部１０２による入力データの処理件数が一定件数に達すると、当該スレッドの処理すべきデータの取得元をバッファ管理部１０６に切り替える制御を行う。ここで、バッファ管理部１０６により管理されるバッファに、他スレッドから転送されてきたレコードが存在する場合、実行制御部１０１は、当該レコード全てをデータ処理部１０４に処理させる。バッファ管理部１０６に蓄えられたレコード全ての処理が完了すると、実行制御部１０１は、再び、入力データの取得元をデータ入力部１０３に切り替える。以降、実行制御部１０１は、入力データの取得元を切り替えながら、レコードを順次処理していく。なお、後述するオプション機能を備えた場合には、そのオプションとなる要素であるパイプ管理部１０７を入力データの取得元として切り換えることができる。
【００３２】
データ入力部１０３は、スレッド間通信システム１０に対応した当該スレッドへの入力データを、担当スレッド判断部１０２に転送して読み込ませる入力処理部分である。
【００３３】
担当スレッド判断部１０２は、入力データ中の各レコードを処理すべき担当スレッドを、所定の方法で判断して決定する。所定の方法とは、例えば、後述するように、各レコードのキーのハッシュ値の、スレッドの総数によるｍｏｄｕｌｏにて決定する方法であってもよく、その他の方法を予め指定する指定手段をプログラマや利用者に提供してもよい。本実施例では、詳細は後述するが、各レコードのキーのハッシュ値の、スレッド総数によるｍｏｄｕｌｏがいずれのスレッドの番号（例：スレッドの数がＮならば、０以上Ｎ−１以下の各整数）と一致するか否かによって判断する方法を用いる。
【００３４】
ここで、自スレッドが処理すべきであると判断された入力レコードは、データ処理部１０４に転送されて処理される。一方、他スレッドが処理すべきであると判断された入力レコードは、レコード転送部１０５によって、該当する他スレッドのバッファ管理部へ転送される。自スレッドと他のスレッドとの間といったようなスレッド間でのレコードの受け渡しには、バッファが用いられる。
【００３５】
データ処理部１０４は、担当スレッド判断部１０２によって処理すべきと判断された入力レコードを処理する処理実行部分である。更に、データ処理部１０４は、バッファ管理部１０６が管理するバッファにレコードが存在する場合に、当該レコードを処理する。なお、後述するパイプ管理部１０７を備えている場合には、そのパイプ管理部１０７のパイプのレコードを処理対象とする。
【００３６】
レコード転送部１０５は、担当スレッド判断部１０２によって他スレッドが処理すべきと判断された入力レコードを当該他スレッドに転送する通信処理部分である。レコード転送部１０５は、担当スレッド判断部１０２から受信した入力レコードを、他のスレッドのバッファ管理部に転送する。各スレッド内のレコード転送部１０５は、他の全てのスレッドのバッファ管理部と通信可能なように接続されている。なお、パイプ管理部１０７およびプール管理部１０８をオプションとして備えている場合には、他のすべてのスレッドのパイプ管理部１０７およびプール管理部１０８と、レコード転送部１０５は通信可能に接続される。
【００３７】
バッファ管理部１０６は、他スレッドから転送されてきたレコードをバッファに格納するための管理部分である。このバッファ管理部１０６は、バッファに対してレコードを格納するためのレコードスペースの管理を行う部分である。他のスレッドは、このバッファ管理部１０６を介して、バッファに空きがあるか否かの判断を行い、空きがある場合には、他のスレッドは、バッファの格納先ポインタ変数に基づいた場所にレコードを格納する。バッファ管理部１０６は、オプションとしてプール管理部１０８を用いない場合においては、レコードスペースの空きがない場合には、空きができるまで待機し、他のスレッドは、バッファに空きができると、バッファ管理部１０６において管理されているバッファの格納先ポインタ変数に基づいた場所にレコードを格納する。
【００３８】
終了条件判断部１０９は、所定の条件が満たされた場合に、自スレッドによる処理が終了したと判断する判断処理部分である。所定の条件とは、「自スレッドにおける入力データの処理が全て完了し終了したこと」、「他のスレッドにおける入力データの処理が全て完了し終了したこと」、且つ「自スレッドの全てのバッファ管理部１０６が管理するバッファにレコードが残っていないこと」のＡＮＤ条件である。
【００３９】
つぎに、オプション機能について説明する。パイプ管理部１０７は、バッファに空きがない場合に、他スレッドから転送されてきたレコードを格納した新規ノードを、自スレッドに対応して用意されたパイプの末尾に追加して格納する処理を、当該他スレッドに行わせるノード管理部分である。まず、他スレッドのレコード転送部が、パイプ管理部１０７へレコードを転送する際に、プールが用いられる構成であれば、当該プールのプール管理部１０８に対して再利用可能なノードがあるかを問い合わせる。ここで、再利用可能なノードが有る場合に、他スレッドは、当該ノードを再利用する。一方で、再利用可能なノードが無い場合に、他スレッドは、当該レコードを格納した新規ノードを生成させる。そして、他スレッドのレコード転送部は、当該新規ノードのポインタ変数に無効値（第一所定値）を設定させつつ、当該新規ノードを対応するパイプの末尾に追加して格納する。
【００４０】
また、パイプ管理部１０７は、データ処理部１０４によるパイプ内のレコードの処理が行われる際に、当該レコードを当該パイプから取り出す。この場合に、パイプ管理部１０７は、パイプの先頭ノードのポインタ変数が無効値（第一所定値）であるか否かを判定する。ここで、当該ポインタ変数が無効値（第一所定値）でないと判定された場合に、パイプ管理部１０７は、自スレッドが、当該ポインタ変数が指す場所のノードからレコードを取り出しつつ当該ノードを新たな先頭ノードとして設定する処理を行うよう制御する。一方、当該ポインタ変数は無効値（第一所定値）であると判定された場合に、パイプ管理部１０７は、自スレッドが、当該パイプから取り出し可能なレコードを格納するノードは無い状態であると判断するよう制御する。
【００４１】
プール管理部１０８は、パイプ管理部１０７の制御によって自スレッドがノードからレコードを取り出す処理を行った場合に、当該レコードが取り出された使用済みノードを再利用するノード管理部である。プール管理部１０８は、ノードからレコードが取り出される処理が行われると、当該レコードが取り出された使用済みノードのポインタ変数（次に格納されている後続ノードの場所を指す）に、無効値（第二所定値）を設定しつつ、当該使用済みノードをプールの末尾に追加して格納する。
【００４２】
また、プール管理部１０８は、他スレッドのレコード転送部によるパイプ管理部１０７へのレコードの転送を検知すると、当該他スレッドから再利用可能なノードの存在についての問い合わせを受けて、再利用可能なノードがプールに格納されていれば、当該再利用可能なノードの存在を当該他スレッドに通知する。より詳しくは、プール管理部１０８は、他スレッドのレコード転送部によるパイプ管理部１０７へのレコードの転送を検知すると、プールにおける先頭ノードのポインタ変数が無効値（第二所定値）であるか否かを判定する。ここで、当該ポインタ変数が無効値（第二所定値）でないと判定された場合に、プール管理部１０８は、プールにおける先頭ノードを当該プールから取り出して新規ノードとして再利用しつつ当該再利用ノードの次にプールに格納されている後続ノードを新たな先頭ノードとして設定する。一方、当該ポインタ変数は無効値（第二所定値）であると判定された場合に、他スレッドが新規ノードを生成する。
【００４３】
また、プール管理部１０８は、レコードが取り出された使用済みノードのポインタ変数（次に格納されている後続ノードの場所を指す）に、無効値（第二所定値）を設定した際に、当該使用済みノードを末尾に追加するプールを複数のプールの中からラウンドロビン方式で選択し、当該選択されたプールの末尾に当該使用済みノードを追加することが可能である。
【００４４】
上述の各構成要件は、各スレッドにより備えられており、バッファ管理部１０６、パイプ管理部１０７、およびプール管理部１０８、並びに各バッファ、各パイプ、各プールは、レコードの送信元となるスレッドにより操作されることで、レコードの格納処理や、プールからの使用済みノードの取出し処理等が行われる。
【００４５】
（２）スレッド間通信システムによるスレッド間通信の一例
引き続き、スレッド間通信システム１０によるスレッド間通信の一例について、図２を用いて説明する。図２に示されるように、ここでは、一例として、三つのスレッドＴ０〜Ｔ２によるスレッド間通信が行われるとして説明する。なお、三つのスレッドＴ０〜Ｔ２のそれぞれには、各スレッドに対応したスレッド間通信システム（図示せず）が存在している。また、一例として、三つのスレッドＴ０〜Ｔ２のそれぞれにより、ハッシュテーブルＨ０〜Ｈ２のそれぞれの編集処理が行われるとする。
【００４６】
ここで、三つのスレッドＴ０〜Ｔ２のそれぞれには、他のスレッドのそれぞれとの通信に用いる専用のバッファ、並びにリンクリストであるパイプ及びプールが用意されている。なお、パイプ及びプールは、オプション機能であり、必須の構成要件ではない。また、スレッド間通信システム１０の制御によって、各プールから使用済みノードの取り出し処理が可能なスレッドおよび各プールに使用済みノードを追加する処理が可能なスレッドは、それぞれ一つに限定されている。更に、スレッド間通信システム１０の制御によって、各バッファのレコードスペースへのレコードの書き込み処理、および、各パイプに対するノードの書き込み処理が可能なスレッドは、一つに限定され、同様に、各バッファのレコードスペースからのレコードの取り出し処理、および、各パイプからのノードの取り出し処理が可能なスレッドは、一つに限定されている。
【００４７】
具体的には、スレッドＴ０には、スレッドＴ１との通信に用いる専用のバッファであるバッファＢ０−１が用意されており、且つ、スレッドＴ２との通信に用いる専用のバッファＢ０−２が用意されている。同様に、スレッドＴ１には、スレッドＴ２との通信に用いる専用のバッファＢ１−２が用意されており、且つ、スレッドＴ０との通信に用いる専用のバッファＢ１−０が用意されている。更に、スレッドＴ２には、スレッドＴ０との通信に用いる専用のバッファＢ２−０が用意されており、且つ、スレッドＴ１との通信に用いる専用のバッファＢ２−１が用意されている。
【００４８】
そして、図２に示されるように、一例としてスレッドＴ０に入力データＤ０が入力されると、自スレッドで処理すべきレコードに関しては、ハッシュテーブルＨ０へ格納される。また、担当スレッド判断部１０２によって他スレッドであるスレッドＴ１で処理すべきと判断されたレコードに関しては、バッファＢ１−０に転送され、ハッシュテーブルＨ１へ格納される。同様に、担当スレッド判断部１０２によって他スレッドであるスレッドＴ２で処理すべきと判断されたレコードに関しては、バッファＢ２−０に転送され、ハッシュテーブルＨ２へ格納される。
【００４９】
このように、三つのスレッドＴ０〜Ｔ２のそれぞれには、他のスレッドのそれぞれとの通信に用いる専用のバッファが用意されており、各バッファにおけるレコードの追加およびレコードの取り出しのそれぞれについて、処理可能なスレッドがそれぞれ一つに限定されていることにより、レコードの追加時におけるスレッド間競合も、レコードの取り出しにおけるスレッド間競合も、発生しない。
【００５０】
ここでは、ＣＡＳ操作が可能な環境よりも広範な環境（全ての計算機、演算端末、及び／又はプログラミング言語）でサポートされている基本特性、すなわち、データとしてのレコードを格納可能なレコードスペースの場所を指すポインタ情報が格納されるポインタ変数へのポインタ値の書き込み処理と、ポインタ変数からのポインタ値の読み込み処理とは、共に不可分に行われる、という特性が利用される。
【００５１】
なお、バッファからレコードの取り出しを行う取出スレッドは、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所ではない場合はバッファに空きがあると判断する。また、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所である場合には、バッファに空きはないと判断する。
【００５２】
これにより、排他ロック機構やＣＡＳ操作を利用することなく、取出スレッドと格納スレッドとの間での競合が解決され、矛盾なくデータの受け渡しを行うことが可能になる。このように、排他ロック機構を用いないことによりロックフリーを実現し、且つＣＡＳ操作を用いないことから、ポインタ情報の読み書きは必ず有限の時間で終了するため、ウェイトフリーの実現が可能になる。
【００５３】
（３）入力データ中の各レコードの担当スレッドをｍｏｄｕｌｏにて決定した場合の一例
引き続き、担当スレッド判断部１０２が、入力データ中の各レコードを処理する担当スレッドをｍｏｄｕｌｏにて決定した場合の一例について、図３を用いて説明する。図３は、入力データ中の各レコードを処理する担当スレッドを、例として三つのスレッドの中から、ｍｏｄｕｌｏにて決定した場合の一例を説明するための説明図である。
【００５４】
図３（ａ）に示されるように、スレッドＴ０〜Ｔ２という三つのスレッド間での通信が行われている状況において、スレッドＴ０に入力データＤ０が入力され、スレッドＴ１に入力データＤ１が入力され、スレッドＴ３に入力データＤ２が入力されたとする。ここで、入力データＤ０は、Ｒｅｃｏｒｄ０−１〜Ｒｅｃｏｒｄ０−６の六つのデータにより構成され、Ｒｅｃｏｒｄ０−１〜Ｒｅｃｏｒｄ０−６のそれぞれのデータのキーのハッシュ値は、ｍｏｄ３（スレッドの総数である３で除した際の余り）であったとする。例えば、Ｒｅｃｏｒｄ０−１のデータのキーのハッシュ値は、「０」であり、Ｒｅｃｏｒｄ０−４のデータのキーのハッシュ値は、「１」であり、Ｒｅｃｏｒｄ０−２のデータのキーのハッシュ値は、「２」であったとする。
【００５５】
ここで、図３（ｂ）に示されるように、キーのハッシュ値が「０」であるレコードは、スレッドＴ０が管理するハッシュテーブルＨ０に対する編集処理に用いられ、キーのハッシュ値が「１」であるレコードは、スレッドＴ１が管理するハッシュテーブルＨ１に対する編集処理に用いられ、キーのハッシュ値が「２」であるレコードは、スレッドＴ２が管理するハッシュテーブルＨ２に対する編集処理に用いられる。これにより、スレッドＴ０に入力されたＲｅｃｏｒｄ０−１はスレッドＴ０における直接処理となり、スレッドＴ０に入力されたＲｅｃｏｒｄ０−４はスレッドＴ１における処理のためバッファＢ１−０（スレッドＴ０からの転送レコードが格納される、スレッドＴ１に用意されたバッファ）に追加され、スレッドＴ０に入力されたＲｅｃｏｒｄ０−２はスレッドＴ２における処理のためバッファＢ２−０（スレッドＴ０からの転送レコードが格納される、スレッドＴ２に用意されたバッファ）に追加される。
【００５６】
（４）スレッド間通信システムによる処理の流れ
引き続き、スレッド間通信システム１０による処理の流れ（スレッド間通信方法）について、図４を用いて説明する。図４は、実行制御部１０１による処理の流れを説明するためのフローチャートである。
【００５７】
図４に示されるように、まず、各スレッドが、自スレッドの入力データの処理から始め、入力データにおける未処理のレコードが残っているか否かを判断する（ステップＳ３０１）。入力データにおける未処理のレコードが残っている場合、担当スレッド判断部１０２に、上述の所定の方法で、当該レコードの担当スレッドは自スレッドであるか否かを判断させる（ステップＳ３０２）。一方、入力データにおける未処理のレコードが残っておらず、全ての処理が完了した場合、ステップＳ３０７に移行する。
【００５８】
ステップＳ３０２において、当該レコードは自スレッドが担当すべきであると判断された場合は、データ処理部１０４に当該レコードが転送されて処理される（ステップＳ３０３）。そして、後述のステップＳ３０４に移行する。一方、当該レコードは他スレッドが担当すべきであると判断された場合は、上述の所定の方法にて担当スレッドが決定されて、レコード転送部１０５が、当該レコードを、担当スレッドに転送する（ステップＳ３０６）。そして、後述のステップＳ３０４に移行する。
【００５９】
ステップＳ３０４において、データ入力部１０３が、処理済みレコード数（自スレッドで処理を担当すべきと判断された入力レコードの総数と、他スレッドで処理を担当すべきと判断された入力レコードの総数との合計である入力レコード合計数）のカウンタ値を１つ増やし、入力レコードが一定数（固定の数値であってもよく、処理開始時に指定された数値であってもよく、設定ファイル等で予め指定されていてもよい）だけ処理されたか否かを判断する（ステップＳ３０４）。一定数に未到達の場合は、ステップＳ３０１へ戻る。一方、一定数に到達した場合は、データ処理部１０４が、上述のカウンタ値を０にリセットすると、バッファ処理（バッファ管理部１０６における、他スレッドから転送されてきたレコードの、データ処理部１０４による処理）が行われる（ステップＳ３０５）。このバッファ処理が完了すると、ステップＳ３０１へ戻る。
【００６０】
ステップＳ３０７では、終了条件判断部１０９が、上記終了条件が成り立つか否かを判定する。上記終了条件が満たされなければ、バッファ処理が行われると（ステップＳ３０８）、ステップＳ３０７へ戻る。すなわち、上述の終了条件が成り立つまで、バッファ処理Ｓ３０５（自スレッドが、自スレッドに対応したバッファ内のレコードを処理すること）が繰り返し呼び出される。このように、上述の終了条件が成り立つまで、バッファ処理が繰り返し呼び出されるのは、他スレッドの全てにおける処理が完了するまで、自スレッド宛のレコードが他スレッドからバッファに転送される可能性があるためである。
【００６１】
ステップＳ３０７において、上記終了条件が成り立つと判定されると、自スレッドにおける処理が完了する。なお、スレッド間通信プログラム全体としては、全てのスレッドにおいて上記終了条件が成立（ステップＳ３０７：Yes）した時点で、スレッド間通信プログラムにおける処理終了となる。
【００６２】
（５）バッファのレコードの格納処理
図５は、他スレッド（例えば、スレッドＴ１）が、担当スレッド（例えば、スレッドＴ０）のバッファにレコードを格納するための処理を示すフローチャートである。図５に示される通り、他スレッドであるスレッドＴｎからレコードの格納要求を受けると、スレッドＴｍのバッファ管理部１０６は、バッファＢｍ−ｎに空きがあるか否かを判断する（Ｓ４０１）。ここでバッファＢｍ−ｎとは、スレッドＴｍにおけるバッファであって、スレッドＴｎから送信されたレコードを格納するためのバッファであることを示している。
【００６３】
ここで、バッファ管理部１０６により空きがあると判断されると、スレッドＴｎは、バッファＢｍ−ｎの格納先ポインタ変数が指す場所にレコードを格納する（Ｓ４０２）。そして、バッファ管理部１０６は、バッファＢｍ−ｎの格納先ポインタ変数が指す場所を次へ移動する（Ｓ４０３）。
【００６４】
一方、バッファ管理部１０６により、バッファＢｍ−ｎに空きがないと判断されると、さらにバッファ管理部１０６により、リンクリストが併用されているか否かが判断される（Ｓ４０４）。ここで、併用されていないと判断されると、バッファＢｍ−ｎに空きができるまで、バッファ管理部１０６は待機する。そして、バッファ管理部１０６がバッファＢｍ−ｎに空きができたと判断すると、スレッドＴｎは、バッファ管理部１０６を介して、バッファＢｍ−ｎにレコードを格納する（Ｓ４０６）。
【００６５】
また、リンクリストを併用していると判断されると（Ｓ４０４）、リンクリストを利用したパイプ処理が行われる（Ｓ４０５）。このパイプ処理については後述する。
【００６６】
ここで、バッファＢｍ−ｎへのレコード格納について詳細に説明する。図６は、バッファＢｍ−ｎのレコードスペースとその取得先ポインタ変数および格納先ポインタ変数とを説明するための説明図であり、図６（ａ）は、その初期状態を示し、図６（ｂ）は、レコード格納時を示す。
【００６７】
図６（ａ）に示される通り、バッファＢｍ−ｎは、複数のレコードスペースを形成しており、論理的にリング状のレコードスペースが形成されている。ここでは、格納先ポインタ変数５０１は格納先のレコードスペースを示し、取得先ポインタ変数５０２は取得先のレコードスペースを示す。バッファ管理部１０６は、初期設定として、取得先ポインタ変数および格納先ポインタ変数を、あらかじめ定めたレコードスペースを示すように設定する。
【００６８】
一方、図６（ｂ）は、レコード格納時の様子を示しており、バッファ管理部１０６は、格納先ポインタ変数５０１が指す場所の次の場所が、取得先ポインタ変数が指す場所ではないことを確認し（Ｓ５１１）、その後、格納先ポインタ変数が指す場所にレコードを格納する（Ｓ５１２）。格納後、バッファ管理部１０６は、格納先ポインタ変数を次の場所へ更新する（Ｓ５１３）。
【００６９】
図７は、担当スレッド（例えば、スレッドＴ０）が、そのバッファに格納されているレコードの処理を示すフローチャートである。まず、担当スレッドＴｍの実行制御部１０１は、自スレッドが管理するバッファについて未処理のものがあるか否かを判断する（Ｓ６０１）。ここで、未処理のものがあると判断されると、実行制御部１０１は、バッファＢｍ−ｎに未処理のレコードがあるか否かを判断する（Ｓ６０２）。
【００７０】
実行制御部１０１は、バッファＢｍ−ｎに未処理のレコードがあると判断すると、データ処理部１０４は、バッファＢｍ−ｎの取得先ポインタ変数が指す場所の次の場所に格納されているレコードを処理する（Ｓ６０３）。処理後、バッファ管理部１０６は、バッファＢｍ−ｎの取得先ポインタ変数が指す場所を次へ移動する（Ｓ６０４）。このように、Ｓ６０１〜Ｓ６０４の処理を、すべてのバッファに対して行う。
【００７１】
また、Ｓ６０１において、バッファＢｍ−ｎに未処理のバッファがないと判断されると、実行制御部１０１は、リンクリストを併用したものか否かを判断する（Ｓ６０５）。ここで、併用なしと判断されると、処理は終了する。リンクリストの併用ありと判断されると、パイプ処理が行われる（Ｓ６０６）。
【００７２】
ここで、バッファＢｍ−ｎからのレコードの取得処理について詳細に説明する。図８は、バッファＢｍ−ｎのレコードスペースとその取得先ポインタ変数および格納先ポインタ変数とを説明するための説明図であり、図８（ａ）は、レコード格納状態を示し、図８（ｂ）は、レコード取得処理を示す。
【００７３】
図８（ａ）において、格納先ポインタ変数７０１および取得先ポインタ変数７０２のそれぞれにおいて、格納先のレコードスペースおよび取得先のレコードスペースを特定可能にしている。すなわち、図８（ａ）に示されている通り、格納先ポインタ変数７０１が指す場所の次の場所にレコード７０２ａが格納されており、格納先ポインタ変数７０１は、格納先を指す場所であるレコードスペースを指している。
【００７４】
また、図８（ｂ）では、実行制御部１０１は、取得先ポインタ変数が指す場所の次の場所が、格納先ポインタ変数が指す場所でないことを確認する（Ｓ７１１）。そして、実行制御部１０１は、取得先ポインタ変数が指す場所の次の場所のレコードを取得する（Ｓ７１２）。そして、バッファ管理部１０６は、取得先ポインタ変数を次の場所へ更新する（Ｓ７１３）。
【００７５】
なお、上述図７のフローチャートでは、すべてのバッファに対する処理が終了した後に、すべてのリンクリストにおけるパイプ処理を行う処理を示したが、これに限るものではない。例えば、一のバッファに対する処理が終了した後に、その一のバッファに対応するリンクリストにおけるパイプ処理を行うようにしてもよい。図９は、その変形例におけるフローチャートである。図９に示される通り、実行制御部１０１により、未処理のバッファがあると判断されると（Ｓ６０１ａ）、バッファＢｍ−ｎにおける未処理のレコードの有無が判断される（Ｓ６０２ａ）。ここで、未処理のレコードがないと判断され、リンクリストの併用処理が設定されている場合には、このバッファＢｍ−ｎに対応するリンクリストにおけるパイプ処理が実行される（Ｓ６０６）。このようにして、バッファごとに、バッファ処理を行うとともに、そのバッファに対応するパイプ処理を行うようにすることもできる。
【００７６】
（６）プールからのノードの取り出しと、取り出したノードのパイプへの追加の様子
つぎに、図５のＳ４０５におけるパイプ処理について説明する。このパイプ処理は、リンクリストを用いた時のプールにある使用済みノードを取り出し、そのノードにレコードを格納する処理である。
【００７７】
引き続き、図２に示される、担当スレッドＴ０によるレコード受信処理において行われる、プールＱ０−１から、再利用するノードである再利用ノード８１１を取り出して、取り出した再利用ノード８１１に受信レコードを格納してパイプＰ０−１へ追加する様子の詳細について、図１０を用いて説明する。図１０は、プールｍ−ｎ８２０からの再利用ノード８１１の取り出しと、取り出した再利用ノード８１１のパイプｍ−ｎ８２１への追加の様子の詳細を説明するための説明図である。
【００７８】
なお、ここでも、レコードの受け取り側をスレッドｍとし、レコードの渡し側をスレッドｎとする（すなわち、レコードがスレッドｎからスレッドｍへ受け渡される）。また、ここでは、スレッドｎが有するレコード転送部１０５と、スレッドｍが有するパイプ管理部１０７及びプール管理部１０８が協調して動作することになるが、これらは全てスレッドｎによって制御（操作）される。更に、この時使用されるパイプ及びプールは、それぞれパイプｍ−ｎ及びプールｍ−ｎであるとして、説明する。
【００７９】
ここに示される例では、パイプｍ−ｎ８２０及びプールｍ−ｎ８２１内が「物理的に空」（すなわち、ノードがゼロ個の状態）にならないよう、常に一個のダミーノードが存在する。パイプｍ−ｎ８２０及びプールｍ−ｎ８２１といったリンクリスト内のノード総数が最低限である一個の場合、ダミーノードは先頭ノード（同時に末尾ノード）であり（「物理的に空」ではないが「論理的に空」の状態）、当該リンクリスト内のノード総数が二個以上の場合、ダミーノードはこれらのノードにおける先頭に配置されている（「物理的に空」でもなく「論理的に空」でもない状態）。また、パイプｍ−ｎ８２０内が「論理的に空」とは、（ダミーノードのみ存在するが、）取り出すべきレコードを格納したノードが無い状態を意味する。なお、当該ダミーノードのポインタ変数には無効値が設定されている。また、プールｍ−ｎ８２１内が「論理的に空」とは、（上記のダミーノードのみ存在するが、）再利用可能なノードが無い状態を意味する。同様に、当該ダミーノードのポインタ変数には無効値が設定されている。
【００８０】
プールｍ−ｎ８２０では、例えば先頭ノードへの場所を指すポインタ情報を格納したポインタ変数８１３が用いられている。これにより、プールｍ−ｎ８２０から先頭ノードを取り出すスレッドが、先頭ノードを容易に特定することができる。この例では最初に、先頭ノードへのポインタ変数８１３は、先頭ノード８１１を指している。また、先頭ノード８１１のポインタ変数（後続のノードの場所を指す）は、ノード８１２を指している。更に、ノード８１２のポインタ変数（後続のノードの場所を指す）には、無効値が格納されている。
【００８１】
プールｍ−ｎ８２０内にダミーノードしか存在しない空状態であるかどうかは、上記の取り出しスレッドが、例えば先頭ノード８１１のポインタ変数が無効値であるか否かに基づいて、判定する。ここでは、先頭ノード８１１のポインタ変数は無効値でないため、上述の空状態ではない。
【００８２】
ここで、スレッドｎのレコード転送部１０５は、ステップＳ８０１にて、プールｍ−ｎ８２０の先頭ノード８１１を取り出しつつ、ステップＳ８０２にて、先頭ノードへのポインタ変数８１３が、ノード８１１の後続であるノード８１２を指すように設定する。先頭ノードとなったノード８１２のポインタ変数（後続のノードの場所を指す）には、無効値が格納されているため、プールｍ−ｎ８２０は空状態になる。
【００８３】
次に、スレッドｎのレコード転送部１０５は、ステップＳ８０３にて、ノード８１１のレコードスペースに、担当スレッドＴ０に渡すべきレコードを設定しつつ（設定後に「レコードスペース」から「レコード」となる）、ノード８１１のポインタ変数（後続のノードの場所を指す）に無効値を設定する。
【００８４】
また、パイプｍ−ｎ８２１では、例えば末尾ノードへの場所を指すポインタ情報を格納したポインタ変数８１５が用いられている。これにより、パイプｍ−ｎ８２１の末尾にノードを追加するスレッドが、末尾ノードを容易に特定することができる。この例では最初に、末尾ノードへのポインタ変数８１５は、末尾ノード８１４を指している。また、末尾ノード８１４のポインタ変数（後続のノードの場所を指す）には、無効値が格納されている。このため、パイプｍ−ｎ８２１は空状態になっている。
【００８５】
ここで、スレッドｎのレコード転送部１０５は、ステップＳ８０４にて、パイプｍ−ｎ８２１の末尾にノード８１１を追加する処理を行う。これは、ノード８１４のポインタ変数（後続のノードの場所を指す）に、ノード８１１のポインタ情報を設定することで実現される。更に、ステップＳ８０５にて、末尾ノードへのポインタ変数８１５のポインタ情報にも、ノード８１１のポインタ情報が設定される。
【００８６】
このように、担当スレッドＴ０向けにレコードが渡される際に、プールｍ−ｎ８２０から使用済みノード８１１が取り出され、取り出されたノード８１１に当該レコードが格納されて、当該ノード８１１がパイプｍ−ｎ８２１の末尾へ追加される（使用済みノードの再利用）。
【００８７】
（７）プールからのノードの取り出しと、取り出したノードのパイプへの追加の際の処理の流れ
引き続き、図１０に示される処理の流れについて、図１１を用いて説明する。図１１は、図１０に示される処理の流れを説明するためのフローチャートである。
【００８８】
図１１に示されるように、まず、スレッドｍのプール管理部１０８が、スレッドｎのレコード転送部によるスレッドｍのパイプ管理部１０７へのレコードの転送を検知すると、プールｍ−ｎ８２０の先頭ノード８１１のポインタ変数が無効値であるか否かを判定することによって、プール管理部１０８が、プールｍ−ｎ８２０に利用可能な空きノード（再利用可能なノード）があるかどうかを判断する（ステップＳ９０１）。プールｍ−ｎ８２０の先頭ノード８１１のポインタ変数が無効値でないことから、プールｍ−ｎ８２０に利用可能な空きノードがあると判定された場合、プール管理部１０８が、プールｍ−ｎ８２０の先頭ノード８１１を取り出し（ステップＳ９０２）、ステップＳ９０４に移行する。一方、プールｍ−ｎ８２０の先頭ノード８１１のポインタ変数が無効値であることから、プールｍ−ｎに利用可能な空きノードが無いと判定された場合、新規のノードを生成する（ステップＳ９０３）。そして、ステップＳ９０４に移行する。
【００８９】
ステップＳ９０４では、プール管理部１０８が、取り出したノード８１１（又は生成した新規のノード）に対して、担当スレッドＴ０が受信することになる受け渡すべきレコードに関する情報を設定し、且つ、当該ノードのポインタ変数（後続のノードの場所を指す）に無効値を設定する（受信取出ステップ）。そして、プール管理部１０８が、当該ノードを、パイプｍ−ｎ８２１の末尾に追加する処理を行う（ステップＳ９０５）。そして、一連の処理は終了する。
【００９０】
（８）パイプからのノードの取り出しと、取り出したノードのプールへの戻し方の様子
引き続き、図２に示される、担当スレッドＴ０によるレコード受信処理において行われる、パイプＰ０−１からノード１０１１を取り出して、取り出したノード１０１１からレコードを取り出した後、当該使用済みノード１０１１をプールＱ０−１へ追加する様子の詳細について、図１２を用いて説明する。図１２は、パイプｍ−ｎ１０２０からのノード１０１１の取り出しと、取り出したノード１０１１のプールｍ−ｎ１０２１への追加の様子の詳細を説明するための説明図である。
【００９１】
なお、ここでは、レコードの受け取り側をスレッドｍとし、レコードの渡し側をスレッドｎとする（すなわち、スレッドｎから渡されたレコードをスレッドｍが取り出す）。また、この時使用されるパイプ及びプールは、それぞれパイプｍ−ｎ及びプールｍ−ｎであって、これらは全てスレッドｍによって制御（操作）される。
【００９２】
パイプｍ−ｎ１０２０では、例えば先頭ノードへのポインタ情報を格納したポインタ変数１０１３が用いられている。これにより、パイプｍ−ｎ１０２０の先頭から先頭ノードを取り出すスレッドが、先頭ノードを容易に特定することができる。この例では最初に、先頭ノードへのポインタ変数１０１３は、先頭ノード１０１１を指している。また、先頭ノード１０１１のポインタ変数（後続のノードの場所を指す）は、ノード１０１２を指している。更に、ノード１０１２のポインタ変数（後続のノードの場所を指す）には、無効値が格納されている。
【００９３】
パイプｍ−ｎ１０２０内にダミーノードしか存在しない空状態であるかどうかは、スレッドが、例えば先頭ノード１０１１のポインタ変数が無効値であるか否かに基づいて、判定する。ここでは、最初に、先頭ノード１０１１のポインタ変数は無効値でないため、上述の空状態ではない。
【００９４】
ここで、スレッドｍのパイプ管理部１０７は、ステップＳ７０１にて、パイプｍ−ｎ１０２０の先頭ノード１０１１のポインタ情報が指し示すノード１０１２のレコードを用いた処理を行いつつ（なお、当該処理の後、ノード１０１２の「レコード」は消去されて「レコードスペース」となる）、先頭ノードへのポインタ変数１０１３が、当該ノード１０１２を指すように設定する。先頭ノードとなったノード１０１２のポインタ変数（後続のノードの場所を指す）には、無効値が格納されているため、パイプｍ−ｎ１０２０は空状態になる。
【００９５】
次に、スレッドｍのパイプ管理部１０７は、ステップＳ１００２にて、元々は先頭ノードだったノード１０１１を取り出し、ステップＳ１００３にて、使用済みノード１０１１のポインタ変数（後続のノードの場所を指す）に無効値を設定する。
【００９６】
また、プールｍ−ｎ１０２１では、例えば末尾ノードへの場所を指すポインタ情報を格納したポインタ変数１０１５が用いられている。これにより、プールｍ−ｎ１０２１の末尾にノードを追加するスレッドが、末尾ノードを容易に特定することができる。この例では最初に、末尾ノードへのポインタ変数１０１５は、末尾ノード１０１４を指している。また、末尾ノード１０１４のポインタ変数（後続のノードの場所を指す）には、無効値が格納されている。このため、プールｍ−ｎ１０２１は空状態になっている。
【００９７】
ここで、スレッドｍのプール管理部１０８は、ステップＳ１００４にて、プールｍ−ｎ１０２１の末尾に使用済みノード１０１１を追加する処理を行う。これは、ノード１０１４のポインタ変数（後続のノードの場所を指す）に、使用済みノード１０１１のポインタ情報を設定することで実現される。更に、ステップＳ１００５にて、末尾ノードへのポインタ変数１０１５のポインタ情報にも、使用済みノード１０１１のポインタ情報を設定する。
【００９８】
このように、担当スレッドＴ０がノード１０１２からレコードを受け取る際に、パイプｍ−ｎ１０２０から使用済みノード１０１１が取り出され、取り出された使用済みノード１０１１がプールｍ−ｎ１０２１の末尾へ追加される。
【００９９】
ここで、図１０と図１２との比較により示されるように、「ノードを取り出す側のスレッドの役割」と「ノードを追加する側のスレッドの役割」とが、正反対になっている。
【０１００】
（９）パイプからのノードの取り出しと、取り出したノードのプールへの戻しの際の処理の流れ
引き続き、図１２に示される処理の流れについて、図１３を用いて説明する。図１３は、図１２に示される処理の流れを説明するためのフローチャートである。
【０１０１】
図１３に示されるように、まず、スレッドｍの実行制御部１０１が、自スレッドｍが管理するパイプ／プールｍ−ｎの組において未処理のノードがあるかどうかを判断する（ステップＳ１１０１）。未処理のノードが無い場合、一連の処理は終了する。一方、未処理のノードがある場合、スレッドｍの実行制御部１０１が、パイプｍ−ｎの先頭ノードのポインタ変数が無効値であるか否かを判断する（ステップＳ１１０２）。ポインタ変数が無効値である場合、当該パイプｍ−ｎには処理すべきノードが設定されていないため、次の（すなわち、その他の）パイプ／プールｍ−ｎの処理へ進むため、ステップＳ１１０１に戻る。一方、ポインタ変数が無効値でない場合（すなわち、未定義でない場合）、スレッドｍの実行制御部１０１が、先頭ノードのポインタ変数が指し示すノードに設定されているレコードを処理する（ステップＳ１１０３）。
【０１０２】
次に、スレッドｍが、パイプｍ−ｎの先頭ノードを取り出し（ステップＳ１１０４）、取り出した先頭ノードのポインタ変数に無効値を設定して（ステップＳ１１０５）、この先頭ノードをプールｍ−ｎの末尾に使用済みノードとして追加する（ステップＳ１１０６）。そして、ステップＳ１１０２に戻る。
【０１０３】
なお、上述の変形例（図９）におけるパイプ処理は、スレッドごとにパイプ処理を行うことになるため、図１３においては、Ｓ１１０１における未処理のノードを判断することなく、ノードの無効値の判断処理から始めるようにしてもよい。
【０１０４】
（１０）コンピュータをスレッド間通信システムとして機能させるためのスレッド間通信プログラム
引き続き、コンピュータをスレッド間通信システムとして機能させるためのスレッド間通信プログラムＰ１０について説明する。図１４は、スレッド間通信プログラムＰ１０のモジュール構成を示すブロック図である。図１４に示すように、スレッド間通信プログラムＰ１０は、実行制御モジュール１１、担当スレッド判断モジュール１２、データ入力部モジュール１３、データ処理モジュール１４、レコード転送モジュール１５、バッファ管理モジュール１６、パイプ管理モジュール１７、プール管理モジュール１８、及び終了条件判断モジュール１９を備える。
【０１０５】
これらモジュール１１〜１９が実行されることにより実現される機能は、上述したスレッド間通信システム１０において対応する実行制御部１０１（レコード判断手段）、担当スレッド判断部１０２、データ入力部１０３、データ処理部１０４、レコード転送部１０５、バッファ管理部１０６（バッファ判断手段、第１の変更手段、第２の変更手段、実行手段）、パイプ管理部１０７（ノード追加手段、ノード判断手段、レコード取出手段）、プール管理部１０８（ノード取出手段、追加手段）、及び終了条件判断部１０９の機能と同様である。
【０１０６】
（１１）本発明による作用及び効果
本実施形態のスレッド間通信システム１０においては、各スレッドＴ０〜Ｔ１には、他のスレッドの数に相当する数だけバッファＢ０−１〜Ｂ２−１（リングバッファ）が用意されており、各バッファＢ０−１〜Ｂ２−１は、互いに異なる他のスレッドの一つと対応付けられている。例えば、バッファＢ０−１は、スレッドＴ１からのレコードを格納するように対応付されている。そして、バッファＢ０−１〜Ｂ２−１は、次のレコードを格納する場所を指す格納先ポインタ変数と、次のレコードを取り出す場所を指す取得先ポインタ変数とを有している。そして、このスレッド間通信システム１０の起動に先立って、各バッファＢ０−１〜Ｂ２−１における取得先ポインタ変数の指す所定の場所が初期値として決定されるとともに、前記取得先ポインタ変数の指す場所の次の場所が、前記格納先ポインタ変数が指す場所の初期値として決定される。バッファ管理部１０６がこのような初期設定処理を実行する。
【０１０７】
そして、例えば送信スレッド（例えば、スレッドＴ１）のデータ入力部において、他のスレッド（例えばスレッドＴ０）が処理を担当する一のレコードが入力されると、当該他のスレッドのバッファＢ０−１における、格納先ポインタ変数が指す場所の次の場所が、取得先ポインタ変数が指す場所ではない場合は、バッファ管理部１０６は、他のスレッドのバッファに空きがあると判断する。そして、スレッドＴ１は、バッファ管理部１０６を介して、格納先ポインタ変数が指す場所に一のレコードを格納するとともに、バッファ管理部１０６は、格納先ポインタ変数が指す場所を次の場所に変更する。これにより、各スレッドＴ０〜Ｔ２には、他のスレッドの数に相当する数だけのバッファＢ０−１〜Ｂ２−１が用意された上で、スレッドＴ１によるバッファＢ０−１へのレコードの格納を可能にする。したがって、実行制御部１０１が、このバッファＢ０−１からのレコードからの取り出しをしようとした場合、ＣＡＳ操作を利用せずに、矛盾なく情報の受け渡しをすることが可能になる、という効果を奏する。さらに、バッファのサイズを十分大きくすることで、バッファに空きがない状況が起きないようにすることで、実質的にウェイトフリー性を確保することができる。
【０１０８】
また、本実施形態において用いたバッファはリングバッファであり、レコードを格納するレコードスペースの数が固定であるため、レコードスペースを新規生成したり、レコードスペース同士を接続または切断するなどの処理が不要となる。よって、送受信リンクリストや保管リンクリストを用いる場合よりも、その分だけオーバヘッドを削減することができ、高速に動作することが可能となる。
【０１０９】
なお、本実施形態においては、各スレッドに、各他のスレッド専用のバッファ（およびオプション機能を備える場合には、パイプおよびプール）を用意することが特徴である。これにより、各バッファ（パイプおよびプール）において、レコード（またはレコードを格納したノード）を格納する送信スレッド及び取り出す取出スレッドは必ずただ一つとなる。すなわち、レコード（またはノード）の格納におけるスレッド間競合、およびレコード（またはノード）の取り出しにおけるスレッド間競合は発生しない。唯一発生するのは、送信スレッドと取出スレッドとの２スレッド間における競合のみとなる。
【０１１０】
さらに、このスレッド間通信システム１０において、スレッドＴ１が、バッファ管理部１０６を介して、バッファＢ０−１にレコードを格納しようとして、そのバッファＢ−０１に空きがないと判断されると、バッファ管理部１０６は、そのバッファＢ０−１に空きができるまで所定時間待機して、空きができると、バッファＢ０−１への一のレコードの格納処理を実行することで、バッファＢ０−１への格納処理を確実に行うことができる。
【０１１１】
また、このスレッド間通信システム１０において、スレッドＴ０のバッファ管理部１０６により管理されているバッファＢ０−１において、取得先ポインタ変数が指す場所の次の場所が、格納先ポインタ変数が指す場所ではない場合は、実行制御部１０１は、バッファＢ０−１に処理すべき一のレコードがあると判断する。また、実行制御部１０１は、取得先ポインタ変数が指す次の場所が、格納先ポインタ変数が指す場所である場合は、バッファＢ０−１に処理すべき一のレコードはないと判断する。そして、処理すべき一のレコードがあると判断されると、実行制御部１０１は、取得先ポインタ変数が指す場所の次の場所から当該処理すべき一のレコードをバッファＢ０−１から取り出してから、取得先ポインタ変数が指す場所を次の場所に変更する。これにより、送信スレッド（例えば、スレッドＴ１）によるバッファＢ０−１に対する格納処理と、取出スレッド（例えば、スレッドＴ０）によるバッファＢ０−１からの取出処理とを行う際に、ＣＡＳ操作を利用せずに、矛盾なく情報の受け渡しをすることが可能になる、という効果を奏する。
【０１１２】
さらに、本実施形態のスレッド間通信システム１０は、図２に示されるように、各スレッド（例えば、スレッドＴ０〜Ｔ２）には、他のスレッドの数に相当する数だけパイプ（パイプＰ０−１〜Ｐ２−１）が用意されており、各パイプは、互いに異なる他のスレッドの一つと対応付けられ、当該対応付けられたスレッドから送信されたレコードを格納順を指定してノードに格納することが可能である。そして、このスレッド間通信システム１０によれば、図１０に示されるように、レコードの送信元である送信スレッド（例えば、スレッドＴ１）が、当該レコードを格納した新規ノード８１１を生成して、当該レコードの送信先である受信スレッド（例えば、スレッドＴ０）と対応するパイプｍ−ｎ８２１に追加する場合に、当該新規ノード８１１のポインタ変数に無効値を設定しつつ当該新規ノード８１１を当該パイプｍ−ｎ８２１の末尾に追加して格納する。次に、図１２に示されるように、取出スレッド（例えば、スレッドＴ０）が、当該レコード１０１１を、対応するパイプｍ−ｎ１０２０から取り出す場合に、当該パイプｍ−ｎ１０２０の先頭ノード１０１１のポインタ変数が無効値であるか否かを判定する。そして、当該ポインタ変数は無効値でないと判定された場合に、取出スレッド（例えば、スレッドＴ０）が、当該ポインタ変数が指す場所のノード１０１２からレコードを取り出しつつ当該ノード１０１２を新たな先頭ノードとして設定する。一方、当該ポインタ変数は無効値であると判定された場合に、取出スレッド（例えば、スレッドＴ０）が、対応するパイプｍ−ｎ１０２０から取り出し可能なレコードを格納するノードは無い状態であると判断する。
【０１１３】
これにより、各スレッドには他のスレッドの数に相当する数だけパイプが用意されており、送信スレッド（例えばスレッドＴ１）が新規ノード８１１を生成して送信先のパイプｍ−ｎ８２１の末尾に追加して格納する。また、取出スレッドが、先頭ノード１０１１のポインタ変数が無効値でない場合に当該ポインタ変数が指す場所のノード１０１２からレコードを取り出す。一方、当該ポインタ変数は無効値である場合に、取り出し可能なレコードは無い状態であると判断される。このように、各スレッドには他のスレッドの数に相当する数だけパイプが用意された上で、送信スレッド（例えば、スレッドＴ１）によるパイプへのノードの格納と、取出スレッド（例えば、スレッドＴ０）によるパイプからのレコードの取り出しとが行われるため、ＣＡＳ操作を利用せずに、矛盾なく情報の受け渡しをすることが可能になり且つウェイトフリーになる。
【０１１４】
すなわち、リングバッファのみを用いる場合、レコードを格納するレコードスペースの数を固定であるため、送受信リンクリスト等と異なり、理論的にウェイトフリー（無待機）性を保証できない。そこで、本実施形態では、スレッド間でレコードの受け渡しをするために用いる第二次のデータ構造として送受信リンクリストを併用してもよい。すなわち、バッファに空きがない場合に限り、送受信リンクリストに、レコードを格納したノードを追加する構成をとってもよい。このような送受信リンクリストを併用することで、バッファにより高速性と、送受信リンクリストによる論理的なウェイトフリー（無待機）性の両方を享受できる。
【０１１５】
また、各スレッド（スレッドＴ０〜Ｔ２）には、他のスレッドの数に相当する数だけプールが用意されており、各プール（プールＰ０−１〜Ｐ２−１）は、互いに異なる他のスレッドの一つと対応付けられ、レコードが取り出された使用済みノードを格納することが可能である。そして、この形態によれば、図１２に示されるように、取出スレッド（例えばスレッドＴ０）が、レコードが取り出された使用済みノード１０１１のポインタ変数に無効値を設定しつつ（ステップＳ１００３）、当該使用済みノード１０１１をプールｍ−ｎ１０２１の末尾に追加して格納する。次に、図１０に示されるように、レコードの送信元である送信スレッド（例えば、スレッドＴ１）が、当該レコードの送信先である受信スレッド（例えば、スレッドＴ０）と対応するプールｍ−ｎ８２０の先頭ノード８１１のポインタ変数が無効値であるか否かを判定する。そして、当該先頭ノード８１１のポインタ変数は無効値でないと判定された場合に、送信スレッド（例えば、スレッドＴ１）が、当該先頭ノード８１１を新規ノードとして再利用しつつ当該再利用するノード８１１のポインタ変数が指す場所のノード８１２を新たな先頭ノードとして設定する。一方、当該ポインタ変数は無効値であると判定された場合に、送信スレッド（例えば、スレッドＴ１）が、新規ノードを生成する。このように、使用済みノード１０１１をプールｍ−ｎ１０２１の末尾に追加・格納してノードを再利用することにより、新たなノードの生成を抑制して処理を効率化することが可能になる。
【０１１６】
また、本発明は、ＣＡＳ操作を用いないため、ＣＡＳ操作が利用できない環境（計算機および／またはプログラミング言語）においても、適用することができる。
【０１１７】
（１２）本実施形態の応用事例
本実施形態は、複数スレッドを用いる処理において、処理すべき各レコードの担当スレッドを所定の方法で決定できるような処理全般に対して、適用できる。典型的な具体例として、ハッシュテーブルの構築がある。図４に示されるように、ハッシュテーブルの要素となるキー／値のペアにおいて、例えばキーのハッシュ値のスレッド数によるｍｏｄｕｌｏを取得することで、担当スレッドを一意に決定することが可能になる。各スレッドは、自スレッドに対応するｍｏｄｕｌｏ値を持つレコードのみを集めてハッシュテーブルを構築すればよい。すなわち、スレッド数分だけ分割されたハッシュテーブルが、構築されることになる。
【０１１８】
ハッシュテーブルを構築した後に要素（レコード）を検索する際は、検索キーのハッシュ値のスレッド数（図４に示されるでは、「３」）によるｍｏｄｕｌｏから、まずは該当するハッシュテーブルを特定し（ハッシュテーブル０，１，２のいずれか）、次に、当該特定されたハッシュテーブルから通常の方法で検索を行えばよい。
【０１１９】
このようなハッシュテーブルに関する応用だけでも、様々な利用形態がある。例えば、「多数のキー／値の組からなる辞書テーブルを構築する」、「多数の値をそのままキーとして用い、ハッシュテーブル上でキーが衝突した回数から、各値の出現回数をカウントする」、「多数のキー／値の組から、同じキーを持つ値の集合を生成する」等が考えられる。このような応用事例に対して本発明を適用することで、処理をウェイトフリーな形態で並列化でき、処理を高速化できる。
【符号の説明】
【０１２０】
１０…スレッド間通信システム、１０１…実行制御部、１０２…担当スレッド判断部、１０３…データ入力部、１０４…データ処理部、１０５…レコード転送部、１０６…バッファ管理部、１０７…パイプ管理部、１０８…プール管理部、１０９…終了条件判断部。
【図１】
2015005123.tif 000003
【図２】
2015005123.tif 000004
【図３】
2015005123.tif 000005
【図４】
2015005123.tif 000006
【図５】
2015005123.tif 000007
【図６】
2015005123.tif 000008
【図７】
2015005123.tif 000009
【図８】
2015005123.tif 000010
【図９】
2015005123.tif 000011
【図１０】
2015005123.tif 000012
【図１１】
2015005123.tif 000013
【図１２】
2015005123.tif 000014
【図１３】
2015005123.tif 000015
【図１４】
2015005123.tif 000016