源码分析之深入理解Linux进程调度

其实本文也是深入理解Linux内核的读书笔记后续

调度基础

很多书中将进程分为CPU密集型和I/O密集型,另外还有一种分法:

  • 交互式进程
    这些进程与用户进行交互,因此会花很多时间等待鼠标键盘的输入,当接受输入之后,必须很快得到相应,否则系统会显得很迟钝。
  • 批处理进程
    不必与用户交互,常运行于后台。
  • 实时进程
    典型的是视频音频应用程序、机器人控制程序等,这些进程有很强的调度需要,不应该被低优先级的进程阻塞,应该有很短的响应时间。

Linux中调度算法可以明确所有实时程序的身份,但没法区分交互式程序和批处理程序。Linux实现了基于进程过去行为的启发式算法以确定进程应被当作交互式进程还是批处理进程,相比批处理进程,调度程序偏爱调度交互式进程。

Linux2.6实现了一个O(1)的调度程序,本博文主要就是要介绍这个算法,Linux将进程分为下面三种:

  • SCHED_FIFO
    先进先出的实时进程,如果没有其他更高优先级的实时进程,进程可以继续使用CPU,想用多久用多久。
  • SCHED_RR
    时间片轮转的实时进程。
  • SCHED_NORMAL
    普通的分时进程。

不同的进程对应的调度算法有很大的区别。

普通进程的调度

每个普通进程都有自己的静态优先级,内核用从100(最高优先级)到139(最低优先级)的数来表示普通进程的静态优先级。新进程总是继承父进程的静态优先级,用户可以改变自己拥有进程的静态优先级,通过nice()和setpriority()。

静态优先级的本质上决定了进程的基本时间片,静态优先级和基本时间片的关系用下面的公式确定:

基本时间片(ms) = (140 – 静态优先级) X 20   若静态优先级<120
基本时间片(ms) = (140 – 静态优先级) X 5     若静态优先级>=120

普通进程除了静态优先级还有动态优先级,其值范围是100~139,动态优先级是调度程序在选择新进程来运行时使用的数,它与静态优先级的关系如下:

动态优先级=max(100, min(静态优先级 – bonus + 5, 139))

bonus是范围从0~10的值,值小于5表示降低优先级以示惩罚,值大于5表示增加优先级以示奖赏。bonus的值依赖于进程的平均睡眠时间。

Linux使用平均睡眠时间来确定进程时交互式进程还是批处理进程,如果满足下面的公式则被看做是交互式进程,否则为批处理进程。

动态优先级<= 3 X 静态优先级 / 4 + 28
即  bonus – 5 >= 静态优先级/4 – 28

另外,表达式 静态优先级/4 – 28 被称为交互式的δ。基本上可以理解成将睡眠时间较长的进程可以看做交互式进程(因为一直在等待I/O)。

为了使低优先级的进程也能够被CPU调度,以免总被高优先级的进程饿死,当一个进程用完它的时间片后,应该被还没用完时间片的低优先级进程取代,为了实现这这种机制,调度程序维护两个不想交的可运行进程的集合。

  • 活动进程
    这些进程的时间片还没用完,因此允许运行。
  • 过期进程
    这些可运行进程的时间片已经用完,因此被禁止运行,直到所有活动进程都过期。

不过因为调度程序试图提升交互式进程(并不一定是优先级高,而是睡眠时间相对较多的进程)的性能,用完其时间片的活动批处理进程进入过期进程,而交互式进程仍然是活动进程,调度程序会重新装填它的时间片。但是如果最老的过期进程已经等待了很长的时间,或者过期进程中比交互式进程的静态优先级高,调度程序就把用完时间片的交互式进程移到过期进程集合中。最终活动进程变为空,过期进程将有机会运行。

实时进程的调度

每个实时进程都与一个实时优先级相关,实时优先级是一个范围从1(最高优先级)到99(最低优先级)的值。调度程序总是让优先级高的进程运行,与普通进程不同,实时进程总是被当做活动进程(不考虑低优先级的进程饥饿问题)。只有发生下面是事件之一时实时进程才会被另一个进程取代:

  • 进程被另一个具有更高实时优先级的实时进程取代。
  • 进程执行了阻塞操作并进入了睡眠。
  • 进程停止或被杀死。
  • 进城通过系统调用sched_yield()自愿放弃CPU。
  • 进程时基于时间片轮转的实时进程(SCHED_RR),且用完了时间片。

基于时间片轮转的实时进程的时间片长度与实时进程的优先级无关,只与进程的静态优先级有关,关系见上一节的公式。

调度程序分析

既然是从源码深入了解调度程序,那一定要从数据结构开始分析,然后再看Linux如何实现/优化调度。

调度程序相关数据结构

运行队列runqueue

runqueue是2.6调度最重要的数据结构,系统中每个CPU拥有自己的运行队列,定义如下:

系统中每个可运行进程属于且只属于一个运行队列,所以每个进程只能运行在拥有该运行队列的CPU上,但是linux可以将进程从一个运行队列迁移到另一个运行队列。

