Breuer P.T., Valls M.G. (2004) Static Deadlock Detection in the Linux Kernel. In: Llamosí A., Strohmeier A. (eds) Reliable Software Technologies - Ada-Europe 2004. Ada-Europe 2004. Lecture Notes in Computer Science, vol 3063. Springer, Berlin, Heidelberg
spinlock
和 mutex 一样用来控制对临界区的访问. 临界区可以看成一种共享资源, 共享的是代码, 任何时刻只能有一个线程访问这个资源.
线程试图进入锁上一个 spinlock 时, 要是 spinlock 已经被锁上, 那么线程在这里循环, 一直尝试锁上 spinlock. 直到时间片耗尽才被换出, 解锁不会唤醒线程.
属于忙等策略, 常用于对小的临界区的保护.
通常使用特殊指令实现, 如 lock cmpxchg (x86), ll; sc (mips).
spinlock 和单核机器
在单核机器上使用 spinlock 通常没有意义, 因为除非等待 spinlock 的线程被换出, 否则永远不会有其他线程来解锁这个 spinlock, 使得等待 spinlock 的线程继续进行.
然而如果我们允许内核中的抢占 (kernel 2.6.x 开始), 那么 单核机器上面的 spinlock 还是有意义的. 详情参见 kernel newbie 那篇 faq.
事实上, 上面说的 “单核” 的意思是, 只有一个对象能够访问这个锁. 广义的考虑, 如果访问锁的除了正在执行的程序 (i.e. 当前线程), 还能有外部设备, 那么单核机器上的 spinlock 也是有意义的.
一个例子就是串口忙等. 在我们的环境中, 串口两根线 (除去时钟) 是 busy 和 data. 只有在 busy 是 0 的时候, 我们才能给串口 data 写数据.
mips 上的 ucore 使用的是忙等, 代码如下
1
2
3
4
5
static void
serial_putc_sub(int c) {
while( (inw(COM1 + 0x04) & 0x01) == 0 );
outw(COM1 + 0x00, c & 0xFF);
}
而 recc, 以及 minikernel 使用的是类似 mutex 的, 造成串口打印速度明显很慢.
spinlock 造成的 bug
主要就是 spin-and-sleep 情况的发生. (似乎隔壁实验室最近有人做过这个, 同行评价还不错, 不过他讲的时候我睡着了, 没听清他做的和 04 年那篇的文章有什么区别. OTZ)
spin-and-sleep 情况就是 (主要是内核当中),
线程在被 spinlock 保护的区域中执行的时候被调出,
或者说是持有 spinlock 的线程被调出的情况.
这种情况主要是由于 spinlock 保护的代码直接或者间接地调用了 sleep() 导致的.
考虑这样的情况下, 其他线程, 无论是在其他核上面运行还是同一个核上被调入的线程, 如果尝试进入这段被 spinlock 保护的区域, 这些线程就会不停地忙转.
如果运气好, 之后某一个时间, 这个持有锁的线程被调入, 那么待它执行完成后这个锁被释放, 一切安好.
但是如果持有锁的线程长时间没被调入, 而又有其他线程试图进入被保护的区域, 那么会导致大量 CPU 空转.
进一步地, 如果不允许 kernel preemption, 那么就会造成某些 CPU 的完全不可用, 就是说出死锁了.
详细的可以参考 Static Deadlock Detection in the Linux Kernel 一文.
mutex
和 spinlock 一样用来控制对临界区的访问.
mutex 可以用来实现 sem.
线程试图进入锁上一个 mutex 时, 要是 mutex 已经被锁上, 那么线程被换出, 当 mutex 被解锁时才被唤醒.
需要线程切换, 所以用于较大的临界区的保护.
spinlock 和 mutex 功能是一样的, 区别只在于加锁失败时, 是忙等还是被换出. 现代操作系统中通常有混合方式, 即先 spin 一段时间, 要是这段时间内线程没有得到锁, 那么被换出.
semaphore
sem 用来控制对共享资源的访问.
sem 可以用来实现 mutex, 但是不能用来实现忙等的 spinlock.
线程试图 down 一个 sem 时, 要是 sem 已经是 0, 那么线程被换出, 当另外线程 up 这个 sem 时被唤醒.
单核系统中, 在 up 和 down 中关中断; 多核系统必须硬件支持.
recursive lock
亦称 recursive mutex.
概念
- 普通 mutex: 一个线程锁上之后, 它成为这个锁的 owner. 其他线程就不能获取这个锁了, 必须等待 owner 释放这个锁. (上锁/解锁和获取/释放是同一件事情的两套说法)
就算是 owner, 如果它尝试再次获取这个锁, 那也不行. 而且要是它尝试这么做, 显然会产生一個死锁.
- recursive mutex: owner 可以在持有锁的情况下再次再次获取锁. 而且, 如果 owner 上锁了 \( n\) 次, 只有他解锁 \(n \) 次之后, 它才真正释放这个锁, 这个锁才能被其他线程获取.
和 semaphore 的比较
大致可以说, recursive lock 和 semaphore 是相反的两个事物. 它们都可以用一个 (操作都是原子的) 整数 \( l\) 表示.
| 上锁 | 解锁 | 什么时候锁是锁上的 | 通常情况下的初始值 | |
|---|---|---|---|---|
| semaphore | \( l = l - 1\) | \( l = l + 1\) | \( l > 0\) | \( l > 0 \) 表示资源的个数 |
| recursive lock | \( l = l + 1\) | \( l = l - 1\) | \( l = 0 \) | \( l = 0\) |
争议
Java 中的 synchronize 就是 recursive lock.
Linux kernel 中的锁都不是 recursive.
mutex 应不应该是 recursive 的争议很多.
支持的一派认为, 这样简化编程, 不容易出现死锁.
反对的一派认为, 非递归的锁使得你写了垃圾代码之后, 系统能够死锁来提示你写了垃圾代码. 而不是放任垃圾代码, 可能造成更大的危害.
反对的一派说, mutex 是用来保护 invariant (不变量) 的. 进入 mutex 临界区之前, 某个 invariant 成立, 临界区里面可能它不成立, 但是离开临界区后 invariant 继续成立. 递归的锁不能保证这一点.
支持的一派说, mutex 当然是用来保护全局数据共享的. 只要一个时刻只有一个线程访问共享数据就行了. recursive 完成了这一点.
当然, 对于这个冷门问题, 我并没有什么想法, 选择旁观.