《Java并发编程实践》笔记6——并发性调优

1.Amdahl定律： 
Amdahl(阿姆达尔)定律描述了在一个系统中，基于可并行化和串行化的组件各自所占的比重，程序通过获得额外的计算资源，理论上能够加速多少。若F是必须串行化执行的比重，那么在一个N处理器的机器中，通过Amdahl定律计算可以获得理论加速为： 
Speedup<=1/(F+(1-F)/N) 
当N无限增大趋近与无穷大时，Speedup的最大值无限接近于1/F。 

Amdahl估算理论加速例子如下： 
(1).在CPU无限多的情况下，一个程序中若有50%的处理需要串行，则Speedup只能提高2倍；若程序中有10%需要串行执行，则Speedup最多只能提高10倍。 
(2).一个程序中若有10%是串行执行，在拥有10个CPU的情况下，Speedup最多只能达到5.3倍；在拥有100个CPU的情况下，Speedup最多只能达到9.2倍。 
所有的并发程序中都有串行执行的部分，因此在评估添加硬件资源对并发程序性能提高时，Amdahl定律是理论基础和计算依据。 

2.减少锁的竞争： 
Amdahl定律告诉我们串行化会损害可伸缩性；线程上下文切换会影响性能；锁竞争会同时影响可伸缩性与性能。 
Little定律：稳定系统中，顾客的平均数量=顾客的平均到达率*顾客在系统中的平均等待时间，通过Little定律我们可得出影响锁竞争性的两个因素：锁被请求的频率、每次持有该锁的时间。 
下面3种方式可以降低锁竞争： 

(1).减少锁的持有时间： 
通过将与锁无关的代码移出同步代码块，缩小同步范围可以减少锁的持有时间，从而减少锁竞争，下面的例子代码演示锁时间持有过长同步范围过大：

public class AttributeStore {
    private final Map<String, String> attributes = new HashMap<String, String>();

    public synchronized boolean userLocationMatches(String name, String regexp){
        String key = "users." + name + ".location";
        String location = attributes.get(key);
        if(location == null){
            return false;
        }else{
            return Pattern.matches(regexp, location);
        }
    }
}

上面例子代码中，只有从map中获取location时需要同步，其他的正则表达式匹配等都不需要同步，我们可以通过减少同步范围来减少锁持有时间，改进后的例子代码如下：

public class AttributeStore {
    private final Map<String, String> attributes = new HashMap<String, String>();

    public boolean userLocationMatches(String name, String regexp){
        String key = "users." + name + ".location";
        synchronized(this){
            String location = attributes.get(key);
        }
        if(location == null){
            return false;
        }else{
            return Pattern.matches(regexp, location);
        }
    }
}

　　减少同步范围可以减少串行化执行比重，通过Amdahl定律知道可以提高可伸缩性。 
(2).降低锁的请求频率： 
若一个应用中只有一个全局锁，而不是为每个对象分配一个独立锁，那么所有同步的操作都变成了串行顺序执行，若将锁请求分配到更多锁对象上，单个锁的请求频率将会被降低，降低锁的请求频率通常有两种方法： 
A.锁分拆(lock splitting)： 
锁分拆是指将多个相互独立状态变量由一个锁来保护分离成为每个独立状态变量由一个单独的锁来保护。 
下面的例子代码演示一个锁保护多个独立状态变量：

public class ServerStatus{
    private final Set<String> users;
    private final Set<String> queries;

    public synchronized void addUserP|(String user){
        users.add(user);
    }

    public synchronized void addQueries(String query){
        queries.add(query);
    }

    public synchronized void removeUser(String user){
        users.remove(user);
    }

    public synchronized void removeQuery(String query){
        querys.remove(query);
    }
}

下面例子代码演示锁分拆技术，例子代码如下：

public class SplitedServerStatus{
    private final Set<String> users;
    private final Set<String> queries;

    public void addUser(String user){
        synchronized(users){
            users.add(user);
        } 
    }

    public void addQueries(String query){
        synchronized(queries){
            queries.add(query);
        }
    }

    public void removeUser(String user){
        synchronized(users){
            users.remove(user);
        }
    }

    public void removeQuery(String query){
        synchronized(queries){
            queries.remove(query);
        }
    }
}

