Linux内核设计与实现—进程调度
最近开始学习 Linux 内核，主要参考书籍为《Linux内核设计与实现》，所以本系列大章节和小章节会遵从原书结构，再辅以其他书籍或网上资料对其未理解部分进行补充。
概述
本系列定位为初级文档，不会详细阐述实现原理，只讲解概念和逻辑。
调度程序的定义
调度程序决定将哪个进程投入运行，何时运行以及运行多长时间。调度程序可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。
只要有可以执行的进程，那么就总会有进程正在执行。但是只要系统中可运行的进程的数目比处理器的个数多，就注定某一给定时刻会有一些进程不能执行。
在一组处于可运行状态的进程中选择一个来执行，是调度程序所需完成的基本工作。
调度策略的分类
策略决定调度程序在何时让什么进程运行。不同策略的调度器对系统呈现的风格不同。
###IO消耗型和处理器消耗型
进程可以被分为I/O 消耗型和处理器消耗型。
I/O消耗型指的是进程大部分时间用来提交I/O或者等待I/O请求。这样的进程进程处于可运行状态，一般都是运行一小会，更多时间是处于阻塞状态。常见的IO消耗型进程通常有图像界面，鼠标或键盘类。
处理器消耗型是把大多数时间用于执行代码，除非被抢占，否则他们一直不停的运行。常见的消耗型进程通常有算法，业务类。
进程优先级
调度算法中最基本的一类就是基于优先级的调度。通常做法是高优先级先运行，低优先级后运行，优先级一样则轮转运行。
Linux 采用了两种不同的优先级范围：
第一种是 Nice 值，Nice值的范围是-20~+19，拥有Nice值越大的进程的实际优先级越小（即Nice值为+19的进程优先级最小，为-20的进程优先级最大），默认的Nice值是0。
“Nice值”这个名称来自英文单词nice，意思为友好。Nice值越高，这个进程越“友好”，就会让给其他进程越多的时间。
第二种范围是实时优先级PRI值，其值是可配。默认情况下它的变化范围是从0 到99 （包括0 和99) 。与nice 值意义相反，越高的实时优先级数值意味着进程优先级越高。
最终的进程优先级为PRI(now) = PRI(start) + NI(now)。Linux操作系统中，我们是通过修改NI值的方式，来修改PRI优先级的大小。
在Linux中使用ps -efl来查看PRI和NI值。
mark@vxworks:~/github/2beanet$ ps -elf
F S UID PID PPID C PRI NI ADDR SZ WCHAN STIME TTY TIME CMD
4 S root 1 0 0 80 0 - 42022 - Apr15 ? 00:00:40 /lib/systemd/systemd splash --system --deserialize 56
1 S root 2 0 0 80 0 - 0 - Apr15 ? 00:00:00 [kthreadd]
1 I root 3 2 0 60 -20 - 0 - Apr15 ? 00:00:00 [rcu_gp]
1 I root 4 2 0 60 -20 - 0 - Apr15 ? 00:00:00 [rcu_par_gp]
1 I root 5 2 0 60 -20 - 0 - Apr15 ? 00:00:00 [slub_flushwq]
1 I root 6 2 0 60 -20 - 0 - Apr15 ? 00:00:00 [netns]
1 I root 8 2 0 60 -20 - 0 - Apr15 ? 00:00:00 [kworker/0:0H-events_highpri]
1 I root 10 2 0 60 -20 - 0 - Apr15 ? 00:00:00 [mm_percpu_wq]
1 I root 11 2 0 80 0 - 0 - Apr15 ? 00:00:00 [rcu_tasks_kthread]
1 I root 12 2 0 80 0 - 0 - Apr15 ? 00:00:00 [rcu_tasks_rude_kthread]
1 I root 13 2 0 80 0 - 0 - Apr15 ? 00:00:00 [rcu_tasks_trace_kthread]
1 S root 14 2 0 80 0 - 0 - Apr15 ? 00:00:08 [ksoftirqd/0]
1 I root 15 2 0 80 0 - 0 - Apr15 ? 00:05:23 [rcu_preempt]
1 S root 16 2 0 -40 - - 0 - Apr15 ? 00:00:04 [migration/0]
1 S root 17 2 0 9 - - 0 - Apr15 ? 00:00:00 [idle_inject/0]
1 S root 19 2 0 80 0 - 0 - Apr15 ? 00:00:00 [cpuhp/0]
5 S root 20 2 0 80 0 - 0 - Apr15 ? 00:00:00 [cpuhp/1]
1 S root 21 2 0 9 - - 0 - Apr15 ? 00:00:00 [idle_inject/1]
1 S root 22 2 0 -40 - - 0 - Apr15 ? 00:00:04 [migration/1]
1 S root 23 2 0 80 0 - 0 - Apr15 ? 00:00:04 [ksoftirqd/1]
1 I root 25 2 0 60 -20 - 0 - Apr15 ? 00:00:00 [kworker/1:0H-events_highpri]
5 S root 26 2 0 80 0 - 0 - Apr15 ? 00:00:00 [cpuhp/2]
1 S root 27 2 0 9 - - 0 - Apr15 ? 00:00:00 [idle_inject/2]
1 S root 28 2 0 -40 - - 0 - Apr15 ? 00:00:04 [migration/2]
1 S root 29 2 0 80 0 - 0 - Apr15 ? 00:01:44 [ksoftirqd/2]
1 I root 31 2 0 60 -20 - 0 - Apr15 ? 00:00:00 [kworker/2:0H-events_highpri]
5 S root 32 2 0 80 0 - 0 - Apr15 ? 00:00:00 [cpuhp/3]
1 S root 33 2 0 9 - - 0 - Apr15 ? 00:00:00 [idle_inject/3]
1 S root 34 2 0 -40 - - 0 - Apr15 ? 00:00:04 [migration/3]
1 S root 35 2 0 80 0 - 0 - Apr15 ? 00:00:14 [ksoftirqd/3]
1 I root 37 2 0 60 -20 - 0 - Apr15 ? 00:00:00 [kworker/3:0H-events_highpri]
时间片
时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。
调度策略必须规定一个默认的时间片，时间片过长会导致系统对交互的响应表现欠佳，让人觉得系统无法并发执行应用程序；
时间片太短会明显增大进程切换带来的处理器耗时，因为肯定会有相当一部分系统时间用在进程切换上，而这些进程能够用来运行的时间片却很短。
任何长时间片都将导致系统交互表现欠佳。很多操作系统中都特别重视这一点，所以默认的时间片很短，如10ms。
调度策略的活动
根据系统的进程自动分配CPU。
比如说现在两个可运行的进程，文字编辑程序和视频编码程序。文本编辑程序是I/O消耗型，大部分时间用于阻塞等待用户键盘输入，视频编码程序属于处理器消耗型，大量的时间用于视频解码运算。
用户希望按下按键能立马响应，而对视频编码没有严格的要求，用户分辨不出是立刻就运行还是延迟后在执行。
理想情况是调度器应该给予文本编辑程序相比视频编码程序更多的处理器时间，因为它属于交互式应用。
对文本编辑器而言，我们有两个目标：
- 我们希望系统给它更多的处理器时间，这并非因为它需要更多的处理器时间（其实它不需要），是因为我们希望在它需要时总是能得到处理器；
- 我们希望文本编辑器能在其被唤醒时（也就是当用户打字时）抢占视频解码程序。这样才能确保文本编辑器具有很好的交互性能，以便能响应用户输入。
在多数操作系统中，上述目标的达成是要依靠系统分配给文本编辑器比视频解码程序更高的优先级和更多的时间片。
在Linux中，默认调度器为CFS（Completely Fair Scheduler，完全公平调度器），它是通过分配一个给定的处理器使用比来实现这个目的。假如文本编辑器和视频解码程序是仅有的两个运行进程，并且又具有同样的nice 值，那么处理器的使用比将都是50％——它们平分了处理器时间。
但因为文本编辑器将更多的时间用于等待用户输人，因此它肯定不会用到处理器的50% 。同时，视频解码程序无疑将能有机会用到超过50％的处理器时间，以便它能更快速地完成解码任务。
在上述场景中， 一旦文本编辑器被唤醒， CFS注意到给它的处理器使用比是50% ，但是其实它却用得少之又少。特别是， CFS 发现文本编辑器比视频解码器运行的时间短得多。
这种情况下，为了兑现让所有进程能公平分享处理器的承诺，它会立刻抢占视频解码程序，让文本编辑器投入运行。文本编辑器运行后，立即处理了用户的击键输入后，又一次进入睡眠等待用户下一次输入。因为文本编辑器井没有消费掉承诺给它的50％处理器使用比，因此情况依旧， CFS 总是会毫不犹豫地让文本编辑器在需要时被投入运行，而让视频处理程序只能在剩下的时刻运行。
Linux的调度策略
Linux内核支持的调度策略如下：
（1）限期进程使用限期调度策略（SCHED_DEADLINE）。
限期调度策略有3个参数：运行时间runtime、截止期限deadline和周期period。
每个周期运行一次，在截止期限之前执行完，一次运行的时间长度是runtime。
（2）实时进程支持两种调度策略：先进先出调度（SCHED_FIFO）和轮流调度（SCHED_RR）。
SCHED_FIFO 实现了一种简单的、先人先出的调度算法。
一但一个SCHED_FIFO 级进程处于可执行状态，就会一直执行，直到它自己受阻塞或显式地释放处理器为止。只有更高优先级的SCHED_FIFO 或者SCHED_RR任务才能抢占SCHED_FIFO 任务。如果有两个或者更多的同优先级的SCHED_FIFO 级进程，它们会轮流执行，但是依然只有在它们愿意让出处理器时才会退出。
SCHED_RR 与SCHED_FIFO 大体相同， 只是SCHED_RR 级的进程在耗尽事先分配给它的 时间后就不能再继续执行了。也就是说， SCHED_RR 是带有时间片的SCHED_FIFO。当SCHED_RR 任务耗尽它的时间片时，在同一优先级的其他实时进程被轮流调度。
（3）普通进程支持两种调度策略：标准轮流分时（SCHED_NORMAL，在POSIX中叫做SCHED_OTHER）和空闲（SCHED_IDLE）。
标准轮流分时策略使用完全公平调度算法，把处理器时间公平地分配给每个进程。
空闲调度策略用来执行优先级非常低的后台作业，优先级比使用标准轮流分时策略和相对优先级为19的普通进程还要低，进程的相对优先级对空闲调度策略没有影响。
Linux调度器类
这5种调度类的优先级从高到低依次为：停机调度类、限期调度类、实时调度类、公平调度类和空闲调度类。
- 停机调度类
停机调度类是优先级最高的调度类，停机进程（stop-task）是优先级最高的进程，可以抢占所有其他进程，其他进程不可以抢占停机进程。
停机（stop是指stop machine）的意思是使处理器停下来，做更紧急的事情。
停机进程没有时间片，如果它不主动让出处理器，那么它将一直霸占处理器。
- 限期调度类
限期调度类使用最早期限优先算法，使用红黑树（一种平衡的二叉树）把进程按照绝对截止期限从小到大排序，每次调度时选择绝对截止期限最小的进程。如果限期进程用完了它的运行时间，它将让出处理器，并且把它从运行队列中删除。在下一个周期的开始，重新把它添加到运行队列中。
- 实时调度器
实时调度类为每个调度优先级维护一个队列，使用位图法用来快速查找第一个非空队列，然后用链表数组串联任务，跟FreeRTOS类似。
- 公平调度类
CFS（Completely Fair Scheduler）是 Linux 内置（也是目前默认）的一个内核调度器 ， 如名字所示，它实现了所谓的“完全公平”调度算法，将 CPU 资源均匀地分配给各进程（ 在内核代码中称为“任务”，task）。简单来说，如果一台机器有一个 CPU 多个（计算密集型）进程，那采用 CFS 调度器。
- 两个进程：每个进程会各占 50% CPU 时间
- 四个进程：每个进程会各占 25% CPU 时间
- 空闲调度器
每个处理器上有一个空闲线程，即0号线程。空闲调度类的优先级最低，仅当没有其他进程可以调度的时候，才会调度空闲线程。
抢占与上下文切换
上下文切换， 也就是从一个可执行进程切换到另一个可执行进程。
上下文切换调用schedule() 函数，schedule() 在调用context_switch()进行处理。它完成了最基本的两项工作：
- 调用声明在中的switch_mm(), 该函数负责把虚拟内存从上一个进程映射切换到新进程中。
- 调用声明在中的switch_to(), 该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复栈信息和寄存器信息，还有其他任何与体系结
构相关的状态信息，都必须以每个进程为对象进行管理和保存。
内核提供need_resched()函数用于检测TIF_NEED_RESCHED是否被置位，用于判断需要重新调度。
在system_tick中断中和主动调用schedule()切换线程时，会对TIF_NEED_RESCHED 置位。
当返回用户空间以及从中断返回的时候，内核也会检查TIF_NEED_RESCHED 标志。如果已被设置， 会重新选择进程执行。
用户抢占
内核在即将返回用户空间的时候，如果need_resched 标志被设置，会导致schedule() 被调用，此时就会发生用户抢占。内核无论是在中断处理程序还是在系统调用后返回，都会检查need_resched 标志，如果它被设置了， 那么，内核会选择一个其他（更合适的）进程运行。
简而言之，用户抢占在以下情况时产生：
- 从系统调用返回用户空间时
- 从中断处理程序返回用户空间时
内核抢占
Linux 在2.6版本后通过config PREEMPT 配置为内核抢占。
在不支持内核抢占的内核中，内核代码可以一直执行，到它完成为止。在内核空间运行的进程不具备抢占性。内核代码一直要执行到完成（返回用户空间）或明显的阻塞为止。现在，只要重新调度是安全的（没有持有锁），内核就可以在任何时间抢占正在执行的任务。
内核抢占会发生在：
- 中断处理程序正在执行，且返回内核空间之前
- 内核代码再一次具有可抢占性的时候
- 如果内核中的任务显式地调用schedule()
- 如果内核中的任务阻塞（ 这同样也会导致调用schedule() ）
简单理解就是被抢占之前是用户空间，就是用户抢占，被抢占之前是内核空间就是内核抢占。
我们在看一下代码就更明确这两个概念了。
我们知道当中断发生在用户空间，即 USR mode 时执行 __irq_usr，当中断发生在内核空间即 SVC mode 时执行 __irq_svc。
// 抢占之前是运行在用户空间，比如说调用文件系统接口(open, read, write)等
__irq_usr:
usr_entry
kuser_cmpxchg_check
irq_handler
get_thread_info tsk
mov why, #0
b ret_to_user_from_irq
UNWIND(.fnend )
ENDPROC(__irq_usr)
// 抢占之前运行在内核空间
**__irq_svc**:
svc_entry
irq_handler
**#ifdef CONFIG_PREEMPT // 判断是否支持内核抢占**
ldr r8, [tsk, #TI_PREEMPT] @ get preempt count
ldr r0, [tsk, #TI_FLAGS] @ get flags
teq r8, #0 @ if preempt count != 0
movne r0, #0 @ force flags to 0
tst r0, #_TIF_NEED_RESCHED
blne svc_preempt
**#endif**
总结
这一章主要描述了调度器的基本概念，以及常见的调度策略和Linux支持的调度类，在最后讲解了一些进程切换相关的知识。如果对RTOS比较熟悉的同学，虽然RTOS简单很多，但毕竟概念相通，阅读起来会比较轻松。如果没有RTOS基础的同学，可以读一下我之前写过的FreeRTOS源码分析相关章节，相信一定大有裨益。