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

发表于 | 0 comments | 阅读次数

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

#0x00 进程管理的任务

  • 进程能创建新的进程（通过复制现有进程）

  • 确定哪个进程能拥有 CPU

  • 接受中断并将中断导向相应的内核子系统

  • 管理时钟硬件

  • 当一个进程结束时释放其资源

  • 动态装载执行模块

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

I 进程模块的内外界面

  • 对用户进程提供了一组简单的系统调用接口

  • 对内核的其他模块提供了丰富的接口功能

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

  • 内存管理模块：当一个进程被调度时，为它建立内存映射

  • IPC 模块：bottom-half 处理使用了其中的信号量队列

  • 文件系统模块：在装载 module 时为进程调度提供实际设备的访问途径

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

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

I 进程描述符

  • task_struct （进程描述符）定义于<linux/sched.h>，其中包含：它打开的文件、进程的地址空间、挂起的信号、进程的状态……

  • 任务队列(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 时传递一些参数标志来实现：

1
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，它其中的每一项都是一种优先级形成的进程的链表，即每一条链表中的进程都有相同优先级

1
2
3
4
5
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().当某进程应该被抢占时，设置该标志；当一个优先级高的进程进入可执行态时，也会设置该标志。

用户抢占的发生

  • 从系统调用返回用户空间时

  • 从中断处理程序返回用户空间时

当内核返回用户空间时，如果 need_resched 被设置，会导致 schedule() 被调用，此时发生用户抢占

内核抢占的发生

  • 从中断程序返回内核空间时

  • 内核代码再一次具有可抢占性时

  • 如果内核中的任务显示调用 schedule()

  • 如果内核中的任务阻塞（同样也会调用schedule()）

本文的版权归作者 罗远航 所有，采用 Attribution-NonCommercial 3.0 License。任何人可以进行转载、分享，但不可在未经允许的情况下用于商业用途；转载请注明出处。感谢配合！