Linux进程调度(一)

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

调度字段

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

struct  task_struct {
…
int prio,static_prio,normal_prio;
struct list_head run_list;
const struct sched_class *sched_class;
struct sched_entity se;
unsigned int policy;
cpumask_t cpus_allowed;
unsigned int time_slice;
unsigned int rt_priority;
...
}

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

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

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

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

#define MAX_USER_RT_PRIO    100
#define MAX_RT_PRIO        MAX_USER_RT_PRIO
#define MAX_PRIO            (MAX_RT_PRIO + 40)
#define DEFAULT_PRIO        (MAX_RT_PRIO  + 20)

与静态优先级相关的宏

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

#define USER_PRIO(p)        ((p)-MAX_RT_PRIO)
#define TASK_USER_PRIO(p)    USER_PRIO((p)->static_prio)
#define MAX_USER_PRIO        (USER_PRIO(MAX_PRIO))

nice系统调用源码如下:

asmlinkage long sys_nice(int increment)
{
    long nice,retval;

    if(increment < -40)    increment = -40;
    if(increment > 40)    increment = 40;

    nice = PRIO_TO_NICE(current->static_prio) + increment;
    if (nice<-20)    nice = -20;
    if(nice > 19)    nice = 19;
    //如果是提高其优先级，判断是否超出用户限制
    if(increment < 0 && !can_nice(current,nice))
        return -EPERM;
    retval = security_task_setnice(current,nice)
    if(retval)    return retval;
    //设置当前进程优先级,优先级改变，进程负载改变
    set_user_nice(current,nice);
    return 0;
}

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

static struct task_struct* copy_process(unsigned long clone_flags,
        unsigned long stack_start,struct pt_regs *regs,
        unsigned long stack_size,int __user *child_tidptr,struct pid *pid)
{
    …....
    sched_fork(p,clone_flags);
    …....
    p->ioprio = current ->ioprio;//io调度优先级
}
void sched_fork(struct task_struct *p,int clone_flags)
{
    …...
    p->prio = current->normal_prio;
    if(!rt_prio(p->prio))
        p->sched_class = &fair_sched_class;
    …..
}

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

void fastcall wake_up_new_task(struct task_struct *p,
                    unsigned long clone_flags)
{
    …...
    rq = task_rq_lock(p,&flags);
    BUG_ON(p->state != TASK_RUNNING);
    //更新该运行队列运行时间
    update_rq_clock(rq);
    //赋值动态优先级
    p->prio = effective_prio(p);
    //如果没有进入运行队列，则进入运行队列
    if(!p->sched_class->task_new || !current->se.on_rq) {
        activate_task(rq,p,0);
    } else {
        //第一次则需要进行初始化
        p->sched_class->task_new(rq,p);
        inc_nr_running(p,rq);
    }
    //可以抢占了
    check_preempt_curr(rq,p);
    task_rq_unlock(rq,&flags);
}

其中effective_prio函数原型如下:

static int effective_prio(struct task_struct *p)
{
    p->normal_prio = normal_prio(p);
    /*
     *If we are RT tasks or we were boosted to RT priority,
     *keep the priority unchanged. Otherwise,update priority to the normal
     *priority
    **/
    if(!rt_prio(p->prio))
        return p->normal_prio;
    return p->prio;
}

而normal_prio原型如下:

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

从上面的代码看出，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:用于决定一个进程是否为实时进程，对应的方法如下:

static inline int rt_policy(int policy)
{
    if(unlikely(policy == SCHED_FIFO) || unlikely(policy == SCHED_RR))
        return 1;
    return 0;
}
static inline int task_has_rt_policy(struct task_struct *p)
{
    return rt_policy(p->policy);
}

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

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