linux - linux进程调度器如何防止进程饥饿

Question

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

摘自 Robert Love 的 Linux 内核开发:

The main entry point into the process schedule is the function schedule() , defined in kernel/sched.c .This is the function that the rest of the kernel uses to invoke the process scheduler, deciding which process to run and then running it. schedule() is generic with respect to scheduler classes.That is, it finds the highest priority scheduler class with a runnable process and asks it what to run next. Given that, it should be no surprise that schedule() is simple.The only important part of the function—which is otherwise too uninteresting to reproduce here—is its invocation of pick_next_task() , also defined in kernel/sched.c .The pick_next_task() function goes through each scheduler class, starting with the highest priority, and selects the highest priority process in the highest priority class.

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

Answer 1

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

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

struct sched_entity {    ...    u64 exec_start;    u64 sum_exec_runtime;    u64 vruntime;    u64 prev_sum_exec_runtime;    ...}

The above four attributes are used to track the runtime of a process and using these attributes along with some other methods(update_curr() where these are updated), the virtual clock is implemented.When a process is assigned to CPU, exec_start is updated to current time and the consumed CPU time is recorded in sum_exec_runtime. When process is taken off from CPU sum_exec_runtime value is preserved in prev_sum_exec_runtime. sum_exec_runtime is calculated cumulatively. (Meaning it grows monotonically).

vruntime stores the amount of time that has elapsed on virtual clock during process execution.

How vruntime is calculated?

Ignoring all the complex calculations, the core concept of how it is calculated is :-

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

这里的 delta_exec 是进程分配给 CPU 和从 CPU 中取出的时间差，而 load.weight 是进程的权重，它取决于优先级(Nice Value ).通常，进程的 nice 值增加 1 意味着它获得的 CPU 时间减少 10%，从而导致权重降低。NICE 值为 0 的进程，权重 = 1024Process re-Niced 值为 1，weight = 1024/1.25 = 820(approx)

从上方绘制的点

• 因此 vruntime 在进程获得 CPU 时增加
• 并且 vruntime与低优先级进程相比，高优先级进程的增长缓慢。

运行队列在红黑树中维护，每个运行队列都有一个min_vruntime变量与之关联，它保存运行队列中所有进程中最小的vruntime . (min_vruntime 只能增加，不能随着进程的调度而减少)。

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

调用调度程序时，内核基本上选择具有最小键(最左边的节点)的任务并将其分配给 CPU。

key 越小的元素越靠左，调度越快

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

因此，如果被剥夺了 CPU，则不会有饥饿的机会，因为优先级较低的进程将使其 vruntime 最小，因此 key 将最小，因此它会快速移动到树的左侧，因此预定。