前言

在一般的应用程序开发中，我们很少会关注程序性能、实时性问题，一方面是因为CPU的硬件资源已经够用，另一方面就是一般的应用程序对于性能、实时性的要求并不会太高，几十毫秒的延时，可能对于多说应用程序的逻辑都是没有太大影响的。但是对于RTOS的代码，我们就需要重点关注代码是否高效、毕竟RTOS的R 是Real time的含义，即对实时性要求很高。

RTOS中对实时性要求高的场景分析

1. 更新所有task的剩余tick。

这种场景很容易理解，这是调度的基础，几乎所有的RTOS的【心跳】服务（比如滴答定时器中断）中，都会遍历所有处于等待的任务，计算这些任务需要等待的剩余tick，所以快速的遍历任务TCB，并且能够快速的获取各tcb的地址就显得尤为重要了，所以在RTOS中，并不会使用类似Linux中的通用list方法，而是定制改造的链表方法，避免使用container_of 计算。

/*
 * Get offset of a member variable.
 *
 * @param[in]   type     the type of the struct this is embedded in.
 * @param[in]   member   the name of the variable within the struct.
 */
#define offsetof(type, member)   ((size_t)&(((type *)0)->member))

/*
 * Get the struct for this entry.
 *
 * @param[in]   ptr     the list head to take the element from.
 * @param[in]   type    the type of the struct this is embedded in.
 * @param[in]   member  the name of the variable within the struct.
 */
#define container_of(ptr, type, member) \
    ((type *) ((char *) (ptr) - offsetof(type, member)))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

上述方法虽然在通用链表中非常好用，但是在RTOS中会牺牲一部分的性能，因为遍历链表，只能获取链表成员地址，还需要通过链表成员的地址计算出链表所在的结构体的地址。

所以在RTOS中，一般都是定制链表，链表成员的类型就是TCB的类型。这种用法在uCOS中很常见，除了TCB链表，其他event链表等都是采用这种定制方式。

2. 快速找到【最高优先级就绪任务】。

这个需求几乎是所有OS都要考虑的问题，有很多种调度调度算法，我们最常用的RTOS功能都是基于优先级的、可剥夺型的RTOS，那么对于RTOS来说，快速的从就绪任务队列中查找到【最高优先级就绪任务】对于OS的性能就尤为重要了，这个时候就需要考虑算法了，当然如果我们不关心性能，也可以采用笨方法，比如遍历所有的任务，然后再找出最高优先级，但是这样的查找算法复杂度是O(n)，那有没有更高效简单查找算法呢？答案是有，用空间换性能。
在uCOS-ii中，经典的查找算法会转换成【针对某个8bit的字节，快速找到其为1的位】。作者的方法是非常简单粗暴的，把1个字节出现所有bit为1的值，全部遍历写一遍，了不起最多也就255个字节，但是这带来的好处是，当我们只需要使用某个byte值，直接查表，就能获取该值的第一个为1的bit，这样查找复杂度就是O(1).

