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/lock.h> 74#include <kern/macro_help.h> 75#include <kern/timer_call.h> 76#include <kern/ast.h> 77 78#define NRQS 128 /* 128 levels per run queue */ 79#define NRQBM (NRQS / 32) /* number of words per bit map */ 80 81#define MAXPRI (NRQS-1) 82#define MINPRI IDLEPRI /* lowest legal priority schedulable */ 83#define IDLEPRI 0 /* idle thread priority */ 84 85/* 86 * High-level priority assignments 87 * 88 ************************************************************************* 89 * 127 Reserved (real-time) 90 * A 91 * + 92 * (32 levels) 93 * + 94 * V 95 * 96 Reserved (real-time) 96 * 95 Kernel mode only 97 * A 98 * + 99 * (16 levels) 100 * + 101 * V 102 * 80 Kernel mode only 103 * 79 System high priority 104 * A 105 * + 106 * (16 levels) 107 * + 108 * V 109 * 64 System high priority 110 * 63 Elevated priorities 111 * A 112 * + 113 * (12 levels) 114 * + 115 * V 116 * 52 Elevated priorities 117 * 51 Elevated priorities (incl. BSD +nice) 118 * A 119 * + 120 * (20 levels) 121 * + 122 * V 123 * 32 Elevated priorities (incl. BSD +nice) 124 * 31 Default (default base for threads) 125 * 30 Lowered priorities (incl. BSD -nice) 126 * A 127 * + 128 * (20 levels) 129 * + 130 * V 131 * 11 Lowered priorities (incl. BSD -nice) 132 * 10 Lowered priorities (aged pri's) 133 * A 134 * + 135 * (11 levels) 136 * + 137 * V 138 * 0 Lowered priorities (aged pri's / idle) 139 ************************************************************************* 140 */ 141 142#define BASEPRI_RTQUEUES (BASEPRI_REALTIME + 1) /* 97 */ 143#define BASEPRI_REALTIME (MAXPRI - (NRQS / 4) + 1) /* 96 */ 144 145#define MAXPRI_KERNEL (BASEPRI_REALTIME - 1) /* 95 */ 146#define BASEPRI_PREEMPT (MAXPRI_KERNEL - 2) /* 93 */ 147#define BASEPRI_KERNEL (MINPRI_KERNEL + 1) /* 81 */ 148#define MINPRI_KERNEL (MAXPRI_KERNEL - (NRQS / 8) + 1) /* 80 */ 149 150#define MAXPRI_RESERVED (MINPRI_KERNEL - 1) /* 79 */ 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_DEFAULT (MAXPRI_USER - (NRQS / 4)) /* 31 */ 158#define MAXPRI_THROTTLE (MINPRI + 4) /* 4 */ 159#define MINPRI_USER MINPRI /* 0 */ 160 161#ifdef CONFIG_EMBEDDED 162#define DEPRESSPRI MAXPRI_THROTTLE 163#else 164#define DEPRESSPRI MINPRI /* depress priority */ 165#endif 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_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_FIXEDPRIORITY) 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_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_FIXEDPRIORITY) */ 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_TRADITIONAL) || defined(CONFIG_SCHED_PROTO) || defined(CONFIG_SCHED_FIXEDPRIORITY) 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 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/* 267 * Scheduler routines. 268 */ 269 270/* Handle quantum expiration for an executing thread */ 271extern void thread_quantum_expire( 272 timer_call_param_t processor, 273 timer_call_param_t thread); 274 275/* Context switch check for current processor */ 276extern ast_t csw_check(processor_t processor); 277 278#if defined(CONFIG_SCHED_TRADITIONAL) 279extern uint32_t std_quantum, min_std_quantum; 280extern uint32_t std_quantum_us; 281#endif 282 283extern uint32_t thread_depress_time; 284extern uint32_t default_timeshare_computation; 285extern uint32_t default_timeshare_constraint; 286 287extern uint32_t max_rt_quantum, min_rt_quantum; 288 289extern int default_preemption_rate; 290extern int default_bg_preemption_rate; 291 292#if defined(CONFIG_SCHED_TRADITIONAL) 293 294/* 295 * Age usage (1 << SCHED_TICK_SHIFT) times per second. 296 */ 297#define SCHED_TICK_SHIFT 3 298 299extern unsigned sched_tick; 300extern uint32_t sched_tick_interval; 301 302#endif /* CONFIG_SCHED_TRADITIONAL */ 303 304extern uint64_t sched_one_second_interval; 305 306/* Periodic computation of various averages */ 307extern void compute_averages(void); 308 309extern void compute_averunnable( 310 void *nrun); 311 312extern void compute_stack_target( 313 void *arg); 314 315extern void compute_memory_pressure( 316 void *arg); 317 318extern void compute_zone_gc_throttle( 319 void *arg); 320 321extern void compute_pageout_gc_throttle( 322 void *arg); 323 324extern void compute_pmap_gc_throttle( 325 void *arg); 326 327/* 328 * Conversion factor from usage 329 * to priority. 330 */ 331#if defined(CONFIG_SCHED_TRADITIONAL) 332extern uint32_t sched_pri_shift; 333extern uint32_t sched_fixed_shift; 334extern int8_t sched_load_shifts[NRQS]; 335#endif 336 337extern int32_t sched_poll_yield_shift; 338extern uint64_t sched_safe_duration; 339 340extern uint32_t sched_run_count, sched_share_count; 341extern uint32_t sched_load_average, sched_mach_factor; 342 343extern uint32_t avenrun[3], mach_factor[3]; 344 345extern uint64_t max_unsafe_computation; 346extern uint64_t max_poll_computation; 347 348#define sched_run_incr() \ 349MACRO_BEGIN \ 350 hw_atomic_add(&sched_run_count, 1); \ 351MACRO_END 352 353#define sched_run_decr() \ 354MACRO_BEGIN \ 355 hw_atomic_sub(&sched_run_count, 1); \ 356MACRO_END 357 358#define sched_share_incr() \ 359MACRO_BEGIN \ 360 (void)hw_atomic_add(&sched_share_count, 1); \ 361MACRO_END 362 363#define sched_share_decr() \ 364MACRO_BEGIN \ 365 (void)hw_atomic_sub(&sched_share_count, 1); \ 366MACRO_END 367 368/* 369 * thread_timer_delta macro takes care of both thread timers. 370 */ 371#define thread_timer_delta(thread, delta) \ 372MACRO_BEGIN \ 373 (delta) = (typeof(delta))timer_delta(&(thread)->system_timer, \ 374 &(thread)->system_timer_save); \ 375 (delta) += (typeof(delta))timer_delta(&(thread)->user_timer, \ 376 &(thread)->user_timer_save); \ 377MACRO_END 378 379#endif /* _KERN_SCHED_H_ */ 380