3.5. 列表

任務(wù)之后，最常用的FreeRTOS數(shù)據(jù)結(jié)構(gòu)是列表。FreeRTOS使用列表結(jié)構(gòu)來(lái)跟蹤調(diào)度任務(wù)，并執(zhí)行隊(duì)列。

圖3.3：就緒列表全貌

這個(gè)FreeRTOS的列表是一個(gè)有著幾個(gè)有趣的補(bǔ)充的標(biāo)準(zhǔn)循環(huán)雙鏈表。下面就是列表元素：

struct xLIST_ITEM
{
portTickType xItemValue; /* The value being listed. In most cases
this is used to sort the list in
descending order. */
volatile struct xLIST_ITEM * pxNext; /* Pointer to the next xListItem in the
list. */
volatile struct xLIST_ITEM * pxPrevious; /* Pointer to the previous xListItem in
the list. */
void * pvOwner; /* Pointer to the object (normally a TCB)
that contains the list item. There is
therefore a two-way link between the
object containing the list item and
the list item itself. */
void * pvContainer; /* Pointer to the list in which this list
item is placed (if any). */
};

每個(gè)元素持有一個(gè)數(shù)字，xItemValue，這通常是一個(gè)被跟蹤的任務(wù)優(yōu)先級(jí)或者是一個(gè)調(diào)度事件的計(jì)時(shí)器值。列表保存從高到低的優(yōu)先級(jí)指令，這意味著最高的優(yōu)先級(jí)xItemValue（最大數(shù)）在列表的最前端，而最低的優(yōu)先級(jí)xItemValue（最小數(shù)）在列表的末尾。

pxNext和pxPrevious指針是標(biāo)準(zhǔn)鏈表指針。pvOwner 列表元素所有者的指針。這通常是任務(wù)的TCB對(duì)象的指針。pvOwner被用來(lái)在vTaskSwitchContext()中加快任務(wù)切換：當(dāng)最高優(yōu)先級(jí)任務(wù)元素在pxReadyTasksLists[]中被發(fā)現(xiàn)，這個(gè)列表元素的pvOwner指針直接連接到需要任務(wù)調(diào)度的TCB。

pvContainer指向自己所在的這個(gè)列表。若列表項(xiàng)處于一個(gè)特定列表它被用作快速終止。任意列表元素可以被置于一個(gè)列表，如下所定義：
typedef struct xLIST
{
volatile unsigned portBASE_TYPE uxNumberOfItems;
volatile xListItem * pxIndex; /* Used to walk through the list. Points to
the last item returned by a call to
pvListGetOwnerOfNextEntry (). */
volatile xMiniListItem xListEnd; /* List item that contains the maximum
possible item value, meaning it is always
at the end of the list and is therefore
used as a marker. */
} xList;

列表的大小任何時(shí)候都是被存儲(chǔ)在uxNumberOfItems中，用于快速列表大小操作。所有的列表都被初始化為容納一個(gè)元素：xListEnd元素。xListEnd.xItemValue是一個(gè)定點(diǎn)值，當(dāng)portTickType是16位數(shù)時(shí)，它等于xItemValue變量的最大值：0xffff，portTickType是32位數(shù)時(shí)為0xffffffff。其他的列表元素也可以使用相同的值；插入算法保證了xListEnd總是列表項(xiàng)中最后一個(gè)值。

自列表從高到低排序后，xListEnd被用作列表開(kāi)始的記號(hào)。并且，自循環(huán)開(kāi)始，xListEnd也被用作列表結(jié)束的記號(hào)。

你也許可以用一個(gè)單獨(dú)的for()循環(huán)或者是函數(shù)調(diào)用來(lái)訪問(wèn)大多數(shù)“傳統(tǒng)的”列表，去做所有的工作，就像這樣：

for (listPtr = listStart; listPtr != NULL; listPtr = listPtr->next) {
// Do something with listPtr here...
}

