进程

在Linux内核中,进程一般称为任务(task), 进程的虚拟地址空间在内存管理模块中被分为用户虚拟地址空间和内核虚拟地址空间,所有的进程共享内核虚拟地址空间, 每一个进程有独立的用户虚拟地址空间. 在内核中,进程有两种特殊形式,没有使用用户虚拟地址空间的进程成为内核线程,共享用户虚拟地址空间的进程成为用户线程.

我们通常开发过程中提及的进程与线程在Linux内核中并没有明确的区别,它们都拥有数据结构task_struct作为描述符,我们通常所讲的进程与线程的区别即是否共享用户虚拟空间.

进程描述符task_struct

(task_struct数据成员较多,仅列出重要的数据成员)

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
52
53
54
55
56
57
58
59
60
61
62
63
64
65
struct task_struct {
/* ... */
/* -1 unrunnable, 0 runnable, >0 stopped: */
volatile long state; /* 进程状态位 */

/* ... */

void *stack; /* 指向内核栈 */

/* ... */

/* 优先级 */
int prio;
int static_prio; /* 普通进程的静态优先级 */
int normal_prio;
unsigned int rt_priority;

/* ... */

/* 调度策略 */
unsigned int policy;

cpumask_t cpus_mask; /* 允许进程在哪些CPU执行, cpuset相关 */

struct sched_info sched_info; /* 调度信息 */

struct mm_struct *mm; /* 内存描述符 */

struct vmacache vmacache; /* 虚拟内存管理 */

/* 进程退出相关 */
int exit_state;
int exit_code;
int exit_signal;
/* The signal sent when the parent dies: */
int pdeath_signal;

/* ... */

pid_t pid; /* 进程号 */
pid_t tgid; /* 线程组标识符 */

/* Real parent process: */
struct task_struct __rcu *real_parent; /* 指向真实父进程 */

/* ... */
char comm[TASK_COMM_LEN]; /* 进程名 */

/* Filesystem information: */
struct fs_struct *fs; /* 文件系统描述符 */

/* Open file information: */
struct files_struct *files; /* 打开的文件信息 */

/* 信号处理相关 */
struct signal_struct *signal;
struct sighand_struct *sighand;
sigset_t blocked;
sigset_t real_blocked;

/* ... */
struct thread_struct thread; /* CPU的部分状态(寄存器)保存在thread中 */

/* ... */
};

进程优先级

  • 限期进程的优先级比实时进程高,实时进程比普通用户进程优先级高
  • 限期进程的优先级是-1
  • 实时进程的优先级是1~99, 优先级数值越大,优先级越高
  • 普通进程的优先级是100~139, 优先级数值越小,优先级越高

调度策略

Linux内核支持以下调度策略:

  • 停机进程使用停机调度策略:

停机进程是优先级最高的进程,停机就是我们通常理解的使处理器停下来,做更紧急的任务.

  • 限期进程使用限期调度策略:

限期进程使用最早期限优先算法,使用红黑书把进程按照绝对截止期限从小到大排序,每次调度时选择绝对截止期限最小的进程.

  • 实时进程支持两种调度策略: 先进先出调度和轮流调度

  • 普通进程支持两种调度策略, 标准轮流分时和空闲调度

  • 处理器上的空闲进程使用空闲调度策略:

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

完全公平调度算法CFS

我们这里介绍相对重要的用户进程的调度策略: 完全公平调度策略CFS(Completely Fair Scheduler):

普通进程使用完全公平调度算法. 完全公平调度算法引入了虚拟运行时间vruntime:

1
虚拟运行时间 = 实际运行时间 * nice0 对应的权重 / 进程的权重(nice值对应的权重)
  • 实际运行时间

实际运行时间就是字面意思,进程在CPU上运行的实际时间. 每一个调度实体sched_entity都记录了进程调度开始时间点(exec_start), 实际运行时间(sum_exec_runtime), 虚拟运行时间(vruntime), 上一次时间运行时间(prev_sum_exec_runtime).

调度进程的时候,选中next, 开始记录next进程的开始运行时间点,运行结束后计算时间差即为进程的实际运行时间.

  • nice0 对应的权重

kernel/sched/core.c中定义了nice值与权重的对应关系,nice0 的值为1024.

  • 进程的权重

普通进程的nice值的取值范围是-20~19, 以下是nice值与权重的对应关系:

1
2
3
4
5
6
7
8
9
10
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值越小,进程的权重也就越大.

完全公平调度算法利用rb-tree将进程按虚拟运行时间从小到大的排序,每次调度选择虚拟运行时间最小的进程. nice0对应的权重为常量,即可以理解在实际运行时间相同的情况下,进程的权重(nice值对应的权重值)越大,被调度的机会就越大.

