spinlock与linux内核调度的关系

spinlock与linux内核调度的关系

注意：Spinlock缺点：一直占用cpu，而且在执行过程中还会锁bus总线，锁总线时其他处理器不能使用总线。

关于自旋锁用法介绍的文章，已经有很多，但有些细节的地方点的还不够透。我这里就把我个人认为大家容易有疑问的地方拿出来讨论一下。

一、自旋锁（spinlock）简介

自旋锁在同一时刻只能被最多一个内核任务持有，所以一个时刻只有一个线程允许存在于临界区中。这点可以应用在多处理机器、或运行在单处理器上的抢占式内核中需要的锁定服务。

二、信号量简介

       这里也介绍下信号量的概念，因为它的用法和自旋锁有相似的地方。

       Linux中的信号量是一种睡眠锁。如果有一个任务试图获得一个已被持有的信号量时，信号量会将其推入等待队列，然后让其睡眠。这时处理器获得自由去执行其它代码。当持有信号量的进程将信号量释放后，在等待队列中的一个任务将被唤醒，从而便可以获得这个信号量。

   三、自旋锁和信号量对比

       在很多地方自旋锁和信号量可以选择任何一个使用，但也有一些地方只能选择某一种。下面对比一些两者的用法。

                                          表1-1自旋锁和信号量对比

应用场合	信号量or自旋锁
低开销加锁（临界区执行时间较快）	优先选择自旋锁
低开销加锁（临界区执行时间较长）	优先选择信号量
临界区可能包含引起睡眠的代码	不能选自旋锁，可以选择信号量
临界区位于非进程上下文时，此时不能睡眠	优先选择自旋锁，即使选择信号量也只能用 down_trylock非阻塞的方式

     

      四、自旋锁与linux内核进程调度关系

       我们讨论下表1-1中的第3种情况（其它几种情况比较好理解），如果临界区可能包含引起睡眠的代码则不能使用自旋锁，否则可能引起死锁。

那么为什么信号量保护的代码可以睡眠而自旋锁就不能呢？

先看下自旋锁的实现方法吧，自旋锁的基本形式如下：

    spin_lock(&mr_lock);
    //临界区
       spin_unlock(&mr_lock);

       跟踪一下spin_lock(&mr_lock)的实现

#define spin_lock(lock)                _spin_lock(lock)

#define _spin_lock(lock)                    __LOCK(lock)

#define __LOCK(lock) \

do { preempt_disable(); __acquire(lock); (void)(lock); } while (0)

       注意到“preempt_disable()”，这个调用的功能是“关抢占”（在spin_unlock中 会重新开启抢占功能）。从中可以看出，使用自旋锁保护的区域是工作在非抢占的状态；即使获取不到锁，在“自旋”状态也是禁止抢占的。了解到这，我想咱们应 该能够理解为何自旋锁保护的代码不能睡眠了。试想一下，如果在自旋锁保护的代码中间睡眠，此时发生进程调度，则可能另外一个进程会再次调用spinlock保护的这段代码。而我们现在知道了即使在获取不到锁的“自旋”状态，也是禁止抢占的，而“自旋”又是动态的，不会再睡眠了，也就是说在这个处理器上不会再有进程调度发生了，那么死锁自然就发生了。

       咱们可以总结下自旋锁的特点：

l         单处理器非抢占内核下：自旋锁会在编译时被忽略；

l         单处理器抢占内核下：自旋锁仅仅当作一个设置内核抢占的开关；

l         多处理器下：此时才能完全发挥出自旋锁的作用，自旋锁在内核中主要用来防止多处理器中并发访问临界区，防止内核抢占造成的竞争。

五、linux抢占发生的时间

       最后在了解下linux抢占发生的时间，抢占分为用户抢占和内核抢占。

用户抢占在以下情况下产生：

l         从系统调用返回用户空间

l         从中断处理程序返回用户空间

内核抢占会发生在：

l         当从中断处理程序返回内核空间的时候，且当时内核具有可抢占性；

l         当内核代码再一次具有可抢占性的时候。（如:spin_unlock时）

l         如果内核中的任务显式的调用schedule()

l         如果内核中的任务阻塞。

基本的进程调度就是发生在时钟中断后，并且发现进程的时间片已经使用完了，则发生

进程抢占。通常我们会利用中断处理程序返回内核空间的时候可以进行内核抢占这个特性来提高一些I/O操作的实时性，如：当I/O事件发生的是时候，对应的中断处理程序被激活，当它发现有进程在等待这个I/O事件的时候，它会激活等待进程，并且设置当前正在执行进程的need_resched标志，这样在中断处理程序返回的时候，调度程序被激活，原来在等待I/O事件的进程（很可能）获得执行权，从而保证了对I/O事件的相对快速响应（毫秒级）。可以看出，在I/O事件发生的时候，I/O事件的处理进程会抢占当前进程，系统的响应速度与调度时间片的长度无关。

