《Java并发编程实战》 同步的性能问题

words: 3.8k    views:    time: 14min
Java并发编程实战

在安全性与活跃性之间通常存在着某种制衡，我们可以使用加锁机制来确保线程安全，但如果过度的使用加锁，则可能导致死锁。

1. 死锁

1.1. 顺序死锁

即两个线程试图以不同的顺序来获得相同的锁，如果按照相同的顺序来请求锁，则不会出现循环的加锁依赖，也就不会产生死锁。

LeftRightDeadlock
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public class LeftRightDeadlock {

    private final Object left = new Object();
	
    private final Object right = new Object();
    
    public void leftRight(){
        synchronized(left){
            synchronized(right){
                dosomething();
            }
        }
    }
 
    public void rightLeft(){
        synchronized(right){
            synchronized(left){
                dosomething();
            }
        }
    }
}

1.2. 动态的锁顺序

考虑资金转账问题，将资金从A账户转入B账户。在开始转账之前，首先要获得这两个Account对象的锁，以确保通过原子的方式来更新两个账户中的余额。

transferMoney
1
2
3
4
5
6
7
8
9
10
11
12
public void transferMoney(Account fromAccount,Account toAccount.DollarAmount amount) throws InsufficientFundsException{
    synchronized(fromAccount){
        synchronized(toAccount){
            if(fromAccount.getBalance().compareTo(amount) < 0){
                throw new InsufficientFundsException();
            }else{
                fromAccount.debit(amount);
                toAccount.credit(amount);
            }
        }
    }
}

在实现中，锁的实际顺序取决外部传入的参数顺序，这种情况下，外部调用很容易发生死锁，比如同时发生A账户向B账户转账，和B账户向A账户转账。

  • 改进

在制定锁的顺序时，可以使用hashcode比较来将顺序固定下来。在极少数情况下，两个对象可能拥有相同的散列值，此时可以在外面再加一层锁，保证每次只有一个线程以一致的顺序获得两个锁，从而消除死锁的可能性。

如果Account自身包含一个唯一的、不可变的，并且具备可比性的键值，那么要制定锁的顺序就更加容易了，也就不需要再另外加锁了。

transferMoney2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
private static final Object tieLock = new Object();

public void transferMoney2(final Account fromAccount, final Account toAccount, final DollarAmount amount) throws InsufficientFundsException{
    class Helper{
        public void transfer() throws InsufficientFundsException{
            if(fromAccount.getBalance().compareTo(amount) < 0){
                throw new InsufficientFundsException();
            }else{
                fromAccount.debit(amount);
                toAccount.credit(amount);
            }
        }
    }

    int fromHash = System.identityHashCode(fromAccount);
    int toHash = System.identityHashCode(toAccount);

    if(fromHash < toHash){
        synchronized(fromAccount){
            synchronized(toAccount){
                new Helper().transfer();
            }
        }
    }else if(fromHash > toHash){
        synchronized(toAccount){
            synchronized(fromAccount){
                new Helper().transfer();
            }
        }
    }else{
        synchronized(tieLock){
            synchronized(fromAccount){
                synchronized(toAccount){
                    new Helper().transfer();
                }
            }
        }
    }
}

1.3. 协作对象间的锁顺序

考虑出租车调度系统问题，Taxi代表一个出租车对象，包含位置和目的地两个属性，Dispatcher代表一个出租车车队。

Taxi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Taxi{
    private Point location;
    private Point destination;
    private final Dispatcher dispather;

    public Taxi(Dispatcher dispather){
        this.dispather = dispather;
    }

    public synchronized Point getLocation(){
        return location;
    }

    public synchronized void setLocation(Point destination){
        this.location = location;
        if(location.equals(destination)){
            dispather.norifyAvailable(this);
        }
    }
}
Dispatcher
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Dispatcher{
    private final Set<Taxi> taxis;
    private final Set<Taxi> availableTaxis;

    public Dispatcher(){
        taxis = new HashSet<Taxi>();
        availableTaxis = new HashSet<Taxi>();
    }

    public synchronized void norifyAvailable(Taxi taxi){
        availableTaxis.add(taxi);
    }

    public synchronized Image getImage(){
        Image image = new Image();
        for(Taxi t : taxis){
            image.drawMarker(t.getLocation());
        }
        return image;
    }
}

尽管没有任何方法会显式地获取两个锁，但setLocation和getImage的调用都需要获取两个锁。如果一个线程收到GPS接收器的更新事件时调用setLocation，那么它将首先更新出租车的位置，然后判断它是否到达了目的地。如果已经到达，它会通知Dispatcher：给它分配一个新的目的地。setLocation将先后获得Taxi和Dispatcher的锁，而getImage将先后获得Dispatcher与Taxi的锁，因此，就可能产生死锁。

