临界资源与同步

发表于 分类于

cover
总结临界区与同步的相关问题

临界资源与竞态条件

临界资源和临界区，是编程的一种通用场景，和具体语言和平台无关，是一类需要解决的普遍问题。其中有以下几个关键的概念

临界资源

临界资源（critical resource）是一次仅允许一个进程使用的资源。例如打印机、进程之间共享的变量、节点之间共享的资源等。所有并发的错误，基本都可以归结到对临界资源的访问不当

临界区

临界区（critical section），就是访问临界资源的代码

例如，

1
2
3
4
5
6
do {
  entry section;    // 进入区（检查进程是否可以进入临界区）
  critical section; // 临界区（访问临界资源）
  exit section;     // 退出区（清除正在访问临界区的标志）
  remainder section;// 剩余区（剩余代码）
} while(true)

上面这个伪代码片段，访问临界资源的那一段，就是临界区

竞态条件和同步

当临界区同时在多个线程/进程/节点中执行，由于执行的顺序不可预知，具有随机性，从而导致结果不正确，称为发生了竞态条件（race condition）。为了避免临界区发生竞态条件，而对临界区代码进行的保护处理，就称为同步（synchronize）

在java里，用关键字synchronized来进行同步，但是不可混淆认为同步是java平台特有的概念。如上所述，临界区和同步是一类普遍问题，跟具体平台实现无关。

根本的目的，是通过某种手段，避免对临界资源的访问引起程序的逻辑错误。

原子操作

避免竞态条件的轻量级方法，是使用原子操作。

原子操作（atomic operation）在硬件层面是通过CPU保证的。linux包装了若干原子操作API，来支持原子操作。由于原子操作的实现与CPU的类型相关，所以具体实现有所不同。以x86平台为例

所有的原子操作都作用于类型为atomic_t的变量。在x86平台上，它被简单的定义为包含int类型的结构体。定义成结构体的好处是防止错误的强制转型，绕过原子操作API去操作原子变量

1
2
3
typedef struct {
    int counter;
} atomic_t
1
2
3
atomic_t a = ATOMIC_INIT(i);// 原子变量初始化
atomic_set(&a, i);// 原子写
atomic_read(&a);// 原子读

对于简单的场景，用原子操作API就可以避免竞态条件，是方便和轻量级的方案。由于不需要加锁，开销很小。所以在条件允许的情况下，应该尽量优先考虑使用原子操作

锁

CPU提供了原子指令，实现算术运算和比较之类的原子操作。但对于更复杂的场景，比如临界资源是不定长的数据结构（例如链表），CPU没有提供原子指令，这种情况就需要对临界资源加锁，来实现同步。

可以把锁想象成一把门锁，门后的房间是临界区。当一个线程/进程获得锁进入房间之后，它会锁住房门；当它结束对临界资源的操作之后，就离开房间，打开门锁。如果另一个线程在房门上锁时来了，它就必须等待。

linux提供的常见锁机制

linux提供常见的锁机制包括，自旋锁，信号量，互斥锁

spin lock

自旋锁（spin lock），是linux中最常见的锁。最多只能被一个线程持有，如果另一个线程试图获得已经被占用的spin lock，那么该线程就会进入忙循环，等待锁重新可用。

一个被争用的自旋锁，使得请求它的线程在等待锁时不断自旋，所以自旋锁不应该被长时间持有，而是应该在短时间内进行轻量级加锁。

把自旋锁读写分开，就是读-写自旋锁

semaphore

信号量（semaphore），是睡眠锁。如果一个线程试图获得不可用的信号量，则会进入等待队列并睡眠。这时处理器可以去执行其他线程的代码。当信号量可用时，处于等待队列的线程会被唤醒，并获得该信号量。

相对于自旋锁，信号量能够更好地利用CPU，因为时间没有浪费在线程自旋上。但是信号量的开销比自旋锁更大。因此，信号量适用于锁被长时间持有的状况。

同自旋锁一样，信号量也可以读写分离为读-写信号量

mutex

mutex基本上可以理解为计数为1的semaphore

死锁

死锁最常见的场景是ABBA死锁。即一个线程持有锁A，等待锁B，另一个线程持有锁B，等待锁A。这种情况下2个线程就发生了死锁

发生死锁通常都是代码的错误，一个关键的原则是，要按顺序加锁。如果有代码是按照顺序先获取锁A，再获取锁B，那么其他的代码也要保持这个顺序。否则当两个线程分别执行这2段代码的时候，就有概率发生死锁。

有一种比较隐蔽的情况，是程序没有显式地加锁，但是依赖的第三方资源加锁，这种情况也会发生死锁。比如一段代码先insert mysql的表A，再insert表B；另外一段代码相反，先update表B，再update表A。这时候由于mysql会给表加行级锁，就可能会发生上述的ABBA死锁。

分布式锁

上面说的都是单机的情况，在集群环境下，单机的锁将会失效，这种情况需要分布式锁

比如有一段逻辑是更新数据库中的商品余量。即使给这段临界区代码加了锁，也只能保证单机情况下的同步。但是对于集群环境，更新商品余量的请求可能同时发到N台节点上，这同样会在数据库产生race condition，造成数据不一致。这种情况需要引入分布式锁，才能避免竞态条件。