Linux进程调度 - 实时调度器 LoyenWang

背景

• Read the fucking source code! --By 鲁迅
• A picture is worth a thousand words. --By 高尔基

说明：

1. Kernel版本：4.14
2. ARM64处理器，Contex-A53，双核
3. 使用工具：Source Insight 3.5， Visio

1. 概述

在Linux内核中，实时进程总是比普通进程的优先级要高，实时进程的调度是由Real Time Scheduler(RT调度器)来管理，而普通进程由CFS调度器来管理。

实时进程的调度方式： 静态优先级策略+先进先出策略/轮转策略
系统调度时，首先执行静态优先级策略，会根据用户设定的静态优先级对实时进程进行排序，先执行优先级高的进程直到完毕，再执行优先级低的进程。当有数个实时进程的优先级相同时，有先进先出策略（SCHED_FIFO）和轮转策略（SCHED_RR）供用户选择。若为先进先出策略，系统会根据进程出现在队列上的位置选择执行的顺序；若为轮转策略，系统会为实时进程分配时间片， 当一个时间片消耗完毕，就会执行下一个相同优先级的进程，如此循环往复，直到同优先级的所有进程执行完毕。实时进程支持的调度策略为：SCHED_FIFO和SCHED_RR。

前边的系列文章都是针对CFS调度器来分析的，包括了CPU负载、组调度、Bandwidth控制等，本文的RT调度器也会从这些角度来分析，如果看过之前的系列文章，那么这篇文章理解起来就会更容易点了。

前戏不多，直奔主题。

2. 数据结构

有必要把关键的结构体罗列一下了：

• struct rq：运行队列，每个CPU都对应一个；
• struct rt_rq：实时运行队列，用于管理实时任务的调度实体；
• struct sched_rt_entity：实时调度实体，用于参与调度，功能与struct sched_entity类似；
• struct task_group：组调度结构体；
• struct rt_bandwidth：带宽控制结构体；

老规矩，先上张图，捋捋这些结构之间的关系吧：

• 从图中的结构组织关系看，与CFS调度器基本一致，区别在与CFS调度器是通过红黑树来组织调度实体，而RT调度器使用的是优先级队列来组织实时调度实体；
• rt_rq运行队列，维护了100个优先级的队列（链表），优先级0-99，从高到底；
• 调度器管理的对象是调度实体，任务task_struct和任务组task_group都是通过内嵌调度实体的数据结构，来最终参与调度管理的；
• task_group任务组调度，自身为每个CPU维护rt_rq，用于存放自己的子任务或者子任务组，子任务组又能往下级联，因此可以构造成树；

上述结构体中，struct rq和struct task_group，在前文中都分析过。
下边针对RT运行队列相关的关键结构体，简单注释下吧：

struct sched_rt_entity {
	struct list_head		run_list;   //用于加入到优先级队列中
	unsigned long			timeout;    //设置的时间超时
	unsigned long			watchdog_stamp;     //用于记录jiffies值
	unsigned int			time_slice;     //时间片，100ms，
	unsigned short			on_rq;
	unsigned short			on_list;
 
	struct sched_rt_entity		*back;  //临时用于从上往下连接RT调度实体时使用
#ifdef CONFIG_RT_GROUP_SCHED
	struct sched_rt_entity		*parent;    //指向父RT调度实体
	/* rq on which this entity is (to be) queued: */
	struct rt_rq			*rt_rq;     //RT调度实体所属的实时运行队列，被调度
	/* rq "owned" by this entity/group: */
	struct rt_rq			*my_q;  //RT调度实体所拥有的实时运行队列，用于管理子任务或子组任务
#endif
} __randomize_layout;
 
 
/* Real-Time classes' related field in a runqueue: */
struct rt_rq {
	struct rt_prio_array active;    //优先级队列，100个优先级的链表，并定义了位图，用于快速查询
	unsigned int rt_nr_running; //在RT运行队列中所有活动的任务数
	unsigned int rr_nr_running;
#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
	struct {
		int curr; /* highest queued rt task prio */     //当前RT任务的最高优先级
#ifdef CONFIG_SMP
		int next; /* next highest */        //下一个要运行的RT任务的优先级，如果两个任务都有最高优先级，则curr == next
#endif
	} highest_prio;
#endif
#ifdef CONFIG_SMP
	unsigned long rt_nr_migratory;      //任务没有绑定在某个CPU上时，这个值会增减，用于任务迁移
	unsigned long rt_nr_total;      //用于overload检查
	int overloaded;     //RT运行队列过载，则将任务推送到其他CPU
	struct plist_head pushable_tasks;   //优先级列表，用于推送过载任务
#endif /* CONFIG_SMP */
	int rt_queued;  //表示RT运行队列已经加入rq队列
 
	int rt_throttled;   //用于限流操作
	u64 rt_time;    //累加的运行时，超出了本地rt_runtime时，则进行限制
	u64 rt_runtime;     //分配给本地池的运行时
	/* Nests inside the rq lock: */
	raw_spinlock_t rt_runtime_lock;
 
#ifdef CONFIG_RT_GROUP_SCHED
	unsigned long rt_nr_boosted;    //用于优先级翻转问题解决
 
	struct rq *rq;      //指向运行队列
	struct task_group *tg;  //指向任务组
#endif
};
 
struct rt_bandwidth {
	/* nests inside the rq lock: */
	raw_spinlock_t		rt_runtime_lock;
	ktime_t			rt_period;      //时间周期
	u64			rt_runtime;     //一个时间周期内的运行时间，超过则限流，默认值为0.95ms
	struct hrtimer		rt_period_timer;    //时间周期定时器
	unsigned int		rt_period_active;
};

3. 流程分析

3.1 运行时统计数据

运行时的统计数据更新，是在update_curr_rt函数中完成的：

• update_curr_rt函数功能，主要包括两部分：
  1. 运行时间的统计更新处理；
  2. 如果运行时间超出了分配时间，进行时间均衡处理，并且判断是否需要进行限流，进行了限流则需要将RT队列出队，并重新进行调度；

为了更直观的理解，下边还是来两张图片说明一下：

sched_rt_avg_update更新示意如下：

• rq->age_stamp：在CPU启动后运行队列首次运行时设置起始时间，后续周期性进行更新；
• rt_avg：累计的RT平均运行时间，每0.5秒减半处理，用于计算CFS负载减去RT在CFS负载平衡中使用的时间百分比；

3.2 组调度

RT调度器与CFS调度器的组调度基本类似，CFS调度器的组调度请参考（四）Linux进程调度-组调度及带宽控制。

看一下RT调度器组调度的组织关系图吧：

• 系统为每个CPU都分配了RT运行队列，以及RT调度实体，任务组通过它包含的RT调度实体来参与调度；
• 任务组task_group的RT队列，用于存放归属于该组的任务或子任务组，从而形成级联的结构；

看一下实际的组织示意图：

3.3 带宽控制

请先参考（四）Linux进程调度-组调度及带宽控制。

RT调度器在带宽控制中，调度时间周期设置的为1s，运行时间设置为0.95s：

/*
 * period over which we measure -rt task CPU usage in us.
 * default: 1s
 */
unsigned int sysctl_sched_rt_period = 1000000;
 
/*
 * part of the period that we allow rt tasks to run in us.
 * default: 0.95s
 */
int sysctl_sched_rt_runtime = 950000;

这两个值可以在用户态通过/sys/fs/cgroup/cpu/rt_runtime_us和/sys/fs/cgroup/cpu/rt_period_us来进行设置。

看看函数调用流程：

• init_rt_bandwidth函数在创建分配RT任务组的时候调用，完成的工作是将rt_bandwidth结构体的相关字段进行初始化：设置好时间周期rt_period和运行时间限制rt_runtime，都设置成默认值；
• 可以从用户态通过操作/sys/fs/cgroup/cpu下对应的节点进行设置rt_period和rt_runtime，最终调用的函数是tg_set_rt_bandwidth，在该函数中会从下往上的遍历任务组进行设置时间周期和限制的运行时间；
• 在enqueue_rt_entity将RT调度实体入列时，最终触发start_rt_bandwidth函数执行，当高精度定时器到期时调用do_sched_rt_period_timer函数；
• do_sched_rt_period_timer函数，会去判断该RT运行队列的累计运行时间rt_time与设置的限制运行时间rt_runtime之间的大小关系，以确定是否限流的操作。在这个函数中，如果已经进行了限流操作，会调用balance_time来在多个CPU之间进行时间均衡处理，简单点说，就是从其他CPU的rt_rq队列中匀出一部分时间增加到当前CPU的rt_rq队列中，也就是将当前rt_rt运行队列的限制运行时间rt_runtime增加一部分，其他CPU的rt_rq运行队列限制运行时间减少一部分。

来一张效果示意图：

3.4 调度器函数分析

来一张前文的图：

看一下RT调度器实例的代码：

const struct sched_class rt_sched_class = {
	.next			= &fair_sched_class,
	.enqueue_task		= enqueue_task_rt,
	.dequeue_task		= dequeue_task_rt,
	.yield_task		= yield_task_rt,
 
	.check_preempt_curr	= check_preempt_curr_rt,
 
	.pick_next_task		= pick_next_task_rt,
	.put_prev_task		= put_prev_task_rt,
 
#ifdef CONFIG_SMP
	.select_task_rq		= select_task_rq_rt,
 
	.set_cpus_allowed       = set_cpus_allowed_common,
	.rq_online              = rq_online_rt,
	.rq_offline             = rq_offline_rt,
	.task_woken		= task_woken_rt,
	.switched_from		= switched_from_rt,
#endif
 
	.set_curr_task          = set_curr_task_rt,
	.task_tick		= task_tick_rt,
 
	.get_rr_interval	= get_rr_interval_rt,
 
	.prio_changed		= prio_changed_rt,
	.switched_to		= switched_to_rt,
 
	.update_curr		= update_curr_rt,
};

3.4.1 pick_next_task_rt

pick_next_task_rt函数是调度器用于选择下一个执行任务。流程如下：

• 与CFS调度器不同，RT调度器会在多个CPU组成的domain中，对任务进行pull/push处理，也就是说，如果当前CPU的运行队列中任务优先级都不高，那么会考虑去其他CPU运行队列中找一个更高优先级的任务来执行，以确保按照优先级处理，此外当前CPU也会把任务推送到其他更低优先级的CPU运行队列上。
• _pick_next_task_rt的处理逻辑比较简单，如果实时调度实体是task，则直接查找优先级队列的位图中，找到优先级最高的任务，而如果实时调度实体是task_group，则还需要继续往下进行遍历查找；

关于任务的pull/push，linux提供了struct plist，基于优先级的双链表，其中任务的组织关系如下图：

pull_rt_task的大概示意图如下：

• 当前CPU上的优先级任务不高，从另一个CPU的pushable_tasks链表中找优先级更高的任务来执行；

3.4.2 enqueue_task_rt/dequeue_task_rt

当RT任务进行出队入队时，通过enqueue_task_rt/dequeue_task_rt两个接口来完成，调用流程如下：