所以，如果在持有锁的情况下调用某个外部方法，那么就需要警惕死锁。

  • 改进

如果在调用某个方法时不需要持有锁，那么这种调用称为开放调用。可以将Taxi与Dispatcher修改为开放调用，从而消除发生死锁的风险。仅使用同步代码块保护那些涉及共享状态的操作，这样在同步操作中不会去获得另外的锁，也就是说在调用另外一个同步方法之前将锁释放掉。

Taxi
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Taxi{
    private Point location;
    private Point destination;
    private final Dispatcher dispather;

    public synchronized Point getLocation(){
        return location;
    }

    public void setLocation(Point location){
        boolean reachedDestination;
        synchronized(this){
            this.location = location;
            reachedDestination = location.equals(destination);
        }
        if(reachedDestination){
            dispather.norifyAvailable(this);
        }
    }
}
Dispatcher
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Dispatcher{
    private final Set<Taxi> taxis;
    private final Set<Taxi> availableTaxis;

    public synchronized void norifyAvailable(Taxi taxi){
        availableTaxis.add(taxi);
    }

    public Image getImage(){
        Set<Taxi> copy;
        synchronized(this){
            copy = new HashSet<Taxi>(taxis);
        }
        Image image = new Image();
        for(Taxi t : copy){
            image.drawMarker(t.getLocation());
        }
        return image;
    }
}

2. 活锁

有时线程不会阻塞，但是会不断重复尝试相同的操作并且总是失败。当多个相互协作的线程都对彼此进行响应从而修改各自的状态，并使得任何一个线程都无法继续执行时，就发生了活锁。

就像两个过于礼貌的人在半路上面对面地相遇，彼此为对方让路，然而又再次相遇，就这样反复的避让下去。要避免这样的活锁问题，可以在重试机制中引入随机性，比如以太协议中定义了在重复发生冲突时采用指数方式回退机制，从而降低在多台存在冲突的机器之间发生拥塞和反复失败的风险。

3. 线程的开销

尽管使用多线程的目标是提升整体性能，但同时也会引入一些额外的性能开销，比如线程之间的协调（加锁、触发信号以及内存同步），线程的创建、销毁以及调度，线程的上下文切换。

3.1. 上下文切换

线程调度过程中需要访问由操作系统和JVM共享的数据结构。应用程序、操作系统以及JVM都使用一组相同的CPU，在JVM和操作系统的代码中消耗的CPU时钟周期越多，就意味着应用程序的可用CPU时钟周期越少。

而且，上下文切换的开销不只包含JVM和操作系统的开销。当一个新的线程被切换进来时，它所需要的数据可能不在当前处理器的本地缓存中。因此上下文切换将导致一些缓存缺失，因而线程在首次调度运行时会更加缓慢。这就是为什么调度器会为每个可运行的线程分配一个最小执行时间，即使有许多其他的线程正在等待执行。它将上下文切换的开销反弹到更多不会中断的执行时间上，以损失响应性为代价而提高整体的吞吐量。

当线程由于某个发生竞争的锁而阻塞时，Jvm通常会将这个线程挂起，并允许它被交换出去。如果线程频繁的发生阻塞，那么它们将无法使用完整的调度时间片，在程序中发生越多的阻塞就意味着越多的上下文切换，从而增加调度开销，并因此降低吞吐量。

在大多数通用的处理器中，上下文切换的开销相当于5000~10000个时钟周期，相当于几微秒。unix的vmstat命令和windows的perfmon工具都能报告上下文切换次数以及在内核中执行时间所占比例等信息，如果内核占用率超过10%，那么通常表示调度活动发生得很频繁，这可能使由I/O或竞争锁导致的阻塞引起的。

3.2. 内存同步

同步操作的性能开销包括多个方面，在synchronized和volatitle提供的可见性保证中可能会使用一些特殊命令，比如内存栅栏。内存栅栏可能刷新缓存，使缓存无效，刷新硬件的写缓冲，以及停止执行管道。另外，在内存栅栏中，大多数操作都是不能重排序的，这会抑制一些编译器优化操作。

通常Jvm也会优化掉一些不会发生竞争的锁，从而减少不必要的同步开销。并且能够通过逃逸分析来找出一些不会发布到堆上的对象，并省去对它们的同步操作。比如一些局部对象，它们只会被当前线程拥有，Jvm会将它的对象内存分配在当前线程的栈空间上，那么就可以省去这个对象中所有操作的同步，而且栈上分配有另一个好处：是可以减轻垃圾回收的工作。

3.3. 阻塞

对于非竞争的同步可以在Jvm中优化掉，而竞争的同步则可能需要操作系统的介入，从而增加开销。当在锁上发生竞争时，竞争失败的线程肯定会阻塞。

