0%

Linux进程管理(番外篇)调度算法的演变

原图

O(n)调度器

如何组织task

调度器模块定义了一个runqueue_head的链表头变量,无论进程是普通进程还是实时进程,只要进程状态变成可运行状态的时候,它会被挂入这个全局runqueue链表中。由于整个系统中的所有CPU共享一个runqueue,为了解决同步问题,调度器模块定义了一个自旋锁来保护对这个全局runqueue的并发访问。

除了这个runqueue队列,系统还有一个囊括所有task(不管其进程状态为何)的链表,链表头定义为init_task,在一个调度周期结束后,重新为task赋初始时间片值的时候会用到该链表。

动态优先级

对于普通进程,计算动态优先级的策略如下:

  • 如果该进程的时间片已经耗尽,那么动态优先级是0,这也意味着在本次调度周期中该进程已经再也没有机会获取CPU资源了
  • 如果该进程的时间片还有剩余,那么其动态优先级等于该进程剩余的时间片和静态优先级之和。之所以用(20-nice value)表示静态优先级,主要是为了让静态优先级变成单调上升。之所以要考虑剩余时间片是为了奖励睡眠的进程,因为睡眠的进程剩余的时间片较多,因此动态优先级也就会高一些,更容易被调度器调度执行

在计算普通进程的动态优先级的时候,除了考虑进程剩余时间片信息和静态优先级,调度器也会酌情考虑cache和TLB的性能问题。例如A和B进程优先级相同,剩余的时间片都是3个tick,但是A进程上一次就是运行在本CPU上,如果选择A,可能会有更好的cache和TLB的命中率,从而提高性能。在这种情况下,调度器会提升A进程的动态优先级。此外,如果备选进程和当前进程共享同一个地址空间,那么在计算调度指数的时候也会做小小的倾斜。

主调度器算法

主调度器(schedule函数)核心代码如下:

1
2
3
4
5
6
list_for_each(tmp, &runqueue_head) {
p = list_entry(tmp, struct task_struct, run_list);
int weight = goodness(p, this_cpu, prev->active_mm);
if (weight > c)
c = weight, next = p;
}

list_for_each用来遍历runqueue_head链表上的所有的进程,临时变量p就是本次需要检查的进程描述符。如何判断哪一个进程是最适合调度执行的进程呢?我们需要计算进程的动态优先级(对应上面程序中的变量weight),它是通过goodness函数实现的。动态优先级最大的那个进程就是当前最适合调度到CPU执行的进程。一旦选中,调度器会启动进程切换,运行该进程以替换之前的那个进程。

时间片处理

普通进程的时间片处理思路是这样:

  • 每个进程根据其静态优先级可以固定分配一个缺省的时间片,静态优先级越大,分配的时间片就越大
  • 一旦Runqueue中的进程被调度执行,那么其时间片就会在tick到来的时候递减,如果进程时间片耗尽,那么该进程将失去分配CPU资源的资格
  • Runqueue中的进程的时间片全部被用完之后,我们称一个调度周期结束,这时候需要为runqueue中的进程重新设定其缺省时间片,这样,一个新的调度周期又开始了

O(1)调度器

Why O(1)调度器

让我们一起来控诉O(n)调度器的“七宗罪”,同时这也是Ingo Molnar发起O(1)调度器项目背后的原因。

  • 算法复杂度问题 让人最不爽的就是对runqueue队列的遍历,随着系统中runnable状态的进程数目增多,那么调度器select next的运算量也随之呈线性的增长,这也是我们为什么叫它O(n)调度器的原因。此外,调度周期结束后,调度器会为所有进程的时间片进行“充值“的动作,为每一个进程计算其时间片的过程太耗费时间。

  • SMP扩展性问题,2.4内核的O(n)调度器有非常差的SMP扩展性

  • CPU空转问题 每当runqueue链表中的所有进程耗尽了其时间片,这时候就需要启动对系统中所有进程时间片重新计算的过程。这个计算过程异常丑陋,需要遍历系统中的所有进程,为进程描述符的counter成员赋一个新值。而这个操作足以把该CPU上的L1 cache全部干掉,这时候L1 cache的命中率急剧下降在只剩最后一个线程的时候多个cpu中就会有cpu处于idle状态,出现cpu空转问题

  • task bouncing issue 一般而言,一个进程最好是从一而终,运行在一个cpu上,在O(n)调度器下很多人都反映有进程在CPU之间跳来跳去的现象导致cache命中率下降

  • RT进程调度性能问题 实时进程和普通进程挂在一个链表中。当调度实时进程的时候,我们需要遍历整个runqueue列表,扫描并计算所有进程的调度指数,从而选择出心仪的那个实时进程

    当然,上面的这些还不是关键,最重要的是整个linux内核不是抢占式内核,在整个内核态都不能被抢占。除了内核抢占性之外,优先级翻转问题也需要引起调度器的重视,否则即便一个rt进程变成runnable状态了,但是也只能眼睁睁的看着比它优先级低的进程运行,直到该rt进程等待的资源被释放。

  • 交互式普通进程的调度延迟问题 O(n)并不区分交互式进程和批处理进程,它只是奖励经常睡眠的那些进程

  • 时间片粒度问题 随着runnable进程增大,调度周期也变大。当一个进程耗尽其时间片之后,只能等待下一个调度周期到来。因此随着调度周期变大,系统响应也会变的较差

