Linux内核中的并发和同步

vmlinz posted @ Tue, 25 Jan 2011 23:57:01 +0800 in Linux with tags kernel LDD linux , 3790 readers

作者: 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()

参考资料


Login *


loading captcha image...
(type the code from the image)
or Ctrl+Enter