Linux内核之实时进程调度和组调度

  Linux内核之实时进程调度和组调度

作者：harvey wang 

邮箱：

 

 

 

      Linux支持三种进程调度策略，分别是SCHED_FIFO 、 SCHED_RR和SCHED_NORMAL。Linux支持两种类型的进程，实时进程和普通进程。实时进程可以采用SCHED_FIFO 和SCHED_RR调度策略；普通进程采用SCHED_NORMAL调度策略。

       Linux为实时进程划分了100个优先级，从0—99，0为最高优先级，99为最低实时优先级，请参考《linux内核之进程优先级》。为了实现O(1)调度算法，内核为每个优先级维护一个运行队列和一个DECLARE_BITMAP，内核根据DECLARE_BITMAP的bit数值找出非空的最高优先级队列编号，即queue[]数组的下标，从而可以直接从非空最高优先级队列中取出进程进行运行。

#define MAX_RT_PRIO   100

       相同优先级的FIFO实时进程和RR实时进程挂到同一个运行队列上，他们的不同在于RR实时进程运行一段时间后（时间片耗尽），重新挂到运行队列的尾部等待下一次运行。而FIFO的实时进程一旦运行，则会一直占据CPU直到更高优先级的FIFO或RR进程抢占，或自己主动放弃CPU。这样子好像很不公平，通常会把运行时间较短的进程设置为FIFO调度策略，把运行时间较长的进程设置为RR调度策略。

       RR实时进程是有时间片的，FIFO实时进程是没有时间片。但也有的说FIFO进程也有时间片，从内核代码看，FIFO实时进程也是有时间片的，是为了在很多处理中不需要使用if语句区分这两种进程，而在时钟中断中只会减少RR进程的时间片，不会改变FIFO进程的时间片。FIFO进程的时间片永远用不完，使其时间片失去作用。

       不同优先级的实时进程间是基于优先级进行抢占的。实时进程也是完全抢占普通进程的吗？Linux内核设置了两个全局变量，单位为us，如下

unsigned int sysctl_sched_rt_period = 1000000;

int sysctl_sched_rt_runtime = 950000;

       sysctl_sched_rt_period表示实时进程运行周期为1s，sysctl_sched_rt_runtime表示在运行周期内，实时进程最多运行0.95秒。内核强制实时进程为普通进程预留出一定的运行时间。当然可以把sysctl_sched_rt_runtime和sysctl_sched_rt_period设置成相同的数值，即实时进程可以完全抢占普通进程。

 

       实时进程调度相关的数据结构

struct rq {

       struct cfs_rq cfs;

       struct rt_rq rt;

}

struct rt_rq {

       struct rt_prio_array active;

}

struct rt_prio_array {

       DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */

       struct list_head queue[MAX_RT_PRIO];

}

       参考下图红色框中，struct rq为每个cpu上最顶层调度数据结构，其中包括CFS调度队列struct cfs_rq cfs（参见《linux内核之CFS调度和组调度》）和实时进程调度数据结构struct rt_rq rt，其中实时进程调度数据结构中包含了调度队列struct rt_prio_array，在该结构中为每个实时优先级分配了一个队列头，用于挂接该优先级的实时进程（其实是进程对应的调度实体se）。

因下图看不清，直接将原始的word文档上传上了： linux内核之实时进程调度和组调度.doc 

 

 

       实时进程组调度

       实时进程组调度的文字是基于《linux组调度浅析》（作者：百度空间的kouu）中的描述整理得到。

       实时进程是对CPU有着实时性要求的进程，它的优先级是跟具体任务相关的，完全由用户来定义的。调度器总是会选择优先级最高的实时进程来运行。实时进程组的优先级就被定义为“组内最高优先级的进程所拥有的优先级”。比如组内有三个优先级分别为10、20、30的进程，则组的优先级就是10（数值越小优先级越大）。

将实时进程分组还有什么意义呢？无论分组与否，调度程序要做的事情都是“在所有TASK_RUNNING状态的实时进程中选择优先级最高的那一个”。 其实，实时进程的分组就把sched_rt_runtime_us和sched_rt_period_us的概念扩展了，每个task_group都有自己的sched_rt_runtime_us和sched_rt_period_us（即task_group中rt_bandwidth. rt_period 和 rt_bandwidth. rt_runtime，harvey add，需要确认正确性），保证自己组内的进程在以sched_rt_period_us为周期的时间内，最多只能运行sched_rt_runtime_us这么多时间。CPU占有比为sched_rt_runtime_us/sched_rt_period_us。

在多核平台或多处理器平台上，此处实时进程组的优先级是指该组在某CPU上，该组对应的调度实体se的优先级，其优先级是se->my_q 中优先级最高进程的优先级。实时进程组在各个CPU上的se独立进行调度，互不影响。对于每一个task_group，它的调度实体和运行队列是每CPU维护一份的。而sched_rt_runtime_us和sched_rt_period_us是作用在调度实体上的，所以如果系统中有N个CPU，实时进程实际占有CPU的上限是N*sched_rt_runtime_us/sched_rt_period_us。也就是说，尽管默认情况下限制了每秒钟之内，实时进程只能运行0.95秒。但是对于某个实时进程来说，如果CPU有两个核，也还是能满足它100%占有CPU的需求的（比如执行死循环）。然后，按道理说，这个实时进程占有的100%的CPU应该是由两部分组成的（每个CPU占有一部分，但都不超过95%）。但是实际上，为了避免进程在CPU间的迁移导致上下文切换、缓存失效等一系列问题，一个CPU上的调度实体可以向另一个CPU上对应的调度实体借用时间。其结果就是，宏观上既满足了sched_rt_runtime_us的限制，又避免了进程的迁移。

 

 

 

特别感谢百度空间的kouu。在学习实时进程组调度时，他的文章《linux组调度浅析》受得很大的启发，在此向kouu致敬。如果能早一点看到这么好的文章，在学习CFS调度时就不会那么费力了。