Linux系统中的”队列”是什么？Linux “队列”相关总结

学习linux内核相关的代码的时候，经常遇到跟"队列“相关的名词。或许你并不是很理解这个“队列”到时是个什么鬼，今天我们一起来看看。

首先总结一下跟“队列”有关的名词：

1：等待队列

2：工作队列

3：请求队列

一：等待队列

在内核里面，等待队列是有很多用处的，尤其是在中断处理、进程同步、定时等场合。

可以使用等待队列在实现阻塞进程的唤醒。它以队列为基础数据结构，与进程调度机制紧密结合，

能够用于实现内核中的异步事件通知机制，同步对系统资源的访问等。

涉及到的数据结构包括：

struct __wait_queue {

unsigned int flags;

#define WQ_FLAG_EXCLUSIVE 0x01

void *private;

wait_queue_func_t func; //为一个函数指针typedef int (*wait_queue_func_t)(wait_queue_t *wait, unsigned mode, int flags, void *key);

struct list_head task_list; //用来将wait_queue_func_t链起来

};

struct __wait_queue_head {

spinlock_t lock;

struct list_head task_list; //双向循环链表，存放等待的进程。

};

typedef struct __wait_queue_head wait_queue_head_t; //定义了等待队列头

其中

等待队列(wait_queue_t)和等待对列头(wait_queue_head_t)的区别是等待队列是等待队列头的成员。

也就是说等待队列头的task_list域链接的成员就是等待队列类型的(wait_queue_t)。

1、定义并初始化等待队列头：有俩种方法

(1)

wait_queue_head_t my_queue;

init_waitqueue_head(&my_queue);

直接定义并初始化。init_waitqueue_head()函数会将自旋锁初始化为未锁，等待队列初始化为空的双向循环链表。

(2)

DECLARE_WAIT_QUEUE_HEAD(my_queue);

定义并初始化，相当于(1)。

2、定义等待队列项：

DECLARE_WAITQUEUE(name,tsk);

其定义如下：

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

#define __WAITQUEUE_INITIALIZER(name, tsk) { \

.private = tsk, \

.func = default_wake_function, \

.task_list = { NULL, NULL } }

从上面的定义可以知道，DECLARE_WAITQUEUE(name,tsk)主要定义了变量name，并对private数据项进行了赋值。

3、(从等待队列头中)添加/移出等待队列项：

(1)add_wait_queue()函数：

void fastcall add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)

函数将wait_queue_t添加到wait_queue_head_t中。

(2)remove_wait_queue()函数：

void fastcall remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)

在等待的资源或事件满足时，进程被唤醒，使用该函数被从等待头中删除。

4、等待事件：

(1)wait_event()宏：

在等待队列中睡眠直到condition为真。在等待的期间，进程会被置为TASK_UNINTERRUPTIBLE进入睡眠，直到condition变量变为真。每次进程被唤醒的时候都会检查condition的值.

(2)wait_event_interruptible()函数:

和wait_event()的区别是调用该宏在等待的过程中当前进程会被设置为TASK_INTERRUPTIBLE状态.在每次被唤醒的时候,首先检查condition是否为真,如果为真则返回,否则检查如果进程是被信号唤醒,会返回-ERESTARTSYS错误码.如果是condition为真,则返回0.

(3)wait_event_timeout()宏:

也与wait_event()类似.不过如果所给的睡眠时间为负数则立即返回.如果在睡眠期间被唤醒,且condition为真则返回剩余的睡眠时间,否则继续睡眠直到到达或超过给定的睡眠时间,然后返回0.

(4)wait_event_interruptible_timeout()宏:

与wait_event_timeout()类似,不过如果在睡眠期间被信号打断则返回ERESTARTSYS错误码.

(5) wait_event_interruptible_exclusive()宏

同样和wait_event_interruptible()一样,不过该睡眠的进程是一个互斥进程.

5、唤醒队列:

(1)wake_up()函数:

唤醒等待队列.可唤醒处于TASK_INTERRUPTIBLE和TASK_UNINTERUPTIBLE状态的进程,和wait_event/wait_event_timeout成对使用.

(2)wake_up_interruptible()函数:

#define wake_up_interruptible(x) __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)

和wake_up()唯一的区别是它只能唤醒TASK_INTERRUPTIBLE状态的进程,

与wait_event_interruptible/wait_event_interruptible_timeout/ wait_event_interruptible_exclusive成对使用.

(3)

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

#define wake_up_interruptible_nr(x, nr) __wake_up(x, TASK_INTERRUPTIBLE, nr, NULL)

#define wake_up_interruptible_all(x) __wake_up(x, TASK_INTERRUPTIBLE, 0, NULL)

这些也基本都和wake_up/wake_up_interruptible一样.

6、在等待队列上睡眠：

(1)sleep_on()函数:

(2)sleep_on_timeout()函数：

long __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)

与sleep_on()函数的区别在于调用该函数时，如果在指定的时间内(timeout)没有获得等待的资源就会返回。实际上是调用schedule_timeout()函数实现的。值得注意的是如果所给的睡眠时间(timeout)小于0，则不会睡眠。该函数返回的是真正的睡眠时间。

(3)interruptible_sleep_on()函数：

void __sched interruptible_sleep_on(wait_queue_head_t *q)

该函数和sleep_on()函数唯一的区别是将当前进程的状态置为TASK_INTERRUPTINLE，这意味在睡眠如果该进程收到信号则会被唤醒。

(4)interruptible_sleep_on_timeout()函数：

