操作系统 EidosOS

EidosOS实现（2）-任务管理结构的演进

Posted by WHX on March 26, 2026

EidosOS 实现之任务管理结构的演进——从数组到链表

从零实现实时操作系统EidosOS系列！

1、摘要

​ 在实现信号量之前，必须先解决任务的组织方式问题，即如何用合适的数据结构表达任务状态。这一问题的解决，正是从全局任务表向链表调度结构转变的核心动机。

2、单数组的问题

​ 在上一篇文章中，我们通过全局指针数组统一管理所有任务的TCB。在这种实现方式下，无论是在时钟中断还是任务调度算法中都需要遍历整个数组，并通过一系列判断条件来确定每个任务的状态，例如是否处于延时、是否等待事件等。这种设计在任务数量较少的时候尚可工作，一旦任务数量增加，问题就会随之显现。表面上，频繁的数组遍历会带来一定的性能开销，但这不是最关键的问题。最根本的缺陷在于：所有任务被放在同一个结构中，不同状态间缺乏清晰的划分，导致系统必须依赖大量条件分支判断当前任务的状态。

​ 随着阻塞类型增加，这种基于“状态判断”的实现方式会迅速变得复杂，甚至难以维护。因为调度器需要理解所有可能的状态组合，从而不断地增大判断逻辑，使得系统失去可扩展性。

3、多链表的优势

​ 前面讲最根本的问题是一个结构管理多个不同的状态下的任务，如果换成单个链表，那意义不大，最多解决的是一点点的性能优化问题。所有多链表的实现其实重点在于多，多个结构管理多个不同状态下的任务（从这一点上看，多数组也是可以的）。链表的优点在于插入和删除的时间复杂度很低，而且从一个链表到另一个链表可以很清楚的表达出任务状态的变化

4、工程修改

4.1链表数据结构

​ 首先是定义数据结构和其操作函数，网上有很多，这里给出EidosOS的实现：

//list.h
typedef struct ListItem
{
    uint32_t value;
    struct ListItem *prev;
    struct ListItem *next;
    void *pvOwner;
    struct List *container;
} ListItem_t;

typedef struct List
{
    uint32_t itemNumber;
    ListItem_t *index;
    ListItem_t end;
} vList;

//list.c

#include <stdlib.h>
#include <string.h>
#include <stdio.h>  
#include "list.h"

vList delayList; // 任务延迟链表
vList readyList; // 就绪链表

//初始化节点
void vListItemInit(ListItem_t *node)
{
    node->value = 0;
    node->prev = NULL;
    node->next = NULL;
    node->pvOwner = NULL;
    node->container = NULL;
}

// 初始化链表
void vListInit(vList *list)
{
    list->itemNumber = 0;
    list->index = NULL;
    list->end.value = 0xFFFFFFFF; // 设置哨兵节点的值为最大
    list->end.prev = &list->end;   // 哨兵节点的前驱和后继都指向自己
    list->end.next = &list->end;
}

// 将节点插入链表尾部
void vListInsertEnd(vList *list, ListItem_t *node)
{
    node->prev = list->end.prev; // 新节点的前驱是当前尾节点
    node->next = &list->end;     // 新节点的后继是哨兵节点
    list->end.prev->next = node; // 当前尾节点的后继指向新节点
    list->end.prev = node;       // 哨兵节点的前驱指向新节点
    node->container = list;      // 设置节点所属链表
    list->itemNumber++;          // 链表元素数量加1
}

// 将节点按照值从大到小插入链表
void vListInsert(vList *list, ListItem_t *node)
{
    ListItem_t *current = list->end.next; // 从头节点开始遍历
    while (current != &list->end && current->value > node->value)
    {
        current = current->next; // 找到第一个值大于等于新节点的节点
    }
    // 将新节点插入到current之前
    node->prev = current->prev;
    node->next = current;
    current->prev->next = node;
    current->prev = node;
    node->container = list; // 设置节点所属链表
    list->itemNumber++;     // 链表元素数量加1
}

// 从链表中删除节点
void vListRemove(ListItem_t *node)
{
    node->prev->next = node->next; // 前驱节点的后继指向当前节点的后继
    node->next->prev = node->prev; // 后继节点的前驱指向当前节点的前驱
    node->container->itemNumber--;   // 链表元素数量减1
    node->container = NULL;          // 清除节点所属链表
}

// 获取链表头部节点
ListItem_t *vListGetHead(vList *list)
{
    if (list->itemNumber == 0)
    {
        return NULL; // 链表为空，返回NULL
    }
    return list->end.next; // 返回头节点（哨兵节点的后继）
}

​ 目前的实现中定义了两个链表，一个就绪链表存放就绪态的任务，一个延时链表存放调用TaskDelay函数的被阻塞的任务，后续添加其他阻塞原因时在增加实现。

​ TCB中添加链表节点，用于放入到两个链表中：

typedef struct TCB
{
    uint32_t *sp; // 堆栈指针，必须在第一个位置，以便在上下文切换时正确保存和恢复
    uint16_t tick_count; // 任务运行的系统滴答数
    int priority;
    task_state_t state;
    ListItem_t stateListItem; // 用于将任务添加到不同的状态链表中的节点
    ListItem_t eventListItem; // 用于将任务添加到事件链表中的节点
}TCB_t;

4.2初始化及创建任务

​ 初始化时要初始化两个链表：

//初始化链表
vListInit(&delayList);
vListInit(&readyList);

​ 修改创建任务的函数，之前创建好加入到全局数组中，现在直接添加到就绪链表中。