1， spinlock介绍

　　spinlock又称自旋锁，线程通过busy-wait-loop的方式来获取锁，任时刻只有一个线程能够获得锁，其他线程忙等待直到获得锁。spinlock在多处理器多线程环境的场景中有很广泛的使用，一般要求使用spinlock的临界区尽量简短，这样获取的锁可以尽快释放，以满足其他忙等的线程。Spinlock和mutex不同，spinlock不会导致线程的状态切换(用户态->内核态)，但是spinlock使用不当(如临界区执行时间过长)会导致cpu busy飙高。

　　2， spinlock与mutex对比

　　2.1，优缺点比较

　　spinlock不会使线程状态发生切换，mutex在获取不到锁的时候会选择sleep。

　　mutex获取锁分为两阶段，第一阶段在用户态采用spinlock锁总线的方式获取一次锁，如果成功立即返回；否则进入第二阶段，调用系统的futex锁去sleep，当锁可用后被唤醒，继续竞争锁。

　　Spinlock优点：没有昂贵的系统调用，一直处于用户态，执行速度快。

　　Spinlock缺点：一直占用cpu，而且在执行过程中还会锁bus总线，锁总线时其他处理器不能使用总线。

　　Mutex优点：不会忙等，得不到锁会sleep。

　　Mutex缺点：sleep时会陷入到内核态，需要昂贵的系统调用。

　　2.2，使用准则

　　Spinlock使用准则：临界区尽量简短，控制在100行代码以内，不要有显式或者隐式的系统调用，调用的函数也尽量简短。例如，不要在临界区中调用read,write,open等会产生系统调用的函数，也不要去sleep；strcpy，memcpy等函数慎用，依赖于数据的大小。

　　3， spinlock系统实现

　　spinlock的实现方式有多种，但是思想都是差不多的，现罗列一下：

　　3.1，glibc-2.9中的实现方法：

int pthread_spin_lock (lock) pthread_spinlock_t *lock;
{
asm ("\n"
"1:\t" LOCK_PREFIX "decl %0\n\t"
"jne 2f\n\t"
".subsection 1\n\t"
".align 16\n"
"2:\trep; nop\n\t"
"cmpl $0, %0\n\t"
"jg 1b\n\t"
"jmp 2b\n\t"
".previous"
: "=m" (*lock)
: "m" (*lock));
return 0;
}

　　执行过程：

　　1，lock_prefix 即 lock。lock decl %0，锁总线将%0(即lock变量)减一。Lock可以保证接下来一条指令的原子性。

　　2， 如果lock=1，decl的执行结果为lock=0，ZF标志位为1，直接跳到return 0；否则跳到标签2。也许要问，为啥能直接跳到return 0呢？因为subsection和previous之间的代码被编译到别的段中，因此jne之后紧接着的代码就是 return 0 (leaveq;retq)。Rep nop在经过编译器编译之后被编译成 pause。

　　3， 如果跳到标签2，说明获取锁不成功，循环等待lock重新变成1，如果lock为1跳到标签1重新竞争锁。

　　该实现采用的是AT&T的汇编语法，更详细的执行流程解释可以参考的文档。

　　3.2，系统自带(glibc-2.3.4)spinlock反汇编代码：

　　系统环境：

2.6.9-89.ELsmp #1 SMP x86_64 x86_64 x86_64 GNU/Linux
(gdb) disas pthread_spin_lock
Dump of assembler code for function pthread_spin_lock:
//eax寄存器清零，做返回值
0x0000003056a092f0 0>: xor %eax,%eax
//rdi存的是lock锁地址，原子减一
0x0000003056a092f2 2>: lock decl (%rdi)
//杯了个催的，加锁不成功，跳转，开始busy wait
0x0000003056a092f5 5>: jne 0x3056a09300 16>
//终于夹上了…加锁成功，返回
0x0000003056a092f7 7>: retq
……………………………………….省略若干nop……………………………………….
0x0000003056a092ff 15>: nop
//pause指令降低CPU功耗
0x0000003056a09300 16>: pause
//检查锁是否可用
0x0000003056a09302 18>: cmpl $0×0,(%rdi)
//回跳，重新锁总线获取锁
0x0000003056a09305 21>: jg 0x3056a092f2 2>
//长夜漫漫，爱上一个不回家的人，继续等~
0x0000003056a09307 23>: jmp 0x3056a09300 16>
0x0000003056a09309 25>: nop
……………………………………….省略若干nop……………………………………….
End of assembler dump.
Glibc的汇编代码还是很简洁的，没有多余的代码。

　　4， Pause指令解释（from intel）：

　　Description

　　Improves the performance of spin-wait loops. When executing a “spin-wait loop,” a Pentium 4 or Intel Xeon processor suffers a severe performance penalty when exiting the loop because it detects a possible memory order violation. The PAUSE instruction provides a hint to the processor that the code sequence is a spin-wait loop. The processor uses this hint to avoid the memory order violation in most situations, which greatly improves processor performance. For this reason, it is recommended that a PAUSE instruction be placed in all spin-wait loops.

