JPH0528866B2 - - Google Patents

Description

【発明の詳細な説明】 （産業上の利用分野） 本発明は、それぞれのプロセツサが共通にアク
セスできる共有メモリを持たないマルチプロセツ
サシステムにおいて、各々のプロセツサが時刻を
示すために有するクロツクを互いに調整するため
のクロツク同期方式に関する。

（従来の技術） マルチプロセツサシステムにおいては、システ
ムを構成する各プロセツサのクロツクをシステム
全体に共通な時刻を示すように同期させることが
必要となる。例えば、分散フアイリングシステム
において、各フアイルに記録された作成および編
集時刻に基づきフアイルのバージヨンを識別する
ためには、各プロセツサ間に共通な時刻が必要と
なる。また、各プロセツサが、システムに共通な
時刻に基づき自己の履歴情報を蓄積しておけば、
障害発生時にどのような順番で障害が検出された
かを知ることができ、障害の発生箇所を特定する
ための情報を得ることができる。

共有メモリを持たないマルチプロセツサシステ
ムの一例である、通信ネツトワークシステムにお
いても、各通信ノードのクロツクが共通な時刻を
示すようにする同期方式が必要である。例えば、
1986年５月に開催された第６回インターナシヨナ
ル・コンフアランス・オン・デイストリビユ−テ
ツド・コンピユーテイング・システムズ
（International Conference on DISTRIBUTED
COMPUTING SYSTEMS）の予稿集p.364−
371に記載されている論文アン・エレクシヨン・
アルゴリズム・フオー・デイストリビユーテツ
ド・クロツク・シンクロナイゼーシヨン・プログ
ラム（An Election Algorithm for ａ
Distributed Clock Synchronization Program）
（文献１）で紹介されているクロツク同期方式
TEMPOは、UNIXオペレーテイングシステム
4.3BSDで動作するネツトワークに設けられてい
るものである。上述のシステムにおいては、マス
タとなる１つのノードが、定められた時間毎にす
べてのノードに時刻の問い合せを行い、求められ
た各ノードの時刻をもとに平均時刻を計算する。
この後すべてのノードに対してクロツクの調整指
示を行い、各ノードはこの指示に従いクロツクの
調整を行う。

また、1986年第16回アニユアル・インターナシ
ヨナル・シンポジウム・オン・フオールトトレラ
ント・コンピユーテイング（Annual
International Symposium on FAULT−
TOLERANT COMPUTING）のダイジエスト
ペーパーp.218−223に記載されている論文クロツ
ク・シンクロナイゼーシヨン・イン・ザ・プレゼ
ンス・オブ・オミツシヨン・アンド・パフオーマ
ンス・フオールツ・アンド・プロセツサ・ジヨイ
ンズ（CLOCK SYNCHRONIZATION IN
THE PRESENCE OF OMISSION AND
PERFORMANCE FAULTS，AND
PROCESSOR JOINS）（文献２）で紹介されて
いるクロツク同期方式は、上で説明した
“TEMPO”のようにマスタ・スレーブ型の制御
ではなく分散型の制御を用いている。同方式にお
いて、プロセツサはシステム内で定期的に同報さ
れる同期メツセージの中で、最も速い時刻を示す
同期メツセージに従いクロツクの時刻合せを行な
う。このため、結果として最も速く進むクロツク
がシステム内の時刻を支配することになる。

さらに、ジヤーナル・オブ・アソシエーシヨ
ン・フオー・コンピユーテイング・マシナリー
（Journal of Association for Computing
Machinery），Vol.32，No.１，January 1985，
p.52−78に記載されている論文シンクロナイジン
グ・クロツクス・イン・ザ・プレゼンス・オブ・
フオールツ（Synchronizing Clocks in the
Presence of Faults）（文献３）で紹介されいる
クロツク同期方式は、すべてのプロセツサが定期
的に互いにプロセツサの時刻を通信しあう完全分
散制御による同期方式である。

（発明が解決しようとする問題点） 上述のUNIXオペレーテイングシステム
4.3BSDのTENPOの同期方法においては、マス
タノードが必要不可欠である。このため、マスタ
ノードの障害時には、他のノードがマスタノード
の機能を果すように、マスタノードの代行の方法
が必要となる。また、すべてのノードのクロツク
の問い合せを１つのマスタノードが行うために、
ノードの数が増えると、マスタノードへの通信量
が増加するとともに、すべてのノードの時刻の平
均を求める作業が増大する。

