十、避免活跃性危险

10.1 死锁

  • 锁顺序死锁：一个锁先锁left 在锁right,另一个锁先锁right再锁left,会发生死锁。

  • 动态的锁顺序死锁

    有时候，并不能清楚地知道是否在锁顺序上有足够的控制权来避免死锁的发生。

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    //注意:容易发生死锁!
    //看似无害的代码，它将资金从一个账户转入另一个账户。在开始转账之前，首先要获得这两个Account对象的锁，以确保通过原子方式来更新两个账户中的余额，同时又不破坏一些不变性条件，例如“账户的余额不能为负数”。
    public void transferMoney (Account fromAccount,
    					Account toAccount ,Dol1arAmount amount)
    		throws InsufficientFundsException {
    	synchronized (fromAccount) {
            synchronized (toAccount) {
            	if (fromAccount.getBalance( ).compareTo (amount) < 0)
                    throw new InsufficientFundsException ( ) ;
            	else {
            		fromAccount.debit (amount) ;
                    toAccount .credit (amount) ;
            }
    	}
    }

    如果两个线程同时转账，一个从X向Y转账，另一个从Y向X转账，就会发生死锁。

    可以使用System.identityHashCode方法，返回hash值，必须通过任意的方法来决定锁定顺序，但仍然有很小道可能发生死锁。

  • 在协作对象之间发送死锁。：这两个锁不一定在同一个方法中被获取。

    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
    //注意:容易发生死锁!
    class Taxi {
    	@GuardedBy ("this") private Point location,destination;//位置和谜底
        private final Dispatcher dispatcher ; //出租车车队
        public Taxi (Dispatcher dispatcher) {
        	this.dispatcher = dispatcher;
        }
        
    	public synchronized Point getLocation ( ) {
    		return location ;
        }
        
    	public synchronized void setLocation (Point location){
    		this.location = location;
    		if ( location. equals(destination))
    			dispatcher.notifyAvailable (this) ;
        }
    class Dispatcher {
    	@GuardedBy ( "this" ) private final set<Taxi> taxis;
    	@GuardedBy( "this" ) private final set<Taxi> availableTaxis;
        public Dispatcher ( ) {
            taxis = new HashSet<Taxi> ();
            avai lableTaxis = new Hashset<Taxi> ( ) ;
        }
        public synchronized void notifyAvailable (Taxi taxi){
        	availableTaxis.add (taxi) ;
        }	
        public synchronized Image getImage ( ) {
            Image image = new Image () ;
            for (Taxi t : taxis)
            	image.drawMarker(t.getLocation ());
            return image ;
        }
    }

    如果一个线程在收到GPS接收器的更新事件时调用setLocation，那么它将首先更新出租车的位置，然后判断它是否到达了目的地。如果已经到达，它会通知Dispatcher : 它需要一个新的目的地。因为setLocation和notifyAvailable都是同步方法，因此调用setLocatior的线程将首先获取Taxi的锁，然后获取 Dispatcher的锁。同样，调用getImage的线程将首先获取 Dispatcher锁，然后再获取每一个Taxi的锁（每次获取一个)。
    如果在持有锁时调用某个外部方法那么将出现活跃性问题。在这个外部方法中可能会荻取其他锁:（这可能会产生死锁）,或者阻塞时间过长，导致其他线程无法及时获得;当前被持有的锁。

  • 开放调用

    如果在调用某个方法时不需要持有锁，那么这种调用被称为开放调用(Open Call)。

    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
    //可以很容易地将Taxi和 Dispatcher修改为使用开放调用，从而消除发生死锁的风险。这需要使同步代码块仅被用于保护那些涉及共享状态的操作，。通常，如果只是为了语法紧凑或简单性（而不是因为整个方法必须通过--个锁来保护）而使用同步方法（而不是同步代码块)，那么就会导致问题。(此外，收缩同步代码块的保护范围还可以提高可伸缩性)
    @Threadsafe
    class Taxi {
     	@GuardedBy ( "this" ) private Point location，destination;
        private final Dispatcher dispatcher ;
    	...
        public synchronized Point getLocation ( ) {
        	return location;
        }
        public void setLocation ( Point location) {
        	boolean reachedDestination ;
        	synchronized(this){
        		this.location = location ;
        		reachedDestination = location.equals(destination) ;
            }
        	if(reachedDestination)
        		dispatcher.notifyAvailable(this) ;
        }
    }
    @Threadsafe
    class Dispatcher {
    	@GuardedBy ( "this" ) private final set<Taxi> taxis;
    	GuardedBy ( "this") private final set<Taxi> availableTaxis ;
        ...
        public synchronized void notifyAvailable (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;
        }
    }

  • 资源死锁

10.2 死锁的避免和诊断

在使用细粒度锁的程序中，可以通过使用一种两阶段策略（Two-Part Strategy）来检查代码中的死锁:首先，找出在什么地方将获取多个锁（使这个集合尽量小)，然后对所有这些实例进行全局分析，从而确保它们在整个程序中获取锁的顺序都保持一致。

  • 支持定时的锁
  • 通过现场转储信息来分析死锁

