Chinaunix首页 | 论坛 | 博客
  • 博客访问: 458261
  • 博文数量: 72
  • 博客积分: 1851
  • 博客等级: 上尉
  • 技术积分: 1464
  • 用 户 组: 普通用户
  • 注册时间: 2010-09-16 17:50
文章分类

全部博文(72)

文章存档

2013年(1)

2012年(17)

2011年(51)

2010年(3)

分类: LINUX

2011-08-28 20:44:19

        在linux调度过程中,采用了红黑树的数据结构,通过虚拟可运行时间与等待时间的时间差作为红黑树的一个key,树中最左边的则为下一次运行的进程,在linux系统中进程调度主要分为:公平调度和实时调度,而进程的运行时间又与进程的优先级,等待时间以及运行时间。

调度字段

进程与调度相关的字段定义如下:

  1. struct task_struct {
  2. int prio,static_prio,normal_prio;
  3. struct list_head run_list;
  4. const struct sched_class *sched_class;
  5. struct sched_entity se;
  6. unsigned int policy;
  7. cpumask_t cpus_allowed;
  8. unsigned int time_slice;
  9. unsigned int rt_priority;
  10. ...
  11. }

其中prionormal_prio属于动态优先级(在运行过程中随着运行时间的变化而变化),static_prio属于静态优先级,可以通过nice系统调用和sched_setschedulers系统调用进行修改,但是在运行过程中系统不会对其进行自动修改。

normal_prio通过进程的静态优先级和进程的调度策略进行计算,相同的静态优先级可以有不同的normal_prio,因为还需要根据该进程是否是实时进程或常规进程。

prio则是在系统运行过程中进行暂时提升进程优先级时,就需要保存在该字段中。

静态优先级可以通过nice系统调用改变,它的范围为[-20,+19],在内核中的范围为[100,139],与优先级相关的转换宏如下:

  1. #define MAX_USER_RT_PRIO    100
  2. #define MAX_RT_PRIO        MAX_USER_RT_PRIO
  3. #define MAX_PRIO            (MAX_RT_PRIO + 40)
  4. #define DEFAULT_PRIO        (MAX_RT_PRIO + 20)

与静态优先级相关的宏

  1. #define NICE_TO_PRIO(nice)    (MAX_RT_PRIO + (nice) + 20)
  2. #define PRIO_TO_NICE(prio)    ((prio) – MAX_RT_PRIO – 20)
  3. #define TASK_NICE(p)            PRIO_TO_NICE((p)->static_prio)

  4. #define USER_PRIO(p)        ((p)-MAX_RT_PRIO)
  5. #define TASK_USER_PRIO(p)    USER_PRIO((p)->static_prio)
  6. #define MAX_USER_PRIO        (USER_PRIO(MAX_PRIO))

nice系统调用源码如下:

  1. asmlinkage long sys_nice(int increment)
  2. {
  3.     long nice,retval;
  4.     
  5.     if(increment < -40)    increment = -40;
  6.     if(increment > 40)    increment = 40;
  7.     
  8.     nice = PRIO_TO_NICE(current->static_prio) + increment;
  9.     if (nice<-20)    nice = -20;
  10.     if(nice > 19)    nice = 19;
  11.     //如果是提高其优先级,判断是否超出用户限制
  12.     if(increment < 0 && !can_nice(current,nice))
  13.         return -EPERM;
  14.     retval = security_task_setnice(current,nice)
  15.     if(retval)    return retval;
  16.     //设置当前进程优先级,优先级改变,进程负载改变
  17.     set_user_nice(current,nice);
  18.     return 0;    
  19. }

当系统创建进程时,优先级部分如下:

  1. static struct task_struct* copy_process(unsigned long clone_flags,
  2.         unsigned long stack_start,struct pt_regs *regs,
  3.         unsigned long stack_size,int __user *child_tidptr,struct pid *pid)
  4. {
  5.     …....
  6.     sched_fork(p,clone_flags);
  7.     …....
  8.     p->ioprio = current ->ioprio;//io调度优先级
  9. }
  10. void sched_fork(struct task_struct *p,int clone_flags)
  11. {
  12.     …...
  13.     p->prio = current->normal_prio;
  14.     if(!rt_prio(p->prio))
  15.         p->sched_class = &fair_sched_class;
  16.     …..
  17. }

