从银行窗口业务办理来看锁的实现

时间:2021-03-17 18:21:20

今天咱们YY一个sitcom来讨论下几种锁的实现,欢迎列位看官批评指正^_^

你很着急,但是取号机叫号机都故障了

你打算办张招行信用卡,然后你决定利用午休的时间跑到公司楼下,文三路上的高新支行去(硬广强势植入^_^)。到了那边你发现,什么情况,取号机叫号机全都故障了,而且只剩一个窗口在服务。

怎么办呢?然后你发现大家用的最原始的方式,就靠抢,谁先跑到窗口前面谁就先办理业务(什么,你问他们为什么不排队?你见过挤公交排队的?)。因为你也很着急啊,待会还要赶回华星时代23楼上班呢^_^,咋办,抢呗。

代码描述

我们可以用自旋锁来描述上述的抢锁方式。

public class SpinLock {

private AtomicReference<Thread> owner = new AtomicReference<Thread>();

public void lock() {
Thread current = Thread.currentThread();

//// reentrant lock
if(owner.compareAndSet(current, current)) {
return;
}

while (!owner.compareAndSet(null, current)) {
//// 蜂拥而上没抢到,继续抢!
}
}

public void unlock() {
Thread current = Thread.currentThread();
owner.compareAndSet(current, null);
}

}

主要问题

  • 无法保证公平性(野蛮人的社会有木有)
  • 系统开销大(每个人都很累啊有木有)

取号机修复了,但是叫号机还有点问题

当你还在努力抢窗口的时候,取号机修复了,但是叫号机还有点问题,现在只能按一下开关展示一下当前正在服务的号码(读取成本略高)。不过至少公平性的问题现在能解决了

于是乎,每个人开始去取号(取号还是抢,木有办法),然后每个人开始不耐烦的一直去按叫号机(大家都不熟,各管各的咯),看上去所有人都很着急。当然了你也按,也一直等着自己的号码。

代码描述

上述其实就是Ticket Lock的实现方式,

public class TicketLock {

private AtomicInteger ticketNum = new AtomicInteger();
private AtomicInteger serviceNum = new AtomicInteger();
private static final ThreadLocal<Integer> LOCAL = new ThreadLocal<Integer>();

public void lock() {
//// reentrant lock
if(LOCAL.get() != null) return;

int iTicket = ticketNum.getAndIncrement();
LOCAL.set(iTicket);

while (iTicket != serviceNum.get()) {
//// 狂按叫号机开关,直到看到是自己的号码
}
}

public void unlock() {
Integer iTicket = LOCAL.get();

//// unlock before lock
if(iTicket == null) return;

serviceNum.compareAndSet(iTicket, iTicket + 1);
}

}

主要问题

  • 系统开销还是大(叫号机表示自己要被按挂了。。)

阿西吧,叫号机彻底挂了

果了个然,不一会,叫号机就被按挂了。。于是乎现在只剩取号机供取号排队了。

怎么办呢?这时候大厅经理想了个办法。取号的时候,大厅经理会把排在你前一位的同学的手机号码给你。然后告诉你,你就打电话给他去询问他业务办理的状况,他如果办好了就换你去。

于是乎,你就开始一直给那位同学打电话。。没办法,你着急啊。。当然了,那位同学肯定是被你烦得不行。

代码描述

这其实就是CLH锁的实现方式,

public class CLHLock {

private static class CLHNode {
volatile boolean blocked = true;
}

@SuppressWarnings("unused")
private volatile CLHNode tail; // 最后一个申请锁的节点
private static final AtomicReferenceFieldUpdater TAIL = AtomicReferenceFieldUpdater
.newUpdater(CLHLock.class, CLHNode.class, "tail");

private static final ThreadLocal<CLHNode> LOCAL = new ThreadLocal<CLHNode>();

public void lock() {
//// reentrant lock
if(LOCAL.get() != null) return;

CLHNode current = new CLHNode();
LOCAL.set(current);

CLHNode predecessor = (CLHNode) TAIL.getAndSet(this, current);

if (predecessor != null) {

while (predecessor.blocked) {
//// 疯狂询问你的前一位同学是否已经结束
}

}
}

public void unlock() {
CLHNode current = LOCAL.get();

//// unlock before lock
if(current == null) return;

TAIL.compareAndSet(this, current, null);

//// 业务办理结束
current.blocked = false;

// LOCAL.remove();
}
}

