调度器 VS CFS完全公平调度器)
文章目录O(1)调度器Per-CPU runqueue 双 prio_array静态优先级 动态优先级时间片机制O(1)抢占模型O(1)调度器优缺点CFS完全公平调度器放弃双队列采用vruntime红黑树就绪队列vruntime 计算公式CFS调度周期与最小调度粒度CFS三类抢占机制CFS调度实体 组调度简述CFS优缺点O(1)查找是O(1)所以整体比CFS更快定时任务抖动原理分析抖动根源nanosleep 为什么一定会存在随机抖动timerfd epoll 缓解抖动原理O(1) vs CFS 全维度对比表Linux 2.6 内核早期引入O(1)调度器解决旧调度器O(n)性能瓶颈但因其公平性缺陷在2.6.23被CFS完全公平调度器取代。O(1)调度器Per-CPU runqueue 双 prio_array每个CPU核心独占独立runqueue运行队列多核队列互相隔离规避全局大锁竞争。runqueue包含两组完全一致的prio_arrayactive活跃数组存放时间片未耗尽的就绪进程expired过期数组存放时间片耗尽的就绪进程。prio_array结构成员nr_active当前数组就绪进程总数bit_map[5]5个int共160bit位图规范使用低140bit。bit 099对应实时进程静态优先级bit 100139对应普通分时进程静态优先级bit置1代表该优先级存在就绪进程可快速定位最高优先级任务。queue[140]140条双向链表下标等于静态优先级同优先级进程挂载在同一条链表。核心轮转逻辑Swap指针交换调度器仅从active数组选取进程通过bit_map找到数值最小优先级最高就绪进程运行进程运行持续消耗时间片时间片耗尽后移出active加入同优先级expired链表active.nr_active 0时执行指针互换active - expired原过期队列变为活跃队列所有进程重新分配时间片开启新一轮调度周期。静态优先级 动态优先级Linux 140 档静态优先级划分实时进程0 ~ 99SCHED_FIFO / SCHED_RR普通分时进程100 ~ 139映射关系static_prio 120 nicenice范围[-20,19]O(1)引入动态优先级作为交互优化手段动态优先级基于静态优先级调整频繁休眠的交互进程唤醒后内核主动提升其动态优先级、奖励额外时间片弊端属于经验策略没有理论边界行为不可预测。时间片机制普通进程时间片由静态优先级直接计算time_slice (MAX_TIMESLICE * (140 - static_prio)) / 140MAX_TIMESLICE 默认 100msstatic_prio越小nice越小时间片越长。O(1)抢占模型实时进程 所有普通进程只要实时任务就绪立刻抢占普通进程不同静态优先级普通进程不会互相抢占普通进程之间必须等到自身时间片耗尽才会让出CPU。这是桌面交互卡顿最核心根源后台大量低nice长耗时进程拿到CPU后会持续运行直到时间片用完鼠标、窗口这类短时交互进程无法及时抢占造成明显延迟。O(1)调度器优缺点优点通过位图查找最高优先级进程查找操作复杂度恒定O(1)不受就绪进程数量影响per-cpu runqueue设计多核扩展性优于更早的O(n)调度器实时进程具备强优先级保障。致命缺陷被CFS替代的根本原因公平性差普通进程静态优先级机制低优先级进程极易饥饿普通进程之间无抢占后台任务长时间霸占CPU交互体验差依赖动态优先级、睡眠奖励等大量启发式策略优化交互逻辑臃肿时序行为难以分析分时模型下任务唤醒后进入就绪链表排队系统重载下唤醒抖动随机性强。CFS完全公平调度器CFS只负责普通分时进程实时调度器独立存在优先级全局高于CFS。放弃双队列采用vruntime红黑树就绪队列移除 active/expired、位图、140条优先级链表;单CPU CFS就绪队列核心一棵以vruntime为key的红黑树:所有CFS就绪调度实体挂在红黑树上排序规则vruntime越小越靠左调度规则永远选择最左侧vruntime最小的调度实体运行。核心思想摒弃固定时间片让就绪进程按权重比例均分CPU时间。vruntime 计算公式物理运行时间 → 虚拟运行时间换算公式vruntime delta_exec * weight_0 / weight_taskweight_0nice0对应的基准权重weight_task当前进程权重高权重进程 weight_task 更大 → 同等物理时间下vruntime增量更小进程休眠、阻塞IO时delta_exec0vruntime停止上涨nice与权重是内核内置常量表nice-20 权重最高nice0基准权重1024nice19权重最低。长时间休眠任务唤醒时内核会对vruntime做对齐修正防止休眠很久的进程唤醒后持续抢占CPU引发调度震荡。CFS调度周期与最小调度粒度CFS不允许无限制频繁抢占内核两个核心阈值sysctl_sched_latency目标调度周期。当就绪进程较少时所有进程需要在该周期内轮流获得CPUsysctl_sched_min_granularity最小调度粒度。一个进程最少持续运行这么久避免频繁上下文切换。也就是说即使别的进程vruntime更小当前进程至少运行min_granularity才允许被抢占防止系统在大量进程间疯狂切换。CFS三类抢占机制唤醒抢占新进程就绪抢占进程被唤醒加入红黑树如果它的vruntime远小于当前运行进程满足阈值条件则触发抢占。交互任务流畅主要依靠该机制。周期抢占定时检查当前进程持续运行超过最小调度粒度内核检查是否存在vruntime更小的任务满足条件则切换。自愿抢占进程主动sleep、调用sched_yield主动放弃CPU。重要结论CFS不存在基于静态优先级的无条件抢占一切抢占判断依托vruntime差值。CFS调度实体 组调度简述CFS调度单元不是task_struct而是sched_entity 调度实体普通进程一个任务对应一个调度实体组调度cgroup CPU子系统进程组作为一个调度实体参与红黑树调度。实现两级公平先组之间按权重分配CPU组内进程再二次分配。天然适配容器、云多租户资源隔离场景。CFS优缺点优点架构层面实现按权重公平分配CPU彻底解决O(1)时代进程饥饿问题依靠唤醒抢占频繁休眠的交互进程可及时抢占CPU天然改善桌面响应移除大量启发式补偿代码核心逻辑简洁原生支持组调度、CPU带宽限制适配虚拟化、容器场景。缺点调度实体查找、插入红黑树复杂度 O(logN)分时调度模型固有局限任务唤醒后仍需要进入红黑树排队CPU满载时存在调度延迟调整nice权重只能降低等待概率无法彻底消除O(1)查找是O(1)所以整体比CFS更快不是。O(1)只是寻找下一个运行进程这一步是常数时间真实系统开销由上下文切换、就绪队列排队延迟、缓存失效主导logN红黑树操作开销极小通用业务场景几乎无法观测CFS带来的公平性、交互体验收益远大于微小的logN开销这也是主线内核全面切换CFS的根本原因。定时任务抖动原理分析抖动根源定时器硬件抖动时钟中断、内核定时器层带来的微小偏差调度延迟主要抖动来源定时器到期唤醒线程 → 线程置为就绪态 → 等待CPU就绪队列调度。O(1)、CFS都会存在调度延迟但抖动特征不同O(1)普通进程之间不能互相抢占后台长任务一旦拿到CPU会跑完整个时间片交互 / 定时线程最长需要等待一整个时间片抖动上限高CFS有唤醒抢占最小调度粒度约束新唤醒的低vruntime任务有机会抢占正在运行的进程不需要等待当前进程“耗尽时间片”。这是CFS相比O(1)定时抖动更小的底层原因。nanosleep 为什么一定会存在随机抖动std::this_thread::sleep_until的底层nanosleep仅在内核定时器到期后将线程标记为TASK_RUNNING不会立刻分配CPU线程加入对应CPU就绪队列排队CPU重载下排队时长随机调高nice只是提升进程权重、缩短平均等待时间不能根除排队延迟。timerfd epoll 缓解抖动原理timerfd到期触发内核中断中断上下文优先级高于进程调度中断上下文可以快速唤醒用户线程缩短就绪等待窗口降低调度延迟。注意属于优化手段不构成硬实时。对严格周期确定性需求需要 SCHED_FIFO/SCHED_RR 实时策略或 PREEMPT_RT 补丁。O(1) vs CFS 全维度对比表对比维度O(1)调度器CFS完全公平调度器就绪队列结构activeexpired双prio_array 位图 140条优先级链表基于vruntime排序的红黑树调度实体sched_entity查找下一个进程复杂度O(1)O(logN)时间片模型固定时间片由static_prio公式计算无固定时间片基于权重比例分配CPU优先级模型静态优先级动态优先级启发式奖励无静态优先级使用权重vruntime普通进程抢占规则时间片耗尽才切换普通进程间无法互相抢占支持唤醒抢占、周期抢占受min_granularity约束nice作用决定静态优先级时间片长度映射权重影响vruntime增长速度轮转机制active/expired指针swap无队列交换调度实体常驻红黑树公平性较差易出现低优先级进程饥饿优秀按权重实现公平分时交互优化手段休眠进程动态优先级提升、时间片奖励启发式架构原生唤醒抢占机制组调度不原生支持原生支持cgroup组调度重载场景抖动上限较高最坏需等待完整时间片相对更低支持抢占正在运行普通进程 Linux O(1)调度器 VS CFS完全公平调度器
文章目录O(1)调度器Per-CPU runqueue 双 prio_array静态优先级 动态优先级时间片机制O(1)抢占模型O(1)调度器优缺点CFS完全公平调度器放弃双队列采用vruntime红黑树就绪队列vruntime 计算公式CFS调度周期与最小调度粒度CFS三类抢占机制CFS调度实体 组调度简述CFS优缺点O(1)查找是O(1)所以整体比CFS更快定时任务抖动原理分析抖动根源nanosleep 为什么一定会存在随机抖动timerfd epoll 缓解抖动原理O(1) vs CFS 全维度对比表Linux 2.6 内核早期引入O(1)调度器解决旧调度器O(n)性能瓶颈但因其公平性缺陷在2.6.23被CFS完全公平调度器取代。O(1)调度器Per-CPU runqueue 双 prio_array每个CPU核心独占独立runqueue运行队列多核队列互相隔离规避全局大锁竞争。runqueue包含两组完全一致的prio_arrayactive活跃数组存放时间片未耗尽的就绪进程expired过期数组存放时间片耗尽的就绪进程。prio_array结构成员nr_active当前数组就绪进程总数bit_map[5]5个int共160bit位图规范使用低140bit。bit 099对应实时进程静态优先级bit 100139对应普通分时进程静态优先级bit置1代表该优先级存在就绪进程可快速定位最高优先级任务。queue[140]140条双向链表下标等于静态优先级同优先级进程挂载在同一条链表。核心轮转逻辑Swap指针交换调度器仅从active数组选取进程通过bit_map找到数值最小优先级最高就绪进程运行进程运行持续消耗时间片时间片耗尽后移出active加入同优先级expired链表active.nr_active 0时执行指针互换active - expired原过期队列变为活跃队列所有进程重新分配时间片开启新一轮调度周期。静态优先级 动态优先级Linux 140 档静态优先级划分实时进程0 ~ 99SCHED_FIFO / SCHED_RR普通分时进程100 ~ 139映射关系static_prio 120 nicenice范围[-20,19]O(1)引入动态优先级作为交互优化手段动态优先级基于静态优先级调整频繁休眠的交互进程唤醒后内核主动提升其动态优先级、奖励额外时间片弊端属于经验策略没有理论边界行为不可预测。时间片机制普通进程时间片由静态优先级直接计算time_slice (MAX_TIMESLICE * (140 - static_prio)) / 140MAX_TIMESLICE 默认 100msstatic_prio越小nice越小时间片越长。O(1)抢占模型实时进程 所有普通进程只要实时任务就绪立刻抢占普通进程不同静态优先级普通进程不会互相抢占普通进程之间必须等到自身时间片耗尽才会让出CPU。这是桌面交互卡顿最核心根源后台大量低nice长耗时进程拿到CPU后会持续运行直到时间片用完鼠标、窗口这类短时交互进程无法及时抢占造成明显延迟。O(1)调度器优缺点优点通过位图查找最高优先级进程查找操作复杂度恒定O(1)不受就绪进程数量影响per-cpu runqueue设计多核扩展性优于更早的O(n)调度器实时进程具备强优先级保障。致命缺陷被CFS替代的根本原因公平性差普通进程静态优先级机制低优先级进程极易饥饿普通进程之间无抢占后台任务长时间霸占CPU交互体验差依赖动态优先级、睡眠奖励等大量启发式策略优化交互逻辑臃肿时序行为难以分析分时模型下任务唤醒后进入就绪链表排队系统重载下唤醒抖动随机性强。CFS完全公平调度器CFS只负责普通分时进程实时调度器独立存在优先级全局高于CFS。放弃双队列采用vruntime红黑树就绪队列移除 active/expired、位图、140条优先级链表;单CPU CFS就绪队列核心一棵以vruntime为key的红黑树:所有CFS就绪调度实体挂在红黑树上排序规则vruntime越小越靠左调度规则永远选择最左侧vruntime最小的调度实体运行。核心思想摒弃固定时间片让就绪进程按权重比例均分CPU时间。vruntime 计算公式物理运行时间 → 虚拟运行时间换算公式vruntime delta_exec * weight_0 / weight_taskweight_0nice0对应的基准权重weight_task当前进程权重高权重进程 weight_task 更大 → 同等物理时间下vruntime增量更小进程休眠、阻塞IO时delta_exec0vruntime停止上涨nice与权重是内核内置常量表nice-20 权重最高nice0基准权重1024nice19权重最低。长时间休眠任务唤醒时内核会对vruntime做对齐修正防止休眠很久的进程唤醒后持续抢占CPU引发调度震荡。CFS调度周期与最小调度粒度CFS不允许无限制频繁抢占内核两个核心阈值sysctl_sched_latency目标调度周期。当就绪进程较少时所有进程需要在该周期内轮流获得CPUsysctl_sched_min_granularity最小调度粒度。一个进程最少持续运行这么久避免频繁上下文切换。也就是说即使别的进程vruntime更小当前进程至少运行min_granularity才允许被抢占防止系统在大量进程间疯狂切换。CFS三类抢占机制唤醒抢占新进程就绪抢占进程被唤醒加入红黑树如果它的vruntime远小于当前运行进程满足阈值条件则触发抢占。交互任务流畅主要依靠该机制。周期抢占定时检查当前进程持续运行超过最小调度粒度内核检查是否存在vruntime更小的任务满足条件则切换。自愿抢占进程主动sleep、调用sched_yield主动放弃CPU。重要结论CFS不存在基于静态优先级的无条件抢占一切抢占判断依托vruntime差值。CFS调度实体 组调度简述CFS调度单元不是task_struct而是sched_entity 调度实体普通进程一个任务对应一个调度实体组调度cgroup CPU子系统进程组作为一个调度实体参与红黑树调度。实现两级公平先组之间按权重分配CPU组内进程再二次分配。天然适配容器、云多租户资源隔离场景。CFS优缺点优点架构层面实现按权重公平分配CPU彻底解决O(1)时代进程饥饿问题依靠唤醒抢占频繁休眠的交互进程可及时抢占CPU天然改善桌面响应移除大量启发式补偿代码核心逻辑简洁原生支持组调度、CPU带宽限制适配虚拟化、容器场景。缺点调度实体查找、插入红黑树复杂度 O(logN)分时调度模型固有局限任务唤醒后仍需要进入红黑树排队CPU满载时存在调度延迟调整nice权重只能降低等待概率无法彻底消除O(1)查找是O(1)所以整体比CFS更快不是。O(1)只是寻找下一个运行进程这一步是常数时间真实系统开销由上下文切换、就绪队列排队延迟、缓存失效主导logN红黑树操作开销极小通用业务场景几乎无法观测CFS带来的公平性、交互体验收益远大于微小的logN开销这也是主线内核全面切换CFS的根本原因。定时任务抖动原理分析抖动根源定时器硬件抖动时钟中断、内核定时器层带来的微小偏差调度延迟主要抖动来源定时器到期唤醒线程 → 线程置为就绪态 → 等待CPU就绪队列调度。O(1)、CFS都会存在调度延迟但抖动特征不同O(1)普通进程之间不能互相抢占后台长任务一旦拿到CPU会跑完整个时间片交互 / 定时线程最长需要等待一整个时间片抖动上限高CFS有唤醒抢占最小调度粒度约束新唤醒的低vruntime任务有机会抢占正在运行的进程不需要等待当前进程“耗尽时间片”。这是CFS相比O(1)定时抖动更小的底层原因。nanosleep 为什么一定会存在随机抖动std::this_thread::sleep_until的底层nanosleep仅在内核定时器到期后将线程标记为TASK_RUNNING不会立刻分配CPU线程加入对应CPU就绪队列排队CPU重载下排队时长随机调高nice只是提升进程权重、缩短平均等待时间不能根除排队延迟。timerfd epoll 缓解抖动原理timerfd到期触发内核中断中断上下文优先级高于进程调度中断上下文可以快速唤醒用户线程缩短就绪等待窗口降低调度延迟。注意属于优化手段不构成硬实时。对严格周期确定性需求需要 SCHED_FIFO/SCHED_RR 实时策略或 PREEMPT_RT 补丁。O(1) vs CFS 全维度对比表对比维度O(1)调度器CFS完全公平调度器就绪队列结构activeexpired双prio_array 位图 140条优先级链表基于vruntime排序的红黑树调度实体sched_entity查找下一个进程复杂度O(1)O(logN)时间片模型固定时间片由static_prio公式计算无固定时间片基于权重比例分配CPU优先级模型静态优先级动态优先级启发式奖励无静态优先级使用权重vruntime普通进程抢占规则时间片耗尽才切换普通进程间无法互相抢占支持唤醒抢占、周期抢占受min_granularity约束nice作用决定静态优先级时间片长度映射权重影响vruntime增长速度轮转机制active/expired指针swap无队列交换调度实体常驻红黑树公平性较差易出现低优先级进程饥饿优秀按权重实现公平分时交互优化手段休眠进程动态优先级提升、时间片奖励启发式架构原生唤醒抢占机制组调度不原生支持原生支持cgroup组调度重载场景抖动上限较高最坏需等待完整时间片相对更低支持抢占正在运行普通进程