Jvm在实现阻塞行为时可以采用自旋等待或者通过操作系统挂起被阻塞的线程。这两种方式的效率高低，要取决于上下文切换的开销以及阻塞需要等待的时间，即如果时间较短则适合使用自旋。jvm通常会根据历史等待时间的分析数据在这两者之间进行选择。

4. 降低锁的竞争

4.1. 缩小锁的范围

举个例子，如果某个操作持有锁的时间超过2ms，且所有的操作都需要这个锁，那么无论拥有多少空闲处理器，吞吐量也不会超过500/s，如果将持有时间降低到1ms，那么这个锁对应的吞吐量就能提高到1000/s。

这意味着我们应该尽量缩小同步代码块来提高可伸缩性，但同步代码块也不能过小，当把一个同步代码块分解为多个同步代码块时反而会对性能产生负面影响（如果分的过小，将增加了线程被换出换进的概率，也就增加上下文切换的次数，因为释放锁后将与其他线程再次重新竞争），其实，Jvm在优化时会执行锁粗化操作，可能会将分解的同步块又重新合并起来。实际中，理想的平衡点需要根据具体情况来判断。

4.2. 降低锁的粒度

办法是采用多个独立的锁来保护相互独立的状态变量而不是只使用一个锁，这样能降低多个线程在的同一个锁上面的竞争程度。

4.3. 锁分段

对于同一个锁，在某些情况下，也可以将其进行分解，比如可以对一组独立对象上的锁进行分解。比如ConcurrentHashMap默认使用了一个包含16个锁的数组，每个锁保护所有散列桶的1/16。使得ConcurrentHashMap能够支持多达16个并发的写入器，这种技巧称为锁分段。

锁分段的劣势在于：与采用单个锁来实现独占访问相比，如果要获得多个锁来实现独占访问将更加困难并且开销更高。一般情况下，执行一个操作时只需获取一个锁，但在某些情况下就需要加锁整个容器。比如，当ConcurrentHashMap需要扩展映射范围，需要重新计算键值的散列值以分布到更大的桶集合中时，就需要获取分段锁集合中所有的锁。

StripedMap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
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 m = buckets[hash]; m != null; m = m.next()){
                if(m.key.equals(key)){
                    return m.value;
                }
            }
        }
        return null;
    }
    
    public void clear(){
        for(int i = 0; i < buckets.length; i++){
            synchronized(locks[i % N_LOCKS]){
                buckets[i] = null;
            }
        }
    }
}

StripedMap中给出了基于散列的Map实现，其中使用了锁分段技术。它拥有N_LOCKS个锁，并且每个锁保护散列桶的一个子集。

方法get只需获得一个锁，但有些方法则需要获得所有的锁，比如clear，这种清除并非原子操作，可能当StripedMap为空时有其他线程正在并发地向其中添加元素。如果要使该操作成为一个原子操作，那么就需要同时获得所有的锁。如果客户代码不通过加锁来实现独占访问，那么像size或isEmpty这样的方法的计算结果在返回时可能会变得无效，不过，尽管这种行为有些奇怪，但通常是可以接受的。

  • 考虑size方法计算元素个数的问题

一种常见的优化措施是，在插入和移除元素时更新一个计数器，虽然这在put和remove等方法中略微增加了一些开销，但这样可以把size方法的开销从O(n)降低到O(1)。

但问题是对计数器的更新操作也需要进行同步，这又重新回到了使用独占锁的问题。为了避免这个问题，ConcurrentHashMap为每个分段都维护了一个独立的计数，并通过对应的分段锁来维护这个值，而不是维护一个全局计数，然后size方法将每个分段进行枚举并累加其计数即可。

5. 对象池问题

在Jvm的早期版本，对象分配和垃圾回收等操作非常慢，但在后续的版本中，这些操作的性能得到了极大的提高。事实上，现在Java的分配操作已经比C语言的malloc调用更快：在HotSpot 1.4.x和5.0中，new Object的代码大约只需要10条机器指令。

很多开发人员为了使对象能够重复使用，选择用对象池，但对于高开销对象以外的其他对象来说（就是对象比较轻量，构造对象的代价不是很高），将会得不偿失。而且在并发程序中，对象池的表现会更糟，因为如果线程从对象池中请求一个对象，需要通过某种同步来协调对对象池数据结构的访问，从而可能使某个线程阻塞。而这种阻塞的开销将是构造对象时内存分配操作的数百倍，即便能保证对象池带来的竞争很小，也可能形成一个可伸缩性瓶颈。所以，通常对象分配操作的开销比同步的开销更低。对象池有其特定的用途，但对于性能优化来说，用途是有限的。


参考：

  1. Copyright ©《java并发编程实战》