目录
处理机调度概述
1. 作业调度（Job Scheduling）
2. 中级调度（Medium-term Scheduling）
3. 进程调度（Process Scheduling）
调度算法
1. 先来先服务（FCFS）
2. 最短作业优先（SJF）
3. 优先级调度
4. 轮转法（RR）
5. 多级队列调度
6. 多级反馈队列调度
实时调度
实现实时调度的基本条件
实时调度算法
1. 最早截至时间优先（EDF）
2. 最低松弛度优先（LLF）
优先级倒置
实时调度的应用场景
实例：Linux 进程调度
概述
CFS 调度算法
调度策略
CPU 带宽控制
处理机调度是操作系统中的一项重要功能，其目的是管理和分配计算机系统的资源，特别是中央处理单元（CPU），以使多个进程或任务能够高效地运行。这种调度机制可以确保系统资源得到充分利用，并根据优先级和需求将资源分配给不同的进程。
处理机调度通常分为三个层次：作业调度、中级调度和进程调度。
1. 作业调度（Job Scheduling）
作业调度是处理机调度的最高层次，主要负责从外部存储设备（如磁盘）中选择作业并将其加载到内存中。作业调度的主要任务包括：
- 选择作业：从后备队列中选择合适的作业进入内存。
- 资源分配：为选中的作业分配必要的资源，如内存、I/O设备等。
- 创建进程：将作业转换为进程，使其能够在系统中执行。
作业调度通常在作业的生命周期开始时进行，决定了哪些作业可以进入系统并开始执行。
2. 中级调度（Medium-term Scheduling）
中级调度也称为交换调度（Swapping），主要目的是优化内存利用率和系统吞吐量。其主要任务包括：
- 挂起进程：当内存资源不足时，将一些暂时不需要运行的进程挂起，释放内存空间。
- 恢复进程：当内存资源充足时，将挂起的进程重新加载到内存中，使其处于就绪状态。
中级调度通过动态调整内存中运行的进程数量，确保系统在高负载下仍能高效运行。
3. 进程调度（Process Scheduling）
进程调度是处理机调度中最基本也是最频繁的一种，它决定了哪个进程将获得CPU时间。进程调度的主要任务包括：
- 选择进程：从就绪队列中选择一个进程，将CPU分配给该进程。
- 分配CPU时间：根据调度算法（如先来先服务、最短作业优先、轮转法等）分配CPU时间片。
- 切换上下文：在不同进程之间切换CPU时，保存和恢复进程的上下文信息。
进程调度的频率非常高，通常每隔几十毫秒就会进行一次，以确保系统能够快速响应用户请求和系统事件。
调度算法
处理机调度算法旨在实现几个关键目标，包括最大化 CPU 的利用率、缩短平均周转时间和平均等待时间、提高系统的吞吐量，以及兼顾不同类型的作业和进程。常见的调度算法包括：
1. 先来先服务（FCFS）
**先来先服务（First-Come, First-Served, FCFS）**算法按照进程到达的顺序进行调度。特点包括：
- 简单易实现：实现起来非常简单，只需维护一个队列。
- 公平性：所有进程按照到达顺序依次获得CPU时间。
- 缺点：可能导致长时间的等待，特别是当一个长作业在队列前面时，会导致后续短作业的等待时间过长（即“长尾效应”）。
2. 最短作业优先（SJF）
**最短作业优先（Shortest Job First, SJF）**算法优先调度预计运行时间最短的进程。特点包括：
- 高效性：能够最小化平均等待时间。
- 两种形式：非抢占式（进程一旦开始运行，直到完成）和抢占式（又称最短剩余时间优先，SRTF，当前运行的进程可以被新到达的更短作业抢占）。
- 缺点：需要准确预测每个作业的运行时间，实际应用中较为困难；可能导致“饥饿”现象，即长作业可能长时间得不到调度。
3. 优先级调度
**优先级调度（Priority Scheduling）**算法根据进程的优先级进行调度，优先级高的进程先调度。特点包括：
- 灵活性：可以根据进程的重要性或紧急程度分配优先级。
- 两种形式：静态优先级（优先级在进程生命周期内不变）和动态优先级（优先级可以随时间改变）。
- 缺点：可能导致“饥饿”现象，即低优先级的进程可能长期得不到调度。可以通过“老化”技术（随着等待时间增加而提高优先级）来解决。
4. 轮转法（RR）
**轮转法（Round Robin, RR）**算法为每个进程分配固定的时间片，轮流调度。特点包括：
- 时间片：每个进程在其时间片内运行，如果时间片用完且进程未完成，则将其放回就绪队列尾部。
- 公平性：所有进程轮流获得CPU时间，适用于时间共享系统。
- 响应时间：能够提供较好的响应时间，但时间片大小的选择需要权衡，过大则类似于FCFS，过小则增加上下文切换开销。
5. 多级队列调度
**多级队列调度（Multilevel Queue Scheduling）**算法将进程分成多个队列，每个队列使用不同的调度算法。特点包括：
- 分层管理：常见的分层方式包括前台/后台进程、交互式/批处理进程等。
- 不同策略：每个队列可以使用不同的调度算法（如前台队列使用RR，后台队列使用FCFS）。
- 优先级：通常前台队列优先级高于后台队列，即使后台队列有进程就绪，前台队列的进程也会优先调度。
6. 多级反馈队列调度
**多级反馈队列调度（Multilevel Feedback Queue Scheduling）**是多级队列调度的改进版本。特点包括：
- 动态调整：进程可以在不同优先级的队列之间移动，通常新进程进入高优先级队列，如果没有完成则逐步降低优先级。
- 适应性：能够动态调整进程优先级，适应不同类型的工作负载。
- 复杂性：实现较为复杂，但能够提供较好的响应时间和系统吞吐量。
实时调度
实时调度在实时系统中至关重要，其主要目标是确保任务在严格的时间限制内完成。以下是对实时调度的详细概述和补充：
实现实时调度的基本条件
为了满足实时系统的要求，实现实时调度需要满足以下基本条件：
- 抢占式调度：处理机调度必须是抢占式的，以保证高优先级任务能够及时中断低优先级任务并获得CPU时间。
- 任务执行时间保证：任务的执行时间必须是可预测的，系统能够确保任务在规定的时间内完成。
- 截止时间保证：任务的截止时间必须能够得到保证，即任务能够在其规定的截止时间前完成。
实时调度算法
实时调度算法主要分为两种类型：最早截至时间优先（EDF）和最低松弛度优先（LLF）。
1. 最早截至时间优先（EDF）
**最早截至时间优先（Earliest Deadline First, EDF）**算法总是选择截至时间最早的任务执行。特点包括：
- 动态优先级：任务的优先级随其截止时间的临近而动态变化。
- 最优性：在单处理器系统中，EDF是最优的实时调度算法，即如果任务集是可调度的，EDF一定能够找到一个调度方案，使所有任务按时完成。
- 缺点：可能导致低优先级任务被无限期推迟，尤其是在任务负载较重时。
2. 最低松弛度优先（LLF）
**最低松弛度优先（Least Laxity First, LLF）**算法选择松弛度最小的任务执行。松弛度是指任务必须完成时间与其本身的运行时间之差。特点包括：
- 松弛度计算：松弛度 = 截止时间 - 当前时间 - 剩余执行时间。
- 动态调整：任务的松弛度随时间变化，系统动态选择松弛度最小的任务执行。
- 优点：可以保证所有任务按时完成，并尽可能减少延迟。
- 缺点：计算松弛度的开销较大，频繁的任务切换可能导致系统性能下降。
优先级倒置
**优先级倒置（Priority Inversion）**是指低优先级任务间接影响高优先级任务的执行，导致高优先级任务无法按时完成。通常出现在以下情况下：
- 共享资源：高优先级任务需要访问由低优先级任务持有的共享资源，而低优先级任务被中等优先级任务抢占。
- 解决方法：常用的解决方法是优先级继承协议（Priority Inheritance Protocol），即当低优先级任务持有高优先级任务需要的资源时，临时提升低优先级任务的优先级到高优先级任务的优先级，直到资源释放。
实时调度的应用场景
实时调度广泛应用于各种需要严格时间控制的系统中，例如：
- 嵌入式系统：如汽车电子控制系统、工业控制系统等。
- 多媒体系统：如视频流处理、音频处理等。
- 电信系统：如电话交换系统、网络路由器等。
- 航空航天系统：如飞行控制系统、卫星通信系统等。
概述
Linux内核采用完全公平调度（CFS）算法作为默认的进程调度算法，旨在为所有进程提供公平的CPU时间分配。CFS 引入了“虚拟运行时间”（vruntime）的概念，并根据每个进程的累计 vruntime 来进行排序，选择 vruntime 最小的进程运行。
CFS 调度算法
CFS 调度算法的核心是红黑树数据结构，用于维护就绪队列。就绪队列中的每个节点都代表一个进程，并存储该进程的 vruntime 值。调度器会从就绪队列中选择 vruntime 最小的进程运行，然后更新该进程的 vruntime 值，并将其移至就绪队列的末尾。
CFS 还引入了时间片的概念，用于限制每个进程每次运行的时间。时间片的长度会根据系统负载进行动态调整，在负载较低时会延长，在负载较高时会缩短。
调度策略
CFS 支持三种调度策略：
- 常规进程调度（SCHED_NORMAL）：这是默认的调度策略，适用于大多数应用程序。
- 实时进程调度（SCHED_FIFO、SCHED_RR）：用于实时应用程序，需要保证其能够及时响应事件。实时进程调度采用静态时间片，即每个进程每次运行的时间都是固定的。
- 普通进程调度（SCHED_OTHER）：用于不属于前两类规则的进程。普通进程调度采用动态时间片，会根据系统负载进行调整。
CPU 带宽控制
Linux 还支持 CPU 带宽控制，可以为不同的进程组分配不同的 CPU 份额。CPU 份额是一个百分比值，表示该进程组可以使用的 CPU 时间的比例。例如，如果一个进程组的 CPU 份额为 50%，则该进程组只能使用一半的 CPU 时间。
-
CFS 调度算法的实现
- CFS 使用红黑树来维护就绪队列。红黑树是一种自平衡二叉查找树，可以保证插入、删除和查找操作的时间复杂度为 O(log n)。
- CFS 的调度过程如下：
- 从就绪队列中选择 vruntime 最小的进程。
- 更新该进程的 vruntime 值。
- 将该进程移至就绪队列的末尾。
- 将该进程切换到运行状态。
-
CFS 调度策略的配置
- CFS 调度策略可以使用以下参数进行配置：
- nice 值：用于调整进程的优先级。nice 值越小，进程的优先级越高。
- 进程组：用于将进程分组，以便为不同的进程组分配不同的 CPU 份额。
- CFS 调度策略的配置可以通过以下命令进行修改：
nice -n command：用于设置进程的 nice 值。taskset -p command：用于将进程绑定到特定的 CPU 或 CPU 组。
-
CPU 带宽控制的实现
- CPU 带宽控制是通过 cgroup 子系统实现的。cgroup 子系统可以将进程划分为不同的组，并为每个组分配不同的资源，例如 CPU 时间、内存和 I/O 带宽。
- CPU 带宽控制可以使用以下命令进行配置：
echo /sys/fs/cgroup/cpu/group/cpu.cfs_quota_us：用于设置进程组的 CPU 份额。echo /sys/fs/cgroup/cpu/group/cpu.cfs_period_us：用于设置进程组的 CPU 时间片长度。