正如list_head结构那样，等待队列(wait queue)作为linux内核中的基础数据结构，与进程调度紧密结合在一起；在驱动程序中，常常使用等待队列来实现进程的阻塞和进程的唤醒。因此，我们很有必要对它的内部实现进行分析。

0.数据结构

一般我们的链式线性表都会有一个头结点，以使我们迅速找到这个线性链表的“领导”。在等待队列中，同样有队列头，只不过等待队列头和普通的等待队列结点定义有所不同。

  
 //yoursource/include/linux/wait.h
 50struct __wait_queue_head {
  51        spinlock_t lock;
  52        struct list_head task_list;
  53};
  54typedef struct __wait_queue_head wait_queue_head_t;

可以看到，等待队列头结构中封装了list_head结构。这么做是可以想象到的，因为队列和栈本质上还是双联表。当我们适当限制双联表的某些操作时，就可以实现这样的功能。另外，等待队列头结构中还有一个自旋锁结构的变量lock，它起到了对等待队列进行互斥操作的作用。

在等待队列结构中，除了使用list_head结构外，还有以下几个字段：

  28typedef struct __wait_queue wait_queue_t;
  32struct __wait_queue {
  33        unsigned int flags;
  34#define WQ_FLAG_EXCLUSIVE       0x01
  35        void *private;
  36        wait_queue_func_t func;
  37        struct list_head task_list;
  38};

flag：指明该等待的进程是互斥还是非互斥，为0时非互斥，为1时互斥；
WQ_FLAG_EXCLUSIVE ：从变量可以看出，此宏代表进程是互斥的；
private：void型指针变量功能强大，你可以赋给它你需要的结构体指针。一般赋值为task_struct类型的指针，也就是说指向一个进程；
func：函数指针，指向该等待队列项的唤醒函数；

我们可以通过下述图来详细了解等待队列头和等待队列的结构关系：

1.定义及初始化

内核中使用init_waitqueue_head宏来初始化等待队列头。

//yourLinuxSourceDir/include/linux/wait.h
  82#define init_waitqueue_head(q)                          \
  83        do {                                            \
  84                static struct lock_class_key __key;     \
  85                                                        \
  86                __init_waitqueue_head((q), &__key);     \
  87        } while (0)

我们可以看到这个宏使用了do-while型循环语句，里面包含两条语句。首先定义了一个变量__key，然后再调用init_waitqueue_head函数。

事实上，这个do-while循环语句只会执行一次。那么，为什么要选择使用这个循环语句？在定义宏的时候将上述语句嵌套在一个大括号里也可以啊！可能我们如下那样使用一个宏：

 10         if(conditon)
 11                 init_waitqueue_head(q);
 12         else
 13                 do_somthing_else();

如果我们去除do-while，那么替换后会编译错误。因为宏末尾的分号使得else语句成为一个单独的句子。你也许会说，那我这样使用：init_waitqueue_head(q)就可以避免这个错误了。这样是可以，但是对于那些初学者来说，很难避免他们要加上一个;。并且，在茫茫代码中，孤零零的出现一个没有;的语句，未免显得有些奇怪。

言归正传，在init_waitqueue_head宏中调用的__init_waitqueue_head函数定义如下：

 13void __init_waitqueue_head(wait_queue_head_t *q, struct lock_class_key *key)
  14{
  15        spin_lock_init(&q->lock);
  16        lockdep_set_class(&q->lock, key);
  17        INIT_LIST_HEAD(&q->task_list);
  18}

在这个函数中，首先利用自旋锁初始化函数初始化这个自旋锁；在上述等待队列头的定义中，我们可以看到task_list字段是一个list_head结构类型，因此我们使用INIT_LIST_HEAD对这个链表进行初始化。这些过程都是我们所熟悉的。

同时，我们也可以使用初始化宏DECLARE_WAIT_QUEUE_HEAD一步的进行定义和初始化。

  70#define __WAIT_QUEUE_HEAD_INITIALIZER(name) {                           \
  71        .lock           = __SPIN_LOCK_UNLOCKED(name.lock),              \
  72        .task_list      = { &(name).task_list, &(name).task_list } }
  73
  74#define DECLARE_WAIT_QUEUE_HEAD(name) \
  75        wait_queue_head_t name = __WAIT_QUEUE_HEAD_INITIALIZER(name)

