操作系统

当前位置:金沙棋牌 > 操作系统 > 内核源码分析之进程调度机制,5的进程模型与调

内核源码分析之进程调度机制,5的进程模型与调

来源:http://www.logblo.com 作者:金沙棋牌 时间:2019-11-05 13:55

《奔跑吧linux内核》3.2笔记,不足之处还望大家批评指正

进程调度所使用到的数据结构:

在抽象模型中vruntime决定了进程被调度的先后顺序,在真实模型中决定被调度的先后顺序的参数是由函数entity_key决定的。   
static inline s64 entity_key(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    return se->vruntime - cfs_rq->min_vruntime;
}
enqueue_task_fair---->enqueue_entity---->__enqueue_entity---->entity_key决定插入就绪队列的位置。

1.操作系统是怎么组织进程的?

建议阅读博文理解linux cfs调度器

1.就绪队列

普通进程分为40个等级,每个等级对应一个权重值,权重值用一个整数来标示。权重值定义在数组prio_to_weight[40]中;普通进程的权重值最大为88761,最小为15。默认情况下,普通进程的权重值为1024(由NICE_0_LOAD指定)。weight是由进程的静态优先级static_prio决定的,静态优先级越高(static_prio值越小)weight值越大。普通进程的默认 nice值为0,即默认静态优先级为120,它的weight值为prio_to_weight[20],即1024。因此NICE_0_LOAD的值就 为1024。

  1.1什么是线程,什么是进程:

  进程大致可以分为交互式进程批处理进程实时进程。对于不同的进程采用不同的调度策略,目前Linux内核中默认实现了4种调度策略,分别是deadline、realtime、CFS和idle,分别适用struct sched_class来定义调度类。

内核为每一个cpu创建一个进程就绪队列,该队列上的进程均由该cpu执行,代码如下(kernel/sched/core.c)。

vruntime行走速度:
    系统规定:默认权重值(1024)对应的进程的vruntime行走时间与实际运行时间runtime是1:1的关系。由于vruntime的行走速度和权重值成反比,那么其它进程的vruntime行走速度都通过以下两个参数计算得到:1、该进程的权重值2、默认进程的权重值。
    例如权重为3096的进程的vruntime行走速度为:1024/3096 * (wall clock)。
    “真实时钟速度”即为runtime(即 wall clock)行走的速度。

    刚接触时可能经常会将这两个东西搞混。简单一点的说,进程是一个大工程,线程则是这个大工程中每个小地方需要做的东西(在linux下看作"轻量级进程"):

  4种调度类通过next指针串联在一起,用户空间程序可以使用调度策略API函数(sched_setscheduler())来设定用户进程的调度策略。

1 DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

    进程执行执行期间周期性调度器周期性地启动,其负责更新一些相关数据,并不负责进程之间的切换:
    timer_tick()---->update_process_times---->schedule_tick()
    schedule_tick---->task_tick_fair---->entity_tick()---->update_curr()
    update_curr()函数完成相关数据的更新。
        update_curr()---->delta_exec = (unsigned long)(now - curr->exec_start)
                              |-->__update_curr()
                              |-->curr_exec_start = now;
    update_curr()函数只负责计算delta_exec以及更新exec_start。其它工作由__update_curr()函数完成:
        1、更新当前进程的实际运行时间(抽象模型中的runtime)。
        2、更新当前进程的虚拟时间vruntime。
        3、更新cfs_rq->min_vruntime。
           在当前进程和下一个将要被调度的进程中选择vruntime较小的值。然后用该值和cfs_rq->min_vruntime比较,如果比min_vruntime大,则更新cfs_rq为的min_vruntime为所求出的值。

    例如当你打开QQ微信,这时系统启动了一个进程。然后你开始看别人发的消息,这时启动了一个线程用来传输文本,如果发了一段语音,这也会启动一个线程来传输语音......(当然一个程序并不代表一定只有一个进程)

问题一:请简述对进程调度器的理解,早起Linux内核调度器(包括O(N)和O(1))调度器是如何工作的?

定义了一个struct rq结构体数组,每个数组元素是一个就绪队列,对应一个cpu。下面看下struct rq结构体(kernel/sched/sched.h):

考虑下当创建新进程或者进程唤醒时,vruntime在真实模型中的处理方式:
I、新建进程
    进程的ideal_time长度和weight成正比,vruntime行走速度与weight值成反比。因此当每个进程在period时间内,都执行了自己对应的ideal_time长时间,那么他们的vruntime的增量相等。而nice为0的进程的vruntime行走速度等于runtime行走速度,所以每个进程都运行它自己对应的ideal_runtime时间,其它进程的vruntime增量都等于nice值为0的进程的ideal_runtime。假设初始情况下,它们的所有进程的vruntime值都等于0,那么当一个进程运行完runtime的时间为ideal_time,那么它的vruntime将为最大,只要其它进程的运行总时间没有达到各自对应的ideal_runtime值,那么它始终排在进程队列的末尾。

  1.2进程内核栈与thread_info(用于存储进、线程及其信息等):

  调度器是按一定的方式对进程进行调度的一种机制,需要为各个普通进程尽可能公平地共享CPU时间。

图片 1图片 2

    对于新进程,task_fork_fair()->place_entity(cfs_rq, se, 1),其intial参数为1。新进程的vruntime值被设置为min_vruntime+sched_vslice(cfs_rq, se), sched_vslice()函数可计算出nice值为0的进程的ideal_runtime。其作用是将新加入的进程的标记为“它在period长时间内已经运行它对应的ideal_time长时间”,那么新加入进程在理论上(所有进程都执行它对应的ideal_runtime时间,没有发生睡眠、进程终止等特殊情况)只有等待period之后才能被调度。
    sched_vslice(cfs_rq, se)---->calc_delta_fair(sched_slice(cfs_rq, se), se), sched_slice()计算新建进程的ideal_runtime,calc_delta_fair()将ideal_runtime转换成vruntime。

struct task_struct {
    ......
 
    /* 指向进程内核栈 */
    void *stack;
 
    ......
 };

  O(N)调度器发布与1992年,从就绪队列中比较所有进程的优先级,然后选择一个最高优先级的进程作为下一个调度进程。每一个进程有一个固定时间片,当进程时间片使用完之后,调度器会选择下一个调度进程,当所有进程都运行一遍后再重新分配时间片。这个调度器选择下一个调度进程前需要遍历整个就绪队列,花费O(N)时间。

  1 struct rq {
  2     /* runqueue lock: */
  3     raw_spinlock_t lock;
  4 
  5     /*
  6      * nr_running and cpu_load should be in the same cacheline because
  7      * remote CPUs use both these fields when doing load calculation.
  8      */
  9     unsigned int nr_running;
 10 #ifdef CONFIG_NUMA_BALANCING
 11     unsigned int nr_numa_running;
 12     unsigned int nr_preferred_running;
 13 #endif
 14     #define CPU_LOAD_IDX_MAX 5
 15     unsigned long cpu_load[CPU_LOAD_IDX_MAX];
 16     unsigned long last_load_update_tick;
 17 #ifdef CONFIG_NO_HZ_COMMON
 18     u64 nohz_stamp;
 19     unsigned long nohz_flags;
 20 #endif
 21 #ifdef CONFIG_NO_HZ_FULL
 22     unsigned long last_sched_tick;
 23 #endif
 24     int skip_clock_update;
 25 
 26     /* capture load from *all* tasks on this cpu: */
 27     struct load_weight load;
 28     unsigned long nr_load_updates;
 29     u64 nr_switches;
 30 
 31     struct cfs_rq cfs;
 32     struct rt_rq rt;
 33     struct dl_rq dl;
 34 
 35 #ifdef CONFIG_FAIR_GROUP_SCHED
 36     /* list of leaf cfs_rq on this cpu: */
 37     struct list_head leaf_cfs_rq_list;
 38 
 39     struct sched_avg avg;
 40 #endif /* CONFIG_FAIR_GROUP_SCHED */
 41 
 42     /*
 43      * This is part of a global counter where only the total sum
 44      * over all CPUs matters. A task can increase this counter on
 45      * one CPU and if it got migrated afterwards it may decrease
 46      * it on another CPU. Always updated under the runqueue lock:
 47      */
 48     unsigned long nr_uninterruptible;
 49 
 50     struct task_struct *curr, *idle, *stop;
 51     unsigned long next_balance;
 52     struct mm_struct *prev_mm;
 53 
 54     u64 clock;
 55     u64 clock_task;
 56 
 57     atomic_t nr_iowait;
 58 
 59 #ifdef CONFIG_SMP
 60     struct root_domain *rd;
 61     struct sched_domain *sd;
 62 
 63     unsigned long cpu_capacity;
 64 
 65     unsigned char idle_balance;
 66     /* For active balancing */
 67     int post_schedule;
 68     int active_balance;
 69     int push_cpu;
 70     struct cpu_stop_work active_balance_work;
 71     /* cpu of this runqueue: */
 72     int cpu;
 73     int online;
 74 
 75     struct list_head cfs_tasks;
 76 
 77     u64 rt_avg;
 78     u64 age_stamp;
 79     u64 idle_stamp;
 80     u64 avg_idle;
 81 
 82     /* This is used to determine avg_idle's max value */
 83     u64 max_idle_balance_cost;
 84 #endif
 85 
 86 #ifdef CONFIG_IRQ_TIME_ACCOUNTING
 87     u64 prev_irq_time;
 88 #endif
 89 #ifdef CONFIG_PARAVIRT
 90     u64 prev_steal_time;
 91 #endif
 92 #ifdef CONFIG_PARAVIRT_TIME_ACCOUNTING
 93     u64 prev_steal_time_rq;
 94 #endif
 95 
 96     /* calc_load related fields */
 97     unsigned long calc_load_update;
 98     long calc_load_active;
 99 
100 #ifdef CONFIG_SCHED_HRTICK
101 #ifdef CONFIG_SMP
102     int hrtick_csd_pending;
103     struct call_single_data hrtick_csd;
104 #endif
105     struct hrtimer hrtick_timer;
106 #endif
107 
108 #ifdef CONFIG_SCHEDSTATS
109     /* latency stats */
110     struct sched_info rq_sched_info;
111     unsigned long long rq_cpu_time;
112     /* could above be rq->cfs_rq.exec_clock + rq->rt_rq.rt_runtime ? */
113 
114     /* sys_sched_yield() stats */
115     unsigned int yld_count;
116 
117     /* schedule() stats */
118     unsigned int sched_count;
119     unsigned int sched_goidle;
120 
121     /* try_to_wake_up() stats */
122     unsigned int ttwu_count;
123     unsigned int ttwu_local;
124 #endif
125 
126 #ifdef CONFIG_SMP
127     struct llist_head wake_list;
128 #endif
129 };

II、睡眠进程被唤醒
    将进程的vruntime值设置为cfs_rq->min_vruntime值,然后再进行一下补偿:将vruntime减去与sysctl_sched_latencyd相关的一个数值。进程进入睡眠状态时cfs_rq->min_vruntime就大于或等于该进程的vruntime值,它在睡眠过程中vruntime值是不改变的,但是cfs_rq->min_vruntime的值却是单调增加的,进程醒来后补偿的量由sysctl_sched_latency给出,不管进程受到的不公平待遇大还是小,一律只补偿这么多。

1 union thread_union { 
2      struct thread_info thread_info;
3      unsigned long stack[THREAD_SIZE/sizeof(long)];    /*内核态的进程堆栈*/
4 };

  O(1)调度器用于Linux2.6.23内核之前,它为每个CPU维护一组进程优先级队列,每个优先级一个队列,这样在选择下一个进程时,只要查询优先级队列相应的位图即可知道哪个队列中有就绪进程,查询时间常数为O(1)。

struct rq

真实模型总结:
    a)进程在就绪队列中用键值key来排序,它没有保存在任何变量中,而是在需要时由函数entity_key()计算得出。它等于
        key = task->vruntime - cfs_rq->min_vruntime
    b)各个进程有不同的重要性(优先等级),越重要的进程权重值weight(task.se.load.weight)越大。
    c)每个进程vruntime行走的速度和weight值成反比。权重值为1024(NICE_0_LOAD)的进程vruntime行走速度和runtime相同。
    d)每个进程每次获得CPU使用权最多执行与该进程对应的ideal_runtime长时间。该时间长度和weight值成正比,它没有用变量来保存,而是需要使用sched_slice()函数计算得出。
    e)ideal_runtime计算的基准是period,它也没有用变量来保存,而是由__sched_period()计算得出。

/*线程描述符(linux4.5 x86架构)*/
/*typedef unsigned int __u32*/
struct thread_info {
    struct task_struct  *task;    /* 存储进(线)程的信息 */
    __u32              flags;    /* 进程标记 */
    __u32              status;    /* 线程状态 */
    __u32              cpu;        /* current CPU */
    mm_segment_t        addr_limit;
    unsigned int        sig_on_uaccess_error:1;
    unsigned int        uaccess_err:1;    /* uaccess failed */
};

问题二:请简述进程优先级、nice和权重之间的关系。

该结构体是本地cpu所有进程组成的就绪队列,在linux内核中,进程被分为普通进程和实时进程,这两种进程的调度策略是不同的,因此在31-32行可以看到rq结构体中又内嵌了struct cfs_rq cfs和struct rt_rq rt两个子就绪队列,分别来组织普通进程和实时进程(普通进程将采用完全公平调度策略cfs,而实时进程将采用实时调度策略),第33行struct dl_rq dl调度空闲进程,暂且不讨论。所以,如果咱们研究的是普通进程的调度,需要关心的就是struct cfs_rq cfs队列;如果研究的是实时进程,就只关心struct rt_rq rt队列。

 

  • 进程在内核态运行时需要自己的堆栈信息, 因此linux内核为每个进程都提供了一个内核栈kernel stack;
  • 内核还需要存储每个进程的PCB信息, linux内核是支持不同体系的的, 但是不同的体系结构可能进程需要存储的信息不尽相同, 这就需要我们实现一种通用的方式, 我们将体系结构相关的部分和无关的部门进行分离;
  • linux将内核栈和thread_info融合在一起, 组成一个联合体thread_union。(下图左块)

  内核使用0~139的数值表示进程的优先级,数值越低优先级越高。优先级0~99给实时进程使用,100~139给普通进程使用。在用户空间由一个传统的变量nice值映射到普通进程的优先级(100~139)。

1.1普通进程的就绪队列struct cfs_rq(kernel/sched/sched.h)

进程的优先等级决定了其权重值,task_struct中与优先级相关数据成员:
    a)static_prio,指普通进程的静态优先级(实时进程没用该参数),值越小则优先级越高。静态优先级是进程启动时分配的优先级。它可以用nice()或者sched_setscheduler()系统调用更改,否则在运行期间一直保持恒定。

