osfmk/kern/priority.c

   1 /*
   2  * Copyright (c) 2000-2009 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. The rights granted to you under the License
  10  * may not be used to create, or enable the creation or redistribution of,
  11  * unlawful or unlicensed copies of an Apple operating system, or to
  12  * circumvent, violate, or enable the circumvention or violation of, any
  13  * terms of an Apple operating system software license agreement.
  14  *
  15  * Please obtain a copy of the License at
  16  * http://www.opensource.apple.com/apsl/ and read it before using this file.
  17  *
  18  * The Original Code and all software distributed under the License are
  19  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  20  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  21  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  22  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  23  * Please see the License for the specific language governing rights and
  24  * limitations under the License.
  25  *
  26  * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
  27  */
  28 /*
  29  * @OSF_COPYRIGHT@
  30  */
  31 /*
  32  * Mach Operating System
  33  * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
  34  * All Rights Reserved.
  35  *
  36  * Permission to use, copy, modify and distribute this software and its
  37  * documentation is hereby granted, provided that both the copyright
  38  * notice and this permission notice appear in all copies of the
  39  * software, derivative works or modified versions, and any portions
  40  * thereof, and that both notices appear in supporting documentation.
  41  *
  42  * CARNEGIE MELLON ALLOWS FREE USE OF THIS SOFTWARE IN ITS "AS IS"
  43  * CONDITION.  CARNEGIE MELLON DISCLAIMS ANY LIABILITY OF ANY KIND FOR
  44  * ANY DAMAGES WHATSOEVER RESULTING FROM THE USE OF THIS SOFTWARE.
  45  *
  46  * Carnegie Mellon requests users of this software to return to
  47  *
  48  *  Software Distribution Coordinator  or  Software.Distribution@CS.CMU.EDU
  49  *  School of Computer Science
  50  *  Carnegie Mellon University
  51  *  Pittsburgh PA 15213-3890
  52  *
  53  * any improvements or extensions that they make and grant Carnegie Mellon
  54  * the rights to redistribute these changes.
  55  */
  56 /*
  57  */
  58 /*
  59  *      File:   clock_prim.c
  60  *      Author: Avadis Tevanian, Jr.
  61  *      Date:   1986
  62  *
  63  *      Clock primitives.
  64  */
  65
  66 #include <mach/boolean.h>
  67 #include <mach/kern_return.h>
  68 #include <mach/machine.h>
  69 #include <kern/host.h>
  70 #include <kern/mach_param.h>
  71 #include <kern/sched.h>
  72 #include <kern/spl.h>
  73 #include <kern/thread.h>
  74 #include <kern/processor.h>
  75 #include <machine/machparam.h>
  76
  77 /*
  78  *      thread_quantum_expire:
  79  *
  80  *      Recalculate the quantum and priority for a thread.
  81  *
  82  *      Called at splsched.
  83  */
  84
  85 void
  86 thread_quantum_expire(
  87         timer_call_param_t      p0,
  88         timer_call_param_t      p1)
  89 {
  90         processor_t                     processor = p0;
  91         thread_t                        thread = p1;
  92         ast_t                           preempt;
  93
  94         thread_lock(thread);
  95
  96         /*
  97          *      Check for fail-safe trip.
  98          */
  99         if (!(thread->sched_mode & (TH_MODE_TIMESHARE|TH_MODE_PROMOTED))) {
 100                 uint64_t                        new_computation;
 101
 102                 new_computation = processor->quantum_end;
 103                 new_computation -= thread->computation_epoch;
 104                 if (new_computation + thread->computation_metered >
 105                                                                                         max_unsafe_computation) {
 106
 107                         if (thread->sched_mode & TH_MODE_REALTIME) {
 108                                 thread->priority = DEPRESSPRI;
 109
 110                                 thread->safe_mode |= TH_MODE_REALTIME;
 111                                 thread->sched_mode &= ~TH_MODE_REALTIME;
 112                         }
 113
 114                         sched_share_incr();
 115
 116                         thread->safe_release = sched_tick + sched_safe_duration;
 117                         thread->sched_mode |= (TH_MODE_FAILSAFE|TH_MODE_TIMESHARE);
 118                 }
 119         }
 120
 121         /*
 122          *      Recompute scheduled priority if appropriate.
 123          */
 124         if (thread->sched_stamp != sched_tick)
 125                 update_priority(thread);
 126         else
 127         if (thread->sched_mode & TH_MODE_TIMESHARE) {
 128                 register uint32_t       delta;
 129
 130                 thread_timer_delta(thread, delta);
 131
 132                 /*
 133                  *      Accumulate timesharing usage only
 134                  *      during contention for processor
 135                  *      resources.
 136                  */
 137                 if (thread->pri_shift < INT8_MAX)
 138                         thread->sched_usage += delta;
 139
 140                 thread->cpu_delta += delta;
 141
 142                 /*
 143                  * Adjust the scheduled priority if
 144                  * the thread has not been promoted
 145                  * and is not depressed.
 146                  */
 147                 if (    !(thread->sched_mode & TH_MODE_PROMOTED)        &&
 148                                 !(thread->sched_mode & TH_MODE_ISDEPRESSED)             )
 149                         compute_my_priority(thread);
 150         }
 151
 152         processor->current_pri = thread->sched_pri;
 153
 154         /*
 155          *      This quantum is up, give this thread another.
 156          */
 157         if (first_timeslice(processor))
 158                 processor->timeslice--;
 159
 160         thread_quantum_init(thread);
 161         processor->quantum_end += thread->current_quantum;
 162         timer_call_enter1(&processor->quantum_timer,
 163                                                         thread, processor->quantum_end);
 164
 165         /*
 166          *      Context switch check.
 167          */
 168         if ((preempt = csw_check(processor)) != AST_NONE)
 169                 ast_on(preempt);
 170         else {
 171                 processor_set_t         pset = processor->processor_set;
 172
 173                 pset_lock(pset);
 174
 175                 pset_pri_hint(pset, processor, processor->current_pri);
 176                 pset_count_hint(pset, processor, processor->runq.count);
 177
 178                 pset_unlock(pset);
 179         }
 180
 181         thread_unlock(thread);
 182 }
 183
 184 /*
 185  *      Define shifts for simulating (5/8) ** n
 186  *
 187  *      Shift structures for holding update shifts.  Actual computation
 188  *      is  usage = (usage >> shift1) +/- (usage >> abs(shift2))  where the
 189  *      +/- is determined by the sign of shift 2.
 190  */
 191 struct shift_data {
 192         int     shift1;
 193         int     shift2;
 194 };
 195
 196 #define SCHED_DECAY_TICKS       32
 197 static struct shift_data        sched_decay_shifts[SCHED_DECAY_TICKS] = {
 198         {1,1},{1,3},{1,-3},{2,-7},{3,5},{3,-5},{4,-8},{5,7},
 199         {5,-7},{6,-10},{7,10},{7,-9},{8,-11},{9,12},{9,-11},{10,-13},
 200         {11,14},{11,-13},{12,-15},{13,17},{13,-15},{14,-17},{15,19},{16,18},
 201         {16,-19},{17,22},{18,20},{18,-20},{19,26},{20,22},{20,-22},{21,-27}
 202 };
 203
 204 /*
 205  *      do_priority_computation:
 206  *
 207  *      Calculate the timesharing priority based upon usage and load.
 208  */
 209 #define do_priority_computation(thread, pri)                                                    \
 210         MACRO_BEGIN                                                                                                                     \
 211         (pri) = (thread)->priority              /* start with base priority */          \
 212             - ((thread)->sched_usage >> (thread)->pri_shift);                           \
 213         if ((pri) < MINPRI_USER)                                                                                        \
 214                 (pri) = MINPRI_USER;                                                                                    \
 215         else                                                                                                                            \
 216         if ((pri) > MAXPRI_KERNEL)                                                                                      \
 217                 (pri) = MAXPRI_KERNEL;                                                                                  \
 218         MACRO_END
 219
 220 /*
 221  *      set_priority:
 222  *
 223  *      Set the base priority of the thread
 224  *      and reset its scheduled priority.
 225  *
 226  *      Called with the thread locked.
 227  */
 228 void
 229 set_priority(
 230         register thread_t       thread,
 231         register int            priority)
 232 {
 233         thread->priority = priority;
 234         compute_priority(thread, FALSE);
 235 }
 236
 237 /*
 238  *      compute_priority:
 239  *
 240  *      Reset the scheduled priority of the thread
 241  *      according to its base priority if the
 242  *      thread has not been promoted or depressed.
 243  *
 244  *      Called with the thread locked.
 245  */
 246 void
 247 compute_priority(
 248         register thread_t       thread,
 249         boolean_t                       override_depress)
 250 {
 251         register int            priority;
 252
 253         if (    !(thread->sched_mode & TH_MODE_PROMOTED)                        &&
 254                         (!(thread->sched_mode & TH_MODE_ISDEPRESSED)    ||
 255                                  override_depress                                                       )               ) {
 256                 if (thread->sched_mode & TH_MODE_TIMESHARE)
 257                         do_priority_computation(thread, priority);
 258                 else
 259                         priority = thread->priority;
 260
 261                 set_sched_pri(thread, priority);
 262         }
 263 }
 264
 265 /*
 266  *      compute_my_priority:
 267  *
 268  *      Reset the scheduled priority for
 269  *      a timesharing thread.
 270  *
 271  *      Only for use on the current thread
 272  *      if timesharing and not depressed.
 273  *
 274  *      Called with the thread locked.
 275  */
 276 void
 277 compute_my_priority(
 278         register thread_t       thread)
 279 {
 280         register int            priority;
 281
 282         do_priority_computation(thread, priority);
 283         assert(thread->runq == PROCESSOR_NULL);
 284         thread->sched_pri = priority;
 285 }
 286
 287 /*
 288  *      update_priority
 289  *
 290  *      Perform housekeeping operations driven by scheduler tick.
 291  *
 292  *      Called with the thread locked.
 293  */
 294 void
 295 update_priority(
 296         register thread_t       thread)
 297 {
 298         register unsigned       ticks;
 299         register uint32_t       delta;
 300
 301         ticks = sched_tick - thread->sched_stamp;
 302         assert(ticks != 0);
 303         thread->sched_stamp += ticks;
 304         thread->pri_shift = sched_pri_shift;
 305
 306         /*
 307          *      Gather cpu usage data.
 308          */
 309         thread_timer_delta(thread, delta);
 310         if (ticks < SCHED_DECAY_TICKS) {
 311                 register struct shift_data      *shiftp;
 312
 313                 /*
 314                  *      Accumulate timesharing usage only
 315                  *      during contention for processor
 316                  *      resources.
 317                  */
 318                 if (thread->pri_shift < INT8_MAX)
 319                         thread->sched_usage += delta;
 320
 321                 thread->cpu_usage += delta + thread->cpu_delta;
 322                 thread->cpu_delta = 0;
 323
 324                 shiftp = &sched_decay_shifts[ticks];
 325                 if (shiftp->shift2 > 0) {
 326                     thread->cpu_usage =
 327                                                 (thread->cpu_usage >> shiftp->shift1) +
 328                                                 (thread->cpu_usage >> shiftp->shift2);
 329                     thread->sched_usage =
 330                                                 (thread->sched_usage >> shiftp->shift1) +
 331                                                 (thread->sched_usage >> shiftp->shift2);
 332                 }
 333                 else {
 334                     thread->cpu_usage =
 335                                                 (thread->cpu_usage >> shiftp->shift1) -
 336                                                 (thread->cpu_usage >> -(shiftp->shift2));
 337                     thread->sched_usage =
 338                                                 (thread->sched_usage >> shiftp->shift1) -
 339                                                 (thread->sched_usage >> -(shiftp->shift2));
 340                 }
 341         }
 342         else {
 343                 thread->cpu_usage = thread->cpu_delta = 0;
 344                 thread->sched_usage = 0;
 345         }
 346
 347         /*
 348          *      Check for fail-safe release.
 349          */
 350         if (    (thread->sched_mode & TH_MODE_FAILSAFE)         &&
 351                         thread->sched_stamp >= thread->safe_release             ) {
 352                 if (!(thread->safe_mode & TH_MODE_TIMESHARE)) {
 353                         if (thread->safe_mode & TH_MODE_REALTIME) {
 354                                 thread->priority = BASEPRI_RTQUEUES;
 355
 356                                 thread->sched_mode |= TH_MODE_REALTIME;
 357                         }
 358
 359                         thread->sched_mode &= ~TH_MODE_TIMESHARE;
 360
 361                         if ((thread->state & (TH_RUN|TH_IDLE)) == TH_RUN)
 362                                 sched_share_decr();
 363
 364                         if (!(thread->sched_mode & TH_MODE_ISDEPRESSED))
 365                                 set_sched_pri(thread, thread->priority);
 366                 }
 367
 368                 thread->safe_mode = 0;
 369                 thread->sched_mode &= ~TH_MODE_FAILSAFE;
 370         }
 371
 372         /*
 373          *      Recompute scheduled priority if appropriate.
 374          */
 375         if (    (thread->sched_mode & TH_MODE_TIMESHARE)        &&
 376                         !(thread->sched_mode & TH_MODE_PROMOTED)        &&
 377                         !(thread->sched_mode & TH_MODE_ISDEPRESSED)             ) {
 378                 register int            new_pri;
 379
 380                 do_priority_computation(thread, new_pri);
 381                 if (new_pri != thread->sched_pri) {
 382                         boolean_t               removed = run_queue_remove(thread);
 383
 384                         thread->sched_pri = new_pri;
 385                         if (removed)
 386                                 thread_setrun(thread, SCHED_TAILQ);
 387                 }
 388         }
 389 }