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;
}
