腾讯T2面试,现场限时3分钟+限最多20行代码,模拟地铁口安检进站。其中安检入口10个,当前排队人数是100个,每个人安检进站耗时5秒。开始吧!
候选人,心中万马奔腾!!!吐了一口82年老血,当场砸电脑回家!
其实,面对这样的面试要求,现实中的头部大厂,甚至一些普通大厂都是设计了很多编程题考查大家的基础功底。但是都不会很复杂,毕竟时间有限,往往都是经典题目,涉及一个或多个核心关键技术点。
这个题目考察的就是并发编程,多个线程并发执行,但是共享资源有限,需要阻塞等待,或者自旋竞争锁。其实如果不限制代码行数,我们有非常多的方式去实现。
1、面试真题:模拟地铁站安检排队进站
这里我们用本文主角semaphore信号量去实现。先上代码,加上package 、import,刚好20行代码。
package lading.java.mutithread; import cn.hutool.core.date.DateTime; import java.util.concurrent.Semaphore; /** * 模拟地铁安检入口排队进站 * 共10个安检口 * 当前有100人进站 * 每人进站需要5s */ public class Demo008Semaphore { public static Semaphore doorNum = new Semaphore(10);//总安检口 public static int peopleNum = 100;//当前排队进站人数 public static int perPersonTimeCostSec = 5;//每个人进站耗时:S public static void main(String[] args) { for (int i = 1; i < peopleNum + 1; i++) { new Thread(() -> { try { doorNum.acquire(); Thread.sleep(perPersonTimeCostSec * 1000); System.out.println(DateTime.now().toString("YYYY-MM-dd hh:mm:ss") + " " + Thread.currentThread().getName() + " 完成进闸。"); doorNum.release(); } catch (InterruptedException e) { throw new RuntimeException(e); } }, "卡号" + i).start(); } } }
运行结果,刚好是每次10个人进站,5s后,又有10个人进站。
实现逻辑:每次只有10个人可以安检进站,进站前通过信号量去竞争锁,拿到就休眠5s,模拟进站耗时,然后释放锁,下一个人就可以继续竞争锁并进站:
2、Semaphore信号量是什么?
首先Semaphore是JUC包提供的一个并发工具类,功能是:支持以及限制多个线程同时访问共享资源。之前我们说《synchronized全能王的原理》和可重入锁《ReentrantLock核心原理剖析》都是限制仅允许一个线程访问共享资源,确保并发的原子性、有序性、可见性。但是Semaphore信号量,像个限流器一样,允许N个线程同时执行。
我们看一下他的源码:
发现和之前分享的AQS优秀实践者ReentrankLock可重入锁,简直就是双胞胎兄弟,就差名字不一样了。里面的三个内部类名字完全一样,抽象类Sync,实现Sync的FairSync 类和NoFairSync类。
但是他是个非重入锁。内部就是通过设置volatile int state的值来维护许可令牌。当state值为0 的时候,其他未执行的线程只能阻塞等着。当有获得锁的线程执行完后,他会把state值+1,这样就相当于有一个空闲令牌,其他等待令牌的就可以竞争执行。
3、具体说一下对Semaphore实现原理
在2的源码图我们看到,信号量里面有三个内部类,其中Sync是直接实现了AQS AbstractQueueSynchronizer队列同步器。然后实现公平锁的FairSync 类和非公平锁NoFairSync类有是Sync的子类。所以信号量的核心在于公平锁、非公平锁的实现上。
首先说说,信号量获取锁的逻辑。这个和之前《ReentrantLock核心原理剖析》锁的公平锁、非公平锁逻辑非常像,这里我们也是上核心源码来剖析。
Semaphore permit= new Semaphore(3,true); permit.acquire();
我们继续看获取锁的acquire()的源码.
public void acquire() throws InterruptedException { sync.acquireSharedInterruptibly(1); }
这个acquireSharedInterruptibly方法是在AQS实现的,之前说AQS是模板方式的设计,这里子类就可以复用父类框架。
public final void acquireSharedInterruptibly(int arg) throws InterruptedException { if (Thread.interrupted()) throw new InterruptedException(); if (tryAcquireShared(arg) < 0) doAcquireSharedInterruptibly(arg); }
到正主了,tryAcquireShared(arg),这个方法里才是获取锁的核心逻辑。我们再继续往下看
static final class FairSync extends Sync { private static final long serialVersionUID = 2014338818796000944L; FairSync(int permits) { super(permits); } protected int tryAcquireShared(int acquires) { //自旋 for (;;) { // 1、首先判断 如果AQS FIFO队列是否有在等待的线程,如果有就返回获取锁失败 if (hasQueuedPredecessors()) return -1; //如果步骤1当前队列是空,以及自己是队列的头节点==说明当前没有其他在等待更久竞争的线程 int available = getState(); //设置state,判断可用信号量是否大于0,大于0则获取锁成功,并通过CAS去更新state值 int remaining = available - acquires; if (remaining < 0 || compareAndSetState(available, remaining)) return remaining; } } }
刚看的是公平锁的源码逻辑,我们再简单看一下非公平锁逻辑。非公平锁简单暴力,上来没有公平锁那个hasQueuedPredecessors()逻辑,不判断是否有其他线程在等待,上来就直接判断当前是否还有可用信号量,以及通过CAS去更新设置state值。CAS成功就拿到锁。
final int nonfairTryAcquireShared(int acquires) { for (;;) { int available = getState(); int remaining = available - acquires; if (remaining < 0 || compareAndSetState(available, remaining)) return remaining; } }
4、Semaphore如何释放锁
释放锁,分2步。
1、tryReleaseShared();获取当前信号量值,并通过CAS去+1,更新state值。
2、doReleaseShared();唤醒队列的线程。
步骤1源码,自旋判断并CAS设置state值。
protected final boolean tryReleaseShared(int releases) { for (;;) { int current = getState(); int next = current + releases; if (next < current) // overflow throw new Error("Maximum permit count exceeded"); if (compareAndSetState(current, next)) return true; } }
今天就这样,明天我们继续分享CountDownLatch、Future、CyclicBarrier等其他内容。