图片 3

  nice值从-20~19,进程默认的nice值为0。这可以理解为40个等级,nice值越高,则优先级越低,反之亦然。(nice每变化1,则相应的进程获得CPU的时间就改变10%)。

图片 4图片 5

       注意:关于a),注意本文的结尾添加的注释。

   由上图(左大块为"进程内核栈", 右块为"进程描述符")所示,进程的内核栈是向下增长的,也就是栈底在高位地址,栈顶在低位地址,thread_info在进程内核栈的最低处。其中可总结出:

  权重信息即为调度实体的权重,为了计算方便,内核约定nice值为0的权重值为1024,其他的nice值对应相应的权重值可以通过查表的方式来获取,表即为prio_to_weight。

 1 /* CFS-related fields in a runqueue */
 2 struct cfs_rq {
 3     struct load_weight load;
 4     unsigned int nr_running, h_nr_running;
 5 
 6     u64 exec_clock;
 7     u64 min_vruntime;
 8 #ifndef CONFIG_64BIT
 9     u64 min_vruntime_copy;
10 #endif
11 
12     struct rb_root tasks_timeline;
13     struct rb_node *rb_leftmost;
14 
15     /*
16      * 'curr' points to currently running entity on this cfs_rq.
17      * It is set to NULL otherwise (i.e when none are currently running).
18      */
19     struct sched_entity *curr, *next, *last, *skip;
20 
21 #ifdef    CONFIG_SCHED_DEBUG
22     unsigned int nr_spread_over;
23 #endif
24 
25 #ifdef CONFIG_SMP
26     /*
27      * CFS Load tracking
28      * Under CFS, load is tracked on a per-entity basis and aggregated up.
29      * This allows for the description of both thread and group usage (in
30      * the FAIR_GROUP_SCHED case).
31      */
32     unsigned long runnable_load_avg, blocked_load_avg;
33     atomic64_t decay_counter;
34     u64 last_decay;
35     atomic_long_t removed_load;
36 
37 #ifdef CONFIG_FAIR_GROUP_SCHED
38     /* Required to track per-cpu representation of a task_group */
39     u32 tg_runnable_contrib;
40     unsigned long tg_load_contrib;
41 
42     /*
43      *   h_load = weight * f(tg)
44      *
45      * Where f(tg) is the recursive weight fraction assigned to
46      * this group.
47      */
48     unsigned long h_load;
49     u64 last_h_load_update;
50     struct sched_entity *h_load_next;
51 #endif /* CONFIG_FAIR_GROUP_SCHED */
52 #endif /* CONFIG_SMP */
53 
54 #ifdef CONFIG_FAIR_GROUP_SCHED
55     struct rq *rq;    /* cpu runqueue to which this cfs_rq is attached */
56 
57     /*
58      * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
59      * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
60      * (like users, containers etc.)
61      *
62      * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
63      * list is used during load balance.
64      */
65     int on_list;
66     struct list_head leaf_cfs_rq_list;
67     struct task_group *tg;    /* group that "owns" this runqueue */
68 
69 #ifdef CONFIG_CFS_BANDWIDTH
70     int runtime_enabled;
71     u64 runtime_expires;
72     s64 runtime_remaining;
73 
74     u64 throttled_clock, throttled_clock_task;
75     u64 throttled_clock_task_time;
76     int throttled, throttle_count;
77     struct list_head throttled_list;
78 #endif /* CONFIG_CFS_BANDWIDTH */
79 #endif /* CONFIG_FAIR_GROUP_SCHED */
80 };

    b)rt_priority,表示实时进程的优先级(普通进程没用该参数),它的值介于[0~99]之间。rt_priority的值越大其优先级越高。
    c)normal_prio,由于static_prio和rt_priority与优先级的关联性不相同,因此用normal_prio统一下“单位”,统一成:normal_prio值越小则进程优先级越高。因此,normal_prio也可以理解为:统一了单位的“静态”优先级。
    d)prio,在系统中使用prio判断进程优先级,prio是进程的动态优先级,其表示进程的有效优先级。对于实时进程来说,有效优先级prio就等于它的normal_prio。普通进程可以临时提高优先级,通过改变prio实现,动态优先级的提高不影响进程的静态优先级。父进程的动态优先级不会遗传给子进程,子进程的动态优先级prio初始化为父进程的静态优先级。

  • esp寄存器为CPU栈指针,用来存放栈顶单元的地址。当数据写入时,esp的值减少;
  • thread_info和内核栈虽然共用了thread_union结构, 但是thread_info大小固定, 存储在联合体的开始部分, 而内核栈由高地址向低地址扩展, 当内核栈的栈顶到达thread_info的存储空间时, 则会发生栈溢出(内核中有kstack_end函数判断);
  • 系统的current指针指向了当前运行进程的thread_union(或者thread_info)的地址;

问题三:请简述CFS调度器是如何工作的。

struct cfs_rq

注:

   其中在早期的Linux内核中使用struct thread_info *thread_info,而之后的新版本(2.6.22后)中用进程task_struct中的stack指针指向了进程的thread_union(或者thread_info)的地址来代替thread_info指针,因为联合体中stack和thread_info都在起始地址, 因此可以很方便的转型:

  CFS调度器抛弃以前固定时间片和固定调度周期的算法,采用进程权重值的比重来量化和计算实际运行时间。引入虚拟时钟的概念,每个进程的虚拟时间是实际运行时间相对nice值为0的权重的比例值。进程按照各自不同的速率比在物理时钟节拍内前进。nice值小的进程,优先级高且权重大,其虚拟时钟比真实时钟跑得慢,但是可以获得比较多的运行时间;反之,nice值大的进程,优先级低,权重也低,其虚拟时钟比真实时钟跑得快,获得比较少的运行时间。CFS调度器总是选择虚拟时钟跑得慢的进程,类似一个多级变速箱,nice值为0的进程是基准齿轮,其他各个进程在不同变速比下相互追赶,从而达到公正公平。

cfs_rq就绪队列是以红黑树的形式来组织调度实体。第12行tasks_timeline成员就是红黑树的树根。第13行rb_leftmost指向了红黑树最左边的左孩子(下一个可调度的实体)。第19行curr指向当前正运行的实体,next指向将被唤醒的进程,last指向唤醒next进程的进程,next和last用法后边会提到。第55行rq指向了该cfs_rq就绪队列所属的rq队列。

由于在某些情况下需要暂时提高进程的优先级,因此不仅需要静态优先级和普通优先级,还需要动态优先级prio;

#define task_thread_info(task)  ((struct thread_info *)(task)->stack)

问题四:CFS调度器中的vruntime是如何计算的?

1.2实时进程的就绪队列struct rt_rq(kernel/sched/sched.h)

参考《深入Linux内核架构》p70-76、 p_288-290;

  1.3进程标示符PID:

  vruntime=(delta_exec*nice_0_weight)/weight。其中,delta_exec为实际运行时间,nice_0_weight为nice为0的权重值,weight表示该进程的权重值。在update_curr()函数中,完成了该值的计算,此时,为了计算高效,将计算方式变成了乘法和移位vruntime=(delta_exec*nice_0_weight*inv_weight)>>shift,其中inv_weight=2^32/weight,是预先计算好存放在prio_to_wmult中的。

图片 6图片 7

         linux内核的优先级继承协议(pip)

struct task_struct {
    ........

问题五:vruntime是何时更新的?

 1 /* Real-Time classes' related field in a runqueue: */
 2 struct rt_rq {
 3     struct rt_prio_array active;
 4     unsigned int rt_nr_running;
 5 #if defined CONFIG_SMP || defined CONFIG_RT_GROUP_SCHED
 6     struct {
 7         int curr; /* highest queued rt task prio */
 8 #ifdef CONFIG_SMP
 9         int next; /* next highest */
10 #endif
11     } highest_prio;
12 #endif
13 #ifdef CONFIG_SMP
14     unsigned long rt_nr_migratory;
15     unsigned long rt_nr_total;
16     int overloaded;
17     struct plist_head pushable_tasks;
18 #endif
19     int rt_queued;
20 
21     int rt_throttled;
22     u64 rt_time;
23     u64 rt_runtime;
24     /* Nests inside the rq lock: */
25     raw_spinlock_t rt_runtime_lock;
26 
27 #ifdef CONFIG_RT_GROUP_SCHED
28     unsigned long rt_nr_boosted;
29 
30     struct rq *rq;
31     struct task_group *tg;
32 #endif
33 };

         进程优先级逆转问题的解决  

    /* 进程ID,每个进程(线程)的PID都不同 */
    pid_t pid;
    /* 线程组ID,同一个线程组拥有相同的pid,与领头线程(该组中第一个轻量级进程)pid一致,保存在tgid中,线程组领头线程的pid和tgid相同 */
    pid_t tgid;
    /* 用于连接到PID、TGID、PGRP、SESSION哈希表 */
    struct pid_link pids[PIDTYPE_MAX];
    /*PID : 进程的ID(Process Identifier),对应pids[PIDTYPE_PID]
    *TGID : 线程组ID(Thread Group Identifier),对应pids[PIDTYPE_TGID]
    *PGRP : 进程组(Process Group),对应pids[PIDTYPE_PGID]
    *SESSION : 会话(Session),对应pids[PIDTYPE_SID]
    */

  创建新进程,加入就绪队列,调度tick等都会更新当前vruntime值。

struct rt_rq

        为了在Linux中使用Priority Inheritance Protocol协议来解决优先级反转问题,Linux中引入实时互斥量rt_mutex,在task_struc结构体中也引入了pi_waiters链表,需要注意的流程为:

    ........
};

问题六:CFS调度器中的min_vruntime有什么作用?

2.调度实体(include/linux/sched.h)

         rt_mutex_slowlock() ----> __rt_mutex_slowlock() ---->

    PID就像我们学生的学号,每个人的身份证号一样,是独一无二的。而我们会有一个群体,比如同一个班级,同一个学校等,即有同一个组群,因此建立了TGID,用来将同一个组的PID串联起来。其中getpid()返回当前进程的tgid值而不是pid的值。

  min_vruntime在CFS就绪队列数据结构中,单步递增,用于跟踪该就绪队列红黑树中最小的vruntime。

2.1普通进程的调度实体sched_entity

                 task_blocks_on_rt_mutex() ---->  __rt_mutex_adjust_prio()

    而在系统运行的时候,可能会建立非常非常多的进程,因此为了提高内核的查找效率,专门建立了四个hash表pids[PIDTYPE_TGID]、pids[PIDTYPE_TGID]、pids[PIDTYPE_PGID]、pids[PIDTYPE_SID]用来索引。

问题七:CFS调度器对新创建的进程和刚唤醒的进程有何关照?

 1 struct sched_entity {
 2     struct load_weight    load;        /* for load-balancing */
 3     struct rb_node        run_node;
 4     struct list_head    group_node;
 5     unsigned int        on_rq;
 6 
 7     u64            exec_start;
 8     u64            sum_exec_runtime;
 9     u64            vruntime;
10     u64            prev_sum_exec_runtime;
11 
12     u64            nr_migrations;
13 
14 #ifdef CONFIG_SCHEDSTATS
15     struct sched_statistics statistics;
16 #endif
17 
18 #ifdef CONFIG_FAIR_GROUP_SCHED
19     int            depth;
20     struct sched_entity    *parent;
21     /* rq on which this entity is (to be) queued: */
22     struct cfs_rq        *cfs_rq;
23     /* rq "owned" by this entity/group: */
24     struct cfs_rq        *my_q;
25 #endif
26 
27 #ifdef CONFIG_SMP
28     /* Per-entity load-tracking */
29     struct sched_avg    avg;
30 #endif
31 };

                                                                   |--> rt_mutex_adjust_prio_chain()

    在内核中,这四个哈希表一共占16个页框,也就是每个哈希表占4个页框,他们每个可以拥有2048个表项,内核会把把这四个哈希表的地址保存到pid_hash数组中。现在问题来了,拿pids[PIDTYPE_TGID]为例,怎么在2048个表项中保存32767个PID值,其实内核会对每个已经分配的PID值进行一个处理,得到的结果的数值就是对应的表项,处理结果相同的PID被串成一个链表,如下:

  对于睡眠进程,其vruntime在睡眠期间不增长,在唤醒后如果还用原来的vruntime值,会进行报复性满载运行,所以要修正vruntime,具体在enqueue_entity()函数中,计算公式为vruntime+=min_vruntime,vruntime=MAX(vruntime, min_vruntime-sysctl_sched_lantency/2)。

每个进程描述符中均包含一个该结构体变量,内核使用该结构体来将普通进程组织到采用完全公平调度策略的就绪队列中(struct rq中的cfs队列中,上边提到过),该结构体有两个作用,一是包含有进程调度的信息(比如进程的运行时间,睡眠时间等等,调度程序参考这些信息决定是否调度进程),二是使用该结构体来组织进程,第3行的struct rb_node类型结构体变量run_node是红黑树节点,因此struct sched_entity调度实体将被组织成红黑树的形式,同时意味着普通进程也被组织成红黑树的形式。第18-25行是和组调度有关的成员,需要开启组调度。第20行parent顾名思义指向了当前实体的上一级实体,后边再介绍。第22行的cfs_rq指向了该调度实体所在的就绪队列。第24行my_q指向了本实体拥有的就绪队列(调度组),该调度组(包括组员实体)属于下一个级别,和本实体不在同一个级别,该调度组中所有成员实体的parent域指向了本实体,这就解释了上边的parent,此外,第19行depth代表了此队列(调度组)的深度,每个调度组都比其parent调度组深度大1。内核依赖my_q域实现组调度。

          __rt_mutex_adjust_prio调整了当前持有锁的进程的动态优先级(继承自等待队列中所有进程的最高优先级),rt_mutex_adjust_prio_chain()如果被调整的动态优先级的进程也在等待某个资源,那么也要链式地调整相应进程的动态优先级。

图片 8

  对于新创建的进程,需要加上一个调度周期的虚拟是时间(sched_vslice())。首先在task_fork_fair()函数中,place_entity()增加了调度周期的虚拟时间,相当于惩罚,se->vruntime=sched_vslice()。接着新进程在添加到就绪队列时,wake_up_new_task()->activate_task()->enqueue_entity()函数里,se->vruntime+=cfs_rq->min_vruntime。

2.2实时进程的调度实体 sched_rt_entity

关于Priority Inversion可以参考《Operating System Concepts》9_ed p217-218                                                                                                                       

    当我们使用"kill 29384"命令时,内核会根据29384处理得出199,然后以199为下标,获取PID哈希表中对应的链表头,并在此链表中找出PID=29384的进程。在进程描述符(thread_info)的*task中使用struct pid_link pids[PIDTYPE_MAX]链入这四个哈希表。对于另外三个哈希表,道理一样。

