博客

自旋锁类型详解

  • Post author:
  • Post category:其他



https://blog.csdn.net/qq_41723615/article/details/104348186


什么是

自旋锁



多线程

中，对共享资源进行访问，为了防止并发引起的相关问题，通常都是引入锁的机制来处理并发问题。


获取到资源的线程A对这个资源加锁，其他线程比如B要访问这个资源首先要获得锁，而此时A持有这个资源的锁，只有等待线程A逻辑执行完，释放锁，这个时候B才能获取到资源的锁进而获取到该资源。


这个过程中，A一直持有着资源的锁，那么没有获取到锁的其他线程比如B怎么办？通常就会有两种方式：


1.


一种是没有获得锁的进程就直接进入阻塞（BLOCKING），这种就是互斥锁


2.


另外一种就是没有获得锁的进程，不进入阻塞，而是一直循环着，看是否能够等到A释放了资源的锁。


上述的两种方式，学术上，就有几种不同的定义方式，大学的时候 学习的是C++， 《C++ 11》中就有这样的描述：


自旋锁（spin lock）是一种非阻塞锁，也就是说，如果某线程需要获取锁，但该锁已经被其他线程占用时，该线程不会被挂起，而是在不断的消耗CPU的时间，不停的试图获取锁。


互斥量（mutex）是阻塞锁，当某线程无法获取锁时，该线程会被直接挂起，该线程不再消耗CPU时间，当其他线程释放锁后，操作系统会激活那个被挂起的线程，让其投入运行。


而《linux内核设计与实现》经常提到两种态，一种是内核态，一种是用户态，对于自旋锁来说，自旋锁使线程处于用户态，而互斥锁需要重新分配，进入到内核态。这里大家对内核态和用户态有个初步的认知就行了，用户态比较轻，内核态比较重。用户态和内核态这个也是linux中必备的知识基础，借鉴这个，可以进行很多程序设计语言API上的优化，就比如说javaio的部分，操作io的时候，先是要从用户态，进入内核态，再用内核态去操作输入输出设备的抽象，这里减少用户态到内核态的转换就是新io的一部分优化，后面再聊。


wiki


中的定义如下：


自旋锁是计算机科学用于多线程同步的一种锁，线程反复检查锁变量是否可用。由于线程在这一过程中保持执行，因此是一种忙等待。


自旋锁避免了进程上下文的调度开销，因此对于线程只会阻塞很短时间的场合是有效的。因此操作系统的实现在很多地方往往用自旋锁。Windows操作系统提供的轻型读写锁（SRW Lock）内部就用了自旋锁。显然，单核CPU不适于使用自旋锁，这里的单核CPU指的是单核单线程的CPU，因为，在同一时间只有一个线程是处在运行状态，假设运行线程A发现无法获取锁，只能等待解锁，但因为A自身不挂起，所以那个持有锁的线程B没有办法进入运行状态，只能等到操作系统分给A的时间片用完，才能有机会被调度。这种情况下使用自旋锁的代价很高。（红字部分是我给wiki编辑的词条，单核CPU不适合自旋锁，这个也只是针对单核单线程的情况，现在的技术基本单核都是支持多线程的）


为什么要使用自旋锁

互斥锁有一个缺点，他的执行流程是这样的 托管代码  – 用户态代码 – 内核态代码、上下文切换开销与损耗，假如获取到资源锁的线程A立马处理完逻辑释放掉资源锁，如果是采取互斥的方式，那么线程B从没有获取锁到获取锁这个过程中，就要用户态和内核态调度、上下文切换的开销和损耗。所以就有了自旋锁的模式，让线程B就在用户态循环等着，减少消耗。


自旋锁比较适用于锁使用者保持锁时间比较短的情况，这种情况下自旋锁的效率要远高于互斥锁。


自旋锁可能潜在的问题

过多占用CPU的资源，如果锁持有者线程A一直长时间的持有锁处理自己的逻辑，那么这个线程B就会一直循环等待过度占用cpu资源

递归使用可能会造成死锁，不过这种场景一般写不出来

CAS

