第四章 进程调度
注：作者：臧文君，原创作品转载请注明出处。
一、多任务
1、多任务操作系统：就是能同时并发地交互执行多个进程的操作系统。能使多个进程处于堵塞或者睡眠状态。
2、多任务系统可以划分为两个：非抢占式多任务和抢占式多任务。
3、抢占：强制的挂起。
进程的时间片：指进程在被抢占之前能够运行的时间。
让步：进程主动挂起自己的操作。
二、Linux的进程调度
1、O(1)调度程序：对于调度那些响应时间敏感的程序---交互进程存在不足。
2、RSDL反转楼梯最后期限调度算法。
3、CFS完全公平调度算法。
三、策略
1、进程分为：I/O消耗型和处理器消耗型。
（1）I/O消耗型：指进程的大部分时间用来提交I/O请求或是等待I/O请求。
I/O：指任何类型的可阻塞资源，如键盘输入、网络I/O、文字编辑程序。
（2）处理器消耗型：指进程把时间大多用在执行代码上，除非被抢占，否则它们通常都一直不停地运行。
例：执行数学计算的程序，视频编码程序。
（3）进程可以同时展示这两种行为：X Windows服务器。
（4）调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）。
2、进程优先级
（1）调度算法中最基本的一类就是基于优先级的调度。
调度程序总是选择时间片未用尽而且优先级最高的进程运行。
（2）Linux采用了两种不用的优先级范围：nice值和实时优先级。
nice值：范围-20~+19，默认值为0。越大的nice值意味着更低的优先级。
Linux系统中，nice值代表时间片的比例。
实时优先级：0~99，越高的实时优先级数值意味着进程优先级越高。
3、时间片
（1）I/O消耗型和处理器消耗型的进程之间的矛盾：
I/O消耗型不需要长的时间片，二处理器消耗型的进程则希望越长越好。
（2）Linux的CFS调度器将处理器的使用比划分给了进程，进程所获得的处理器时间其实是和系统负载密切相关的。
（3）Linux系统时抢占式的，在Linux中使用新的CFS调度器，其抢占时机取决于新的可运行程序消耗了多少处理器使用比。
四、Linux调度算法
1、调度器类
Linux调度器是以模块方式提供的，目的是允许不同类型的进程可以有针对性地选择调度算法，这种模块化的结构被称为调度器类。
2、完全公平调度CFS
是一个针对普通进程的调度类，在Linux中称为SCHED_NORMAL，CFS算法实现定义在文件kernel/sched_fair.c中。
3、Unix系统中的进程调度
CFS采用的方法是：完全摒弃时间片而是分配给进程一个处理器使用比重。
4、公平调度
（1）调度时进程抢占会带来一定的代价：本身有消耗，同时还会影响到缓存的效率。
（2）CFS的做法：允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程。
nice指在CFS中被作为进程获得的处理器运行比的权值：
5、任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。
五、Linux调度的实现
1、CFS是如何实现的：关注时间记账，进程选择，调度器入口，睡眠和唤醒四个部分。
2、时间记账
（1）CFS使用调度器实体结构来追踪进程运行记账，调度器实体结构作为一个名为se的成员变量，嵌入在进程描述符struct task_struct内。
（2）vruntime变量存放进程的虚拟运行时间，以ns为单位，和定时器节拍不再相关。
CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。
3、进程选择
（1）CFS调度算法的核心：选择具有最小vruntime的任务。
（2）CFS使用红黑树来组织可运行进程队列，并利用其迅速找到最小vruntime值的进程。
红黑树是一个自平衡二叉搜索树，是一种以树节点形式存储的数据；从树的根结点沿着左边的子节点向下找，一直找到叶子节点，你便找到了其vruntime值最小的那个进程。
（3）CFS的进程选择算法可简单总结为“运行rbtree树中最左边叶子节点所代表的那个进程”。实现这一过程的函数是_pick_next_entity()，它定义在文件kernel/sched_fair.c中。
（4）将进程加入rbtree中以及缓存最左叶子节点：发生在进程变为可运行状态（被唤醒）或者是通过fork()调用第一次创建进程时，enqueue_entity()函数实现了这一目的。
（5）删除动作发生在进程堵塞（变为不可运行态）或者终止时（结束运行），实际工作是由辅助函数_dequeue_entity()完成的。
4、进程调度的主要入口点是函数schedule()，它定义在文件kernel/sched.c中。该函数调用pick_next_task()。
5、休眠（被阻塞）的进程处于一个特殊的不可执行状态。
六、抢占和上下文切换
1、上下文切换，是从一个可执行进程切换到另一个可执行进程，由定义在kernel/sched.c中的context_switch()函数负责处理。每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用该函数。
2、内核提供了一个need_resched标志来表明是否需要重新执行一次调度。
3、用户抢占：内核即将返回用户空间的时候，如果need_resched标志被设置，会导致schedule()被调用，此时就会发生用户抢占。
用户抢占在以下情况时产生：
从系统调用返回用户空间时；从中断处理程序返回用户空间时。
4、锁是非抢占区域的标志，只要没有持有锁，内核就可以进行抢占。
每个进程的thread_info引人preempt_count计数器。该计数器韧始值为0，每当使用锁的时候数值加1，释放锁的时候数值减1。当数值为0的时候，内核就可执行抢占。
内核抢占发生在：
·中断处理程序正在执行，且返回内核空间之前；
·内核代码再一次具有可抢占性的时候；
·如果内核中的任务显式地调用schedule()；
·如果内核中的任务阻塞（这同样也会导敖调用schedule()）。
七、实时调度策略
1、Linux 提供了两种实时调度策略：SCHED_FIF0和SCHED_RR。而普通的、非实时的调度策略是SCHED_NORMAL。
2、SCHED_FIFO实现了一种简单的、先入先出的调度算法：它不使用时间片。
SCHED_RR是带有时间片的SCHED_FIFO---这是一种实时轮流调度算法。
3、对于SCHED_FIFO进程，高优先级总是立即抢占低优先级，但低优先级进程决不能抢占SCHED_RR 任务，即使它的时间片耗尽。
这两种实时算法实现的都是静态优先级。
4、Linux的实时调度算法提供了一种软实时工作方式。软实时的含义是，内核调度进程，尽力使进程在它的限定时间到来前运行，但内核不保证总能满足这些进程的要求。相反，硬实时系统保证在一定条件下，可以满足任何调度的要求。
八、与调度相关的系统调用
1、Linux 提供了一个系统调用族，用于管理与调度程序相关的参数。这些系统调用可以用来操作和处理进程优先级、调度策略及处理器绑定，同时还提供了显式地将处理器交给其他进程的机制。
2、sched_setscheduler()和sched_getscheduler()分别用于设置和获取进程的调度策略和实时优先级。
sched_setparam()和sched_getparam()分别用于设置和获取进程的实时优先级。
sched_get_priority_max()和sched_get_priority_min()分别用于返回给定调度策略的最大和最小优先级。
3、实时调度策略的最大优先级是MAX_ USER_RT_PRIO减1，最小优先级等于1。
4、Linux调度程序提供强制的处理器绑定（processor affinity）机制。
这种强制的亲和性保存在进程task_struct的cpus_allowed 这个位掩码标志中。
5、Linux通过sched_yield()系统调用，提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制。
6、内核代码为了方便，可以直接调用yield()，先要确定给定进程确实处于可执行状态，然后再调用sched_yield()。
用户空间的应用程序直接使用sched_yield()系统调用就可以了。