问题八:如何计算普通进程的平均负载load_avg_contrib?runnable_avg_sum和runnable_avg_period分别表示了什么含义?

 1 struct sched_rt_entity {
 2     struct list_head run_list;
 3     unsigned long timeout;
 4     unsigned long watchdog_stamp;
 5     unsigned int time_slice;
 6 
 7     struct sched_rt_entity *back;
 8 #ifdef CONFIG_RT_GROUP_SCHED
 9     struct sched_rt_entity    *parent;
10     /* rq on which this entity is (to be) queued: */
11     struct rt_rq        *rt_rq;
12     /* rq "owned" by this entity/group: */
13     struct rt_rq        *my_q;
14 #endif
15 };

  1.4进程状态的转换:

  load_avg_contrib=runnable_avg_sum*weight/runnable_avg_period。

该结构体和上个结构体是类似的,只不过用来组织实时进程,实时进程被组织到struct rq中的rt队列中,上边有提到。每个进程描述符中也包含一个该结构体。该结构体中并未包含struct rb_node类型结构体变量,而在第1行出现了struct list_head类型结构体变量run_list,因此可以看出实时进程的就绪队列是双向链表形式,而不是红黑数的形式。

    进程的状态用state表示,简单表示有以下3种:

  runnable_avg_sum为调度实体的可运行状态下总衰减累加时间。

3.调度类(kernel/sched/sched.h)

volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */

  runnable_avg_period记录的是上一次更新时的总周期数(一个周期是1024us),即调度实体在调度器中的总衰减累加时间。

 1 struct sched_class {
 2     const struct sched_class *next;
 3 
 4     void (*enqueue_task) (struct rq *rq, struct task_struct *p, int flags);
 5     void (*dequeue_task) (struct rq *rq, struct task_struct *p, int flags);
 6     void (*yield_task) (struct rq *rq);
 7     bool (*yield_to_task) (struct rq *rq, struct task_struct *p, bool preempt);
 8 
 9     void (*check_preempt_curr) (struct rq *rq, struct task_struct *p, int flags);
10 
11     /*
12      * It is the responsibility of the pick_next_task() method that will
13      * return the next task to call put_prev_task() on the @prev task or
14      * something equivalent.
15      *
16      * May return RETRY_TASK when it finds a higher prio class has runnable
17      * tasks.
18      */
19     struct task_struct * (*pick_next_task) (struct rq *rq,
20                         struct task_struct *prev);
21     void (*put_prev_task) (struct rq *rq, struct task_struct *p);
22 
23 #ifdef CONFIG_SMP
24     int  (*select_task_rq)(struct task_struct *p, int task_cpu, int sd_flag, int flags);
25     void (*migrate_task_rq)(struct task_struct *p, int next_cpu);
26 
27     void (*post_schedule) (struct rq *this_rq);
28     void (*task_waking) (struct task_struct *task);
29     void (*task_woken) (struct rq *this_rq, struct task_struct *task);
30 
31     void (*set_cpus_allowed)(struct task_struct *p,
32                  const struct cpumask *newmask);
33 
34     void (*rq_online)(struct rq *rq);
35     void (*rq_offline)(struct rq *rq);
36 #endif
37 
38     void (*set_curr_task) (struct rq *rq);
39     void (*task_tick) (struct rq *rq, struct task_struct *p, int queued);
40     void (*task_fork) (struct task_struct *p);
41     void (*task_dead) (struct task_struct *p);
42 
43     void (*switched_from) (struct rq *this_rq, struct task_struct *task);
44     void (*switched_to) (struct rq *this_rq, struct task_struct *task);
45     void (*prio_changed) (struct rq *this_rq, struct task_struct *task,
46                  int oldprio);
47 
48     unsigned int (*get_rr_interval) (struct rq *rq,
49                      struct task_struct *task);
50 
51 #ifdef CONFIG_FAIR_GROUP_SCHED
52     void (*task_move_group) (struct task_struct *p, int on_rq);
53 #endif
54 };

    其中详细有以下状态:

  runnable_avg_sum越接近runnable_avg_period,则平均负载越大,表示该调度实体一直在占用CPU。

内核声明了一个调度类sched_class的结构体类型,用来实现不同的调度策略,可以看到该结构体成员都是函数指针,这些指针指向的函数就是调度策略的具体实现,所有和进程调度有关的函数都直接或者间接调用了这些成员函数,来实现进程调度。此外,每个进程描述符中都包含一个指向该结构体类型的指针sched_class,指向了所采用的调度类。下面我们看下完全公平调度策略类的定义和初始化(kernel/sched/fair.c)。

/*
 * Task state bitmask. NOTE! These bits are also
 * encoded in fs/proc/array.c: get_task_state().
 *
 * We have two separate sets of flags: task->state
 * is about runnability, while task->exit_state are
 * about the task exiting. Confusing, but this way
 * modifying one set can't modify the other one by
 * mistake.
 */
#define TASK_RUNNING            0
#define TASK_INTERRUPTIBLE      1
#define TASK_UNINTERRUPTIBLE    2
#define __TASK_STOPPED          4
#define __TASK_TRACED          8

问题九:内核代码中定义了若干个表,请分别说出它们的含义,比如prio_to_weight、prio_to_wmult、runnable_avg_yN_inv、runnable_avg_yN_sum。

1 const struct sched_class fair_sched_class;

/* in tsk->exit_state */
#define EXIT_DEAD              16
#define EXIT_ZOMBIE            32
#define EXIT_TRACE              (EXIT_ZOMBIE | EXIT_DEAD)
 
/* in tsk->state again */
#define TASK_DEAD              64
#define TASK_WAKEKILL          128    /** wake on signals that are deadly **/
#define TASK_WAKING            256
#define TASK_PARKED            512
#define TASK_NOLOAD            1024
#define TASK_STATE_MAX          2048

  prio_to_weight表记录的是nice值对应的权重值。

定义了一个全局的调度策略变量。初始化如下:

 /* Convenience macros for the sake of set_task_state */
#define TASK_KILLABLE          (TASK_WAKEKILL | TASK_UNINTERRUPTIBLE)
#define TASK_STOPPED            (TASK_WAKEKILL | __TASK_STOPPED)
#define TASK_TRACED            (TASK_WAKEKILL | __TASK_TRACED)

  prio_to_wmult表记录的是nice值对应的权重值倒转后的值inv_weight=2^32/weight。

 1 const struct sched_class fair_sched_class = {
 2     .next            = &idle_sched_class,
 3     .enqueue_task        = enqueue_task_fair,
 4     .dequeue_task        = dequeue_task_fair,
 5     .yield_task        = yield_task_fair,
 6     .yield_to_task        = yield_to_task_fair,
 7 
 8     .check_preempt_curr    = check_preempt_wakeup,
 9 
10     .pick_next_task        = pick_next_task_fair,
11     .put_prev_task        = put_prev_task_fair,
12 
13 #ifdef CONFIG_SMP
14     .select_task_rq        = select_task_rq_fair,
15     .migrate_task_rq    = migrate_task_rq_fair,
16 
17     .rq_online        = rq_online_fair,
18     .rq_offline        = rq_offline_fair,
19 
20     .task_waking        = task_waking_fair,
21 #endif
22 
23     .set_curr_task          = set_curr_task_fair,
24     .task_tick        = task_tick_fair,
25     .task_fork        = task_fork_fair,
26 
27     .prio_changed        = prio_changed_fair,
28     .switched_from        = switched_from_fair,
29     .switched_to        = switched_to_fair,
30 
31     .get_rr_interval    = get_rr_interval_fair,
32 
33 #ifdef CONFIG_FAIR_GROUP_SCHED
34     .task_move_group    = task_move_group_fair,
35 #endif
36 };

1.4.1五种互斥状态:      

  runnable_avg_yN_inv表是为了避免CPU做浮点计算,提前计算了公式2^32*实际衰减因子(第32ms约为0.5)的值,有32个下标,对应过去0~32ms的负载贡献的衰减因子。

可以看到该结构体变量中函数成员很多,它们实现了不同的功能,待会用到时我们再做分析。

state域能够取5个互为排斥的值(简单来说就是这五个值任意两个不能一起使用,只能单独使用):

  runnable_avg_yN_sum表为1024*(y+y^2+…+y^n),y为实际衰减因子,n取1~32。(实际衰减因子下图所示)

4.进程描述符task_struct(include/linux/sched.h)

状态 描述
TASK_RUNNING 表示进程要么正在执行,要么正要准备执行(已经就绪),正在等待cpu时间片的调度
TASK_INTERRUPTIBLE 进程因为等待一些条件而被挂起(阻塞)而所处的状态。这些条件主要包括:硬中断、资源、一些信号……,一旦等待的条件成立,进程就会从该状态(阻塞)迅速转化成为就绪状态TASK_RUNNING
TASK_UNINTERRUPTIBLE 意义与TASK_INTERRUPTIBLE类似,除了不能通过接受一个信号来唤醒以外,对于处于TASK_UNINTERRUPIBLE状态的进程,哪怕我们传递一个信号或者有一个外部中断都不能唤醒他们。只有它所等待的资源可用的时候,他才会被唤醒。这个标志很少用,但是并不代表没有任何用处,其实他的作用非常大,特别是对于驱动刺探相关的硬件过程很重要,这个刺探过程不能被一些其他的东西给中断,否则就会让进城进入不可预测的状态
TASK_STOPPED 进程被停止执行,当进程接收到SIGSTOP、SIGTTIN、SIGTSTP或者SIGTTOU信号之后就会进入该状态
TASK_TRACED 表示进程被debugger等进程监视,进程执行被调试程序所停止,当一个进程被另外的进程所监视,每一个信号都会让进城进入该状态

图片 9图 实际衰减因子

 1 struct task_struct {
 2     volatile long state;    /* -1 unrunnable, 0 runnable, >0 stopped */
 3     .....
 4     int on_rq;
 5 
 6     int prio, static_prio, normal_prio;
 7     unsigned int rt_priority;
 8     const struct sched_class *sched_class;
 9     struct sched_entity se;
10     struct sched_rt_entity rt;
11 #ifdef CONFIG_CGROUP_SCHED
12     struct task_group *sched_task_group;
13 #endif
14     struct sched_dl_entity dl;
15     .....
16     .....
17     unsigned int policy;
18     .....
19     .....
20     struct sched_info sched_info;
21     .....
22     .....
23 };

 1.4.2二种终止状态:      

问题十:如果一个普通进程在就绪队列里等待了很长时间才被调度,那么它的平均负载该如何计算?

只列出了和进程调度有关的成员。第6行三个变量代表了普通进程的三个优先级,第7行的变量代表了实时进程的优先级。关于进程优先级的概念,大家可以看看《深入理解linux内核架构》这本书的进程管理章节。第8-10行就是我们上边提到的那些结构体在进程描述符中的定义。第17行的policy代表了当前进程的调度策略,内核给出了宏定义,它可以在这些宏中取值,关于详细的讲解还是去看《深入理解linux内核架构》这本书的进程管理部分。policy取了什么值,sched_class也应该取相应的调度类指针。

      这两个附加的进程状态既可以被添加到state域中,又可以被添加到exit_state域中。只有当进程终止的时候,才会达到这两种状态:

   一个进程等待很长时间之后(过了很多个period),原来的runnable_avg_sum和runable_ave_period值衰减后可能变成0,相当于之前的统计值被清0。

进程调度过程分析:

状态 描述
EXIT_ZOMBIE 进程的执行被终止,但是其父进程还没有使用wait()等系统调用来获知它的终止信息,此时进程成为僵尸进程
EXIT_DEAD 进程的最终状态

进程调度过程分为两部分,一是对进程信息进行修改,主要是修改和调度相关的信息,比如进程的运行时间,睡眠时间,进程的状态,cpu的负荷等等,二是进程的切换。和进程调度相关的所有函数中,只有schedule函数是用来进行进程切换的,其他函数都是用来修改进程的调度信息。schedule函数我们在前边的博文中已经探讨过了,这里不再分析。对于其他函数,我们将按照其功能,逐类来分析。

    1.4.3睡眠状态:      

      正常只需将state域的值设为以下两种状态就可进入睡眠状态:

状态 描述
TASK_INTERRUPTIBLE 进程处于睡眠状态,正在等待某些事件发生。进程可以被信号中断。接收到信号或被显式的唤醒呼叫唤醒之后,进程将转变为 TASK_RUNNING 状态。
TASK_UNINTERRUPTIBLE 此进程状态类似于 TASK_INTERRUPTIBLE,只是它不会处理信号。中断处于这种状态的进程是不合适的,因为它可能正在完成某些重要的任务。 当它所等待的事件发生时,进程将被显式的唤醒呼叫唤醒。

      而在Linux2.6.25以后,新增了一条睡眠状态 : “TASK_KILLABLE”:

状态 描述
TASK_KILLABLE 当进程处于这种可以终止的新睡眠状态中,它的运行原理类似于 TASK_UNINTERRUPTIBLE,只不过可以响应致命信号。

      由代码的line 31可以看出,TASK_UNINTERRUPTIBLE + TASK_WAKEKILL = TASK_KILLABLE。

1.scheduler_tick(kernel/sched/core.c )

  1.4.4进程转换图:     图片 10

  因此,通过对以上数据的操作,操作系统便可以对进程进行组织和管理。

 1 void scheduler_tick(void)
 2 {
 3     int cpu = smp_processor_id();
 4     struct rq *rq = cpu_rq(cpu);
 5     struct task_struct *curr = rq->curr;
 6 
 7     sched_clock_tick();
 8 
 9     raw_spin_lock(&rq->lock);
10     update_rq_clock(rq);
11     curr->sched_class->task_tick(rq, curr, 0);
12     update_cpu_load_active(rq);
13     raw_spin_unlock(&rq->lock);
14 
15     perf_event_task_tick();
16 
17 #ifdef CONFIG_SMP
18     rq->idle_balance = idle_cpu(cpu);
19     trigger_load_balance(rq);
20 #endif
21     rq_last_tick_reset(rq);
22 }

2.进程是怎么被调度的?

