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

1. 数据结构

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

2. 图解

图一：任务优先级队列

3. 队列操作函数解析

场景：将任务加入到对应优先级队列的尾部
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;

}