Linux0.11中的等待链实现解析

Linux0.11调度算法中的等待链实现

本文初次写于2024年7月,两年多过去了,我再回头看,发现当初的表述有一些有问题,修改之:勘误表

最近在研究kernel0.11的源码,调度这部分写的很有意思,记个笔记。

在内核中io操作部分的代码常常能看到类似如下的调用:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
static inline void lock_inode(struct m_inode * inode)
{
cli();
while (inode->i_lock)
sleep_on(&inode->i_wait);
inode->i_lock=1;
sti();
}

static inline void unlock_inode(struct m_inode * inode)
{
inode->i_lock=0;
wake_up(&inode->i_wait);
}

那我们先看看他们是怎么实现的:

取自kernel/schd.c

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
void sleep_on(struct task_struct **p)
{
struct task_struct *tmp;

if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp = *p;
*p = current;
current->state = TASK_UNINTERRUPTIBLE;
schedule();
if (tmp)
tmp->state=0;
}
void interruptible_sleep_on(struct task_struct **p)
{
struct task_struct *tmp;

if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp=*p;
*p=current;
repeat: current->state = TASK_INTERRUPTIBLE;
schedule();
if (*p && *p != current) {
(**p).state=0;
goto repeat;
}
*p=NULL;
if (tmp)
tmp->state=0;
}
void wake_up(struct task_struct **p)
{
if (p && *p) {
(**p).state=0;
*p=NULL;
}
}

ps.以下的"被调度"是指该任务被schedule()选中,switch_to跳转,真正被cpu运行时。而置就绪态(唤醒)时只是具备了被选中的能力,并未真正被cpu执行。

sleep_on()和interruptible_sleep_on()

这两个东西区别在效果上讲在于interruptible_sleep_on的程序可以在得到信号的时候被schedule()调度执行,而sleep_on的却不行。

全局搜索一下,不难发现它们的参数都是某个资源的成员指针,比如

1
2
&inode->i_wait	//某个inode
&bh->b_wait //某个buffer_head

先说结论:sleep_on是和某个资源挂钩的,它的参数就对应了一个资源的等待链。而这个参数就是这个链的头。这个链类似于栈,最后sleep_on的会最先被唤醒。

我们先说sleep_on,interruptible_sleep_on和他大同小异,之后会给出他们的区别。

逻辑解析

调用进去的时候,它会把前一个等待这个资源的任务结构指针保存到一个临时变量tmp里面,再把当前调用它的任务的结构current设置成这个资源的等待链的新头。从而把这个任务插入到等待链中。所以每个调用sleep_on的地方,都在自己的栈里保存了自己的前一个调用者的指针,这样就形成了一个类似链表的东西。

这条链是附属于某个资源的,比如说一个inode。 inode->i_wait实际上保存的是等待链中最后插入进去的任务指针。 当某个任务需要等待这个资源的时候,通过sleep_on把自己插入到这条链里,把自己置睡眠态,然后让内核调度其他的任务去执行。

sleep_on把调用它的任务状态置为TASK_UNINTERRUPTIBLE,也就是在通过wake_up明确唤醒之前是不能被调度到的,也就是在wake_up之前是不会被cpu继续执行的。

在设置了任务状态后,内核通过schedule()重新选择了一个可以被调度的任务,并且让cpu跳转到这个新的任务,于是对于旧的任务(正在等待的)而言就被定格在了schedule()返回的前一刻。

当这个等待的进程被wake_up之后,它的状态被置为就绪,在下次被调度程序选中之后,它就会返回到schedule()的下一句执行,把自己的先来者也变成就绪态,这样它的先来者也获得了被调度器选中的机会,这样子子孙孙无穷匮也,这样就递归地把一条链都唤醒了。当然,在万物之始,等待链头会是NULL,所以对于第一个加入队列的任务而言,它的tmp指向了NULL。所以我们需要在唤醒先来者之前判断一下。

内部的区别

对于调用sleep_on而言,它的唤醒需要明确调用wake_up(链头地址);所以作为被wake_up唤醒的程序,它的唤醒一定是按顺序来的,在第一个被调度后第二个才被置就绪态。在被调度后*p一定指向current。 而interruptible_sleep_on就不同了,它可以被调度程序在收到信号的时候唤醒,所以在它重新被选中调度的时候,可能自己处在这条链的中间。这时候如果只唤醒它之前入列的任务就会缺漏,所以interruptible_sleep_on做了判断,确保唤醒是按顺序来的。