创建完成之后就唤醒进程,调用下面的方法:

  1. void fastcall wake_up_new_task(struct task_struct *p,
  2.                     unsigned long clone_flags)
  3. {
  4.     …...
  5.     rq = task_rq_lock(p,&flags);
  6.     BUG_ON(p->state != TASK_RUNNING);
  7.     //更新该运行队列运行时间
  8.     update_rq_clock(rq);
  9.     //赋值动态优先级
  10.     p->prio = effective_prio(p);
  11.     //如果没有进入运行队列,则进入运行队列
  12.     if(!p->sched_class->task_new || !current->se.on_rq) {
  13.         activate_task(rq,p,0);
  14.     } else {
  15.         //第一次则需要进行初始化
  16.         p->sched_class->task_new(rq,p);
  17.         inc_nr_running(p,rq);
  18.     }
  19.     //可以抢占了
  20.     check_preempt_curr(rq,p);
  21.     task_rq_unlock(rq,&flags);
  22. }

其中effective_prio函数原型如下:

  1. static int effective_prio(struct task_struct *p)
  2. {
  3.     p->normal_prio = normal_prio(p);
  4.     /*
  5.      *If we are RT tasks or we were boosted to RT priority,
  6.      *keep the priority unchanged. Otherwise,update priority to the normal
  7.      *priority
  8.     **/
  9.     if(!rt_prio(p->prio))
  10.         return p->normal_prio;
  11.     return p->prio;
  12. }

normal_prio原型如下:

  1. static inline int normal_prio(struct task_struct *p)
  2. {
  3. int prio;
  4. //如果有实时优先级,则返回经过转换后的实时优先级,
  5. //这里防止了非实时进程突然增长到实时进程的优先级,
  6. //所以创建进程时子进程继承父进程的normal_prio
  7. if(task_has_rt_policy(p)) prio = MAX_RT_PRIO – 1 – p->rt_priority;
  8. else //否则就返回静态优先级
  9. prio = __normal_prio(p);//prio = p->static_prio
  10. return prio;
  11. }

从上面的代码看出,prio,normal_prio的计算均基于调度策略,优先级的变化情况如下:

进程类型/优先级

static_prio

normal_prio

prio

非实时

static_prio

static_prio

static_prio

增长优先级的非实时

static_prio

static_prio

prio

实时

static_prio

MAX_RT_PRIO-1-rt_priority

prio


rt_priority:暗示一个进程为实时进程,实时优先级的范围为:0~99,正常优先级范围为:100~139

数值越高,实时优先级越大,而正常优先级则相反,创建进程时,均为cfs类型的进程,可通过系统调用set_scheduler来转换为实时进程。

sched_class:该进程所在的调度类型,目前主要有两种:CFS公平调度和Real-Time实时调度。

se:调度实体,以什么为一个调度单位,通常而言,以进程为单位,也可以以进程组为单位,来进行cpu时间的分配,调度器设计在调度实体之上,每个进程都有一个该实体,这也就成为了进程的一部分。

policy:进程所使用的调度策略,Linux支持下面五种策略:

1.SCHED_NORMAL,一般进程都是此策略,通过CFS调度器来实现,另外,SCHED_BATCH,SCHED_IDLE都是通过cfs来实现,但是用于不太重要的进程中,而SCHED_BATCH用于cpu密集型进程非交互型,这种类型的进程不抢占另外的进程,用于高优先级的进程中,但是需要在不影响系统交互性的前提下。

SCHED_IDLE:低优先级的调度,而且在系统负载很小的情况下才使用。

SCHED_RR,SCHED_FIFO:用于实现软实时进程,SCHED_RR实现轮转式调度策略,SCHED_FIFO实现了先来先服务的调度机制,这两类用于实时调度中。

rt_policy:用于决定一个进程是否为实时进程,对应的方法如下:

  1. static inline int rt_policy(int policy)
  2. {
  3.     if(unlikely(policy == SCHED_FIFO) || unlikely(policy == SCHED_RR))
  4.         return 1;
  5.     return 0;
  6. }
  7. static inline int task_has_rt_policy(struct task_struct *p)
  8. {
  9.     return rt_policy(p->policy);
  10. }

cpu_allowed:进程可能运行的cpu,系统调用sched_setaffinity就是修改此字段

run_list,time_slice:用于轮转式实时调度,run_list用来保存进程的运行列表,time_slice则用于进程剩下的时间。

阅读(2543) | 评论(0) | 转发(1) |
0

上一篇:回溯法总结

下一篇:动态规划小结

给主人留下些什么吧!~~