曲径通幽论坛

 找回密码
 立即注册
搜索
查看: 8633|回复: 5

等待队列中的双向链表建立分析

[复制链接]

4917

主题

5879

帖子

3万

积分

GROAD

曲径通幽,安觅芳踪。

Rank: 6Rank: 6

积分
34382
发表于 2011-3-4 12:43:46 | 显示全部楼层 |阅读模式
等待队列是一个双向链表。主要构成由是一个等待队列头和多个等待队列结构组成。


在内核中,add_wait_queue() 函数用于将一个等待进程添加到等待队列中,该函数定义为:
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);
}

该函数在获得必要的自旋锁后,调用 __add_wait_queue() 函数来完成这道工作,__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);
}



list_add 是标准链表操作函数,它定义为:

/**
* list_add - add a new entry
* @new: new entry to be added
* @head: list head to add it after
*
* Insert a new entry after the specified head.
* This is good for implementing stacks.
*/

static inline void list_add(struct list_head *new, struct list_head *head)
{
    __list_add(new, head, head->next);
}

从上面的注释注意到,链表的添加是一种堆栈式添加的,按照添加的规则是先进后出,后进先出。那么可以想象,后来的节点是添加到链表头的。


__list_add() 定义为:
static inline void __list_add(struct list_head *new,
                  struct list_head *prev,
                  struct list_head *next)
{
    next->prev = new;
    new->next = next;
    new->prev = prev;
    prev->next = new;
}

从上面的代码可以看到,新添加的节点会插入到链表头和第一个节点中间


为了更直观的体现出链表的建立过程,我将相关的宏定义都挪倒用户态程序中,然后打印出链表中指针的指向地址,最后得出链表的结构。客户端代码如下:
#include <stdio.h>

struct list_head {
        struct list_head *next, *prev;
};

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

typedef struct __wait_queue {
        int a;
        int b;
        struct list_head task_list;
}wait_queue_t;

#define LIST_HEAD_INIT(name) { &(name), &(name) }

#define DEFINE_WAIT(name)                       \
        wait_queue_t name = {                   \
                .a = 7,                         \
                .b = 8,                         \
                .task_list = LIST_HEAD_INIT((name).task_list),  \
        }

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

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

static inline int list_empty(const struct list_head *head)
{
        return head->next == head;
}


static inline void __list_add(struct list_head *new,
                struct list_head *prev,
                struct list_head *next)
{
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
}

static inline void list_add(struct list_head *new, struct list_head *head)
{
        __list_add(new, head, head->next);
}

static inline void __add_wait_queue(wait_queue_head_t *head, wait_queue_t *new)
{
        list_add(&new->task_list, &head->task_list);
}

void prepare_to_wait (wait_queue_head_t *q, wait_queue_t *wait)
{
        if (list_empty(&wait->task_list))
                __add_wait_queue(q, wait);
}
int main(void)
{
        DECLARE_WAIT_QUEUE_HEAD(wq);
        printf ("header task_list address: 0x%x\n", &wq.task_list);
        printf ("header prev: 0x%x\n", wq.task_list.prev);
        printf ("header next: 0x%x\n", wq.task_list.next);

        printf ("------------list_add a new-------------\n\n");

        DEFINE_WAIT(__wait);
        prepare_to_wait (&wq, &__wait);
        printf ("header prev: 0x%x\n", wq.task_list.prev);
        printf ("header next: 0x%x\n", wq.task_list.next);
        printf ("first node task_list address: 0x%x\n", &__wait.task_list);
        printf ("first node prev: 0x%x\n", __wait.task_list.prev);
        printf ("first node next: 0x%x\n", __wait.task_list.next);

        printf ("------------list_add a new-------------\n");

        DEFINE_WAIT(second);
        prepare_to_wait (&wq, &second);
        printf ("header prev: 0x%x\n", wq.task_list.prev);
        printf ("header next: 0x%x\n", wq.task_list.next);
        printf ("first node prev: 0x%x\n", __wait.task_list.prev);
        printf ("first node next: 0x%x\n", __wait.task_list.next);
        printf ("second node task_list address: 0x%x\n", &second.task_list);
        printf ("second node prev: 0x%x\n", second.task_list.prev);
        printf ("second node next: 0x%x\n", second.task_list.next);

        printf ("------------list_add a new-------------\n");

        DEFINE_WAIT(third);
        prepare_to_wait (&wq, &third);
        printf ("header prev: 0x%x\n", wq.task_list.prev);
        printf ("header next: 0x%x\n", wq.task_list.next);
        printf ("first node prev: 0x%x\n", __wait.task_list.prev);
        printf ("first node next: 0x%x\n", __wait.task_list.next);
        printf ("second node prev: 0x%x\n", second.task_list.prev);
        printf ("second node next: 0x%x\n", second.task_list.next);
        printf ("third node task_list address: 0x%x\n", &third.task_list);
        printf ("third node prev: 0x%x\n", third.task_list.prev);
        printf ("third node next: 0x%x\n", third.task_list.next);

        return (0);
}

