linux内核队列实现方式,Linux内核等待队列机制原理分析

系统管理员 2023-01-20 01:57 48阅读 0赞

1.等待队列数据结构

等待队列由双向链表实现，其元素包括指向进程描述符的指针。每个等待队列都有一个等待队列头(wait queue head)，等待队列头是一个类型为wait\_queque\_head\_t的数据结构：

struct \_\_wait\_queue\_head \{

spinlock\_t lock;

struct list\_head task\_list;

\};

typedef struct \_\_wait\_queue\_head wait\_queue\_head\_t;

其中，lock是用来防止并发访问，task\_list字段是等待进程链表的头。

等待队列链表中的元素类型为wait\_queue\_t,我们可以称之为等待队列项：

struct \_\_wait\_queue \{

unsigned int flags;

\#define WQ\_FLAG\_EXCLUSIVE0x01

void \*private;

wait\_queue\_func\_t func;

struct list\_head task\_list;

\};

typedef struct \_\_wait\_queue wait\_queue\_t;

每一个等待队列项代表一个睡眠进程，该进程等待某一事件的发生。它的描述符地址通常放在private字段中。Task\_list字段中包含的是指针，由这个指针把一个元素链接到等待相同事件的进程链表中。

等待队列元素的func字段用来表示等待队列中睡眠进程应该用什么方式唤醒(互斥方式和非互斥方式)。

整个等待队列的结构如下图所示：

![081024183145.jpg][]

下面看看等待队列的工作原理。

2.等待队列的睡眠过程

使用等待队列前通常先定义一个等待队列头：static wait\_queue\_head\_t wq ,然后调用wait\_event\_\*函数将等待某条件condition的当前进程插入到等待队列wq中并睡眠，一直等到condition条件满足后，内核再将睡眠在等待队列wq上的某一进程或所有进程唤醒。

定义等待队列头没什么好讲的，下面从调用wait\_event\_\*开始分析：

这里我们举比较常用的wait\_event\_interruptible：

/\*\*

\* wait\_event\_interruptible - sleep until a condition gets true

\* @wq: the waitqueue to wait on

\* @condition: a C expression for the event to wait for

\* The process is put to sleep (TASK\_INTERRUPTIBLE) until the

\* @condition evaluates to true or a signal is received.

\* The @condition is checked each time the waitqueue @wq is woken up.

\* wake\_up() has to be called after changing any variable that could

\* change the result of the wait condition.

\* The function will return -ERESTARTSYS if it was interrupted by a

\* signal and 0 if @condition evaluated to true.

\*/

\#define wait\_event\_interruptible(wq, condition)\\

(\{\\

int \_\_ret = 0;\\

if (!(condition))\\

\_\_wait\_event\_interruptible(wq, condition, \_\_ret);\\

\_\_ret;\\

\})

这里很简单，判断一下condition条件是否满足，如果不满足则调用\_\_wait\_event\_interruptible函数。

\#define \_\_wait\_event\_interruptible(wq, condition, ret)\\

do \{\\

DEFINE\_WAIT(\_\_wait);\\

for (;;) \{\\

prepare\_to\_wait(&wq, &\_\_wait, TASK\_INTERRUPTIBLE);\\

if (condition)\\

break;\\

if (!signal\_pending(current)) \{\\

schedule();\\

continue;\\

\}\\

ret = -ERESTARTSYS;\\

break;\\

\}\\

finish\_wait(&wq, &\_\_wait);\\

\} while (0)

\_\_wait\_event\_interruptible首先定义了一个wait\_queue\_t类型的等待队列项\_\_wait :

\#define DEFINE\_WAIT(name)\\

wait\_queue\_t name = \{\\

.private= current,\\

.func= autoremove\_wake\_function,\\

.task\_list= LIST\_HEAD\_INIT((name).task\_list),\\

可以发现，这里\_\_wait的private成员(通常用来存放进程的描述符)已经被初始化为current,表示该等待队列项对应为当前进程。func成员为该等待队列项对应的唤醒函数，该进程被唤醒后会执行它，已经被初始化为默认的autoremove\_wake\_function函数。

然后在一个for (;;)循环内调用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);

prepare\_to\_wait做如下两件事，将先前定义的等待队列项\_\_wait插入到等待队列头wq，然后将当前进程设为TASK\_INTERRUPTIBLE状态。prepare\_to\_wait执行完后立马再检查一下condition有没有满足，如果此时碰巧满足了则不必要在睡眠了。如果还没有满足，则准备睡眠。

睡眠是通过调用schedule()函数实现的，由于之前已经将当前进程设置为TASK\_INTERRUPTIBLE状态，因而这里再执行schedule()进行进程切换的话，之后就永远不会再调度到该进程运行的，直到该进程被唤醒(即更改为TASK\_RUNNING状态)。

