Linux进程调度

1
2
3
4
5

   In computing, scheduling is the method by which work is assigned
   to resources that complete the work. The work may be virtual
   computation elements such as threads, processes or data flows,
   which are in turn scheduled onto hardware resources such as
   processors, network links or expansion cards.

1

struct task_struct * task[NR_TASKS] = {&(init_task.task), };

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44

void schedule(void)
{
  int i,next,c;
  struct task_struct ** p;

/* check alarm, wake up any interruptible tasks that have got a signal */

  for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
    if (*p) {
      if ((*p)->timeout && (*p)->timeout < jiffies) {
          (*p)->timeout = 0;
          if ((*p)->state == TASK_INTERRUPTIBLE)
              (*p)->state = TASK_RUNNING;
      }
      if ((*p)->alarm && (*p)->alarm < jiffies) {
          (*p)->signal |= (1<<(SIGALRM-1));
          (*p)->alarm = 0;
      }
      if (((*p)->signal & ~(_BLOCKABLE & (*p)->blocked)) &&\

      (*p)->state==TASK_INTERRUPTIBLE)
      (*p)->state=TASK_RUNNING;
   }

/* this is the scheduler proper: */

 while (1) {
    c = -1;
    next = 0;
    i = NR_TASKS;
    p = &task[NR_TASKS];
    while (--i) {
        if (!*--p)
        continue;
        if ((*p)->state == TASK_RUNNING && (*p)->counter > c)
        c = (*p)->counter, next = i;
    }
   if (c) break;
    for(p = &LAST_TASK ; p > &FIRST_TASK ; --p)
        if (*p)
        (*p)->counter = ((*p)->counter >> 1) + (*p)->priority;
 }
 switch_to(next);
}

1
2
3
4
5
6

