osfmk/kern/priority.c

   1 /*
   2  * Copyright (c) 2000-2008 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(thread, 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
 177                 pset_unlock(pset);
 178         }
 179
 180         thread_unlock(thread);
 181 }
 182
 183 /*
 184  *      Define shifts for simulating (5/8) ** n
 185  *
 186  *      Shift structures for holding update shifts.  Actual computation
 187  *      is  usage = (usage >> shift1) +/- (usage >> abs(shift2))  where the
 188  *      +/- is determined by the sign of shift 2.
 189  */
 190 struct shift_data {
 191         int     shift1;
 192         int     shift2;
 193 };
 194
 195 #define SCHED_DECAY_TICKS       32
 196 static struct shift_data        sched_decay_shifts[SCHED_DECAY_TICKS] = {
 197         {1,1},{1,3},{1,-3},{2,-7},{3,5},{3,-5},{4,-8},{5,7},
 198         {5,-7},{6,-10},{7,10},{7,-9},{8,-11},{9,12},{9,-11},{10,-13},
 199         {11,14},{11,-13},{12,-15},{13,17},{13,-15},{14,-17},{15,19},{16,18},
 200         {16,-19},{17,22},{18,20},{18,-20},{19,26},{20,22},{20,-22},{21,-27}
 201 };
 202
 203 /*
 204  *      do_priority_computation:
 205  *
 206  *      Calculate the timesharing priority based upon usage and load.
 207  */
 208 #define do_priority_computation(thread, pri)                                                    \
 209         MACRO_BEGIN                                                                                                                     \
 210         (pri) = (thread)->priority              /* start with base priority */          \
 211             - ((thread)->sched_usage >> (thread)->pri_shift);                           \
 212         if ((pri) < MINPRI_USER)                                                                                        \
 213                 (pri) = MINPRI_USER;                                                                                    \
 214         else                                                                                                                            \
 215         if ((pri) > MAXPRI_KERNEL)                                                                                      \
 216                 (pri) = MAXPRI_KERNEL;                                                                                  \
 217         MACRO_END
 218
 219 /*
 220  *      set_priority:
 221  *
 222  *      Set the base priority of the thread
 223  *      and reset its scheduled priority.
 224  *
 225  *      Called with the thread locked.
 226  */
 227 void
 228 set_priority(
 229         register thread_t       thread,
 230         register int            priority)
 231 {
 232         thread->priority = priority;
 233         compute_priority(thread, FALSE);
 234 }
 235
 236 /*
 237  *      compute_priority:
 238  *
 239  *      Reset the scheduled priority of the thread
 240  *      according to its base priority if the
 241  *      thread has not been promoted or depressed.
 242  *
 243  *      Called with the thread locked.
 244  */
 245 void
 246 compute_priority(
 247         register thread_t       thread,
 248         boolean_t                       override_depress)
 249 {
 250         register int            priority;
 251
 252         if (    !(thread->sched_mode & TH_MODE_PROMOTED)                        &&
 253                         (!(thread->sched_mode & TH_MODE_ISDEPRESSED)    ||
 254                                  override_depress                                                       )               ) {
 255                 if (thread->sched_mode & TH_MODE_TIMESHARE)
 256                         do_priority_computation(thread, priority);
 257                 else
 258                         priority = thread->priority;
 259
 260                 set_sched_pri(thread, priority);
 261         }
 262 }
 263
 264 /*
 265  *      compute_my_priority:
 266  *
 267  *      Reset the scheduled priority for
 268  *      a timesharing thread.
 269  *
 270  *      Only for use on the current thread
 271  *      if timesharing and not depressed.
 272  *
 273  *      Called with the thread locked.
 274  */
 275 void
 276 compute_my_priority(
 277         register thread_t       thread)
 278 {
 279         register int            priority;
 280
 281         do_priority_computation(thread, priority);
 282         assert(thread->runq == PROCESSOR_NULL);
 283         thread->sched_pri = priority;
 284 }
 285
 286 /*
 287  *      update_priority
 288  *
 289  *      Perform housekeeping operations driven by scheduler tick.
 290  *
 291  *      Called with the thread locked.
 292  */
 293 void
 294 update_priority(
 295         register thread_t       thread)
 296 {
 297         register unsigned       ticks;
 298         register uint32_t       delta;
 299
 300         ticks = sched_tick - thread->sched_stamp;
 301         assert(ticks != 0);
 302         thread->sched_stamp += ticks;
 303         thread->pri_shift = sched_pri_shift;
 304
 305         /*
 306          *      Gather cpu usage data.
 307          */
 308         thread_timer_delta(thread, delta);
 309         if (ticks < SCHED_DECAY_TICKS) {
 310                 register struct shift_data      *shiftp;
 311
 312                 /*
 313                  *      Accumulate timesharing usage only
 314                  *      during contention for processor
 315                  *      resources.
 316                  */
 317                 if (thread->pri_shift < INT8_MAX)
 318                         thread->sched_usage += delta;
 319
 320                 thread->cpu_usage += delta + thread->cpu_delta;
 321                 thread->cpu_delta = 0;
 322
 323                 shiftp = &sched_decay_shifts[ticks];
 324                 if (shiftp->shift2 > 0) {
 325                     thread->cpu_usage =
 326                                                 (thread->cpu_usage >> shiftp->shift1) +
 327                                                 (thread->cpu_usage >> shiftp->shift2);
 328                     thread->sched_usage =
 329                                                 (thread->sched_usage >> shiftp->shift1) +
 330                                                 (thread->sched_usage >> shiftp->shift2);
 331                 }
 332                 else {
 333                     thread->cpu_usage =
 334                                                 (thread->cpu_usage >> shiftp->shift1) -
 335                                                 (thread->cpu_usage >> -(shiftp->shift2));
 336                     thread->sched_usage =
 337                                                 (thread->sched_usage >> shiftp->shift1) -
 338                                                 (thread->sched_usage >> -(shiftp->shift2));
 339                 }
 340         }
 341         else {
 342                 thread->cpu_usage = thread->cpu_delta = 0;
 343                 thread->sched_usage = 0;
 344         }
 345
 346         /*
 347          *      Check for fail-safe release.
 348          */
 349         if (    (thread->sched_mode & TH_MODE_FAILSAFE)         &&
 350                         thread->sched_stamp >= thread->safe_release             ) {
 351                 if (!(thread->safe_mode & TH_MODE_TIMESHARE)) {
 352                         if (thread->safe_mode & TH_MODE_REALTIME) {
 353                                 thread->priority = BASEPRI_RTQUEUES;
 354
 355                                 thread->sched_mode |= TH_MODE_REALTIME;
 356                         }
 357
 358                         thread->sched_mode &= ~TH_MODE_TIMESHARE;
 359
 360                         if ((thread->state & (TH_RUN|TH_IDLE)) == TH_RUN)
 361                                 sched_share_decr();
 362
 363                         if (!(thread->sched_mode & TH_MODE_ISDEPRESSED))
 364                                 set_sched_pri(thread, thread->priority);
 365                 }
 366
 367                 thread->safe_mode = 0;
 368                 thread->sched_mode &= ~TH_MODE_FAILSAFE;
 369         }
 370
 371         /*
 372          *      Recompute scheduled priority if appropriate.
 373          */
 374         if (    (thread->sched_mode & TH_MODE_TIMESHARE)        &&
 375                         !(thread->sched_mode & TH_MODE_PROMOTED)        &&
 376                         !(thread->sched_mode & TH_MODE_ISDEPRESSED)             ) {
 377                 register int            new_pri;
 378
 379                 do_priority_computation(thread, new_pri);
 380                 if (new_pri != thread->sched_pri) {
 381                         boolean_t               removed = run_queue_remove(thread);
 382
 383                         thread->sched_pri = new_pri;
 384                         if (removed)
 385                                 thread_setrun(thread, SCHED_TAILQ);
 386                 }
 387         }
 388 }