　　提升spin-wait-loop的性能，当执行spin-wait循环的时候，笨死和小强处理器会因为在退出循环的时候检测到memory order violation而导致严重的性能损失，pause指令就相当于提示处理器哥目前处于spin-wait中。在绝大多数情况下，处理器根据这个提示来避免violation，藉此大幅提高性能，由于这个原因，我们建议在spin-wait中加上一个pause指令。

　　名词解释(以下为本人猜想)：memory order violation，直译为-内存访问顺序冲突，当处理器在(out of order)乱序执行的流水线上去内存load某个内存地址的值(此处是lock)的时候，发现这个值正在被store，而且store本身就在load之前，对于处理器来说，这就是一个hazard，流水流不起来。

　　在本文中，具体是指当一个获得锁的工作线程W从临界区退出，在调用unlock释放锁的时候，有若干个等待线程S都在自旋检测锁是否可用，此时W线程会产生一个store指令，若干个S线程会产生很多load指令，在store之后的load指令要等待store在流水线上执行完毕才能执行，由于处理器是乱序执行，在没有store指令之前，处理器对多个没有依赖的load是可以随机乱序执行的，当有了store指令之后，需要reorder重新排序执行，此时会严重影响处理器性能，按照intel的说法，会带来25倍的性能损失。Pause指令的作用就是减少并行load的数量，从而减少reorder时所耗时间。

　　An additional function of the PAUSE instruction is to reduce the power consumed by a Pentium 4 processor while executing a spin loop. The Pentium 4 processor can execute a spin-wait loop extremely quickly, causing the processor to consume a lot of power while it waits for the resource it is spinning on to become available. Inserting a pause instruction in a spin-wait loop greatly reduces the processor’s power consumption.

　　Pause指令还有一个附加作用是减少笨死处理器在执行spin loop时的耗电量。当笨死探测锁是否可用时，笨死以飞快的速度执行spin-wait loop，导致消耗大量电量。在spin-wait loop中插入一条pause指令会显著减少处理器耗电量。

　　This instruction was introduced in the Pentium 4 processors, but is backward compat?ible with all IA-32 processors. In earlier IA-32 processors, the PAUSE instruction operates like a NOP instruction. The Pentium 4 and Intel Xeon processors implement the PAUSE instruction as a pre-defined delay. The delay is finite and can be zero for some processors. This instruction does not change the architectural state of the processor (that is, it performs essentially a delaying no-op operation).

　　该指令在笨死中被引入，但是向后兼容所有IA-32处理器，在早期的IA-32处理器中，pause指令以nop的方式来运行，笨死和小强以一个预定义delay的方式来实现pause，该延迟是有限的，在某些处理器上可能是0，pause指令并不改变处理器的架构（位？）状态（也就是说，它是一个延迟执行的nop指令）。至于Pause指令的延迟有多大，intel并没有给出具体数值，但是据某篇文章给出的测试结果，大概有38~40个clock左右（官方数字：nop延迟是1个clock），一下子延迟40个clock，intel也够狠的。

　　This instruction’s operation is the same in non-64-bit modes and 64-bit mode.

　　该指令在64位与非64位模式下的表现是一致的。

　　5， spinlock改进

　　根据上一小节的分析，pause指令最主要的作用是减低功耗和延迟执行下一条指令。所以我们可以有这样的猜想：如果在spin-wait的过程中，记录下加锁失败的次数，对失败的加锁行为进行惩罚(failure penalty)，让等待时间和失败次数成正比，即失败次数越多等待时间越长、执行的pause指令越多。

• 这样的好处有：

　　A，在锁竞争很激烈的情况下，通过增加延迟来降低锁总线的次数，当锁总线次数降低时，系统其它程序对内存的竞争减少，提高系统整体吞吐量。

　　B，在锁竞争很激烈的情况下，减少计算指令的执行次数，降低功耗，低碳低碳！！！

　　C，当锁竞争不激烈时，还能获得和原来一样的性能。

• 但是带来的问题有：

　　A，如果竞争锁失败次数越多，pause次数越多的话，会导致有些线程产生starvation。

　　B，在某些特殊的场景下，锁竞争很小的时候，failure penalty可能会导致程序执行时间变长，进而导致总的加锁次数不一定减少。

• 解决方案：

　　当失败次数超过一个阈值的时候，将失败次数清零，使线程以洁白之躯重新参与竞争；对于少数failure penalty导致执行时间延长的情况，可以先忽略。

• 基于failure penalty的改进实现：

　　为了便于区分，起了很山寨的名字叫newlock，对比对象是sim_spin_lock，sim_spin_lock与pthread_spin_lock算法一致，实现细节基本一致，之所以加入这种对比是为了更加精确地衡量新算法的效果。ecx寄存器记录下本次加锁过程的失败次数。