01_进程调度算法

调度算法影响的是等待时间（进程在就绪队列中等待调度的时间总和），而不能影响进程真在使用 CPU 的时间和 I/O 时间。

非抢占式调度

• 进程从运行状态转到等待状态
• 进程从运行状态转到终止状态

抢占式调度

• 进程从运行状态转到就绪状态
• 进程从等待状态转到就绪状态

先来先服务（First Come First Severd, FCFS）算法

每次从就绪队列选择最先进入队列的进程，然后一直运行，直到进程退出或被阻塞，才会继续从队列中选择第一个进程接着运行

高响应比优先 （Highest Response Ratio Next, HRRN）

高响应比优先 （Highest Response Ratio Next, HRRN）调度算法主要是权衡了短作业和长作业。每次进行进程调度时，先计算「响应比优先级」，然后把「响应比优先级」最高的进程投入运行，「响应比优先级」的计算公式：[插图]

时间片轮转（Round Robin, RR）

最古老、最简单、最公平且使用最广的算法就是时间片轮转（Round Robin, RR）调度算法。

如果时间片设得太短会导致过多的进程上下文切换，降低了 CPU 效率；

通常时间片设为 20ms~50ms 通常是一个比较合理的折中值。

最高优先级（Highest Priority First，HPF）

希望调度程序能从就绪队列中选择最高优先级的进程进行运行，这称为最高优先级（Highest Priority First，HPF）调度算法。

动态优先级

随着时间的推移增加等待进程的优先级。

缺点，可能会导致低优先级的进程永远不会运行。

多级反馈队列（Multilevel Feedback Queue）

多级反馈队列（Multilevel Feedback Queue）调度算法是「时间片轮转算法」和「最高优先级算法」的综合和发展。

优先级越高时间片越短

兼顾了长短作业，同时有较好的响应时间。

Sched_other

在Linux操作系统中，SCHED_OTHER是默认的调度策略，用于普通的应用程序。

在Linux系统中，除了SCHED_OTHER，还有几种实时调度策略，如SCHED_FIFO（先进先出）和SCHED_RR（时间片轮转），它们提供了不同的保证和特性，适用于需要严格时序和性能保证的实时应用程序。

实时调度策略与分时调度策略的主要区别

• 实时调度策略通常保证任务能够获得及时的处理，而不会受到其他低优先级任务的影响。
• 实时任务通常与系统安全和可靠性密切相关，如工业控制系统、音频视频同步处理等。

特点

在Linux操作系统中，SCHED_OTHER是默认的调度策略，用于普通的应用程序。

• 非实时调度：这种调度策略是非实时的，意味着它不保证进程将在特定的时间限制内得到调度执行。
• 标准分时：它使用标准的分时调度算法，通常是抢占式的时间片轮转调度（Preemptive Time-Sliced Round Robin），允许多个进程共享处理器时间。
• 动态优先级：在SCHED_OTHER调度策略下，进程的优先级可能会根据其行为动态调整。例如，如果一个进程使用了过多的CPU时间，它可能会被降低优先级。
• 适合一般应用：这种调度策略适合大多数用户级应用程序，因为它提供了良好的响应性和公平性。
• 自动调度：操作系统会自动管理SCHED_OTHER队列中的进程调度，进程无需特别设置。

Linux进程调度

内存中保存了对每个进程的唯一描述, 并通过若干结构与其他进程连接起来。

调度器面对的情形就是这样, 其任务是在程序之间共享CPU时间, 创造并行执行的错觉, 该任务分为两个不同的部分, 其中一个涉及调度策略, 另外一个涉及上下文切换。

调度策略

根据进程的不同分类Linux采用不同的调度策略。

1. 实时进程：尽快响应⇒基于优先级，采用FIFO或者Round Robin的调度策略。
2. 普通进程：公平占用CPU⇒需要区分交互式和批处理式的不同。
   • 传统Linux调度器提高交互式应用的优先级，使得它们能更快地被调度。
   • CFS和RSDL等新的调度器的核心思想是完全公平。这个设计理念不仅大大简化了调度器的代码复杂度，还对各种调度需求的提供了更完美的支持。

Linux通过将进程和线程调度视为一个，同时包含二者。

进程可以看做是单个线程，但是进程可以包含共享一定资源（代码和/或数据）的多个线程。因此进程调度也包含了线程调度的功能。

linux调度器的演变

1. $O(n)$调度器 $O(n)$调度算法（遍历所有任务）的缺点时当内核有很多任务时，调度器本身会耗费不少时间。

2. $O(1)$调度器 $O(1)$调度器从Linux2.5引入。

3. CFS调度器Completely Fair Scheduler 在2.6内核中引入的，具体为2.6.23，即从此版本开始，内核使用CFS作为它的默认调度器。

