Build Your Own RTOS Advanced Part1：任务优先级

Build Your Own RTOS Advanced系列文章：

当前阅读：任务优先级

写在前面

这是 Build Your Own RTOS 系列文章的续集，也是提高篇。预计内容有四章：优先级调度、互斥锁、队列以及内存管理。这都是现代RTOS比较精髓的部分，但同时也会有一定的难度。和之前一样，作者不会手把手的教学写代码，只是记录自己的coding过程顺便记录一些知识点，希望做到一定的参考作用。

1 升级

在真实的系统中，时间片轮转虽然可以解决一部分的问题，但是有许多困难是不可解决的。比如说你的两个任务，闪烁LED和火灾报警，当报警的需求产生时，CPU却还在闪烁LED，在嵌入式系统中是难以接受的。所以，我们必须设计一种算法，让CPU可以判断哪个任务更加紧急，直接踢走低优先级的任务（即使它此刻正在运行！）。

1.1 时间复杂度与确定性

既然我们需要设计算法，很自然的就可以想到遍历。CPU从零开始遍历一遍某个数组，直到其找到一个任务，这个任务就是优先级最高的。但是这个算法有一个显而易见的劣势：它的时间复杂度是O(N)，即所消耗的时间与任务个数成正比例。即使我们的任务很少，即使遍历数组这个操作本身非常快，我们还是不希望它这么做，因为这损坏了RTOS的确定性。我们希望在系统中的每一个操作都只需要恒定时间，而不是像遍历这样消耗不确定的时间。

所以，我们应该且必须设计出一个O(1)的算法。这就引出一个概念：位图（Bitmap）。所谓位图，就是使用一个定长的整数，例如uint32_t，作为一个“地图”，它的每一位来代表一个优先级。比如第0位是1，就代表有一个优先级为0的任务。（注意我们一般设定优先级数字越低，优先级越高。为了简化，本期我们只实现同个优先级下只有一个任务）

那么查找优先级，就变成了：找到在这个整数中的位数最低的1。这时你的脑海里可能自动蹦出了软件的实现方法：循环查找每一位，直到找到一个1。但是这样不还是O(N)吗？所以我们不能依赖软件来实现，直接用硬件给我们优化好的指令CLZ。这条指令可以在一个指令周期内就完成：查找一个整数前面有多少个0。注意如果单独使用CLZ只能找到优先级最低的任务，所以我们配合上另一条指令RBIT来翻转一个整数，这样就可以找到优先级最高的任务，且只消耗两个指令周期。

2 开始编码

理论说完了，其实很简单。但是我们需要修改的地方是很多的，包括TCB、FindNextTask()等等。

2.1 TCB

任务的优先级是任务的特性，自然是塞在任务控制块里。

typedef struct Task_Control_Block
{
    volatile uint32_t *stackPtr; ///< 任务对应的栈指针
    struct Task_Control_Block *Next; ///< 指向下一个任务的指针
    OS_TaskState State; ///< 任务状态
    volatile uint32_t DelayTicks; ///< 延时的时间（单位ms）
    struct Task_Control_Block *NextWaitTask; ///< 指向下一个正在等待同一个信号量的任务
    volatile uint8_t Priority;  ///< 任务优先级
} OS_TCB;

2.2 就绪列表

现在我们的任务轮转不能是简单的CurrentTCB->Next，我们需要新建一个全局的指针数组OS_TCB *ReadyList[OS_MAX_PRIO]（这里的OS_MAX_PRIO应该用一个宏定义，通常设为32）。ReadyList[0]存放优先级为 0 的任务指针，ReadyList[1]存放优先级为 1 的任务指针……

好了，有了列表之后，我们就要想它如何和我们的位图uint32_t g_PrioMap交互。ReadyList[0]对应的应该是g_PrioMap的第0位，以此类推。当一个优先级为p的任务进入/退出阻塞态时，位图中对应的位就要置0/置1。

注意：我们并不能删除TCB里的Next成员。 OS_Tick_Handler()仍然使用旧的任务链表来管理时间，只是调度改用新的方法。

2.3 `FindNextTask`

有了以上逻辑，其实FindNextTask()的逻辑也很清晰了。这里直接给出代码。

/* in os_cpu.c */
uint8_t OS_GetTopPrio(uint32_t PrioMap)
{
    return __CLZ(__RBIT(PrioMap)); // 这是ARM封装好的两个宏指令，和上面的汇编指令一样
}

/* in os_core.c */
OS_TCB *FindNextTask(void)
{
    if(g_PrioMap == 0) while(1); // 如果g_PrioMap==0 说明出现错误，我们就卡在这

    uint8_t TopPrio = OS_GetTopPrio(g_PrioMap); // 由于涉及宏汇编指令，我们在os_cpu.c里封装Get_TopPrio

    return ReadyList[TopPrio];
}

2.4 注册与注销

注册和注销，就是任务进入/退出就绪态所要做的事情：将自身填入ReadyList或在ReadyList里清除自己，修改g_PrioMap自己对应的那一位。

我们这里将这两个操作封装成辅助函数。它们的逻辑非常简单，都只需两行代码：

注册：任务对应哪个优先级，就把g_PrioMap对应的那一位置1，然后将ReadyList中任务优先级对应的那个元素替换成这个任务。
注销：任务对应哪个优先级，就把g_PrioMap对应的那一位置0，然后将ReadyList中任务优先级对应的那个元素替换成NULL。