• enqueue_task_rt和dequeue_task_rt都会调用dequeue_rt_stack接口，当请求的rt_se对应的是任务组时，会从顶部到请求的rt_se将调度实体出列；
• 任务添加到rt运行队列时，如果存在多个任务可以分配给多个CPU，设置overload，用于任务的迁移；

有点累了，收工了。

本文主要关注实时进程，及FIFO和RR调度策略的区别。

主要分析rt_sched_class各函数；然后通过可视化，更直观明白的看出两者的区别，也通过RR_TIMESLICE可以看出时隙对调度的影响。

1. 实时进程FIFO和RR区别

Linux进程可以分为两大类：实时进程和普通进程。

实时进程与普通进程的根本不同之处：如果系统中有一个实时进程且可运行，那么调度器总是会选择它，除非另有一个优先级更高的实时进程。

实时进程分为两种：

SCHED_FIFO：没有时间片，在被调度器选择之后，可以运行任意长时间。

SCHED_RR：有时间片，其值在进程运行时会减少。在所有的时间段都到期后，则该值重置为初始值，而进程则置于队列末尾。这确保了在有几个优先级相同的SCHED_RR进程的情况下，它们总是依次执行。

参考资料：《linux进程调度方法(SCHED_OTHER,SCHED_FIFO,SCHED_RR)》

2. 实时调度类代码分析

实时调度器是整个调度器框架的一部分，所以首先需要了解其在框架中的位置；实时调度相关数据结构作为单度部分嵌入到全局中。

比如strcut sched_rt_entity和struct sched_entity对比嵌入到struct task_struct中；strcut rt_rq嵌入到struct rq中。

然后就是实时调度器最核心的区别，实时调度类struct sched_class rt_sched_class。

最后看看进程具备什么条件会使用rt_sched_class作为调度策略，以及rt_sched_class各成员被调用的时机。

下面的代码分析默认CONFIG_RT_GROUP_SCHED关闭。

2.1 实时调度体struct sched_rt_entity

 struct sched_rt_entity表示一个可实时调度的实体，包含了完整的实时调度信息，是struct task_struct的一个成员。

struct task_struct {
...
    int prio, static_prio, normal_prio;
    unsigned int rt_priority;
    const struct sched_class *sched_class;
    struct sched_entity se;
    struct sched_rt_entity rt;
#ifdef CONFIG_CGROUP_SCHED
    struct task_group *sched_task_group;
#endif
    struct sched_dl_entity dl;
...
}

struct sched_rt_entity {
    struct list_head run_list;
    unsigned long timeout;----------------------------------------watchdog计数，用于判断当前进程时间是否超过RLIMIT_RTTIME。
    unsigned long watchdog_stamp;
    unsigned int time_slice;--------------------------------------针对RR调度策略的调度时隙

    struct sched_rt_entity *back;---------------------------------dequeue_rt_stack()中作为临时变量使用
#ifdef CONFIG_RT_GROUP_SCHED
    struct sched_rt_entity    *parent;----------------------------指向上一层调度实体
    /* rq on which this entity is (to be) queued: */
    struct rt_rq        *rt_rq;-----------------------------------当前实时调度实体所在的就绪队列
    /* rq "owned" by this entity/group: */
    struct rt_rq        *my_q;------------------------------------当前实时调度实体的子调度实体所在的就绪队列
#endif
}

2.2 实时就绪队列struct rt_rq

核心调度器用于管理活动进程的主要数据结构称之为就绪队列。各个CPU都有自身的就绪队列，各个活动进程只出现在一个就绪队列中。

在多个CPU上同时运行一个进程是不可能的。

就绪队列是全局调度器许多操作的起点，进程并不是由就绪队列的成员直接管理的。这是各个调度器类的职责，因此各个就绪队列中嵌入了特定于调度器类的子就绪队列。

struct rq用于表示就绪队列：

struct rq {
    /* runqueue lock: */
    raw_spinlock_t lock;

    /*
     * nr_running and cpu_load should be in the same cacheline because
     * remote CPUs use both these fields when doing load calculation.
     */
    unsigned int nr_running;-----------------------指定了队列上可运行进程的数目，不考虑器有限激活调度类。
...
    #define CPU_LOAD_IDX_MAX 5
    unsigned long cpu_load[CPU_LOAD_IDX_MAX];------用于跟踪此前的负荷状态。
    unsigned long last_load_update_tick;
...
    /* capture load from *all* tasks on this cpu: */
    struct load_weight load;-----------------------提供了就绪队列当前负荷的度量。队列的负荷本质上与队列上当前活动进程的数成正比，其中的各个进程又有优先级作为权重。
    unsigned long nr_load_updates;
    u64 nr_switches;

    struct cfs_rq cfs;-----------------------------完全公平调度器嵌入的子就绪队列
    struct rt_rq rt;-------------------------------实时调度器嵌入的子就绪队列
    struct dl_rq dl;
...

    /*
     * This is part of a global counter where only the total sum
     * over all CPUs matters. A task can increase this counter on
     * one CPU and if it got migrated afterwards it may decrease
     * it on another CPU. Always updated under the runqueue lock:
     */
    unsigned long nr_uninterruptible;

    struct task_struct *curr, *idle, *stop;--------curr当前运行的进程task_struct实例，idle空闲进程的task_struct实例。
    unsigned long next_balance;
    struct mm_struct *prev_mm;

    unsigned int clock_skip_update;
    u64 clock;-------------------------------------用于实现就绪队列自身的时钟。
    u64 clock_task;

    atomic_t nr_iowait;

#ifdef CONFIG_SMP
    struct root_domain *rd;
    struct sched_domain *sd;

    unsigned long cpu_capacity;

    unsigned char idle_balance;
    /* For active balancing */
    int post_schedule;
    int active_balance;
    int push_cpu;
    struct cpu_stop_work active_balance_work;
    /* cpu of this runqueue: */
    int cpu;
    int online;

    struct list_head cfs_tasks;

    u64 rt_avg;
    u64 age_stamp;
    u64 idle_stamp;
    u64 avg_idle;

    /* This is used to determine avg_idle's max value */
    u64 max_idle_balance_cost;
#endif
...
}

具有相同优先级的所有实时进程都保存在一个链表中，表头为active.queue[prio]，而active.bitmap位图中的每个比特位对应于一个链表，凡包含了进程的链表，对应的比特位则置位。如果链表中没有进程，则对应的比特位不置位。

 struct rt_prio_array是一组链表，每个优先级对应一个链表。还维护一个bitmap，其中实时进程优先级为0~99，再加上1bit的定界符。

当某个优先级别上有进程被插入列表时，相应的比特位就被置位。

通常用sched_find_first_bit()函数来查询该bitmap，他返回当前被置位的最高优先级的数组下标。

在实时调度中，运行进程根据优先级放到对应的队列里面，对于相同的优先级进程后面来的进程放到同一优先级队列的末尾。

对于FIFO/RR调度，各自的进程需要设置相关的属性。进程运行时，要根据task中的这些属性判断和设置，放弃CPU的时机。

struct rt_prio_array {
    DECLARE_BITMAP(bitmap, MAX_RT_PRIO+1); /* include 1 bit for delimiter */
    struct list_head queue[MAX_RT_PRIO];---------------------------按优先级排列的实时调度器的就绪队列
}

核心调度器的就绪队列也包含了用于实时进程的子就绪队列，是一个嵌入的struct rt_rq实例。

struct rt_rq {
    struct rt_prio_array active;
    unsigned int rt_nr_running;
#if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
    struct {
        int curr; /* highest queued rt task prio */---------------最高实时任务的优先级
#ifdef CONFIG_SMP
        int next; /* next highest */------------------------------下一个实时任务最高优先级
#endif
    } highest_prio;
#endif
#ifdef CONFIG_SMP
    unsigned long rt_nr_migratory;
    unsigned long rt_nr_total;
    int overloaded;
    struct plist_head pushable_tasks;
#endif
    int rt_queued;

    int rt_throttled;------------------------------------------------当前队列的实时调度是否受限
    u64 rt_time;-----------------------------------------------------当前队列的累积运行时间
    u64 rt_runtime;--------------------------------------------------当前队列的单个period周期内最大运行时间
    /* Nests inside the rq lock: */
    raw_spinlock_t rt_runtime_lock;

#ifdef CONFIG_RT_GROUP_SCHED
    unsigned long rt_nr_boosted;

    struct rq *rq;
    struct task_group *tg;
#endif
}

  

2.3 实时调度器类struct sched_class

调度器类提供了通用调度器和各个调度方法之间的关联，

每个调度类都定义了一套操作方法struct sched_class，

struct sched_class {
    const struct sched_class *next;

    void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);-------向就绪队列添加一个新进程，在进程从睡眠状态变为运行状态时，即发生该操作。
    void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);-------将一个进程从就绪队列去除，在进程从可运行状态切换到不可运行状态时，就会发生该操作。内核有可能因为其他理由将进程从就绪队列去除，比如进程的优先级可能需要改变。
    void (*yield_task) (struct rq *rq);-------------------------------------------在进程想要自愿放弃对处理器的控制权时使用，这导致内核调用yield_task。
    bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);

    void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);-用一个新唤醒的进程来抢占当前进程

    /*
     * It is the responsibility of the pick_next_task() method that will
     * return the next task to call put_prev_task() on the @prev task or
     * something equivalent.
     *
     * May return RETRY_TASK when it finds a higher prio class has runnable
     * tasks.
     */
    struct task_struct * (*pick_next_task) (struct rq *rq,
                        struct task_struct *prev);--------------------------------用于选择下一个将要运行的进程，而put_prev_task则在用另一个进程代替当前运行的进程之前调用。
    void (*put_prev_task) (struct rq *rq, struct task_struct *p);

#ifdef CONFIG_SMP
    int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
    void (*migrate_task_rq)(struct task_struct *p, int next_cpu);

    void (*post_schedule) (struct rq *this_rq);
    void (*task_waking) (struct task_struct *task);
    void (*task_woken) (struct rq *this_rq, struct task_struct *task);

    void (*set_cpus_allowed)(struct task_struct *p,
                 const struct cpumask *newmask);

    void (*rq_online)(struct rq *rq);
    void (*rq_offline)(struct rq *rq);
#endif

    void (*set_curr_task) (struct rq *rq);----------------------------------------在进程的调度策略发生变化时，需要调用set_curr_task。
    void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);---------在每次激活周期性调度器时，由周期性调度器调用。
    void (*task_fork) (struct task_struct *p);------------------------------------用于建立fork系统调用和调度器之间的关联
    void (*task_dead) (struct task_struct *p);

    /*
     * The switched_from() call is allowed to drop rq->lock, therefore we
     * cannot assume the switched_from/switched_to pair is serliazed by
     * rq->lock. They are however serialized by p->pi_lock.
     */
    void (*switched_from) (struct rq *this_rq, struct task_struct *task);
    void (*switched_to) (struct rq *this_rq, struct task_struct *task);
    void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
                 int oldprio);

    unsigned int (*get_rr_interval) (struct rq *rq,
                     struct task_struct *task);

    void (*update_curr) (struct rq *rq);

