进程调度

总览

进程调度的总览图如下,当进程被标记为运行状态时,会加入到就绪队列中;队列中的调度实体(进程)维护自己的虚拟时间,该虚拟时间与就绪队列虚拟时间的差值作为红黑树的键值,将调度实体存入红黑树中,其中左下节点为键值最小的节点,最急需被调度,越向右节点的优先级越低;

调度子系统总图如下,进程调度激活有两种方式:一种是直接的,如进程打算睡眠或者其他原因放弃CPU;另一种是通过周期性机制,以固定的频率运行,不时的检测是否有必要进行进程切换;

当需要进行切换时,调度器调用调度类中实现的代理方法,从就绪队列中选取一个进程,并完成任务切换;

这里调度器本身不涉及任何进程管理,工作都会委托给调度器类(比如完全公平调度器类);

数据结构
task_struct成员

一些进程调度相关的成员如下:

调度器类

调度器类定义了一些函数,调度类实例实现这些函数,当调度放生时,会实际调用实例的调度类函数来执行具体的调度任务;

就绪队列

就绪队列是核心调度器管理活动进程的主要数据结构,每个cpu都有自身的调度队列,每个进程只出现在一个调度队列中;多个cpu同时运行一个进程是不可能的,注意,但不同cpu可以同时运行由一个进程产生的多个线程;

就绪队列中嵌入了特定调度类的子就绪队列,用于管理调度的进程;

系统中所有就绪队列都在runqueues数组中,该数组中的每个队列都对应着一个cpu,即每个cpu一个就绪队列;

调度实体

调度器可以调度比进程更一般的实体,在每个task_struct都嵌入了该实体的一个实例,所以进程是可调度的实体;

处理优先级
优先级的内核表示

用户空间可以使用nice值设置进程的静态优先级,内部会调用nice系统调用;nice值在[-20,19]之间,值越低表明优先级越高;

内核使用一个简单的数值范围[0-139]来表示内部优先级,同样是值越低,优先级越高;[0-99]范围的值专供实时进程使用,普通进程的nice值[-20,19]映射到范围[100,139];实时进程的优先级总比普通进程更高;

计算优先级

各种类型优先级的计算如下表

计算负荷权重

进程的重要性不仅由优先级指定,而且还需要考虑保存在task_struct->se.load中的负荷权重;

内核不仅维护了负荷权重本身,还维护了一组数值,用于计算被负荷权重除的结果;

一般概念为,进程每降低一个nice值,则多获得10%的cpu时间,每升高一个nice值,则放弃10%的cpu时间;为执行该策略,内核将优先级转换为权重值;

如下图所示,内核使用范围[-20,19]的每个nice值都对应一项权重值;

另外,不仅进程,就绪队列也关联到一个负荷权重,每次进程被加到就绪队列时,内核会将进程的权重值加到就绪队列的权重中;

核心调度器

调度器的实现基于两个函数:周期性调度器函数和主调度器函数;这两个函数根据现有进程的优先级分配CPU时间;

周期性调度器

周期性调度器在scheduler_tick中实现,如果系统正在活动中,内核会按照频率HZ自动调用该函数;如果没有进程在等待调度,也可以关闭调度器减少消耗;

周期性调度函数完成两个任务:

1. 管理内核中与整个系统和各个进程调度相关的统计量;

2. 激活负责当前进程调度类的周期性调度方法;

调度器实际上最终调用的是调度类实现的task_tick函数,如,完全公平调度器会在该方法中检查是否进程已经运行太长时间,以避免过程的延迟;

如果当前进程应该被重新调度,那么调度器类方法会在task_struct中设置TIF_NEED_RESCHED标志,以表示该请求,而内核会在接下来的适当时机完成该请求;

主调度器

内核中很多地方,如果要将cpu分配给与当前活动进程不同的另一个进程,都会直接调用主调度函数(schedule);在从系统调用返回之后,内核也会简称当前进程是否设置了重新调度标志TIF_NEED_RESCHED,如果设置了,内核会调用schedule;该函数假定当前活动进程一定会被另一个进程取代;

schedule函数首先确定当前就绪队列,保存当前活动进程;然后使用调度器类的函数选择下一个应该执行的进程,最后执行硬件级别的进程切换;

上下文切换

内核选择新进程之后,必须处理与多任务相关的技术细节,这些细节称为上下文切换;

上下文切换本身通过调用两个特定于处理器的函数完成:

1. switch_mm更换通过task_struct->mm描述的内存管理上下文;该工作的细节取决于处理器,主要包括加载页表,刷出地址转换后备缓冲器,向内存管理单元提供新的信息;

2. switch_to切换处理器寄存器内容和内核栈;

由于用户空间的寄存器内容会在进入核心态时保存在内核栈上,在上下文切换期间无需显示的操作;而因为每个进程首先都是从黑心态开始执行,在返回到用户空间时,会使用内核栈是哪个保存的值自动回复寄存器数据;

内核线程没有自身的用户空间内存上下文,可能在某个随机进程地址空间的上部执行;其task_struct->mm设置为NULL;从当前进程借来的地址空间记录在active_mm中;

 

本文链接:进程调度

转载声明:转载请注明来源:Linux TCP/IP Stack,谢谢!


发表评论

电子邮件地址不会被公开。 必填项已用*标注