一、什么是进程调度
出现背景：
无论是在批处理系统还是分时系统中，用户进程数一般都多于处理机数、这将导致它们互相争夺处理机。另外，系统进程也同样需要使用处理机。这就要求进程调度程序按一定的策略，动态地把处理机分配给处于就绪队列中的某一个进程，以使之执行。
进程调度，是确保进程能有效工作的一个内核子系统。
调度程序负责决定将哪些进程投入到运行，何时进行以及运行多长时间。
进程调度程序（通常简称为调度程序）可看成是可运行态进程之间分配有限的处理器时间资源的内核子系统。
进程调度是对TASK_RUNNING状态的进程进行调度， 如果进程不可执行(正在睡眠或其他)，那么它跟进程调度没多大关系。
我们说进程调度性能的衡量方法可分为定形和定量两种。在定形衡量方面，首先是调度的可靠性。包括一次进程调度是否可能引起数据结构的破坏等。这要求我们对调度时机的选择和保存CPU现场十分谨慎。另外，简洁性也是衡量进程调度的一个重要指标，由于调度程序的执行涉及到多个进程和必须进行上下文切换，如果调度程序过于繁琐和复杂，将会耗去较大的系统开销。这在用户进程调用系统调用较多的情况下，将会造成响应时间大幅度增加。
二、linux的上下文
参考：https://www.cnblogs.com/lambda107/archive/2010/08/10/1795767.html
2.1 内核态与用户态
（1）**当一个任务（进程）执行系统调用而陷入内核代码中执行时，称进程处于内核运行态（内核态）。**此时处理器处于特权级最高的（0级）内核代码中执行。当进程处于内核态时，执行的内核代码会使用当前进程的内核栈。每个进程都有自己的内核栈。
（2）**当进程在执行用户自己的代码时，则称其处于用户运行态（用户态）。**此时处理器在特权级最低的（3级）用户代码中运行。当正在执行用户程序而突然被中断程序中断时，此时用户程序也可以象征性地称为处于进程的内核态。因为中断处理程序将使用当前进程的内核栈。
上下文context： 上下文简单说来就是一个环境。
2.2 进程上下文
用户空间的应用程序，通过系统调用，进入内核空间。这个时候用户空间的进程要传递很多变量、参数的值给内核，内核态运行的时候也要保存用户进程的一些寄存 器值、变量等。所谓的“进程上下文”，可以看作是用户进程传递给内核的这些参数以及内核要保存的那一整套的变量和寄存器值和当时的环境等。
用户进程在执行系统调用，或者发生一个异常的时候，这时这个进程就进入了内核空间，这时候对内核来说就叫做进程上下文
进程上下文，一定是进行了系统调用或者异常执行，导致CPU从用户空间到内核空间了，简单理解点，可以把执行在用户空间的代码叫做进程上文，执行在内核空间的叫做进程下文
相对于进程而言，就是进程执行时的环境。具体来说就是各个变量和数据，包括所有的寄存器变量、进程打开的文件、内存信息等。一个进程的上下文可以分为三个部分:用户级上下文、寄存器上下文以及系统级上下文。
（1）用户级上下文: 正文、数据、用户堆栈以及共享存储区；
（2）寄存器上下文: 通用寄存器、程序寄存器(IP)、处理器状态寄存器(EFLAGS)、栈指针(ESP)；
（3）系统级上下文: 进程控制块task_struct、内存管理信息(mm_struct、vm_area_struct、pgd、pte)、内核栈。
当发生进程调度时，进行进程切换就是上下文切换(context switch).操作系统必须对上面提到的全部信息进行切换，新调度的进程才能运行。而系统调用进行的模式切换(mode switch)。模式切换与进程切换比较起来，容易很多，而且节省时间，因为模式切换最主要的任务只是切换进程寄存器上下文的切换。
2.3 中断上下文
硬件通过触发信号，导致内核调用中断处理程序，进入内核空间。这个过程中，硬件的 一些变量和参数也要传递给内核，内核通过这些参数进行中断处理。所谓的“ 中断上下文”，其实也可以看作就是硬件传递过来的这些参数和内核需要保存的一些其他环境（主要是当前被打断执行的进程环境）。中断时，内核不代表任何进程运行，它一般只访问系统空间，而不会访问进程空间，内核在中断上下文中执行时一般不会阻塞。
当内核在执行一个中断处理函数或者执行中断下半部时，这时候，内核是处在中断上下文
这里引入一个中断下半部，那就应该有中断上半部
中断上半部： 中断处理程序是上半部，它接收到一个中断，就立即执行，但只做有严格时限的工作
中断下半部： 主要做被允许能稍后完成的工作。
2.3 两者区别
- 进程上下文可以睡眠，也可以调用调度程序
- 中断上下文不可以睡眠，不能使用信号量
- 中断上半部应该快速，不执行耗时任务，应该交由中断处理例程下半部来处理
- 因为中断上下文是和特定进程无关的，它是内核代表硬件运行在内核空间，所以在中断上下文无法访问用户空间的虚拟地址
- 中断处理例程可以被更高级别的IRQ中断。如果想禁止这种中断，可以将中断处理例程定义成快速处理例程，相当于告诉CPU，该例程运行时，禁止本地CPU上所有中断请求。这直接导致的结果是，由于其他中断被延迟响应，系统性能下降。
三、linux的进程调度策略
策略决定调度程序在何时让什么进程运行。调度器的策略往往就决定系统的整体印象，并且还要负责优化使用处理器时间。
2.1 Linux进程调度分为三种策略
Linux进程调度分为三种策略
实时进程的调度策略是SCHED_FIFO和SCHED_RR，普通的，非实时进程的调度策略（分时调度策略）是SCHED_NORMAL（SCHED_OTHER）。
Linux进程调度分为三种策略
（1）SCHED_OTHER，分时调度策略
（2）SCHED_FIFO，实时调度策略，先到先服务
（3）SCHED_RR，实时调度策略，时间片轮转
实时调度策略被实时调度器管理，普通调度策略被完全公平调度器来管理。实时进程的优先级要高于普通进程（nice越小优先级越高）。
实时调度策略就是在指定的时间执行，由调度程序来设定开始结束时间， 普通调度策略是由内核调度器自己设定的，所以人为设定的实时进程优先级要高于普通进程。
两种实时调度策略的区别
????SCHED_FIFO实现了一种简单的先入先出的调度算法，它不使用时间片，但支持抢占，只有优先级更高的SCHED_FIFO或者SCHED_RR进程才能抢占它，否则它会一直执行下去，低优先级的进程不能抢占它，直到它受阻塞或自己主动释放处理器。
????SCHED_RR是带有时间片的一种实时轮流调度算法，当SCHED_RR进程耗尽它的时间片时，同一优先级的其它实时进程被轮流调度，时间片只用来重新调用同一优先级的进程，低优先级的进程决不能抢占SCHED_RR任务，即使它的时间片耗尽。SCHED_RR是带时间片的SCHED_FIFO。
2.2 Linux分时调度策略CFS
SCHED_NORMAL（SCHED_OTHER）是默认的Linux分时调度（time-sharing scheduling）策略，它是Linux线程默认的调度策略。
SCHED_OTHER策略的静态优先级总是为0，对于该策略列表上的线程，调度器是基于动态优先级（dynamic priority）来调度的，动态优先级是跟nice中相关(nice值可以由接口nice, setpriority,sched_setattr来设置)，该值会随着线程的运行时间而动态改变，以确保所有具有SCHED_OTHER策略的线程公平运行。在Linux上，nice值的范围是-20到+19，默认值为0；nice值越大则优先级越低，相比高nice值（低优先级）的进程，低nice值（高优先级）的进程可以获得更多的处理器时间。使用命令ps -el查看系统的进程列表，其中NI列就是进程对应的nice值；使用top命令，看到的NI列也是nice值。运行命令的时候可用nice –n xx cmd来调整cmd任务的nice值，xx的范围是-20~19之间。
CFS是一种可以说是近乎完美公平的调度。
我们先说一下时间片，时间片就是一个数值，表明进程在被抢占前所能持续运行的时间。
在传统的unix调度器中，时间片是依赖nice值来计算的，由于这种原因，绝对的nice值会引起4种不好的情况（看书籍p40），如两个进程，nice值分配是 0 和1，映射时间片为100ms和95ms，两者差距很小，但是如果nice分配是18和19，映射时间片为10ms和5ms，几乎2倍差距，显然这种调度是不公平的。
CFS采用的方法是对时间片分配方式进行根本性的重新设计（就调度器而言）：完全摒弃时间片而是分配给进程一个处理器使用比重。通过这种方式，CFS确保了进程调度中能有恒定的公平性。而将切换频率置于不断变动中。
nice值在CFS中被作为进程获得的处理器运行比的权重，而不是时间片：越高的nice值（越低的优先级）进程获得更低的处理器使用权重，这是相对默认nice值进程的进程而言的；相反，更低的nice值（越高的优先级）的进程获得更高的处理器使用权重。
然而，CFS并非一个完美的公平调度，在可运行任务近乎无限时，按道理他们各自所获得的处理器使用片都将趋向于0，但是CFS引入每个进程获得的时间片底线，这个底线称为最小颗粒，默认值是1ms，保证每个进程最少也能获得1ms的运行时间。
NICE值
是反应一个进程“优先级”状态的值
nice越小优先级越高
实时调度策略中的优先级将nice值对应时间片的长度。 而在CFS中，nice值只作为进程获取处理器运行比的权重，每个进程都有一个权重，nice优先级越高，权重越大，表示应该运行更长的时间。
NI and PRI
用ps -l命令可以查看以上字段，对他们都加以说明：
F 代表这个程序的旗标 (flag)， 4 代表使用者为 superuser；
S 代表这个程序的状态 (STAT)；
UID 代表执行者身份
PID 进程的ID号！底下的 PPID 则父进程的ID；
C CPU 使用的资源百分比
PRI指进程的执行优先权，其值越小越早被执行；
NI 这个进程的nice值，其表示进程可被执行的优先级的修正数值。
ADDR 这个是内核函数，指出该程序在内存的那个部分。如果是个执行的程序，一般就是『 - 』
SZ 使用掉的内存大小；
WCHAN 目前这个程序是否正在运作当中，若为 - 表示正在运作；
TTY 登入者的终端机位置；
TIME 使用掉的 CPU 时间。
CMD 所下达的指令名称
我们这里只对PRI和NI做详解，其他字段以后会说明。
先来解释PRI与NI是什么含义：
PRI：就是进程的优先级，其值越小，优先级越高
NI：即nice值。表示进程可被执行的优先级的修正数值
PRI(new)=PRI（old）+NI
PRI与NI不是一个概念，是两个不同的概念。
nice值的取值范围是：-20~19；一共40个级别。
这个值越小，表示进程”优先级”越高，而值越大“优先级”越低。
nice值不是 进程的优先级，PRI才是。但是nice可以影响PRI，即影响优先级
2.3 CFS调度类的实现
在linux中，大部分都是不同进程，所以它们大多数是CFS调度类。
CFS调度类的实现由4个组成部分：
- 时间记账
- 进程选择
- 调度器入口
- 睡眠和唤醒
2.3.1时间记账
所有的调度器都必须对进程运行时间进行记账
CFS不再有时间片的概念，但是它也必须维护每个进程运行的时间记账，因为它需要确保每个进程只在公平分配给它的处理器时间内运行。
CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还能运行多长时间
2.3.2 进程选择（确定下一个运行进程）
当CFS需要选择下一个运行进程时，他会挑选具有最小vruntime的进程。
即CFS调度算法的核心：选择具有最小vruntime的任务
CFS使用红黑树来组织可运行进程队列，并利用它来迅速找到最小vruntime值的进程。在linux中，红黑树称为rbtree，它时自平衡二叉搜索树，树节点储存数据，这些数据都对应一个键值。
CFS的进程选择算法可以总结为：运行rbtree树中最左边叶子节点所代表的那个进程
注意只有等待CPU的就绪态进程在这棵树上，睡眠进程和正在运行的进程都不在树上。
2.3.3 调度器入口
进程调度的主要入口点函数是schedule（），他会调用pick_next_task(),pick_nexttask()会以优先级为序，从高到低依次检查每一个调度类，并且从最高优先级的调度类中选择最高优先级的进程，pick_next_task()会返回指向下一个可运行进程的指针，没有的话返回NULL。
Pick_next_task()函数实现会调用pick_next_entity()，而该函数会调用__pick_next_entity()函数。
2.3.4 睡眠和唤醒
休眠（被阻塞）的进程处于一个特殊的不可执行状态，为了等待一些事件
休眠的一个常见的原因就是文件I/O
休眠内核的操作都相同：进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待序列，然后调用schedule（）选择和执行一个其他进程
唤醒过程：进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中
休眠两种状态：TASK_INTERRUPTIBLE（接收到信号会被唤醒）和TASK_UNINTERRUPTIBLE（忽略信号）
等待队列：等待队列是由等待某些事件发生的进程组成的简单链表，休眠通过等待队列进行处理，内核用wake_queue_head_t来表示等待队列。等待队列可以通过DECLARE_WAITQUEUE()静态创建，也可以由init_waitqueue_head()动态创建。
进程通过执行以下几个步骤将自己加入到一个等待队列中
1）调用宏DEFINE_WAIT()创建一个等待队列的选项。
2）调用add_wait_queue()把自己加入到队列中。
3）调用prepare_to_wait()方法将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。
4）如果状态被设置成TASK_INTERRUPTIBLE，则信号唤醒进程。
5）当进程被唤醒的时候，会再次检查条件是否为真，真则退出循环，否则再次调用schedule()并且一直重复这步动作。
6）当条件满足后，进程将自己设置为TASK_RUNNING并调用finish_wait()方法把自己移出等待序列。
唤醒操作通过函数wake_up()进行，它会唤醒指定的等待队列上的所有进程。它调用try_to_wake_up()，该函数负责将进程设置成TASK_RUNNING状态，调用enqueue_task()将此进程放入红黑树中，如果被唤醒的进程优先级比正在执行的进程优先级高，设置need_resched标志。通常哪段代码促成等待条件达成，它就负责随后调用wake_up()函数
四、抢占和上下文切换
4.1 抢占
所谓抢占，即抢占CPU资源
4.1.1 用户抢占
内核提供了一个need_resched标志来表明是否需要重新执行一次调度。
当一个优先级高的进程进入可执行状态时，try_to_wake_up()会设置这个标志。内核检查这个标志确认其被设置，调用schedule()来切换到一个新的进程。该标志对于内核来说是一个信息，表示有进程应当被运行了，要尽快调用调度程序。再返回用户空间以及从中断返回时，内核也会检查标志。
内核即将返回用户空间的时候，如果need_resched被设置，会导致schedule()被调用，此时就会发生用户抢占。在内核返回用户空间的时候，它知道自己是安全的，因为既然它可以继续去执行当前进程，那么它当然可以再去选择一个新的进程去执行。所以内核无论是从中断处理程序还是在系统调用后返回，都会检查need_resched标志。如果它被设置了，那么，内核就会选择一个其他（更合适的）进程投入运行。从中断处理程序或系统调用返回的代码都是跟体系结构相关的，在entry.S文件中通过汇编语言来实现。
简而言之，用户抢占在以下情况时发生：
从系统调用返回用户空间；
从中断处理程序返回用户空间；
4.1.2 内核抢占
与其他大部分的unix变体和其他大部分的操作系统不同，Linux完整地支持内核抢占。在不支持内核抢占的内核中，内核代码可以一直执行，到它完成为止。也就是说，调度程序没有办法在一个内核级的任务正在执行的时候重新调度–内核中的各任务是协作方式调度的，不具备抢占性。内核代码一直要执行到完成（返回用户空间）或明显的阻塞为止。在2.6版的内核中，内核引入了抢占；现在，只要重新调度是安全的，那么内核就可以在任何时间抢占正在执行的任务。
那么，什么时候重新调度才是安全的呢？只要没有持有锁，内核就可以进行抢占。 锁是非抢占区的域的标志。由于内核是支持SMP的，所以，如果没有持有锁，那么正在执行的代码就是可重新导入的，也就是可以抢占的。
只要重新调度是安全的，内核就可以在任何时间抢占正在执行的任务。
内核抢占会发生在：
1）中断处理程序正在执行，且返回内核空间之前
2）内核代码再一次具有可抢占性的时候。
3）如果内核中的任务显式地调用 schedule()
4）如果内核中的任务阻塞（这同样也会导致调用schedule()）
非抢占式和可抢占式内核
早期的Linux内核（2.5.4版本之前）是不可抢占的。
Linux内核（2.6版本）加入了内核抢占(preempt)机制
内核抢占（可抢占式内核）：即当进程位于内核空间时，有一个更高优先级的任务出现时，如果当前内核允许抢占，则可以将当前任务挂起，执行优先级更高的进程。
非抢占式内核：高优先级的进程不能中止正在内核中运行的低优先级的进程而抢占CPU运行。进程一旦处于核心态（例如用户进程执行系统调用），则除非进程自愿放弃CPU，否则该进程将一直运行下去，直至完成或退出内核
?
?
进程管理与调度可参考优秀专栏：https://blog.csdn.net/gatieme/category_6225543.html