字数

3654 字

阅读时间

15 分钟

引言

在并发编程中，我们已经学习了如何使用“锁”（Lock）来解决“互斥”（Mutual Exclusion）问题，确保临界区代码在同一时刻只有一个线程执行。然而，互斥只是并发控制中的一个方面。我们经常面临更复杂的场景，线程之间需要相互协作，等待某个条件达成后才能继续执行。这种协作关系，我们称之为“同步”（Synchronization）。本讲义将从一个经典的同步问题——“生产者-消费者问题”入手，揭示初级同步方案的缺陷，并最终引出强大而优雅的同步工具：信号量（Semaphore）。

---

第一章：同步问题的提出与初步探索 🌱

1.1 从互斥到同步：问题的升级 🧐

【重点】 互斥与同步是两个紧密相关但又有所区别的概念：

• 互斥（Mutual Exclusion）：确保多个线程不会同时进入临界区，解决了“竞争”的问题。
• 同步（Synchronization）：指的是两个或多个线程为了完成某个共同任务而进行的协调。一个线程可能需要等待另一个线程，直到某个条件为真时，才能继续执行。它解决了“协作”的问题。

生产者-消费者问题 就是一个典型的同步问题：生产者线程负责生成数据并放入一个共享的缓冲区，而消费者线程则从该缓冲区中取出数据进行处理。这里面既包含互斥（访问缓冲区是临界区），也包含同步（缓冲区满时生产者必须等待，缓冲区空时消费者必须等待）。

1.2 低效的轮询方案：忙等待的陷阱 ⏳

【了解】 一个最直观但效率低下的实现方式是轮询（Polling），也称为忙等待（Busy-Waiting）。

在 send()（生产者）和 receive()（消费者）函数中，我们可以使用一个循环来不断检查缓冲区是否已满或已空。

// 生产者伪代码
send(message msg) {
    acquire(buffer_lock); // 获取锁
    while (in - out == N) { // 当缓冲区满时
        release(buffer_lock); // 释放锁，让消费者有机会消费
        // 循环检查，不做任何事
        acquire(buffer_lock); // 再次获取锁，准备下一轮检查
    }
    // ... 放入数据 ...
    release(buffer_lock);
}

这种做法虽然能保证逻辑正确，但其缺点是致命的：当线程在 while 循环中等待时，它仍然在持续占用 CPU，执行空循环，这极大地浪费了宝贵的处理器资源。

1.3 初级同步原语：sleep() 与 wakeup() 💡

【重点】 为了解决忙等待的问题，操作系统提供了一对更高效的原语：

• sleep(): 将当前线程的状态从“运行态”更改为“阻塞态”（BLOCKED），并将其挂起。该线程将不再占用 CPU，直到被其他线程唤醒。
• wakeup(thread_id): 将 thread_id 指定的线程从“阻塞态”更改为“就绪态”（READY），使其有机会重新被调度执行。

通过这对原语，当缓冲区满或空时，线程可以调用 sleep() 主动放弃 CPU，而不是空转。

1.4 致命缺陷：“丢失的唤醒”问题 (Lost Wakeup) 💥

【核心考点】 尽管 sleep() 和 wakeup() 避免了 CPU 的浪费，但它们引入了一个非常微妙且致命的并发问题——“丢失的唤醒”。

让我们分析以下场景（其时序关系如图 1.1 所示）：

1. 消费者获取锁，检查缓冲区，发现 in == out（缓冲区为空）。
2. 消费者准备调用 sleep() 进入睡眠。但就在它调用 sleep() 之前，发生了一次上下文切换，操作系统暂停了消费者，开始执行生产者。
3. 生产者开始运行。它获取锁，向缓冲区放入一个数据，然后调用 wakeup(consumerThread) 试图唤醒消费者。
4. 问题发生点：此时消费者还没有真正进入睡眠状态，所以这次 wakeup 调用就像对一个清醒的人说“起床了”，是无效的，这个唤醒信号就此丢失了。
5. 生产者继续执行，最终释放锁。
6. 消费者被重新调度执行。它从上次中断的地方继续，执行 sleep()，因为它认为自己应该等待，于是进入了永久的睡眠，再也无法被唤醒。 ![[Pic/Pasted image 20251015082124.png]] [图 1.1：消费者永久睡眠问题时序图]