$O(n)$调度算法

在$O(n)$算法前，采用基于环形队列的任务管理；添加和删除进程效率很高（具有保护结构的锁）；总而言之，简单快捷。

$O(n)$的算法实现采用基于优先级的设计：

• pick next：对就绪队列（runqueue）中所有进程的优先级进行依次进行比较，选择最高优先级的进程作为下一个被调度的进程。
• 花费时间：系统中任务个数正相关。
• 时间片： 为每个进程赋予时间片，时钟中断递减时间片。
• epoch：Linux2.4调度器保证只有当所有RUNNING进程的时间片都被用完之后，才对所有进程重新分配时间片。确保每个进程都有机会执行。
• 修改优先级：Linux 2.4调度器主要依靠改变进程的优先级，来满足不同进程的调度需求。

实时进程：

• 实时进程的优先级是静态设定的，而且始终大于普通进程的优先级。
• 调度策略：SCHED_FIFO 和 SCHED_RR FIFO
• 对于所有相同优先级的进程，最先进入 runqueue 的进程总能优先获得调度。
• Round Robin：采用更加公平的轮转策略，使得相同优先级的实时进程能够轮流获得调度。

普通进程：

• 用户响应：调度器倾向于提高交互式进程的优先级，因为它们需要快速的用户响应。
• 优先级：由进程描述符中的Counter字段决定 (还要加上 nice 设定的静态优先级) 。
• 进程被创建时子进程的 counter值为父进程counter值的一半，这样保证了任何进程不能依靠不断地 fork() 子进程从而获得更多的执行机会。
• 提高交互式优先级：当所有 RUNNING 进程的时间片被用完之后，调度器将重新计算所有进程的 counter 值，所有进程不仅包括 RUNNING 进程，也包括处于睡眠状态的进程。处于睡眠状态的进程的 counter 本来就没有用完，在重新计算时，他们的 counter 值会加上这些原来未用完的部分，从而提高了它们的优先级。交互式进程经常因等待用户输入而处于睡眠状态，当它们重新被唤醒并进入 runqueue 时，就会优先于其它进程而获得 CPU。从用户角度来看，交互式进程的响应速度就提高了。

主要缺点

1. 可扩展性不好 调度器选择进程时需要遍历整个 runqueue 从中选出最佳人选，因此该算法的执行时间与进程数成正比。另外每次重新计算 counter 所花费的时间也会随着系统中进程数的增加而线性增长，当进程数很大时，更新 counter 操作的代价会非常高，导致系统整体的性能下降。
2. 高负载系统上的调度性能比较低 2.4的调度器预分配给每个进程的时间片比较大，因此在高负载的服务器上，该调度器的效率比较低，因为平均每个进程的等待时间于该时间片的大小成正比。
3. 交互式进程的优化并不完善 Linux2.4识别交互式进程的原理基于以下假设，即交互式进程比批处理进程更频繁地处于SUSPENDED状态。然而现实情况往往并非如此，有些批处理进程虽然没有用户交互，但是也会频繁地进行IO操作，比如一个数据库引擎在处理查询时会经常地进行磁盘IO，虽然它们并不需要快速地用户响应，还是被提高了优先级。当系统中这类进程的负载较重时，会影响真正的交互式进程的响应时间。
4. 对实时进程的支持不够 Linux2.4内核是非抢占的，当进程处于内核态时不会发生抢占，这对于真正的实时应用是不能接受的。

$O(1)$调度算法

由于进程优先级的最大值为139，因此MAX_PRIO的最大值取140

• 普通进程：100~139
• 实时进程：0~99

$O(1)$调度器主要解决了以前版本中的扩展性问题:

• 多个就绪队列链表：为每个优先级都设置一个可运行队列, 即包含140个可运行状态的进程链表，每一条优先级链表上的进程都具有相同的优先级，而不同进程链表上的进程都拥有不同的优先级。
• 优先级位图bitmap：使用一个位(bit)来代表一个优先级，而140个优先级最少需要5个32位来表示， 因此只需要一个int[5]就可以表示位图，该位图中的所有位都被置0，当某个优先级的进程处于可运行状态时，该优先级所对应的位就被置1。
• 内核态抢占：Linux 2.6内核支持内核态抢占，因此更好地支持了实时进程。

$O(1)$调度器跟踪队列：

• 每个优先级水平有两个运行队列。
• 一个用于活动任务，一个用于过期任务。

$O(1)$调度器在Linux2.4的基础上修改：

• 优先级计算方法
• pick next算法

进程优先级

普通进程优先级：

• 每个进程从父进程继承静态优先级。

静态优先级与基本时间片的关系：

