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