基于锁与共享状态的并发

基于锁与共享状态的并发

命令式编程源于 Von Neumann 架构,作为目前主流的结构化编程范式之一,其主要基于顺序执行的概念与共享的状态。而 Threads 被认为是这种编程范式在保证多个同步控制流上地有效扩展,类似于重量级的 Processes,Threads 是由操作系统与硬件架构级别提供地并行实现地元素之一。众所周知,在大部分的编程语言中线程都是最流行的用于实现并发的构建块,不过基于线程、锁与共享状态的并发模型无论在实现的便捷性与容错性上都存在着很大的问题。

The Implications of Shared and Mutable State | 共享的可变状态

从概念来看,一个线程定义了控制流的顺序执行序列。而不同于进程的是,线程往往会共享相同的内存地址空间,也就意味着多个独立的线程也可以并发访问相同的变量与状态。同时,顺序编程也是构建于可变状态的基础上,而导致了可能有多个线程争抢对于某个变量的写操作权限。此时多线程之间往往会采取优先权方式进行调度,也就是说,我们并不能提前知道多个线程之间何时发生上下文切换与交叉执行,从而使得程序充满了不确定性,最终导致极大的风险会出现 Race Conditions(竞态条件)。

当两个或者更多的线程竞争某个包含多个线程之间共享状态的临界区域的访问权时,也就称出现了 Race Condition。鉴于可能出现的交叉执行,Race Condition 会导致许多的线程不一致的状态出现。譬如某个线程读取到的某个值可能已经被其他线程更新了,而如果多个线程同时竞争修改某个变量状态时,可能只有一个最终的修改会保留下来而其他所有的修改都被丢弃。综上所述,我们需要一种机制来保证关键共享区域的安全并且强制性保证同步的访问。

Locking Mechanism | 锁原理

锁是同步中最常用的执行单元,可以用于控制对于临界区域的访问次序。我们常用的锁根据其语义与行为特征又可以分为好几个类别,Semaphores 就是一种简单的锁实现,其提供了 wait 与 signal 两个函数,来同步多个线程之间的访问次序。当某个线程需要访问临界区域时,其都需要调用wait函数。而系统在遍历临界区域并且发现该区域处于空闲状态时,会调用 signal 函数。

Semaphore 锁会通过在 wait 函数中阻塞其他线程而保障多线程情况下仅有一个线程可以获得允许访问临界区。Semaphore 的一个相对复杂的实现就是 Counting Semaphores,其允许指定数目的线程访问临界资源区。从这个角度看,上面讲的二元的 Semaphore 可以认为是被限定为同时只允许单线程访问的 Counting Semaphores 的一个特例。不同线程之间的互斥访问也提供了所谓所有权的概念,即是当临界区域在某时刻仅被单个线程访问时,我们认为该线程对临界区域具有所有权,也是唯一有权将临界区域解锁的线程。

另一个更高级点的互斥锁模型即是 Monitor,利用条件变量来保证对于临界区的互斥访问。Monitor 对于临界区域是以对象、方法或者函数为粒度进行切割,某个线程会根据内置的条件变量来判断是否要进入阻塞,然后等待其他线程触发的该条件变量的变化来进行其他操作。而对于锁还有一个重要的特性就是锁的可重入性。当某个锁支持可重入时,已经获取到某个锁通行证的线程可以畅通无阻的通过该锁。这个属性对于编写递归函数很有帮助,在递归函数中往往需要重复多次访问临界区域。其他的还有譬如 Read/Write Locks,可以允许所有的读线程之间共享访问权限,而排斥所有写线程。

Consequences of Locking | 锁的影响

Locks 允许我们重新编排所有对于临界区域的访问,互斥机制也能保证多线程情况下对于某个临界区域的操作的原子性。程序员在开发过程中只需要指明哪些代码块可能引发竞态情况,小心地设置访问锁以强制保证线性顺序访问即可。不过,对于锁概念的引入也可能导致另一些危险情况,譬如当线程活得到锁之后即不再释放或者线程一直在等待某个永远无法获取的锁的时候,整个应用可能就被这些不恰当的锁破坏掉。最著名的因为不恰当使用锁而导致程序崩溃的情况即是死锁,当两个或更多有循环依赖的线程竞争获取某个锁权限时,每个线程都占据了其他线程等待的锁。以双线程为例,每个线程都已经占据了一个锁,但是都在等待获取另一个线程拥有的锁,这就陷入了一个尴尬的境地,以至于两个线程都被阻塞而无法前进。

