スレッドセーフなLIFOデータ構造の実装
1. 序章
このチュートリアルでは、スレッドセーフなLIFOデータ構造の実装のさまざまなオプションについて説明します。
LIFOデータ構造では、後入れ先出しの原則に従って要素が挿入および取得されます。 これは、最後に挿入された要素が最初に取得されることを意味します。
コンピュータサイエンスでは、スタックはそのようなデータ構造を指すために使用される用語です。
stack は、式の評価、元に戻る操作の実装など、いくつかの興味深い問題を処理するのに便利です。 同時実行環境で使用できるため、スレッドセーフにする必要がある場合があります。
2. スタックを理解する
基本的に、スタックは次のメソッドを実装する必要があります:
- push() –上部に要素を追加します
- pop() –最上位の要素をフェッチして削除します
- peek() –基になるコンテナから削除せずに要素をフェッチします
前に説明したように、コマンド処理エンジンが必要であると仮定しましょう。
このシステムでは、実行されたコマンドを元に戻すことが重要な機能です。
一般に、すべてのコマンドはスタックにプッシュされ、元に戻す操作を簡単に実装できます。
- pop()メソッドを使用して、最後に実行されたコマンドを取得します
- ポップされたコマンドオブジェクトでundo()メソッドを呼び出します
3. スタックのスレッドセーフを理解する
データ構造がスレッドセーフでない場合、同時にアクセスすると、競合状態になる可能性があります。
競合状態は、一言で言えば、コードの正しい実行がスレッドのタイミングとシーケンスに依存する場合に発生します。 これは主に、複数のスレッドがデータ構造を共有し、この構造がこの目的のために設計されていない場合に発生します。
JavaコレクションクラスArrayDequeから以下のメソッドを調べてみましょう。
public E pollFirst() {
int h = head;
E result = (E) elements[h];
// ... other book-keeping operations removed, for simplicity
head = (h + 1) & (elements.length - 1);
return result;
}
上記のコードで発生する可能性のある競合状態を説明するために、次のシーケンスで指定されているように、このコードを実行する2つのスレッドを想定します。
- 最初のスレッドは3行目を実行します:インデックス’head’に要素を持つ結果オブジェクトを設定します
- 2番目のスレッドは3行目を実行します:インデックス’head’に要素を持つ結果オブジェクトを設定します
- 最初のスレッドは5行目を実行します。インデックス’head’をバッキング配列の次の要素にリセットします
- 2番目のスレッドは5行目を実行します。インデックス’head’をバッキング配列の次の要素にリセットします
おっとっと! これで、両方の実行で同じ結果オブジェクトが返されます
このような競合状態を回避するために、この場合、他のスレッドが5行目の「head」インデックスのリセットを完了するまで、スレッドは最初の行を実行しないでください。 言い換えると、インデックス’head’の要素にアクセスし、インデックス’head’をリセットすることは、スレッドに対してアトミックに行われる必要があります。
明らかに、この場合、コードの正しい実行はスレッドのタイミングに依存するため、スレッドセーフではありません。
4. ロックを使用したスレッドセーフスタック
このセクションでは、スレッドセーフの具体的な実装のための2つの可能なオプションについて説明します。
特に、Javaについて説明します。 スタックスレッドセーフな装飾が施されています
どちらも、相互に排他的なアクセスにロックを使用します。
4.1. Javaスタックを使用する
Javaコレクションには、基本的にArrayListの同期バリアントであるVector に基づいた、スレッドセーフなStackのレガシー実装があります。
ただし、公式ドキュメント自体は、ArrayDequeの使用を検討することを提案しています。 したがって、あまり詳細には立ち入りません。
Java Stack はスレッドセーフで簡単に使用できますが、このクラスには大きな欠点があります。
- 初期容量の設定はサポートされていません
- すべての操作にロックを使用します。 これにより、シングルスレッド実行のパフォーマンスが低下する可能性があります。
4.2. ArrayDequeを使用する
Dequeインターフェースの使用は、必要なすべてのスタック操作を提供するため、LIFOデータ構造にとって最も便利なアプローチです。 ArrayDeque そのような具体的な実装の1つです
操作にロックを使用していないため、シングルスレッドの実行は問題なく機能します。 ただし、マルチスレッド実行の場合、これには問題があります。
ただし、同期デコレータを実装することはできます
このクラスを見てみましょう:
public class DequeBasedSynchronizedStack<T> {
// Internal Deque which gets decorated for synchronization.
private ArrayDeque<T> dequeStore;
public DequeBasedSynchronizedStack(int initialCapacity) {
this.dequeStore = new ArrayDeque<>(initialCapacity);
}
public DequeBasedSynchronizedStack() {
dequeStore = new ArrayDeque<>();
}
public synchronized T pop() {
return this.dequeStore.pop();
}
public synchronized void push(T element) {
this.dequeStore.push(element);
}
public synchronized T peek() {
return this.dequeStore.peek();
}
public synchronized int size() {
return this.dequeStore.size();
}
}
このソリューションには、さらに多くのメソッドが含まれているため、簡単にするためにDeque自体は実装されていないことに注意してください。
また、Guavaには SynchronizedDeque が含まれています。これは、装飾されたArrayDequeueの本番環境に対応した実装です。
5. ロックフリーのスレッドセーフスタック
ConcurrentLinkedDeque は、Dequeインターフェースのロックフリー実装です。 この実装は、効率的なロックフリーアルゴリズムを使用しているため、完全にスレッドセーフです。
ロックフリーの実装は、ロックベースの実装とは異なり、次の問題の影響を受けません。
- 優先順位の逆転–これは、優先順位の低いスレッドが優先順位の高いスレッドに必要なロックを保持している場合に発生します。 これにより、優先度の高いスレッドがブロックされる可能性があります
- Deadlocks –これは、異なるスレッドが同じリソースのセットを異なる順序でロックする場合に発生します。
さらに、ロックフリーの実装には、シングルスレッド環境とマルチスレッド環境の両方での使用に最適な機能がいくつかあります。
- 非共有データ構造およびシングルスレッドアクセスの場合、パフォーマンスはArrayDequeと同等になります。
- 共有データ構造の場合、パフォーマンスは、同時にアクセスするスレッドの数によって異なります。
また、使いやすさの点では、どちらも Deque インターフェイスを実装しているため、ArrayDequeと同じです。
6. 結論
この記事では、スタックデータ構造と、コマンド処理エンジンや式エバリュエーターなどのシステムの設計におけるその利点について説明しました。
また、Javaコレクションフレームワークのさまざまなスタック実装を分析し、それらのパフォーマンスとスレッドセーフのニュアンスについて説明しました。
いつものように、コード例はGitHubのにあります。