昨天我听到有人说面试问双缓冲队列,略感好奇于是搜了一下这是个什么数据结构。

引用网上的一段话:

传统队列是生产者线程和消费者线程从同一个队列中存取数据,必然需要互斥访 问,在互相同步等待中浪费了宝贵的时间,使队列吞吐量受影响。双缓冲队使用两个队列,将读写分离,一个队列专门用来读,另一个专门用来写,当读队列空或写 队列满时将两个队列互换。这里为了保证队列的读写顺序,当读队列为空且写队列不为空时候才允许两个队列互换

看起来挺不错的,于是我就尝试着自己写一个出来。首先凭直觉把put和take方法写出来

    @Override
    public void put(T e) throws InterruptedException {
        // TODO Auto-generated method stub
        synchronized (queueP) {
            queueP.offer(e);
        }
    }

    @Override
    public T take() throws InterruptedException {
        // TODO Auto-generated method stub
        synchronized (queueC) {
            if (queueC.isEmpty()) {             
                while (queueP.isEmpty()) ;
                synchronized (queueP) {
                    Queue<T> tmp = queueC;
                    queueC = queueP;
                    queueP = tmp;
                }
            }
            return queueC.poll();
        }
    }

queueP和queueC是两个LinkedList,分别是生产者的写队列和消费者的读队列,为了保证可见性全部声明为volatile。

写完就觉得不科学,用synchronized对list加锁,而在锁保护中又去swap两个list的引用,感觉肯定有坑,应该用ReetrantLock比较好。不过还是试着跑了一下,果不其然有bug。这个bug是:有一定概率消费者在

while (queueP.isEmpty()) ;

进入死循环,同时全部生产者也无法继续运行。

为了简化情景我把生产者和消费者的数目都设为1个,问题依然存在,用jstack打出线程快照,没有死锁,里面关键片段如下:

"c2-0" #11 prio=5 os_prio=0 tid=0x000000001d51b800 nid=0x46a0 runnable [0x000000001de4e000]
   java.lang.Thread.State: RUNNABLE
    at dbq.DoubleBufferQueue.take(DoubleBufferQueue.java:44)
    - locked <0x000000076f2083b8> (a java.util.LinkedList)
    at dbq.Test$ToyConsumer.run(Test.java:91)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - None
    
"p2-0" #10 prio=5 os_prio=0 tid=0x000000001d519800 nid=0xbc4 waiting for monitor entry [0x000000001dd4e000]
   java.lang.Thread.State: BLOCKED (on object monitor)
    at dbq.DoubleBufferQueue.put(DoubleBufferQueue.java:33)
    - waiting to lock <0x000000076f2083b8> (a java.util.LinkedList)
    at dbq.Test$ToyProducer.run(Test.java:58)
    at java.lang.Thread.run(Thread.java:745)

   Locked ownable synchronizers:
    - None

DoubleBufferQueue.java的44行就是那个while循环。问题很清楚,消费者在循环时持有queueP的锁,而生产者一直无法获取锁往queueP写入,queueP为空消费者就一直循环下去,一个典型的饥饿问题

看到这个我的第一反应是难道while循环会对list加锁?为什么呢?莫非是JVM的什么奇怪动作?随后我打开-XX:+PrintComplation参数,没有发现什么奇怪的,查了一下JVM的一些优化参数,也没法先有什么相关的东西,再加上-Xint参数使用纯解释模式执行,问题依然存在。

最后我终于想明白了,问题还是出现在交换引用那个地方。复盘一下饥饿发生的情况。主要有这么几步:

  1. 消费者c2-0进入交换引用的部分,执行完queueC = queueP之后时间片用尽,挂起。此时c2-0持有queueC和queueP两个锁。

  2. 生产者p2-0试图对queueP加锁,失败,阻塞挂起。

  3. c2-0恢复运行,执行了queueP = tmp后释放原来的queueP,再return之后释放原来的queueC,然后c2-0进入第二次take()调用,试图在现在的queueC上加锁。注意:此时试图加锁的queueC和p2-0挂起前试图加锁的queueP是同一个对象,因为p2-0刚好在交换进行到一般的时候来试图加锁并被挂起。

  4. 后申请锁的c2-0却先获得了锁,进入while循环,发现queueP为空,一直循环,而生产者也在等待同一个锁,无法写入


原因清除了,总结经验教训:

  1. ReetrantLock是个好东西,synchronized对于引用会改变的对象,完全就是显而易见的坑。

  2. 线程之间的运行顺序等行为非常难以琢磨,cpu跑那么快,什么事都会发生。除了Happens-Before原则,不要假设任何顺序

  3. jstack的信息并不是说while循环对list加了锁,上面jstack给出的结果中,3、4行的意思是线程运行在44行,且线程持有锁,这两者没关联,这是造成我一开始思路错误的原因。

最后贴一个图:理想中的多线程;现实中的多线程

62ce04ffjw1en049de62fj20gy0y90x7.jpg