就不写术语定义了，简单的理解就是这个CAS是由操作系统定义的，由若干指令组成的，这个操作具有原子性，这些指令如果执行，就会全部执行完，不会被中断。CAS有3个操作数，内存值V，旧的预期值A，要修改的新值B。当且仅当预期值A和内存值V相同时，将内存值V修改为B，否则什么都不做。


CAS


的问题

经典的CAS的ABA问题，上面提到了CAS操作的时候，要检测值有没有变化，如果一个值原来是A，后来变成了B， 后来又变成了A，CAS会认为没有发生变化。

解决方案：


1.


加版本号   1A – 2B –  3A


2.


对java而言，jdk1.5提供了AtomicStampedReference来解决这个问题


只能保证一个共享变量的原子操作

CAS通常是对一个变量来进行原子操作的，所以如果对多个变量进行原子操作就会有问题了。


解决方案


1.


简单粗暴，加锁，反而加入了复杂性，最low的方式


2.


跟上面的加版本号的道理一样，就是将多个变量拼成一个变量（可以拼成一个字符串）


3.


对java而言，jdk1.5 提供了AtomicStampedReference，这个reference 就是个对象引用，把多个变量放在这个对象里即可


JAVA CAS


封装

sun.misc.Unsafe是JDK里面的一个内部类，这个类当中有三个CAS的操作


JAVA


自旋锁应用

Jdk1.5以后，提供了java.util.concurrent.atomic包，这个包里面提供了一组原子类。基本上就是当前获取锁的线程，执行更新的方法，其他线程自旋等待，比如atomicInteger类中的getAndAdd方法内部实际上使用的就是Unsafe的方法。


/**

* Atomically adds the given value to the current value.

*

* @param delta the value to add

* @return the previous value

*/

public final int getAndAdd(int delta) {undefined

return unsafe.getAndAddInt(this, valueOffset, delta);

}



当然java中的syncronized关键字，在1.5中有了很大的优化，加入了偏隙锁也有人叫偏向锁，主要的实现方式就是在对象头markword中打上线程的信息，这样资源上的锁的获取就偏向了这个线程，后面，会涉及一系列的锁升级的问题，间隙锁 – 轻量锁 – 重量级锁 ，锁升级后面单独抽出来写一篇，这个轻量锁实际上就是使用的也是自旋锁的实现方式。

原文链接：https://blog.csdn.net/u010372981/article/details/814632





简单自旋锁（可重入）



自旋锁是指当一个线程尝试获取某个锁时，如果该锁已被其他线程占用，就一直循环检测锁是否被释放，而不是进入线程挂起或睡眠状态。


自旋锁适用于锁保护的临界区很小的情况，临界区很小的话，锁占用的时间就很短。


  1. public


    class SpinLock implements Lock {

  2. /**

  3. *  use thread itself as  synchronization state

  4. *


    使用Owner Thread作为同步状态，比使用一个简单的boolean flag可以携带更多信息

  5. */

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

  7. /**

  8. * reentrant count of a thread, no need to be volatile

  9. */

  10. private int count = 0;

  12. @Override

  13. public void lock() {

  14. Thread t = Thread.currentThread();

  15. // if re-enter, increment the count.

  16. if (t == owner.get()) {

  17. ++count;

  18. return;

  19. }

  20. //spin

  21. while (owner.compareAndSet(null, t)) {

  22. }

  23. }

  25. @Override

  26. public void unlock() {

  27. Thread t = Thread.currentThread();

  28. //only the owner could do unlock;

  29. if (t == owner.get()) {

  30. if (count > 0) {

  31. // reentrant count not zero, just decrease the counter.

  32. –count;

  33. } else {

  34. // compareAndSet is not need here, already checked

  35. owner.set(null);

  36. }

  37. }

  38. }

  39. }


SimpleSpinLock


里有一个owner属性持有锁当前拥有者的线程的引用，如果该引用为null，则表示锁未被占用，不为null则被占用。


这里用AtomicReference是为了使用它的原子性的compareAndSet方法（CAS操作），解决了多线程并发操作导致数据不一致的问题，确保其他线程可以看到锁的真实状态。