static void do_timer(int irq, struct pt_regs * regs)
{
  ...
  if ((--current->counter)>0) return;
  ...
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

static inline void __sleep_on(struct task_struct **p, int state)
{
    struct task_struct *tmp;
    if (!p)
        return;
    if (current == &(init_task.task))
        panic("task[0] trying to sleep");
    tmp = *p;
    *p = current;
    current->state = state;
repeat: schedule();
    if (*p && *p != current) {
        (**p).state = 0;
        current->state = TASK_UNINTERRUPTIBLE;
        goto repeat;
    }
    if (!*p)
        printk("Warning: *P = NULL\n\r");
    if (*p = tmp)
        tmp->state=0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

void wake_up(struct task_struct **p)
{
    if (p && *p) {
        if ((**p).state == TASK_STOPPED)
            printk("wake_up: TASK_STOPPED");
        if ((**p).state == TASK_ZOMBIE)
            printk("wake_up: TASK_ZOMBIE");
        (**p).state=0;
    }
}

1
2
3
4
5
6
7
8
9

struct task_struct {
  long state;
  long counter;
  long priority;
  ...
};

#define INIT_TASK \
  { 0,15,15, \

1
2
3
4
5
6
7
8
9

int copy_process(int nr,long ebp,long edi,long esi,long gs,long none,
        long ebx,long ecx,long edx, long orig_eax, 
        long fs,long es,long ds,
        long eip,long cs,long eflags,long esp,long ss)
{
  ...
  p->counter = p->priority;
  ...
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

void main(void)     
{   
/*
 *   NOTE!!   For any other task 'pause()' would mean we have to get a
 * signal to awaken, but task0 is the sole exception (see 'schedule()')
 * as task 0 gets activated at every idle moment (when no other tasks
 * can run). For task0 'pause()' just means we go check if some other
 * task can run, and if not we return here.
 */
  for(;;)
   __asm__("int $0x80"::"a" (__NR_pause):"ax");
}

1

#define NR_TASKS   64

1
2

static union task_union init_task = {INIT_TASK,};
struct task_struct *current = &(init_task.task);

1
2
3
4
5
6
7
8

static union {
  struct schedule_data {
    struct task_struct * prev;
      long prevstate;
      cycles_t last_schedule;
    } schedule_data;
  char __pad [SMP_CACHE_BYTES];
} aligned_data [NR_CPUS] __cacheline_aligned = { {{&init_task,0}}};

1
2
3

#define SCHED_OTHER   0
#define SCHED_FIFO    1
#define SCHED_RR      2

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107

asmlinkage void schedule(void)
{
    struct schedule_data * sched_data;
    struct task_struct * prev, * next;
    int this_cpu;

    run_task_queue(&tq_scheduler);

    prev = current;
    this_cpu = prev->processor;

    sched_data = & aligned_data[this_cpu].schedule_data;

    if (in_interrupt())
        goto scheduling_in_interrupt;
    release_kernel_lock(prev, this_cpu);

    if (bh_active & bh_mask)
        do_bottom_half();

    spin_lock(&scheduler_lock);
    spin_lock_irq(&runqueue_lock);

    prev->need_resched = 0;

    if (!prev->counter && prev->policy == SCHED_RR) {
        prev->counter = prev->priority;
        move_last_runqueue(prev);
    }

    switch (prev->state) {
        case TASK_INTERRUPTIBLE:
            if (signal_pending(prev)) {
                prev->state = TASK_RUNNING;
                break;
            }
        default:
            del_from_runqueue(prev);
        case TASK_RUNNING:
    }

    sched_data->prevstate = prev->state;

    {
        struct task_struct * p = init_task.next_run;
        int c = -1000;

        next = idle_task;
        if (prev->state == TASK_RUNNING) {
            c = goodness(prev, prev, this_cpu);
            next = prev;
        }

        spin_unlock_irq(&runqueue_lock);

        while (p != &init_task) {
            if (can_schedule(p)) {
                int weight = goodness(p, prev, this_cpu);
                if (weight > c)
                    c = weight, next = p;
            }
            p = p->next_run;
        }

        if (!c) {
            struct task_struct *p;
            read_lock(&tasklist_lock);
            for_each_task(p)
                p->counter = (p->counter >> 1) + p->priority;
            read_unlock(&tasklist_lock);
        }
    }

#ifdef __SMP__
    {
        cycles_t t, this_slice;

        t = get_cycles();
        this_slice = t - sched_data->last_schedule;
        sched_data->last_schedule = t;

        prev->avg_slice = this_slice + prev->avg_slice;
        prev->avg_slice >>= 1;
    }

    next->processor = this_cpu;
    next->has_cpu = 1;
    spin_unlock(&scheduler_lock);
#endif 
    if (prev != next) {
#ifdef __SMP__
        sched_data->prev = prev;
#endif
        kstat.context_swtch++;
        get_mmu_context(next);
        switch_to(prev,next);

        __schedule_tail();
    }

    reacquire_kernel_lock(current);
    return;

scheduling_in_interrupt:
    printk("Scheduling in interrupt\n");
    *(int *)0 = 0;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

static inline int goodness(struct task_struct * p, \
struct task_struct * prev, int this_cpu)
{
  int policy = p->policy;
  int weight;

  if (policy & SCHED_YIELD) {
    p->policy = policy & ~SCHED_YIELD;
    return 0;
  }

  if (policy != SCHED_OTHER)
    return 1000 + p->rt_priority;

  weight = p->counter;
  if (weight) {

#ifdef __SMP__
    if (p->processor == this_cpu)
        weight += PROC_CHANGE_PENALTY;
#endif
  if (p->mm == prev->mm)
    weight += 1;
 weight += p->priority;
 }
 return weight;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

static void update_process_times(unsigned long ticks, \
unsigned long system)
{
   ...
    p->counter -= ticks;
    if (p->counter < 0) {
      p->counter = 0;
      p->need_resched = 1;
   }
   ...
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

struct task_struct {
  ...
  long counter;
  long priority;
  ...
};

#define DEF_PRIORITY   (20*HZ/100) /* 210 ms time slices */

#define INIT_TASK \
/* state etc */ { 0,0,0,KERNEL_DS,&default_exec_domain,0, \
/* counter */   DEF_PRIORITY,DEF_PRIORITY,0, 

1
2
3
4
5
6
7

static inline struct task_struct * get_current(void)
{
  struct task_struct *current;
  __asm__("andl %%esp,%0; ":"=r" (current) : "0" (~8191UL));
  return current;
 }
#define current get_current()

1
2
3

#define SCHED_OTHER   0
#define SCHED_FIFO    1
#define SCHED_RR      2

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111

asmlinkage void schedule(void)
{
  struct schedule_data * sched_data;
  struct task_struct *prev, *next, *p;
  struct list_head *tmp;
  int this_cpu, c;

  spin_lock_prefetch(&runqueue_lock);

  if (!current->active_mm) BUG();
need_resched_back:
  prev = current;
  this_cpu = prev->processor;

  if (unlikely(in_interrupt())) {
    printk("Scheduling in interrupt\n");
    BUG();
  }

  release_kernel_lock(prev, this_cpu);

  sched_data = & aligned_data[this_cpu].schedule_data;

  spin_lock_irq(&runqueue_lock);

  if (unlikely(prev->policy == SCHED_RR))
    if (!prev->counter) {
      prev->counter = NICE_TO_TICKS(prev->nice);
      move_last_runqueue(prev);
  }

  switch (prev->state) {
    case TASK_INTERRUPTIBLE:
     if (signal_pending(prev)) {
        prev->state = TASK_RUNNING;
        break;
     }
    default:
      del_from_runqueue(prev);
    case TASK_RUNNING:;
  }
  prev->need_resched = 0;

repeat_schedule:
  next = idle_task(this_cpu);
  c = -1000;
  list_for_each(tmp, &runqueue_head) {
    p = list_entry(tmp, struct task_struct, run_list);
    if (can_schedule(p, this_cpu)) {
      int weight = goodness(p, this_cpu, prev->active_mm);
      if (weight > c)
         c = weight, next = p;
    }
 }

  if (unlikely(!c)) {
    struct task_struct *p;

    spin_unlock_irq(&runqueue_lock);
    read_lock(&tasklist_lock);
    for_each_task(p)
      p->counter = (p->counter >> 1) + NICE_TO_TICKS(p->nice);
    read_unlock(&tasklist_lock);
    spin_lock_irq(&runqueue_lock);
    goto repeat_schedule;
 }

  sched_data->curr = next;
  task_set_cpu(next, this_cpu);
  spin_unlock_irq(&runqueue_lock);

  if (unlikely(prev == next)) {
    prev->policy &= ~SCHED_YIELD;
    goto same_process;
  }

#ifdef CONFIG_SMP
  sched_data->last_schedule = get_cycles();

#endif

  kstat.context_swtch++;
  prepare_to_switch();
  {
    struct mm_struct *mm = next->mm;
    struct mm_struct *oldmm = prev->active_mm;
   if (!mm) {
      if (next->active_mm) BUG();
      next->active_mm = oldmm;
      atomic_inc(&oldmm->mm_count);
      enter_lazy_tlb(oldmm, next, this_cpu);
   } else {
      if (next->active_mm != mm) BUG();
      switch_mm(oldmm, mm, next, this_cpu);
   }

   if (!prev->mm) {
      prev->active_mm = NULL;
      mmdrop(oldmm);
   }
  }

  switch_to(prev, next, prev);
  __schedule_tail(prev);

same_process:
  reacquire_kernel_lock(current);
  if (current->need_resched)
     goto need_resched_back;
     return;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

#ifdef CONFIG_SMP

#define idle_task(cpu) (init_tasks[cpu_number_map(cpu)])
#define can_schedule(p,cpu) \
    ((p)->cpus_runnable & (p)->cpus_allowed & (1UL << cpu))

#else

#define idle_task(cpu) (&init_task)
#define can_schedule(p,cpu) (1)

#endif

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

/*
 * Scheduling quanta.
 *
 * NOTE! The unix "nice" value influences how long a process
 * gets. The nice value ranges from -20 to +19, where a -20
 * is a "high-priority" task, and a "+10" is a low-priority
 * task.
 *
 * We want the time-slice to be around 50ms or so, so this
 * calculation depends on the value of HZ.
 */
#if HZ < 200
#define TICK_SCALE(x)  ((x) >> 2)
#elif HZ < 400
#define TICK_SCALE(x)  ((x) >> 1)
#elif HZ < 800
#define TICK_SCALE(x)  (x)
#elif HZ < 1600
#define TICK_SCALE(x)  ((x) << 1)
#else
#define TICK_SCALE(x)  ((x) << 2)
#endif

#define NICE_TO_TICKS(nice)    (TICK_SCALE(20-(nice))+1)

1

#define DEF_COUNTER    (10*HZ/100) /* 100 ms time slice */

1
2
3
4
5

#define INIT_TASK(tsk) \
{                                   \
    ...
    counter:        DEF_COUNTER,                    \
    ...

1
2
3
4

#define SCHED_NORMAL       0
#define SCHED_FIFO     1
#define SCHED_RR       2
#define SCHED_BATCH        3

1

Dynamic priority ≤ 3 x static priority /4 + 28

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159

asmlinkage void __sched schedule(void)
{
    struct task_struct *prev, *next;
    struct prio_array *array;
    struct list_head *queue;
    unsigned long long now;
    unsigned long run_time;
    int cpu, idx, new_prio;
    long *switch_count;
    struct rq *rq;

    /*
     * Test if we are atomic.  Since do_exit() needs to call into
     * schedule() atomically, we ignore that path for now.
     * Otherwise, whine if we are scheduling when we should not be.
     */
    if (unlikely(in_atomic() && !current->exit_state)) {
        printk(KERN_ERR "BUG: scheduling while atomic: "
            "%s/0x%08x/%d\n",
            current->comm, preempt_count(), current->pid);
        debug_show_held_locks(current);
        if (irqs_disabled())
            print_irqtrace_events(current);
        dump_stack();
    }
    profile_hit(SCHED_PROFILING, __builtin_return_address(0));

need_resched:
    preempt_disable();
    prev = current;
    release_kernel_lock(prev);
need_resched_nonpreemptible:
    rq = this_rq();

    /*:
     * The idle thread is not allowed to schedule!
     * Remove this check after it has been exercised a bit.
     */
    if (unlikely(prev == rq->idle) && prev->state != TASK_RUNNING) {
        printk(KERN_ERR "bad: scheduling from the idle thread!\n");
        dump_stack();
    }

    schedstat_inc(rq, sched_cnt);
    now = sched_clock();
    if (likely((long long)(now - prev->timestamp) < NS_MAX_SLEEP_AVG)) {
        run_time = now - prev->timestamp;
        if (unlikely((long long)(now - prev->timestamp) < 0))
            run_time = 0;
    } else
        run_time = NS_MAX_SLEEP_AVG;

    /*
     * Tasks charged proportionately less run_time at high sleep_avg to
     * delay them losing their interactive status
     */
    run_time /= (CURRENT_BONUS(prev) ? : 1);

    spin_lock_irq(&rq->lock);

    switch_count = &prev->nivcsw;
    if (prev->state && !(preempt_count() & PREEMPT_ACTIVE)) {
        switch_count = &prev->nvcsw;
        if (unlikely((prev->state & TASK_INTERRUPTIBLE) &&
                unlikely(signal_pending(prev))))
            prev->state = TASK_RUNNING;
        else {
            if (prev->state == TASK_UNINTERRUPTIBLE)
                rq->nr_uninterruptible++;
            deactivate_task(prev, rq);
        }
    }

    cpu = smp_processor_id();
    if (unlikely(!rq->nr_running)) {
        idle_balance(cpu, rq);
        if (!rq->nr_running) {
            next = rq->idle;
            rq->expired_timestamp = 0;
            goto switch_tasks;
        }
    }

    array = rq->active;
    if (unlikely(!array->nr_active)) {
        /*
         * Switch the active and expired arrays.
         */
        schedstat_inc(rq, sched_switch);
        rq->active = rq->expired;
        rq->expired = array;
        array = rq->active;
        rq->expired_timestamp = 0;
        rq->best_expired_prio = MAX_PRIO;
    }

    idx = sched_find_first_bit(array->bitmap);
    queue = array->queue + idx;
    next = list_entry(queue->next, struct task_struct, run_list);

    if (!rt_task(next) && interactive_sleep(next->sleep_type)) {
        unsigned long long delta = now - next->timestamp;
        if (unlikely((long long)(now - next->timestamp) < 0))
            delta = 0;

        if (next->sleep_type == SLEEP_INTERACTIVE)
            delta = delta * (ON_RUNQUEUE_WEIGHT * 128 / 100) / 128;

        array = next->array;
        new_prio = recalc_task_prio(next, next->timestamp + delta);

        if (unlikely(next->prio != new_prio)) {
            dequeue_task(next, array);
            next->prio = new_prio;
            enqueue_task(next, array);
        }
    }
    next->sleep_type = SLEEP_NORMAL;
switch_tasks:
    if (next == rq->idle)
        schedstat_inc(rq, sched_goidle);
    prefetch(next);
    prefetch_stack(next);
    clear_tsk_need_resched(prev);
    rcu_qsctr_inc(task_cpu(prev));

    update_cpu_clock(prev, rq, now);

    prev->sleep_avg -= run_time;
    if ((long)prev->sleep_avg <= 0)
        prev->sleep_avg = 0;
    prev->timestamp = prev->last_ran = now;

    sched_info_switch(prev, next);
    if (likely(prev != next)) {
        next->timestamp = next->last_ran = now;
        rq->nr_switches++;
        rq->curr = next;
        ++*switch_count;

        prepare_task_switch(rq, next);
        prev = context_switch(rq, prev, next);
        barrier();
        /*
         * this_rq must be evaluated again because prev may have moved
         * CPUs since it called schedule(), thus the 'rq' on its stack
         * frame will be invalid.
         */
        finish_task_switch(this_rq(), prev);
    } else
        spin_unlock_irq(&rq->lock);

    prev = current;
    if (unlikely(reacquire_kernel_lock(prev) < 0))
        goto need_resched_nonpreemptible;
    preempt_enable_no_resched();
    if (unlikely(test_thread_flag(TIF_NEED_RESCHED)))
        goto need_resched;
}

1
2
3
4
5

static inline int interactive_sleep(enum sleep_type sleep_type)
{
    return (sleep_type == SLEEP_INTERACTIVE ||
        sleep_type == SLEEP_INTERRUPTED);
}

1

    rcu_qsctr_inc(task_cpu(prev));

1
2
3
4
5
6
7

void release_task(struct task_struct * p)
{
  ...

  sched_exit(p);
  ...
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

void fastcall sched_exit(struct task_struct *p)
{
    unsigned long flags;
    struct rq *rq;

    /*
     * If the child was a (relative-) CPU hog then decrease
     * the sleep_avg of the parent as well.
     */
    rq = task_rq_lock(p->parent, &flags);
    if (p->first_time_slice && task_cpu(p) == task_cpu(p->parent)) {
        p->parent->time_slice += p->time_slice;
        if (unlikely(p->parent->time_slice > task_timeslice(p)))
            p->parent->time_slice = task_timeslice(p);
    }
    if (p->sleep_avg < p->parent->sleep_avg)
        p->parent->sleep_avg = p->parent->sleep_avg /
        (EXIT_WEIGHT + 1) * EXIT_WEIGHT + p->sleep_avg /
        (EXIT_WEIGHT + 1);
    task_rq_unlock(rq, &flags);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

static void
place_entity(struct cfs_rq *cfs_rq, struct sched_entity *se, int initial)
{
    u64 vruntime = cfs_rq->min_vruntime;
    ...
    if (initial && sched_feat(START_DEBIT))
        vruntime += sched_vslice(cfs_rq, se);
    ...
    se->vruntime = max_vruntime(se->vruntime, vruntime);
}

1
2
3
4
5
6
7
8
9

/*
 * We calculate the vruntime slice of a to-be-inserted task.
 *
 * vs = s/w
 */
static u64 sched_vslice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    return calc_delta_fair(sched_slice(cfs_rq, se), se);
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10

/*
 * delta /= w
 */
static inline u64 calc_delta_fair(u64 delta, struct sched_entity *se)
{
    if (unlikely(se->load.weight != NICE_0_LOAD))
        delta = __calc_delta(delta, NICE_0_LOAD, &se->load);

    return delta;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

/*
 * The idea is to set a period in which each task runs once.
 *
 * When there are too many tasks (sched_nr_latency) we have to stretch
 * this period because otherwise the slices get too small.
 *
 * p = (nr <= nl) ? l : l*nr/nl
 */
static u64 __sched_period(unsigned long nr_running)
{
    if (unlikely(nr_running > sched_nr_latency))
        return nr_running * sysctl_sched_min_granularity;
    else
        return sysctl_sched_latency;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27

/*
 * We calculate the wall-time slice from the period by taking a part
 * proportional to the weight.
 *
 * s = p*P[w/rw]
 */
 static u64 sched_slice(struct cfs_rq *cfs_rq, struct sched_entity *se)
{
    u64 slice = __sched_period(cfs_rq->nr_running + !se->on_rq);

    for_each_sched_entity(se) {
        struct load_weight *load;
        struct load_weight lw;

        cfs_rq = cfs_rq_of(se);
        load = &cfs_rq->load;

        if (unlikely(!se->on_rq)) {
            lw = cfs_rq->load;

            update_load_add(&lw, se->load.weight);
            load = &lw;
        }
        slice = __calc_delta(slice, se->load.weight, load);
    }
    return slice;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

/*
 * delta_exec * weight / lw.weight
 *   OR
 * (delta_exec * (weight * lw->inv_weight)) >> WMULT_SHIFT
 *
 * Either weight := NICE_0_LOAD and lw \e sched_prio_to_wmult[], in which case
 * we're guaranteed shift stays positive because inv_weight is guaranteed to
 * fit 32 bits, and NICE_0_LOAD gives another 10 bits; therefore shift >= 22.
 *
 * Or, weight =< lw.weight (because lw.weight is the runqueue weight), thus
 * weight/lw.weight <= 1, and therefore our shift will also be positive.
 */
static u64 __calc_delta(u64 delta_exec, unsigned long weight, struct load_weight *lw)
{
    u64 fact = scale_load_down(weight);
    int shift = WMULT_SHIFT;

    __update_inv_weight(lw);

    if (unlikely(fact >> 32)) {
        while (fact >> 32) {
            fact >>= 1;
            shift--;
        }
    }

    /* hint to use a 32x32->64 mul */
    fact = (u64)(u32)fact * lw->inv_weight;

    while (fact >> 32) {
        fact >>= 1;
        shift--;
    }

    return mul_u64_u32_shr(delta_exec, fact, shift);
}