21、链表的应用：任务调度中的就绪队列、内存管理中的空闲块链表

链表这东西，说白了就是一根绳子串起一堆珠子。但真正把它用好了，能解决不少实际问题。今天咱们就聊聊链表在嵌入式系统里的两个经典应用场景——任务调度中的就绪队列，还有内存管理中的空闲块链表。

这两个场景，我当年刚入行时都踩过坑。嗯，咱们一个一个说。

21.1 任务调度中的就绪队列

先说说任务调度。你想想看，一个嵌入式系统里可能同时跑着十几个任务。有的要处理按键，有的要刷新屏幕，有的要采集传感器数据。CPU只有一个，那谁先跑谁后跑？

这时候就需要一个就绪队列。所有准备好运行的任务，都挂在这个队列上。调度器每次从队列头部取出一个任务来执行。

我在一个RTOS项目里就遇到过这种情况。当时有8个任务，优先级各不相同。调度器每次都要遍历整个链表找最高优先级的任务。后来我改成按优先级排序的链表，每次直接取头节点，效率提升了不少。

就绪队列的数据结构

// 任务控制块
typedef struct tcb {
    uint32_t    task_id;        // 任务ID
    uint32_t    priority;       // 优先级（数值越小优先级越高）
    void        (*task_func)(void*);  // 任务函数指针
    uint32_t    stack_size;     // 栈大小
    uint8_t     state;          // 任务状态：就绪、运行、阻塞
    struct tcb  *prev;          // 前驱指针
    struct tcb  *next;          // 后继指针
} tcb_t;

// 就绪队列
typedef struct {
    tcb_t       *head;          // 队列头
    tcb_t       *tail;          // 队列尾
    uint32_t    count;          // 队列中任务数量
} ready_queue_t;

你看这个结构体，每个任务都带着前后指针。这就是双向链表的标准做法。我个人习惯在TCB里直接嵌入链表节点，而不是用单独的链表结构体去包装。这样内存更紧凑，访问也更快。

就绪队列的核心操作

就绪队列主要就三个操作：插入、删除、取头。咱们一个一个看。

插入操作：按优先级排序插入。新任务来了，找到合适的位置插进去。

void ready_queue_insert(ready_queue_t *queue, tcb_t *task) {
    tcb_t *curr = queue->head;
    
    // 空队列，直接插入
    if (queue->head == NULL) {
        queue->head = task;
        queue->tail = task;
        task->prev = NULL;
        task->next = NULL;
        queue->count = 1;
        return;
    }
    
    // 按优先级查找插入位置
    while (curr != NULL && curr->priority <= task->priority) {
        curr = curr->next;
    }
    
    // 插入到curr前面
    if (curr == queue->head) {
        // 插到头部
        task->next = queue->head;
        task->prev = NULL;
        queue->head->prev = task;
        queue->head = task;
    } else if (curr == NULL) {
        // 插到尾部
        task->prev = queue->tail;
        task->next = NULL;
        queue->tail->next = task;
        queue->tail = task;
    } else {
        // 插到中间
        task->prev = curr->prev;
        task->next = curr;
        curr->prev->next = task;
        curr->prev = task;
    }
    
    queue->count++;
}

删除操作：任务执行完毕或者被阻塞了，就从队列里摘掉。

void ready_queue_remove(ready_queue_t *queue, tcb_t *task) {
    if (task->prev == NULL) {
        // 删除头节点
        queue->head = task->next;
        if (queue->head != NULL) {
            queue->head->prev = NULL;
        }
    } else {
        task->prev->next = task->next;
    }
    
    if (task->next == NULL) {
        // 删除尾节点
        queue->tail = task->prev;
        if (queue->tail != NULL) {
            queue->tail->next = NULL;
        }
    } else {
        task->next->prev = task->prev;
    }
    
    task->prev = NULL;
    task->next = NULL;
    queue->count--;
}

就绪队列的调度流程

调度器的工作流程其实很简单：

1. 从就绪队列头部取出一个任务
2. 执行该任务（或者切换上下文）
3. 任务执行完或被阻塞后，从队列中删除
4. 如果有新任务就绪，插入队列
5. 回到步骤1

这里有个关键点——取头操作必须是原子的。如果在取头的过程中被中断打断，队列结构可能被破坏。我一般会在取头前关中断，取完再开。

21.2 内存管理中的空闲块链表

说完任务调度，咱们聊聊内存管理。嵌入式系统里，动态内存分配是个大问题。标准库的malloc/free在裸机环境下往往不太靠谱——碎片多、速度慢、还不确定。

