进程管理

进程数据结构

进程的数据结构是task struct

  1. cpu资源:
    1. 调度优先级
  2. 内存地址空间资源:
    1. mm_struct
  3. 打开的文件资源:
    1. file_struct files (一个数组, 存的就是打开的文件的地址, 索引即是文件描符 fd)

进程自己的信息与状态

  1. 进程状态: 存储在task->state, task->exit_state两个字段中
    1. 如TASK_RUNNING, TASK_INTERRUPTIBLE, TASK_UNINTERRUPTIBLE, __TASK_STOPED…
  2. 唯一ID
    1. pid: 线程级别的id
    2. gtid: 进程级别的id
  3. 文件系统信息 struct fs_struct *fs
  4. namespace
  5. 进程树关系: 该进程在整个进程树里面的位置

进程的状态

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/* Used in tsk->state: */
#define TASK_RUNNING            0x00000000
#define TASK_INTERRUPTIBLE      0x00000001
#define TASK_UNINTERRUPTIBLE    0x00000002
#define __TASK_STOPPED          0x00000004
#define __TASK_TRACED           0x00000008
/* Used in tsk->exit_state: */
#define EXIT_DEAD               0x00000010
#define EXIT_ZOMBIE             0x00000020
/* Used in tsk->state again: */
#define TASK_DEAD               0x00000080

/* 组合状态（便利宏）: */
#define TASK_KILLABLE           (TASK_WAKEKILL | TASK_UNINTERRUPTIBLE)
#define TASK_STOPPED            (TASK_WAKEKILL | __TASK_STOPPED)
#define TASK_IDLE               (TASK_UNINTERRUPTIBLE | TASK_NOLOAD)
#define TASK_NORMAL			(TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE)
// ...

常见状态语义说明:

存储在task->state的

  • TASK_RUNNING: 进程正在运行队列中, 准备运行/正在运行
  • TASK_NORAML/TASK_INTERRUPTIBLE/TASK_UNINTERRUPTIBLE:
    • TASK_NORMAL = (TASK_INTERRUPTIBLE | TASK_UNINTERRUPTIBLE) 是这两个状态的综合, 表明进程正在睡眠
    • TASK_INTERRUPTIBLE: 进程处于可打断的睡眠状态, 正在等待某个条件满足, 被wake_up唤醒, 或者被信号唤醒. 不会被计入load average
    • TASK_UNINTERRUPTIBLE: 进程处于不可中断的睡眠状态, 只能在条件满足时, 被wake_up唤醒, 不能被信号唤醒, 常用于(如磁盘 I/O)等不能被中途打断的SLEEP, 这也代表, 在这个状态的进程的数量能一定程度反应当前计算机的物理负载, 这个状态会被计入load average
    • TASK_KILLABLE = (TASK_WAKEKILL | TASK_UNINTERRUPTIBLE) 可以被致命信号杀死(SIGKILL)的不可中断睡眠
    • __TASK_STOPPED = 进程被暂停执行了, 不会被调度. 1. 收到SIGSTOP / SIGSTP / SIGTTIN / SIGTTOU 信号 2. ptrace attach 后发送 SIGSTOP. 常见的进入情景: 1. Ctrl + z 2. debug. 退出的时机: 收到 SIGCONT 信号
    • __TASK_TRACED = 进程正在被调试器跟踪
    • TASK_IDLE (TASK_UNINTERRUPTIBLE | TASK_NOLOAD):
      • 语义: TASK_UNINTERRUPTIBLE类似的不可中断睡眠, 但不计入 load average
      • 内核中空闲时会运行的 idle线程, 内核中某些无关紧要的等待
      • 如果 idle线程用TASK_UNINTERRUPTIBLE而包含TASK_NOLOAD会导致load average空长, 不能反应真实物理资源负载

存储在task->exit_code的

  • EXIT_ZOMBIE: 僵尸状态
    • 语义: 代码已经执行完毕
    • 进入的时机: 进程调用exit() -> do_exit() -> exit_notify() 中设置 tsk->exit_state = EXIT_ZOMBIE
    • 退出的时机: 父进程调用 wait / waitpid() 读取退出状态 -> wait_task_zombie() -> exit_state中改为 EXIT_DEAD -> task_struct 被释放
  • EXIT_DEAD (0x10) : 彻底死亡
    • 语义: 进程的task_struct正在被回收或者已经被回收
    • 进入的时机: 父进程 wait() 成功后, 状态从 EXIT_ZOMBIE 变成 EXIT_DEAD
    • 退出的时机: 这是一个瞬态, 存在的时间极短, 之后 task_struct 被回收