缺点：


  1. CAS


    操作需要硬件的配合；

  2. 保证各个CPU的缓存（L1、L2、L3、跨CPU Socket、主存）的数据一致性，通讯开销很大，在多处理器系统上更严重；

  3. 没法保证公平性，不保证等待进程/线程按照FIFO顺序获得锁。





TicketLock



Ticket Lock


是为了解决上面的公平性问题，类似于现实中银行柜台的排队叫号：锁拥有一个服务号，表示正在服务的线程，还有一个排队号；每个线程尝试获取锁之前先拿一个排队号，然后不断轮询锁的当前服务号是否是自己的排队号，如果是，则表示自己拥有了锁，不是则继续轮询。


当线程释放锁时，将服务号加1，这样下一个线程看到这个变化，就退出自旋。


  1. public


    class TicketLock implements Lock {

  2. private AtomicInteger serviceNum = new AtomicInteger(0);

  3. private AtomicInteger ticketNum = new AtomicInteger(0);

  4. private final ThreadLocal<Integer> myNum = new ThreadLocal<>();

  6. @Override

  7. public void lock() {

  8. myNum.set(ticketNum.getAndIncrement());

  9. while (serviceNum.get() != myNum.get()) {

  10. }

  11. }

  13. @Override

  14. public void unlock() {

  15. serviceNum.compareAndSet(myNum.get(), myNum.get() + 1);

  16. myNum.remove();

  17. }

  18. }



缺点：




Ticket Lock


虽然解决了公平性的问题，但是多处理器系统上，每个进程/线程占用的处理器都在读写同一个变量serviceNum ，每次读写操作都必须在多个处理器缓存之间进行缓存同步，这会导致繁重的系统总线和内存的流量，大大降低系统整体的性能。


下面介绍的CLH锁和MCS锁都是为了解决这个问题的。





CLHLock



CLH


的发明人是：Craig，Landin and Hagersten。是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，它不断轮询前驱的状态，如果发现前驱释放了锁就结束自旋。


CLH


队列中的结点QNode中含有一个locked字段，该字段若为true表示该线程需要获取锁，且不释放锁，为false表示线程释放了锁。结点之间是通过隐形的链表相连，之所以叫隐形的链表是因为这些结点之间没有明显的next指针，而是通过preNode所指向的结点的变化情况来影响myNode的行为。CLHLock上还有一个尾指针，始终指向队列的最后一个结点。CLHLock的类图如下所示：


当一个线程需要获取锁时，会创建一个新的QNode，将其中的locked设置为true表示需要获取锁，然后线程对tail域调用getAndSet方法，使自己成为队列的尾部，同时获取一个指向其前趋的引用preNode,然后该线程就在前趋结点的locked字段上自旋，直到前趋结点释放锁。当一个线程需要释放锁时，将当前结点的locked域设置为false，同时回收前趋结点。如下图所示，线程A需要获取锁，其myNode域为true，些时tail指向线程A的结点，然后线程B也加入到线程A后面，tail指向线程B的结点。然后线程A和B都在它的preNode域上旋转，一旦它的preNode结点的locked字段变为false，它就可以获取锁。明显线程A的preNode locked域为false，此时线程A获取到了锁。


实现如下：


  1. public


    class CLHLock implements Lock {

  3. /**

  4. *


    锁等待队列的尾部

  5. */

  6. private AtomicReference<QNode> tail;

  7. private ThreadLocal<QNode> preNode;

  8. private ThreadLocal<QNode> myNode;

  10. public CLHLock() {

  11. tail = new AtomicReference<>(null);

  12. myNode = ThreadLocal.withInitial(QNode::new);

  13. preNode = ThreadLocal.withInitial(() -> null);

  14. }

  16. @Override

  17. public void lock() {

  18. QNode qnode = myNode.get();

  19. //


    设置自己的状态为locked=true表示需要获取锁

  20. qnode.locked = true;

  21. //


    链表的尾部设置为本线程的qNode，并将之前的尾部设置为当前线程的preNode

  22. QNode pre = tail.getAndSet(qnode);

  23. preNode.set(pre);

  24. if(pre != null) {

  25. //


    当前线程在前驱节点的locked字段上旋转，直到前驱节点释放锁资源

  26. while (pre.locked) {

  27. }

  28. }

  29. }

  31. @Override

  32. public void unlock() {

  33. QNode qnode = myNode.get();

  34. //


    释放锁操作时将自己的locked设置为false，可以使得自己的后继节点可以结束自旋

  35. qnode.locked = false;

  36. //


    回收自己这个节点，从虚拟队列中删除

  37. //


    将当前节点引用置为自己的preNode，那么下一个节点的preNode就变为了当前节点的preNode，这样就将当前节点移出了队列

  38. myNode.set(preNode.get());

  39. }

  41. private class QNode {

  42. /**

  43. * true


    表示该线程需要获取锁，且不释放锁，为false表示线程释放了锁，且不需要锁

  44. */

  45. private volatile boolean locked = false;

  46. }

  47. }


