共计 8879 个字符，预计需要花费 23 分钟才能阅读完成。
过程调度
过程调度程序是从一组处于可运行状态的过程中，决定其中一个过程何时运行以及运行多长时间。
多任务
- 多任务操作系统就是能同时并发地交互执行多个过程的操作系统；能使得多个过程处于阻塞或者睡眠状态直到特定工夫产生，进入可执行状态。
- 分成抢占式 preemptive multitasking 和非抢占式 cooperative multitasking（通过退让进行调度，悬挂的过程会让零碎解体等）。Linux 是抢占式，即由调度程序决定什么时候挂起以后过程，让其余过程取得执行。
- 工夫片是过程被抢占之前能够运行的工夫，他是被预设的。局部操作系统通过动静工夫片计算的形式，进行工夫片治理，以达到调度的目标。但 Linux 的偏心调度算法并没有采取工夫片来达到偏心调度。
策略
策略决定调度程序何时让过程运行。
首先对过程分类：I/ O 消耗型和处理器消耗型。注：响应工夫是从用户角度思考。
- I/ O 消耗型如交互式程序，常常处于可运行状态，但只运行很短时间，绝大部分工夫在期待 I / O 申请。但他有很高的交互需要，须要很短的响应工夫。
- 处理器消耗性须要大量工夫解决计算。调度器应升高他们的应用频率，缩短其执行工夫。
有局部程序两者特点都有，如 X Windows 服务。调度程序须要均衡响应工夫和最大零碎利用率。Linux 对程序响应做了优化，同时兼顾了处理器消耗型的过程。
过程优先级
调度算法最简略的是基于优先级的调度。思维是优先级高的先运行，同级的轮转调度；某些零碎中优先级高的，工夫片也长；抉择工夫片未用完的，优先级高的先运行。
Linux 有两种优先级:nice 和实时优先级。nice 值越高，优先级越低 (-20-19)，获取的处理器工夫。nice 是 Unix 零碎的标准化概念，但各个系统的实现定义不同。Linux 中代表的是工夫片的比例(ps -el =>NI)。实时优先级能够配置（0-99），与优先级正相干，任何实时过程的优先级都高于一般过程，与 nice 优先级互不相交,ps -eo state, uid, pid, ppid, rtprio, time, comm 其中 rtprio 指的就是实时优先级，- 代表不是实时过程。
工夫片
被抢占前能继续运行的工夫。如果默认的话会呈现很多问题：太长交互性差，无奈并发的感觉；太短增大过程切换的开销。Linux 并没有间接调配工夫片到过程，他采取的是 处理器应用比例，过程运行的工夫片与零碎负载无关，与 nice 无关。CFS 齐全偏心调度算法的抢占机会取决于心的可执行程序耗费了多少处理器应用比，如果耗费的应用比比以后过程小，则新过程立即投入运行，抢占以后过程。
举例：一个文字编辑程序，重交互 I / O 消耗型（须要更多解决工夫但理论解决工夫少；须要被唤醒时抢占）；一个视频处理程序，处理器消耗型。Linux 各调配 50% 给两个程序，雷同 nice 值，文本编辑器更多工夫在期待客户输出，他不会用到处理器的 50%；视频解码程序超过 50% 应用工夫；但 CFS 为了 兑现让所有过程能偏心分享处理器的承诺，他会抢占视频解码程序。
Linux 调度算法
调度器类
Linux 调度器是以模块形式提供，容许不同类型的过程能够有针对性地抉择调度算法，容许多种不同的可动静增加的调度算法并存，每个调度器都有一个优先级，根底的调度器代码定义在 kernel/sched.c 文件中，他会依照优先级程序遍历调度类，领有一个可执行过程的最高优先级的调用器类胜出，去抉择上面要执行的那一个程序。
CFS 算法
CFS 是针对一般过程的调度算法，SCHED_NORMAL（POSIX 中 SCHED_OTHER），定义在 kernel/sched_fair.c 中。他的次要思维是过程调度的成果应该如同零碎具备一个现实中的完满的多任务处理器，在这个零碎中，每个过程都能取得 1 / n 的处理器工夫，n 为可运行的过程数量。为了兼顾过程切换的开销和缓存效率，CFS 容许每个过程运行一段时间、循环轮转、抉择运行起码的过程作为下一个运行过程，而不再采纳调配给每个过程工夫片的做法了，CFS 在所有可运行的过程的总数根底上计算一个过程应该运行多久。nice 为权重，任何过程所获取的工夫是由他本人和其余所有可运行程序 nice 值的绝对差值决定的，而不是 nice 的绝对值比方权重 0 和 5，取得 15ms 和 5ms；权重 15 和 20，同样取得 15ms 和 5ms。在调度过程中，CFS 设置了一个指标提早作为调度周期 20ms，同时设置了 1ms 作为最小粒度（在无穷多过程的状况下，每个过程至多运行 1ms）。
linux 调度算法的实现
kernel/sched/fair.c 中，四个组成部分：
- 工夫记账
- 过程抉择
- 调度器入口
-
睡眠和唤醒
工夫记账
-
调度器实体构造
struct sched_entity { /* For load-balancing: */ struct load_weight load; 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_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; /* cached value of my_q->h_nr_running */ unsigned long runnable_weight; #endif #ifdef CONFIG_SMP /* * Per entity load average tracking. * * Put into separate cache line so it does not * collide with read-mostly values above. */ struct sched_avg avg; #endif };作为 se 成员变量放在 struct task_struct 中，他保护每一个过程运行的工夫记账，保障每个过程只有在偏心调配给他的处理器工夫内运行。
- 虚构实时
vruntime 寄存过程的虚构运行工夫，该运行工夫的计算是通过了所有可运行过程总数的标准化。虚构工夫是 ns 为单位的，与定时器的节拍器不再相干，CFS 用 vruntime 记录一个程序运行了多长时间还要运行多长时间。
/*
* Update the current task's runtime statistics.
*/
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;
if (unlikely((s64)delta_exec <= 0))
return;
curr->exec_start = now;
if (schedstat_enabled()) {
struct sched_statistics *stats;
stats = __schedstats_from_se(curr);
__schedstat_set(stats->exec_max,
max(delta_exec, stats->exec_max));
}
curr->sum_exec_runtime += delta_exec;
schedstat_add(cfs_rq->exec_clock, delta_exec);
curr->vruntime += calc_delta_fair(delta_exec, curr);
update_min_vruntime(cfs_rq);
if (entity_is_task(curr)) {struct task_struct *curtask = task_of(curr);
trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
cgroup_account_cputime(curtask, delta_exec);
account_group_exec_runtime(curtask, delta_exec);
}
account_cfs_rq_runtime(cfs_rq, delta_exec);
}update_curr()由零碎定时器周期性调用，无论是过程处于可运行态还是不可运行状态。vruntime 能够获取给定过程的运行工夫，而且可晓得谁应该是下一个被运行的过程。
过程抉择
抉择最小的 vruntime 过程，如何实现？
Linux 通过红黑树来组织可运行过程队列，自均衡二叉搜寻树，以树节点模式存在的数据，通过键值间接疾速索引节点上的数据。获取最右边的节点
static struct sched_entity *__pick_next_entity(struct sched_entity *se)
{struct rb_node *next = rb_next(&se->run_node);
if (!next)
return NULL;
return __node_2_se(next);
}向树中退出过程：
/*
* Enqueue an entity into the rb-tree:
*/
static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{rb_add_cached(&se->run_node, &cfs_rq->tasks_timeline, __entity_less);
}
/**
* rb_add_cached() - insert @node into the leftmost cached tree @tree
* @node: node to insert
* @tree: leftmost cached tree to insert @node into
* @less: operator defining the (partial) node order
*
* Returns @node when it is the new leftmost, or NULL.
*/
static __always_inline struct rb_node *
rb_add_cached(struct rb_node *node, struct rb_root_cached *tree,
bool (*less)(struct rb_node *, const struct rb_node *))
{
struct rb_node **link = &tree->rb_root.rb_node;
struct rb_node *parent = NULL;
bool leftmost = true;
while (*link) {
parent = *link;
if (less(node, parent)) {link = &parent->rb_left;} else {
link = &parent->rb_right;
leftmost = false;
}
}
rb_link_node(node, parent, link);
rb_insert_color_cached(node, tree, leftmost);
return leftmost ? node : NULL;
}从树中删除过程，删除动作产生在过程梗塞或者终止
static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
{rb_erase_cached(&se->run_node, &cfs_rq->tasks_timeline);
}
void rb_erase(struct rb_node *node, struct rb_root *root)
{
struct rb_node *rebalance;
rebalance = __rb_erase_augmented(node, root, &dummy_callbacks);
if (rebalance)
____rb_erase_color(rebalance, root, dummy_rotate);
}
调度器入口
次要入口是 schedule()函数，在 kernel/sched/core.c
static struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{return __pick_next_task(rq, prev, rf);
}
/*
* 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 lose the
* opportunity to pull in more work from other CPUs.
*/
if (likely(prev->sched_class <= &fair_sched_class &&
rq->nr_running == rq->cfs.h_nr_running)) {p = pick_next_task_fair(rq, prev, rf);
if (unlikely(p == RETRY_TASK))
goto restart;
/* Assume the next prioritized class is idle_sched_class */
if (!p) {put_prev_task(rq, prev);
p = pick_next_task_idle(rq);
}
return p;
}
restart:
put_prev_task_balance(rq, prev, rf);
for_each_class(class) {p = class->pick_next_task(rq);
if (p)
return p;
}
BUG(); /* The idle class should always have a runnable task. */}schedule 先找一个优先级最高的调度类，有运行队列，而后问下个运行的过程是谁。
睡眠和唤醒
休眠（被阻塞）（期待某些事件 IO 或者硬件）的过程处于一个不可执行的状态，休眠必须以轮询的形式实现。内核的操作：过程把本人标记为休眠状态，从可执行红黑树中移出，放入期待队列，而后调用 schedule()抉择和执行一个其余过程；唤醒过程相同：过程被设置为可执行状态，而后再从期待队列中移到可执行红黑树中
-
期待队列
期待队列是由期待某些事件产生的过程组成的简略链表，内核用wake_queue_head_t来代表期待队列。DECLARE_WAITQUEUE()动态创立，也能够由init_waitqueue_head()动态创建。过程把本人放入期待队列中设置成不可执行状态。当与期待队列相干的事件产生的时候，队列上的过程就会被唤醒。
在内核中进行休眠的举荐操作：// 创立一个期待队列的项 DEFINE_WAIT(wait); // 把本人退出队列，期待 wake_up() add_wait_queue(q, &wait); while (!condition) {// 调用 prepare_to_wait()将过程的状态变更为 TASK_INTERRUPTIBLE 或者 TASK_UNTERRUPTIBLE。而且该函数如果有必要的话会将过程加回到期待队列，这是在接下来循环遍历中所须要的。prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE); // 如果状态被设置为 TASK_INTERRUPTIBLE, 则信号唤醒过程。这就是所谓的伪唤醒（唤醒不是因为工夫产生），因而查看并解决信号。// 当过程被唤醒的时候，它会再次查看条件是否为真，如果是，他就退出循环；如果不是，他再次调用 schedule()并始终反复这步操作。if(signal_pending(current)) schedule();} // 当条件满足后，过程将本人设置为 TASK_RUNNING 并调用 finish_wait()办法把本人移出期待队列。finish_wait(&q, &wait);如果在过程开始休眠之前条件就曾经达成了，那么循环会退出，过程不会存在谬误地进入休眠的偏向。内核代码在循环体内经常须要实现一些其余的工作。
- 唤醒
唤醒操作是通过函数 wake_up() 进行，会唤醒指定的期待队列上的所有过程。它调用函数 try_to_wake_up(), 该函数负责将过程设置为TASK_RUNNING 状态，调用 enqueue_task() 将此过程放入红黑树中，如果被唤醒的过程优先级比以后正在执行的过程的优先级高，还要设置 need_resched 标记。但存在 假唤醒，有时候过程被唤醒并不是因为他所期待的条件达成了才须要一个循环解决来保障他期待的条件真正达成。
抢占和上下文切换
- 上下文切换就是从一个可执行过程切换到另一个可执行过程，由 kernel/sched.c 中的 context_switch()函数负责，schedule()会调用该函数。
- 调用申明在 <asm/mmu_context.h> 中的 switch_mm()，该函数负责把虚拟内存从上一个过程映射切换到新过程中。
- 调用申明在 <asm/system.h> 中的 switch_to(), 负责从上一个过程的处理器状态切换到新过程的处理器状态。这包含保留，复原栈信息和寄存器信息，还有其余任何与体系相干的状态信息，都必须以每个过程为对象进行治理和保留。
- 内核通过查看 need_resched 标记来确定是否须要调用 schedule(); 过程要被抢占时,schedule_tick()；一个更高优先级的过程进入可执行状态时，try_to_wake_up()也会设置这个标记，内核查看该标记，示意其余过程要被运行，须要调用调度程序。
| 函数 | 目标 |
|---|---|
| set_tsk_need_resched() | 设置指定过程 need_resched 标记 |
| clear_tsk_need_resched() | 革除 |
| need_resched() | 查看 |
每个过程都含有这个标记位，不是全局变量，存在 thread_info 构造体中，
用户抢占
再次返回用户空间以及从中断返回时也会进行查看，如果被置位会再次执行调度程序，抉择一个新的过程执行，被称为用户抢占
内核抢占
Linux 反对内核抢占，调度程序能够在一个内核级任务执行的时候进行调度。不反对内核抢占的零碎会让内核代码始终执行，直到实现返回用户空间或者显著阻塞。
只有没有持有锁，内核就能够进行抢占。实现形式：
- thread_info 引入 preempt_count 计数器，初始值为 0，每当应用锁 +1, 开释 -1，= 0 能够抢占。状况 1：中断返回，内核查看 need_resched 和 preempt_count，如果前者置位，后者为 0，调度程序执行。后者不为 0，返回以后执行过程。所有锁开释后，会查看 need_resched，如果置位，调用调度程序。
- 内核过程被阻塞或者显式调用 schedule()。
实时调度策略
两种实时调度策略：SCHED_FIFO 和 SCHED_RR 是当初 kernel/sched_rt.c。一般的，非实时的为 SCHED_NORMAL。
- FIFO：先进先出，不必工夫片，处于运行状态的 SCHED_FIFO 过程比处于 SCHED_NORMAL 过程先被调度。一旦处于可执行，会始终执行，直到受阻塞或者显式开释处理器。只有更高优先级的 SCHED_FIFO 或者 SCHED_RR 过程能力抢占其工作。同级轮流执行，只有他们违心让出处理器的时候才会退出。只有其在执行，低优先级的只能期待至其不可运行状态。
- SCHED_RR 是带工夫片的 SCHED_FIFO。工夫片耗尽后，同级别实时过程轮流调度，工夫片只能用来调度同一优先级的。SCHED_FIFO 高优先级立刻抢占，但低级别优先级绝不能抢占 SCHED_RR 工作，即便他工夫片用尽。
应用动态优先级，优先级从 0 -MAX_RT_PRIO-1（99 默认）与 SCHED_NORMAL 的 nice 共享取值空间,nice 从 -20～+19 对应 100-139 实时优先级。
零碎调用
nice(): 只有超级用户能力调用他应用正数, sched_setscheduler(),get : 读取或者该信 task_struct 的 policy 和 rt_priority; sched_setparam(), get(): 设置实时优先级; sched_get_priority_max(),min();sched_rr_get_interval()获取工夫片;sched_setaffinity(),get 设置亲和力: 容许用户设置过程在哪个处理器上执行 task_struct 中的 cpus_allowed 位掩码，默认 1，都容许;sched_yield()让出处理器：实时过程被挪动到优先级队列的开端，一般过程被放优先级队列最初和过期队列中，保障一段时间内不执行，能够间接调用 yeild()。
