`
MauerSu
  • 浏览: 513460 次
  • 性别: Icon_minigender_1
  • 来自: 北京
文章分类
社区版块
存档分类
最新评论

自旋锁、排队自旋锁、MCS锁、CLH锁

 
阅读更多
源:http://coderbee.net/index.php/concurrent/20131115/577/comment-page-1
评: 黑色加粗部分为原文 bug
自旋锁(Spin lock)

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

自旋锁适用于锁保护的临界区很小的情况,临界区很小的话,锁占用的时间就很短。
简单的实现

import java.util.concurrent.atomic.AtomicReference;

public class SpinLock {
   private AtomicReference<Thread> owner = new AtomicReference<Thread>();

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

              // 如果锁未被占用,则设置当前线程为锁的拥有者
       while (owner.compareAndSet(null, currentThread)) {
       }
   }

   public void unlock() {
       Thread currentThread = Thread.currentThread();

              // 只有锁的拥有者才能释放锁
       owner.compareAndSet(currentThread, null);
   }
}

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

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

    CAS操作需要硬件的配合;
    保证各个CPU的缓存(L1、L2、L3、跨CPU Socket、主存)的数据一致性,通讯开销很大,在多处理器系统上更严重;
    没法保证公平性,不保证等待进程/线程按照FIFO顺序获得锁。

Ticket Lock

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

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

import java.util.concurrent.atomic.AtomicInteger;

public class TicketLock {
   private AtomicInteger serviceNum = new AtomicInteger(); // 服务号
   private AtomicInteger ticketNum = new AtomicInteger(); // 排队号

   public int lock() {
         // 首先原子性地获得一个排队号
         int myTicketNum = ticketNum.getAndIncrement();

              // 只要当前服务号不是自己的就不断轮询
       while (serviceNum.get() != myTicketNum) {
       }

       return myTicketNum;
    }

    public void unlock(int myTicket) {
        // 只有当前线程拥有者才能释放锁
        int next = myTicket + 1;
        serviceNum.compareAndSet(myTicket, next);
    }
}

缺点

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

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

MCS 来自于其发明人名字的首字母: John Mellor-Crummey和Michael Scott。

CLH的发明人是:Craig,Landin and Hagersten。
MCS锁

MCS Spinlock 是一种基于链表的可扩展、高性能、公平的自旋锁,申请线程只在本地变量上自旋,直接前驱负责通知其结束自旋,从而极大地减少了不必要的处理器缓存同步的次数,降低了总线和内存的开销。

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class MCSLock {
    public static class MCSNode {
        volatile MCSNode next;
        volatile boolean isBlock = true; // 默认是在等待锁
    }

    volatile MCSNode queue;// 指向最后一个申请锁的MCSNode
    private static final AtomicReferenceFieldUpdater UPDATER = AtomicReferenceFieldUpdater
            .newUpdater(MCSLock.class, MCSNode.class, "queue");

    public void lock(MCSNode currentThread) {
        MCSNode predecessor = UPDATER.getAndSet(this, currentThread);// step 1
        if (predecessor != null) {
            predecessor.next = currentThread;// step 2

            while (currentThread.isBlock) {// step 3
            }
        } else {
   currentThread.isBlock = false;
}

    }

    public void unlock(MCSNode currentThread) {
        if (currentThread.isBlock) {// 锁拥有者进行释放锁才有意义
            return;
        }

        if (currentThread.next == null) {// 检查是否有人排在自己后面
            if (UPDATER.compareAndSet(this, currentThread, null)) {// step 4
                // compareAndSet返回true表示确实没有人排在自己后面
                return;
            } else {
                // 突然有人排在自己后面了,可能还不知道是谁,下面是等待后续者
                // 这里之所以要忙等是因为:step 1执行完后,step 2可能还没执行完
                while (currentThread.next == null) { // step 5
                }
            }
        }

        currentThread.next.isBlock = false;
        currentThread.next = null;// for GC
    }
}

CLH锁

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

import java.util.concurrent.atomic.AtomicReferenceFieldUpdater;

public class CLHLock {
    public static class CLHNode {
        private boolean isLocked = true; // 默认是在等待锁
    }

    @SuppressWarnings("unused" )
    private volatile CLHNode tail ;
    private static final AtomicReferenceFieldUpdater<CLHLock, CLHNode> UPDATER = AtomicReferenceFieldUpdater
                  . newUpdater(CLHLock.class, CLHNode .class , "tail" );

    public void lock(CLHNode currentThread) {
        CLHNode preNode = UPDATER.getAndSet( this, currentThread);
        if(preNode != null) {//已有线程占用了锁,进入自旋
            while(preNode.isLocked ) {
            }
        }
    }

    public void unlock(CLHNode currentThread) {
        // 如果队列里只有当前线程,则释放对当前线程的引用(for GC)。
        if (!UPDATER .compareAndSet(this, currentThread, null)) {
            // 还有后续线程
            currentThread. isLocked = false ;// 改变状态,让后续线程结束自旋
        }
    }
}

CLH锁 与 MCS锁 的比较

下图是CLH锁和MCS锁队列图示:
CLH-MCS-SpinLock

差异:

    从代码实现来看,CLH比MCS要简单得多。
    从自旋的条件来看,CLH是在前驱节点的属性上自旋,而MCS是在本地属性变量上自旋。
    从链表队列来看,CLH的队列是隐式的,CLHNode并不实际持有下一个节点;MCS的队列是物理存在的。
    CLH锁释放时只需要改变自己的属性,MCS锁释放则需要改变后继节点的属性。

注意:这里实现的锁都是独占的,且不能重入的。
  • 大小: 15.9 KB
分享到:
评论

相关推荐

    基于SMP的Linux内核自旋锁分析.pdf

    为了实现自旋锁,Linux内核使用了多种技术,包括Ticket Lock、MCS Lock和CLH Lock等。 Ticket Lock是一种简单的自旋锁机制,它使用一个 ticket 变量来记录当前获取自旋锁的处理器的ID。当一个处理器尝试获取自旋锁...

    一种Linux内核自旋锁死锁检测机制的设计与实现.pdf

    在 Linux 内核中,自旋锁的种类有很多,包括基本型、读写自旋、排队锁和 MCS 自旋锁等。每种自旋锁都有其特点和使用场景,需要根据不同的情况选择合适的自旋锁。 在设计自旋锁死锁检测机制时,需要考虑到自旋锁的...

    信号量、互斥体和自旋锁的区别

    ### 信号量、互斥体和自旋锁的区别详解 #### 一、基本概念与应用场景 **信号量**、**互斥体**和**自旋锁**是操作系统中三种常用的同步机制,主要用于解决多线程或多进程环境中资源的并发访问问题。这三种机制虽然...

    无锁编程之自旋锁的C++实现

    本文将围绕"无锁编程之自旋锁的C++实现"这一主题,详细介绍无锁编程和自旋锁的概念,并分析提供的C++代码实现。 首先,无锁编程(Lock-Free Programming)强调的是在没有锁的情况下实现并发操作。这种方法的关键...

    Linux系统内核的同步机制-自旋锁

    Linux系统内核的同步机制是确保多线程和多处理器环境下正确访问共享资源的关键部分,其中自旋锁作为一项重要工具,被广泛用于保护短暂的、临界区的访问。自旋锁的设计理念在于,当一个线程尝试获取已被其他线程持有...

    Windows驱动编程视频教程 提升IRQ与自旋锁

    在Windows驱动程序开发中,理解和掌握中断请求级别(IRQ)以及自旋锁是至关重要的。本视频教程将深入探讨这两个核心概念,旨在帮助开发者提升驱动程序的性能和稳定性。 首先,我们来了解一下中断请求级别(IRQ)。...

    自旋锁操作 spin_lock

    自旋锁(Spin Lock)是操作系统中用于多线程同步的一种机制,特别是在处理并发和实时系统中非常常见。自旋锁的基本思想是当一个线程试图获取已被其他线程持有的锁时,它不会立即阻塞,而是不断地循环检查锁的状态,...

    信号量与自旋锁

    ### 信号量与自旋锁:并发控制的关键技术 在多任务操作系统中,尤其是在像Linux这样的高度并发系统中,管理共享资源的访问是一项至关重要的任务。为了确保数据的一致性和完整性,开发人员需要采取措施来避免竞态...

    SQL server 自旋锁争用专题

    SQL Server自旋锁争用是一个高级数据库管理问题,通常出现在高性能、高并发的系统中。自旋锁是操作系统中的一个同步机制,用于控制对共享资源的访问。在数据库系统中,自旋锁用于保护数据结构在并发访问时的完整性。...

    linux系统中基于自旋锁的进程调度的实现

    本文将深入探讨Linux系统中基于自旋锁的进程调度实现,以及自旋锁、共享内存和汇编语言在其中的作用。 自旋锁(Spinlock)是一种简单的互斥机制。当一个进程持有一个自旋锁时,其他试图获取该锁的进程将进入“自旋...

    Java并发篇乐观锁,悲观锁,自旋锁

    本文主要讨论了四种锁类型:乐观锁、悲观锁、自旋锁以及Java中的synchronized同步锁,并深入解析了synchronized锁的内部机制,包括其核心组件、实现方式以及锁的状态。 1. **乐观锁**:乐观锁假设在多线程环境下,...

    深入讲解我们说的CAS自旋锁到底是什么

    深入讲解CAS自旋锁的实现机理和原理 CAS(Compare and Swap)是实现自旋锁或乐观锁的核心操作,它的出现是为了解决原子操作的问题。在多线程环境下,原子操作是保证线程安全的重要手段。CAS操作的实现很简单,就是...

    自旋锁公平性的三种实现代码下载

    4. **MCSLock(Mellor-Crummey and Scott Lock)**:与CLHLock类似,也是一种链表型自旋锁。MCSLock使用单向链表,并且等待线程的自旋状态是通过一个链表节点的next指针来传递的,这减少了不必要的内存访问,提高了...

    golang实现Redis分布式自旋锁+本地自旋锁

    在Golang中,实现分布式自旋锁和本地自旋锁是一种常见的并发控制策略,用于解决多线程或分布式系统中的资源竞争问题。自旋锁的基本思想是,当一个线程试图获取锁时,如果锁已被其他线程持有,它会不断地检查锁的状态...

    redis实现分布式锁,自旋式加锁,lua原子性解锁

    本文将深入探讨如何使用Redis实现分布式锁,以及如何利用自旋式加锁和Lua脚本实现原子性解锁。 首先,我们来理解分布式锁的基本概念。分布式锁是在多节点之间共享资源时,用于协调各个节点的访问控制机制。在分布式...

    linux下自旋锁程序源码.zip

    在Linux操作系统中,自旋锁(Spinlock)是一种用于多线程环境下的低级同步机制。自旋锁的原理是,当一个线程试图获取一个已经被其他线程持有的锁时,它不会像普通互斥锁那样进入睡眠状态,而是会不断地循环检查锁的...

    并发控制之自旋锁.pdf

    自旋锁是操作系统中一种重要的同步机制,尤其在多处理器环境下,用于保护共享资源免受并发访问的影响。自旋锁的设计理念是,在等待锁释放的过程中,持有锁的任务会不断地检查锁的状态,即“自旋”,直到锁变为可用...

    zynq的linux驱动6-使用自旋锁实现竞争保护

    在这个场景下,“zynq的linux驱动6-使用自旋锁实现竞争保护”是一个关于如何在Zynq SoC的Linux驱动中使用自旋锁来避免数据竞争的重要教程。 自旋锁(Spinlock)是一种同步原语,用于在多线程环境下保护共享资源。在...

    CPU自旋锁优化20191020-CLK-new1

    综上所述,CPU自旋锁的优化主要集中在减少数据迁移、降低锁争用以及利用NUMA架构特性,通过MCS自旋锁、CSI和NUMA-Aware Spinlock等策略,来提升多核系统中并发执行的效率和性能。这些技术对于理解和优化大规模并发...

Global site tag (gtag.js) - Google Analytics