Chinaunix首页 | 论坛 | 博客
  • 博客访问: 109735
  • 博文数量: 76
  • 博客积分: 106
  • 博客等级: 民兵
  • 技术积分: 170
  • 用 户 组: 普通用户
  • 注册时间: 2010-11-04 16:55
文章分类

全部博文(76)

文章存档

2014年(47)

2013年(2)

2012年(20)

2011年(7)

分类:

2012-10-29 21:10:32

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

作者:harvey wang 

邮箱:harvey.perfect@gmail.com

 

 

 

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

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

#define MAX_RT_PRIO   100

       相同优先级的FIFO实时进程和RR实时进程挂到同一个运行队列上,他们的不同在于RR实时进程运行一段时间后(时间片耗尽),重新挂到运行队列的尾部等待下一次运行。而FIFO的实时进程一旦运行,则会一直占据CPU直到更高优先级的FIFORR进程抢占,或自己主动放弃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表示实时进程运行周期为1ssysctl_sched_rt_runtime表示在运行周期内,实时进程最多运行0.95秒。内核强制实时进程为普通进程预留出一定的运行时间。当然可以把sysctl_sched_rt_runtimesysctl_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有着实时性要求的进程,它的优先级是跟具体任务相关的,完全由用户来定义的。调度器总是会选择优先级最高的实时进程来运行。实时进程组的优先级就被定义为组内最高优先级的进程所拥有的优先级。比如组内有三个优先级分别为102030的进程,则组的优先级就是10(数值越小优先级越大)。

将实时进程分组还有什么意义呢?无论分组与否,调度程序要做的事情都是在所有TASK_RUNNING状态的实时进程中选择优先级最高的那一个 其实,实时进程的分组就把sched_rt_runtime_ussched_rt_period_us的概念扩展了,每个task_group都有自己的sched_rt_runtime_ussched_rt_period_us(即task_grouprt_bandwidth. rt_period rt_bandwidth. rt_runtimeharvey 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_ussched_rt_period_us是作用在调度实体上的,所以如果系统中有NCPU,实时进程实际占有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调度时就不会那么费力了。

阅读(502) | 评论(0) | 转发(0) |
给主人留下些什么吧!~~