10.3 其他活跃性问题

  • 饥饿：

    线程由于无法访问它所需的资源而不能继续执行，就发生了饥饿。（CPU时钟周期）

  • 糟糕的响应性

  • 活锁

    活锁(Livelock)是另一种形式的活跃性问题，该问题尽管不会阻塞线程，但也不能继续执行，因为线程将不断重复执行相同的操作，而且总会失败。活锁通常发生在处理事务消息的应用程序中﹔如果不能成功地处理某个消息，那么消息处理机制将回滚整个事务，并将它重新放到队列的开头。如果消息处理器在处理某种特定类型的消息时存在错误并导致它失败，那么每当这个消息从队列中取出并传递到存在错误的处理器时，都会发生事务回滚。由于这条消息又被放回到队列开头，因此处理器将被反复调用，并返回相同的结果。

    要解决这个问题需要在重试机制上加入随机性。在并发程序中，通过等待随机长度的时间和回退可以有效的避免活锁

十一、性能与可伸缩性

11.1 对性能的思考

要想通过并发来获得更好的性能，需要努力做好两件事情:更有效地利用现有处理资源，以及在出现新的处理资源时使程序尽可能地利用这些新资源。

性能与可伸缩性

应用程序的性能可以采用多个指标来衡量，例如服务时间、延迟时间、吞吐率、效率、可伸缩性以及容量等。其中一-些指标（服务时间、等待时间〉用于衡量程序的“运行速度”，即某个指定的任务单元需要“多快”才能处理完成。另一些指标（生产量、吞吐量〉用于程序的“处理能力”，即在计算资源一定的情况下，能完成“多少”工作。
可伸缩性指的是，当增加计算资源时程序的吞吐量或者处理能力能理应地增加。

11.2 Amdahl定律

Amdahl定律描述的是﹔在增加计算资源的情况下，程序在理论上能够实现最高加速比，这个值取决于程序中可并行组件与串行组件所占的比重。

假设应用程序中N个线程正在执行，这些线程从一个共享的工作队列中取出任务进行处理，而且这里的任务都不依赖于其他任务的执行结果或影响。暂时先不考虑任务是如何进入这个队列的，如果增加处理器，那么应用程序的性能是否会相应地发生变化?初看上去，这个程序似乎能完全并行化:各个任务之间不会相互等待，因此处理器越多,能够并发处理的任务也就越多。然而，在这个过程中包含了一个串行部分—从队列中获取任务。所有工作者线程都共享同一个工作队列，因此在对该队列进行并发访问时需要采用某种同步机制来维持队列的完整性。如果通过加锁来保护队列的状态，那么当一个线程从队列中取出任务时，其他需要获取下一个任务的线程就必须等待，这就是任务处理过程中的串行部分。

单个任务的处理时间不仅包括执行任务Runnable的时间，也包括从共享队列中取出任务的时间。如果使用LinkedBlockingQueue作为工作队列，那么出列操作被阻塞的可能性将小于使用同步LinkedList时发生阻塞的可能性，因为LinkedBlockingQueue使用了一种可伸缩性更高的算法。然而，无论访问何种共享数据结构，基本上都会在程序中引入一个串行部分。
这个示例还忽略了另一种常见的串行操作:对结果进行处理。所有有用的计算都会生成某种结果或者产生某种效应——如果不会，那么可以将它们作为“死亡代码”删除掉。由于Runnable没有提供明确的结果处理过程，因此这些任务一定会产生某种效果，例如将它们的结果写入到日志或者保存到某个数据结构。通常，日志文件和结果容器都会由多个工作者线程共享，并且这也是一个串行部分。如果所有线程都将各自的计算结果保存到自行维护数据结构中，并且在所有任务都执行完成后再合并所有的结果，那么这种合并操作也是一个串行部分。

