FreeRTOS学习（十一）：列表和列表项详解（一篇讲懂！简单易懂！）

发布于：2025-03-28 ⋅ 阅读:(24) ⋅ 点赞:(0)

FreeRTOS学习（十一）：列表和列表项详解

文章目录

列表简介

FreeRTOS中的列表是一个重要的数据结构，它在概念上类似于链表。它是一个双向环形链表结构，具有以下特点：

  • 列表项之间的地址是非连续的，是通过指针人为连接到一起的
  • 列表项的数目可以动态改变，随时可以添加或删除
  • 非常适合管理OS中数量不确定且状态会发生改变的任务

一、列表结构详解

1.1 列表(List)结构定义

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;

主要成员说明：

  • uxNumberOfItems：记录列表中列表项的个数（不包含xListEnd）
  • pxIndex：用于指向列表中的某个列表项，通常用于遍历列表
  • xListEnd：一个迷你列表项，始终位于列表末尾

1.2 列表项(List 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 /* 指向上一个列表项 */
    void * pvOwner                             /* 列表项的拥有者 */
    struct xLIST * configLIST_VOLATILE pxContainer;    /* 列表项所在列表 */
    listSECOND_LIST_ITEM_INTEGRITY_CHECK_VALUE /* 用于检测列表项的数据完整性 */
};
typedef struct xLIST_ITEM ListItem_t;

主要成员说明：

  1. xItemValue：列表项的值，通常用于按优先级对列表2项进行排序
  2. pxNext和pxPrevious：分别指向下一个和上一个列表项
  3. pvOwner：指向列表项的拥有者（通常是任务控制块）
  4. pxContainer：指向该列表项所属的列表

二、列表的工作原理

列表结构

List_t 是整个列表的"管理者"
uxNumberOfItems：记录列表中有多少个项目（就像购物袋里有几件商品）
pxIndex：像一个指针，指向当前正在查看的项目
xListEnd：列表的结束标记，永远指向最后一个位置
在这里插入图片描述

列表初始化

像一个新开的班级：

刚开始时是空的
只有一个班级标志（结束标记）
准备好接收新成员
项目数从0开始计数
在这里插入图片描述

  • uxNumberOfItems被初始化为0
  • xListEnd项被初始化并放置在列表末尾
  • 所有新列表项通过pxNext和pxPrevious指针连接成双向环形链表

列表项结构

列表项详细结构

在这里插入图片描述

就像一个人的身份信息卡：

  • xItemValue：重要程度（优先级），像是紧急程度
  • pxNext：指向下一个伙伴
  • pxPrevious：指向上一个伙伴
  • pvOwner：这个项目属于谁（比如哪个任务）
  • pxContainer：属于哪个列表（比如在哪个班级）

这样的设计让系统能够：

  1. 快速找到最高优先级的任务（通过xItemValue）
  2. 方便地在列表中移动（通过pxNext和pxPrevious）
  3. 知道每个列表项属于哪个任务（通过pvOwner）
  4. 知道列表项在哪个列表中（通过pvContainer）

这就像一个设计精良的学生证：

  • 不仅有学号（优先级）
  • 还能找到前后的同学（双列表-下面会讲）
  • 知道是谁的证件（任务归属）
  • 知道属于哪个学校（列表归属）

就绪列表

双列表结构
在这里插入图片描述

在这里插入图片描述

  • 列表头（粉色）：标记列表的起始位置
  • 任务1-3（蓝色）：具有相同优先级3的任务
  • 结束标记（黄色）：列表的结束位置，同时连接回列表头形成环
  • 所有任务按优先级排序，相同优先级的任务排在一起
  • 形成环形结构，便于循环调度

上面那图只有一个箭头但其实是双链表结构，可以看看下面的解释

双链表好处

在这里插入图片描述

  1. 方便走动：
  • 可以向前走（找下一个任务）
  • 也可以向后走（找上一个任务）
  • 不会迷路，因为是个圈
  1. 容易插入新同学：
  • 比如小李要插入到小明和小红之间
  • 只需要让小李拉住小明和小红
  • 小明和小红也拉住小李
  • 就完成了插入
  1. 容易删除：
  • 如果小红生病请假
  • 小明直接拉住小刚的手
  • 小刚直接拉住小明的手
  • 小红就可以安心回家了

这样的设计让FreeRTOS能够：

  1. 快速找到该执行的任务
  2. 方便地添加新任务
  3. 方便地删除完成的任务
  4. 在任务之间灵活切换

三、FreeRTOS列表的插入和移除机制

插入函数

vListInsert() - 按值排序插入

void vListInsert(List_t *pxList, ListItem_t *pxNewListItem)

在这里插入图片描述
在这里插入图片描述

  • 从列表头开始遍历
  • 找到第一个xItemValue大于待插入项的位置
  • 在该位置之前插入新项
  • 适用于优先级队列

vListInsertEnd() - 末尾插入

