构建RTOS Kernel指南 (下)

单单具有任务切换功能自然不能称之为RTOS Kernel，一个任务往往具有多个重要的属性，优先级就是其中之一。一个任务的优先级决定了它的“尊贵”程度，越尊贵的任务越有优先占用CPU运行的权力。

1优先级查找

位图是指一组连续的标志位，是一种常见的优先级框架的实现方式。每个比特位通常用来对应一个优先级，越低位的优先级越高，其状态标识该优先级是否有就绪状态的任务。

以下图32位为例，存在优先级为1、7、9、16……24、25、31的就绪态任务。每个优先级存在对应的任务链表，同一个优先级中采用“先就绪先执行”的原则。

图1 位图

那么，CPU的任务从“寻找优先级最高的任务”变成了“寻找位图中最低位的1”。如果按照上图中依次按位查找，速度是较慢的，系统的实时性可能会有一定程度的影响，下面介绍一种较为巧妙的方法——分组查表法。

图2 分组查表法

const rt_uint8_t __lowest_bit_bitmap[] =
{
    /* 00 */ 0, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 10 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 20 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 30 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 40 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 50 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 60 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 70 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 80 */ 7, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* 90 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* A0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* B0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* C0 */ 6, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* D0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* E0 */ 5, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0,
    /* F0 */ 4, 0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0
};

int __rt_ffs(int value)
{
    if (value == 0) return 0;

    if (value & 0xff)
        return __lowest_bit_bitmap[value & 0xff] + 1;

    if (value & 0xff00)
        return __lowest_bit_bitmap[(value & 0xff00) >> 8] + 9;

    if (value & 0xff0000)
        return __lowest_bit_bitmap[(value & 0xff0000) >> 16] + 17;

    return __lowest_bit_bitmap[(value & 0xff000000) >> 24] + 25;

这种方法将32位共分成4组，每组8位，那么每组的8位二进制数0x00~0xFF对应数组bitmap的序号0-255，数组中的值的含义为其对应8位二进制数最低位“1”的序号。那么通过这样巧妙的分组查表方式，通过至多四次查找，便可得到位图的最低位“1”的位置。除此之外，还有更为巧妙的利用汇编指令CLZ和RBIT组合实现这个目的，其中CLZ可以统计出现“1”的最高位位置，RBIT是数据进行按位反转的指令。这样就可以先通过RBIT进行位反转，再通过CLZ获取反转后最高位“1”的位置，即原数据中最低位“1”的位置。

2临界区保护和线程同步

在RTOS中，时常会出现多个线程访问公用资源的情况，即都需要访问公用的程序片段，如若没有对应的处理机制，可能会对系统造成意想不到的混乱。常用的方法有调度器上锁和禁止中断，这两者相互依赖，例如在调度器上锁时需要禁止中断。除此之外，还可以采用互斥机制来进行临界区保护，如信号量和互斥量，这两者也用于线程的同步机制。

图3 信号量类比

信号量可以类比停车位，当有空车位的时候，才能开进停车场，对于线程而言，假如某临界资源对应的信号量为0，是不能对其进行操作的。信号量应该有两个重要的属性：信号量值和等待队列，信号量的值表示对应可操作临界资源实例数，假如线程申请信号量是其值为0，那么该线程将被挂起在此信号量的等待队列。

图4 互斥量类比

互斥量的作用类似于二值信号量，它是一种特殊的信号量，只具有“上锁”和“解锁”两种状态，对应的临界资源具有极强的排他性。就像景区的豪华单间卫生间，每个人在使用的时候都不能被打扰。虽然功能类似，但是二值信号量和互斥量还是有区别的，后续会进行相应的介绍。

图5 事件集工作原理

除了信号量互斥量，还有一种有趣的同步机制-事件集，它通常可以用一个32位二进制数表示，每一位代表了一个事件，也可以说成一种触发条件，而事件集的作用便是可以用“逻辑或”和“逻辑与”自由组合出想要触发的条件，就好像“明天天气好”和“我心情愉悦”都发生，“我出去郊游”才会触发，又像“发表一篇论文”或“发明一项专利”任一发生，都触发“达成硕士毕业标准”。

3优先级反转问题

当隐入互斥量的机制后，读者可以思考一下，这会不会和优先级机制产生冲突？

一个是根据优先级制定的“国家法律”，一个是根据临界资源制定的“地方法律”，当遵守“地方法律“的时候会不会违背“国家法律”？这就是优先级反转问题。

图6 优先级反转

如上图，假设我们有三个线程，它们的优先级Thread1 > Thread2 > Thread3，t0之前Thread3获取某资源的互斥量，互斥量值变locked状态，t0时刻Thread2线程就绪，由于优先级Thread2 > Thread3，Thread3让出CPU执行权给Thread2，但没有解开互斥量。到t1时刻，Thread1就绪，Thread2让出CPU，Thread1执行过程申请Thread3所占有的互斥量，由于互斥量为locked状态，在t2时刻Thread1被挂起等待，剩余两个就绪态的线程Thread2优先级高于Thread1，因此继续执行。

至此，我们发现，都处于就绪态的线程，低优先级的Thread2反而能比高优先级的Thread1优先执行，其原因是更低优先级的Thread3占有信号量并被抢占，造成了优先级反转。所以为了让“地方法律”更加适配“国家法律”，常用的做法是优先级继承。即可以让Thread3短暂地提升到Thread1的优先级，得以抢占CPU快速执行完将互斥量解锁，从而让Thread1及时获取到互斥量得以执行。除此之外，还存在一些另外的处理方式，如优先级天花板等，有兴趣的读者可以自行查阅相关资料。

二值信号量和互斥信号量非常类似，但还是有一些细微的差别。互斥信号量拥有优先级继承机制，而二值信号量没有。互斥量必须是同一个任务申请，同一个任务释放，其他任务释放无效，且同一个任务可以递归申请。然而对于二值信号量，一个任务申请成功后，可以由另一个任务释放，因此二值信号另更适合用于同步（任务与任务或任务与中断的同步），互斥信号量适合用于简单的互斥访问。

4线程间通信

线程间通信主要是通过消息队列和邮箱实现，消息队列一般采用先进先出的原则（FIFO），而邮箱可以理解成队列长度为1的特殊消息队列，但是消息队列中为待传输的数据按值拷贝的副本，所以支持各种类型的数据的传递，而邮箱中传输的通常为指向待交换数据的指针。

5总结

至此，一个RTOS的内核功能基本就实现了，下面对一个RTOS Kernel应具备的功能进行分条总结：

实时性：实时系统对任务的响应时间要求较高。具备严格的按优先级调度任务的机制，并且一般要支持抢占式调度。

多任务调度：RTOS需要能够同时管理多个任务，并合理分配CPU时间片给每个任务。设计任务调度算法以确保相同优先级的任务能公平使用CPU，避免优先级反转问题，并提供优先级继承、优先级天花板等机制。

同步和通信：多任务系统中，任务之间需要进行同步和通信。设计合适的同步机制，如信号量、互斥锁、消息队列等，并确保在多个任务之间实现可靠的数据传输和共享。

但是，这些仅仅是内核的基本功能，一个成熟的RTOS还应该具有更多的扩展功能予以支撑。例如内存管理功能、外设驱动的支持、硬件依赖性和可移植性、调试和测试功能等等。罗马非一日而建，希望大家都能脚踏实地，乐于钻研，乐于进步，共勉！