分类目录归档:进程管理

从几个问题开始理解CFS调度器

CFS(完全公平调度器)是Linux内核2.6.23版本开始采用的进程调度器,它的基本原理是这样的:设定一个调度周期(sched_latency_ns),目标是让每个进程在这个周期内至少有机会运行一次,换一种说法就是每个进程等待CPU的时间最长不超过这个调度周期;然后根据进程的数量,大家平分这个调度周期内的CPU使用权,由于进程的优先级即nice值不同,分割调度周期的时候要加权;每个进程的累计运行时间保存在自己的vruntime字段里,哪个进程的vruntime最小就获得本轮运行的权利。

那么问题就来了:

新进程的vruntime的初值是不是0啊?

假如新进程的vruntime初值为0的话,比老进程的值小很多,那么它在相当长的时间内都会保持抢占CPU的优势,老进程就要饿死了,这显然是不公平的。所以CFS是这样做的:每个CPU的运行队列cfs_rq都维护一个min_vruntime字段,记录该运行队列中所有进程的vruntime最小值,新进程的初始vruntime值就以它所在运行队列的min_vruntime为基础来设置,与老进程保持在合理的差距范围内。参见后面的源代码。

新进程的vruntime初值的设置与两个参数有关:
sched_child_runs_first:规定fork之后让子进程先于父进程运行;
sched_features的START_DEBIT位:规定新进程的第一次运行要有延迟。

注:
sched_features是控制调度器特性的开关,每个bit表示调度器的一个特性。在sched_features.h文件中记录了全部的特性。START_DEBIT是其中之一,如果打开这个特性,表示给新进程的vruntime初始值要设置得比默认值更大一些,这样会推迟它的运行时间,以防进程通过不停的fork来获得cpu时间片。

如果参数 sched_child_runs_first打开,意味着创建子进程后,保证子进程会在父进程之前运行。

子进程在创建时,vruntime初值首先被设置为min_vruntime;然后,如果sched_features中设置了START_DEBIT位,vruntime会在min_vruntime的基础上再增大一些。设置完子进程的vruntime之后,检查sched_child_runs_first参数,如果为1的话,就比较父进程和子进程的vruntime,若是父进程的vruntime更小,就对换父、子进程的vruntime,这样就保证了子进程会在父进程之前运行。

休眠进程的vruntime一直保持不变吗?

如果休眠进程的 vruntime 保持不变,而其他运行进程的 vruntime 一直在推进,那么等到休眠进程终于唤醒的时候,它的vruntime比别人小很多,会使它获得长时间抢占CPU的优势,其他进程就要饿死了。这显然是另一种形式的不公平。CFS是这样做的:在休眠进程被唤醒时重新设置vruntime值,以min_vruntime值为基础,给予一定的补偿,但不能补偿太多。

 休眠进程在唤醒时会立刻抢占CPU吗?

这是由CFS的唤醒抢占 特性决定的,即sched_features的WAKEUP_PREEMPT位。

由于休眠进程在唤醒时会获得vruntime的补偿,所以它在醒来的时候有能力抢占CPU是大概率事件,这也是CFS调度算法的本意,即保证交互式进程的响应速度,因为交互式进程等待用户输入会频繁休眠。除了交互式进程以外,主动休眠的进程同样也会在唤醒时获得补偿,例如通过调用sleep()、nanosleep()的方式,定时醒来完成特定任务,这类进程往往并不要求快速响应,但是CFS不会把它们与交互式进程区分开来,它们同样也会在每次唤醒时获得vruntime补偿,这有可能会导致其它更重要的应用进程被抢占,有损整体性能。

我曾经处理过一个案例,服务器上有两类应用进程:
A进程定时循环检查有没有新任务,如果有的话就简单预处理后通知B进程,然后调用nanosleep()主动休眠,醒来后再重复下一个循环;
B进程负责数据运算,是CPU消耗型的;
B进程的运行时间很长,而A进程每次运行时间都很短,但睡眠/唤醒却十分频繁,每次唤醒就会抢占B,导致B的运行频繁被打断,大量的进程切换带来很大的开销,整体性能下降很厉害。
那有什么办法吗?有,最后我们通过禁止CFS唤醒抢占 特性解决了问题:

禁用唤醒抢占 特性之后,刚唤醒的进程不会立即抢占运行中的进程,而是要等到运行进程用完时间片之后。在以上案例中,经过这样的调整之后B进程被抢占的频率大大降低了,整体性能得到了改善。

