Linux0.11中的等待链实现解析
Linux0.11调度算法中的等待链实现
本文初次写于2024年7月,两年多过去了,我再回头看,发现当初的表述有一些有问题,修改之:勘误表
最近在研究kernel0.11的源码,调度这部分写的很有意思,记个笔记。
在内核中io操作部分的代码常常能看到类似如下的调用:
1 | |
那我们先看看他们是怎么实现的:
取自kernel/schd.c
1 | |
ps.以下的"被调度"是指该任务被schedule()选中,switch_to跳转,真正被cpu运行时。而置就绪态(唤醒)时只是具备了被选中的能力,并未真正被cpu执行。
sleep_on()和interruptible_sleep_on()
这两个东西区别在效果上讲在于interruptible_sleep_on的程序可以在得到信号的时候被schedule()调度执行,而sleep_on的却不行。
全局搜索一下,不难发现它们的参数都是某个资源的成员指针,比如
1 | |
先说结论: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 | |
wake_up()
和sleep_on类似,它的参数也对应了一个资源的等待链。
通过把链头任务置就绪态,它让整条被"冻结"的链的头(最后调用sleep_on的任务)变得就绪,让它重新能够继续执行sleep_on,在那里它还递归地唤醒前面的每一个。就像机械波的传播那样。
在这里我们的linus写错了一行代码,如果在这里把*p也就是整个链的头都变成NULL的话,整条链就丢失了。但是现在这些等待链中的所有程序还没被调度运行完,这条链还不能清空。所以这一行应该删掉,而0.12版的内核也确实把它删掉了。
参考文献
- 《Linux内核完全注释 修正版V1.9.5》 赵炯 对应内核0.11
- 《Linux内核0.12完全注释 修正版V5.0》 赵炯 对应内核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 把它清掉了,这是最常见的一种;② 比你更晚入链的任务;③ 才是 current | if (*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 也变成空操作 | 改为"失去公共锚点(可达性)" |
三条补注(不算错,但容易忽略):
- 这套隐式链只在三根拐杖同时成立时才安全:
cli()把"检查条件 + 入睡"包成原子(fs/buffer.c:36-42、fs/inode.c:20-35、kernel/blk_drv/ll_rw_blk.c:42-49)、单 CPU 且内核不可抢占、state = 0重复设置幂等。 - 同一个等待地址会被不同条件复用:
fs/pipe.c的读写两端都睡在inode->i_wait上(:22、:52),fs/inode.c:40、:158释放 I_LOCK 时也wake_up(&inode->i_wait)。所以唤醒可能被"等错条件"的人吃掉,外层必须用while重新检查条件。 - 0.99/1.x 换成了显式
struct wait_queue+add_wait_queue/remove_wait_queue,就是为了消掉上面这些问题——锚点由队列自己持有,不再寄生在资源结构体里。