Raw os 的基础链表是双向循环链表,这样的好处是插到尾部速度非常快,有些传统的os 采用了单个指针头的双向链表,虽然这样省了4个字节指针,但是算法复杂了,插入到尾部时间不确定,意义不大。
Raw os 里有3处地方主要会用到链表,第一个地方是就绪链表,第二个地方是block 在mutex, semaphore,queue, event ,memory 上的任务,第三种是挂在tick_list 上的任务,和软件timer 头上的timer.
就绪链表的插入根据插到头或者尾部去决定, 除了就绪链表外第二种维护的是一个优先级链表,block 在mutex, semaphore,queue, event ,memory 上的任务按照优先级的大小去去排序,从小到大。比如:
Semphore1<->task1<->task2<->task5<->task7<->task9
event1<->task1<->task2<->task5<->task7<->task9
当唤醒的时候总是唤醒打头指向的第一个优先级最高的任务。
第三种是挂在tick_list 上的用来处理任务超时的,是按照tick_remain 的大小从低到大排序的。链表头是LIST tick_head[TICK_HEAD_ARRAY],根据算法去判定任务的tick_list连接在哪个头上。软件timer 的处理方法是类似的。
总结下来raw os 的链表有2种,一种是普通的双向链表,还有一种是按照优先级来排序的。