死锁问题2例

死锁问题2例

2020-05-30
Java
并发

Java有能力使任务为等待某些条件成立而进入阻塞状态，所以就有可能出现这样一种情况：某个任务在等待另一个任务，而后者又在等待其他的任务，这样一直等待下去，直到等待链上的最后一个任务又在等待第一个任务释放锁，这样就出现了任务之间相互等待的连续循环现象，这种情况出现之后，没有哪个任务能够执行，于是 死锁 出现。

死锁之所以难以规避，其重要的原因就在于其不确定性，可能程序运行良好，但是有潜在的死锁风险，这个风险在某些域的初始条件变化时，变得特别大，导致程序很快死锁。同时，死锁难以复现，当程序出现死锁时，往往只能通过jvm的堆栈日志来探究原因。

我们不妨回顾在 转账问题中使用的等待条件——账户余额不足时使任务等待，在余额足够的时候再进行转账。这个程序没有问题，因为有100个账户每个账户初始金额1000元，而转账金额不大于初始金额，所以任一时刻都会有账户的金额满足转账条件。如果去除转账金额不大于1000的限制，死锁就会发生。

比如有2个账户

账户A 余额200元
账户B 余额300元

账户A向账户B转账300元，余额不足等待；账户B向账户A转账400，余额不足等待；程序就进入死锁。

上面描述的死锁，线程的状态并不是BLOCKED，而是WAITING。资源上所有的线程都进入等待，实际上锁并没有被占用，但是程序无法被唤醒而继续运行。

还有一种死锁，即线程的状态是BLOCKED，这种情形在使用多把锁时容易出现。

抢票问题 #

下面的示例模拟一个放票与抢票的场景，单线程的放票任务与多线程的抢票任务同时执行，直到停止放票并且所有票售罄程序结束。为了尽可能让更多的任务抢到票，任务中做了特殊处理。

以下示例代码只为阐述因使用Object.wait()方法，且程序逻辑严密性存在问题的情形下，出现死锁的可能。并不能作为开发实践。

程序使用了Callable接口和ThreadLocal来获取每个任务抢到的票数。

  1public class TicketIssue {
  2
  3    protected final Tick tick = new Tick(0);
  4    private final List<Future<TV>> resultList = new ArrayList<>();
  5
  6    static class Tick {
  7        // 一般将共享资源设置为私有以降低同步问题的复杂性
  8        int tickCount;
  9        boolean isTickSupply = true;
 10
 11        public Tick(int tick) {
 12            this.tickCount = tick;
 13        }
 14
 15        boolean getTick() {
 16            if (isTick()) {
 17                tickCount--;
 18                if (getTickCount() < 0) {
 19                    System.out.println("余票数 " + tickCount + "不合法，系统错误！");
 20                    System.exit(0);
 21                }
 22                return true;
 23            }
 24            return false;
 25        }
 26
 27        // 检查余票
 28        boolean isTick() {
 29            return tickCount > 0;
 30        }
 31
 32        // 获取余票
 33        int getTickCount() {
 34            return tickCount;
 35        }
 36
 37        // 停止放票
 38        void cancelSupply() {
 39            isTickSupply = false;
 40        }
 41    }
 42
 43    @Setter
 44    @Getter
 45    static class TV {
 46        Thread t;
 47        Integer v = 0;
 48    }
 49
 50    static class Purchase implements Callable<TV> {
 51
 52        // 线程抢到的票计数器
 53        // 线程内部存储一般声明为static
 54        private static final ThreadLocal<TV> tl 
 55                = ThreadLocal.withInitial(TV::new);
 56
 57        private final Tick tick;
 58
 59        Purchase(Tick tick) {
 60            this.tick = tick;
 61        }
 62
 63        /*
 64            此处在run/call方法里同步
 65         */
 66        @Override
 67        public TV call() {
 68            while (true) {
 69                synchronized (tick) {
 70                    TV tv = tl.get();
 71                    tv.setT(Thread.currentThread());
 72                    if (tick.getTick()) {
 73                        tv.setV((tv.getV() == null ? 0 : tv.getV()) + 1);
 74                        tl.set(tv);
 75//                        System.out.println(Thread.currentThread().getName() 
 76//                              + " 抢到票, 余票数: " + tick.getTickCount());
 77                        try {
 78                            // 给其他线程机会
 79                            tick.wait();
 80                        } catch (InterruptedException e) {
 81                            e.printStackTrace();
 82                        }
 83                    } else {
 84                        tick.notifyAll();
 85                        if (!tick.isTickSupply) break;
 86                    }
 87                }
 88            }
 89            return tl.get();
 90        }
 91    }
 92
 93    void multiPurchase(int threadCount) 
 94        throws InterruptedException, ExecutionException {
 95
 96        ExecutorService pool = Executors.newCachedThreadPool();
 97        for (int i = 0; i < threadCount; i++) {
 98            Future<TV> future = pool.submit(new Purchase(tick));
 99            resultList.add(future);
100        }
101        pool.shutdown();
102
103        int sum = 0;
104        for (int i = 0; i < resultList.size(); i++) {
105            TV tv = resultList.get(i).get();
106            System.out.println(tv.getT().getName() 
107                    + " 抢到票：" + tv.getV() + "张");
108            sum = sum + tv.getV();
109        }
110        System.out.println("已购票数：" + sum);
111    }
112
113    /** 放票 */
114    void singleSupply(int count) {
115
116        new Thread(() -> {
117            for (int i = 0; i < count; i++) {
118                // 此处不使用同步不影响最终结果，线程会一直抢票
119                // 即使某刻读取到了未刷新的tickCount数值，最终都会抢到票
120                tick.tickCount++;
121                // 降低出票速率
122                try {
123                    TimeUnit.MILLISECONDS.sleep(2);
124                } catch (InterruptedException e) {
125                    e.printStackTrace();
126                }
127            }
128            // 停止放票
129            tick.cancelSupply();
130        }).start();
131    }
132
133
134    public static void main(String[] args) throws Exception {
135
136        TicketIssue ti = new TicketIssue();
137        int count = 10 ,  threadHold = 10;
138        if (args.length > 1){
139            count = Integer.parseInt(args[0]);
140        }
141        if (args.length > 2){
142            threadHold = Integer.parseInt(args[1]);
143        }
144        ti.singleSupply(count);
145        ti.multiPurchase(threadHold);
146    }
147}
148/* output (sample)
149pool-1-thread-1 抢到票：2张
150pool-1-thread-2 抢到票：2张
151pool-1-thread-3 抢到票：2张
152pool-1-thread-4 抢到票：0张
153pool-1-thread-5 抢到票：0张
154pool-1-thread-6 抢到票：0张
155pool-1-thread-7 抢到票：0张
156pool-1-thread-8 抢到票：1张
157pool-1-thread-9 抢到票：0张
158pool-1-thread-10 抢到票：3张
159已购票数：10
160*///:~