另外的常见的锁的问题还有活锁与饥饿,类似于死锁,活锁也会导致线程无法继续执行。不过活锁情况下,它们并不是处于阻塞状态,而是不断地对其他线程的锁请求予以响应,譬如让渡出自己的锁权限,这样每个线程一方面不断地获得新的锁权限,另一方面又不断让渡出锁权限,最终导致自己处于一种动态平衡地情形下。同样是在双线程情况下,每个线程都在等待获取两个资源才能继续操作,当它们无法获取到某个资源时就会让渡出已经获取到的资源并且稍后再重新请求。而当它们几乎同步地请求某个资源时,活锁就产生了。活锁可以被认为是饥饿地一种特殊情况,即某个线程因为其他线程不断地抢占资源或锁而导致自己一直无法获取某个资源或者锁的情况。

尽管很多地譬如活锁这样的饥饿情况可以通过动态设置重试时间进行避免,然而因为整个程序的不确定性潜在的锁的问题还是非常难于侦测。特别是在细粒度的锁控制的情况下死锁产生的概率也会大幅增加。此时我们也可以选择通过使用粗粒度的锁来避免死锁,不过这样只能对于临界区域保证最终一致性,与我们的初衷就相违背了。对于具有硬件并行支持的并发实现,我们需要选择合适的锁粒度来保证不同的线程能够尽可能地并行执行。不过这样过多的细小的临界区域的设置不仅会增加锁管理的复杂度,消耗额外的需要用于管理锁的资源,还会增加出现上述提到的各种潜在的锁问题的概率。选择合适的临界区域的粒度可不是件容易事。 另一方面,除了上文介绍的死锁、活锁以及饥饿这几种情况,在真正的编程实践中对于锁的应用还会面临如下的挑战。当我们需要为项目集成进某个大的模块或者组件时,我们并不能保证在我们自己已经使用了线程安全模型地情况下,这些第三方模块就不会产生锁的问题。我们习惯地去使用严格的编程规范去准则去尽可能避免出现锁的问题,但是这些准则并不能通过程序的方式强行检测,而更多依赖于程序员的个人素养。虽然基于线程、共享状态与锁的并发模型存在着很多本质上的问题,但是其以其简单易用性还是在大部分的编程语言中占据了主导地位,理解该模型会非常有助于我们理解关于并发实现的底层概念。

Case Study | Java 中的并发编程

Java 语言从诞生之初就提供了基于线程的并发机制,它使用 Mesa Monitor 作为锁与互斥模型的具体实现,并且提供了多种同步的手段。Java 中的一致性主要是基于 Happens-Before 顺序以及潜在的内存栅栏。不过 Java 并没有提供真正的顺序一致性的保证,JMM 类似于对称多处理模型,每个 CPU 共享统一的主存然后都拥有自己的独立的缓存。在 CPU 访问主存之后,它们会刷新自己的缓存并且最终同步修改。而 Java 的线程就跟这 CPU 一样,每个线程都共享有统一的主存然后对数据在线程内部有一份自己的副本。

多线程与锁模型的实践

public class CountingRequestHandler extends AbstractHandler {
//Variable for counting requests handled so far
private long count = 0;
public void handle(String target, Request baseRequest,
HttpServletRequest request, HttpServletResponse response)
throws IOException, ServletException {
response.setContentType("text/plain");
response.setStatus(200);
baseRequest.setHandled(true);
final long current;
//Access and modification of a variable shared between threads.
synchronized (this) {
current = ++count;
}
response.getWriter().println("" + current);
}
public static void main(String[] args) throws Exception {
Server server = new Server(8080);
server.setHandler(new CountingRequestHandler());
server.start();
server.join();
}
}