📚 课程目录第3章等待队列（Wait Queue）数据结构

3、等待队列（Wait Queue）数据结构：struct wait_queue_head 与 struct wait_queue_entry

等待队列是 Linux 内核实现阻塞 I/O 和异步事件通知的核心基础设施。它允许进程在某个条件不满足时主动让出 CPU（休眠），并在条件满足时被内核唤醒。理解等待队列的数据结构是掌握阻塞与非阻塞 I/O 机制的第一步。

  核心概念：等待队列本质上是一个“休眠进程链表 + 唤醒回调函数”的组合。当进程需要等待某个事件时，它将自己封装成一个等待队列项（entry），挂入等待队列头（head）管理的链表中，然后调度器将其移出运行队列。当事件发生时，内核遍历等待队列头下的所有项，逐一执行唤醒回调，将进程重新置入运行队列。

3.1 struct wait_queue_head：等待队列的“队首”

struct wait_queue_head 是等待队列的管理结构，每个需要被等待的事件（如设备可读、可写、中断完成）都对应一个独立的等待队列头。其定义位于 <linux/wait.h>：

struct wait_queue_head {
    spinlock_t          lock;       // 自旋锁，保护链表操作，防止并发竞争
    struct list_head    head;       // 双向链表头，链接所有等待队列项
};

成员	类型	作用
`lock`	`spinlock_t`	自旋锁，保护对 `head` 链表的并发访问（中断上下文、SMP 多核环境）
`head`	`struct list_head`	内核标准双向链表头，链接所有挂入该等待队列的 `wait_queue_entry` 项

初始化等待队列头有两种方式：

静态初始化：DECLARE_WAIT_QUEUE_HEAD(wq_name);
动态初始化：init_waitqueue_head(&wq);

最佳实践：等待队列头通常作为设备结构体（struct device 或自定义结构体）的成员存在，生命周期与设备一致。例如：struct my_device { ... wait_queue_head_t read_wq; ... };

3.2 struct wait_queue_entry：等待队列的“节点”

每个因等待事件而休眠的进程，在内核中都被封装为一个 struct wait_queue_entry 实例。该结构体记录了进程信息、唤醒回调函数以及等待标志：

struct wait_queue_entry {
    unsigned int        flags;      // 等待标志，如 WQ_FLAG_EXCLUSIVE（排他等待）
    void                *private;   // 通常指向当前进程的 task_struct 指针
    wait_queue_func_t   func;       // 唤醒回调函数，默认是 autoremove_wake_function
    struct list_head    entry;      // 链表节点，用于挂入 wait_queue_head 的 head 链表
};

成员	说明
`flags`	控制等待行为。常用 `WQ_FLAG_EXCLUSIVE`：排他等待，一次只唤醒一个进程，避免惊群效应
`private`	私有数据指针。标准用法指向 `current`（当前进程的 task_struct）
`func`	唤醒回调函数。内核提供默认实现 `autoremove_wake_function`，自动将进程状态设为 `TASK_RUNNING` 并从等待队列中移除
`entry`	标准双向链表节点，通过 `list_add_tail` / `list_del_init` 操作挂入或脱离等待队列头

关键区别：wait_queue_head 是“容器”，一个设备通常只有一个；wait_queue_entry 是“容器中的元素”，每个等待的进程都有一个。多个进程可以同时等待同一个等待队列头。

3.3 数据结构关系图

下图展示了等待队列头与等待队列项之间的链表关系，以及每个项如何关联到具体的进程：

3.4 排他等待标志：WQ_FLAG_EXCLUSIVE

当多个进程等待同一个事件时，默认行为是 广播唤醒：事件发生时，内核遍历整个等待队列，唤醒所有进程。这在某些场景下会导致“惊群效应”（thundering herd），即所有进程被唤醒后竞争同一个资源，最终只有一个能成功，其余进程再次休眠，造成不必要的上下文切换开销。

为解决此问题，内核引入了 排他等待 机制：

非排他等待（默认）：flags = 0，唤醒时所有等待项都会被处理。
排他等待：flags = WQ_FLAG_EXCLUSIVE，唤醒时内核只处理第一个设置了该标志的等待项，然后停止遍历。

特性	非排他等待 (flags=0)	排他等待 (WQ_FLAG_EXCLUSIVE)
唤醒行为	唤醒队列中所有进程	只唤醒第一个排他等待进程
适用场景	共享事件（如数据到达，所有读者都可读）	互斥事件（如互斥锁释放，只有一个竞争者能获得锁）
惊群效应	容易引发	有效避免
典型 API	`wake_up()`	`wake_up()` 内部自动处理

  内核唤醒策略：__wake_up_common() 函数在遍历等待队列时，遇到第一个设置了 WQ_FLAG_EXCLUSIVE 的 entry 后，会调用其回调函数并立即返回，不再继续遍历后续项。这保证了互斥场景下只有一个进程被唤醒。

3.5 等待队列的典型操作流程

等待队列的使用遵循“准备 → 休眠 → 唤醒”三阶段模式：

准备阶段：调用 DECLARE_WAITQUEUE(wait, current) 创建等待队列项，将当前进程绑定到 entry 中。
休眠阶段：调用 add_wait_queue() 将 entry 挂入等待队列头，然后设置进程状态为 TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE，最后调用 schedule() 让出 CPU。
唤醒阶段：事件发生时，调用 wake_up() 或 wake_up_interruptible()，内核遍历等待队列，执行唤醒回调，将进程状态置为 TASK_RUNNING 并从队列中移除。

// 典型等待队列使用模式（内核驱动中常见）
static DECLARE_WAIT_QUEUE_HEAD(my_wq);   // 定义等待队列头

// 等待线程
int wait_for_event(void)
{
    DEFINE_WAIT(wait);                    // 定义并初始化等待队列项
    add_wait_queue(&my_wq, &wait);       // 将当前进程加入等待队列
    set_current_state(TASK_INTERRUPTIBLE); // 设置进程状态为可中断休眠
    schedule();                           // 让出 CPU，进入休眠
    remove_wait_queue(&my_wq, &wait);     // 唤醒后从队列中移除
    return 0;
}

// 唤醒线程
void wakeup_event(void)
{
    wake_up(&my_wq);                      // 唤醒等待队列中的所有进程
}

注意：实际驱动开发中很少直接使用 DEFINE_WAIT + schedule() 的原始方式，而是使用封装好的 wait_event_interruptible() 等宏。这些宏内部自动完成了上述所有步骤，并增加了条件检查，防止虚假唤醒。

3.6 等待队列与进程状态的关系

等待队列机制与 Linux 进程状态管理紧密配合。进程在等待队列中休眠时，其状态被设置为 TASK_INTERRUPTIBLE（可被信号中断）或 TASK_UNINTERRUPTIBLE（不可中断）：

TASK_INTERRUPTIBLE：进程可以被信号唤醒（如 SIGKILL），适合用户态可中断的等待场景。
TASK_UNINTERRUPTIBLE：进程忽略所有信号，只能通过 wake_up() 唤醒，适合关键资源等待（如磁盘 I/O）。
TASK_KILLABLE：内核 2.6.25 引入的折中方案，只能被致命信号（SIGKILL）唤醒。

等待队列本身不关心进程状态，它只负责管理链表和唤醒回调。进程状态由调用者在休眠前通过 set_current_state() 显式设置。

常见错误：忘记在 schedule() 之前调用 set_current_state() 设置休眠状态，或者在唤醒后忘记调用 remove_wait_queue() 将 entry 从链表中移除。前者会导致进程立即被重新调度（忙等待），后者会导致内存泄漏或链表损坏。