FreeRTOS简单内核实现2 双向链表

freertos · 浏览次数 : 0

小编点评

**1. 数据结构** FreeRTOS 中的链表使用结构体 `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`：链表容器，通常是一个任务控制块 (TCB)。 - `listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE`：检查链表项数据完整性的值（这是 `xLIST_ITEM` 结构中的第二个检查值）。 `XMINI_LIST_ITEM` 是链表项的缩减版，专门用于表示链表尾节点。在 32 位 MCU 上，它比普通链表项节省了 8 个字节（两个指针）。 `xLIST` 是由多个链表项构成的链表，用于区分不同任务状态或任务优先级。例如，就绪状态的任务放在就绪链表中，阻塞状态的任务放在阻塞链表中。 **2. 操作链表** 链表的初始化、插入、移除等操作通过以下函数实现： - `vListInitialiseItem()`：初始化链表项，设置其 `pxContainer` 成员为 `NULL`。 - `vListInitialise()`：初始化整个链表，设置链表指针 `pxIndex` 指向尾链表项，设置尾链表项的排序值为最大值，并将尾链表项的前后链表项指针均指向自己。 - `vListInsertEnd()`：将一个链表项插入到链表当前指针 `pxIndex` 指向的链表项前面。 - `vListInsert()`：将一个链表项按照链表中所有链表项的 `xItemValue` 值大小升序插入链表中。 - `uxListRemove()`：从链表中移除指定的链表项。 此外，还有一些宏函数用于设置和获取链表项的 `pxOwner`、`xValue` 成员，以及链表中头链表项的 `xItemValue` 成员、链表项地址、链表当前长度等。 链表的移植过程包括替换 FreeRTOS 内核中的 `list.c` 和 `list.h` 文件，统一基本类型定义，删除测试函数和特权函数宏，以及编译和测试工程以确保正确性。

正文

FreeRTOS Kernel V10.3.1

FreeRTOS 的 list.c / list.h 文件中有 3 个数据结构、2 个初始化函数、2 个插入函数、1 个移除函数和一些宏函数，链表是 FreeRTOS 中的重要数据结构，下述 “1、数据结构” 和 “2、操作链表” 两个小节内容主要对其原理进行讲解

1、数据结构

1.1、xLIST_ITEM

链表项，即节点，通常用链表项来表示一个任务

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;
    // 记录此 链表项 归谁拥有，通常是 TCB (任务控制块)
    void * pvOwner;
    // 拥有该 链表项 的 链表 
    struct xLIST * configLIST_VOLATILE pxContainer;
    // 检验一个 链表项 数据是否完整
    listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE
};
typedef struct xLIST_ITEM ListItem_t;

1.2、XMINI_LIST_ITEM

MINI 链表项，链表项的缩减版，专门用于表示链表尾节点，在 32 位 MCU 上不启用链表项数据完整性校验的情况下相比于普通的链表项节省了 8 个字节（两个指针）

struct xMINI_LIST_ITEM
{
	// 检验一个 MINI链表项 数据是否完整
    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;

1.3、xLIST

由多个链表项构成的链表，常用于区分不同任务状态或任务优先级，比如就绪状态的任务放在就绪链表中，阻塞状态的任务放在阻塞链表中，方便任务管理

typedef struct xLIST
{
	// 检验一个 链表 数据是否完整
    listFIRST_LIST_INTEGRITY_CHECK_VALUE 
    // 记录 链表 中 链表项 数目
    volatile UBaseType_t uxNumberOfItems;
    // 遍历 链表 的指针
    ListItem_t * configLIST_VOLATILE pxIndex;
    // 使用 MINI链表项 表示 链表尾部
    MiniListItem_t xListEnd;
    // 检验一个 链表 数据是否完整
    listSECOND_LIST_INTEGRITY_CHECK_VALUE
} List_t;

2、操作链表

注意：由于不涉及数据校验完整性，因此下述函数中关于校验的所有部分将被删除

2.1、初始化

2.1.1、vListInitialiseItem( )

初始化链表项函数

将链表项的 pxContainer 成员设置为 NULL ，因为初始化的时候该链表项未被任何链表包含

void vListInitialiseItem( ListItem_t * const pxItem )  
{  
    // 确保链表项未被记录在链表中
    pxItem->pxContainer = NULL;
}

2.1.2、vListInitialise( )

初始化链表函数，具体步骤如下

