Java concurrent programming (8) Atomic variables and non-blocking synchronization mechanism

Atomic variables and non-blocking synchronization mechanism

1. Disadvantages of locks

1. Under multi-threading: there is a lot of overhead in the process of lock suspension and recovery ( Modern jvm will determine when to use suspend and when to spin and wait)

　2.volatile: lightweight level synchronization mechanism, but cannot be used to build atomic composite operations

Therefore : There needs to be a way to manage competition between threads with a finer granularity, similar to the volatile mechanism, while also supporting atomic update operations

2. CAS

Exclusive locking is a pessimistic technique - it assumes the worst case scenario, so each thread is exclusive

And CAS compare and swap: compareAndSwap/Set(A,B): We think the value in memory It is A. If it is A, modify it to B, otherwise no operation will be performed; return the original value in the memory or whether the modification is successful

For example: simulate CAS operation

//模拟的CASpublic class SimulatedCAS {private int value;public synchronized int get() {return value;
    }//CAS操作public synchronized int compareAndSwap(int expectedValue, int newValue) {int oldValue = value;if (oldValue == expectedValue) {
            value = newValue;
        }return oldValue;
    }public synchronized boolean compareAndSet(int expectedValue, int newValue) {return (expectedValue == compareAndSwap(expectedValue, newValue));
    }
}//典型使用场景public class CasCounter {private SimulatedCAS value;public int getValue() {return value.get();
    }public int increment() {int v;do {
            v = value.get();
        } while {
            (v != value.compareAndSwap(v, v + 1));
        }return v + 1;
    }
}

JAVA provides CAS operations

Atomic state class: CAS method of AtomicXXX

JAVA7/8: Map operations: putIfAbsent, computerIfAbsent, computerIfPresent.. .......

3. Atomic variable class

AtomicRefence atomic update object can be a custom object; such as:

public class CasNumberRange {private static class IntPair {// INVARIANT: lower <= upperfinal int lower;        //将值定义为不可变域final int upper;        //将值定义为不可变域public IntPair(int lower, int upper) {this.lower = lower;this.upper = upper;
        }
    }private final AtomicReference<IntPair> values = new AtomicReference<IntPair>(new IntPair(0, 0));    //封装对象public int getLower() {return values.get().lower;
    }public int getUpper() {return values.get().upper;
    }public void setLower(int i) {while (true) {
            IntPair oldv = values.get();if (i > oldv.upper) {throw new IllegalArgumentException("Can't set lower to " + i + " > upper");
            }
            IntPair newv = new IntPair(i, oldv.upper);  //属性为不可变域，则每次更新新建对象if (values.compareAndSet(oldv, newv)) {     //原子更新，如果在过程中有线程修改了，则其他线程不会更新成功，因为oldv与内存处值就不同了return;
            }
        }
    }//同上public void setUpper(int i) {while (true) {
            IntPair oldv = values.get();if (i < oldv.lower)throw new IllegalArgumentException("Can&#39;t set upper to " + i + " < lower");
            IntPair newv = new IntPair(oldv.lower, i);if (values.compareAndSet(oldv, newv))return;
        }
    }
}

Performance issue: Using atomic variables is faster than using locks under medium and low concurrency (competition). Generally, it is faster than locking speed

4. Non-blocking algorithm

Non-blocking algorithm can be used in many common data structures

Non-blocking algorithm: In multi-threading, there is uncertainty about whether the work will be successful and it needs to be executed in a loop. And perform atomic operations through CAS

1. The above CasNumberRange

2. Non-blocking algorithm of the stack: only save the head pointer, only one state

//栈实现的非阻塞算法：单向链表public class ConcurrentStack <E> {
    AtomicReference<Node<E>> top = new AtomicReference<Node<E>>();public void push(E item) {
        Node<E> newHead = new Node<E>(item);
        Node<E> oldHead;do {
            oldHead = top.get();
            newHead.next = oldHead;
        } while (!top.compareAndSet(oldHead, newHead));//CAS操作：原子更新操作,循环判断，非阻塞    }public E pop() {
        Node<E> oldHead;
        Node<E> newHead;do {
            oldHead = top.get();if (oldHead == null) {return null;
            }
            newHead = oldHead.next;
        } while (!top.compareAndSet(oldHead, newHead));//CAS操作：原子更新操作,循环判断，非阻塞return oldHead.item;
    }private static class Node <E> {public final E item;public Node<E> next;public Node(E item) {this.item = item;
        }
    }
}

　3. Non-blocking algorithm for linked lists: fast access to the head and tail, saving two states, more complex

public class LinkedQueue <E> {private static class Node <E> {final E item;final AtomicReference<LinkedQueue.Node<E>> next;public Node(E item, LinkedQueue.Node<E> next) {this.item = item;this.next = new AtomicReference<LinkedQueue.Node<E>>(next);
        }
    }private final LinkedQueue.Node<E> dummy = new LinkedQueue.Node<E>(null, null);private final AtomicReference<LinkedQueue.Node<E>> head = new AtomicReference<LinkedQueue.Node<E>>(dummy);private final AtomicReference<LinkedQueue.Node<E>> tail = new AtomicReference<LinkedQueue.Node<E>>(dummy);  //保存尾节点public boolean put(E item) {
        LinkedQueue.Node<E> newNode = new LinkedQueue.Node<E>(item, null);while (true) {
            LinkedQueue.Node<E> curTail = tail.get();
            LinkedQueue.Node<E> tailNext = curTail.next.get();if (curTail == tail.get()) {if (tailNext != null) {// 处于中间状态，更新尾节点为当前尾节点的next                    tail.compareAndSet(curTail, tailNext);
                } else {// 将当前尾节点的next 设置为新节点：链表if (curTail.next.compareAndSet(null, newNode)) {/** * 此处即为中间状态，虽然在这里进行了两次原子操作，整体不是原子的，但是通过算法保证了安全：
                         * 原因是处于中间状态时，如果有其他线程进来操作，则上面那个if将执行；
                         * 上面if的操作是来帮助当前线程完成更新尾节点操作，而当前线程的更新就会失败返回，最终则是更新成功                         */// 链接成功，尾节点已经改变，则将当前尾节点，设置为新节点                        tail.compareAndSet(curTail, newNode);return true;
                    }
                }
            }
        }
    }
}

3. Atomic domain updater

The above logic implements the non-blocking algorithm of the linked list, using Node to save the head node and tail node

The actual ConcurrentLinkedQueue is based on Reflected AtomicReferenceFiledUpdater to wrap Node

5. ABA problem

Issues that are likely to occur in CAS operations:

Judgment value Whether it is A, if so, continue the update operation and change it to B;

But if a thread changes the value A to C, and then changes it back to A, at this time, the original thread will judge that A=A and successfully execute the update Operation;

If you change A to C and then change it back to A, it also needs to be regarded as a change, and the algorithm needs to be optimized

Solution: Add a version number every time it is updated All operations must update the version number, even if the value is the same

　　　

The above is the detailed content of Java concurrent programming (8) Atomic variables and non-blocking synchronization mechanism. For more information, please follow other related articles on the PHP Chinese website!