技术成就梦想

死锁、饥饿和活锁 原 死锁、饥饿和活锁 霍淇滨



死锁:

经典例子:“哲学家进餐”问题

死锁的解决:

数据库服务器解决死锁:数据库系统中考虑了检测死锁和从死锁中恢复。当数据库服务器检测到死锁时(通常在表示等待关系的有向图中搜索循环),将选择一个牺牲者并放弃这个事务。作为牺牲者的事务会放弃它持有的所有资源,从而使其他事务继续执行。然后可以重新执行被强制终止的事务。

JVM解决死锁:JVM在解决死锁只能终止并重启。

死锁的产生:

锁顺序死锁:

两个线程试图以不同的顺序来获得相同的锁,那么就用可能发生死锁。

public class LeftRightLock{
    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();
            }
        }
    }    
}

解决方法:如果所有线程以固定的顺序来请求锁,那么在程序中就不会出现锁顺序死锁问题。

动态的锁顺序死锁:

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

public void transferMoney(Account fromAccount, Account toAccount){
    synchronized(fromAccount){
        synchronized(toAccount){
            doSomething();
        }
    }
}

上述方法可以用来实现A和B的转账,看似安全,但也有可能发生死锁。所有线程似乎都是按照相同的顺序来获得锁,实则不是。这里获得锁的顺序和传入的参数顺序有关,而这些参数又取决于外部输入。如果两个线程同时调用transferMoney方法,其中一个线程从X向Y转账,并一个线程从Y向X转账,嘛呢就会发生死锁:

  • A线程:transferMoney(myAccount, yourAccount);
  • B线程:transferMoney(yourAccount, myAccount);

那么该问题应该如何解决?要解决这种死锁,必须定义锁的顺序,在整个应用程序中都要按照这个顺序来获取锁。

定义锁的顺序可以使用System.identityHashCode方法,可以先获取所有要加锁对象的哈希值,每次要嵌套锁的时候都先获取哈希值大的对象,再获取哈希值小的对象。

int formHash = System.identityHashCode(formAcct);
int toHash = System.indntityHashCode(toAcct);

if(formHash < toHash){
    synchronized(toHash){
        synchronized(fromHash){
            doSomething();
        }
    }
}else{
    synchronized(fromHash){
        synchronized(toHash){
            doSomething();
        }
    }
}

在协作对象之间发生的死锁:

有时候获取多个锁的操作并不像前两个例子那么明显,这两个锁并不一定在同一个方法中获取。

class Taxi{
    @GuardedBy("this") private Point location, destination;
    private final Dispacher dispacher;
    
    public Taxi(Dispacher dispacher){ this.dispacher = dispacher; }
    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<Texi> taxis;
    @GuardedBy("this") private final Set<Texi> availableTaxis;
    
    public Dispatcher(){ 
        taxis = new HashSet<Taxi>();  
        availableTaxis = new HashSet<Taxi>();
    }

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

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

尽管没有任何方法会显式获取两个锁,但setLocation和getImage等方法的调用者都会获得两个锁。如果一个线程在收到GPS更新事件时会调用setLocation,它会更新位置,然后判断是否到达的目的地,如果到达了,则会通知Dispatcher:获得一个新的目的地。因为setLocation和notifyAvailable都是同步方法,因此调用setLocation会先获取Texi的锁,然后获取Dispatcher的锁。同样,调用getImage会先获取Dispatcher的锁,再获取Taxi的锁。所以改代码可能发生死锁。

解决方法:通过开放调用来解决。

开放调用:

方法调用相当于一种抽象屏障,因而无需了解在被调用方法中被执行的操作。正是该原因,在持有锁的时候对调用某个外部方法难以进行分析,从而可能导致死锁。

如果在调用某个方法时不需要持有锁,这种调用被称为开放调用。依赖于开放调用的类通常能表现出更好的行为,并且与那些在调用方法时需要持有锁的类相比,也更容易编写。

下面代码对Texi和Dispatcher进行来写,通过开放调用使得同步代码块仅用于保护那些涉及共享的操作,从而消除了发生死锁的风险(避免了锁嵌套)。

class Taxi{
    @GuardedBy("this") private Point location, destination;
    private final Dispacher dispacher;
    ...
    public void setLocation(Point location){
        boolean reacherDestination;
        synchronized (this){
            this.location = location;
            reacherDestination = location.equals(destination);
        }
        if(reacherDestination)
            dispatcher.notifyAvailable(this);
    }
}

class Dispatcher{
    @GuardedBy("this") private final Set<Texi> taxis;
    @GuardedBy("this") private final Set<Texi> availableTaxis;
    ...
    public synchronized Image getImage(){
        Set<Taxi> copy;
        synchronized (this){
            copy = new HashSet<Taxi>(taxis);
        }
        Image image = new Inage();
        for(Taxi t: taxis)
            image.drawMarker(t.getLocation());
         return image();
    }
}
    

资源死锁:

上面几种情况都是多个线程互相持有彼此正在等待的锁而又不释放自己持有的锁时产生的死锁。当多个线程在相同资源集合上等待时,也会发生死锁。

资源死锁的典型例子:银行家算法

饥饿:

当线程无法访问它所需要的资源而不能继续执行时,就发生了饥饿现象。引发饥饿最常见的资源就是CPU时钟周期。如果在Java应用程序中对线程的优先级使用不当,或者在持有锁的时候执行一些无法结束的结构,那么也可能导致饥饿。

通常尽量不要更改线程的优先级,只要改变了线程的优先级,程序的行为就将与平台相关,并且会导致发生饥饿的风险。

活锁:

活锁是另一种形式的活跃性问题。该问题尽管不会阻塞线程,但也不能继续执行,因为线程将不断重复同样的操作,而且总会失败。活锁通常发生在处理事务消息中:如果不能成功处理某个消息,那么消息处理机制将回滚事务,并将它重新放到队列的开头。这样,错误的事务被一直回滚重复执行。这种形式的活锁通常是由过度的错误恢复代码造成的,因为它错误地将不可修复的错误认为是可修复的错误。

当多个相互协作的线程都对彼此进行相应而修改自己的状态,并使得任何一个线程都无法继续执行时,就导致了活锁。这就像两个过于礼貌的人在路上相遇:他们彼此让路,然后在另一条路上相遇,然后他们就一直这样避让下去。

要解决这种活锁问题,需要在重试机制中引入随机性。例如在网络上发送数据包,如果检测到冲突,都要停止并在一段时间后重发。如果都在1秒后重发,还是会冲突。所以引入随机性可以解决该类问题。