【JUC】COW容器浅析

文書ディレクトリ

1、COW

とは

2、JavaにおけるCowコンテナ

3、CopyOnWriteArrayListソース分析

4、COW容器の長所と短所及び適用シーン

1、COWとは
Wikipedia定義:書き込み時のレプリケーション(英語:Copy-on-write、略称COW)は、コンピュータプログラム設計分野の最適化戦略です.複数の呼び出し元(callers)が同じリソース(メモリやディスク上のデータストレージなど)を同時に要求すると、同じポインタが同じリソースを指し、ある呼び出し元がリソースの内容を変更しようとするまで、システムは本当に専用コピー(private copy)を呼び出し元にコピーすることができます.他の呼び出し者が見た最初のリソースは依然として変わらない.このプロセスは他の呼び出し者に対して透明である(transparently).  この方法の主な利点は、呼び出し元がリソースを変更していない場合、private copyが作成されないため、複数の呼び出し元は、操作を読み込むときに同じリソースを共有できるだけであることです.一般的に言えば、cowは「書き込み時コピー」の考え方に基づいて、同じデータリソースの読み取りを同時に要求すると、同じデータが読み込まれ、ある要求がリソースの修正を試みると、コピーをコピーしてコピーのデータを修正し、他の要求が読み取ったデータは最初は変わらない.最後に、ソースデータへの参照は、このスレッドが変更されたコピーデータを指します.
2、Javaの中のCow容器
  JavaにおけるCowコンテナは2つあり、Jdk 1.5バージョンではCopyOnWriteArrayListおよびCopyOnWriteArraySetとして登場し始めた. CopyOnWriteArrayListはCopyOnWriteArraySetとほぼ一致しており、主な違いはaddメソッド、CopyOnWriteArraySet、setの特性があり、すなわち記憶要素は重複しないため、CopyOnWriteArraySetのaddメソッドではaddIfAbsent(E e)が使用され、すなわち要素が存在しない場合にのみ集合の末尾に要素が追加される.
3、CopyOnWriteArrayListソースコード分析
  ソースコードから、CopyOnWriteArrayList内部にReentrantLockロックがあり、最も重要な属性arrayはObjectタイプの配列であり、volatileキーワード修飾があり、このarrayはgetArray()とsetArray()のみでアクセスできることがわかります.

    /** The lock protecting all mutators */
    final transient ReentrantLock lock = new ReentrantLock();

    /** The array, accessed only via getArray/setArray. */
    private transient volatile Object[] array;
    /**
     *      
     */
    final Object[] getArray() {
        return array;
    }

    /**
     *           
     */
    final void setArray(Object[] a) {
        array = a;
    }

add()メソッド:

    public boolean add(E e) {
        final ReentrantLock lock = this.lock;
        // 1、  
        lock.lock();
        try {
        	// 2、       
            Object[] elements = getArray();
            int len = elements.length;
        	// 3、        ，     =      + 1
            Object[] newElements = Arrays.copyOf(elements, len + 1);
            // 4、            
            newElements[len] = e;
            // 5、           
            setArray(newElements);
            return true;
        } finally {
            lock.unlock();
        }
    }

add()メソッドの主なワークフローは以下の通りです.

まずロック操作

を行う.

getArray()メソッドによりソース配列

を取得

は新しい配列をコピーし、新しい配列の長さを1

加算する.

追加する要素を新しい配列の末尾

に追加する

setArray()メソッドによりソース配列参照を新しい配列

に向ける.

最終リリースロック

remove()メソッド

public boolean remove(Object o) {
	// 1、      
    Object[] snapshot = getArray();
    // 2、            
    int index = indexOf(o, snapshot, 0, snapshot.length);
    // 3、    ，     false，    remove      
    return (index < 0) ? false : remove(o, snapshot, index);
}

private static int indexOf(Object o, Object[] elements,
                           int index, int fence) {
    //         null,       ,       null                              
    if (o == null) {
        for (int i = index; i < fence; i++)
            if (elements[i] == null)
                return i;
    } else {
    //     ，  equals               
        for (int i = index; i < fence; i++)
            if (o.equals(elements[i]))
                return i;
    }
    //          ，    -1
    return -1;
}

private boolean remove(Object o, Object[] snapshot, int index) {
    final ReentrantLock lock = this.lock;
    // 1、  
    lock.lock();
    try {
    	// 2、     
        Object[] current = getArray();
        int len = current.length;
        // 3、          ，                
        if (snapshot != current) findIndex: {
        	//        
            int prefix = Math.min(index, len);
            //                    ，      if  
            for (int i = 0; i < prefix; i++) {
                if (current[i] != snapshot[i] && eq(o, current[i])) {
                    index = i;
                    break findIndex;
                }
            }
            //                    ，     false
            if (index >= len)
                return false;
            //                        ，   if  
            if (current[index] == o)
                break findIndex;
            //             
            index = indexOf(o, current, index, len);
            if (index < 0)
                return false;
        }
        //      
        Object[] newElements = new Object[len - 1];
        //                          
        System.arraycopy(current, 0, newElements, 0, index);
        //                          
        System.arraycopy(current, index + 1,
                         newElements, index,
                         len - index - 1);
        //   setArray()             
        setArray(newElements);
        return true;
    } finally {
    	//   
        lock.unlock();
    }
}

remove()メソッドのワークフローも複雑ではありません.ソースコードに沿って下を見るとスムーズになります.主なフローは以下の通りです.

は、まずロックがない場合に、現在の配列で除去する要素の下付きラベルを探し、見つからない場合は直接返し、そうでない場合は書き換えのremove()メソッド

を呼び出す.

書き換えのremove()メソッドを呼び出すと、まずロック操作

が行われる.

次に、現在の配列がロック前に変化したかどうかを確認します(ロックされていないときに取得されたソース配列と比較します).これは、同時の場合、ソース配列が他の修正操作によって変更された可能性があるためです.

現在の配列が変化すると、削除する要素の下付き

を取得しようとする.

削除する要素の下付き文字が見つかったら、新しい配列を生成し、配列要素のコピーを行います.そうでなければ

に戻る

最後にソース配列参照を新しい配列

に向ける.

最後に再ロック

を解除する.
4、COW容器の長所と短所及び適用シーン
  ソースコードから、cowコンテナは、操作を修正する際に、新しい配列をコピーする方法を提供し、修正操作(追加または削除)にロックをかけ、読み取り操作が同時では読み取り要素が最新であることは保証されませんが、修正操作はデータの最終的な一致性を保証します.メリット:

マルチスレッド同時シーンでは、データの同時修正の最終的な一貫性を空間を犠牲にして取り替える、特に読み書きの少ないシーン

に適している.

同時修正操作(追加または削除)同時修正異常(C o n c u r r e ntModificationException)

は発生しません.
欠点:

は書き込み操作が多いシーンには向いていません.書き込み操作はロックされているため、性能に影響します.

操作を変更すると、メモリ容量が2倍になります.

適用シーン:

マルチスレッド同時の場合、かつ読み書きの少ないシーンは、マルチスレッド環境におけるデータの最終的な一貫性

を取り替えるために一部の空間を犠牲にすることを許容する.