これに対し、分散型の制御を採用している文献
２記載の方式では、分散型ではあるものの、最も
速いクロツクをもつ１つのプロセツサがシステム
内の時刻を支配する結果となる。また、文献３の
方法は、すべてのプロセツサが互いにすべてのプ
ロセツサと通信を行なうために、実際のシステム
に適用する場合に通信のオーバヘツドが問題とな
る。

本発明においては、集中制御を行なうプロセツ
サを設ける必要がなく、よつて一つのプロセツサ
がシステム内の時刻を支配することがなく、シス
テム内のプロセツサ数が増加した場合にも、通信
のメツセージ数が極端に増加して処理オーバヘツ
ドが増加することがなく、システム内の総メツセ
ージ数を従来方式より削減することが可能な分散
制御型のマルチプロセツサシステムにおけるクロ
ツク同期方式を提供することにある。

（問題を解決するための手段） 本発明によれば、ｎ個のプロセツサからなるマ
ルチプロセツサシステムのクロツク同期方式にお
いて、前記プロセツサは時刻を示すクロツクとラ
ンダム変数を生成する手段を具備し、該ランダム
変数生成手段ｍ／ｎ（ｍはｎより小さい正数）の
確率で１を、（１−ｍ／ｎ）の確率で０を選択す
るようになつており、各プロセツサはあらかじめ
定められた周期毎にランダム変数を選択し、該選
択されたランダム変数が１の場合にはクロツクが
あらかじめ定められた時刻を示すときに全てのプ
ロセツサにクロツク情報を送出し、クロツク情報
を受信した全てのプロセツサでは受信した全ての
クロツク情報に基づき各自のクロツクを制御する
ことを特徴とするマルチプロセツサシステムにお
けるクロツク同期方式が得られる。

（発明の原理） 本発明の原理について、第３図を参照して説明
する。第３図は、マルチプロセツサシステムの具
体例を示す。各プロセツサ３０１，３０２，３０
３，３０４，３０５は、自己の時刻を示すクロツ
クを備えている。また、各プロセツサはランダム
変数ｖを生成する手段を備えており、あらかじめ
与えられた確率ｐでｖ＝１を、確率（１−ｐ）で
ｖ＝０が選択されるようになつている。さらに各
プロセツサは任意のプロセツサのクロツク情報を
読み出せるよう、相互に論理的な通信路により結
合されており、例えばプロセツサ３０３とプロセ
ツサ３０４の間は通信路３０６により接続されて
いる。互いにプロセツサが共通にアクセスできる
共有メモリを持たないマルチプロセツサシステム
においては、システムが初期状態の時に、各プロ
セツサのクロツクは同一の時刻を示してはいな
い。しかも同じ値からスタートしたクロツクも、
凡そ同じ割合で時刻を測定するものの、時刻の経
過にともない徐々にずれて行く。従つて、各プロ
セツサは以下に説明する本同期方式に従い、メツ
セージ通信により互いにクロツクの調整を行う必
要がある。この結果、すべてのプロセツサのクロ
ツクがある同期精度の範囲内で同一の時刻を指す
ように制御される。

本同期方式では、各プロセツサは、自プロセツ
サのクロツクが予め決められた時刻になる毎に
（例えば、１：00，２：00，３：00というように
定められた時刻になる毎に）、変数ｖの値を選択
し、もしｖ＝１ならば自己のクロツク値を全ての
プロセツサに送出する。またクロツクを受信した
プロセツサでは受信した全てのクロツク値とクロ
ツク値を受信した自プロセツサの時刻との差分を
とり、その差分の平均値Δによりクロツクの調整
を行なうものである。即ち、Δが正ならば自クロ
ツク値にΔを加算し、Δが負ならば自クロツクを
Δだけ停止させる。ここで、全プロセツサ数をｎ
とし、ｖ＝１をとる確率をｍ／ｎとなるようにセ
ツトすると、１回の制御あたり平均ｍ個のプロセ
ツサが自己のクロツクを全プロセツサに送出する
ことになる。各プロセツサではこの平均ｍ個のプ
ロセツサからのクロツク値の平均値に自分のクロ
ツク値をあわせることになる。

例えば各プロセツサのクロツク値が第３図に示
すような値をとつている場合について本発明の動
作を説明する。このとき、各プロセツサは各自の
時計が１：00を指すときに変数ｖの値を選択し制
御を開始するものとする。また、確率2/5でｖ＝
１を、確率3/5でｖ＝０を選ぶものとする。いま、
プロセツサ３０１とプロセツサ３０２がｖ＝１を
選択し、他のプロセツサはｖ＝０を選択したもの
とする。通信遅延を無視すると、まずプロセツサ
３０１が最初に１：00に到達し、そのクロツク値
（１：00）をすべてのプロセツサに送出する。各
プロセツサではプロセツサ３０１のクロツク値を
受信すると自己のクロツク値との差分をとる。差
分値は、プロセツサ３０１では０、プロセツサ３
０２では＋６、プロセツサ３０３では＋４、プロ
セツサ３０４では＋８、プロセツサ３０５では＋
２となる。