为了解决这个问题，我们需要一种更强大的同步原语，它必须能够“记住”发生的唤醒事件。

---

第二章：信号量——更强大的同步工具 🛠️

2.1 信号量的核心思想：资源计数器 💡

【重点】 信号量（由 Edsger Dijkstra 在 1965 年提出）的核心思想是维护一个“资源计数器”。

想象一个餐厅门口的服务员，他手里有一个计数器，记录着空闲餐桌的数量。

• 每当有客人（线程）想就餐（请求资源），服务员就检查计数器。
• 如果计数器大于 0，就减一，并安排客人入座。
• 如果计数器等于 0，客人就需要排队等待（线程阻塞）。
• 每当有客人用餐完毕离开，服务员就把计数器加一，并通知排在队首的客人可以入座了（唤醒阻塞的线程）。

这个计数器就是信号量。它不仅记录了资源的数量，还隐含地维护了一个等待队列。

2.2 信号量的定义与原子操作 📖

信号量本质上是一个特殊的整数变量，只能通过两个原子操作来进行访问：

• P() 操作 (来自荷兰语 Proberen，尝试)：也常被称为 down() 或 wait()。
• V() 操作 (来自荷兰语 Verhogen，增加)：也常被称为 up() 或 signal()。

关于信号量的值，有两种主流定义：

2.2.1 第一种定义（Dijkstra 原始定义）

【重点】

• 信号量是一个非负整数。
• down(semaphore):
  • 如果 semaphore > 0，则将其值减一，线程继续执行。
  • 如果 semaphore == 0，则线程阻塞，直到另一个线程对该信号量执行 up 操作。
• up(semaphore):
  • 将 semaphore 的值加一。
  • 如果有线程因该信号量而阻塞，则唤醒其中一个。

这种定义很好地解决了“丢失的唤醒”问题。如果 up 操作先于 down 操作执行，信号量的值会先加一，当 down 操作稍后执行时，它会发现信号量大于 0，于是直接减一并继续，而不会睡眠。信号量的值**“记住”**了那次 up 操作。

2.2.2 第二种定义（常用实现方式）

【重点】

• 信号量的值可以为负数。
• 值的含义：
  • 正值：表示可用资源的数量。
  • 零值：表示无可用资源，也无线程等待。
  • 负值：其绝对值表示正在等待该资源的线程数量。
• down(semaphore):
  • 无条件将 semaphore 的值减一。
  • 如果结果值小于 0，则将当前线程状态更改为 BLOCKED 并加入等待队列。
• up(semaphore):
  • 无条件将 semaphore 的值加一。
  • 如果结果值小于或等于 0，则从等待队列中唤醒一个线程。

2.3 特殊的信号量：二元信号量 (Binary Semaphore) ⚖️

【重点】 二元信号量是信号量的一个特例，其值只能为 0 或 1。它完美地实现了互斥锁的功能，且无需忙等待：

• 初始值为 1。
• down() 操作对应于 acquire()：第一个线程执行 down() 后，信号量变为 0，线程进入临界区。其他线程再执行 down() 就会阻塞。
• up() 操作对应于 release()：持有锁的线程退出临界区时执行 up()，信号量恢复为 1，等待队列中的一个线程被唤醒。

---

第三章：应用信号量解决生产者-消费者问题 ✅

3.1 问题建模：定义三个信号量 🔧

【核心考点】 要用信号量完美解决生产者-消费者问题，我们需要三个信号量，分别扮演不同的角色：

• semaphore mutex = 1;
  • 角色：二元信号量，用于互斥。
  • 作用：确保任何时候只有一个线程（生产者或消费者）能够访问缓冲区。
• semaphore empty = N;
  • 角色：计数信号量，用于同步。
  • 作用：记录缓冲区中空闲槽位的数量。初始值为缓冲区大小 N。
