目录

1. 基于软件层面(Peterson's Solution)

Peterson's Solution 满足三个要求:

好处:

缺点

2. 基于硬件层面

        1. Disabling Interrupts (禁用中断)

概念解释：

代码框架：

        要求：

        禁用中断的好处与问题：

2. Test and Set Lock (测试并设置锁, TSL) 

        第一部分 - 概述

        第二部分 - 锁的工作机制

        Test-and-Set 锁的工作机制

c. CAS（Compare_and_Swap）硬件方法

CAS的定义

CAS的要求：

​​​​​​​​​​​​​​​​​CAS的优点：

CAS的缺点：

1. 抢占式内核（Preemptive kernels）

2. 非抢占式内核（Non-preemptive kernels）

---

1. 基于软件层面(Peterson's Solution)

do {
    flag[i] = true;        // i wants to enter critical section
    turn = j;              // allow j to access first

    while (flag[j] && turn == j)
        ; // busy wait

    // CRITICAL SECTION
    flag[i] = false;

    // REMAINDER SECTION
} while (true);

do {
    flag[j] = true;        // j wants to enter critical section
    turn = i;              // allow i to access first

    while (flag[i] && turn == i)
        ; // busy wait

    // CRITICAL SECTION
    flag[j] = false;

    // REMAINDER SECTION
} while (true);

• flag[2] 数组：每个进程都有一个布尔值来表示它是否想要进入临界区。
  • flag[0] 表示 Process P0 是否想要进入临界区。
  • flag[1] 表示 Process P1 是否想要进入临界区。
• turn 变量：决定哪个进程可以进入临界区。它可以是 0（P0的轮次）或 1（P1的轮次），只有没有轮到的进程才会等待。

假设有两个进程 i 和 j：

• 当 i 想要进入临界区时，它会设置 flag[i] = true，表示自己准备进入，并设置 turn = j，表示优先让 Process j 进入。

• 如果此时 Process j 没有想要进入临界区（即 flag[j] = false），那么 Process i 会进入临界区。
• 如果 Process j 也想进入临界区，Process i 会根据 turn 的值决定自己是忙等待还是进入临界区。

当 Process i 完成临界区任务后，它会将 flag[i] 设置为 false，释放临界区，允许 Process j 进入。

总结

• flag：用来表示进程是否想要进入临界区。
• turn：决定哪个进程可以优先进入。
• 互斥机制：通过轮流方式解决临界区访问冲突，确保不会同时有多个进程进入临界区。

Peterson's Solution 满足三个要求:

1. Mutual Exclusion（互斥）：
   • 在任意时刻，只有一个进程可以进入临界区。这个互斥性是解决临界区问题的核心要求之一，防止多个进程同时修改共享资源导致数据不一致。
2. Progress（进展）：
   • 理论上，Peterson 算法保证了进展，即不会有进程无限等待。每个进程都有机会进入临界区。然而，在实际操作中，由于调度行为等因素，进程的进展可能会被延迟，或者在某些情况下一个进程可能似乎“饥饿”了（无法及时进入临界区）。
3. Bounded Waiting（有界等待）：
   • Peterson's Solution 理论上保证了有限等待的特性，这意味着每个进程都有机会在有限时间内进入临界区。但在实际应用中，有时可能会发生一个进程被系统偏爱，而另一个进程会因为饥饿问题而无法及时进入临界区。

好处:

1. 易于理解和实现：
   • Peterson 的算法在处理两个进程的临界区问题时非常简单易懂，并且实现起来也不复杂。
2. 不需要特殊硬件：
   • 与一些依赖于硬件支持的算法不同，Peterson's Solution 不需要依赖硬件级的原子操作或者禁用中断。它只使用简单的共享变量，通过软件级别的方式实现同步。

缺点

1. Limited to two processes (仅限于两个进程)

• 扩展性差：Peterson's Solution 仅支持两个进程同时操作，这意味着无法处理多个进程。这在现代操作系统中是一个严重的局限，因为多个进程常常需要同时访问共享资源。
  • "Limited to two processes" 表示 Peterson's Solution 只能处理两个进程的互斥问题，无法扩展到多个进程使用。
• 扩展困难：虽然理论上可以通过增加更多的标志位（flag）和更复杂的条件来支持多个进程，但这会导致代码复杂度和错误率增加。
  • flag 是指布尔标志，用来表示进程是否要进入临界区 (Critical Section)。如果多个进程要共享资源，管理这些标志位和调度将变得极其复杂。

2. Busy waiting leads to inefficient use of CPU resources (忙等待导致CPU资源利用低效)

• 忙等待问题：Busy Waiting 是指进程在等待时，不断循环检查条件是否满足，这会消耗大量的 CPU 资源，而这些资源本可以用于其他任务。
  • Busy Waiting 是一种低效的资源管理方法，因为进程在循环中没有做实际有用的工作，只是在不断检查能否进入临界区。
• 资源浪费：由于进程反复检查标志位（flag[] 和 turn），在等待期间未做任何有用的计算，导致了 CPU 资源的浪费。
  • turn 是控制进程轮流进入临界区的变量。在忙等待过程中，CPU 的资源被用来持续检查这些变量是否允许进入临界区。

3. Performance Issues on Modern Architectures (现代架构上的性能问题)

• Cache Coherence Problems (缓存一致性问题)：在多核处理器上，每个核（core）有自己的缓存（Cache），并非所有处理器会立即看到共享变量的变化。Peterson's Solution 假设共享变量的更新能被所有核及时看到，这在现代架构中并不总是成立，可能会导致错误。
  • Cache Coherence (缓存一致性) 问题出现在当处理器各自处理局部缓存时，变量的更新未能及时同步到其他处理器上，导致不同步的访问。
• Memory Model (内存模型问题)：现代处理器会进行诸如指令重排（Instruction Reordering）和乱序执行（Out-of-Order Execution）等优化操作。这些操作会改变代码执行的顺序，破坏 Peterson's Solution 的基本假设，即变量的读写必须严格按顺序进行。
  • 在现代处理器中，指令重排有时会打乱程序执行顺序，导致变量更新的延迟，进而影响 Peterson's Solution 的同步准确性。

4. No fairness or priority mechanism, which may lead to starvation (缺乏公平性或优先级机制，可能导致饥饿问题)

• 缺乏公平性：Peterson's Solution 确保了进程互斥，但它没有保证进程之间的公平竞争。某些进程可能会被系统优先调度，而其他进程长时间得不到执行机会，导致 Starvation (饥饿) 问题。
  • Starvation (饥饿) 是指某个进程由于调度机制的原因，长时间无法获得资源使用权限，从而无法执行。
• 无优先级机制：Peterson's Solution 不能支持不同重要性进程之间的优先级调度。如果一个进程比另一个进程更重要，该算法无法确保重要的进程优先进入临界区。
  • Priority (优先级) 控制指的是，系统应当能够识别进程的重要性，并基于此分配资源。在 Peterson's Solution 中，这种优先级机制不存在。

5. Lack of Deadlock Prevention (缺乏死锁预防)

• 无法预防死锁：Peterson's Solution 确保两个进程不会同时进入临界区（Critical Section），但它不能预防外部资源竞争导致的 Deadlock (死锁)。如果两个进程在等待外部资源（例如文件锁或数据库连接）时，可能会相互阻塞，导致死锁。
  • Deadlock (死锁) 是指两个或多个进程由于互相等待对方释放资源，导致所有进程都无法继续执行。

2. 基于硬件层面

        1. Disabling Interrupts (禁用中断)

1. 概念解释：

   • 当进程进入临界区 (Critical Section) 时，它会禁用中断 (Disable Interrupts)。这样确保在进程执行临界区代码时，不会发生上下文切换 (Context Switch)，时钟中断 (Clock Interrupt)，或其他系统中断。这保证了进程的独占执行，直到它退出临界区。
     • Interrupts (中断) 是操作系统用来暂停当前执行进程并处理紧急任务（如硬件请求）的一种机制。在禁用中断期间，这些请求将无法被处理，确保当前进程独占 CPU 资源。

2. 代码框架：

   

• 逻辑说明：禁用中断 -> 执行临界区代码 -> 重新启用中断 -> 处理剩余代码。
• 这种方法主要确保了临界区中的代码可以独占执行，不会被打断。

要求：

1. 单处理器系统中的应用：
   • 在单处理器系统 (Single-Processor System) 中，禁用中断部分满足了临界区问题的要求，但有一定的局限性。
2. 优点：
   • Mutual Exclusion (互斥)：禁用中断可以保证互斥性，只有当前进程可以进入临界区，因为没有其他进程有机会获得 CPU 的控制权。
3. 缺点：
   • Progress (进展)：整个系统的性能可能受损，尤其是其他进程（例如，依赖中断的 I/O 绑定进程）在等待中断被启用时无法执行。这会影响系统的整体进程调度。
   • Bounded Waiting (有界等待)：禁用中断不保证有界等待。如果一个进程长时间禁用中断，其他等待进入临界区或依赖中断的进程可能会被无限期延迟。

禁用中断的好处与问题：

1. Benefits (好处)：
   • Exclusive access (独占访问)：一旦禁用中断，CPU 不会切换到其他进程，允许当前进程在没有中断的情况下执行临界区操作。
     • 无中断：确保了进程的独占性，不会受到其他进程或事件的干扰。
   • Simplicity (简单性)：禁用中断的方法简单有效，尤其在单处理器系统中，容易实现互斥。
2. Drawbacks (问题)：
   • Affects system responsiveness (影响系统响应能力)：禁用中断会阻止系统及时处理重要任务，例如 I/O 或外部事件，这可能导致系统反应迟缓。
     • 响应问题：进程长时间占用 CPU，会让系统无法及时处理来自外部的硬件请求或用户输入。
   • Not scalable (无法扩展到多处理器系统)：此方法不适合多处理器系统。在多处理器系统中，禁用一个处理器的中断并不能防止其他处理器上的进程进入临界区或访问共享资源。
     • 多核问题：只禁用一个 CPU 的中断无法阻止其他 CPU 的进程进行操作，这在多处理器环境下导致禁用中断方法的无效性。

2. Test and Set Lock (测试并设置锁, TSL) 

第一部分 - 概述

1. Lock Variable (锁变量)：
   • 这是一个共享的锁变量（通常是一个比特位或内存位置），用于指示临界区 (Critical Section) 是否空闲（值为 0 表示解锁 "unlocked"）或被占用（值为 1 表示锁定 "locked"）。
   • 锁的作用：防止多个进程/线程同时进入临界区。
2. Test-and-Set Instruction (测试并设置指令)：
   • 硬件支持的原子操作 (Atomic Operation)，称为 test-and-set，确保操作不可分割，避免其他进程/线程在操作过程中干扰。具体步骤如下：
     • 检查锁的当前值。
     • 如果锁是空闲的（值为 0），则将其设置为锁定（值为 1），同时返回旧值。
     • 如果操作是原子性的，其他进程/线程不能在操作未完成前看到中间状态或干扰操作。

示例代码 (图示中)：

第二部分 - 锁的工作机制

1. 流程：
   • 如果进程成功将锁设置为 1，则可以进入临界区。其他进程/线程将被阻止，因为锁现在是锁定状态。
   • 当进程完成临界区的代码后，它会将锁重置为 0，允许其他进程/线程进入。
2. 锁的初始值是 0 (false)：
   • 在锁未被占用时，值为 0，表示解锁状态，进程可以进入临界区。
   • 当锁定时，锁的值变为 1，表示当前临界区正在被占用，其他进程必须等待。
3. 代码示例 (图示中的 P1 和 P2)：
   • 两个进程 P1 和 P2 通过检查锁变量，进入临界区并执行代码。只有当锁值为 0 时，进程才能进入临界区，设置锁为 1 并阻止其他进程进入。

 

Test-and-Set 锁的工作机制

1. 锁的初始状态：
   • 当程序启动时，锁的初始值通常设置为 0，表示未锁定状态（解锁）。这意味着临界区是空闲的，任何进程/线程都可以尝试进入。
2. 进程如何使用锁：
   • 假设有两个进程 P1 和 P2，它们都想进入临界区执行某些操作。
   • 它们首先使用 test_and_set() 函数检查锁的状态，并根据返回值决定是否可以进入临界区。
3. test_and_set() 函数：
   • test_and_set() 函数是一个原子操作，意味着它在执行过程中不可被其他进程/线程打断。
   • test_and_set() 做两件事：
     1. 检查锁的当前值：它会检查当前锁变量的值，如果锁的值是 0，表示解锁状态，进程可以进入临界区。
     2. 设置锁：如果锁是空闲的（值为 0），它会将锁的值设置为 1，表示锁定状态。这个过程是原子的，意味着只有一个进程能成功将锁设置为 1。
4. 如何保证互斥 (Mutual Exclusion)：
   • 只有一个进程可以成功进入临界区：
     • 当第一个进程（例如 P1）调用 test_and_set() 时，它会发现锁的值是 0，表示未被锁定。于是，P1 会将锁设置为 1，并成功进入临界区执行任务。
     • 如果另一个进程（P2）在 P1 已经锁定的情况下也调用 test_and_set()，P2 会发现锁的值已经是 1，这意味着临界区被锁定，因此 P2 不能进入，它会进入等待状态。
     • P2 会持续检查锁变量，直到锁的值再次变为 0（即解锁状态）。
5. 释放锁：
   • 当 P1 完成它的临界区任务后，它会将锁的值重置为 0，这就表示解锁，允许其他等待的进程（如 P2）进入临界区。
6. 总结锁的状态变化：
   • 初始状态：锁的值是 0，表示临界区空闲。
   • 第一个进程进入：第一个调用 test_and_set() 的进程会将锁值设置为 1，锁定临界区。
   • 其他进程等待：在锁定期间，其他进程调用 test_and_set() 时会发现锁已经是 1，因此它们必须等待。
   • 进程完成任务后释放锁：进程完成任务后，会将锁重置为 0，表示解锁，其他进程可以再次尝试进入临界区。

1. Test-and-Set锁的要求

• 互斥（Mutual Exclusion）：
  • Test-and-Set锁保证同一时刻只有一个进程可以进入临界区，从而满足互斥要求。
• 进展（Progress）：
  • 理论上，进展是可以保证的，但在实际中，忙等待（busy-waiting）可能导致低效和延迟，特别是在系统负载高的情况下。尽管没有进程被阻塞，但进程可能由于调度或系统负载问题而变得缓慢。
• 有界等待（Bounded Waiting）：
  • Test-and-Set锁并不保证有界等待。忙等待会让进程无限期地在等待锁定过程中徘徊，导致某些进程可能被其他进程长时间阻塞，从而引发饥饿问题（starvation）。

2. Test-and-Set锁的优点

• 简单高效：
  • Test-and-Set锁很容易实现，并且确保了互斥，使其在需要快速解决问题的场合中非常实用。
• 适用于小临界区：
  • 如果临界区很短，争用锁的情况不严重，那么Test-and-Set锁会显得非常高效。这种情况下，忙等待所消耗的CPU资源相对较少，系统开销较小。

3. Test-and-Set锁的缺点

• 忙等待问题（Spinlock Overhead）：
  • 使用Test-and-Set锁时，进程在等待锁时会持续忙等待，占用CPU资源。特别是当临界区较长或存在大量竞争线程时，忙等待会导致CPU资源浪费，降低系统效率。
• 饥饿风险（Starvation Risk）：
  • Test-and-Set锁不保证所有进程都有机会访问临界区。尤其是在高度竞争的环境中，一些进程可能永远无法获得锁，导致饥饿。
• 扩展性问题（Scalability Issues）：
  • 随着并发进程或线程数量的增加，锁的争用变得更为严重，忙等待的开销也会增加。因此，在高并发环境下，这种锁的效率下降。
• 死锁风险（Deadlock Potential）：
  • 如果Test-and-Set锁使用不当，可能会导致死锁。例如，如果某个进程在持有锁的情况下再次尝试获取锁，它将阻塞自身，从而导致死锁。

总结：

• 互斥可以通过Test-and-Set锁来保证，但这种方法存在明显的缺点，比如忙等待导致资源浪费、饥饿问题和扩展性差。在高并发或临界区较长的情况下，这种锁可能不再适用。
• 需要注意的是，死锁风险必须通过合理的锁管理来避免，这也是Test-and-Set锁需要特别小心的地方。

c. CAS（Compare_and_Swap）硬件方法

1. CAS的定义:

• CAS 是一种硬件支持的 原子操作（atomic operation）。它能够确保在多处理器系统中执行的操作不会被打断。
• 工作原理：
  • 比较：它首先会检查存储在某个内存地址上的值是否与期望值相符。
  • 交换：如果当前值与期望值匹配，它将用新的值替换旧值。
  • 返回：最后，CAS 操作会返回是否执行了替换操作，返回旧值。

1. 代码实现：

• 代码展示了 compare_and_swap() 的实现。CAS 操作将原子地比较并替换锁的值。

• lock 表示锁所在的内存位置。
• expected 是期望的当前值，new_value 是需要设置的新值。

       2. CAS的要求：

• 互斥：由于 CAS 是原子操作，所以它能够确保 互斥（Mutual Exclusion），即一次只有一个进程能进入临界区。
• 进度：CAS可以确保进度，但是如果没有公平性机制（如退避策略或基于队列的CAS策略），可能会出现**忙等待（busy waiting）**问题，导致部分进程一直占用临界区，影响其他进程的进度。
• 有界等待（Bounded Waiting）：CAS 并不能保证有界等待，这意味着一些进程可能会被长时间延迟，因为某些进程反复成功获取锁。

• • ​​​​​​​​​​​​​​​​​​​​​​​​CAS的优点：

• 支持多处理器：CAS 在现代多处理器系统中得到了很好的支持，非常适合大规模、高性能的应用程序。
•  

  • CAS的缺点：

• 忙等待（Spinlock）：如同Test and Set一样，CAS 操作在无法获取锁时会忙等待，导致 CPU 资源浪费，特别是当锁被长时间持有时。
• 没有公平性：CAS 操作不能保证公平性，可能导致某些进程长期无法进入临界区，进而导致**饥饿（Starvation）**问题。

1. 抢占式内核（Preemptive kernels）

• 在抢占式内核中，进程在内核模式下运行时，可以被中断，另一个进程可能会被调度。这意味着：
  • 多个进程可以同时在内核中运行，但这会导致潜在的竞争条件（race conditions）。竞争条件是指多个进程并发地访问共享资源时，由于访问顺序的不确定性，可能导致数据不一致或错误。
• 需要同步机制来避免这些竞争条件，常用的同步方法包括：
  • 锁（locks）
  • 互斥锁（mutexes）
  • 原子操作（atomic operations）
• 例子：Windows 和 Linux 都使用抢占式内核。这些系统需要额外的同步机制来确保内核中的数据一致性。

2. 非抢占式内核（Non-preemptive kernels）

• 在非抢占式内核中，进程一旦进入内核模式，它将继续运行，直到其完成、阻塞或主动让出CPU为止。在此期间，其他进程不会中断它的执行。
  • 因此，在这种内核模式下，没有竞争条件，因为同一时刻只会有一个进程在内核中活动。
• 由于没有多个进程并发执行，因此不需要复杂的同步机制，这简化了系统设计。
• 例子：老旧或简单的操作系统，如早期的MS-DOS或一些嵌入式系统（embedded systems），通常使用非抢占式内核。

总结：

• 抢占式内核允许多个进程同时在内核模式下运行，但需要复杂的同步机制来处理共享数据。
• 非抢占式内核确保只有一个进程在内核中执行，因此不需要同步机制，但可能导致效率低下，因为无法在进程阻塞时进行上下文切换。