Jan Fan     About     Archive     Feed     English Blog

并发程序设计:杜绝共享变量(Shared Mutability)

并发计算,这是一个之前笔者很少接触的领域。所幸笔者的毕设涉及到了这方面的研究,让笔者对并发模型有了全新的了解。

这篇文章就跟大家分享如何写出更健壮、更简洁的并发程序。

并发计算,大势所趋

并发计算,即多个执行单元的计算同时进行。这篇文章不讨论在多台机器上的并发计算,那属于分布式计算(Distributed Computing)的范畴了,我们仅仅讨论在单个机器上(单核或多核)的并发计算。

Concurrency is a property of systems in which several computations are executing simultaneously, and potentially interacting with each other. The computations may be executing on multiple cores in the same chip, preemptively time-shared threads on the same processor, or physically separated processors.

并发计算在当下越来越受到重视,因为单个CPU的性能已经到达了瓶颈,程序性能的提高不能再指望CPU性能的提升了,免费的午餐已经没有了。 具体为什么摩尔定律(Moore’s Law)不再生效,并不是因为芯片时钟频率真的达到了极限,而是因为无法负担芯片频率进一步的提高所增加的额外能耗。从2004年开始,程序性能提升的重心已经从单纯地增强芯片转移到并发计算了。

moore law

即使不考虑芯片的能力,并发计算也能使人们更彻底地利用(压榨)机器的能力,同时也能使程序具有良好的交互和响应能力。

传统的并发程序设计:Shared Mutability 是万恶之源

国内传统计算机院校只单一地教授过程式编程(Procedural Programming)或者面向对象编程(Object-oriented Programming),学生只知道可以通过对“共享变量”(Shared Mutability)进行“同步”(synchronization)的那一套编程范式来设计并发程序,他们不知道其它的方法。

共享变量会带来一个非常棘手的问题——资源竞争(Race Condition),多个线程同时修改共享变量,其结果是不确定的。

// after execution, sum is expected to be 2, but try to guess?
int sum = 0;

// thread 1
sum++;

// thread 2
sum++;

对的,可以通过使用下面列出的这些同步工具(synchronization primitives)来保证对临界区(Critical Region)进行排外(Exclusively)的访问来解决资源竞争的问题。

但这些同步工具在解决问题的同时又带来了更多的问题:死锁(Deadlock)、饥饿(Starvation)、优先级反转(Priority inversion)等等。 即使是简单的问题,使用共享变量写出正确的并发逻辑也是困难的,可以参考 State: You’re Doing It Wrong中的一个简单例子,Banking,从对Critical Region的加锁、到转帐的原子操作、再到死锁,并发的隐藏错误层出不穷,很难去发现、推理和修正。

同步手段的蔽端远远不止眼前的这些问题。 它们与程序的主体业务逻辑没有关系,我们往往是使用单线程的线性逻辑写出了程序,然后再使用同步工具来保证程序在并发环境下的正确性。这些同步工具遍布在代码的各个角落,使得真正的主体代码难以被阅读、理解。

这些问题常常十分隐蔽,难以排查。最重要的原因是因为这些同步的手段缺乏可分解性(lack of composability),底层的同步过程无法被很好地隐藏起来,上层的同步过程需要考虑到整个程序中的所有锁(lock)。 这个例子很仔细地说明了锁的不可分解性。

因为同步工具的不可分解性,这在稍微大一点的项目中都将意味着人类所不能控制的复杂度。读者可以在 Learning from Mistakes — A Comprehensive Study on Real World Concurrency Bug Characteristics去看看在实际项目开发中基于共享变量的并发技术带来了多少的bug。

The problem is that we have chosen concurrent abstractions that do not even vaguely resemble the concurrency of the physical world. Non-trivial multi-threaded programs are incomprehensible to human …

lock

追溯错误的根源,都是因为共享变量(Shared Mutability)所带来的不确定性。 由于线程是由操作系统来调度的,导致执行单元的执行顺序是随机的、不可控制的,但对共享变量的访问需要有一定的限制,不然程序的正确性不能得到保证。

non-determinism = parallel processing + mutable state

面对更多更复杂的实际问题,我们需要另一种更正确的、能进一步减少并发模型中的不确定性的抽象模型来设计并发程序。

Software Transactional Memory (STM)

STM是一种非常类似数据库事务处理(transactions)的并发模型。 数据库在执行事务时,如果在提交(commit)的时候发现数据不一致,那么它将回滚(roll back),避免冲突。 STM也是如此,只不过因为程序执行过程中数据驻存于内存中,所以STM针对的数据不是在硬盘,而是在程序的内存。

