分散共有メモリ（DSM）を実装するための4つのアルゴリズムを徹底解説

共有メモリと分散共有メモリ（DSM）とは

共有メモリとは、複数のプログラムからアクセスできるメモリ領域のことです。共有メモリの概念は、プロセス間の通信手段を提供するとともに、冗長性の少ない効率的なメモリ管理を実現するために用いられます。

分散共有メモリ（Distributed Shared Memory、略称：DSM）は、この共有メモリの概念を分散システム上で実現したものです。DSMシステムは、ローカルな物理共有メモリを持たない疎結合システムにおいて、共有メモリモデルを実装します。この種のシステムでは、分散階層内のすべてのシステム（ノードとも呼ばれます）がアクセスできる仮想メモリ空間が提供されます。

DSM実装における主な課題

DSMを実装する際には、以下のような共通の課題に留意する必要があります。

• 共有メモリ上の遠隔地に格納されたデータのアドレス（位置）の追跡。
• リモートデータへの参照に伴う通信遅延や大きなオーバーヘッドの削減。
• DSM内で共有されるデータへの同時アクセスの制御。

これらの課題を踏まえて、分散共有メモリを実装するためのアルゴリズムが設計されています。代表的なものとして、次の4つのアルゴリズムがあります。

• 中央サーバ方式（Central Server Algorithm）
• マイグレーション方式（Migration Algorithm）
• 読み取りレプリケーション方式（Read Replication Algorithm）
• 完全レプリケーション方式（Full Replication Algorithm）

中央サーバ方式（Central Server Algorithm）

すべての共有データは中央サーバによって管理・維持されます。分散システム内の他のノードは、データの読み書きをサーバに要求し、サーバはその要求に応答して、確認応答（ACK）メッセージとともにデータへのアクセスや更新を提供します。

これらの確認応答メッセージは、サーバがデータ要求を処理した状態を通知するために使用されます。データが呼び出し元へ送信される際には、並行性を維持するためのデータのアクセス順序を示す番号が確認応答として返され、処理に失敗した場合はタイムアウトが返されます。

大規模な分散システムでは、複数のサーバが存在することもあります。その場合、サーバはアドレスまたはマッピング関数を使用して特定されます。

マイグレーション方式（Migration Algorithm）

名前の通り、マイグレーション方式はデータ要素の移動（マイグレーション）を行うアルゴリズムです。中央サーバが個々の要求に応答する代わりに、あるシステムが要求したデータを含むブロック全体がそのノードへ移動し、以降のアクセスや処理がそこで行われます。

このアルゴリズムは、同一のデータブロックに繰り返しアクセスする場合に特に有効であり、仮想メモリの概念との統合が可能であるという利点がありますが、対処すべき短所も存在します。

一度に共有データ要素へアクセスできるのは1つのノードのみで、ブロック全体がそのノードに移動します。また、ノードからの要求のたびにデータ項目が移動するため、スラッシングが発生しやすいという欠点もあります。

読み取りレプリケーション方式（Read Replication Algorithm）

読み取りレプリケーション方式では、アクセス対象となるデータブロックが複製（レプリケート）され、すべてのコピーに対して読み取り操作のみが許可されます。書き込み操作を行う場合は、すべてのコピーが更新されるまで、すべての読み取りアクセスが一時停止されます。

同時アクセスが許可されるため、システム全体のパフォーマンスが向上します。しかし、並行性を維持するために共有されているすべてのブロックを更新する必要があるため、書き込み操作のコストが高いという課題があります。また、一貫性を保つためには、データ要素のすべてのコピーを追跡しなければなりません。

完全レプリケーション方式（Full Replication Algorithm）

完全レプリケーション方式は、読み取りレプリケーション方式を拡張したものであり、ノードが共有ブロックに対して読み取りと書き込みの両方の操作を同時に実行できるようにしたものです。ただし、一貫性を維持するために、ノードによるアクセスは適切に制御されます。

すべてのノードによる同時アクセス時にデータの一貫性を維持するため、アクセス順序が管理されており、データに対する変更が行われるたびに、マルチキャストによって変更内容がすべてのデータコピーへ反映されます。