1.はじめに

  • コンピュータサイエンスでは、

    stack

    はそのようなデータ構造を指すのに使われる用語です。 **


2

Stacks


について

.

.

.

**

**


3

Stacks


でスレッドの安全性を理解する

  • データ構造がスレッドセーフではない場合、同時にアクセスすると、競合状態になる可能性があります** 。

簡単に言うと、競合状態は、コードの正しい実行がスレッドのタイミングと順序に依存する場合に発生します。これは主に複数のスレッドがデータ構造を共有し、この構造がこの目的のために設計されていない場合に発生します。

次のJava Collectionクラス

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」をにリセットします。

バッキング配列内の次の要素

おっとっと!これで、両方の実行は同じ結果object


_を返します。

_

このような競合状態を避けるため、この場合、他のスレッドが5行目の「head」インデックスのリセットを完了するまで、スレッドは最初の行を実行しないでください。つまり、インデックス「head」の要素にアクセスしてインデックス「head」をリセットすることは、スレッドに対してアトミックに行われるはずです。

明らかに、この場合、コードの正しい実行はスレッドのタイミングに依存するため、スレッドセーフではありません。

4.ロックを使ったスレッドセーフなスタック

このセクションでは、スレッドセーフ

stackの具体的な実装のための2つの可能なオプションについて説明します。

特に、Javaの


_Stack


とスレッドセーフな装飾の

ArrayDequeについて説明します。 _

両方とも相互に排他的なアクセスのためにhttps://www.baeldung.com/java-concurrent-locks[Locks]を使用します


_.

_

4.1. Javaの使い方

Stack

  • Javaコレクションは、基本的には

    ArrayList .

    ** の同期バリアントである

    Vector

    に基づいて、スレッドセーフhttps://www.baeldung.com/java-stack[

    Stack

    ]用のレガシー実装を持っています。

ただし、公式文書自体は

ArrayDeque

の使用を検討することを提案しています。それゆえ、私達はあまり詳細には入りません。

Javaの

Stack

はスレッドセーフで簡単に使用できますが、このクラスには大きな欠点があります。

  • 初期容量の設定はサポートされていません

  • すべての操作にロックを使用します。これはパフォーマンスを低下させる可能性があります

シングルスレッド実行用。

4.2.

ArrayDeque

を使う


  • Deque

    インタフェースを使用することは、必要なすべてのスタック操作を提供するため、LIFOデータ構造にとって最も便利なアプローチです。

    __

操作にロックを使用していないので、シングルスレッドの実行は問題なく動作します。しかし、マルチスレッド実行の場合、これは問題があります。

ただし、

ArrayDequeの同期デコレータを実装することもできます。これはJava Collection Frameworkの

Stack

クラスと同様に機能しますが、

Stack__クラスの重要な問題、初期容量設定の欠如は解決されています。

このクラスを見てみましょう。

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には

__https://google.github.io/guava/releases/snapshot/api/docs/com/google/common/collect/Queue.html #synchronizedDeque-java.util.Deque-[SynchronizedDeque]装飾された

ArrayDequeue.__のプロダクション対応の実装

5.ロックフリーのスレッドセーフスタック



ConcurrentLinkedDeque


は、

Deque

インタフェースのロックのない実装です。 ** この実装はhttp://www.cs.rochester.edu/~scott/papers/1996

PODC

queues.pdf[効率的なロックフリーアルゴリズム]を使用しているため、完全にスレッドセーフです。

ロックフリーの実装は、ロックベースの実装とは異なり、以下の問題の影響を受けません。

反転

] – 優先度の低いスレッドがロックを保持している場合に発生します。
優先順位の高いスレッドに必要です。これは高優先度を引き起こすかもしれません
ブロックするスレッド


デッドロック

– これは、異なるスレッドが同じセットをロックしたときに発生します。

順序が異なるリソース

それに加えて、ロックフリーの実装にはシングルスレッド環境とマルチスレッド環境の両方での使用に最適な機能がいくつかあります。

非共有データ構造およびシングルスレッドアクセスの場合

パフォーマンスは

ArrayDeque


と同等です

共有データ構造の場合、パフォーマンスは** によって異なります。

同時にアクセスするスレッド数** 。

そして使いやすさの点では、どちらも

Deque

インターフェースを実装しているので

ArrayDeque

と同じです。

6.まとめ

この記事では、

__stack

__data構造と、Command処理エンジンやExpressionエバリュエーターなどのシステム設計におけるその利点について説明しました。

また、Javaコレクションフレームワークのさまざまなスタック実装を分析し、それらのパフォーマンスとスレッドセーフなニュアンスについて説明しました。

いつもどおり、コード例はhttps://github.com/eugenp/tutorials/tree/master/core-java-collections[over on GitHub]にあります。