源码解读Linux等待队列

等级 701 1 0

从源码角度来解读Linux等待队列机制,了解休眠与唤醒的运转原理

kernel/include/linux/wait.h
kernel/kernel/sched/wait.c
kernel/include/linux/sched.h
kernel/kernel/sched/core.c 

一、概述

Linux内核的等待队列是非常重要的数据结构,在内核驱动中广为使用,它是以双循环链表为基础数据结构,与进程的休眠唤醒机制紧密相联,是实现异步事件通知、跨进程通信、同步资源访问等技术的底层技术支撑。

研究等待队列这个内核非常基础的数据结构,对于加深理解Linux非常有帮忙,等待队列有两种数据结构:等待队列头(wait_queue_head_t)和等待队列项(wait_queue_t),两者都有一个list_head类型task_list。双向链表通过task_list将 等待队列头和一系列等待队列项串起来,源码如下所示。

二、等待队列

2.1 struct wait_queue_head_t

struct __wait_queue_head {
    spinlock_t        lock;  //用于互斥访问的自旋锁
    struct list_head    task_list;
};
typedef struct __wait_queue_head wait_queue_head_t; 

可通过宏DECLARE_WAIT_QUEUE_HEAD(name)来创建类型为wait_queue_head_t的等待队列头name。

#define DECLARE_WAIT_QUEUE_HEAD(name) \
    struct wait_queue_head name = __WAIT_QUEUE_HEAD_INITIALIZER(name)

#define __WAIT_QUEUE_HEAD_INITIALIZER(name) {                    \
    .lock        = __SPIN_LOCK_UNLOCKED(name.lock),            \
    .head        = { &(name).head, &(name).head } } 

2.2 struct wait_queue_t

struct __wait_queue {
    unsigned int        flags;
    void            *private;  //指向等待队列的进程task_struct
    wait_queue_func_t    func;  //唤醒函数
    struct list_head    task_list; //链表元素,将wait_queue_t挂到wait_queue_head_t
};
typedef struct __wait_queue wait_queue_t; 

可通过宏DECLARE_WAITQUEUE(name, tsk) 来创建类型为wait_queue_t的等待队列项name,并将tsk赋值给成员变量private, default_wake_function赋值给成员变量func。

#define DECLARE_WAITQUEUE(name, tsk)                        \
    struct wait_queue_entry name = __WAITQUEUE_INITIALIZER(name, tsk)

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

2.3 add_wait_queue

void 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);
}

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

该方法的功能是将wait等待队列项 挂到等待队列头q中。

2.4 remove_wait_queue

void 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);
}

static inline void __remove_wait_queue(wait_queue_head_t *head, wait_queue_t *old)
{
    list_del(&old->task_list);
} 

该方法主要功能是将wait等待队列项 从等待队列头q中移除。

到这里,已经介绍了wait_queue_head_t和wait_queue_t这两个创建方法,以及增加和删除等待队列元素的方法。接下里说一说如何在等待队列的基础上建立休眠与唤醒机制。

三、休眠与唤醒

3.1 wait_event

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

#define __wait_event(wq, condition)                    \
    (void)___wait_event(wq, condition, TASK_UNINTERRUPTIBLE, 0, 0, schedule()) 

将___wait_event()宏展开如下所示

___wait_event(wq, condition, state, exclusive, ret, cmd){  
    wait_queue_t __wait;                    
    INIT_LIST_HEAD(&__wait.task_list);                
    for (;;) {
        //当检测进程是否有待处理信号则返回值__int不为0,【见3.1.1】
        long __int = prepare_to_wait_event(&wq, &__wait, state);
        if (condition)  //当满足条件,则跳出循环                    
            break;                        

        //当有待处理信号且进程处于可中断状态(TASK_INTERRUPTIBLE或TASK_KILLABLE)),则跳出循环
        if (___wait_is_interruptible(state) && __int) {        
            __ret = __int;                    
            break;                      
        }                            
        cmd; //schedule(),进入睡眠,从进程就绪队列选择一个高优先级进程来代替当前进程运行                       
    }                                
    finish_wait(&wq, &__wait);  //如果__wait还位于队列wq,则将__wait从wq中移除              
} 

3.1.1 prepare_to_wait_event

再来看看进入睡眠状态之前的准备工作,用于防止wait没有队列中,而事件已产生,则会无线等待。