这里其实linus有个错误,在sleep_on唤醒上一个等待的任务的时候,我们需要把链头设置成上一个等待的任务的指针,在interruptible_sleep_on里头被直接设置成了NULL,这是不行的原因待会再说。总而言之,在唤醒自己的上家的时候,需要一句*p = tmp;。在0.12版本中,它们被统一写成了如下形式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
static inline void __sleep_on(struct task_struct **p, int state)
if (!p)
return;
if (current == &(init_task.task))
panic("task[0] trying to sleep");
tmp = *p;
*p = current;
current->state = state;
repeat: schedule();
if (*p && *p != current) {
(**p).state = 0;
current->state = TASK_UNINTERRUPTIBLE;
goto repeat;
}
if (!*p)
printk("Warning: *P = NULL\n\r");
if (*p = tmp) //链头被重新设置.
tmp->state=0;
}
void interruptible_sleep_on(struct task_struct **p)
{
__sleep_on(p,TASK_INTERRUPTIBLE);
}
void sleep_on(struct task_struct **p)
{
__sleep_on(p,TASK_UNINTERRUPTIBLE);
}

wake_up()

和sleep_on类似,它的参数也对应了一个资源的等待链。

通过把链头任务置就绪态,它让整条被"冻结"的链的头(最后调用sleep_on的任务)变得就绪,让它重新能够继续执行sleep_on,在那里它还递归地唤醒前面的每一个。就像机械波的传播那样。

在这里我们的linus写错了一行代码,如果在这里把*p也就是整个链的头都变成NULL的话,整条链就丢失了。但是现在这些等待链中的所有程序还没被调度运行完,这条链还不能清空。所以这一行应该删掉,而0.12版的内核也确实把它删掉了。

参考文献

勘误表_2026_11

ai帮我写的,我看了看没有什么问题

#位置原表述问题更正
1「sleep_on()和interruptible_sleep_on()」第 2 段“它们的参数都是某个资源的成员指针”多数是,但不全是。fs/buffer.c:33 的 static struct task_struct * buffer_wait、kernel/blk_drv/ll_rw_blk.c:26 的 wait_for_request、kernel/sched.c:201 的 wait_motor[4] 都是独立变量参数的类型是 struct task_struct **,语义是"等待地址"——某个 task_struct * 槽位;它通常正好是资源的成员(i_wait、b_wait),但不是必须
2「内部的区别」第 1 段“在被调度后 *p 一定指向 current”不成立。被调度回来时 *p 有三种可能:① NULL——wake_up 在 kernel/sched.c:192 把它清掉了,这是最常见的一种;② 比你更晚入链的任务;③ 才是 currentif (*p && *p != current) 不只是为"被信号唤醒"准备的,它同时在处理"我已经不是队头"
3同上“唤醒一定是按顺序来的,在第一个被调度后第二个才被置就绪态”把两件事混成一件:置就绪的先后确实沿链逐级发生,但被执行的顺序没有保证(schedule() 按 counter 挑人,kernel/sched.c:124-140);而且 wake_up 只把队头置就绪,并不存在"一次唤醒整条链"改为"置就绪沿链逐级传播;谁先被 CPU 执行不确定"
4「内部的区别」第 2 段“linus 在 sleep_on 唤醒上一个等待的任务的时候……在 interruptible_sleep_on 里头被直接设置成了 NULL”归因错了。0.11 的 sleep_on(kernel/sched.c:151-165)里没有 *p=NULL;全树只有两处:wake_up(:192)和 interruptible_sleep_on(:183)。0.12 的修法也不是"补一句",而是把职责拆开:唤醒者不再碰 *p,摘链交给睡眠者自己
作者注:应该是当初写的时候号犯迷糊了,这段我现在自己也没读通。不过意思就是这个设置成NULL行为是不对的
见 0.12 kernel/sched.c:171-192(__sleep_on)与 :204-213(wake_up),关键一行是 :190 的 if (*p = tmp)
5「wake_up()」第 2 段“整条链就丢失了”结论对,措辞过头。链没丢:每个睡眠者都在内核栈帧里存着前驱 tmp,连接还在;丢的是公共锚点——*p 一空,队列从"共享数据结构"退化成"只能靠逐级传递",窗口期内新来的睡眠者 tmp 记到 NULL,挂不上旧链,窗口期内的 wake_up 也变成空操作改为"失去公共锚点(可达性)"

三条补注(不算错,但容易忽略):

  1. 这套隐式链只在三根拐杖同时成立时才安全:cli() 把"检查条件 + 入睡"包成原子(fs/buffer.c:36-42、fs/inode.c:20-35、kernel/blk_drv/ll_rw_blk.c:42-49)、单 CPU 且内核不可抢占、state = 0 重复设置幂等。
  2. 同一个等待地址会被不同条件复用:fs/pipe.c 的读写两端都睡在 inode->i_wait 上(:22、:52),fs/inode.c:40、:158 释放 I_LOCK 时也 wake_up(&inode->i_wait)。所以唤醒可能被"等错条件"的人吃掉,外层必须用 while 重新检查条件。
  3. 0.99/1.x 换成了显式 struct wait_queue + add_wait_queue/remove_wait_queue,就是为了消掉上面这些问题——锚点由队列自己持有,不再寄生在资源结构体里。

Linux0.11中的等待链实现解析
https://www.hakurei.org.cn/2024/07/27/linux-011-waiting-queue/
作者
zjkimin
发布于
2024年7月28日
更新于
2026年11月7日
许可协议