11.3 线程引入的开销

  • 上下文切换

    如果主线程是唯一的线程，那么它基本上不会被调度出去。另一方面，如果可运行的线程数大于CPU的数量，那么操作系统最终会将某个正在运行的线程调度出来，从而使其他线程能够使用CPU。这将导致一次上下文切换，在这个过程中将保存当前运行线程的执行上下文，并将新调度进来的线程的执行上下文设置为当前上下文。

  • 内存同步

    在synchronized和volatile提供的可见性保证中可能会使用一些特殊指令，即内存栅栏(Memory Barrier)。内存栅栏可以刷新缓存，使缓存无效，剧新硬件的写缓冲，以及停止执行管道。内存栅栏可能同样会对性能带来间接的影响，因为它们将抑制-些编译器优化操作。在内存栅栏中，大多数操作都是不能被重排序的。
    现代的JVM能通过优化来去掉一些不会发生竞争的锁，从而减少不必要的同步开销。如果一个锁对象只能由当前线程访问，那么JVM就可以通过优化来去掉这个锁获取操作

  • 阻塞

11.4 减少锁的竞争

有两个因素将影响在锁上发生竞争的可能性:锁的请求频率，以及每次持有该锁的时间。如果二者的乘积很小，那么大多数获取锁的操作都不会发生竞争，因此在该锁上的竞争不会对可伸缩性造成严重影响。然而，如果在锁上的请求量很高，那么需要获取该锁的线程将被阻塞并等待。在极端情况下，即使仍有大量工作等待完成，处理器也会被闲置。

  • 缩小锁的范围

  • 减小锁的粒度

    降低线程请求锁的频率，锁分解和锁分段。

  • 锁分段

  • 避免热点域

    将一些反复计算的结果缓存起来

  • 一些代替独占锁的方法

    • ReadWriteLock 读取不加锁，写加锁
    • 原子变量

11.5 比较Map的性能

在单线程环境下，ConcurrentHashMap 的性能比同步的HashMap 的性能略好一些，但在并发环境中则要好得多。
在同步Map的实现中，可伸缩性的最主要阻碍在于整个 Map中只有一个锁，因此每次只有一个线程能够访问这个 Map。不同的是，ConcurrentHashMap对于大多数读操作并不会加锁,并且在写人操作以及其他一些需要锁的读操作中使用了锁分段技术。因此，多个线程能并发地访问这个Map而不会发生阻塞。
ConcurrentHashMap,ConcurrentSkipListMap,以及通过synchronizedMap来包装的HashMap 和TreeMap。前两种Map是线程安全的，而后两种通过同步容器确保线程安全性。

11.6 减少上下文切换的开销

在许多任务中都包含一些可能被阻塞的操作。当任务在运行和阻塞这两个状态之间转换时，就相当于一次上下文切换。在服务器应用程序中，发生阻塞的原因之一就是在处理请求时产生各种日志消息。

在大多数日志框架中都是简单地对println进行包装，当需要记录某个消息时，只需将其写人日志文件中。在第7章的LogWriter中给出了另一种方法:记录日志的工作由一个专门的后台线程完成，而不是由发出请求的线程完成。从开发人员的角度来看，这两种方法基本上是相同的。但二者在性能上可能存在一些差异，这取决于日志操作的工作量，即有多少线程正在记录日志，以及其他一些因素，例如上下文切换的开销等。
日志操作的服务时间包括与I/О流类相关的计算时间，如果IО操作被阻塞，那么还会包括线程被阻塞的时间。
请求服务的时间不应该过长，主要有以下原因。首先，服务时间将影响服务质量:服务时间越长，就意味着有程序在获得结果时需要等待更长的时间。但更重要的是，服务时间越长，也就意味着存在越多的锁竞争。

十二、并发程序的测试

有两类测试：安全性测试和活跃性测试。

在进行安全性测试时，通常会采用测试不变性条件的形式，即判断某个类的行为是否与其规范保持一致。例如，
测试活跃性本身也存在问题。活跃性测试包括进展测试和无进展测试两方面，这些都是很难量化的——如何验证某个方法是被阻塞了，而不只是运行缓慢﹖同样，如何测试某个算法不会发生死锁﹖要等待多久才能宣告它发生了故障?
与活跃性测试相关的是性能测试。性能可以通过多个方面来衡量，包括:

  • 吞吐量:指一组并发任务中已完成任务所占的比例。
  • 响应性．指请求从发出到完成之间的实际
  • 可伸缩性：在增加更多的资源情况下，吞吐量的提示情况。