该函数被时钟中断处理程序调用,将当前cpu的负载情况记载到运行队列struct rq的某些成员中,并更新当前进程的时间片。第3行获取当前的cpu号,第4行获取当前cpu的就绪队列(每个cpu有一个)rq,第5行从就绪队列中获取当前运行进程的描述符,第10行更新就绪队列中的clock和clock_task成员值,代表当前的时间,一般我们会用到clock_task。第11行进入当前进程的调度类的task_tick函数中,更新当前进程的时间片,不同调度类的该函数实现不同,待会我们分析下完全公平调度类的该函数。第12行更新就绪队列的cpu负载信息。第18行判断当前cpu是否是空闲的,是的话idle_cpu返回1,否则返回0。第19行挂起SCHED_SOFTIRQ软中断函数,去做周期性的负载平衡操作。第21行将最新的时钟滴答数jiffies存入就绪队列的last_sched_tick域中。再来看下task_tick_fair函数(kernel/sched/fair.c):

  2.1什么是调度器?    

    一台个人电脑,最直观的资源便是你的硬盘、磁盘、内存等等,但其实CPU也是一个资源,每个程序在跑的时候都需要占用CPU一定时间。因此,如何让每个程序合理、公平地跑一定的时间,是一个很重要的问题,需要设计一个专门的地方去分配,这就是调度器。调度器的一个重要目标是有效地分配 CPU 时间片,同时提供很好的用户体验。调度器还需要面对一些互相冲突的目标,例如既要为关键实时任务最小化响应时间, 又要最大限度地提高 CPU 的总体利用率。

 1 static void task_tick_fair(struct rq *rq, struct task_struct *curr, int queued)
 2 {
 3     struct cfs_rq *cfs_rq;
 4     struct sched_entity *se = &curr->se;
 5 
 6     for_each_sched_entity(se) {
 7         cfs_rq = cfs_rq_of(se);
 8         entity_tick(cfs_rq, se, queued);
 9     }
10 
11     if (numabalancing_enabled)
12         task_tick_numa(rq, curr);
13 
14     update_rq_runnable_avg(rq, 1);
15 }

  2.2进程的分类.

    当涉及有关调度的问题时, 传统上把进程分类为”I/O受限(I/O-dound)”或”CPU受限(CPU-bound)”.

类型

别称

描述

示例

I/O受限型

I/O密集型

频繁的使用I/O设备, 并花费很多时间等待I/O操作的完成

数据库服务器, 文本编辑器

CPU受限型

计算密集型

花费大量CPU时间进行数值计算

图形绘制程序

    另外一种分类法把进程区分为三类:

类型

描述

示例

交互式进程(interactive process)

此类进程经常与用户进行交互, 因此需要花费很多时间等待键盘和鼠标操作. 当接受了用户的输入后, 进程必须很快被唤醒, 否则用户会感觉系统反应迟钝

shell, 文本编辑程序和图形应用程序

批处理进程(batch process)

此类进程不必与用户交互, 因此经常在后台运行. 因为这样的进程不必很快相应, 因此常受到调度程序的怠慢

程序语言的编译程序, 数据库搜索引擎以及科学计算

实时进程(real-time process)

这些进程由很强的调度需要, 这样的进程绝不会被低优先级的进程阻塞. 并且他们的响应时间要尽可能的短

视频音频应用程序, 机器人控制程序以及从物理传感器上收集数据的程序

如果某个进程的调度类采用完全公平调度类的话,那么上个函数scheduler_tick第11行所执行的task_tick函数指针,就指向了本函数。可以回头看看完全公平调度对象的初始化,第24行的赋值语句.task_tick

task_tick_fair。回到本函数,第4行获取当前进程的普通调度实体,将指针存放到se中,第6-8行遍历当前调度实体的上一级实体,以及上上一级实体,以此类推,然后在entity_tick函数中更新调度实体的运行时间等信息。在这里用循环来遍历的原因是当开启了组调度后,调度实体的parent域就存储了它的上一级节点,该实体和它parent指向的实体不是同一级别,因此使用循环就把从当前级别(组)到最顶层的级别遍历完了;如果未选择组支持,则循环只执行一次,仅对当前调度实体进行更新。下面看下entity_tick的代码(kernel/sched/fair.c):

 1 static void
 2 entity_tick(struct cfs_rq *cfs_rq, struct sched_entity *curr, int queued)
 3 {
 4     /*
 5      * Update run-time statistics of the 'current'.
 6      */
 7     update_curr(cfs_rq);
 8 
 9     /*
10      * Ensure that runnable average is periodically updated.
11      */
12     update_entity_load_avg(curr, 1);
13     update_cfs_rq_blocked_load(cfs_rq, 1);
14     update_cfs_shares(cfs_rq);
15 
16 #ifdef CONFIG_SCHED_HRTICK
17     /*
18      * queued ticks are scheduled to match the slice, so don't bother
19      * validating it and just reschedule.
20      */
21     if (queued) {
22         resched_task(rq_of(cfs_rq)->curr);
23         return;
24     }
25     /*
26      * don't let the period tick interfere with the hrtick preemption
27      */
28     if (!sched_feat(DOUBLE_TICK) &&
29             hrtimer_active(&rq_of(cfs_rq)->hrtick_timer))
30         return;
31 #endif
32 
33     if (cfs_rq->nr_running > 1)
34         check_preempt_tick(cfs_rq, curr);
35 }

在该函数中对调度实体(进程)的运行时间等信息进行更新。第7行update_curr函数对当前进程的运行时间进行更新,随后分析。 第21行如果传进来的参数queued不为0的话,当前进程会被无条件设置重新调度标志(允许被抢占了)。第33-34行如果当前cfs_rq队列等待调度的进程数量大于1,那么就执行check_preempt_tick函数检查当前进程的时间片是否用完,用完的话就需要调度别的进程来运行(具体来说,如果当前进程“真实时间片”用完,该函数给当前进程设置need_resched标志,然后schedule程序就可以重新在就绪队列中调度新的进程),下面分析update_curr函数(kernel/sched/fair.c):

 1 static void update_curr(struct cfs_rq *cfs_rq)
 2 {
 3     struct sched_entity *curr = cfs_rq->curr;
 4     u64 now = rq_clock_task(rq_of(cfs_rq));
 5     u64 delta_exec;
 6 
 7     if (unlikely(!curr))
 8         return;
 9 
10     delta_exec = now - curr->exec_start;
11     if (unlikely((s64)delta_exec <= 0))
12         return;
13 
14     curr->exec_start = now;
15 
16     schedstat_set(curr->statistics.exec_max,
17               max(delta_exec, curr->statistics.exec_max));
18 
19     curr->sum_exec_runtime += delta_exec;
20     schedstat_add(cfs_rq, exec_clock, delta_exec);
21 
22     curr->vruntime += calc_delta_fair(delta_exec, curr);
23     update_min_vruntime(cfs_rq);
24 
25     if (entity_is_task(curr)) {
26         struct task_struct *curtask = task_of(curr);
27 
28         trace_sched_stat_runtime(curtask, delta_exec, curr->vruntime);
29         cpuacct_charge(curtask, delta_exec);
30         account_group_exec_runtime(curtask, delta_exec);
31     }
32 
33     account_cfs_rq_runtime(cfs_rq, delta_exec);
34 } 

该函数是更新进程运行时间最核心的一个函数。第3行获取当前的调度实体,第4行从就绪队列rq的clock_task成员中获取当前时间,存入now中,该成员我们在scheduler_tick函数中提到过。第10行用当前时间减去进程在上次时钟中断tick中的开始时间得到进程运行的时间间隔,存入delta_exec中。第14行当前时间又成为进程新的开始时间。第19行将进程运行的时间间隔delta_exec累加到调度实体的sum_exec_runtime成员中,该成员代表进程到目前为止运行了多长时间。第20行将进程运行的时间间隔delta_exec也累加到公平调度就绪队列cfs_rq的exec_clock成员中。第22行calc_delta_fair函数很关键,它将进程执行的真实运行时间转换成虚拟运行时间,然后累加到调度实体的vruntime域中,进程的虚拟时间非常重要,完全公平调度策略就是依赖该时间进行调度。关于进程的真实时间和虚拟时间的概念,以及它们之间的转换算法,文章的后面会提到,详细的内容大家可以看看《深入理解linux内核架构》的进程管理章节。第23行更新cfs_rq队列中的最小虚拟运行时间min_vruntime,该时间是就绪队列中所有进程包括当前进程的已运行的最小虚拟时间,只能单调递增,待会我们分析update_min_vruntime函数,该函数比较重要。第25-30行,如果调度单位是进程的话(不是组),会更新进程描述符中的运行时间。第33行更新cfs_rq队列的剩余运行时间,并计算出期望运行时间,必要的话可以对进程重新调度。下面我们先分析update_min_vruntime函数,然后分析calc_delta_fair函数(kernel/sched/fair.c):

 1 static void update_min_vruntime(struct cfs_rq *cfs_rq)
 2 {
 3     u64 vruntime = cfs_rq->min_vruntime;
 4 
 5     if (cfs_rq->curr)
 6         vruntime = cfs_rq->curr->vruntime;
 7 
 8     if (cfs_rq->rb_leftmost) {
 9         struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
10                            struct sched_entity,
11                            run_node);
12 
13         if (!cfs_rq->curr)
14             vruntime = se->vruntime;
15         else
16             vruntime = min_vruntime(vruntime, se->vruntime);
17     }
18 
19     /* ensure we never gain time by being placed backwards. */
20     cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
21 #ifndef CONFIG_64BIT
22     smp_wmb();
23     cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
24 #endif
25 } 

每个cfs_rq队列均有一个min_vruntime成员,装的是就绪队列中所有进程包括当前进程已运行的虚拟时间中最小的那个时间。本函数来更新这个时间。第5-6行如果当前有进程正在执行,将当前进程已运行的虚拟时间保存在vruntime变量中。第8-17行如果就绪队列中有下一个要被调度的进程(由rb_leftmost指针指向),则进入if体,第13-16行从当前进程和下个被调度进程中,选择最小的已运行虚拟时间,保存到vruntime中。第20行从当前队列的min_vruntime域和vruntime变量中,选最大的保存到队列的min_vruntime域中,完成更新。其实第13-17行是最关键的,保证了队列的min_vruntime域中存放的是就绪队列中最小的虚拟运行时间,而第20行的作用仅仅是保证min_vruntime域中的值单调递增,没有别的含义了。队列中的min_vruntime成员非常重要,用于在睡眠进程被唤醒后以及新进程被创建好时,进行虚拟时间补偿或者惩罚,后面会分析到。

1 static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
2 {
3     if (unlikely(se->load.weight != NICE_0_LOAD))
4         delta = __calc_delta(delta, NICE_0_LOAD, &se->load);
5 
6     return delta;
7 } 

第3行判断当前进程nice值是否为0,如果是的话,直接返回真实运行时间delta(nice0级别的进程真实运行时间和虚拟运行时间值相等);如果不是的话,第4行将真实时间转换成虚拟时间。下面我们分析__calc_delta函数(kernel/sched/fair.c):

 1 static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
 2 {
 3     u64 fact = scale_load_down(weight);
 4     int shift = WMULT_SHIFT;
 5 
 6     __update_inv_weight(lw);
 7 
 8     if (unlikely(fact >> 32)) {
 9         while (fact >> 32) {
10             fact >>= 1;
11             shift--;
12         }
13     }
14 
15     /* hint to use a 32x32->64 mul */
16     fact = (u64)(u32)fact * lw->inv_weight;
17 
18     while (fact >> 32) {
19         fact >>= 1;
20         shift--;
21     }
22 
23     return mul_u64_u32_shr(delta_exec, fact, shift);
24 }

该函数执行了两种算法:要么是delta_exec * weight / lw.weight,要么是(delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT。计算的结果就是转换后的虚拟时间。至此,scheduler_tick函数大致就分析完了,当然还有一些细节没有分析到,进程调度这块非常庞杂,要想把所有函数分析完非常耗费时间和精力,以后如果分析到的话,再慢慢补充。scheduler_tick函数主要更新进程的运行时间,包括物理时间和虚拟时间。

2.进程优先级设置的函数,进程的优先级和调度关系密切,通过上边分析可以看到,计算进程的虚拟运行时间要用到优先级,优先级决定进程权重,权重决定进程虚拟时间的增加速度,最终决定进程可运行时间的长短。权重越大的进程可以执行的时间越长。从effective_prio函数开始(kernel/sched/core.c):

 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
 7      * to the normal priority:
 8      */
 9     if (!rt_prio(p->prio))
10         return p->normal_prio;
11     return p->prio;
12 }

该函数在进程创建时或者在用户的nice系统调用中都会被调用到,来设置进程的活动优先级(进程的三种优先级:活动优先级prio,静态优先级static_prio,普通优先级normal_prio),该函数设计的有一定技巧性,函数的返回值是用来设置进程的活动优先级,但是在函数体中也把进程的普通优先级设置了。第3行设置进程的普通优先级,随后分析normal_prio函数。第9-11行,通过进程的活动优先级可以判断出该进程是不是实时进程,如果是实时进程,则执行11行,返回p->prio,实时进程的活动优先级不变。否则返回p->normal_prio,这说明普通进程的活动优先级等于它的普通优先级。下面我们看看normal_prio函数(kernel/sched/core.c):

 1 static inline int normal_prio(struct task_struct *p)
 2 {
 3     int prio;
 4 
 5     if (task_has_dl_policy(p))
 6         prio = MAX_DL_PRIO-1;
 7     else if (task_has_rt_policy(p))
 8         prio = MAX_RT_PRIO-1 - p->rt_priority;
 9     else
10         prio = __normal_prio(p);
11     return prio;
12 }

该函数用来设置进程的普通优先级。第5行判断当前进程是不是空闲进程,是的话设置进程的普通优先级为-1(-1是空闲进程的优先级),否则的话第7行判断进程是不是实时进程,是的话设置实时进程的普通优先级为0-99(数字越小优先级越高),可以看到这块减去了p->rt_priority,比较奇怪,这是因为实时进程描述符的rt_priority成员中事先存放了它自己的优先级(数字也是0-99,但在这里数字越大,优先级越高),因此往p->prio中倒换的时候,需要处理一下,MAX_RT_PRIO值为100,因此MAX_RT_PRIO-1-(0,99)就倒换成了(99,0),这仅仅是个小技巧。如果当前进程也不是实时进程(说明是普通进程喽),则第10行将进程的静态优先级存入prio中,然后返回(也就是说普通进程的普通优先级等于其静态优先级)。

总结下,总共有三种进程:空闲进程,实时进程,普通进程;每种进程都包含三种优先级:活动优先级,普通优先级,静态优先级。空闲进程的普通优先级永远-1,实时进程的普通优先级是根据p->rt_priority设定的(0-99),普通进程的普通优先级是根据其静态优先级设定的(100-139)。

3.进程权重设置的函数,上边我们提到,进程的优先级决定进程的权重。权重进而决定进程运行时间的长短。我们先分析和权重相关的数据结构。

struct load_weight(include/linux/sched.h)

1 struct load_weight {
2     unsigned long weight;
3     u32 inv_weight;
4 };

每个进程描述符,调度实体,就绪对列中都包含一个该类型变量,用来保存各自的权重。成员weight中存放进程优先级所对应的权重。成员inv_weight中存放NICE_0_LOAD/weight的结果,这个结果乘以进程运行的时间间隔delta_exec就是进程运行的虚拟时间。因此引入权重就是为了计算进程的虚拟时间。在这里将中间的计算结果保存下来,后边就不用再计算了,直接可以用。

