分类
并发控制算法通常根据读写操作同步的方式来分类。同步可以通过共享数据上的互斥机制（例如，锁🔒），或者通过显式地使用时间戳排序来实现。
并发控制算法可以进一步区分为悲观算法和乐观算法。
悲观算法（pessimistic approaches）的基本原则是Murphy定律（墨菲定律）：如果某事物可以出错，那么它就会出错。在悲观算法中，操作时在它们被执行前同步的，这意味着冲突在允许发生之前就解决了。
相反，乐观算法（optimistic approachs）是基于错误一般不会发生的观点。所以操作被简单地执行，在事务结束的时候再进行同步。如果那是确实发生了冲突，一个或更多的事务将被迫终止。
下面将讨论两个悲观算法和一个乐观算法。
两阶段锁定
最古老最简单也是最广泛使用的并发控制算法是锁定（locking🔒）。
当一个进程要作为事务的一部分来读或写一个数据项时，它请求调度管理器允许它给该数据项加锁。同样，当它不再需要一个数据项时，就请求调度管理器释放该锁。
调度管理器的任务是以一种可以得到正确调度结果的方式来允许加锁和释放锁，即需要使用一种可以提供串行调度的算法。这样一个算法是两阶段锁定算法。
如下图所示的两阶段锁定（two-phase locking，2PL）中，调度管理器先在增长阶段（growing phase）获得它所需要的所有锁，然后在收缩阶段（shrinking phase）释放它们。尤其要遵守下面三个规则：
- 当调度管理器收到来自事务管理器的
open(T,x)操作时，它检测该操作是否跟它已经允许锁定的另一个进程冲突。如果存在冲突，操作open(T,x)被延迟（这样事务$T$也被延迟）。如果没有冲突，调度管理器就允许对数据项$x$加锁，并将这个操作传递给数据管理器。 - 直到数据管理器通知它已经完成了对锁定数据项x的操作，调度管理器才会释放数据项x的锁。
- 一旦调度管理器为事务$T$释放了锁，那么无论事务T请求为哪个数据项加锁，调度管理器都不会允许T加另外一把锁（即只能一次获取到所需的所有锁）。$T$获取另外一把锁的任何企图都是一个程序错误，都会终止事务$T$。
在许多系统中，收缩阶段是在事务运行结束之后，要么提交、要么终止时出现，它导致锁的释放（同时释放），如下图所示。这种策略被称为严格的两阶段锁定。
严格的两阶段锁定有两个主要的优点：
- 事务总是读提交事务写入的值，所以我们从来都不会因为事务的计算是基于一个它不应该看到的数据项而终止它。
- 所有锁的获得和释放都可以由系统来处理而无需事务关心。要访问一个数据项就要获得锁，当事务完成时就释放锁。这种策略消除了瀑布型终止（cascaded aborts），即不得不撤销一个已经提交的事务，因为它看到了它不该看见的数据项。
悲观的时间戳排序
一个完全不同的并发控制方法是在每个事务$T$开始时给它分配一个时间戳$ts(T)$。
使用Lamport算法，我们可以保证时间戳是惟一的。事务$T$的每个操作都被盖上时间戳$ts(T)$，并且系统中的每个数据项$x$都有一个相关的读时间戳$ts_{RD}(x)$和写时间戳$ts_{WR}(x)$。读时间戳被设置为最近读$x$的事务的时间戳，而写时间戳是最近修改$x$的事务的时间戳。使用时间戳排序，如果两个操作冲突，则数据管理器先处理时间戳最早的操作。
现在假设调度管理器从具有时间戳$ts$的事务$T$收到一个操作，read(T,x)。但是$ts<ts_{WR}(x)$。**换句话说，调度管理器发现一个对$x$的写操作在事务开始后已经完成（也即，在事务$T$启动到开始读之间，调度管理器发现一个对x的写操作在此期间完成了）。在这种情况下，事务$T$简单的被终止。**相反，如果$ts>ts_{WR}(x)$，那么让读操作发生（即上一个对$x$的写操作是在事务$T$之前完成的）。此外，$ts_{RD}(x)$被设置为$max{ts, ts_{RD}(x)}$。
同样，假设调度管理器收到一个具有时间戳$ts$并包含写操作write(T, x)的事务$T$。**如果$ts<ts_{RD}(x)$，那么它只能取消事务$T$，这是因为$x$的当前值已经被更晚的事务读过**（也即，在事务$T$启动到开始写之前完成了一个事物对$x$的读操作，实际上应该事务$T$先来的，但是被别人插队了，为了大局，事务$T$只能取消）。另一方面，如果$ts>ts_{RD}(x)$，那么它改变$x$的值，因为没有更晚的事务读过它。$ts_{WR}$也被设置为$max{ts, ts_{WR}(x)}$。
时间戳具有与锁定不同的特性。当事务遇到一个更大（或更晚）的时间戳时，它中止，而在同样的情况下，如果使用锁定方法，事务将等待或立即执行（也即，要是被人插了队自己就中止退出）。另一方面，它不会造成死锁，这是一个很大的优点。
乐观的时间戳排序
第三种处理多个事务同时执行的方法是乐观的并发控制（optimistic concurrency）。此技术的思想是：不关心别人在干什么，继续做自己要做的事情。如果有问题，等到后面再考虑（许多政客也使用这个算法，注：个人认为西方政客会这样做，咱们中国的政客都是特别怕出事情担责任的）。实际上，相对来讲冲突是很少的，所以系统大部分时间都运行正常。
尽管冲突可能很少发生，但也不是不会发生，因此仍需要某种方法来处理冲突。乐观的并发控制所做的事情是跟踪哪些数据项被改写了。在某个事务被提交的时候，它检查其他所有事务，看看是否有某些数据项从这个事务开始后被改变了（即在某个事务提交的时候检查其数据项是否被其他事务改变了）。如果被改变了，该事务被终止；如果没有被改变，则该事务提交。
乐观的并发控制算法最适合基于私有工作空间的实现。在这种方式下，每个事务私下改变自己的数据，不受别的事务的干涉。最终，新数据要么被提交、要么被释放，这是一个相对简单直接的方法。
乐观的并发控制的最大优点是它不会发生死锁，允许最大的并行性。这是因为没有进程需要等待一个锁。缺点是有时它可能会失败，那时事务将不得不再次执行。在负载较重的情况下，失败的可能性比较大，使得乐观的并发控制成为了一个较差的选择。
此外，对乐观的并发控制的研究主要集中在非分布式系统中。
注：本文内容摘自「分布式系统原理与范型」，供本人学习回顾使用。