如果禁止唤醒抢占特性对你的系统来说太过激进的话,你还可以选择调大以下参数:

sched_wakeup_granularity_ns
这个参数限定了一个唤醒进程要抢占当前进程之前必须满足的条件:只有当该唤醒进程的vruntime比当前进程的vruntime小、并且两者差距(vdiff)大于sched_wakeup_granularity_ns的情况下,才可以抢占,否则不可以。这个参数越大,发生唤醒抢占就越不容易。

进程占用的CPU时间片可以无穷小吗?

假设有两个进程,它们的vruntime初值都是一样的,第一个进程只要一运行,它的vruntime马上就比第二个进程更大了,那么它的CPU会立即被第二个进程抢占吗?答案是这样的:为了避免过于短暂的进程切换造成太大的消耗,CFS设定了进程占用CPU的最小时间值,sched_min_granularity_ns,正在CPU上运行的进程如果不足这个时间是不可以被调离CPU的。

sched_min_granularity_ns发挥作用的另一个场景是,本文开门见山就讲过,CFS把调度周期sched_latency按照进程的数量平分,给每个进程平均分配CPU时间片(当然要按照nice值加权,为简化起见不再强调),但是如果进程数量太多的话,就会造成CPU时间片太小,如果小于sched_min_granularity_ns的话就以sched_min_granularity_ns为准;而调度周期也随之不再遵守sched_latency_ns,而是以 (sched_min_granularity_ns * 进程数量) 的乘积为准。

进程从一个CPU迁移到另一个CPU上的时候vruntime会不会变?

在多CPU的系统上,不同的CPU的负载不一样,有的CPU更忙一些,而每个CPU都有自己的运行队列,每个队列中的进程的vruntime也走得有快有慢,比如我们对比每个运行队列的min_vruntime值,都会有不同:

如果一个进程从min_vruntime更小的CPU (A) 上迁移到min_vruntime更大的CPU (B) 上,可能就会占便宜了,因为CPU (B) 的运行队列中进程的vruntime普遍比较大,迁移过来的进程就会获得更多的CPU时间片。这显然不太公平。

CFS是这样做的:
当进程从一个CPU的运行队列中出来 (dequeue_entity) 的时候,它的vruntime要减去队列的min_vruntime值;
而当进程加入另一个CPU的运行队列 ( enqueue_entiry) 时,它的vruntime要加上该队列的min_vruntime值。
这样,进程从一个CPU迁移到另一个CPU之后,vruntime保持相对公平。

 

抢占(preemption)是如何发生的

进程切换有自愿(Voluntary)和强制(Involuntary)之分,在前文中详细解释了两者的不同,简单来说,自愿切换意味着进程需要等待某种资源,强制切换则与抢占(Preemption)有关。

抢占(Preemption)是指内核强行切换正在CPU上运行的进程,在抢占的过程中并不需要得到进程的配合,在随后的某个时刻被抢占的进程还可以恢复运行。发生抢占的原因主要有:进程的时间片用完了,或者优先级更高的进程来争夺CPU了。

抢占的过程分两步,第一步触发抢占,第二步执行抢占,这两步中间不一定是连续的,有些特殊情况下甚至会间隔相当长的时间:

  1. 触发抢占:给正在CPU上运行的当前进程设置一个请求重新调度的标志(TIF_NEED_RESCHED),仅此而已,此时进程并没有切换。
  2. 执行抢占:在随后的某个时刻,内核会检查TIF_NEED_RESCHED标志并调用schedule()执行抢占。

抢占只在某些特定的时机发生,这是内核的代码决定的。

触发抢占的时机

每个进程都包含一个TIF_NEED_RESCHED标志,内核根据这个标志判断该进程是否应该被抢占,设置TIF_NEED_RESCHED标志就意味着触发抢占。

直接设置TIF_NEED_RESCHED标志的函数是 set_tsk_need_resched();
触发抢占的函数是resched_task()。

TIF_NEED_RESCHED标志什么时候被设置呢?在以下时刻:

  • 周期性的时钟中断

时钟中断处理函数会调用scheduler_tick(),这是调度器核心层(scheduler core)的函数,它通过调度类(scheduling class)的task_tick方法 检查进程的时间片是否耗尽,如果耗尽则触发抢占:

