FreeRtos學(xué)習(xí)筆記（11）查找就緒任務(wù)中優(yōu)先級(jí)最高任務(wù)原理刨析

怎么查找就緒任務(wù)中優(yōu)先級(jí)最高的？

tasks.c中聲明了一個(gè)全局變量 uxTopReadyPriority，任務(wù)從其他狀態(tài)進(jìn)入就緒態(tài)時(shí)，需要修改 uxTopReadyPriority，將就緒任務(wù)優(yōu)先級(jí)信息保存在 uxTopReadyPriority 中。在FreeRtos進(jìn)行剪裁時(shí)，如果最大任務(wù)優(yōu)先級(jí) configMAX_PRIORITIES 不超過(guò)32，則任務(wù)就緒時(shí)會(huì)將 uxTopReadyPriority 中任務(wù)優(yōu)先級(jí)對(duì)應(yīng)的位置一（例如有一個(gè)優(yōu)先級(jí)為5的任務(wù)從堵塞態(tài)變?yōu)榫途w態(tài)，則將uxTopReadyPriority |= 1 << 5）。

然后在任務(wù)進(jìn)行切換時(shí)，根據(jù) uxTopReadyPriority 變量的值，找到就緒任務(wù)中優(yōu)先級(jí)最高的

這里用到的cortex-M特有的匯編指令 clz – 計(jì)算前導(dǎo)零指令

比如： 一個(gè) 32 位的變量 uxTopReadyPriority， 其位 0、
位 24 和位 25 均置 1 ， 其余位為 0 ， 那么使用前導(dǎo)零指令 __CLZ
(uxTopReadyPriority)可以很快的計(jì)算出 uxTopReadyPriority 的前導(dǎo)零的個(gè)數(shù)為 6。

使用前導(dǎo)零指令 __CLZ 來(lái)查找就緒任務(wù)中優(yōu)先級(jí)最高的 顯然是方便快捷的，但是當(dāng)遇到 最大任務(wù)優(yōu)先級(jí) configMAX_PRIORITIES 超過(guò)32 或者沒(méi)有前導(dǎo)零指令__CLZ的內(nèi)核時(shí)，需要在Free RTOSConfig.h中添加宏定義

#define configUSE_PORT_OPTIMISED_TASK_SELECTION 0

使用一種更通用的方法去查找就緒任務(wù)中優(yōu)先級(jí)最高的。

鏈表操作

FreeRtos中有任務(wù)就緒表，任務(wù)堵塞表，任務(wù)掛起表等鏈表，鏈表操作貫穿FreeRtos整個(gè)底層，有必要了解一下FreeRtos的鏈表操作。這里只是大致介紹，具體代碼細(xì)節(jié)可以參考野火的《FreeRTOS 內(nèi)核實(shí)現(xiàn)與應(yīng)用開(kāi)發(fā)實(shí)戰(zhàn)指南》

鏈表初始化

list.h中有一下三個(gè)結(jié)構(gòu)體，鏈表節(jié)點(diǎn)xLIST_ITEM、鏈表最小節(jié)點(diǎn)xMINI_LIST_ITEM、鏈表頭節(jié)點(diǎn)xLIST。

/** 鏈表節(jié)點(diǎn)*/ 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; /*< 節(jié)點(diǎn)中的值，一般排序插入時(shí)需要使用 */struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*< 指向下一個(gè)節(jié)點(diǎn) */struct xLIST_ITEM * configLIST_VOLATILE pxPrevious; /*< 指向上一個(gè)結(jié)點(diǎn) */void * pvOwner; /*< 指向該節(jié)點(diǎn)的任務(wù)控制塊 */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; /*< 節(jié)點(diǎn)中的值，一般排序插入時(shí)需要使用 */struct xLIST_ITEM * configLIST_VOLATILE pxNext; /*< 指向下一個(gè)節(jié)點(diǎn) */struct xLIST_ITEM * configLIST_VOLATILE pxPrevious;/*< 指向上一個(gè)結(jié)點(diǎn) */ }; typedef struct xMINI_LIST_ITEM MiniListItem_t;/** 頭節(jié)點(diǎn)*/ 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; /*< 該鏈表中節(jié)點(diǎn)個(gè)數(shù) */ListItem_t * configLIST_VOLATILE pxIndex; /*< 指向鏈表第一個(gè)節(jié)點(diǎn) */MiniListItem_t xListEnd; /*< 指向固定的鏈表結(jié)束節(jié)點(diǎn) */listSECOND_LIST_INTEGRITY_CHECK_VALUE /*< Set to a known value if configUSE_LIST_DATA_INTEGRITY_CHECK_BYTES is set to 1. */ } List_t;