FreeRTOS經(jīng)常需要通過(guò)多個(gè)for()和while()循環(huán)，也包括函數(shù)調(diào)用來(lái)訪問(wèn)列表，因此它使用操縱pxIndex指針的列表函數(shù)來(lái)遍歷這個(gè)列表。這個(gè)列表函數(shù)listGET_OWNER_OF_NEXT_ENTRY()執(zhí)行pxIndex = pxIndex->pxNext;并且返回pxIndex。（當(dāng)然它也會(huì)正確檢測(cè)列尾環(huán)繞。）這種，當(dāng)執(zhí)行遍歷的時(shí)候使用pxIndex，由列表自己負(fù)責(zé)跟蹤“在哪里”的方法，使FreeRTOS可以休息而不用關(guān)心這方面的事。

圖3.4：系統(tǒng)節(jié)拍計(jì)時(shí)器下的FreeRTOS就緒列表全貌

pxReadyTasksLists[]列出了在vTaskSwitchContext()中已經(jīng)操縱完成的內(nèi)容，是如何使用pxIndex的一個(gè)很好的例子。讓我們假設(shè)我們僅有一個(gè)優(yōu)先級(jí)，優(yōu)先級(jí)0，并且有三個(gè)任務(wù)在此優(yōu)先級(jí)上。這與我們之前看到的基本就緒列表圖相似，但這一次我們將包括所有的數(shù)據(jù)結(jié)構(gòu)和字段。

就如你在圖3.3中所見(jiàn)，pxCurrentTCB顯示我們當(dāng)前正在運(yùn)行任務(wù)B。下一個(gè)時(shí)刻，vTaskSwitchContext()運(yùn)行，它調(diào)用listGET_OWNER_OF_NEXT_ENTRY()載入下一個(gè)任務(wù)來(lái)運(yùn)行。如圖3.4所示，這個(gè)函數(shù)使用pxIndex->pxNext找出下一個(gè)任務(wù)是任務(wù)C，并且pxIndex指向任務(wù)C的列表元素，同時(shí)pxCurrentTCB指向任務(wù)C的TCB。

請(qǐng)注意，每個(gè)struct xlistitem對(duì)象實(shí)際上都是來(lái)自相關(guān)TCB的xGenericListItem對(duì)象。

3.6. 隊(duì)列

FreeRTOS允許任務(wù)使用隊(duì)列來(lái)互相間通信和同步。中斷服務(wù)程序（ISRs）同樣使用隊(duì)列來(lái)通信和同步。

基本隊(duì)列數(shù)據(jù)結(jié)構(gòu)如下：
typedef struct QueueDefinition
{
signed char *pcHead; /* Points to the beginning of the queue
storage area. */
signed char *pcTail; /* Points to the byte at the end of the
queue storage area. One more byte is
allocated than necessary to store the
queue items; this is used as a marker. */
signed char *pcWriteTo; /* Points to the free next place in the
storage area. */
signed char *pcReadFrom; /* Points to the last place that a queued
item was read from. */

xList xTasksWaitingToSend; /* List of tasks that are blocked waiting
to post onto this queue. Stored in
priority order. */
xList xTasksWaitingToReceive; /* List of tasks that are blocked waiting
to read from this queue. Stored in
priority order. */

volatile unsigned portBASE_TYPE uxMessagesWaiting; /* The number of items currently
in the queue. */
unsigned portBASE_TYPE uxLength; /* The length of the queue
defined as the number of
items it will hold, not the
number of bytes. */
unsigned portBASE_TYPE uxItemSize; /* The size of each items that
the queue will hold. */

} xQUEUE;

這是一個(gè)頗為標(biāo)準(zhǔn)的隊(duì)列，不但包括了頭部和尾部指針，而且指針指向我們剛剛讀過(guò)或者寫(xiě)過(guò)的位置。

