並行性：共有状態で生活する6つの方法

マルチスレッドプログラミングには多くの困難がありますが、その主なものは、共有状態の操作と提供されたカーネルの効率的な使用です。 コアの使用については、次の記事で説明します。



マルチスレッド環境での共有状態では、すべての困難を引き起こす2つのポイントがあります。 レースの状態と変更の可視性です。 競合状態では、スレッドが同時に状態を変更し、非決定的な動作を引き起こします。 また、可視性の問題は、あるストリームのデータを変更した結果が別のストリームから見えなくなる可能性があることです。 この記事では、これらの問題に対処する6つの方法について説明します。



すべての例はJavaで提供されていますが、それらにはコメントが含まれており、Javaに精通していないプログラマーに明確になることを願っています。 この記事はレビュー用であり、網羅的なものではありません。 同時に、用語とステートメントのより詳細な説明を提供するリンクで満たされています。

共有状態

フィボナッチ数の計算の例について、共有状態での作業を示します。

計算の式は次のとおりです。

f(0) = 0 f(1) = 1 f(n) = f(n - 1) + f(n - 2) , n >= 2
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

まず、インターフェイスを定義します。

 public interface FibonacciGenerator<T> { /** *    */ T next(); /** *     */ public T val(); }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

クラスは、 FibonacciGenerator



インターフェースを実装します。 次の番号を提供するには、前の2つの番号を保存する必要があることが式からわかります。これは、競合が行われる共有状態になります。 実装はスレッドセーフでなければなりません。 つまり、同時消費者数に関係なく、不変量を保持し、契約を順守します。 それでは、始めましょう。

ロック

