北京网站建设企业,wordpress汉语公益,苏州网站建设设计制作公司怎么样,网上注册公司流程和费用标准目录
一、从厨房看调度器本质
二、O(1)算法的核心架构
1.时间复杂度的革命
2.动态优先级魔法
三、算法运行的全景图
1.时间片分配策略
2.上下文切换的艺术 前言#xff1a;前面文章提到关于并发的概念#xff0c;并发针对的是单核的CPU上同时运行很多情况#xff0c…目录
一、从厨房看调度器本质
二、O(1)算法的核心架构
1.时间复杂度的革命
2.动态优先级魔法
三、算法运行的全景图
1.时间片分配策略
2.上下文切换的艺术 前言前面文章提到关于并发的概念并发针对的是单核的CPU上同时运行很多情况并不是某个程序在CPU上运行就一直运行而是根据一定的时间片和调度算法来进行合理的调度从而引出了优先级的概念造成的最终目的就是可以让每一个进程都享受到CPU上的资源否则会导致进程饥饿。
一、从厨房看调度器本质
想象一家米其林餐厅的后厨主厨需要同时处理 10 位客人的订单5 个灶台同时开火3 位帮厨待命。此时 牛排需要每 30 秒翻面 浓汤需要持续搅拌防糊底 甜点装饰需要精确到秒 突发 VIP 订单要优先处理
优秀的主厨会动态调整任务顺序既保证出餐速度又维持菜品质量。这正是操作系统进程调度的现实映射——O(1) 调度算法就是 Linux 内核这位数字主厨的调度秘籍。
二、O(1)算法的核心架构
1.时间复杂度的革命
传统调度器如 Linux 2.4 的 O(n) 调度器像新手主厨逐个检查每个订单
// 伪代码示意 O(n) 遍历
for_each_process(p) {if (p-priority max_prio)max_prio p-priority;
}
这种线性扫描在面对数千进程时效率骤降。O(1) 调度器通过创新数据结构实现质的飞跃 双数组结构active待运行和 expired已耗尽时间片 位图索引140 级优先级0-139每个优先级对应队列 常数时间查询通过 __ffs() 指令直接定位最高优先级队列
2.动态优先级魔法
算法通过智能调整避免饿死交互式进程
// 动态优先级计算简化版
bonus CURRENT-sleep_avg / 32 - MAX_BONUS/2;
priority MAX_RT_PRIO (bonus 0 ? bonus : 0); 睡眠时间统计记录进程在可运行状态外的停留时间 交互式奖励频繁等待 I/O 的进程获得优先级提升 CPU 密集型惩罚持续占用 CPU 的进程优先级衰减
三、算法运行的全景图
1.时间片分配策略
# 时间片计算公式
if priority 120:time_slice (140 - priority) * 20 / CPU_LOAD
else:time_slice (140 - priority) * 5 / CPU_LOAD 实时进程获得更长的时间片20ms 级 普通进程短时间片5ms 级 负载自适应根据系统负载动态调整
2.上下文切换的艺术
在学习 C 语言时会接触到各类函数部分函数有返回值能被函数外部的变量接收。从函数栈帧的原理来看函数创建后执行至结束其栈帧会被销毁。而函数的数据以及外部程序要接收的数据其来源与函数栈帧的传值方式相关。函数栈帧的传值是通过 CPU 寄存器进行的程序运行过程中产生的各种临时数据也都存储在寄存器里。
当 CPU 进行进程切换时会将当前正在运行程序的临时数据存储起来。在早期版本的内核中这些数据存储于进程的进程控制块PCB中而在当前版本中虽并非直接存储在 PCB 中但也是与 PCB 相关的存储位置。这意味着程序运行时的数据是直接或间接存储于 PCB 中的。
如此一来当该进程后续被重新调度回来时寄存器便能从进程的 PCB 中获取当时运行位置所产生的数据并在此基础上继续运行从而实现进程切换且保证程序运行时产生的数据不会丢失。 A[时钟中断] -- B{检查时间片}B -- 未耗尽 -- C[继续运行]B -- 已耗尽 -- D{优先级调整}D -- E[移入expired数组]E -- F{active数组空?}F -- 是 -- G[交换active/expired]F -- 否 -- H[选择新进程]
这个状态机确保了 硬件定时器驱动调度节奏 双数组实现无锁切换 位图操作保持 O(1) 复杂度
上下文数据的保存和恢复 上下文数据的保存当一个进程在运行中因为某些原因比如时间片到了需要暂时停止运行让出 CPU此时进程需要保存好自己所有的临时数据即当前进程的上下文数据到对应的 PCB 中保存的目的是为了恢复。上下文数据的恢复当这个进程又被切换回来时或者切换到下一个新进程运行时只需要把该进程的 PCB 中的上下文数据重新写入到 CPU 寄存器中即可恢复运行。
【总结】
O(1) 调度器的设计体现了 Unix 哲学的经典原则 机制与策略分离核心调度框架与具体优先级策略解耦 时空平衡用空间换时间双数组位图 渐进式优化通过历史行为预测未来需求sleep_avg
虽然 CFS (Completely Fair Scheduler) 在 2.6.23 后取代了 O(1)但前者继承并发扬了其精髓 红黑树代替优先级数组 虚拟时间替代静态优先级 纳秒级精度替代毫秒级时间片
这种演进如同从机械手表到原子钟的跨越但核心思想始终如一在有限的硬件资源中寻找最优的任务执行轨迹。理解 O(1) 算法不仅是学习一个经典案例更是掌握系统设计的底层思维——在约束中创造秩序在混沌中寻找最优解。
