高效实时操作系原理以及实践-就绪队列

lulu爱

就绪队列

raw os 总是运行就绪队列中最高优先级的任务。就绪队列实质上是一个hash table, 也就是说有一个链表数组，每一个数组元素代表一个优先级的就绪队列，raw os最多支持256优先级的就绪队列，也就是说数组下标0到255.

typedef        struct RAW_RUN_QUEUE {

        RAW_U8      highest_priority;                              (1)
       
        LIST          task_ready_list[CONFIG_RAW_PRIO_MAX];         (2)         
       
        RAW_U32     task_bit_map[NUM_WORDS];                   (3)
       
} RAW_RUN_QUEUE;

RAW_RUN_QUEUE 这个数据结构代表了整个系统的就绪队列，(2)处代码说明了有多少个优先级就有多少个就绪队列。(3)处代码是一个位图，一个bit代表一个优先级。 (1)处代码中的highest_priority维护了系统中最高的优先级是多少。

(2)处代码中的LIST结构体定义如下:

typedef struct LIST {
        struct LIST        *next;
        struct LIST        *previous;
} LIST;

可以看到LIST是一个双向链表，raw os的就绪队列采用了双向链表，而不是采用了传统的单向链表是为了加快插入到尾部的速度，虽然比起单链表浪费了一个指针的大小，实则是明智的做法。

下图代表着raw os系统的其中一个优先级的就绪队列:



可以看到上图中，就绪队列Y是一个双链表(LIST)，任务1，任务2，任务3，都是包含一个双链表(LIST),就绪的任务与任务之间也是用双链表连接在一起。需要注意的是任务2和优先级Y的链表也是首尾相连的。


如果一个优先级对应的就绪队列中有多个任务的话，raw os调度时总是会选择链表打头指向的的那个任务做为最高优先级任务去运行，比如上图中最高优先级的任务就是任务1。

raw os 找到最高优先级的方法，实质上去查找task_bit_map第一个bit为1的位置。

raw os 查找task_bit_map第一个bit为1的位置的API是bit_search_first_one。bit_search_first_one这个API有两套版本一个是给32位的cpu用的，另外一个是给8位和16位单片机使用的。

raw os 涉及到内部就绪队列的api有以下几个:

1 add_ready_list_head

假设当前的就绪队列为：


加入任务2到队列头部后就变为:


可以看到任务2变到前面去了。



2 add_ready_list_end

假设当前的就绪队列为：


加入任务2后就变为如下：


3 remove_ready_list

假设当前的就绪队列为:


移除任务1后，就绪队列变为


4 move_to_ready_list_end

假设当前的就绪队列为：


假设任务1的时间片消耗完以后，会移到就绪队列最后去,此时就绪队列为:


5 get_ready_task

假设当前系统最高就绪态的任务优先级为Y, 系统的就绪图如下:


这个时候函数将会返回任务2为系统最高优先级的任务。


这些函数都是raw os 内核内部的函数，用户是不会接触到这些函数的，以下描述这些函数的具体功能以及参数含义。

1 void add_ready_list_head(RAW_RUN_QUEUE *rq, RAW_TASK_OBJ *task_ptr)

函数功能：
往就绪队列rq里面加入一个任务。也就是说该任务已经处于就绪状态。需要注意的是加入的任务加到就绪队列头部去。

此函数的参数有4个，含义如下:
rq 为指针指向raw os 系统维护的一个优先级队列实体raw_ready_queue。
task_ptr是要准备被加入的任务。

函数的返回值：
无

2 void add_ready_list_end(RAW_RUN_QUEUE *rq, RAW_TASK_OBJ *task_ptr)

函数功能：
往就绪队列rq里面加入一个任务。也就是说该任务已经处于就绪状态。需要注意的是加入的任务加到就绪队列尾部去。

此函数的参数有4个，含义如下:
rq 为指针指向raw os 系统维护的一个优先级队列实体raw_ready_queue。
task_ptr是要准备被加入的任务。

函数的返回值：
无

3 void remove_ready_list(RAW_RUN_QUEUE *rq, RAW_TASK_OBJ *task_ptr)

函数功能：
往就绪队列rq里面移除一个任务。也就是说该任务已经处于非就绪状态。非就绪状态有很多任务状态，具体请参阅任务状态一章。需要注意的是此函数内部可能会更新系统的rq->highest_priority， rq->highest_priority永远维护着整个系统最高的优先级。

此函数的参数有2个，含义如下:
rq 为指针指向raw os 系统维护的一个优先级队列实体raw_ready_queue。
task_ptr是要准备被从就绪态移除出去的任务。

函数的返回值：
无

4 void move_to_ready_list_end(RAW_RUN_QUEUE *rq, RAW_TASK_OBJ *task_ptr)

函数功能：
把任务task_ptr放到就绪队列最后面去。

此函数的参数有2个，含义如下:
rq 为指针指向raw os 系统维护的一个优先级队列实体raw_ready_queue。
task_ptr是要准备放到就绪队列最后面去的任务。

函数的返回值：
无

5 void get_ready_task(RAW_RUN_QUEUE *rq)

函数功能:
更新就绪队列里面优先级最高的任务, 此函数的算法效率相当重要，对实时性有举足轻重的影响，此函数必须要运行时间是恒定的，因为此函数是在关了系统中断情况下使用的需要越快越好，raw os的实现只有3句C语言，具体的请参照相关代码。

此函数的参数有1个，含义如下:
rq为指针指向raw os系统维护的一个优先级队列实体raw_ready_queue。


raw os 官网地址为:www.raw-os.org