Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

Vinllen Chen


烛昭

linux下进程调度

  linux 2.6之后内核的进程调度算法是CFS:完全公平调度算法。

1.策略

1.1 I/O消耗性和处理器消耗型的进程

  调度策略通常要在两个矛盾的目标中间寻找平衡:进程响应迅速和最大系统利用率了。

1.2 进程优先级

  linux采用了两种不同的优先级范围。第一种是用nice值,范围从-20到+19,默认值为0;越大的nice值意味着更低的优先级。相比高nice值的进程,低nice值的进程可以获得更多的处理器时间。nice值也代表时间片的比例。可以通过ps -ef查看系统中的进程列表,结果中标记NI的一列就是进程对应的nice值。
  第二种是实时优先级,其值是可配置的,默认情况下它的变化范围从0到99。与nice相反,越高的实时优先级数值意味着进程优先级越高。对应的Linux下是PTPRIO。

1.3 时间片

  时间片是一个数值,代表进程在被抢占前所能持续运行的时间。时间片过长会导致系统对交互的响应表现欠佳,让人觉得系统无法并发执行应用程序;时间片太短会明显增大进程切换带来的处理器耗时,因为会有相当一部分系统时间用在进程切换上。
  linux下的CFS调度器并没有直接分配时间片到进程,它是将处理器的使用比划分给了进程。

2.linux调度算法

2.1 调度器类

  linux调度器是以模块方式提供的,这样做的目的是允许不同类型的进程可以有针对性地选择调度算法。
  这种模块化结构被称为调度器类,它允许多种不同的可动态添加的调度算法并存,调度属于自己范畴的进程。每个调度器都有一个优先级,它会按照优先级顺序遍历调度类,拥有一个可执行进程的最高优先级的调度器类胜出,去选择下面要执行的那一个程序。
  完全公平调度(CFS)是一个针对普通进程的调度类。

2.2 公平调度

  CFS的出发点基于一个简单的理念:进程调度的效果应如同系统具备一个理想中的完美多任务处理器。在这种系统中,每个进程将能获得1/n的处理器时间--n是指可运行进程的数量。
  CFS的做法是允许每个进程运行一段时间,循环轮转,选择运行最少的进程作为下一个运行进程,而不再采用分配给每个进程时间片的做法了,CFS在所有可运行进程总数基础上计算出一个进程应该运行多久,而不是依靠nice值来计算时间片。nice值在CFS中被作为进程获得的处理器运行比的权重:越高的nice值进程获得更低的处理器使用权重,这是相对默认nice值进程的进程而言的;同理低nice值。
  每个进程都按其权重在全部可运行进程中所占比例的“时间片”来运行,为了计算准确的时间片,CFS为完美多任务中的无限小调度周期的近似值设立了一个目标。而这个目标被称作“目标延迟”,越小的调度周期将带来教好的交互性,同时也更接近完美的多任务。但必须承受更高的切换代价和更差的系统总吞吐能力。一个目标延迟代表一次循环:所有进程都循环一次。
  当可运行任务数量趋于无限时,它们各自所获得的处理器使用比和时间比将趋于0.这样无疑造成了不可接受的切换消耗。CFS为此引入每个进程获得的时间片底线,也称为最小粒度。
  总结来说,任何进程所获得的处理器时间是由它自己和其他所有可运行进程nice值和相对差值决定的。nice值对时间片的作用不再是算数加权,而是几何加权。任何nice值对应的绝对时间不再是一个绝对值,而是处理器的使用比。

3.linux调度的实现

  vruntime变量存放进程的虚拟运行时间,该运行时间的计算是经历过了所有可运行进程总数的标准化。CFS使用vruntime变量来记录一个程序到底运行了多久时间以及它还应该再运行多久。
  CFS试图利用一个简单的规则去均衡进程的虚拟运行时间:当CFS需要选择下一个运行进程时,它会挑一个具有最小vruntime的进程。其内部实现为红黑树,键值为vruntime。

3.1调度器入口

  进程调度的主要入口点是函数schedule(),该函数中唯一重要的事情是调用pick_next_task()。
  pick_next_task()会以优先级为序,从高到低,依次检查每一个调度类,并且从最高优先级的调度类中,选择最高优先级的进程。

