2.8.3 调度类

为了方便添加新的调度策略，Linux内核抽象了一个调度类sched_class，目前实现了5种调度类，如表2.10所示。

表2.10 调度类

这5种调度类的优先级从高到低依次为：停机调度类、限期调度类、实时调度类、公平调度类和空闲调度类。

1．停机调度类

停机调度类是优先级最高的调度类，停机进程（stop-task）是优先级最高的进程，可以抢占所有其他进程，其他进程不可以抢占停机进程。停机（stop是指stop machine）的意思是使处理器停下来，做更紧急的事情。

目前只有迁移线程属于停机调度类，每个处理器有一个迁移线程（名称是migration/<cpu_id>），用来把进程从当前处理器迁移到其他处理器，迁移线程对外伪装成实时优先级是99的先进先出实时进程。

停机进程没有时间片，如果它不主动让出处理器，那么它将一直霸占处理器。

引入停机调度类的一个原因是：支持限期调度类，迁移线程的优先级必须比限期进程的优先级高，能够抢占所有其他进程，才能快速处理调度器发出的迁移请求，把进程从当前处理器迁移到其他处理器。

2．限期调度类

限期调度类使用最早期限优先算法，使用红黑树（一种平衡的二叉树）把进程按照绝对截止期限从小到大排序，每次调度时选择绝对截止期限最小的进程。

如果限期进程用完了它的运行时间，它将让出处理器，并且把它从运行队列中删除。在下一个周期的开始，重新把它添加到运行队列中。

3．实时调度类

实时调度类为每个调度优先级维护一个队列，其代码如下：

    kernel/sched/sched.h
    struct rt_prio_array {
          DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /*包含一个作为分隔符的位*/
          struct list_head queue[MAX_RT_PRIO];
    };

位图bitmap用来快速查找第一个非空队列。数组queue的下标是实时进程的调度优先级，下标越小，优先级越高。

每次调度，先找到优先级最高的第一个非空队列，然后从队列中选择第一个进程。

使用先进先出调度策略的进程没有时间片，如果没有优先级更高的进程，并且它不主动让出处理器，那么它将一直霸占处理器。

使用轮流调度策略的进程有时间片，用完时间片以后，进程加入队列的尾部。默认的时间片是5毫秒，可以通过文件“/proc/sys/kernel/sched_rr_timeslice_ms”修改时间片。

4．公平调度类

公平调度类使用完全公平调度算法。完全公平调度算法引入了虚拟运行时间的概念：

虚拟运行时间 = 实际运行时间 × nice 0对应的权重 / 进程的权重

nice值和权重的对应关系如下：

    kernel/sched/core.c
    const int sched_prio_to_weight[40] = {
      /* -20 */     88761,     71755,     56483,     46273,     36291,
      /* -15 */     29154,     23254,     18705,     14949,     11916,
      /* -10 */      9548,      7620,      6100,      4904,      3906,
      /*  -5 */      3121,      2501,      1991,      1586,      1277,
      /*   0 */      1024,       820,       655,       526,       423,
      /*   5 */       335,       272,       215,       172,       137,
      /*  10 */       110,        87,        70,        56,        45,
      /*  15 */        36,        29,        23,        18,        15,
    };

nice 0对应的权重是1024, nice n-1的权重大约是nice n权重的1.25倍。

使用空闲调度策略的普通进程的权重是3, nice值对权重没有影响，定义如下：

    kernel/sched/sched.h
    #define WEIGHT_IDLEPRIO            3

完全公平调度算法使用红黑树把进程按虚拟运行时间从小到大排序，每次调度时选择虚拟运行时间最小的进程。

显然，进程的静态优先级越高，权重越大，在实际运行时间相同的情况下，虚拟运行时间越短，进程累计的虚拟运行时间增加得越慢，在红黑树中向右移动的速度越慢，被调度器选中的机会越大，被分配的运行时间相对越多。


调度器选中进程以后分配的时间片是多少呢？

调度周期：在某个时间长度可以保证运行队列中的每个进程至少运行一次，我们把这个时间长度称为调度周期。

调度最小粒度：为了防止进程切换太频繁，进程被调度后应该至少运行一小段时间，我们把这个时间长度称为调度最小粒度。默认值是0.75毫秒，可以通过文件“/proc/sys/kernel/sched_min_granularity_ns”调整。

如果运行队列中的进程数量大于8，那么调度周期等于调度最小粒度乘以进程数量，否则调度周期是6毫秒。

进程的时间片的计算公式如下：

进程的时间片=（调度周期×进程的权重 / 运行队列中所有进程的权重总和）

按照这个公式计算出来的时间片称为理想的运行时间。

5．空闲调度类

每个处理器上有一个空闲线程，即0号线程。空闲调度类的优先级最低，仅当没有其他进程可以调度的时候，才会调度空闲线程。

上一章目录下一章