O(1)和CFS调度算法简介

简要介绍linux中的O(1)调度算法和CFS调度算法的雏形（发展及设计思想）

O(1)调度算法

概述： 是linux kernel 2.6引入的一种调度算法，无论系统中有多少进程，调度器总能在恒定时间内完成操作，即时间复杂度为O(1)

什么是调度？

假设这样一个场景，只有一个CPU，然后有两个进程需要执行，可以让它们交替执行。为了实现切换，我们提供一个API函数，这些进程执行一会就主动调用一下这个API函数，实现进程的切换执行，这是一种主动配合式的调度

进程切换的本质：

把当前进程的上下文（也就是CPU的一堆寄存器值）保存到该进程的PCB（进程控制块），然后把另一个进程的上下文放到CPU寄存器中开始执行。

中断抢占式调度：

有些进程在CPU执行过程中可能死锁，这样另一个进程就永远没有执行的机会了。可以利用时钟中断（一旦有中断事件到CPU，CPU就得去执行中断处理程序），在时钟中断的中断处理程序加入调度入口，就能抢到CPU的执行权。可以让每个进程都执行一个时间片（比如100ms），然后每隔一个时间片就会有一个中断事件到来，切换进程的执行。

就绪队列：

准备被CPU执行的进程，会被存储在一个队列中，这个队列就叫就绪队列

等待队列：

当有进程等待锁、IO等待或者sleep的时候，让CPU时间白白浪费了，调度程序需要介入，将其移动到等待队列，等它没有上述情况后再移动到就绪队列

优先级：

当进程数逐渐多起来，这时候进程执行一次后，等下次执行可能需要等长时间，这是不合理（比如键盘输入等1、2s才响应）。需要给每个进程设置优先级，从0-139（这里假设数字越高优先级越大，实际上并不是这样，后面有结介绍）。这样调度就需要先遍历就绪队列，这样复杂度就是O(N)了。

可以按照优先级拆分成不同的队列，0-139一共140个队列，调度可以先从高优先级队列查起，可以通过一个位图(10001000....)，1表示该队列有等待调度的进程，0则无。

active队列和expired队列：

为了防止低优先级进程starvation（也就是一直没有被调度），多添加一个队列expired队列。调度器从active队列中选择最高优先级的进程运行，运行完时间片的进程被移动到expired队列，当active进程中所有进程都被移动到expired队列，直接交换两个队列（active和expired定义为指针，交换队列直接交换指针即可

时间片机制：

到上面这一步，好像跟一开始没啥区别了（也就是进程执行完一次，下一次执行需要经过很长时间，如果进程数量多的话）。故引入时间片机制，优先级越高的进程时间片越长（根据权重划分），需要设定一个最小值，不然进程数多的话有的进程时间片太小，这样调度切换多了，实际CPU执行时间就少了。

这样就是O(1)调度算法的一个雏形了

优点：

• 时间复杂度为O(1)
• 优先级机制

缺点：

• 不够公平

完全公平调度算法

概述： CFS(Completely Fair Scheduler)是Linux内核2.6.23引入的调度算法，旨在更加公平的调度

虚拟运行时间(vruntime)：

为了让优先级较小的进程能“追赶”到公平的水平，引入vruntime的概念，也就是低优先级的vruntime增长的更快，高优先级的进程vruntime增长较慢，可以把vruntime作为衡量任务实际消耗CPU时间的账本，所以为了公平调度，每次选择vruntime最小的进程运行（让它吃个饱

举个例子，假设有三个任务A,B，权重分别为2,1，三个任务刚进入系统，vruntime都是0，调度器先选择优先级高的A执行，运行10ms后，A的vruntime增加5（因为优先级高的进程vruntime增长慢），然后调度选择vrumtime目前最小的B运行10ms后，B的vruntime增加10（低优先级进程vruntime增长快），第三次调度器仍选择vruntime最小的A执行。

把CPU比作很多个蛋糕，任务的优先级比作拿到蛋糕的能力（A拿蛋糕速度快吃得也快，B拿蛋糕速度慢）。调度器通过监控每个任务拿的蛋糕数量（vruntime），优先让蛋糕少的人去拿，确保大家都能吃到蛋糕，同时让能力强的人吃得多一些。

红黑树：

那要怎么去取vruntime最小的进程效率最高呢？答案是红黑树，因为它是一棵近似平衡的二叉搜索树，也就是这颗树最左节点是vruntime最小的进程，也就是需要调度的进程

AVL vs. 红黑树：

红黑树的近似平衡规则：

• 每个节点是红色或黑色（颜色用于控制树的平衡调整）
• 根节点始终是黑色的（确保树的整体平衡从根节点开始）
• 每个叶子节点（nil节点）是黑色（nil节点是所有空子树的占位符）
• 红色节点的子节点必须是黑色的
• 从任一节点到其叶子节点的每条路径必须包含相同数量的黑色节点（黑高）

示例：

   (10B)
  /    \
(5R)   (15R)

插入2：

       (10B)
      /    \
   (5R)    (15R)
  /
(2R)

将5改为黑色，右旋（以5为轴：

    (5B)
   /    \
(2R)   (10B)
          \
          (15R)

而AVL树是严格平衡的，也就是节点的左右子树高度差不超过1，而CFS更看重实时响应性，AVL树需要更加频繁地调整，且红黑树的实现较简单，旋转次数更少，较低的调度延迟。

优点：

• 公平性
• 高效，红黑树操作时间复杂度是O(logN)
• CFS支持调度公平性程序（如通过sched_latenct和sched_min_granularity参数）

缺点：

• 较高复杂度相比O(1)调度算法
• 对实时任务支持较弱

其他

二者的对比：

O(1)调度算法更适合实时系统和对复杂性要求较高的场景，CFS调度是现代通用linux系统的默认调度器，它在公平性和灵活性上显著优于O(1)调度

调度的是线程：

在现代linux内核中，参与调度的实体是线程而不是进程，linux将线程视为轻量级线程(LWP)。

相比于进程：

• 线程的上下文切换开销更小，因为线程共享进程资源，不需要切换整个地址空间等信息
• 符合现代应用程序的并发需求，现代程序常常通过多线程模型来实现高性能并发
• 更好地支持多核架构，不同线程可以同时运行在多个CPU核心上，而且线程粒度更细

实时优先级和普通优先级：

• 0-99：实时优先级，用于实时任务，更高数字表示更高优先级
• 100-139：普通优先级，更低数字表示更高的优先级

nice值：

进程通过一个nice值（对其他进程的友好度，nice越大越友好，越谦让，优先级越低）映射到优先级，nice越大优先级越低

进程优先级是分动态和静态的

在多核模式下，为了防止加锁带来的性能损失，每个CPU核都有自己的调度队列