并发计算

所有可能产生竞争状态的操作最终都可以追溯到"锁"的概念.
锁开销是因为使用锁而带来的开销, 具体开销取决于具体平台的实现, 一些开销可能非常大.
分布式服务无法在不同实例中共享内存, 因此需要通过其他中间件实现锁.
分布式锁的实现需要这样一个原子操作:
当值不存在时设置值, 并返回真值, 其他情况返回假值.
通过该原子操作, 可以模拟实现"互斥锁的获取(acquire)", Redis的SETNX就是一个典型互斥锁获取操作.
锁也可以通过类似变长数组的结构(比如队列、栈)实现:
  1. 1.
    创建一个UUID作为标识符
  2. 2.
    在尾部追加此标识符
  3. 3.
    检查标识符的索引
    上述过程可被视作一种锁获取操作,
    当标识符的索引大于0时, 表示锁已被他人获取, 删去此标识符(这隐式要求了该数据结构能够实现基于值的删除).
    通过这种方法可以制造出信号量机制(即"同时获取次数有限制的锁").
最常见的显式锁, 使用显式锁而不使用synchronized关键字的原因在于锁的锁定和解锁不再是一个代码块的开头与结尾,
而是可以任意设置(增加了自由度).
互斥锁的一种, 这种锁可以在外层使用锁之后, 内层的代码再次获得这把锁(不会死锁).
这种锁具有公平性, 因此等待时间更长的线程会更有机会访问共享的资源.
只有只读任务不互斥的锁(写时也会锁住读), 分为读锁和写锁两个部分.
自旋锁是一种锁获取机制.
这种机制下的锁使用忙等待(Busy waiting, 忙碌等待)进行获取:
在获得锁之前, 线程会一直反复检查锁是否可用, 不会像互斥锁那样让出计算资源.
在大多数需要一定等待时间的竞争条件里, 使用自旋锁会对性能造成浪费, 通常不会使用自旋锁.
优点: 通过忙等待避免了互斥锁的上下文切换开销.
缺点: 性能浪费.
自旋锁是为解决无锁忙等待中的竞争条件而出现的衍生品, 通常只对底层编码有价值.
无锁忙等待的问题在于没有解决竞争条件:
状态检查和状态变是两个独立的步骤, 即使检查通过, 也可能立即被其他线程改变状态.
实现自旋锁需要硬件支持相关的原子指令CAS, 将"检查和锁的获取"变成一个原子操作.
在单核CPU上, 实现自旋锁需要抢占式调度器, 否则线程的忙等待将成为整个CPU的唯一任务.
在多核CPU上, 实现自旋锁需要能够在执行相关原子指令时锁住内存总线, 以防止竞争条件.
互斥锁是由操作系统实现的, 当互斥锁获取失败时, 操作系统会将线程休眠, 直到锁被释放时才唤醒.
线程的休眠和唤醒导致了两次上下文切换:
  1. 1.
    休眠: 保存上下文(线程的私有状态).
  2. 2.
    唤醒: 读取上下文(线程的私有状态).
如果互斥锁被锁定的时间总是极短, 则上下文切换会频繁发生, 成为一项开销.
条件变量是一种需要与显式锁配对使用的阻塞机制.
通常会将条件变量的名字以谓语命名, 例如notFull, notEmpty.
条件变量维护一个内部线程队列.
条件变量提供以下原语/功能:
  • 等待(await):
    1. 1.
      将当前线程插入内部队列的末尾.
    2. 2.
      解除与条件变量配对的显式锁, 阻塞, 等待条件变量收到信号.
    3. 3.
      收到信号后, 重新锁定显式锁.
  • 通知(notify, 或称signal):
    移除线程队列里的第一个线程, 解除它的阻塞.
  • 广播(broadcast, 或称signalAll):
    移除线程队列里的所有线程, 解除它们的阻塞.