當(dāng)剛剛創(chuàng)建一個(gè)隊(duì)列，用戶(hù)指定了隊(duì)列的長(zhǎng)度和需要隊(duì)列跟蹤的項(xiàng)目大小。pcHead和pcTail被用來(lái)跟蹤隊(duì)列的內(nèi)部存儲(chǔ)器。加入一個(gè)項(xiàng)目到隊(duì)列就對(duì)隊(duì)列內(nèi)部存儲(chǔ)器進(jìn)行一次深拷貝。

FreeRTOS用深拷貝替代在項(xiàng)目中存放一個(gè)指針是因?yàn)橛锌赡茼?xiàng)目插入的生命周期要比隊(duì)列的生命周期短。例如，試想一個(gè)簡(jiǎn)單的整數(shù)隊(duì)列使用局部變量，跨幾個(gè)函數(shù)調(diào)用的插入和刪除。如果這個(gè)隊(duì)列在局部變量里存儲(chǔ)這些整數(shù)的指針，當(dāng)整數(shù)的局部變量離開(kāi)作用域時(shí)指針將會(huì)失效，同時(shí)局部變量的存儲(chǔ)空間將被新的數(shù)值使用。

什么需要用戶(hù)選擇使用隊(duì)列。若內(nèi)容很少，用戶(hù)可以把復(fù)制的內(nèi)容進(jìn)行排列，就像上圖中簡(jiǎn)單整數(shù)的例子，或者，若內(nèi)容很多，用戶(hù)可以排列內(nèi)容的指針。請(qǐng)注意，在這兩種情況下FreeRTOS都是在做深拷貝：如果用戶(hù)選擇排列復(fù)制的內(nèi)容，那么這個(gè)隊(duì)列存儲(chǔ)了每項(xiàng)內(nèi)容的一份深拷貝；如果用戶(hù)選擇了排列指針，隊(duì)列存儲(chǔ)了指針的一份深拷貝。當(dāng)然，用戶(hù)在隊(duì)列里存儲(chǔ)了指針，那么用戶(hù)有責(zé)任管理與內(nèi)存相關(guān)的指針。隊(duì)列并不關(guān)心你存儲(chǔ)了什么樣的數(shù)據(jù)，它只需要知道數(shù)據(jù)的大小。

FreeRTOS支持阻塞和非阻塞隊(duì)列的插入和移除。非阻塞隊(duì)列操作會(huì)立即返回"隊(duì)列的插入是否完成?"或者 "隊(duì)列的移除是否完成？"的狀態(tài)。阻塞操作則根據(jù)特定的超時(shí)。一個(gè)任務(wù)可以無(wú)限期地阻塞或者在有限時(shí)間里阻塞。

一個(gè)阻塞任務(wù)——叫它任務(wù)A——將保持阻塞只要它的插入/移除操作沒(méi)有完成，并且它的超時(shí)（如果存在）沒(méi)有過(guò)期。如果一個(gè)中斷或者另一個(gè)任務(wù)編輯了這個(gè)隊(duì)列以便任務(wù)A的操作能夠完成，任務(wù)A將被解除阻塞。如果此時(shí)任務(wù)A的隊(duì)列操作仍然是允許的，那么它實(shí)際上會(huì)執(zhí)行操作，于是任務(wù)A會(huì)完成它的隊(duì)列操作，并且返回“成功”的狀態(tài)。不過(guò)，任務(wù)A正在執(zhí)行的那個(gè)時(shí)間，有可能同時(shí)有一個(gè)高優(yōu)先級(jí)任務(wù)或者中斷也在同一個(gè)隊(duì)列上執(zhí)行另一個(gè)操作，這會(huì)阻止任務(wù)A正在執(zhí)行的操作。在這種情況下任務(wù)A將檢查它的超時(shí)，同時(shí)，如果它未超時(shí)就恢復(fù)阻塞，否則就返回隊(duì)列操作“失敗”的狀態(tài)。

