Java同時プログラミング(三)--同時データ構造

3976 ワード

データ構造 Javaプログラミング

コンカレントHashMapのデザインが実現しました.
なぜコンカレントHashMapが必要なのですか?Hashtableがあるのではないですか?すべてのことをSynchronizedで解決すれば、この世界は大変になります.
ConcerenthashMapの最も絶妙なところはロックセグメント技術を採用しています.一つのhashMapはいくつかのSegmentに分けられています.各Segmentで同期制御を行います.
ConcerenthashMapの操作はまずSegmentを見つけてからSegmentで行います.

public V put(K key, V value) {
        if (value == null)
            throw new NullPointerException();
        int hash = hash(key.hashCode());
        return segmentFor(hash).put(key, hash, value, false);
}
final Segment<K,V> segmentFor(int hash) {
        return segments[(hash >>> segmentShift) & segmentMask];
    }
                 。
  ConcurrentHashMap        ，     Segment Entry         ！
V get(Object key, int hash) {
            if (count != 0) { // read-volatile
                HashEntry<K,V> e = getFirst(hash);
                while (e != null) {
                    if (e.hash == hash && key.equals(e.key)) {
                        V v = e.value;
                        if (v != null)
                            return v;
                        return readValueUnderLock(e); // recheck
                    }
                    e = e.next;
                }
            }
            return null;
        }

まず対応する項目を見つけて、nullでない場合はそのまま返します.そうでなければ、readValue UnderLock方法を呼び出します.注意したいのは、そのreadValue Unider Lock(e)方法です.

/**
         * Reads value field of an entry under lock. Called if value
         * field ever appears to be null. This is possible only if a
         * compiler happens to reorder a HashEntry initialization with
         * its table assignment, which is legal under memory model
         * but is not known to ever occur.
         */
        V readValueUnderLock(HashEntry<K,V> e) {
            lock();
            try {
                return e.value;
            } finally {
                unlock();
            }
        }

ソースコメントの解釈はコンパイラがHash Entryを並べ替えるかもしれません.JMMには許容されます.まだ他のスレッドがありますので、ロックをかけて他のスレッドの更新を待っています.

CopyOWriteArayList設計実現
すべての可変操作(add、set) など)は、一次配列を新たにコピーすることによって達成されます.

BlockingQueデザインが実現しました.
生来の生産者消費者型のデータ構造.
BlockingQueの実現は、2つのロックTake LockとputLock、2つの信号量(条件変数)notEmptyとnotFullで、PV原理に基づいて実現されます.Await操作は遅延対応ですので、対応するputとtakeも遅延操作に対応しています.

コンカレントLinkedQueのデザインが実現しました.
非ブロッキングアルゴリズムに基づくチェーン列.ブロッキングアルゴリズムでないと分かりにくいところの一つは、複数のポインタまたはCAS操作の使い方を参照することです.ここでは、2つのポインタにのみ関連しています.1 offerの動作は例として挙げられます.

public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
        Node<E> n = new Node<E>(e);
        retry:
        for (;;) {
            Node<E> t = tail;
            Node<E> p = t;
            for (int hops = 0; ; hops++) {
                Node<E> next = succ(p);
                if (next != null) {
                    if (hops > HOPS && t != tail)
                        continue retry;
                    p = next;
                } else if (p.casNext(null, n)) {
                    if (hops >= HOPS)
                        casTail(t, n); // Failure is OK.
                    return true;   
                } else {
                    p = succ(p);
                }
            }
        }
    }

複数のポインタの修正は、データ構造状態が一致しないようにすることがあります.例えば、最初の参照の指向修正が成功しましたが、第二の修正が失敗した場合、この中間に他のスレッドがデータ構造を動作させると、予測不可能な問題が発生する可能性があります.一般的にマルチスレッドの協力による非ブロッキング処理が行われていますが、最初のスレッドが未完成の操作があれば、後続スレッドが判断でき、それを継続的に完了させることができます.offer動作については、他のスレッドが更新中にノードが一致していることが発見されたが、後尾ノードの後継ノードが空ではないことを示し、前のスレッドの動作が完了していないことを示すと、このスレッドは、ループ内に現在の後尾ノードの後継者として末尾ノードを設定し続ける.

データ構造——3単鎖表逆方向