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

}

int main()

{

Link head//链表(不带头节点)

int n

printf("输入链表的长度n: ")

scanf("%d",&n)

printf("连续输入%d个数据(以空格隔开): ",n)

head=CreateLink(n)

printf("\n原本链表的节点是: ")

DispLink(head)

LinkSort(head)

printf("\n从大到小排序之后: ")

DispLink(head)

printf("\n")

return 0

}

链表的具体存储表示为：

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

以上内容参考：百度百科-单链表

---