FreeRTOS 的链表 vListInsertEnd() 方法笔记
在研究 FreeRTOS 内核时, 发现自已一直理解错了 vListInsertEnd() 的意思, 特此记录下.
vListInsertEnd() 这个方法比较迷惑人, 这个方法真正的意思是尾插, 而不是插到链表的尾部. 这两者的意思是不一样的.
那究竟什么是尾插呢? 我们应该知道头插, 给定一个链表节点 A, 头插就是说新的节点要插在 A 的后面, 而尾插则是说新的节点要插在 A 的前面. 这就是尾插的意思: 把给定的节点当作尾部.
FreeRTOS 的链表结构 List_t 中有一个成员叫做 pxIndex, 这个成员是用来遍历这个链表用的, 具体来说就是在同优先级任务链上, 依次取得下一次任务以达到同优先级任务共享 CPU 时间的. List_t 结构中还有一个成员叫做 xListEnd, xListEnd 是不包含有效数据的节点, 它标识着这个链表的真正的尾部.
之前令我误解的一点就是, 我总以为 vListInsertEnd() 就是将新的节点插到整个链表的尾部, 也就是 xListEnd 的前面. 但是 vListInsertEnd() 却是将新的节点插入到 pxIndex 前面. 我想了好久没明白这什么意思, 直到我看到 listGET_OWNER_OF_NEXT_ENTRY(pxTCB, pxList) 这个宏我才明白, 这个宏就是每次调度器选择下一个任务时所调用的, 这个宏会每次将 pxIndex 更新为它后面的节点. 所以, 为什么 vListInsertEnd() 是将新的节点插入到 pxIndex 前面也就解释的通了, 这是为了更公平的让各个任务共享时间片. 比如说当前有如下的任务链表, 每个任务的优先级相同:
1 2 3 4 5 end
其中 1, 2, 3 任务刚刚依次获得完时间片, pxIndex 现在指向 4, 那么现在又来了一个新的任务 6, 当调用 vListInsertEnd() 的时候, 任务 6 就会被插入到 4 前面, 之后调度就会变成 4, 5, 1, 2, 3, 6, … 而如果 6 被插入 end 前面, 那之后的调度就会变成 4, 5, 6, 1, 2, 3, … 显然这对 1, 2, 3 是不公平的.
FreeRTOS 确实是个精悍的内核, 用最少的代码实现了非常多的复杂精细, 逻辑缜密的功能, 值得一看！
其它文章
数字货币
- 什么是比特币的链上 (on-chain) 与链下 (off-chain) 交易, 以及往交易所充币后发生了什么
- 为何留在 steemit?
- 说一说重放, 重放保护, 以及分叉期间我们该怎么做
- 闲聊即将到来的 segwit2x 分叉
- electrum 钱包的 sweep 功能小记
- 浅读 Steemit 的设计与规则
- bitshares 中的账户与权限个人理解
- 比特币地址, 公钥与私钥的格式以及如何保证比特币不丢失