Linux 同步方法剖析

FROM :http://www.ibm.com/developerworks/cn/linux/l-linux-synchronization.html (这里面还有一些没讲到,2.6同步机制包括:per-cpu variables, atomic operation, memory barrier, spin lock,semaphore, seqlocks, local interrupt disabling, local softirq disable, read-copy-update。详见ULK3)

Linux 同步方法剖析

M. Tim Jones 是一名嵌入式软件工程师,他是 GNU/Linux Application Programming、AI
Application Programming 以及 BSD Sockets Programming from a Multilanguage
Perspective 等书的作者。他的工程背景非常广泛,从同步宇宙飞船的内核开发到嵌入式
架构设计,再到网络协议的开发。Tim 是位于科罗拉多州 Longmont 的 Emulex Corp. 的
一名顾问工程师。
简介: 在学习 Linux® 的过程中,您也许接触过并发(concurrency)、临界段(
critical section)和锁定,但是如何在内核中使用这些概念呢?本文讨论了 2.6 版内核
中可用的锁定机制,包括原子运算符(atomic operator)、自旋锁(spinlock)、读/写
锁(reader/writer lock)和内核信号量(kernel semaphore)。本文还探讨了每种机制
最适合应用到哪些地方,以构建安全高效的内核代码。
发布日期: 2007 年 11 月 19 日
本文讨论了 Linux 内核中可用的大量同步或锁定机制。这些机制为 2.6.23 版内核的许多
可用方法提供了应用程序接口(API)。但是在深入学习 API 之前,首先需要明白将要解
决的问题。

并发和锁定

当存在并发特性时,必须使用同步方法。当在同一时间段出现两个或更多进程并且这些进
程彼此交互(例如,共享相同的资源)时,就存在并发现象。
在单处理器(uniprocessor,UP)主机上可能发生并发,在这种主机中多个线程共享同一
个 CPU 并且抢占(preemption)创建竞态条件。抢占通过临时中断一个线程以执行另一个
线程的方式来实现 CPU 共享。竞态条件发生在两个或更多线程操纵一个共享数据项时,其
结果取决于执行的时间。在多处理器(MP)计算机中也存在并发,其中每个处理器中共享
相同数据的线程同时执行。注意在 MP 情况下存在真正的并行(parallelism),因为线程
是同时执行的。而在 UP 情形中,并行是通过抢占创建的。两种模式中实现并发都较为困
难。
Linux 内核在两种模式中都支持并发。内核本身是动态的,而且有许多创建竞态条件的方
法。Linux 内核也支持多处理(multiprocessing),称为对称多处理(SMP)。可以在本
文后面的参考资料部分学到更多关于 SMP 的知识。
临界段概念是为解决竞态条件问题而产生的。一个临界段是一段不允许多路访问的受保护
的代码。这段代码可以操纵共享数据或共享服务(例如硬件外围设备)。临界段操作时坚
持互斥锁(mutual exclusion)原则(当一个线程处于临界段中时,其他所有线程都不能
进入临界段)。
临界段中需要解决的一个问题是死锁条件。考虑两个独立的临界段,各自保护不同的资源
。每个资源拥有一个锁,在本例中称为 A 和 B。假设有两个线程需要访问这些资源,线程
X 获取了锁 A,线程 Y 获取了锁 B。当这些锁都被持有时,每个线程都试图占有其他线程
当前持有的锁(线程 X 想要锁 B,线程 Y 想要锁 A)。这时候线程就被死锁了,因为它
们都持有一个锁而且还想要其他锁。一个简单的解决方案就是总是按相同次序获取锁,从
而使其中一个线程得以完成。还需要其他解决方案检测这种情形。表 1 定义了此处用到的
一些重要的并发术语。
表 1. 并发中的重要定义
术语                定义
竞态 两个或更多线程同时操作资源时将会导
条件 致不一致的结果。
临界 用于协调对共享资源的访问的代码段。
互斥 确保对共享资源进行排他访问的软件特
锁  性。
死锁 由两个或更多进程和资源锁导致的一种
特殊情形,将会降低进程的工作效率。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Linux 同步方法

