浅谈FreeRTOS之唯快不破

1. 前言

         天下武功，唯快不破。FreeRTOS作为一款微控制器实时操作系统，其微内核，讲究极致的低资源消耗；其实时，追求的就是极致的快。本文主要从几个细节来阐述FreeRTOS为实时性所作出的努力。

2. 任务切换

图1 任务状态机

        FreeRTOS的每个任务拥有独立的堆栈，在自己独立的上下文中运行，而调度器要做的就是在触发调度时，以最快的速度选择处当前优先级最高的任务，使之进入运行状态。FreeRTOS的强大之处，在于仅使用双向链表和循环队列两种较复杂的数据结构就实现了整个内核。任务的调度就是依赖几个双向链表来实现的，其对应的任务状态机如图1所示。

2.1 任务调度相关的双向链表

PRIVILEGED_DATA static List_t pxReadyTasksLists[ configMAX_PRIORITIES ]; /*< Prioritised ready tasks. */
PRIVILEGED_DATA static List_t xDelayedTaskList1;                         /*< Delayed tasks. */
PRIVILEGED_DATA static List_t xDelayedTaskList2;                         /*< Delayed tasks (two lists are used - one for delays that have overflowed the current tick count. */
PRIVILEGED_DATA static List_t * volatile pxDelayedTaskList;              /*< Points to the delayed task list currently being used. */
PRIVILEGED_DATA static List_t * volatile pxOverflowDelayedTaskList;      /*< Points to the delayed task list currently being used to hold tasks that have overflowed the current tick count. */
PRIVILEGED_DATA static List_t xPendingReadyList;                         /*< Tasks that have been readied while the scheduler was suspended.  They will be moved to the ready list when the scheduler is resumed. */

       内核调度相关的链表包括pxReadyTasksLists数组（对应就绪态）、xDelayedTaskList1和xDelayedTaskList2（对应阻塞态）、xPendingReadyList（对应挂起态）。

        首先，就绪态对应的是一个链表数组，该数组的元素个数为configMAX_PRIORITIES，即内核为每个任务优先级都安排了一个链表，该链表内为各任务TCB（任务控制块）中表示任务状态的列表项，即且可以认为了装着一系列同优先级的任务。当触发调度时，调度器只要知道当前就绪任务中的最高优先级，就可以按图索骥，根据该链表找到对应任务的TCB，而同一个就绪链表中的多个任务则按时序排列，类似于队列，先到先处理。

        其次，由于阻塞态需要维护任务阻塞时间，内核采用了两个链表实体，并由pxDelayedTaskList和pxOverflowDelayedTaskList交替指向这两个链表，巧妙地解决了计时器可能存在计数溢出的问题。指针的高效率巧妙地避免了不必要的数据搬运，使得阻塞时间的维护变的轻松。

2.2 触发任务切换的两种方式

2.2.1 在系统时钟中断时触发调度

/*-----------------------------------------------------------*/

void xPortSysTickHandler( void )
{
    /* The SysTick runs at the lowest interrupt priority, so when this interrupt
     * executes all interrupts must be unmasked.  There is therefore no need to
     * save and then restore the interrupt mask value as its value is already
     * known. */
    portDISABLE_INTERRUPTS();
    {
        /* Increment the RTOS tick. */
        if( xTaskIncrementTick() != pdFALSE )
        {
            /* A context switch is required.  Context switching is performed in
             * the PendSV interrupt.  Pend the PendSV interrupt. */
            portNVIC_INT_CTRL_REG = portNVIC_PENDSVSET_BIT;
        }
    }
    portENABLE_INTERRUPTS();
}
/*-----------------------------------------------------------*/

        当系统中断到来时，xTaskIncrementTick会查询阻塞态列表，如果存在任务阻塞时间溢出，则将该任务添加到对应优先级的就绪态任务列表中，进一步地，如果该任务的优先级大于当前运行的任务，则触发调度。

        随后，也会判断就绪态任务列表中，是否存在与当前运行的任务同优先级的任务，如果存在，也会触发调度（同优先级分时运行）。

        触发调度后，置位PendSv，进行任务切换，具体的处理过程此处不展开，可以参照另一篇博文《FreeRtos(Arm M7)中断压栈分析》进行理解；

2.2.2 应用程序发起任务调度请求

    #define portYIELD()                                 \
    {                                                   \
        /* Set a PendSV to request a context switch. */ \
        portNVIC_INT_CTRL_REG = portNVIC_PENDSVSET_BIT; \
                                                        \
        /* Barriers are normally not required but do ensure the code is completely \
         * within the specified behaviour for the architecture. */ \
        __asm volatile ( "dsb" ::: "memory" );                     \
        __asm volatile ( "isb" );                                  \
    }

    #define portEND_SWITCHING_ISR( xSwitchRequired )    do { if( xSwitchRequired != pdFALSE ) portYIELD(); } while( 0 )

        内核给应用程序提供了发起任务调度请求的接口，包括  portYIELD 和 portYIELD_FROM_ISR，其本质都是通过置位PendSv来实现的。

