Linux进程调度概述

进程: 进程是系统进行资源分配和调度的基本单位, 进程在运行过程中使用 CPU 的各种寄存器, 占用 CPU 计算时间(和其他资源, 如:内存,硬盘,网络等).

进程切换: 进程切换就是让当前运行的程序让出使用的 CPU 寄存器,不再分配 CPU 计算时间, 使其他进程运行以及使用 CPU 寄存器.

进程调度: Linux 通过一个进程到另一个进程的快速切换, 达到表面上看来多个进程同时执行的效果. 进程调度主要解决什么时候进行进程切换和切换成什么进程的问题.

image

进程调度需要考虑以下几个方面:

  1. 保证进程的响应速度(一个进程占用 CPU 时, 另外的进程就挂起了)
  2. CPU 高效使用(不能把时间都浪费在进程切换上)
  3. 高低优先级进程的协调(高优先级进程和低优先级进程占用 CPU 比例的问题)

时间片

时间片是分时操作系统分配给每个正在运行的进程微观上的一段CPU时间, 当进程的执行时间用完时, 系统使用调度程序停止该程序的运行, 把 CPU 分配给下一个需要运行的进程.

注:

  • 不同进程的时间片可能是不同的
  • 进程切换对进程来讲是透明的, 进程是感知不到的(对进程来讲, 进程可以认为整个系统就运行了自己一个进程).
  • 时间片在 kernel 中记录在进程描述符的counter中(Linux2.4默认为5, 换算成时间为50ms)

如何获取进程的时间片?
参考 How to know linux scheduler time slice?, 写了下面这个简单的程序来获取进程的时间片.

#include <sched.h>
#include <stdio.h>

int main(int argc, char const *argv[])
{
    if (argc != 2)
    {
        printf("%s pid\n", argv[0]);
        return 1;
    }

    int pid = atoi(argv[1]);
    struct timespec tp;
    int rv = sched_rr_get_interval(pid, &tp);
    if (rv != 0)
    {
        perror("get timeslice ");
        return 1;
    }

    printf("Timeslice: %lld.%.9lds\n", (long long)tp.tv_sec, tp.tv_nsec);
    return 0;
}

测试运行结果:

$gcc timeslice.c  -o timeslice
$sudo ./timeslice 431
Timeslice: 0.099984800s

进程优先级

nice 值: 系统中运行的每个进程都有一个优先级, 其范围从 -20 (最高优先级)到 19 (最低优先级), 这个值就是进程优先级. ( top 命令中的 NI 列就是这个值 )

  • 默认情况下, 进程的优先级是 0 ( “基本”调度优先级 )
  • 优先级比较大的进程相对优先级比较小的进程将比较频繁地被调度运行, 因此就拥有更多的进程周期
  • 优先级比较大的进程有更长的时间片初值
  • 一般用户只能降低它们自己进程的优先级别, 并限于 0 到 19 之间
  • 超级用户(root)可以将任何进程的优先级设定为任何值

进程优先级相关命令有 nice 和 renice, 例如:

  • 以指定优先级运行程序: nice -n -5 /usr/local/mysql/bin/mysqld_safe &
  • 改变运行进程的优先级: renice -5 -p 5200

使用我前面写的程序测试一下不同优先级进程的时间片:

$top
PID USER      PR  NI  VIRT  RES  SHR S %CPU %MEM    TIME+  COMMAND
   1 root      15   0 10348  680  572 S  0.0  0.0   0:01.74 init
   2 root      RT  -5     0    0    0 S  0.0  0.0   0:00.85 migration/0
   3 root      34  19     0    0    0 S  0.0  0.0   0:00.03 ksoftirqd/0

$sudo ./timeslice 3
Timeslice: 0.004999240s
$sudo ./timeslice 1
Timeslice: 0.099984800s

上面挑选了两个 NI 值不同的进程进行测试, 可见不同优先级的进程分配的时间片长度不同, 优先级高的进程时间片长一些, 能够占用更多的 CPU 时间.

Linux进程调度时机

  1. 进程状态转换的时刻:进程终止、进程睡眠
  2. 当前进程的时间片用完时(current->counter=0)
  3. 设备驱动程序
  4. 进程从中断、异常及系统调用返回到用户态时