  1. 将链表当前指针 pxIndex 指向尾链表项 xListEnd
  2. 确保尾链表项 xListEnd 被排在链表最尾部
  3. 将尾链表项 xListEnd 的前/后链表项指针均指向自己，因为初始化链表时只有尾链表项
  4. 链表中有 0 个链表项
void vListInitialise( List_t * const pxList )  
{  
    // 链表当前指针指向 xListEnd
    pxList->pxIndex = ( ListItem_t * ) &( pxList->xListEnd );
    
    // 设置链表尾链表项排序值为最大， 保证 xListEnd 会被放在链表的尾部
    pxList->xListEnd.xItemValue = portMAX_DELAY;
  
    // 尾链表项 xListEnd 的前/后链表项指针均指向自己
    pxList->xListEnd.pxNext = ( ListItem_t * ) &( pxList->xListEnd );
    pxList->xListEnd.pxPrevious = ( ListItem_t * ) &( pxList->xListEnd );
	// 初始化时链表中有 0 个链表项
    pxList->uxNumberOfItems = ( UBaseType_t ) 0U;
}

2.2、插入

2.2.1、vListInsertEnd( )

将一个链表项插入到链表当前指针 pxIndex 指向的链表项前面，具体步骤如下

  1. 改变要插入链表项自身的 pxNext 和 pxPrevious
  2. 改变前一个链表项（也就是 pxIndex 指向的链表项的 Previous）的 pxNext
  3. 改变后一个链表项（也就是 pxIndex 指向的链表项）的 pxPrevious
void vListInsertEnd( List_t * const pxList, ListItem_t * const pxNewListItem )  
{
	// 获取链表中当前指针 pxIndex 位置
	ListItem_t * const pxIndex = pxList->pxIndex;
	 
	// 1. 改变自身 pxNext 和 pxPrevious
    pxNewListItem->pxNext = pxIndex;
    pxNewListItem->pxPrevious = pxIndex->pxPrevious;
    
	// 2. 改变前一个链表项的 pxNext
    pxIndex->pxPrevious->pxNext = pxNewListItem;
    // 3. 改变后一个链表项的 pxPrevious
    pxIndex->pxPrevious = pxNewListItem;
	  
    // 标记新插入的链表项所在的链表 
    pxNewListItem->pxContainer = pxList;
	// 链表数量增加一
    ( pxList->uxNumberOfItems )++;
}

为方便绘图演示，将链表的结构在图上做了简化，具体如下图所示

注意：这里 pxList->pxIndex 自初始化以来从未修改过，保持指向链表 xListEnd 链表项，下图所有演示中，橙色虚线表示该步骤做了修改，黑色实线表示与上一步骤相比无修改

插入一个链表项

插入第二个链表项

插入第三个链表项

插入第四个链表项

2.2.2、vListInsert( )

将一个链表项按照链表中所有链表项的 xItemValue 值大小升序插入链表中，具体步骤如下

  1. 找到应该插入的位置（应该插入到 pxIterator 的后面）
  2. 改变要插入链表项自身 pxNext 和 pxPrevious
  3. 改变后一个链表项的 pxPrevious
  4. 改变前一个链表项的 pxNext （也即 pxIterator 指向的链表项的 pxNext）
void vListInsert( List_t * const pxList, ListItem_t * const pxNewListItem )  
{
	ListItem_t *pxIterator;
	// 记录要插入的链表项的排序值
	const TickType_t xValueOfInsertion = pxNewListItem->xItemValue;
	
	// 如果新插入的链表项排序值为最大值，直接插到尾节点 xListEnd 的前面
	if( xValueOfInsertion == portMAX_DELAY )  
	{  
	    pxIterator = pxList->xListEnd.pxPrevious;  
	}
	else  
	{
		/*
		1. 遍历链表，将当前链表项 pxIterator 与要插入的新的链表项 pxNewListItem 
		的 xItemValue 值比较，直到 pxIterator 的 xItemValue 大于 pxNewListItem 
		的 xItemValue 值，此时 pxNewListItem 应该插入到 pxIterator 的后面
		*/
		for( pxIterator = ( ListItem_t * ) &( pxList->xListEnd ); 
			 pxIterator->pxNext->xItemValue <= xValueOfInsertion; 
			 pxIterator = pxIterator->pxNext ){}
	}
	// 2. 改变要插入链表项自身 pxNext 和 pxPrevious
	pxNewListItem->pxNext = pxIterator->pxNext;
	pxNewListItem->pxPrevious = pxIterator;
	// 3. 改变后一个链表项的 pxPrevious
	pxNewListItem->pxNext->pxPrevious = pxNewListItem;
	// 4. 改变前一个链表项的 pxNext
	pxIterator->pxNext = pxNewListItem;
	
	// 标记新插入的链表项所在的链表
	pxNewListItem->pxContainer = pxList;
	// 链表数量增加一
	( pxList->uxNumberOfItems )++;
}

2.3、移除

2.3.1、uxListRemove( )

从链表中移除指定的链表项，具体步骤如下

