并发计算

并发问题的根本原因是存在竞争条件, 而竞争条件出现的根本原因是"状态被共享给多个写入者".
如果使用的是函数式的"不可变"状态, 就不会出现并发问题.
问题是否一定需要引入竞争条件才能解决, 取决于问题本身.
有一类被称为Embarrassingly Parallel的问题, 专门指代那些可以完全并行的, 几乎不发生通信的并行任务.
锁是解决竞争状态的最终解决方案, 所有此类问题都可以通过对状态加锁来解决.
锁通常不是性能最优的解决方案.
锁开销是锁本身带来的开销, 锁开销取决于具体实现, 一些锁的开销可能会非常大.
最常见的锁, 获取锁之后就会独占相应的资源直到解锁为止.
互斥锁的一种, 这种锁可以在外层使用锁之后, 内层的代码再次获得同一把锁(不会造成死锁).
这种锁具有公平性, 等待时间更长的线程会更有机会访问共享的资源.
分为读锁和写锁两个部分, 在读任务上不互斥的锁.
写时仍会锁住读.
互斥锁是由操作系统实现的, 当互斥锁获取失败时, 操作系统会将线程休眠, 直到锁被释放时才唤醒.
线程的休眠和唤醒导致了两次上下文切换:
  1. 1.
    休眠: 保存上下文(线程的私有状态).
  2. 2.
    唤醒: 读取上下文(线程的私有状态).
如果互斥锁被锁定的时间总是极短, 则上下文切换会频繁发生, 成为一项开销.
分布式服务无法在不同实例中共享内存, 因此需要通过中间件实现锁.
分布式锁的实现需要这样一个原子操作:
当值不存在时设置值, 并返回真值, 其他情况返回假值.
通过该原子操作, 可以模拟实现"互斥锁的获取(acquire)", Redis的SETNX就是一个典型互斥锁获取操作.
锁也可以通过类似变长数组的结构(比如队列、栈)实现:
  1. 1.
    创建一个UUID作为标识符
  2. 2.
    在尾部追加此标识符
  3. 3.
    检查该标识符的索引
    上述过程可被视作一种锁获取操作,
    当标识符的索引大于0时, 表示锁已被他人获取, 删去此标识符(这隐式要求该数据结构能够实现基于值的删除).
    通过这种方法可以制造出信号量机制(即"同时获取次数有限制的锁").
自旋锁是一种锁获取机制.
这种机制下的锁使用忙等待(Busy waiting, 忙碌等待)进行获取:
在获得锁之前, 线程会一直反复检查锁是否可用, 不会像互斥锁那样让出计算资源.
在大多数需要一定等待时间的竞争条件里, 使用自旋锁会对性能造成浪费, 通常不会使用自旋锁.
优点: 通过忙等待避免了互斥锁的上下文切换开销.
缺点: 性能浪费.
自旋锁是为解决无锁忙等待中的竞争条件而出现的衍生品, 通常只对底层编码有价值.
无锁忙等待的问题在于没有解决竞争条件:
状态检查和状态变是两个独立的步骤, 即使检查通过, 也可能立即被其他线程改变状态.
实现自旋锁需要硬件支持相关的原子指令CAS, 将"检查和锁的获取"变成一个原子操作.
在单核CPU上, 实现自旋锁需要抢占式调度器, 否则线程的忙等待将成为整个CPU的唯一任务.
在多核CPU上, 实现自旋锁需要能够在执行相关原子指令时锁住内存总线, 以防止竞争条件.
条件变量是一种与锁配对使用的阻塞机制.
通常会将条件变量的名字以谓语命名, 例如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)算法.
因为可以避免错误的锁实现, 通常认为使用原子变量要优于手动使用锁.
线程池是一种对象池, 用于复用线程, 任务会排队后分发给特定的线程执行.
此模式通过避免频繁创建和销毁线程, 可节省资源和避免不必要的延迟,
同时还能限制相关任务使用的最大线程数量.
线程池的大小取决于具体任务类型, 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)的那一刻才对数据库锁定
(该锁定是为了完成数据写入, 所以不是一种实际存在的锁).
在乐观并发控制下, 每个事务在提交时,
(数据库)都会检查目标数据是否被其他人修改, 如果数据被修改,
则事务执行失败.
  • 由于不会长时间锁定数据库, 所以有更高的吞吐量.
  • 不会有死锁风险.
竞争激烈的情况下, 事务的失败概率将变得很高, 导致成功执行一次事务需要很长时间.
竞争不激烈的情况(事务执行失败带来的损失比锁定数据带来的损失要少的情况).
悲观并发控制在事务开始的那一刻就对数据库加锁.
  • 长时间锁定数据, 持有锁的当事人决定锁定何时释放, 当事人效率很低时, 锁定的时间很长.
  • 有死锁风险.
竞争激烈的情况.