(57)【要約】  本発明は、共有ＦＩＦＯバッファからデータ要素を読み出し、共有ＦＩＦＯバッファへデータ要素を書き込む方法および装置に関し、ここで、データ要素、又は、データ要素用の記憶空間がＦＩＦＯバッファ内で利用可能であることの信号伝達、即ち、Ｖ−オペレーションを実行することは、データ要素、又は、データ要素用の記憶空間が前記ＦＩＦＯバッファで利用可能になると直ぐに最小単位で実行されることはなく、Ｌ個のデータ要素、又は、Ｌ個のデータ要素用のＬ個の記憶空間の利用可能性の１回の信号伝達を実行する前に、Ｌ個のデータ要素、又は、Ｌ個のデータ要素用のＬ個の記憶空間が前記ＦＩＦＯバッファで利用可能になるまで待機させられる。ある意味で、データ要素、又は、データ要素用の記憶空間の利用可能性の信号伝達、即ち、Ｖ−オペレーションを実行することは、利用可能性の信号を出力する前に、ある程度の量のＶオペレーションが集められるまで一時的に蓄えられる。
2005509943.tif 000002
【特許請求の範囲】
【請求項１】
セマフォオペレーションに基づいて共有ＦＩＦＯバッファへデータ要素を書き込む方法であって、
データ要素を記憶するための記憶空間（余地）が前記ＦＩＦＯバッファ内で利用可能であるかどうかを判定するステップ（ａ）と、
ステップ（ａ）において前記ＦＩＦＯバッファ内に利用可能な記憶空間（余地）が存在しないと判定された場合に、前記ＦＩＦＯバッファの入力を阻止するステップ（ｂ）と、
ステップ（ａ）において記憶空間（余地）が前記ＦＩＦＯバッファ内で利用可能であると判定された場合に、データ要素を前記ＦＩＦＯバッファへ入力するステップ（ｃ）と、
データ要素がステップ（ｃ）で入力されたとき、前記ＦＩＦＯバッファへ入力されたデータ要素の個数を示す書き込みカウンタのカウントをインクリメントするステップ（ｄ）と、
前記書き込みカウンタの前記カウントがＬだけインクリメントしたとき、第１のシグナリングオペレーションを実行するステップ（ｅ）とを有する、方法。
【請求項２】
ステップ（ｅ）における前記第１のシグナリングオペレーションは、ステップ（ｃ）において前記ＦＩＦＯバッファに入力されたＬ個のデータ要素が前記ＦＩＦＯバッファから出力するために利用可能であることを示す、請求項１に記載の方法。
【請求項３】
前記ステップ（ｄ）は、前記書き込みカウンタの前記カウントを所定の開始カウントからインクリメントするステップを含み、
当該方法は、
前記書き込みカウンタの前記カウントが所定の第１の限界Ｌに到達したかどうかを判定するステップ（ｆ）と、
ステップ（ｆ）の後、前記書き込みカウンタの前記カウントを前記所定の開始点にリセットするステップ（ｇ）とをさらに含む、請求項１または２に記載の方法。
【請求項４】
セマフォオペレーションに基づいて共有ＦＩＦＯバッファからデータ要素を読み出す方法であって、
前記ＦＩＦＯバッファから読み出すためのデータ要素が前記ＦＩＦＯバッファ内で利用可能であるかどうかを判定するステップ（ａ）と、
ステップ（ａ）において前記ＦＩＦＯバッファから読み出すために利用可能であるデータ要素が前記ＦＩＦＯバッファ内に存在しないと判定された場合に、前記ＦＩＦＯバッファの出力を阻止するステップ（ｂ）と、
ステップ（ａ）において前記ＦＩＦＯバッファから読み出すためのデータ要素が前記ＦＩＦＯバッファ内で利用可能であると判定された場合に、前記ＦＩＦＯバッファからデータ要素を出力するステップ（ｃ）と、
データ要素がステップ（ｃ）で前記ＦＩＦＯバッファから出力されたとき、前記ＦＩＦＯバッファから出力されたデータ要素の個数を示す読み出しカウンタのカウントをインクリメントするステップ（ｄ）と、
前記読み出しカウンタの前記カウントがＬだけインクリメントしたとき、第２のシグナリングオペレーションを実行するステップ（ｅ）とを有する、方法。
【請求項５】
ステップ（ｅ）における前記第２のシグナリングオペレーションは、Ｌ個のデータ要素を記憶するため前記ＦＩＦＯバッファ内でＬ個の記憶空間（余地）が利用可能であることを示す、請求項４に記載の方法。
【請求項６】
前記ステップ（ｄ）は、前記読み出しカウンタの前記カウントを所定の開始カウントからインクリメントするステップを含み、
当該方法は、
前記読み出しカウンタの前記カウントが所定の第１の限界Ｌに到達したかどうかを判定するステップ（ｆ）と、
ステップ（ｆ）の後、前記読み出しカウンタの前記カウントを前記所定の開始点にリセットするステップ（ｇ）とをさらに含む、請求項４または５に記載の方法。
【請求項７】
前記所定の開始カウントは０である、請求項３または６に記載の方法。
【請求項８】
前記第１の限界Ｌは１よりも大きい整数である、請求項１、２、４または５に記載の方法。
【請求項９】
セマフォオペレーションに基づいて共有ＦＩＦＯバッファへデータ要素を書き込む装置であって、
データ要素を記憶するための記憶空間（余地）が前記ＦＩＦＯバッファ内で利用可能であるかどうかを判定する第１の判定手段と、
前記第１の判定手段が前記ＦＩＦＯバッファ内に利用可能な記憶空間（余地）は存在しないと判定したとき、前記ＦＩＦＯバッファの入力を阻止する入力ブロック手段と、
前記第１の判定手段が前記ＦＩＦＯバッファ内で記憶空間（余地）が利用可能であると判定したとき、データ要素を前記ＦＩＦＯバッファへ入力する入力手段と、
データ要素がステップ（ｃ）で入力されたとき、前記ＦＩＦＯバッファへ入力されたデータ要素の個数を示す書き込みカウントをインクリメントする書き込みカウンタと、
前記書き込みカウンタの前記カウントがＬだけインクリメントしたとき、第１のシグナリングオペレーションを実行する第１のシグナリング手段とを有する、装置。
【請求項１０】
セマフォオペレーションに基づいて共有ＦＩＦＯバッファからデータ要素を読み出す装置であって、
前記ＦＩＦＯバッファから読み出すためのデータ要素が前記ＦＩＦＯバッファ内で利用可能であるかどうかを判定する第３の判定手段と、
前記第３の判定手段が前記ＦＩＦＯバッファから読み出すために利用可能であるデータ要素は前記ＦＩＦＯバッファ内に存在しないと判定したとき、前記ＦＩＦＯバッファの出力を阻止する出力ブロック手段と、
前記第３の判定手段が前記ＦＩＦＯバッファ内でデータ要素は利用可能であると判定したとき、前記ＦＩＦＯバッファからデータ要素を出力する出力手段と、
前記出力手段が前記ＦＩＦＯバッファからデータ要素を出力したとき、前記ＦＩＦＯバッファから出力されたデータ要素の個数を示すカウントをインクリメントする読み出しカウンタと、
前記読み出しカウンタの前記カウントがＬだけインクリメントしたとき、第２のシグナリングオペレーションを実行する第２のシグナリング手段とを有する、装置。
【請求項１１】
請求項９に記載のセマフォオペレーションを使用して共有ＦＩＦＯバッファへデータ要素を書き込む装置、および／または、
請求項１０に記載のセマフォオペレーションを使用して共有ＦＩＦＯバッファからデータ要素を読み出す装置を含む、並列処理用のコンピュータシステム。
【請求項１２】
コンピュータプログラムがコンピュータ上で実行されるとき、請求項１〜８のいずれかに記載された方法のステップをコンピュータに実行させるためのコンピュータプログラムコード手段を含む、コンピュータプログラムプロダクト。
【発明の詳細な説明】
【技術分野】
【０００１】
本発明は、データ要素を共有ＦＩＦＯバッファへ書き込む方法および装置と、データ要素を共有ＦＩＦＯバッファから読み出す方法および装置と、コンピュータシステムと、対応したコンピュータプログラムプロダクトと、に関する。
【背景技術】
【０００２】
コンピュータシステムにおいて、プロセッサの協調は重要な懸案事項である。集中システムでは、セマフォは、相互排除や、再使用可能で消費可能なリソースの管理のような多様なプロセス協調問題を解決するため一般に使用される。
【０００３】
相互排除の問題は並列処理における重要な懸案事項である。多数のプロセスが一つ以上のプロセッサ上で並列的に実行される。プロセッサは、たびたび、記憶装置、入出力装置、および、メモリのようなリソースを共有する。二つ以上のプロセスが同じデータおよびメモリに関して動作する必要があるとき、リソースへの相互排除アクセスを実施するためのメカニズムを提供することが必要になる。このメカニズムは、唯一のプロセスだけが同時にあるソースにアクセスできるようにするために要求される。
【０００４】
たびたび、セマフォは、共有リソースへのアクセスを調停する同期メカニズムとして使用される。セマフォは値が関連付けられ、この値には、一般的に、セマフォによって調節されるリソースの個数が設定される。セマフォがプロセスによって取得される毎に、セマフォの値は１ずつ減少する。セマフォの値が０に達した後、セマフォを取得する新たな試行は、セマフォがプロセッサのうちの一つによって解放され、セマフォの値が１だけインクリメントするまでは阻止される。
【０００５】
セマフォは、ＰオペレーションとＶオペレーションだけが許可される非負整数変数である。Ｖオペレーションは、プロデューサプロセスによって使用され、プロデューサプロセスがコンシューマプロセスによる使用のための情報を生成したことを知らせる。Ｐオペレーションは、コンシューマプロセスがプロデューサプロセスによって生成された情報を要求するときにコンシューマプロセスによって使用される。Ｐオペレーションは相互排除に入るため使用され、Ｖオペレーションは相互排除から出るために使用される。セマフォと、ＰオペレーションおよびＶオペレーションの非常に図形的な説明は米国特許第４，９２８，２２２号に記載されている。
【０００６】
通常、いわゆるプロデューサ・コンシューマ問題は並列処理で生じる。プロデューサ・コンシューマ問題の基本は、データのプロデューサがコンシューマの準備が完了するまで上記データを保存する手段を備えていなければならないこと、並びに、コンシューマがそこに存在しないデータを使おうとしてはならないことである。コンシューマが使用する準備を完了したときに限り、プロデューサがデータを生成することは非現実的であると思われる。これらのプロセスの何れかが先に到着した場合、それは待機させる必要がある。しかし、コンシューマ又はプロデューサのデータレートがプログラムの実行中に変化するならば、或いは、プロデューサ又はコンシューマのデータレートが同じではないならば、データをバッファ処理することが必要になる。バッファはメモリの一区分であり、プロデューサとコンシューマの両方がそのバッファにアクセスする。バッファが十分に大きくデータ生成のピークを取り扱うことができるならば、プロデューサとコンシューマの両方は、時折発生するピークによる誤動作を心配することなく、安定した高い平均レートのデータ転送を維持する。
【０００７】
並列プロセスがプロデューサ・コンシューマのペアでリンクされ、全ての部分が各プロセスからアクセスできる有限バッファを共有するとき、速度の遅いコンシューマはシステム全体をかなり遅らせる。一部のケースでは、コンシューマは妨害され、共同プロデューサにより生成されたメッセージがバッファ全部を占領し、システムを妨害するであろう。このような挙動を回避するため、プロデューサ・コンシューマのペア毎に、正常動作のための適切な数の部分を確保し、様々なペアの生成ピークを吸収するためにバッファの残りを費やすことが知られている。
【０００８】
図３Ａおよび３Ｂは、二つのプロセッサの間でキャッシュされた共有メモリで実施される有界ＦＩＦＯバッファへの書き込みおよび読み出しのための標準的な方法を示し、セマフォは同期のために使用されている。有界ＦＩＦＯバッファからの読み出しおよび書き込みのための上記方法のオペレーションは二つのセマフォに基づくものであり、「データ」セマフォは空のＦＩＦＯバッファからの読み出しを防止するため使用され、「ルーム」セマフォは満杯のバッファへの書き込みを防止するため使用される。「データ」セマフォの値はＦＩＦＯバッファ内の有効データエントリーの個数に対応し、「ルーム」セマフォの値はＦＩＦＯバッファ内の空き位置の個数に対応する。
【０００９】
図３Ａは、「ルーム」セマフォに基づいて上記有界ＦＩＦＯバッファへデータを書き込む方法を示す。ＦＩＦＯバッファ内のスペースに関するＰオペレーション（Ｐ（ｒｏｏｍ））が実行され、即ち、ＦＩＦＯバッファ内のデータ要素のためのスペース又は余地の要求が実行される。ＦＩＦＯバッファ内にて利用可能とされたスペース又は余地が存在しない場合、書き込みプロセスは待機させられる。しかし、ＦＩＦＯバッファに余地があるならば、データ要素はキューに入力され、Ｖオペレーション（Ｖ（ｄａｔａ））、即ち、新しいデータ要素がＦＩＦＯバッファ内にて利用可能であることのシグナリングが実行される。
【００１０】
図３Ｂは「データ」セマフォに基づいて上記有界ＦＩＦＯバッファからデータを読み出す方法を示す。ＦＩＦＯバッファ内のデータ要素に関するＰオペレーション（Ｐ（ｄａｔａ））、即ち、データ要素がＦＩＦＯバッファ内で利用可能であるかどうかの要求が実行される。ＦＩＦＯバッファ内にデータ要素が利用可能でないならば、読み出しプロセスは待機させられる。しかし、ＦＩＦＯバッファ内にデータ要素が存在するならば、データ要素はキューから出力され、Ｖオペレーション（Ｖ（ｄａｔａ））、即ち、新しいスペースがＦＩＦＯバッファ内で利用可能であることのシグナリングが実行される。
【００１１】
特に、コンシューマプロセス、即ち、読み出しプロセスと、プロデューサプロセス、即ち、書き込みプロセスが別々の処理レートに基づいている場合、「ルーム」と「データ」の二つのセマフォは、二つのプロセスキャッシュの間で繰り返し通信され、その結果として、キャッシュコヒーレンストラフィックが増大する。
【発明の開示】
【発明が解決しようとする課題】
【００１２】
したがって、本発明の目的は、特に、書き込みプロセスと読み出しプロセスが異なる速度を有する場合に、キャッシュコヒーレンストラフィックを削減し、処理速度を改善するセマフォオペレーションに基づいて共有ＦＩＦＯバッファへの読み書きを行う方法および対応した装置を提供することである。
【課題を解決するための手段】
【００１３】
この本発明の目的は、請求項１による共有ＦＩＦＯバッファへデータを書き込む方法と、請求項４による共有ＦＩＦＯバッファからデータを読み出す方法と、請求項９による共有ＦＩＦＯバッファへデータを書き込む装置と、請求項１０による共有ＦＩＦＯバッファからデータを読み出す装置と、によって解決される。
【００１４】
本発明は、データ要素、又は、データ要素用の記憶空間が上記ＦＩＦＯバッファ内で利用可能であることのシグナリングを実行するアイデアに基づく。即ち、データ要素、又は、データ要素用の記憶空間が上記ＦＩＦＯバッファで利用可能になると直ぐに最小単位で実行されることはなく、Ｌ個のデータ要素、又は、Ｌ個のデータ要素用のＬ個の記憶空間の利用可能性の１回のシグナリングを実行する前に、Ｌ個のデータ要素、又は、Ｌ個のデータ要素用のＬ個の記憶空間が上記ＦＩＦＯバッファで利用可能になるまで待機させられる、というＶ−オペレーションを実行することに基づいている。ある意味で、データ要素、又は、データ要素用の記憶空間の利用可能性のシグナリング、即ち、Ｖ−オペレーションを実行することは、利用可能性のシグナリングを出力する前に、ある程度の量のＶオペレーションが集められるまで一時的に蓄えられる。
【００１５】
本発明によれば、データ要素が共有ＦＩＦＯバッファへ書き込まれようとするとき、第一に、上記ＦＩＦＯ内でデータ要素を記憶するため記憶空間が利用可能であるかどうかを判定する。上記ＦＩＦＯバッファの入力は、上記ＦＩＦＯバッファ内に利用可能な記憶空間が存在しないとき阻止され、一方、上記ＦＩＦＯバッファ内に利用可能な記憶空間が存在するとき上記ＦＩＦＯバッファへデータ要素が入力される。書き込みカウンタのカウントは、データ要素が上記ＦＩＦＯバッファへ入力されるときインクリメントされ、ここで、上記カウントは、上記ＦＩＦＯバッファへ入力されたデータ要素の個数を表す。このカウントの値がＬに達した後、即ち、Ｌ個のデータ要素が上記ＦＩＦＯバッファへ入力されたとき、第１のシグナリングオペレーションが実行される。
【００１６】
共有ＦＩＦＯバッファからのデータ要素の読み出しは、上記共有ＦＩＦＯバッファへのデータ要素の書き込みと対称的に実行される。最初に、上記ＦＩＦＯバッファから読み出すためにデータ要素が上記ＦＩＦＯバッファ内で利用可能であるかどうかが判定される。上記ＦＩＦＯバッファの出力は、上記ＦＩＦＯバッファ内に利用可能なデータ要素が存在しないとき阻止され、一方、上記ＦＩＦＯバッファ内に利用可能なデータ要素が存在するときデータ要素は上記ＦＩＦＯバッファから出力される。読み出しカウンタのカウントは、データ要素が上記ＦＩＦＯバッファから出力されるときにインクリメントされ、ここで、上記カウントは、上記ＦＩＦＯバッファから出力されたデータ要素の個数を表す。このカウントの値がＬに達した後、即ち、Ｌ個のデータ要素が上記ＦＩＦＯバッファから出力されたとき、第２のシグナリングオペレーションが実行される。
【００１７】
本発明は、読み出しプロセスと書き込みプロセスが異なるプロセッサで実行され、ＦＩＦＯバッファが共有メモリに実現され、共有メモリが両方のプロセッサによってキャッシュされ、キャッシュコヒーレンスプロトコルによって整合性を保たれている状況で問題が生じるという認識に基づいている。読み出しと書き込みの速度が異なる場合、速い方のプロセスは、セマフォカウンタのデクリメントであるＰオペレーション、即ち、データ要素又はデータ要素用の記憶空間の要求によってブロック自体を繰り返し阻止する（セマフォカウンタ＝０）。速い方のプロセスは、遅い方のプロセスが通常のオペレーションを再開する前に遅い方のプロセスから、セマフォカウンタのインクリメントであるＶオペレーション、即ち、データ要素又はデータ要素用の記憶空間の解放によって阻止されるべきではない（セマフォカウンタ＞０）。しかし、この場合、遅い方のプロセスは、通常のオペレーションの他に、Ｖオペレーション、即ち、解放オペレーションの実行を余儀なくされ、これにより、遅い方のプロセスはさらに速度が遅くなる。
【００１８】
この特有の問題は、Ｌ回のＶオペレーションが集められるまでＶオペレーションを一時的に蓄えることにより、そしてＬ個のデータ要素、又は、Ｌ個のデータ要素用のＬ個の記憶空間が共有ＦＩＦＯバッファ内で利用可能であることを示す単一のＶオペレーションを出力することにより、本発明によって解決される。このように、プロセスが通常のオペレーションの他に実行するＶオペレーションは少なくする必要がある。
【００１９】
アプリケーションが、ビデオストリームの画素のように、高レートで共有ＦＩＦＯバッファの読み出しオペレーションおよび書き込みオペレーションを実行するとき、Ｌ回のＶオペレーションが集められるので、画素はＦＩＦＯから直接読み出され、ＦＩＦＯへ直接書き込まれ、もう一方のプロセス（書き込みの場合の読み出し、および、読み出しの場合の書き込み）は、Ｌ個の画素のバースト中の画素を受け取り、又は、「見る」。したがって、もう一方のプロセスのシグナリングレートはＬ分の１である。これにより、プロデューサとコンシューマプロセスの間で、同期の分離、即ち、データ要素又はデータ要素用の記憶空間が利用可能であることをもう一方のプロセスへ通知することが可能になり、通信、即ち、ＦＩＦＯバッファからの読み出し／ＦＩＦＯバッファへの書き込みが可能になる。
【００２０】
本発明のさらなる効果は、１個のデータ要素が利用可能であることを示すＬ回のシグナリングオペレーションとは違って、Ｌ個のデータ要素が利用可能であることを示す１回のシグナリングオペレーションが使用されるので、キャッシュコヒーレンストラフィックが低減されることである。
【００２１】
本発明のさらなる効果は、通信よりも粗い粒度で読み出しと書き込みが同期することである。この結果として、セマフォオペレーションが減少して機械語命令が少なくなり、キャッシュ整合性を維持するためのデータトラフィックが減少し、スレッドスケジューラ／オペレーティングシステムによるプロセスのブロックとブロック解除が減少する。
【００２２】
本発明の好ましい実施形態によれば、データ要素を共有ＦＩＦＯバッファへ書き込むとき、上記第１のシグナリングオペレーションは、上記ＦＩＦＯバッファへ入力されたＬ個のデータ要素が上記ＦＩＦＯバッファから出力するため利用可能になったことを示す。共有ＦＩＦＯバッファからデータ要素を読み出す場合、上記第２のシグナリングオペレーションは、Ｌ個のデータ要素用のＬ個の記憶空間が利用可能になったことを示すので、Ｌ個のデータ要素を上記ＦＩＦＯバッファへ入力することができる。
【００２３】
本発明のさらなる実施形態によれば、上記書き込みカウンタおよび／または上記読み出しカウンタは、所定の開始カウントから前方へインクリメントされる。上記書き込みカウンタのカウントおよび／または上記読み出しカウンタのカウントが所定の第１の限界Ｌに到達したかどうかが判定され、所定の第１の限界Ｌに到達した後、データ要素を上記ＦＩＦＯバッファへ書き込むときに第１のシグナリングオペレーションが実行され、又は、データ要素を上記ＦＩＦＯバッファから読み出すときに第２のシグナリングオペレーションが実行される。上記書き込みカウンタの上記カウントおよび／または上記読み出しカウンタの上記カウントが上記所定の第１の限界Ｌに到達したとき、上記書き込みカウンタおよび／または上記読み出しカウンタは上記所定の開始点にリセットされる。
【００２４】
本発明のまたさらなる実施形態によれば、所定の開始カウントは０であり、所定の第１の限界Ｌは１よりも大きい整数である。
【００２５】
本発明の目的は、共有ＦＩＦＯバッファへデータ要素を書き込む上記方法に対応した共有ＦＩＦＯバッファへデータ要素を書き込む装置と、共有ＦＩＦＯバッファからデータ要素を読み出す上記方法に対応した共有ＦＩＦＯバッファからデータ要素を読み出す装置と、によってさらに解決される。
【００２６】
本発明によれば、請求項１１によるコンピュータシステムも提供される。
【００２７】
さらに、本発明は、請求項１２によるコンピュータプログラムプロダクトを提供する。
【００２８】
以下、添付図面を参照して本発明をより詳細に説明する。
【発明を実施するための最良の形態】
【００２９】
第１および第２の実施形態では、上記ＦＩＦＯバッファ１００は、コンピュータシステムの共有メモリに実現され、共有メモリは、上記コンピュータシステムの少なくとも二つのプロセッサによってキャッシュされ、キャッシュコヒーレントプロトコルによって整合性が維持される。読み出しプロセスおよび書き込みプロセスは、別々のプロセッサ上で実行されるが、上記共有ＦＩＦＯバッファ１００へアクセスする。
【００３０】
図１は、第１の実施形態による、データ要素を共有ＦＩＦＯバッファ１００へ書き込む装置のブロック構成図である。上記装置は、入力ブロック手段１０と、入力手段１１と、第１の判定手段１４と、書き込みカウンタ１２と、第１のシグナリング手段１３と、第２の判定手段１７と、第１のリセット手段１８と、により構成される。
【００３１】
入力ブロック手段１０は、入力信号としてＦＩＦＯバッファ１００用の入力を受け取り、入力手段１１に接続され、この入力手段は共有ＦＩＦＯバッファ１００の入力に接続される。入力ブロック手段１０は、第１の判定手段１４へさらに接続され、第１の判定手段は入力信号として共有ＦＩＦＯバッファ１００の状態を受け取る。入力ブロック１０および共有ＦＩＦＯバッファ１００の入力に接続された入力手段１１は、書き込みカウンタ１２にも接続される。書き込みカウンタ１２は、第１のリセット手段１８と第２の判定手段１７にさらに接続される。第２の判定手段１７は第１の信号伝達手段１３にも接続される。
【００３２】
第１の判定手段１４は、記憶空間（余地）がデータ要素を書き込むことができる上記ＦＩＦＯバッファ１００内にて利用可能であるかどうかを判定し、判定結果を第１のブロック手段１０へ出力する。入力ブロック手段１０は、第１の判定手段が上記ＦＩＦＯバッファ１００内に記憶空間（余地）が利用可能でないと判定した場合、上記ＦＩＦＯバッファ１００への入力を阻止する。しかし、第１の判定手段１４が上記ＦＩＦＯバッファ１００内に記憶空間（余地）が利用可能であると判定した場合、入力手段はデータ要素を上記ＦＩＦＯバッファ１００へ入力する。その後、入力手段１１は、１個のデータ要素が上記ＦＩＦＯバッファ１００へ入力されたことを書き込みカウンタ１２に通知する。書き込みカウンタ１２は、入力手段１１によって１個のデータ要素が上記ＦＩＦＯバッファ１００へ入力されたことを通知されているならば、そのカウンタをインクリメントする。したがって、書き込みカウンタ１２のカウントは、上記ＦＩＦＯバッファ１００へ入力されたデータ要素の個数を示す。
【００３３】
第２の判定手段１７は、書き込みカウンタ１２のカウントが第１の限界Ｌに到達したかどうかを判定する。書き込みカウンタ１２のカウントが第１の限界Ｌに到達したとき、第２の判定手段１７は、第１の信号伝達手段１３および第１のリセット手段１８に、書き込みカウンタ１２のカウントが第１の限界Ｌに到達した旨を知らせる。第１の信号伝達手段１３は、第２の判定手段１７によって、書き込みカウンタ１２のカウントが第１の限界Ｌに到達した旨を知らされているとき、第１の信号伝達オペレーションを実行する。第１の信号伝達オペレーションは、Ｌ個のデータ要素が上記ＦＩＦＯバッファ１００から出力するために利用可能になった旨を示し、即ち、第１の信号伝達オペレーションは、利用可能なＬ個のデータ要素に関する１個のＶオペレーションを表す。
【００３４】
第１のリセット手段１８が第２の判定手段１７によって書き込みカウンタ１２のカウントが第１の限界Ｌに到達した旨を知らされたとき、好ましくは、第１の信号伝達オペレーションが実行された後に、第１のリセット手段１８は書き込みカウンタ１２のカウントを０でリセットする。これに応じて、第１の信号伝達オペレーションのバッファ処理は、書き込みカウンタ１２のカウントが第１の限界Ｌに到達した後に再始動される。
【００３５】
図２は、第２の実施形態による、データ要素を上記共有ＦＩＦＯバッファ１００から読み出す装置のブロック構成図である。上記装置は、出力ブロック手段２６と、出力手段２５と、第３の判定手段２４と、読み出しカウンタ２２と、第２の信号伝達手段２３と、第４の判定手段２７と、第２のリセット手段２８と、により構成される。
【００３６】
出力ブロック手段２６は、入力信号として、ＦＩＦＯバッファの出力要求又は読み出し要求を受け取り、出力手段２５に接続され、再度出力手段は共有ＦＩＦＯバッファ１００の出力に接続される。出力ブロック手段２６は、第３の判定手段２４にさらに接続され、第３の判定手段は共有ＦＩＦＯバッファ１００の状態を入力信号として受け取る。出力手段２５は、出力ブロック手段２６および共有ＦＩＦＯバッファ１００の出力に接続され、読み出しカウンタ２２にも接続される。読み出しカウンタ２２は、第２のリセット手段２８および第４の判定手段２７にさらに接続される。第４の判定手段２７はまた第２の信号伝達手段１３に接続される。
【００３７】
第３の判定手段２４は、上記ＦＩＦＯバッファ１００から読み出すためデータ要素が上記ＦＩＦＯバッファ１００にて利用可能であるかどうかを判定し、判定結果を出力ブロック手段１２６へ出力する。出力ブロック手段２６は、第３の判定手段２４が上記ＦＩＦＯバッファ１００内にデータ要素は利用可能でないと判定したとき、上記ＦＩＦＯバッファ１００からの出力を阻止する。しかし、第３の判定手段２４が上記ＦＩＦＯバッファ１００内にデータ要素が利用可能であると判定したならば、出力手段２５は上記ＦＩＦＯバッファ１００からデータ要素を出力又は抽出する。出力手段２５は、読み出しカウンタ２２に、１個のデータ要素が上記ＦＩＦＯバッファ１００から出力された旨を通知する。読み出しカウンタ２２は、出力手段２５によって、１個のデータ要素が上記ＦＩＦＯバッファ１００から出力された旨を通知されたならば、読み出しカウンタのカウントをインクリメントする。したがって、読み出しカウンタ１２のカウントは、上記ＦＩＦＯバッファ１００から出力されたデータ要素の個数を、即ち、上記ＦＩＦＯバッファ１００内でデータ要素のために利用可能な記憶空間の個数を示す。
【００３８】
第４の判定手段２７は、読み出しカウンタ２２のカウントが第１の限界Ｌに到達したかどうかを判定する。読み出しカウンタ２２のカウントが第１の限界Ｌに到達したとき、第４の判定手段２７は、第２の信号伝達手段２３および第２のリセット手段２８に、読み出しカウンタ２２のカウントが第１の限界Ｌに到達した旨を通知する。第２の信号伝達手段２３は、第４の判定手段２７によって、読み出しカウンタ２２のカウントが第１の限界Ｌに到達した旨を知らされたとき、第２の信号伝達オペレーションを実行する。第２の信号伝達オペレーションは、Ｌ個のデータ要素が出力手段２５によってＦＩＦＯバッファ１００から出力されたこと、並びに、上記ＦＩＦＯバッファ１００内で別のＬ個のデータ要素で充填するためにＬ個の記憶空間が利用可能であることを示し、即ち、第２の信号伝達オペレーションは、利用可能なＬ個の記憶空間に関して１回のＶオペレーションを表す。
【００３９】
第２のリセット手段２８が、第４の判定手段１７によって、読み出しカウンタ２２のカウントが第１の限界Ｌに到達したことを知らせるとき、好ましくは、第２の信号伝達オペレーションが実行された後、第２のリセット手段２８は、読み出しカウンタ２２のカウントを０でリセットする。これに応じて、第２の信号伝達オペレーションのバッファ処理は、読み出しカウンタ２２のカウントが第１の限界Ｌに到達した後に再始動される。
【００４０】
上記共有ＦＩＦＯバッファ１００からデータ要素を読み出す装置、および、上記共有ＦＩＦＯバッファ１００へデータ要素を書き込む装置は、並列処理に基づくコンピュータシステムで実現してもよく、又は、マルチタスク処理に基づくコンピュータシステムで実現してもよい。
【００４１】
注意すべき点は、上記ＦＩＦＯバッファ１００内で利用可能なデータ要素に関するＶオペレーションは、デッドロックが発生するかもしれないので、本発明の第１の実施形態で提案されているように一時的に蓄えられることである。例えば、プロセスＡが別のプロセスＢへトークンを送出し、プロセスＢからの応答を待機し始めるならば、プロセスＢにプロセスＡによって送出されたトークンが知らされない場合にデッドロックが発生する。なぜならば、利用可能なデータ要素に関するＶオペレーションは、Ｌ個のデータ要素が上記ＦＩＦＯバッファ１００から出力するために利用可能になるまで一時的に蓄えられるからである。これは、プロセス毎にブロックハンドラーを導入することによって回避できる。ブロックハンドラーは、例えば、セマフォカウンタが０であるためにプロセスが阻止される直前に、全体的なプロセススケジューラによって実行される。ブロックハンドラーは、読み出しプロセスが書き込みをする全てのＦＩＦＯバッファに対して、上記第１の信号伝達オペレーションを実行することによって、即ち、読み出しプロセスによって読み出すためにデータ要素がＦＩＦＯバッファ内で利用可能であることを知らせることによって実現される。
【００４２】
要約すると、２個のプロセッサは共有メモリに格納されたＦＩＦＯを用いて相互に通信するプロセスを実行する、ということである。相互接続は典型的にバスである。たびたび、プロセッサは、プロセッサと相互接続によって実現されるキャッシュコヒーレントプロトコルによって整合性を保たれるべきキャッシュを含む。また、ソフトウェア通信は同期の意味を含み、読み出し側はデータが利用可能になる前に読み出しをすべきではなく、書き込み側は空きスペースが利用可能になる前に書き込みをすべきではない。本発明は、通信よりも粗い精度で読み出し側と書き込み側を同期させることを目指している。この結果として、セマフォオペレーションが減少し、キャッシュ整合性を維持するためのデータトラフィックが減少し、スレッドスケジューラ／オペレーティングシステムによるプロセスのブロックとブロック解除が減少する。
【図面の簡単な説明】
【００４３】
【図１】第１の実施形態による、データ要素を共有ＦＩＦＯバッファへ書き込む装置のブロック構成図である。
【図２】第２の実施形態による、データ要素を共有ＦＩＦＯバッファから読み出す装置のブロック構成図である。
【図３Ａ】従来技術による、データ要素を共有ＦＩＦＯバッファへ書き込む方法のフローチャートである。
【図３Ｂ】従来技術による、データ要素を共有ＦＩＦＯバッファへ書き込む方法のフローチャートである。
【図１】
2005509943.tif 000003
【図２】
2005509943.tif 000004
【図３Ａ】
2005509943.tif 000005
【図３Ｂ】
2005509943.tif 000006
【国際調査報告】
2005509943.tif 000007
2005509943.tif 000008