Linux进程调度策略（CFS调度）详解
|
Linux 进程调度有一个有趣历史。在 2.5 版本之前，Linux 内核采用传统 UNIX 调度算法。然而，由于这个算法并没有考虑 SMP 系统，因此它并不足够支持 SMP 系统。此外，当有大量的可运行进程时，系统性能表现欠佳。 友好一词源自如下想法：当一个任务增加了它的友好值，如从 0 至 +10，该任务通过降低优先级，进而对其他任务更加友好。 CFS 没有使用离散的时间片，而是采用目标延迟，这是每个可运行任务应当运行一次的时间间隔。根据目标延迟，按比例分配 CPU 时间。除了默认值和最小值外，随着系统内的活动任务数量超过了一定阈值，目标延迟可以增加。CFS 调度程序没有直接分配优先级。相反，它通过每个任务的变量 vruntime 以便维护虚拟运行时间，进而记录每个任务运行多久。虚拟运行时间与基于任务优先级的衰减因子有关，更低优先级的任务比更高优先级的任务具有更高衰减速率。对于正常优先级的任务（友好值为 0），虚拟运行时间与实际物理运行时间是相同的。 因此，如果一个默认优先级的任务运行 200ms，则它的虚拟运行时间也为 200ms。然而，如果一个较低优先级的任务运行 200ms，则它的虚拟运行时间将大于 200ms。同样，如果一个更高优先级的任务运行 200ms，则它的虚拟运行时间将小于 200ms。当决定下步运行哪个任务时，调度程序只需选择具有最小虚拟运行时间的任务。此外，一个更高优先级的任务如成为可运行，就会抢占低优先级任务。 下面分析一下 CFS 调度程序是如何工作的。假设有两个任务，它们具有相同的友好值。一个任务是 I/O 密集型而另一个为 CPU 密集型。通常，I/O 密集型任务在运行很短时间后就会阻塞以便等待更多的 I/O；而 CPU 密集型任务只要有在处理器上运行的机会，就会用完它的时间片。 因此，I/O 密集型任务的虚拟运行时间最终将会小于 CPU 密集型任务的，从而使得 I/O 密集型任务具有更高的优先级。这时，如果 CPU 密集型任务在运行，而 I/O 密集型任务变得有资格可以运行（如该任务所等待的 I/O 已成为可用)，那么 I/O 密集型任务就会抢占 CPU 密集型任务。 Linux 也实现了实时调度。采用 SCHED_FIFO 或 SCHED_RR 实时策略来调度的任何任务，与普通（非实时的）任务相比，具有更高的优先级。 Linux 采用两个单独的优先级范围，一个用于实时任务，另一个用于正常任务。实时任务分配的静态优先级为 0?99，而正常任务分配的优先级为 100?139。 这两个值域合并成为一个全局的优先级方案，其中较低数值表明较高的优先级。正常任务，根据它们的友好值，分配一个优先级；这里 -20 的友好值映射到优先级 100，而 +19 的友好值映射到 139。图 1 显示了这个方案。  图 1 Linux系统的调度优先级 CFS 性能Linux CFS 调度程序釆用高效算法，以便选择运行下个任务。每个可运行的任务放置在红黑树上（这是一种平衡的、二分搜索树，它的键是基于虚拟运行时间的）。这种树如下图所示： 图 2 红黑树 ? 当一个任务变成可运行时，它被添加到树上。当一个任务变成不可运行时（例如，当阻塞等待 I/O 时），它从树上被删除。一般来说，得到较少处理时间的任务（虚拟运行时间较小）会偏向树的左侧；得到较多处理时间的任务会偏向树的右侧。 根据二分搜索树的性质，最左侧的结点有最小的键值；从 CFS 调度程序角度而言，这也是具有最高优先级的任务。由于红黑树是平衡的，找到最左侧结点会需要? O(lgN)?操作（这里 N 为树内结点总数）。不过，为高效起见，Linux 调度程序将这个值缓存在变量 rb_leftmost 中，从而确定哪个任务运行只需检索缓存的值。
（编辑：ASP站长网） |
Redis未授权检测漏洞G
严峻Web对抗环境下的W
遭黑客盗走AMD GPU 部
企业级信息防泄漏大方