进程

在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 权重 / 进程的权重

实际运行时间

进程调度

运行队列

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

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()

参考

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