osfmk/kern/priority.c

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