转载

读薄「Linux 内核设计与实现」(2) - 进程管理和调度

这篇文章是《读薄「Linux 内核设计与实现」》系列文章的第 II 篇，本文主要讲了以下问题：进程管理的任务、进程管理与其他模块的依赖关系、进程描述符和任务队列、进程的创建、线程的实现、进程的终止、进程调度。

0x00 进程管理的任务

进程能创建新的进程（通过复制现有进程）
确定哪个进程能拥有 CPU
接受中断并将中断导向相应的内核子系统
管理时钟硬件
当一个进程结束时释放其资源
动态装载执行模块

0x01 进程管理与其他模块的依赖关系

I 进程模块的内外界面

对用户进程提供了一组简单的系统调用接口
对内核的其他模块提供了丰富的接口功能

II 进程模块与其他模块的依赖关系

内存管理模块：当一个进程被调度时，为它建立内存映射
IPC 模块：bottom-half 处理使用了其中的信号量队列
文件系统模块：在装载 module 时为进程调度提供实际设备的访问途径

所有其他模块都依赖于进程调度模块，因为当要进行硬件访问时，它们需要 CPU 挂起用户进程，切换到系统态进行处理

0x02 进程描述符和任务队列

I 进程描述符

task_struct （进程描述符）定义于，其中包含：它打开的文件、进程的地址空间、挂起的信号、进程的状态……
任务队列( task_list )是一个双向循环链表，每一项都是 task_struct

II 分配进程描述符

Linux 通过 slab 分配 task_struct 可以达到对象复用和缓存着色的目的，不需要频繁调用内存管理相应功能，相当于一种高级缓存

III 进程描述符的存放

通过 PID 标识进程，最大值默认为32768
如何获得当前运行的进程？

通过 current 宏（体系结构相关）， current_thread_info()->task;

0x03 进程的创建

I 进程创建过程描述

Linux 中，进程的创建是通过拷贝已存在的进程来实现的
内核启动的时候， start_kernel() 初始化各系统数据结构，同时生成了与系统共存亡的后台进程：init
这些子进程通过 fork() 系统调用生成他们的子进程
进程的终止是通过系统调用 _exit() 实现的

II 进程创建函数

fork(): 进程复制自身产生子进程
exec(): 加载可执行代码模块覆盖自身代码

III 写时拷贝(copy-on-write)

使地址空间上的页的拷贝被推迟到实际发生写入的时候才进行

0x04 线程的实现

Linux 没有真正的线程，线程当做进程来实现（仅仅是进程间资源直接共享的一种机制）
通过 clone 时传递一些参数标志来实现：

clone(CLONE_VM | CLONE_FS | CLONE_FILES | CLONE_SIGHAND, 0);

这些标志定义于 <linux/sched.h>

内核线程：独立运行在内核的标准进程

0x05 进程的终止

删除进程描述符

父进程得知进程终止的消息后才能删除子进程的描述符
父进程 WAIT() （通过系统调用 wait4() 实现），挂起父进程，直到其中一个子进程退出
之后，真正释放描述符（ release_task() ）:
- 调用 _unhash_process() 从 pidhash 上删除该进程
- _exit_signal() 释放目前僵死进程所使用剩余资源
- 调用 put_task_struct 释放描述符（内核栈、thread_info 所占的页、slab 高速缓存）

若父进程异常终止，将发生什么情况？

如果父进程在子进程之前推出，这些成为孤儿的进程会处于僵死状态，解决方案是给子线程在当前进程中找一个父亲，如果不行，则以 init 进程为父亲，过程：

do_exit() -> exit_notify() -> forget_original_parent() -> find_new_reaper()

开始寻父。

0x06 进程调度

I 多任务系统分类

抢占式：由调度程序决定一个进程的运行与挂起，挂起的动作就叫做抢占（Linux 为抢占式内核），进程在被抢占之前的运行时间是预先设置好的，叫做时间片
非抢占式：除非进程自己停止，否则它会一直运行，它主动挂起自己的动作叫让步（yielding）

II 调度策略

I/O 消耗型和 CPU 消耗型进程

I/O 消耗型：进程大部分时间用来提交 I/O 请求或是等待 I/O 请求
CPU 消耗型：进程把时间大多用在执行代码上

UNIX 系列倾向于 I/O 消耗型

进程优先级(Linux 采用2种不同的优先级范围)

nice 值：从 -20~+19，默认为0，nice 越大，优先级越低
实时优先级：从 0~99，越高的实时优先级越高，它的值可以配置

时间片

时间片分配多大？：时间片过长使得系统交互性不好；时间片过短会导致大部分 CPU 时间浪费在进程的切换上。
Linux 采用可变长的时间片

III Linux 调度算法

O(1) 调度

优先级数组

O(1)调度算法中的一个核心数据结构即为 prio_array 结构体，该结构体中有一个用来表示进程动态优先级的 queue，它其中的每一项都是一种优先级形成的进程的链表，即每一条链表中的进程都有相同优先级

struct prio_array{     unsigned int nr_active;     unsigned long bitmap[BITMAP_SIZE];     struct list_head queue[MAX_PRIO]; }

另外，该结构体中还包含一个优先级位图 bitmap，该位图使用1位来表示1种优先级，开始时，所有位置都置0，一旦有进程处于可运行状态时，该进程所在优先级对应位图中的相应位被置1.

因此，在 O(1)调度中查找最高的优先级就转化为查找优先级位图中第一个被置1的位

确定了最高优先级之后，选取下一个进程就是在 queue 对应的链表中取一个进程即可

活动进程和过期进程

在 O(1)调度中，对可运行态的进程分了两类：一类为 活动进程 ，即时间片还未用完的进程；另一类为 过期进程 ，即时间片已经用完的进程，但进程还未结束，它们没有机会得到执行。

在可运行队列结构中（runqueue）的 arrays 的两个元素分别来表示上述两个集合， active 和 expire 两个指针分别指向这2个集合

时间片的计算

active 中的进程一旦时间片使用完毕就会放入 expire 中，并设置好新的时间片；当 active 为空时，说明所有进程时间片已耗尽，此时，将 active 和 expire 对调，重新开始下一轮时间片的递减过程。

O(1)算法中的两个核心

选择下一个进程
时间片的重新分配

CFS 调度（公平调度）

O(1)算法是根据进程的优先级进行调度的；CFS 是根据进程的虚拟进程运行时间来进行调度的

如何选择进程?

CFS 提出了虚拟运行时间的概念（vruntime），vruntime 记录了一个 可执行进程到当前时刻为止执行的总时间 ，vruntime 越大，它被调度的可能性越小，因此每次选择 vruntime 越小的进程进行调度（在 Linux 中使用红黑树来找出 vruntime 最小的进程）

调度进程的运行时间

现在已经知道了进程是如何调度的，那么当进程运行时，它的运行时间是多少呢？

CFS 的运行时间是由当前所有可调度进程优先级比重来确定的

例：3个进程优先级为5，15，20，它们时间片大小分配为：5/40, 15/40, 20/40

IV 抢占和上下文切换

上下文切换表示从一个可执行进程切换到另一个可执行进程（定义在 sched.h 中的 context_switch()）

调用 switch_mm() ：把虚拟进程从一个进程切换到新进程
调用 switch_to() ：保存和恢复栈信息、寄存器信息
need_resched 标志：每个进程都包含该标志，为了让内核知道在什么时候调用 schedule() .当某进程应该被抢占时，设置该标志；当一个优先级高的进程进入可执行态时，也会设置该标志。