拼多多 D2面试,现场编程模拟拼团,10人拼团成功。限时2分钟!开始吧.....!
在面试过程经常有算法题、模拟现实案例、经典功能设计、核心原理分析等。这些看似简单,实际需要候选人有非常扎实的基础,才能应付这些八股考古面试。
和之前文章一样,我们通过现实案例出发,最后抛出主角的方式,带大家由浅入深地了解并发编程核心知识点。
一、面试真题:模拟拼团
我们利用CountDownLatch倒计时的特性,多线程并发条件下,多线程可以调用CountDownLatch.countDown()方法进行减1,然后等候信号的线程调用CountDownLatch.await()方法,等待CountDownLatch倒数为0,会被唤醒继续执行。
package lading.java.mutithread; import java.util.HashSet; import java.util.concurrent.CountDownLatch; import java.util.concurrent.TimeUnit; /** * 模拟拼团,满10人成团 */ public class Demo009CountDownLatch { public static int total = 10;//成团人数 public static CountDownLatch buySuccess = new CountDownLatch(total);//倒数门闩 public static HashSet<String> customersName = new HashSet<>(); public static void main(String[] args) throws InterruptedException { //10个线程,模拟10个客户参团,参团后CountDownLatch.countDown(); for (int i = 0; i < total; i++) { new Thread(() -> { try { Thread.sleep(3000); } catch (InterruptedException e) { throw new RuntimeException(e); } System.out.println(Thread.currentThread().getName()); buySuccess.countDown();//参团后,计数减一 customersName.add(Thread.currentThread().getName()); }, "客户" + (i + 1) + "参团").start(); } //主线程进行超限等待阻塞,如果CountDownLatch值为0,会被唤醒;如果超时也会唤醒继续执行 buySuccess.await(5, TimeUnit.SECONDS);//限时5秒,5秒不成团就超时 //判断是否参团成功 if (customersName.size() == total) { System.out.println("拼团成功,参团客户有:" + customersName); } else { System.out.println("拼团失败,参团客户数量不足" + total + ",目前参数人数为:" + customersName); } } }
二、说说CountDownLatch的核心原理
看了CountDownLatch源码,发现这个也是JUC家族兄弟,和之前说的《Semaphore信号量剖析》、《ReentrantLock核心原理剖析》有非常多相似的地方,都是AQS实现。AQS原理我们之前也专门说过《AQS原理剖析》,以及AQS底层通过CAS的实现,这个《JUC包之CAS原理》也有详细剖析。
先看一下CountDownLatch类结构图,是JUC包里几个兄弟里代码最少最简单的一个。
其中唯一的内部类Sync,实现了AQS队列同步器。AQS里面的核心变量volatile int state,就是个共享变量。new CountDownLatch(count )构造器变量count实际就是AQS的state。通过多线程countDown()去修改state值,达到多线程协同效果。
CountDownLatch核心方法就2个,非常简单:
await():调用该方法的线程进行阻塞,等待count值为0被唤醒,继续执行。以及可以设置超时时间,超时后,该阻塞线程就会重行执行。
countDown():就是减一。源码如下,获取到state值后,通过CAS去减1.里面没有竞争锁的逻辑,也没有公平锁、非公平锁这些。
protected boolean tryReleaseShared(int releases) { // Decrement count; signal when transition to zero for (;;) { int c = getState(); if (c == 0) return false; int nextc = c-1; if (compareAndSetState(c, nextc)) return nextc == 0; } } }
三、说说CountDownLatch的await()方法是如何实现的
大佬问的很细。确实整个CountDownLatch核心的核心就是await(),方法。那个countDown()实在没啥好说的。
我们具体总结一下await():
1、先判断线程是否已中断,如果中断就抛出线程中断异常。
//1 await()方法 public void await() throws InterruptedException { sync.acquireSharedInterruptibly(1); } //2 await()里面的acquireSharedInterruptibly() public final void acquireSharedInterruptibly(int arg) throws InterruptedException { if (Thread.interrupted()) throw new InterruptedException(); if (tryAcquireShared(arg) < 0) doAcquireSharedInterruptibly(arg); }
2、判断state值是否为0,如果是0,那就继续运行。
protected int tryAcquireShared(int acquires) { return (getState() == 0) ? 1 : -1; }
3、如果不是0,就要做线程阻塞等待的准备。具体如下:
先构建一个共享模式NODE节点,并把它放到AQS的FIFO队列里。
然后开始自旋,不断判断当前FIFO队列里,自己是否为头节点,以及判断state共享变量是否为0.就干这点事。
private void doAcquireInterruptibly(int arg) throws InterruptedException { final Node node = addWaiter(Node.EXCLUSIVE); boolean failed = true; try { for (;;) { final Node p = node.predecessor(); //如果自己是头节点,且state值是0,说明CountDown的倒计时已经为0,不用再等了。 if (p == head && tryAcquire(arg)) { setHead(node); p.next = null; // help GC failed = false; return; } //判断是否要挂起当前线程 if (shouldParkAfterFailedAcquire(p, node) && parkAndCheckInterrupt()) throw new InterruptedException(); } } finally { if (failed) //如果出现失败或者异常,就取消该节点,唤醒后续节点 cancelAcquire(node); } }
今天就分享到这,明天我们分享CyclicBarrier。