続いてプロセツサ３０２が１：00に達したとき
にクロツク値を送出し、そのクロツク値を全ての
プロセツサが受信するわけである。各プロセツサ
での差分値は、プロセツサ３０１では−６、プロ
セツサ３０２では０、プロセツサ３０３では−
２、プロセツサ３０４では＋２、プロセツサ３０
５では−４となる。よつて、各プロセツサは上記
の差分値の平均値をとり、その値をプロセツサ３
０１では−３、プロセツサ３０２では＋３、プロ
セツサ３０３では＋１、プロセツサ３０４では＋
５、プロセツサ３０５では−１となる。この差分
値の平均値に基づき、先に示したクロツク値の調
整を行なうこととすると、プロセツサ３０１のク
ロツクは３分遅らされ、プロセツサ３０２のクロ
ツクは３分進められ、プロセツサ３０３のクロツ
クは１分進められ、プロセツサ３０４のクロツク
は５分進められ、プロセツサ３０５のクロツクは
１分遅らされ、全てのプロセツサのクロツク値が
同一の値となるように調整されることがわかる。
この例では、説明の容易さのため各プロセツサの
クロツクドリフトおよび伝送路遅延は十分小さい
として無視している。以上の制御はすべてのプロ
セツサが、自分のもつクロツクが予め定められた
時刻になる毎に繰り返し行う。勿論、選択される
変数ｖの値は各時刻にてランダムであるので、各
時刻毎に自己のクロツクを送出するプロセツサお
よびプロセツサ数は結果としてランダムとなる。

このようにすべてのプロセツサは、完全対等な
立場にあり全く同一のアルゴリズムを実施する。
このランダムに選択されたプロセツサのみがその
クロツク値を送出するので、従来に比べ通信量を
削減することができる。また、１つのプロセツサ
のみがシステムの時刻を制御するのではなく、複
数のプロセツサの平均時刻でシステム時刻を制御
することにより、耐障害性のある時刻制御が可能
となる。さらに、耐障害性の度合いは、変数ｖが
１をとる確率を変えることで柔軟に制御すること
ができる。

（発明の詳細な説明） 第１図ａ，ｂ，ｃに本発明の方式を実現するた
めに各プロセツサにて実行される制御の一フロー
チヤート例を示す。第１図ａはクロツク情報の送
信制御を示すフローチヤート例であり、第１図ｂ
はクロツク情報の受信制御を示すフローチヤート
例であり、第１図ｃはクロツク受信処理の詳細を
示すフローチヤート例である。まず第１図ａの送
信制御フローチヤートの説明を行なう。各プロセ
ツサでは、ブロツク１０１にてクロツク割込み１
を検出すると、ブロツク１０２にてランダム変数
ｖを選択する。この変数ｖは１と０とをそれぞれ
確率ｐおよび（１−ｐ）でとるものである。１０
３のブロツクでは選択されたｖの値により制御の
スイツチが行なわれ、もしｖ＝１ならばブロツク
１０４でクロツク割込み２を待ち、クロツク割込
み２が検出されるとブロツク１０５にて自己のク
ロツク値を全プロセツサに送出し、送出後に送信
制御処理を終了してブロツク１０１に戻る。ま
た、ｖ＝０ならばブロツク１０１に戻り、次の周
期のクロツク割込み１を待つ。第１図ｂの受信制
御では、各プロセツサにてブロツク１０１でクロ
ツク割込み１を検出すると、ブロツク１１０のク
ロツク受信処理を実行する。なお、ブロツク１１
０のクロツク受信処理の詳細を示す一フローチヤ
ート例は第１図ｃに示しており、後で説明を加え
る。ブロツク１１０の受信処理が終了すると、受
信した全てのクロツク値と自クロツク値との差分
の平均値Δを、ブロツク１１１にて算出する。ブ
ロツク１１２では算出されたΔの正負により制御
のスイツチを行ない。もしΔが正ならばブロツク
１１３にて自クロツク値にΔを加算して自クロツ
クの調整を行なう。もしΔが負ならば、ブロツク
１１４にて自クロツクをΔだけ停止させて自クロ
ツクの調整を行なう。ブロツク１１３あるいは１
１４の処理が終了すると、ブロツク１０１に戻
り、次の周期でのクロツク制御を開始するための
クロツク割込み１を待つ。

