Linux进程调度，从服务器到桌面

发表于 分类于

用了一周linux-ck和MuQSS，发现没有想象中的那么好。哦，这还要从一个麻醉师说起。

没仔细看调度器之前我以为Linux进程调度都是和内存管理一样很复杂的东西。实现比较简单的进程调度就几十行代码。CFS这种比较复杂的就不仔细说了、多核和分布式调度这些比较复杂的下面也不会多讲。（主要是我水平太菜了，怕讲错）

进程调度简介

进程是操作系统虚拟化出来的东西，

Linux里面基本不区分进程和线程，统称为task（任务）。下面的进程等词都指task。

CPU的资源是有限的，进程之间需要一个调度器来分配资源使用。最常见的调度器是Linux内核主线默认采用的CFS。

注：不要只盯着复杂度O(n), O(1), O(log n), 效果还是得看实测。引用一下cauche调度器readme里的一段话

O(n) sounds scary, but usually for a machine with 4 CPUS where it is used for desktop or mobile jobs, the maximum number of runnable tasks might not exceeds 10 (at the pick next run time) - the idle tasks are excluded since they are dequeued when sleeping and enqueued when they wake up.

在电脑桌面和手机、4核CPU使用场景，最多运行任务不超过10个。所以复杂度O(n)不一定比O(1)调度速度快。

关于进程

在include/linux/sched.h头文件里面有进程的定义（一个结构体来表示的task）

1
struct task_struct

Linux系统在启动的时候会首先执行start_kernel()函数init/main.c。

首先是set_task_stack_end_magic(&init_task)创建一个叫init_task的进程，一般管它叫0号进程（也就是后面的idle进程）。

然后调用sched_init();函数初始化进程调度。

然后在start_kernel()函数最后调用rest_init, 两个kernel_thread分别创建了一号进程（init）和二号进程(kthreadd)。

1
2
3
4
5
6
7
8
9
10
11
12
noinline void __ref rest_init(void)
{
  struct task_struct *tsk;
  int pid;

  rcu_scheduler_starting();
    ...........
  pid = kernel_thread(kernel_init, NULL, CLONE_FS);
  ...........
  pid = kernel_thread(kthreadd, NULL, CLONE_FS | CLONE_FILES);
  ...........
}

一般1号进程是用户态进程，整个用户态的进程树都是它fork出来的。关于1号进程的介绍可以看看systemd作者写的Rethinking PID 1 中文翻译: 重新思考 1 号进程

2号进程是内核进程，负责管理和调度内核线程。

进程描述符里面有一些调度需要的信息，比如。

初代调度器

初代调度器非常简单，就是一个runqueue（运行队列），源码在kernel/sched.c, 我们忽略掉系统调用和printk日志以及floppy之类的，只看调度部分：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
/*
 *  'schedule()' is the scheduler function. This is GOOD CODE! There
 * probably won't be any reason to change this, as it should work well
 * in all circumstances (ie gives IO-bound processes good response etc).
 * The one thing you might take a look at is the signal-handler code here.
 *
 *   NOTE!!  Task 0 is the 'idle' task, which gets called when no other
 * tasks can run. It can not be killed, and it cannot sleep. The 'state'
 * information in task[0] is never used.
 */
void schedule(void)
{
  int i,next,c;
  struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */

  for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
    if (*p) {
      if ((*p)->alarm && (*p)->alarm < jiffies) {
          (*p)->signal |= (1<<(SIGALRM-1));
          (*p)->alarm = 0;
        }
      if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&
      (*p)->state==TASK_INTERRUPTIBLE)
        (*p)->state=TASK_RUNNING;
    }

/* this is the scheduler proper: */

  while (1) {
    c = -1;
    next = 0;
    i = NR_TASKS;
    p = &task[NR_TASKS];
    while (--i) {
      if (!*--p)
        continue;
      if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
        c = (*p)->counter, next = i;
    }
    if (c) break;
    for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
      if (*p)
        (*p)->counter = ((*p)->counter >> 1) +
            (*p)->priority;
  }
  switch_to(next);
}

就只有这么几行。也没有nice值和多核，甚至没有生命周期，还是很容易理解的。

jiffies是系统开机以来tick的次数（alarm>jiffies说明过期了，重置为0）

counter是时间片，单位是tick（时钟滴答），调度器根据couter大小决定优先级（couter越大优先级越高）

NR_TASKS是task（进程）总数。

第一个循环是检查一遍alarm()函数，唤醒任何收到alarm传来的signal的没有被阻塞的tasks，将TASK_INTERRUPTIBLE（挂起）改为TASK_RUNNING可执行。

然后while(1) 这个死循环一直执行到关机，每次循环先while (--i)找出counter（时间片）最大的task。（couter越大说明）

if (c) break;和下面的这些是说如果c为0（所有进程的counter用完了），就重新分配counter。

最后调用switch_to(next)切换进程。（切换到counter最大的一个）

