並行データ構造

コンピュータサイエンスにおいて、並行データ構造（共有データ構造とも呼ばれる）は、コンピュータ上の複数のコンピューティングスレッド（またはプロセスやノード）によるアクセスと変更のために設計されたデータ構造であり、並行キュー、並行スタックなどがその例です。並行データ構造は通常、共有メモリと呼ばれる抽象的なストレージ環境に存在すると考えられており、物理的には密結合または分散ストレージモジュールのコレクションとして実装される場合があります。^{[1] [2]}

並列または分散コンピューティング環境での使用を意図した並行データ構造は、単一プロセッサマシンでの使用を意図した「シーケンシャル」データ構造とはいくつかの点で異なります。^{[3]最も顕著なのは、シーケンシャル環境では、}安全プロパティを提供することで、データ構造のプロパティを指定し、それらが正しく実装されていることを確認することです。並行環境では、仕様では 実装が提供する必要がある活性プロパティも記述する必要があります。安全プロパティは通常、悪いことが決して起こらないことを示し、活性プロパティは良いことが起こり続けることを示します。これらのプロパティは、たとえば線形時相論理を使用して表現できます。

活性要件のタイプは、データ構造を定義する傾向があります。メソッド呼び出しは、ブロッキングまたは非ブロッキングにすることができます。データ構造は、どちらかのタイプに限定されず、一部のメソッド呼び出しがブロッキングで、他のメソッド呼び出しが非ブロッキングである組み合わせを許可できます (例は、Java 並行性ソフトウェア ライブラリにあります)。

並行データ構造の安全性特性は、異なるスレッドによって呼び出されるメソッドの多くの可能なインターリーブを前提とした動作を捉える必要があります。インターリーブのない順次設定で抽象データ構造がどのように動作するかを指定することは非常に直感的です。したがって、並行データ構造の安全性特性を議論するための多くの主流のアプローチ（直列化可能性、線形化可能性、順次一貫性、静止一貫性など^[3]）は、構造の特性を順次指定し、その並行実行を順次実行のコレクションにマッピングします。

安全性と活性特性を保証するために、並行データ構造では通常 (常にではないが)、スレッドが同時にデータにアクセスし、変更を要求した結果について合意に達することができるようにする必要があります。このような合意をサポートするために、並行データ構造は、 複数のスレッドが合意に達することができる最新のマルチプロセッサ マシンで使用できる特別なプリミティブ同期操作 (同期プリミティブを参照)を使用して実装されます。この合意は、ロックを使用してブロッキング方式で達成することも、ロックを使用せずに非ブロッキング方式で達成することもできます。並行データ構造の設計に関する理論は多岐にわたります (参考文献を参照)。

並行データ構造は、順次データ構造に比べて設計および正確性の検証が非常に困難です。

この追加の困難の主な原因は同時実行性であり、スレッドは完全に非同期であると考えなければならないという事実によってさらに悪化します。つまり、スレッドはオペレーティング システムのプリエンプション、ページ フォールト、割り込みなどの影響を受けます。

今日のマシンでは、プロセッサとメモリのレイアウト、メモリ内のデータのレイアウト、マルチプロセッサアーキテクチャのさまざまな要素の通信負荷がすべてパフォーマンスに影響します。さらに、正確性とパフォーマンスの間には緊張関係があります。パフォーマンスの向上を目指すアルゴリズムの強化により、正しいデータ構造の実装を設計および検証することがより困難になることがよくあります。^[4]

パフォーマンスの重要な尺度はスケーラビリティであり、これは実装の高速化によって表されます。高速化は、アプリケーションが実行中のマシンをどれだけ効率的に使用しているかの尺度です。P 個のプロセッサを搭載したマシンでは、高速化は、単一プロセッサでの構造実行時間と P 個のプロセッサでの構造実行時間の比率です。理想的には、線形の高速化が望まれます。つまり、P 個のプロセッサを使用したときに P の高速化を達成したいのです。P とともに高速化が増加するデータ構造は、スケーラブルと呼ばれます。並行データ構造のパフォーマンスをどの程度拡張できるかは、アムダールの法則と呼ばれる式と、そのより洗練されたバージョンであるグスタフソンの法則によって表されます。

同時データ構造のパフォーマンスに関する重要な問題は、メモリ競合のレベルです。これは、複数のスレッドが同時にメモリ内の同じ場所にアクセスしようとすることで発生する、メモリとの間のトラフィックのオーバーヘッドです。この問題は、ロックがメモリへのアクセスを制御するブロッキング実装で最も深刻です。ロックを取得するには、スレッドはその場所の変更を繰り返し試行する必要があります。キャッシュ コヒーレント マルチプロセッサ (プロセッサがローカル キャッシュを持ち、ハードウェアによって更新され、最新の格納値との一貫性が保たれるプロセッサ) では、場所の変更試行ごとに長い待機時間が発生し、ロック取得の試行が失敗した場合に発生する追加のメモリ トラフィックによって状況が悪化します。

• Java 並行性(JSR 166)
• Java コンカレントマップ

• ナンシー・リンチ「分散コンピューティング」
• Hagit Attiyaと Jennifer Welch 著「分散コンピューティング: 基礎、シミュレーション、高度なトピック、第 2 版」
• Doug Lea、「Java での並行プログラミング: 設計原則とパターン」
• Maurice HerlihyとNir ​​Shavit、「マルチプロセッサ プログラミングの技法」
• Mattson、Sanders、Massingil「並列プログラミングのパターン」

• 並列コンピューティングのためのマルチスレッド データ構造、パート 1 (並行データ構造の設計)、Arpan Sen 著
• 並列コンピューティングのためのマルチスレッド データ構造: パート 2 (ミューテックスを使用しない並行データ構造の設計)、Arpan Sen 著
• libcds – ロックフリーコンテナと安全なメモリ再利用スキーマの C++ ライブラリ
• Synchronobench – ロックフリー、ロックベース、TM ベース、RCU/COW ベースのデータ構造の C/C++ および Java ライブラリとベンチマーク。