Spinlock

来自osdev
跳到导航 跳到搜索

概述

与所有形式的可重入锁（reentrancy locks）一样，自旋锁（spinlocks）用于确保对资源(例如，数据结构、硬件等)的有序访问，以便在一个上下文中运行的软件不会获得该资源的不一致视图，因为在另一个上下文中运行的软件正在修改资源。 例如，想象一个包含一个人的名字和姓氏的结构，该结构当前包含数据 “Fred” 和 “Smith”。 如果一个CPU将此数据更改为“Jane”和“Doe”，那么它可能需要会先后将名字更改为“Jane”，然后将姓氏更改为“Doe”， 不同的CPU(或线程或IRQ处理程序)可能在错误的时间访问此结构并读取“Jane”和“Smith”。 为了防止此问题，您可以使用锁，这样在任何时候只有一个上下文可以拥有锁，并且只有拥有锁的上下文才允许访问资源。 例如，如果一个CPU将该数据更改为“Jane”和“Doe”，它将获取锁，然后更改数据，然后释放锁； 如果其他人试图访问该结构，则在访问数据之前必须等待，直到它可以获取锁。

自旋锁是一种可重入锁，其中CPU反复尝试获取该锁，直到成功为止 (或者，CPU “自旋（Spin）” 直到成功为止)。 如果锁可以在第一次尝试时获得，并且不需要自旋，则锁是“无争用（uncontended）”的。 如果锁是“争用的（contended）”(需要多次尝试获取锁)，自旋锁可能会浪费CPU时间。 由于竞争/自旋而浪费的CPU时间可能比其他形式的锁开销有时更多，有时更少 （例如，在某些情况下，浪费一点CPU时间自旋比在切换任务的开销上浪费更多CPU时间要好）。


锁结构

锁的基础

x86处理器上有几个原子操作可以设置和比较内存或寄存器，它们可以用作自旋锁的基础。 我将重点介绍本讨论的BTS和BTR指令(但也可以使用其他指令，如CMPXCHG、ADD/SUB、INC/DEC等)。

锁的基础看起来像这样 (但通常实现为宏): 

acquireLock:
.retry:
    lock bts [lock],0
    jc .retry
    ret


releaseLock:
    lock btr [lock],0
    ret


改进的锁

基础版的锁有一些性能问题。 前面实现的锁可以授予一个CPU独占使用总线，因此可以防止其他CPU在 (非常短的) 时间内访问总线。 如果不经常使用这个锁，这不是问题， 但是(当出现争用时)上面显示的锁持续使用它，因此会严重影响其他CPU使用总线的能力，从而降低它们的速度。 为了避免这种情况，最好避免锁，除非有必要。 这可以通过在尝试获取锁之前测试锁是否空闲来实现： 

acquireLock:
    lock bts [lock],0        ;尝试获取锁(以防锁并不处于争用状态)
    jc .spin_wait            ;如果锁定，则自旋 (组织代码，以便通常不进行条件跳转) 
    ret                      ;获得锁

.spin_wait:
    test dword [lock],1      ;锁是自由的吗？
    jnz .spin_wait           ;否，等待
    jmp acquireLock          ;也许，重试（也可以在此处重复bts、jc、ret指令，而不是jmp）

甚至： 

.spin_wait:
    test dword [lock],1      ;锁是自由的吗？
    jnz .spin_wait           ;否，等待

acquireLock:
    lock bts [lock],0        ;尝试获取锁(以防锁其实并不在争用)
    jc .spin_wait            ;如果锁定，则自旋 (组织代码，以便通常不进行条件跳转) 
    ret                      ;获得锁

此外，在释放自旋锁时可以避免使用前面的锁争用。 CPU保证写入对齐的uint32_t是原子性的，因此释放锁的代码可以更改为: 

releaseLock:
    mov dword [lock],0
    ret

支持超线程的CPU也有一个问题。 在这种情况下，实际CPU的资源(管道等)由2个(或更多)逻辑CPU共享，如果这些逻辑CPU中的一个在自旋，则可能会浪费本可以由另一个逻辑CPU使用的资源。 为了减少这个问题，英特尔引入了暂停指令，该指令旨在用于紧密（tight）的轮询循环 (如自旋锁)。 PAUSE指令的操作码是经过特别选择的，因此它的行为就像旧CPU上的NOP一样 (在较旧的CPU上，它实际上是“REP NOP”，其中“REP”前缀被忽略)。 为了提高支持超线程的cpu的性能，可以对自旋锁进行如下修改: 

