1. 序章

このチュートリアルでは、非ブロッキングデータ構造とは何か、およびそれらがロックベースの同時データ構造の重要な代替手段である理由を学習します。

まず、障害物なし、ロックなし、待機なしなどの用語について説明します。

次に、 CAS （コンペアアンドスワップ）のような非ブロッキングアルゴリズムの基本的な構成要素を見ていきます。

第三に、Javaでのロックフリーキューの実装を見て、最後に、wait-freedomを実現する方法の概要を説明します。

2. ロック対飢餓

まず、ブロックされたスレッドと飢えたスレッドの違いを見てみましょう。

上の図では、スレッド2がデータ構造のロックを取得しています。 スレッド1もロックを取得しようとすると、スレッド2がロックを解放するまで待機する必要があります。 ロックを取得する前に続行しません。 ロックを保持している間にスレッド2を一時停止すると、スレッド1は永久に待機する必要があります。

次の図は、スレッドの枯渇を示しています。

ここで、スレッド2はデータ構造にアクセスしますが、ロックを取得しません。 スレッド1は同時にデータ構造へのアクセスを試み、同時アクセスを検出してすぐに戻り、操作を完了できなかった（赤）ことをスレッドに通知します。 その後、スレッド1は、操作の完了に成功するまで再試行します（緑色）。

このアプローチの利点は、ロックが不要なことです。 ただし、スレッド2（または他のスレッド）がデータ構造に頻繁にアクセスする場合、スレッド1は最終的に成功するまで、多数の試行が必要になる可能性があります。 これを飢餓と呼びます。

後で、コンペアアンドスワップ操作がどのように非ブロッキングアクセスを実現するかを見ていきます。

3. 非ブロッキングデータ構造のタイプ

非ブロッキングデータ構造の3つのレベルを区別できます。

3.1. 障害物なし

障害物のない自由は、非ブロッキングデータ構造の最も弱い形式です。 ここでは、他のすべてのスレッドが中断された場合にのみ、スレッドの進行が保証される必要があります。

より正確には、他のすべてのスレッドが中断されている場合、スレッドは飢餓状態を継続しません。 これは、その意味でロックを使用することとは異なります。つまり、スレッドがロックを待機していて、ロックを保持しているスレッドが中断された場合、待機中のスレッドは永久に待機します。

3.2. ロックフリー

データ構造は、いつでも少なくとも1つのスレッドが続行できる場合にロックの自由を提供します。 他のすべてのスレッドが不足している可能性があります。 障害物のない自由との違いは、スレッドが中断されていなくても、少なくとも1つの非飢餓スレッドがあることです。

3.3. 待ち時間なし

データ構造は、ロックフリーであり、すべてのスレッドが有限のステップ数の後に進むことが保証されている場合、つまり、スレッドが「不当に大きな」ステップ数に飢えない場合、待機はありません。

3.4. 概要

これらの定義をグラフィカルな表現で要約してみましょう。

画像の最初の部分は、他のスレッド（下部の黄色）を一時停止するとすぐにスレッド1（上部のスレッド）が進むことができるため（緑色の矢印）、障害物のないことを示しています。

真ん中の部分はロックの自由を示しています。 少なくともスレッド1は進行できますが、他のスレッドは飢えている可能性があります（赤い矢印）。

最後の部分は待機の自由を示しています。 ここでは、スレッド1が一定期間の飢餓（赤い矢印）の後で続行できること（緑の矢印）を保証します。

4. ノンブロッキングプリミティブ

このセクションでは、データ構造に対してロックフリー操作を構築するのに役立つ3つの基本的な操作について説明します。

4.1. コンペアアンドスワップ

ロックを回避するために使用される基本的な操作の1つは、コンペアアンドスワップ（CAS）操作です。

コンペアアンドスワップの考え方は、メインメモリから変数の値をフェッチしたときと同じ値がまだある場合にのみ変数が更新されるというものです。 CASは不可分操作です。つまり、フェッチと更新を一緒に行うことは1つの操作です：

ここでは、両方のスレッドがメインメモリから値3をフェッチします。 スレッド2は成功し（緑色）、変数を8に更新します。 スレッド1による最初のCASは、値がまだ3であることを期待しているため、CASは失敗します（赤）。 したがって、スレッド1は値を再度フェッチし、2番目のCASは成功します。

ここで重要なのは、CASはデータ構造のロックを取得せず、更新が成功した場合は true を返し、それ以外の場合はfalseを返すことです。

次のコードスニペットは、CASの仕組みの概要を示しています。

volatile int value;

boolean cas(int expectedValue, int newValue) {
    if(value == expectedValue) {
        value = newValue;
        return true;
    }
    return false;
}