• 静态优先级<120，基本时间片=max((140-静态优先级)*20,MIN_TIMESLICE)。
• 静态优先级>=120，基本时间片=max((140-静态优先级)*5, MIN_TIMESLICE)。
• MIN_TIMESLICE为系统规定的最小时间片，静态优先级越高（值越低），进程得到的时间片越长。

当调度程序选择新进程运行时就会使用进程的动态优先级

• 动态优先级=max(100 , min(静态优先级 – bonus + 5) , 139)。
• 惩罚或奖励(bonus)：根据进程过去的平均睡眠时间设定。
• 平均睡眠时间（sleep_avg，位于task_struct结构中）：进程在睡眠状态所消耗的总时间数，这里的平均并不是直接对时间求平均数。平均睡眠时间随着进程的睡眠而增长，随着进程的运行而减少。
• 比如一个进程在某一小段时间交互性很强，那么sleep_avg就有可能暴涨（当然它不能超过 MAX_SLEEP_AVG），但如果之后都一直处于执行状态，那么sleep_avg就又可能一直递减。
• ⇒bonus的含义：交互性强的进程会得到调度程序的奖励（bonus为正），而那些一直霸占CPU的进程会得到相应的惩罚（bonus为负）

交互式进程认定：动态优先级≤3*静态优先级/4 + 28

实时进程：

• 由sys_sched_setschedule()设置，该值不会动态修改。
• 总是比普通进程优先级高，在进程描述符中用rt_priority表示。

pick next 算法

todo

• pick next算法

Linux 2.6的新一代调度器CFS

楼梯调度算法staircase scheduler

楼梯算法(SD)相比$O(1)$算法优势：

• SD删除了$O(1)$调度器中动态修改优先级的复杂代码；淘汰expire数组，简化代码。
• 采用完全公平策略，对交互式进程响应效果更好。

普通进程：

• 多优先级队列进程列表：和$O(1)$算法一样，楼梯算法也同样为每一个优先级维护一个进程列表，并将这些列表组织在active数组中。当选取下一个被调度进程时，SD算法也同样从active数组中直接读取。
• 临时降低优先级：与$O(1)$算法不同在于，当进程用完了自己的时间片后，并不是被移到expire数组中。而是被加入active数组的低一优先级列表中，即将其降低一个级别。不过请注意这里只是将该任务插入低一级优先级任务列表中，任务本身的优先级并没有改变。
• 任务本身优先级为P，当它从第N级台阶开始下楼梯并到达底部后，将回到第N+1级台阶。并且赋予该任务N+1倍的时间片。

实时进程：

• 仍采用FIFO或者Round Robin调度策略。

楼梯算法能避免进程饥饿

• 高优先级的进程会最终和低优先级的进程竞争，使得低优先级进程最终获得执行机会。
• 对于交互式应用，当进入睡眠状态时，与它同等优先级的其他进程将一步一步地走下楼梯，进入低优先级进程队列。当该交互式进程再次唤醒后，它还留在高处的楼梯台阶上，从而能更快地被调度器选中，加速了响应时间。

RSDL(Rotating Staircase Deadline Scheduler)

RSDL也是由Con Kolivas开发的，它是对SD算法的改进。核心的思想还是”完全公平”。没有复杂的动态优先级调整策略。RSDL重新引入了expire数组。它为每一个优先级都分配了一个 “组时间配额”，记为Tg；同一优先级的每个进程都拥有同样的”优先级时间配额”，用Tp表示。当进程用完了自身的Tp时，就下降到下一优先级进程组中。这个过程和SD相同，在RSDL中这个过程叫做minor rotation（次轮询）。请注意Tp不等于进程的时间片，而是小于进程的时间片。下图表示了minor rotation。进程从priority1的队列中一步一步下到priority140之后回到priority2的队列中，这个过程如下图左边所示，然后从priority 2开始再次一步一步下楼，到底后再次反弹到priority3队列中**，如下图所示：**

在SD算法中，处于楼梯底部的低优先级进程必须等待所有的高优先级进程执行完才能获得CPU。因此低优先级进程的等待时间无法确定。RSDL中，当高优先级进程组用完了它们的Tg(即组时间配额)时，无论该组中是否还有进程Tp尚未用完，所有属于该组的进程都被强制降低到下一优先级进程组中。这样低优先级任务就可以在一个可以预计的未来得到调度。从而改善了调度的公平性。这就是RSDL中Deadline代表的含义。

进程用完了自己的时间片time_slice时（下图中T2），将放入expire数组指向的对应初始优先级队列中(priority 1)。

当active数组为空，或者所有的进程都降低到最低优先级时就会触发主轮询major rotation。Major rotation交换active数组和expire数组，所有进程都恢复到初始状态，再一次从新开始minor rotation的过程。

