1.等待表用途
在多任务系统中，一些任务往往需要在运行到节点时等待一段时间。等待表的作用是帮助操作系统的核心管理。 当运行任务需要延迟等待时，操作系统内核将任务从就绪表移动到等待表；延迟等待时间完成后，操作系统内核将任务从等待表移动到就绪表，状态图如下： 
例如现在需要连续读取一个温湿度传感头的数据，但是该温度传感器在启动一次测量到输出一个稳定数值需要等待50ms。我们有两种策略： 1.启动测量后死亡等50ms，然后读取测量值。 2.启动测量后，操作其他任务，50ms然后读取温湿度测量值。 这两种策略的运行状态如下图所示： 很明显，这种策略需要在延迟等待时执行其他任务。CPU利用率较高，操作系统内核利用等待表实现此策略。
2.等待策略
有两种常见的策略有两种常见策略：
相信大家都看过火箭发射的场景，清晰洪亮的倒计时声似乎在耳边回响: 10…9…8…7…6…5…4…3…2…1…0 火箭发射的就是使用的倒计时法，这种策略只用关注剩余的时间。 当大多数人早上起床时，他们必须被设定的闹钟唤醒。这种策略使用非常方便，只需注意设定的时间即可。
倒计时法的算法逻辑是：判断剩余时间是否为0，如果剩余时间不为0，如果剩余时间为0，则完成延迟等待。 闹钟法的算法逻辑是：比较当前时间是否小于设定时间，小于设定时间继续等待，不小于设定时间完成延迟等待。
倒计时需要一个判断操作和一个减法操作，闹钟法只需要一个判断操作(当前时间由系统生成)。由于闹钟法执行步骤较少，闹钟法机制通常用于实时操作系统的等待表。 闹钟法有时间归零的问题。假设当前时间是23点，如果需要等待2小时，闹钟时间会变成1点。这里需要注意比较逻辑和计算逻辑。
3.等待表实现
可以通过静态数组构建一个就绪表，代码如下： 其中tcb_item_t为 TCB项 ，list_item_t列表项，delay_table为等待表。 delay_table每个列表包含10个列表TCB项，itme[0]表示任务0，itme[9]表示任务9。 每个TCB项目中包含一个标志位和TCB指针，TCB指针指向任务TCB数据结构图如下： 使用该方法的优点是：结构简单，使用方便。但使用静态数组的缺点非常明显： 1.每个优先级容纳的任务数量是固定的。一旦需要增加优先级任务数量，整个列表将增加。 2.在同一优先任务中插入一个任务，需要移动多个任务TCB项。 3.存在多种优先级无用的情况，导致内存严重浪费。
可使用构建等待表代码实现如下： list_item_t列表项，delay_table为等待表。 每个list_item_t列表中包含一个TCB指针，下列项指针和上列项指针。数据结构图如下： 使用该方法具有以下优点： 1.每个链表可以连接任何数量的链表项，长度不受限制。 2.链表的每一项都是有用的，没有内存浪费 3.在链表中间插入一项，操作效率高。
4.等待表优化
上面提出了一个等待表，用链表构建。链表是根据时间构建的间小的放在链表头部，时间大的放在链表尾部。每次更新时间只能检查第一个对象，因为第一个对象时间最小(与当前时间间隔最小)。 这种方法很简单，但有一个问题：当任务很多时，插入和删除新任务的时间成本将非常大。例如，现在有100个任务。假设新插入的任务延迟最长，则需要执行100次比较和100次阅读下一个任务才能完成插入操作。
首先例子解释时间取模分表法： 假设现在有一家靠近火车站的酒店，客户进入酒店休息，申请醒来业务，酒店及时提供服务员醒来服务，假设醒来业务分为单位。由于客户的时间是无序的，不同客户的等待时间也是无序的，如果在这里制作一个普通的醒来表，每次更新一分钟，服务员应检查以下所有客户的固定时间，这也很容易出错。 因此，我们用时间取模分表制作一个特殊的表： 时间是当前时间的个位，如12:37对应时间为7 ，8:15对应时间为5。客户信息包括闹钟时间和房间号，按时间由近到远排列。 加入客户后的叫醒表如下：
此时，服务员只需检查当前时间的时间位置，然后判断相应项目的第一个客户是否到达，整个过程只需判断两次。 例如：当前时间为8点05分，服务员只有判断表中时间为5的那列，然后检查第一个，结果是没有客户需要唤醒。 例如，当前时间是9:02，服务员只有判断表中时间为2的列，然后检查第一个列。因此，没有客户需要醒来。 例如当前时间是11:19，服务员只判断表中时间是9，然后检查第一个，结果是客户需要唤醒。
5.FreeRTOS源码分析
FreeRTOS等待表的定义如下： FreeRTOS等待表采用排序链表法。
等待表的三种操作方法： 1.插入等待表。 2.移除等待表。 3.查询等待表。
/* 将任务插入等待表，插入位置和延迟 */ vListInsert( pxDelayedTaskList, &( pxCurrentTCB->xStateListItem ) );
将任务插入等待表，插入位置和延时时候有关，时间小的放在链表头部，时间大的放在链表尾部。
将任务从等待表头部移除，每次更新时间只检查等待表的第一个对象，因为第一个对象是时间最小的（与当前时间间隔最小）。
/* 将等待表的表头任务移除 */
( void ) uxListRemove( &( pxTCB->xStateListItem ));
pxTCB = listGET_OWNER_OF_HEAD_ENTRY( pxDelayedTaskList ); /* 获取等待表的表头 */
xItemValue = listGET_LIST_ITEM_VALUE( &( pxTCB->xStateListItem ) ); /* 获取表头任务的延时时间 */
if( xConstTickCount < xItemValue ) /* 比较延时时间 */
{
xNextTaskUnblockTime = xItemValue;
break;
}
从等待表头部获取任务，每次更新时间只检查等待表的第一个对象，因为第一个对象是时间最小的（与当前时间间隔最小），判断该任务等待时间是否完成。
6.FreeRTOS等待表更新维护
前文说明了等待表的3种操作方法：插入等待表，移除等待表，查询等待表。操作系统在哪些地方完成这些操作，下面来一一列举一下：
vTaskDelay的作用是当前任务需要延时等待一定时间,该系统函数的调用流程如下：
vTaskDelay ->
prvAddCurrentTaskToDelayedList->
vListInsert( pxDelayedTaskList, &( pxCurrentTCB->xStateListItem ) )
等待表变化：将当前任务从就绪表中移除，然后将当前任务插入等待表中，对应的优先级位清0。（清0操作会判断该优先级下的就绪任务总数量）
vTaskDelayUntil的作用是当前任务需要延时等待一定时间,该系统函数的调用流程如下：
vTaskDelayUntil->
prvAddCurrentTaskToDelayedList->
vListInsert( pxDelayedTaskList, &( pxCurrentTCB->xStateListItem ) )
等待表变化：将当前任务从就绪表中移除，然后将当前任务插入等待表中，对应的优先级位清0。（清0操作会判断该优先级下的就绪任务总数量）
XPortSysTickHandler的作用是定时更新系统时间,并判断任务是否完成等待时间，该系统函数的调用流程如下：
XPortSysTickHandler->
xTaskIncrementTick->
listGET_OWNER_OF_HEAD_ENTRY
listGET_LIST_ITEM_VALUE
( void ) uxListRemove( &( pxTCB->xStateListItem ) );
等待表变化：将当前任务从等待表中移除，然后将当前任务插入就绪表中，对应的优先级位清1。
7.源码
PRIVILEGED_DATA static List_t * volatile pxDelayedTaskList; /* 等待表 */
void vTaskDelay( const TickType_t xTicksToDelay )
{
BaseType_t xAlreadyYielded = pdFALSE;
/* A delay time of zero just forces a reschedule. */
if( xTicksToDelay > ( TickType_t ) 0U )
{
configASSERT( uxSchedulerSuspended == 0 );
vTaskSuspendAll();
{
traceTASK_DELAY();
/* A task that is removed from the event list while the scheduler is suspended will not get placed in the ready list or removed from the blocked list until the scheduler is resumed. This task cannot be in an event list as it is the currently executing task. */
prvAddCurrentTaskToDelayedList( xTicksToDelay, pdFALSE );
}
xAlreadyYielded = xTaskResumeAll();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* Force a reschedule if xTaskResumeAll has not already done so, we may have put ourselves to sleep. */
if( xAlreadyYielded == pdFALSE )
{
portYIELD_WITHIN_API();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
static void prvAddCurrentTaskToDelayedList( TickType_t xTicksToWait, const BaseType_t xCanBlockIndefinitely )
{
TickType_t xTimeToWake;
const TickType_t xConstTickCount = xTickCount;
#if( INCLUDE_xTaskAbortDelay == 1 )
{
/* About to enter a delayed list, so ensure the ucDelayAborted flag is reset to pdFALSE so it can be detected as having been set to pdTRUE when the task leaves the Blocked state. */
pxCurrentTCB->ucDelayAborted = pdFALSE;
}
#endif
/* Remove the task from the ready list before adding it to the blocked list as the same list item is used for both lists. */
if( uxListRemove( &( pxCurrentTCB->xStateListItem ) ) == ( UBaseType_t ) 0 )
{
/* The current task must be in a ready list, so there is no need to check, and the port reset macro can be called directly. */
portRESET_READY_PRIORITY( pxCurrentTCB->uxPriority, uxTopReadyPriority ); /*lint !e931 pxCurrentTCB cannot change as it is the calling task. pxCurrentTCB->uxPriority and uxTopReadyPriority cannot change as called with scheduler suspended or in a critical section. */
}
else
{
mtCOVERAGE_TEST_MARKER();
}
#if ( INCLUDE_vTaskSuspend == 1 )
{
if( ( xTicksToWait == portMAX_DELAY ) && ( xCanBlockIndefinitely != pdFALSE ) )
{
/* Add the task to the suspended task list instead of a delayed task list to ensure it is not woken by a timing event. It will block indefinitely. */
vListInsertEnd( &xSuspendedTaskList, &( pxCurrentTCB->xStateListItem ) );
}
else
{
/* Calculate the time at which the task should be woken if the event does not occur. This may overflow but this doesn't matter, the kernel will manage it correctly. */
xTimeToWake = xConstTickCount + xTicksToWait;
/* The list item will be inserted in wake time order. */
listSET_LIST_ITEM_VALUE( &( pxCurrentTCB->xStateListItem ), xTimeToWake );
if( xTimeToWake < xConstTickCount )
{
/* Wake time has overflowed. Place this item in the overflow list. */
vListInsert( pxOverflowDelayedTaskList, &( pxCurrentTCB->xStateListItem ) );
}
else
{
/* The wake time has not overflowed, so the current block list is used. */
vListInsert( pxDelayedTaskList, &( pxCurrentTCB->xStateListItem ) );
/* If the task entering the blocked state was placed at the head of the list of blocked tasks then xNextTaskUnblockTime needs to be updated too. */
if( xTimeToWake < xNextTaskUnblockTime )
{
xNextTaskUnblockTime = xTimeToWake;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
}
}
#else /* INCLUDE_vTaskSuspend */
{
/* Calculate the time at which the task should be woken if the event does not occur. This may overflow but this doesn't matter, the kernel will manage it correctly. */
xTimeToWake = xConstTickCount + xTicksToWait;
/* The list item will be inserted in wake time order. */
listSET_LIST_ITEM_VALUE( &( pxCurrentTCB->xStateListItem ), xTimeToWake );
if( xTimeToWake < xConstTickCount )
{
/* Wake time has overflowed. Place this item in the overflow list. */
vListInsert( pxOverflowDelayedTaskList, &( pxCurrentTCB->xStateListItem ) );
}
else
{
/* The wake time has not overflowed, so the current block list is used. */
vListInsert( pxDelayedTaskList, &( pxCurrentTCB->xStateListItem ) );
/* If the task entering the blocked state was placed at the head of the list of blocked tasks then xNextTaskUnblockTime needs to be updated too. */
if( xTimeToWake < xNextTaskUnblockTime )
{
xNextTaskUnblockTime = xTimeToWake;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
/* Avoid compiler warning when INCLUDE_vTaskSuspend is not 1. */
( void ) xCanBlockIndefinitely;
}
#endif /* INCLUDE_vTaskSuspend */
}
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 - therefore the slightly faster vPortRaiseBASEPRI() function is used in place of portSET_INTERRUPT_MASK_FROM_ISR(). */
vPortRaiseBASEPRI();
{
/* 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;
}
}
vPortClearBASEPRIFromISR();
}
BaseType_t xTaskIncrementTick( void )
{
TCB_t * pxTCB;
TickType_t xItemValue;
BaseType_t xSwitchRequired = pdFALSE;
/* Called by the portable layer each time a tick interrupt occurs. Increments the tick then checks to see if the new tick value will cause any tasks to be unblocked. */
traceTASK_INCREMENT_TICK( xTickCount );
if( uxSchedulerSuspended == ( UBaseType_t ) pdFALSE )
{
/* Minor optimisation. The tick count cannot change in this block. */
const TickType_t xConstTickCount = xTickCount + ( TickType_t ) 1;
/* Increment the RTOS tick, switching the delayed and overflowed delayed lists if it wraps to 0. */
xTickCount = xConstTickCount;
if( xConstTickCount == ( TickType_t ) 0U ) /*lint !e774 'if' does not always evaluate to false as it is looking for an overflow. */
{
taskSWITCH_DELAYED_LISTS();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* See if this tick has made a timeout expire. Tasks are stored in the queue in the order of their wake time - meaning once one task has been found whose block time has not expired there is no need to look any further down the list. */
if( xConstTickCount >= xNextTaskUnblockTime )
{
for( ;; )
{
if( listLIST_IS_EMPTY( pxDelayedTaskList ) != pdFALSE )
{
/* The delayed list is empty. Set xNextTaskUnblockTime to the maximum possible value so it is extremely unlikely that the if( xTickCount >= xNextTaskUnblockTime ) test will pass next time through. */
xNextTaskUnblockTime = portMAX_DELAY; /*lint !e961 MISRA exception as the casts are only redundant for some ports. */
break;
}
else
{
/* The delayed list is not empty, get the value of the item at the head of the delayed list. This is the time at which the task at the head of the delayed list must be removed from the Blocked state. */
pxTCB = listGET_OWNER_OF_HEAD_ENTRY( pxDelayedTaskList ); /*lint !e9079 void * is used as this macro is used with timers and co-routines too. Alignment is known to be fine as the type of the pointer stored and retrieved is the same. */
xItemValue = listGET_LIST_ITEM_VALUE( &( pxTCB->xStateListItem ) );
if( xConstTickCount < xItemValue )
{
/* It is not time to unblock this item yet, but the item value is the time at which the task at the head of the blocked list must be removed from the Blocked state - so record the item value in xNextTaskUnblockTime. */
xNextTaskUnblockTime = xItemValue;
break; /*lint !e9011 Code structure here is deedmed easier to understand with multiple breaks. */
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* It is time to remove the item from the Blocked state. */
( void ) uxListRemove( &( pxTCB->xStateListItem ) );
/* Is the task waiting on an event also? If so remove it from the event list. */
if( listLIST_ITEM_CONTAINER( &( pxTCB->xEventListItem ) ) != NULL )
{
( void ) uxListRemove( &( pxTCB->xEventListItem ) );
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* Place the unblocked task into the appropriate ready list. */
prvAddTaskToReadyList( pxTCB );
/* A task being unblocked cannot cause an immediate context switch if preemption is turned off. */
#if ( configUSE_PREEMPTION == 1 )
{
/* Preemption is on, but a context switch should only be performed if the unblocked task has a priority that is equal to or higher than the currently executing task. */
if( pxTCB->uxPriority >= pxCurrentTCB->uxPriority )
{
xSwitchRequired = pdTRUE;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif /* configUSE_PREEMPTION */
}
}
}
/* Tasks of equal priority to the currently running task will share processing time (time slice) if preemption is on, and the application writer has not explicitly turned time slicing off. */
#if ( ( configUSE_PREEMPTION == 1 ) && ( configUSE_TIME_SLICING == 1 ) )
{
if( listCURRENT_LIST_LENGTH( &( pxReadyTasksLists[ pxCurrentTCB->uxPriority ] ) ) > ( UBaseType_t ) 1 )
{
xSwitchRequired = pdTRUE;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif /* ( ( configUSE_PREEMPTION == 1 ) && ( configUSE_TIME_SLICING == 1 ) ) */
#if ( configUSE_TICK_HOOK == 1 )
{
/* Guard against the tick hook being called when the pended tick count is being unwound (when the scheduler is being unlocked). */
if( uxPendedTicks == ( UBaseType_t ) 0U )
{
vApplicationTickHook();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif /* configUSE_TICK_HOOK */
}
else
{
++uxPendedTicks;
/* The tick hook gets called at regular intervals, even if the scheduler is locked. */
#if ( configUSE_TICK_HOOK == 1 )
{
vApplicationTickHook();
}
#endif
}
#if ( configUSE_PREEMPTION == 1 )
{
if( xYieldPending != pdFALSE )
{
xSwitchRequired = pdTRUE;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif /* configUSE_PREEMPTION */
return xSwitchRequired;
}