第１図ｃのフローチヤート例を用いて、第１図
ｂのブロツク１１０に示したクロツク受信処理を
次に説明する。クロツク受信処理に入ると、ブロ
ツク１２０にてタイマがセツトされる。続いてブ
ロツク１２１にて送出されてくるクロツクの受信
待ちになる。ブロツク１２２ではセツトしたタイ
マがタイムアウトしたかどうかの判定を行ない、
もしタイムアウトしたならば受信処理を抜ける。
またタイムアウトしていなければ、クロツクが到
着したときにブロツク１２３にてクロツクの受信
がなされる。続くブロツク１２４では受信された
クロツクと自クロツク値との差分を求め、格納し
ておく。さらに続くブロツク１２５にてタイムア
ウト判定がなされ、もしタイムアウトならば受信
処理を終了し、タイムアウトでなければブロツク
１２１に戻つて新たなクロツク受信待ちの状態に
なる。

第２図に本発明のクロツク同期方式のタイミン
グチヤートの一例を示す。横軸は時間の推移を示
し、クロツク割込み１検出で各ブロセツサのクロ
ツク制御周期が開始される。図に示すように、ク
ロツク受信時間領域の窓が設けられ、その間に到
着したクロツク情報によつて各プロセツサのクロ
ツク値が調整されるわけである。なお、図におい
て、時間軸の上側はクロツク受信処理を示してお
り、下側はクロツク送信処理を示している。

（発明の効果） このように、本発明のクロツク同期方式を用い
ることにより、マルチプロセツサシステムにおい
て、集中制御を行なうプロセツサを設けることな
く、すべてのプロセツサを対等に動作させて、各
プロセツサのクロツクを共通な時刻を指すように
制御することができる。クロツク同期制御を行な
うプロセツサは、同期周期ごとにランダムに選択
されることになり、特定のプロセツサの障害がシ
ステムに致命的な障害を与えることがなく高い信
頼性が確保できる。また、この信頼性の度合いは
ランダム変数ｖが１をとる確率を制御することで
柔軟に変えることが可能である。さらに、固定の
数のプロセツサが各同期周期毎に選択されるので
はなく、同期制御用にクロツクを送出するプロセ
ツサ数もランダムであり、各周期毎に平均値とし
て与えられるので、制御にともなうデツドロツク
状態を回避することが容易である。また、全ての
プロセツサのクロツク値を用いて同期制御を行な
うものではなく、部分プロセツサ集合のクロツク
値を用いて制御がなされるので、プロセツサ数が
増えた場合にも同期制御に要する処理時間が極端
に増大することはない。

以上のように本発明により得られる効果は大き
い。

【図面の簡単な説明】

第１図ａ，ｂ，ｃは、本発明によるクロツク同
期方式の一実施例を示すフローチヤート、第２図
は、本発明によるクロツク同期方式の制御タイミ
ングチヤート、第３図は本発明の原理を説明する
ためのマルチプロセツサシステムの一例を示す図
である。 図において、１０１〜１０５，１１０〜１１４
および１２０〜１２５は制御ブロツク、３０１〜
３０５はプロセツサ、３０６はプロセツサ３０３
とプロセツサ３０４間の論理的な通信路を示す。

Claims (1)

1. 【特許請求の範囲】 １ ｎ個のプロセツサからなるマルチプロセツサ
   システムのクロツク同期方式において、前記プロ
   セツサは時刻を示すクロツクとランダム変数を生
   成する手段を具備し、該ランダム変数生成手段は
   ｍ／ｎ（ｍはｎより小さい整数）の確率で１を、
   （１−ｍ／ｎ）の確率で０を選択するようになつ
   ており、各プロセツサはあらかじめ定められた周
   期毎にランダム変数を選択し、該選択されたラン
   ダム変数が１の場合にはクロツクがあらかじめ定
   められた時刻を示すときに全てのプロセツサにク
   ロツク情報を送出し、クロツク情報を受信した全
   てのプロセツサでは受信した全てのクロツク情報
   に基づき各自のクロツクを制御することを特徴と
   するマルチプロセツサシステムにおけるクロツク
   同期方式。 ２ 前記各プロセツサは任意時間の経過を測定で
   きるタイマを具備し、前記受信した全てのクロツ
   ク情報の平均時刻が、自分のクロツクの示す時刻
   よりもΔ進んでいる場合は自分のクロツクにΔを
   加算し、前記平均時刻が自分のクロツクの示す時
   刻よりもΔ遅れている場合は、前記タイマが時間
   Δの経過を通知するまで自分のクロツクを停止さ
   せることを特徴とする特許請求の範囲第１項記載
   のマルチプロセツサシステムにおけるクロツク同
   期方式。