类似于sleep_on_timeout()函数。进程在睡眠中可能在等待的时间没有到达就被信号打断而被唤醒，也可能是等待的时间到达而被唤醒。

以上四个函数都是让进程在等待队列上睡眠，不过是小有诧异而已。

在实际用的过程中，根据需要选择合适的函数使用就是了。

例如在对软驱数据的读写中，如果设备没有就绪则调用sleep_on()函数睡眠直到数据可读(可写),在打开串口的时候，如果串口端口处于关闭状态则调用interruptible_sleep_on()函数尝试等待其打开。

在声卡驱动中，读取声音数据时，如果没有数据可读，就会等待足够常的时间直到可读取。

二：工作队列

在linux中断处理中，有上半部和下半部之分，在下半部中主要来处理比较耗时的操作，其主要由工作队列workqueue来完成。

Linux 2.6内核使用了不少工作队列来处理任务，他在使用上和 tasklet最大的不同是工作队列的函数可以使用休眠，而tasklet的函数是不允许使用休眠的。

工作队列的使用又分两种情况，

一种是利用系统共享的工作队列来添加自己的工作，这种情况处理函数不能消耗太多时间，这样会影响共享队列中其他任务的处理;

另外一种是创建自己的工作队列并添加工作。

我们把推后执行的任务叫做工作(work)，其数据结构为work_struct。

这些工作以队列结构组织成工作队列(workqueue)，其数据结构为workqueue_struct，而工作线程就是负责执行工作队列中的工作。系统默认的工作者线程为events,自己也可以创建自己的工作者线程。

首先来看看这俩个重要的数据结构：work_struct 和 workqueue_struct。

struct workqueue_struct {

struct cpu_workqueue_struct *cpu_wq;

struct list_head list;

const char *name;

int singlethread;

int freezeable; /* Freeze threads during suspend */

int rt;

#ifdef CONFIG_LOCKDEP

struct lockdep_map lockdep_map;

#endif

};

struct work_struct {

atomic_long_t data;

#define WORK_STRUCT_PENDING 0 /* T if work item pending execution */

#define WORK_STRUCT_FLAG_MASK (3UL)

#define WORK_STRUCT_WQ_DATA_MASK (~WORK_STRUCT_FLAG_MASK)

struct list_head entry;

work_func_t func; //typedef void (*work_func_t)(struct work_struct *work);为函数指针

#ifdef CONFIG_LOCKDEP

struct lockdep_map lockdep_map;

#endif

};

系统默认workqueue_struct定义如下

static struct workqueue_struct *keventd_wq __read_mostly;

keventd_wq = create_workqueue("events"); //名字为events

工作队列的创建方法：将work_struct添加到系统默认的工作队列中，添加work_struct到自定义的队列中

(1)：将work_struct添加到系统默认的工作队列中

a：声明或编写一个工作处理函数

void my_func(void *data); //相当与一个任务处理函数task()，会周期性的执行。

b：在创建工作work_struct时候，有俩种方法，即编译时和运行时。

编译时

创建名为my_work的结构体变量并把函数入口地址和参数地址赋给它;

创建一个工作结构体变量，并将处理函数和参数的入口地址赋给这个工作结构体变量

DECLARE_WORK(my_work,my_func,&data);

运行时

struct work_struct my_work; //创建一个名为my_work的结构体变量，创建后才能使用INIT_WORK()

INIT_WORK(&my_work,my_func,&data); //初始化已经创建的my_work，其实就是往这个结构体变量中添加处理函数的入口地址和data的地址，通常在驱动的open函数中完成

c：将工作结构体变量添加入系统的共享工作队列

schedule_work(&my_work); //添加my_work到keventd_wq中，一旦其所在的处理器上的工作者线程被唤醒，它就会被执行。

或有时候并不希望工作马上就被执行，而是希望它经过一段延迟以后再执行。

在这种情况下，可以调度它在指定的时间执行：

schedule_delayed_work(&my_work,tick); //延时tick个滴答后再提交工作这时，&my_work指向的work_struct直到delay指定的时钟节拍用完以后才会执行。

(2):创建自己的工作队列来添加工作

a：声明工作处理函数和一个指向工作队列的指针

void my_func(void *data); //相当与一个任务处理函数task()，会周期性的执行。

b：创建自己的工作队列和工作结构体变量(通常在open函数中完成)

struct workqueue_struct *p_queue;

p_queue=create_workqueue("my_queue"); //创建一个名为my_queue的工作队列并把工作队列的入口地址赋给声明的指针

struct work_struct my_work;

INIT_WORK(&my_work,my_func,&data); //创建一个工作结构体变量并初始化，和第一种情况的方法一样

c：将工作添加入自己创建的工作队列等待执行

queue_work(p_queue,&my_work);

//作用与schedule_work()类似，不同的是将工作添加入p_queue指针指向的工作队列而不是系统共享的工作队列

d：删除自己的工作队列

destroy_workqueue(p_queue); //一般是在close函数中删除

其工作队列的使用方法，可以参考linux中scsi_tgt_if.c函数中的代码。

static void scsi_tgt_cmd_done(struct scsi_cmnd *cmd)

{

struct scsi_tgt_cmd *tcmd = cmd->request->end_io_data;

dprintk("cmd %p %u\n", cmd, rq_data_dir(cmd->request));

scsi_tgt_uspace_send_status(cmd, tcmd->itn_id, tcmd->tag);

scsi_release_buffers(cmd);

queue_work(scsi_tgtd, &tcmd->work); // scsi_tgtd = create_workqueue("scsi_tgtd");

}