虽然O(n)调度器存在不少的issue,但是社区的人还是基本认可这套算法的,O(1)基于O(n)调度器进行改进。鉴于O(1)调度器和O(n)调度器没有本质区别,因此我们只是描述它们之间不同的地方。

O(1)调度器的软件功能划分

下图是一个O(1)调度器的软件框架:

O(n)调度器中只有一个全局的runqueue,严重影响了扩展性,因此在O(1)调度器中引入了per-CPU runqueue的概念。系统中所有的可运行状态的进程首先经过负载均衡模块挂入各个CPU的runqueue,然后由主调度器和tick调度器驱动该CPU上的调度行为。

由于引入了per-CPU runqueue,O(1)调度器删除了全局runqueue的spin lock,而是把这个spin lock放入到per-CPU runqueue数据结构中(rq->lock),通过把一个大锁细分成小锁,可以大大降低调度延迟,提升系统响应时间。这种方法在内核中经常使用,是一个比较通用的性能优化方法。

通过上面的软件结构划分可以解决O(n)调度的SMP扩展性问题和CPU空转问题。此外,好的复杂均衡算法也可以解决O(n)调度器的task bouncing 问题。

O(1)调度器的runqueue结构

O(1)调度器的基本优化思路就是把原来runqueue上的单链表变成多个链表,即每一个优先级的进程被挂入不同链表中。相关的软件结构可以参考下面的图片:

在调度器中,runqueue是一个很重要的数据结构,它最重要的作用是管理那些处于可运行状态的进程。O(1)调度器引入了优先级队列的概念来管理task,具体由struct prio_array抽象:

1
2
3
4
5
struct prio_array {
unsigned int nr_active;
unsigned long bitmap[BITMAP_SIZE];
struct list_head queue[MAX_PRIO];
};

由于支持140个优先级,因此queue成员中有140个分别表示各个优先级的链表头,不同优先级的进程挂入不同的链表中。bitmap 是表示各个优先级进程链表是空还是非空。 nr_active表示这个队列中有多少个task。在这些队列中,100~139是普通进程的优先级,其他的是实时进程的优先级。因此,在O(1)调度器中,RT进程和普通进程被区分开了,普通进程根本不会影响RT进程的调度。 Runqueue中有两个优先级队列(struct prio_array)分别用来管理active(即时间片还有剩余)和expired(时间片耗尽)的进程。Runqueue中有两个优先级队列的指针,分别指向这两个优先级队列。随着系统的运行,active队列的task一个个的耗尽其时间片,挂入到expired队列。当active队列的task为空的时候,切换active和expired队列,开始一轮新的调度过程。

虽然在O(1)调度器中task组织的形式发生了变化,但是其核心思想仍然和O(n)调度器一致的。

核心调度算法

主调度器(就是schedule函数)的主要功能是从该CPU的runqueue找到一个最合适的进程调度执行。其基本的思路就是从active优先级队列中寻找,代码如下:

1
2
3
idx = sched_find_first_bit(array->bitmap);
queue = array->queue + idx;
next = list_entry(queue->next, task_t, run_list);

首先在当前active优先级队列的bitmap寻找第一个非空的进程链表,然后从该链表中找到的第一个节点就是最适合下一个调度执行的进程。由于没有遍历整个链表的操作,因此这个调度器的算法复杂度是一个常量,从而解决了O(n)算法复杂度的issue。