  1. 改变后一个链表项的 pxPrevious
  2. 改变前一个链表项的 pxNext
UBaseType_t uxListRemove( ListItem_t * const pxItemToRemove )  
{  
	List_t * const pxList = pxItemToRemove->pxContainer;  
	
	// 1. 改变后一个链表项 pxPrevious
    pxItemToRemove->pxNext->pxPrevious = pxItemToRemove->pxPrevious;
    // 2. 改变前一个链表项 pxNext
    pxItemToRemove->pxPrevious->pxNext = pxItemToRemove->pxNext;
	  
    // 确保索引指向有效的项目
    if( pxList->pxIndex == pxItemToRemove )  
    {  
       pxList->pxIndex = pxItemToRemove->pxPrevious;  
    }
	
	// 从链表中移除链表项后，该链表项不属于任何链表
    pxItemToRemove->pxContainer = NULL;  
    // 链表中链表项的数量减一
    ( pxList->uxNumberOfItems )--;  
	
	// 返回链表中链表项的数量
    return pxList->uxNumberOfItems;  
}

2.4、宏函数

2.4.1、设置相关

// 设置 pxListItem 的 pxOwner 成员
#define listSET_LIST_ITEM_OWNER( pxListItem, pxOwner )

// 设置 pxListItem 的 xValue 成员值
#define listSET_LIST_ITEM_VALUE( pxListItem, xValue )

2.4.2、获取相关

// 获取 pxListItem 的 pxOwner 成员
#define listGET_LIST_ITEM_OWNER( pxListItem )

// 获取 pxListItem 的 xValue 成员值
#define listGET_LIST_ITEM_VALUE( pxListItem )

// 获取链表中头链表项的 xItemValue 成员值
#define listGET_ITEM_VALUE_OF_HEAD_ENTRY( pxList )

// 获取链表中头链表项地址
#define listGET_HEAD_ENTRY( pxList )

// 获取某个链表项的下一个链表项地址
#define listGET_NEXT( pxListItem )

// 获取链表中 xListEnd 的地址
#define listGET_END_MARKER( pxList )

// 获取链表当前长度
#define listCURRENT_LIST_LENGTH( pxList )

// 将链表中 pxIndex 指向下一个链表项，用于获取下一个链表项（任务）
#define listGET_OWNER_OF_NEXT_ENTRY( pxTCB, pxList )

// 获取链表中头链表项的 pvOwner 成员
#define listGET_OWNER_OF_HEAD_ENTRY( pxList )

// 获取链表项的 pxContainer 成员
#define listLIST_ITEM_CONTAINER( pxListItem )

2.4.3、判断相关

// 判断链表是否为空
#define listLIST_IS_EMPTY( pxList )

// 判断链表项是否和链表匹配（链表项是否在该链表中）
#define listIS_CONTAINED_WITHIN( pxList, pxListItem )

// 判断链表是否被初始化
#define listLIST_IS_INITIALISED( pxList )

3、链表移植

下面直接将 FreeRTOS 内核中 list.c / list.h 文件移植到自己的工程中使用（当然，如果你已经懂得双向链表数据结构的原理，你也可以构建属于你自己的 list.c / list.h 文件）

移植可以总结为以下 4 个步骤

