[linux]进程（五）——进程调度（实时进程调度）

点击打开链接

1，实时进程和普通进程调度的差别

实时进程需要严格按照优先级的顺序执行，比如在八核平台上，必须是优先级最高的八个进程得到调度，如果此时八个优先级最高的进程都在某一个cpu的rt队列上，那么此时的调度就会涉及到了进程在不同cpu的迁移。

2，实时调度算法概述

该实时调度器主要为了解决以下四种情况：

（1）. 在唤醒任务时，待唤醒的任务放置到哪个运行队列最合适（这里称为pre-balance）；

（2）. 新唤醒任务的优先级比某个运行队列的当前任务更低时，怎么处理这个更低优先级任务；

（3）. 新唤醒任务的优先级比同一运行队列的某个任务更高时，并且抢占了该低优先级任务，该低优先级任务怎么处理？

（4）. 当某个任务降低自身优先级，导致原来更低优先级任务相比之下具有更高优先级，这种情况怎么处理。

对于情况2和情况3，实时调度器采用push操作。push操作从根域中所有运行队列中挑选一个运行队列（一个cpu对应一个运行队列），该运行队列的优先级比待push任务的优先级更低。运行队列的优先级是指该运行队列上所有任务的最高优先级。

对于情况4，实时调度器采用pull操作。当某个运行队列上准备调度时，候选任务比当前任务的优先级更低时，实时调度器检查其他运行队列，确定是否可以pull更高优先级任务到本运行队列。还有，当某个运行队列上发生调度时，该运行队列上没有任务比当前任务优先级高，实时调度器执行pull操作，从其他运行队列中pull更高优先级任务到本运行队列。

每CPU变量运行队列rq，包含一个rt_rq数据结构。rt_rq结构体主要内容如下：

struct rt_rq {
    struct rt_prio_array  active;
    ...
    unsigned long         rt_nr_running;         // 可运行实时任务个数
    unsigned long         rt_nr_migratory;       // 该运行队列上可以迁移到其他运行队列的实时任务个数
    unsigned long         rt_nr_uninterruptible;
    int                   highest_prio;
    int                   overloaded;
};
           

实时任务优先级范围为0到99。这些实时任务组织成优先级索引数组active，该优先级数组的数据结构类型为rt_prio_arry。rt_prio_arry数据结构由两部分组成，一部分是位图，

另一部分是数组。

struct rt_prio_arry {
    unsigned long bitmap[BITS_TO_LONGS(MAX_RT_PRIO+1)];
    struct list_head queue[MAX_RT_PRIO]；
}
           

3,根域的概念

cpusets提供了一种机制，cpusets可以将部分CPU划入一个子集合，这个CPU子集供某个任务或者某个任务组使用。各个cpusets之间可以重叠，如果某个cpuset与其他cpuset没有重复CPU，那么将该cpuset称为独立的。每个独立的cpuset定义为一个孤立的域（根域）。与根域有关的信息保存在数据结构root_domain中。

struct root_domain {
    atomic_t   refcount;  /* reference count for the domain */
    cpumask_t  span;      /* span of member cpus of the domain*/
    cpumask_t  online;    /* number of online cpus in the domain*/
    cpumask_t  rto_mask;  /* mask of overloaded cpus in the domain*/
    atomic_t   rto_count; /* number of overloaded cpus */
   ....
};
           

4，cpu的优先级管理

每个CPU可以处于如下任何一种状态：INVALID，IDLE，NORMAL，RT1，．．．，RT99，处于INVALID状态的CPU不适合任务路由。系统使用2维位图来维护这些状态信息。第1个位图用于处于同一优先级的不同CPU，CPU优先级是指rt_rq结构中的highest_prio变量；第2个位图用于不同的优先级。

#define CPUPRI_NR_PRIORITIES (MAX_RT_PRIO + 2)
struct cpupri {
    struct cpupri_vec  pri_to_cpu[CPUPRI_NR_PRIORITIES];     //pri_to_cpu位图可以快速找到优先级最低的cpu集合
    int                cpu_to_pri[NR_CPUS]; // 各个cpu对应优先级
};
           

5,push和pull算法

push算法

push_rt_task - 把当前run_queue中多余的实时进程推给其他run_queue。需要满足以下条件：

1、每次push一个进程，这个进程的优先级在当前run_queue中是第二高的（优先级最高的进程必定正在运行，不需要移动）；

2、目标run_queue上正在运行的不是实时进程（是普通进程），或者是top-N中优先级最低的实时进程，且优先级低于被push的进程；

3、被push的进程允许在目标CPU上运行（没有亲和性限制）；

4、满足条件的目标run_queue可能存在多个（可能多个CPU上都没有实时进程在运行），应该选择与当前CPU最具亲缘性的一组CPU中的第一个CPU所对应的run_queue作为push的目标（顺着sched_domain--调度域--逐步往上，找到第一个包含目标CPU的sched_domain。见后面关于sched_domain的描述）；

该函数会在以下时间点被调用：

1、非正在运行的普通进程变成实时进程时（比如通过sched_setscheduler系统调用）；

2、发生调度之后（这时候可能有一个实时进程被更高优先级的实时进程抢占了）；

3、实时进程被唤醒之后，如果不能马上在当前CPU上运行（它不是当前CPU上优先级最高的进程）；

pull算法

pull_rt_task - 把其他CPU的run_queue中的实时进程pull过来，放到当前CPU的run_queue中。被pull过来的实时进程要满足以下条件：

1、进程是其所在的run_queue中优先级第二高的（优先级最高的进程必定正在运行，不需要移动）；

2、进程的优先级比当前run_queue中最高优先级的进程还要高；

3、进程允许在当前CPU上运行（没有亲和性限制）；

该函数会在以下时间点被调用：

1、发生调度之前，如果prev进程（将要被替换下去的进程）是实时进程，且优先级高于当前run_queue中优先级最高的实时进程（这说明prev进程已经离开TASK_RUNNING状态了，否则它不会让位于比它优先级低的进程）；

2、正在运行的实时进程优先级被调低时（比如通过sched_setparam系统调用）；

3、正在运行的实时进程变成普通进程时（比如通过sched_setscheduler系统调用）；