3

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

摘自 Robert Love 的 Linux 内核开发：

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

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

4

2 回答 2

5

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

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

结构 sched_entity {
    ...
    u64 执行开始；
    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 Value）。通常，进程的 nice 值增加 1 意味着它会减少 10% 的 CPU 时间，从而减少重量。NICE 值为 0 的过程，权重 = 1024 重新NICE 值为 1 的过程，权重 = 1024/1.25 = 820（大约）

从上面绘制的点

  • 所以vruntime当一个进程获得 CPU 时增加
  • 与vruntime较低优先级的进程相比，较高优先级的进程缓慢增加。

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

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

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

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

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

因此，如果 CPU 被剥夺，作为较低优先级的进程就没有饥饿的机会，它将拥有其vruntime最小的，因此密钥将是最小的，因此它会快速移动到树的左侧并因此被调度。

于 2016-10-02T18:32:09.170 回答
1

它确实会饿死。有很多方法可以处理这种情况。

  1. 老化，进程在系统中的时间越长，优先级越高。
  2. 调度算法为每个进程提供使用 CPU 的时间量。时间量子不同，通常，交互过程被赋予较低的时间量子，因为它们花费更多时间进行 I/O，而耗时/计算过程被给予更大的时间量子。进程运行其时间段后，将其放入过期队列中，直到系统中没有活动进程。然后，过期队列变为活动队列，反之亦然。这是防止饥饿的两种方法。
于 2016-10-02T17:27:02.883 回答