进程调度
进程调度
调度程序负责决定将哪个进程投入运行,何时运行以及运行多长时间。进程调度程序可看作在可运行态进程之间分配有限的处理器时间资源的内核子系统。调度程序是像linux这样的多任务操作系统的基础。只有通过调度程序的合理调度,系统资源才能最大限度地发挥作用,多进程才会有并发执行的效果。
多任务
多任务操作系统就是能同时并发地交互执行多个进程地操作系统。在单处理器机器上,这会造成多个进程同时运行地幻觉。在多处理器机器上,这会使多个进程在不同地处理机上真正同时、并行地运行。多任务操作系统能使多个进程处于阻塞或者睡眠状态,也就是说,实际不被投入运行,直到工作就绪。
多任务系统可以划分为两类:非抢占式多任务和抢占式多任务。linux提供了抢占式地多任务模式。在此模式下,由调度程序来决定什么时候停止一个进程地运行,以便其他进程能够得到执行机会。这个强制地挂起动作就是抢占(preemption)。进程在被抢占之前能够运行地时间是预先设置好的,叫进程地时间片(timeslice),也就是分配给每个可运行进程的处理时间段。有效管理时间片能使调度程序从系统全局的角度做出调度决定,避免个别线程独占系统资源。
在非抢占式多任务模式下,除非进程自己主动停止运行,否则它会一直运行。进程主动挂起自己的操作称为yielding让步。
linux的进程调度
完全公平调度算法,简称CFS
策略
策略决定调度程序在何时让什么进程运行。调度器的策略往往就决定系统的整体印象,并且,还要负责优化使用处理器时间。
IO消耗型和处理器消耗型的进程
进程可以被分为IO消耗型和处理器消耗型。前者指进程的大部分时间用来提交IO请求或是等待IO请求。因此,这样的进程经常处于可运行状态,但通常都是运行短短的一会儿,因为他在等待更多的IO请求时最后总会阻塞。
处理器消耗型进程把时间大多用在执行代码上。除非被抢占,否则它们通常都一直不停地运行,因为它们没有太多的IO需求。但是,因为它们不属于IO驱动类型,所以从系统响应速度考虑,调度器不应该经常让它们运行。对于这类处理器消耗型的进程,调度策略往往是尽量降低它们的调度频率,而延长其运行时间。
调度策略通常要在这两个矛盾的目标中间寻找平衡:进程响应迅速和最大系统利用率。为了满足上述需求,调度程序通常采用一套非常复杂的算法来决定最值得运行的进程投入运行,但是它往往不能保证低优先级进程被公平对待。为了保证交互式应用,通常优先调度IO消耗型进程,也不会忽略处理器消耗型的进程。
进程优先级
调度算法中最基本的一类就是基于优先级调度。这是一种根据进程的价值和其对处理器时间的需求来对进程分级的想法。通常做法是(并未为linux完全采用)优先级高的进程先运行,低的后运行,相同优先级的进程按轮转方式进行调度。在某些系统中,优先级高的进程使用的时间片也较长。调度程序总是选择时间片未用尽而且优先级最高的进程运行。用户和系统都可以通过设置进程的优先级来影响系统的调度。
linux采用了两种不同的优先级范围。第一种是用nice值,它的范围是从-20到+19。默认值为0,越大的nice值意味着更低的优先级。相比高nice值的进程,低nice值的进程可以获得等多的处理器时间。在linux中,nice值代表时间片的比例。ps -el命令中NI的一列就是进程对应的nice值。
第二种范围是实时优先级,其值是可配置的,默认情况下它的变化范围是从0到99。与nice值意义相反,越高的实时优先级数值意味着进程优先级越高。任何实时进程的优先级都高于普通的进程。实时优先级为RTPRIO列,如果显示”-“,则说明它不是实时进程。
时间片
时间片是一个数值,它表明进程在被抢占前所能持续运行的时间。调度策略必须规定一个默认的时间片,但这并不是一件简单的事情。时间片过长会导致系统对交互的响应表现欠佳,时间片太短会显著增大进程切换带来的处理器耗时。IO消耗型不需要很长的时间片,而处理器消耗型却希望越长越好。
linux的CFS调度其没有直接分配时间片到进程,它是将处理器的使用比划分给了进程。这样一来,进程所获得的处理器时间和系统负载密切相关。这个比例进一步还会收到进程nice值的影响。
linux系统是抢占式的。当一个进程进入可运行态,它就被准许投入运行。在多数操作系统中,是否要将一个进程立刻投入运行,是完全由进程优先级和是否有时间片决定的。而在linux中使用新的CFS调度器,其抢占时机取决于新的可运行程序消耗了多少处理器使用比。如果消耗的使用比比当前进程小,则新进程立刻投入运行,抢占当前进程。否则,将推迟其运行。
linux调度算法
调度器类
linux调度器是以模块方式提供的,这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。
这种模块化结构被称为调度器类,它允许不同地可动态添加的调度算法并存,调度属于自己范畴的进程。每个调度器都有一个优先级,基础的调度器会按照优先级遍历调度类,拥有一个可执行进程的最高优先级的调度器类胜出,去选择下面要执行的一个程序。
完全公平调度(CFS)是一个针对普通进程的调度类。
传统unix系统中的进程调度
公平调度
CFS的出发点基于一个简单的理念:进程调度的效果应如同系统具备一个理想中的完美多任务处理器。在这种系统中,每个进程能获得1/n的处理器时间——n是指可运行进程的数量。举例来说,假如我们有两个运行进程,在标准Unix调度模型中,我们先运行其中一个5ms,然后再运行另一个5ms。但它们任何一个运行时都将占有100%的处理器。而在理想情况下,完美的多任务处理器模型应该是这样的:我们能在10ms内同时运行两个进程,它们各自使用处理器一半的能力。
当然,上述理想模型并非显示,因为我们无法在一个处理器上真的同时运行多个线程。而且如果每个进程运行无限小的时间周期也是不高效的——因为调度时进程抢占会带来一定的代价:将一个进程换出,另一个进程换入本身有消耗,同时还会影响到缓存的效率。CFS的做法是允许每个进程运行一段时间、循环轮转、选择运行时间最少的进程作为下一个运行进程,CFS在所有可运行进程总数基础上计算出一个进程应该运行多久。nice值在CFS中被作为进程获得的处理器运行比的权重。
每个进程都按其权重在全部可运行进程中所占比例的“时间片”来运行,为了计算准确的时间片,CFS为完美多任务中的无限小调度周期的近似值设立了一个目标。而这个目标称为目标延迟,越小的调度周期将带来越好的交互性,同时也更接近完美的多任务。但是你必须承受更高的切换代价。假定目标延迟值为20ms,如果我们有两个任务,则每个任务只能运行10ms,如果有4个,则只能运行5ms。
当运行任务数量趋于无限时,它们各自所获取的处理器使用比和时间片都将趋于0。CFS为此引入每个进程获得的时间片底线,这个底线被称为最小粒度。默认情况下为1ms。
任何进程所获的处理器时间是由它自己和其他所有可运行进程nice值的差值决定的。
linux调度的实现
- 时间记账
- 进程选择
- 调度器入口
- 睡眠和唤醒
时间记账
所有的调度器都必须对进程运行时间做记账。多数Unix系统,分配一个时间片给每一个进程。当每次系统时钟节拍发生时,时间片都会被减少一个节拍周期。一个进程的时间片被减少到0时,它就会被另一个尚未减少到0的可运行进程抢占。
- 调度器实体结构
CFS不再有时间片的概念,但是它也必须维护每个进程运行的时间记账,因为它需要确保每个进程只在公平分配给它的处理器时间内运行。CFS使用调度器实体结构来追踪进程运行记账。
1
2
3
4
// linux/sched.h
struct sched_entity {
u64 vruntime;
}
调度器实体作为一个名叫se的成员变量,嵌入在进程描述符struct task_struct内。
- 虚拟实时
vruntime变量存放进程的虚拟运行时间,该运行时间的计算是经过了所有可运行进程总数的标准化(或者说是被加权的)。虚拟时间是以ns为单位的,所以vruntime和定时器节拍不再相关。虚拟运行时间可以帮助我们逼近CFS模型所追求的理想多任务处理器。CFS使用vruntime来记录一个程序到底运行了多长时间以及它还能再运行多久。
1
2
3
4
update_curr
// 获取从最后一次修改负载后当前任务所占用的运行总时间
->delta_exec = now - curr->exec_start
__update_curr(.. delta_exec)
update_curr计算了当前进程的执行时间,并且将其存放在变量delta_exec中。然后它又将运行时间传递给了__update_curr,由后者再根据当前可运行进程总数对运行时间进行加权计算。最终将上述的权重值与当前运行进程的vruntime相加。
update_curr是由系统定时器周期性调到用的,无论是再进程处于可运行态,还是被阻塞处于不可运行态。根据这种方式,vruntime可以准确地测量给定进程的运行时间,并且可知道谁应该是下一个被运行的进程。
进程选择
CFS试图利用一个简单的规则去均衡进程的虚拟运行时间:当CFS需要选择下一个运行进程时,它会挑选一个具有最小vruntime的进程。
CFS使用红黑树来组织可运行进程队列,并利用其迅速找到最小vruntime值的进程。
- 挑选下一个任务
CFS进程选择算法可以简单总结为运行rbtree树中最左边叶子节点所代表的那个进程。实现这一过程的函数是__pick_next_entity,此时对应节点已被缓存
- 向树中加入进程
enqueue_entity
- 从树中删除进程
删除动作发生在进程堵塞(变为不可运行状态)或者终止时(结束运行)。