4.5.4等待队列

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.22.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等待队列上睡眠的任务。