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/smp.h> |
73 | #include <kern/queue.h> |
74 | #include <kern/macro_help.h> |
75 | #include <kern/timer_call.h> |
76 | #include <kern/ast.h> |
77 | #include <kern/kalloc.h> |
78 | #include <kern/bits.h> |
79 | |
80 | #define NRQS 128 /* 128 levels per run queue */ |
81 | |
82 | #define MAXPRI (NRQS-1) |
83 | #define MINPRI 0 /* lowest legal priority schedulable */ |
84 | #define IDLEPRI MINPRI /* idle thread priority */ |
85 | #define NOPRI -1 |
86 | |
87 | /* |
88 | * High-level priority assignments |
89 | * |
90 | ************************************************************************* |
91 | * 127 Reserved (real-time) |
92 | * A |
93 | * + |
94 | * (32 levels) |
95 | * + |
96 | * V |
97 | * 96 Reserved (real-time) |
98 | * 95 Kernel mode only |
99 | * A |
100 | * + |
101 | * (16 levels) |
102 | * + |
103 | * V |
104 | * 80 Kernel mode only |
105 | * 79 System high priority |
106 | * A |
107 | * + |
108 | * (16 levels) |
109 | * + |
110 | * V |
111 | * 64 System high priority |
112 | * 63 Elevated priorities |
113 | * A |
114 | * + |
115 | * (12 levels) |
116 | * + |
117 | * V |
118 | * 52 Elevated priorities |
119 | * 51 Elevated priorities (incl. BSD +nice) |
120 | * A |
121 | * + |
122 | * (20 levels) |
123 | * + |
124 | * V |
125 | * 32 Elevated priorities (incl. BSD +nice) |
126 | * 31 Default (default base for threads) |
127 | * 30 Lowered priorities (incl. BSD -nice) |
128 | * A |
129 | * + |
130 | * (20 levels) |
131 | * + |
132 | * V |
133 | * 11 Lowered priorities (incl. BSD -nice) |
134 | * 10 Lowered priorities (aged pri's) |
135 | * A |
136 | * + |
137 | * (11 levels) |
138 | * + |
139 | * V |
140 | * 0 Lowered priorities (aged pri's / idle) |
141 | ************************************************************************* |
142 | */ |
143 | |
144 | #define BASEPRI_RTQUEUES (BASEPRI_REALTIME + 1) /* 97 */ |
145 | #define BASEPRI_REALTIME (MAXPRI - (NRQS / 4) + 1) /* 96 */ |
146 | |
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 */ |
151 | |
152 | #define BASEPRI_KERNEL (MINPRI_KERNEL + 1) /* 81 */ |
153 | #define MINPRI_KERNEL (MAXPRI_KERNEL - (NRQS / 8) + 1) /* 80 */ |
154 | |
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 */ |
158 | |
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 */ |
169 | |
170 | #define DEPRESSPRI (MINPRI) /* depress priority */ |
171 | |
172 | #define MAXPRI_PROMOTE (MAXPRI_KERNEL) /* ceiling for mutex promotion */ |
173 | #define MINPRI_RWLOCK (BASEPRI_BACKGROUND) /* floor when holding rwlock count */ |
174 | #define MINPRI_EXEC (BASEPRI_DEFAULT) /* floor when in exec state */ |
175 | #define MINPRI_WAITQ (BASEPRI_DEFAULT) /* floor when in waitq handover state */ |
176 | |
177 | |
178 | /* Type used for thread->sched_mode and saved_mode */ |
179 | typedef enum { |
180 | TH_MODE_NONE = 0, /* unassigned, usually for saved_mode only */ |
181 | TH_MODE_REALTIME, /* time constraints supplied */ |
182 | TH_MODE_FIXED, /* use fixed priorities, no decay */ |
183 | TH_MODE_TIMESHARE, /* use timesharing algorithm */ |
184 | } sched_mode_t; |
185 | |
186 | /* Buckets used for load calculation */ |
187 | typedef enum { |
188 | TH_BUCKET_RUN = 0, /* All runnable threads */ |
189 | TH_BUCKET_FIXPRI, /* Fixed-priority */ |
190 | TH_BUCKET_SHARE_FG, /* Timeshare thread above BASEPRI_DEFAULT */ |
191 | TH_BUCKET_SHARE_DF, /* Timeshare thread between BASEPRI_DEFAULT and BASEPRI_UTILITY */ |
192 | TH_BUCKET_SHARE_UT, /* Timeshare thread between BASEPRI_UTILITY and MAXPRI_THROTTLE */ |
193 | TH_BUCKET_SHARE_BG, /* Timeshare thread between MAXPRI_THROTTLE and MINPRI */ |
194 | TH_BUCKET_MAX, |
195 | } sched_bucket_t; |
196 | |
197 | /* |
198 | * Macro to check for invalid priorities. |
199 | */ |
200 | #define invalid_pri(pri) ((pri) < MINPRI || (pri) > MAXPRI) |
201 | |
202 | struct runq_stats { |
203 | uint64_t count_sum; |
204 | uint64_t last_change_timestamp; |
205 | }; |
206 | |
207 | #if defined(CONFIG_SCHED_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO) |
208 | |
209 | struct run_queue { |
210 | int highq; /* highest runnable queue */ |
211 | bitmap_t bitmap[BITMAP_LEN(NRQS)]; /* run queue bitmap array */ |
212 | int count; /* # of threads total */ |
213 | int urgency; /* level of preemption urgency */ |
214 | queue_head_t queues[NRQS]; /* one for each priority */ |
215 | |
216 | struct runq_stats runq_stats; |
217 | }; |
218 | |
219 | inline static void |
220 | rq_bitmap_set(bitmap_t *map, u_int n) |
221 | { |
222 | assert(n < NRQS); |
223 | bitmap_set(map, n); |
224 | } |
225 | |
226 | inline static void |
227 | rq_bitmap_clear(bitmap_t *map, u_int n) |
228 | { |
229 | assert(n < NRQS); |
230 | bitmap_clear(map, n); |
231 | } |
232 | |
233 | #endif /* defined(CONFIG_SCHED_TIMESHARE_CORE) || defined(CONFIG_SCHED_PROTO) */ |
234 | |
235 | struct rt_queue { |
236 | _Atomic int count; /* # of threads total */ |
237 | queue_head_t queue; /* all runnable RT threads */ |
238 | #if __SMP__ |
239 | decl_simple_lock_data(,rt_lock) |
240 | #endif |
241 | struct runq_stats runq_stats; |
242 | }; |
243 | typedef struct rt_queue *rt_queue_t; |
244 | |
245 | #if defined(CONFIG_SCHED_GRRR_CORE) |
246 | |
247 | /* |
248 | * We map standard Mach priorities to an abstract scale that more properly |
249 | * indicates how we want processor time allocated under contention. |
250 | */ |
251 | typedef uint8_t grrr_proportional_priority_t; |
252 | typedef uint8_t grrr_group_index_t; |
253 | |
254 | #define NUM_GRRR_PROPORTIONAL_PRIORITIES 256 |
255 | #define MAX_GRRR_PROPORTIONAL_PRIORITY ((grrr_proportional_priority_t)255) |
256 | |
257 | #if 0 |
258 | #define NUM_GRRR_GROUPS 8 /* log(256) */ |
259 | #endif |
260 | |
261 | #define NUM_GRRR_GROUPS 64 /* 256/4 */ |
262 | |
263 | struct grrr_group { |
264 | queue_chain_t priority_order; /* next greatest weight group */ |
265 | grrr_proportional_priority_t minpriority; |
266 | grrr_group_index_t index; |
267 | |
268 | queue_head_t clients; |
269 | int count; |
270 | uint32_t weight; |
271 | #if 0 |
272 | uint32_t deferred_removal_weight; |
273 | #endif |
274 | uint32_t work; |
275 | thread_t current_client; |
276 | }; |
277 | |
278 | struct grrr_run_queue { |
279 | int count; |
280 | uint32_t last_rescale_tick; |
281 | struct grrr_group groups[NUM_GRRR_GROUPS]; |
282 | queue_head_t sorted_group_list; |
283 | uint32_t weight; |
284 | grrr_group_t current_group; |
285 | |
286 | struct runq_stats runq_stats; |
287 | }; |
288 | |
289 | #endif /* defined(CONFIG_SCHED_GRRR_CORE) */ |
290 | |
291 | extern int rt_runq_count(processor_set_t); |
292 | extern void rt_runq_count_incr(processor_set_t); |
293 | extern void rt_runq_count_decr(processor_set_t); |
294 | |
295 | #if defined(CONFIG_SCHED_MULTIQ) |
296 | sched_group_t sched_group_create(void); |
297 | void sched_group_destroy(sched_group_t sched_group); |
298 | #endif /* defined(CONFIG_SCHED_MULTIQ) */ |
299 | |
300 | |
301 | |
302 | /* |
303 | * Scheduler routines. |
304 | */ |
305 | |
306 | /* Handle quantum expiration for an executing thread */ |
307 | extern void thread_quantum_expire( |
308 | timer_call_param_t processor, |
309 | timer_call_param_t thread); |
310 | |
311 | /* Context switch check for current processor */ |
312 | extern ast_t csw_check(processor_t processor, |
313 | ast_t check_reason); |
314 | |
315 | extern void sched_update_generation_count(void); |
316 | |
317 | #if defined(CONFIG_SCHED_TIMESHARE_CORE) |
318 | extern uint32_t std_quantum, min_std_quantum; |
319 | extern uint32_t std_quantum_us; |
320 | #endif /* CONFIG_SCHED_TIMESHARE_CORE */ |
321 | |
322 | extern uint32_t thread_depress_time; |
323 | extern uint32_t default_timeshare_computation; |
324 | extern uint32_t default_timeshare_constraint; |
325 | |
326 | extern uint32_t max_rt_quantum, min_rt_quantum; |
327 | |
328 | extern int default_preemption_rate; |
329 | extern int default_bg_preemption_rate; |
330 | |
331 | #if defined(CONFIG_SCHED_TIMESHARE_CORE) |
332 | |
333 | /* |
334 | * Age usage at approximately (1 << SCHED_TICK_SHIFT) times per second |
335 | * Aging may be deferred during periods where all processors are idle |
336 | * and cumulatively applied during periods of activity. |
337 | */ |
338 | #define SCHED_TICK_SHIFT 3 |
339 | #define SCHED_TICK_MAX_DELTA (8) |
340 | |
341 | extern unsigned sched_tick; |
342 | extern uint32_t sched_tick_interval; |
343 | |
344 | #endif /* CONFIG_SCHED_TIMESHARE_CORE */ |
345 | |
346 | extern uint64_t sched_one_second_interval; |
347 | |
348 | /* Periodic computation of various averages */ |
349 | extern void compute_sched_load(void); |
350 | |
351 | extern void compute_averages(uint64_t); |
352 | |
353 | extern void compute_averunnable( |
354 | void *nrun); |
355 | |
356 | extern void compute_stack_target( |
357 | void *arg); |
358 | |
359 | extern void compute_pageout_gc_throttle( |
360 | void *arg); |
361 | |
362 | extern void compute_pmap_gc_throttle( |
363 | void *arg); |
364 | |
365 | /* |
366 | * Conversion factor from usage |
367 | * to priority. |
368 | */ |
369 | #if defined(CONFIG_SCHED_TIMESHARE_CORE) |
370 | |
371 | #define MAX_LOAD (NRQS - 1) |
372 | extern uint32_t sched_pri_shifts[TH_BUCKET_MAX]; |
373 | extern uint32_t sched_fixed_shift; |
374 | extern int8_t sched_load_shifts[NRQS]; |
375 | extern uint32_t sched_decay_usage_age_factor; |
376 | void sched_timeshare_consider_maintenance(uint64_t ctime); |
377 | #endif /* CONFIG_SCHED_TIMESHARE_CORE */ |
378 | |
379 | void sched_consider_recommended_cores(uint64_t ctime, thread_t thread); |
380 | |
381 | extern int32_t sched_poll_yield_shift; |
382 | extern uint64_t sched_safe_duration; |
383 | |
384 | extern uint32_t sched_load_average, sched_mach_factor; |
385 | |
386 | extern uint32_t avenrun[3], mach_factor[3]; |
387 | |
388 | extern uint64_t max_unsafe_computation; |
389 | extern uint64_t max_poll_computation; |
390 | |
391 | extern volatile uint32_t sched_run_buckets[TH_BUCKET_MAX]; |
392 | |
393 | extern uint32_t sched_run_incr(thread_t thread); |
394 | extern uint32_t sched_run_decr(thread_t thread); |
395 | |
396 | /* |
397 | * thread_timer_delta macro takes care of both thread timers. |
398 | */ |
399 | #define thread_timer_delta(thread, delta) \ |
400 | MACRO_BEGIN \ |
401 | (delta) = (typeof(delta))timer_delta(&(thread)->system_timer, \ |
402 | &(thread)->system_timer_save); \ |
403 | (delta) += (typeof(delta))timer_delta(&(thread)->user_timer, \ |
404 | &(thread)->user_timer_save); \ |
405 | MACRO_END |
406 | |
407 | #endif /* _KERN_SCHED_H_ */ |
408 | |