2 * Copyright (c) 2000-2009 Apple Inc. All rights reserved.
4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
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.
15 * Please obtain a copy of the License at
16 * http://www.opensource.apple.com/apsl/ and read it before using this file.
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.
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
32 * Mach Operating System
33 * Copyright (c) 1991,1990,1989,1988,1987 Carnegie Mellon University
34 * All Rights Reserved.
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.
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.
46 * Carnegie Mellon requests users of this software to return to
48 * Software Distribution Coordinator or Software.Distribution@CS.CMU.EDU
49 * School of Computer Science
50 * Carnegie Mellon University
51 * Pittsburgh PA 15213-3890
53 * any improvements or extensions that they make and grant Carnegie Mellon
54 * the rights to redistribute these changes.
60 * Author: Avadis Tevanian, Jr.
63 * Header file for scheduler.
67 #ifndef _KERN_SCHED_H_
68 #define _KERN_SCHED_H_
70 #include <mach/policy.h>
71 #include <kern/kern_types.h>
73 #include <kern/queue.h>
74 #include <kern/macro_help.h>
75 #include <kern/timer_call.h>
77 #include <kern/kalloc.h>
78 #include <kern/bits.h>
80 #define NRQS 128 /* 128 levels per run queue */
82 #define MAXPRI (NRQS-1)
83 #define MINPRI 0 /* lowest legal priority schedulable */
84 #define IDLEPRI MINPRI /* idle thread priority */
88 * High-level priority assignments
90 *************************************************************************
91 * 127 Reserved (real-time)
97 * 96 Reserved (real-time)
104 * 80 Kernel mode only
105 * 79 System high priority
111 * 64 System high priority
112 * 63 Elevated priorities
118 * 52 Elevated priorities
119 * 51 Elevated priorities (incl. BSD +nice)
125 * 32 Elevated priorities (incl. BSD +nice)
126 * 31 Default (default base for threads)
127 * 30 Lowered priorities (incl. BSD -nice)
133 * 11 Lowered priorities (incl. BSD -nice)
134 * 10 Lowered priorities (aged pri's)
140 * 0 Lowered priorities (aged pri's / idle)
141 *************************************************************************
144 #define BASEPRI_RTQUEUES (BASEPRI_REALTIME + 1) /* 97 */
145 #define BASEPRI_REALTIME (MAXPRI - (NRQS / 4) + 1) /* 96 */
147 #define MAXPRI_KERNEL (BASEPRI_REALTIME - 1) /* 95 */
148 #define BASEPRI_PREEMPT_HIGH (BASEPRI_PREEMPT + 1) /* 93 */
149 #define BASEPRI_PREEMPT (MAXPRI_KERNEL - 3) /* 92 */
150 #define BASEPRI_VM (BASEPRI_PREEMPT - 1) /* 91 */
152 #define BASEPRI_KERNEL (MINPRI_KERNEL + 1) /* 81 */
153 #define MINPRI_KERNEL (MAXPRI_KERNEL - (NRQS / 8) + 1) /* 80 */
155 #define MAXPRI_RESERVED (MINPRI_KERNEL - 1) /* 79 */
156 #define BASEPRI_GRAPHICS (MAXPRI_RESERVED - 3) /* 76 */
157 #define MINPRI_RESERVED (MAXPRI_RESERVED - (NRQS / 8) + 1) /* 64 */
159 #define MAXPRI_USER (MINPRI_RESERVED - 1) /* 63 */
160 #define BASEPRI_CONTROL (BASEPRI_DEFAULT + 17) /* 48 */
161 #define BASEPRI_FOREGROUND (BASEPRI_DEFAULT + 16) /* 47 */
162 #define BASEPRI_BACKGROUND (BASEPRI_DEFAULT + 15) /* 46 */
163 #define BASEPRI_USER_INITIATED (BASEPRI_DEFAULT + 6) /* 37 */
164 #define BASEPRI_DEFAULT (MAXPRI_USER - (NRQS / 4)) /* 31 */
165 #define MAXPRI_SUPPRESSED (BASEPRI_DEFAULT - 3) /* 28 */
166 #define BASEPRI_UTILITY (BASEPRI_DEFAULT - 11) /* 20 */
167 #define MAXPRI_THROTTLE (MINPRI + 4) /* 4 */
168 #define MINPRI_USER MINPRI /* 0 */
170 #define DEPRESSPRI MINPRI /* depress priority */
171 #define MAXPRI_PROMOTE (MAXPRI_KERNEL) /* ceiling for mutex promotion */
173 /* Type used for thread->sched_mode and saved_mode */
175 TH_MODE_NONE
= 0, /* unassigned, usually for saved_mode only */
176 TH_MODE_REALTIME
, /* time constraints supplied */
177 TH_MODE_FIXED
, /* use fixed priorities, no decay */
178 TH_MODE_TIMESHARE
, /* use timesharing algorithm */
181 /* Buckets used for load calculation */
183 TH_BUCKET_RUN
= 0, /* All runnable threads */
184 TH_BUCKET_FIXPRI
, /* Fixed-priority */
185 TH_BUCKET_SHARE_FG
, /* Timeshare thread above BASEPRI_UTILITY */
186 TH_BUCKET_SHARE_UT
, /* Timeshare thread between BASEPRI_UTILITY and MAXPRI_THROTTLE */
187 TH_BUCKET_SHARE_BG
, /* Timeshare thread between MAXPRI_THROTTLE and MINPRI */
192 * Macro to check for invalid priorities.
194 #define invalid_pri(pri) ((pri) < MINPRI || (pri) > MAXPRI)
198 uint64_t last_change_timestamp
;
201 #if defined(CONFIG_SCHED_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO)
204 int highq
; /* highest runnable queue */
205 bitmap_t bitmap
[BITMAP_LEN(NRQS
)]; /* run queue bitmap array */
206 int count
; /* # of threads total */
207 int urgency
; /* level of preemption urgency */
208 queue_head_t queues
[NRQS
]; /* one for each priority */
210 struct runq_stats runq_stats
;
214 rq_bitmap_set(bitmap_t
*map
, u_int n
)
221 rq_bitmap_clear(bitmap_t
*map
, u_int n
)
224 bitmap_clear(map
, n
);
227 #endif /* defined(CONFIG_SCHED_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO) */
230 _Atomic
int count
; /* # of threads total */
231 queue_head_t queue
; /* all runnable RT threads */
233 decl_simple_lock_data(,rt_lock
)
235 struct runq_stats runq_stats
;
237 typedef struct rt_queue
*rt_queue_t
;
239 #if defined(CONFIG_SCHED_GRRR_CORE)
242 * We map standard Mach priorities to an abstract scale that more properly
243 * indicates how we want processor time allocated under contention.
245 typedef uint8_t grrr_proportional_priority_t
;
246 typedef uint8_t grrr_group_index_t
;
248 #define NUM_GRRR_PROPORTIONAL_PRIORITIES 256
249 #define MAX_GRRR_PROPORTIONAL_PRIORITY ((grrr_proportional_priority_t)255)
252 #define NUM_GRRR_GROUPS 8 /* log(256) */
255 #define NUM_GRRR_GROUPS 64 /* 256/4 */
258 queue_chain_t priority_order
; /* next greatest weight group */
259 grrr_proportional_priority_t minpriority
;
260 grrr_group_index_t index
;
262 queue_head_t clients
;
266 uint32_t deferred_removal_weight
;
269 thread_t current_client
;
272 struct grrr_run_queue
{
274 uint32_t last_rescale_tick
;
275 struct grrr_group groups
[NUM_GRRR_GROUPS
];
276 queue_head_t sorted_group_list
;
278 grrr_group_t current_group
;
280 struct runq_stats runq_stats
;
283 #endif /* defined(CONFIG_SCHED_GRRR_CORE) */
285 extern int rt_runq_count(processor_set_t
);
286 extern void rt_runq_count_incr(processor_set_t
);
287 extern void rt_runq_count_decr(processor_set_t
);
289 #if defined(CONFIG_SCHED_MULTIQ)
290 sched_group_t
sched_group_create(void);
291 void sched_group_destroy(sched_group_t sched_group
);
292 #endif /* defined(CONFIG_SCHED_MULTIQ) */
297 * Scheduler routines.
300 /* Handle quantum expiration for an executing thread */
301 extern void thread_quantum_expire(
302 timer_call_param_t processor
,
303 timer_call_param_t thread
);
305 /* Context switch check for current processor */
306 extern ast_t
csw_check(processor_t processor
,
309 #if defined(CONFIG_SCHED_TIMESHARE_CORE)
310 extern uint32_t std_quantum
, min_std_quantum
;
311 extern uint32_t std_quantum_us
;
312 #endif /* CONFIG_SCHED_TIMESHARE_CORE */
314 extern uint32_t thread_depress_time
;
315 extern uint32_t default_timeshare_computation
;
316 extern uint32_t default_timeshare_constraint
;
318 extern uint32_t max_rt_quantum
, min_rt_quantum
;
320 extern int default_preemption_rate
;
321 extern int default_bg_preemption_rate
;
323 #if defined(CONFIG_SCHED_TIMESHARE_CORE)
326 * Age usage at approximately (1 << SCHED_TICK_SHIFT) times per second
327 * Aging may be deferred during periods where all processors are idle
328 * and cumulatively applied during periods of activity.
330 #define SCHED_TICK_SHIFT 3
331 #define SCHED_TICK_MAX_DELTA (8)
333 extern unsigned sched_tick
;
334 extern uint32_t sched_tick_interval
;
336 #endif /* CONFIG_SCHED_TIMESHARE_CORE */
338 extern uint64_t sched_one_second_interval
;
340 /* Periodic computation of various averages */
341 extern void compute_averages(uint64_t);
343 extern void compute_averunnable(
346 extern void compute_stack_target(
349 extern void compute_memory_pressure(
352 extern void compute_pageout_gc_throttle(
355 extern void compute_pmap_gc_throttle(
359 * Conversion factor from usage
362 #if defined(CONFIG_SCHED_TIMESHARE_CORE)
364 #define MAX_LOAD (NRQS - 1)
365 extern uint32_t sched_pri_shifts
[TH_BUCKET_MAX
];
366 extern uint32_t sched_fixed_shift
;
367 extern int8_t sched_load_shifts
[NRQS
];
368 extern uint32_t sched_decay_usage_age_factor
;
369 void sched_timeshare_consider_maintenance(uint64_t ctime
);
370 #endif /* CONFIG_SCHED_TIMESHARE_CORE */
372 void sched_consider_recommended_cores(uint64_t ctime
, thread_t thread
);
374 extern int32_t sched_poll_yield_shift
;
375 extern uint64_t sched_safe_duration
;
377 extern uint32_t sched_load_average
, sched_mach_factor
;
379 extern uint32_t avenrun
[3], mach_factor
[3];
381 extern uint64_t max_unsafe_computation
;
382 extern uint64_t max_poll_computation
;
384 extern volatile uint32_t sched_run_buckets
[TH_BUCKET_MAX
];
386 extern uint32_t sched_run_incr(thread_t thread
);
387 extern uint32_t sched_run_decr(thread_t thread
);
390 * thread_timer_delta macro takes care of both thread timers.
392 #define thread_timer_delta(thread, delta) \
394 (delta) = (typeof(delta))timer_delta(&(thread)->system_timer, \
395 &(thread)->system_timer_save); \
396 (delta) += (typeof(delta))timer_delta(&(thread)->user_timer, \
397 &(thread)->user_timer_save); \
400 #endif /* _KERN_SCHED_H_ */