Linux的进程调度是模块化的,不同的调度策略比如CFS、Real-Time被封装成不同的调度类,每个调度类都可以实现自己的task_tick方法,调度器核心层根据进程所属的调度类调用对应的方法,比如CFS对应的是task_tick_fair,Real-Time对应的是task_tick_rt,每个调度类对进程的时间片都有不同的定义。

  • 唤醒进程的时候

当进程被唤醒的时候,如果优先级高于CPU上的当前进程,就会触发抢占。相应的内核代码中,try_to_wake_up()最终通过check_preempt_curr()检查是否触发抢占。

  • 新进程创建的时候

如果新进程的优先级高于CPU上的当前进程,会触发抢占。相应的调度器核心层代码是sched_fork(),它再通过调度类的 task_fork方法触发抢占:

  • 进程修改nice值的时候

如果进程修改nice值导致优先级高于CPU上的当前进程,也会触发抢占。内核代码参见 set_user_nice()。

  • 进行负载均衡的时候

在多CPU的系统上,进程调度器尽量使各个CPU之间的负载保持均衡,而负载均衡操作可能会需要触发抢占。

不同的调度类有不同的负载均衡算法,涉及的核心代码也不一样,比如CFS类在load_balance()中触发抢占:

RT类的负载均衡基于overload,如果当前运行队列中的RT进程超过一个,就调用push_rt_task()把进程推给别的CPU,在这里会触发抢占。

执行抢占的时机

触发抢占通过设置进程的TIF_NEED_RESCHED标志告诉调度器需要进行抢占操作了,但是真正执行抢占还要等内核代码发现这个标志才行,而内核代码只在设定的几个点上检查TIF_NEED_RESCHED标志,这也就是执行抢占的时机。

抢占如果发生在进程处于用户态的时候,称为User Preemption(用户态抢占);如果发生在进程处于内核态的时候,则称为Kernel Preemption(内核态抢占)。

执行User Preemption(用户态抢占)的时机

  1. 从系统调用(syscall)返回用户态时;
  2. 从中断返回用户态时。

执行Kernel Preemption(内核态抢占)的时机

Linux在2.6版本之后就支持内核抢占了,但是请注意,具体取决于内核编译时的选项:

  • CONFIG_PREEMPT_NONE=y
    不允许内核抢占。这是SLES的默认选项。
  • CONFIG_PREEMPT_VOLUNTARY=y
    在一些耗时较长的内核代码中主动调用cond_resched()让出CPU。这是RHEL的默认选项。
  • CONFIG_PREEMPT=y
    允许完全内核抢占。

在 CONFIG_PREEMPT=y 的前提下,内核态抢占的时机是:

  1. 中断处理程序返回内核空间之前会检查TIF_NEED_RESCHED标志,如果置位则调用preempt_schedule_irq()执行抢占。preempt_schedule_irq()是对schedule()的包装。
  2. 当内核从non-preemptible(禁止抢占)状态变成preemptible(允许抢占)的时候;
    在preempt_enable()中,会最终调用 preempt_schedule 来执行抢占。preempt_schedule()是对schedule()的包装。

 

进程切换:自愿(voluntary)与强制(involuntary)

从进程的角度看,CPU是共享资源,由所有的进程按特定的策略轮番使用。一个进程离开CPU、另一个进程占据CPU的过程,称为进程切换(process switch)。进程切换是在内核中通过调用schedule()完成的。

发生进程切换的场景有以下三种:

  1. 进程运行不下去了:
    比如因为要等待IO完成,或者等待某个资源、某个事件,典型的内核代码如下:
  2. 进程还在运行,但内核不让它继续使用CPU了:
    比如进程的时间片用完了,或者优先级更高的进程来了,所以该进程必须把CPU的使用权交出来;
  3. 进程还可以运行,但它自己的算法决定主动交出CPU给别的进程:
    用户程序可以通过系统调用sched_yield()来交出CPU,内核则可以通过函数cond_resched()或者yield()来做到。

进程切换分为自愿切换(Voluntary)和强制切换(Involuntary),以上场景1属于自愿切换,场景2和3属于强制切换。如何分辨自愿切换和强制切换呢?

  • 自愿切换发生的时候,进程不再处于运行状态,比如由于等待IO而阻塞(TASK_UNINTERRUPTIBLE),或者因等待资源和特定事件而休眠(TASK_INTERRUPTIBLE),又或者被debug/trace设置为TASK_STOPPED/TASK_TRACED状态;
  • 强制切换发生的时候,进程仍然处于运行状态(TASK_RUNNING),通常是由于被优先级更高的进程抢占(preempt),或者进程的时间片用完了。

