kernel hacker修炼之道之调度器与时间系统-等待队列

浅析linux内核调度器与时间系统之等待队列

作者：李万鹏

等待队列实现了在事件上的条件等待：希望等待特定事件的进程把自己放在合适的等待队列，并放弃控制权。因此，等待队列表示一组睡眠的进程，当某一条件为真时，由内核唤醒他们。

等待队列的数据结构

等待队列头：

struct __wait_queue_head {
	spinlock_t lock;
	struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;

这个task_list字段是等待队列链表的头，等待队列是一个双向链表，同步通过lock自旋锁来实现。

等待队列元素：

struct __wait_queue {
	unsigned int flags;
#define WQ_FLAG_EXCLUSIVE	0x01
	struct task_struct * task;
	wait_queue_func_t func;
	struct list_head task_list;
};
typedef struct __wait_queue wait_queue_t;

这个flags字段标示了这个进程是互斥进程还是非互斥进程。那么何为互斥进程，非互斥进程呢？经常会产生一个现象，当某个资源被释放后内核唤醒了所有等待这个资源的进程，结构只有一个进程可以得到这个资源，而其他的进程再次进入睡眠。因此有两种睡眠的进程：互斥进程(等待队列元素的flags字段为1)由内核有选择的唤醒；非互斥进程(等待队列元素的flags字段为0)由内核在事件发生时唤醒。等待访问临界资源的进程就是互斥进程的典型例子。等待相关事件的进程是非互斥的。例如，我们考虑等待磁盘传输结束的一组进程：一旦磁盘传输完成，所有等待的进程都会被唤醒。task字段指向这个等待队列元素对应的进程描述符。func字段表示用什么方式唤醒。等待队列元素都用task_list这个双向链表链接在一起。

等待队列的操作

声明等待队列头：

1）静态声明

DECLARE_WAIT_QUEUE_HEAD(name);

#define __WAIT_QUEUE_HEAD_INITIALIZER(name) {				\
	.lock		= SPIN_LOCK_UNLOCKED,				\
	.task_list	= { &(name).task_list, &(name).task_list } }

#define DECLARE_WAIT_QUEUE_HEAD(name) \
	wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)

2）动态声明

wait_queue_head_t name;

init_waitqueue_head(&name);

static inline void init_waitqueue_head(wait_queue_head_t *q)
{
	q->lock = SPIN_LOCK_UNLOCKED;
	INIT_LIST_HEAD(&q->task_list);
}

由于静态声明不但包括了对变量的声明还包括了初始化，所以动态声明的分成两个步骤，对动态声明的等待队列元素进行初始化。

声明等待队列元素：

1）静态声明

DECLARE_WAITQUEUE(name, tsk)

#define __WAITQUEUE_INITIALIZER(name, tsk) {				\
	.task		= tsk,						\
	.func		= default_wake_function,			\
	.task_list	= { NULL, NULL } }

#define DECLARE_WAITQUEUE(name, tsk)					\
	wait_queue_t name = __WAITQUEUE_INITIALIZER(name, tsk)

这个default_wake_function调用的是try_to_wake_up()。

int default_wake_function(wait_queue_t *curr, unsigned mode, int sync, void *key)
{
	task_t *p = curr->task;
	return try_to_wake_up(p, mode, sync);
}

2）动态声明

wait_queue_t tsk;

init_waitqueue_entry(tsk);

static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
{
	q->flags = 0;
	q->task = p;
	q->func = default_wake_function;
}

插入等待队列：

1）add_wait_queue()

static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
{
	list_add(&new->task_list, &head->task_list);
}
void fastcall add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
	unsigned long flags;
	wait->flags &= ~WQ_FLAG_EXCLUSIVE;
	spin_lock_irqsave(&q->lock, flags);
	__add_wait_queue(q, wait);
	spin_unlock_irqrestore(&q->lock, flags);
}

将等待队列元素插入到等待队列的前面。

2）add_wait_queue_exclusive()

static inline void __add_wait_queue_tail(wait_queue_head_t *head,
						wait_queue_t *new)
{
	list_add_tail(&new->task_list, &head->task_list);
}
void fastcall add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *wait)
{
	unsigned long flags;

	wait->flags |= WQ_FLAG_EXCLUSIVE;
	spin_lock_irqsave(&q->lock, flags);
	__add_wait_queue_tail(q, wait);
	spin_unlock_irqrestore(&q->lock, flags);
}

将等待队列元素设置称互斥进程，添加到队列末尾，注意互斥的是需要添加到末尾的，这样唤醒的时候可以选择是唤醒一个还是全部还是nr。

3）prepare_to_wait()

void fastcall
prepare_to_wait(wait_queue_head_t *q, wait_queue_t *wait, int state)
{
	unsigned long flags;

	wait->flags &= ~WQ_FLAG_EXCLUSIVE;
	spin_lock_irqsave(&q->lock, flags);
	if (list_empty(&wait->task_list))
		__add_wait_queue(q, wait);
	/*
	 * don't alter the task state if this is just going to
	 * queue an async wait queue callback
	 */
	if (is_sync_wait(wait))
		set_current_state(state);
	spin_unlock_irqrestore(&q->lock, flags);
}

