竞争条件：多个进程并发访问和操作同一数据，且执行结果与特定访问顺序有关
防止竞争条件：确保一次只有一个进程可以操作变量，即进程需要进行同步
临界区问题
在临界区内进程可能修改公共变量等，当一个进程在临界区内执行时，其他进程不允许进入该临界区执行。
进程的一般结构
临界区问题的解决方案要满足三条要求
-
互斥
如果Pi在临界区执行，则其他进程不能在其中执行
-
进步
如果没有进程在临界区执行，并且有进程要进入临界区，那么只有那些不在剩余区的进程可以参加选择，并且这种选择不能无限推迟
-
有限等待
从一个进程要求进入临界区到这个请求被允许，其他进程不能无休止地进入其临界区
Peterson解决方案
适合于两个进程Pi、Pj交错执行临界区与剩余区。
int turn; // 哪个进程可以进入临界区
boolean flag[2]; // 哪个进程准备进入临界区
进入过程：
- Pi设置
flag[i]=true，turn=j，表示自己已经准备好，并且如果Pj要进入可以进入 - 考虑双方同时设置的情况，
turn最终只会有一个值，只有一个进程真正进入临界区 
while (flag[j] && turn==j);当对方准备好且轮到对方时，等待，直到对方释放
硬件同步
从硬件角度出发解决同步问题。
单处理器环境
对于单处理器环境，在修改共享变量时只要禁止中断，就能解决临界区问题。
多处理器环境
对于多处理器环境，这种解决方案不可行，因为耗时长、系统效率降低、影响时钟更新中断。给出下面两个方案：
test_and_set
原子指令。设该值为真，并返回原值。
原理：
- lock为false，没有被锁住，则while停止，lock被置true，该进程进入临界区
- 其他进程看到lock是true，无限while
- 直到该进程到lock=false释放lock
- 某个进程重复第一步
compare_and_swap
原子指令。仅当值等于期待值时赋新值，返回原值。
实现同步的原理较为复杂，不作讨论。
问题
test_and_set 和 compare_and_swap 能保证互斥，但不能满足有限等待，需要做一定的修改。
互斥锁
基于硬件的解决方案太复杂，并且不能由程序员直接使用。互斥锁（mutex lock）更简单。
每个互斥锁有一个available变量 ，提供acquire()和release()方法用于获取和释放锁。这两个方法的执行必须是原子的。
互斥锁有多种实现。一种需要忙等待的实现如下。这种互斥锁也被称为自旋锁。
acquire() {
while (!available); // busy wait
available = false;
}
-
自旋锁的优点：当进程等待锁时没有上下文切换，因此等待时间短时，性能更好
-
自旋锁的缺点：多道程序系统中（多个进程共享CPU），忙等待浪费CPU周期
信号量
信号量S是一个整型变量，表征某个资源的可用量。提供两个原子方法：wait()和signal()。
wait(S) { // 等待并申请
while (S <= 0); // busy wait
S--;
}
signal(S) { // 释放
S++;
}
上面的实现方案仍有忙等待问题，但信号量是可以解决自旋问题的。当wait()并发现信号量非正时，不是忙等待，而是阻塞自己，把自己放到与信号量相关的等待队列中，并且将进程状态切换为等待状态。当有signal()被调用时，wakeup()等待队列中的某个进程。这时，信号量的功能表现类似于一个外设。
相关问题
- 信号量的值可以为负，其绝对值就是等待该信号量的进程数
- 每个信号量都有一个等待队列
- wait()和signal()操作本身也是临界区操作，需要硬件实现互斥。多机系统中会导致忙等，但是时间很短
信号量死锁
考虑信号量S=Q=1。P0操作序列wait(S),wait(Q),signal(S),signal(Q)，P1操作序列wait(Q),wait(S),signal(Q),signal(S)。两个signal可能都无法执行，导致死锁。
一组进程处于死锁：组内的每个进程都等待一个事件，而该事件只能由组内的另一个进程产生
饥饿（无限阻塞）
如果对与信号量有关的链表按LIFO顺序增加和删除进程，那么可能发生无限阻塞。
优先级反转
假设有三个进程优先级L<M<H。H需要R，R正被L访问，则H需要等待L用完R。但此时M可以抢占L（尽管M不用资源R），即较低优先级的进程影响了H应该等待多久。
该问题只出现在具有两个以上优先级的系统中。解决时可以采用优先级继承协议，L临时继承H的优先级，防止M抢占，直到L用完资源R时释放优先级。
经典同步问题
有界缓冲问题
第一读者-写者问题
有的进程可能只需要读（读者），而其他进程需要读+写（写者），即要求写者在写入时具有独占访问权。
第一读者-写者问题要求读者不应等待，除非写者已经在使用共享对象。下面的解决方案可能产生饥饿。
有些系统提供读写锁，锁具有两形式：读锁和写锁。多个进程可以并发获得读锁，但只有一个可以获得写锁。
读写锁在：①容易识别哪些进程只读，哪些只写；②读者比写者多，从而并发程度可以弥补锁的开销时最有用。
哲学家就餐问题
五个哲学家坐在圆桌边，桌上有五只筷子。哲学家要么思考，要么进餐。进餐时需要获得左右两根筷子，但一次只能拿起一根筷子。
这可能造成死锁，存在一个哲学家永远不能获得需要的第二只筷子。补救措施有：
- 允许最多四个哲学家坐在桌上
- 只有两根筷子都可用时，哲学家才在临界区一起拿起
- 非对称拿起方案，如单号先左后右，双号先右后左
管程
信号量存在时序错误的可能性。因此提出一种重要的、高级的同步工具，管程（monitor）。
结构
管程结构确保每次只有一个进程在管程内处于活动状态。
- 一组程序员定义的，在管程内互斥的操作
- 一组变量记录管程实例状态
管程 = 锁+条件变量（两种同步机制）
锁：用来互斥，通常由编译器提供；条件变量：控制进程或线程执行顺序。
管程的中心思想是去运行一个在管程中睡觉的线程。
条件变量
condition x, y;条件变量用于表示某一个条件，每个条件都有一个与之关联的队列。
-
x.wait()：挂起调用该句的进程 -
x.signal()：恢复挂起队列中的一个进程Q，如果没有就不产生作用。如果有，则有两种策略：①当前进程等待，Q执行；②当前进程离开管程后Q执行。
哲学家就餐问题的管程解答（无死锁）
采取“只有两根筷子都可用时，哲学家才在临界区一起拿起”策略。
替代方法
-
事务内存
在内存上执行事务操作（原子的，可提交或回滚）
-
OpenMP
-
函数式编程语言
不允许可变状态，不用关心竞争条件和死锁等问题