并发简史

死锁.jpeg

本人在并发方面属于小白一枚，之前有尝试看《Java并发编程实战》、java concurrent包的源码，一直感觉在看的过程中找不到融会贯通的那个点，拘泥于细节，浮于表面。所以就开始尝试着从源头看起，想找到最本质的东西。这篇文章是自己在看到了相关的书籍和文章之后，思考出来的一点东西，内容并没有什么深入的东西，但是本人通过对这些内容的了解，感觉隐约看到了些不一样的东西。

本文的整体思路：

• 为什么会出现并发
• 并发导致了哪些问题
• 如何解决并发问题

这里讨论的背景是单机、单CPU，为了简化问题本身。多CPU的计算机架构和分布式系统的出现使得并发问题变得更加棘手。

这里不会具体讨论细节的东西，更想提现的是思路~

开始的开始

在抢占式调度操作系统出现之前，是不存在并发问题的。计算机读取一段计算机指令 -> cpu依次执行指令 -> 完成，整个过程一气呵成。不过这种方式存在两个问题：

• cpu不能被充分利用。在当前执行的程序做I/O操作的时候，cpu是空闲的，又因为不能被抢占，所以cpu就被闲置掉了。
• 不能让计算机同时做多个事情。比如个人计算机的场景，想要同时听歌和浏览网页。

于是出现了抢占式调度操作系统。

抢占的时机

根据上边的两个出现的问题，就能判断出来，应该何时抢占：

• 在当前程序做I/O操作的时候。发生I/O的时候，切换到另一个程序执行，从而充分使用cpu。
• 在当前程序执行了一段时间的时候。在音乐软件执行了一段时间，这时候需要切换到浏览器软件来执行。当两个软件在短时间内快速切换并执行时，就达到了两个软件在同时运行的假象。

抢占.jpg

如上图，当抢占的时机出现的时候，执行抢占这个动作，从而完成程序的切换。

如何抢占

知道要什么时候抢占了，那下一个问题来了，要怎么抢占？

要知道，在当前程序执行的时候，cpu运行的仅仅是当前程序的指令，也就是说如果当前程序不主动让出cpu的话，它就能够一直运行下去。为了能够解决这个问题，出现了一个新的概念：中断（Interrupts）。

中断会在以下场景被触发：

• 执行系统调用时。系统调用都是I/O相关，所以执行系统调用就是在做I/O操作。
• 每隔固定时间。
• 异常。

一旦发生中断，cpu的使用权就会从当前执行的程序手中回收，并交给操作系统。操作系统的调度系统会根据情况来决定接下来要运行哪个程序。这样就完成了一次抢占。

中断是并发问题的原罪

中断的出现为操作系统对资源做掌控和充分利用提供了可能，但也同时带来了新的问题。

无论是进程之间，还是线程之间，都可能存在共享的资源。共享资源不可怕，同时对共享做操作也不可怕，可怕的是在不恰当的时机发生了中断。

比如看这个场景：

count = count + 1

这是一个累加操作，在高级语言中，这就是一行代码，但是当把它转换成机器码时，就变成了三条命令：

1. mov ax, 0x1111 # 把内存地址0x1111中的数据读取到ax寄存器
2. add ax, 1      # 对ax寄存器做加1操作
3. mov 0x1111, ax # 把ax寄存器中的数据存入内存地址0x1111中

如果两个线程同时在做这个操作，并且中断发生在不恰当的时候，看看会导致什么问题：

中断问题.png

当线程1执行完第二条指令时，此时ax寄存器的值为1。此时操作系统进行了调度，进行上下文切换，保存寄存器ax的值为1，切换至线程2。线程2完成了以上三条指令，内存地址0x1111此时存储的值为1。这时切换回线程1，恢复寄存器ax的值为1，执行第三条指令，此时内存地址0x1111的值为1。所以，当两个线程分别完成两次加一操作后，结果为1。

并发问题出现了。

如何解决并发问题

上边的这个场景就是很典型的并发问题的场景，可以看出来导致并发问题的原因有两个：

• 对资源的操作不是原子的。
• 在操作过程中发生了中断。

中断是抢占式调度不可避免的，虽然能够屏蔽中断，但是这就又出现了刚才提到了非抢占调度的问题。那么就看看能不能把操作变成原子操作。这时出现了锁的概念。

锁是什么

锁出现的目的是希望提供一种方式，能够把一串命令变成原子的操作，比如：

lock()
count = count + 1
unlock()

