JPH01114964A - マルチプロセッサシステムにおけるクロック同期方式 - Google Patents

Abstract

(57)【要約】本公報は電子出願前の出願データであるた
め要約のデータは記録されません。

Description

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

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

共有メモリを持たないマルチプロセッサシステムの一例
である、通信ネットワークシステムにおいても、各通信
ノードのクロックが共通な時刻を示すようにする同期方
式が必要である。例えば、１９８６年５月に開催された
第６回インターナショナル、コンファランス・オン・デ
イストリビューテッド・コンピユーテイング・シろテム
ズ（ＩｎｔｅｒｎａｔｉｏｎａｌＣｏｎｆｅｒｅｎｃｅ
　ｏｎ　ＤＩＳＴＲＩＢＵＴＥＤ　ＣＯＭＰＵＴＩＮＧ
ＳＹＳＴＥＭＳ）の予稿集ｐ、３６４−３７１に記載さ
れている論文アン・エレクション・アルゴリズム・フォ
ー・デイストリビューテッド・クロック・シンクロナイ
ゼーション・プログラム（Ａｎ　Ｅｌｅｃｔｉｏｎ　Ａ
ｌｇｏｒｉｔｈｍ　ｆｏｒ　ａＤｉｓｔｒｉｂｕｔｅｄ
　Ｃ１ｏｃｋ　５ｙｎｃｈｒｏｎｉｚａｔｉｏｎ　Ｐｒ
ｏｇｒａｍ）（文献１）で紹介されているクロック同期
方式ＴＥＭＰＯは、ＵＮＩＸオペレーティングシステム
４．３ＢＳＤで動作するネットワークに設けられている
ものである。上述のシステムにおいては、マスクとなる
１つのノードが、定められた時間毎にすべてのノードに
時刻の問い合せを行い、求められた各ノードの時刻をも
とに平均時刻を計算する。この後すべてのノードに対し
てクロックの調整指示を行い、各ノードはこの指示に従
いクロックの調整を行う。

また、１９８６年第１６回アニュアル・インターナショ
ナル・シンポジウム・オン・フォールトトレラントコン
ピユーテイング（Ａｎｎｕａｌ　Ｉｎｔｅｒｎａｔｉｏ
ｎａｌＳｙｍｐｏｓｉｕｍｏｎＦＡＵＬＴ−ＴＯＬＥＲ
ＡＮＴＣＯＭＰＵＴＩＮＧ）のダイジェストペーパーｐ
、２１８−２２３に記載されている論文クロック・シン
クロナイゼーション・イン、ザ、プレゼンス・オン・オ
ミッション・アンド・バヅオーマンス・フォールツ・ア
ンド・プロセッサ・ジョＦＡＵＬＴＳ、　ＡＮＤ　ＰＲ
ＯＣＥＳＳＯＲＪＯＩＮＳＸ文厭２）で紹介されている
クロック同期方式は、上で説明した“ＴＥＭＰＯ”のよ
うにマスク・スレーブ型の制御ではなく分散型の制御を
用いている。同方式において、プロセッサはシステム内
で定期的に同報される同期メツセージの中で、最も速い
時刻を示す同期メツセージに従いクロックの時刻合せを
行なう。

このため、結果として最も速く進むクロックがシステム
内の時刻を支配することになる。

さらに、ジャーナル・オン・アソシエーション・フォー
・コンピユ−テイング・マシナリ−（Ｊｏｕｒｎａｌｏ
ｆ　Ａｓ５ｏｃｉａｔｉｏｎ　ｆｏｒ　Ｃｏｍｐｕｔｉ
ｎｇ　Ｍａｃｈｉｎｅｒｙ）、　Ｖｏｌ、３２゜Ｎｏ、
１．　Ｊａｎｕａｒｙ　１９８５．ｐ、５２−７８に記
載されている論文シンクロナイジング・クロックス・イ
ン、ザ・プレゼンス・オン・フォールツ（Ｓｙｎｃｈｒ
ｏｎｉｚｉｎｇ　Ｃ１ｏｃｋｓ　ｉｎ　ｔｈｅＰｒｅｓ
ｅｎｃｅ　ｏｆ　Ｆａｕｌｔｓ）（文献３）で紹介され
いるクロ、ツク同期方式は、すべてのプロセッサが定期
的に互いにプロセッサの時刻を通信しあう完全分散制御
による同期方式である。