鏈表初始化其實(shí)就做了上圖的幾個(gè)箭頭工作，將對(duì)應(yīng)指針指向xListEnd尾節(jié)點(diǎn)，具體代碼如下

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 ); }

鏈表節(jié)點(diǎn)尾插入到鏈表尾部

如下圖所示，xLIST_ITEM 1、xLIST_ITEM 2、xLIST_ITEM 3、xListEnd這四個(gè)節(jié)點(diǎn)構(gòu)成了一個(gè)雙向循環(huán)鏈表。

這里需要注意的是，xLIST的pxIndex項(xiàng)指向的節(jié)點(diǎn)為第一個(gè)節(jié)點(diǎn)，因此 vListInsertEnd 函數(shù)會(huì)將節(jié)點(diǎn)插入到 pxIndex指向的節(jié)點(diǎn)的前面,并不是插入到 xListEnd 的后面，pxIndex會(huì)不斷移動(dòng)，因此第一個(gè)節(jié)點(diǎn)不是固定的。

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 )++; }

按值排序并插入鏈表節(jié)點(diǎn)

上面說(shuō)了插入到列表末尾但是并不是插入到 xListEnd 后面，那 xListEnd 有什么作用？

xListEnd 可以看作是一個(gè)特殊節(jié)點(diǎn)，節(jié)點(diǎn)內(nèi)部的值 xItemValue 最大，方便按值排序并插入鏈表節(jié)點(diǎn)（從xListEnd開(kāi)始遍歷）

刪除鏈表節(jié)點(diǎn)

就是將當(dāng)前節(jié)點(diǎn)從對(duì)應(yīng)鏈表移除。

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; }

任務(wù)就緒表

FreeRtos為了支持時(shí)間片調(diào)度（不同任務(wù)可以擁有相同的任務(wù)優(yōu)先級(jí)），為每個(gè)任務(wù)優(yōu)先級(jí)都建立了一個(gè)環(huán)形鏈表。因此優(yōu)先級(jí)在夠用的情況下盡量少。

每個(gè)優(yōu)先級(jí)都有一個(gè)頭結(jié)點(diǎn)

當(dāng)任務(wù)從其他狀態(tài)轉(zhuǎn)為就緒態(tài)時(shí)，會(huì)調(diào)用 prvAddTaskToReadyList 宏對(duì) uxTopReadyPriority 進(jìn)行修改

然后將任務(wù)控制塊中的 xStateListItem 掛在對(duì)應(yīng)優(yōu)先級(jí)的頭結(jié)點(diǎn)下。

同樣，在任務(wù)從就緒態(tài)轉(zhuǎn)為其他狀態(tài)時(shí)，會(huì)將任務(wù)控制塊中的 xStateListItem 從對(duì)應(yīng)就緒列表移除。

這里需要注意一點(diǎn)：在禁止調(diào)度任務(wù)期間，若ISR導(dǎo)致了一個(gè)任務(wù)的就緒，這個(gè)任務(wù)就會(huì)放到xPendingReadyList中而不是直接加入就緒列表。

為什么不直接加入就緒列表 而要用 xPendingReadyList 做個(gè)緩沖？
任務(wù)A轉(zhuǎn)為就緒態(tài)時(shí)，會(huì)將任務(wù)A的優(yōu)先級(jí)和當(dāng)前任務(wù)優(yōu)先級(jí)做比較，如果任務(wù)A優(yōu)先級(jí)高，則會(huì)立即觸發(fā)PendSV中斷進(jìn)行任務(wù)切換。