• semaphore full = 0;
  • 角色：计数信号量，用于同步。
  • 作用：记录缓冲区中已占用槽位的数量。初始值为 0。

3.2 一个错误的尝试与死锁分析 ❌

【核心考点】 信号量的操作顺序至关重要，错误的顺序会导致死锁（Deadlock）。看下面这个错误的实现：

// 错误的生产者实现
send(message msg) {
    down(mutex);         // 1. 先锁住缓冲区
    down(empty);         // 2. 再检查是否有空位
    // ... 放入数据 ...
    up(full);
    up(mutex);
}

// 错误的消费者实现
message receive() {
    down(mutex);         // 1. 先锁住缓冲区
    down(full);          // 2. 再检查是否有数据
    // ... 取出数据 ...
    up(empty);
    up(mutex);
}

死锁场景分析：

1. 缓冲区已满 (empty 信号量为 0)。
2. 生产者线程运行，成功执行 down(mutex)，获得了缓冲区的锁。
3. 生产者接着执行 down(empty)，由于 empty 为 0，生产者线程阻塞。关键在于，它在阻塞时并未释放 mutex 锁！
4. 消费者线程运行，想要消费数据以腾出空间。它尝试执行 down(mutex) 来获取缓冲区锁。
5. 由于 mutex 锁仍被阻塞的生产者持有，消费者线程也阻塞。
6. 结果：生产者在等待消费者释放空间，而消费者在等待生产者释放锁。两者相互等待，形成永久阻塞，即死锁。

3.3 正确的解决方案 ✅

【核心考点】 为了避免上述死锁，我们必须调整 down 操作的顺序。

信号量使用黄金法则：在需要同时获取“同步”和“互斥”资源时，应始终先执行用于同步的 down 操作，再执行用于互斥的 down 操作。

// 正确的生产者实现
send(message msg) {
    down(empty);         // 1. 先检查是否有空位 (同步)
    down(mutex);         // 2. 确认有空位后，再锁住缓冲区 (互斥)
    buffer[in % N] = msg;
    in = in + 1;
    up(mutex);           // 3. 释放互斥锁
    up(full);            // 4. 通知 full 计数增加
}

// 正确的消费者实现
message receive() {
    down(full);          // 1. 先检查是否有数据 (同步)
    down(mutex);         // 2. 确认有数据后，再锁住缓冲区 (互斥)
    msg = buffer[out % N];
    out = out + 1;
    up(mutex);           // 3. 释放互斥锁
    up(empty);           // 4. 通知 empty 计数增加
    return msg;
}

为什么这样能行？ 如果生产者因 down(empty) 而阻塞，它此时并未持有 mutex 锁。这意味着消费者可以自由地获取 mutex 锁，进入临界区消费数据，并通过 up(empty) 来增加空闲槽位的数量，最终唤醒阻塞的生产者。死锁的循环被打破了。

---

第四章：总结与展望 🚀

4.1 信号量回顾 📝

信号量是一种功能强大的同步原语，它通过一个内部的计数器和等待队列，优雅地解决了 sleep/wakeup 的“丢失唤醒”问题。它既可以像二元信号量（mutex）那样实现互斥，也可以像计数信号量（empty/full）那样实现复杂的线程同步。

4.2 对锁实现的思考：自旋 vs 阻塞 🤔

【了解】 我们最初讨论了自旋锁（忙等待）的低效。而基于 sleep() 或信号量实现的锁，则是一种阻塞锁。当锁被占用时，请求线程会进入阻塞状态，让出 CPU。

在实际的操作系统内核开发（如 BLITZ 实验）中，实现一个高效的 acquire() 函数需要仔细考虑：

• waitingThreads: 需要一个队列来存放所有等待该锁的线程。
• heldBy: 需要一个变量来记录当前是哪个线程持有该锁。
• 竞争条件: 必须仔细处理各种竞争条件，确保锁的正确性和原子性。

这提示我们，即使是看似简单的锁，其底层实现也充满了对并发编程的深刻理解。

贡献者

Xyea

页面历史

最后编辑于 7 天前

查看完整历史

fc9cfc6-vault backup: 2025-10-15 09:06:13