]> git.saurik.com Git - apple/xnu.git/blob - osfmk/kern/sched.h
xnu-2050.24.15.tar.gz
[apple/xnu.git] / osfmk / kern / sched.h
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 */
168 typedef 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
181 struct 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
188 struct 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
200 struct 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)
208 struct 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 */
222 typedef uint8_t grrr_proportional_priority_t;
223 typedef 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
234 struct 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
249 struct 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
264 extern struct rt_queue rt_runq;
265
266 /*
267 * Scheduler routines.
268 */
269
270 /* Handle quantum expiration for an executing thread */
271 extern void thread_quantum_expire(
272 timer_call_param_t processor,
273 timer_call_param_t thread);
274
275 /* Context switch check for current processor */
276 extern ast_t csw_check(processor_t processor);
277
278 #if defined(CONFIG_SCHED_TRADITIONAL)
279 extern uint32_t std_quantum, min_std_quantum;
280 extern uint32_t std_quantum_us;
281 #endif
282
283 extern uint32_t thread_depress_time;
284 extern uint32_t default_timeshare_computation;
285 extern uint32_t default_timeshare_constraint;
286
287 extern uint32_t max_rt_quantum, min_rt_quantum;
288
289 extern int default_preemption_rate;
290 extern 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
299 extern unsigned sched_tick;
300 extern uint32_t sched_tick_interval;
301
302 #endif /* CONFIG_SCHED_TRADITIONAL */
303
304 extern uint64_t sched_one_second_interval;
305
306 /* Periodic computation of various averages */
307 extern void compute_averages(void);
308
309 extern void compute_averunnable(
310 void *nrun);
311
312 extern void compute_stack_target(
313 void *arg);
314
315 extern void compute_memory_pressure(
316 void *arg);
317
318 extern void compute_zone_gc_throttle(
319 void *arg);
320
321 extern void compute_pageout_gc_throttle(
322 void *arg);
323
324 extern 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)
332 extern uint32_t sched_pri_shift;
333 extern uint32_t sched_fixed_shift;
334 extern int8_t sched_load_shifts[NRQS];
335 #endif
336
337 extern int32_t sched_poll_yield_shift;
338 extern uint64_t sched_safe_duration;
339
340 extern uint32_t sched_run_count, sched_share_count;
341 extern uint32_t sched_load_average, sched_mach_factor;
342
343 extern uint32_t avenrun[3], mach_factor[3];
344
345 extern uint64_t max_unsafe_computation;
346 extern uint64_t max_poll_computation;
347
348 #define sched_run_incr() \
349 MACRO_BEGIN \
350 hw_atomic_add(&sched_run_count, 1); \
351 MACRO_END
352
353 #define sched_run_decr() \
354 MACRO_BEGIN \
355 hw_atomic_sub(&sched_run_count, 1); \
356 MACRO_END
357
358 #define sched_share_incr() \
359 MACRO_BEGIN \
360 (void)hw_atomic_add(&sched_share_count, 1); \
361 MACRO_END
362
363 #define sched_share_decr() \
364 MACRO_BEGIN \
365 (void)hw_atomic_sub(&sched_share_count, 1); \
366 MACRO_END
367
368 /*
369 * thread_timer_delta macro takes care of both thread timers.
370 */
371 #define thread_timer_delta(thread, delta) \
372 MACRO_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); \
377 MACRO_END
378
379 #endif /* _KERN_SCHED_H_ */