同步互斥
一. 背景
临界资源：一次仅允许一个进程独自占有使用的不可剥夺资源。
临界区：进程访问临界资源的那一段代码。
互斥：当一个进程正在临界区中访问临界资源时，其他进程不能进入临界区。
同步：合作的并发进程需要按先后次序执行。例如：一个进程的执行依赖于合作进程的消息或信号。当一个进程没有得到来自合作进程的消息或信号时需阻塞等待，直到消息或信号到达才唤醒。
并发进程可能出现间歇性发生的错误，随着外界环境的变化可能会发生错误。
并发示例：理想情况下，进程执行工作是将next_pid写给寄存器，读寄存器赋值给new_pid，然后寄存器加1赋值给next_pid。两个进程先后执行，不会中间中断。
四条语句中可能出现切换
并发执行时要保证一些是原子操作，否则会引发一些问题。
二. 现实中的同步问题
前两个方案都是只看最后结果的话，有面包和没有面包有便签时什么都不做，没有面包也没有便签时买面包。因为检查和买面包可能被分开可能出现问题。
一个人检查面包和检查便签之后，在贴便签之前；另一个人也来检查面包和便签发现没有便签，就会买重。（两个进程交替执行时，检查和后续设置可能被分开）
方案一不理想。
后两个方案有面包和没有面包有对方的便签时什么都不做，没有面包也没有对方的便签时买面包。因为检查和买面包可能被分开，会出现问题。
以上都不可取
可能采用设置锁和钥匙，使检查过程（包括留便签）和买面包过程不会被分开
进程之间会出现三种关系：
- 互斥：一个进程占用了资源，其他进程不能使用
- 死锁：多个进程各自占用部分资源，形成循环等待
- 饥饿：其他进程可能轮流占用资源，一个进程一直得不到资源
三. 临界区及同步方法
临界区是我们要保护的代码，任何时刻只允许一个进程执行这段代码，需要互斥的访问。
1.临界区标准的访问模式的约定
进入区：检查是否可进入临界区的一段代码，如可进入，设置相应的“正在访问临界区”标志
临界区：进程中访问临界资源的一段需要互斥执行的代码
退出区：清除“正在访问临界区”标志
剩余区：代码中的其余部分
在临界区之前有进入区，条件检查之后会进入临界区执行，执行之后进入退出区。
2.临界区的访问规则
空闲则入：没有进程在临界区时，任何进程可进入。
忙则等待：有进程在临界区时，其他进程均不能进入临界区。
有限等待：等待进入临界区的进程不能无限等待。
让权等待：不能进入临界区的进程，应释放CPU（如转换到阻塞状态）。
3.临界区的实现方法，保证进程之间可以交替、多次访问临界区资源
（1）禁止中断：禁止中断后，其他进程就无法对当前进程的执行进行打扰。当前进程对临界区资源的访问不会有问题。
（2）软件：共享变量的协调
（3）更高级的抽象方法：有操作系统支持
采用并发级别（允许什么样的并发执行）来比较3种做法的性能。
方法一：禁用硬件中断的同步方法
禁止中断：整个系统由当前进程独占
进入区中会把当前cpu的执行状态保存起来，同时把中断禁止掉。接下来访问临界区，之后在退出区恢复系统状态并使能中断
方法二：基于软件的同步方法
在两个进程（线程）之间，通过共享变量的访问实现进程的同步。
first try:
两个线程共享一个变量，表示允许谁进入临界区
对于线程Ti，变量是i就进入临界区，在退出区把变量改为另一个线程j；变量是j就进不去临界区。
对于线程Tj，变量是j就进入临界区，在退出区把变量改为另一个线程i；变量是i就进不去临界区。
两个线程可交替进入临界区，但不能一个线程进入两次。
second try:
可以满足交替进入或进入两次，但如果while交替判断完，两个进程就同时进入临界区。
third try:
两个都执行贴标签等于1之后，两个线程就都进不去了。
final:
若两个线程都申请进入，flag都为1，两个线程都写turn变量，都写完之后判断，先写turn的标志的线程能进去，后写的线程等着。先写的线程执行完之后flag[先写]变成false，后写的进程就可以进去了。
方法三：更高级的抽象方法
在多线程编程中，为了保证数据操作的一致性，操作系统引入了锁机制，用于保证临界区代码的安全。通过锁机制，能够保证在多核多线程环境中，在某一个时间点上，只能有一个线程进入临界区代码，从而保证临界区中操作数据的一致性。
两个锁操作都是原子的。
当前进程占用这个锁，后续来的处于等待状态。锁释放前，Lock:acquire()内的操作必须执行完其他线程才可以操作，