同期・並行クラスコンテナ

I. なぜ同期コンテナがあるのですか？

Javaのコレクション・コンテナ・フレームワークでは、主に4つのクラスが存在します。リスト、セット、キュー、マップです。

CollectionとMapはトップレベルのインタフェースで、List、Set、QueueはCollectionインタフェースを継承し、それぞれ配列、コレクション、キューというコンテナの3つの主要なクラスを表現していることに注意してください。

ArrayListとLinkedListはListインタフェースを、HashSetはSetインタフェースを、Deque（キューの先頭と末尾で入出操作ができる双方向キュー）はQueueインタフェースを継承し、PriorityQueueはQueueインタフェースを実装している。また、LinkedList（実際には双方向リンクリスト）もDequeインタフェースを実装している。

しかし、上記のコンテナはすべてノンスレッドセーフである。複数のスレッドがこれらのコンテナに同時にアクセスすると、問題が発生する可能性があります。そのため、プログラムを書く際には、プログラマが手動でこれらのコンテナへのアクセスを同期させなければならず、これらのコンテナを使用することは非常に不便です。そこで、Javaでは、ユーザが利用できるように同期用コンテナを用意しています。

II.Javaにおける同期型クラスコンテナ

Javaでは、同期コンテナは主に2つのカテゴリで構成されています。

<スパン 　　1) ベクター、スタック、ハッシュテーブル

　　2) Collectionsクラスで提供される静的ファクトリーメソッドで作成されるクラス

VectorはListインタフェースを実装しており、Vectorは実際にはArrayListに似た配列ですが、Vectorのメソッドはsynchronizedメソッド、つまり同期化対策です。Stackも同期化コンテナで、そのメソッドはsynchronizedで、実際にはVectorクラスから継承されています。HashTableはMapインタフェースを実装し、HashMapと非常に似ていますが、HashTableが同期化を実行し、HashMapには同期化は行われていないです。

<スパン Collectionsクラスは、ツールを提供するクラスである。トップレベルのインターフェイスであるCollectionsとは異なることに注意してください。Collectionsクラスには、コレクションやコンテナに対して、ソート、検索などの操作を行うためのメソッドが多数用意されている。最も重要なのは、次の画像に示すように、同期コンテナクラスを作成するための静的ファクトリーメソッドがいくつか提供されていることである。

これらの同期コンテナは、スレッドセーフを実現するためにsynchronizedを介して同期されるので、明らかに実行性能に影響を与えるに違いありません。

また、これらはすべてスレッドセーフですが、次の例のように使い方によっては、すべてのケースでスレッドセーフになるわけではありません。

public class Test {
    static Vector<Integer> vector = new Vector<Integer>();
    public static void main(String[] args) throws InterruptedException {
        while(true) {
            for(int i=0;i<10;i++)
                vector.add(i);
            Thread thread1 = new Thread(){
                public void run() {
                    for(int i=0;i<vector.size();i++)
                        vector.remove(i);
                };
            };
            Thread thread2 = new Thread(){
                public void run() {
                    for(int i=0;i<vector.size();i++)
                        vector.get(i);
                };
            };
            thread1.start();
            thread2.start();
            while(Thread.activeCount()>10) {
                 
            }
        }
    }
}

その結果、配列の添え字が境界外であるという実行時例外が発生します。Vectorはスレッドセーフなのに、なぜこのようなエラーが報告されるのでしょうか？単純に考えて、Vectorは一度に1つのスレッドしかアクセスできないことが保証されていますが、スレッドがある時点でこの文を実行したときの可能性を排除することはできないのです。

に対して ( int  i= 0 ;i<vector.size();i++)です。

     vector.get(i)です。

この時点でvectorのsizeメソッドが10を返し、iの値が9で、添え字が9の要素を取得しようとした時点で、別のスレッドが先にこの文を実行したとします。

に対して ( int  i= 0 ;i<vector.size();i++)です。

     vector.remove(i)を実行します。

添え字9の要素が削除され、その過程で前のスレッドはロックされているためvector.get(i)を実行できず、ブロッキング状態になって添え字9の要素が削除された後にこのスレッドがロックを取得するのを待っている状態になっています。そうすると、getメソッドで添え字9の要素にアクセスすることは、間違いなく問題になります。これは、プログラムロジック自体にスレッドセーフの問題があることを意味するので、スレッドセーフを確保するためには、以下のようにメソッド呼び出し側で追加の同期を行う必要があります。

public class Test {
    static Vector<Integer> vector = new Vector<Integer>();
    public static void main(String[] args) throws InterruptedException {
        while(true) {
            for(int i=0;i<10;i++)
                vector.add(i);
            Thread thread1 = new Thread(){
                public void run() {
                    synchronized (Test.class) { // perform additional synchronization
                        for(int i=0;i<vector.size();i++)
                            vector.remove(i);
                    }
                };
            };
            Thread thread2 = new Thread(){
                public void run() {
                    synchronized (Test.class) {
                        for(int i=0;i<vector.size();i++)
                            vector.get(i);
                    }
                };
            };
            thread1.start();
            thread2.start();
            while(Thread.activeCount()>10) {
                 
            }
        }
    }
}

III.Javaの並列クラスコンテナ

同期クラスコンテナの性能問題を解決するために、Java 1.5以降では並列コンテナが提供され、java.util.concurrentディレクトリ（通称：concurrentパッケージ）に配置されています。

3.1. コンカレントマップ

