Linux 阻塞与唤醒实现原理

在前面的文件 I/O 文章中,我们有提到 Linux 文件 I/O 支持阻塞和非阻塞的数据读取方式,当采用阻塞方式进行 I/O 时,进程将会阻塞在read()或者write()系统调用上,直到文件可读或者是内核缓冲区可写。这些阻塞与唤醒的实现与内核调度紧密相关,Linux 内核使用等待队列和完成量来实现该功能。

注: 本篇文章所用Linux内核源码版本为v5.8

1. 进程状态有限状态机

进程并不总是可以立即运行的,一方面是 CPU 资源有限,另一方面则是进程时常需要等待外部事件的发生,例如 I/O 事件、定时器事件等。

因此,对进程的状态进行分类就是一件非常有必要的事情,对于等待某事件发生的进程给予 CPU 资源是没有任何意义的,因为此时事件可能仍未发生。而对于正等待 CPU 资源的进程而言,在得到 CPU 之后即可立即执行。调度器为了尽可能最大地使用硬件资源,通常会将进程分为3个主要的状态: 运行、等待和睡眠。

处于运行状态的进程正在使用 CPU 等资源,从上图中可以看到,运行态的进程在执行完任务后结束,进入到结束状态。当 CPU 时间片到期之后,调度器选择其它进程执行,此时将进入等待状态。同时,当运行时的进程发起 I/O 操作,或者等待其它事件的发生时,将进入睡眠状态。

处于等待状态的进程由于缺少 CPU 资源而被迫停止运行,只要调度器下次选中该进程即可立即执行,由等待状态转变为运行状态。

处于睡眠状态的进程在等待外部事件的发生,例如 I/O 操作的数据抵达,创建的定时器到期等等,处于睡眠状态的进程永远不会被调度器进行选择并执行。当期望的事件到达后,进程由睡眠状态更改为等待状态,等待调度器的下一次选择。

处于等待的进程将会被放置于就绪队列中(红黑树实现),而处于睡眠状态的进程则放置于等待队列(双链表实现)中。调度器的目光主要放在就绪队列上,从该队列中取出下一个将要执行的进程,而等待队列和就绪队列中的进程会因为事件的发生而进行相互转移。

在实际的内核实现中,进程的运行状态表示要比上文所述更加详细一些,进程状态定义于include/linux/sched.h:

  • TASK_RUNNING,可运行状态。此时进程并不一定正在运行,一旦得到调度器的调度即可立即运行。
  • TASK_INTERRUPTIBLE,可中断睡眠状态。此时进程因为等待外部事件的发生而睡眠,此时可由信号或者是内核唤醒。
  • TASK_UNINTERRUPTIBLE,不可中断睡眠状态。和TASK_INTERRUPTIBLE状态类似,等待外部事件发生的睡眠状态。不同的是改状态只能由内核亲自唤醒,不能由信号唤醒,通常用于进程必须等待某件工作完成,不能被 Kill。

除了这三个核心进程状态以外,还有__TASK_STOPPED__TASK_TRACED等状态,由于这些状态在本文中并不重要,所以略去。

2. 等待队列

等待队列相关的源码位于include/linux/wait.h以及kernel/sched/wait.c文件中,头文件中定义了等待队列以及队列元素的基本数据结构,wait.c源文件则主要包含具体的方法实现。

首先来看等待队列的基本结构,分为队列头和队列项:

/* 等待队列头 */
struct wait_queue_head {
	spinlock_t		lock;       /* 自旋锁 */
	struct list_head	head;   /* previous、next指针 */
};
typedef struct wait_queue_head wait_queue_head_t;

/* 等待队列元素 */
struct wait_queue_entry {
	unsigned int		flags;  /* 标识位 */
	void			*private;   /* 通常指向等待进程 */
	wait_queue_func_t	func;   /* 唤醒函数 */
	struct list_head	entry;  /* previous、next指针 */
};

在内核的链表实现中,绝大多数的链表均为循环双链表,等待队列也不例外。因为等待队列可能会在系统中断时进行修改,所以必须要添加互斥锁机制保护队列元素。

等待队列元素的设计也非常简洁,除了双链表必要的前后指针以外,仅包含一个指向等待进程task_struct实例的指针,一个唤醒函数和一个标识位。

唤醒函数通常由调度器实现,如kernel/sched/core.c中定义的try_to_wake_up方法,可以简单的认为唤醒函数就是将进程的状态由TASK_INTERRUPTIBLETASK_UNINTERRUPTIBLE修改为TASK_RUNNING,并将其加入至就绪队列中。

wait.h中提供了一系列与等待队列相关的宏定义供外部使用,例如wait_event,本质上是对等待队列的进一步封装:

#define wait_event(wq_head, condition)						\
do {										\
	might_sleep();								\
	if (condition)								\
		break;								\
    /* 这里将原有的__wait_event宏展开,使用___wait_event代替 */     \
	___wait_event(wq_head, condition, TASK_UNINTERRUPTIBLE, 0, 0, schedule())	\
} while (0)

其中wq_headwait_queue_headcondition则是一个C语言表达式,表示一个等待条件。宏定义的wait_event使得使用标准C表达式指定条件成为可能,如果使用函数实现的话,无法做到如宏实现的灵活性。注意到在调用___wait_event之前会首先检查一遍条件是否满足,避免进行无效的睡眠。

___wait_event宏定义中传入的进程状态为TASK_UNINTERRUPTIBLE,也就是说,wait_event实现的事件等待是不可中断的。当然,wait.h中同样提供了其它时间等待实现:

  • wait_event_timeout: 带有超时时间的不可中断事件等待
  • wait_event_interruptible: 可中断的事件等待
  • wait_event_interruptible_timeout: 带有超时时间的可中断事件等待

最后再来看___wait_event实现,该方法将会把当前进程包装成wait_queue_entry对象,并发安全地放置于等待队列中,并且在实际的让出CPU资源、引发调度器重新调度之前会再一次的检查等待事件是否发生,避免无效睡眠。由于源代码中该方法宏定义实现符号较多,所以将原实现抽象成伪代码:

___wait_event(wq_head, condition, state, exclusive, ret, cmd) {
    /* 初始化队列元素 */
    init_wait_entry(...);
    
    for (;;) {
        /* 将队列元素插入至等待队列中(线程安全) */
        long __int = prepare_to_wait_event(&wq_head, &__wq_entry, state);
        
        /* 检查事件条件是否满足 */
        if (condition)
            break;
            
        /* 触发调度器重新调度 */
        schedule();
}

对于唤醒一个进程在前文中已经描述过了,通用方法为wake_up(),本质上会调用内核调度模块中的try_to_wake_up()来唤醒某个进程,唤醒的实质是将进程状态修改为TASK_RUNNING,从等待队列中移出并加入至就绪队列中。