背景概述
当多线程同时读写一个变量时，实际执行结果容易和预期不一致。
因此我们引入一些概念，采取相关保障线程安全的手段。
数据同步
Synchronization
并不是说线程同时运行，而是让线程按照一定的顺序执行，使得最后的数据能达到同步。
- 「操作 A 应在 B 之前执行」，「操作 C 必须在 A 和 B 都完成之后才能执行」
- 可以理解为它注重实现对资源的有序访问
互斥访问
Mutual Exclusion
系统中的某些资源虽然可以提供给多个进程（线程）使用，但同一时间段只允许一个访问。
- 「操作 A 和 B 不能在同一时刻执行」
临界区
为了访问共享资源而存在
进入区 (entry section) 用来检测当前进程是否可以进入临界区，如果可以进入，则设置相应"正在访问临界区"标志，如果不可进入，（通过一些机制）进程 / 线程可以选择不同的等待方式
忙等
Busy Waiting
已有进程处在临界区内，外面某个正在等待的线程不断测试某个变量尝试进入，消耗着 CPU资源，可能还会导致进程优先级反转（Priority inversion，高优先级任务被低优先级任务所阻塞）
有限等待
Bounded Waiting
等待资源时会设定一个最大等待时间或等待次数的限制，线程会定期检查资源是否可用，并在达到上限后放弃等待，继续执行其他操作。
可以理解为是一种“进展” (progress) 操作，要求系统在合理的时间内能够向前推进并执行必要的操作，即没有线程可以无限期地阻止其他线程进入临界区。
软件解决
Peterson 算法
用于仅有两个进程或线程之间的互斥访问问题
初步尝试
指的是自身的线程， 指的是另一个线程
But Lockstep Execution (锁步执行)
每个步骤的执行需要等待所有处理单元都完成上一个步骤。只有当所有处理单元都完成当前步骤后，才能继续执行下一个步骤。能确保同步执行，但处理速度太慢。
不满足“空闲则入”
- 假设
turn = 0时， 不需要访问临界区，但线程 想执行。由于turn不等于 ，则 会进入循环等待状态，直到它变为1
改进 Using Two Bowls
“bowl” 通常用来表示一个共享资源区域，它可以是一个变量、缓冲区、队列等数据结构，用于在多个线程或进程之间进行数据交换或共享信息。
类似于大家围坐在一起共享一只碗里的食物，每个人可以从碗中取出或放入食物。类比到并发编程中，多个进程或线程可以访问或修改共享资源。
But is susceptible to deadlock
假设线程 和 同时执行，并且两个线程都执行到了
flag = true ，即 flag[j] 和 flag[i] 都为 true，此时，两个线程都想要进入临界区，两个线程将陷入互相等待对方释放标志位的情况，导致死锁。结合方案
- 初始化标志位和选择变量：将两个线程的标志位
flag都设置为 false，将选择变量turn设置为 0 或 1，表示哪个线程有权进入临界区。
- 进入临界区：线程将自己的
flag置为 true，然后将turn置为对方线程的标识（0 或 1）。
- 检查对方线程：线程检查对方线程的标志位和选择变量。如果对方线程正在访问临界区（
flag = true），或者轮到对方线程进入临界区（turn为对方线程的标识），则当前线程进入等待状态。
- 退出临界区：线程执行完临界区的代码后，将自己的标志位置为 false。
Bakery 算法
硬件支持
屏蔽硬件中断
Disabling Interrupts (Pre-emption)
进入临界区后禁止所有中断，处理器无法响应外部中断请求，没有上下文切换，没有并发。
缺点
- 有风险和不可预测性，导致系统响应性下降
- 整个系统都会为此停下来
- 可能导致其他线程处于饥饿状态
- 无法限制响应中断所需的时间
禁用中断后，线程无法被停止
- 非可移植性，不适合多核处理器
禁用硬件中断的能力在不同的处理器架构和操作系统之间可能存在差异
（基于软件也同理有这个限制）
在多处理器系统中，共享的数据结构可能存储在每个处理器的缓存或寄存器中，因此当一个线程修改其缓存副本时，其他在该时间附近读取数据的线程可能会从各自的副本中读取过期的值。修改可能不会立即对其他处理器可见。这意味着可能无法保持互斥。
原子操作指令
抽象结构
锁
锁（名词）本质上是一个（内存）变量 / 标志 ，保存了“锁”（动词）在某一时刻的信息。
事实上，这个变量可以用户程序自定义，只要满足标准的都可以称为锁。
但是在软件层面，我们经常把它直接抽象成一个特定的同步原语 (Synchronizing Primitive / Object) Lock / Mutex (互斥锁，互斥量)，方便操作系统管理（底层本质是调用原子操作指令）
- A lock is specific to the AppDomain, while Mutex to the Operating System allowing you to perform inter-process locking and synchronization
它有两个基本操作
- 锁定：当一个线程想要进入临界区访问共享资源时，它首先尝试获取一个锁。如果锁当前是未锁定状态，则该线程获得锁，并进入临界区执行操作。如果锁已经被其他线程锁定，那么当前线程将被阻塞，直到锁被解锁。
- 解锁：当一个线程完成了对共享资源的访问，它释放锁，使其他线程获取锁并进入临界区。
自旋锁
一种基于忙等待的锁，不断检查锁的状态，直到获取到锁为止。
Spinlock based on the use of indivisible instructions such as:
Test-and-Set
Swap
局限性
- 硬件操作指令的执行效率低
- 无法提供对进展和有限等待的保证
It could spend its time repeatedly reevaluating the lock condition.
信号量
Semaphore，表示资源的数量，对应的变量是一个整型
sem主要操作
- ：Wait and Signal，等待操作。当一个线程或进程需要访问某个共享资源时，它会执行 P 操作。如果信号量计数器的值大于零，则将计数器的值减一，表示一个资源被占用。如果计数器的值为零，那么线程或进程将被阻塞，等待资源的释放。
- P 来源荷兰语 "Proberen" (to attempt)
- ：Acquire and Release，释放操作。当一个线程或进程完成对共享资源的访问时，它会执行 V 操作，将计数器的值加一，表示释放了一个资源。同时，如果有其他线程或进程正在等待该资源，它们中的一个将被唤醒继续执行。
- V 来源荷兰语 "Verhogen" (to increment)
二元信号量
Binary Semaphore
只能取 0 或 1 的值 ➡️ It is used as a mutex locking mechanism
计数信号量
Counting Semaphore（如果只出现 Semaphore 一个单词，默认指这个）
也称为速率限制信号量，通过将计数值设置为最大允许同时进入某一代码区域的线程数（比如 ），实现限制线程数量的功能。在这种情况下， 个线程可以对计数信号量进行递减操作，但第 个线程将被阻塞，直到之前的线程之一释放了信号量。它也可以视为一种常同步通信机制，用于实现线程之间的等待和通知。
为了解决忙等待和公平访问的问题，我们可以提供一个更好的 PV 操作实现