然后还有几个函数，是几个状态的转换，也很简单。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
int sys_pause(void)
{
  current->state = TASK_INTERRUPTIBLE;
  schedule();
  return 0;
}

void sleep_on(struct task_struct **p)
{
  struct task_struct *tmp;

  if (!p)
    return;
  if (current == &(init_task.task))
    panic("task[0] trying to sleep");
  tmp = *p;
  *p = current;
  current->state = TASK_UNINTERRUPTIBLE;
  schedule();
  if (tmp)小
    tmp->state=0;
}

void interruptible_sleep_on(struct task_struct **p)
{
  struct task_struct *tmp;

  if (!p)
    return;
  if (current == &(init_task.task))
    panic("task[0] trying to sleep");
  tmp=*p;
  *p=current;
repeat:  current->state = TASK_INTERRUPTIBLE;
  schedule();
  if (*p && *p != current) {
    (**p).state=0;
    goto repeat;
  }
  *p=NULL;
  if (tmp)
    tmp->state=0;
}

void wake_up(struct task_struct **p)
{
  if (p && *p) {
    (**p).state=0;
    *p=NULL;
  }
}

这个调度器复杂度是O(n)的（复杂度没啥用，因为NR_TASKS早期特别小）。只有分配的counter值作为调度优先级

0号进程的优先级是最低的（最后被调度）。在后面的调度器中0号进程根本不参与调度。

O(n)调度器

早期的调度器是和UNIX的差不多，就是O(n)调度器。

O(n)调度器是用runqueue（运行队列），和初代调度器不同的是CPU每个核都有一个runqueue。

O(1)调度器

2.6版本

O(1)调度器比较适合服务器，基本上做到了将I/O利用率最大化。

静态优先级（一般叫nice值）

CFS

CFS调度器（Completely Fair Scheduler），用的最广的一个（从2.6开始Linux内核主线默认就是他）。CFS的意思是完全公平调度器，完全公平是说每一个进程在一个周期时间内运行相同的时间。在一个生命周期T内，N个task占用CPU的时间均为$T/N$

CFS是一个红黑树实现的。是几种调度器中实现很复杂的一个调度器，源码在这里：sched_fair.c Linux Kernel Source

文档在这里：https://www.kernel.org/doc/Documentation/scheduler/sched-design-CFS.txt

调度实体sched_entity，虚拟运行时间vruntime

RT调度器

实时调度器，Real Time Scheduler。一般使用优先级队列（priority queue）实现的

进程根据优先级（priority）

实时调度器调度的实时进程的优先级通常很高（优先级0-99，不同内核可能不太一样）

非实时的进程优先级在100-139

执行ps命令可以查看优先级，PRI这一列是优先级（priority），NI这一列是NICE值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
$ps -el
F S   UID     PID    PPID  C PRI  NI ADDR SZ WCHAN  TTY          TIME CMD
4 R     0       1       0  0  80   0 - 25249 -      ?        00:00:07 systemd
1 S     0       2       0  0  80   0 -     0 -      ?        00:00:00 kthreadd
1 I     0       3       2  0  60 -20 -     0 -      ?        00:00:00 rcu_gp
1 I     0       4       2  0  60 -20 -     0 -      ?        00:00:00 rcu_par_gp
1 I     0       6       2  0  60 -20 -     0 -      ?        00:00:00 kworker/0:0H-events_highpri
1 I     0       8       2  0  60 -20 -     0 -      ?        00:00:00 mm_percpu_wq
1 S     0       9       2  0  80   0 -     0 -      ?        00:00:00 rcu_tasks_rude_
1 S     0      10       2  0  80   0 -     0 -      ?        00:00:00 rcu_tasks_trace
1 S     0      11       2  0  80   0 -     0 -      ?        00:00:08 ksoftirqd/0
1 I     0      12       2  0  80   0 -     0 -      ?        00:00:18 rcu_sched
1 S     0      13       2  0 -40   - -     0 -      ?        00:00:00 migration/0
1 S     0      14       2  0   9   - -     0 -      ?        00:00:00 idle_inject/0
1 S     0      16       2  0  80   0 -     0 -      ?        00:00:00 cpuhp/0
5 S     0      17       2  0  80   0 -     0 -      ?        00:00:00 cpuhp/1
1 S     0      18       2  0   9   - -     0 -      ?        00:00:00 idle_inject/1

多核

CPU的每个核都有一个runqueue

组调度

本来打算先跳过这一部分的，以后写cgroup的时候再说。但是这个东西对桌面的优化很重要，比如这个很老的补丁。

The ~200 Line Linux Kernel Patch That Does Wonders

Re: [RFC/RFT PATCH v3] sched: automated per tty task groups

现在Linux的调度策略比较多，不同用户通过组调度进行资源的分配和隔离。说到这里你是不是想起了cgroup，对，这个东西就是用cgroup实现的。

其他的调度器

