linux kernel调度算法之任务优先级队列

struct prio_array {

    unsigned intnr_active//优先级队列数据中task个数

    unsignedlong bitmap[BITMAP_SIZE]

    structlist_head queue[MAX_PRIO]

}

#define BITMAP_SIZE ((((MAX_PRIO+1+7)/8)+sizeof(long)-1)/sizeof(long))

//内核中long型占4个字节，一个字节8位，BITMAP_SIZE的值为5

场景：将任务加入到对应优先级队列的尾部

static void enqueue_task(struct task_struct *p, prio_array_t *array)

{

    sched_info_queued(p)

    list_add_tail(&p->run_list, array->queue + p->prio)

    __set_bit(p->prio, array->bitmap)

    array->nr_active++

    p->array = array

}

场景：将任务从优先级队列中移除

static void dequeue_task(struct task_struct *p, prio_array_t *array)

{

    array->nr_active--

    list_del(&p->run_list)

    if (list_empty(array->queue + p->prio))

    __clear_bit(p->prio, array->bitmap)

}

场景：将任务移动到对应优先级队列的尾部

/*

* Put task to the end of the run list without the overhead of dequeue

* followed by enqueue.

*/

static void requeue_task(struct task_struct *p, prio_array_t *array)

{

    list_move_tail(&p->run_list, array->queue + p->prio)

}

场景：将任务加入到对应优先级队列的首部

static inline void enqueue_task_head(struct task_struct *p, prio_array_t *array)

{

    list_add(&p->run_list, array->queue + p->prio)

    __set_bit(p->prio, array->bitmap)

    array->nr_active++

    p->array = array

}

work queue是一种bottom half，中断处理的后半程，强调的是动态的概念，即work是重点，而queue是其次。

wait queue是一种「任务队列」，可以把一些进程放在上面睡眠等待某个事件，强调静态多一些，重点在queue上，即它就是一个queue，这个queue如何调度，什么时候调度并不重要

等待队列在内核中有很多用途，尤其适合用于中断处理，进程同步及定时。这里只说，进程经常必须等待某些事件的发生。例如，等待一个磁盘 *** 作的终止，等待释放系统资源，或者等待时间经过固定的间隔。

等待队列实现了在事件上的条件等待，希望等待特定事件的进程把放进合适的等待队列，并放弃控制权。因此。等待队列表示一组睡眠的进程，当某一条件为真时，由内核唤醒进程。

等待队列由循环链表实现，其元素包括指向进程描述符的指针。每个等待队列都有一个等待队列头，等待队列头是一个类型为wait_queue_head_t的数据结构。

等待队列链表的每个元素代表一个睡眠进程，该进程等待某一事件的发生，描述符地址存放在task字段中。然而，要唤醒等待队列中所有的进程有时并不方便。例如，如果两个或多个进程在等待互斥访问某一个要释放的资源，仅唤醒等待队列中一个才有意义。这个进程占有资源，而其他进程继续睡眠可以用DECLARE_WAIT_QUEUE_HEAD(name)宏定义一个新的等待队列，该宏静态地声明和初始化名为name的等待队列头变量。 init_waitqueue_head()函数用于初始化已动态分配的wait queue head变量等待队列可以通过DECLARE_WAITQUEUE()静态创建，也可以用init_waitqueue_head()动态创建。进程放入等待队列并设置成不可执行状态。

工作队列，workqueue，它允许内核代码来请求在将来某个时间调用一个函数。用来处理不是很紧急事件的回调方式处理方法.工作队列的作用就是把工作推后,交由一个内核线程去执行，更直接的说就是写了一个函数,而现在不想马上执行它，需要在将来某个时刻去执行，那就得用工作队列准没错。

如果需要用一个可以重新调度的实体来执行下半部处理，也应该使用工作队列。是唯一能在进程上下文运行的下半部实现的机制。这意味着在需要获得大量的内存时、在需要获取信号量时，在需要执行阻塞式的I/O *** 作时，都会非常有用。

工作队列中是即将要调度到的任务队列，等待队列是暂时被挂起的任务队列，或者有些任务无事可做休眠状态的任务，它们会在某些条件触发时恢复换入工作队列并进入执行状态，同样在工作队列中的任务在某个时刻也可以被换入到等待队列中

---