首页 文章

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

提问于
浏览 次
2

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

摘自Robert Love的Linux内核开发：

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

让我们假设以下场景 . 有些进程在较低优先级的类中等待，并且进程正在连续地添加到更高优先级的类中 . 低优先级的流程不会饿死吗？

linux process linux-kernel operating-system starvation

2 回答

  • 1

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

    • 老化，进程在系统中的时间越长，优先级越高 .

    • 调度算法为每个进程提供一个使用CPU的时间量程 . 时间 - 量子变化，通常，交互过程被给予较低的时间 - 量子，因为它们花费更多时间进行I / O，而耗时/计算过程被给予更大的时间量 . 在进程运行其时间量程之后，它将被置于过期队列中，直到系统中没有活动进程 . 然后，过期的队列成为活动队列，反之亦然 . 这是防止饥饿的两种方法 .

    回复于
  • 1

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

    每个调度实体都有一个与之关联的 sched_entity 结构，其快照如下所示

    struct sched_entity {
    ...
    u64 exec_start;
    u64 sum_exec_runtime;
    u64 vruntime;
    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 存储流程执行期间虚拟时钟已经过的时间量 .

    How vruntime is calculated?

    无视所有复杂的计算，计算方法的核心概念是： -

    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的过程重新处理值为1，重量= 1024 / 1.25 = 820（约）

    Points drawn from above

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

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

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

    调用调度程序时，内核基本上会选择具有最小密钥（最左边的节点）的任务并将其分配给CPU .

    具有较小键的元素将更多地放置在左侧，因此可以更快地安排 .

    • 当进程运行时，它的 vruntime 将稳定增加，因此它最终会在红黑树中向右移动 . 因为 vruntime 对于更重要的过程增加得更慢，所以它们也会向右移动得更慢，因此他们被安排的机会更大，更少重要的过程 - 按要求 .

    • 如果进程休眠，其 vruntime 将保持不变 . 因为每个队列 min_vruntime 会在此期间增加，所以睡眠过程将在唤醒后更多地放在左边，因为密钥（如上所述）变小了 .

    因此，如果没有CPU，则没有机会将饥饿作为优先级较低的进程，其最小值将会最小，因此密钥将最小，因此它会快速移动到树的左侧并因此进行调度 .

    回复于

相关问题