Contents
  1. 1. 分类
  2. 2. 进程的抢占
  3. 3. 调度算法
  4. 4. 普通进程的调度 (参考自linux进程调度浅析)
  5. 5. 实时进程的调度
  6. 6. 调度程序所使用的函数
  7. 7. 多处理器系统中运行队列的平衡
  8. 8. 与调度相关的系统调用
  9. 9. 与实时进程相关的系统调用

摘要:linux与任何分时系统一样,通过一个进程到另一个进程的快速切换,达到表面上看来的多个进程同时执行的神奇效果。



Linux的调度基于分时(time sharing)技术:多个进程以“时间多路复用”方式运行,因为CPU的时间被分成“片(slice)”,给每个可运行进程分配一片。

在linux中,进程的优先级是动态的。调度程序跟踪进程正在做什么,并周期性地调整它们的优先级。

分类

传统上,把进程分类为“IO受限(IO bound)”或“CPU受限(CPU bound)”。前者频繁使用IO设备,并花费很多时间等待IO操作的完成;而后者则需要大量CPU时间的数值计算应用程序。

另一种分类方法把进程区分为三类:交互式进程(interactive process)、批处理进程(batch process、实时进程(real-time process)。

进程的抢占

Linux的进程是抢占式的。根据优先级和时间片是否国企决定是否可以被抢占。

Linux2.6内核是抢占式的,这意味着进程无论是处于内核态还是用户态,都可能被抢占。

调度算法

调度程序总能成功地找到要执行的进程。事实上,总是至少有一个可运行进程,即swapper进程,它的PID等于0,而且它只有在CPU不能执行其他进程时才执行。

每个Linux进程总是按照下面的调度类型被调度:

SCHED_FIFO(先进先出的实时进程):直到先被执行的进程变为非可执行状态,后来的进程才被调度执行。在这种策略下,先来的进程可以执行sched_yield系统调用,自愿放弃CPU,以让权给后来的进程;

SCHED_RR(时间片轮转的实时进程):轮转调度。内核为实时进程分配时间片,在时间片用完时,让下一个进程使用CPU;

SCHED_NORMAL(普通的分时进程)。

普通进程的调度 (参考自linux进程调度浅析)

实时进程调度的中心思想是,让处于可执行状态的最高优先级的实时进程尽可能地占有CPU,因为它有实时需求;而普通进程则被认为是没有实时需求的进程,于是调度程序力图让各个处于可执行状态的普通进程和平共处地分享CPU,从而让用户觉得这些进程是同时运行的。

每个普通进程都有它自己的静态优先级,还有动态优先级。

与实时进程相比,普通进程的调度要复杂得多。内核需要考虑两件麻烦事:

一、动态调整进程的优先级

按进程的行为特征,可以将进程分为“交互式进程”和“批处理进程”:

交互式进程(如桌面程序、服务器、等)主要的任务是与外界交互。这样的进程应该具有较高的优先级,它们总是睡眠等待外界的输入。而在输入到来,内核将其唤醒时,它们又应该很快被调度执行,以做出响应。比如一个桌面程序,如果鼠标点击后半秒种还没反应,用户就会感觉系统“卡”了;

批处理进程(如编译程序)主要的任务是做持续的运算,因而它们会持续处于可执行状态。这样的进程一般不需要高优先级,比如编译程序多运行了几秒种,用户多半不会太在意;

如果用户能够明确知道进程应该有怎样的优先级,可以通过nice、setpriority系统调用来对优先级进行设置。(如果要提高进程的优先级,要求用户进程具有CAP_SYS_NICE能力。)

然而应用程序未必就像桌面程序、编译程序这样典型。程序的行为可能五花八门,可能一会儿像交互式进程,一会儿又像批处理进程。以致于用户难以给它设置一个合适的优先级。

再者,即使用户明确知道一个进程是交互式还是批处理,也多半碍于权限或因为偷懒而不去设置进程的优先级。(你又是否为某个程序设置过优先级呢?)

于是,最终,区分交互式进程和批处理进程的重任就落到了内核的调度程序上。

调度程序关注进程近一段时间内的表现(主要是检查其睡眠时间和运行时间),根据一些经验性的公式,判断它现在是交互式的还是批处理的?程度如何?最后决定给它的优先级做一定的调整。

进程的优先级被动态调整后,就出现了两个优先级:

1、用户程序设置的优先级(如果未设置,则使用默认值),称为静态优先级。这是进程优先级的基准,在进程执行的过程中往往是不改变的;

2、优先级动态调整后,实际生效的优先级。这个值是可能时时刻刻都在变化的;

二、调度的公平性

在支持多进程的系统中,理想情况下,各个进程应该是根据其优先级公平地占有CPU。而不会出现“谁运气好谁占得多”这样的不可控的情况。

linux实现公平调度基本上是两种思路:

1、给处于可执行状态的进程分配时间片(按照优先级),用完时间片的进程被放到“过期队列”中。等可执行状态的进程都过期了,再重新分配时间片;

2、动态调整进程的优先级。随着进程在CPU上运行,其优先级被不断调低,以便其他优先级较低的进程得到运行机会;

后一种方式有更小的调度粒度,并且将“公平性”与“动态调整优先级”两件事情合而为一,大大简化了内核调度程序的代码。因此,这种方式也成为内核调度程序的新宠。

强调一下,以上两点都是仅针对普通进程的。而对于实时进程,内核既不能自作多情地去动态调整优先级,也没有什么公平性可言。

普通进程具体的调度算法非常复杂,并且随linux内核版本的演变也在不断更替(不仅仅是简单的调整),所以本文就不继续深入了。有兴趣的朋友可以参考下面的链接:

《Linux 调度器发展简述》

《鼠眼看Linux调度器》

《鼠眼再看Linux调度器[1]》

《鼠眼再看Linux调度器[2]》

实时进程的调度

每个实时进程都与一个实时优先级相关,实时优先级是一个范围从1(最高优先级)~99(最低优先级)的值。调度程序总是让优先级高的进程运行,换句话说,实时进程运行的过程中,禁止低优先级的进程的执行。与普通进程相反,实时进程总是被当成活动进程。用户可以通过系统调用sched_setparam()和sched_setscheduler()改变进程的实时优先级。

只有在下述时间之一发生时,实时进程才会被另一个进程取代:

进程被另外一个具有更高实时优先级的实时进程抢占 

进程执行了阻塞操作并进入睡眠(处于TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE状态)。 

进程停止(处于TASK_STOPPED或TASK_TRACED状态)或被杀死(处于EXIT_ZOMBIE或EXIT_DEAD状态)。 

进程通过调用系统调用sched_yield()自愿放弃CPU。 

进程是基于时间片轮转的实时进程(SCHED_RR),而且用完了它的时间片。 

数据结构runqueue是Linux2.6调度程序最重要的数据结构。系统中的每个CPU都有它自己的运行队列,所有的runqueue结构存放在runqueues每CPU变量中。

调度程序所使用的函数

scheduler_tick():维持当前最新的time_slice计数器

try_to_wake_up():唤醒睡眠进程

recalc_task_prio():更新进程的动态优先级

schedule():选择要被执行的新进程

load_balance():维持多处理器系统中运行队列的平衡

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

Linux一直坚持采用对称多处理模式,这意味着,与其他CPU相比,内核不对一个CPU有任何偏向,但是,多处理器机器具有很多不同的风格,而且调度程序的实现随硬件特征的不同而有所不同,我们将特别关注下面三种不同类型的多处理器机器:

(1)标准的多处理器体系结构

直到最近,这是多处理器机器最普通的体系结构。这些机器所共有的RAM芯片集被所有CPU共享。

(2)超线程

超线程芯片是一个立刻执行几个执行线程的微处理器;它包括几个内部寄存器的拷贝,并快速在它们之间切换。这种由Intel发明的技术,使得当前线程在访问内存的间隙,处理器可以使用它的机器周期去执行另外一个线程。一个超线程的物理CPU可以被Linux看作几个不同的逻辑CPU。

(3)NUMA

把CPU和RAM以本地“结点”为单位分组,(通常一个结点包括一个CPU和几个RAM芯片)。内存仲裁器(一个使系统中的CPU以串型方式访问RAM的专用电路)是典型的多处理器系统的瓶颈。在NUMA体系结构中,当CPU访问与它同在一个结点中的“本地”RAM芯片时,几乎没有竞争,因此访问通常是非常快的。另一方面,访问它所属结点外的“远程”RAM芯片就非常慢。

与调度相关的系统调用

nice()、getpriority()和setpriority()系统调用、sched_getaffinity()和sched_setaffinity()调用

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

sched_getscheduler()和sched_setscheduler()系统调用、sched_getparam()和sched_setparam()系统调用、sched_yield()系统调用、sched_get_priority_min()和 sched_get_priority_max()系统调用、sched_rr_get_interval()系统调用



本文章参考自《深入理解linux内核》。

Contents
  1. 1. 分类
  2. 2. 进程的抢占
  3. 3. 调度算法
  4. 4. 普通进程的调度 (参考自linux进程调度浅析)
  5. 5. 实时进程的调度
  6. 6. 调度程序所使用的函数
  7. 7. 多处理器系统中运行队列的平衡
  8. 8. 与调度相关的系统调用
  9. 9. 与实时进程相关的系统调用