3.5. 列表

任務之后，最常用的FreeRTOS數據結構是列表。FreeRTOS使用列表結構來跟蹤調度任務，并執行隊列。

圖3.3：就緒列表全貌

這個FreeRTOS的列表是一個有著幾個有趣的補充的標準循環雙鏈表。下面就是列表元素：

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). */
};

每個元素持有一個數字，xItemValue，這通常是一個被跟蹤的任務優先級或者是一個調度事件的計時器值。列表保存從高到低的優先級指令，這意味著最高的優先級xItemValue（最大數）在列表的最前端，而最低的優先級xItemValue（最小數）在列表的末尾。

pxNext和pxPrevious指針是標準鏈表指針。pvOwner 列表元素所有者的指針。這通常是任務的TCB對象的指針。pvOwner被用來在vTaskSwitchContext()中加快任務切換：當最高優先級任務元素在pxReadyTasksLists[]中被發現，這個列表元素的pvOwner指針直接連接到需要任務調度的TCB。

pvContainer指向自己所在的這個列表。若列表項處于一個特定列表它被用作快速終止。任意列表元素可以被置于一個列表，如下所定義：
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;

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

自列表從高到低排序后，xListEnd被用作列表開始的記號。并且，自循環開始，xListEnd也被用作列表結束的記號。

你也許可以用一個單獨的for()循環或者是函數調用來訪問大多數“傳統的”列表，去做所有的工作，就像這樣：

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

FreeRTOS經常需要通過多個for()和while()循環，也包括函數調用來訪問列表，因此它使用操縱pxIndex指針的列表函數來遍歷這個列表。這個列表函數listGET_OWNER_OF_NEXT_ENTRY()執行pxIndex = pxIndex->pxNext;并且返回pxIndex。（當然它也會正確檢測列尾環繞。）這種，當執行遍歷的時候使用pxIndex，由列表自己負責跟蹤“在哪里”的方法，使FreeRTOS可以休息而不用關心這方面的事。

圖3.4：系統節拍計時器下的FreeRTOS就緒列表全貌

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

就如你在圖3.3中所見，pxCurrentTCB顯示我們當前正在運行任務B。下一個時刻，vTaskSwitchContext()運行，它調用listGET_OWNER_OF_NEXT_ENTRY()載入下一個任務來運行。如圖3.4所示，這個函數使用pxIndex->pxNext找出下一個任務是任務C，并且pxIndex指向任務C的列表元素，同時pxCurrentTCB指向任務C的TCB。

請注意，每個struct xlistitem對象實際上都是來自相關TCB的xGenericListItem對象。

3.6. 隊列

FreeRTOS允許任務使用隊列來互相間通信和同步。中斷服務程序（ISRs）同樣使用隊列來通信和同步。

基本隊列數據結構如下：
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;

這是一個頗為標準的隊列，不但包括了頭部和尾部指針，而且指針指向我們剛剛讀過或者寫過的位置。

當剛剛創建一個隊列，用戶指定了隊列的長度和需要隊列跟蹤的項目大小。pcHead和pcTail被用來跟蹤隊列的內部存儲器。加入一個項目到隊列就對隊列內部存儲器進行一次深拷貝。

FreeRTOS用深拷貝替代在項目中存放一個指針是因為有可能項目插入的生命周期要比隊列的生命周期短。例如，試想一個簡單的整數隊列使用局部變量，跨幾個函數調用的插入和刪除。如果這個隊列在局部變量里存儲這些整數的指針，當整數的局部變量離開作用域時指針將會失效，同時局部變量的存儲空間將被新的數值使用。

什么需要用戶選擇使用隊列。若內容很少，用戶可以把復制的內容進行排列，就像上圖中簡單整數的例子，或者，若內容很多，用戶可以排列內容的指針。請注意，在這兩種情況下FreeRTOS都是在做深拷貝：如果用戶選擇排列復制的內容，那么這個隊列存儲了每項內容的一份深拷貝；如果用戶選擇了排列指針，隊列存儲了指針的一份深拷貝。當然，用戶在隊列里存儲了指針，那么用戶有責任管理與內存相關的指針。隊列并不關心你存儲了什么樣的數據，它只需要知道數據的大小。

FreeRTOS支持阻塞和非阻塞隊列的插入和移除。非阻塞隊列操作會立即返回"隊列的插入是否完成?"或者 "隊列的移除是否完成？"的狀態。阻塞操作則根據特定的超時。一個任務可以無限期地阻塞或者在有限時間里阻塞。

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

特別需要注意的是，當任務被阻塞在一個隊列時，系統保持運行所帶來的風險；以及當任務被阻塞在一個隊列時，有其他任務或中斷在繼續運行。這種阻塞任務的方法能不浪費CPU周期，使其他任務和中斷可以有效地使用CPU周期。

FreeRTOS使用xTasksWaitingToSend列表來保持對正阻塞在插入隊列里的任務的跟蹤。每當有一個元素被移出隊列，xTasksWaitingToSend列表就會被檢查。如果有個任務在那個列表中等待，那個是未阻塞任務。同樣的，xTasksWaitingToReceive保持對那些正阻塞在移除隊列里的任務的跟蹤。每當有一個新元素被插入到隊列，xTasksWaitingToReceive列表就會被檢查。如果有個任務在那個列表中等待，那個是未阻塞任務。

信號燈和互斥

FreeRTOS使用它的隊列與任務通信，也在任務間通信。FreeRTOS也使用它的隊列來實現信號燈與互斥。

有什么區別？

信號燈與互斥聽上去像一回事，但它們不是。FreeRTOS同樣地實現了它們，但本來它們以不同的方式被使用。它們是如何不同地被使用？嵌入式系統宗師Michael Barr說這是在他文章中寫得最好的，“信號燈與互斥揭秘”：

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.

正確使用的一個信號是從一個任務向另一個發信號。從每個使用被保護共享資源的任務來看，總是認為，一個互斥意味著獲得和釋放。相比之下，使用信號燈的任務不是發信號[在FreeRTOS里“發送”]就是在等信號[在FreeRTOS里“接收”]——不能同時。

互斥被用來保護共享資源。一個使用共享資源的任務獲得互斥，接著釋放互斥。當有另一個任務占據互斥時，沒有一個任務可以獲得這個互斥。這就是保證，在同一時刻僅有一個任務可以使用共享資源。

一個任務向另一個任務發信號時使用信號燈。以下引用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.

舉例來說，任務一可能包含當“電源”按鈕被按下時，發布（即，發信號或增加信號量）一個特定的信號燈的代碼，并且喚醒顯示屏的任務二，取決于同一個信號燈。在這種情況下，一個任務是發信號事件的制造者；另一個是消費者。

如果你是在信號燈和互斥有任何疑問，請查閱Michael的文章。