将一个竞争适中而不竞争激烈的锁，分离为两个锁，可以最大限度地提高可伸缩性和性能。 
B.锁分离(lock striping)： 
将一个竞争激烈的锁分拆为两个锁时，这两个锁可能都竞争激烈，虽然采用两个线程并发执行能提高一部分可伸缩性，但是在一个拥有多处理器系统中，仍然无法给可伸缩性带来极大的提高，这时我们需要使用锁分离技术。 
锁分离是锁分拆技术的扩展，将被加锁对象分成可大可小加锁块的集合，并且这些集合使用相互独立的锁对象。JDK1.5引入的ConcurrentHashMap就使用的是锁分离技术，ConcurrentHashMap的实现中使用一个包含16个锁的数组，每个锁包含散列桶的1/16，其中第N个散列桶由第(N mod 16)个锁来保护。若哈希算法实现的比较好，即哈希值均匀分布，则ConcurrentHashMap的锁分离可以将锁请求减少为原来的1/16，并且可以支持多达16路的并发写入。 
下面的例子代码演示锁分离：

public class StripedMap{
    private static final int N_LOCKS = 16;
    private final Node[] buckets;
    private final Object[] locks;
    private static class Node{......}

    public StripedMap(int numBuckets){
        buckets = new Node[numBuckets];
        locks = new Object[N_LOCKS];
        for(int i = 0; i < N_LOCKS; i++){
            locks[i] = new Object();
        }
    }

    private final int hash(Object key){
        return Math.abs(key.hashCode() % buckets.length);
    }

    public Object get(Object key){
        int hash = hash(key);
        synchronized(locks[hash % N_LOCKS]){
            for(Node n = buckets[hash]; n != null; n = n.next){
                if(n.key.equals(key)){
                    return n.value;
                }
            }
        }
        return null;
    }

    public void clear(){
        for(int i = 0; i < buckets.length; i++){
            synchronized(locks[i % N_LOCKS]){
                buckets[i] = null;
            }
        }
    }

    ......
}

(3).放弃使用独占锁： 
使用并发容器、读-写锁，不可变对象，原子变量等代替独占锁来管理共享对象可以获得比独占锁更好的可伸缩性与性能。 
ReadWriteLock读-写锁实现了单写入多读取情况下的加锁机制，读取操作可以同时访问共享变量，而写入操作采用独占锁方式，对于读取操作占多数的情况下，读-写锁可以提供比独占锁更好的并发性。 
读写锁例子如下：

public class RWDictionary {
    private final Map<String, Data> m = new TreeMap<String, Data>(); 
    private final ReadWriteLock rwl = new ReentrantReadWriteLock();   
    private final Lock r = rwl.readLock();    
    private final Lock w = rwl.writeLock();    

    public Data get(String key) {      
        r.lock();       
        try { 
            return m.get(key); 
        }finally {
            r.unlock(); 
        }
    }

    public Data put(String key, Data value) {
        w.lock(); 
        try { 
            return m.put(key, value); 
        }finally {
            w.unlock(); 
        }
    }

    ......
}

ReentrantReadWriteLock读-写锁默认是公平的，也可以显式指定为非公平的，其区别如下： 
A.公平模式： 
选择权交给等待时间最长的线程，若锁由读者线程获得，而一个线程请求写入锁，那么不再允许读者获得读取锁，直到写线程被受理并且已经释放写入锁。 
B.非公平模式： 
线程允许访问的顺序是不确定的，由写锁降级为读锁是允许的，反之由读锁升级为写锁是禁止的(可能会导致死锁)。 
3.ReentranLock与synchronized的选择： 
ReentranLock实现了Lock接口，提供了与synchronized内部锁相同的互斥、内存可见性以及可重入加锁语义，与synchronized内部锁不同的是，提供了无条件的、可轮询的、可定时的、可中断的锁操作。ReentranLock与synchronized使用时的选择考量： 
(1).要使用可轮询、可定时、可中断、公平性等特性的使用ReentranLock： 
A.ReentranLock的可轮询特性可以避免锁顺序死锁，若无法同时获得两个锁会回退释放所获得的锁，以银行转账为例演示可轮询特性：

public boolean transferMoney(Account fromAccount, 
                                Account toAccount, 
                                DollarAmount amount, 
                                long timeout, 
                                TimeUnit unit) 
                                throws InsufficientFundsException, InterruptedException{
    long fixedDelay = getFixedDelayComponentNanos(timeout, unit);
    long randMod = getRandomDelayModulusNanos(timeout, unit);
    long stopTime = System.nanoTime() + unit.toNanos(timeout);
    while(true){
        if(fromAccount.lock.tryLock()){
            try{
                if(toAccount.lock.tryLock()){
                    try{
                        if(fromAccount.getBalance().compareTo(amount) < 0){
                            throw new InsufficientFundsException();
                        }else{
                            fromAccount.debit(amount);
                            toAccount.credit(amount);
                            return true;
                        }
                    }finally{
                        toAccount.unlock();
                    }
                }
            }finally{
                fromAccount.unlock();
            }
        }
        if(System.nanoTime() < stopTime){
            return false;
        }
        NANOSECONDS.sleep(fixedDelay + rnd.nextLong() % randMod);
    }
}

