并发的各种概念定义
数据竞争（Data Race）
数据共享读， 数据可写（会发生变化）
竞态条件（Race Condition）
- 多线程、进程操作（读写）共享数据的最终结果取决于进程、线程执行的时序（顺序）;如if(a>0) a++,可能执行一次a++也可能执行多次a++;
互斥
进程、线程竞争使用具有排它性的共享资源。
临界资源
临界资源、互斥资源或者共享变量（一次值允许一个进程、线程使用）。
临界区（互斥区）
对临界资源实施操作的程序片段
同步
系统中多个进程、线程中发生的事件存在某种时序关系，需要相互合作，共同完成一项任务。
关键字：多*程，通信，时序（协作）
同步机制
为何叫同步机制，而不是叫别的？？因为常常把互斥看做一种特殊的同步，实际上同步机制技能解决互斥问题也能解决同步问题，
线程上下文
是指再某一时间CPU寄存器和程序计数器的内容
Tss任务状态段，位于内存中的一段数据
经典同步机制-信号量以及PV操作
信号量：
描述：进程、线程间传递信息的一个整数值
定义：
struc semaphore{
int count
queueType queue;//等待队列
}
操作：初始化 ，P和V（P、v分别是荷兰语的test(proberen）和 increment(verhogen))
| P | V |
|---|---|
| DOWN | UP |
| - | + |
p(s){
s.count--;
if(s.count < 0){
该进程状态设置为阻塞状态；
将该进程插入s.queue这个等待队列末尾
进程、线程让出cpu，操作系统调度选择新的线程、进程来运行；
}
//如果count 不小于0 ,那么继承继续持有cpu，继续运行。
}
v(s){
s.count++;
if(s.count <= 0){
唤醒s.queue这个等待队中等待的一个进程；
将其状态设置为就绪态，并将其插入就绪队列。
}
//如果count > 0，继续持有cpu，继续运行。
}
如何解决互斥和同步的问题？
同步机制-管程
- PV操作由程序员控制容易出错，提供更方便的并发处理操作。
- 由关于共享资源的数据结构以及在其上操作的一组过程组成
- 进程只能通过调用管程中的过程来间接地访问管程中的数据结构。
- 有标示以区分
如何解决互斥和同步问题
- 互斥问题：
1 管程是互斥进入（为了保证管程中数据结构的数据完整性）
2 管程的互斥性是由编译器负责保证的。 - 同步问题
1 管程中设置条件变量，等待/唤醒操作，以解决同步问题。
1.1 条件变量
1.2 等待操作:可以让进程、线程在条件变量上等待（此时，应先释放管程的使用权，不然别其它线程、进程拿不到使用权）；
1.3 发信号操作:也可以通过发送信号将等待在条件变量上的进程、线程唤醒。
管程的大麻烦
image.png
HOARE管程
Q等待
Q被放置到条件变量等待队列中。
P唤醒Q P等待Q执行;
1.Q在条件变量队列中被移除唤醒，
2.P被放置到紧急等待队列中，
3.优先级 紧急等待队列 > 入口等待队列
缺点：两次进程、线程切换
P唤醒Q，P：活动，Q：等待
P等待Q, P: 休眠，Q:激活；Q执行完，P激活。
image.png
image.png
条件变量的实现
- 在管程内部声明和使用
- 对条件变量执行wait和signal操作
wait(c)操作：
- 如果紧急等待队列非空，则唤醒第一个等待者（不施放管程的互斥权，入口等待队列的优先级低，不让执行）；
- 否则释放管程的互斥权
- 执行此操作的进程进入C链末端
signal(c)操作：
c:链为空，则相当于空操作，执行此操作的进程继续执行；否则唤醒第一个等待着，执行此操作的进程进入紧急等待队列末尾。
管程的实现
实现途径：
- 直接构造：语言中自带管程
- 间接构造： 用某种已经实现的同步机制去构造（比如用信号量和PV操作来构造管程）
MESA管程
image.png
-
notify强调了不进行进程/线程切换，发信号的进程/线程继续执行。
-
notify的结果：位于条件变量等待队列头部（第一个wait）的进程在将来合适的时候，且当处理器可用时恢复执行，即不是notify后，立即执行。
-
不能保证在它执行前，条件变量内容没变(1.可能其他的进程进入管程,修改了条件,2notify()方法 到 到线程退出前这区间的代码修改了条件)，因此这个进程必须重新检查条件。用while循环取代if
-
导致对条件变量至少多一次额外的检测，但不再有额外的进程切换；并且对等待进程在notify之后何时运行没有任何限制。
-
对notify改进
1.wait(long timeout);给每个条件原语关联一个监视计时器，无论是否被通知，一个等待时间超时的进程都可以被设置为就绪状态；当该进程被调度执行时，会再次检查相关的条件，如果满足则继续执行。
3.超时可以防止这种情况，当某些进程/线程 在notify之前就挂掉，等待该条件的进程/线程会处于饥饿状态，永远的等下去； -
引入broadcast:使所有在该条件上等待的进程都被释放并进入就绪队列。
- 当不知道多少进程被激活时候，这种方式非常方便。
- 无法判准确判读按激活那个进程/线程，也可以使用广播。
CAS
CAS(Compare and swap )：比较并交换
白话说是 ，如果你是nn的情况下（比较），那么我才要把你更新成mm（交换）；如果..那么.. 对应 and；所以是比较并交换。
JUC里的AtomicInteger,AtomicBoolean,AtomicLong等内部都用CAS操作来实现原子操作的功能。
ABA
ABA是一种现象，即从A变为B，又从B变为A，如果第一次看到第一个A，第二次看到第二个A, 两个A都是A，好像没有变化，但是其实漏掉中间状态B。如果我们的程序要求区分第一个A和第二个A，即认为两个A不同，且能区别，那只能通过附加的版本信息来标识区分。举个例子昨天的你和今天的你 都是你 ，但是又不是相同的你，如何区分两个你呢，比如今天的你是xx年xx月xx日的你，那么昨天的你就是xx年xx月mm日的你，附加上版本信息（这里用了日期）。
数据库的乐观锁，一般也都是采用加上一个Version字段，不但目标值要相同，版本也要相同。
JUC中的AtomicStampedReference，就是提供引用+stamp（版本）的方式来增强CAS的实现，我们可以借助它来避免ABA问题
自旋
while(xxx){
//获取最新的值
currentValue = get();
// cas操作成功了，就退出；
if(true == CAS(... , currentValue,destValue)){
break;
}
//cas操作不成功，继续循环。这个循环的线程中不会主动的释放CPU的使用权。
}
公平锁 && 非公平锁
多个线程都申请持有锁，锁同一时刻只能被一个线程持有；
当持有锁的线程使用完毕，释放锁之后，其他线程开始抢占锁，其中一个线程拿到锁之后，其他线程等待锁释放后再争夺。
- 公平锁 ： 申请抢占锁的线程排队，当锁被释放后，先申请的将先得到锁；缺点，os激活线程是随机的，如果激活的不是队列头一个，就得放弃本次激活的线程的使用，再次执行线程调度。直到激活的线程是等待队列头的线程。
- 非公平锁：当锁被释放后，哪个线程持有锁不遵守申请的顺序，而根据os对线程的调度的结果，哪个线程被优先唤醒，哪个线程就持有锁。
- 公平锁的缺点：等待队列头的线程可能要经历n次线程调度才能被唤醒；这n次线程调度用时多久不确定。
