O(1)调度算法与CFS

目录

引言

linux内核的O（1）进程调度算法介绍

主要特点

工作原理

优点

缺点

运行队列

活动队列

过期队列

active指针和expired指针

O(1)调度器，两个队列的机制

两个队列的机制如下：

这个算法后期被CFS替代

CFS

工作原理：

主要特点：

优势：

发展：

CFS相对于O(1)调度器有以下几个优点：

---

引言

在Linux操作系统中，进程调度算法是核心组件之一，它负责决定哪个进程将获得CPU时间以及它们将获得多长时间。历史上，Linux经历了多种调度算法的演变，其中O(1)调度算法和完全公平调度器（Completely Fair Scheduler，简称CFS）是两个重要的里程碑。
O(1)调度算法，顾名思义，其设计目标是在确定的时间内完成进程调度，不依赖于进程数量。这种算法在Linux内核的2.6版本中引入，它通过使用两个数组来分别管理活动进程和过期进程，实现了固定时间的调度复杂度。O(1)调度算法在当时被认为是革命性的，因为它极大地提高了调度器的性能，尤其是在高负载情况下。
随后，Linux内核在2.6.23版本中引入了CFS，这是一种更为先进和公平的调度算法。CFS不再使用固定的时间片，而是基于虚拟运行时间（vruntime）来调度进程，确保所有进程获得公平的CPU时间份额。CFS的核心思想是维护一个红黑树，根据进程的vruntime来平衡进程的调度，从而实现真正的公平性。
接下来，我们将深入探讨O(1)调度算法与CFS的工作原理、它们各自的特点以及它们对Linux系统性能的影响。通过这一分析，我们能够更好地理解Linux调度器的发展历程，以及它是如何不断优化以适应现代计算需求的。
 

linux内核的O（1）进程调度算法介绍

Linux内核中的O(1)调度器是Linux早期版本中的一个进程调度算法，它在Linux 2.6版本内核中首次引入，并在2.6.23版本内核之前一直作为默认的调度器。O(1)调度器的名称来源于其设计目标：在任何给定的系统负载下，调度决策的时间复杂度都是常数时间，即O(1)。

以下是O(1)调度器的主要特点和原理：

主要特点

两个运行队列：

活动队列：包含所有正在运行的进程。

过期队列：包含所有已经耗尽时间片的进程。

时间片轮转：

每个进程在活动队列中都有一个固定的时间片（quantum）来运行。

当进程用完其时间片后，它会被移到过期队列。

固定优先级：

进程根据其nice值被分配到不同的优先级类，每个优先级类有自己的活动队列和过期队列。

动态优先级调整：

调度器会根据进程的行为动态调整其优先级。

工作原理

选择进程：

调度器从最高优先级的非空活动队列中选择下一个要运行的进程。

如果活动队列为空，则交换活动队列和过期队列，使所有进程重新获得时间片。

时间片管理：

每个进程在运行时都会减少其时间片。

时间片耗尽的进程会被移到过期队列。

队列管理：

为了保持O(1)的时间复杂度，活动队列和过期队列都通过数组实现，每个优先级类对应数组中的一个槽位。

负载平衡：

调度器会在必要时在活动队列和过期队列之间进行负载平衡，确保CPU时间在所有进程之间公平分配。

优点

常数时间调度决策：在任何系统负载下，调度决策都非常快。

良好的交互性能：通过动态优先级调整，调度器能够提供较好的交互性能。

缺点

不公平的负载平衡：在多CPU系统中，O(1)调度器可能不会很好地平衡负载，导致某些CPU比其他CPU更忙。

固定时间片：固定时间片可能导致某些进程在没有完成其工作时就被迫让出CPU。

O(1)调度器最终被CFS（Completely Fair Scheduler，完全公平调度器）取代，CFS从Linux 2.6.23版本开始成为默认的调度器。CFS的目标是提供一个更公平的CPU分配策略，它不是基于固定时间片，而是基于虚拟运行时间（vruntime）来调度进程。

对于两个运行队列而言，可以简单的理解为两个开散列哈希，相同PRI的进程在同一个小桶。

不同的PRI在不同的小桶排队。

运行队列

一个CPU拥有一个runqueue，如果有多个CPU就要考虑进程个数的负载均衡问题  。

优先级

普通优先级：100～139（我们都是普通的优先级，想想nice值的取值范围，可与之对应！）

实时优先级：0～99（不关心）

活动队列

时间片还没有结束的所有进程都按照优先级放在该队列。

nr_active: 总共有多少个运行状态的进程。

queue[140]: 一个元素就是一个进程队列，相同优先级的进程按照FIFO规则进行排队调度,所以，数组下标就是优先级！

从该结构中，选择一个最合适的进程，过程是怎么的呢？

1. 从0下表开始遍历queue[140]。

2. 找到第一个非空队列，该队列必定为优先级最高的队列。

3. 拿到选中队列的第一个进程，开始运行，调度完成！

4. 遍历queue[140]时间复杂度是常数！但还是太低效了！

bitmap[5]:一共140个优先级，一共140个进程队列，为了提高查找非空队列的效率，就可以用5*32个

比特位表示队列是否为空，这样，便可以大大提高查找效率

过期队列

过期队列和活动队列结构一模一样

过期队列上放置的进程，都是时间片耗尽的进程

当活动队列上的进程都被处理完毕之后，对过期队列的进程进行时间片重新计算

active指针和expired指针

active指针永远指向活动队列

expired指针永远指向过期队列

可是活动队列上的进程会越来越少，过期队列上的进程会越来越多，因为进程时间片到期时一直都存在的。

没关系，在合适的时候，只要能够交换active指针和expired指针的内容，就相当于有具有了一批新的活动进程！