数组prio_to_weight[40](kernel/sched/sched.h)

 1 static const int prio_to_weight[40] = {
 2  /* -20 */     88761,     71755,     56483,     46273,     36291,
 3  /* -15 */     29154,     23254,     18705,     14949,     11916,
 4  /* -10 */      9548,      7620,      6100,      4904,      3906,
 5  /*  -5 */      3121,      2501,      1991,      1586,      1277,
 6  /*   0 */      1024,       820,       655,       526,       423,
 7  /*   5 */       335,       272,       215,       172,       137,
 8  /*  10 */       110,        87,        70,        56,        45,
 9  /*  15 */        36,        29,        23,        18,        15,
10 };

该数组是普通进程的优先级和权重对应关系。数组元素是权重值,分别是优先级从100-139或者nice值从-20-+19所对应的权重值。nice值(-20-+19)是从用户空间看到的普通进程的优先级,和内核空间的优先级(100-139)一一对应。struct load_weight中的weight成员存放正是这些权重值。

中间结果数组prio_to_wmult[40] (kernel/sched/sched.h)

 1 static const u32 prio_to_wmult[40] = {
 2  /* -20 */     48388,     59856,     76040,     92818,    118348,
 3  /* -15 */    147320,    184698,    229616,    287308,    360437,
 4  /* -10 */    449829,    563644,    704093,    875809,   1099582,
 5  /*  -5 */   1376151,   1717300,   2157191,   2708050,   3363326,
 6  /*   0 */   4194304,   5237765,   6557202,   8165337,  10153587,
 7  /*   5 */  12820798,  15790321,  19976592,  24970740,  31350126,
 8  /*  10 */  39045157,  49367440,  61356676,  76695844,  95443717,
 9  /*  15 */ 119304647, 148102320, 186737708, 238609294, 286331153,
10 };

该数组元素就是上个数组元素被NICE_0_LOAD除的结果,一一对应。struct load_weight中的inv_weight成员存放正是这些值。

下边我们分析和权重设置相关的函数。从set_load_weight函数开始(kernel/sched/core.c):

 1 static void set_load_weight(struct task_struct *p)
 2 {
 3     int prio = p->static_prio - MAX_RT_PRIO;
 4     struct load_weight *load = &p->se.load;
 5 
 6     /*
 7      * SCHED_IDLE tasks get minimal weight:
 8      */
 9     if (p->policy == SCHED_IDLE) {
10         load->weight = scale_load(WEIGHT_IDLEPRIO);
11         load->inv_weight = WMULT_IDLEPRIO;
12         return;
13     }
14 
15     load->weight = scale_load(prio_to_weight[prio]);
16     load->inv_weight = prio_to_wmult[prio];
17 } 

该函数用来设置进程p的权重。第3行将进程p的静态优先级转换成数组下标(减去100,从100-139--->0-39)。第4行获取当前进程的调度实体中的权重结构体指针,存入load中。第9-12行,如果当前进程是空闲进程,则设置相应的权重和中间计算结果。第15-16行,设置实时进程和普通进程的权重和中间计算结果。

由于就绪队列中也包含权重结构体,所以也要对它们进行设置。使用以下函数(kernel/sched/fair.c):

1 static inline void update_load_set(struct load_weight *lw, unsigned long w)
2 {
3     lw->weight = w;
4     lw->inv_weight = 0;
5 }

该函数用来设置就绪队列的权重。

1 static inline void update_load_add(struct load_weight *lw, unsigned long inc)
2 {
3     lw->weight += inc;
4     lw->inv_weight = 0;
5 }

当有进程加入就绪队列,使用该函数增加就绪队列的权重。

1 static inline void update_load_sub(struct load_weight *lw, unsigned long dec)
2 {
3     lw->weight -= dec;
4     lw->inv_weight = 0;
5 }

当有进程从就绪队列移除时,使用该函数减少就绪队列的权重。就绪队列的load_weight.inv_weight成员总是0,因为不会使用到就绪队列的该域。

4.计算进程延迟周期的相关函数。进程的延迟周期指的是将所有进程执行一遍的时间。当就绪队列中的进程数量不超出规定的时候,内核有一个固定的延迟周期供调度使用,但是当进程数量超出规定以后,就需要对该固定延迟周期进行扩展(不然随着进程越多,每个进程分配的执行时间会越少)。下面看看sched_slice函数(kernel/sched/fair.c):

 1 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
 2 {
 3     u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);
 4 
 5     for_each_sched_entity(se) {
 6         struct load_weight *load;
 7         struct load_weight lw;
 8 
 9         cfs_rq = cfs_rq_of(se);
10         load = &cfs_rq->load;
11 
12         if (unlikely(!se->on_rq)) {
13             lw = cfs_rq->load;
14 
15             update_load_add(&lw, se->load.weight);
16             load = &lw;
17         }
18         slice = __calc_delta(slice, se->load.weight, load);
19     }
20     return slice;
21 }

直接看第18行,__calc_delta用来计算当前进程在延迟周期中可占的时间(相当于“时间片”,就是当前进程可用的时间)。__calc_delta函数很强大,记得前边在entity_tick函数中也调用过该函数(entity_tick--->update_curr--->calc_delta_fair--->__calc_delta),当时使用该函数是为了将进程运行过的物理时间(真实时间)转换成虚拟时间;而在此处,我们用它来计算当前进程在延迟周期中可占的时间(相当于“时间片”)。前边提过,__calc_delta中用到param1 * param2 / param3.weight这个公式(param代表该函数接收的参数),当param2的值固定不变(等于NICE_0_LOAD),param3(代表当前进程的权重)在变化时,该函数是用来转换真实时间和虚拟时间的;当param3(代表当前cfs_rq的权重,cfs_rq->load->weight)的值固定不变,param2在变化(代表当前进程的权重)时,该函数则是用来计算当前进程应该运行的时间。因此第18行计算结果slice就是当前进程应该运行的真实时间。下面再看一个函数sched_vslice(kernel/sched/fair.c):

1 static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
2 {
3     return calc_delta_fair(sched_slice(cfs_rq, se), se);
4 }

该函数用来将进程应该运行的真实时间转换成应该运行的虚拟时间,以供调度使用。可以看到该函数调用了cals_delta_fair来进行时间转换,前边已分析过,不再赘述。

5.选择下一个需要调度的进程。所使用的函数是pick_next_task_fair,代码如下(kernel/sched/fair.c):

图片 11图片 12

  1 static struct task_struct *
  2 pick_next_task_fair(struct rq *rq, struct task_struct *prev)
  3 {
  4     struct cfs_rq *cfs_rq = &rq->cfs;
  5     struct sched_entity *se;
  6     struct task_struct *p;
  7     int new_tasks;
  8 
  9 again:
 10 #ifdef CONFIG_FAIR_GROUP_SCHED
 11     if (!cfs_rq->nr_running)
 12         goto idle;
 13 
 14     if (prev->sched_class != &fair_sched_class)
 15         goto simple;
 16 
 17     /*
 18      * Because of the set_next_buddy() in dequeue_task_fair() it is rather
 19      * likely that a next task is from the same cgroup as the current.
 20      *
 21      * Therefore attempt to avoid putting and setting the entire cgroup
 22      * hierarchy, only change the part that actually changes.
 23      */
 24 
 25     do {
 26         struct sched_entity *curr = cfs_rq->curr;
 27 
 28         /*
 29          * Since we got here without doing put_prev_entity() we also
 30          * have to consider cfs_rq->curr. If it is still a runnable
 31          * entity, update_curr() will update its vruntime, otherwise
 32          * forget we've ever seen it.
 33          */
 34         if (curr && curr->on_rq)
 35             update_curr(cfs_rq);
 36         else
 37             curr = NULL;
 38 
 39         /*
 40          * This call to check_cfs_rq_runtime() will do the throttle and
 41          * dequeue its entity in the parent(s). Therefore the 'simple'
 42          * nr_running test will indeed be correct.
 43          */
 44         if (unlikely(check_cfs_rq_runtime(cfs_rq)))
 45             goto simple;
 46 
 47         se = pick_next_entity(cfs_rq, curr);
 48         cfs_rq = group_cfs_rq(se);
 49     } while (cfs_rq);
 50 
 51     p = task_of(se);
 52 
 53     /*
 54      * Since we haven't yet done put_prev_entity and if the selected task
 55      * is a different task than we started out with, try and touch the
 56      * least amount of cfs_rqs.
 57      */
 58     if (prev != p) {
 59         struct sched_entity *pse = &prev->se;
 60 
 61         while (!(cfs_rq = is_same_group(se, pse))) {
 62             int se_depth = se->depth;
 63             int pse_depth = pse->depth;
 64 
 65             if (se_depth <= pse_depth) {
 66                 put_prev_entity(cfs_rq_of(pse), pse);
 67                 pse = parent_entity(pse);
 68             }
 69             if (se_depth >= pse_depth) {
 70                 set_next_entity(cfs_rq_of(se), se);
 71                 se = parent_entity(se);
 72             }
 73         }
 74 
 75         put_prev_entity(cfs_rq, pse);
 76         set_next_entity(cfs_rq, se);
 77     }
 78 
 79     if (hrtick_enabled(rq))
 80         hrtick_start_fair(rq, p);
 81 
 82     return p;
 83 simple:
 84     cfs_rq = &rq->cfs;
 85 #endif
 86 
 87     if (!cfs_rq->nr_running)
 88         goto idle;
 89 
 90     put_prev_task(rq, prev);
 91 
 92     do {
 93         se = pick_next_entity(cfs_rq, NULL);
 94         set_next_entity(cfs_rq, se);
 95         cfs_rq = group_cfs_rq(se);
 96     } while (cfs_rq);
 97 
 98     p = task_of(se);
 99 
100     if (hrtick_enabled(rq))
101         hrtick_start_fair(rq, p);
102 
103     return p;
104 
105 idle:
106     new_tasks = idle_balance(rq);
107     /*
108      * Because idle_balance() releases (and re-acquires) rq->lock, it is
109      * possible for any higher priority task to appear. In that case we
110      * must re-start the pick_next_entity() loop.
111      */
112     if (new_tasks < 0)
113         return RETRY_TASK;
114 
115     if (new_tasks > 0)
116         goto again;
117 
118     return NULL;
119 }

pick_next_task_fair

该函数会被赋给公平调度类的pick_next_task成员(.pick_next_task = pick_next_task_fair),在schedule函数中会调用该函数选择下一个需要调用的进程,然后进行进程切换。第11-12行如果当前就绪队列中的进程数量为0,则退出函数。第25-49行对所有的调度组进行遍历,从中选择下一个可调度的进程,而不只局限在当前队列的当前组。第26行获取当前调度实体,第34-37行如果存在一个当前调度实体(进程)并且正在运行,则更新进程的运行时间,否则就绪队列cfs_rq.curr置为null,表示当前无进程运行。第47行获取下一个调度实体,待会来分析该函数。第48行获取下个调度实体所拥有的就绪队列my_q(代表一个调度组),如果调度组非空,则进入下一次循环,在新的就绪队列(调度组)中挑选下一个可调度进程,直到某个实体没有自己的就绪队列为止(遍历完所有的调度组了)。退出循环后,可以发现此时的se是所遍历的最后一个调度组的下个可运行实体。第51行获取se对应的进程描述符,第58-77行,如果当前进程和下一个进程(se所对应的进程)不是同一个的话,则执行if体,第59行将当前进程的调度实体指针装入pse中,第61-72行如果当前进程和下一个调度的进程(se对应的进程)不属于同一调度组,则进入循环。否则,执行第75-76行,将当前进程放回就绪队列,将下个进程从就绪队列中拿出,这两个函数涉及到了就绪队列的出队和入队操作,我们在下边分析。第61-73的循环根据当前实体和下个调度实体的节点深度进行调整(同一个级别的进程才能切换)。下面看看pick_next_entity,put_prev_entity和set_prev_entity函数代码(kernel/sched/fair.c):

 1 static struct sched_entity *
 2 pick_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *curr)
 3 {
 4     struct sched_entity *left = __pick_first_entity(cfs_rq);
 5     struct sched_entity *se;
 6 
 7     /*
 8      * If curr is set we have to see if its left of the leftmost entity
 9      * still in the tree, provided there was anything in the tree at all.
10      */
11     if (!left || (curr && entity_before(curr, left)))
12         left = curr;
13 
14     se = left; /* ideally we run the leftmost entity */
15 
16     /*
17      * Avoid running the skip buddy, if running something else can
18      * be done without getting too unfair.
19      */
20     if (cfs_rq->skip == se) {
21         struct sched_entity *second;
22 
23         if (se == curr) {
24             second = __pick_first_entity(cfs_rq);
25         } else {
26             second = __pick_next_entity(se);
27             if (!second || (curr && entity_before(curr, second)))
28                 second = curr;
29         }
30 
31         if (second && wakeup_preempt_entity(second, left) < 1)
32             se = second;
33     }
34 
35     /*
36      * Prefer last buddy, try to return the CPU to a preempted task.
37      */
38     if (cfs_rq->last && wakeup_preempt_entity(cfs_rq->last, left) < 1)
39         se = cfs_rq->last;
40 
41     /*
42      * Someone really wants this to run. If it's not unfair, run it.
43      */
44     if (cfs_rq->next && wakeup_preempt_entity(cfs_rq->next, left) < 1)
45         se = cfs_rq->next;
46 
47     clear_buddies(cfs_rq, se);
48 
49     return se;
50 }

该函数选择下一个调度的实体。第4行将红黑树的最左边实体赋给left,第11-12行如果红黑树的最左边实体为空或者当前实体运行的虚拟时间小于下一个实体(继续当前的实体),把当前实体赋给left,实际上left指向的是下一个要执行的进程(该进程要么还是当前进程,要么是下一个进程),第14行将left赋给se,第20-33行如果se进程是需要跳过的进程(不能被调度),执行if体,如果se进程是当前进程,则选择红黑数最左的进程赋给second,否则se进程已经是最左的进程,就把next指向的进程赋给second(next指向的是刚刚被唤醒的进程),第32行将second再次赋给se,se是挑选出来的下个进程。第38-45,再次判断,要么把last指向的进程赋给se,要么把next指向进程赋给se,内核更倾向于把last赋给se,因为last是唤醒next进程的进程(一般就是当前进程),所以执行last就意味着不用切换进程,效率最高。第47行清理掉next和last域。第31,38,44行使用到的wakeup_preempt_entity函数我们在进程唤醒那块再分析。

 1 static void put_prev_entity(struct cfs_rq *cfs_rq, struct sched_entity *prev)
 2 {
 3     /*
 4      * If still on the runqueue then deactivate_task()
 5      * was not called and update_curr() has to be done:
 6      */
 7     if (prev->on_rq)
 8         update_curr(cfs_rq);
 9 
10     /* throttle cfs_rqs exceeding runtime */
11     check_cfs_rq_runtime(cfs_rq);
12 
13     check_spread(cfs_rq, prev);
14     if (prev->on_rq) {
15         update_stats_wait_start(cfs_rq, prev);
16         /* Put 'current' back into the tree. */
17         __enqueue_entity(cfs_rq, prev);
18         /* in !on_rq case, update occurred at dequeue */
19         update_entity_load_avg(prev, 1);
20     }
21     cfs_rq->curr = NULL;
22 } 