STM在并发过程中,各个线程不共享原来的变量数据,而是各自拥有一份“副本”,使其无须竞争对共享数据的访问,彻底避免了race conditions的问题。

        ┌────────┐   ┌────────┐         
        │thread 1│   │thread 2│         
        └────────┘   └────────┘         
operate      │            │     operate 
             ▼            ▼             
        ┌─────────┐  ┌─────────┐        
        │dup data1│  │dup data2│        
        └─────────┘  └─────────┘        
             ▲            ▲             
             │            │             
       copy  │ ┌────────┐ │ copy        
             │ │original│ │             
             └─│  data  │─┘             
               └────────┘               

当各个线程完成对数据的操作之后,如果原数据在这段时期没有被改动,它们将以新的数据直接覆盖;如果有改动,则线程这段时期的操作失效,将回滚,复制最新的数据重新执行。

基于JVM的Clojure语言是STM模型的最佳典范。 Clojure的全部数据结构都是immutable的,并且数据结构的复制非常高效。 这对于STM机制是非常关键的。 否则STM的并发将因为需要创建数据副本而导致时间和空间上的大量开销,性能将不可接受。

Actor Model

近来相当火热的Erlang语言相信大家都有所耳闻,Erlang超大规模的并发能力就是基于Actor模型实现的。

Actor模型与传统的并发模型在思维方式上出入很大。 传统的并发模型是通过对共享变量的阻塞式访问来保证数据一致的,STM也没有脱离这个思维方式,只是数据的一致性由底层的事务来处理了,不需要程序员去担心。 但Actor模型是通过异步的多任务来完成任务的,因此在划分和设计问题的时候需要采取完全不同的思维方式。

举个例子,一个典型的Observer Pattern,假设两个老师站在黑板上统计全班同学的总人数,中间结果写在黑板上,老师每点到一个学生就去修改黑板上的总数,用C语言的Pthread并发库来模拟。

#include <pthread.h>

int sum_in_blackboard = 0;
pthread_mutex_t mutex1 = PTHREAD_MUTEX_INITIALIZER;

// teacher 1
...
pthread_mutex_lock( &mutex1 );
sum_in_blackboard++;
pthread_mutex_unlock( &mutex1 );
...

// teacher 2
...
pthread_mutex_lock( &mutex1 );
sum_in_blackboard++;
pthread_mutex_unlock( &mutex1 );
...

如何用异步的方式应该怎么设计?我们用Python的gevent并发库来模拟。

import gevent
from gevent.queue import Queue

count_quque = Queue()
students_total = 0

def blackboard():
    while not count_queue.empty():
        n = count_queue.get()
        students_total += n
        print('Erasing... Now total number of students is: %s' % students_total)
        gevent.sleep(0)

def teacher1(n):
    for i in xrange(1,n):
        count_queue.put_nowait(1)
        print('Teacher 1: so far I have counted %s students, where is the next one?’)

def teacher2(n):
    for i in xrange(1,n):
        count_queue.put_nowait(1)
        print('Teacher 2: so far I have counted %s students, where is the next one?’)

gevent.spawn(teacher1, 25).join()
gevent.spawn(teacher2, 25).join()

gevent.joinall([
    gevent.spawn(blackboard),
])

其中的差异在于,传统方法是通过对共享变量的读取和修改来协调各个线程的任务;而Actor模型需要把问题分解成多个单独执行的任务,相互之间通过传递消息来通信。

的确可能有朋友会指出,Actor模型的底下不也就是一个共享的队列么,哪有什么区别? 我会推荐这篇贴子。 当前的操作系统的并发机制都是基于多线程模型的,这个基层是充满不确定性的,我们能做的只是在其上搭建一个灵活而简明的“模式”,在这个模式的指导下写出尽可能确定的并发程序。 这篇论文对此作了很好的总结,推荐一看,它还介绍了一些替代现有多线程基层模型的具备确定性的并发理论,但笔者水平有限没有看懂。

最后

还有一些其它的方法也能帮助程序员写出更好的并发程序,比如静态代码分析(formal program analysis)、优化的软件设计流程(software engineering processes)。

这些先进的并发方法也有其各自的弊端,比如STM只适用于读取多而写入少的场景,并且对不可逆转的操作无效(如I/O),Actor模型在任务间存在大量通信的情况下也会引发低并发性。 但它们都无一例外地使得并发程序的开发变得更加简单明晰,高度抽象,less error-prone。

面对并发需求,我们要学着使用更锋利的武器。

主要参考资料

Comments

多说 Disqus