FreeRTOS调度器的复杂度是多少？有什么方法可以自行检测？

调度器的时间复杂度 #

FreeRTOS默认使用优先级抢占式调度，调度逻辑的时间复杂度固定为O(1)，和系统中现存的任务总数无关。
这是因为FreeRTOS内核做了专门的架构优化：

• 内核为每个优先级单独维护就绪任务链表，同时用位图变量标记当前存在就绪任务的最高优先级
• 调度器每次执行时，仅需要直接读取最高优先级对应的就绪链表头结点的任务即可，不需要遍历所有就绪任务
  如果开启了同优先级任务的时间片轮转功能，调度逻辑依然是O(1)，仅需要把当前运行的同优先级任务移到对应就绪链表的队尾，再取新的队首任务执行，不会遍历所有任务。

自行检测调度器开销的方法 #

你可以通过以下几种方式实测当前软硬件环境下的调度器实际性能：

• GPIO翻转测量法：在上下文切换的入口和出口位置分别控制同一个GPIO引脚输出高低电平，用示波器测量电平翻转的时间差，就是单次调度的实际耗时。你可以直接修改portCONTEXT_SWITCH()相关的宏定义或者上下文切换的汇编代码插入GPIO控制逻辑，也可以在任务切换钩子函数vApplicationTaskSwitchedIn()/vApplicationTaskSwitchedOut()中插入翻转逻辑，测试时注意扣除钩子函数本身的执行耗时。
• 内核运行时间统计法：启用FreeRTOS的configGENERATE_RUN_TIME_STATS配置项，配置一个精度至少是系统滴答时钟10倍的硬件定时器作为统计时钟，之后调用vTaskGetRunTimeStats()接口即可获取调度器自身的开销占比、各个任务的运行时间占比数据。
• 多场景对比测试法：在系统中创建不同数量、不同优先级组合的任务，分别测量从调度触发（比如滴答中断触发、高优先级任务解除阻塞）到目标任务实际开始执行的时间差，多轮测试取平均值即可得到对应配置下的调度器实际耗时。

注意：不同硬件架构、不同FreeRTOS配置（比如是否启用MPU、是否需要保存浮点上下文、是否开启调试功能等）都会影响调度器的实际执行耗时，测试结果仅对应当前的软硬件配置。

内容的提问来源于stack exchange，提问作者Caglayan Dokme