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

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

1.操作系统是怎么协会进程的?

在架空模型中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决定插入就绪队列的岗位。

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

1.就绪队列

  1.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。

  进程大约可以分为交互式进度批处理进度实时进度。对于分裂的历程选择不一样的调度策略,近年来Linux内核中默许达成了4种调度策略,分别是deadline、realtime、CFS和idle,分别适用struct
sched_class来定义调度类。

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

    刚接触时可能时时会将那个东西搞混。简单一点的说,进程是一个大工程,线程则是以此大工程中每个小地方须求做的事物(在linux下作为”轻量级进度”):

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

  4种调度类经过next指针串联在一齐,用户空间程序能够应用调度策略API函数(sched_setscheduler())来设定用户进程的调度策略。

1 DEFINE_PER_CPU_SHARED_ALIGNED(struct rq, runqueues);

    例如当您打开QQ微信,那时系统启动了一个进度。然后你起来看外人发的新闻,那时启动了一个线程用来传输文本,假如发了一段语音,那也会启动一个线程来传输语音……(当然一个程序并不意味一定唯有一个进度)

   
进度执行实施时期周期性调度器周期性地启动,其负责更新一些连锁数据,并不承担进程之间的切换:
   
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为所求出的值。

标题一:请简述对进度调度器的了然,早起Linux内核调度器(包蕴O(N)和O(1))调度器是何等工作的?

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

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

考虑下当创设新进度或者经过唤醒时,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值,那么它始终排在进程队列的末段。

  调度器是按自然的章程对经过展开调度的一种机制,须要为顺序普通进度尽可能公平地共享CPU时间。

澳门金沙国际 1澳门金沙国际 2

struct task_struct {
    ……
 
    /* 指向经过内核栈 */
    void *stack;
 
    ……
 };

    对于新进程,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。

  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 };

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

II、睡眠进度被唤醒
   
将经过的vruntime值设置为cfs_rq->min_vruntime值,然后再开展一下互补:将vruntime减去与sysctl_sched_latencyd相关的一个数值。进度进入睡眠境况时cfs_rq->min_vruntime就当先或等于该进程的vruntime值,它在上床进程中vruntime值是不改动的,然而cfs_rq->min_vruntime的值却是单调增添的,进度醒来后补充的量由sysctl_sched_latency给出,不管进度遭到的有失偏颇待遇大仍然小,一律只补充这么多。

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

struct rq

/*线程描述符(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 */
};

实打实模型总括:
   
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()计算得出。

题目二:请简述进程优先级、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)

澳门金沙国际 3

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

  nice值从-20~19,进度默许的nice值为0。这足以知晓为40个等级,nice值越高,则先行级越低,反之亦然。(nice每变化1,则附和的进程取得CPU的时间就改变10%)。

澳门金沙国际 4澳门金沙国际 5

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

      
注意:关于a),注意本文的尾声添加的笺注。

  权重音信即为调度实体的权重,为了计算方便,内核约定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 };
  • esp寄存器为CPU栈指针,用来存放在栈顶单元的地点。当数码写入时,esp的值缩小;
  • thread_info和内核栈固然共用了thread_union结构,
    但是thread_info大小固定, 存储在联合体的开始有的,
    而内核栈由高地址向低地址增加,
    当内核栈的栈顶到达thread_info的储存空间时,
    则会发生栈溢出(内核中有kstack_end函数判断);
  • 系统的current指针指向了当前运作进度的thread_union(或者thread_info)的地址;

   
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早先化为父进程的静态优先级。

题材三:请简述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队列。

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

由于在一些意况下要求暂时进步进程的优先级,因而不但要求静态优先级和常见优先级,还亟需动态优先级prio;

难点四:CFS调度器中的vruntime是如何统计的?

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

  1.3经过标示符PID:

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

  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

struct task_struct {
    ……..

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

标题五: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)

    PID就好像大家学生的学号,每个人的身份证号一样,是全球无双的。而我辈会有一个群体,比就像一个班级,同一个学府等,即有同一个组群,由此建立了TGID,用来将同一个组的PID串联起来。其中getpid()再次回到当前进程的tgid值而不是pid的值。

         rt_mutex_slowlock() —->
__rt_mutex_基础源码分析之进度调度机制,进度管理之CFS调度器。slowlock() —->

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

2.1普通进度的调度实体sched_entity

    而在系统运转的时候,可能会建立极度卓殊多的进度,因而为了坚实基础的搜索效能,专门建立了几个hash表pids[PIDTYPE_TGID]、pids[PIDTYPE_TGID]、pids[PIDTYPE_PGID]、pids[PIDTYPE_SID]用来索引。

                
task_blocks_on_rt_mutex() —-> 
__rt_mutex_adjust_prio()

标题七: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 };

    在基础中,那三个哈希表一共占16个页框,也就是各样哈希表占4个页框,他们每个可以具备2048个表项,内核会把把那多少个哈希表的地点保存到pid_hash数组中。现在题材来了,拿pids[PIDTYPE_TGID]为例,怎么在2048个表项中保留32767个PID值,其实内核会对每个已经分配的PID值进行一个处理,获得的结果的数值就是对应的表项,处理结果相同的PID被串成一个链表,如下:

                                                                  
|–> rt_mutex_adjust_prio_chain()

  对于睡觉进程,其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域达成组调度。

澳门金沙国际 8

         
__rt_mutex_adjust_prio调整了近来抱有锁的进度的动态优先级(继承自等待队列中享有进度的最高优先级),rt_mutex_adjust_prio_chain()如若被调动的动态优先级的进度也在等候某个资源,那么也要链式地调动相应进程的动态优先级。

  对于新创制的进度,要求添加一个调度周期的虚构是时间(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

    当大家采纳”kill
29384″命令时,内核会按照29384甩卖得出199,然后以199为下标,获取PID哈希表中对应的链表头,并在此链表中找出PID=29384的进度。在进程描述符(thread_info)的*task中使用struct
pid_link
pids[PIDTYPE_MAX]链入这一个哈希表。对于其余多个哈希表,道理同样。

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

难点八:咋样总结普通进度的平分负载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中调用(其他地点也有),由此也是每个时钟周期调用五回,用来总计当前经过应该推行的“时间片”,进而才能看清进度是还是不是已经超(英文名:jīng chāo)越它的日子片,超出的话就要设置抢占标志,切换其他进程。

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-罗布in
语义,选取时间片,相同优先级的天职当用完时间片会被置于队列底部,以有限辅助公平性,同样,高优先级的天职可以抢占低优先级的天职。差异必要的实时职责可以依照须求用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-罗布in算法或者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-罗布in或者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

相关文章