从零理解RTOS机制：基于Cortex-M3的任务优先级查表与同优先级轮转调度实现

文章目录前言一、问题背景为什么不能用循环判断优先级二、位图与查表法的设计2.1 位图一个bit对应一个优先级2.2 分块查找把32位拆成4个8位2.3 quickFindTable[256]核心查找表2.4 获取最高优先级任务三、同优先级任务的轮转调度3.1 为什么需要轮转3.2 taskTable每个优先级对应一条链表3.3 时间片耗尽把当前任务从头摘到尾3.4 完整流程四、两层机制配合起来看总结前言在实现一个抢占式RTOS时调度器最核心的两个问题是当前有多个任务就绪怎么快速找到优先级最高的那个如果多个任务优先级相同又该怎么分配CPU时间本文基于Cortex-M3内核结合tBitmap位图查表结构和tTask任务链表把这两个问题的实现方式讲清楚。一、问题背景为什么不能用循环判断优先级最直接的思路是从优先级0开始一个个判断任务是否就绪找到第一个就绪的就是最高优先级。这种方式的时间复杂度是O(n)优先级数量越多最坏情况下遍历次数越多对实时性要求高的RTOS来说是不可接受的。解决办法是用一个位图表示所有任务的就绪状态再配合一张预先计算好的查找表把查找时间压缩到O(1)。二、位图与查表法的设计2.1 位图一个bit对应一个优先级系统支持32个优先级用一个uint32_t变量表示typedefstruct_tBitmap{uint32_tbitmap;}tBitmap;第几位为1就代表第几号优先级有任务就绪。比如优先级2的任务就绪了就把第2位置1该任务不再就绪阻塞/延时就把第2位清0voidtBitmapSet(tBitmap*bitmap,uint32_tpos){bitmap-bitmap|(1pos);}voidtBitmapClear(tBitmap*bitmap,uint32_tpos){bitmap-bitmap~(1pos);}在main.c的tTaskInit中可以看到每创建一个任务就会把它的优先级对应的位置1task-prioprio;tListAddFirst(taskTable[prio],(task-linkNode));tBitmapSet(taskPrioBitmap,prio);2.2 分块查找把32位拆成4个8位32个优先级的所有就绪组合共有 2³² 种直接建查找表内存开销无法接受。解决办法是把32位拆成4段每段8位1字节逐段判断uint32_ttBitmapGetFirstSet(tBitmap*bitmap){uint32_tvaluebitmap-bitmap;if(value0xFF)returnquickFindTable[value0xFF];elseif(value0xFF00)returnquickFindTable[(value8)0xFF]8;elseif(value0xFF0000)returnquickFindTable[(value16)0xFF]16;elsereturnquickFindTable[(value24)0xFF]24;}因为数字越小优先级越高所以永远优先检查最低的8位优先级0~7非0就直接查表返回否则再检查下一段结果需要加上对应的偏移量8/16/24。2.3 quickFindTable[256]核心查找表每一段只有8位8位共有 2⁸256 种组合正好可以用一张256项的表把所有组合的答案穷举出来。表里的值永远是0~7代表这8位里最低位的1在第几位。十进制值二进制最低位1所在位置表中的值000000000无全灭特殊值如0xFF100000001第0位0200000010第1位11000001010第1位112810000000第7位725511111111第0位0这张表在编译期就已经生成好、写死在Flash里运行时不需要计算直接查表即可所以查找过程是常数时间。2.4 获取最高优先级任务拿到最高优先级编号后再从对应的任务链表里取出任务tTask*tTaskHighestReady(void){uint32_thighestPriotBitmapGetFirstSet(taskPrioBitmap);tNode*nodetListFirst(taskTable[highestPrio]);return(tTask*)tNodeParent(node,tTask,linkNode);}到这一步调度器已经能在O(1)时间内确定当前该跑哪个优先级。但问题来了如果同一个优先级下挂了多个任务呢三、同优先级任务的轮转调度3.1 为什么需要轮转看main.c里的任务创建tTaskInit(tTask2,task2Entry,(void*)0x22222222,1,task2Env[1024]);tTaskInit(tTask3,task3Entry,(void*)0x33333333,1,task3Env[1024]);task2和task3优先级都是1。位图查表只能定位到优先级1这一层无法区分该跑task2还是task3——这一层的调度靠的不是位图而是同优先级链表 时间片轮转Round-Robin。3.2 taskTable每个优先级对应一条链表tList taskTable[TINYOS_PRO_COUNT];taskTable的每个下标对应一个优先级存的不是单个任务而是一条链表可以挂多个同优先级任务。tTaskHighestReady里的tListFirst永远只取链表头部的任务来跑。3.3 时间片耗尽把当前任务从头摘到尾轮转的关键逻辑在SysTick_Handler里if(--(currentTask-slice)0)// 时间片计数器归零{if(tListCount(taskTable[currentTask-prio])0){tListRemoveFirst(taskTable[currentTask-prio]);// 把当前任务从链表头摘下tListAddLast(taskTable[currentTask-prio],(currentTask-linkNode));// 塞到链表尾部currentTask-sliceTINYOS_SLICE_MAX;// 重置时间片}}每个任务都有一个slice字段每个时钟节拍SysTick中断减1减到0就说明这个任务的时间片用完了。这时把它从链表头摘下、塞进链表尾部并把slice重新填满再触发一次调度tTaskSched()。由于tTaskHighestReady每次都是取链表头部的任务链表顺序一变下一次被选中运行的自然就是原来排在第二位的任务从而实现了同优先级任务的轮流执行。3.4 完整流程否是SysTick中断触发currentTask-slice减到0?结束本次tick处理把currentTask从taskTable链表头摘下塞入taskTable链表尾部重置slice为TINYOS_SLICE_MAXtTaskSched触发调度tBitmapGetFirstSet查位图定位最高优先级tListFirst取该优先级链表头部任务切换到新任务运行四、两层机制配合起来看整个调度器其实是两层结构叠加第一层跨优先级位图 quickFindTable查表O(1)时间定位当前该跑哪个优先级。第二层同优先级内部链表头尾轮转配合时间片计数器解决同优先级里该跑哪一个任务。两者结合才是一个完整、实时性可预测的抢占式调度器实现。总结位图法把32位优先级拆成4段8位用一张256项的静态表把查找复杂度从O(n)降到O(1)。表中存的是8位组合中最低位1的位置永远落在0~7区间是查表法能复用同一张表处理32个优先级的关键。同优先级任务靠链表结构和时间片轮转来分配CPU与位图查表是相互独立又配合工作的两套机制。