long prepare_to_wait_event(wait_queue_head_t *q, wait_queue_t *wait, int state)
{
    unsigned long flags;
    if (signal_pending_state(state, current)) //信号检测
        return -ERESTARTSYS;

    wait->private = current;
    wait->func = autoremove_wake_function; //设置func唤醒函数,【小节3.1.2】

    spin_lock_irqsave(&q->lock, flags);
    if (list_empty(&wait->task_list)) {  //当wait不在队列q,则加入其中,防止无法唤醒
        if (wait->flags & WQ_FLAG_EXCLUSIVE)
            __add_wait_queue_tail(q, wait);
        else
            __add_wait_queue(q, wait);
    }
    set_current_state(state);  //设置进程状态
    spin_unlock_irqrestore(&q->lock, flags);

    return 0;
} 

wait_event(wq, condition):进入睡眠状态直到condition为true,在等待期进程状态为TASK_UNINTERRUPTIBLE。对应的唤醒方法是wake_up(),当等待队列wq被唤醒时会执行如下两个检测:

  • 检查condition是否为true,满足条件,则跳出循环。
  • 检测该进程task的成员thread_info->flags是否被设置TIF_SIGPENDING,被设置则说明有待处理的信号,则跳出循环。

wait_event_xxx有一组用于睡眠的函数,基于是否可中断(TASK_UNINTERRUPTIBLE),是否有超时机制,在方法名后缀加上interruptible,timeout等信息,对应的含义就是允许中断(TASK_INTERRUPTINLE)和带有超时机制,比如wait_event_interruptible(),这里就不再列举。另外sleep_on()也是进入睡眠状态,没有condition,不过该方法有可能导致竞态,从kernel 3.15移除该方法,采用wait_event代替sleep_on()。

3.1.2 autoremove_wake_function

int autoremove_wake_function(wait_queue_t *wait, unsigned mode, int sync, void *key)
{
    int ret = default_wake_function(wait, mode, sync, key); //唤醒函数
    if (ret)
        list_del_init(&wait->task_list); //从列表中移除wait
    return ret;
} 

3.2 wake_up

#define wake_up(x)            __wake_up(x, TASK_NORMAL, 1, NULL)


void __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);
}