ConcurrentMapインターフェースには、2つの重要な実装があります。ConcurrentHashMap と ConcurrentSkipListMap である。ConcurrentHashMap はハッシュテーブル全体を複数のセグメントに分割し、セグメントごとに1つのロックを行うもので、主にロックセグメンテーション技術によりロックの粒度を小さくする。これにより、ロックの粒度が小さくなり、競合が減少するため、同時実行性が向上する。ConcurrentHashMap は読み込み操作に対して多くの最適化を行い、不変オブジェクトやメモリの可視性を確保する volatile などの並行処理技術を多用しているので、ほとんどの場合、読み込み操作でロックせずに正しい値を取得することができる。concurrencyLevel（デフォルト値は16）は並行処理レベルを示し、concurrencyLevelの2〜n乗以上のSegmentの数を決定するために使用される。例えば、concurrencyLevelが12, 13, 14, 15, 16の場合、Segmentの数は16（2の4乗）である。ConcurrencyLevelのSegmentが存在するため、ConcurrentHashMapの実際の同時アクセスはconcurrencyLevelに達することが理想的である。ConcurrencyLevelのスレッドがMapにアクセスする必要があり、アクセスする必要があるデータがたまたま異なるSegmentにある場合、これらのスレッドは（同じロックを奪い合う必要がないため）競合せずに自由にアクセスでき、同時アクセスの効果を得ることができます。このため、このパラメータはquot;concurrency level"と名付けられています。値を高くしすぎると無駄なスペースが発生し、低くしすぎると同時実行性が低下します。このようなチューニングの把握は、根本的な実装を深く理解し、継続的に実践することで初めて身につくものです。

3.2. CopyOnWirte コンテナ

Cope-On-Write、略してCOWは、コピーオンライトと呼ばれるプログラミングで使われる最適化戦略である。簡単に説明すると，変更操作を行う際に基礎となる配列をコピーし，変更操作が新しい配列に対して行われ，元の配列に対する同時読み取り操作を妨げないようにし，コピー変更完了後に元の配列参照を新しい配列に指し示すというものです．この利点は、現在のコンテナでは要素が追加されないため、ロックせずに同時読み出しが可能であることで、これも読み書きの分離の考え方と言えます。しかし、コピーオンライトのため、リアルタイムのデータは保証されず、究極の一貫性だけが保証されます。

CopyOnWriteの仕組みを実装したコンテナは、concurrentパッケージの下にCopyOnWriteArrayListとCopyOnWriteArraySetという2つのコンテナが存在する。

CopyOnWriteArrayListは、オブジェクトの配列のデータを格納するために、セット（）、追加（）、削除（）と他の操作を変更するためのロックReentrantLockに追加されます、変更操作の完了後にロックを解放する前に配列への参照を交換する、したがって、書き込み操作のスレッド安全性を確保します。

CopyOnWriteArraySetは実際にはCopyOnWriteArrayListですが、ただメソッド内の重複データを避けるために、これらの関数もCopyOnWriteArrayListで定義されており、CopyOnWriteArraySetにはCopyOnWriteArraySetのプロパティが入っており、それからメソッドのラッパーをしています。equalsメソッドを除いて、現在のクラスの他のすべての関数は、CopyOnWriteArrayListメソッドと呼ばれるので、厳密に言えば、書き込みのSet特性としてCopyOnWriteArrayListを使用することができます だから、技術的にはSetプロパティ（ただし抽象セットを継承していないだけ）で書き込み時のコピー配列としてCopyOnWriteArrayListを使用することができます。

CopyOnWirteコンテナの実装原理から、CopyOnWirteコンテナは読み書きの分離を保証しており、読み書きが少ないシナリオには非常に適しているが、書き込みが多いシナリオには適していないことは明らかである。

3.3. スレッドセーフなキュー

<スパン 並行プログラミングでは、スレッドセーフな待ち行列を使用する必要がある場合があります。スレッドセーフな待ち行列を実装したい場合、2つの方法があります。1つはブロッキングアルゴリズムを使用する方法、もう1つはノンブロッキングアルゴリズムを使用する方法です。ブロッキングアルゴリズムを用いたキューは、1つのロック（受信キューと送信キューに同じロック）または2つのロック（受信キューと送信キューに異なるロック）などで実装でき、ノンブロッキング実装は循環CASを用いて実装できる。java.util.concurrent.atomicパッケージ関連クラスはCAS実装である。

<スパン ConcurrentLinkedQueueは、高連続性シナリオのためのノンブロッキングキューで、ロックフリー（CASオペレーションを使用）であることにより、高度な並列状態での高いパフォーマンスを達成し、通常、ConcurrentLinkedQueueはBlockingQueueより性能が優れている。 ConcurrentLinkedQueueは、リンクノードに基づく非束縛のスレッドセーフキューで、ノードのソートに先入先出ルールを使用します。要素を追加するとキューの末尾に追加され、要素をフェッチするとキューの先頭にある要素を返すが、これはNULL要素を許さない。

ブロッキングキューは、キューが空になるとブロックして待ち状態にし、それから要素を取り出そうとするので、producer-consumerパターンに最適です。BlockingQueue インターフェース JDK は 7 つの実装を提供しています。

• ArrayBlockingQueue : 配列構造からなる有界ブロックキュー。
• LinkedBlockingQueue : リンクされたテーブル構造からなる境界型ブロックキュー。
• PriorityBlockingQueue : 優先順位付けをサポートする非束縛型ブロックキューです。
• 遅延キュー(DelayQueue) : 優先度キューを利用して実装された非拘束型ブロックキューです。
• SynchronousQueue。要素を保存しないブロッキングキュー。
• LinkedTransferQueue。リンクされたテーブル構造からなる非束縛のブロッキングキュー。
• LinkedBlockingDeque: リンクされたテーブル構造からなる双方向のブロッキングキュー。