这里在执行schedule()切换进程前会先判断一下有没signal过来，如果有则立即返回ERESTARTSYS。没有的话则执行schedule()睡眠去了。

for (;;)循环的作用是让进程被唤醒后再一次去检查一下condition是否满足。主要是为了防止等待队列上的多个进程被同时唤醒后有可能其他进程已经抢先把资源占有过去造成资源又变为不可用，因此最好再判断一下。(当然，内核也提供了仅唤醒一个或多个进程(独占等待进程)的方式，有兴趣的可以参考相关资料)

进程被唤醒后最后一步是调用finish\_wait(&wq, &\_\_wait)函数进行清理工作。finish\_wait将进程的状态再次设为TASK\_RUNNING并从等待队列中删除该进程。

void fastcall finish\_wait(wait\_queue\_head\_t \*q, wait\_queue\_t \*wait)

unsigned long flags;

\_\_set\_current\_state(TASK\_RUNNING);

if (!list\_empty\_careful(&wait->task\_list)) \{

spin\_lock\_irqsave(&q->lock, flags);

list\_del\_init(&wait->task\_list);

spin\_unlock\_irqrestore(&q->lock, flags);

再往后就是返回你先前调用wait\_event\_interruptible(wq, condition)被阻塞的地方继续往下执行。

3.等待队列的唤醒过程

直到这里我们明白等待队列是如何睡眠的，下面我们分析等待队列的唤醒过程。

使用等待队列有个前提，必须得有人唤醒它，如果没人唤醒它，那么同眠在该等待队列上的所有进程岂不是变成“僵尸进程”了。

对于设备驱动来讲，通常是在中断处理函数内唤醒该设备的等待队列。驱动程序通常会提供一组自己的读写等待队列以实现上层(user level)所需的BLOCK和O\_NONBLOCK操作。当设备资源可用时，如果驱动发现有进程睡眠在自己的读写等待队列上便会唤醒该等待队列。

唤醒一个等待队列是通过wake\_up\_\*函数实现的。这里我们举对应的wake\_up\_interruptible作为例子分析。定义如下：

\#define wake\_up\_interruptible(x)\_\_wake\_up(x, TASK\_INTERRUPTIBLE, 1, NULL)

这里的参数x即要唤醒的等待队列对应的等待队列头。唤醒TASK\_INTERRUPTIBLE类型的进程并且默认唤醒该队列上所有非独占等待进程和一个独占等待进程。

\_\_wake\_up定义如下：

/\*\*

\* \_\_wake\_up - wake up threads blocked on a waitqueue.

\* @q: the waitqueue

\* @mode: which threads

\* @nr\_exclusive: how many wake-one or wake-many threads to wake up

\* @key: is directly passed to the wakeup function

\*/

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, 1, key);

spin\_unlock\_irqrestore(&q->lock, flags);

preempt\_check\_resched\_delayed();

\_\_wake\_up简单的调用\_\_wake\_up\_common进行实际唤醒工作。

\_\_wake\_up\_common定义如下：

/\*

\* The core wakeup function. Non-exclusive wakeups (nr\_exclusive == 0) just

\* wake everything up.If it's an exclusive wakeup (nr\_exclusive == small +ve

\* number) then we wake all the non-exclusive tasks and one exclusive task.

\* There are circumstances in which we can try to wake a task which has already

\* started to run but is not in state TASK\_RUNNING.try\_to\_wake\_up() returns

\* zero in this (rare) case, and we handle it by continuing to scan the queue.

\*/

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 = list\_entry(tmp, wait\_queue\_t, task\_list);

unsigned flags = curr->flags;

if (curr->func(curr, mode, sync, key) &&

(flags & WQ\_FLAG\_EXCLUSIVE) && !--nr\_exclusive)

break;

\_\_wake\_up\_common循环遍历等待队列内的所有元素，分别执行其对应的唤醒函数。

这里的唤醒函数即先前定义等待队列项DEFINE\_WAIT(\_\_wait)时默认初始化的autoremove\_wake\_function函数。autoremove\_wake\_function最终会调用try\_to\_wake\_up函数将进程置为TASK\_RUNNING状态。这样后面的进程调度便会调度到该进程，从而唤醒该进程继续执行。

Reference:

1)OReilly.Understanding.the.Linux.Kernel.3rd.Edition.Nov.2005.HAPPY.NEW.YEAR

2)Linux 2.6.18\_Pro500 (Montavista)

[081024183145.jpg]: http://blogimg.chinaunix.net/blog/upfile2/081024183145.jpg