在系统当中查找一个最合适调度的进程的时间复杂度是一个常数，不随着进程增多而导致时间成本增加，我们称之为进程调度O(1)算法

O(1)调度器，两个队列的机制

O(1)调度器使用了两个主要的队列机制来管理进程，这两个队列分别是：

运行队列（Run Queue）： 运行队列是所有可运行进程的列表。在O(1)调度器中，运行队列被分为140个不同的优先级队列，每个队列对应一个不同的动态优先级。动态优先级是基于进程的行为和特性（如睡眠时间和运行时间）动态调整的。进程根据其优先级被放置到相应的队列中。

时间片：每个队列中的进程会被分配一个时间片，用于在CPU上执行。时间片的大小与优先级相关，优先级越高，时间片通常越小。

轮转调度：O(1)调度器使用轮转调度算法（Round Robin），在每个优先级队列内部，进程按顺序使用CPU，当一个进程用完其时间片后，它会被放回队列的末尾。

过期队列（Expired Queue）： 当一个进程用完了它的时间片，它会被移到过期队列。这个队列是为了处理那些已经用完时间片的进程。在O(1)调度器中，过期队列同样按照优先级组织。

两个队列的机制如下：

正常工作流程：

当一个进程变为可运行状态时，它会被放入对应的优先级运行队列。

调度器选择最高优先级队列中的第一个进程进行调度。

当进程的时间片用完时，它会被移到过期队列的相应优先级位置。

调度器会检查过期队列，如果有进程，则可能重新计算其优先级，并将其放回运行队列。

优先级调整：

进程的优先级会根据其行为（如是否是I/O密集型或CPU密集型）动态调整。

调度器会定期进行优先级更新，以确保公平性和响应性。

O(1)调度器的设计目标是为了在多处理器系统和大规模负载下提供高效的调度，但是随着时间的推移，它被其他更先进的调度器（如CFS，Completely Fair Scheduler）所取代，因为CFS提供了更好的性能和更公平的调度策略。CFS不再使用固定的时间片和优先级队列，而是采用红黑树来管理进程，并试图为所有进程提供相等的CPU时间份额。

这个算法后期被CFS替代

O(1)调度器在Linux内核中并不是一直被使用的。虽然它在Linux 2.6系列内核中作为默认调度器引入，并且在一段时间内得到了广泛的使用，但它最终被更先进的调度器所取代。

具体来说，O(1)调度器在Linux 2.6.23内核版本中被完全公平调度器（Completely Fair Scheduler, CFS）所取代。CFS是一个基于红黑树的调度器，它旨在提供一个更加公平和高效的CPU时间分配策略，而不是简单地基于固定时间片。CFS的目标是为所有运行在系统上的进程提供等量的CPU时间，这被称为“完全公平”。

CFS

完全公平调度器（Completely Fair Scheduler, CFS）是Linux内核中的一个调度器，它自Linux 2.6.23版本开始成为默认的CPU调度器。CFS的设计目标是提供一个对所有进程都公平的CPU时间分配策略。以下是CFS的主要特点和介绍：

工作原理：

基于红黑树：CFS使用一种数据结构叫做红黑树来管理可运行的进程。每个进程节点都存储了该进程的虚拟运行时间（vruntime），这是CFS用来决定调度顺序的关键指标。

vruntime：虚拟运行时间是CFS用来衡量一个进程应该获得多少CPU时间的一种方式。vruntime越低的进程会获得更多的CPU时间。

时间片：尽管CFS不是基于固定时间片的，但它仍然会根据系统的负载和进程的数量来分配一个大致的时间片。这个时间片是动态调整的。

主要特点：

公平性：CFS试图确保所有可运行进程获得相等的CPU时间份额，这是通过计算每个进程的vruntime并选择vruntime最小的进程来执行的。

多核优化：CFS能够有效地在多核处理器上分配负载，它尝试保持负载均衡，避免在某些核心上堆积太多的工作。

动态优先级调整：CFS会根据进程的行为和系统负载动态调整进程的优先级，这有助于优化系统性能和响应时间。

睡眠公平性：CFS还考虑了进程的睡眠时间，确保那些睡眠时间较长的进程在醒来时能够获得优先的CPU时间。

可扩展性：CFS的设计使其易于扩展和适应不同的工作负载和硬件架构。

优势：

高效的负载均衡：CFS通过其负载均衡算法，确保了在多核系统上CPU时间分配的均衡。

适应性：CFS能够适应各种不同的工作负载，无论是CPU密集型、I/O密集型还是交互式任务。

低延迟：CFS的设计有助于减少调度延迟，提高系统的响应性。

发展：

自CFS被引入以来，它一直是Linux内核中CPU调度的核心部分，并且随着时间的推移，它不断地被社区的开发者们改进和优化，以适应不断变化的硬件和软件需求。

总的来说，CFS是Linux内核中一个非常重要的组件，它通过其独特的调度策略，为Linux系统提供了高效、公平和响应迅速的CPU时间管理。

CFS相对于O(1)调度器有以下几个优点：

更好的多核支持：CFS能够更好地在多核处理器上平衡负载。

动态调整：CFS根据进程的行为动态调整其优先级，而不是依赖于固定的时间片。

公平性：CFS使用虚拟运行时间（vruntime）来确保所有进程公平地分享CPU时间。

可扩展性：CFS的设计更加模块化，易于扩展和维护。

自Linux 2.6.23版本以来，CFS一直是Linux内核的默认调度器，并且随着时间的推移，它不断地被改进和优化。因此，O(1)调度器在Linux内核的发展历程中已经被淘汰，不再是现代Linux系统的标准调度器。