RSDL对交互式进程的支持：和SD同样的道理，交互式进程在睡眠时间时，它所有的竞争者都因为minor rotation而降到了低优先级进程队列中。当它重新进入RUNNING状态时，就获得了相对较高的优先级，从而能被迅速响应。

完全公平的调度器CFS

CFS是最终被内核采纳的调度器。它从RSDL/SD中吸取了完全公平的思想，不再跟踪进程的睡眠时间，也不再企图区分交互式进程。它将所有的进程都统一对待，这就是公平的含义。

CFS对每个CPU维护一个以时间为顺序的红黑树。

CFS的红黑树良好运行的原因

• 红黑树可以始终保持平衡，这意味着树上没有路径比任何其他路径长两倍以上。
• 由于红黑树是二叉树，查找操作的时间复杂度为O(log n)。但是除了最左侧查找以外，很难执行其他查找，并且最左侧的节点指针始终被缓存。
• 对于大多数操作（插入、删除、查找等），红黑树的执行时间为O(log n)，而以前的调度程序通过具有固定优先级的优先级数组使用 O(1)。O(log n) 行为具有可测量的延迟，但是对于较大的任务数无关紧要。
• 红黑树可通过内部存储实现，即不需要使用外部分配即可对数据结构进行维护。

CFS如何实现pick next

• 所有可运行的任务通过不断地插入操作最终都存储在以时间为顺序的红黑树中（由 sched_entity 对象表示）。
• 对处理器需求最多的任务（最低虚拟运行时）存储在树的左侧。
• 处理器需求最少的任务（最高虚拟运行时）存储在树的右侧。
• 为了公平，CFS调度器会选择红黑树最左边的叶子节点作为下一个将获得cpu的任务。这样，树左侧的进程就被给予时间运行了。

tick中断：

• 在CFS中，tick中断首先更新调度信息。然后调整当前进程在红黑树中的位置。
• 调整完成后如果发现当前进程不再是最左边的叶子，就标记need_resched标志，中断返回时就会调用scheduler()完成进程切换。否则当前进程继续占用CPU。

红黑树键值计算

键值由三个因子计算而得：

1. 进程已经占用的CPU时间：对键值影响最大，键值近似于已占用CPU时间。
2. 当前进程的nice值：nice值为1的进程比nice值为0的进程多获得10%的 CPU时间，nice值越大，键值也越大。
3. 当前的CPU负载。

CFS为每个进程都维护两个重要变量：fair_clock和wait_runtime。

• 进程插入红黑树的键值即为fair_clock – wait_runtime。
• fair_clock：一个进程应获得的CPU时间，即等于进程已占用的CPU时间除以当前 runqueue中的进程总数。
• wait_runtime：进程的等待时间。
• fair_clock – wait_runtime：代表了一个进程的公平程度。该值越大，代表当前进程相对于其它进程越不公平。对于交互式任务，wait_runtime长时间得不到更新，因此它能拥有更高的红黑树键值，更靠近红黑树的左边。从而得到快速响应。

调度器管理器

为了支持实时进程，CFS提供了调度器模块管理器。

各种不同的调度器算法都可以作为一个模块注册到该管理器中。不同的进程可以选择使用不同的调度器模块。

2.6.23中，CFS实现了两个调度算法，CFS算法模块和实时调度模块。

CFS 调度模块（在 kernel/sched_fair.c 中实现）用于以下调度策略：

• SCHED_OTHER
• SCHED_BATCH
• SCHED_IDLE

实时调度模块（该模块在 kernel/sched_rt.c 中实现）：

• SCHED_RR
• SCHED_FIFO

CFS组调度

CFS组调度（在 2.6.24 内核中引入）是另一种为调度带来公平性的方式，尤其是在处理产生很多其他任务的任务时。

假设一个产生了很多任务的服务器要并行化进入的连接（HTTP 服务器的典型架构）。不是所有任务都会被统一公平对待， CFS 引入了组来处理这种行为。产生任务的服务器进程在整个组中（在一个层次结构中）共享它们的虚拟运行时，而单个任务维持其自己独立的虚拟运行时。这样单个任务会收到与组大致相同的调度时间。

/proc 接口用于管理进程层次结构，让您对组的形成方式有完全的控制。使用此配置，您可以跨用户、跨进程或其变体分配公平性。

一个两用户示例，用户 A 和用户 B 在一台机器上运行作业。用户 A 只有两个作业正在运行，而用户 B 正在运行 48 个作业。组调度使 CFS 能够对用户 A 和用户 B 进行公平调度，而不是对系统中运行的 50 个作业进行公平调度。每个用户各拥有 50% 的 CPU 使用。用户 B 使用自己 50% 的 CPU 分配运行他的 48 个作业，而不会占用属于用户 A 的另外 50% 的 CPU 分配。

返璞归真的Linux BFS调度器

todo