FreeRTOS链表与通信机制

System rtos

FreeRTOS的链表
1. 插入
2. 删除
FreeRTOS中的queue

FreeRTOS的链表

链表是一个非常常见的数据结构，各种实现基本大同小异且实现也相对简单。在FreeRTOS中同样也实现了链表，这个链表是特意为FreeRTOS的调度器而设计的，为的是满足调度器的功能需求，不同在普通应用中也可以使用这个链表。

如下为FreeRTOS中链表的定义：

struct xLIST_ITEM
{
    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
    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
};
typedef struct xLIST_ITEM ListItem_t;

struct xMINI_LIST_ITEM
{
    listFIRST_LIST_ITEM_INTEGRITY_CHECK_VALUE
    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    
    volatile UBaseType_t uxNumberOfItems;
    ListItem_t * configLIST_VOLATILE pxIndex
    MiniListItem_t xListEnd;                
    listSECOND_LIST_INTEGRITY_CHECK_VALUE
} List_t;

其组织结构如下图所示：

List组织结构

其中在ListItem_t结构中定义了一个MiniListItem_t成员xListEnd，它是作为List的一个锚点使用的，它总是代表List的最后一个元素，其中记录的xItemValue值为一个整型的最大值。

另外就是结构中包含的*_CHECK_VALUE，这几个宏会根据宏开关的使能情况在结构体中定义用于完整性检查的整型变量，相对于FreeRTOS的功能性而言不用关注，但这是一个有用的编程技巧，常用于调试中。

插入

这个List有两个插入接口:

1 2	void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem ); void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )

vListInsertEnd

vListInsertEnd接口将新插入的节点放在链表末尾
vListInsert

vListInsert这个接口比较有趣，这是一个有序的插入接口。由于按这个接口插入的节点是有序的，从前向后为由小到大排序，因此插入时会根据新节点的xItemValue值将新节点插入到这个有序链表的合适位置。

Note: 其中存在一个边界情况，当新节点的值和链表中某一个节点的值相等时，总是将新节点置于其后，而不是其前。

删除

1	UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )

删除就是简单的链表遍历和删除。

FreeRTOS中的queue

queue的结构定义如下：

typedef struct QueuePointers
{
    int8_t *pcTail;                 /*< Points to the byte at the end of the queue storage area.  Once more byte is allocated than necessary to store the queue items, this is used as a marker. */
    int8_t *pcReadFrom;             /*< Points to the last place that a queued item was read from when the structure is used as a queue. */
} QueuePointers_t;

typedef struct SemaphoreData
{
    TaskHandle_t xMutexHolder;       /*< The handle of the task that holds the mutex. */
    UBaseType_t uxRecursiveCallCount;/*< Maintains a count of the number of times a recursive mutex has been recursively 'taken' when the structure is used as a mutex. */
} SemaphoreData_t;

struct QueueDefinition      /* The old naming convention is used to prevent breaking kernel aware debuggers. */
{
    int8_t *pcHead;                 /*< Points to the beginning of the queue storage area. */
    int8_t *pcWriteTo;              /*< Points to the free next place in the storage area. */

    union
    {
        QueuePointers_t xQueue;     /*< Data required exclusively when this structure is used as a queue. */
        SemaphoreData_t xSemaphore; /*< Data required exclusively when this structure is used as a semaphore. */
    } u;

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

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

    volatile int8_t cRxLock;        /*< Stores the number of items received from the queue (removed from the queue) while the queue was locked.  Set to queueUNLOCKED when the queue is not locked. */
    volatile int8_t cTxLock;        /*< Stores the number of items transmitted to the queue (added to the queue) while the queue was locked.  Set to queueUNLOCKED when the queue is not locked. */

    #if( ( configSUPPORT_STATIC_ALLOCATION == 1 ) && ( configSUPPORT_DYNAMIC_ALLOCATION == 1 ) )
        uint8_t ucStaticallyAllocated;  /*< Set to pdTRUE if the memory used by the queue was statically allocated to ensure no attempt is made to free the memory. */
    #endif

    #if ( configUSE_QUEUE_SETS == 1 )
        struct QueueDefinition *pxQueueSetContainer;
    #endif

    #if ( configUSE_TRACE_FACILITY == 1 )
        UBaseType_t uxQueueNumber;
        uint8_t ucQueueType;
    #endif

} xQUEUE;

Queue的实现机制

QueueHandle_t xQueueGenericCreate( const UBaseType_t uxQueueLength, const UBaseType_t uxItemSize, const uint8_t ucQueueType );

BaseType_t xQueueReceive( QueueHandle_t xQueue, void * const pvBuffer, TickType_t xTicksToWait );

BaseType_t xQueueGenericSend( QueueHandle_t xQueue, const void * const pvItemToQueue, TickType_t xTicksToWait, const BaseType_t xCopyPosition );

关于Queue主要由三类接口，创建、发送和接收。在这三类接口的基础上，FreeRTOS又对其进行了二次封装，从而衍生出了互斥量和信号量和消息队列机制。因此在FreeRTOS的具体实现中，queue不仅仅是我们在数据结构上理解的队列形式，更是FreeRTOS实现的一套进程间通信机制。

由于互斥量，信号量和消息队列机制都拥有阻塞进程执行的能力，因此在FreeRTOS队列的实现分为了两个版本，一个是用于进程使用的版本，一个是用于中断服务例程，它们的区别就是进程的版本中，内部实现拥有阻塞进程，引起进程切换的能力，反之，中断版本则没有，都是直接返回。

对于FreeRTOS而言，实现互斥、信号量和消息队列机制依赖的底层实现需要根据不同的平台而定，但通常都直接基于了开/关中断的机制与进程切换机制，这样是比较常见的一种实现。

Queue创建

xQueueGenericCreate会创建并初始化一个QueueHandle_t类型的队列指针，这个指针指向一个队列结构，同时一块用于存储入队对象的内存也会紧贴队列结构创建，因此QueueHandle_t返回的指针所指向的对象结构初始化后结构如下所示：

动态申请内存创建队列

其中uxItemSize字段与ucQueueType字段是FreeRTOS中的队列区分消息队列、信号量和互斥量的关键，其值不同，在发送与接收时所表现的特征有细微的区别。

Queue的消息发送

消息队列

对于消息队列而言，消息发送接口会将发送的消息完整copy到相应的队列中去，所有进程正在这个队列上等待且优先级较高，则会执行进程调度。
信号量

对于信号量或互斥量而言，由于它们不存在数据存储区，而只有queue这个结构体，因此在消息发送时，不会引起任何数据拷贝，而只会使uxMessagesWaiting这个字段加1，而uxMessagesWaiting字段的值则是区分信号量与互斥量的标准，对互斥量而言，该字段的可能值只为0或1。

同时在FreeRTOS中，为了避免优先级反转问题的发生，实现了优先级继承算法，当然对于这个问题的解决，还可以使用优先级天花板算法。

Queue的消息接收

消息队列

对于消息队列而言，消息接收接口会从队列的缓冲区拿到消息，同时会检查发送等待队列上是否有优先级较高的进程需要调度。
信号量

对于信号量或互斥量而言，消息接收所做的操作刚好与消息发送相反，这从抽象的角度，它们的发送与接收就是操作系统中典型的PV操作。

转载请注明来源，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 yxhlfx@163.com