(57)【特許請求の範囲】
【請求項１】
他のスレッドからのシグナルの発行又はタイムアウト状態の発生まで待機状態におかれるスレッドについて、その処理をブロックしておくセマフォーと、
待機スレッド数をカウントする待機カウンタと、
待機スレッドのタイムアウト状態に基づいて当該待機スレッドを再始動させ、前記待機カウンタを減少させる手段と、
再始動シグナルに応答して再始動させる待機スレッドについて出された再始動シグナルの個数をカウントするシグナルカウンタと、
前記再始動シグナルの個数分の待機スレッドを再始動し、前記待機カウンタと前記シグナルカウンタを減少させる手段と、
前記スレッドが前記待機カウンタ及び前記シグナルカウンタへアクセスできないように排他的にロックする手段と、
前記再始動シグナルの個数がゼロを越えかつ前記待機スレッドの個数がゼロであるか否かを判定する手段と、
前記再始動シグナルの個数がゼロを越えかつ前記待機スレッドの個数がゼロの場合に、前記再始動シグナルの個数に等しい個数のダミー待機処理を実行する手段と、
を含むことを特徴とするシステム。
【請求項２】
セマフォー値を仲立ちとして複数のスレッド間において同期制御を行う方法であって、
前記セマフォー値がゼロの場合にそれを獲得しようとしたスレッドが待機状態におかれる待機処理工程と、
他のスレッドから再始動シグナルが発行された場合に、待機スレッドがあればそれを再始動させるシグナル処理工程と、
待機状態が一定時間継続した場合に待機スレッドを再始動させるタイムアウト処理工程と、
前記タイムアウト処理工程と相前後して他のスレッドから再始動シグナルが発行され、これにより前記セマフォー値が増加して不適正の値になった場合にそれを判定する不適正判定工程と、
前記不適正が判定された場合にダミー待機処理を行って前記セマフォー値を適正にするダミー待機処理工程と、
を含むことを特徴とする同期制御方法。
【請求項３】
請求項２記載の方法において、更に、
前記再始動シグナルが発行された場合にシグナルカウンタの値を増加させるシグナルカウンタ増加工程と、
再始動シグナルの発行により待機スレッドが再始動した場合に前記シグナルカウンタの値を減少させるシグナルカウンタ減少工程と、
を含み、
前記ダミー待機処理工程では、前記シグナルカウンタの値に相当する個数のダミー待機処理が実行され、シグナルカウンタの値がゼロに初期化されることを特徴とする同期制御方法。
【発明の詳細な説明】
【０００１】
【発明の属する技術分野】
この発明は、マルチタスクコンピュータシステムにおける共用資源（リソース）に対する排他的なアクセス制御に関する。特に、この発明は、処理スレッド間の高度な通信同期を取るための条件変数に関わるものである。
【０００２】
【従来の技術及びその課題】
現在のコンピュータシステムでは、複数のプロセスが１又は複数のプロセッサ上で並行して実行されることがある。それらのプロセス間においては、しばしば記憶装置、入出力装置及びメモリ等の資源が共用される。複数のプロセスが同じデータ及びメモリまたは同じ資源を利用して動作しなければならない場合には、何等かの機構を用意し、資源に対する相互排他的なアクセスを実現することが必要になる。そのような機構は、プロセスのプリエンプト方式（優先実行方式）に従うマルチタスクをサポートしている単一プロセッサシステムでも必要である。つまり、ある時点では、特定の資源に対しただ１つのプロセスだけにアクセス権を与える機構が必要である。さらに、１つのコンピュータシステムで複数のプロセッサが動作を実行していて、動作を正常に完了させるためにそれらプロセッサ間で相互調整が必要である場合、プロセッサ間の処理の同期を取るためには何等かの工夫が必要がある。
【０００３】
セマフォーは、共用資源に対するアクセスを調整する同期機構である。セマフォーはその内部にカウンタを有しており、そのカウンタには、非負整数をとる値が管理される。そのカウンタの初期値は、通常、セマフォーが管理する資源の個数に設定される。バイナリセマフォーの初期値は１である。また、セマフォーの初期化後は、通常、獲得処理（wait）と開放処理（signal）の２つの場合のみアクセスが許容される。あるプロセスがバイナリセマフォーを獲得すると、そのプロセスがセマフォーを解放するまでは、他のプロセスは同じセマフォーを獲得することはできない。１より大きな値をもっているセマフォーは、カウントセマフォーと呼ばれる。カウントセマフォーは、複数のプロセスにより獲得できる。カウントセマフォーの値は、獲得される度に１ずつ減算される。値がゼロになると、いずれかのプロセスがセマフォーを解放するまでは、新たにセマフォーを獲得しようとしてもブロックされる。このように、セマフォーは共用資源を相互排他的に使用できるようにするものである。
【０００４】
条件変数は、セマフォーと同じような同期機構である。第１のプロセス群（１つまたは複数のプロセスで構成される）が条件変数の下で待ち状態の場合、第２のプロセスが再始動するための「シグナル」または「ブロードキャスト」を送信しない限り、第１のプロセス群はブロックされたままである。第２のプロセスが条件変数に対し「シグナル」を送信すると、当該条件変数の下でブロックされている第１のプロセス群のいずれかのプロセスが再始動される。第２のプロセスが条件変数に対し「ブロードキャスト」を送信すると、第１のプロセス群に属するすべてのプロセスが再始動される。条件変数の下でブロックされているプロセスがない場合は、条件変数に対しシグナルまたはブロードキャストを送信しても、当然何も実行されない。
【０００５】
条件変数方式では構造化アクセス機能が利用できるため、お互いにロックしているプロセスを簡単に訂正できる。一方、実際のシステムでは構成要素に関するタイムアウト機能が必要であるため、プロセス同期化機構でもタイムアウト機能を実現する必要がある。
【０００６】
【課題を解決するための手段】
本発明は、プロセッサの動作上の遅れが最小になるように、自己管理型分散システムにおいて非同期対話プロセスの排他機能を可能にする装置及び方法を提供するものである。また、本発明は、時間が重要な意味をもつアプリケーションにおけるシステム信頼性を向上させるためのプロトコルも提供する。また、本発明は、遊休状態の分散プロセッサによる計算時間の無駄を省く通信プロトコルも提供する。さらに、本発明は、プリミティブな同期装置しか備わっていないオペレーティングシステムに、強力な同期機構を提供するものである。このように、この発明の装置及び方法は、条件変数が備わっていないオペレーティングシステムでも条件変数を使用できるようにするものである。
【０００７】
条件変数は、自己管理型分散システムにおいて、非同期に対話するプロセッサが相互排他機能を利用できるようにするものである。また、条件変数は通信プロトコルとしても利用でき、これにより時間が重要な意味を持つアプリケーションでシステムを使用できるようにし、プロセッサの遊休状態により引き起こされる無駄な計算時間を最小限に抑えることができる。この発明の装置には、マルチプロセッシングコンピューティング環境における共用資源へのアクセスを制御するシステムも含まれる。この発明の方法にれば、タイムアウトが発生した時に対処できる条件変数が提供される。条件変数はセマフォーに似ているが、条件変数はmutexロック機能を利用してスレッドを待ち状態にすることができる点、およびシグナルをブロードキャストできる点でセマフォーとは異なっている。条件変数は、１つのセマフォーと２つのカウンタとで実現されている。一方のカウンタは待ち状態のスレッドをカウントし、他方のカウンタはセマフォーに対しシグナルを送信するスレッド数をカウントしている。
【０００８】
本発明は、望ましくは、セマフォー値を仲立ちとして複数のスレッド間において同期制御を行う方法であって、前記セマフォー値がゼロの場合にそれを獲得しようとしたスレッドが待機状態におかれる待機処理工程と、他のスレッドから再始動シグナルが発行された場合に待機スレッドがあればそれを再始動させるシグナル処理工程と、待機状態が一定時間継続した場合に待機スレッドを再始動させかつ前記セマフォー値を減少させるタイムアウト処理工程と、前記タイムアウト工程と相前後して、他のスレッドから再始動シグナルが発行されて前記セマフォー値が増加することによりそれが不適正の値になった場合に、それを判定する不適正判定工程と、前記不適正が判定された場合にダミー待機処理を行って前記セマフォー値を適正にするダミー待機処理工程と、を含むことを特徴とする。
【０００９】
【発明の実施の形態】
以下に、図面を参照しながら、この発明に係る実施形態を詳細に説明する。なお、同じ数字は対応する構成要素を示している。
【００１０】
図１は、分散マルチプロセッシングシステム１０を示したもので、複数のプロセッサ１２と資源１４が相互接続システム１６を介して接続されている。マルチプロセッシングシステム１０は、リアルタイムシステム、広域ネットワーク、またはローカルエリアネットワークであってもよい。また、１次プロセッサと複数の２次プロセッサとで構成されるネットワークでもよい。ただし、この場合、２次プロセッサ同士はピアツーピア（対等）ネットワークで実行され、１次プロセッサの監視は受けないものとする。さらに、マルチプロセッシングシステム１０は単一のコンピュータでもよい。この場合、図１に示されている各プロセッサは独立した処理スレッドになるため、別々の処理スレッド間で同期を取る必要がある。プロセッサ１２は、分散コンピューティング環境における個別スレッドでもよい。基本的には、本発明においては、資源が競合関係にあるオブジェクト、又は別のオブジェクトとの同期が必要なオブジェクトであれば、効果を期待できる。
【００１１】
図２は、図１の相互接続システム１６を中心としたブロック図である。図２に示されるように、相互接続システム１６にはメモリ４０が含まれ、インターフェース４２を介してスレッド４４と通信している。インターフェース４２には、記憶装置４６及び入出力（I/O）装置４８も接続されている。メモリ装置４０には、実行可能プログラムを記憶するための記憶領域４１、データを記憶するためのデータ記憶領域４３、及び条件変数モジュール４５が含まれている。
【００１２】
マルチプロセッシングシステム１０の操作時には、複数のプロセスＰ１〜Ｐｎを実行するために、各プロセスＰｉは複数のスレッド４４のいずれかに割り当てられる。これらのプロセスの実行可能コードは、記憶領域４３に記憶されている。記憶領域４３には、プロセスの処理対象になるデータも含まれている。記憶領域４３は、図２に示されるように、別々の記憶領域４３ｉ〜４３ｎに論理的に分割され、データ構造体を記憶できるようになっている。プロセスＰ１〜ＰＮの実行時には、データ記憶領域４３、データ記憶装置４６、及び入出力装置４８等の各種システム資源に対するアクセスの同期をとることが望まれる。このようにすることで任意の時点では、ただ１つのスレッドまたは限られた数のスレッドにだけ、これらの資源に対するアクセス権を与えることができる。
【００１３】
図３は、条件変数モジュール４５を論理的に図示したものである。条件変数モジュール４５には、要素としてレコードＲｉが含まれている。各レコードＲｉには、１つの条件変数が含まれる。各条件変数は、任意のスレッド４４からアクセス可能である。
【００１４】
図４は、条件変数モジュール４５の各要素Ｒｉの内容を示すブロック図である。条件変数モジュール４５の各要素Ｒｉは、セマフォー５０、シグナルカウンタ５１、及び、待ち状態カウンタ５２で構成されている。待ち状態カウンタ５２は待ち状態にあるスレッド４４の数を示していて、そのようなスレッド数に応じて増減するものである。セマフォー５０は、スレッドにより待ち状態におかれたりスレッド４４からのシグナルを受け取ったりして、各スレッド間の処理の同期を取るために使用される。シグナルカウンタ５１は、スレッドにより出されたシグナル数を示している。
【００１５】
条件変数は、幾つかの点でセマフォーと同様である。ただし、セマフォーがデータに対するアクセスを制御することでプロセス（つまりスレッド）の同期をとっているのに対し、条件変数はデータの値を基にスレッドの同期をとっている。複数のスレッドが連携処理を実行する場合、データが特定の状態になるか又は特定の事象が発生するまで、待ち状態におかれる。このように、条件変数は同期をとるためのオブジェクトとして使用され、特定の事象が発生してロックが解除されるまでスレッドがロック状態のままにしておかれる。ロックは、同時に解除されることもあり、また、タイムアウトが発生するかあるいは他のスレッドが条件変数に対しシグナルを発行することで解除されることもある。条件変数は、使用時には、常に、mutexロックに関連付けられている。
【００１６】
ここで、mutexロックは、特殊なバイナリセマフォーであり、所有者スレッド情報を有し、そのセマフォーを獲得したスレッドのみが開放処理を行うことができるというものである。本実施形態では、通常のバイナリセマフォーの他、metexセマフォーを利用できる。
【００１７】
スレッドとは、あるプロセスにおいて制御が順次に実行される場合の１つの単位である。スレッドは、現在、処理実行中のこともあり、待ち状態（つまり、処理が中断されている）のこともある。上記mutexは同期を取るためのオブジェクトで、複数のスレッドが共用データに対するアクセスの逐次化を図るために使用される。mutexは相互排他機能を実現するためのものである。この相互排他機能は、あるスレッドがmutexに対しロックをかけると、同じスレッドがmutexのロックを解除するまではそのスレッドがオーナーの状態を継続することで実現されている。
【００１８】
スレッドは待ち状態になると、特定の事象が発生するまで（signalセマフォーが特定のスレッドに対し送られるかまたはbroadcastセマフォーがすべてのスレッドに対し送られるまで）待ち状態を継続する。特定の事象が発生しない場合は、無限待ち状態になる。あるいは、セマフォー（signalまたはbroadcast）を受け取るかタイムアウトが発生するまで、待ち状態を継続する。タイムアウトが発生して待ち状態のスレッドが再始動されてからセマフォーが受け取られると、セマフォーカウンタ５０にはカウント１が残ったままになる。つまり、次のスレッドの待ち状態処理は正しく行われない。これに関しては図５及び図６を用いて後に詳述する。
【００１９】
条件変数をインプリメントするために、図２に示されているメモリ装置４０は幾つかの条件変数を受け取り及び発行する。プロシージャー“Initialize”は、条件変数を初期設定し及び獲得する。プロシージャー“CondWait”はmutexを解放し、条件変数にシグナルが送られてくるのを待つ。このシーケンスは、並行プロシージャー処理が他のスレッドによりこのシーケンスに関連付けられずに行われる。言い換えると、条件変数“CondWait”は、アトミックに処理される。条件変数に対しシグナルまたはブロードキャストが送られると、その条件変数に属する待ち状態のスレッドのいずれか又はすべてが再始動され、mutexが獲得される。プロシージャー“CondWaitTimed”と“CondWait”とは同じであるが、前者にタイムアウト値の引数が用意されている点が異なっている。タイムアウトで指定する時間内で処理が行われないと、スレッドは待ち状態から元の状態に自動的に戻る。条件変数“CondSignal”は、条件変数にシグナルを送る。条件変数“CondBroadcast”は、条件変数にブロードキャストを送る。条件変数“CondTerminate”は、条件変数を終了させる。これらの条件変数の使用方法については、後で説明する。
【００２０】
図５は、シグナルカウンタが備わっていない従来のコンピュータシステムにおけるwait及びbroadcastシグナルの通常のインプリメンテーションを示したタイミングチャートである。説明のため、セマフォー（カウンタ）の値（分子）及びセマフォーで待つスレッド数（分母）を表す分数として、セマフォー５０の状態が便宜上表現されている。実際には、セマフォーの値だけが管理されている。
【００２１】
いま、スレッド１（CondBroadcast）及びスレッド２（CondWaitTimed）が処理を行っている。時間Ｔ１では、待ち状態カウンタ５２（condcount）及びセマフォー５０（condsem）の状態に示されているように、初期状態では待ち状態のスレッドはなく、カウントはゼロである。時間Ｔ２では、スレッド２は待ち状態になり、セマフォー５０で待つスレッド数は１だけ増加する。スレッド２は待ち条件変数を獲得し、signalセマフォーが送られてくるかタイムアウトが発生することで再始動されるまで待つ。待ち状態カウンタ５２は１に設定される。時間Ｔ３では、スレッド１はsignalセマフォーを送信してスレッド２を再始動した後、スレッド１は待ち状態になる。セマフォー５０で待つスレッド数はゼロになる。セマフォーの値（分子）も０である。時間Ｔ４では、スレッド２は待ち状態カウンタ５２を１だけ減少させる。このタイミングチャートで示されているように、スレッド２はスレッド１からのsignalセマフォーにより再始動される。
【００２２】
図６は図５と同じ事象を示しているが、タイムアウトが発生する点が異なっている。時間Ｔ１では、スレッド１及びスレッド２が処理を行っており、待ち状態のスレッドはない。したがって、待ち状態カウンタ５２はゼロに設定され、セマフォー５０の値はゼロに設定されている。時間Ｔ２では、スレッド２は待ち状態になり、待ち状態カウンタ５２を１だけ増加させる。スレッド２は、waitセマフォーシグナルが送られてくるかまたはタイムアウトが発生するまで待ち状態になる。時間Ｔ３では、スレッド２はタイムアウトが発生することで再始動される。時間Ｔ４では、スレッド１はsignalをセマフォー５０へ送信し、セマフォー５０の値は１になる。しかし、スレッド２はタイムアウトによりすでに再始動されているため、スレッド１からのsignalはスレッド２の再始動でなく、セマフォー５０の値は不正な値になる。時間Ｔ５では、スレッド２は待ち状態カウンタ５２を１だけ減少させる。したがって、次の“CondWait”条件変数処理は正しい処理を行うことができない。
【００２３】
これに対し、図７は、スレッド１と２の処理を示したタイミングチャートであるが、シグナルカウンタ５１（sigcount）が追加されている。図７では、スレッド２がスレッド１からのsignalセマフォーにより再始動される点では、通常のルーチンに従った処理が行われている。まず時間Ｔ１では、システムは条件が初期設定された状態で設定される。つまり、待ち状態カウンタ５２及びセマフォー５０の値は両方共ゼロに設定される。さらに、シグナルカウンタ５１もゼロに設定される。時間Ｔ２では、スレッド２が待ち状態になり、セマフォー５０で待つスレッド数は１だけ増加する。スレッド２はsignalセマフォーが送られてくることにより、wait条件変数を獲得するか、またはタイムアウトが発生して再始動されるまで、待ち状態になる。待ち状態カウンタ５０は１に設定される。図５で示した場合と同様に、待ち状態のスレッド２は、タイムアウトが引き起こされる前に、時間Ｔ３でスレッド１からのsignalセマフォーにより再始動される。また、時間Ｔ３では、スレッド１はSignalの数をSigcountに設定する。時間Ｔ４では、待ち状態カウンタが１だけ減少される。時間Ｔ５では、シグナルカウンタは１だけ減少される。このように、シグナルカウンタ５１を追加しても、通常の処理の実行には影響を与えない。
【００２４】
図８は、タイムアウトが発生してスレッド２を再始動させるとき、本発明によるスレッド１及び２の処理を示したものである。このケースは図６に示したケースと同じであるが、シグナルカウンタ５１が追加されている点が異なっている。時間Ｔ１でシステムは初期設定され、この時、待ち状態、シグナル、及びセマフォー５０〜５２はゼロに設定される。時間Ｔ２で、スレッド２は処理を待つかまたは中断しなければならない条件を検出する。したがって、スレッド２は“ConWaitTimed”を実行し、signalセマフォーが送られてくるかタイムアウトが発生することで再始動されるまで待つ。このため、時間Ｔ２では、待ち状態カウンタ５２は１に設定され、セマフォー５０で１つのスレッドが待ち状態であることを示す。
【００２５】
時間Ｔ３で、スレッド２はタイムアウトが発生したことで再始動され、セマフォー５０には待ち状態のスレッドは存在しなくなる。時間Ｔ４では、signalセマフォーがブロードキャストされる。スレッド２はすでに再始動されているにもかかわらず、signalセマフォーはスレッド２の再始動を試みる。シグナルカウンタ５１はスレッド１により１に設定され、セマフォー５０の値は１だけ増加される。このように、セマフォー５０は待ち状態スレッドの数を正しく表すことができない。
【００２６】
時間Ｔ５では、待ち状態カウンタ５２は時間Ｔ３で発生したタイムアウトに応答して１だけ減少される。待ち状態カウンタ５２はゼロになり、シグナルカウンタ５１（１に設定されたまま）はシグナルの超過数を表す。このように、セマフォー５０の状態は、シグナルカウンタの値を使用して訂正することができる。
【００２７】
時間Ｔ６では、ダミー処理が開始される。つまり、スレッド２はシグナルカウンタ５１の値により、「シグナル」を受けた回数だけ待ち処理を実行する。この処理により、セマフォー５０の値は、ゼロに設定される。このように、シグナルカウンタ５１を追加することで、セマフォー状態を訂正できる。つまり、１または複数のスレッドがタイムアウトにより再始動されても、シグナルカウンタ５１はすべてのスレッドが再始動された時点でセマフォーカウンタ５０をゼロにリセットできる。
【００２８】
図９〜図１１は、この発明の方式及び方法を使用しない従来のシステムを示している。図９は、シグナルカウンタ５１を使用しないコンピュータシステム１０の従来の初期値設定方法を示している。コンピュータシステム１０を初期設定するために、待機スレッドカウンタ（condcount）５２が０に設定され、セマフォー（condsem）が０に設定される。
【００２９】
図１０は、“CondSignal”条件変数処理のサブルーチンを示したものである。ステップＳ１０では、条件変数によりアクセスを制御される共用資源の排他ロックを取得できるまで待ち、ロックが取得できたならば、次の処理ステップに進む。
【００３０】
ステップＳ１２では、メモリ装置４０の待機スレッド数カウンタ（condcount）５２を検査する。待機スレッド数カウンタ（condcount）５２の値が０より大きい場合は、処理はステップＳ１３に進む。０以下の場合は、処理はステップＳ１４にジャンプする。ステップＳ１３では、セマフォー（condsem）５０で待機しているスレッドを再始動するため、signalをセマフォー（condsem）５０に発行する。次に、ステップＳ１５に移る。ステップ１４では、Ｓ１０で獲得したロックを開放する。次に処理はステップＳ１５に進み、制御は主ルーチンへ戻る。
【００３１】
図１１は、シグナルカウンタが備わっていないシステムにおける“CondWait”条件変数処理のサブルーチンを示したものである。ステップＳ１６では、条件変数によりアクセスを制御される共用資源の排他ロックを獲得できるまで待ち、ロックが獲得できたならば、次の処理ステップＳ１７へ進む。ステップＳ１７では、待機スレッド数カウンタ（condcount）５２に１を加算し、Ｓ１６で獲得したロックを開放し、セマフォー（condsem）５０にsignalが発行されるまで待機する。セマフォー（condsem）５０にSignalが発行されることにより、再始動したら、待機スレッド数カウンタ（condcount）５２から１を減算し、制御は主ルーチンに戻る。
【００３２】
図１２〜１４は、この発明に係る方法を示したものである。図１２は、システム初期設定を示したものであるが、シグナルカウンタ（sigcount）５１及び待機スレッド数カウンタ（condcount）５２、シグナルカウンタ（sigcount）５１へのアクセスを排他制御するロックが追加されている。ステップＳ２０では、セマフォー（condsem）５０は初期値０に、待機スレッド数カウンタ（condcount）５２及びシグナルカウンタ（sigcount）５１は０に設定される。
【００３３】
図１３は、“CondSignal”条件変数処理のサブルーチンを示したものである。ステップＳ２１で、条件変数によりアクセスを制御される共用資源の排他ロック及び条件変数を構成するカウンタにアクセスするためのロックを獲得できるまで待ち、ロックが獲得できたならば次の処理ステップＳ２２へ進む。ステップ２２で、メモリ装置４０の待機スレッド数カウンタ（condcount）５２を検査する。待機スレッド数カウンタ（condcount）５２の値が０より大きな値に設定されている場合、処理はステップＳ２４に進む。０以下の場合は処理はステップＳ２６へ直接ジャンプする。
【００３４】
ステップＳ２４では、シグナルカウンタ（sigcount）５１に１を加算し、セマフォー（condsem）５０で待機しているスレッドを再始動するためsignalをセマフォー（condsem）５０に対して発行する。ステップＳ２６では、獲得していたロックを開放し、制御は主ルーチンへ戻る。
【００３５】
図１４は、“CondWait”条件変数処理のサブルーチンを示したものである。ステップＳ３０では、条件変数によりアクセスを制御される共用資源の排他ロックを獲得できるまで待ち、ロックが獲得できたならば、次のステップＳ３４へ進む。
【００３６】
ステップＳ３４では、待機スレッド数カウンタ（condcount）５２、シグナル数カウンタ（sigcount）５１にアクセスするためのロックを獲得するまで待ち、獲得できたならば、待機スレッド数カウンタ（condcount）５２に１を加算し、ロックを開放する。次にステップＳ３６へ進む。
【００３７】
ステップＳ３６では、条件変数によりアクセスを制御される共有資源の排他ロックを開放し、セマフォー（condsem）５０でsignal又はタイムアウトの発生を待つ。セマフォー５０に対しsignalが発行されるか、タイムアウトが発生したことにより、再始動されると、次のステップＳ３８へ進む。ステップＳ３８では、待機スレッド数カウンタ（condcount）５２、シグナル数カウンタ（sigcount）５１にアクセスするためのロックを獲得するまで待ち、獲得できたならば、待機スレッド数カウンタ（condcount）５２から１を減算し、次のステップＳ４０へ進む。
【００３８】
ステップ４０では、スレッドがセマフォー（coundsem）５０へのsignalが発行されたために再始動したのか、タイムアウトしたのかを検査する。signalにより再始動した場合は、処理はステップＳ４２へ進む。そうでない場合、処理はステップＳ４４へ直接ジャンプする。
【００３９】
ステップＳ４２では、シグナルカウンタ（sigcount）５１から１を減算する。次に、処理はステップＳ４４へ進む。ステップＳ４４で、待機スレッド数カウンタ（condcount）５２が０に設定されていて、しかもシグナルカウンタ（sigcount）５１が０より大きいかどうか判断する。両方の条件が満たされている場合、処理はステップＳ４６へ進む。満たされていない場合、処理はステップＳ５０へジャンプする。
【００４０】
ステップＳ４６では、ダミー wait処理が実行され、シグナルカウンタ（sigcount）５１から１を減算する。次に、処理はステップＳ４８へ進む。ステップＳ４８で、シグナルカウンタ（sigcount）５１が０に設定されたかどうかを判別する。シグナルカウンタ（sigcount）５１が０に設定された場合、処理はステップＳ５０へ進む。設定されていない場合、処理はステップＳ４６へ戻る。
【００４１】
ステップＳ５０では、待機スレッド数カウンタ（condcount）５２、シグナルカウンタ（sigcount）５１にアクセスするためのロックを開放する。次に、条件変数にアクセスするためのロックを獲得するまで待ち、獲得できたならば、制御は主ルーチンへ戻る。
【００４２】
上記実施形態によれば、タイムアウト機能付きの条件変数を実現できる。セマフォーによる条件変数自体は従来から知られているが、上記実施形態によれば、タイムアウト機能が付加された条件変数を実現できる。
【００４３】
ここで、タイムアウト処理は、セマフォーの機能を利用して実行され、タイムアウト発生タイミングは制御できない。よって、開放処理（signal処理）とタイムアウト処理とがほとんど同時に起こった場合、開放処理で読み出されるセマフォーの値が、タイムアウト前の値であるかタイムアウト後の値であるか判別できなくなる。具体的に説明すると、シグナル処理とタイムアウト処理とが相前後して発生した場合、シグナル処理を行うスレッドは、待機スレッド数カウンタから、タイムアウトしたスレッドを含んだ待機スレッド数を読み出す可能性がある。この場合、必要な数より多い数のシグナルが発生してしまう。その状態では、最終的にセマフォーの値が０より大きな値（正の値）となり、次にウエイト処理を行うスレッドが期待通りにウエイトせず、セマフォーを獲得して処理を終了してしまうという問題が生じる。これに対し、上記実施形態によれば、シグナルカウンタが設けられ、その値に基づいてダミー処理を実行することにより、セマフォーの値を強制的に修正できる。ダミー処理では、待機状態から起きてきたスレッドが待機スレッド数から１を減算してその値が０になり、シグナルカウンタが正の値をもっている時に実行される。具体的には、シグナルカウンタの値だけ待機処理を呼び、シグナルカウンタの値を０に戻す処理が実行されるる。ちなみに、タイムアウトしたスレッドだけでなく、正常にシグナルにより再起動したスレッドでもダミー処理が必要となる場合がある。その理由は、タイムアウト処理とシグナル処理がほとんど同時に発生した場合に、機構の実現方法如何によっては、一連の処理の結果、最後に処理されるスレッドがタイムアウトしたスレッドである保証はなく、問題を検知するスレットが正常にシグナル処理により再起動されたスレッドになる可能性があるからである。
【００４４】
上記で説明した実施例では、適切にプログラムされた汎用コンピュータがデータ処理を制御している。しかし、これらの処理機能は、システムレベル全体の制御を実行する中央処理装置部とその中央処理装置部の制御下で特定の計算、機能等の処理を実行する独立専用回路とを備えた、単一目的集積回路（ASIC等）を使用して実現することもできる。また、この処理は、独立した専用またはプログラマブル集積電子回路あるいは装置（PAL、PLA、FPGA、及びPLD等のハードワイヤード電子または論理装置等）を使用して実現することもできる。通常、図１０〜１２のフローチャートを実行できる有限状態マシンに接続されている装置または装置の集合を使用し、データ処理を制御できる。
【００４５】
好ましい実施態様を参照しながらこの発明を説明したが、この実施態様は説明上のもので、制約的なものではない。特許請求の範囲で定義しているこの発明の精神と範囲に反することなしに、各種変更が可能である。
【図面の簡単な説明】
【図１】  この発明の特徴を実現している分散プロセッサシステムを示すブロック図である。
【図２】  図１の分散プロセッサシステムの相互接続システムを示すブロック図である。
【図３】  図１の分散プロセッサシステムの条件変数モジュールを論理的に示す図である。
【図４】  図３の条件変数モジュールの各要素を示すブロック図である。
【図５】  コンピュータシステムのタイミング図である。
【図６】  タイムアウトが発生したときのコンピュータシステムのタイミング図である。
【図７】  シグナルカウンタを使用するコンピュータシステムのタイミング図である。
【図８】  タイムアウトが発生したときにシグナルカウンタを備えているコンピュータシステムのタイミング図である。
【図９】  シグナルカウンタを備えていないコンピュータシステムにおけるセマフォーの使用方法を示したフローチャートである。
【図１０】  シグナルカウンタを備えていないコンピュータシステムにおけるセマフォーの使用方法を示したフローチャートである。
【図１１】  シグナルカウンタを備えていないコンピュータシステムにおけるセマフォーの使用方法を示したフローチャートである。
【図１２】  シグナルカウンタを備えたコンピュータシステムにおける条件変数の使用方法を示しているフローチャートである。
【図１３】  シグナルカウンタを備えたコンピュータシステムにおける条件変数の使用方法を示しているフローチャートである。
【図１４】  シグナルカウンタを備えたコンピュータシステムにおける条件変数の使用方法を示しているフローチャートである。
【符号の説明】
４４  スレッド、５０  セマフォー、５２  待ち状態カウンタ、５１  シグナルカウンタ。
【図１】
0003707273.tif 000002
【図２】
0003707273.tif 000003
【図３】
0003707273.tif 000004
【図４】
0003707273.tif 000005
【図５】
0003707273.tif 000006
【図６】
0003707273.tif 000007
【図７】
0003707273.tif 000008
【図８】
0003707273.tif 000009
【図９】
0003707273.tif 000010
【図１０】
0003707273.tif 000011
【図１１】
0003707273.tif 000012
【図１２】
0003707273.tif 000013
【図１３】
0003707273.tif 000014
【図１４】
0003707273.tif 000015