什么是自旋锁
经过上次的《PostgreSQL查询优化器详解》中大明和牛二哥对PostgreSQL优化器的概要的讲解，小明感到自己已经深深的爱上了数据库内核，小明在GitChat网站上购买了《PostgreSQL优化器入门》的文字网课，还跑到实体书店买了本《PostgreSQL技术内幕：查询优化深度探索》，每天对照着网课和书上的内容仔细研读PostgreSQL的优化器的实现，准备在毕业之后去从事数据库内核开发的工作。
不过，最近在学校的数据库原理课程学到了并发控制的部分，这部分对小明来说有点难度，因为小明没有对数据库的原理进行过实践，无法理解锁的重要性，于是小明又来到自己的哥哥大明家里向大明请教PostgreSQL是如何实现并发控制的。
大明说：“并发控制的部分比较繁杂，我们今天主要关注PostgreSQL锁的实现，不过我们先从最底层的部分开始，先来看一看PostgreSQL是如何实现一个自旋锁的，你知道自旋锁吗？”
小明感觉这个概念好像在哪里听过，但又没什么印象，于是小声的说：“不知道。”
大明哈哈一笑，嘲讽道：“这么轻易就说不知道？自信一点！大胆一点！再问你一遍，知道不知道自旋锁？！”
小明感觉受到了很大的鼓舞，于是大声的说：“我不知道！”
“嗯，很自信嘛。。。来，让朕给你讲讲。PostgreSQL的锁的概念有很多种，比如常见的表锁、行锁、页锁、轻量锁、自旋锁等等，这里面最底层的是实现是自旋锁，它和硬件直接接触，并且屏蔽各种不同硬件和操作系统的细节，通常利用硬件提供的原子操作指令来实现。”
“那为什么要使用这种锁呢？”
“自旋锁是一种互斥锁，它通常是用来保护临界区，这种保护的方式是一种‘不是你死就是我活’的方式，比如说我通过锁获取到这个临界区的访问权限，那么其他人就必须等待，那它怎么等待呢？”
“我知道！”小明抢答道：“如果干等着的话，CPU就不能被充分的利用，所以我知道系统里有一个sleep函数能很好的解决这个问题，如果我们不能获取到锁，那么我们可以睡一会，再来获取锁，我听说sleep函数可以释放CPU资源，这样其他进程或者线程就能充分的利用CPU了，这样CPU即被充分的利用，我也能不停的对锁发出请求，岂不是两全其美。”小明伸了伸衣袖，对大明说：“拿笔来！让我展示一下coding的能力。”
大明给他找了纸和笔，调侃道“看上去很高调嘛？”
“我也想低调，但是实力不允许啊！”小明一边说，一边在纸上写出了自己的蓝图：
while(!spinlock_aquire(&lock))
sleep(100);大明接过笔在小明写的代码上画了一个大大的对勾，对小明的行为表示肯定，然后又画了一个X，解释道：“虽然看上去合理，但是这里存在一个问题，有时我们要保护的临界区只有区区几个指令，锁的持有者实际上占有锁的时间是极短的，换句话说锁的请求者实际上不用等太长时间就能获得锁，这时候就需要考虑这个睡眠是不是合适了。”
小明说：“我读书少，你别骗我，有什么不合适的？不睡眠难道一直占着CPU资源不放，浪费CPU资源？这简直是占着茅坑XXX嘛。”
对，就是占着茅坑XXX，你说的睡眠模式实际上进行了CPU上下文的切换，但这种切换需要非常多的时钟周期，如果我们要保护的临界区很短，这种切换的代价就显得有点大了，所以释放CPU资源还不如占着好。”
小明想了想，说：“哦，那这种锁有点像一个小朋友遇到了想要的玩具，家长不给买的时候的行为。。。”
大明笑着说：“是的，你小时候就是这样，而且，你在地上打滚的时候从来不休息，一直处于滚动的状态，所以你很小的时候就理解了自旋锁的本质，就是忙等。”
自旋锁的伪码
小明继续说：“这样的话，自旋锁的实现就比较容易了，也就是不sleep嘛，我来把它写出来。”说着开始在纸上开始写自旋锁实现的伪码，因为已经了解了自旋锁的基本原理，所以写代码的过程是极为顺利的，小明一边写一边暗暗佩服自己：都是九年义务教育，怎么我就这么优秀呢，像我这样优秀的人，本该灿烂过一生啊。
//让我们假设lock参数是一个线程或进程共享变量
int spinlock_acquire(int *lock)
{
while(*lock != 0)
continue;
*lock = 1;
return *lock;
}
int spinlock_release(int *lock)
{
*lock = 0;
}大明看着小明洋洋自得的写的这段代码，鄙视到：“你觉得这样就能实现一个自旋锁吗？谬矣。”说着拿笔在小明写的自旋锁上画了一个大大的X，然后一边打开电脑，一边继续说：“让我们看看你错在哪里。”说着啪啪啪的在编译器里敲出了和小明同样逻辑的代码，编译之后，通过代码调试工具查看了spinlock_acquire函数的汇编代码：
spinlock1`spinlock_acquire:
0x100000f10 <+0>: pushq %rbp
0x100000f11 <+1>: movq %rsp, %rbp
0x100000f14 <+4>: movq %rdi, -0x8(%rbp)
0x100000f18 <+8>: movq -0x8(%rbp), %rax
0x100000f1c <+12>: cmpl $0x0, (%rax)
0x100000f1f <+15>: je 0x100000f2a
0x100000f25 <+21>: jmp 0x100000f18
0x100000f2a <+26>: movq -0x8(%rbp), %rax
0x100000f2e <+30>: movl $0x1, (%rax)
0x100000f34 <+36>: movq -0x8(%rbp), %rax
0x100000f38 <+40>: movl (%rax), %eax
0x100000f3a <+42>: popq %rbp
0x100000f3b <+43>: retq
0x100000f3c <+44>: nopl (%rax)大明指着屏幕上的汇编代码说：“这段代码是无法作为锁的实现的，因为上面的操作缺乏原子性，比如对lock对应的值是否为0（*lock != 0）的判断就不是一个原子操作，它是通过movq -0x8(%rbp), %rax和cmpl $0x0, (%rax)两个指令来实现。假如有两个线程来获取同一个锁，那么会发生什么情况呢？”说着大明在纸上画了一个示意图：
“你看，这时候问题就出现了，线程A和线程B同时觉得当前的lock中的值是0，也就是说他们两个都能获得锁资源，也就出现了两个线程同时获得锁的情况，你觉得这还合理吗？”
小明羞愧的低下了头，怪不得自己二十多年到头来，还在人海里浮沉，原来是因为不懂汇编语言啊。
看着小明羞愧的表情，大明解释道：“C语言的一条语句可能对应几条汇编指令，在执行期间无法保证它的原子性，所以在高级语言的层面需要借助一些算法或者底层的指令来实现临界区的同步功能，如果想通过高级语言的算法来实现临界区的同步功能，也不是补可以，但是需要使用一些比较精妙的算法（比如Peterson算法），这些方法都有很大的局限性，现在已经很少使用这些方法了，今天我们需要关注的是目前的计算机提供的一些硬件指令，通过这些指令，我们可以借助这些指令来实现临界区的同步功能。”
TAS VS CAS
小明怯怯的问道：“是不是我们学操作系统课程的时候说的那些原子指令？”
“对的，现在大部分硬件都支持两种类型的原子操作指令，比如TAS和CAS指令，下面我们给出他们的伪码。”说着，大明拿了一张新的白纸，边写边说道：“TEST-AND-SET简称为TAS，它的流程是向内存变量写入1，然后返回内存变量的原值，伪码是这样的。”
int TAS(int *lock)
{
int temp = *lock;
*lock = 1;
return int temp;
}“COMPARE-AND-SWAP简称CAS，它的流程是比较锁中的值和期望值，如果锁中的值和期望值相同，则设置为新值，返回true,否则不设置新值，返回false，它的伪码是这样的。”大明继续写道。
int CAS(int *lock, int expect, int new)
{
if(*lock == expect)
{
*lock = new;
return true;
}
return false;
}大明提示道：“注意，上面的伪码是借用高级语言的形式来描述这两种类型的指令的含义，实际上它是一个完整的原子操作，在X86架构的CPU中，分别提供了XCHG指令和CMPXCHG指令来实现TAS和CAS操作，PostgreSQL在X86架构下采用的是基于XCHG指令的TAS来实现的自旋锁。”
小明兴奋的说：“我已经迫不及待的想看看PostgreSQL是怎么使用TAS指令来实现自旋锁的了。”
大明看着小明手舞足蹈的神态，做了一个calmdown的手势，然后说：“稍安勿躁，不要急，再过一会精神病院的救护车就到了。在这之前我们先来谈一下TTAS。”
“TTAS？感觉像是TEST AND TEST-AND-SET？”
“是的，TAS虽然已经足够我们使用，但是也带来一个问题，大部分CPU实现TAS的方法是锁住总线，一旦锁住总线就等于一个CPU占用了整个总线，而频繁的锁住总线会降低CPU的使用效率，所以在进入TAS之前，我们可以先做一个粗略的检测，这个检测不在原子操作之中，但是它可以让我们快速的知道目前锁的状态，如果第一个TEST检测到锁已经被占用了，那么我们就再等一会，就不用进行TAS了，这样就避免了锁住总线，如果第一个TEST发现锁没有被占用，那么就值得去做TAS。”
小明说：“但在第一个TEST和TEST-AND-SET之间，锁的状态可能会被其他CPU上的进程修改掉吧？”
“是的，所以这个TEST只是我们提高性能的一个手段。比如在PostgreSQL数据库中，它就是采用的TTAS的方法。”说着，大明打开了PostgreSQL源代码，找到了TAS实现的部分：
static __inline__ int
tas(volatile slock_t *lock)
{
register slock_t _res = 1;
__asm__ __volatile__(
" cmpb $0,%1 \n"
" jne 1f \n"
" lock \n"
" xchgb %0,%1 \n"
"1: \n"
: "+q"(_res), "+m"(*lock)
:
: "memory", "cc");
return (int) _res;
}大明一边用鼠标在编译器里划住了tas函数，一边说：“从这段汇编代码可以看出，CMP指令和下面的XCHG不能组成一个原子操作，比如一个线程B已经持有了锁，线程A做了CMP指令也发现了有其他线程已经占有了锁资源，于是他就会JNE跳过XCHG指令，但是很可能在CMP指令之后，线程B就立即释放了锁资源。”大明在纸上画了一个示意图：
“XCHG指令会尝试交换两个操作数，如果想要获得一个锁，也就是说我们打算在‘锁对应的值是0的情况下把锁的值设置为1’，同时我们还可以用0和1来代表TEST-AND-SET是否成功，那么对上面的汇编代码翻译成高级语言就变成下面这样。”大明开始在纸上写出了对应于PostgreSQL的tas函数的伪码：
static __inline__ int
tas(volatile slock_t lock)
{
register slock_res = 1;
if(*lock != 1) //CMP指令
{
//下面3行是原子操作，对应XCHG
int temp = *lock;
lock = 1; //同*lock = res;
res = temp;
}
return (int) _res;
}小明听得云里雾里的，只好说：“感觉听着有点吃力，”
大明说：“不要担心嘛，自旋锁的事才刚刚开始，有了TAS我们才能继续实现PostgreSQL的自旋锁，让我们来看看自旋锁的实现吧。”
PostgreSQL的自旋锁
大明继续说道：“在有些CPU架构下，PostgreSQL没有直接使用TTAS，而是先实现了TAS，然后借用TAS_SPIN函数(或者说宏)来实现的自旋锁。”
#define TAS_SPIN(lock) (*(lock) ? 1 : TAS(lock))“有了TAS_SPIN我们是不是就很容易实现一个自旋锁了呢？”大明问道。
小明想了想说：“让我来写一下，看看这次能不能实现一个可用的自旋锁。”说着小明在纸上写了起来：
void spinlock_acquire(int *lock)
{
while(TAS_SPIN(lock));
}写完之后，小明又推演了几遍，感觉没什么错误了，于是帅气的摇了摇头，说道：“怎么样，是不是很佩服我这样美貌与智慧并重的人？”
“嗯，这个自旋锁是可用的，不过美貌和智慧你都没做到，你做到了病重，精神病院的救护车还没到，我们还有时间继续说自旋锁。”大明调侃道，“我们还能继续优化它。比如适当的偷懒，这种自旋目的是不放弃CPU，但也没必要不停的旋，我们可以用空指令来适当的让CPU歇一会，而不必过度旋转，旋转太频繁了浪费电，我们使用nop指令来进行偷懒”，说着大明在PostgreSQL的源代码中指出了spin_delay函数。
static __inline__ void
spin_delay(void)
{
__asm__ __volatile__(
" rep; nop \n");
}大明继续说道：“另外，我们也应该处理一些特殊的情况，比如尝试了很多次TAS之后仍然无法获得锁资源，那么就进入sleep，也就是交出CPU资源，需要注意的是睡眠的时间是随机的，但不能超出上下界。”
//第一次sleep的时间，sleep的时间逐步递增，第一次是1000微秒
if (status->cur_delay == 0) /* first time to delay? */
status->cur_delay = MIN_DELAY_USEC;
pg_usleep(status->cur_delay);“当然，如果旋转了很长时间，仍然没有办法获得锁资源，就进入自杀模式，因为我们假设自旋锁保护的临界区都很短，如果很长时间还获取不到锁资源，那么就可能出问题了。”
if (++(status->delays) > NUM_DELAYS)
s_lock_stuck(status->file, status->line, status->func);“这基本上就是PostgreSQL自旋锁的实现了，不过还需要注意我们只谈了X86架构下的实现方法，在不同的CPU架构下，TAS的实现是不同的，比如在MIPS架构下提供的是ll和sc指令，我们要借助这两个指令来实现TAS。”
“明白了，看来我需要学的东西还有很多。”小明沮丧的说。
“不要这么悲观嘛，你不了解这些知识主要是因为你还没有参加工作，还是学生，还在学习的阶段，等你参加工作了，时间长了，也就习惯了。”大明笑着说，“反正债多了不愁，在我们结束之前，再来补充一下自旋锁释放的知识。”
“锁的释放，直接把值设置成0就可以了嘛。”
“bingo！是的，我也是这么认为的，但是还有一个注意事项。”
“什么注意事项，难道这还有什么幺蛾子吗？”小明惊奇道。
“有一个很大的幺蛾子，就是目前很多CPU为了提高执行效率，实现了乱序执行功能，关于乱序执行的具体内容我们就不展开了，以免你不好消化。不过需要记住的是，如果把释放锁写成只是简单设置lock的值，由于乱序执行的作用，有些临界区中的指令可能会在lock释放后才执行，这就相当于两个进（线）程共同进入了临界区，那肯定会出问题，所以我们可以采用内存屏障的方式来保证锁释放的有序性，你看，PostgreSQL的有些锁释放时用的是这种方式。”说着，大明在源代码中标出了一行锁释放的代码：
do { __memory_barrier(); *(lock) = 0; } while (0)。“好吧，我记下了，念了这么多年的书，我觉得还是幼儿园适合我。”小明苦着脸说。
“没事，中午我们去吃点好的，弥补一下你受伤的心灵，我准备一下，咱们马上就出发。”PostgreSQL 自旋锁浅析