#ifdef CONFIG_FAIR_GROUP_SCHED
    void (*task_move_group) (struct task_struct *p, int on_rq);
#endif
}

 实时调度器类对应rt_sched_class：

const struct sched_class rt_sched_class = {
    .next            = &fair_sched_class,
    .enqueue_task        = enqueue_task_rt,----------------------------将一个task放入到就绪队列头或者尾部
    .dequeue_task        = dequeue_task_rt,----------------------------将一个task从就绪队列末尾
    .yield_task        = yield_task_rt,--------------------------------主动放弃执行

    .check_preempt_curr    = check_preempt_curr_rt,

    .pick_next_task        = pick_next_task_rt,------------------------核心调度器选择就绪队列的哪个任务将要被调度，prev是将要被调度出的任务，返回值是将要被调度的任务。
    .put_prev_task        = put_prev_task_rt,--------------------------当一个任务将要被调度出时执行

#ifdef CONFIG_SMP
    .select_task_rq        = select_task_rq_rt,------------------------核心调度器给任务选定CPU，用于将任务分发到不同CPU上执行。

    .set_cpus_allowed       = set_cpus_allowed_rt,
    .rq_online              = rq_online_rt,
    .rq_offline             = rq_offline_rt,
    .post_schedule        = post_schedule_rt,
    .task_woken        = task_woken_rt,
    .switched_from        = switched_from_rt,
#endif

    .set_curr_task          = set_curr_task_rt,------------------------当任务修改其调度类或修改其它任务组时，将调用这个函数。
    .task_tick        = task_tick_rt,----------------------------------当时钟中断出发时被调用，主要更新进程运行统计信息以及是否需要调度。

    .get_rr_interval    = get_rr_interval_rt,

    .prio_changed        = prio_changed_rt,
    .switched_to        = switched_to_rt,

    .update_curr        = update_curr_rt,
}

关于for_each_sched_rt_entity的使用很频繁，通过它可以遍历当前实时调度实体所在组的所有调度实体。

2.3.1 enqueue_task_rt()和dequeue_task_rt()

先了解一下两个函数的flag，有助于理解这两函数。

#define ENQUEUE_WAKEUP        0x01--------------当前进程刚变为可执行状态
#define ENQUEUE_HEAD        0x02----------------将当前进程放入就绪队列的头部
#ifdef CONFIG_SMP
#define ENQUEUE_WAKING        0x04    /* sched_class::task_waking was called */
#else
#define ENQUEUE_WAKING        0x00
#endif
#define ENQUEUE_REPLENISH    0x08--------------
#define ENQUEUE_RESTORE    0x10

#define DEQUEUE_SLEEP        0x01---------------当前进程不再可运行
#define DEQUEUE_SAVE        0x02

首先这两个函数的调用轨迹是：enqueue_task()->enqueue_task_rt()和dequeue_task()->dequeue_task_rt()。

enqueue_task_rt会根据需要将实时调度实体移到链表头或尾，但是dequeue_task_rt()一定会移到链表末尾。两者都会先判断是否在当前rt_rq上，如果在的话需要先移除。

static void __enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
{
    struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
    struct rt_prio_array *array = &rt_rq->active;
    struct rt_rq *group_rq = group_rt_rq(rt_se);
    struct list_head *queue = array->queue + rt_se_prio(rt_se);-----------通过rt_se得出当前进程的优先级，进而通过array->queue偏移得到当前优先级所在的链表。
...
    if (head)
        list_add(&rt_se->run_list, queue);--------------------------------根据head来执行是插入头部还是插入尾部
    else
        list_add_tail(&rt_se->run_list, queue);
    __set_bit(rt_se_prio(rt_se), array->bitmap);--------------------------当前优先级对应的bitmap置位

    inc_rt_tasks(rt_se, rt_rq);-------------------------------------------更新当前rt_rq的统计信息，比如最高优先级、进程总数等等。
}

static void __dequeue_rt_entity(struct sched_rt_entity *rt_se)
{
    struct rt_rq *rt_rq = rt_rq_of_se(rt_se);
    struct rt_prio_array *array = &rt_rq->active;

    list_del_init(&rt_se->run_list);--------------------------------------将当前进程在rt_rq->active->queue上优先级对应列表上节点删除
    if (list_empty(array->queue + rt_se_prio(rt_se)))
        __clear_bit(rt_se_prio(rt_se), array->bitmap);--------------------如果当前优先级列表为空，则bitmap清零。

    dec_rt_tasks(rt_se, rt_rq);-------------------------------------------类似于inc_rt_tasks反操作。
}

/*
 * Because the prio of an upper entry depends on the lower
 * entries, we must remove entries top - down.
 */
static void dequeue_rt_stack(struct sched_rt_entity *rt_se)
{
    struct sched_rt_entity *back = NULL;

    for_each_sched_rt_entity(rt_se) {
        rt_se->back = back;
        back = rt_se;
    }

    dequeue_top_rt_rq(rt_rq_of_se(back));

    for (rt_se = back; rt_se; rt_se = rt_se->back) {
        if (on_rt_rq(rt_se))--------------------------------------------判断当前的实时调度实体是否已经在rt_rq上，如果已经在在从中摘除。
            __dequeue_rt_entity(rt_se);
    }
}


static void enqueue_rt_entity(struct sched_rt_entity *rt_se, bool head)
{
    struct rq *rq = rq_of_rt_se(rt_se);

    dequeue_rt_stack(rt_se);
    for_each_sched_rt_entity(rt_se)
        __enqueue_rt_entity(rt_se, head);
    enqueue_top_rt_rq(&rq->rt);
}

static void dequeue_rt_entity(struct sched_rt_entity *rt_se)
{
    struct rq *rq = rq_of_rt_se(rt_se);

    dequeue_rt_stack(rt_se);

    for_each_sched_rt_entity(rt_se) {
        struct rt_rq *rt_rq = group_rt_rq(rt_se);

        if (rt_rq && rt_rq->rt_nr_running)
            __enqueue_rt_entity(rt_se, false);-----------------------------一定会被移到链表尾部
    }
    enqueue_top_rt_rq(&rq->rt);
}

/*
 * Adding/removing a task to/from a priority array:
 */
static void
enqueue_task_rt(struct rq *rq, struct task_struct *p, int flags)
{
    struct sched_rt_entity *rt_se = &p->rt;

    if (flags & ENQUEUE_WAKEUP)
        rt_se->timeout = 0;

    enqueue_rt_entity(rt_se, flags & ENQUEUE_HEAD);------------------------将当前实时调度实体添加到对应优先级链表上，添加到头部还是尾部蜂聚flags是否包含ENQUEUE_HEAD来判断。

    if (!task_current(rq, p) && p->nr_cpus_allowed > 1)
        enqueue_pushable_task(rq, p);
}

static void dequeue_task_rt(struct rq *rq, struct task_struct *p, int flags)
{
    struct sched_rt_entity *rt_se = &p->rt;

    update_curr_rt(rq);
    dequeue_rt_entity(rt_se);----------------------------------------------这里只是将当前实时调度实体移到链表尾部

    dequeue_pushable_task(rq, p);
}

2.3.2 update_curr_rt()

task_sched_runtime()->update_curr_rt()

update_curr_rt()除了更新各种运行时间、总执行时间等等，还会根据时间片使用情况设置当前进程是否可以被调度。

static void update_curr_rt(struct rq *rq)
{
    struct task_struct *curr = rq->curr;
    struct sched_rt_entity *rt_se = &curr->rt;
    u64 delta_exec;

    if (curr->sched_class != &rt_sched_class)---------------------------保证当前进程的调度策略是rt_sched_class
        return;

    delta_exec = rq_clock_task(rq) - curr->se.exec_start;---------------当前进程的单次执行时间
    if (unlikely((s64)delta_exec <= 0))
        return;

    schedstat_set(curr->se.statistics.exec_max,
              max(curr->se.statistics.exec_max, delta_exec));-----------调度统计信息的取最大单次执行时间

    curr->se.sum_exec_runtime += delta_exec;----------------------------当前进程的总执行时间
    account_group_exec_runtime(curr, delta_exec);

    curr->se.exec_start = rq_clock_task(rq);----------------------------更新执行开始时间
    cpuacct_charge(curr, delta_exec);

    sched_rt_avg_update(rq, delta_exec);

    if (!rt_bandwidth_enabled())----------------------------------------当前系统是否打开了RT带宽限制？
        return;

    for_each_sched_rt_entity(rt_se) {-----------------------------------遍历组调度实体，更新统计信息
        struct rt_rq *rt_rq = rt_rq_of_se(rt_se);

        if (sched_rt_runtime(rt_rq) != RUNTIME_INF) {
            raw_spin_lock(&rt_rq->rt_runtime_lock);
            rt_rq->rt_time += delta_exec;-------------------------------实时就绪队列的总执行时间
            if (sched_rt_runtime_exceeded(rt_rq))-----------------------当前rt_rq的运行时间是否超过了分配时间片，如果超过了则将当前进程设置为可调度TIF_NEED_RESCHED。
                resched_curr(rq);
            raw_spin_unlock(&rt_rq->rt_runtime_lock);
        }
    }
}

2.3.3 yield_task_rt()

yield_task_rt()表示当前进程主动暂时放弃执行，调用轨迹是do_sched_yield()->yield_task_rt()。

从下面的代码可以看出，操作很简单，就是将当前的实时调度实体移到所在优先级链表的尾部。

/*
 * Put task to the head or the end of the run list without the overhead of
 * dequeue followed by enqueue.
 */
static void
requeue_rt_entity(struct rt_rq *rt_rq, struct sched_rt_entity *rt_se, int head)
{
    if (on_rt_rq(rt_se)) {
        struct rt_prio_array *array = &rt_rq->active;
        struct list_head *queue = array->queue + rt_se_prio(rt_se);

        if (head)
            list_move(&rt_se->run_list, queue);---------------------------移到队列头部
        else
            list_move_tail(&rt_se->run_list, queue);----------------------移到队列尾部
    }
}

static void requeue_task_rt(struct rq *rq, struct task_struct *p, int head)
{
    struct sched_rt_entity *rt_se = &p->rt;
    struct rt_rq *rt_rq;

    for_each_sched_rt_entity(rt_se) {
        rt_rq = rt_rq_of_se(rt_se);
        requeue_rt_entity(rt_rq, rt_se, head);
    }
}

static void yield_task_rt(struct rq *rq)
{
    requeue_task_rt(rq, rq->curr, 0);---------------------------------------0表示移到链表的末尾
}

2.3.4 task_tick_rt()

task_tick_rt()对于SCHED_FIFO基本不起作用，因为FIFO没有时间片的概念，调用轨迹是scheduler_tick()->task_tick_rt()。

对于采取RR调度策略的进程，每次执行的时间片是由sched_rr_timeslice决定的。

所以sched_rr_timeslice对于RR是一个关键参数，它首先有一个初始值RR_TIMESLICE，注意这个值的单位是jiffies。

  #define RR_TIMESLICE (100 * HZ / 1000)----------------这个定义能保证RR_TIMESLICE无论是多少，其对应的时间总是100ms。

