深入探讨Linux的进程调度器
发布日期: 2024-09-18 17:47 信息来源: 望获Linux-CSDN

 Linux操作系统作为一个开源且广泛应用的操作系统,其内核设计包含了许多核心功能,而进程调度器(Scheduler)就是其中一个至关重要的模块。进程调度器负责决定在任何给定的时刻哪个进程可以运行,以及其运行的顺序。这篇文章将详细探讨Linux进程调度器的工作原理、主要算法、调度策略以及其在实际操作中的应用。

     进程调度是指操作系统决定在多道程序环境下如何分配CPU时间给多个进程或线程的过程。在一个现代操作系统中,通常有多个进程或线程需要执行,但是CPU的核心数量有限,因此需要通过调度来合理分配这些有限的计算资源。Linux进程调度的目标包括以下几个方面:


响应时间:保证交互式进程有良好的响应时间。

吞吐量:尽可能多地完成任务,提高系统的整体吞吐量。

公平性:确保所有进程都有机会获得CPU时间,避免饥饿现象。

实时性:对于实时系统,调度器应能确保实时任务在其时间约束内完成。

     为达到以上目标,Linux按照调度的优先级,分别实现了DEADLINE调度策略、实时(RT)调度策略、完全公平调度策略等。


9a2c43c8360b4c9eb1f6f6ddef4ebb8c.png


图1 Linux调度策略的优先次序


     如图1所示[1],Linux在调度过程中首先尝试在最高级别的策略模块中寻找调度实体(即进程),如果没找到,则到下一级的策略模块中寻找,如果都没找到,则进入idle状态。例如,Linux内核如果在DEADLINE策略模块中找到了调度实体,就会在处理器上调度运行该实体,而不会继续到RT调度策略模块中寻找。接下来分节介绍Linux中最常用的DEADLINE、RT以及完全公平调度策略模块,又称调度器。DEADLINE调度器

     Linux内核中的DEADLINE调度器是一种实时调度策略,旨在满足具有严格时间要求的实时任务的需求。它在设计上结合了EDF(Earliest Deadline First)和CBS(Constant Bandwidth Server)两种经典的实时调度算法,为实时应用程序提供了更可靠和可预测的执行环境。

     Linux DEADLINE调度器是Linux内核自3.14版本以来引入的调度策略,其目的是为实时任务提供精确的时间控制和调度保证。DEADLINE调度器通过为每个任务分配三个关键参数——开始时间(Start Time)、截止时间(Deadline)和运行时间(Runtime),来确定任务的执行顺序和调度行为。

     调度器的目标是在任务的截止时间到达之前,完成所有具有时间约束的任务。如果任务没有在截止时间前完成,通常会被视为任务失败或延迟,这在硬实时系统中是不可接受的。

     DEADLINE调度器基于EDF(Earliest Deadline First)的思想,即在系统中,优先选择截止时间最早的任务执行。此外,结合CBS(Constant Bandwidth Server)机制,DEADLINE调度器还能控制任务的CPU时间消耗,防止任务因超出分配的时间片而影响系统的整体实时性能。

     Linux DEADLINE调度器的主要应用场景是硬实时系统,如工业控制系统、机器人控制、航空航天等领域,这些系统对任务的时间精度要求非常高,任务的延迟或未按时完成会导致严重的后果。通过DEADLINE调度器,系统可以确保任务在其指定的截止时间内完成。多媒体应用,如音频和视频流处理,要求任务以固定的周期执行,并在特定时间内完成,以保证输出的连续性和质量。DEADLINE调度器可以帮助这些任务获得所需的CPU时间,从而避免丢帧或音视频不同步的问题。以及高精度定时任务,如在金融交易系统、科学计算、医疗设备等场景中,高精度的定时任务非常重要。DEADLINE调度器能够确保这些任务按预定时间精确执行,满足系统的严格要求。

     DEADLINE调度器的缺点是相比于普通调度器,DEADLINE调度器的配置参数较多,需要用户对任务的时间需求有详细了解,这对应用开发者提出了更高的要求。另外,DEADLINE调度器需要系统有足够的资源来满足实时任务的要求,当任务过多或系统资源有限时,可能会出现任务调度失败的情况。最后,DEADLINE调度器缺乏弹性,在负载非常动态的系统中,DEADLINE调度器可能不如CFS等调度器灵活,因为它严格依赖于预先设定的时间参数。


