]> git.saurik.com Git - apple/xnu.git/blame - osfmk/kern/priority.c
xnu-792.17.14.tar.gz
[apple/xnu.git] / osfmk / kern / priority.c
CommitLineData
1c79356b 1/*
91447636 2 * Copyright (c) 2000-2004 Apple Computer, Inc. All rights reserved.
1c79356b 3 *
8f6c56a5 4 * @APPLE_OSREFERENCE_LICENSE_HEADER_START@
1c79356b 5 *
8f6c56a5
A
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
8ad349bb 24 * limitations under the License.
8f6c56a5
A
25 *
26 * @APPLE_OSREFERENCE_LICENSE_HEADER_END@
1c79356b
A
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: clock_prim.c
60 * Author: Avadis Tevanian, Jr.
61 * Date: 1986
62 *
63 * Clock primitives.
64 */
65
1c79356b
A
66#include <mach/boolean.h>
67#include <mach/kern_return.h>
68#include <mach/machine.h>
69#include <kern/host.h>
70#include <kern/mach_param.h>
71#include <kern/sched.h>
72#include <kern/spl.h>
73#include <kern/thread.h>
74#include <kern/processor.h>
75#include <machine/machparam.h>
1c79356b
A
76
77/*
0b4e3aa0 78 * thread_quantum_expire:
1c79356b
A
79 *
80 * Recalculate the quantum and priority for a thread.
1c79356b
A
81 */
82
83void
0b4e3aa0
A
84thread_quantum_expire(
85 timer_call_param_t p0,
86 timer_call_param_t p1)
1c79356b 87{
0b4e3aa0
A
88 register processor_t myprocessor = p0;
89 register thread_t thread = p1;
1c79356b
A
90 spl_t s;
91
0b4e3aa0
A
92 s = splsched();
93 thread_lock(thread);
1c79356b
A
94
95 /*
9bccf70c 96 * Check for fail-safe trip.
1c79356b 97 */
0b4e3aa0 98 if (!(thread->sched_mode & TH_MODE_TIMESHARE)) {
0b4e3aa0
A
99 uint64_t new_computation;
100
101 new_computation = myprocessor->quantum_end;
102 new_computation -= thread->computation_epoch;
9bccf70c 103 if (new_computation + thread->computation_metered >
0b4e3aa0 104 max_unsafe_computation) {
0b4e3aa0
A
105
106 if (thread->sched_mode & TH_MODE_REALTIME) {
9bccf70c 107 thread->priority = DEPRESSPRI;
0b4e3aa0
A
108
109 thread->safe_mode |= TH_MODE_REALTIME;
110 thread->sched_mode &= ~TH_MODE_REALTIME;
111 }
1c79356b 112
55e303ae
A
113 pset_share_incr(thread->processor_set);
114
0b4e3aa0
A
115 thread->safe_release = sched_tick + sched_safe_duration;
116 thread->sched_mode |= (TH_MODE_FAILSAFE|TH_MODE_TIMESHARE);
9bccf70c 117 thread->sched_mode &= ~TH_MODE_PREEMPT;
0b4e3aa0
A
118 }
119 }
1c79356b
A
120
121 /*
9bccf70c 122 * Recompute scheduled priority if appropriate.
1c79356b 123 */
0b4e3aa0
A
124 if (thread->sched_stamp != sched_tick)
125 update_priority(thread);
126 else
9bccf70c 127 if (thread->sched_mode & TH_MODE_TIMESHARE) {
91447636
A
128 register uint32_t delta;
129
130 thread_timer_delta(thread, delta);
131
132 /*
133 * Accumulate timesharing usage only
134 * during contention for processor
135 * resources.
136 */
137 if (thread->pri_shift < INT8_MAX)
138 thread->sched_usage += delta;
139
140 thread->cpu_delta += delta;
9bccf70c
A
141
142 /*
143 * Adjust the scheduled priority if
144 * the thread has not been promoted
145 * and is not depressed.
146 */
147 if ( !(thread->sched_mode & TH_MODE_PROMOTED) &&
148 !(thread->sched_mode & TH_MODE_ISDEPRESSED) )
149 compute_my_priority(thread);
0b4e3aa0 150 }
1c79356b 151
0b4e3aa0
A
152 /*
153 * This quantum is up, give this thread another.
154 */
55e303ae
A
155 if (first_timeslice(myprocessor))
156 myprocessor->timeslice--;
1c79356b 157
55e303ae 158 thread_quantum_init(thread);
0b4e3aa0
A
159 myprocessor->quantum_end += thread->current_quantum;
160 timer_call_enter1(&myprocessor->quantum_timer,
161 thread, myprocessor->quantum_end);
1c79356b 162
0b4e3aa0 163 thread_unlock(thread);
1c79356b 164
0b4e3aa0
A
165 /*
166 * Check for and schedule ast if needed.
167 */
9bccf70c
A
168 ast_check(myprocessor);
169
170 splx(s);
1c79356b 171}
91447636
A
172
173/*
174 * Define shifts for simulating (5/8) ** n
175 *
176 * Shift structures for holding update shifts. Actual computation
177 * is usage = (usage >> shift1) +/- (usage >> abs(shift2)) where the
178 * +/- is determined by the sign of shift 2.
179 */
180struct shift_data {
181 int shift1;
182 int shift2;
183};
184
185#define SCHED_DECAY_TICKS 32
186static struct shift_data sched_decay_shifts[SCHED_DECAY_TICKS] = {
187 {1,1},{1,3},{1,-3},{2,-7},{3,5},{3,-5},{4,-8},{5,7},
188 {5,-7},{6,-10},{7,10},{7,-9},{8,-11},{9,12},{9,-11},{10,-13},
189 {11,14},{11,-13},{12,-15},{13,17},{13,-15},{14,-17},{15,19},{16,18},
190 {16,-19},{17,22},{18,20},{18,-20},{19,26},{20,22},{20,-22},{21,-27}
191};
192
193/*
194 * do_priority_computation:
195 *
196 * Calculate the timesharing priority based upon usage and load.
197 */
198#define do_priority_computation(thread, pri) \
199 MACRO_BEGIN \
200 (pri) = (thread)->priority /* start with base priority */ \
201 - ((thread)->sched_usage >> (thread)->pri_shift); \
202 if ((pri) < MINPRI_USER) \
203 (pri) = MINPRI_USER; \
204 else \
205 if ((pri) > MAXPRI_KERNEL) \
206 (pri) = MAXPRI_KERNEL; \
207 MACRO_END
208
209/*
210 * set_priority:
211 *
212 * Set the base priority of the thread
213 * and reset its scheduled priority.
214 *
215 * Called with the thread locked.
216 */
217void
218set_priority(
219 register thread_t thread,
220 register int priority)
221{
222 thread->priority = priority;
223 compute_priority(thread, FALSE);
224}
225
226/*
227 * compute_priority:
228 *
229 * Reset the scheduled priority of the thread
230 * according to its base priority if the
231 * thread has not been promoted or depressed.
232 *
233 * Called with the thread locked.
234 */
235void
236compute_priority(
237 register thread_t thread,
238 boolean_t override_depress)
239{
240 register int priority;
241
242 if ( !(thread->sched_mode & TH_MODE_PROMOTED) &&
243 (!(thread->sched_mode & TH_MODE_ISDEPRESSED) ||
244 override_depress ) ) {
245 if (thread->sched_mode & TH_MODE_TIMESHARE)
246 do_priority_computation(thread, priority);
247 else
248 priority = thread->priority;
249
250 set_sched_pri(thread, priority);
251 }
252}
253
254/*
255 * compute_my_priority:
256 *
257 * Reset the scheduled priority for
258 * a timesharing thread.
259 *
260 * Only for use on the current thread
261 * if timesharing and not depressed.
262 *
263 * Called with the thread locked.
264 */
265void
266compute_my_priority(
267 register thread_t thread)
268{
269 register int priority;
270
271 do_priority_computation(thread, priority);
272 assert(thread->runq == RUN_QUEUE_NULL);
273 thread->sched_pri = priority;
274}
275
276/*
277 * update_priority
278 *
279 * Perform housekeeping operations driven by scheduler tick.
280 *
281 * Called with the thread locked.
282 */
283void
284update_priority(
285 register thread_t thread)
286{
287 register unsigned ticks;
288 register uint32_t delta;
289
290 ticks = sched_tick - thread->sched_stamp;
291 assert(ticks != 0);
292 thread->sched_stamp += ticks;
293 thread->pri_shift = thread->processor_set->pri_shift;
294
295 /*
296 * Gather cpu usage data.
297 */
298 thread_timer_delta(thread, delta);
299 if (ticks < SCHED_DECAY_TICKS) {
300 register struct shift_data *shiftp;
301
302 /*
303 * Accumulate timesharing usage only
304 * during contention for processor
305 * resources.
306 */
307 if (thread->pri_shift < INT8_MAX)
308 thread->sched_usage += delta;
309
310 thread->cpu_usage += delta + thread->cpu_delta;
311 thread->cpu_delta = 0;
312
313 shiftp = &sched_decay_shifts[ticks];
314 if (shiftp->shift2 > 0) {
315 thread->cpu_usage =
316 (thread->cpu_usage >> shiftp->shift1) +
317 (thread->cpu_usage >> shiftp->shift2);
318 thread->sched_usage =
319 (thread->sched_usage >> shiftp->shift1) +
320 (thread->sched_usage >> shiftp->shift2);
321 }
322 else {
323 thread->cpu_usage =
324 (thread->cpu_usage >> shiftp->shift1) -
325 (thread->cpu_usage >> -(shiftp->shift2));
326 thread->sched_usage =
327 (thread->sched_usage >> shiftp->shift1) -
328 (thread->sched_usage >> -(shiftp->shift2));
329 }
330 }
331 else {
332 thread->cpu_usage = thread->cpu_delta = 0;
333 thread->sched_usage = 0;
334 }
335
336 /*
337 * Check for fail-safe release.
338 */
339 if ( (thread->sched_mode & TH_MODE_FAILSAFE) &&
340 thread->sched_stamp >= thread->safe_release ) {
341 if (!(thread->safe_mode & TH_MODE_TIMESHARE)) {
342 if (thread->safe_mode & TH_MODE_REALTIME) {
343 thread->priority = BASEPRI_RTQUEUES;
344
345 thread->sched_mode |= TH_MODE_REALTIME;
346 }
347
348 thread->sched_mode &= ~TH_MODE_TIMESHARE;
349
350 if (thread->state & TH_RUN)
351 pset_share_decr(thread->processor_set);
352
353 if (!(thread->sched_mode & TH_MODE_ISDEPRESSED))
354 set_sched_pri(thread, thread->priority);
355 }
356
357 thread->safe_mode = 0;
358 thread->sched_mode &= ~TH_MODE_FAILSAFE;
359 }
360
361 /*
362 * Recompute scheduled priority if appropriate.
363 */
364 if ( (thread->sched_mode & TH_MODE_TIMESHARE) &&
365 !(thread->sched_mode & TH_MODE_PROMOTED) &&
366 !(thread->sched_mode & TH_MODE_ISDEPRESSED) ) {
367 register int new_pri;
368
369 do_priority_computation(thread, new_pri);
370 if (new_pri != thread->sched_pri) {
371 run_queue_t runq;
372
373 runq = run_queue_remove(thread);
374 thread->sched_pri = new_pri;
375 if (runq != RUN_QUEUE_NULL)
376 thread_setrun(thread, SCHED_TAILQ);
377 }
378 }
379}