转载

读薄「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 的两个元素分别来表示上述两个集合, activeexpire 两个指针分别指向这2个集合

时间片的计算

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

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 。任何人可以进行转载、分享,但不可在未经允许的情况下用于商业用途;转载请注明出处。感谢配合!

原文  http://blog.luoyuanhang.com/2016/06/23/lkd-thin-02/
正文到此结束
Loading...