Raw os 内核链表篇

jorya_txj

Raw os 内核链表篇 [复制链接]

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种，一种是普通的双向链表，还有一种是按照优先级来排序的。