作者: Nick Qi

0.简介

Linux内核中并发处理、抢占调度的支持以及中断的处理都需要处理竞争条件和同步问题，
下面我将通过《Linux设备驱动程序》以及相关文档中的内核同步机制以及使用方法做一
个总结。

竞争条件是指代码段的实际效果依赖于代码段的执行顺序。包含可能产生竞争条件的代码
被叫做临界区。在Linux内核添加了SMP支持之后，竞争条件和临界区就成了内核设计和
实现主要关注的问题之一。

1.Linux 内核中的锁

避免锁相关问题的一个建议：keep it simple。

1.0.内核锁的两种主要类型

内核锁主要分为两种类型：spinlock和semaphore。

spinlock很简单，如果你不能获取到它，你就忙等待（spinning）。它只允许一个所有者，
spinlocks非常小而且快，可以在任何需要的地方使用它。

semaphore可以有多个所有者，但它通常也只有一个所有者（取决于初始值）。当你不能获
取到当前的semaphore时，当前的任务会被添加到semaphore的waiter队列中，当
semaphore被释放时它会依次唤醒队列中的任务。当你在semahore上排队等待时，cpu可
以执行别的指令，不需要忙等待。但是在某些情况下内核代码是不允许睡眠的，这些情
况下就不能使用semaphore。

这两种锁都不是递归的，意味着你不能多次持有或者释放同一个锁。
递归锁

1.1.只在用户空间上下文中上锁

如果你要保护的数据只在用户空间上下文中被访问到，那你可以只用一个简单的semaphore就可
以很好的保护它了。

1.2.在用户空间和软中断之间上锁

如果软中断和用户空间共享数据，那你需要处理两个问题。首先，当前的用户上下文可能被软
中断所中断；其次，临界区可能被另一个cpu访问。这种情况下你可以使用
spin_lock_softirq()(include/linux/spinlock.h)。它禁用当前cpu的软中断，然
后获取spinlock。

注意你也可以使用spin_lock_irq()或者spin_lock_irqsave同时禁用硬件中断。

对于UP，这些技术也同样适用，它只需要禁用软中断就行了，UP中没有spinlock。

1.3.用户空间和tasklets(timers)

tasklets和timers，它们实质上都是软中断，所以可以参考软中断的上锁策略。

1.4.tasklets(timers)之间

有时候tasklet(timer)希望和另一个tasklet(timer)共享数据

1.4.0.同一个tasklet(timer)

因为同一个tasklet不会两个cpu上运行，所以你不用担心tasklet的重入问题。

1.4.1.不同tasklet(timer)之间

如果另外一个tasklet/timer想和tasklet/timer共享数据，你就需要使用spin_lock()和
spin_unlock()。

1.5.软中断之间

使用spinlock()和spin_unlock()来共享数据。

2.硬件中断上下文

硬件中断通常需要和tasklet以及软中断通信。

2.0.硬件中断和软中断之间的锁

如果硬件中断处理函数和软中断共享数据，你需要注意两个问题。首先，软中断的处理可能被
硬件中断；其次，临界区可能被另一个cpu的硬件中断访问。这里通常使用
spin_lock_irq()和spin_unlock_irq()。

2.1.cheat sheet

Cheat Sheet For Locking

3.常见的问题

3.0.死锁

一个常见的错误是一段代码尝试两次获取同一个锁：这样它就会永远自旋，等待锁被释放。

另一种稍微复杂的情况是，软中断和用户上下文共享同一段代码，如果你使用spin_lock()来
保护它，那么用户上下文在持有锁的时候就有可能被软中断中断，然后软中断中的
spin_lock()就可能永远自旋。

更复杂的情形是由两个或者以上的锁造成的死锁。

3.1.预防死锁

最好的的锁是封装良好的：它们绝对不会暴露在头文件中，也不会被不在同一个文件的函数持
有。这种情况下代码一般不会死锁，因为当它已经持有一个锁的时候它不会再尝试持有
别的锁。

当你提供回调或者挂钩函数时，这里可能会出现一个经典的问题：如果你在调用这些函数时持
有锁的话，你就可能死锁。不要这样做，因为其他的程序员可能会抓住你然后痛扁你。

3.2.0.不要太过热衷于预防死锁

死锁是严重的问题，但还是没有数据损坏来的严重。一段代码，它首先获取一个读锁；然后搜
索链表，如果没有找到想要的数据就释放读锁，然后持有写锁并插入数据到链表。这段
代码中有竞争条件(代码的执行效果和执行时间有关系)。

如果你不能看出问题所在，那你TMD还是离我的代码远点。

4.锁的性能和时间

在考量锁算法的速度时，主要有三个问题需要考虑。首先是并发：一段代码获取锁之后有多少
代码会等待；其次是获取和释放没有竞争的锁需要多长时间；再次是使用更小粒度或者
更加智能的锁。我假设我们经常使用锁：不然就没有必要关心效率问题了。

4.0.读\写类锁

spinlocks和semaphores都有对应的读写类锁：rwlock_t和struct rw_semaphore。这些锁将
用户划分为读者和作者。如果你只需要读取数据，那你就去获取一个读锁；如果你要写
入数据，你就需要写锁。

如果你的代码中有大量时间使用读锁，这样可以增加并发。但是他们消耗的时间要比普通锁要
多一些，所以如果使用不当的话，反而效果不好。实际操作时rwlock_t通常没有太大的
用处。

4.1.免锁算法

使用锁的代价很高，所以在可以不使用锁就能完成要求的情况下就不要使用锁。

4.1.0 免锁算法

某些情况下可以使用精心设计的无锁算法来保证数据的一致性

4.1.1 原子变量

内核提供了一些原子变量以及相关的操作，使得我们可以在只需要共享一个原子变量的情况下
可以不使用锁机制。

4.1.2 位操作

内核也提供一些原子的位操作

4.1.3 seqlock

seqlock允许读取这对资源的自由访问，但需要读取者检测是否和写入者冲突，如果冲突就需要
它重新读取数据。seqlock不能用于保护含有指针的数据结构。

4.1.4 RCU

RCU读取，将需要保护的数据放在RCU的lock和unlock之间。

RCU修改，分配一个新的数据结构，复制原来的数据结构到新的数据结构中，替换读取代码可以
看到的数据指针为新数据结构的指针。

5. 可以在中断中安全调用的函数

许多内核函数可能会直接或者间接休眠（例如调用schedule()）：千万不要在持有spinlock的
时候调用它们，也不要在禁用抢占之后调用它们。同时也意味着你需要在用户上下文中
调用它们，在中断中使用它们也是非法的。

5.0.常见的会休眠的函数

• 访问用户空间
  • copy_from_user()
  • copy_to_user()
  • getuser()
  • putuser()
• kmalloc(GFP_KERNEL)
• down_interruptible()和down()
• down_trylock()可以在中断上下文中使用

5.1.不会休眠的函数

• printk()
• kfree()
• add_tiemr() 以及 del_timer()

参考资料

• Linux Device Drivers
• Unreliable Guide To Locking