进程在CPU上执行的时间周期称为调度周期,内核设置了调度最小粒度,默认为0.75毫秒,可以通过文件/proc/sys/kernel/sched_min_granularity_ns调整. 假如运行队列中的进程数量大于8, 那么调度周期等于调度最小粒度 * 进程数量,否则调度周期为6毫秒.

进程的时间片公式如下:

进程的时间片 = (调度周期 * 进程权重 / 运行队列中所有进程的权重总和)

进程调度

运行队列

每一个处理器都有一个运行队列,定义如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
/* kernel/sched/sched.h */

struct rq {
/* runqueue lock: */
raw_spinlock_t lock; /* 运行队列的锁 */

unsigned int nr_running; /* 运行队列的进程数量 */

/* ... */
struct cfs_rq cfs; /* 公平运行进程队列 */
struct rt_rq rt; /* 实时运行进程队列 */
struct dl_rq dl; /* 限期运行进程队列 */

/* ... */
struct task_struct *curr; /* 正在运行的进程 */
struct task_struct *idle; /* 空闲进程 */
struct task_struct *stop; /* 迁移进程 */

/* ... */
};

调度进程

调度进程的核心函数是__schedule, 函数__schedule()的处理流程如下:

  • 调用pick_next_task()以选择下一个进程
  • 调用context_switch()以切换进程

pick_next_task()

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
static inline struct task_struct *
pick_next_task(struct rq *rq, struct task_struct *prev, struct rq_flags *rf)
{
/* sched_class是Linux抽象的调度类,类别和优先级分别如下:
* 停机调度类,限期调度类,实时调度类,公平调度类和空闲调度类. */
const struct sched_class *class;
struct task_struct *p;

/* 假如所有进程属于公平调度类,
* 我们可以直接调用公平调度类的pick_next_task函数. */
if (likely((prev->sched_class == &idle_sched_class ||
prev->sched_class == &fair_sched_class) &&
rq->nr_running == rq->cfs.h_nr_running)) {

p = fair_sched_class.pick_next_task(rq, prev, rf);
/* 假如没有可调度的进程,跳转again, 选择其他优先级的调度类. */
if (unlikely(p == RETRY_TASK))
goto again;

/* 假如公平调度类选择的下一个进程属于空闲调度类,直接调用
* 空闲调度类的pikc_next_task(). */
if (unlikely(!p))
p = idle_sched_class.pick_next_task(rq, prev, rf);

return p;
}

again:
/* 迭代调度类,从优先级最高的调度类开始,调用对应的pick_next_task
* 选择下一个进程,假如没有可以调度的进程,就选择一个优先级的调度类. */
for_each_class(class) {
p = class->pick_next_task(rq, prev, rf);
if (p) {
if (unlikely(p == RETRY_TASK))
goto again;
return p;
}
}

/* 正常的情况下,不会走到这里,因为空闲调度类总会有可以调度的进程. */
BUG();
}

用户进程属于公平调度类,即调用pick_next_task_fair()选择下一个运行的进程, 公平调度类会从当前cfs_rq即公平调度运行队列中选择虚拟运行时间最小的调度进程,所有的调度进程都由rb-tree(红黑树)维护.

context_switch()

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
/* linux/kernel/sched/core.c */

static __always_inline struct rq *
context_switch(struct rq *rq, struct task_struct *prev,
struct task_struct *next, struct rq_flags *rf)
{
struct mm_struct *mm, *oldmm;

/* 执行进程切换的准备工作,ARM64架构为默认定义: 一个空的宏. */
prepare_task_switch(rq, prev, next);

/* mm为下一个选择的进程的内存描述符,
* old_mm为上一个进程的内存描述符. */
mm = next->mm;
oldmm = prev->active_mm;
/* 开始执行上下文切换,ARM64架构依旧使用默认定义,是一个空的宏. */
arch_start_context_switch(prev);

if (!mm) {
/* 假如mm为空, 即下一个选择的进程为内核线程,
* 内核线程没有用户虚拟地址空间, 所以需要借用上一个进程的mm_struct,
* 调用enter_lazy_tlb()通知处理器架构不需要切换用户虚拟地址空间. */
next->active_mm = oldmm;
mmgrab(oldmm);
enter_lazy_tlb(oldmm, next);
} else
/* 否则需要进行切换进程的地址空间. */
switch_mm_irqs_off(oldmm, mm, next);

/* ... */

/* 切换寄存器和堆栈. */
switch_to(prev, next, prev);
barrier(); /* 内存屏障 */

/* finish_task_switch负责进程切换后执行的清理工作. */
return finish_task_switch(prev);
}

用户虚拟地址空间切换

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
/* switch_mm_irqs_off() -> switch_mm() -> __switch_mm() */