但是如果此時(shí)調(diào)度器是掛起狀態(tài)，則不會(huì)進(jìn)行任務(wù)切換

這里使用 xPendingReadyList 做了緩沖，假設(shè)任務(wù)A優(yōu)先級(jí)比當(dāng)前任務(wù)優(yōu)先級(jí)高，在禁止調(diào)度任務(wù)期間，ISR導(dǎo)致了任務(wù)A就緒，任務(wù)A就會(huì)放到xPendingReadyList中，當(dāng)任務(wù)調(diào)度器解掛，則會(huì)將 xPendingReadyList 中的任務(wù)A轉(zhuǎn)移到對(duì)應(yīng)就緒表，由于任務(wù)A優(yōu)先級(jí)比當(dāng)前任務(wù)優(yōu)先級(jí)高，則進(jìn)行任務(wù)切換。如果不使用 xPendingReadyList 則在調(diào)度器解掛后不會(huì)判斷任務(wù)A和當(dāng)前任務(wù)的優(yōu)先級(jí)，任務(wù)A也就不會(huì)及時(shí)運(yùn)行。

任務(wù)堵塞表

FreeRtos中和堵塞表相關(guān)的有下面四個(gè)變量

為什么有兩個(gè)堵塞表？
32位內(nèi)核的單片機(jī)中，FreeRtos的時(shí)間節(jié)拍類型為 uint32_t，當(dāng)時(shí)間過(guò)長(zhǎng)時(shí)就會(huì)有溢出風(fēng)險(xiǎn)。

在任務(wù)轉(zhuǎn)為堵塞態(tài)時(shí)，會(huì)判斷當(dāng)前系統(tǒng)時(shí)間節(jié)拍數(shù)+任務(wù)堵塞節(jié)拍數(shù)是否溢出？如果溢出就將該任務(wù)掛在溢出堵塞表中，如果不溢出就掛在堵塞表中。

當(dāng)系統(tǒng)時(shí)間節(jié)拍要溢出時(shí)，會(huì)將溢出堵塞表和堵塞表互換。

任務(wù)掛起表

理解了任務(wù)就緒表和堵塞表后，掛起表就比較簡(jiǎn)單了。當(dāng)任務(wù)掛起時(shí)，會(huì)將該任務(wù)掛到掛起表中。

更新任務(wù)流程

調(diào)用 vTaskStartScheduler() 啟動(dòng)調(diào)度器后，會(huì)觸發(fā)SCV中斷，在SCV中斷服務(wù)函數(shù)中將堆棧指針寄存器從MSP切換成PSP，并且啟動(dòng)第一個(gè)任務(wù)。

除了任務(wù)中的堵塞、掛起、手動(dòng)切換任務(wù)操作，任務(wù)之間的切換主要發(fā)生在時(shí)鐘節(jié)拍中斷服務(wù)函數(shù)中

