多线程摘录 009

Atomic Variable & nonblocking synchronization
* int i=0; 想不到 ++i 竟然不是原子操作, 而是包含了3步

* 使用锁定缺点:
    - 很明显的, 性能和吞吐量问题, 包括context switch, 内存同步等
    - cpu利用率低, 因为其他线程都阻塞了, cpu处理几乎空闲的状态
    - 高优先级的线程也被阻塞了

* CAS算法(compare and set)
这是基于硬件语义的, 当一个引用的值等于期望值时, 赋上它新值.
然而这是JDK5才引入支持的, 在这之前即使用JNI也做不到
public class SimulatedCAS {
    @GuardedBy("this") private int value;
    public synchronized int get() { return value; }
    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));
        //告诉其他线程不断尝试 +1 操作
        return v + 1;
    }
}

In Java 5.0, low-level support was added to expose CAS operations on int, long, and object references, and the JVM compiles these into the most efficient means provided by the underlying hardware

* atomic variable classes 是等同于volatile的实现
AtomicInteger, AtomicLong, AtomicBoolean, and AtomicReference. All support CAS. 见下面摘录的"JDK关于AtomicXXX的介绍"

* 涉及多个变量的操作的时候, 可以考虑把它们"合并"起来
建一个新的(内部)类X包含要处理的多个变量, 使用AtomicReference把X包裹起来, 执行compareAndSet
public class CasNumberRange {
    @Immutable
    private static class IntPair {
        final int lower; // Invariant: lower <= upper
        final int 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))
                return;
        }
    }
    // similarly for setUpper
}

比较一下ReentrantLock和AtomicInteger的使用
ReentrantLock:
public class ReentrantLockPseudoRandom extends PseudoRandom {
    private final Lock lock = new ReentrantLock(false);
    private int seed;

    ReentrantLockPseudoRandom(int seed) {
        this.seed = seed;
    }

    public int nextInt(int n) {
        lock.lock();
        try {
            int s = seed;
            seed = calculateNext(s);
            int remainder = s % n;
            return remainder > 0 ? remainder : remainder + n;
        } finally {
            lock.unlock();
        }
    }
}
AtomicInteger:
public class AtomicPseudoRandom extends PseudoRandom {
    private AtomicInteger seed;

    AtomicPseudoRandom(int seed) {
        this.seed = new AtomicInteger(seed);
    }

    public int nextInt(int n) {
        while (true) {
            int s = seed.get();
            int nextSeed = calculateNext(s);
            if (seed.compareAndSet(s, nextSeed)) {
                int remainder = s % n;
                return remainder > 0 ? remainder : remainder + n;
            }
        }
    }
}

* 在非常高并发的情况下, ReentrantLock比AtomicInteger高校, 因为ReentrantLock让线程阻塞了, cpu可以处于空闲状态, 而AtomicInteger则是把决定权还给了caller线程, 让它去尝试, 会占用不少的cpu时间. 然后, 真是的情况不会是经常出现高并发, 而是中等并发, 那么AtomicInteger就更适合. 而且曲线图也证明这点

# 非阻塞算法
1) Nonblocking Stack Using Treiber's Algorithm
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));
    }

    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));
        return oldHead.item;
    }

    private static class Node <E> {
        public final E item;
        public Node<E> next;

        public Node(E item) {
            this.item = item;
        }
    }
}

2) Michael-Scott nonblocking linked-queue algorithm
public class LinkedQueue <E> {
    private static class Node <E> {
        final E item;
        final AtomicReference<Node<E>> next;

        public Node(E item, Node<E> next) {
            this.item = item;
            this.next = new AtomicReference<Node<E>>(next);
        }
    }

    private final Node<E> dummy = new Node<E>(null, null);
    private final AtomicReference<Node<E>> head
            = new AtomicReference<Node<E>>(dummy);
    private final AtomicReference<Node<E>> tail
            = new AtomicReference<Node<E>>(dummy);

    public boolean put(E item) {
        Node<E> newNode = new Node<E>(item, null);
        while (true) {
            Node<E> curTail = tail.get();
            Node<E> tailNext = curTail.next.get();
            if (curTail == tail.get()) {
                if (tailNext != null) {                    
                    // Queue in intermediate state, advance tail
                    tail.compareAndSet(curTail, tailNext);  
                } else {
                    // In quiescent state, try inserting new node
                    if (curTail.next.compareAndSet(null, newNode)) {
                        // Insertion succeeded, try advancing tail
                        tail.compareAndSet(curTail, newNode);       
                        return true;
                   }
                }
            }
        }
    }
}

* 关于CAS的ABA问题
CAS的核心是compareAndXXX, 然后compare前后涉及到是两次操作(先在外部代码取得expectedValue,再调用compareAndXXX), 那么, 很可能两次操作之间可能出现一些变化, 但又变回去了.

假设, 第一次读取V地址的A值, 然后通过CAS来判断V地址的值是否仍旧为A, 如果是, 就将B的值写入V地址,覆盖A值.