主要问题

  • 依旧还是系统开销的问题,特别是在NUMA架构下(电话费很贵的啊喂)

纳尼,你被拉黑了

终于,你打了若干次电话后,人家把你拉黑了。然后你就跟大厅经理抱怨,于是乎他就想了另一个方法。在取号的时候,排在你前一位的同学将会收到你的手机号码,等他业务办理完之后会主动通知你。

于是乎你现在要做的就是一直盯着你的手机了。。

代码描述

这其实就是MCS锁的实现方式了,

public class MCSLock {

private static class MCSNode {
volatile MCSNode next;
volatile boolean blocked = true;
}

@SuppressWarnings("unused")
private volatile MCSNode tail;
private static final AtomicReferenceFieldUpdater TAIL = AtomicReferenceFieldUpdater
.newUpdater(MCSLock.class, MCSNode.class, "tail");

private static final ThreadLocal<MCSNode> LOCAL = new ThreadLocal<MCSNode>();

public void lock() {
//// reentrant lock
if(LOCAL.get() != null) return;

MCSNode current = new MCSNode();
LOCAL.set(current);

//// step1
MCSNode predecessor = (MCSNode) TAIL.getAndSet(this, current);

if (predecessor != null) {

//// step2
predecessor.next = current;

while (current.blocked) {
//// 一直盯着自己的手机,等待通知
}

} else {
current.blocked = false;
}
}

public void unlock() {
MCSNode current = LOCAL.get();

//// unlock before lock
if(current == null) return;

if (current.next == null) {
//// 你是最后一位了
if (TAIL.compareAndSet(this, current, null)) {
LOCAL.remove();
return;
}
//// step1+step2并非原子操作
else {
while (current.next == null) {}
}
}

//// 主动通知下一位同学
current.next.blocked = false;

current.next = null;
LOCAL.remove();
}

}

现在你不着急了

等着等着你发现,我去,已经两点了,你观察了一下,按照目前窗口的办理速度,至少还得半小时(竞争激烈,锁持有时间长),于是你给老板发了消息说明情况,半小时后回,老板表示OK。

所以你现在也没有那么着急了,既来之则安之,并且中午不睡下午崩溃嘛,于是你决定先小憩一会(进入休眠状态),也不盯着手机了,就等着待会被叫醒了。

代码描述

将MCS锁实现稍微修改一下,就可以实现上述的阻塞锁了。

public class MCSBlockingLock {

private static class MCSBlockingNode {
volatile MCSBlockingNode next;
volatile boolean blocked = true;
volatile Thread thread = Thread.currentThread(); // 该节点所属的线程
}

@SuppressWarnings("unused")
private volatile MCSBlockingNode tail;
private static final AtomicReferenceFieldUpdater TAIL = AtomicReferenceFieldUpdater
.newUpdater(MCSBlockingLock.class, MCSBlockingNode.class, "tail");

private static final ThreadLocal<MCSBlockingNode> LOCAL = new ThreadLocal<MCSBlockingNode>();

public void lock() {
//// reentrant lock
if(LOCAL.get() != null) return;

MCSBlockingNode current = new MCSBlockingNode();
LOCAL.set(current);

//// step1
MCSBlockingNode predecessor = (MCSBlockingNode) TAIL.getAndSet(this, current);

if (predecessor != null) {

//// step2
predecessor.next = current;

while (current.blocked) {
//// 睡一觉,等待通知
LockSupport.park(this);
}

} else {
current.blocked = false;
}
}

public void unlock() {
MCSBlockingNode current = LOCAL.get();

//// unlock before lock
if(current == null) return;

if (current.next == null) {
if (TAIL.compareAndSet(this, current, null)) {
LOCAL.remove();
return;
} else {
while (current.next == null) {}
}
}

//// 主动通知下一位同学
current.next.blocked = false;
LockSupport.unpark(current.next.thread);

current.next = null;
LOCAL.remove();
}
}

参考资料