Linux 内核中的无锁分析

Linux 内核可能是当今最大最复杂的并行程序之一，它的并行主要来至于中断、内核抢占及 SMP 等。内核设计者们为了不断提高 Linux 内核的效率，从全局着眼，逐步废弃了大内核锁来降低锁的粒度；从细处下手，不断对局部代码进行优化，用无锁编程替代基于锁的方案，如 seqlock 及 RCU 等；不断减少锁冲突程度、降低等待时间，如 Double-checked locking 和原子锁等。

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

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

清单 3. 少锁操作

984 static int wait_task_zombie(task_t *p, int noreap,

985 struct siginfo __user *infop,

986 int __user *stat_addr, struct rusage __user *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 上运行，在子进程调用 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-checked locking 不属于无锁编程的范畴，但由原来的每次加锁访问到大多数情况下无须加锁，就是一个巨大的进步。同时从这里也可以看出一点端倪，内核开发者为了降低锁冲突率，减少等待时间，提高运行效率，一直在持续不断的进行改进。

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

1. Lock-free 应用场景一 —— Spin Lock

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

清单 4. spin lock 实现代码

static inline void __preempt_spin_lock(spinlock_t *lock)

{

……

do {

preempt_enable();

while (spin_is_locked(lock))

cpu_relax();

preempt_disable();

} while (!_raw_spin_trylock(lock));

}

static inline int _raw_spin_trylock(spinlock_t *lock)

{

char oldval;

__asm__ __volatile__(

"xchgb %b0,%1"

:"=q" (oldval), "=m" (lock->lock)

:"0" (0) : "memory");

return oldval > 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);大电流电感

 2/5   首页 上一页 1 2 3 4 5 下一页 尾页