ReentrantLock mutex = new ReentrantLock();
Condition condition = mutex.newCondition();
private foo() {
	mutex.lock();
	try {
		while (!someCondition()) { // 检查条件是否满足
			condition.await(); // 阻塞, 等待其他线程发出信号
		}
		// ...
	} finally { mutex.unlock(); }
}
// 其他线程
private bar() {
	mutex.lock();
	try {
		// ...
		condition.signal(); // 发出信号
	} finally { mutex.unlock(); }
}
原子操作指的是具有原子性的操作:
(从当事人以外的角度来看)一个只能处于"已发生"或"未发生"状态的操作.
原子操作不存在"发生了一半"的状态.
"自增"就是典型的原子操作.
在支持ACID的数据库管理系统(DBMS)里, 一个事务(transcation)就具有原子性:
当事务出现错误时, 会回滚到事务开始前的状态.
大部分事务都是以数据库内部加锁的二阶段锁定的形式出现的(开始事务时进行锁定, 事务提交时释放).
请不要将二阶段锁定和二阶段提交(2PC, two-phase commit)混淆, 后者是一种分布式事务协议.
二阶段锁定是数据库主要的事务处理方式, 在第一阶段获取锁, 在第二阶段释放锁.
对客户端而言, 二阶段就是事务的开始与提交.
在Redis里, Multi/Exec事务虽然是原子操作, 却只在最后提交时一次性处理整个事务.
在事务执行时, 其基于的读取数据可能已经被其他客户端操作改变了, 这就会造成错误的写入,
因此需要配合一些额外的机制让事务在数据被改变时直接失败(Redis的Watch).
原子变量是带有原子性的数据结构, 这种数据结构自身已经实现了线程安全性.
使用原子变量比手动用锁要好, 可以避免错误的锁实现.
原子变量是一种支持原子操作的变量, 使用原子变量在多线程场景里总是安全的.
使用原子变量, 可以实现无锁(lock-free)非阻塞(non-blocking)算法.
在Java里, 分为线程安全和线程不安全两种类型,
线程安全的类型创建出的就是原子变量, 这种类型的性能总是低于线程不安全的类型.
一种原子操作, 根据比较内存中的值与原值是否相同, 以决定是否将数据替换为新值.
并发问题的根本原因是存在竞争条件, 而竞争条件出现的根本原因是"状态被共享给多个写入者".
如果使用的是函数式的"不可变"状态, 就不会出现并发问题.
问题是否一定需要引入竞争条件才能解决, 取决于问题本身.
有一类被称为Embarrassingly Parallel的问题, 专门指代那些可以完全并行的, 几乎不发生通信的并行任务.
线程池是一种对象池, 用于复用线程, 任务会排队后分发给特定的线程执行.
此模式通过避免频繁创建和销毁线程, 可节省资源和避免不必要的延迟,
同时还能限制相关任务使用的最大线程数量.
线程池的大小取决于具体任务类型, CPU密集型的任务线程池最佳大小接近核心数量
(考虑到系统上还有其他任务在执行, 所以可能不等于核心数量).
IO密集型的任务可以用超出核心数量的线程, 但用线程实现的并发在效率上远远不如异步IO模式.
使用线程池实现的HTTP服务器可能在大量请求的情况下因线程池满而无法响应请求.
可以通过压力测试来决定线程池的大小.
这是一种为避免类似如下添加了synchronized关键字(Java的隐式锁)的方法的开销而出现的模式
(synchronized方法的开销非常大):
class Foo {
	private Helper helper = null;
	public synchronized Helper getHelper() {
		if (helper == null) {
			helper = new Helper();
		}		
		return helper;
	}
}
使用双重检查锁定模式的代码:
class Foo {
	private Helper helper = null;
	public Helper getHelper() {
		if (helper == null) {
			synchronized(this) {
				if (helper == null) {
					helper = new Helper();
				}
			}
		}
		return helper;
	}
}
由于一些编译器优化, 该模式有可能导致程序崩溃(例如J2SE 1.4).
在J2SE 5.0里, 添加volatile关键字(Java的volatile关键字保证变量不进行乱序执行优化)可以正确处理此模式:
class Foo {
	private volatile Helper helper = null;
	public Helper getHelper() {
		if (helper == null) {
			synchronized(this) {
				if (helper == null) {
					helper = new Helper();
				}
			}
		}
		return helper;
	}
}
一种基于消息传递的数学计算模型, 用于处理并发计算.
Actor模型最著名的应用是它在Erlang语言中的运用.
在Erlang里, 两个Actor可以建立连接, 当一个Actor出错崩溃时, 与之相连的Actor会一起崩溃,
这种"崩溃时一定会通知使用者"的机制使得Erlang的let it crash哲学能够成立.
由于Actor之间具有隔离性, 它们永远不会遇到传统多线程模型的并发问题.
根据接收到的消息, 一个Actor可以选择执行以下三件事中的一件:
  • 创建更多Actor.
  • 向其他Actor发送消息.
  • 指定自己收到下一条消息时应该采取的行为.
    这是指Actor可以有自己的私有状态.
参考: https://www.brianstorti.com/the-actor-model/
Actor不依赖于中央消息队列, 它自己就是消息的接收者,
每个Actor有一个信箱(mailbox), 按序堆放了收到的消息, Actor一次从信箱里获取一个消息进行处理.
乐观并发控制在事务(transcation)提交(commit)的那一刻才对数据库锁定
(该锁定是为了完成数据写入, 所以不是一种实际存在的锁).
在乐观并发控制下, 每个事务在提交时,
(数据库)都会检查目标数据是否被其他人修改, 如果数据被修改,
则事务执行失败.
  • 由于不会长时间锁定数据库, 所以有更高的吞吐量.
  • 不会有死锁风险.
竞争激烈的情况下, 事务的失败概率将变得很高, 导致成功执行一次事务需要很长时间.
竞争不激烈的情况(事务执行失败带来的损失比锁定数据带来的损失要少的情况).
悲观并发控制在事务开始的那一刻就对数据库加锁.
  • 长时间锁定数据, 持有锁的当事人决定锁定何时释放, 当事人效率很低时, 锁定的时间很长.
  • 有死锁风险.
竞争激烈的情况.