static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
            int nr_exclusive, int wake_flags, void *key)
{
    wait_queue_t *curr, *next;

    list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
        unsigned flags = curr->flags;
        //调用唤醒函数 【小节3.2.1】
        if (curr->func(curr, mode, wake_flags, key) &&
                (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
            break;
    }
} 

wait_event(wq)遍历整个等待列表wq中的每一项wait_queue_t,依次调用唤醒函数来唤醒该等待队列中的所有项,唤醒函数如下:

  • 对于通过宏DECLARE_WAITQUEUE(name, tsk) 来创建wait,再调用add_wait_queue(wq, wait)方法,则唤醒函数为default_wake_function
  • 对于通过wait_event(wq, condition)方式加入的wait项,则经过调用prepare_to_wait_event()方法,则唤醒函数为autoremove_wake_function,由小节[1.3.5]可知,该方法主要还是调用default_wake_function来唤醒。

wake_up_xxx有一组用于唤醒的函数,跟wait_event配套使用。比如wait_event()与wake_up(),wait_event_interruptible()与wake_up_interruptible()。

3.2.1 default_wake_function

再来看看唤醒函数函数

int default_wake_function(wait_queue_t *curr, unsigned mode, int wake_flags,
              void *key)
{
    //获取wait所对应的进程 【小节3.2.2】
    return try_to_wake_up(curr->private, mode, wake_flags);
} 

3.2.2 try_to_wake_up

try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
{
    unsigned long flags;
    int cpu, src_cpu, success = 0;

    bool freq_notif_allowed = !(wake_flags & WF_NO_NOTIFIER);
    bool check_group = false;
    wake_flags &= ~WF_NO_NOTIFIER;

    smp_mb__before_spinlock();
    raw_spin_lock_irqsave(&p->pi_lock, flags); //关闭本地中断
    src_cpu = cpu = task_cpu(p);

    //如果当前进程状态不属于可唤醒状态集,则无法唤醒该进程
    //wake_up()传递过来的TASK_NORMAL等于(TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE)
    if (!(p->state & state)) 
        goto out;

    success = 1; 
    smp_rmb();
    if (p->on_rq && ttwu_remote(p, wake_flags)) //当前进程已处于rq运行队列,则无需唤醒
        goto stat;
    ...

    ttwu_queue(p, cpu); //【小节3.2.3】
stat:
    ttwu_stat(p, cpu, wake_flags);
out:
    raw_spin_unlock_irqrestore(&p->pi_lock, flags); //恢复本地中断
    ...
    return success;
} 

3.2.3 ttwu_queue

static void ttwu_queue(struct task_struct *p, int cpu)
{
    struct rq *rq = cpu_rq(cpu); // 获取当前进程的运行队列
    raw_spin_lock(&rq->lock);
    lockdep_pin_lock(&rq->lock);
    ttwu_do_activate(rq, p, 0); // 【小节3.2.4】
    lockdep_unpin_lock(&rq->lock);
    raw_spin_unlock(&rq->lock);
} 

在kernel/sched/core.c目录中发现有大量ttwu_xxx的方法,这个单词缩写可真是厉害,琢磨一会结合上下文,才明白原来是try to wake up的缩写,另外为了简化,这里只介绍单处理器的逻辑。

3.2.4 ttwu_do_activate

static void ttwu_do_activate(struct rq *rq, struct task_struct *p, int wake_flags)
{
    ttwu_activate(rq, p, ENQUEUE_WAKEUP | ENQUEUE_WAKING);
    ttwu_do_wakeup(rq, p, wake_flags);
}

static inline void ttwu_activate(struct rq *rq, struct task_struct *p, int en_flags)
{
    activate_task(rq, p, en_flags); //将进程task加入rq队列
    p->on_rq = TASK_ON_RQ_QUEUED;

    if (p->flags & PF_WQ_WORKER)
        wq_worker_waking_up(p, cpu_of(rq)); //worker正在唤醒中,则通知工作队列
}

static void ttwu_do_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
{
    check_preempt_curr(rq, p, wake_flags);
    p->state = TASK_RUNNING; //标记该进程为TASK_RUNNING状态
    ...
} 

四、总结

通过DECLARE_WAIT_QUEUE_HEAD(name)可初始化wait_queue_head_t结构体,通过DECLARE_WAITQUEUE可初始化wait_queue_t结构体,由等待队列头(wait_queue_head_t)和等待队列项(wait_queue_t)构建一个双向链表。 可通过add_wait_queue和remove_wait_queue分别向双向链表中添加或删除等待项。

休眠与唤醒流程:

  1. 进程A调用wait_event(wq, condition)就是向等待队列头中添加等待队列项wait_queue_t,该该等待队列项中的成员变量private记录当前进程,其成员变量func记录唤醒回调函数,然后调用schedule()使当前进程进入休眠状态。
  2. 进程B调用wake_up(wq)会遍历整个等待列表wq中的每一项wait_queue_t,依次调用每一项的唤醒函数try_to_wake_up()。这个过程会将private记录的进程加入rq运行队列,并设置进程状态为TASK_RUNNING。
  3. 进程A被唤醒后只执行如下检测:
    • 检查condition是否为true,满足条件则跳出循环,再把wait_queue_t从wq队列中移除;
    • 检测该进程task的成员thread_info->flags是否被设置TIF_SIGPENDING,被设置则说明有待处理的信号,则跳出循环,再把wait_queue_t从wq队列中移除;
    • 否则,继续调用schedule()再次进入休眠等待状态,如果wait_queue_t不在wq队列,则再次加入wq队列。

本文转自 http://gityuan.com/2018/12/02/linux-wait-queue/,如有侵权,请联系删除。

收藏
评论区

相关推荐

Linux使用 常见经验和技巧总结
1.XShell连接远程Linux服务器并运行程序后关闭XShell继续执行XShell是用来连接远程Linux很好的工具,在连接之后并运行好需要运行的程序后,往往需要关闭XShell,但是直接运行比如运行python crawler.py运行一个Python爬虫程序后,并直接关闭XShell往往会同时杀掉正在运行的爬虫程序,因此需要使用sudo
源码解读Linux等待队列
从源码角度来解读Linux等待队列机制,了解休眠与唤醒的运转原理kernel/include/linux/wait.hkernel/kernel/sched/wait.ckernel/include/linux/sched.hkernel/kernel/sched/core.c 一、概述Linux内核的等待队列是非常重要的数据结构,在内核驱动中广为使用,它是
Java程序员必须掌握的常用Linux命令。
点击上方蓝色文字关注↑↑↑↑↑ ![](https://oscimg.oschina.net/oscnet/2ab1caa1-208a-4204-9d64-b55b0b38f09f.jpg) Java程序员也是半个运维了,在日常开发中经常会接触到Linux环境操作。小公司的开发人员甚至是兼了全运维的工作,下面整理了一些常用的Linux操作命令。 *
28个企业运维岗经典面试题,你能回答多少?
![](https://oscimg.oschina.net/oscnet/dd3f36b3-da04-45a0-accd-f2a0059b5edb.gif) ![](https://oscimg.oschina.net/oscnet/a08b06e1-2f8d-40fb-b0a2-f7f0181f4d87.jpg) 作者:运维派 来源:http://
Linux 运维 9月30日 笔记 6.1
目录 一、压缩打包介绍 二、gzip压缩工具 三、bzip2压缩工具 四、xz压缩工具 **一、压缩打包介绍** 1. 常见压缩文件 * Windows .rar .zip. 7z * Linux .zip .gz .bz2 .xz .tar  **二、gzip压缩工具**
Linux 运维是做什么的
![](https://oscimg.oschina.net/oscnet/up-25a98115c12319b11895484bc9dd5ecd170.png) Linux在现在社会发展是非常受欢迎的一个行业,对于从事Linux方面工作的人来说,属于互联网背后的英雄,没有他们的付出,就没有如今的互联网时代。而在Linux从事岗位之中,Linux运维工程师
Linux云计算工程师
**一、[Linux运维基础](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fwww.cnblogs.com%2Fyxiaodao%2Fp%2F10275366.html)** **二、[Linux运维高级-核心知识提高](https://www.oschina.net/action/G
Linux日常运维小结
**1\. 如何看当前Linux系统有几颗物理CPU和每颗CPU的核数?** 物理cpu个数:cat /proc/cpuinfo |grep -c 'physical id' CPU一共有多少核:grep -c processor /proc/cpuinfo 将CPU的总核数除以物理CPU的个数,得到每颗CPU的核数。 **2\. 查看系统负载有两个常用的命
Linux系统与服务构建运维
Linux系统与服务构建运维 1+x初级,项目三 FTP服务的使用 ======== ### 配置YUM源 #### 将CD设备进行连接 ![](https://img2020.cnblogs.com/blog/1893874/202005/1893874-20200508194528832-718337495.png) #### 将CD设备挂载
Linux菜鸟到老鸟的那些建议
相信很多同学对[Linux](https://www.oschina.net/action/GoToLink?url=https%3A%2F%2Fwww.linuxprobe.com%2Fchapter-00.html)的认识并不多,平常接触的也不多,对Linux的开发运维等也是一无所知。如今,如果要做一名优秀的程序猿,掌握Linux知识已经是一门必备技能了
Linux运维常用命令详解
1、ls 文件属性:  -:普通文件  d:目录文件  b:块设备  c:字符设备文件  l:符号连接文件  p:命令管道  s:套接字文件  文件权限: 9位数字,每3位一组  文件硬链接次数  文件所属主(owner)  文件的属组(group)  文件大小(size),单位默认是字节  ls常用选项: -l:显示文件属性,ls -l=ll 
Linux运维常见故障排查和处理的技巧汇总
![](https://oscimg.oschina.net/oscnet/e1b447c0-2806-447a-9930-7351cd397e4f.gif) ![](https://oscimg.oschina.net/oscnet/02a88775-b9ed-430b-b43f-fba5122d45bf.jpg) 作为Linux运维,工作中多多少少会
Linux运维常见面试题之精华收录
Linux运维常见面试题之精华收录 ================= **1、什么是运维?什么是游戏运维?** 1)运维是指大型组织已经建立好的网络软硬件的维护,就是要保证业务的上线与运作的正常, 在他运转的过程中,对他进行维护,他集合了网络、系统、数据库、开发、安全、监控于一身的技术 运维又包括很多种,有DBA运维、网站运维、虚
Linux运维高级篇—CentOS 7下Postfix邮件服务器搭建
第一章 实验环境 1. 硬件环境: Linux服务器一台,IP地址:192.168.80.10; WIN7客户端一台,拥有OUTLOOK2013,测试用,与服务器在同一局域网内。 2. Linux系统环境,如下图: ![Linux运维高级篇—CentOS 7下Postfix邮件服务器搭建]