该函数将当前调度实体放回就绪队列。第7-8行如果当前实体正在运行,更新其时间片。第17行将当前实体加入到就绪队列中,待会分析__enqueue_entity函数。第21行将就绪队列的curr域置为null,因为当前进程已经放回就绪队列了,就表示当前没有进程正在执行了,因此curr为空。

 1 static void
 2 set_next_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 3 {
 4     /* 'current' is not kept within the tree. */
 5     if (se->on_rq) {
 6         /*
 7          * Any task has to be enqueued before it get to execute on
 8          * a CPU. So account for the time it spent waiting on the
 9          * runqueue.
10          */
11         update_stats_wait_end(cfs_rq, se);
12         __dequeue_entity(cfs_rq, se);
13     }
14 
15     update_stats_curr_start(cfs_rq, se);
16     cfs_rq->curr = se;
17 #ifdef CONFIG_SCHEDSTATS
18     /*
19      * Track our maximum slice length, if the CPU's load is at
20      * least twice that of our own weight (i.e. dont track it
21      * when there are only lesser-weight tasks around):
22      */
23     if (rq_of(cfs_rq)->load.weight >= 2*se->load.weight) {
24         se->statistics.slice_max = max(se->statistics.slice_max,
25             se->sum_exec_runtime - se->prev_sum_exec_runtime);
26     }
27 #endif
28     se->prev_sum_exec_runtime = se->sum_exec_runtime;
29 }

该函数将下一个被调度实体从就绪队列中取出。第12行实现取出操作,待会分析该函数。第16行将取出的调度实体指针赋给就绪队列的curr,那么此时就有了正在运行的进程了。后边的代码更新当前进程的时间统计信息。

6.就绪队列的入队和出队操作(kernel/sched/fair.c)。

 1 static void __enqueue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 2 {
 3     struct rb_node **link = &cfs_rq->tasks_timeline.rb_node;
 4     struct rb_node *parent = NULL;
 5     struct sched_entity *entry;
 6     int leftmost = 1;
 7 
 8     /*
 9      * Find the right place in the rbtree:
10      */
11     while (*link) {
12         parent = *link;
13         entry = rb_entry(parent, struct sched_entity, run_node);
14         /*
15          * We dont care about collisions. Nodes with
16          * the same key stay together.
17          */
18         if (entity_before(se, entry)) {
19             link = &parent->rb_left;
20         } else {
21             link = &parent->rb_right;
22             leftmost = 0;
23         }
24     }
25 
26     /*
27      * Maintain a cache of leftmost tree entries (it is frequently
28      * used):
29      */
30     if (leftmost)
31         cfs_rq->rb_leftmost = &se->run_node;
32 
33     rb_link_node(&se->run_node, parent, link);
34     rb_insert_color(&se->run_node, &cfs_rq->tasks_timeline);
35 }

该函数实现入队操作。第3行获取就绪队列中红黑树的根节点,将树根指针保存在link中。第12行parent暂时指向树根。第13行获得树根节点的调度实体,保存在entry中。第18-22行,比较要入队的实体中的已运行虚拟时间和树根实体中的该信息,如果前者小的话,就要插入到树的左子树上(link指向树根的左孩子,再次进入循环,类似于递归),否则就要插入到树的右子树上(同上)。这块就将进程的调度策略展现的淋漓尽致:根据进程已运行的虚拟时间来决定进程的调度,红黑树的左子树比右子树要先被调度,已运行的虚拟时间越小的进程越在树的左侧。第30-31行,如果入队的实体最终被插在左孩子上(该入队实体仍是就绪队列上最靠前的实体,下次就会被调用),那么就要让就绪队列的rb_leftmost指向入队实体。rb_leftmost指针始终指向下次要被调度的实体(进程)。最后两行要给红黑数重新着色。

 1 static void __dequeue_entity(struct cfs_rq *cfs_rq, struct sched_entity *se)
 2 {
 3     if (cfs_rq->rb_leftmost == &se->run_node) {
 4         struct rb_node *next_node;
 5 
 6         next_node = rb_next(&se->run_node);
 7         cfs_rq->rb_leftmost = next_node;
 8     }
 9 
10     rb_erase(&se->run_node, &cfs_rq->tasks_timeline);
11 }

该函数实现出队操作。第3行判断要出队的实体是不是红黑树最左侧的孩子(rb_leftmost所指向的),如果不是的话,第10行直接删除该出队实体。否则执行if体,第6行找到出队实体的下一个实体(中序遍历的下一个节点,也就是当出队实体删除后,最左边的孩子),赋给next_node。第7行让rb_leftmost指向next_node。在删除掉要出队实体后,下一个需要被调度的实体也就设置好了。

7.睡眠进程被唤醒后抢占当前进程。当某个资源空出来后,等待该资源的进程就会被唤醒,唤醒后也许就要抢占当前进程,因此这块的函数也需要分析(kernel/sched/core.c)。

 1 static int
 2 try_to_wake_up(struct task_struct *p, unsigned int state, int wake_flags)
 3 {
 4     unsigned long flags;
 5     int cpu, success = 0;
 6 
 7     /*
 8      * If we are going to wake up a thread waiting for CONDITION we
 9      * need to ensure that CONDITION=1 done by the caller can not be
10      * reordered with p->state check below. This pairs with mb() in
11      * set_current_state() the waiting thread does.
12      */
13     smp_mb__before_spinlock();
14     raw_spin_lock_irqsave(&p->pi_lock, flags);
15     if (!(p->state & state))
16         goto out;
17 
18     success = 1; /* we're going to change ->state */
19     cpu = task_cpu(p);
20 
21     if (p->on_rq && ttwu_remote(p, wake_flags))
22         goto stat;
23 
24 #ifdef CONFIG_SMP
25     /*
26      * If the owning (remote) cpu is still in the middle of schedule() with
27      * this task as prev, wait until its done referencing the task.
28      */
29     while (p->on_cpu)
30         cpu_relax();
31     /*
32      * Pairs with the smp_wmb() in finish_lock_switch().
33      */
34     smp_rmb();
35 
36     p->sched_contributes_to_load = !!task_contributes_to_load(p);
37     p->state = TASK_WAKING;
38 
39     if (p->sched_class->task_waking)
40         p->sched_class->task_waking(p);
41 
42     cpu = select_task_rq(p, p->wake_cpu, SD_BALANCE_WAKE, wake_flags);
43     if (task_cpu(p) != cpu) {
44         wake_flags |= WF_MIGRATED;
45         set_task_cpu(p, cpu);
46     }
47 #endif /* CONFIG_SMP */
48 
49     ttwu_queue(p, cpu);
50 stat:
51     ttwu_stat(p, cpu, wake_flags);
52 out:
53     raw_spin_unlock_irqrestore(&p->pi_lock, flags);
54 
55     return success;
56 }

该函数会唤醒参数p指定的进程,将进程加入就绪队列中等待调度。第15行判断p进程的状态码和传进来的状态码是否一致,不一致的话函数结束(不一致则说明进程等待的条件未满足)。第19行获取要唤醒进程p原先所在的cpu号。第37行设置要唤醒进程p的状态为TASK_WAKING。第40行执行进程p的调度类中的task_waking函数,该函数指针指向了task_waking_fair函数,该函数主要是对睡眠进程的已运行虚拟时间进行补偿,待会分析该函数。第42行为刚唤醒进程p选择一个合适的就绪队列供其加入,返回就绪队列所在的cpu号。第43行如果进程p所在的原先cpu和为它挑选的cpu不是同一个的话,第45行更改进程p的cpu号。

 1 void wake_up_new_task(struct task_struct *p)
 2 {
 3     unsigned long flags;
 4     struct rq *rq;
 5 
 6     raw_spin_lock_irqsave(&p->pi_lock, flags);
 7 #ifdef CONFIG_SMP
 8     /*
 9      * Fork balancing, do it here and not earlier because:
10      *  - cpus_allowed can change in the fork path
11      *  - any previously selected cpu might disappear through hotplug
12      */
13     set_task_cpu(p, select_task_rq(p, task_cpu(p), SD_BALANCE_FORK, 0));
14 #endif
15 
16     /* Initialize new task's runnable average */
17     init_task_runnable_average(p);
18     rq = __task_rq_lock(p);
19     activate_task(rq, p, 0);
20     p->on_rq = 1;
21     trace_sched_wakeup_new(p, true);
22     check_preempt_curr(rq, p, WF_FORK);
23 #ifdef CONFIG_SMP
24     if (p->sched_class->task_woken)
25         p->sched_class->task_woken(rq, p);
26 #endif
27     task_rq_unlock(rq, p, &flags);
28 }

 该函数用来唤醒刚创建好的进程,而上个函数是用来唤醒睡眠中的进程。第13行为将唤醒的进程p设置合适的cpu。第17行设置进程p的可运行时间长度(类似“时间片”),第19行activate_task函数主要将唤醒的进程p加入就绪队列,并更新队列的时间,初始化进程p的时间等,该函数中的调用关系大致为activate_task->enqueue_task->enqueue_task_fair(p->sched_class->enqueue_task)->enqueue_entity。第22行check_preempt_curr函数调用了check_preempt_wakeup函数,来检查唤醒进程是否能抢占当前进程,下面分析该函数(kernel/sched/fair.c)。

 1 static void check_preempt_wakeup(struct rq *rq, struct task_struct *p, int wake_flags)
 2 {
 3     struct task_struct *curr = rq->curr;
 4     struct sched_entity *se = &curr->se, *pse = &p->se;
 5     struct cfs_rq *cfs_rq = task_cfs_rq(curr);
 6     int scale = cfs_rq->nr_running >= sched_nr_latency;
 7     int next_buddy_marked = 0;
 8 
 9     if (unlikely(se == pse))
10         return;
11 
12     /*
13      * This is possible from callers such as move_task(), in which we
14      * unconditionally check_prempt_curr() after an enqueue (which may have
15      * lead to a throttle).  This both saves work and prevents false
16      * next-buddy nomination below.
17      */
18     if (unlikely(throttled_hierarchy(cfs_rq_of(pse))))
19         return;
20 
21     if (sched_feat(NEXT_BUDDY) && scale && !(wake_flags & WF_FORK)) {
22         set_next_buddy(pse);
23         next_buddy_marked = 1;
24     }
25 
26     /*
27      * We can come here with TIF_NEED_RESCHED already set from new task
28      * wake up path.
29      *
30      * Note: this also catches the edge-case of curr being in a throttled
31      * group (e.g. via set_curr_task), since update_curr() (in the
32      * enqueue of curr) will have resulted in resched being set.  This
33      * prevents us from potentially nominating it as a false LAST_BUDDY
34      * below.
35      */
36     if (test_tsk_need_resched(curr))
37         return;
38 
39     /* Idle tasks are by definition preempted by non-idle tasks. */
40     if (unlikely(curr->policy == SCHED_IDLE) &&
41         likely(p->policy != SCHED_IDLE))
42         goto preempt;
43 
44     /*
45      *  do not preempt non-idle tasks (their preemption
46      * is driven by the tick):
47      */
48     if (unlikely(p->policy != SCHED_NORMAL) || !sched_feat(WAKEUP_PREEMPTION))
49         return;
50 
51     find_matching_se(&se, &pse);
52     update_curr(cfs_rq_of(se));
53     BUG_ON(!pse);
54     if (wakeup_preempt_entity(se, pse) == 1) {
55         /*
56          * Bias pick_next to pick the sched entity that is
57          * triggering this preemption.
58          */
59         if (!next_buddy_marked)
60             set_next_buddy(pse);
61         goto preempt;
62     }
63 
64     return;
65 
66 preempt:
67     resched_task(curr);
68     /*
69      * Only set the backward buddy when the current task is still
70      * on the rq. This can happen when a wakeup gets interleaved
71      * with schedule on the ->pre_schedule() or idle_balance()
72      * point, either of which can * drop the rq lock.
73      *
74      * Also, during early boot the idle thread is in the fair class,
75      * for obvious reasons its a bad idea to schedule back to it.
76      */
77     if (unlikely(!se->on_rq || curr == rq->idle))
78         return;
79 
80     if (sched_feat(LAST_BUDDY) && scale && entity_is_task(se))
81         set_last_buddy(se);
82 }

第21-24行,如果开启了NEXT_BUDDY并且唤醒的进程不是新进程(而是睡眠进程),那么第22行就将cfs_rq的next指针指向唤醒的进程,并且设置标记。第36行如果当前进程可以被抢占,函数直接返回。否则,第40-42行如果当前进程是空闲进程并且被唤醒的进程不是空闲进程,则跳到preempt处,设置need_resched标志,完成抢占设置。第48行,如果被唤醒进程是空闲进程或者批处理进程,直接返回,这些进程不能抢占别的进程。第51行如果当前进程和被唤醒进程不在同一级别(同一个调度组),则寻找它们的祖先parent,把它们调整到同一级别,才能进行虚拟运行时间的比较,进而决定能否抢占。第54行,对当前进程和被唤醒进程的虚拟运行时间进行比较,可以抢占的话(唤醒进程的虚拟时间小于当前进程)执行if体,跳到preempt处完成抢占。否则所有都不满足的话,当前进程不能被抢占,执行第64行返回,随后分析该函数。第80-81行如果开启了LAST_BUDDY,就将cfs_rq的last指针指向唤醒进程的进程。在pick_next_entity函数中,next和last所指的进程会先于就绪队列的left进程被选择。下面分析下wakeup_preempt_entity函数(kernel/sched/fair.c)。

 1 static int
 2 wakeup_preempt_entity(struct sched_entity *curr, struct sched_entity *se)
 3 {
 4     s64 gran, vdiff = curr->vruntime - se->vruntime;
 5 
 6     if (vdiff <= 0)
 7         return -1;
 8 
 9     gran = wakeup_gran(curr, se);
10     if (vdiff > gran)
11         return 1;
12 
13     return 0;
14 }

