concurrency-1.md

Modern Haskell - Concurrency

dedication

When the limestone of imperative programming has worn away, the granite of functional programming will be revealed underneath -- Simon Peyton Jones

前言

虽然 Haskell 拥有丰富而成熟的并发特性，但在平时交谈时这些特性似乎很少被提到。因此我想通过 Concurrency 系列文章从用户角度科普一下 Haskell 的并发编程的特性 (先从 User-level concurrency primitives 讲起)。本文将默认读者对 Haskell 和并发编程有基本的了解。

Haskell (GHC) 提供的基础并发抽象是 lightweight threads (aka. green threads/绿色线程), 与 OS threads 相比占用的内存少很多 (能轻松生成百万个 lightweight thread)，而且 context switching 的 overhead 更小，同时比 Async callback 更方便使用。

side note: Haskell 与并发相关的 module 一般都在 Control.Concurrent 下

Basic Threading

最基础的并发操作就是 forking。 Haskell 提供了 forkIO 用于生成新的 thread：

forkIO :: IO () -> IO ThreadId

forkIO 接受一个返回 () (Unit type) 的 IO 操作，生成一个新的 thread 执行这个 IO 操作，并返回这个新生成 thread 的 unique identifier - ThreadId. ThreadId 可被用来杀死 thread:

killThread :: ThreadId -> IO ()

注意只要主 thread 退出，即使有其他 thread 在运行程序也会退出。

Basic Synchronization - MVar

我们接下来介绍最基础的线程间通信和同步的方式 - MVar. MVar 可被想象成一个可以空 (即有两种状态）的可变 (mutable) 盒子，它的 API 定义如下:

data MVar a  -- 忽略实现细节

newEmptyMVar :: IO (MVar a)
newMVar :: a -> IO (MVar a)
takeMVar :: MVar a -> IO a
putMVar :: MVar a -> a -> IO ()

newEmptyMVar 返回一个初始状态为空的 MVar，newMVar 在给定一个 x 后返回一个装有 x 的 MVar. takeMVar 将 MVar a 中所装有的值取出, 若 MVar 处于空的状态则会阻塞直到有东西被放进去，putMVar 将一个值放进 MVar 中，对称的，若 MVar 中已装有东西则会阻塞直到其中的值被取出。

Fairness

MVar 保证公平性，即如果一个 thread 因为 takeMVar 阻塞，同时有其他 thread 持续的往这个 MVar 中放东西，则这个 thread 一定会在有限时间内 unblock。 事实上所有阻塞在某个 MVar 上的线程都处在一个和这个 MVar 相关的 FIFO 队列中。

Software Transactional Memory

MVar 本质上就是一个 mutable reference + lock, 因此也有很多问题，比如锁的粒度细了容易死锁，锁的粒度粗了影响性能，无法使原子性的操作组合后仍保留原子性等等。

Software Transaction Memory (STM) 是一种支持 transaction 的共享内存。其 API 定义如下：

data STM a             -- STM a 代表一个返回值为 a 的 transaction
instance Monad STM     -- STM 是 Monad, 因此可以组合
instance MonadPlus STM -- STM 支持 selection

data TVar a            -- transactional variable

newTVar :: a -> STM (TVar a)       -- 生成一个 TVar
readTVar :: TVar a -> STM a        -- 读取 TVar
writeTVar :: TVar a -> a -> STM () -- 写入 TVar
retry :: STM a                     -- 等于 empty/mzero
orElse :: STM a -> STM a -> STM a  -- 等于 <|>/mplus

-- exception 先不考虑
throwSTM :: Excpetion e => e -> STM
catchSTM :: Exception e => STM a -> (e -> STM a) -> STM a

atomically :: STM a -> IO a  -- runs a transaction atomically

可以看到 STM 的原子性是可组合的 -- 可以像组合其他 Monad 一样组合 STM, 最后用 atomically 原子性地运行这个 transaction. 如果 transaction 产生了冲突 (transaction 前后 transaction 中用到的 TVar 有被修改过)，则整个 transaction 会被 rollback 并重新执行。Haskell 的 purity 保证了不会有 IO 在 transaction 中被执行，从而可以完全被 rollback，如果用的是其他不纯的语言则无法在编译期区别是否有 IO 出现，从而导致 rollback 后 IO 被执行多遍。(FYI 另一个实现 STM 的语言 clojure 通过在运行期会检查在 transaction 是否包含 IO，若有 IO 则会抛出异常的方式避免了 IO 重复多遍，但这显然不如在编译期就决定更好)

注意 TVar 不像 MVar 一样有公平性保证。

阻塞

阻塞在并发编程中是很自然的一件事，我们经常需要等待某些条件被满足之后才能继续执行程序。Haskell 的 STM 提供了在 transaction 中阻塞的办法：

retry :: STM a

retry 的意思为放弃当前的 transaction 并重试，当然这不会立即导致重试，因为如果 TVar 都没有改变的话重试一定会再次触发这个 retry (STM 中无法进行 IO, 因此 transaction 是 deterministic 的)。因此 runtime 会 block 这个 thread 直到 transaction 中用到的 TVar 被其他 thread 改变 (并不会检查值是否改变，只要 writeTVar 了就算) 后才会 unblock thread 并重试 transaction。

注意如果有很多的 transaction 都阻塞在某个 TVar 上，那么每次改变这个 TVar 时都会触发很多的 retry, 从而导致性能问题，这也是 OCC 的一个缺点。

总结

STM 提供了可组合的原子性与无锁方便的同步和线程间通信方式，能减少程序死锁的可能, 并已被广泛的应用于 Haskell 程序中。

next up

以后的文章中我们将介绍 Haskell 中的异常, specifically asynchronous exceptions, 并用这些 concurrency primmitives 来构建一些常见的 concurrency construct, 如 TMVar (底层使用 TVar 的 MVar), Async (asynchronous computation, 即 rust, python 中的 async/await) 与 TQueue (golang 中的 channel)。

References

• parallel and concurrent programming in haskell - Simon Marlow
• composable memory transactions - Tim Harris et al.
• beautiful concurrency - Simon Peyton Jones

拓展阅读

• GHC wiki - RTS scheduler 这篇文章介绍了 GHC runtime system 的 scheduler
• GHC wiki - lightweight concurrency 这篇文章介绍了 GHC 是如何使用 PTM 实现 User-level concurrency primitives 的