CLH


队列锁的

优点

是空间复杂度低（如果有n个线程，L个锁，每个线程每次只获取一个锁，那么需要的存储空间是O（L+n），n个线程有n个myNode，L个锁有L个tail），CLH的一种变体被应用在了JAVA并发框架中。唯一的

缺点

是在NUMA系统结构下性能很差，在这种系统结构下，每个线程有自己的内存，如果前趋结点的内存位置比较远，自旋判断前趋结点的locked域，性能将大打折扣，但是在SMP系统结构下该法还是非常有效的。一种解决NUMA系统结构的思路是MCS队列锁。





MCSLock



MCS


来自于其发明人名字的首字母： John Mellor-Crummey和Michael Scott。是一种基于链表的可扩展、高性能、公平的自旋锁，申请线程只在本地变量上自旋，直接前驱负责通知其结束自旋，从而极大地减少了不必要的处理器缓存同步的次数，降低了总线和内存的开销。


  1. public


    class MCSLock implements Lock {

  2. private AtomicReference<QNode> tail;

  3. private ThreadLocal<QNode> myNode;

  5. public MCSLock() {

  6. tail = new AtomicReference<>(null);

  7. myNode = ThreadLocal.withInitial(QNode::new);

  8. }

  10. @Override

  11. public void lock() {

  12. QNode qnode = myNode.get();

  13. QNode preNode = tail.getAndSet(qnode);

  14. if (preNode != null) {

  15. qnode.locked = false;

  16. preNode.next = qnode;

  17. //wait until predecessor gives up the lock

  18. while (!qnode.locked) {

  19. }

  20. }

  21. qnode.locked = true;

  22. }

  24. @Override

  25. public void unlock() {

  26. QNode qnode = myNode.get();

  27. if (qnode.next == null) {

  28. //


    后面没有等待线程的情况

  29. if (tail.compareAndSet(qnode, null)) {

  30. //


    真的没有等待线程，则直接返回，不需要通知

  31. return;

  32. }

  33. //wait until predecessor fills in its next field

  34. //


    突然有人排在自己后面了，可能还不知道是谁，下面是等待后续者

  35. while (qnode.next == null) {

  36. }

  37. }

  38. //


    后面有等待线程，则通知后面的线程

  39. qnode.next.locked = true;

  40. qnode.next = null;

  41. }

  43. private class QNode {

  44. /**

  45. *


    是否被qNode所属线程锁定

  46. */

  47. private volatile boolean locked = false;

  48. /**

  49. *


    与CLHLock相比，多了这个真正的next

  50. */

  51. private volatile QNode next = null;

  52. }

  53. }



CLH




锁 与 MCS锁 的比较


CLH


锁和MCS锁队列图示



差异



：


  1. 从代码实现来看，CLH比MCS要简单得多。

  2. 从自旋的条件来看，CLH是在前驱节点的属性上自旋，而MCS是在本地属性变量上自旋。

  3. 从链表队列来看，CLHNode不直接持有前驱节点，CLH锁释放时只需要改变自己的属性；MCSNode直接持有后继节点，MCS锁释放需要改变后继节点的属性。

  4. CLH


    锁释放时只需要改变自己的属性，MCS锁释放则需要改变后继节点的属性


链接：https://www.jianshu.com/p/824b2e4f1eed