该函数是要保证在se实体在抢占curr实体时,curr实体已经运行过一段时间(具体而言,物理时间1ms),第9行wakeup_gran函数是将sysctl_sched_wakeup_granularity的值(1ms)转换成se实体的虚拟时间,保存在gran中,第10行比较vdiff和gran大小,实际上是比较curr->vruntime 和 se->vruntime+gran,因此就是想让curr实体多执行gran时间,才能被抢占。

最后我们再分析下 try_to_wake_up函数中第40行遗留的那个函数指针task_waking,该指针指向了task_waking_fair函数,代码如下(kernel/sched/fair.c):

 1 static void task_waking_fair(struct task_struct *p)
 2 {
 3     struct sched_entity *se = &p->se;
 4     struct cfs_rq *cfs_rq = cfs_rq_of(se);
 5     u64 min_vruntime;
 6 
 7 #ifndef CONFIG_64BIT
 8     u64 min_vruntime_copy;
 9 
10     do {
11         min_vruntime_copy = cfs_rq->min_vruntime_copy;
12         smp_rmb();
13         min_vruntime = cfs_rq->min_vruntime;
14     } while (min_vruntime != min_vruntime_copy);
15 #else
16     min_vruntime = cfs_rq->min_vruntime;
17 #endif
18 
19     se->vruntime -= min_vruntime;
20     record_wakee(p);
21 }

该函数完成对睡眠进程的虚拟时间补偿。考虑到睡眠时间长时间没有运行,因此第19行从唤醒进程se的已运行虚拟时间中减去就绪队列的最小虚拟时间,做点补偿,让其可以多运行一点时间。

8.新进程的处理函数(kernel/sched/fair.c):

 1 static void task_fork_fair(struct task_struct *p)
 2 {
 3     struct cfs_rq *cfs_rq;
 4     struct sched_entity *se = &p->se, *curr;
 5     int this_cpu = smp_processor_id();
 6     struct rq *rq = this_rq();
 7     unsigned long flags;
 8 
 9     raw_spin_lock_irqsave(&rq->lock, flags);
10 
11     update_rq_clock(rq);
12 
13     cfs_rq = task_cfs_rq(current);
14     curr = cfs_rq->curr;
15 
16     /*
17      * Not only the cpu but also the task_group of the parent might have
18      * been changed after parent->se.parent,cfs_rq were copied to
19      * child->se.parent,cfs_rq. So call __set_task_cpu() to make those
20      * of child point to valid ones.
21      */
22     rcu_read_lock();
23     __set_task_cpu(p, this_cpu);
24     rcu_read_unlock();
25 
26     update_curr(cfs_rq);
27 
28     if (curr)
29         se->vruntime = curr->vruntime;
30     place_entity(cfs_rq, se, 1);
31 
32     if (sysctl_sched_child_runs_first && curr && entity_before(curr, se)) {
33         /*
34          * Upon rescheduling, sched_class::put_prev_task() will place
35          * 'current' within the tree based on its new key value.
36          */
37         swap(curr->vruntime, se->vruntime);
38         resched_task(rq->curr);
39     }
40 
41     se->vruntime -= cfs_rq->min_vruntime;
42 
43     raw_spin_unlock_irqrestore(&rq->lock, flags);
44 }

该函数在do_fork--->copy_process函数中调用,用来设置新创建进程的虚拟时间信息。第5行获取当前的cpu号,第23行为新进程设置该cpu号。第29行将当前进程(父进程)的虚拟运行时间拷贝给新进程(子进程)。第30行的place_entity函数完成新进程的“时间片”计算以及虚拟时间惩罚,之后将新进程加入红黑数中,待会分析。第32行如果设置了子进程先于父进程运行的标志并且当前进程不为空且当前进程已运行的虚拟时间比新进程小,则执行if体,第37行交换当前进程和新进程的虚拟时间(新进程的虚拟时间变小,就排在了红黑树的左侧,当前进程之前,下次就能被调度),第38行设置重新调度标志。第41行给新进程的虚拟运行时间减去队列的最小虚拟时间来做一点补偿(因为在上边的place_entity函数中给新进程的虚拟时间加了一次min_vruntime,所以在这里要减去),再来看看place_entity函数(kernel/sched/fair.c):

 1 static void
 2 place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
 3 {
 4     u64 vruntime = cfs_rq->min_vruntime;
 5 
 6     /*
 7      * The 'current' period is already promised to the current tasks,
 8      * however the extra weight of the new task will slow them down a
 9      * little, place the new task so that it fits in the slot that
10      * stays open at the end.
11      */
12     if (initial && sched_feat(START_DEBIT))
13         vruntime += sched_vslice(cfs_rq, se);
14 
15     /* sleeps up to a single latency don't count. */
16     if (!initial) {
17         unsigned long thresh = sysctl_sched_latency;
18 
19         /*
20          * Halve their sleep time's effect, to allow
21          * for a gentler effect of sleepers:
22          */
23         if (sched_feat(GENTLE_FAIR_SLEEPERS))
24             thresh >>= 1;
25 
26         vruntime -= thresh;
27     }
28 
29     /* ensure we never gain time by being placed backwards. */
30     se->vruntime = max_vruntime(se->vruntime, vruntime);
31 }

该函数完成新进程的“时间片”计算和虚拟时间惩罚,并且将新进程加入就绪队列。第4行将就绪队列的min_vruntime值存入vruntime中,第12-13行,如果initial标志为1的话(说明当前计算的是新进程的时间),将计算出的新进程的虚拟时间片累加到vruntime中,累加到原因是调度系统要保证先把就绪队列中的所有的进程执行一遍之后才能执行新进程,一会具体解释。第16-17行,如果当前计算的不是新进程(睡眠的进程),把一个延迟周期的长度sysctl_sched_latency(6ms)赋给thresh,第24行thresh减半,第26行睡眠进程的虚拟运行时间减去减半后的thresh,因为睡眠进程好长时间未运行,因此要进行虚拟时间补偿,把它已运行的虚拟时间减小一点,使得它能多运行一会。第30行将设置好的虚拟时间保存到进程调度实体的vruntime域。下面解释下为什么要对新进程进行虚拟时间惩罚,其实原因只有一个,就是调度系统要保证将就绪队列中现有的进程执行一遍之后再执行新进程,那么就必须使新进程的 vruntime=cfs_rq->min_vruntime+新进程的虚拟时间片,才能使得新进程插入到红黑树的右边,最后参与调度,不然无法保证所有进程在新进程之前执行。

最后,分析下和调度相关的这些函数执行的时机

前面在介绍这些函数的时候,基本上都提到了会在哪里调用这些函数,最后,我们再系统总结一下:

进程调度分为两个部分:一是进程信息的修改,二是进程切换。进程切换只有一个函数schedule,schedule的运行时机我们最后分析。其它函数的运行时机如下:

1.scheduler_tick函数是在每个时钟中断中被调用,用来更新当前进程运行的时间。

2.effective_prio函数是在创建一个新进程或者用户使用nice系统调用设置进程的优先级时调用,用来设置进程的在内核中优先级(不同于nice值)。

3.set_load_weight函数也是在创建新进程或者用户使用nice()设置进程的优先级时调用,用来设置进程的权重。该函数和2中的函数其实是配套使用的,当设置或者改变了一个进程的优先级时,要么就要为这个进程设置或者改变该优先级对应的权重。

4.sched_slice函数主要是在scheduler_tick->...->check_preempt_tick中调用(别的地方也有),因此也是每个时钟周期调用一次,用来计算当前进程应该执行的“时间片”,进而才能判断进程是否已经超出它的时间片,超出的话就要设置抢占标志,切换别的进程。

5.pick_next_task_fair函数schedule中调用,用来选择下一个要被调度的进程,然后才能切换进程。它的执行时机就是schedule的执行时机,随后分析。

6.__enqueue_entity/__dequeue_entity函数是在需要入就绪队列或者出就绪队列的地方被调用,因此使用它们的地方较多,比如schedule中调用(间接调用),就不一一分析了。

7.try_to_wake_up/wake_up_new_task函数,前者在进程所等待的资源满足时被调用(一般在中断内调用);后者是在创建好新进程后被调用。都是用来唤醒进程的,前者唤醒睡眠进程,后者唤醒新进程并将进程加入就绪队列。

8.task_fork_fair函数也是在新进程被创建好后调用,用来设置新进程的“时间片”等信息,设置好以后新进程就可以被唤醒了。所以该函数和wake_up_new_task函数调用时机是一样的。

最后,我们分析schedule函数的调用时机。该函数是唯一实现进程切换的函数。

在分析schedule函数的调用时机之前,我们先为大家介绍下“内核控制路径“的概念。所谓内核控制路径,就是由中断或者异常引出的执行路径,说白了,执行中断或者异常处理程序时就处在内核控制路径中,此时代表的也是当前进程。内核控制路径可以嵌套(也就是可以嵌套中断),但是无论嵌套多少,最终都要回到当前进程中,也就是说要从内核控制路径中返回,不可以在内核控制路径中进行进程切换(因此中断处理程序中不允许调用能引起进程睡眠的函数)。说到底,内核要么处在进程中,要么处在内核控制路径中(其实内核控制路径也代表当前进程,因为其有特殊性,所以我们单列出来谈),不会再有别的什么路径了。那么进程切换的时机,或者说schedule函数被调用的时机,也就只可能发生于上述两种路径中。那么,1.当在进程中调用schedule函数时(就是ULK这本书上说的直接调用),表明当前进程因为等待资源或者别的原因需要挂起,主动放弃使用cpu,调用schedule函数切换到别的进程中;2.当在内核控制路径中调用schedule函数时(上边说过了,内核控制路径中不允许切换进程),其实是在内核控制路径返回进程时调用(该时机就是ULK上说的延迟调用),说明有更重要的进程等待执行,需要抢占当前进程,因此在中断处理程序/异常处理程序返回时都要去检查当前进程能否被抢占,可以抢占的话就要调用schedule函数进行进程切换,包括从系统调用中返回用户空间时也要检查(这是统一的,因为系统调用本身也是异常,因此从系统调用中返回相当于从异常处理程序中返回,通过系统调用进入到内核态也可以说是内核控制路径,但是一般不这么叫)当前进程的抢占标志,能发生抢占的话就要去调用schedule函数。至此,进程切换的时机就分析完了。很好记的,要么是进程上下文发生进程切换(主动调用schedule),要么是从中断返回时切换,因此每次中断返回时必须要检查能否发生抢占,包括从系统调用返回也属于这种情形。

 

至此,进程调度机制咱们就分析完了(其实只分析了CFS调度)。实时进程调度以后再分析!

 

参考书籍:《深入理解linux内核》

     《深入理解linux内核架构》

参考文章:blog.csdn.net/wudongxu/article/details/8574737

     blog.csdn.net/dog250/article/details/5302869

       chxxxyg.blog.163.com/blog/static/1502811932012912546208/

  2.3调度器的演变.

    一开始的调度器是复杂度为O(n)**的始调度算法(实际上每次会遍历所有任务,所以复杂度为O(n)), 这个算法的缺点是当内核中有很多任务时,调度器本身就会耗费不少时间,所以,从linux2.5开始引入赫赫有名的O(1)**调度器。然而,linux是集全球很多程序员的聪明才智而发展起来的超级内核,没有最好,只有更好,在O(1)调度器风光了没几天就又被另一个更优秀的调度器取代了,它就是CFS调度器(Completely Fair Scheduler). 这个也是在2.6内核中引入的,具体为2.6.23,即从此版本开始,内核使用CFS作为它的默认调度器,O(1)调度器被抛弃了, 其实CFS的发展也是经历了很多阶段,最早期的楼梯算法(SD), 后来逐步对SD算法进行改进出RSDL(Rotating Staircase Deadline Scheduler), 这个算法已经是”完全公平”的雏形了, 直至CFS是最终被内核采纳的调度器, 它从RSDL/SD中吸取了完全公平的思想,不再跟踪进程的睡眠时间,也不再企图区分交互式进程。它将所有的进程都统一对待,这就是公平的含义。CFS的算法和实现都相当简单,众多的测试表明其性能也非常优越。     

调度器

Linux版本

O(n)的始调度算法

linux-0.11~2.4

O(1)调度器

linux-2.5

CFS调度器

linux-2.6~至今

  2.4调度器的设计.

    Linux的2种调度器:

调度器 描述
主调度器 直接根据进程的状态进行调度,比如当其打算睡眠或出于其他原因放弃占用CPU时
周期调度器 通过周期性的机制, 以固定的频率运行, 不时地去检测是否有必要进行调度

    其中这两者统称为通用调度器(generic scheduler)核心调度器(core scheduler)。

    每个调度器包括两个内容:调度框架(其实质就是两个函数框架)及调度器类。

    Linux的6种调度策略:

调度策略

描述

所在**调度器类**

SCHED_NORMAL

(也叫SCHED_OTHER)用于普通进程,通过CFS调度器实现。SCHED_BATCH用于非交互的处理器消耗型进程。SCHED_IDLE是在系统负载很低时使用

CFS

SCHED_BATCH

SCHED_NORMAL普通进程策略的分化版本。采用分时策略,根据动态优先级(可用nice()API设置),分配CPU运算资源。注意:这类进程比上述两类实时进程优先级低,换言之,在有实时进程存在时,实时进程优先调度。但针对吞吐量优化, 除了不能抢占外与常规任务一样,允许任务运行更长时间,更好地使用高速缓存,适合于成批处理的工作

CFS

SCHED_IDLE

优先级最低,在系统空闲时才跑这类进程(如利用闲散计算机资源跑地外文明搜索,蛋白质结构分析等任务,是此调度策略的适用者)

CFS-IDLE

SCHED_FIFO

先入先出调度算法(实时调度策略),相同优先级的任务先到先服务,高优先级的任务可以抢占低优先级的任务

RT

SCHED_RR

轮流调度算法(实时调度策略),后者提供 Roound-Robin 语义,采用时间片,相同优先级的任务当用完时间片会被放到队列尾部,以保证公平性,同样,高优先级的任务可以抢占低优先级的任务。不同要求的实时任务可以根据需要用sched_setscheduler() API设置策略

RT

SCHED_DEADLINE

新支持的实时进程调度策略,针对突发型计算,且对延迟和完成时间高度敏感的任务适用。基于Earliest Deadline First (EDF) 调度算法

DL

    Linux的5种调度类:

 

调度器类

描述

对应调度策略

stop_sched_class

优先级最高的线程,会中断所有其他线程,且不会被其他任务打断作用
1.发生在cpu_stop_cpu_callback 进行cpu之间任务migration
2.HOTPLUG_CPU的情况下关闭任务

无, 不需要调度普通进程

dl_sched_class

采用EDF最早截至时间优先算法调度实时进程

SCHED_DEADLINE

rt_sched_class

采用提供 Roound-Robin算法或者FIFO算法调度实时进程
具体调度策略由进程的task_struct->policy指定

