第四章 进程调度
序
进程在操作系统看来是程序的运行态的表现形式。
4.1多任务
多任务操作系统：同时并发地交互执行多个进程的操作系统
多任务操作系统会使多个进程处于堵塞或者睡眠状态。这些任务尽管位于内存，但是并不处于可运行状态。这些进程利用内核堵塞自己，直到某一事件发生。
多任务系统可以划分为两类：非抢占式和抢占式。
抢占：强制挂起。
时间片：分配给每个可运行进程的处理器时间段。
4.2 linux的进程调度
O（1）调度程序
4.3策略
策略决定调度程序在何时让什么程序运行。
4.3.1 I/O消耗型和处理器消耗型的进程
I/O消耗型：进程的大部分时间用来提交I/O请求或是等待I/O请求。这样的进程经常处于可运行状态，但通常都是运行短短一会儿，因为它在等待更多的I/O请求时总会阻塞。
处理器消耗型：把时间大多用在执行代码上。除非被抢占，否则他们一般都在一直不停地运行。对待他们的调度策略通常是尽量降低他们的调度频率，而延长其运行时间。
调度策略的要求：1、响应时间短 2、高吞吐量
4.3.3 进程优先级
思想：根据进程的价值和其对处理器时间的需求来对进程分级
调度程序总是选择时间片未用尽而且优先级最高的进程运行。
Linux采用了两种不同 的优先级范围：
1、nice值：范围-20~+19，默认值为0；越大的nice值意味着更低的优先级。高优先级的进程可以获得更多的处理器时间。
2、实时优先级：值可配置，默认情况下的变化范围是0~99.越高的实时优先级数值意味着进程优先级越高。任何实时进程的优先级都高于普通的进程。参考了UNIX相关
标准：POSIX.1b。
实时优先级和nice优先级处于互不相交的两个范畴。
4.3.3时间片
时间片过长会导致系统对交互的响应表现欠佳，太短会明显增大进程切换带来的处理器耗时。
进程所获得的处理器时间与系统负载nice值有关。
4.4linux调度算法
4.4.1调度器类
Linux调度器是以模块方式提供的，这样可以允许不同类型的进程可以有针对性地选择调度算法。这种模块化的结构称为调度器类。
每个调度器都有一个优先级，基础的调度器代码定义在kernel/sched.c文件中，它会按照优先级顺序来遍历调度器，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的一个程序。
完全公平调度（CFS）：针对普通进程的调度类，在linux中称为SCHED_NORMAL，CFS算法定义在文件kernel/sched_fair.c中。
4.4.2 unix进程中的进程调度
存在以下几方面的问题：
1、若要将nice值映射到时间片，就必然需要将nice单位值对应到处理器的绝对时间，但这样做就会导致进程切换无法最优化进行。
2、把进程的nice值减小1所带来的效果极大地取决于其nice 的初始值。
3、如果执行nice 值到时间片的映射，时间片必须是定时器节拍的整数倍，系统定时器限制了两个时间片的差异。
4、基于优先级的调度器为了优化交互任务而唤醒相关进程，为了进程能够尽快的投入运行，而去对新要唤醒的进程提升优先级，即使他们的时间片已经用尽，使得给定进程打破公平原则，获得更多处理器时间，损害系统中其他进程的利益。
CFS的改进：
完全摒弃时间片而是分配给进程一个处理器使用比重。
4.4.3公平调度
我们希望进程只运行一个非常短的周期，CFS实现时首先确保系统性能不受损失。
CFS的做法：允许每个进程运行一段时间、循环轮转、选择运行最少的进程作为下一个运行进程，而不再采用分配给每个进程时间片的做法。Nice值在CFS中被作为进程获得的处理器运行比的权重：越高的nice 值进程获得更低的处理器使用权重。
如何计算准确的时间片？
CFS为完美多任务中的无限小调度周期的近似值设立了“目标延迟”，越小的调度周期将带来越好的交互性，同时也更接近完美的多任务。CFS引入每个进程获得的时间片 底线—最小粒度。默认情况下这个值是1ms。即便是可运行进程数量趋于无穷，每个最少也能获得1ms的运行时间，确保切换消耗被限制在一定范围内。
总结：任何进程获得的处理器时间是由它自己和其他所有可运行进程nice值的相对差值决定的。Nice值对时间片的作用是几何加权，任何nice值对应的绝对时间不再是一个绝对值，而是处理器的使用比。
4.5 linux调度的实现
4.5.1时间记账
当每次系统时钟节拍发生时，时间片都会被减少一个节拍周期。当一个进程的时间片被减少到0的时候，它就会被另一个尚未减到0的时间片可运行进程抢占。
1.调度器实体结构：用来追踪进程运行记账
调度器实体结构作为一个名为se的成员变量，嵌入在进程描述符struct task_struct内。
2.虚拟实时
Vruntime变量存放进程的虚拟运行时间，该运行时间的计算是经过了所有可运行进程总数的标准化。虚拟时间以ns为单位，所以和定时器街拍不再相关。CFS使用vruntime变量来记录一个程序到底运行了多长时间以及它还应该再运行多久。
Update_curr()计算了当前进程的执行时间，并且将其存放在变量delta_exec中。然后他把运行时间传递给__update_curr()，由后者再根据当前可运行进程总数对运 行时间进行加权计算，最终将上述的权值与当前运行进程的vruntime相加。
Update_curr()由系统计数器周期性调用。
4.5.2进程选择
CFS调度算法的核心：选择具有最小vruntime值得进程。
CFS使用红黑树来组织可运行进程队列，并利用其迅速找到最小vruntime值得进程。
1.挑选下一个任务
CFS的进程选择算法可总结为“运行rbtree树中最左边叶子节点所代表的那个进程。”实现这一过程的函数是__pick_next_entity()。
2.向树中加入进程
发生在进程变为可运行状态（被唤醒）或者通过fork（）调用第一次创建进程时。enqueue_entity()函数实现了这一目的。
该函数更新运行时间和其他一些统计数据，然后调用__enqueue_entity()进行繁重的插入操作，把数据项真正插入到红黑色树中。
3.从树中删除进程
删除动作发生在进程堵塞或者终止时。
4.5.3调度器入口
进程调度的主要入口点是函数schedule()，它是内核其他部分用于调用进程调度器的入口：选择哪个进程可以运行，何时将其投入运行。该函数中唯一重要的是调用pick_next_task()，该函数会以优先级为序，从高到低，一次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程。该函数的核心是for（）循环，实现了遍历。
4.5.4睡眠和唤醒
休眠：进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule（）选择和执行一个其他进程。
唤醒：进程被置为可执行状态，然后在从等待队列中移到可执行红黑树中。
休眠有两种相关的进程状态：TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。他们唯一的区别是TASK_UNINTERRUPTIBLE的进程会忽略信号，而TASK_INTERRUPTIBLE状态的进程如果接收到一个信号，会被提前唤醒并响应该信号。两种状态的信号位于同一等待队列上，等待某些事件，不能够运行。
1.等待队列
进程通过下面几个步骤把自己加入一个等待队列：
2.唤醒
通过函数wake_up()进行，它会唤醒指定的等待队列上的所有进程。它调用函数try_to_wake_up()，该函数负责将进程设置为TASK_RUNNING状态，调用enqueue_task()将此进程放入红黑树中，如果被唤醒的进程优先级比当前就正在执行的进程优先级高，还要设置need_resched标志。
4.6抢占和上下文切换
由定义在kernel/sched.c中的context_switch()函数负责处理。当一个新的进程被选出来准备投入运行的时候，schedule（）就会调用该函数。它完成了下面两项基本工作：
调用声明在<asm/mmu_contesxt.h>中的switch_mm()，该函数负责把虚拟内存从上一个进程映射切换到新进程中。
调用声明在<asm/system.h>中的switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。
4.6.1用户抢占
发生在：
从系统调用返回用户空间时。
从中断处理程序返回用户空间时。
4.6.2内核抢占
只要没有持有锁，内核就可以发生抢占。
发生在：
中断处理程序正在执行，且返回内核空间之前。
内核代码再一次具有可抢占性的时候。
如果内核空间中的任务显式地调用schedule（）。
如果内核中的任务阻塞。（也会调用schedule（））。
4.7实时调度策略
Linux提供了两种实时调度策略：SCHED_FIFO和SCHED_RR。
SCHED_FIFO：先入先出算法。
SCHED_RR：带有时间片的先入先出算法。
4.8与调度相关的系统调用