RT调度器

     RT调度器是Linux内核中专门为实时任务设计的调度器,它为那些对延迟敏感的任务提供了更高的调度优先级,以确保它们能够在预定时间内执行。Linux中主要有两种RT调度策略:SCHED_FIFO 和 SCHED_RR,它们都是基于优先级的调度策略,与普通调度策略相比,RT调度策略提供了更严格的时间保证。

     SCHED_FIFO(First In, First Out):这是一个简单的实时调度策略,任务按优先级排序,优先级相同的任务按到达顺序执行。SCHED_FIFO任务一旦获得CPU资源,将持续运行,直到任务主动让出CPU或被更高优先级的任务抢占。没有时间片的概念,这意味着低优先级的任务可能会被高优先级任务“饿死”。

     SCHED_RR(Round-Robin):SCHED_RR与SCHED_FIFO类似,但它在相同优先级的任务之间实现了时间片轮转。每个任务在获得CPU时会运行一个时间片(默认100ms),然后让位给同一优先级的下一个任务。这样可以防止同一优先级的任务发生饥饿现象。

     RT调度器具有严格的优先级控制,RT调度策略减少了调度延迟,保证了任务在规定时间内获得CPU资源。在需要高可靠性和时间精度的场景中,RT调度器提供了比普通调度器更高的稳定性和可预测性。

     RT调度器的缺点是高优先级的RT任务可能长期占用CPU,导致低优先级任务得不到执行,甚至可能导致系统不响应(例如,一个SCHED_FIFO任务如果没有主动释放CPU,系统将无法响应其他任务)。另外RT调度器配置复杂,配置复杂:合理配置RT调度器的优先级和时间片需要深入了解任务的时间需求,配置不当可能导致系统不稳定或性能下降。RT调度器对资源的占用较为刚性,在动态负载环境下可能表现不佳。


完全公平调度器

     Linux内核的完全公平调度器(Completely Fair Scheduler, CFS)是目前Linux系统中默认的进程调度器,它旨在提供一个公平、可扩展且高效的调度机制。CFS调度器的设计理念是尽量公平地分配CPU时间,使得每个任务都能获得与其优先级相符的CPU时间份额。

     在CFS中,公平的概念体现在所有任务都应该在相同优先级的情况下,获得相等的CPU时间份额。CFS通过维护每个任务的“虚拟运行时间”来实现这一点。任务的虚拟运行时间越少,意味着它获得的CPU时间越少,因此CFS会优先调度虚拟运行时间较少的任务,以实现CPU时间的公平分配。

     CFS使用红黑树(Red-Black Tree)数据结构来管理所有可运行的任务。红黑树是一种自平衡二叉搜索树,能够在O(log N)时间内插入、删除和查找元素。CFS将所有任务按其虚拟运行时间排序存储在红黑树中,每次调度时,选择树中最左边(虚拟运行时间最少)的任务来运行。

     最后,CFS调度器与cgroups(Control Groups)紧密结合,允许管理员对任务组设置CPU资源的配额。通过cgroups,系统管理员可以将进程划分为不同的组,并为每个组分配CPU时间份额,从而实现更精细的资源控制。

d04658c51d44467386bf02ccc98cef9f.png

图2 Linux完全公平调度策略与Cgroup的进程组的结合


     如图2所示,与Cgroup结合后,Linux完全公平调度的实体,按照调度任务组形成了一个树状结构。在进行调度实体选择时,调度器首先从树的根结点(与处理器直接对应的调度组),逐层选取最佳调度实体,一直到叶子结点(与具体进程对应)。


望获自适应调度器

     最后简单介绍一下,国科环宇在研的望获自适应调度器。该调度器针对Linux实时调度器配置和运行不够灵活的缺点,对进程的行为进行在线分析,并利用机器学习的方法对进程的调度进行配置,以做到实时性和灵活性的兼顾。


参考文献

[1] Digging into the Linux scheduler

http:// https://deepdives.medium.com/digging-into-linux-scheduler-47a32ad5a0a8


在线客服