Linux中的实时调度

Question

今天早上我读到关于Linux实时调度的内容。根据罗伯特·洛夫（Robert Love）所著的《Linux系统编程》一书，有两种主要的调度方式。一种是SCHED_FIFO，先进先出，另一种是SCHED_RR，轮询。我了解了先进先出和轮询算法的工作原理。但是我们有一个系统调用，

sched_setscheduler (pid_t pid, int policy, const struct sched_parem *sp)

我们可以明确地为进程设置调度策略。因此，在某些情况下，由root运行的两个进程可能具有不同的调度策略。一个进程具有SCHED_FIFO，另一个进程具有SCHED_RR，并且具有相同的优先级。在这种情况下，哪个进程将首先被选中？FIFO类进程还是RR类进程？为什么？

考虑这种情况。有三个进程A、B、C，它们都具有相同的优先级。A和B是RR类进程，C是FIFO类进程。 A和B都是可运行的（因此在某些时间间隔内交替运行）。当前A正在运行。现在C变得可运行。在这种情况下，

1. A will preempt for C, or
2. A will run until its timeslice goes zero and let C run. Or
3. A will run until its timeslice goes zero and let B run.
   a) here after B runs till its timeslice becomes zero and let C run or
   b) after B runs till its timeslice becomes zero and let A run again (then C will starve untill A and B finishes)

- theB

---

注：自从Linux 3.14版本以后，新增了一种调度策略叫做SCHED_DEADLINE（http://en.wikipedia.org/wiki/SCHED_DEADLINE）。该策略实现了最早期限优先（EDF）调度算法。在该策略下，每个任务都被分配了一个截止时间，并执行最早截止时间的任务。 - Claudio

Answer 1

在实时调度中，FIFO和RR的意义与非实时调度中不完全相同。进程始终以FIFO方式被选择，但是SCHED_FIFO的时间量子没有限制，而SCHED_RR的时间量子有限。

SCHED_FIFO进程不会抢占相同优先级的SCHED_RR进程。

sched_setscheduler(2) - Linux手册页面

......

"进程的调度策略确定了它将插入到具有相等静态优先级的进程列表中的位置以及它将如何在此列表内移动。所有调度都是可抢占的：如果具有更高静态优先级的进程变为就绪状态，则当前运行的进程将被抢占并返回到其静态优先级级别的等待列表中。调度策略仅确定相同静态优先级的可运行进程列表中的排序顺序。"

......

"SCHED_FIFO进程运行直到被I/O请求阻塞、被更高优先级进程抢占或调用sched_yield(2)为止。"

......

"当SCHED_FIFO进程变得可运行时，它将被插入到其优先级列表的末尾。"

......

"SCHED_RR: Round Robin调度

SCHED_RR是SCHED_FIFO的简单增强版。上面描述的所有内容都适用于SCHED_RR，除了每个进程只允许运行一定的最大时间量子之外。如果一个SCHED_RR进程运行时间等于或长于时间量子，它将被放置在其优先级列表的末尾。一个被更高优先级进程抢占并随后恢复执行作为正在运行进程的SCHED_RR进程将完成其剩余的轮流时间量子。"

- svenfx

---

那么你的意思是，所有具有相同优先级的进程将被放置在同一个队列中。其中FIFO类进程将运行直到完成或阻塞，但RR类进程仅运行其时间片。我理解得对吗？ - theB

是的，我理解手册的方式也是这样。其他实时系统定义FIFO和RR的方式也是相同的（例如，Freescale的MQX RTOS）。 - svenfx

@theB 但是Robert也说：“当FIFO类进程阻塞时，调度程序会将其从可运行进程列表中移除。当它再次变为可运行状态时，它将被插入到其优先级进程列表的末尾。因此，在任何其他高于或等于其优先级的进程停止执行之前，它都不会运行。”（第189页）。这不是矛盾吗？然而，这就是手册上所说的。 - svenfx

@theB 我认为你指的是罗伯特书的第一版（2007年），正如我在之前的评论中提到的那样。第三版（2010年）不再有这种矛盾了。它所说的与man页完全相同，因此我们最初的假设似乎又是正确的：SCHED_FIFO进程不会抢占相同优先级的SCHED_RR进程。 - svenfx

非常感谢您，Grossamer。正如您所说，我正在使用第一版的PDF。 :-) - theB

Answer 2

man sched_setscheduler详细解释了这些调度策略。

在这种情况下，由于两个实时进程具有相同的优先级，它们中没有一个会抢占另一个。一个SCHED_FIFO进程一直运行直到自己阻塞，SCHED_RR进程一直运行直到自己阻塞或时间片过期。

- Maxim Egorushkin

Answer 3

根据手册，我认为1是答案。A、B是RR策略，C是FIFO策略。由于RR也是增强型FIFO，所以它们都是FIFO类。

由于它们都具有相同的优先级，并且手册说：“调用sched_setscheduler()或sched_setparam(2)将把pid标识的SCHED_FIFO（或SCHED_RR）进程放在列表的开头，如果它是可运行的，则可能抢占当前正在运行的进程，如果它具有相同的优先级。（POSIX.1-2001规定该进程应该转到列表的末尾。）”

一旦调用sched_setscheduler将C的策略设置为FIFO，C将抢占A。

- annabel1832

Answer 4

我对这两个不同类别的理解是，SCHED_FIFO进程永远不会被内核抢占。即使另一个“SCHED_FIFO”类进程正在等待轮到它...

而SCHED_RR策略会更加平均地共享CPU资源。调度程序将让SCHED_RR进程运行一段时间，然后仅在让另一个SCHED_RR进程运行之前抢占它。这正是轮询。

SCHED_FIFO在某种意义上更“强大”，因为如果SCHED_FIFO进程从未yield()给内核或在单核设备上调用系统调用，则所有其他实时进程可能永远不会运行。

- yves Baumes

---

调度程序将允许SCHED_RR进程运行一段时间，然后仅在让另一个SCHED_RR进程轮流运行时才抢占它是不正确的。可以是任何具有相同优先级的调度类进程（接替SCHED_RR进程）。 - Maxim Egorushkin

这个说法不准确。实时（RT）进程有优先级，而优先级较低的SCHED_FIFO进程将被抢占以运行优先级更高的进程。 - cha0site