osfmk/kern/priority.c

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