注:实际情况更复杂一些,由于Linux内核支持抢占,kernel preemption有可能发生在自愿切换的过程之中,比如进程正进入休眠,本来如果顺利完成的话就属于自愿切换,但休眠的过程并不是原子操作,进程状态先被置成TASK_INTERRUPTIBLE,然后进程切换,如果Kernel Preemption恰好发生在两者之间,那就打断了休眠过程,自愿切换尚未完成,转而进入了强制切换的过程(虽然是强制切换,但此时的进程状态已经不是运行状态了),下一次进程恢复运行之后会继续完成休眠的过程。所以判断进程切换属于自愿还是强制的算法要考虑进程在切换时是否正处于被抢占(preempt)的过程中,参见以下内核代码:

最后,澄清几个容易产生误解的场景:

  • 进程可以通过调用sched_yield()主动交出CPU,这不是自愿切换,而是属于强制切换,因为进程仍然处于运行状态。
  • 有时候内核代码会在耗时较长的循环体内通过调用 cond_resched()或yield() ,主动让出CPU,以免CPU被内核代码占据太久,给其它进程运行机会。这也属于强制切换,因为进程仍然处于运行状态。

进程自愿切换(Voluntary)和强制切换(Involuntary)的次数被统计在 /proc/<pid>/status 中,其中voluntary_ctxt_switches表示自愿切换的次数,nonvoluntary_ctxt_switches表示强制切换的次数,两者都是自进程启动以来的累计值。

也可以用 pidstat -w 命令查看进程切换的每秒统计值:

自愿切换和强制切换的统计值在实践中有什么意义呢?
大致而言,如果一个进程的自愿切换占多数,意味着它对CPU资源的需求不高。如果一个进程的强制切换占多数,意味着对它来说CPU资源可能是个瓶颈,这里需要排除进程频繁调用sched_yield()导致强制切换的情况。

Real-Time进程会导致系统lockup吗?

Linux kernel支持两种实时(real-time)调度策略(scheduling policy):SCHED_FIFO和SCHED_RR,无论是哪一种,实时进程的优先级范围[0~99]都高于普通进程[100~139],始终优先于普通进程得到运行。如果实时进程是CPU消耗型的,会不会导致其它进程得不到运行机会,造成系统lockup呢?

这实际上是两个问题,不能混为一谈,第一个问题是会不会造成系统lockup,第二个问题是会不会导致其它进程得不到运行机会。我们一个一个分别来谈。

实时进程会不会造成系统lockup?

Lockup分为soft lockup和hard lockup,我在《内核如何检测SOFT LOCKUP与HARD LOCKUP》一文中解释了Linux kernel检测lockup的原理。

Hard lockup发生在CPU中断被屏蔽的情况下,因为实时进程本身并不会屏蔽CPU中断,hrtimer时钟中断是可以得到响应的,所以不会导致hard lockup

Soft lockup发生在内核线程[watchdog/x]得不到运行的情况下,理论上如果实时进程占着CPU不放,确实有可能导致[watchdog/x]得不到运行而发生soft lockup,然而这个可能性并不大,因为[watchdog/x]本身也是实时进程,调度策略为SCHED_FIFO,优先级已经是最高的99:

如果占着CPU不放的实时进程也是SCHED_FIFO并且优先级为99,就有可能导致soft lockup。为什么呢?我们看一下实时进程的调度策略就明白了:

  • 在多个实时进程之间,优先级更高的会抢先运行
    (注:实时进程的优先级数字越大则优先级越高,99最高,0最低;而普通进程正好相反,优先级数字越大则优先级越低,139最低,100最高);
  • 优先级相同的实时进程之间,不会互相抢占,只能等对方主动释放CPU;
  • SCHED_FIFO调度策略的特点是,进程会一直保持运行直到发生以下情况之一:
    1. 进程主动调用sched_yield(2)放弃运行,自动排到运行队列的队尾,等到相同优先级的其它进程运行之后才有机会再运行;
    2. 进程进入睡眠状态(比如由于等待I/O的原因),唤醒后自动排到运行队列的队尾,等到相同优先级的其它进程运行之后才有机会再运行;
    3. 被优先级更高的实时进程抢占,这种情况下会自动排到运行队列的队首,下次运行的机会排在相同优先级的其它进程的前面。
  • SCHED_RR进程与SCHED_FIFO唯一不同的是,实时进程的运行时间是分为一段一段的,在相同优先级的进程之间轮流运行,每个进程运行完一个时间段之后,必须让给下一个进程(强调:仅对相同优先级而言,不同优先级的进程之间仍然会互相抢占)。