特別需要注意的是，當(dāng)任務(wù)被阻塞在一個(gè)隊(duì)列時(shí)，系統(tǒng)保持運(yùn)行所帶來(lái)的風(fēng)險(xiǎn)；以及當(dāng)任務(wù)被阻塞在一個(gè)隊(duì)列時(shí)，有其他任務(wù)或中斷在繼續(xù)運(yùn)行。這種阻塞任務(wù)的方法能不浪費(fèi)CPU周期，使其他任務(wù)和中斷可以有效地使用CPU周期。

FreeRTOS使用xTasksWaitingToSend列表來(lái)保持對(duì)正阻塞在插入隊(duì)列里的任務(wù)的跟蹤。每當(dāng)有一個(gè)元素被移出隊(duì)列，xTasksWaitingToSend列表就會(huì)被檢查。如果有個(gè)任務(wù)在那個(gè)列表中等待，那個(gè)是未阻塞任務(wù)。同樣的，xTasksWaitingToReceive保持對(duì)那些正阻塞在移除隊(duì)列里的任務(wù)的跟蹤。每當(dāng)有一個(gè)新元素被插入到隊(duì)列，xTasksWaitingToReceive列表就會(huì)被檢查。如果有個(gè)任務(wù)在那個(gè)列表中等待，那個(gè)是未阻塞任務(wù)。

信號(hào)燈和互斥

FreeRTOS使用它的隊(duì)列與任務(wù)通信，也在任務(wù)間通信。FreeRTOS也使用它的隊(duì)列來(lái)實(shí)現(xiàn)信號(hào)燈與互斥。

有什么區(qū)別？

信號(hào)燈與互斥聽(tīng)上去像一回事，但它們不是。FreeRTOS同樣地實(shí)現(xiàn)了它們，但本來(lái)它們以不同的方式被使用。它們是如何不同地被使用？嵌入式系統(tǒng)宗師Michael Barr說(shuō)這是在他文章中寫(xiě)得最好的，“信號(hào)燈與互斥揭秘”：

The correct use of a semaphore is for signaling from one task to another. A mutex is meant to be taken and released, always in that order, by each task that uses the shared resource it protects. By contrast, tasks that use semaphores either signal ["send" in FreeRTOS terms] or wait ["receive" in FreeRTOS terms] - not both.

正確使用的一個(gè)信號(hào)是從一個(gè)任務(wù)向另一個(gè)發(fā)信號(hào)。從每個(gè)使用被保護(hù)共享資源的任務(wù)來(lái)看，總是認(rèn)為，一個(gè)互斥意味著獲得和釋放。相比之下，使用信號(hào)燈的任務(wù)不是發(fā)信號(hào)[在FreeRTOS里“發(fā)送”]就是在等信號(hào)[在FreeRTOS里“接收”]——不能同時(shí)。

互斥被用來(lái)保護(hù)共享資源。一個(gè)使用共享資源的任務(wù)獲得互斥，接著釋放互斥。當(dāng)有另一個(gè)任務(wù)占據(jù)互斥時(shí)，沒(méi)有一個(gè)任務(wù)可以獲得這個(gè)互斥。這就是保證，在同一時(shí)刻僅有一個(gè)任務(wù)可以使用共享資源。

一個(gè)任務(wù)向另一個(gè)任務(wù)發(fā)信號(hào)時(shí)使用信號(hào)燈。以下引用Barr的文章：

For example, Task 1 may contain code to post (i.e., signal or increment) a particular semaphore when the "power" button is pressed and Task 2, which wakes the display, pends on that same semaphore. In this scenario, one task is the producer of the event signal; the other the consumer.

舉例來(lái)說(shuō)，任務(wù)一可能包含當(dāng)“電源”按鈕被按下時(shí)，發(fā)布（即，發(fā)信號(hào)或增加信號(hào)量）一個(gè)特定的信號(hào)燈的代碼，并且喚醒顯示屏的任務(wù)二，取決于同一個(gè)信號(hào)燈。在這種情況下，一個(gè)任務(wù)是發(fā)信號(hào)事件的制造者；另一個(gè)是消費(fèi)者。

如果你是在信號(hào)燈和互斥有任何疑問(wèn)，請(qǐng)查閱Michael的文章。