osfmk/kern/priority.c

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