一. 同步与互斥基本概念
多道程序环境下，进程并发执行，为了协调不同进程之间的相互制约关系，引入** 进程同步** 的概念。
如：计算 1+1 × 3，假设系统产生 加法进程 和 乘法进程 ，由于进程异步性，可能发生先计算加法后计算乘法；
因此需要制定一种机制 约束加法进程在乘法进程执行结束后发生。
临界资源
- 临界资源：同一时刻仅允许一个进程使用的资源。
- 如：许多物理设备（打印机，键盘等）；被多个进程共享的变量，数据等。
临界区与临界资源：
- **临界区：**对临界资源的访问，必须互斥进行，每个进程中，访问临界资源的代码段 称为临界区。
- 访问临界资源的过程：
- 进入区：检查是否可以进入临界区。如果可以进入，将设置访问临界区标志，阻止其他进程进入。
- 临界区：访问临界资源的那段代码，又称临界段。
- 退出区：清除访问临界区的标志。
- 剩余区：代码中剩余的部分。
同步
- 亦称直接制约关系，是指为完成某种任务而建立的≥2个进程，由于需要协调它们的运行次序而等待、传递信息产生的制约关系。源于进程之间的合作
- 例如：进程A通过单缓冲向进程B提供数据。
- 缓存区empty：B进程阻塞，A进程送入数据 唤醒进程B。
- 缓冲区full： A进程被阻塞，进程B取走数 唤醒进程A。
互斥
- 亦称间接制约关系。一个进程A进入临界区使用临界资源时，另一个进程必须等待。进程A退出临界区后，另一进程才允许访问临界资源。
- 例如：仅有一台打印机的系统中，两个进程A和B。
- 若进程A需要打印，但是打印机已经被分配给进程B，则进程A阻塞。
- 进程B释放打印机后，唤醒进程A，从阻塞态变为就绪态。
实现临界区互斥遵循的准则：
为了禁止两个进程同时进入临界区。
- 空闲让进：临界区空闲，让一个请求进程进入。
- 忙则等待：已有进程进入临界区，其他请求进程必须等待。
- 有限等待：请求的进程，保证在有限时间进入临界区，防止进程无限等待。
- 让权等待（原则上，非必须）：进程无法进入临界区，立即释放处理机，防止进程忙等待。
二. 临界区互斥实现方法
2.1 软件实现
进入区设置并检查访问临界区标志，已有进程进入临界区，则通过在进入区循环检查进行等待，进程离开后在退出区修改标记。
算法一：单标志法
设置一个公用整形变量 turn，指示允许进入临界区的进程标号。turn=N，表示允许进程 P(N) 进入临界区；进程退出临界区时，转移临界区使用权，如进程 P(i) 退出临界区，将 turn 置为 j。（i ≠ j）
特点：
- 每次只允许一个进程进入临界区。
- 两个进程必须交替进入临界区，若只有两个进程，进程 P(B) 不再进入临界区，则进程 P(A) 从临界区退出后，由于修改后 turn = B，（此时临界区空闲） 进程 P(A) 将不能再次进入临界区。【违背了“空闲让进”原则】
算法二：双标志先检查法
设置布尔型数组 flag[2] ,标记各个进程想进入临界区的意愿，flag[i] = true 表示进程 P(i) 想要进入临界区【i=0 或 1】
- P(i)进入临界区之前，先检查对方是否想进入临界区；
- 若 flag[ 1-i ] = true，则 P(i) 进程等待，否则设置 flag[ i ] = true，然后 进入临界区。
- P(i) 退出临界区时，设置 flag[ i ] = false。
- 优点：不需要交替进入，可以连续使用。
- 缺点：可能存在 P(0) 和 P(1)同时进入临界区。
- 上图中，按照 ①⑤②⑥③⑦ 执行的时候【即检查对方标记后和设置自己的标记前 可能发生进程切换】，出现两个进程都通过检查的情况，同时进入临界区。（违背“忙则等待”原则）。原因在于 检查和设置操作 不是一气呵成的。
算法三：双标志后检查法
基于算法二的机制，采用先设置后检查法，以避免算法二导致量两个进程同时进入临界区的问题。
- P(i)进入临界区之前，先设置 flag[ i ] = true， 再检查对方是否想进入临界区；
- 若 flag[ 1-i ] = true，则 P(i) 进程等待，否则直接进入临界区。
- P(i) 退出临界区时，设置 flag[ i ] = false。
- 优点：避免了两个进程同时进入临界区的问题。
- 缺点：上图中，按照 ①⑤②⑥… 执行的时候，出现两个进程 都想要进入临界区 情况，结果都无法进入 临界区。（违背“空闲让进”原则）。
各个进程长期无法访问临界区导致“饥饿”现象。（违背“有限等待”原则）
算法四：Peterson算法
结合算法一和算法三思想，**利用 flag[ ] 解决互斥访问，利用“turn”**解决“饥饿”问题。
- 进程进入临界区之前，先设置 flag 标志，再设置** turn 标志**【turn 标志设置为对方的，表示对方优先进入。】；
- 接着 同时检查对方的 flag 和 turn 标志，以保证同时要求进入时候，只允许一个进入。
若检查时候出现冲突：都想要进入，则最后设置 turn 标志【发出“谦让”】的进程等待。最终 turn 指示进入临界区的进程标号。
- 优点：P[j] 退出后，如果 P[ i ] 不想进入临界区，则设置 flag[ i ] = false（P[ i ] 不会陷入 while 循环），遵循了“空闲等待”，“忙则等待”，“有限等待”。
- 缺点：未遵循“让权等待”原则，依然不够好
2.2 硬件实现
- 计算机提供特殊硬件指令，允许对一个字的内容进行检测和修正，或交换两个字的内容。
中断屏蔽方法
硬件指令方法——TestAndSet 指令
硬件指令方法——Swap 指令
** 总结 **
三. 互斥锁