B.ReentranLock的可定时特性使得在超出规定时间内没有结束的线程释放所获得的锁，避免线程无限阻塞，例子代码如下：

public boolean trySendOnSharedLine(String message, long timeout, TimeUnit unit)
throws InterruptedException{
    long nanosToLock = unit.toNanos(timeout) - estimatedNanosToSend(message);
    if(!lock.tryLock(nanosToLock, NANOSECONDS)){
        return false;
    }try{
        return sendOnSharedLine(message);
    }finally{
        lock.unlock();
    }
}

C.ReentranLock的可中断特性使得可以在可取消的任务中使用，线程在响应中断时可以获得锁，例子代码如下：

public boolean sendOnSharedLine(String message) throws InterruptedException{
    lock.lockInterruptibly();
    try{
        return cancellableSendOnSharedLine(message);
    }finally{
        lock.unlock();
    }
}

public boolean cancellableSendOnSharedLine(String message) throws InterruptedException{......}

D.ReentranLock默认是非公平锁，可以显式指定为公平锁。 
在锁竞争激烈情况下(大多数情况下)非公平锁性能比较好；当持有锁的时间比较长，或者请求锁的平均时间间隔比较长情况下，公平锁性能比较好。 
(2).一般情况下使用synchronized： 
synchronized内部锁是内置于JVM的，编译器可以在运行时动态进行锁消除、锁粗化等优化，同时线程转储中synchronized的锁信息比较详细便于调试。 
ReentranLock必须在finally中释放锁，如果忘记释放则会造成严重错误。因此只有synchronized不能满足需求，需要使用ReentranLock高级特性时才使用ReentranLock，一般情况下推荐优先使用synchronized。 
4.使用Condition代替notify/notifyAll： 
在JDK1.5之前，经常使用Object对象的wait和notify/notifyAll作为线程协调机制，以一个有限缓存队列为例，演示例子代码如下：

public abstract class BasesBoundedBuffer<V> {
    private final V[] buf;
    private int count;

    protected BaseBoundedBuffer(int capacity) {
        this.buf = (V[]) new Object[capacity];
    }

    protected synchronized void doPut(V v){......};

    protected synchronized void doTake(){......};

    public synchronized final boolean isFull() {
        return count == buf.length;
    }

    public synchronized final boolean isEmpty() {
        return count == 0;
    }
}

public class WaitNofiyBoundedBuffer<V> extends BasesBoundedBuffer<V> {
    public synchronized void put(V v) throws InterruptedException {
        while (isFull()) {
            wait();
        }
        doPut(v);
        notifyAll();
    }

    public synchronized V take() throws InterruptedException {
        while (isEmpty()) {
            wait();
        }
        V v = doTake();
        notifyAll();
        return v;
    }
}

notify和notifyAll的区别如下： 
(1)notifyAll： 
唤醒所有正在条件队列中等待的线程，让他们去竞争锁，只有一个线程会获得锁，其他的线程又重新回到等待状态，会带来大量的线程上下文切换和大量的锁竞争，效率低下。 
(2).notify： 
只是选择一个等待状态线程进行通知，并使它获得该对象上的锁，但不通知其他同样在等待被该对象唤醒的线程们，若被唤醒的线程发现其执行条件不成立，则继续转回等待状态，而其他执行条件成立的线程不会被唤醒，一直在等待已经过期的信号，这就发生了被劫持的信号(或丢失的信号)问题。 
一般情况下为了避免被劫持的信号情况发生，通常使用notifyAll代替notify，当且仅当只有一个被激活线程且条件谓词(如上面例子中队列满、空等)只有一个时才使用notify。 
为了克服notifyAll低效的缺点，JDK1.5引入了Condition，下面的例子使用Condition代替notifyAll/notify演示上述的有限缓存队列：

public class ConditionBoundedBuffer<V> extends BasesBoundedBuffer<V>{
    protected final Lock lock = new ReentrantLock();
    private final Condition notFull = lock.newCondition();
    private final Condition notEmpty = lock.newCondition();

    public void put(V v) throws InterruptedException{
        lock.lock();
        try{
            while(isFull()){
                notFull.await();
            }
            doPut(v);
            notEmpty.signal();
        }finally{
            lock.unlock();
        }
    }

    public V take() throws InterruptedException{
        lock.lock();
        try{
            while(isEmpty()){
                notEmpty.await();
            }
            V v = doTake();
            notFull.signal();
            return v;
        }finally{
            lock.unlock();
        }
    }
}

Condition的signal和signalAll方法类似于Object的notify和notifyAll，但是Condition的signal克服了notify的信号劫持问题，同样又避免了notifyAll的效率低下问题。 
Condition的await和signal方法必须在持有锁对象时调用。 
Condition与Object的notify/notifyAll的选择类似于ReentrantLock与synchronized之间的选择。