BAT面试官:你先手动用LockSupport实现一个先进先出的不可重入锁?吊炸天

1,838

引言

不知道大家面试的过程有没有遇到过吊炸天的面试官,一上来就说,你先手动实现一个先进先出的不可重入锁。惊不惊喜?激不激动?大展身手的时刻到了,来,我们一起看看下面这个例子

public class FIFOMutex {

    private final AtomicBoolean locked = new AtomicBoolean(false);
    private final Queue<Thread> waiters
        = new ConcurrentLinkedQueue<Thread>();

    public void lock() {
        boolean wasInterrupted = false;
        Thread current = Thread.currentThread();
        waiters.add(current);

        // 只有自己在队首才可以获得锁,否则阻塞自己
        //cas 操作失败的话说明这里有并发,别人已经捷足先登了,那么也要阻塞自己的
        //有了waiters.peek() != current判断如果自己队首了,为什么不直接获取到锁还要cas 操作呢?
        //主要是因为接下来那个remove 操作把自己移除掉了额,但是他还没有真正释放锁,锁的释放在unlock方法中释放的
        while (waiters.peek() != current ||
            !locked.compareAndSet(false, true)) {
            //这里就是使用LockSupport 来阻塞当前线程
            LockSupport.park(this);
            //这里的意思就是忽略线程中断,只是记录下曾经被中断过
            //大家注意这里的java 中的中断仅仅是一个状态,要不要退出程序或者抛异常需要程序员来控制的
            if (Thread.interrupted()) {
                wasInterrupted = true;
            }
        }
        // 移出队列,注意这里移出后,后面的线程就处于队首了,但是还是不能获取到锁的,locked 的值还是true,
        // 上面while 循环的中的cas 操作还是会失败进入阻塞的
        waiters.remove();
        //如果被中断过,那么设置中断状态
        if (wasInterrupted) {
            current.interrupt();
        }

    }

    public void unlock() {
        locked.set(false);
        //唤醒位于队首的线程
        LockSupport.unpark(waiters.peek());
    }

}

上面这个例子其实就是jdk中LockSupport 提供的一个例子。LockSupport 是提供线程的同步原语的非常底层的一个类,如果一定要深挖的话,他的实现又是借用了Unsafe这个类来实现的,Unsafe 类中的方法都是native 的,真正的实现是C++的代码

通过上面这个例子,分别调用了以下两个方法

    public static void park(Object blocker) 
    public static void unpark(Thread thread) 

LockSupport的等待和唤醒是基于许可的,这个许可在C++ 的代码中用一个变量count来保存,它只有两个可能的值,一个是0,一个是1。初始值为0

调用一次park

  1. 如果count=0,阻塞,等待count 变成1
  2. 如果count=1,修改count=0,并且直接运行,整个过程没有阻塞

调用一次unpark

  1. 如果count=0,修改count=1
  2. 如果count=1,保持count=1

多次连续调用unpark 效果等同于一次

所以整个过程即使你多次调用unpark,他的值依然只是等于1,并不会进行累加

源码分析

park

    public static void park(Object blocker) {
        Thread t = Thread.currentThread();
        //设置当前线程阻塞在blocker,主要是为了方便以后dump 线程出来排查问题,接下来会讲
        setBlocker(t, blocker);
        //调用UNSAFE来阻塞当前线程,具体行为看下面解释
        UNSAFE.park(false, 0L);
        //被唤醒之后来到这里
        setBlocker(t, null);
    }

这里解释下UNSAFE.park(false, 0L)。调用这个方法会有以下情况

  1. 如果许可值为1(也就是之前调用过unpark,并且后面没有调用过park来消耗许可),立即返回,并且整个过程不阻塞,修改许可值为0
  2. 如果许可值为0,进行阻塞等待,直到以下三种情况发生会被唤醒
    1. 其他线程调用了unpark 方法指定唤醒该线程
    2. 其他线程调用该线程的interrupt方法指定中断该线程
    3. 无理由唤醒该线程(就是耍流氓,下面会解析)

unpark

    public static void unpark(Thread thread) {
        if (thread != null)
        //通过UNSAFE 来唤醒指定的线程
        //注意我们需要保证该线程还是存活的
        //如果该线程还没启动或者已经结束了,调用该方法是没有作用的
            UNSAFE.unpark(thread);
    }

源码非常简单,直接通过UNSAFE 来唤醒指定的线程,但是要注意一个非常关键的细节,就是这里指定了唤醒的线程,这个跟Object 中的notify 完全不一样的特性,synchronized 的锁是加在对象的监视锁上的,线程会阻塞在对象上,在唤醒的时候没办法指定唤醒哪个线程,只能通知在这个对象监视锁 上等待的线程去抢这个锁,具体是谁抢到这把锁是不可预测的,这也就决定了synchronized 是没有办法实现类似上面这个先进先出的公平锁。

park 和unpark 的调用不分先后顺序

先来个列子


public class LockSupportTest {

    private static final Logger logger = LoggerFactory.getLogger(LockSupportTest.class);