所以很多嵌入式系统会自己实现一个内存池。空闲块链表就是内存池的核心数据结构。

空闲块链表的工作原理

说白了，就是预先划分一大块内存，切成若干固定大小的块。每个块里放一个指针，指向下一个空闲块。所有空闲块串成一个链表。

分配内存时，从链表头部取一个块。释放内存时，把块放回链表头部。

空闲块链表的数据结构

// 空闲块节点（和内存块共用空间）
typedef struct free_block {
    struct free_block *next;    // 指向下一个空闲块
} free_block_t;

// 内存池
typedef struct {
    void        *pool_start;    // 内存池起始地址
    uint32_t    block_size;     // 每个块的大小（字节）
    uint32_t    block_count;    // 块的总数
    free_block_t *free_list;    // 空闲块链表头
    uint32_t    free_count;     // 当前空闲块数量
} mem_pool_t;

你看这个free_block_t结构体，就一个next指针。它和内存块是同一块内存。当这个块空闲时，前4个字节（32位系统）存的是next指针。当这个块被分配出去后，这4个字节就是用户数据的一部分了。

内存池的初始化

void mem_pool_init(mem_pool_t *pool, void *buffer, 
                   uint32_t block_size, uint32_t block_count) {
    uint32_t i;
    free_block_t *block;
    uint8_t *addr = (uint8_t*)buffer;
    
    pool->pool_start = buffer;
    pool->block_size = block_size;
    pool->block_count = block_count;
    pool->free_list = (free_block_t*)addr;
    pool->free_count = block_count;
    
    // 把所有块串成链表
    for (i = 0; i < block_count - 1; i++) {
        block = (free_block_t*)(addr + i * block_size);
        block->next = (free_block_t*)(addr + (i + 1) * block_size);
    }
    
    // 最后一个块的next置NULL
    block = (free_block_t*)(addr + (block_count - 1) * block_size);
    block->next = NULL;
}

初始化时，我把所有空闲块串成一个单向链表。分配时从头取，释放时放回头部。这就是典型的LIFO（后进先出）策略。

分配与释放

void* mem_pool_alloc(mem_pool_t *pool) {
    free_block_t *block;
    
    if (pool->free_list == NULL) {
        return NULL;  // 没有空闲块了
    }
    
    // 从链表头部取一个块
    block = pool->free_list;
    pool->free_list = block->next;
    pool->free_count--;
    
    return (void*)block;
}

void mem_pool_free(mem_pool_t *pool, void *ptr) {
    free_block_t *block = (free_block_t*)ptr;
    
    // 把块放回链表头部
    block->next = pool->free_list;
    pool->free_list = block;
    pool->free_count++;
}

你看，分配和释放都是O(1)的复杂度，非常快。比标准库的malloc快了一个数量级不止。

21.3 两种链表的对比

特性	就绪队列	空闲块链表
链表类型	双向链表	单向链表
节点存储	节点在TCB内部	节点和内存块共用空间
插入策略	按优先级排序插入	插入头部（LIFO）
删除策略	任意位置删除	只从头部取
时间复杂度	插入O(n)，删除O(1)	分配O(1)，释放O(1)
主要用途	任务调度	内存分配

为什么就绪队列要用双向链表？因为调度器经常需要从中间删除一个任务（比如任务被阻塞了）。双向链表删除任意节点是O(1)的，单向链表得遍历找到前驱节点，那就是O(n)了。

而空闲块链表只用单向就够了。因为分配和释放都只操作头部，不需要从中间删除。单向链表省了一个指针，内存利用率更高。

21.4 核心知识图谱

下面这张图展示了链表在嵌入式系统中的两个核心应用场景，以及它们之间的关系。

从这张图可以看出，链表在嵌入式系统里扮演的角色就是「资源管理器」。无论是CPU时间（任务调度）还是内存空间（内存分配），都用链表来组织和管理空闲资源。

为什么都用链表？因为链表插入和删除的效率高。数组虽然随机访问快，但插入删除要移动大量元素，在实时系统里根本不敢用。

好了，关于链表在任务调度和内存管理中的应用，就聊到这儿。这两种场景是嵌入式开发中最常见的链表应用。你想想看，一个RTOS内核里，就绪队列、等待队列、消息队列、信号量队列……到处都是链表的身影。掌握了链表，你就掌握了嵌入式系统的一半。

---

公众号:蓝海资料掘金营，微信deep3321