/* arch/arm64/include/asm/mmu_context.h */

static inline void __switch_mm(struct mm_struct *next)
{
unsigned int cpu = smp_processor_id();

/*
* init_mm.pgd does not contain any user mappings and it is always
* active for kernel addresses in TTBR1. Just set the reserved TTBR0.
*/
if (next == &init_mm) {
cpu_set_reserved_ttbr0();
return;
}

check_and_switch_context(next, cpu);
}

static inline void
switch_mm(struct mm_struct *prev, struct mm_struct *next,
struct task_struct *tsk)
{
if (prev != next)
/* 假如切换的两个进程不共享虚拟地址空间,
* 调用__switch_mm()进行切换. */
__switch_mm(next);

/* 更新TTBR0寄存器 */
update_saved_ttbr0(tsk, next);
}

寄存器和堆栈切换

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
/* switch_to() -> __switch_to() */

/* arch/arm64/kernel/process.c */

__notrace_funcgraph struct task_struct *__switch_to(struct task_struct *prev,
struct task_struct *next)
{
struct task_struct *last;

fpsimd_thread_switch(next); /* 切换浮点寄存器 */
tls_thread_switch(next); /* 切换线程本地存储相关的寄存器 */
hw_breakpoint_thread_switch(next); /* 切换调试寄存器 */
contextidr_thread_switch(next); /* 切换上下文标识符寄存器 */
entry_task_switch(next); /* 将下一个进程的task_struct存入CPU的__entry_task */
uao_thread_switch(next); /* 用户访问覆盖相关切换 */
ptrauth_thread_switch(next); /* 指针验证相关切换 */
ssbs_thread_switch(next); /* 推测性执行侧通道相关切换 */

/* 数据同步屏障 */
dsb(ish);

/* 切换通用寄存器 */
last = cpu_switch_to(prev, next);

return last;
}

进程切换与线程切换

通过上面的系统的分析,我们可以发现在Linux内核中并没有区分进程和线程,对于线程和进程,我们可以这么理解:

  • 当进程只有一个线程时,可以认为进程就等于线程.
  • 当进程拥有多个线程时,这些线程会共享相同的虚拟地址空间, 虚拟地址空间在上下文切换时是不需要切换的。另外,线程也有自己的私有数据,比如栈和寄存器等,这些在上下文切换时也是需要切换保存的.

查看进程上下文切换

我们通常所说的上下文切换分为CPU上下文切换和进程上下文切换, 例如C/C++中的系统调用即会执行CPU上下文切换,而系统性能分析工具vmstat所显示的也是 CPU 上下文切换和中断的次数. 关于进程上下文切换我们可以利用工具 pidstat:

每隔5秒输出1组数据

pidstat

这个结果中有两列内容是我们的重点关注对象。一个是 cswch ,表示每秒自愿上下文切换(voluntary context switches)的次数,另一个则是 nvcswch ,表示每秒非自愿上下文切换(non voluntary context switches)的次数. 所谓自愿上下文切换,是指进程无法获取所需资源,导致的上下文切换。比如说, I/O、内存等系统资源不足时,就会发生自愿上下文切换。而非自愿上下文切换,则是指进程由于时间片已到等原因,被系统强制调度,进而发生的上下文切换。比如说,大量进程都在争抢 CPU 时,就容易发生非自愿上下文.

调度时机

调度进程的时机如下:

  • 进程主动调用schedule()函数.
  • 周期性调度,抢占当前进程,强迫当前进程让出处理器.
  • 唤醒进程的时候,被唤醒的进程可能会抢占当前进程.
  • 创建新进程的时候, 新进程可能抢占当前进程.

主动调度

进程在用户模式下运行的时候,无法直接调用schedule()函数, 只能通过系统调用进入内核模式,假如系统调用需要等待某个资源,例如互斥锁(mutex)或者信号量,会将进程的状态设为睡眠状态,然后调用schedule()来调度进程.

进程也可以通过系统调用sched_yield()让出处理器,这种情况下进程不会进入睡眠.

周期性调度

Linux内核依靠周期性的时钟中断抢夺处理器的控制权,时钟中断处理程序检查当前进程的执行时间有没有超过限额,如果超过了限额,设置需要重新调度的标志.

在CFS算法中,如果当前调度实体的运行时间超过了前面介绍的进程的时间片,那么会设置重新调度的标志位.

修改进程优先级

  • Linux系统可以通过renice设置进程优先级,具体使用方法可以通过man renice.

  • C/C++编程可以使用以下方法:

1
2
3
4
5
#include <sys/time.h>
#include <sys/resource.h>

int getpriority(int which, int who);
int setpriority(int which, int who, int prio);

参考

  • <<Linux内核深度解析>>