所以,如果占着CPU不放的实时进程的调度策略是SCHED_FIFO,并且优先级为与[watchdog/x]相同的99,SCHED_FIFO的调度策略决定了只要它不放手,[watchdog/x]就无法运行,结果是会导致soft lockup。

接下来第二个问题是:

实时进程会不会导致其它进程得不到运行机会?

如果实时进程占着CPU不放,会不会导致其它进程得不到运行机会,包括管理员的shell也无法运行、连基本的管理任务也进行不了,最终造成整个系统失去控制?

通常不会。因为Linux kernel有一个RealTime Throttling机制,就是为了防止CPU消耗型的实时进程霸占所有的CPU资源而造成整个系统失去控制。它的原理很简单,就是保证无论如何普通进程都能得到一定比例(默认5%)的CPU时间,可以通过两个内核参数来控制:

  • /proc/sys/kernel/sched_rt_period_us
    缺省值是1,000,000 μs (1秒),表示实时进程的运行粒度为1秒。(注:修改这个参数请谨慎,太大或太小都可能带来问题)。
  • /proc/sys/kernel/sched_rt_runtime_us
    缺省值是 950,000 μs (0.95秒),表示在1秒的运行周期里所有的实时进程一起最多可以占用0.95秒的CPU时间。
    如果sched_rt_runtime_us=-1,表示取消限制,意味着实时进程可以占用100%的CPU时间(慎用,有可能使系统失去控制)。

所以,Linux kernel默认情况下保证了普通进程无论如何都可以得到5%的CPU时间,尽管系统可能会慢如蜗牛,但管理员仍然可以利用这5%的时间设法恢复系统,比如停掉失控的实时进程,或者给自己的shell进程赋予更高的实时优先级以便执行管理任务,等等。

Real-time Throttling支持cgroup,详见https://www.kernel.org/doc/Documentation/scheduler/sched-rt-group.txt

参考资料:
https://lwn.net/Articles/296419/

理解Linux load average的误区

uptime和top等命令都可以看到load average指标,从左至右三个数字分别表示1分钟、5分钟、15分钟的load average:

Load average的概念源自UNIX系统,虽然各家的公式不尽相同,但都是用于衡量正在使用CPU的进程数量和正在等待CPU的进程数量,一句话就是runnable processes的数量。所以load average可以作为CPU瓶颈的参考指标,如果大于CPU的数量,说明CPU可能不够用了。

但是,Linux上不是这样的!

Linux上的load average除了包括正在使用CPU的进程数量和正在等待CPU的进程数量之外,还包括uninterruptible sleep的进程数量。通常等待IO设备、等待网络的时候,进程会处于uninterruptible sleep状态。Linux设计者的逻辑是,uninterruptible sleep应该都是很短暂的,很快就会恢复运行,所以被等同于runnable。然而uninterruptible sleep即使再短暂也是sleep,何况现实世界中uninterruptible sleep未必很短暂,大量的、或长时间的uninterruptible sleep通常意味着IO设备遇到了瓶颈。众所周知,sleep状态的进程是不需要CPU的,即使所有的CPU都空闲,正在sleep的进程也是运行不了的,所以sleep进程的数量绝对不适合用作衡量CPU负载的指标,Linux把uninterruptible sleep进程算进load average的做法直接颠覆了load average的本来意义。所以在Linux系统上,load average这个指标基本失去了作用,因为你不知道它代表什么意思,当看到load average很高的时候,你不知道是runnable进程太多还是uninterruptible sleep进程太多,也就无法判断是CPU不够用还是IO设备有瓶颈。

参考资料:https://en.wikipedia.org/wiki/Load_(computing)
“Most UNIX systems count only processes in the running (on CPU) or runnable (waiting for CPU) states. However, Linux also includes processes in uninterruptible sleep states (usually waiting for disk activity), which can lead to markedly different results if many processes remain blocked in I/O due to a busy or stalled I/O system.“

源代码: