Java多线程之自旋锁与自适应自旋锁

前言

我们可以通过以下概念来进行分类:

锁住同步资源失败,线程要不要阻塞?

  • 阻塞
  • 不阻塞
    • 自旋锁
    • 适应性自旋锁

自旋锁

什么是自旋

阻塞或唤醒一个Java线程需要操作系统切换CPU状态来完成,这种状态转换需要耗费处理器时间。如果同步代码块中的内容过于简单,状态转换消耗的时间有可能比用户代码执行的时间还要长。

在许多场景中,同步资源的锁定时间很短,为了这一小段时间去切换线程,线程挂起和恢复现场的花费可能会让系统得不偿失。如果物理机器有多个处理器,能够让两个或以上的线程同时并行执行,我们就可以让后面那个请求锁的线程不放弃CPU的执行时间,看看持有锁的线程是否很快就会释放锁。

而为了让当前线程“稍等一下”,我们需让当前线程进行自旋,如果在自旋完成后前面锁定同步资源的线程已经释放了锁,那么当前线程就可以不必阻塞而是直接获取同步资源,从而避免切换线程的开销。这就是自旋锁。

自旋锁(spinlock):是指当一个线程在获取锁的时候,如果锁已经被其它线程获取,那么该线程将循环等待,然后不断的判断锁是否能够被成功获取,直到获取到锁才会退出循环。

自旋的优点

  • 自旋不会发生线程转态的转换,减少不必要的上下文切换
  • 不阻塞线程,不进行上下文切换

自旋的缺点

自旋等待虽然避免了线程切换的开销,但是还是有缺点的:

  • 自旋不能代替阻塞
  • 自旋时间长的话会过度消耗CPU,占用CPU时间

如果锁被占用的时间很短,自旋等待的效果就会非常好。反之,如果锁被占用的时间很长,那么自旋的线程只会白白浪费处理器资源。所以,自旋等待的时间必须要有一定的限度,如果自旋超过了限定次数(默认是10次,可以使用-XX:PreBlockSpin来更改)没有成功获得锁,就应当挂起线程。

自旋的实现原理

自旋锁的实现原理同样也是CAS,AtomicInteger中调用unsafe进行自增操作的源码中的do-while循环就是一个自旋操作,如果修改数值失败则通过循环来执行自旋,直至修改成功。

自旋锁在JDK1.4.2中引入,使用-XX:+UseSpinning来开启。JDK 6中变为默认开启,并且引入了自适应的自旋锁(适应性自旋锁)。

如何实现自旋锁

下面是个简单的例子:

1
2
3
4
5
6
7
8
9
10
11
12
13
public class SpinLock {
private AtomicReference<Thread> cas = new AtomicReference<Thread>();
public void lock() {
Thread current = Thread.currentThread();
// 利用CAS
while (!cas.compareAndSet(null, current)) {
}
}
public void unlock() {
Thread current = Thread.currentThread();
cas.compareAndSet(current, null);
}
}

当一个线程A进入lock方法后,成功获取到锁后,不会进入while循环,此时如果线程B进入lock方法,通过CAS判断失败后会进入while循环,然后不断重复地判断是否满足条件,直到线程A调用unlock释放锁。

可重入自旋锁

上面代码实现的自旋锁有个问题,就是同一个线程再次获取锁的时候是不能获取到锁的,也就是锁不能重入。

为了实现可重入锁,我们引入一个计数器,用来记录锁的线程数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class ReentrantSpinLock {
private AtomicReference<Thread> cas = new AtomicReference<Thread>();
private int count;
public void lock() {
Thread current = Thread.currentThread();
if (current == cas.get()) { // 如果当前线程已经获取到了锁,线程数增加一,然后返回
count++;
return;
}
// 如果没获取到锁,则通过CAS自旋
while (!cas.compareAndSet(null, current)) {
}
}
public void unlock() {
Thread cur = Thread.currentThread();
if (cur == cas.get()) {
if (count > 0) {// 如果大于0,表示当前线程多次获取了该锁,释放锁通过count减一来模拟
count--;
} else {// 如果count==0,可以将锁释放,这样就能保证获取锁的次数与释放锁的次数是一致的了。
cas.compareAndSet(cur, null);
}
}
}
}

自适应自旋锁

什么是自适应自旋

  • 自适应意味着自旋的时间(次数)不再固定
  • 由前一次在同一个锁上的自旋时间及锁的拥有者的状态来决定

如果在同一个锁对象上,自旋等待刚刚成功获得过锁,并且持有锁的线程正在运行中,那么虚拟机就会认为这次自旋也是很有可能再次成功,进而它将允许自旋等待持续相对更长的时间。如果对于某个锁,自旋很少成功获得过,那在以后尝试获取这个锁时将可能省略掉自旋过程,直接阻塞线程,避免浪费处理器资源。

自旋锁的分类

在自旋锁中有三种常见的锁形式:TicketLockCLHLockMCSLock

TicketLock

TicketLock:每当有线程获取锁的时候,就给该线程分配一个递增的排队号,同时,锁对应一个服务号,每当有线程释放锁,服务号就会递增,此时如果服务号与某个线程的排队号一致,那么该线程就获得锁,由于排队号是递增的,所以就保证了最先请求获取锁的线程可以最先获取到锁,就实现了公平性。

可以想象成银行办理业务排队,排队的每一个顾客都代表一个需要请求锁的线程,而银行服务窗口表示锁,每当有窗口服务完成就把自己的服务号加一,此时在排队的所有顾客中,只有自己的排队号与服务号一致的才可以得到服务。