  1. 用 FreeRTOS Kernel V10.3.1 内核中 list.c / list.h 替换掉 RTOS 文件夹中的同名文件
  2. 在 portMacro.h 中统一一些用到基本类型
/* portMacro.h */
#include <stdint.h>

#define port_CHAR                   char
#define port_FLOAT                  float
#define port_DOUBLE                 double
#define port_LONG                   long
#define port_SHORT                  short
#define port_STACK_TYPE             unsigned int
#define port_BASE_TYPE              long

typedef port_STACK_TYPE             StackType_t;
typedef long                        BaseType_t;
typedef unsigned long               UBaseType_t;

typedef port_STACK_TYPE*            StackType_p;
typedef long*                       BaseType_p;
typedef unsigned long*              UBaseType_p;


#if(configUSE_16_BIT_TICKS == 1)
    typedef uint16_t                TickType_t;
    #define portMAX_DELAY           (TickType_t) 0xffff
#else
    typedef uint32_t                TickType_t;
    #define portMAX_DELAY           (TickType_t) 0xffffffffUL
#endif

#define pdFALSE                     ((BaseType_t) 0)
#define pdTRUE                      ((BaseType_t) 1)
#define pdPASS                      (pdTRUE)
#define pdFAIL                      (pdFALSE)

configUSE_16_BIT_TICKS 是一个宏，用于 TickType_t 类型位数，具体定义如下

/* FreeRTOSConfig.h */
// 设置 TickType_t 类型位 16 位 
#define configUSE_16_BIT_TICKS                  0
  1. 删除掉 list.c 文件中所有的 mtCOVERAGE_TEST_DELAY() 测试函数
  2. 删除掉 list.h 文件中所有的 PRIVILEGED_FUNCTION 宏

完成后编译工程应该不会出现错误，这样实现 RTOS 简单内核关键的双链表数据结构就完成了

freertos

与FreeRTOS简单内核实现2 双向链表相似的内容：

FreeRTOS简单内核实现2 双向链表

FreeRTOS 的 list.c / list.h 文件中有 3 个数据结构、2 个初始化函数、2 个插入函数、1 个移除函数和一些宏函数，链表是 FreeRTOS 中的重要数据结构

freertos
0
FreeRTOS简单内核实现7 阻塞链表

0、思考与回答 0.1、思考一 如何处理进入阻塞状态的任务？ 为了让 RTOS 支持多优先级，我们创建了多个就绪链表（数组形式），用每一个就绪链表表示一个优先级，对于阻塞状态的任务显然要从就绪链表中移除，但是阻塞状态的任务并不是永久阻塞了，等待一段时间后应该从阻塞状态恢复，所以我们需要创建一个阻塞链

freertos
0
FreeRTOS简单内核实现6 优先级

0、思考与回答 0.1、思考一 如何实现 RTOS 内核支持多优先级？ 因为不支持优先级，所以所有的任务都插入了一个名为 pxReadyTasksLists 的就绪链表中，相当于所有任务的优先级都是一致的，那如果我们创建一个就绪链表数组，数组下标代表优先级，优先级为 x 的任务就插入到 pxRead

freertos
0
FreeRTOS简单内核实现5 阻塞延时

0、思考与回答 0.1、思考一 为什么 FreeRTOS简单内核实现3 任务管理 文章中实现的 RTOS 内核不能看起来并行运行呢？ Task1 延时 100ms 之后执行 taskYIELD() 切换到 Task2，Task2 延时 500ms 之后执行 taskYIELD() 再次切换 Task

freertos
11
FreeRTOS简单内核实现3 任务管理

0、思考与回答 0.1、思考一 对于 Cotex-M4 内核的 MCU 在发生异常/中断时，哪些寄存器会自动入栈，哪些需要手动入栈？ 会自动入栈的寄存器如下 R0 - R3：通用寄存器 R12：通用寄存器 LR （Link Register）：链接寄存器，保存返回地址 PC （Program Cou

freertos
0
# 热门排行
微软 New Bing AI 申请与使用保姆级教程（免魔法） ChatGPT API使用介绍 ChatGPT开发实战 一篇带你了解如何使用纯前端类Excel表格构建现金流量表 手把手教你玩转 Excel 数据透视表 为什么 C# 可能是最好的第一编程语言 .NET 入门到高级路线 提高工作效率的神器：基于前端表格实现Chrome Excel扩展插件 React + Springboot + Quartz，从0实现Excel报表自动化 用Echarts实现前端表格引用从属关系可视化
© PmDaddy. 2023 PmDaddy教程网 All rights reserved.