线程同步与锁

线程为什么要同步？

一个简单的例子

i++;

虽然高级语言中是一个简单的自增表达式，但是对于计算机底层而言，还是多条指令运行的。 指令运行一般如下：

1. 从内存中拿到 i 变量值，放到寄存器中
2. 对 i 值进行+1 运算操作
3. 把 i 值再写会内存

现在有两个线程X、Y来执行该语句

我们期望的

或者线程Y 先执行。最后i = 2

可能情况

最后i 写到内存是1。

多个线程对共享变量并发访问操作，就可能发生这种数据覆盖不一致的情况。所以线程之间要同步来避免。

临界区和竞争条件

临界区：即是访问和操作共享数据的代码段。多个执行线程操作这个代码段时，要保证其原子性，不能被中途打断。

竞争条件：如果多个线程处于同一个临界区同时执行，这就是竞争条件。要避免这种情况发生。

为了避免发生竞争条件，需要锁的介入。在操作资源之前，先获取锁，这时其它线程来要等这把锁释放。

这里可能会有疑问，这里获取锁的指令如果也被其它执行线程打断，那锁还有啥意义了？ 所以 获取锁的操作是原子性的。

锁是怎么实现的？

锁是怎么实现的？只用软件是没法实现原子操作的，这要求拉来硬件支持。硬件为操作系统实现原子操作提供了现实基础。一些原子操作：

1. 中断禁止和启用（interrupt disable/enable) 我们知道操作系统通过周期性的时钟中断来获得CPU控制权，所以可以通过禁止中断来实现原子操作不被打断。获得锁以后，再启用中断。
2. 测试和设置（test&set） test&set会执行一个原子操作： 1）设置操作：将1写入到指定内存单元 2）读取操作：返回这个指定内存单元之前（写入1之前）的内容

test&set 的代码示例：

test_and_set(x){
    tmp = x;
    x = 1;
    return tmp;
}

这样的功能，怎么来实现锁呢？一段很聪明有着启发性的代码如下：

x = 0;// x初始为0
# 获得锁
lock(){
    while(test_and_set(x) == 1){}
}
# 释放锁
unlock(){
    x = 0;
}

lock() ：x初始为0，当test&set后返回的还是初始0，退出while，从而获得锁。此时其它线程过来 lock()时，test&set即是1，陷入while循环，表示忙等锁释放。

同步方法

原子操作

类似 i = 10; i++; 大多数体系结构会支持原子操作的简单算数指令。

自旋锁 spinlock

自旋锁，是一种互斥锁。如果某个线程获取到这把锁，那么其它线程就要忙等待（自旋中spining），直到占有的线程释放锁。 忙等 的意思是线程会一直占用着CPU的资源，一直在问锁有没有打开。 所以使用自旋锁要保证获取锁到释放锁之间的时间尽量短，它不允许你占用自旋锁时睡眠。

信号量

上边说的自旋锁会让等待线程忙等占用CPU，如果让等待线程睡眠过去，锁释放的时候再唤醒它，这样就好了。信号量就可以帮到你，信号量是一种睡眠锁。

如果一个线程获取某一资源（信号量代表了这个资源）时，发现已经不够用被占用了，那么他不会像自旋锁一样忙等，而是进到了一个等待队列，然后去睡眠，放弃CPU资源。如果信号量被释放了，就会在等待队列里找到一个等待这个信号量的线程。这就是睡眠与唤醒。它提高了CPU的利用率，但是信号量会比自旋锁有更大的系统开销。

信号量说白了是一个整数，它可以大于1。比如一个资源允许多个锁持有者的情况。自旋锁这种互斥锁就是0和1，只允许有一个锁持有者。如果信号量也只是0和1，一般就叫做二元信号量。信号量是由早期荷兰计算机科学家迪杰斯特拉提出，系统有两种操作，P、V，后来美国佬拿来用就变成了down、up。down操作就是减1，获取信号量的意思，up就是+1，释放这个信号量。down发现如果是0或者>0，就可以获取信号量。

死锁

一个显而易见的死锁例子，可以用 ABBA死锁 记忆。 A和B表示资源，代表不同资源的锁。

这时就会发生死锁，线程X想获取B锁，但是线程Y占用着未释放；线程Y想获取A锁，但是线程X占用未释放。死锁导致系统没法推进下去。

死锁的4个必要条件：

1. 需要的资源有限
2. 持有资源不释放
3. 资源不能抢占
4. 循环等待

几个简单的规则来避免死锁的发生：

1. 按顺序加锁
2. 防止饥饿发生
3. 不要重复请求一个锁

顺序加锁：使用多个锁资源时，保证按一定顺序获取。如上线程X、Y，对A、B资源锁时，X按照A->B，Y按照B->A，导致了循环等待的发生。这一条规则比较重要。

• 操作系统