代码如下：

static void OS_ReadyListAdd(OS_TCB* tcb)
{
    g_PrioMap |= (1U << tcb->Priority);
    ReadyList[tcb->Priority] = tcb;
} 

static void OS_ReadyListRemove(OS_TCB* tcb)
{
    g_PrioMap &= ~(1U << tcb->Priority);
    ReadyList[tcb->Priority] = NULL;
}

接下来我们就可以用这两个函数修改其他的地方。对于每一个把任务设置为就绪态/阻塞态的地方，都要有一个注册或注销的函数对应。我们首先修改OS_TaskCreate()，添加任务优先级的初始化，然后不要忘记由于任务出生时是就绪的，所以这个函数里也要注册一次任务。然后我们要修改OS_Tick_Handler()、OS_Delay()、OS_SemWait()、OS_SemPost()。注意还要修改OS_StartScheduler()里空闲函数的初始化部分，将空闲函数的优先级设置为最低（数值最高，31）。

void OS_TaskCreate(OS_TCB *tcb, void *task_function, uint32_t *stack_init_address, uint32_t stack_depth, uint8_t priority)
{
    /* 之前代码 */
    tcb->NextWaitTask = NULL;
    tcb->Priority = priority; // 给任务设置优先级
    OS_ReadyListAdd(tcb); // 注册任务
    /* 之后代码不变 */
}

void OS_Tick_Handler(void)
{
    /* 之前代码不变 */
    do
    {
        if (ptr->State == TASK_BLOCKED)
        {
            if (ptr->DelayTicks > 0)
            {
                ptr->DelayTicks--;
                if (ptr->DelayTicks == 0)
                {
                    ptr->State = TASK_READY;
                    OS_ReadyListAdd(ptr); // 添加注册
                }
            }
        }
        ptr = ptr->Next; // 将当前标记指针指向下一个任务
    } while (ptr != CurrentTCB);
    /* 之后代码不变 */
}

void OS_Delay(uint32_t ticks)
{ 
    /* 之前代码不变 */
    CurrentTCB->State = TASK_BLOCKED; 
    OS_ReadyListRemove(CurrentTCB); // 添加注销
    /* 之后代码不变 */
}

uint8_t OS_SemWait(OS_Sem *p_sem)
{
    /* 之前代码不变 */
    else // 原本没信号量，我睡觉去了，直到信号量来了
    {
        CurrentTCB->State = TASK_BLOCKED; // 设置当前任务状态

        OS_ReadyListRemove(CurrentTCB); // 添加注销

        /* 之后代码不变 */
    }
}

uint8_t OS_SemPost(OS_Sem *p_sem)
{
    /* 之前代码不变 */
    else
    {
      /* 省略 */
        TaskToWake->State = TASK_READY;

        OS_ReadyListAdd(TaskToWake); // 添加注册

        NextTCB = FindNextTask(); // 寻找是否有高优先级的任务苏醒了
        OS_Trigger_PendSV(); // 立刻触发PendSV 这就是抢占
        OS_ExitCritical();
    }
}

至此，我们所有的优先级调度代码修改完毕了。

3 动手

代码写完了就开始实操。我们在main.c里创建这样两个任务：

// 高优先级任务 (Prio 0)
void Task_High(void)
{
    while (1)
    {
        // 翻转 LED_BLUE
        HAL_GPIO_TogglePin(LED_BLUE_GPIO_Port, LED_BLUE_Pin);
        
        // 纯软件延时（死循环），不交出 CPU 权！
        // 绝对不要调用 OS_Delay 或 OS_SemWait
        for(volatile int i=0; i<1000000; i++); 
    }
}

// 低优先级任务 (Prio 1)
void Task_Low(void)
{
    while (1)
    {
        // 如果抢占逻辑正确，这行代码永远不会执行
        // LED_RED 应该永远不亮，或者保持初始状态
        HAL_GPIO_TogglePin(LED_RED_GPIO_Port, LED_RED_Pin);
        
        OS_Delay(100);
    }
}

可以看到，高优先级的任务从不进入阻塞态，一直处于就绪态。也就是说，如果我们的抢占调度逻辑正常，高优先级的任务会“饿死”低优先级的任务，让红灯永远保持状态。

4 总结

至此，我们的RTOS完成了一次质的飞跃。通过引入位图和硬件指令优化，我们成功将调度算法的时间复杂度压到了O(1)。这意味着无论系统中有多少个任务，调度器都能在恒定的时间内找到那个最重要的任务，这正是“硬实时”系统的基石。

在最后的实验中，我们亲眼见证了“饥饿”现象：高优先级任务无情地霸占了CPU，低优先级任务完全无法运行。虽然这验证了我们的抢占逻辑是正确的，但在实际开发中，任务之间往往需要协作和共享资源。如果低优先级任务占用了资源还没来得及释放，就被高优先级任务抢占了，会发生什么？

这就引入了并发编程中最棘手的问题之一——竞态条件与优先级反转。为了解决这些问题，单纯的信号量可能已经力不从心了。

下一章，我们将深入探讨“互斥（Mutex）”，看看它是如何保护共享资源，又是如何防止高优先级任务被“卡死”的。