简单解释一下每个字段:

  • lock就是运行队列锁,因为其他CPU也会将进程插入到本CPU的运行队列中,所以虽然是CPU私有队列也需要锁保护。
  • nr_running是运行队列中可运行的进程数。
  • cpu_load是基于运行队列中进程的平均数量的CPU负载因子。
  • nr_switches是CPU进程切换的次数。
  • nr_uninterruptible表示先前在运行队列链表中而现在睡眠在TASK_UNINTERRUPTIBLE状态的进程数。
  • expired_timestamp过期队列中最老的进程被插入队列的时间。
  • timestamp_last_tick最近一次定时器中断的时间戳的值。
  • curr当前正在运行的进程描述符。
  • idle当前CPU上swapper进程描述符指针。
  • prev_mm在进程切换期间用来保存被替换进程内存描述符的地址。
  • active指向活动进程链表的指针
  • expired指向过期进程链表的指针
  • arrays活动进程和过期进程的两个集合
  • best_expired_prio过期进程中静态优先级最高的进程
  • nr_iowait先前在运行队列中而现在在等待I/O操作结束的进程数量。
  • sd指向当前CPU的基本调度域。
  • active_balance如果要把一些进程从本地运行队列迁移到另外的运行队列,就设置这个标志。
  • 未使用push_cpu字段。
  • migration_thread迁移内核线程的进程描述符指针。
  • migration_queue从运行队列中被删除的进程的列表。

稍微解释一下活动进程和过期进程的设计,arrays声明了一个prio_array_t结构数组,active指向其中一个作为运行进程队列链表,expired就指向另一个作为过期进程队列链表,如此反复切换只有修改指针值的开销,拥有很高的效率。

运行队列链表prio_array_t

  • nr_active表示队列中的进程数。
  • 因为Linux有0~139(140个)种优先级,因此queue拥有140个链表,每个链表对应一个优先级。
  • bitmap用位来表示各个优先级的链表是否有元素。

进程描述符task_t

这个结构包含了进城相关的所有数据结构,去掉一些调试用的仍然有一百多项,因此只说明和调度程序有关的一些字段。

挑一些和调度相关的字段注释一下:

  • state包含进程的当前状态。
  • thread_info是存放在内核态栈的底端的数据结构对应的指针,thread_info->flags存放TIF_NEED_RESCHED标志,表示必须调用调度程序。thread_info->cpu表示可运行进程所在队列的CPU逻辑号。
  • prio是进程的动态优先级。
  • static_prio是进程的静态优先级。
  • run_list指向进程所属的运行队列(对应的优先级)中的下一个和上一个元素。
  • array指向包含进程的运行队列集合。
  • sleep_avg是进程的平均睡眠时间。
  • timestamp是进程最近插入运行队列的时间,或涉及本进程最后一次进程切换的时间。
  • last_ran最近一次替换本进程的进程切换时间。
  • activated进程被唤醒时所使用的条件代码
    0表示处于TASK_RUNNING状态;
    1表示TASK_INTERRUPTBLE或TASK_STOP状态,并正在被系统调用或内核线程唤醒;
    2表示TASK_INTERRUPTBLE或TASK_STOP状态,并且正在被中断处理程序或可延迟函数唤醒;
    -1表示TASK_UNINTERRUPTIBLE状态并且正在被唤醒;
  • policy进程的调度类型(SCHED_NORMAL, SCHED_RR或SCHED_FIFO)
  • cpus_allowed能执行进程的CPU位掩码。
  • first_time_slice第一个时间片标志,在创建新进程时总会置1。
  • rt_priority进程的实时优先级。

调度程序使用的方法

  • scheduler_tick()
    维持当前最新的time_slice计数器
  • try_to_wake_up()
    唤醒睡眠进程
  • recalc_task_prio()
    更新进程的动态优先级
  • schedule()
    选择要被执行的新进程
  • load_balance()
    维持多处理器系统中运行队列的平衡(下一节)

scheduler_tick()函数

在每次硬件时钟节拍到来时,中断处理函数中会调用本函数,本函数更新当前进程的时间片,如果需要重新调度会设置标志位,函数如下(注释直接放在代码中)

try_to_wake_up()函数

将进程设置为TASK_RUNNING,并把进程插入某个CPU的运行队列来唤醒睡眠或停止的进程,代码和注释如下。

recalc_task_prio()函数

更新进程的平均睡眠时间和动态优先级,它接受进程描述符p和由函数sched_clock()计算出来的当前时间戳now作为参数。

schedule()函数

实现调度程序,它的任务是从运行队列的链表中找到一个进程,并将CPU分配给这个进程。schedule()可以由几个内核控制路径调用。

直接调用

如果current进程因不能获得必要的资源而要立刻被阻塞,就直接调用调度程序。在这种情况下,要阻塞进程的内核路径按以下步骤执行:

  1. 把current进程插入到合适的等待队列;
  2. 把current的进程状态改为TASK_INTERRUPTBLE或者TASK_UNINTERUPTBLE。
  3. 调用schedule()
  4. 检查资源是否可用,否则返回第2步。
  5. 一旦资源可用,就从等待队列中删除current进程。

延迟调用