lock和unlock代表这个原子操作的开始和结束，这两者之间就是所谓的临界区。希望锁能够达到的效果是，在同一时刻，有且仅有一个线程在临界区中。这样即使线程1在累加的过程中发生了中断并切换到线程2运行，线程2也无法做累加操作。

如何实现锁

锁的在概念上能够解决共享资源上的并发问题了，但是仔细想一下，其实锁本身也是一种资源，是需要竞争的，这就又出现了共享资源的并发问题，比如：

int flag = 0;

int lock() {
    while(flag == 1) {
        //空循环
    }
    flag = 1; //如果行执行前发生中断，就会出现问题
}

int unlock() {
    flag = 0;
}

lock()
count = count + 1
unlock()

这种情况，仅仅通过软件层面是无法解决的了，需要硬件的支持。

原子指令

为了能够实现锁，cpu提供了一部分原子指令来做支持。

Test-And-Set

int TestAndSet(int *old_ptr, int new) {
    int old = *old_ptr;
    *old_ptr = new;
    return old;
}

Compare-And-Swap

int CompareAndSwap(int *ptr, int expected, int new) {
    int actual = *ptr;
    if (actual == expected)
        *ptr = new;
    return actual;
}

Load-Linked And Store-Conditional (LL/SC)

int LoadLinked(int *ptr) {
    return *ptr;
}

int StoreConditional(int *ptr, int value) {
    if (no on has updated *ptr since the LoadLinked to this address) {
        *ptr = value;
        return 1; // success!
    } else {
        return 0; // failed to update
    }
}

Fetch-And-Add

int FetchAndAdd (int *ptr) {
    int old = *ptr;
    *ptr = old + 1;
    return old;
}

用原子指令实现锁

有了这些原子指令，锁就能够实现了。java这边主要用的是CAS，所以用CAS来看下：

int guard = 0;

int lock() {
    while(CompareAndSwap(guard, 0, 1) == 1) {
        //spin
    }
}

int unlock() {
    guard = 0;
}

lock()
count = count + 1
unlock()

CAS指令保证了 （读取flag，判断是0） --> （设置flag = 1） 这两个动作是原子操作，不会被中断，因此避免了并发问题。这样在硬件的支持下完成了锁的实现，并发问题有了解决方案。

自旋锁的问题

上边的实现在竞争锁失败的时候，当前线程会一直空循环，竞争成功后才继续进行下去，这就是自旋锁(spin lock)。

自旋锁很好地解决了互斥的问题，但它也存在一些问题：

1. 公平问题。不能保证对线程公平，可能会出现线程饥饿。
2. 性能问题。在单CPU中，自旋锁的性能很差，每个thread在等待锁的时候，都会消耗一个完整的时间片，这个消耗随thread数量的增加而增加；在多CPU种，性能有所改善，当某个CPU上的线程释放了锁时，其他CPU上的线程就能立即获得锁，停止轮询。

yield一下就好

自旋锁的自旋过程会浪费cpu资源，从而导致性能下降。为了解决这个问题提出了一个新的概念：yield。
当竞争锁失败时，通过yield指令来让出cpu资源：

while(CompareAndSwap(guard, 0, 1) == 1) {
    yield();
}

这样就解决了自旋锁的性能问题，但仍然存在问题：

1. 公平问题。自旋锁的公平问题这里仍然存在。
2. 性能问题。如果一个thread获得了锁并且在释放之前被抢占，这时被调度的其他thread会分别yield，有可能同一个thread被调度两次，也就是说yield两次，这种情况要一直持续到，调度到竞争到锁的那个thread成功释放锁时才会终止。这期间可能产生大量的yield和调度操作。

用sleep和队列代替自旋

为了解决自旋的公平问题和性能问题，操作系统提供了两个新的系统调用park和unpark（Solaris系统中，其他系统的名称会有所不同）。park会使当前线程挂起，unpark会使指定线程唤醒。

这两个系统调用，在结合上队列，看看如何实现一个锁。

Lock {
 int guard = 0;
 int flag = 0;
 Queue<Integer> q = new Queue<Integer>();
}

Lock lock;

lock() {
    while(CompareAndSwap(lock.guard, 0, 1) == 1) {
        if (lock.flag = 0) {
            lock.flag = 1;
            lock.guard = 0;
        } else {
            lock.q.add(currentThreadId());
            lock.guard = 0;
            park();
        }
    }
}

unlock() {
    while(CompareAndSwap(lock.guard, 0, 1) == 1) {
        if(lock.q.isEmpty()) {
            lock.flag = 0;
        } else {
            unpark(lock.q.take());
        }
        lock.guard = 0;
    }
}

