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: sched.h 60 * Author: Avadis Tevanian, Jr. 61 * Date: 1985 62 * 63 * Header file for scheduler. 64 * 65 */ 66 67#ifndef _KERN_SCHED_H_ 68#define _KERN_SCHED_H_ 69 70#include <mach/policy.h> 71#include <kern/kern_types.h> 72#include <kern/queue.h> 73#include <kern/macro_help.h> 74#include <kern/timer_call.h> 75#include <kern/ast.h> 76 77#define NRQS 128 /* 128 levels per run queue */ 78#define NRQBM (NRQS / 32) /* number of words per bit map */ 79 80#define MAXPRI (NRQS-1) 81#define MINPRI IDLEPRI /* lowest legal priority schedulable */ 82#define IDLEPRI 0 /* idle thread priority */ 83 84/* 85 * High-level priority assignments 86 * 87 ************************************************************************* 88 * 127 Reserved (real-time) 89 * A 90 * + 91 * (32 levels) 92 * + 93 * V 94 * 96 Reserved (real-time) 95 * 95 Kernel mode only 96 * A 97 * + 98 * (16 levels) 99 * + 100 * V 101 * 80 Kernel mode only 102 * 79 System high priority 103 * A 104 * + 105 * (16 levels) 106 * + 107 * V 108 * 64 System high priority 109 * 63 Elevated priorities 110 * A 111 * + 112 * (12 levels) 113 * + 114 * V 115 * 52 Elevated priorities 116 * 51 Elevated priorities (incl. BSD +nice) 117 * A 118 * + 119 * (20 levels) 120 * + 121 * V 122 * 32 Elevated priorities (incl. BSD +nice) 123 * 31 Default (default base for threads) 124 * 30 Lowered priorities (incl. BSD -nice) 125 * A 126 * + 127 * (20 levels) 128 * + 129 * V 130 * 11 Lowered priorities (incl. BSD -nice) 131 * 10 Lowered priorities (aged pri's) 132 * A 133 * + 134 * (11 levels) 135 * + 136 * V 137 * 0 Lowered priorities (aged pri's / idle) 138 ************************************************************************* 139 */ 140 141#define BASEPRI_RTQUEUES (BASEPRI_REALTIME + 1) /* 97 */ 142#define BASEPRI_REALTIME (MAXPRI - (NRQS / 4) + 1) /* 96 */ 143 144#define MAXPRI_KERNEL (BASEPRI_REALTIME - 1) /* 95 */ 145#define BASEPRI_PREEMPT (MAXPRI_KERNEL - 2) /* 93 */ 146#define BASEPRI_KERNEL (MINPRI_KERNEL + 1) /* 81 */ 147#define MINPRI_KERNEL (MAXPRI_KERNEL - (NRQS / 8) + 1) /* 80 */ 148 149#define MAXPRI_RESERVED (MINPRI_KERNEL - 1) /* 79 */ 150#define BASEPRI_GRAPHICS (MAXPRI_RESERVED - 3) /* 76 */ 151#define MINPRI_RESERVED (MAXPRI_RESERVED - (NRQS / 8) + 1) /* 64 */ 152 153#define MAXPRI_USER (MINPRI_RESERVED - 1) /* 63 */ 154#define BASEPRI_CONTROL (BASEPRI_DEFAULT + 17) /* 48 */ 155#define BASEPRI_FOREGROUND (BASEPRI_DEFAULT + 16) /* 47 */ 156#define BASEPRI_BACKGROUND (BASEPRI_DEFAULT + 15) /* 46 */ 157#define BASEPRI_USER_INITIATED (BASEPRI_DEFAULT + 6) /* 37 */ 158#define BASEPRI_DEFAULT (MAXPRI_USER - (NRQS / 4)) /* 31 */ 159#define MAXPRI_SUPPRESSED (BASEPRI_DEFAULT - 3) /* 28 */ 160#define BASEPRI_UTILITY (BASEPRI_DEFAULT - 11) /* 20 */ 161#define MAXPRI_THROTTLE (MINPRI + 4) /* 4 */ 162#define MINPRI_USER MINPRI /* 0 */ 163 164#define DEPRESSPRI MINPRI /* depress priority */ 165#define MAXPRI_PROMOTE (MAXPRI_KERNEL) /* ceiling for mutex promotion */ 166 167/* Type used for thread->sched_mode and saved_mode */ 168typedef enum { 169 TH_MODE_NONE = 0, /* unassigned, usually for saved_mode only */ 170 TH_MODE_REALTIME, /* time constraints supplied */ 171 TH_MODE_FIXED, /* use fixed priorities, no decay */ 172 TH_MODE_TIMESHARE, /* use timesharing algorithm */ 173 TH_MODE_FAIRSHARE /* use fair-share scheduling */ 174} sched_mode_t; 175 176/* 177 * Macro to check for invalid priorities. 178 */ 179#define invalid_pri(pri) ((pri) < MINPRI || (pri) > MAXPRI) 180 181struct runq_stats { 182 uint64_t count_sum; 183 uint64_t last_change_timestamp; 184}; 185 186#if defined(CONFIG_SCHED_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO) 187 188struct run_queue { 189 int highq; /* highest runnable queue */ 190 int bitmap[NRQBM]; /* run queue bitmap array */ 191 int count; /* # of threads total */ 192 int urgency; /* level of preemption urgency */ 193 queue_head_t queues[NRQS]; /* one for each priority */ 194 195 struct runq_stats runq_stats; 196}; 197 198#endif /* defined(CONFIG_SCHED_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO) */ 199 200struct rt_queue { 201 int count; /* # of threads total */ 202 queue_head_t queue; /* all runnable RT threads */ 203 204 struct runq_stats runq_stats; 205}; 206 207#if defined(CONFIG_SCHED_FAIRSHARE_CORE) 208struct fairshare_queue { 209 int count; /* # of threads total */ 210 queue_head_t queue; /* all runnable threads demoted to fairshare scheduling */ 211 212 struct runq_stats runq_stats; 213}; 214#endif /* CONFIG_SCHED_FAIRSHARE_CORE */ 215 216#if defined(CONFIG_SCHED_GRRR_CORE) 217 218/* 219 * We map standard Mach priorities to an abstract scale that more properly 220 * indicates how we want processor time allocated under contention. 221 */ 222typedef uint8_t grrr_proportional_priority_t; 223typedef uint8_t grrr_group_index_t; 224 225#define NUM_GRRR_PROPORTIONAL_PRIORITIES 256 226#define MAX_GRRR_PROPORTIONAL_PRIORITY ((grrr_proportional_priority_t)255) 227 228#if 0 229#define NUM_GRRR_GROUPS 8 /* log(256) */ 230#endif 231 232#define NUM_GRRR_GROUPS 64 /* 256/4 */ 233 234struct grrr_group { 235 queue_chain_t priority_order; /* next greatest weight group */ 236 grrr_proportional_priority_t minpriority; 237 grrr_group_index_t index; 238 239 queue_head_t clients; 240 int count; 241 uint32_t weight; 242#if 0 243 uint32_t deferred_removal_weight; 244#endif 245 uint32_t work; 246 thread_t current_client; 247}; 248 249struct grrr_run_queue { 250 int count; 251 uint32_t last_rescale_tick; 252 struct grrr_group groups[NUM_GRRR_GROUPS]; 253 queue_head_t sorted_group_list; 254 uint32_t weight; 255 grrr_group_t current_group; 256 257 struct runq_stats runq_stats; 258}; 259 260#endif /* defined(CONFIG_SCHED_GRRR_CORE) */ 261 262#define first_timeslice(processor) ((processor)->timeslice > 0) 263 264extern struct rt_queue rt_runq; 265 266#if defined(CONFIG_SCHED_MULTIQ) 267sched_group_t sched_group_create(void); 268void sched_group_destroy(sched_group_t sched_group); 269 270extern boolean_t sched_groups_enabled; 271 272#endif /* defined(CONFIG_SCHED_MULTIQ) */ 273 274/* 275 * Scheduler routines. 276 */ 277 278/* Handle quantum expiration for an executing thread */ 279extern void thread_quantum_expire( 280 timer_call_param_t processor, 281 timer_call_param_t thread); 282 283/* Context switch check for current processor */ 284extern ast_t csw_check(processor_t processor, 285 ast_t check_reason); 286 287#if defined(CONFIG_SCHED_TIMESHARE_CORE) 288extern uint32_t std_quantum, min_std_quantum; 289extern uint32_t std_quantum_us; 290#endif /* CONFIG_SCHED_TIMESHARE_CORE */ 291 292extern uint32_t thread_depress_time; 293extern uint32_t default_timeshare_computation; 294extern uint32_t default_timeshare_constraint; 295 296extern uint32_t max_rt_quantum, min_rt_quantum; 297 298extern int default_preemption_rate; 299extern int default_bg_preemption_rate; 300 301#if defined(CONFIG_SCHED_TIMESHARE_CORE) 302 303/* 304 * Age usage at approximately (1 << SCHED_TICK_SHIFT) times per second 305 * Aging may be deferred during periods where all processors are idle 306 * and cumulatively applied during periods of activity. 307 */ 308#define SCHED_TICK_SHIFT 3 309#define SCHED_TICK_MAX_DELTA (8) 310 311extern unsigned sched_tick; 312extern uint32_t sched_tick_interval; 313 314#endif /* CONFIG_SCHED_TIMESHARE_CORE */ 315 316extern uint64_t sched_one_second_interval; 317 318/* Periodic computation of various averages */ 319extern void compute_averages(uint64_t); 320 321extern void compute_averunnable( 322 void *nrun); 323 324extern void compute_stack_target( 325 void *arg); 326 327extern void compute_memory_pressure( 328 void *arg); 329 330extern void compute_zone_gc_throttle( 331 void *arg); 332 333extern void compute_pageout_gc_throttle( 334 void *arg); 335 336extern void compute_pmap_gc_throttle( 337 void *arg); 338 339/* 340 * Conversion factor from usage 341 * to priority. 342 */ 343#if defined(CONFIG_SCHED_TIMESHARE_CORE) 344extern uint32_t sched_pri_shift; 345extern uint32_t sched_background_pri_shift; 346extern uint32_t sched_combined_fgbg_pri_shift; 347extern uint32_t sched_fixed_shift; 348extern int8_t sched_load_shifts[NRQS]; 349extern uint32_t sched_decay_usage_age_factor; 350extern uint32_t sched_use_combined_fgbg_decay; 351void sched_traditional_consider_maintenance(uint64_t); 352#endif /* CONFIG_SCHED_TIMESHARE_CORE */ 353 354extern int32_t sched_poll_yield_shift; 355extern uint64_t sched_safe_duration; 356 357extern uint32_t sched_run_count, sched_share_count, sched_background_count; 358extern uint32_t sched_load_average, sched_mach_factor; 359 360extern uint32_t avenrun[3], mach_factor[3]; 361 362extern uint64_t max_unsafe_computation; 363extern uint64_t max_poll_computation; 364 365/* TH_RUN & !TH_IDLE controls whether a thread has a run count */ 366#define sched_run_incr(th) \ 367 hw_atomic_add(&sched_run_count, 1) \ 368 369#define sched_run_decr(th) \ 370 hw_atomic_sub(&sched_run_count, 1) \ 371 372#if MACH_ASSERT 373extern void sched_share_incr(thread_t thread); 374extern void sched_share_decr(thread_t thread); 375extern void sched_background_incr(thread_t thread); 376extern void sched_background_decr(thread_t thread); 377 378extern void assert_thread_sched_count(thread_t thread); 379 380#else /* MACH_ASSERT */ 381/* sched_mode == TH_MODE_TIMESHARE controls whether a thread has a timeshare count when it has a run count */ 382#define sched_share_incr(th) \ 383MACRO_BEGIN \ 384 (void)hw_atomic_add(&sched_share_count, 1); \ 385MACRO_END 386 387#define sched_share_decr(th) \ 388MACRO_BEGIN \ 389 (void)hw_atomic_sub(&sched_share_count, 1); \ 390MACRO_END 391 392/* TH_SFLAG_THROTTLED controls whether a thread has a background count when it has a run count and a share count */ 393#define sched_background_incr(th) \ 394MACRO_BEGIN \ 395 hw_atomic_add(&sched_background_count, 1); \ 396MACRO_END 397 398#define sched_background_decr(th) \ 399MACRO_BEGIN \ 400 hw_atomic_sub(&sched_background_count, 1); \ 401MACRO_END 402 403#define assert_thread_sched_count(th) \ 404MACRO_BEGIN \ 405MACRO_END 406 407#endif /* !MACH_ASSERT */ 408 409/* 410 * thread_timer_delta macro takes care of both thread timers. 411 */ 412#define thread_timer_delta(thread, delta) \ 413MACRO_BEGIN \ 414 (delta) = (typeof(delta))timer_delta(&(thread)->system_timer, \ 415 &(thread)->system_timer_save); \ 416 (delta) += (typeof(delta))timer_delta(&(thread)->user_timer, \ 417 &(thread)->user_timer_save); \ 418MACRO_END 419 420#endif /* _KERN_SCHED_H_ */ 421