运行输出:
linux-kd1q:/home/beyes/C/micro # ./micro
header task_list address: 0xbfc6b3b8
header prev: 0xbfc6b3b8
header next: 0xbfc6b3b8
------------list_add a new-------------


header prev: 0xbfc6b3ac
header next: 0xbfc6b3ac
first node task_list address: 0xbfc6b3ac
first node prev: 0xbfc6b3b8
first node next: 0xbfc6b3b8
------------list_add a new-------------
header prev: 0xbfc6b3ac
header next: 0xbfc6b39c
first node prev: 0xbfc6b39c
first node next: 0xbfc6b3b8
second node task_list address: 0xbfc6b39c
second node prev: 0xbfc6b3b8
second node next: 0xbfc6b3ac
------------list_add a new-------------
header prev: 0xbfc6b3ac
header next: 0xbfc6b38c
first node prev: 0xbfc6b39c
first node next: 0xbfc6b3b8
second node prev: 0xbfc6b38c
second node next: 0xbfc6b3ac
third node task_list address: 0xbfc6b38c
third node prev: 0xbfc6b3b8
third node next: 0xbfc6b39c
首先,使用 DECLARE_WAIT_QUEUE_HEAD 宏静态的建立一个链表头,链表头的名字为 wq 。从第一次的输出:
header task_list address: 0xbfc6b3b8
header prev: 0xbfc6b3b8
header next: 0xbfc6b3b8

此时链表头的结构是:

list_head 结构体里面的指针都指向链表头自身。


下面添加第一个等待节点,从输出代码:
header prev: 0xbfc6b3ac
header next: 0xbfc6b3ac
first node task_list address: 0xbfc6b3ac
first node prev: 0xbfc6b3b8
first node next: 0xbfc6b3b8

我们可以得到如下的结构:

再添加第 2 个节点,从代码片段:
        next->prev = new;
        new->next = next;
        new->prev = prev;
        prev->next = new;
可以知道,第 2 个节点是插入到链表头和第 1 个节点之间的。比较输出结果中的:
header prev: 0xbfc6b3ac
header next: 0xbfc6b39c
first node prev: 0xbfc6b39c
first node next: 0xbfc6b3b8
second node task_list address: 0xbfc6b39c
second node prev: 0xbfc6b3b8
second node next: 0xbfc6b3ac

也能看出这一点。这时结构如下图所示:

从上图可知,这种节点的添加,犹如堆栈一样,最后进来的就成为了栈顶,先进去的节点则一层一层的往后推去。依次类推后面的节点。注意的是,链表头的 prev 永远指向最后一个节点;最后一个节点的 next 永远指向链表头。下面是一个更美观的图:

0

主题

7

帖子

0

积分

初学弟子

积分
0
发表于 2012-7-3 23:10:31 | 显示全部楼层
描述的真清晰。我想请教一下你使用什么工具画的图啊?我也想学习学习。

4917

主题

5879

帖子

3万

积分

GROAD

曲径通幽,安觅芳踪。

Rank: 6Rank: 6

积分
34382
 楼主| 发表于 2012-7-4 11:48:52 | 显示全部楼层

回 0x521 的帖子

0x521:描述的真清晰。我想请教一下你使用什么工具画的图啊?我也想学习学习。 (2012-07-03 23:10) 
也有 Windows 里的画图,还有 Linux 里的 GIMP 。

0

主题

7

帖子

0

积分

初学弟子

积分
0
发表于 2012-7-4 12:56:15 | 显示全部楼层
非常想知道倒数第二张图是用什么工具画的,麻烦分享一下啊,谢啦!

0

主题

7

帖子

0

积分

初学弟子

积分
0
发表于 2012-7-5 21:27:11 | 显示全部楼层

回 beyes 的帖子

beyes:也有 Windows 里的画图,还有 Linux 里的 GIMP 。 (2012-07-04 11:48) 
大侠,你的倒数第二张图是用什么工具画的啊?求解
您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

小黑屋|手机版|Archiver|曲径通幽 ( 琼ICP备11001422号-1|公安备案:46900502000207 )

GMT+8, 2024-3-29 18:27 , Processed in 0.085712 second(s), 22 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

快速回复 返回顶部 返回列表