SCHED_FIFO, SCHED_RR

fair_sched_clas

采用CFS算法调度普通的非实时进程

SCHED_NORMAL, SCHED_BATCH

idle_sched_class

采用CFS算法调度idle进程, 每个cup的第一个pid=0线程:swapper,是一个静态线程。调度类属于:idel_sched_class,所以在ps里面是看不到的。一般运行在开机过程和cpu异常的时候做dump

SCHED_IDLE

其所属进程的优先级顺序为:

stop_sched_class -> dl_sched_class -> rt_sched_class -> fair_sched_class -> idle_sched_class

Linux的3种调度实体:

调度器不限于调度进程, 还可以调度更大的实体, 比如实现组调度: 可用的CPUI时间首先在一半的进程组(比如, 所有进程按照所有者分组)之间分配, 接下来分配的时间再在组内进行二次分配,这种一般性要求调度器不直接操作进程, 而是处理可调度实体, 因此需要一个通用的数据结构描述这个调度实体,即seched_entity结构, 其实际上就代表了一个调度对象,可以为一个进程,也可以为一个进程组。linux中针对当前可调度的实时和非实时进程, 定义了类型为seched_entity的3个调度实体:

调度实体

名称

描述

对应调度器类

sched_dl_entity

DEADLINE调度实体

采用EDF算法调度的实时调度实体

dl_sched_class

sched_rt_entity

RT调度实体

采用Roound-Robin或者FIFO算法调度的实时调度实体

rt_sched_class

sched_entity

CFS调度实体

采用CFS算法调度的普通非实时进程的调度实体

fair_sched_class

  2.5CFS调度器.

    CFS完全公平调度器的调度器类叫fair_sched_class,下面是linux 4.5中的数据结构:

/*
 * All the scheduling class methods:
 */
const struct sched_class fair_sched_class = {
    .next            = &idle_sched_class,
    .enqueue_task        = enqueue_task_fair,
    .dequeue_task        = dequeue_task_fair,
    .yield_task        = yield_task_fair,
    .yield_to_task        = yield_to_task_fair,

    .check_preempt_curr    = check_preempt_wakeup,

    .pick_next_task        = pick_next_task_fair,
    .put_prev_task        = put_prev_task_fair,

#ifdef CONFIG_SMP
    .select_task_rq        = select_task_rq_fair,
    .migrate_task_rq    = migrate_task_rq_fair,

    .rq_online        = rq_online_fair,
    .rq_offline        = rq_offline_fair,

    .task_waking        = task_waking_fair,
    .task_dead        = task_dead_fair,
    .set_cpus_allowed    = set_cpus_allowed_common,
#endif

    .set_curr_task          = set_curr_task_fair,
    .task_tick        = task_tick_fair,
    .task_fork        = task_fork_fair,

    .prio_changed        = prio_changed_fair,
    .switched_from        = switched_from_fair,
    .switched_to        = switched_to_fair,

    .get_rr_interval    = get_rr_interval_fair,

    .update_curr        = update_curr_fair,

#ifdef CONFIG_FAIR_GROUP_SCHED
    .task_move_group    = task_move_group_fair,
#endif
};

其中一些成员变量的含义为:

成员

描述

next

下个优先级的调度类, 让所有的调度类通过next链接在一个链表中

enqueue_task

向就绪队列中添加一个进程, 某个任务进入可运行状态时,该函数将得到调用。它将调度实体(进程)放入红黑树中,并对 nr_running 变量加 1

dequeue_task

将一个进程从就就绪队列中删除, 当某个任务退出可运行状态时调用该函数,它将从红黑树中去掉对应的调度实体,并从 nr_running 变量中减 1

yield_task

在进程想要资源放弃对处理器的控制权的时, 可使用在sched_yield系统调用, 会调用内核API yield_task完成此工作. compat_yield sysctl 关闭的情况下,该函数实际上执行先出队后入队;在这种情况下,它将调度实体放在红黑树的最右端

check_preempt_curr

该函数将检查当前运行的任务是否被抢占。在实际抢占正在运行的任务之前,CFS 调度程序模块将执行公平性测试。这将驱动唤醒式(wakeup)抢占

pick_next_task

该函数选择接下来要运行的最合适的进程

put_prev_task

用另一个进程代替当前运行的进程

set_curr_task

当任务修改其调度类或修改其任务组时,将调用这个函数

task_tick

在每次激活周期调度器时, 由周期性调度器调用, 该函数通常调用自 time tick 函数;它可能引起进程切换。这将驱动运行时(running)抢占

task_fork

内核调度程序为调度模块提供了管理新任务启动的机会, 用于建立fork系统调用和调度器之间的关联, 每次新进程建立后, 则用new_task通知调度器, CFS 调度模块使用它进行组调度,而用于实时任务的调度模块则不会使用这个函数

    CFS的就绪队列:

struct cfs_rq {
    struct load_weight load;/*CFS队列中所有进程的总负载*/
    unsigned int nr_running, h_nr_running;

    u64 exec_clock;/**/
    u64 min_vruntime; /*最小虚拟运行时间*/
#ifndef CONFIG_64BIT
    u64 min_vruntime_copy;
#endif
   /*红黑树的根root*/
    struct rb_root tasks_timeline;
  /*红黑树最左边的节点,也是下一个调度节点*/
    struct rb_node *rb_leftmost;
  
    /*
    * 'curr' points to currently running entity on this cfs_rq.
    * It is set to NULL otherwise (i.e when none are currently running).
    */
    struct sched_entity *curr, *next, *last, *skip;

#ifdef    CONFIG_SCHED_DEBUG
    unsigned int nr_spread_over;
#endif

#ifdef CONFIG_SMP
    /*
    * CFS load tracking
    */
    struct sched_avg avg;
    u64 runnable_load_sum;
    unsigned long runnable_load_avg;
#ifdef CONFIG_FAIR_GROUP_SCHED
    unsigned long tg_load_avg_contrib;
#endif
    atomic_long_t removed_load_avg, removed_util_avg;
#ifndef CONFIG_64BIT
    u64 load_last_update_time_copy;
#endif

#ifdef CONFIG_FAIR_GROUP_SCHED
    /*
    *  h_load = weight * f(tg)
    *
    * Where f(tg) is the recursive weight fraction assigned to
    * this group.
    */
    unsigned long h_load;
    u64 last_h_load_update;
    struct sched_entity *h_load_next;
#endif /* CONFIG_FAIR_GROUP_SCHED */
#endif /* CONFIG_SMP */

#ifdef CONFIG_FAIR_GROUP_SCHED
    struct rq *rq;    /* cpu runqueue to which this cfs_rq is attached */

    /*
    * leaf cfs_rqs are those that hold tasks (lowest schedulable entity in
    * a hierarchy). Non-leaf lrqs hold other higher schedulable entities
    * (like users, containers etc.)
    *
    * leaf_cfs_rq_list ties together list of leaf cfs_rq's in a cpu. This
    * list is used during load balance.
    */
    int on_list;
    struct list_head leaf_cfs_rq_list;
    struct task_group *tg;    /* group that "owns" this runqueue */

#ifdef CONFIG_CFS_BANDWIDTH
    int runtime_enabled;
    u64 runtime_expires;
    s64 runtime_remaining;

    u64 throttled_clock, throttled_clock_task;
    u64 throttled_clock_task_time;
    int throttled, throttle_count;
    struct list_head throttled_list;
#endif /* CONFIG_CFS_BANDWIDTH */
#endif /* CONFIG_FAIR_GROUP_SCHED */
};

一些成员变量的含义:

成员

描述

nr_running

队列上可运行进程的数目

h_nr_running

只对进程组有效,其下所有进程组中cfs_rq的nr_running总和

load

就绪队列上可运行进程的累计负荷权重(总负载)

min_vruntime

跟踪记录队列上所有进程的最小虚拟运行时间. 这个值是实现与就绪队列相关的虚拟时钟的基础。当更新当前运行任务的累计运行时间时或者当任务从队列删除去,如任务睡眠或退出,这时候会查看剩下的任务的vruntime是否大于min_vruntime,如果是则更新该值。

tasks_timeline

用于在按时间排序的红黑树中管理所有进程(红黑树的root)

rb_leftmost

总是设置为指向红黑树最左边的节点, 即需要被调度的进程. 该值其实可以可以通过病例红黑树获得, 但是将这个值存储下来可以减少搜索红黑树花费的平均时间

curr

当前正在运行的sched_entity(对于组虽然它不会在cpu上运行,但是当它的下层有一个task在cpu上运行,那么它所在的cfs_rq就把它当做是该cfs_rq上当前正在运行的sched_entity

next

表示有些进程急需运行,即使不遵从CFS调度也必须运行它,调度时会检查是否next需要调度,有就调度next

skip

略过进程(不会选择skip指定的进程调度)

    CFS调度的原理:

    在理想状态下时每个进程都能获得相同的时间片,并且同时运行在CPU上,但实际上一个CPU同一时刻运行的进程只能有一个。 也就是说,当一个进程占用CPU时,其他进程就必须等待。而往往有一些需要优先去占用CPU的进程,所以实际上我们是根据每个进程的权重来分配每个进程的运行时间,越重要的进程,我们设置的权重就越高。

    而前面说过,调度还有一个重要的意义在于要对所有进程尽可能地公平分配时间,可是从分配时间来看,权重越高的似乎分配到的运行时间就会越多,并没有让人感觉到公平,于是CFS引入了一个变量 : 虚拟运行时间(virtual runtime),它会惩罚当前正在运行的进程,以使那些正在等待的进程下次被调度。用vruntime的大小来衡量哪个进程是最优先需要被调度的。

    虚拟运行时间计算公式为:一次调度间隔的vruntime = 实际运行时间 * NICE_0_LOAD / 进程权重;**

    其中代码NICE_0_LOAD对应的是nice为0的进程的权重值为1024,而所有进程都以nice为0的进程的权重1024作为基准,计算自己的vruntime增加速度。(见后面公式)

/*nice和权重值的转换表*/
static const int prio_to_weight[40] = { 
 /* -20 */    88761,    71755,    56483,    46273,    36291, 
 /* -15 */    29154,    23254,    18705,    14949,    11916, 
 /* -10 */    9548,    7620,      6100,      4904,      3906, 
 /*  -5 */    3121,    2501,      1991,      1586,      1277, 
 /*  0 */    1024,      820,      655,      526,      423, 
 /*  5 */      335,      272,      215,      172,      137, 
 /*  10 */      110,      87,        70,        56,        45, 
 /*  15 */      36,      29,        23,        18,        15, 
};

因为CFS中的就绪队列是一棵以vruntime为键值的红黑树,虚拟时间越小的进程越靠近整个红黑树的最左端。因此,调度器每次选择位于红黑树最左端的那个进程,该进程的vruntime最小。(对应之前的min_vruntime)

    其中vruntime以下公式计算它的增长数值:

条件

公式

当前进程的nice != NICE_0_LOAD

vruntime += delta_exec * NICE_0_LOAD / 进程权重

当前进程的nice == NICE_0_LOAD

vruntime += delta_exec

  •  其中delta_exce为"内核计算当前和上一次更新负荷权重时两次的时间的差值", 计算公式为:delta_exec = 当前时间 - 上次更新时间

    因此权重越大的进程的vruntime的增长率会越小,更容易排在红黑树偏左端,进而更容易被调度,而权重小的则相反。

    计算完vruntime之后,就要进行设置红黑树。

  2.6红黑树

    2.6.1什么是红黑树?

    红黑树是一种在插入或删除结点时都需要维持平衡的二叉查找树,并且每个结点都具有颜色属性:

  1.     一个结点要么是红色的,要么是黑色的。
  2.     根结点是黑色的。
  3.     如果一个结点是红色的,那么它的子结点必须是黑色的,也就是说在沿着从根结点出发的任何路径上都不会出现两个连续的红色结点。
  4.     从一个结点到一个NULL指针的每条路径上必须包含相同数目的黑色结点。

    如下图所示:

    图片 13

    可以很明显的看出,该树的最左端的值是最小的。取走最左端的端点后,需要重新平衡红黑树。

    2.6.2重新设置min_vruntime的红黑树

    代码如下:

static void update_min_vruntime(struct cfs_rq *cfs_rq)
{
   /*初始化vruntime的值
   *相当于如下的代码
   *if (cfs_rq->curr != NULL)
   *  vruntime = cfs_rq->curr->vruntime;
   *else
   *  vruntime = cfs_rq->min_vruntime;
   */
    u64 vruntime = cfs_rq->min_vruntime;
  if (cfs_rq->curr)
        vruntime = cfs_rq->curr->vruntime;

    /* 检测红黑树是都有最左的节点, 即是否有进程在树上等待调度
     * cfs_rq->rb_leftmost(struct rb_node *)存储了进程红黑树的最左节点
     * 这个节点存储了即将要被调度的结点 */

  if (cfs_rq->rb_leftmost) {
    /* 获取最左结点的调度实体信息se, se中存储了其vruntime      
     * rb_leftmost的vruntime即树中所有节点的vruntiem中最小的那个 */
struct sched_entity *se = rb_entry(cfs_rq->rb_leftmost,
                          struct sched_entity,
                          run_node);
   /* 如果就绪队列上没有curr进程      
    * 则vruntime设置为树种最左结点的vruntime      
    * 否则设置vruntiem值为cfs_rq->curr->vruntime和se->vruntime的最小值 */
        if (!cfs_rq->curr)  /* 此时vruntime的原值为cfs_rq->min_vruntime*/
            vruntime = se->vruntime;
        else          /* 此时vruntime的原值为cfs_rq->curr->vruntime*/
            vruntime = min_vruntime(vruntime, se->vruntime);
    }

    /* ensure we never gain time by being placed backwards.
   * 为了保证min_vruntime单调不减
   * 只有在vruntime超出的cfs_rq->min_vruntime的时候才更新 */
    cfs_rq->min_vruntime = max_vruntime(cfs_rq->min_vruntime, vruntime);
#ifndef CONFIG_64BIT
    smp_wmb();
    cfs_rq->min_vruntime_copy = cfs_rq->min_vruntime;
#endif
}

    重新平衡完min_vruntime的红黑树之后,就可以继续通过CFS去调度进程了,并以此循环。

3.体会

  这些只是Linux下的一小部分罢了,源码的代码量大到吓人,基于无数大牛们的努力写出了现在的Linux,而Linux永远在不断的更新,这些代码算法等等永远不会是最好的,我还需要不断的学习新的知识,继续探索这个充斥着01的世界。

本文永久更新链接地址

 

 

 

图片 14

本文由金沙棋牌发布于操作系统,转载请注明出处:内核源码分析之进程调度机制,5的进程模型与调

关键词:

上一篇:Linux目录结构及文件基本操作,文件管理

下一篇:没有了