标签：head 队列 内核 wq linux 进程 entry wait

一 背景和意义

在实际编程中，我们会经常碰到这种场景：进程P需要等待条件C的成立，才能继续执行某个动作。例如，当串口没有数据可以读取时，我们可以通过轮询的方式，等到有数据来的时候，串口程序再去读取。但是这种方式显得比较笨拙，影响CPU的性能。因此，内核中提供了等待队列的方式，即可以将进程P先挂到等待队列Q（wait_queue）上去，并将进程的状态由RUNNING切换为睡眠状态，主动让出CPU，直到条件满足时，由内核调用wake_up（）接口，自动唤醒Q上的所有进程，这样进程P就继续执行。

因此，wait_queue的实现，能够提高整个系统以及CPU运行的效率。

二 数据结构分析

wait_queue使用到的数据结构很简单，就是使用内核链表，将等待同一事件的所有进程串联起来。

第一个数据结构是等待队列头：

struct wait_queue_head {
    spinlock_t      lock;        \\用于同步的自旋锁
    struct list_head    head;    \\等待队列头
};
typedef struct wait_queue_head wait_queue_head_t;

 

等待队列头可以用以下API进行初始化：

wait_queue_head_t wait_queue_head;
init_waitqueue_head(&wait_queue_head);

 

第二个数据结构是等待队列的队列元素：

struct wait_queue_entry {                                                                                 
    unsigned int        flags; // 最低位为1代表互斥进程，其他代表非互斥进程
    void            *private;  //一般用于指向当前进程，即设置为current指针
    wait_queue_func_t   func;  //唤醒方式
    struct list_head    entry; //用于链表管理
};

/* wait_queue_entry::flags */ #define WQ_FLAG_EXCLUSIVE   0x01 #define WQ_FLAG_WOKEN       0x02 #define WQ_FLAG_BOOKMARK    0x04 #define WQ_FLAG_CUSTOM      0x08 #define WQ_FLAG_DONE        0x10 #define WQ_FLAG_PRIORITY    0x20

 

这里，睡眠进程被分成两种，最低位为1代表的是互斥进程，这些进程在唤醒时会被有选择地唤醒；其他代表的是非互斥进程，唤醒时，内核将唤醒所有的非互斥进程。

当多个进程等待互斥资源时，同时唤醒所有进程将会导致又一次的竞争，而只有一个进程会获得互斥资源，因此其他进程又必须重新睡眠。为了避免以上的情况，才定义了互斥进程的概念，并使用flags来区分互斥进程和非互斥进程。

func字段是进程被唤醒的方式，默认会被初始化为default_wake_function(）。

可以使用以下API对等待队列的队列元素进行动态的初始化：

struct wait_queue_entry wait_entry;
init_wait(&wait_entry);

或者使用静态的初始化方法：

DEFINE_WAIT(wait_entry);

以上两种方式的结果相同，以init_wait 为例：

#define DEFINE_WAIT_FUNC(name, function)                    \
    struct wait_queue_entry name ={     \ 
        .private    = current,                  \
        .func       = function,                 \
        .entry      = LIST_HEAD_INIT((name).entry),         \
    }
 
#define DEFINE_WAIT(name) DEFINE_WAIT_FUNC(name, autoremove_wake_function)

 

等待队列头和等待队列的关系图

 

 

三 等待队列的操作

3.1 典型应用

/* 1. 定义一个等待队列项 */
DEFINE_WAIT(wait);
/* 2. 将等待队列项wait插入等待队列wq中，并将进程的状态设置为INTERRUPTIBLE */
prepare_to_wait(&wq, &wait, TASK_INTERRUPTIBLE);
...
/* 3. 如果期望的条件不满足，则主动让出CPU，切换其他进程运行 */
if (!condition)
    schedule();
/* 
 * 4. 进程被唤醒后，继续向下执行，将进程的状态设置为运行状态，并将等待队列项wait从等待队列wq中删除。
 */
finish_wait(&wq, &wait);
 

3.2 将等待队列项插入等待队列

一般，定义并初始化完等待队列后，需要通过prepare_to_wait() 或者 prepare_to_wait_exclusive ()函数，将进程的状态改变，并将其加入对应的等待队列中：

void
prepare_to_wait(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
{
    unsigned long flags;
 
    wq_entry->flags &= ~WQ_FLAG_EXCLUSIVE;
    spin_lock_irqsave(&wq_head->lock, flags);
    if (list_empty(&wq_entry->entry))
        __add_wait_queue(wq_head, wq_entry);
    set_current_state(state);
    spin_unlock_irqrestore(&wq_head->lock, flags);
}
EXPORT_SYMBOL(prepare_to_wait);
 
void
prepare_to_wait_exclusive(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry, int state)
{
    unsigned long flags;
 
    wq_entry->flags |= WQ_FLAG_EXCLUSIVE;
    spin_lock_irqsave(&wq_head->lock, flags);
    if (list_empty(&wq_entry->entry))
        __add_wait_queue_entry_tail(wq_head, wq_entry);
    set_current_state(state);
    spin_unlock_irqrestore(&wq_head->lock, flags);
}
EXPORT_SYMBOL(prepare_to_wait_exclusive);

从以上源码可以看出，prepare_to_wait() 或者 prepare_to_wait_exclusive ()函数有以下区别：

1. prepare_to_wait_exclusive ()函数会将等待队列项对应的flags的WQ_FLAG_EXCLUSIVE使能，也就是说，通过prepare_to_wait_exclusive ()函数添加的等待队列项，对应的进程被设置为互斥进程；而通过prepare_to_wait()添加的等待队列项，对应的进程被设置为非互斥进程。

2. 通过prepare_to_wait()添加的非互斥等待队列项，会被添加至等待队列的队头，而通过 prepare_to_wait_exclusive ()函数添加的互斥项，会被添加至等待队列的队尾。

二者都会改变当前进程的状态，由传入的参数state 决定。

3.3 将等待队列从等待队列中删除

当进程被唤醒后，一般会直接调用finish_wait函数，将进程的状态重新设置为running，并将该进程对应的等待队列项从等待队列中删除：

void finish_wait(struct wait_queue_head *wq_head, struct wait_queue_entry *wq_entry)
{
    unsigned long flags;
 
    __set_current_state(TASK_RUNNING);
    /*
    ¦* We can check for list emptiness outside the lock
    ¦* IFF:
    ¦*  - we use the "careful" check that verifies both
    ¦*    the next and prev pointers, so that there cannot
    ¦*    be any half-pending updates in progress on other
    ¦*    CPU's that we haven't seen yet (and that might
    ¦*    still change the stack area.
    ¦* and
    ¦*  - all other users take the lock (ie we can only
    ¦*    have _one_ other CPU that looks at or modifies
    ¦*    the list).
    ¦*/
    if (!list_empty_careful(&wq_entry->entry)) {
        spin_lock_irqsave(&wq_head->lock, flags);
        list_del_init(&wq_entry->entry);
        spin_unlock_irqrestore(&wq_head->lock, flags);
    }
}

3.4 将等待队列从等待队列中删除

唤醒等待队列上的进程：

一般，可以通过wake_up, wake_up_all等API对唤醒队列上的进程进行唤醒。wake_up将会唤醒所有的非互斥进程，而只唤醒一个互斥进程； wake_up_all将会唤醒所有的非互斥进程，和所有的互斥进程。其他API可以参看内核源码。

 

标签：head,队列,内核,wq,linux,进程,entry,wait
From： https://www.cnblogs.com/god-of-death/p/17343866.html