Ticket主要解决的是访问顺序(公平性)的问题,主要的问题是在多核CPU上。

以下是实现TicketLock的示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.concurrent.atomic.AtomicInteger;

public class TicketLock {
//当前服务号
private AtomicInteger serviceNum = new AtomicInteger();
//每个线程lock时自增,并设置到线程的ThreadLocal中
private AtomicInteger ticketNum = new AtomicInteger();
//用于保存每个线程的票号
private static final ThreadLocal<Integer> LOCAL = new ThreadLocal<Integer>();

//获取TicketLock的流程如下:
//1、线程进入lock方法,原子地获取当前加1的票号
//2、将票号设置到本地线程ThreadLocal中
//3、自旋比较本地线程的票号是否和当前服务号,直至相等为止
public void lock() {
int myticket = ticketNum.getAndIncrement();
LOCAL.set(myticket);
//如果线程持有的票号和当前的服务号不相等就自旋等待
while (myticket != serviceNum.get()) {}
}

public void unlock() {
int myticket = LOCAL.get();
//释放锁,将服务号加1
serviceNum.compareAndSet(myticket, myticket + 1);
}
}

TicketLock的缺点:每次都要读写一个serviceNum服务号,并且还要保证读写操作在多个处理器缓存之间进行同步,这样会增加系统压力,影响性能。

CLHLock

CLHLock采用链表的形式进行排序,有如下好处:

  • 公平,FIFO,先来后到的顺序进入锁
  • 没有竞争同一个变量,因为每个线程都是在等待前继释放锁

以下是实现CLHLock的示例代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class CLHLock {
public static class CLHNode {
private volatile boolean isLocked = true;
}

@SuppressWarnings("unused")
private volatile CLHNode tail;
//每个线程私有的,用于保存每个线程所对应的CLHNode节点
private static final ThreadLocal<CLHNode> LOCAL = new ThreadLocal<CLHNode>();
//用于原子地更新CLHLock中的tail字段
private static final AtomicReferenceFieldUpdater<CLHLock, CLHNode> UPDATER = AtomicReferenceFieldUpdater.newUpdater(CLHLock.class, CLHNode.class, "tail");

//获取CLHLock锁的过程:
//1、新建CLHNode节点并设置到当前线程的ThreadLocal中
//2、原子地更新tail字段并获得前置节点
//3、自旋判断前置节点是否释放锁
public void lock() {
CLHNode node = new CLHNode();
LOCAL.set(node);
CLHNode preNode = UPDATER.getAndSet(this, node);
if (preNode != null) {
while (preNode.isLocked) {
}
//用于GC
preNode = null;
LOCAL.set(node);
}
}

public void unlock() {
CLHNode node = LOCAL.get();
if (!UPDATER.compareAndSet(this, node, null)) {
node.isLocked = false;
}
//用于GC
node = null;
}
}

CLHLock是不停的查询前驱变量, 导致不适合在NUMA 架构下使用(在这种结构下,每个线程分布在不同的物理内存区域)

这里介绍以下NUMA非统一内存访问架构(英语:Non-uniform memory access,简称NUMA)是一种为多处理器的计算机设计的内存架构,内存访问时间取决于内存相对于处理器的位置。在NUMA下,处理器访问它自己的本地内存的速度比非本地内存(内存位于另一个处理器,或者是处理器之间共享的内存)快一些。

非统一内存访问架构的特点是:被共享的内存物理上是分布式的,所有这些内存的集合就是全局地址空间。所以处理器访问这些内存的时间是不一样的,显然访问本地内存的速度要比访问全局共享内存或远程访问外地内存要快些。另外,NUMA中内存可能是分层的:本地内存,群内共享内存,全局共享内存。

MCSLock

MCSLock则是对本地变量的节点进行循环。不存在CLHlock 的问题。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class MCSLock {
public static class MCSNode {
volatile MCSNode next;
volatile boolean isLocked = true;
}

private static final ThreadLocal<MCSNode> NODE = new ThreadLocal<MCSNode>();
@SuppressWarnings("unused")
private volatile MCSNode queue;
private static final AtomicReferenceFieldUpdater<MCSLock, MCSNode> UPDATER = AtomicReferenceFieldUpdater.newUpdater(MCSLock.class, MCSNode.class, "queue");

//获取MCSLock锁的过程:
//1、新建MCSNode节点并设置到当前线程的ThreadLocal中
//2、原子地更新queue字段并获得前置节点
//3、设置前置节点的next为当前节点
//4、自旋判断当前节点是否释放锁
public void lock() {
MCSNode currentNode = new MCSNode();
NODE.set(currentNode);
MCSNode preNode = UPDATER.getAndSet(this, currentNode);
if (preNode != null) {
preNode.next = currentNode;
while (currentNode.isLocked) {
}
}
}

public void unlock() {
MCSNode currentNode = NODE.get();
if (currentNode.next == null) {
if (UPDATER.compareAndSet(this, currentNode, null)) {

} else {
while (currentNode.next == null) {
}
}
} else {
currentNode.next.isLocked = false;
currentNode.next = null;
}
}
}

CLHLock和MSCLock

  • CLH 的队列是隐式的队列,没有真实的后继结点属性。

  • MCS 的队列是显式的队列,有真实的后继结点属性。

  • 线程状态借助节点保存,每个线程都有一份独有的节点,这样就解决了TicketLock多处理器下的问题。

  • JUC ReentrantLock 默认内部使用的锁是 CLH锁(有很多改进的地方,将自旋锁换成了阻塞锁等等)。

参考资料