将等待队列元素添加到等待队列，与add_wait_queue()不同点是它可以设置进程的状态。

4）prepare_to_wait_exclusive()

void fastcall
prepare_to_wait_exclusive(wait_queue_head_t *q, wait_queue_t *wait, int state)
{
	unsigned long flags;

	wait->flags |= WQ_FLAG_EXCLUSIVE;
	spin_lock_irqsave(&q->lock, flags);
	if (list_empty(&wait->task_list))
		__add_wait_queue_tail(q, wait);
	/*
	 * don't alter the task state if this is just going to
 	 * queue an async wait queue callback
	 */
	if (is_sync_wait(wait))
		set_current_state(state);
	spin_unlock_irqrestore(&q->lock, flags);
}

与prepare_to_wait()的区别是prepare_to_wait_exclusive是把非互斥进程添加到等待队列。

删除等待队列：

remove_wait_queue()

static inline void __remove_wait_queue(wait_queue_head_t *head,
							wait_queue_t *old)
{
	list_del(&old->task_list);
}
void fastcall remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__remove_wait_queue(q, wait);
	spin_unlock_irqrestore(&q->lock, flags);
}

把等待队列元素从等待队列删除。

检查队列是否为空：

waitqueue_active()

static inline int waitqueue_active(wait_queue_head_t *q)
{
	return !list_empty(&q->task_list);
}

判断等待队列是否为空。

睡眠函数：

1）sleep_on()

#define	SLEEP_ON_VAR					\
	unsigned long flags;				\
	wait_queue_t wait;				\
	init_waitqueue_entry(&wait, current);

#define SLEEP_ON_HEAD					\
	spin_lock_irqsave(&q->lock,flags);		\
	__add_wait_queue(q, &wait);			\
	spin_unlock(&q->lock);

#define	SLEEP_ON_TAIL					\
	spin_lock_irq(&q->lock);			\
	__remove_wait_queue(q, &wait);			\
	spin_unlock_irqrestore(&q->lock, flags);
void fastcall __sched sleep_on(wait_queue_head_t *q)
{
	SLEEP_ON_VAR

	current->state = TASK_UNINTERRUPTIBLE;

	SLEEP_ON_HEAD
	schedule();
	SLEEP_ON_TAIL
}

sleep_on()这个函数动态的创建了等待队列元素，并将其添加到等待队列睡眠，然后调度让其他进程执行，如果被唤醒了就从等待队列移除。

2）wait_event()

#define __wait_event(wq, condition) 					\
do {									\
	DEFINE_WAIT(__wait);						\
									\
	for (;;) {							\
		prepare_to_wait(&wq, &__wait, TASK_UNINTERRUPTIBLE);	\
		if (condition)						\
			break;						\
		schedule();						\
	}								\
	finish_wait(&wq, &__wait);					\
} while (0)

#define wait_event(wq, condition) 					\
do {									\
	if (condition)	 						\
		break;							\
	__wait_event(wq, condition);					\
} while (0)

首先判断条件是否已经成立，如果成立就不用睡眠了。如果不成立创建等待队列元素，将等待队列元素添加到等待队列并设置状态标志。如果此时条件已经满足了就不用调用schedule()让CPU了，可以将等待队列元素从等待队列移除往下执行。

总结一下sleep_on()与wait_event()，如果条件不满足进程会阻塞，被调到等待队列。但是sleep_on()内部没有条件判断，可能在创建等待队列元素并添加到等待队列的时候condition已经为true了，却要调用schedule()将CPU让与别的进程，委屈了！

唤醒函数：

首先看一下唤醒的底层核心函数：

static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
			     int nr_exclusive, int sync, void *key)
{
	struct list_head *tmp, *next;

	list_for_each_safe(tmp, next, &q->task_list) {
		wait_queue_t *curr;
		unsigned flags;
		curr = list_entry(tmp, wait_queue_t, task_list);
		flags = curr->flags;
		if (curr->func(curr, mode, sync, key) &&
		    (flags & WQ_FLAG_EXCLUSIVE) &&
		    !--nr_exclusive)
			break;
	}
}

void fastcall __wake_up(wait_queue_head_t *q, unsigned int mode,
				int nr_exclusive, void *key)
{
	unsigned long flags;

	spin_lock_irqsave(&q->lock, flags);
	__wake_up_common(q, mode, nr_exclusive, 0, key);
	spin_unlock_irqrestore(&q->lock, flags);
}

__wake_up_common是唤醒的底层核心函数，调用list_for_each_safe先将非互斥进程唤醒，再根据参数nr_exclusive来决定唤醒互斥进程的数量。从头到尾遍历等待队列，这也是为什么add_wait_queue_exclusive()的时候将互斥进程添加到等待队列末尾而不是头。

1）wake_up()

#define wake_up(x)			__wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 1, NULL)

2）wake_up_nr()

#define wake_up_nr(x, nr)		__wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, nr, NULL)

3）wake_up_all()

#define wake_up_all(x)			__wake_up(x, TASK_UNINTERRUPTIBLE | TASK_INTERRUPTIBLE, 0, NULL)