int sched_rr_timeslice = RR_TIMESLICE;


static void task_tick_rt(struct rq *rq, struct task_struct *p, int queued)
{
    struct sched_rt_entity *rt_se = &p->rt;

    update_curr_rt(rq);

    watchdog(rq, p);

    /*
     * RR tasks need a special form of timeslice management.
     * FIFO tasks have no timeslices.
     */
    if (p->policy != SCHED_RR)-----------------------------------只有RR调度策略有time_slice概念
        return;

    if (--p->rt.time_slice)--------------------------------------当前可用时间片在变小，每次减少一个tick。不为0表示当前的时间片没有用完，不需要考虑主动放弃。
        return;

    p->rt.time_slice = sched_rr_timeslice;-----------------------等于time_slice复位。

    /*
     * Requeue to the end of queue if we (and all of our ancestors) are not
     * the only element on the queue
     */
    for_each_sched_rt_entity(rt_se) {
        if (rt_se->run_list.prev != rt_se->run_list.next) {
            requeue_task_rt(rq, p, 0);---------------------------将当前进程移动到链表尾部
            resched_curr(rq);------------------------------------设置当前进程为TIF_NEED_RESCHED，表示可以被调度。
            return;
        }
    }
}

sched_rr_timeslice的另一个相关点是通过/proc/sys/kernel/sched_rr_timeslice_ms进行修改。

这里有需要注意的地方，写入的参数单位是ms，但是读出来的单位是当前系统的jiffies。

int sched_rr_handler(struct ctl_table *table, int write,
        void __user *buffer, size_t *lenp,
        loff_t *ppos)
{
    int ret;
    static DEFINE_MUTEX(mutex);

    mutex_lock(&mutex);
    ret = proc_dointvec(table, write, buffer, lenp, ppos);
    /* make sure that internally we keep jiffies */
    /* also, writing zero resets timeslice to default */
    if (!ret && write) {
        sched_rr_timeslice = sched_rr_timeslice <= 0 ?
            RR_TIMESLICE : msecs_to_jiffies(sched_rr_timeslice);----------写入的参数经过msecs_to_jiffies将ms转换成了jiffes。
    }
    mutex_unlock(&mutex);
    return ret;
}


static struct ctl_table kern_table[] = {
...
    {
        .procname    = "sched_rr_timeslice_ms",
        .data        = &sched_rr_timeslice,-------------------------------读的参数单位是jiffies
        .maxlen        = sizeof(int),
        .mode        = 0644,
        .proc_handler    = sched_rr_handler,
    },
...
    { }
}

2.3.5 get_rr_interval_rt()

这个函数很简单，调用轨迹是do_sched_rr_get_interval()->get_rr_interval_rt()。

就是检查当前的调度策略是不是RR，然后返回sched_rr_timeslice参数。

static unsigned int get_rr_interval_rt(struct rq *rq, struct task_struct *task)
{
    /*
     * Time slice is 0 for SCHED_FIFO tasks
     */
    if (task->policy == SCHED_RR)
        return sched_rr_timeslice;
    else
        return 0;
}

2.3.6 check_preempt_curr_rt()

check_preempt_curr_rt()用于检查是否满足可抢占的条件，调用轨迹是check_preempt_curr()->check_preempt_curr_rt()。

static void check_preempt_curr_rt(struct rq *rq, struct task_struct *p, int flags)
{
    if (p->prio < rq->curr->prio) {--------------------------------如果给定进程p实时进程的优先级小于就绪队列当前进程优先级，说明p的优先级更高。
        resched_curr(rq);------------------------------------------将就绪队列上的当前进程设置为TIF_NEED_RESCHED。
        return;
    }

#ifdef CONFIG_SMP
    /*
     * If:
     *
     * - the newly woken task is of equal priority to the current task
     * - the newly woken task is non-migratable while current is migratable
     * - current will be preempted on the next reschedule
     *
     * we should check to see if current can readily move to a different
     * cpu.  If so, we will reschedule to allow the push logic to try
     * to move current somewhere else, making room for our non-migratable
     * task.
     */
    if (p->prio == rq->curr->prio && !test_tsk_need_resched(rq->curr))
        check_preempt_equal_prio(rq, p);
#endif
}

2.3.7 pick_next_task_rt()和put_next_task_rt()

 pick_next_task_rt()挑选下一个要被执行的实时任务，调用轨迹是schedule()->__schedule()->pick_next_task()->pick_next_task_rt()。

static struct sched_rt_entity *pick_next_rt_entity(struct rq *rq,
                           struct rt_rq *rt_rq)
{
    struct rt_prio_array *array = &rt_rq->active;
    struct sched_rt_entity *next = NULL;
    struct list_head *queue;
    int idx;

    idx = sched_find_first_bit(array->bitmap);-----------------------------获取当前实时就绪队列上的最高优先级，idx对应了优先级
    BUG_ON(idx >= MAX_RT_PRIO);

    queue = array->queue + idx;--------------------------------------------获取最高优先级对应的链表
    next = list_entry(queue->next, struct sched_rt_entity, run_list);------从链表头获取实时调度实体

    return next;
}


static struct task_struct *_pick_next_task_rt(struct rq *rq)
{
    struct sched_rt_entity *rt_se;
    struct task_struct *p;
    struct rt_rq *rt_rq  = &rq->rt;

    do {
        rt_se = pick_next_rt_entity(rq, rt_rq);---------------------------从rt_rq获取最高优先级对应的实时调度实体
        BUG_ON(!rt_se);
        rt_rq = group_rt_rq(rt_se);
    } while (rt_rq);

    p = rt_task_of(rt_se);
    p->se.exec_start = rq_clock_task(rq);---------------------------------更新当前进程的开始执行事件

    return p;
}

static struct task_struct *
pick_next_task_rt(struct rq *rq, struct task_struct *prev)
{
    struct task_struct *p;
    struct rt_rq *rt_rq = &rq->rt;
...
    /*
     * We may dequeue prev's rt_rq in put_prev_task().
     * So, we update time before rt_nr_running check.
     */
    if (prev->sched_class == &rt_sched_class)
        update_curr_rt(rq);

    if (!rt_rq->rt_queued)
        return NULL;

    put_prev_task(rq, prev);----------------调用put_prev_task_rt()

    p = _pick_next_task_rt(rq);-------------从rq中选择最合适的进程，并返回进程描述符

    /* The running task is never eligible for pushing */
    dequeue_pushable_task(rq, p);

    queue_push_tasks(rq);

    return p;
}

  

put_prev_task_rt()用另一个进程代替当前运行的进程，调用轨迹是put_prev_task()->put_prev_task_rt()。

static void put_prev_task_rt(struct rq *rq, struct task_struct *p)
{
    update_curr_rt(rq);

    /*
     * The previous task needs to be made eligible for pushing
     * if it is still active
     */
    if (on_rt_rq(&p->rt) && p->nr_cpus_allowed > 1)
        enqueue_pushable_task(rq, p);
}

  

2.3.8 prio_changed_rt()

prio_changed_rt()用于判断修改了进程优先级之后，判断是否需要重新调度，调用轨迹是check_class_changed()->prio_changed_rt()。

/*
 * Priority of the task has changed. This may cause
 * us to initiate a push or pull.
 */
static void
prio_changed_rt(struct rq *rq, struct task_struct *p, int oldprio)
{
    if (!task_on_rq_queued(p))
        return;

    if (rq->curr == p) {
#ifdef CONFIG_SMP
        /*
         * If our priority decreases while running, we
         * may need to pull tasks to this runqueue.
         */
        if (oldprio < p->prio)
            queue_pull_task(rq);

        /*
         * If there's a higher priority task waiting to run
         * then reschedule.
         */
        if (p->prio > rq->rt.highest_prio.curr)
            resched_curr(rq);
#else
        /* For UP simply resched on drop of prio */
        if (oldprio < p->prio)----------------------------------如果其优先级变大，说明优先级变低了，需要重新调度。
            resched_curr(rq);
#endif /* CONFIG_SMP */
    } else {
        /*
         * This task is not running, but if it is
         * greater than the current running task
         * then reschedule.
         */
        if (p->prio < rq->curr->prio)---------------------------如果进程p的优先级比rq->curr的优先级大的话，说明rq->curr的优先级较低，需要设置重新调度。
            resched_curr(rq);
    }
}

2.3.9 switched_to_rt()

switched_to_rt()用于修改了调度类的情况，调用轨迹是check_class_changed()->switched_to_rt()。

/*
 * When switching a task to RT, we may overload the runqueue
 * with RT tasks. In this case we try to push them off to
 * other runqueues.
 */
static void switched_to_rt(struct rq *rq, struct task_struct *p)
{
    /*
     * If we are already running, then there's nothing
     * that needs to be done. But if we are not running
     * we may need to preempt the current running task.
     * If that current running task is also an RT task
     * then see if we can move to another run queue.
     */
    if (task_on_rq_queued(p) && rq->curr != p) {
#ifdef CONFIG_SMP
        if (p->nr_cpus_allowed > 1 && rq->rt.overloaded)
            queue_push_tasks(rq);
#endif /* CONFIG_SMP */
        if (p->prio < rq->curr->prio)
            resched_curr(rq);
    }
}

2.3.10 set_curr_task_rt()

static void set_curr_task_rt(struct rq *rq)
{
    struct task_struct *p = rq->curr;

    p->se.exec_start = rq_clock_task(rq);

    /* The running task is never eligible for pushing */
    dequeue_pushable_task(rq, p);
}

2.4 RT Bandwith

RT进程和普通进程之间有一个分配带宽的比例，默认情况是RT:CFS=95:5。

通过/proc/sys/kernel/sched_rt_period_us和/proc/sys/kernel/sched_rt_runtime_us来设置。

如果设置sched_rt_runtime_us为-1，则禁止对RT进程的带宽限制。

 2.4.1 RT进程带宽初始化

在系统开机的时候start_kernel()->sched_init()->init_rt_bandwidth()进行带宽的设置。

init_rt_bandwidth()将sysctl_sched_rt_period和sysctl_sched_rt_runtime设置到def_rt_bandwidth，并初始化def_rt_bandwidth->rt_pediod_timer，处理函数是sched_rt_period_timer()。

void __init sched_init(void)
{
...
    init_rt_bandwidth(&def_rt_bandwidth,
            global_rt_period(), global_rt_runtime());
...
}

void init_rt_bandwidth(struct rt_bandwidth *rt_b, u64 period, u64 runtime)
{
    rt_b->rt_period = ns_to_ktime(period);
    rt_b->rt_runtime = runtime;

    raw_spin_lock_init(&rt_b->rt_runtime_lock);

    hrtimer_init(&rt_b->rt_period_timer,
            CLOCK_MONOTONIC, HRTIMER_MODE_REL);
    rt_b->rt_period_timer.function = sched_rt_period_timer;
}

start_rt_bandwidth启动rt_bandwidth->rt_period_timer，周期为rt_bandwidth->rt_period，这就保证每隔一定时间回去检查超时问题。