acquireLock:
    lock bts [lock],0        ;尝试获取锁（如果锁未被争夺）
    jc .spin_with_pause
    ret

.spin_with_pause:
    pause                    ; 告诉CPU我们在自旋
    test dword [lock],1      ; 锁被释放了吗？
    jnz .spin_with_pause     ; 不，等待
    jmp acquireLock          ; 重试

releaseLock:
    mov dword [lock],0
    ret

也可以在不尝试获取自旋锁的情况下检查自旋锁的状态。 这可以在没有任何锁的情况下完成（CPU保证从对齐的uint32_t读取的数据也是原子性的）： 

    cmp dword [lock],0
    je .free
    jne .locked

锁定位

现代CPU倾向于在高速缓存行上操作; 对于大多数现代80x86 CPU，高速缓存行是64字节区域。 每个缓存线都有一个状态（修改、独占等），不同的CPU相互（以及从内存控制器）请求缓存线。 如果高速缓存线包含处于争用中的锁，则该高速缓存线可能会保留在一个CPU的高速缓存中，而该CPU正在重复测试该锁(因此不会导致任何总线流量)，直到另一个CPU修改该高速缓存线。 如果另一个CPU修改了该缓存行中的某些内容，则该缓存行的数据将被传输到另一个CPU并进行修改，然后再次传输回第一个CPU (这确实花费了一些总线流量)。 为了减少不必要的总线流量（由其他CPU修改包含锁的缓存线中的其他数据引起），英特尔建议为每个重入锁使用整个缓存线。

此外，锁应该在合适的边界(例如uint32_t边界)上正确对齐。 最坏的情况是将锁跨页面边界和缓存行边界分开; 但是通常，访问未对齐的uint16_t/uint32_t/uint64_t可能会受到惩罚。


锁调试

对于必须处理并发(例如内核)的大型复杂软件，涉及不正确使用可重入锁的某些类型的错误可能是难以避免的。 更糟糕的是，涉及可重入锁的错误通常取决于确切的时间，并且可能是难以检测和纠正的间歇性错误。 这些问题包括“死锁”（例如，获得锁的人试图再次获得锁）、释放未获得的锁、未能足够快地释放锁（并导致过度的锁争用）等。

很容易在代码中添加额外的检查来释放锁，以检测锁是否真的是首先获得的。 对于其他检查，需要额外的信息。

自旋锁本身实际上只需要一个位，但实际上通常使用完整的uint32_t或整个缓存线。 额外的空间可用于存储附加信息，以帮助检测错误。 对于一个简单的示例，如果使用uint32_t，则一位可以是锁本身，并且剩余的31位可以用于存储某些东西以识别谁获得了锁 (例如，CPU号或线程ID)。 这样，需要修改获取锁的代码，以检查同一个CPU或同一个线程是否正在第二次尝试获取锁（并检测某些类型的死锁）， 并且可以修改释放锁的代码，以检测锁是否由获取它的相同CPU或线程释放。

以类似的方式，第二个uint32_t可以用作计数器，以跟踪有多少次尝试获取锁失败 (例如，由于锁争用)， 这些计数器可用于查找性能瓶颈和可伸缩性问题。 还可以 “完全检测” 重入锁以跟踪其他信息，例如已获取的次数和已获取的循环总数 (以确定所获取的锁的平均循环数)。

当然，可以使用条件编译来启用/禁用这些额外检查。 例如，您可能有一个“生产”版本的内核，没有启用这些额外的检查(为了更好的性能)； 以及启用了所有这些检查的内核的 “测试” 版本。

C宏

以下是可用于自旋锁的C语言示例宏： 

#define DECLARE_LOCK(name) volatile int name ## Locked
#define LOCK(name) \
	while (!__sync_bool_compare_and_swap(& name ## Locked, 0, 1)); \
	__sync_synchronize();
#define UNLOCK(name) \
	__sync_synchronize(); \
	name ## Locked = 0;

调用DECLARE_LOCK(name) 以创建锁定义，LOCK(name) 以获取锁，以及UNLOCK(name)以释放它。 LOCK宏将自旋，直到锁被释放，然后继续。 这段代码利用了特定于GCC的复杂功能，但它也在Clang上也可以编译。

另见

文章

论坛主题

外部链接

取自“http://wiki.foofun.cn//index.php?title=Spinlock&oldid=851”