第四章 进程调度
进程调度程序（常常简称调度程序）可看做在可运行态进程之间分配有限的处理器时间资源的内核子系统。只有通过调度程序的合理调度，系统资源才能最大限度地发挥作用，多进程才会有并发执行的数果。调度程序没有太复杂的原理。最大限度地利用处理器时间的原则是，只要有可以执行的进程，那么就总会有进程正在执行。
4.1 多任务
①多任务操作系统就是能同时并发地交互执行多个进程的操作系统。多任务系统可以划分为两类：非抢占式多任务和抢占式多任务。。在此模式下，由调度程序来决定什么时候停止一个进程的运行，以便其他进程能够得到执行机会．这个强制的挂起动作就叫做抢占。进程在被抢占之前能够运行的时间是预先设置好的，而且有一个专门的名字，叫进程的时间片。时间片实际上就是分配给每个可运行进程的处理器时间段。
②在非抢占式多任务模式下，除非进程自己主动停止运行，否则它会一直执行。进程主动挂起自己的操作称为让步。但这种机制有很多缺点：调度程序无诠对每个进程该执行多长时间做出统一规定，所以进程独占的处理器时间可能超出用户的预料。
4.2 Linux 的进程调度
调度程序做了大手术，开始采用了一种叫做0(1）调度程序的新调度程序。0(1）调度器虽然在拥有数以十计（不是数以百计）的多处理器的环境下尚能表现出近乎完美的性能和可扩展性，但是时间证明该调度算提对于调度那些响应时间敏感的程序却有一些先天不足。
4.3 策略
策略决定调度程序在何时让什么进程运行。调度器的策略往往就决定系统的整体印象，并且，还要负责优化使用处理器时间。
4.3.1 I/O 消耗型和处理器消耗型的进程
①进程可以被分为I/O 消耗型和处理器消耗型。前者指进程的大部分时间用来提交I/O请求或是等待I/O请求。这样的进程经常处于可运行状态，但通常都是运行短短的一会儿，它在等待更多的I/O请求时最后总会阻塞。处理器消费型进程把时间大多用在执行代码上。除非被抢占，否则它们通常都一直不停地运行，因为它们没有太多的I/O 需求。处理器消耗型进程的极端例子就是无限循环地执行。
②X Window 服务器既是I/O 消耗型，也是处理器消耗型。还有些进程可以是I/O 消耗型，但属于处理器消耗型活动的范围。其典型的例子就是字处理器。
③调度策略通常要在两个矛盾的目标中间寻找平衡：进程响应迅速（响应时间短）和最大系统利用率（高吞吐量）。为了满足上述需求，调度程序通常采用一套非常复杂的算撞来决定最值得运行的进程投入运行，但是它往往并不保证低优先级进程会被公平对待。
4.3.2 进程优先级
①调度算站中最基本的一类就是基于优先级的调度。常是（其并未被Linux 系统完全采用）优先级高的进程先运行，低的后运行，相同优先级的进程按轮转方式进行调度（一个接一个，重复进行）。
②Linux 采用了两种不同的优先级范围。第一种是用nice 值，色的范围是从－20 到＋19，默认值为0 ：越大的nice 值意味着更低的优先级一－nice 似乎意味着你对系统中的其他进程更“优待”。。相比高nice 值（低优先级）的进程，低nice 值（高优先级〉的进程可以获得更多的处理器时间。nice 值则代表时间片的比例，可以通过ps-el 命令查看。
③第二种范围是实时优先级，其值是可配置的，默认情况下它的变化范围是从0 到99 （包括0和99 ）。越高的实时优先级数值意味着进程优先级越高。你可以通过命令：
ps-eo state , uid,pi d,ppid,rtpri o,time,comm.查看到你系统中的进程列衰，以及它们对应的实时优先级。其中如果有进
程对应列显示“-”，则说明它不是实时进程。
4.3.3 时间片
时间片是一个数值，它表明进程在被抢占前所能持续运行的时间。任何长时间片都将导致系统交互表现欠佳。Linux 的CFS 调度器并没有直接分配时
间片到进程，它是将处理器的使用比划分给了进程。nice 值作为权重将调整进程所使用的处理器时间使用比。具有更高nice 值（更低优先权）的进程将被赋予低权重，从而丧失一小部分的处理器使用比：而具有更小nice 值（更高优先级）的进程则会被赋予高权重，从而抢得更多的处理器使用比。
4.3.4 调度策略的活动
Linux 操作系统同样需要追求上述目标，但是它采用不同方法。它不再通过给分配给定的优先级和时间片，而是分配一个给定的处理器使用比。我们首要目标是确保其能在用户输入发生时立刻运行。
4.4 Linux 调度算法
4.4.1 调度器类
①Linux 调度器是以模块方式提供的，这样做的目的是允许不同类型的进程可以有针对性地选择调度算。这种模块化结构被称为调度器类，它允许多种不同的可动态添加的调度算法并存，调度属于自己范畴的进程。。每个调度器都有一个优先级，基础的调度器代码定义在kemel/scbed.c 文件中，它会按照优先级顺序遍历调度类，拥有一个可执行进程的最高优先级的调度器类胜出，去选择下面要执行的那一个程序。
②完全公平调度（CFS）是一个针对普通进程的调度类，在Linux 中称为SCHED_NORMAL（在POSIX 中称为SCHED_OTHER) , CFS算法实现定义在文件kemel/scbed_ fair.c中。
4.4.2 Unix 系统中的进程调度
①现代进程调度器有两个通用的概念：进程优先级和时间片。时间片是指进程运行多少时间，进程一旦启动就会有一个默认时间片。具有更高优先级的进程将运行得更频繁，而且（在多数系统上）也会被赋予更多的时间片。
②CFS 采用的方越是对时间片分配方式进行根本性的重新设计（就进程调度
器而吉）：完全摒弃时间片而是分配给进程一个处理器使用比重。通过这种方式， CFS 确保了进程调度中能有恒定的公平性，而将切换频率置于不断变动中。
4.4.3 公平调度
①CFS 的出发点基于一个简单的理念：进程调度的效果应如同系统具备一个理想中的完美多任务处理器。每个进程将能获得l/n 的处理器时间一n 是指可运行进程的数量。我们无能在一个处理器上真的同时运行多个进程。因为调度时进程抢占会带来一定的代价：
将一个进程换出，另一个换入本身有消耗，同时还会影响到缓存的效率②CFS 的做怯是允许每个进程运行一段时间、循环轮转、选择运行最少的进
程作为下一个运行进程，而不再采用分配给每个进程时间片的做法了， CFS 在所有可运行进程总数基础上计算出一个进程应该运行多久，而不是依靠nice 值来计算时间片。
越高的nice 值（越低的优先级）进程在得更低的处理器使用权重，这是相对默认nice 值进程的进程而言的：相反， 更低的nice 值（越高的优先级）的进程获得更高的处理器使用权重。③当可运行任务数量趋于无限时，它们各自所获得的处理器使用比和时间片都将趋于0。这样无疑造成了不可接受的切换消耗. CFS 为此引人每个进程获得的时间片底线，这个底线称为最小粒度。默认情况下这个值是lms.
④任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice 值的相对差值决定的。nice 值对时间片的作用不再是算数加权，而是几何权。任何回回值对应的绝对时间不再是一个绝对值，而是处理器的使用比。CFS 称为公平调度器是因为它确保给每个进程公平的处理器使用比。
4.5 Linux 调度的实现
4 .5.1 时间记账
所有的调度器都必须对进程运行时间做记账。多数Unix系统，正如我们前面所说，分配一个时间片给每一个进程。那么当每次系统时钟节拍发生时，时间片都会被减少一个节拍周期。当一个进程的时间片被减少到0 时，它就会被另一个尚未减到0的时间片可运行进程抢占。
l. 调度嚣实体结构
CFS 不再有时间片的概念，但是它也必须维护每个进程运行的时间记账，因为它需要确保每个进程只在公平分配给它的处理器时间内运行。CFS 使用调度器实体结构（定义在文件＜linux/sched.h＞的struct_sched _entity 中）来追踪进程运行记账：
2. 虚拟实时
vruntime 变量存放进程的虚拟运行时间，该运行时间（花在运行上的时间和）的计算是经过了所有可运行进程总数的标准化（或者说是被加权的）。虚拟时间是以因为单位的，所以vruntime 和定时器节拍不再相关。定义在kemeVsched_fair.c 文件中的update_curr(）函数实现了该记账功能：
update_ curr（）计算了当前进程的执行时间，并且将其存放在变量delta_exec 中。然后它又将运行时间传递给了一update_curr（），由后者再根据当前可运行进程总数对运行时间进行加权计算。最终将上述的权重值与当前运行进程的vruntime 相加。
update_ curr（）是囱系统定时器周期性调用的，无论是在进程处于可运行态，还是被堵塞处于不可运行态。
4.5.2 进程选择
是CFS 调度的核心：选择具有最小vruntime的任务。
l. 挑选下一个任务
CFS 调度器选取待运行的下一个进程，是所有进程中vruntime 最小的那个，它对应的便是在树中最左侧的叶子节点。也就是说，你从树的根节点沿着左边的子节点向下找，一直找到叶子节点，你便找到了其vruntime 值最小的那个进程。
实现这一过程的函数是_pick_next_ entityQ，它定义在文件kemelsched＿中
static struct sched_entity *__pick_next_entity(struct cfs_rq *cf s_rq)
{
struct rb_node *left = cfs_rq- >rb_leftmost;
if ( !left)
return NULL;
return r b_entry(left, struct sched_entity, run_n。de );
}2. 向树中加入进程
①CFS 如何将进程加入rbtree 中，以及如何缓存最左叶子节点。这一切发生在进程变为可运行状态（被唤醒)或者是通过fork（）调用第一次创建进程时.
②while（） 循环中遍历树以寻找合适的匹配键值，该值就是被插入进程的vruntime. 平衡二叉树的基本规则是，如果键值小于当前节点的键值，则需转向树的左分支：相反如果大于当前节点的键值，则转向右分支。如果一旦走过右边分支，哪怕一次，也说明插入的进程不会是新的最左节点，因此可以设置le加ost 为0。如果一直都是向左移动，那么leftmost 维持1，这说明我们有一个新的最左节点，并且可以更新缓存一一设置rb_leftmost 指向被插入的进程。
③当我们沿着一个方向和一个没有子节的节点比较后： link 如果这时是NULL，循环随之终止。当退出循环后，接着在父节点上调用rb_link_ node()，以使得新插入的进程成为其子节点。最后函数rb_insert_color() 更新树的自平衡相关属性。
3. 从树中则除进程
从红黑树中删除进程要容易得多。因为rbtree 实现了rb_erase（）函数，它可完成所有工作。该函数的剩下工作是更新rb_leftmost 缓存。如果要删除的进程是最左节点，那么主函数要调用rb_next（）按顺序遍历，找到谁是下一个节点，也就是当前最左节点被删除后，新的最左节点。
4.5.3 调度器入口
进程调度的主要入口点是函数schedule（），它定义在文件kemel/sched .c 中。它正是内核其他部分用子调用进程调度器的入口：选择哪个进程可以运行，何时将其投入运行。Schedule（）通常都需要和一个具的调度类相关联，也就是说，它会找到一个最高优先级的调度类一一后者需
要有自己的可运行队列，然后问后者谁才是下一个该运行的进程。
它会调用pick_next_task() （也定义在文件kernel/sched.c 中）.pick_next_task（）会以优先级为序，从高到低，依次检查每一个调度类，并且从最高优先级的调度类中，选择最高优先级的进程：
该函数的核心是for（）循环，它以优先级为序，从最高的优先级类开始，遍历了每一个调度类。每一个调度类都实现了pick_next_tas均函数，它会返回指向下一个可运行进程的指针，没有时返回NULL。
4.5.4 睡眠和唤醒
①休眠（被阻塞）的进程处于一个特殊的不可执行状态。事件可能是一段时间从文件I/O读更多数据，或者是某个硬件事件。进程把自己标记成休眠状态，从可执行红黑树中移出，放入等待队列，然后调用schedule（）选择和执行一个其他进程。唤醒的过程刚好相反t 进程被设置为可执行状态，然后再从等待队列中移到可执行红黑树中。
②休眠有两种相关的进程状态： TASK_INTERRUPTIBLE 和TASK_UN INTERRUPTIBLE。它们的唯一区别是处于TASK_UNINTERRUPTIBLE 的进程会忽略信号，而处于TASK_INTERRUPTIBLE 状态的进程如果接收到一个信号，会被提前唤醒。
1. 等待队列
进程通过执行下面几个步骤将自己加入到一个等待队列中：
1 ）调用宏DEFINE_WAIT（）创建一个等待队列的项。
2 ）调用add_waiT_ queue（）把自己加入到队列中。该队列会在进程等待的条件摘足时唤醒它。当然我们必须在其他地方撰写相关代码，在事件发生时，对等待队列执行wake_up）操作。
3 ）调用prepare_to_ wait（）方站将进程的状态变更为TASK＿剧TERRUPTIBLE 或TASK_UNINTERRUPTIBLE。而且该函数如果有必要的话会将进程加回到等待队列，这是在接下来的循环遍历中所需要的。
4 ）如果状态被设置为TASK_INTERRUPTIBLE ，贝I］信号唤醒进程。这就是所谓的伪唤醒〈唤醒不是因为事件的发生），因此检查并处理倍号。
5 ）当进程被唤醒的时候，它会再次检查条件是否为真。如果是，它就退出循环：如果不是，它再次调用schedule（）井一直重复这步操作。
6）当条件满足后，进程将自己设置为TASK_RUNNING 并调用finish_wait（）方挫把自己移出等待队列。2. 唤醒
唤醒操作通过函数wake_up()进行，它会唤醒指定的等待队列上的所有进程。它调用函数try_to_wake_upO，该函数负责将进程设置为TASK_RUNNING 状态，调用enqueue_task（）将此进程放入红黑树中，如果被唤醒的进程优先级比当前正在执行的进程的优先级高，还要设置need _resched 标志。关于休眠有一点需要注意，存在虚假的唤醒．有时候进程被唤醒并不是因为它所等待的条件达成了才需要用一个循环处理来保证它等待的条件 真正达成。
4.6 抢占和上下文切换
上下文切换，也就是从一个可执行进程切换到另一个可执行进程，由定义在kernel/ sched.c 中的context_switch（）函数负责处理．每当一个新的进程被选出来准备投入运行的时候，schedule()就会调用该函数。它完成了两项基本的工作：
1.调用声明在＜asm/mmu_ context.h＞中的switch_mm(), 该函数负责把虚拟内存从上一个进程映射切换到新进程中。
2.调用声明在<asm/system.h> 中的switch_to()，该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。这包括保存、恢复检信息和寄存器信息，还有其他任何与体系结构相关的状态信息，都必须以每个进程为对象进行管理和保存。
内核提供了一个need_resched 标志来表明是否需要重新执行一次调度。当某个进程应该被抢占时， scheduler_tick（）就会设置这个标志：当一个优先级高的进程进入可执行状态的时候，try＿to_wake_ up（）也会设置这个标志，内核检查该标志，确认其被设置，调用schedule（）来切换到一个新的进程。
再返回用户空间以及从中断返回的时候，内核也会检查need_resched 标志．如果已被设置，内核会在继续执行之前调用调度程序。
4.6.1 用户抢占
内核即将返回用户空间的时候，如果need_resched 标志被设置，会导致schedule()被调用，此时就会发生用户抢占.简而言之，用户抢占在以下情况时产生:
．从系统调返回用户空间时．
·从中断处理程序返回用户空间时。4.6.2 内核抢占
①Linux 完整地支持内核抢占。在不支持内核抢占的内核中，内核代码可以一直执行，到它完成为止。为了支持内核抢占所傲的第一处变动，就是为每个进程的也read_info 引人preempt_count 计数器。该计数器韧始值为0，每当使用锁的时候数值加1，释放锁的时候数值减1。当数值为0的时候，内核就可执行抢占。
②如果内核中的进程被阻塞了，或它显式地调用了schedule（），内核抢占也会显式地发生.这种形式的内核抢占从来都是受支持的，因为根本无须额外的逻辑来保证内核可以安全地被抢占。
③内核抢占会发生在:
·中断处理程序正在执行，且返回内核空间之前．
·内核代码再一次具有可抢占性的时候。
·如果内核中的任务显式地调用schedule()
·如果内核中的任务阻塞（这同样也会导敖调用schedule()）。4.7 实时调度策略
①Linux 提供了两种实时调度策略： SCHED_FIFO 和SCHED_RR。而普通的、非实时的调度策略是SCHED二NORMAL， 借助调度类的框架，这些实时策略并不被完全公平调度器来管理，而是被一个特殊的实时调度器管理。具体的实现定义在文件kemel/sched_rt.c. 中。
②SCHED_FIFO 实现了一种简单的、先入先出的调度算怯：它不使用时间片．处于可运行状态的SCHED_FIFO 级的进程会比任何SCHED_NORMAL 级的进程都先得到调度。SCHED_RR与SCHED_FIFO 大体相同，只是SCHED_RR 级的进程在耗尽事先分配给它的时间后就不能再继续执行了．也就是说， SC阻止RR 是带有时闹片的SCHED_FIFO-这是一种实时轮流调度算挂。
③这两种实时算桂实现的都是静态优先级。内核不为实时进程计算动态优先级．这能保证给定优先级别的实时进程总能抢占优先级比它低的进程。
④实时优先级范围从0 到MAX_RT_PRIO 减1. 默认情况下， MAX_RT_P0 为100--所以默认的实时优先级范围是从0 到99. SCHED _NORMAL 级进程的nice 值共享了这个取值空间：它的取值范围是从MAX_RT_PRIO 到＜MAX_RT_PRIO + 40）.也就是说，在默认情况下， nice值从-20 到＋ 19 直接对应的是从100 到139 的实时优先级范围.
4.8 与调度相关的系统调用
4.8.1 与调度策略和优先组相关的系统调用
sched _ setscheduler（） 和sched_getscheduler(）分别用于设置和获取进程的调度策略和实时优级。sched setparam（）和sched__getparam（）分别用于设置和获取进程的实时优先级。这两个系统调用族取封装在sched_param 特殊结构体的rt_priority 中。对于一个普通的进程， nice(）函数可以将给定进程的静态优先级增加一个给定的量。只有超级用户才能在调用它时使用负值，从而提高进程的优先级。
4.8.2 与处理器绑定有关的系统调用
①Linux 调度程序提供强制的处理器绑定机制。用户可以通过sched _ setaffinity（）设置不同的一个或几个位组合的位掩码，而调用scbed_ getaffinity（）则返回当前的us_allowed 位掩码。
②内核提供的强制处理器绑定的方法很简单：
首先，当处理进行第一次创建时，它继承了其父进程的相关掩码。由于父进程运行在指定处理器上， 子进程也运行在相应处理器上。
其次，当处理器绑定关系改变时，内核会采用“移植钱程”把任务推到合曲的处理器上。
最后，加载平衡器只把任务拉到允许的处理器上。4.8.3 放弃处理器时间
Linux 通过sched_yield（） 系统调用，提供了一种让进程显式地将处理器时间让给其他等待执行进程的机制。它是通过将进程从活动队列中（ 因为进程正在执行，所以它肯定位于此队列当中）移到过期队列中实现的。内核代码为了方便，可以直接调用yield（），先要确定给定进程确实处于可执行状态，然后再调用sched__yield() 。 用户空间的应用程序直接使用sched__yield（）系统调用就可以了。