引言
为什么需要调度
调度有关的进程描述符
struct task_struct {
int prio, static_prio, normal_prio;
unsigned int rt_priority;
const struct sched_class *sched_class;
struct sched_entity se;
struct sched_rt_entity rt;
…
unsigned int policy;
cpumask_t cpus_allowed;
…
};
-
prio
表示进程的优先级。进程运行时间,抢占频率都依赖于这些值。rt_priority
则用于实时(real-time)任务; -
sched_class
表示进程位于哪个调度类; -
sched_entity
的意义比较特殊。通常把一个线程(Linux 中的进程、任务同义词)叫作最小调度单元。但是 Linux 调度器不仅仅只能够调度单个任务,而且还可以将一组进程,甚至属于某个用户的所有进程作为整体进行调度。这就允许我们实现组调度,从而将 CPU 时间先分配到进程组,再在组内分配到单个线程。当引入这项功能后,可以大幅度提升桌面系统的交互性。比如,可以将编译任务聚集成一个组,然后进行调度,从而不会对交互性产生明显的影响。这里再次强调下,**Linux 调度器不仅仅能直接调度进程,也能对调度单元(schedulable entities)进行调度。这样的调度单元正是用struct sched_entity
来表示的。需要说明的是,它并非一个指针,而是直接嵌套在进程描述符中的。当然,后面的谈论将聚焦在单进程调度这种简单场景。由于调度器是面向调度单元设计的,所以它会将单个进程也视为调度单元,因此会使用sched_entity
结构体操作它们。sched_rt_entity
则是实时调度时使用的。 -
policy
表明任务的调度策略:通常意味着针对某些特定的进程组(如需要更长时间片,更高优先级等)应用特殊的调度决策。Linux 内核目前支持的调度策略如下: -
SCHED_NORMAL
:普通任务使用的调度策略; -
SCHED_BATCH
:不像普通任务那样被频繁抢占,可允许任务运行尽可能长的时间,从而更好地利用缓存,但是代价自然是损失交互性能。这种非常适合批量任务调度(批量的 CPU 密集型任务); -
SCHED_IDLE
:它要比 nice 19 的任务优先级还要低,但它并非真的空闲任务; -
SCHED_FIFO
和SCHED_RR
是软实时进程调度策略。它们是由 POSIX 标准定义的,由<kernel/sched/rt.c>
里面定义的实时调度器负责调度。RR 实现的是带有固定时间片的轮转调度方式;SCHED_FIFO 则使用的是先进先出的队列机制。 -
cpus_allowed
:用来表示任务的 CPU 亲和性。用户空间可以通过sched_setaffinity
系统调用来设置。
优先级 Priority
普通任务优先级:
nice(int increment)
系统调用来修改当前进程的优先级。该系统调用的实现位于
<kernel/shced/core.c>
中。默认情况下,用户只能为该用户启动的进程增加 nice 值(即降低优先级)。如果需要增加优先级(减少 nice 值),或者修改其它用户进程优先级,则必须以 root 身份操作。
-
硬实时任务:会有严格的时间限制,任务必须在时限内完成。比如直升机的飞控系统,就需要及时响应驾驶员的操控,并做出预期的动作。然而,Linux 本身并不支持硬实时任务,但是有一些基于它修改的版本,如 RTLinux(它们通常被称为 RTOS)则是支持硬实时调度的。 -
软实时任务:软实时任务其实也会有时间限制,但不是那么严格。也就是说,任务晚一点运行任务,并不会造成不可挽回的灾难性事故。实践中,软实时任务会提供一定的时间限制保障,但是不要过度依赖这种特性。例如,VOIP 软件会使用软实时保障的协议传来送音视频信号,但是即便因为操作系统负载过高,而产生一点延迟,也不会造成很大影响。 无论如何,软实时任务总会比普通任务的优先级更高。
类似其它的 Unix 系统,Linux 也是基于 POSIX 1b 标准定义的 「Real-time Extensions」实现实时优先级。可以通过如下的命令查看系统中的实时任务:
$ ps -eo pid, rtprio, cmd
chrt -p pid
查看单个进程的详情。Linux 中可以通过
chrt -p prio pid
更改实时任务优先级。这里需要注意的是,如果操作的是一个系统进程(通常并不会将普通用户的进程设置为实时的),则必须有 root 权限才可以修改实时优先级。
内核视角下的进程优先级:
#define MAX_NICE 19
#define MIN_NICE -20
#define NICE_WIDTH (MAX_NICE - MIN_NICE + 1)
…
#define MAX_USER_RT_PRIO 100
#define MAX_RT_PRIO MAX_USER_RT_PRIO
#define MAX_PRIO (MAX_RT_PRIO + NICE_WIDTH)
#define DEFAULT_PRIO (MAX_RT_PRIO + NICE_WIDTH / 2)
/*
* Convert user-nice values [ -20 ... 0 ... 19 ]
* to static priority [ MAX_RT_PRIO..MAX_PRIO-1 ],
* and back.
*/
#define NICE_TO_PRIO(nice) ((nice) + DEFAULT_PRIO)
#define PRIO_TO_NICE(prio) ((prio) - DEFAULT_PRIO)
/*
* 'User priority' is the nice value converted to something we
* can work with better when scaling various scheduler parameters,
* it's a [ 0 ... 39 ] range.
*/
#define USER_PRIO(p) ((p)-MAX_RT_PRIO)
#define TASK_USER_PRIO(p) USER_PRIO((p)->static_prio)
#define MAX_USER_PRIO (USER_PRIO(MAX_PRIO))
优先级计算:
int prio, static_prio, normal_prio;
unsigned int rt_priority;
static_prio 是由用户或系统设定的「静态」优先级映射成内核表示的优先级:
p->static_prio = NICE_TO_PRIO(nice_value);
normal_prio 存放的是基于 static_prio 和进程调度策略(实时或普通)决定的优先级,相同的静态优先级,在不同的调度策略下,得到的正常优先级是不同的。子进程在 fork 时,会继承父进程的 normal_prio。
prio 则是「动态优先级」,在某些场景下优先级会发生变动。一种场景就是,系统可以通过给某个任务优先级提升一段时间,从而抢占其它高优先级任务,一旦 static_prio 确定,prio 字段就可以通过下面的方式计算:
p->prio = effective_prio(p);
// kernel/sched/core.c 中定义了计算方法
static int effective_prio(struct task_struct *p)
{
p->normal_prio = normal_prio(p);
/*
* If we are RT tasks or we were boosted to RT priority,
* keep the priority unchanged. Otherwise, update priority
* to the normal priority:
*/
if (!rt_prio(p->prio))
return p->normal_prio;
return p->prio;
}
static inline int normal_prio(struct task_struct *p)
{
int prio;
if (task_has_dl_policy(p))
prio = MAX_DL_PRIO-1;
else if (task_has_rt_policy(p))
prio = MAX_RT_PRIO-1 - p->rt_priority;
else
prio = __normal_prio(p);
return prio;
}
static inline int __normal_prio(struct task_struct *p)
{
return p->static_prio;
}
task_struct->se.load
中看到进程的权重,定义如下:
struct sched_entity {
struct load_weight load; /* for load-balancing */
…
}
struct load_weight {
unsigned long weight;
u32 inv_weight;
};
为了让 nice 值的变化反映到 CPU 时间变化片上更加合理,Linux 内核中定义了一个数组,用于映射 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,
};
来看看如何使用上面的映射表,假设有两个优先级都是 0 的任务,每个都能获得 50% 的 CPU 时间(1024 / (1024 + 1024) = 0.5)。如果突然给其中的一个任务优先级提升了 1 (nice 值 -1)。此时,一个任务应该会获得额外 10% 左右的 CPU 时间,而另一个则会减少 10% CPU 时间。来看看计算结果:1277 / (1024 + 1277) ≈ 0.55,1024 / (1024 + 1277) ≈ 0.45,二者差距刚好在 10% 左右,符合预期。完整的计算函数定义在 <kernel/sched/core.c> 中:
static void set_load_weight(struct task_struct *p)
{
int prio = p->static_prio - MAX_RT_PRIO;
struct load_weight *load = &p->se.load;
/*
* SCHED_IDLE tasks get minimal weight:
*/
if (p->policy == SCHED_IDLE) {
load->weight = scale_load(WEIGHT_IDLEPRIO);
load->inv_weight = WMULT_IDLEPRIO;
return;
}
load->weight = scale_load(prio_to_weight[prio]);
load->inv_weight = prio_to_wmult[prio];
}
调度类 Scheduling Classes
// 为了简单起见,隐藏了部分代码(如 SMP 相关的)
struct sched_class {
// 多个 sched_class 是链接在一起的
const struct sched_class *next;
// 该 hook 会在任务进入可运行状态时调用。它会将调度单元(如一个任务)放到
// 队列中,同时递增 `nr_running` 变量(该变量表示运行队列中可运行的任务数)
void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
// 该 hook 会在任务不可运行时调用。它会将任务移出队列,同时递减 `nr_running`
void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
// 该 hook 可以在任务需要主动放弃 CPU 时调用,但是需要注意的是,它不会改变
// 任务的可运行状态,也就是说依然会在队列中等待下次调度。类似于先 dequeue_task,
// 再 enqueue_task
void (*yield_task) (struct rq *rq);
// 该 hook 会在任务进入可运行状态时调用并检查是否需要抢占当前任务
void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
// 该 hook 用来选择最适合运行的下一个任务
struct task_struct * (*pick_next_task) (struct rq *rq, struct task_struct *prev);
// 该 hook 会在任务修改自身的调度类或者任务组时调用
void (*set_curr_task) (struct rq *rq);
// 通常是在时钟中断时调用,可能会导致任务切换
void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
// 当任务被 fork 时通知调度器
void (*task_fork) (struct task_struct *p);
// 当任务挂掉时通知调度器
void (*task_dead) (struct task_struct *p);
};
-
core.c
包含调度器的核心部分; -
fair.c
实现了 CFS(Comple Faire Scheduler,完全公平任务调度器) 调度器,应用于普通任务; -
rt.c
实现了实时调度,应用于实时任务; -
idle_task.c
当没有其它可运行的任务时,会运行空闲任务。
内核是基于任务的调度策略(SCHED_*)来决定使用何种调度类实现,并会调用相应的方法。SCHED_NORMAL
,SCHED_BATCH
和SCHED_IDLE
进程会映射到fair_sched_class
(由 CFS 实现);SCHED_RR
和SCHED_FIFO
则映射的rt_sched_class
(实时调度器)。
运行队列 runqueue
运行队列数据结构定义如下(位于 <kernel/sched/sched.h>):
// 为了简单起见,隐藏了部分代码(SMP 相关)
// 这个是每个 CPU 都会有的一个任务运行队列
struct rq
{
// 表示当前队列中总共有多少个可运行的任务(包含所有的 sched class)
unsigned int nr_running;
#define CPU_LOAD_IDX_MAX 5
unsigned long cpu_load[CPU_LOAD_IDX_MAX];
// 运行队列负载记录
struct load_weight load;
// 嵌套的 CFS 调度器运行队列
struct cfs_rq cfs;
// 嵌套的实时任务调度器运行队列
struct rt_rq rt;
// curr 指向当前正在运行的进程描述符
// idle 则指向空闲进程描述符(当没有其它可运行任务时,该任务才会启动)
struct task_struct *curr, *idle;
u64 clock;
int cpu;
}
何时运行调度器?
schedule()
会在很多场景下被调用。有的是直接调用,有的则是隐式调用(通过设置
TIF_NEED_RESCHED
来提示操作系统尽快运行调度函数)。以下三个调度时机值得关注下:
时钟中断发生时,会调用 scheduler_tick() 函数,该函数会更新一些和调度有关的数据统计,并触发调度类的周期调度方法,从而间接地进行调度。以 2.6.39 源码为例,可能的调用链路如下:
scheduler_tick
└── task_tick
└── entity_tick
└── check_preempt_tick
└── resched_task
└── set_tsk_need_resched
当前正在运行的任务进入睡眠状态。在这种情况下,任务会主动释放 CPU。通常情况下,该任务会因为等待指定的事件而睡眠,它可以将自己添加到等待队列,并启动循环检查期望的条件是否满足。在进入睡眠前,任务可以将自己的状态设置为 TASK_INTERRUPTABLE(除了任务要等待的事件可唤醒外,也可以被信号唤醒)或者 TASK_UNINTERRUPTABLE(自然是不会理会信号咯),然后调用 schedule() 选择下一个任务运行。
Linux 调度器
Linux 0.0.1 版本就已经有了一个简单的调度器,当然并非适合拥有特别多处理器的系统。该调度器只维护了一个全局的进程队列,每次都需要遍历该队列来寻找新的进程执行,而且对任务数量还有严格限制(NR_TASKS 在最初的版本中只有 32)。下面来看看这个调度器是如何实现的吧:
// 'schedule()' is the scheduler function.
// This is GOOD CODE! There probably won't be any reason to change
// this, as it should work well in all circumstances (ie gives
// IO-bound processes good response etc)...
void schedule(void)
{
int i, next, c;
struct task_struct **p;
// 遍历所有任务,如果有信号,则需要唤醒 `TASK_INTERRUPTABLE` 的任务
for (p = &LAST_TASK; p > &FIRST_TASK; --p)
if (*p) {
if ((*p)->alarm && (*p)->alarm < jiffies) {
(*p)->signal |= (1 << (SIGALRM - 1));
(*p)->alarm = 0;
}
if ((*p)->signal && (*p)->state == TASK_INTERRUPTIBLE)
(*p)->state = TASK_RUNNING;
}
while (1)
{
c = -1;
next = 0;
i = NR_TASKS;
p = &task[NR_TASKS];
// 遍历所有任务,找到时间片最长的那个
while (--i) {
if (!*--p)
continue;
if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
c = (*p)->counter, next = i;
}
if (c)
break;
// 遍历任务,重新设值时间片
for (p = &LAST_TASK; p > &FIRST_TASK; --p)
if (*p)
(*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
}
// 切换到下一个需要执行的任务
switch_to(next);
}
O(n):
// schedule() 算法会遍历所有的任务(O(N)),并且计算出每个任务的
// goodness 值,且挑选出「最好」的任务来运行。
// 以下是部分核心源码,主要是了解下它的思路。
asmlinkage void schedule(void)
{
// 任务(进程)描述符:
// 1. prev: 当前正在运行的任务
// 2. next: 下一个将运行的任务
// 3. p: 当前正在遍历的任务
struct task_struct *prev, *next, *p;
int this_cpu, c; // c 表示权重值
repeat_schedule:
// 默认选中的任务
next = idle_task(this_cpu);
c = -1000;
list_for_each(tmp, &runqueue_head) {
p = list_entry(tmp, struct task_struct, run_list);
if (can_schedule(p, this_cpu)) {
int weight = goodness(p, this_cpu, prev->active_mm);
if (weight > c)
c = weight, next = p;
}
}
}
源码中的 goodness() 函数会计算出一个权重值,它的算法基本思想就是基于进程所剩余的时钟节拍数(时间片),再加上基于进程优先级的权重值。返回值如下:
-
-1000 表示不要选择该进程运行 -
0 表示时间片用完了,需要重新计算 counters(可能会被选中运行) -
正整数:表示 goodness 值(越大越好) -
+1000 表示实时进程,接下来就要选择它运行
-
算法实现非常简单,但是不高效(任务越多,遍历耗费时间越久) -
没有很好的扩展性,多核处理器怎么办? -
对于实时任务调度支持较弱(无论如何作为优先级高的实时任务都需要在遍历完列表后才可以知道)
O(1):
-
全局优先级单位,范围是 0~139,数值越低,优先级越高 -
将任务拆分成实时(099)和正常(100139)两部分。更高优先级任务获得更多时间片 -
即刻抢占(early preemption)。当任务状态变成 TASK_RUNNING
时,内核会检查其优先级是否比当前运行的任务优先级更高,如果是的话,则抢占当前正在运行的任务,切换到该任务 -
实时任务使用静态优先级 -
普通任务使用使用动态优先级。任务优先级会在其使用完自己的时间片后重新计算,内核会考虑它过去的行为,决定它的交互性等级。交互型任务更容易得到调度
O(n) 的调度器会在每个纪元结束后(所有任务的时间片都使用过),才会重新计算任务优先级。而 O(1) 则是在每个任务时间片配额用完后就重新计算优先级。O(1) 调度器为每个 CPU 维护了两个队列,即 active 和 expired。active 队列存放的是时间片尚未用完的任务,而 expired 则是时间片已经耗尽的任务。当一个任务的时间片用完后,就会被转到 expired 队列,而且会重新计算它的优先级。当 active 队列任务全部转移到 expired 队列后,会交换二者(让 active 指向 expired 队列,expired 指向 active 队列)。可以看到,优先级的计算,队列切换都和任务数量多寡无关,能够在 O(1) 时间复杂度下完成。
struct runqueue {
unsigned long nr_running; /* 可运行的任务总数(某个 CPU) */
struct prio_array *active; /* 指向 active 的队列的指针 */
struct prio_array *expired; /* 指向 expired 的队列的指针 */
struct prio_array arrays[2]; /* 实际存放不同优先级对应的任务链表 */
}
通过下面的图可以直观感受下任务队列:
接下来看看 prio_array 是怎么定义的:
struct prio_array {
int nr_active; /* 列表中的任务总数 */
unsigned long bitmap[BITMAP_SIZE]; /* 位图表示对应优先级链表是否有任务存在 */
struct list_head queue[MAX_PRIO]; /* 任务队列(每种优先级对应一个双向链表) */
};
可以看到,在 prio_array 中存在一个位图,它是用来标记每个 priority 对应的任务链表是否存在任务的。接下来看看为何 O(1) 调度器可以在常数时间找到需要运行的任务:
-
常数时间确定优先级:首先会在位图中查找到第一个设置为 1 的位(总共有 140 bits,从第一个 bit 开始搜索,这样可以保证高优先级的任务先得到机会运行),如果找到了就可以确定哪个优先级有任务,假设找到后的值为 priority
; -
常数时间获得下一个任务:在 queue[priority]
对应的任务链表中提取第一个任务来执行(多个任务会轮转执行)。
-
设计上要比 O(n) 调度器更加复杂精妙; -
相对来说扩展性更好,性能更优,在任务切换上的开销更小; -
用来标记任务是否为交互类型的算法还是过于复杂,且容易出错。
CFS 通过在一定时间内运行调度所有的线程来避免饥饿问题。当运行的 线程数在 8 个及以下时,默认的时间周期是 48ms;而当多于 8 个线程时,时间周期就会随着线程数量而增加(6ms * 线程数,之所以选择 6ms,是为了避免频繁抢占,导致上下文切换频繁切换的开销)。由于 CFS 总是会挑选 vruntime 最小的线程执行,它就需要避免某个线程的 vruntime 太小,以至于其它线程需要等待很久才能得到调度(会有饥饿问题)。所以在实践中,CFS 会保证所有线程之间的 vruntime 之差低于抢占时间(6ms),它是通过如下两点来保证的:
当线程创建时,它的 vruntime 值等于运行队列中等待执行线程的最大 vruntime;
当线程从睡眠中唤醒时,它的 vruntime 值会被更新为大于或等于所有待调度线程中最小的 vruntime。使用最小 vruntime 还可以保证频繁睡眠的线程优先被调度,这对于桌面系统非常适合,它会减少交互应用的响应延迟。
CFS 还引入了启发式调度思想来改善高速缓存利用率。例如,当线程被唤醒时,它会检查该线程的 vruntime 和正在运行的线程 vruntime 之差是否非常显著(临界值是 1ms),如果不是的话,则不会抢占当前正在运行的任务。但是这种做法还是以牺牲调度延迟为代价的,算是一种权衡吧。
多核负载均衡:
为了多个处理器上的工作量均衡,CFS 使用了 load 指标来衡量线程和处理器的负载情况。线程的负载和线程的 CPU 平均使用率相关:经常睡眠的线程负载要低于不睡眠的线程负载。类似 vruntime,线程的负载也是线程的优先级加权得到的。而处理器的负载是在该处理器上可运行线程的负载之和。CFS 会尝试均衡处理器的负载。
CFS 会在线程创建和唤醒时关注处理器的负载情况,调度器首先要决定将任务放在哪个处理器的运行队列中。这里也会涉及到启发式思想,比如,如果 CFS 检查到生产者-消费者模型,那么它会将消费者线程尽可能地分散到机器的多个处理器上,因为多数核心都适合处理唤醒的线程。
负载均衡还会周期性发生,每隔 4ms,每个处理器都会尝试从其它处理器偷取一些工作。当然,这种 work-stealing 均衡方法还会考虑机器的拓扑结构:处理器会尝试从距离它们「更近」的其它处理器上尝试窃取工作,而非距离「更远」的处理器(如远程 NUMA 节点)。当处理器决定要从其它处理器窃取任务时,它会尝试在二者之间均衡负载,并且会窃取多达 32 个线程。此外,当处理器进入空闲状态时,它也会立刻调用负载均衡器。
在大型的 NUMA 机器上,CFS 并不会粗暴地比较所有 CPU 的负载,而是以分层的方式进行负载均衡。以一台有两个 NUMA 节点的机器为例,CFS 会先在 NUMA 节点内部的处理器之间进行负载均衡,然后比较 NUMA 节点之间的负载(通过节点内部处理器负载计算得到),再决定要不要在两个节点之间进行负载均衡。如果 NUMA 节点之间的负载差距在 25% 以内,则不会进行负载均衡。总结来说,如果两个处理器(或处理器组)之间的距离越远,那么只有在不平衡性差距越大的情况下才会考虑负载均衡。
运行队列:
CFS 引入了红黑树(本质上是一棵半平衡二叉树,对于插入和查找都有 O(log(N)) 的时间复杂度)来维护运行队列,树的节点值是调度单元的 vruntime,拥有最小 vruntime 的节点位于树的最左下边。
接下来看看 cfs_rq 数据结构的定义(位于 <kernel/sched/sched.h>):
struct cfs_rq
{
// 所有任务的累计权重值
struct load_weight load;
// 表示该队列中有多少个可运行的任务
unsigned int nr_running;
// 运行队列中最小的 vruntime
u64 min_vruntime;
// 红黑树的根节点,指向运行任务队列
struct rb_root tasks_timeline;
// 下一个即将被调度的任务
struct rb_node *rb_leftmost;
// 指向当前正在运行的调度单元
struct sched_entity *curr;
}
CFS 算法实际应用于调度单元(这是一个更通用的抽象,可以是线程、cgroups 等),调度单元数据结构定义如下(位于 <include/linux/sched.h>):
struct sched_entity
{
// 表示调度单元的负载权重(比如该调度单元是一个组,则该值就是该组下所有线程的负载权重的组合)
struct load_weight load; /* for load-balancing */
// 表示红黑树的节点
struct rb_node run_node;
// 表示当前调度单元是否位于运行队列
unsigned int on_rq;
// 开始执行时间
u64 exec_start;
// 总共运行的时间,该值是通过 `update_curr()` 更新的。
u64 sum_exec_runtime;
// 基于虚拟时钟计算出该调度单元已运行的时间
u64 vruntime;
// 用于记录之前运行的时间之和
u64 prev_sum_exec_runtime;
};
虚拟时钟:
static void update_curr(struct cfs_rq *cfs_rq)
{
struct sched_entity *curr = cfs_rq->curr;
u64 now = rq_clock_task(rq_of(cfs_rq));
u64 delta_exec;
if (unlikely(!curr))
return;
// 计算出调度单元开始执行时间和当前之间的差值,即真实运行时间
delta_exec = now - curr->exec_start;
curr->vruntime += calc_delta_fair(delta_exec, curr);
update_min_vruntime(cfs_rq);
}
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
// 如果任务的优先级是默认的优先级(内部 nice 值是 120),那么虚拟运行时间
// 就是真实运行时间。否则,会基于 `__calc_delta` 计算出虚拟运行时间。
if (unlikely(se->load.weight != NICE_0_LOAD))
// 该计算过程基本等同于:
// delta = delta_exec * NICE_0_LOAD / cur->load.weight;
delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
return delta;
}
static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
u64 vruntime = cfs_rq->min_vruntime;
if (cfs_rq->curr)
// 如果此时有任务在运行,就更新最小运行时间为当前任务的 vruntime
vruntime = cfs_rq->curr->vruntime;
if (cfs_rq->rb_leftmost)
{
// 获得下一个要运行的调度单元
struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
struct sched_entity,
run_node);
if (!cfs_rq->curr)
vruntime = se->vruntime;
else
// 保证 min_vruntime 是二者之间较小的那个值
vruntime = min_vruntime(vruntime, se->vruntime);
}
// 这里之所以去二者之间的最大值,是为了保证 min_vruntime 能够单调增长
// 可以想想为什么需要这样做?
cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
}
当任务运行时,它的虚拟时间总是会增加,从而保证它会被移动到红黑树的右侧;
对于高优先级的任务,虚拟时钟的节拍更慢,从而让它移动到红黑树右侧的速度就越慢,因此它们被再次调度的机会就更大些。
选择下一个任务:
struct sched_entity *__pick_first_entity(struct cfs_rq *cfs_rq)
{
// 其实这里取的是缓存的 leftmost 节点
// 所以执行就会更快了
struct rb_node *left = cfs_rq->rb_leftmost;
if (!left)
return NULL;
return rb_entry(left, struct sched_entity, run_node);
}
实时调度器:
SCHED_FIFO: 这个其实就是一个先到先服务的调度算法。这类任务没有时间片限制,它们会一直运行直到阻塞或者主动放弃 CPU,亦或者被更高优先级的实时任务抢占。该类任务总会抢占 SCHED_NORMAL 任务。如果多个任务具有相同的优先级,那它们会以轮询的方式调度(也就是当一个任务完成后,会被放到队列尾部等待下次执行);
SCHED_RR: 这种策略类似于 SCHED_FIFO,只是多了时间片限制。相同优先级的任务会以轮询的方式被调度,每个运行的任务都会一直运行,直到其用光自己的时间片,或者被更高优先级的任务抢占。当任务的时间片用光后,它会重新补充能量,并被加入到队列尾部。默认的时间片是 100ms,可以在 <include/linux/sched/rt.h> 找到其定义。
实时任务的优先级是静态的,不会像之前提到的算法,会重新计算任务优先级。用户可以通过 chrt 命令更改任务优先级。
实现细节:
struct sched_rt_entity
{
struct list_head run_list;
unsigned long timeout;
unsigned long watchdog_stamp;
unsigned int time_slice;
struct sched_rt_entity *back;
struct sched_rt_entity *parent;
/* rq on which this entity is (to be) queued: */
struct rt_rq *rt_rq;
};
SCHED_FIFO 的时间片是 0,可以在 <kernel/sched/rt.c> 中看到具体定义:
int sched_rr_timeslice = RR_TIMESLICE;
static unsigned int get_rr_interval_rt(struct rq *rq,
struct task_struct *task)
{
if (task->policy == SCHED_RR)
return sched_rr_timeslice;
else
return 0;
}
/* Real-Time classes' related field in a runqueue: */
struct rt_rq
{
// 所有相同优先级的实时任务都保存在 `active.queue[prio]` 链表中
struct rt_prio_array active;
unsigned int rt_nr_running;
struct rq *rq; /* main runqueue */
};
/*
* This is the priority-queue data structure of the RT scheduling class:
*/
struct rt_prio_array
{
/* include 1 bit for delimiter */
// 类似 O(1) 调度器,使用位图来标记对应优先级的链表是否为空
DECLARE_BITMAP(bitmap, MAX_RT_PRIO + 1);
struct list_head queue[MAX_RT_PRIO];
};
每次需要在对应优先级链表中遍历查找需要执行任务,这个时间复杂度为 O(n)。所以新的调度器引入了跳表来解决该问题,从而将时间复杂度降低到 O(1)。
全局锁争夺的开销优化,采用 try_lock 替代 lock。
本文分享自微信公众号 - TXP嵌入式(txp1121518wo-)。
如有侵权,请联系 support@oschina.cn 删除。
本文参与“OSC源创计划”,欢迎正在阅读的你也加入,一起分享。