程序接受2个参数1，第一个为放票数，第二个为抢票线程数，这两个参数的默认值都是10，运行程序我们可以看到每个线程所抢到的票数。

在call()方法中，为了避免某一任务独占cpu时间，我们让每个抢到票的线程进入等待，若某个线程没有抢到票，则唤醒之。因为放票是有时间间隔的，所以肯定存在某个没有抢到票的线程能够唤醒之前抢到票的线程。

到目前为止，程序看起来都运行正常。但是，如果抢票线程数远小于票数，或者放票间隔很小(甚至没有间隔)的情况下，死锁很快就会发生。比如我们使用2个线程抢10张票，那么很快将会看到死锁，这是一个很明显的因逻辑漏洞而出现死锁的情况。

破坏这个死锁的方法也很简单，不让获得票的任务进入永久等待，使用带参数的wait(timeout)方法或者使用休眠即可。

哲学家就餐问题 #

这个问题2的描述是指定5个哲学家，他们将花部分时间思考，花部分时间就餐。当他们思考的时候，不需要任何共享资源；但当他们就餐时，将使用有限数量的餐具。哲学家们围坐在桌子周围，每人之间放一支筷子（总之筷子和哲学家数量相同），当哲学家想要就餐时，他必须同时获得左边和右边的筷子，如果这个哲学家的左边或者右边已经有人使用筷子了，那么哲学家必须等待，直到他可以获得筷子。

