osfmk/kern/priority.c

   1 /*
   2  * Copyright (c) 2000-2004 Apple Computer, 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
  83 void
  84 thread_quantum_expire(
  85         timer_call_param_t      p0,
  86         timer_call_param_t      p1)
  87 {
  88         register processor_t            myprocessor = p0;
  89         register thread_t                       thread = p1;
  90         spl_t                                           s;
  91
  92         s = splsched();
  93         thread_lock(thread);
  94
  95         /*
  96          *      Check for fail-safe trip.
  97          */
  98         if (!(thread->sched_mode & TH_MODE_TIMESHARE)) {
  99                 uint64_t                        new_computation;
 100
 101                 new_computation = myprocessor->quantum_end;
 102                 new_computation -= thread->computation_epoch;
 103                 if (new_computation + thread->computation_metered >
 104                                                                                         max_unsafe_computation) {
 105
 106                         if (thread->sched_mode & TH_MODE_REALTIME) {
 107                                 thread->priority = DEPRESSPRI;
 108
 109                                 thread->safe_mode |= TH_MODE_REALTIME;
 110                                 thread->sched_mode &= ~TH_MODE_REALTIME;
 111                         }
 112
 113                         pset_share_incr(thread->processor_set);
 114
 115                         thread->safe_release = sched_tick + sched_safe_duration;
 116                         thread->sched_mode |= (TH_MODE_FAILSAFE|TH_MODE_TIMESHARE);
 117                         thread->sched_mode &= ~TH_MODE_PREEMPT;
 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         /*
 153          *      This quantum is up, give this thread another.
 154          */
 155         if (first_timeslice(myprocessor))
 156                 myprocessor->timeslice--;
 157
 158         thread_quantum_init(thread);
 159         myprocessor->quantum_end += thread->current_quantum;
 160         timer_call_enter1(&myprocessor->quantum_timer,
 161                                                         thread, myprocessor->quantum_end);
 162
 163         thread_unlock(thread);
 164
 165         /*
 166          * Check for and schedule ast if needed.
 167          */
 168         ast_check(myprocessor);
 169
 170         splx(s);
 171 }
 172
 173 /*
 174  *      Define shifts for simulating (5/8) ** n
 175  *
 176  *      Shift structures for holding update shifts.  Actual computation
 177  *      is  usage = (usage >> shift1) +/- (usage >> abs(shift2))  where the
 178  *      +/- is determined by the sign of shift 2.
 179  */
 180 struct shift_data {
 181         int     shift1;
 182         int     shift2;
 183 };
 184
 185 #define SCHED_DECAY_TICKS       32
 186 static struct shift_data        sched_decay_shifts[SCHED_DECAY_TICKS] = {
 187         {1,1},{1,3},{1,-3},{2,-7},{3,5},{3,-5},{4,-8},{5,7},
 188         {5,-7},{6,-10},{7,10},{7,-9},{8,-11},{9,12},{9,-11},{10,-13},
 189         {11,14},{11,-13},{12,-15},{13,17},{13,-15},{14,-17},{15,19},{16,18},
 190         {16,-19},{17,22},{18,20},{18,-20},{19,26},{20,22},{20,-22},{21,-27}
 191 };
 192
 193 /*
 194  *      do_priority_computation:
 195  *
 196  *      Calculate the timesharing priority based upon usage and load.
 197  */
 198 #define do_priority_computation(thread, pri)                                                    \
 199         MACRO_BEGIN                                                                                                                     \
 200         (pri) = (thread)->priority              /* start with base priority */          \
 201             - ((thread)->sched_usage >> (thread)->pri_shift);                           \
 202         if ((pri) < MINPRI_USER)                                                                                        \
 203                 (pri) = MINPRI_USER;                                                                                    \
 204         else                                                                                                                            \
 205         if ((pri) > MAXPRI_KERNEL)                                                                                      \
 206                 (pri) = MAXPRI_KERNEL;                                                                                  \
 207         MACRO_END
 208
 209 /*
 210  *      set_priority:
 211  *
 212  *      Set the base priority of the thread
 213  *      and reset its scheduled priority.
 214  *
 215  *      Called with the thread locked.
 216  */
 217 void
 218 set_priority(
 219         register thread_t       thread,
 220         register int            priority)
 221 {
 222         thread->priority = priority;
 223         compute_priority(thread, FALSE);
 224 }
 225
 226 /*
 227  *      compute_priority:
 228  *
 229  *      Reset the scheduled priority of the thread
 230  *      according to its base priority if the
 231  *      thread has not been promoted or depressed.
 232  *
 233  *      Called with the thread locked.
 234  */
 235 void
 236 compute_priority(
 237         register thread_t       thread,
 238         boolean_t                       override_depress)
 239 {
 240         register int            priority;
 241
 242         if (    !(thread->sched_mode & TH_MODE_PROMOTED)                        &&
 243                         (!(thread->sched_mode & TH_MODE_ISDEPRESSED)    ||
 244                                  override_depress                                                       )               ) {
 245                 if (thread->sched_mode & TH_MODE_TIMESHARE)
 246                         do_priority_computation(thread, priority);
 247                 else
 248                         priority = thread->priority;
 249
 250                 set_sched_pri(thread, priority);
 251         }
 252 }
 253
 254 /*
 255  *      compute_my_priority:
 256  *
 257  *      Reset the scheduled priority for
 258  *      a timesharing thread.
 259  *
 260  *      Only for use on the current thread
 261  *      if timesharing and not depressed.
 262  *
 263  *      Called with the thread locked.
 264  */
 265 void
 266 compute_my_priority(
 267         register thread_t       thread)
 268 {
 269         register int            priority;
 270
 271         do_priority_computation(thread, priority);
 272         assert(thread->runq == RUN_QUEUE_NULL);
 273         thread->sched_pri = priority;
 274 }
 275
 276 /*
 277  *      update_priority
 278  *
 279  *      Perform housekeeping operations driven by scheduler tick.
 280  *
 281  *      Called with the thread locked.
 282  */
 283 void
 284 update_priority(
 285         register thread_t       thread)
 286 {
 287         register unsigned       ticks;
 288         register uint32_t       delta;
 289
 290         ticks = sched_tick - thread->sched_stamp;
 291         assert(ticks != 0);
 292         thread->sched_stamp += ticks;
 293         thread->pri_shift = thread->processor_set->pri_shift;
 294
 295         /*
 296          *      Gather cpu usage data.
 297          */
 298         thread_timer_delta(thread, delta);
 299         if (ticks < SCHED_DECAY_TICKS) {
 300                 register struct shift_data      *shiftp;
 301
 302                 /*
 303                  *      Accumulate timesharing usage only
 304                  *      during contention for processor
 305                  *      resources.
 306                  */
 307                 if (thread->pri_shift < INT8_MAX)
 308                         thread->sched_usage += delta;
 309
 310                 thread->cpu_usage += delta + thread->cpu_delta;
 311                 thread->cpu_delta = 0;
 312
 313                 shiftp = &sched_decay_shifts[ticks];
 314                 if (shiftp->shift2 > 0) {
 315                     thread->cpu_usage =
 316                                                 (thread->cpu_usage >> shiftp->shift1) +
 317                                                 (thread->cpu_usage >> shiftp->shift2);
 318                     thread->sched_usage =
 319                                                 (thread->sched_usage >> shiftp->shift1) +
 320                                                 (thread->sched_usage >> shiftp->shift2);
 321                 }
 322                 else {
 323                     thread->cpu_usage =
 324                                                 (thread->cpu_usage >> shiftp->shift1) -
 325                                                 (thread->cpu_usage >> -(shiftp->shift2));
 326                     thread->sched_usage =
 327                                                 (thread->sched_usage >> shiftp->shift1) -
 328                                                 (thread->sched_usage >> -(shiftp->shift2));
 329                 }
 330         }
 331         else {
 332                 thread->cpu_usage = thread->cpu_delta = 0;
 333                 thread->sched_usage = 0;
 334         }
 335
 336         /*
 337          *      Check for fail-safe release.
 338          */
 339         if (    (thread->sched_mode & TH_MODE_FAILSAFE)         &&
 340                         thread->sched_stamp >= thread->safe_release             ) {
 341                 if (!(thread->safe_mode & TH_MODE_TIMESHARE)) {
 342                         if (thread->safe_mode & TH_MODE_REALTIME) {
 343                                 thread->priority = BASEPRI_RTQUEUES;
 344
 345                                 thread->sched_mode |= TH_MODE_REALTIME;
 346                         }
 347
 348                         thread->sched_mode &= ~TH_MODE_TIMESHARE;
 349
 350                         if (thread->state & TH_RUN)
 351                                 pset_share_decr(thread->processor_set);
 352
 353                         if (!(thread->sched_mode & TH_MODE_ISDEPRESSED))
 354                                 set_sched_pri(thread, thread->priority);
 355                 }
 356
 357                 thread->safe_mode = 0;
 358                 thread->sched_mode &= ~TH_MODE_FAILSAFE;
 359         }
 360
 361         /*
 362          *      Recompute scheduled priority if appropriate.
 363          */
 364         if (    (thread->sched_mode & TH_MODE_TIMESHARE)        &&
 365                         !(thread->sched_mode & TH_MODE_PROMOTED)        &&
 366                         !(thread->sched_mode & TH_MODE_ISDEPRESSED)             ) {
 367                 register int            new_pri;
 368
 369                 do_priority_computation(thread, new_pri);
 370                 if (new_pri != thread->sched_pri) {
 371                         run_queue_t             runq;
 372
 373                         runq = run_queue_remove(thread);
 374                         thread->sched_pri = new_pri;
 375                         if (runq != RUN_QUEUE_NULL)
 376                                 thread_setrun(thread, SCHED_TAILQ);
 377                 }
 378         }
 379 }