static void start_rt_bandwidth(struct rt_bandwidth *rt_b)
{
    if (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF)
        return;

    raw_spin_lock(&rt_b->rt_runtime_lock);
    if (!rt_b->rt_period_active) {
        rt_b->rt_period_active = 1;
        hrtimer_forward_now(&rt_b->rt_period_timer, rt_b->rt_period);
        hrtimer_start_expires(&rt_b->rt_period_timer, HRTIMER_MODE_ABS_PINNED);
    }
    raw_spin_unlock(&rt_b->rt_runtime_lock);
}

sched_rt_period_timer是rt_bandwidth->rt_period_timer定时器的超时函数。

每个周期到达时，将rt_rq->rt_time更新一下，并且根据需要将当前进程重新调度一下。如果当前rt_rq处于idle状态，那么可以停止相应的timer。

static enum hrtimer_restart sched_rt_period_timer(struct hrtimer *timer)
{
    struct rt_bandwidth *rt_b =
        container_of(timer, struct rt_bandwidth, rt_period_timer);
    int idle = 0;
    int overrun;

    raw_spin_lock(&rt_b->rt_runtime_lock);
    for (;;) {
        overrun = hrtimer_forward_now(timer, rt_b->rt_period);--------------overrun表示定时器执行已经超过了interval时间，覆盖到下一次定时一部分，overrun是覆盖次数。
        if (!overrun)-------------------------------------------------------overrun为0跳出本次for循环
            break;

        raw_spin_unlock(&rt_b->rt_runtime_lock);
        idle = do_sched_rt_period_timer(rt_b, overrun);---------------------更新对应rt_rq->rt_time，并且根据需要设置对应进程重新调度。
        raw_spin_lock(&rt_b->rt_runtime_lock);
    }
    if (idle)
        rt_b->rt_period_active = 0;
    raw_spin_unlock(&rt_b->rt_runtime_lock);

    return idle ? HRTIMER_NORESTART : HRTIMER_RESTART;-----------------------根据是否idle决定是否重启rt_bandwidth->rt_period_timer。
}

static int do_sched_rt_period_timer(struct rt_bandwidth *rt_b, int overrun)
{
    int i, idle = 1, throttled = 0;
    const struct cpumask *span;

    span = sched_rt_period_mask();

    for_each_cpu(i, span) {
        int enqueue = 0;
        struct rt_rq *rt_rq = sched_rt_period_rt_rq(rt_b, i);
        struct rq *rq = rq_of_rt_rq(rt_rq);

        raw_spin_lock(&rq->lock);
        if (rt_rq->rt_time) {-----------------------------------------------------当前累计执行时间不为0
            u64 runtime;

            raw_spin_lock(&rt_rq->rt_runtime_lock);
            if (rt_rq->rt_throttled)
                balance_runtime(rt_rq);-------------------------------------------如果当前CPU的rt_rq->rt_runtime时间用完，尝试从其它CPU借时间。
            runtime = rt_rq->rt_runtime;------------------------------------------每一个周期允许运行的最长时间
            rt_rq->rt_time -= min(rt_rq->rt_time, overrun*runtime);---------------如果overrun为1，那么rt_rq->rt_time减去一个runtime，否则rt_rq->rt_time保持不变。
            if (rt_rq->rt_throttled && rt_rq->rt_time < runtime) {
                rt_rq->rt_throttled = 0;
                enqueue = 1;

                if (rt_rq->rt_nr_running && rq->curr == rq->idle)
                    rq_clock_skip_update(rq, false);
            }
            if (rt_rq->rt_time || rt_rq->rt_nr_running)
                idle = 0;
            raw_spin_unlock(&rt_rq->rt_runtime_lock);
        } else if (rt_rq->rt_nr_running) {
            idle = 0;
            if (!rt_rq_throttled(rt_rq))
                enqueue = 1;
        }
        if (rt_rq->rt_throttled)
            throttled = 1;

        if (enqueue)
            sched_rt_rq_enqueue(rt_rq);--------------------------------------标记当前rt_rq所在进程为TIF_NEED_RESCHED
        raw_spin_unlock(&rq->lock);
    }

    if (!throttled && (!rt_bandwidth_enabled() || rt_b->rt_runtime == RUNTIME_INF))
        return 1;

    return idle;
}

2.4.2 sysctl调节RT进程带宽及占比

系统启动是有默认参数，还可以通过sysct进行设置，l操作交给sched_rt_handler()，

unsigned int sysctl_sched_rt_period = 1000000;
int sysctl_sched_rt_runtime = 950000;

static struct ctl_table kern_table[] = {
...
    {
        .procname    = "sched_rt_period_us",
        .data        = &sysctl_sched_rt_period,
        .maxlen        = sizeof(unsigned int),
        .mode        = 0644,
        .proc_handler    = sched_rt_handler,
    },
    {
        .procname    = "sched_rt_runtime_us",
        .data        = &sysctl_sched_rt_runtime,
        .maxlen        = sizeof(int),
        .mode        = 0644,
        .proc_handler    = sched_rt_handler,
    },
...
}

int sched_rt_handler(struct ctl_table *table, int write,
        void __user *buffer, size_t *lenp,
        loff_t *ppos)
{
    int old_period, old_runtime;
    static DEFINE_MUTEX(mutex);
    int ret;

    mutex_lock(&mutex);
    old_period = sysctl_sched_rt_period;
    old_runtime = sysctl_sched_rt_runtime;

    ret = proc_dointvec(table, write, buffer, lenp, ppos);

    if (!ret && write) {
        ret = sched_rt_global_validate();------------验证sysctl_sched_rt_period和sysctl_sched_rt_runtime有效性
        if (ret)
            goto undo;
...
        ret = sched_rt_global_constraints();---------更新每个CPU的rt_rq->rt_runtime
        if (ret)
            goto undo;

        sched_rt_do_global();------------------------设置sysctl_sched_rt_runtime和sysctl_sched_rt_period到def_rt_bandwidth中
        sched_dl_do_global();
    }
    if (0) {
undo:
        sysctl_sched_rt_period = old_period;
        sysctl_sched_rt_runtime = old_runtime;
    }
    mutex_unlock(&mutex);

    return ret;
}

static void sched_rt_do_global(void)
{
    def_rt_bandwidth.rt_runtime = global_rt_runtime();
    def_rt_bandwidth.rt_period = ns_to_ktime(global_rt_period());
}

static inline u64 global_rt_period(void)
{
    return (u64)sysctl_sched_rt_period * NSEC_PER_USEC;
}

static inline u64 global_rt_runtime(void)
{
    if (sysctl_sched_rt_runtime < 0)
        return RUNTIME_INF;

    return (u64)sysctl_sched_rt_runtime * NSEC_PER_USEC;
}

static inline u64 sched_rt_runtime(struct rt_rq *rt_rq)
{
    return rt_rq->rt_runtime;
}

static inline u64 sched_rt_period(struct rt_rq *rt_rq)
{
    return ktime_to_ns(def_rt_bandwidth.rt_period);
}

rt_bandwidth_enabled()用于判断当前系统是否打开了RT带宽限制，这也是设置sched_rt_runtime_us为-1就可以关闭带宽限制的原因。

sched_rt_runtime_exceeded()判断当前rt_rq是否超出分配的可执行时间。

static inline int rt_bandwidth_enabled(void)
{
    return sysctl_sched_rt_runtime >= 0;
}


static int sched_rt_runtime_exceeded(struct rt_rq *rt_rq)
{
    u64 runtime = sched_rt_runtime(rt_rq);------------------------获取rt_rq->rt_runtime，也即当前CPU的RT进程总执行时间的限制。
...
    runtime = sched_rt_runtime(rt_rq);
    if (runtime == RUNTIME_INF)
        return 0;

    if (rt_rq->rt_time > runtime) {-------------------------------当前CUP的RT进程执行时间已经超出执行时间限制。
        struct rt_bandwidth *rt_b = sched_rt_bandwidth(rt_rq);

        /*
         * Don't actually throttle groups that have no runtime assigned
         * but accrue some time due to boosting.
         */
        if (likely(rt_b->rt_runtime)) {
            rt_rq->rt_throttled = 1;
            printk_deferred_once("sched: RT throttling activated\n");
        } else {
            /*
             * In case we did anyway, make it go away,
             * replenishment is a joke, since it will replenish us
             * with exactly 0 ns.
             */
            rt_rq->rt_time = 0;
        }

        if (rt_rq_throttled(rt_rq)) {
            sched_rt_rq_dequeue(rt_rq);
            return 1;----------------------------------------------表示当前rt_rq的执行事件已经超额，需要放弃控制权。
        }
    }

    return 0;
}

可能导致重新调度的点包括，update_curr_rt()中sched_rt_runtime_exceeded()时间用完。

或者rt_bandwidth->rt_period_timer超时。

或者实时进程改变了优先级switched_to_rt()等等。

这也是设置RT带宽参数能保证RT进程用完执行事件后，留一段事件给普通进程使用的原因。

2.5 何时进程会采用rt_sched_class调度类

2.5.1 哪些情况设置rt_sched_class调度策略

主要在do_fork()和sched_setscheduler()两个函数中进行调度器相关设置。

2.5.1.1 shed_fork

sched_fork主要被系统调用fork调用，do_fork()->copy_process()->sched_fork()。

sched_fork()主要进行调度器相关设置，其中一个重要操作就是设置调度器类。

static inline int rt_prio(int prio)
{
    if (unlikely(prio < MAX_RT_PRIO))
        return 1;
    return 0;
}

int sched_fork(unsigned long clone_flags, struct task_struct *p)
{
...
    if (dl_prio(p->prio)) {
        put_cpu();
        return -EAGAIN;
    } else if (rt_prio(p->prio)) {----------------------当前进程task_struct->prio小于100，使用rt_sched_class。
        p->sched_class = &rt_sched_class;
    } else {
        p->sched_class = &fair_sched_class;-------------其它情况使用公平调度类fair_sched_class。
    }
...
}

  

2.5.1.2 sched_setscheduler

内核中有很多直接调用sched_setscheduler()设置进程的调度策略和优先级的地方，但是更常用的方法是通过系统调用sys_sched_setscheduler()在用户空间对进程进行设置。

在调用__setscheduler()进行设置之前，__sched_setscheduler()进行了一些有效性检查。

然后根据task_struct->prio来判断采用哪个调度类，对于实时进程需要满足条件prio<100。 