INT8U  const  OSUnMapTbl[256] = {
    0u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x00 to 0x0F                   */
    4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x10 to 0x1F                   */
    5u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x20 to 0x2F                   */
    4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x30 to 0x3F                   */
    6u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x40 to 0x4F                   */
    4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x50 to 0x5F                   */
    5u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x60 to 0x6F                   */
    4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x70 to 0x7F                   */
    7u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x80 to 0x8F                   */
    4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0x90 to 0x9F                   */
    5u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xA0 to 0xAF                   */
    4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xB0 to 0xBF                   */
    6u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xC0 to 0xCF                   */
    4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xD0 to 0xDF                   */
    5u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, /* 0xE0 to 0xEF                   */
    4u, 0u, 1u, 0u, 2u, 0u, 1u, 0u, 3u, 0u, 1u, 0u, 2u, 0u, 1u, 0u  /* 0xF0 to 0xFF                   */
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

3. 快速创建任务。

快速创建任务的核心是解决减少链表的遍历，如果使用通用链表方法，我们每插入1个新的链表节点，都需要遍历当前的链表所有成员，然后将节点添加到链表尾，所以任务越多，需要遍历的次数也多。那如何快速添加新的节点到链表尾呢？答案是定制链表，通过添加1个[链表尾]指针来实现，每次添加新节点，直接添加到【链表尾】处，然后再更新【链表尾】指针即可，这样做虽然链表不再通用，但是性能能够大幅度提升，而我们要的就是性能。

4. TCB 任务控制块数据结构的第一个成员是任务堆栈指针。

这样做的目的是为了快速查找到任务的堆栈，因为任务的上下文切换，就是堆栈的切换，所以必须要能快速的获取任务的堆栈，如果将任务堆栈放到TCB的首个成员，那么任务堆栈的地址就等于TCB的地址，这样对于OS内部调度实现会降低复杂度。

小结

1. 在一般的应用程序开发中，如果只是逻辑功能的代码实现，程序员是不需要考虑太多程序运行效率是不是最高，性能是不是最好，简单、易懂、容易实现的代码就是最好的，因为简单，所以就容易维护，就不容易出错。
2. 对于一些特殊的场景，比如OS调度，因为考核指标就是要求性能足够优越，我们就不能只考虑简单。所以此时就需要使用一些优秀的算法来实现，甚至是定制化的算法。
3. 代码技巧、算法都是为业务功能服务的，我们不追求炫技，但是我们需要针对不同的需求场景来使用不用的技术方法。

附录： 提升性能的定制单相链表demo

#include 
#include 
#include 
#include 

typedef struct os_tcb{
    int a;
    struct os_tcb *list_next_tcb;
} os_tcb_t;


static os_tcb_t *k2os_list_head_tcbs = NULL;
static os_tcb_t *k2os_list_tcbs_tail = NULL;

static void tcb_slist_add_tail(os_tcb_t *node)
{
    os_tcb_t *ptcb = NULL;

    if(k2os_list_head_tcbs == NULL){
        k2os_list_head_tcbs = node;
        k2os_list_tcbs_tail = node;
        return;
    }

    ptcb = k2os_list_tcbs_tail;
    ptcb->list_next_tcb = node;
    k2os_list_tcbs_tail = node;
}

#define tcb_slist_for_each_entry(node)              \
    for(node = k2os_list_head_tcbs; node; node = node->list_next_tcb)


#define tcb_slist_for_each_entry_safe(tmp, node)    \
    for(node = k2os_list_head_tcbs,                 \
        tmp = k2os_list_head_tcbs ? k2os_list_head_tcbs->list_next_tcb : NULL; \
        node;                                       \
        node = tmp, \
        tmp = tmp ? tmp->list_next_tcb : tmp)

static void tcb_slist_del2(os_tcb_t *node)
{
    os_tcb_t *ptmp = NULL, *ptcb = NULL;

    if(k2os_list_head_tcbs == node){
        k2os_list_head_tcbs = node->list_next_tcb;
        /* update the tcb tail */
        if(k2os_list_head_tcbs == NULL){
            k2os_list_tcbs_tail = NULL;
        }

        return;
    }

    tcb_slist_for_each_entry_safe(ptmp, ptcb){
        if(ptmp == node){
            ptcb->list_next_tcb = node->list_next_tcb;
             /* update the tcb tail */
            if(ptcb->list_next_tcb == NULL){
                k2os_list_tcbs_tail = ptcb;
            }

            return;
        }
    }
}


static void tcb_slist_del(os_tcb_t *node)
{
    os_tcb_t *ptcb;
    
    if(k2os_list_head_tcbs == node){
        k2os_list_head_tcbs = node->list_next_tcb;
        return;
    }

    ptcb = k2os_list_head_tcbs;
    while(ptcb->list_next_tcb){
        if(ptcb->list_next_tcb == node){
            ptcb->list_next_tcb == node->list_next_tcb;
            break;
        }
        ptcb = ptcb->list_next_tcb;
    }

    /* update k2os_list_tcbs_tail */
    tcb_slist_for_each_entry(ptcb){
        /*do nothing, go to the end of list */
    }

    k2os_list_tcbs_tail = ptcb;
}




int main(void)
{
    k2os_list_head_tcbs = NULL;
    os_tcb_t *ptcb, *ptcb_tmp;
    int i;
    printf("hello world.\n");

    for(i = 0; i > 0; i++){
        printf("hello i:%d\n", i);
    }

    printf("-------------------------1----------add 100 entry----\n");
    for(i = 0; i < 100; i++){
        ptcb = (os_tcb_t *)malloc(sizeof(os_tcb_t));
        ptcb->a = i + 1;
        ptcb->list_next_tcb = NULL;

        tcb_slist_add_tail(ptcb);
    }

    printf("-------------------------2---------- loop printf \n");
    printf("tcb head info: a = %02d, next addr:0x%lX\n", 
            k2os_list_head_tcbs->a, (long int)(k2os_list_head_tcbs));
    
    tcb_slist_for_each_entry(ptcb){
        printf("tcb info: a = %02d, next addr:0x%lX\n", 
            ptcb->a, (long int)(ptcb->list_next_tcb));
    }


    printf("-------------------------3----------- safe loop printf \n");
    printf("tcb head info: a = %02d, next addr:0x%lX\n", 
            k2os_list_head_tcbs->a, (long int)(k2os_list_head_tcbs));

    tcb_slist_for_each_entry_safe(ptcb_tmp, ptcb){
        printf("tcb info: a = %02d, next addr:0x%lX\n", 
            ptcb->a, (long int)(ptcb->list_next_tcb));
    }

    printf("-------------------------4------------ delete > 50 node \n");
    tcb_slist_for_each_entry_safe(ptcb_tmp, ptcb){
        if(ptcb->a > 50){
            printf("delete node[%02d]\n", ptcb->a);
            tcb_slist_del2(ptcb);
            free(ptcb);
        }
    }

    printf("-------------------------4------------ last print \n");
    tcb_slist_for_each_entry(ptcb){
        printf("tcb info: a = %02d, next addr:0x%lX\n", 
            ptcb->a, (long int)(ptcb->list_next_tcb));
    }

    printf("-------------------------5----------add > 50, 50 entry----\n");
    for(i = 0; i < 50; i++){
        ptcb = (os_tcb_t *)malloc(sizeof(os_tcb_t));
        ptcb->a = i + 51;
        ptcb->list_next_tcb = NULL;

        tcb_slist_add_tail(ptcb);
    }

    printf("-------------------------6---------- loop printf \n");
    printf("tcb head info: a = %02d, next addr:0x%lX\n", 
            k2os_list_head_tcbs->a, (long int)(k2os_list_head_tcbs));
    
    tcb_slist_for_each_entry(ptcb){
        printf("tcb info: a = %02d, next addr:0x%lX\n", 
            ptcb->a, (long int)(ptcb->list_next_tcb));
    }

    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171