如果当前active优先级队列中“空无一人”(nr_active等于0),那么这时候就需要切换active和expired优先级队列了:

1
2
3
4
5
if (unlikely(!array->nr_active)) {
rq->active = rq->expired;
rq->expired = array;
array = rq->active;
}
  • 切换很快,并没有一个遍历所有进程重新赋default时间片的操作(大大缩减了runqueue临界区的size)。这些都避免了O(n)调度器带来的种种问题,从而提高了调度器的性能。
  • 对于O(1)调度器,时间片的重新赋值是分散处理的,在各个task耗尽其时间片之后立刻进行的。这样的改动也修正了O(n)调度器一次性的遍历系统所有进程,重新为时间片赋值的过程。
  • O(1)调度器使用非常复杂的算法来判断进程的用户交互指数以及进程是否是交互式进程,它总是比仅仅考虑睡眠时间的O(n)调度器性能要好。
  • Linux引入了抢占式内核的概念(CONFIG_PREEMPT),如果没有配置该选项,那么一切和2.4内核保持一致。

番外之番外-多级反馈队列算法

多级反馈队列算法的核心思想是把进程按照优先级分成多个队列,相同优先级的进程在同一个队列中。如图所示,系统中有5个优先级,每个优先级有一个队列,队列5的优先级最高,队列1的优先级最低。

多级反馈队列算法有如下几条基本规则。

  • 规则1:如果进程A的优先级大于进程B的优先级,那么调度器选择进程A
  • 规则2:如果进程A和进程B的优先级一样,那么它们同属一个队列,可使用轮转调度算法来选择
  • 规则3:当一个新进程进入调度器时,把它放入优先级最高的队列里
  • 规则4a:当一个进程吃满时间片时,说明这是一个CPU消耗型的进程,需要把优先级降一级,从高优先级队列中迁移到低一级的队列里
  • 规则4b:当一个进程在时间片还没有结束之前放弃CPU时,说明这是一个I/O消耗型的进程,优先级保持不变,维持原来的高优先级

其实多级反馈队列算法的精髓在于“反馈”二字,也就是说,调度器可以动态地修改进程的优先级。进程可以大致分成两类,一类是I/O消耗型这类进程很少会完全占用时间片,通常情况下在发送I/O请求或者在等待I/O请求,比如等待鼠标操作、等待键盘输入等,这里进程和系统的用户体验很相关:另一类是CPU消耗型这类进程会完全占用时间片,比如计算密集型的应用程序、批处理应用程序等。多级反馈队列算法需要区分进程属于哪种类型,然后做出不同的反馈。

多级反馈队列算法看起来很不错,可是在实际应用过程中还是有不少问题的。

  • 第一个问题就是产生饥饿,当系统中有大量的I/O消耗型的进程时,这些I/O消耗型的进程会完全占用CPU,它们的优先级最高,那些CPU消耗型的进程就得不到CPU时间片,产生饥饿
  • 第二个问题是有些进程会欺骗调度器。比如,有的进程在时间片快要结束时突然发起一个I/O请求并且放弃CPU
  • 第三个问题是,一个进程在生命周期里,有可能一会儿是I/O消耗型的,一会儿是CPU消耗型的,所以很难判断一个进程究竟是哪种类型

针对第一个问题,多级反馈队列算法提出了一种改良方案,也就是在一定的时间周期后,把系统中的全部进程都提升到最高优先级,相当于系统中的进程过了一段时间又重新开始一样。

  • 规则5:每隔时间周期S之后,把系统中所有进程的优先级都提到最高级别。规则5可以解决进程饥饿的问题,然而,将时间周期S设置为多少合适呢?如果S太长,那么CPU消耗型的进程会饥饿;如果S太短,那么会影响系统的交互性

针对第二个问题,需要对规则4做一些改进:

  • 新的规则4:当一个进程使用完时间片后,不管它是否在时间片的最末尾发生I/O请求从而放弃CPU,都把它的优先级降一级。经过改进后的规则4可以有效地避免进程的欺骗行为

在介绍完多级反馈队列算法的核心实现后,在实际工程应用中还有很多问题需要思考和解决,其中一个最难的问题是参数如何确定和优化。比如,系统需要设计多少个优先级队列?时间片应该设置成多少?规则5中的时间间隔S又应该设置成多少,才能实现既不会让进程饥饿,也不会降低系统的交互性?这些问题很难回答。

参考文献

http://www.wowotech.net/process_management/scheduler-history.html