kernel/ckrm_sched.c

   1 /* kernel/ckrm_sched.c - Supporting functions for ckrm scheduling
   2  *
   3  * Copyright (C) Haoqiang Zheng,  IBM Corp. 2004
   4  *           (C) Hubertus Franke, IBM Corp. 2004
   5  *
   6  * Latest version, more details at http://ckrm.sf.net
   7  *
   8  * This program is free software; you can redistribute it and/or modify
   9  * it under the terms of the GNU General Public License as published by
  10  * the Free Software Foundation; either version 2 of the License, or
  11  * (at your option) any later version.
  12  *
  13  */
  14 #include <linux/mm.h>
  15 #include <linux/init.h>
  16 #include <linux/ckrm_sched.h>
  17
  18 rwlock_t   class_list_lock = RW_LOCK_UNLOCKED;
  19 LIST_HEAD(active_cpu_classes);   // list of active cpu classes; anchor
  20
  21 struct ckrm_cpu_class default_cpu_class_obj;
  22
  23 struct ckrm_cpu_class * get_default_cpu_class(void) {
  24         return (&default_cpu_class_obj);
  25 }
  26
  27 /*******************************************************/
  28 /*                CVT Management                       */
  29 /*******************************************************/
  30
  31 static inline void check_inactive_class(ckrm_lrq_t * lrq,CVT_t cur_cvt)
  32 {
  33         CVT_t min_cvt;
  34         CVT_t bonus;
  35
  36         //just a safty measure
  37         if (unlikely(! cur_cvt))
  38                 return;
  39
  40 #ifndef INTERACTIVE_BONUS_SUPPORT
  41 #warning "ACB taking out interactive bonus calculation"
  42         bonus = 0;
  43 #else
  44         /*
  45          * Always leaving a small bonus for inactive classes
  46          * allows them to compete for cycles immediately when the become
  47          * active. This should improve interactive behavior
  48          */
  49         bonus = INTERACTIVE_BONUS(lrq);
  50 #endif
  51
  52         //cvt can't be negative
  53         if (cur_cvt > bonus)
  54                 min_cvt = cur_cvt - bonus;
  55         else
  56                 min_cvt = 0;
  57
  58         if (lrq->local_cvt < min_cvt) {
  59                 CVT_t lost_cvt;
  60
  61                 lost_cvt = scale_cvt(min_cvt - lrq->local_cvt,lrq);
  62                 lrq->local_cvt = min_cvt;
  63
  64                 /* add what the class lost to its savings*/
  65                 lrq->savings += lost_cvt;
  66                 if (lrq->savings > MAX_SAVINGS)
  67                         lrq->savings = MAX_SAVINGS;
  68         } else if (lrq->savings) {
  69                 /*
  70                  *if a class saving and falling behind
  71                  * then start to use it saving in a leaking bucket way
  72                  */
  73                 CVT_t savings_used;
  74
  75                 savings_used = scale_cvt((lrq->local_cvt - min_cvt),lrq);
  76                 if (savings_used > lrq->savings)
  77                         savings_used = lrq->savings;
  78
  79                 if (savings_used > SAVINGS_LEAK_SPEED)
  80                         savings_used = SAVINGS_LEAK_SPEED;
  81
  82                 BUG_ON(lrq->savings < savings_used);
  83                 lrq->savings -= savings_used;
  84                 unscale_cvt(savings_used,lrq);
  85                 BUG_ON(lrq->local_cvt < savings_used);
  86 #ifndef CVT_SAVINGS_SUPPORT
  87 #warning "ACB taking out cvt saving"
  88 #else
  89                 lrq->local_cvt -= savings_used;
  90 #endif
  91         }
  92 }
  93
  94 /*
  95  * return the max_cvt of all the classes
  96  */
  97 static inline CVT_t get_max_cvt(int this_cpu)
  98 {
  99         struct ckrm_cpu_class *clsptr;
 100         ckrm_lrq_t * lrq;
 101         CVT_t max_cvt;
 102
 103         max_cvt = 0;
 104
 105         /*update class time, at the same time get max_cvt */
 106         list_for_each_entry(clsptr, &active_cpu_classes, links) {
 107                 lrq = get_ckrm_lrq(clsptr, this_cpu);
 108                 if (lrq->local_cvt > max_cvt)
 109                         max_cvt = lrq->local_cvt;
 110         }
 111
 112         return max_cvt;
 113 }
 114
 115 /**
 116  * update_class_cputime - updates cvt of inactive classes
 117  * -- an inactive class shouldn't starve others when it comes back
 118  * -- the cpu time it lost when it's inactive should be accumulated
 119  * -- its accumulated saving should be compensated (in a leaky bucket fashion)
 120  *
 121  * class_list_lock must have been acquired
 122  */
 123 void update_class_cputime(int this_cpu)
 124 {
 125         struct ckrm_cpu_class *clsptr;
 126         ckrm_lrq_t * lrq;
 127         CVT_t cur_cvt;
 128
 129         /*
 130          *  a class's local_cvt must not be significantly smaller than min_cvt
 131          *  of active classes otherwise, it will starve other classes when it
 132          *  is reactivated.
 133          *
 134          *  Hence we keep all local_cvt's within a range of the min_cvt off
 135          *  all active classes (approximated by the local_cvt of the currently
 136          *  running class) and account for how many cycles where thus taken
 137          *  from an inactive class building a savings (not to exceed a few seconds)
 138          *  for a class to gradually make up upon reactivation, without
 139          *  starvation of other classes.
 140          *
 141          */
 142         cur_cvt = get_local_cur_cvt(this_cpu);
 143
 144         /*
 145          * cur_cvt == 0 means the system is now idle
 146          * in this case, we use max_cvt as cur_cvt
 147          * max_cvt roughly represents the cvt of the class
 148          * that has just finished running
 149          *
 150          * fairness wouldn't be a problem since we account for whatever lost in savings
 151          * if the system is not busy, the system responsiveness is not a problem.
 152          * still fine if the sytem is busy, but happened to be idle at this certain point
 153          * since bias toward interactive classes (class priority) is a more important way to improve system responsiveness
 154          */
 155         if (unlikely(! cur_cvt))  {
 156                 cur_cvt = get_max_cvt(this_cpu);
 157                 //return;
 158         }
 159
 160         /*
 161          *  - check the local cvt of all the classes
 162          *  - update total_ns received by the class
 163          *  - do a usage sampling for the whole class
 164          */
 165         list_for_each_entry(clsptr, &active_cpu_classes, links) {
 166                 lrq = get_ckrm_lrq(clsptr, this_cpu);
 167
 168                 spin_lock(&clsptr->stat.stat_lock);
 169                 clsptr->stat.total_ns += lrq->uncounted_ns;
 170                 ckrm_sample_usage(clsptr);
 171                 spin_unlock(&clsptr->stat.stat_lock);
 172                 lrq->uncounted_ns = 0;
 173
 174                 check_inactive_class(lrq,cur_cvt);
 175         }
 176 }
 177
 178 /*******************************************************/
 179 /*                PID load balancing stuff             */
 180 /*******************************************************/
 181 #define PID_SAMPLE_T 32
 182 #define PID_KP 20
 183 #define PID_KI 60
 184 #define PID_KD 20
 185
 186 /**
 187  * sample pid load periodically
 188  */
 189 void ckrm_load_sample(ckrm_load_t* pid,int cpu)
 190 {
 191         long load;
 192         long err;
 193
 194         if (jiffies % PID_SAMPLE_T)
 195                 return;
 196
 197         adjust_local_weight();
 198
 199         load = ckrm_cpu_load(cpu);
 200         err = load - pid->load_p;
 201         pid->load_d = err;
 202         pid->load_p = load;
 203         pid->load_i *= 9;
 204         pid->load_i += load;
 205         pid->load_i /= 10;
 206 }
 207
 208 long pid_get_pressure(ckrm_load_t* ckrm_load, int local_group)
 209 {
 210         long pressure;
 211         pressure = ckrm_load->load_p * PID_KP;
 212         pressure += ckrm_load->load_i * PID_KI;
 213         pressure += ckrm_load->load_d * PID_KD;
 214         pressure /= 100;
 215         return pressure;
 216 }