在2.4版本中，引入了一种特殊的链表-通用双向链表，它是内核中实现其它链表的基础，也是面向对象的思想在C语言中的应用。在等待队列的实现中多次涉及与此链表相关的内容。
1．通用双向链表
在include/linux/list.h中定义了这种链表：
struct list_head {
struct list_head *next, *prev;
};
这是双向链表的一个基本框架，在其它使用链表的地方就可以使用它来定义任意一个双向链表，例如：
struct foo_list {
int data;
struct list_head list;
};
对于list_head类型的链表，Linux定义了五个宏：
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
#define INIT_LIST_HEAD(ptr) do { \
(ptr)->next = (ptr); (ptr)->prev
= (ptr); \
} while (0)
#define list_entry(ptr, type, member) \
((type *)((char *)(ptr)-(unsigned
long)(&((type *)0)->member)))
#define list_for_each(pos, head) \
for (pos = (head)->next; pos != (head); pos =
pos->next)
前三个宏都是初始化一个空的链表，但用法不同，LIST_HEAD_INIT()在声明时使用，用来初始化结构元素，第二个宏用在静态变量初始化的声明中，而第三个宏用在函数内部。
其中，最难理解的宏为list_entry（），在内核代码的很多处都用到这个宏，例如，在调度程序中，从运行队列中选择一个最值得运行的进程，部分代码如下：
static LIST_HEAD(runqueue_head);
struct list_head *tmp;
struct task_struct *p;
list_for_each(tmp,
&runqueue_head) {
p = list_entry(tmp, struct task_struct,
run_list);
if (can_schedule(p)) {
int weight = goodness(p, this_cpu, prev->active_mm);
if (weight > c)
c
= weight, next = p;
}
}
从这段代码可以分析出list_entry(ptr, type, member)宏及参数的含义： ptr是指向list_head类型链表的指针，type为一个结构，而member为结构type中的一个域，类型为list_head，这个宏返回指向type结构的指针。在内核代码中大量引用了这个宏，因此，搞清楚这个宏的含义和用法非常重要。
另外，对list_head类型的链表进行删除和插入（头或尾）的宏为list_del()/list_add()/list_add_tail()，在内核的其它函数中可以调用这些宏。例如，从运行队列中删除、增加及移动一个任务的代码如下：
static inline void del_from_runqueue(struct
task_struct * p)
{
nr_running--;
list_del(&p->run_list);
p->run_list.next = NULL;
}
static inline void add_to_runqueue(struct
task_struct * p)
{
list_add(&p->run_list, &runqueue_head);
nr_running++;
}
static inline void move_last_runqueue(struct
task_struct * p)
{
list_del(&p->run_list);
list_add_tail(&p->run_list,
&runqueue_head);
}
static inline void move_first_runqueue(struct
task_struct * p)
{
list_del(&p->run_list);
list_add(&p->run_list,
&runqueue_head);
}
2.等待队列
运行队列链表把处于TASK_RUNNING状态的所有进程组织在一起。当要把其他状态的进程分组时，不同的状态要求不同的处理，Linux选择了下列方式之一：
· TASK_STOPPED或 TASK_ZOMBIE状态的进程不链接在专门的链表中，也没必要把它们分组，因为父进程可以通过进程的PID，或进程间的亲属关系检索到子进程。
· 把TASK_INTERRUPTIBLE 或 TASK_UNINTERRUPTIBLE状态的进程再分成很多类，其每一类对应一个特定的事件。在这种情况下，进程状态提供的信息满足不了快速检索进程，因此，有必要引入另外的进程链表。这些链表叫等待队列。
等待队列在内核中有很多用途，尤其对中断处理、进程同步及定时用处更大。因为这些内容在以后的章节中讨论，我们只在这里说明，进程必须经常等待某些事件的发生，例如，等待一个磁盘操作的终止，等待释放系统资源，或等待时间走过固定的间隔。等待队列实现在事件上的条件等待，也就是说，希望等待特定事件的进程把自己放进合适的等待队列，并放弃控制权。因此，等待队列表示一组睡眠的进程，当某一条件变为真时，由内核唤醒它们。等待队列由循环链表实现。在2.4的版本中，关于等待队列的定义如下（为了描述方便，有所简化）：
struct __wait_queue {
unsigned int flags;
struct task_struct * task;
struct list_head task_list;
};
typedef struct __wait_queue wait_queue_t;
另外，关于等待队列另一个重要的数据结构—等待队列首部的描述如下：
struct __wait_queue_head {
wq_lock_t lock;
struct list_head task_list;
};
typedef struct __wait_queue_head wait_queue_head_t;
在这两个数据结构的定义中，都涉及到类型为list_head的链表，这与2.2版定义是不同的，在2.2版中的定义为：
struct wait_queue {
struct task_struct * task;
struct wait_queue * next;
};
typedef struct wait_queue wait_queue_t;
typedef struct wait_queue *wait_queue_head_t;
这里要特别强调的是，2.4版中对等待队列的操作函数和宏比2.2版丰富了，而在你编写设备驱动程序时会用到这些函数和宏，因此，要注意2.2到2.4函数的移植问题。下面给出2.4版中的一些主要函数及其功能：
init_waitqueue_head（）—对等待队列首部进行初始化
init_waitqueue_entry（）－对要加入等待队列的元素进行初始化
waitqueue_active（）—判断等待队列中已经没有等待的进程
add_wait_queue（）—给等待队列中增加一个元素
remove_wait_queue（）—从等待队列中删除一个元素
注意，在以上函数的实现中，都调用了对list_head 类型链表的操作函数（list_del()/list_add()/list_add_tail()），因此说，list_head 类型相当于C++中的基类型，这也是对2.2 版的极大改进。
希望等待一个特定事件的进程能调用下列函数中的任一个：
· sleep_on( )函数对当前的进程起作用，我们把当前进程叫做P：
sleep_on(wait_queue_head_t *q)
{
SLEEP_ON_VAR ／＊宏定义，用来初始化要插入到等待队列中的元素＊／
current->state = TASK_UNINTERRUPTIBLE;
SLEEP_ON_HEAD ／＊宏定义，把P插入到等待队列 ＊／
schedule();
SLEEP_ON_TAIL ／＊宏定义， 把P从等待队列中删除 ＊／
}
这个函数把P的状态设置为TASK_UNINTERRUPTIBLE，并把P插入等待队列。然后，它调用调度程序恢复另一个程序的执行。当P被唤醒时，调度程序恢复sleep_on( )函数的执行，把P从等待队列中删除。
· interruptible_sleep_on( )与sleep_on( )函数是一样的，但稍有不同，前者把进程P的状态设置为TASK_INTERRUPTIBLE 而不是TASK_UNINTERRUPTIBLE ，因此，通过接受一个信号可以唤醒P。
· sleep_on_timeout( ) 和interruptible_sleep_on_timeout( )与前面情况类似，但它们允许调用者定义一个时间间隔，过了这个间隔以后，内核唤醒进程。为了做到这点，它们调用schedule_timeout( )函数而不是schedule( )函数。
利用wake_up 或者 wake_up_interruptible宏，让插入等待队列中的进程进入TASK_RUNNING状态，这两个宏最终都调用了try_to_wake_up( )函数：
static inline int try_to_wake_up(struct task_struct * p, int synchronous)
{
unsigned long flags;
int success = 0;
spin_lock_irqsave(&runqueue_lock, flags); /＊加锁＊／
p->state = TASK_RUNNING;
if (task_on_runqueue(p)) ／＊判断p是否已经在运行队列＊／
goto out;
add_to_runqueue(p); ／＊不在，则把p插入到运行队列＊／
if (!synchronous || !(p->cpus_allowed & (1 << smp_processor_id()))) ／
reschedule_idle(p);
success = 1;
out:
spin_unlock_irqrestore(&runqueue_lock, flags); ／＊开锁＊／
return success;
}
在这个函数中，p为要唤醒的进程。如果p不在运行队列中，则把它放入运行队列。如果重新调度正在进行的过程中，则调用reschedule_idle（）函数，这个函数决定进程p是否应该抢占某一CPU上的当前进程（参见下一章）。
实际上，在内核的其它部分，最常用的还是wake_up 或者 wake_up_interruptible宏，也就是说，如果你要在内核级进行编程，只需调用其中的一个宏。例如一个简单的实时时钟（RTC）中断程序如下：
static DECLARE_WAIT_QUEUE_HEAD(rtc_wait); ／＊初始化等待队列首部＊／
void rtc_interrupt(int irq, void *dev_id, struct pt_regs *regs)
{
spin_lock(&rtc_lock);
rtc_irq_data = CMOS_READ(RTC_INTR_FLAGS);
spin_unlock(&rtc_lock);
wake_up_interruptible(&rtc_wait);
}
这个中断处理程序通过从实时时钟的I/O端口（CMOS_READ宏产生一对outb/inb）读取数据，然后唤醒在rtc_wait等待队列上睡眠的任务。