static int __sched_setscheduler(struct task_struct *p,
                const struct sched_attr *attr,
                bool user, bool pi)
{
    int newprio = dl_policy(attr->sched_policy) ? MAX_DL_PRIO - 1 :
              MAX_RT_PRIO - 1 - attr->sched_priority;--------------------这里的newprio已经经过了转换，是99-sched_param->sched_priority。DL就对应-1。
    int retval, oldprio, oldpolicy = -1, queued, running;
    int new_effective_prio, policy = attr->sched_policy;
...
    /*
     * Valid priorities for SCHED_FIFO and SCHED_RR are
     * 1..MAX_USER_RT_PRIO-1, valid priority for SCHED_NORMAL,
     * SCHED_BATCH and SCHED_IDLE is 0.
     */
    if ((p->mm && attr->sched_priority > MAX_USER_RT_PRIO-1) ||
        (!p->mm && attr->sched_priority > MAX_RT_PRIO-1))----------------因为MAX_USER_RT_PRIO和MAX_RT_PRIO都为100，所以只要sched_priority大于99都返回-EINVAL。
        return -EINVAL;
    if ((dl_policy(policy) && !__checkparam_dl(attr)) ||
        (rt_policy(policy) != (attr->sched_priority != 0)))--------------FIFO和RR调度策略的sched_priority不能为0，所以范围变成1~99。
        return -EINVAL;
...
}

调用路径如下sched_setscheduler()->__sched_setscheduler()->__setscheduler()，下面就来看看如何设置调度策略和优先级的。

#define MAX_USER_RT_PRIO    100
#define MAX_RT_PRIO        MAX_USER_RT_PRIO

static inline int rt_prio(int prio)
{
    if (unlikely(prio < MAX_RT_PRIO))------------------------------------判断当前优先级是否是实时进程优先级，进而判断当前进程是否是实时进程。从0~99即为实时进程。
        return 1;
    return 0;
}

static inline int rt_policy(int policy)
{
    if (policy == SCHED_FIFO || policy == SCHED_RR)----------------------FIFO和RR两者是实时调度策略
        return 1;
    return 0;
}

static inline int task_has_rt_policy(struct task_struct *p)
{
    return rt_policy(p->policy);
}
static inline int __normal_prio(struct task_struct *p)
{
    return p->static_prio;
}

/*
 * Calculate the expected normal priority: i.e. priority
 * without taking RT-inheritance into account. Might be
 * boosted by interactivity modifiers. Changes upon fork,
 * setprio syscalls, and whenever the interactivity
 * estimator recalculates.
 */
static inline int normal_prio(struct task_struct *p)
{
    int prio;

    if (task_has_rt_policy(p))
        prio = MAX_RT_PRIO-1 - p->rt_priority;
    else
        prio = __normal_prio(p);
    return prio;
}

static void __setscheduler_params(struct task_struct *p, int policy, int prio)
{
    p->policy = policy;-----------------------------------------设置进程调度策略
    p->rt_priority = prio;--------------------------------------设置实时进程优先级
    p->normal_prio = normal_prio(p);----------------------------如果是普通进程等于task_struct->static_prio；如果使用了FIFO或者RR调度策略，等于99-rt_priority。
    set_load_weight(p);
}

/* Actually do priority change: must hold rq lock. */
static void
__setscheduler(struct rq *rq, struct task_struct *p, int policy, int prio)---------------p表示当前进程task_struct，policy表示调度策略，prio表示优先级。
{
    __setscheduler_params(p, policy, prio);
    /* we are holding p->pi_lock already */
    p->prio = rt_mutex_getprio(p);
    if (rt_prio(p->prio))
        p->sched_class = &rt_sched_class;
    else
        p->sched_class = &fair_sched_class;
}

   

3. SCHED_FIFO和SCHED_RR的测试

3.1 构造测试用例

构造测试之前，首先借用perf timechart测试代码，然后稍微修改一下分成机组进行对比测试。

1. 初始情况：普通进程，默认调度策略SCHED_NORMAL。

2. 设置FIFO调度策略：设置为SCHED_FIFO，并且优先级为49。

3. 设置FIFO并CPU亲和性：在2的基础上，固定进程在CPU0上。

4. 设置RR调度策略：设置为SCHED_RR，并且优先级为49。

5. 设置RR并CPU亲和性：在4的基础上，固定进程在CPU0上。

代码如下，主要是对颜色部分带代码进行组合排列：

#define _GNU_SOURCE
#include <stdio.h>
#include <sched.h>
#include <stdlib.h>
#include <unistd.h>

void test_little(void)
{
  int i,j;

  for(i = 0; i < 30000000; i++) 
    j=i; 
}

void test_medium(void)
{
  int i,j;

  for(i = 0; i < 60000000; i++) 
    j=i; 
}

void test_high(void)
{
  int i,j;

  for(i = 0; i < 90000000; i++) 
    j=i; 
}

void test_hi(void)
{
  int i,j;

  for(i = 0; i < 120000000; i++) 
    j=i; 
}

int main(void)
{
  int i, pid, result;
  cpu_set_t mask;
  struct sched_param param;

  //Set CPU affinity.
  CPU_ZERO(&mask);
  CPU_SET(0, &mask);
  if(sched_setaffinity(0, sizeof(cpu_set_t), &mask) == -1)
  {
    exit(EXIT_FAILURE);
  }

  //Set scheduler and priority.
  param.sched_priority = 50;
  sched_setscheduler(0, SCHED_FIFO, &param);

  for(i = 0; i<2; i++) {
    result = fork();
    if(result>0)
      printf("i=%d parent parent=%d current=%d child=%d\n", i, getppid(), getpid(), result);
    else
      printf("i=%d child parent=%d current=%d\n", i, getppid(), getpid());

    if(i==0)
    {
      test_little();
      sleep(1);
    } else {
      test_medium();
      sleep(1);
    }
  }

  pid = wait(NULL);
  test_high();
  printf("pid=%d wait=%d\n", getpid(), pid);
  sleep(1);
  pid = wait(NULL);
  test_hi();
  printf("pid=%d wait=%d\n", getpid(), pid);
  return 0;
}

3.1.1 设置CPU亲和性

设置CPU亲和性的API是sched_setaffinity()。

#define _GNU_SOURCE
#include <sched.h>

void CPU_ZERO(cpu_set_t *set);-------------------------------初始化一个空cpu_set_t
void CPU_SET(int cpu, cpu_set_t *set);-----------------------将cpu加入到set
void CPU_CLR(int cpu, cpu_set_t *set);-----------------------将cpu从set移除
int CPU_ISSET(int cpu, cpu_set_t *set); ----------------------判断cpu是否在set中，在返回true。

int sched_setaffinity(pid_t pid, size_t len, cpu_set_t *set); 

示范如下：

cpu_set_t mask;
struct sched_param param;

//Set CPU affinity.
CPU_ZERO(&mask);
CPU_SET(0, &mask);
if(sched_setaffinity(0, sizeof(cpu_set_t), &mask) == -1)
{
  exit(EXIT_FAILURE);
}

参考资料：《Linux中CPU亲和性(affinity)》

3.1.2 设置优先级和调度策略

#include <sched.h>

struct sched_param {
int sched_priority; /* Scheduling priority */
};

int sched_setscheduler(pid_t pid, int policy, const struct sched_param *param);

policy常用的包括SCHED_OTHER、SCHED_FIFO、SCHED_RR。

实际在进程中看到的SCHED_FIFO优先级，是99减去sched_priority。比如这里设置为50，看到的是49。

示例如下：

//Set scheduler and priority.
param.sched_priority = 50;
sched_setscheduler(0, SCHED_FIFO, &param);

3.2 分析测试手段

在执行包含sched_setscheduler()函数的时候，必须具有root权限才能修改调度器类或者优先级。

可以通过perf timechart可视化查看fork及其子进程的执行情况。

sudo perf timechart record -T ./fork

sudo perf timechart -p fork

trace-cmd+kernelshark查看个进程间的执行情况。

sudo trace-cmd record -e sched_wakeup -e sched_switch ./fork

kernelshark

两个方法对比下来，trace-cmd结果更清晰点。

3.3 SCHED_NORMAL/SCHED_FIFO/SCHED_RR对比分析如下，以及RR_TIMESLICE修改

3.3.1 初始情况：普通进程，默认调度策略SCHED_NORMAL

可以看出，由于具有相同优先级且调度策略为SCHED_NORMAL，几个线程在不停的调入调出。

并且择机在CPU0或者CPU1上运行。

 看一下细节，可以看出四个线程之间的频繁切换。

3.3.2 设置FIFO调度策略：设置为SCHED_FIFO，并且优先级为49

设置了SCHED_FIFO之后，可以清晰看出FIFO调度策略的特性。

由于优先级为49，已经非常低，没有其他进程会抢占fork，并且fork都是49，所以知道其它进程执行完毕才有机会调度到。

下面不同线程颜色看出6953和6956 在CPU0上执行，6954和6955在CPU1上执行。

6954在6955执行稍后就sched_wakeup了，但是知道6955换出后才得到执行的机会。6955在执行的过程中是不会被抢占的。

   

3.3.3 设置FIFO并CPU亲和性：在2的基础上，固定进程在CPU0上

在3.3.2基础上设置了，CPU亲和性，可以看出所有的线程都集中在CPU0上。

可以看出四个线程串行在一个CPU上，等待时间更长了。

3.3.4 设置RR调度策略：设置为SCHED_RR，并且优先级为49

和3.3.2对比可以看出，SCHED_RR进程在执行过程中存在换入换出的情况。

那么RR的timeslice怎么样的呢？

下图中三个点分别对应上图三个sched_switch，可以看出10187的第一段为36ms左右，10185的第一段也为36ms左右。

但是从/proc/sys/kernel/sched_rr_timeslice_ms读出的置位25，也即25*4ms=100ms。

这两者不符，why？应该是开头36ms之后部分，还没有超过100ms的timeslice，所以不存在进程切换。

  

3.3.5 设置RR并CPU亲和性：在4的基础上，固定进程在CPU0上

 和3.3.4对比，可以看出四个线程固定在CPU0上。它们之间的调度相对于3.3.4应该更加频繁。

来看一下细节，7532在执行了34ms后调出给7535执行；7535执行了36ms之后跳出给7532执行。

7532执行完之后，7533开始执行；7532执行了34ms之后调出给7535执行。

7535执行完之后，7536开始执行；7536执行了34ms之后调出给7533执行。

当前RR_TIMESLICE为100ms，后面执行的事件可能都不到100ms，所以加大循环次数，让执行事件超过200ms。

发现规律如下：每个线程第一次执行的事件都在36ms左右，后面就按照RR_TIMESLICE进行切换。上图看不出切换的原因是，36ms后剩下的不到100ms。所以不会存在切换的需求。

查看下图就会发现，除了每个线程开头运行36ms和结尾不定(进程主动放弃原因)之外，所有的段都在100ms左右。这就解释了RR_TIMESLICE所起的作用。

调整代码如下：

void test_medium(void)
{
  int i,j;

  for(i = 0; i < 120000000; i++) 
    j=i; 
}

void test_high(void)
{
  int i,j;

  for(i = 0; i < 240000000; i++) 
    j=i; 
}

void test_hi(void)
{
  int i,j;

  for(i = 0; i < 360000000; i++) 
    j=i; 
}

  

3.3.6 调整RR_TIMESLICE

对RR_TIMESLICE的调整可以通过/proc/sys/kernel/sched_rr_timeslice_ms进行，这个sysfs节点的单位是jiffies。

echo 100 > /proc/sys/kernel/sched_rr_timeslice_ms，读出来的结果是25，说明jiffies为4ms。

