Linux 排程背后的数学

为什么要搞这些数学为了确保你的电脑、手机、服务器在忙碌时不会「卡死」或「崩溃」并且能公平地分配资源你可以想象成在管理一个超市收银台一、为什么要检定「稳定条件」ADF / KPSS白话问题收银台会不会排队排到爆炸数学解释检查「顾客来的速度」是不是一直比「结账速度」快。如果来的速度持续大于结账速度队伍就会无限增长核心洞察统计假说就是在问「现在是不是已经快要爆炸了」现实案例情况结果稳定每分钟来5人结账速度6人/分钟队伍会消化不稳定每分钟来10人结账速度6人/分钟队伍无限增长系统崩溃二、为什么要看「服务时间的二阶矩」P-K公式 / lognormal / Pareto白话问题结账时间「忽快忽慢」很恐怖还是「都很慢」比较恐怖数学解释忽快忽慢方差大比稳定慢更可怕。P-K公式证明服务时间的方差越大平均等待时间就越长核心洞察一个偶尔出现的大延迟比持续的中等延迟更伤系统现实案例情况说明稳定慢平均2分钟每个人都2分钟 → 队伍可预测忽快忽慢有时10秒、有时10分钟 → 那偶尔的10分钟会害后面全部塞车应用场景lognormal / Pareto 分布用来描述真实世界「很常出现的极端慢」事件例如文件下载、网页读取。在CPU调度中你需要关心「有没有某个任务突然卡很久」三、为什么要看「i.i.d. 假设成不成立」白话问题每次事件是不是「独立」且「同分布」数学解释很多简单的排队公式都假设 i.i.d.独立同分布。如果不成立算出来的预测会完全不准确核心洞察真实世界的调度不能用太简单的数学去套现实案例情况说明按键盘wakeup后几乎一定会切换任务switch→ 事件之间相依晚上闲置 vs 早上忙碌分布不一样 → 不是同分布四、为什么要讨论 EEVDF 的 lag 有界性白话问题公平调度器会不会「偏心某个进程」数学解释lag 某个进程「被亏欠」或「多拿」的CPU时间。有界性保证偏心不会无限扩大核心洞察最多偏心一个时间片例如1ms就会修正。这保证了没有进程会被饿死现实案例情况结果没界限某个进程可能永远拿不到CPU饿死有界限最多偏心1ms下次就会补偿离散误差推导因为电脑是「一段一段」给时间时间片不是连续流体所以一定会有小误差。数学证明这个误差很小。这保证了你的Zoom不会因为某个后台进程就卡死五、为什么要算熵率entropy rate白话问题系统的行为「有多乱」能不能预测数学解释熵率衡量系统行为的随机程度。熵越低越规律熵越高越难预测。核心洞察工程师用熵来判断「要不要花力气去做高级预测」现实案例熵值说明对调度的影响熵低很规律例如每10ms切换一次任务好预测好优化熵高很随机例如用户乱按、网络乱入难预测需要更强的调度器总结数学工具白话目的ADF / KPSS检查系统会不会「排队到死」P-K公式证明「忽快忽慢比稳定慢更糟」logNormal / Pareto模拟真实世界的「极端慢」事件i.i.d.检定提醒你「真实世界不简单」EEVDF lag界限保证调度器不会饿死任何进程熵率判断系统行为「多乱、多可预测」