把当前进程的TIF_NEED_RESCHED标志置为1,而以延迟方式调用调度程序。由于用户总是在恢复用户态进程的执行之前检查这个标志的值,所以schedule()将在不久之后某个时间被明确地调用。以下是典型的例子:

  • 当current进程用完了时间片之后,由scheduler_tick()函数完成schedule()的延迟调用。
  • 当一个被唤醒进程的优先级比当前进程的优先级高的时候,由try_to_wake_up()函数完成schedule()的延迟调用。
  • 当发出系统调用sched_setscheduler()时。

 

多处理器系统中运行队列的平衡

Linux坚持使用对称多处理器模型,这意味着与其他CPU相比,内核不对任何一个CPU有偏见,多处理器的模型有许多,下面额外关注三种:

  • 标准的多处理器体系结构
    这是多处理器机器最普遍的体系结构,所有的RAM芯片集被所有的CPU共享。
  • 超线程
    超线程芯片是一个立刻执行几个执行线程的微处理器;它包括几个内部寄存器的拷贝,并快速在它们之间切换。这种由Intel发明的技术,使得当前线程在访问内存的间隙,处理器可以使用它的机器周期去执行另外一个线程。一个超线程的物理CPU可以被Linux看作几个不同的逻辑CPU。
  • NUMA
    把CPU和RAM以本地“节点”为单位分组(通常一个节点包括一个CPU和几个RAM芯片)。内存仲裁器(一个使系统中的CPU以串行方式访问RAM的专用电路)是典型的多处理器系统瓶颈。在NUMA体系结构中,当CPU访问与它同在一个节点的“本地”RAM芯片时,几乎没有竞争,因此是非常快的。另一方面,访问“远程”RAM芯片就非常慢。

因为Linux使每个处理器拥有独立的运行队列,CPU之间相互不共享进程,那么很可能会出现一个CPU非常繁忙,其他CPU空闲的情况,为了避免这种情况,Linux提出了一种基于“调度域”的运行队列平衡算法,可以将一些进程从一个运行队列迁移到另一个运行队列。

调度域

调度域就是一个CPU集合,它们的工作量应该保持平衡。调度域采用分层的组织形式:最上层的调度域包括多个子调度域,每个子调度域包括一个CPU子集。每个调度域被划分成一个或多个组,每个组代表调度域的一个CPU子集。工作量的平衡总是在调度域的组之间来完成。换言之,在某调度域的某个组的总工作量远远低于同一个调度域的另一个组时,能把进程从一个CPU迁移到另一个CPU。

每个调度域由一个sched_domain描述符表示,定义如下:

调度域中的每个组由sched_group描述符表示,它是groups字段,指向组描述符表中的第一个元素,此外,parents字段指向父调度域的描述符(如果有的话)。

系统中所有物理CPU的sched_domain描述符都存放在每CPU变量phys_domain中。如果内核不支持超线程技术,这些域就是在域层次结构的最底层,运行队列描述符的sd字段指向它们,即为它们的调度域。相反,如果内核支持超线程技术,则底层调度域存放在每个CPU变量cpu_domains中。

这里的源码就不细细分析(太累)了,大致上就是在某CPU会经常检查自己是不是太闲了,如果是就看看别的CPU是不是很忙,然后把它的队列中的一些进程给自己来运行。这里唯一要注意的一点就是死锁问题,因此Linux加锁的顺序是,先把原CPU的锁释放,然后根据cpu id递增的顺序重新加锁。

与调度相关的系统调用

nice()系统调用

系统调用允许进程改变它们的优先级。包含在increment参数中的整数值用来修改进程描述符的nice字段。
sys_nice()服务例程处理nice()系统调用。尽管increment参数可以是任何值,但是大于40的绝对值会被截为40。从传统来说,负值就是优先级增加。
nice()系统调用只是维持向后兼容,已经被下面的setpriority()取代了。

getpriority()和setpriority()系统调用

nice()系统调用只影响调用它的进程,而这两个则作用于给定组中所有进程的基本优先级。

sched_getaffinity()和sched_setaffinity()系统调用

分别返回和设置CPU进程亲和力掩码,即允许执行进程的CPU的位掩码,掩码存放在进程描述符的cpus_allowed字段中。

与实时进程相关的系统调用

sched_getscheduler()和sched_setscheduler()系统调用

查询和设置进程的调度策略(SCHED_FIFO, SCHED_RR或SCHED_NORMAL)。

sched_getparam()和sched_setparam()系统调用

sched_getparam()为pid所表示的进程检索调度参数,如果pid是0则current进程的参数被检索,sched_setparam()即设置。

sched_yield()系统调用

允许进程在不被挂起的情况下自愿放弃CPU,进程仍属于TASK_RUNNING状态,但调度进程将它放到队尾,使相同优先级的进程得以运行。

sched_get_priority_min()和sched_get_priority_max()系统调用

分别返回最小和最大实时静态优先级的值,如果current是实时进程则最小返回1,否则返回0;如果current是实时进程,则最大返回99否则返回0。

sched_rr_get_interval()系统调用

获得pid指定的进程的时间片,0为current。通常,FIFO实时进程的时间片为0。

 

End.

1 评论

发表评论

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