透过 Linux 内核看无锁编程
简介： 多核多线程已经成为当下一个时髦的话题，而无锁编程更是这个时髦话题中的热点话题。Linux 内核可能是当今最大最复杂的并行程序之一，为我们分析多核多线程提供了绝佳的范例。内核设计者已经将最新的无锁编程技术带进了 2.6 系统内核中，本文以 2.6.10 版本为蓝本，带领您领略多核多线程编程的真谛，窥探无锁编程的奥秘，体味大师们的高雅设计
非阻塞型同步 (Non-blocking Synchronization) 简介
如何正确有效的保护共享数据是编写并行程序必须面临的一个难题，通常的手段就是同步。同步可分为阻塞型同步（Blocking Synchronization）和非阻塞型同步（ Non-blocking Synchronization）。
阻塞型同步是指当一个线程到达临界区时，因另外一个线程已经持有访问该共享数据的锁，从而不能获取锁资源而阻塞，直到另外一个线程释放锁。常见的同步原语有mutex、maphore 等。如果同步方案采用不当，就会造成死锁（deadlock），活锁（livelock）和优先级反转（priority inversion），以及效率低下等现象。
为了降低风险程度和提高程序运行效率，业界提出了不采用锁的同步方案，依照这种设计思路设计的算法称为非阻塞型算法，其本质特征就是停止一个线程的执行不会阻碍系统中其他执行实体的运行。
当今比较流行的 Non-blocking Synchronization 实现方案有三种：
1. Wait-free
Wait-free 是指任意线程的任何操作都可以在有限步之内结束，而不用关心其它线程的执行速度。 Wait-free 是基于 per-thread 的，可以认为是 starvation-free 的。非常遗憾的是实际情况并非如此，采用 Wait-free 的程序并不能保证 starvation-free，同时内存消耗也随线程数量而线性增长。目前只有极少数的非阻塞算法实现了这一点。
2. Lock-free
Lock-Free 是指能够确保执行它的所有线程中至少有一个能够继续往下执行。由于每个线程不是 starvation-free 的，即有些线程可能会被任意地延迟，然而在每一步都至少有一个线程能够往下执行，因此系统作为一个整体是在持续执行的，可以认为是 system-wide 的。
所有 Wait-free 的算法都是 Lock-Free 的。
3. Obstruction-free
冰激凌图片Obstruction-free 是指在任何时间点，一个孤立运行线程的每一个操作可以在有限步之内结束。只要没有竞争，线程就可以持续运行。一旦共享数据被修改，Obstruction-free 要求中止已经完成的部分操作，并进行回滚。所有 Lock-Free 的算法都是 Obstruction-free 的。
综上所述，不难得出 Obstruction-free 是 Non-blocking synchronization 中性能最差的，而 Wait-free 性能是最好的，但实现难度也是最大的，因此 Lock-free 算法开始被重视，并广泛运用于当今正在运行的程序中，比如linux内核。
一般采用原子级的 read-modify-write 原语来实现 Lock-Free 算法，其中 LL 和 SC 是 Lock-Free 理论研究领域的理想原语，但实现这些原语需要 CPU 指令的支持，非常遗憾的是目前没有任何 CPU 直接实现了 SC 原语。根据此理论，业界在原子操作的基础上提出了著名的 CAS（Compare - And - Swap）操作来实现 Lock-Free 算法，Intel 实现了一条类似该操作的指令：cmpxchg8。
CAS 原语负责将某处内存地址的值（1 个字节）与一个期望值进行比较，如果相等，则将该内存地址处的值替换为新值，CAS 操作伪码描述如下：
清单 1. CAS 伪码
Bool CAS(T* addr, T expected, T newValue) { if( *addr == expected ) { *addr = newValue; return true; } el 十大珠宝排名 return fal; } |
|
在实际开发过程中，利用 CAS 进行同步，代码如下所示：
清单 2. CAS 实际操作中秋慰问
do{ 备份旧数据； 基于旧数据构造新数据； }while(!CAS( 内存地址，备份的旧数据，新数据 )) |
|
就是指当两者进行比较时，如果相等，则证明共享数据没有被修改，替换成新值，然后继续往下运行；如果不相等，说明共享数据已经被修改，放弃已经所做的操作，然后重新执行刚才的操作。容易看出 CAS 操作是基于共享数据不会被修改的假设，采用了类似于数据库的 commit-retry 的模式。当同步冲突出现的机会很少时，这种假设能带来较大的性能提升。
回页首
加锁的层级
根据复杂程度、加锁粒度及运行速度，可以得出如下图所示的锁层级：
图 1. 加锁层级
其中标注为红色字体的方案为 Blocking synchronization，黑色字体为 Non-blocking synchronization。Lock-bad 和 Lockless-bad 两者之间的区别仅仅是加锁粒度的不同。
图中最底层的方案就是大家经常使用的mutex和 maphore 等方案，代码复杂度低，但运行效率也最低。
空调多久加一次氟
回页首
Linux 内核中的无锁分析
Linux 内核可能是当今最大最复杂的并行程序之一，它的并行主要来至于中断、内核抢占及 SMP 等。内核设计者们为了不断提高 Linux 内核的效率，从全局着眼，逐步废弃了大内核锁来降低锁的粒度；从细处下手，不断对局部代码进行优化，用无锁编程替代基于锁的方案，如qlock及 RCU 等；不断减少锁冲突程度、降低等待时间，如 Double-checked locking 和原子锁等。
内核无锁第一层级 — 少锁
无论什么时候当临界区中的代码仅仅需要加锁一次，同时当其获取锁的时候必须是线程安全的，此时就可以利用 Double-checked Locking 模式来减少锁竞争和加锁载荷。目前 Double-checked Locking 已经广泛应用于单例 (Singleton) 模式中。内核设计者基于此思
想，巧妙的将 Double-checked Locking 方法运用于内核代码中。
当一个进程已经僵死，即进程处于 TASK_ZOMBIE 状态，如果父进程调用waitpid() 系统调用时，父进程需要为子进程做一些清理性的工作，代码如下所示：
清单 3. 少锁操作
984 static intwait_task_zombie(task_t *p, intnoreap, 985 structsiginfo __ur *infop, 986 int __ur *stat_addr, structrusage __ur *ru) 987 { …… 1103 if (p->real_parent != p->parent) { 1104 write_lock_irq(&tasklist_lock); 1105 /* Double-check with lock held. */ 1106 if (p->real_parent != p->parent) { 1107 __ptrace_unlink(p); 1108 // TODO: is this safe? 1109 p->exit_state = EXIT_ZOMBIE; …… 接收机灵敏度 1120 } 1121 write_unlock_irq(&tasklist_lock); 1122 } …… 沉寂的反义词 1127 } |
|
如果将write_lock_irq放置于 1103 行之前，锁的范围过大，锁的负载也会加重，影响效率；如果将加锁的代码放到判断里面，且没有 1106 行的代码，程序会正确吗？在单核情况下是正确的，但在双核情况下问题就出现了。一个非主进程在一个 CPU 上运行，正准备调用 exit 退出，此时主进程在另外一个 CPU 上运行，在子进程调用relea_task函数之前调用上述代码。子进程在exit_notify函数中，先持有读写锁tasklist_lock，调用forget_original_parent。主进程运行到 1104 处，由于此时子进程先持有该锁，所以父进程只好等待。在forget_original_parent函数中，如果该子进程还有子进程，则会调用reparent_thread()，将执行 p->parent = p->real_parent; 语句，导致两者相等，等非主进程释放读写锁tasklist_lock时，另外一个 CPU 上的主进程被唤醒，一旦开始执行，继续运行将会导致 bug。
严格的说，Double-checked locking 不属于无锁编程的范畴，但由原来的每次加锁访问到大多数情况下无须加锁，就是一个巨大的进步。同时从这里也可以看出一点端倪，内核开发者为了降低锁冲突率，减少等待时间，提高运行效率，一直在持续不断的进行改进。
艺术理论中小学教师网内核无锁第二层级 — 原子锁
原子操作可以保证指令以原子的方式执行——执行过程不被打断。内核提供了两组原子操作接口：一组针对于整数进行操作，另外一组针对于单独的位进行操作。内核中的原子操作通常是内联函数，一般是通过内嵌汇编指令来完成。对于一些简单的需求，例如全局统计、引用计数等等，可以归结为是对整数的原子计算。
内核无锁第三层级 — Lock-free
1. Lock-free 应用场景一 —— Spin Lock
Spin Lock 是一种轻量级的同步方法，一种非阻塞锁。当 lock 操作被阻塞时，并不是把自己挂到一个等待队列，而是死循环 CPU 空转等待其他线程释放锁。 Spin lock 锁实现代码如下：