然后修改RR_TIMESLICE为50ms，读出的结果变成13，所以实际的timeslice应该是13*4=52ms。

从下图可以看出，每个timeslice确实变成了52ms，并且进程切换的次数增加了，每个进程中间包含了4个52ms的timeslice。

3.3.7 当RR和FIFO混合调度

首先以都采用SCHED_FIFO或者SCHED_RR作为参照，然后分别修改父进程为RR和修改子进程为RR，进行对比看看FIFO和RR混合时调度情况。

1.全部采用FIFO情况，从下图可以看出8653和8654分成四部分，8659和8668分成三部分。

2.全部采用RR情况，test_medium部分4个线程互相抢占，后面test_high和test_hi部分由于wait()需要等待，只有个两两抢占。

3.那么如果将三个子进程都改成RR，结果如何呢？

test_little部分，由于8983和8984不能交叉调度。

因为进程8983是FIFO，在(1)等到子进程8985结束之后，得到执行的机会。此时虽然8986也由调度机会，但是因为8983是FIFO，只能等8983执行结束，主动放弃。

所以直到(2)8986才有机会调度，执行完毕。

8984在8986结束过后(3)，wait条件满足后继续执行，直到8984结束过后(4)继续8983执行。

和全部RR的区别主要在于(1)~(3)部分。

4. 那么只将父进程改成RR呢？

可以看出wait()的逻辑关系仍然被严格遵循着，只不过由于9098是RR，其他线程是FIFO。

所以9098被抢占的严重，9098的test_medium执行时间拉的很长，被其他FIFO线程阻塞较多。

那么提高父进程RR的优先级会是什么情况呢？

可以看出，虽然10457是RR调度策略，但是由于优先级较高，10458必须等待10457执行完毕，才有机会得到调度。

所以10457的test_medium部分先得到机会执行。后面的10459虽然也处于可被调度情况，但苦于优先级较低，无法得到执行，只能等待10457主动放弃执行。

后面部分仍然严格遵循wait逻辑。

4. 对实时进程的优化

4.1 调整调度策略和优先级

通过chrt(Change Real Time)来改变进程的属性。

如，chrt -r -p 20 xxx设置进程调度策略为RR，优先级为20。

chrt -m可以查看支持的调度策略，以及优先级取值范围。

4.2 sysctl动态调整调度器各种参数

sysctl variable获取属性的值。

sysctl variable=value设置属性的值。

4.3 实时调度策略相关调节参数

这些参数都位于/proc/sys/kernel中。

sched_rr_timeslice_ms：针对SCHED_RR类型实时进程的时隙，用完时隙之后实时进程可能被强占并放入队列尾部。

sched_rt_period_us：实时进程调度的单位CPU时间，默认1000000us。

sched_rt_runtime_us：在sched_rt_pediod_us基础上，实时进程的占比，默认950000us。

4.3.1 sched_rt_period_us和sched_rt_runtime_us

关于sched_rr_timeslice_ms的测试，上面已经进行了相关说明。

下面看看修改sched_rt_period_us和sched_rt_runtime_us参数对实时进程和普通进程调度的影响。

测试环境：Ubuntu+Kernel 4.4.0-116 @ Dual CPUs

测试代码：

创建两个可执行文件，执行死循环。test_fifo采用FIFO调度策略，优先级为49；test_normal采用NORMAL调度策略，优先级wie120。

同时为了方便查看两者的占比情况，将两个进程都绑定到CPU0上。

#define _GNU_SOURCE
#include <stdio.h>
#include <sched.h>
#include <stdlib.h>
#include <unistd.h>

int main(void)
{
  int i, pid, result;
  cpu_set_t mask;
  struct sched_param param;

  //Set CPU affinity.
  CPU_ZERO(&mask);
  CPU_SET(0, &mask);
  if(sched_setaffinity(0, sizeof(cpu_set_t), &mask) == -1)
  {
    exit(EXIT_FAILURE);
  }

  //Set scheduler and priority.
  param.sched_priority = 50;
  sched_setscheduler(0, SCHED_FIFO, &param);------------------------test_normal只要注释这部分代码

  while(1)
  {
  }

  return 0;
}

4.3.1.1 2CPU sched_rt_runtime_us=950000

可以看出test_fifo占用了100%的CPU，看不到test_normal的身影。

为什么呢？

因为这是在一个双核的系统上，并且test_fifo和test_normal都固定在CPU0上。

sched_rt_runtime_us=950000就导致了test_fifo可以独占CPU0，test_normal得不到执行的机会。

test_fifo独占了CPU0。

4.3.1.2 2CPU sched_rt_runtime_us=400000

那么简单修改sched_rt_runtime_us到50%一下看看效果。

可以看到两者的比例变成了test_fifo:test_normal=4:1，这符合在双核系统上的预期，80%/2=40%。

来看看细节，可以看出test_normal得到了调度。

看看细节如何，test_normal+test_fifo的总时间为1s，test_fifo执行事件为800ms。这在双核系统上也说得过去。

可以看出在SMP系统上sched_rt_runtime_us是如何分配的。

4.3.1.3 2 CPU sched_rt_runtime_us=400000 sched_rt_pediod_us=2000000

那么增大sched_rt_pediod_us到2000000us情况如何呢？

可以看出40%/2=20%=400000/2000000，符合预期。

可以看出test_fifo和test_normal的比例改变了。

 test_fifo+test_normal的总时间变成2000000us，并且test_fifo执行事件为800ms，不变。

4.3.1.4 1CPU sched_rt_pediod_us=1000000 sched_rt_runtime_us=750000

将CPU1 offline，echo 0 > /sys/bus/cpu/devices/cpu1/online。

可以看到test_fifoCPU占比变成了75%，剩下的test_normal和其它进程使用。

 可以看出test_fifo在单核状态下，和设置的参数是一一对应的。

 test_fifo CPU占比75%，执行时间为750ms，剩余的250ms由test_normal和其它进行分配。

虽然test_normal的nice为-20，但是对于CFS调取器来说，其它进程仍然有机会得到调度。

4.3.1.5 1CPU sched_rt_pediod_us=10000 sched_rt_runtime_us=9000

这样的目的是CFS得到很平滑的调度，并且保证普通进程占比10%。

实际情况是，test_fifo基本接近90%占比。

可以看到test_normal和test_fifo之间的调度更加频繁了。

可以看出test_normal+test_fifo并不等于10ms，而是20ms。

但是两者的比例是一致的，test_fifo:test_normal=9:1

那么将sched_rt_runtime_us=36000、sched_rt_pediod_us=40000,呢？

结果如下，可以看出test_fifo+test_normal=40ms，两者比例也符合预期。

 难道sched_rt_pediod_us有最小值20ms的限制？

4.3.2 一个实时任务很重的场景调节sched_rt_runtime_us

Linux默认sched_rt_runtime_us为950000，在此场景下场景上下行速率离目标差很远。

将其设置为-1，差不多达到目标。

所以在实际调度中，打开RT Bandwidth的开销还是很大的。

要保证CFS保留5%的CPU，花费的开销要大很多。

4.4 调试和统计接口

/proc/sched_debug：全局调试信息，包括cfs/rt/dl等就绪队列信息，以及运行中进程相关信息。

/proc/schedstat：全局调度的统计信息。

version 15
timestamp 4549804362
cpu0 4340 0 492167328 210807124 220972523 109642580 93539887439988 27717517566019 281300914
domain0 3 55479654 55454558 22085 8414771 3745 67 217 55454341 1092592 1029317 50266 11959758 15413 301 280 1029037 13709443 9063193 3910056 865357935 837652 599 2432437 6630756 41 0 41 0 0 0 0 0 0 111329937 41920159 0
cpu1 4546 0 527388167 223958553 306630172 161858229 91272746397129 25577018812315 303373597
domain0 3 77608259 77584351 20709 8378910 4007 137 221 77584130 716522 672167 31250 295259964 15454 273 97 672070 14581612 9475898 4287779 3002623546 925448 622 2366766 7109132 116 1 115 0 0 0 0 0 0 144771943 42740754 0

/proc/pid/sched：单个进程的统计信息，