上述代码对于有C基础的人理解起来并不困难。需要注意的是对task_list进行赋值后，这个结点的前后指针都会指向自己。

同样，对于等待队列，我们可以使用DECLARE_WAITQUEUE宏来定义并初始化一个等待队列项。

  30int default_wake_function(wait_queue_t *wait, unsigned mode, int flags, void *key);
  62#define __WAITQUEUE_INITIALIZER(name, tsk) {                            \
  63        .private        = tsk,                                          \
  64        .func           = default_wake_function,                        \
  65        .task_list      = { NULL, NULL } }
  66
  67#define DECLARE_WAITQUEUE(name, tsk)                                    \
  68        wait_queue_t name = __WAITQUEUE_INITIALIZER(name, tsk)

name要定义的等待队列项的名称；tsk是task_struct类型的指针变量，它指向这个等待队列项所对应的进程。

3.添加/移除等待队列

add_wait_queue添加函数将等待队列wait添加到以q为等待队列头的那个等待队列链表中。

22void add_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
23{
24        unsigned long flags;
25
26        wait->flags &= ~WQ_FLAG_EXCLUSIVE;
27        spin_lock_irqsave(&q->lock, flags);
28        __add_wait_queue(q, wait);
29        spin_unlock_irqrestore(&q->lock, flags);
30}

我们可以看到flags的结果必然是0，也就是说这个函数是将非互斥进程添加到等待队列当中。而且在调用具体的添加函数时候，使用关中断并保护现场的自旋锁方式使得添加操作每次只被一个进程访问。

具体的添加过程是将当前进程所对应的等待队列结点wait添加到等待队列头结点q之后。具体来说，就是将new->task_list结点添加到以head->task_list为头指针的双链表当中。另外，通过add_wait_queue_exclusive函数可以将一个互斥进程添加到等待队列当中。从添加过程可以发现，add_wait_queue函数会将非互斥进程添加到等待队列的前部。

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

另外， add_wait_queue_exclusive添加函数则会将互斥进程添加到等待队列的末尾。

  33void add_wait_queue_exclusive(wait_queue_head_t *q, wait_queue_t *wait)
  34{
  35        unsigned long flags;
  36
  37        wait->flags |= WQ_FLAG_EXCLUSIVE;
  38        spin_lock_irqsave(&q->lock, flags);
  39        __add_wait_queue_tail(q, wait);
  40        spin_unlock_irqrestore(&q->lock, flags);
  41}

remove_wait_queue函数用于将等待队列项wait从以q为等待队列头的等待队列中移除，源码如下。

  44void remove_wait_queue(wait_queue_head_t *q, wait_queue_t *wait)
  45{
  46        unsigned long flags;
  47
  48        spin_lock_irqsave(&q->lock, flags);
  49        __remove_wait_queue(q, wait);
  50        spin_unlock_irqrestore(&q->lock, flags);
  51}
 150static inline void __remove_wait_queue(wait_queue_head_t *head,
 151                                                        wait_queue_t *old)
 152{
 153        list_del(&old->task_list);
 154}

有了上述的基础，那么移除函数就简单了许多。

4.在等待队列上睡眠

如何实现进程的阻塞？大致过程就是将当前进程的状态设置成睡眠状态，然后将这个进程加入到等待队列即可。在linux内核中有一组函数接口来实现这个功能。