期待値がまだある場合にのみ新しい値で値を更新します。それ以外の場合は、falseを返します。 次のコードスニペットは、CASを呼び出す方法を示しています。

void testCas() {
    int v = value;
    int x = v + 1;

    while(!cas(v, x)) {
        v = value;
        x = v + 1;
    }
}

CAS操作が成功するまで、つまり true が返されるまで、値を更新しようとします。

ただし、スレッドが飢餓状態でスタックする可能性があります。 これは、他のスレッドが同じ変数に対して同時にCASを実行する場合に発生する可能性があるため、特定のスレッドで操作が成功することはありません（または、成功するのに不当な時間がかかります）。 それでも、 compare-and-swap が失敗した場合は、別のスレッドが成功したことがわかります。したがって、ロックの自由に必要なグローバルな進行も保証します。

ロックを使用せずに真にアトミックな操作にするために、ハードウェアはコンペアアンドスワップをサポートする必要があることに注意することが重要です。

Javaは、クラスsun.misc.Unsafeにcompare-and-swapの実装を提供します。 ただし、ほとんどの場合、このクラスを直接使用するのではなく、原子変数を使用する必要があります。

さらに、コンペアアンドスワップはABA問題を防ぎません。 これについては、次のセクションで説明します。

4.2. ロードリンク/ストア-条件付き

コンペアアンドスワップの代わりに、 load-link /store-conditionalがあります。 まず、コンペアアンドスワップに戻りましょう。 これまで見てきたように、CASは、メインメモリの値が期待どおりの値である場合にのみ値を更新します。

ただし、CASは、値が変更され、その間に以前の値に戻った場合にも成功します。

次の画像は、この状況を示しています。

スレッド1とスレッド2はどちらも、変数の値である3を読み取ります。 次に、スレッド2はCASを実行し、変数を8に設定することに成功します。 次に、スレッド2はCASを実行して、変数を3に戻します。これも成功します。 最後に、スレッド1は値3を期待してCASを実行し、変数の値がその間に2回変更された場合でも、成功します。

これはABA問題と呼ばれます。 もちろん、ユースケースによっては、この動作は問題にならない場合があります。 ただし、他の人には望ましくない場合があります。 Javaは、 load-link /store-conditionalとAtomicStampedReferenceクラスの実装を提供します。

4.3. フェッチアンドアッド

もう1つの方法は、フェッチアンドアッドです。 この操作は、メインメモリ内の変数を指定された値だけインクリメントします。 繰り返しになりますが、重要な点は、操作がアトミックに行われることです。つまり、他のスレッドが干渉することはありません。

Javaは、そのアトミッククラスにfetch-and-addの実装を提供します。 例としては、 AtomicInteger.incrementAndGet（）があります。これは、値をインクリメントして新しい値を返します。 AtomicInteger.getAndIncrement（）は、古い値を返し、値をインクリメントします。

5. 複数のスレッドからリンクされたキューにアクセスする

2つ（またはそれ以上）のスレッドが同時にキューにアクセスする問題をよりよく理解するために、リンクされたキューと2つのスレッドが要素を同時に追加しようとしているところを見てみましょう。

ここで説明するキューは、二重にリンクされたFIFOキューであり、最後の要素（L）の後に新しい要素を追加し、変数tailがその最後の要素を指します。

新しい要素を追加するには、スレッドは次の3つの手順を実行する必要があります。1）次の要素へのポインタを null に設定して、新しい要素（NおよびM）を作成します。 2）前の要素への参照がLを指し、Lの次の要素への参照がN（それぞれM）を指すようにします。 3） tail がN（それぞれM）を指すようにします。

2つのスレッドがこれらの手順を同時に実行すると、何がうまくいかない可能性がありますか？ 上の図のステップがABCDまたはACBDの順序で実行される場合、LとtailはMを指します。 Nはキューから切断されたままになります。

ステップがACDBの順序で実行される場合、 tail はNを指し、LはMを指します。これにより、キューに不整合が発生します。

もちろん、この問題を解決する1つの方法は、1つのスレッドにキューのロックを取得させることです。 次の章で説明する解決策は、前に見たCAS操作を使用して、ロックフリー操作を使用して問題を解決します。

6. Javaのノンブロッキングキュー

Javaの基本的なロックフリーキューを見てみましょう。 まず、クラスメンバーとコンストラクターを見てみましょう。

public class NonBlockingQueue<T> {

    private final AtomicReference<Node<T>> head, tail;
    private final AtomicInteger size;