    public static void main(String[] args) throws Exception {
        LockSupportTest test = new LockSupportTest();
        Thread park = new Thread(() -> {
            logger.info(Thread.currentThread().getName() + ":park线程先休眠一下,等待其他线程对这个线程执行一次unpark");
            try {
                Thread.sleep(4000);
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
            logger.info(Thread.currentThread().getName() + ":调用park");
            LockSupport.park(test);
            logger.info(Thread.currentThread().getName() + ": 被唤醒");
        });

        Thread unpark = new Thread(() -> {
            logger.info(Thread.currentThread().getName() + ":调用unpark唤醒线程" + park.getName());
            LockSupport.unpark(park);
            logger.info(Thread.currentThread().getName() + ": 执行完毕");
        });
        park.start();
        Thread.sleep(2000);
        unpark.start();
    }
}

输出结果:

18:52:42.065 Thread-0:park线程先休眠一下,等待其他线程对这个线程执行一次unpark
18:52:44.064 Thread-1:调用unpark唤醒线程Thread-0
18:52:44.064 Thread-1: 执行完毕
18:52:46.079 Thread-0:调用park
18:52:46.079 Thread-0:被唤醒

从结果中可以看到,即使先调用unpark,后调用park,线程也可以马上返回,并且整个过程是不阻塞的。这个跟Object对象的wait()和notify()有很大的区别,Object 中的wait() 和notify()顺序错乱的话,会导致线程一直阻塞在wait()上得不到唤醒。正是LockSupport这个特性,使我们并不需要去关心线程的执行顺序,大大的降低了死锁的可能性。

支持超时

//nanos 单位是纳秒,表示最多等待nanos 纳秒,
//比如我最多等你1000纳秒,如果你还没到,就不再等你了,其他情况跟park 一样
public static void parkNanos(Object blocker, long nanos)
//deadline 是一个绝对时间,单位是毫秒,表示等待这个时间点就不再等
//(比如等到今天早上9点半,如果你还没到,我就不再等你了) ,其他情况跟park 一样
public static void parkUntil(Object blocker, long deadline)

正是有了这个方法,所以我们平时用的ReentrantLock 等各种lock 才可以支持超时等待,底层其实就是借用了这两个方法来实现的。这个也是synchronized 没有办法实现的特性

支持查询线程在哪个对象上阻塞

    public static Object getBlocker(Thread t) {
        if (t == null)
            throw new NullPointerException();
        return UNSAFE.getObjectVolatile(t, parkBlockerOffset);
    }

以前没看源码的时候有个疑问,线程都已经阻塞了,为什么还可以查看指定线程的阻塞在相关的对象上呢?不应该是调用的话也是没有任何反应的的吗?直到看了源码,才知道它其实不是用该线程去直接获取线程的属性,而是通过UNSAFE.getObjectVolatile(t, parkBlockerOffset) 来获取的。这个方法的意思就是获取内存区域指定偏移量的对象

最佳实践

阻塞语句LockSupport.park() 需要在循环体,例如本文一开始的例子

        while (waiters.peek() != current ||
            !locked.compareAndSet(false, true)) {
            //在循环体内
            LockSupport.park(this);
            //唤醒后来到这里
            //忽略其他无关代码
        }

如果不在循环体内会有什么问题呢?假如变成以下代码片段

        if (waiters.peek() != current ||
            !locked.compareAndSet(false, true)) {
            //在循环体内
            LockSupport.park(this);
            //唤醒后来到这里
            //忽略其他无关代码
        }

这里涉及一个线程无理由唤醒的概念,也就是说阻塞的线程并没有其他线程调用unpark() 方法的时候就被唤醒

假如先后来了两个线程A和B,这时候A先到锁,这个时候B阻塞。但是在A还没释放锁的时候,同时B被无理由唤醒了,如果是if,那么 线程B就直接往下执行获取到了锁,这个时候同时A和B都可以访问临界资源,这样是不合法的,如果是while 循环的话,会判断B不是 在队首或者CAS 失败的会继续调用park 进入阻塞。所以大家记得park方法一定要放在循环体内

LockSupport中的 park ,unpark 和Object 中的wait,notify 比较

  1. 他们都可以实现线程之间的通讯
  2. park 和wait 都可以让线程进入阻塞状态
  3. park 和unpark 可以在代码的任何地方使用
  4. wait 和notify,notifyAll 需要和synchronized 搭配使用,必须在获取到监视锁之后才可以使用,例如
synchronized (lock){
 lock.wait()
}
  1. wait 和notify 需要严格控制顺序,如果wait 在notify 后面执行,则这个wait 会一直得不到通知
  2. park 和unpark 通过许可来进行通讯,无需保证顺序
  3. park 支持超时等待,但是wait 不支持
  4. unpark 支持唤醒指定线程,但是notify 不支持
  5. wait 和park 都可以被中断唤醒,wait 会获得一个中断异常

思考题

LockSupport 本质上也是一个Object,那么调用LockSupport的unpark 可以唤醒调用LockSupport.wait() 方法的线程吗?请把你的答案写在留言区

看完两件事

如果你觉得这篇内容对你挺有启发,我想邀请你帮我2个小忙:

  1. 点赞,让更多的人也能看到这篇内容(收藏不点赞,都是耍流氓 -_-)
  2. 关注公众号「面试bat」,不定期分享原创知识,原创不易,请多支持(里面还提供刷题小程序哦)。