linux 进程调度程序如何防止进程饥饿

Question

我读过 linux 内核包含许多调度类，每个类都有自己的优先级。为了选择一个新进程来运行，进程调度器从最高优先级到最低优先级迭代。如果在类中找到可运行的进程，则选择优先级最高的进程从该类中运行。

摘自 Robert Love 的 Linux 内核开发：

进程调度的主要入口点是函数 schedule() ，定义在 kernel/sched.c 中。这是内核其余部分用来调用进程调度程序，决定运行哪个进程然后运行它的函数。schedule() 对于调度程序类是通用的。也就是说，它找到具有可运行进程的最高优先级调度程序类，并询问它接下来要运行什么。鉴于此，schedule() 很简单也就不足为奇了。该函数唯一重要的部分——否则在这里重现就太无趣了——是它对 pick_next_task() 的调用，它也在 kernel/sched.c 中定义。 pick_next_task() 函数遍历每个调度程序类，从最高优先级开始，并在最高优先级类中选择最高优先级的进程。

让我们想象一下下面的场景。有一些进程在较低优先级中等待，并且进程不断被添加到较高优先级中。低优先级的进程不会饿死吗？

Answer 1

Linux内核实现了基于虚拟时钟的完全公平调度算法。

每个调度实体都有一个sched_entity与之关联的结构，其快照看起来像

结构调度实体{
    ...
    u64 exec_start;
    u64 sum_exec_runtime;
    u64 虚拟机；
    u64 prev_sum_exec_runtime;
    ...
}

以上四个属性用于跟踪进程的运行时间，并使用这些属性以及其他一些方法（update_curr()更新这些方法），实现虚拟时钟。当一个进程被分配给 CPU 时，exec_start更新为当前时间，消耗的 CPU 时间记录在sum_exec_runtime. 当进程从 CPU 中取出时，sum_exec_runtime值保留在prev_sum_exec_runtime. sum_exec_runtime是累计计算的。（意味着它单调增长）。

vruntime 存储进程执行期间虚拟时钟上已经过去的时间量。

如何vruntime计算？

忽略所有复杂的计算，其计算方式的核心概念是：-

vruntime += delta_exec_weighted;
delta_exec_weighted = delta_exec * (NICE_0_LOAD/load.weight);

这delta_exec是分配给 CPU 的进程和从 CPU 中取出的进程之间的时间差，而进程load.weight的权重取决于优先级（Nice 值）。通常，进程的 nice 值增加 1 意味着它的 CPU 时间减少 10%，从而导致权重减少。处理 NICE 值为 0，权重 = 1024 重新处理 NICE 值为 1，权重 = 1024/1.25 = 820（大约）

从上面绘制的点

• 所以vruntime当一个进程获得 CPU 时增加
• 而vruntime慢慢更高优先级的进程增加低优先级的进程进行比较。

运行队列维护在红黑树中，每个运行队列都有一个min_vruntime与之关联的变量，该变量保存vruntime运行队列中所有进程中最小的一个。（min_vruntime只能增加，不能减少，因为进程将被安排）。

红黑树节点的key是 process->vruntime - min_vruntime

当调度器被调用时，内核基本上选择具有最小键（最左边的节点）的任务并为其分配 CPU。

具有较小键的元素将被放置在更靠左的位置，因此被安排得更快。

1. 当一个进程运行时，它vruntime会稳步增加，所以它最终会在红黑树中向右移动。因为vruntime对于更重要的过程增加得更慢，它们也会更慢地向右移动，所以对于不太重要的过程，它们被安排的机会更大 - 正如需要的那样。
2. 如果一个进程休眠，它vruntime会保持不变。由于每个队列min_vruntime同时会增加，因此唤醒后睡眠进程将被放置在更靠左的位置，因为密钥（上面提到的）变小了。

因此，作为低优先级进程，如果被剥夺 CPU，则不会有饥饿的机会，它将具有vruntime最小且因此键将最小，因此它会快速移动到树的左侧并因此被调度。