官方不支持调度器像kernel module一样做成可插拔的，所以其他魔改的调度策略通常单独做一个内核。

适合桌面的进程调度

Linux的一些设计和参数偏向服务器、嵌入式设备等用途，毕竟普通桌面用户的意见加起来都比不上半个红帽。
IO调度没关系，反正有个SSD就完全够了，用NOOP调度甚至直接不要IO调度都没关系。
进程调度就不太行了，默认的CFS (Completely Fair Scheduler)调度非常不适合日常桌面使用。
通常服务器多是I/O密集型任务，而桌面（Desktop Enviroment，比如KDE和GNOME这种）需要快速响应（低延迟）和不断切换任务，CFS就不适合了（没法做到不断的切换优先级和抢占）。

比如编译、看视频CPU硬解码、玩游戏，负载高了之后，如果用CFS调度桌面会非常卡，极大影响体验。

好吧这不太符合Unix哲学，你在terminal里面用管道

麻醉师Con Kolivas针对桌面系统做的BFS（后来改名叫MuQSS了）

https://www.linux-magazine.com/var/linux_magazin/storage/images/media/linux-magazine-eng-us/images/news-images/cartoon-features/367908-1-eng-US/Cartoon-Features_medium.png

服务器进程调度

大多数服务器默认的CFS以及足够合适了。

https://github.com/Tencent/TencentOS-kernel#离线调度算法bt

更改进程调度

chrt更改调度策略

使用见使用chrt修改进程调度策略及优先级

内核选择

选择非官方支持的内核请谨慎，因为可能有很多不兼容的问题。没有特别需求和强迫症还是推荐使用有官方支持的内核，比如Archlinux官方源支持维护``linux（没啥特殊偏好就这个呗），linux-lts（lts版，不想天天更新内核就用这个）， linux-zen（跟AMD的zen关系不太大，主要是针对桌面的），linux-harended`（有安全加固，会牺牲一定性能）

linux这个包的调度器是CFS，大多数情况下表现都不差。（lts当然也是喽）

如果你是桌面用户，对性能和延迟有需求，可以试试linux-ck、linux-zen、linux-xanmod、linux-tgk等一堆针对桌面和性能优化的内核。linux-ck的调度器是MuQSS。xanmod的调度器可以选cauche。

我个人体验是xanmod内核的延迟最低（直接拯救了我玩空洞骑士时肉眼可见的延迟）。玩OSU音游的喜欢用linux-zen，这个包是官方维护，比较省心，xanmod延迟虽然跑分上比这个低，对延迟要求不苛刻、反应慢的，可能体验不出来太大区别。

（音游在Linux上的声音延迟应该是PulseAudio的锅，但是现在Pipewire又不稳，实际效果还不如PulseAudio,等pipewire稳定下来不知道要多久，只有打点补丁才能维持的了生活的样子。感谢这位玩家给wine-osu打的补丁Low-latency osu! on Linux）
关于游戏的题外话
Archlinux可以装gamemode和performance-tweaks（这个在chaotic-aur里面）。

xanmod实测见：XanMod’s Linux 5.10 Kernel Helping Tap Extra Performance With The AMD Ryzen 9 5900X
cuache相关讨论：https://forum.endeavouros.com/t/introducing-the-cacule-scheduler-a-cfs-replacement/13644

如果要用btrfs或者cgroups，请注意MuQSS兼容性不太好。

Archlinux直接AUR编译就行了。不过很多人换ck内核是因为老机器性能不好，找一个编译好的源（比如repo-ck）或者在别的机子上编译一个吧。

链接

https://lwn.net/Articles/720227/
https://www.linux-magazine.com/Online/News/Con-Kolivas-Introduces-New-BFS-Scheduler

为什么Linux CFS调度器没有带来惊艳的碾压效果
Linux桌面GUI系统的调度器应该怎么做才不卡顿呢？
为什么Windows/iOS操作很流畅而Linux/Android却很卡顿呢 dog250这位博主在CSDN上从2009年开始，一直在写，文章还不错（不要因为CSDN就不看啊，这是早期良心用户）。这样的稀有博主是我一直没舍得狠下心屏蔽CSDN的原因（颇有一种在垃圾坑里淘宝的感觉）

调度系统设计精要 - 面向信仰编程

http://ck.kolivas.org/

https://liquorix.net/ 这个内核是基于zen内核加了一些其他的补丁和改动（有ck补丁，但是没有MuQSS，原因I'm severely prejudiced against MuQSS, so it will continue "giving a null"., 见这里https://bugs.archlinux.org/task/56312）

The Linux Scheduler: a Decade of Wasted Cores 讲多核的

https://blog.ihypo.net/15279557709685.html

http://linuxperf.com/?p=42

https://www.cnblogs.com/hellokitty2/p/14199741.html

https://github.com/theanarkh/read-linux-0.11

http://www.wowotech.net/process_management/449.html

Linux进程调度-组调度及带宽控制