1.等待表用途
在多任務系統中經常會有部分任務在運行到某個節點時需要延時等待一段時間，等待表的作用就是幫助作業系統內核管理需要延時等待的任務，
當運行的任務需要延時等待，此時作業系統內核會將該任務從就緒表中移動到等待表中；當完成延時等待時間后，作業系統內核會將該任務從等待表中移動到就緒表中，狀態圖如下：
例如現在需要連續讀取一個溫濕度傳感頭的資料，但是該溫度傳感器在啟動一次測量到輸出一個穩定數值需要等待50ms，這種情況我們有兩種策略：
1、啟動測量后死等50ms，然后讀取測量值，
2、啟動測量后，運行其他任務，50ms后再來讀取溫濕度測量值，
這兩種策略的運行狀態如下圖：
很顯然需要延時等待時去執行其他任務的這種策略的CPU利用率更高，作業系統內核就時利用等待表實作這種策略，
2.等待策略
要完成等待很多種策略，常見的策略有以下兩種：
1、倒計時法
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.等待表優化
1、排序鏈表法
前文提出了一種利用鏈表的方式構建的等待表，根據時間構建鏈表，時間小的放在鏈表頭部，時間大的放在鏈表尾部，每次更新時間只有檢查第一個物件即可，因為第一個物件是時間最小的（與當前時間間隔最小），
這種方式操作簡單，但是有一個問題：當任務很多時，插入和移除一個新任務的時間開銷會非常大，比如現在有100個任務，假設現在新插入一個任務，該新插入的任務延時時間最大，因此該任務需要執行100次比較之和100次讀取下一個任務的操作才能完成插入操作，
2、 時間取模分表
先用一個實體解釋時間取模分表法：
假設現在有一個靠近火車站的旅店，客戶進旅店休息并申請一個叫醒業務，旅店到時間后提供服務員上面叫醒服務，假設叫醒業務是以分為單位，由于來的客戶的時間是亂序的，不同的客戶等待的時間也是亂序的，這里如果制作一個普通的叫醒表，每次更新一分鐘，服務員要核對以下所有客戶的定時時間，這樣費時也容易出錯，
因此我們用時間取模分表法制作一個特殊的表：
時間是當前時間的分時間的個位，如12點37分對應的時間為7 ，8點15分對應的時間為5，客戶資訊中包含鬧鐘時間和房號，客戶資訊中按照時間由近及遠的方式排列，
加入客戶后的叫醒表如下：
這時候服務員只用檢查當前時間的分時間的個位，然后再判斷對應表項的第一個客戶的時間是否到了即可，整個程序只用判斷2次既可，
例如：當前時間為8點05分，服務員只有判斷表中時間為5的那列，然后檢查第一個，結果是沒有客戶需要喚醒，
例如：當前時間為9點02分，服務員只有判斷表中時間為2的那列，然后檢查第一個，結果是沒有客戶需要喚醒，
例如：當前時間為11點19分，服務員只有判斷表中時間為9的那列，然后檢查第一個，結果是有客戶需要喚醒，
這種策略執行效率較高，并且插入和移除一個新任務的時間開銷比較小，
5.FreeRTOS原始碼分析
FreeRTOS的等待表定義如下：
FreeRTOS的等待表使用的是排序鏈表法，
等待表的3種操作方法：
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的作用是當前任務需要延時等待一定時間,該系統函式的呼叫流程如下：
vTaskDelay ->
prvAddCurrentTaskToDelayedList->
vListInsert( pxDelayedTaskList, &( pxCurrentTCB->xStateListItem ) )
等待表變化：將當前任務從就緒表中移除，然后將當前任務插入等待表中，對應的優先級位清0，（清0操作會判斷該優先級下的就緒任務總數量）
vTaskDelayUntil
vTaskDelayUntil的作用是當前任務需要延時等待一定時間,該系統函式的呼叫流程如下：
vTaskDelayUntil->
prvAddCurrentTaskToDelayedList->
vListInsert( pxDelayedTaskList, &( pxCurrentTCB->xStateListItem ) )
等待表變化：將當前任務從就緒表中移除，然后將當前任務插入等待表中，對應的優先級位清0，（清0操作會判斷該優先級下的就緒任務總數量）
XPortSysTickHandler
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;
}
未完待續…
實時作業系統系列將持續更新
創作不易希望朋友們點贊，轉發，評論，關注，
您的點贊，轉發，評論，關注將是我持續更新的動力
作者：李巍
Github：liyinuoman2017
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/393921.html
標籤：其他
上一篇：計算機組成原理（復習）