常见的进程类型

  • 僵尸进程: 进程(task_struct)已经被释放, 但是还保留PID和exit_state为EXIT_ZOMBIE

    • 为什么需要这个状态: 父进程可能需要在进程被关闭以后, 获取进程的PID并检查它的退出码来衡量进程是不是正常退出的
    • 资源泄漏: 状态为EXIT_ZOMBIE的进程占用一个PID和少量的内核内存. 如果大量堆积, 会导致内核内存泄漏, 或PID耗尽
    • 怎么产生的: 父进程没有调用wait()或者waitpid()
    • 解决方式:
      • 父进程调用 wait() / waitpid()
      • 设置 signal(SIGCHLD, SIG_IGN) 让内核自动回收 (do_notigy_parent返回true的时候直接设置状态为EXIT_DEAD)
      • 杀死父进程 -> 僵尸被init(PID=1)收养 -> init会自动 wait()清理

  • 孤儿进程: 进程的父进程先于子进程被杀死了, 子进程就成为了孤儿进程

    • 内核会将孤儿进程的父进程指向init, 或者当前 PID namespace 中的 subreaper 进程, init进程会定期调用 wait()来清理
    • 本身是正常的, 不会造成问题

  • 守护进程: 在后台运行的, 不再与任何终端关联的长期运行的进程. 如 sshd, nginx等

    • 不是一个内核概念, 而是一个用户空间的编程的概念
    • 经典的创建过程: double-fork
      • fork() - 创建子进程
      • 父进程退出 - 子进程被托孤给init
      • setsid - 创建新的session (和原终端解绑)
      • 再次 fork() - 确保不会重新获得中断控制能力
      • chdir(“/) - 避免占用可卸载的文件系统
      • 关闭/重定向 stdin/stdout/stderr

进程的唯一ID

tgid和pid, 为什么要有两个ID
经典的用途是区分进程和线程, 本身是进程组概念, 父进程和他fork出来的子进程组成一个进程组, 共享一个tgid.
他们的id (pid, tgid)会是 (1, 1), (2, 1), (3, 1). 对于操作系统来说, 只有进程这个概念, 线程实际上是一个轻量级进程, 对于操作系统的调度来说, 进程和线程是同等地位的实体, 唯一通过PID来作为唯一标识, 而tgid是标识”进程”而非”线程”的唯一标识.

进程树

通过 task_struct 中的 parent/real_parent、children/sibling 字段, 所有进程构成一棵多叉双向树. Linux 使用侵入式链表(list_head)而非传统多叉树来实现, 使得增删 O(1)、零内存分配、API 全内核复用.

进程树支撑了 wait() 回收、托孤、SIGCHLD 通知等核心操作. 进程树与进程组(PGID)、会话(Session) 共同构成了完整的作业控制体系.

详细内容: 进程树

进程调度

运行队列 struct rq

内核声明了一个per-CPU变量: runqueues, 每个CPU都有自己的rq变量, 通过cpu_rq(cpu)等宏能执行拿到第N号CPU的运行队列指针等操作.

1
2
3
4
5
6
7
DECLARE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

#define cpu_rq(cpu)		(&per_cpu(runqueues, (cpu)))
#define this_rq()		this_cpu_ptr(&runqueues)
#define task_rq(p)		cpu_rq(task_cpu(p))
#define cpu_curr(cpu)		(cpu_rq(cpu)->curr)
#define raw_rq()		raw_cpu_ptr(&runqueues)

这个数据结构嵌入了cfs_rq, rt_rq, dl_rq三个内部运行队列(注意这里是嵌入, 这三个字段不是指针). 这意味着 rq本身就包含了所有调度类各自的运行队列数据. 每个调度类管自己的调度队列.

1
2
3
4
5
6
7
8
9
10
11
12
13
struct rq {
	raw_spinlock_t		__lock; // 自旋锁, 保护整个队列的并发访问

	struct task_struct __rcu	*curr; // 当前正在运行的进程

	struct cfs_rq		cfs; // cfs rq, 完全公平调度队列, 直接嵌入
	struct rt_rq		rt; // real time rq, 实时调度队列, 直接嵌入
	struct dl_rq		dl; // deadline rq, 强实时调度队列, 有完成截止时间, 直接嵌入

	unsigned int		nr_running; // 一个CPU上最多有多少进程可以是running状态
	u64			nr_switches; // 上下文切换的次数
  // 其他...
}

调度类 - struct sched_class

调度类本身是一个虚函数表, 里面定义了一系列的虚函数(接口), 里面的各个函数实际上是函数指针. 可以把调度类就看作是一个interface/vitrual class.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
struct sched_class {
  // 把一个进程加入到该调度类的子队列
	void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
  // 新进程唤醒的时候, 检查是否应该要抢占当前进程
	void (*check_preempt_curr)(struct rq *rq, struct task_struct *p, int flags);
  // 把一个进程移除到该调度类的子队列
	void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);

  // 从该调度类中选出下一个要运行的进程
	struct task_struct *(*pick_next_task)(struct rq *rq);

  // 当前进程被换下前的清理工作, 比如对于cfs调度器来说, 就会重新计算vruntime, 然后重新放回cfs.timeline(红黑树)里面
	void (*put_prev_task)(struct rq *rq, struct task_struct *p);
  // 新进程被换上前的初始化工作
	void (*set_next_task)(struct rq *rq, struct task_struct *p, bool first);

  // 每个时钟tick时被调用, 检查时间片/vruntime
	void (*task_tick)(struct rq *rq, struct task_struct *p, int queued);
  // 更新当前进程的运行时间
  void (*update_curr)(struct rq *rq);
}

