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 #ifdef CONFIG_EMBEDDED
 210
 211 #define do_priority_computation(thread, pri)                                                    \
 212         MACRO_BEGIN                                                                                                                     \
 213         (pri) = (thread)->priority              /* start with base priority */          \
 214             - ((thread)->sched_usage >> (thread)->pri_shift);                           \
 215         if ((pri) < MAXPRI_THROTTLE) {                                                                          \
 216                 if ((thread)->task->max_priority > MAXPRI_THROTTLE)                             \
 217                         (pri) = MAXPRI_THROTTLE;                                                                        \
 218                 else                                                                                                                    \
 219                         if ((pri) < MINPRI_USER)                                                                        \
 220                                 (pri) = MINPRI_USER;                                                                    \
 221         } else                                                                                                                          \
 222         if ((pri) > MAXPRI_KERNEL)                                                                                      \
 223                 (pri) = MAXPRI_KERNEL;                                                                                  \
 224         MACRO_END
 225
 226 #else
 227
 228 #define do_priority_computation(thread, pri)                                                    \
 229         MACRO_BEGIN                                                                                                                     \
 230         (pri) = (thread)->priority              /* start with base priority */          \
 231             - ((thread)->sched_usage >> (thread)->pri_shift);                           \
 232         if ((pri) < MINPRI_USER)                                                                                        \
 233                 (pri) = MINPRI_USER;                                                                                    \
 234         else                                                                                                                            \
 235         if ((pri) > MAXPRI_KERNEL)                                                                                      \
 236                 (pri) = MAXPRI_KERNEL;                                                                                  \
 237         MACRO_END
 238
 239 #endif
 240
 241 /*
 242  *      set_priority:
 243  *
 244  *      Set the base priority of the thread
 245  *      and reset its scheduled priority.
 246  *
 247  *      Called with the thread locked.
 248  */
 249 void
 250 set_priority(
 251         register thread_t       thread,
 252         register int            priority)
 253 {
 254         thread->priority = priority;
 255         compute_priority(thread, FALSE);
 256 }
 257
 258 /*
 259  *      compute_priority:
 260  *
 261  *      Reset the scheduled priority of the thread
 262  *      according to its base priority if the
 263  *      thread has not been promoted or depressed.
 264  *
 265  *      Called with the thread locked.
 266  */
 267 void
 268 compute_priority(
 269         register thread_t       thread,
 270         boolean_t                       override_depress)
 271 {
 272         register int            priority;
 273
 274         if (    !(thread->sched_mode & TH_MODE_PROMOTED)                        &&
 275                         (!(thread->sched_mode & TH_MODE_ISDEPRESSED)    ||
 276                                  override_depress                                                       )               ) {
 277                 if (thread->sched_mode & TH_MODE_TIMESHARE)
 278                         do_priority_computation(thread, priority);
 279                 else
 280                         priority = thread->priority;
 281
 282                 set_sched_pri(thread, priority);
 283         }
 284 }
 285
 286 /*
 287  *      compute_my_priority:
 288  *
 289  *      Reset the scheduled priority for
 290  *      a timesharing thread.
 291  *
 292  *      Only for use on the current thread
 293  *      if timesharing and not depressed.
 294  *
 295  *      Called with the thread locked.
 296  */
 297 void
 298 compute_my_priority(
 299         register thread_t       thread)
 300 {
 301         register int            priority;
 302
 303         do_priority_computation(thread, priority);
 304         assert(thread->runq == PROCESSOR_NULL);
 305         thread->sched_pri = priority;
 306 }
 307
 308 /*
 309  *      update_priority
 310  *
 311  *      Perform housekeeping operations driven by scheduler tick.
 312  *
 313  *      Called with the thread locked.
 314  */
 315 void
 316 update_priority(
 317         register thread_t       thread)
 318 {
 319         register unsigned       ticks;
 320         register uint32_t       delta;
 321
 322         ticks = sched_tick - thread->sched_stamp;
 323         assert(ticks != 0);
 324         thread->sched_stamp += ticks;
 325         thread->pri_shift = sched_pri_shift;
 326
 327         /*
 328          *      Gather cpu usage data.
 329          */
 330         thread_timer_delta(thread, delta);
 331         if (ticks < SCHED_DECAY_TICKS) {
 332                 register struct shift_data      *shiftp;
 333
 334                 /*
 335                  *      Accumulate timesharing usage only
 336                  *      during contention for processor
 337                  *      resources.
 338                  */
 339                 if (thread->pri_shift < INT8_MAX)
 340                         thread->sched_usage += delta;
 341
 342                 thread->cpu_usage += delta + thread->cpu_delta;
 343                 thread->cpu_delta = 0;
 344
 345                 shiftp = &sched_decay_shifts[ticks];
 346                 if (shiftp->shift2 > 0) {
 347                     thread->cpu_usage =
 348                                                 (thread->cpu_usage >> shiftp->shift1) +
 349                                                 (thread->cpu_usage >> shiftp->shift2);
 350                     thread->sched_usage =
 351                                                 (thread->sched_usage >> shiftp->shift1) +
 352                                                 (thread->sched_usage >> shiftp->shift2);
 353                 }
 354                 else {
 355                     thread->cpu_usage =
 356                                                 (thread->cpu_usage >> shiftp->shift1) -
 357                                                 (thread->cpu_usage >> -(shiftp->shift2));
 358                     thread->sched_usage =
 359                                                 (thread->sched_usage >> shiftp->shift1) -
 360                                                 (thread->sched_usage >> -(shiftp->shift2));
 361                 }
 362         }
 363         else {
 364                 thread->cpu_usage = thread->cpu_delta = 0;
 365                 thread->sched_usage = 0;
 366         }
 367
 368         /*
 369          *      Check for fail-safe release.
 370          */
 371         if (    (thread->sched_mode & TH_MODE_FAILSAFE)         &&
 372                         thread->sched_stamp >= thread->safe_release             ) {
 373                 if (!(thread->safe_mode & TH_MODE_TIMESHARE)) {
 374                         if (thread->safe_mode & TH_MODE_REALTIME) {
 375                                 thread->priority = BASEPRI_RTQUEUES;
 376
 377                                 thread->sched_mode |= TH_MODE_REALTIME;
 378                         }
 379
 380                         thread->sched_mode &= ~TH_MODE_TIMESHARE;
 381
 382                         if ((thread->state & (TH_RUN|TH_IDLE)) == TH_RUN)
 383                                 sched_share_decr();
 384
 385                         if (!(thread->sched_mode & TH_MODE_ISDEPRESSED))
 386                                 set_sched_pri(thread, thread->priority);
 387                 }
 388
 389                 thread->safe_mode = 0;
 390                 thread->sched_mode &= ~TH_MODE_FAILSAFE;
 391         }
 392
 393         /*
 394          *      Recompute scheduled priority if appropriate.
 395          */
 396         if (    (thread->sched_mode & TH_MODE_TIMESHARE)        &&
 397                         !(thread->sched_mode & TH_MODE_PROMOTED)        &&
 398                         !(thread->sched_mode & TH_MODE_ISDEPRESSED)             ) {
 399                 register int            new_pri;
 400
 401                 do_priority_computation(thread, new_pri);
 402                 if (new_pri != thread->sched_pri) {
 403                         boolean_t               removed = run_queue_remove(thread);
 404
 405                         thread->sched_pri = new_pri;
 406                         if (removed)
 407                                 thread_setrun(thread, SCHED_TAILQ);
 408                 }
 409         }
 410 }