void vListInsertEnd(List_t *pxList, ListItem_t *pxNewListItem)

在这里插入图片描述
在这里插入图片描述

  • 直接插入到列表末尾（pxIndex指向的位置之前）
  • 常用于FIFO队列

移除函数

uxListRemove() - 从列表中移除项

UBaseType_t uxListRemove(ListItem_t *pxItemToRemove)

在这里插入图片描述
在这里插入图片描述

  • 调整前后项的指针连接
  • 清除被移除项的pvContainer指针
  • 返回列表中剩余项目数

四、实验结果解析

主要代码（正点原子demo）

void task2(void *pvParameters)
{
   
    vListInitialise(&TestList);
		vListInitialiseItem(&ListItem1);
		vListInitialiseItem(&ListItem2);
		vListInitialiseItem(&ListItem3);
	ListItem1.xItemValue=40;
	ListItem2.xItemValue=60;
	ListItem3.xItemValue=50;
		    while (key_scan(0) != KEY0_PRES)
    {
        vTaskDelay(10);
    }
  /* 第二步：打印列表和其他列表项的地址 */
    printf("\r\n/**************第二步：打印列表和列表项的地址**************/\r\n");
    printf("项目\t\t\t地址\r\n");
    printf("TestList\t\t0x%p\t\r\n", &TestList);
    printf("TestList->pxIndex\t0x%p\t\r\n", TestList.pxIndex);
    printf("TestList->xListEnd\t0x%p\t\r\n", (&TestList.xListEnd));
    printf("ListItem1\t\t0x%p\t\r\n", &ListItem1);
    printf("ListItem2\t\t0x%p\t\r\n", &ListItem2);
    printf("ListItem3\t\t0x%p\t\r\n", &ListItem3);
    printf("/**************************结束***************************/\r\n");
 

    /* 第三步：列表项1插入列表 */
    printf("\r\n/*****************第三步：列表项1插入列表******************/\r\n");
    vListInsert((List_t*    )&TestList,         /* 列表 */
                (ListItem_t*)&ListItem1);       /* 列表项 */
    printf("项目\t\t\t\t地址\r\n");
    printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
    printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
    printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
    printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
    printf("/**************************结束***************************/\r\n");
  

    /* 第四步：列表项2插入列表 */
    printf("\r\n/*****************第四步：列表项2插入列表******************/\r\n");
    vListInsert((List_t*    )&TestList,         /* 列表 */
                (ListItem_t*)&ListItem2);       /* 列表项 */
    printf("项目\t\t\t\t地址\r\n");
    printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
    printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
    printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
    printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
    printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
    printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
    printf("/**************************结束***************************/\r\n");
  

    
    /* 第五步：列表项3插入列表 */
    printf("\r\n/*****************第五步：列表项3插入列表******************/\r\n");
    vListInsert((List_t*    )&TestList,         /* 列表 */
                (ListItem_t*)&ListItem3);       /* 列表项 */
    printf("项目\t\t\t\t地址\r\n");
    printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
    printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
    printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
    printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
    printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
    printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
    printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
    printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
    printf("/**************************结束***************************/\r\n");
   

    
    /* 第六步：移除列表项2 */
    printf("\r\n/*******************第六步：移除列表项2********************/\r\n");
    uxListRemove((ListItem_t*   )&ListItem2);   /* 移除列表项 */
    printf("项目\t\t\t\t地址\r\n");
    printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
    printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
    printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
    printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
    printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
    printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
    printf("/**************************结束***************************/\r\n");
  

    
    /* 第七步：列表末尾添加列表项2 */
    printf("\r\n/****************第七步：列表末尾添加列表项2****************/\r\n");
    vListInsertEnd((List_t*     )&TestList,     /* 列表 */
                   (ListItem_t* )&ListItem2);   /* 列表项 */
    printf("项目\t\t\t\t地址\r\n");
    printf("TestList->pxIndex\t\t0x%p\r\n", TestList.pxIndex);
    printf("TestList->xListEnd->pxNext\t0x%p\r\n", (TestList.xListEnd.pxNext));
    printf("ListItem1->pxNext\t\t0x%p\r\n", (ListItem1.pxNext));
    printf("ListItem2->pxNext\t\t0x%p\r\n", (ListItem2.pxNext));
    printf("ListItem3->pxNext\t\t0x%p\r\n", (ListItem3.pxNext));
    printf("TestList->xListEnd->pxPrevious\t0x%p\r\n", (TestList.xListEnd.pxPrevious));
    printf("ListItem1->pxPrevious\t\t0x%p\r\n", (ListItem1.pxPrevious));
    printf("ListItem2->pxPrevious\t\t0x%p\r\n", (ListItem2.pxPrevious));
    printf("ListItem3->pxPrevious\t\t0x%p\r\n", (ListItem3.pxPrevious));
    printf("/************************实验结束***************************/\r\n");
    while (key_scan(0) != KEY0_PRES)
    {
        vTaskDelay(10);
    }
    while (1)
    {
			printf("2222");
			vTaskDelay(1000);

    }
}

