嵌入式中高效管理调度和动态内存
关注+星标公众号，不错过精彩内容转自| 嵌入式情报局
搞嵌入式开发，内存管理比较重要，我们遇到的bug，很多时候都有因为内存导致的。今天就跟大家聊聊这红黑树到底干啥的~
首先两个典型的问题:
实时任务调度：如何从百万级定时器中快速找到最先超时的事件？
内存分配：如何在海量碎片中高效搜索≥10KB的可用内存块？
红黑树正是解决这些问题的好办法：
? 通常使用链表管理1000个定时器？插入操作可能从1ms暴增到100ms！
? 用数组实现内存分配器？查找空闲块的时间会随着碎片增加直线上升！
时间复杂度如下数据结构插入删除查找链表/数组O(n)O(1)~O(n)O(n)红黑树O(log n)O(log n)O(log n)红黑树能够保证所有操作在 ( O(log n) ) 内完成，一、案例1：时间戳搜索（实时任务调度）1. 场景需求? 问题：实时系统需管理数千个定时器，普通链表或数组的插入/删除效率无法满足实时性要求。
? 目标：
? 插入新定时器（如50ms后触发的任务） → O(log n)
? 查找最早超时的任务 → O(1)（直接取最左节点）
? 删除已触发的定时器 → O(log n)
2. 红黑树实现方案键值设计：
? 用32位时间戳（如uint32_t timeout = systick + 50）表示超时时间。
? 时间戳溢出处理：（伪代码，只为说明应用）
// 判断时间戳a是否早于b（考虑32位溢出）
bool is_earlier(uint32_t a, uint32_t b) {
return (int32_t)(a - b) 0; // 利用有符号数溢出特性
}
数据结构：
typedef struct TimerEvent {
uint32_t timeout;// 超时时间戳
void (*callback)(void); // 回调函数指针
} TimerEvent;
typedef struct RBNode {
uint32_t key; // 存储timeout
TimerEvent event;
Color color;
struct RBNode *left, *right, *parent;
} RBNode;
3. 核心操作代码插入定时器：
void timer_insert(RBNode **root, uint32_t timeout, TimerEvent *evt) {
RBNode *z = alloc_node(timeout); // 从预分配内存池申请节点
z->event = *evt;
// 标准BST插入逻辑
RBNode *y = NULL;
RBNode *x = *root;
while (x) {
y = x;
x = (is_earlier(timeout, x->key)) ? x->left : x->right;
}
z->parent = y;
if (!y)
*root = z;
elseif (is_earlier(timeout, y->key))
y->left = z;
else
y->right = z;
fix_insert(root, z); // 红黑树平衡修复
}
查找最早超时事件：
// 直接取最左节点（最小值）
RBNode* find_earliest_timeout(RBNode *root) {
if (!root) return NULL;
while (root->left) root = root->left;
return root;
}
删除定时器：
// 先调用bst_delete删除节点，再修复红黑树
void timer_delete(RBNode **root, RBNode *z) {
RBNode *y = z;
Color y_original_color = y->color;
RBNode *x = NULL;
if (!z->left) {
x = z->right;
transplant(root, z, z->right);
} elseif (!z->right) {
x = z->left;
transplant(root, z, z->left);
} else {
y = minimum(z->right); // 找后继节点
y_original_color = y->color;
x = y->right;
if (y->parent == z)
x->parent = y;
else {
transplant(root, y, y->right);
y->right = z->right;
y->right->parent = y;
}
transplant(root, z, y);
y->left = z->left;
y->left->parent = y;
y->color = z->color;
}
if (y_original_color == BLACK)
fix_delete(root, x); // 红黑树删除修复
}
二、案例2：内存块大小搜索（动态内存分配）1. 场景需求? 问题：动态内存分配需快速查找≥请求大小的最小空闲块，首次适应算法效率低下。
? 目标：
? 插入释放的内存块 → O(log n)
? 查找合适块 → O(log n)
? 分割块后插入剩余空间 → O(log n)
2. 红黑树实现方案键值设计：
? 用内存块大小（uint32_t block_size）作为键值，树节点按块大小升序排列。
数据结构：
typedef struct MemBlock {
uint32_t start_addr; // 内存块起始地址
uint32_t size; // 块大小
} MemBlock;
typedef struct RBNode {
uint32_t key; // 存储block_size
MemBlock block;
Color color;
struct RBNode *left, *right, *parent;
} RBNode;
3. 核心操作代码查找≥size的最小内存块：
RBNode* find_suitable_block(RBNode *root, uint32_t size) {
RBNode *current = root;
RBNode *result = NULL;
while (current) {
if (current->key >= size) {
result = current; // 记录候选块
current = current->left; // 继续向左找更小的块
} else {
current = current->right; // 当前块太小，向右找更大的
}
}
return result; // 返回NULL或合适块
}
内存分配逻辑：
MemBlock* mem_alloc(RBNode **root, uint32_t size) {
RBNode *node = find_suitable_block(*root, size);
if (!node) returnNULL; // 内存不足
MemBlock *alloc_block = &node->block;
// 分割块（例如：找到12KB的块，申请10KB）
if (alloc_block->size > size) {
MemBlock remain = {
.start_addr = alloc_block->start_addr + size,
.size = alloc_block->size - size
};
mem_insert(root, remain.size, &remain); // 插入剩余块
}
mem_delete(root, node); // 从树中删除原节点
return alloc_block;
}
插入释放的内存块：
void mem_insert(RBNode **root, uint32_t size, MemBlock *blk) {
RBNode *z = alloc_node(size);
z->block = *blk;
// 标准BST插入
RBNode *y = NULL;
RBNode *x = *root;
while (x) {
y = x;
x = (size key) ? x->left : x->right;
}
z->parent = y;
if (!y)
*root = z;
elseif (size key)
y->left = z;
else
y->right = z;
fix_insert(root, z); // 红黑树平衡修复
}
所以红黑树的本质：通过颜色规则和旋转策略，在动态操作中维持近似平衡，以极低开销（每个节点仅1bit颜色标记）实现高效搜索。
不过传统的链表数组也有他们的优势,比如:
极小型数据（节点数 只追加不删除：数组的尾插操作 ( O(1) ) 更快严格顺序访问：如循环缓冲区，数组效率更高
如何更换JLink的Flashloader
MCU触摸按键噪声处理方法
AI设计PCB靠谱吗？
页:
[1]