マルチスレッド環境でクラスを正しく機能させるための最初の方法は、 ロックを使用して、すべてのメソッドの同期を宣言することです。 例は、 Vectorクラスです。

 public class IntrinsicLock implements FibonacciGenerator<BigInteger> { private BigInteger curr = BigInteger.ONE; private BigInteger next = BigInteger.ONE; @Override public synchronized BigInteger next() { BigInteger result = curr; curr = next; next = result.add(next); return result; } @Override public synchronized BigInteger val() { return curr; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最小限の労力で、マルチスレッド環境で正しく動作するクラスを取得しました。 まず、パフォーマンスを犠牲にします。 クラスのパフォーマンスは、シングルスレッド環境で起動された場合と同じです。 さらに、ロックを使用すると、 デッドロック 、 ライブ ロックなどの問題が発生します。

きめ細かいロック

次の方法は、構造をパーツに分割し、共有状態での作業が発生するセクションのみをロックすることです。 このアプローチの例はoncurrentHashMapです。 その中で、すべてのデータはいくつかの部分に分割されます。 アクセスすると、その部分のみがブロックされ、その変更は現在行われています。 StampedLock（java 8） 、 ReadWriteLockなど、より機能的なロックを使用するオプションもあります。 正しいアルゴリズムと実装により、より高いレベルの並列性が得られます。 ReadWriteLockを使用した例：

 public class FineGrainedLock implements FibonacciGenerator<BigInteger> { private final ReadWriteLock lock = new ReentrantReadWriteLock(); private BigInteger curr = BigInteger.ONE; private BigInteger next = BigInteger.ONE; @Override public BigInteger next() { BigInteger result; lock.writeLock().lock(); try { //     result = curr; curr = next; next = result.add(next); return result; } finally { lock.writeLock().unlock(); } } @Override public BigInteger val() { lock.readLock().lock(); try { //   write lock // `    return curr; } finally { lock.readLock().unlock(); } } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

クラスを改善し、読み取りスループットを高めました。 このような実装には、ロックのマイナス面がすべてあります。 さらに、マイナスから、アルゴリズムがより複雑になり（作業のロジックに関連しないノイズが追加された）、誤った実装の可能性が増加したことが追加されました。

ロックフリーアルゴリズム

ロックの使用には、パフォーマンスと正確性に関する多くの問題が伴います。 ノンブロッキングアルゴリズムの形で代替があります 。 このようなアルゴリズムは、プロセッサによって提供されるアトミック操作に基づいています。 例は、ConcurrentHashMapのgetメソッドです。 非ブロッキングアルゴリズムを記述するには、既存の非ブロッキングクラスを使用するのが理にかなっています： ConcurrentLinkedQueue 、ConcurrentHashMapなど。 クラスのノンブロッキング実装を作成します。

 public class LockFree implements FibonacciGenerator<BigInteger> { //      private static class State { final BigInteger next; final BigInteger curr; public State(BigInteger curr, BigInteger next) { this.next = next; this.curr = curr; } } //     private final AtomicReference<State> atomicState = new AtomicReference<>( new State(BigInteger.ONE, BigInteger.ONE)); public BigInteger next() { BigInteger value = null; while (true) { //    State state = atomicState.get(); //         value = state.curr; //    State newState = new State(state.next, state.curr.add(state.next)); //         //   ,     , //      if (atomicState.compareAndSet(state, newState)) {break;} } return value; } @Override public BigInteger val() { return atomicState.get().curr; } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

このアプローチの利点のうち、ブロッキングアルゴリズムと比較してパフォーマンスが向上することは注目に値します。 また、同様に重要なことは、 ロックの欠陥を取り除くことです。 欠点は、ノンブロッキングアルゴリズムを考え出すのがはるかに難しいことです。

ソフトウェアトランザクションメモリ

ノンブロッキングアルゴリズムに代わるものは、 ソフトウェアトランザクションメモリの使用です。 その使用法は、データベースを操作するときのトランザクションの使用法に似ています。 コンセプトは非常に新しく（1995）、一般的な言語の中でネイティブサポートはClojureでのみ行われます。 ライブラリレベルのSTMサポートは、Javaを含む多くの言語で利用できます。 Akkaプロジェクトの一部として実装されたSTMを使用します。

 public class STM implements FibonacciGenerator<BigInteger> { //      //         private final Ref<BigInteger> curr = new Ref<>(BigInteger.ONE); private final Ref<BigInteger> next = new Ref<>(BigInteger.ONE); @Override public BigInteger next() { //   return new Atomic<BigInteger>() { //    //   I (https://en.wikipedia.org/wiki/ACID) @Override public BigInteger atomically() { //      BigInteger result = curr.get(); //      curr.set(next.get()); next.set(result.add(next.get())); //       // .  ,   ,   //      . //   ,     . return result; } //    }.execute(); } @Override public BigInteger val() { //    return curr.get(); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

コードは理解しやすく、非ブロッキングアルゴリズムとロックの使用によって生じるノイズはありません。 しかし、STMはライターよりもリーダーの方が多い場合に優れたパフォーマンスを発揮するため、生産性は低く、適用性は限られています。

不変性

可変であるという事実と状態を共有する問題。 つまり、クラスimmutableを設計することで、スレッドセーフになるため、制限なしでマルチスレッド環境で作業できます。 ただし、メモリのコストは非常に高くなる可能性があるため、不変のデータ構造には機能的 な アプローチと特別なデータ構造が必要になることがよくあります 。

 public class Immutable { private final BigInteger next; //   public final BigInteger val; private Immutable(BigInteger next, BigInteger val) { this.next = next; this.val = val; } public Immutable next() { return new Immutable(val.add(next), next); } public static Immutable first() { return new Immutable(BigInteger.ONE, BigInteger.ONE); } }
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

お気づきのように、クラスインターフェイスは変更されており、これを操作するには他の方法が必要です。

孤立した可変性

オブジェクトの分離された可変性の考え方は、オブジェクトへのアクセスは常に単一のスレッドに制限されるということです。 したがって、マルチスレッドプログラムに特有の問題は発生しません。 このアプローチでは、アクターモデルを使用します。 アクターは、可変の状態と動作を持つオブジェクトに似たエンティティです。 アクターの相互作用は、非同期メッセージングを通じて発生します。 メッセージは不変であり、アクターは一度に1つのメッセージを処理します。 メッセージ処理の結果は、動作、状態、およびその他のアクションの変化です。 アクターの使用例については、次の記事で説明します。

まとめ

それぞれのアプローチにはマイナス面とプラス面があり、普遍的なアドバイスはできません。

Javaで最もよく使用されるアプローチである、きめの細かいロックとノンブロッキングアルゴリズムの組み合わせ。 Clojureでは、反対はトランザクションメモリと不変のデータ構造です。 私の意見では、トランザクションメモリは有望なツールです（ガベージコレクションとの類似性を独自に引き出すことを読者に提案します）。 次回システム、モジュール、またはクラスを設計するときに、この記事で説明したアプローチを思い出して、自分に合ったアプローチを選択してください。



ご清聴ありがとうございました。 コメントや提案を待っています。