メモリ共有型マルチプロセッサシステムにおける無待機アルゴリズムに関する研究

メモリ共有型マルチプロセッサシステムにおける無待機アルゴリズムに関して研究を行った。複数のプロセスが協調動作を行うためのアルゴリズムにおいて、各プロセスが他のプロセスの動作速度に関わらす有限回のステップで処理を完了することを保証するとき、そのアルゴリズムは無待機であるという。無待機アルゴリズムは自プロセス以外のプロセスが故障して停止しても正しく動作することから、高い故障耐性を持つアルゴリズムとして注目されている。本研究では、無待機アルゴリズムにの研究に関して、主に以下の2つの成果を得た。1. 自己安定無待機時計合わせプロトコルに関する研究全プロセスが大域パルスを共有する同期式共有メモリシステムで、各プロセスが個別に管理する局所時計を同期させるプロトコルに関する研究を行った。これまで、同期に要するパルス数である同期時間が最適であるプロトコルを提案していたが、今年度はこの最適性を損なうことなく自己安定性をも有するプロトコルを提案した。2. 共有オブジェクトの無待機な実現に関する研究メッセージ交換システムにおいて、複数のプロセスが同時に利用することのできる共有オブジェクトを実現する研究を行った。共有オブジェクトに対する操作を開始してから応答が得られるまでの応答時間に関して、効率の良い共有レジスタおよび一般の共有オブジェクトの実現、および、応答時間の下界に関する結果を示した。

メモリ共有型マルチプロセッサシステムにおける無待機アルゴリズムに関して研究を行った。複数のプロセスが協調動作を行うためのアルゴリズムにおいて、各プロセスが他のプロセスの動作速度に関わらす有限回のステップで処理を完了することを保証するとき、そのアルゴリズムは無待機であるという。無待機アルゴリズムは自プロセス以外のプロセスが故障して停止しても正しく動作することから、高い故障耐性を持つアルゴリズムとして注目されている。本研究では、無待機アルゴリズムにの研究に関して、主に以下の2つの成果を得た。1. 自己安定無待機時計合わせプロトコルに関する研究全プロセスが大域パルスを共有する同期式共有メモリシステムで、各プロセスが個別に管理する局所時計を同期させるプロトコルに関する研究を行った。これまで、同期に要するパルス数である同期時間が最適であるプロトコルを提案していたが、今年度はこの最適性を損なうことなく自己安定性をも有するプロトコルを提案した。2. 共有オブジェクトの無待機な実現に関する研究メッセージ交換システムにおいて、複数のプロセスが同時に利用することのできる共有オブジェクトを実現する研究を行った。共有オブジェクトに対する操作を開始してから応答が得られるまでの応答時間に関して、効率の良い共有レジスタおよび一般の共有オブジェクトの実現、および、応答時間の下界に関する結果を示した。