Sage's Notes

Recent Notes

11 Lock and Condition Variables Implementation

Created at Jan 05, 2025 Last Modified at Nov 24, 2025 7 min read

How to Implement Locks?

11 Lock and Condition Variables Implementation 如何实现锁1 11 Lock and Condition Variables Implementation 如何实现锁2 如何实现原子操作？需要关中断 11 Lock and Condition Variables Implementation 如何实现锁3

“What happens with I/O or other important events?”（I/O或其他重要事件会怎样？）

  • 在禁用中断期间，系统无法响应I/O事件
  • 可能会丢失重要的外部事件
  • 可能导致系统无法及时响应紧急情况

11 Lock and Condition Variables Implementation 如何实现锁4 11 Lock and Condition Variables Implementation 如何实现锁5 比起单纯的全局关中断，这种方式更好，只有在对锁的操作的时候才需要关中断

关中断检查锁的状态，避免中途被修改，保证原子性

提前开中断，不管是哪个位置开，都是存在问题的 11 Lock and Condition Variables Implementation 如何实现锁6 11 Lock and Condition Variables Implementation 如何实现锁7

11 Lock and Condition Variables Implementation 如何实现锁8 thread switch出去的时候会自动打开中断，然后又遇到锁的时候又会关闭中断

多处理器实现锁

多处理器中又应该如何实现呢？ 11 Lock and Condition Variables Implementation 多处理器实现锁1 11 Lock and Condition Variables Implementation 多处理器实现锁2 这三个都是原子操作

自旋锁

11 Lock and Condition Variables Implementation 多线程实现锁3 如果不用test&set，那就无法保证原子性，value值在中途会被改

11 Lock and Condition Variables Implementation 自旋锁的问题1 拿不到锁会一直循环 busy-waiting，如何解决？能否放在等待队列中？

11 Lock and Condition Variables Implementation 更好的自旋锁1 11 Lock and Condition Variables Implementation 更好的自选锁2 将test&set限制到一个地方，只有在获取guard变量的时候才短暂自旋

  • 最小化自旋等待时间
    • 普通自旋锁在整个等待过程中都在循环检查锁状态，持续消耗 CPU
    • 这个实现只在获取 guard 变量时短暂自旋
    • 一旦发现锁被占用，就将线程放入等待队列并切换上下文，而不是继续自旋
  • 两级锁机制
    • 使用 guard 和 value 两个变量来实现锁
    • guard 用于保护对 value 的访问，实现了更细粒度的控制
    • value 表示实际的锁状态
  • 更好的资源利用
    • 不需要持续轮询锁的状态
    • 线程在无法获取锁时会主动让出 CPU
    • 等待的线程被放入队列，而不是消耗 CPU 资源

11 Lock and Condition Variables Implementation 中断开关和test&set锁的对比 中断开关锁和自旋锁非常类似，就是将开关中断换为了自旋锁

自旋锁采用的是全局共享的变量，所以多处理器可以使用

条件变量实现

条件变量这里讲了基础概念

总的来说就是，拿锁，临时释放锁(等待条件满足)，拿锁，唤醒，再释放

11 Lock and Condition Variables Implementation 条件变量实现1 wake返回的时候，需要拿回锁。只有中途调用其他部分的时候，才是释放锁的

11 Lock and Condition Variables Implementation 管程风格 11 Lock and Condition Variables Implementation 管程风格2 11 Lock and Condition Variables Implementation 管程风格3 下面是一个为什么用while的例子解释

11 Lock and Condition Variables Implementation 例子1 11 Lock and Condition Variables Implementation 例子2 这里发现队列是空的，需要等待条件完成才能继续执行，所以会释放锁，切换线程 11 Lock and Condition Variables Implementation 例子3 11 Lock and Condition Variables Implementation 例子4 11 Lock and Condition Variables Implementation 例子5 11 Lock and Condition Variables Implementation 例子6 这里会等待的线程，但只是将Waiting 切换为了Ready，而不会立刻调度过去，需要等待线程2执行完 11 Lock and Condition Variables Implementation 例子7 11 Lock and Condition Variables Implementation 例子8 11 Lock and Condition Variables Implementation 例子9 11 Lock and Condition Variables Implementation 例子10 11 Lock and Condition Variables Implementation 例子11 11 Lock and Condition Variables Implementation 例子12

11 Lock and Condition Variables Implementation 例子13 11 Lock and Condition Variables Implementation 例子14 所以不能是if，如果是if就直接跳出去了 11 Lock and Condition Variables Implementation 例子15 11 Lock and Condition Variables Implementation 例子16 11 Lock and Condition Variables Implementation 例子17

什么时候能用if？

11 Lock and Condition Variables Implementation 什么时候能用if Hoare模式

  1. “Signaler gives up lock, CPU to waiter; waiter runs immediately”
  • 当发出信号的线程（signaler）执行signal()操作时，它会：
    • 立即放弃锁
    • 放弃CPU控制权
    • 直接将这两个资源转交给等待的线程（waiter）
  • 等待线程会立即执行，不需要重新竞争资源
  1. “Waiter gives up lock, processor back to signaler when it exits critical section or if it waits again”
  • 被唤醒的线程（waiter）在以下情况会将锁和CPU还给signaler：
    • 当它退出临界区时
    • 或者当它再次进入等待状态时

图示展示了这个过程：

  • 左侧的signaler获取锁后，执行signal()操作
  • 右侧的waiter之前因为条件不满足而等待
  • signal()操作会直接将锁和CPU传递给waiter
  • waiter执行完后再将控制权还给signaler

这种实现方式的特点：

  1. 更高效：无需额外的调度开销
  2. 更严格：保证被唤醒的线程能立即执行
  3. 实现更复杂：需要保存和恢复多个线程的状态
  4. 不够灵活：强制了线程执行的顺序

一些问题

11 Lock and Condition Variables Implementation 一些问题

  1. “Do lock.Acquire() and lock.Release() always trap into kernel?” （lock.Acquire() 和 lock.Release() 是否总是需要陷入内核？）

答案：不是总需要陷入内核。

  • 如果锁是空闲的，Acquire() 可以直接通过原子操作（如 test&set）获取锁，无需陷入内核
  • 只有在以下情况才需要陷入内核：
    • 获取锁时发现锁被占用，需要将线程放入等待队列
    • 释放锁时需要唤醒等待队列中的线程
  • 这种设计遵循了快速路径优化的原则，只在必要时才进行代价较大的内核操作
  1. “Interrupt handlers must use spinlocks instead of queueing locks. Why?” （为什么中断处理程序必须使用自旋锁而不是排队锁？）

答案：这是因为中断处理程序有几个重要特性：

  • 中断处理程序不能睡眠（如注释所说：“interrupt handlers are not supposed to sleep”）
  • 原因如下：
    1. 如果中断处理程序睡眠，就需要保存和恢复中断上下文，这是很复杂的操作
    2. 中断处理程序本身就是为了快速响应硬件事件，不应该被阻塞
    3. 如果允许睡眠可能会导致死锁（比如等待的资源正好被中断的程序持有）
    4. 中断处理程序通常执行时间很短，用自旋锁更合适
    5. 中断上下文中没有完整的进程上下文，无法进行正常的进程调度

因此：

  • 中断处理程序必须使用自旋锁
  • 自旋锁保证了中断处理程序可以快速完成，不会睡眠
  • 这种设计虽然可能会短暂占用CPU，但符合中断处理的特性要求

Graph View

Backlinks

  • No backlinks found