这个实现通过队列记录了竞争过锁的线程，用队列的先后顺序解决了锁的公平问题；通过park和unpark避免了自旋，解决了锁的性能问题。

更高级的同步原语

锁的问题算是全部解决了，不过在这个讨论的过程中会有一种感觉，就是细节的东西太琐碎了，在编程过程中要非常仔细地控制锁。为了提效，计算机界的大佬们对常见的并发场景做了一层抽象，提出了一些比锁更高层次的同步原语，从而屏蔽了锁的细节。

互斥量（mutex）

mutex是最简单的同步原语了，它仅允许同一时刻只有一个线程进入临界区。

Mutex mutex;

void run() {
    mutex.lock();
    //do something
    mutex.unlock();
}

条件变量（condition variables）

为了能够很好的解决生产者/消费者这种的并发模型，提出了条件变量这个同步原语。

条件变量能够让一系列线程等待在某个条件上，当这个条件满足时，等待在该条件上的线程会被唤醒。条件变量需要和mutex配套使用。

Mutex mutex;
Condition notEmpty;
Condition notFull;

Queue queue;

void cunsum() {
    mutex.lock();
    while(queue.isEmpty()) {
        notEmpty.await(mutex);
    }
    data = queue.take();
    notFull.singal();
    mutex.unlock();
}

void product() {
    mutex.lock();
    while(queue.isFull()) {
        notFull.await(mutex);
    }
    queue.add(data);
    notEmpty.signal();
    mutex.unlock();
}

在await之前，必须保证已经竞争到mutex。await时，会将当前线程加入到condition的等待队列中，然后释放mutex，线程等待。当这个condition被signal时，之前等待的线程重新获得mutex，并被唤醒，从之前await的位置继续执行。

信号量（Semaphore）

有了互斥量和条件变量这两个同步原语之后，计算机届的大佬又感觉有点儿麻烦，我们在解决并发问题时，有时要用互斥量，有时又要用条件变量，如果能把这两个合起来是不是方便些？于是就提出了信号量。

信号量是一个包含了数值的对象，wait()会对数值减1，当数值小于零时，线程等待，直到数值大于等于零时被唤醒；post()会对数值加1，如果有等待的线程，唤醒它们。

把信号量当互斥量使用

Semaphore semaphore;
semphore.init(1);

void run() {
    semaphore.wait();
    //do something
    semaphore.post();
}

信号量实现生产者/消费者模型

int MAX = 10;

Semaphore full;
full.init(0);

Semaphore empty;
full.init(MAX);

Semaphore mutex;
lock.init(1);

Queue queue;

void cunsum() {
    full.wait();
    mutex.lock();
    data = queue.take();
    mutex.unlock();
    empty.post();
}

void product() {
    empty.wait();
    mutex.lock();
    queue.add(data);
    mutex.unlock();
    full.post();
}

管程（Monitor）

有了上面的这些原语之后，大佬们还是觉得用起来不够简单，还是要关心一些并发问题的细节，它们希望把这些再封装一下，让使用者完全不关心这些细节，让他们能够像写单线程的程序一样来写并发程序，于是提出了管程这个概念。

“管程”这个翻译很棒，顾名思义，管程就是一个管道，在同一时刻，只有一个线程能够访问管道内的程序。

不像上边的几个同步原语在操作系统层面就有实现了，管程是在编程语言层面才提供的同步原语，对于不同的语言，都会针对自己所关心的场景有着自己不同的实现。

java里面的管程

Object lock = new Object();

synchronized(lock) {
    //do something;
}

sychronized代码块在编译之后，会在开始和结束的位置加上monitorenter和monitorexit指令，代表管程的进入和退出。至于管程具体的实现，就要看java语言本身的实现了。对于不同的java版本，管程的实现都会有所不同。

总结

上边讨论的这些内容总结一下，就是下图了。

工具概览.png

由于中断、进程调度等原因，导致了并发问题的出现。为了解决这个问题，提出了锁的概念，并在硬件层面上通过一些原子指令来支持锁的实现。为了隐藏掉锁的实现细节，并希望能够更高效的解决并发问题，于是提出了互斥量、信号量、管程等同步原语。再往上一层，无论是操作系统，还是各种应用程序，在解决并发问题的时候基本都是使用前边说这些概念和思路。

以上，欢迎讨论和指正~

tip

这篇文章的内容大部分来自于一本叫做《Operate System: Three Easy Pieces》的操作系统教材。这本教材是开源的，属于操作系统的入门教材，教材编写的很有趣，有兴趣的人可以去看一看。本文内容主要来自对Concurrency那个部分的思考。