test_fifo (17739, #threads: 1)
-------------------------------------------------------------------
se.exec_start                                :    1019445477.050445
se.vruntime                                  :            -2.507707
se.sum_exec_runtime                          :        810819.452208
se.statistics.sum_sleep_runtime              :             0.000000
se.statistics.wait_start                     :             0.000000
se.statistics.sleep_start                    :             0.000000
se.statistics.block_start                    :             0.000000
se.statistics.sleep_max                      :             0.000000
se.statistics.block_max                      :             0.000000
se.statistics.exec_max                       :             4.008440
se.statistics.slice_max                      :             0.000000
se.statistics.wait_max                       :             0.041248
se.statistics.wait_sum                       :             0.050407
se.statistics.wait_count                     :                    4
se.statistics.iowait_sum                     :             0.000000
se.statistics.iowait_count                   :                    0
se.nr_migrations                             :                    1
se.statistics.nr_migrations_cold             :                    0
se.statistics.nr_failed_migrations_affine    :                    0
se.statistics.nr_failed_migrations_running   :                    0
se.statistics.nr_failed_migrations_hot       :                    0
se.statistics.nr_forced_migrations           :                    0
se.statistics.nr_wakeups                     :                    0
se.statistics.nr_wakeups_sync                :                    0
se.statistics.nr_wakeups_migrate             :                    0
se.statistics.nr_wakeups_local               :                    0
se.statistics.nr_wakeups_remote              :                    0
se.statistics.nr_wakeups_affine              :                    0
se.statistics.nr_wakeups_affine_attempts     :                    0
se.statistics.nr_wakeups_passive             :                    0
se.statistics.nr_wakeups_idle                :                    0
avg_atom                                     :          3955.216840
avg_per_cpu                                  :        810819.452208
nr_switches                                  :                  205
nr_voluntary_switches                        :                    0
nr_involuntary_switches                      :                  205
se.load.weight                               :                 1024
se.avg.load_sum                              :             48293853
se.avg.util_sum                              :             48244723
se.avg.load_avg                              :                 1002
se.avg.util_avg                              :                 1002
se.avg.last_update_time                      :     1018634657576560
policy                                       :                    2
prio                                         :                   49
clock-delta                                  :                   22
mm->numa_scan_seq                            :                    0
numa_pages_migrated                          :                    0
numa_preferred_nid                           :                   -1
total_numa_faults                            :                    0
current_node=0, numa_group_id=0
numa_faults node=0 task_private=0 task_shared=0 group_private=0 group_shared=0

5. 总结

从上面可以看出实时进程的调度很简单，对于FIFO严格按照优先级来执行，同一优先级先进先得到执行。

对于RR调度策略，存在一个RR_TIMESLICE时隙设置，可以通过调节时隙让各进程得到相对公平的机会。

当相同优先级的FIFO和RR进程执行时，RR相对吃亏，因为FIFO一旦抢占会执行到主动放弃。

最近花了10几天的时间，将linux进程调度相关的内核代码看了两遍左右，也看了一些讲述linux进程调度的一些文章，总想写个系列文章，把进程调度全景剖析一遍，但是总是感觉力不逮己，自己都不敢下笔写文章了。算了，还是不难为自己了，就随便写写自己的心得好了。

输出结果如下：

 首先看看维基百科对实时操作系统的定义：

实时操作系统（Real-time operating system, RTOS），又称即时操作系统，它会按照排序运行、管理系统资源，并为开发应用程序提供一致的基础。实时操作系统与一般的操作系统相比，最大的特色就是“实时性”，如果有一个任务需要执行，实时操作系统会马上（在较短时间内）执行该任务，不会有较长的延时。这种特性保证了各个任务的及时执行。

实时操作系统 (Real-time OS) 是相对于分时操作系统 (Time-Sharing OS) 的一个概念。在一个分时操作系统中，计算机资源会被平均地分配给系统内所有的工作。在分时系统中，各项任务需要花多长时间来完成，这一点并不重要。

所以在一 个实时操作系统之中，最关注的是每个任务在多长时间内可以完成。简单地说，实时和分时操作系统最大的不同在于 时限(deadline)”这个概念。 在一个特定任务的执行时间内必须是确定的并且可预测的，在任何情况下都能保证任务的最大执行时间限制，通常实时分为软实时和硬实时。

软实时： 仅仅要求事件的响应是实时的，并不要求任务必须在多长的时间内完成，大多数情况下要求的时统计意义上的实时，而不需要100%达到实时。在许多情况下，这种软性正确性已经达到了用户期望的水平。比如用户在操作DVD播放的时候，偶尔不能在限定的时间内完成任务也是可以接受的，它可以容忍偶然的超时错误，失败造成的后果并不严重
硬实时： 在任务的执行时间的要求是非常严格的，无论在什么情况下，任务的执行时间必须要得到绝对的保证，否则将会产生灾难性的后果。比如，汽车碰撞后，必须在X时间内弹开安全气囊，你弹开晚了，人已经挂了。
1 为什么linux不是硬实时
Linux系统一开始就被按照GPOS(通用操作系统)来设计的，它所追求的是尽量缩短系统的平均响应时间，提高吞吐量，达到更好的平均性能。在这个背景下，Linux无法达到强实时性的因素是多方面的，比如虚拟内存管理、共享资源互斥访问机制等等，但最重要的因素是进程调度以及内核抢占机制，这也是本文讨论的重点。

我们首先来看看，为什么Linux不是一个硬实时的操作系统，其主要有以下几个原因

spinlock是一个随处可见被内核和驱动使用的API

首先，我们来看看spinlock的实现，spin_lock()会调用preempt_disable() 导致本核的抢占调度被关闭(preempt_disable函数实际增加preempt_count来达到此效果)，其次我们理解spin_lock_irq()是local_irq_disable()+preempt_disable()的合体。

对于两个接口，大家是不是很熟悉，我们在linux内核和驱动程序中随处可见，在不用睡眠，时间较短的临界区的场景，我们都会第一时间想到spinlock。自旋锁的优点是，在两个人(这两个人可能是线程与线程，中断与线程，中断与中断等）同时竞争一个锁的时候，防止出现失败的那一方出现上下文切换，所以希望在原点等待。

但是这样的自旋锁本身也会导致一些副作用，它导致了持有该锁的CPU核的抢占被禁止，所以内核自旋锁的实现，是通过禁止抢占来实现临界区的保护，如下图的例子

假设T1, T2, T3, T4运行在一个核上面，当T1拿到spinlock后，这个核上的抢占调度被禁止

如果在T1持有spinlock的时间内，T2是一个高优先级的实时任务，尽管T2被唤醒，它也不可能立即打断T1的执行，必须等待T1释放spinlock
由于T1究竟会持有spinlock多久做什么，这个鬼都不知道，所以T2究竟要等多久，也未可知，这显然破坏了决定性的时延。

假设T0时刻，系统正在执行自旋锁进入临界区，此时在T1时刻，系统唤醒了一个高优先级的任务，而此时抢占调度是关闭的，所以RT实时进程是无法得以调度的
而当中断T2时刻，发生了一个中断，就会导致进入中断处理，这段时间发生了多久，鬼也不知道，当中断处理完后，返回到自旋锁的临界区，当退出临界区时候，会打开内核抢占并且尝试抢占当前的进程，此时RT实时任务将会得以调度，但是此时的延时有太多的不确定性
Linux的中断执行时间可能过长且不可嵌套

当中断发生后，一般硬件会自动屏蔽当前CPU对于中断的响应，而软件层面上，直到IRQ HANDLER做完，才会重新开启中断，比如，对于ARM处理器而言，exception进来的时候，硬件都会自动屏蔽中断

也就是说，当ARM处理器收到中断的时候，它进入中断模式，同时ARM处理器的CPSR寄存器的IRQ位会被硬件设置为屏蔽IRQ。

Linux内核会在如下2个时候重新开启CPSR对IRQ的响应：

从IRQ HANDLER返回中断底半部的SOFTIRQ
从IRQ HANDLER返回一个线程上下文
中断在执行的时候，所有的中断都进不来，这个设计本身简化了内核，但是对于硬实时的打击是致命的，前面的中断不执行完成，优先级再高的中断也得给我等着。

比如中断1在执行的过程中，来了中断2，而中断2对应的事情是必须要决定性时延的，由于IRQ1的中断服务程序也是码农写的，我们无法确定这个中断服务程序要执行多久。这显然让高优先级中断2的进入延迟不再具备可预期性。

软中断(softirq)是一个比进程上下文优先级更高的上下文

我们设想一个场景，哪怕Linux解决了问题2，就是Linux的中断变地可嵌套，高优先级的中断可以打断低优先级的中断，并且高优先级的中断2唤醒了一个用户写的实时线程。

IRQ2唤醒了实时任务T1，但是T1必须等待IRQ1唤起的软中断(也包括使用软中断上下文的tasklet等)被执行完，T1才能投入执行。IRQ1唤起的softirq的代码是码农写的，这个码农写多久，鬼都不知道，这显然破坏了实时任务T1得以调度执行的确定性时延。

内核里面会屏蔽中断的API如local_irq_disable、spin_lock_irqsave等

那么，问题又来了，spin_lock_irqsave既屏蔽了抢占，又屏蔽了中断，这会导致中断和实时任务的确定性时延造成不可预期的破坏。因为spin_lock_irqsave和spin_lock_irqrestore是码农写的，鬼都不知道它要多久。

所有针对这个问题，我们回顾linux中的四类区间：

1 中断
2 软中断
3 进程上下文中的spin_lock
4 进程上下文中的其他区域
上述四类区间中，只有第四类区间支持抢占调度。当可以调度的事情发生在前3类区间中，即如果在这3类区间中唤醒了高优先级的可以抢占的task，实际上却不能抢占，直到这3类区间结束。

用一个例子说明如下：

如上图所示：

T0时刻Normal task因为syscall陷入内核
T1时刻CPU拿到spin lock，进入Critical section
T2时刻系统产生中断IRQ1，进入IRQ handler
T3时刻系统唤醒了高优先级的RT task，但由于此时系统处于不可调度区域，所以RT task无法立即运行
T4时刻IRQ1结束，但接着产生中断IRQ2，进入IRQ handler
T5时刻，中断都结束，但spin lock仍然没有释放，系统仍然处于不可调度区域
T6时刻，spin lock释放，高优先级的RT task立马得到调度
T7时刻RT task运行结束，Normal task再一次被调度到
T8时刻从内核态返回
从T1到T6，这个区间的时间是不可预测的，因此通用的Linux系统无法达到硬实时的标准。

2 linux内核实时性改进
早在2001年时，内核就开始打上抢占补丁，回顾之前的知识点

如果linux内核不支持抢占，那么进程要么主动要求调度，入调用schedule()或者cond_resched()等，要么在系统调用、异常处理和中断处理完成后返回用户空间强进行调度，上述都会导致早期linux内核调度时延非常大
如果linux内核支持抢占，如果唤醒动作发生在系统调用或者异常处理上下文，在下一次调用preempt_enable时会检查调度标志位，是否需要抢占调度。同时对于中断处理返回内核态，也会检查调度，而preempt_enable函数会主动调用__preempt_schedule来判断是否需要抢占当前的进程。

主要是用thread_info数据结构中的一个preempt_count计数

 

当preempt_count为0时，表示内核可以被抢占
当preempt_count大于0时，则禁止抢占
preempt_count包含preempt， softirq，hardirq，nim以及need_resched几个域

内核提供preempt_disable来关闭抢占，之后preempt_count会加1，preempt_enable函数用于打开抢占，preempt_count计数会减1，程序会判断当前是否为0，如果为0，就调用___preempt_schedule

preempt_count本质上是一个per-CPU的32位变量，它在各种处理器架构下的存放位置和命名不尽相同，但其值都可以使用preempt_count()函数统一获取。preempt_count逻辑相关的核心代码位于include/linux/preempt.h，虽然只是一个32位变量，但由于其和中断、调度/抢占密切相关，因此在系统中发挥的作用不容小觑。

preemption count占8个bits，因此一共可以表示最多256层调度关闭的嵌套
preempt_count中的第8到15个bit表示softirq count，它记录了进入softirq的嵌套次数，如果softirq count的值为正数，说明现在正处于softirq上下文中。由于softirq在单个CPU上是不会嵌套执行的，因此和hardirq count一样，实际只需要一个bit(bit 8)就可以了。但这里多出的7个bits并不是因为历史原因多出来的，而是另有他用。
preempt_count中的第16到19个bit表示hardirq count，它记录了进入hardirq/top half的嵌套次数，在do_IRQ()中，irq_enter()用于标记hardirq的进入，此时hardirq count的值会加1。irq_exit()用于标记hardirq的退出，hardirq count的值会相应的减1。如果hardirq count的值为正数，说明现在正处于hardirq上下文中，代码中可借助**in_irq()**宏实现快速判断。注意这里的命名是"in_irq"而不是"in_hardirq"。
对于内核仅仅的支持抢占调度，要达到硬实时系统的要求还远远的达不到要求，为此社区一直致力于linux内核实时性优化和改进工作，最近几年有很多优化的补丁和方法，

PREEMPT_RT补丁可以通过以下方面对kernel进行源码级的改造：

spinlock迁移为可调度的mutex
中断线程化
软中断线程化
从而将Linux内核中的1/2/3类区间都改造成4类区间，大大提高了系统的实时性。对于linux也提供了很多工具用于检查哪些地方有比较大的调度延时

对于可以通过工具cyclictest工具来测试Linux实时性能。该工具的使用方法已经安装方法这里不做过多介绍。
ftrace工具是一个很多好的追踪跟踪器，如preemptirqsoff跟踪器可以跟踪中断并禁止抢占代码的延迟，同时记录关闭的最大时延
linux内核还继承了latencytop工具，它在内核上下文切换时被记录进程的内核栈，然后通过匹配内核栈函数来判断导致上下文奇幻的原因。这个不仅方便判断系统出现了哪些方面的延时，还有助于查看某个进程或线程的延迟情况。详细的用法见https://blog.yufeng.info/archives/1239