透过Linux内核看无锁编程

从全局着眼，逐步废弃了大内核锁来降低锁的粒度；从细处下手，不断对局部代码进行优化，用无锁编程替代基于锁的方案，如seqlock及RCU等；不断减少锁冲突程度、降低等待时间，如Double-checkedlocking和原子锁等。

无论什么时候当临界区中的代码仅仅需要加锁一次，同时当其获取锁的时候必须是线程安全的，此时就可以利用Double-checkedLocking模式来减少锁竞争和加锁载荷。目前Double-checkedLocking已经广泛应用于单例(Singleton)模式中。内核设计者基于此思想，巧妙的将Double-checkedLocking方法运用于内核代码中。

当一个进程已经僵死，即进程处于TASK_ZOMBIE状态，如果父进程调用waitpid()系统调用时，父进程需要为子进程做一些清理性的工作，代码如下所示：

清单3。少锁操作

984staticintwait_task_zombie(task_t*p，intnoreap，

985structsiginfo__user*infop，

986int__user*stat_addr，structrusage__user*ru)

987{

……

1103if(p->real_parent！=p->parent){

1104write_lock_irq(tasklist_lock);

1105/*Double-checkwithlockheld。*/

1106if(p->real_parent！=p->parent){

1107__ptrace_unlink(p);

1108//TODO：isthissafe？

1109p->exit_state=EXIT_ZOMBIE;

……

1120}

1121write_unlock_irq(tasklist_lock);

1122}

……

1127}

如果将write_lock_irq放置于1103行之前，锁的范围过大，锁的负载也会加重，影响效率；如果将加锁的代码放到判断里面，且没有1106行的代码，程序会正确吗？在单核情况下是正确的，但在双核情况下问题就出现了。一个非主进程在一个CPU上运行，正准备调用exit退出，此时主进程在另外一个CPU上运行，在子进程调用release_task函数之前调用上述代码。子进程在exit_notify函数中，先持有读写锁tasklist_lock，调用forget_original_parent。主进程运行到1104处，由于此时子进程先持有该锁，所以父进程只好等待。在forget_original_parent函数中，如果该子进程还有子进程，则会调用reparent_thread()，将执行p->parent=p->real_parent;语句，导致两者相等，等非主进程释放读写锁tasklist_lock时，另外一个CPU上的主进程被唤醒，一旦开始执行，继续运行将会导致bug。

严格的说，Double-checkedlocking不属于无锁编程的范畴，但由原来的每次加锁访问到大多数情况下无须加锁，就是一个巨大的进步。同时从这里也可以看出一点端倪，内核开发者为了降低锁冲突率，减少等待时间，提高运行效率，一直在持续不断的进行改进。

原子操作可以保证指令以原子的方式执行——执行过程不被打断。内核提供了两组原子操作接口：一组针对于整数进行操作，另外一组针对于单独的位进行操作。内核中的原子操作通常是内联函数，一般是通过内嵌汇编指令来完成。对于一些简单的需求，例如全局统计、引用计数等等，可以归结为是对整数的原子计算。

1。Lock-free应用场景一——SpinLock

SpinLock是一种轻量级的同步方法，一种非阻塞锁。当lock操作被阻塞时，并不是把自己挂到一个等待队列，而是死循环CPU空转等待其他线程释放锁。Spinlock锁实现代码如下：

清单4。spinlock实现代码

staticinlinevoid__preempt_spin_lock(spinlock_t*lock)

{

……

do{

preempt_enable();

while(spin_is_locked(lock))

cpu_relax();

preempt_disable();

}while(！_raw_spin_trylock(lock));

}

staticinlineint_raw_spin_trylock(spinlock_t*lock)

{

charoldval;

__asm____volatile__(

xchgb%b0，%1

：=q(oldval)，=m(lock->lock)

：0(0)：memory);

returnoldval>0;

}

汇编语言指令xchgb原子性的交换8位oldval(存0)和lock->lock的值，如果oldval为1(lock初始值为1)，则获取锁成功，反之，则继续循环，接着relax休息一会儿，然后继续周而复始，直到成功。

对于应用程序来说，希望任何时候都能获取到锁，也就是期望lock->lock为1，那么用CAS原语来描述_raw_spin_trylock(lock)就是CAS(lock->lock，1，0);

如果同步操作总是能在数条指令内完成，那么使用SpinLock会比传统的mutexlock快一个数量级。SpinLock多用于多核系统中，适合于锁持有时间小于将一个线程阻塞和唤醒所需时间的场合。

pthread库已经提供了对spinlock的支持，所以用户态程序也能很方便的使用spinlock了，需要包含pthread。h。在某些场景下，pthread_spin_lock效率是pthread_mutex_lock效率的一倍多。美中不足的是，内核实现了读写spinlock锁，但pthread未能实现。

2。L