FreeRtos學習筆記（11）查找就緒任務中優先級最高任務原理刨析
怎么查找就緒任務中優先級最高的？
tasks.c中宣告了一個全域變數 uxTopReadyPriority，任務從其他狀態進入就緒態時，需要修改 uxTopReadyPriority，將就緒任務優先級資訊保存在 uxTopReadyPriority 中，在FreeRtos進行剪裁時，如果最大任務優先級 configMAX_PRIORITIES 不超過32，則任務就緒時會將 uxTopReadyPriority 中任務優先級對應的位置一（例如有一個優先級為5的任務從堵塞態變為就緒態，則將uxTopReadyPriority |= 1 << 5），
然后在任務進行切換時，根據 uxTopReadyPriority 變數的值，找到就緒任務中優先級最高的
這里用到的cortex-M特有的匯編指令 clz – 計算前導零指令
比如： 一個 32 位的變數 uxTopReadyPriority， 其位 0、
位 24 和位 25 均置 1 ， 其余位為 0 ， 那么使用前導零指令 __CLZ
(uxTopReadyPriority)可以很快的計算出 uxTopReadyPriority 的前導零的個數為 6，
使用前導零指令 __CLZ 來查找就緒任務中優先級最高的 顯然是方便快捷的，但是當遇到 最大任務優先級 configMAX_PRIORITIES 超過32 或者沒有前導零指令__CLZ的內核時，需要在Free RTOSConfig.h中添加宏定義
#define configUSE_PORT_OPTIMISED_TASK_SELECTION 0
使用一種更通用的方法去查找就緒任務中優先級最高的，
鏈表操作
FreeRtos中有任務就緒表，任務堵塞表，任務掛起表等鏈表，鏈表操作貫穿FreeRtos整個底層，有必要了解一下FreeRtos的鏈表操作，這里只是大致介紹，具體代碼細節可以參考野火的《FreeRTOS 內核實作與應用開發實戰指南》
鏈表初始化
list.h中有一下三個結構體，鏈表節點xLIST_ITEM、鏈表最小節點xMINI_LIST_ITEM、鏈表頭節點xLIST，
/*
* 鏈表節點
*/
struct xLIST;
struct xLIST_ITEM
{
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
configLIST_VOLATILE TickType_t xItemValue; /*< 節點中的值，一般排序插入時需要使用 */
struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*< 指向下一個節點 */
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*< 指向上一個結點 */
void * pvOwner; /*< 指向該節點的任務控制塊 */
struct xLIST * configLIST_VOLATILE pxContainer; /*< 指向表頭 */
listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
};
typedef struct xLIST_ITEM ListItem_t; /* For some reason lint wants this as two separate definitions. */
struct xMINI_LIST_ITEM
{
listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
configLIST_VOLATILE TickType_t xItemValue; /*< 節點中的值，一般排序插入時需要使用 */
struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*< 指向下一個節點 */
struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;/*< 指向上一個結點 */
};
typedef struct xMINI_LIST_ITEM MiniListItem_t;
/*
* 頭節點
*/
typedef struct xLIST
{
listFIRST_LIST_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
volatile UBaseType_t uxNumberOfItems; /*< 該鏈表中節點個數 */
ListItem_t * configLIST_VOLATILE pxIndex; /*< 指向鏈表第一個節點 */
MiniListItem_t xListEnd; /*< 指向固定的鏈表結束節點 */
listSECOND_LIST_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
} List_t;
鏈表初始化其實就做了上圖的幾個箭頭作業，將對應指標指向xListEnd尾節點，具體代碼如下
void vListInitialise( List_t * const pxList )
{
/* The list structure contains a list item which is used to mark the
* end of the list. To initialise the list the list end is inserted
* as the only list entry. */
pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
/* The list end value is the highest possible value in the list to
* ensure it remains at the end of the list. */
pxList->xListEnd.xItemValue = portMAX_DELAY;
/* The list end next and previous pointers point to itself so we know
* when the list is empty. */
pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd ); /*lint !e826 !e740 !e9087 The mini list structure is used as the list end to save RAM. This is checked and valid. */
pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
/* Write known values into the list if
* configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */
listSET_LIST_INTEGRITY_CHECK_1_VALUE( pxList );
listSET_LIST_INTEGRITY_CHECK_2_VALUE( pxList );
}
鏈表節點尾插入到鏈表尾部
如下圖所示，xLIST_ITEM 1、xLIST_ITEM 2、xLIST_ITEM 3、xListEnd這四個節點構成了一個雙向回圈鏈表，
這里需要注意的是，xLIST的pxIndex項指向的節點為第一個節點，因此 vListInsertEnd 函式會將節點插入到 pxIndex指向的節點的前面,并不是插入到 xListEnd 的后面，pxIndex會不斷移動，因此第一個節點不是固定的，
void vListInsertEnd( List_t * const pxList,
ListItem_t * const pxNewListItem )
{
ListItem_t * const pxIndex = pxList->pxIndex;
/* Only effective when configASSERT() is also defined, these tests may catch
* the list data structures being overwritten in memory. They will not catch
* data errors caused by incorrect configuration or use of FreeRTOS. */
listTEST_LIST_INTEGRITY( pxList );
listTEST_LIST_ITEM_INTEGRITY( pxNewListItem );
/* Insert a new list item into pxList, but rather than sort the list,
* makes the new list item the last item to be removed by a call to
* listGET_OWNER_OF_NEXT_ENTRY(). */
pxNewListItem->pxNext = pxIndex;
pxNewListItem->pxPrevious = pxIndex->pxPrevious;
/* Only used during decision coverage testing. */
mtCOVERAGE_TEST_DELAY();
pxIndex->pxPrevious->pxNext = pxNewListItem;
pxIndex->pxPrevious = pxNewListItem;
/* Remember which list the item is in. */
pxNewListItem->pxContainer = pxList;
( pxList->uxNumberOfItems )++;
}
按值排序并插入鏈表節點
上面說了插入到串列末尾但是并不是插入到 xListEnd 后面，那 xListEnd 有什么作用？
xListEnd 可以看作是一個特殊節點，節點內部的值 xItemValue 最大，方便按值排序并插入鏈表節點（從xListEnd開始遍歷）
洗掉鏈表節點
就是將當前節點從對應鏈表移除，
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )
{
/* The list item knows which list it is in. Obtain the list from the list
* item. */
List_t * const pxList = pxItemToRemove->pxContainer;
pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
/* Only used during decision coverage testing. */
mtCOVERAGE_TEST_DELAY();
/* Make sure the index is left pointing to a valid item. */
if( pxList->pxIndex == pxItemToRemove )
{
pxList->pxIndex = pxItemToRemove->pxPrevious;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
pxItemToRemove->pxContainer = NULL;
( pxList->uxNumberOfItems )--;
return pxList->uxNumberOfItems;
}
任務就緒表
FreeRtos為了支持時間片調度（不同任務可以擁有相同的任務優先級），為每個任務優先級都建立了一個環形鏈表，因此優先級在夠用的情況下盡量少，
每個優先級都有一個頭結點
當任務從其他狀態轉為就緒態時，會呼叫 prvAddTaskToReadyList 宏對 uxTopReadyPriority 進行修改
然后將任務控制塊中的 xStateListItem 掛在對應優先級的頭結點下，
同樣，在任務從就緒態轉為其他狀態時，會將任務控制塊中的 xStateListItem 從對應就緒串列移除，
這里需要注意一點：在禁止調度任務期間，若ISR導致了一個任務的就緒，這個任務就會放到xPendingReadyList中而不是直接加入就緒串列，
為什么不直接加入就緒串列 而要用 xPendingReadyList 做個緩沖？
任務A轉為就緒態時，會將任務A的優先級和當前任務優先級做比較，如果任務A優先級高，則會立即觸發PendSV中斷進行任務切換，
但是如果此時調度器是掛起狀態，則不會進行任務切換
這里使用 xPendingReadyList 做了緩沖，假設任務A優先級比當前任務優先級高，在禁止調度任務期間，ISR導致了任務A就緒，任務A就會放到xPendingReadyList中，當任務調度器解掛，則會將 xPendingReadyList 中的任務A轉移到對應就緒表，由于任務A優先級比當前任務優先級高，則進行任務切換，如果不使用 xPendingReadyList 則在調度器解掛后不會判斷任務A和當前任務的優先級，任務A也就不會及時運行，
任務堵塞表
FreeRtos中和堵塞表相關的有下面四個變數
為什么有兩個堵塞表？
32位內核的單片機中，FreeRtos的時間節拍型別為 uint32_t，當時間過長時就會有溢位風險，
在任務轉為堵塞態時，會判斷當前系統時間節拍數+任務堵塞節拍數是否溢位？如果溢位就將該任務掛在溢位堵塞表中，如果不溢位就掛在堵塞表中，
當系統時間節拍要溢位時，會將溢位堵塞表和堵塞表互換，
任務掛起表
理解了任務就緒表和堵塞表后，掛起表就比較簡單了，當任務掛起時，會將該任務掛到掛起表中，
更新任務流程
呼叫 vTaskStartScheduler() 啟動調度器后，會觸發SCV中斷，在SCV中斷服務函式中將堆疊指標暫存器從MSP切換成PSP，并且啟動第一個任務，
除了任務中的堵塞、掛起、手動切換任務操作，任務之間的切換主要發生在時鐘節拍中斷服務函式中
BaseType_t xTaskIncrementTick( void )
{
TCB_t * pxTCB;
TickType_t xItemValue;
BaseType_t xSwitchRequired = pdFALSE;
/* 調度器沒有掛起 */
if( uxSchedulerSuspended == ( UBaseType_t ) pdFALSE )
{
const TickType_t xConstTickCount = xTickCount + ( TickType_t ) 1;
/* 時鐘節拍自增 */
xTickCount = xConstTickCount;
if( xConstTickCount == ( TickType_t ) 0U )
{
/* 時鐘節拍溢位 溢位堵塞表和堵塞表互換 */
taskSWITCH_DELAYED_LISTS();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* 當前時鐘節拍大于等于堵塞串列中第一個節點堵塞時間. */
if( xConstTickCount >= xNextTaskUnblockTime )
{
for( ; ; )
{
if( listLIST_IS_EMPTY( pxDelayedTaskList ) != pdFALSE )
{
/* 堵塞串列為空 退出 */
xNextTaskUnblockTime = portMAX_DELAY;
break;
}
else
{
/* 拿出堵塞串列中第一個節點任務控制塊 */
pxTCB = listGET_OWNER_OF_HEAD_ENTRY( pxDelayedTaskList );
/* 獲取該任務解除堵塞的時間節拍 */
xItemValue = listGET_LIST_ITEM_VALUE( &( pxTCB->xStateListItem ) );
if( xConstTickCount < xItemValue )
{
/* 該任務還未到解除堵塞的時間節拍 退出 */
xNextTaskUnblockTime = xItemValue;
break;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* 將該任務從堵塞串列洗掉 */
( void ) uxListRemove( &( pxTCB->xStateListItem ) );
/* 如果該任務也在等信號到來，將該任務從事件串列移除. 例如如果一個任務因為等待信號量到來進入堵塞串列，等待信號量到來的最大時間為100個時鐘節拍，則該任務控制塊會利用 xStateListItem 將任務控制塊掛在堵塞串列，利用 xEventListItem 將任務控制塊掛在事件串列， */
if( listLIST_ITEM_CONTAINER( &( pxTCB->xEventListItem ) ) != NULL )
{
( void ) uxListRemove( &( pxTCB->xEventListItem ) );
}
else
{
mtCOVERAGE_TEST_MARKER();
}
/* 添加到對應的就緒串列 */
prvAddTaskToReadyList( pxTCB );
#if ( configUSE_PREEMPTION == 1 )
{
/* 如果該任務優先級比當前任務優先級高，任務切換標志位置1 */
if( pxTCB->uxPriority >= pxCurrentTCB->uxPriority )
{
xSwitchRequired = pdTRUE;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif /* configUSE_PREEMPTION */
}
}
}
/* 如果開啟 支持時間片調度 功能， 當前任務優先級就緒串列中如果有多個任務，任務切換標志位置1 */
#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 )
{
/* 節拍鉤子函式 */
if( xPendedTicks == ( TickType_t ) 0 )
{
vApplicationTickHook();
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif /* configUSE_TICK_HOOK */
#if ( configUSE_PREEMPTION == 1 )
{
/* 如果中斷服務函式中有任務從掛起進入就緒態 xYieldPending 會置1，任務切換標志位 xSwitchRequired 置1 */
if( xYieldPending != pdFALSE )
{
xSwitchRequired = pdTRUE;
}
else
{
mtCOVERAGE_TEST_MARKER();
}
}
#endif /* configUSE_PREEMPTION */
}
else
{
++xPendedTicks;
/* The tick hook gets called at regular intervals, even if the
* scheduler is locked. */
#if ( configUSE_TICK_HOOK == 1 )
{
vApplicationTickHook();
}
#endif
}
return xSwitchRequired;
}
在 xTaskIncrementTick() 函式中分析是否需要進行任務切換，如果需要任務切換則觸發PendSV中斷
在PendSV中斷服務函式中進行任務切換
void vTaskSwitchContext( void )
{
if( uxSchedulerSuspended != ( UBaseType_t ) pdFALSE )
{
/* 調度器掛起 */
xYieldPending = pdTRUE;
}
else
{
xYieldPending = pdFALSE;
traceTASK_SWITCHED_OUT();
#if ( configGENERATE_RUN_TIME_STATS == 1 )
{
#ifdef portALT_GET_RUN_TIME_COUNTER_VALUE
portALT_GET_RUN_TIME_COUNTER_VALUE( ulTotalRunTime );
#else
ulTotalRunTime = portGET_RUN_TIME_COUNTER_VALUE();
#endif
/* 各個任務CPU使用率統計 可以參考筆記9 */
if( ulTotalRunTime > ulTaskSwitchedInTime )
{
pxCurrentTCB->ulRunTimeCounter += ( ulTotalRunTime - ulTaskSwitchedInTime );
}
else
{
mtCOVERAGE_TEST_MARKER();
}
ulTaskSwitchedInTime = ulTotalRunTime;
}
#endif /* configGENERATE_RUN_TIME_STATS */
/* 堆疊溢位檢查. */
taskCHECK_FOR_STACK_OVERFLOW();
/* Before the currently running task is switched out, save its errno. */
#if ( configUSE_POSIX_ERRNO == 1 )
{
pxCurrentTCB->iTaskErrno = FreeRTOS_errno;
}
#endif
/* 找到優先級最高的就緒串列，并切換任務控制塊. */
taskSELECT_HIGHEST_PRIORITY_TASK();
/* After the new task is switched in, update the global errno. */
#if ( configUSE_POSIX_ERRNO == 1 )
{
FreeRTOS_errno = pxCurrentTCB->iTaskErrno;
}
#endif
#if ( configUSE_NEWLIB_REENTRANT == 1 )
{
/* Switch Newlib's _impure_ptr variable to point to the _reent
* structure specific to this task.
* See the third party link http://www.nadler.com/embedded/newlibAndFreeRTOS.html
* for additional information. */
_impure_ptr = &( pxCurrentTCB->xNewLib_reent );
}
#endif /* configUSE_NEWLIB_REENTRANT */
}
}
其中任務切換的核心就是 taskSELECT_HIGHEST_PRIORITY_TASK();
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/347207.html
標籤：其他
上一篇：關于本人學習JAVA的方法