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

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

最近在研究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版的内核也确实把它删掉了。

参考文献

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