    public NonBlockingQueue() {
        head = new AtomicReference<>(null);
        tail = new AtomicReference<>(null);
        size = new AtomicInteger();
        size.set(0);
    }
}

重要な部分は、ヘッドとテールの参照をAtomicReferencesとして宣言することです。これにより、これらの参照の更新がアトミック操作であることが保証されます。 Javaのこのデータ型は、必要なコンペアアンドスワップ操作を実装します。

次に、Nodeクラスの実装を見てみましょう。

private class Node<T> {
    private volatile T value;
    private volatile Node<T> next;
    private volatile Node<T> previous;

    public Node(T value) {
        this.value = value;
        this.next = null;
    }

    // getters and setters 
}

ここで重要なのは、前のノードと次のノードへの参照をvolatileとして宣言することです。 これにより、これらの参照が常にメインメモリで更新されるようになります（したがって、すべてのスレッドに直接表示されます）。 実際のノード値についても同じです。

6.1. ロックフリー追加

ロックフリーのadd操作により、複数のスレッドが同時に新しい要素を追加したい場合でも、テールに新しい要素を追加し、キューから切断されないようにします。

public void add(T element) {
    if (element == null) {
        throw new NullPointerException();
    }

    Node<T> node = new Node<>(element);
    Node<T> currentTail;
    do {
        currentTail = tail.get();
        node.setPrevious(currentTail);
    } while(!tail.compareAndSet(currentTail, node));

    if(node.previous != null) {
        node.previous.next = node;
    }

    head.compareAndSet(null, node); // for inserting the first element
    size.incrementAndGet();
}

注意を払うべき重要な部分は、強調表示された線です。 CAS操作がテールの更新に成功するまで、新しいノードをキューに追加しようとします。テールは、新しいノードを追加したテールと同じである必要があります。

6.2. ロックフリーget

add-operationと同様に、lock-free get-operationは、最後の要素を確実に戻し、テールを現在の位置に移動します。

public T get() {
    if(head.get() == null) {
        throw new NoSuchElementException();
    }

    Node<T> currentHead;
    Node<T> nextNode;
    do {
        currentHead = head.get();
        nextNode = currentHead.getNext();
    } while(!head.compareAndSet(currentHead, nextNode));

    size.decrementAndGet();
    return currentHead.getValue();
}

繰り返しますが、注意を払うべき重要な部分は強調表示された線です。 CAS操作により、その間に他のノードが削除されていない場合にのみ、現在のヘッドを移動できます。

Javaは、非ブロッキングキューであるConcurrentLinkedQueueの実装をすでに提供しています。 これは、Mからのロックフリーキューの実装です。 マイケルとL。 スコットはこの論文で説明しました。 ここで興味深い補足として、Javaのドキュメントには、待機なしキューであり、実際にはロックなしであると記載されています。 Java 8のドキュメントでは、実装ロックフリーが正しく呼び出されています。

7. 待機なしのキュー

これまで見てきたように、上記の実装はロックフリーですが、待機フリーではありません。 addメソッドとgetメソッドの両方のwhileループは、アクセスするスレッドが多数ある場合、長時間（または、可能性は低いですが、永久に）ループする可能性があります。列。

どうすれば待機の自由を実現できますか？ 一般に、待機なしのアルゴリズムの実装は非常に注意が必要です。 興味のある読者には、このペーパーを参照してください。このペーパーでは、待機なしのキューについて詳しく説明しています。 この記事では、キューの待機なしの実装にアプローチする方法の基本的な考え方を見てみましょう。

待機のないキューでは、すべてのスレッドが（有限のステップ数の後に）確実に進行する必要があります。 つまり、addメソッドとgetメソッドの while ループは、特定のステップ数の後に成功する必要があります。

これを実現するために、すべてのスレッドにヘルパースレッドを割り当てます。 そのヘルパースレッドがキューに要素を追加することに成功した場合、別の要素を挿入する前に、他のスレッドがその要素を挿入するのを支援します。

ヘルパースレッドにはヘルパー自体があり、スレッドのリスト全体ですべてのスレッドにヘルパーがあるため、すべてのスレッドが1回の挿入を行った後、スレッドが最後に挿入に成功することを保証できます。 次の図は、そのアイデアを示しています。

もちろん、スレッドを動的に追加または削除できると、事態はさらに複雑になります。

8. 結論

この記事では、ノンブロッキングデータ構造の基本について説明しました。 コンペアアンドスワップのようなさまざまなレベルと基本的な操作について説明しました。

次に、Javaでのロックフリーキューの基本的な実装について説明しました。 最後に、wait-freedomを実現する方法のアイデアについて概説しました。

この記事のすべての例の完全なソースコードは、GitHubでから入手できます。