读书笔记.Linux内核设计与实现.4 linux

进程调度进程调度程序是从一组处于可运行状态的进程中，决定其中一个进程何时运行以及运行多长时间。
多任务

多任务操作系统就是能同时并发地交互执行多个进程的操作系统；能使得多个进程处于阻塞或者睡眠状态直到特定时间发生，进入可执行状态。
分成抢占式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_weightload; struct rb_noderun_node; struct list_headgroup_node; unsigned inton_rq; u64exec_start; u64sum_exec_runtime; u64vruntime; u64prev_sum_exec_runtime; u64nr_migrations; #ifdef CONFIG_FAIR_GROUP_SCHED intdepth; 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 longrunnable_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_avgavg; #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()会调用该函数。
调用声明在中的switch_mm()，该函数负责把虚拟内存从上一个进程映射切换到新进程中。
调用声明在中的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实时优先级。
系统调用 【读书笔记.Linux内核设计与实现.4】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()。