共有メモリマルチプロセッサシステムおける
無待機時計合わせプロトコルに関する研究

守屋 宣 (9551113)


自律的に動作する複数のプロセッサと共有メモリからなるシステムのことを 共有メモリマルチプロセッサシステムと呼ぶ。 本発表では、 システム内の全プロセッサが大域パルスを共有する、 フェーズ内システムと呼ばれる 同期式マルチプロセッサシステムにおける無待機時計合わせプロトコル について考察する。

システム内の全プロセッサがそれぞれの局所時計を管理しているようなシステムにおいて、 故障が存在するにも関わらず局所時計を同期させ続ける問題を 時計合わせ問題は、多くの応用問題にとって重要であり、 またそれ自体も興味深い問題である。 特に、無待機時計合わせプロトコルとは、ある特定時間(同期時間と呼ぶ)以上 正常に動作し続けているすべてのプロセッサの局所時計が同期することを保証する プロトコルである。 無待機時計合わせプロトコルは、プロセッサが任意の時間動作を停止する居眠り故障に 耐性がある。

フェーズ内システムにおける無待機時計合わせプロトコルとしては、 DolevとWelchにより同期時間O(n2)(nはプロセッサ数)のプロトコルが 提案されていた。本発表では、 同期時間O(n)となる無待機時計合わせプロトコルを提案する。 フェーズ内システムにおける無待機時計合わせプロトコルの下界はΩ(n)であり、 本発表で提案するプロトコルは同期時間がオーダー的に最適であることが言える。