3.2 睡眠和唤醒

  休眠时,内核操作:进程把自己标记成休眠状态,从可执行红黑树中移除,放入等待队列,然后调用schedule()选择和执行一个其他进程。唤醒的过程刚好相反:进程被设置为可执行状态,然后再从等待队列中移到可执行红黑树中。
  休眠有两种相关的进程状态:TASK_INTERRUPTIBLE和TASK_UNINTERRUPTIBLE。它们的唯一区别是处于TASK_UNINTERRUPTIBLE的进程会忽略信号,而处于TASK_INTERRUPTIBLE状态的进程如果接收一个信号,会被提前唤醒并响应该信号。两种状态的进程位于同一个等待队列上,等待某些事件,不能运行。

  1. 等待队列
      休眠通过等待队列进行处理。等待队列是由等待某些事件发生的进程组成的简单链表。内核用wakequeuehead_t来代表等待队列。休眠过程:

DEFINE_WAIT(wait);
add_wait_queue(q, &wait);
while(!condition) { /*condition为我们在等待的事件*/
  prepare_to_wait(&q, &wait, TASK_INTERRUPTIBLE);
  if(signal_pending(current))
    /*处理信号*/
  schedule();
}
find_wait(&q, &wait);

(1)调用DEFINE_WAIT()创建一个等待队列的项。
(2)调用add_wait_queue()把自己加入到队列中。该队列会在进程等待的条件满足时唤醒它,当然我们必须在其他地方撰写相关代码,在事件发生时,对等待队列执行wake_up()操作。
(3)调用prepare_to_wait()方法将进程的状态变更为TASK_INTERRUPTIBLE或TASK_UNINTERRUPTIBLE。而且该函数如果有必要的话会将进程加回到等待队列,这是在接下来循环遍历中所需要的。
(4)如果状态被设置为TASK_INTERRUPTIBLE,则信号唤醒进程。这就是所谓的伪唤醒,因此检查并处理信号。
(5)当进程被唤醒的时候,它会再次检查条件是否为真。如果是,它就退出循环;如果不是,再次调用schedule()并一直重复这步操作。
(6)当条件满足后,进程将自己设置为TASK_RUNNING并调用finish_wait()方法把自己移除等待队列。
2.唤醒
  唤醒操作通过函数wake_up进行。

4.抢占和上下文切换

  上下文切换,也就是从一个可执行进程切换到另一个可执行进程,由context_switch()负责处理。每当一个新的进程被选出来准备投入运行的时候,schedule()就会调用该函数。它完成两项工作:

  1. 调用switch_mm(),该函数负责把虚拟内存从上一个进程切换到新进程。
  2. 调用switch_to(),该函数负责从上一个进程的处理器状态切换到新进程的处理器状态。

  内核必须知道什么时候调用schedule()。内核提供了一个need_resched标志来表明是否需要重新执行一次调度。在2.6以后的版本,它被移到thread_info结构体里,用一个特别的标志变量的一位来表示。

4.1 用户态抢占

  用户态抢占发生在:

  1. 从系统调用返回用户空间时。
  2. 从中断处理程序返回用户空间时。

4.2 内核态抢占

  只要没有持有锁,内核就可以进行抢占。锁是非抢占区的标志。
  内核抢占发生在:

  1. 中断处理程序正在执行,且返回内核空间之前。
  2. 内核代码再一次具有可抢占性的时候。
  3. 如果内核中的任务显示调用schedule()。
  4. 如果内核中的任务阻塞(这样同样会调用schedule())。

5.实时调度策略

  linux提供了两种实时调度策略:SCHED_FIFO和SCHED_RR。而普通的,非实时的调度策略是SCHED_NORMAL。
  SCHED_FIFO实现了一种简单的,先入先出的调度算法:不使用时间片。处于可运行状态的SCHED_FIFO级的进程会比任何SCHED_NORMAL级的进程都先得到调度。
  SCHED_RR 与SCHED_FIFO大体相同,只是SCHED_FIFO级的进程在耗尽事先分配给它的时间片后就不能再继续执行了。
  这两种实时算法实现的都是静态优先级。内核不为实时进程计算动态优先级。
  linux的实时调度算法提供了一种软实时的工作方式:内核调度进程,尽力使进程在它的限定时间到来前运行,但内核不保证总能满足这些进程的要求。相反,硬实时满足。

6.与调度相关的函数调用

  linux提供了一个系统调用族,用于管理与调度程序相关的参数。

参考:《Linux内核设计与实现》


About the author

vinllen chen

Beijing, China

格物致知


Discussions

comments powered by Disqus