4313void __sched interruptible_sleep_on(wait_queue_head_t *q)
4314{
4315        sleep_on_common(q, TASK_INTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
4316}
4317EXPORT_SYMBOL(interruptible_sleep_on);
4318
4319long __sched
4320interruptible_sleep_on_timeout(wait_queue_head_t *q, long timeout)
4321{
4322        return sleep_on_common(q, TASK_INTERRUPTIBLE, timeout);
4323}
4324EXPORT_SYMBOL(interruptible_sleep_on_timeout);
4325
4326void __sched sleep_on(wait_queue_head_t *q)
4327{
4328        sleep_on_common(q, TASK_UNINTERRUPTIBLE, MAX_SCHEDULE_TIMEOUT);
4329}
4330EXPORT_SYMBOL(sleep_on);
4331
4332long __sched sleep_on_timeout(wait_queue_head_t *q, long timeout)
4333{
4334        return sleep_on_common(q, TASK_UNINTERRUPTIBLE, timeout);
4335}
4336EXPORT_SYMBOL(sleep_on_timeout);

通过上述源码，你可以发现这些函数在内部都调用了sleep_on_common函数，通过传递不同的值来实现不同的功能。而这个通用函数的三个参数分别关注的是：进程要加入到那个等待队列？进程是那种睡眠状态（TASK_UNINTERRUPTIBLE还是TASK_INTERRUPTIBLE）？进程睡眠的时间？

4292static long __sched
4293sleep_on_common(wait_queue_head_t *q, int state, long timeout)
4294{
4295        unsigned long flags;
4296        wait_queue_t wait;
4297
4298        init_waitqueue_entry(&wait, current);
4299
4300        __set_current_state(state);
4301
4302        spin_lock_irqsave(&q->lock, flags);
4303        __add_wait_queue(q, &wait);
4304        spin_unlock(&q->lock);
4305        timeout = schedule_timeout(timeout);
4306        spin_lock_irq(&q->lock);
4307        __remove_wait_queue(q, &wait);
4308        spin_unlock_irqrestore(&q->lock, flags);
4309
4310        return timeout;
4311}

在此函数中，首先定义了一个等待队列项结点，通过 init_waitqueue_entry函数对其进行初始化。可以从下述初始化源码中看到，此时该等待队列项指向当前当前进程。而唤醒函数指针func则指向内核自定义的一个默认唤醒函数default_wake_function。

  98static inline void init_waitqueue_entry(wait_queue_t *q, struct task_struct *p)
  99{
 100        q->flags = 0;
 101        q->private = p;
 102        q->func = default_wake_function;
 103}

初始化完毕后，通过__set_current_state函数将当前进程的状态设置成state。接着，在自旋锁的保护下，将当前进程对应的等待队列结点插入到等待队列链表当中。更重要的是，在schedule_timeout函数中不仅要设置进程的睡眠时间（以jiffies为单位的），还要使用schedule函数进行重新调度。一旦使用了schedule函数后，也就意味这当前这个进程真正的睡眠了，那么接下来的代码会在它唤醒后执行。当该进程被唤醒后（资源可用时），会从等待队列中将自己对应的那个等待队列结点wait移除。

上述过程都是在自旋锁保护下进行的，并且在整个执行过程中不可被其他中断所打断。现在再回过头去看一开始的那四个睡眠函数接口，你就明白了它们各自的不同之处了。

5.唤醒函数

唤醒函数会唤醒以x为头结点的等待队列中的等待队列项所对应的进程。与睡眠函数类似，内核中也有一组函数可以对阻塞的进程进行唤醒。

 170#define wake_up(x)                      __wake_up(x, TASK_NORMAL, 1, NULL)
 171#define wake_up_nr(x, nr)               __wake_up(x, TASK_NORMAL, nr, NULL)
 172#define wake_up_all(x)                  __wake_up(x, TASK_NORMAL, 0, NULL)

 175#define wake_up_interruptible(x)        __wake_up(x, TASK_INTERRUPTIBLE, 1, NULL)
 176#define wake_up_interruptible_nr(x, nr) __wake_up(x, TASK_INTERRUPTIBLE, nr, NULL)
 177#define wake_up_interruptible_all(x)    __wake_up(x, TASK_INTERRUPTIBLE, 0, NULL)

通过上述代码，我们可以发现这些唤醒函数均调用了__wake_up函数。__wake_up函数的四个参数分别指：头结点指针、唤醒进程的类型、唤醒进程的数量和一个附加的void型指针变量。

3999void __wake_up(wait_queue_head_t *q, unsigned int mode,
4000                        int nr_exclusive, void *key)
4001{
4002        unsigned long flags;
4003
4004        spin_lock_irqsave(&q->lock, flags);
4005        __wake_up_common(q, mode, nr_exclusive, 0, key);
4006        spin_unlock_irqrestore(&q->lock, flags);
4007}

在__wake_up函数又通过传递不同的参数调用__wake_up_common函数来实现不同的唤醒功能。

3975static void __wake_up_common(wait_queue_head_t *q, unsigned int mode,
3976                        int nr_exclusive, int wake_flags, void *key)
3977{
3978        wait_queue_t *curr, *next;
3979
3980        list_for_each_entry_safe(curr, next, &q->task_list, task_list) {
3981                unsigned flags = curr->flags;
3982
3983                if (curr->func(curr, mode, wake_flags, key) &&
3984                                (flags & WQ_FLAG_EXCLUSIVE) && !--nr_exclusive)
3985                        break;
3986        }
3987}

list_for_each_entry_safe函数将遍历整个等待队列中的链表，通过每次的逻辑判断来唤醒相应的进程。这个if语句初看起来有点麻烦，不过我们一点一点的将它拆解。

curr->func(curr, mode, sync, key)：即执行默认的唤醒函数，将指定的进程curr以mode方式唤醒。成功唤醒返回1；否则，返回0；
(flags & WQ_FLAG_EXCLUSIVE)：判断当前进程是否以互斥形式唤醒。是互斥形式则返回1；否则返回0；
!–nr_exclusive：nr_exclusive为需要唤醒的互斥进程的数量。

这三个部分是通过逻辑与连接起来的。根据逻辑与的运算规则，只有当第一部分为真时才会判断第二部分的值，依次再判断第三部分的值。

通过上述的等待队列的添加过程我们知道，等待队列中前面均是非互斥进程，后面才是互斥进程。因此，唤醒函数总先唤醒全部的非互斥进程。因为当__wake_up_commom函数每一次去判断if语时，总会“不自觉”去执行默认的唤醒函数（除非唤醒失败，那么会退出遍历宏）；当全部的非互斥进程被唤醒后，第二个判断条件也就成立了。因此__wake_up_commom函数会依次唤醒nr_exclusive个互斥进程；当–nr_exclusive为0时（!–nr_exclusive也就为真），整个遍历过程也恰好结束，而此时if语句的三个判断条件才刚好满足（这段代码太强大了!!!）。

6.有条件的睡眠

与睡眠函数不同，条件睡眠是指当某些条件发生时，这个进程才会加入到等待队列当中。关于条件睡眠有下列的宏：

wait_event(wq, condition)
wait_event_timeout(wq, condition, timeout)
wait_event_interruptible(wq, condition)
wait_event_interruptible_timeout(wq, condition, timeout)

关于条件睡眠，虽然函数实现与睡眠函数不同，但是基本思想是相似的，各位可以查找相应的源码进行分析。Try！

内核中时间的相关概念

节拍率：系统定时器以某种频率触发时钟中断，这个频率就称为节拍率（tick rate）。节拍率是通过静态预处理定义的，被定义为HZ。对于x86体系结构来说，它的HZ为100。

节拍：两次时钟中断的间隔就称为节拍（tick）。可以看到，节拍等于节拍率分之一。

jiffies：全局变量jiffies用来记录系统自启动以来产生的节拍总数。通过jiffies/HZ就可获取系统自启动以来的秒数。

内核定时器

内核定时器，也称为动态定时器，是管理内核时间的基础，它是一种用来推迟执行程序的工具。前面中断的文章中我们说到内核将在稍候的时间执行下部分工作，具体是何时来执行就需要内核定时器。我们在使用关于定时器的相关函数时，先来看看内核是如何描述定时器的：

  10struct tvec_base;
  11
  12struct timer_list {
  13        /*
  14         * All fields that change during normal runtime grouped to the
  15         * same cacheline
  16         */
  17        struct list_head entry;//定时器链表入口
  18        unsigned long expires;//以jiffies为单位的定时值
  19        struct tvec_base *base;//
  20
  21        void (*function)(unsigned long);//定时器处理函数
  22        unsigned long data;//传给定时器处理函数的参数，无符号长整型
  23
  24        int slack;
  25
  26#ifdef CONFIG_TIMER_STATS
  27        void *start_site;
  28        char start_comm[16];
  29        int start_pid;
  30#endif
  31#ifdef CONFIG_LOCKDEP
  32        struct lockdep_map lockdep_map;
  33#endif
  34};

内核定时器使用起来也是相当简单的，基本的使用思路是：定义一个timer_list；初始化定时器，即对timer_list结构中的相关字段进行赋值；定义你自己的定时器处理函数；激活定时器；修改定时器，如果有必要的话；删除定时器。上述过程通过以下的API就可简单的完成。

秒字符驱动与内核定时器API

下面要分析的这个程序实现了一个秒字符设备驱动，程序整体的框架与之前我们分析的字符设备驱动相同。内核模块加载函数和卸载函数的功能和之前的字符设备驱动完全相同，因此接下来主要分析这个设备的操作函数。我们使用下面的结构来描述我们当前所讨论的秒字符设备。

struct second_dev
{
	struct cdev cdev;
	atomic_t counter;
	struct timer_list s_timer;
};

cdev即为内核中描述字符设备的结构体；counter用来记录秒数，它在测试程序中用来显示当前程序运行的时间。同时也是此设备驱动进行读写的数据；s_timer是为此设备所定义的定时器。每次定时一个HZ，也就是1秒，当定时到后，通过定时器处理函数对其进行修改，每次增加一个HZ。

接下来，我们一边分析驱动程序中的设备文件操作函数，一边学习内核定时器的API。

1.打开函数

秒字符设备在文件打开函数中实现对定时器的初始化以及赋值。

static int second_open(struct inode*inode,struct file*filp)
{
	//initializing the timer
	init_timer(&second_devp->s_timer);
	second_devp->s_timer.function=&second_timer_handler;
	second_devp->s_timer.expires=jiffies+HZ;
	add_timer(&second_devp->s_timer);//add a timer
	atomic_set(&second_devp->counter,0);//clear the counter
	return 0;
}

可以看到，内核定时器函数通过：init_timer(&t);来进行定时器的初始化，其中t为timer_list类型的指针。expires是用来设置定时器的定时值，单位是节拍数。我们可以看到初始定时值为一秒，即在当前时钟节拍数上加上一个节拍率。function则是上面提到的定时器处理函数。

另外，在open函数中，还通过add_timer(&t);来进行定时器的激活，也就是把当前这个定时器加入到内核定时器链表当中。由于我们在该设备对应的街头体中将counter设置为atomic_t（关于atomic.h头文件，本博客稍候会专门来分析，请持续关注～ ），因此我们使用atomic_set函数对其进行初始化，其值设置为0。

2.读函数

static ssize_t second_read(struct file *filp,char __user *buf,size_t count,loff_t *ppos)
{
	int counter;

	counter=atomic_read(&second_devp->counter);
	if(put_user(counter,(int*)buf))
	{
		return -EFAULT;
	}
	else
	{
		return sizeof(unsigned int);
	}

}

这个读函数的意思是从内核中通过atomic_read函数读取counter，再通过put_user函数将其值返回至用户空间。

3.定时器处理函数

static void second_timer_handler(unsigned long arg)
{
	mod_timer(&second_devp->s_timer,jiffies+HZ);
	atomic_inc(&second_devp->counter);
	printk("Current jiffies is %ld\n",jiffies);
}

执行此处理函数时，说明先前定时器的时间已经到期。我们通过mod_timer(&t,jiffies+newdelay);来改变定时器的超时时间。这里我们每次增加一秒的时间。接着通过atomic_inc函数对counter加一，并且在内核中显示当前的节拍数。

4.文件释放函数

static int second_release(struct inode*inode,struct file*filp)
{
	del_timer(&second_devp->s_timer);
	return 0;
}

在文件释放函数中，通过del_timer(&t);就可以删除这个定时器。

测试

1.make编译并将此模块插入内核：sudo insmod secondcdev.ko
2.查看/proc/devices文件中是否有主设备号为250的设备
3.创建该设备文件节点，使用命令：sudo mknod /dev/secondcdev  c  250  0
4.修改该设备文件权限：sudo chmod 777 /dev/secondcdev
5.编译测试文件：gcc -o test test.c
6.运行测试程序：./test；

关于测试程序代码如下：

#include < stdio.h >
#include < sys/stat.h >
#include < sys/types.h >
#include < fcntl.h >
#include < stdlib.h >
int main()
{
	int fd;
	int counter=0;
	int old_counter=0;

	//open the /dev/secondcdev device file
	if((fd=open("/dev/secondcdev",O_RDONLY))<0)
	{
		printf("Device open failed\n");
		return -1;
	}

	while(1)
	{
		read(fd,&counter,sizeof(unsigned int));//read the current second number
		if(counter!=old_counter)
		{
			printf("seconds after open /dev/second:%d\n",counter);
			old_counter=counter;
		}
	}

	return 0;

在测试程序中，首先创建一个设备文件；然后循环读取counter的值，如果前后两次读取的counter值不一样，那么就输出；由于我们在定时器处理函数中是每隔一秒修改一次定时器，因此测试程序将每个一秒输出一次counter值。可以看到，我们所编写的秒字符设备驱动使得数据（即counter）在内核空间和用户空间之间进行交互。