自学内容网 自学内容网

FreeRTOS 11:FreeRTOS队列的数据结构与队列创建原理

队列数据结构Queue_t

队列的结构体为 Queue_t,在 queue.c 文件中有定义,具体的代码如下所示:

typedef struct QueueDefinition /* 保留旧的命名约定以防止破坏内核感知调试器。 */
{
    int8_t * pcHead;           /*< 指向队列存储区域的起始位置。 */
    int8_t * pcWriteTo;        /*< 指向存储区域中的下一个空闲位置。 */

    union
    {
        QueuePointers_t xQueue;     /*< 当此结构用作队列时所需的数据。 */
        SemaphoreData_t xSemaphore; /*< 当此结构用作信号量时所需的数据。 */
    } u;

    List_t xTasksWaitingToSend;             /*< 等待向此队列发送数据的任务列表。按优先级顺序存储。 */
    List_t xTasksWaitingToReceive;          /*< 等待从队列读取数据的任务列表。按优先级顺序存储。 */

    volatile UBaseType_t uxMessagesWaiting; /*< 队列中当前的项目数量。 */
    UBaseType_t uxLength;                   /*< 队列的长度,定义为它可以持有的项目数量,而不是字节数。 */
    UBaseType_t uxItemSize;                 /*< 队列将持有的每个项目的大小。 */

    volatile int8_t cRxLock;                /*< 存储在队列锁定期间从队列接收(移除)的项目数量。当队列未锁定时设置为queueUNLOCKED。 */
    volatile int8_t cTxLock;                /*< 存储在队列锁定期间向队列传输(添加)的项目数量。当队列未锁定时设置为queueUNLOCKED。 */

    #if ( ( configSUPPORT_STATIC_ALLOCATION == 1 ) && ( configSUPPORT_DYNAMIC_ALLOCATION == 1 ) )
        uint8_t ucStaticallyAllocated; /*< 如果队列使用的内存是静态分配的,则设置为pdTRUE,以确保不会尝试释放内存。 */
    #endif

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

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

/* 上面保留了旧的 xQUEUE 名称,然后在此处 typedef 为新的 Queue_t 名称,以便使用较旧的内核感知调试器。 */
typedef xQUEUE Queue_t;

主要成员包括:

  • pcHead 和 pcWriteTo:分别指向队列存储区域的起始位置和下一个空闲位置。

  • u:联合体,包含队列和信号量所需的数据。

  • xTasksWaitingToSend 和 xTasksWaitingToReceive:分别存储等待发送和接收数据的任务列表。

  • uxMessagesWaiting:队列中当前的项目数量。

  • uxLength 和 uxItemSize:队列的长度和每个项目的大小。

  • cRxLock 和 cTxLock:用于队列锁定期间的计数。

  • 其他成员根据编译选项动态添加,用于支持静态分配、队列集合和跟踪设施。

FreeRTOS 基于队列实现了互斥信号量和递归互斥信号量功能,在队列的结构体中,就包含了一个联合体 u,当队列结构体用作队列时,使用联合体 u 中的 xQueue,其数据类 型为 QueuePointers_t,在 queue.c 文件中有定义,具体的代码如下QueuePointers_t所示;而当队列结构体用于互斥信号量和递归互斥信号量时,则是使用联合体 u 中的 xSemaphore,其数据类型为 SemaphoreData_t,在 queue.c 文件中有定义,具体的代码如下SemaphoreData_t所示:

typedef struct QueuePointers
{
    int8_t * pcTail;     /*< 指向队列存储区域末尾的字节。分配的字节数比存储队列项目所需的多一个,用作标记。 */
    int8_t * pcReadFrom; /*< 当此结构用作队列时,指向最后一个从队列中读取项目的地址。 */
} QueuePointers_t;

typedef struct SemaphoreData
{
    TaskHandle_t xMutexHolder;        /*< 持有互斥锁的任务句柄。 */
    UBaseType_t uxRecursiveCallCount; /*< 当此结构用作互斥锁时,维护递归互斥锁被递归“获取”的次数。 */
} SemaphoreData_t;
  1. QueuePointers 结构体:

    • pcTail: 指向队列存储区域末尾的字节,用于标记队列的结束位置。

    • pcReadFrom: 指向最后一个从队列中读取项目的地址,用于记录读取位置。

  2. SemaphoreData 结构体:

    • xMutexHolder: 持有互斥锁的任务句柄,用于标识当前持有互斥锁的任务。

    • uxRecursiveCallCount: 维护递归互斥锁被递归“获取”的次数,用于支持递归锁功能。

在创建消息队列的时候,是需要用户自己定义消息队列的句柄的,但是注意了,定义了队列的句柄并不等于创建了队列,创建队列必须是调用消息队列创建函数进行创建(可以是静态也可以是动态创建) ,否则,以后根据队列句柄使用消息队列的其它函数的时候会发生错误,创建完成会返回消息队列的句柄,用户通过句柄就可使用消息队列进行发送与读取消息队列的操作,如果返回的是 NULL 则表示创建失败 。创建完成的队列示意图具体见图

动态创建xQueueCreate

此函数用于使用动态方式创建队列,队列所需的内存空间由 FreeRTOS 从 FreeRTOS 管理的堆中分配。函数 xQueueCreate()实际上是一个宏定义,在 queue.h 文件中有定义,具体的代码如下所示:

函数 xQueueCreate()的形参描述,如下表所示:

函数 xQueueCreate()的返回值,如下表所示:

/**
 * queue.h
 * <pre>
 * QueueHandle_t xQueueCreate(
 *                            UBaseType_t uxQueueLength,
 *                            UBaseType_t uxItemSize
 *                        );
 * </pre>
 *
 * 创建一个新的队列实例,并返回一个可以引用新队列的句柄。
 *
 * 在 FreeRTOS 内部实现中,队列使用两块内存。第一块用于保存队列的数据结构。第二块用于保存放入队列中的项。如果使用 xQueueCreate() 创建队列,则这两块内存都会在 xQueueCreate() 函数内部自动动态分配。(参见 https://www.FreeRTOS.org/a00111.html)。如果使用 xQueueCreateStatic() 创建队列,则应用程序编写者必须提供队列将使用的内存。因此,xQueueCreateStatic() 允许在不使用任何动态内存分配的情况下创建队列。
 *
 * https://www.FreeRTOS.org/Embedded-RTOS-Queues.html
 *
 * @param uxQueueLength 队列可以包含的最大项数。
 *
 * @param uxItemSize 队列中每个项所需的字节数。项是按值排队的,而不是按引用排队,所以这是每个发布项将被复制的字节数。队列中的每个项必须是相同的大小。
 *
 * @return 如果队列成功创建,则返回新创建队列的句柄。如果无法创建队列,则返回 0。
 *
 * 使用示例:
 * <pre>
 * struct AMessage
 * {
 *  char ucMessageID;
 *  char ucData[ 20 ];
 * };
 *
 * void vATask( void *pvParameters )
 * {
 * QueueHandle_t xQueue1, xQueue2;
 *
 *  // 创建一个能够包含 10 个 uint32_t 值的队列。
 *  xQueue1 = xQueueCreate( 10, sizeof( uint32_t ) );
 *  if( xQueue1 == 0 )
 *  {
 *      // 队列未创建且不得使用。
 *  }
 *
 *  // 创建一个能够包含 10 个指向 AMessage 结构的指针的队列。
 *  // 这些应该通过指针传递,因为它们包含大量数据。
 *  xQueue2 = xQueueCreate( 10, sizeof( struct AMessage * ) );
 *  if( xQueue2 == 0 )
 *  {
 *      // 队列未创建且不得使用。
 *  }
 *
 *  // ... 任务其余代码。
 * }
 * </pre>
 * \defgroup xQueueCreate xQueueCreate
 * \ingroup QueueManagement
 */
#if ( configSUPPORT_DYNAMIC_ALLOCATION == 1 )
    #define xQueueCreate( uxQueueLength, uxItemSize )    xQueueGenericCreate( ( uxQueueLength ), ( uxItemSize ), ( queueQUEUE_TYPE_BASE ) )
#endif

函数 xQueueCreate()实际上是调用了函数 xQueueGenericCreate(),函数xQueueGenericCreate()用于使用动态方式创建指定类型的队列,前面说 FreeRTOS 基于队列实现了多种功能,每一种功能对应一种队列类型,队列类型的 queue.h 文件中有定义,具体的代码如下所示:

#define queueQUEUE_TYPE_BASE ( ( uint8_t ) 0U ) /* 队列 */
#define queueQUEUE_TYPE_SET ( ( uint8_t ) 0U ) /* 队列集 */
#define queueQUEUE_TYPE_MUTEX ( ( uint8_t ) 1U ) /* 互斥信号量 */
#define queueQUEUE_TYPE_COUNTING_SEMAPHORE ( ( uint8_t ) 2U ) /* 计数型信号量 */
#define queueQUEUE_TYPE_BINARY_SEMAPHORE ( ( uint8_t ) 3U ) /* 二值信号量 */
#define queueQUEUE_TYPE_RECURSIVE_MUTEX ( ( uint8_t ) 4U ) /* 递归互斥信号量 */

xQueueGenericCreate

QueueHandle_t xQueueGenericCreate( const UBaseType_t uxQueueLength,
                                   const UBaseType_t uxItemSize,
                                   const uint8_t ucQueueType )
{
    Queue_t * pxNewQueue;
    size_t xQueueSizeInBytes;
    uint8_t * pucQueueStorage;

    configASSERT( uxQueueLength > ( UBaseType_t ) 0 );

    /* 分配足够的空间来保存队列中任何时候可能的最大项目数。当队列用作信号量时,uxItemSize 为零是有效的。 */
    xQueueSizeInBytes = ( size_t ) ( uxQueueLength * uxItemSize ); /*lint !e961 MISRA 异常,因为对于某些端口,强制转换是多余的。 */

    /* 检查乘法溢出。 */
    configASSERT( ( uxItemSize == 0 ) || ( uxQueueLength == ( xQueueSizeInBytes / uxItemSize ) ) );

    /* 检查加法溢出。 */
    configASSERT( ( sizeof( Queue_t ) + xQueueSizeInBytes ) >  xQueueSizeInBytes );

    /* 分配队列和存储区域。MISRA 偏差的理由如下:pvPortMalloc() 总是确保返回的内存块按 MCU 栈的要求对齐。在这种情况下,pvPortMalloc() 必须返回一个满足 Queue_t 结构对齐要求的指针——在这种情况下是一个 int8_t *。因此,只要栈对齐要求大于或等于指针到字符的要求,强制转换就是安全的。在其他情况下,对齐要求不严格(一两个字节)。 */
    pxNewQueue = ( Queue_t * ) pvPortMalloc( sizeof( Queue_t ) + xQueueSizeInBytes ); /*lint !e9087 !e9079 见上面的注释。 */

    if( pxNewQueue != NULL )
    {
        /* 跳过队列结构以找到队列存储区域的位置。 */
        pucQueueStorage = ( uint8_t * ) pxNewQueue;
        pucQueueStorage += sizeof( Queue_t ); /*lint !e9016 指针算术允许在 char 类型上使用,特别是当它有助于传达意图时。 */

        #if ( configSUPPORT_STATIC_ALLOCATION == 1 )
            {
                /* 队列可以静态或动态创建,因此注意此队列是动态创建的,以防稍后删除。 */
                pxNewQueue->ucStaticallyAllocated = pdFALSE;
            }
        #endif /* configSUPPORT_STATIC_ALLOCATION */

        prvInitialiseNewQueue( uxQueueLength, uxItemSize, pucQueueStorage, ucQueueType, pxNewQueue );
    }
    else
    {
        traceQUEUE_CREATE_FAILED( ucQueueType );
        mtCOVERAGE_TEST_MARKER();
    }

    return pxNewQueue;
}

  1. 参数检查

    • configASSERT( uxQueueLength > ( UBaseType_t ) 0 ):确保队列长度大于0。

  2. 计算队列所需内存大小

    • xQueueSizeInBytes = ( size_t ) ( uxQueueLength * uxItemSize ):计算队列所需内存大小。

    • configASSERT( ( uxItemSize == 0 ) || ( uxQueueLength == ( xQueueSizeInBytes / uxItemSize ) ) ):检查乘法溢出。

    • configASSERT( ( sizeof( Queue_t ) + xQueueSizeInBytes ) > xQueueSizeInBytes ):检查加法溢出。

  3. 内存分配

    • pxNewQueue = ( Queue_t * ) pvPortMalloc( sizeof( Queue_t ) + xQueueSizeInBytes ):分配内存。

  4. 初始化队列

    • pucQueueStorage = ( uint8_t * ) pxNewQueue; pucQueueStorage += sizeof( Queue_t ):跳过队列结构找到存储区域。

    • #if ( configSUPPORT_STATIC_ALLOCATION == 1 ):如果支持静态分配,标记为动态分配。

    • prvInitialiseNewQueue( uxQueueLength, uxItemSize, pucQueueStorage, ucQueueType, pxNewQueue ):初始化新队列。

  5. 失败处理

    • traceQUEUE_CREATE_FAILED( ucQueueType ):记录失败信息。

    • mtCOVERAGE_TEST_MARKER():覆盖率测试标记。

通过以上步骤,xQueueGenericCreate 函数完成了队列的创建和初始化。

函数 xQueueGenericCreate()主要负责为队列申请内存,然后调用函数 prvInitialiseNewQueue()对队列进行初始化,函数 prvInitialiseNewQueue()在 queue.c 文件中有定义,具体的代码如下所示:

prvInitialiseNewQueue()

xQueueGenericCreate()

prvInitialiseNewQueue()

static void prvInitialiseNewQueue( const UBaseType_t uxQueueLength,
                                   const UBaseType_t uxItemSize,
                                   uint8_t * pucQueueStorage,
                                   const uint8_t ucQueueType,
                                   Queue_t * pxNewQueue )
{
    /* 移除编译器关于未使用参数的警告,如果 configUSE_TRACE_FACILITY 未设置为 1。 */
    ( void ) ucQueueType;

    if( uxItemSize == ( UBaseType_t ) 0 )
    {
        /* 没有为队列存储区域分配 RAM,但 pcHead 不能设置为 NULL,因为 NULL 用作表示队列用作互斥锁的键。因此,将 pcHead 设置为指向队列的一个无害值,该值已知在内存映射中。 */
        pxNewQueue->pcHead = ( int8_t * ) pxNewQueue;
    }
    else
    {
        /* 将头指针设置为队列存储区域的起始位置。 */
        pxNewQueue->pcHead = ( int8_t * ) pucQueueStorage;
    }

    /* 初始化队列成员,如队列类型定义中所述。 */
    pxNewQueue->uxLength = uxQueueLength;
    pxNewQueue->uxItemSize = uxItemSize;
    ( void ) xQueueGenericReset( pxNewQueue, pdTRUE );

    #if ( configUSE_TRACE_FACILITY == 1 )
        {
            /* 如果启用了跟踪设施,设置队列类型。 */
            pxNewQueue->ucQueueType = ucQueueType;
        }
    #endif /* configUSE_TRACE_FACILITY */

    #if ( configUSE_QUEUE_SETS == 1 )
        {
            /* 如果启用了队列集,初始化队列集容器指针。 */
            pxNewQueue->pxQueueSetContainer = NULL;
        }
    #endif /* configUSE_QUEUE_SETS */

    traceQUEUE_CREATE( pxNewQueue );
}

  1. 移除编译器警告:如果 configUSE_TRACE_FACILITY 未设置为 1,则移除编译器关于未使用参数 ucQueueType 的警告。

  2. 设置队列头指针

    • 如果 uxItemSize 为 0,将 pcHead 设置为 pxNewQueue 的地址。

    • 否则,将 pcHead 设置为 pucQueueStorage 的地址。

  3. 初始化队列成员

    • 设置队列长度 uxLength 和项大小 uxItemSize

    • 调用 xQueueGenericReset 重置队列。

  4. 启用跟踪设施:如果 configUSE_TRACE_FACILITY 为 1,设置队列类型 ucQueueType

  5. 启用队列集:如果 configUSE_QUEUE_SETS 为 1,初始化队列集容器指针 pxQueueSetContainer

xQueueGenericReset()

函数 prvInitialiseNewQueue()主要用于初始化队列结构体中的成员变量,其中还会调用函数 xQueueGenericReset()对队列进行重置,函数 xQueueGenericReset()在queue.c 文件中有定义,具体的代码如下所示:

xQueueGenericCreate()

prvInitialiseNewQueue()

xQueueGenericReset()--javascripttypescriptshellbashsqljsonhtmlcssccppjavarubypythongorustmarkdown

BaseType_t xQueueGenericReset( QueueHandle_t xQueue,
                               BaseType_t xNewQueue )
{
    Queue_t * const pxQueue = xQueue;

    configASSERT( pxQueue );

    taskENTER_CRITICAL();
    {
        pxQueue->u.xQueue.pcTail = pxQueue->pcHead + ( pxQueue->uxLength * pxQueue->uxItemSize ); /*lint !e9016 指针算术允许在 char 类型上使用,特别是当它有助于传达意图时。 */
        pxQueue->uxMessagesWaiting = ( UBaseType_t ) 0U;
        pxQueue->pcWriteTo = pxQueue->pcHead;
        pxQueue->u.xQueue.pcReadFrom = pxQueue->pcHead + ( ( pxQueue->uxLength - 1U ) * pxQueue->uxItemSize ); /*lint !e9016 指针算术允许在 char 类型上使用,特别是当它有助于传达意图时。 */
        pxQueue->cRxLock = queueUNLOCKED;
        pxQueue->cTxLock = queueUNLOCKED;

        if( xNewQueue == pdFALSE )
        {
            /* 如果有任务阻塞等待从队列读取数据,那么这些任务将保持阻塞状态,因为在该函数退出后队列仍然为空。如果有任务阻塞等待向队列写入数据,那么应该解除一个任务的阻塞,因为在该函数退出后可以向队列写入数据。 */
            if( listLIST_IS_EMPTY( &( pxQueue->xTasksWaitingToSend ) ) == pdFALSE )
            {
                if( xTaskRemoveFromEventList( &( pxQueue->xTasksWaitingToSend ) ) != pdFALSE )
                {
                    queueYIELD_IF_USING_PREEMPTION();
                }
                else
                {
                    mtCOVERAGE_TEST_MARKER();
                }
            }
            else
            {
                mtCOVERAGE_TEST_MARKER();
            }
        }
        else
        {
            /* 确保事件队列以正确状态开始。 */
            vListInitialise( &( pxQueue->xTasksWaitingToSend ) );
            vListInitialise( &( pxQueue->xTasksWaitingToReceive ) );
        }
    }
    taskEXIT_CRITICAL();

    /* 返回一个值是为了与早期版本的调用语义保持一致。 */
    return pdPASS;
}

  1. Start:函数开始执行。

  2. CheckQueue:检查传入的队列指针是否有效。

  3. EnterCritical:进入临界区,防止多任务并发访问。

  4. ResetQueueState:重置队列的尾指针、等待消息数、写指针、读指针、接收锁和发送锁。

  5. CheckNewQueue:判断 xNewQueue 是否为 pdFALSE

  6. CheckSendTasks:如果 xNewQueue 为 pdFALSE,检查发送任务等待列表是否为空。

  7. UnblockSendTask:如果发送任务等待列表不为空,解除一个发送任务的阻塞。

  8. CoverageTestMarker:如果发送任务等待列表为空,执行覆盖率测试标记。

  9. InitializeLists:如果 xNewQueue 为 pdTRUE,初始化队列的任务等待列表。

  10. ExitCritical:退出临界区,恢复任务调度。

  11. ReturnPass:返回 pdPASS,表示操作成功。

函数 xQueueGenericReset()复位队列的操作也是复位队列的结构体中的成员变量。

函数xQueueCreate()创建队列的整个流程,大致就是先为队列申请内存空间,然后初始化队列结构体中的成员变量 。

静态创建xQueueCreateStatic()

QueueHandle_t xQueueGenericCreateStatic( const UBaseType_t uxQueueLength,
                                         const UBaseType_t uxItemSize,
                                         uint8_t * pucQueueStorage,
                                         StaticQueue_t * pxStaticQueue,
                                         const uint8_t ucQueueType )
{
    Queue_t * pxNewQueue;

    configASSERT( uxQueueLength > ( UBaseType_t ) 0 );

    /* 必须提供 StaticQueue_t 结构和队列存储区域。 */
    configASSERT( pxStaticQueue != NULL );

    /* 如果项目大小不为 0,则应提供队列存储区域;如果项目大小为 0,则不应提供队列存储区域。 */
    configASSERT( !( ( pucQueueStorage != NULL ) && ( uxItemSize == 0 ) ) );
    configASSERT( !( ( pucQueueStorage == NULL ) && ( uxItemSize != 0 ) ) );

    #if ( configASSERT_DEFINED == 1 )
        {
            /* 检查用于声明 StaticQueue_t 或 StaticSemaphore_t 变量的结构的大小是否等于实际队列和信号量结构的大小。 */
            volatile size_t xSize = sizeof( StaticQueue_t );
            configASSERT( xSize == sizeof( Queue_t ) );
            ( void ) xSize; /* 当 configASSERT() 未定义时,保持 lint 安静。 */
        }
    #endif /* configASSERT_DEFINED */

    /* 传递了一个静态分配的队列的地址,使用它。队列存储区域的地址也已传递,但已设置。 */
    pxNewQueue = ( Queue_t * ) pxStaticQueue; /*lint !e740 !e9087 不寻常的强制转换是可以的,因为这些结构设计为具有相同的对齐方式,并且大小由断言检查。 */

    if( pxNewQueue != NULL )
    {
        #if ( configSUPPORT_DYNAMIC_ALLOCATION == 1 )
            {
                /* 队列可以静态或动态分配,因此注意此队列是静态分配的,以防稍后删除队列。 */
                pxNewQueue->ucStaticallyAllocated = pdTRUE;
            }
        #endif /* configSUPPORT_DYNAMIC_ALLOCATION */

        prvInitialiseNewQueue( uxQueueLength, uxItemSize, pucQueueStorage, ucQueueType, pxNewQueue );
    }
    else
    {
        traceQUEUE_CREATE_FAILED( ucQueueType );
        mtCOVERAGE_TEST_MARKER();
    }

    return pxNewQueue;
}

xQueueGenericCreateStatic 函数用于创建一个静态分配的队列。具体功能如下:

  1. 参数检查

    • 确保队列长度大于0。

    • 确保提供了 StaticQueue_t 结构和队列存储区域。

    • 确保项目大小和存储区域匹配。

  2. 断言检查

    • 确保 StaticQueue_t 结构的大小与实际队列结构的大小一致。

  3. 初始化队列

    • 将 StaticQueue_t 结构转换为 Queue_t 结构。

    • 调用 prvInitialiseNewQueue 函数初始化队列。

  4. 失败处理

    • 如果参数无效,记录队列创建失败并返回 NULL


原文地址:https://blog.csdn.net/weixin_52849254/article/details/143582151

免责声明:本站文章内容转载自网络资源,如本站内容侵犯了原著者的合法权益,可联系本站删除。更多内容请关注自学内容网(zxcms.com)!