本人在并发方面属于小白一枚，之前有尝试看《Java并发编程实战》、java concurrent包的源码，一直感觉在看的过程中找不到融会贯通的那个点，拘泥于细节，浮于表面。所以就开始尝试着从源头看起，想找到最本质的东西。这篇文章是自己在看到了相关的书籍和文章之后，思考出来的一点东西，内容并没有什么深入的东西，但是本人通过对这些内容的了解，感觉隐约看到了些不一样的东西。
本文的整体思路：
- 为什么会出现并发
- 并发导致了哪些问题
- 如何解决并发问题
这里讨论的背景是单机、单CPU，为了简化问题本身。多CPU的计算机架构和分布式系统的出现使得并发问题变得更加棘手。
这里不会具体讨论细节的东西，更想提现的是思路~
开始的开始
在抢占式调度操作系统出现之前，是不存在并发问题的。计算机读取一段计算机指令 -> cpu依次执行指令 -> 完成，整个过程一气呵成。不过这种方式存在两个问题：
- cpu不能被充分利用。在当前执行的程序做I/O操作的时候，cpu是空闲的，又因为不能被抢占，所以cpu就被闲置掉了。
- 不能让计算机同时做多个事情。比如个人计算机的场景，想要同时听歌和浏览网页。
于是出现了抢占式调度操作系统。
抢占的时机
根据上边的两个出现的问题，就能判断出来，应该何时抢占：
- 在当前程序做I/O操作的时候。发生I/O的时候，切换到另一个程序执行，从而充分使用cpu。
- 在当前程序执行了一段时间的时候。在音乐软件执行了一段时间，这时候需要切换到浏览器软件来执行。当两个软件在短时间内快速切换并执行时，就达到了两个软件在同时运行的假象。
如上图，当抢占的时机出现的时候，执行抢占这个动作，从而完成程序的切换。
如何抢占
知道要什么时候抢占了，那下一个问题来了，要怎么抢占？
要知道，在当前程序执行的时候，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中
如果两个线程同时在做这个操作，并且中断发生在不恰当的时候，看看会导致什么问题：
当线程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)。
自旋锁很好地解决了互斥的问题，但它也存在一些问题：
- 公平问题。不能保证对线程公平，可能会出现线程饥饿。
- 性能问题。在单CPU中，自旋锁的性能很差，每个thread在等待锁的时候，都会消耗一个完整的时间片，这个消耗随thread数量的增加而增加；在多CPU种，性能有所改善，当某个CPU上的线程释放了锁时，其他CPU上的线程就能立即获得锁，停止轮询。
yield一下就好
自旋锁的自旋过程会浪费cpu资源，从而导致性能下降。为了解决这个问题提出了一个新的概念：yield。
当竞争锁失败时，通过yield指令来让出cpu资源：
while(CompareAndSwap(guard, 0, 1) == 1) {
yield();
}
这样就解决了自旋锁的性能问题，但仍然存在问题：
- 公平问题。自旋锁的公平问题这里仍然存在。
- 性能问题。如果一个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版本，管程的实现都会有所不同。
总结
上边讨论的这些内容总结一下，就是下图了。
由于中断、进程调度等原因，导致了并发问题的出现。为了解决这个问题，提出了锁的概念，并在硬件层面上通过一些原子指令来支持锁的实现。为了隐藏掉锁的实现细节，并希望能够更高效的解决并发问题，于是提出了互斥量、信号量、管程等同步原语。再往上一层，无论是操作系统，还是各种应用程序，在解决并发问题的时候基本都是使用前边说这些概念和思路。
以上，欢迎讨论和指正~
tip
这篇文章的内容大部分来自于一本叫做《Operate System: Three Easy Pieces》的操作系统教材。这本教材是开源的，属于操作系统的入门教材，教材编写的很有趣，有兴趣的人可以去看一看。本文内容主要来自对Concurrency那个部分的思考。