代码片段1:

 1public class PhilosopherDeadLocking {
 2
 3    protected final int id;
 4    protected final int ponderFactor;
 5
 6    public PhilosopherDeadLocking(int id, int ponderFactor) {
 7        this.id = id;
 8        this.ponderFactor = ponderFactor;
 9    }
10
11    protected void pause() throws InterruptedException {
12        Random rand = new Random(47);
13        if (ponderFactor == 0) {
14            return;
15        }
16        TimeUnit.MILLISECONDS.sleep(rand.nextInt(ponderFactor * 250));
17    }
18
19    @Override
20    public String toString() {
21        return "Philosopher " + id;
22    }
23
24    static class Chopstick {
25        private boolean taken;
26
27        private synchronized void take() throws InterruptedException {
28            while (taken) {
29                wait();
30            }
31            taken = true;
32        }
33
34        private synchronized void drop() {
35            taken = false;
36            notifyAll();
37        }
38    }

哲学家有一个构造参数ponderFactor，用来控制哲学家思考的时间；当调用take()方法拿起筷子时，它要先判断筷子是否已经被使用，如果是则进入等待，否则获得筷子并将taken置为true；当调用drop()方法放下筷子时，将taken置为false并唤醒所有在等待使用这个筷子的哲学家。

代码片段2:

 1    static class Dinner implements Runnable {
 2        private Chopstick left;
 3        private Chopstick right;
 4        private PhilosopherDeadLocking philosopherDeadLocking;
 5
 6        public Dinner(Chopstick left, 
 7                                Chopstick right, 
 8                                PhilosopherDeadLocking phi) {
 9            this.left = left;
10            this.right = right;
11            this.philosopherDeadLocking = phi;
12        }
13
14        @Override
15        public void run() {
16            try {
17                while (!Thread.interrupted()) {
18                    System.out.println(philosopherDeadLocking 
19                        + " " + "thinking");
20                    philosopherDeadLocking.pause();
21                    // Philosopher becomes hungry
22                    System.out.println(philosopherDeadLocking 
23                        + " " + "grabbing right");
24                    right.take();
25                    System.out.println(philosopherDeadLocking 
26                        + " " + "grabbing left");
27                    left.take();
28                    System.out.println(philosopherDeadLocking 
29                        + " " + "eating");
30                    philosopherDeadLocking.pause();
31                    System.out.println(philosopherDeadLocking 
32                        + " " + "drop right");
33                    right.drop();
34                    System.out.println(philosopherDeadLocking 
35                        + " " + "drop left");
36                    left.drop();
37                }
38            } catch (InterruptedException e) {
39                System.out.println(philosopherDeadLocking 
40                    + " " + "exiting via interrupt");
41            }
42        }
43    }

在哲学家就餐的run()方法中，哲学家只是不停的思考和吃饭，如果ponderFactor不为0，那么哲学家先会思考一会儿，然后拿起右边的筷子，再拿起左边的筷子，然后在吃饭上花掉一会时间，然后放下筷子，之后重复此过程。

代码片段3:

 1    public static void main(String[] args) throws Exception {
 2        ExecutorService pool = Executors.newCachedThreadPool();
 3        int size = 5, ponder = 0;
 4        if (args.length > 0) {
 5            ponder = Integer.parseInt(args[0]);
 6        }
 7        if (args.length > 1) {
 8            size = Integer.parseInt(args[1]);
 9        }
10        Chopstick[] chopsticks = new Chopstick[size];
11
12        for (int i = 0; i < size; i++) {
13            chopsticks[i] = new Chopstick();
14        }
15        for (int i = 0; i < size; i++) {
16            pool.execute(
17                new Dinner(chopsticks[i],
18                                     chopsticks[(i + 1) % size],
19                                    new PhilosopherDeadLocking(i, ponder)));
20        }
21
22        if (args.length > 2) {
23            TimeUnit.SECONDS.sleep(Integer.parseInt(args[2]));
24        } else {
25            System.out.println("Press 'q' to quit");
26            System.in.read();
27        }
28        pool.shutdownNow();
29    }
30}

main()方法接受3个命令行参数，分别是ponderFactor，筷子数，以及程序结束前运行的时间（程序需要主动结束运行）。这个程序的特别之处在于，它大部分时间是正常运行的——如果哲学家花在思考上的时间足够长，那么死锁可能永远不可能发生，但是如果将ponderFactor设置为0，那么死锁将很快会发生。

因为每个哲学家都是先拿右边的筷子，后拿左边的筷子，如果哲学家思考的时间很短，就会出现所有的哲学家都拿到了右边的筷子，并等待左边的筷子的情况，如此一来，所有的哲学家都陷入了“等待的陷阱”，这就是循环等待的情形，此时程序的死锁就发生了。如果让最后一位哲学家先拿左边的筷子而非右边的筷子，那么就可以破坏循环等待的条件，阻止死锁的发生：

 1public static void main(String[] args) throws Exception {
 2    ExecutorService pool = Executors.newCachedThreadPool();
 3    int size = 5, ponder = 0;
 4    if (args.length > 0) {
 5        ponder = Integer.parseInt(args[0]);
 6    }
 7    if (args.length > 1) {
 8        size = Integer.parseInt(args[1]);
 9    }
10    Chopstick[] chopsticks = new Chopstick[size];
11
12    for (int i = 0; i < size; i++) {
13        chopsticks[i] = new Chopstick();
14    }
15    for (int i = 0; i < size - 1; i++) {
16        pool.execute(
17            new Dinner(chopsticks[i],
18            chopsticks[(i + 1) % size], 
19            new PhilosopherDeadLocking(i, ponder)));
20    }
21
22    // 让最后一位哲学家先拿左边的筷子，破坏可能发生的循环等待
23    pool.execute(
24        new Dinner(chopsticks[0],chopsticks[size -1], 
25        new PhilosopherFixDeadLocking(size-1, ponder)));
26
27    if (args.length > 2) {
28        TimeUnit.MILLISECONDS.sleep(Integer.parseInt(args[2]));
29    } else {
30        System.out.println("Press 'q' to quit");
31        System.in.read();
32    }
33    pool.shutdownNow();
34}

就死锁而言，Java并没有就此提供语言上的支持，能否通过仔细地设计程序逻辑来避免死锁，取决于你。

  1. 这个程序使用同步的方式只是为了说明问题，并不是最好的同步方式。 ↩︎

  2. 这是由Edsger Dijkstra提出的一个经典的死锁例证，参考自《Java编程思想 第四版》 ↩︎

← 获取任务的返回值
终结任务 →
相似文章
获取任务的返回值
synchronized关键字
原子性和可见性

Notes and Memos by wangy325 © CC BY 4.0

2019-2025. Powered by Hugo Book Presented by Github.