JPH0528864B2 - - Google Patents

Description

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

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

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

また、第16回アニユマル インターナシヨナル
シンポジウム オン フオールト トレラント
コンピユーテイング（Annual
InternationalSymposium 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.3
BSDのTEMPOの同期方式においては、マスタ
ノードが必要不可欠である。このため、マスタノ
ードの障害時には、他のノードがマスタノードの
機能を果すように、マスタノードの代行の方法が
必要となる。また、すべてのノードのクロツクの
問い合せ等を１つのマスタノードが行うために、
ノードの数が増えると、マスタノードへの通信量
が増加するとともに、すべてのノードの時刻の平
均を求める作業が増大する。

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

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

（問題を解決するための手段） 本発明によれば、ｎ個のプロセツサからなるマ
ルチプロセツサシステムのクロツク同期方式にお
いて、前記プロセツサは、時刻を示すクロツクを
具備し、前記クロツクが予め定められた時刻を示
す時に、前記ｎ個のプロセツサの中からｍ個のプ
ロセツサをランダムに選択して該ｍ個のプロセツ
サのクロツク情報を読み出し、該ｍ個のプロセツ
サの時刻に基づき前記クロツクを制御することを
特徴とするマルチプロセツサシステムにおけるク
ロツク同期方式が得られる。

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

本同期方式では、各プロセツサは、自プロセツ
サのクロツクが予め決められた時刻になる毎に、
システム内のｎ個のプロセツサの中からｍ個のプ
ロセツサをランダムに選択し、同プロセツサのク
ロツク情報を問い合せる。さらに、これら問い合
せたクロツク情報に基づき自分のクロツクの値を
再設定する。例えば、プロセツサ３０１は自己の
クロツクが１：00，２：00，３：00、というよう
に定められた時刻になる毎に、システム内の５つ
のプロセツサの中から、ランダムにプロセツサを
選択する。プロセツサ３０１は、ある時、プロセ
ツサ３０２，３０２，３０４を選択し、通信路３
０６を介してこれらプロセツサにクロツク値を問
い合せる。プロセツサ３０１は、得られた３個の
プロセツサのクロツク値に基づき、これらクロツ
ク値の平均値を計算し、該平均値をもとに自分の
クロツクの値を再設定する。例えば、３個のプロ
セツサの時刻の平均値が自分のクロツクの示す時
刻よりもδ進んでいる場合は自分のクロツクに該
差分δを加算し、該３個のプロセツサの時刻の平
均値が自分のクロツクが示す時刻よりもδ遅れて
いる場合は、自分のクロツクをδ停止させる。以
上の操作は、すべてのプロセツサが、自分のもつ
クロツクが予め定められた時刻になる毎に繰り返
し行う。

このようにすべてのプロセツサは、完全対等な
立場にあり全く同一のアルゴリズムを実施する。
この時、各プロセツサはｍ個のプロセツサのクロ
ツク情報をもとに同期制御を行なうため、従来に
比べ通信量を削減することができる。しかもこの
際にｍ個のプロセツサはランダムに選択されるた
め、同期制御を繰り返し行なうことにより、シス
テム内のすべてのプロセツサのクロツク情報が同
期制御に反映される。模擬実験により、プロセツ
サのクロツクの同期範囲が、ｎの値には依存せず
ｍ＝２〜10で充分な同期精度を満足するように収
束することを確認した。

以上のように、特定のプロセツサが共通時刻を
定義し同期制御を実施することがないため、ある
プロセツサの障害がシステムに致命的な障害をも
たらすことがない。

（第１の実施例） 第１図ａおよびｂに、本発明によるクロツク同
期方式を実現するアルゴリズムの第１の実施例を
示す。

第１図ａは、プロセツサが自分のクロツクが予
め定められた時刻を示した時に実行する同期制御
アルゴリズムであり、例えば、自己のクロツクが
１：00，２：00，３：00というようにある定めら
れた時刻になる毎に実行される。第１図ｂは、あ
るプロセツサが前記同期制御アルゴリズムを実行
し、同プロセツサからのメツセージを受信した時
に、実行されるアルゴリズムを示す。なお、これ
ら２つのアルゴリズムは並列に実行されるととも
に、自分自身に対するクロツク情報の送信要求が
発生してもかまわない。

プロセツサは、自分のクロツクが予め定められ
た時刻になると発生するように設定されたクロツ
クからの割込みを、第１図ａに示す制御ブロツク
１０１において検出する。このクロツクからの割
込みの検出により、以降の同期制御アルゴリズム
が起動される。すなわち、制御ブロツク１０２に
おいては、ｎ個のプロセツサの中からランダムに
ｍ個のプロセツサを選択し、引続き制御ブロツク
１０３ではこれら各プロセツサにクロツク情報の
送信を要求するメツセージを送信する。

各プロセツサは、第１図ｂに示したアルゴリズ
ムも並列に実行しており、同図の制御ブロツク１
１０では、プロセツサからのクロツク情報の送信
要求メツセージの受信時に発生する受信割込みが
検出することができる。つまり、あるプロセツサ
が第１図ａの制御ブロツク１０３にてメツセージ
を送信すると、該メツセージを受信したプロセツ
サは第１図ｂの制御ブロツク１１０にて、受信割
込みを検出し、続いて第１図ｂの制御ブロツク１
１１において該メツセージの送信元プロセツサに
クロツク情報を送信する。この時にプロセツサが
送信するクロツク情報は、クロツクの示す値自身
とするが、クロツク情報を要求するプロセツサが
該要求メツセージに自分の時刻を記録するものと
すると、該要求プロセツサの時刻との差分をクロ
ツク情報として送信してもかまわない。

このように、クロツク情報の送信要求メツセー
ジを送信したプロセツサは、ｍ個のプロセツサか
らクロツク情報を受信する。続く制御ブロツク１
０４においては、これらｍ個のプロセツサのクロ
ツク情報に基づきｍ個のプロセツサの平均クロツ
ク値を計算し、自プロセツサのクロツクが示す時
刻から該ｍ個のプロセツサの平均時刻を差引き、
差分δを求める。

プロセツサは以上のようにして求めたｍ個のプ
ロセツサの平均時刻との差分δに基づき、制御ブ
ロツク１０５以降において次に説明するように自
分のクロツクの値を設定する。すなわち、自プロ
セツサのクロツクが示す時刻が該平均時刻に等し
い場合（δ＝０）には、制御ブロツクに１０１に
戻る。また、該平均時刻よりも自分のクロツクが
示す時刻が遅れている場合（δ＜０）には、制御
ブロツク１０６において自分のクロツクに該差分
δを加算して時刻を進めた後に制御ブロツク１０
１に戻る。さらに、該平均時刻よりも自分のクロ
ツクが示す時刻が進んでいる場合（δ＞０）に
は、制御ブロツク１０７において自プロセツサ内
のタイマに該誤差δを設定し、制御ブロツク１０
８において、タイマが時間δの経過を通知するま
でクロツクを停止させる。このようにして時刻を
遅らせた後に制御ブロツク１０１に戻る。いずれ
の場合にも制御ブロツク１０１では、定められた
時刻に発生する次のクロツクからの割込みを検出
する。

以上説明したアルゴリズムはすべてのプロセツ
サが実行する。

（第２の実施例） 第２図ａおよびｂに、本発明によるクロツク同
期方式を実現するアルゴリズムの第２の実施例を
示す。

マルチプロセツサシステムの一例である通信ネ
ツトワークシステムにおいては、プロセツサが互
いに他のクロツク情報を読み出す場合に、プロセ
ツサ間の通信遅延、もしくは通信処理・平均時刻
の計算に必要な時間がクロツクの時間精度に比べ
て大きくなることが考えられる。クロツクの同期
制御にこのような処理オーバヘツドによる悪影響
を与えないようにするために、次に説明するよう
なアルゴリズムを用いてクロツク情報を読み出し
たプロセツサの時刻を定義する。

第２図ａおよびｂは、同アルゴリズムを示して
いる。ここに示したアルゴリズムは、すでに説明
した第１図ａの制御ブロツク１０２，１０３およ
び１０４に相当するアルゴリズムであり、具体的
には、プロセツサをランダムに選択するととも
に、同プロセツサにクロツク情報の送信を要求す
るメツセージの送信をｍ回繰り返し行ない、さら
に逐次受信されるこれらｍ個のプロセツサからの
クロツク情報に基づき、自プロセツサのクロツク
が示す時刻と平均時刻との差分δを求める制御を
示している。なお、第２の実施例において、第２
図ａおよびｂ以降の制御手順は、第１図ａの制御
ブロツク１０５以下の手順と同一である。

第２図ａに示す結合子２００は、第１図ａの制
御ブロツク１０１の後部に接続される。制御ブロ
ツク２０１において、選択すべきプロセツサの数
を計数する変数ｋに値０を代入し、制御ブロツク
２０２においてシステム内のｎ個のプロセツサか
らランダムにプロセツサｉを選択する。続いて制
御ブロツク２０３において、この時に自プロセツ
サ内のクロツクが示す時刻を変数Ti，０に代入
するとともに、制御ブロツク２０４において該プ
ロセツサｉにクロツク情報の送信を要求するメツ
セージを送信する。この後制御ブロツク２０５に
おいてランダムに選択したプロセツサ数を計数す
る変数ｋに１を加える。制御ブロツク２０６にお
いて変数ｋを値ｍと比較し、ｋ＜ｍならば再び制
御ブロツク２０２に戻り、ｋ＝ｍならば次の処理
に接続される結合子２０７へと続く。

結合子２０７は、第２図ｂに示す制御ブロツク
２０８の前部に接続される。制御ブロツク２０８
では、第２図ａで説明したようにｍ個のプロセツ
サに対して送信したクロツク情報の要求メツセー
ジに対する応答を待つている。該要求メツセージ
の送信時刻のばらつきおよび通信遅延のばらつき
により各プロセツサからの応答の到着もまちまち
となる。あるプロセツサｉからの応答が到着する
と、制御ブロツク２０９において、該応答が到着
した時刻を変数Ti，１に代入し、さらに制御ブ
ロツク２１０において該応答メツセージの中に記
録されたプロセツサｉの時刻を変数Tiに代入す
る。この後ランダムに選択し、前記要求メツセー
ジを送信したプロセツサ数を記憶した変数ｋから
１を差引き、制御ブロツク２１２において該変数
ｋの値を比較し、ｋ＞０ならば制御ブロツク２０
８に戻つて他のプロセツサからの応答を待ち、す
べてのプロセツサからの応答を受信し、ｋ＝０で
あるならば、制御ブロツク２１３を実行する。な
お、メツセージの紛失等により一定時間経過して
もすべてのプロセツサからの応答が得られない場
合が生ずる。この場合、すでに得られているクロ
ツク情報をもとに制御ブロツク２１３を実行して
もかまわない。同制御ブロツク２１３では、プロ
セツサｉを選択した時の時刻を示す変数Ti，０
とプロセツサｉからの応答が到着した時刻を示す
変数Ti，１およびプロセツサｉからの応答メツ
セージの中に記録されたプロセツサｉの時刻を示
す変数Tiをもとに、自プロセツサが時刻Ti，０
の時のプロセツサｉの時刻を予測し、プロセツサ
ｉの時刻と自プロセツサの時刻の差分δiを求め
る。つまり、プロセツサａからプロセツサｉへの
メツセージの通信遅延とほぼ同時に送信されたプ
ロセツサｉからプロセツサａへのメツセージの通
信遅延は等しいと仮定し、次式に従いプロセツサ
ｉの時刻を予測する。

