进程调度是所有操作系统中最关键的执行工作之一，Linux 也不例外。 任何操作系统(如通用操作系统、服务器或实时系统)在调度过程中的启发式和高效性使其正常运转，并赋予其身份。 在本章中，我们将深入了解 Linux 调度器，了解以下概念：
- Linux 调度器设计
- 排课课程
- 调度策略和优先级
- 完全公平的调度器
- 实时调度程序
- 截止日期调度器
- 团体调度
- 抢占
任何操作系统的有效性都与其公平调度所有竞争进程的能力成正比。 进程调度器是内核的核心组件，它计算并决定进程获得 CPU 时间的时间和时间。 理想情况下，进程需要个 CPU 时间片才能运行，因此调度器基本上需要在进程之间公平地分配处理器时间片。
调度程序通常必须：
- 避免进程饥饿
- 管理优先级计划
- 最大化所有进程的吞吐量
- 确保较短的周转时间
- 确保均匀的资源使用
- 避免占用 CPU
- 考虑进程的行为模式以确定优先级
- 重载下的高雅补贴
- 高效处理多核调度
Linux 最初是为桌面系统开发的，但随着其使用范围从嵌入式设备、大型机和超级计算机扩展到房间大小的服务器，它已经不假思索地演变成了一个多维操作系统。 它还无缝地适应了不断发展的多样化计算平台，如 SMP、虚拟化和实时系统。 这些平台的多样性是由这些系统上运行的进程类型带来的。 例如，高度交互的桌面系统可能运行受 I/O 限制的进程，而实时系统则依靠确定性进程而蓬勃发展。 因此，当需要对其进行合理调度时，每种进程都需要不同类型的启发式方法，因为 CPU 密集型进程可能比正常进程需要更多的 CPU 时间，而实时进程将需要确定性执行。 因此，迎合各种系统的 Linux 面临着在管理这些不同进程时出现的各种调度挑战。
Linux 进程调度器的内部设计优雅而巧妙地采用了简单的两层模型，第一层是Generic Scheduler，定义抽象操作作为调度器的入口函数，第二层是调度类，实现实际的调度操作，其中每个类都致力于处理特定类型进程的调度启发式。 此模型使通用调度器能够保持从每个调度器类的实现细节中抽象出来。 例如，正常进程(I/O 限制)可以由一个类处理，而需要确定性执行的进程(如实时进程)可以由另一个类处理。 此体系结构还支持无缝添加新的调度类。 上图描述了进程调度器的分层设计。
通用调度器通过名为sched_class的结构定义抽象接口：
struct sched_class {
const struct sched_class *next;
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
void (*yield_task) (struct rq *rq);
bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
/*
* It is the responsibility of the pick_next_task() method that will
* return the next task to call put_prev_task() on the @prev task or
* something equivalent.
*
* May return RETRY_TASK when it finds a higher prio class has runnable
* tasks.
*/
struct task_struct * (*pick_next_task) (struct rq *rq,
struct task_struct *prev,
struct rq_flags *rf);
void (*put_prev_task) (struct rq *rq, struct task_struct *p);
#ifdef CONFIG_SMP
int (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
void (*migrate_task_rq)(struct task_struct *p);
void (*task_woken) (struct rq *this_rq, struct task_struct *task);
void (*set_cpus_allowed)(struct task_struct *p,
const struct cpumask *newmask);
void (*rq_online)(struct rq *rq);
void (*rq_offline)(struct rq *rq);
#endif
void (*set_curr_task) (struct rq *rq);
void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
void (*task_fork) (struct task_struct *p);
void (*task_dead) (struct task_struct *p);
/*
* The switched_from() call is allowed to drop rq->lock, therefore we
* cannot assume the switched_from/switched_to pair is serialized by
* rq->lock. They are however serialized by p->pi_lock.
*/
void (*switched_from) (struct rq *this_rq, struct task_struct *task);
void (*switched_to) (struct rq *this_rq, struct task_struct *task);
void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
int oldprio);
unsigned int (*get_rr_interval) (struct rq *rq,
struct task_struct *task);
void (*update_curr) (struct rq *rq);
#define TASK_SET_GROUP 0
#define TASK_MOVE_GROUP 1
#ifdef CONFIG_FAIR_GROUP_SCHED
void (*task_change_group) (struct task_struct *p, int type);
#endif
};每个调度器类都实现sched_class结构中定义的操作。 在 4.12.x 内核中，有三个调度类：完全公平调度(CFS)类、实时调度类和截止日期调度类，每个类处理具有特定调度要求的进程。 以下代码片段显示了每个类如何根据sched_class结构填充其操作。
CFS 类**：**
const struct sched_class fair_sched_class = {
.next = &idle_sched_class,
.enqueue_task = enqueue_task_fair,
.dequeue_task = dequeue_task_fair,
.yield_task = yield_task_fair,
.yield_to_task = yield_to_task_fair,
.check_preempt_curr = check_preempt_wakeup,
.pick_next_task = pick_next_task_fair,
.put_prev_task = put_prev_task_fair,
....
}实时调度类**：**
const struct sched_class rt_sched_class = {
.next = &fair_sched_class,
.enqueue_task = enqueue_task_rt,
.dequeue_task = dequeue_task_rt,
.yield_task = yield_task_rt,
.check_preempt_curr = check_preempt_curr_rt,
.pick_next_task = pick_next_task_rt,
.put_prev_task = put_prev_task_rt,
....
}截止日期安排类**：**
const struct sched_class dl_sched_class = {
.next = &rt_sched_class,
.enqueue_task = enqueue_task_dl,
.dequeue_task = dequeue_task_dl,
.yield_task = yield_task_dl,
.check_preempt_curr = check_preempt_curr_dl,
.pick_next_task = pick_next_task_dl,
.put_prev_task = put_prev_task_dl,
....
}通常，运行队列包含在给定 CPU 核心上争用 CPU 时间的所有进程(运行队列是按 CPU 的)。 通用调度程序被设计为每当调用它来调度下一个最佳可运行任务时都会查看运行队列。 维护所有可运行进程的公共运行队列是不可能的，因为每个调度类处理特定的调度策略和优先级。
内核通过突出其设计原则来解决这一问题。 每个调度类将其运行队列数据结构的布局定义为最适合其策略。 通用调度器层实现了一个抽象的运行队列结构，其中包含充当运行队列接口的公共元素。 此结构通过引用特定于类的运行队列的指针进行了扩展。 换句话说，所有调度类都将其运行队列嵌入到主运行队列结构中。 这是一个经典的设计技巧，它允许每个调度器类为其运行队列数据结构选择适当的布局。
下面的struct rq(RunQueue)代码片段将帮助我们理解这个概念(结构中省略了与 SMP 相关的元素，以便我们将重点放在相关的内容上)：
struct rq {
/* runqueue lock: */
raw_spinlock_t lock;
/*
* nr_running and cpu_load should be in the same cacheline because
* remote CPUs use both these fields when doing load calculation.
*/
unsigned int nr_running;
#ifdef CONFIG_NUMA_BALANCING
unsigned int nr_numa_running;
unsigned int nr_preferred_running;
#endif
#define CPU_LOAD_IDX_MAX 5
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
#ifdef CONFIG_NO_HZ_COMMON
#ifdef CONFIG_SMP
unsigned long last_load_update_tick;
#endif /* CONFIG_SMP */
unsigned long nohz_flags;
#endif /* CONFIG_NO_HZ_COMMON */
#ifdef CONFIG_NO_HZ_FULL
unsigned long last_sched_tick;
#endif
/* capture load from *all* tasks on this cpu: */
struct load_weight load;
unsigned long nr_load_updates;
u64 nr_switches;
struct cfs_rq cfs;
struct rt_rq rt;
struct dl_rq dl;
#ifdef CONFIG_FAIR_GROUP_SCHED
/* list of leaf cfs_rq on this cpu: */
struct list_head leaf_cfs_rq_list;
struct list_head *tmp_alone_branch;
#endif /* CONFIG_FAIR_GROUP_SCHED */
unsigned long nr_uninterruptible;
struct task_struct *curr, *idle, *stop;
unsigned long next_balance;
struct mm_struct *prev_mm;
unsigned int clock_skip_update;
u64 clock;
u64 clock_task;
atomic_t nr_iowait;
#ifdef CONFIG_IRQ_TIME_ACCOUNTING
u64 prev_irq_time;
#endif
#ifdef CONFIG_PARAVIRT
u64 prev_steal_time;
#endif
#ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
u64 prev_steal_time_rq;
#endif
/* calc_load related fields */
unsigned long calc_load_update;
long calc_load_active;
#ifdef CONFIG_SCHED_HRTICK
#ifdef CONFIG_SMP
int hrtick_csd_pending;
struct call_single_data hrtick_csd;
#endif
struct hrtimer hrtick_timer;
#endif
...
#ifdef CONFIG_CPU_IDLE
/* Must be inspected within a rcu lock section */
struct cpuidle_state *idle_state;
#endif
};您可以看到调度类(cfs、rt和dl)如何将自身嵌入到运行队列中。 运行队列中感兴趣的其他元素包括：
nr_running：这表示运行队列中的进程数load：这表示队列(所有可运行进程)上的当前负载curr和idle：它们分别指向当前运行任务和空闲任务的task_struct。 当没有其他任务可运行时，将调度空闲任务。
调度过程从调用<kernel/sched/core.c>中定义的通用调度器(即schedule()函数)开始。 这可能是内核中调用最多的例程之一。 schedule()的功能是挑选下一个最佳的可运行任务。 函数schedule()的pick_next_task()迭代包含在调度程序类中的所有相应函数，最终选择下一个最佳任务来运行。 每个调度器类都使用单个链表进行链接，这使得pick_next_task()能够遍历这些类。
考虑到 Linux 主要是为迎合高度交互的系统而设计的，如果在任何其他类中没有更高优先级的可运行任务(这是通过检查运行队列中的可运行任务总数(nr_running)是否等于 CFS 类的子运行队列中的可运行任务总数来实现的)，该函数首先在 CFS 类中查找下一个最好的可运行任务；否则，它迭代所有其他类并选择下一个最好的可运行任务。 最后，如果没有找到任务，它会调用空闲的后台任务(总是返回非空值)。
以下代码块显示了pick_next_task()的实现：
/*
* Pick up the highest-prio task:
*/
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
const struct sched_class *class;
struct task_struct *p;
/*
* Optimization: we know that if all tasks are in the fair class we can
* call that function directly, but only if the @prev task wasn't of a
* higher scheduling class, because otherwise those loose the
* opportunity to pull in more work from other CPUs.
*/
if (likely((prev->sched_class == &idle_sched_class ||
prev->sched_class == &fair_sched_class) &&
rq->nr_running == rq->cfs.h_nr_running)) {
p = fair_sched_class.pick_next_task(rq, prev, rf);
if (unlikely(p == RETRY_TASK))
goto again;
/* Assumes fair_sched_class->next == idle_sched_class */
if (unlikely(!p))
p = idle_sched_class.pick_next_task(rq, prev, rf);
return p;
}
again:
for_each_class(class) {
p = class->pick_next_task(rq, prev, rf);
if (p) {
if (unlikely(p == RETRY_TASK))
goto again;
return p;
}
}
/* The idle class should always have a runnable task: */
BUG();
}运行哪个进程的决定取决于进程的优先级。 每个进程都标有优先级值，使其在何时获得 CPU 时间方面处于直接位置。 在nix 系统上，优先级基本上分为动态和静态*优先级。 动态优先级基本上由内核动态地应用于正常进程，并考虑各种因素，例如进程的良好值、其历史行为(I/O 限制或处理器限制)、已执行时间和等待时间。 静态优先级由用户应用于实时进程，内核不会动态更改它们的优先级。 因此，在调度时，具有静态优先级的进程被赋予更高的优先级。
I/O bound process: When the execution of a process is heavily punctuated with I/O operations (waiting for a resource or an event), for instance a text editor, which almost alternates between running and waiting for a key press, such processes are called I/O bound. Due to this nature, the scheduler normally allocates short processor time slices to I/O-bound processes and multiplexes them with other processes, adding the overhead of context switching and the subsequent heuristics of computing the next best process to run. Processor bound process: These are processes that love to stick on to CPU time slices, as they require maximum utilization of the processor's computing capacity. Processes requiring heavy computations such as complex scientific calculations, and video rendering codecs are processor bound. Though the need for a longer CPU slice looks desirable, the expectation to run them under fixed time periods is not often a requirement. Schedulers on interactive operating systems tend to favor more I/O-bound processes than processor-bound ones. Linux, which aims for good interactive performance, is more optimized for faster response time, inclining towards I/O bound processes, even though processor-bound processes are run less frequently they are ideally given longer timeslices to run. Processes can also be multi-faceted, with an I/O-bound process needing to perform serious scientific computations, burning the CPU.
任何正常进程的NICE值的范围在 19(最低优先级)和-20(最高优先级)之间，默认值为 0。 较高的 NICE 值表示较低的优先级(该进程对其他进程较好)。 实时进程的优先级在 0 到 99 之间(静态优先级)。 所有这些优先级范围都是从用户的角度出发的。
内核的优先级观点
然而，Linux 从自己的角度看待进程优先级。 它为获得进程的优先级增加了更多的计算。 基本上，它将所有优先级调整在 0 到 139 之间，其中 0 到 99 分配给实时进程，100 到 139 表示较好的值范围(-20 到 19)。
现在，让我们更深入地了解每个调度类，并了解它在熟练而优雅地管理其流程的调度操作时使用的操作、策略和启发式方法。 如前所述，每个调度类必须提供struct sched_class的一个实例；让我们看看该结构中的一些关键元素：
enqueue_task：基本上将一个新进程添加到运行队列dequeue_task：当进程从运行队列中移除时yield_task：当进程想要自愿放弃 CPU 时pick_next_task：schedule()调用的PICK_NEXT_TASK的对应函数。 它从类中挑选下一个最好的可运行任务。
所有具有动态优先级的进程都由 CFS 类处理，由于通用*NIX 系统中的大多数进程都是正常的(非实时的)，因此 CFS 仍然是内核中最繁忙的调度器类。
CFS 根据每个任务分配的策略和动态优先级，在为任务分配处理器时间时依赖于保持平衡。 CFS 下的进程调度是在拥有“理想的、精确的多任务 CPU”的前提下实现的，该 CPU 能够在峰值容量下平等地为所有进程提供动力。 例如，如果有两个进程，完美的多任务 CPU 可确保两个进程同时运行，每个进程利用其 50%的功率。 由于这实际上是不可能的(实现并行性)，CFS 通过在所有争用的进程之间保持适当的平衡来将处理器时间分配给一个进程。 如果一个进程没有收到相当长的时间，那么它就会被认为是不平衡的，因此接下来会被认为是最佳可运行的进程。
CFS 不依赖于传统的时间片来分配处理器时间，而是使用虚拟运行时(vruntime)的概念：它表示进程获得 CPU 时间的时间量，这意味着较低的vruntime值表示该进程没有处理器，而较高的vruntime值表示该进程获得了相当多的处理器时间。 vruntime值较低的进程在调度时获得最大优先级。 CFS 还为理想地等待 I/O 请求的进程提供休眠公平性。 休眠公平性要求等待进程在事件后最终醒来时获得相当大的 CPU 时间。 根据vruntime值，CFS 决定进程要运行的时间量。 它还使用 NICE 值来衡量一个进程相对于所有竞争进程的权重：值越高、优先级越低的进程权重越小，值越低、优先级越高的任务权重越大。 在 Linux 中，即使处理具有不同优先级的进程也很优雅，因为与高优先级任务相比，低优先级任务会得到相当大的延迟因素；这使得分配给低优先级任务的时间很快消散。
根据进程等待的时间、进程运行的时间、进程的历史行为及其良好值来分配优先级。 通常，调度器使用复杂的算法来运行下一个最佳进程。
在计算每个进程获得的时间片时，CFS 不仅依赖于进程的 NICE 值，还会查看进程的负载量。 进程的 NICE 值每增加 1，CPU 时间片就会减少 10%，NICE 值每减少 1，CPU 时间片就会增加 10%，这表明 NICE 值会乘以每次跳跃 10%的变化。 为了计算相应 NICE 值的负载权重，内核维护一个名为prio_to_weight*，*的数组，其中每个 NICE 值对应一个权重：
static const int prio_to_weight[40] = {
/* -20 */ 88761, 71755, 56483, 46273, 36291,
/* -15 */ 29154, 23254, 18705, 14949, 11916,
/* -10 */ 9548, 7620, 6100, 4904, 3906,
/* -5 */ 3121, 2501, 1991, 1586, 1277,
/* 0 */ 1024, 820, 655, 526, 423,
/* 5 */ 335, 272, 215, 172, 137,
/* 10 */ 110, 87, 70, 56, 45,
/* 15 */ 36, 29, 23, 18, 15,
};进程的负载值存储在struct load_weight的weight字段中。
与进程的权重一样，CFS 的运行队列也被分配了一个权重，即运行队列中所有任务的总权重。 现在，通过分解实体的负载权重、运行队列的负载权重和sched_period(调度周期)来计算时间片。
CFS 不再需要正常的运行队列，而是使用自平衡的红黑树，以便在尽可能短的时间内获得下一个最佳进程来运行。 RB 树保存所有竞争进程，便于轻松快速地插入、删除和搜索进程。 优先级最高的进程被放置到其最左边的节点。 现在，pick_next_task()函数只从rb tree中选择最左边的节点进行调度。
为了确保调度时的公平性，CFS 被设计为保证每个可运行进程在定义的时间段(称为调度周期)内至少在处理器上运行一次。 在一个调度周期内，CFS 初步确保公平性，换句话说，确保将不公平性保持在最低限度，因为每个进程至少运行一次。 CFS 在所有执行线程之间将调度周期划分为时间片以避免进程饥饿；然而，想象一下这样一个场景：进程 A 派生 10 个执行线程，进程 B 派生 5 个执行线程：在这里，CFS 将时间片平均分配给所有线程，导致进程 A 及其派生的线程获得最大时间，而进程 B 则受到不公平的处理。 如果进程 A 继续产生更多的线程，那么对于进程 B 及其产生的线程来说，情况可能会变得非常严重，因为进程 B 将不得不与最小调度粒度或时间片(即 1 毫秒)作斗争。 此场景中的公平性要求进程 A 和 B 获得与生成的线程相等的时间片，以便在内部共享这些时间片。 例如，如果进程 A 和 B 各获得 50%的时间，则进程 A 应在其派生的 10 个线程之间分配其 50%的时间，每个线程在内部获得 5%的时间。
为了解决这个问题并保持公平性，CFS 引入了组调度，其中时间片被分配给线程组，而不是单独的线程。 继续相同的示例，在组调度下，进程 A 及其派生的线程属于一个组，而进程 B 及其派生的线程属于另一个组。 由于调度粒度是在组级别而不是在线程级别强加的，因此它为进程 A 和 B 提供了相等的处理器时间份额，而进程 A 和 B 在内部将时间片分配给其组成员。 在这里，在进程 A 下产生的线程会受到影响，因为它会因为产生更多的执行线程而受到惩罚。 为确保组调度，在配置内核时设置CONFIG_FAIR_GROUP_SCHED。 CFS 任务组由结构sched_entity*，*表示，每个组称为调度实体。 以下代码片段显示了计划实体结构的关键元素：
struct sched_entity {
struct load_weight load; /* for load-balancing */
struct rb_node run_node;
struct list_head group_node;
unsigned int on_rq;
u64 exec_start;
u64 sum_exec_runtime;
u64 vruntime;
u64 prev_sum_exec_runtime;
u64 nr_migrations;
#ifdef CONFIG_SCHEDSTATS
struct sched_statistics statistics;
#endif
#ifdef CONFIG_FAIR_GROUP_SCHED
int depth;
struct sched_entity *parent;
/* rq on which this entity is (to be) queued: */
struct cfs_rq *cfs_rq;
/* rq "owned" by this entity/group: */
struct cfs_rq *my_q;
#endif
....
};load：表示每个实体对队列总负载的负载量vruntime：表示进程运行的时间量
在多核系统中，任务组可以在任何 CPU 核上运行，但要实现这一点，仅创建一个调度实体是不够的。 因此，组必须为系统上的每个 CPU 核心创建调度实体。 跨 CPU 的调度实体由struct task_group表示：
/* task group related information */
struct task_group {
struct cgroup_subsys_state css;
#ifdef CONFIG_FAIR_GROUP_SCHED
/* schedulable entities of this group on each cpu */
struct sched_entity **se;
/* runqueue "owned" by this group on each cpu */
struct cfs_rq **cfs_rq;
unsigned long shares;
#ifdef CONFIG_SMP
/*
* load_avg can be heavily contended at clock tick time, so put
* it in its own cacheline separated from the fields above which
* will also be accessed at each tick.
*/
atomic_long_t load_avg ____cacheline_aligned;
#endif
#endif
#ifdef CONFIG_RT_GROUP_SCHED
struct sched_rt_entity **rt_se;
struct rt_rq **rt_rq;
struct rt_bandwidth rt_bandwidth;
#endif
struct rcu_head rcu;
struct list_head list;
struct task_group *parent;
struct list_head siblings;
struct list_head children;
#ifdef CONFIG_SCHED_AUTOGROUP
struct autogroup *autogroup;
#endif
struct cfs_bandwidth cfs_bandwidth;
};现在，每个任务组都有一个针对每个 CPU 核心的调度实体，以及一个与其相关联的 CFS 运行队列。 当来自一个任务组的任务从一个 CPU 核心(X)迁移到另一个 CPU 核心(Y)时，该任务从 CPU x 的 CFS 运行队列中出列，并排队到 CPU y 的 CFS 运行队列中。
调度策略应用于流程，并帮助确定调度决策。 如果您还记得，在第 1 章，理解进程、地址空间和线程中，我们在 structtask_struct的调度属性下描述了int policy字段。 policy field包含指示调度时将哪个策略应用于进程的值。 CFS 类使用以下两个策略处理所有正常进程：
SCHED_NORMAL (0)：此选项用于所有正常进程。 所有非实时进程都可以概括为正常进程。 由于 Linux 的目标是成为一个高响应性和交互性的系统，所以大多数调度活动和启发式方法都集中在公平地调度正常进程上。 根据 POSIX，正常进程称为SCHED_OTHER。SCHED_BATCH (3)：通常在进程非交互的服务器中，使用 CPU 限制的批处理。 这些 CPU 密集型进程的优先级低于SCHED_NORMAL进程，并且它们不会抢占已调度的正常进程。- CFS 类还处理调度空闲进程，这由以下策略指定：
SCHED_IDLE (5)：当没有要运行的进程时，调度空闲进程(低优先级后台进程)。 分配给空闲进程的优先级在所有进程中最低。
Linux 支持软实时任务，由实时调度类进行调度。 rt进程被分配静态优先级，内核动态地保持不变。 由于实时任务的目标是确定性的运行，并且希望控制它们被调度的时间和时间，因此它们总是优先于普通任务(SCHED_NORMAL)。 与使用rb tree作为其子运行队列的 CFS 不同，较简单的rt调度器对每个优先级值(1 到 99)使用一个简单的linked list。 Linux 在调度静态优先级进程时应用两个实时策略，rr和fifo，；它们由struct task_struct的policy元素指示。
SCHED_FIFO(1)：这使用先进先出方法来调度软实时进程SCHED_RR(2)：这是用于调度软实时进程的轮询策略
FIFO是一种调度机制，适用于优先级高于 0 的进程(0 分配给正常进程)。 FIFO 进程在没有任何时间片分配的情况下运行；换句话说，它们总是一直运行，直到它们因某个事件阻塞或显式地让给另一个进程。 当调度程序遇到优先级更高的可运行 FIFO、RR 或截止日期任务时，FIFO 进程也会被抢占。 当调度程序遇到多个具有相同优先级的 FIFO 任务时，它将以循环方式运行进程，从列表顶部的第一个进程开始。 在抢占时，该过程被添加回列表的尾部。 如果较高优先级的进程抢占了 FIFO 进程，它会在列表的最前面等待，当所有其他高优先级任务都被抢占时，它会再次被选中运行。 当新的 FIFO 进程变为可运行时，它将被添加到列表的尾部。
循环策略类似于 FIFO，唯一的不同之处在于它被分配了一个时间片来运行。 这是对 FIFO 的一种增强(因为 FIFO 进程可能会一直运行，直到它产生或等待)。 与 FIFO 类似，位于列表头部的 RR 进程被选中执行(如果没有其他更高优先级的任务可用)，并且在时间片完成时被抢占，并被添加回列表的尾部。 具有相同优先级的 RR 进程运行循环调度，直到被高优先级任务抢占。 当高优先级任务抢占 RR 任务时，它在列表的最前面等待，恢复时只在其剩余的时间片内运行。
与 CFS 下的分组调度类似，实时进程也可以通过设置CONFIG_RT_GROUP_SCHED进行分组调度。 要使组调度成功，必须为每个组分配一部分 CPU 时间，并保证时间片足以运行每个实体下的任务，否则会失败。 因此，“运行时间”(CPU 在一段时间内运行的时间的一部分)是按组分配的。 分配给一个组的运行时间不会被另一个组使用。 未分配给实时组的 CPU 时间将由普通优先级任务使用，任何未被实时实体使用的时间也将由普通任务挑选。 FIFO 和 RR 组由struct sched_rt_entity*：*表示
struct sched_rt_entity {
struct list_head run_list;
unsigned long timeout;
unsigned long watchdog_stamp;
unsigned int time_slice;
unsigned short on_rq;
unsigned short on_list;
struct sched_rt_entity *back;
#ifdef CONFIG_RT_GROUP_SCHED
struct sched_rt_entity *parent;
/* rq on which this entity is (to be) queued: */
struct rt_rq *rt_rq;
/* rq "owned" by this entity/group: */
struct rt_rq *my_q;
#endif
};Deadline代表 Linux 上的新一代 RT 进程(从 3.14 内核开始添加)。 与 FIFO 和 RR 不同，进程可能占用 CPU 或受时间片限制，而基于 GEDF(全局最早截止日期优先)和 CBS(恒定带宽服务器)算法的截止日期进程预先确定其运行时要求。 一个零星的进程在内部运行多个任务，每个任务都有一个必须在其中完成执行的相对截止日期和一个计算时间，这定义了 CPU 完成进程执行所需的时间。 为了确保内核成功执行 Deadline 进程，内核根据 Deadline 参数运行准入测试，失败时返回错误EBUSY。 具有截止日期策略的进程优先于所有其他进程。 截止日期流程使用SCHED_DEADLINE(6)作为其策略元素。
Linux 提供了一整套系统调用，这些系统调用管理各种调度程序参数、策略和优先级，并检索调用线程的大量与调度相关的信息。 它还使线程能够显式地产生 CPU：
nice(int inc)nice()接受int参数，并将其与调用线程的nice值相加。 如果成功，它将返回线程的新的 nice 值。 NICE 值在 19(最低优先级)到-20(最高优先级)范围内。 Nice值只能在此范围内递增：
getpriority(int which, id_t who)它返回由其参数指示的指定用户的线程、组、用户或线程集的nice值。 它返回任何进程持有的最高优先级：
setpriority(int which, id_t who, int prio)由参数指示的指定用户的线程、组、用户或线程集的调度优先级由setpriority设置。 如果成功，则返回零：
sched_setscheduler(pid_t pid, int policy, const struct sched_param *param)这将设置指定线程的调度策略和参数，由线程的pid指示。 如果pid为零，则设置调用线程的策略。 指定调度参数的param参数指向保存int sched_priority的结构sched_param。 sched_priority对于正常进程，必须为零，对于 FIFO 和 RR 策略(在策略参数中提到)，优先级值必须介于 1 到 99 之间。 如果成功，则返回零：
sched_getscheduler(pid_t pid)它返回线程的调度策略(pid)。 如果pid为零，则检索调用线程的策略：
sched_setparam(pid_t pid, const struct sched_param *param)它设置与给定线程的调度策略相关联的调度参数(pid)。 如果pid为零，则设置调用进程的参数。 如果成功，则返回零：
sched_getparam(pid_t pid, struct sched_param *param)这将设置指定线程(pid)的调度参数。 如果pid为零，则检索调用线程的调度参数。 如果成功，则返回零：
sched_setattr(pid_t pid, struct sched_attr *attr, unsigned int flags)它设置指定线程(pid)的调度策略和相关属性。 如果pid为零，则设置调用进程的策略和属性。 这是特定于 Linux 的调用，是sched_setscheduler()和sched_setparam()调用提供的功能的超集。 如果成功，则返回零。
sched_getattr(pid_t pid, struct sched_attr *attr, unsigned int size, unsigned int flags)它获取指定线程(pid)的调度策略和相关属性。 如果pid为零，则将检索调用线程的调度策略和相关属性。 这是特定于 Linux 的调用，是sched_getscheduler()和sched_getparam()调用提供的功能的超集。 如果成功，则返回零。
sched_get_priority_max(int policy)
sched_get_priority_min(int policy)这将分别返回指定policy的最大和最小优先级。 fifo、rr、deadline、normal、batch、idle是支持的策略值。
sched_rr_get_interval(pid_t pid, struct timespec *tp)它获取指定线程(pid)的时间段，并将其写入由tp指定的timespec struct。 如果pid为零，则将调用进程的时间段取入tp。 这仅适用于使用*rr*策略的进程。 如果成功，则返回零。
sched_yield(void)调用此函数是为了显式放弃 CPU。 现在，该线程被添加回队列。 如果成功，则返回零。
提供了特定于 Linux 的处理器亲和性调用，帮助线程定义它们想要在哪些 CPU 上运行。 默认情况下，每个线程继承其父线程的处理器亲和性，但它可以定义其亲和性掩码来确定其处理器亲和性。 在多核系统上，CPU 亲和性调用通过帮助进程坚持使用一个内核来帮助提高性能(但是，Linux 会尝试在一个 CPU 上保留一个线程)。 亲和位掩码信息包含在struct task_struct的cpu_allowed字段中。 关联调用如下：
sched_setaffinity(pid_t pid, size_t cpusetsize, const cpu_set_t *mask)它将线程的 CPU 关联掩码(pid)设置为mask提到的值。 如果线程(pid)没有在指定的 CPU 队列中运行，则会将其迁移到指定的cpu。 如果成功，则返回零。
sched_getaffinity(pid_t pid, size_t cpusetsize, cpu_set_t *mask)这会将线程(pid)的亲和性掩码提取到由掩码指向的cpusetsize结构中。 如果pid为零，则返回调用线程的掩码。 如果成功，则返回零。
理解抢占和上下文切换是全面理解调度以及它在保持低延迟和一致性方面对内核的影响的关键。 每个进程都必须被隐式或显式抢占，以便为另一个进程让路。 抢占可能导致上下文切换，这需要由函数context_switch()执行的特定于体系结构的低级操作。 处理器切换上下文需要完成两个主要任务：将旧进程的虚拟内存映射切换到新进程，以及将处理器状态从旧进程的虚拟内存映射切换到新进程的虚拟内存映射。 这两个任务由switch_mm()和switch_to()执行。
发生抢占的原因有以下任何一种：
当高优先级进程变为可运行时。 为此，调度程序必须定期检查高优先级的可运行线程。 从中断和系统调用返回时，设置TIF_NEED_RESCHEDULE(内核提供的指示需要重新调度的标志)，调用调度器。 由于存在保证以规则间隔发生的周期性定时器中断，因此保证了调度器的调用。 当进程进入阻塞调用或发生中断事件时，也会发生抢占。
Linux 内核历史上一直是不可抢占的，这意味着内核模式下的任务是不可抢占的，除非发生中断事件或它选择显式放弃 CPU。 从 2.6 内核开始，增加了抢占功能(需要在内核构建过程中启用)。 在启用内核抢占的情况下，内核模式下的任务由于列出的所有原因都是可抢占的，但是内核模式任务可以在执行关键操作时禁用内核抢占。 这可以通过向每个进程的thread_info结构添加抢占计数器(preempt_count)来实现。 任务可以通过内核宏preempt_disable()和preempt_enable()、禁用/启用抢占，这反过来会递增和递减preempt_counter。 这确保了只有当preempt_counter为零时(表示没有获取锁)，内核才是可抢占的。
内核代码中的关键部分是通过禁用抢占来执行的，这是通过在内核锁定操作(自旋锁、互斥)中调用preempt_disable和preempt_enable调用来强制执行的。
Linux 内核使用“抢占 RT”构建，支持完全可抢占内核选项，当启用该选项时，包括关键部分在内的所有内核代码都是完全可抢占的。
进程调度是内核不断发展的一个方面，随着 Linux 的发展并进一步扩展到许多计算领域，将要求对进程调度程序进行更精细的调整和更改。 然而，随着我们对这一章的理解建立起来，获得更深层次的洞察力或理解任何新的变化将是相当容易的。 我们现在可以更进一步，探索作业控制和信号管理的另一个重要方面。 我们将简要介绍信号的基础知识，然后进入内核的信号管理数据结构和例程。