raw-os内核设计中的一些算法和思想

lulu爱

有一些读者可能会关心在raw-os内核开发中采用了哪些高深的算法。其实开发一个rtos的难点不在于算法，而在于逻辑的完整性，算法和思想往往是很简单的，充分验证了大道至简的思想。

下面将例举一下开发中所用到的算法有:

1 循环双链表

循环双链表的算法在raw_list.h中，这个算法普遍的用在内核设计中，起初的设计采用了单链表的设计为了节省内存的开销，因为单链表没一个节点只有一个指针，省去了4个字节的大小，但是插入到尾部的算法是时间不确定的，所以最终衡量放弃了。

2 哈希表

哈希表的算法的优势是查找以及插入的速度很快，而且时间是恒定的o(1)。利用这一个优势，raw-os中的软件定时器(raw_timer)以及raw_tick的开发都采用到了。

raw-os内核开发中用到了一些比较重要的思想有:

1 基于状态机的思想，大家都知道状态机的思想可以用C语言的语法switch 和case来表达出来，raw-os中的任务状态，raw-os中大量采用到了这样的机制，比如以下函数raw_task_delete中的代码:

switch (task_ptr->task_state) {
                case RAW_RDY:
                        remove_ready_list(&raw_ready_queue, task_ptr);
                        break;

                case RAW_SUSPENDED:
                        break;

                case RAW_DLY:                           
                case RAW_DLY_SUSPENDED:
                        tick_list_remove(task_ptr);
                        break;

                case RAW_PEND:
                case RAW_PEND_SUSPENDED:
                case RAW_PEND_TIMEOUT:
                case RAW_PEND_TIMEOUT_SUSPENDED:
                        tick_list_remove(task_ptr);
                        list_delete(&task_ptr->task_list);
                       
                        #if (CONFIG_RAW_MUTEX > 0)
                        mutex_state_change(task_ptr);
                        #endif
                       
                        break;

                default:
                       
                        RAW_CRITICAL_EXIT();
                       
                        return  RAW_STATE_UNKNOWN;
        }  


可以看到上述的代码中case 的后面都是任务的状态，比如RAW_RDY和RAW_DLY这种。

2 面向对象的继承和多态的设计方法。举例如下:

RAW_COMMON_BLOCK_OBJECT是父类结构体，定义如下:

typedef        struct RAW_COMMON_BLOCK_OBJECT {       
       
        LIST                      block_list;
        RAW_U8                    *name;
        RAW_U8                    block_way;
        RAW_U8                    object_type;
       
} RAW_COMMON_BLOCK_OBJECT;

RAW_COMMON_BLOCK_OBJECT这个结构体是很多内核对象所需要使用到的，比如semaphore, queue, event 这种内核对象都会使用到这个结构体。下面是semaphore的结构体：

typedef struct RAW_SEMAPHORE
{
        RAW_COMMON_BLOCK_OBJECT       common_block_obj;
        RAW_U32                       count;
……………………………………………
       
} RAW_SEMAPHORE;

可以看到上面的RAW_SEMAPHORE这个结构体中common_block_obj是放在第一个位置，这种叫做继承，意思是RAW_SEMAPHORE这个子类继承了父类common_block_obj，根据面向对象中多态的原理，子类可以被强制转换为父类，利用这个特性可以很方便的设计通用的函数，例如以下函数:

RAW_U16 raw_pend_object(RAW_COMMON_BLOCK_OBJECT  *block_common_obj, RAW_TASK_OBJ *task_ptr, RAW_TICK_TYPE timeout)

可以看到函数raw_pend_object的第一个参数类型为RAW_COMMON_BLOCK_OBJECT，也就是说这个是之前讲的父类的函数，在信号量的设计中有如下的设计:
raw_pend_object((RAW_COMMON_BLOCK_OBJECT  *)semaphore_ptr, raw_task_active, wait_option);

semaphore_ptr的类型为RAW_SEMAPHORE，RAW_SEMAPHORE的类型为RAW_COMMON_BLOCK_OBJECT的子类，所以设计的时候，可以把子类强制转换为父类这样的设计。类似的设计还有queue的设计等，比如:
raw_pend_object((RAW_COMMON_BLOCK_OBJECT  *)p_q, raw_task_active, wait_option);
p_q的类型为RAW_QUEUE， RAW_QUEUE也是RAW_COMMON_BLOCK_OBJECT的子类。

这样的设计有什么好吃吗？如果不这样做的话，就要多写很多这样的函数，结构上，代码体积上都会有浪费，通过C语言这种面向对象的写法，可以很有效的提高结构，以及节约必要的空间。

霸气侧漏

很高深的感觉

zllfdd

单链表插入到尾部的算法是时间不确定，不是很明白。楼主能不能细说一下

lulu爱

单链表插入到尾部需要遍历到最后才能插入，如果链表上东西多的话，遍历的时间是不固定的，双链表是o(1)的效率。