调度类的实现类有五个

  1. stop_sched_class
  2. dl_sched_class
  3. rt_sched_class
  4. fair_sched_class
  5. idle_sched_class

这五个类实现了上面的各个函数, 使用不同的策略和子队列.
每个task_struct里面都一个sched_class字段, 指向这个进程对应的调度类全局实例(看成是静态类即可)

在rq挑选下一个任务的时候, 会按照上面的顺序遍历所有的调度类, 尝试调用他们各自的pick_next_task.
如果调度到的不是NULL, 返回找到的任务.

调度的整体运行流程

rq是容器, sched_class是行为, 子队列 (cfs_rq, rt_rq, dl_rq) 是各调度类在容器内的私有存储队列. 三者通过task_struct.sched_class桥接

1. 进程入队: 从唤醒到进入到子队列里面

1
2
3
4
try_wake_up(task_struct* p)
  -> activate_task(rq, p, flags)
    -> enqueue_task(rq, p, flags)
      -> p->sched_class->enqueue_task
  • 如果这里的进程是普通的进程, 这里的p->sched_class就是fair_sched_class, p->sched_class->enqueue_task最后调用的就是enqueue_task_fair(), 这个函数会将p插入到cfs rq中的红黑树子队列中
  • 如果p是RT进程, 实际调用的就是enqueue_task_rt()

2. 进程出队: 睡眠或退出

__schedule()
-> deactivate_task(rq, prev, DEQUEUE_SLEEP)
-> dequeue_task(rq, prev, flags)
-> p->sched_class->dequeue_task(rq, p, flags)

3. 选择下一个进程: pick_next_task的两条路径

这里的pick_next_task并不是调度类里面的这个函数, 而是sched.h里面的一个文件

__scheduler()
-> pick_next_task(rq, prev, &rf)
-> __pick_next_task(rq, prev, rf)

快速路径

rq->nr_running == rq->cfs.h_nr_running ? (全部进程都是normal/CFS进程)
-> pick_next_task_fair(rq, prev, rf)
-> 从rq->cfs.tasks_timeline 取出来最左边的节点

慢速路径

for_each_class(class)
class->pick_next_task(rq)
-> stop_sched_class.pick_next_task(rq) -> 检查 rq->stop
-> dl_sched_class.pick_next_task(rq) -> 检查 rq->dl 红黑树
-> rt_sched_class.pick_next_task(rq) -> 检查 rq->rt 优先级数组
-> fair_sched_class.pick_next_task(rq) -> 检查 rq->cfs 红黑树
-> idle_sched_class.pick_next_task(rq) -> 返回 rq->idle（兜底）

for_each_class是一个宏, 会遍历所有的sched_class, 尝试调用每个调度类自己实现的pick_next_task, 直到返回的不是NULL, 返回. 这样就构造出来了不同rq/调度器之间的优先级问题.

将task_struct挂载在运行队列上

这里主要聚焦的是, rq中的子队列, 比如cfs, 是把task_struct直接存在里面的吗, 是怎么挂载上去的?

1
2
3
4
5
6
struct task_struct{
	struct sched_entity		se;
	struct sched_rt_entity		rt;
	struct sched_dl_entity		dl;
	const struct sched_class	*sched_class;
}

同样是侵入式数据结构设计, 通过将这几个嵌入式的字段挂载在task_struct中, 通过container_of来取出task_struct.
同时rb_node嵌入到sched_entity中, 来将这个数据结构挂在红黑树上

为什么不直接操作task_struct呢?

在cgroup分组调度下, CFS需要把“一组进程”当成一个整体来调度, sched_entity可以代表一个进程, 也可以代表一个进程组.

1
2
3
4
5
6
7
8
9
10
11
12
struct sched_entity {
	struct load_weight		load; // 该实体的权重, 通过nice值转化出来的, CFS通过这个计算出来应该分到多少CPU时间
	struct rb_node			run_node; //  红黑树节点, 挂在rq.cfs_rq->task_timeline上
	struct list_head		group_node; // 挂在rq->cfs_tasks链表上, 用于SMP均衡负载
	unsigned int			on_rq; // 是否在运行队列里面

	u64				exec_start; // 当前这一轮开始执行的时间戳, 每次tick或调度的时候更新
	u64				sum_exec_runtime; // 累计实际的运行时间
	u64				vruntime; // 虚拟运行时间, 值越小越优先被选中
	u64				prev_sum_exec_runtime; // 上次调度时候实际运行时间的快照, 用来算, 这次用了多少的时间片
	u64				nr_migrations; // 这个entity被迁移到其他的cpu上的次数
};

sched_entity 是 CFS 调度器的操作单元，嵌入在 task_struct.se 中。它通过 run_node 挂在 cfs_rq 的红黑树上，以 vruntime 为排序键。CFS 选人就是取 vruntime 最小的 sched_entity，再通过 container_of 反推到 task_struct。分组调度下，一个 sched_entity 可以代表整个 task_group，通过 parent/cfs_rq/my_q 构成层级树。