BaseType_t xTaskIncrementTick( void ) {TCB_t * pxTCB;TickType_t xItemValue;BaseType_t xSwitchRequired = pdFALSE;/* 調(diào)度器沒(méi)有掛起 */if( uxSchedulerSuspended == ( UBaseType_t ) pdFALSE ){const TickType_t xConstTickCount = xTickCount + ( TickType_t ) 1;/* 時(shí)鐘節(jié)拍自增 */xTickCount = xConstTickCount;if( xConstTickCount == ( TickType_t ) 0U ) {/* 時(shí)鐘節(jié)拍溢出 溢出堵塞表和堵塞表互換 */taskSWITCH_DELAYED_LISTS();}else{mtCOVERAGE_TEST_MARKER();}/* 當(dāng)前時(shí)鐘節(jié)拍大于等于堵塞列表中第一個(gè)節(jié)點(diǎn)堵塞時(shí)間. */if( xConstTickCount >= xNextTaskUnblockTime ){for( ; ; ){if( listLIST_IS_EMPTY( pxDelayedTaskList ) != pdFALSE ){/* 堵塞列表為空 退出 */xNextTaskUnblockTime = portMAX_DELAY; break;}else{/* 拿出堵塞列表中第一個(gè)節(jié)點(diǎn)任務(wù)控制塊 */pxTCB = listGET_OWNER_OF_HEAD_ENTRY( pxDelayedTaskList ); /* 獲取該任務(wù)解除堵塞的時(shí)間節(jié)拍 */xItemValue = listGET_LIST_ITEM_VALUE( &( pxTCB->xStateListItem ) );if( xConstTickCount < xItemValue ){/* 該任務(wù)還未到解除堵塞的時(shí)間節(jié)拍 退出 */xNextTaskUnblockTime = xItemValue;break; }else{mtCOVERAGE_TEST_MARKER();}/* 將該任務(wù)從堵塞列表刪除 */( void ) uxListRemove( &( pxTCB->xStateListItem ) );/* 如果該任務(wù)也在等信號(hào)到來(lái)，將該任務(wù)從事件列表移除. 例如如果一個(gè)任務(wù)因?yàn)榈却盘?hào)量到來(lái)進(jìn)入堵塞列表，等待信號(hào)量到來(lái)的最大時(shí)間為100個(gè)時(shí)鐘節(jié)拍，則該任務(wù)控制塊會(huì)利用 xStateListItem 將任務(wù)控制塊掛在堵塞列表，利用 xEventListItem 將任務(wù)控制塊掛在事件列表。 */if( listLIST_ITEM_CONTAINER( &( pxTCB->xEventListItem ) ) != NULL ){( void ) uxListRemove( &( pxTCB->xEventListItem ) );}else{mtCOVERAGE_TEST_MARKER();}/* 添加到對(duì)應(yīng)的就緒列表 */prvAddTaskToReadyList( pxTCB );#if ( configUSE_PREEMPTION == 1 ){/* 如果該任務(wù)優(yōu)先級(jí)比當(dāng)前任務(wù)優(yōu)先級(jí)高，任務(wù)切換標(biāo)志位置1 */if( pxTCB->uxPriority >= pxCurrentTCB->uxPriority ){xSwitchRequired = pdTRUE;}else{mtCOVERAGE_TEST_MARKER();}}#endif /* configUSE_PREEMPTION */}}}/* 如果開(kāi)啟 支持時(shí)間片調(diào)度 功能， 當(dāng)前任務(wù)優(yōu)先級(jí)就緒列表中如果有多個(gè)任務(wù)，任務(wù)切換標(biāo)志位置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 ){/* 節(jié)拍鉤子函數(shù) */if( xPendedTicks == ( TickType_t ) 0 ){vApplicationTickHook();}else{mtCOVERAGE_TEST_MARKER();}}#endif /* configUSE_TICK_HOOK */#if ( configUSE_PREEMPTION == 1 ){/* 如果中斷服務(wù)函數(shù)中有任務(wù)從掛起進(jìn)入就緒態(tài) xYieldPending 會(huì)置1，任務(wù)切換標(biāo)志位 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() 函數(shù)中分析是否需要進(jìn)行任務(wù)切換，如果需要任務(wù)切換則觸發(fā)PendSV中斷

在PendSV中斷服務(wù)函數(shù)中進(jìn)行任務(wù)切換

void vTaskSwitchContext( void ) {if( uxSchedulerSuspended != ( UBaseType_t ) pdFALSE ){/* 調(diào)度器掛起 */xYieldPending = pdTRUE;}else{xYieldPending = pdFALSE;traceTASK_SWITCHED_OUT();#if ( configGENERATE_RUN_TIME_STATS == 1 ){#ifdef portALT_GET_RUN_TIME_COUNTER_VALUEportALT_GET_RUN_TIME_COUNTER_VALUE( ulTotalRunTime );#elseulTotalRunTime = portGET_RUN_TIME_COUNTER_VALUE();#endif/* 各個(gè)任務(wù)CPU使用率統(tǒng)計(jì) 可以參考筆記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/* 找到優(yōu)先級(jí)最高的就緒列表，并切換任務(wù)控制塊. */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 */} }

其中任務(wù)切換的核心就是 taskSELECT_HIGHEST_PRIORITY_TASK();

總結(jié)

以上是生活随笔為你收集整理的FreeRtos学习笔记（11）查找就绪任务中优先级最高任务原理刨析的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。