为什么需要锁

当多个线程共享同一块内存区域时, 我们需要保证任何一个线程在访问这块内存时, 所看到的内容是稳定的. 如果所有的线程对这块内存的访问都只是读取, 那么我们就不需要采取额外措施. 但哪怕其中有一个线程会修改这块内存, 那我们就要对这些线程进行同步.之所以要这么做是因为修改内存的操作往往都不是原子操作, 而是分成多个时钟周期, 一个线程对内存的操作可能在任何一个周期被另一个线程打断, 从而导致这块内存的内容不稳定.所谓线程同步, 也就是说当好几个线程同时想要操作某块内存时, 它们必须按照顺序一个一个来, 只有上一个线程对这块内存操作完毕了, 下一个线程才能接着对这块内存进行操作.如何实现线程同步呢? 就是加锁.

对谁加锁

虽然我们都用过锁, 但有没有考虑过这个锁本质上是给谁加呢?显然, 是对这块内存加锁, 好让某个线程操作这块内存时, 其他线程进不来.

锁的本质

那么这把锁得是什么形式的呢? 既然要锁内存, 是不是在内存上有这么一个物理元器件? 不得不说, 这是一种方法, 但实际并不是这么实现的. 但是硬件层面确实要提供一种原子的访问内存的指令, 别急, 我们一步一步分析.

假设两个线程都要去操作内存 A, 我们现在仅从软件角度考虑, 如果要实现这把锁, 我们可以选择另一块内存 L 来标记是否能够操作 A, 也就是: 线程操作 A 前, 要先取出 L 的值, 如果是 1 的话就将其改成 0, 然后操作 A, 访问完 A 就再将 L 改成 1; 如果 L 是 0 的话, 就说明别的线程正在操作 A, 那我就等着直到别人释放.

你应该注意到了, L 既然也是一块内存, 那修改 L 不也是会分多个时钟周期吗? 线程一取 L 的值进寄存器, 发现是 1, 于是在寄存器上改为 0, 然后正准备要写回去, 结果线程二打断了它, 也取了 L 的值发现是 1, 于是后面不就又两个线程同时访问 A 内存了吗? 这锁不管用啊!

别急, 虽然都是内存, 但是对 L 和 A 的操作还真是不一样的, 我们会采取手段使得对 L 的操作是原子的. 其中最简单直接的手段就是 — 关闭时钟中断 (后面简称为关中断. 或者是挂起调度器, 效果类似), 这可是很不得了的事情, 一旦执行了这个操作, 其它的线程可就捞不着执行了, 这样对 L 的操作当然就不会被打断了, 当然改完 L 之后一定要开时钟中断 (后面简称为开中断) 恢复调度器的.

说到挂起调度器, 多解释一下. 我们知道处理器有很多中断, 其中时钟中断是源自晶振的非常规律的周期性中断, 操作系统内核为了能够支持多任务, 需要利用这一点在每个时钟中断到来之时, 切换 CPU 上下文, 执行另一个任务. 我们可以认为, 捕获时钟中断, 并执行任务切换工作的这段代码就是调度器, 而挂起调度器什么呢? 意味着时钟中断将成为一个摆设, 除了挂起调度器的那个任务, 所有其他任务都将再也得不到执行. 所以, 挂起调度器是一个影响巨大的操作, 负责挂起调度器的那个任务, 一定, 必须, 绝对要负责随后恢复调度器! 挂起调度器实际上是触及到了操作系统内核的工作, 不过还没有介入到处理器这一层, 时钟中断实际上还在不断的产生, ISR (中断处理函数) 也会被调用, 只是操作系统内核不再去处理了罢了. 比这更进一步的就是直接关闭时钟中断, 这样一来中断直接不再产生. 关于这块内容, 可以参考回顾 FreeRTOS 的源代码. 从应用程序层面看, 挂起调度器这个操作已经足够危险了, 所以在 Linux 这样的操作系统中, 应用程序是没有权限做这个事情的, 必须要通过系统调用委托内核去做才行.

我知道你可能会想, 既然还有关中断这一招, 那还折腾出个 L 干什么? 直接在访问 A 的时候就关中断, 访问完了 A 就再恢复中断不就行了吗?

这个是不行的, L 只是存个标记, 不到 1 个字节就够, A 这块内存大小是不一定的, 可能大到好几兆, 假设访问一个字节是 1us, 那么访问一兆字节我们不妨认为需要 10^6us = 1s. 如果每个线程访问 A 都要把可能原本也没有打算访问 A 的, 无辜躺枪的其它线程全都挂起 1s, 这就没有王法了.

为什么需要原子访存指令

然而, 即便我们只是在访问 1 字节的 L 时关中断, 这种方式仍旧是存在很多问题的, 尤其是在多核处理器的情况下还是无效的! 因为关中断对单个 CPU 关中断, 但是线程可以切换到另一个 CPU 上执行, 从而无视前一个 CPU 的关中断.

除此之外,关中断是权限极高的操作, 需要切换到 CPU 的特权模式进行, 这 linux 系统中这当然是要从用户态切换到内核态的; 另外关中断存在很大的风险, 就是关中断的线程死循环或者直接 crash 了, 这样其他线程就永远得不到执行了 — 除非重启机器; 再次, 关中断就意味着可能会丢失中断, 如果线程关中断时间太长, 会破坏线程调度机制, 这点上面我们已经看到了; 最后, 关中断这个操作效率上也是很低的.所以用关中断来实现锁是不可取的, 实际上只有操作系统在执行关键任务时才会使用关中断的手段, 而且会严格控制关闭时间.

既然又不能关中断, 我们又想原子访存, 那怎么办? 那就是需要硬件层面提供一种原子访存指令了.CPU 架构提供的原子访存指令典型的有如下这些, 这些指令也是实现所谓 “无锁编程” 的关键:

• Test-And-Set
• Compare-And-Swap
• Load-Linked and Store-Conditional
• Fetch-And-Add
• etc…

具体怎么用这些指令实现锁, 就是另一个话题了.

结语

Ok, 到此为止, 我们阐述了锁的本质, 实际上就是对一块内存进行原子访问, 而实现锁的这块内存, 它的名字就叫做 — 互斥量.

参考

1. 强烈推荐此书, 神作: http://pages.cs.wisc.edu/~remzi/OSTEP/ 第 28 章.
2. https://stackoverflow.com/questions/1485924/how-are-mutexes-implemented
3. https://en.wikipedia.org/wiki/Test-and-set
4. https://stackoverflow.com/questions/31978324/what-exactly-is-stdatomic

(首发于: 编程笔记)

cifer