Linux 等待队列（Wait Queue）和进程/线程调度

[cyrushine]

https://hughesxu.github.io/posts/Linux_Wait_Queue/

---

注意！

1. 对于 Linux 内核来说，进程 Process 和线程 Thread 都是一样的，是同一个数据结构，只不过线程间共享了内存

2. 核心函数 schedule() 表示让渡出 cpu 资源给内核任务队列里的下一个进程/线程，它不同于高级编程语言里的阻塞/休眠的概念

---

Linux内核的等待队列（Wait Queue）是重要的数据结构，与进程调度机制紧密相关联，可以用来同步对系统资源的访问、异步事件通知、跨进程通信等。

在Linux中，等待队列以循环链表为基础结构，包括两种数据结构：等待队列头(wait queue head)和等待队列元素(wait queue)，整个等待队列由等待队列头进行管理。

等待队列头结构 wait_queue_head_t 包括一个自旋锁和一个链表头

等待队列元素 wait_queue_entry_t 除了包括链表项，还包括：

• flags: 标识队列元素状态和属性
• *private: 用于指向关联进程task_struct结构体的指针
• func: 函数指针，用于指向等待队列被唤醒时的回调的唤醒函数

以进程阻塞和唤醒的过程为例，等待队列的使用场景可以简述为：
进程A因等待某些资源（依赖进程B的某些操作）而不得不进入阻塞状态，便将当前进程加入到等待队列Q中。进程B在一系列操作后，可通知进程A所需资源已到位，便调用唤醒函数wake up来唤醒等待队列上Q的进程，注意此时所有等待在队列Q上的进程均被置为可运行状态。

上述场景中看到，当某进程调用wake up函数唤醒等待队列时，队列上所有的进程均被唤醒，在某些场合会出现唤醒的所有进程中，只有某个进程获得了期望的资源，而其他进程由于资源被占用不得不再次进入休眠。如果等待队列中进程数量庞大时，该行为将影响系统性能。
内核增加了“独占等待” (WQ_FLAG_EXCLUSIVE)来解决此类问题。一个独占等待的行为和通常的休眠类似，但有如下两个重要的不同：

• 等待队列元素设置 WQ_FLAG_EXCLUSIVE 标志时，会被添加到等待队列的尾部，而非头部。
• 在某等待队列上调用wake up时，执行独占等待的进程每次只会唤醒其中第一个（所有非独占等待进程仍会被同时唤醒）

初始化等待队列头：DECLARE_WAIT_QUEUE_HEAD(name) 和 init_waitqueue_head(&wq_head)

初始化等待队列元素

1. 调用宏定义 DECLARE_WAITQUEUE(name, task)，将定义一个名为name的等待队列元素，private数据指向给定的关联进程结构体task，唤醒函数为 default_wake_function()
2. 调用宏定义 DEFINE_WAIT(name) 和 init_wait(&wait_queue)，这两种方式都将当前进程 current 关联到所定义的等待队列上，唤醒函数为 autoremove_wake_function()

添加至等待队列

1. add_wait_queue()：在等待队列头部添加普通的等待队列元素（非独占等待，清除WQ_FLAG_EXCLUSIVE标志）。
2. add_wait_queue_exclusive()：在等待队列尾部添加独占等待队列元素（设置了WQ_FLAG_EXCLUSIVE标志）。

remove_wait_queue() 函数用于将等待队列元素 wq_entry 从等待队列 wq_head 中移除

休眠进程直到某个条件成立

wait_event(wq_head, condition)
wait_event_timeout(wq_head, condition, timeout) 
wait_event_interruptible(wq_head, condition)
wait_event_interruptible_timeout(wq_head, condition, timeout)
io_wait_event(wq_head, condition)
// wq_head 是等待队列头，condition 是任意一个布尔表达式，interruptible 进程可以被信号中断，timeout 只等待限定的时间

唤醒等待队列

wake_up(&wq_head)
wake_up_interruptible(&wq_head)
wake_up_nr(&wq_head, nr)
wake_up_interruptible_nr(&wq_head, nr)
wake_up_interruptible_all(&wq_head)

总结等待队列的使用主要有三种方式：

(1) 等待事件方式
wait_event() 和 wake_up() 函数配合，实现进程阻塞睡眠和唤醒

(2) 手动休眠1

DECLARE_WAIT_QUEUE_HEAD(queue);
DECLARE_WAITQUEUE(wait, current);

for (;;) {
    add_wait_queue(&queue, &wait);
    set_current_state(TASK_INTERRUPTIBLE);
    if (condition)
        break;
    schedule();
    remove_wait_queue(&queue, &wait);
    if (signal_pending(current))
        return -ERESTARTSYS;
}
set_current_state(TASK_RUNNING);
remove_wait_queue(&queue, &wait)

(3) 手动休眠2

DELARE_WAIT_QUEUE_HEAD(queue);
DEFINE_WAIT(wait);

while (! condition) {
    prepare_to_wait(&queue, &wait, TASK_INTERRUPTIBLE);
    if (! condition)
        schedule();
    finish_wait(&queue, &wait)
}

参考资料
[1] LINUX 设备驱动程序（LDD3），2012年
[2] Linux设备驱动开发详解（基于最新的Linux4.0内核），宋宝华编著，2016年
[3] linux设备驱动模型：https://blog.csdn.net/qq_40732350/article/details/82992904
[4] Linux 等待队列 (wait queue)：https://xyfu.me/posts/236f51d8/
[5] Linux Wait Queue 等待队列：https://www.cnblogs.com/gctech/p/6872301.html
[6] 源码解读Linux等待队列：http://gityuan.com/2018/12/02/linux-wait-queue/
[7] Driver porting: sleeping and waking up：https://lwn.net/Articles/22913/

[cyrushine]