Ti−（Ti，１−Ti，０）／２ (1) 従つて自プロセツサのクロツクが示す時刻とプ
ロセツサｉのクロツクが示す時刻の差分δiは次の
ように示される。

δi＝Ti，０−｛Ti−（Ti，１−Ti，０）／２｝
(2) 制御ブロツク２１４においては、このようにし
て求めたｍ個のδiの平均値を計算し、同値がラン
ダムに選択されたｍ個のプロセツサの平均時刻と
の差分δであるとする。なお、結合子２１５は、
第１図ａの制御ブロツク１０５の前部に接続され
る。以上のように求めた平均時刻との差分δをも
とに、すでに説明した第１図ａの制御ブロツク１
０５以降の手順を実施する。このアルゴリズムで
は、プロセツサ間の通信遅延を考慮してプロセツ
サの時刻を予測しており、通信遅延による影響を
除くことが可能である。

（発明の効果） このように、本発明のクロツク同期方式を用い
ることにより、マルチプロセツサシステムにおい
て、集中制御を行なうプロセツサを設けることな
く、すべてのプロセツサを対等に動作させて、各
プロセツサのクロツクをある範囲内で共通な時刻
を指すように制御することができる。集中制御を
行なうプロセツサが不要であるために、特定のプ
ロセツサの障害がシステムに致命的な障害を与え
ることがなく高い信頼性が確保できる。また、各
プロセツサが必要とする情報は、ｍ個のプロセツ
サの時刻情報だけでよく、模擬実験によれば、ｍ
＝２〜10で充分な同期精度が得られる。従つて、
すべてのプロセツサのクロツク情報を集める必要
がないため、プロセツサ数が増えた場合にも同期
制御に要する処理時間が増大することはない。し
かも、これらプロセツサは周期的にランダムに選
択されるために、すべてのプロセツサのクロツク
情報をもとにして同期制御が実施される。

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

【図面の簡単な説明】

第１図ａ，ｂは、本発明による第１の実施例を
示す流れ図、第２図ａ，ｂは通信遅延を考慮した
場合の第２の実施例におけるプロセツサの時刻を
求めるためのアルゴリズムを示す図、第３図は、
マルチプロセツサシステムの一例を示す図であ
る。 図において、１０１〜１１１、および２０１〜
２１４は制御ブロツク、２００，２０７，２１５
は結合子、３０１〜３０５はプロセツサ、３０６
はプロセツサ間の論理的な通信路を示す。

Claims (1)

1. 【特許請求の範囲】 １ ｎ個のプロセツサからなるマルチプロセツサ
   システムのクロツク同期方式において、前記プロ
   セツサは、時刻を示すクロツクを具備し、前記ク
   ロツクが予め定められた時刻を示す時に、前記ｎ
   個のプロセツサの中からｍ個のプロセツサをラン
   ダムに選択して該ｍ個のプロセツサのクロツク情
   報を読み出し、該ｍ個のプロセツサの時刻に基づ
   き前記クロツクを制御することを特徴とするマル
   チプロセツサシステムにおけるクロツク同期方
   式。 ２ 前記プロセツサは、任意時間の経過を測定で
   きるタイマを具備し、前記ｍ個のクロツク情報に
   基づき求められるｍ個のプロセツサの平均時刻
   が、自分のクロツクの示す時刻よりもδ進んでい
   る場合は自分のクロツクにδを加算し、該ｍ個の
   プロセツサの平均時刻が自分のクロツクの示す時
   刻よりもδ遅れている場合は、前記タイマが時間
   δの経過を通知するまで自分のクロツクを停止さ
   せることを特徴とする特許請求の範囲第１項記載
   のマルチプロセツサシステムにおけるクロツク同
   期方式。