如果您了解了一些基本理论并且明白了需要解决的问题,接下来将学习 Linux 支持并发和
互斥锁的各种方法。在以前,互斥锁是通过禁用中断来提供的,但是这种形式的锁定效率
比较低(现在在内核中仍然存在这种用法)。这种方法也不能进行扩展,而且不能保证其
他处理器上的互斥锁。
在以下关于锁定机制的讨论中,我们首先看一下原子运算符,它可以保护简单变量(计数
器和位掩码(bitmask))。然后介绍简单的自旋锁和读/写锁,它们构成了一个 SMP 架构
的忙等待锁(busy-wait lock)覆盖。最后,我们讨论构建在原子 API 上的内核互斥锁。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
回页首
原子操作
Linux 中最简单的同步方法就是原子操作。原子意味着临界段被包含在 API 函数中。不需
要额外的锁定,因为 API 函数已经包含了锁定。由于 C 不能实现原子操作,因此 Linux
依靠底层架构来提供这项功能。各种底层架构存在很大差异,因此原子函数的实现方法也
各不相同。一些方法完全通过汇编语言来实现,而另一些方法依靠 c 语言并且使用
local_irq_save 和 local_irq_restore 禁用中断。
旧的锁定方法
在内核中实现锁定的一种不太好的方法是通过禁用本地 CPU 的硬中断。这些函数均可用并
且仍得到使用(有时用于原子运算符),但我们并不推荐使用。local_irq_save 例程禁用
中断,而 local_irq_restore 恢复以前启用过的中断。这些例程都是可重入的(
reentrant),也就是说它们可以在其他例程上下文中被调用。
当需要保护的数据非常简单时,例如一个计数器,原子运算符是种理想的方法。尽管原理
简单,原子 API 提供了许多针对不同情形的运算符。下面是一个使用此 API 的示例。
要声明一个原子变量(atomic variable),首先声明一个 atomic_t 类型的变量。这个结
构包含了单个 int 元素。接下来,需确保您的原子变量使用 ATOMIC_INIT 符号常量进行
了初始化。在清单 1 的情形中,原子计数器被设置为 0。也可以使用 atomic_set
function 在运行时对原子变量进行初始化。
清单 1. 创建和初始化原子变量
atomic_t my_counter ATOMIC_INIT(0);
… or …
atomic_set( &my_counter, 0 );
原子 API 支持一个涵盖许多用例的富函数集。可以使用 atomic_read 读取原子变量中的
内容,也可以使用 atomic_add 为一个变量添加指定值。最常用的操作是使用 atomic_inc
使变量递增。也可用减号运算符,它的作用与相加和递增操作相反。清单 2. 演示了这些
函数。
清单 2. 简单的算术原子函数
val = atomic_read( &my_counter );
atomic_add( 1, &my_counter );
atomic_inc( &my_counter );
atomic_sub( 1, &my_counter );
atomic_dec( &my_counter );
该 API 也支持许多其他常用用例,包括 operate-and-test 例程。这些例程允许对原子变
量进行操纵和测试(作为一个原子操作来执行)。一个叫做 atomic_add_negative 的特殊
函数被添加到原子变量中,然后当结果值为负数时返回真(true)。这被内核中一些依赖
于架构的信号量函数使用。
许多函数都不返回变量的值,但两个函数除外。它们会返回结果值( atomic_add_return
和 atomic_sub_return),如清单 3所示。
清单 3. Operate-and-test 原子函数
if (atomic_sub_and_test( 1, &my_counter )) {
// my_counter is zero
}
if (atomic_dec_and_test( &my_counter )) {
// my_counter is zero
}
if (atomic_inc_and_test( &my_counter )) {
// my_counter is zero
}
if (atomic_add_negative( 1, &my_counter )) {
// my_counter is less than zero
}
val = atomic_add_return( 1, &my_counter ));
val = atomic_sub_return( 1, &my_counter ));
如果您的架构支持 64 位长类型(BITS_PER_LONG 是 64 的),那么可以使用 long_t
atomic 操作。可以在 linux/include/asm-generic/atomic.h 中查看可用的长操作(long
operation)。
原子 API 还支持位掩码(bitmask)操作。跟前面提到的算术操作不一样,它只包含设置
和清除操作。许多驱动程序使用这些原子操作,特别是 SCSI。位掩码原子操作的使用跟算
术操作存在细微的差别,因为其中只有两个可用的操作(设置掩码和清除掩码)。使用这
些操作前,需要提供一个值和将要进行操作的位掩码,如清单 4 所示。
清单 4. 位掩码原子函数
unsigned long my_bitmask;
atomic_clear_mask( 0, &my_bitmask );
atomic_set_mask( (1<<24), &my_bitmask );
原子 API 原型
原子操作依赖于架构,可以在 ./linux/include/asm-<arch>/atomic.h 中找到。
自旋锁
自旋锁是使用忙等待锁来确保互斥锁的一种特殊方法。如果锁可用,则获取锁,执行互斥
锁动作,然后释放锁。如果锁不可用,线程将忙等待该锁,直到其可用为止。忙等待看起
来效率低下,但它实际上比将线程休眠然后当锁可用时将其唤醒要快得多。
自旋锁只在 SMP 系统中才有用,但是因为您的代码最终将会在 SMP 系统上运行,将它们
添加到 UP 系统是个明智的做法。
自旋锁有两种可用的形式:完全锁(full lock)和读写锁。首先看一下完全锁。
首先通过一个简单的声明创建一个新的自旋锁。这可以通过调用 spin_lock_init 进行初
始化。清单 5 中显示的每个变量都会实现相同的结果。
清单 5. 创建和初始化自旋锁
spinlock_t my_spinlock = SPIN_LOCK_UNLOCKED;
… or …
DEFINE_SPINLOCK( my_spinlock );
… or …
spin_lock_init( &my_spinlock );
定义了自旋锁之后,就可以使用大量的锁定变量了。每个变量用于不同的上下文。
清单 6 中显示了 spin_lock 和 spin_unlock 变量。这是一个最简单的变量,它不会执行
中断禁用,但是包含全部的内存壁垒(memory barrier)。这个变量假定中断处理程序和
该锁之间没有交互。
清单 6. 自旋锁 lock 和 unlock 函数
spin_lock( &my_spinlock );
// critical section
spin_unlock( &my_spinlock );
接下来是 irqsave 和 irqrestore 对,如清单 7 所示。spin_lock_irqsave 函数需要自
旋锁,并且在本地处理器(在 SMP 情形中)上禁用中断。spin_unlock_irqrestore 函数
释放自旋锁,并且(通过 flags 参数)恢复中断。
清单 7. 自旋锁变量,其中禁用了本地 CPU 中断
spin_lock_irqsave( &my_spinlock, flags );
// critical section
spin_unlock_irqrestore( &my_spinlock, flags );
spin_lock_irqsave/spin_unlock_irqrestore 的一个不太安全的变体是 spin_lock_irq/
spin_unlock_irq。我建议不要使用此变体,因为它会假设中断状态。
最后,如果内核线程通过 bottom half 方式共享数据,那么可以使用自旋锁的另一个变体
。bottom half 方法可以将设备驱动程序中的工作延迟到中断处理后执行。这种自旋锁禁
用了本地 CPU 上的软中断。这可以阻止 softirq、tasklet 和 bottom half 在本地 CPU
上运行。这个变体如清单 8 所示。
清单 8. 自旋锁函数实现 bottom-half 交互
spin_lock_bh( &my_spinlock );
// critical section
spin_unlock_bh( &my_spinlock );
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
回页首
读/写锁
在许多情形下,对数据的访问是由大量的读和少量的写操作来完成的(读取数据比写入数
据更常见)。读/写锁的创建就是为了支持这种模型。这个模型有趣的地方在于允许多个线
程同时访问相同数据,但同一时刻只允许一个线程写入数据。如果执行写操作的线程持有
此锁,则临界段不能由其他线程读取。如果一个执行读操作的线程持有此锁,那么多个读
线程都可以进入临界段。清单 9 演示了这个模型。
清单 9. 读/写自旋锁函数
rwlock_t my_rwlock;
rwlock_init( &my_rwlock );
write_lock( &my_rwlock );
// critical section — can read and write
write_unlock( &my_rwlock );
read_lock( &my_rwlock );
// critical section — can read only
read_unlock( &my_rwlock );
根据对锁的需求,还针对 bottom half 和中断请求(IRQ)对读/写自旋锁进行了修改。显
然,如果您使用的是原版的读/写锁,那么按照标准自旋锁的用法使用这个自旋锁,而不区
分读线程和写线程。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
回页首
内核互斥锁
在内核中可以使用互斥锁来实现信号量行为。内核互斥锁是在原子 API 之上实现的,但这
对于内核用户是不可见的。互斥锁很简单,但是有一些规则必须牢记。同一时间只能有一
个任务持有互斥锁,而且只有这个任务可以对互斥锁进行解锁。互斥锁不能进行递归锁定
或解锁,并且互斥锁可能不能用于交互上下文。但是互斥锁比当前的内核信号量选项更快
,并且更加紧凑,因此如果它们满足您的需求,那么它们将是您明智的选择。
可以通过 DEFINE_MUTEX 宏使用一个操作创建和初始化互斥锁。这将创建一个新的互斥锁
并初始化其结构。可以在 ./linux/include/linux/mutex.h 中查看该实现。
DEFINE_MUTEX( my_mutex );
互斥锁 API 提供了 5 个函数:其中 3 个用于锁定,一个用于解锁,另一个用于测试互斥
锁。首先看一下锁定函数。在需要立即锁定以及希望在互斥锁不可用时掌握控制的情形下
,可以使用第一个函数 mutex_trylock。该函数如清单 10 所示。
清单 10. 尝试使用 mutex_trylock 获得互斥锁
ret = mutex_trylock( &my_mutex );
if (ret != 0) {
// Got the lock!
} else {
// Did not get the lock
}
如果想等待这个锁,可以调用 mutex_lock。这个调用在互斥锁可用时返回,否则,在互斥
锁锁可用之前它将休眠。无论在哪种情形中,当控制被返回时,调用者将持有互斥锁。最
后,当调用者休眠时使用 mutex_lock_interruptible。在这种情况下,该函数可能返回
-EINTR。清单 11 中显示了这两种调用。
清单 11. 锁定一个可能处于休眠状态的互斥锁
mutex_lock( &my_mutex );
// Lock is now held by the caller.
if (mutex_lock_interruptible( &my_mutex ) != 0)  {
// Interrupted by a signal, no mutex held
}
当一个互斥锁被锁定后,它必须被解锁。这是由 mutex_unlock 函数来完成的。这个函数
不能从中断上下文调用。最后,可以通过调用 mutex_is_locked 检查互斥锁的状态。这个
调用实际上编译成一个内联函数。如果互斥锁被持有(锁定),那么就会返回 1;否则,
返回 0。清单 12 演示了这些函数。
清单 12. 用 mutex_is_locked 测试互斥锁锁
mutex_unlock( &my_mutex );
if (mutex_is_locked( &my_mutex ) == 0) {
// Mutex is unlocked
}
互斥锁 API 存在着自身的局限性,因为它是基于原子 API 的。但是其效率比较高,如果
能满足你的需要,还是可以使用的。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
回页首
大内核锁(Big kernel lock)
最后看一下大内核锁(BLK)。它在内核中的用途越来越小,但是仍然有一些保留下来的用
法。BKL 使多处理器 Linux 成为可能,但是细粒度(finer-grained)锁正在慢慢取代
BKL。BKL 通过 lock_kernel 和 unlock_kernel 函数提供。要获得更多信息,请查看 ./
linux/lib/kernel_lock.c。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━
回页首
结束语
*
Linux 性能非凡,其锁定方法也一样。原子锁不仅提供了一种锁定机制,同时也提供了算
术或 bitwise 操作。自旋锁提供了一种锁定机制(主要应用于 SMP),而且读/写自旋锁
允许多个读线程且仅有一个写线程获得给定的锁。最后,互斥锁是一种新的锁定机制,提
供了一种构建在原子之上的简单 API。不管你需要什么,Linux 都会提供一种锁定方案保
护您的数据。
━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━━

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.