February 1, 2023

我尝试用 markdown 写了这篇笔记，然后导入 Notion。看上去它工作得不太好：代码块内的换行全没了，到文章内某节的超链接也不工作。

CiteSeerX

动机

我们期望写出简单而优雅、显然没有错误的程序，但是并行程序往往丑陋，尤其是模块化程度较低。STM 被期望作为一种在共享内存的并行处理器上编程的新方法解决这个问题，或者至少提供一些启发。

示例：银行账户

考虑这个编程任务：两个银行账户，账户的状态在内存中保存。一个线程可以调用转账操作，将钱从一个账户转移到另一个账户。转账操作可能同时被多个线程调用。要求任何线程都不能观察到钱已经离开一个账户，但未到达另一个账户的中间状态。

锁

我们可以提供一个加了同步锁的 withdraw 方法来修改账户余额，阻止两个线程同时调用这一方法。于是，一次转账看起来大概是这样的：

from.withdraw(n);
to.withdraw(-n);

但是，锁的粒度太小，其他线程是可以看到 from 已经调用完 withdraw，to 还没调用 withdraw 的状态的。所以 from 和 to 也需要加锁：

from.lock();
to.lock();
from.withdraw(n);
to.withdraw(-n);
from.unlock();
to.unlock();

但是这个写法不能避免死锁。我们可以同时分别由两个账户向另一个账户转账，此时两个线程会各拿到一个锁然后死等另一个。标准的做法是为锁增加一个任意的全序，递增地获取它们：

if (from < to) {
    from.lock();
    to.lock();
} else {
    to.lock();
    from.lock();
}

这个写法的缺陷在于假定了我们可以提前预测所需的所有锁。一个负面的例子是：如果 withdraw 实现为在 from 没有足够余额的情况下由 from2 转账，我们不能预先知道是否要获取 from2 的锁。在获取 from 的锁并发现需要获取 from2 的锁时可能太晚了（虽然原文没写，我认为另一方面假定总是要获取 from2 的锁会过于保守）。此外，from2 若非需要加锁，其实只应由 from 知道，不该由 transfer 知道。

当考虑阻塞时，事情变得更复杂。比如当我们希望阻塞至 from 有足够的钱来转账，此时需要释放 from 的锁并等待一个条件变量。

Locks are bad

作为并发编程技术，锁和条件变量是有根本的缺陷的。有几类典型的容易犯错的地方：