但是, 语义上, 有一个漏洞, 当第一次读取V的A值, 此时, 内存V的值变为B值, 然后在未执行CAS前, 又变回了A值.
此时, CAS再执行时, 会判断其正确的, 并进行赋值.

这种判断值的方式来断定内存是否被修改过, 针对某些问题, 是不适用的.

为了解决这种问题, jdk 1.5并发包提供了AtomicStampedReference(有标记的原子引用)类, 通过控制变量值的版本来保证CAS正确性.


JDK关于AtomicXXX的介绍, 很清晰
===============================
软件包 java.util.concurrent.atomic 的描述
类的小工具包，支持在单个变量上解除锁定的线程安全编程。事实上，此包中的类可将 volatile 值、字段和数组元素的概念扩展到那些也提供原子条件更新操作的类，其形式如下：

boolean compareAndSet(expectedValue, updateValue);
如果此方法（在不同的类间参数类型也不同）当前保持 expectedValue，则以原子方式将变量设置为 updateValue，并在成功时报告 true。此包中的类还包含获取并无条件设置值的方法，以及较弱条件的原子更新操作 weakCompareAndSet。该弱版本操作在正常情况下可能更有效，但不同的是 weakCompareAndSet 方法的任何给定调用可能会失败，甚至意外失败（即没有明确的原因）。返回 false 仅意味着可以在需要时重新尝试操作，具体取决于重复执行调用的保证，当该变量保持 expectedValue 并且没有其他线程也在尝试设置该变量时，调用最终将获得成功。

这些方法的规范使实现能够使用当代处理器上提供的高效机器级别原子指令。但是在某些平台上，该支持可能需要某种形式的内部锁定。因而，该方法不能严格保证不被阻塞 - 执行操作之前可能暂时阻塞线程。

类 AtomicBoolean、AtomicInteger、AtomicLong 和 AtomicReference 的实例各自提供对相应类型单个变量的访问和更新。每个类也为该类型提供适当的实用工具方法。例如，类 AtomicLong 和 AtomicInteger 提供了原子增量方法。一个应用程序将按以下方式生成序列号：

class Sequencer {
private AtomicLong sequenceNumber = new AtomicLong(0);
public long next() { return sequenceNumber.getAndIncrement(); }
}
原子访问和更新的内存效果一般遵循以下可变规则：

get 具有读取 volatile 变量的内存效果。
set 具有写入（分配） volatile 变量的内存效果。
weakCompareAndSet 以原子方式读取和有条件地写入变量，并对于该变量上的其他内存操作进行排序，否则将充当普通的非可变内存操作。
compareAndSet 和所有其他的读取和更新操作（如 getAndIncrement）都有读取和写入 volatile 变量的内存效果。
除了包含表示单个值的类之外，此包还包含 Updater 类，该类可用于获取任意选定类的任意选定 volatile 字段上的 compareAndSet 操作。AtomicReferenceFieldUpdater、AtomicIntegerFieldUpdater 和 AtomicLongFieldUpdater 是基于反射的实用工具，可以提供对关联字段类型的访问。它们主要用于原子数据结构中，该结构中同一节点（例如，树节点的链接）的几个 volatile 字段都独立受原子更新控制。这些类在如何以及何时使用原子更新方面具有更大的灵活性，但相应的弊端是基于映射的设置较为拙笨、使用不太方便，而且在保证方面也较差。

AtomicIntegerArray、AtomicLongArray 和 AtomicReferenceArray 类进一步扩展了原子操作，对这些类型的数组提供了支持。这些类在为其数组元素提供 volatile 访问语义方面也引人注目，这对于普通数组来说是不受支持的。

AtomicMarkableReference 类将单个布尔值与引用关联起来。例如，可以在数据结构内部使用此位，这意味着引用的对象在逻辑上已被删除。AtomicStampedReference 类将整数值与引用关联起来。例如，这可用于表示与更新系列对应的版本号。

设计原子类主要用作各种构造块，用于实现非阻塞数据结构和相关的基础结构类。compareAndSet 方法不是锁定的常规替换方法。仅当对象的重要更新限定于单个 变量时才应用它。

原子类不是 java.lang.Integer 和相关类的通用替换方法。它们不 定义诸如 hashCode 和 compareTo 之类的方法。（因为原子变量是可变的，所以对于哈希表键来说，它们不是好的选择。）另外，仅为那些通常在预期应用程序中使用的类型提供类。例如，没有表示 byte 的原子类。这种情况不常见，如果要这样做，可以使用 AtomicInteger 来保持 byte 值，并进行适当的强制转换。也可以使用 Float.floatToIntBits 和 Float.intBitstoFloat 转换来保持 float 值，使用 Double.doubleToLongBits 和 Double.longBitsToDouble 转换来保持 double 值。

转自：http://hi.baidu.com/iwishyou2/blog/item/6d3d8e4bb107cbf882025cff.html