实时进程和普通进程

实时进程和普通进程在调度中使用不同的调度算法, 前面提到的 nice 用来影响普通进程的调度.
一个程序是哪种类型的进程是通过系统调用sched_setscheduler来设置的, 这个值存在进程描述符中的 policy 变量, 其中:

  • 实时进程包括: SCHED_FIFO 和 SCHED_RR
  • 普通进程包括: SCHED_OTHER 或 SCHED_NORMAL
  • 其他类型: SCHED_BATCH(批处理进程) 和 SCHED_IDLE(后台任务, 优先级很低)

另外 sched_setscheduler 函数还可以设置用来标识实时进程优先级的量(在进程描述符中用 rt_priority 保存), 用来干预实时进程的调度.

调度算法

在上面列举到的调度时机, 系统会进行进程调度, Linux2.6 的调度方法比 Linux2.4 效率更高, 能更好的满足实时性和多处理机并行性.
下面分别说明

2.4的调度算法

核心调度程序包含以下步骤:

  1. 如果当前进程是用 SCHED_RR 方法调度, 并且时间片用完了, 将其移到队尾
  2. 遍历运行队列, 计算每个进程的 goodness (用于决定下面切换到哪个进程)
  3. 如果所有运行进程的时间片都已经用完, 重新计算所有进程时间片
  4. 切换成合适的进程( goodness 最大的那个)

注: 重新计算时间片时, 是计算所有进程的时间片, 这个时候包括睡眠的进程. 新的counter=剩余counter/2 + nice值转化为counter的值. 可以看出长期睡眠的进程会获得更大的时间片.

goodness的计算方法 (也就是上面第2步):

  • 如果该进程主动让出, 则直接返回最小值 -1 (比如程序调用 sleep)
  • 如果进程为实时进程, 返回1000+进程rt_priority
  • 如果进程为普通进程, goodness 初始值为进程counter(时间片剩余嘀嗒数)
    • 如果该 goodness 值为0, 返回0
    • 如果当前进程的内存空间为0或者就是当前的用户空间, 意味着切换的话不需要切换内存空间, goodness+1
    • 如果配置了 SMP, 并且进程上次所在 CPU 是当前 CPU, 说明不会有 Cache miss, goodness+PROC_CHANGE_PENALTY(一般为15)
    • goodness+20-nice(优先级)

从上面 goodness 的计算方法以及调度算法可以看出:

  • 实时进程有绝对的优势(基数1000), 一定会优于普通进程进行调度
  • SCHED_FIFO方法调度的进程会一直执行到结束, 除非自己让出 CPU 或者有更高优先级的进程申请运行
  • SCHED_RR方法调度的进程在时间片用完之后会让给其他进程
  • 普通进程中, 如果一个进程经常睡眠, 那么它的counter会变大, 这样在调度普通进程时会获得更高的优先级, 得以优先调度(一般为交互进程, 比如用户终端)

2.6的调度算法

2.6优于2.4的地方有:

  • 优先级不在调度器中计算, 节省时间
  • 每个 CPU 一个运行队列, 减少了锁的使用
  • SMP 亲和算法更新, 减少程序在 CPU 间的漂移

为了达到上面提到的优点, 2.6的实现方法更加复杂, 但总体原则不变, 具体可参考下面链接Linux 2.6 调度系统分析

应用

上面描述了这么多, 简单描述就是:

  • 交互进程响应快, 同类型的计算密集型的进程优先级低于交互进程
  • 如果想提升普通进程占用 CPU 的时间, 提升其 nice 值
  • 如果再想提升, 调用 sched_setscheduler 升级为实时进程
  • 如果再想提升, 调用 sched_setscheduler 增加实时进程的优先级

参考:
进程调度时机
Linux 2.4调度系统分析
Linux 2.6 调度系统分析
进程调度
学习 Linux: 进程执行优先级
基于Linux的实时系统
Linux SCHED_OTHER, SCHED_FIFO and SCHED_RR - differences
The Linux Scheduler

本文地址 Linux进程调度 转载请注明出处