MCS队列锁原理解析
MCS锁
MCS锁,全称:John Mellor-Crummey和Michael Scott (MCS) locks。(MCS是两位大佬名字的缩写)
MCS锁,与CLH锁类似;一种基于FIFO队列的自旋锁,提供先来先服务的公平性。确保无饥饿性。
核心思想
MCS锁,是一种基于链表的可扩展、高性能、公平的自旋锁,申请线程只在本地变量上自旋,直接前继节点负责通知其结束自旋(与CLH自旋锁不同的地方,不在轮询前继节点的状态,而是由前继节点主动通知),从而极大地减少了不必要的处理器缓存同步的次数,降低了总线和内存的开销。
原理
MCS锁的队列是一个显示链表,是通过next指针串起来的
代码实现
MCSQueueLock.java
public class MCSQueueLock {
/**
* CLH锁节点
*/
private class MCSNode {
/**
* 持有后继者的引用
*/
MCSNode next;
/**
* 默认未锁定
*/
boolean locked = true;
}
/**
* 当前节点
* 每个线程拥有自己的副本用于记录自己线程中持有的CLH节点状态信息
*/
private final ThreadLocal<MCSNode> curNode;
/**
* 最后一个队列种MCS节点的状态信息,指向最后一个申请锁的MCSNode
* 【注意】这里用了java的原子系列之AtomicReference,能保证原子更新
*/
private final AtomicReference<MCSNode> tailNode;
MCSQueueLock() {
// 初始化当前线程(即实例化锁的线程)的MCS节点,锁状态为false;next指针为null
curNode = ThreadLocal.withInitial(MCSNode::new);
// 初始化最后一个队列种CLH节点的状态信息
tailNode = new AtomicReference<>();
}
void lock() {
MCSNode myNode = curNode.get();
MCSNode preNode = tailNode.getAndSet(myNode);
int spinCount = 0;
//类似的,preNode == null从tail中没获取到值标志没有线程占用锁
if (preNode != null) {
//获取前继节点的下个指针引用,也就是当前线程持有的锁的状态
preNode.next = myNode;
//在自己node的locked变量自旋
while (myNode.locked) {
spinCount++;
}
}
System.out.println("线程" + Thread.currentThread().getName() + "自旋" + spinCount + "次后获取了锁");
}
void unlock() {
MCSNode myNode = curNode.get();
//获取下个指针的引用
MCSNode next = myNode.next;
int spinCount = 0;
//如果有后继者,直接设置next.locked = false通知后继者结束自旋.
//如果有执行下面操作
if (next == null) {
//设置成功表示设置期间也没有后继者加入,设置失败表示有后继者加入
if (tailNode.compareAndSet(myNode, null)) {
System.out.println("无后继节点直接释放锁");
return;
}
//同样的需要等待lock()中step1完成
while (next == null) {
spinCount++;
}
}
System.out.println("线程" + Thread.currentThread().getName() + "自旋" + spinCount + "次后释放锁");
next.locked = false;
//for CG
next = null;
}
}
MCSQueueLockTest.java
public class MCSQueueLockTest extends Thread {
private static int count = 0;
private static MCSQueueLock lock = new MCSQueueLock();
@Override
public void run() {
lock.lock();
try {
for (int i = 0; i < 1000; i++) {
count++;
}
} finally {
lock.unlock();
}
}
public static void main(String[] args) throws InterruptedException {
Thread[] threads = new Thread[10];
for (int i = 0; i < threads.length; i++) {
MCSQueueLockTest clhQueueLockTest = new MCSQueueLockTest();
threads[i] = clhQueueLockTest;
threads[i].start();
}
for (Thread thread : threads) {
thread.join();
}
System.out.println("count=" + count);
}
}
代码好像还是优点问题,后续再优化;但是思想了解到了就OK了
流程图说明
假设有三个并发线程同时启动执行lock操作,假如三个线程的实际执行顺序为:P1 –> P2 –> P3;其中存在一个初始化所得线程,在这里我们设置为P0
-
第一步初始化
-
第二步P1线程去获取锁,获取成功(最后的tailNode为引用为NULL不存在自旋)
-
- 第三步P2线程去获取锁,P2自旋等待P1通知**
- 第三步P2线程去获取锁,P2自旋等待P1通知**
- 第四步P3线程去获取锁,P3自旋等待P2通知(这里就存在很明显的next的指针引用了)
MCS释放锁是由前一个线程通知他所属指针指向的线程(通知方式是在解锁的时候修改指针指向线程的锁的状态)。
优缺点
优点 优点是适用于NUMA系统架构 缺点 缺点是释放锁也需要自旋等待,且比CLH读、写、CAS等操作调用次数多。
一种解决SMP系统结构的思路是CLH队列锁。
SMP/NUMA 系统结构
SMP SMP (Symmetric Multi Processing),对称多处理系统内有许多紧耦合多处理器,在这样的系统中,所有的CPU共享全部资源,如总线,内存和I/O系统等,操作系统或管理数据库的复本只有一个,这种系统有一个最大的特点就是共享所有资源。多个CPU之间没有区别,平等地访问内存、外设、一个操作系统。操作系统管理着一个队列,每个处理器依次处理队列中的进程。如果两个处理器同时请求访问一个资源(例如同一段内存地址),由硬件、软件的锁机制去解决资源争用问题。
所谓对称多处理器结构,是指服务器中多个 CPU 对称工作,无主次或从属关系。各 CPU 共享相同的物理内存,每个 CPU 访问内存中的任何地址所需时间是相同的,因此 SMP 也被称为一致存储器访问结构 (UMA : Uniform Memory Access) 。对 SMP 服务器进行扩展的方式包括增加内存、使用更快的 CPU 、增加 CPU 、扩充 I/O( 槽口数与总线数 ) 以及添加更多的外部设备 ( 通常是磁盘存储 ) 。
SMP 服务器的主要特征是共享,系统中所有资源 (CPU 、内存、 I/O 等 ) 都是共享的。也正是由于这种特征,导致了 SMP 服务器的主要问题,那就是它的扩展能力非常有限。对于 SMP 服务器而言,每一个共享的环节都可能造成 SMP 服务器扩展时的瓶颈,而最受限制的则是内存。由于每个 CPU 必须通过相同的内存总线访问相同的内存资源,因此随着 CPU 数量的增加,内存访问冲突将迅速增加,最终会造成 CPU 资源的浪费,使 CPU 性能的有效性大大降低。
我们常用的计算机就是这种结构
NUMA 由于 SMP 在扩展能力上的限制,人们开始探究如何进行有效地扩展从而构建大型系统的技术, NUMA 就是这种努力下的结果之一。利用 NUMA 技术,可以把几十个 CPU( 甚至上百个 CPU) 组合在一个服务器内。
NUMA 服务器的基本特征是具有多个 CPU 模块,每个 CPU 模块由多个 CPU( 如 4 个 ) 组成,并且具有独立的本地内存、 I/O 槽口等。由于其节点之间可以通过互联模块 ( 如称为 Crossbar Switch) 进行连接和信息交互,因此每个 CPU 可以访问整个系统的内存 ( 这是 NUMA 系统与 MPP 系统的重要差别 ) 。显然,访问本地内存的速度将远远高于访问远地内存 ( 系统内其它节点的内存 ) 的速度,这也是非一致存储访问 NUMA 的由来。由于这个特点,为了更好地发挥系统性能,开发应用程序时需要尽量减少不同 CPU 模块之间的信息交互。
利用 NUMA 技术,可以较好地解决原来 SMP 系统的扩展问题,在一个物理服务器内可以支持上百个 CPU 。比较典型的 NUMA 服务器的例子包括 HP 的 Superdome 、 SUN15K 、 IBMp690 等。
但 NUMA 技术同样有一定缺陷,由于访问远地内存的延时远远超过本地内存,因此当 CPU 数量增加时,系统性能无法线性增加。