由于并发访问共享资源时，对共享资源的竞争（程序的正确性依赖于特定的执行顺序）导致错误，操作系统提供同步原语供开发者使用。

互斥锁

01 临界区问题

• 临界区：保证互斥访问的共享资源的代码区域。

1. 互斥访问：同一时刻，至多一个线程可以进入临界区。
2. 有限等待：当一个线程申请进入临界区后，必须在有限时间内获得许可并进入临界区，不能无限等待。
3. 空闲让进：当没有线程执行临界区代码时，必须在申请进入临界区的线程中选择一个，允许其执行代码，保证程序执行的进展。

02 互斥锁的硬件实现：关闭中断

03 互斥锁的软件实现：皮特森算法，解决只有两个线程的情况。

• boolean全局数组flag[]，flag[0]，flag[1]分别代表线程0与线程1是否尝试进入临界区。初始值都为false。
• 全局变量turn，决定最终进入临界区的线程编号。无需初始化，会在线程申请进入临界区时初始化。
• 线程0进入临界区前必须满足：flag[1]==false || turn == 0，否则循环等待。

04 软硬件协同：使用原子操作实现互斥锁。

• 原子操作
  • Compare-And-Swap (CAS)：比较地址addr上的值与期望值expected是否相等，若相等则将地址上的值换为新的new_value，否则不进行置换。cpu对任意地址的修改都会锁总线，以实现原子操作。
  • Fetch-And-Add (FAA)：读取地址addr上的旧值，将其加上add_value后重新存回改地址，最后返回addr上的旧值。
  • Load Link/Store-Conditional(LL/SC)：LL时cpu使用一个专门的监视器记录当前访问的地址，而在SC时，仅当监视的地址没有被其他核修改，才执行存储，否则返回存储失败。
• 互斥锁抽象：
  • CAS自旋锁：利用一个lock变量表示锁状态，0：锁空闲，1：锁占用。加锁时，会确认是否锁空闲，空闲的话加锁，否则循环确认。
    • 缺点：不保证有限等待，不公平。
    • 优点：在竞争程度低时非常高效。
  • FAA牌号自旋锁：FIFO

条件变量

通过使用条件变量接口，一个线程可以停止使用cpu并将自己挂起，当等待条件满足后，其他线程会唤醒使它继续执行。场景：避免线程的循环忙等。必须搭配互斥锁一起使用，用于保护对条件的判断与修改。

信号量

根据剩余资源数量控制不同线程的执行。

读写锁

在多个读操作同时进行时不需要互斥锁。针对读者与写者分别提供不同的加锁解锁操作。

• 读临界区：只能保证读者与写者互斥，允许多个读者同时。
• 写临界区：不允许其他读者或写者进入。
• 读写锁的偏向性：
  • 偏向读者：读者并行度提高，写者延迟。
  • 偏向写者：避免写延迟，读者并行度下降。

RCU Read Copy Update

多读者并行，写者不会阻塞读者。通过订阅/发布机制（保证顺序和原子性，修改链表节点），让写者原子的更新任意大小的数据；

• 宽限期：为了确定何时回收旧资源，宽限期用于描述从写者更新指针到最后一个可能观察到旧数据的读者离开的时间段。读者需要标记自己读临界区的开始与结束点。
• 优势：读者开销更小，不会被阻塞且无需耗时的同步操作。
• 弊端：对于双向链表的订阅/发布机制较难实现，需要等待到所有读者离开临界区后才回收旧数据。

同步带来的问题

01 死锁

• 死锁出现的必要条件：
  1. 互斥访问：保证一个共享资源在同一时间至多允许一个线程访问。
  2. 持有并等待：线程持有一些资源并等待另一些资源。
  3. 资源非抢占：一旦一个资源被持有，除非持有者主动放弃，否则其他竞争者都得不到。
  4. 循环等待：存在一系列线程都得不到资源，形成等待循环。
• 死锁的检测与恢复：
  1. 被动策略：定时检测死锁存在、超时等待检测。
  2. 死锁预防：
     1. 避免互斥访问：如设计代理线程，专门用于管理对共享数据的访问和修改。（不易实现，代理线程多余）
     2. 不允许持有并等待：线程一次性申请所有资源，一旦任意资源不可用则释放所有资源。（造成线程饥饿，资源利用率低）
     3. 允许资源被抢占：允许线程抢占其他线程已占有的资源。（需保证被抢占的线程正确回滚）
     4. 避免循环等待：要求线程必须按照一定顺序获取资源，顺序靠前的线程能获取所有所需资源，避免循环等待。
• 死锁避免算法：让系统在每次分配资源后处于安全状态，否则不分配资源给线程。（银行家算法）

02 活锁

• 锁的竞争者长时间无法获取锁进入临界区。线程没有发生阻塞，而是一直不断尝试获取锁、失败。

03 优先级反转：由于同步导致线程执行顺序违反预设优先级问题。

• 缺点：实时操作系统中，优先级反转会导致高优先级任务阻塞。
• 避免优先级反转
  1. 不可抢占临界区协议：仍然阻塞优先级更高的线程。
  2. 优先级继承协议：当高优先级线程等待锁时，会使锁的持有者继承其优先级，从而避免该锁的临界区被低优先级任务打断。
  3. 优先级置顶协议：将获取锁的线程优先级置为可能竞争该锁线程中的最高优先级。