//初始化链表节点
void taskListItemInit(TCB_t *task)
{
    vListItemInit(&task->stateListItem);
    vListItemInit(&task->eventListItem);
    task->stateListItem.pvOwner = task; // 设置节点所属任务
    task->eventListItem.pvOwner = task; // 设置节点所属任务
    task->stateListItem.value = task->priority; // 将优先级作为节点值，便于排序
    task->eventListItem.value = 0; // 事件链表节点值暂
}

int task_init(void (*func)(void *), int priority, void *const pvParameters, uint32_t stackSize)
{
    // 创建新的任务控制块
    TCB_t *newTask = malloc(sizeof(TCB_t));
    if (newTask == NULL)
    {
        return -1;
    }
    // 分配任务栈
    uint32_t *stack = malloc(stackSize);
    if (stack == NULL)
    {
        free(newTask);
        return -1;
    }
    else
    {
        uint32_t stack_addr = (uint32_t)stack + stackSize;
        uint32_t *stack_top = (uint32_t *)stack_addr;
        // 初始化任务栈
        newTask->sp = myInitialiseStack(stack_top, func, pvParameters);
        newTask->state = READY;
        newTask->priority = priority;
        // 初始化链表节点
        taskListItemInit(newTask);
        // 插入就绪链表
        vListInsert(&readyList, &newTask->stateListItem);
    }
    return 0;
    
}

vListInsert算法根据节点的value值进行排序，在就绪链表中根据优先级排序，在延时链表中根据延时时间排序

4.3任务调度算法

​ 由于插入到链表中是按序插入的，所以调度时直接取链表头即可。优先级调度算法已经在插入链表时用到了。

void vTaskSwitchContext()
{
    //根据链表头部选择优先级最高的就绪任务
    if (readyList.itemNumber > 0)
    {
        ListItem_t *nextItem = readyList.end.next; // 就绪链表头部节点
        TCB_t *nextTask = (TCB_t *)nextItem->pvOwner; // 获取对应的任务控制块
        currentTCB = nextTask; // 切换到下一个任务
    }
    return;
}

4.4TaskDelay函数实现

​ 任务延时就是把TCB从就绪链表删除，然后添加到延时阻塞链表中：

void task_delay(uint32_t ticks)
{
    // 设置任务状态为阻塞
    currentTCB->state = BLOCKED;
    // 从就绪链表中移除当前任务
    vListRemove(&currentTCB->stateListItem);
    // 设置节点的延时值为绝对时间，便于在延迟链表中排序
    currentTCB->stateListItem.value = currentTicks + ticks;
    // 插入延迟链表，按照剩余时间排序
    vListInsert(&delayList, &currentTCB->stateListItem);
    // 切换到下一个任务
    taskYield();
}

这里的value值设置为绝对时间，而不是之前的delay值，因为之前是每次中断delay值减一判断是否为0，而现在是计数值每次中断加一判断是否与value值相等。

4.5SysTick中断

​ 在SysTick时钟中断服务函数中，也要修改对延时链表进行遍历，如果时间等于当前的Tick值，则从delay链表中删除，重新加入到就绪链表中：

void SysTick_Handler(void)
{
  HAL_IncTick();

  currentTicks++; // 系统滴答数加1
  // 超限清零
  if (currentTicks == 0xFFFFFFFF)
  {
    currentTicks = 0;
  }
  if (currentTCB != NULL)
  {
    currentTCB->tick_count++;
  }
  // 时间片切换
  if (currentTCB && currentTCB->tick_count >= 1000)
  {
    currentTCB->tick_count = 0;
    SCB->ICSR |= SCB_ICSR_PENDSVSET_Msk;
  }
  // 根据delayList中的任务延迟时间，更新任务状态
  ListItem_t *currentItem = delayList.end.next;
  while (currentItem != &delayList.end)
  {
    ListItem_t *next = currentItem->next;
    TCB_t *task = (TCB_t *)currentItem->pvOwner;
    if (currentTicks == task->stateListItem.value)
    {
      task->state = READY;
      // 从延迟链表中移除当前任务
      vListRemove(&task->stateListItem);
      // 设置优先级
      task->stateListItem.value = task->priority;
      // 插入就绪链表
      vListInsert(&readyList, &task->stateListItem);
      // 如果新就绪的任务优先级高于当前正在运行的任务，则触发 PendSV 进行任务切换
      if (task->priority > currentTCB->priority)
      {
        SCB->ICSR |= SCB_ICSR_PENDSVSET_Msk; // 触发 PendSV 进行任务切换
      }
    }
    currentItem = next;
  }
}

5、总结

​ 在本文中，从上一篇的全局指针数组出发，逐步演进到基于链表的任务调度结构，这一过程不仅仅是数据结构的替换，更是对整个操作系统的任务调度模型进行一次抽象升级。

​ 最初采用全局数组管理所有任务时，系统只采用一个结构管理所有状态的任务，当任务数量变多以及状态变得更复杂时，任务调度算法可能需要更复杂的分支逻辑来处理不同的任务。同时，遍历整个全局数组降低了系统效率。在引入链表之后，任务不再依赖单一结构来表达状态，而是根据其所处的链表来直接体现当前状态。Ready、Delay 等不同状态被映射为不同的链表集合，使得“状态即位置”的设计思想得以体现。这种方式不仅简化了调度逻辑，也使任务状态的管理更加清晰和直观，同时提升了任务在不同状态之间切换的效率。

从全局数组到多链表结构的转变，本质上是从“以任务为中心的统一管理”，走向“以状态为中心的分离管理”。这一演进为后续信号量、互斥锁等同步机制的实现奠定了基础，也使 EdiosOS 的调度模型更加贴近真实 RTOS 的设计思想。

CATALOG
    FEATURED TAGS
    ns3 SDN OpenFlow Linux 链接 操作系统 EidosOS
    FRIENDS