（発明が解決しようとする問題点） 上述のＵＮＩＸオペレーティングシステム４．３ＢＳＤ
のＴＥＭＰＯの同期方法においては、マスタノードが必
要不可欠である。このため、マスタノードの障害時には
、他のノードがマスタノードの機能を果すように、マス
タノードの代行の方法が必要となる。また、すべてのノ
ードのクロックの問い合せを１つのマスタノードが行う
ために、ノードの数が増えると、マスタノードへの通信
量が増加するとともに、すべてのノードの時刻の平均を
求める作業が増大する。

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

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

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

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

本同期方式では、各プロセッサは、自プロセッサのクロ
ックが予め決められた時刻になる毎に（例えば、１：０
０，２：００，３：００というように定められた時刻に
なる毎に）、変数Ｖの値を選択し、もしｖ＝１ならば自
己のクロック値を全てのプロセッサに送出する。またク
ロックを受信したプロセッサでは受信した全てのクロッ
ク値とクロック値を受信した自プロセッサの時刻との差
分をとり、その差分の平均値Δによりクロックの調整を
行なうものである。

即ち、Δが正ならば自クロック値にΔを加算し、Δが負
ならば自クロックをΔだけ停止させる。ここで、全プロ
セッサ数をｎとし、ｖ＝１をとる確率をｍ／ｎとなるよ
うにセットすると、１回の制御あたり平均ｍ個のプロセ
ッサが自己のクロックを全プロセッサに送出することに
なる。各プロセッサではこの平均ｍ個のプロセッサから
のクロック値の平均値に自分のクロック値をあわせるこ
とになる。

例えば各プロセッサのクロック値が第３図に示すような
値をとっている場合について本発明の詳細な説明する。

このとき、各プロセッサは各自の時計がに００を指すと
きに変数Ｖの値を選択し制御を開始するものとする。ま
た、確率２１５でｖ＝１を、確率３１５でｖ＝０を選ぶ
ものとする。いま、プロセッサ３０１とプロセッサ３０
２がｖ＝１を選択し、他のプロセッサはｖ＝０を選択し
たものとする。通信遅延を無視すると、まずプロセッサ
３０１が最初に１＝００に到達し、そのクロック値（１
：００）をすべてのプロセッサに送出する。各プロセッ
サではプロセッサ３０１のクロック値を受信すると自己
のクロック値との差分をとる。差分値は、プロセッサ３
０１では０１　プロセッサ３０２では＋６、プロセッサ
３０３では＋４、プロセッサ３０４では＋８、プロセッ
サ３０５では＋２となる。

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

このようにすべてのプロセッサは、完全対等な立場にあ
り全く同一のアルゴリズムを実施する。

このランダムに選択されたプロセッサのみがそのクロッ
ク値を送出するので、従来に比べ通信量を削減すること
ができる。また、１つのプロセッサのみがシステムの時
刻を制御するのではなく、複数のプロセッサの平均時刻
でシステム時刻を制御することにより、耐障害性のある
時刻制御が可能となる。さらに、耐障害性の度合いは、
変数Ｖが１をとる確率を変えることで柔軟に制御するこ
とができる。

（発明の詳細な説明） 第１図（ａ）、（ｂ）、（ｃ）に本発明の方式を実現す
るために各プロセッサにて実行される制御の一フローチ
ャート例を示す。第１図（ａ）はクロック情報の送信制
御を示すフローチャート例であり、第１図（ｂ）はクロ
ック情報の受信制御を示すフローチャート例であり、第
１図（ｃ）はクロック受信処理の詳細を示すフローチャ
ート例である。まず第１図（ａ）の送信制御フローチャ
ートの説明を行なう。各プロセッサでは、ブロック１０
１にてクロック割込み１を検出すると、ブロック１０２
にてランダム変数Ｖを選択する。

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

ブロック１１３あるいは１１４の処理が終了すると、ブ
ロック１０１に戻り、次の周期でのクロック制御を開始
するためのクロック割込み１を待つ。

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

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

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

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

【図面の簡単な説明】

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

Claims (1)

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