解析输出结果

第二步：打印初始地址

/**************第二步：打印列表和列表项的地址**************/
项目			地址
TestList		0x200000d0	
TestList->pxIndex	0x200000d8	
TestList->xListEnd	0x200000d8	
ListItem1		0x200000e4	
ListItem2		0x200000f8	
ListItem3		0x2000010c	
/**************************结束***************************/

这里可以看到：

  • TestList结构体本身位于0x200000d0
  • TestList的xListEnd成员位于0x200000d8
  • pxIndex指向xListEnd，所以也是0x200000d8
  • 三个ListItem分别位于0x200000e4、0x200000f8、0x2000010c
    在这里插入图片描述

第三步：插入ListItem1

vListInsert(&TestList, &ListItem1);vListInsert((List_t*    )&TestList,         /* 列表 */
                (ListItem_t*)&ListItem1);       /* 列表项 */

结果为

/*****************第三步：列表项1插入列表******************/
项目				地址
TestList->xListEnd->pxNext	0x200000e4
ListItem1->pxNext		0x200000d8
TestList->xListEnd->pxPrevious	0x200000e4
ListItem1->pxPrevious		0x
200000d8
/**************************结束***************************/

插入后的结果显示：

  • xListEnd.pxNext = 0x200000e4 (指向ListItem1)
  • ListItem1.pxNext = 0x200000d8 (指向xListEnd)
  • xListEnd.pxPrevious = 0x200000e4 (指向ListItem1)
  • ListItem1.pxPrevious = 0x200000d8 (指向xListEnd)

此时形成了一个只有一个节点的循环双向链表，ListItem1与xListEnd互相指向。
在这里插入图片描述

第四步：插入ListItem2

vListInsert((List_t*    )&TestList,         /* 列表 */
                (ListItem_t*)&ListItem2);       /* 列表项 */

结果为

/*****************第四步：列表项2插入列表******************/
项目				地址
TestList->xListEnd->pxNext	0x200000e4
ListItem1->pxNext		0x200000f8
ListItem2->pxNext		0x200000d8
TestList->xListEnd->pxPrevious	0x200000f8
ListItem1->pxPrevious		0x200000d8
ListItem2->pxPrevious		0x200000e4
/**************************结束***************************/

插入后：

  • xListEnd.pxNext = 0x200000e4 (仍指向ListItem1)
  • ListItem1.pxNext = 0x200000f8 (指向ListItem2)
  • ListItem2.pxNext = 0x200000d8 (指向xListEnd)
  • xListEnd.pxPrevious = 0x200000f8 (指向ListItem2)
  • ListItem1.pxPrevious = 0x200000d8 (指向xListEnd)
  • ListItem2.pxPrevious = 0x200000e4 (指向ListItem1)

形成了顺序为：xListEnd -> ListItem1 -> ListItem2 -> xListEnd的循环。
在这里插入图片描述
到七步再显示结果

第五步：插入ListItem3

插入后形成：xListEnd -> ListItem1 -> ListItem3 -> ListItem2 -> xListEnd
可以从地址值看出链接关系：

  • ListItem1.pxNext = 0x2000010c (ListItem3)
  • ListItem3.pxNext = 0x200000f8 (ListItem2)
  • ListItem2.pxNext = 0x200000d8 (xListEnd)
    在这里插入图片描述

第六步：移除ListItem2

移除后：

  • ListItem1.pxNext = 0x2000010c (直接指向ListItem3)
  • ListItem3.pxNext = 0x200000d8 (指向xListEnd)
  • ListItem2的链接被断开

在这里插入图片描述

第七步：末尾添加ListItem2

vListInsertEnd(&TestList, &ListItem2);
在末尾添加后：

  • ListItem1.pxNext = 0x2000010c (ListItem3)
  • ListItem3.pxNext = 0x200000f8 (ListItem2)
  • ListItem2.pxNext = 0x200000d8 (xListEnd)

最终形成：xListEnd -> ListItem1 -> ListItem3 -> ListItem2 -> xListEnd
在这里插入图片描述

/****************第七步：列表末尾添加列表项2****************/
项目				地址
TestList->pxIndex		0x200000d8
TestList->xListEnd->pxNext	0x200000e4
ListItem1->pxNext		0x2000010c
ListItem2->pxNext		0x200000d8
ListItem3->pxNext		0x200000f8
TestList->xListEnd->pxPrevious	0x200000f8
ListItem1->pxPrevious		0x200000d8
ListItem2->pxPreviou
s		0x2000010c
ListItem3->pxPrevious		0x200000e4
/************************实验结束***************************/

总结

FreeRTOS中的列表和列表项是一个设计精巧的数据结构，它为任务管理提供了灵活且高效的解决方案。通过双向环形链表的设计，使得列表的操作既简单又高效，非常适合用于管理操作系统中动态变化的任务。

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布