2.3 如何快速找到当前最高优先级的任务

        PendSv被置位悬起后，会由void xPortPendSVHandler调用vTaskSwitchContext来进行任务调度的具体处理。其中最关键的就是快速找到当前优先级最高的任务，这主要由taskSELECT_HIGHEST_PRIORITY_TASK来实现。 其中，uxTopReadyPriority为内核维护的一个静态变量，记录着系统当前就绪态任务的优先级信息。而在这个变量的维护上，存在着两种方式。

        一种较为通用的方法是用uxTopReadyPriority记录就绪态任务中的最高优先级：

/* uxTopReadyPriority holds the priority of the highest priority ready
 * state task. */
    #define taskRECORD_READY_PRIORITY( uxPriority ) \
    {                                               \
        if( ( uxPriority ) > uxTopReadyPriority )   \
        {                                           \
            uxTopReadyPriority = ( uxPriority );    \
        }                                           \
    } /* taskRECORD_READY_PRIORITY */

/*-----------------------------------------------------------*/

/*-----------------------------------------------------------*/

    #define taskSELECT_HIGHEST_PRIORITY_TASK()                                \
    {                                                                         \
        UBaseType_t uxTopPriority = uxTopReadyPriority;                       \
                                                                              \
        /* Find the highest priority queue that contains ready tasks. */      \
        while( listLIST_IS_EMPTY( &( pxReadyTasksLists[ uxTopPriority ] ) ) ) \
        {                                                                     \
            configASSERT( uxTopPriority );                                    \
            --uxTopPriority;                                                  \
        }                                                                     \
                                                                              \
        /* listGET_OWNER_OF_NEXT_ENTRY indexes through the list, so the tasks of \
         * the  same priority get an equal share of the processor time. */                    \
        listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority ] ) ); \
        uxTopReadyPriority = uxTopPriority;                                                   \
    } /* taskSELECT_HIGHEST_PRIORITY_TASK */

/*-----------------------------------------------------------*/

        显然，这种方式uxTopReadyPriority只能记录一个优先级信息，完全由C语言实现，通用性强，其对应的taskSELECT_HIGHEST_PRIORITY_TASK实现方式也不同，即通过while循环来寻找到非空的优先级任务列表。由于uxTopReadyPriority记录了当前就绪的最高优先级，这个while循环通常首次执行就会退出，但这种遍历的写法显然给人一种不够快的感觉。

        而另一种改进版的方式，则是使用了利用了处理器的前导0计算指令，以位图的方式来记录就绪态任务的优先级：

#define portRECORD_READY_PRIORITY( uxPriority, uxReadyPriorities )    ( uxReadyPriorities ) |= ( 1UL << ( uxPriority ) )
    
#define taskRECORD_READY_PRIORITY( uxPriority )    portRECORD_READY_PRIORITY( uxPriority, uxTopReadyPriority )

__attribute__( ( always_inline ) ) static inline uint8_t ucPortCountLeadingZeros( uint32_t ulBitmap )
{
     uint8_t ucReturn;

     __asm volatile ( "clz %0, %1" : "=r" ( ucReturn ) : "r" ( ulBitmap ) : "memory" );

     return ucReturn;
}

#define portGET_HIGHEST_PRIORITY( uxTopPriority, uxReadyPriorities )    uxTopPriority = ( 31UL - ( uint32_t ) ucPortCountLeadingZeros( ( uxReadyPriorities ) ) )

PRIVILEGED_DATA static volatile UBaseType_t uxTopReadyPriority = tskIDLE_PRIORITY;

/*-----------------------------------------------------------*/

    #define taskSELECT_HIGHEST_PRIORITY_TASK()                                                  \
    {                                                                                           \
        UBaseType_t uxTopPriority;                                                              \
                                                                                                \
        /* Find the highest priority list that contains ready tasks. */                         \
        portGET_HIGHEST_PRIORITY( uxTopPriority, uxTopReadyPriority );                          \
        configASSERT( listCURRENT_LIST_LENGTH( &( pxReadyTasksLists[ uxTopPriority ] ) ) > 0 ); \
        listGET_OWNER_OF_NEXT_ENTRY( pxCurrentTCB, &( pxReadyTasksLists[ uxTopPriority ] ) );   \
    } /* taskSELECT_HIGHEST_PRIORITY_TASK() */

/*-----------------------------------------------------------*/

        这种情况下，所有就绪态任务的优先级被按位map在uxTopReadyPriority中，而通过clz指令来计算其前导0的个数，从而确定就绪态任务的最高优先级。例如，当uxTopReadyPriority（32位平台，unsigned long，4字节）的值为0xff时，其前导0的个数为24个，从而得到就绪任务的最高优先级为31-24 = 7，从而对应就绪态任务列表数组的第7个列表。clz指令在处理器的汇编层面，速度很快。

        需要注意的是，由于uxTopReadyPriority只有32位，这种情况下，系统最高支持32个任务优先级。